[InstCombine] transform multiplication overflow check written as a > (UINT_MAX /u b) to umul.with.overflow

[regehr]

Summary

there aren't a lot of good ways to express a portable overflow check for a multiply in conformant C. here's one way that people do it:

a > (UINT_MAX /u b)

this patch teaches instcombine to turn this back into a umul.with.overflow

[majnemer]

@sanjoy, you dealt with this sort of canonicalization before. What are your thoughts? Would we want this is InstCombine or CGP? umul_with_overflow may be more canonical because it can be speculated...

lib/Transforms/InstCombine/InstCombineCompares.cpp

3253–3255

This might not be a canonical transform if the division has multiple users.

[sanjoy]

The conclusions / guidelines decided from the earlier work were

1. The optimizer should not introduce these intrinsics early in the pipeline, since there are passes that don't understand them yet.
2. CGP should do a best-effort replacement of arithmetic with overflow intrinsics (i.e. this change should live in CGP).
3. If the programmer really would have liked the codegen to use overflow bits in the CPU flags, then she need to use __builtin_umull_overflow etc. directly.

@regehr is there some specific reason it helps to canonicalize like this?

[regehr]

Hi guys, I don't know the best place for this-- just wanted to implement it since Rich Felker, author of Musl libc, was complaining that the transformation is missing. If this isn't the right place I'm happy to close this out.

[xbolva00]

Please upload with the full context

lib/Transforms/InstCombine/InstCombineCompares.cpp

 
   bool isSignBit = false;
 
+  // a > (UINT_MAX /u b) is a portable way to check if a * b overflows --
+  // replace it with a umul_with_overflow
+  {
+    ConstantInt *CI;
+    Value *R;
+    if (I.getPredicate() == ICmpInst::ICMP_ULT &&
+        match(Op0, m_UDiv(m_ConstantInt(CI), m_Value(R))) &&
+        CI->isMaxValue(false)) {
+      Type *T = IntegerType::get(I.getContext(), CI->getBitWidth());
+      Value *F = Intrinsic::getDeclaration(I.getModule(),
+                                           Intrinsic::umul_with_overflow, T);
+      Builder->SetInsertPoint(&I);
+      CallInst *Call = Builder->CreateCall(F, {I.getOperand(1), R}, "umul");
+      return ExtractValueInst::Create(Call, 1, "umul.overflow");
+    }
+  }
+
   // See if we are doing a comparison with a constant.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
     Value *A = nullptr, *B = nullptr;

test/Transforms/InstCombine/overflow-mul.ll

   ret <4 x i32> %vcgez.i
 }
 
+; a > (UINT_MAX /u b)  -->  mul.with.overflow(a, b)
+define i32 @div_elim32(i32 %a, i32 %b) #0 {
+; CHECK-LABEL: div_elim32
+; CHECK-NOT: udiv
+; CHECK: umul.with.overflow
+entry:
+  %div = udiv i32 -1, %b
+  %cmp = icmp ult i32 %div, %a
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
 
+; a > (UINT_MAX /u b)  -->  mul.with.overflow(a, b)
+define i32 @div_elim64(i64 %a, i64 %b) #0 {
+; CHECK-LABEL: div_elim64
+; CHECK-NOT: udiv
+; CHECK: umul.with.overflow
+entry:
+  %div = udiv i64 -1, %b
+  %cmp = icmp ult i64 %div, %a
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+
 ; The last test needs this weird datalayout.
 target datalayout = "i32:8:8"
 ; Without it, InstCombine will align the pointed on 4 Bytes