1 //===- ScopDetection.cpp - Detect Scops -----------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Detect the maximal Scops of a function.
12 // A static control part (Scop) is a subgraph of the control flow graph (CFG)
13 // that only has statically known control flow and can therefore be described
14 // within the polyhedral model.
16 // Every Scop fulfills these restrictions:
18 // * It is a single entry single exit region
20 // * Only affine linear bounds in the loops
22 // Every natural loop in a Scop must have a number of loop iterations that can
23 // be described as an affine linear function in surrounding loop iterators or
24 // parameters. (A parameter is a scalar that does not change its value during
25 // execution of the Scop).
27 // * Only comparisons of affine linear expressions in conditions
29 // * All loops and conditions perfectly nested
31 // The control flow needs to be structured such that it could be written using
32 // just 'for' and 'if' statements, without the need for any 'goto', 'break' or
35 // * Side effect free functions call
37 // Function calls and intrinsics that do not have side effects (readnone)
38 // or memory intrinsics (memset, memcpy, memmove) are allowed.
40 // The Scop detection finds the largest Scops by checking if the largest
41 // region is a Scop. If this is not the case, its canonical subregions are
42 // checked until a region is a Scop. It is now tried to extend this Scop by
43 // creating a larger non canonical region.
45 //===----------------------------------------------------------------------===//
47 #include "polly/ScopDetection.h"
48 #include "polly/LinkAllPasses.h"
49 #include "polly/Options.h"
50 #include "polly/ScopDetectionDiagnostic.h"
51 #include "polly/Support/SCEVValidator.h"
52 #include "polly/Support/ScopHelper.h"
53 #include "polly/Support/ScopLocation.h"
54 #include "llvm/ADT/DenseMap.h"
55 #include "llvm/ADT/SetVector.h"
56 #include "llvm/ADT/SmallPtrSet.h"
57 #include "llvm/ADT/SmallVector.h"
58 #include "llvm/ADT/Statistic.h"
59 #include "llvm/ADT/StringRef.h"
60 #include "llvm/Analysis/AliasAnalysis.h"
61 #include "llvm/Analysis/Loads.h"
62 #include "llvm/Analysis/LoopInfo.h"
63 #include "llvm/Analysis/MemoryLocation.h"
64 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
65 #include "llvm/Analysis/RegionInfo.h"
66 #include "llvm/Analysis/ScalarEvolution.h"
67 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
68 #include "llvm/IR/BasicBlock.h"
69 #include "llvm/IR/Constants.h"
70 #include "llvm/IR/DebugLoc.h"
71 #include "llvm/IR/DerivedTypes.h"
72 #include "llvm/IR/DiagnosticInfo.h"
73 #include "llvm/IR/DiagnosticPrinter.h"
74 #include "llvm/IR/Dominators.h"
75 #include "llvm/IR/Function.h"
76 #include "llvm/IR/InstrTypes.h"
77 #include "llvm/IR/Instruction.h"
78 #include "llvm/IR/Instructions.h"
79 #include "llvm/IR/IntrinsicInst.h"
80 #include "llvm/IR/Intrinsics.h"
81 #include "llvm/IR/LLVMContext.h"
82 #include "llvm/IR/Metadata.h"
83 #include "llvm/IR/Module.h"
84 #include "llvm/IR/PassManager.h"
85 #include "llvm/IR/Type.h"
86 #include "llvm/IR/Value.h"
87 #include "llvm/Pass.h"
88 #include "llvm/Support/Casting.h"
89 #include "llvm/Support/CommandLine.h"
90 #include "llvm/Support/Debug.h"
91 #include "llvm/Support/ErrorHandling.h"
92 #include "llvm/Support/Regex.h"
93 #include "llvm/Support/raw_ostream.h"
102 using namespace llvm
;
103 using namespace polly
;
105 #define DEBUG_TYPE "polly-detect"
107 // This option is set to a very high value, as analyzing such loops increases
108 // compile time on several cases. For experiments that enable this option,
109 // a value of around 40 has been working to avoid run-time regressions with
110 // Polly while still exposing interesting optimization opportunities.
111 static cl::opt
<int> ProfitabilityMinPerLoopInstructions(
112 "polly-detect-profitability-min-per-loop-insts",
113 cl::desc("The minimal number of per-loop instructions before a single loop "
114 "region is considered profitable"),
115 cl::Hidden
, cl::ValueRequired
, cl::init(100000000), cl::cat(PollyCategory
));
117 bool polly::PollyProcessUnprofitable
;
119 static cl::opt
<bool, true> XPollyProcessUnprofitable(
120 "polly-process-unprofitable",
122 "Process scops that are unlikely to benefit from Polly optimizations."),
123 cl::location(PollyProcessUnprofitable
), cl::init(false), cl::ZeroOrMore
,
124 cl::cat(PollyCategory
));
126 static cl::list
<std::string
> OnlyFunctions(
128 cl::desc("Only run on functions that match a regex. "
129 "Multiple regexes can be comma separated. "
130 "Scop detection will run on all functions that match "
131 "ANY of the regexes provided."),
132 cl::ZeroOrMore
, cl::CommaSeparated
, cl::cat(PollyCategory
));
134 static cl::list
<std::string
> IgnoredFunctions(
136 cl::desc("Ignore functions that match a regex. "
137 "Multiple regexes can be comma separated. "
138 "Scop detection will ignore all functions that match "
139 "ANY of the regexes provided."),
140 cl::ZeroOrMore
, cl::CommaSeparated
, cl::cat(PollyCategory
));
142 bool polly::PollyAllowFullFunction
;
144 static cl::opt
<bool, true>
145 XAllowFullFunction("polly-detect-full-functions",
146 cl::desc("Allow the detection of full functions"),
147 cl::location(polly::PollyAllowFullFunction
),
148 cl::init(false), cl::cat(PollyCategory
));
150 static cl::opt
<std::string
> OnlyRegion(
152 cl::desc("Only run on certain regions (The provided identifier must "
153 "appear in the name of the region's entry block"),
154 cl::value_desc("identifier"), cl::ValueRequired
, cl::init(""),
155 cl::cat(PollyCategory
));
158 IgnoreAliasing("polly-ignore-aliasing",
159 cl::desc("Ignore possible aliasing of the array bases"),
160 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
161 cl::cat(PollyCategory
));
163 bool polly::PollyAllowUnsignedOperations
;
165 static cl::opt
<bool, true> XPollyAllowUnsignedOperations(
166 "polly-allow-unsigned-operations",
167 cl::desc("Allow unsigned operations such as comparisons or zero-extends."),
168 cl::location(PollyAllowUnsignedOperations
), cl::Hidden
, cl::ZeroOrMore
,
169 cl::init(true), cl::cat(PollyCategory
));
171 bool polly::PollyUseRuntimeAliasChecks
;
173 static cl::opt
<bool, true> XPollyUseRuntimeAliasChecks(
174 "polly-use-runtime-alias-checks",
175 cl::desc("Use runtime alias checks to resolve possible aliasing."),
176 cl::location(PollyUseRuntimeAliasChecks
), cl::Hidden
, cl::ZeroOrMore
,
177 cl::init(true), cl::cat(PollyCategory
));
180 ReportLevel("polly-report",
181 cl::desc("Print information about the activities of Polly"),
182 cl::init(false), cl::ZeroOrMore
, cl::cat(PollyCategory
));
184 static cl::opt
<bool> AllowDifferentTypes(
185 "polly-allow-differing-element-types",
186 cl::desc("Allow different element types for array accesses"), cl::Hidden
,
187 cl::init(true), cl::ZeroOrMore
, cl::cat(PollyCategory
));
190 AllowNonAffine("polly-allow-nonaffine",
191 cl::desc("Allow non affine access functions in arrays"),
192 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
193 cl::cat(PollyCategory
));
196 AllowModrefCall("polly-allow-modref-calls",
197 cl::desc("Allow functions with known modref behavior"),
198 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
199 cl::cat(PollyCategory
));
201 static cl::opt
<bool> AllowNonAffineSubRegions(
202 "polly-allow-nonaffine-branches",
203 cl::desc("Allow non affine conditions for branches"), cl::Hidden
,
204 cl::init(true), cl::ZeroOrMore
, cl::cat(PollyCategory
));
207 AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
208 cl::desc("Allow non affine conditions for loops"),
209 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
210 cl::cat(PollyCategory
));
212 static cl::opt
<bool, true>
213 TrackFailures("polly-detect-track-failures",
214 cl::desc("Track failure strings in detecting scop regions"),
215 cl::location(PollyTrackFailures
), cl::Hidden
, cl::ZeroOrMore
,
216 cl::init(true), cl::cat(PollyCategory
));
218 static cl::opt
<bool> KeepGoing("polly-detect-keep-going",
219 cl::desc("Do not fail on the first error."),
220 cl::Hidden
, cl::ZeroOrMore
, cl::init(false),
221 cl::cat(PollyCategory
));
223 static cl::opt
<bool, true>
224 PollyDelinearizeX("polly-delinearize",
225 cl::desc("Delinearize array access functions"),
226 cl::location(PollyDelinearize
), cl::Hidden
,
227 cl::ZeroOrMore
, cl::init(true), cl::cat(PollyCategory
));
230 VerifyScops("polly-detect-verify",
231 cl::desc("Verify the detected SCoPs after each transformation"),
232 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
233 cl::cat(PollyCategory
));
235 bool polly::PollyInvariantLoadHoisting
;
237 static cl::opt
<bool, true> XPollyInvariantLoadHoisting(
238 "polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."),
239 cl::location(PollyInvariantLoadHoisting
), cl::Hidden
, cl::ZeroOrMore
,
240 cl::init(false), cl::cat(PollyCategory
));
242 /// The minimal trip count under which loops are considered unprofitable.
243 static const unsigned MIN_LOOP_TRIP_COUNT
= 8;
245 bool polly::PollyTrackFailures
= false;
246 bool polly::PollyDelinearize
= false;
247 StringRef
polly::PollySkipFnAttr
= "polly.skip.fn";
249 //===----------------------------------------------------------------------===//
252 STATISTIC(NumScopRegions
, "Number of scops");
253 STATISTIC(NumLoopsInScop
, "Number of loops in scops");
254 STATISTIC(NumScopsDepthZero
, "Number of scops with maximal loop depth 0");
255 STATISTIC(NumScopsDepthOne
, "Number of scops with maximal loop depth 1");
256 STATISTIC(NumScopsDepthTwo
, "Number of scops with maximal loop depth 2");
257 STATISTIC(NumScopsDepthThree
, "Number of scops with maximal loop depth 3");
258 STATISTIC(NumScopsDepthFour
, "Number of scops with maximal loop depth 4");
259 STATISTIC(NumScopsDepthFive
, "Number of scops with maximal loop depth 5");
260 STATISTIC(NumScopsDepthLarger
,
261 "Number of scops with maximal loop depth 6 and larger");
262 STATISTIC(NumProfScopRegions
, "Number of scops (profitable scops only)");
263 STATISTIC(NumLoopsInProfScop
,
264 "Number of loops in scops (profitable scops only)");
265 STATISTIC(NumLoopsOverall
, "Number of total loops");
266 STATISTIC(NumProfScopsDepthZero
,
267 "Number of scops with maximal loop depth 0 (profitable scops only)");
268 STATISTIC(NumProfScopsDepthOne
,
269 "Number of scops with maximal loop depth 1 (profitable scops only)");
270 STATISTIC(NumProfScopsDepthTwo
,
271 "Number of scops with maximal loop depth 2 (profitable scops only)");
272 STATISTIC(NumProfScopsDepthThree
,
273 "Number of scops with maximal loop depth 3 (profitable scops only)");
274 STATISTIC(NumProfScopsDepthFour
,
275 "Number of scops with maximal loop depth 4 (profitable scops only)");
276 STATISTIC(NumProfScopsDepthFive
,
277 "Number of scops with maximal loop depth 5 (profitable scops only)");
278 STATISTIC(NumProfScopsDepthLarger
,
279 "Number of scops with maximal loop depth 6 and larger "
280 "(profitable scops only)");
281 STATISTIC(MaxNumLoopsInScop
, "Maximal number of loops in scops");
282 STATISTIC(MaxNumLoopsInProfScop
,
283 "Maximal number of loops in scops (profitable scops only)");
285 static void updateLoopCountStatistic(ScopDetection::LoopStats Stats
,
286 bool OnlyProfitable
);
290 class DiagnosticScopFound
: public DiagnosticInfo
{
292 static int PluginDiagnosticKind
;
295 std::string FileName
;
296 unsigned EntryLine
, ExitLine
;
299 DiagnosticScopFound(Function
&F
, std::string FileName
, unsigned EntryLine
,
301 : DiagnosticInfo(PluginDiagnosticKind
, DS_Note
), F(F
), FileName(FileName
),
302 EntryLine(EntryLine
), ExitLine(ExitLine
) {}
304 void print(DiagnosticPrinter
&DP
) const override
;
306 static bool classof(const DiagnosticInfo
*DI
) {
307 return DI
->getKind() == PluginDiagnosticKind
;
312 int DiagnosticScopFound::PluginDiagnosticKind
=
313 getNextAvailablePluginDiagnosticKind();
315 void DiagnosticScopFound::print(DiagnosticPrinter
&DP
) const {
316 DP
<< "Polly detected an optimizable loop region (scop) in function '" << F
319 if (FileName
.empty()) {
320 DP
<< "Scop location is unknown. Compile with debug info "
321 "(-g) to get more precise information. ";
325 DP
<< FileName
<< ":" << EntryLine
<< ": Start of scop\n";
326 DP
<< FileName
<< ":" << ExitLine
<< ": End of scop";
329 /// Check if a string matches any regex in a list of regexes.
330 /// @param Str the input string to match against.
331 /// @param RegexList a list of strings that are regular expressions.
332 static bool doesStringMatchAnyRegex(StringRef Str
,
333 const cl::list
<std::string
> &RegexList
) {
334 for (auto RegexStr
: RegexList
) {
339 report_fatal_error("invalid regex given as input to polly: " + Err
, true);
346 //===----------------------------------------------------------------------===//
349 ScopDetection::ScopDetection(Function
&F
, const DominatorTree
&DT
,
350 ScalarEvolution
&SE
, LoopInfo
&LI
, RegionInfo
&RI
,
351 AliasAnalysis
&AA
, OptimizationRemarkEmitter
&ORE
)
352 : DT(DT
), SE(SE
), LI(LI
), RI(RI
), AA(AA
), ORE(ORE
) {
353 if (!PollyProcessUnprofitable
&& LI
.empty())
356 Region
*TopRegion
= RI
.getTopLevelRegion();
358 if (!OnlyFunctions
.empty() &&
359 !doesStringMatchAnyRegex(F
.getName(), OnlyFunctions
))
362 if (doesStringMatchAnyRegex(F
.getName(), IgnoredFunctions
))
365 if (!isValidFunction(F
))
368 findScops(*TopRegion
);
370 NumScopRegions
+= ValidRegions
.size();
372 // Prune non-profitable regions.
373 for (auto &DIt
: DetectionContextMap
) {
374 auto &DC
= DIt
.getSecond();
375 if (DC
.Log
.hasErrors())
377 if (!ValidRegions
.count(&DC
.CurRegion
))
379 LoopStats Stats
= countBeneficialLoops(&DC
.CurRegion
, SE
, LI
, 0);
380 updateLoopCountStatistic(Stats
, false /* OnlyProfitable */);
381 if (isProfitableRegion(DC
)) {
382 updateLoopCountStatistic(Stats
, true /* OnlyProfitable */);
386 ValidRegions
.remove(&DC
.CurRegion
);
389 NumProfScopRegions
+= ValidRegions
.size();
390 NumLoopsOverall
+= countBeneficialLoops(TopRegion
, SE
, LI
, 0).NumLoops
;
392 // Only makes sense when we tracked errors.
393 if (PollyTrackFailures
)
394 emitMissedRemarks(F
);
399 assert(ValidRegions
.size() <= DetectionContextMap
.size() &&
400 "Cached more results than valid regions");
403 template <class RR
, typename
... Args
>
404 inline bool ScopDetection::invalid(DetectionContext
&Context
, bool Assert
,
405 Args
&&... Arguments
) const {
406 if (!Context
.Verifying
) {
407 RejectLog
&Log
= Context
.Log
;
408 std::shared_ptr
<RR
> RejectReason
= std::make_shared
<RR
>(Arguments
...);
410 if (PollyTrackFailures
)
411 Log
.report(RejectReason
);
413 LLVM_DEBUG(dbgs() << RejectReason
->getMessage());
414 LLVM_DEBUG(dbgs() << "\n");
416 assert(!Assert
&& "Verification of detected scop failed");
422 bool ScopDetection::isMaxRegionInScop(const Region
&R
, bool Verify
) const {
423 if (!ValidRegions
.count(&R
))
427 DetectionContextMap
.erase(getBBPairForRegion(&R
));
428 const auto &It
= DetectionContextMap
.insert(std::make_pair(
429 getBBPairForRegion(&R
),
430 DetectionContext(const_cast<Region
&>(R
), AA
, false /*verifying*/)));
431 DetectionContext
&Context
= It
.first
->second
;
432 return isValidRegion(Context
);
438 std::string
ScopDetection::regionIsInvalidBecause(const Region
*R
) const {
439 // Get the first error we found. Even in keep-going mode, this is the first
440 // reason that caused the candidate to be rejected.
441 auto *Log
= lookupRejectionLog(R
);
443 // This can happen when we marked a region invalid, but didn't track
445 if (!Log
|| !Log
->hasErrors())
448 RejectReasonPtr RR
= *Log
->begin();
449 return RR
->getMessage();
452 bool ScopDetection::addOverApproximatedRegion(Region
*AR
,
453 DetectionContext
&Context
) const {
454 // If we already know about Ar we can exit.
455 if (!Context
.NonAffineSubRegionSet
.insert(AR
))
458 // All loops in the region have to be overapproximated too if there
459 // are accesses that depend on the iteration count.
461 for (BasicBlock
*BB
: AR
->blocks()) {
462 Loop
*L
= LI
.getLoopFor(BB
);
464 Context
.BoxedLoopsSet
.insert(L
);
467 return (AllowNonAffineSubLoops
|| Context
.BoxedLoopsSet
.empty());
470 bool ScopDetection::onlyValidRequiredInvariantLoads(
471 InvariantLoadsSetTy
&RequiredILS
, DetectionContext
&Context
) const {
472 Region
&CurRegion
= Context
.CurRegion
;
473 const DataLayout
&DL
= CurRegion
.getEntry()->getModule()->getDataLayout();
475 if (!PollyInvariantLoadHoisting
&& !RequiredILS
.empty())
478 for (LoadInst
*Load
: RequiredILS
) {
479 // If we already know a load has been accepted as required invariant, we
480 // already run the validation below once and consequently don't need to
481 // run it again. Hence, we return early. For certain test cases (e.g.,
482 // COSMO this avoids us spending 50% of scop-detection time in this
483 // very function (and its children).
484 if (Context
.RequiredILS
.count(Load
))
486 if (!isHoistableLoad(Load
, CurRegion
, LI
, SE
, DT
, Context
.RequiredILS
))
489 for (auto NonAffineRegion
: Context
.NonAffineSubRegionSet
) {
490 if (isSafeToLoadUnconditionally(Load
->getPointerOperand(),
491 Load
->getAlignment(), DL
))
494 if (NonAffineRegion
->contains(Load
) &&
495 Load
->getParent() != NonAffineRegion
->getEntry())
500 Context
.RequiredILS
.insert(RequiredILS
.begin(), RequiredILS
.end());
505 bool ScopDetection::involvesMultiplePtrs(const SCEV
*S0
, const SCEV
*S1
,
507 SetVector
<Value
*> Values
;
508 findValues(S0
, SE
, Values
);
510 findValues(S1
, SE
, Values
);
512 SmallPtrSet
<Value
*, 8> PtrVals
;
513 for (auto *V
: Values
) {
514 if (auto *P2I
= dyn_cast
<PtrToIntInst
>(V
))
515 V
= P2I
->getOperand(0);
517 if (!V
->getType()->isPointerTy())
520 auto *PtrSCEV
= SE
.getSCEVAtScope(V
, Scope
);
521 if (isa
<SCEVConstant
>(PtrSCEV
))
524 auto *BasePtr
= dyn_cast
<SCEVUnknown
>(SE
.getPointerBase(PtrSCEV
));
528 auto *BasePtrVal
= BasePtr
->getValue();
529 if (PtrVals
.insert(BasePtrVal
).second
) {
530 for (auto *PtrVal
: PtrVals
)
531 if (PtrVal
!= BasePtrVal
&& !AA
.isNoAlias(PtrVal
, BasePtrVal
))
539 bool ScopDetection::isAffine(const SCEV
*S
, Loop
*Scope
,
540 DetectionContext
&Context
) const {
541 InvariantLoadsSetTy AccessILS
;
542 if (!isAffineExpr(&Context
.CurRegion
, Scope
, S
, SE
, &AccessILS
))
545 if (!onlyValidRequiredInvariantLoads(AccessILS
, Context
))
551 bool ScopDetection::isValidSwitch(BasicBlock
&BB
, SwitchInst
*SI
,
552 Value
*Condition
, bool IsLoopBranch
,
553 DetectionContext
&Context
) const {
554 Loop
*L
= LI
.getLoopFor(&BB
);
555 const SCEV
*ConditionSCEV
= SE
.getSCEVAtScope(Condition
, L
);
557 if (IsLoopBranch
&& L
->isLoopLatch(&BB
))
560 // Check for invalid usage of different pointers in one expression.
561 if (involvesMultiplePtrs(ConditionSCEV
, nullptr, L
))
564 if (isAffine(ConditionSCEV
, L
, Context
))
567 if (AllowNonAffineSubRegions
&&
568 addOverApproximatedRegion(RI
.getRegionFor(&BB
), Context
))
571 return invalid
<ReportNonAffBranch
>(Context
, /*Assert=*/true, &BB
,
572 ConditionSCEV
, ConditionSCEV
, SI
);
575 bool ScopDetection::isValidBranch(BasicBlock
&BB
, BranchInst
*BI
,
576 Value
*Condition
, bool IsLoopBranch
,
577 DetectionContext
&Context
) const {
578 // Constant integer conditions are always affine.
579 if (isa
<ConstantInt
>(Condition
))
582 if (BinaryOperator
*BinOp
= dyn_cast
<BinaryOperator
>(Condition
)) {
583 auto Opcode
= BinOp
->getOpcode();
584 if (Opcode
== Instruction::And
|| Opcode
== Instruction::Or
) {
585 Value
*Op0
= BinOp
->getOperand(0);
586 Value
*Op1
= BinOp
->getOperand(1);
587 return isValidBranch(BB
, BI
, Op0
, IsLoopBranch
, Context
) &&
588 isValidBranch(BB
, BI
, Op1
, IsLoopBranch
, Context
);
592 if (auto PHI
= dyn_cast
<PHINode
>(Condition
)) {
593 auto *Unique
= dyn_cast_or_null
<ConstantInt
>(
594 getUniqueNonErrorValue(PHI
, &Context
.CurRegion
, LI
, DT
));
595 if (Unique
&& (Unique
->isZero() || Unique
->isOne()))
599 if (auto Load
= dyn_cast
<LoadInst
>(Condition
))
600 if (!IsLoopBranch
&& Context
.CurRegion
.contains(Load
)) {
601 Context
.RequiredILS
.insert(Load
);
605 // Non constant conditions of branches need to be ICmpInst.
606 if (!isa
<ICmpInst
>(Condition
)) {
607 if (!IsLoopBranch
&& AllowNonAffineSubRegions
&&
608 addOverApproximatedRegion(RI
.getRegionFor(&BB
), Context
))
610 return invalid
<ReportInvalidCond
>(Context
, /*Assert=*/true, BI
, &BB
);
613 ICmpInst
*ICmp
= cast
<ICmpInst
>(Condition
);
615 // Are both operands of the ICmp affine?
616 if (isa
<UndefValue
>(ICmp
->getOperand(0)) ||
617 isa
<UndefValue
>(ICmp
->getOperand(1)))
618 return invalid
<ReportUndefOperand
>(Context
, /*Assert=*/true, &BB
, ICmp
);
620 Loop
*L
= LI
.getLoopFor(&BB
);
621 const SCEV
*LHS
= SE
.getSCEVAtScope(ICmp
->getOperand(0), L
);
622 const SCEV
*RHS
= SE
.getSCEVAtScope(ICmp
->getOperand(1), L
);
624 LHS
= tryForwardThroughPHI(LHS
, Context
.CurRegion
, SE
, LI
, DT
);
625 RHS
= tryForwardThroughPHI(RHS
, Context
.CurRegion
, SE
, LI
, DT
);
627 // If unsigned operations are not allowed try to approximate the region.
628 if (ICmp
->isUnsigned() && !PollyAllowUnsignedOperations
)
629 return !IsLoopBranch
&& AllowNonAffineSubRegions
&&
630 addOverApproximatedRegion(RI
.getRegionFor(&BB
), Context
);
632 // Check for invalid usage of different pointers in one expression.
633 if (ICmp
->isEquality() && involvesMultiplePtrs(LHS
, nullptr, L
) &&
634 involvesMultiplePtrs(RHS
, nullptr, L
))
637 // Check for invalid usage of different pointers in a relational comparison.
638 if (ICmp
->isRelational() && involvesMultiplePtrs(LHS
, RHS
, L
))
641 if (isAffine(LHS
, L
, Context
) && isAffine(RHS
, L
, Context
))
644 if (!IsLoopBranch
&& AllowNonAffineSubRegions
&&
645 addOverApproximatedRegion(RI
.getRegionFor(&BB
), Context
))
651 return invalid
<ReportNonAffBranch
>(Context
, /*Assert=*/true, &BB
, LHS
, RHS
,
655 bool ScopDetection::isValidCFG(BasicBlock
&BB
, bool IsLoopBranch
,
656 bool AllowUnreachable
,
657 DetectionContext
&Context
) const {
658 Region
&CurRegion
= Context
.CurRegion
;
660 TerminatorInst
*TI
= BB
.getTerminator();
662 if (AllowUnreachable
&& isa
<UnreachableInst
>(TI
))
665 // Return instructions are only valid if the region is the top level region.
666 if (isa
<ReturnInst
>(TI
) && CurRegion
.isTopLevelRegion())
669 Value
*Condition
= getConditionFromTerminator(TI
);
672 return invalid
<ReportInvalidTerminator
>(Context
, /*Assert=*/true, &BB
);
674 // UndefValue is not allowed as condition.
675 if (isa
<UndefValue
>(Condition
))
676 return invalid
<ReportUndefCond
>(Context
, /*Assert=*/true, TI
, &BB
);
678 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(TI
))
679 return isValidBranch(BB
, BI
, Condition
, IsLoopBranch
, Context
);
681 SwitchInst
*SI
= dyn_cast
<SwitchInst
>(TI
);
682 assert(SI
&& "Terminator was neither branch nor switch");
684 return isValidSwitch(BB
, SI
, Condition
, IsLoopBranch
, Context
);
687 bool ScopDetection::isValidCallInst(CallInst
&CI
,
688 DetectionContext
&Context
) const {
689 if (CI
.doesNotReturn())
692 if (CI
.doesNotAccessMemory())
695 if (auto *II
= dyn_cast
<IntrinsicInst
>(&CI
))
696 if (isValidIntrinsicInst(*II
, Context
))
699 Function
*CalledFunction
= CI
.getCalledFunction();
701 // Indirect calls are not supported.
702 if (CalledFunction
== nullptr)
705 if (isDebugCall(&CI
)) {
706 LLVM_DEBUG(dbgs() << "Allow call to debug function: "
707 << CalledFunction
->getName() << '\n');
711 if (AllowModrefCall
) {
712 switch (AA
.getModRefBehavior(CalledFunction
)) {
713 case FMRB_UnknownModRefBehavior
:
715 case FMRB_DoesNotAccessMemory
:
716 case FMRB_OnlyReadsMemory
:
717 // Implicitly disable delinearization since we have an unknown
718 // accesses with an unknown access function.
719 Context
.HasUnknownAccess
= true;
720 Context
.AST
.add(&CI
);
722 case FMRB_OnlyReadsArgumentPointees
:
723 case FMRB_OnlyAccessesArgumentPointees
:
724 for (const auto &Arg
: CI
.arg_operands()) {
725 if (!Arg
->getType()->isPointerTy())
728 // Bail if a pointer argument has a base address not known to
729 // ScalarEvolution. Note that a zero pointer is acceptable.
730 auto *ArgSCEV
= SE
.getSCEVAtScope(Arg
, LI
.getLoopFor(CI
.getParent()));
731 if (ArgSCEV
->isZero())
734 auto *BP
= dyn_cast
<SCEVUnknown
>(SE
.getPointerBase(ArgSCEV
));
738 // Implicitly disable delinearization since we have an unknown
739 // accesses with an unknown access function.
740 Context
.HasUnknownAccess
= true;
743 Context
.AST
.add(&CI
);
745 case FMRB_DoesNotReadMemory
:
746 case FMRB_OnlyAccessesInaccessibleMem
:
747 case FMRB_OnlyAccessesInaccessibleOrArgMem
:
755 bool ScopDetection::isValidIntrinsicInst(IntrinsicInst
&II
,
756 DetectionContext
&Context
) const {
757 if (isIgnoredIntrinsic(&II
))
760 // The closest loop surrounding the call instruction.
761 Loop
*L
= LI
.getLoopFor(II
.getParent());
763 // The access function and base pointer for memory intrinsics.
765 const SCEVUnknown
*BP
;
767 switch (II
.getIntrinsicID()) {
768 // Memory intrinsics that can be represented are supported.
769 case Intrinsic::memmove
:
770 case Intrinsic::memcpy
:
771 AF
= SE
.getSCEVAtScope(cast
<MemTransferInst
>(II
).getSource(), L
);
773 BP
= dyn_cast
<SCEVUnknown
>(SE
.getPointerBase(AF
));
774 // Bail if the source pointer is not valid.
775 if (!isValidAccess(&II
, AF
, BP
, Context
))
779 case Intrinsic::memset
:
780 AF
= SE
.getSCEVAtScope(cast
<MemIntrinsic
>(II
).getDest(), L
);
782 BP
= dyn_cast
<SCEVUnknown
>(SE
.getPointerBase(AF
));
783 // Bail if the destination pointer is not valid.
784 if (!isValidAccess(&II
, AF
, BP
, Context
))
788 // Bail if the length is not affine.
789 if (!isAffine(SE
.getSCEVAtScope(cast
<MemIntrinsic
>(II
).getLength(), L
), L
,
801 bool ScopDetection::isInvariant(Value
&Val
, const Region
&Reg
,
802 DetectionContext
&Ctx
) const {
803 // A reference to function argument or constant value is invariant.
804 if (isa
<Argument
>(Val
) || isa
<Constant
>(Val
))
807 Instruction
*I
= dyn_cast
<Instruction
>(&Val
);
811 if (!Reg
.contains(I
))
814 // Loads within the SCoP may read arbitrary values, need to hoist them. If it
815 // is not hoistable, it will be rejected later, but here we assume it is and
816 // that makes the value invariant.
817 if (auto LI
= dyn_cast
<LoadInst
>(I
)) {
818 Ctx
.RequiredILS
.insert(LI
);
827 /// Remove smax of smax(0, size) expressions from a SCEV expression and
828 /// register the '...' components.
830 /// Array access expressions as they are generated by GFortran contain smax(0,
831 /// size) expressions that confuse the 'normal' delinearization algorithm.
832 /// However, if we extract such expressions before the normal delinearization
833 /// takes place they can actually help to identify array size expressions in
834 /// Fortran accesses. For the subsequently following delinearization the smax(0,
835 /// size) component can be replaced by just 'size'. This is correct as we will
836 /// always add and verify the assumption that for all subscript expressions
837 /// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify
838 /// that 0 <= size, which means smax(0, size) == size.
839 class SCEVRemoveMax
: public SCEVRewriteVisitor
<SCEVRemoveMax
> {
841 SCEVRemoveMax(ScalarEvolution
&SE
, std::vector
<const SCEV
*> *Terms
)
842 : SCEVRewriteVisitor(SE
), Terms(Terms
) {}
844 static const SCEV
*rewrite(const SCEV
*Scev
, ScalarEvolution
&SE
,
845 std::vector
<const SCEV
*> *Terms
= nullptr) {
846 SCEVRemoveMax
Rewriter(SE
, Terms
);
847 return Rewriter
.visit(Scev
);
850 const SCEV
*visitSMaxExpr(const SCEVSMaxExpr
*Expr
) {
851 if ((Expr
->getNumOperands() == 2) && Expr
->getOperand(0)->isZero()) {
852 auto Res
= visit(Expr
->getOperand(1));
854 (*Terms
).push_back(Res
);
862 std::vector
<const SCEV
*> *Terms
;
866 SmallVector
<const SCEV
*, 4>
867 ScopDetection::getDelinearizationTerms(DetectionContext
&Context
,
868 const SCEVUnknown
*BasePointer
) const {
869 SmallVector
<const SCEV
*, 4> Terms
;
870 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
871 std::vector
<const SCEV
*> MaxTerms
;
872 SCEVRemoveMax::rewrite(Pair
.second
, SE
, &MaxTerms
);
873 if (!MaxTerms
.empty()) {
874 Terms
.insert(Terms
.begin(), MaxTerms
.begin(), MaxTerms
.end());
877 // In case the outermost expression is a plain add, we check if any of its
878 // terms has the form 4 * %inst * %param * %param ..., aka a term that
879 // contains a product between a parameter and an instruction that is
880 // inside the scop. Such instructions, if allowed at all, are instructions
881 // SCEV can not represent, but Polly is still looking through. As a
882 // result, these instructions can depend on induction variables and are
883 // most likely no array sizes. However, terms that are multiplied with
884 // them are likely candidates for array sizes.
885 if (auto *AF
= dyn_cast
<SCEVAddExpr
>(Pair
.second
)) {
886 for (auto Op
: AF
->operands()) {
887 if (auto *AF2
= dyn_cast
<SCEVAddRecExpr
>(Op
))
888 SE
.collectParametricTerms(AF2
, Terms
);
889 if (auto *AF2
= dyn_cast
<SCEVMulExpr
>(Op
)) {
890 SmallVector
<const SCEV
*, 0> Operands
;
892 for (auto *MulOp
: AF2
->operands()) {
893 if (auto *Const
= dyn_cast
<SCEVConstant
>(MulOp
))
894 Operands
.push_back(Const
);
895 if (auto *Unknown
= dyn_cast
<SCEVUnknown
>(MulOp
)) {
896 if (auto *Inst
= dyn_cast
<Instruction
>(Unknown
->getValue())) {
897 if (!Context
.CurRegion
.contains(Inst
))
898 Operands
.push_back(MulOp
);
901 Operands
.push_back(MulOp
);
906 Terms
.push_back(SE
.getMulExpr(Operands
));
911 SE
.collectParametricTerms(Pair
.second
, Terms
);
916 bool ScopDetection::hasValidArraySizes(DetectionContext
&Context
,
917 SmallVectorImpl
<const SCEV
*> &Sizes
,
918 const SCEVUnknown
*BasePointer
,
920 // If no sizes were found, all sizes are trivially valid. We allow this case
921 // to make it possible to pass known-affine accesses to the delinearization to
922 // try to recover some interesting multi-dimensional accesses, but to still
923 // allow the already known to be affine access in case the delinearization
924 // fails. In such situations, the delinearization will just return a Sizes
925 // array of size zero.
926 if (Sizes
.size() == 0)
929 Value
*BaseValue
= BasePointer
->getValue();
930 Region
&CurRegion
= Context
.CurRegion
;
931 for (const SCEV
*DelinearizedSize
: Sizes
) {
932 if (!isAffine(DelinearizedSize
, Scope
, Context
)) {
936 if (auto *Unknown
= dyn_cast
<SCEVUnknown
>(DelinearizedSize
)) {
937 auto *V
= dyn_cast
<Value
>(Unknown
->getValue());
938 if (auto *Load
= dyn_cast
<LoadInst
>(V
)) {
939 if (Context
.CurRegion
.contains(Load
) &&
940 isHoistableLoad(Load
, CurRegion
, LI
, SE
, DT
, Context
.RequiredILS
))
941 Context
.RequiredILS
.insert(Load
);
945 if (hasScalarDepsInsideRegion(DelinearizedSize
, &CurRegion
, Scope
, false,
946 Context
.RequiredILS
))
947 return invalid
<ReportNonAffineAccess
>(
948 Context
, /*Assert=*/true, DelinearizedSize
,
949 Context
.Accesses
[BasePointer
].front().first
, BaseValue
);
952 // No array shape derived.
957 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
958 const Instruction
*Insn
= Pair
.first
;
959 const SCEV
*AF
= Pair
.second
;
961 if (!isAffine(AF
, Scope
, Context
)) {
962 invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Insn
,
973 // We first store the resulting memory accesses in TempMemoryAccesses. Only
974 // if the access functions for all memory accesses have been successfully
975 // delinearized we continue. Otherwise, we either report a failure or, if
976 // non-affine accesses are allowed, we drop the information. In case the
977 // information is dropped the memory accesses need to be overapproximated
978 // when translated to a polyhedral representation.
979 bool ScopDetection::computeAccessFunctions(
980 DetectionContext
&Context
, const SCEVUnknown
*BasePointer
,
981 std::shared_ptr
<ArrayShape
> Shape
) const {
982 Value
*BaseValue
= BasePointer
->getValue();
983 bool BasePtrHasNonAffine
= false;
984 MapInsnToMemAcc TempMemoryAccesses
;
985 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
986 const Instruction
*Insn
= Pair
.first
;
987 auto *AF
= Pair
.second
;
988 AF
= SCEVRemoveMax::rewrite(AF
, SE
);
989 bool IsNonAffine
= false;
990 TempMemoryAccesses
.insert(std::make_pair(Insn
, MemAcc(Insn
, Shape
)));
991 MemAcc
*Acc
= &TempMemoryAccesses
.find(Insn
)->second
;
992 auto *Scope
= LI
.getLoopFor(Insn
->getParent());
995 if (isAffine(Pair
.second
, Scope
, Context
))
996 Acc
->DelinearizedSubscripts
.push_back(Pair
.second
);
1000 if (Shape
->DelinearizedSizes
.size() == 0) {
1001 Acc
->DelinearizedSubscripts
.push_back(AF
);
1003 SE
.computeAccessFunctions(AF
, Acc
->DelinearizedSubscripts
,
1004 Shape
->DelinearizedSizes
);
1005 if (Acc
->DelinearizedSubscripts
.size() == 0)
1008 for (const SCEV
*S
: Acc
->DelinearizedSubscripts
)
1009 if (!isAffine(S
, Scope
, Context
))
1013 // (Possibly) report non affine access
1015 BasePtrHasNonAffine
= true;
1016 if (!AllowNonAffine
)
1017 invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, Pair
.second
,
1019 if (!KeepGoing
&& !AllowNonAffine
)
1024 if (!BasePtrHasNonAffine
)
1025 Context
.InsnToMemAcc
.insert(TempMemoryAccesses
.begin(),
1026 TempMemoryAccesses
.end());
1031 bool ScopDetection::hasBaseAffineAccesses(DetectionContext
&Context
,
1032 const SCEVUnknown
*BasePointer
,
1033 Loop
*Scope
) const {
1034 auto Shape
= std::shared_ptr
<ArrayShape
>(new ArrayShape(BasePointer
));
1036 auto Terms
= getDelinearizationTerms(Context
, BasePointer
);
1038 SE
.findArrayDimensions(Terms
, Shape
->DelinearizedSizes
,
1039 Context
.ElementSize
[BasePointer
]);
1041 if (!hasValidArraySizes(Context
, Shape
->DelinearizedSizes
, BasePointer
,
1045 return computeAccessFunctions(Context
, BasePointer
, Shape
);
1048 bool ScopDetection::hasAffineMemoryAccesses(DetectionContext
&Context
) const {
1049 // TODO: If we have an unknown access and other non-affine accesses we do
1050 // not try to delinearize them for now.
1051 if (Context
.HasUnknownAccess
&& !Context
.NonAffineAccesses
.empty())
1052 return AllowNonAffine
;
1054 for (auto &Pair
: Context
.NonAffineAccesses
) {
1055 auto *BasePointer
= Pair
.first
;
1056 auto *Scope
= Pair
.second
;
1057 if (!hasBaseAffineAccesses(Context
, BasePointer
, Scope
)) {
1067 bool ScopDetection::isValidAccess(Instruction
*Inst
, const SCEV
*AF
,
1068 const SCEVUnknown
*BP
,
1069 DetectionContext
&Context
) const {
1072 return invalid
<ReportNoBasePtr
>(Context
, /*Assert=*/true, Inst
);
1074 auto *BV
= BP
->getValue();
1075 if (isa
<UndefValue
>(BV
))
1076 return invalid
<ReportUndefBasePtr
>(Context
, /*Assert=*/true, Inst
);
1078 // FIXME: Think about allowing IntToPtrInst
1079 if (IntToPtrInst
*Inst
= dyn_cast
<IntToPtrInst
>(BV
))
1080 return invalid
<ReportIntToPtr
>(Context
, /*Assert=*/true, Inst
);
1082 // Check that the base address of the access is invariant in the current
1084 if (!isInvariant(*BV
, Context
.CurRegion
, Context
))
1085 return invalid
<ReportVariantBasePtr
>(Context
, /*Assert=*/true, BV
, Inst
);
1087 AF
= SE
.getMinusSCEV(AF
, BP
);
1090 if (!isa
<MemIntrinsic
>(Inst
)) {
1091 Size
= SE
.getElementSize(Inst
);
1094 SE
.getEffectiveSCEVType(PointerType::getInt8PtrTy(SE
.getContext()));
1095 Size
= SE
.getConstant(SizeTy
, 8);
1098 if (Context
.ElementSize
[BP
]) {
1099 if (!AllowDifferentTypes
&& Context
.ElementSize
[BP
] != Size
)
1100 return invalid
<ReportDifferentArrayElementSize
>(Context
, /*Assert=*/true,
1103 Context
.ElementSize
[BP
] = SE
.getSMinExpr(Size
, Context
.ElementSize
[BP
]);
1105 Context
.ElementSize
[BP
] = Size
;
1108 bool IsVariantInNonAffineLoop
= false;
1109 SetVector
<const Loop
*> Loops
;
1110 findLoops(AF
, Loops
);
1111 for (const Loop
*L
: Loops
)
1112 if (Context
.BoxedLoopsSet
.count(L
))
1113 IsVariantInNonAffineLoop
= true;
1115 auto *Scope
= LI
.getLoopFor(Inst
->getParent());
1116 bool IsAffine
= !IsVariantInNonAffineLoop
&& isAffine(AF
, Scope
, Context
);
1117 // Do not try to delinearize memory intrinsics and force them to be affine.
1118 if (isa
<MemIntrinsic
>(Inst
) && !IsAffine
) {
1119 return invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Inst
,
1121 } else if (PollyDelinearize
&& !IsVariantInNonAffineLoop
) {
1122 Context
.Accesses
[BP
].push_back({Inst
, AF
});
1124 if (!IsAffine
|| hasIVParams(AF
))
1125 Context
.NonAffineAccesses
.insert(
1126 std::make_pair(BP
, LI
.getLoopFor(Inst
->getParent())));
1127 } else if (!AllowNonAffine
&& !IsAffine
) {
1128 return invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Inst
,
1135 // Check if the base pointer of the memory access does alias with
1136 // any other pointer. This cannot be handled at the moment.
1138 Inst
->getAAMetadata(AATags
);
1139 AliasSet
&AS
= Context
.AST
.getAliasSetFor(
1140 MemoryLocation(BP
->getValue(), MemoryLocation::UnknownSize
, AATags
));
1142 if (!AS
.isMustAlias()) {
1143 if (PollyUseRuntimeAliasChecks
) {
1144 bool CanBuildRunTimeCheck
= true;
1145 // The run-time alias check places code that involves the base pointer at
1146 // the beginning of the SCoP. This breaks if the base pointer is defined
1147 // inside the scop. Hence, we can only create a run-time check if we are
1148 // sure the base pointer is not an instruction defined inside the scop.
1149 // However, we can ignore loads that will be hoisted.
1151 InvariantLoadsSetTy VariantLS
, InvariantLS
;
1152 // In order to detect loads which are dependent on other invariant loads
1153 // as invariant, we use fixed-point iteration method here i.e we iterate
1154 // over the alias set for arbitrary number of times until it is safe to
1155 // assume that all the invariant loads have been detected
1157 const unsigned int VariantSize
= VariantLS
.size(),
1158 InvariantSize
= InvariantLS
.size();
1160 for (const auto &Ptr
: AS
) {
1161 Instruction
*Inst
= dyn_cast
<Instruction
>(Ptr
.getValue());
1162 if (Inst
&& Context
.CurRegion
.contains(Inst
)) {
1163 auto *Load
= dyn_cast
<LoadInst
>(Inst
);
1164 if (Load
&& InvariantLS
.count(Load
))
1166 if (Load
&& isHoistableLoad(Load
, Context
.CurRegion
, LI
, SE
, DT
,
1168 if (VariantLS
.count(Load
))
1169 VariantLS
.remove(Load
);
1170 Context
.RequiredILS
.insert(Load
);
1171 InvariantLS
.insert(Load
);
1173 CanBuildRunTimeCheck
= false;
1174 VariantLS
.insert(Load
);
1179 if (InvariantSize
== InvariantLS
.size() &&
1180 VariantSize
== VariantLS
.size())
1184 if (CanBuildRunTimeCheck
)
1187 return invalid
<ReportAlias
>(Context
, /*Assert=*/true, Inst
, AS
);
1193 bool ScopDetection::isValidMemoryAccess(MemAccInst Inst
,
1194 DetectionContext
&Context
) const {
1195 Value
*Ptr
= Inst
.getPointerOperand();
1196 Loop
*L
= LI
.getLoopFor(Inst
->getParent());
1197 const SCEV
*AccessFunction
= SE
.getSCEVAtScope(Ptr
, L
);
1198 const SCEVUnknown
*BasePointer
;
1200 BasePointer
= dyn_cast
<SCEVUnknown
>(SE
.getPointerBase(AccessFunction
));
1202 return isValidAccess(Inst
, AccessFunction
, BasePointer
, Context
);
1205 bool ScopDetection::isValidInstruction(Instruction
&Inst
,
1206 DetectionContext
&Context
) const {
1207 for (auto &Op
: Inst
.operands()) {
1208 auto *OpInst
= dyn_cast
<Instruction
>(&Op
);
1213 if (isErrorBlock(*OpInst
->getParent(), Context
.CurRegion
, LI
, DT
)) {
1214 auto *PHI
= dyn_cast
<PHINode
>(OpInst
);
1216 for (User
*U
: PHI
->users()) {
1217 auto *UI
= dyn_cast
<Instruction
>(U
);
1218 if (!UI
|| !UI
->isTerminator())
1227 if (isa
<LandingPadInst
>(&Inst
) || isa
<ResumeInst
>(&Inst
))
1230 // We only check the call instruction but not invoke instruction.
1231 if (CallInst
*CI
= dyn_cast
<CallInst
>(&Inst
)) {
1232 if (isValidCallInst(*CI
, Context
))
1235 return invalid
<ReportFuncCall
>(Context
, /*Assert=*/true, &Inst
);
1238 if (!Inst
.mayReadOrWriteMemory()) {
1239 if (!isa
<AllocaInst
>(Inst
))
1242 return invalid
<ReportAlloca
>(Context
, /*Assert=*/true, &Inst
);
1245 // Check the access function.
1246 if (auto MemInst
= MemAccInst::dyn_cast(Inst
)) {
1247 Context
.hasStores
|= isa
<StoreInst
>(MemInst
);
1248 Context
.hasLoads
|= isa
<LoadInst
>(MemInst
);
1249 if (!MemInst
.isSimple())
1250 return invalid
<ReportNonSimpleMemoryAccess
>(Context
, /*Assert=*/true,
1253 return isValidMemoryAccess(MemInst
, Context
);
1256 // We do not know this instruction, therefore we assume it is invalid.
1257 return invalid
<ReportUnknownInst
>(Context
, /*Assert=*/true, &Inst
);
1260 /// Check whether @p L has exiting blocks.
1262 /// @param L The loop of interest
1264 /// @return True if the loop has exiting blocks, false otherwise.
1265 static bool hasExitingBlocks(Loop
*L
) {
1266 SmallVector
<BasicBlock
*, 4> ExitingBlocks
;
1267 L
->getExitingBlocks(ExitingBlocks
);
1268 return !ExitingBlocks
.empty();
1271 bool ScopDetection::canUseISLTripCount(Loop
*L
,
1272 DetectionContext
&Context
) const {
1273 // Ensure the loop has valid exiting blocks as well as latches, otherwise we
1274 // need to overapproximate it as a boxed loop.
1275 SmallVector
<BasicBlock
*, 4> LoopControlBlocks
;
1276 L
->getExitingBlocks(LoopControlBlocks
);
1277 L
->getLoopLatches(LoopControlBlocks
);
1278 for (BasicBlock
*ControlBB
: LoopControlBlocks
) {
1279 if (!isValidCFG(*ControlBB
, true, false, Context
))
1283 // We can use ISL to compute the trip count of L.
1287 bool ScopDetection::isValidLoop(Loop
*L
, DetectionContext
&Context
) const {
1288 // Loops that contain part but not all of the blocks of a region cannot be
1289 // handled by the schedule generation. Such loop constructs can happen
1290 // because a region can contain BBs that have no path to the exit block
1291 // (Infinite loops, UnreachableInst), but such blocks are never part of a
1295 // | Loop Header | <-----------.
1296 // --------------- |
1298 // _______________ ______________
1299 // | RegionEntry |-----> | RegionExit |----->
1300 // --------------- --------------
1303 // | EndlessLoop | <--.
1304 // --------------- |
1308 // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
1309 // neither entirely contained in the region RegionEntry->RegionExit
1310 // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
1312 // The block EndlessLoop is contained in the region because Region::contains
1313 // tests whether it is not dominated by RegionExit. This is probably to not
1314 // having to query the PostdominatorTree. Instead of an endless loop, a dead
1315 // end can also be formed by an UnreachableInst. This case is already caught
1316 // by isErrorBlock(). We hence only have to reject endless loops here.
1317 if (!hasExitingBlocks(L
))
1318 return invalid
<ReportLoopHasNoExit
>(Context
, /*Assert=*/true, L
);
1320 // The algorithm for domain construction assumes that loops has only a single
1321 // exit block (and hence corresponds to a subregion). Note that we cannot use
1322 // L->getExitBlock() because it does not check whether all exiting edges point
1324 SmallVector
<BasicBlock
*, 4> ExitBlocks
;
1325 L
->getExitBlocks(ExitBlocks
);
1326 BasicBlock
*TheExitBlock
= ExitBlocks
[0];
1327 for (BasicBlock
*ExitBB
: ExitBlocks
) {
1328 if (TheExitBlock
!= ExitBB
)
1329 return invalid
<ReportLoopHasMultipleExits
>(Context
, /*Assert=*/true, L
);
1332 if (canUseISLTripCount(L
, Context
))
1335 if (AllowNonAffineSubLoops
&& AllowNonAffineSubRegions
) {
1336 Region
*R
= RI
.getRegionFor(L
->getHeader());
1337 while (R
!= &Context
.CurRegion
&& !R
->contains(L
))
1340 if (addOverApproximatedRegion(R
, Context
))
1344 const SCEV
*LoopCount
= SE
.getBackedgeTakenCount(L
);
1345 return invalid
<ReportLoopBound
>(Context
, /*Assert=*/true, L
, LoopCount
);
1348 /// Return the number of loops in @p L (incl. @p L) that have a trip
1349 /// count that is not known to be less than @MinProfitableTrips.
1350 ScopDetection::LoopStats
1351 ScopDetection::countBeneficialSubLoops(Loop
*L
, ScalarEvolution
&SE
,
1352 unsigned MinProfitableTrips
) {
1353 auto *TripCount
= SE
.getBackedgeTakenCount(L
);
1356 int MaxLoopDepth
= 1;
1357 if (MinProfitableTrips
> 0)
1358 if (auto *TripCountC
= dyn_cast
<SCEVConstant
>(TripCount
))
1359 if (TripCountC
->getType()->getScalarSizeInBits() <= 64)
1360 if (TripCountC
->getValue()->getZExtValue() <= MinProfitableTrips
)
1363 for (auto &SubLoop
: *L
) {
1364 LoopStats Stats
= countBeneficialSubLoops(SubLoop
, SE
, MinProfitableTrips
);
1365 NumLoops
+= Stats
.NumLoops
;
1366 MaxLoopDepth
= std::max(MaxLoopDepth
, Stats
.MaxDepth
+ 1);
1369 return {NumLoops
, MaxLoopDepth
};
1372 ScopDetection::LoopStats
1373 ScopDetection::countBeneficialLoops(Region
*R
, ScalarEvolution
&SE
,
1374 LoopInfo
&LI
, unsigned MinProfitableTrips
) {
1376 int MaxLoopDepth
= 0;
1378 auto L
= LI
.getLoopFor(R
->getEntry());
1380 // If L is fully contained in R, move to first loop surrounding R. Otherwise,
1381 // L is either nullptr or already surrounding R.
1382 if (L
&& R
->contains(L
)) {
1383 L
= R
->outermostLoopInRegion(L
);
1384 L
= L
->getParentLoop();
1388 L
? L
->getSubLoopsVector() : std::vector
<Loop
*>(LI
.begin(), LI
.end());
1390 for (auto &SubLoop
: SubLoops
)
1391 if (R
->contains(SubLoop
)) {
1393 countBeneficialSubLoops(SubLoop
, SE
, MinProfitableTrips
);
1394 LoopNum
+= Stats
.NumLoops
;
1395 MaxLoopDepth
= std::max(MaxLoopDepth
, Stats
.MaxDepth
);
1398 return {LoopNum
, MaxLoopDepth
};
1401 Region
*ScopDetection::expandRegion(Region
&R
) {
1402 // Initial no valid region was found (greater than R)
1403 std::unique_ptr
<Region
> LastValidRegion
;
1404 auto ExpandedRegion
= std::unique_ptr
<Region
>(R
.getExpandedRegion());
1406 LLVM_DEBUG(dbgs() << "\tExpanding " << R
.getNameStr() << "\n");
1408 while (ExpandedRegion
) {
1409 const auto &It
= DetectionContextMap
.insert(std::make_pair(
1410 getBBPairForRegion(ExpandedRegion
.get()),
1411 DetectionContext(*ExpandedRegion
, AA
, false /*verifying*/)));
1412 DetectionContext
&Context
= It
.first
->second
;
1413 LLVM_DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion
->getNameStr() << "\n");
1414 // Only expand when we did not collect errors.
1416 if (!Context
.Log
.hasErrors()) {
1417 // If the exit is valid check all blocks
1418 // - if true, a valid region was found => store it + keep expanding
1419 // - if false, .tbd. => stop (should this really end the loop?)
1420 if (!allBlocksValid(Context
) || Context
.Log
.hasErrors()) {
1421 removeCachedResults(*ExpandedRegion
);
1422 DetectionContextMap
.erase(It
.first
);
1426 // Store this region, because it is the greatest valid (encountered so
1428 if (LastValidRegion
) {
1429 removeCachedResults(*LastValidRegion
);
1430 DetectionContextMap
.erase(getBBPairForRegion(LastValidRegion
.get()));
1432 LastValidRegion
= std::move(ExpandedRegion
);
1434 // Create and test the next greater region (if any)
1436 std::unique_ptr
<Region
>(LastValidRegion
->getExpandedRegion());
1439 // Create and test the next greater region (if any)
1440 removeCachedResults(*ExpandedRegion
);
1441 DetectionContextMap
.erase(It
.first
);
1443 std::unique_ptr
<Region
>(ExpandedRegion
->getExpandedRegion());
1448 if (LastValidRegion
)
1449 dbgs() << "\tto " << LastValidRegion
->getNameStr() << "\n";
1451 dbgs() << "\tExpanding " << R
.getNameStr() << " failed\n";
1454 return LastValidRegion
.release();
1457 static bool regionWithoutLoops(Region
&R
, LoopInfo
&LI
) {
1458 for (const BasicBlock
*BB
: R
.blocks())
1459 if (R
.contains(LI
.getLoopFor(BB
)))
1465 void ScopDetection::removeCachedResultsRecursively(const Region
&R
) {
1466 for (auto &SubRegion
: R
) {
1467 if (ValidRegions
.count(SubRegion
.get())) {
1468 removeCachedResults(*SubRegion
.get());
1470 removeCachedResultsRecursively(*SubRegion
);
1474 void ScopDetection::removeCachedResults(const Region
&R
) {
1475 ValidRegions
.remove(&R
);
1478 void ScopDetection::findScops(Region
&R
) {
1479 const auto &It
= DetectionContextMap
.insert(std::make_pair(
1480 getBBPairForRegion(&R
), DetectionContext(R
, AA
, false /*verifying*/)));
1481 DetectionContext
&Context
= It
.first
->second
;
1483 bool RegionIsValid
= false;
1484 if (!PollyProcessUnprofitable
&& regionWithoutLoops(R
, LI
))
1485 invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &R
);
1487 RegionIsValid
= isValidRegion(Context
);
1489 bool HasErrors
= !RegionIsValid
|| Context
.Log
.size() > 0;
1492 removeCachedResults(R
);
1494 ValidRegions
.insert(&R
);
1498 for (auto &SubRegion
: R
)
1499 findScops(*SubRegion
);
1501 // Try to expand regions.
1503 // As the region tree normally only contains canonical regions, non canonical
1504 // regions that form a Scop are not found. Therefore, those non canonical
1505 // regions are checked by expanding the canonical ones.
1507 std::vector
<Region
*> ToExpand
;
1509 for (auto &SubRegion
: R
)
1510 ToExpand
.push_back(SubRegion
.get());
1512 for (Region
*CurrentRegion
: ToExpand
) {
1513 // Skip invalid regions. Regions may become invalid, if they are element of
1514 // an already expanded region.
1515 if (!ValidRegions
.count(CurrentRegion
))
1518 // Skip regions that had errors.
1519 bool HadErrors
= lookupRejectionLog(CurrentRegion
)->hasErrors();
1523 Region
*ExpandedR
= expandRegion(*CurrentRegion
);
1528 R
.addSubRegion(ExpandedR
, true);
1529 ValidRegions
.insert(ExpandedR
);
1530 removeCachedResults(*CurrentRegion
);
1531 removeCachedResultsRecursively(*ExpandedR
);
1535 bool ScopDetection::allBlocksValid(DetectionContext
&Context
) const {
1536 Region
&CurRegion
= Context
.CurRegion
;
1538 for (const BasicBlock
*BB
: CurRegion
.blocks()) {
1539 Loop
*L
= LI
.getLoopFor(BB
);
1540 if (L
&& L
->getHeader() == BB
) {
1541 if (CurRegion
.contains(L
)) {
1542 if (!isValidLoop(L
, Context
) && !KeepGoing
)
1545 SmallVector
<BasicBlock
*, 1> Latches
;
1546 L
->getLoopLatches(Latches
);
1547 for (BasicBlock
*Latch
: Latches
)
1548 if (CurRegion
.contains(Latch
))
1549 return invalid
<ReportLoopOnlySomeLatches
>(Context
, /*Assert=*/true,
1555 for (BasicBlock
*BB
: CurRegion
.blocks()) {
1556 bool IsErrorBlock
= isErrorBlock(*BB
, CurRegion
, LI
, DT
);
1558 // Also check exception blocks (and possibly register them as non-affine
1559 // regions). Even though exception blocks are not modeled, we use them
1560 // to forward-propagate domain constraints during ScopInfo construction.
1561 if (!isValidCFG(*BB
, false, IsErrorBlock
, Context
) && !KeepGoing
)
1567 for (BasicBlock::iterator I
= BB
->begin(), E
= --BB
->end(); I
!= E
; ++I
)
1568 if (!isValidInstruction(*I
, Context
) && !KeepGoing
)
1572 if (!hasAffineMemoryAccesses(Context
))
1578 bool ScopDetection::hasSufficientCompute(DetectionContext
&Context
,
1579 int NumLoops
) const {
1585 for (auto *BB
: Context
.CurRegion
.blocks())
1586 if (Context
.CurRegion
.contains(LI
.getLoopFor(BB
)))
1587 InstCount
+= BB
->size();
1589 InstCount
= InstCount
/ NumLoops
;
1591 return InstCount
>= ProfitabilityMinPerLoopInstructions
;
1594 bool ScopDetection::hasPossiblyDistributableLoop(
1595 DetectionContext
&Context
) const {
1596 for (auto *BB
: Context
.CurRegion
.blocks()) {
1597 auto *L
= LI
.getLoopFor(BB
);
1598 if (!Context
.CurRegion
.contains(L
))
1600 if (Context
.BoxedLoopsSet
.count(L
))
1602 unsigned StmtsWithStoresInLoops
= 0;
1603 for (auto *LBB
: L
->blocks()) {
1604 bool MemStore
= false;
1605 for (auto &I
: *LBB
)
1606 MemStore
|= isa
<StoreInst
>(&I
);
1607 StmtsWithStoresInLoops
+= MemStore
;
1609 return (StmtsWithStoresInLoops
> 1);
1614 bool ScopDetection::isProfitableRegion(DetectionContext
&Context
) const {
1615 Region
&CurRegion
= Context
.CurRegion
;
1617 if (PollyProcessUnprofitable
)
1620 // We can probably not do a lot on scops that only write or only read
1622 if (!Context
.hasStores
|| !Context
.hasLoads
)
1623 return invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &CurRegion
);
1626 countBeneficialLoops(&CurRegion
, SE
, LI
, MIN_LOOP_TRIP_COUNT
).NumLoops
;
1627 int NumAffineLoops
= NumLoops
- Context
.BoxedLoopsSet
.size();
1629 // Scops with at least two loops may allow either loop fusion or tiling and
1630 // are consequently interesting to look at.
1631 if (NumAffineLoops
>= 2)
1634 // A loop with multiple non-trivial blocks might be amendable to distribution.
1635 if (NumAffineLoops
== 1 && hasPossiblyDistributableLoop(Context
))
1638 // Scops that contain a loop with a non-trivial amount of computation per
1639 // loop-iteration are interesting as we may be able to parallelize such
1640 // loops. Individual loops that have only a small amount of computation
1641 // per-iteration are performance-wise very fragile as any change to the
1642 // loop induction variables may affect performance. To not cause spurious
1643 // performance regressions, we do not consider such loops.
1644 if (NumAffineLoops
== 1 && hasSufficientCompute(Context
, NumLoops
))
1647 return invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &CurRegion
);
1650 bool ScopDetection::isValidRegion(DetectionContext
&Context
) const {
1651 Region
&CurRegion
= Context
.CurRegion
;
1653 LLVM_DEBUG(dbgs() << "Checking region: " << CurRegion
.getNameStr() << "\n\t");
1655 if (!PollyAllowFullFunction
&& CurRegion
.isTopLevelRegion()) {
1656 LLVM_DEBUG(dbgs() << "Top level region is invalid\n");
1661 if (CurRegion
.getExit() &&
1662 isa
<UnreachableInst
>(CurRegion
.getExit()->getTerminator())) {
1663 LLVM_DEBUG(dbgs() << "Unreachable in exit\n");
1664 return invalid
<ReportUnreachableInExit
>(Context
, /*Assert=*/true,
1665 CurRegion
.getExit(), DbgLoc
);
1668 if (!CurRegion
.getEntry()->getName().count(OnlyRegion
)) {
1670 dbgs() << "Region entry does not match -polly-region-only";
1676 // SCoP cannot contain the entry block of the function, because we need
1677 // to insert alloca instruction there when translate scalar to array.
1678 if (!PollyAllowFullFunction
&&
1679 CurRegion
.getEntry() ==
1680 &(CurRegion
.getEntry()->getParent()->getEntryBlock()))
1681 return invalid
<ReportEntry
>(Context
, /*Assert=*/true, CurRegion
.getEntry());
1683 if (!allBlocksValid(Context
))
1686 if (!isReducibleRegion(CurRegion
, DbgLoc
))
1687 return invalid
<ReportIrreducibleRegion
>(Context
, /*Assert=*/true,
1688 &CurRegion
, DbgLoc
);
1690 LLVM_DEBUG(dbgs() << "OK\n");
1694 void ScopDetection::markFunctionAsInvalid(Function
*F
) {
1695 F
->addFnAttr(PollySkipFnAttr
);
1698 bool ScopDetection::isValidFunction(Function
&F
) {
1699 return !F
.hasFnAttribute(PollySkipFnAttr
);
1702 void ScopDetection::printLocations(Function
&F
) {
1703 for (const Region
*R
: *this) {
1704 unsigned LineEntry
, LineExit
;
1705 std::string FileName
;
1707 getDebugLocation(R
, LineEntry
, LineExit
, FileName
);
1708 DiagnosticScopFound
Diagnostic(F
, FileName
, LineEntry
, LineExit
);
1709 F
.getContext().diagnose(Diagnostic
);
1713 void ScopDetection::emitMissedRemarks(const Function
&F
) {
1714 for (auto &DIt
: DetectionContextMap
) {
1715 auto &DC
= DIt
.getSecond();
1716 if (DC
.Log
.hasErrors())
1717 emitRejectionRemarks(DIt
.getFirst(), DC
.Log
, ORE
);
1721 bool ScopDetection::isReducibleRegion(Region
&R
, DebugLoc
&DbgLoc
) const {
1722 /// Enum for coloring BBs in Region.
1724 /// WHITE - Unvisited BB in DFS walk.
1725 /// GREY - BBs which are currently on the DFS stack for processing.
1726 /// BLACK - Visited and completely processed BB.
1727 enum Color
{ WHITE
, GREY
, BLACK
};
1729 BasicBlock
*REntry
= R
.getEntry();
1730 BasicBlock
*RExit
= R
.getExit();
1731 // Map to match the color of a BasicBlock during the DFS walk.
1732 DenseMap
<const BasicBlock
*, Color
> BBColorMap
;
1733 // Stack keeping track of current BB and index of next child to be processed.
1734 std::stack
<std::pair
<BasicBlock
*, unsigned>> DFSStack
;
1736 unsigned AdjacentBlockIndex
= 0;
1737 BasicBlock
*CurrBB
, *SuccBB
;
1740 // Initialize the map for all BB with WHITE color.
1741 for (auto *BB
: R
.blocks())
1742 BBColorMap
[BB
] = WHITE
;
1744 // Process the entry block of the Region.
1745 BBColorMap
[CurrBB
] = GREY
;
1746 DFSStack
.push(std::make_pair(CurrBB
, 0));
1748 while (!DFSStack
.empty()) {
1749 // Get next BB on stack to be processed.
1750 CurrBB
= DFSStack
.top().first
;
1751 AdjacentBlockIndex
= DFSStack
.top().second
;
1754 // Loop to iterate over the successors of current BB.
1755 const TerminatorInst
*TInst
= CurrBB
->getTerminator();
1756 unsigned NSucc
= TInst
->getNumSuccessors();
1757 for (unsigned I
= AdjacentBlockIndex
; I
< NSucc
;
1758 ++I
, ++AdjacentBlockIndex
) {
1759 SuccBB
= TInst
->getSuccessor(I
);
1761 // Checks for region exit block and self-loops in BB.
1762 if (SuccBB
== RExit
|| SuccBB
== CurrBB
)
1765 // WHITE indicates an unvisited BB in DFS walk.
1766 if (BBColorMap
[SuccBB
] == WHITE
) {
1767 // Push the current BB and the index of the next child to be visited.
1768 DFSStack
.push(std::make_pair(CurrBB
, I
+ 1));
1769 // Push the next BB to be processed.
1770 DFSStack
.push(std::make_pair(SuccBB
, 0));
1771 // First time the BB is being processed.
1772 BBColorMap
[SuccBB
] = GREY
;
1774 } else if (BBColorMap
[SuccBB
] == GREY
) {
1775 // GREY indicates a loop in the control flow.
1776 // If the destination dominates the source, it is a natural loop
1777 // else, an irreducible control flow in the region is detected.
1778 if (!DT
.dominates(SuccBB
, CurrBB
)) {
1779 // Get debug info of instruction which causes irregular control flow.
1780 DbgLoc
= TInst
->getDebugLoc();
1786 // If all children of current BB have been processed,
1787 // then mark that BB as fully processed.
1788 if (AdjacentBlockIndex
== NSucc
)
1789 BBColorMap
[CurrBB
] = BLACK
;
1795 static void updateLoopCountStatistic(ScopDetection::LoopStats Stats
,
1796 bool OnlyProfitable
) {
1797 if (!OnlyProfitable
) {
1798 NumLoopsInScop
+= Stats
.NumLoops
;
1800 std::max(MaxNumLoopsInScop
.getValue(), (unsigned)Stats
.NumLoops
);
1801 if (Stats
.MaxDepth
== 0)
1802 NumScopsDepthZero
++;
1803 else if (Stats
.MaxDepth
== 1)
1805 else if (Stats
.MaxDepth
== 2)
1807 else if (Stats
.MaxDepth
== 3)
1808 NumScopsDepthThree
++;
1809 else if (Stats
.MaxDepth
== 4)
1810 NumScopsDepthFour
++;
1811 else if (Stats
.MaxDepth
== 5)
1812 NumScopsDepthFive
++;
1814 NumScopsDepthLarger
++;
1816 NumLoopsInProfScop
+= Stats
.NumLoops
;
1817 MaxNumLoopsInProfScop
=
1818 std::max(MaxNumLoopsInProfScop
.getValue(), (unsigned)Stats
.NumLoops
);
1819 if (Stats
.MaxDepth
== 0)
1820 NumProfScopsDepthZero
++;
1821 else if (Stats
.MaxDepth
== 1)
1822 NumProfScopsDepthOne
++;
1823 else if (Stats
.MaxDepth
== 2)
1824 NumProfScopsDepthTwo
++;
1825 else if (Stats
.MaxDepth
== 3)
1826 NumProfScopsDepthThree
++;
1827 else if (Stats
.MaxDepth
== 4)
1828 NumProfScopsDepthFour
++;
1829 else if (Stats
.MaxDepth
== 5)
1830 NumProfScopsDepthFive
++;
1832 NumProfScopsDepthLarger
++;
1836 ScopDetection::DetectionContext
*
1837 ScopDetection::getDetectionContext(const Region
*R
) const {
1838 auto DCMIt
= DetectionContextMap
.find(getBBPairForRegion(R
));
1839 if (DCMIt
== DetectionContextMap
.end())
1841 return &DCMIt
->second
;
1844 const RejectLog
*ScopDetection::lookupRejectionLog(const Region
*R
) const {
1845 const DetectionContext
*DC
= getDetectionContext(R
);
1846 return DC
? &DC
->Log
: nullptr;
1849 void ScopDetection::verifyRegion(const Region
&R
) const {
1850 assert(isMaxRegionInScop(R
) && "Expect R is a valid region.");
1852 DetectionContext
Context(const_cast<Region
&>(R
), AA
, true /*verifying*/);
1853 isValidRegion(Context
);
1856 void ScopDetection::verifyAnalysis() const {
1860 for (const Region
*R
: ValidRegions
)
1864 bool ScopDetectionWrapperPass::runOnFunction(Function
&F
) {
1865 auto &LI
= getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
1866 auto &RI
= getAnalysis
<RegionInfoPass
>().getRegionInfo();
1867 auto &AA
= getAnalysis
<AAResultsWrapperPass
>().getAAResults();
1868 auto &SE
= getAnalysis
<ScalarEvolutionWrapperPass
>().getSE();
1869 auto &DT
= getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
1870 auto &ORE
= getAnalysis
<OptimizationRemarkEmitterWrapperPass
>().getORE();
1871 Result
.reset(new ScopDetection(F
, DT
, SE
, LI
, RI
, AA
, ORE
));
1875 void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage
&AU
) const {
1876 AU
.addRequired
<LoopInfoWrapperPass
>();
1877 AU
.addRequiredTransitive
<ScalarEvolutionWrapperPass
>();
1878 AU
.addRequired
<DominatorTreeWrapperPass
>();
1879 AU
.addRequired
<OptimizationRemarkEmitterWrapperPass
>();
1880 // We also need AA and RegionInfo when we are verifying analysis.
1881 AU
.addRequiredTransitive
<AAResultsWrapperPass
>();
1882 AU
.addRequiredTransitive
<RegionInfoPass
>();
1883 AU
.setPreservesAll();
1886 void ScopDetectionWrapperPass::print(raw_ostream
&OS
, const Module
*) const {
1887 for (const Region
*R
: Result
->ValidRegions
)
1888 OS
<< "Valid Region for Scop: " << R
->getNameStr() << '\n';
1893 ScopDetectionWrapperPass::ScopDetectionWrapperPass() : FunctionPass(ID
) {
1894 // Disable runtime alias checks if we ignore aliasing all together.
1896 PollyUseRuntimeAliasChecks
= false;
1899 ScopAnalysis::ScopAnalysis() {
1900 // Disable runtime alias checks if we ignore aliasing all together.
1902 PollyUseRuntimeAliasChecks
= false;
1905 void ScopDetectionWrapperPass::releaseMemory() { Result
.reset(); }
1907 char ScopDetectionWrapperPass::ID
;
1909 AnalysisKey
ScopAnalysis::Key
;
1911 ScopDetection
ScopAnalysis::run(Function
&F
, FunctionAnalysisManager
&FAM
) {
1912 auto &LI
= FAM
.getResult
<LoopAnalysis
>(F
);
1913 auto &RI
= FAM
.getResult
<RegionInfoAnalysis
>(F
);
1914 auto &AA
= FAM
.getResult
<AAManager
>(F
);
1915 auto &SE
= FAM
.getResult
<ScalarEvolutionAnalysis
>(F
);
1916 auto &DT
= FAM
.getResult
<DominatorTreeAnalysis
>(F
);
1917 auto &ORE
= FAM
.getResult
<OptimizationRemarkEmitterAnalysis
>(F
);
1918 return {F
, DT
, SE
, LI
, RI
, AA
, ORE
};
1921 PreservedAnalyses
ScopAnalysisPrinterPass::run(Function
&F
,
1922 FunctionAnalysisManager
&FAM
) {
1923 OS
<< "Detected Scops in Function " << F
.getName() << "\n";
1924 auto &SD
= FAM
.getResult
<ScopAnalysis
>(F
);
1925 for (const Region
*R
: SD
.ValidRegions
)
1926 OS
<< "Valid Region for Scop: " << R
->getNameStr() << '\n';
1929 return PreservedAnalyses::all();
1932 Pass
*polly::createScopDetectionWrapperPassPass() {
1933 return new ScopDetectionWrapperPass();
1936 INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass
, "polly-detect",
1937 "Polly - Detect static control parts (SCoPs)", false,
1939 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
);
1940 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
);
1941 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass
);
1942 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
);
1943 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
);
1944 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass
);
1945 INITIALIZE_PASS_END(ScopDetectionWrapperPass
, "polly-detect",
1946 "Polly - Detect static control parts (SCoPs)", false, false)