[PR18861] Fix for LoopUnroll pass was breaking LCSSA form while completely removing loop

[dinesh.d]

Summary

I have already sent mail to llvm-commits [http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140303/207346.html].

If LoopUnroll pass decides to completely unroll a loop, before deleting it [deleteLoopFromQueue()] from the loop list, it updates parent loop for all blocks in the loop to be unrolled [updateUnloop()->updateBlockParents()]. Candidate for parent loop is based on finding nearest parent loop among the block successors [getNearestLoop()], and returns null if a block does not have any successor [e.g. exit blocks having return statement, not sure if this may happen in other cases]. This causes the block to come out of loop nest. Now if this block is using some variable assigned inside loop nest, then it breaks LCSSA form.

This is what I have come up to fix LCSSA while detaching exit block from loop nest.

I have assumed few things.

1. As block was part of loop getting unrolled, it will have predecessor which is part of loop nest.
2. If any value used as instruction operand in the block whose parent is out side the loop getting unrolled, we have to add PHI node from all predecessor of the block for it to maintain LCSSA.

I will appreciate any comment or pointer to right direction.

[dinesh.d]

gentle ping.

this patch fixes crash reported in PR18861.

[dinesh.d]

fixed issue while iterating users of instruction in the patch

[dinesh.d]

Gentle ping

[atrick]

Thanks for fixing this bug! And sorry for the review delay.

I'm concerned that this implementation only handles some cases. I know
this code is super confusing, and your fix is better than nothing. But
we should try to generalize a bit because the existing LCSSA update is
full of missing corner cases. Your fix is just working around one specific
case with a new analysis.

In general, the problem is that full unrolling may cause some basic blocks to bubble up in the loop tree. Now some of the original loop's blocks may be shallower in the loop nest than others. The -view-cfg of each of the unloop.ll functions will hopefully show you some interesting cases. You have to have at least four levels of loops to see the interesting cases. Note that the problem you are solving is not limited to the case when a block "exits the function".

Also when replacing uses:

+ if (OiPN != Ui && Ui->getParent() == BB)
+ Ui->replaceUsesOfWith(Oi, OiPN);

We need to replace all uses that are not contained in the defining instruction's parent loop.

The only clean, robust way of handling this is to rerun LCSSA
formation as a utility on any block on a path to a new loop exit after
unrolling. Trying to reimplement LCSSA formation and take shortcuts is
not a good idea, because the problem of updating after unrolling seems
subject to the same corner cases as the general problem. Also,
"updateUnloop" is only supposed to update LoopInfo so we don't want to
mess with that unless necessary.

Currently, LoopUnroll does attempt to rerun LCSSA on the parent loop. So the real question is, why does this fail to catch some cases? The problem is that it only handles loop exits that end up in the parent loop. Now, we don't want to rerun LCSSA on the whole function, so what do we do? The answer is to find the shallowest loop one level deeper than the shallowest exit and rerun formLCSSARecursively on that loop.

i.e.

• Outer->L1->L2->L3
• Fully unroll L3.
• If we see an exit to L1, formLCSSA for L2
• If we see an exit to Outer, formLCSSA for L1

Loop unrolling can probably notice these exits when setting up
branches. Then walk up the loop tree from the current loop to find the
child of the exit.

[dinesh.d]

Thanks, I agree that I don't understand complete flow and internals.

But While debugging for this bug, I observed that there are only 2 places we are messing
up with PHI nodes during LoopUnrool pass, one in FoldBlockIntoPredecessor() while folding
single entry PHI nodes and other during loop simplify.

For issue due to loop simplify, Chandler has added formLCSSARecursively() for parent loop
if current loop is unrolled completely. I saw that if we run formLCSSARecursively() on the
root node of the loop nest, it fixes this bug too. But as this was temporary fix as per chandler,
I started looking to completely avoid formLCSSARecursively.

This patch tries to fix PHIs deleted by FoldBlockIntoPredecessor. I had send another patch
to keep PHIs nodes from deletion while simplifying loop.

I assumed that if loop was in LCSSA and we keep/ re-insert deleted PHI nodes which was
there only to keep loop in LCSSA form, that will ensure that loop will be in LCSSA after pass
and will take care of all corner cases. But I may be wrong.

I will try to update patch as per your suggestions.

Again thanks for review and suggestions :).

[dinesh.d]

Sorry for delay in response.

Andrew has suggested some investigations in loop unroll pass. I am going through them and will update this patch soon.

[dinesh.d]

To start with, I looked through all latches in the the loop, and check if they are
moved higher in loop nest, if so, I am trying to run formLCSSARecursively on highest
loop where any latch is landed.

This resolves PR18861, as the issue was caused by FoldBlockIntoPredecessor() call
in following code.

for (unsigned i = 0, e = Latches.size(); i != e; ++i) {
  BranchInst *Term = cast<BranchInst>(Latches[i]->getTerminator());
  if (Term->isUnconditional()) {
    BasicBlock *Dest = Term->getSuccessor(0);
    if (BasicBlock *Fold = FoldBlockIntoPredecessor(Dest, LI, LPM))
      std::replace(Latches.begin(), Latches.end(), Dest, Fold);
  }
}

FoldBlockIntoPredecessor() call merges BB and removes all single PHIs. In such cases,
new block will end up in 'Latches' list and all those invalidations are handled by the patch.

I am experimenting further to see if we have to check any other BB apart from latches.

[atrick]

Hi Dinesh,

This looks like it will work. It is different than the fix I was proposing and very tricky. I actually thought your fix was incorrect before realizing you're checking the Latch's ParentLoop after calling deleteLoopFromQueue. This ensures that the final loop latch will already be promoted to the outermost loop that any loop exit branches to. Note that we only care about the last loop latch (std::prev(Latches.end())), so I don't think you need to check all latches. If you add comments something like this then it's good to commit:

LCSSA must be performed on the outermost affected loop. The unrolled
loop's last loop latch is guaranteed to be in the outermost loop after
deleteLoopFromQueue updates LoopInfo.

Then you could either add this comment:

This may conservatively run LCSSA on the parent loop one level higher in the loop tree than necessary.

Or you could optimize the code further by keeping track of the loop one level below OuterL and calling formLCSSA on that intstead.

[dinesh.d]

I have updated patch as per your suggestions. I will commit this patch and continue
experimenting with different loop structure. I already have tried many different combinations
but none of them cause similar crash.

Thanks for review and support.

[dinesh.d]

Closed by commit rL209796 (authored by dinesh).

lib/Analysis/LoopInfo.cpp

 #include "llvm/Analysis/LoopInfoImpl.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Metadata.h"
+#include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include <algorithm>
 using namespace llvm;
 
 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
 template class llvm::LoopBase<BasicBlock, Loop>;
 template class llvm::LoopInfoBase<BasicBlock, Loop>;
class UnloopUpdater {
   // Flag the presence of an irreducible backedge whose destination is a block
   // directly contained by the original unloop.
   bool FoundIB;
 
 public:
   UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
     Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {}
 
+  void fixLCSSAForDetachedBlock(BasicBlock *BB);
+
   void updateBlockParents();
 
   void removeBlocksFromAncestors();
 
   void updateSubloopParents();
 
 protected:
   Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
 };
 } // end anonymous namespace
 
+/// fixLCSSAForDetachedBlocks - Fix LCSSA if basic block was removed from the
+/// loop getting unrolled and now not inside any loop.
+void UnloopUpdater::fixLCSSAForDetachedBlock(BasicBlock *BB) {
+  assert(!LI->getLoopFor(BB) && "block part of other loop");
+  for (BasicBlock::iterator I = BB->begin(), ie = BB->end(); I != ie; ++I) {
+    Instruction *Inst = dyn_cast<Instruction>(&*I);
+    for (User::op_iterator Op = Inst->op_begin(), Oe = Inst->op_end(); Op != Oe;
+         ++Op)
+      if (Instruction *Oi = dyn_cast<Instruction>(*Op))
+        if (!Unloop->contains(LI->getLoopFor(Oi->getParent()))) {
+          PredIteratorCache PIC;
+          if (PIC.GetNumPreds(BB)) {
+            PHINode *OiPN =
+                PHINode::Create(Oi->getType(), PIC.GetNumPreds(BB),
+                                Oi->getName() + ".lcssa", BB->getFirstNonPHI());
+            for (BasicBlock **PI = PIC.GetPreds(BB); *PI; ++PI)
+              OiPN->addIncoming(Oi, *PI);
+
+            for (Value::user_iterator U = Oi->user_begin(), Ue = Oi->user_end();
+                 U != Ue; ++U)
+              if (Instruction *Ui = dyn_cast<Instruction>(*U))
+                if (OiPN != Ui && Ui->getParent() == BB)
+                  Ui->replaceUsesOfWith(Oi, OiPN);
+          }
+        }
+  }
+}
+
 /// updateBlockParents - Update the parent loop for all blocks that are directly
 /// contained within the original "unloop".
 void UnloopUpdater::updateBlockParents() {
   if (Unloop->getNumBlocks()) {
     // Perform a post order CFG traversal of all blocks within this loop,
     // propagating the nearest loop from sucessors to predecessors.
     LoopBlocksTraversal Traversal(DFS, LI);
     for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
            POE = Traversal.end(); POI != POE; ++POI) {
 
       Loop *L = LI->getLoopFor(*POI);
       Loop *NL = getNearestLoop(*POI, L);
 
       if (NL != L) {
         // For reducible loops, NL is now an ancestor of Unloop.
         assert((NL != Unloop && (!NL || NL->contains(Unloop))) &&
                "uninitialized successor");
         LI->changeLoopFor(*POI, NL);
+
+        if (!NL)
+          fixLCSSAForDetachedBlock(*POI);
       }
       else {
         // Or the current block is part of a subloop, in which case its parent
         // is unchanged.
         assert((FoundIB || Unloop->contains(L)) && "uninitialized successor");
       }
     }
   }
for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
            POE = DFS.endPostorder(); POI != POE; ++POI) {
 
       Loop *L = LI->getLoopFor(*POI);
       Loop *NL = getNearestLoop(*POI, L);
       if (NL != L) {
         assert(NL != Unloop && (!NL || NL->contains(Unloop)) &&
                "uninitialized successor");
         LI->changeLoopFor(*POI, NL);
+
+        if (!NL)
+          fixLCSSAForDetachedBlock(*POI);
+
         Changed = true;
       }
     }
   }
 }
 
 /// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below
 /// their new parents.

test/Transforms/LoopUnroll/pr18861.ll

+; RUN: opt < %s -loop-unroll -indvars -disable-output
+
+@b = external global i32, align 4
+
+; Function Attrs: nounwind uwtable
+define void @fn1() #0 {
+entry:
+  br label %for.cond1thread-pre-split
+
+for.cond1thread-pre-split:                        ; preds = %for.inc8, %entry
+  %storemerge1 = phi i32 [ 0, %entry ], [ %inc9, %for.inc8 ]
+  br i1 undef, label %for.inc8, label %for.cond2.preheader.lr.ph
+
+for.cond2.preheader.lr.ph:                        ; preds = %for.cond1thread-pre-split
+  br label %for.cond2.preheader
+
+for.cond2.preheader:                              ; preds = %for.inc5, %for.cond2.preheader.lr.ph
+  br label %for.cond2
+
+for.cond2:                                        ; preds = %for.body3, %for.cond2.preheader
+  %storemerge = phi i32 [ %add, %for.body3 ], [ 0, %for.cond2.preheader ]
+  %cmp = icmp slt i32 %storemerge, 1
+  br i1 %cmp, label %for.body3, label %for.inc5
+
+for.body3:                                        ; preds = %for.cond2
+  %tobool4 = icmp eq i32 %storemerge, 0
+  %add = add nsw i32 %storemerge, 1
+  br i1 %tobool4, label %for.cond2, label %if.then
+
+if.then:                                          ; preds = %for.body3
+  store i32 %storemerge1, i32* @b, align 4
+  ret void
+
+for.inc5:                                         ; preds = %for.cond2
+  br i1 undef, label %for.cond1.for.inc8_crit_edge, label %for.cond2.preheader
+
+for.cond1.for.inc8_crit_edge:                     ; preds = %for.inc5
+  br label %for.inc8
+
+for.inc8:                                         ; preds = %for.cond1.for.inc8_crit_edge, %for.cond1thread-pre-split
+  %inc9 = add nsw i32 %storemerge1, 1
+  br label %for.cond1thread-pre-split
+}