[FIX] Bail out if there is a dependence cycle between invariant loads

  While the program cannot cause a dependence cycle between invariant
  loads, additional constraints (e.g., to ensure finite loops) can
  introduce them. It is hard to detect them in the SCoP description,
  thus we will only check for them at code generation time. If such a
  recursion is detected we will bail out the code generation and place a
  "false" runtime check to guarantee the original code is used.

  This fixes bug 25443.

llvm-svn: 252412

5 files changed, 175 insertions, 51 deletions

diff --git a/polly/include/polly/CodeGen/IslNodeBuilder.h b/polly/include/polly/CodeGen/IslNodeBuilder.h
index d1fb31c3845..30be60a0299 100644
--- a/polly/include/polly/CodeGen/IslNodeBuilder.h
+++ b/polly/include/polly/CodeGen/IslNodeBuilder.h
@@ -44,7 +44,7 @@ public:
   void create(__isl_take isl_ast_node *Node);
 
   /// @brief Preload all memory loads that are invariant.
-  void preloadInvariantLoads();
+  bool preloadInvariantLoads();
 
   /// @brief Finalize code generation for the SCoP @p S.
   ///
@@ -119,13 +119,17 @@ protected:
   ValueMapT ValueMap;
 
   /// @brief Materialize code for @p Id if it was not done before.
-  void materializeValue(__isl_take isl_id *Id);
+  ///
+  /// @returns False, iff a problem occured and the value was not materialized.
+  bool materializeValue(__isl_take isl_id *Id);
 
   /// @brief Materialize parameters of @p Set.
   ///
   /// @param All If not set only parameters referred to by the constraints in
   ///            @p Set will be materialized, otherwise all.
-  void materializeParameters(__isl_take isl_set *Set, bool All);
+  ///
+  /// @returns False, iff a problem occured and the value was not materialized.
+  bool materializeParameters(__isl_take isl_set *Set, bool All);
 
   // Extract the upper bound of this loop
   //
@@ -204,6 +208,9 @@ protected:
   virtual void createMark(__isl_take isl_ast_node *Marker);
   virtual void createFor(__isl_take isl_ast_node *For);
 
+  /// @brief Set to remember materialized invariant loads.
+  SmallPtrSet<const SCEV *, 16> PreloadedPtrs;
+
   /// @brief Preload the memory access at @p AccessRange with @p Build.
   ///
   /// @returns The preloaded value casted to type @p Ty
@@ -228,7 +235,9 @@ protected:
   /// This function will preload the representing load from @p IAClass and
   /// map all members of @p IAClass to that preloaded value, potentially casted
   /// to the required type.
-  void preloadInvariantEquivClass(const InvariantEquivClassTy &IAClass);
+  ///
+  /// @returns False, iff a problem occured and the load was not preloaded.
+  bool preloadInvariantEquivClass(const InvariantEquivClassTy &IAClass);
 
   void createForVector(__isl_take isl_ast_node *For, int VectorWidth);
   void createForSequential(__isl_take isl_ast_node *For);
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
index 7e6f044953d..95ddbfbbfd6 100644
--- a/polly/lib/CodeGen/CodeGeneration.cpp
+++ b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -147,8 +147,15 @@ public:
     // parameters they reference. Afterwards, for the remaining parameters that
     // might reference the hoisted loads. Finally, build the runtime check
     // that might reference both hoisted loads as well as parameters.
+    // If the hoisting fails we have to bail and execute the original code.
     Builder.SetInsertPoint(SplitBlock->getTerminator());
-    NodeBuilder.preloadInvariantLoads();
+    if (!NodeBuilder.preloadInvariantLoads()) {
+      auto *FalseI1 = Builder.getFalse();
+      Builder.GetInsertBlock()->getTerminator()->setOperand(0, FalseI1);
+      isl_ast_node_free(AstRoot);
+      return true;
+    }
+
     NodeBuilder.addParameters(S.getContext());
 
     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index 5e037e215cc..0a6d265ad73 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -612,6 +612,8 @@ Value *IslExprBuilder::createId(__isl_take isl_ast_expr *Expr) {
   assert(IDToValue.count(Id) && "Identifier not found");
 
   V = IDToValue[Id];
+  if (!V)
+    V = UndefValue::get(getType(Expr));
 
   assert(V && "Unknown parameter id found");
 
diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp
index 1942d9d35c0..9e4358f27ad 100644
--- a/polly/lib/CodeGen/IslNodeBuilder.cpp
+++ b/polly/lib/CodeGen/IslNodeBuilder.cpp
@@ -815,7 +815,7 @@ void IslNodeBuilder::create(__isl_take isl_ast_node *Node) {
   llvm_unreachable("Unknown isl_ast_node type");
 }
 
-void IslNodeBuilder::materializeValue(isl_id *Id) {
+bool IslNodeBuilder::materializeValue(isl_id *Id) {
   // If the Id is already mapped, skip it.
   if (!IDToValue.count(Id)) {
     auto *ParamSCEV = (const SCEV *)isl_id_get_user(Id);
@@ -828,22 +828,28 @@ void IslNodeBuilder::materializeValue(isl_id *Id) {
     findValues(ParamSCEV, Values);
     for (auto *Val : Values)
       if (const auto *IAClass = S.lookupInvariantEquivClass(Val))
-        preloadInvariantEquivClass(*IAClass);
+        if (!preloadInvariantEquivClass(*IAClass)) {
+          isl_id_free(Id);
+          return false;
+        }
 
     auto *V = generateSCEV(ParamSCEV);
     IDToValue[Id] = V;
   }
 
   isl_id_free(Id);
+  return true;
 }
 
-void IslNodeBuilder::materializeParameters(isl_set *Set, bool All) {
+bool IslNodeBuilder::materializeParameters(isl_set *Set, bool All) {
   for (unsigned i = 0, e = isl_set_dim(Set, isl_dim_param); i < e; ++i) {
     if (!All && !isl_set_involves_dims(Set, isl_dim_param, i, 1))
       continue;
     isl_id *Id = isl_set_get_dim_id(Set, isl_dim_param, i);
-    materializeValue(Id);
+    if (!materializeValue(Id))
+      return false;
   }
+  return true;
 }
 
 Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
@@ -860,10 +866,14 @@ Value *IslNodeBuilder::preloadUnconditionally(isl_set *AccessRange,
 Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
                                             isl_set *Domain) {
 
-  auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
   isl_set *AccessRange = isl_map_range(MA.getAccessRelation());
-  materializeParameters(AccessRange, false);
+  if (!materializeParameters(AccessRange, false)) {
+    isl_set_free(AccessRange);
+    isl_set_free(Domain);
+    return nullptr;
+  }
 
+  auto *Build = isl_ast_build_from_context(isl_set_universe(S.getParamSpace()));
   isl_set *Universe = isl_set_universe(isl_set_get_space(Domain));
   bool AlwaysExecuted = isl_set_is_equal(Domain, Universe);
   isl_set_free(Universe);
@@ -871,58 +881,66 @@ Value *IslNodeBuilder::preloadInvariantLoad(const MemoryAccess &MA,
   Instruction *AccInst = MA.getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
-  Value *PreloadVal;
+  Value *PreloadVal = nullptr;
   if (AlwaysExecuted) {
-    isl_set_free(Domain);
     PreloadVal = preloadUnconditionally(AccessRange, Build, AccInstTy);
-  } else {
+    isl_ast_build_free(Build);
+    isl_set_free(Domain);
+    return PreloadVal;
+  }
 
-    materializeParameters(Domain, false);
-    isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
+  if (!materializeParameters(Domain, false)) {
+    isl_ast_build_free(Build);
+    isl_set_free(AccessRange);
+    isl_set_free(Domain);
+    return nullptr;
+  }
 
-    Value *Cond = ExprBuilder.create(DomainCond);
-    if (!Cond->getType()->isIntegerTy(1))
-      Cond = Builder.CreateIsNotNull(Cond);
+  isl_ast_expr *DomainCond = isl_ast_build_expr_from_set(Build, Domain);
+  Domain = nullptr;
 
-    BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
-                                    &*Builder.GetInsertPoint(), &DT, &LI);
-    CondBB->setName("polly.preload.cond");
+  Value *Cond = ExprBuilder.create(DomainCond);
+  if (!Cond->getType()->isIntegerTy(1))
+    Cond = Builder.CreateIsNotNull(Cond);
 
-    BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
-    MergeBB->setName("polly.preload.merge");
+  BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
+                                  &*Builder.GetInsertPoint(), &DT, &LI);
+  CondBB->setName("polly.preload.cond");
 
-    Function *F = Builder.GetInsertBlock()->getParent();
-    LLVMContext &Context = F->getContext();
-    BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
+  BasicBlock *MergeBB = SplitBlock(CondBB, &CondBB->front(), &DT, &LI);
+  MergeBB->setName("polly.preload.merge");
 
-    DT.addNewBlock(ExecBB, CondBB);
-    if (Loop *L = LI.getLoopFor(CondBB))
-      L->addBasicBlockToLoop(ExecBB, LI);
+  Function *F = Builder.GetInsertBlock()->getParent();
+  LLVMContext &Context = F->getContext();
+  BasicBlock *ExecBB = BasicBlock::Create(Context, "polly.preload.exec", F);
+
+  DT.addNewBlock(ExecBB, CondBB);
+  if (Loop *L = LI.getLoopFor(CondBB))
+    L->addBasicBlockToLoop(ExecBB, LI);
 
-    auto *CondBBTerminator = CondBB->getTerminator();
-    Builder.SetInsertPoint(CondBBTerminator);
-    Builder.CreateCondBr(Cond, ExecBB, MergeBB);
-    CondBBTerminator->eraseFromParent();
+  auto *CondBBTerminator = CondBB->getTerminator();
+  Builder.SetInsertPoint(CondBBTerminator);
+  Builder.CreateCondBr(Cond, ExecBB, MergeBB);
+  CondBBTerminator->eraseFromParent();
 
-    Builder.SetInsertPoint(ExecBB);
-    Builder.CreateBr(MergeBB);
+  Builder.SetInsertPoint(ExecBB);
+  Builder.CreateBr(MergeBB);
 
-    Builder.SetInsertPoint(ExecBB->getTerminator());
-    Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInstTy);
+  Builder.SetInsertPoint(ExecBB->getTerminator());
+  Value *PreAccInst = preloadUnconditionally(AccessRange, Build, AccInstTy);
 
-    Builder.SetInsertPoint(MergeBB->getTerminator());
-    auto *MergePHI = Builder.CreatePHI(
-        AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
-    MergePHI->addIncoming(PreAccInst, ExecBB);
-    MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
-    PreloadVal = MergePHI;
-  }
+  Builder.SetInsertPoint(MergeBB->getTerminator());
+  auto *MergePHI = Builder.CreatePHI(
+      AccInstTy, 2, "polly.preload." + AccInst->getName() + ".merge");
+  MergePHI->addIncoming(PreAccInst, ExecBB);
+  MergePHI->addIncoming(Constant::getNullValue(AccInstTy), CondBB);
+  PreloadVal = MergePHI;
 
   isl_ast_build_free(Build);
   return PreloadVal;
 }
 
-void IslNodeBuilder::preloadInvariantEquivClass(
+bool IslNodeBuilder::preloadInvariantEquivClass(
     const InvariantEquivClassTy &IAClass) {
   // For an equivalence class of invariant loads we pre-load the representing
   // element with the unified execution context. However, we have to map all
@@ -936,19 +954,29 @@ void IslNodeBuilder::preloadInvariantEquivClass(
   // If the access function was already mapped, the preload of this equivalence
   // class was triggered earlier already and doesn't need to be done again.
   if (ValueMap.count(MA->getAccessInstruction()))
-    return;
+    return true;
+
+  // Check for recurrsion which can be caused by additional constraints, e.g.,
+  // non-finitie loop contraints. In such a case we have to bail out and insert
+  // a "false" runtime check that will cause the original code to be executed.
+  if (!PreloadedPtrs.insert(std::get<0>(IAClass)).second)
+    return false;
 
   // If the base pointer of this class is dependent on another one we have to
   // make sure it was preloaded already.
   auto *SAI = S.getScopArrayInfo(MA->getBaseAddr());
   if (const auto *BaseIAClass = S.lookupInvariantEquivClass(SAI->getBasePtr()))
-    preloadInvariantEquivClass(*BaseIAClass);
+    if (!preloadInvariantEquivClass(*BaseIAClass))
+      return false;
 
   Instruction *AccInst = MA->getAccessInstruction();
   Type *AccInstTy = AccInst->getType();
 
   isl_set *Domain = isl_set_copy(std::get<2>(IAClass));
   Value *PreloadVal = preloadInvariantLoad(*MA, Domain);
+  if (!PreloadVal)
+    return false;
+
   assert(PreloadVal->getType() == AccInst->getType());
   for (const MemoryAccess *MA : MAs) {
     Instruction *MAAccInst = MA->getAccessInstruction();
@@ -999,13 +1027,15 @@ void IslNodeBuilder::preloadInvariantEquivClass(
     EscapeMap[MA->getAccessInstruction()] =
         std::make_pair(Alloca, std::move(EscapeUsers));
   }
+
+  return true;
 }
 
-void IslNodeBuilder::preloadInvariantLoads() {
+bool IslNodeBuilder::preloadInvariantLoads() {
 
   const auto &InvariantEquivClasses = S.getInvariantAccesses();
   if (InvariantEquivClasses.empty())
-    return;
+    return true;
 
   BasicBlock *PreLoadBB = SplitBlock(Builder.GetInsertBlock(),
                                      &*Builder.GetInsertPoint(), &DT, &LI);
@@ -1013,7 +1043,10 @@ void IslNodeBuilder::preloadInvariantLoads() {
   Builder.SetInsertPoint(&PreLoadBB->front());
 
   for (const auto &IAClass : InvariantEquivClasses)
-    preloadInvariantEquivClass(IAClass);
+    if (!preloadInvariantEquivClass(IAClass))
+      return false;
+
+  return true;
 }
 
 void IslNodeBuilder::addParameters(__isl_take isl_set *Context) {
diff --git a/polly/test/Isl/CodeGen/stack-overflow-in-load-hoisting.ll b/polly/test/Isl/CodeGen/stack-overflow-in-load-hoisting.ll
new file mode 100644
index 00000000000..9534b7270ea
--- /dev/null
+++ b/polly/test/Isl/CodeGen/stack-overflow-in-load-hoisting.ll
@@ -0,0 +1,73 @@
+; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
+;
+; This caused an infinite recursion during invariant load hoisting at some
+; point. Check it does not and we add a "false" runtime check.
+;
+; CHECK:       polly.preload.begin:
+; CHECK-NEXT:    br i1 false, label %polly.start, label %for.body.14.lr.ph
+;
+target datalayout = "e-m:o-p:32:32-f64:32:64-f80:128-n8:16:32-S128"
+
+%struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573 = type { %struct.AVClass.10.32.868.1198.1286.1308.1566*, %struct.AVFrame.5.27.863.1193.1281.1303.1572*, i32, i32, i32, i32, i32, [4 x i32], [4 x i32], double, %struct.AVRational.0.22.858.1188.1276.1298.1567 }
+%struct.AVClass.10.32.868.1198.1286.1308.1566 = type { i8*, i8* (i8*)*, %struct.AVOption.7.29.865.1195.1283.1305.1563*, i32, i32, i32, i8* (i8*, i8*)*, %struct.AVClass.10.32.868.1198.1286.1308.1566* (%struct.AVClass.10.32.868.1198.1286.1308.1566*)*, i32, i32 (i8*)*, i32 (%struct.AVOptionRanges.9.31.867.1197.1285.1307.1565**, i8*, i8*, i32)* }
+%struct.AVOption.7.29.865.1195.1283.1305.1563 = type { i8*, i8*, i32, i32, %union.anon.6.28.864.1194.1282.1304.1562, double, double, i32, i8* }
+%union.anon.6.28.864.1194.1282.1304.1562 = type { i64 }
+%struct.AVOptionRanges.9.31.867.1197.1285.1307.1565 = type { %struct.AVOptionRange.8.30.866.1196.1284.1306.1564**, i32, i32 }
+%struct.AVOptionRange.8.30.866.1196.1284.1306.1564 = type { i8*, double, double, double, double, i32 }
+%struct.AVFrame.5.27.863.1193.1281.1303.1572 = type { [8 x i8*], [8 x i32], i8**, i32, i32, i32, i32, i32, i32, %struct.AVRational.0.22.858.1188.1276.1298.1567, i64, i64, i64, i32, i32, i32, i8*, [8 x i64], i32, i32, i32, i32, i64, i32, i64, [8 x %struct.AVBufferRef.2.24.860.1190.1278.1300.1569*], %struct.AVBufferRef.2.24.860.1190.1278.1300.1569**, i32, %struct.AVFrameSideData.4.26.862.1192.1280.1302.1571**, i32, i32, i32, i32, i32, i32, i32, i64, i64, i64, %struct.AVDictionary.3.25.861.1191.1279.1301.1570*, i32, i32, i32, i8*, i32, i32, %struct.AVBufferRef.2.24.860.1190.1278.1300.1569* }
+%struct.AVFrameSideData.4.26.862.1192.1280.1302.1571 = type { i32, i8*, i32, %struct.AVDictionary.3.25.861.1191.1279.1301.1570*, %struct.AVBufferRef.2.24.860.1190.1278.1300.1569* }
+%struct.AVDictionary.3.25.861.1191.1279.1301.1570 = type opaque
+%struct.AVBufferRef.2.24.860.1190.1278.1300.1569 = type { %struct.AVBuffer.1.23.859.1189.1277.1299.1568*, i8*, i32 }
+%struct.AVBuffer.1.23.859.1189.1277.1299.1568 = type opaque
+%struct.AVRational.0.22.858.1188.1276.1298.1567 = type { i32, i32 }
+
+; Function Attrs: nounwind ssp
+define void @fade(%struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s) #0 {
+entry:
+  br label %for.cond.12.preheader.lr.ph
+
+for.cond.12.preheader.lr.ph:                      ; preds = %entry
+  %outpicref = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 1
+  %arrayidx2 = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 8, i32 0
+  %tobool = icmp eq i32 0, 0
+  %arrayidx4 = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 8, i32 1
+  %tmp = load i32, i32* %arrayidx4, align 4
+  %tobool5 = icmp eq i32 %tmp, 0
+  %h = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 3
+  %tmp1 = load i32, i32* %h, align 4
+  %cmp.48 = icmp sgt i32 %tmp1, 0
+  %tmp2 = load %struct.AVFrame.5.27.863.1193.1281.1303.1572*, %struct.AVFrame.5.27.863.1193.1281.1303.1572** %outpicref, align 4
+  %arrayidx11 = getelementptr inbounds %struct.AVFrame.5.27.863.1193.1281.1303.1572, %struct.AVFrame.5.27.863.1193.1281.1303.1572* %tmp2, i32 0, i32 0, i32 0
+  %tmp3 = load i8*, i8** %arrayidx11, align 4
+  br label %for.body.14.lr.ph
+
+for.body.14.lr.ph:                                ; preds = %for.end, %for.cond.12.preheader.lr.ph
+  %d.050 = phi i8* [ %tmp3, %for.cond.12.preheader.lr.ph ], [ undef, %for.end ]
+  %w = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 2
+  %tmp4 = load i32, i32* %w, align 4
+  %cmp13.46 = icmp sgt i32 %tmp4, 0
+  br label %for.body.14
+
+for.body.14:                                      ; preds = %for.body.14, %for.body.14.lr.ph
+  %arrayidx30 = getelementptr inbounds i8, i8* %d.050, i32 0
+  store i8 undef, i8* %arrayidx30, align 1
+  %arrayidx54 = getelementptr inbounds %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573, %struct.AudioVectorScopeContext.21.43.879.1209.1297.1319.1573* %s, i32 0, i32 8, i32 2
+  %tmp5 = load i32, i32* %arrayidx54, align 4
+  %add92 = add nuw nsw i32 0, 4
+  %tmp6 = load i32, i32* %w, align 4
+  %mul = shl nsw i32 %tmp6, 2
+  %cmp13 = icmp slt i32 %add92, %mul
+  br i1 %cmp13, label %for.body.14, label %for.end
+
+for.end:                                          ; preds = %for.body.14
+  %inc = add nuw nsw i32 0, 1
+  %tmp7 = load i32, i32* %h, align 4
+  %cmp = icmp slt i32 %inc, %tmp7
+  br i1 %cmp, label %for.body.14.lr.ph, label %if.end.loopexit
+
+if.end.loopexit:                                  ; preds = %for.end
+  br label %if.end
+
+if.end:                                           ; preds = %if.end.loopexit
+  ret void
+}