Page MenuHomePhabricator

[InstCombine] fold min/max tree with common operand (PR35717)
ClosedPublic

Authored by spatel on Dec 27 2017, 4:14 PM.

Details

Summary

This might be over the edge of what we want from instcombine, but I'm not sure. There is precedence for factorization transforms in instcombine for FP ops with fast-math.

I think it would take more work to add this to reassociate because that's specialized for binops, and min/max are not binops (or even single instructions). Also, I don't have evidence that larger min/max trees than this exist in real code.

In the motivating example from https://bugs.llvm.org/show_bug.cgi?id=35717 , we have:

int test(int xc, int xm, int xy) {
  int xk;
  if (xc < xm)
    xk = xc < xy ? xc : xy;
  else
    xk = xm < xy ? xm : xy;
  return xk;
}

This patch solves that problem because we recognize more min/max patterns after rL321672

https://rise4fun.com/Alive/Qjne
https://rise4fun.com/Alive/3yg

Diff Detail

Repository
rL LLVM

Event Timeline

spatel created this revision.Dec 27 2017, 4:14 PM
RKSimon added a subscriber: RKSimon.Jan 2 2018, 4:11 AM
spatel updated this revision to Diff 128565.Jan 3 2018, 2:33 PM
spatel edited the summary of this revision. (Show Details)

Ping.

Patch updated:
I adjusted the use checks to be '<='. This accounts for non-canonical min/max patterns as seen in the motivating test (the compare operands are not the same as the select operands). So now this patch should be the last step towards solving PR35717.

hfinkel accepted this revision.Jan 7 2018, 9:20 AM

If I'm right about the easy FP cases, I'd like to see those handled in follow-up. Regardless, this LGTM.

lib/Transforms/InstCombine/InstCombineSelect.cpp
1297 ↗(On Diff #128565)

I think that you can easily handle most of the interesting FP cases by checking all of the select pattern results for NaNBehavior == SPNB_NA || NaNBehavior == SPNB_RETURNS_ANY. The other cases will require further thought (so make sure we had the correct relative ordering of all the potentially-NaN inputs).

This revision is now accepted and ready to land.Jan 7 2018, 9:20 AM
spatel added a comment.Jan 8 2018, 7:00 AM

If I'm right about the easy FP cases, I'd like to see those handled in follow-up. Regardless, this LGTM.

Thanks - yes, I'm planning on that; still working on the similar FP min/max enhancement for early-cse ( D41136 ) too.

This revision was automatically updated to reflect the committed changes.