summaryrefslogtreecommitdiffstats
path: root/polly
diff options
context:
space:
mode:
Diffstat (limited to 'polly')
-rw-r--r--polly/include/polly/CodeGen/IslNodeBuilder.h17
-rw-r--r--polly/lib/CodeGen/CodeGeneration.cpp9
-rw-r--r--polly/lib/CodeGen/IslExprBuilder.cpp2
-rw-r--r--polly/lib/CodeGen/IslNodeBuilder.cpp125
-rw-r--r--polly/test/Isl/CodeGen/stack-overflow-in-load-hoisting.ll73
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
+}
OpenPOWER on IntegriCloud