[InstCombine] Demand bits of UMAX
ClosedPublic

Authored by dmgreen on Tue, Oct 9, 12:00 PM.

Details

Summary

This is part of of D52508. It uses the demand bits of umax(A, C) to prove we use just A, so long as:
"The lowest non-zero bit of DemandMask is higher than the highest non-zero bit of C"

https://rise4fun.com/Alive/q4Z

Conceptually, this works because:
if A > C, we pick A. No big deal.
if A < C then all the demanded bits of A == demanded bits of C, so we can pick either and get the same result. So we pick A.

Diff Detail

Repository
rL LLVM
dmgreen created this revision.Tue, Oct 9, 12:00 PM

Unfortunately I don't have a great way to prove this with Alive, as I don't believe it can do clz/ctz's in preconditions.

WDYM?
Seems to work fine https://rise4fun.com/Alive/BKg
https://github.com/nunoplopes/alive/blob/eda494ab9ad668fe1bce02978bd018b917d88230/constants.py#L257-L258

Ah, I must have been looking at the wrong bit of code. Thanks!

In that case, https://rise4fun.com/Alive/q4Z

lebedev.ri added inline comments.Tue, Oct 9, 12:34 PM
lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
326–327 ↗(On Diff #168817)

I wonder if it's any cleaner to write this as

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

https://rise4fun.com/Alive/o49
I.e. that leading zeros (in high bits), and trailing zeros (in low bits) overlap/touch.

craig.topper added inline comments.Tue, Oct 9, 1:14 PM
lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
326–327 ↗(On Diff #168817)

How about DemandedMask.countTrailingZeros() >= C->getActiveBits()

dmgreen updated this revision to Diff 168971.Wed, Oct 10, 3:46 AM
dmgreen edited the summary of this revision. (Show Details)

Updated to use activeBits. Thanks for the suggestions.

lebedev.ri accepted this revision.Wed, Oct 10, 3:51 AM

Looks good, but maybe wait a bit for someone else to confirm.

This revision is now accepted and ready to land.Wed, Oct 10, 3:51 AM
spatel accepted this revision.Wed, Oct 10, 2:23 PM

LGTM

spatel added inline comments.Wed, Oct 10, 2:25 PM
lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp
323 ↗(On Diff #168971)

Add period at end of sentence.

This revision was automatically updated to reflect the committed changes.