[ScopBuilder] Build invariant loads separately.

Create the MemoryAccesses of invariant loads separately and before
all other MemoryAccesses.

Invariant loads are classified as synthesizable and therefore are not
contained in any statement. When iterating over all instructions of all
statements, the invariant loads are consequently not processed and
iterating over them separately becomes necessary.

This patch can change the order in which MemoryAccesses are created, but
otherwise has no functional change.

Some temporary code is introduced to ensure correctness, but will be
removed in the next commit.

llvm-svn: 314664

5 files changed, 58 insertions, 14 deletions

diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index bbf8f582afb..d84ffa8653b 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -721,6 +721,20 @@ void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
   if (isErrorBlock(BB, scop->getRegion(), LI, DT))
     return;
 
+  auto &RIL = scop->getRequiredInvariantLoads();
+  std::function<bool(Instruction & Inst)> IsInStmtFunc =
+      [&RIL](Instruction &Inst) -> bool {
+    return !isa<LoadInst>(Inst) || !RIL.count(cast<LoadInst>(&Inst));
+  };
+  bool IsEntryBlock = (Stmt->getEntryBlock() == &BB);
+  if (IsEntryBlock) {
+    auto &Insts = Stmt->getInstructions();
+    SmallPtrSet<Instruction *, 8> InStmtInsts(Insts.begin(), Insts.end());
+    IsInStmtFunc = [InStmtInsts](const Instruction &Inst) -> bool {
+      return InStmtInsts.count(&Inst);
+    };
+  }
+
   int Count = 0;
   bool Split = false;
   for (Instruction &Inst : BB) {
@@ -738,9 +752,12 @@ void ScopBuilder::buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
     if (PHI)
       buildPHIAccesses(Stmt, PHI, NonAffineSubRegion, false);
 
-    if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
-      assert(Stmt && "Cannot build access function in non-existing statement");
-      buildMemoryAccess(MemInst, Stmt);
+    if (IsInStmtFunc(Inst)) {
+      if (auto MemInst = MemAccInst::dyn_cast(Inst)) {
+        assert(Stmt &&
+               "Cannot build access function in non-existing statement");
+        buildMemoryAccess(MemInst, Stmt);
+      }
     }
 
     if (isIgnoredIntrinsic(&Inst))
@@ -1185,6 +1202,33 @@ void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
   scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
 
   buildStmts(R);
+
+  // Create all invariant load instructions first. These are categorized as
+  // 'synthesizable', therefore are not part of any ScopStmt but need to be
+  // created somewhere.
+  const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
+  for (BasicBlock *BB : scop->getRegion().blocks()) {
+    if (isErrorBlock(*BB, scop->getRegion(), LI, DT))
+      continue;
+
+    for (Instruction &Inst : *BB) {
+      LoadInst *Load = dyn_cast<LoadInst>(&Inst);
+      if (!Load)
+        continue;
+
+      if (!RIL.count(Load))
+        continue;
+
+      // Invariant loads require a MemoryAccess to be created in some statement.
+      // It is not important to which statement the MemoryAccess is added
+      // because it will later be removed from the ScopStmt again. We chose the
+      // first statement of the basic block the LoadInst is in.
+      ArrayRef<ScopStmt *> List = scop->getStmtListFor(BB);
+      assert(!List.empty());
+      ScopStmt *RILStmt = List.front();
+      buildMemoryAccess(Load, RILStmt);
+    }
+  }
   buildAccessFunctions();
 
   // In case the region does not have an exiting block we will later (during
diff --git a/polly/test/ScopInfo/invariant_load_zext_parameter.ll b/polly/test/ScopInfo/invariant_load_zext_parameter.ll
index f2c81cec4ff..ab2507aa52b 100644
--- a/polly/test/ScopInfo/invariant_load_zext_parameter.ll
+++ b/polly/test/ScopInfo/invariant_load_zext_parameter.ll
@@ -22,7 +22,7 @@
 ; CODEGEN:      polly.preload.begin:
 ; CODEGEN-NEXT:   %polly.access.I0 = getelementptr i32, i32* %I0, i64 0
 ; CODEGEN-NEXT:   %polly.access.I0.load = load i32, i32* %polly.access.I0
-; CODEGEN-NEXT:   store i32 %polly.access.I0.load, i32* %loadI0.preload.s2a
+; CODEGEN-NEXT:   store i32 %polly.access.I0.load, i32* %loadI1a.preload.s2a
 ; CODEGEN-NEXT:   %0 = sext i32 %polly.access.I0.load to i64
 ; CODEGEN-NEXT:   %1 = icmp eq i64 %0, 0
 ; CODEGEN-NEXT:   br label %polly.preload.cond
diff --git a/polly/test/ScopInfo/multidim_2d_with_modref_call.ll b/polly/test/ScopInfo/multidim_2d_with_modref_call.ll
index 6def1371608..74cd0095251 100644
--- a/polly/test/ScopInfo/multidim_2d_with_modref_call.ll
+++ b/polly/test/ScopInfo/multidim_2d_with_modref_call.ll
@@ -78,15 +78,15 @@
 ; NONAFFINE-NEXT:    p0: %tmp9
 ; NONAFFINE-NEXT:    p1: %tmp14
 ; NONAFFINE-NEXT:    Arrays {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        double MemRef_arg4[*]; // Element size 8
 ; NONAFFINE-NEXT:    }
 ; NONAFFINE-NEXT:    Arrays (Bounds as pw_affs) {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        double MemRef_arg4[*]; // Element size 8
@@ -115,10 +115,10 @@
 ; NONAFFINE-NEXT:            MayWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg4[o0] };
 ; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
-; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg1[o0] };
-; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg[o0] };
 ; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg1[o0] };
+; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg4[o0] };
 
 target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
diff --git a/polly/test/ScopInfo/multidim_2d_with_modref_call_2.ll b/polly/test/ScopInfo/multidim_2d_with_modref_call_2.ll
index 53d4fd1d857..1598d8ee140 100644
--- a/polly/test/ScopInfo/multidim_2d_with_modref_call_2.ll
+++ b/polly/test/ScopInfo/multidim_2d_with_modref_call_2.ll
@@ -76,15 +76,15 @@
 ; NONAFFINE-NEXT:    p0: %tmp9
 ; NONAFFINE-NEXT:    p1: %tmp14
 ; NONAFFINE-NEXT:    Arrays {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        [1000 x double]* MemRef_arg4[*]; // Element size 8
 ; NONAFFINE-NEXT:    }
 ; NONAFFINE-NEXT:    Arrays (Bounds as pw_affs) {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        [1000 x double]* MemRef_arg4[*]; // Element size 8
diff --git a/polly/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll b/polly/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
index c7ac31bda2a..786ad84493c 100644
--- a/polly/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
+++ b/polly/test/ScopInfo/multidim_fortran_2d_with_modref_call.ll
@@ -77,15 +77,15 @@
 ; NONAFFINE-NEXT:    p0: %tmp9
 ; NONAFFINE-NEXT:    p1: %tmp14
 ; NONAFFINE-NEXT:    Arrays {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        double MemRef_arg4[*]; // Element size 8
 ; NONAFFINE-NEXT:    }
 ; NONAFFINE-NEXT:    Arrays (Bounds as pw_affs) {
-; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_arg[*]; // Element size 8
+; NONAFFINE-NEXT:        i64 MemRef_arg1[*]; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp7; // Element size 8
 ; NONAFFINE-NEXT:        i64 MemRef_tmp8; // Element size 8
 ; NONAFFINE-NEXT:        double MemRef_arg4[*]; // Element size 8
@@ -114,10 +114,10 @@
 ; NONAFFINE-NEXT:            MayWriteAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg4[o0] };
 ; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
-; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg1[o0] };
-; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg[o0] };
 ; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
+; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg1[o0] };
+; NONAFFINE-NEXT:            ReadAccess :=	[Reduction Type: NONE] [Scalar: 0]
 ; NONAFFINE-NEXT:                [tmp9, tmp14] -> { Stmt_bb17[i0, i1] -> MemRef_arg4[o0] };
 ; NONAFFINE-NEXT:    }