Re: PATCH: fold BIT_AND_EXPR's with ADDR_EXPR operands

["Richard Guenther" <richard dot guenther at gmail dot com>]

On 9/20/07, Ollie Wild <aaw@google.com> wrote:
> On 9/19/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> > +      /* If arg0 is derived from the address of an object or function, we may
> > +        be able to fold this expression using the object or function's
> > +        alignment.  */
> > +      if (POINTER_TYPE_P (TREE_TYPE (arg0)) &&
> > +         TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0)
> > +       {
> >
> > coding style says the && goes to the next line.  Instead of
> > TREE_CODE (arg1) == INTEGER_CST && TREE_INT_CST_HIGH (arg1) == 0 use
> > host_integer_p (arg1, 1).
>
> OK.
>
> > The description of get_pointer_modulus_and_residue isn't exactly clear
> > to me.  It looks
> > like it should compute the biggest power-of-two N and M so that p % N == M?  But
> > this doesn't have a single solution - so what is it exactly computing?
> >  Please clarify
> > that in the functions description.
>
> It computes a power-of-two N and (arbitrary) M such that N divides (p
> - M).  This tells us that p and M have log2(N) least significant
> digits in common.  M is essentially arbitrary so long as these
> constraints are met.  Given the information at our disposal, we choose
> N as large as possible such that a constant M can be determined.
>
> I'll update the comments.

Thanks.

> >
> > +         expr = get_inner_reference (expr, &bitsize, &bitpos, &offset,
> > +                                     &mode, &unsignedp, &volatilep, false);
> > +         *residue = bitpos / BITS_PER_UNIT;
> > +         if (offset)
> > +           {
> > +             if (TREE_CODE (offset) == INTEGER_CST)
> > +               *residue += TREE_INT_CST_LOW (offset);
> > +             else
> > +               expr = NULL;
> >
> > an INTEGER_CST offset is always accounted for in bitpos,  no need to repeat that
> > here, just bail out.
>
> I'm pretty sure offset *can* be an INTEGER_CST.  The end of
> get_inner_reference looks something like:
>
>     if (host_integerp (offset, 0)) {
>       /* move offset into *pbitbos and return */
>     }
>
>     *pbitpos = tree_low_cst (bit_offset, 0);
>     *poffset = offset;
>
> If a constant offset is too large to store in a HOST_WIDE_INT, it is
> returned in offset instead.  For our purposes, we can safely ignore
> the high order bits.
>
> Or is there some other constraint which limits the size of offsets?

No, you are right.

> > As for the function I would make it return the modulus, that would
> > make the flow easier.
>
> OK.
>
> > +      if (expr && DECL_P (expr))
> > +       *modulus = DECL_ALIGN_UNIT (expr);
> > +      else
> >
> > expr can't be non-NULL here.
>
> If the "if (handled_component_p (expr))" branch gets executed and the
> offset returned from get_inner_reference is not an INTEGER_CST or
> NULL, then expr gets set to NULL.  In all other cases, it is non-NULL.
>  I guess it would be easier to understand if I just returned rather
> than setting expr to NULL.

Doh, indeed, I missed that.

> > I don't see how you protect against a residue bigger
> > than modulus?  But I guess it doesn't matter, still the names are
> > confusing then.
>
> Since it doesn't affect the results of subsequent operations, I don't
> try to limit the size of residue.  Technically, it's an (arbitrary)
> representative of a residue class modulo *modulus.  I could put
> "*residue %= *modulus" before returning if you think that would be
> more comprehensible.  Alternatively, I'll just make the comments
> clearer on this point.

Comments are enough.

> > I would still like you to re-investigate using get_pointer_alignment.
> > Basically you
> > would split out a helper function to get the pointer expression with
> > its ADDR_EXPR
> > stripped off and do
> >
> >    base = get_inner_reference (expr, ...);
> >    base_align = get_pointer_alignment_1 (base, -1);
> >
> > where base_align yields your modulus and from the get_inner_reference result
> > you compute the residue.  And yes, the result from get_pointer_alignment has
> > to be useful for folding as strict alignment targets rely on it for
> > correct code.
>
> Just to make sure I'm following you, are you suggesting that I should
> pull the code that calculates alignments for DECL's, CONSTANT_CLASS's,
> VIEW_CONVERT_EXPR's, and INDIRECT_REF's into a new function,
> get_pointer_alignment_1?  Here's some example code which illustrates
> my concern about using get_pointer_alignment for folding.
>
>     struct S {
>       int i;
>     };
>
>     static const char c[8] __attribute__ ((aligned (4)));
>     static const struct S *ps = (struct S *)&c[1];
>
>     unsigned f (void)
>     {
>       return 3 & (__SIZE_TYPE__)&(ps->i);
>     }
>
> On machines with strict alignment requirements, treating &c[1] as a
> struct S * is illegal, but on x86, this compiles fine without
> triggering a warning.  This generates an ADDR_EXPR whose base is an
> INDIRECT_REF.  Using the logic from get_pointer_alignment, we set the
> alignment to TYPE_ALIGN (TREE_TYPE (indirect_ref_expr)) which on x86
> is 32 (4 bytes).  If we incorporated this logic into
> get_pointer_modulus_and_residue, we'd fold the BITAND_EXPR to 0, but
> the correct value is 1.

Hm, right.  So much for less code duplication :/

There's one extra thing,

+    case POINTER_PLUS_EXPR:
+      {
+       tree op0, op1;
...
+         case MULT_EXPR:
+           op1 = TREE_OPERAND (op1, 1);
+           STRIP_NOPS (op1);
+           if (TREE_CODE (op1) == INTEGER_CST)
+             {

there shouldn't be NOPs if op1 is INTEGER_CST, so the STRIP_NOPS
is not necessary.  What happens if op1 is not INTEGER_CST?  Don't
we need to set modulus/residue to 1/0?  For example

int a, n, m;
if (&a + n*m & 3)
   ...

if n == m == 1 then we leave modulus/residue to that of &a which is
wrong.

Otherwise the patch should be ok after you incorporated the changes
(please re-post it).

Thanks for your patience,
Richard.