blob: 883fe2ceafca72174fffda4237114c808bcaee8e [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
47#include "polly/ScopDetection.h"
48
49#include "polly/LinkAllPasses.h"
50#include "polly/Support/ScopHelper.h"
51#include "polly/Support/AffineSCEVIterator.h"
52
53#include "llvm/LLVMContext.h"
54#include "llvm/ADT/Statistic.h"
55#include "llvm/Analysis/AliasAnalysis.h"
56#include "llvm/Analysis/RegionIterator.h"
57#include "llvm/Support/CommandLine.h"
58#include "llvm/Assembly/Writer.h"
59
60#define DEBUG_TYPE "polly-detect"
61#include "llvm/Support/Debug.h"
62
63using namespace llvm;
64using namespace polly;
65
Tobias Grosser2ff87232011-10-23 11:17:06 +000066static cl::opt<std::string>
67OnlyFunction("polly-detect-only",
68 cl::desc("Only detect scops in function"), cl::Hidden,
69 cl::value_desc("The function name to detect scops in"),
70 cl::ValueRequired, cl::init(""));
71
72
Tobias Grosser75805372011-04-29 06:27:02 +000073//===----------------------------------------------------------------------===//
74// Statistics.
75
76STATISTIC(ValidRegion, "Number of regions that a valid part of Scop");
77
78#define BADSCOP_STAT(NAME, DESC) STATISTIC(Bad##NAME##ForScop, \
79 "Number of bad regions for Scop: "\
80 DESC)
81
82#define STATSCOP(NAME); assert(!Context.Verifying && #NAME); \
83 if (!Context.Verifying) ++Bad##NAME##ForScop;
84
Tobias Grosserc4a0bd12011-10-08 00:30:48 +000085#define INVALID(NAME, MESSAGE) \
86 do { \
Tobias Grosser4f129a62011-10-08 00:30:55 +000087 std::string Buf; \
88 raw_string_ostream fmt(Buf); \
89 fmt << MESSAGE; \
90 fmt.flush(); \
91 LastFailure = Buf; \
Tobias Grosserc4a0bd12011-10-08 00:30:48 +000092 DEBUG(dbgs() << MESSAGE); \
93 DEBUG(dbgs() << "\n"); \
94 STATSCOP(NAME); \
95 return false; \
96 } while (0);
97
98
Tobias Grosser75805372011-04-29 06:27:02 +000099BADSCOP_STAT(CFG, "CFG too complex");
100BADSCOP_STAT(IndVar, "Non canonical induction variable in loop");
101BADSCOP_STAT(LoopBound, "Loop bounds can not be computed");
102BADSCOP_STAT(FuncCall, "Function call with side effects appeared");
103BADSCOP_STAT(AffFunc, "Expression not affine");
104BADSCOP_STAT(Scalar, "Found scalar dependency");
105BADSCOP_STAT(Alias, "Found base address alias");
106BADSCOP_STAT(SimpleRegion, "Region not simple");
107BADSCOP_STAT(Other, "Others");
108
109//===----------------------------------------------------------------------===//
110// ScopDetection.
111
Tobias Grosser3fb49922011-11-02 21:40:08 +0000112namespace SCEVType {
113 enum TYPE {INT, PARAM, IV, INVALID};
114}
115
Tobias Grossereadc4282011-11-07 12:58:41 +0000116struct ValidatorResult {
117 SCEVType::TYPE type;
118
119 ValidatorResult() : type(SCEVType::INVALID) {};
120
121 ValidatorResult(const ValidatorResult &vres) {
122 type = vres.type;
123 };
124
125 ValidatorResult(SCEVType::TYPE type) : type(type) {};
126
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000127 bool isConstant() {
128 return type == SCEVType::INT || type == SCEVType::PARAM;
129 }
130
131 bool isValid() {
132 return type != SCEVType::INVALID;
133 }
134
135 bool isIV() {
136 return type == SCEVType::IV;
137 }
138
139 bool isINT() {
140 return type == SCEVType::INT;
141 }
Tobias Grossereadc4282011-11-07 12:58:41 +0000142};
143
Tobias Grosser3fb49922011-11-02 21:40:08 +0000144/// Check if a SCEV is valid in a SCoP.
Tobias Grossereadc4282011-11-07 12:58:41 +0000145struct SCEVValidator
146 : public SCEVVisitor<SCEVValidator, struct ValidatorResult> {
Tobias Grosser3fb49922011-11-02 21:40:08 +0000147private:
148 const Region *R;
149 ScalarEvolution &SE;
Tobias Grosser76164672011-11-03 21:03:18 +0000150 Value **BaseAddress;
Tobias Grosser3fb49922011-11-02 21:40:08 +0000151
152public:
153 static bool isValid(const Region *R, const SCEV *Scev,
154 ScalarEvolution &SE,
Tobias Grosser76164672011-11-03 21:03:18 +0000155 Value **BaseAddress = NULL) {
Tobias Grosser3fb49922011-11-02 21:40:08 +0000156 if (isa<SCEVCouldNotCompute>(Scev))
157 return false;
158
Tobias Grosser76164672011-11-03 21:03:18 +0000159 if (BaseAddress)
160 *BaseAddress = NULL;
161
Tobias Grosser3fb49922011-11-02 21:40:08 +0000162 SCEVValidator Validator(R, SE, BaseAddress);
Tobias Grossereadc4282011-11-07 12:58:41 +0000163 ValidatorResult Result = Validator.visit(Scev);
164
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000165 return Result.isValid();
Tobias Grosser3fb49922011-11-02 21:40:08 +0000166 }
167
168 SCEVValidator(const Region *R, ScalarEvolution &SE,
Tobias Grosser76164672011-11-03 21:03:18 +0000169 Value **BaseAddress) : R(R), SE(SE),
Tobias Grosser3fb49922011-11-02 21:40:08 +0000170 BaseAddress(BaseAddress) {};
171
Tobias Grossereadc4282011-11-07 12:58:41 +0000172 struct ValidatorResult visitConstant(const SCEVConstant *Constant) {
173 return ValidatorResult(SCEVType::INT);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000174 }
175
Tobias Grossereadc4282011-11-07 12:58:41 +0000176 struct ValidatorResult visitTruncateExpr(const SCEVTruncateExpr* Expr) {
177 ValidatorResult Op = visit(Expr->getOperand());
Tobias Grosser3fb49922011-11-02 21:40:08 +0000178
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000179 // We currently do not represent a truncate expression as an affine
180 // expression. If it is constant during Scop execution, we treat it as a
181 // parameter, otherwise we bail out.
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000182 if (Op.isConstant())
Tobias Grossereadc4282011-11-07 12:58:41 +0000183 return ValidatorResult(SCEVType::PARAM);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000184
Tobias Grossereadc4282011-11-07 12:58:41 +0000185 return ValidatorResult (SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000186 }
187
Tobias Grossereadc4282011-11-07 12:58:41 +0000188 struct ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr * Expr) {
189 ValidatorResult Op = visit(Expr->getOperand());
Tobias Grosser3fb49922011-11-02 21:40:08 +0000190
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000191 // We currently do not represent a zero extend expression as an affine
192 // expression. If it is constant during Scop execution, we treat it as a
193 // parameter, otherwise we bail out.
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000194 if (Op.isConstant())
Tobias Grossereadc4282011-11-07 12:58:41 +0000195 return ValidatorResult (SCEVType::PARAM);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000196
Tobias Grossereadc4282011-11-07 12:58:41 +0000197 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000198 }
199
Tobias Grossereadc4282011-11-07 12:58:41 +0000200 struct ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr* Expr) {
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000201 // We currently allow only signed SCEV expressions. In the case of a
202 // signed value, a sign extend is a noop.
203 //
204 // TODO: Reconsider this when we add support for unsigned values.
Tobias Grosser3fb49922011-11-02 21:40:08 +0000205 return visit(Expr->getOperand());
206 }
207
Tobias Grossereadc4282011-11-07 12:58:41 +0000208 struct ValidatorResult visitAddExpr(const SCEVAddExpr* Expr) {
209 ValidatorResult Return(SCEVType::INT);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000210
211 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
Tobias Grossereadc4282011-11-07 12:58:41 +0000212 ValidatorResult Op = visit(Expr->getOperand(i));
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000213
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000214 if (!Op.isValid())
Tobias Grossereadc4282011-11-07 12:58:41 +0000215 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000216
Tobias Grossereadc4282011-11-07 12:58:41 +0000217 Return.type = std::max(Return.type, Op.type);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000218 }
219
220 // TODO: Check for NSW and NUW.
221 return Return;
222 }
223
Tobias Grossereadc4282011-11-07 12:58:41 +0000224 struct ValidatorResult visitMulExpr(const SCEVMulExpr* Expr) {
225 ValidatorResult Return(SCEVType::INT);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000226
227 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
Tobias Grossereadc4282011-11-07 12:58:41 +0000228 ValidatorResult Op = visit(Expr->getOperand(i));
Tobias Grosser3fb49922011-11-02 21:40:08 +0000229
Tobias Grossereadc4282011-11-07 12:58:41 +0000230 if (Op.type == SCEVType::INT)
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000231 continue;
232
Tobias Grossereadc4282011-11-07 12:58:41 +0000233 if (Op.type == SCEVType::INVALID || Return.type != SCEVType::INT)
234 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000235
Tobias Grossereadc4282011-11-07 12:58:41 +0000236 Return.type = Op.type;
Tobias Grosser3fb49922011-11-02 21:40:08 +0000237 }
238
239 // TODO: Check for NSW and NUW.
240 return Return;
241 }
242
Tobias Grossereadc4282011-11-07 12:58:41 +0000243 struct ValidatorResult visitUDivExpr(const SCEVUDivExpr* Expr) {
244 ValidatorResult LHS = visit(Expr->getLHS());
245 ValidatorResult RHS = visit(Expr->getRHS());
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000246
247 // We currently do not represent a unsigned devision as an affine
248 // expression. If the division is constant during Scop execution we treat it
249 // as a parameter, otherwise we bail out.
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000250 if (LHS.isConstant() && RHS.isConstant())
Tobias Grossereadc4282011-11-07 12:58:41 +0000251 return ValidatorResult(SCEVType::PARAM);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000252
Tobias Grossereadc4282011-11-07 12:58:41 +0000253 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000254 }
255
Tobias Grossereadc4282011-11-07 12:58:41 +0000256 struct ValidatorResult visitAddRecExpr(const SCEVAddRecExpr* Expr) {
Tobias Grosser3fb49922011-11-02 21:40:08 +0000257 if (!Expr->isAffine())
Tobias Grossereadc4282011-11-07 12:58:41 +0000258 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000259
Tobias Grossereadc4282011-11-07 12:58:41 +0000260 ValidatorResult Start = visit(Expr->getStart());
261 ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000262
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000263 if (!Start.isValid() || !Recurrence.isValid() || Recurrence.isIV())
Tobias Grossereadc4282011-11-07 12:58:41 +0000264 return ValidatorResult(SCEVType::INVALID);
265
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000266
267 if (!R->contains(Expr->getLoop())) {
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000268 if (Start.isIV())
Tobias Grossereadc4282011-11-07 12:58:41 +0000269 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000270 else
Tobias Grossereadc4282011-11-07 12:58:41 +0000271 return ValidatorResult(SCEVType::PARAM);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000272 }
273
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000274 if (!Recurrence.isINT())
Tobias Grossereadc4282011-11-07 12:58:41 +0000275 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000276
Tobias Grossereadc4282011-11-07 12:58:41 +0000277 return ValidatorResult(SCEVType::IV);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000278 }
279
Tobias Grossereadc4282011-11-07 12:58:41 +0000280 struct ValidatorResult visitSMaxExpr(const SCEVSMaxExpr* Expr) {
281 ValidatorResult Return(SCEVType::INT);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000282
283 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
Tobias Grossereadc4282011-11-07 12:58:41 +0000284 ValidatorResult Op = visit(Expr->getOperand(i));
Tobias Grosser3fb49922011-11-02 21:40:08 +0000285
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000286 if (!Op.isValid())
Tobias Grossereadc4282011-11-07 12:58:41 +0000287 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000288
Tobias Grossereadc4282011-11-07 12:58:41 +0000289 Return.type = std::max(Return.type, Op.type);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000290 }
291
292 return Return;
293 }
294
Tobias Grossereadc4282011-11-07 12:58:41 +0000295 struct ValidatorResult visitUMaxExpr(const SCEVUMaxExpr* Expr) {
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000296 // We do not support unsigned operations. If 'Expr' is constant during Scop
297 // execution we treat this as a parameter, otherwise we bail out.
Tobias Grosser3fb49922011-11-02 21:40:08 +0000298 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
Tobias Grossereadc4282011-11-07 12:58:41 +0000299 ValidatorResult Op = visit(Expr->getOperand(i));
Tobias Grosser3fb49922011-11-02 21:40:08 +0000300
Tobias Grosser60e85cb2011-11-07 12:58:46 +0000301 if (!Op.isConstant())
Tobias Grossereadc4282011-11-07 12:58:41 +0000302 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000303 }
304
Tobias Grossereadc4282011-11-07 12:58:41 +0000305 return ValidatorResult(SCEVType::PARAM);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000306 }
307
Tobias Grossereadc4282011-11-07 12:58:41 +0000308 ValidatorResult visitUnknown(const SCEVUnknown* Expr) {
Tobias Grosser76164672011-11-03 21:03:18 +0000309 Value *V = Expr->getValue();
310
311 if (isa<UndefValue>(V))
Tobias Grossereadc4282011-11-07 12:58:41 +0000312 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser76164672011-11-03 21:03:18 +0000313
314 if (BaseAddress) {
315 if (*BaseAddress)
Tobias Grossereadc4282011-11-07 12:58:41 +0000316 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser76164672011-11-03 21:03:18 +0000317 else
318 *BaseAddress = V;
319 }
320
Tobias Grosserad96c4b2011-11-03 21:03:01 +0000321 if (Instruction *I = dyn_cast<Instruction>(Expr->getValue()))
322 if (R->contains(I))
Tobias Grossereadc4282011-11-07 12:58:41 +0000323 return ValidatorResult(SCEVType::INVALID);
Tobias Grosser2d0b1f92011-11-04 10:08:08 +0000324
Tobias Grossereadc4282011-11-07 12:58:41 +0000325 if (BaseAddress)
326 return ValidatorResult(SCEVType::PARAM);
327 else
328 return ValidatorResult(SCEVType::PARAM);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000329 }
330};
331
Tobias Grosser75805372011-04-29 06:27:02 +0000332bool ScopDetection::isMaxRegionInScop(const Region &R) const {
333 // The Region is valid only if it could be found in the set.
334 return ValidRegions.count(&R);
335}
336
Tobias Grosser4f129a62011-10-08 00:30:55 +0000337std::string ScopDetection::regionIsInvalidBecause(const Region *R) const {
338 if (!InvalidRegions.count(R))
339 return "";
340
341 return InvalidRegions.find(R)->second;
342}
343
344
Tobias Grosser75805372011-04-29 06:27:02 +0000345bool ScopDetection::isValidAffineFunction(const SCEV *S, Region &RefRegion,
346 Value **BasePtr) const {
347 assert(S && "S must not be null!");
348 bool isMemoryAccess = (BasePtr != 0);
349 if (isMemoryAccess) *BasePtr = 0;
350 DEBUG(dbgs() << "Checking " << *S << " ... ");
351
352 if (isa<SCEVCouldNotCompute>(S)) {
353 DEBUG(dbgs() << "Non Affine: SCEV could not be computed\n");
354 return false;
355 }
356
357 for (AffineSCEVIterator I = affine_begin(S, SE), E = affine_end(); I != E;
358 ++I) {
359 // The constant part must be a SCEVConstant.
360 // TODO: support sizeof in coefficient.
361 if (!isa<SCEVConstant>(I->second)) {
362 DEBUG(dbgs() << "Non Affine: Right hand side is not constant\n");
363 return false;
364 }
365
366 const SCEV *Var = I->first;
367
368 // A constant offset is affine.
369 if(isa<SCEVConstant>(Var))
370 continue;
371
372 // Memory accesses are allowed to have a base pointer.
373 if (Var->getType()->isPointerTy()) {
374 if (!isMemoryAccess) {
375 DEBUG(dbgs() << "Non Affine: Pointer in non memory access\n");
376 return false;
377 }
378
379 assert(I->second->isOne() && "Only one as pointer coefficient allowed.\n");
380 const SCEVUnknown *BaseAddr = dyn_cast<SCEVUnknown>(Var);
381
382 if (!BaseAddr || isa<UndefValue>(BaseAddr->getValue())){
383 DEBUG(dbgs() << "Cannot handle base: " << *Var << "\n");
384 return false;
385 }
386
387 // BaseAddr must be invariant in Scop.
388 if (!isParameter(BaseAddr, RefRegion, *LI, *SE)) {
389 DEBUG(dbgs() << "Non Affine: Base address not invariant in SCoP\n");
390 return false;
391 }
392
393 assert(*BasePtr == 0 && "Found second base pointer.\n");
394 *BasePtr = BaseAddr->getValue();
395 continue;
396 }
397
398 if (isParameter(Var, RefRegion, *LI, *SE)
399 || isIndVar(Var, RefRegion, *LI, *SE))
400 continue;
401
402 DEBUG(dbgs() << "Non Affine: " ;
403 Var->print(dbgs());
404 dbgs() << " is neither parameter nor induction variable\n");
405 return false;
406 }
407
408 DEBUG(dbgs() << " is affine.\n");
409 return !isMemoryAccess || (*BasePtr != 0);
410}
411
412bool ScopDetection::isValidCFG(BasicBlock &BB, DetectionContext &Context) const
413{
414 Region &RefRegion = Context.CurRegion;
415 TerminatorInst *TI = BB.getTerminator();
416
417 // Return instructions are only valid if the region is the top level region.
418 if (isa<ReturnInst>(TI) && !RefRegion.getExit() && TI->getNumOperands() == 0)
419 return true;
420
421 BranchInst *Br = dyn_cast<BranchInst>(TI);
422
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000423 if (!Br)
424 INVALID(CFG, "Non branch instruction terminates BB: " + BB.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000425
426 if (Br->isUnconditional()) return true;
427
428 Value *Condition = Br->getCondition();
429
430 // UndefValue is not allowed as condition.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000431 if (isa<UndefValue>(Condition))
432 INVALID(AffFunc, "Condition based on 'undef' value in BB: "
433 + BB.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000434
435 // Only Constant and ICmpInst are allowed as condition.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000436 if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition)))
437 INVALID(AffFunc, "Condition in BB '" + BB.getNameStr() + "' neither "
438 "constant nor an icmp instruction");
Tobias Grosser75805372011-04-29 06:27:02 +0000439
440 // Allow perfectly nested conditions.
441 assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
442
443 if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
444 // Unsigned comparisons are not allowed. They trigger overflow problems
445 // in the code generation.
446 //
447 // TODO: This is not sufficient and just hides bugs. However it does pretty
448 // well.
449 if(ICmp->isUnsigned())
450 return false;
451
452 // Are both operands of the ICmp affine?
453 if (isa<UndefValue>(ICmp->getOperand(0))
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000454 || isa<UndefValue>(ICmp->getOperand(1)))
455 INVALID(AffFunc, "undef operand in branch at BB: " + BB.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000456
457 const SCEV *ScevLHS = SE->getSCEV(ICmp->getOperand(0));
458 const SCEV *ScevRHS = SE->getSCEV(ICmp->getOperand(1));
459
Tobias Grosser2fea5c62011-11-03 21:03:14 +0000460 bool affineLHS = SCEVValidator::isValid(&Context.CurRegion, ScevLHS, *SE);
461 bool affineRHS = SCEVValidator::isValid(&Context.CurRegion, ScevRHS, *SE);
Tobias Grosser75805372011-04-29 06:27:02 +0000462
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000463 if (!affineLHS || !affineRHS)
464 INVALID(AffFunc, "Non affine branch in BB: " + BB.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000465 }
466
467 // Allow loop exit conditions.
468 Loop *L = LI->getLoopFor(&BB);
469 if (L && L->getExitingBlock() == &BB)
470 return true;
471
472 // Allow perfectly nested conditions.
473 Region *R = RI->getRegionFor(&BB);
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000474 if (R->getEntry() != &BB)
475 INVALID(CFG, "Not well structured condition at BB: " + BB.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000476
477 return true;
478}
479
480bool ScopDetection::isValidCallInst(CallInst &CI) {
481 if (CI.mayHaveSideEffects() || CI.doesNotReturn())
482 return false;
483
484 if (CI.doesNotAccessMemory())
485 return true;
486
487 Function *CalledFunction = CI.getCalledFunction();
488
489 // Indirect calls are not supported.
490 if (CalledFunction == 0)
491 return false;
492
493 // TODO: Intrinsics.
494 return false;
495}
496
497bool ScopDetection::isValidMemoryAccess(Instruction &Inst,
498 DetectionContext &Context) const {
499 Value *Ptr = getPointerOperand(Inst), *BasePtr;
500 const SCEV *AccessFunction = SE->getSCEV(Ptr);
501
Tobias Grosser76164672011-11-03 21:03:18 +0000502 if (!SCEVValidator::isValid(&Context.CurRegion, AccessFunction, *SE,
503 &BasePtr))
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000504 INVALID(AffFunc, "Bad memory address " << *AccessFunction);
Tobias Grosser75805372011-04-29 06:27:02 +0000505
Tobias Grosser76164672011-11-03 21:03:18 +0000506 // FIXME: Also check with isValidAffineFunction, as for the moment it is
507 // protecting us to fail because of not supported features in TempScop.
508 // As soon as TempScop is fixed, this needs to be removed.
509 if (!isValidAffineFunction(AccessFunction, Context.CurRegion, &BasePtr))
510 INVALID(AffFunc, "Access not supported in TempScop" << *AccessFunction);
511
Tobias Grosser75805372011-04-29 06:27:02 +0000512 // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions
513 // created by IndependentBlocks Pass.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000514 if (isa<IntToPtrInst>(BasePtr))
Tobias Grosserb43ba822011-10-08 00:49:30 +0000515 INVALID(Other, "Find bad intToptr prt: " << *BasePtr);
Tobias Grosser75805372011-04-29 06:27:02 +0000516
517 // Check if the base pointer of the memory access does alias with
518 // any other pointer. This cannot be handled at the moment.
519 AliasSet &AS =
520 Context.AST.getAliasSetForPointer(BasePtr, AliasAnalysis::UnknownSize,
521 Inst.getMetadata(LLVMContext::MD_tbaa));
522 if (!AS.isMustAlias()) {
523 DEBUG(dbgs() << "Bad pointer alias found:" << *BasePtr << "\nAS:\n" << AS);
524
525 // STATSCOP triggers an assertion if we are in verifying mode.
526 // This is generally good to check that we do not change the SCoP after we
527 // run the SCoP detection and consequently to ensure that we can still
528 // represent that SCoP. However, in case of aliasing this does not work.
529 // The independent blocks pass may create memory references which seem to
530 // alias, if -basicaa is not available. They actually do not. As we do not
531 // not know this and we would fail here if we verify it.
532 if (!Context.Verifying) {
533 STATSCOP(Alias);
534 }
535
536 return false;
537 }
538
539 return true;
540}
541
542
543bool ScopDetection::hasScalarDependency(Instruction &Inst,
544 Region &RefRegion) const {
545 for (Instruction::use_iterator UI = Inst.use_begin(), UE = Inst.use_end();
546 UI != UE; ++UI)
547 if (Instruction *Use = dyn_cast<Instruction>(*UI))
548 if (!RefRegion.contains(Use->getParent())) {
549 // DirtyHack 1: PHINode user outside the Scop is not allow, if this
550 // PHINode is induction variable, the scalar to array transform may
551 // break it and introduce a non-indvar PHINode, which is not allow in
552 // Scop.
553 // This can be fix by:
554 // Introduce a IndependentBlockPrepare pass, which translate all
555 // PHINodes not in Scop to array.
556 // The IndependentBlockPrepare pass can also split the entry block of
557 // the function to hold the alloca instruction created by scalar to
558 // array. and split the exit block of the Scop so the new create load
559 // instruction for escape users will not break other Scops.
560 if (isa<PHINode>(Use))
561 return true;
562 }
563
564 return false;
565}
566
567bool ScopDetection::isValidInstruction(Instruction &Inst,
568 DetectionContext &Context) const {
569 // Only canonical IVs are allowed.
570 if (PHINode *PN = dyn_cast<PHINode>(&Inst))
Tobias Grosserb43ba822011-10-08 00:49:30 +0000571 if (!isIndVar(PN, LI))
572 INVALID(IndVar, "Non canonical PHI node: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000573
574 // Scalar dependencies are not allowed.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000575 if (hasScalarDependency(Inst, Context.CurRegion))
576 INVALID(Scalar, "Scalar dependency found: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000577
578 // We only check the call instruction but not invoke instruction.
579 if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
580 if (isValidCallInst(*CI))
581 return true;
582
Tobias Grosserb43ba822011-10-08 00:49:30 +0000583 INVALID(FuncCall, "Call instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000584 }
585
586 if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) {
587 // Handle cast instruction.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000588 if (isa<IntToPtrInst>(Inst) || isa<BitCastInst>(Inst))
Tobias Grosserb43ba822011-10-08 00:49:30 +0000589 INVALID(Other, "Cast instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000590
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000591 if (isa<AllocaInst>(Inst))
Tobias Grosserb43ba822011-10-08 00:49:30 +0000592 INVALID(Other, "Alloca instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000593
594 return true;
595 }
596
597 // Check the access function.
598 if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
599 return isValidMemoryAccess(Inst, Context);
600
601 // We do not know this instruction, therefore we assume it is invalid.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000602 INVALID(Other, "Unknown instruction: " << Inst);
Tobias Grosser75805372011-04-29 06:27:02 +0000603}
604
605bool ScopDetection::isValidBasicBlock(BasicBlock &BB,
606 DetectionContext &Context) const {
607 if (!isValidCFG(BB, Context))
608 return false;
609
610 // Check all instructions, except the terminator instruction.
611 for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
612 if (!isValidInstruction(*I, Context))
613 return false;
614
615 Loop *L = LI->getLoopFor(&BB);
616 if (L && L->getHeader() == &BB && !isValidLoop(L, Context))
617 return false;
618
619 return true;
620}
621
622bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
623 PHINode *IndVar = L->getCanonicalInductionVariable();
624 // No canonical induction variable.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000625 if (!IndVar)
Tobias Grosserb43ba822011-10-08 00:49:30 +0000626 INVALID(IndVar, "No canonical IV at loop header: "
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000627 << L->getHeader()->getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000628
629 // Is the loop count affine?
630 const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
Tobias Grosser3fb49922011-11-02 21:40:08 +0000631 if (!SCEVValidator::isValid(&Context.CurRegion, LoopCount, *SE))
Tobias Grosserbd54f322011-10-26 01:27:49 +0000632 INVALID(LoopBound, "Non affine loop bound '" << *LoopCount << "' in loop: "
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000633 << L->getHeader()->getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000634
635 return true;
636}
637
638Region *ScopDetection::expandRegion(Region &R) {
639 Region *CurrentRegion = &R;
640 Region *TmpRegion = R.getExpandedRegion();
641
642 DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n");
643
644 while (TmpRegion) {
645 DetectionContext Context(*TmpRegion, *AA, false /*verifying*/);
646 DEBUG(dbgs() << "\t\tTrying " << TmpRegion->getNameStr() << "\n");
647
648 if (!allBlocksValid(Context))
649 break;
650
651 if (isValidExit(Context)) {
652 if (CurrentRegion != &R)
653 delete CurrentRegion;
654
655 CurrentRegion = TmpRegion;
656 }
657
658 Region *TmpRegion2 = TmpRegion->getExpandedRegion();
659
660 if (TmpRegion != &R && TmpRegion != CurrentRegion)
661 delete TmpRegion;
662
663 TmpRegion = TmpRegion2;
664 }
665
666 if (&R == CurrentRegion)
667 return NULL;
668
669 DEBUG(dbgs() << "\tto " << CurrentRegion->getNameStr() << "\n");
670
671 return CurrentRegion;
672}
673
674
675void ScopDetection::findScops(Region &R) {
676 DetectionContext Context(R, *AA, false /*verifying*/);
677
678 if (isValidRegion(Context)) {
679 ++ValidRegion;
680 ValidRegions.insert(&R);
681 return;
682 }
683
Tobias Grosser4f129a62011-10-08 00:30:55 +0000684 InvalidRegions[&R] = LastFailure;
685
Tobias Grosser75805372011-04-29 06:27:02 +0000686 for (Region::iterator I = R.begin(), E = R.end(); I != E; ++I)
687 findScops(**I);
688
689 // Try to expand regions.
690 //
691 // As the region tree normally only contains canonical regions, non canonical
692 // regions that form a Scop are not found. Therefore, those non canonical
693 // regions are checked by expanding the canonical ones.
694
695 std::vector<Region*> ToExpand;
696
697 for (Region::iterator I = R.begin(), E = R.end(); I != E; ++I)
698 ToExpand.push_back(*I);
699
700 for (std::vector<Region*>::iterator RI = ToExpand.begin(),
701 RE = ToExpand.end(); RI != RE; ++RI) {
702 Region *CurrentRegion = *RI;
703
704 // Skip invalid regions. Regions may become invalid, if they are element of
705 // an already expanded region.
706 if (ValidRegions.find(CurrentRegion) == ValidRegions.end())
707 continue;
708
709 Region *ExpandedR = expandRegion(*CurrentRegion);
710
711 if (!ExpandedR)
712 continue;
713
714 R.addSubRegion(ExpandedR, true);
715 ValidRegions.insert(ExpandedR);
716 ValidRegions.erase(CurrentRegion);
717
718 for (Region::iterator I = ExpandedR->begin(), E = ExpandedR->end(); I != E;
719 ++I)
720 ValidRegions.erase(*I);
721 }
722}
723
724bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
725 Region &R = Context.CurRegion;
726
727 for (Region::block_iterator I = R.block_begin(), E = R.block_end(); I != E;
728 ++I)
729 if (!isValidBasicBlock(*(I->getNodeAs<BasicBlock>()), Context))
730 return false;
731
732 return true;
733}
734
735bool ScopDetection::isValidExit(DetectionContext &Context) const {
736 Region &R = Context.CurRegion;
737
738 // PHI nodes are not allowed in the exit basic block.
739 if (BasicBlock *Exit = R.getExit()) {
740 BasicBlock::iterator I = Exit->begin();
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000741 if (I != Exit->end() && isa<PHINode> (*I))
742 INVALID(Other, "PHI node in exit BB");
Tobias Grosser75805372011-04-29 06:27:02 +0000743 }
744
745 return true;
746}
747
748bool ScopDetection::isValidRegion(DetectionContext &Context) const {
749 Region &R = Context.CurRegion;
750
751 DEBUG(dbgs() << "Checking region: " << R.getNameStr() << "\n\t");
752
753 // The toplevel region is no valid region.
754 if (!R.getParent()) {
755 DEBUG(dbgs() << "Top level region is invalid";
756 dbgs() << "\n");
757 return false;
758 }
759
760 // SCoP can not contains the entry block of the function, because we need
761 // to insert alloca instruction there when translate scalar to array.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000762 if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock()))
763 INVALID(Other, "Region containing entry block of function is invalid!");
Tobias Grosser75805372011-04-29 06:27:02 +0000764
765 // Only a simple region is allowed.
Tobias Grosserc4a0bd12011-10-08 00:30:48 +0000766 if (!R.isSimple())
767 INVALID(SimpleRegion, "Region not simple: " << R.getNameStr());
Tobias Grosser75805372011-04-29 06:27:02 +0000768
769 if (!allBlocksValid(Context))
770 return false;
771
772 if (!isValidExit(Context))
773 return false;
774
775 DEBUG(dbgs() << "OK\n");
776 return true;
777}
778
779bool ScopDetection::isValidFunction(llvm::Function &F) {
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000780 return !InvalidFunctions.count(&F);
Tobias Grosser75805372011-04-29 06:27:02 +0000781}
782
783bool ScopDetection::runOnFunction(llvm::Function &F) {
784 AA = &getAnalysis<AliasAnalysis>();
785 SE = &getAnalysis<ScalarEvolution>();
786 LI = &getAnalysis<LoopInfo>();
787 RI = &getAnalysis<RegionInfo>();
788 Region *TopRegion = RI->getTopLevelRegion();
789
Tobias Grosser2ff87232011-10-23 11:17:06 +0000790 releaseMemory();
791
792 if (OnlyFunction != "" && F.getNameStr() != OnlyFunction)
793 return false;
794
Tobias Grosser75805372011-04-29 06:27:02 +0000795 if(!isValidFunction(F))
796 return false;
797
798 findScops(*TopRegion);
799 return false;
800}
801
802
803void polly::ScopDetection::verifyRegion(const Region &R) const {
804 assert(isMaxRegionInScop(R) && "Expect R is a valid region.");
805 DetectionContext Context(const_cast<Region&>(R), *AA, true /*verifying*/);
806 isValidRegion(Context);
807}
808
809void polly::ScopDetection::verifyAnalysis() const {
810 for (RegionSet::const_iterator I = ValidRegions.begin(),
811 E = ValidRegions.end(); I != E; ++I)
812 verifyRegion(**I);
813}
814
815void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const {
816 AU.addRequired<DominatorTree>();
817 AU.addRequired<PostDominatorTree>();
818 AU.addRequired<LoopInfo>();
819 AU.addRequired<ScalarEvolution>();
820 // We also need AA and RegionInfo when we are verifying analysis.
821 AU.addRequiredTransitive<AliasAnalysis>();
822 AU.addRequiredTransitive<RegionInfo>();
823 AU.setPreservesAll();
824}
825
826void ScopDetection::print(raw_ostream &OS, const Module *) const {
827 for (RegionSet::const_iterator I = ValidRegions.begin(),
828 E = ValidRegions.end(); I != E; ++I)
829 OS << "Valid Region for Scop: " << (*I)->getNameStr() << '\n';
830
831 OS << "\n";
832}
833
834void ScopDetection::releaseMemory() {
835 ValidRegions.clear();
Tobias Grosser4f129a62011-10-08 00:30:55 +0000836 InvalidRegions.clear();
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000837 // Do not clear the invalid function set.
Tobias Grosser75805372011-04-29 06:27:02 +0000838}
839
840char ScopDetection::ID = 0;
841
Tobias Grosser73600b82011-10-08 00:30:40 +0000842INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect",
843 "Polly - Detect static control parts (SCoPs)", false,
844 false)
845INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
846INITIALIZE_PASS_DEPENDENCY(DominatorTree)
847INITIALIZE_PASS_DEPENDENCY(LoopInfo)
848INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
849INITIALIZE_PASS_DEPENDENCY(RegionInfo)
850INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
851INITIALIZE_PASS_END(ScopDetection, "polly-detect",
852 "Polly - Detect static control parts (SCoPs)", false, false)
Tobias Grosser75805372011-04-29 06:27:02 +0000853
Tobias Grosser83f5c432011-08-23 22:35:08 +0000854Pass *polly::createScopDetectionPass() {
855 return new ScopDetection();
856}