This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Fix PR 33870


On Nov 13, 2007 5:08 PM, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> On Nov 13, 2007 4:44 PM, Diego Novillo <dnovillo@google.com> wrote:
> > Richard Guenther wrote:
> >
> > > taking the address of result.x.pDirty causes the SFT to be marked as
> > > in substructure and the problem re-surfaces.
> >
> > Yes.  Thanks for the test case.  The original patch did not take into
> > account that the nesting level of the memory reference is also important.
> >
> > There are two problems here:
> >
> > 1- Given an arbitrary memory expression M dereferencing a pointer P into
> > a nested structure, the offset computed for M is the offset starting at
> > P.  However, the offsets computed for the original SFTs are offsets from
> > the top of the pointed-to memory object O.  So, when we recognize this
> > situation, we must adjust the offsets.  This was the situation
> > recognized and fixed by the original patch.
> >
> > The bug was in the detection of whether P is "pointing to the middle of
> > an object".  This is where the nesting level comes in to play.  Suppose
> > that M was the expression p_3->b[3] and the original pointed-to object
> > was v.x.y:
> >
> >                 struct {
> >                         ...
> >                         struct {
> >                                 ...
> >                                 struct {
> >                                         ...
> >                                         int b[4];
> >                                 } y;
> >                         } x;
> >                 } v;
> >
> >                 p_3 = &v.x.y;
> >
> > If alias analysis created SFTs for this structure, the array 'b' will
> > have 4 SFTs associated with it.  Say SFT.12, SFT.13, SFT.14 and SFT.15.
> >   However, only SFT.12 will be added to the alias set of p_3's name tag.
> >
> > So, when we see the expression 'p_3->b[3]', we compute an offset of 96,
> > but we need SFT.14 which will probably have an offset much higher than
> > that.  So, we adjust 96 by the offset of SFT.12 and get to SFT.14.
> >
> > In the original patch, we recognized this situation by asking whether
> > the SFT.12 was inside a nested structure.  However, it may happen that
> > the pointer was actually pointing to the base of the original object
> > 'v'.  In which case, we would have the expression 'p_3->x.y.b[3]', which
> > also takes us to SFT.12.
> >
> > But in this case, the offset we computed from 'p_3->x.y.b[3]' is
> > *already* the right offset, so adding the offset of SFT.12 to it gives
> > us the wrong offset.  So, what this patch does is determine the nesting
> > level of each SFT and the nesting level of the memory expression.  We
> > only need to adjust the offset of an SFT if the nesting level of the
> > memory expression is lower than the nesting level of the SFT that we are
> > analyzing.
> >
> >
> > 2- The second problem we have with this scheme is that we rely on the
> > presence of key SFTs to adjust offsets when we detect references to
> > nested aggregates.  This is something we cannot easily undo because
> > inside the operand scanner we cannot really start doing use-def chain
> > chasing to determine the original pointed-to objects.  This work has
> > already been done by alias analysis, so duplicating this in the operand
> > scanner would be wasteful.
> >
> > This means that this scheme cannot tolerate these key SFTs to be
> > partitioned away.  If they are partitioned, then inside the operand
> > scanner is essentially impossible to determine where in the structure is
> > an arbitrary memory expression referring to.  This is shown in the new
> > test gcc.dg/tree-ssa/alias-16.c.
> >
> > One way to deal with this would be to use the pointed-to set for the
> > base pointer instead of the alias set of the name tag.  This has the
> > problem that we'd miss the compile-time benefits of partitioning, as we
> > would be traversing the original sets instead of the partitioned
> > (smaller) alias sets.  Also, we may want to get rid of the duplicate
> > pointed-to/alias sets in the future (not sure if they're both worth
> > keeping).
> >
> > The other way of dealing with this is to recognize which SFTs are
> > important to not partition and make sure they are never partitioned.
> > During alias analysis, if a nested SFT is added to the alias set of a
> > pointer, then it is marked as unpartitionable.  The partitioner, in
> > turn, gives these SFTs a very high score and makes sure that they are
> > never added to a partition.  The effects of this are/should be
> > negligible as it only involves a single SFT and nested structures.
> >
> > The new test alias-16.c tests for these edge cases.
> >
> > Tested on x86_64 and ppc64.  Committed to trunk.
>
> Thanks.  Now, you should be able to do all this without introducing
> all the nesting-level stuff if you make all pointed-to SFTs unpartitionable.
>
> In fact,
>
> > -  if (SFT_IN_NESTED_STRUCT (var))
> > +  if (full_ref
> > +      && SFT_NESTING_LEVEL (var) > 0
> > +      && ref_nesting_level (full_ref) < SFT_NESTING_LEVEL (var))
> >      {
> >        /* Since VAR is an SFT inside a nested structure, the OFFSET
> >          computed by get_ref_base_and_extent is the offset from the
> > -        start of the immediately containing structure.  However, to
> > -        find out what other SFTs are affected by this reference, we
> > -        need to know the offsets starting at the root structure in
> > -        the nesting hierarchy.
> > +        start of the immediately containing structure.  If VAR is an
> > +        SFT inside a nested structure, then FULL_REF may be a
> > +        reference to the structure immediately enclosing SFT, and so
> > +        OFFSET will be the offset from the start of the immediately
> > +        enclosing structure.
> > +
> > +        However, to find out what other SFTs are affected by this
> > +        reference, we need to know the offsets starting at the root
> > +        structure in the nesting hierarchy.
> >
> >          For instance, given the following structure:
>
> This looks like a pure workaround for that you do not retain the offset
> zero SFT as unpartitionable.  Otherwise you'd enter this function with
> it (if it is pointed-to), and you can always add the pointed-to SFT offset.
>
> I believe your patch makes it more twisted than it needs to be (it doesn't
> even look like an optimization, as you are scanning for pointed-to offset
> zero multiple times, for all pointed-to SFTs with a nesting level >
> than the ref).
>
> And don't you still get
>
> struct X {
>   int i;
>   int a[4];
> } x;
>
> p = &x->a[0];
> return p[3];
>
> wrong?  You don't keep the SFT for a[0] from being partitioned away(?).
> [it get's twisted to force GCC to generate IL with an ARRAY_REF here, but
> with fortran it's possible I believe, so this is a theory example]

Ok, I see that even for

  struct X {
     int i;
     int a[4];
  };

the SFTs for i and a have a nesting level of 1 (that is, if pointed-to, they
are disregarded for partitioning).  So the case that is not fixed yet is only
the case of a toplevel array:

struct X {
  int i;
  int a[4];
} m;

int a[4];

static inline void *fwd(void *p) { return p; }

int foo(int b)
{
  int (*p)[4] = b ? &a : &m.a;
  a[3] = 0;
  (*p)[3] = 1;
  return (*p)[3] + (*p)[2] + (*p)[1] + a[0] + a[3];
}

extern void abort (void);

int main()
{
  int i;
  for (i = 0; i < 4; ++i)
    a[i] = 0;
  if (foo(1) != 2)
    abort ();
  return 0;
}

fails with at least -O --param max-aliased-vops=1

Because we partition away the SFT for &a[0].  I'm going to fix this by removing
all the nesting level logic again and just mark all pointed-to SFTs as
unpartitionable.  That means, the following fixes this:

Index: tree-ssa-structalias.c
===================================================================
--- tree-ssa-structalias.c      (revision 130174)
+++ tree-ssa-structalias.c      (working copy)
@@ -4770,7 +4770,7 @@ set_uids_in_ptset (tree ptr, bitmap into
                         this SFT because the operand scanner will not
                         be able to find the other SFTs next to this
                         one.  */
-                     if (SFT_NESTING_LEVEL (sft) > 0)
+                     if (1 || SFT_NESTING_LEVEL (sft) > 0)
                        SFT_UNPARTITIONABLE_P (sft) = true;
                    }
                }

Richard.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]