1 | //===- ScopDetection.cpp - Detect Scops -----------------------------------===// |
---|---|
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 | // Function calls and intrinsics that do not have side effects (readnone) |
37 | // or memory intrinsics (memset, memcpy, memmove) are allowed. |
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 | #include "polly/ScopDetection.h" |
47 | #include "polly/LinkAllPasses.h" |
48 | #include "polly/Options.h" |
49 | #include "polly/ScopDetectionDiagnostic.h" |
50 | #include "polly/Support/SCEVValidator.h" |
51 | #include "polly/Support/ScopHelper.h" |
52 | #include "polly/Support/ScopLocation.h" |
53 | #include "llvm/ADT/SmallPtrSet.h" |
54 | #include "llvm/ADT/Statistic.h" |
55 | #include "llvm/Analysis/AliasAnalysis.h" |
56 | #include "llvm/Analysis/Delinearization.h" |
57 | #include "llvm/Analysis/Loads.h" |
58 | #include "llvm/Analysis/LoopInfo.h" |
59 | #include "llvm/Analysis/OptimizationRemarkEmitter.h" |
60 | #include "llvm/Analysis/RegionInfo.h" |
61 | #include "llvm/Analysis/ScalarEvolution.h" |
62 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
63 | #include "llvm/IR/BasicBlock.h" |
64 | #include "llvm/IR/DebugLoc.h" |
65 | #include "llvm/IR/DerivedTypes.h" |
66 | #include "llvm/IR/DiagnosticInfo.h" |
67 | #include "llvm/IR/DiagnosticPrinter.h" |
68 | #include "llvm/IR/Dominators.h" |
69 | #include "llvm/IR/Function.h" |
70 | #include "llvm/IR/InstrTypes.h" |
71 | #include "llvm/IR/Instruction.h" |
72 | #include "llvm/IR/Instructions.h" |
73 | #include "llvm/IR/IntrinsicInst.h" |
74 | #include "llvm/IR/Metadata.h" |
75 | #include "llvm/IR/Module.h" |
76 | #include "llvm/IR/PassManager.h" |
77 | #include "llvm/IR/Value.h" |
78 | #include "llvm/InitializePasses.h" |
79 | #include "llvm/Pass.h" |
80 | #include "llvm/Support/Debug.h" |
81 | #include "llvm/Support/Regex.h" |
82 | #include "llvm/Support/raw_ostream.h" |
83 | #include <algorithm> |
84 | #include <cassert> |
85 | #include <memory> |
86 | #include <stack> |
87 | #include <string> |
88 | #include <utility> |
89 | #include <vector> |
90 | |
91 | using namespace llvm; |
92 | using namespace polly; |
93 | |
94 | #include "polly/Support/PollyDebug.h" |
95 | #define DEBUG_TYPE "polly-detect" |
96 | |
97 | // This option is set to a very high value, as analyzing such loops increases |
98 | // compile time on several cases. For experiments that enable this option, |
99 | // a value of around 40 has been working to avoid run-time regressions with |
100 | // Polly while still exposing interesting optimization opportunities. |
101 | static cl::opt<int> ProfitabilityMinPerLoopInstructions( |
102 | "polly-detect-profitability-min-per-loop-insts", |
103 | cl::desc("The minimal number of per-loop instructions before a single loop " |
104 | "region is considered profitable"), |
105 | cl::Hidden, cl::ValueRequired, cl::init(Val: 100000000), cl::cat(PollyCategory)); |
106 | |
107 | bool polly::PollyProcessUnprofitable; |
108 | |
109 | static cl::opt<bool, true> XPollyProcessUnprofitable( |
110 | "polly-process-unprofitable", |
111 | cl::desc( |
112 | "Process scops that are unlikely to benefit from Polly optimizations."), |
113 | cl::location(L&: PollyProcessUnprofitable), cl::cat(PollyCategory)); |
114 | |
115 | static cl::list<std::string> OnlyFunctions( |
116 | "polly-only-func", |
117 | cl::desc("Only run on functions that match a regex. " |
118 | "Multiple regexes can be comma separated. " |
119 | "Scop detection will run on all functions that match " |
120 | "ANY of the regexes provided."), |
121 | cl::CommaSeparated, cl::cat(PollyCategory)); |
122 | |
123 | static cl::list<std::string> IgnoredFunctions( |
124 | "polly-ignore-func", |
125 | cl::desc("Ignore functions that match a regex. " |
126 | "Multiple regexes can be comma separated. " |
127 | "Scop detection will ignore all functions that match " |
128 | "ANY of the regexes provided."), |
129 | cl::CommaSeparated, cl::cat(PollyCategory)); |
130 | |
131 | bool polly::PollyAllowFullFunction; |
132 | |
133 | static cl::opt<bool, true> |
134 | XAllowFullFunction("polly-detect-full-functions", |
135 | cl::desc("Allow the detection of full functions"), |
136 | cl::location(L&: polly::PollyAllowFullFunction), |
137 | cl::init(Val: false), cl::cat(PollyCategory)); |
138 | |
139 | static cl::opt<std::string> OnlyRegion( |
140 | "polly-only-region", |
141 | cl::desc("Only run on certain regions (The provided identifier must " |
142 | "appear in the name of the region's entry block"), |
143 | cl::value_desc("identifier"), cl::ValueRequired, cl::init(Val: ""), |
144 | cl::cat(PollyCategory)); |
145 | |
146 | static cl::opt<bool> |
147 | IgnoreAliasing("polly-ignore-aliasing", |
148 | cl::desc("Ignore possible aliasing of the array bases"), |
149 | cl::Hidden, cl::cat(PollyCategory)); |
150 | |
151 | bool polly::PollyAllowUnsignedOperations; |
152 | |
153 | static cl::opt<bool, true> XPollyAllowUnsignedOperations( |
154 | "polly-allow-unsigned-operations", |
155 | cl::desc("Allow unsigned operations such as comparisons or zero-extends."), |
156 | cl::location(L&: PollyAllowUnsignedOperations), cl::Hidden, cl::init(Val: true), |
157 | cl::cat(PollyCategory)); |
158 | |
159 | bool polly::PollyUseRuntimeAliasChecks; |
160 | |
161 | static cl::opt<bool, true> XPollyUseRuntimeAliasChecks( |
162 | "polly-use-runtime-alias-checks", |
163 | cl::desc("Use runtime alias checks to resolve possible aliasing."), |
164 | cl::location(L&: PollyUseRuntimeAliasChecks), cl::Hidden, cl::init(Val: true), |
165 | cl::cat(PollyCategory)); |
166 | |
167 | static cl::opt<bool> |
168 | ReportLevel("polly-report", |
169 | cl::desc("Print information about the activities of Polly"), |
170 | cl::cat(PollyCategory)); |
171 | |
172 | static cl::opt<bool> AllowDifferentTypes( |
173 | "polly-allow-differing-element-types", |
174 | cl::desc("Allow different element types for array accesses"), cl::Hidden, |
175 | cl::init(Val: true), cl::cat(PollyCategory)); |
176 | |
177 | static cl::opt<bool> |
178 | AllowNonAffine("polly-allow-nonaffine", |
179 | cl::desc("Allow non affine access functions in arrays"), |
180 | cl::Hidden, cl::cat(PollyCategory)); |
181 | |
182 | static cl::opt<bool> |
183 | AllowModrefCall("polly-allow-modref-calls", |
184 | cl::desc("Allow functions with known modref behavior"), |
185 | cl::Hidden, cl::cat(PollyCategory)); |
186 | |
187 | static cl::opt<bool> AllowNonAffineSubRegions( |
188 | "polly-allow-nonaffine-branches", |
189 | cl::desc("Allow non affine conditions for branches"), cl::Hidden, |
190 | cl::init(Val: true), cl::cat(PollyCategory)); |
191 | |
192 | static cl::opt<bool> |
193 | AllowNonAffineSubLoops("polly-allow-nonaffine-loops", |
194 | cl::desc("Allow non affine conditions for loops"), |
195 | cl::Hidden, cl::cat(PollyCategory)); |
196 | |
197 | static cl::opt<bool, true> |
198 | TrackFailures("polly-detect-track-failures", |
199 | cl::desc("Track failure strings in detecting scop regions"), |
200 | cl::location(L&: PollyTrackFailures), cl::Hidden, cl::init(Val: true), |
201 | cl::cat(PollyCategory)); |
202 | |
203 | static cl::opt<bool> KeepGoing("polly-detect-keep-going", |
204 | cl::desc("Do not fail on the first error."), |
205 | cl::Hidden, cl::cat(PollyCategory)); |
206 | |
207 | static cl::opt<bool, true> |
208 | PollyDelinearizeX("polly-delinearize", |
209 | cl::desc("Delinearize array access functions"), |
210 | cl::location(L&: PollyDelinearize), cl::Hidden, |
211 | cl::init(Val: true), cl::cat(PollyCategory)); |
212 | |
213 | static cl::opt<bool> |
214 | VerifyScops("polly-detect-verify", |
215 | cl::desc("Verify the detected SCoPs after each transformation"), |
216 | cl::Hidden, cl::cat(PollyCategory)); |
217 | |
218 | bool polly::PollyInvariantLoadHoisting; |
219 | |
220 | static cl::opt<bool, true> |
221 | XPollyInvariantLoadHoisting("polly-invariant-load-hoisting", |
222 | cl::desc("Hoist invariant loads."), |
223 | cl::location(L&: PollyInvariantLoadHoisting), |
224 | cl::Hidden, cl::cat(PollyCategory)); |
225 | |
226 | static cl::opt<bool> PollyAllowErrorBlocks( |
227 | "polly-allow-error-blocks", |
228 | cl::desc("Allow to speculate on the execution of 'error blocks'."), |
229 | cl::Hidden, cl::init(Val: true), cl::cat(PollyCategory)); |
230 | |
231 | /// The minimal trip count under which loops are considered unprofitable. |
232 | static const unsigned MIN_LOOP_TRIP_COUNT = 8; |
233 | |
234 | bool polly::PollyTrackFailures = false; |
235 | bool polly::PollyDelinearize = false; |
236 | StringRef polly::PollySkipFnAttr = "polly.skip.fn"; |
237 | |
238 | //===----------------------------------------------------------------------===// |
239 | // Statistics. |
240 | |
241 | STATISTIC(NumScopRegions, "Number of scops"); |
242 | STATISTIC(NumLoopsInScop, "Number of loops in scops"); |
243 | STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0"); |
244 | STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1"); |
245 | STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2"); |
246 | STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3"); |
247 | STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4"); |
248 | STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5"); |
249 | STATISTIC(NumScopsDepthLarger, |
250 | "Number of scops with maximal loop depth 6 and larger"); |
251 | STATISTIC(NumProfScopRegions, "Number of scops (profitable scops only)"); |
252 | STATISTIC(NumLoopsInProfScop, |
253 | "Number of loops in scops (profitable scops only)"); |
254 | STATISTIC(NumLoopsOverall, "Number of total loops"); |
255 | STATISTIC(NumProfScopsDepthZero, |
256 | "Number of scops with maximal loop depth 0 (profitable scops only)"); |
257 | STATISTIC(NumProfScopsDepthOne, |
258 | "Number of scops with maximal loop depth 1 (profitable scops only)"); |
259 | STATISTIC(NumProfScopsDepthTwo, |
260 | "Number of scops with maximal loop depth 2 (profitable scops only)"); |
261 | STATISTIC(NumProfScopsDepthThree, |
262 | "Number of scops with maximal loop depth 3 (profitable scops only)"); |
263 | STATISTIC(NumProfScopsDepthFour, |
264 | "Number of scops with maximal loop depth 4 (profitable scops only)"); |
265 | STATISTIC(NumProfScopsDepthFive, |
266 | "Number of scops with maximal loop depth 5 (profitable scops only)"); |
267 | STATISTIC(NumProfScopsDepthLarger, |
268 | "Number of scops with maximal loop depth 6 and larger " |
269 | "(profitable scops only)"); |
270 | STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops"); |
271 | STATISTIC(MaxNumLoopsInProfScop, |
272 | "Maximal number of loops in scops (profitable scops only)"); |
273 | |
274 | static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, |
275 | bool OnlyProfitable); |
276 | |
277 | namespace { |
278 | |
279 | class DiagnosticScopFound final : public DiagnosticInfo { |
280 | private: |
281 | static int PluginDiagnosticKind; |
282 | |
283 | Function &F; |
284 | std::string FileName; |
285 | unsigned EntryLine, ExitLine; |
286 | |
287 | public: |
288 | DiagnosticScopFound(Function &F, std::string FileName, unsigned EntryLine, |
289 | unsigned ExitLine) |
290 | : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName), |
291 | EntryLine(EntryLine), ExitLine(ExitLine) {} |
292 | |
293 | void print(DiagnosticPrinter &DP) const override; |
294 | |
295 | static bool classof(const DiagnosticInfo *DI) { |
296 | return DI->getKind() == PluginDiagnosticKind; |
297 | } |
298 | }; |
299 | } // namespace |
300 | |
301 | int DiagnosticScopFound::PluginDiagnosticKind = |
302 | getNextAvailablePluginDiagnosticKind(); |
303 | |
304 | void DiagnosticScopFound::print(DiagnosticPrinter &DP) const { |
305 | DP << "Polly detected an optimizable loop region (scop) in function '"<< F |
306 | << "'\n"; |
307 | |
308 | if (FileName.empty()) { |
309 | DP << "Scop location is unknown. Compile with debug info " |
310 | "(-g) to get more precise information. "; |
311 | return; |
312 | } |
313 | |
314 | DP << FileName << ":"<< EntryLine << ": Start of scop\n"; |
315 | DP << FileName << ":"<< ExitLine << ": End of scop"; |
316 | } |
317 | |
318 | /// Check if a string matches any regex in a list of regexes. |
319 | /// @param Str the input string to match against. |
320 | /// @param RegexList a list of strings that are regular expressions. |
321 | static bool doesStringMatchAnyRegex(StringRef Str, |
322 | const cl::list<std::string> &RegexList) { |
323 | for (auto RegexStr : RegexList) { |
324 | Regex R(RegexStr); |
325 | |
326 | std::string Err; |
327 | if (!R.isValid(Error&: Err)) |
328 | report_fatal_error(reason: Twine("invalid regex given as input to polly: ") + Err, |
329 | gen_crash_diag: true); |
330 | |
331 | if (R.match(String: Str)) |
332 | return true; |
333 | } |
334 | return false; |
335 | } |
336 | |
337 | //===----------------------------------------------------------------------===// |
338 | // ScopDetection. |
339 | |
340 | ScopDetection::ScopDetection(const DominatorTree &DT, ScalarEvolution &SE, |
341 | LoopInfo &LI, RegionInfo &RI, AAResults &AA, |
342 | OptimizationRemarkEmitter &ORE) |
343 | : DT(DT), SE(SE), LI(LI), RI(RI), AA(AA), ORE(ORE) {} |
344 | |
345 | void ScopDetection::detect(Function &F) { |
346 | assert(ValidRegions.empty() && "Detection must run only once"); |
347 | |
348 | if (!PollyProcessUnprofitable && LI.empty()) |
349 | return; |
350 | |
351 | Region *TopRegion = RI.getTopLevelRegion(); |
352 | |
353 | if (!OnlyFunctions.empty() && |
354 | !doesStringMatchAnyRegex(Str: F.getName(), RegexList: OnlyFunctions)) |
355 | return; |
356 | |
357 | if (doesStringMatchAnyRegex(Str: F.getName(), RegexList: IgnoredFunctions)) |
358 | return; |
359 | |
360 | if (!isValidFunction(F)) |
361 | return; |
362 | |
363 | findScops(R&: *TopRegion); |
364 | |
365 | NumScopRegions += ValidRegions.size(); |
366 | |
367 | // Prune non-profitable regions. |
368 | for (auto &DIt : DetectionContextMap) { |
369 | DetectionContext &DC = *DIt.getSecond(); |
370 | if (DC.Log.hasErrors()) |
371 | continue; |
372 | if (!ValidRegions.count(key: &DC.CurRegion)) |
373 | continue; |
374 | LoopStats Stats = countBeneficialLoops(R: &DC.CurRegion, SE, LI, MinProfitableTrips: 0); |
375 | updateLoopCountStatistic(Stats, OnlyProfitable: false /* OnlyProfitable */); |
376 | if (isProfitableRegion(Context&: DC)) { |
377 | updateLoopCountStatistic(Stats, OnlyProfitable: true /* OnlyProfitable */); |
378 | continue; |
379 | } |
380 | |
381 | ValidRegions.remove(X: &DC.CurRegion); |
382 | } |
383 | |
384 | NumProfScopRegions += ValidRegions.size(); |
385 | NumLoopsOverall += countBeneficialLoops(R: TopRegion, SE, LI, MinProfitableTrips: 0).NumLoops; |
386 | |
387 | // Only makes sense when we tracked errors. |
388 | if (PollyTrackFailures) |
389 | emitMissedRemarks(F); |
390 | |
391 | if (ReportLevel) |
392 | printLocations(F); |
393 | |
394 | assert(ValidRegions.size() <= DetectionContextMap.size() && |
395 | "Cached more results than valid regions"); |
396 | } |
397 | |
398 | template <class RR, typename... Args> |
399 | inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert, |
400 | Args &&...Arguments) const { |
401 | if (!Context.Verifying) { |
402 | RejectLog &Log = Context.Log; |
403 | std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...); |
404 | Context.IsInvalid = true; |
405 | |
406 | // Log even if PollyTrackFailures is false, the log entries are also used in |
407 | // canUseISLTripCount(). |
408 | Log.report(Reject: RejectReason); |
409 | |
410 | POLLY_DEBUG(dbgs() << RejectReason->getMessage()); |
411 | POLLY_DEBUG(dbgs() << "\n"); |
412 | } else { |
413 | assert(!Assert && "Verification of detected scop failed"); |
414 | } |
415 | |
416 | return false; |
417 | } |
418 | |
419 | bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) { |
420 | if (!ValidRegions.count(key: &R)) |
421 | return false; |
422 | |
423 | if (Verify) { |
424 | BBPair P = getBBPairForRegion(R: &R); |
425 | std::unique_ptr<DetectionContext> &Entry = DetectionContextMap[P]; |
426 | |
427 | // Free previous DetectionContext for the region and create and verify a new |
428 | // one. Be sure that the DetectionContext is not still used by a ScopInfop. |
429 | // Due to changes but CodeGeneration of another Scop, the Region object and |
430 | // the BBPair might not match anymore. |
431 | Entry = std::make_unique<DetectionContext>(args&: const_cast<Region &>(R), args&: AA, |
432 | /*Verifying=*/args: false); |
433 | |
434 | return isValidRegion(Context&: *Entry); |
435 | } |
436 | |
437 | return true; |
438 | } |
439 | |
440 | std::string ScopDetection::regionIsInvalidBecause(const Region *R) const { |
441 | // Get the first error we found. Even in keep-going mode, this is the first |
442 | // reason that caused the candidate to be rejected. |
443 | auto *Log = lookupRejectionLog(R); |
444 | |
445 | // This can happen when we marked a region invalid, but didn't track |
446 | // an error for it. |
447 | if (!Log || !Log->hasErrors()) |
448 | return ""; |
449 | |
450 | RejectReasonPtr RR = *Log->begin(); |
451 | return RR->getMessage(); |
452 | } |
453 | |
454 | bool ScopDetection::addOverApproximatedRegion(Region *AR, |
455 | DetectionContext &Context) const { |
456 | // If we already know about Ar we can exit. |
457 | if (!Context.NonAffineSubRegionSet.insert(X: AR)) |
458 | return true; |
459 | |
460 | // All loops in the region have to be overapproximated too if there |
461 | // are accesses that depend on the iteration count. |
462 | |
463 | for (BasicBlock *BB : AR->blocks()) { |
464 | Loop *L = LI.getLoopFor(BB); |
465 | if (AR->contains(L)) |
466 | Context.BoxedLoopsSet.insert(X: L); |
467 | } |
468 | |
469 | return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty()); |
470 | } |
471 | |
472 | bool ScopDetection::onlyValidRequiredInvariantLoads( |
473 | InvariantLoadsSetTy &RequiredILS, DetectionContext &Context) const { |
474 | Region &CurRegion = Context.CurRegion; |
475 | const DataLayout &DL = CurRegion.getEntry()->getModule()->getDataLayout(); |
476 | |
477 | if (!PollyInvariantLoadHoisting && !RequiredILS.empty()) |
478 | return false; |
479 | |
480 | for (LoadInst *Load : RequiredILS) { |
481 | // If we already know a load has been accepted as required invariant, we |
482 | // already run the validation below once and consequently don't need to |
483 | // run it again. Hence, we return early. For certain test cases (e.g., |
484 | // COSMO this avoids us spending 50% of scop-detection time in this |
485 | // very function (and its children). |
486 | if (Context.RequiredILS.count(key: Load)) |
487 | continue; |
488 | if (!isHoistableLoad(LInst: Load, R&: CurRegion, LI, SE, DT, KnownInvariantLoads: Context.RequiredILS)) |
489 | return false; |
490 | |
491 | for (auto NonAffineRegion : Context.NonAffineSubRegionSet) { |
492 | if (isSafeToLoadUnconditionally(V: Load->getPointerOperand(), |
493 | Ty: Load->getType(), Alignment: Load->getAlign(), DL, |
494 | ScanFrom: nullptr)) |
495 | continue; |
496 | |
497 | if (NonAffineRegion->contains(Inst: Load) && |
498 | Load->getParent() != NonAffineRegion->getEntry()) |
499 | return false; |
500 | } |
501 | } |
502 | |
503 | Context.RequiredILS.insert_range(R&: RequiredILS); |
504 | |
505 | return true; |
506 | } |
507 | |
508 | bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, |
509 | Loop *Scope) const { |
510 | SetVector<Value *> Values; |
511 | findValues(Expr: S0, SE, Values); |
512 | if (S1) |
513 | findValues(Expr: S1, SE, Values); |
514 | |
515 | SmallPtrSet<Value *, 8> PtrVals; |
516 | for (auto *V : Values) { |
517 | if (auto *P2I = dyn_cast<PtrToIntInst>(Val: V)) |
518 | V = P2I->getOperand(i_nocapture: 0); |
519 | |
520 | if (!V->getType()->isPointerTy()) |
521 | continue; |
522 | |
523 | const SCEV *PtrSCEV = SE.getSCEVAtScope(V, L: Scope); |
524 | if (isa<SCEVConstant>(Val: PtrSCEV)) |
525 | continue; |
526 | |
527 | auto *BasePtr = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: PtrSCEV)); |
528 | if (!BasePtr) |
529 | return true; |
530 | |
531 | Value *BasePtrVal = BasePtr->getValue(); |
532 | if (PtrVals.insert(Ptr: BasePtrVal).second) { |
533 | for (auto *PtrVal : PtrVals) |
534 | if (PtrVal != BasePtrVal && !AA.isNoAlias(V1: PtrVal, V2: BasePtrVal)) |
535 | return true; |
536 | } |
537 | } |
538 | |
539 | return false; |
540 | } |
541 | |
542 | bool ScopDetection::isAffine(const SCEV *S, Loop *Scope, |
543 | DetectionContext &Context) const { |
544 | InvariantLoadsSetTy AccessILS; |
545 | if (!isAffineExpr(R: &Context.CurRegion, Scope, Expression: S, SE, ILS: &AccessILS)) |
546 | return false; |
547 | |
548 | if (!onlyValidRequiredInvariantLoads(RequiredILS&: AccessILS, Context)) |
549 | return false; |
550 | |
551 | return true; |
552 | } |
553 | |
554 | bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI, |
555 | Value *Condition, bool IsLoopBranch, |
556 | DetectionContext &Context) const { |
557 | Loop *L = LI.getLoopFor(BB: &BB); |
558 | const SCEV *ConditionSCEV = SE.getSCEVAtScope(V: Condition, L); |
559 | |
560 | if (IsLoopBranch && L->isLoopLatch(BB: &BB)) |
561 | return false; |
562 | |
563 | // Check for invalid usage of different pointers in one expression. |
564 | if (involvesMultiplePtrs(S0: ConditionSCEV, S1: nullptr, Scope: L)) |
565 | return false; |
566 | |
567 | if (isAffine(S: ConditionSCEV, Scope: L, Context)) |
568 | return true; |
569 | |
570 | if (AllowNonAffineSubRegions && |
571 | addOverApproximatedRegion(AR: RI.getRegionFor(BB: &BB), Context)) |
572 | return true; |
573 | |
574 | return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, Arguments: &BB, |
575 | Arguments&: ConditionSCEV, Arguments&: ConditionSCEV, Arguments&: SI); |
576 | } |
577 | |
578 | bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI, |
579 | Value *Condition, bool IsLoopBranch, |
580 | DetectionContext &Context) { |
581 | // Constant integer conditions are always affine. |
582 | if (isa<ConstantInt>(Val: Condition)) |
583 | return true; |
584 | |
585 | if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val: Condition)) { |
586 | auto Opcode = BinOp->getOpcode(); |
587 | if (Opcode == Instruction::And || Opcode == Instruction::Or) { |
588 | Value *Op0 = BinOp->getOperand(i_nocapture: 0); |
589 | Value *Op1 = BinOp->getOperand(i_nocapture: 1); |
590 | return isValidBranch(BB, BI, Condition: Op0, IsLoopBranch, Context) && |
591 | isValidBranch(BB, BI, Condition: Op1, IsLoopBranch, Context); |
592 | } |
593 | } |
594 | |
595 | if (auto PHI = dyn_cast<PHINode>(Val: Condition)) { |
596 | auto *Unique = dyn_cast_or_null<ConstantInt>( |
597 | Val: getUniqueNonErrorValue(PHI, R: &Context.CurRegion, SD: this)); |
598 | if (Unique && (Unique->isZero() || Unique->isOne())) |
599 | return true; |
600 | } |
601 | |
602 | if (auto Load = dyn_cast<LoadInst>(Val: Condition)) |
603 | if (!IsLoopBranch && Context.CurRegion.contains(Inst: Load)) { |
604 | Context.RequiredILS.insert(X: Load); |
605 | return true; |
606 | } |
607 | |
608 | // Non constant conditions of branches need to be ICmpInst. |
609 | if (!isa<ICmpInst>(Val: Condition)) { |
610 | if (!IsLoopBranch && AllowNonAffineSubRegions && |
611 | addOverApproximatedRegion(AR: RI.getRegionFor(BB: &BB), Context)) |
612 | return true; |
613 | return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Arguments&: BI, Arguments: &BB); |
614 | } |
615 | |
616 | ICmpInst *ICmp = cast<ICmpInst>(Val: Condition); |
617 | |
618 | // Are both operands of the ICmp affine? |
619 | if (isa<UndefValue>(Val: ICmp->getOperand(i_nocapture: 0)) || |
620 | isa<UndefValue>(Val: ICmp->getOperand(i_nocapture: 1))) |
621 | return invalid<ReportUndefOperand>(Context, /*Assert=*/true, Arguments: &BB, Arguments&: ICmp); |
622 | |
623 | Loop *L = LI.getLoopFor(BB: &BB); |
624 | const SCEV *LHS = SE.getSCEVAtScope(V: ICmp->getOperand(i_nocapture: 0), L); |
625 | const SCEV *RHS = SE.getSCEVAtScope(V: ICmp->getOperand(i_nocapture: 1), L); |
626 | |
627 | LHS = tryForwardThroughPHI(Expr: LHS, R&: Context.CurRegion, SE, SD: this); |
628 | RHS = tryForwardThroughPHI(Expr: RHS, R&: Context.CurRegion, SE, SD: this); |
629 | |
630 | // If unsigned operations are not allowed try to approximate the region. |
631 | if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations) |
632 | return !IsLoopBranch && AllowNonAffineSubRegions && |
633 | addOverApproximatedRegion(AR: RI.getRegionFor(BB: &BB), Context); |
634 | |
635 | // Check for invalid usage of different pointers in one expression. |
636 | if (ICmp->isEquality() && involvesMultiplePtrs(S0: LHS, S1: nullptr, Scope: L) && |
637 | involvesMultiplePtrs(S0: RHS, S1: nullptr, Scope: L)) |
638 | return false; |
639 | |
640 | // Check for invalid usage of different pointers in a relational comparison. |
641 | if (ICmp->isRelational() && involvesMultiplePtrs(S0: LHS, S1: RHS, Scope: L)) |
642 | return false; |
643 | |
644 | if (isAffine(S: LHS, Scope: L, Context) && isAffine(S: RHS, Scope: L, Context)) |
645 | return true; |
646 | |
647 | if (!IsLoopBranch && AllowNonAffineSubRegions && |
648 | addOverApproximatedRegion(AR: RI.getRegionFor(BB: &BB), Context)) |
649 | return true; |
650 | |
651 | if (IsLoopBranch) |
652 | return false; |
653 | |
654 | return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, Arguments: &BB, Arguments&: LHS, Arguments&: RHS, |
655 | Arguments&: ICmp); |
656 | } |
657 | |
658 | bool ScopDetection::isValidCFG(BasicBlock &BB, bool IsLoopBranch, |
659 | bool AllowUnreachable, |
660 | DetectionContext &Context) { |
661 | Region &CurRegion = Context.CurRegion; |
662 | |
663 | Instruction *TI = BB.getTerminator(); |
664 | |
665 | if (AllowUnreachable && isa<UnreachableInst>(Val: TI)) |
666 | return true; |
667 | |
668 | // Return instructions are only valid if the region is the top level region. |
669 | if (isa<ReturnInst>(Val: TI) && CurRegion.isTopLevelRegion()) |
670 | return true; |
671 | |
672 | Value *Condition = getConditionFromTerminator(TI); |
673 | |
674 | if (!Condition) |
675 | return invalid<ReportInvalidTerminator>(Context, /*Assert=*/true, Arguments: &BB); |
676 | |
677 | // UndefValue is not allowed as condition. |
678 | if (isa<UndefValue>(Val: Condition)) |
679 | return invalid<ReportUndefCond>(Context, /*Assert=*/true, Arguments&: TI, Arguments: &BB); |
680 | |
681 | if (BranchInst *BI = dyn_cast<BranchInst>(Val: TI)) |
682 | return isValidBranch(BB, BI, Condition, IsLoopBranch, Context); |
683 | |
684 | SwitchInst *SI = dyn_cast<SwitchInst>(Val: TI); |
685 | assert(SI && "Terminator was neither branch nor switch"); |
686 | |
687 | return isValidSwitch(BB, SI, Condition, IsLoopBranch, Context); |
688 | } |
689 | |
690 | bool ScopDetection::isValidCallInst(CallInst &CI, |
691 | DetectionContext &Context) const { |
692 | if (CI.doesNotReturn()) |
693 | return false; |
694 | |
695 | if (CI.doesNotAccessMemory()) |
696 | return true; |
697 | |
698 | if (auto *II = dyn_cast<IntrinsicInst>(Val: &CI)) |
699 | if (isValidIntrinsicInst(II&: *II, Context)) |
700 | return true; |
701 | |
702 | Function *CalledFunction = CI.getCalledFunction(); |
703 | |
704 | // Indirect calls are not supported. |
705 | if (CalledFunction == nullptr) |
706 | return false; |
707 | |
708 | if (isDebugCall(Inst: &CI)) { |
709 | POLLY_DEBUG(dbgs() << "Allow call to debug function: " |
710 | << CalledFunction->getName() << '\n'); |
711 | return true; |
712 | } |
713 | |
714 | if (AllowModrefCall) { |
715 | MemoryEffects ME = AA.getMemoryEffects(F: CalledFunction); |
716 | if (ME.onlyAccessesArgPointees()) { |
717 | for (const auto &Arg : CI.args()) { |
718 | if (!Arg->getType()->isPointerTy()) |
719 | continue; |
720 | |
721 | // Bail if a pointer argument has a base address not known to |
722 | // ScalarEvolution. Note that a zero pointer is acceptable. |
723 | const SCEV *ArgSCEV = |
724 | SE.getSCEVAtScope(V: Arg, L: LI.getLoopFor(BB: CI.getParent())); |
725 | if (ArgSCEV->isZero()) |
726 | continue; |
727 | |
728 | auto *BP = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: ArgSCEV)); |
729 | if (!BP) |
730 | return false; |
731 | |
732 | // Implicitly disable delinearization since we have an unknown |
733 | // accesses with an unknown access function. |
734 | Context.HasUnknownAccess = true; |
735 | } |
736 | |
737 | // Explicitly use addUnknown so we don't put a loop-variant |
738 | // pointer into the alias set. |
739 | Context.AST.addUnknown(I: &CI); |
740 | return true; |
741 | } |
742 | |
743 | if (ME.onlyReadsMemory()) { |
744 | // Implicitly disable delinearization since we have an unknown |
745 | // accesses with an unknown access function. |
746 | Context.HasUnknownAccess = true; |
747 | // Explicitly use addUnknown so we don't put a loop-variant |
748 | // pointer into the alias set. |
749 | Context.AST.addUnknown(I: &CI); |
750 | return true; |
751 | } |
752 | return false; |
753 | } |
754 | |
755 | return false; |
756 | } |
757 | |
758 | bool ScopDetection::isValidIntrinsicInst(IntrinsicInst &II, |
759 | DetectionContext &Context) const { |
760 | if (isIgnoredIntrinsic(V: &II)) |
761 | return true; |
762 | |
763 | // The closest loop surrounding the call instruction. |
764 | Loop *L = LI.getLoopFor(BB: II.getParent()); |
765 | |
766 | // The access function and base pointer for memory intrinsics. |
767 | const SCEV *AF; |
768 | const SCEVUnknown *BP; |
769 | |
770 | switch (II.getIntrinsicID()) { |
771 | // Memory intrinsics that can be represented are supported. |
772 | case Intrinsic::memmove: |
773 | case Intrinsic::memcpy: |
774 | AF = SE.getSCEVAtScope(V: cast<MemTransferInst>(Val&: II).getSource(), L); |
775 | if (!AF->isZero()) { |
776 | BP = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AF)); |
777 | // Bail if the source pointer is not valid. |
778 | if (!isValidAccess(Inst: &II, AF, BP, Context)) |
779 | return false; |
780 | } |
781 | [[fallthrough]]; |
782 | case Intrinsic::memset: |
783 | AF = SE.getSCEVAtScope(V: cast<MemIntrinsic>(Val&: II).getDest(), L); |
784 | if (!AF->isZero()) { |
785 | BP = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AF)); |
786 | // Bail if the destination pointer is not valid. |
787 | if (!isValidAccess(Inst: &II, AF, BP, Context)) |
788 | return false; |
789 | } |
790 | |
791 | // Bail if the length is not affine. |
792 | if (!isAffine(S: SE.getSCEVAtScope(V: cast<MemIntrinsic>(Val&: II).getLength(), L), Scope: L, |
793 | Context)) |
794 | return false; |
795 | |
796 | return true; |
797 | default: |
798 | break; |
799 | } |
800 | |
801 | return false; |
802 | } |
803 | |
804 | bool ScopDetection::isInvariant(Value &Val, const Region &Reg, |
805 | DetectionContext &Ctx) const { |
806 | // A reference to function argument or constant value is invariant. |
807 | if (isa<Argument>(Val) || isa<Constant>(Val)) |
808 | return true; |
809 | |
810 | Instruction *I = dyn_cast<Instruction>(Val: &Val); |
811 | if (!I) |
812 | return false; |
813 | |
814 | if (!Reg.contains(Inst: I)) |
815 | return true; |
816 | |
817 | // Loads within the SCoP may read arbitrary values, need to hoist them. If it |
818 | // is not hoistable, it will be rejected later, but here we assume it is and |
819 | // that makes the value invariant. |
820 | if (auto LI = dyn_cast<LoadInst>(Val: I)) { |
821 | Ctx.RequiredILS.insert(X: LI); |
822 | return true; |
823 | } |
824 | |
825 | return false; |
826 | } |
827 | |
828 | namespace { |
829 | |
830 | /// Remove smax of smax(0, size) expressions from a SCEV expression and |
831 | /// register the '...' components. |
832 | /// |
833 | /// Array access expressions as they are generated by GFortran contain smax(0, |
834 | /// size) expressions that confuse the 'normal' delinearization algorithm. |
835 | /// However, if we extract such expressions before the normal delinearization |
836 | /// takes place they can actually help to identify array size expressions in |
837 | /// Fortran accesses. For the subsequently following delinearization the smax(0, |
838 | /// size) component can be replaced by just 'size'. This is correct as we will |
839 | /// always add and verify the assumption that for all subscript expressions |
840 | /// 'exp' the inequality 0 <= exp < size holds. Hence, we will also verify |
841 | /// that 0 <= size, which means smax(0, size) == size. |
842 | class SCEVRemoveMax final : public SCEVRewriteVisitor<SCEVRemoveMax> { |
843 | public: |
844 | SCEVRemoveMax(ScalarEvolution &SE, std::vector<const SCEV *> *Terms) |
845 | : SCEVRewriteVisitor(SE), Terms(Terms) {} |
846 | |
847 | static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, |
848 | std::vector<const SCEV *> *Terms = nullptr) { |
849 | SCEVRemoveMax Rewriter(SE, Terms); |
850 | return Rewriter.visit(S: Scev); |
851 | } |
852 | |
853 | const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { |
854 | if ((Expr->getNumOperands() == 2) && Expr->getOperand(i: 0)->isZero()) { |
855 | auto Res = visit(S: Expr->getOperand(i: 1)); |
856 | if (Terms) |
857 | (*Terms).push_back(x: Res); |
858 | return Res; |
859 | } |
860 | |
861 | return Expr; |
862 | } |
863 | |
864 | private: |
865 | std::vector<const SCEV *> *Terms; |
866 | }; |
867 | } // namespace |
868 | |
869 | SmallVector<const SCEV *, 4> |
870 | ScopDetection::getDelinearizationTerms(DetectionContext &Context, |
871 | const SCEVUnknown *BasePointer) const { |
872 | SmallVector<const SCEV *, 4> Terms; |
873 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
874 | std::vector<const SCEV *> MaxTerms; |
875 | SCEVRemoveMax::rewrite(Scev: Pair.second, SE, Terms: &MaxTerms); |
876 | if (!MaxTerms.empty()) { |
877 | Terms.insert(I: Terms.begin(), From: MaxTerms.begin(), To: MaxTerms.end()); |
878 | continue; |
879 | } |
880 | // In case the outermost expression is a plain add, we check if any of its |
881 | // terms has the form 4 * %inst * %param * %param ..., aka a term that |
882 | // contains a product between a parameter and an instruction that is |
883 | // inside the scop. Such instructions, if allowed at all, are instructions |
884 | // SCEV can not represent, but Polly is still looking through. As a |
885 | // result, these instructions can depend on induction variables and are |
886 | // most likely no array sizes. However, terms that are multiplied with |
887 | // them are likely candidates for array sizes. |
888 | if (auto *AF = dyn_cast<SCEVAddExpr>(Val: Pair.second)) { |
889 | for (auto Op : AF->operands()) { |
890 | if (auto *AF2 = dyn_cast<SCEVAddRecExpr>(Val: Op)) |
891 | collectParametricTerms(SE, Expr: AF2, Terms); |
892 | if (auto *AF2 = dyn_cast<SCEVMulExpr>(Val: Op)) { |
893 | SmallVector<const SCEV *, 0> Operands; |
894 | |
895 | for (const SCEV *MulOp : AF2->operands()) { |
896 | if (auto *Const = dyn_cast<SCEVConstant>(Val: MulOp)) |
897 | Operands.push_back(Elt: Const); |
898 | if (auto *Unknown = dyn_cast<SCEVUnknown>(Val: MulOp)) { |
899 | if (auto *Inst = dyn_cast<Instruction>(Val: Unknown->getValue())) { |
900 | if (!Context.CurRegion.contains(Inst)) |
901 | Operands.push_back(Elt: MulOp); |
902 | |
903 | } else { |
904 | Operands.push_back(Elt: MulOp); |
905 | } |
906 | } |
907 | } |
908 | if (Operands.size()) |
909 | Terms.push_back(Elt: SE.getMulExpr(Ops&: Operands)); |
910 | } |
911 | } |
912 | } |
913 | if (Terms.empty()) |
914 | collectParametricTerms(SE, Expr: Pair.second, Terms); |
915 | } |
916 | return Terms; |
917 | } |
918 | |
919 | bool ScopDetection::hasValidArraySizes(DetectionContext &Context, |
920 | SmallVectorImpl<const SCEV *> &Sizes, |
921 | const SCEVUnknown *BasePointer, |
922 | Loop *Scope) const { |
923 | // If no sizes were found, all sizes are trivially valid. We allow this case |
924 | // to make it possible to pass known-affine accesses to the delinearization to |
925 | // try to recover some interesting multi-dimensional accesses, but to still |
926 | // allow the already known to be affine access in case the delinearization |
927 | // fails. In such situations, the delinearization will just return a Sizes |
928 | // array of size zero. |
929 | if (Sizes.size() == 0) |
930 | return true; |
931 | |
932 | Value *BaseValue = BasePointer->getValue(); |
933 | Region &CurRegion = Context.CurRegion; |
934 | for (const SCEV *DelinearizedSize : Sizes) { |
935 | // Don't pass down the scope to isAfffine; array dimensions must be |
936 | // invariant across the entire scop. |
937 | if (!isAffine(S: DelinearizedSize, Scope: nullptr, Context)) { |
938 | Sizes.clear(); |
939 | break; |
940 | } |
941 | if (auto *Unknown = dyn_cast<SCEVUnknown>(Val: DelinearizedSize)) { |
942 | auto *V = dyn_cast<Value>(Val: Unknown->getValue()); |
943 | if (auto *Load = dyn_cast<LoadInst>(Val: V)) { |
944 | if (Context.CurRegion.contains(Inst: Load) && |
945 | isHoistableLoad(LInst: Load, R&: CurRegion, LI, SE, DT, KnownInvariantLoads: Context.RequiredILS)) |
946 | Context.RequiredILS.insert(X: Load); |
947 | continue; |
948 | } |
949 | } |
950 | if (hasScalarDepsInsideRegion(Expr: DelinearizedSize, R: &CurRegion, Scope, AllowLoops: false, |
951 | ILS: Context.RequiredILS)) |
952 | return invalid<ReportNonAffineAccess>( |
953 | Context, /*Assert=*/true, Arguments&: DelinearizedSize, |
954 | Arguments&: Context.Accesses[BasePointer].front().first, Arguments&: BaseValue); |
955 | } |
956 | |
957 | // No array shape derived. |
958 | if (Sizes.empty()) { |
959 | if (AllowNonAffine) |
960 | return true; |
961 | |
962 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
963 | const Instruction *Insn = Pair.first; |
964 | const SCEV *AF = Pair.second; |
965 | |
966 | if (!isAffine(S: AF, Scope, Context)) { |
967 | invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Arguments&: AF, Arguments&: Insn, |
968 | Arguments&: BaseValue); |
969 | if (!KeepGoing) |
970 | return false; |
971 | } |
972 | } |
973 | return false; |
974 | } |
975 | return true; |
976 | } |
977 | |
978 | // We first store the resulting memory accesses in TempMemoryAccesses. Only |
979 | // if the access functions for all memory accesses have been successfully |
980 | // delinearized we continue. Otherwise, we either report a failure or, if |
981 | // non-affine accesses are allowed, we drop the information. In case the |
982 | // information is dropped the memory accesses need to be overapproximated |
983 | // when translated to a polyhedral representation. |
984 | bool ScopDetection::computeAccessFunctions( |
985 | DetectionContext &Context, const SCEVUnknown *BasePointer, |
986 | std::shared_ptr<ArrayShape> Shape) const { |
987 | Value *BaseValue = BasePointer->getValue(); |
988 | bool BasePtrHasNonAffine = false; |
989 | MapInsnToMemAcc TempMemoryAccesses; |
990 | for (const auto &Pair : Context.Accesses[BasePointer]) { |
991 | const Instruction *Insn = Pair.first; |
992 | auto *AF = Pair.second; |
993 | AF = SCEVRemoveMax::rewrite(Scev: AF, SE); |
994 | bool IsNonAffine = false; |
995 | TempMemoryAccesses.insert(x: std::make_pair(x&: Insn, y: MemAcc(Insn, Shape))); |
996 | MemAcc *Acc = &TempMemoryAccesses.find(x: Insn)->second; |
997 | auto *Scope = LI.getLoopFor(BB: Insn->getParent()); |
998 | |
999 | if (!AF) { |
1000 | if (isAffine(S: Pair.second, Scope, Context)) |
1001 | Acc->DelinearizedSubscripts.push_back(Elt: Pair.second); |
1002 | else |
1003 | IsNonAffine = true; |
1004 | } else { |
1005 | if (Shape->DelinearizedSizes.size() == 0) { |
1006 | Acc->DelinearizedSubscripts.push_back(Elt: AF); |
1007 | } else { |
1008 | llvm::computeAccessFunctions(SE, Expr: AF, Subscripts&: Acc->DelinearizedSubscripts, |
1009 | Sizes&: Shape->DelinearizedSizes); |
1010 | if (Acc->DelinearizedSubscripts.size() == 0) |
1011 | IsNonAffine = true; |
1012 | } |
1013 | for (const SCEV *S : Acc->DelinearizedSubscripts) |
1014 | if (!isAffine(S, Scope, Context)) |
1015 | IsNonAffine = true; |
1016 | } |
1017 | |
1018 | // (Possibly) report non affine access |
1019 | if (IsNonAffine) { |
1020 | BasePtrHasNonAffine = true; |
1021 | if (!AllowNonAffine) { |
1022 | invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Arguments: Pair.second, |
1023 | Arguments&: Insn, Arguments&: BaseValue); |
1024 | if (!KeepGoing) |
1025 | return false; |
1026 | } |
1027 | } |
1028 | } |
1029 | |
1030 | if (!BasePtrHasNonAffine) |
1031 | Context.InsnToMemAcc.insert(first: TempMemoryAccesses.begin(), |
1032 | last: TempMemoryAccesses.end()); |
1033 | |
1034 | return true; |
1035 | } |
1036 | |
1037 | bool ScopDetection::hasBaseAffineAccesses(DetectionContext &Context, |
1038 | const SCEVUnknown *BasePointer, |
1039 | Loop *Scope) const { |
1040 | auto Shape = std::shared_ptr<ArrayShape>(new ArrayShape(BasePointer)); |
1041 | |
1042 | auto Terms = getDelinearizationTerms(Context, BasePointer); |
1043 | |
1044 | findArrayDimensions(SE, Terms, Sizes&: Shape->DelinearizedSizes, |
1045 | ElementSize: Context.ElementSize[BasePointer]); |
1046 | |
1047 | if (!hasValidArraySizes(Context, Sizes&: Shape->DelinearizedSizes, BasePointer, |
1048 | Scope)) |
1049 | return false; |
1050 | |
1051 | return computeAccessFunctions(Context, BasePointer, Shape); |
1052 | } |
1053 | |
1054 | bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { |
1055 | // TODO: If we have an unknown access and other non-affine accesses we do |
1056 | // not try to delinearize them for now. |
1057 | if (Context.HasUnknownAccess && !Context.NonAffineAccesses.empty()) |
1058 | return AllowNonAffine; |
1059 | |
1060 | for (auto &Pair : Context.NonAffineAccesses) { |
1061 | auto *BasePointer = Pair.first; |
1062 | auto *Scope = Pair.second; |
1063 | if (!hasBaseAffineAccesses(Context, BasePointer, Scope)) { |
1064 | Context.IsInvalid = true; |
1065 | if (!KeepGoing) |
1066 | return false; |
1067 | } |
1068 | } |
1069 | return true; |
1070 | } |
1071 | |
1072 | bool ScopDetection::isValidAccess(Instruction *Inst, const SCEV *AF, |
1073 | const SCEVUnknown *BP, |
1074 | DetectionContext &Context) const { |
1075 | |
1076 | if (!BP) |
1077 | return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, Arguments&: Inst); |
1078 | |
1079 | auto *BV = BP->getValue(); |
1080 | if (isa<UndefValue>(Val: BV)) |
1081 | return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, Arguments&: Inst); |
1082 | |
1083 | // FIXME: Think about allowing IntToPtrInst |
1084 | if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(Val: BV)) |
1085 | return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Arguments&: Inst); |
1086 | |
1087 | // Check that the base address of the access is invariant in the current |
1088 | // region. |
1089 | if (!isInvariant(Val&: *BV, Reg: Context.CurRegion, Ctx&: Context)) |
1090 | return invalid<ReportVariantBasePtr>(Context, /*Assert=*/true, Arguments&: BV, Arguments&: Inst); |
1091 | |
1092 | AF = SE.getMinusSCEV(LHS: AF, RHS: BP); |
1093 | |
1094 | const SCEV *Size; |
1095 | if (!isa<MemIntrinsic>(Val: Inst)) { |
1096 | Size = SE.getElementSize(Inst); |
1097 | } else { |
1098 | auto *SizeTy = |
1099 | SE.getEffectiveSCEVType(Ty: PointerType::getUnqual(C&: SE.getContext())); |
1100 | Size = SE.getConstant(Ty: SizeTy, V: 8); |
1101 | } |
1102 | |
1103 | if (Context.ElementSize[BP]) { |
1104 | if (!AllowDifferentTypes && Context.ElementSize[BP] != Size) |
1105 | return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true, |
1106 | Arguments&: Inst, Arguments&: BV); |
1107 | |
1108 | Context.ElementSize[BP] = SE.getSMinExpr(LHS: Size, RHS: Context.ElementSize[BP]); |
1109 | } else { |
1110 | Context.ElementSize[BP] = Size; |
1111 | } |
1112 | |
1113 | bool IsVariantInNonAffineLoop = false; |
1114 | SetVector<const Loop *> Loops; |
1115 | findLoops(Expr: AF, Loops); |
1116 | for (const Loop *L : Loops) |
1117 | if (Context.BoxedLoopsSet.count(key: L)) |
1118 | IsVariantInNonAffineLoop = true; |
1119 | |
1120 | auto *Scope = LI.getLoopFor(BB: Inst->getParent()); |
1121 | bool IsAffine = !IsVariantInNonAffineLoop && isAffine(S: AF, Scope, Context); |
1122 | // Do not try to delinearize memory intrinsics and force them to be affine. |
1123 | if (isa<MemIntrinsic>(Val: Inst) && !IsAffine) { |
1124 | return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Arguments&: AF, Arguments&: Inst, |
1125 | Arguments&: BV); |
1126 | } else if (PollyDelinearize && !IsVariantInNonAffineLoop) { |
1127 | Context.Accesses[BP].push_back(x: {Inst, AF}); |
1128 | |
1129 | if (!IsAffine) |
1130 | Context.NonAffineAccesses.insert( |
1131 | X: std::make_pair(x&: BP, y: LI.getLoopFor(BB: Inst->getParent()))); |
1132 | } else if (!AllowNonAffine && !IsAffine) { |
1133 | return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Arguments&: AF, Arguments&: Inst, |
1134 | Arguments&: BV); |
1135 | } |
1136 | |
1137 | if (IgnoreAliasing) |
1138 | return true; |
1139 | |
1140 | // Check if the base pointer of the memory access does alias with |
1141 | // any other pointer. This cannot be handled at the moment. |
1142 | AAMDNodes AATags = Inst->getAAMetadata(); |
1143 | AliasSet &AS = Context.AST.getAliasSetFor( |
1144 | MemLoc: MemoryLocation::getBeforeOrAfter(Ptr: BP->getValue(), AATags)); |
1145 | |
1146 | if (!AS.isMustAlias()) { |
1147 | if (PollyUseRuntimeAliasChecks) { |
1148 | bool CanBuildRunTimeCheck = true; |
1149 | // The run-time alias check places code that involves the base pointer at |
1150 | // the beginning of the SCoP. This breaks if the base pointer is defined |
1151 | // inside the scop. Hence, we can only create a run-time check if we are |
1152 | // sure the base pointer is not an instruction defined inside the scop. |
1153 | // However, we can ignore loads that will be hoisted. |
1154 | |
1155 | auto ASPointers = AS.getPointers(); |
1156 | |
1157 | InvariantLoadsSetTy VariantLS, InvariantLS; |
1158 | // In order to detect loads which are dependent on other invariant loads |
1159 | // as invariant, we use fixed-point iteration method here i.e we iterate |
1160 | // over the alias set for arbitrary number of times until it is safe to |
1161 | // assume that all the invariant loads have been detected |
1162 | while (true) { |
1163 | const unsigned int VariantSize = VariantLS.size(), |
1164 | InvariantSize = InvariantLS.size(); |
1165 | |
1166 | for (const Value *Ptr : ASPointers) { |
1167 | Instruction *Inst = dyn_cast<Instruction>(Val: const_cast<Value *>(Ptr)); |
1168 | if (Inst && Context.CurRegion.contains(Inst)) { |
1169 | auto *Load = dyn_cast<LoadInst>(Val: Inst); |
1170 | if (Load && InvariantLS.count(key: Load)) |
1171 | continue; |
1172 | if (Load && isHoistableLoad(LInst: Load, R&: Context.CurRegion, LI, SE, DT, |
1173 | KnownInvariantLoads: InvariantLS)) { |
1174 | if (VariantLS.count(key: Load)) |
1175 | VariantLS.remove(X: Load); |
1176 | Context.RequiredILS.insert(X: Load); |
1177 | InvariantLS.insert(X: Load); |
1178 | } else { |
1179 | CanBuildRunTimeCheck = false; |
1180 | VariantLS.insert(X: Load); |
1181 | } |
1182 | } |
1183 | } |
1184 | |
1185 | if (InvariantSize == InvariantLS.size() && |
1186 | VariantSize == VariantLS.size()) |
1187 | break; |
1188 | } |
1189 | |
1190 | if (CanBuildRunTimeCheck) |
1191 | return true; |
1192 | } |
1193 | return invalid<ReportAlias>(Context, /*Assert=*/true, Arguments&: Inst, Arguments&: AS); |
1194 | } |
1195 | |
1196 | return true; |
1197 | } |
1198 | |
1199 | bool ScopDetection::isValidMemoryAccess(MemAccInst Inst, |
1200 | DetectionContext &Context) const { |
1201 | Value *Ptr = Inst.getPointerOperand(); |
1202 | Loop *L = LI.getLoopFor(BB: Inst->getParent()); |
1203 | const SCEV *AccessFunction = SE.getSCEVAtScope(V: Ptr, L); |
1204 | const SCEVUnknown *BasePointer; |
1205 | |
1206 | BasePointer = dyn_cast<SCEVUnknown>(Val: SE.getPointerBase(V: AccessFunction)); |
1207 | |
1208 | return isValidAccess(Inst, AF: AccessFunction, BP: BasePointer, Context); |
1209 | } |
1210 | |
1211 | bool ScopDetection::isValidInstruction(Instruction &Inst, |
1212 | DetectionContext &Context) { |
1213 | for (auto &Op : Inst.operands()) { |
1214 | auto *OpInst = dyn_cast<Instruction>(Val: &Op); |
1215 | |
1216 | if (!OpInst) |
1217 | continue; |
1218 | |
1219 | if (isErrorBlock(BB&: *OpInst->getParent(), R: Context.CurRegion)) { |
1220 | auto *PHI = dyn_cast<PHINode>(Val: OpInst); |
1221 | if (PHI) { |
1222 | for (User *U : PHI->users()) { |
1223 | auto *UI = dyn_cast<Instruction>(Val: U); |
1224 | if (!UI || !UI->isTerminator()) |
1225 | return false; |
1226 | } |
1227 | } else { |
1228 | return false; |
1229 | } |
1230 | } |
1231 | } |
1232 | |
1233 | if (isa<LandingPadInst>(Val: &Inst) || isa<ResumeInst>(Val: &Inst)) |
1234 | return false; |
1235 | |
1236 | // We only check the call instruction but not invoke instruction. |
1237 | if (CallInst *CI = dyn_cast<CallInst>(Val: &Inst)) { |
1238 | if (isValidCallInst(CI&: *CI, Context)) |
1239 | return true; |
1240 | |
1241 | return invalid<ReportFuncCall>(Context, /*Assert=*/true, Arguments: &Inst); |
1242 | } |
1243 | |
1244 | if (!Inst.mayReadOrWriteMemory()) { |
1245 | if (!isa<AllocaInst>(Val: Inst)) |
1246 | return true; |
1247 | |
1248 | return invalid<ReportAlloca>(Context, /*Assert=*/true, Arguments: &Inst); |
1249 | } |
1250 | |
1251 | // Check the access function. |
1252 | if (auto MemInst = MemAccInst::dyn_cast(V&: Inst)) { |
1253 | Context.hasStores |= isa<StoreInst>(Val: MemInst); |
1254 | Context.hasLoads |= isa<LoadInst>(Val: MemInst); |
1255 | if (!MemInst.isSimple()) |
1256 | return invalid<ReportNonSimpleMemoryAccess>(Context, /*Assert=*/true, |
1257 | Arguments: &Inst); |
1258 | |
1259 | return isValidMemoryAccess(Inst: MemInst, Context); |
1260 | } |
1261 | |
1262 | // We do not know this instruction, therefore we assume it is invalid. |
1263 | return invalid<ReportUnknownInst>(Context, /*Assert=*/true, Arguments: &Inst); |
1264 | } |
1265 | |
1266 | /// Check whether @p L has exiting blocks. |
1267 | /// |
1268 | /// @param L The loop of interest |
1269 | /// |
1270 | /// @return True if the loop has exiting blocks, false otherwise. |
1271 | static bool hasExitingBlocks(Loop *L) { |
1272 | SmallVector<BasicBlock *, 4> ExitingBlocks; |
1273 | L->getExitingBlocks(ExitingBlocks); |
1274 | return !ExitingBlocks.empty(); |
1275 | } |
1276 | |
1277 | bool ScopDetection::canUseISLTripCount(Loop *L, DetectionContext &Context) { |
1278 | // FIXME: Yes, this is bad. isValidCFG() may call invalid<Reason>() which |
1279 | // causes the SCoP to be rejected regardless on whether non-ISL trip counts |
1280 | // could be used. We currently preserve the legacy behaviour of rejecting |
1281 | // based on Context.Log.size() added by isValidCFG() or before, regardless on |
1282 | // whether the ISL trip count can be used or can be used as a non-affine |
1283 | // region. However, we allow rejections by isValidCFG() that do not result in |
1284 | // an error log entry. |
1285 | bool OldIsInvalid = Context.IsInvalid; |
1286 | |
1287 | // Ensure the loop has valid exiting blocks as well as latches, otherwise we |
1288 | // need to overapproximate it as a boxed loop. |
1289 | SmallVector<BasicBlock *, 4> LoopControlBlocks; |
1290 | L->getExitingBlocks(ExitingBlocks&: LoopControlBlocks); |
1291 | L->getLoopLatches(LoopLatches&: LoopControlBlocks); |
1292 | for (BasicBlock *ControlBB : LoopControlBlocks) { |
1293 | if (!isValidCFG(BB&: *ControlBB, IsLoopBranch: true, AllowUnreachable: false, Context)) { |
1294 | Context.IsInvalid = OldIsInvalid || Context.Log.size(); |
1295 | return false; |
1296 | } |
1297 | } |
1298 | |
1299 | // We can use ISL to compute the trip count of L. |
1300 | Context.IsInvalid = OldIsInvalid || Context.Log.size(); |
1301 | return true; |
1302 | } |
1303 | |
1304 | bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) { |
1305 | // Loops that contain part but not all of the blocks of a region cannot be |
1306 | // handled by the schedule generation. Such loop constructs can happen |
1307 | // because a region can contain BBs that have no path to the exit block |
1308 | // (Infinite loops, UnreachableInst), but such blocks are never part of a |
1309 | // loop. |
1310 | // |
1311 | // _______________ |
1312 | // | Loop Header | <-----------. |
1313 | // --------------- | |
1314 | // | | |
1315 | // _______________ ______________ |
1316 | // | RegionEntry |-----> | RegionExit |-----> |
1317 | // --------------- -------------- |
1318 | // | |
1319 | // _______________ |
1320 | // | EndlessLoop | <--. |
1321 | // --------------- | |
1322 | // | | |
1323 | // \------------/ |
1324 | // |
1325 | // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is |
1326 | // neither entirely contained in the region RegionEntry->RegionExit |
1327 | // (containing RegionEntry,EndlessLoop) nor is the region entirely contained |
1328 | // in the loop. |
1329 | // The block EndlessLoop is contained in the region because Region::contains |
1330 | // tests whether it is not dominated by RegionExit. This is probably to not |
1331 | // having to query the PostdominatorTree. Instead of an endless loop, a dead |
1332 | // end can also be formed by an UnreachableInst. This case is already caught |
1333 | // by isErrorBlock(). We hence only have to reject endless loops here. |
1334 | if (!hasExitingBlocks(L)) |
1335 | return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, Arguments&: L); |
1336 | |
1337 | // The algorithm for domain construction assumes that loops has only a single |
1338 | // exit block (and hence corresponds to a subregion). Note that we cannot use |
1339 | // L->getExitBlock() because it does not check whether all exiting edges point |
1340 | // to the same BB. |
1341 | SmallVector<BasicBlock *, 4> ExitBlocks; |
1342 | L->getExitBlocks(ExitBlocks); |
1343 | BasicBlock *TheExitBlock = ExitBlocks[0]; |
1344 | for (BasicBlock *ExitBB : ExitBlocks) { |
1345 | if (TheExitBlock != ExitBB) |
1346 | return invalid<ReportLoopHasMultipleExits>(Context, /*Assert=*/true, Arguments&: L); |
1347 | } |
1348 | |
1349 | if (canUseISLTripCount(L, Context)) |
1350 | return true; |
1351 | |
1352 | if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) { |
1353 | Region *R = RI.getRegionFor(BB: L->getHeader()); |
1354 | while (R != &Context.CurRegion && !R->contains(L)) |
1355 | R = R->getParent(); |
1356 | |
1357 | if (addOverApproximatedRegion(AR: R, Context)) |
1358 | return true; |
1359 | } |
1360 | |
1361 | const SCEV *LoopCount = SE.getBackedgeTakenCount(L); |
1362 | return invalid<ReportLoopBound>(Context, /*Assert=*/true, Arguments&: L, Arguments&: LoopCount); |
1363 | } |
1364 | |
1365 | /// Return the number of loops in @p L (incl. @p L) that have a trip |
1366 | /// count that is not known to be less than @MinProfitableTrips. |
1367 | ScopDetection::LoopStats |
1368 | ScopDetection::countBeneficialSubLoops(Loop *L, ScalarEvolution &SE, |
1369 | unsigned MinProfitableTrips) { |
1370 | const SCEV *TripCount = SE.getBackedgeTakenCount(L); |
1371 | |
1372 | int NumLoops = 1; |
1373 | int MaxLoopDepth = 1; |
1374 | if (MinProfitableTrips > 0) |
1375 | if (auto *TripCountC = dyn_cast<SCEVConstant>(Val: TripCount)) |
1376 | if (TripCountC->getType()->getScalarSizeInBits() <= 64) |
1377 | if (TripCountC->getValue()->getZExtValue() <= MinProfitableTrips) |
1378 | NumLoops -= 1; |
1379 | |
1380 | for (auto &SubLoop : *L) { |
1381 | LoopStats Stats = countBeneficialSubLoops(L: SubLoop, SE, MinProfitableTrips); |
1382 | NumLoops += Stats.NumLoops; |
1383 | MaxLoopDepth = std::max(a: MaxLoopDepth, b: Stats.MaxDepth + 1); |
1384 | } |
1385 | |
1386 | return {.NumLoops: NumLoops, .MaxDepth: MaxLoopDepth}; |
1387 | } |
1388 | |
1389 | ScopDetection::LoopStats |
1390 | ScopDetection::countBeneficialLoops(Region *R, ScalarEvolution &SE, |
1391 | LoopInfo &LI, unsigned MinProfitableTrips) { |
1392 | int LoopNum = 0; |
1393 | int MaxLoopDepth = 0; |
1394 | |
1395 | auto L = LI.getLoopFor(BB: R->getEntry()); |
1396 | |
1397 | // If L is fully contained in R, move to first loop surrounding R. Otherwise, |
1398 | // L is either nullptr or already surrounding R. |
1399 | if (L && R->contains(L)) { |
1400 | L = R->outermostLoopInRegion(L); |
1401 | L = L->getParentLoop(); |
1402 | } |
1403 | |
1404 | auto SubLoops = |
1405 | L ? L->getSubLoopsVector() : std::vector<Loop *>(LI.begin(), LI.end()); |
1406 | |
1407 | for (auto &SubLoop : SubLoops) |
1408 | if (R->contains(L: SubLoop)) { |
1409 | LoopStats Stats = |
1410 | countBeneficialSubLoops(L: SubLoop, SE, MinProfitableTrips); |
1411 | LoopNum += Stats.NumLoops; |
1412 | MaxLoopDepth = std::max(a: MaxLoopDepth, b: Stats.MaxDepth); |
1413 | } |
1414 | |
1415 | return {.NumLoops: LoopNum, .MaxDepth: MaxLoopDepth}; |
1416 | } |
1417 | |
1418 | static bool isErrorBlockImpl(BasicBlock &BB, const Region &R, LoopInfo &LI, |
1419 | const DominatorTree &DT) { |
1420 | if (isa<UnreachableInst>(Val: BB.getTerminator())) |
1421 | return true; |
1422 | |
1423 | if (LI.isLoopHeader(BB: &BB)) |
1424 | return false; |
1425 | |
1426 | // Don't consider something outside the SCoP as error block. It will precede |
1427 | // the code versioning runtime check. |
1428 | if (!R.contains(BB: &BB)) |
1429 | return false; |
1430 | |
1431 | // Basic blocks that are always executed are not considered error blocks, |
1432 | // as their execution can not be a rare event. |
1433 | bool DominatesAllPredecessors = true; |
1434 | if (R.isTopLevelRegion()) { |
1435 | for (BasicBlock &I : *R.getEntry()->getParent()) { |
1436 | if (isa<ReturnInst>(Val: I.getTerminator()) && !DT.dominates(A: &BB, B: &I)) { |
1437 | DominatesAllPredecessors = false; |
1438 | break; |
1439 | } |
1440 | } |
1441 | } else { |
1442 | for (auto Pred : predecessors(BB: R.getExit())) { |
1443 | if (R.contains(BB: Pred) && !DT.dominates(A: &BB, B: Pred)) { |
1444 | DominatesAllPredecessors = false; |
1445 | break; |
1446 | } |
1447 | } |
1448 | } |
1449 | |
1450 | if (DominatesAllPredecessors) |
1451 | return false; |
1452 | |
1453 | for (Instruction &Inst : BB) |
1454 | if (CallInst *CI = dyn_cast<CallInst>(Val: &Inst)) { |
1455 | if (isDebugCall(Inst: CI)) |
1456 | continue; |
1457 | |
1458 | if (isIgnoredIntrinsic(V: CI)) |
1459 | continue; |
1460 | |
1461 | // memset, memcpy and memmove are modeled intrinsics. |
1462 | if (isa<MemSetInst>(Val: CI) || isa<MemTransferInst>(Val: CI)) |
1463 | continue; |
1464 | |
1465 | if (!CI->doesNotAccessMemory()) |
1466 | return true; |
1467 | if (CI->doesNotReturn()) |
1468 | return true; |
1469 | } |
1470 | |
1471 | return false; |
1472 | } |
1473 | |
1474 | bool ScopDetection::isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R) { |
1475 | if (!PollyAllowErrorBlocks) |
1476 | return false; |
1477 | |
1478 | auto It = ErrorBlockCache.insert(KV: {std::make_pair(x: &BB, y: &R), false}); |
1479 | if (!It.second) |
1480 | return It.first->getSecond(); |
1481 | |
1482 | bool Result = isErrorBlockImpl(BB, R, LI, DT); |
1483 | It.first->second = Result; |
1484 | return Result; |
1485 | } |
1486 | |
1487 | Region *ScopDetection::expandRegion(Region &R) { |
1488 | // Initial no valid region was found (greater than R) |
1489 | std::unique_ptr<Region> LastValidRegion; |
1490 | auto ExpandedRegion = std::unique_ptr<Region>(R.getExpandedRegion()); |
1491 | |
1492 | POLLY_DEBUG(dbgs() << "\tExpanding "<< R.getNameStr() << "\n"); |
1493 | |
1494 | while (ExpandedRegion) { |
1495 | BBPair P = getBBPairForRegion(R: ExpandedRegion.get()); |
1496 | std::unique_ptr<DetectionContext> &Entry = DetectionContextMap[P]; |
1497 | Entry = std::make_unique<DetectionContext>(args&: *ExpandedRegion, args&: AA, |
1498 | /*Verifying=*/args: false); |
1499 | DetectionContext &Context = *Entry; |
1500 | |
1501 | POLLY_DEBUG(dbgs() << "\t\tTrying "<< ExpandedRegion->getNameStr() |
1502 | << "\n"); |
1503 | // Only expand when we did not collect errors. |
1504 | |
1505 | if (!Context.Log.hasErrors()) { |
1506 | // If the exit is valid check all blocks |
1507 | // - if true, a valid region was found => store it + keep expanding |
1508 | // - if false, .tbd. => stop (should this really end the loop?) |
1509 | if (!allBlocksValid(Context) || Context.Log.hasErrors()) { |
1510 | removeCachedResults(R: *ExpandedRegion); |
1511 | DetectionContextMap.erase(Val: P); |
1512 | break; |
1513 | } |
1514 | |
1515 | // Store this region, because it is the greatest valid (encountered so |
1516 | // far). |
1517 | if (LastValidRegion) { |
1518 | removeCachedResults(R: *LastValidRegion); |
1519 | DetectionContextMap.erase(Val: P); |
1520 | } |
1521 | LastValidRegion = std::move(ExpandedRegion); |
1522 | |
1523 | // Create and test the next greater region (if any) |
1524 | ExpandedRegion = |
1525 | std::unique_ptr<Region>(LastValidRegion->getExpandedRegion()); |
1526 | |
1527 | } else { |
1528 | // Create and test the next greater region (if any) |
1529 | removeCachedResults(R: *ExpandedRegion); |
1530 | DetectionContextMap.erase(Val: P); |
1531 | ExpandedRegion = |
1532 | std::unique_ptr<Region>(ExpandedRegion->getExpandedRegion()); |
1533 | } |
1534 | } |
1535 | |
1536 | POLLY_DEBUG({ |
1537 | if (LastValidRegion) |
1538 | dbgs() << "\tto "<< LastValidRegion->getNameStr() << "\n"; |
1539 | else |
1540 | dbgs() << "\tExpanding "<< R.getNameStr() << " failed\n"; |
1541 | }); |
1542 | |
1543 | return LastValidRegion.release(); |
1544 | } |
1545 | |
1546 | static bool regionWithoutLoops(Region &R, LoopInfo &LI) { |
1547 | for (const BasicBlock *BB : R.blocks()) |
1548 | if (R.contains(L: LI.getLoopFor(BB))) |
1549 | return false; |
1550 | |
1551 | return true; |
1552 | } |
1553 | |
1554 | void ScopDetection::removeCachedResultsRecursively(const Region &R) { |
1555 | for (auto &SubRegion : R) { |
1556 | if (ValidRegions.count(key: SubRegion.get())) { |
1557 | removeCachedResults(R: *SubRegion); |
1558 | } else |
1559 | removeCachedResultsRecursively(R: *SubRegion); |
1560 | } |
1561 | } |
1562 | |
1563 | void ScopDetection::removeCachedResults(const Region &R) { |
1564 | ValidRegions.remove(X: &R); |
1565 | } |
1566 | |
1567 | void ScopDetection::findScops(Region &R) { |
1568 | std::unique_ptr<DetectionContext> &Entry = |
1569 | DetectionContextMap[getBBPairForRegion(R: &R)]; |
1570 | Entry = std::make_unique<DetectionContext>(args&: R, args&: AA, /*Verifying=*/args: false); |
1571 | DetectionContext &Context = *Entry; |
1572 | |
1573 | bool DidBailout = true; |
1574 | if (!PollyProcessUnprofitable && regionWithoutLoops(R, LI)) |
1575 | invalid<ReportUnprofitable>(Context, /*Assert=*/true, Arguments: &R); |
1576 | else |
1577 | DidBailout = !isValidRegion(Context); |
1578 | |
1579 | (void)DidBailout; |
1580 | if (KeepGoing) { |
1581 | assert((!DidBailout || Context.IsInvalid) && |
1582 | "With -polly-detect-keep-going, it is sufficient that if " |
1583 | "isValidRegion short-circuited, that SCoP is invalid"); |
1584 | } else { |
1585 | assert(DidBailout == Context.IsInvalid && |
1586 | "isValidRegion must short-circuit iff the ScoP is invalid"); |
1587 | } |
1588 | |
1589 | if (Context.IsInvalid) { |
1590 | removeCachedResults(R); |
1591 | } else { |
1592 | ValidRegions.insert(X: &R); |
1593 | return; |
1594 | } |
1595 | |
1596 | for (auto &SubRegion : R) |
1597 | findScops(R&: *SubRegion); |
1598 | |
1599 | // Try to expand regions. |
1600 | // |
1601 | // As the region tree normally only contains canonical regions, non canonical |
1602 | // regions that form a Scop are not found. Therefore, those non canonical |
1603 | // regions are checked by expanding the canonical ones. |
1604 | |
1605 | std::vector<Region *> ToExpand; |
1606 | |
1607 | for (auto &SubRegion : R) |
1608 | ToExpand.push_back(x: SubRegion.get()); |
1609 | |
1610 | for (Region *CurrentRegion : ToExpand) { |
1611 | // Skip invalid regions. Regions may become invalid, if they are element of |
1612 | // an already expanded region. |
1613 | if (!ValidRegions.count(key: CurrentRegion)) |
1614 | continue; |
1615 | |
1616 | // Skip regions that had errors. |
1617 | bool HadErrors = lookupRejectionLog(R: CurrentRegion)->hasErrors(); |
1618 | if (HadErrors) |
1619 | continue; |
1620 | |
1621 | Region *ExpandedR = expandRegion(R&: *CurrentRegion); |
1622 | |
1623 | if (!ExpandedR) |
1624 | continue; |
1625 | |
1626 | R.addSubRegion(SubRegion: ExpandedR, moveChildren: true); |
1627 | ValidRegions.insert(X: ExpandedR); |
1628 | removeCachedResults(R: *CurrentRegion); |
1629 | removeCachedResultsRecursively(R: *ExpandedR); |
1630 | } |
1631 | } |
1632 | |
1633 | bool ScopDetection::allBlocksValid(DetectionContext &Context) { |
1634 | Region &CurRegion = Context.CurRegion; |
1635 | |
1636 | for (const BasicBlock *BB : CurRegion.blocks()) { |
1637 | Loop *L = LI.getLoopFor(BB); |
1638 | if (L && L->getHeader() == BB) { |
1639 | if (CurRegion.contains(L)) { |
1640 | if (!isValidLoop(L, Context)) { |
1641 | Context.IsInvalid = true; |
1642 | if (!KeepGoing) |
1643 | return false; |
1644 | } |
1645 | } else { |
1646 | SmallVector<BasicBlock *, 1> Latches; |
1647 | L->getLoopLatches(LoopLatches&: Latches); |
1648 | for (BasicBlock *Latch : Latches) |
1649 | if (CurRegion.contains(BB: Latch)) |
1650 | return invalid<ReportLoopOnlySomeLatches>(Context, /*Assert=*/true, |
1651 | Arguments&: L); |
1652 | } |
1653 | } |
1654 | } |
1655 | |
1656 | for (BasicBlock *BB : CurRegion.blocks()) { |
1657 | bool IsErrorBlock = isErrorBlock(BB&: *BB, R: CurRegion); |
1658 | |
1659 | // Also check exception blocks (and possibly register them as non-affine |
1660 | // regions). Even though exception blocks are not modeled, we use them |
1661 | // to forward-propagate domain constraints during ScopInfo construction. |
1662 | if (!isValidCFG(BB&: *BB, IsLoopBranch: false, AllowUnreachable: IsErrorBlock, Context) && !KeepGoing) |
1663 | return false; |
1664 | |
1665 | if (IsErrorBlock) |
1666 | continue; |
1667 | |
1668 | for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I) |
1669 | if (!isValidInstruction(Inst&: *I, Context)) { |
1670 | Context.IsInvalid = true; |
1671 | if (!KeepGoing) |
1672 | return false; |
1673 | } |
1674 | } |
1675 | |
1676 | if (!hasAffineMemoryAccesses(Context)) |
1677 | return false; |
1678 | |
1679 | return true; |
1680 | } |
1681 | |
1682 | bool ScopDetection::hasSufficientCompute(DetectionContext &Context, |
1683 | int NumLoops) const { |
1684 | int InstCount = 0; |
1685 | |
1686 | if (NumLoops == 0) |
1687 | return false; |
1688 | |
1689 | for (auto *BB : Context.CurRegion.blocks()) |
1690 | if (Context.CurRegion.contains(L: LI.getLoopFor(BB))) |
1691 | InstCount += BB->size(); |
1692 | |
1693 | InstCount = InstCount / NumLoops; |
1694 | |
1695 | return InstCount >= ProfitabilityMinPerLoopInstructions; |
1696 | } |
1697 | |
1698 | bool ScopDetection::hasPossiblyDistributableLoop( |
1699 | DetectionContext &Context) const { |
1700 | for (auto *BB : Context.CurRegion.blocks()) { |
1701 | auto *L = LI.getLoopFor(BB); |
1702 | if (!L) |
1703 | continue; |
1704 | if (!Context.CurRegion.contains(L)) |
1705 | continue; |
1706 | if (Context.BoxedLoopsSet.count(key: L)) |
1707 | continue; |
1708 | unsigned StmtsWithStoresInLoops = 0; |
1709 | for (auto *LBB : L->blocks()) { |
1710 | bool MemStore = false; |
1711 | for (auto &I : *LBB) |
1712 | MemStore |= isa<StoreInst>(Val: &I); |
1713 | StmtsWithStoresInLoops += MemStore; |
1714 | } |
1715 | return (StmtsWithStoresInLoops > 1); |
1716 | } |
1717 | return false; |
1718 | } |
1719 | |
1720 | bool ScopDetection::isProfitableRegion(DetectionContext &Context) const { |
1721 | Region &CurRegion = Context.CurRegion; |
1722 | |
1723 | if (PollyProcessUnprofitable) |
1724 | return true; |
1725 | |
1726 | // We can probably not do a lot on scops that only write or only read |
1727 | // data. |
1728 | if (!Context.hasStores || !Context.hasLoads) |
1729 | return invalid<ReportUnprofitable>(Context, /*Assert=*/true, Arguments: &CurRegion); |
1730 | |
1731 | int NumLoops = |
1732 | countBeneficialLoops(R: &CurRegion, SE, LI, MinProfitableTrips: MIN_LOOP_TRIP_COUNT).NumLoops; |
1733 | int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size(); |
1734 | |
1735 | // Scops with at least two loops may allow either loop fusion or tiling and |
1736 | // are consequently interesting to look at. |
1737 | if (NumAffineLoops >= 2) |
1738 | return true; |
1739 | |
1740 | // A loop with multiple non-trivial blocks might be amendable to distribution. |
1741 | if (NumAffineLoops == 1 && hasPossiblyDistributableLoop(Context)) |
1742 | return true; |
1743 | |
1744 | // Scops that contain a loop with a non-trivial amount of computation per |
1745 | // loop-iteration are interesting as we may be able to parallelize such |
1746 | // loops. Individual loops that have only a small amount of computation |
1747 | // per-iteration are performance-wise very fragile as any change to the |
1748 | // loop induction variables may affect performance. To not cause spurious |
1749 | // performance regressions, we do not consider such loops. |
1750 | if (NumAffineLoops == 1 && hasSufficientCompute(Context, NumLoops)) |
1751 | return true; |
1752 | |
1753 | return invalid<ReportUnprofitable>(Context, /*Assert=*/true, Arguments: &CurRegion); |
1754 | } |
1755 | |
1756 | bool ScopDetection::isValidRegion(DetectionContext &Context) { |
1757 | Region &CurRegion = Context.CurRegion; |
1758 | |
1759 | POLLY_DEBUG(dbgs() << "Checking region: "<< CurRegion.getNameStr() |
1760 | << "\n\t"); |
1761 | |
1762 | if (!PollyAllowFullFunction && CurRegion.isTopLevelRegion()) { |
1763 | POLLY_DEBUG(dbgs() << "Top level region is invalid\n"); |
1764 | Context.IsInvalid = true; |
1765 | return false; |
1766 | } |
1767 | |
1768 | DebugLoc DbgLoc; |
1769 | if (CurRegion.getExit() && |
1770 | isa<UnreachableInst>(Val: CurRegion.getExit()->getTerminator())) { |
1771 | POLLY_DEBUG(dbgs() << "Unreachable in exit\n"); |
1772 | return invalid<ReportUnreachableInExit>(Context, /*Assert=*/true, |
1773 | Arguments: CurRegion.getExit(), Arguments&: DbgLoc); |
1774 | } |
1775 | |
1776 | if (!OnlyRegion.empty() && |
1777 | !CurRegion.getEntry()->getName().count(Str: OnlyRegion)) { |
1778 | POLLY_DEBUG({ |
1779 | dbgs() << "Region entry does not match -polly-only-region"; |
1780 | dbgs() << "\n"; |
1781 | }); |
1782 | Context.IsInvalid = true; |
1783 | return false; |
1784 | } |
1785 | |
1786 | for (BasicBlock *Pred : predecessors(BB: CurRegion.getEntry())) { |
1787 | Instruction *PredTerm = Pred->getTerminator(); |
1788 | if (isa<IndirectBrInst>(Val: PredTerm) || isa<CallBrInst>(Val: PredTerm)) |
1789 | return invalid<ReportIndirectPredecessor>( |
1790 | Context, /*Assert=*/true, Arguments&: PredTerm, Arguments: PredTerm->getDebugLoc()); |
1791 | } |
1792 | |
1793 | // SCoP cannot contain the entry block of the function, because we need |
1794 | // to insert alloca instruction there when translate scalar to array. |
1795 | if (!PollyAllowFullFunction && |
1796 | CurRegion.getEntry() == |
1797 | &(CurRegion.getEntry()->getParent()->getEntryBlock())) |
1798 | return invalid<ReportEntry>(Context, /*Assert=*/true, Arguments: CurRegion.getEntry()); |
1799 | |
1800 | if (!allBlocksValid(Context)) { |
1801 | // TODO: Every failure condition within allBlocksValid should call |
1802 | // invalid<Reason>(). Otherwise we reject SCoPs without giving feedback to |
1803 | // the user. |
1804 | Context.IsInvalid = true; |
1805 | return false; |
1806 | } |
1807 | |
1808 | if (!isReducibleRegion(R&: CurRegion, DbgLoc)) |
1809 | return invalid<ReportIrreducibleRegion>(Context, /*Assert=*/true, |
1810 | Arguments: &CurRegion, Arguments&: DbgLoc); |
1811 | |
1812 | POLLY_DEBUG(dbgs() << "OK\n"); |
1813 | return true; |
1814 | } |
1815 | |
1816 | void ScopDetection::markFunctionAsInvalid(Function *F) { |
1817 | F->addFnAttr(Kind: PollySkipFnAttr); |
1818 | } |
1819 | |
1820 | bool ScopDetection::isValidFunction(Function &F) { |
1821 | return !F.hasFnAttribute(Kind: PollySkipFnAttr); |
1822 | } |
1823 | |
1824 | void ScopDetection::printLocations(Function &F) { |
1825 | for (const Region *R : *this) { |
1826 | unsigned LineEntry, LineExit; |
1827 | std::string FileName; |
1828 | |
1829 | getDebugLocation(R, LineBegin&: LineEntry, LineEnd&: LineExit, FileName); |
1830 | DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit); |
1831 | F.getContext().diagnose(DI: Diagnostic); |
1832 | } |
1833 | } |
1834 | |
1835 | void ScopDetection::emitMissedRemarks(const Function &F) { |
1836 | for (auto &DIt : DetectionContextMap) { |
1837 | DetectionContext &DC = *DIt.getSecond(); |
1838 | if (DC.Log.hasErrors()) |
1839 | emitRejectionRemarks(P: DIt.getFirst(), Log: DC.Log, ORE); |
1840 | } |
1841 | } |
1842 | |
1843 | bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const { |
1844 | /// Enum for coloring BBs in Region. |
1845 | /// |
1846 | /// WHITE - Unvisited BB in DFS walk. |
1847 | /// GREY - BBs which are currently on the DFS stack for processing. |
1848 | /// BLACK - Visited and completely processed BB. |
1849 | enum Color { WHITE, GREY, BLACK }; |
1850 | |
1851 | BasicBlock *REntry = R.getEntry(); |
1852 | BasicBlock *RExit = R.getExit(); |
1853 | // Map to match the color of a BasicBlock during the DFS walk. |
1854 | DenseMap<const BasicBlock *, Color> BBColorMap; |
1855 | // Stack keeping track of current BB and index of next child to be processed. |
1856 | std::stack<std::pair<BasicBlock *, unsigned>> DFSStack; |
1857 | |
1858 | unsigned AdjacentBlockIndex = 0; |
1859 | BasicBlock *CurrBB, *SuccBB; |
1860 | CurrBB = REntry; |
1861 | |
1862 | // Initialize the map for all BB with WHITE color. |
1863 | for (auto *BB : R.blocks()) |
1864 | BBColorMap[BB] = WHITE; |
1865 | |
1866 | // Process the entry block of the Region. |
1867 | BBColorMap[CurrBB] = GREY; |
1868 | DFSStack.push(x: std::make_pair(x&: CurrBB, y: 0)); |
1869 | |
1870 | while (!DFSStack.empty()) { |
1871 | // Get next BB on stack to be processed. |
1872 | CurrBB = DFSStack.top().first; |
1873 | AdjacentBlockIndex = DFSStack.top().second; |
1874 | DFSStack.pop(); |
1875 | |
1876 | // Loop to iterate over the successors of current BB. |
1877 | const Instruction *TInst = CurrBB->getTerminator(); |
1878 | unsigned NSucc = TInst->getNumSuccessors(); |
1879 | for (unsigned I = AdjacentBlockIndex; I < NSucc; |
1880 | ++I, ++AdjacentBlockIndex) { |
1881 | SuccBB = TInst->getSuccessor(Idx: I); |
1882 | |
1883 | // Checks for region exit block and self-loops in BB. |
1884 | if (SuccBB == RExit || SuccBB == CurrBB) |
1885 | continue; |
1886 | |
1887 | // WHITE indicates an unvisited BB in DFS walk. |
1888 | if (BBColorMap[SuccBB] == WHITE) { |
1889 | // Push the current BB and the index of the next child to be visited. |
1890 | DFSStack.push(x: std::make_pair(x&: CurrBB, y: I + 1)); |
1891 | // Push the next BB to be processed. |
1892 | DFSStack.push(x: std::make_pair(x&: SuccBB, y: 0)); |
1893 | // First time the BB is being processed. |
1894 | BBColorMap[SuccBB] = GREY; |
1895 | break; |
1896 | } else if (BBColorMap[SuccBB] == GREY) { |
1897 | // GREY indicates a loop in the control flow. |
1898 | // If the destination dominates the source, it is a natural loop |
1899 | // else, an irreducible control flow in the region is detected. |
1900 | if (!DT.dominates(A: SuccBB, B: CurrBB)) { |
1901 | // Get debug info of instruction which causes irregular control flow. |
1902 | DbgLoc = TInst->getDebugLoc(); |
1903 | return false; |
1904 | } |
1905 | } |
1906 | } |
1907 | |
1908 | // If all children of current BB have been processed, |
1909 | // then mark that BB as fully processed. |
1910 | if (AdjacentBlockIndex == NSucc) |
1911 | BBColorMap[CurrBB] = BLACK; |
1912 | } |
1913 | |
1914 | return true; |
1915 | } |
1916 | |
1917 | static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, |
1918 | bool OnlyProfitable) { |
1919 | if (!OnlyProfitable) { |
1920 | NumLoopsInScop += Stats.NumLoops; |
1921 | MaxNumLoopsInScop = |
1922 | std::max(a: MaxNumLoopsInScop.getValue(), b: (uint64_t)Stats.NumLoops); |
1923 | if (Stats.MaxDepth == 0) |
1924 | NumScopsDepthZero++; |
1925 | else if (Stats.MaxDepth == 1) |
1926 | NumScopsDepthOne++; |
1927 | else if (Stats.MaxDepth == 2) |
1928 | NumScopsDepthTwo++; |
1929 | else if (Stats.MaxDepth == 3) |
1930 | NumScopsDepthThree++; |
1931 | else if (Stats.MaxDepth == 4) |
1932 | NumScopsDepthFour++; |
1933 | else if (Stats.MaxDepth == 5) |
1934 | NumScopsDepthFive++; |
1935 | else |
1936 | NumScopsDepthLarger++; |
1937 | } else { |
1938 | NumLoopsInProfScop += Stats.NumLoops; |
1939 | MaxNumLoopsInProfScop = |
1940 | std::max(a: MaxNumLoopsInProfScop.getValue(), b: (uint64_t)Stats.NumLoops); |
1941 | if (Stats.MaxDepth == 0) |
1942 | NumProfScopsDepthZero++; |
1943 | else if (Stats.MaxDepth == 1) |
1944 | NumProfScopsDepthOne++; |
1945 | else if (Stats.MaxDepth == 2) |
1946 | NumProfScopsDepthTwo++; |
1947 | else if (Stats.MaxDepth == 3) |
1948 | NumProfScopsDepthThree++; |
1949 | else if (Stats.MaxDepth == 4) |
1950 | NumProfScopsDepthFour++; |
1951 | else if (Stats.MaxDepth == 5) |
1952 | NumProfScopsDepthFive++; |
1953 | else |
1954 | NumProfScopsDepthLarger++; |
1955 | } |
1956 | } |
1957 | |
1958 | ScopDetection::DetectionContext * |
1959 | ScopDetection::getDetectionContext(const Region *R) const { |
1960 | auto DCMIt = DetectionContextMap.find(Val: getBBPairForRegion(R)); |
1961 | if (DCMIt == DetectionContextMap.end()) |
1962 | return nullptr; |
1963 | return DCMIt->second.get(); |
1964 | } |
1965 | |
1966 | const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const { |
1967 | const DetectionContext *DC = getDetectionContext(R); |
1968 | return DC ? &DC->Log : nullptr; |
1969 | } |
1970 | |
1971 | void ScopDetection::verifyRegion(const Region &R) { |
1972 | assert(isMaxRegionInScop(R) && "Expect R is a valid region."); |
1973 | |
1974 | DetectionContext Context(const_cast<Region &>(R), AA, true /*verifying*/); |
1975 | isValidRegion(Context); |
1976 | } |
1977 | |
1978 | void ScopDetection::verifyAnalysis() { |
1979 | if (!VerifyScops) |
1980 | return; |
1981 | |
1982 | for (const Region *R : ValidRegions) |
1983 | verifyRegion(R: *R); |
1984 | } |
1985 | |
1986 | bool ScopDetectionWrapperPass::runOnFunction(Function &F) { |
1987 | auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
1988 | auto &RI = getAnalysis<RegionInfoPass>().getRegionInfo(); |
1989 | auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults(); |
1990 | auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
1991 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
1992 | auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); |
1993 | |
1994 | Result = std::make_unique<ScopDetection>(args&: DT, args&: SE, args&: LI, args&: RI, args&: AA, args&: ORE); |
1995 | Result->detect(F); |
1996 | return false; |
1997 | } |
1998 | |
1999 | void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { |
2000 | AU.addRequired<LoopInfoWrapperPass>(); |
2001 | AU.addRequiredTransitive<ScalarEvolutionWrapperPass>(); |
2002 | AU.addRequired<DominatorTreeWrapperPass>(); |
2003 | AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); |
2004 | // We also need AA and RegionInfo when we are verifying analysis. |
2005 | AU.addRequiredTransitive<AAResultsWrapperPass>(); |
2006 | AU.addRequiredTransitive<RegionInfoPass>(); |
2007 | AU.setPreservesAll(); |
2008 | } |
2009 | |
2010 | void ScopDetectionWrapperPass::print(raw_ostream &OS, const Module *) const { |
2011 | for (const Region *R : Result->ValidRegions) |
2012 | OS << "Valid Region for Scop: "<< R->getNameStr() << '\n'; |
2013 | |
2014 | OS << "\n"; |
2015 | } |
2016 | |
2017 | ScopDetectionWrapperPass::ScopDetectionWrapperPass() : FunctionPass(ID) { |
2018 | // Disable runtime alias checks if we ignore aliasing all together. |
2019 | if (IgnoreAliasing) |
2020 | PollyUseRuntimeAliasChecks = false; |
2021 | } |
2022 | |
2023 | ScopAnalysis::ScopAnalysis() { |
2024 | // Disable runtime alias checks if we ignore aliasing all together. |
2025 | if (IgnoreAliasing) |
2026 | PollyUseRuntimeAliasChecks = false; |
2027 | } |
2028 | |
2029 | void ScopDetectionWrapperPass::releaseMemory() { Result.reset(); } |
2030 | |
2031 | char ScopDetectionWrapperPass::ID; |
2032 | |
2033 | AnalysisKey ScopAnalysis::Key; |
2034 | |
2035 | ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { |
2036 | auto &LI = FAM.getResult<LoopAnalysis>(IR&: F); |
2037 | auto &RI = FAM.getResult<RegionInfoAnalysis>(IR&: F); |
2038 | auto &AA = FAM.getResult<AAManager>(IR&: F); |
2039 | auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(IR&: F); |
2040 | auto &DT = FAM.getResult<DominatorTreeAnalysis>(IR&: F); |
2041 | auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F); |
2042 | |
2043 | ScopDetection Result(DT, SE, LI, RI, AA, ORE); |
2044 | Result.detect(F); |
2045 | return Result; |
2046 | } |
2047 | |
2048 | PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F, |
2049 | FunctionAnalysisManager &FAM) { |
2050 | OS << "Detected Scops in Function "<< F.getName() << "\n"; |
2051 | auto &SD = FAM.getResult<ScopAnalysis>(IR&: F); |
2052 | for (const Region *R : SD.ValidRegions) |
2053 | OS << "Valid Region for Scop: "<< R->getNameStr() << '\n'; |
2054 | |
2055 | OS << "\n"; |
2056 | return PreservedAnalyses::all(); |
2057 | } |
2058 | |
2059 | Pass *polly::createScopDetectionWrapperPassPass() { |
2060 | return new ScopDetectionWrapperPass(); |
2061 | } |
2062 | |
2063 | INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect", |
2064 | "Polly - Detect static control parts (SCoPs)", false, |
2065 | false); |
2066 | INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); |
2067 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); |
2068 | INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); |
2069 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); |
2070 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); |
2071 | INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass); |
2072 | INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect", |
2073 | "Polly - Detect static control parts (SCoPs)", false, false) |
2074 | |
2075 | //===----------------------------------------------------------------------===// |
2076 | |
2077 | namespace { |
2078 | /// Print result from ScopDetectionWrapperPass. |
2079 | class ScopDetectionPrinterLegacyPass final : public FunctionPass { |
2080 | public: |
2081 | static char ID; |
2082 | |
2083 | ScopDetectionPrinterLegacyPass() : ScopDetectionPrinterLegacyPass(outs()) {} |
2084 | |
2085 | explicit ScopDetectionPrinterLegacyPass(llvm::raw_ostream &OS) |
2086 | : FunctionPass(ID), OS(OS) {} |
2087 | |
2088 | bool runOnFunction(Function &F) override { |
2089 | ScopDetectionWrapperPass &P = getAnalysis<ScopDetectionWrapperPass>(); |
2090 | |
2091 | OS << "Printing analysis '"<< P.getPassName() << "' for function '" |
2092 | << F.getName() << "':\n"; |
2093 | P.print(OS); |
2094 | |
2095 | return false; |
2096 | } |
2097 | |
2098 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
2099 | FunctionPass::getAnalysisUsage(AU); |
2100 | AU.addRequired<ScopDetectionWrapperPass>(); |
2101 | AU.setPreservesAll(); |
2102 | } |
2103 | |
2104 | private: |
2105 | llvm::raw_ostream &OS; |
2106 | }; |
2107 | |
2108 | char ScopDetectionPrinterLegacyPass::ID = 0; |
2109 | } // namespace |
2110 | |
2111 | Pass *polly::createScopDetectionPrinterLegacyPass(raw_ostream &OS) { |
2112 | return new ScopDetectionPrinterLegacyPass(OS); |
2113 | } |
2114 | |
2115 | INITIALIZE_PASS_BEGIN(ScopDetectionPrinterLegacyPass, "polly-print-detect", |
2116 | "Polly - Print static control parts (SCoPs)", false, |
2117 | false); |
2118 | INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); |
2119 | INITIALIZE_PASS_END(ScopDetectionPrinterLegacyPass, "polly-print-detect", |
2120 | "Polly - Print static control parts (SCoPs)", false, false) |
2121 |
Definitions
- ProfitabilityMinPerLoopInstructions
- PollyProcessUnprofitable
- XPollyProcessUnprofitable
- OnlyFunctions
- IgnoredFunctions
- PollyAllowFullFunction
- XAllowFullFunction
- OnlyRegion
- IgnoreAliasing
- PollyAllowUnsignedOperations
- XPollyAllowUnsignedOperations
- PollyUseRuntimeAliasChecks
- XPollyUseRuntimeAliasChecks
- ReportLevel
- AllowDifferentTypes
- AllowNonAffine
- AllowModrefCall
- AllowNonAffineSubRegions
- AllowNonAffineSubLoops
- TrackFailures
- KeepGoing
- PollyDelinearizeX
- VerifyScops
- PollyInvariantLoadHoisting
- XPollyInvariantLoadHoisting
- PollyAllowErrorBlocks
- MIN_LOOP_TRIP_COUNT
- PollyTrackFailures
- PollyDelinearize
- PollySkipFnAttr
- NumScopRegions
- NumLoopsInScop
- NumScopsDepthZero
- NumScopsDepthOne
- NumScopsDepthTwo
- NumScopsDepthThree
- NumScopsDepthFour
- NumScopsDepthFive
- NumScopsDepthLarger
- NumProfScopRegions
- NumLoopsInProfScop
- NumLoopsOverall
- NumProfScopsDepthZero
- NumProfScopsDepthOne
- NumProfScopsDepthTwo
- NumProfScopsDepthThree
- NumProfScopsDepthFour
- NumProfScopsDepthFive
- NumProfScopsDepthLarger
- MaxNumLoopsInScop
- MaxNumLoopsInProfScop
- DiagnosticScopFound
- DiagnosticScopFound
- classof
- PluginDiagnosticKind
- doesStringMatchAnyRegex
- ScopDetection
- detect
- invalid
- isMaxRegionInScop
- regionIsInvalidBecause
- addOverApproximatedRegion
- onlyValidRequiredInvariantLoads
- involvesMultiplePtrs
- isAffine
- isValidSwitch
- isValidBranch
- isValidCFG
- isValidCallInst
- isValidIntrinsicInst
- isInvariant
- SCEVRemoveMax
- SCEVRemoveMax
- rewrite
- visitSMaxExpr
- getDelinearizationTerms
- hasValidArraySizes
- computeAccessFunctions
- hasBaseAffineAccesses
- hasAffineMemoryAccesses
- isValidAccess
- isValidMemoryAccess
- isValidInstruction
- hasExitingBlocks
- canUseISLTripCount
- isValidLoop
- countBeneficialSubLoops
- countBeneficialLoops
- isErrorBlockImpl
- isErrorBlock
- expandRegion
- regionWithoutLoops
- removeCachedResultsRecursively
- removeCachedResults
- findScops
- allBlocksValid
- hasSufficientCompute
- hasPossiblyDistributableLoop
- isProfitableRegion
- isValidRegion
- markFunctionAsInvalid
- isValidFunction
- printLocations
- emitMissedRemarks
- isReducibleRegion
- updateLoopCountStatistic
- getDetectionContext
- lookupRejectionLog
- verifyRegion
- verifyAnalysis
- runOnFunction
- getAnalysisUsage
- ScopDetectionWrapperPass
- ScopAnalysis
- releaseMemory
- ID
- Key
- run
- run
- createScopDetectionWrapperPassPass
- ScopDetectionPrinterLegacyPass
- ScopDetectionPrinterLegacyPass
- ScopDetectionPrinterLegacyPass
- runOnFunction
- getAnalysisUsage
- ID
Improve your Profiling and Debugging skills
Find out more