+static const APInt gcd(const SCEVConstant *C1, const SCEVConstant *C2) {
+ APInt A = C1->getValue()->getValue().abs();
+ APInt B = C2->getValue()->getValue().abs();
+ uint32_t ABW = A.getBitWidth();
+ uint32_t BBW = B.getBitWidth();
+
+ if (ABW > BBW)
+ B = B.zext(ABW);
+ else if (ABW < BBW)
+ A = A.zext(BBW);
+
+ return APIntOps::GreatestCommonDivisor(A, B);
+}
+
+/// getUDivExactExpr - Get a canonical unsigned division expression, or
+/// something simpler if possible. There is no representation for an exact udiv
+/// in SCEV IR, but we can attempt to remove factors from the LHS and RHS.
+/// We can't do this when it's not exact because the udiv may be clearing bits.
+const SCEV *ScalarEvolution::getUDivExactExpr(const SCEV *LHS,
+ const SCEV *RHS) {
+ // TODO: we could try to find factors in all sorts of things, but for now we
+ // just deal with u/exact (multiply, constant). See SCEVDivision towards the
+ // end of this file for inspiration.
+
+ const SCEVMulExpr *Mul = dyn_cast<SCEVMulExpr>(LHS);
+ if (!Mul)
+ return getUDivExpr(LHS, RHS);
+
+ if (const SCEVConstant *RHSCst = dyn_cast<SCEVConstant>(RHS)) {
+ // If the mulexpr multiplies by a constant, then that constant must be the
+ // first element of the mulexpr.
+ if (const SCEVConstant *LHSCst =
+ dyn_cast<SCEVConstant>(Mul->getOperand(0))) {
+ if (LHSCst == RHSCst) {
+ SmallVector<const SCEV *, 2> Operands;
+ Operands.append(Mul->op_begin() + 1, Mul->op_end());
+ return getMulExpr(Operands);
+ }
+
+ // We can't just assume that LHSCst divides RHSCst cleanly, it could be
+ // that there's a factor provided by one of the other terms. We need to
+ // check.
+ APInt Factor = gcd(LHSCst, RHSCst);
+ if (!Factor.isIntN(1)) {
+ LHSCst = cast<SCEVConstant>(
+ getConstant(LHSCst->getValue()->getValue().udiv(Factor)));
+ RHSCst = cast<SCEVConstant>(
+ getConstant(RHSCst->getValue()->getValue().udiv(Factor)));
+ SmallVector<const SCEV *, 2> Operands;
+ Operands.push_back(LHSCst);
+ Operands.append(Mul->op_begin() + 1, Mul->op_end());
+ LHS = getMulExpr(Operands);
+ RHS = RHSCst;
+ Mul = dyn_cast<SCEVMulExpr>(LHS);
+ if (!Mul)
+ return getUDivExactExpr(LHS, RHS);
+ }
+ }
+ }
+
+ for (int i = 0, e = Mul->getNumOperands(); i != e; ++i) {
+ if (Mul->getOperand(i) == RHS) {
+ SmallVector<const SCEV *, 2> Operands;
+ Operands.append(Mul->op_begin(), Mul->op_begin() + i);
+ Operands.append(Mul->op_begin() + i + 1, Mul->op_end());
+ return getMulExpr(Operands);
+ }
+ }
+
+ return getUDivExpr(LHS, RHS);
+}