1 2 #include "polly/Support/SCEVValidator.h" 3 #include "polly/ScopDetection.h" 4 #include "llvm/Analysis/RegionInfo.h" 5 #include "llvm/Analysis/ScalarEvolution.h" 6 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 7 #include "llvm/Support/Debug.h" 8 9 using namespace llvm; 10 using namespace polly; 11 12 #define DEBUG_TYPE "polly-scev-validator" 13 14 namespace SCEVType { 15 /// The type of a SCEV 16 /// 17 /// To check for the validity of a SCEV we assign to each SCEV a type. The 18 /// possible types are INT, PARAM, IV and INVALID. The order of the types is 19 /// important. The subexpressions of SCEV with a type X can only have a type 20 /// that is smaller or equal than X. 21 enum TYPE { 22 // An integer value. 23 INT, 24 25 // An expression that is constant during the execution of the Scop, 26 // but that may depend on parameters unknown at compile time. 27 PARAM, 28 29 // An expression that may change during the execution of the SCoP. 30 IV, 31 32 // An invalid expression. 33 INVALID 34 }; 35 } // namespace SCEVType 36 37 /// The result the validator returns for a SCEV expression. 38 class ValidatorResult { 39 /// The type of the expression 40 SCEVType::TYPE Type; 41 42 /// The set of Parameters in the expression. 43 ParameterSetTy Parameters; 44 45 public: 46 /// The copy constructor 47 ValidatorResult(const ValidatorResult &Source) { 48 Type = Source.Type; 49 Parameters = Source.Parameters; 50 } 51 52 /// Construct a result with a certain type and no parameters. 53 ValidatorResult(SCEVType::TYPE Type) : Type(Type) { 54 assert(Type != SCEVType::PARAM && "Did you forget to pass the parameter"); 55 } 56 57 /// Construct a result with a certain type and a single parameter. 58 ValidatorResult(SCEVType::TYPE Type, const SCEV *Expr) : Type(Type) { 59 Parameters.insert(Expr); 60 } 61 62 /// Get the type of the ValidatorResult. 63 SCEVType::TYPE getType() { return Type; } 64 65 /// Is the analyzed SCEV constant during the execution of the SCoP. 66 bool isConstant() { return Type == SCEVType::INT || Type == SCEVType::PARAM; } 67 68 /// Is the analyzed SCEV valid. 69 bool isValid() { return Type != SCEVType::INVALID; } 70 71 /// Is the analyzed SCEV of Type IV. 72 bool isIV() { return Type == SCEVType::IV; } 73 74 /// Is the analyzed SCEV of Type INT. 75 bool isINT() { return Type == SCEVType::INT; } 76 77 /// Is the analyzed SCEV of Type PARAM. 78 bool isPARAM() { return Type == SCEVType::PARAM; } 79 80 /// Get the parameters of this validator result. 81 const ParameterSetTy &getParameters() { return Parameters; } 82 83 /// Add the parameters of Source to this result. 84 void addParamsFrom(const ValidatorResult &Source) { 85 Parameters.insert(Source.Parameters.begin(), Source.Parameters.end()); 86 } 87 88 /// Merge a result. 89 /// 90 /// This means to merge the parameters and to set the Type to the most 91 /// specific Type that matches both. 92 void merge(const ValidatorResult &ToMerge) { 93 Type = std::max(Type, ToMerge.Type); 94 addParamsFrom(ToMerge); 95 } 96 97 void print(raw_ostream &OS) { 98 switch (Type) { 99 case SCEVType::INT: 100 OS << "SCEVType::INT"; 101 break; 102 case SCEVType::PARAM: 103 OS << "SCEVType::PARAM"; 104 break; 105 case SCEVType::IV: 106 OS << "SCEVType::IV"; 107 break; 108 case SCEVType::INVALID: 109 OS << "SCEVType::INVALID"; 110 break; 111 } 112 } 113 }; 114 115 raw_ostream &operator<<(raw_ostream &OS, class ValidatorResult &VR) { 116 VR.print(OS); 117 return OS; 118 } 119 120 /// Check if a SCEV is valid in a SCoP. 121 struct SCEVValidator 122 : public SCEVVisitor<SCEVValidator, class ValidatorResult> { 123 private: 124 const Region *R; 125 Loop *Scope; 126 ScalarEvolution &SE; 127 InvariantLoadsSetTy *ILS; 128 129 public: 130 SCEVValidator(const Region *R, Loop *Scope, ScalarEvolution &SE, 131 InvariantLoadsSetTy *ILS) 132 : R(R), Scope(Scope), SE(SE), ILS(ILS) {} 133 134 class ValidatorResult visitConstant(const SCEVConstant *Constant) { 135 return ValidatorResult(SCEVType::INT); 136 } 137 138 class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr, 139 const SCEV *Operand) { 140 ValidatorResult Op = visit(Operand); 141 auto Type = Op.getType(); 142 143 // If unsigned operations are allowed return the operand, otherwise 144 // check if we can model the expression without unsigned assumptions. 145 if (PollyAllowUnsignedOperations || Type == SCEVType::INVALID) 146 return Op; 147 148 if (Type == SCEVType::IV) 149 return ValidatorResult(SCEVType::INVALID); 150 return ValidatorResult(SCEVType::PARAM, Expr); 151 } 152 153 class ValidatorResult visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) { 154 return visit(Expr->getOperand()); 155 } 156 157 class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) { 158 return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand()); 159 } 160 161 class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { 162 return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand()); 163 } 164 165 class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { 166 return visit(Expr->getOperand()); 167 } 168 169 class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) { 170 ValidatorResult Return(SCEVType::INT); 171 172 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 173 ValidatorResult Op = visit(Expr->getOperand(i)); 174 Return.merge(Op); 175 176 // Early exit. 177 if (!Return.isValid()) 178 break; 179 } 180 181 return Return; 182 } 183 184 class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) { 185 ValidatorResult Return(SCEVType::INT); 186 187 bool HasMultipleParams = false; 188 189 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 190 ValidatorResult Op = visit(Expr->getOperand(i)); 191 192 if (Op.isINT()) 193 continue; 194 195 if (Op.isPARAM() && Return.isPARAM()) { 196 HasMultipleParams = true; 197 continue; 198 } 199 200 if ((Op.isIV() || Op.isPARAM()) && !Return.isINT()) { 201 LLVM_DEBUG( 202 dbgs() << "INVALID: More than one non-int operand in MulExpr\n" 203 << "\tExpr: " << *Expr << "\n" 204 << "\tPrevious expression type: " << Return << "\n" 205 << "\tNext operand (" << Op << "): " << *Expr->getOperand(i) 206 << "\n"); 207 208 return ValidatorResult(SCEVType::INVALID); 209 } 210 211 Return.merge(Op); 212 } 213 214 if (HasMultipleParams && Return.isValid()) 215 return ValidatorResult(SCEVType::PARAM, Expr); 216 217 return Return; 218 } 219 220 class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) { 221 if (!Expr->isAffine()) { 222 LLVM_DEBUG(dbgs() << "INVALID: AddRec is not affine"); 223 return ValidatorResult(SCEVType::INVALID); 224 } 225 226 ValidatorResult Start = visit(Expr->getStart()); 227 ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE)); 228 229 if (!Start.isValid()) 230 return Start; 231 232 if (!Recurrence.isValid()) 233 return Recurrence; 234 235 auto *L = Expr->getLoop(); 236 if (R->contains(L) && (!Scope || !L->contains(Scope))) { 237 LLVM_DEBUG( 238 dbgs() << "INVALID: Loop of AddRec expression boxed in an a " 239 "non-affine subregion or has a non-synthesizable exit " 240 "value."); 241 return ValidatorResult(SCEVType::INVALID); 242 } 243 244 if (R->contains(L)) { 245 if (Recurrence.isINT()) { 246 ValidatorResult Result(SCEVType::IV); 247 Result.addParamsFrom(Start); 248 return Result; 249 } 250 251 LLVM_DEBUG(dbgs() << "INVALID: AddRec within scop has non-int" 252 "recurrence part"); 253 return ValidatorResult(SCEVType::INVALID); 254 } 255 256 assert(Recurrence.isConstant() && "Expected 'Recurrence' to be constant"); 257 258 // Directly generate ValidatorResult for Expr if 'start' is zero. 259 if (Expr->getStart()->isZero()) 260 return ValidatorResult(SCEVType::PARAM, Expr); 261 262 // Translate AddRecExpr from '{start, +, inc}' into 'start + {0, +, inc}' 263 // if 'start' is not zero. 264 const SCEV *ZeroStartExpr = SE.getAddRecExpr( 265 SE.getConstant(Expr->getStart()->getType(), 0), 266 Expr->getStepRecurrence(SE), Expr->getLoop(), Expr->getNoWrapFlags()); 267 268 ValidatorResult ZeroStartResult = 269 ValidatorResult(SCEVType::PARAM, ZeroStartExpr); 270 ZeroStartResult.addParamsFrom(Start); 271 272 return ZeroStartResult; 273 } 274 275 class ValidatorResult visitSMaxExpr(const SCEVSMaxExpr *Expr) { 276 ValidatorResult Return(SCEVType::INT); 277 278 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 279 ValidatorResult Op = visit(Expr->getOperand(i)); 280 281 if (!Op.isValid()) 282 return Op; 283 284 Return.merge(Op); 285 } 286 287 return Return; 288 } 289 290 class ValidatorResult visitSMinExpr(const SCEVSMinExpr *Expr) { 291 ValidatorResult Return(SCEVType::INT); 292 293 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 294 ValidatorResult Op = visit(Expr->getOperand(i)); 295 296 if (!Op.isValid()) 297 return Op; 298 299 Return.merge(Op); 300 } 301 302 return Return; 303 } 304 305 class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) { 306 // We do not support unsigned max operations. If 'Expr' is constant during 307 // Scop execution we treat this as a parameter, otherwise we bail out. 308 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 309 ValidatorResult Op = visit(Expr->getOperand(i)); 310 311 if (!Op.isConstant()) { 312 LLVM_DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand"); 313 return ValidatorResult(SCEVType::INVALID); 314 } 315 } 316 317 return ValidatorResult(SCEVType::PARAM, Expr); 318 } 319 320 class ValidatorResult visitUMinExpr(const SCEVUMinExpr *Expr) { 321 // We do not support unsigned min operations. If 'Expr' is constant during 322 // Scop execution we treat this as a parameter, otherwise we bail out. 323 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 324 ValidatorResult Op = visit(Expr->getOperand(i)); 325 326 if (!Op.isConstant()) { 327 LLVM_DEBUG(dbgs() << "INVALID: UMinExpr has a non-constant operand"); 328 return ValidatorResult(SCEVType::INVALID); 329 } 330 } 331 332 return ValidatorResult(SCEVType::PARAM, Expr); 333 } 334 335 class ValidatorResult 336 visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Expr) { 337 // We do not support unsigned min operations. If 'Expr' is constant during 338 // Scop execution we treat this as a parameter, otherwise we bail out. 339 for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { 340 ValidatorResult Op = visit(Expr->getOperand(i)); 341 342 if (!Op.isConstant()) { 343 LLVM_DEBUG( 344 dbgs() 345 << "INVALID: SCEVSequentialUMinExpr has a non-constant operand"); 346 return ValidatorResult(SCEVType::INVALID); 347 } 348 } 349 350 return ValidatorResult(SCEVType::PARAM, Expr); 351 } 352 353 ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) { 354 if (R->contains(I)) { 355 LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction " 356 "within the region\n"); 357 return ValidatorResult(SCEVType::INVALID); 358 } 359 360 return ValidatorResult(SCEVType::PARAM, S); 361 } 362 363 ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) { 364 if (R->contains(I) && ILS) { 365 ILS->insert(cast<LoadInst>(I)); 366 return ValidatorResult(SCEVType::PARAM, S); 367 } 368 369 return visitGenericInst(I, S); 370 } 371 372 ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor, 373 const SCEV *DivExpr, 374 Instruction *SDiv = nullptr) { 375 376 // First check if we might be able to model the division, thus if the 377 // divisor is constant. If so, check the dividend, otherwise check if 378 // the whole division can be seen as a parameter. 379 if (isa<SCEVConstant>(Divisor) && !Divisor->isZero()) 380 return visit(Dividend); 381 382 // For signed divisions use the SDiv instruction to check for a parameter 383 // division, for unsigned divisions check the operands. 384 if (SDiv) 385 return visitGenericInst(SDiv, DivExpr); 386 387 ValidatorResult LHS = visit(Dividend); 388 ValidatorResult RHS = visit(Divisor); 389 if (LHS.isConstant() && RHS.isConstant()) 390 return ValidatorResult(SCEVType::PARAM, DivExpr); 391 392 LLVM_DEBUG( 393 dbgs() << "INVALID: unsigned division of non-constant expressions"); 394 return ValidatorResult(SCEVType::INVALID); 395 } 396 397 ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) { 398 if (!PollyAllowUnsignedOperations) 399 return ValidatorResult(SCEVType::INVALID); 400 401 auto *Dividend = Expr->getLHS(); 402 auto *Divisor = Expr->getRHS(); 403 return visitDivision(Dividend, Divisor, Expr); 404 } 405 406 ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) { 407 assert(SDiv->getOpcode() == Instruction::SDiv && 408 "Assumed SDiv instruction!"); 409 410 auto *Dividend = SE.getSCEV(SDiv->getOperand(0)); 411 auto *Divisor = SE.getSCEV(SDiv->getOperand(1)); 412 return visitDivision(Dividend, Divisor, Expr, SDiv); 413 } 414 415 ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) { 416 assert(SRem->getOpcode() == Instruction::SRem && 417 "Assumed SRem instruction!"); 418 419 auto *Divisor = SRem->getOperand(1); 420 auto *CI = dyn_cast<ConstantInt>(Divisor); 421 if (!CI || CI->isZeroValue()) 422 return visitGenericInst(SRem, S); 423 424 auto *Dividend = SRem->getOperand(0); 425 auto *DividendSCEV = SE.getSCEV(Dividend); 426 return visit(DividendSCEV); 427 } 428 429 ValidatorResult visitUnknown(const SCEVUnknown *Expr) { 430 Value *V = Expr->getValue(); 431 432 if (!Expr->getType()->isIntegerTy() && !Expr->getType()->isPointerTy()) { 433 LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer"); 434 return ValidatorResult(SCEVType::INVALID); 435 } 436 437 if (isa<UndefValue>(V)) { 438 LLVM_DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value"); 439 return ValidatorResult(SCEVType::INVALID); 440 } 441 442 if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) { 443 switch (I->getOpcode()) { 444 case Instruction::IntToPtr: 445 return visit(SE.getSCEVAtScope(I->getOperand(0), Scope)); 446 case Instruction::Load: 447 return visitLoadInstruction(I, Expr); 448 case Instruction::SDiv: 449 return visitSDivInstruction(I, Expr); 450 case Instruction::SRem: 451 return visitSRemInstruction(I, Expr); 452 default: 453 return visitGenericInst(I, Expr); 454 } 455 } 456 457 if (Expr->getType()->isPointerTy()) { 458 if (isa<ConstantPointerNull>(V)) 459 return ValidatorResult(SCEVType::INT); // "int" 460 } 461 462 return ValidatorResult(SCEVType::PARAM, Expr); 463 } 464 }; 465 466 /// Check whether a SCEV refers to an SSA name defined inside a region. 467 class SCEVInRegionDependences { 468 const Region *R; 469 Loop *Scope; 470 const InvariantLoadsSetTy &ILS; 471 bool AllowLoops; 472 bool HasInRegionDeps = false; 473 474 public: 475 SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops, 476 const InvariantLoadsSetTy &ILS) 477 : R(R), Scope(Scope), ILS(ILS), AllowLoops(AllowLoops) {} 478 479 bool follow(const SCEV *S) { 480 if (auto Unknown = dyn_cast<SCEVUnknown>(S)) { 481 Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue()); 482 483 if (Inst) { 484 // When we invariant load hoist a load, we first make sure that there 485 // can be no dependences created by it in the Scop region. So, we should 486 // not consider scalar dependences to `LoadInst`s that are invariant 487 // load hoisted. 488 // 489 // If this check is not present, then we create data dependences which 490 // are strictly not necessary by tracking the invariant load as a 491 // scalar. 492 LoadInst *LI = dyn_cast<LoadInst>(Inst); 493 if (LI && ILS.contains(LI)) 494 return false; 495 } 496 497 // Return true when Inst is defined inside the region R. 498 if (!Inst || !R->contains(Inst)) 499 return true; 500 501 HasInRegionDeps = true; 502 return false; 503 } 504 505 if (auto AddRec = dyn_cast<SCEVAddRecExpr>(S)) { 506 if (AllowLoops) 507 return true; 508 509 auto *L = AddRec->getLoop(); 510 if (R->contains(L) && !L->contains(Scope)) { 511 HasInRegionDeps = true; 512 return false; 513 } 514 } 515 516 return true; 517 } 518 bool isDone() { return false; } 519 bool hasDependences() { return HasInRegionDeps; } 520 }; 521 522 namespace polly { 523 /// Find all loops referenced in SCEVAddRecExprs. 524 class SCEVFindLoops { 525 SetVector<const Loop *> &Loops; 526 527 public: 528 SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {} 529 530 bool follow(const SCEV *S) { 531 if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S)) 532 Loops.insert(AddRec->getLoop()); 533 return true; 534 } 535 bool isDone() { return false; } 536 }; 537 538 void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) { 539 SCEVFindLoops FindLoops(Loops); 540 SCEVTraversal<SCEVFindLoops> ST(FindLoops); 541 ST.visitAll(Expr); 542 } 543 544 /// Find all values referenced in SCEVUnknowns. 545 class SCEVFindValues { 546 ScalarEvolution &SE; 547 SetVector<Value *> &Values; 548 549 public: 550 SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values) 551 : SE(SE), Values(Values) {} 552 553 bool follow(const SCEV *S) { 554 const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S); 555 if (!Unknown) 556 return true; 557 558 Values.insert(Unknown->getValue()); 559 Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue()); 560 if (!Inst || (Inst->getOpcode() != Instruction::SRem && 561 Inst->getOpcode() != Instruction::SDiv)) 562 return false; 563 564 auto *Dividend = SE.getSCEV(Inst->getOperand(1)); 565 if (!isa<SCEVConstant>(Dividend)) 566 return false; 567 568 auto *Divisor = SE.getSCEV(Inst->getOperand(0)); 569 SCEVFindValues FindValues(SE, Values); 570 SCEVTraversal<SCEVFindValues> ST(FindValues); 571 ST.visitAll(Dividend); 572 ST.visitAll(Divisor); 573 574 return false; 575 } 576 bool isDone() { return false; } 577 }; 578 579 void findValues(const SCEV *Expr, ScalarEvolution &SE, 580 SetVector<Value *> &Values) { 581 SCEVFindValues FindValues(SE, Values); 582 SCEVTraversal<SCEVFindValues> ST(FindValues); 583 ST.visitAll(Expr); 584 } 585 586 bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R, 587 llvm::Loop *Scope, bool AllowLoops, 588 const InvariantLoadsSetTy &ILS) { 589 SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops, ILS); 590 SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps); 591 ST.visitAll(Expr); 592 return InRegionDeps.hasDependences(); 593 } 594 595 bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr, 596 ScalarEvolution &SE, InvariantLoadsSetTy *ILS) { 597 if (isa<SCEVCouldNotCompute>(Expr)) 598 return false; 599 600 SCEVValidator Validator(R, Scope, SE, ILS); 601 LLVM_DEBUG({ 602 dbgs() << "\n"; 603 dbgs() << "Expr: " << *Expr << "\n"; 604 dbgs() << "Region: " << R->getNameStr() << "\n"; 605 dbgs() << " -> "; 606 }); 607 608 ValidatorResult Result = Validator.visit(Expr); 609 610 LLVM_DEBUG({ 611 if (Result.isValid()) 612 dbgs() << "VALID\n"; 613 dbgs() << "\n"; 614 }); 615 616 return Result.isValid(); 617 } 618 619 static bool isAffineExpr(Value *V, const Region *R, Loop *Scope, 620 ScalarEvolution &SE, ParameterSetTy &Params) { 621 auto *E = SE.getSCEV(V); 622 if (isa<SCEVCouldNotCompute>(E)) 623 return false; 624 625 SCEVValidator Validator(R, Scope, SE, nullptr); 626 ValidatorResult Result = Validator.visit(E); 627 if (!Result.isValid()) 628 return false; 629 630 auto ResultParams = Result.getParameters(); 631 Params.insert(ResultParams.begin(), ResultParams.end()); 632 633 return true; 634 } 635 636 bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope, 637 ScalarEvolution &SE, ParameterSetTy &Params, 638 bool OrExpr) { 639 if (auto *ICmp = dyn_cast<ICmpInst>(V)) { 640 return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params, 641 true) && 642 isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true); 643 } else if (auto *BinOp = dyn_cast<BinaryOperator>(V)) { 644 auto Opcode = BinOp->getOpcode(); 645 if (Opcode == Instruction::And || Opcode == Instruction::Or) 646 return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params, 647 false) && 648 isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params, 649 false); 650 /* Fall through */ 651 } 652 653 if (!OrExpr) 654 return false; 655 656 return isAffineExpr(V, R, Scope, SE, Params); 657 } 658 659 ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope, 660 const SCEV *Expr, ScalarEvolution &SE) { 661 if (isa<SCEVCouldNotCompute>(Expr)) 662 return ParameterSetTy(); 663 664 InvariantLoadsSetTy ILS; 665 SCEVValidator Validator(R, Scope, SE, &ILS); 666 ValidatorResult Result = Validator.visit(Expr); 667 assert(Result.isValid() && "Requested parameters for an invalid SCEV!"); 668 669 return Result.getParameters(); 670 } 671 672 std::pair<const SCEVConstant *, const SCEV *> 673 extractConstantFactor(const SCEV *S, ScalarEvolution &SE) { 674 auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1)); 675 676 if (auto *Constant = dyn_cast<SCEVConstant>(S)) 677 return std::make_pair(Constant, SE.getConstant(S->getType(), 1)); 678 679 auto *AddRec = dyn_cast<SCEVAddRecExpr>(S); 680 if (AddRec) { 681 auto *StartExpr = AddRec->getStart(); 682 if (StartExpr->isZero()) { 683 auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE); 684 auto *LeftOverAddRec = 685 SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(), 686 AddRec->getNoWrapFlags()); 687 return std::make_pair(StepPair.first, LeftOverAddRec); 688 } 689 return std::make_pair(ConstPart, S); 690 } 691 692 if (auto *Add = dyn_cast<SCEVAddExpr>(S)) { 693 SmallVector<const SCEV *, 4> LeftOvers; 694 auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE); 695 auto *Factor = Op0Pair.first; 696 if (SE.isKnownNegative(Factor)) { 697 Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor)); 698 LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second)); 699 } else { 700 LeftOvers.push_back(Op0Pair.second); 701 } 702 703 for (unsigned u = 1, e = Add->getNumOperands(); u < e; u++) { 704 auto OpUPair = extractConstantFactor(Add->getOperand(u), SE); 705 // TODO: Use something smarter than equality here, e.g., gcd. 706 if (Factor == OpUPair.first) 707 LeftOvers.push_back(OpUPair.second); 708 else if (Factor == SE.getNegativeSCEV(OpUPair.first)) 709 LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second)); 710 else 711 return std::make_pair(ConstPart, S); 712 } 713 714 auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags()); 715 return std::make_pair(Factor, NewAdd); 716 } 717 718 auto *Mul = dyn_cast<SCEVMulExpr>(S); 719 if (!Mul) 720 return std::make_pair(ConstPart, S); 721 722 SmallVector<const SCEV *, 4> LeftOvers; 723 for (auto *Op : Mul->operands()) 724 if (isa<SCEVConstant>(Op)) 725 ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op)); 726 else 727 LeftOvers.push_back(Op); 728 729 return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers)); 730 } 731 732 const SCEV *tryForwardThroughPHI(const SCEV *Expr, Region &R, 733 ScalarEvolution &SE, ScopDetection *SD) { 734 if (auto *Unknown = dyn_cast<SCEVUnknown>(Expr)) { 735 Value *V = Unknown->getValue(); 736 auto *PHI = dyn_cast<PHINode>(V); 737 if (!PHI) 738 return Expr; 739 740 Value *Final = nullptr; 741 742 for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) { 743 BasicBlock *Incoming = PHI->getIncomingBlock(i); 744 if (SD->isErrorBlock(*Incoming, R) && R.contains(Incoming)) 745 continue; 746 if (Final) 747 return Expr; 748 Final = PHI->getIncomingValue(i); 749 } 750 751 if (Final) 752 return SE.getSCEV(Final); 753 } 754 return Expr; 755 } 756 757 Value *getUniqueNonErrorValue(PHINode *PHI, Region *R, ScopDetection *SD) { 758 Value *V = nullptr; 759 for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) { 760 BasicBlock *BB = PHI->getIncomingBlock(i); 761 if (!SD->isErrorBlock(*BB, *R)) { 762 if (V) 763 return nullptr; 764 V = PHI->getIncomingValue(i); 765 } 766 } 767 768 return V; 769 } 770 } // namespace polly 771