[Bug tree-optimization/33259] New: limited range of remainder operation can prove loop runs at most once

[Bug tree-optimization/33259] New: limited range of remainder operation can prove loop runs at most once

[raeburn at raeburn dot org]

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.


-- 
           Summary: limited range of remainder operation can prove loop runs
                    at most once
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: raeburn at raeburn dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33259

[Bug tree-optimization/33259] limited range of remainder operation can prove loop runs at most once

[raeburn at raeburn dot org]

------- Comment #1 from raeburn at raeburn dot org  2007-08-31 08:06 -------
Created an attachment (id=14145)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14145&action=view)
C test case, description and assembly in comments


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33259

[Bug tree-optimization/33259] limited range of remainder operation can prove loop runs at most once

[raeburn at raeburn dot org]

------- Comment #2 from raeburn at raeburn dot org  2008-08-16 18:18 -------
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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33259

[Bug tree-optimization/33259] limited range of remainder operation can prove loop runs at most once

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2008-12-27 07:18 -------
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].


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
           Severity|normal                      |enhancement
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
  GCC build triplet|i686-pc-linux-gnu           |
   GCC host triplet|i686-pc-linux-gnu           |
 GCC target triplet|i686-pc-linux-gnu           |
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2008-12-27 07:18:40
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33259

[Bug tree-optimization/33259] limited range of remainder operation can prove loop runs at most once

[raeburn at raeburn dot org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=33259

--- Comment #4 from Ken Raeburn <raeburn at raeburn dot org> 2011-09-05 22:45:28 UTC ---
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.