summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h10
-rw-r--r--polly/include/polly/Support/SCEVAffinator.h3
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp32
-rw-r--r--polly/lib/Support/SCEVAffinator.cpp18
-rw-r--r--polly/test/ScopInfo/non-precise-inv-load-6.ll41
5 files changed, 76 insertions, 28 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 58421b247fd..ba086f8facf 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1267,8 +1267,11 @@ public:
/// @brief Compute the isl representation for the SCEV @p E in this stmt.
///
+ /// @param E The SCEV that should be translated.
+ /// @param NonNegative Flag to indicate the @p E has to be non-negative.
+ ///
/// Note that this function will also adjust the invalid context accordingly.
- __isl_give isl_pw_aff *getPwAff(const SCEV *E);
+ __isl_give isl_pw_aff *getPwAff(const SCEV *E, bool NonNegative = false);
/// @brief Get the loop for a dimension.
///
@@ -2125,15 +2128,18 @@ public:
/// @brief Compute the isl representation for the SCEV @p E
///
+ /// @param E The SCEV that should be translated.
/// @param BB An (optional) basic block in which the isl_pw_aff is computed.
/// SCEVs known to not reference any loops in the SCoP can be
/// passed without a @p BB.
+ /// @param NonNegative Flag to indicate the @p E has to be non-negative.
///
/// Note that this function will always return a valid isl_pw_aff. However, if
/// the translation of @p E was deemed to complex the SCoP is invalidated and
/// a dummy value of appropriate dimension is returned. This allows to bail
/// for complex cases without "error handling code" needed on the users side.
- __isl_give PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr);
+ __isl_give PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr,
+ bool NonNegative = false);
/// @brief Compute the isl representation for the SCEV @p E
///
diff --git a/polly/include/polly/Support/SCEVAffinator.h b/polly/include/polly/Support/SCEVAffinator.h
index 3c7822cf895..864e6f597a0 100644
--- a/polly/include/polly/Support/SCEVAffinator.h
+++ b/polly/include/polly/Support/SCEVAffinator.h
@@ -64,6 +64,9 @@ public:
__isl_give PWACtx getPwAff(const llvm::SCEV *E,
llvm::BasicBlock *BB = nullptr);
+ /// @brief Take the asumption that @p PWAC is non-negative.
+ void takeNonNegativeAssumption(PWACtx &PWAC);
+
/// @brief Check an <nsw> AddRec for the loop @p L is cached.
bool hasNSWAddRecForLoop(llvm::Loop *L) const;
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 2b0c1829507..636eb0786e9 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1045,8 +1045,8 @@ __isl_give isl_map *ScopStmt::getSchedule() const {
return M;
}
-__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E) {
- PWACtx PWAC = getParent()->getPwAff(E, getEntryBlock());
+__isl_give isl_pw_aff *ScopStmt::getPwAff(const SCEV *E, bool NonNegative) {
+ PWACtx PWAC = getParent()->getPwAff(E, getEntryBlock(), NonNegative);
InvalidDomain = isl_set_union(InvalidDomain, PWAC.second);
return PWAC.first;
}
@@ -1315,20 +1315,12 @@ buildConditionSets(ScopStmt &Stmt, Value *Condition, TerminatorInst *TI,
ScalarEvolution &SE = *S.getSE();
isl_pw_aff *LHS, *RHS;
- LHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L));
- RHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L));
-
- if (ICond->isUnsigned()) {
- // For unsigned comparisons we assumed the signed bit of neither operand
- // to be set. The comparison is equal to a signed comparison under this
- // assumption.
- auto *BB = Stmt.getEntryBlock();
- S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(LHS)),
- TI->getDebugLoc(), AS_ASSUMPTION, BB);
- S.recordAssumption(UNSIGNED, isl_pw_aff_nonneg_set(isl_pw_aff_copy(RHS)),
- TI->getDebugLoc(), AS_ASSUMPTION, BB);
- }
-
+ // For unsigned comparisons we assumed the signed bit of neither operand
+ // to be set. The comparison is equal to a signed comparison under this
+ // assumption.
+ bool NonNeg = ICond->isUnsigned();
+ LHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), NonNeg);
+ RHS = Stmt.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), NonNeg);
ConsequenceCondSet =
buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
}
@@ -3789,15 +3781,19 @@ void Scop::dump() const { print(dbgs()); }
isl_ctx *Scop::getIslCtx() const { return IslCtx.get(); }
-__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB) {
+__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
+ bool NonNegative) {
// First try to use the SCEVAffinator to generate a piecewise defined
// affine function from @p E in the context of @p BB. If that tasks becomes to
// complex the affinator might return a nullptr. In such a case we invalidate
// the SCoP and return a dummy value. This way we do not need to add error
// handling cdoe to all users of this function.
auto PWAC = Affinator.getPwAff(E, BB);
- if (PWAC.first)
+ if (PWAC.first) {
+ if (NonNegative)
+ Affinator.takeNonNegativeAssumption(PWAC);
return PWAC;
+ }
auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
invalidate(COMPLEXITY, DL);
diff --git a/polly/lib/Support/SCEVAffinator.cpp b/polly/lib/Support/SCEVAffinator.cpp
index ed3eb10345e..c1f2023e2b6 100644
--- a/polly/lib/Support/SCEVAffinator.cpp
+++ b/polly/lib/Support/SCEVAffinator.cpp
@@ -119,6 +119,15 @@ SCEVAffinator::~SCEVAffinator() {
freePWACtx(CachedPair.second);
}
+void SCEVAffinator::takeNonNegativeAssumption(PWACtx &PWAC) {
+ auto *NegPWA = isl_pw_aff_neg(isl_pw_aff_copy(PWAC.first));
+ auto *NegDom = isl_pw_aff_pos_set(NegPWA);
+ PWAC.second = isl_set_union(PWAC.second, isl_set_copy(NegDom));
+ auto *Restriction = BB ? NegDom : isl_set_params(NegDom);
+ auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
+ S->recordAssumption(UNSIGNED, Restriction, DL, AS_RESTRICTION, BB);
+}
+
__isl_give PWACtx SCEVAffinator::getPWACtxFromPWA(__isl_take isl_pw_aff *PWA) {
return std::make_pair(
PWA, isl_set_empty(isl_space_set_alloc(Ctx, 0, NumIterators)));
@@ -334,14 +343,7 @@ SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
// If the width is to big we assume the negative part does not occur.
if (!Precise) {
- auto *NegOpPWA = isl_pw_aff_neg(isl_pw_aff_copy(OpPWAC.first));
- auto *NegDom = isl_pw_aff_pos_set(NegOpPWA);
- auto *ExprDomain = BB ? S->getDomainConditions(BB) : nullptr;
- NegDom = ExprDomain ? isl_set_intersect(NegDom, ExprDomain) : NegDom;
- OpPWAC.second = isl_set_union(OpPWAC.second, isl_set_copy(NegDom));
- NegDom = BB ? NegDom : isl_set_params(NegDom);
- auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
- S->recordAssumption(UNSIGNED, NegDom, DL, AS_RESTRICTION, BB);
+ takeNonNegativeAssumption(OpPWAC);
return OpPWAC;
}
diff --git a/polly/test/ScopInfo/non-precise-inv-load-6.ll b/polly/test/ScopInfo/non-precise-inv-load-6.ll
new file mode 100644
index 00000000000..69b2f8e4fd8
--- /dev/null
+++ b/polly/test/ScopInfo/non-precise-inv-load-6.ll
@@ -0,0 +1,41 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+l Check that we model the execution context correctly.
+;
+; void f(unsigned *I, unsigned *A, int c) {
+; for (unsigned i = c; i < 10; i++)
+; A[i] += *I;
+; }
+;
+; CHECK: Invariant Accesses: {
+; CHECK-NEXT: ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT: [c] -> { Stmt_for_body[i0] -> MemRef_I[0] };
+; CHECK-NEXT: Execution Context: [c] -> { : 0 <= c <= 9 }
+; CHECK-NEXT: }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %I, i32* %A, i64 %c) {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %entry
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ %c, %entry ]
+ %exitcond = icmp ult i64 %indvars.iv, 10
+ br i1 %exitcond, label %for.body, label %for.end
+
+for.body: ; preds = %for.cond
+ %tmp = load i32, i32* %I, align 4
+ %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+ %tmp1 = load i32, i32* %arrayidx, align 4
+ %add = add i32 %tmp1, %tmp
+ store i32 %add, i32* %arrayidx, align 4
+ br label %for.inc
+
+for.inc: ; preds = %for.body
+ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+ br label %for.cond
+
+for.end: ; preds = %for.cond
+ ret void
+}
OpenPOWER on IntegriCloud