This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Get rid of select of bittest (PR36950 / PR17564)
ClosedPublic

Authored by lebedev.ri on Mar 30 2018, 2:29 PM.

Details

Summary

See PR36950, PR17564, D45065, D45107

This is complementary to D45065, either one will solve PR17564,
but this one will add one more fold pattern, which may be useful.

Notes:

  • I don't actually check that C is < 32, some other fold already happens by then. Should i check anyway?
  • Am i missing some has-one-use checks?

Please review carefully.

Alive proof: https://rise4fun.com/Alive/uiH

Testing: ninja check-llvm

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri planned changes to this revision.Mar 30 2018, 3:24 PM

Hmm yeah, as expected, not fully correct.
https://rise4fun.com/Alive/rD0 (should be 341, not 21760)

  • Rebased ontop of updated tests
  • Fixed nasty bug when accidentally using m_Value() instead of m_Specific() (test included)

Fix vector handling, too.

  • Rebased ontop of revised tests.
  • Handle non-splat constant vectors too.
lebedev.ri added inline comments.Mar 31 2018, 2:18 PM
lib/Transforms/InstCombine/InstCombineSelect.cpp
1542

Hmm, or should this be separated into two(?) different folds,
one to get rid of lshr, and another to get rid of select (i.e. the first ^ variant only, without lshr)?

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

spatel added a comment.Apr 4 2018, 3:08 PM

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

Ok, if there's no easy way to meld these together, then just move it over. I wasn't sure; just seemed like there was similarity with the existing code.
A couple of things to change while doing that:

  1. We should separate the case with a shift into its own block. Creating a shift-by-zero and then deleting it isn't efficient. Code readability will also improve.
  2. We need to check 'm_OneUse' to make sure we're not creating more instructions than we're removing. There should also be some negative tests to exercise that. Example:
declare void @use32(i32)
declare void @use1(i1)

define i32 @f_var1(i32 %x, i32 %y) {
  %t3 = and i32 %x, %y
  %t4 = icmp eq i32 %t3, 0
  %t5 = and i32 %x, 1
  %t6 = select i1 %t4, i32 %t5, i32 1
  call void @use32(i32 %t3)
  call void @use32(i32 %t5)
  call void @use1(i1 %t4)
  ret i32 %t6
}

We shouldn't have 3 extra instructions here.

I think we should solve this using something like D45108 instead, but I need to look closer at how the case in the bug report escaped the matching that we already have in foldSelectInstWithICmp() and foldSelectICmpAnd().

Ok, so let's look at those functions

So while i don't have any particular expirience with InstCombine,
i don't see anything that would suggest that foldSelectInstWithICmp()
is already supposed to handle that case. Am i wrong?

But yes, i should at the very least move the code into that function.

Ok, if there's no easy way to meld these together, then just move it over.

I wasn't sure; just seemed like there was similarity with the existing code.

I agree that the code is *similar*.
But right now i'm not seeing enough similarities yet to combine them.

A couple of things to change while doing that:

  1. We should separate the case with a shift into its own block. Creating a shift-by-zero and then deleting it isn't efficient. Code readability will also improve.

Ok, sure.

  1. We need to check 'm_OneUse' to make sure we're not creating more instructions than we're removing. There should also be some negative tests to exercise that. Example:
declare void @use32(i32)
declare void @use1(i1)

define i32 @f_var1(i32 %x, i32 %y) {
  %t3 = and i32 %x, %y
  %t4 = icmp eq i32 %t3, 0
  %t5 = and i32 %x, 1
  %t6 = select i1 %t4, i32 %t5, i32 1
  call void @use32(i32 %t3)
  call void @use32(i32 %t5)
  call void @use1(i1 %t4)
  ret i32 %t6
}

We shouldn't have 3 extra instructions here.

Thank you for the test! I was wondering about that (in the differential's description)

lebedev.ri updated this revision to Diff 141152.Apr 5 2018, 7:33 AM
  • Refactored into a function
  • Flattened the nesting
  • Added some one-use checks
  • Do not create shl if it is to be removed immediately.

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

spatel added a comment.Apr 5 2018, 8:59 AM

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

You've already coded it to allow that case, right? Just remove the m_NonNegative() check and add a test?

FIXME: do we want to allow the shift amount to be a value (not a constant), too?

You've already coded it to allow that case, right?

Yes, but not intentionally.

Just remove the m_NonNegative() check and add a test?

Doing that already right now :)

spatel added inline comments.Apr 6 2018, 11:11 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
407

IIRC, we don't want Alive links in the LLVM source (but Alive links in commit messages and bug reports are fine) - avoid any potential legal/licensing problems.

lebedev.ri added inline comments.Apr 6 2018, 11:22 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
407

First time i'm reading about this, will remove.
Source only, it's ok in tests?

lebedev.ri marked 2 inline comments as done.
spatel added inline comments.Apr 6 2018, 11:46 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
407

No, we don't want the links in tests either because those are included in the greater body of 'LLVM source'.
So you should remove the existing link from the test file too. It's fine to paste the Alive proof text if you want though.

There's no official guideline about this AFAIK, but there probably should be. I'm certain that I also wanted to include an Alive link in some patch long ago and was told not to, but I can't find that thread.

I'm not an expert, so if you want better answers, it's best to ask on llvm-dev.

lebedev.ri marked an inline comment as done.

The fact that comments-that-are-marked-as-done are submitted by the diff update, but not the new comments i added, always catches me off guard.

lib/Transforms/InstCombine/InstCombineSelect.cpp
407

... Ok, good to know.

spatel accepted this revision.Apr 6 2018, 1:38 PM

LGTM.

This revision is now accepted and ready to land.Apr 6 2018, 1:38 PM

LGTM.

Thank you for the review!

This revision was automatically updated to reflect the committed changes.