[IRCE] Create llvm::Loop instances for cloned out loops

llvm-svn: 278618

13 files changed, 61 insertions, 26 deletions

diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
index cf67c00ae9c..291d5b4b685 100644
--- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
@@ -515,6 +515,11 @@ class LoopConstrainer {
   //
   void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
 
+  // Create the appropriate loop structure needed to describe a cloned copy of
+  // `Original`.  The clone is described by `VM`.
+  Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
+                                  ValueToValueMapTy &VM);
+
   // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
   // iteration space of the rewritten loop ends at ExitLoopAt.  The start of the
   // iteration space is not changed.  `ExitLoopAt' is assumed to be slt
@@ -567,6 +572,7 @@ class LoopConstrainer {
   LLVMContext &Ctx;
   ScalarEvolution &SE;
   DominatorTree &DT;
+  LPPassManager &LPM;
 
   // Information about the original loop we started out with.
   Loop &OriginalLoop;
@@ -586,13 +592,13 @@ class LoopConstrainer {
   LoopStructure MainLoopStructure;
 
 public:
-  LoopConstrainer(Loop &L, LoopInfo &LI, const LoopStructure &LS,
-                  ScalarEvolution &SE, DominatorTree &DT,
-                  InductiveRangeCheck::Range R)
+  LoopConstrainer(Loop &L, LoopInfo &LI, LPPassManager &LPM,
+                  const LoopStructure &LS, ScalarEvolution &SE,
+                  DominatorTree &DT, InductiveRangeCheck::Range R)
       : F(*L.getHeader()->getParent()), Ctx(L.getHeader()->getContext()),
-        SE(SE), DT(DT), OriginalLoop(L), LI(LI), LatchTakenCount(nullptr),
-        OriginalPreheader(nullptr), MainLoopPreheader(nullptr), Range(R),
-        MainLoopStructure(LS) {}
+        SE(SE), DT(DT), LPM(LPM), OriginalLoop(L), LI(LI),
+        LatchTakenCount(nullptr), OriginalPreheader(nullptr),
+        MainLoopPreheader(nullptr), Range(R), MainLoopStructure(LS) {}
 
   // Entry point for the algorithm.  Returns true on success.
   bool run();
@@ -1159,6 +1165,22 @@ void LoopConstrainer::addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs) {
     ParentLoop->addBasicBlockToLoop(BB, LI);
 }
 
+Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
+                                                 ValueToValueMapTy &VM) {
+  Loop &New = LPM.addLoop(Parent);
+
+  // Add all of the blocks in Original to the new loop.
+  for (auto *BB : Original->blocks())
+    if (LI.getLoopFor(BB) == Original)
+      New.addBasicBlockToLoop(cast<BasicBlock>(VM[BB]), LI);
+
+  // Add all of the subloops to the new loop.
+  for (Loop *SubLoop : *Original)
+    createClonedLoopStructure(SubLoop, &New, VM);
+
+  return &New;
+}
+
 bool LoopConstrainer::run() {
   BasicBlock *Preheader = nullptr;
   LatchTakenCount = SE.getExitCount(&OriginalLoop, MainLoopStructure.Latch);
@@ -1280,10 +1302,23 @@ bool LoopConstrainer::run() {
       std::remove(std::begin(NewBlocks), std::end(NewBlocks), nullptr);
 
   addToParentLoopIfNeeded(makeArrayRef(std::begin(NewBlocks), NewBlocksEnd));
-  addToParentLoopIfNeeded(PreLoop.Blocks);
-  addToParentLoopIfNeeded(PostLoop.Blocks);
 
   DT.recalculate(F);
+
+  if (!PreLoop.Blocks.empty()) {
+    auto *L = createClonedLoopStructure(
+        &OriginalLoop, OriginalLoop.getParentLoop(), PreLoop.Map);
+    formLCSSARecursively(*L, DT, &LI, &SE);
+    simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
+  }
+
+  if (!PostLoop.Blocks.empty()) {
+    auto *L = createClonedLoopStructure(
+        &OriginalLoop, OriginalLoop.getParentLoop(), PostLoop.Map);
+    formLCSSARecursively(*L, DT, &LI, &SE);
+    simplifyLoop(L, &DT, &LI, &SE, nullptr, true);
+  }
+
   formLCSSARecursively(OriginalLoop, DT, &LI, &SE);
   simplifyLoop(&OriginalLoop, &DT, &LI, &SE, nullptr, true);
 
@@ -1458,8 +1493,8 @@ bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
     return false;
 
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LS,
-                     SE, DT, SafeIterRange.getValue());
+  LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), LPM,
+                     LS, SE, DT, SafeIterRange.getValue());
   bool Changed = LC.run();
 
   if (Changed) {
diff --git a/llvm/test/Transforms/IRCE/bug-loop-varying-upper-limit.ll b/llvm/test/Transforms/IRCE/bug-loop-varying-upper-limit.ll
index 4635bb4381e..c6243d3b558 100644
--- a/llvm/test/Transforms/IRCE/bug-loop-varying-upper-limit.ll
+++ b/llvm/test/Transforms/IRCE/bug-loop-varying-upper-limit.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce-print-changed-loops -S -irce -verify < %s 2>&1 | FileCheck %s
+; RUN: opt -irce-print-changed-loops -S -verify-loop-info -irce -verify < %s 2>&1 | FileCheck %s
 
 ; CHECK-NOT: constrained loop
 
diff --git a/llvm/test/Transforms/IRCE/bug-mismatched-types.ll b/llvm/test/Transforms/IRCE/bug-mismatched-types.ll
index 05f4a93f3aa..dfec6ccd53f 100644
--- a/llvm/test/Transforms/IRCE/bug-mismatched-types.ll
+++ b/llvm/test/Transforms/IRCE/bug-mismatched-types.ll
@@ -1,7 +1,7 @@
-; RUN: opt -irce -S < %s
+; RUN: opt -verify-loop-info -irce -S < %s
 
 ; These test cases don't check the correctness of the transform, but
-; that the -irce does not crash in the presence of certain things in
+; that -irce does not crash in the presence of certain things in
 ; the IR:
 
 define void @mismatched_types_1() {
diff --git a/llvm/test/Transforms/IRCE/conjunctive-checks.ll b/llvm/test/Transforms/IRCE/conjunctive-checks.ll
index be058148977..f6a909e432c 100644
--- a/llvm/test/Transforms/IRCE/conjunctive-checks.ll
+++ b/llvm/test/Transforms/IRCE/conjunctive-checks.ll
@@ -1,4 +1,4 @@
-; RUN: opt -S -irce < %s | FileCheck %s
+; RUN: opt -S -verify-loop-info -irce < %s | FileCheck %s
 
 define void @f_0(i32 *%arr, i32 *%a_len_ptr, i32 %n, i1* %cond_buf) {
 ; CHECK-LABEL: @f_0(
@@ -34,7 +34,7 @@ define void @f_0(i32 *%arr, i32 *%a_len_ptr, i32 %n, i1* %cond_buf) {
 ; CHECK: loop:
 ; CHECK:  %cond = load volatile i1, i1* %cond_buf
 ; CHECK:  %abc = and i1 %cond, true
-; CHECK:  br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit, !prof !1
+; CHECK:  br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit3, !prof !1
 
 ; CHECK: out.of.bounds.loopexit:
 ; CHECK:  br label %out.of.bounds
@@ -84,7 +84,7 @@ define void @f_1(
 
 ; CHECK: loop:
 ; CHECK:   %abc = and i1 true, true
-; CHECK:   br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit, !prof !1
+; CHECK:   br i1 %abc, label %in.bounds, label %out.of.bounds.loopexit4, !prof !1
 
 ; CHECK: out.of.bounds.loopexit:
 ; CHECK-NEXT:  br label %out.of.bounds
diff --git a/llvm/test/Transforms/IRCE/decrementing-loop.ll b/llvm/test/Transforms/IRCE/decrementing-loop.ll
index a3a03b182a5..fac873b4a24 100644
--- a/llvm/test/Transforms/IRCE/decrementing-loop.ll
+++ b/llvm/test/Transforms/IRCE/decrementing-loop.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce -S < %s | FileCheck %s
+; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
 
 define void @decrementing_loop(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
  entry:
diff --git a/llvm/test/Transforms/IRCE/low-becount.ll b/llvm/test/Transforms/IRCE/low-becount.ll
index 89b91d6496a..a4ea7ed7efb 100644
--- a/llvm/test/Transforms/IRCE/low-becount.ll
+++ b/llvm/test/Transforms/IRCE/low-becount.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -irce-print-changed-loops -verify-loop-info -irce -S < %s 2>&1 | FileCheck %s
 
 ; CHECK-NOT: constrained Loop
 
diff --git a/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll b/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll
index eedfc420bdb..31bfe7881b6 100644
--- a/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll
+++ b/llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce -S < %s | FileCheck %s
+; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
 
 define void @multiple_access_no_preloop(
     i32* %arr_a, i32* %a_len_ptr, i32* %arr_b, i32* %b_len_ptr, i32 %n) {
diff --git a/llvm/test/Transforms/IRCE/only-lower-check.ll b/llvm/test/Transforms/IRCE/only-lower-check.ll
index 428c3aabdec..114edb32984 100644
--- a/llvm/test/Transforms/IRCE/only-lower-check.ll
+++ b/llvm/test/Transforms/IRCE/only-lower-check.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce-print-range-checks -irce-print-changed-loops -irce < %s 2>&1 | FileCheck %s
+; RUN: opt -irce-print-range-checks -irce-print-changed-loops -verify-loop-info -irce < %s 2>&1 | FileCheck %s
 
 ; CHECK: irce: loop has 1 inductive range checks:
 ; CHECK-NEXT: InductiveRangeCheck:
diff --git a/llvm/test/Transforms/IRCE/only-upper-check.ll b/llvm/test/Transforms/IRCE/only-upper-check.ll
index 8e3e1ffe99b..24aaef00101 100644
--- a/llvm/test/Transforms/IRCE/only-upper-check.ll
+++ b/llvm/test/Transforms/IRCE/only-upper-check.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce -irce-print-range-checks -irce-print-changed-loops %s -S 2>&1 | FileCheck %s
+; RUN: opt -verify-loop-info -irce -irce-print-range-checks -irce-print-changed-loops %s -S 2>&1 | FileCheck %s
 
 ; CHECK: irce: loop has 1 inductive range checks:
 ; CHECK-NEXT:InductiveRangeCheck:
diff --git a/llvm/test/Transforms/IRCE/single-access-no-preloop.ll b/llvm/test/Transforms/IRCE/single-access-no-preloop.ll
index 17464f25f70..b61a1c3b0c8 100644
--- a/llvm/test/Transforms/IRCE/single-access-no-preloop.ll
+++ b/llvm/test/Transforms/IRCE/single-access-no-preloop.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce -S < %s | FileCheck %s
+; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
 
 define void @single_access_no_preloop_no_offset(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
  entry:
diff --git a/llvm/test/Transforms/IRCE/single-access-with-preloop.ll b/llvm/test/Transforms/IRCE/single-access-with-preloop.ll
index 204c24caa7e..57e828b663a 100644
--- a/llvm/test/Transforms/IRCE/single-access-with-preloop.ll
+++ b/llvm/test/Transforms/IRCE/single-access-with-preloop.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce -S < %s | FileCheck %s
+; RUN: opt -verify-loop-info -irce -S < %s | FileCheck %s
 
 define void @single_access_with_preloop(i32 *%arr, i32 *%a_len_ptr, i32 %n, i32 %offset) {
  entry:
@@ -61,7 +61,7 @@ define void @single_access_with_preloop(i32 *%arr, i32 *%a_len_ptr, i32 %n, i32
 ; CHECK: br i1 [[continue_preloop_cond]], label %loop.preloop, label %preloop.exit.selector
 
 ; CHECK: preloop.exit.selector:
-; CHECK: [[preloop_its_left:[^ ]+]] = icmp slt i32 %idx.next.preloop, %n
+; CHECK: [[preloop_its_left:[^ ]+]] = icmp slt i32 %idx.next.preloop.lcssa, %n
 ; CHECK: br i1 [[preloop_its_left]], label %preloop.pseudo.exit, label %exit.loopexit
 
 ; CHECK: in.bounds.postloop:
diff --git a/llvm/test/Transforms/IRCE/skip-profitability-checks.ll b/llvm/test/Transforms/IRCE/skip-profitability-checks.ll
index f12898955b4..f37d3e8412f 100644
--- a/llvm/test/Transforms/IRCE/skip-profitability-checks.ll
+++ b/llvm/test/Transforms/IRCE/skip-profitability-checks.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce-skip-profitability-checks -S -irce < %s | FileCheck %s
+; RUN: opt -irce-skip-profitability-checks -S -verify-loop-info -irce < %s | FileCheck %s
 
 define void @single_access_no_preloop_no_offset(i32 *%arr, i32 *%a_len_ptr, i32 %n) {
 ; CHECK-LABEL: @single_access_no_preloop_no_offset(
diff --git a/llvm/test/Transforms/IRCE/unhandled.ll b/llvm/test/Transforms/IRCE/unhandled.ll
index 9889b75bca7..4d9d4f72efa 100644
--- a/llvm/test/Transforms/IRCE/unhandled.ll
+++ b/llvm/test/Transforms/IRCE/unhandled.ll
@@ -1,4 +1,4 @@
-; RUN: opt -irce-print-changed-loops -irce -S < %s 2>&1 | FileCheck %s
+; RUN: opt -irce-print-changed-loops -verify-loop-info -irce -S < %s 2>&1 | FileCheck %s
 
 ; CHECK-NOT: constrained Loop at depth