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 | |
| 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 | |
| 63 | using namespace llvm; |
| 64 | using namespace polly; |
| 65 | |
Tobias Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 66 | static cl::opt<std::string> |
| 67 | OnlyFunction("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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 73 | //===----------------------------------------------------------------------===// |
| 74 | // Statistics. |
| 75 | |
| 76 | STATISTIC(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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 85 | #define INVALID(NAME, MESSAGE) \ |
| 86 | do { \ |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 87 | std::string Buf; \ |
| 88 | raw_string_ostream fmt(Buf); \ |
| 89 | fmt << MESSAGE; \ |
| 90 | fmt.flush(); \ |
| 91 | LastFailure = Buf; \ |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 92 | DEBUG(dbgs() << MESSAGE); \ |
| 93 | DEBUG(dbgs() << "\n"); \ |
| 94 | STATSCOP(NAME); \ |
| 95 | return false; \ |
| 96 | } while (0); |
| 97 | |
| 98 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 99 | BADSCOP_STAT(CFG, "CFG too complex"); |
| 100 | BADSCOP_STAT(IndVar, "Non canonical induction variable in loop"); |
| 101 | BADSCOP_STAT(LoopBound, "Loop bounds can not be computed"); |
| 102 | BADSCOP_STAT(FuncCall, "Function call with side effects appeared"); |
| 103 | BADSCOP_STAT(AffFunc, "Expression not affine"); |
| 104 | BADSCOP_STAT(Scalar, "Found scalar dependency"); |
| 105 | BADSCOP_STAT(Alias, "Found base address alias"); |
| 106 | BADSCOP_STAT(SimpleRegion, "Region not simple"); |
| 107 | BADSCOP_STAT(Other, "Others"); |
| 108 | |
| 109 | //===----------------------------------------------------------------------===// |
| 110 | // ScopDetection. |
| 111 | |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 112 | namespace SCEVType { |
| 113 | enum TYPE {INT, PARAM, IV, INVALID}; |
| 114 | } |
| 115 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 116 | struct 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 Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 127 | 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 Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 142 | }; |
| 143 | |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 144 | /// Check if a SCEV is valid in a SCoP. |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 145 | struct SCEVValidator |
| 146 | : public SCEVVisitor<SCEVValidator, struct ValidatorResult> { |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 147 | private: |
| 148 | const Region *R; |
| 149 | ScalarEvolution &SE; |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 150 | Value **BaseAddress; |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 151 | |
| 152 | public: |
| 153 | static bool isValid(const Region *R, const SCEV *Scev, |
| 154 | ScalarEvolution &SE, |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 155 | Value **BaseAddress = NULL) { |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 156 | if (isa<SCEVCouldNotCompute>(Scev)) |
| 157 | return false; |
| 158 | |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 159 | if (BaseAddress) |
| 160 | *BaseAddress = NULL; |
| 161 | |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 162 | SCEVValidator Validator(R, SE, BaseAddress); |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 163 | ValidatorResult Result = Validator.visit(Scev); |
| 164 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 165 | return Result.isValid(); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 166 | } |
| 167 | |
| 168 | SCEVValidator(const Region *R, ScalarEvolution &SE, |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 169 | Value **BaseAddress) : R(R), SE(SE), |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 170 | BaseAddress(BaseAddress) {}; |
| 171 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 172 | struct ValidatorResult visitConstant(const SCEVConstant *Constant) { |
| 173 | return ValidatorResult(SCEVType::INT); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 174 | } |
| 175 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 176 | struct ValidatorResult visitTruncateExpr(const SCEVTruncateExpr* Expr) { |
| 177 | ValidatorResult Op = visit(Expr->getOperand()); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 178 | |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 179 | // 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 Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 182 | if (Op.isConstant()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 183 | return ValidatorResult(SCEVType::PARAM); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 184 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 185 | return ValidatorResult (SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 186 | } |
| 187 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 188 | struct ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr * Expr) { |
| 189 | ValidatorResult Op = visit(Expr->getOperand()); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 190 | |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 191 | // 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 Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 194 | if (Op.isConstant()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 195 | return ValidatorResult (SCEVType::PARAM); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 196 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 197 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 198 | } |
| 199 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 200 | struct ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr* Expr) { |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 201 | // 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 Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 205 | return visit(Expr->getOperand()); |
| 206 | } |
| 207 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 208 | struct ValidatorResult visitAddExpr(const SCEVAddExpr* Expr) { |
| 209 | ValidatorResult Return(SCEVType::INT); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 210 | |
| 211 | for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 212 | ValidatorResult Op = visit(Expr->getOperand(i)); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 213 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 214 | if (!Op.isValid()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 215 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 216 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 217 | Return.type = std::max(Return.type, Op.type); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 218 | } |
| 219 | |
| 220 | // TODO: Check for NSW and NUW. |
| 221 | return Return; |
| 222 | } |
| 223 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 224 | struct ValidatorResult visitMulExpr(const SCEVMulExpr* Expr) { |
| 225 | ValidatorResult Return(SCEVType::INT); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 226 | |
| 227 | for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 228 | ValidatorResult Op = visit(Expr->getOperand(i)); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 229 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 230 | if (Op.type == SCEVType::INT) |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 231 | continue; |
| 232 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 233 | if (Op.type == SCEVType::INVALID || Return.type != SCEVType::INT) |
| 234 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 235 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 236 | Return.type = Op.type; |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 237 | } |
| 238 | |
| 239 | // TODO: Check for NSW and NUW. |
| 240 | return Return; |
| 241 | } |
| 242 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 243 | struct ValidatorResult visitUDivExpr(const SCEVUDivExpr* Expr) { |
| 244 | ValidatorResult LHS = visit(Expr->getLHS()); |
| 245 | ValidatorResult RHS = visit(Expr->getRHS()); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 246 | |
| 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 Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 250 | if (LHS.isConstant() && RHS.isConstant()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 251 | return ValidatorResult(SCEVType::PARAM); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 252 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 253 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 254 | } |
| 255 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 256 | struct ValidatorResult visitAddRecExpr(const SCEVAddRecExpr* Expr) { |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 257 | if (!Expr->isAffine()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 258 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 259 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 260 | ValidatorResult Start = visit(Expr->getStart()); |
| 261 | ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE)); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 262 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 263 | if (!Start.isValid() || !Recurrence.isValid() || Recurrence.isIV()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 264 | return ValidatorResult(SCEVType::INVALID); |
| 265 | |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 266 | |
| 267 | if (!R->contains(Expr->getLoop())) { |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 268 | if (Start.isIV()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 269 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 270 | else |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 271 | return ValidatorResult(SCEVType::PARAM); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 272 | } |
| 273 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 274 | if (!Recurrence.isINT()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 275 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 276 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 277 | return ValidatorResult(SCEVType::IV); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 278 | } |
| 279 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 280 | struct ValidatorResult visitSMaxExpr(const SCEVSMaxExpr* Expr) { |
| 281 | ValidatorResult Return(SCEVType::INT); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 282 | |
| 283 | for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 284 | ValidatorResult Op = visit(Expr->getOperand(i)); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 285 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 286 | if (!Op.isValid()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 287 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 288 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 289 | Return.type = std::max(Return.type, Op.type); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 290 | } |
| 291 | |
| 292 | return Return; |
| 293 | } |
| 294 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 295 | struct ValidatorResult visitUMaxExpr(const SCEVUMaxExpr* Expr) { |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 296 | // 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 Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 298 | for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 299 | ValidatorResult Op = visit(Expr->getOperand(i)); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 300 | |
Tobias Grosser | 60e85cb | 2011-11-07 12:58:46 +0000 | [diff] [blame^] | 301 | if (!Op.isConstant()) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 302 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 303 | } |
| 304 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 305 | return ValidatorResult(SCEVType::PARAM); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 306 | } |
| 307 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 308 | ValidatorResult visitUnknown(const SCEVUnknown* Expr) { |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 309 | Value *V = Expr->getValue(); |
| 310 | |
| 311 | if (isa<UndefValue>(V)) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 312 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 313 | |
| 314 | if (BaseAddress) { |
| 315 | if (*BaseAddress) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 316 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 317 | else |
| 318 | *BaseAddress = V; |
| 319 | } |
| 320 | |
Tobias Grosser | ad96c4b | 2011-11-03 21:03:01 +0000 | [diff] [blame] | 321 | if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) |
| 322 | if (R->contains(I)) |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 323 | return ValidatorResult(SCEVType::INVALID); |
Tobias Grosser | 2d0b1f9 | 2011-11-04 10:08:08 +0000 | [diff] [blame] | 324 | |
Tobias Grosser | eadc428 | 2011-11-07 12:58:41 +0000 | [diff] [blame] | 325 | if (BaseAddress) |
| 326 | return ValidatorResult(SCEVType::PARAM); |
| 327 | else |
| 328 | return ValidatorResult(SCEVType::PARAM); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 329 | } |
| 330 | }; |
| 331 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 332 | bool 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 Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 337 | std::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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 345 | bool 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 | |
| 412 | bool 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 423 | if (!Br) |
| 424 | INVALID(CFG, "Non branch instruction terminates BB: " + BB.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 425 | |
| 426 | if (Br->isUnconditional()) return true; |
| 427 | |
| 428 | Value *Condition = Br->getCondition(); |
| 429 | |
| 430 | // UndefValue is not allowed as condition. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 431 | if (isa<UndefValue>(Condition)) |
| 432 | INVALID(AffFunc, "Condition based on 'undef' value in BB: " |
| 433 | + BB.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 434 | |
| 435 | // Only Constant and ICmpInst are allowed as condition. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 436 | if (!(isa<Constant>(Condition) || isa<ICmpInst>(Condition))) |
| 437 | INVALID(AffFunc, "Condition in BB '" + BB.getNameStr() + "' neither " |
| 438 | "constant nor an icmp instruction"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 439 | |
| 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 454 | || isa<UndefValue>(ICmp->getOperand(1))) |
| 455 | INVALID(AffFunc, "undef operand in branch at BB: " + BB.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 456 | |
| 457 | const SCEV *ScevLHS = SE->getSCEV(ICmp->getOperand(0)); |
| 458 | const SCEV *ScevRHS = SE->getSCEV(ICmp->getOperand(1)); |
| 459 | |
Tobias Grosser | 2fea5c6 | 2011-11-03 21:03:14 +0000 | [diff] [blame] | 460 | bool affineLHS = SCEVValidator::isValid(&Context.CurRegion, ScevLHS, *SE); |
| 461 | bool affineRHS = SCEVValidator::isValid(&Context.CurRegion, ScevRHS, *SE); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 462 | |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 463 | if (!affineLHS || !affineRHS) |
| 464 | INVALID(AffFunc, "Non affine branch in BB: " + BB.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 465 | } |
| 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 474 | if (R->getEntry() != &BB) |
| 475 | INVALID(CFG, "Not well structured condition at BB: " + BB.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 476 | |
| 477 | return true; |
| 478 | } |
| 479 | |
| 480 | bool 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 | |
| 497 | bool ScopDetection::isValidMemoryAccess(Instruction &Inst, |
| 498 | DetectionContext &Context) const { |
| 499 | Value *Ptr = getPointerOperand(Inst), *BasePtr; |
| 500 | const SCEV *AccessFunction = SE->getSCEV(Ptr); |
| 501 | |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 502 | if (!SCEVValidator::isValid(&Context.CurRegion, AccessFunction, *SE, |
| 503 | &BasePtr)) |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 504 | INVALID(AffFunc, "Bad memory address " << *AccessFunction); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 505 | |
Tobias Grosser | 7616467 | 2011-11-03 21:03:18 +0000 | [diff] [blame] | 506 | // 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 Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 512 | // FIXME: Alias Analysis thinks IntToPtrInst aliases with alloca instructions |
| 513 | // created by IndependentBlocks Pass. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 514 | if (isa<IntToPtrInst>(BasePtr)) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 515 | INVALID(Other, "Find bad intToptr prt: " << *BasePtr); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 516 | |
| 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 | |
| 543 | bool 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 | |
| 567 | bool ScopDetection::isValidInstruction(Instruction &Inst, |
| 568 | DetectionContext &Context) const { |
| 569 | // Only canonical IVs are allowed. |
| 570 | if (PHINode *PN = dyn_cast<PHINode>(&Inst)) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 571 | if (!isIndVar(PN, LI)) |
| 572 | INVALID(IndVar, "Non canonical PHI node: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 573 | |
| 574 | // Scalar dependencies are not allowed. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 575 | if (hasScalarDependency(Inst, Context.CurRegion)) |
| 576 | INVALID(Scalar, "Scalar dependency found: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 577 | |
| 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 Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 583 | INVALID(FuncCall, "Call instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 584 | } |
| 585 | |
| 586 | if (!Inst.mayWriteToMemory() && !Inst.mayReadFromMemory()) { |
| 587 | // Handle cast instruction. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 588 | if (isa<IntToPtrInst>(Inst) || isa<BitCastInst>(Inst)) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 589 | INVALID(Other, "Cast instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 590 | |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 591 | if (isa<AllocaInst>(Inst)) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 592 | INVALID(Other, "Alloca instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 593 | |
| 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 602 | INVALID(Other, "Unknown instruction: " << Inst); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 603 | } |
| 604 | |
| 605 | bool 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 | |
| 622 | bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { |
| 623 | PHINode *IndVar = L->getCanonicalInductionVariable(); |
| 624 | // No canonical induction variable. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 625 | if (!IndVar) |
Tobias Grosser | b43ba82 | 2011-10-08 00:49:30 +0000 | [diff] [blame] | 626 | INVALID(IndVar, "No canonical IV at loop header: " |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 627 | << L->getHeader()->getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 628 | |
| 629 | // Is the loop count affine? |
| 630 | const SCEV *LoopCount = SE->getBackedgeTakenCount(L); |
Tobias Grosser | 3fb4992 | 2011-11-02 21:40:08 +0000 | [diff] [blame] | 631 | if (!SCEVValidator::isValid(&Context.CurRegion, LoopCount, *SE)) |
Tobias Grosser | bd54f32 | 2011-10-26 01:27:49 +0000 | [diff] [blame] | 632 | INVALID(LoopBound, "Non affine loop bound '" << *LoopCount << "' in loop: " |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 633 | << L->getHeader()->getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 634 | |
| 635 | return true; |
| 636 | } |
| 637 | |
| 638 | Region *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 | |
| 675 | void 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 Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 684 | InvalidRegions[&R] = LastFailure; |
| 685 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 686 | 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 | |
| 724 | bool 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 | |
| 735 | bool 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 741 | if (I != Exit->end() && isa<PHINode> (*I)) |
| 742 | INVALID(Other, "PHI node in exit BB"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 743 | } |
| 744 | |
| 745 | return true; |
| 746 | } |
| 747 | |
| 748 | bool 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 Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 762 | if (R.getEntry() == &(R.getEntry()->getParent()->getEntryBlock())) |
| 763 | INVALID(Other, "Region containing entry block of function is invalid!"); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 764 | |
| 765 | // Only a simple region is allowed. |
Tobias Grosser | c4a0bd1 | 2011-10-08 00:30:48 +0000 | [diff] [blame] | 766 | if (!R.isSimple()) |
| 767 | INVALID(SimpleRegion, "Region not simple: " << R.getNameStr()); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 768 | |
| 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 | |
| 779 | bool ScopDetection::isValidFunction(llvm::Function &F) { |
Hongbin Zheng | 94c5df1 | 2011-05-06 02:38:20 +0000 | [diff] [blame] | 780 | return !InvalidFunctions.count(&F); |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 781 | } |
| 782 | |
| 783 | bool 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 Grosser | 2ff8723 | 2011-10-23 11:17:06 +0000 | [diff] [blame] | 790 | releaseMemory(); |
| 791 | |
| 792 | if (OnlyFunction != "" && F.getNameStr() != OnlyFunction) |
| 793 | return false; |
| 794 | |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 795 | if(!isValidFunction(F)) |
| 796 | return false; |
| 797 | |
| 798 | findScops(*TopRegion); |
| 799 | return false; |
| 800 | } |
| 801 | |
| 802 | |
| 803 | void 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 | |
| 809 | void polly::ScopDetection::verifyAnalysis() const { |
| 810 | for (RegionSet::const_iterator I = ValidRegions.begin(), |
| 811 | E = ValidRegions.end(); I != E; ++I) |
| 812 | verifyRegion(**I); |
| 813 | } |
| 814 | |
| 815 | void 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 | |
| 826 | void 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 | |
| 834 | void ScopDetection::releaseMemory() { |
| 835 | ValidRegions.clear(); |
Tobias Grosser | 4f129a6 | 2011-10-08 00:30:55 +0000 | [diff] [blame] | 836 | InvalidRegions.clear(); |
Hongbin Zheng | 94c5df1 | 2011-05-06 02:38:20 +0000 | [diff] [blame] | 837 | // Do not clear the invalid function set. |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 838 | } |
| 839 | |
| 840 | char ScopDetection::ID = 0; |
| 841 | |
Tobias Grosser | 73600b8 | 2011-10-08 00:30:40 +0000 | [diff] [blame] | 842 | INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect", |
| 843 | "Polly - Detect static control parts (SCoPs)", false, |
| 844 | false) |
| 845 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
| 846 | INITIALIZE_PASS_DEPENDENCY(DominatorTree) |
| 847 | INITIALIZE_PASS_DEPENDENCY(LoopInfo) |
| 848 | INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) |
| 849 | INITIALIZE_PASS_DEPENDENCY(RegionInfo) |
| 850 | INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) |
| 851 | INITIALIZE_PASS_END(ScopDetection, "polly-detect", |
| 852 | "Polly - Detect static control parts (SCoPs)", false, false) |
Tobias Grosser | 7580537 | 2011-04-29 06:27:02 +0000 | [diff] [blame] | 853 | |
Tobias Grosser | 83f5c43 | 2011-08-23 22:35:08 +0000 | [diff] [blame] | 854 | Pass *polly::createScopDetectionPass() { |
| 855 | return new ScopDetection(); |
| 856 | } |