Page MenuHomePhabricator

Teaching loop simplify to preserve LCSSA
Needs RevisionPublic

Authored by dinesh.d on Mar 6 2014, 7:53 AM.

Details

Summary

As Chandler has mentioned at http://llvm.org/bugs/show_bug.cgi?id=18616#c4, it is loop simplify which destroy LCSSA. I tried to find out what destroys LCSSA and found that it is 'removePredecessor()' calls at the end of 'simplifyOneLoop()'.

removePredecessor() deletes all PHIs with one incoming value, which in some cases destroy LCSSA. Calling removePredecessor() call with 'DontDeleteUselessPHIs = true' preserves LSCCA, atleast in case of the test-cases attached with PR18616.

With this fix, we can remove bulky formLCSSARecursively() call from LoopUnroll.

Diff Detail

Event Timeline

gentle ping

To my understanding, this change will not leave many unnecessory phi nodes around. Loop was in LCSSA form and to keep it in that way, we can not discard phi node even if there is only one incomming node and as commented in many places in code, keeping extra phi nodes will not trouble us in further analysis and transform. Ultimately they will be removed for the IR.

I have tested this with few test cases and resulting IR at the end of pass is same as with the old code where we were using formLCSSARecursively() call.

Gentle Ping..

gentle ping

If required, the patch can be modified to keep deleted phi nodes only for selected cases by adding one parameter 'bool DontDeleteUselessPHIs'.

chandlerc added inline comments.May 5 2014, 3:56 PM
lib/Transforms/Utils/LoopSimplify.cpp
703–705

This seems like a ... very heavy hammer. And yet, it is used pervasively. I think this code should be written differently, but your patch doesn't make it any worse.

If you do this, you should make the actual LoopSimplify pass preserve LCSSA.

It would also be good to write some direct test cases for LoopSimplify preserving LCSSA.

lib/Transforms/Utils/LoopUnroll.cpp
487–490

Hmm, I'm a touch hesitant to just remove this. When I first changed the loop pass stuff it was... surprisingly noisy due to how much broke.

If we're going to switch back, I'd like to do it in a separate commit so its easier to revert if things break. Have you tested this change on any large code bases out of curiosity?

dinesh.d added inline comments.May 6 2014, 5:25 AM
lib/Transforms/Utils/LoopSimplify.cpp
703–705

It has nothing to do with making LoopSimply pass preserve LCSSA. Sorry for
confusing title. I have missed this fact that it is a pass. I think
LoopSimplify need not preserve LCSSA.

What I am trying to solve with this patch is how SimplifyLoop affect LCSSA
when called from UnrollLoop(). I was working on PR18861, crash due to LCSSA
invalidation in LoopUnroll pass and during analysis, I observed that it is
happening when we merge/ delete some block which results in PHIs with only
one in-coming path which gets removed by merge/ delete routine. I saw similar
change by you and tried to fix [http://reviews.llvm.org/D2976] it by reforming
LCSSA in such cases.

This patch is on same line, given IR in LCSSA form, and we maintaining it through pass,
it was getting invalidated due to SimplifyLoop call at the end of pass and reason was
same, deleting PHI nodes with one in-coming path.

Now, I think we should update SimplifyLoop() to take an argument like 'DontDeleteUselessPHIs'
and selectively keep PHI nodes to preserve LCSSA when needed.

lib/Transforms/Utils/LoopUnroll.cpp
487–490

I am ok with anything you decide to do with this. If we go with removing these,
I can create/ test/ submit patch for the same.

I tried building gcc with and without this patch. Both build was successful. I will try
building some more large code. It will be great if you can suggest any code base, good
to verify loop optimization.

dinesh.d updated this revision to Diff 9169.May 7 2014, 7:08 AM
dinesh.d edited edge metadata.

Added parameter to SimplifyLoop to selectively KeepSingleValuePHIs. I am looking in to making LoopSimplify pass preserve LCSSA

atrick edited edge metadata.May 9 2014, 3:58 PM

I'm confused, are you trying to get rid of formLCSSARecursively because it is too expensive? It should do the job right?

Yes,

While working on PR18861 [http://reviews.llvm.org/D2976], I saw Chandler's comment in LICM.cpp about formLCSSARecursively() being heavy.

I observed that formLCSSARecursively() is added in LoopUnroll to fix LCSSA breakage during loop simplify which is happening due to deletion of PHI nodes with single incoming value. As per my understanding, keeping few PHI nodes and removing them later is much cheaper than formLCSSARecursively() and that's why this patch.

atrick requested changes to this revision.May 9 2014, 4:15 PM
atrick edited edge metadata.

Ok. But sometimes we need to create new phis after full unrolling. We can have a sequence of blocks initially in the same inner loop. After unrolling, they all end up in different loops and now we need a phi between them. I think we should make this correct first. Yes, LCSSA update is expensive and that is the drawback of doing it.

This revision now requires changes to proceed.May 9 2014, 4:15 PM

I will updated this patch once http://reviews.llvm.org/D2976 is done and committed.