[LoopInstSimplify] Discard SCEV if simplification happened.

[lebedev.ri]

Summary

Fixes PR37936.

The problem is as follows:

1. indvars marks %dec as NUW.
2. loop-instsimplify runs instsimplify, which constant-folds %dec to -1 (D47908)
3. loop-reduce tries to do some further modification, but crashes with an type assertion in cast, because %dec is no longer an Instruction,

If the runline is split into two, i.e. you first run -indvars -loop-instsimplify,
store that into a file, and then run -loop-reduce, there is no crash.

So it looks like the problem is due to -loop-instsimplify not discarding SCEV.
This does fix the crash (without the patch, that test file crashes),
although i do not know whether there is some other problem that should be solved.

[sanjoy]

IMO this doesn't seem like an invalidation bug -- SCEV Expander needs to be smarter about dealing with these kinds of simplifications.

[lebedev.ri]

In D48597#1143645, @sanjoy wrote:

IMO this doesn't seem like an invalidation bug -- SCEV Expander needs to be smarter about dealing with these kinds of simplifications.

Does this sound better?

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index f2ce0f4aa86..2058e591a77 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1169,8 +1169,10 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
           continue;
 
-      Instruction *TempIncV =
-          cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
+      Value* IncomingValue = PN.getIncomingValueForBlock(LatchBlock);
+      if(!isa<Instruction>(IncomingValue))
+        continue;
+      Instruction *TempIncV = cast<Instruction>(IncomingValue);
 
       // Check whether we can reuse this PHI node.
       if (LSRMode) {

[sanjoy]

In D48597#1143657, @lebedev.ri wrote:

In D48597#1143645, @sanjoy wrote:

IMO this doesn't seem like an invalidation bug -- SCEV Expander needs to be smarter about dealing with these kinds of simplifications.

Does this sound better?

Yes -- that seems better to me.

diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp
index f2ce0f4aa86..2058e591a77 100644
--- a/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1169,8 +1169,10 @@ SCEVExpander::getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized,
       if (!IsMatchingSCEV && !TryNonMatchingSCEV)
           continue;
 
-      Instruction *TempIncV =
-          cast<Instruction>(PN.getIncomingValueForBlock(LatchBlock));
+      Value* IncomingValue = PN.getIncomingValueForBlock(LatchBlock);
+      if(!isa<Instruction>(IncomingValue))
+        continue;
+      Instruction *TempIncV = cast<Instruction>(IncomingValue);
 
       // Check whether we can reuse this PHI node.
       if (LSRMode) {

[lebedev.ri]

In D48597#1143719, @sanjoy wrote:

In D48597#1143657, @lebedev.ri wrote:

In D48597#1143645, @sanjoy wrote:

IMO this doesn't seem like an invalidation bug -- SCEV Expander needs to be smarter about dealing with these kinds of simplifications.

Does this sound better?

Yes -- that seems better to me.

Superseded by https://reviews.llvm.org/D48599
Although that is a less general fix, so there may be other problems.

[uabelho]

This change indeed makes the crash go away but I have no idea if this is the right solution or if https://reviews.llvm.org/D48599 is better.

lib/Transforms/Scalar/LoopInstSimplify.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/User.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include <algorithm>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-instsimplify"
 
 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
 
 static bool simplifyLoopInst(Loop &L, DominatorTree &DT, LoopInfo &LI,
-                             AssumptionCache &AC,
-                             const TargetLibraryInfo &TLI) {
+                             AssumptionCache &AC, const TargetLibraryInfo &TLI,
+                             ScalarEvolution *SE) {
   const DataLayout &DL = L.getHeader()->getModule()->getDataLayout();
   SimplifyQuery SQ(DL, &TLI, &DT, &AC);
 
   // On the first pass over the loop body we try to simplify every instruction.
   // On subsequent passes, we can restrict this to only simplifying instructions
   // where the inputs have been updated. We end up needing two sets: one
   // containing the instructions we are simplifying in *this* pass, and one for
   // the instructions we will want to simplify in the *next* pass. We use
for (;;) {
     // Otherwise, put the next set in place for the next iteration and reset it
     // and the visited PHIs for that iteration.
     std::swap(Next, ToSimplify);
     Next->clear();
     VisitedPHIs.clear();
     DeadInsts.clear();
   }
 
+  // If ScalarEvolution is around and knows anything about values in this loop,
+  // tell it to forget them, because we simplifed the in-loop instructions.
+  if (SE && Changed)
+    SE->forgetLoop(&L);
+
   return Changed;
 }
 
 namespace {
 
 class LoopInstSimplifyLegacyPass : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
 
   LoopInstSimplifyLegacyPass() : LoopPass(ID) {
     initializeLoopInstSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     AssumptionCache &AC =
         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
             *L->getHeader()->getParent());
     const TargetLibraryInfo &TLI =
         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
+    auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
+    ScalarEvolution *SE = SEWP ? &SEWP->getSE() : nullptr;
 
-    return simplifyLoopInst(*L, DT, LI, AC, TLI);
+    return simplifyLoopInst(*L, DT, LI, AC, TLI, SE);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addPreserved<ScalarEvolutionWrapperPass>();
     AU.setPreservesCFG();
     getLoopAnalysisUsage(AU);
   }
 };
 
 } // end anonymous namespace
 
 PreservedAnalyses LoopInstSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
                                             LoopStandardAnalysisResults &AR,
                                             LPMUpdater &) {
-  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI))
+  const auto &FAM =
+      AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
+  Function *F = L.getHeader()->getParent();
+  ScalarEvolution *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
+  if (!simplifyLoopInst(L, AR.DT, AR.LI, AR.AC, AR.TLI, SE))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
   PA.preserveSet<CFGAnalyses>();
+  PA.preserve<ScalarEvolutionAnalysis>();
   return PA;
 }
 
 char LoopInstSimplifyLegacyPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                       "Simplify instructions in loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(LoopInstSimplifyLegacyPass, "loop-instsimplify",
                     "Simplify instructions in loops", false, false)
 
 Pass *llvm::createLoopInstSimplifyPass() {
   return new LoopInstSimplifyLegacyPass();
 }

test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Starting Loop pass manager run.
 ; CHECK-O-NEXT: Running pass: LoopInstSimplifyPass
+; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}>
 ; CHECK-O-NEXT: Running pass: LoopSimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: LoopRotatePass
 ; CHECK-O-NEXT: Running pass: LICM
-; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy
 ; CHECK-O-NEXT: Running pass: SimpleLoopUnswitchPass
 ; CHECK-O-NEXT: Finished Loop pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopStandardAnalysisResults{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass

test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running analysis: LoopAnalysis
 ; CHECK-O-NEXT: Running pass: LCSSAPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run
 ; CHECK-O-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Starting Loop pass manager run.
 ; CHECK-O-NEXT: Running pass: LoopInstSimplifyPass
+; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}FunctionAnalysisManager{{.*}}>
 ; CHECK-O-NEXT: Running pass: LoopSimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: LoopRotatePass
 ; CHECK-O-NEXT: Running pass: LICM
-; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy
 ; CHECK-O-NEXT: Running pass: SimpleLoopUnswitchPass
 ; CHECK-O-NEXT: Finished Loop pass manager run.
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running pass: FunctionToLoopPassAdaptor<{{.*}}LoopStandardAnalysisResults{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run
 ; CHECK-O-NEXT: Running pass: LoopSimplifyPass
 ; CHECK-O-NEXT: Running pass: LCSSAPass

test/Transforms/LoopInstSimplify/forget-scev.ll

+; RUN: opt %s -indvars -loop-instsimplify -loop-reduce
+; We are only checking that there is no crash!
+
+; https://bugs.llvm.org/show_bug.cgi?id=37936
+
+; The problem is as follows:
+; 1. indvars marks %dec as NUW.
+; 2. loop-instsimplify runs instsimplify, which constant-folds %dec to -1
+; 3. loop-reduce tries to do some further modification, but crashes
+;    with an type assertion in cast, because %dec is no longer an Instruction,
+;    even though the SCEV data indicated it was.
+
+; If the runline is split into two, i.e. -indvars -loop-instsimplify first, that
+; stored into a file, and then -loop-reduce is run on that, there is no crash.
+; So it looks like the problem is due to -loop-instsimplify not discarding SCEV.
+
+target datalayout = "n16"
+
+@a = external global i16, align 1
+
+define void @f1() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %land.end, %entry
+  %c.0 = phi i16 [ 0, %entry ], [ %dec, %land.end ]
+  br i1 undef, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond
+  ret void
+
+for.body:                                         ; preds = %for.cond
+  %0 = load i16, i16* @a, align 1
+  %cmp = icmp sgt i16 %0, %c.0
+  br i1 %cmp, label %land.rhs, label %land.end
+
+land.rhs:                                         ; preds = %for.body
+  unreachable
+
+land.end:                                         ; preds = %for.body
+  %dec = add nsw i16 %c.0, -1
+  br label %for.cond
+}