Proposal for path splitting for reduction in register pressure for Loops.
Hello All: The path splitting that replicates the code for better Data flow Analysis available. One of the properties of path splitting removes the joining nodes for the forked path like IF-THEN-ELSE and the Loops. The removal of joining nodes makes the path splitted into two independent paths. The increase in register Pressures for the loops are the performance bottleneck and sometimes lead to spill code in loops. The removal of joining nodes like loops and IF-THEN-ELSE makes the target independent optimization like CSE and Partial redundancy Elimination effective. Along with ease of these optimization the path splitting reduces the registers because Of the Liveness wont intersect because of independent splitted path. The ease of less intersection of liveness Reduces the register pressure for the Loops, thus better register allocation and less spilling code for Loops. The heuristics used in IRA code for register pressure will have better impact on the splitted path and thus optimized code. Thoughts Please? Thanks & Regards Ajit
Re: Proposal for path splitting for reduction in register pressure for Loops.
On March 8, 2015 3:39:08 PM CET, Ajit Kumar Agarwal wrote: >Hello All: > >The path splitting that replicates the code for better Data flow >Analysis available. One of the properties >of path splitting removes the joining nodes for the forked path like >IF-THEN-ELSE and the Loops. > >The removal of joining nodes makes the path splitted into two >independent paths. > >The increase in register Pressures for the loops are the performance >bottleneck and sometimes >lead to spill code in loops. > >The removal of joining nodes like loops and IF-THEN-ELSE makes the >target independent optimization like >CSE and Partial redundancy Elimination effective. Along with ease of >these optimization the path splitting >reduces the registers because Of the Liveness wont intersect because of >independent splitted path. The >ease of less intersection of liveness Reduces the register pressure for >the Loops, thus better register >allocation and less spilling code for Loops. > >The heuristics used in IRA code for register pressure will have better >impact on the splitted path and thus >optimized code. > >Thoughts Please? Are you talking about loop unswitching? Richard. >Thanks & Regards >Ajit > >
RE: Proposal for path splitting for reduction in register pressure for Loops.
-Original Message- From: Richard Biener [mailto:richard.guent...@gmail.com] Sent: Sunday, March 08, 2015 9:05 PM To: Ajit Kumar Agarwal; vmaka...@redhat.com; Jeff Law; gcc@gcc.gnu.org Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju Mekala Subject: Re: Proposal for path splitting for reduction in register pressure for Loops. On March 8, 2015 3:39:08 PM CET, Ajit Kumar Agarwal wrote: >Hello All: > >The path splitting that replicates the code for better Data flow >Analysis available. One of the properties of path splitting removes the >joining nodes for the forked path like IF-THEN-ELSE and the Loops. > >The removal of joining nodes makes the path splitted into two >independent paths. > >The increase in register Pressures for the loops are the performance >bottleneck and sometimes lead to spill code in loops. > >The removal of joining nodes like loops and IF-THEN-ELSE makes the >target independent optimization like CSE and Partial redundancy >Elimination effective. Along with ease of these optimization the path >splitting reduces the registers because Of the Liveness wont intersect >because of independent splitted path. The ease of less intersection of >liveness Reduces the register pressure for the Loops, thus better >register allocation and less spilling code for Loops. > >The heuristics used in IRA code for register pressure will have better >impact on the splitted path and thus optimized code. > >Thoughts Please? >>Are you talking about loop unswitching? Loop unswitching is a way of path splitting but I am proposing about the path splitting for the removal of joining node for the FOR Loops with IF-THEN-ELSE path. The tail of loop there is a joining node for the iF-THEN-ELSE forked at the header or the IF Region. The path splitting removes the joining node by splitting the path by replicating the code and joining nodes which leads to independent path(removing the joining node), thus the live ranges wont intersects and there is a reduction in the register pressure for the Loops. The Loop unswitching move the For Loops inside the IF-THEN and IF-ELSE path but the path splitting I am proposing would still have the IF-THEN-ELSE region Inside the loop instead of Loop unswitching but replicate the code for the joining nodes and splitting the path into two independent paths. Though there is Performance bottleneck with the replication of the code and spliiting the joining nodes and thus there wont be any joining node. This will makes the Live Ranges not intersecting thus reducing the register pressure and better register allocations. This makes it to check for the profitability for the reduction in register pressure with the replication of joining nodes thus removing the joining node. I am sure this makes the reduction in register pressure through the loops and IF-THEN-ELSE regions inside the Loops and thus better register allocation. Some profitability heuristics need to be added with this optimization. Thanks & Regards Ajit Richard. >Thanks & Regards >Ajit > >
Re: Proposal for path splitting for reduction in register pressure for Loops.
On 03/08/15 09:35, Richard Biener wrote: On March 8, 2015 3:39:08 PM CET, Ajit Kumar Agarwal wrote: Hello All: The path splitting that replicates the code for better Data flow Analysis available. One of the properties of path splitting removes the joining nodes for the forked path like IF-THEN-ELSE and the Loops. The removal of joining nodes makes the path splitted into two independent paths. The increase in register Pressures for the loops are the performance bottleneck and sometimes lead to spill code in loops. The removal of joining nodes like loops and IF-THEN-ELSE makes the target independent optimization like CSE and Partial redundancy Elimination effective. Along with ease of these optimization the path splitting reduces the registers because Of the Liveness wont intersect because of independent splitted path. The ease of less intersection of liveness Reduces the register pressure for the Loops, thus better register allocation and less spilling code for Loops. The heuristics used in IRA code for register pressure will have better impact on the splitted path and thus optimized code. Thoughts Please? Are you talking about loop unswitching? It's more like superblock formation. You duplicate from the join point into the predecessors. The actual transformation is very similar to what we do for join blocks in jump threading paths, though we do it in two steps (first we duplicate the entire join point, then let later passes merge that into the predecessor if it's profitable to do so) I'm not sure how much a more generalized path splitter buys us -- PRE picks up a lot of the redundancies that were traditionally exposed by superblock formation. And jump threading picks up the branching redundancies that tend to get exposed. I've pondered from time to time using jump threader to guide this kind of transformation -- it actually has enough knowledge to say "hey, instructions I1, I3, I5 in this this block are actually redundant when the block is reached via path P". But I've never bothered to implement. It also doesn't fit well into the long term plans to change the threader from a forward walk to a backward walk. LLVM has integrated a very limited form of this transformation into their jump threader, specifically for memory loads. Jeff
RE: Proposal for path splitting for reduction in register pressure for Loops.
On March 8, 2015 4:58:49 PM CET, Ajit Kumar Agarwal wrote: > > >-Original Message- >From: Richard Biener [mailto:richard.guent...@gmail.com] >Sent: Sunday, March 08, 2015 9:05 PM >To: Ajit Kumar Agarwal; vmaka...@redhat.com; Jeff Law; gcc@gcc.gnu.org >Cc: Vinod Kathail; Shail Aditya Gupta; Vidhumouli Hunsigida; Nagaraju >Mekala >Subject: Re: Proposal for path splitting for reduction in register >pressure for Loops. > >On March 8, 2015 3:39:08 PM CET, Ajit Kumar Agarwal > wrote: >>Hello All: >> >>The path splitting that replicates the code for better Data flow >>Analysis available. One of the properties of path splitting removes >the >>joining nodes for the forked path like IF-THEN-ELSE and the Loops. >> >>The removal of joining nodes makes the path splitted into two >>independent paths. >> >>The increase in register Pressures for the loops are the performance >>bottleneck and sometimes lead to spill code in loops. >> >>The removal of joining nodes like loops and IF-THEN-ELSE makes the >>target independent optimization like CSE and Partial redundancy >>Elimination effective. Along with ease of these optimization the path >>splitting reduces the registers because Of the Liveness wont intersect > >>because of independent splitted path. The ease of less intersection of > >>liveness Reduces the register pressure for the Loops, thus better >>register allocation and less spilling code for Loops. >> >>The heuristics used in IRA code for register pressure will have better > >>impact on the splitted path and thus optimized code. >> >>Thoughts Please? > >>>Are you talking about loop unswitching? > >Loop unswitching is a way of path splitting but I am proposing about >the path splitting for the removal of joining node for the FOR Loops >with IF-THEN-ELSE path. >The tail of loop there is a joining node for the iF-THEN-ELSE forked at >the header or the IF Region. The path splitting removes the joining >node by splitting the >path by replicating the code and joining nodes which leads to >independent path(removing the joining node), thus the live ranges wont >intersects and there is a >reduction in the register pressure for the Loops. > >The Loop unswitching move the For Loops inside the IF-THEN and IF-ELSE >path but the path splitting I am proposing would still have the >IF-THEN-ELSE region >Inside the loop instead of Loop unswitching but replicate the code for >the joining nodes and splitting the path into two independent paths. >Though there is >Performance bottleneck with the replication of the code and spliiting >the joining nodes and thus there wont be any joining node. This will >makes the Live >Ranges not intersecting thus reducing the register pressure and better >register allocations. > >This makes it to check for the profitability for the reduction in >register pressure with the replication of joining nodes thus removing >the joining node. >I am sure this makes the reduction in register pressure through the >loops and IF-THEN-ELSE regions inside the Loops and thus better >register allocation. > >Some profitability heuristics need to be added with this optimization. I see. This basically creates two loop latches and thus will make our loop detection code turn the loop into a fake loop nest. Not sure if that is a good idea. Richard. >Thanks & Regards >Ajit > >Richard. > >>Thanks & Regards >>Ajit >> >>
Re: Proposal for path splitting for reduction in register pressure for Loops.
On 03/08/15 12:13, Richard Biener wrote: I see. This basically creates two loop latches and thus will make our loop detection code turn the loop into a fake loop nest. Not sure if that is a good idea. I'd have to sit down and ponder this for a while -- what would be the register pressure implications of duplicating the contents of the join block into its predecessors, leaving an empty joiner so that we still have a single latch? Jeff
gcc-5-20150308 is now available
Snapshot gcc-5-20150308 is now available on ftp://gcc.gnu.org/pub/gcc/snapshots/5-20150308/ and on various mirrors, see http://gcc.gnu.org/mirrors.html for details. This snapshot has been generated from the GCC 5 SVN branch with the following options: svn://gcc.gnu.org/svn/gcc/trunk revision 221264 You'll find: gcc-5-20150308.tar.bz2 Complete GCC MD5=19b19115e924c3e38b81d3497b12cb8e SHA1=07b526792a99d91a59eb528250a61724e3f7af62 Diffs from 5-20150301 are available in the diffs/ subdirectory. When a particular snapshot is ready for public consumption the LATEST-5 link is updated and a message is sent to the gcc list. Please do not use a snapshot before it has been announced that way.
