blob: bbf15ff1bf24eafa49c52a2ca98ad829cead50ed [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"
Tobias Grosserecfe21b2013-03-20 18:03:18 +000050#include "polly/ScopDetection.h"
Tobias Grosser120db6b2011-11-07 12:58:54 +000051#include "polly/Support/SCEVValidator.h"
Tobias Grosser83628182013-05-07 08:11:54 +000052#include "polly/Support/ScopHelper.h"
Tobias Grosser75805372011-04-29 06:27:02 +000053#include "llvm/ADT/Statistic.h"
54#include "llvm/Analysis/AliasAnalysis.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000055#include "llvm/Analysis/LoopInfo.h"
Tobias Grosser75805372011-04-29 06:27:02 +000056#include "llvm/Analysis/RegionIterator.h"
Tobias Grosser6e9f25a2011-11-09 22:35:00 +000057#include "llvm/Analysis/ScalarEvolution.h"
Tobias Grosserb8710b52011-11-10 12:44:50 +000058#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Tobias Grosser75805372011-04-29 06:27:02 +000059#include "llvm/Assembly/Writer.h"
Tobias Grosser83628182013-05-07 08:11:54 +000060#include "llvm/DebugInfo.h"
61#include "llvm/IR/LLVMContext.h"
Tobias Grosser75805372011-04-29 06:27:02 +000062
63#define DEBUG_TYPE "polly-detect"
64#include "llvm/Support/Debug.h"
65
Tobias Grosser60b54f12011-11-08 15:41:28 +000066#include <set>
67
Tobias Grosser75805372011-04-29 06:27:02 +000068using namespace llvm;
69using namespace polly;
70
Sebastian Pop8fe6d112013-05-30 17:47:32 +000071static cl::opt<bool>
72DetectScopsWithoutLoops("polly-detect-scops-in-functions-without-loops",
73 cl::desc("Detect scops in functions without loops"),
74 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
75
Tobias Grosser2ff87232011-10-23 11:17:06 +000076static cl::opt<std::string>
Tobias Grosser637bd632013-05-07 07:31:10 +000077OnlyFunction("polly-only-func", cl::desc("Only run on a single function"),
78 cl::value_desc("function-name"), cl::ValueRequired, cl::init(""),
79 cl::cat(PollyCategory));
Tobias Grosser2ff87232011-10-23 11:17:06 +000080
Tobias Grosser60cd9322011-11-10 12:47:26 +000081static cl::opt<bool>
82IgnoreAliasing("polly-ignore-aliasing",
83 cl::desc("Ignore possible aliasing of the array bases"),
Tobias Grosser637bd632013-05-07 07:31:10 +000084 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
Tobias Grosser2ff87232011-10-23 11:17:06 +000085
Tobias Grosser637bd632013-05-07 07:31:10 +000086static cl::opt<bool>
87ReportLevel("polly-report",
88 cl::desc("Print information about the activities of Polly"),
89 cl::init(false), cl::cat(PollyCategory));
Tobias Grosser531891e2012-11-01 16:45:20 +000090
91static cl::opt<bool>
Tobias Grossera1879642011-12-20 10:43:14 +000092AllowNonAffine("polly-allow-nonaffine",
93 cl::desc("Allow non affine access functions in arrays"),
Tobias Grosser637bd632013-05-07 07:31:10 +000094 cl::Hidden, cl::init(false), cl::cat(PollyCategory));
Tobias Grossera1879642011-12-20 10:43:14 +000095
Tobias Grosser75805372011-04-29 06:27:02 +000096//===----------------------------------------------------------------------===//
97// Statistics.
98
99STATISTIC(ValidRegion, "Number of regions that a valid part of Scop");
100
Tobias Grosser74394f02013-01-14 22:40:23 +0000101#define BADSCOP_STAT(NAME, DESC) \
102 STATISTIC(Bad##NAME##ForScop, "Number of bad regions for Scop: " DESC)
Tobias Grosser75805372011-04-29 06:27:02 +0000103
Tobias Grosser74394f02013-01-14 22:40:23 +0000104#define INVALID(NAME, MESSAGE) \
105 do { \
106 std::string Buf; \
107 raw_string_ostream fmt(Buf); \
108 fmt << MESSAGE; \
109 fmt.flush(); \
110 LastFailure = Buf; \
111 DEBUG(dbgs() << MESSAGE); \
112 DEBUG(dbgs() << "\n"); \
113 assert(!Context.Verifying && #NAME); \
114 if (!Context.Verifying) \
115 ++Bad##NAME##ForScop; \
116 return false; \
Tobias Grosser84b81de2013-03-19 21:44:07 +0000117 } while (0)
Tobias Grosserfff5adc2011-11-10 13:21:43 +0000118
Tobias Grosser74394f02013-01-14 22:40:23 +0000119#define INVALID_NOVERIFY(NAME, MESSAGE) \
120 do { \
121 std::string Buf; \
122 raw_string_ostream fmt(Buf); \
123 fmt << MESSAGE; \
124 fmt.flush(); \
125 LastFailure = Buf; \
126 DEBUG(dbgs() << MESSAGE); \
127 DEBUG(dbgs() << "\n"); \
128 /* DISABLED: assert(!Context.Verifying && #NAME); */ \
129 if (!Context.Verifying) \
130 ++Bad##NAME##ForScop; \
131 return false; \
Tobias Grosser84b81de2013-03-19 21:44:07 +0000132 } while (0)
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000133
Tobias Grosser74394f02013-01-14 22:40:23 +0000134BADSCOP_STAT(CFG, "CFG too complex");
135BADSCOP_STAT(IndVar, "Non canonical induction variable in loop");
136BADSCOP_STAT(LoopBound, "Loop bounds can not be computed");
137BADSCOP_STAT(FuncCall, "Function call with side effects appeared");
138BADSCOP_STAT(AffFunc, "Expression not affine");
139BADSCOP_STAT(Scalar, "Found scalar dependency");
140BADSCOP_STAT(Alias, "Found base address alias");
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000141BADSCOP_STAT(SimpleLoop, "Loop not in -loop-simplify form");
Tobias Grosser74394f02013-01-14 22:40:23 +0000142BADSCOP_STAT(Other, "Others");
Tobias Grosser75805372011-04-29 06:27:02 +0000143
144//===----------------------------------------------------------------------===//
145// ScopDetection.
Tobias Grosser75805372011-04-29 06:27:02 +0000146bool ScopDetection::isMaxRegionInScop(const Region &R) const {
147 // The Region is valid only if it could be found in the set.
148 return ValidRegions.count(&R);
149}
150
Tobias Grosser4f129a62011-10-08 00:30:55 +0000151std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
152 if (!InvalidRegions.count(R))
153 return "";
154
155 return InvalidRegions.find(R)->second;
156}
157
Tobias Grossere602a072013-05-07 07:30:56 +0000158bool ScopDetection::isValidCFG(BasicBlock &BB,
159 DetectionContext &Context) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000160 Region &RefRegion = Context.CurRegion;
161 TerminatorInst *TI = BB.getTerminator();
162
163 // Return instructions are only valid if the region is the top level region.
164 if (isa<ReturnInst>(TI) && !RefRegion.getExit() && TI->getNumOperands() == 0)
165 return true;
166
167 BranchInst *Br = dyn_cast<BranchInst>(TI);
168
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000169 if (!Br)
Tobias Grosser29ee0b12011-11-17 14:52:36 +0000170 INVALID(CFG, "Non branch instruction terminates BB: " + BB.getName());
Tobias Grosser75805372011-04-29 06:27:02 +0000171
Tobias Grosser74394f02013-01-14 22:40:23 +0000172 if (Br->isUnconditional())
173 return true;
Tobias Grosser75805372011-04-29 06:27:02 +0000174
175 Value *Condition = Br->getCondition();
176
177 // UndefValue is not allowed as condition.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000178 if (isa<UndefValue>(Condition))
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000179 INVALID(AffFunc, "Condition based on 'undef' value in BB: " + BB.getName());
Tobias Grosser75805372011-04-29 06:27:02 +0000180
181 // Only Constant and ICmpInst are allowed as condition.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000182 if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition)))
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000183 INVALID(AffFunc, "Condition in BB '" + BB.getName() +
Tobias Grosserd7e58642013-04-10 06:55:45 +0000184 "' neither constant nor an icmp instruction");
Tobias Grosser75805372011-04-29 06:27:02 +0000185
186 // Allow perfectly nested conditions.
187 assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
188
189 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
190 // Unsigned comparisons are not allowed. They trigger overflow problems
191 // in the code generation.
192 //
193 // TODO: This is not sufficient and just hides bugs. However it does pretty
194 // well.
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000195 if (ICmp->isUnsigned())
Tobias Grosser75805372011-04-29 06:27:02 +0000196 return false;
197
198 // Are both operands of the ICmp affine?
Tobias Grosser74394f02013-01-14 22:40:23 +0000199 if (isa<UndefValue>(ICmp->getOperand(0)) ||
200 isa<UndefValue>(ICmp->getOperand(1)))
Tobias Grosser29ee0b12011-11-17 14:52:36 +0000201 INVALID(AffFunc, "undef operand in branch at BB: " + BB.getName());
Tobias Grosser75805372011-04-29 06:27:02 +0000202
Sebastian Pop9f57c5b2013-04-10 04:05:18 +0000203 Loop *L = LI->getLoopFor(ICmp->getParent());
204 const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
205 const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
Tobias Grosser75805372011-04-29 06:27:02 +0000206
Tobias Grossera66fa6c2011-11-10 12:45:11 +0000207 if (!isAffineExpr(&Context.CurRegion, LHS, *SE) ||
208 !isAffineExpr(&Context.CurRegion, RHS, *SE))
Tobias Grosser29ee0b12011-11-17 14:52:36 +0000209 INVALID(AffFunc, "Non affine branch in BB '" << BB.getName()
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000210 << "' with LHS: " << *LHS
211 << " and RHS: " << *RHS);
Tobias Grosser75805372011-04-29 06:27:02 +0000212 }
213
214 // Allow loop exit conditions.
215 Loop *L = LI->getLoopFor(&BB);
216 if (L && L->getExitingBlock() == &BB)
217 return true;
218
219 // Allow perfectly nested conditions.
220 Region *R = RI->getRegionFor(&BB);
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000221 if (R->getEntry() != &BB)
Tobias Grosser29ee0b12011-11-17 14:52:36 +0000222 INVALID(CFG, "Not well structured condition at BB: " + BB.getName());
Tobias Grosser75805372011-04-29 06:27:02 +0000223
224 return true;
225}
226
227bool ScopDetection::isValidCallInst(CallInst &CI) {
228 if (CI.mayHaveSideEffects() || CI.doesNotReturn())
229 return false;
230
231 if (CI.doesNotAccessMemory())
232 return true;
233
234 Function *CalledFunction = CI.getCalledFunction();
235
236 // Indirect calls are not supported.
237 if (CalledFunction == 0)
238 return false;
239
240 // TODO: Intrinsics.
241 return false;
242}
243
244bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
245 DetectionContext &Context) const {
Tobias Grossere5e171e2011-11-10 12:45:03 +0000246 Value *Ptr = getPointerOperand(Inst);
Sebastian Pop9f57c5b2013-04-10 04:05:18 +0000247 Loop *L = LI->getLoopFor(Inst.getParent());
248 const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L);
Tobias Grosserb8710b52011-11-10 12:44:50 +0000249 const SCEVUnknown *BasePointer;
Tobias Grossere5e171e2011-11-10 12:45:03 +0000250 Value *BaseValue;
Tobias Grosser75805372011-04-29 06:27:02 +0000251
Tobias Grosserb8710b52011-11-10 12:44:50 +0000252 BasePointer = dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
253
254 if (!BasePointer)
255 INVALID(AffFunc, "No base pointer");
256
257 BaseValue = BasePointer->getValue();
258
259 if (isa<UndefValue>(BaseValue))
260 INVALID(AffFunc, "Undefined base pointer");
261
262 AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
263
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000264 if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue) &&
265 !AllowNonAffine)
Tobias Grossereeb776a2012-09-08 14:00:37 +0000266 INVALID(AffFunc, "Non affine access function: " << *AccessFunction);
Tobias Grosser75805372011-04-29 06:27:02 +0000267
268 // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
269 // created by IndependentBlocks Pass.
Tobias Grossere5e171e2011-11-10 12:45:03 +0000270 if (isa<IntToPtrInst>(BaseValue))
271 INVALID(Other, "Find bad intToptr prt: " << *BaseValue);
Tobias Grosser75805372011-04-29 06:27:02 +0000272
273 // Check if the base pointer of the memory access does alias with
274 // any other pointer. This cannot be handled at the moment.
275 AliasSet &AS =
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000276 Context.AST.getAliasSetForPointer(BaseValue, AliasAnalysis::UnknownSize,
277 Inst.getMetadata(LLVMContext::MD_tbaa));
Tobias Grosserfff5adc2011-11-10 13:21:43 +0000278
279 // INVALID triggers an assertion in verifying mode, if it detects that a SCoP
280 // was detected by SCoP detection and that this SCoP was invalidated by a pass
281 // that stated it would preserve the SCoPs.
282 // We disable this check as the independent blocks pass may create memory
283 // references which seem to alias, if -basicaa is not available. They actually
284 // do not, but as we can not proof this without -basicaa we would fail. We
285 // disable this check to not cause irrelevant verification failures.
Tobias Grosser428b3e42013-02-04 15:46:25 +0000286 if (!AS.isMustAlias() && !IgnoreAliasing) {
287 std::string Message;
288 raw_string_ostream OS(Message);
289
290 OS << "Possible aliasing: ";
291
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000292 std::vector<Value *> Pointers;
Tobias Grosser428b3e42013-02-04 15:46:25 +0000293
294 for (AliasSet::iterator AI = AS.begin(), AE = AS.end(); AI != AE; ++AI)
295 Pointers.push_back(AI.getPointer());
296
297 std::sort(Pointers.begin(), Pointers.end());
298
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000299 for (std::vector<Value *>::iterator PI = Pointers.begin(),
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000300 PE = Pointers.end();
301 ;) {
Tobias Grosser428b3e42013-02-04 15:46:25 +0000302 Value *V = *PI;
303
304 if (V->getName().size() == 0)
305 OS << "\"" << *V << "\"";
306 else
307 OS << "\"" << V->getName() << "\"";
308
309 ++PI;
310
311 if (PI != PE)
312 OS << ", ";
313 else
314 break;
315 }
316
Tobias Grosser84b81de2013-03-19 21:44:07 +0000317 INVALID_NOVERIFY(Alias, OS.str());
Tobias Grosser428b3e42013-02-04 15:46:25 +0000318 }
Tobias Grosser75805372011-04-29 06:27:02 +0000319
320 return true;
321}
322
Tobias Grossere602a072013-05-07 07:30:56 +0000323bool ScopDetection::hasScalarDependency(Instruction &Inst,
324 Region &RefRegion) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000325 for (Instruction::use_iterator UI = Inst.use_begin(), UE = Inst.use_end();
326 UI != UE; ++UI)
327 if (Instruction *Use = dyn_cast<Instruction>(*UI))
328 if (!RefRegion.contains(Use->getParent())) {
329 // DirtyHack 1: PHINode user outside the Scop is not allow, if this
330 // PHINode is induction variable, the scalar to array transform may
331 // break it and introduce a non-indvar PHINode, which is not allow in
332 // Scop.
333 // This can be fix by:
334 // Introduce a IndependentBlockPrepare pass, which translate all
335 // PHINodes not in Scop to array.
336 // The IndependentBlockPrepare pass can also split the entry block of
337 // the function to hold the alloca instruction created by scalar to
338 // array. and split the exit block of the Scop so the new create load
339 // instruction for escape users will not break other Scops.
340 if (isa<PHINode>(Use))
341 return true;
342 }
343
344 return false;
345}
346
347bool ScopDetection::isValidInstruction(Instruction &Inst,
348 DetectionContext &Context) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000349 if (PHINode *PN = dyn_cast<PHINode>(&Inst))
Tobias Grosserecfe21b2013-03-20 18:03:18 +0000350 if (!canSynthesize(PN, LI, SE, &Context.CurRegion)) {
351 if (SCEVCodegen)
352 INVALID(IndVar,
353 "SCEV of PHI node refers to SSA names in region: " << Inst);
354 else
355 INVALID(IndVar, "Non canonical PHI node: " << Inst);
356 }
Tobias Grosser75805372011-04-29 06:27:02 +0000357
358 // Scalar dependencies are not allowed.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000359 if (hasScalarDependency(Inst, Context.CurRegion))
360 INVALID(Scalar, "Scalar dependency found: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000361
362 // We only check the call instruction but not invoke instruction.
363 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
364 if (isValidCallInst(*CI))
365 return true;
366
Tobias Grosserb43ba822011-10-08 00:49:30 +0000367 INVALID(FuncCall, "Call instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000368 }
369
370 if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) {
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000371 if (isa<AllocaInst>(Inst))
Tobias Grosserb43ba822011-10-08 00:49:30 +0000372 INVALID(Other, "Alloca instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000373
374 return true;
375 }
376
377 // Check the access function.
378 if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
379 return isValidMemoryAccess(Inst, Context);
380
381 // We do not know this instruction, therefore we assume it is invalid.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000382 INVALID(Other, "Unknown instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000383}
384
385bool ScopDetection::isValidBasicBlock(BasicBlock &BB,
386 DetectionContext &Context) const {
387 if (!isValidCFG(BB, Context))
388 return false;
389
390 // Check all instructions, except the terminator instruction.
391 for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
392 if (!isValidInstruction(*I, Context))
393 return false;
394
395 Loop *L = LI->getLoopFor(&BB);
396 if (L && L->getHeader() == &BB && !isValidLoop(L, Context))
397 return false;
398
399 return true;
400}
401
402bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
Tobias Grosser826b2af2013-03-21 16:14:50 +0000403 if (!SCEVCodegen) {
404 // If code generation is not in scev based mode, we need to ensure that
405 // each loop has a canonical induction variable.
406 PHINode *IndVar = L->getCanonicalInductionVariable();
407 if (!IndVar)
408 INVALID(IndVar,
409 "No canonical IV at loop header: " << L->getHeader()->getName());
410 }
Tobias Grosser75805372011-04-29 06:27:02 +0000411
412 // Is the loop count affine?
413 const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
Tobias Grosser120db6b2011-11-07 12:58:54 +0000414 if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE))
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000415 INVALID(LoopBound,
416 "Non affine loop bound '"
Tobias Grosserd7e58642013-04-10 06:55:45 +0000417 << *LoopCount << "' in loop: " << L->getHeader()->getName());
Tobias Grosser75805372011-04-29 06:27:02 +0000418
419 return true;
420}
421
422Region *ScopDetection::expandRegion(Region &R) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000423 // Initial no valid region was found (greater than R)
424 Region *LastValidRegion = NULL;
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000425 Region *ExpandedRegion = R.getExpandedRegion();
Tobias Grosser75805372011-04-29 06:27:02 +0000426
427 DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
428
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000429 while (ExpandedRegion) {
430 DetectionContext Context(*ExpandedRegion, *AA, false /* verifying */);
431 DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
Tobias Grosser75805372011-04-29 06:27:02 +0000432
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000433 // Check the exit first (cheap)
Tobias Grosser75805372011-04-29 06:27:02 +0000434 if (isValidExit(Context)) {
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000435 // If the exit is valid check all blocks
436 // - if true, a valid region was found => store it + keep expanding
437 // - if false, .tbd. => stop (should this really end the loop?)
438 if (!allBlocksValid(Context))
439 break;
Tobias Grosser75805372011-04-29 06:27:02 +0000440
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000441 // Delete unnecessary regions (allocated by getExpandedRegion)
442 if (LastValidRegion)
443 delete LastValidRegion;
444
Tobias Grosserd7e58642013-04-10 06:55:45 +0000445 // Store this region, because it is the greatest valid (encountered so
446 // far).
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000447 LastValidRegion = ExpandedRegion;
448
449 // Create and test the next greater region (if any)
450 ExpandedRegion = ExpandedRegion->getExpandedRegion();
451
452 } else {
453 // Create and test the next greater region (if any)
454 Region *TmpRegion = ExpandedRegion->getExpandedRegion();
455
456 // Delete unnecessary regions (allocated by getExpandedRegion)
457 delete ExpandedRegion;
458
459 ExpandedRegion = TmpRegion;
Tobias Grosser75805372011-04-29 06:27:02 +0000460 }
Tobias Grosser75805372011-04-29 06:27:02 +0000461 }
462
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000463 DEBUG(if (LastValidRegion)
Tobias Grosserd7e58642013-04-10 06:55:45 +0000464 dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n";
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000465 else dbgs() << "\tExpanding " << R.getNameStr() << " failed\n";);
Tobias Grosser75805372011-04-29 06:27:02 +0000466
Hongbin Zhenged986ab2012-04-07 15:14:28 +0000467 return LastValidRegion;
Tobias Grosser75805372011-04-29 06:27:02 +0000468}
469
Tobias Grosser75805372011-04-29 06:27:02 +0000470void ScopDetection::findScops(Region &R) {
471 DetectionContext Context(R, *AA, false /*verifying*/);
472
Tobias Grosser4eb73812011-11-10 12:45:15 +0000473 LastFailure = "";
474
Tobias Grosser75805372011-04-29 06:27:02 +0000475 if (isValidRegion(Context)) {
476 ++ValidRegion;
477 ValidRegions.insert(&R);
478 return;
479 }
480
Tobias Grosser4f129a62011-10-08 00:30:55 +0000481 InvalidRegions[&R] = LastFailure;
482
Tobias Grosser75805372011-04-29 06:27:02 +0000483 for (Region::iterator I = R.begin(), E = R.end(); I != E; ++I)
484 findScops(**I);
485
486 // Try to expand regions.
487 //
488 // As the region tree normally only contains canonical regions, non canonical
489 // regions that form a Scop are not found. Therefore, those non canonical
490 // regions are checked by expanding the canonical ones.
491
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000492 std::vector<Region *> ToExpand;
Tobias Grosser75805372011-04-29 06:27:02 +0000493
494 for (Region::iterator I = R.begin(), E = R.end(); I != E; ++I)
495 ToExpand.push_back(*I);
496
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000497 for (std::vector<Region *>::iterator RI = ToExpand.begin(),
498 RE = ToExpand.end();
499 RI != RE; ++RI) {
Tobias Grosser75805372011-04-29 06:27:02 +0000500 Region *CurrentRegion = *RI;
501
502 // Skip invalid regions. Regions may become invalid, if they are element of
503 // an already expanded region.
504 if (ValidRegions.find(CurrentRegion) == ValidRegions.end())
505 continue;
506
507 Region *ExpandedR = expandRegion(*CurrentRegion);
508
509 if (!ExpandedR)
510 continue;
511
512 R.addSubRegion(ExpandedR, true);
513 ValidRegions.insert(ExpandedR);
514 ValidRegions.erase(CurrentRegion);
515
516 for (Region::iterator I = ExpandedR->begin(), E = ExpandedR->end(); I != E;
517 ++I)
518 ValidRegions.erase(*I);
519 }
520}
521
522bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
523 Region &R = Context.CurRegion;
524
525 for (Region::block_iterator I = R.block_begin(), E = R.block_end(); I != E;
526 ++I)
Chandler Carruth30dfdfc2012-05-04 21:24:27 +0000527 if (!isValidBasicBlock(**I, Context))
Tobias Grosser75805372011-04-29 06:27:02 +0000528 return false;
529
530 return true;
531}
532
533bool ScopDetection::isValidExit(DetectionContext &Context) const {
534 Region &R = Context.CurRegion;
535
536 // PHI nodes are not allowed in the exit basic block.
537 if (BasicBlock *Exit = R.getExit()) {
538 BasicBlock::iterator I = Exit->begin();
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000539 if (I != Exit->end() && isa<PHINode>(*I))
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000540 INVALID(Other, "PHI node in exit BB");
Tobias Grosser75805372011-04-29 06:27:02 +0000541 }
542
543 return true;
544}
545
546bool ScopDetection::isValidRegion(DetectionContext &Context) const {
547 Region &R = Context.CurRegion;
548
549 DEBUG(dbgs() << "Checking region: " << R.getNameStr() << "\n\t");
550
551 // The toplevel region is no valid region.
Tobias Grosseraeabcf22013-04-02 06:41:48 +0000552 if (R.isTopLevelRegion()) {
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000553 DEBUG(dbgs() << "Top level region is invalid"; dbgs() << "\n");
Tobias Grosser75805372011-04-29 06:27:02 +0000554 return false;
555 }
556
Tobias Grossere602a072013-05-07 07:30:56 +0000557 if (!R.getEnteringBlock()) {
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000558 Loop *L = LI->getLoopFor(R.getEntry());
559 if (L && !L->isLoopSimplifyForm())
560 INVALID(SimpleLoop, "Loop not in simplify form is invalid!");
561 }
562
Tobias Grosserd654c252012-04-10 18:12:19 +0000563 // SCoP cannot contain the entry block of the function, because we need
Tobias Grosser75805372011-04-29 06:27:02 +0000564 // to insert alloca instruction there when translate scalar to array.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000565 if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock()))
566 INVALID(Other, "Region containing entry block of function is invalid!");
Tobias Grosser75805372011-04-29 06:27:02 +0000567
Hongbin Zheng94868e62012-04-07 12:29:17 +0000568 if (!isValidExit(Context))
Tobias Grosser75805372011-04-29 06:27:02 +0000569 return false;
570
Hongbin Zheng94868e62012-04-07 12:29:17 +0000571 if (!allBlocksValid(Context))
Tobias Grosser75805372011-04-29 06:27:02 +0000572 return false;
573
574 DEBUG(dbgs() << "OK\n");
575 return true;
576}
577
578bool ScopDetection::isValidFunction(llvm::Function &F) {
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000579 return !InvalidFunctions.count(&F);
Tobias Grosser75805372011-04-29 06:27:02 +0000580}
581
Tobias Grosser531891e2012-11-01 16:45:20 +0000582void ScopDetection::getDebugLocation(const Region *R, unsigned &LineBegin,
583 unsigned &LineEnd, std::string &FileName) {
584 LineBegin = -1;
585 LineEnd = 0;
586
587 for (Region::const_block_iterator RI = R->block_begin(), RE = R->block_end();
588 RI != RE; ++RI)
589 for (BasicBlock::iterator BI = (*RI)->begin(), BE = (*RI)->end(); BI != BE;
590 ++BI) {
591 DebugLoc DL = BI->getDebugLoc();
592 if (DL.isUnknown())
593 continue;
594
595 DIScope Scope(DL.getScope(BI->getContext()));
596
597 if (FileName.empty())
598 FileName = Scope.getFilename();
599
600 unsigned NewLine = DL.getLine();
601
602 LineBegin = std::min(LineBegin, NewLine);
603 LineEnd = std::max(LineEnd, NewLine);
604 break;
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000605 }
Tobias Grosser531891e2012-11-01 16:45:20 +0000606}
607
Tobias Grosserb2863ca2013-03-04 19:49:51 +0000608void ScopDetection::printLocations(llvm::Function &F) {
609 int NumberOfScops = std::distance(begin(), end());
610
611 if (NumberOfScops)
612 outs() << ":: Static control regions in " << F.getName() << "\n";
613
Tobias Grosser531891e2012-11-01 16:45:20 +0000614 for (iterator RI = begin(), RE = end(); RI != RE; ++RI) {
615 unsigned LineEntry, LineExit;
616 std::string FileName;
617
618 getDebugLocation(*RI, LineEntry, LineExit, FileName);
619
620 if (FileName.empty()) {
621 outs() << "Scop detected at unknown location. Compile with debug info "
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000622 "(-g) to get more precise information. \n";
Tobias Grosser531891e2012-11-01 16:45:20 +0000623 return;
624 }
625
Tobias Grosserb2863ca2013-03-04 19:49:51 +0000626 outs() << FileName << ":" << LineEntry
627 << ": Start of static control region\n";
628 outs() << FileName << ":" << LineExit << ": End of static control region\n";
Tobias Grosser531891e2012-11-01 16:45:20 +0000629 }
630}
631
Tobias Grosser75805372011-04-29 06:27:02 +0000632bool ScopDetection::runOnFunction(llvm::Function &F) {
Sebastian Pop8fe6d112013-05-30 17:47:32 +0000633 LI = &getAnalysis<LoopInfo>();
634 if (!DetectScopsWithoutLoops && LI->empty())
635 return false;
636
Tobias Grosser75805372011-04-29 06:27:02 +0000637 AA = &getAnalysis<AliasAnalysis>();
638 SE = &getAnalysis<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +0000639 RI = &getAnalysis<RegionInfo>();
640 Region *TopRegion = RI->getTopLevelRegion();
641
Tobias Grosser2ff87232011-10-23 11:17:06 +0000642 releaseMemory();
643
Tobias Grosser29ee0b12011-11-17 14:52:36 +0000644 if (OnlyFunction != "" && F.getName() != OnlyFunction)
Tobias Grosser2ff87232011-10-23 11:17:06 +0000645 return false;
646
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000647 if (!isValidFunction(F))
Tobias Grosser75805372011-04-29 06:27:02 +0000648 return false;
649
650 findScops(*TopRegion);
Tobias Grosser531891e2012-11-01 16:45:20 +0000651
652 if (ReportLevel >= 1)
Tobias Grosserb2863ca2013-03-04 19:49:51 +0000653 printLocations(F);
Tobias Grosser531891e2012-11-01 16:45:20 +0000654
Tobias Grosser75805372011-04-29 06:27:02 +0000655 return false;
656}
657
Tobias Grosser75805372011-04-29 06:27:02 +0000658void polly::ScopDetection::verifyRegion(const Region &R) const {
659 assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
Tobias Grosser0d1eee32013-02-05 11:56:05 +0000660 DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/);
Tobias Grosser75805372011-04-29 06:27:02 +0000661 isValidRegion(Context);
662}
663
664void polly::ScopDetection::verifyAnalysis() const {
665 for (RegionSet::const_iterator I = ValidRegions.begin(),
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000666 E = ValidRegions.end();
667 I != E; ++I)
Tobias Grosser75805372011-04-29 06:27:02 +0000668 verifyRegion(**I);
669}
670
671void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
672 AU.addRequired<DominatorTree>();
673 AU.addRequired<PostDominatorTree>();
674 AU.addRequired<LoopInfo>();
675 AU.addRequired<ScalarEvolution>();
676 // We also need AA and RegionInfo when we are verifying analysis.
677 AU.addRequiredTransitive<AliasAnalysis>();
678 AU.addRequiredTransitive<RegionInfo>();
679 AU.setPreservesAll();
680}
681
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000682void ScopDetection::print(raw_ostream &OS, const Module *) const {
Tobias Grosser75805372011-04-29 06:27:02 +0000683 for (RegionSet::const_iterator I = ValidRegions.begin(),
Tobias Grosseraf3c00b82013-02-05 09:40:22 +0000684 E = ValidRegions.end();
685 I != E; ++I)
Tobias Grosser75805372011-04-29 06:27:02 +0000686 OS << "Valid Region for Scop: " << (*I)->getNameStr() << '\n';
687
688 OS << "\n";
689}
690
691void ScopDetection::releaseMemory() {
692 ValidRegions.clear();
Tobias Grosser4f129a62011-10-08 00:30:55 +0000693 InvalidRegions.clear();
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000694 // Do not clear the invalid function set.
Tobias Grosser75805372011-04-29 06:27:02 +0000695}
696
697char ScopDetection::ID = 0;
698
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000699Pass *polly::createScopDetectionPass() { return new ScopDetection(); }
700
Tobias Grosser73600b82011-10-08 00:30:40 +0000701INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect",
702 "Polly - Detect static control parts (SCoPs)", false,
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000703 false);
704INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
705INITIALIZE_PASS_DEPENDENCY(DominatorTree);
706INITIALIZE_PASS_DEPENDENCY(LoopInfo);
707INITIALIZE_PASS_DEPENDENCY(PostDominatorTree);
708INITIALIZE_PASS_DEPENDENCY(RegionInfo);
709INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
Tobias Grosser73600b82011-10-08 00:30:40 +0000710INITIALIZE_PASS_END(ScopDetection, "polly-detect",
711 "Polly - Detect static control parts (SCoPs)", false, false)