The present invention describes a method of efficiently optimizing instruction
scheduling and register allocation in a post optimizer. The method removes false
register dependencies between pipelined instructions by building an incremental
(partial) interference graph of register allocation for scheduled instructions.
False dependency graph indicates the amount of parallelism in the data flow graph.
The incremental interference graph uses a mix of virtual and physical registers.
The interference graph is built incrementally as an instruction schedular schedules
each instruction. The optimization is done incrementally on localized code. The
physical register mapping is maximized and virtual registers are created on demand basis.