This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] fold sign-bit compares of srem
ClosedPublic

Authored by spatel on Sep 8 2019, 1:58 PM.

Details

Summary

(srem X, pow2C) sgt/slt 0 can be reduced using bit hacks as shown:
https://rise4fun.com/Alive/jSO
A '2' divisor allows slightly more folding:
https://rise4fun.com/Alive/tDBM

Any chance to remove an 'srem' use is probably worthwhile, but I've kept this to the strict improvement case because it may expose other missing folds. That means it does nothing for PR21929 yet:
https://bugs.llvm.org/show_bug.cgi?id=21929

Diff Detail

Repository
rL LLVM

Event Timeline

spatel created this revision.Sep 8 2019, 1:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 8 2019, 1:58 PM

Slightly beyond the scope of this patch, but would it be realistic to support non-constant cases? I know at present m_Power2 can't handle this

spatel added a comment.Sep 9 2019, 7:04 AM

Slightly beyond the scope of this patch, but would it be realistic to support non-constant cases? I know at present m_Power2 can't handle this

Yes, this patch is only for constant divisors. We could use ValueTracking's isKnownToBeAPowerOfTwo() and be more general. But in that case, the transform would require 2 extra instructions: sub + or to produce the bitmask. It's unusual for instcombine to increase instruction sequences, but this is probably a justifiable case since there's almost no analysis for srem. Another option would be to add an SDAG expansion for that.

I'm not sure about the cases where we'd have to increase instruction count,
those may be best suited for codegen, but this patch looks good, some nits.

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
2255–2256 ↗(On Diff #219277)

Match an 'is positive' or 'is negative' comparison of remainder by a constant power-of-2 value

2265–2268 ↗(On Diff #219277)

I'd maybe split this into correctness check, and one-use check, to make the comment even more obvious.

spatel updated this revision to Diff 219610.Sep 10 2019, 2:45 PM
spatel marked 2 inline comments as done.

Patch updated:
Corrected code comment and improved structure.

This revision is now accepted and ready to land.Sep 10 2019, 3:00 PM
This revision was automatically updated to reflect the committed changes.