1 //===--- ScopDetection.h - 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 // Only function calls and intrinsics that do not have side effects 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 #ifndef POLLY_SCOP_DETECTION_H
48 #define POLLY_SCOP_DETECTION_H
50 #include "polly/ScopDetectionDiagnostic.h"
51 #include "polly/Support/ScopHelper.h"
52 #include "llvm/ADT/SetVector.h"
53 #include "llvm/Analysis/AliasAnalysis.h"
54 #include "llvm/Analysis/AliasSetTracker.h"
55 #include "llvm/Analysis/RegionInfo.h"
56 #include "llvm/Pass.h"
66 class ScalarEvolution
;
77 typedef std::set
<const SCEV
*> ParamSetType
;
79 // Description of the shape of an array.
81 // Base pointer identifying all accesses to this array.
82 const SCEVUnknown
*BasePointer
;
84 // Sizes of each delinearized dimension.
85 SmallVector
<const SCEV
*, 4> DelinearizedSizes
;
87 ArrayShape(const SCEVUnknown
*B
) : BasePointer(B
), DelinearizedSizes() {}
91 const Instruction
*Insn
;
93 // A pointer to the shape description of the array.
94 std::shared_ptr
<ArrayShape
> Shape
;
96 // Subscripts computed by delinearization.
97 SmallVector
<const SCEV
*, 4> DelinearizedSubscripts
;
99 MemAcc(const Instruction
*I
, std::shared_ptr
<ArrayShape
> S
)
100 : Insn(I
), Shape(S
), DelinearizedSubscripts() {}
103 typedef std::map
<const Instruction
*, MemAcc
> MapInsnToMemAcc
;
104 typedef std::pair
<const Instruction
*, const SCEV
*> PairInstSCEV
;
105 typedef std::vector
<PairInstSCEV
> AFs
;
106 typedef std::map
<const SCEVUnknown
*, AFs
> BaseToAFs
;
107 typedef std::map
<const SCEVUnknown
*, const SCEV
*> BaseToElSize
;
109 extern bool PollyTrackFailures
;
110 extern bool PollyDelinearize
;
111 extern bool PollyUseRuntimeAliasChecks
;
112 extern bool PollyProcessUnprofitable
;
113 extern bool PollyInvariantLoadHoisting
;
114 extern bool PollyAllowUnsignedOperations
;
116 /// A function attribute which will cause Polly to skip the function
117 extern llvm::StringRef PollySkipFnAttr
;
119 //===----------------------------------------------------------------------===//
120 /// Pass to detect the maximal static control parts (Scops) of a
122 class ScopDetection
{
124 typedef SetVector
<const Region
*> RegionSet
;
126 // Remember the valid regions
127 RegionSet ValidRegions
;
129 /// Context variables for SCoP detection.
130 struct DetectionContext
{
131 Region
&CurRegion
; // The region to check.
132 AliasSetTracker AST
; // The AliasSetTracker to hold the alias information.
133 bool Verifying
; // If we are in the verification phase?
135 /// Container to remember rejection reasons for this region.
138 /// Map a base pointer to all access functions accessing it.
140 /// This map is indexed by the base pointer. Each element of the map
141 /// is a list of memory accesses that reference this base pointer.
144 /// The set of base pointers with non-affine accesses.
146 /// This set contains all base pointers and the locations where they are
147 /// used for memory accesses that can not be detected as affine accesses.
148 SetVector
<std::pair
<const SCEVUnknown
*, Loop
*>> NonAffineAccesses
;
149 BaseToElSize ElementSize
;
151 /// The region has at least one load instruction.
154 /// The region has at least one store instruction.
157 /// Flag to indicate the region has at least one unknown access.
158 bool HasUnknownAccess
;
160 /// The set of non-affine subregions in the region we analyze.
161 RegionSet NonAffineSubRegionSet
;
163 /// The set of loops contained in non-affine regions.
164 BoxedLoopsSetTy BoxedLoopsSet
;
166 /// Loads that need to be invariant during execution.
167 InvariantLoadsSetTy RequiredILS
;
169 /// Map to memory access description for the corresponding LLVM
171 MapInsnToMemAcc InsnToMemAcc
;
173 /// Initialize a DetectionContext from scratch.
174 DetectionContext(Region
&R
, AliasAnalysis
&AA
, bool Verify
)
175 : CurRegion(R
), AST(AA
), Verifying(Verify
), Log(&R
), hasLoads(false),
176 hasStores(false), HasUnknownAccess(false) {}
178 /// Initialize a DetectionContext with the data from @p DC.
179 DetectionContext(const DetectionContext
&&DC
)
180 : CurRegion(DC
.CurRegion
), AST(DC
.AST
.getAliasAnalysis()),
181 Verifying(DC
.Verifying
), Log(std::move(DC
.Log
)),
182 Accesses(std::move(DC
.Accesses
)),
183 NonAffineAccesses(std::move(DC
.NonAffineAccesses
)),
184 ElementSize(std::move(DC
.ElementSize
)), hasLoads(DC
.hasLoads
),
185 hasStores(DC
.hasStores
), HasUnknownAccess(DC
.HasUnknownAccess
),
186 NonAffineSubRegionSet(std::move(DC
.NonAffineSubRegionSet
)),
187 BoxedLoopsSet(std::move(DC
.BoxedLoopsSet
)),
188 RequiredILS(std::move(DC
.RequiredILS
)) {
193 /// Helper data structure to collect statistics about loop counts.
200 //===--------------------------------------------------------------------===//
204 const DominatorTree
&DT
;
211 /// Map to remember detection contexts for all regions.
212 using DetectionContextMapTy
= DenseMap
<BBPair
, DetectionContext
>;
213 mutable DetectionContextMapTy DetectionContextMap
;
215 /// Remove cached results for @p R.
216 void removeCachedResults(const Region
&R
);
218 /// Remove cached results for the children of @p R recursively.
219 void removeCachedResultsRecursively(const Region
&R
);
221 /// Check if @p S0 and @p S1 do contain multiple possibly aliasing pointers.
223 /// @param S0 A expression to check.
224 /// @param S1 Another expression to check or nullptr.
225 /// @param Scope The loop/scope the expressions are checked in.
227 /// @returns True, if multiple possibly aliasing pointers are used in @p S0
228 /// (and @p S1 if given).
229 bool involvesMultiplePtrs(const SCEV
*S0
, const SCEV
*S1
, Loop
*Scope
) const;
231 /// Add the region @p AR as over approximated sub-region in @p Context.
233 /// @param AR The non-affine subregion.
234 /// @param Context The current detection context.
236 /// @returns True if the subregion can be over approximated, false otherwise.
237 bool addOverApproximatedRegion(Region
*AR
, DetectionContext
&Context
) const;
239 /// Find for a given base pointer terms that hint towards dimension
240 /// sizes of a multi-dimensional array.
242 /// @param Context The current detection context.
243 /// @param BasePointer A base pointer indicating the virtual array we are
245 SmallVector
<const SCEV
*, 4>
246 getDelinearizationTerms(DetectionContext
&Context
,
247 const SCEVUnknown
*BasePointer
) const;
249 /// Check if the dimension size of a delinearized array is valid.
251 /// @param Context The current detection context.
252 /// @param Sizes The sizes of the different array dimensions.
253 /// @param BasePointer The base pointer we are interested in.
254 /// @param Scope The location where @p BasePointer is being used.
255 /// @returns True if one or more array sizes could be derived - meaning: we
256 /// see this array as multi-dimensional.
257 bool hasValidArraySizes(DetectionContext
&Context
,
258 SmallVectorImpl
<const SCEV
*> &Sizes
,
259 const SCEVUnknown
*BasePointer
, Loop
*Scope
) const;
261 /// Derive access functions for a given base pointer.
263 /// @param Context The current detection context.
264 /// @param Sizes The sizes of the different array dimensions.
265 /// @param BasePointer The base pointer of all the array for which to compute
266 /// access functions.
267 /// @param Shape The shape that describes the derived array sizes and
268 /// which should be filled with newly computed access
270 /// @returns True if a set of affine access functions could be derived.
271 bool computeAccessFunctions(DetectionContext
&Context
,
272 const SCEVUnknown
*BasePointer
,
273 std::shared_ptr
<ArrayShape
> Shape
) const;
275 /// Check if all accesses to a given BasePointer are affine.
277 /// @param Context The current detection context.
278 /// @param basepointer the base pointer we are interested in.
279 /// @param Scope The location where @p BasePointer is being used.
280 /// @param True if consistent (multi-dimensional) array accesses could be
281 /// derived for this array.
282 bool hasBaseAffineAccesses(DetectionContext
&Context
,
283 const SCEVUnknown
*BasePointer
, Loop
*Scope
) const;
285 // Delinearize all non affine memory accesses and return false when there
286 // exists a non affine memory access that cannot be delinearized. Return true
287 // when all array accesses are affine after delinearization.
288 bool hasAffineMemoryAccesses(DetectionContext
&Context
) const;
290 // Try to expand the region R. If R can be expanded return the expanded
291 // region, NULL otherwise.
292 Region
*expandRegion(Region
&R
);
294 /// Find the Scops in this region tree.
296 /// @param The region tree to scan for scops.
297 void findScops(Region
&R
);
299 /// Check if all basic block in the region are valid.
301 /// @param Context The context of scop detection.
303 /// @return True if all blocks in R are valid, false otherwise.
304 bool allBlocksValid(DetectionContext
&Context
) const;
306 /// Check if a region has sufficient compute instructions.
308 /// This function checks if a region has a non-trivial number of instructions
309 /// in each loop. This can be used as an indicator if a loop is worth
312 /// @param Context The context of scop detection.
313 /// @param NumLoops The number of loops in the region.
315 /// @return True if region is has sufficient compute instructions,
317 bool hasSufficientCompute(DetectionContext
&Context
,
318 int NumAffineLoops
) const;
320 /// Check if the unique affine loop might be amendable to distribution.
322 /// This function checks if the number of non-trivial blocks in the unique
323 /// affine loop in Context.CurRegion is at least two, thus if the loop might
324 /// be amendable to distribution.
326 /// @param Context The context of scop detection.
328 /// @return True only if the affine loop might be amendable to distributable.
329 bool hasPossiblyDistributableLoop(DetectionContext
&Context
) const;
331 /// Check if a region is profitable to optimize.
333 /// Regions that are unlikely to expose interesting optimization opportunities
334 /// are called 'unprofitable' and may be skipped during scop detection.
336 /// @param Context The context of scop detection.
338 /// @return True if region is profitable to optimize, false otherwise.
339 bool isProfitableRegion(DetectionContext
&Context
) const;
341 /// Check if a region is a Scop.
343 /// @param Context The context of scop detection.
345 /// @return True if R is a Scop, false otherwise.
346 bool isValidRegion(DetectionContext
&Context
) const;
348 /// Check if an intrinsic call can be part of a Scop.
350 /// @param II The intrinsic call instruction to check.
351 /// @param Context The current detection context.
353 /// @return True if the call instruction is valid, false otherwise.
354 bool isValidIntrinsicInst(IntrinsicInst
&II
, DetectionContext
&Context
) const;
356 /// Check if a call instruction can be part of a Scop.
358 /// @param CI The call instruction to check.
359 /// @param Context The current detection context.
361 /// @return True if the call instruction is valid, false otherwise.
362 bool isValidCallInst(CallInst
&CI
, DetectionContext
&Context
) const;
364 /// Check if the given loads could be invariant and can be hoisted.
366 /// If true is returned the loads are added to the required invariant loads
367 /// contained in the @p Context.
369 /// @param RequiredILS The loads to check.
370 /// @param Context The current detection context.
372 /// @return True if all loads can be assumed invariant.
373 bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy
&RequiredILS
,
374 DetectionContext
&Context
) const;
376 /// Check if a value is invariant in the region Reg.
378 /// @param Val Value to check for invariance.
379 /// @param Reg The region to consider for the invariance of Val.
380 /// @param Ctx The current detection context.
382 /// @return True if the value represented by Val is invariant in the region
383 /// identified by Reg.
384 bool isInvariant(Value
&Val
, const Region
&Reg
, DetectionContext
&Ctx
) const;
386 /// Check if the memory access caused by @p Inst is valid.
388 /// @param Inst The access instruction.
389 /// @param AF The access function.
390 /// @param BP The access base pointer.
391 /// @param Context The current detection context.
392 bool isValidAccess(Instruction
*Inst
, const SCEV
*AF
, const SCEVUnknown
*BP
,
393 DetectionContext
&Context
) const;
395 /// Check if a memory access can be part of a Scop.
397 /// @param Inst The instruction accessing the memory.
398 /// @param Context The context of scop detection.
400 /// @return True if the memory access is valid, false otherwise.
401 bool isValidMemoryAccess(MemAccInst Inst
, DetectionContext
&Context
) const;
403 /// Check if an instruction has any non trivial scalar dependencies as part of
406 /// @param Inst The instruction to check.
407 /// @param RefRegion The region in respect to which we check the access
410 /// @return True if the instruction has scalar dependences, false otherwise.
411 bool hasScalarDependency(Instruction
&Inst
, Region
&RefRegion
) const;
413 /// Check if an instruction can be part of a Scop.
415 /// @param Inst The instruction to check.
416 /// @param Context The context of scop detection.
418 /// @return True if the instruction is valid, false otherwise.
419 bool isValidInstruction(Instruction
&Inst
, DetectionContext
&Context
) const;
421 /// Check if the switch @p SI with condition @p Condition is valid.
423 /// @param BB The block to check.
424 /// @param SI The switch to check.
425 /// @param Condition The switch condition.
426 /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
427 /// @param Context The context of scop detection.
429 /// @return True if the branch @p BI is valid.
430 bool isValidSwitch(BasicBlock
&BB
, SwitchInst
*SI
, Value
*Condition
,
431 bool IsLoopBranch
, DetectionContext
&Context
) const;
433 /// Check if the branch @p BI with condition @p Condition is valid.
435 /// @param BB The block to check.
436 /// @param BI The branch to check.
437 /// @param Condition The branch condition.
438 /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
439 /// @param Context The context of scop detection.
441 /// @return True if the branch @p BI is valid.
442 bool isValidBranch(BasicBlock
&BB
, BranchInst
*BI
, Value
*Condition
,
443 bool IsLoopBranch
, DetectionContext
&Context
) const;
445 /// Check if the SCEV @p S is affine in the current @p Context.
447 /// This will also use a heuristic to decide if we want to require loads to be
448 /// invariant to make the expression affine or if we want to treat is as
451 /// @param S The expression to be checked.
452 /// @param Scope The loop nest in which @p S is used.
453 /// @param Context The context of scop detection.
454 bool isAffine(const SCEV
*S
, Loop
*Scope
, DetectionContext
&Context
) const;
456 /// Check if the control flow in a basic block is valid.
458 /// This function checks if a certain basic block is terminated by a
459 /// Terminator instruction we can handle or, if this is not the case,
460 /// registers this basic block as the start of a non-affine region.
462 /// This function optionally allows unreachable statements.
464 /// @param BB The BB to check the control flow.
465 /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch.
466 // @param AllowUnreachable Allow unreachable statements.
467 /// @param Context The context of scop detection.
469 /// @return True if the BB contains only valid control flow.
470 bool isValidCFG(BasicBlock
&BB
, bool IsLoopBranch
, bool AllowUnreachable
,
471 DetectionContext
&Context
) const;
473 /// Is a loop valid with respect to a given region.
475 /// @param L The loop to check.
476 /// @param Context The context of scop detection.
478 /// @return True if the loop is valid in the region.
479 bool isValidLoop(Loop
*L
, DetectionContext
&Context
) const;
481 /// Count the number of loops and the maximal loop depth in @p L.
483 /// @param L The loop to check.
484 /// @param SE The scalar evolution analysis.
485 /// @param MinProfitableTrips The minimum number of trip counts from which
486 /// a loop is assumed to be profitable and
487 /// consequently is counted.
488 /// returns A tuple of number of loops and their maximal depth.
489 static ScopDetection::LoopStats
490 countBeneficialSubLoops(Loop
*L
, ScalarEvolution
&SE
,
491 unsigned MinProfitableTrips
);
493 /// Check if the function @p F is marked as invalid.
495 /// @note An OpenMP subfunction will be marked as invalid.
496 bool isValidFunction(llvm::Function
&F
);
498 /// Can ISL compute the trip count of a loop.
500 /// @param L The loop to check.
501 /// @param Context The context of scop detection.
503 /// @return True if ISL can compute the trip count of the loop.
504 bool canUseISLTripCount(Loop
*L
, DetectionContext
&Context
) const;
506 /// Print the locations of all detected scops.
507 void printLocations(llvm::Function
&F
);
509 /// Check if a region is reducible or not.
511 /// @param Region The region to check.
512 /// @param DbgLoc Parameter to save the location of instruction that
513 /// causes irregular control flow if the region is irreducible.
515 /// @return True if R is reducible, false otherwise.
516 bool isReducibleRegion(Region
&R
, DebugLoc
&DbgLoc
) const;
518 /// Track diagnostics for invalid scops.
520 /// @param Context The context of scop detection.
521 /// @param Assert Throw an assert in verify mode or not.
522 /// @param Args Argument list that gets passed to the constructor of RR.
523 template <class RR
, typename
... Args
>
524 inline bool invalid(DetectionContext
&Context
, bool Assert
,
525 Args
&&... Arguments
) const;
528 ScopDetection(Function
&F
, const DominatorTree
&DT
, ScalarEvolution
&SE
,
529 LoopInfo
&LI
, RegionInfo
&RI
, AliasAnalysis
&AA
);
531 /// Get the RegionInfo stored in this pass.
533 /// This was added to give the DOT printer easy access to this information.
534 RegionInfo
*getRI() const { return &RI
; }
536 /// Get the LoopInfo stored in this pass.
537 LoopInfo
*getLI() const { return &LI
; }
539 /// Is the region is the maximum region of a Scop?
541 /// @param R The Region to test if it is maximum.
542 /// @param Verify Rerun the scop detection to verify SCoP was not invalidated
545 /// @return Return true if R is the maximum Region in a Scop, false otherwise.
546 bool isMaxRegionInScop(const Region
&R
, bool Verify
= true) const;
548 /// Return the detection context for @p R, nullptr if @p R was invalid.
549 DetectionContext
*getDetectionContext(const Region
*R
) const;
551 /// Return the set of rejection causes for @p R.
552 const RejectLog
*lookupRejectionLog(const Region
*R
) const;
554 /// Return true if @p SubR is a non-affine subregion in @p ScopR.
555 bool isNonAffineSubRegion(const Region
*SubR
, const Region
*ScopR
) const;
557 /// Get a message why a region is invalid
559 /// @param R The region for which we get the error message
561 /// @return The error or "" if no error appeared.
562 std::string
regionIsInvalidBecause(const Region
*R
) const;
564 /// @name Maximum Region In Scops Iterators
566 /// These iterators iterator over all maximum region in Scops of this
569 typedef RegionSet::iterator iterator
;
570 typedef RegionSet::const_iterator const_iterator
;
572 iterator
begin() { return ValidRegions
.begin(); }
573 iterator
end() { return ValidRegions
.end(); }
575 const_iterator
begin() const { return ValidRegions
.begin(); }
576 const_iterator
end() const { return ValidRegions
.end(); }
579 /// Emit rejection remarks for all rejected regions.
581 /// @param F The function to emit remarks for.
582 void emitMissedRemarks(const Function
&F
);
584 /// Mark the function as invalid so we will not extract any scop from
587 /// @param F The function to mark as invalid.
588 static void markFunctionAsInvalid(Function
*F
);
590 /// Verify if all valid Regions in this Function are still valid
591 /// after some transformations.
592 void verifyAnalysis() const;
594 /// Verify if R is still a valid part of Scop after some transformations.
596 /// @param R The Region to verify.
597 void verifyRegion(const Region
&R
) const;
599 /// Count the number of loops and the maximal loop depth in @p R.
601 /// @param R The region to check
602 /// @param SE The scalar evolution analysis.
603 /// @param MinProfitableTrips The minimum number of trip counts from which
604 /// a loop is assumed to be profitable and
605 /// consequently is counted.
606 /// returns A tuple of number of loops and their maximal depth.
607 static ScopDetection::LoopStats
608 countBeneficialLoops(Region
*R
, ScalarEvolution
&SE
, LoopInfo
&LI
,
609 unsigned MinProfitableTrips
);
612 struct ScopAnalysis
: public AnalysisInfoMixin
<ScopAnalysis
> {
613 static AnalysisKey Key
;
614 using Result
= ScopDetection
;
615 Result
run(Function
&F
, FunctionAnalysisManager
&FAM
);
618 struct ScopAnalysisPrinterPass
: public PassInfoMixin
<ScopAnalysisPrinterPass
> {
619 ScopAnalysisPrinterPass(raw_ostream
&O
) : Stream(O
) {}
620 PreservedAnalyses
run(Function
&F
, FunctionAnalysisManager
&FAM
);
624 struct ScopDetectionWrapperPass
: public FunctionPass
{
626 std::unique_ptr
<ScopDetection
> Result
;
628 ScopDetectionWrapperPass();
629 /// @name FunctionPass interface
631 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const;
632 virtual void releaseMemory();
633 virtual bool runOnFunction(Function
&F
);
634 virtual void print(raw_ostream
&OS
, const Module
*) const;
637 ScopDetection
&getSD() { return *Result
; }
638 const ScopDetection
&getSD() const { return *Result
; }
641 } // end namespace polly
645 void initializeScopDetectionWrapperPassPass(llvm::PassRegistry
&);