[LoopSimplify] Preserve LCSSA when merging exit blocks.

[mzolotukhin]

Summary

This fixes PR26682. Also add LCSSA as a preserved pass to LoopSimplify,
that looks correct to me and allows to write a test for the issue.

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

753 ↗

(On Diff #59981)

We should definitely add asserts verifying this. I'd suggest something like

LoopSimplify::runOnFunction() {
#ifndef NDEBUG
  DenseSet<Loop *> InLCSSA;
  // put loops that are in LCSSA in InLCSSA
#endif

  .. do whatever it is that LoopSimplify does ..

#ifndef NDEBUG
  // assert every Loop in InLCSSA is in LCSSA
#endif
}

(i.e. we should also catch cases where simplifying a loop breaks LCSSA in another loop).

786 ↗

(On Diff #59981)

Can this be folded to true? (I'm not asking you to do that in this change itself.)

[mzolotukhin]

lib/Transforms/Utils/LoopSimplify.cpp

753 ↗

(On Diff #59981)

Good point. I'll add some verification.

786 ↗

(On Diff #59981)

Theoretically, there might be users that don't want LCSSA to be preserved. They don't have LCSSA prior loop-simplify, so PreserveLCSSA is false for them. But I'm not sure if such users exist in real world, and I'd be glad to replace it with plain true and always preserve LCSSA here (and eventually in all loop passes).

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

786 ↗

(On Diff #59981)

Yes, I'm more coming to the conclusion that this form of complexity
(having a prior pass affect behavior in a way that isn't obvious in
the IR itself) is probably not worth it unless it is actually paying off in
compile time / code quality.

[mzolotukhin]

• Add verification that LCSSA is not broken (requires D21118).

[mzolotukhin]

• Use existing routine, don't reinvent a wheel.

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

795 ↗

(On Diff #60000)

The indent looks weird -- did you clang-format?

Note: since you're inside an NDEBUG it is fine to pull out the computation to outside the assert.

808 ↗

(On Diff #60000)

Ditto.

[chandlerc]

Minor post-commit coments.

I do think we should just always preserve LCSSA. I can't come up with any good reason for not preserving it, and it gives us one fewer code path to test.

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

791–793

Hoist the assert into the loop? As is, when the assert fires, you have to go step through a bunch ef iterations of stuff to find the loop in question.

803–805

Same comment as above.

[chandlerc]

Minor post-commit coments.

I do think we should just always preserve LCSSA. I can't come up with any good reason for not preserving it, and it gives us one fewer code path to test.

llvm/trunk/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, /* DontDeleteUselessPHIs */ PreserveLCSSA);
+      BI->getSuccessor(1)->removePredecessor(
+          ExitingBlock, /* DontDeleteUselessPHIs */ PreserveLCSSA);
       ExitingBlock->eraseFromParent();
     }
   }
 
   return Changed;
 }
 
 bool llvm::simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
 
       AU.addPreserved<BasicAAWrapperPass>();
       AU.addPreserved<AAResultsWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<ScalarEvolutionWrapperPass>();
       AU.addPreserved<SCEVAAWrapperPass>();
+      AU.addPreservedID(LCSSAID);
       AU.addPreserved<DependenceAnalysisWrapperPass>();
       AU.addPreservedID(BreakCriticalEdgesID);  // No critical edges added.
     }
 
     /// verifyAnalysis() - Verify LoopSimplifyForm's guarantees.
     void verifyAnalysis() const override;
   };
 }

 bool LoopSimplify::runOnFunction(Function &F) {
   bool Changed = false;
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
   SE = SEWP ? &SEWP->getSE() : nullptr;
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+#ifndef NDEBUG
+  if (PreserveLCSSA) {
+    assert(DT && "DT not available.");
+    assert(LI && "LI not available.");
+    bool InLCSSA =
+        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    assert(InLCSSA && "Requested to preserve LCSSA, but it's already broken.");
+  }
+#endif
 
   // Simplify each loop nest in the function.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
     Changed |= simplifyLoop(*I, DT, LI, SE, AC, PreserveLCSSA);
 
+#ifndef NDEBUG
+  if (PreserveLCSSA) {
+    bool InLCSSA =
+        all_of(*LI, [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT); });
+    assert(InLCSSA && "LCSSA is broken after loop-simplify.");
+  }
+#endif
   return Changed;
 }
 
 // FIXME: Restore this code when we re-enable verification in verifyAnalysis
 // below.
 #if 0
 static void verifyLoop(Loop *L) {
   // Verify subloops.

llvm/trunk/test/Transforms/LoopSimplify/pr26682.ll

+; RUN: opt < %s -lcssa -loop-simplify -indvars -S | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-unknown"
+
+@a = external global i32, align 4
+
+; Check that loop-simplify merges two loop exits, but preserves LCSSA form.
+; CHECK-LABEL: @foo
+; CHECK: for:
+; CHECK: %or.cond = and i1 %cmp1, %cmp2
+; CHECK-NOT: for.cond:
+; CHECK: for.end:
+; CHECK: %a.lcssa = phi i32 [ %a, %for ]
+define i32 @foo(i32 %x) {
+entry:
+  br label %for
+
+for:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %for.cond ]
+  %cmp1 = icmp eq i32 %x, 0
+  %iv.next = add nuw nsw i32 %iv, 1
+  %a = load i32, i32* @a
+  br i1 %cmp1, label %for.cond, label %for.end
+
+for.cond:
+  %cmp2 = icmp slt i32 %iv.next, 4
+  br i1 %cmp2, label %for, label %for.end
+
+for.end:
+  %a.lcssa = phi i32 [ %a, %for ], [ %a, %for.cond ]
+  ret i32 %a.lcssa
+}