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

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]

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]

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.

include/llvm/Transforms/Utils/LoopUtils.h

 
 /// \brief Simplify each loop in a loop nest recursively.
 ///
 /// This takes a potentially un-simplified loop L (and its children) and turns
 /// it into a simplified loop nest with preheaders and single backedges. It
 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
 /// passed into it.
 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
-                  AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr);
+                  AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
+                  bool KeepSingleValuePHIs = false);
 
 /// \brief Put loop into LCSSA form.
 ///
 /// Looks at all instructions in the loop which have uses outside of the
 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 /// the loop are rewritten to use this node.
 ///
 /// LoopInfo and DominatorTree are required and preserved.

lib/Transforms/Utils/LoopSimplify.cpp

 /// \brief Simplify one loop and queue further loops for simplification.
 ///
 /// FIXME: Currently this accepts both lots of analyses that it uses and a raw
 /// Pass pointer. The Pass pointer is used by numerous utilities to update
 /// specific analyses. Rather than a pass it would be much cleaner and more
 /// explicit if they accepted the analysis directly and then updated it.
 static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
                             AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI,
-                            ScalarEvolution *SE, Pass *PP) {
+                            ScalarEvolution *SE, Pass *PP,
+                            bool KeepSingleValuePHIs = false) {
   bool Changed = false;
 ReprocessLoop:
 
   // Check to see that no blocks (other than the header) in this loop have
   // predecessors that are not in the loop.  This is not valid for natural
   // loops, but can occur if the blocks are unreachable.  Since they are
   // unreachable we can just shamelessly delete those CFG edges!
   for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
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, KeepSingleValuePHIs);
+      BI->getSuccessor(1)->removePredecessor(ExitingBlock, KeepSingleValuePHIs);
       ExitingBlock->eraseFromParent();
     }
   }
 
   return Changed;
 }
 
 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
-                        AliasAnalysis *AA, ScalarEvolution *SE) {
+                        AliasAnalysis *AA, ScalarEvolution *SE,
+                        bool KeepSingleValuePHIs) {
   bool Changed = false;
 
   // Worklist maintains our depth-first queue of loops in this nest to process.
   SmallVector<Loop *, 4> Worklist;
   Worklist.push_back(L);
 
   // Walk the worklist from front to back, pushing newly found sub loops onto
   // the back. This will let us process loops from back to front in depth-first
   // order. We can use this simple process because loops form a tree.
   for (unsigned Idx = 0; Idx != Worklist.size(); ++Idx) {
     Loop *L2 = Worklist[Idx];
     for (Loop::iterator I = L2->begin(), E = L2->end(); I != E; ++I)
       Worklist.push_back(*I);
   }
 
   while (!Worklist.empty())
-    Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, AA, DT, LI, SE, PP);
+    Changed |= simplifyOneLoop(Worklist.pop_back_val(), Worklist, AA, DT, LI,
+                               SE, PP, KeepSingleValuePHIs);
 
   return Changed;
 }
 
 namespace {
   struct LoopSimplify : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     LoopSimplify() : FunctionPass(ID) {

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*/ nullptr, SE);
-      formLCSSARecursively(*OuterL, *DT, SE);
+      simplifyLoop(OuterL, DT, LI, PP, /*AliasAnalysis*/ 0,
+                   PP->getAnalysisIfAvailable<ScalarEvolution>(),
+                   /* KeepSingleValuePHIs = */ true);
     }
   }
 
   return true;
 }