[LCSSA] Don't let SSAUpdater to break LCSSA during LCSSA construction.

[mzolotukhin]

Summary

This change essentially does the following:

1. Factors out formLCSSAForOneInstruction, so that we can use the same instance of SSAUpdate for all rewritings corresponding to the same instruction.
2. Starts to use a stricter check than just SSAUpdate.HasValueForBlock: we need to process the value even if SSAUpdater thinks it's available unless it's a PHI-node defined in this block.

(1) allows us to avoid generating duplicate phi-nodes in the same BB for
the same instruction - we did this because we cleared SSAUpdater on
every iteration in our Worklist loop. Now we only clear it once, before
processing an instruction.
(2) makes sure that we still generate LCSSA phi-nodes even in cases
where SSAUpdater thinks we have an available value.

[mzolotukhin]

Ping.

[chandlerc]

Thanks for the ping!

lib/Transforms/Utils/LCSSA.cpp

83–84

The only hesitation I really have here is that this makes us do a lot more memory allocations when we're rewriting a lot of instructions with a lot of uses.

Is it worthwhile to try and share the worklists in some way? Have you looked at whether this worklist is just always small and so it doesn't matter in practice?

[mzolotukhin]

lib/Transforms/Utils/LCSSA.cpp

83–84

Frankly, I haven't thought about that -- thanks for pointing this out!
We can have a single worklist object, which we'll pass to this function, and that should get rid of allocations you are concerned about. We cannot use the same worklist as in formLCSSAForInstructions though - we clear SSAUpdater when we leave formLCSSAForOneInstruction, and we leave it when the worklist is empty. If we want to reuse worklist from the upper function, we need to somehow introduce boundaries at which we need to clear SSAUpdater, and I don't see a good way to do it.

If that makes sense to you, I'll update the patch so that we don't create a new worklist for every invocation of formLCSSAForOneInstruction.

[chandlerc]

lib/Transforms/Utils/LCSSA.cpp

83–84

Yeah, that makes sense.

Do we ever really want formLCSSForOneInstruction? I wonder if we should just leave the single function and scope the SSAUpdater more tightly. Happy to leave the code structuring question up to you though.

[sanjoy]

lib/Transforms/Utils/LCSSA.cpp

81

Note: this cache become less effective since we're not reusing it for the entire worklist anymore.

226

Why is it legal to re-use the same SSAUpdater to rewrite uses for these newly inserted PHIs? Asking mostly because earlier SSAUpdate would get reset for each iteration of the inner loop on the worklist.

251

(Fix separately without review if you agree) Why not just a range for over an ArrayRef<Instruction *>?

lib/Transforms/Utils/LCSSA.cpp

VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA),
                     cl::desc("Verify loop lcssa form (time consuming)"));
 
 /// Return true if the specified block is in the list.
 static bool isExitBlock(BasicBlock *BB,
                         const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
   return is_contained(ExitBlocks, BB);
 }
 
-/// For every instruction from the worklist, check to see if it has any uses
-/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
-/// rewrite the uses.
-bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
-                                    DominatorTree &DT, LoopInfo &LI) {
+/// For instruction I, check to see if it has any uses that are outside the
+/// current loop.  If so, insert LCSSA PHI nodes and rewrite the uses.
+static bool formLCSSAForOneInstruction(Instruction *I, DominatorTree &DT,
+                                       LoopInfo &LI) {
   SmallVector<Use *, 16> UsesToRewrite;
   SmallSetVector<PHINode *, 16> PHIsToRemove;
   PredIteratorCache PredCache;
   bool Changed = false;
 
   // Cache the Loop ExitBlocks across this loop.  We expect to get a lot of
   // instructions within the same loops, computing the exit blocks is
   // expensive, and we're not mutating the loop structure.
   SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>> LoopExitBlocks;
 
+  SmallVector<Instruction *, 4> Worklist;
+  Worklist.push_back(I);
+
+  SmallVector<PHINode *, 4> InsertedPHIs;
+  SSAUpdater SSAUpdate(&InsertedPHIs);
+  SSAUpdate.Initialize(I->getType(), I->getName());
+
   while (!Worklist.empty()) {
     UsesToRewrite.clear();
 
     Instruction *I = Worklist.pop_back_val();
     BasicBlock *InstBB = I->getParent();
     Loop *L = LI.getLoopFor(InstBB);
     if (!LoopExitBlocks.count(L))   
       L->getExitBlocks(LoopExitBlocks[L]);
while (!Worklist.empty()) {
     if (InvokeInst *Inv = dyn_cast<InvokeInst>(I))
       DomBB = Inv->getNormalDest();
 
     DomTreeNode *DomNode = DT.getNode(DomBB);
 
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
-    SmallVector<PHINode *, 4> InsertedPHIs;
-    SSAUpdater SSAUpdate(&InsertedPHIs);
-    SSAUpdate.Initialize(I->getType(), I->getName());
-
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
-      if (SSAUpdate.HasValueForBlock(ExitBB))
+      if (SSAUpdate.HasValueForBlock(ExitBB)) {
+        Value *AV = SSAUpdate.GetValueAtEndOfBlock(ExitBB);
+        if (isa<PHINode>(AV) && cast<Instruction>(AV)->getParent() == ExitBB)
           continue;
+      }
 
       PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
                                     I->getName() + ".lcssa", &ExitBB->front());
 
       // Add inputs from inside the loop for this PHI.
       for (BasicBlock *Pred : PredCache.get(ExitBB)) {
         PN->addIncoming(I, Pred);
 
while (!Worklist.empty()) {
 
     // Post process PHI instructions that were inserted into another disjoint
     // loop and update their exits properly.
     for (auto *PostProcessPN : PostProcessPHIs) {
       if (PostProcessPN->use_empty())
         continue;
 
       // Reprocess each PHI instruction.
       Worklist.push_back(PostProcessPN);
     }
 
     // Keep track of PHI nodes that we want to remove because they did not have
     // any uses rewritten.
     for (PHINode *PN : AddedPHIs)
       if (PN->use_empty())
         PHIsToRemove.insert(PN);
 
     Changed = true;
   }
   // Remove PHI nodes that did not have any uses rewritten.
   for (PHINode *PN : PHIsToRemove) {
     assert (PN->use_empty() && "Trying to remove a phi with uses.");
     PN->eraseFromParent();
   }
   return Changed;
 }
 
+/// For every instruction from the worklist, check to see if it has any uses
+/// that are outside the current loop.  If so, insert LCSSA PHI nodes and
+/// rewrite the uses.
+bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
+                                    DominatorTree &DT, LoopInfo &LI) {
+  bool Changed = false;
+  while (!Worklist.empty()) {
+    Instruction *I = Worklist.pop_back_val();
+    Changed |= formLCSSAForOneInstruction(I, DT, LI);
+  }
+  return Changed;
+}
+
 /// Return true if the specified block dominates at least
 /// one of the blocks in the specified list.
 static bool
 blockDominatesAnExit(BasicBlock *BB,
                      DominatorTree &DT,
                      const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
   DomTreeNode *DomNode = DT.getNode(BB);
   return any_of(ExitBlocks, [&](BasicBlock *EB) {

test/Transforms/LCSSA/pr28424.ll

 loop_with_insert_point:
   br i1 undef, label %loop_with_insert_point, label %exit
 
 ; CHECK: exit:
 ; CHECK:   %x2.lcssa = phi i32 [ %x2, %loop_with_insert_point ]
 exit:
   ret i32 %x
 }
+
+; This test failed at some point when invoked with '-lcssa -licm'. The problem
+; was that SSAUpdater didn't try to preserve LCSSA and happened to insert a
+; phi-node, which broke LCSSA (it inserted one more phi-node to if.end block).
+; Here we check that we inserted no more than one phi-node where needed.
+; CHECK-LABEL: @foo3
+define void @foo3() {
+entry:
+  br label %loop.A
+entry2:
+  br label %inner.loop.B
+entry3:
+  br label %inner.loop.C
+
+loop.A:
+  %c.0 = phi i32 [ 0, %entry ], [ 0, %loop.A ]
+  br i1 false, label %loop.A.end, label %loop.A
+; CHECK: loop.A.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+loop.A.end:
+  br label %outer.loop
+
+; CHECK: outer.loop:
+; CHECK:     phi
+; CHECK-NOT: phi
+outer.loop:
+  br label %inner.loop.B
+
+; CHECK: inner.loop.B:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.B:
+  br i1 false, label %inner.loop.B.latch, label %outer.loop.latch
+inner.loop.B.latch:
+  br i1 false, label %if.then, label %inner.loop.B
+
+; CHECK: if.then:
+; CHECK:     phi
+; CHECK-NOT: phi
+if.then:
+  br i1 false, label %inner.loop.C, label %if.end
+
+; CHECK: inner.loop.C:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.C:
+  %tobool9 = icmp ne i32 %c.0, 0
+  br i1 false, label %inner.loop.C, label %inner.loop.C.end
+
+; CHECK: inner.loop.C.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+inner.loop.C.end:
+  br label %if.end
+
+; CHECK: if.end:
+; CHECK:     phi
+; CHECK-NOT: phi
+if.end:
+  br label %outer.loop.latch
+
+; CHECK: outer.loop.latch:
+; CHECK:     phi
+; CHECK-NOT: phi
+outer.loop.latch:
+  br label %outer.loop
+}