A computer, computer compiler and method for reducing the number of
interferences between variables during graph coloring while maintaining
the possibility that the instructions will be executed in parallel. A
compiler, which converts into a machine language the source code of a
program written in a programming language and optimizes the program
includes: a directed acyclic graph DAG analysis unit 11 for constructing
and analyzing a DAG for an instruction in a program to be processed; an
interference graph construction unit 12 for employing the analysis
results to construct an interference graph representing the probability
that an interference will occur between variables used by the
instructions; and a graph coloring unit 13 for allocating registers for
the instruction based on the interference graph that is constructed.