[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 ↗

(On Diff #472694)

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/Analysis/ScalarEvolution.cpp

else if (isBasicBlockEntryGuardedByCond(CtxI->getParent(),
     return false;
   return None;
 }
 
 bool ScalarEvolution::isKnownOnEveryIteration(ICmpInst::Predicate Pred,
                                               const SCEVAddRecExpr *LHS,
                                               const SCEV *RHS) {
   const Loop *L = LHS->getLoop();
-  return isLoopEntryGuardedByCond(L, Pred, LHS->getStart(), RHS) &&
+  const SCEV *Start = LHS->getStart();
+  if (!isAvailableAtLoopEntry(Start, L))
+    return false;
+
+  return isLoopEntryGuardedByCond(L, Pred, Start, RHS) &&
          isLoopBackedgeGuardedByCond(L, Pred, LHS->getPostIncExpr(*this), RHS);
 }
 
 Optional<ScalarEvolution::MonotonicPredicateType>
 ScalarEvolution::getMonotonicPredicateType(const SCEVAddRecExpr *LHS,
                                            ICmpInst::Predicate Pred) {
   auto Result = getMonotonicPredicateTypeImpl(LHS, Pred);