Re: pr26026: udiv and umod optimization

[Jeffrey A Law <law at redhat dot com>]

On Thu, 2006-02-09 at 21:45 +1030, Alan Modra wrote:
> On Mon, Feb 06, 2006 at 11:26:29AM -0700, Jeffrey A Law wrote:
> > On Sun, 2006-02-05 at 13:03 +1030, Alan Modra wrote:
> > >           pat1 = reg->node[i].state % ((MAX_UNSIGNED) 1 << width);
> > I'll note that this is something VRP is supposed to handle (the code
> > was moved from DOM into VRP a while back).
> > 
> > VRP should be performing two closely related transformations:
> > 
> > TRUNC_DIV_EXPR -> RSHIFT_EXPR
> > TRUNC_MOD_EXPR -> BIT_AND_EXPR
> > 
> > We basically require that the first operand be > 0 (which can 
> > be derived from the type of propagating range info) and the second
> > operand be a power of two (see simplify_stmt_using_ranges).
> > 
> > So, if VRP isn't performing this transformation on the testcase
> > in question, I'd really like to know why.
> 
> VRP simplifies cases where the divisor is a constant power of two.  In
> this testcase, we have a divisor which is a non-constant power of two.
> (It's a constant power of two shifted left a variable amount.)
Seems to me we could tackle this in a couple easy ways.

First is to create a special range type for values with one and only
one bit set (not a power of two range, consider 0x8000000 on a 32bit
target).   Only a few operations would create such a range (1 << X)
being one of them.  We could then apply the div/mod transformation
when the divisor is one of these ranges.

The second alternative would be to walk the def-use chain back one
step for the divisor and see if the divisor is set from a 1 << X
style operation.  This would be trivial to implement inside the
existing simplification code.

jeff