Page MenuHomePhabricator

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

Authored by xbolva00 on Dec 10 2019, 3:50 PM.

Details

Event Timeline

xbolva00 created this revision.Dec 10 2019, 3:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 10 2019, 3:50 PM

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

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.

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.

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 updated this revision to Diff 233227.Dec 10 2019, 4:46 PM

Addressed comments.

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.

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

xbolva00 updated this revision to Diff 233236.Dec 10 2019, 5:14 PM

Implement general pattern.

xbolva00 retitled this revision from [InstCombine] Fold X / abs(X) to X < 0 ? -1 : 1 to [InstCombine] X / (select C, X, -X) -> select C ? 1 : -1.Dec 10 2019, 5:15 PM
craig.topper added inline comments.Dec 10 2019, 5:38 PM
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

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?

lebedev.ri edited the summary of this revision. (Show Details)Dec 11 2019, 1:18 AM

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

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

Yes - D49382

xbolva00 planned changes to this revision.Jan 19 2020, 6:57 AM

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

Thanks