This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold BW/2+1 tops bits are same pattern
ClosedPublic

Authored by dmgreen on Sep 2 2021, 6:57 AM.

Details

Summary

Match icmp eq (trunc (lsr A, BW), (ashr (trunc A), BW-1)), which checks the top BW/2 + 1 bits are all the same. Create "A >=s INT_MIN && A <=s INT_MAX", which we generate as "icmp ult (add A, 2^BW-1), 2^BW" to skip a few steps of instcombining.
https://alive2.llvm.org/ce/z/NjH6Ty
https://alive2.llvm.org/ce/z/_fEQ9P

Diff Detail

Event Timeline

dmgreen created this revision.Sep 2 2021, 6:57 AM
dmgreen requested review of this revision.Sep 2 2021, 6:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 2 2021, 6:57 AM
spatel added inline comments.Sep 2 2021, 9:58 AM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4510

We don't need the commutative matcher (and the regression test shows this). That's because we always canonicalize the 'ashr' as op0 and 'trunc' as op1 based on getComplexity.

Actually, we don't need to rematch the icmp at all if we handle both predicates - see next comment.

4514

We should handle ICMP_NE for symmetry. Flip from ULT to UGE?
https://alive2.llvm.org/ce/z/_fEQ9P

dmgreen added inline comments.Sep 2 2021, 12:10 PM
llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4510

Oh that's good to hear. Yeah the only reason for starting the match at the ICmp was to get commutativity through the m_c_ICmp.

dmgreen updated this revision to Diff 370358.Sep 3 2021, 1:10 AM
dmgreen edited the summary of this revision. (Show Details)

Remove commutative matchers, adding NE handling.

foad added a subscriber: foad.Sep 3 2021, 2:12 AM

"A >s INT_MIN && A <s INT_MAX"

>=s and <=s, in the commit message and the inline comment?

dmgreen updated this revision to Diff 370578.Sep 3 2021, 7:03 AM
dmgreen edited the summary of this revision. (Show Details)

Yep, thanks. Update comment with = bounds.

spatel added a comment.Sep 3 2021, 7:06 AM

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

spatel added a comment.Sep 3 2021, 7:12 AM

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

Disregard that failed attempt at a proof. :)
Trying to find another example now...

foad added a comment.Sep 3 2021, 7:12 AM

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

What does ashr i8 %t2, 25 do in that example? Surely it's poison?

spatel added a comment.Sep 3 2021, 8:18 AM

The half-width truncate clause seems too restrictive. I assume we want to catch a case like this too:
https://alive2.llvm.org/ce/z/UAQ4yQ

What does ashr i8 %t2, 25 do in that example? Surely it's poison?

Yes, that was all wrong. If we're not doing a half-width truncate, the bits aren't lined up consecutively, so it probably doesn't matter:
https://alive2.llvm.org/ce/z/YdoXeg

Yeah, that was what I thought about the now-half-width-cases. The maths doesn't work at as well, and they at least feel like a different case to me.

spatel accepted this revision.Sep 7 2021, 5:39 AM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
4503

lsr -> lshr

This revision is now accepted and ready to land.Sep 7 2021, 5:39 AM

I agree that the double-the-bitwidth precondition is needed *for this pattern*, but there are other possible cases:
https://alive2.llvm.org/ce/z/RjUMzM (double)
https://alive2.llvm.org/ce/z/Jd3aHC (more than double => sext)
https://alive2.llvm.org/ce/z/CS2xkv (less than double => trunc)

lebedev.ri accepted this revision.Sep 7 2021, 6:07 AM
This revision was landed with ongoing or failed builds.Oct 29 2021, 4:30 AM
This revision was automatically updated to reflect the committed changes.