//===- DependenceInfo.cpp - Calculate dependency information for a Scop. --===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // Calculate the data dependency relations for a Scop using ISL. // // The integer set library (ISL) from Sven, has a integrated dependency analysis // to calculate data dependences. This pass takes advantage of this and // calculate those dependences a Scop. // // The dependences in this pass are exact in terms that for a specific read // statement instance only the last write statement instance is returned. In // case of may writes a set of possible write instances is returned. This // analysis will never produce redundant dependences. // //===----------------------------------------------------------------------===// // #include "polly/DependenceInfo.h" #include "polly/LinkAllPasses.h" #include "polly/Options.h" #include "polly/ScopInfo.h" #include "polly/Support/GICHelper.h" #include "polly/Support/ISLTools.h" #include "llvm/ADT/Sequence.h" #include "llvm/Support/Debug.h" #include "isl/aff.h" #include "isl/ctx.h" #include "isl/flow.h" #include "isl/map.h" #include "isl/schedule.h" #include "isl/set.h" #include "isl/union_map.h" #include "isl/union_set.h" usingnamespacepolly; usingnamespacellvm; #include "polly/Support/PollyDebug.h" #define DEBUG_TYPE … static cl::opt<int> OptComputeOut( "polly-dependences-computeout", cl::desc("Bound the dependence analysis by a maximal amount of " "computational steps (0 means no bound)"), cl::Hidden, cl::init(500000), cl::cat(PollyCategory)); static cl::opt<bool> LegalityCheckDisabled("disable-polly-legality", cl::desc("Disable polly legality check"), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool> UseReductions("polly-dependences-use-reductions", cl::desc("Exploit reductions in dependence analysis"), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); enum AnalysisType { … }; static cl::opt<enum AnalysisType> OptAnalysisType( "polly-dependences-analysis-type", cl::desc("The kind of dependence analysis to use"), cl::values(clEnumValN(VALUE_BASED_ANALYSIS, "value-based", "Exact dependences without transitive dependences"), clEnumValN(MEMORY_BASED_ANALYSIS, "memory-based", "Overapproximation of dependences")), cl::Hidden, cl::init(VALUE_BASED_ANALYSIS), cl::cat(PollyCategory)); static cl::opt<Dependences::AnalysisLevel> OptAnalysisLevel( "polly-dependences-analysis-level", cl::desc("The level of dependence analysis"), cl::values(clEnumValN(Dependences::AL_Statement, "statement-wise", "Statement-level analysis"), clEnumValN(Dependences::AL_Reference, "reference-wise", "Memory reference level analysis that distinguish" " accessed references in the same statement"), clEnumValN(Dependences::AL_Access, "access-wise", "Memory reference level analysis that distinguish" " access instructions in the same statement")), cl::Hidden, cl::init(Dependences::AL_Statement), cl::cat(PollyCategory)); //===----------------------------------------------------------------------===// /// Tag the @p Relation domain with @p TagId static __isl_give isl_map *tag(__isl_take isl_map *Relation, __isl_take isl_id *TagId) { … } /// Tag the @p Relation domain with either MA->getArrayId() or /// MA->getId() based on @p TagLevel static __isl_give isl_map *tag(__isl_take isl_map *Relation, MemoryAccess *MA, Dependences::AnalysisLevel TagLevel) { … } /// Collect information about the SCoP @p S. static void collectInfo(Scop &S, isl_union_map *&Read, isl_union_map *&MustWrite, isl_union_map *&MayWrite, isl_union_map *&ReductionTagMap, isl_union_set *&TaggedStmtDomain, Dependences::AnalysisLevel Level) { … } /// Fix all dimension of @p Zero to 0 and add it to @p user static void fixSetToZero(isl::set Zero, isl::union_set *User) { … } /// Compute the privatization dependences for a given dependency @p Map /// /// Privatization dependences are widened original dependences which originate /// or end in a reduction access. To compute them we apply the transitive close /// of the reduction dependences (which maps each iteration of a reduction /// statement to all following ones) on the RAW/WAR/WAW dependences. The /// dependences which start or end at a reduction statement will be extended to /// depend on all following reduction statement iterations as well. /// Note: "Following" here means according to the reduction dependences. /// /// For the input: /// /// S0: *sum = 0; /// for (int i = 0; i < 1024; i++) /// S1: *sum += i; /// S2: *sum = *sum * 3; /// /// we have the following dependences before we add privatization dependences: /// /// RAW: /// { S0[] -> S1[0]; S1[1023] -> S2[] } /// WAR: /// { } /// WAW: /// { S0[] -> S1[0]; S1[1024] -> S2[] } /// RED: /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 } /// /// and afterwards: /// /// RAW: /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} /// WAR: /// { } /// WAW: /// { S0[] -> S1[i0] : i0 >= 0 and i0 <= 1023; /// S1[i0] -> S2[] : i0 >= 0 and i0 <= 1023} /// RED: /// { S1[i0] -> S1[1 + i0] : i0 >= 0 and i0 <= 1022 } /// /// Note: This function also computes the (reverse) transitive closure of the /// reduction dependences. void Dependences::addPrivatizationDependences() { … } static __isl_give isl_union_flow *buildFlow(__isl_keep isl_union_map *Snk, __isl_keep isl_union_map *Src, __isl_keep isl_union_map *MaySrc, __isl_keep isl_union_map *Kill, __isl_keep isl_schedule *Schedule) { … } void Dependences::calculateDependences(Scop &S) { … } bool Dependences::isValidSchedule(Scop &S, isl::schedule NewSched) const { … } bool Dependences::isValidSchedule( Scop &S, const StatementToIslMapTy &NewSchedule) const { … } // Check if the current scheduling dimension is parallel. // // We check for parallelism by verifying that the loop does not carry any // dependences. // // Parallelism test: if the distance is zero in all outer dimensions, then it // has to be zero in the current dimension as well. // // Implementation: first, translate dependences into time space, then force // outer dimensions to be equal. If the distance is zero in the current // 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 Dependences::isParallel(__isl_keep isl_union_map *Schedule, __isl_take isl_union_map *Deps, __isl_give isl_pw_aff **MinDistancePtr) const { … } static void printDependencyMap(raw_ostream &OS, __isl_keep isl_union_map *DM) { … } void Dependences::print(raw_ostream &OS) const { … } void Dependences::dump() const { … } void Dependences::releaseMemory() { … } isl::union_map Dependences::getDependences(int Kinds) const { … } bool Dependences::hasValidDependences() const { … } __isl_give isl_map * Dependences::getReductionDependences(MemoryAccess *MA) const { … } void Dependences::setReductionDependences(MemoryAccess *MA, __isl_take isl_map *D) { … } const Dependences & DependenceAnalysis::Result::getDependences(Dependences::AnalysisLevel Level) { … } const Dependences &DependenceAnalysis::Result::recomputeDependences( Dependences::AnalysisLevel Level) { … } void DependenceAnalysis::Result::abandonDependences() { … } DependenceAnalysis::Result DependenceAnalysis::run(Scop &S, ScopAnalysisManager &SAM, ScopStandardAnalysisResults &SAR) { … } AnalysisKey DependenceAnalysis::Key; PreservedAnalyses DependenceInfoPrinterPass::run(Scop &S, ScopAnalysisManager &SAM, ScopStandardAnalysisResults &SAR, SPMUpdater &U) { … } const Dependences & DependenceInfo::getDependences(Dependences::AnalysisLevel Level) { … } const Dependences & DependenceInfo::recomputeDependences(Dependences::AnalysisLevel Level) { … } void DependenceInfo::abandonDependences() { … } bool DependenceInfo::runOnScop(Scop &ScopVar) { … } /// Print the dependences for the given SCoP to @p OS. void polly::DependenceInfo::printScop(raw_ostream &OS, Scop &S) const { … } void DependenceInfo::getAnalysisUsage(AnalysisUsage &AU) const { … } char DependenceInfo::ID = …; Pass *polly::createDependenceInfoPass() { … } INITIALIZE_PASS_BEGIN(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false); INITIALIZE_PASS_DEPENDENCY(ScopInfoRegionPass); INITIALIZE_PASS_END(DependenceInfo, "polly-dependences", "Polly - Calculate dependences", false, false) //===----------------------------------------------------------------------===// namespace { /// Print result from DependenceAnalysis. class DependenceInfoPrinterLegacyPass final : public ScopPass { … }; char DependenceInfoPrinterLegacyPass::ID = …; } // namespace Pass *polly::createDependenceInfoPrinterLegacyPass(raw_ostream &OS) { … } INITIALIZE_PASS_BEGIN(DependenceInfoPrinterLegacyPass, "polly-print-dependences", "Polly - Print dependences", false, false); INITIALIZE_PASS_DEPENDENCY(DependenceInfo); INITIALIZE_PASS_END(DependenceInfoPrinterLegacyPass, "polly-print-dependences", "Polly - Print dependences", false, false) //===----------------------------------------------------------------------===// const Dependences & DependenceInfoWrapperPass::getDependences(Scop *S, Dependences::AnalysisLevel Level) { … } const Dependences &DependenceInfoWrapperPass::recomputeDependences( Scop *S, Dependences::AnalysisLevel Level) { … } bool DependenceInfoWrapperPass::runOnFunction(Function &F) { … } void DependenceInfoWrapperPass::print(raw_ostream &OS, const Module *M) const { … } void DependenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … } char DependenceInfoWrapperPass::ID = …; Pass *polly::createDependenceInfoWrapperPassPass() { … } INITIALIZE_PASS_BEGIN( DependenceInfoWrapperPass, "polly-function-dependences", "Polly - Calculate dependences for all the SCoPs of a function", false, false) INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); INITIALIZE_PASS_END( DependenceInfoWrapperPass, "polly-function-dependences", "Polly - Calculate dependences for all the SCoPs of a function", false, false) //===----------------------------------------------------------------------===// namespace { /// Print result from DependenceInfoWrapperPass. class DependenceInfoPrinterLegacyFunctionPass final : public FunctionPass { … }; char DependenceInfoPrinterLegacyFunctionPass::ID = …; } // namespace Pass *polly::createDependenceInfoPrinterLegacyFunctionPass(raw_ostream &OS) { … } INITIALIZE_PASS_BEGIN( DependenceInfoPrinterLegacyFunctionPass, "polly-print-function-dependences", "Polly - Print dependences for all the SCoPs of a function", false, false); INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass); INITIALIZE_PASS_END(DependenceInfoPrinterLegacyFunctionPass, "polly-print-function-dependences", "Polly - Print dependences for all the SCoPs of a function", false, false)
Codebase Browser
llvm