This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Demand bits of UMin
ClosedPublic

Authored by dmgreen on Oct 9 2018, 12:18 PM.

Details

Summary

This is the umin alternative to the umax code from D53033, If I'm getting the maths correct.

As Sanjay suggested, we can use De Morgan's law on the umax case to bring us to the same thing on umin, but using countLeadingOnes, not countLeadingZeros.

https://rise4fun.com/Alive/O9i

Diff Detail

Repository
rL LLVM

Event Timeline

dmgreen created this revision.Oct 9 2018, 12:18 PM
dmgreen updated this revision to Diff 168973.Oct 10 2018, 3:54 AM
dmgreen edited the summary of this revision. (Show Details)

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

Huh https://github.com/nunoplopes/alive/search?utf8=%E2%9C%93&q=countLeadingOnes&type=
CC @nlopes

lebedev.ri accepted this revision.Oct 10 2018, 4:17 AM

Same as with D53033, looks ok, but maybe wait a bit for someone else.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
335–336 ↗(On Diff #168973)

Nit, probably ignore:
Is

DemandedMask.countTrailingZeros() + C->countLeadingOnes() >= C->getBitWidth()

worse?
I guess you could write it as

DemandedMask.countTrailingZeros() >= (~C)->getActiveBits()

but that will be less readable, and may be worse if the compiler won't see through the bitwise-inversion.

test/Transforms/InstCombine/minmax-demandbits.ll
190 ↗(On Diff #168973)

There are negative tests here for this fold?

This revision is now accepted and ready to land.Oct 10 2018, 4:17 AM
dmgreen updated this revision to Diff 169002.Oct 10 2018, 7:01 AM

Just added a new test, and changed some of the others around a little.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
335–336 ↗(On Diff #168973)

Yeah, I was trying to make it look like the above umax example. With DemandedMask.countTrailingZeros() >= <something>. I have no strong opinion, let me know if I should change it.

Luckily, it appears that Alive can do countLeadingOnes too (although I don't see it anywhere in the sources I have).
https://rise4fun.com/Alive/O9i

Huh https://github.com/nunoplopes/alive/search?utf8=%E2%9C%93&q=countLeadingOnes&type=
CC @nlopes

This is the page I look at as reference for alive coding:
https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

spatel accepted this revision.Oct 10 2018, 2:39 PM

LGTM - see inline for a couple of nits.

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
330–332 ↗(On Diff #169002)

Period at end of each sentence. Rather than random math, note this as the DeMorgan'd version of the umax logic.

335 ↗(On Diff #169002)

Might read easier and fit better in 80-cols if we give the CTZ a name and use it here and for umax:
unsigned LowestDemandedBit = DemandedMask.countTrailingZeros();

This is the page I look at as reference for alive coding:
https://github.com/nunoplopes/alive/blob/newsema/rise4fun/language

Thanks. Different branch, that makes sense.

This revision was automatically updated to reflect the committed changes.