This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Teach foldSelectICmpAndOr to recognize (select (icmp slt (trunc (X)), 0), Y, (or Y, C2))
ClosedPublic

Authored by craig.topper on Jun 13 2017, 4:42 PM.

Details

Summary

InstCombine likes to turn (icmp eq (and X, C1), 0) into (icmp slt (trunc (X)), 0) sometimes. This breaks foldSelectICmpAndOr's ability to recognize (select (icmp eq (and X, C1), 0), Y, (or Y, C2))->(or (shl (and X, C1), C3), y).

This patch tries to recover this. I had to flip around some of the early out checks so that I could create a new And instruction during the compare processing without it possibly never getting used.

Diff Detail

Event Timeline

craig.topper created this revision.Jun 13 2017, 4:42 PM
spatel edited edge metadata.Jun 15 2017, 10:59 AM

The enhancement looks right, but I'm worried that the existing transform can increase the instruction count if any of the pieces in the pattern have more than one use. Are we missing m_OneUse() in some/all of the matchers?

lib/Transforms/InstCombine/InstCombineSelect.cpp
396

Formatting.

I think you're right. The 'icmp' and the 'or' pieces aren't checked for single use. In the existing code we do reuse the 'and'. In my new code i did make sure the trunc only had one use so that putting back an 'and' doesn't increase anything. So in the existing code we potentially create an 'or' and possibly a 'shift' and only delete a 'select'. And the really bad case we create an 'xor', an 'or', and a 'shift' while only removing a 'select'. This is kinda weird to handle because we don't always create a shift and don't always create an xor.

I think you're right. The 'icmp' and the 'or' pieces aren't checked for single use. In the existing code we do reuse the 'and'. In my new code i did make sure the trunc only had one use so that putting back an 'and' doesn't increase anything. So in the existing code we potentially create an 'or' and possibly a 'shift' and only delete a 'select'. And the really bad case we create an 'xor', an 'or', and a 'shift' while only removing a 'select'. This is kinda weird to handle because we don't always create a shift and don't always create an xor.

Yeah, it's a mess. I think the safe thing would be:

  1. Add tests with extra uses to show how this can go bad.
  2. Check one-use on everything to avoid that.
  3. Make the enhancement proposed in this patch.
  4. Separate out the various cases and remove one-use if possible (I think this would be a rare enhancement, so probably not too important...but I don't have any actual data).

Extra use tests committed in r305509

Rebase on top of the one use fixes to the existing code.

spatel accepted this revision.Jun 22 2017, 6:25 AM

LGTM. See inline for a nit.

lib/Transforms/InstCombine/InstCombineSelect.cpp
384–388

That "line" still looks awful. :)
Give the OneBitSet variable a name and its own line(s), so clang-format can do better?

This revision is now accepted and ready to land.Jun 22 2017, 6:25 AM
This revision was automatically updated to reflect the committed changes.