summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopBuilder.h4
-rw-r--r--polly/include/polly/ScopInfo.h71
-rw-r--r--polly/lib/Analysis/ScopBuilder.cpp79
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp116
4 files changed, 152 insertions, 118 deletions
diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h
index 415190b5dfd..5a525cdc191 100644
--- a/polly/include/polly/ScopBuilder.h
+++ b/polly/include/polly/ScopBuilder.h
@@ -442,6 +442,10 @@ class ScopBuilder {
/// Add user provided parameter constraints to context (command line).
void addUserContext();
+ /// Add user provided parameter constraints to context (source code).
+ void addUserAssumptions(AssumptionCache &AC,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
+
/// Add all recorded assumptions to the assumed context.
void addRecordedAssumptions();
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 9405d8c26c6..b63d271ae16 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1642,6 +1642,44 @@ struct Assumption {
BasicBlock *BB;
};
+/// Build the conditions sets for the branch condition @p Condition in
+/// the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors. If @p TI is nullptr the
+/// context under which @p Condition is true/false will be returned as the
+/// new elements of @p ConditionSets.
+bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+ Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
+/// Build condition sets for unsigned ICmpInst(s).
+/// Special handling is required for unsigned operands to ensure that if
+/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
+/// it should wrap around.
+///
+/// @param IsStrictUpperBound holds information on the predicate relation
+/// between TestVal and UpperBound, i.e,
+/// TestVal < UpperBound OR TestVal <= UpperBound
+__isl_give isl_set *
+buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+ __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
+ const SCEV *SCEV_UpperBound,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ bool IsStrictUpperBound);
+
+/// Build the conditions sets for the terminator @p TI in the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors.
+bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
+ __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
/// Static Control Part
///
/// A Scop is the polyhedral representation of a control flow region detected
@@ -2040,29 +2078,12 @@ private:
/// Build the Context of the Scop.
void buildContext();
- /// Add user provided parameter constraints to context (source code).
- void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
-
/// Add the bounds of the parameters to the context.
void addParameterBounds();
/// Simplify the assumed and invalid context.
void simplifyContexts();
- /// Get the representing SCEV for @p S if applicable, otherwise @p S.
- ///
- /// Invariant loads of the same location are put in an equivalence class and
- /// only one of them is chosen as a representing element that will be
- /// modeled as a parameter. The others have to be normalized, i.e.,
- /// replaced by the representing element of their equivalence class, in order
- /// to get the correct parameter value, e.g., in the SCEVAffinator.
- ///
- /// @param S The SCEV to normalize.
- ///
- /// @return The representing SCEV for invariant loads or @p S if none.
- const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const;
-
/// Create a new SCoP statement for @p BB.
///
/// A new statement for @p BB will be created and added to the statement
@@ -2205,6 +2226,9 @@ public:
/// @return The count of parameters used in this Scop.
size_t getNumParams() const { return Parameters.size(); }
+ /// Return whether given SCEV is used as the parameter in this Scop.
+ bool isParam(const SCEV *Param) const { return Parameters.count(Param); }
+
/// Take a list of parameters and add the new ones to the scop.
void addParams(const ParameterSetTy &NewParameters);
@@ -2769,6 +2793,19 @@ public:
/// statement.
long getNextStmtIdx() { return StmtIdx++; }
+ /// Get the representing SCEV for @p S if applicable, otherwise @p S.
+ ///
+ /// Invariant loads of the same location are put in an equivalence class and
+ /// only one of them is chosen as a representing element that will be
+ /// modeled as a parameter. The others have to be normalized, i.e.,
+ /// replaced by the representing element of their equivalence class, in order
+ /// to get the correct parameter value, e.g., in the SCEVAffinator.
+ ///
+ /// @param S The SCEV to normalize.
+ ///
+ /// @return The representing SCEV for invariant loads or @p S if none.
+ const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const;
+
/// Return the MemoryAccess that writes an llvm::Value, represented by a
/// ScopArrayInfo.
///
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index d301cfe4401..b69239fb102 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -27,6 +27,7 @@
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/OptimizationRemarkEmitter.h"
@@ -621,6 +622,82 @@ void ScopBuilder::addRecordedAssumptions() {
scop->clearRecordedAssumptions();
}
+void ScopBuilder::addUserAssumptions(
+ AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+ for (auto &Assumption : AC.assumptions()) {
+ auto *CI = dyn_cast_or_null<CallInst>(Assumption);
+ if (!CI || CI->getNumArgOperands() != 1)
+ continue;
+
+ bool InScop = scop->contains(CI);
+ if (!InScop && !scop->isDominatedBy(DT, CI->getParent()))
+ continue;
+
+ auto *L = LI.getLoopFor(CI->getParent());
+ auto *Val = CI->getArgOperand(0);
+ ParameterSetTy DetectedParams;
+ auto &R = scop->getRegion();
+ if (!isAffineConstraint(Val, &R, L, SE, DetectedParams)) {
+ ORE.emit(
+ OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
+ << "Non-affine user assumption ignored.");
+ continue;
+ }
+
+ // Collect all newly introduced parameters.
+ ParameterSetTy NewParams;
+ for (auto *Param : DetectedParams) {
+ Param = extractConstantFactor(Param, SE).second;
+ Param = scop->getRepresentingInvariantLoadSCEV(Param);
+ if (scop->isParam(Param))
+ continue;
+ NewParams.insert(Param);
+ }
+
+ SmallVector<isl_set *, 2> ConditionSets;
+ auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
+ BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
+ auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get())
+ : isl_set_copy(scop->getContext().get());
+ assert(Dom && "Cannot propagate a nullptr.");
+ bool Valid = buildConditionSets(*scop, BB, Val, TI, L, Dom,
+ InvalidDomainMap, ConditionSets);
+ isl_set_free(Dom);
+
+ if (!Valid)
+ continue;
+
+ isl_set *AssumptionCtx = nullptr;
+ if (InScop) {
+ AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
+ isl_set_free(ConditionSets[0]);
+ } else {
+ AssumptionCtx = isl_set_complement(ConditionSets[1]);
+ AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
+ }
+
+ // Project out newly introduced parameters as they are not otherwise useful.
+ if (!NewParams.empty()) {
+ for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
+ auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
+ auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
+ isl_id_free(Id);
+
+ if (!NewParams.count(Param))
+ continue;
+
+ AssumptionCtx =
+ isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
+ }
+ }
+ ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
+ << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
+ isl::set newContext =
+ scop->getContext().intersect(isl::manage(AssumptionCtx));
+ scop->setContext(newContext);
+ }
+}
+
bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
Value *Val = Inst.getValueOperand();
Type *ElementType = Val->getType();
@@ -2683,7 +2760,7 @@ void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
return;
}
- scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap);
+ addUserAssumptions(AC, InvalidDomainMap);
// Initialize the invalid domain.
for (ScopStmt &Stmt : scop->Stmts)
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 199729e38e0..f8f215fe003 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1336,12 +1336,11 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
/// @param IsStrictUpperBound holds information on the predicate relation
/// between TestVal and UpperBound, i.e,
/// TestVal < UpperBound OR TestVal <= UpperBound
-__isl_give isl_set *
-buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
- __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
- const SCEV *SCEV_UpperBound,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- bool IsStrictUpperBound) {
+__isl_give isl_set *polly::buildUnsignedConditionSets(
+ Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
+ const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ bool IsStrictUpperBound) {
// Do not take NonNeg assumption on TestVal
// as it might have MSB (Sign bit) set.
isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
@@ -1367,18 +1366,11 @@ buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
return ConsequenceCondSet;
}
-/// Build the conditions sets for the branch condition @p Condition in
-/// the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors. If @p TI is nullptr the
-/// context under which @p Condition is true/false will be returned as the
-/// new elements of @p ConditionSets.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
- Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool polly::buildConditionSets(
+ Scop &S, BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
+ __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
ScalarEvolution &SE = *S.getSE();
isl_set *ConsequenceCondSet = nullptr;
@@ -1511,15 +1503,11 @@ bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
return true;
}
-/// Build the conditions sets for the terminator @p TI in the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool polly::buildConditionSets(
+ Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
+ __isl_keep isl_set *Domain,
+ DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+ SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
ConditionSets);
@@ -1898,79 +1886,6 @@ bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
return DT.dominates(BB, getEntry());
}
-void Scop::addUserAssumptions(
- AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- for (auto &Assumption : AC.assumptions()) {
- auto *CI = dyn_cast_or_null<CallInst>(Assumption);
- if (!CI || CI->getNumArgOperands() != 1)
- continue;
-
- bool InScop = contains(CI);
- if (!InScop && !isDominatedBy(DT, CI->getParent()))
- continue;
-
- auto *L = LI.getLoopFor(CI->getParent());
- auto *Val = CI->getArgOperand(0);
- ParameterSetTy DetectedParams;
- if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
- ORE.emit(
- OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
- << "Non-affine user assumption ignored.");
- continue;
- }
-
- // Collect all newly introduced parameters.
- ParameterSetTy NewParams;
- for (auto *Param : DetectedParams) {
- Param = extractConstantFactor(Param, *SE).second;
- Param = getRepresentingInvariantLoadSCEV(Param);
- if (Parameters.count(Param))
- continue;
- NewParams.insert(Param);
- }
-
- SmallVector<isl_set *, 2> ConditionSets;
- auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
- BasicBlock *BB = InScop ? CI->getParent() : getRegion().getEntry();
- auto *Dom = InScop ? DomainMap[BB].copy() : Context.copy();
- assert(Dom && "Cannot propagate a nullptr.");
- bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom,
- InvalidDomainMap, ConditionSets);
- isl_set_free(Dom);
-
- if (!Valid)
- continue;
-
- isl_set *AssumptionCtx = nullptr;
- if (InScop) {
- AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
- isl_set_free(ConditionSets[0]);
- } else {
- AssumptionCtx = isl_set_complement(ConditionSets[1]);
- AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
- }
-
- // Project out newly introduced parameters as they are not otherwise useful.
- if (!NewParams.empty()) {
- for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
- auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
- auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
- isl_id_free(Id);
-
- if (!NewParams.count(Param))
- continue;
-
- AssumptionCtx =
- isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
- }
- }
- ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
- << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
- Context = Context.intersect(isl::manage(AssumptionCtx));
- }
-}
-
void Scop::buildContext() {
isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
Context = isl::set::universe(Space);
@@ -2902,6 +2817,7 @@ std::pair<std::string, std::string> Scop::getEntryExitStr() const {
}
isl::set Scop::getContext() const { return Context; }
+
isl::space Scop::getParamSpace() const { return getContext().get_space(); }
isl::space Scop::getFullParamSpace() const {
OpenPOWER on IntegriCloud