438 lines · cpp
1//===------ PhaseManager.cpp ------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "polly/Pass/PhaseManager.h"10#include "polly/CodeGen/CodeGeneration.h"11#include "polly/CodeGen/IslAst.h"12#include "polly/CodePreparation.h"13#include "polly/DeLICM.h"14#include "polly/DeadCodeElimination.h"15#include "polly/DependenceInfo.h"16#include "polly/FlattenSchedule.h"17#include "polly/ForwardOpTree.h"18#include "polly/JSONExporter.h"19#include "polly/MaximalStaticExpansion.h"20#include "polly/PruneUnprofitable.h"21#include "polly/ScheduleOptimizer.h"22#include "polly/ScopDetection.h"23#include "polly/ScopDetectionDiagnostic.h"24#include "polly/ScopGraphPrinter.h"25#include "polly/ScopInfo.h"26#include "polly/Simplify.h"27#include "polly/Support/PollyDebug.h"28#include "llvm/ADT/PriorityWorklist.h"29#include "llvm/Analysis/AssumptionCache.h"30#include "llvm/Analysis/OptimizationRemarkEmitter.h"31#include "llvm/Analysis/TargetTransformInfo.h"32#include "llvm/IR/Module.h"33 34#define DEBUG_TYPE "polly-pass"35 36using namespace polly;37using namespace llvm;38 39namespace {40 41/// Recurse through all subregions and all regions and add them to RQ.42static void addRegionIntoQueue(Region &R, SmallVector<Region *> &RQ) {43 RQ.push_back(&R);44 for (const auto &E : R)45 addRegionIntoQueue(*E, RQ);46}47 48/// The phase pipeline of Polly to be embedded into another pass manager than49/// runs passes on functions.50///51/// Polly holds state besides LLVM-IR (RegionInfo and ScopInfo) between phases52/// that LLVM pass managers do not consider when scheduling analyses and passes.53/// That is, the ScopInfo must persist between phases that a pass manager must54/// not invalidate to recompute later.55class PhaseManager {56private:57 Function &F;58 FunctionAnalysisManager &FAM;59 PollyPassOptions Opts;60 61public:62 PhaseManager(Function &F, FunctionAnalysisManager &FAM, PollyPassOptions Opts)63 : F(F), FAM(FAM), Opts(std::move(Opts)) {}64 65 /// Execute Polly's phases as indicated by the options.66 bool run() {67 // Get analyses from the function pass manager.68 // These must be preserved during all phases so that if processing one SCoP69 // has finished, the next SCoP can still use them. Recomputing is not an70 // option because ScopDetection stores references to the old results.71 // TODO: CodePreparation doesn't actually need these analysis, it just keeps72 // them up-to-date. If they are not computed yet, can also compute after the73 // prepare phase.74 LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);75 DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);76 bool ModifiedIR = false;77 78 // Phase: prepare79 // TODO: Setting ModifiedIR will invalidate any analysis, even if DT, LI are80 // preserved.81 if (Opts.isPhaseEnabled(PassPhase::Prepare)) {82 if (runCodePreparation(F, &DT, &LI, nullptr)) {83 PreservedAnalyses PA;84 PA.preserve<DominatorTreeAnalysis>();85 PA.preserve<LoopAnalysis>();86 FAM.invalidate(F, PA);87 ModifiedIR = true;88 }89 }90 91 // Can't do anything without detection92 if (!Opts.isPhaseEnabled(PassPhase::Detection))93 return false;94 95 AAResults &AA = FAM.getResult<AAManager>(F);96 ScalarEvolution &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);97 OptimizationRemarkEmitter &ORE =98 FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);99 100 // ScopDetection is modifying RegionInfo, do not cache it, nor use a cached101 // version.102 RegionInfo RI = RegionInfoAnalysis().run(F, FAM);103 104 // Phase: detection105 ScopDetection SD(DT, SE, LI, RI, AA, ORE);106 SD.detect(F);107 if (Opts.isPhaseEnabled(PassPhase::PrintDetect)) {108 outs() << "Detected Scops in Function " << F.getName() << "\n";109 for (const Region *R : SD.ValidRegions)110 outs() << "Valid Region for Scop: " << R->getNameStr() << '\n';111 outs() << "\n";112 }113 114 if (Opts.isPhaseEnabled(PassPhase::DotScops))115 printGraphForFunction(F, &SD, "scops", false);116 if (Opts.isPhaseEnabled(PassPhase::DotScopsOnly))117 printGraphForFunction(F, &SD, "scopsonly", true);118 119 auto ViewScops = [&](const char *Name, bool IsSimply) {120 if (Opts.ViewFilter.empty() && !F.getName().count(Opts.ViewFilter))121 return;122 123 if (Opts.ViewAll || std::distance(SD.begin(), SD.end()) > 0)124 viewGraphForFunction(F, &SD, Name, IsSimply);125 };126 if (Opts.isPhaseEnabled(PassPhase::ViewScops))127 ViewScops("scops", false);128 if (Opts.isPhaseEnabled(PassPhase::ViewScopsOnly))129 ViewScops("scopsonly", true);130 131 // Phase: scops132 AssumptionCache &AC = FAM.getResult<AssumptionAnalysis>(F);133 const DataLayout &DL = F.getParent()->getDataLayout();134 ScopInfo Info(DL, SD, SE, LI, AA, DT, AC, ORE);135 if (Opts.isPhaseEnabled(PassPhase::PrintScopInfo)) {136 if (Region *TLR = RI.getTopLevelRegion()) {137 SmallVector<Region *> Regions;138 addRegionIntoQueue(*TLR, Regions);139 140 // reverse iteration because the regression tests expect it.141 for (Region *R : reverse(Regions)) {142 Scop *S = Info.getScop(R);143 outs() << "Printing analysis 'Polly - Create polyhedral "144 "description of Scops' for region: '"145 << R->getNameStr() << "' in function '" << F.getName()146 << "':\n";147 if (S)148 outs() << *S;149 else150 outs() << "Invalid Scop!\n";151 }152 }153 }154 155 SmallPriorityWorklist<Region *, 4> Worklist;156 for (auto &[R, S] : Info)157 if (S)158 Worklist.insert(R);159 160 TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);161 while (!Worklist.empty()) {162 Region *R = Worklist.pop_back_val();163 Scop *S = Info.getScop(R);164 if (!S) {165 // This can happen if codegenning of a previous SCoP made this region166 // not-a-SCoP anymore.167 POLLY_DEBUG(dbgs() << "SCoP in Region '" << *R << "' disappeared");168 continue;169 }170 171 if (!SD.isMaxRegionInScop(*R, /*Verify=*/false))172 continue;173 174 // Phase: flatten175 if (Opts.isPhaseEnabled(PassPhase::Flatten))176 runFlattenSchedulePass(*S);177 178 // Phase: deps179 // Actual analysis runs on-demand, so it does not matter whether the phase180 // is actually enabled, but use this location to print dependencies.181 DependenceAnalysis::Result DA = runDependenceAnalysis(*S);182 if (Opts.isPhaseEnabled(PassPhase::PrintDependences)) {183 assert(Opts.isPhaseEnabled(PassPhase::Dependences));184 const Dependences &D = DA.getDependences(Opts.PrintDepsAnalysisLevel);185 D.print(outs());186 }187 188 // Phase: import-jscop189 if (Opts.isPhaseEnabled(PassPhase::ImportJScop))190 runImportJSON(*S, DA);191 192 // Phase: simplify-0193 bool ModifiedSinceSimplify = true;194 if (Opts.isPhaseEnabled(PassPhase::Simplify0)) {195 runSimplify(*S, 0);196 ModifiedSinceSimplify = false;197 }198 199 // Phase: optree200 if (Opts.isPhaseEnabled(PassPhase::Optree)) {201 bool ModifiedByOptree = runForwardOpTree(*S);202 ModifiedSinceSimplify |= ModifiedByOptree;203 }204 205 // Phase: delicm206 if (Opts.isPhaseEnabled(PassPhase::DeLICM)) {207 bool ModifiedByDelicm = runDeLICM(*S);208 ModifiedSinceSimplify |= ModifiedByDelicm;209 }210 211 // Phase: simplify-1212 // If we have already run simplify-0, do not re-run it if the SCoP has not213 // changed since then.214 if (ModifiedSinceSimplify && Opts.isPhaseEnabled(PassPhase::Simplify1)) {215 runSimplify(*S, 1);216 ModifiedSinceSimplify = false;217 }218 219 // Phase: dce220 if (Opts.isPhaseEnabled(PassPhase::DeadCodeElimination))221 runDeadCodeElim(*S, DA);222 223 // Phase: mse224 if (Opts.isPhaseEnabled(PassPhase::MaximumStaticExtension))225 runMaximalStaticExpansion(*S, DA);226 227 // Phase: prune228 if (Opts.isPhaseEnabled(PassPhase::PruneUnprofitable))229 runPruneUnprofitable(*S);230 231 // Phase: opt-isl232 if (Opts.isPhaseEnabled(PassPhase::Optimization))233 runIslScheduleOptimizer(*S, &TTI, DA);234 235 // Phase: import-jscop236 if (Opts.isPhaseEnabled(PassPhase::ExportJScop))237 runExportJSON(*S);238 239 // Phase: ast240 // Cannot run codegen unless ast is enabled241 if (!Opts.isPhaseEnabled(PassPhase::AstGen))242 continue;243 std::unique_ptr<IslAstInfo> IslAst = runIslAstGen(*S, DA);244 245 // Phase: codegen246 if (!Opts.isPhaseEnabled(PassPhase::CodeGen))247 continue;248 bool ModifiedByCodeGen = runCodeGeneration(*S, RI, *IslAst);249 if (ModifiedByCodeGen) {250 ModifiedIR = true;251 252 // For all regions, create new polly::Scop objects because the old ones253 // refere to invalidated LLVM-IR.254 // FIXME: Adds all SCoPs again to statistics255 Info.recompute();256 }257 }258 259 return ModifiedIR;260 }261};262} // namespace263 264StringRef polly::getPhaseName(PassPhase Phase) {265 switch (Phase) {266 case PassPhase::Prepare:267 return "prepare";268 case PassPhase::Detection:269 return "detect";270 case PassPhase::PrintDetect:271 return "print-detect";272 case PassPhase::DotScops:273 return "dot-scops";274 case PassPhase::DotScopsOnly:275 return "dot-scops-only";276 case PassPhase::ViewScops:277 return "view-scops";278 case PassPhase::ViewScopsOnly:279 return "view-scops-only";280 case PassPhase::ScopInfo:281 return "scops";282 case PassPhase::PrintScopInfo:283 return "print-scops";284 case PassPhase::Flatten:285 return "flatten";286 case PassPhase::Dependences:287 return "deps";288 case PassPhase::PrintDependences:289 return "print-deps";290 case PassPhase::ImportJScop:291 return "import-jscop";292 case PassPhase::Simplify0:293 return "simplify-0";294 case PassPhase::Optree:295 return "optree";296 case PassPhase::DeLICM:297 return "delicm";298 case PassPhase::Simplify1:299 return "simplify-1";300 case PassPhase::DeadCodeElimination:301 return "dce";302 case PassPhase::MaximumStaticExtension:303 return "mse";304 case PassPhase::PruneUnprofitable:305 return "prune";306 case PassPhase::Optimization:307 return "opt-isl"; // "opt" would conflict with the llvm executable308 case PassPhase::ExportJScop:309 return "export-jscop";310 case PassPhase::AstGen:311 return "ast";312 case PassPhase::CodeGen:313 return "codegen";314 default:315 llvm_unreachable("Unexpected phase");316 }317}318 319PassPhase polly::parsePhase(StringRef Name) {320 return StringSwitch<PassPhase>(Name)321 .Case("prepare", PassPhase::Prepare)322 .Case("detect", PassPhase::Detection)323 .Case("print-detect", PassPhase::PrintDetect)324 .Case("dot-scops", PassPhase::DotScops)325 .Case("dot-scops-only", PassPhase::DotScopsOnly)326 .Case("view-scops", PassPhase::ViewScops)327 .Case("view-scops-only", PassPhase::ViewScopsOnly)328 .Case("scops", PassPhase::ScopInfo)329 .Case("print-scops", PassPhase::PrintScopInfo)330 .Case("flatten", PassPhase::Flatten)331 .Case("deps", PassPhase::Dependences)332 .Case("print-deps", PassPhase::PrintDependences)333 .Case("import-jscop", PassPhase::ImportJScop)334 .Case("simplify-0", PassPhase::Simplify0)335 .Case("optree", PassPhase::Optree)336 .Case("delicm", PassPhase::DeLICM)337 .Case("simplify-1", PassPhase::Simplify1)338 .Case("dce", PassPhase::DeadCodeElimination)339 .Case("mse", PassPhase::MaximumStaticExtension)340 .Case("prune", PassPhase::PruneUnprofitable)341 .Case("opt-isl", PassPhase::Optimization)342 .Case("export-jscop", PassPhase::ExportJScop)343 .Case("ast", PassPhase::AstGen)344 .Case("codegen", PassPhase::CodeGen)345 .Default(PassPhase::None);346}347 348bool polly::dependsOnDependenceInfo(PassPhase Phase) {349 // Nothing before dep phase can depend on it350 if (static_cast<size_t>(Phase) <= static_cast<size_t>(PassPhase::Dependences))351 return false;352 353 switch (Phase) {354 case PassPhase::Simplify0:355 case PassPhase::Optree:356 case PassPhase::DeLICM:357 case PassPhase::Simplify1:358 case PassPhase::PruneUnprofitable:359 case PassPhase::ImportJScop:360 case PassPhase::ExportJScop:361 case PassPhase::AstGen: // transitively through codegen362 case PassPhase::CodeGen:363 return false;364 default:365 return true;366 }367}368 369void PollyPassOptions::enableEnd2End() {370 setPhaseEnabled(PassPhase::Detection);371 setPhaseEnabled(PassPhase::ScopInfo);372 setPhaseEnabled(PassPhase::Dependences);373 setPhaseEnabled(PassPhase::AstGen);374 setPhaseEnabled(PassPhase::CodeGen);375}376 377void PollyPassOptions::enableDefaultOpts() {378 setPhaseEnabled(PassPhase::Prepare);379 setPhaseEnabled(PassPhase::Simplify0);380 setPhaseEnabled(PassPhase::Optree);381 setPhaseEnabled(PassPhase::DeLICM);382 setPhaseEnabled(PassPhase::Simplify1);383 setPhaseEnabled(PassPhase::PruneUnprofitable);384 setPhaseEnabled(PassPhase::Optimization);385}386 387void PollyPassOptions::disableAfter(PassPhase Phase) {388 assert(Phase != PassPhase::None);389 for (PassPhase P : enum_seq_inclusive(Phase, PassPhase::PassPhaseLast)) {390 if (P == Phase)391 continue;392 setPhaseEnabled(P, false);393 }394}395 396Error PollyPassOptions::checkConsistency() const {397 for (PassPhase P : enum_seq_inclusive(PassPhase::PassPhaseFirst,398 PassPhase::PassPhaseLast)) {399 if (!isPhaseEnabled(P))400 continue;401 402 // Prepare and Detection have no requirements403 if (P == PassPhase::Prepare || P == PassPhase::Detection)404 continue;405 406 if (!isPhaseEnabled(PassPhase::Detection))407 return make_error<StringError>(408 formatv("'{0}' requires 'detect' to be enabled", getPhaseName(P))409 .str(),410 inconvertibleErrorCode());411 412 if (static_cast<size_t>(P) < static_cast<size_t>(PassPhase::ScopInfo))413 continue;414 415 if (!isPhaseEnabled(PassPhase::ScopInfo))416 return make_error<StringError>(417 formatv("'{0}' requires 'scops' to be enabled", getPhaseName(P))418 .str(),419 inconvertibleErrorCode());420 421 if (dependsOnDependenceInfo(P) && !isPhaseEnabled(PassPhase::Dependences))422 return make_error<StringError>(423 formatv("'{0}' requires 'deps' to be enabled", getPhaseName(P)).str(),424 inconvertibleErrorCode());425 }426 427 if (isPhaseEnabled(PassPhase::CodeGen) && !isPhaseEnabled(PassPhase::AstGen))428 return make_error<StringError>("'codegen' requires 'ast' to be enabled",429 inconvertibleErrorCode());430 431 return Error::success();432}433 434bool polly::runPollyPass(Function &F, FunctionAnalysisManager &FAM,435 PollyPassOptions Opts) {436 return PhaseManager(F, FAM, std::move(Opts)).run();437}438