[SCEV] Do not erase LoopUsers. PR53969

[mkazantsev]

Summary

This patch fixes a logical error in how we work with LoopUsers map.
It maps a loop onto a set of AddRecs that depend on it. The Addrecs
are added to this map only once when they are created and put to
the UniqueSCEVs` map.

The only purpose of this map is to make sure that, whenever we forget
a loop, all (directly or indirectly) dependent SCEVs get forgotten too.

Current code erases SCEVs from dependent set of a given loop whenever
we forget this loop. This is not a correct behavior due to the following scenario:

1. We have a loop L and an AddRec AR that depends on it;
2. We modify something in the loop, but don't destroy it. We still call forgetLoop on it;
3. AR is no longer dependent on L according to LoopUsers. It is erased from ValueExprMap` and `ExprValue map, but still exists in UniqueSCEVs;
4. We can later request the very same AddRec for the very same loop again, and get existing SCEV AR.
5. Now, AR exists and is used again, but its notion that it depends on L is lost;
6. Then we decide to delete L. AR will not be forgotten because we have lost it;
7. Just you wait when you run into a dangling pointer problem, or any other kind of problem because an active SCEV is now referecing a non-existent loop.

The solution to this is to stop erasing values from LoopUsers. Yes, we will maybe forget something
that is already not used, but it's cheap. The only real problem we can run into is following: if we
delete a loop, and then create a new loop by the same address, this may cause cache confusion.
However, this still should be safe because the *only* purpose of LoopUsers is invalidation, and
invalidation never reads loops from AddRecs.

This fixes a functional bug and potentially may have negative compile time impact on methods with
huge or numerous loops.

[nikic]

LGTM. It's a bit unfortunate that we conflate the notion of "forget this loop because we're about to delete it" and "forget this loop because we made a significant change to it", but as things are right now, I agree that dropping from LoopUsers is not correct here.

The only real problem we can run into is following: if we
delete a loop, and then create a new loop by the same address, this may cause cache confusion.
However, this still should be safe because the *only* purpose of LoopUsers is invalidation, and
invalidation never reads loops from AddRecs.

This can't happen, because Loop addresses are not reused.

[mkazantsev]

JFYI: I ran it through 4k fuzzed Java tests and it didn't fail, so it should be ok.

llvm/lib/Analysis/ScalarEvolution.cpp

for (auto I = PredicatedSCEVRewrites.begin();
       else
         ++I;
     }
 
     auto LoopUsersItr = LoopUsers.find(CurrL);
     if (LoopUsersItr != LoopUsers.end()) {
       ToForget.insert(ToForget.end(), LoopUsersItr->second.begin(),
                 LoopUsersItr->second.end());
-      LoopUsers.erase(LoopUsersItr);
     }
 
     // Drop information about expressions based on loop-header PHIs.
     PushLoopPHIs(CurrL, Worklist, Visited);
 
     while (!Worklist.empty()) {
       Instruction *I = Worklist.pop_back_val();
 

llvm/test/Transforms/LoopDeletion/pr53969.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes="loop(indvars,loop-deletion)" -S  < %s | FileCheck %s
-; XFAIL: *
-; REQUIRES: asserts
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Make sure we don't crash.
 define void @test() {
-; CHECK-LABEL: test
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i32 [ 11, [[BB:%.*]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = add nsw i32 112, -1
+; CHECK-NEXT:    [[TMP4:%.*]] = add nuw nsw i32 [[TMP2]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = mul i32 [[TMP3]], [[TMP3]]
+; CHECK-NEXT:    [[TMP6:%.*]] = mul nsw i32 [[TMP2]], -6
+; CHECK-NEXT:    [[TMP7:%.*]] = mul nsw i32 [[TMP6]], [[TMP5]]
+; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i32 [[TMP7]], [[TMP2]]
+; CHECK-NEXT:    [[TMP9:%.*]] = and i32 undef, 1
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[TMP9]], 0
+; CHECK-NEXT:    br i1 [[TMP10]], label [[BB33_LOOPEXIT1:%.*]], label [[BB34_PREHEADER:%.*]]
+; CHECK:       bb34.preheader:
+; CHECK-NEXT:    br label [[BB34:%.*]]
+; CHECK:       bb11:
+; CHECK-NEXT:    [[TMP2_LCSSA12:%.*]] = phi i32 [ 11, [[BB34]] ]
+; CHECK-NEXT:    br label [[BB33_LOOPEXIT:%.*]]
+; CHECK:       bb12:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[TMP40:%.*]], 0
+; CHECK-NEXT:    br label [[BB14:%.*]]
+; CHECK:       bb14:
+; CHECK-NEXT:    br i1 true, label [[BB32:%.*]], label [[BB22:%.*]]
+; CHECK:       bb22:
+; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 4 to i32
+; CHECK-NEXT:    [[TMP23:%.*]] = or i32 [[TMP1]], undef
+; CHECK-NEXT:    [[TMP24:%.*]] = add i32 [[TMP23]], undef
+; CHECK-NEXT:    br i1 false, label [[BB42:%.*]], label [[BB25:%.*]]
+; CHECK:       bb25:
+; CHECK-NEXT:    br label [[BB31:%.*]]
+; CHECK:       bb31:
+; CHECK-NEXT:    unreachable
+; CHECK:       bb32:
+; CHECK-NEXT:    ret void
+; CHECK:       bb33.loopexit:
+; CHECK-NEXT:    [[TMP2_LCSSA9:%.*]] = phi i32 [ [[TMP2_LCSSA12]], [[BB11:%.*]] ]
+; CHECK-NEXT:    br label [[BB33:%.*]]
+; CHECK:       bb33.loopexit1:
+; CHECK-NEXT:    [[TMP2_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[BB1]] ]
+; CHECK-NEXT:    br label [[BB33]]
+; CHECK:       bb33:
+; CHECK-NEXT:    [[TMP210:%.*]] = phi i32 [ [[TMP2_LCSSA]], [[BB33_LOOPEXIT1]] ], [ [[TMP2_LCSSA9]], [[BB33_LOOPEXIT]] ]
+; CHECK-NEXT:    call void @use(i32 [[TMP210]])
+; CHECK-NEXT:    ret void
+; CHECK:       bb34:
+; CHECK-NEXT:    [[TMP36:%.*]] = xor i32 0, [[TMP8]]
+; CHECK-NEXT:    [[TMP38:%.*]] = add i32 [[TMP36]], undef
+; CHECK-NEXT:    [[TMP39:%.*]] = add i32 [[TMP38]], undef
+; CHECK-NEXT:    [[TMP40]] = sext i32 [[TMP39]] to i64
+; CHECK-NEXT:    br i1 false, label [[BB11]], label [[BB12:%.*]]
+; CHECK:       bb42:
+; CHECK-NEXT:    [[TMP24_LCSSA:%.*]] = phi i32 [ [[TMP24]], [[BB22]] ]
+; CHECK-NEXT:    [[TMP18_LCSSA4:%.*]] = phi i64 [ [[TMP0]], [[BB22]] ]
+; CHECK-NEXT:    store atomic i64 [[TMP18_LCSSA4]], i64 addrspace(1)* undef unordered, align 8
+; CHECK-NEXT:    call void @use(i32 [[TMP24_LCSSA]])
+; CHECK-NEXT:    ret void
+;
 bb:
   br label %bb1
 
 bb1:                                              ; preds = %bb31, %bb
   %tmp = phi i32 [ %tmp29, %bb31 ], [ undef, %bb ]
   %tmp2 = phi i32 [ %tmp4, %bb31 ], [ 11, %bb ]
   %tmp3 = add nsw i32 112, -1
   %tmp4 = add nuw nsw i32 %tmp2, 1