[IndVars] Forget the SCEV when the instruction has been sunk.

[StephenFan]

Summary

In the past, the SCEV expression of the sunk instruction was not
forgetted. This led to the incorrect block dispositions after the
instruction be sunk.

Fixes https://github.com/llvm/llvm-project/issues/58662

[StephenFan]

The test will be added if it is the right fix.

[nikic]

This is likely not the right fix. I don't see how there can be an addrec whose start value is not available at loop entry (of its own loop).

[nikic]

Marking this as changes request, as this does not look correct without more information. A reduced test case that shows how the addrec looks like would be helpful. (Maybe something like this could happen in unreachable code or something.)

[StephenFan]

In D137060#3898526, @nikic wrote:

Marking this as changes request, as this does not look correct without more information. A reduced test case that shows how the addrec looks like would be helpful. (Maybe something like this could happen in unreachable code or something.)

@f = dso_local global i16 0, align 2
@a = dso_local global i32 0, align 4
@b = dso_local global i32 0, align 4
@d = dso_local global i32 0, align 4
@e = dso_local global i32 0, align 4
@g = dso_local global i8 0, align 1

define dso_local zeroext i8 @l() local_unnamed_addr #2 {
entry:
  %0 = load i32, ptr @b, align 4
  %a.promoted = load i32, ptr @a, align 4
  br label %for.cond

for.cond:                                         ; preds = %h.exit, %entry
  %inc8 = phi i32 [ %a.promoted, %entry ], [ %inc, %h.exit ]
  %storemerge = phi i16 [ 0, %entry ], [ %sub6, %h.exit ]
  %inc = add nsw i32 %inc8, 1
  %and = and i32 %0, %inc
  %conv = sext i16 %storemerge to i32
  %sub = add nsw i32 %conv, -6
  br label %while.body.i

while.body.i:                                     ; preds = %for.cond, %while.body.i
  %c.05.i = phi i32 [ %inc.i, %while.body.i ], [ 0, %for.cond ]
  %i.addr.04.i = phi i32 [ %shr.i, %while.body.i ], [ %sub, %for.cond ]
  %shr.i = ashr i32 %i.addr.04.i, 1
  %inc.i = add nsw i32 %c.05.i, 1
  %cmp.i = icmp sgt i32 %c.05.i, 5
  %tobool.not.i = icmp ult i32 %i.addr.04.i, 4
  %or.cond.i = select i1 %cmp.i, i1 true, i1 %tobool.not.i
  br i1 %or.cond.i, label %h.exit, label %while.body.i

h.exit:                                           ; preds = %while.body.i
  %inc.i.lcssa = phi i32 [ %inc.i, %while.body.i ]
  %1 = trunc i32 %and to i8
  %2 = trunc i32 %inc.i.lcssa to i8
  %3 = sub i8 %1, %2
  %tobool.not = icmp eq i8 %3, 17
  %sub6 = add i16 %storemerge, -8
  br i1 %tobool.not, label %for.cond, label %if.then

if.then:                                          ; preds = %h.exit
  %storemerge.lcssa = phi i16 [ %storemerge, %h.exit ]
  %inc.lcssa = phi i32 [ %inc, %h.exit ]
  %and.lcssa = phi i32 [ %and, %h.exit ]
  %inc.i.lcssa.lcssa = phi i32 [ %inc.i.lcssa, %h.exit ]
  store i16 %storemerge.lcssa, ptr @f, align 2
  store i32 %inc.lcssa, ptr @a, align 4
  store i32 %and.lcssa, ptr @d, align 4
  store i32 %inc.i.lcssa.lcssa, ptr @e, align 4
  %4 = load i8, ptr @g, align 1
  ret i8 %4
}

This is the test case that I am debugging. But I have not reduced it.
The scalar evolution output of %3 = sub i8 %1, %2 is {(-1 + (trunc i32 %and to i8)),+,-1}<%while.body.i> U: full-set S: full-set --> (-1 + (trunc i32 %and to i8)) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond: Variant, %while.body.i: Computable }
It seems that this problem is caused by calling isKnownOnEveryIteration with the SCEVAddRecExpr above. Since the above SCEV's LoopHeader is while.body.i but the start value is not available at while.body.i's entry.

[StephenFan]

Change solution.

[StephenFan]

Drop previous solution.

[fhahn]

Thanks for the update. Could you add a test case?

[StephenFan]

Fix grammer.

[StephenFan]

In D137060#3902907, @fhahn wrote:

Thanks for the update. Could you add a test case?

Yes. I will add a test case tomorrow.

[nikic]

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

1284

I think you can drop the forgetBlockAndLoopDispositions() call now, it should be handled by forgetValue().

[StephenFan]

Add a test case and drop the forgetBlockAndLoopDispositions call.

[StephenFan]

Update.

[nikic]

llvm/test/Transforms/IndVarSimplify/pr58662.ll

99 ↗

(On Diff #472851)

Could you please reduce this test case further? Just running it through llvm-reduce already produces something smaller (https://gist.github.com/nikic/b315c6ab41ee4676c2a32953a077a3e9), and possibly further manual reduction is possible.

[StephenFan]

reduce test case.

[fhahn]

LGTM, thanks!

llvm/test/Transforms/IndVarSimplify/pr58662.ll

6 ↗

(On Diff #472951)

It looks like there already SCEV invalidation tests in llvm/test/Transforms/IndVarSimplify/scev-invalidation.ll. Could you move the test there?

33 ↗

(On Diff #472951)

Naming could be improved to make things easier to read, e.g. %for.cond -> outer.header, while.body.i -> inner, h.exit-> outer.latch.

34 ↗

(On Diff #472951)

store merge -> outer.iv, sub6 -> outer.iv.next

48 ↗

(On Diff #472951)

this seems mis-named, maybe just lcssa?

[StephenFan]

Move test case and reduce variable name.

[StephenFan]

Thanks for reviewing! And thanks @nikic for providing a reduced test case.

llvm/lib/Transforms/Scalar/IndVarSimplify.cpp

if (I != Preheader->begin()) {
       if (I->isDebugOrPseudoInst() && I == Preheader->begin())
         Done = true;
     } else {
       Done = true;
     }
 
     MadeAnyChanges = true;
     ToMove->moveBefore(*ExitBlock, InsertPt);
-    SE->forgetBlockAndLoopDispositions(ToMove);
+    SE->forgetValue(ToMove);
     if (Done) break;
     InsertPt = ToMove->getIterator();
   }
 
   return MadeAnyChanges;
 }
 
 static void replaceExitCond(BranchInst *BI, Value *NewCond,

llvm/test/Transforms/IndVarSimplify/scev-invalidation.ll

loop:
   %c.1 = icmp eq i32 %iv.next, %or
   %c.ext = zext i1 %c.1 to i32
   br i1 false, label %loop, label %exit
 
 exit:
   %res = add i32 %c.ext, %or
   ret i32 %res
 }
+
+define i8 @l(i32 %inc, i1 %tobool.not.i) {
+; CHECK-LABEL: @l(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    br label [[INNER:%.*]]
+; CHECK:       inner:
+; CHECK-NEXT:    [[C_05_I:%.*]] = phi i32 [ [[INC_I:%.*]], [[INNER]] ], [ 0, [[OUTER_HEADER]] ]
+; CHECK-NEXT:    [[INC_I]] = add nuw nsw i32 [[C_05_I]], 1
+; CHECK-NEXT:    [[CMP_I:%.*]] = icmp ugt i32 [[C_05_I]], 0
+; CHECK-NEXT:    [[OR_COND_I:%.*]] = select i1 [[CMP_I]], i1 true, i1 [[TOBOOL_NOT_I:%.*]]
+; CHECK-NEXT:    br i1 [[OR_COND_I]], label [[OUTER_LATCH:%.*]], label [[INNER]]
+; CHECK:       outer.latch:
+; CHECK-NEXT:    [[C_05_I_LCSSA:%.*]] = phi i32 [ [[C_05_I]], [[INNER]] ]
+; CHECK-NEXT:    [[LCSSA:%.*]] = phi i32 [ 0, [[INNER]] ]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 1, [[INC:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = trunc i32 [[AND]] to i8
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i32 [[C_05_I_LCSSA]] to i8
+; CHECK-NEXT:    [[TMP2:%.*]] = sub i8 [[TMP0]], [[TMP1]]
+; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP2]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label [[OUTER_HEADER]], label [[IF_THEN:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    ret i8 0
+;
+entry:
+  br label %outer.header
+
+outer.header:                                         ; preds = %h.exit, %entry
+  %outer.iv = phi i16 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
+  %and = and i32 1, %inc
+  %conv = sext i16 %outer.iv to i32
+  br label %inner
+
+inner:                                     ; preds = %while.body.i, %for.cond
+  %c.05.i = phi i32 [ %inc.i, %inner ], [ 0, %outer.header ]
+  %i.addr.04.i = phi i32 [ 0, %inner ], [ %conv, %outer.header ]
+  %inc.i = add nsw i32 %c.05.i, 1
+  %cmp.i = icmp sgt i32 %c.05.i, 0
+  %or.cond.i = select i1 %cmp.i, i1 true, i1 %tobool.not.i
+  br i1 %or.cond.i, label %outer.latch, label %inner
+
+outer.latch:                                           ; preds = %while.body.i
+  %lcssa = phi i32 [ 0, %inner ]
+  %0 = trunc i32 %and to i8
+  %1 = trunc i32 %c.05.i to i8
+  %2 = sub i8 %0, %1
+  %tobool.not = icmp eq i8 %2, 0
+  %outer.iv.next = add i16 %outer.iv, 1
+  br i1 %tobool.not, label %outer.header, label %if.then
+
+if.then:                                          ; preds = %h.exit
+  ret i8 0
+}