Teaching loop simplify to preserve LCSSA

[dinesh.d]

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.

[dinesh.d]

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.

[dinesh.d]

Gentle Ping..

[dinesh.d]

Gentle Ping..

[dinesh.d]

gentle ping

[dinesh.d]

gentle ping

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

[dinesh.d]

gentle ping

[chandlerc]

lib/Transforms/Utils/LoopSimplify.cpp

700–701

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

472–473

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]

lib/Transforms/Utils/LoopSimplify.cpp

700–701

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

472–473

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]

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

[atrick]

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

[dinesh.d]

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]

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.

[dinesh.d]

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

lib/Transforms/Utils/LoopSimplify.cpp

for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
       const std::vector<DomTreeNodeBase<BasicBlock> *> &Children =
         Node->getChildren();
       while (!Children.empty()) {
         DomTreeNode *Child = Children.front();
         DT->changeImmediateDominator(Child, Node->getIDom());
       }
       DT->eraseNode(ExitingBlock);
 
-      BI->getSuccessor(0)->removePredecessor(ExitingBlock);
-      BI->getSuccessor(1)->removePredecessor(ExitingBlock);
+      BI->getSuccessor(0)->removePredecessor(ExitingBlock, true);
+      BI->getSuccessor(1)->removePredecessor(ExitingBlock, true);
       ExitingBlock->eraseFromParent();
     }
   }
 
   return Changed;
 }
 
 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,

lib/Transforms/Utils/LoopUnroll.cpp

bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount,
   // If we have a pass and a DominatorTree we should re-simplify impacted loops
   // to ensure subsequent analyses can rely on this form. We want to simplify
   // at least one layer outside of the loop that was unrolled so that any
   // changes to the parent loop exposed by the unrolling are considered.
   if (PP && DT) {
     if (!OuterL && !CompletelyUnroll)
       OuterL = L;
     if (OuterL) {
-      ScalarEvolution *SE = PP->getAnalysisIfAvailable<ScalarEvolution>();
-      simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ 0, SE);
-      formLCSSARecursively(*OuterL, *DT, SE);
+      simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ 0,
+                   PP->getAnalysisIfAvailable<ScalarEvolution>());
     }
   }
 
   return true;
 }