(n * 3 % 3) is not known to be zero.

[nlewycky]

Bugzilla Link	712
Resolution	FIXED
Resolved on	Mar 06, 2010 14:00
Version	1.0
OS	All

Extended Description

There is a missed optimization opportunity in the following code:

int case1(unsigned char c)
{
unsigned long x = c * 3;

return x % 3;
}

Of course, the modulo operation is a form of division, so it should be combined
with the multiply and realize that the result must be zero. The resulting ll is:

int %case1(ubyte %argc) {
entry:
%tmp.1 = cast ubyte %argc to uint ; [#uses=1]
%tmp.3 = mul uint %tmp.1, 3 ; [#uses=1]
%tmp.5 = rem uint %tmp.3, 3 ; [#uses=1]
%tmp.6 = cast uint %tmp.5 to int ; [#uses=1]
ret int %tmp.6
}

I expected the following output:

int %case1(ubyte %c) {
entry:
ret int 0
}

Note that it works properly where you replace "3" with a power of two.

[nlewycky]

assigned to @lattner

[lattner]

Verified. I'll try to take care of this tonight.

FWIW, this is handled by extract_muldiv in GCC.

Thanks!

-Chris

[nlewycky]

Hi, Chris.

I'd appreciate if you could either post the patch, or a link to the patch in
this bug after you fix it. I'm hoping to learn LLVM, little by little.

Thanks!

[lattner]

I certainly will. Thanks again for the bug report!!

-Chris

[lattner]

Implemented. Testcase here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060227/032183.html

Patch here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060227/032184.html

BTW, another good way to learn about LLVM is to sign up for the llvm-commits list.

-Chris

[nlewycky]

Thanks Chris. I've been reading the scalar optimizations code.

It works where variable "x" is declared as an int or uint. However, my testcase
as originally posted still doesn't get optimized away. The problem seems to be
an extra cast from int c*3 to ulong (this wasn't there when I tested with LLVM
1.6), before the remainder is taken:

int %case1(ubyte %c) {
entry:
%tmp.1 = cast ubyte %c to int ; [#uses=1]
%tmp.2 = mul int %tmp.1, 3 ; [#uses=1]
%tmp.3 = cast int %tmp.2 to ulong ; [#uses=1]
%tmp.5 = rem ulong %tmp.3, 3 ; [#uses=1]
%tmp.6 = cast ulong %tmp.5 to int ; [#uses=1]
ret int %tmp.6
}

Peering through a cast should work in general for upcasting and will work for
downcasting iff you can show that the values are in range for the new type.

I found another similar issue (should I file a new bug?) by adding "+1" to x;
((n*3)+1)%3 --> 1%3 doesn't happen. I suggest it's related because the fix only
covered multiply and shiftleft.

[lattner]

Extending the existing code to handle the cast seems reasonable, I can do that, perhaps tomorrow.

Handling: ((n*3)+1)%3 --> 1%3 is tricker. How often does this sort of code occur in practice? Do you
know of any real-world examples where it does?

-Chris

[nlewycky]

I haven't seen any examples of ((n*C1)+C2)%C3 in the real world. It would
probably be too slow to test for in a production compiler. I may try to write a
pass for that myself, as an exercise.

[lattner]

Ok, sounds good. I'll take care of the casting cases tonight.

[lattner]

More aggressive case fixed. Tests here:

Patch here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060227/032247.html

Note that GCC doesn't handle the AND case.
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20060227/032246.html

-Chris