polly/lib/Support/SCEVValidator.cpp

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