The result of a signed remainder operation with a constant divisor is limited in absolute value to less than the value of the divisor. Following it with code to force the remainder to be positive by adjusting the quotient and remainder values is pretty straightforward. However, if it's written as a loop it doesn't get optimized well. The rtl initially generated appears to have the loop transformed into arithmetic to figure out the number of times the loop would run, in a branch conditionalized on whether the loop would be run at all. (Actually, it appears to run the loop body once, and then do math to figure out how many more times.) However, the compiler doesn't figure out that in that branch, the loop body would be run exactly once, either in the tree or rtl optimizations.
Created attachment 14145 [details] C test case, description and assembly in comments
Just noting for future reference: I looked at the VRP results and that does seem to be where the optimization opportunity is missed; x%y with constant y is VARYING if x is, though it seems to me the result should be [-abs(y)+1,abs(y)-1] for signed math and [0,abs(y)-1] for unsigned math. If x can be constrained to either nonnegative or nonpositive, that reduces the range in the signed case, and if it has a shorter range [x1,x2] where floor(x1/y)==floor(x2/y) it might be constrained further still. If y has a range, the result is still bound by the larger of the absolute values of the ends of the range. (Similarly, though not related to this case, x/const can't be larger than type_max(x)/const. Seems to me that in general there are a few cases where varying should be treated as [type_min,type_max] and processed like any other range, but maybe I'm missing something.) I experimented with a patch to tree-vrp.c to support TRUNC_MOD_EXPR(varying,const), and found I also had to get VRP to understand BIT_NOT_EXPR, but then it generated the same code for both test functions. The patch needs work still, and I need to understand the infinity and overflow stuff in tree-vrp.c a little better to make sure I'm not breaking something.
Confirmed, simple testcase for this really: int f(int a) { int b = a % 3; return b > 4 || b < -4; } This should always return false as b can be proved to be in between -2 and 2. for unsigned mod, the range is [0, C].
I did a little experimentation with git revision c3f18f1 and it looks like it does the right thing (optimizes away the calculations and returns a constant) with Andrew Pinski's simplified test case if the argument is unsigned, but still executes the code if the argument is signed.
Fixed in GCC 5.4 at least.