xref: /llvm-project/polly/lib/Support/SCEVValidator.cpp (revision 62d11b2ccaeec8abc12e07aa009c922d72fd6377) 
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 }
776