HomePhabricator

[CodeGen][SelectionDAG] More efficient code for X % C == 0 (SREM case)

Description

[CodeGen][SelectionDAG] More efficient code for X % C == 0 (SREM case)

Summary:
This implements an optimization described in Hacker's Delight 10-17:
when C is constant, the result of X % C == 0 can be computed
more cheaply without actually calculating the remainder.
The motivation is discussed here: https://bugs.llvm.org/show_bug.cgi?id=35479.

One huge caveat: this signed case is only valid for positive divisors.

While we can freely negate negative divisors, we can't negate INT_MIN,
so for now if INT_MIN is encountered, we bailout.
As a follow-up, it should be possible to handle that more gracefully
via extra and+setcc+select.

This passes llvm's test-suite, and from cursory(!) cross-examination
the folds (the assembly) match those of GCC, and manual checking via alive
did not reveal any issues (other than the INT_MIN case)

Reviewers: RKSimon, spatel, hermord, craig.topper, xbolva00

Reviewed By: RKSimon, xbolva00

Subscribers: xbolva00, thakis, javed.absar, hiraditya, dexonsmith, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D65366

Details

Event Timeline

RKSimon added inline comments.
/llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp
3815

@lebedev.ri Can't this just be } else { ?

lebedev.ri added inline comments.Aug 13 2019, 8:27 AM
/llvm/trunk/lib/CodeGen/SelectionDAG/TargetLowering.cpp
3815

It currently can since we just checked that next to // Fold remainder of division by a constant..
Should this be simplified like that?