[LoopSimplifyCFG] Preserve Scalar Evolution in LoopSimplifyCFG

[dmgreen]

Summary

LoopSimplifyCFG, being a loop pass, needs to preserve scalar
evolution. This invalidates SE for the loops altered during
block merging.

Needs https://reviews.llvm.org/D48202 for the test to cause
a validation failure.

[asbirlea]

Perhaps a more accurate description is "Invalidate ScEv in LoopSimplifyCFG" (when merging blocks).
LGTM.

[dmgreen]

Thanks

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
-static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI) {
+static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
+                            ScalarEvolution &SE) {
   bool Changed = false;
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 
   for (auto &Block : Blocks) {
     // Attempt to merge blocks in the trivial case. Don't modify blocks which
     // belong to other loops.
     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
     if (!Succ)
       continue;
 
     BasicBlock *Pred = Succ->getSinglePredecessor();
     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
       continue;
 
     // Pred is going to disappear, so we need to update the loop info.
     if (L.getHeader() == Pred)
       L.moveToHeader(Succ);
     LI.removeBlock(Pred);
     MergeBasicBlockIntoOnlyPred(Succ, &DT);
+
+    SE.forgetLoop(&L);
     Changed = true;
   }
 
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &) {
-  if (!simplifyLoopCFG(L, AR.DT, AR.LI))
+  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE))
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 class LoopSimplifyCFGLegacyPass : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &) override {
     if (skipLoop(L))
       return false;
 
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    return simplifyLoopCFG(*L, DT, LI);
+    ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+    return simplifyLoopCFG(*L, DT, LI, SE);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<DependenceAnalysisWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 }

test/Transforms/LoopSimplifyCFG/scev.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -loop-simplifycfg -verify-scev < %s | FileCheck %s
+
+; Verify that the scev information is still valid. Verification should not fail
+
+define void @t_run_test() {
+; CHECK-LABEL: @t_run_test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_PH:%.*]]
+; CHECK:       loop.ph:
+; CHECK-NEXT:    br label [[LOOP_BODY:%.*]]
+; CHECK:       loop.body:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[LOOP_PH]] ], [ [[INC:%.*]], [[LOOP_BODY]] ]
+; CHECK-NEXT:    [[INC]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC]], 10
+; CHECK-NEXT:    br i1 [[CMP]], label [[LOOP_BODY]], label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    br label [[LOOP_BODY2:%.*]]
+; CHECK:       loop.body2:
+; CHECK-NEXT:    [[IV2:%.*]] = phi i32 [ 0, [[EXIT]] ], [ [[INC2:%.*]], [[LOOP_BODY2]] ]
+; CHECK-NEXT:    [[INC2]] = add i32 [[IV2]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[INC2]], 10
+; CHECK-NEXT:    br i1 [[CMP2]], label [[LOOP_BODY2]], label [[EXIT2:%.*]]
+; CHECK:       exit2:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %loop.ph
+
+loop.ph:
+  br label %loop.header
+
+loop.header:
+  %iv = phi i32 [0, %loop.ph], [%inc, %loop.body]
+  br label %loop.body1
+
+loop.body1:
+  br label %loop.body
+
+loop.body:
+  %inc = add i32 %iv, 1
+  %cmp = icmp ult i32 %inc, 10
+  br i1 %cmp, label %loop.header, label %exit
+
+exit:
+  br label %loop.body2
+
+loop.body2:
+  %iv2 = phi i32 [0, %exit], [%inc2, %loop.body2]
+  %inc2 = add i32 %iv2, 1
+  %cmp2 = icmp ult i32 %inc2, 10
+  br i1 %cmp2, label %loop.body2, label %exit2
+
+exit2:
+  ret void
+}
+