[Polly] [WIP] [PPCGCodeGeneration] teach PPCG to codegen with variable bounds + invariant load hoisting.

[bollu]

Summary

• For some reason, upper bound being a variable works, lower bound does not.
• Teach PPCGCodeGeneration to codegen even when lower bound is variable.

[bollu]

• Remove a testcase that trivially worked (merged into master).
• Add a testcase that has both lower and upper bounds.

[bollu]

• Hoist out values from the SubtreeValue because it appears like the value is used in two different "branches" of the code. So, find the closest dominator between where the value is and where it is used by PPCGCodeGeneration and put this instruction there.
• This is crazy, I see no reason as to why this is "correct". However, it seems to generate reasonable code for the testcases I have in mind.
• However, other test cases fail due to the change in hasScalarDepsInsideRegion, because of the change in SCEVInRegionDependences::follow.

[bollu]

• Teach PPCGCodeGeneration to pick up values from ValueMap when it generates

loads and stores.

• No invalid code generated anymore.

• Some test cases fail due to change in generated IR / dependences.

[bollu]

• Simplify replacement logic in PPCGCodeGeneration. [NFC wrt patch]

[bollu]

• Fix all test cases to work with this patch. I'm not sure about two test cases, have written them down here:
• test/ScopInfo/invariant-loads-leave-read-only-statements
• invariant_load_scalar_escape_alloca_sharing.ll

[bollu]

• [NFC wrt patch] General Style & code fixes.

[bollu]

test/DeLICM/reduction_looprotate_hoisted.ll

67 ↗

(On Diff #106396)

@Meinersbur: Does this change fix the FIXME you had added?

[grosser]

LGTM.

polly/trunk/include/polly/Support/SCEVValidator.h

 /// region.
 ///
 /// @param Expr The SCEV to analyze.
 /// @param R The region in which we look for dependences.
 /// @param Scope Location where the value is needed.
 /// @param AllowLoops Whether loop recurrences outside the loop that are in the
 ///                   region count as dependence.
 bool hasScalarDepsInsideRegion(const llvm::SCEV *Expr, const llvm::Region *R,
-                               llvm::Loop *Scope, bool AllowLoops);
+                               llvm::Loop *Scope, bool AllowLoops,
+                               const InvariantLoadsSetTy &ILS);
 bool isAffineExpr(const llvm::Region *R, llvm::Loop *Scope,
                   const llvm::SCEV *Expression, llvm::ScalarEvolution &SE,
                   InvariantLoadsSetTy *ILS = nullptr);
 
 /// Check if @p V describes an affine constraint in @p R.
 bool isAffineConstraint(llvm::Value *V, const llvm::Region *R,
                         llvm::Loop *Scope, llvm::ScalarEvolution &SE,
                         ParameterSetTy &Params, bool OrExpr = false);

polly/trunk/include/polly/Support/ScopHelper.h

 // the loop itself.
 //
 // @param BB            Pointer to the Basic Block to analyze.
 // @param LI            Reference to the LoopInfo.
 // @param BoxedLoops    Set of Boxed Loops we get from the SCoP.
 llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI,
                                     const BoxedLoopsSetTy &BoxedLoops);
 } // namespace polly
-#endif
+#endif
 

polly/trunk/lib/Analysis/ScopDetection.cpp

if (auto *Unknown = dyn_cast<SCEVUnknown>(DelinearizedSize)) {
       auto *V = dyn_cast<Value>(Unknown->getValue());
       if (auto *Load = dyn_cast<LoadInst>(V)) {
         if (Context.CurRegion.contains(Load) &&
             isHoistableLoad(Load, CurRegion, LI, SE, DT))
           Context.RequiredILS.insert(Load);
         continue;
       }
     }
-    if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false))
+    if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion, Scope, false,
+                                  Context.RequiredILS))
       return invalid<ReportNonAffineAccess>(
           Context, /*Assert=*/true, DelinearizedSize,
           Context.Accesses[BasePointer].front().first, BaseValue);
   }
 
   // No array shape derived.
   if (Sizes.empty()) {
     if (AllowNonAffine)

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::getReferencesInSubtree(__isl_keep isl_ast_node *For,
   Values.remove_if([](const Value *V) { return isa<GlobalValue>(V); });
 
   /// Remove loops that contain the scop or that are part of the scop, as they
   /// are considered local. This leaves only loops that are before the scop, but
   /// do not contain the scop itself.
   Loops.remove_if([this](const Loop *L) {
     return S.contains(L) || L->contains(S.getEntry());
   });
+
+  // Contains Values that may need to be replaced with other values
+  // due to replacements from the ValueMap. We should make sure
+  // that we return correctly remapped values.
+  // NOTE: this code path is tested by:
+  //     1.  test/Isl/CodeGen/OpenMP/single_loop_with_loop_invariant_baseptr.ll
+  //     2.  test/Isl/CodeGen/OpenMP/loop-body-references-outer-values-3.ll
+  SetVector<Value *> ReplacedValues;
+  for (Value *V : Values) {
+    auto It = ValueMap.find(V);
+    if (It == ValueMap.end())
+      ReplacedValues.insert(V);
+    else
+      ReplacedValues.insert(It->second);
+  }
+  Values = ReplacedValues;
 }
 
 void IslNodeBuilder::updateValues(ValueMapT &NewValues) {
   SmallPtrSet<Value *, 5> Inserted;
 
   for (const auto &I : IDToValue) {
     IDToValue[I.first] = NewValues[I.second];
     Inserted.insert(I.second);

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

GPUNodeBuilder::getReferencesInKernel(ppcg_kernel *Kernel) {
   // ValidSubtree{Values, Functions} have any common element.
   auto ValidSubtreeValuesIt =
       make_filter_range(SubtreeValues, isValidSubtreeValue);
   SetVector<Value *> ValidSubtreeValues(ValidSubtreeValuesIt.begin(),
                                         ValidSubtreeValuesIt.end());
   SetVector<Function *> ValidSubtreeFunctions(
       getFunctionsFromRawSubtreeValues(SubtreeValues));
 
-  return std::make_pair(ValidSubtreeValues, ValidSubtreeFunctions);
+  // @see IslNodeBuilder::getReferencesInSubtree
+  SetVector<Value *> ReplacedValues;
+  for (Value *V : ValidSubtreeValues) {
+    auto It = ValueMap.find(V);
+    if (It == ValueMap.end())
+      ReplacedValues.insert(V);
+    else
+      ReplacedValues.insert(It->second);
+  }
+  return std::make_pair(ReplacedValues, ValidSubtreeFunctions);
 }
 
 void GPUNodeBuilder::clearDominators(Function *F) {
   DomTreeNode *N = DT.getNode(&F->getEntryBlock());
   std::vector<BasicBlock *> Nodes;
   for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
     Nodes.push_back(I->getBlock());
 
for (long i = 0; i < NumHostIters; i++) {
     Index++;
   }
 
   int NumVars = isl_space_dim(Kernel->space, isl_dim_param);
 
   for (long i = 0; i < NumVars; i++) {
     isl_id *Id = isl_space_get_dim_id(Kernel->space, isl_dim_param, i);
     Value *Val = IDToValue[Id];
+    if (ValueMap.count(Val))
+      Val = ValueMap[Val];
     isl_id_free(Id);
 
     ArgSizes[Index] = computeSizeInBytes(Val->getType());
 
     Instruction *Param =
         new AllocaInst(Val->getType(), AddressSpace,
                        Launch + "_param_" + std::to_string(Index),
                        EntryBlock->getTerminator());

polly/trunk/lib/Support/SCEVValidator.cpp

public:
   bool isDone() { return HasIVParams; }
   bool hasIVParams() { return HasIVParams; }
 };
 
 /// Check whether a SCEV refers to an SSA name defined inside a region.
 class SCEVInRegionDependences {
   const Region *R;
   Loop *Scope;
+  const InvariantLoadsSetTy &ILS;
   bool AllowLoops;
   bool HasInRegionDeps = false;
 
 public:
-  SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops)
-      : R(R), Scope(Scope), AllowLoops(AllowLoops) {}
+  SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops,
+                          const InvariantLoadsSetTy &ILS)
+      : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {}
 
   bool follow(const SCEV *S) {
     if (auto Unknown = dyn_cast<SCEVUnknown>(S)) {
       Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
 
       CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
 
       if (Call && isConstCall(Call))
         return false;
 
+      if (Inst) {
+        // When we invariant load hoist a load, we first make sure that there
+        // can be no dependences created by it in the Scop region. So, we should
+        // not consider scalar dependences to `LoadInst`s that are invariant
+        // load hoisted.
+        //
+        // If this check is not present, then we create data dependences which
+        // are strictly not necessary by tracking the invariant load as a
+        // scalar.
+        LoadInst *LI = dyn_cast<LoadInst>(Inst);
+        if (LI && ILS.count(LI) > 0)
+          return false;
+      }
+
       // Return true when Inst is defined inside the region R.
       if (!Inst || !R->contains(Inst))
         return true;
 
       HasInRegionDeps = true;
       return false;
     }
 

 bool hasIVParams(const SCEV *Expr) {
   SCEVHasIVParams HasIVParams;
   SCEVTraversal<SCEVHasIVParams> ST(HasIVParams);
   ST.visitAll(Expr);
   return HasIVParams.hasIVParams();
 }
 
 bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
-                               llvm::Loop *Scope, bool AllowLoops) {
-  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops);
+                               llvm::Loop *Scope, bool AllowLoops,
+                               const InvariantLoadsSetTy &ILS) {
+  SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS);
   SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
   ST.visitAll(Expr);
   return InRegionDeps.hasDependences();
 }
 
 bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
                   ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
   if (isa<SCEVCouldNotCompute>(Expr))

polly/trunk/lib/Support/ScopHelper.cpp

bool polly::isIgnoredIntrinsic(const Value *V) {
   return false;
 }
 
 bool polly::canSynthesize(const Value *V, const Scop &S, ScalarEvolution *SE,
                           Loop *Scope) {
   if (!V || !SE->isSCEVable(V->getType()))
     return false;
 
+  const InvariantLoadsSetTy &ILS = S.getRequiredInvariantLoads();
   if (const SCEV *Scev = SE->getSCEVAtScope(const_cast<Value *>(V), Scope))
     if (!isa<SCEVCouldNotCompute>(Scev))
-      if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false))
+      if (!hasScalarDepsInsideRegion(Scev, &S.getRegion(), Scope, false, ILS))
         return true;
 
   return false;
 }
 
 llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
   Instruction *UI = dyn_cast<Instruction>(U.getUser());
   if (!UI)

polly/trunk/test/DeLICM/reduction_looprotate_hoisted.ll

 }
 
 ; FIXME: The accesses for %i should not be there because, with
 ; load-hoisting %Start is an affine loop. To be fixed in ScopBuilder.
 
 ; CHECK:      After accesses {
 ; CHECK-NEXT:     Stmt_reduction_preheader
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_i__phi[] };
-; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
 ; CHECK-NEXT:     Stmt_reduction_for
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_i__phi[] };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and -i0 < i1 <= 3 - Start; Stmt_reduction_for[1, 0] -> MemRef_A[1] : Start >= 4; Stmt_reduction_for[0, 0] -> MemRef_A[0] };
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_reduction_for[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= -4 + Start; Stmt_reduction_for[1, 0] -> MemRef_A[1] : Start <= 4 };
-; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [Start] -> { Stmt_reduction_for[i0, i1] -> MemRef_i[] };
 ; CHECK-NEXT:     Stmt_body
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_body[i0, i1] -> MemRef_mul[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_body[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 and i0 <= -4 + Start; Stmt_body[1, 0] -> MemRef_A[1] : Start <= 4 };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_body[i0, i1] -> MemRef_phi[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_body[i0, i1] -> MemRef_A[i0] : Start <= 3 and 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_body[1, 0] -> MemRef_A[1]; Stmt_body[0, 0] -> MemRef_A[0] : Start >= 4 };
 ; CHECK-NEXT:     Stmt_reduction_inc
-; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_i__phi[] };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_mul[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : Start <= 3 and 0 <= i0 <= 1 and i0 <= i1 <= 3 - Start; Stmt_reduction_inc[1, 0] -> MemRef_A[1]; Stmt_reduction_inc[0, 0] -> MemRef_A[0] : Start >= 4 };
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 < i1 <= 3 - Start; Stmt_reduction_inc[i0, 0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:                 [Start] -> { Stmt_reduction_inc[i0, i1] -> MemRef_i[] };
 ; CHECK-NEXT:     Stmt_reduction_exit
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
-; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:             ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 [Start] -> { Stmt_reduction_exit[i0] -> MemRef_mul[] };
 ; CHECK-NEXT:            new: [Start] -> { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
 ; CHECK-NEXT: }

polly/trunk/test/GPGPU/invariant-load-hoisting-with-variable-bounds.ll

+; RUN: opt %loadPolly -analyze -polly-use-llvm-names -polly-scops \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=SCOP
+
+
+; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-codegen-ppcg \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=HOST-IR
+
+; REQUIRES: pollyacc
+
+; SCOP:      Function: f
+; SCOP-NEXT: Region: %entry.split---%for.end
+; SCOP-NEXT: Max Loop Depth:  1
+; SCOP-NEXT: Invariant Accesses: {
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             [tmp1, tmp4] -> { Stmt_entry_split[] -> MemRef_begin[0] };
+; SCOP-NEXT:         Execution Context: [tmp1, tmp4] -> {  :  }
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             [tmp1, tmp4] -> { Stmt_for_body[i0] -> MemRef_end[0] };
+; SCOP-NEXT:         Execution Context: [tmp1, tmp4] -> {  :  }
+; SCOP-NEXT: }
+
+
+; Check that the kernel launch is generated in the host IR.
+; This declaration would not have been generated unless a kernel launch exists.
+; HOST-IR: declare void @polly_launchKernel(i8*, i32, i32, i32, i32, i32, i8*)
+
+;    void f(int *begin, int *end, int *arr) {
+;      for (int i = *begin; i < *end; i++) {
+;        arr[i] = 0;
+;      }
+;    }
+;
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
+
+define void @f(i32* %begin, i32* %end, i32* %arr) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %tmp1 = load i32, i32* %begin, align 4
+  %tmp41 = load i32, i32* %end, align 4
+  %cmp2 = icmp slt i32 %tmp1, %tmp41
+  br i1 %cmp2, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.03 = phi i32 [ %tmp1, %for.body.lr.ph ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %arr, i32 %i.03
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i32 %i.03, 1
+  %tmp4 = load i32, i32* %end, align 4
+  %cmp = icmp slt i32 %inc, %tmp4
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  ret void
+}

polly/trunk/test/GPGPU/invariant-load-hoisting-with-variable-lower-bound.ll

+; RUN: opt %loadPolly -analyze -polly-use-llvm-names -polly-scops \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=SCOP
+
+
+; RUN: opt %loadPolly -S -polly-use-llvm-names -polly-codegen-ppcg \
+; RUN: -polly-invariant-load-hoisting < %s | FileCheck %s -check-prefix=HOST-IR
+
+; REQUIRES: pollyacc
+
+; Check that we detect a scop with invariant accesses.
+; SCOP:      Function: f
+; SCOP-NEXT: Region: %entry.split---%for.end
+; SCOP-NEXT: Max Loop Depth:  1
+; SCOP-NEXT: Invariant Accesses: {
+; SCOP-NEXT:         ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; SCOP-NEXT:             [beginval] -> { Stmt_entry_split[] -> MemRef_begin[0] };
+; SCOP-NEXT:         Execution Context: [beginval] -> {  :  }
+; SCOP-NEXT: }
+
+; Check that the kernel launch is generated in the host IR.
+; This declaration would not have been generated unless a kernel launch exists.
+; HOST-IR: declare void @polly_launchKernel(i8*, i32, i32, i32, i32, i32, i8*)
+
+; 
+; void f(int *begin, int *arr) {
+;     for (int i = *begin; i < 100; i++) {
+;         arr[i] = 0;
+;     }
+; }
+
+target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
+
+define void @f(i32* %begin, i32* %arr) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %beginval = load i32, i32* %begin, align 4
+  %cmp1 = icmp slt i32 %beginval, 100
+  br i1 %cmp1, label %for.body, label %for.end
+
+
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %ival = phi i32 [ %beginval, %entry.split ], [ %inc, %for.body ]
+  %arrayidx = getelementptr inbounds i32, i32* %arr, i32 %ival
+  store i32 0, i32* %arrayidx, align 4
+  %inc = add nsw i32 %ival, 1
+  %cmp = icmp slt i32 %ival, 99
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  ret void
+}

polly/trunk/test/GPGPU/invariant-load-hoisting.ll

 ; SCOP:       Function: f
 ; SCOP-NEXT:  Region: %entry.split---%for.end26
 ; SCOP-NEXT:  Max Loop Depth:  3
 ; SCOP-NEXT:  Invariant Accesses: {
 ; SCOP-NEXT:          ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; SCOP-NEXT:              [n, tmp12] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_invariant[0] };
 ; SCOP-NEXT:          Execution Context: [n, tmp12] -> {  : n > 0 }
 ; SCOP-NEXT:  }
-;
-; HOST-IR:      call void @polly_launchKernel(i8* %215, i32 %221, i32 1, i32 32, i32 1, i32 1, i8* %polly_launch_0_params_i8ptr)
-; HOST-IR-NEXT: call void @polly_freeKernel(i8* %215)
-;
-; KERNEL-IR: define ptx_kernel void @FUNC_f_SCOP_0_KERNEL_0(i8 addrspace(1)* %MemRef_B, i8 addrspace(1)* %MemRef_A, i32 %n, i32 %tmp12) #0 {
-;
+; HOST-IR:      call void @polly_launchKernel(i8* %219, i32 %225, i32 1, i32 32, i32 1, i32 1, i8* %polly_launch_0_params_i8ptr)
+; HOST-IR-NEXT: call void @polly_freeKernel(i8* %219)
+
+; KERNEL-IR: define ptx_kernel void @FUNC_f_SCOP_0_KERNEL_0(i8 addrspace(1)* %MemRef_B, i8 addrspace(1)* %MemRef_A, i32 %n, i32 %tmp12, i32 %polly.preload.tmp21.merge)
+
+
 ; Check that we generate correct GPU code in case of invariant load hoisting.
 ;
 ;
 ;    static const int N = 3000;
 ;
 ;    void f(int A[N][N], int *invariant, int B[N][N], int n) {
 ;      for (int i = 0; i < n; i++) {
 ;        for (int j = 0; j < n; j++) {

polly/trunk/test/Isl/CodeGen/invariant_load_base_pointer.ll

 ; RUN: opt %loadPolly  -polly-codegen -polly-invariant-load-hoisting=true -polly-ignore-aliasing -polly-process-unprofitable -S < %s | FileCheck %s
 ;
 ; CHECK-LABEL: polly.preload.begin:
 ; CHECK-NEXT:    %polly.access.BPLoc = getelementptr i32*, i32** %BPLoc, i64 0
 ; CHECK-NEXT:    %polly.access.BPLoc.load = load i32*, i32** %polly.access.BPLoc
 ;
 ; CHECK-LABEL: polly.stmt.bb2:
-; CHECK-NEXT:    %p_tmp3 = getelementptr inbounds i32, i32* %polly.access.BPLoc.load, i64 %polly.indvar
+; CHECK-NEXT:    %scevgep = getelementptr i32, i32* %polly.access.BPLoc.load, i64 %polly.indvar
 ;
 ;    void f(int **BPLoc) {
 ;      for (int i = 0; i < 1024; i++)
 ;        (*BPLoc)[i] = 0;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 

polly/trunk/test/Isl/CodeGen/invariant_load_base_pointer_conditional.ll

 ; RUN: opt %loadPolly  -polly-codegen -polly-invariant-load-hoisting=true -polly-ignore-aliasing -polly-process-unprofitable -S < %s | FileCheck %s
 ;
 ; CHECK-LABEL: polly.preload.begin:
 ; CHECK-NEXT:    %0 = sext i32 %N to i64
 ; CHECK-NEXT:    %1 = icmp sge i64 %0, 514
 ; CHECK-NEXT:    br label %polly.preload.cond
 ;
 ; CHECK-LABEL: polly.preload.cond:
 ; CHECK-NEXT:    br i1 %1, label %polly.preload.exec, label %polly.preload.merge
 ;
 ; CHECK-LABEL: polly.preload.merge:
 ; CHECK-NEXT:    %polly.preload.tmp6.merge = phi i32* [ %polly.access.BPLoc.load, %polly.preload.exec ], [ null, %polly.preload.cond ]
 ;
 ; CHECK-LABEL: polly.stmt.bb5:
-; CHECK-NEXT:    %p_tmp7 = getelementptr inbounds i32, i32* %polly.preload.tmp6.merge, i64 %polly.indvar6
+; CHECK-NEXT:    %scevgep9 = getelementptr i32, i32* %polly.preload.tmp6.merge, i64 %polly.indvar6
 ;
 ;    void f(int **BPLoc, int *A, int N) {
 ;      for (int i = 0; i < N; i++)
 ;        if (i > 512)
 ;          (*BPLoc)[i] = 0;
 ;        else
 ;          A[i] = 0;
 ;    }

polly/trunk/test/Isl/CodeGen/invariant_load_ptr_ptr_noalias.ll

 ; RUN: opt %loadPolly -polly-process-unprofitable -polly-codegen -polly-invariant-load-hoisting=true -polly-ignore-aliasing -S  < %s | FileCheck %s
 ;
 ; CHECK-LABEL: polly.preload.begin:
 ; CHECK:   %polly.access.A = getelementptr i32**, i32*** %A, i64 42
 ; CHECK:   %polly.access.A.load = load i32**, i32*** %polly.access.A
 ; CHECK:   %polly.access.polly.access.A.load = getelementptr i32*, i32** %polly.access.A.load, i64 32
 ; CHECK:   %polly.access.polly.access.A.load.load = load i32*, i32** %polly.access.polly.access.A.load
 ;
 ; CHECK: polly.stmt.bb2:
-; CHECK:   %p_tmp6 = getelementptr inbounds i32, i32* %polly.access.polly.access.A.load.load, i64 %polly.indvar
-; CHECK:   store i32 0, i32* %p_tmp6, align 4
+; CHECK: %scevgep = getelementptr i32, i32* %polly.access.polly.access.A.load.load, i64 %polly.indvar
+; CHECK:   store i32 0, i32* %scevgep, align 4
 ;
 ;    void f(int ***A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[42][32][i] = 0;
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 

polly/trunk/test/Isl/CodeGen/invariant_load_scalar_escape_alloca_sharing.ll

 ; RUN: opt %loadPolly -polly-codegen -polly-invariant-load-hoisting=true -S < %s | FileCheck %s
 ;
 ; Verify the preloaded %tmp0 is stored and communicated in the same alloca.
 ; In this case, we do not reload %ncol.load from the scalar stack slot, but
 ; instead use directly the preloaded value stored in GlobalMap.
 ;
 ; CHECK-NOT: alloca
-; CHECK:     %dec3.s2a = alloca i32
-; CHECK-NOT: alloca
-; CHECK:     %dec3.in.phiops = alloca i32
-; CHECK-NOT: alloca
 ; CHECK:     %tmp0.preload.s2a = alloca i32
 ; CHECK-NOT: alloca
 ;
 ; CHECK:       %ncol.load = load i32, i32* @ncol
 ; CHECK-NEXT:  store i32 %ncol.load, i32* %tmp0.preload.s2a
 ;
-; CHECK:      polly.stmt.while.body.lr.ph:
-; CHECK-NEXT:   store i32 %ncol.load, i32* %dec3.in.phiops
-;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 @ncol = external global i32, align 4
 
 define void @melt_data(i32* %data1, i32* %data2) {
 entry:
   br label %entry.split
 

polly/trunk/test/ScopInfo/complex-successor-structure-3.ll

 ; RUN: opt %loadPolly -analyze -polly-scops \
 ; RUN: -polly-invariant-load-hoisting=true < %s | FileCheck %s
 ;
 ; Check that propagation of domains from A(X) to A(X+1) will keep the
 ; domains small and concise.
 ;
 ; CHECK:         Assumed Context:
 ; CHECK-NEXT:    [tmp5, tmp, tmp8, tmp11, tmp14, tmp17, tmp20, tmp23, tmp26] -> {  :  }
 ; CHECK-NEXT:    Invalid Context:
 ; CHECK-NEXT:    [tmp5, tmp, tmp8, tmp11, tmp14, tmp17, tmp20, tmp23, tmp26] -> {  : 1 = 0 }
 ;
 ; CHECK:         Stmt_FINAL
 ; CHECK-NEXT:            Domain :=
 ; CHECK-NEXT:                [tmp5, tmp, tmp8, tmp11, tmp14, tmp17, tmp20, tmp23, tmp26] -> { Stmt_FINAL[] };
 ; CHECK-NEXT:            Schedule :=
-; CHECK-NEXT:                [tmp5, tmp, tmp8, tmp11, tmp14, tmp17, tmp20, tmp23, tmp26] -> { Stmt_FINAL[] -> [22] };
+; CHECK-NEXT:                [tmp5, tmp, tmp8, tmp11, tmp14, tmp17, tmp20, tmp23, tmp26] -> { Stmt_FINAL[] -> [16] };
 ;
 ;
 ;    void f(short *restrict In, int *restrict Out) {
 ;      int InV, V, Idx;
 ;      Idx = 0;
 ;      V = 999;
 ;
 ;    A0:

polly/trunk/test/ScopInfo/invariant-loads-leave-read-only-statements.ll

 ; RUN: opt %loadPolly -polly-scops -polly-invariant-load-hoisting=true -analyze < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen -polly-invariant-load-hoisting=true -analyze < %s
 
 ; CHECK:      Statements {
-; CHECK-NEXT:     Stmt_top_split
-; CHECK-NEXT:         Domain :=
-; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_top_split[] };
-; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_top_split[] -> [0, 0, 0, 0] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_top_split[] -> MemRef_tmp25[] };
-; CHECK-NEXT:     Stmt_L_4
+; CHECK-NEXT:   Stmt_L_4
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] : 0 <= i0 < tmp8 and 0 <= i1 < tmp8 and 0 <= i2 < tmp8 };
 ; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> [1, i0, i1, i2] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> MemRef_tmp19[i1, i0] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> MemRef_tmp5[i2, i0] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> MemRef_tmp12[i2, i1] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> MemRef_tmp19[i1, i0] };
-; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [tmp8, tmp22, tmp15] -> { Stmt_L_4[i0, i1, i2] -> MemRef_tmp25[] };
 ; CHECK-NEXT: }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 %jl_value_t = type { %jl_value_t* }
 
 define %jl_value_t* @julia_gemm_22583(%jl_value_t*, %jl_value_t** %tmp1, i32) {
 top: