Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 1 | //===----- 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 Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 47 | #include "polly/CodeGen/BlockGenerators.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 48 | #include "polly/LinkAllPasses.h" |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 49 | #include "polly/Options.h" |
Tobias Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 50 | #include "polly/ScopDetection.h" |
Tobias Grosser | 120db6b | 2011-11-07 12:58:54 +0000 | [diff] [blame] | 51 | #include "polly/Support/SCEVValidator.h" |
Tobias Grosser | 8362818 | 2013-05-07 08:11:54 +0000 | [diff] [blame] | 52 | #include "polly/Support/ScopHelper.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 53 | #include "llvm/ADT/Statistic.h" |
| 54 | #include "llvm/Analysis/AliasAnalysis.h" |
Tobias Grosser | 6e9f25a | 2011-11-09 22:35:00 +0000 | [diff] [blame] | 55 | #include "llvm/Analysis/LoopInfo.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 56 | #include "llvm/Analysis/RegionIterator.h" |
Tobias Grosser | 6e9f25a | 2011-11-09 22:35:00 +0000 | [diff] [blame] | 57 | #include "llvm/Analysis/ScalarEvolution.h" |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 58 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 59 | #include "llvm/Assembly/Writer.h" |
Tobias Grosser | 8362818 | 2013-05-07 08:11:54 +0000 | [diff] [blame] | 60 | #include "llvm/DebugInfo.h" |
| 61 | #include "llvm/IR/LLVMContext.h" |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 62 | |
| 63 | #define DEBUG_TYPE "polly-detect" |
| 64 | #include "llvm/Support/Debug.h" |
| 65 | |
Tobias Grosser | 60b54f1 | 2011-11-08 15:41:28 +0000 | [diff] [blame] | 66 | #include <set> |
| 67 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 68 | using namespace llvm; |
| 69 | using namespace polly; |
| 70 | |
Sebastian Pop | 8fe6d11 | 2013-05-30 17:47:32 +0000 | [diff] [blame^] | 71 | static cl::opt<bool> |
| 72 | DetectScopsWithoutLoops("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 Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 76 | static cl::opt<std::string> |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 77 | OnlyFunction("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 Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 80 | |
Tobias Grosser | 60cd932 | 2011-11-10 12:47:26 +0000 | [diff] [blame] | 81 | static cl::opt<bool> |
| 82 | IgnoreAliasing("polly-ignore-aliasing", |
| 83 | cl::desc("Ignore possible aliasing of the array bases"), |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 84 | cl::Hidden, cl::init(false), cl::cat(PollyCategory)); |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 85 | |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 86 | static cl::opt<bool> |
| 87 | ReportLevel("polly-report", |
| 88 | cl::desc("Print information about the activities of Polly"), |
| 89 | cl::init(false), cl::cat(PollyCategory)); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 90 | |
| 91 | static cl::opt<bool> |
Tobias Grosser | a187964 | 2011-12-20 10:43:14 +0000 | [diff] [blame] | 92 | AllowNonAffine("polly-allow-nonaffine", |
| 93 | cl::desc("Allow non affine access functions in arrays"), |
Tobias Grosser | 637bd63 | 2013-05-07 07:31:10 +0000 | [diff] [blame] | 94 | cl::Hidden, cl::init(false), cl::cat(PollyCategory)); |
Tobias Grosser | a187964 | 2011-12-20 10:43:14 +0000 | [diff] [blame] | 95 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 96 | //===----------------------------------------------------------------------===// |
| 97 | // Statistics. |
| 98 | |
| 99 | STATISTIC(ValidRegion, "Number of regions that a valid part of Scop"); |
| 100 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 101 | #define BADSCOP_STAT(NAME, DESC) \ |
| 102 | STATISTIC(Bad##NAME##ForScop, "Number of bad regions for Scop: " DESC) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 103 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 104 | #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 Grosser | 84b81de | 2013-03-19 21:44:07 +0000 | [diff] [blame] | 117 | } while (0) |
Tobias Grosser | fff5adc | 2011-11-10 13:21:43 +0000 | [diff] [blame] | 118 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 119 | #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 Grosser | 84b81de | 2013-03-19 21:44:07 +0000 | [diff] [blame] | 132 | } while (0) |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 133 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 134 | BADSCOP_STAT(CFG, "CFG too complex"); |
| 135 | BADSCOP_STAT(IndVar, "Non canonical induction variable in loop"); |
| 136 | BADSCOP_STAT(LoopBound, "Loop bounds can not be computed"); |
| 137 | BADSCOP_STAT(FuncCall, "Function call with side effects appeared"); |
| 138 | BADSCOP_STAT(AffFunc, "Expression not affine"); |
| 139 | BADSCOP_STAT(Scalar, "Found scalar dependency"); |
| 140 | BADSCOP_STAT(Alias, "Found base address alias"); |
Tobias Grosser | 8edce4e | 2013-04-16 08:04:42 +0000 | [diff] [blame] | 141 | BADSCOP_STAT(SimpleLoop, "Loop not in -loop-simplify form"); |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 142 | BADSCOP_STAT(Other, "Others"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 143 | |
| 144 | //===----------------------------------------------------------------------===// |
| 145 | // ScopDetection. |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 146 | bool 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 Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 151 | std::string ScopDetection::regionIsInvalidBecause(const Region *R) const { |
| 152 | if (!InvalidRegions.count(R)) |
| 153 | return ""; |
| 154 | |
| 155 | return InvalidRegions.find(R)->second; |
| 156 | } |
| 157 | |
Tobias Grosser | e602a07 | 2013-05-07 07:30:56 +0000 | [diff] [blame] | 158 | bool ScopDetection::isValidCFG(BasicBlock &BB, |
| 159 | DetectionContext &Context) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 160 | 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 169 | if (!Br) |
Tobias Grosser | 29ee0b1 | 2011-11-17 14:52:36 +0000 | [diff] [blame] | 170 | INVALID(CFG, "Non branch instruction terminates BB: " + BB.getName()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 171 | |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 172 | if (Br->isUnconditional()) |
| 173 | return true; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 174 | |
| 175 | Value *Condition = Br->getCondition(); |
| 176 | |
| 177 | // UndefValue is not allowed as condition. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 178 | if (isa<UndefValue>(Condition)) |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 179 | INVALID(AffFunc, "Condition based on 'undef' value in BB: " + BB.getName()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 180 | |
| 181 | // Only Constant and ICmpInst are allowed as condition. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 182 | if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 183 | INVALID(AffFunc, "Condition in BB '" + BB.getName() + |
Tobias Grosser | d7e5864 | 2013-04-10 06:55:45 +0000 | [diff] [blame] | 184 | "' neither constant nor an icmp instruction"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 185 | |
| 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 Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 195 | if (ICmp->isUnsigned()) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 196 | return false; |
| 197 | |
| 198 | // Are both operands of the ICmp affine? |
Tobias Grosser | 74394f0 | 2013-01-14 22:40:23 +0000 | [diff] [blame] | 199 | if (isa<UndefValue>(ICmp->getOperand(0)) || |
| 200 | isa<UndefValue>(ICmp->getOperand(1))) |
Tobias Grosser | 29ee0b1 | 2011-11-17 14:52:36 +0000 | [diff] [blame] | 201 | INVALID(AffFunc, "undef operand in branch at BB: " + BB.getName()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 202 | |
Sebastian Pop | 9f57c5b | 2013-04-10 04:05:18 +0000 | [diff] [blame] | 203 | 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 206 | |
Tobias Grosser | a66fa6c | 2011-11-10 12:45:11 +0000 | [diff] [blame] | 207 | if (!isAffineExpr(&Context.CurRegion, LHS, *SE) || |
| 208 | !isAffineExpr(&Context.CurRegion, RHS, *SE)) |
Tobias Grosser | 29ee0b1 | 2011-11-17 14:52:36 +0000 | [diff] [blame] | 209 | INVALID(AffFunc, "Non affine branch in BB '" << BB.getName() |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 210 | << "' with LHS: " << *LHS |
| 211 | << " and RHS: " << *RHS); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 212 | } |
| 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 221 | if (R->getEntry() != &BB) |
Tobias Grosser | 29ee0b1 | 2011-11-17 14:52:36 +0000 | [diff] [blame] | 222 | INVALID(CFG, "Not well structured condition at BB: " + BB.getName()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 223 | |
| 224 | return true; |
| 225 | } |
| 226 | |
| 227 | bool 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 | |
| 244 | bool ScopDetection::isValidMemoryAccess(Instruction &Inst, |
| 245 | DetectionContext &Context) const { |
Tobias Grosser | e5e171e | 2011-11-10 12:45:03 +0000 | [diff] [blame] | 246 | Value *Ptr = getPointerOperand(Inst); |
Sebastian Pop | 9f57c5b | 2013-04-10 04:05:18 +0000 | [diff] [blame] | 247 | Loop *L = LI->getLoopFor(Inst.getParent()); |
| 248 | const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L); |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 249 | const SCEVUnknown *BasePointer; |
Tobias Grosser | e5e171e | 2011-11-10 12:45:03 +0000 | [diff] [blame] | 250 | Value *BaseValue; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 251 | |
Tobias Grosser | b8710b5 | 2011-11-10 12:44:50 +0000 | [diff] [blame] | 252 | 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 Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 264 | if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, BaseValue) && |
| 265 | !AllowNonAffine) |
Tobias Grosser | eeb776a | 2012-09-08 14:00:37 +0000 | [diff] [blame] | 266 | INVALID(AffFunc, "Non affine access function: " << *AccessFunction); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 267 | |
| 268 | // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions |
| 269 | // created by IndependentBlocks Pass. |
Tobias Grosser | e5e171e | 2011-11-10 12:45:03 +0000 | [diff] [blame] | 270 | if (isa<IntToPtrInst>(BaseValue)) |
| 271 | INVALID(Other, "Find bad intToptr prt: " << *BaseValue); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 272 | |
| 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 Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 276 | Context.AST.getAliasSetForPointer(BaseValue, AliasAnalysis::UnknownSize, |
| 277 | Inst.getMetadata(LLVMContext::MD_tbaa)); |
Tobias Grosser | fff5adc | 2011-11-10 13:21:43 +0000 | [diff] [blame] | 278 | |
| 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 Grosser | 428b3e4 | 2013-02-04 15:46:25 +0000 | [diff] [blame] | 286 | if (!AS.isMustAlias() && !IgnoreAliasing) { |
| 287 | std::string Message; |
| 288 | raw_string_ostream OS(Message); |
| 289 | |
| 290 | OS << "Possible aliasing: "; |
| 291 | |
Tobias Grosser | 0d1eee3 | 2013-02-05 11:56:05 +0000 | [diff] [blame] | 292 | std::vector<Value *> Pointers; |
Tobias Grosser | 428b3e4 | 2013-02-04 15:46:25 +0000 | [diff] [blame] | 293 | |
| 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 Grosser | 0d1eee3 | 2013-02-05 11:56:05 +0000 | [diff] [blame] | 299 | for (std::vector<Value *>::iterator PI = Pointers.begin(), |
Tobias Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 300 | PE = Pointers.end(); |
| 301 | ;) { |
Tobias Grosser | 428b3e4 | 2013-02-04 15:46:25 +0000 | [diff] [blame] | 302 | 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 Grosser | 84b81de | 2013-03-19 21:44:07 +0000 | [diff] [blame] | 317 | INVALID_NOVERIFY(Alias, OS.str()); |
Tobias Grosser | 428b3e4 | 2013-02-04 15:46:25 +0000 | [diff] [blame] | 318 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 319 | |
| 320 | return true; |
| 321 | } |
| 322 | |
Tobias Grosser | e602a07 | 2013-05-07 07:30:56 +0000 | [diff] [blame] | 323 | bool ScopDetection::hasScalarDependency(Instruction &Inst, |
| 324 | Region &RefRegion) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 325 | 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 | |
| 347 | bool ScopDetection::isValidInstruction(Instruction &Inst, |
| 348 | DetectionContext &Context) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 349 | if (PHINode *PN = dyn_cast<PHINode>(&Inst)) |
Tobias Grosser | ecfe21b | 2013-03-20 18:03:18 +0000 | [diff] [blame] | 350 | 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 357 | |
| 358 | // Scalar dependencies are not allowed. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 359 | if (hasScalarDependency(Inst, Context.CurRegion)) |
| 360 | INVALID(Scalar, "Scalar dependency found: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 361 | |
| 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 Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 367 | INVALID(FuncCall, "Call instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 368 | } |
| 369 | |
| 370 | if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) { |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 371 | if (isa<AllocaInst>(Inst)) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 372 | INVALID(Other, "Alloca instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 373 | |
| 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 382 | INVALID(Other, "Unknown instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 383 | } |
| 384 | |
| 385 | bool 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 | |
| 402 | bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { |
Tobias Grosser | 826b2af | 2013-03-21 16:14:50 +0000 | [diff] [blame] | 403 | 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 411 | |
| 412 | // Is the loop count affine? |
| 413 | const SCEV *LoopCount = SE->getBackedgeTakenCount(L); |
Tobias Grosser | 120db6b | 2011-11-07 12:58:54 +0000 | [diff] [blame] | 414 | if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE)) |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 415 | INVALID(LoopBound, |
| 416 | "Non affine loop bound '" |
Tobias Grosser | d7e5864 | 2013-04-10 06:55:45 +0000 | [diff] [blame] | 417 | << *LoopCount << "' in loop: " << L->getHeader()->getName()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 418 | |
| 419 | return true; |
| 420 | } |
| 421 | |
| 422 | Region *ScopDetection::expandRegion(Region &R) { |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 423 | // Initial no valid region was found (greater than R) |
| 424 | Region *LastValidRegion = NULL; |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 425 | Region *ExpandedRegion = R.getExpandedRegion(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 426 | |
| 427 | DEBUG(dbgs() << "\tExpanding " << R.getNameStr() << "\n"); |
| 428 | |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 429 | while (ExpandedRegion) { |
| 430 | DetectionContext Context(*ExpandedRegion, *AA, false /* verifying */); |
| 431 | DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 432 | |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 433 | // Check the exit first (cheap) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 434 | if (isValidExit(Context)) { |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 435 | // 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 440 | |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 441 | // Delete unnecessary regions (allocated by getExpandedRegion) |
| 442 | if (LastValidRegion) |
| 443 | delete LastValidRegion; |
| 444 | |
Tobias Grosser | d7e5864 | 2013-04-10 06:55:45 +0000 | [diff] [blame] | 445 | // Store this region, because it is the greatest valid (encountered so |
| 446 | // far). |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 447 | 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 460 | } |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 461 | } |
| 462 | |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 463 | DEBUG(if (LastValidRegion) |
Tobias Grosser | d7e5864 | 2013-04-10 06:55:45 +0000 | [diff] [blame] | 464 | dbgs() << "\tto " << LastValidRegion->getNameStr() << "\n"; |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 465 | else dbgs() << "\tExpanding " << R.getNameStr() << " failed\n";); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 466 | |
Hongbin Zheng | ed986ab | 2012-04-07 15:14:28 +0000 | [diff] [blame] | 467 | return LastValidRegion; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 468 | } |
| 469 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 470 | void ScopDetection::findScops(Region &R) { |
| 471 | DetectionContext Context(R, *AA, false /*verifying*/); |
| 472 | |
Tobias Grosser | 4eb7381 | 2011-11-10 12:45:15 +0000 | [diff] [blame] | 473 | LastFailure = ""; |
| 474 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 475 | if (isValidRegion(Context)) { |
| 476 | ++ValidRegion; |
| 477 | ValidRegions.insert(&R); |
| 478 | return; |
| 479 | } |
| 480 | |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 481 | InvalidRegions[&R] = LastFailure; |
| 482 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 483 | 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 Grosser | 0d1eee3 | 2013-02-05 11:56:05 +0000 | [diff] [blame] | 492 | std::vector<Region *> ToExpand; |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 493 | |
| 494 | for (Region::iterator I = R.begin(), E = R.end(); I != E; ++I) |
| 495 | ToExpand.push_back(*I); |
| 496 | |
Tobias Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 497 | for (std::vector<Region *>::iterator RI = ToExpand.begin(), |
| 498 | RE = ToExpand.end(); |
| 499 | RI != RE; ++RI) { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 500 | 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 | |
| 522 | bool 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 Carruth | 30dfdfc | 2012-05-04 21:24:27 +0000 | [diff] [blame] | 527 | if (!isValidBasicBlock(**I, Context)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 528 | return false; |
| 529 | |
| 530 | return true; |
| 531 | } |
| 532 | |
| 533 | bool 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 Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 539 | if (I != Exit->end() && isa<PHINode>(*I)) |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 540 | INVALID(Other, "PHI node in exit BB"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 541 | } |
| 542 | |
| 543 | return true; |
| 544 | } |
| 545 | |
| 546 | bool 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 Grosser | aeabcf2 | 2013-04-02 06:41:48 +0000 | [diff] [blame] | 552 | if (R.isTopLevelRegion()) { |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 553 | DEBUG(dbgs() << "Top level region is invalid"; dbgs() << "\n"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 554 | return false; |
| 555 | } |
| 556 | |
Tobias Grosser | e602a07 | 2013-05-07 07:30:56 +0000 | [diff] [blame] | 557 | if (!R.getEnteringBlock()) { |
Tobias Grosser | 8edce4e | 2013-04-16 08:04:42 +0000 | [diff] [blame] | 558 | Loop *L = LI->getLoopFor(R.getEntry()); |
| 559 | if (L && !L->isLoopSimplifyForm()) |
| 560 | INVALID(SimpleLoop, "Loop not in simplify form is invalid!"); |
| 561 | } |
| 562 | |
Tobias Grosser | d654c25 | 2012-04-10 18:12:19 +0000 | [diff] [blame] | 563 | // SCoP cannot contain the entry block of the function, because we need |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 564 | // to insert alloca instruction there when translate scalar to array. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 565 | if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock())) |
| 566 | INVALID(Other, "Region containing entry block of function is invalid!"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 567 | |
Hongbin Zheng | 94868e6 | 2012-04-07 12:29:17 +0000 | [diff] [blame] | 568 | if (!isValidExit(Context)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 569 | return false; |
| 570 | |
Hongbin Zheng | 94868e6 | 2012-04-07 12:29:17 +0000 | [diff] [blame] | 571 | if (!allBlocksValid(Context)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 572 | return false; |
| 573 | |
| 574 | DEBUG(dbgs() << "OK\n"); |
| 575 | return true; |
| 576 | } |
| 577 | |
| 578 | bool ScopDetection::isValidFunction(llvm::Function &F) { |
Hongbin Zheng | 94c5df1 | 2011-05-06 02:38:20 +0000 | [diff] [blame] | 579 | return !InvalidFunctions.count(&F); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 580 | } |
| 581 | |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 582 | void 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 Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 605 | } |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 606 | } |
| 607 | |
Tobias Grosser | b2863ca | 2013-03-04 19:49:51 +0000 | [diff] [blame] | 608 | void 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 Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 614 | 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 Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 622 | "(-g) to get more precise information. \n"; |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 623 | return; |
| 624 | } |
| 625 | |
Tobias Grosser | b2863ca | 2013-03-04 19:49:51 +0000 | [diff] [blame] | 626 | outs() << FileName << ":" << LineEntry |
| 627 | << ": Start of static control region\n"; |
| 628 | outs() << FileName << ":" << LineExit << ": End of static control region\n"; |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 629 | } |
| 630 | } |
| 631 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 632 | bool ScopDetection::runOnFunction(llvm::Function &F) { |
Sebastian Pop | 8fe6d11 | 2013-05-30 17:47:32 +0000 | [diff] [blame^] | 633 | LI = &getAnalysis<LoopInfo>(); |
| 634 | if (!DetectScopsWithoutLoops && LI->empty()) |
| 635 | return false; |
| 636 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 637 | AA = &getAnalysis<AliasAnalysis>(); |
| 638 | SE = &getAnalysis<ScalarEvolution>(); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 639 | RI = &getAnalysis<RegionInfo>(); |
| 640 | Region *TopRegion = RI->getTopLevelRegion(); |
| 641 | |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 642 | releaseMemory(); |
| 643 | |
Tobias Grosser | 29ee0b1 | 2011-11-17 14:52:36 +0000 | [diff] [blame] | 644 | if (OnlyFunction != "" && F.getName() != OnlyFunction) |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 645 | return false; |
| 646 | |
Tobias Grosser | 1bb59b0 | 2012-12-29 23:47:38 +0000 | [diff] [blame] | 647 | if (!isValidFunction(F)) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 648 | return false; |
| 649 | |
| 650 | findScops(*TopRegion); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 651 | |
| 652 | if (ReportLevel >= 1) |
Tobias Grosser | b2863ca | 2013-03-04 19:49:51 +0000 | [diff] [blame] | 653 | printLocations(F); |
Tobias Grosser | 531891e | 2012-11-01 16:45:20 +0000 | [diff] [blame] | 654 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 655 | return false; |
| 656 | } |
| 657 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 658 | void polly::ScopDetection::verifyRegion(const Region &R) const { |
| 659 | assert(isMaxRegionInScop(R) && "Expect R is a valid region."); |
Tobias Grosser | 0d1eee3 | 2013-02-05 11:56:05 +0000 | [diff] [blame] | 660 | DetectionContext Context(const_cast<Region &>(R), *AA, true /*verifying*/); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 661 | isValidRegion(Context); |
| 662 | } |
| 663 | |
| 664 | void polly::ScopDetection::verifyAnalysis() const { |
| 665 | for (RegionSet::const_iterator I = ValidRegions.begin(), |
Tobias Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 666 | E = ValidRegions.end(); |
| 667 | I != E; ++I) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 668 | verifyRegion(**I); |
| 669 | } |
| 670 | |
| 671 | void 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 Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 682 | void ScopDetection::print(raw_ostream &OS, const Module *) const { |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 683 | for (RegionSet::const_iterator I = ValidRegions.begin(), |
Tobias Grosser | af3c00b8 | 2013-02-05 09:40:22 +0000 | [diff] [blame] | 684 | E = ValidRegions.end(); |
| 685 | I != E; ++I) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 686 | OS << "Valid Region for Scop: " << (*I)->getNameStr() << '\n'; |
| 687 | |
| 688 | OS << "\n"; |
| 689 | } |
| 690 | |
| 691 | void ScopDetection::releaseMemory() { |
| 692 | ValidRegions.clear(); |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 693 | InvalidRegions.clear(); |
Hongbin Zheng | 94c5df1 | 2011-05-06 02:38:20 +0000 | [diff] [blame] | 694 | // Do not clear the invalid function set. |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 695 | } |
| 696 | |
| 697 | char ScopDetection::ID = 0; |
| 698 | |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 699 | Pass *polly::createScopDetectionPass() { return new ScopDetection(); } |
| 700 | |
Tobias Grosser | 73600b8 | 2011-10-08 00:30:40 +0000 | [diff] [blame] | 701 | INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect", |
| 702 | "Polly - Detect static control parts (SCoPs)", false, |
Tobias Grosser | 4d96c8d | 2013-03-23 01:05:07 +0000 | [diff] [blame] | 703 | false); |
| 704 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis); |
| 705 | INITIALIZE_PASS_DEPENDENCY(DominatorTree); |
| 706 | INITIALIZE_PASS_DEPENDENCY(LoopInfo); |
| 707 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTree); |
| 708 | INITIALIZE_PASS_DEPENDENCY(RegionInfo); |
| 709 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolution); |
Tobias Grosser | 73600b8 | 2011-10-08 00:30:40 +0000 | [diff] [blame] | 710 | INITIALIZE_PASS_END(ScopDetection, "polly-detect", |
| 711 | "Polly - Detect static control parts (SCoPs)", false, false) |