[Codegen][SelectionDAG] X u% C == 0 fold: non-splat vector improvements

Authored by lebedev.ri on Jul 20 2019, 9:33 AM.


[Codegen][SelectionDAG] X u% C == 0 fold: non-splat vector improvements

Four things here:

  1. Generalize the fold to handle non-splat divisors. Reasonably trivial.
  2. Unban power-of-two divisors. I don't see any reason why they should be illegal.
    • There is no ban in Hacker's Delight
    • I think the ban came from the same bug that caused the miscompile in the base patch - in floor((2^W - 1) / D) we were dividing by D0 instead of D, and we were ensuring that D0 is not 1, which made sense.
  3. Unban 1 divisors. I no longer believe Hacker's Delight actually says that the fold is invalid for D = 0. Further considerations:
    • We know that
      • (X u% 1) == 0 can be constant-folded to 1,
      • (X u% 1) != 0 can be constant-folded to 0,
    • Also, we know that
      • X u<= -1 can be constant-folded to 1,
      • X u> -1 can be constant-folded to 0,
    • https://godbolt.org/z/7jnZJX https://rise4fun.com/Alive/oF6p
    • We know will end up with the following: (setule/setugt (rotr (mul N, P), K), Q)
    • Therefore, for given new DAG nodes and comparison predicates (ule/ugt), we will still produce the correct answer if: Q is a all-ones constant; and both P and K are *anything* other than undef.
    • The fold will indeed produce Q = all-ones.
  4. Try to re-splat the P and K vectors - we don't care about their values for the lanes where divisor was 1.

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

Reviewed By: RKSimon

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

Tags: #llvm

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

llvm-svn: 366637