xref: /llvm-project/polly/lib/Support/SCEVValidator.cpp (revision 82fb4f4b223d78e86647f3576e41e3086ab42cd5)
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