[InstCombine] X / (select C, X, -X) -> select C ? 1 : -1

[xbolva00]

Summary

https://rise4fun.com/Alive/8Mb

[MaskRay]

What does this patch do with INT_MIN? Is there demonstrable benefit (code patterns in real world applications)?

[xbolva00]

Isn't abs(INT_MIN) undefined?

expensive div is removed:

_Z4fooai: # @_Z4fooai
  mov eax, edi
  mov ecx, edi
  neg ecx
  cmovl ecx, edi
  cdq
  idiv ecx
  ret
_Z5fooari: # @_Z5fooari
  mov eax, edi
  sar eax, 31
  or eax, 1
  ret

GCC knows this trick too.

[craig.topper]

In D71312#1778585, @xbolva00 wrote:

Isn't abs(INT_MIN) undefined?

expensive div is removed:

_Z4fooai: # @_Z4fooai
  mov eax, edi
  mov ecx, edi
  neg ecx
  cmovl ecx, edi
  cdq
  idiv ecx
  ret
_Z5fooari: # @_Z5fooari
  mov eax, edi
  sar eax, 31
  or eax, 1
  ret

GCC knows this trick too.

abs(INT_MIN) is only undefined if the sub 0, %x operation that SPF_ABS matched has the nsw flag set on it.

[xbolva00]

Yeah, thanks. Alive proof:

https://rise4fun.com/Alive/9CR

[craig.topper]

Isn't it sufficient to just check that the true/false values of the select are x and -x. The condition itself doesn't matter. x / (select c, x, -x) -> select c ? 1 : -1

[xbolva00]

Addressed comments.

[xbolva00]

In D71312#1778626, @craig.topper wrote:

Isn't it sufficient to just check that the true/false values of the select are x and -x. The condition itself doesn't matter. x / (select c, x, -x) -> select c ? 1 : -1

Name: div abs
%cmp = icmp slt i32 %x, 0
%sub = sub nsw i32 0, %x
%cond = select i1 %cmp, i32 %sub, i32 %x
%div = sdiv i32 %x, %cond
=>
%div = select i1 %cmp, i32 -1, i32 1

Right.

[craig.topper]

Seems to be what gcc really implements https://godbolt.org/z/ZBooz9

[xbolva00]

Implement general pattern.

[craig.topper]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

1115

Taking this even farther. Can't we do

X / (select C, A, X) -> select C, X / A, 1

I assume if A happens to be X or -X it would continue folding on its own when the new nodes are processed in the worklist

[craig.topper]

Seems like we should maybe teach InstCombiner::FoldOpIntoSelect to handle cases where one of the select operands becomes a constant if we fold. But we might only call FoldOpIntoSelect when one of the operands of the binop is a constant today.

I think we also miss
x + (c ? -x : y) -> c ? 0 : x + y
x - (c ? x : y) -> c ? 0 : x - y

Also does InstSimplify know X / -X -> -1 when the neg has NSW?

[spatel]

I'm not sure if this does everything you want, but you probably should look at:
InstCombiner::SimplifySelectsFeedingBinaryOp()

[spatel]

In D71312#1778774, @craig.topper wrote:

Also does InstSimplify know X / -X -> -1 when the neg has NSW?

Yes - D49382

[xbolva00]

In D71312#1779869, @spatel wrote:

I'm not sure if this does everything you want, but you probably should look at:
InstCombiner::SimplifySelectsFeedingBinaryOp()

Thanks

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
   }
 
   // -X / Y --> -(X / Y)
   Value *Y;
   if (match(&I, m_SDiv(m_OneUse(m_NSWSub(m_Zero(), m_Value(X))), m_Value(Y))))
     return BinaryOperator::CreateNSWNeg(
         Builder.CreateSDiv(X, Y, I.getName(), I.isExact()));
 
+  // X / (select C, X, -X) -> select C ? 1 : -1
+  // (select C, X, -X) / X -> select C ? 1 : -1
+  Value *Cond;
+  if ((match(Op0, m_Select(m_Value(Cond), m_Value(X),
+                           m_NSWSub(m_Zero(), m_Deferred(X)))) &&
+       Op1 == X) ||
+      (match(Op1, m_Select(m_Value(Cond), m_Value(X),
+                           m_NSWSub(m_Zero(), m_Deferred(X)))) &&
+       Op0 == X)) {
+    return SelectInst::Create(Cond, ConstantInt::get(I.getType(), 1),
+                              Constant::getAllOnesValue(I.getType()));
+  }
+
+  // X / (select C, -X, X) -> select C ? -1 : 1
+  // (select C, -X, X) / X -> select C ? -1 : 1
+  if ((match(Op0, m_Select(m_Value(Cond), m_NSWSub(m_Zero(), m_Value(X)),
+                           m_Deferred(X))) &&
+       Op1 == X) ||
+      (match(Op1, m_Select(m_Value(Cond), m_NSWSub(m_Zero(), m_Value(X)),
+                           m_Deferred(X))) &&
+       Op0 == X)) {
+    return SelectInst::Create(Cond, Constant::getAllOnesValue(I.getType()),
+                              ConstantInt::get(I.getType(), 1));
+  }
+
   // If the sign bits of both operands are zero (i.e. we can prove they are
   // unsigned inputs), turn this into a udiv.
   APInt Mask(APInt::getSignMask(I.getType()->getScalarSizeInBits()));
   if (MaskedValueIsZero(Op0, Mask, 0, &I)) {
     if (MaskedValueIsZero(Op1, Mask, 0, &I)) {
       // X sdiv Y -> X udiv Y, iff X and Y don't have sign bit set
       auto *BO = BinaryOperator::CreateUDiv(Op0, Op1, I.getName());
       BO->setIsExact(I.isExact());

llvm/test/Transforms/InstCombine/sdiv-select.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+declare void @use(i32)
+
+define i32 @sdiv_abs(i32 %x) {
+; CHECK-LABEL: @sdiv_abs(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP_INV]], i32 1, i32 -1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %x, %cond
+  ret i32 %div
+}
+
+define i32 @sdiv_abs2(i32 %x) {
+; CHECK-LABEL: @sdiv_abs2(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP_INV]], i32 1, i32 -1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %cond, %x
+  ret i32 %div
+}
+
+define i32 @sdiv_abs3(i32 %x) {
+; CHECK-LABEL: @sdiv_abs3(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP_INV]], i32 -1, i32 1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %x, i32 %sub
+  %div = sdiv i32 %x, %cond
+  ret i32 %div
+}
+
+define i32 @sdiv_eq(i32 %x) {
+; CHECK-LABEL: @sdiv_eq(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], 4
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP]], i32 -1, i32 1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp eq i32 %x, 4
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %x, %cond
+  ret i32 %div
+}
+
+define i32 @sdiv_eq2(i32 %x, i32 %y) {
+; CHECK-LABEL: @sdiv_eq2(
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[Y:%.*]], 0
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[TOBOOL]], i32 -1, i32 1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %tobool = icmp eq i32 %y, 0
+  %div = select i1 %tobool, i32 -1, i32 1
+  ret i32 %div
+}
+
+
+define i32 @sdiv_abs_extra_use(i32 %x) {
+; CHECK-LABEL: @sdiv_abs_extra_use(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[X]]
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 [[X]]
+; CHECK-NEXT:    call void @use(i32 [[COND]])
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP]], i32 -1, i32 1
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  call void @use(i32 %cond)
+  %div = sdiv i32 %x, %cond
+  ret i32 %div
+}
+
+define i32 @sdiv_extra_use_abs(i32 %x) {
+; CHECK-LABEL: @sdiv_extra_use_abs(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[DIV:%.*]] = select i1 [[CMP_INV]], i32 1, i32 -1
+; CHECK-NEXT:    call void @use(i32 [[DIV]])
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub nsw i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %x, %cond
+  call void @use(i32 %div)
+  ret i32 %div
+}
+
+
+define <4 x i32> @sdiv_abs_vec(<4 x i32> %x) {
+; CHECK-LABEL: @sdiv_abs_vec(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[DIV:%.*]] = select <4 x i1> [[CMP_INV]], <4 x i32> <i32 1, i32 1, i32 1, i32 1>, <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    ret <4 x i32> [[DIV]]
+;
+  %cmp = icmp slt <4 x i32> %x, zeroinitializer
+  %sub = sub nsw <4 x i32> zeroinitializer, %x
+  %cond = select <4 x i1> %cmp,  <4 x i32> %sub,  <4 x i32> %x
+  %div = sdiv <4 x i32> %x, %cond
+  ret <4 x i32> %div
+}
+
+
+define <4 x i32> @sdiv_abs_vec2(<4 x i32> %x) {
+; CHECK-LABEL: @sdiv_abs_vec2(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[DIV:%.*]] = select <4 x i1> [[CMP_INV]], <4 x i32> <i32 1, i32 1, i32 1, i32 1>, <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    ret <4 x i32> [[DIV]]
+;
+  %cmp = icmp slt <4 x i32> %x, zeroinitializer
+  %sub = sub nsw <4 x i32> zeroinitializer, %x
+  %cond = select <4 x i1> %cmp,  <4 x i32> %sub,  <4 x i32> %x
+  %div = sdiv <4 x i32> %cond, %x
+  ret <4 x i32> %div
+}
+
+define <4 x i32> @sdiv_abs_vec3(<4 x i32> %x) {
+; CHECK-LABEL: @sdiv_abs_vec3(
+; CHECK-NEXT:    [[CMP_INV:%.*]] = icmp sgt <4 x i32> [[X:%.*]], <i32 -1, i32 -1, i32 -1, i32 -1>
+; CHECK-NEXT:    [[DIV:%.*]] = select <4 x i1> [[CMP_INV]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, <4 x i32> <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    ret <4 x i32> [[DIV]]
+;
+  %cmp = icmp slt <4 x i32> %x, zeroinitializer
+  %sub = sub nsw <4 x i32> zeroinitializer, %x
+  %cond = select <4 x i1> %cmp,  <4 x i32> %x,  <4 x i32> %sub
+  %div = sdiv <4 x i32> %cond, %x
+  ret <4 x i32> %div
+}
+
+define <4 x i32> @sdiv_eq_vec(<4 x i32> %x) {
+; CHECK-LABEL: @sdiv_eq_vec(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> [[X:%.*]], <i32 4, i32 4, i32 4, i32 4>
+; CHECK-NEXT:    [[DIV:%.*]] = select <4 x i1> [[CMP]], <4 x i32> <i32 -1, i32 -1, i32 -1, i32 -1>, <4 x i32> <i32 1, i32 1, i32 1, i32 1>
+; CHECK-NEXT:    ret <4 x i32> [[DIV]]
+;
+  %cmp = icmp eq <4 x i32> %x, <i32 4, i32 4, i32 4, i32 4>
+  %sub = sub nsw <4 x i32> zeroinitializer, %x
+  %cond = select <4 x i1> %cmp,  <4 x i32> %sub,  <4 x i32> %x
+  %div = sdiv <4 x i32> %x, %cond
+  ret <4 x i32> %div
+}
+
+
+; Negative tests
+
+define i32 @sdiv_abs_no_nsw(i32 %x) {
+; CHECK-LABEL: @sdiv_abs_no_nsw(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[X]]
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 [[X]]
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[X]], [[COND]]
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %x, %cond
+  ret i32 %div
+}
+
+define i32 @sdiv_abs2_no_nsw(i32 %x) {
+; CHECK-LABEL: @sdiv_abs2_no_nsw(
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
+; CHECK-NEXT:    [[SUB:%.*]] = sub i32 0, [[X]]
+; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[SUB]], i32 [[X]]
+; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[COND]], [[X]]
+; CHECK-NEXT:    ret i32 [[DIV]]
+;
+  %cmp = icmp slt i32 %x, 0
+  %sub = sub i32 0, %x
+  %cond = select i1 %cmp, i32 %sub, i32 %x
+  %div = sdiv i32 %cond, %x
+  ret i32 %div
+}