This is the mail archive of the
mailing list for the GCC project.
Register Allocation with Instruction Scheduling.
- From: Ajit Kumar Agarwal <ajit dot kumar dot agarwal at xilinx dot com>
- To: "vmakarov at redhat dot com" <vmakarov at redhat dot com>, "law at redhat dot com" <law at redhat dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Cc: Vinod Kathail <vinodk at xilinx dot com>, Shail Aditya Gupta <shailadi at xilinx dot com>, Vidhumouli Hunsigida <vidhum at xilinx dot com>, "Nagaraju Mekala" <nmekala at xilinx dot com>
- Date: Sun, 21 Dec 2014 19:43:00 +0000
- Subject: Register Allocation with Instruction Scheduling.
- Authentication-results: sourceware.org; auth=none
- Authentication-results: spf=pass (sender IP is 126.96.36.199) smtp dot mailfrom=ajit dot kumar dot agarwal at xilinx dot com;
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