[InstCombine] extract(u[add|sub].with.overflow(X, C), 0) --> [add|sub](X, C)

[nico-abram]

Summary

Trying to fix https://github.com/llvm/llvm-project/issues/53978 I ran into something like this: https://alive2.llvm.org/ce/z/bduF3e (generalized here https://alive2.llvm.org/ce/z/HdrUXt ) which is not currently optimized.

@nikic mentioned on discord that it might make more sense to canonicalize the intrinsic into a simple add/sub instead of trying to match that specific pattern

Yes, InstCombine would be the place. Though frankly, we should probably just canonicalize uadd/usub away from intrinsics. That should result in better mid-end optimization, and CGP can reform them

This patch does that, but only when the addition is by a constant. I added @uadd_res_ugt_smaller_const_or_ov and @uadd_res_ult_const_five_and_ov as a baseline (The baseline is in the second diff. The third one is the patch against main HEAD).

With this patch, the original case in https://github.com/llvm/llvm-project/issues/53978 gets optimized to a constant false.

[nikic]

Hrm, unfortunately canonicalizing the intrinsic to add/icmp is not safe with undef: https://alive2.llvm.org/ce/z/cgiQ_n We effectively introduce two uses of undef, which can each take a different value.

This might need to be addressed on the front-end side instead, by not emitting uadd/usub intrinsics in the first place.

[nico-abram]

Abandoning revision since the transformation is not safe.

"front-end" means rustc/clang right?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

if (L->isSimple() && L->hasOneUse()) {
       Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);
       // Whatever aliasing information we had for the orignal load must also
       // hold for the smaller load, so propagate the annotations.
       NL->setAAMetadata(L->getAAMetadata());
       // Returning the load directly will cause the main loop to insert it in
       // the wrong spot, so use replaceInstUsesWith().
       return replaceInstUsesWith(EV, NL);
     }
+
+  if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) {
+    Intrinsic::ID OvID = WO->getIntrinsicID();
+    const APInt *C;
+    // Canonicalize:
+    // extractvalue (u[add|sub]_with_overflow X, Y), 0 -> [add|sub] X, Y
+    if (*EV.idx_begin() == 0 &&
+        (OvID == Intrinsic::uadd_with_overflow ||
+         OvID == Intrinsic::usub_with_overflow) &&
+        match(WO->getArgOperand(1), m_APInt(C))) {
+      Instruction::BinaryOps BinOp = WO->getBinaryOp();
+      Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
+      return BinaryOperator::Create(BinOp, LHS, RHS);
+    }
+  }
   // We could simplify extracts from other values. Note that nested extracts may
   // already be simplified implicitly by the above: extract (extract (insert) )
   // will be translated into extract ( insert ( extract ) ) first and then just
   // the value inserted, if appropriate. Similarly for extracts from single-use
   // loads: extract (extract (load)) will be translated to extract (load (gep))
   // and if again single-use then via load (gep (gep)) to load (gep).
   // However, double extracts from e.g. function arguments or return values
   // aren't handled yet.

llvm/test/Transforms/InstCombine/with_overflow.ll

;
   store i1 %b, i1* %p
   %c = extractvalue { i32, i1 } %a, 0
   %d = icmp ugt i32 %y, %c
   ret i1 %d
 }
 
 define i1 @uadd_res_ult_const(i32 %x, i1* %p) nounwind {
 ; CHECK-LABEL: @uadd_res_ult_const(
-; CHECK-NEXT:    [[A:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 42)
-; CHECK-NEXT:    [[B:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[B:%.*]] = icmp ugt i32 [[X]], -43
 ; CHECK-NEXT:    store i1 [[B]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[D:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[D:%.*]] = icmp ugt i32 [[X]], -43
 ; CHECK-NEXT:    ret i1 [[D]]
 ;
   %a = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 42)
   %b = extractvalue { i32, i1 } %a, 1
   store i1 %b, i1* %p
   %c = extractvalue { i32, i1 } %a, 0
   %d = icmp ult i32 %c, 42
   ret i1 %d
 }
 
 define i1 @uadd_res_ult_const_one(i32 %x, i1* %p) nounwind {
 ; CHECK-LABEL: @uadd_res_ult_const_one(
-; CHECK-NEXT:    [[A:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 1)
-; CHECK-NEXT:    [[B:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[B:%.*]] = icmp eq i32 [[X]], -1
 ; CHECK-NEXT:    store i1 [[B]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[D:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[D:%.*]] = icmp eq i32 [[X]], -1
 ; CHECK-NEXT:    ret i1 [[D]]
 ;
   %a = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 1)
   %b = extractvalue { i32, i1 } %a, 1
   store i1 %b, i1* %p
   %c = extractvalue { i32, i1 } %a, 0
   %d = icmp ult i32 %c, 1
   ret i1 %d
 }
 
 define i1 @uadd_res_ult_const_minus_one(i32 %x, i1* %p) nounwind {
 ; CHECK-LABEL: @uadd_res_ult_const_minus_one(
-; CHECK-NEXT:    [[A:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 -1)
-; CHECK-NEXT:    [[B:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[B:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    store i1 [[B]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[D:%.*]] = extractvalue { i32, i1 } [[A]], 1
+; CHECK-NEXT:    [[D:%.*]] = icmp ne i32 [[X]], 0
 ; CHECK-NEXT:    ret i1 [[D]]
 ;
   %a = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 -1)
   %b = extractvalue { i32, i1 } %a, 1
   store i1 %b, i1* %p
   %c = extractvalue { i32, i1 } %a, 0
   %d = icmp ult i32 %c, -1
   ret i1 %d
 }
 
+define i1 @uadd_res_ult_const_five_and_ov(i32 %x) nounwind {
+; CHECK-LABEL: @uadd_res_ult_const_five_and_ov
+; CHECK-NEXT:    [[B:%.*]] = add i32 [[X]], 5
+; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[B]], 4
+; CHECK-NEXT:    ret i1 [[C]]
+;
+  %a = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 5)
+  %c = extractvalue { i32, i1 } %a, 0
+  %b = extractvalue { i32, i1 } %a, 1
+  %d = icmp ult i32 %c, 4
+  %r = and i1 %d, %b
+  ret i1 %r
+}
+
+define i1 @uadd_res_ugt_smaller_const_or_ov(i32 %x) nounwind {
+; CHECK-LABEL: @uadd_res_ugt_smaller_const_or_ov(
+; CHECK-NEXT:    ret i1 true
+;
+  %a = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %x, i32 5)
+  %c = extractvalue { i32, i1 } %a, 0
+  %b = extractvalue { i32, i1 } %a, 1
+  %d = icmp ugt i32 %c, 4
+  %r = or i1 %d, %b
+  ret i1 %r
+}
+
 define { i32, i1 } @sadd_canonicalize_constant_arg0(i32 %x) nounwind {
 ; CHECK-LABEL: @sadd_canonicalize_constant_arg0(
 ; CHECK-NEXT:    [[A:%.*]] = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[X:%.*]], i32 42)
 ; CHECK-NEXT:    ret { i32, i1 } [[A]]
 ;
   %a = call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 42, i32 %x)
   ret { i32, i1 } %a
 }