This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Canonicalize sadd.with.overflow to sadd.sat
ClosedPublic

Authored by dmgreen on Oct 21 2019, 5:54 AM.

Details

Summary

This adds to D69245, adding extra signed patterns for folding from a sadd_with_overflow to a sadd_sat. These are more complex than the unsigned patterns, as the overflow can occur in either direction.

For the add case, the positive overflow can only occur if both of the values are positive (same for both the values being negative). So there is an extra select on whether to use the positive or negative overflow limit.

Diff Detail

Event Timeline

dmgreen created this revision.Oct 21 2019, 5:54 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 21 2019, 5:54 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
dmgreen updated this revision to Diff 226111.Oct 23 2019, 3:15 AM

Just a rebase.

This patch is doing too much at once - i think there are ~14 folds being added here.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1762

s/A/TrueVal/, s/B/FalseVal/

1807

/*IsAdd=*/true

1818

/*IsAdd=*/false

Yeah, this one got a bit big! Let me at least split it in half.

dmgreen updated this revision to Diff 227580.Nov 2 2019, 9:25 AM
dmgreen edited the summary of this revision. (Show Details)

Split out the subs, leaving just the adds here

Alives, all of which pass:

Name: SAdd_x_lt0
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp slt i8 %x, 0
  %s = select i1 %c, i8 -128, i8 127
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_x_lt1
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp slt i8 %x, 1
  %s = select i1 %c, i8 -128, i8 127
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_x_lg0
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp sgt i8 %x, 0
  %s = select i1 %c, i8 127, i8 -128
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_x_lg1
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp sgt i8 %x, -1
  %s = select i1 %c, i8 127, i8 -128
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_y_lt0
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp slt i8 %y, 0
  %s = select i1 %c, i8 -128, i8 127
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_y_lt1
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp slt i8 %y, 1
  %s = select i1 %c, i8 -128, i8 127
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_y_lg0
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp sgt i8 %y, 0
  %s = select i1 %c, i8 127, i8 -128
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y

Name: SAdd_y_lg1
  %ao = sadd_overflow i8 %x, %y
  %a = extractvalue %ao, 0
  %o = extractvalue %ao, 1
  %c = icmp sgt i8 %y, -1
  %s = select i1 %c, i8 127, i8 -128
  %x5 = select i1 %o, i8 %s, i8 %a
=>
  %x5 = sadd_sat %x, %y
dmgreen updated this revision to Diff 227587.Nov 2 2019, 1:06 PM

Updated the patterns to be more straight forward.

spatel accepted this revision.Nov 5 2019, 9:57 AM

LGTM (but give @lebedev.ri a chance to comment again too)

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1755–1756

Sink these values to their uses in IsMinMax()?

1765

Probably want to make this a const reference (avoid copy for crazy big numbers).

This revision is now accepted and ready to land.Nov 5 2019, 9:57 AM

Not a fan of such large amount of patterns.
There's obvious duplication here:

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1772
if(Op != X && Op != Y)
  return false;
1775–1780

drop Op == X &&

1783–1792

drop

lebedev.ri accepted this revision.Nov 10 2019, 10:01 AM

Not a fan of such large amount of patterns.
There's obvious duplication here:

To be noted, those can be fixed when committing, no need for further review.

dmgreen updated this revision to Diff 228627.Nov 10 2019, 3:20 PM
dmgreen marked 2 inline comments as done.

Right. I was aiming for a symmetry between the adds and the subs. But you are probably correct that it's better simplified like this.