Polly 20.0.0git
Macros | Functions | Variables
ScopDetection.cpp File Reference
#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>
#include "polly/Support/PollyDebug.h"

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "polly-detect"
 

Functions

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))
 
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))
 
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))
 
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))
 
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))
 
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))
 
 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)
 
static bool doesStringMatchAnyRegex (StringRef Str, const cl::list< std::string > &RegexList)
 Check if a string matches any regex in a list of regexes.
 
static bool hasExitingBlocks (Loop *L)
 Check whether L has exiting blocks.
 
static bool isErrorBlockImpl (BasicBlock &BB, const Region &R, LoopInfo &LI, const DominatorTree &DT)
 
static bool regionWithoutLoops (Region &R, LoopInfo &LI)
 
 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
 
 INITIALIZE_PASS_BEGIN (ScopDetectionPrinterLegacyPass, "polly-print-detect", "Polly - Print static control parts (SCoPs)", false, false)
 
 INITIALIZE_PASS_DEPENDENCY (ScopDetectionWrapperPass)
 

Variables

static const unsigned MIN_LOOP_TRIP_COUNT = 8
 The minimal trip count under which loops are considered unprofitable.
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "polly-detect"

Definition at line 95 of file ScopDetection.cpp.

Function Documentation

◆ AllowDifferentTypes()

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

◆ AllowModrefCall()

static cl::opt< bool > AllowModrefCall ( "polly-allow-modref-calls"  ,
cl::desc("Allow functions with known modref behavior")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ AllowNonAffine()

static cl::opt< bool > AllowNonAffine ( "polly-allow-nonaffine"  ,
cl::desc("Allow non affine access functions in arrays")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ AllowNonAffineSubLoops()

static cl::opt< bool > AllowNonAffineSubLoops ( "polly-allow-nonaffine-loops"  ,
cl::desc("Allow non affine conditions for loops")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ AllowNonAffineSubRegions()

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

◆ doesStringMatchAnyRegex()

static bool doesStringMatchAnyRegex ( StringRef  Str,
const cl::list< std::string > &  RegexList 
)
static

Check if a string matches any regex in a list of regexes.

Parameters
Strthe input string to match against.
RegexLista list of strings that are regular expressions.

Definition at line 321 of file ScopDetection.cpp.

References Str.

Referenced by polly::ScopDetection::detect().

◆ hasExitingBlocks()

static bool hasExitingBlocks ( Loop *  L)
static

Check whether L has exiting blocks.

Parameters
LThe loop of interest
Returns
True if the loop has exiting blocks, false otherwise.

Definition at line 1270 of file ScopDetection.cpp.

Referenced by polly::ScopDetection::isValidLoop().

◆ IgnoreAliasing()

static cl::opt< bool > IgnoreAliasing ( "polly-ignore-aliasing"  ,
cl::desc("Ignore possible aliasing of the array bases")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ IgnoredFunctions()

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  
)
static

◆ INITIALIZE_PASS_BEGIN() [1/2]

INITIALIZE_PASS_BEGIN ( ScopDetectionPrinterLegacyPass  ,
"polly-print-detect"  ,
"Polly - Print static control parts (SCoPs)"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN ( ScopDetectionWrapperPass  ,
"polly-detect"  ,
"Polly - Detect static control parts (SCoPs)"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_DEPENDENCY() [1/7]

INITIALIZE_PASS_DEPENDENCY ( AAResultsWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [2/7]

INITIALIZE_PASS_DEPENDENCY ( DominatorTreeWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [3/7]

INITIALIZE_PASS_DEPENDENCY ( LoopInfoWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [4/7]

INITIALIZE_PASS_DEPENDENCY ( OptimizationRemarkEmitterWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [5/7]

INITIALIZE_PASS_DEPENDENCY ( RegionInfoPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [6/7]

INITIALIZE_PASS_DEPENDENCY ( ScalarEvolutionWrapperPass  )

◆ INITIALIZE_PASS_DEPENDENCY() [7/7]

INITIALIZE_PASS_DEPENDENCY ( ScopDetectionWrapperPass  )

◆ INITIALIZE_PASS_END()

INITIALIZE_PASS_END ( ScopDetectionWrapperPass  ,
"polly-detect"  ,
"Polly - Detect static control parts (SCoPs)"  ,
false  ,
false   
)

Print result from ScopDetectionWrapperPass.

Definition at line 2069 of file ScopDetection.cpp.

References Function, and polly::ScopDetectionWrapperPass::print().

◆ isErrorBlockImpl()

static bool isErrorBlockImpl ( BasicBlock &  BB,
const Region &  R,
LoopInfo &  LI,
const DominatorTree &  DT 
)
static

◆ KeepGoing()

static cl::opt< bool > KeepGoing ( "polly-detect-keep-going"  ,
cl::desc("Do not fail on the first error.")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ OnlyFunctions()

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

◆ OnlyRegion()

static cl::opt< std::string > OnlyRegion ( "polly-only-region"  )
static

◆ PollyAllowErrorBlocks()

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  
)
static

◆ PollyDelinearizeX()

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

◆ ProfitabilityMinPerLoopInstructions()

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  
)
static

◆ regionWithoutLoops()

static bool regionWithoutLoops ( Region &  R,
LoopInfo &  LI 
)
static

Definition at line 1545 of file ScopDetection.cpp.

Referenced by polly::ScopDetection::findScops().

◆ ReportLevel()

static cl::opt< bool > ReportLevel ( "polly-report"  ,
cl::desc("Print information about the activities of Polly")  ,
cl::cat(PollyCategory  
)
static

◆ STATISTIC() [1/21]

STATISTIC ( MaxNumLoopsInProfScop  ,
"Maximal number of loops in scops (profitable scops only)"   
)

References Function.

◆ STATISTIC() [2/21]

STATISTIC ( MaxNumLoopsInScop  ,
"Maximal number of loops in scops"   
)

◆ STATISTIC() [3/21]

STATISTIC ( NumLoopsInProfScop  ,
"Number of loops in scops (profitable scops only)"   
)

◆ STATISTIC() [4/21]

STATISTIC ( NumLoopsInScop  ,
"Number of loops in scops"   
)

◆ STATISTIC() [5/21]

STATISTIC ( NumLoopsOverall  ,
"Number of total loops"   
)

◆ STATISTIC() [6/21]

STATISTIC ( NumProfScopRegions  ,
"Number of scops (profitable scops only)"   
)

◆ STATISTIC() [7/21]

STATISTIC ( NumProfScopsDepthFive  ,
"Number of scops with maximal loop depth 5 (profitable scops only)"   
)

◆ STATISTIC() [8/21]

STATISTIC ( NumProfScopsDepthFour  ,
"Number of scops with maximal loop depth 4 (profitable scops only)"   
)

◆ STATISTIC() [9/21]

STATISTIC ( NumProfScopsDepthLarger  ,
"Number of scops with maximal loop depth 6 and larger " "(profitable scops only)"   
)

◆ STATISTIC() [10/21]

STATISTIC ( NumProfScopsDepthOne  ,
"Number of scops with maximal loop depth 1 (profitable scops only)"   
)

◆ STATISTIC() [11/21]

STATISTIC ( NumProfScopsDepthThree  ,
"Number of scops with maximal loop depth 3 (profitable scops only)"   
)

◆ STATISTIC() [12/21]

STATISTIC ( NumProfScopsDepthTwo  ,
"Number of scops with maximal loop depth 2 (profitable scops only)"   
)

◆ STATISTIC() [13/21]

STATISTIC ( NumProfScopsDepthZero  ,
"Number of scops with maximal loop depth 0 (profitable scops only)"   
)

◆ STATISTIC() [14/21]

STATISTIC ( NumScopRegions  ,
"Number of scops"   
)

◆ STATISTIC() [15/21]

STATISTIC ( NumScopsDepthFive  ,
"Number of scops with maximal loop depth 5"   
)

◆ STATISTIC() [16/21]

STATISTIC ( NumScopsDepthFour  ,
"Number of scops with maximal loop depth 4"   
)

◆ STATISTIC() [17/21]

STATISTIC ( NumScopsDepthLarger  ,
"Number of scops with maximal loop depth 6 and larger"   
)

◆ STATISTIC() [18/21]

STATISTIC ( NumScopsDepthOne  ,
"Number of scops with maximal loop depth 1"   
)

◆ STATISTIC() [19/21]

STATISTIC ( NumScopsDepthThree  ,
"Number of scops with maximal loop depth 3"   
)

◆ STATISTIC() [20/21]

STATISTIC ( NumScopsDepthTwo  ,
"Number of scops with maximal loop depth 2"   
)

◆ STATISTIC() [21/21]

STATISTIC ( NumScopsDepthZero  ,
"Number of scops with maximal loop depth 0"   
)

◆ TrackFailures()

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

◆ updateLoopCountStatistic()

static void updateLoopCountStatistic ( ScopDetection::LoopStats  Stats,
bool  OnlyProfitable 
)
static

◆ VerifyScops()

static cl::opt< bool > VerifyScops ( "polly-detect-verify"  ,
cl::desc("Verify the detected SCoPs after each transformation")  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ XAllowFullFunction()

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

◆ XPollyAllowUnsignedOperations()

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  
)
static

◆ XPollyInvariantLoadHoisting()

static cl::opt< bool, true > XPollyInvariantLoadHoisting ( "polly-invariant-load-hoisting"  ,
cl::desc("Hoist invariant loads.")  ,
cl::location(PollyInvariantLoadHoisting)  ,
cl::Hidden  ,
cl::cat(PollyCategory  
)
static

◆ XPollyProcessUnprofitable()

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

◆ XPollyUseRuntimeAliasChecks()

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

Variable Documentation

◆ MIN_LOOP_TRIP_COUNT

const unsigned MIN_LOOP_TRIP_COUNT = 8
static

The minimal trip count under which loops are considered unprofitable.

Definition at line 232 of file ScopDetection.cpp.

Referenced by polly::ScopDetection::isProfitableRegion().