[IndVars] Invalidate SCEV when IR is changed in rewriteLoopExitValue.

[fhahn]

Summary

At the moment, rewriteLoopExitValue forgets the current phi node in the
loop that collects phis to rewrite. A few lines after the value is
forgotten, SCEV is used again to analyze incoming values and
potentially expand SCEV expression. This means that another SCEV is
created for PN, before the IR is actually updated in the next loop.

This leads to accessing invalid cached expression in combination with

PN should only be changed once the actual incoming exit value is set in
the next loop. Moving invalidation there should ensure that PN is
invalidated in all relevant cases.

[nikic]

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

[mkazantsev]

Agreed, change in test's behavior looks suspicious. Looks like something else is missing.

[fhahn]

In D111495#3053355, @nikic wrote:

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

Thanks for sharing the patch, I completely missed that one! Happy to got with this one, it just looks like it's been marked as changes-planned for a while with a mention of adding something. But it seems like it would be good to go in as is, potentially with the test case in llvm/test/Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll? (I can also commit that test separately).

In D111495#3054169, @mkazantsev wrote:

Agreed, change in test's behavior looks suspicious. Looks like something else is missing.

yeah, it still seems correct but potentially can be fixed by the additional change in D82799

[mkazantsev]

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

[reames]

In D111495#3055151, @mkazantsev wrote:

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

Yeah, but also widespread unfortunately. Whenever we have a case where an analysis is not precise or we have two equally precise states, we have that problem. We don't really have a great way to address this in general.

[nikic]

In D111495#3054492, @fhahn wrote:

In D111495#3053355, @nikic wrote:

This looks like basically the same change as D82799, though there I thought this was just a compile-time optimization, not a correctness fix. In that patch, I also added an extra forgetValue() call in IV widening to prevent the elim-extend.ll test change.

Thanks for sharing the patch, I completely missed that one! Happy to got with this one, it just looks like it's been marked as changes-planned for a while with a mention of adding something. But it seems like it would be good to go in as is, potentially with the test case in llvm/test/Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll? (I can also commit that test separately).

Happy to go with your patch, just wanted to point out the additional forgetValue() call. I never had the time to fully investigate the binary changes, though I think they were of the harmless sort (different but equivalent SCEV expressions).

[mkazantsev]

In D111495#3055252, @reames wrote:

In D111495#3055151, @mkazantsev wrote:

The very fact that invalidation or non-invalidation in SCEV changes behavior (even if the transforms are correct) is worrysome. It introduces more non-determinism in our compilations...

Yeah, but also widespread unfortunately. Whenever we have a case where an analysis is not precise or we have two equally precise states, we have that problem. We don't really have a great way to address this in general.

This may be misleading when we make a change in SCEV and think that it really makes difference, when the only thing it does is caches differently. :(

As for the patch, I'm also fine with that. I don't have strong opinion whether we really want 2nd forget if we know for sure that the results with and without it are both functionally correct. Might be nice to have it anyways just for the sole purpose of consevatism. :)

llvm/lib/Transforms/Utils/LoopUtils.cpp

for (BasicBlock *ExitBB : ExitBlocks) {
     BasicBlock::iterator BBI = ExitBB->begin();
     while ((PN = dyn_cast<PHINode>(BBI++))) {
       if (PN->use_empty())
         continue; // dead use, don't replace it
 
       if (!SE->isSCEVable(PN->getType()))
         continue;
 
-      // It's necessary to tell ScalarEvolution about this explicitly so that
-      // it can walk the def-use list and forget all SCEVs, as it may not be
-      // watching the PHI itself. Once the new exit value is in place, there
-      // may not be a def-use connection between the loop and every instruction
-      // which got a SCEVAddRecExpr for that loop.
-      SE->forgetValue(PN);
-
       // Iterate over all of the values in all the PHI nodes.
       for (unsigned i = 0; i != NumPreds; ++i) {
         // If the value being merged in is not integer or is not defined
         // in the loop, skip it.
         Value *InVal = PN->getIncomingValue(i);
         if (!isa<Instruction>(InVal))
           continue;
 
if (auto *ExitInsn = dyn_cast<Instruction>(ExitVal))
       if (auto *EVL = LI->getLoopFor(ExitInsn->getParent()))
         if (EVL != L)
           assert(EVL->contains(L) && "LCSSA breach detected!");
 #endif
 
     NumReplaced++;
     Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
     PN->setIncomingValue(Phi.Ith, ExitVal);
+    // It's necessary to tell ScalarEvolution about this explicitly so that
+    // it can walk the def-use list and forget all SCEVs, as it may not be
+    // watching the PHI itself. Once the new exit value is in place, there
+    // may not be a def-use connection between the loop and every instruction
+    // which got a SCEVAddRecExpr for that loop.
+    SE->forgetValue(PN);
 
     // If this instruction is dead now, delete it. Don't do it now to avoid
     // invalidating iterators.
     if (isInstructionTriviallyDead(Inst, TLI))
       DeadInsts.push_back(Inst);
 
     // Replace PN with ExitVal if that is legal and does not break LCSSA.
     if (PN->getNumIncomingValues() == 1 &&

llvm/test/Transforms/IndVarSimplify/elim-extend.ll

 ; %outercount is straightforward to widen, besides being in an outer loop.
 ; %innercount is currently blocked by lcssa, so is not widened.
 ; %inneriv can be widened only after proving it has no signed-overflow
 ;   based on the loop test.
 define void @nestedIV(i8* %address, i32 %limit) nounwind {
 ; CHECK-LABEL: @nestedIV(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[LIMITDEC:%.*]] = add i32 [[LIMIT:%.*]], -1
-; CHECK-NEXT:    [[TMP0:%.*]] = sext i32 [[LIMITDEC]] to i64
 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LIMIT]], i32 1)
-; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[SMAX]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT4:%.*]] = zext i32 [[SMAX]] to i64
 ; CHECK-NEXT:    br label [[OUTERLOOP:%.*]]
 ; CHECK:       outerloop:
 ; CHECK-NEXT:    [[INDVARS_IV1:%.*]] = phi i64 [ [[INDVARS_IV_NEXT2:%.*]], [[OUTERMERGE:%.*]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[INNERCOUNT:%.*]] = phi i32 [ [[INNERCOUNT_MERGE:%.*]], [[OUTERMERGE]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV1]], -1
-; CHECK-NEXT:    [[ADR1:%.*]] = getelementptr i8, i8* [[ADDRESS:%.*]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i64 [[INDVARS_IV1]], -1
+; CHECK-NEXT:    [[ADR1:%.*]] = getelementptr i8, i8* [[ADDRESS:%.*]], i64 [[TMP0]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR1]], align 1
 ; CHECK-NEXT:    br label [[INNERPREHEADER:%.*]]
 ; CHECK:       innerpreheader:
 ; CHECK-NEXT:    [[INNERPRECMP:%.*]] = icmp sgt i32 [[LIMITDEC]], [[INNERCOUNT]]
 ; CHECK-NEXT:    br i1 [[INNERPRECMP]], label [[INNERLOOP_PREHEADER:%.*]], label [[OUTERMERGE]]
 ; CHECK:       innerloop.preheader:
-; CHECK-NEXT:    [[TMP2:%.*]] = sext i32 [[INNERCOUNT]] to i64
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[INNERCOUNT]] to i64
+; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = sext i32 [[LIMITDEC]] to i64
 ; CHECK-NEXT:    br label [[INNERLOOP:%.*]]
 ; CHECK:       innerloop:
-; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP2]], [[INNERLOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[INNERLOOP]] ]
+; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[TMP1]], [[INNERLOOP_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[INNERLOOP]] ]
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[ADR2:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR2]], align 1
 ; CHECK-NEXT:    [[ADR3:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV_NEXT]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR3]], align 1
-; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[TMP0]]
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[INNERLOOP]], label [[INNEREXIT:%.*]]
 ; CHECK:       innerexit:
 ; CHECK-NEXT:    [[INNERCOUNT_LCSSA_WIDE:%.*]] = phi i64 [ [[INDVARS_IV_NEXT]], [[INNERLOOP]] ]
-; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
+; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[INNERCOUNT_LCSSA_WIDE]] to i32
 ; CHECK-NEXT:    br label [[OUTERMERGE]]
 ; CHECK:       outermerge:
-; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP3]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
+; CHECK-NEXT:    [[INNERCOUNT_MERGE]] = phi i32 [ [[TMP2]], [[INNEREXIT]] ], [ [[INNERCOUNT]], [[INNERPREHEADER]] ]
 ; CHECK-NEXT:    [[ADR4:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[INDVARS_IV1]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR4]], align 1
 ; CHECK-NEXT:    [[OFS5:%.*]] = sext i32 [[INNERCOUNT_MERGE]] to i64
 ; CHECK-NEXT:    [[ADR5:%.*]] = getelementptr i8, i8* [[ADDRESS]], i64 [[OFS5]]
 ; CHECK-NEXT:    store i8 0, i8* [[ADR5]], align 1
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT2]] = add nuw nsw i64 [[INDVARS_IV1]], 1
-; CHECK-NEXT:    [[EXITCOND4:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT2]], [[WIDE_TRIP_COUNT]]
-; CHECK-NEXT:    br i1 [[EXITCOND4]], label [[OUTERLOOP]], label [[RETURN:%.*]]
+; CHECK-NEXT:    [[EXITCOND5:%.*]] = icmp ne i64 [[INDVARS_IV_NEXT2]], [[WIDE_TRIP_COUNT4]]
+; CHECK-NEXT:    br i1 [[EXITCOND5]], label [[OUTERLOOP]], label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %limitdec = add i32 %limit, -1
   br label %outerloop
 
 ; Eliminate %ofs1 after widening outercount.

llvm/test/Transforms/IndVarSimplify/invalidate-modified-lcssa-phi.ll

 
 latch.1:
   %p.2.next = add i32 %p.2, 1
   br i1 false, label %header.2, label %header.1
 
 latch.2:
   %p.2.lcssa = phi i32 [ %p.2, %header.2 ]
   br label %header.1
+}
+
+define i8 @test_pr52023(i1 %c.1, i1 %c.2) {
+; CHECK-LABEL: @test_pr52023(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_1:%.*]]
+; CHECK:       loop.1:
+; CHECK-NEXT:    [[INC79:%.*]] = phi i8 [ [[TMP0:%.*]], [[LOOP_1_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP0]] = add i8 [[INC79]], 1
+; CHECK-NEXT:    br label [[LOOP_2:%.*]]
+; CHECK:       loop.2:
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[LOOP_2_LATCH:%.*]], label [[LOOP_1_LATCH]]
+; CHECK:       loop.2.latch:
+; CHECK-NEXT:    br label [[LOOP_1_LATCH]]
+; CHECK:       loop.1.latch:
+; CHECK-NEXT:    br i1 [[C_2:%.*]], label [[EXIT:%.*]], label [[LOOP_1]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[INC_LCSSA_LCSSA:%.*]] = phi i8 [ [[TMP0]], [[LOOP_1_LATCH]] ]
+; CHECK-NEXT:    ret i8 [[INC_LCSSA_LCSSA]]
+;
+entry:
+  br label %loop.1
 
+loop.1:
+  %inc79 = phi i8 [ %inc.lcssa, %loop.1.latch ], [ 0, %entry ]
+  br label %loop.2
+
+loop.2:
+  %inc6 = phi i8 [ %inc79, %loop.1 ], [ %inc, %loop.2.latch ]
+  %inc = add i8 %inc6, 1
+  br i1 %c.1, label %loop.2.latch , label %loop.1.latch
+
+loop.2.latch:
+  br i1 false, label %loop.2, label %loop.1.latch
+
+loop.1.latch:
+  %inc.lcssa = phi i8 [ %inc, %loop.2.latch ], [ undef, %loop.2 ]
+  br i1 %c.2, label %exit, label %loop.1
+
+exit:
+  %inc.lcssa.lcssa = phi i8 [ %inc.lcssa, %loop.1.latch ]
+  ret i8 %inc.lcssa.lcssa
 }