[LoopRotate] Forget SCEV values in RewriteUsesOfClonedInstructions

[bjope]

Summary

This patch fixes problems reported in PR51981.

When rotating a loop it isn't enough to just forget SCEV for that
loop nest. When rotating we might clone some instructions from the
old header into the preheader, and insert new PHI nodes to merge
values together. There could be users of the original value that are
updated to use the PHI result. And those users were not necessarily
depending on a PHI node earlier, so they weren't cleaned up when just
forgetting all SCEV:s for the loop nest. So we need to explicitly
forget those values to avoid invalid cached SCEV expressions.

[bjope]

Notice that I feel a bit "on deep water" here. Is the patch (and the description in the commit msg) making sense?

Btw, I'm not sure if this is enough to keep ScalarEvolution valid throughout LoopRotate. There is for example a comment on line 769 that says "I don't believe this invalidates SCEV." that looks a bit fearsome.

[bjope]

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

837

I think that at least SE could be made a reference instead of a pointer here. At least loop-rotate always fetches ScalarEvolution nowadays (but probably also DominatorTree).
So we could get rid of the conditional checks if SE is non-null.

Maybe I'll fix that in a separate patch later. Unless someone beats me to it.

[fhahn]

When rotating a loop it isn't enough to just forget SCEV for that loop nest.

I think this analysis is correct; the expression for phi that's now outside the loop won't be cleared by forgetting the loop

Btw, I'm not sure if this is enough to keep ScalarEvolution valid throughout LoopRotate. There is for example a comment on line 769 that says "I don't believe this invalidates SCEV." that looks a bit fearsome.

There are probably still other issue lurking unfortunately, same as in other parts of the codebase.

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

837

Sounds like a good cleanup!

[fhahn]

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

[bjope]

Rebased after modifications in D110812.

[bjope]

In D110813#3041983, @fhahn wrote:

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

Yep. I've downloaded D110385, and used verify<scalar-evolution> after loop-rotate instead of print<scalar-evolution>. Then I see this:

Cached block disposition of SCEV (trunc i32 %wide to i16) for basic block: 
loop.inner:                                       ; preds = %loop.inner, %loop.inner.ph
  %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
  %iv.promoted = zext i16 %iv to i32
  %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted
  store i32 7, i32* %gep, align 1
  %iv.plus = add i16 %iv, 1
  %cmp = icmp ult i16 %iv.plus, 700
  br i1 %cmp, label %loop.inner, label %loop.outer.latch
 has changed!
Cached: 2
Actual: 0

[bjope]

In D110813#3045467, @bjope wrote:

In D110813#3041983, @fhahn wrote:

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

Yep. I've downloaded D110385, and used verify<scalar-evolution> after loop-rotate instead of print<scalar-evolution>. Then I see this:

Cached block disposition of SCEV (trunc i32 %wide to i16) for basic block: 
loop.inner:                                       ; preds = %loop.inner, %loop.inner.ph
  %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
  %iv.promoted = zext i16 %iv to i32
  %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted
  store i32 7, i32* %gep, align 1
  %iv.plus = add i16 %iv, 1
  %cmp = icmp ult i16 %iv.plus, 700
  br i1 %cmp, label %loop.inner, label %loop.outer.latch
 has changed!
Cached: 2
Actual: 0

But only for the RUN-lines that uses print<scalar-evolution> before loop-rotate. When using loop(canon-freeze) I get the same kind of crash in the verifier as when using the print pass.

[mkazantsev]

That's exactly the kind of things I'm hunting. Thanks!
There might be more of this type. It would be nice if we could somehow find and fix them.

[fhahn]

In D110813#3047663, @mkazantsev wrote:

That's exactly the kind of things I'm hunting. Thanks!
There might be more of this type. It would be nice if we could somehow find and fix them.

Great to see issues like this being caught by the verification!

In D110813#3045494, @bjope wrote:

In D110813#3045467, @bjope wrote:

In D110813#3041983, @fhahn wrote:

It looks like the crash/differences may be caused by stale entries in the loop disposition cache. Are those caught by the checks in D110385?

Yep. I've downloaded D110385, and used verify<scalar-evolution> after loop-rotate instead of print<scalar-evolution>. Then I see this:

Cached block disposition of SCEV (trunc i32 %wide to i16) for basic block: 
loop.inner:                                       ; preds = %loop.inner, %loop.inner.ph
  %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
  %iv.promoted = zext i16 %iv to i32
  %gep = getelementptr inbounds [11263 x i32], [11263 x i32]* @array, i32 0, i32 %iv.promoted
  store i32 7, i32* %gep, align 1
  %iv.plus = add i16 %iv, 1
  %cmp = icmp ult i16 %iv.plus, 700
  br i1 %cmp, label %loop.inner, label %loop.outer.latch
 has changed!
Cached: 2
Actual: 0

But only for the RUN-lines that uses print<scalar-evolution> before loop-rotate. When using loop(canon-freeze) I get the same kind of crash in the verifier as when using the print pass.

Thanks for checking!

LGTM!

[mkazantsev]

In D110813#3047685, @fhahn wrote:

In D110813#3047663, @mkazantsev wrote:

That's exactly the kind of things I'm hunting. Thanks!
There might be more of this type. It would be nice if we could somehow find and fix them.

Great to see issues like this being caught by the verification!

I'm glad someone can do it, because I'm trying to investigate a bug where verification dies before it can find the bug because of dangling pointers. :)

[mkazantsev]

I've updated verifier patch and added this one as unit test for verifier. I hope you don't mind @bjope. :)

llvm/lib/Transforms/Utils/LoopRotationUtils.cpp

 //===----------------- LoopRotationUtils.cpp -----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 }
 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
 /// old header into the preheader.  If there were uses of the values produced by
 /// these instruction that were outside of the loop, we have to insert PHI nodes
 /// to merge the two values.  Do this now.
 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                             BasicBlock *OrigPreheader,
                                             ValueToValueMapTy &ValueMap,
+                                            ScalarEvolution *SE,
                                 SmallVectorImpl<PHINode*> *InsertedPHIs) {
   // Remove PHI node entries that are no longer live.
   BasicBlock::iterator I, E = OrigHeader->end();
   for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
     PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
 
   // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
   // as necessary.
   SSAUpdater SSA(InsertedPHIs);
   for (I = OrigHeader->begin(); I != E; ++I) {
     Value *OrigHeaderVal = &*I;
 
     // If there are no uses of the value (e.g. because it returns void), there
     // is nothing to rewrite.
     if (OrigHeaderVal->use_empty())
       continue;
 
     Value *OrigPreHeaderVal = ValueMap.lookup(OrigHeaderVal);
 
     // The value now exits in two versions: the initial value in the preheader
     // and the loop "next" value in the original header.
     SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
+    // Force re-computation of OrigHeaderVal, as some users now need to use the
+    // new PHI node.
+    if (SE)
+      SE->forgetValue(OrigHeaderVal);
     SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
     SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
 
     // Visit each use of the OrigHeader instruction.
     for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
                              UE = OrigHeaderVal->use_end();
          UI != UE;) {
       // Grab the use before incrementing the iterator.
if (MSSAU) {
       InsertNewValueIntoMap(ValueMapMSSA, OrigHeader, OrigPreheader);
       MSSAU->updateForClonedBlockIntoPred(OrigHeader, OrigPreheader,
                                           ValueMapMSSA);
     }
 
     SmallVector<PHINode*, 2> InsertedPHIs;
     // If there were any uses of instructions in the duplicated block outside the
     // loop, update them, inserting PHI nodes as required
-    RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap,
+    RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap, SE,
                                     &InsertedPHIs);
 
     // Attach dbg.value intrinsics to the new phis if that phi uses a value that
     // previously had debug metadata attached. This keeps the debug info
     // up-to-date in the loop body.
     if (!InsertedPHIs.empty())
       insertDebugValuesForPHIs(OrigHeader, InsertedPHIs);
 
bool LoopRotate::processLoop(Loop *L) {
 
   return MadeChange || SimplifiedLatch;
 }
 
 
 /// The utility to convert a loop into a loop with bottom test.
 bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                         AssumptionCache *AC, DominatorTree *DT,
                         ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
                         const SimplifyQuery &SQ, bool RotationOnly = true,
                         unsigned Threshold = unsigned(-1),
                         bool IsUtilMode = true, bool PrepareForLTO) {
   LoopRotate LR(Threshold, LI, TTI, AC, DT, SE, MSSAU, SQ, RotationOnly,
                 IsUtilMode, PrepareForLTO);
   return LR.processLoop(L);
 }

llvm/test/Transforms/LoopRotate/pr51981-scev-problem.ll

-; RUN: opt < %s -passes='print<scalar-evolution>,loop(loop-rotate),invalidate<scalar-evolution>,print<scalar-evolution>' -disable-output 2>&1 | FileCheck -check-prefixes CHECK-SCEV,CHECK-SCEV-OK %s
-; RUN: opt < %s -passes='print<scalar-evolution>,loop(loop-rotate),print<scalar-evolution>' -disable-output 2>&1 | FileCheck -check-prefixes CHECK-SCEV,CHECK-SCEV-NOK %s
-; FIXME (crashes): opt < %s -passes='loop(canon-freeze),loop(loop-rotate),print<scalar-evolution>' -disable-output
+; RUN: opt < %s -passes='print<scalar-evolution>,loop(loop-rotate),invalidate<scalar-evolution>,print<scalar-evolution>' -disable-output 2>&1 | FileCheck -check-prefixes CHECK-SCEV %s
+; RUN: opt < %s -passes='print<scalar-evolution>,loop(loop-rotate),print<scalar-evolution>' -disable-output 2>&1 | FileCheck -check-prefixes CHECK-SCEV %s
+; RUN: opt < %s -passes='loop(canon-freeze),loop(loop-rotate),print<scalar-evolution>' -disable-output
 
 ; In the first two RUN lines print<scalar-evolution> is used to populate the
-; analysis cache before loop-rotate. That seem to be enough to see the problem
-; by examining print<scalar-evolution> printouts after loop-rotate. However,
-; I've only seen the crashes when using canon-freeze as a trigger to populate
-; the analysis cache.
+; analysis cache before loop-rotate. That was enough to see the problem by
+; examining print<scalar-evolution> printouts after loop-rotate. However, the
+; crashes where only observed when using canon-freeze as a trigger to populate
+; the analysis cache, so that is why canon-freeze is used in the third RUN
+; line.
 
-; Verify that we get the same SCEV expressions after loop-rotate, regardless if we invalidate scalar-evolution before the final printing or not.
-; FIXME: As indicated by CHECK-SCEV-OK vs CHECK-SCEV-NOK this isn't currently true (PR51981).
+; Verify that we get the same SCEV expressions after loop-rotate, regardless
+; if we invalidate scalar-evolution before the final printing or not.
+;
+; This used to fail as described by PR51981 (some expressions still referred
+; to (trunc i32 %div210 to i16) but after the rotation it should be (trunc i32
+; %div2102 to i16).
 ;
 ; CHECK-SCEV: Classifying expressions for: @test_function
 ; CHECK-SCEV:   %wide = load i32, i32* @offset, align 1
 ; CHECK-SCEV:   -->  %wide U: full-set S: full-set          Exits: <<Unknown>>              LoopDispositions: { %loop.outer.header: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %narrow = trunc i32 %wide to i16
 ; CHECK-SCEV:   -->  (trunc i32 %wide to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.outer.header: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
 ; CHECK-SCEV:   -->  {(trunc i32 %wide to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.outer.header: Variant }
 ;
 ; CHECK-SCEV: Classifying expressions for: @test_function
 ; CHECK-SCEV:   %wide1 = load i32, i32* @offset, align 1
 ; CHECK-SCEV:   -->  %wide1 U: full-set S: full-set
 ; CHECK-SCEV:   %wide2 = phi i32 [ %wide1, %loop.inner.ph.lr.ph ], [ %wide, %loop.outer.latch ]
 ; CHECK-SCEV:   -->  %wide2 U: full-set S: full-set         Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %narrow = trunc i32 %wide2 to i16
-; CHECK-SCEV-OK:   -->  (trunc i32 %wide2 to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
-; CHECK-SCEV-NOK:   -->  (trunc i32 %wide to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
+; CHECK-SCEV:   -->  (trunc i32 %wide2 to i16) U: full-set S: full-set               Exits: <<Unknown>>              LoopDispositions: { %loop.inner.ph: Variant, %loop.inner: Invariant }
 ; CHECK-SCEV:   %iv = phi i16 [ %narrow, %loop.inner.ph ], [ %iv.plus, %loop.inner ]
-; CHECK-SCEV-OK:   -->  {(trunc i32 %wide2 to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide2 to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.inner.ph: Variant }
-; CHECK-SCEV-NOK:   -->  {(trunc i32 %wide to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.inner.ph: Variant }
+; CHECK-SCEV:   -->  {(trunc i32 %wide2 to i16),+,1}<%loop.inner> U: full-set S: full-set           Exits: (-1 + (700 umax (1 + (trunc i32 %wide2 to i16))))               LoopDispositions: { %loop.inner: Computable, %loop.inner.ph: Variant }
 
 
 @offset = external dso_local global i32, align 1
 @array = internal global [11263 x i32] zeroinitializer, align 1
 
 define void @test_function(i1 %cond) {
 entry:
   br label %loop.outer.header