Register Allocation with Instruction Scheduling.

[Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>]

Hello All:

I was going through the following article

" Register Allocation with instruction scheduling:  a new approach" by Pinter etal.

The phase ordering of register allocation and Instruction scheduling is important topic. The scheduling before register allocator 
 increases the register pressure whereas the instruction scheduling after register allocation will be seeing the false dependencies
created by Register allocator. The false dependencies between the instructions will not be able to schedule the two instruction 
simultaneously reducing the Instruction Level Parallelism. To achieve better ILP for the instruction scheduling after register
allocation the false dependencies created by the register allocator should be reduced.

Let Gs(V,E) is the scheduling Graph  and G'(V,E) is the Scheduling Graph after the register allocation. The Graph G'(V,E) has 
the false dependencies created by Register Allocator Another graph is created with Gf(V,E) where the edges represents
the false dependencies. To make sure the  false dependencies Graph which is the complement of Gs(V,E) and the edges
of Gf are the intersection of the edge in the G'(V,E) and the edges in the complement of Gs scheduling graph. 

With the availability of the  false dependencies graph and the interference graph, The edges in the interference graph
doesn't  intersects with the edges in the false dependencies graph, this edge will be added to the interference graph 
and since this edge interfere and the assigning phase will assign different register. Thus the false dependencies can be
removed and the scheduling graph after the register allocator will not have false dependencies and the better ILP and 
scheduling is achieved. This overcomes the disadvantages of instruction scheduling after register allocator.

This looks feasible to implement in GCC and I would like to implement the above if not done in the GCC.

Please let me know what do you think.

Thanks & Regards
Ajit