[LCSSA] Post-process PHI-nodes created by SSAUpdate when constructing LCSSA form.

[mzolotukhin]

Summary

SSAUpdate might insert PHI-nodes inside loops, which can break LCSSA
form unless we fix it up.

This fixes PR28424.

[uabelho]

The patch at least solves my original problem and I haven't seen anything breaking with it during the limited testing i've done so far.

[mzolotukhin]

Ping.

[chandlerc]

LGTM, this makes perfect sense.

test/Transforms/LCSSA/pr28424.ll

4 ↗

(On Diff #62761)

Maybe actually explain the particular patterns you're testing here?

[mzolotukhin]

Thanks for taking a look, Chandler!

Michael

llvm/trunk/lib/Transforms/Utils/LCSSA.cpp

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;
 
-    SSAUpdater SSAUpdate;
+    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;
 
for (Use *UseToRewrite : UsesToRewrite) {
         if (UseToRewrite->get()->hasValueHandle())
           ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
         UseToRewrite->set(&UserBB->front());
         continue;
       }
 
       // Otherwise, do full PHI insertion.
       SSAUpdate.RewriteUse(*UseToRewrite);
+
+      // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
+      // to post-process them to keep LCSSA form.
+      for (PHINode *InsertedPN : InsertedPHIs) {
+        if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
+          if (!L->contains(OtherLoop))
+            PostProcessPHIs.push_back(InsertedPN);
+      }
     }
 
     // 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;
 

llvm/trunk/test/Transforms/LCSSA/pr28424.ll

+; RUN: opt < %s -lcssa -S -o - | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+; PR28424
+; Here LCSSA adds phi-nodes for %x into the loop exits. Then, SSAUpdater needs
+; to insert phi-nodes to merge these values. That creates a new def, which in
+; its turn needs another LCCSA phi-node, and this test ensures that we insert
+; it.
+
+; CHECK-LABEL: @foo1
+define internal i32 @foo1() {
+entry:
+  br label %header
+
+header:
+  %x = add i32 0, 1
+  br i1 undef, label %if, label %loopexit1
+
+if:
+  br i1 undef, label %latch, label %loopexit2
+
+latch:
+  br i1 undef, label %header, label %loopexit3
+
+; CHECK: loopexit1:
+; CHECK:   %x.lcssa = phi i32 [ %x, %header ]
+loopexit1:
+  br label %loop_with_insert_point
+
+; CHECK: loopexit2:
+; CHECK:   %x.lcssa1 = phi i32 [ %x, %if ]
+loopexit2:
+  br label %exit
+
+; CHECK: loopexit3:
+; CHECK:   %x.lcssa2 = phi i32 [ %x, %latch ]
+loopexit3:
+  br label %loop_with_insert_point
+
+; CHECK: loop_with_insert_point:
+; CHECK:   %x4 = phi i32 [ %x4, %loop_with_insert_point ], [ %x.lcssa2, %loopexit3 ], [ %x.lcssa, %loopexit1 ]
+loop_with_insert_point:
+  br i1 undef, label %loop_with_insert_point, label %bb
+
+; CHECK: bb:
+; CHECK:   %x4.lcssa = phi i32 [ %x4, %loop_with_insert_point ]
+bb:
+  br label %exit
+
+; CHECK: exit:
+; CHECK:   %x3 = phi i32 [ %x4.lcssa, %bb ], [ %x.lcssa1, %loopexit2 ]
+exit:
+  ret i32 %x
+}
+
+; CHECK-LABEL: @foo2
+define internal i32 @foo2() {
+entry:
+  br label %header
+
+header:
+  %x = add i32 0, 1
+  br i1 undef, label %latch, label %loopexit1
+
+latch:
+  br i1 undef, label %header, label %loopexit2
+
+; CHECK: loopexit1:
+; CHECK:   %x.lcssa = phi i32 [ %x, %header ]
+loopexit1:
+  br label %loop_with_insert_point
+
+; CHECK: loopexit2:
+; CHECK:   %x.lcssa1 = phi i32 [ %x, %latch ]
+loopexit2:
+  br label %loop_with_insert_point
+
+; CHECK: loop_with_insert_point:
+; CHECK:   %x2 = phi i32 [ %x2, %loop_with_insert_point ], [ %x.lcssa1, %loopexit2 ], [ %x.lcssa, %loopexit1 ]
+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
+}