[SCCP] Support NUW/NSW inference for all overflowing binary operators.

[fhahn]

Summary

Extend the NUW/NSW inference logic add in 72121a20cd and cdeaf5f28c3dc
to all overflowing binary operators.

[nikic]

LGTM

[tstellar]

This commit is causing a segfault when building python 3.11.3 on ppc64le. I'm still working on gathering more info.

[tstellar]

In D142721#4292972, @tstellar wrote:

This commit is causing a segfault when building python 3.11.3 on ppc64le. I'm still working on gathering more info.

I've tracked this down to the C function that is miscompiled/buggy. What kind of dumps can I provide that would be the most useful for debugging?

[nikic]

In D142721#4294180, @tstellar wrote:

In D142721#4292972, @tstellar wrote:

This commit is causing a segfault when building python 3.11.3 on ppc64le. I'm still working on gathering more info.

I've tracked this down to the C function that is miscompiled/buggy. What kind of dumps can I provide that would be the most useful for debugging?

The input IR (-S -emit-llvm -Xclang -disable-llvm-optzns) would probably be enough. Which one is the problematic function?

Just to double check, did you test this with the final version of these changes? They were reverted and later reapplied, so a bisect might have hit a bad intermediate revision.

[fhahn]

In D142721#4294922, @nikic wrote:

In D142721#4294180, @tstellar wrote:

In D142721#4292972, @tstellar wrote:

This commit is causing a segfault when building python 3.11.3 on ppc64le. I'm still working on gathering more info.

I've tracked this down to the C function that is miscompiled/buggy. What kind of dumps can I provide that would be the most useful for debugging?

The input IR (-S -emit-llvm -Xclang -disable-llvm-optzns) would probably be enough. Which one is the problematic function?

That would be helpful or the full module IR before IPSCCP/SCCP run on the function.

[tstellar]

I've filed an issue here with the LLVM IR dump: https://github.com/llvm/llvm-project/issues/62379

llvm/lib/Transforms/Utils/SCCPSolver.cpp

bool SCCPSolver::tryToReplaceWithConstant(Value *V) {
   V->replaceAllUsesWith(Const);
   return true;
 }
 
 /// Try to use \p Inst's value range from \p Solver to infer the NUW flag.
 static bool refineInstruction(SCCPSolver &Solver,
                               const SmallPtrSetImpl<Value *> &InsertedValues,
                               Instruction &Inst) {
-  if (Inst.getOpcode() != Instruction::Add)
+  if (!isa<OverflowingBinaryOperator>(Inst))
     return false;
 
   auto GetRange = [&Solver, &InsertedValues](Value *Op) {
     if (auto *Const = dyn_cast<ConstantInt>(Op))
       return ConstantRange(Const->getValue());
     if (isa<Constant>(Op) || InsertedValues.contains(Op)) {
       unsigned Bitwidth = Op->getType()->getScalarSizeInBits();
       return ConstantRange::getFull(Bitwidth);
     }
     return getConstantRange(Solver.getLatticeValueFor(Op), Op->getType(),
                             /*UndefAllowed=*/false);
   };
   auto RangeA = GetRange(Inst.getOperand(0));
   auto RangeB = GetRange(Inst.getOperand(1));
   bool Changed = false;
   if (!Inst.hasNoUnsignedWrap()) {
     auto NUWRange = ConstantRange::makeGuaranteedNoWrapRegion(
-        Instruction::Add, RangeB, OverflowingBinaryOperator::NoUnsignedWrap);
+        Instruction::BinaryOps(Inst.getOpcode()), RangeB,
+        OverflowingBinaryOperator::NoUnsignedWrap);
     if (NUWRange.contains(RangeA)) {
       Inst.setHasNoUnsignedWrap();
       Changed = true;
     }
   }
   if (!Inst.hasNoSignedWrap()) {
     auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(
-        Instruction::Add, RangeA, OverflowingBinaryOperator::NoSignedWrap);
+        Instruction::BinaryOps(Inst.getOpcode()), RangeA,
+        OverflowingBinaryOperator::NoSignedWrap);
     if (NSWRange.contains(RangeB)) {
       Inst.setHasNoSignedWrap();
       Changed = true;
     }
   }
 
   return Changed;
 }

llvm/test/Transforms/PhaseOrdering/min-max-abs-cse.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -S -O1 | FileCheck %s
 ; RUN: opt -passes='default<O1>' -S < %s | FileCheck %s
 
 ; In all tests, expect instcombine to canonicalize the select patterns
 ; for min/max/abs to allow CSE and subsequent simplification.
 
 ; TODO:
 ; This should be reduced to 0, but we are missing some
 ; fold(s) in instcombine.
 
 define i8 @smax_nsw(i8 %a, i8 %b) {
 ; CHECK-LABEL: @smax_nsw(
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i8 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i8 [[A]], [[B]]
 ; CHECK-NEXT:    [[M1:%.*]] = select i1 [[CMP1]], i8 0, i8 [[SUB]]
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i8 @llvm.smax.i8(i8 [[SUB]], i8 0)
-; CHECK-NEXT:    [[R:%.*]] = sub i8 [[TMP1]], [[M1]]
+; CHECK-NEXT:    [[M2:%.*]] = tail call i8 @llvm.smax.i8(i8 [[SUB]], i8 0)
+; CHECK-NEXT:    [[R:%.*]] = sub i8 [[M2]], [[M1]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sub = sub nsw i8 %a, %b
   %cmp1 = icmp slt i8 %a, %b
   %cmp2 = icmp sgt i8 %sub, 0
   %m1 = select i1 %cmp1, i8 0, i8 %sub
   %m2 = select i1 %cmp2, i8 %sub, i8 0
   %r = sub i8 %m2, %m1
   ret i8 %r
 }
 
 ; or (abs a), (abs a) --> abs a
 
 define i8 @abs_swapped(i8 %a) {
 ; CHECK-LABEL: @abs_swapped(
-; CHECK-NEXT:    [[TMP1:%.*]] = tail call i8 @llvm.abs.i8(i8 [[A:%.*]], i1 false)
-; CHECK-NEXT:    ret i8 [[TMP1]]
+; CHECK-NEXT:    [[M1:%.*]] = tail call i8 @llvm.abs.i8(i8 [[A:%.*]], i1 true)
+; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp sgt i8 %a, 0
   %cmp2 = icmp slt i8 %a, 0
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = or i8 %m2, %m1
   ret i8 %r
;
   ret i8 %r
 }
 
 ; or (nabs a), (nabs a) --> nabs a
 
 define i8 @nabs_different_constants(i8 %a) {
 ; CHECK-LABEL: @nabs_different_constants(
 ; CHECK-NEXT:    [[TMP1:%.*]] = tail call i8 @llvm.abs.i8(i8 [[A:%.*]], i1 false)
-; CHECK-NEXT:    [[M1:%.*]] = sub i8 0, [[TMP1]]
+; CHECK-NEXT:    [[M1:%.*]] = sub nsw i8 0, [[TMP1]]
 ; CHECK-NEXT:    ret i8 [[M1]]
 ;
   %neg = sub i8 0, %a
   %cmp1 = icmp slt i8 %a, 0
   %cmp2 = icmp sgt i8 %a, -1
   %m1 = select i1 %cmp1, i8 %a, i8 %neg
   %m2 = select i1 %cmp2, i8 %neg, i8 %a
   %r = or i8 %m2, %m1
   ret i8 %r
 }

llvm/test/Transforms/PhaseOrdering/pr32544.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -O3 -S < %s                    | FileCheck %s
-; RUN: opt -passes='default<O3>' -S < %s  | FileCheck %s
+; RUN: opt -passes='default<O3>' -S < %s  | FileCheck %s
 
 define void @foo(i1 %which, i32 %a, i32 %b, ptr %result) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 0, [[B:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 0, [[B:%.*]]
 ; CHECK-NEXT:    [[Z_V_P:%.*]] = select i1 [[WHICH:%.*]], i32 [[B]], i32 [[TMP0]]
 ; CHECK-NEXT:    [[Z_V:%.*]] = add i32 [[Z_V_P]], [[A:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = zext i32 [[Z_V]] to i64
 ; CHECK-NEXT:    [[C:%.*]] = load i64, ptr [[RESULT:%.*]], align 4
 ; CHECK-NEXT:    [[VALUE:%.*]] = add i64 [[C]], [[Z]]
 ; CHECK-NEXT:    store i64 [[VALUE]], ptr [[RESULT]], align 4
 ; CHECK-NEXT:    ret void
 ;
final:
   %value = add i64 %z, %c
   store i64 %value, ptr %result
   ret void
 }
 
 define void @bar(i1 %which, i32 %a, i32 %b, ptr %result) {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 0, [[B:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 0, [[B:%.*]]
 ; CHECK-NEXT:    [[SPEC_SELECT_P:%.*]] = select i1 [[WHICH:%.*]], i32 [[B]], i32 [[TMP0]]
 ; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = add i32 [[SPEC_SELECT_P]], [[A:%.*]]
 ; CHECK-NEXT:    [[Z2:%.*]] = zext i32 [[SPEC_SELECT]] to i64
 ; CHECK-NEXT:    [[C:%.*]] = load i64, ptr [[RESULT:%.*]], align 4
 ; CHECK-NEXT:    [[VALUE:%.*]] = add i64 [[C]], [[Z2]]
 ; CHECK-NEXT:    store i64 [[VALUE]], ptr [[RESULT]], align 4
 ; CHECK-NEXT:    ret void
 ;
final:
   %value = add i64 %z2, %c
   store i64 %value, ptr %result
   ret void
 }
 
 define void @foo_opt(i1 %which, i32 %a, i32 %b, ptr nocapture %result) {
 ; CHECK-LABEL: @foo_opt(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 0, [[B:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub nsw i32 0, [[B:%.*]]
 ; CHECK-NEXT:    [[Z_V_P:%.*]] = select i1 [[WHICH:%.*]], i32 [[B]], i32 [[TMP0]]
 ; CHECK-NEXT:    [[Z_V:%.*]] = add i32 [[Z_V_P]], [[A:%.*]]
 ; CHECK-NEXT:    [[Z:%.*]] = zext i32 [[Z_V]] to i64
 ; CHECK-NEXT:    [[C:%.*]] = load i64, ptr [[RESULT:%.*]], align 4
 ; CHECK-NEXT:    [[VALUE:%.*]] = add i64 [[C]], [[Z]]
 ; CHECK-NEXT:    store i64 [[VALUE]], ptr [[RESULT]], align 4
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/SCCP/ip-constant-ranges.ll

 ; CHECK-LABEL: define {{[^@]+}}@recursive_f
 ; CHECK-SAME: (i32 [[I:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[I]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    br label [[RETURN:%.*]]
 ; CHECK:       if.else:
-; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[I]], 1
+; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 [[I]], 1
 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @recursive_f(i32 [[SUB]])
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[I]], [[CALL]]
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ 0, [[IF_THEN]] ], [ [[ADD]], [[IF_ELSE]] ]
 ; CHECK-NEXT:    ret i32 [[RETVAL_0]]
 ;
 entry:

llvm/test/Transforms/SCCP/ip-ranges-binaryops.ll

;
   ret i1 %res
 }
 
 
 ; x = [10, 21), y = [100, 201)
 ; x - y = [-190, -79)
 define internal i1 @f.sub(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.sub(
-; CHECK-NEXT:    [[A_1:%.*]] = sub i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A_1:%.*]] = sub nsw i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[A_1]], -81
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i32 [[A_1]], -189
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[A_1]], -150
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp slt i32 [[A_1]], -150
 ; CHECK-NEXT:    [[RES_1:%.*]] = add nuw nsw i1 false, [[C_2]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = add nuw nsw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]
;
   %res = and i1 %call.1, %call.2
   ret i1 %res
 }
 
 ; x = [10, 21), y = [100, 201)
 ; x * y = [1000, 4001)
 define internal i1 @f.mul(i32 %x, i32 %y) {
 ; CHECK-LABEL: @f.mul(
-; CHECK-NEXT:    [[A_1:%.*]] = mul i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[A_1:%.*]] = mul nuw nsw i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sgt i32 [[A_1]], 3999
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp slt i32 [[A_1]], 1001
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[A_1]], 1500
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp slt i32 [[A_1]], 1500
 ; CHECK-NEXT:    [[RES_1:%.*]] = add nuw nsw i1 false, [[C_2]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = add nuw nsw i1 [[RES_1]], false
 ; CHECK-NEXT:    [[RES_3:%.*]] = add i1 [[RES_2]], [[C_4]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = add i1 [[RES_3]], [[C_5]]

llvm/test/Transforms/SCCP/ub-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=sccp -S | FileCheck %s
 
 define void @shift_undef_64(ptr %p) {
 ; CHECK-LABEL: @shift_undef_64(
 ; CHECK-NEXT:    store i64 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    store i64 -1, ptr [[P]], align 4
-; CHECK-NEXT:    [[R3:%.*]] = shl i64 -1, 4294967298
+; CHECK-NEXT:    [[R3:%.*]] = shl nuw nsw i64 -1, 4294967298
 ; CHECK-NEXT:    store i64 [[R3]], ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i64 -1, 4294967296 ; 2^32
   store i64 %r1, ptr %p
 
   %r2 = ashr i64 -1, 4294967297 ; 2^32 + 1
   store i64 %r2, ptr %p
 
   %r3 = shl i64 -1, 4294967298 ; 2^32 + 2
   store i64 %r3, ptr %p
 
   ret void
 }
 
 define void @shift_undef_65(ptr %p) {
 ; CHECK-LABEL: @shift_undef_65(
 ; CHECK-NEXT:    store i65 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    store i65 0, ptr [[P]], align 4
-; CHECK-NEXT:    [[R3:%.*]] = shl i65 1, -18446744073709551615
+; CHECK-NEXT:    [[R3:%.*]] = shl nuw i65 1, -18446744073709551615
 ; CHECK-NEXT:    store i65 [[R3]], ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i65 2, 18446744073709551617
   store i65 %r1, ptr %p
 
   %r2 = ashr i65 4, 18446744073709551617
   store i65 %r2, ptr %p
 
   %r3 = shl i65 1, 18446744073709551617
   store i65 %r3, ptr %p
 
   ret void
 }
 
 define void @shift_undef_256(ptr %p) {
 ; CHECK-LABEL: @shift_undef_256(
 ; CHECK-NEXT:    store i256 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    store i256 0, ptr [[P]], align 4
-; CHECK-NEXT:    [[R3:%.*]] = shl i256 1, 18446744073709551619
+; CHECK-NEXT:    [[R3:%.*]] = shl nuw nsw i256 1, 18446744073709551619
 ; CHECK-NEXT:    store i256 [[R3]], ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i256 2, 18446744073709551617
   store i256 %r1, ptr %p
 
   %r2 = ashr i256 4, 18446744073709551618
   store i256 %r2, ptr %p
 
   %r3 = shl i256 1, 18446744073709551619
   store i256 %r3, ptr %p
 
   ret void
 }
 
 define void @shift_undef_511(ptr %p) {
 ; CHECK-LABEL: @shift_undef_511(
 ; CHECK-NEXT:    store i511 0, ptr [[P:%.*]], align 4
 ; CHECK-NEXT:    store i511 -1, ptr [[P]], align 4
-; CHECK-NEXT:    [[R3:%.*]] = shl i511 -3, 1208925819614629174706180
+; CHECK-NEXT:    [[R3:%.*]] = shl nuw nsw i511 -3, 1208925819614629174706180
 ; CHECK-NEXT:    store i511 [[R3]], ptr [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %r1 = lshr i511 -1, 1208925819614629174706276 ; 2^80 + 100
   store i511 %r1, ptr %p
 
   %r2 = ashr i511 -2, 1208925819614629174706200
   store i511 %r2, ptr %p
 
   %r3 = shl i511 -3, 1208925819614629174706180
   store i511 %r3, ptr %p
 
   ret void
 }

llvm/test/Transforms/SCCP/widening.ll

 ; SCCP-NEXT:    i32 2, label [[BB4:%.*]]
 ; SCCP-NEXT:    i32 4, label [[BB19:%.*]]
 ; SCCP-NEXT:    ]
 ; SCCP:       bb3:
 ; SCCP-NEXT:    unreachable
 ; SCCP:       bb4:
 ; SCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; SCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
-; SCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
-; SCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
+; SCCP-NEXT:    [[TMP7:%.*]] = sub nuw nsw i64 3, [[TMP6]]
+; SCCP-NEXT:    [[TMP8:%.*]] = shl nuw nsw i64 [[TMP7]], 1
 ; SCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
 ; SCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
 ; SCCP-NEXT:    br label [[BB11:%.*]]
 ; SCCP:       bb11:
 ; SCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; SCCP-NEXT:    br label [[BB13:%.*]]
 ; SCCP:       bb13:
 ; SCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6

 ; IPSCCP-NEXT:    i32 2, label [[BB4:%.*]]
 ; IPSCCP-NEXT:    i32 4, label [[BB19:%.*]]
 ; IPSCCP-NEXT:    ]
 ; IPSCCP:       bb3:
 ; IPSCCP-NEXT:    unreachable
 ; IPSCCP:       bb4:
 ; IPSCCP-NEXT:    [[TMP5:%.*]] = add i64 [[TMP2]], 3
 ; IPSCCP-NEXT:    [[TMP6:%.*]] = and i64 [[TMP5]], 3
-; IPSCCP-NEXT:    [[TMP7:%.*]] = sub i64 3, [[TMP6]]
-; IPSCCP-NEXT:    [[TMP8:%.*]] = shl i64 [[TMP7]], 1
+; IPSCCP-NEXT:    [[TMP7:%.*]] = sub nuw nsw i64 3, [[TMP6]]
+; IPSCCP-NEXT:    [[TMP8:%.*]] = shl nuw nsw i64 [[TMP7]], 1
 ; IPSCCP-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP8]] to i32
 ; IPSCCP-NEXT:    [[TMP10:%.*]] = zext i32 [[TMP9]] to i64
 ; IPSCCP-NEXT:    br label [[BB11:%.*]]
 ; IPSCCP:       bb11:
 ; IPSCCP-NEXT:    [[TMP12:%.*]] = phi i64 [ [[TMP10]], [[BB4]] ], [ [[TMP17:%.*]], [[BB18:%.*]] ]
 ; IPSCCP-NEXT:    br label [[BB13:%.*]]
 ; IPSCCP:       bb13:
 ; IPSCCP-NEXT:    [[C_1:%.*]] = icmp eq i64 [[TMP12]], 6