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