1. A compiler, which converts into a machine language the source code of a program written in a programming language and optimizes said program, comprising: a DAG analysis unit for constructing and analyzing a DAG for an instruction in a program to be processed; an interference graph construction unit for employing the analysis results obtained by said DAG analysis unit to construct an interference graph representing the probability that an interference will occur between variables used by said instruction; and a graph identifier for allocating registers for said instruction based on said interference graph that is constructed by said interference graph construction unit, wherein, when the overall time for executing said program is extended unless predetermined multiple instructions are executed in parallel, said interference graph construction unit assumes that an interference has occurred among variables used by said multiple instructions, and constructs said interference graph.