[LCSSA] Don't use VH callbacks to invalidate SCEV when creating LCSSA phis

[DaniilSuchkov]

Summary

In general ValueHandleBase::ValueIsRAUWd shouldn't be called when not all uses of the value were actually replaced, though, currently formLCSSAForInstructions calls it when it inserts LCSSA-phis.

Calls of ValueHandleBase::ValueIsRAUWd were added to LCSSA specifically to update/invalidate SCEV. In the best case these calls duplicate some of the work already done by SE->forgetValue, though in case when SCEV of the value is SCEVUnknown, SCEV replaces the underlying value of SCEVUnknown with the new value (i.e. acts like LCSSA-phi actually fully replaces the value it is created for), which leads to SCEV being corrupted because LCSSA-phi rarely dominates all uses of its inputs.

This fixes bug https://bugs.llvm.org/show_bug.cgi?id=44058.

[DaniilSuchkov]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

322

This change is required to preserve current behavior in cases when it's valid: sometimes invalidation of SCEV through VH actually worked as intended.

[efriedma]

Are the changes to loop unswitch supposed to be in this patch?

[DaniilSuchkov]

In D70593#1759353, @efriedma wrote:

Are the changes to loop unswitch supposed to be in this patch?

Yes. I knew it won't be obvious, so I left an inline comment:

This change is required to preserve current behavior in cases when it's valid: sometimes invalidation of SCEV through VH actually worked as intended.

[fhahn]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

322

Do you have a test case that breaks when passing nullptr? After a quick scan of the code, it looks like SimpleLoopUnswitch forgets the whole loop when making changes (but I am not sure if that holds for all paths that use formLCSSA). But the SimpleLoopUnswitch tests all seem to pass when passing nullptr.

llvm/test/Transforms/LCSSA/pr44058.ll

2

if you're not checking the output, maybe pass -disable-output?

Also, can you also run using the legacy pass manager? It's still the default.....

[DaniilSuchkov]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

322

Do you have a test case that breaks when passing nullptr?

No, don't have one. I have tried to write such a test but failed.

After a quick scan of the code, it looks like SimpleLoopUnswitch forgets the whole loop when making changes (but I am not sure if that holds for all paths that use formLCSSA).

Yes, but for SCEV "forget the whole loop" doesn't include "forget all values defined within the loop".

But I personally don't want to find such a test by submitting this patch without any changes to SimpleLoopUnswitch and waiting for bugs to come.

By the way, if you wonder why only this pass was modified: it is because this pass is the only user of "formLCSSA" function outside LCSSAPass.

llvm/test/Transforms/LCSSA/pr44058.ll

2

if you're not checking the output, maybe pass -disable-output?

Ok

Also, can you also run using the legacy pass manager? It's still the default.....

To my knowledge there is no clear way to get effect of the first "verify<scalar-evolution>" invocation when using legacy PM. If I'm wrong and you know how to force SCEV cache population without tricks like "lets invoke a pass that (hopefully) won't transform anything but will (again, hopefully) perform SCEV queries we need", I will happily add a command for legacy PM too.

[fhahn]

LGTM, but please wait a bit before committing (with Thanksgiving coming up, maybe till early next week?), in case someone more familiar with the SimpleLoopUnswitch internals wants to chime in.

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

322

Thanks for checking, I was mostly curious if there's something SimpleLoopUnswitch specific that makes us not requiring updating SCEV in fromLCSSA. I tried building SPEC2000, SPEC2006 & the MultiSource tests from test-suite with SimpleLoopUnswitch and scev-verify and everything passed. So in practice, we probably invalidate properly in most cases, but I agree it is better to be on the safe side here!

llvm/test/Transforms/LCSSA/pr44058.ll

2

To my knowledge there is no clear way to get effect of the first "verify<scalar-evolution>" invocation when using legacy PM. If I'm wrong and you know how to force SCEV cache population without tricks like "lets invoke a pass that (hopefully) won't transform anything but will (again, hopefully) perform SCEV queries we need", I will happily add a command for legacy PM too.

Right, I am not sure what the best solution would be for that. Given that, having just the New PM version is probably fine, thanks!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 
 /// Hoist the current loop up to the innermost loop containing a remaining exit.
 ///
 /// Because we've removed an exit from the loop, we may have changed the set of
 /// loops reachable and need to move the current loop up the loop nest or even
 /// to an entirely separate nest.
 static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader,
                                  DominatorTree &DT, LoopInfo &LI,
-                                 MemorySSAUpdater *MSSAU) {
+                                 MemorySSAUpdater *MSSAU, ScalarEvolution *SE) {
   // If the loop is already at the top level, we can't hoist it anywhere.
   Loop *OldParentL = L.getParentLoop();
   if (!OldParentL)
     return;
 
   SmallVector<BasicBlock *, 4> Exits;
   L.getExitBlocks(Exits);
   Loop *NewParentL = nullptr;
for (Loop *OldContainingL = OldParentL; OldContainingL != NewParentL;
 
     OldContainingL->getBlocksSet().erase(&Preheader);
     for (BasicBlock *BB : L.blocks())
       OldContainingL->getBlocksSet().erase(BB);
 
     // Because we just hoisted a loop out of this one, we have essentially
     // created new exit paths from it. That means we need to form LCSSA PHI
     // nodes for values used in the no-longer-nested loop.
-    formLCSSA(*OldContainingL, DT, &LI, nullptr);
+    formLCSSA(*OldContainingL, DT, &LI, SE);
 
     // We shouldn't need to form dedicated exits because the exit introduced
     // here is the (just split by unswitching) preheader. However, after trivial
     // unswitching it is possible to get new non-dedicated exits out of parent
     // loop so let's conservatively form dedicated exit blocks and figure out
     // if we can optimize later.
     formDedicatedExitBlocks(OldContainingL, &DT, &LI, MSSAU,
                             /*PreserveLCSSA*/ true);
static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT,
   // Since this is an i1 condition we can also trivially replace uses of it
   // within the loop with a constant.
   for (Value *Invariant : Invariants)
     replaceLoopInvariantUses(L, Invariant, *Replacement);
 
   // If this was full unswitching, we may have changed the nesting relationship
   // for this loop so hoist it to its correct parent if needed.
   if (FullUnswitch)
-    hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+    hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
 
   LLVM_DEBUG(dbgs() << "    done: unswitching trivial branch...\n");
   ++NumTrivial;
   ++NumBranches;
   return true;
if (MSSAU) {
     if (VerifyMemorySSA)
       MSSAU->getMemorySSA()->verifyMemorySSA();
   }
 
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 
   // We may have changed the nesting relationship for this loop so hoist it to
   // its correct parent if needed.
-  hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU);
+  hoistLoopToNewParent(L, *NewPH, DT, LI, MSSAU, SE);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
 
   ++NumTrivial;
   ++NumSwitches;
   LLVM_DEBUG(dbgs() << "    done: unswitching trivial switch...\n");
   return true;
for (Loop *ChildL : UpdateL) {
       ChildL->verifyLoop();
       assert(ChildL->isRecursivelyLCSSAForm(DT, LI) &&
              "Perturbed a child loop's LCSSA form!");
     }
 #endif
     // First build LCSSA for this loop so that we can preserve it when
     // forming dedicated exits. We don't want to perturb some other loop's
     // LCSSA while doing that CFG edit.
-    formLCSSA(UpdateL, DT, &LI, nullptr);
+    formLCSSA(UpdateL, DT, &LI, SE);
 
     // For loops reached by this loop's original exit blocks we may
     // introduced new, non-dedicated exits. At least try to re-form dedicated
     // exits for these loops. This may fail if they couldn't have dedicated
     // exits to start with.
     formDedicatedExitBlocks(&UpdateL, &DT, &LI, MSSAU, /*PreserveLCSSA*/ true);
   };
 

llvm/lib/Transforms/Utils/LCSSA.cpp

for (Use *UseToRewrite : UsesToRewrite) {
       // in the same block.  It assumes the PHI we inserted is at the end of the
       // block.
       Instruction *User = cast<Instruction>(UseToRewrite->getUser());
       BasicBlock *UserBB = User->getParent();
       if (auto *PN = dyn_cast<PHINode>(User))
         UserBB = PN->getIncomingBlock(*UseToRewrite);
 
       if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
-        // Tell the VHs that the uses changed. This updates SCEV's caches.
-        if (UseToRewrite->get()->hasValueHandle())
-          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
         UseToRewrite->set(&UserBB->front());
         continue;
       }
 
       // If we added a single PHI, it must dominate all uses and we can directly
       // rename it.
       if (AddedPHIs.size() == 1) {
-        // Tell the VHs that the uses changed. This updates SCEV's caches.
-        // We might call ValueIsRAUWd multiple times for the same value.
-        if (UseToRewrite->get()->hasValueHandle())
-          ValueHandleBase::ValueIsRAUWd(*UseToRewrite, AddedPHIs[0]);
         UseToRewrite->set(AddedPHIs[0]);
         continue;
       }
 
       // Otherwise, do full PHI insertion.
       SSAUpdate.RewriteUse(*UseToRewrite);
     }
 

llvm/test/Transforms/LCSSA/pr44058.ll

+; RUN: opt -passes="verify<scalar-evolution>,lcssa,verify<scalar-evolution>" -verify-scev-strict -S %s
+
+; The first SCEV verification is required because it queries SCEV and populates
+; SCEV caches. Second SCEV verification checks if the caches are in valid state.
+
+; Check that the second SCEV verification doesn't fail.
+define void @foo(i32* %arg, i32* %arg1, i1 %arg2) {
+bb:
+  br label %bb3
+
+bb3:                                              ; preds = %bb13, %bb
+  %tmp = load i32, i32* %arg
+  %tmp4 = load i32, i32* %arg1
+  %tmp5 = add i32 %tmp4, %tmp
+  %tmp6 = icmp sgt i32 %tmp5, %tmp
+  br i1 %tmp6, label %bb7, label %bb11
+
+bb7:                                              ; preds = %bb3
+  br i1 %arg2, label %bb10, label %bb8
+
+bb8:                                              ; preds = %bb7
+  %tmp9 = add nsw i32 %tmp, 1
+  ret void
+
+bb10:                                             ; preds = %bb7
+  br label %bb11
+
+bb11:                                             ; preds = %bb10, %bb3
+  %tmp12 = phi i32 [ 0, %bb3 ], [ %tmp4, %bb10 ]
+  br label %bb13
+
+bb13:                                             ; preds = %bb13, %bb11
+  %tmp14 = phi i32 [ %tmp15, %bb13 ], [ 0, %bb11 ]
+  %tmp15 = add nuw nsw i32 %tmp14, 1
+  %tmp16 = icmp slt i32 %tmp15, %tmp12
+  br i1 %tmp16, label %bb13, label %bb3
+}