[SCEVExpander] Add helper to clean up instrs inserted while expanding.

[fhahn]

Summary

SCEVExpander already tracks which instructions have been inserted n
InsertedValues/InsertedPostIncValues. This patch adds an additional
vector to collect the instructions in insertion order. This can then be
used to remove exactly the instructions inserted by the expander.

This replaces ExpandedValuesCleaner, which in some cases might remove
values not inserted by the expander (e.g. if a value was dead before
insertion and is then used during expansion).

[lebedev.ri]

This looks about right to me. Some thoughts.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

67

Should this also be AssertingVH, just to be extra safe?

489

This doesn't read as a setter to me i'm afraid.
Maybe either keep commit(), or at least markResultAsUsed(), or something.

[jroelofs]

Good call. This is definitely a better place for that to live.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1119

I think the interface between SCEVExpanderCleaner and SCEVExpander should be a subscriber/consumer model, and the cleaner should own the tracking of what gets added, rather than the expander. Then SCEVExpanderCleaner can hook into IRBuilderCallbackInserter to track these too.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1259

Where does InsertedValues differ from InsertedInstructions? Should the former be re-used with an appropriate isa<Instruction>() filter, rather than keeping two separate lists?

[fhahn]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1119

I am not sure. What would the benefit be? SCEVExpander already needs to track which values it inserted for some internal optimizations, so hooking up 2 different callbacks seems to make things more complex than they need to be. But as mentioned inline earlier, we don't really need the extra vector, we can combine the sets and sort them.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1259

The main purpose of a separate list is to keep track of the insertion order, while InsertedValues/InsertedPostIncValues are sets. We could trade the extra memory cost for extra compile-time cost, by combing the sets and sort them by. dominance when it comes to deleting.

[jroelofs]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1119

Oh, never mind. I misread the early return on line 1127 as post-dominating this insertion, and thought it needed to be cleaned up if that happened.

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1259

Ah, ok. Sounds not worth it.

[fhahn]

I explored getting rid of the InsertedInstructions vector and instead combine & sort the existing sets.

I think this is probably beneficial, as long as cleaning up remains more uncommon. The removal logic is also updated, to also work for inserted PHIs. The patch now replaces all uses of a rewritten value with undef before removing. This works fine, if all uses are part of instructions inserted by the expander (which will be removed).

I added an assertion to ensure that, which uncovered a case where the expander actually modifies uses outside of the instructions it creates. This needs to be addressed first, I put up D84399.

[lebedev.ri]

LG to me, but probably wait a bit for @jroelofs.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

185

I think it's not unreasonable to reserve the worst-case final size?

482

bool ResultUsed = false;

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2642–2643

You need to wrap this into #ifndef NDEBUG, we won't manage to optimize this out
https://godbolt.org/z/Mhq5P1

[lebedev.ri]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2642–2643

Correction: it looks slightly less ugly -RTTI -EH, but still: https://godbolt.org/z/sjr1dd

[jroelofs]

In D84327#2173284, @lebedev.ri wrote:

LG to me, but probably wait a bit for @jroelofs.

LGTM also

[fhahn]

Rebase, guard InsertedSet by ifndef NDEBUG, add messages to asserts, increase size of getAllInsertedInstrs result vector.

[rupprecht]

FYI, I reverted this in 38884641f28e373ce291dc5ea93416756216e536 due to the assertion failure being triggered. The reduction is taking longer than usual, so I wasn't able to finish it today. I should be able to have something on Monday.

It's down to a couple hundred lines of C++, but when I try to get an IR reduction (e.g. using -Xclang -disable-O0-optnone -S -emit-llvm), the crash does not reproduce. And creduce doesn't seem to know how to reduce a bunch of the stuff (heavy on the templates), so I'm paring it down manually.

The assertion failure is only with the new pass manager, btw.

[rupprecht]

Here's as far as I could get with a repro. Sorry it's weird:

$ cat /tmp/repro.cc 
template <typename bm>
class b {
 public:
  b(bm d) : bn(d) {}
  template <typename bo>
  void operator=(bo d) {
    bh(bn, d);
  }
  bm bn;
};

template <typename>
class c;

template <typename a>
class e {
 public:
  b<a> ai() { return *static_cast<a *>(this); }
  c<a> ag(long d) { return c<a>(a(), d); }
};

template <typename ax, typename bg>
void bh(ax d, bg g) {
  float *h = d.al(), *k = g.al();
  for (long f; f; ++f) h[f] = k[f];
}

class n : public e<n> {
 public:
  float *al();
};

class o : public e<c<int> > {
 public:
  float *al() { return ak; }
  o(float *d) : ak(d) {}
  float *ak;
};

template <typename aj>
class c : public o {
 public:
  c(aj d, long g) : o(d.al() + g) {}
};

n l, m;
void by() {
  for (int j = 0, i = 0;; ++j, i += j) m.ag(i).ai() = l;
}
$ clang -O1 -fexperimental-new-pass-manager -c /tmp/repro.cc -o /tmp/repro.o                                                                                                                                                                                                         
clang: /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2663: llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner(): Assertion `all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: bin/clang -O1 -fexperimental-new-pass-manager -c /tmp/repro.cc -o /tmp/repro.o
1.      <eof> parser at end of file
2.      Optimizer
 ....
#12 0x0000000008d6eac0 llvm::SCEVExpanderCleaner::~SCEVExpanderCleaner() /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2665:5
#13 0x00000000088ebc6e (anonymous namespace)::LoopIdiomRecognize::processLoopStoreOfLoopLoad(llvm::StoreInst*, llvm::SCEV const*) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:1174:1
#14 0x00000000088e9e0d (anonymous namespace)::LoopIdiomRecognize::runOnLoopBlock(llvm::BasicBlock*, llvm::SCEV const*, llvm::SmallVectorImpl<llvm::BasicBlock*>&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:589:19
#15 0x00000000088e99f1 (anonymous namespace)::LoopIdiomRecognize::runOnCountableLoop() /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:366:19
#16 0x00000000088e91ce (anonymous namespace)::LoopIdiomRecognize::runOnLoop(llvm::Loop*) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:326:7
#17 0x00000000088e8e26 llvm::LoopIdiomRecognizePass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp:274:7
#18 0x000000000a70b885 llvm::detail::PassModel<llvm::Loop, llvm::LoopIdiomRecognizePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#19 0x000000000a892f8c llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/Scalar/LoopPassManager.cpp:45:14
#20 0x000000000a70d83a llvm::FunctionToLoopPassAdaptor<llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h:335:16
#21 0x000000000a70d445 llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor<llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#22 0x000000000814afc0 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#23 0x000000000a719ff8 llvm::CGSCCToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:508:16
#24 0x000000000a719d05 llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#25 0x0000000008209465 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp:84:14
#26 0x0000000008364046 llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> >::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:641:11
#27 0x0000000008363787 llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/Analysis/CGSCCPassManager.h:902:20
#28 0x0000000008362ed5 llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor<llvm::DevirtSCCRepeatedPass<llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#29 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#30 0x0000000008350706 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/lib/Transforms/IPO/Inliner.cpp:1072:3
#31 0x000000000a71a835 llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#32 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#33 0x000000000a7340f5 llvm::detail::PassModel<llvm::Module, llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:85:17
#34 0x0000000008149d9d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /home/rupprecht/src/llvm-project/llvm/include/llvm/IR/PassManager.h:517:16
#35 0x0000000009015591 (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1460:5
#36 0x00000000090122e5 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1685:5
#37 0x0000000009cb0155 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /home/rupprecht/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:335:7
#38 0x000000000c2b1658 clang::ParseAST(clang::Sema&, bool, bool) /home/rupprecht/src/llvm-project/clang/lib/Parse/ParseAST.cpp:178:12
#39 0x0000000009add31d clang::ASTFrontendAction::ExecuteAction() /home/rupprecht/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1059:1
#40 0x0000000009cac47f clang::CodeGenAction::ExecuteAction() /home/rupprecht/src/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:1183:1
#41 0x0000000009adcce8 clang::FrontendAction::Execute() /home/rupprecht/src/llvm-project/clang/lib/Frontend/FrontendAction.cpp:954:7
#42 0x0000000009a0b5fc clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/rupprecht/src/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:984:23
#43 0x0000000009c981ed clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/rupprecht/src/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278:8
#44 0x0000000005ae603c cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /home/rupprecht/src/llvm-project/clang/tools/driver/cc1_main.cpp:240:13
...

[fhahn]

Thanks for the reproducer! Looking into what is going wrong now.

[fhahn]

I recommitted the change in 8eded24bf46c05ffd110d521f58320cdee93866e with a fix for the issue reported by @rupprecht, which was caused due to the expander also adding existing, re-used values to InsertedValues, which we should not try to remove.

[rupprecht]

In D84327#2230474, @fhahn wrote:

I recommitted the change in 8eded24bf46c05ffd110d521f58320cdee93866e with a fix for the issue reported by @rupprecht, which was caused due to the expander also adding existing, re-used values to InsertedValues, which we should not try to remove.

I can confirm the recommit looks good, thanks!

I forgot to mention we actually saw this as a miscompile when building w/ a release build of clang; the assertion caught the underlying issue. Both the miscompile (with the release build) and the assertion (with the debug build) are gone now.

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

class SCEVExpander : public SCEVVisitor<SCEVExpander, Value *> {
   DenseMap<std::pair<const SCEV *, Instruction *>, TrackingVH<Value>>
       InsertedExpressions;
 
   // InsertedValues only flags inserted instructions so needs no RAUW.
   DenseSet<AssertingVH<Value>> InsertedValues;
   DenseSet<AssertingVH<Value>> InsertedPostIncValues;
 
   /// A memoization of the "relevant" loop for a given SCEV.
   DenseMap<const SCEV *, const Loop *> RelevantLoops;
 
   /// Addrecs referring to any of the given loops are expanded in post-inc
   /// mode. For example, expanding {1,+,1}<L> in post-inc mode returns the add
   /// instruction that adds one to the phi for {0,+,1}<L>, as opposed to a new
   /// phi starting at 1. This is only supported in non-canonical mode.
   PostIncLoopSet PostIncLoops;
 
   /// When this is non-null, addrecs expanded in the loop it indicates should
#endif
   /// places within the same BasicBlock can do so.
   void clear() {
     InsertedExpressions.clear();
     InsertedValues.clear();
     InsertedPostIncValues.clear();
     ChainedPhis.clear();
   }
 
+  /// Return a vector containing all instructions inserted during expansion.
+  SmallVector<Instruction *, 32> getAllInsertedInstructions() const {
+    SmallVector<Instruction *, 32> Result;
+    for (auto &VH : InsertedValues) {
+      Value *V = VH;
+      if (auto *Inst = dyn_cast<Instruction>(V))
+        Result.push_back(Inst);
+    }
+    for (auto &VH : InsertedPostIncValues) {
+      Value *V = VH;
+      if (auto *Inst = dyn_cast<Instruction>(V))
+        Result.push_back(Inst);
+    }
+
+    return Result;
+  }
+
   /// Return true for expressions that can't be evaluated at runtime
   /// within given \b Budget.
   ///
   /// At is a parameter which specifies point in code where user is going to
   /// expand this expression. Sometimes this knowledge can lead to
   /// a less pessimistic cost estimation.
   bool isHighCostExpansion(const SCEV *Expr, Loop *L, unsigned Budget,
                            const TargetTransformInfo *TTI,
private:
 
   void fixupInsertPoints(Instruction *I);
 
   /// If required, create LCSSA PHIs for \p Users' operand \p OpIdx. If new
   /// LCSSA PHIs have been created, return the LCSSA PHI available at \p User.
   /// If no PHIs have been created, return the unchanged operand \p OpIdx.
   Value *fixupLCSSAFormFor(Instruction *User, unsigned OpIdx);
 };
+
+/// Helper to remove instructions inserted during SCEV expansion, unless they
+/// are marked as used.
+class SCEVExpanderCleaner {
+  SCEVExpander &Expander;
+
+  DominatorTree &DT;
+
+  /// Indicates whether the result of the expansion is used. If false, the
+  /// instructions added during expansion are removed.
+  bool ResultUsed;
+
+public:
+  SCEVExpanderCleaner(SCEVExpander &Expander, DominatorTree &DT)
+      : Expander(Expander), DT(DT), ResultUsed(false) {}
+
+  ~SCEVExpanderCleaner();
+
+  /// Indicate that the result of the expansion is used.
+  void markResultUsed() { ResultUsed = true; }
+};
 } // namespace llvm
 
 #endif

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 
 Pass *llvm::createLoopIdiomPass() { return new LoopIdiomRecognizeLegacyPass(); }
 
 static void deleteDeadInstruction(Instruction *I) {
   I->replaceAllUsesWith(UndefValue::get(I->getType()));
   I->eraseFromParent();
 }
 
-namespace {
-class ExpandedValuesCleaner {
-  SCEVExpander &Expander;
-  TargetLibraryInfo *TLI;
-  SmallVector<Value *, 4> ExpandedValues;
-  bool Commit = false;
-
-public:
-  ExpandedValuesCleaner(SCEVExpander &Expander, TargetLibraryInfo *TLI)
-      : Expander(Expander), TLI(TLI) {}
-
-  void add(Value *V) { ExpandedValues.push_back(V); }
-
-  void commit() { Commit = true; }
-
-  ~ExpandedValuesCleaner() {
-    if (!Commit) {
-      Expander.clear();
-      for (auto *V : ExpandedValues)
-        RecursivelyDeleteTriviallyDeadInstructions(V, TLI);
-    }
-  }
-};
-} // namespace
-
 //===----------------------------------------------------------------------===//
 //
 //          Implementation of LoopIdiomRecognize
 //
 //===----------------------------------------------------------------------===//
 
 bool LoopIdiomRecognize::runOnLoop(Loop *L) {
   CurLoop = L;
bool LoopIdiomRecognize::processLoopStridedStore(
 
   // The trip count of the loop and the base pointer of the addrec SCEV is
   // guaranteed to be loop invariant, which means that it should dominate the
   // header.  This allows us to insert code for it in the preheader.
   unsigned DestAS = DestPtr->getType()->getPointerAddressSpace();
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
   IRBuilder<> Builder(Preheader->getTerminator());
   SCEVExpander Expander(*SE, *DL, "loop-idiom");
-  ExpandedValuesCleaner EVC(Expander, TLI);
+  SCEVExpanderCleaner ExpCleaner(Expander, *DT);
 
   Type *DestInt8PtrTy = Builder.getInt8PtrTy(DestAS);
   Type *IntIdxTy = DL->getIndexType(DestPtr->getType());
 
   bool Changed = false;
   const SCEV *Start = Ev->getStart();
   // Handle negative strided loops.
   if (NegStride)
     Start = getStartForNegStride(Start, BECount, IntIdxTy, StoreSize, SE);
 
   // TODO: ideally we should still be able to generate memset if SCEV expander
   // is taught to generate the dependencies at the latest point.
   if (!isSafeToExpand(Start, *SE))
     return Changed;
 
   // Okay, we have a strided store "p[i]" of a splattable value.  We can turn
   // this into a memset in the loop preheader now if we want.  However, this
   // would be unsafe to do if there is anything else in the loop that may read
   // or write to the aliased location.  Check for any overlap by generating the
   // base pointer and checking the region.
   Value *BasePtr =
       Expander.expandCodeFor(Start, DestInt8PtrTy, Preheader->getTerminator());
-  EVC.add(BasePtr);
 
   // From here on out, conservatively report to the pass manager that we've
   // changed the IR, even if we later clean up these added instructions. There
   // may be structural differences e.g. in the order of use lists not accounted
   // for in just a textual dump of the IR. This is written as a variable, even
   // though statically all the places this dominates could be replaced with
   // 'true', with the hope that anyone trying to be clever / "more precise" with
   // the return value will read this comment, and leave them alone.
bool LoopIdiomRecognize::processLoopStridedStore(
   for (auto *I : Stores) {
     if (MSSAU)
       MSSAU->removeMemoryAccess(I, true);
     deleteDeadInstruction(I);
   }
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   ++NumMemSet;
-  EVC.commit();
+  ExpCleaner.markResultUsed();
   return true;
 }
 
 /// If the stored value is a strided load in the same loop with the same stride
 /// this may be transformable into a memcpy.  This kicks in for stuff like
 /// for (i) A[i] = B[i];
 bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
                                                     const SCEV *BECount) {
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
 
   // The trip count of the loop and the base pointer of the addrec SCEV is
   // guaranteed to be loop invariant, which means that it should dominate the
   // header.  This allows us to insert code for it in the preheader.
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
   IRBuilder<> Builder(Preheader->getTerminator());
   SCEVExpander Expander(*SE, *DL, "loop-idiom");
 
-  ExpandedValuesCleaner EVC(Expander, TLI);
+  SCEVExpanderCleaner ExpCleaner(Expander, *DT);
 
   bool Changed = false;
   const SCEV *StrStart = StoreEv->getStart();
   unsigned StrAS = SI->getPointerAddressSpace();
   Type *IntIdxTy = Builder.getIntNTy(DL->getIndexSizeInBits(StrAS));
 
   // Handle negative strided loops.
   if (NegStride)
     StrStart = getStartForNegStride(StrStart, BECount, IntIdxTy, StoreSize, SE);
 
   // Okay, we have a strided store "p[i]" of a loaded value.  We can turn
   // this into a memcpy in the loop preheader now if we want.  However, this
   // would be unsafe to do if there is anything else in the loop that may read
   // or write the memory region we're storing to.  This includes the load that
   // feeds the stores.  Check for an alias by generating the base address and
   // checking everything.
   Value *StoreBasePtr = Expander.expandCodeFor(
       StrStart, Builder.getInt8PtrTy(StrAS), Preheader->getTerminator());
-  EVC.add(StoreBasePtr);
 
   // From here on out, conservatively report to the pass manager that we've
   // changed the IR, even if we later clean up these added instructions. There
   // may be structural differences e.g. in the order of use lists not accounted
   // for in just a textual dump of the IR. This is written as a variable, even
   // though statically all the places this dominates could be replaced with
   // 'true', with the hope that anyone trying to be clever / "more precise" with
   // the return value will read this comment, and leave them alone.
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
   // Handle negative strided loops.
   if (NegStride)
     LdStart = getStartForNegStride(LdStart, BECount, IntIdxTy, StoreSize, SE);
 
   // For a memcpy, we have to make sure that the input array is not being
   // mutated by the loop.
   Value *LoadBasePtr = Expander.expandCodeFor(
       LdStart, Builder.getInt8PtrTy(LdAS), Preheader->getTerminator());
-  EVC.add(LoadBasePtr);
 
   if (mayLoopAccessLocation(LoadBasePtr, ModRefInfo::Mod, CurLoop, BECount,
                             StoreSize, *AA, Stores))
     return Changed;
 
   if (avoidLIRForMultiBlockLoop())
     return Changed;
 
   // Okay, everything is safe, we can transform this!
 
   const SCEV *NumBytesS =
       getNumBytes(BECount, IntIdxTy, StoreSize, CurLoop, DL, SE);
 
   Value *NumBytes =
       Expander.expandCodeFor(NumBytesS, IntIdxTy, Preheader->getTerminator());
-  EVC.add(NumBytes);
 
   CallInst *NewCall = nullptr;
   // Check whether to generate an unordered atomic memcpy:
   //  If the load or store are atomic, then they must necessarily be unordered
   //  by previous checks.
   if (!SI->isAtomic() && !LI->isAtomic())
     NewCall = Builder.CreateMemCpy(StoreBasePtr, SI->getAlign(), LoadBasePtr,
                                    LI->getAlign(), NumBytes);
   else {
     // We cannot allow unaligned ops for unordered load/store, so reject
     // anything where the alignment isn't at least the element size.
     const Align StoreAlign = SI->getAlign();
     const Align LoadAlign = LI->getAlign();
     if (StoreAlign < StoreSize || LoadAlign < StoreSize)
       return Changed;
bool LoopIdiomRecognize::processLoopStoreOfLoopLoad(StoreInst *SI,
   // Okay, the memcpy has been formed.  Zap the original store and anything that
   // feeds into it.
   if (MSSAU)
     MSSAU->removeMemoryAccess(SI, true);
   deleteDeadInstruction(SI);
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   ++NumMemCpy;
-  EVC.commit();
+  ExpCleaner.markResultUsed();
   return true;
 }
 
 // When compiling for codesize we avoid idiom recognition for a multi-block loop
 // unless it is a loop_memset idiom or a memset/memcpy idiom in a nested loop.
 //
 bool LoopIdiomRecognize::avoidLIRForMultiBlockLoop(bool IsMemset,
                                                    bool IsLoopMemset) {

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

if (AddRecPhiMatch) {
       // Potentially, move the increment. We have made sure in
       // isExpandedAddRecExprPHI or hoistIVInc that this is possible.
       if (L == IVIncInsertLoop)
         hoistBeforePos(&SE.DT, IncV, IVIncInsertPos, AddRecPhiMatch);
 
       // Ok, the add recurrence looks usable.
       // Remember this PHI, even in post-inc mode.
       InsertedValues.insert(AddRecPhiMatch);
       // Remember the increment.
       rememberInstruction(IncV);
       return AddRecPhiMatch;
     }
   }
 
   // Save the original insertion point so we can restore it when we're done.
   SCEVInsertPointGuard Guard(Builder, this);
 
for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());;
           // position. SCEVExpander must correct for this in all cases.
           InsertPt = &*L->getHeader()->getFirstInsertionPt();
       } else {
         // If the SCEV is computable at this level, insert it into the header
         // after the PHIs (and after any other instructions that we've inserted
         // there) so that it is guaranteed to dominate any user inside the loop.
         if (L && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L))
           InsertPt = &*L->getHeader()->getFirstInsertionPt();
+
         while (InsertPt->getIterator() != Builder.GetInsertPoint() &&
                (isInsertedInstruction(InsertPt) ||
-                isa<DbgInfoIntrinsic>(InsertPt)))
+                isa<DbgInfoIntrinsic>(InsertPt))) {
           InsertPt = &*std::next(InsertPt->getIterator());
+        }
         break;
       }
     }
   }
 
   // Check to see if we already expanded this here.
   auto I = InsertedExpressions.find(std::make_pair(S, InsertPt));
   if (I != InsertedExpressions.end())
if (InsertionPoint->getParent()->getTerminator() == InsertionPoint)
       return true;
     if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S))
       for (const Value *V : InsertionPoint->operand_values())
         if (V == U->getValue())
           return true;
   }
   return false;
 }
+
+SCEVExpanderCleaner::~SCEVExpanderCleaner() {
+  // Result is used, nothing to remove.
+  if (ResultUsed)
+    return;
+
+  auto InsertedInstructions = Expander.getAllInsertedInstructions();
+#ifndef NDEBUG
+  SmallPtrSet<Instruction *, 8> InsertedSet(InsertedInstructions.begin(),
+                                            InsertedInstructions.end());
+  (void)InsertedSet;
+#endif
+  // Remove sets with value handles.
+  Expander.clear();
+
+  // Sort so that earlier instructions do not dominate later instructions.
+  stable_sort(InsertedInstructions, [this](Instruction *A, Instruction *B) {
+    return DT.dominates(B, A);
+  });
+  // Remove all inserted instructions.
+  for (Instruction *I : InsertedInstructions) {
+
+#ifndef NDEBUG
+    assert(all_of(I->users(),
+                  [&InsertedSet](Value *U) {
+                    return InsertedSet.contains(cast<Instruction>(U));
+                  }) &&
+           "removed instruction should only be used by instructions inserted "
+           "during expansion");
+#endif
+    assert(!I->getType()->isVoidTy() &&
+           "inserted instruction should have non-void types");
+    I->replaceAllUsesWith(UndefValue::get(I->getType()));
+    I->eraseFromParent();
+  }
+}
 }