aboutsummaryrefslogtreecommitdiff
path: root/polly/lib/Pass
diff options
context:
space:
mode:
Diffstat (limited to 'polly/lib/Pass')
-rw-r--r--polly/lib/Pass/PhaseManager.cpp437
-rw-r--r--polly/lib/Pass/PollyFunctionPass.cpp22
-rw-r--r--polly/lib/Pass/PollyModulePass.cpp29
3 files changed, 488 insertions, 0 deletions
diff --git a/polly/lib/Pass/PhaseManager.cpp b/polly/lib/Pass/PhaseManager.cpp
new file mode 100644
index 0000000..330dfe8
--- /dev/null
+++ b/polly/lib/Pass/PhaseManager.cpp
@@ -0,0 +1,437 @@
+//===------ PhaseManager.cpp ------------------------------------*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Pass/PhaseManager.h"
+#include "polly/CodeGen/CodeGeneration.h"
+#include "polly/CodeGen/IslAst.h"
+#include "polly/CodePreparation.h"
+#include "polly/DeLICM.h"
+#include "polly/DeadCodeElimination.h"
+#include "polly/DependenceInfo.h"
+#include "polly/FlattenSchedule.h"
+#include "polly/ForwardOpTree.h"
+#include "polly/JSONExporter.h"
+#include "polly/MaximalStaticExpansion.h"
+#include "polly/PruneUnprofitable.h"
+#include "polly/ScheduleOptimizer.h"
+#include "polly/ScopDetection.h"
+#include "polly/ScopDetectionDiagnostic.h"
+#include "polly/ScopGraphPrinter.h"
+#include "polly/ScopInfo.h"
+#include "polly/Simplify.h"
+#include "polly/Support/PollyDebug.h"
+#include "llvm/ADT/PriorityWorklist.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Module.h"
+
+#define DEBUG_TYPE "polly-pass"
+
+using namespace polly;
+using namespace llvm;
+
+namespace {
+
+/// Recurse through all subregions and all regions and add them to RQ.
+static void addRegionIntoQueue(Region &R, SmallVector<Region *> &RQ) {
+ RQ.push_back(&R);
+ for (const auto &E : R)
+ addRegionIntoQueue(*E, RQ);
+}
+
+/// The phase pipeline of Polly to be embedded into another pass manager than
+/// runs passes on functions.
+///
+/// Polly holds state besides LLVM-IR (RegionInfo and ScopInfo) between phases
+/// that LLVM pass managers do not consider when scheduling analyses and passes.
+/// That is, the ScopInfo must persist between phases that a pass manager must
+/// not invalidate to recompute later.
+class PhaseManager {
+private:
+ Function &F;
+ FunctionAnalysisManager &FAM;
+ PollyPassOptions Opts;
+
+public:
+ PhaseManager(Function &F, FunctionAnalysisManager &FAM, PollyPassOptions Opts)
+ : F(F), FAM(FAM), Opts(std::move(Opts)) {}
+
+ /// Execute Polly's phases as indicated by the options.
+ bool run() {
+ // Get analyses from the function pass manager.
+ // These must be preserved during all phases so that if processing one SCoP
+ // has finished, the next SCoP can still use them. Recomputing is not an
+ // option because ScopDetection stores references to the old results.
+ // TODO: CodePreparation doesn't actually need these analysis, it just keeps
+ // them up-to-date. If they are not computed yet, can also compute after the
+ // prepare phase.
+ LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
+ DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+ bool ModifiedIR = false;
+
+ // Phase: prepare
+ // TODO: Setting ModifiedIR will invalidate any analysis, even if DT, LI are
+ // preserved.
+ if (Opts.isPhaseEnabled(PassPhase::Prepare)) {
+ if (runCodePreparation(F, &DT, &LI, nullptr)) {
+ PreservedAnalyses PA;
+ PA.preserve<DominatorTreeAnalysis>();
+ PA.preserve<LoopAnalysis>();
+ FAM.invalidate(F, PA);
+ ModifiedIR = true;
+ }
+ }
+
+ // Can't do anything without detection
+ if (!Opts.isPhaseEnabled(PassPhase::Detection))
+ return false;
+
+ AAResults &AA = FAM.getResult<AAManager>(F);
+ ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);
+ OptimizationRemarkEmitter &ORE =
+ FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+
+ // ScopDetection is modifying RegionInfo, do not cache it, nor use a cached
+ // version.
+ RegionInfo RI = RegionInfoAnalysis().run(F, FAM);
+
+ // Phase: detection
+ ScopDetection SD(DT, SE, LI, RI, AA, ORE);
+ SD.detect(F);
+ if (Opts.isPhaseEnabled(PassPhase::PrintDetect)) {
+ outs() << "Detected Scops in Function " << F.getName() << "\n";
+ for (const Region *R : SD.ValidRegions)
+ outs() << "Valid Region for Scop: " << R->getNameStr() << '\n';
+ outs() << "\n";
+ }
+
+ if (Opts.isPhaseEnabled(PassPhase::DotScops))
+ printGraphForFunction(F, &SD, "scops", false);
+ if (Opts.isPhaseEnabled(PassPhase::DotScopsOnly))
+ printGraphForFunction(F, &SD, "scopsonly", true);
+
+ auto ViewScops = [&](const char *Name, bool IsSimply) {
+ if (Opts.ViewFilter.empty() && !F.getName().count(Opts.ViewFilter))
+ return;
+
+ if (Opts.ViewAll || std::distance(SD.begin(), SD.end()) > 0)
+ viewGraphForFunction(F, &SD, Name, IsSimply);
+ };
+ if (Opts.isPhaseEnabled(PassPhase::ViewScops))
+ ViewScops("scops", false);
+ if (Opts.isPhaseEnabled(PassPhase::ViewScopsOnly))
+ ViewScops("scopsonly", true);
+
+ // Phase: scops
+ AssumptionCache &AC = FAM.getResult<AssumptionAnalysis>(F);
+ const DataLayout &DL = F.getParent()->getDataLayout();
+ ScopInfo Info(DL, SD, SE, LI, AA, DT, AC, ORE);
+ if (Opts.isPhaseEnabled(PassPhase::PrintScopInfo)) {
+ if (Region *TLR = RI.getTopLevelRegion()) {
+ SmallVector<Region *> Regions;
+ addRegionIntoQueue(*TLR, Regions);
+
+ // reverse iteration because the regression tests expect it.
+ for (Region *R : reverse(Regions)) {
+ Scop *S = Info.getScop(R);
+ outs() << "Printing analysis 'Polly - Create polyhedral "
+ "description of Scops' for region: '"
+ << R->getNameStr() << "' in function '" << F.getName()
+ << "':\n";
+ if (S)
+ outs() << *S;
+ else
+ outs() << "Invalid Scop!\n";
+ }
+ }
+ }
+
+ SmallPriorityWorklist<Region *, 4> Worklist;
+ for (auto &[R, S] : Info)
+ if (S)
+ Worklist.insert(R);
+
+ TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
+ while (!Worklist.empty()) {
+ Region *R = Worklist.pop_back_val();
+ Scop *S = Info.getScop(R);
+ if (!S) {
+ // This can happen if codegenning of a previous SCoP made this region
+ // not-a-SCoP anymore.
+ POLLY_DEBUG(dbgs() << "SCoP in Region '" << *R << "' disappeared");
+ continue;
+ }
+
+ if (!SD.isMaxRegionInScop(*R, /*Verify=*/false))
+ continue;
+
+ // Phase: flatten
+ if (Opts.isPhaseEnabled(PassPhase::Flatten))
+ runFlattenSchedulePass(*S);
+
+ // Phase: deps
+ // Actual analysis runs on-demand, so it does not matter whether the phase
+ // is actually enabled, but use this location to print dependencies.
+ DependenceAnalysis::Result DA = runDependenceAnalysis(*S);
+ if (Opts.isPhaseEnabled(PassPhase::PrintDependences)) {
+ assert(Opts.isPhaseEnabled(PassPhase::Dependences));
+ const Dependences &D = DA.getDependences(Opts.PrintDepsAnalysisLevel);
+ D.print(outs());
+ }
+
+ // Phase: import-jscop
+ if (Opts.isPhaseEnabled(PassPhase::ImportJScop))
+ runImportJSON(*S, DA);
+
+ // Phase: simplify-0
+ bool ModifiedSinceSimplify = true;
+ if (Opts.isPhaseEnabled(PassPhase::Simplify0)) {
+ runSimplify(*S, 0);
+ ModifiedSinceSimplify = false;
+ }
+
+ // Phase: optree
+ if (Opts.isPhaseEnabled(PassPhase::Optree)) {
+ bool ModifiedByOptree = runForwardOpTree(*S);
+ ModifiedSinceSimplify |= ModifiedByOptree;
+ }
+
+ // Phase: delicm
+ if (Opts.isPhaseEnabled(PassPhase::DeLICM)) {
+ bool ModifiedByDelicm = runDeLICM(*S);
+ ModifiedSinceSimplify |= ModifiedByDelicm;
+ }
+
+ // Phase: simplify-1
+ // If we have already run simplify-0, do not re-run it if the SCoP has not
+ // changed since then.
+ if (ModifiedSinceSimplify && Opts.isPhaseEnabled(PassPhase::Simplify1)) {
+ runSimplify(*S, 1);
+ ModifiedSinceSimplify = false;
+ }
+
+ // Phase: dce
+ if (Opts.isPhaseEnabled(PassPhase::DeadCodeElimination))
+ runDeadCodeElim(*S, DA);
+
+ // Phase: mse
+ if (Opts.isPhaseEnabled(PassPhase::MaximumStaticExtension))
+ runMaximalStaticExpansion(*S, DA);
+
+ // Phase: prune
+ if (Opts.isPhaseEnabled(PassPhase::PruneUnprofitable))
+ runPruneUnprofitable(*S);
+
+ // Phase: opt-isl
+ if (Opts.isPhaseEnabled(PassPhase::Optimization))
+ runIslScheduleOptimizer(*S, &TTI, DA);
+
+ // Phase: import-jscop
+ if (Opts.isPhaseEnabled(PassPhase::ExportJScop))
+ runExportJSON(*S);
+
+ // Phase: ast
+ // Cannot run codegen unless ast is enabled
+ if (!Opts.isPhaseEnabled(PassPhase::AstGen))
+ continue;
+ std::unique_ptr<IslAstInfo> IslAst = runIslAstGen(*S, DA);
+
+ // Phase: codegen
+ if (!Opts.isPhaseEnabled(PassPhase::CodeGen))
+ continue;
+ bool ModifiedByCodeGen = runCodeGeneration(*S, RI, *IslAst);
+ if (ModifiedByCodeGen) {
+ ModifiedIR = true;
+
+ // For all regions, create new polly::Scop objects because the old ones
+ // refere to invalidated LLVM-IR.
+ // FIXME: Adds all SCoPs again to statistics
+ Info.recompute();
+ }
+ }
+
+ return ModifiedIR;
+ }
+};
+} // namespace
+
+StringRef polly::getPhaseName(PassPhase Phase) {
+ switch (Phase) {
+ case PassPhase::Prepare:
+ return "prepare";
+ case PassPhase::Detection:
+ return "detect";
+ case PassPhase::PrintDetect:
+ return "print-detect";
+ case PassPhase::DotScops:
+ return "dot-scops";
+ case PassPhase::DotScopsOnly:
+ return "dot-scops-only";
+ case PassPhase::ViewScops:
+ return "view-scops";
+ case PassPhase::ViewScopsOnly:
+ return "view-scops-only";
+ case PassPhase::ScopInfo:
+ return "scops";
+ case PassPhase::PrintScopInfo:
+ return "print-scops";
+ case PassPhase::Flatten:
+ return "flatten";
+ case PassPhase::Dependences:
+ return "deps";
+ case PassPhase::PrintDependences:
+ return "print-deps";
+ case PassPhase::ImportJScop:
+ return "import-jscop";
+ case PassPhase::Simplify0:
+ return "simplify-0";
+ case PassPhase::Optree:
+ return "optree";
+ case PassPhase::DeLICM:
+ return "delicm";
+ case PassPhase::Simplify1:
+ return "simplify-1";
+ case PassPhase::DeadCodeElimination:
+ return "dce";
+ case PassPhase::MaximumStaticExtension:
+ return "mse";
+ case PassPhase::PruneUnprofitable:
+ return "prune";
+ case PassPhase::Optimization:
+ return "opt-isl"; // "opt" would conflict with the llvm executable
+ case PassPhase::ExportJScop:
+ return "export-jscop";
+ case PassPhase::AstGen:
+ return "ast";
+ case PassPhase::CodeGen:
+ return "codegen";
+ default:
+ llvm_unreachable("Unexpected phase");
+ }
+}
+
+PassPhase polly::parsePhase(StringRef Name) {
+ return StringSwitch<PassPhase>(Name)
+ .Case("prepare", PassPhase::Prepare)
+ .Case("detect", PassPhase::Detection)
+ .Case("print-detect", PassPhase::PrintDetect)
+ .Case("dot-scops", PassPhase::DotScops)
+ .Case("dot-scops-only", PassPhase::DotScopsOnly)
+ .Case("view-scops", PassPhase::ViewScops)
+ .Case("view-scops-only", PassPhase::ViewScopsOnly)
+ .Case("scops", PassPhase::ScopInfo)
+ .Case("print-scops", PassPhase::PrintScopInfo)
+ .Case("flatten", PassPhase::Flatten)
+ .Case("deps", PassPhase::Dependences)
+ .Case("print-deps", PassPhase::PrintDependences)
+ .Case("import-jscop", PassPhase::ImportJScop)
+ .Case("simplify-0", PassPhase::Simplify0)
+ .Case("optree", PassPhase::Optree)
+ .Case("delicm", PassPhase::DeLICM)
+ .Case("simplify-1", PassPhase::Simplify1)
+ .Case("dce", PassPhase::DeadCodeElimination)
+ .Case("mse", PassPhase::MaximumStaticExtension)
+ .Case("prune", PassPhase::PruneUnprofitable)
+ .Case("opt-isl", PassPhase::Optimization)
+ .Case("export-jscop", PassPhase::ExportJScop)
+ .Case("ast", PassPhase::AstGen)
+ .Case("codegen", PassPhase::CodeGen)
+ .Default(PassPhase::None);
+}
+
+bool polly::dependsOnDependenceInfo(PassPhase Phase) {
+ // Nothing before dep phase can depend on it
+ if (static_cast<size_t>(Phase) <= static_cast<size_t>(PassPhase::Dependences))
+ return false;
+
+ switch (Phase) {
+ case PassPhase::Simplify0:
+ case PassPhase::Optree:
+ case PassPhase::DeLICM:
+ case PassPhase::Simplify1:
+ case PassPhase::PruneUnprofitable:
+ case PassPhase::ImportJScop:
+ case PassPhase::ExportJScop:
+ case PassPhase::AstGen: // transitively through codegen
+ case PassPhase::CodeGen:
+ return false;
+ default:
+ return true;
+ }
+}
+
+void PollyPassOptions::enableEnd2End() {
+ setPhaseEnabled(PassPhase::Detection);
+ setPhaseEnabled(PassPhase::ScopInfo);
+ setPhaseEnabled(PassPhase::Dependences);
+ setPhaseEnabled(PassPhase::AstGen);
+ setPhaseEnabled(PassPhase::CodeGen);
+}
+
+void PollyPassOptions::enableDefaultOpts() {
+ setPhaseEnabled(PassPhase::Prepare);
+ setPhaseEnabled(PassPhase::Simplify0);
+ setPhaseEnabled(PassPhase::Optree);
+ setPhaseEnabled(PassPhase::DeLICM);
+ setPhaseEnabled(PassPhase::Simplify1);
+ setPhaseEnabled(PassPhase::PruneUnprofitable);
+ setPhaseEnabled(PassPhase::Optimization);
+}
+
+void PollyPassOptions::disableAfter(PassPhase Phase) {
+ assert(Phase != PassPhase::None);
+ for (PassPhase P : enum_seq_inclusive(Phase, PassPhase::PassPhaseLast)) {
+ if (P == Phase)
+ continue;
+ setPhaseEnabled(P, false);
+ }
+}
+
+Error PollyPassOptions::checkConsistency() const {
+ for (PassPhase P : enum_seq_inclusive(PassPhase::PassPhaseFirst,
+ PassPhase::PassPhaseLast)) {
+ if (!isPhaseEnabled(P))
+ continue;
+
+ // Prepare and Detection have no requirements
+ if (P == PassPhase::Prepare || P == PassPhase::Detection)
+ continue;
+
+ if (!isPhaseEnabled(PassPhase::Detection))
+ return make_error<StringError>(
+ formatv("'{0}' requires 'detect' to be enabled", getPhaseName(P))
+ .str(),
+ inconvertibleErrorCode());
+
+ if (static_cast<size_t>(P) < static_cast<size_t>(PassPhase::ScopInfo))
+ continue;
+
+ if (!isPhaseEnabled(PassPhase::ScopInfo))
+ return make_error<StringError>(
+ formatv("'{0}' requires 'scops' to be enabled", getPhaseName(P))
+ .str(),
+ inconvertibleErrorCode());
+
+ if (dependsOnDependenceInfo(P) && !isPhaseEnabled(PassPhase::Dependences))
+ return make_error<StringError>(
+ formatv("'{0}' requires 'deps' to be enabled", getPhaseName(P)).str(),
+ inconvertibleErrorCode());
+ }
+
+ if (isPhaseEnabled(PassPhase::CodeGen) && !isPhaseEnabled(PassPhase::AstGen))
+ return make_error<StringError>("'codegen' requires 'ast' to be enabled",
+ inconvertibleErrorCode());
+
+ return Error::success();
+}
+
+bool polly::runPollyPass(Function &F, FunctionAnalysisManager &FAM,
+ PollyPassOptions Opts) {
+ return PhaseManager(F, FAM, std::move(Opts)).run();
+}
diff --git a/polly/lib/Pass/PollyFunctionPass.cpp b/polly/lib/Pass/PollyFunctionPass.cpp
new file mode 100644
index 0000000..a478e4d
--- /dev/null
+++ b/polly/lib/Pass/PollyFunctionPass.cpp
@@ -0,0 +1,22 @@
+//===------ PollyFunctionPass.cpp - Polly function pass ------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Pass/PollyFunctionPass.h"
+
+using namespace llvm;
+using namespace polly;
+
+PreservedAnalyses PollyFunctionPass::run(llvm::Function &F,
+ llvm::FunctionAnalysisManager &FAM) {
+ bool ModifiedIR = runPollyPass(F, FAM, Opts);
+
+ // Be conservative about preserved analyses.
+ // FIXME: May also need to invalidate/update Module/CGSCC passes, but cannot
+ // reach them within a FunctionPassManager.
+ return ModifiedIR ? PreservedAnalyses::none() : PreservedAnalyses::all();
+}
diff --git a/polly/lib/Pass/PollyModulePass.cpp b/polly/lib/Pass/PollyModulePass.cpp
new file mode 100644
index 0000000..f56ee67
--- /dev/null
+++ b/polly/lib/Pass/PollyModulePass.cpp
@@ -0,0 +1,29 @@
+//===------ PollyModulePass.cpp - Polly module pass ----------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "polly/Pass/PollyModulePass.h"
+#include "llvm/IR/Module.h"
+
+using namespace llvm;
+using namespace polly;
+
+PreservedAnalyses PollyModulePass::run(llvm::Module &M,
+ llvm::ModuleAnalysisManager &MAM) {
+ FunctionAnalysisManager &FAM =
+ MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+
+ bool ModifiedAnyIR = false;
+ for (Function &F : M) {
+ bool LocalModifiedIR = runPollyPass(F, FAM, Opts);
+ ModifiedAnyIR |= LocalModifiedIR;
+ }
+
+ // Be conservative about preserved analyses, especially if parallel functions
+ // have been outlined.
+ return ModifiedAnyIR ? PreservedAnalyses::none() : PreservedAnalyses::all();
+}
generated by cgit v1.1 at 2026-01-06 08:34:04 +0000