//===- ScopDetection.cpp - Detect Scops -----------------------------------===// // // 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 // //===----------------------------------------------------------------------===// // // Detect the maximal Scops of a function. // // A static control part (Scop) is a subgraph of the control flow graph (CFG) // that only has statically known control flow and can therefore be described // within the polyhedral model. // // Every Scop fulfills these restrictions: // // * It is a single entry single exit region // // * Only affine linear bounds in the loops // // Every natural loop in a Scop must have a number of loop iterations that can // be described as an affine linear function in surrounding loop iterators or // parameters. (A parameter is a scalar that does not change its value during // execution of the Scop). // // * Only comparisons of affine linear expressions in conditions // // * All loops and conditions perfectly nested // // The control flow needs to be structured such that it could be written using // just 'for' and 'if' statements, without the need for any 'goto', 'break' or // 'continue'. // // * Side effect free functions call // // Function calls and intrinsics that do not have side effects (readnone) // or memory intrinsics (memset, memcpy, memmove) are allowed. // // The Scop detection finds the largest Scops by checking if the largest // region is a Scop. If this is not the case, its canonical subregions are // checked until a region is a Scop. It is now tried to extend this Scop by // creating a larger non canonical region. // //===----------------------------------------------------------------------===// #include "polly/ScopDetection.h" #include "polly/LinkAllPasses.h" #include "polly/Options.h" #include "polly/ScopDetectionDiagnostic.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" #include "polly/Support/ScopLocation.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/DiagnosticPrinter.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/Value.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Regex.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> #include <cassert> #include <memory> #include <stack> #include <string> #include <utility> #include <vector> usingnamespacellvm; usingnamespacepolly; #include "polly/Support/PollyDebug.h" #define DEBUG_TYPE … // This option is set to a very high value, as analyzing such loops increases // compile time on several cases. For experiments that enable this option, // a value of around 40 has been working to avoid run-time regressions with // Polly while still exposing interesting optimization opportunities. static cl::opt<int> ProfitabilityMinPerLoopInstructions( "polly-detect-profitability-min-per-loop-insts", cl::desc("The minimal number of per-loop instructions before a single loop " "region is considered profitable"), cl::Hidden, cl::ValueRequired, cl::init(100000000), cl::cat(PollyCategory)); bool polly::PollyProcessUnprofitable; static cl::opt<bool, true> XPollyProcessUnprofitable( "polly-process-unprofitable", cl::desc( "Process scops that are unlikely to benefit from Polly optimizations."), cl::location(PollyProcessUnprofitable), cl::cat(PollyCategory)); static cl::list<std::string> OnlyFunctions( "polly-only-func", cl::desc("Only run on functions that match a regex. " "Multiple regexes can be comma separated. " "Scop detection will run on all functions that match " "ANY of the regexes provided."), cl::CommaSeparated, cl::cat(PollyCategory)); static cl::list<std::string> IgnoredFunctions( "polly-ignore-func", cl::desc("Ignore functions that match a regex. " "Multiple regexes can be comma separated. " "Scop detection will ignore all functions that match " "ANY of the regexes provided."), cl::CommaSeparated, cl::cat(PollyCategory)); bool polly::PollyAllowFullFunction; static cl::opt<bool, true> XAllowFullFunction("polly-detect-full-functions", cl::desc("Allow the detection of full functions"), cl::location(polly::PollyAllowFullFunction), cl::init(false), cl::cat(PollyCategory)); static cl::opt<std::string> OnlyRegion( "polly-only-region", cl::desc("Only run on certain regions (The provided identifier must " "appear in the name of the region's entry block"), cl::value_desc("identifier"), cl::ValueRequired, cl::init(""), cl::cat(PollyCategory)); static cl::opt<bool> IgnoreAliasing("polly-ignore-aliasing", cl::desc("Ignore possible aliasing of the array bases"), cl::Hidden, cl::cat(PollyCategory)); bool polly::PollyAllowUnsignedOperations; static cl::opt<bool, true> XPollyAllowUnsignedOperations( "polly-allow-unsigned-operations", cl::desc("Allow unsigned operations such as comparisons or zero-extends."), cl::location(PollyAllowUnsignedOperations), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); bool polly::PollyUseRuntimeAliasChecks; static cl::opt<bool, true> XPollyUseRuntimeAliasChecks( "polly-use-runtime-alias-checks", cl::desc("Use runtime alias checks to resolve possible aliasing."), cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<bool> ReportLevel("polly-report", cl::desc("Print information about the activities of Polly"), cl::cat(PollyCategory)); static cl::opt<bool> AllowDifferentTypes( "polly-allow-differing-element-types", cl::desc("Allow different element types for array accesses"), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<bool> AllowNonAffine("polly-allow-nonaffine", cl::desc("Allow non affine access functions in arrays"), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool> AllowModrefCall("polly-allow-modref-calls", cl::desc("Allow functions with known modref behavior"), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool> AllowNonAffineSubRegions( "polly-allow-nonaffine-branches", cl::desc("Allow non affine conditions for branches"), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<bool> AllowNonAffineSubLoops("polly-allow-nonaffine-loops", cl::desc("Allow non affine conditions for loops"), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool, true> TrackFailures("polly-detect-track-failures", cl::desc("Track failure strings in detecting scop regions"), cl::location(PollyTrackFailures), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<bool> KeepGoing("polly-detect-keep-going", cl::desc("Do not fail on the first error."), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool, true> PollyDelinearizeX("polly-delinearize", cl::desc("Delinearize array access functions"), cl::location(PollyDelinearize), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); static cl::opt<bool> VerifyScops("polly-detect-verify", cl::desc("Verify the detected SCoPs after each transformation"), cl::Hidden, cl::cat(PollyCategory)); bool polly::PollyInvariantLoadHoisting; static cl::opt<bool, true> XPollyInvariantLoadHoisting("polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."), cl::location(PollyInvariantLoadHoisting), cl::Hidden, cl::cat(PollyCategory)); static cl::opt<bool> PollyAllowErrorBlocks( "polly-allow-error-blocks", cl::desc("Allow to speculate on the execution of 'error blocks'."), cl::Hidden, cl::init(true), cl::cat(PollyCategory)); /// The minimal trip count under which loops are considered unprofitable. static const unsigned MIN_LOOP_TRIP_COUNT = …; bool polly::PollyTrackFailures = …; bool polly::PollyDelinearize = …; StringRef polly::PollySkipFnAttr = …; //===----------------------------------------------------------------------===// // Statistics. STATISTIC(NumScopRegions, "Number of scops"); STATISTIC(NumLoopsInScop, "Number of loops in scops"); STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0"); STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1"); STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2"); STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3"); STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4"); STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5"); STATISTIC(NumScopsDepthLarger, "Number of scops with maximal loop depth 6 and larger"); STATISTIC(NumProfScopRegions, "Number of scops (profitable scops only)"); STATISTIC(NumLoopsInProfScop, "Number of loops in scops (profitable scops only)"); STATISTIC(NumLoopsOverall, "Number of total loops"); STATISTIC(NumProfScopsDepthZero, "Number of scops with maximal loop depth 0 (profitable scops only)"); STATISTIC(NumProfScopsDepthOne, "Number of scops with maximal loop depth 1 (profitable scops only)"); STATISTIC(NumProfScopsDepthTwo, "Number of scops with maximal loop depth 2 (profitable scops only)"); STATISTIC(NumProfScopsDepthThree, "Number of scops with maximal loop depth 3 (profitable scops only)"); STATISTIC(NumProfScopsDepthFour, "Number of scops with maximal loop depth 4 (profitable scops only)"); STATISTIC(NumProfScopsDepthFive, "Number of scops with maximal loop depth 5 (profitable scops only)"); STATISTIC(NumProfScopsDepthLarger, "Number of scops with maximal loop depth 6 and larger " "(profitable scops only)"); STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops"); STATISTIC(MaxNumLoopsInProfScop, "Maximal number of loops in scops (profitable scops only)"); static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, bool OnlyProfitable); namespace { class DiagnosticScopFound final : public DiagnosticInfo { … }; } // namespace int DiagnosticScopFound::PluginDiagnosticKind = …; void DiagnosticScopFound::print(DiagnosticPrinter &DP) const { … } /// Check if a string matches any regex in a list of regexes. /// @param Str the input string to match against. /// @param RegexList a list of strings that are regular expressions. static bool doesStringMatchAnyRegex(StringRef Str, const cl::list<std::string> &RegexList) { … } //===----------------------------------------------------------------------===// // ScopDetection. ScopDetection::ScopDetection(const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, AAResults &AA, OptimizationRemarkEmitter &ORE) : … { … } void ScopDetection::detect(Function &F) { … } template <class RR, typename... Args> inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert, Args &&...Arguments) const { … } bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) { … } std::string ScopDetection::regionIsInvalidBecause(const Region *R) const { … } bool ScopDetection::addOverApproximatedRegion(Region *AR, DetectionContext &Context) const { … } bool ScopDetection::onlyValidRequiredInvariantLoads( InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const { … } bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const { … } bool ScopDetection::isAffine(const SCEV *S, Loop *Scope, DetectionContext &Context) const { … } bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const { … } bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) { … } bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, DetectionContext &Context) { … } bool ScopDetection::isValidCallInst(CallInst &CI, DetectionContext &Context) const { … } bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const { … } bool ScopDetection::isInvariant(Value &Val, const Region &Reg, DetectionContext &Ctx) const { … } namespace { /// Remove smax of smax(0, size) expressions from a SCEV expression and /// register the '...' components. /// /// Array access expressions as they are generated by GFortran contain smax(0, /// size) expressions that confuse the 'normal' delinearization algorithm. /// However, if we extract such expressions before the normal delinearization /// takes place they can actually help to identify array size expressions in /// Fortran accesses. For the subsequently following delinearization the smax(0, /// size) component can be replaced by just 'size'. This is correct as we will /// always add and verify the assumption that for all subscript expressions /// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify /// that 0 <= size, which means smax(0, size) == size. class SCEVRemoveMax final : public SCEVRewriteVisitor<SCEVRemoveMax> { … }; } // namespace SmallVector<const SCEV *, 4> ScopDetection::getDelinearizationTerms(DetectionContext &Context, const SCEVUnknown *BasePointer) const { … } bool ScopDetection::hasValidArraySizes(DetectionContext &Context, SmallVectorImpl<const SCEV *> &Sizes, const SCEVUnknown *BasePointer, Loop *Scope) const { … } // We first store the resulting memory accesses in TempMemoryAccesses. Only // if the access functions for all memory accesses have been successfully // delinearized we continue. Otherwise, we either report a failure or, if // non-affine accesses are allowed, we drop the information. In case the // information is dropped the memory accesses need to be overapproximated // when translated to a polyhedral representation. bool ScopDetection::computeAccessFunctions( DetectionContext &Context, const SCEVUnknown *BasePointer, std::shared_ptr<ArrayShape> Shape) const { … } bool ScopDetection::hasBaseAffineAccesses(DetectionContext &Context, const SCEVUnknown *BasePointer, Loop *Scope) const { … } bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { … } bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP, DetectionContext &Context) const { … } bool ScopDetection::isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const { … } bool ScopDetection::isValidInstruction(Instruction &Inst, DetectionContext &Context) { … } /// Check whether @p L has exiting blocks. /// /// @param L The loop of interest /// /// @return True if the loop has exiting blocks, false otherwise. static bool hasExitingBlocks(Loop *L) { … } bool ScopDetection::canUseISLTripCount(Loop *L, DetectionContext &Context) { … } bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) { … } /// Return the number of loops in @p L (incl. @p L) that have a trip /// count that is not known to be less than @MinProfitableTrips. ScopDetection::LoopStats ScopDetection::countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, unsigned MinProfitableTrips) { … } ScopDetection::LoopStats ScopDetection::countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI, unsigned MinProfitableTrips) { … } static bool isErrorBlockImpl(BasicBlock &BB, const Region &R, LoopInfo &LI, const DominatorTree &DT) { … } bool ScopDetection::isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R) { … } Region *ScopDetection::expandRegion(Region &R) { … } static bool regionWithoutLoops(Region &R, LoopInfo &LI) { … } void ScopDetection::removeCachedResultsRecursively(const Region &R) { … } void ScopDetection::removeCachedResults(const Region &R) { … } void ScopDetection::findScops(Region &R) { … } bool ScopDetection::allBlocksValid(DetectionContext &Context) { … } bool ScopDetection::hasSufficientCompute(DetectionContext &Context, int NumLoops) const { … } bool ScopDetection::hasPossiblyDistributableLoop( DetectionContext &Context) const { … } bool ScopDetection::isProfitableRegion(DetectionContext &Context) const { … } bool ScopDetection::isValidRegion(DetectionContext &Context) { … } void ScopDetection::markFunctionAsInvalid(Function *F) { … } bool ScopDetection::isValidFunction(Function &F) { … } void ScopDetection::printLocations(Function &F) { … } void ScopDetection::emitMissedRemarks(const Function &F) { … } bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const { … } static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, bool OnlyProfitable) { … } ScopDetection::DetectionContext * ScopDetection::getDetectionContext(const Region *R) const { … } const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const { … } void ScopDetection::verifyRegion(const Region &R) { … } void ScopDetection::verifyAnalysis() { … } bool ScopDetectionWrapperPass::runOnFunction(Function &F) { … } void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { … } void ScopDetectionWrapperPass::print(raw_ostream &OS, const Module *) const { … } ScopDetectionWrapperPass::ScopDetectionWrapperPass() : … { … } ScopAnalysis::ScopAnalysis() { … } void ScopDetectionWrapperPass::releaseMemory() { … } char ScopDetectionWrapperPass::ID; AnalysisKey ScopAnalysis::Key; ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { … } PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F, FunctionAnalysisManager &FAM) { … } Pass *polly::createScopDetectionWrapperPassPass() { … } INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false); INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass); INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false) //===----------------------------------------------------------------------===// namespace { /// Print result from ScopDetectionWrapperPass. class ScopDetectionPrinterLegacyPass final : public FunctionPass { … }; char ScopDetectionPrinterLegacyPass::ID = …; } // namespace Pass *polly::createScopDetectionPrinterLegacyPass(raw_ostream &OS) { … } INITIALIZE_PASS_BEGIN(ScopDetectionPrinterLegacyPass, "polly-print-detect", "Polly - Print static control parts (SCoPs)", false, false); INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_END(ScopDetectionPrinterLegacyPass, "polly-print-detect", "Polly - Print static control parts (SCoPs)", false, false)
Codebase Browser
llvm