blob: 7eb20a930a597b10106d9e9809568ed0df9f7eea [file] [log] [blame]
Tobias Grosser75805372011-04-29 06:27:02 +00001//===----- ScopDetection.cpp - Detect Scops --------------------*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Detect the maximal Scops of a function.
11//
12// A static control part (Scop) is a subgraph of the control flow graph (CFG)
13// that only has statically known control flow and can therefore be described
14// within the polyhedral model.
15//
16// Every Scop fullfills these restrictions:
17//
18// * It is a single entry single exit region
19//
20// * Only affine linear bounds in the loops
21//
22// Every natural loop in a Scop must have a number of loop iterations that can
23// be described as an affine linear function in surrounding loop iterators or
24// parameters. (A parameter is a scalar that does not change its value during
25// execution of the Scop).
26//
27// * Only comparisons of affine linear expressions in conditions
28//
29// * All loops and conditions perfectly nested
30//
31// The control flow needs to be structured such that it could be written using
32// just 'for' and 'if' statements, without the need for any 'goto', 'break' or
33// 'continue'.
34//
35// * Side effect free functions call
36//
37// Only function calls and intrinsics that do not have side effects are allowed
38// (readnone).
39//
40// The Scop detection finds the largest Scops by checking if the largest
41// region is a Scop. If this is not the case, its canonical subregions are
42// checked until a region is a Scop. It is now tried to extend this Scop by
43// creating a larger non canonical region.
44//
45//===----------------------------------------------------------------------===//
46
Tobias Grosserecfe21b2013-03-20 18:03:18 +000047#include "polly/CodeGen/BlockGenerators.h"
Tobias Grosser75805372011-04-29 06:27:02 +000048#include "polly/LinkAllPasses.h"
Tobias Grosser637bd632013-05-07 07:31:10 +000049#include "polly/Options.h"
Andreas Simbuerger01a37a02014-04-02 11:54:01 +000050#include "polly/ScopDetectionDiagnostic.h"
Tobias Grosserecfe21b2013-03-20 18:03:18 +000051#include "polly/ScopDetection.h"
Tobias Grosser120db6b2011-11-07 12:58:54 +000052#include "polly/Support/SCEVValidator.h"
Tobias Grosser83628182013-05-07 08:11:54 +000053#include "polly/Support/ScopHelper.h"
Johannes Doerfertb164c792014-09-18 11:17:17 +000054#include "polly/CodeGen/CodeGeneration.h"
Tobias Grosser75805372011-04-29 06:27:02 +000055#include "llvm/ADT/Statistic.h"
56#include "llvm/Analysis/AliasAnalysis.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000057#include "llvm/Analysis/LoopInfo.h"
Matt Arsenault8ca36812014-07-19 18:40:17 +000058#include "llvm/Analysis/PostDominators.h"
Tobias Grosser75805372011-04-29 06:27:02 +000059#include "llvm/Analysis/RegionIterator.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000060#include "llvm/Analysis/ScalarEvolution.h"
Tobias Grosserb8710b52011-11-10 12:44:50 +000061#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chandler Carruth6b96c242014-03-06 00:47:27 +000062#include "llvm/IR/DebugInfo.h"
Johannes Doerfert3f500fa2015-01-25 18:07:30 +000063#include "llvm/IR/IntrinsicInst.h"
Tobias Grosser8519f892013-12-18 10:49:53 +000064#include "llvm/IR/DiagnosticInfo.h"
65#include "llvm/IR/DiagnosticPrinter.h"
Chandler Carruth6b96c242014-03-06 00:47:27 +000066#include "llvm/IR/LLVMContext.h"
Tobias Grosser75805372011-04-29 06:27:02 +000067#include "llvm/Support/Debug.h"
Tobias Grosser60b54f12011-11-08 15:41:28 +000068#include <set>
69
Tobias Grosser75805372011-04-29 06:27:02 +000070using namespace llvm;
71using namespace polly;
72
Chandler Carruth95fef942014-04-22 03:30:19 +000073#define DEBUG_TYPE "polly-detect"
74
Sebastian Pop8fe6d112013-05-30 17:47:32 +000075static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +000076 DetectScopsWithoutLoops("polly-detect-scops-in-functions-without-loops",
77 cl::desc("Detect scops in functions without loops"),
78 cl::Hidden, cl::init(false), cl::ZeroOrMore,
79 cl::cat(PollyCategory));
Sebastian Pop8fe6d112013-05-30 17:47:32 +000080
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +000081static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +000082 DetectRegionsWithoutLoops("polly-detect-scops-in-regions-without-loops",
83 cl::desc("Detect scops in regions without loops"),
84 cl::Hidden, cl::init(false), cl::ZeroOrMore,
85 cl::cat(PollyCategory));
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +000086
Tobias Grosser483a90d2014-07-09 10:50:10 +000087static cl::opt<std::string> OnlyFunction(
88 "polly-only-func",
89 cl::desc("Only run on functions that contain a certain string"),
90 cl::value_desc("string"), cl::ValueRequired, cl::init(""),
91 cl::cat(PollyCategory));
Tobias Grosser2ff87232011-10-23 11:17:06 +000092
Tobias Grosser483a90d2014-07-09 10:50:10 +000093static cl::opt<std::string> OnlyRegion(
94 "polly-only-region",
95 cl::desc("Only run on certain regions (The provided identifier must "
96 "appear in the name of the region's entry block"),
97 cl::value_desc("identifier"), cl::ValueRequired, cl::init(""),
98 cl::cat(PollyCategory));
Tobias Grosser4449e522014-01-27 14:24:53 +000099
Tobias Grosser60cd9322011-11-10 12:47:26 +0000100static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000101 IgnoreAliasing("polly-ignore-aliasing",
102 cl::desc("Ignore possible aliasing of the array bases"),
103 cl::Hidden, cl::init(false), cl::ZeroOrMore,
104 cl::cat(PollyCategory));
Tobias Grosser2ff87232011-10-23 11:17:06 +0000105
Johannes Doerfertb164c792014-09-18 11:17:17 +0000106bool polly::PollyUseRuntimeAliasChecks;
107static cl::opt<bool, true> XPollyUseRuntimeAliasChecks(
108 "polly-use-runtime-alias-checks",
109 cl::desc("Use runtime alias checks to resolve possible aliasing."),
110 cl::location(PollyUseRuntimeAliasChecks), cl::Hidden, cl::ZeroOrMore,
111 cl::init(true), cl::cat(PollyCategory));
112
Tobias Grosser637bd632013-05-07 07:31:10 +0000113static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000114 ReportLevel("polly-report",
115 cl::desc("Print information about the activities of Polly"),
116 cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
Tobias Grosser531891e2012-11-01 16:45:20 +0000117
118static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000119 AllowNonAffine("polly-allow-nonaffine",
120 cl::desc("Allow non affine access functions in arrays"),
121 cl::Hidden, cl::init(false), cl::ZeroOrMore,
122 cl::cat(PollyCategory));
Tobias Grossera1879642011-12-20 10:43:14 +0000123
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000124static cl::opt<bool> AllowUnsigned("polly-allow-unsigned",
125 cl::desc("Allow unsigned expressions"),
126 cl::Hidden, cl::init(false), cl::ZeroOrMore,
127 cl::cat(PollyCategory));
128
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000129static cl::opt<bool, true>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000130 TrackFailures("polly-detect-track-failures",
131 cl::desc("Track failure strings in detecting scop regions"),
132 cl::location(PollyTrackFailures), cl::Hidden, cl::ZeroOrMore,
Andreas Simbuerger3efe40b2014-08-17 10:09:03 +0000133 cl::init(true), cl::cat(PollyCategory));
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000134
Andreas Simbuerger04472402014-05-24 09:25:10 +0000135static cl::opt<bool> KeepGoing("polly-detect-keep-going",
136 cl::desc("Do not fail on the first error."),
137 cl::Hidden, cl::ZeroOrMore, cl::init(false),
138 cl::cat(PollyCategory));
139
Sebastian Pop18016682014-04-08 21:20:44 +0000140static cl::opt<bool, true>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000141 PollyDelinearizeX("polly-delinearize",
142 cl::desc("Delinearize array access functions"),
143 cl::location(PollyDelinearize), cl::Hidden,
144 cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory));
Sebastian Pop18016682014-04-08 21:20:44 +0000145
Tobias Grossera1689932014-02-18 18:49:49 +0000146static cl::opt<bool>
Tobias Grosser483a90d2014-07-09 10:50:10 +0000147 VerifyScops("polly-detect-verify",
148 cl::desc("Verify the detected SCoPs after each transformation"),
149 cl::Hidden, cl::init(false), cl::ZeroOrMore,
150 cl::cat(PollyCategory));
Tobias Grossera1689932014-02-18 18:49:49 +0000151
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000152bool polly::PollyTrackFailures = false;
Sebastian Pop18016682014-04-08 21:20:44 +0000153bool polly::PollyDelinearize = false;
Johannes Doerfert43e1ead2014-07-15 21:06:48 +0000154StringRef polly::PollySkipFnAttr = "polly.skip.fn";
Tobias Grosserc7d3fc52013-07-25 03:02:29 +0000155
Tobias Grosser75805372011-04-29 06:27:02 +0000156//===----------------------------------------------------------------------===//
157// Statistics.
158
159STATISTIC(ValidRegion, "Number of regions that a valid part of Scop");
160
Tobias Grosser8519f892013-12-18 10:49:53 +0000161class DiagnosticScopFound : public DiagnosticInfo {
162private:
163 static int PluginDiagnosticKind;
164
165 Function &F;
166 std::string FileName;
167 unsigned EntryLine, ExitLine;
168
169public:
Tobias Grosser1b12f462013-12-18 11:14:36 +0000170 DiagnosticScopFound(Function &F, std::string FileName, unsigned EntryLine,
171 unsigned ExitLine)
Tobias Grosser8519f892013-12-18 10:49:53 +0000172 : DiagnosticInfo(PluginDiagnosticKind, DS_Note), F(F), FileName(FileName),
Tobias Grosser1b12f462013-12-18 11:14:36 +0000173 EntryLine(EntryLine), ExitLine(ExitLine) {}
Tobias Grosser8519f892013-12-18 10:49:53 +0000174
175 virtual void print(DiagnosticPrinter &DP) const;
176
177 static bool classof(const DiagnosticInfo *DI) {
178 return DI->getKind() == PluginDiagnosticKind;
179 }
180};
181
182int DiagnosticScopFound::PluginDiagnosticKind = 10;
183
Tobias Grosser8519f892013-12-18 10:49:53 +0000184void DiagnosticScopFound::print(DiagnosticPrinter &DP) const {
Tobias Grosser1b12f462013-12-18 11:14:36 +0000185 DP << "Polly detected an optimizable loop region (scop) in function '" << F
186 << "'\n";
Tobias Grosser8519f892013-12-18 10:49:53 +0000187
188 if (FileName.empty()) {
189 DP << "Scop location is unknown. Compile with debug info "
190 "(-g) to get more precise information. ";
Tobias Grosser1b12f462013-12-18 11:14:36 +0000191 return;
Tobias Grosser8519f892013-12-18 10:49:53 +0000192 }
193
194 DP << FileName << ":" << EntryLine << ": Start of scop\n";
195 DP << FileName << ":" << ExitLine << ": End of scop";
196}
197
Tobias Grosser75805372011-04-29 06:27:02 +0000198//===----------------------------------------------------------------------===//
199// ScopDetection.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000200
Johannes Doerfertb164c792014-09-18 11:17:17 +0000201ScopDetection::ScopDetection() : FunctionPass(ID) {
202 if (!PollyUseRuntimeAliasChecks)
203 return;
204
Johannes Doerfert928229f2014-09-29 17:06:29 +0000205 // Disable runtime alias checks if we ignore aliasing all together.
206 if (IgnoreAliasing) {
207 PollyUseRuntimeAliasChecks = false;
208 return;
209 }
210
Johannes Doerfertb164c792014-09-18 11:17:17 +0000211 if (AllowNonAffine) {
212 DEBUG(errs() << "WARNING: We disable runtime alias checks as non affine "
213 "accesses are enabled.\n");
214 PollyUseRuntimeAliasChecks = false;
215 }
Johannes Doerfertb164c792014-09-18 11:17:17 +0000216}
217
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000218template <class RR, typename... Args>
219inline bool ScopDetection::invalid(DetectionContext &Context, bool Assert,
220 Args &&... Arguments) const {
221
222 if (!Context.Verifying) {
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000223 RejectLog &Log = Context.Log;
224 std::shared_ptr<RR> RejectReason = std::make_shared<RR>(Arguments...);
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000225
Andreas Simbuerger8a00c9b2014-05-24 09:25:06 +0000226 if (PollyTrackFailures)
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000227 Log.report(RejectReason);
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000228
229 DEBUG(dbgs() << RejectReason->getMessage());
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000230 DEBUG(dbgs() << "\n");
231 } else {
232 assert(!Assert && "Verification of detected scop failed");
233 }
234
235 return false;
236}
237
Tobias Grossera1689932014-02-18 18:49:49 +0000238bool ScopDetection::isMaxRegionInScop(const Region &R, bool Verify) const {
239 if (!ValidRegions.count(&R))
240 return false;
241
242 if (Verify)
243 return isValidRegion(const_cast<Region &>(R));
244
245 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000246}
247
Tobias Grosser4f129a62011-10-08 00:30:55 +0000248std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
Andreas Simbuerger8a00c9b2014-05-24 09:25:06 +0000249 if (!RejectLogs.count(R))
Tobias Grosser4f129a62011-10-08 00:30:55 +0000250 return "";
251
Andreas Simbuerger8a00c9b2014-05-24 09:25:06 +0000252 // Get the first error we found. Even in keep-going mode, this is the first
253 // reason that caused the candidate to be rejected.
254 RejectLog Errors = RejectLogs.at(R);
Andreas Simbuerger83ed8612014-06-12 07:25:08 +0000255
256 // This can happen when we marked a region invalid, but didn't track
257 // an error for it.
258 if (Errors.size() == 0)
259 return "";
260
261 RejectReasonPtr RR = *Errors.begin();
262 return RR->getMessage();
Tobias Grosser4f129a62011-10-08 00:30:55 +0000263}
264
Tobias Grossere602a072013-05-07 07:30:56 +0000265bool ScopDetection::isValidCFG(BasicBlock &BB,
266 DetectionContext &Context) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000267 Region &RefRegion = Context.CurRegion;
268 TerminatorInst *TI = BB.getTerminator();
269
270 // Return instructions are only valid if the region is the top level region.
271 if (isa<ReturnInst>(TI) && !RefRegion.getExit() && TI->getNumOperands() == 0)
272 return true;
273
274 BranchInst *Br = dyn_cast<BranchInst>(TI);
275
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000276 if (!Br)
277 return invalid<ReportNonBranchTerminator>(Context, /*Assert=*/true, &BB);
Tobias Grosser75805372011-04-29 06:27:02 +0000278
Tobias Grosser74394f02013-01-14 22:40:23 +0000279 if (Br->isUnconditional())
280 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000281
282 Value *Condition = Br->getCondition();
283
284 // UndefValue is not allowed as condition.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000285 if (isa<UndefValue>(Condition))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000286 return invalid<ReportUndefCond>(Context, /*Assert=*/true, Br, &BB);
Tobias Grosser75805372011-04-29 06:27:02 +0000287
288 // Only Constant and ICmpInst are allowed as condition.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000289 if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition)))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000290 return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Br, &BB);
Tobias Grosser75805372011-04-29 06:27:02 +0000291
292 // Allow perfectly nested conditions.
293 assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
294
295 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
296 // Unsigned comparisons are not allowed. They trigger overflow problems
297 // in the code generation.
298 //
299 // TODO: This is not sufficient and just hides bugs. However it does pretty
300 // well.
Tobias Grosserbfbc3692015-01-09 00:01:33 +0000301 if (ICmp->isUnsigned() && !AllowUnsigned)
Tobias Grosser75805372011-04-29 06:27:02 +0000302 return false;
303
304 // Are both operands of the ICmp affine?
Tobias Grosser74394f02013-01-14 22:40:23 +0000305 if (isa<UndefValue>(ICmp->getOperand(0)) ||
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000306 isa<UndefValue>(ICmp->getOperand(1)))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000307 return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
Tobias Grosser75805372011-04-29 06:27:02 +0000308
Sebastian Pop9f57c5b2013-04-10 04:05:18 +0000309 Loop *L = LI->getLoopFor(ICmp->getParent());
310 const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
311 const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
Tobias Grosser75805372011-04-29 06:27:02 +0000312
Tobias Grossera66fa6c2011-11-10 12:45:11 +0000313 if (!isAffineExpr(&Context.CurRegion, LHS, *SE) ||
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000314 !isAffineExpr(&Context.CurRegion, RHS, *SE))
315 return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000316 RHS, ICmp);
Tobias Grosser75805372011-04-29 06:27:02 +0000317 }
318
319 // Allow loop exit conditions.
320 Loop *L = LI->getLoopFor(&BB);
321 if (L && L->getExitingBlock() == &BB)
322 return true;
323
324 // Allow perfectly nested conditions.
325 Region *R = RI->getRegionFor(&BB);
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000326 if (R->getEntry() != &BB)
327 return invalid<ReportCondition>(Context, /*Assert=*/true, &BB);
Tobias Grosser75805372011-04-29 06:27:02 +0000328
329 return true;
330}
331
332bool ScopDetection::isValidCallInst(CallInst &CI) {
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000333 if (CI.doesNotReturn())
Tobias Grosser75805372011-04-29 06:27:02 +0000334 return false;
335
336 if (CI.doesNotAccessMemory())
337 return true;
338
339 Function *CalledFunction = CI.getCalledFunction();
340
341 // Indirect calls are not supported.
342 if (CalledFunction == 0)
343 return false;
344
Johannes Doerfert3f500fa2015-01-25 18:07:30 +0000345 // Check if we can handle the intrinsic call.
346 if (auto *IT = dyn_cast<IntrinsicInst>(&CI)) {
347 switch (IT->getIntrinsicID()) {
348 // Lifetime markers are supported/ignored.
349 case llvm::Intrinsic::lifetime_start:
350 case llvm::Intrinsic::lifetime_end:
351 // Invariant markers are supported/ignored.
352 case llvm::Intrinsic::invariant_start:
353 case llvm::Intrinsic::invariant_end:
354 // Some misc annotations are supported/ignored.
355 case llvm::Intrinsic::var_annotation:
356 case llvm::Intrinsic::ptr_annotation:
357 case llvm::Intrinsic::annotation:
358 case llvm::Intrinsic::donothing:
359 case llvm::Intrinsic::assume:
360 case llvm::Intrinsic::expect:
361 return true;
362 default:
363 // Other intrinsics which may access the memory are not yet supported.
364 break;
365 }
366 }
367
Tobias Grosser75805372011-04-29 06:27:02 +0000368 return false;
369}
370
Tobias Grosser458fb782014-01-28 12:58:58 +0000371bool ScopDetection::isInvariant(const Value &Val, const Region &Reg) const {
372 // A reference to function argument or constant value is invariant.
373 if (isa<Argument>(Val) || isa<Constant>(Val))
374 return true;
375
376 const Instruction *I = dyn_cast<Instruction>(&Val);
377 if (!I)
378 return false;
379
380 if (!Reg.contains(I))
381 return true;
382
383 if (I->mayHaveSideEffects())
384 return false;
385
386 // When Val is a Phi node, it is likely not invariant. We do not check whether
387 // Phi nodes are actually invariant, we assume that Phi nodes are usually not
388 // invariant. Recursively checking the operators of Phi nodes would lead to
389 // infinite recursion.
390 if (isa<PHINode>(*I))
391 return false;
392
Tobias Grosser26108892014-04-02 20:18:19 +0000393 for (const Use &Operand : I->operands())
Tobias Grosser1d191902014-03-03 13:13:55 +0000394 if (!isInvariant(*Operand, Reg))
Tobias Grosser458fb782014-01-28 12:58:58 +0000395 return false;
Tobias Grosser458fb782014-01-28 12:58:58 +0000396
397 // When the instruction is a load instruction, check that no write to memory
398 // in the region aliases with the load.
399 if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
400 AliasAnalysis::Location Loc = AA->getLocation(LI);
401 const Region::const_block_iterator BE = Reg.block_end();
402 // Check if any basic block in the region can modify the location pointed to
403 // by 'Loc'. If so, 'Val' is (likely) not invariant in the region.
Tobias Grosser26108892014-04-02 20:18:19 +0000404 for (const BasicBlock *BB : Reg.blocks())
Tobias Grosser1d191902014-03-03 13:13:55 +0000405 if (AA->canBasicBlockModify(*BB, Loc))
Tobias Grosser458fb782014-01-28 12:58:58 +0000406 return false;
Tobias Grosser458fb782014-01-28 12:58:58 +0000407 }
408
409 return true;
410}
411
Sebastian Pop422e33f2014-06-03 18:16:31 +0000412MapInsnToMemAcc InsnToMemAcc;
413
Sebastian Popb57c0992014-05-12 20:24:26 +0000414bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const {
Tobias Grosser230acc42014-09-13 14:47:55 +0000415 for (const SCEVUnknown *BasePointer : Context.NonAffineAccesses) {
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000416 Value *BaseValue = BasePointer->getValue();
Sebastian Pop422e33f2014-06-03 18:16:31 +0000417 ArrayShape *Shape = new ArrayShape(BasePointer);
Tobias Grosser230acc42014-09-13 14:47:55 +0000418 bool BasePtrHasNonAffine = false;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000419
420 // First step: collect parametric terms in all array references.
421 SmallVector<const SCEV *, 4> Terms;
Tobias Grosser230acc42014-09-13 14:47:55 +0000422 for (const auto &Pair : Context.Accesses[BasePointer]) {
423 const SCEVAddRecExpr *AccessFunction =
424 dyn_cast<SCEVAddRecExpr>(Pair.second);
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000425
Tobias Grosser230acc42014-09-13 14:47:55 +0000426 if (AccessFunction)
427 AccessFunction->collectParametricTerms(*SE, Terms);
428 }
Sebastian Pope8863b82014-05-12 19:02:02 +0000429
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000430 // Second step: find array shape.
Sebastian Pop422e33f2014-06-03 18:16:31 +0000431 SE->findArrayDimensions(Terms, Shape->DelinearizedSizes,
432 Context.ElementSize[BasePointer]);
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000433
Tobias Grosser230acc42014-09-13 14:47:55 +0000434 // No array shape derived.
435 if (Shape->DelinearizedSizes.empty()) {
436 if (AllowNonAffine)
437 continue;
Sebastian Pope8863b82014-05-12 19:02:02 +0000438
Tobias Grosser230acc42014-09-13 14:47:55 +0000439 for (const auto &Pair : Context.Accesses[BasePointer]) {
440 const Instruction *Insn = Pair.first;
441 const SCEV *AF = Pair.second;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000442
Tobias Grosser230acc42014-09-13 14:47:55 +0000443 if (!isAffineExpr(&Context.CurRegion, AF, *SE, BaseValue)) {
444 invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, AF, Insn,
445 BaseValue);
446 if (!KeepGoing)
447 return false;
448 }
449 }
450 continue;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000451 }
Tobias Grosser230acc42014-09-13 14:47:55 +0000452
453 // Third step: compute the access functions for each subscript.
454 //
455 // We first store the resulting memory accesses in TempMemoryAccesses. Only
456 // if the access functions for all memory accesses have been successfully
457 // delinearized we continue. Otherwise, we either report a failure or, if
458 // non-affine accesses are allowed, we drop the information. In case the
459 // information is dropped the memory accesses need to be overapproximated
460 // when translated to a polyhedral representation.
461 MapInsnToMemAcc TempMemoryAccesses;
462 for (const auto &Pair : Context.Accesses[BasePointer]) {
463 const Instruction *Insn = Pair.first;
464 const SCEVAddRecExpr *AF = dyn_cast<SCEVAddRecExpr>(Pair.second);
465 bool IsNonAffine = false;
466 MemAcc *Acc = new MemAcc(Insn, Shape);
467 TempMemoryAccesses.insert({Insn, Acc});
468
469 if (!AF) {
470 if (isAffineExpr(&Context.CurRegion, Pair.second, *SE, BaseValue))
471 Acc->DelinearizedSubscripts.push_back(Pair.second);
472 else
473 IsNonAffine = true;
474 } else {
475 AF->computeAccessFunctions(*SE, Acc->DelinearizedSubscripts,
476 Shape->DelinearizedSizes);
477 if (Acc->DelinearizedSubscripts.size() == 0)
478 IsNonAffine = true;
479 for (const SCEV *S : Acc->DelinearizedSubscripts)
480 if (!isAffineExpr(&Context.CurRegion, S, *SE, BaseValue))
481 IsNonAffine = true;
482 }
483
484 // (Possibly) report non affine access
485 if (IsNonAffine) {
486 BasePtrHasNonAffine = true;
487 if (!AllowNonAffine)
Tobias Grosser021eaef2015-01-08 19:03:10 +0000488 invalid<ReportNonAffineAccess>(Context, /*Assert=*/true, Pair.second,
489 Insn, BaseValue);
Tobias Grosser230acc42014-09-13 14:47:55 +0000490 if (!KeepGoing && !AllowNonAffine)
491 return false;
492 }
493 }
494
495 if (!BasePtrHasNonAffine)
496 InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end());
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000497 }
Sebastian Pope8863b82014-05-12 19:02:02 +0000498 return true;
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000499}
500
Tobias Grosser75805372011-04-29 06:27:02 +0000501bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
502 DetectionContext &Context) const {
Tobias Grossere5e171e2011-11-10 12:45:03 +0000503 Value *Ptr = getPointerOperand(Inst);
Sebastian Pop9f57c5b2013-04-10 04:05:18 +0000504 Loop *L = LI->getLoopFor(Inst.getParent());
505 const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
Tobias Grosserb8710b52011-11-10 12:44:50 +0000506 const SCEVUnknown *BasePointer;
Tobias Grossere5e171e2011-11-10 12:45:03 +0000507 Value *BaseValue;
Tobias Grosser75805372011-04-29 06:27:02 +0000508
Tobias Grosserb8710b52011-11-10 12:44:50 +0000509 BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
510
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000511 if (!BasePointer)
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000512 return invalid<ReportNoBasePtr>(Context, /*Assert=*/true, &Inst);
Tobias Grosserb8710b52011-11-10 12:44:50 +0000513
514 BaseValue = BasePointer->getValue();
515
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000516 if (isa<UndefValue>(BaseValue))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000517 return invalid<ReportUndefBasePtr>(Context, /*Assert=*/true, &Inst);
Tobias Grosserb8710b52011-11-10 12:44:50 +0000518
Tobias Grosser458fb782014-01-28 12:58:58 +0000519 // Check that the base address of the access is invariant in the current
520 // region.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000521 if (!isInvariant(*BaseValue, Context.CurRegion))
Tobias Grosserab2227a2014-01-28 13:43:24 +0000522 // Verification of this property is difficult as the independent blocks
523 // pass may introduce aliasing that we did not have when running the
524 // scop detection.
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000525 return invalid<ReportVariantBasePtr>(Context, /*Assert=*/false, BaseValue,
526 &Inst);
Tobias Grosser458fb782014-01-28 12:58:58 +0000527
Tobias Grosserb8710b52011-11-10 12:44:50 +0000528 AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
529
Tobias Grosserbcd4eff2014-09-13 14:47:40 +0000530 const SCEV *Size = SE->getElementSize(&Inst);
531 if (Context.ElementSize.count(BasePointer)) {
532 if (Context.ElementSize[BasePointer] != Size)
533 return invalid<ReportDifferentArrayElementSize>(Context, /*Assert=*/true,
534 &Inst, BaseValue);
535 } else {
536 Context.ElementSize[BasePointer] = Size;
537 }
538
Tobias Grosser230acc42014-09-13 14:47:55 +0000539 if (PollyDelinearize) {
540 Context.Accesses[BasePointer].push_back({&Inst, AccessFunction});
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000541
Tobias Grosser230acc42014-09-13 14:47:55 +0000542 if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
543 Context.NonAffineAccesses.insert(BasePointer);
544 } else if (!AllowNonAffine) {
545 if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue))
Sebastian Popcd3bb592014-04-10 16:08:11 +0000546 return invalid<ReportNonAffineAccess>(Context, /*Assert=*/true,
Andreas Simbuergerd46b9352014-08-17 10:09:11 +0000547 AccessFunction, &Inst, BaseValue);
Sebastian Pop18016682014-04-08 21:20:44 +0000548 }
Tobias Grosser75805372011-04-29 06:27:02 +0000549
550 // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
551 // created by IndependentBlocks Pass.
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000552 if (IntToPtrInst *Inst = dyn_cast<IntToPtrInst>(BaseValue))
553 return invalid<ReportIntToPtr>(Context, /*Assert=*/true, Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000554
Tobias Grosser1eedb672014-09-24 21:04:29 +0000555 if (IgnoreAliasing)
Sebastian Pop8c2d7532013-07-03 22:50:36 +0000556 return true;
Tobias Grosserfff5adc2011-11-10 13:21:43 +0000557
Sebastian Pop8c2d7532013-07-03 22:50:36 +0000558 // Check if the base pointer of the memory access does alias with
559 // any other pointer. This cannot be handled at the moment.
Benjamin Kramerae81abf2014-10-05 11:58:57 +0000560 AAMDNodes AATags;
561 Inst.getAAMetadata(AATags);
562 AliasSet &AS = Context.AST.getAliasSetForPointer(
563 BaseValue, AliasAnalysis::UnknownSize, AATags);
Tobias Grosser428b3e42013-02-04 15:46:25 +0000564
Sebastian Pop8c2d7532013-07-03 22:50:36 +0000565 // INVALID triggers an assertion in verifying mode, if it detects that a
566 // SCoP was detected by SCoP detection and that this SCoP was invalidated by
567 // a pass that stated it would preserve the SCoPs. We disable this check as
568 // the independent blocks pass may create memory references which seem to
569 // alias, if -basicaa is not available. They actually do not, but as we can
570 // not proof this without -basicaa we would fail. We disable this check to
571 // not cause irrelevant verification failures.
Tobias Grosser1eedb672014-09-24 21:04:29 +0000572 if (!AS.isMustAlias()) {
573 if (PollyUseRuntimeAliasChecks) {
574 bool CanBuildRunTimeCheck = true;
575 // The run-time alias check places code that involves the base pointer at
576 // the beginning of the SCoP. This breaks if the base pointer is defined
577 // inside the scop. Hence, we can only create a run-time check if we are
578 // sure the base pointer is not an instruction defined inside the scop.
579 for (const auto &Ptr : AS) {
580 Instruction *Inst = dyn_cast<Instruction>(Ptr.getValue());
581 if (Inst && Context.CurRegion.contains(Inst)) {
582 CanBuildRunTimeCheck = false;
583 break;
584 }
585 }
586
587 if (CanBuildRunTimeCheck)
588 return true;
589 }
Andreas Simbuergere2c92432014-06-26 10:19:57 +0000590 return invalid<ReportAlias>(Context, /*Assert=*/false, &Inst, AS);
Tobias Grosser1eedb672014-09-24 21:04:29 +0000591 }
Tobias Grosser75805372011-04-29 06:27:02 +0000592
593 return true;
594}
595
Tobias Grosser75805372011-04-29 06:27:02 +0000596bool ScopDetection::isValidInstruction(Instruction &Inst,
597 DetectionContext &Context) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000598 if (PHINode *PN = dyn_cast<PHINode>(&Inst))
Tobias Grosserecfe21b2013-03-20 18:03:18 +0000599 if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) {
Tobias Grosser683b8e42014-11-30 14:33:31 +0000600 return invalid<ReportPhiNodeRefInRegion>(Context, /*Assert=*/true, &Inst);
Tobias Grosserecfe21b2013-03-20 18:03:18 +0000601 }
Tobias Grosser75805372011-04-29 06:27:02 +0000602
Tobias Grosser75805372011-04-29 06:27:02 +0000603 // We only check the call instruction but not invoke instruction.
604 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
605 if (isValidCallInst(*CI))
606 return true;
607
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000608 return invalid<ReportFuncCall>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000609 }
610
611 if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) {
Tobias Grosser5b1a7f22013-07-22 03:50:33 +0000612 if (!isa<AllocaInst>(Inst))
613 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000614
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000615 return invalid<ReportAlloca>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000616 }
617
618 // Check the access function.
619 if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
620 return isValidMemoryAccess(Inst, Context);
621
622 // We do not know this instruction, therefore we assume it is invalid.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000623 return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000624}
625
Tobias Grosser75805372011-04-29 06:27:02 +0000626bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000627 // Is the loop count affine?
628 const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000629 if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE))
630 return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
Tobias Grosser75805372011-04-29 06:27:02 +0000631
632 return true;
633}
634
635Region *ScopDetection::expandRegion(Region &R) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000636 // Initial no valid region was found (greater than R)
Tobias Grosser5a56cbf2014-04-16 07:33:47 +0000637 Region *LastValidRegion = nullptr;
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000638 Region *ExpandedRegion = R.getExpandedRegion();
Tobias Grosser75805372011-04-29 06:27:02 +0000639
640 DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
641
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000642 while (ExpandedRegion) {
643 DetectionContext Context(*ExpandedRegion, *AA, false /* verifying */);
644 DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
Andreas Simbuergerb379edb2014-06-27 06:21:14 +0000645 // Only expand when we did not collect errors.
Tobias Grosser75805372011-04-29 06:27:02 +0000646
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000647 // Check the exit first (cheap)
Andreas Simbuergerb379edb2014-06-27 06:21:14 +0000648 if (isValidExit(Context) && !Context.Log.hasErrors()) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000649 // If the exit is valid check all blocks
650 // - if true, a valid region was found => store it + keep expanding
651 // - if false, .tbd. => stop (should this really end the loop?)
Andreas Simbuergerb379edb2014-06-27 06:21:14 +0000652 if (!allBlocksValid(Context) || Context.Log.hasErrors())
653 break;
654
655 if (Context.Log.hasErrors())
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000656 break;
Tobias Grosser75805372011-04-29 06:27:02 +0000657
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000658 // Delete unnecessary regions (allocated by getExpandedRegion)
659 if (LastValidRegion)
660 delete LastValidRegion;
661
Tobias Grosserd7e58642013-04-10 06:55:45 +0000662 // Store this region, because it is the greatest valid (encountered so
663 // far).
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000664 LastValidRegion = ExpandedRegion;
665
666 // Create and test the next greater region (if any)
667 ExpandedRegion = ExpandedRegion->getExpandedRegion();
668
669 } else {
670 // Create and test the next greater region (if any)
671 Region *TmpRegion = ExpandedRegion->getExpandedRegion();
672
673 // Delete unnecessary regions (allocated by getExpandedRegion)
674 delete ExpandedRegion;
675
676 ExpandedRegion = TmpRegion;
Tobias Grosser75805372011-04-29 06:27:02 +0000677 }
Tobias Grosser75805372011-04-29 06:27:02 +0000678 }
679
Tobias Grosser378a9f22013-11-16 19:34:11 +0000680 DEBUG({
681 if (LastValidRegion)
682 dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n";
683 else
684 dbgs() << "\tExpanding " << R.getNameStr() << " failed\n";
685 });
Tobias Grosser75805372011-04-29 06:27:02 +0000686
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000687 return LastValidRegion;
Tobias Grosser75805372011-04-29 06:27:02 +0000688}
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +0000689static bool regionWithoutLoops(Region &R, LoopInfo *LI) {
Tobias Grosser26108892014-04-02 20:18:19 +0000690 for (const BasicBlock *BB : R.blocks())
Tobias Grosser1d191902014-03-03 13:13:55 +0000691 if (R.contains(LI->getLoopFor(BB)))
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +0000692 return false;
693
694 return true;
695}
Tobias Grosser75805372011-04-29 06:27:02 +0000696
Tobias Grosser28a70c52014-01-29 19:05:30 +0000697// Remove all direct and indirect children of region R from the region set Regs,
698// but do not recurse further if the first child has been found.
699//
700// Return the number of regions erased from Regs.
David Peixotto8da2b932014-10-22 20:39:07 +0000701static unsigned eraseAllChildren(ScopDetection::RegionSet &Regs,
David Blaikieb035f6d2014-04-15 18:45:27 +0000702 const Region &R) {
Tobias Grosser28a70c52014-01-29 19:05:30 +0000703 unsigned Count = 0;
David Blaikieb035f6d2014-04-15 18:45:27 +0000704 for (auto &SubRegion : R) {
David Peixotto8da2b932014-10-22 20:39:07 +0000705 if (Regs.count(SubRegion.get())) {
Tobias Grosser28a70c52014-01-29 19:05:30 +0000706 ++Count;
David Peixotto8da2b932014-10-22 20:39:07 +0000707 Regs.remove(SubRegion.get());
Tobias Grosser28a70c52014-01-29 19:05:30 +0000708 } else {
David Blaikieb035f6d2014-04-15 18:45:27 +0000709 Count += eraseAllChildren(Regs, *SubRegion);
Tobias Grosser28a70c52014-01-29 19:05:30 +0000710 }
711 }
712 return Count;
713}
714
Tobias Grosser75805372011-04-29 06:27:02 +0000715void ScopDetection::findScops(Region &R) {
Sebastian Pop2c9ec2e2013-06-03 16:35:37 +0000716 if (!DetectRegionsWithoutLoops && regionWithoutLoops(R, LI))
717 return;
718
Andreas Simbuerger04472402014-05-24 09:25:10 +0000719 bool IsValidRegion = isValidRegion(R);
720 bool HasErrors = RejectLogs.count(&R) > 0;
721
722 if (IsValidRegion && !HasErrors) {
Tobias Grosser75805372011-04-29 06:27:02 +0000723 ++ValidRegion;
724 ValidRegions.insert(&R);
725 return;
726 }
727
David Blaikieb035f6d2014-04-15 18:45:27 +0000728 for (auto &SubRegion : R)
Tobias Grosser00dc3092014-03-02 12:02:46 +0000729 findScops(*SubRegion);
Tobias Grosser75805372011-04-29 06:27:02 +0000730
731 // Try to expand regions.
732 //
733 // As the region tree normally only contains canonical regions, non canonical
734 // regions that form a Scop are not found. Therefore, those non canonical
735 // regions are checked by expanding the canonical ones.
736
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000737 std::vector<Region *> ToExpand;
Tobias Grosser75805372011-04-29 06:27:02 +0000738
David Blaikieb035f6d2014-04-15 18:45:27 +0000739 for (auto &SubRegion : R)
740 ToExpand.push_back(SubRegion.get());
Tobias Grosser75805372011-04-29 06:27:02 +0000741
Tobias Grosser26108892014-04-02 20:18:19 +0000742 for (Region *CurrentRegion : ToExpand) {
Andreas Simbuergerb379edb2014-06-27 06:21:14 +0000743 // Skip regions that had errors.
744 bool HadErrors = RejectLogs.hasErrors(CurrentRegion);
745 if (HadErrors)
746 continue;
747
Tobias Grosser75805372011-04-29 06:27:02 +0000748 // Skip invalid regions. Regions may become invalid, if they are element of
749 // an already expanded region.
David Peixotto8da2b932014-10-22 20:39:07 +0000750 if (!ValidRegions.count(CurrentRegion))
Tobias Grosser75805372011-04-29 06:27:02 +0000751 continue;
752
753 Region *ExpandedR = expandRegion(*CurrentRegion);
754
755 if (!ExpandedR)
756 continue;
757
758 R.addSubRegion(ExpandedR, true);
759 ValidRegions.insert(ExpandedR);
David Peixotto8da2b932014-10-22 20:39:07 +0000760 ValidRegions.remove(CurrentRegion);
Tobias Grosser75805372011-04-29 06:27:02 +0000761
Tobias Grosser28a70c52014-01-29 19:05:30 +0000762 // Erase all (direct and indirect) children of ExpandedR from the valid
763 // regions and update the number of valid regions.
David Blaikieb035f6d2014-04-15 18:45:27 +0000764 ValidRegion -= eraseAllChildren(ValidRegions, *ExpandedR);
Tobias Grosser75805372011-04-29 06:27:02 +0000765 }
766}
767
768bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
769 Region &R = Context.CurRegion;
770
Tobias Grosser26108892014-04-02 20:18:19 +0000771 for (const BasicBlock *BB : R.blocks()) {
Tobias Grosser1d191902014-03-03 13:13:55 +0000772 Loop *L = LI->getLoopFor(BB);
Andreas Simbuerger04472402014-05-24 09:25:10 +0000773 if (L && L->getHeader() == BB && (!isValidLoop(L, Context) && !KeepGoing))
Sebastian Popb88ea5e2013-06-11 22:20:32 +0000774 return false;
775 }
776
Tobias Grosser26108892014-04-02 20:18:19 +0000777 for (BasicBlock *BB : R.blocks())
Andreas Simbuerger04472402014-05-24 09:25:10 +0000778 if (!isValidCFG(*BB, Context) && !KeepGoing)
Sebastian Pop9e3d2dd2013-06-11 22:20:27 +0000779 return false;
780
Tobias Grosser26108892014-04-02 20:18:19 +0000781 for (BasicBlock *BB : R.blocks())
Tobias Grosser1d191902014-03-03 13:13:55 +0000782 for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
Andreas Simbuerger04472402014-05-24 09:25:10 +0000783 if (!isValidInstruction(*I, Context) && !KeepGoing)
Sebastian Pop8ca899c2013-06-14 20:20:43 +0000784 return false;
Tobias Grosser75805372011-04-29 06:27:02 +0000785
Sebastian Pope8863b82014-05-12 19:02:02 +0000786 if (!hasAffineMemoryAccesses(Context))
Sebastian Pop46e1ecd2014-05-09 22:45:15 +0000787 return false;
788
Tobias Grosser75805372011-04-29 06:27:02 +0000789 return true;
790}
791
792bool ScopDetection::isValidExit(DetectionContext &Context) const {
793 Region &R = Context.CurRegion;
794
795 // PHI nodes are not allowed in the exit basic block.
796 if (BasicBlock *Exit = R.getExit()) {
797 BasicBlock::iterator I = Exit->begin();
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000798 if (I != Exit->end() && isa<PHINode>(*I))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000799 return invalid<ReportPHIinExit>(Context, /*Assert=*/true, I);
Tobias Grosser75805372011-04-29 06:27:02 +0000800 }
801
802 return true;
803}
804
Tobias Grosser9b1100b2014-02-18 18:49:46 +0000805bool ScopDetection::isValidRegion(Region &R) const {
806 DetectionContext Context(R, *AA, false /*verifying*/);
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000807
808 bool RegionIsValid = isValidRegion(Context);
Andreas Simbuerger04472402014-05-24 09:25:10 +0000809 bool HasErrors = !RegionIsValid || Context.Log.size() > 0;
810
Andreas Simbuerger5bf774c2014-06-26 13:36:52 +0000811 if (PollyTrackFailures && HasErrors)
812 RejectLogs.insert(std::make_pair(&R, Context.Log));
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000813
814 return RegionIsValid;
Tobias Grosser9b1100b2014-02-18 18:49:46 +0000815}
816
Tobias Grosser75805372011-04-29 06:27:02 +0000817bool ScopDetection::isValidRegion(DetectionContext &Context) const {
818 Region &R = Context.CurRegion;
819
820 DEBUG(dbgs() << "Checking region: " << R.getNameStr() << "\n\t");
821
Tobias Grosseraeabcf22013-04-02 06:41:48 +0000822 if (R.isTopLevelRegion()) {
Tobias Grosserf084edd2014-10-22 23:00:03 +0000823 DEBUG(dbgs() << "Top level region is invalid\n");
Tobias Grosser75805372011-04-29 06:27:02 +0000824 return false;
825 }
826
Tobias Grosser4449e522014-01-27 14:24:53 +0000827 if (!R.getEntry()->getName().count(OnlyRegion)) {
828 DEBUG({
829 dbgs() << "Region entry does not match -polly-region-only";
830 dbgs() << "\n";
831 });
832 return false;
833 }
834
Tobias Grossere602a072013-05-07 07:30:56 +0000835 if (!R.getEnteringBlock()) {
Sebastian Pop9d632342013-06-11 22:20:40 +0000836 BasicBlock *entry = R.getEntry();
837 Loop *L = LI->getLoopFor(entry);
838
839 if (L) {
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000840 if (!L->isLoopSimplifyForm())
841 return invalid<ReportSimpleLoop>(Context, /*Assert=*/true);
Sebastian Pop9d632342013-06-11 22:20:40 +0000842
843 for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
844 ++PI) {
845 // Region entering edges come from the same loop but outside the region
846 // are not allowed.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000847 if (L->contains(*PI) && !R.contains(*PI))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000848 return invalid<ReportIndEdge>(Context, /*Assert=*/true, *PI);
Sebastian Pop9d632342013-06-11 22:20:40 +0000849 }
850 }
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000851 }
852
Tobias Grosserd654c252012-04-10 18:12:19 +0000853 // SCoP cannot contain the entry block of the function, because we need
Tobias Grosser75805372011-04-29 06:27:02 +0000854 // to insert alloca instruction there when translate scalar to array.
Andreas Simbuerger01a37a02014-04-02 11:54:01 +0000855 if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock()))
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000856 return invalid<ReportEntry>(Context, /*Assert=*/true, R.getEntry());
Tobias Grosser75805372011-04-29 06:27:02 +0000857
Hongbin Zheng94868e62012-04-07 12:29:17 +0000858 if (!isValidExit(Context))
Tobias Grosser75805372011-04-29 06:27:02 +0000859 return false;
860
Hongbin Zheng94868e62012-04-07 12:29:17 +0000861 if (!allBlocksValid(Context))
Tobias Grosser75805372011-04-29 06:27:02 +0000862 return false;
863
864 DEBUG(dbgs() << "OK\n");
865 return true;
866}
867
Johannes Doerfert43e1ead2014-07-15 21:06:48 +0000868void ScopDetection::markFunctionAsInvalid(Function *F) const {
869 F->addFnAttr(PollySkipFnAttr);
870}
871
Tobias Grosser75805372011-04-29 06:27:02 +0000872bool ScopDetection::isValidFunction(llvm::Function &F) {
Johannes Doerfert43e1ead2014-07-15 21:06:48 +0000873 return !F.hasFnAttribute(PollySkipFnAttr);
Tobias Grosser75805372011-04-29 06:27:02 +0000874}
875
Tobias Grosserb2863ca2013-03-04 19:49:51 +0000876void ScopDetection::printLocations(llvm::Function &F) {
Tobias Grosser26108892014-04-02 20:18:19 +0000877 for (const Region *R : *this) {
Tobias Grosser531891e2012-11-01 16:45:20 +0000878 unsigned LineEntry, LineExit;
879 std::string FileName;
880
Tobias Grosser00dc3092014-03-02 12:02:46 +0000881 getDebugLocation(R, LineEntry, LineExit, FileName);
Tobias Grosser8519f892013-12-18 10:49:53 +0000882 DiagnosticScopFound Diagnostic(F, FileName, LineEntry, LineExit);
883 F.getContext().diagnose(Diagnostic);
Tobias Grosser531891e2012-11-01 16:45:20 +0000884 }
885}
886
Daniel Jasper8a1dea02014-10-27 19:45:31 +0000887void ScopDetection::emitMissedRemarksForValidRegions(
888 const Function &F, const RegionSet &ValidRegions) {
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000889 for (const Region *R : ValidRegions) {
890 const Region *Parent = R->getParent();
891 if (Parent && !Parent->isTopLevelRegion() && RejectLogs.count(Parent))
892 emitRejectionRemarks(F, RejectLogs.at(Parent));
893 }
894}
895
896void ScopDetection::emitMissedRemarksForLeaves(const Function &F,
897 const Region *R) {
898 for (const std::unique_ptr<Region> &Child : *R) {
899 bool IsValid = ValidRegions.count(Child.get());
900 if (IsValid)
901 continue;
902
903 bool IsLeaf = Child->begin() == Child->end();
904 if (!IsLeaf)
905 emitMissedRemarksForLeaves(F, Child.get());
906 else {
907 if (RejectLogs.count(Child.get())) {
908 emitRejectionRemarks(F, RejectLogs.at(Child.get()));
909 }
910 }
911 }
912}
913
Tobias Grosser75805372011-04-29 06:27:02 +0000914bool ScopDetection::runOnFunction(llvm::Function &F) {
Chandler Carruthf5579872015-01-17 14:16:56 +0000915 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Matt Arsenault8ca36812014-07-19 18:40:17 +0000916 RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
Sebastian Pop8fe6d112013-05-30 17:47:32 +0000917 if (!DetectScopsWithoutLoops && LI->empty())
918 return false;
919
Tobias Grosser75805372011-04-29 06:27:02 +0000920 AA = &getAnalysis<AliasAnalysis>();
921 SE = &getAnalysis<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +0000922 Region *TopRegion = RI->getTopLevelRegion();
923
Tobias Grosser2ff87232011-10-23 11:17:06 +0000924 releaseMemory();
925
Tobias Grossera3ab27e2014-05-07 11:23:32 +0000926 if (OnlyFunction != "" && !F.getName().count(OnlyFunction))
Tobias Grosser2ff87232011-10-23 11:17:06 +0000927 return false;
928
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000929 if (!isValidFunction(F))
Tobias Grosser75805372011-04-29 06:27:02 +0000930 return false;
931
932 findScops(*TopRegion);
Tobias Grosser531891e2012-11-01 16:45:20 +0000933
Andreas Simbuerger5569bf32014-06-26 10:06:40 +0000934 // Only makes sense when we tracked errors.
935 if (PollyTrackFailures) {
936 emitMissedRemarksForValidRegions(F, ValidRegions);
937 emitMissedRemarksForLeaves(F, TopRegion);
938 }
939
940 for (const Region *R : ValidRegions)
941 emitValidRemarks(F, R);
942
Johannes Doerferta05214f2014-10-15 23:24:28 +0000943 if (ReportLevel)
Tobias Grosserb2863ca2013-03-04 19:49:51 +0000944 printLocations(F);
Tobias Grosser531891e2012-11-01 16:45:20 +0000945
Tobias Grosser75805372011-04-29 06:27:02 +0000946 return false;
947}
948
Tobias Grosser75805372011-04-29 06:27:02 +0000949void polly::ScopDetection::verifyRegion(const Region &R) const {
950 assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000951 DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/);
Tobias Grosser75805372011-04-29 06:27:02 +0000952 isValidRegion(Context);
953}
954
955void polly::ScopDetection::verifyAnalysis() const {
Tobias Grossera1689932014-02-18 18:49:49 +0000956 if (!VerifyScops)
957 return;
958
Tobias Grosser26108892014-04-02 20:18:19 +0000959 for (const Region *R : ValidRegions)
Tobias Grosser00dc3092014-03-02 12:02:46 +0000960 verifyRegion(*R);
Tobias Grosser75805372011-04-29 06:27:02 +0000961}
962
963void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
Tobias Grosser42aff302014-01-13 22:29:56 +0000964 AU.addRequired<DominatorTreeWrapperPass>();
Tobias Grosser75805372011-04-29 06:27:02 +0000965 AU.addRequired<PostDominatorTree>();
Chandler Carruthf5579872015-01-17 14:16:56 +0000966 AU.addRequired<LoopInfoWrapperPass>();
Tobias Grosser75805372011-04-29 06:27:02 +0000967 AU.addRequired<ScalarEvolution>();
968 // We also need AA and RegionInfo when we are verifying analysis.
969 AU.addRequiredTransitive<AliasAnalysis>();
Matt Arsenault8ca36812014-07-19 18:40:17 +0000970 AU.addRequiredTransitive<RegionInfoPass>();
Tobias Grosser75805372011-04-29 06:27:02 +0000971 AU.setPreservesAll();
972}
973
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000974void ScopDetection::print(raw_ostream &OS, const Module *) const {
Tobias Grosser26108892014-04-02 20:18:19 +0000975 for (const Region *R : ValidRegions)
Tobias Grosser00dc3092014-03-02 12:02:46 +0000976 OS << "Valid Region for Scop: " << R->getNameStr() << '\n';
Tobias Grosser75805372011-04-29 06:27:02 +0000977
978 OS << "\n";
979}
980
981void ScopDetection::releaseMemory() {
982 ValidRegions.clear();
Andreas Simbuerger4870e092014-05-24 09:25:01 +0000983 RejectLogs.clear();
984
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000985 // Do not clear the invalid function set.
Tobias Grosser75805372011-04-29 06:27:02 +0000986}
987
988char ScopDetection::ID = 0;
989
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000990Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
991
Tobias Grosser73600b82011-10-08 00:30:40 +0000992INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect",
993 "Polly - Detect static control parts (SCoPs)", false,
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000994 false);
995INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
Tobias Grosser42aff302014-01-13 22:29:56 +0000996INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
Chandler Carruthf5579872015-01-17 14:16:56 +0000997INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000998INITIALIZE_PASS_DEPENDENCY(PostDominatorTree);
Matt Arsenault8ca36812014-07-19 18:40:17 +0000999INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00001000INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
Tobias Grosser73600b82011-10-08 00:30:40 +00001001INITIALIZE_PASS_END(ScopDetection, "polly-detect",
1002 "Polly - Detect static control parts (SCoPs)", false, false)