[SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".

[timshen]

Summary

FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows.

[timshen]

Don't generate the multiply, as we get the result for free anyway (we need to check overflow by using umul_ov).

[sanjoy]

llvm/lib/Analysis/ScalarEvolution.cpp

3072

LLVM usually prefers auto * for pointers.

3076

If it does overflow then we can just return 0 here right?

[Up to you if you want to handle that case or just add a TODO]

[sanjoy]

llvm/test/Analysis/ScalarEvolution/fold.ll

106

These should be written as CHECK: <var name> followed by CHECK-NEXT: <expression> like in @test7.

[timshen]

Added folding to 0 when denominator overflows.

llvm/lib/Analysis/ScalarEvolution.cpp

if (!RHSC->getValue()->isZero()) {
             if (!isa<SCEVUDivExpr>(Div) && getMulExpr(Div, RHSC) == Op) {
               Operands = SmallVector<const SCEV *, 4>(M->op_begin(),
                                                       M->op_end());
               Operands[i] = Div;
               return getMulExpr(Operands);
             }
           }
       }
+
+      // (A/B)/C --> A/(B*C) if safe and B*C can be folded.
+      if (const SCEVUDivExpr *OtherDiv = dyn_cast<SCEVUDivExpr>(LHS)) {
+        if (auto DivisorConstant = dyn_cast<SCEVConstant>(OtherDiv->getRHS())) {
+          bool Overflow = false;
+          DivisorConstant->getAPInt().umul_ov(RHSC->getAPInt(), Overflow);
+          if (!Overflow) {
+            return getUDivExpr(OtherDiv->getLHS(),
+                               getMulExpr(DivisorConstant, RHSC));
+          }
+        }
+      }
+
       // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
       if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(LHS)) {
         SmallVector<const SCEV *, 4> Operands;
         for (const SCEV *Op : A->operands())
           Operands.push_back(getZeroExtendExpr(Op, ExtTy));
         if (getZeroExtendExpr(A, ExtTy) == getAddExpr(Operands)) {
           Operands.clear();
           for (unsigned i = 0, e = A->getNumOperands(); i != e; ++i) {

llvm/test/Analysis/ScalarEvolution/fold.ll

; CHECK-LABEL: @test7
   %B = sext i32 %A to i64
   %C = zext i32 %A to i64
   %D = sub i64 %B, %C
   %E = trunc i64 %D to i16
 ; CHECK: %E
 ; CHECK-NEXT: -->  0
   ret void
 }
+
+define i64 @test8(i64 %a) {
+; CHECK-LABEL: @test8
+  %t0 = udiv i64 %a, 56
+  %t1 = udiv i64 %t0, 56
+; CHECK: -->  (%a /u 3136)
+  ret i64 %t1
+}
+
+define i64 @test9(i64 %a) {
+; CHECK-LABEL: @test9
+  %t0 = udiv i64 %a, 100000000000000
+  %t1 = udiv i64 %t0, 100000000000000
+; CHECK: ((%a /u 100000000000000) /u 100000000000000)
+  ret i64 %t1
+}