[instcombine] Fold overflow check using umulo to comparison

[reames]

Summary

If we have a umul.with.overflow where the multiply result is not used and one of the operands is a constant, we can perform the overflow check cheaper with a comparison then by performing the multiply an extracting the overflow flag.

(Noticed when looking at the conditions SCEV emits for overflow checks.)

[spatel]

Seems right- see inline for a few nits along with the clang-format warnings from the bot.
Please pre-commit the test file with the baseline CHECKs.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3085–3086

This comment is too specific now - we handle more than just adds.

// If we are only checking for overflow (math result is not used) and the RHS is a constant...

3086

Add assert msg - "Unexpected extract index for overflow inst"

3107

This matches the existing check for add, but we could use match(WO->getRHS(), m_APInt(C)) and handle vector splat constants for almost free. Add a TODO comment?

[reames]

Address review comments

[reames]

Add requested todo.

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3086

Done, though I don't think this actually improves the code.

3107

I hadn't know these had vector overloads. Learn something new every day.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (WO->hasOneUse()) {
       if (*EV.idx_begin() == 0) {
         Instruction::BinaryOps BinOp = WO->getBinaryOp();
         Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
         // Replace the old instruction's uses with poison.
         replaceInstUsesWith(*WO, PoisonValue::get(WO->getType()));
         eraseInstFromFunction(*WO);
         return BinaryOperator::Create(BinOp, LHS, RHS);
       }
 
-      // If the normal result of the add is dead, and the RHS is a constant,
-      // we can transform this into a range comparison.
+      assert(*EV.idx_begin() == 1 &&
+             "unexpected extract index for overflow inst");
+
+      // If the normal result of the computation is dead, and the RHS is a
+      // constant, we can transform this into a range comparison for many cases.
+      // TODO: We can generalize these for non-constant rhs when the newly
+      // formed expressions are known to simplify.  Constants are merely one
+      // such case.
+      // TODO: Handle vector splats.
+      switch (WO->getIntrinsicID()) {
+      default:
+        break;
+      case Intrinsic::uadd_with_overflow:
         // overflow = uadd a, -4  -->  overflow = icmp ugt a, 3
-      if (WO->getIntrinsicID() == Intrinsic::uadd_with_overflow)
         if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS()))
           return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(),
                               ConstantExpr::getNot(CI));
+        break;
+      case Intrinsic::umul_with_overflow:
+        // overflow for umul a, C  --> a > UINT_MAX udiv C
+        // (unless C == 0, in which case no overflow ever occurs)
+        if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS())) {
+          assert(!CI->isZero() && "handled by instruction simplify");
+          auto UMax = APInt::getMaxValue(CI->getType()->getBitWidth());
+          auto *Op =
+            ConstantExpr::getUDiv(ConstantInt::get(CI->getType(), UMax), CI);
+          return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(), Op);
+        }
+        break;
+      };
     }
   }
   if (LoadInst *L = dyn_cast<LoadInst>(Agg))
     // If the (non-volatile) load only has one use, we can rewrite this to a
     // load from a GEP. This reduces the size of the load. If a load is used
     // only by extractvalue instructions then this either must have been
     // optimized before, or it is a struct with padding, in which case we
     // don't want to do the transformation as it loses padding knowledge.

llvm/test/Transforms/InstCombine/umulo.ll

 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 1)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_constant2(i8 %a) {
 ; CHECK-LABEL: @test_constant2(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 2)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp slt i8 [[A:%.*]], 0
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 2)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_constant3(i8 %a) {
 ; CHECK-LABEL: @test_constant3(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 3)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 85
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 3)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_constant4(i8 %a) {
 ; CHECK-LABEL: @test_constant4(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 4)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 63
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 4)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 
 define i1 @test_constant127(i8 %a) {
 ; CHECK-LABEL: @test_constant127(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 127)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 2
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 127)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_constant128(i8 %a) {
 ; CHECK-LABEL: @test_constant128(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 -128)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 128)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }
 
 define i1 @test_constant255(i8 %a) {
 ; CHECK-LABEL: @test_constant255(
-; CHECK-NEXT:    [[RES:%.*]] = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[A:%.*]], i8 -1)
-; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[RES]], 1
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = icmp ugt i8 [[A:%.*]], 1
 ; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %res = tail call { i8, i1 } @llvm.umul.with.overflow.i8(i8 %a, i8 255)
   %overflow = extractvalue { i8, i1 } %res, 1
   ret i1 %overflow
 }