Page MenuHomePhabricator

[InstCombine] reduce demand-limited bool math to logic
ClosedPublic

Authored by spatel on Mar 10 2020, 2:29 PM.

Details

Summary

The cmp math test is inspired by memcmp() patterns seen in D75840. I know there's at least 1 related fold we can do here if both values are sext'd, but I'm not seeing a way to generalize further.

I know we have some other bool math patterns that we want to reduce, but that might require fixing the bogus transforms noted in D72396.

Alive proof translations of the regression tests:
https://rise4fun.com/Alive/zGWi

Name: demand add 1
  %xz = zext i1 %x to i32
  %ys = sext i1 %y to i32
  %sub = add i32 %xz, %ys
  %r = lshr i32 %sub, 31
=>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = zext i1 %and to i32
  
Name: demand add 2
  %xz = zext i1 %x to i5
  %ys = sext i1 %y to i5
  %sub = add i5 %xz, %ys
  %r = and i5 %sub, 16
  =>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = select i1 %and, i5 -16, i5 0

Name: demand add 3
  %xz = zext i1 %x to i8
  %ys = sext i1 %y to i8
  %a = add i8 %ys, %xz
  %r = ashr i8 %a, 7
=>
  %notx = xor i1 %x, 1
  %and = and i1 %y, %notx
  %r = sext i1 %and to i8
  
Name: cmp math
  %gt = icmp ugt i32 %x, %y
  %lt = icmp ult i32 %x, %y
  %xz = zext i1 %gt to i32
  %yz = zext i1 %lt to i32
  %s = sub i32 %xz, %yz
  %r = lshr i32 %s, 31
=>
  %r = zext i1 %lt to i32

Diff Detail

Event Timeline

spatel created this revision.Mar 10 2020, 2:29 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 10 2020, 2:29 PM
nikic added inline comments.Mar 10 2020, 4:00 PM
llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
457

Wouldn't it be sufficient to check that the LSB is not demanded? I don't think we care that specifically the MSB is demanded, any of the top bits could be.

spatel marked 2 inline comments as done.Mar 11 2020, 7:07 AM
spatel added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
457

Yes - good point. Once the low-bit is removed, the result can only be 0 or -1.

spatel updated this revision to Diff 249612.Mar 11 2020, 7:10 AM
spatel marked an inline comment as done.

Patch updated:

  1. Change the demanded mask predicate to be more liberal; we only need to know that the low-bit is not demanded.
  2. Update tests to more accurately check the mask constraint (adjust 'and' mask and shift amounts).
nikic accepted this revision.Mar 11 2020, 11:06 AM

LGTM

This revision is now accepted and ready to land.Mar 11 2020, 11:06 AM
This revision was automatically updated to reflect the committed changes.