[NaryReassociate] SeenExprs records WeakVH

[jingyue]

Summary

The instructions SeenExprs records may be deleted during rewriting.
FindClosestMatchingDominator should ignore these deleted instructions.

Fixes PR24301.

[grosser]

This fixes the memory issue for me. Thank you.

Tobias

lib/Transforms/Scalar/NaryReassociate.cpp

private:
   // Note that there can be multiple instructions at different locations
   // computing to the same SCEV, so we map a SCEV to an instruction list.  For
   // example,
   //
   //   if (p1)
   //     foo(a + b);
   //   if (p2)
   //     bar(a + b);
-  DenseMap<const SCEV *, SmallVector<Instruction *, 2>> SeenExprs;
+  DenseMap<const SCEV *, SmallVector<WeakVH, 2>> SeenExprs;
 };
 } // anonymous namespace
 
 char NaryReassociate::ID = 0;
 INITIALIZE_PASS_BEGIN(NaryReassociate, "nary-reassociate", "Nary reassociation",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
for (auto Node = GraphTraits<DominatorTree *>::nodes_begin(DT);
     BasicBlock *BB = Node->getBlock();
     for (auto I = BB->begin(); I != BB->end(); ++I) {
       if (SE->isSCEVable(I->getType()) && isPotentiallyNaryReassociable(I)) {
         const SCEV *OldSCEV = SE->getSCEV(I);
         if (Instruction *NewI = tryReassociate(I)) {
           Changed = true;
           SE->forgetValue(I);
           I->replaceAllUsesWith(NewI);
+          // If SeenExprs constains I's WeakVH, that entry will be replaced with
+          // nullptr.
           RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
           I = NewI;
         }
         // Add the rewritten instruction to SeenExprs; the original instruction
         // is deleted.
         const SCEV *NewSCEV = SE->getSCEV(I);
-        SeenExprs[NewSCEV].push_back(I);
+        SeenExprs[NewSCEV].push_back(WeakVH(I));
         // Ideally, NewSCEV should equal OldSCEV because tryReassociate(I)
         // is equivalent to I. However, ScalarEvolution::getSCEV may
         // weaken nsw causing NewSCEV not to equal OldSCEV. For example, suppose
         // we reassociate
         //   I = &a[sext(i +nsw j)] // assuming sizeof(a[0]) = 4
         // to
         //   NewI = &a[sext(i)] + sext(j).
         //
         // ScalarEvolution computes
         //   getSCEV(I)    = a + 4 * sext(i + j)
         //   getSCEV(newI) = a + 4 * sext(i) + 4 * sext(j)
         // which are different SCEVs.
         //
         // To alleviate this issue of ScalarEvolution not always capturing
         // equivalence, we add I to SeenExprs[OldSCEV] as well so that we can
         // map both SCEV before and after tryReassociate(I) to I.
         //
         // This improvement is exercised in @reassociate_gep_nsw in nary-gep.ll.
         if (NewSCEV != OldSCEV)
-          SeenExprs[OldSCEV].push_back(I);
+          SeenExprs[OldSCEV].push_back(WeakVH(I));
       }
     }
   }
   return Changed;
 }
 
 Instruction *NaryReassociate::tryReassociate(Instruction *I) {
   switch (I->getOpcode()) {
if (Pos == SeenExprs.end())
     return nullptr;
 
   auto &Candidates = Pos->second;
   // Because we process the basic blocks in pre-order of the dominator tree, a
   // candidate that doesn't dominate the current instruction won't dominate any
   // future instruction either. Therefore, we pop it out of the stack. This
   // optimization makes the algorithm O(n).
   while (!Candidates.empty()) {
-    Instruction *Candidate = Candidates.back();
-    if (DT->dominates(Candidate, Dominatee))
-      return Candidate;
+    // Candidates stores WeakVHs, so a candidate can be nullptr if it's removed
+    // during rewriting.
+    if (Value *Candidate = Candidates.back()) {
+      Instruction *CandidateInstruction = cast<Instruction>(Candidate);
+      if (DT->dominates(CandidateInstruction, Dominatee))
+        return CandidateInstruction;
+    }
     Candidates.pop_back();
   }
   return nullptr;
 }

test/Transforms/NaryReassociate/pr24301.ll

+; RUN: opt < %s -nary-reassociate -S | FileCheck %s
+
+define i32 @foo(i32 %tmp4) {
+; CHECK-LABEL: @foo(
+entry:
+  %tmp5 = add i32 %tmp4, 8
+  %tmp13 = add i32 %tmp4, -128  ; deleted
+  %tmp14 = add i32 %tmp13, 8    ; => %tmp5 + -128
+  %tmp21 = add i32 119, %tmp4
+  ; do not rewrite %tmp23 against %tmp13 because %tmp13 is already deleted
+  %tmp23 = add i32 %tmp21, -128
+; CHECK: %tmp23 = add i32 %tmp21, -128
+  ret i32 %tmp23
+}