[LoopUnroll] Forget block and loop dispositions during unrolling.

[fhahn]

Summary

After unrolling a loop, the block and loop dispositions need to be
cleared. As we don't know which SCEVs in the loop/blocks may be
impacted, completely clear the cache. This should also fix some cases
where deleted loops remained in the LoopDispositions cache.

This fixes a verification failure surfaced by D134531.

I am planning on reviewing/updating the existing uses of
forgetLoopDispositions to check if they should be replaced by
forgetBlockAndLoopDispositions.

[fhahn]

Fix formatting.

[mkazantsev]

llvm/lib/Transforms/Utils/LoopUnroll.cpp

470

Doesn't forgetAllLoops already do it? I guess this should be under else clause.

[fhahn]

Move SE->forgetBlockAndLoopDispositions() into else {} clause, thanks!

llvm/lib/Transforms/Utils/LoopUnroll.cpp

470

Done, thanks!

[nikic]

LGTM

[fhahn]

Rebase on current main.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Called when the client has changed the disposition of values in
   /// this loop.
   ///
   /// We don't have a way to invalidate per-loop dispositions. Clear and
   /// recompute is simpler.
   void forgetLoopDispositions();
 
+  /// Called when the client has changed the disposition of values in
+  /// a loop or block.
+  ///
+  /// We don't have a way to invalidate per-loop/per-block dispositions. Clear and
+  /// recompute is simpler.
+  void forgetBlockAndLoopDispositions();
+
   /// Determine the minimum number of zero bits that S is guaranteed to end in
   /// (at every loop iteration).  It is, at the same time, the minimum number
   /// of times S is divisible by 2.  For example, given {4,+,8} it returns 2.
   /// If S is guaranteed to be 0, it returns the bitwidth of S.
   uint32_t GetMinTrailingZeros(const SCEV *S);
 
   /// Determine the unsigned range for a particular SCEV.
   /// NOTE: This returns a copy of the reference returned by getRangeRef.

llvm/lib/Analysis/ScalarEvolution.cpp

while (!Worklist.empty()) {
 
     PushDefUseChildren(I, Worklist, Visited);
   }
   forgetMemoizedResults(ToForget);
 }
 
 void ScalarEvolution::forgetLoopDispositions() { LoopDispositions.clear(); }
 
+void ScalarEvolution::forgetBlockAndLoopDispositions() { BlockDispositions.clear(); LoopDispositions.clear();}
+
 /// Get the exact loop backedge taken count considering all loop exits. A
 /// computable result can only be returned for loops with all exiting blocks
 /// dominating the latch. howFarToZero assumes that the limit of each loop test
 /// is never skipped. This is a valid assumption as long as the loop exits via
 /// that test. For precise results, it is the caller's responsibility to specify
 /// the relevant loop exiting block using getExact(ExitingBlock, SE).
 const SCEV *
 ScalarEvolution::BackedgeTakenInfo::getExact(const Loop *L, ScalarEvolution *SE,

llvm/lib/Transforms/Utils/LoopUnroll.cpp

LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
   // and if something changes inside them then any of outer loops may also
   // change. When we forget outermost loop, we also forget all contained loops
   // and this is what we need here.
   if (SE) {
     if (ULO.ForgetAllSCEV)
       SE->forgetAllLoops();
     else
       SE->forgetTopmostLoop(L);
+    SE->forgetBlockAndLoopDispositions();
   }
 
   if (!LatchIsExiting)
     ++NumUnrolledNotLatch;
 
   // For the first iteration of the loop, we should use the precloned values for
   // PHI nodes.  Insert associations now.
   ValueToValueMapTy LastValueMap;

llvm/test/Transforms/LoopUnroll/loop-block-disposition-after-full-unroll.ll

-; RUN: opt -passes='loop(indvars,loop-deletion,loop-unroll-full),verify<scalar-evolution>' -S %s
-
-; XFAIL: *
-; FIXME: currently fails verification.
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes='loop(indvars,loop-deletion,loop-unroll-full),verify<scalar-evolution>' -S %s | FileCheck %s
 
 define void @test(i1 %c.0, ptr %A) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[C_0:%.*]], label [[LOOP_1_HEADER_PREHEADER:%.*]], label [[OUTER_HEADER_PREHEADER:%.*]]
+; CHECK:       outer.header.preheader:
+; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
+; CHECK:       loop.1.header.preheader:
+; CHECK-NEXT:    br label [[LOOP_1_HEADER:%.*]]
+; CHECK:       loop.1.header:
+; CHECK-NEXT:    store i32 0, ptr [[A:%.*]], align 4
+; CHECK-NEXT:    br label [[LOOP_1_LATCH:%.*]]
+; CHECK:       loop.1.latch:
+; CHECK-NEXT:    store i32 0, ptr [[A]], align 4
+; CHECK-NEXT:    br label [[LOOP_1_LATCH_1:%.*]]
+; CHECK:       loop.1.latch.1:
+; CHECK-NEXT:    ret void
+; CHECK:       outer.header.loopexit:
+; CHECK-NEXT:    br label [[OUTER_HEADER]]
+; CHECK:       outer.header:
+; CHECK-NEXT:    [[L:%.*]] = load i32, ptr [[A]], align 4
+; CHECK-NEXT:    br label [[OUTER_HEADER_LOOPEXIT:%.*]]
+;
 entry:
   br i1 %c.0, label %loop.1.header, label %outer.header
 
 loop.1.header:
   %iv.1 = phi i32 [ 0, %entry ],  [ 1, %loop.1.latch ]
   store i32 0, ptr %A, align 4
   br label %loop.1.latch