Check if array base addresses are invariant

Array base addresses need to be invariant in the region considered. The base
address has to be computed outside the region, or, when it is computed inside,
the value must not change with the iterations of the loops. For example, when a
two-dimensional array is represented as a pointer to pointers the base address
A[i] in an access A[i][j] changes with i; therefore, such regions have to be
rejected.

Contributed by:  Armin Größlinger <armin.groesslinger@uni-passau.de>

llvm-svn: 200314

3 files changed, 130 insertions, 5 deletions

diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h
index 63c5c1bbe72..0450311e256 100755
--- a/polly/include/polly/ScopDetection.h
+++ b/polly/include/polly/ScopDetection.h
@@ -152,6 +152,15 @@ class ScopDetection : public FunctionPass {
   /// @return The failure message why the alias is invalid.
   std::string formatInvalidAlias(AliasSet &AS) const;
 
+  /// @brief Check if a value is invariant in the region Reg.
+  ///
+  /// @param Val Value to check for invariance.
+  /// @param Reg The region to consider for the invariance of Val.
+  ///
+  /// @return True if the value represented by Val is invariant in the region
+  ///         identified by Reg.
+  bool isInvariant(const Value &Val, const Region &Reg) const;
+
   /// @brief Check if a memory access can be part of a Scop.
   ///
   /// @param Inst The instruction accessing the memory.
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 9456ab3afa5..87314b88200 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -348,6 +348,53 @@ std::string ScopDetection::formatInvalidAlias(AliasSet &AS) const {
   return OS.str();
 }
 
+bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
+  // A reference to function argument or constant value is invariant.
+  if (isa<Argument>(Val) || isa<Constant>(Val))
+    return true;
+
+  const Instruction *I = dyn_cast<Instruction>(&Val);
+  if (!I)
+    return false;
+
+  if (!Reg.contains(I))
+    return true;
+
+  if (I->mayHaveSideEffects())
+    return false;
+
+  // When Val is a Phi node, it is likely not invariant. We do not check whether
+  // Phi nodes are actually invariant, we assume that Phi nodes are usually not
+  // invariant. Recursively checking the operators of Phi nodes would lead to
+  // infinite recursion.
+  if (isa<PHINode>(*I))
+    return false;
+
+  // Check that all operands of the instruction are
+  // themselves invariant.
+  const Instruction::const_op_iterator OE = I->op_end();
+  for (Instruction::const_op_iterator OI = I->op_begin(); OI != OE; ++OI) {
+    if (!isInvariant(**OI, Reg))
+      return false;
+  }
+
+  // When the instruction is a load instruction, check that no write to memory
+  // in the region aliases with the load.
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
+    AliasAnalysis::Location Loc = AA->getLocation(LI);
+    const Region::const_block_iterator BE = Reg.block_end();
+    // Check if any basic block in the region can modify the location pointed to
+    // by 'Loc'.  If so, 'Val' is (likely) not invariant in the region.
+    for (Region::const_block_iterator BI = Reg.block_begin(); BI != BE; ++BI) {
+      const BasicBlock &BB = **BI;
+      if (AA->canBasicBlockModify(BB, Loc))
+        return false;
+    }
+  }
+
+  return true;
+}
+
 bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
                                         DetectionContext &Context) const {
   Value *Ptr = getPointerOperand(Inst);
@@ -370,6 +417,14 @@ bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
     return false;
   }
 
+  // Check that the base address of the access is invariant in the current
+  // region.
+  if (!isInvariant(*BaseValue, Context.CurRegion)) {
+    INVALID(AffFunc,
+            "Base address not invariant in current region:" << *BaseValue);
+    return false;
+  }
+
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
   if (!AllowNonAffine &&
diff --git a/polly/test/ScopDetect/base_pointer.ll b/polly/test/ScopDetect/base_pointer.ll
index 45bd6b78bbc..ee05d13a3b1 100644
--- a/polly/test/ScopDetect/base_pointer.ll
+++ b/polly/test/ScopDetect/base_pointer.ll
@@ -151,9 +151,9 @@ entry:
 for.i:
   %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
   %ptr = phi float* [ %ptr.next, %for.i.inc ], [ %A, %entry ]
-; To get a PHI node inside a SCoP, that can not be analyzed but
-; for which the surrounding scop is normally still valid we use a function
-; without any sideeffects.
+; To get a PHI node inside a SCoP that can not be analyzed but
+; for which the surrounding SCoP is normally still valid we use a function
+; without any side effects.
   %ptr.next = call float* @getNextBasePtr(float* %ptr)
   br label %S1
 
@@ -182,8 +182,8 @@ entry:
 for.i:
   %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
 ; To get an instruction inside a region, we use a function without side
-; effects on which SCEV blocks, but for which still is clear that the return
-; value remains invariant throughout the whole loop.
+; effects on which SCEV blocks, but for which it is still clear that the
+; return value remains invariant throughout the whole loop.
   %ptr = call float* @getNextBasePtr(float* %A)
   br label %S1
 
@@ -234,3 +234,64 @@ exit:
 
 ; CHECK-LABEL: base_pointer_is_inst_inside_invariant_2
 ; CHECK: Valid Region for Scop: for.i => exit
+
+declare float* @getNextBasePtr3(float*, i64) readnone nounwind
+
+define void @base_pointer_is_inst_inside_variant(i64 %n, float* %A) {
+entry:
+  br label %for.i
+
+for.i:
+  %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
+  %ptr = call float* @getNextBasePtr3(float* %A, i64 %indvar.i)
+  %ptr2 = call float* @getNextBasePtr(float* %ptr)
+  br label %S1
+
+S1:
+  %conv = sitofp i64 %indvar.i to float
+  %arrayidx5 = getelementptr float* %ptr2, i64 %indvar.i
+  store float %conv, float* %arrayidx5, align 4
+  br label %for.i.inc
+
+for.i.inc:
+  %indvar.i.next = add i64 %indvar.i, 1
+  %exitcond.i = icmp ne i64 %indvar.i.next, %n
+  br i1 %exitcond.i, label %for.i, label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: base_pointer_is_inst_inside_variant
+; CHECK-NOT: Valid Region for Scop
+
+define void @base_pointer_is_ptr2ptr(float** noalias %A, i64 %n) {
+entry:
+  br label %for.i
+
+for.i:
+  %indvar.i = phi i64 [ %indvar.i.next, %for.i.inc ], [ 0, %entry ]
+  %arrayidx = getelementptr float** %A, i64 %indvar.i
+  br label %for.j
+
+for.j:
+  %indvar.j = phi i64 [ 0, %for.i ], [ %indvar.j.next, %for.j ]
+  %conv = sitofp i64 %indvar.i to float
+  %basepointer = load float** %arrayidx, align 8
+  %arrayidx5 = getelementptr float* %basepointer, i64 %indvar.j
+  store float %conv, float* %arrayidx5, align 4
+  %indvar.j.next = add i64 %indvar.j, 1
+  %exitcond.j = icmp ne i64 %indvar.j.next, %n
+  br i1 %exitcond.j, label %for.j, label %for.i.inc
+
+for.i.inc:
+  %indvar.i.next = add i64 %indvar.i, 1
+  %exitcond.i = icmp ne i64 %indvar.i.next, %n
+  br i1 %exitcond.i, label %for.i, label %exit
+
+exit:
+  ret void
+}
+
+; CHECK: base_pointer_is_ptr2ptr
+; CHECK-NOT: Valid Region for Scop