[ValueTracking] usub(a, b) cannot overflow if a >= b.

[fhahn]

Summary

If we know that a >= b (unsigned), usub.with.overflow(a, b) cannot
overflow. Similarly, if b > a, the same expression overflows.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[nikic]

My only concern here is compile-time impact. Keep in mind that this function is not just being called for usub.with.overflow, but for every sub in the IR, trying to infer the nuw flag. As isImpliedByDomCondition() only inspects the direct predecessor, that's probably fine though.

Generally we're missing a pass that can propagate conditions and assumes with non-constant operands (CVP mostly covers the constant operand case)...

[fhahn]

Updated to limit isImpliedByDomCond to usub.with.overflow calls for now.

In D74066#1859995, @nikic wrote:

My only concern here is compile-time impact. Keep in mind that this function is not just being called for usub.with.overflow, but for every sub in the IR, trying to infer the nuw flag. As isImpliedByDomCondition() only inspects the direct predecessor, that's probably fine though.

Ah right! isImpliedByDomCondition should not be too expensive, but I've limited using it to usub.with.overflow for now.

Generally we're missing a pass that can propagate conditions and assumes with non-constant operands (CVP mostly covers the constant operand case)...

Agreed!

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[fhahn]

clang-format.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[Gerolf]

Nice. LGTM.

-Gerolf

[nikic]

LG as well.

For what it's worth, I think doing this generally is also fine, but we should probably wait until it actually shows up in practice before enabling that.

[fhahn]

Thanks for taking a look!

llvm/lib/Analysis/ValueTracking.cpp

 }
 
 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,
                                                    const Instruction *CxtI,
                                                    const DominatorTree *DT) {
+  // Checking for conditions implied by dominating conditions may be expensive.
+  // Limit it to usub_with_overflow calls for now.
+  if (match(CxtI,
+            m_Intrinsic<Intrinsic::usub_with_overflow>(m_Value(), m_Value())))
+    if (auto C =
+            isImpliedByDomCondition(CmpInst::ICMP_UGE, LHS, RHS, CxtI, DL)) {
+      if (*C)
+        return OverflowResult::NeverOverflows;
+      return OverflowResult::AlwaysOverflowsLow;
+    }
   ConstantRange LHSRange = computeConstantRangeIncludingKnownBits(
       LHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
   ConstantRange RHSRange = computeConstantRangeIncludingKnownBits(
       RHS, /*ForSigned=*/false, DL, /*Depth=*/0, AC, CxtI, DT);
   return mapOverflowResult(LHSRange.unsignedSubMayOverflow(RHSRange));
 }
 
 OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS,

llvm/test/Transforms/InstCombine/usub-overflow-known-by-implied-cond.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 
 ; RUN: opt -instcombine -S %s | FileCheck %s
 
 declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32)
 
 define i32 @test1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB3:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB2:%.*]], label [[BB3]]
+; CHECK-NEXT:    br i1 false, label [[BB2:%.*]], label [[BB3]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    ret i32 undef
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp uge i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
   %r1 = extractvalue { i32, i1 } %sub1, 0
   %c1 = extractvalue { i32, i1 } %sub1, 1
   br i1 %c1, label %bb2, label %bb3
 
 bb2:
   ret i32 %r1
 
 bb3:
   ret i32 0
 }
 
 define i32 @test2(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB3:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB3]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i32 [[A]], [[B]]
+; CHECK-NEXT:    ret i32 [[SUB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp uge i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)

 }
 
 
 define i32 @test3(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ugt i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB2:%.*]], label [[BB3]]
+; CHECK-NEXT:    br i1 false, label [[BB2:%.*]], label [[BB3]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    ret i32 undef
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp ugt i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
   %r1 = extractvalue { i32, i1 } %sub1, 0
   %c1 = extractvalue { i32, i1 } %sub1, 1
   br i1 %c1, label %bb2, label %bb3
 
 bb2:
   ret i32 %r1
 
 bb3:
   ret i32 0
 }
 
 define i32 @test4(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ugt i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB3]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i32 [[A]], [[B]]
+; CHECK-NEXT:    ret i32 [[SUB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp ugt i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)

 }
 
 
 define i32 @test5(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB3]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i32 [[A]], [[B]]
+; CHECK-NEXT:    ret i32 [[SUB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp eq i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)
   %r1 = extractvalue { i32, i1 } %sub1, 0
   %c1 = extractvalue { i32, i1 } %sub1, 1
   br i1 %c1, label %bb3, label %bb2
 
 bb2:
   ret i32 %r1
 
 bb3:
   ret i32 0
 }
 
 define i32 @test6(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ult i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB3]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 true, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    ret i32 undef
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp ult i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)

 }
 
 define i32 @test9(i32 %a, i32 %b, i1 %cond2) {
 ; CHECK-LABEL: @test9(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp ugt i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[COND]], [[COND2:%.*]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    [[SUB1:%.*]] = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 [[A]], i32 [[B]])
-; CHECK-NEXT:    [[C1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 1
-; CHECK-NEXT:    br i1 [[C1]], label [[BB3]], label [[BB2:%.*]]
+; CHECK-NEXT:    br i1 false, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[R1:%.*]] = extractvalue { i32, i1 } [[SUB1]], 0
-; CHECK-NEXT:    ret i32 [[R1]]
+; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i32 [[A]], [[B]]
+; CHECK-NEXT:    ret i32 [[SUB1]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp ugt i32 %a, %b
   %and = and i1 %cond, %cond2
   br i1 %and, label %bb1, label %bb3
 
 bb1: