1 | //===- ScopDetection.h - Detect Scops ---------------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // Detect the maximal Scops of a function. |
10 | // |
11 | // A static control part (Scop) is a subgraph of the control flow graph (CFG) |
12 | // that only has statically known control flow and can therefore be described |
13 | // within the polyhedral model. |
14 | // |
15 | // Every Scop fulfills these restrictions: |
16 | // |
17 | // * It is a single entry single exit region |
18 | // |
19 | // * Only affine linear bounds in the loops |
20 | // |
21 | // Every natural loop in a Scop must have a number of loop iterations that can |
22 | // be described as an affine linear function in surrounding loop iterators or |
23 | // parameters. (A parameter is a scalar that does not change its value during |
24 | // execution of the Scop). |
25 | // |
26 | // * Only comparisons of affine linear expressions in conditions |
27 | // |
28 | // * All loops and conditions perfectly nested |
29 | // |
30 | // The control flow needs to be structured such that it could be written using |
31 | // just 'for' and 'if' statements, without the need for any 'goto', 'break' or |
32 | // 'continue'. |
33 | // |
34 | // * Side effect free functions call |
35 | // |
36 | // Only function calls and intrinsics that do not have side effects are allowed |
37 | // (readnone). |
38 | // |
39 | // The Scop detection finds the largest Scops by checking if the largest |
40 | // region is a Scop. If this is not the case, its canonical subregions are |
41 | // checked until a region is a Scop. It is now tried to extend this Scop by |
42 | // creating a larger non canonical region. |
43 | // |
44 | //===----------------------------------------------------------------------===// |
45 | |
46 | #ifndef POLLY_SCOPDETECTION_H |
47 | #define POLLY_SCOPDETECTION_H |
48 | |
49 | #include "polly/ScopDetectionDiagnostic.h" |
50 | #include "polly/Support/ScopHelper.h" |
51 | #include "llvm/Analysis/AliasAnalysis.h" |
52 | #include "llvm/Analysis/AliasSetTracker.h" |
53 | #include "llvm/Analysis/RegionInfo.h" |
54 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
55 | #include "llvm/Pass.h" |
56 | #include <set> |
57 | |
58 | namespace polly { |
59 | using llvm::AAResults; |
60 | using llvm::AliasSetTracker; |
61 | using llvm::AnalysisInfoMixin; |
62 | using llvm::AnalysisKey; |
63 | using llvm::AnalysisUsage; |
64 | using llvm::BatchAAResults; |
65 | using llvm::BranchInst; |
66 | using llvm::CallInst; |
67 | using llvm::DenseMap; |
68 | using llvm::DominatorTree; |
69 | using llvm::Function; |
70 | using llvm::FunctionAnalysisManager; |
71 | using llvm::FunctionPass; |
72 | using llvm::IntrinsicInst; |
73 | using llvm::LoopInfo; |
74 | using llvm::Module; |
75 | using llvm::OptimizationRemarkEmitter; |
76 | using llvm::PassInfoMixin; |
77 | using llvm::PreservedAnalyses; |
78 | using llvm::RegionInfo; |
79 | using llvm::ScalarEvolution; |
80 | using llvm::SCEVUnknown; |
81 | using llvm::SetVector; |
82 | using llvm::SmallSetVector; |
83 | using llvm::SmallVectorImpl; |
84 | using llvm::StringRef; |
85 | using llvm::SwitchInst; |
86 | |
87 | using ParamSetType = std::set<const SCEV *>; |
88 | |
89 | // Description of the shape of an array. |
90 | struct ArrayShape { |
91 | // Base pointer identifying all accesses to this array. |
92 | const SCEVUnknown *BasePointer; |
93 | |
94 | // Sizes of each delinearized dimension. |
95 | SmallVector<const SCEV *, 4> DelinearizedSizes; |
96 | |
97 | ArrayShape(const SCEVUnknown *B) : BasePointer(B) {} |
98 | }; |
99 | |
100 | struct MemAcc { |
101 | const Instruction *Insn; |
102 | |
103 | // A pointer to the shape description of the array. |
104 | std::shared_ptr<ArrayShape> Shape; |
105 | |
106 | // Subscripts computed by delinearization. |
107 | SmallVector<const SCEV *, 4> DelinearizedSubscripts; |
108 | |
109 | MemAcc(const Instruction *I, std::shared_ptr<ArrayShape> S) |
110 | : Insn(I), Shape(S) {} |
111 | }; |
112 | |
113 | using MapInsnToMemAcc = std::map<const Instruction *, MemAcc>; |
114 | using PairInstSCEV = std::pair<const Instruction *, const SCEV *>; |
115 | using AFs = std::vector<PairInstSCEV>; |
116 | using BaseToAFs = std::map<const SCEVUnknown *, AFs>; |
117 | using BaseToElSize = std::map<const SCEVUnknown *, const SCEV *>; |
118 | |
119 | extern bool PollyTrackFailures; |
120 | extern bool PollyDelinearize; |
121 | extern bool PollyUseRuntimeAliasChecks; |
122 | extern bool PollyProcessUnprofitable; |
123 | extern bool PollyInvariantLoadHoisting; |
124 | extern bool PollyAllowUnsignedOperations; |
125 | extern bool PollyAllowFullFunction; |
126 | |
127 | /// A function attribute which will cause Polly to skip the function |
128 | extern StringRef PollySkipFnAttr; |
129 | |
130 | //===----------------------------------------------------------------------===// |
131 | /// Pass to detect the maximal static control parts (Scops) of a |
132 | /// function. |
133 | class ScopDetection { |
134 | public: |
135 | using RegionSet = SetVector<const Region *>; |
136 | |
137 | // Remember the valid regions |
138 | RegionSet ValidRegions; |
139 | |
140 | /// Context variables for SCoP detection. |
141 | struct DetectionContext { |
142 | Region &CurRegion; // The region to check. |
143 | BatchAAResults BAA; // The batched alias analysis results. |
144 | AliasSetTracker AST; // The AliasSetTracker to hold the alias information. |
145 | bool Verifying; // If we are in the verification phase? |
146 | |
147 | /// If this flag is set, the SCoP must eventually be rejected, even with |
148 | /// KeepGoing. |
149 | bool IsInvalid = false; |
150 | |
151 | /// Container to remember rejection reasons for this region. |
152 | RejectLog Log; |
153 | |
154 | /// Map a base pointer to all access functions accessing it. |
155 | /// |
156 | /// This map is indexed by the base pointer. Each element of the map |
157 | /// is a list of memory accesses that reference this base pointer. |
158 | BaseToAFs Accesses; |
159 | |
160 | /// The set of base pointers with non-affine accesses. |
161 | /// |
162 | /// This set contains all base pointers and the locations where they are |
163 | /// used for memory accesses that can not be detected as affine accesses. |
164 | llvm::SetVector<std::pair<const SCEVUnknown *, Loop *>> NonAffineAccesses; |
165 | BaseToElSize ElementSize; |
166 | |
167 | /// The region has at least one load instruction. |
168 | bool hasLoads = false; |
169 | |
170 | /// The region has at least one store instruction. |
171 | bool hasStores = false; |
172 | |
173 | /// Flag to indicate the region has at least one unknown access. |
174 | bool HasUnknownAccess = false; |
175 | |
176 | /// The set of non-affine subregions in the region we analyze. |
177 | RegionSet NonAffineSubRegionSet; |
178 | |
179 | /// The set of loops contained in non-affine regions. |
180 | BoxedLoopsSetTy BoxedLoopsSet; |
181 | |
182 | /// Loads that need to be invariant during execution. |
183 | InvariantLoadsSetTy RequiredILS; |
184 | |
185 | /// Map to memory access description for the corresponding LLVM |
186 | /// instructions. |
187 | MapInsnToMemAcc InsnToMemAcc; |
188 | |
189 | /// Initialize a DetectionContext from scratch. |
190 | DetectionContext(Region &R, AAResults &AA, bool Verify) |
191 | : CurRegion(R), BAA(AA), AST(BAA), Verifying(Verify), Log(&R) {} |
192 | }; |
193 | |
194 | /// Helper data structure to collect statistics about loop counts. |
195 | struct LoopStats { |
196 | int NumLoops; |
197 | int MaxDepth; |
198 | }; |
199 | |
200 | int NextScopID = 0; |
201 | int getNextID() { return NextScopID++; } |
202 | |
203 | private: |
204 | //===--------------------------------------------------------------------===// |
205 | |
206 | /// Analyses used |
207 | //@{ |
208 | const DominatorTree &DT; |
209 | ScalarEvolution &SE; |
210 | LoopInfo &LI; |
211 | RegionInfo &RI; |
212 | AAResults &AA; |
213 | //@} |
214 | |
215 | /// Map to remember detection contexts for all regions. |
216 | using DetectionContextMapTy = |
217 | DenseMap<BBPair, std::unique_ptr<DetectionContext>>; |
218 | DetectionContextMapTy DetectionContextMap; |
219 | |
220 | /// Cache for the isErrorBlock function. |
221 | DenseMap<std::tuple<const BasicBlock *, const Region *>, bool> |
222 | ErrorBlockCache; |
223 | |
224 | /// Remove cached results for @p R. |
225 | void removeCachedResults(const Region &R); |
226 | |
227 | /// Remove cached results for the children of @p R recursively. |
228 | void removeCachedResultsRecursively(const Region &R); |
229 | |
230 | /// Check if @p S0 and @p S1 do contain multiple possibly aliasing pointers. |
231 | /// |
232 | /// @param S0 A expression to check. |
233 | /// @param S1 Another expression to check or nullptr. |
234 | /// @param Scope The loop/scope the expressions are checked in. |
235 | /// |
236 | /// @returns True, if multiple possibly aliasing pointers are used in @p S0 |
237 | /// (and @p S1 if given). |
238 | bool involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const; |
239 | |
240 | /// Add the region @p AR as over approximated sub-region in @p Context. |
241 | /// |
242 | /// @param AR The non-affine subregion. |
243 | /// @param Context The current detection context. |
244 | /// |
245 | /// @returns True if the subregion can be over approximated, false otherwise. |
246 | bool addOverApproximatedRegion(Region *AR, DetectionContext &Context) const; |
247 | |
248 | /// Find for a given base pointer terms that hint towards dimension |
249 | /// sizes of a multi-dimensional array. |
250 | /// |
251 | /// @param Context The current detection context. |
252 | /// @param BasePointer A base pointer indicating the virtual array we are |
253 | /// interested in. |
254 | SmallVector<const SCEV *, 4> |
255 | getDelinearizationTerms(DetectionContext &Context, |
256 | const SCEVUnknown *BasePointer) const; |
257 | |
258 | /// Check if the dimension size of a delinearized array is valid. |
259 | /// |
260 | /// @param Context The current detection context. |
261 | /// @param Sizes The sizes of the different array dimensions. |
262 | /// @param BasePointer The base pointer we are interested in. |
263 | /// @param Scope The location where @p BasePointer is being used. |
264 | /// @returns True if one or more array sizes could be derived - meaning: we |
265 | /// see this array as multi-dimensional. |
266 | bool hasValidArraySizes(DetectionContext &Context, |
267 | SmallVectorImpl<const SCEV *> &Sizes, |
268 | const SCEVUnknown *BasePointer, Loop *Scope) const; |
269 | |
270 | /// Derive access functions for a given base pointer. |
271 | /// |
272 | /// @param Context The current detection context. |
273 | /// @param Sizes The sizes of the different array dimensions. |
274 | /// @param BasePointer The base pointer of all the array for which to compute |
275 | /// access functions. |
276 | /// @param Shape The shape that describes the derived array sizes and |
277 | /// which should be filled with newly computed access |
278 | /// functions. |
279 | /// @returns True if a set of affine access functions could be derived. |
280 | bool computeAccessFunctions(DetectionContext &Context, |
281 | const SCEVUnknown *BasePointer, |
282 | std::shared_ptr<ArrayShape> Shape) const; |
283 | |
284 | /// Check if all accesses to a given BasePointer are affine. |
285 | /// |
286 | /// @param Context The current detection context. |
287 | /// @param BasePointer the base pointer we are interested in. |
288 | /// @param Scope The location where @p BasePointer is being used. |
289 | /// @param True if consistent (multi-dimensional) array accesses could be |
290 | /// derived for this array. |
291 | bool hasBaseAffineAccesses(DetectionContext &Context, |
292 | const SCEVUnknown *BasePointer, Loop *Scope) const; |
293 | |
294 | /// Delinearize all non affine memory accesses and return false when there |
295 | /// exists a non affine memory access that cannot be delinearized. Return true |
296 | /// when all array accesses are affine after delinearization. |
297 | bool hasAffineMemoryAccesses(DetectionContext &Context) const; |
298 | |
299 | /// Try to expand the region R. If R can be expanded return the expanded |
300 | /// region, NULL otherwise. |
301 | Region *expandRegion(Region &R); |
302 | |
303 | /// Find the Scops in this region tree. |
304 | /// |
305 | /// @param The region tree to scan for scops. |
306 | void findScops(Region &R); |
307 | |
308 | /// Check if all basic block in the region are valid. |
309 | /// |
310 | /// @param Context The context of scop detection. |
311 | bool allBlocksValid(DetectionContext &Context); |
312 | |
313 | /// Check if a region has sufficient compute instructions. |
314 | /// |
315 | /// This function checks if a region has a non-trivial number of instructions |
316 | /// in each loop. This can be used as an indicator whether a loop is worth |
317 | /// optimizing. |
318 | /// |
319 | /// @param Context The context of scop detection. |
320 | /// @param NumLoops The number of loops in the region. |
321 | /// |
322 | /// @return True if region is has sufficient compute instructions, |
323 | /// false otherwise. |
324 | bool hasSufficientCompute(DetectionContext &Context, |
325 | int NumAffineLoops) const; |
326 | |
327 | /// Check if the unique affine loop might be amendable to distribution. |
328 | /// |
329 | /// This function checks if the number of non-trivial blocks in the unique |
330 | /// affine loop in Context.CurRegion is at least two, thus if the loop might |
331 | /// be amendable to distribution. |
332 | /// |
333 | /// @param Context The context of scop detection. |
334 | /// |
335 | /// @return True only if the affine loop might be amendable to distributable. |
336 | bool hasPossiblyDistributableLoop(DetectionContext &Context) const; |
337 | |
338 | /// Check if a region is profitable to optimize. |
339 | /// |
340 | /// Regions that are unlikely to expose interesting optimization opportunities |
341 | /// are called 'unprofitable' and may be skipped during scop detection. |
342 | /// |
343 | /// @param Context The context of scop detection. |
344 | /// |
345 | /// @return True if region is profitable to optimize, false otherwise. |
346 | bool isProfitableRegion(DetectionContext &Context) const; |
347 | |
348 | /// Check if a region is a Scop. |
349 | /// |
350 | /// @param Context The context of scop detection. |
351 | /// |
352 | /// @return If we short-circuited early to not waste time on known-invalid |
353 | /// SCoPs. Use Context.IsInvalid to determine whether the region is a |
354 | /// valid SCoP. |
355 | bool isValidRegion(DetectionContext &Context); |
356 | |
357 | /// Check if an intrinsic call can be part of a Scop. |
358 | /// |
359 | /// @param II The intrinsic call instruction to check. |
360 | /// @param Context The current detection context. |
361 | bool isValidIntrinsicInst(IntrinsicInst &II, DetectionContext &Context) const; |
362 | |
363 | /// Check if a call instruction can be part of a Scop. |
364 | /// |
365 | /// @param CI The call instruction to check. |
366 | /// @param Context The current detection context. |
367 | bool isValidCallInst(CallInst &CI, DetectionContext &Context) const; |
368 | |
369 | /// Check if the given loads could be invariant and can be hoisted. |
370 | /// |
371 | /// If true is returned the loads are added to the required invariant loads |
372 | /// contained in the @p Context. |
373 | /// |
374 | /// @param RequiredILS The loads to check. |
375 | /// @param Context The current detection context. |
376 | /// |
377 | /// @return True if all loads can be assumed invariant. |
378 | bool onlyValidRequiredInvariantLoads(InvariantLoadsSetTy &RequiredILS, |
379 | DetectionContext &Context) const; |
380 | |
381 | /// Check if a value is invariant in the region Reg. |
382 | /// |
383 | /// @param Val Value to check for invariance. |
384 | /// @param Reg The region to consider for the invariance of Val. |
385 | /// @param Ctx The current detection context. |
386 | /// |
387 | /// @return True if the value represented by Val is invariant in the region |
388 | /// identified by Reg. |
389 | bool isInvariant(Value &Val, const Region &Reg, DetectionContext &Ctx) const; |
390 | |
391 | /// Check if the memory access caused by @p Inst is valid. |
392 | /// |
393 | /// @param Inst The access instruction. |
394 | /// @param AF The access function. |
395 | /// @param BP The access base pointer. |
396 | /// @param Context The current detection context. |
397 | bool isValidAccess(Instruction *Inst, const SCEV *AF, const SCEVUnknown *BP, |
398 | DetectionContext &Context) const; |
399 | |
400 | /// Check if a memory access can be part of a Scop. |
401 | /// |
402 | /// @param Inst The instruction accessing the memory. |
403 | /// @param Context The context of scop detection. |
404 | bool isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const; |
405 | |
406 | /// Check if an instruction can be part of a Scop. |
407 | /// |
408 | /// @param Inst The instruction to check. |
409 | /// @param Context The context of scop detection. |
410 | bool isValidInstruction(Instruction &Inst, DetectionContext &Context); |
411 | |
412 | /// Check if the switch @p SI with condition @p Condition is valid. |
413 | /// |
414 | /// @param BB The block to check. |
415 | /// @param SI The switch to check. |
416 | /// @param Condition The switch condition. |
417 | /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. |
418 | /// @param Context The context of scop detection. |
419 | bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, |
420 | bool IsLoopBranch, DetectionContext &Context) const; |
421 | |
422 | /// Check if the branch @p BI with condition @p Condition is valid. |
423 | /// |
424 | /// @param BB The block to check. |
425 | /// @param BI The branch to check. |
426 | /// @param Condition The branch condition. |
427 | /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. |
428 | /// @param Context The context of scop detection. |
429 | bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition, |
430 | bool IsLoopBranch, DetectionContext &Context); |
431 | |
432 | /// Check if the SCEV @p S is affine in the current @p Context. |
433 | /// |
434 | /// This will also use a heuristic to decide if we want to require loads to be |
435 | /// invariant to make the expression affine or if we want to treat is as |
436 | /// non-affine. |
437 | /// |
438 | /// @param S The expression to be checked. |
439 | /// @param Scope The loop nest in which @p S is used. |
440 | /// @param Context The context of scop detection. |
441 | bool isAffine(const SCEV *S, Loop *Scope, DetectionContext &Context) const; |
442 | |
443 | /// Check if the control flow in a basic block is valid. |
444 | /// |
445 | /// This function checks if a certain basic block is terminated by a |
446 | /// Terminator instruction we can handle or, if this is not the case, |
447 | /// registers this basic block as the start of a non-affine region. |
448 | /// |
449 | /// This function optionally allows unreachable statements. |
450 | /// |
451 | /// @param BB The BB to check the control flow. |
452 | /// @param IsLoopBranch Flag to indicate the branch is a loop exit/latch. |
453 | /// @param AllowUnreachable Allow unreachable statements. |
454 | /// @param Context The context of scop detection. |
455 | bool isValidCFG(BasicBlock &BB, bool IsLoopBranch, bool AllowUnreachable, |
456 | DetectionContext &Context); |
457 | |
458 | /// Is a loop valid with respect to a given region. |
459 | /// |
460 | /// @param L The loop to check. |
461 | /// @param Context The context of scop detection. |
462 | bool isValidLoop(Loop *L, DetectionContext &Context); |
463 | |
464 | /// Count the number of loops and the maximal loop depth in @p L. |
465 | /// |
466 | /// @param L The loop to check. |
467 | /// @param SE The scalar evolution analysis. |
468 | /// @param MinProfitableTrips The minimum number of trip counts from which |
469 | /// a loop is assumed to be profitable and |
470 | /// consequently is counted. |
471 | /// returns A tuple of number of loops and their maximal depth. |
472 | static ScopDetection::LoopStats |
473 | countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, |
474 | unsigned MinProfitableTrips); |
475 | |
476 | /// Check if the function @p F is marked as invalid. |
477 | /// |
478 | /// @note An OpenMP subfunction will be marked as invalid. |
479 | static bool isValidFunction(Function &F); |
480 | |
481 | /// Can ISL compute the trip count of a loop. |
482 | /// |
483 | /// @param L The loop to check. |
484 | /// @param Context The context of scop detection. |
485 | /// |
486 | /// @return True if ISL can compute the trip count of the loop. |
487 | bool canUseISLTripCount(Loop *L, DetectionContext &Context); |
488 | |
489 | /// Print the locations of all detected scops. |
490 | void printLocations(Function &F); |
491 | |
492 | /// Check if a region is reducible or not. |
493 | /// |
494 | /// @param Region The region to check. |
495 | /// @param DbgLoc Parameter to save the location of instruction that |
496 | /// causes irregular control flow if the region is irreducible. |
497 | /// |
498 | /// @return True if R is reducible, false otherwise. |
499 | bool isReducibleRegion(Region &R, DebugLoc &DbgLoc) const; |
500 | |
501 | /// Track diagnostics for invalid scops. |
502 | /// |
503 | /// @param Context The context of scop detection. |
504 | /// @param Assert Throw an assert in verify mode or not. |
505 | /// @param Args Argument list that gets passed to the constructor of RR. |
506 | template <class RR, typename... Args> |
507 | inline bool invalid(DetectionContext &Context, bool Assert, |
508 | Args &&...Arguments) const; |
509 | |
510 | public: |
511 | (const DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI, |
512 | RegionInfo &RI, AAResults &AA, OptimizationRemarkEmitter &ORE); |
513 | |
514 | void detect(Function &F); |
515 | |
516 | /// Get the RegionInfo stored in this pass. |
517 | /// |
518 | /// This was added to give the DOT printer easy access to this information. |
519 | RegionInfo *getRI() const { return &RI; } |
520 | |
521 | /// Get the LoopInfo stored in this pass. |
522 | LoopInfo *getLI() const { return &LI; } |
523 | |
524 | /// Is the region is the maximum region of a Scop? |
525 | /// |
526 | /// @param R The Region to test if it is maximum. |
527 | /// @param Verify Rerun the scop detection to verify SCoP was not invalidated |
528 | /// meanwhile. Do not use if the region's DetectionContect is |
529 | /// referenced by a Scop that is still to be processed. |
530 | /// |
531 | /// @return Return true if R is the maximum Region in a Scop, false otherwise. |
532 | bool isMaxRegionInScop(const Region &R, bool Verify = true); |
533 | |
534 | /// Return the detection context for @p R, nullptr if @p R was invalid. |
535 | DetectionContext *getDetectionContext(const Region *R) const; |
536 | |
537 | /// Return the set of rejection causes for @p R. |
538 | const RejectLog *lookupRejectionLog(const Region *R) const; |
539 | |
540 | /// Get a message why a region is invalid |
541 | /// |
542 | /// @param R The region for which we get the error message |
543 | /// |
544 | /// @return The error or "" if no error appeared. |
545 | std::string regionIsInvalidBecause(const Region *R) const; |
546 | |
547 | /// @name Maximum Region In Scops Iterators |
548 | /// |
549 | /// These iterators iterator over all maximum region in Scops of this |
550 | /// function. |
551 | //@{ |
552 | using iterator = RegionSet::iterator; |
553 | using const_iterator = RegionSet::const_iterator; |
554 | |
555 | iterator begin() { return ValidRegions.begin(); } |
556 | iterator end() { return ValidRegions.end(); } |
557 | |
558 | const_iterator begin() const { return ValidRegions.begin(); } |
559 | const_iterator end() const { return ValidRegions.end(); } |
560 | //@} |
561 | |
562 | /// Emit rejection remarks for all rejected regions. |
563 | /// |
564 | /// @param F The function to emit remarks for. |
565 | void (const Function &F); |
566 | |
567 | /// Mark the function as invalid so we will not extract any scop from |
568 | /// the function. |
569 | /// |
570 | /// @param F The function to mark as invalid. |
571 | static void markFunctionAsInvalid(Function *F); |
572 | |
573 | /// Verify if all valid Regions in this Function are still valid |
574 | /// after some transformations. |
575 | void verifyAnalysis(); |
576 | |
577 | /// Verify if R is still a valid part of Scop after some transformations. |
578 | /// |
579 | /// @param R The Region to verify. |
580 | void verifyRegion(const Region &R); |
581 | |
582 | /// Count the number of loops and the maximal loop depth in @p R. |
583 | /// |
584 | /// @param R The region to check |
585 | /// @param SE The scalar evolution analysis. |
586 | /// @param MinProfitableTrips The minimum number of trip counts from which |
587 | /// a loop is assumed to be profitable and |
588 | /// consequently is counted. |
589 | /// returns A tuple of number of loops and their maximal depth. |
590 | static ScopDetection::LoopStats |
591 | countBeneficialLoops(Region *R, ScalarEvolution &SE, LoopInfo &LI, |
592 | unsigned MinProfitableTrips); |
593 | |
594 | /// Check if the block is a error block. |
595 | /// |
596 | /// A error block is currently any block that fulfills at least one of |
597 | /// the following conditions: |
598 | /// |
599 | /// - It is terminated by an unreachable instruction |
600 | /// - It contains a call to a non-pure function that is not immediately |
601 | /// dominated by a loop header and that does not dominate the region exit. |
602 | /// This is a heuristic to pick only error blocks that are conditionally |
603 | /// executed and can be assumed to be not executed at all without the |
604 | /// domains being available. |
605 | /// |
606 | /// @param BB The block to check. |
607 | /// @param R The analyzed region. |
608 | /// |
609 | /// @return True if the block is a error block, false otherwise. |
610 | bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R); |
611 | |
612 | private: |
613 | /// OptimizationRemarkEmitter object used to emit diagnostic remarks |
614 | OptimizationRemarkEmitter &ORE; |
615 | }; |
616 | |
617 | struct ScopAnalysis : AnalysisInfoMixin<ScopAnalysis> { |
618 | static AnalysisKey Key; |
619 | |
620 | using Result = ScopDetection; |
621 | |
622 | ScopAnalysis(); |
623 | |
624 | Result run(Function &F, FunctionAnalysisManager &FAM); |
625 | }; |
626 | |
627 | struct ScopAnalysisPrinterPass final : PassInfoMixin<ScopAnalysisPrinterPass> { |
628 | ScopAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {} |
629 | |
630 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); |
631 | |
632 | raw_ostream &OS; |
633 | }; |
634 | |
635 | class ScopDetectionWrapperPass final : public FunctionPass { |
636 | std::unique_ptr<ScopDetection> Result; |
637 | |
638 | public: |
639 | ScopDetectionWrapperPass(); |
640 | |
641 | /// @name FunctionPass interface |
642 | ///@{ |
643 | static char ID; |
644 | void getAnalysisUsage(AnalysisUsage &AU) const override; |
645 | void releaseMemory() override; |
646 | bool runOnFunction(Function &F) override; |
647 | void print(raw_ostream &OS, const Module *M = nullptr) const override; |
648 | ///@} |
649 | |
650 | ScopDetection &getSD() const { return *Result; } |
651 | }; |
652 | |
653 | llvm::Pass *createScopDetectionPrinterLegacyPass(llvm::raw_ostream &OS); |
654 | } // namespace polly |
655 | |
656 | namespace llvm { |
657 | void initializeScopDetectionWrapperPassPass(llvm::PassRegistry &); |
658 | void initializeScopDetectionPrinterLegacyPassPass(llvm::PassRegistry &); |
659 | } // namespace llvm |
660 | |
661 | #endif // POLLY_SCOPDETECTION_H |
662 | |