The pattern x % constant == 0 (where the constant is odd) can be optimized
more than it currently is, using some modular arithmetic trick, to:
x * inv(constant) <=u MaxValue / constant
This patch sort of does that (hopefully, I did test it and it seemed to work,
and please give me feedback on it, it's only my first try at an llvm patch),
however I ran into a problem. This trick can in theory be easily generalized
to even `constant` (let's ignore powers of two though, they can be done better
the obvious way), but to do so a bitwise rotation is needed.
But when I build it from two shifts:
Value *Mul = Builder->CreateMul(A, Builder->getInt(Multiplier));
Value *RShift = Builder->CreateLShr(Mul, Builder->getInt32(Ctz));
Value *LShift = Builder->CreateShl(Mul, Builder->getInt32(W - Ctz));
Rotated = Builder->CreateOr(RShift, LShift);
Somewhere along the line, the left shift gets merged with the multiplication,
resulting in two multiplications (and some extra stuff), and no rotation.
Having two multiplications mostly defeats this optimization, though it's still
a bit less code than what would be generated currently.
It would be really nice if it could reliably generate something like this on x86:
imul eax, edi, foo
ror eax, bar
cmp eax, baz
; use flags
How should this be handled?
(the attached patch is limited to odd divisors to avoid this problem)
Regards,
Harold
divisibilitypatch (1.66 KB)