summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopBuilder.h8
-rw-r--r--polly/include/polly/ScopInfo.h6
-rw-r--r--polly/lib/Analysis/ScopBuilder.cpp12
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp135
4 files changed, 82 insertions, 79 deletions
diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h
index d8656f1a393..31a64c28814 100644
--- a/polly/include/polly/ScopBuilder.h
+++ b/polly/include/polly/ScopBuilder.h
@@ -55,7 +55,7 @@ class ScopBuilder {
std::unique_ptr<Scop> scop;
// Build the SCoP for Region @p R.
- void buildScop(Region &R);
+ void buildScop(Region &R, AssumptionCache &AC);
/// Try to build a multi-dimensional fixed sized MemoryAccess from the
/// Load/Store instruction.
@@ -241,9 +241,9 @@ class ScopBuilder {
void addPHIReadAccess(PHINode *PHI);
public:
- explicit ScopBuilder(Region *R, AliasAnalysis &AA, const DataLayout &DL,
- DominatorTree &DT, LoopInfo &LI, ScopDetection &SD,
- ScalarEvolution &SE);
+ explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
+ const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
+ ScopDetection &SD, ScalarEvolution &SE);
~ScopBuilder() {}
/// Try to build the Polly IR of static control part on the current
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index d64afe00760..e25c4ed713e 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -33,6 +33,7 @@
using namespace llvm;
namespace llvm {
+class AssumptionCache;
class Loop;
class LoopInfo;
class PHINode;
@@ -1708,7 +1709,8 @@ private:
//@}
/// Initialize this ScopBuilder.
- void init(AliasAnalysis &AA, DominatorTree &DT, LoopInfo &LI);
+ void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
+ LoopInfo &LI);
/// Propagate domains that are known due to graph properties.
///
@@ -1882,7 +1884,7 @@ private:
void buildContext();
/// Add user provided parameter constraints to context (source code).
- void addUserAssumptions(DominatorTree &DT, LoopInfo &LI);
+ void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI);
/// Add user provided parameter constraints to context (command line).
void addUserContext();
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index 47281db54d4..6ca659d8571 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -649,7 +649,7 @@ void ScopBuilder::addPHIReadAccess(PHINode *PHI) {
ArrayRef<const SCEV *>(), MemoryKind::PHI);
}
-void ScopBuilder::buildScop(Region &R) {
+void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
scop.reset(new Scop(R, SE, LI, *SD.getDetectionContext(&R)));
buildStmts(R);
@@ -673,12 +673,12 @@ void ScopBuilder::buildScop(Region &R) {
addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP,
BP->getType(), false, {AF}, {nullptr}, GlobalRead);
- scop->init(AA, DT, LI);
+ scop->init(AA, AC, DT, LI);
}
-ScopBuilder::ScopBuilder(Region *R, AliasAnalysis &AA, const DataLayout &DL,
- DominatorTree &DT, LoopInfo &LI, ScopDetection &SD,
- ScalarEvolution &SE)
+ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
+ const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
+ ScopDetection &SD, ScalarEvolution &SE)
: AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
Function *F = R->getEntry()->getParent();
@@ -688,7 +688,7 @@ ScopBuilder::ScopBuilder(Region *R, AliasAnalysis &AA, const DataLayout &DL,
std::string Msg = "SCoP begins here.";
emitOptimizationRemarkAnalysis(F->getContext(), DEBUG_TYPE, *F, Beg, Msg);
- buildScop(*R);
+ buildScop(*R, AC);
DEBUG(scop->print(dbgs()));
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index dc80dc13848..49c086fabcd 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -29,10 +29,10 @@
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopIterator.h"
@@ -1946,82 +1946,76 @@ bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
return DT.dominates(BB, getEntry());
}
-void Scop::addUserAssumptions(DominatorTree &DT, LoopInfo &LI) {
+void Scop::addUserAssumptions(AssumptionCache &AC, DominatorTree &DT,
+ LoopInfo &LI) {
auto &F = getFunction();
+ for (auto &Assumption : AC.assumptions()) {
+ auto *CI = dyn_cast_or_null<CallInst>(Assumption);
+ if (!CI || CI->getNumArgOperands() != 1)
+ continue;
- // TODO: Walk the DominatorTree from getRegion().getExit() to its root in
- // order to not iterate over blocks we skip anyways.
- for (auto &BB : F) {
- bool InScop = contains(&BB);
- if (!InScop && !isDominatedBy(DT, &BB))
+ bool InScop = contains(CI);
+ if (!InScop && !isDominatedBy(DT, CI->getParent()))
continue;
- for (auto &Assumption : BB) {
- auto *CI = dyn_cast_or_null<IntrinsicInst>(&Assumption);
- if (!CI || CI->getNumArgOperands() != 1 ||
- CI->getIntrinsicID() != Intrinsic::assume)
- continue;
+ auto *L = LI.getLoopFor(CI->getParent());
+ auto *Val = CI->getArgOperand(0);
+ ParameterSetTy DetectedParams;
+ if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
+ emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE, F,
+ CI->getDebugLoc(),
+ "Non-affine user assumption ignored.");
+ continue;
+ }
- auto *L = LI.getLoopFor(CI->getParent());
- auto *Val = CI->getArgOperand(0);
- ParameterSetTy DetectedParams;
- if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
- emitOptimizationRemarkAnalysis(F.getContext(), DEBUG_TYPE, F,
- CI->getDebugLoc(),
- "Non-affine user assumption ignored.");
+ // Collect all newly introduced parameters.
+ ParameterSetTy NewParams;
+ for (auto *Param : DetectedParams) {
+ Param = extractConstantFactor(Param, *SE).second;
+ Param = getRepresentingInvariantLoadSCEV(Param);
+ if (Parameters.count(Param))
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);
- }
+ NewParams.insert(Param);
+ }
- SmallVector<isl_set *, 2> ConditionSets;
- auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
- auto &Stmt = InScop ? *getStmtFor(CI->getParent()) : *Stmts.begin();
- auto *Dom = InScop ? getDomainConditions(&Stmt) : isl_set_copy(Context);
- bool Valid = buildConditionSets(Stmt, Val, TI, L, Dom, ConditionSets);
- isl_set_free(Dom);
+ SmallVector<isl_set *, 2> ConditionSets;
+ auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
+ auto &Stmt = InScop ? *getStmtFor(CI->getParent()) : *Stmts.begin();
+ auto *Dom = InScop ? getDomainConditions(&Stmt) : isl_set_copy(Context);
+ bool Valid = buildConditionSets(Stmt, Val, TI, L, Dom, ConditionSets);
+ isl_set_free(Dom);
- if (!Valid)
- continue;
+ 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]);
- }
+ 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);
+ // 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;
+ if (!NewParams.count(Param))
+ continue;
- AssumptionCtx =
- isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
- }
+ AssumptionCtx =
+ isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
}
-
- emitOptimizationRemarkAnalysis(
- F.getContext(), DEBUG_TYPE, F, CI->getDebugLoc(),
- "Use user assumption: " + stringFromIslObj(AssumptionCtx));
- Context = isl_set_intersect(Context, AssumptionCtx);
}
+
+ emitOptimizationRemarkAnalysis(
+ F.getContext(), DEBUG_TYPE, F, CI->getDebugLoc(),
+ "Use user assumption: " + stringFromIslObj(AssumptionCtx));
+ Context = isl_set_intersect(Context, AssumptionCtx);
}
}
@@ -3363,13 +3357,14 @@ void Scop::finalizeAccesses() {
assumeNoOutOfBounds();
}
-void Scop::init(AliasAnalysis &AA, DominatorTree &DT, LoopInfo &LI) {
+void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
+ LoopInfo &LI) {
buildInvariantEquivalenceClasses();
if (!buildDomains(&R, DT, LI))
return;
- addUserAssumptions(DT, LI);
+ addUserAssumptions(AC, DT, LI);
// Remove empty statements.
// Exit early in case there are no executable statements left in this scop.
@@ -4649,6 +4644,7 @@ void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
AU.addRequiredTransitive<ScopDetection>();
AU.addRequired<AAResultsWrapperPass>();
+ AU.addRequired<AssumptionCacheTracker>();
AU.setPreservesAll();
}
@@ -4683,8 +4679,9 @@ bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) {
auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
auto const &DL = F->getParent()->getDataLayout();
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(*F);
- ScopBuilder SB(R, AA, DL, DT, LI, SD, SE);
+ ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
S = SB.getScop(); // take ownership of scop object
if (S) {
@@ -4711,6 +4708,7 @@ INITIALIZE_PASS_BEGIN(ScopInfoRegionPass, "polly-scops",
"Polly - Create polyhedral description of Scops", false,
false);
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
@@ -4728,6 +4726,7 @@ void ScopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
AU.addRequiredTransitive<ScopDetection>();
AU.addRequired<AAResultsWrapperPass>();
+ AU.addRequired<AssumptionCacheTracker>();
AU.setPreservesAll();
}
@@ -4739,6 +4738,7 @@ bool ScopInfoWrapperPass::runOnFunction(Function &F) {
auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
auto const &DL = F.getParent()->getDataLayout();
auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+ auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
/// Create polyhedral descripton of scops for all the valid regions of a
/// function.
@@ -4747,7 +4747,7 @@ bool ScopInfoWrapperPass::runOnFunction(Function &F) {
if (!SD.isMaxRegionInScop(*R))
continue;
- ScopBuilder SB(R, AA, DL, DT, LI, SD, SE);
+ ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE);
std::unique_ptr<Scop> S = SB.getScop();
if (!S)
continue;
@@ -4779,6 +4779,7 @@ INITIALIZE_PASS_BEGIN(
"Polly - Create polyhedral description of all Scops of a function", false,
false);
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass);
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker);
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
OpenPOWER on IntegriCloud