[LoopPredication] Preserve MemorySSA

[anna]

Summary

Since LICM has now unconditionally moved to MemorySSA based form, all
passes that run in same LPM as LICM need to preserve MemorySSA (i.e. our
downstream pipeline).

Added loop-mssa to all tests and perform -verify-memoryssa within
LoopPredication itself.

[nikic]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

329

Should mark MemorySSAWrapperPass as preserved here.

827

There's another RecursivelyDeleteTriviallyDeadInstructions() use in the function below, needs to be adjusted as well?

[asbirlea]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

383

This needs to be under the conditional too:

if (AR.MSSA)
  PA.preserve<MemorySSAAnalysis>();

llvm/test/Transforms/LoopPredication/widened.ll

3

Add -verify-memoryssa .

[anna]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

383

missed it, thanks.

827

Thank you! good catch.

[anna]

addressed review comments

[nikic]

LGTM. Doesn't look like this pass is doing anything exciting with memory or control flow, so this should be sufficient...

[anna]

In D108724#2966683, @nikic wrote:

LGTM. Doesn't look like this pass is doing anything exciting with memory or control flow, so this should be sufficient...

Nothing w.r.t. memory. And control flow - we "widen" an existing check across iterations of a loop. We don't have any DT updates, so I reached the conclusion that there's no MSSA updates needed either.

llvm/lib/Transforms/Scalar/LoopPredication.cpp

 
 #include "llvm/Transforms/Scalar/LoopPredication.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"

 };
 
 class LoopPredication {
   AliasAnalysis *AA;
   DominatorTree *DT;
   ScalarEvolution *SE;
   LoopInfo *LI;
   BranchProbabilityInfo *BPI;
+  MemorySSAUpdater *MSSAU;
 
   Loop *L;
   const DataLayout *DL;
   BasicBlock *Preheader;
   LoopICmp LatchCheck;
 
   bool isSupportedStep(const SCEV* Step);
   Optional<LoopICmp> parseLoopICmp(ICmpInst *ICI);
class LoopPredication {
   // predicate based on the latch check. For example, the latch check can be a
   // very coarse grained check and there can be more fine grained exit checks
   // within the loop. We identify such unprofitable loops through BPI.
   bool isLoopProfitableToPredicate();
 
   bool predicateLoopExits(Loop *L, SCEVExpander &Rewriter);
 
 public:
-  LoopPredication(AliasAnalysis *AA, DominatorTree *DT,
-                  ScalarEvolution *SE, LoopInfo *LI,
-                  BranchProbabilityInfo *BPI)
-    : AA(AA), DT(DT), SE(SE), LI(LI), BPI(BPI) {};
+  LoopPredication(AliasAnalysis *AA, DominatorTree *DT, ScalarEvolution *SE,
+                  LoopInfo *LI, BranchProbabilityInfo *BPI,
+                  MemorySSAUpdater *MSSAU)
+      : AA(AA), DT(DT), SE(SE), LI(LI), BPI(BPI), MSSAU(MSSAU){};
   bool runOnLoop(Loop *L);
 };
 
 class LoopPredicationLegacyPass : public LoopPass {
 public:
   static char ID;
   LoopPredicationLegacyPass() : LoopPass(ID) {
     initializeLoopPredicationLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<BranchProbabilityInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
+    AU.addPreserved<MemorySSAWrapperPass>();
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    auto *MSSAWP = getAnalysisIfAvailable<MemorySSAWrapperPass>();
+    std::unique_ptr<MemorySSAUpdater> MSSAU;
+    if (MSSAWP)
+      MSSAU = std::make_unique<MemorySSAUpdater>(&MSSAWP->getMSSA());
     BranchProbabilityInfo &BPI =
         getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
     auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
-    LoopPredication LP(AA, DT, SE, LI, &BPI);
+    LoopPredication LP(AA, DT, SE, LI, &BPI, MSSAU ? MSSAU.get() : nullptr);
     return LP.runOnLoop(L);
   }
 };
 
 char LoopPredicationLegacyPass::ID = 0;
 } // end namespace
 
 INITIALIZE_PASS_BEGIN(LoopPredicationLegacyPass, "loop-predication",

 PreservedAnalyses LoopPredicationPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &U) {
   Function *F = L.getHeader()->getParent();
   // For the new PM, we also can't use BranchProbabilityInfo as an analysis
   // pass. Function analyses need to be preserved across loop transformations
   // but BPI is not preserved, hence a newly built one is needed.
   BranchProbabilityInfo BPI(*F, AR.LI, &AR.TLI, &AR.DT, nullptr);
-  LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI, &BPI);
+  std::unique_ptr<MemorySSAUpdater> MSSAU;
+  if (AR.MSSA)
+    MSSAU = std::make_unique<MemorySSAUpdater>(AR.MSSA);
+  LoopPredication LP(&AR.AA, &AR.DT, &AR.SE, &AR.LI, &BPI,
+                     MSSAU ? MSSAU.get() : nullptr);
   if (!LP.runOnLoop(&L))
     return PreservedAnalyses::all();
 
-  return getLoopPassPreservedAnalyses();
+  auto PA = getLoopPassPreservedAnalyses();
+  if (AR.MSSA)
+    PA.preserve<MemorySSAAnalysis>();
+  return PA;
 }
 
 Optional<LoopICmp>
 LoopPredication::parseLoopICmp(ICmpInst *ICI) {
   auto Pred = ICI->getPredicate();
   auto *LHS = ICI->getOperand(0);
   auto *RHS = ICI->getOperand(1);
 
bool LoopPredication::widenGuardConditions(IntrinsicInst *Guard,
 
   TotalWidened += NumWidened;
 
   // Emit the new guard condition
   IRBuilder<> Builder(findInsertPt(Guard, Checks));
   Value *AllChecks = Builder.CreateAnd(Checks);
   auto *OldCond = Guard->getOperand(0);
   Guard->setOperand(0, AllChecks);
-  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+  RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
 
   LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
   return true;
 }
 
 bool LoopPredication::widenWidenableBranchGuardConditions(
     BranchInst *BI, SCEVExpander &Expander) {
   assert(isGuardAsWidenableBranch(BI) && "Must be!");
bool LoopPredication::widenWidenableBranchGuardConditions(
 
   TotalWidened += NumWidened;
 
   // Emit the new guard condition
   IRBuilder<> Builder(findInsertPt(BI, Checks));
   Value *AllChecks = Builder.CreateAnd(Checks);
   auto *OldCond = BI->getCondition();
   BI->setCondition(AllChecks);
-  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
+  RecursivelyDeleteTriviallyDeadInstructions(OldCond, nullptr /* TLI */, MSSAU);
   assert(isGuardAsWidenableBranch(BI) &&
          "Stopped being a guard after transform?");
 
   LLVM_DEBUG(dbgs() << "Widened checks = " << NumWidened << "\n");
   return true;
 }
 
 Optional<LoopICmp> LoopPredication::parseLoopLatchICmp() {
bool LoopPredication::runOnLoop(Loop *Loop) {
 
   SCEVExpander Expander(*SE, *DL, "loop-predication");
   bool Changed = false;
   for (auto *Guard : Guards)
     Changed |= widenGuardConditions(Guard, Expander);
   for (auto *Guard : GuardsAsWidenableBranches)
     Changed |= widenWidenableBranchGuardConditions(Guard, Expander);
   Changed |= predicateLoopExits(L, Expander);
+
+  if (MSSAU && VerifyMemorySSA)
+    MSSAU->getMemorySSA()->verifyMemorySSA();
   return Changed;
 }

llvm/test/Transforms/LoopPredication/basic.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,loop(loop-predication)' < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define i32 @unsigned_loop_0_to_n_ult_check(i32* %array, i32 %length, i32 %n) {
 ; CHECK-LABEL: @unsigned_loop_0_to_n_ult_check(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]

llvm/test/Transforms/LoopPredication/basic_widenable_branch_guards.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication -loop-predication-predicate-widenable-branches-to-deopt=true < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,loop(loop-predication)' -loop-predication-predicate-widenable-branches-to-deopt=true < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,require<branch-prob>,loop(loop-predication)' -loop-predication-predicate-widenable-branches-to-deopt=true < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)'  -verify-memoryssa -loop-predication-predicate-widenable-branches-to-deopt=true < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,require<branch-prob>,loop-mssa(loop-predication)' -verify-memoryssa -loop-predication-predicate-widenable-branches-to-deopt=true < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define i32 @unsigned_loop_0_to_n_ult_check(i32* %array, i32 %length, i32 %n) {
 ; CHECK-LABEL: @unsigned_loop_0_to_n_ult_check(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]

llvm/test/Transforms/LoopPredication/invariant_load.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -basic-aa -loop-predication < %s 2>&1 | FileCheck %s
-; RUN: opt -S -aa-pipeline=basic-aa -passes='require<aa>,require<scalar-evolution>,loop(loop-predication)' < %s 2>&1 | FileCheck %s
+; RUN: opt -S -aa-pipeline=basic-aa -passes='require<aa>,require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 @UNKNOWN = external global i1
 
 define i32 @neg_length_variant(i32* %array, i32* %length, i32 %n) {
 ; CHECK-LABEL: @neg_length_variant(
 ; CHECK-NEXT:  entry:

llvm/test/Transforms/LoopPredication/nested.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,loop(loop-predication)' < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define i32 @signed_loop_0_to_n_nested_0_to_l_inner_index_check(i32* %array, i32 %length, i32 %n, i32 %l) {
 ; CHECK-LABEL: @signed_loop_0_to_n_nested_0_to_l_inner_index_check(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp sle i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[OUTER_LOOP_PREHEADER:%.*]]

llvm/test/Transforms/LoopPredication/predicate-exits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -loop-predication -S | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 declare void @prevent_merging()
 
 ; Base case - with side effects in loop
 define i32 @test1(i32* %array, i32 %length, i32 %n, i1 %cond_0) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()

llvm/test/Transforms/LoopPredication/profitability.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication -loop-predication-skip-profitability-checks=false < %s 2>&1 | FileCheck %s
-; RUN: opt -S -loop-predication-skip-profitability-checks=false -passes='require<scalar-evolution>,require<branch-prob>,loop(loop-predication)' < %s 2>&1 | FileCheck %s
+; RUN: opt -S -loop-predication-skip-profitability-checks=false -passes='require<scalar-evolution>,require<branch-prob>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 ; latch block exits to a speculation block. BPI already knows (without prof
 ; data) that deopt is very rarely
 ; taken. So we do not predicate this loop using that coarse latch check.
 ; LatchExitProbability: 0x04000000 / 0x80000000 = 3.12%
 ; ExitingBlockProbability: 0x7ffa572a / 0x80000000 = 99.98%
 define i64 @donot_predicate(i64* nocapture readonly %arg, i32 %length, i64* nocapture readonly %arg2, i64* nocapture readonly %n_addr, i64 %i) {
 ; CHECK-LABEL: @donot_predicate(

llvm/test/Transforms/LoopPredication/reverse.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication -loop-predication-enable-count-down-loop=true < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,loop(loop-predication)' -loop-predication-enable-count-down-loop=true < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -loop-predication-enable-count-down-loop=true < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define i32 @signed_reverse_loop_n_to_lower_limit(i32* %array, i32 %length, i32 %n, i32 %lowerlimit) {
 ; CHECK-LABEL: @signed_reverse_loop_n_to_lower_limit(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]

llvm/test/Transforms/LoopPredication/unswitch-exit-loop.ll

 ; RUN: opt < %s -loop-predication -S | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 ;; This is a simplified copy of @unswitch_exit_form test that should trigger loop-predication
 ;; activity and properly bail out when discovering that widenable check does not lead to deopt.
 ;;
 ;; Error checking is rather silly here - it should pass compilation successfully,
 ;; in bad case it will just timeout.
 ;;
 define i32 @unswitch_exit_form_with_endless_loop(i32* %array, i32 %length, i32 %n, i1 %cond_0) {

llvm/test/Transforms/LoopPredication/visited.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication < %s 2>&1 | FileCheck %s
-; RUN: opt -S -passes='require<scalar-evolution>,loop(loop-predication)' < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 
 declare void @llvm.experimental.guard(i1, ...)
 
 define i32 @test_visited(i32* %array, i32 %length, i32 %n, i32 %x) {
 ; CHECK-LABEL: @test_visited(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i32 [[N:%.*]], 0
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[LOOP_PREHEADER:%.*]]

llvm/test/Transforms/LoopPredication/widened.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-predication -loop-predication-enable-iv-truncation=true < %s 2>&1 | FileCheck %s
+; RUN: opt -S -passes='require<scalar-evolution>,loop-mssa(loop-predication)' -verify-memoryssa < %s 2>&1 | FileCheck %s
 declare void @llvm.experimental.guard(i1, ...)
 
 declare i32 @length(i8*)
 
 declare i16 @short_length(i8*)
 ; Consider range check of type i16 and i32, while IV is of type i64
 ; We can loop predicate this because the IV range is within i16 and within i32.
 define i64 @iv_wider_type_rc_two_narrow_types(i32 %offA, i16 %offB, i8* %arrA, i8* %arrB) {