Proposal of new Unrolling degree before/after the allocated Register Allocation is done in GCC.

Ajit Kumar Agarwal
Sat Jun 13 13:49:00 GMT 2015


Given a Data Dependency Graph(DDG) the unrolling degree proposed by Monica Lam calculates the unrolling degree as follows.

Unrolling degree = Length of Longest Live range/ Number of cycles in the kernel ( Initiation Interval). The unrolling degree based on the 
Above leads to more register Spills and Fetch inside the Loops.

Given the Data Dependency Graph(DDG) and the unrolling degree calculated as above we build the reuse graph. Lot has been presented 
On the Reuse graph. Each node nodes labelled the DDG nodes that writes into registers and the arc(u,v) represents that the destination 
Share same registers if there is no dependency between the between the iterations of DDG nodes.

As there is no dependency as represented by the Reuse graph the life time will not overlap and assign the same registers. Each arc will
Have the weight that describes the allocated registers and the Unrolling as proposed by Monica Lam given above The reuse graph will be
Partitioned based on the heuristics and the Sum of weights of each arc in each partitioned is calculated.  Then based on sum of weights of
Each partitioned reuse graphs the least common factor of all the weights will be the new Unrolling degree.

This new unrolling degree will lead to better register allocation and reduction of register pressure and  because the destination registers is
Shared between different iterations because of no dependency as described by the Data dependency distance given in DDG, the allocated 
registers will lead to less spill and Fetch.

The calculation of getting the Unrolling degree(new) as above will lead to register allocation  for loops ( that has the candidate of lots of 
Parallelism ) on assigning the Same destination registers between the DDG nodes having no dependency.

Some of the Logic for calculation of new unrolling degree is taken from the proposed Unrolling degree based on Periodic register allocation 
Albert Cohen

This will efficiently use before and after the register allocation based in gcc so that weights of each reuse graph that describes the allocated 
Registers Will be known after the register allocation and the weights that describes unrolling degree is done before register allocation and the
new Unrolling degree efficiently calculated that reduces the register pressure.


Thanks & Regards

More information about the Gcc mailing list