1 //===----- ScopDetection.cpp - Detect Scops --------------------*- C++ -*-===//
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 fullfills 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/CodeGen/CodeGeneration.h"
49 #include "polly/LinkAllPasses.h"
50 #include "polly/Options.h"
51 #include "polly/ScopDetectionDiagnostic.h"
52 #include "polly/Support/SCEVValidator.h"
53 #include "polly/Support/ScopLocation.h"
54 #include "llvm/ADT/Statistic.h"
55 #include "llvm/Analysis/AliasAnalysis.h"
56 #include "llvm/Analysis/LoopInfo.h"
57 #include "llvm/Analysis/PostDominators.h"
58 #include "llvm/Analysis/RegionIterator.h"
59 #include "llvm/Analysis/ScalarEvolution.h"
60 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
61 #include "llvm/IR/DebugInfo.h"
62 #include "llvm/IR/DiagnosticInfo.h"
63 #include "llvm/IR/DiagnosticPrinter.h"
64 #include "llvm/IR/IntrinsicInst.h"
65 #include "llvm/IR/LLVMContext.h"
66 #include "llvm/Support/Debug.h"
71 using namespace polly
;
73 #define DEBUG_TYPE "polly-detect"
75 // This option is set to a very high value, as analyzing such loops increases
76 // compile time on several cases. For experiments that enable this option,
77 // a value of around 40 has been working to avoid run-time regressions with
78 // Polly while still exposing interesting optimization opportunities.
79 static cl::opt
<int> ProfitabilityMinPerLoopInstructions(
80 "polly-detect-profitability-min-per-loop-insts",
81 cl::desc("The minimal number of per-loop instructions before a single loop "
82 "region is considered profitable"),
83 cl::Hidden
, cl::ValueRequired
, cl::init(100000000), cl::cat(PollyCategory
));
85 bool polly::PollyProcessUnprofitable
;
86 static cl::opt
<bool, true> XPollyProcessUnprofitable(
87 "polly-process-unprofitable",
89 "Process scops that are unlikely to benefit from Polly optimizations."),
90 cl::location(PollyProcessUnprofitable
), cl::init(false), cl::ZeroOrMore
,
91 cl::cat(PollyCategory
));
93 static cl::opt
<std::string
> OnlyFunction(
95 cl::desc("Only run on functions that contain a certain string"),
96 cl::value_desc("string"), cl::ValueRequired
, cl::init(""),
97 cl::cat(PollyCategory
));
99 static cl::opt
<std::string
> OnlyRegion(
101 cl::desc("Only run on certain regions (The provided identifier must "
102 "appear in the name of the region's entry block"),
103 cl::value_desc("identifier"), cl::ValueRequired
, cl::init(""),
104 cl::cat(PollyCategory
));
107 IgnoreAliasing("polly-ignore-aliasing",
108 cl::desc("Ignore possible aliasing of the array bases"),
109 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
110 cl::cat(PollyCategory
));
112 bool polly::PollyUseRuntimeAliasChecks
;
113 static cl::opt
<bool, true> XPollyUseRuntimeAliasChecks(
114 "polly-use-runtime-alias-checks",
115 cl::desc("Use runtime alias checks to resolve possible aliasing."),
116 cl::location(PollyUseRuntimeAliasChecks
), cl::Hidden
, cl::ZeroOrMore
,
117 cl::init(true), cl::cat(PollyCategory
));
120 ReportLevel("polly-report",
121 cl::desc("Print information about the activities of Polly"),
122 cl::init(false), cl::ZeroOrMore
, cl::cat(PollyCategory
));
124 static cl::opt
<bool> AllowDifferentTypes(
125 "polly-allow-differing-element-types",
126 cl::desc("Allow different element types for array accesses"), cl::Hidden
,
127 cl::init(true), cl::ZeroOrMore
, cl::cat(PollyCategory
));
130 AllowNonAffine("polly-allow-nonaffine",
131 cl::desc("Allow non affine access functions in arrays"),
132 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
133 cl::cat(PollyCategory
));
136 AllowModrefCall("polly-allow-modref-calls",
137 cl::desc("Allow functions with known modref behavior"),
138 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
139 cl::cat(PollyCategory
));
141 static cl::opt
<bool> AllowNonAffineSubRegions(
142 "polly-allow-nonaffine-branches",
143 cl::desc("Allow non affine conditions for branches"), cl::Hidden
,
144 cl::init(true), cl::ZeroOrMore
, cl::cat(PollyCategory
));
147 AllowNonAffineSubLoops("polly-allow-nonaffine-loops",
148 cl::desc("Allow non affine conditions for loops"),
149 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
150 cl::cat(PollyCategory
));
152 static cl::opt
<bool, true>
153 TrackFailures("polly-detect-track-failures",
154 cl::desc("Track failure strings in detecting scop regions"),
155 cl::location(PollyTrackFailures
), cl::Hidden
, cl::ZeroOrMore
,
156 cl::init(true), cl::cat(PollyCategory
));
158 static cl::opt
<bool> KeepGoing("polly-detect-keep-going",
159 cl::desc("Do not fail on the first error."),
160 cl::Hidden
, cl::ZeroOrMore
, cl::init(false),
161 cl::cat(PollyCategory
));
163 static cl::opt
<bool, true>
164 PollyDelinearizeX("polly-delinearize",
165 cl::desc("Delinearize array access functions"),
166 cl::location(PollyDelinearize
), cl::Hidden
,
167 cl::ZeroOrMore
, cl::init(true), cl::cat(PollyCategory
));
170 VerifyScops("polly-detect-verify",
171 cl::desc("Verify the detected SCoPs after each transformation"),
172 cl::Hidden
, cl::init(false), cl::ZeroOrMore
,
173 cl::cat(PollyCategory
));
175 bool polly::PollyInvariantLoadHoisting
;
176 static cl::opt
<bool, true> XPollyInvariantLoadHoisting(
177 "polly-invariant-load-hoisting", cl::desc("Hoist invariant loads."),
178 cl::location(PollyInvariantLoadHoisting
), cl::Hidden
, cl::ZeroOrMore
,
179 cl::init(false), cl::cat(PollyCategory
));
181 /// The minimal trip count under which loops are considered unprofitable.
182 static const unsigned MIN_LOOP_TRIP_COUNT
= 8;
184 bool polly::PollyTrackFailures
= false;
185 bool polly::PollyDelinearize
= false;
186 StringRef
polly::PollySkipFnAttr
= "polly.skip.fn";
188 //===----------------------------------------------------------------------===//
191 STATISTIC(ValidRegion
, "Number of regions that a valid part of Scop");
193 class DiagnosticScopFound
: public DiagnosticInfo
{
195 static int PluginDiagnosticKind
;
198 std::string FileName
;
199 unsigned EntryLine
, ExitLine
;
202 DiagnosticScopFound(Function
&F
, std::string FileName
, unsigned EntryLine
,
204 : DiagnosticInfo(PluginDiagnosticKind
, DS_Note
), F(F
), FileName(FileName
),
205 EntryLine(EntryLine
), ExitLine(ExitLine
) {}
207 virtual void print(DiagnosticPrinter
&DP
) const;
209 static bool classof(const DiagnosticInfo
*DI
) {
210 return DI
->getKind() == PluginDiagnosticKind
;
214 int DiagnosticScopFound::PluginDiagnosticKind
=
215 getNextAvailablePluginDiagnosticKind();
217 void DiagnosticScopFound::print(DiagnosticPrinter
&DP
) const {
218 DP
<< "Polly detected an optimizable loop region (scop) in function '" << F
221 if (FileName
.empty()) {
222 DP
<< "Scop location is unknown. Compile with debug info "
223 "(-g) to get more precise information. ";
227 DP
<< FileName
<< ":" << EntryLine
<< ": Start of scop\n";
228 DP
<< FileName
<< ":" << ExitLine
<< ": End of scop";
231 //===----------------------------------------------------------------------===//
234 ScopDetection::ScopDetection() : FunctionPass(ID
) {
235 // Disable runtime alias checks if we ignore aliasing all together.
237 PollyUseRuntimeAliasChecks
= false;
240 template <class RR
, typename
... Args
>
241 inline bool ScopDetection::invalid(DetectionContext
&Context
, bool Assert
,
242 Args
&&... Arguments
) const {
244 if (!Context
.Verifying
) {
245 RejectLog
&Log
= Context
.Log
;
246 std::shared_ptr
<RR
> RejectReason
= std::make_shared
<RR
>(Arguments
...);
248 if (PollyTrackFailures
)
249 Log
.report(RejectReason
);
251 DEBUG(dbgs() << RejectReason
->getMessage());
252 DEBUG(dbgs() << "\n");
254 assert(!Assert
&& "Verification of detected scop failed");
260 bool ScopDetection::isMaxRegionInScop(const Region
&R
, bool Verify
) const {
261 if (!ValidRegions
.count(&R
))
265 DetectionContextMap
.erase(getBBPairForRegion(&R
));
266 const auto &It
= DetectionContextMap
.insert(std::make_pair(
267 getBBPairForRegion(&R
),
268 DetectionContext(const_cast<Region
&>(R
), *AA
, false /*verifying*/)));
269 DetectionContext
&Context
= It
.first
->second
;
270 return isValidRegion(Context
);
276 std::string
ScopDetection::regionIsInvalidBecause(const Region
*R
) const {
277 // Get the first error we found. Even in keep-going mode, this is the first
278 // reason that caused the candidate to be rejected.
279 auto *Log
= lookupRejectionLog(R
);
281 // This can happen when we marked a region invalid, but didn't track
283 if (!Log
|| !Log
->hasErrors())
286 RejectReasonPtr RR
= *Log
->begin();
287 return RR
->getMessage();
290 bool ScopDetection::addOverApproximatedRegion(Region
*AR
,
291 DetectionContext
&Context
) const {
293 // If we already know about Ar we can exit.
294 if (!Context
.NonAffineSubRegionSet
.insert(AR
))
297 // All loops in the region have to be overapproximated too if there
298 // are accesses that depend on the iteration count.
300 for (BasicBlock
*BB
: AR
->blocks()) {
301 Loop
*L
= LI
->getLoopFor(BB
);
303 Context
.BoxedLoopsSet
.insert(L
);
306 return (AllowNonAffineSubLoops
|| Context
.BoxedLoopsSet
.empty());
309 bool ScopDetection::onlyValidRequiredInvariantLoads(
310 InvariantLoadsSetTy
&RequiredILS
, DetectionContext
&Context
) const {
311 Region
&CurRegion
= Context
.CurRegion
;
313 if (!PollyInvariantLoadHoisting
&& !RequiredILS
.empty())
316 for (LoadInst
*Load
: RequiredILS
)
317 if (!isHoistableLoad(Load
, CurRegion
, *LI
, *SE
))
320 Context
.RequiredILS
.insert(RequiredILS
.begin(), RequiredILS
.end());
325 bool ScopDetection::isAffine(const SCEV
*S
, Loop
*Scope
,
326 DetectionContext
&Context
) const {
328 InvariantLoadsSetTy AccessILS
;
329 if (!isAffineExpr(&Context
.CurRegion
, Scope
, S
, *SE
, &AccessILS
))
332 if (!onlyValidRequiredInvariantLoads(AccessILS
, Context
))
338 bool ScopDetection::isValidSwitch(BasicBlock
&BB
, SwitchInst
*SI
,
339 Value
*Condition
, bool IsLoopBranch
,
340 DetectionContext
&Context
) const {
341 Loop
*L
= LI
->getLoopFor(&BB
);
342 const SCEV
*ConditionSCEV
= SE
->getSCEVAtScope(Condition
, L
);
344 if (IsLoopBranch
&& L
->isLoopLatch(&BB
))
347 if (isAffine(ConditionSCEV
, L
, Context
))
350 if (AllowNonAffineSubRegions
&&
351 addOverApproximatedRegion(RI
->getRegionFor(&BB
), Context
))
354 return invalid
<ReportNonAffBranch
>(Context
, /*Assert=*/true, &BB
,
355 ConditionSCEV
, ConditionSCEV
, SI
);
358 bool ScopDetection::isValidBranch(BasicBlock
&BB
, BranchInst
*BI
,
359 Value
*Condition
, bool IsLoopBranch
,
360 DetectionContext
&Context
) const {
362 // Constant integer conditions are always affine.
363 if (isa
<ConstantInt
>(Condition
))
366 if (BinaryOperator
*BinOp
= dyn_cast
<BinaryOperator
>(Condition
)) {
367 auto Opcode
= BinOp
->getOpcode();
368 if (Opcode
== Instruction::And
|| Opcode
== Instruction::Or
) {
369 Value
*Op0
= BinOp
->getOperand(0);
370 Value
*Op1
= BinOp
->getOperand(1);
371 return isValidBranch(BB
, BI
, Op0
, IsLoopBranch
, Context
) &&
372 isValidBranch(BB
, BI
, Op1
, IsLoopBranch
, Context
);
376 // Non constant conditions of branches need to be ICmpInst.
377 if (!isa
<ICmpInst
>(Condition
)) {
378 if (!IsLoopBranch
&& AllowNonAffineSubRegions
&&
379 addOverApproximatedRegion(RI
->getRegionFor(&BB
), Context
))
381 return invalid
<ReportInvalidCond
>(Context
, /*Assert=*/true, BI
, &BB
);
384 ICmpInst
*ICmp
= cast
<ICmpInst
>(Condition
);
386 // Are both operands of the ICmp affine?
387 if (isa
<UndefValue
>(ICmp
->getOperand(0)) ||
388 isa
<UndefValue
>(ICmp
->getOperand(1)))
389 return invalid
<ReportUndefOperand
>(Context
, /*Assert=*/true, &BB
, ICmp
);
391 Loop
*L
= LI
->getLoopFor(&BB
);
392 const SCEV
*LHS
= SE
->getSCEVAtScope(ICmp
->getOperand(0), L
);
393 const SCEV
*RHS
= SE
->getSCEVAtScope(ICmp
->getOperand(1), L
);
395 if (isAffine(LHS
, L
, Context
) && isAffine(RHS
, L
, Context
))
398 if (!IsLoopBranch
&& AllowNonAffineSubRegions
&&
399 addOverApproximatedRegion(RI
->getRegionFor(&BB
), Context
))
405 return invalid
<ReportNonAffBranch
>(Context
, /*Assert=*/true, &BB
, LHS
, RHS
,
409 bool ScopDetection::isValidCFG(BasicBlock
&BB
, bool IsLoopBranch
,
410 bool AllowUnreachable
,
411 DetectionContext
&Context
) const {
412 Region
&CurRegion
= Context
.CurRegion
;
414 TerminatorInst
*TI
= BB
.getTerminator();
416 if (AllowUnreachable
&& isa
<UnreachableInst
>(TI
))
419 // Return instructions are only valid if the region is the top level region.
420 if (isa
<ReturnInst
>(TI
) && !CurRegion
.getExit() && TI
->getNumOperands() == 0)
423 Value
*Condition
= getConditionFromTerminator(TI
);
426 return invalid
<ReportInvalidTerminator
>(Context
, /*Assert=*/true, &BB
);
428 // UndefValue is not allowed as condition.
429 if (isa
<UndefValue
>(Condition
))
430 return invalid
<ReportUndefCond
>(Context
, /*Assert=*/true, TI
, &BB
);
432 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(TI
))
433 return isValidBranch(BB
, BI
, Condition
, IsLoopBranch
, Context
);
435 SwitchInst
*SI
= dyn_cast
<SwitchInst
>(TI
);
436 assert(SI
&& "Terminator was neither branch nor switch");
438 return isValidSwitch(BB
, SI
, Condition
, IsLoopBranch
, Context
);
441 bool ScopDetection::isValidCallInst(CallInst
&CI
,
442 DetectionContext
&Context
) const {
443 if (CI
.doesNotReturn())
446 if (CI
.doesNotAccessMemory())
449 if (auto *II
= dyn_cast
<IntrinsicInst
>(&CI
))
450 if (isValidIntrinsicInst(*II
, Context
))
453 Function
*CalledFunction
= CI
.getCalledFunction();
455 // Indirect calls are not supported.
456 if (CalledFunction
== nullptr)
459 if (AllowModrefCall
) {
460 switch (AA
->getModRefBehavior(CalledFunction
)) {
461 case llvm::FMRB_UnknownModRefBehavior
:
463 case llvm::FMRB_DoesNotAccessMemory
:
464 case llvm::FMRB_OnlyReadsMemory
:
465 // Implicitly disable delinearization since we have an unknown
466 // accesses with an unknown access function.
467 Context
.HasUnknownAccess
= true;
468 Context
.AST
.add(&CI
);
470 case llvm::FMRB_OnlyReadsArgumentPointees
:
471 case llvm::FMRB_OnlyAccessesArgumentPointees
:
472 for (const auto &Arg
: CI
.arg_operands()) {
473 if (!Arg
->getType()->isPointerTy())
476 // Bail if a pointer argument has a base address not known to
477 // ScalarEvolution. Note that a zero pointer is acceptable.
478 auto *ArgSCEV
= SE
->getSCEVAtScope(Arg
, LI
->getLoopFor(CI
.getParent()));
479 if (ArgSCEV
->isZero())
482 auto *BP
= dyn_cast
<SCEVUnknown
>(SE
->getPointerBase(ArgSCEV
));
486 // Implicitly disable delinearization since we have an unknown
487 // accesses with an unknown access function.
488 Context
.HasUnknownAccess
= true;
491 Context
.AST
.add(&CI
);
493 case FMRB_DoesNotReadMemory
:
494 case FMRB_OnlyAccessesInaccessibleMem
:
495 case FMRB_OnlyAccessesInaccessibleOrArgMem
:
503 bool ScopDetection::isValidIntrinsicInst(IntrinsicInst
&II
,
504 DetectionContext
&Context
) const {
505 if (isIgnoredIntrinsic(&II
))
508 // The closest loop surrounding the call instruction.
509 Loop
*L
= LI
->getLoopFor(II
.getParent());
511 // The access function and base pointer for memory intrinsics.
513 const SCEVUnknown
*BP
;
515 switch (II
.getIntrinsicID()) {
516 // Memory intrinsics that can be represented are supported.
517 case llvm::Intrinsic::memmove
:
518 case llvm::Intrinsic::memcpy
:
519 AF
= SE
->getSCEVAtScope(cast
<MemTransferInst
>(II
).getSource(), L
);
521 BP
= dyn_cast
<SCEVUnknown
>(SE
->getPointerBase(AF
));
522 // Bail if the source pointer is not valid.
523 if (!isValidAccess(&II
, AF
, BP
, Context
))
527 case llvm::Intrinsic::memset
:
528 AF
= SE
->getSCEVAtScope(cast
<MemIntrinsic
>(II
).getDest(), L
);
530 BP
= dyn_cast
<SCEVUnknown
>(SE
->getPointerBase(AF
));
531 // Bail if the destination pointer is not valid.
532 if (!isValidAccess(&II
, AF
, BP
, Context
))
536 // Bail if the length is not affine.
537 if (!isAffine(SE
->getSCEVAtScope(cast
<MemIntrinsic
>(II
).getLength(), L
), L
,
549 bool ScopDetection::isInvariant(const Value
&Val
, const Region
&Reg
) const {
550 // A reference to function argument or constant value is invariant.
551 if (isa
<Argument
>(Val
) || isa
<Constant
>(Val
))
554 const Instruction
*I
= dyn_cast
<Instruction
>(&Val
);
558 if (!Reg
.contains(I
))
561 if (I
->mayHaveSideEffects())
564 if (isa
<SelectInst
>(I
))
567 // When Val is a Phi node, it is likely not invariant. We do not check whether
568 // Phi nodes are actually invariant, we assume that Phi nodes are usually not
570 if (isa
<PHINode
>(*I
))
573 for (const Use
&Operand
: I
->operands())
574 if (!isInvariant(*Operand
, Reg
))
580 /// Remove smax of smax(0, size) expressions from a SCEV expression and
581 /// register the '...' components.
583 /// Array access expressions as they are generated by gfortran contain smax(0,
584 /// size) expressions that confuse the 'normal' delinearization algorithm.
585 /// However, if we extract such expressions before the normal delinearization
586 /// takes place they can actually help to identify array size expressions in
587 /// fortran accesses. For the subsequently following delinearization the smax(0,
588 /// size) component can be replaced by just 'size'. This is correct as we will
589 /// always add and verify the assumption that for all subscript expressions
590 /// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify
591 /// that 0 <= size, which means smax(0, size) == size.
592 class SCEVRemoveMax
: public SCEVRewriteVisitor
<SCEVRemoveMax
> {
594 static const SCEV
*rewrite(const SCEV
*Scev
, ScalarEvolution
&SE
,
595 std::vector
<const SCEV
*> *Terms
= nullptr) {
596 SCEVRemoveMax
Rewriter(SE
, Terms
);
597 return Rewriter
.visit(Scev
);
600 SCEVRemoveMax(ScalarEvolution
&SE
, std::vector
<const SCEV
*> *Terms
)
601 : SCEVRewriteVisitor(SE
), Terms(Terms
) {}
603 const SCEV
*visitSMaxExpr(const SCEVSMaxExpr
*Expr
) {
604 if ((Expr
->getNumOperands() == 2) && Expr
->getOperand(0)->isZero()) {
605 auto Res
= visit(Expr
->getOperand(1));
607 (*Terms
).push_back(Res
);
615 std::vector
<const SCEV
*> *Terms
;
618 SmallVector
<const SCEV
*, 4>
619 ScopDetection::getDelinearizationTerms(DetectionContext
&Context
,
620 const SCEVUnknown
*BasePointer
) const {
621 SmallVector
<const SCEV
*, 4> Terms
;
622 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
623 std::vector
<const SCEV
*> MaxTerms
;
624 SCEVRemoveMax::rewrite(Pair
.second
, *SE
, &MaxTerms
);
625 if (MaxTerms
.size() > 0) {
626 Terms
.insert(Terms
.begin(), MaxTerms
.begin(), MaxTerms
.end());
629 // In case the outermost expression is a plain add, we check if any of its
630 // terms has the form 4 * %inst * %param * %param ..., aka a term that
631 // contains a product between a parameter and an instruction that is
632 // inside the scop. Such instructions, if allowed at all, are instructions
633 // SCEV can not represent, but Polly is still looking through. As a
634 // result, these instructions can depend on induction variables and are
635 // most likely no array sizes. However, terms that are multiplied with
636 // them are likely candidates for array sizes.
637 if (auto *AF
= dyn_cast
<SCEVAddExpr
>(Pair
.second
)) {
638 for (auto Op
: AF
->operands()) {
639 if (auto *AF2
= dyn_cast
<SCEVAddRecExpr
>(Op
))
640 SE
->collectParametricTerms(AF2
, Terms
);
641 if (auto *AF2
= dyn_cast
<SCEVMulExpr
>(Op
)) {
642 SmallVector
<const SCEV
*, 0> Operands
;
644 for (auto *MulOp
: AF2
->operands()) {
645 if (auto *Const
= dyn_cast
<SCEVConstant
>(MulOp
))
646 Operands
.push_back(Const
);
647 if (auto *Unknown
= dyn_cast
<SCEVUnknown
>(MulOp
)) {
648 if (auto *Inst
= dyn_cast
<Instruction
>(Unknown
->getValue())) {
649 if (!Context
.CurRegion
.contains(Inst
))
650 Operands
.push_back(MulOp
);
653 Operands
.push_back(MulOp
);
658 Terms
.push_back(SE
->getMulExpr(Operands
));
663 SE
->collectParametricTerms(Pair
.second
, Terms
);
668 bool ScopDetection::hasValidArraySizes(DetectionContext
&Context
,
669 SmallVectorImpl
<const SCEV
*> &Sizes
,
670 const SCEVUnknown
*BasePointer
,
672 Value
*BaseValue
= BasePointer
->getValue();
673 Region
&CurRegion
= Context
.CurRegion
;
674 for (const SCEV
*DelinearizedSize
: Sizes
) {
675 if (!isAffine(DelinearizedSize
, Scope
, Context
)) {
679 if (auto *Unknown
= dyn_cast
<SCEVUnknown
>(DelinearizedSize
)) {
680 auto *V
= dyn_cast
<Value
>(Unknown
->getValue());
681 if (auto *Load
= dyn_cast
<LoadInst
>(V
)) {
682 if (Context
.CurRegion
.contains(Load
) &&
683 isHoistableLoad(Load
, CurRegion
, *LI
, *SE
))
684 Context
.RequiredILS
.insert(Load
);
688 if (hasScalarDepsInsideRegion(DelinearizedSize
, &CurRegion
, Scope
, false))
689 return invalid
<ReportNonAffineAccess
>(
690 Context
, /*Assert=*/true, DelinearizedSize
,
691 Context
.Accesses
[BasePointer
].front().first
, BaseValue
);
694 // No array shape derived.
699 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
700 const Instruction
*Insn
= Pair
.first
;
701 const SCEV
*AF
= Pair
.second
;
703 if (!isAffine(AF
, Scope
, Context
)) {
704 invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Insn
,
715 // We first store the resulting memory accesses in TempMemoryAccesses. Only
716 // if the access functions for all memory accesses have been successfully
717 // delinearized we continue. Otherwise, we either report a failure or, if
718 // non-affine accesses are allowed, we drop the information. In case the
719 // information is dropped the memory accesses need to be overapproximated
720 // when translated to a polyhedral representation.
721 bool ScopDetection::computeAccessFunctions(
722 DetectionContext
&Context
, const SCEVUnknown
*BasePointer
,
723 std::shared_ptr
<ArrayShape
> Shape
) const {
724 Value
*BaseValue
= BasePointer
->getValue();
725 bool BasePtrHasNonAffine
= false;
726 MapInsnToMemAcc TempMemoryAccesses
;
727 for (const auto &Pair
: Context
.Accesses
[BasePointer
]) {
728 const Instruction
*Insn
= Pair
.first
;
729 auto *AF
= Pair
.second
;
730 AF
= SCEVRemoveMax::rewrite(AF
, *SE
);
731 bool IsNonAffine
= false;
732 TempMemoryAccesses
.insert(std::make_pair(Insn
, MemAcc(Insn
, Shape
)));
733 MemAcc
*Acc
= &TempMemoryAccesses
.find(Insn
)->second
;
734 auto *Scope
= LI
->getLoopFor(Insn
->getParent());
737 if (isAffine(Pair
.second
, Scope
, Context
))
738 Acc
->DelinearizedSubscripts
.push_back(Pair
.second
);
742 SE
->computeAccessFunctions(AF
, Acc
->DelinearizedSubscripts
,
743 Shape
->DelinearizedSizes
);
744 if (Acc
->DelinearizedSubscripts
.size() == 0)
746 for (const SCEV
*S
: Acc
->DelinearizedSubscripts
)
747 if (!isAffine(S
, Scope
, Context
))
751 // (Possibly) report non affine access
753 BasePtrHasNonAffine
= true;
755 invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, Pair
.second
,
757 if (!KeepGoing
&& !AllowNonAffine
)
762 if (!BasePtrHasNonAffine
)
763 Context
.InsnToMemAcc
.insert(TempMemoryAccesses
.begin(),
764 TempMemoryAccesses
.end());
769 bool ScopDetection::hasBaseAffineAccesses(DetectionContext
&Context
,
770 const SCEVUnknown
*BasePointer
,
772 auto Shape
= std::shared_ptr
<ArrayShape
>(new ArrayShape(BasePointer
));
774 auto Terms
= getDelinearizationTerms(Context
, BasePointer
);
776 SE
->findArrayDimensions(Terms
, Shape
->DelinearizedSizes
,
777 Context
.ElementSize
[BasePointer
]);
779 if (!hasValidArraySizes(Context
, Shape
->DelinearizedSizes
, BasePointer
,
783 return computeAccessFunctions(Context
, BasePointer
, Shape
);
786 bool ScopDetection::hasAffineMemoryAccesses(DetectionContext
&Context
) const {
787 // TODO: If we have an unknown access and other non-affine accesses we do
788 // not try to delinearize them for now.
789 if (Context
.HasUnknownAccess
&& !Context
.NonAffineAccesses
.empty())
790 return AllowNonAffine
;
792 for (auto &Pair
: Context
.NonAffineAccesses
) {
793 auto *BasePointer
= Pair
.first
;
794 auto *Scope
= Pair
.second
;
795 if (!hasBaseAffineAccesses(Context
, BasePointer
, Scope
)) {
805 bool ScopDetection::isValidAccess(Instruction
*Inst
, const SCEV
*AF
,
806 const SCEVUnknown
*BP
,
807 DetectionContext
&Context
) const {
810 return invalid
<ReportNoBasePtr
>(Context
, /*Assert=*/true, Inst
);
812 auto *BV
= BP
->getValue();
813 if (isa
<UndefValue
>(BV
))
814 return invalid
<ReportUndefBasePtr
>(Context
, /*Assert=*/true, Inst
);
816 // FIXME: Think about allowing IntToPtrInst
817 if (IntToPtrInst
*Inst
= dyn_cast
<IntToPtrInst
>(BV
))
818 return invalid
<ReportIntToPtr
>(Context
, /*Assert=*/true, Inst
);
820 // Check that the base address of the access is invariant in the current
822 if (!isInvariant(*BV
, Context
.CurRegion
))
823 return invalid
<ReportVariantBasePtr
>(Context
, /*Assert=*/true, BV
, Inst
);
825 AF
= SE
->getMinusSCEV(AF
, BP
);
828 if (!isa
<MemIntrinsic
>(Inst
)) {
829 Size
= SE
->getElementSize(Inst
);
832 SE
->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE
->getContext()));
833 Size
= SE
->getConstant(SizeTy
, 8);
836 if (Context
.ElementSize
[BP
]) {
837 if (!AllowDifferentTypes
&& Context
.ElementSize
[BP
] != Size
)
838 return invalid
<ReportDifferentArrayElementSize
>(Context
, /*Assert=*/true,
841 Context
.ElementSize
[BP
] = SE
->getSMinExpr(Size
, Context
.ElementSize
[BP
]);
843 Context
.ElementSize
[BP
] = Size
;
846 bool IsVariantInNonAffineLoop
= false;
847 SetVector
<const Loop
*> Loops
;
848 findLoops(AF
, Loops
);
849 for (const Loop
*L
: Loops
)
850 if (Context
.BoxedLoopsSet
.count(L
))
851 IsVariantInNonAffineLoop
= true;
853 auto *Scope
= LI
->getLoopFor(Inst
->getParent());
854 bool IsAffine
= !IsVariantInNonAffineLoop
&& isAffine(AF
, Scope
, Context
);
855 // Do not try to delinearize memory intrinsics and force them to be affine.
856 if (isa
<MemIntrinsic
>(Inst
) && !IsAffine
) {
857 return invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Inst
,
859 } else if (PollyDelinearize
&& !IsVariantInNonAffineLoop
) {
860 Context
.Accesses
[BP
].push_back({Inst
, AF
});
863 Context
.NonAffineAccesses
.insert(
864 std::make_pair(BP
, LI
->getLoopFor(Inst
->getParent())));
865 } else if (!AllowNonAffine
&& !IsAffine
) {
866 return invalid
<ReportNonAffineAccess
>(Context
, /*Assert=*/true, AF
, Inst
,
873 // Check if the base pointer of the memory access does alias with
874 // any other pointer. This cannot be handled at the moment.
876 Inst
->getAAMetadata(AATags
);
877 AliasSet
&AS
= Context
.AST
.getAliasSetForPointer(
878 BP
->getValue(), MemoryLocation::UnknownSize
, AATags
);
880 if (!AS
.isMustAlias()) {
881 if (PollyUseRuntimeAliasChecks
) {
882 bool CanBuildRunTimeCheck
= true;
883 // The run-time alias check places code that involves the base pointer at
884 // the beginning of the SCoP. This breaks if the base pointer is defined
885 // inside the scop. Hence, we can only create a run-time check if we are
886 // sure the base pointer is not an instruction defined inside the scop.
887 // However, we can ignore loads that will be hoisted.
888 for (const auto &Ptr
: AS
) {
889 Instruction
*Inst
= dyn_cast
<Instruction
>(Ptr
.getValue());
890 if (Inst
&& Context
.CurRegion
.contains(Inst
)) {
891 auto *Load
= dyn_cast
<LoadInst
>(Inst
);
892 if (Load
&& isHoistableLoad(Load
, Context
.CurRegion
, *LI
, *SE
)) {
893 Context
.RequiredILS
.insert(Load
);
897 CanBuildRunTimeCheck
= false;
902 if (CanBuildRunTimeCheck
)
905 return invalid
<ReportAlias
>(Context
, /*Assert=*/true, Inst
, AS
);
911 bool ScopDetection::isValidMemoryAccess(MemAccInst Inst
,
912 DetectionContext
&Context
) const {
913 Value
*Ptr
= Inst
.getPointerOperand();
914 Loop
*L
= LI
->getLoopFor(Inst
->getParent());
915 const SCEV
*AccessFunction
= SE
->getSCEVAtScope(Ptr
, L
);
916 const SCEVUnknown
*BasePointer
;
918 BasePointer
= dyn_cast
<SCEVUnknown
>(SE
->getPointerBase(AccessFunction
));
920 return isValidAccess(Inst
, AccessFunction
, BasePointer
, Context
);
923 bool ScopDetection::isValidInstruction(Instruction
&Inst
,
924 DetectionContext
&Context
) const {
925 for (auto &Op
: Inst
.operands()) {
926 auto *OpInst
= dyn_cast
<Instruction
>(&Op
);
931 if (isErrorBlock(*OpInst
->getParent(), Context
.CurRegion
, *LI
, *DT
))
935 if (isa
<LandingPadInst
>(&Inst
) || isa
<ResumeInst
>(&Inst
))
938 // We only check the call instruction but not invoke instruction.
939 if (CallInst
*CI
= dyn_cast
<CallInst
>(&Inst
)) {
940 if (isValidCallInst(*CI
, Context
))
943 return invalid
<ReportFuncCall
>(Context
, /*Assert=*/true, &Inst
);
946 if (!Inst
.mayWriteToMemory() && !Inst
.mayReadFromMemory()) {
947 if (!isa
<AllocaInst
>(Inst
))
950 return invalid
<ReportAlloca
>(Context
, /*Assert=*/true, &Inst
);
953 // Check the access function.
954 if (auto MemInst
= MemAccInst::dyn_cast(Inst
)) {
955 Context
.hasStores
|= isa
<StoreInst
>(MemInst
);
956 Context
.hasLoads
|= isa
<LoadInst
>(MemInst
);
957 if (!MemInst
.isSimple())
958 return invalid
<ReportNonSimpleMemoryAccess
>(Context
, /*Assert=*/true,
961 return isValidMemoryAccess(MemInst
, Context
);
964 // We do not know this instruction, therefore we assume it is invalid.
965 return invalid
<ReportUnknownInst
>(Context
, /*Assert=*/true, &Inst
);
968 /// Check whether @p L has exiting blocks.
970 /// @param L The loop of interest
972 /// @return True if the loop has exiting blocks, false otherwise.
973 static bool hasExitingBlocks(Loop
*L
) {
974 SmallVector
<BasicBlock
*, 4> ExitingBlocks
;
975 L
->getExitingBlocks(ExitingBlocks
);
976 return !ExitingBlocks
.empty();
979 bool ScopDetection::canUseISLTripCount(Loop
*L
,
980 DetectionContext
&Context
) const {
981 // Ensure the loop has valid exiting blocks as well as latches, otherwise we
982 // need to overapproximate it as a boxed loop.
983 SmallVector
<BasicBlock
*, 4> LoopControlBlocks
;
984 L
->getExitingBlocks(LoopControlBlocks
);
985 L
->getLoopLatches(LoopControlBlocks
);
986 for (BasicBlock
*ControlBB
: LoopControlBlocks
) {
987 if (!isValidCFG(*ControlBB
, true, false, Context
))
991 // We can use ISL to compute the trip count of L.
995 bool ScopDetection::isValidLoop(Loop
*L
, DetectionContext
&Context
) const {
996 // Loops that contain part but not all of the blocks of a region cannot be
997 // handled by the schedule generation. Such loop constructs can happen
998 // because a region can contain BBs that have no path to the exit block
999 // (Infinite loops, UnreachableInst), but such blocks are never part of a
1003 // | Loop Header | <-----------.
1004 // --------------- |
1006 // _______________ ______________
1007 // | RegionEntry |-----> | RegionExit |----->
1008 // --------------- --------------
1011 // | EndlessLoop | <--.
1012 // --------------- |
1016 // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
1017 // neither entirely contained in the region RegionEntry->RegionExit
1018 // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
1020 // The block EndlessLoop is contained in the region because Region::contains
1021 // tests whether it is not dominated by RegionExit. This is probably to not
1022 // having to query the PostdominatorTree. Instead of an endless loop, a dead
1023 // end can also be formed by an UnreachableInst. This case is already caught
1024 // by isErrorBlock(). We hence only have to reject endless loops here.
1025 if (!hasExitingBlocks(L
))
1026 return invalid
<ReportLoopHasNoExit
>(Context
, /*Assert=*/true, L
);
1028 if (canUseISLTripCount(L
, Context
))
1031 if (AllowNonAffineSubLoops
&& AllowNonAffineSubRegions
) {
1032 Region
*R
= RI
->getRegionFor(L
->getHeader());
1033 while (R
!= &Context
.CurRegion
&& !R
->contains(L
))
1036 if (addOverApproximatedRegion(R
, Context
))
1040 const SCEV
*LoopCount
= SE
->getBackedgeTakenCount(L
);
1041 return invalid
<ReportLoopBound
>(Context
, /*Assert=*/true, L
, LoopCount
);
1044 /// Return the number of loops in @p L (incl. @p L) that have a trip
1045 /// count that is not known to be less than MIN_LOOP_TRIP_COUNT.
1046 static int countBeneficialSubLoops(Loop
*L
, ScalarEvolution
&SE
) {
1047 auto *TripCount
= SE
.getBackedgeTakenCount(L
);
1050 if (auto *TripCountC
= dyn_cast
<SCEVConstant
>(TripCount
))
1051 if (TripCountC
->getType()->getScalarSizeInBits() <= 64)
1052 if (TripCountC
->getValue()->getZExtValue() < MIN_LOOP_TRIP_COUNT
)
1055 for (auto &SubLoop
: *L
)
1056 count
+= countBeneficialSubLoops(SubLoop
, SE
);
1061 int ScopDetection::countBeneficialLoops(Region
*R
) const {
1064 auto L
= LI
->getLoopFor(R
->getEntry());
1065 L
= L
? R
->outermostLoopInRegion(L
) : nullptr;
1066 L
= L
? L
->getParentLoop() : nullptr;
1069 L
? L
->getSubLoopsVector() : std::vector
<Loop
*>(LI
->begin(), LI
->end());
1071 for (auto &SubLoop
: SubLoops
)
1072 if (R
->contains(SubLoop
))
1073 LoopNum
+= countBeneficialSubLoops(SubLoop
, *SE
);
1078 Region
*ScopDetection::expandRegion(Region
&R
) {
1079 // Initial no valid region was found (greater than R)
1080 std::unique_ptr
<Region
> LastValidRegion
;
1081 auto ExpandedRegion
= std::unique_ptr
<Region
>(R
.getExpandedRegion());
1083 DEBUG(dbgs() << "\tExpanding " << R
.getNameStr() << "\n");
1085 while (ExpandedRegion
) {
1086 const auto &It
= DetectionContextMap
.insert(std::make_pair(
1087 getBBPairForRegion(ExpandedRegion
.get()),
1088 DetectionContext(*ExpandedRegion
, *AA
, false /*verifying*/)));
1089 DetectionContext
&Context
= It
.first
->second
;
1090 DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion
->getNameStr() << "\n");
1091 // Only expand when we did not collect errors.
1093 if (!Context
.Log
.hasErrors()) {
1094 // If the exit is valid check all blocks
1095 // - if true, a valid region was found => store it + keep expanding
1096 // - if false, .tbd. => stop (should this really end the loop?)
1097 if (!allBlocksValid(Context
) || Context
.Log
.hasErrors()) {
1098 removeCachedResults(*ExpandedRegion
);
1099 DetectionContextMap
.erase(It
.first
);
1103 // Store this region, because it is the greatest valid (encountered so
1105 if (LastValidRegion
) {
1106 removeCachedResults(*LastValidRegion
);
1107 DetectionContextMap
.erase(getBBPairForRegion(LastValidRegion
.get()));
1109 LastValidRegion
= std::move(ExpandedRegion
);
1111 // Create and test the next greater region (if any)
1113 std::unique_ptr
<Region
>(LastValidRegion
->getExpandedRegion());
1116 // Create and test the next greater region (if any)
1117 removeCachedResults(*ExpandedRegion
);
1118 DetectionContextMap
.erase(It
.first
);
1120 std::unique_ptr
<Region
>(ExpandedRegion
->getExpandedRegion());
1125 if (LastValidRegion
)
1126 dbgs() << "\tto " << LastValidRegion
->getNameStr() << "\n";
1128 dbgs() << "\tExpanding " << R
.getNameStr() << " failed\n";
1131 return LastValidRegion
.release();
1133 static bool regionWithoutLoops(Region
&R
, LoopInfo
*LI
) {
1134 for (const BasicBlock
*BB
: R
.blocks())
1135 if (R
.contains(LI
->getLoopFor(BB
)))
1141 unsigned ScopDetection::removeCachedResultsRecursively(const Region
&R
) {
1143 for (auto &SubRegion
: R
) {
1144 if (ValidRegions
.count(SubRegion
.get())) {
1145 removeCachedResults(*SubRegion
.get());
1148 Count
+= removeCachedResultsRecursively(*SubRegion
);
1153 void ScopDetection::removeCachedResults(const Region
&R
) {
1154 ValidRegions
.remove(&R
);
1157 void ScopDetection::findScops(Region
&R
) {
1158 const auto &It
= DetectionContextMap
.insert(std::make_pair(
1159 getBBPairForRegion(&R
), DetectionContext(R
, *AA
, false /*verifying*/)));
1160 DetectionContext
&Context
= It
.first
->second
;
1162 bool RegionIsValid
= false;
1163 if (!PollyProcessUnprofitable
&& regionWithoutLoops(R
, LI
))
1164 invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &R
);
1166 RegionIsValid
= isValidRegion(Context
);
1168 bool HasErrors
= !RegionIsValid
|| Context
.Log
.size() > 0;
1171 removeCachedResults(R
);
1174 ValidRegions
.insert(&R
);
1178 for (auto &SubRegion
: R
)
1179 findScops(*SubRegion
);
1181 // Try to expand regions.
1183 // As the region tree normally only contains canonical regions, non canonical
1184 // regions that form a Scop are not found. Therefore, those non canonical
1185 // regions are checked by expanding the canonical ones.
1187 std::vector
<Region
*> ToExpand
;
1189 for (auto &SubRegion
: R
)
1190 ToExpand
.push_back(SubRegion
.get());
1192 for (Region
*CurrentRegion
: ToExpand
) {
1193 // Skip invalid regions. Regions may become invalid, if they are element of
1194 // an already expanded region.
1195 if (!ValidRegions
.count(CurrentRegion
))
1198 // Skip regions that had errors.
1199 bool HadErrors
= lookupRejectionLog(CurrentRegion
)->hasErrors();
1203 Region
*ExpandedR
= expandRegion(*CurrentRegion
);
1208 R
.addSubRegion(ExpandedR
, true);
1209 ValidRegions
.insert(ExpandedR
);
1210 removeCachedResults(*CurrentRegion
);
1212 // Erase all (direct and indirect) children of ExpandedR from the valid
1213 // regions and update the number of valid regions.
1214 ValidRegion
-= removeCachedResultsRecursively(*ExpandedR
);
1218 bool ScopDetection::allBlocksValid(DetectionContext
&Context
) const {
1219 Region
&CurRegion
= Context
.CurRegion
;
1221 for (const BasicBlock
*BB
: CurRegion
.blocks()) {
1222 Loop
*L
= LI
->getLoopFor(BB
);
1223 if (L
&& L
->getHeader() == BB
&& CurRegion
.contains(L
) &&
1224 (!isValidLoop(L
, Context
) && !KeepGoing
))
1228 for (BasicBlock
*BB
: CurRegion
.blocks()) {
1229 bool IsErrorBlock
= isErrorBlock(*BB
, CurRegion
, *LI
, *DT
);
1231 // Also check exception blocks (and possibly register them as non-affine
1232 // regions). Even though exception blocks are not modeled, we use them
1233 // to forward-propagate domain constraints during ScopInfo construction.
1234 if (!isValidCFG(*BB
, false, IsErrorBlock
, Context
) && !KeepGoing
)
1240 for (BasicBlock::iterator I
= BB
->begin(), E
= --BB
->end(); I
!= E
; ++I
)
1241 if (!isValidInstruction(*I
, Context
) && !KeepGoing
)
1245 if (!hasAffineMemoryAccesses(Context
))
1251 bool ScopDetection::hasSufficientCompute(DetectionContext
&Context
,
1252 int NumLoops
) const {
1258 for (auto *BB
: Context
.CurRegion
.blocks())
1259 if (Context
.CurRegion
.contains(LI
->getLoopFor(BB
)))
1260 InstCount
+= BB
->size();
1262 InstCount
= InstCount
/ NumLoops
;
1264 return InstCount
>= ProfitabilityMinPerLoopInstructions
;
1267 bool ScopDetection::hasPossiblyDistributableLoop(
1268 DetectionContext
&Context
) const {
1269 for (auto *BB
: Context
.CurRegion
.blocks()) {
1270 auto *L
= LI
->getLoopFor(BB
);
1271 if (!Context
.CurRegion
.contains(L
))
1273 if (Context
.BoxedLoopsSet
.count(L
))
1275 unsigned StmtsWithStoresInLoops
= 0;
1276 for (auto *LBB
: L
->blocks()) {
1277 bool MemStore
= false;
1278 for (auto &I
: *LBB
)
1279 MemStore
|= isa
<StoreInst
>(&I
);
1280 StmtsWithStoresInLoops
+= MemStore
;
1282 return (StmtsWithStoresInLoops
> 1);
1287 bool ScopDetection::isProfitableRegion(DetectionContext
&Context
) const {
1288 Region
&CurRegion
= Context
.CurRegion
;
1290 if (PollyProcessUnprofitable
)
1293 // We can probably not do a lot on scops that only write or only read
1295 if (!Context
.hasStores
|| !Context
.hasLoads
)
1296 return invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &CurRegion
);
1298 int NumLoops
= countBeneficialLoops(&CurRegion
);
1299 int NumAffineLoops
= NumLoops
- Context
.BoxedLoopsSet
.size();
1301 // Scops with at least two loops may allow either loop fusion or tiling and
1302 // are consequently interesting to look at.
1303 if (NumAffineLoops
>= 2)
1306 // A loop with multiple non-trivial blocks migt be amendable to distribution.
1307 if (NumAffineLoops
== 1 && hasPossiblyDistributableLoop(Context
))
1310 // Scops that contain a loop with a non-trivial amount of computation per
1311 // loop-iteration are interesting as we may be able to parallelize such
1312 // loops. Individual loops that have only a small amount of computation
1313 // per-iteration are performance-wise very fragile as any change to the
1314 // loop induction variables may affect performance. To not cause spurious
1315 // performance regressions, we do not consider such loops.
1316 if (NumAffineLoops
== 1 && hasSufficientCompute(Context
, NumLoops
))
1319 return invalid
<ReportUnprofitable
>(Context
, /*Assert=*/true, &CurRegion
);
1322 bool ScopDetection::isValidRegion(DetectionContext
&Context
) const {
1323 Region
&CurRegion
= Context
.CurRegion
;
1325 DEBUG(dbgs() << "Checking region: " << CurRegion
.getNameStr() << "\n\t");
1327 if (CurRegion
.isTopLevelRegion()) {
1328 DEBUG(dbgs() << "Top level region is invalid\n");
1332 if (!CurRegion
.getEntry()->getName().count(OnlyRegion
)) {
1334 dbgs() << "Region entry does not match -polly-region-only";
1340 // SCoP cannot contain the entry block of the function, because we need
1341 // to insert alloca instruction there when translate scalar to array.
1342 if (CurRegion
.getEntry() ==
1343 &(CurRegion
.getEntry()->getParent()->getEntryBlock()))
1344 return invalid
<ReportEntry
>(Context
, /*Assert=*/true, CurRegion
.getEntry());
1346 if (!allBlocksValid(Context
))
1350 if (!isReducibleRegion(CurRegion
, DbgLoc
))
1351 return invalid
<ReportIrreducibleRegion
>(Context
, /*Assert=*/true,
1352 &CurRegion
, DbgLoc
);
1354 DEBUG(dbgs() << "OK\n");
1358 void ScopDetection::markFunctionAsInvalid(Function
*F
) {
1359 F
->addFnAttr(PollySkipFnAttr
);
1362 bool ScopDetection::isValidFunction(llvm::Function
&F
) {
1363 return !F
.hasFnAttribute(PollySkipFnAttr
);
1366 void ScopDetection::printLocations(llvm::Function
&F
) {
1367 for (const Region
*R
: *this) {
1368 unsigned LineEntry
, LineExit
;
1369 std::string FileName
;
1371 getDebugLocation(R
, LineEntry
, LineExit
, FileName
);
1372 DiagnosticScopFound
Diagnostic(F
, FileName
, LineEntry
, LineExit
);
1373 F
.getContext().diagnose(Diagnostic
);
1377 void ScopDetection::emitMissedRemarks(const Function
&F
) {
1378 for (auto &DIt
: DetectionContextMap
) {
1379 auto &DC
= DIt
.getSecond();
1380 if (DC
.Log
.hasErrors())
1381 emitRejectionRemarks(DIt
.getFirst(), DC
.Log
);
1385 bool ScopDetection::isReducibleRegion(Region
&R
, DebugLoc
&DbgLoc
) const {
1386 /// Enum for coloring BBs in Region.
1388 /// WHITE - Unvisited BB in DFS walk.
1389 /// GREY - BBs which are currently on the DFS stack for processing.
1390 /// BLACK - Visited and completely processed BB.
1391 enum Color
{ WHITE
, GREY
, BLACK
};
1393 BasicBlock
*REntry
= R
.getEntry();
1394 BasicBlock
*RExit
= R
.getExit();
1395 // Map to match the color of a BasicBlock during the DFS walk.
1396 DenseMap
<const BasicBlock
*, Color
> BBColorMap
;
1397 // Stack keeping track of current BB and index of next child to be processed.
1398 std::stack
<std::pair
<BasicBlock
*, unsigned>> DFSStack
;
1400 unsigned AdjacentBlockIndex
= 0;
1401 BasicBlock
*CurrBB
, *SuccBB
;
1404 // Initialize the map for all BB with WHITE color.
1405 for (auto *BB
: R
.blocks())
1406 BBColorMap
[BB
] = WHITE
;
1408 // Process the entry block of the Region.
1409 BBColorMap
[CurrBB
] = GREY
;
1410 DFSStack
.push(std::make_pair(CurrBB
, 0));
1412 while (!DFSStack
.empty()) {
1413 // Get next BB on stack to be processed.
1414 CurrBB
= DFSStack
.top().first
;
1415 AdjacentBlockIndex
= DFSStack
.top().second
;
1418 // Loop to iterate over the successors of current BB.
1419 const TerminatorInst
*TInst
= CurrBB
->getTerminator();
1420 unsigned NSucc
= TInst
->getNumSuccessors();
1421 for (unsigned I
= AdjacentBlockIndex
; I
< NSucc
;
1422 ++I
, ++AdjacentBlockIndex
) {
1423 SuccBB
= TInst
->getSuccessor(I
);
1425 // Checks for region exit block and self-loops in BB.
1426 if (SuccBB
== RExit
|| SuccBB
== CurrBB
)
1429 // WHITE indicates an unvisited BB in DFS walk.
1430 if (BBColorMap
[SuccBB
] == WHITE
) {
1431 // Push the current BB and the index of the next child to be visited.
1432 DFSStack
.push(std::make_pair(CurrBB
, I
+ 1));
1433 // Push the next BB to be processed.
1434 DFSStack
.push(std::make_pair(SuccBB
, 0));
1435 // First time the BB is being processed.
1436 BBColorMap
[SuccBB
] = GREY
;
1438 } else if (BBColorMap
[SuccBB
] == GREY
) {
1439 // GREY indicates a loop in the control flow.
1440 // If the destination dominates the source, it is a natural loop
1441 // else, an irreducible control flow in the region is detected.
1442 if (!DT
->dominates(SuccBB
, CurrBB
)) {
1443 // Get debug info of instruction which causes irregular control flow.
1444 DbgLoc
= TInst
->getDebugLoc();
1450 // If all children of current BB have been processed,
1451 // then mark that BB as fully processed.
1452 if (AdjacentBlockIndex
== NSucc
)
1453 BBColorMap
[CurrBB
] = BLACK
;
1459 bool ScopDetection::runOnFunction(llvm::Function
&F
) {
1460 LI
= &getAnalysis
<LoopInfoWrapperPass
>().getLoopInfo();
1461 RI
= &getAnalysis
<RegionInfoPass
>().getRegionInfo();
1462 if (!PollyProcessUnprofitable
&& LI
->empty())
1465 AA
= &getAnalysis
<AAResultsWrapperPass
>().getAAResults();
1466 SE
= &getAnalysis
<ScalarEvolutionWrapperPass
>().getSE();
1467 DT
= &getAnalysis
<DominatorTreeWrapperPass
>().getDomTree();
1468 Region
*TopRegion
= RI
->getTopLevelRegion();
1472 if (OnlyFunction
!= "" && !F
.getName().count(OnlyFunction
))
1475 if (!isValidFunction(F
))
1478 findScops(*TopRegion
);
1480 // Prune non-profitable regions.
1481 for (auto &DIt
: DetectionContextMap
) {
1482 auto &DC
= DIt
.getSecond();
1483 if (DC
.Log
.hasErrors())
1485 if (!ValidRegions
.count(&DC
.CurRegion
))
1487 if (isProfitableRegion(DC
))
1490 ValidRegions
.remove(&DC
.CurRegion
);
1493 // Only makes sense when we tracked errors.
1494 if (PollyTrackFailures
)
1495 emitMissedRemarks(F
);
1500 assert(ValidRegions
.size() <= DetectionContextMap
.size() &&
1501 "Cached more results than valid regions");
1505 ScopDetection::DetectionContext
*
1506 ScopDetection::getDetectionContext(const Region
*R
) const {
1507 auto DCMIt
= DetectionContextMap
.find(getBBPairForRegion(R
));
1508 if (DCMIt
== DetectionContextMap
.end())
1510 return &DCMIt
->second
;
1513 const RejectLog
*ScopDetection::lookupRejectionLog(const Region
*R
) const {
1514 const DetectionContext
*DC
= getDetectionContext(R
);
1515 return DC
? &DC
->Log
: nullptr;
1518 void polly::ScopDetection::verifyRegion(const Region
&R
) const {
1519 assert(isMaxRegionInScop(R
) && "Expect R is a valid region.");
1521 DetectionContext
Context(const_cast<Region
&>(R
), *AA
, true /*verifying*/);
1522 isValidRegion(Context
);
1525 void polly::ScopDetection::verifyAnalysis() const {
1529 for (const Region
*R
: ValidRegions
)
1533 void ScopDetection::getAnalysisUsage(AnalysisUsage
&AU
) const {
1534 AU
.addRequired
<LoopInfoWrapperPass
>();
1535 AU
.addRequiredTransitive
<ScalarEvolutionWrapperPass
>();
1536 AU
.addRequired
<DominatorTreeWrapperPass
>();
1537 // We also need AA and RegionInfo when we are verifying analysis.
1538 AU
.addRequiredTransitive
<AAResultsWrapperPass
>();
1539 AU
.addRequiredTransitive
<RegionInfoPass
>();
1540 AU
.setPreservesAll();
1543 void ScopDetection::print(raw_ostream
&OS
, const Module
*) const {
1544 for (const Region
*R
: ValidRegions
)
1545 OS
<< "Valid Region for Scop: " << R
->getNameStr() << '\n';
1550 void ScopDetection::releaseMemory() {
1551 ValidRegions
.clear();
1552 DetectionContextMap
.clear();
1554 // Do not clear the invalid function set.
1557 char ScopDetection::ID
= 0;
1559 Pass
*polly::createScopDetectionPass() { return new ScopDetection(); }
1561 INITIALIZE_PASS_BEGIN(ScopDetection
, "polly-detect",
1562 "Polly - Detect static control parts (SCoPs)", false,
1564 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass
);
1565 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass
);
1566 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass
);
1567 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass
);
1568 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass
);
1569 INITIALIZE_PASS_END(ScopDetection
, "polly-detect",
1570 "Polly - Detect static control parts (SCoPs)", false, false)