[LCSSA] Forget values we create LCSSA phis for

[fhahn]

Summary

Currently we only forget the loop we added LCSSA phis for. But SCEV
expressions in other loops could also depend on the instruction we added
a PHI for and currently we do not invalidate those expressions. This can
happen when we use ScalarEvolution before converting a function to LCSSA
form. The SCEV expressions will refer to the non-LCSSA value. If this
SCEV expression is then used with the expander, we do not preserve LCSSA
form.

This patch properly forgets the values we created PHIs for. Those need
to be recomputed again. This patch fixes PR43458.

Currently SCEV::verify does not catch this mismatch and any test would
need to run multiple passes to trigger the error (e.g. -loop-reduce
-loop-unroll). I will also look into catching this kind of mismatch in
the verifier. Also, we currently forget the whole loop in LCSSA and I'll
check if we can be more surgical.

[hiraditya]

LGTM, can we add test case from the PR?
https://bugs.llvm.org/show_bug.cgi?id=43458

[fhahn]

Add test.

[sanjoy.google]

If the SCEV expression is mathematically correct I think this is a problem with SCEV expander. If it is expected to preserve LCSSA it should add the necessary PHIs.

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll

77

Minor thing: I'd avoid adding branches on undef (unless you need them to reproduce the test) because there is no guarantee on how the optimizers will optimize these.

(It is also unclear whether this is UB.)

[efriedma]

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

[fhahn]

In D68194#1698311, @efriedma wrote:

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

AFAICT, there are at least 2 issues that need addressing if we want to handle LCSSA PHIs differently: 1) teach SCEV to look through LCSSA phis and 2) updating SCEV expander to insert LCSSA Phi nodes, if required. Incidentally, I started out with a patch to fix the issue in the expander. But addressing both 1) and 2) seems like a more fundamental change.

As a first step I guess we could try to find some cases where we would get more precise results by looking through LCSSA PHIs. IMO that would be a better motivation than just the expander issue.

[fhahn]

remove undef branch conditions from tests.

[fhahn]

llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll

77

Excellent point, thanks! This was originally reduced by bug point which likes undef, but I've added proper conditions now.

[fhahn]

ping. I did not have time to look into looking through LCSSA phis in SCEV, but I think it will be quite a complex change. I think it would be great if we could get in this fix regardless of addressing the bigger issue.

[efriedma]

LGTM

[fhahn]

In D68194#1698311, @efriedma wrote:

I know this contradicts existing code in SCEV that tries not to break LCSSA, I'm wondering if we should just remove those in favor of teaching SCEV expander about preserving LCSSA.

Currently, SCEV deliberately doesn't look through LCSSA PHI nodes (there's code in ScalarEvolution::createNodeForPHI etc.). You're saying we should change that? It might be a good idea. I recently ran into an performance issue involving a nested loop where SCEV for the outer loop was getting confused by an LCSSA PHI for the inner loop. I'd be worried about loop passes getting confused, though; for example, if they assume all AddRecs are part of the current loop nest.

That said, this patch probably isn't the right place to have that discussion.

I've put up a WIP patch that teaches SCEVExpander to preserve LCSSA while expanding: D71538 it still needs a bit of refactoring and cleanup. And D71539 to look through trivial PHIs which also needs a bit of work.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// node is inserted and the uses outside the loop are rewritten to use this
 /// node.
 ///
 /// LoopInfo and DominatorTree are required and, since the routine makes no
 /// changes to CFG, preserved.
 ///
 /// Returns true if any modifications are made.
 bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
-                              DominatorTree &DT, LoopInfo &LI);
+                              DominatorTree &DT, LoopInfo &LI,
+                              ScalarEvolution *SE);
 
 /// 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. Sub-loops must be in LCSSA form
 /// already.
 ///

llvm/lib/Transforms/Utils/LCSSA.cpp

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) {
+                                    DominatorTree &DT, LoopInfo &LI,
+                                    ScalarEvolution *SE) {
   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.
while (!Worklist.empty()) {
 
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
     SmallVector<PHINode *, 4> InsertedPHIs;
     SSAUpdater SSAUpdate(&InsertedPHIs);
     SSAUpdate.Initialize(I->getType(), I->getName());
 
+    // Force re-computation of I, as some users now need to use the new PHI
+    // node.
+    if (SE)
+      SE->forgetValue(I);
+
     // 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))
for (Instruction &I : *BB) {
       // instructions in Windows EH if the catchswitch has one catchpad which
       // is inside the loop and another which is not.
       if (I.getType()->isTokenTy())
         continue;
 
       Worklist.push_back(&I);
     }
   }
-  Changed = formLCSSAForInstructions(Worklist, DT, *LI);
+  Changed = formLCSSAForInstructions(Worklist, DT, *LI, SE);
 
   // If we modified the code, remove any caches about the loop from SCEV to
   // avoid dangling entries.
   // FIXME: This is a big hammer, can we clear the cache more selectively?
   if (SE && Changed)
     SE->forgetLoop(&L);
 
   assert(L.isLCSSAForm(DT));

llvm/test/Transforms/LoopUnroll/unroll-preserve-scev-lcssa.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -loop-reduce -loop-unroll -unroll-runtime -verify-scev -verify-loop-lcssa < %s -S | FileCheck %s
+
+; Test case for PR43458. We check that we do properly invalidate LCSSA phi
+; users in SCEV. Run -loop-reduce first, so SCEV is already populated.
+
+define void @spam() {
+; CHECK-LABEL: @spam(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    br i1 false, label [[BB9:%.*]], label [[BB5_PREHEADER:%.*]]
+; CHECK:       bb5.preheader:
+; CHECK-NEXT:    br label [[BB5:%.*]]
+; CHECK:       bb5:
+; CHECK-NEXT:    br label [[BB9]]
+; CHECK:       bb9:
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i64 [ 0, [[BB3]] ], [ 5, [[BB5]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = trunc i64 [[TMP10]] to i32
+; CHECK-NEXT:    [[TMP21:%.*]] = sext i32 [[TMP11]] to i64
+; CHECK-NEXT:    [[TMP22:%.*]] = icmp slt i64 0, [[TMP21]]
+; CHECK-NEXT:    br i1 [[TMP22]], label [[BB24_PREHEADER:%.*]], label [[BB29:%.*]]
+; CHECK:       bb24.preheader:
+; CHECK-NEXT:    br label [[BB24:%.*]]
+; CHECK:       bb24:
+; CHECK-NEXT:    [[TMP25:%.*]] = phi i64 [ [[TMP26:%.*]], [[BB24]] ], [ 0, [[BB24_PREHEADER]] ]
+; CHECK-NEXT:    [[TMP26]] = add nuw nsw i64 [[TMP25]], 1
+; CHECK-NEXT:    [[TMP27:%.*]] = icmp slt i64 [[TMP26]], [[TMP21]]
+; CHECK-NEXT:    br i1 [[TMP27]], label [[BB24]], label [[BB29_LOOPEXIT:%.*]]
+; CHECK:       bb29.loopexit:
+; CHECK-NEXT:    br label [[BB29]]
+; CHECK:       bb29:
+; CHECK-NEXT:    ret void
+;
+bb:
+  br label %bb3
+
+bb3:                                              ; preds = %bb9, %bb
+  %pv1 = phi i64 [ 0, %bb ], [ %iv1, %bb9]
+  %c1 = icmp eq i64 %pv1, 5
+  br i1 %c1, label %bb9, label %bb5
+
+bb5:                                              ; preds = %bb5, %bb3
+  %pv = phi i64 [ 0, %bb3], [ %tmp6, %bb5]
+  %tmp6 = add nsw i64 %pv, 1
+  %cond = icmp eq i64 %tmp6, 5
+  br i1 %cond, label %bb8, label %bb5
+
+bb8:                                              ; preds = %bb5
+  br label %bb9
+
+bb9:                                              ; preds = %bb8, %bb3
+  %tmp10 = phi i64 [ 0, %bb3 ], [ %tmp6, %bb8 ]
+  %tmp11 = trunc i64 %tmp10 to i32
+  %iv1 = add nsw i64 %pv1, 1
+  br i1 false, label %bb3, label %bb20
+
+bb20:                                             ; preds = %bb9
+  %tmp21 = sext i32 %tmp11 to i64
+  %tmp22 = icmp slt i64 0, %tmp21
+  br i1 %tmp22, label %bb24, label %bb29
+
+bb24:                                             ; preds = %bb24, %bb20
+  %tmp25 = phi i64 [ %tmp26, %bb24 ], [ 0, %bb20 ]
+  %tmp26 = add nuw nsw i64 %tmp25, 1
+  %tmp27 = icmp slt i64 %tmp26, %tmp21
+  br i1 %tmp27, label %bb24, label %bb29
+
+bb29:                                             ; preds = %bb24, %bb20
+  ret void
+}