xref: /llvm-project/polly/lib/Support/SCEVValidator.cpp (revision f5e7e60bc8dc362dd98107d6db41b9b758ecbf20) 
1 
2 #include "polly/Support/SCEVValidator.h"
3 #include "polly/ScopInfo.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 bool polly::isConstCall(llvm::CallInst *Call) {
121   if (Call->mayReadOrWriteMemory())
122     return false;
123 
124   for (auto &Operand : Call->arg_operands())
125     if (!isa<ConstantInt>(&Operand))
126       return false;
127 
128   return true;
129 }
130 
131 /// Check if a SCEV is valid in a SCoP.
132 struct SCEVValidator
133     : public SCEVVisitor<SCEVValidator, class ValidatorResult> {
134 private:
135   const Region *R;
136   Loop *Scope;
137   ScalarEvolution &SE;
138   InvariantLoadsSetTy *ILS;
139 
140 public:
141   SCEVValidator(const Region *R, Loop *Scope, ScalarEvolution &SE,
142                 InvariantLoadsSetTy *ILS)
143       : R(R), Scope(Scope), SE(SE), ILS(ILS) {}
144 
145   class ValidatorResult visitConstant(const SCEVConstant *Constant) {
146     return ValidatorResult(SCEVType::INT);
147   }
148 
149   class ValidatorResult visitZeroExtendOrTruncateExpr(const SCEV *Expr,
150                                                       const SCEV *Operand) {
151     ValidatorResult Op = visit(Operand);
152     auto Type = Op.getType();
153 
154     // If unsigned operations are allowed return the operand, otherwise
155     // check if we can model the expression without unsigned assumptions.
156     if (PollyAllowUnsignedOperations || Type == SCEVType::INVALID)
157       return Op;
158 
159     if (Type == SCEVType::IV)
160       return ValidatorResult(SCEVType::INVALID);
161     return ValidatorResult(SCEVType::PARAM, Expr);
162   }
163 
164   class ValidatorResult visitTruncateExpr(const SCEVTruncateExpr *Expr) {
165     return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
166   }
167 
168   class ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
169     return visitZeroExtendOrTruncateExpr(Expr, Expr->getOperand());
170   }
171 
172   class ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
173     return visit(Expr->getOperand());
174   }
175 
176   class ValidatorResult visitAddExpr(const SCEVAddExpr *Expr) {
177     ValidatorResult Return(SCEVType::INT);
178 
179     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
180       ValidatorResult Op = visit(Expr->getOperand(i));
181       Return.merge(Op);
182 
183       // Early exit.
184       if (!Return.isValid())
185         break;
186     }
187 
188     return Return;
189   }
190 
191   class ValidatorResult visitMulExpr(const SCEVMulExpr *Expr) {
192     ValidatorResult Return(SCEVType::INT);
193 
194     bool HasMultipleParams = false;
195 
196     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
197       ValidatorResult Op = visit(Expr->getOperand(i));
198 
199       if (Op.isINT())
200         continue;
201 
202       if (Op.isPARAM() && Return.isPARAM()) {
203         HasMultipleParams = true;
204         continue;
205       }
206 
207       if ((Op.isIV() || Op.isPARAM()) && !Return.isINT()) {
208         DEBUG(dbgs() << "INVALID: More than one non-int operand in MulExpr\n"
209                      << "\tExpr: " << *Expr << "\n"
210                      << "\tPrevious expression type: " << Return << "\n"
211                      << "\tNext operand (" << Op
212                      << "): " << *Expr->getOperand(i) << "\n");
213 
214         return ValidatorResult(SCEVType::INVALID);
215       }
216 
217       Return.merge(Op);
218     }
219 
220     if (HasMultipleParams && Return.isValid())
221       return ValidatorResult(SCEVType::PARAM, Expr);
222 
223     return Return;
224   }
225 
226   class ValidatorResult visitAddRecExpr(const SCEVAddRecExpr *Expr) {
227     if (!Expr->isAffine()) {
228       DEBUG(dbgs() << "INVALID: AddRec is not affine");
229       return ValidatorResult(SCEVType::INVALID);
230     }
231 
232     ValidatorResult Start = visit(Expr->getStart());
233     ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE));
234 
235     if (!Start.isValid())
236       return Start;
237 
238     if (!Recurrence.isValid())
239       return Recurrence;
240 
241     auto *L = Expr->getLoop();
242     if (R->contains(L) && (!Scope || !L->contains(Scope))) {
243       DEBUG(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       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   class 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   class ValidatorResult visitUMaxExpr(const SCEVUMaxExpr *Expr) {
296     // We do not support unsigned max operations. If 'Expr' is constant during
297     // Scop execution we treat this as a parameter, otherwise we bail out.
298     for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) {
299       ValidatorResult Op = visit(Expr->getOperand(i));
300 
301       if (!Op.isConstant()) {
302         DEBUG(dbgs() << "INVALID: UMaxExpr has a non-constant operand");
303         return ValidatorResult(SCEVType::INVALID);
304       }
305     }
306 
307     return ValidatorResult(SCEVType::PARAM, Expr);
308   }
309 
310   ValidatorResult visitGenericInst(Instruction *I, const SCEV *S) {
311     if (R->contains(I)) {
312       DEBUG(dbgs() << "INVALID: UnknownExpr references an instruction "
313                       "within the region\n");
314       return ValidatorResult(SCEVType::INVALID);
315     }
316 
317     return ValidatorResult(SCEVType::PARAM, S);
318   }
319 
320   ValidatorResult visitCallInstruction(Instruction *I, const SCEV *S) {
321     assert(I->getOpcode() == Instruction::Call && "Call instruction expected");
322 
323     auto Call = cast<CallInst>(I);
324 
325     if (!isConstCall(Call))
326       return ValidatorResult(SCEVType::INVALID, S);
327 
328     return ValidatorResult(SCEVType::PARAM, S);
329   }
330 
331   ValidatorResult visitLoadInstruction(Instruction *I, const SCEV *S) {
332     if (R->contains(I) && ILS) {
333       ILS->insert(cast<LoadInst>(I));
334       return ValidatorResult(SCEVType::PARAM, S);
335     }
336 
337     return visitGenericInst(I, S);
338   }
339 
340   ValidatorResult visitDivision(const SCEV *Dividend, const SCEV *Divisor,
341                                 const SCEV *DivExpr,
342                                 Instruction *SDiv = nullptr) {
343 
344     // First check if we might be able to model the division, thus if the
345     // divisor is constant. If so, check the dividend, otherwise check if
346     // the whole division can be seen as a parameter.
347     if (isa<SCEVConstant>(Divisor) && !Divisor->isZero())
348       return visit(Dividend);
349 
350     // For signed divisions use the SDiv instruction to check for a parameter
351     // division, for unsigned divisions check the operands.
352     if (SDiv)
353       return visitGenericInst(SDiv, DivExpr);
354 
355     ValidatorResult LHS = visit(Dividend);
356     ValidatorResult RHS = visit(Divisor);
357     if (LHS.isConstant() && RHS.isConstant())
358       return ValidatorResult(SCEVType::PARAM, DivExpr);
359 
360     DEBUG(dbgs() << "INVALID: unsigned division of non-constant expressions");
361     return ValidatorResult(SCEVType::INVALID);
362   }
363 
364   ValidatorResult visitUDivExpr(const SCEVUDivExpr *Expr) {
365     if (!PollyAllowUnsignedOperations)
366       return ValidatorResult(SCEVType::INVALID);
367 
368     auto *Dividend = Expr->getLHS();
369     auto *Divisor = Expr->getRHS();
370     return visitDivision(Dividend, Divisor, Expr);
371   }
372 
373   ValidatorResult visitSDivInstruction(Instruction *SDiv, const SCEV *Expr) {
374     assert(SDiv->getOpcode() == Instruction::SDiv &&
375            "Assumed SDiv instruction!");
376 
377     auto *Dividend = SE.getSCEV(SDiv->getOperand(0));
378     auto *Divisor = SE.getSCEV(SDiv->getOperand(1));
379     return visitDivision(Dividend, Divisor, Expr, SDiv);
380   }
381 
382   ValidatorResult visitSRemInstruction(Instruction *SRem, const SCEV *S) {
383     assert(SRem->getOpcode() == Instruction::SRem &&
384            "Assumed SRem instruction!");
385 
386     auto *Divisor = SRem->getOperand(1);
387     auto *CI = dyn_cast<ConstantInt>(Divisor);
388     if (!CI || CI->isZeroValue())
389       return visitGenericInst(SRem, S);
390 
391     auto *Dividend = SRem->getOperand(0);
392     auto *DividendSCEV = SE.getSCEV(Dividend);
393     return visit(DividendSCEV);
394   }
395 
396   ValidatorResult visitUnknown(const SCEVUnknown *Expr) {
397     Value *V = Expr->getValue();
398 
399     if (!Expr->getType()->isIntegerTy() && !Expr->getType()->isPointerTy()) {
400       DEBUG(dbgs() << "INVALID: UnknownExpr is not an integer or pointer");
401       return ValidatorResult(SCEVType::INVALID);
402     }
403 
404     if (isa<UndefValue>(V)) {
405       DEBUG(dbgs() << "INVALID: UnknownExpr references an undef value");
406       return ValidatorResult(SCEVType::INVALID);
407     }
408 
409     if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) {
410       switch (I->getOpcode()) {
411       case Instruction::IntToPtr:
412         return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
413       case Instruction::PtrToInt:
414         return visit(SE.getSCEVAtScope(I->getOperand(0), Scope));
415       case Instruction::Load:
416         return visitLoadInstruction(I, Expr);
417       case Instruction::SDiv:
418         return visitSDivInstruction(I, Expr);
419       case Instruction::SRem:
420         return visitSRemInstruction(I, Expr);
421       case Instruction::Call:
422         return visitCallInstruction(I, Expr);
423       default:
424         return visitGenericInst(I, Expr);
425       }
426     }
427 
428     return ValidatorResult(SCEVType::PARAM, Expr);
429   }
430 };
431 
432 /// Check whether a SCEV refers to an SSA name defined inside a region.
433 class SCEVInRegionDependences {
434   const Region *R;
435   Loop *Scope;
436   bool AllowLoops;
437   bool HasInRegionDeps = false;
438 
439 public:
440   SCEVInRegionDependences(const Region *R, Loop *Scope, bool AllowLoops)
441       : R(R), Scope(Scope), AllowLoops(AllowLoops) {}
442 
443   bool follow(const SCEV *S) {
444     if (auto Unknown = dyn_cast<SCEVUnknown>(S)) {
445       Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
446 
447       CallInst *Call = dyn_cast<CallInst>(Unknown->getValue());
448 
449       if (Call && isConstCall(Call))
450         return false;
451 
452       // Return true when Inst is defined inside the region R.
453       if (!Inst || !R->contains(Inst))
454         return true;
455 
456       HasInRegionDeps = true;
457       return false;
458     }
459 
460     if (auto AddRec = dyn_cast<SCEVAddRecExpr>(S)) {
461       if (AllowLoops)
462         return true;
463 
464       if (!Scope) {
465         HasInRegionDeps = true;
466         return false;
467       }
468       auto *L = AddRec->getLoop();
469       if (R->contains(L) && !L->contains(Scope)) {
470         HasInRegionDeps = true;
471         return false;
472       }
473     }
474 
475     return true;
476   }
477   bool isDone() { return false; }
478   bool hasDependences() { return HasInRegionDeps; }
479 };
480 
481 namespace polly {
482 /// Find all loops referenced in SCEVAddRecExprs.
483 class SCEVFindLoops {
484   SetVector<const Loop *> &Loops;
485 
486 public:
487   SCEVFindLoops(SetVector<const Loop *> &Loops) : Loops(Loops) {}
488 
489   bool follow(const SCEV *S) {
490     if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(S))
491       Loops.insert(AddRec->getLoop());
492     return true;
493   }
494   bool isDone() { return false; }
495 };
496 
497 void findLoops(const SCEV *Expr, SetVector<const Loop *> &Loops) {
498   SCEVFindLoops FindLoops(Loops);
499   SCEVTraversal<SCEVFindLoops> ST(FindLoops);
500   ST.visitAll(Expr);
501 }
502 
503 /// Find all values referenced in SCEVUnknowns.
504 class SCEVFindValues {
505   ScalarEvolution &SE;
506   SetVector<Value *> &Values;
507 
508 public:
509   SCEVFindValues(ScalarEvolution &SE, SetVector<Value *> &Values)
510       : SE(SE), Values(Values) {}
511 
512   bool follow(const SCEV *S) {
513     const SCEVUnknown *Unknown = dyn_cast<SCEVUnknown>(S);
514     if (!Unknown)
515       return true;
516 
517     Values.insert(Unknown->getValue());
518     Instruction *Inst = dyn_cast<Instruction>(Unknown->getValue());
519     if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
520                   Inst->getOpcode() != Instruction::SDiv))
521       return false;
522 
523     auto *Dividend = SE.getSCEV(Inst->getOperand(1));
524     if (!isa<SCEVConstant>(Dividend))
525       return false;
526 
527     auto *Divisor = SE.getSCEV(Inst->getOperand(0));
528     SCEVFindValues FindValues(SE, Values);
529     SCEVTraversal<SCEVFindValues> ST(FindValues);
530     ST.visitAll(Dividend);
531     ST.visitAll(Divisor);
532 
533     return false;
534   }
535   bool isDone() { return false; }
536 };
537 
538 void findValues(const SCEV *Expr, ScalarEvolution &SE,
539                 SetVector<Value *> &Values) {
540   SCEVFindValues FindValues(SE, Values);
541   SCEVTraversal<SCEVFindValues> ST(FindValues);
542   ST.visitAll(Expr);
543 }
544 
545 bool hasScalarDepsInsideRegion(const SCEV *Expr, const Region *R,
546                                llvm::Loop *Scope, bool AllowLoops) {
547   SCEVInRegionDependences InRegionDeps(R, Scope, AllowLoops);
548   SCEVTraversal<SCEVInRegionDependences> ST(InRegionDeps);
549   ST.visitAll(Expr);
550   return InRegionDeps.hasDependences();
551 }
552 
553 bool isAffineExpr(const Region *R, llvm::Loop *Scope, const SCEV *Expr,
554                   ScalarEvolution &SE, InvariantLoadsSetTy *ILS) {
555   if (isa<SCEVCouldNotCompute>(Expr))
556     return false;
557 
558   SCEVValidator Validator(R, Scope, SE, ILS);
559   DEBUG({
560     dbgs() << "\n";
561     dbgs() << "Expr: " << *Expr << "\n";
562     dbgs() << "Region: " << R->getNameStr() << "\n";
563     dbgs() << " -> ";
564   });
565 
566   ValidatorResult Result = Validator.visit(Expr);
567 
568   DEBUG({
569     if (Result.isValid())
570       dbgs() << "VALID\n";
571     dbgs() << "\n";
572   });
573 
574   return Result.isValid();
575 }
576 
577 static bool isAffineExpr(Value *V, const Region *R, Loop *Scope,
578                          ScalarEvolution &SE, ParameterSetTy &Params) {
579   auto *E = SE.getSCEV(V);
580   if (isa<SCEVCouldNotCompute>(E))
581     return false;
582 
583   SCEVValidator Validator(R, Scope, SE, nullptr);
584   ValidatorResult Result = Validator.visit(E);
585   if (!Result.isValid())
586     return false;
587 
588   auto ResultParams = Result.getParameters();
589   Params.insert(ResultParams.begin(), ResultParams.end());
590 
591   return true;
592 }
593 
594 bool isAffineConstraint(Value *V, const Region *R, llvm::Loop *Scope,
595                         ScalarEvolution &SE, ParameterSetTy &Params,
596                         bool OrExpr) {
597   if (auto *ICmp = dyn_cast<ICmpInst>(V)) {
598     return isAffineConstraint(ICmp->getOperand(0), R, Scope, SE, Params,
599                               true) &&
600            isAffineConstraint(ICmp->getOperand(1), R, Scope, SE, Params, true);
601   } else if (auto *BinOp = dyn_cast<BinaryOperator>(V)) {
602     auto Opcode = BinOp->getOpcode();
603     if (Opcode == Instruction::And || Opcode == Instruction::Or)
604       return isAffineConstraint(BinOp->getOperand(0), R, Scope, SE, Params,
605                                 false) &&
606              isAffineConstraint(BinOp->getOperand(1), R, Scope, SE, Params,
607                                 false);
608     /* Fall through */
609   }
610 
611   if (!OrExpr)
612     return false;
613 
614   return isAffineExpr(V, R, Scope, SE, Params);
615 }
616 
617 ParameterSetTy getParamsInAffineExpr(const Region *R, Loop *Scope,
618                                      const SCEV *Expr, ScalarEvolution &SE) {
619   if (isa<SCEVCouldNotCompute>(Expr))
620     return ParameterSetTy();
621 
622   InvariantLoadsSetTy ILS;
623   SCEVValidator Validator(R, Scope, SE, &ILS);
624   ValidatorResult Result = Validator.visit(Expr);
625   assert(Result.isValid() && "Requested parameters for an invalid SCEV!");
626 
627   return Result.getParameters();
628 }
629 
630 std::pair<const SCEVConstant *, const SCEV *>
631 extractConstantFactor(const SCEV *S, ScalarEvolution &SE) {
632   auto *ConstPart = cast<SCEVConstant>(SE.getConstant(S->getType(), 1));
633 
634   if (auto *Constant = dyn_cast<SCEVConstant>(S))
635     return std::make_pair(Constant, SE.getConstant(S->getType(), 1));
636 
637   auto *AddRec = dyn_cast<SCEVAddRecExpr>(S);
638   if (AddRec) {
639     auto *StartExpr = AddRec->getStart();
640     if (StartExpr->isZero()) {
641       auto StepPair = extractConstantFactor(AddRec->getStepRecurrence(SE), SE);
642       auto *LeftOverAddRec =
643           SE.getAddRecExpr(StartExpr, StepPair.second, AddRec->getLoop(),
644                            AddRec->getNoWrapFlags());
645       return std::make_pair(StepPair.first, LeftOverAddRec);
646     }
647     return std::make_pair(ConstPart, S);
648   }
649 
650   if (auto *Add = dyn_cast<SCEVAddExpr>(S)) {
651     SmallVector<const SCEV *, 4> LeftOvers;
652     auto Op0Pair = extractConstantFactor(Add->getOperand(0), SE);
653     auto *Factor = Op0Pair.first;
654     if (SE.isKnownNegative(Factor)) {
655       Factor = cast<SCEVConstant>(SE.getNegativeSCEV(Factor));
656       LeftOvers.push_back(SE.getNegativeSCEV(Op0Pair.second));
657     } else {
658       LeftOvers.push_back(Op0Pair.second);
659     }
660 
661     for (unsigned u = 1, e = Add->getNumOperands(); u < e; u++) {
662       auto OpUPair = extractConstantFactor(Add->getOperand(u), SE);
663       // TODO: Use something smarter than equality here, e.g., gcd.
664       if (Factor == OpUPair.first)
665         LeftOvers.push_back(OpUPair.second);
666       else if (Factor == SE.getNegativeSCEV(OpUPair.first))
667         LeftOvers.push_back(SE.getNegativeSCEV(OpUPair.second));
668       else
669         return std::make_pair(ConstPart, S);
670     }
671 
672     auto *NewAdd = SE.getAddExpr(LeftOvers, Add->getNoWrapFlags());
673     return std::make_pair(Factor, NewAdd);
674   }
675 
676   auto *Mul = dyn_cast<SCEVMulExpr>(S);
677   if (!Mul)
678     return std::make_pair(ConstPart, S);
679 
680   SmallVector<const SCEV *, 4> LeftOvers;
681   for (auto *Op : Mul->operands())
682     if (isa<SCEVConstant>(Op))
683       ConstPart = cast<SCEVConstant>(SE.getMulExpr(ConstPart, Op));
684     else
685       LeftOvers.push_back(Op);
686 
687   return std::make_pair(ConstPart, SE.getMulExpr(LeftOvers));
688 }
689 } // namespace polly
690