summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/DependenceInfo.h144
-rw-r--r--polly/lib/Analysis/DependenceInfo.cpp72
-rw-r--r--polly/lib/CodeGen/IslAst.cpp17
-rw-r--r--polly/lib/Exchange/JSONExporter.cpp6
-rw-r--r--polly/lib/Transform/DeadCodeElimination.cpp9
-rw-r--r--polly/lib/Transform/ScheduleOptimizer.cpp22
6 files changed, 155 insertions, 115 deletions
diff --git a/polly/include/polly/DependenceInfo.h b/polly/include/polly/DependenceInfo.h
index 432ba33f0d8..8b93767519e 100644
--- a/polly/include/polly/DependenceInfo.h
+++ b/polly/include/polly/DependenceInfo.h
@@ -25,7 +25,6 @@
#include "polly/ScopPass.h"
-#include <map>
#include "isl/ctx.h"
struct isl_pw_aff;
@@ -43,9 +42,18 @@ class Scop;
class ScopStmt;
class MemoryAccess;
-class DependenceInfo : public ScopPass {
-public:
- static char ID;
+/// @brief The accumulated dependence information for a SCoP.
+///
+/// The dependences struct holds all dependence information we collect and
+/// compute for one SCoP. It also offers an interface that allows users to
+/// query only specific parts.
+struct Dependences {
+
+ /// @brief Map type for reduction dependences.
+ using ReductionDependencesMapTy = DenseMap<MemoryAccess *, isl_map *>;
+
+ /// @brief Map type to associate statements with schedules.
+ using StatementToIslMapTy = DenseMap<ScopStmt *, isl_map *>;
/// @brief The type of the dependences.
///
@@ -75,17 +83,25 @@ public:
TYPE_TC_RED = 1 << 4,
};
- typedef std::map<ScopStmt *, isl_map *> StatementToIslMapTy;
+ /// @brief Get the dependences of type @p Kinds.
+ ///
+ /// @param Kinds This integer defines the different kinds of dependences
+ /// that will be returned. To return more than one kind, the
+ /// different kinds are 'ored' together.
+ __isl_give isl_union_map *getDependences(int Kinds) const;
- DependenceInfo();
+ /// @brief Report if valid dependences are available.
+ bool hasValidDependences() const;
- /// @brief Check if a new scattering is valid.
- ///
- /// @param NewScattering The new scatterings
+ /// @brief Return the reduction dependences caused by @p MA.
///
- /// @return bool True if the new scattering is valid, false it it reverses
- /// dependences.
- bool isValidScattering(StatementToIslMapTy *NewScatterings);
+ /// @return The reduction dependences caused by @p MA or nullptr if none.
+ __isl_give isl_map *getReductionDependences(MemoryAccess *MA) const;
+
+ /// @brief Return all reduction dependences.
+ const ReductionDependencesMapTy &getReductionDependences() const {
+ return ReductionDependences;
+ }
/// @brief Check if a partial schedule is parallel wrt to @p Deps.
///
@@ -99,66 +115,90 @@ public:
/// @p Schedule is valid according to the dependences @p Deps.
bool isParallel(__isl_keep isl_union_map *Schedule,
__isl_take isl_union_map *Deps,
- __isl_give isl_pw_aff **MinDistancePtr = nullptr);
+ __isl_give isl_pw_aff **MinDistancePtr = nullptr) const;
- /// @brief Get the dependences in this Scop.
+ /// @brief Check if a new scattering is valid.
///
- /// @param Kinds This integer defines the different kinds of dependences
- /// that will be returned. To return more than one kind, the
- /// different kinds are 'ored' together.
- isl_union_map *getDependences(int Kinds);
+ /// @param S The current SCoP.
+ /// @param NewScattering The new scatterings
+ ///
+ /// @return bool True if the new scattering is valid, false it it reverses
+ /// dependences.
+ bool isValidScattering(Scop &S, StatementToIslMapTy *NewScatterings) const;
- /// @brief Report if valid dependences are available.
- bool hasValidDependences();
+ /// @brief Print the dependence information stored.
+ void print(llvm::raw_ostream &OS) const;
- /// @brief Return the reduction dependences caused by @p MA.
+ /// @brief Dump the dependence information stored to the dbgs stream.
+ void dump() const;
+
+ /// @brief Allow the DependenceInfo access to private members and methods.
///
- /// @return The reduction dependences caused by @p MA or nullptr if None.
- __isl_give isl_map *getReductionDependences(MemoryAccess *MA);
+ /// To restict access to the internal state only the DependenceInfo class
+ /// is able to call or modify a dependences struct.
+ friend class DependenceInfo;
- /// @brief Return the reduction dependences mapped by the causing @p MA.
- const DenseMap<MemoryAccess *, isl_map *> &getReductionDependences() const {
- return ReductionDependences;
- }
+private:
+ /// @brief Create an empty dependences struct.
+ Dependences()
+ : RAW(nullptr), WAR(nullptr), WAW(nullptr), RED(nullptr),
+ TC_RED(nullptr) {}
- /// @brief Recompute dependences from schedule and memory accesses.
- void recomputeDependences();
+ /// @brief Destructor that will free internal objects.
+ ~Dependences() { releaseMemory(); }
- bool runOnScop(Scop &S) override;
- void printScop(raw_ostream &OS, Scop &S) const override;
- void releaseMemory() override;
- void getAnalysisUsage(AnalysisUsage &AU) const override;
+ /// @brief Calculate and add at the privatization dependences.
+ void addPrivatizationDependences();
-private:
- Scop *S;
+ /// @brief Calculate the dependences for a certain SCoP @p S.
+ void calculateDependences(Scop &S);
+
+ /// @brief Set the reduction dependences for @p MA to @p Deps.
+ void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
- /// @brief The different kinds of dependences we calculate.
+ /// @brief Free the objects associated with this dependences struct.
+ ///
+ /// The dependences struct will again be "empty" afterwards.
+ void releaseMemory();
+
+ /// @brief The different basic kinds of dependences we calculate.
isl_union_map *RAW;
isl_union_map *WAR;
isl_union_map *WAW;
- /// @brief The map of reduction dependences
- isl_union_map *RED = nullptr;
+ /// @brief The special reduction dependences.
+ isl_union_map *RED;
- /// @brief The (reverse) transitive closure of reduction dependences
- isl_union_map *TC_RED = nullptr;
+ /// @brief The (reverse) transitive closure of reduction dependences.
+ isl_union_map *TC_RED;
- /// @brief Map from memory accesses to their reduction dependences.
- DenseMap<MemoryAccess *, isl_map *> ReductionDependences;
+ /// @brief Mapping from memory accesses to their reduction dependences.
+ ReductionDependencesMapTy ReductionDependences;
+};
- /// @brief Collect information about the SCoP.
- void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write,
- isl_union_map **MayWrite, isl_union_map **AccessSchedule,
- isl_union_map **StmtSchedule);
+class DependenceInfo : public ScopPass {
+public:
+ static char ID;
- /// @brief Calculate and add at the privatization dependences
- void addPrivatizationDependences();
+ /// @brief Construct a new DependenceInfo pass.
+ DependenceInfo() : ScopPass(ID) {}
- /// @brief Calculate the dependences for a certain SCoP.
- void calculateDependences(Scop &S);
+ /// @brief Return the dependence information for the current SCoP.
+ const Dependences &getDependences() { return D; }
- /// @brief Set the reduction dependences for @p MA to @p Deps.
- void setReductionDependences(MemoryAccess *MA, __isl_take isl_map *Deps);
+ /// @brief Recompute dependences from schedule and memory accesses.
+ void recomputeDependences();
+
+ bool runOnScop(Scop &S) override;
+ void printScop(raw_ostream &OS, Scop &) const override { D.print(OS); }
+ void releaseMemory() override { D.releaseMemory(); }
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+private:
+ Scop *S;
+
+ /// @brief Dependences struct for the current SCoP.
+ Dependences D;
};
} // End polly namespace.
diff --git a/polly/lib/Analysis/DependenceInfo.cpp b/polly/lib/Analysis/DependenceInfo.cpp
index 8fb79dd6727..f7936c6c87c 100644
--- a/polly/lib/Analysis/DependenceInfo.cpp
+++ b/polly/lib/Analysis/DependenceInfo.cpp
@@ -63,13 +63,12 @@ static cl::opt<enum AnalysisType> OptAnalysisType(
cl::cat(PollyCategory));
//===----------------------------------------------------------------------===//
-DependenceInfo::DependenceInfo() : ScopPass(ID) { RAW = WAR = WAW = nullptr; }
-void DependenceInfo::collectInfo(Scop &S, isl_union_map **Read,
- isl_union_map **Write,
- isl_union_map **MayWrite,
- isl_union_map **AccessSchedule,
- isl_union_map **StmtSchedule) {
+/// @brief Collect information about the SCoP @p S.
+static void collectInfo(Scop &S, isl_union_map **Read, isl_union_map **Write,
+ isl_union_map **MayWrite,
+ isl_union_map **AccessSchedule,
+ isl_union_map **StmtSchedule) {
isl_space *Space = S.getParamSpace();
*Read = isl_union_map_empty(isl_space_copy(Space));
*Write = isl_union_map_empty(isl_space_copy(Space));
@@ -174,7 +173,7 @@ static int fixSetToZero(__isl_take isl_set *Zero, void *user) {
///
/// Note: This function also computes the (reverse) transitive closure of the
/// reduction dependences.
-void DependenceInfo::addPrivatizationDependences() {
+void Dependences::addPrivatizationDependences() {
isl_union_map *PrivRAW, *PrivWAW, *PrivWAR;
// The transitive closure might be over approximated, thus could lead to
@@ -217,7 +216,7 @@ void DependenceInfo::addPrivatizationDependences() {
isl_union_set_free(Universe);
}
-void DependenceInfo::calculateDependences(Scop &S) {
+void Dependences::calculateDependences(Scop &S) {
isl_union_map *Read, *Write, *MayWrite, *AccessSchedule, *StmtSchedule,
*Schedule;
@@ -309,7 +308,7 @@ void DependenceInfo::calculateDependences(Scop &S) {
isl_union_map_domain(StmtSchedule));
DEBUG({
dbgs() << "Wrapped Dependences:\n";
- printScop(dbgs(), S);
+ dump();
dbgs() << "\n";
});
@@ -356,7 +355,7 @@ void DependenceInfo::calculateDependences(Scop &S) {
DEBUG({
dbgs() << "Final Wrapped Dependences:\n";
- printScop(dbgs(), S);
+ dump();
dbgs() << "\n";
});
@@ -404,7 +403,7 @@ void DependenceInfo::calculateDependences(Scop &S) {
DEBUG({
dbgs() << "Zipped Dependences:\n";
- printScop(dbgs(), S);
+ dump();
dbgs() << "\n";
});
@@ -416,7 +415,7 @@ void DependenceInfo::calculateDependences(Scop &S) {
DEBUG({
dbgs() << "Unwrapped Dependences:\n";
- printScop(dbgs(), S);
+ dump();
dbgs() << "\n";
});
@@ -430,23 +429,11 @@ void DependenceInfo::calculateDependences(Scop &S) {
RED = isl_union_map_coalesce(RED);
TC_RED = isl_union_map_coalesce(TC_RED);
- DEBUG(printScop(dbgs(), S));
+ DEBUG(dump());
}
-void DependenceInfo::recomputeDependences() {
- releaseMemory();
- calculateDependences(*S);
-}
-
-bool DependenceInfo::runOnScop(Scop &ScopVar) {
- S = &ScopVar;
- recomputeDependences();
- return false;
-}
-
-bool DependenceInfo::isValidScattering(StatementToIslMapTy *NewScattering) {
- Scop &S = *this->S;
-
+bool Dependences::isValidScattering(Scop &S,
+ StatementToIslMapTy *NewScattering) const {
if (LegalityCheckDisabled)
return true;
@@ -502,8 +489,8 @@ bool DependenceInfo::isValidScattering(StatementToIslMapTy *NewScattering) {
// dimension, then the loop is parallel. The distance is zero in the current
// dimension if it is a subset of a map with equal values for the current
// dimension.
-bool DependenceInfo::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
- isl_pw_aff **MinDistancePtr) {
+bool Dependences::isParallel(isl_union_map *Schedule, isl_union_map *Deps,
+ isl_pw_aff **MinDistancePtr) const {
isl_set *Deltas, *Distance;
isl_map *ScheduleDeps;
unsigned Dimension;
@@ -557,7 +544,7 @@ static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) {
OS << "n/a\n";
}
-void DependenceInfo::printScop(raw_ostream &OS, Scop &) const {
+void Dependences::print(raw_ostream &OS) const {
OS << "\tRAW dependences:\n\t\t";
printDependencyMap(OS, RAW);
OS << "\tWAR dependences:\n\t\t";
@@ -570,7 +557,9 @@ void DependenceInfo::printScop(raw_ostream &OS, Scop &) const {
printDependencyMap(OS, TC_RED);
}
-void DependenceInfo::releaseMemory() {
+void Dependences::dump() const { print(dbgs()); }
+
+void Dependences::releaseMemory() {
isl_union_map_free(RAW);
isl_union_map_free(WAR);
isl_union_map_free(WAW);
@@ -584,7 +573,7 @@ void DependenceInfo::releaseMemory() {
ReductionDependences.clear();
}
-isl_union_map *DependenceInfo::getDependences(int Kinds) {
+isl_union_map *Dependences::getDependences(int Kinds) const {
assert(hasValidDependences() && "No valid dependences available");
isl_space *Space = isl_union_map_get_space(RAW);
isl_union_map *Deps = isl_union_map_empty(Space);
@@ -609,20 +598,31 @@ isl_union_map *DependenceInfo::getDependences(int Kinds) {
return Deps;
}
-bool DependenceInfo::hasValidDependences() {
+bool Dependences::hasValidDependences() const {
return (RAW != nullptr) && (WAR != nullptr) && (WAW != nullptr);
}
-isl_map *DependenceInfo::getReductionDependences(MemoryAccess *MA) {
- return isl_map_copy(ReductionDependences[MA]);
+isl_map *Dependences::getReductionDependences(MemoryAccess *MA) const {
+ return isl_map_copy(ReductionDependences.lookup(MA));
}
-void DependenceInfo::setReductionDependences(MemoryAccess *MA, isl_map *D) {
+void Dependences::setReductionDependences(MemoryAccess *MA, isl_map *D) {
assert(ReductionDependences.count(MA) == 0 &&
"Reduction dependences set twice!");
ReductionDependences[MA] = D;
}
+void DependenceInfo::recomputeDependences() {
+ releaseMemory();
+ D.calculateDependences(*S);
+}
+
+bool DependenceInfo::runOnScop(Scop &ScopVar) {
+ S = &ScopVar;
+ recomputeDependences();
+ return false;
+}
+
void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const {
ScopPass::getAnalysisUsage(AU);
}
diff --git a/polly/lib/CodeGen/IslAst.cpp b/polly/lib/CodeGen/IslAst.cpp
index 666d7fd9158..aa103f65b67 100644
--- a/polly/lib/CodeGen/IslAst.cpp
+++ b/polly/lib/CodeGen/IslAst.cpp
@@ -73,7 +73,7 @@ static cl::opt<bool> NoEarlyExit(
namespace polly {
class IslAst {
public:
- IslAst(Scop *Scop, DependenceInfo &D);
+ IslAst(Scop *Scop, const Dependences &D);
~IslAst();
@@ -111,7 +111,7 @@ struct AstBuildUserInfo {
: Deps(nullptr), InParallelFor(false), LastForNodeId(nullptr) {}
/// @brief The dependence information used for the parallelism check.
- DependenceInfo *Deps;
+ const Dependences *Deps;
/// @brief Flag to indicate that we are inside a parallel for node.
bool InParallelFor;
@@ -197,21 +197,20 @@ static isl_printer *cbPrintFor(__isl_take isl_printer *Printer,
/// we can perform the parallelism check as we are only interested in a zero
/// (or non-zero) dependence distance on the dimension in question.
static bool astScheduleDimIsParallel(__isl_keep isl_ast_build *Build,
- DependenceInfo *D,
+ const Dependences *D,
IslAstUserPayload *NodeInfo) {
if (!D->hasValidDependences())
return false;
isl_union_map *Schedule = isl_ast_build_get_schedule(Build);
- isl_union_map *Deps =
- D->getDependences(DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAW |
- DependenceInfo::TYPE_WAR);
+ isl_union_map *Deps = D->getDependences(
+ Dependences::TYPE_RAW | Dependences::TYPE_WAW | Dependences::TYPE_WAR);
if (!D->isParallel(Schedule, Deps, &NodeInfo->MinimalDependenceDistance) &&
!isl_union_map_free(Schedule))
return false;
- isl_union_map *RedDeps = D->getDependences(DependenceInfo::TYPE_TC_RED);
+ isl_union_map *RedDeps = D->getDependences(Dependences::TYPE_TC_RED);
if (!D->isParallel(Schedule, RedDeps))
NodeInfo->IsReductionParallel = true;
@@ -363,7 +362,7 @@ static bool benefitsFromPolly(Scop *Scop, bool PerformParallelTest) {
return true;
}
-IslAst::IslAst(Scop *Scop, DependenceInfo &D)
+IslAst::IslAst(Scop *Scop, const Dependences &D)
: S(Scop), Root(nullptr), RunCondition(nullptr) {
bool PerformParallelTest = PollyParallel || DetectParallel ||
@@ -428,7 +427,7 @@ bool IslAstInfo::runOnScop(Scop &Scop) {
S = &Scop;
- DependenceInfo &D = getAnalysis<DependenceInfo>();
+ const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
Ast = new IslAst(&Scop, D);
diff --git a/polly/lib/Exchange/JSONExporter.cpp b/polly/lib/Exchange/JSONExporter.cpp
index a7ce4c662a8..9d07250fcea 100644
--- a/polly/lib/Exchange/JSONExporter.cpp
+++ b/polly/lib/Exchange/JSONExporter.cpp
@@ -178,11 +178,11 @@ void JSONImporter::printScop(raw_ostream &OS, Scop &S) const {
OS << "New access function '" << *I << "'detected in JSCOP file\n";
}
-typedef DependenceInfo::StatementToIslMapTy StatementToIslMapTy;
+typedef Dependences::StatementToIslMapTy StatementToIslMapTy;
bool JSONImporter::runOnScop(Scop &S) {
Region &R = S.getRegion();
- DependenceInfo *D = &getAnalysis<DependenceInfo>();
+ const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
const DataLayout &DL = getAnalysis<DataLayoutPass>().getDataLayout();
std::string FileName = ImportDir + "/" + getFileName(S);
@@ -239,7 +239,7 @@ bool JSONImporter::runOnScop(Scop &S) {
index++;
}
- if (!D->isValidScattering(&NewScattering)) {
+ if (!D.isValidScattering(S, &NewScattering)) {
errs() << "JScop file contains a scattering that changes the "
<< "dependences. Use -disable-polly-legality to continue anyways\n";
for (StatementToIslMapTy::iterator SI = NewScattering.begin(),
diff --git a/polly/lib/Transform/DeadCodeElimination.cpp b/polly/lib/Transform/DeadCodeElimination.cpp
index e18fc2c135a..07c7e6cc2f7 100644
--- a/polly/lib/Transform/DeadCodeElimination.cpp
+++ b/polly/lib/Transform/DeadCodeElimination.cpp
@@ -112,14 +112,15 @@ isl_union_set *DeadCodeElim::getLiveOut(Scop &S) {
/// combine a certain number of precise steps with one approximating step that
/// simplifies the life set with an affine hull.
bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
- DependenceInfo *D = &getAnalysis<DependenceInfo>();
+ DependenceInfo &DI = getAnalysis<DependenceInfo>();
+ const Dependences &D = DI.getDependences();
- if (!D->hasValidDependences())
+ if (!D.hasValidDependences())
return false;
isl_union_set *Live = getLiveOut(S);
isl_union_map *Dep =
- D->getDependences(DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_RED);
+ D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_RED);
Dep = isl_union_map_reverse(Dep);
if (PreciseSteps == -1)
@@ -156,7 +157,7 @@ bool DeadCodeElim::eliminateDeadCode(Scop &S, int PreciseSteps) {
// FIXME: We can probably avoid the recomputation of all dependences by
// updating them explicitly.
if (Changed)
- D->recomputeDependences();
+ DI.recomputeDependences();
return Changed;
}
diff --git a/polly/lib/Transform/ScheduleOptimizer.cpp b/polly/lib/Transform/ScheduleOptimizer.cpp
index 20c4f9b1d09..c8585099efa 100644
--- a/polly/lib/Transform/ScheduleOptimizer.cpp
+++ b/polly/lib/Transform/ScheduleOptimizer.cpp
@@ -481,29 +481,29 @@ bool IslScheduleOptimizer::runOnScop(Scop &S) {
return false;
}
- DependenceInfo *D = &getAnalysis<DependenceInfo>();
+ const Dependences &D = getAnalysis<DependenceInfo>().getDependences();
- if (!D->hasValidDependences())
+ if (!D.hasValidDependences())
return false;
isl_schedule_free(LastSchedule);
LastSchedule = nullptr;
// Build input data.
- int ValidityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
- DependenceInfo::TYPE_WAW;
+ int ValidityKinds =
+ Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
int ProximityKinds;
if (OptimizeDeps == "all")
- ProximityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
- DependenceInfo::TYPE_WAW;
+ ProximityKinds =
+ Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
else if (OptimizeDeps == "raw")
- ProximityKinds = DependenceInfo::TYPE_RAW;
+ ProximityKinds = Dependences::TYPE_RAW;
else {
errs() << "Do not know how to optimize for '" << OptimizeDeps << "'"
<< " Falling back to optimizing all dependences.\n";
- ProximityKinds = DependenceInfo::TYPE_RAW | DependenceInfo::TYPE_WAR |
- DependenceInfo::TYPE_WAW;
+ ProximityKinds =
+ Dependences::TYPE_RAW | Dependences::TYPE_WAR | Dependences::TYPE_WAW;
}
isl_union_set *Domain = S.getDomains();
@@ -511,8 +511,8 @@ bool IslScheduleOptimizer::runOnScop(Scop &S) {
if (!Domain)
return false;
- isl_union_map *Validity = D->getDependences(ValidityKinds);
- isl_union_map *Proximity = D->getDependences(ProximityKinds);
+ isl_union_map *Validity = D.getDependences(ValidityKinds);
+ isl_union_map *Proximity = D.getDependences(ProximityKinds);
// Simplify the dependences by removing the constraints introduced by the
// domains. This can speed up the scheduling time significantly, as large
OpenPOWER on IntegriCloud