+/// FactorOutConstant - Test if S is divisible by Factor, using signed
+/// division. If so, update S with Factor divided out and return true.
+/// S need not be evenly divisble if a reasonable remainder can be
+/// computed.
+/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made
+/// unnecessary; in its place, just signed-divide Ops[i] by the scale and
+/// check to see if the divide was folded.
+static bool FactorOutConstant(const SCEV *&S,
+ const SCEV *&Remainder,
+ const APInt &Factor,
+ ScalarEvolution &SE) {
+ // Everything is divisible by one.
+ if (Factor == 1)
+ return true;
+
+ // For a Constant, check for a multiple of the given factor.
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) {
+ ConstantInt *CI =
+ ConstantInt::get(SE.getContext(), C->getValue()->getValue().sdiv(Factor));
+ // If the quotient is zero and the remainder is non-zero, reject
+ // the value at this scale. It will be considered for subsequent
+ // smaller scales.
+ if (C->isZero() || !CI->isZero()) {
+ const SCEV *Div = SE.getConstant(CI);
+ S = Div;
+ Remainder =
+ SE.getAddExpr(Remainder,
+ SE.getConstant(C->getValue()->getValue().srem(Factor)));
+ return true;
+ }
+ }
+
+ // In a Mul, check if there is a constant operand which is a multiple
+ // of the given factor.
+ if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S))
+ if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0)))
+ if (!C->getValue()->getValue().srem(Factor)) {
+ const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands();
+ SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(),
+ MOperands.end());
+ NewMulOps[0] =
+ SE.getConstant(C->getValue()->getValue().sdiv(Factor));
+ S = SE.getMulExpr(NewMulOps);
+ return true;
+ }
+
+ // In an AddRec, check if both start and step are divisible.
+ if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
+ const SCEV *Step = A->getStepRecurrence(SE);
+ const SCEV *StepRem = SE.getIntegerSCEV(0, Step->getType());
+ if (!FactorOutConstant(Step, StepRem, Factor, SE))
+ return false;
+ if (!StepRem->isZero())
+ return false;
+ const SCEV *Start = A->getStart();
+ if (!FactorOutConstant(Start, Remainder, Factor, SE))
+ return false;
+ S = SE.getAddRecExpr(Start, Step, A->getLoop());
+ return true;
+ }
+
+ return false;
+}
+