Re: More fun with aliasing - removing assignments?

Re: More fun with aliasing - removing assignments?

[Ian Lance Taylor]

Harald van Dijk <truedfx@gentoo.org> writes:

> I finally managed to track down the problem I've been having to this
> short code:
> 
> 	typedef struct {
> 	    unsigned car;
> 	    unsigned cdr;
> 	} cons;
> 
> 	void nconc (unsigned x, unsigned y) {
> 	    unsigned *ptr = &x;
> 	    while(!(*ptr & 3))
> 	        ptr = &((cons *)(*ptr))->cdr;
> 	    *ptr = y;
> 	}
> 
> With gcc 4.0-20050728 on i686-pc-linux-gnu, compiling this with -O2
> appears to remove the assignment to *ptr. (I didn't prepare an example
> program, but it's verifiable with objdump.) Obviously, this code is
> non-portable, but still, I don't see why this can happen. Would anyone
> be kind enough to explain this to me? It works as expected with -O2
> -fno-strict-aliasing.

Well, I'd say it's a bug.  It works in 4.1.  The final assignment gets
removed by tree-ssa-dce.c because it looks like a useless store.  This
is because alias analysis thinks it knows what is going on, when it
clearly does not.

This patch happens to fix it in 4.0.  I doubt this is the right
approach, though.  It's a big hammer, which says that if you set a
pointer to the address of something, and you're not sure what that
thing is, then you have no idea what the pointer points to.

This code is completely different in 4.1.  In 4.1 the function
find_what_p_points_to is called, and it determines that it has no idea
what 'ptr' points to.

I think this should probably be fixed for 4.0.2, but I don't know if
this is the right patch at all.  It should at least be safe.

Ian

Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.71.2.2
diff -p -u -r2.71.2.2 tree-ssa-alias.c
--- tree-ssa-alias.c	26 Jul 2005 20:54:21 -0000	2.71.2.2
+++ tree-ssa-alias.c	2 Aug 2005 05:07:41 -0000
@@ -1901,6 +1901,8 @@ add_pointed_to_var (struct alias_info *a
       if (is_global_var (pt_var))
 	pi->pt_global_mem = 1;
     }
+  else
+    set_pt_anything (ptr);
 }
 
 

Re: More fun with aliasing - removing assignments?

[Diego Novillo]

On Mon, Aug 01, 2005 at 10:12:37PM -0700, Ian Lance Taylor wrote:
> Harald van D??k <truedfx@gentoo.org> writes:
> 
> > I finally managed to track down the problem I've been having to this
> > short code:
> > 
> > 	typedef struct {
> > 	    unsigned car;
> > 	    unsigned cdr;
> > 	} cons;
> > 
> > 	void nconc (unsigned x, unsigned y) {
> > 	    unsigned *ptr = &x;
> > 	    while(!(*ptr & 3))
> > 	        ptr = &((cons *)(*ptr))->cdr;
> > 	    *ptr = y;
> > 	}
> > 
> > With gcc 4.0-20050728 on i686-pc-linux-gnu, compiling this with -O2
> > appears to remove the assignment to *ptr. (I didn't prepare an example
> > program, but it's verifiable with objdump.) Obviously, this code is
> > non-portable, but still, I don't see why this can happen. Would anyone
> > be kind enough to explain this to me? It works as expected with -O2
> > -fno-strict-aliasing.
> 
> Well, I'd say it's a bug.  It works in 4.1.  The final assignment gets
> removed by tree-ssa-dce.c because it looks like a useless store.  This
> is because alias analysis thinks it knows what is going on, when it
> clearly does not.
> 
Are you sure?  I am not a language lawyer, but my understanding
is that you cannot legally make pointer 'p' point outside of
'x' using pointer arithmetic.  Since 'x' is a PARM_DECL passed by
value, the last assignment is a dead store.

In this case, 'ptr' should be marked as pointing anywhere.
However, alias analysis could also conclude that 'ptr' may not
point outside the current local frame.  So, the last store would
still be marked dead.

This distinction of different meanings for "points anywhere" will
be a feature of 4.2, most likely.

Having said that, I sent rth a 4.0 patch for a similar bug that
will "fix" this problem.  Richard, have you applied it yet?



	* tree-ssa-alias.c (add_pointed_to_var): If VALUE is of
	the form &(*PTR), take points-to information from PTR.

Index: tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.71.2.1
diff -d -u -p -r2.71.2.1 tree-ssa-alias.c
--- tree-ssa-alias.c	26 Feb 2005 16:24:27 -0000	2.71.2.1
+++ tree-ssa-alias.c	21 Jul 2005 20:13:44 -0000
@@ -1904,7 +1904,11 @@ add_pointed_to_var (struct alias_info *a
   if (REFERENCE_CLASS_P (pt_var))
     pt_var = get_base_address (pt_var);
 
-  if (pt_var && SSA_VAR_P (pt_var))
+  if (pt_var == NULL)
+    {
+      pi->pt_anything = 1;
+    }
+  else if (SSA_VAR_P (pt_var))
     {
       uid = var_ann (pt_var)->uid;
       bitmap_set_bit (ai->addresses_needed, uid);
@@ -1918,6 +1922,18 @@ add_pointed_to_var (struct alias_info *a
       if (is_global_var (pt_var))
 	pi->pt_global_mem = 1;
     }
+  else if (TREE_CODE (pt_var) == INDIRECT_REF
+           && TREE_CODE (TREE_OPERAND (pt_var, 0)) == SSA_NAME)
+    {
+      /* If VALUE is of the form &(*P_j), then PTR will have the same
+	 points-to information as P_j.  */
+      add_pointed_to_expr (ai, ptr, TREE_OPERAND (pt_var, 0));
+    }
+  else
+    {
+      /* Give up.  PTR points anywhere.  */
+      set_pt_anything (ptr);
+    }
 }

Re: More fun with aliasing - removing assignments?

[Richard Guenther]

On 8/2/05, Diego Novillo <dnovillo@redhat.com> wrote:
> On Mon, Aug 01, 2005 at 10:12:37PM -0700, Ian Lance Taylor wrote:
> > Harald van D??k <truedfx@gentoo.org> writes:
> >
> > > I finally managed to track down the problem I've been having to this
> > > short code:
> > >
> > >     typedef struct {
> > >         unsigned car;
> > >         unsigned cdr;
> > >     } cons;
> > >
> > >     void nconc (unsigned x, unsigned y) {
> > >         unsigned *ptr = &x;
> > >         while(!(*ptr & 3))
> > >             ptr = &((cons *)(*ptr))->cdr;
> > >         *ptr = y;
> > >     }
> > >
> > > With gcc 4.0-20050728 on i686-pc-linux-gnu, compiling this with -O2
> > > appears to remove the assignment to *ptr. (I didn't prepare an example
> > > program, but it's verifiable with objdump.) Obviously, this code is
> > > non-portable, but still, I don't see why this can happen. Would anyone
> > > be kind enough to explain this to me? It works as expected with -O2
> > > -fno-strict-aliasing.
> >
> > Well, I'd say it's a bug.  It works in 4.1.  The final assignment gets
> > removed by tree-ssa-dce.c because it looks like a useless store.  This
> > is because alias analysis thinks it knows what is going on, when it
> > clearly does not.
> >
> Are you sure?  I am not a language lawyer, but my understanding
> is that you cannot legally make pointer 'p' point outside of
> 'x' using pointer arithmetic.  Since 'x' is a PARM_DECL passed by
> value, the last assignment is a dead store.

p is not made to point 'outside' of x, but x is treated as a pointer, cast
to a struct pointer and then dereferenced.  Only if the loop entry condition
is false we end up storing into x (but only to x, not to memory beyond x),
and this store is of course dead.

Richard.

Re: More fun with aliasing - removing assignments?

[Richard Guenther]

On 8/2/05, Richard Guenther <richard.guenther@gmail.com> wrote:
> On 8/2/05, Diego Novillo <dnovillo@redhat.com> wrote:
> > On Mon, Aug 01, 2005 at 10:12:37PM -0700, Ian Lance Taylor wrote:
> > > Harald van D??k <truedfx@gentoo.org> writes:
> > >
> > > > I finally managed to track down the problem I've been having to this
> > > > short code:
> > > >
> > > >     typedef struct {
> > > >         unsigned car;
> > > >         unsigned cdr;
> > > >     } cons;
> > > >
> > > >     void nconc (unsigned x, unsigned y) {
> > > >         unsigned *ptr = &x;
> > > >         while(!(*ptr & 3))
> > > >             ptr = &((cons *)(*ptr))->cdr;
> > > >         *ptr = y;
> > > >     }
> > > >
> > > > With gcc 4.0-20050728 on i686-pc-linux-gnu, compiling this with -O2
> > > > appears to remove the assignment to *ptr. (I didn't prepare an example
> > > > program, but it's verifiable with objdump.) Obviously, this code is
> > > > non-portable, but still, I don't see why this can happen. Would anyone
> > > > be kind enough to explain this to me? It works as expected with -O2
> > > > -fno-strict-aliasing.
> > >
> > > Well, I'd say it's a bug.  It works in 4.1.  The final assignment gets
> > > removed by tree-ssa-dce.c because it looks like a useless store.  This
> > > is because alias analysis thinks it knows what is going on, when it
> > > clearly does not.
> > >
> > Are you sure?  I am not a language lawyer, but my understanding
> > is that you cannot legally make pointer 'p' point outside of
> > 'x' using pointer arithmetic.  Since 'x' is a PARM_DECL passed by
> > value, the last assignment is a dead store.
> 
> p is not made to point 'outside' of x, but x is treated as a pointer, cast
> to a struct pointer and then dereferenced.  Only if the loop entry condition
> is false we end up storing into x (but only to x, not to memory beyond x),
> and this store is of course dead.

Oh, and a workaround and slight correction would be to write

    void nconc (unsigned x, unsigned y) {
         unsigned *ptr = &((cons *)x)->cdr;
         while(!(*ptr & 3))
             ptr = &((cons *)(*ptr))->cdr;
         *ptr = y;
     }

which makes aliasing see that the store is not dead and in fact it never will
be to the argument area.

Richard.

Re: More fun with aliasing - removing assignments?

[Diego Novillo]

On Tue, Aug 02, 2005 at 02:56:50PM +0200, Richard Guenther wrote:
> Oh, and a workaround and slight correction would be to write
> 
>     void nconc (unsigned x, unsigned y) {
>          unsigned *ptr = &((cons *)x)->cdr;
>          while(!(*ptr & 3))
>              ptr = &((cons *)(*ptr))->cdr;
>          *ptr = y;
>      }
> 
No.  Same problem.  The aliaser would say "yes, ptr points
anywhere, but it cannot escape the local frame".  The final store
is dead just the same.

We only "get it right" because we do not distinguish between
different degrees of points-anywhere.

Re: More fun with aliasing - removing assignments?

[Daniel Jacobowitz]

On Tue, Aug 02, 2005 at 09:08:51AM -0400, Diego Novillo wrote:
> On Tue, Aug 02, 2005 at 02:56:50PM +0200, Richard Guenther wrote:
> > Oh, and a workaround and slight correction would be to write
> > 
> >     void nconc (unsigned x, unsigned y) {
> >          unsigned *ptr = &((cons *)x)->cdr;
> >          while(!(*ptr & 3))
> >              ptr = &((cons *)(*ptr))->cdr;
> >          *ptr = y;
> >      }
> > 
> No.  Same problem.  The aliaser would say "yes, ptr points
> anywhere, but it cannot escape the local frame".  The final store
> is dead just the same.
> 
> We only "get it right" because we do not distinguish between
> different degrees of points-anywhere.

Then the alias analyzer's broken.  This isn't pointer arithmetic in the
sense that you mean.  It would be if the line were:

             ptr = &((cons *)(ptr))->cdr;

which is equivalent to some offset plus ptr.  But there's an extra
dereference:

             ptr = &((cons *)(*ptr))->cdr;
                              ^

As far as I can tell, this code doesn't actually violate any of the
aliasing rules.  It just looks funny.

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Re: More fun with aliasing - removing assignments?

[Diego Novillo]

On Tue, Aug 02, 2005 at 09:39:56AM -0400, Daniel Jacobowitz wrote:

> Then the alias analyzer's broken.
>
Broken?  I'm saying that we currently get this right.  I don't
know what position are you arguing.

> This isn't pointer arithmetic in the sense that you mean.  It
> would be if the line were:
> 
>              ptr = &((cons *)(ptr))->cdr;
> 
Yes, I realize this now.  And that is not my point.  

> which is equivalent to some offset plus ptr.  But there's an extra
> dereference:
> 
>              ptr = &((cons *)(*ptr))->cdr;
>                               ^
> 
This code does builds an address location out of an arbitrary integer:

  unsigned int D.1142_8 = *ptr_1;
  struct cons *D.1143_9 = (struct cons *) D.1142_8;
  ptr_10 = &D.1143_9->cdr;

Does the language allow the creation of address locations out of
arbitrary integer values?  Is the dereference of such an
address a defined operation?  If so, then it's simply a matter of
recognizing this situation when computing points-anywhere
attributes.

Re: More fun with aliasing - removing assignments?

[Daniel Jacobowitz]

On Tue, Aug 02, 2005 at 09:57:39AM -0400, Diego Novillo wrote:
> On Tue, Aug 02, 2005 at 09:39:56AM -0400, Daniel Jacobowitz wrote:
> 
> > Then the alias analyzer's broken.
> >
> Broken?  I'm saying that we currently get this right.  I don't
> know what position are you arguing.

Sorry, my mistake.  I'd forgotten that Ian said we got this right in
4.1.

> This code does builds an address location out of an arbitrary integer:
> 
>   unsigned int D.1142_8 = *ptr_1;
>   struct cons *D.1143_9 = (struct cons *) D.1142_8;
>   ptr_10 = &D.1143_9->cdr;
> 
> Does the language allow the creation of address locations out of
> arbitrary integer values?  Is the dereference of such an
> address a defined operation?  If so, then it's simply a matter of
> recognizing this situation when computing points-anywhere
> attributes.

Yes, it does - well, it's implementation defined, but GCC has long
chosen the natural interpretation.  C99 6.3.2.3, paragraph 5.  This is
no different from that classic example, a pointer which escapes via
printf/scanf.

-- 
Daniel Jacobowitz
CodeSourcery, LLC

Re: More fun with aliasing - removing assignments?

[Diego Novillo]

On Tue, Aug 02, 2005 at 10:05:37AM -0400, Daniel Jacobowitz wrote:

> Yes, it does - well, it's implementation defined, but GCC has long
> chosen the natural interpretation.  C99 6.3.2.3, paragraph 5.  This is
> no different from that classic example, a pointer which escapes via
> printf/scanf.
> 
OK, thanks.  That settles it then.

Re: More fun with aliasing - removing assignments?

[Andreas Schwab]

Diego Novillo <dnovillo@redhat.com> writes:

> Does the language allow the creation of address locations out of
> arbitrary integer values?

Yes.

    6.3.2.3 Pointers

    5 An integer may be converted to any pointer type. [...]

>  Is the dereference of such an address a defined operation?

It is implemetation-defined.

    [...] Except as previously specified, the result is
    implementation-defined, might not be correctly aligned, might not
    point to an entity of the referenced type, and might be a trap
    representation.

Also, the integer may have been the result of casting a valid pointer, in
which case the operation is fully defined (assuming the integer is wide
enough).

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: More fun with aliasing - removing assignments?

[Richard Henderson]

On Tue, Aug 02, 2005 at 08:32:53AM -0400, Diego Novillo wrote:
> Having said that, I sent rth a 4.0 patch for a similar bug that
> will "fix" this problem.  Richard, have you applied it yet?

No, I forgot about it.


r~

Re: More fun with aliasing - removing assignments?

[Diego Novillo]

On Tue, Aug 02, 2005 at 10:05:53AM -0700, Richard Henderson wrote:
> On Tue, Aug 02, 2005 at 08:32:53AM -0400, Diego Novillo wrote:
> > Having said that, I sent rth a 4.0 patch for a similar bug that
> > will "fix" this problem.  Richard, have you applied it yet?
> 
> No, I forgot about it.
> 
That's fine.  Just applied it.

Re: More fun with aliasing - removing assignments?

[Ian Lance Taylor]

Diego Novillo <dnovillo@redhat.com> writes:

> On Tue, Aug 02, 2005 at 10:05:37AM -0400, Daniel Jacobowitz wrote:
> 
> > Yes, it does - well, it's implementation defined, but GCC has long
> > chosen the natural interpretation.  C99 6.3.2.3, paragraph 5.  This is
> > no different from that classic example, a pointer which escapes via
> > printf/scanf.
> > 
> OK, thanks.  That settles it then.

Just to close out this thread for the record, Andrew Pinski opened PR
23912 for this problem, and Diego checked in a patch for the 4.0
branch.  So all should be well in 4.0.2.

Ian

Re: More fun with aliasing - removing assignments?

[Daniel Berlin]

> > OK, thanks.  That settles it then.
> 
> Just to close out this thread for the record, Andrew Pinski opened PR
> 23912 for this problem, and Diego checked in a patch for the 4.0
> br
> n
> h.  So all should be well in 4.0.2.
> 

And the alias analyzer for 4.1 has tihs code, which is why it comes up
with the right answer:

  case NOP_EXPR:
          case CONVERT_EXPR:
          case NON_LVALUE_EXPR:
            {
              tree op = TREE_OPERAND (t, 0);

              /* Cast from non-pointer to pointers are bad news for us.
                 Anything else, we see through */
              if (!(POINTER_TYPE_P (TREE_TYPE (t))
                    && ! POINTER_TYPE_P (TREE_TYPE (op))))
                return get_constraint_for (op);

              /* FALLTHRU  */

    }
          default:
            {
              temp.type = ADDRESSOF;
              temp.var = anything_id;
              temp.offset = 0;
              return temp;
            }


We special case casts from integer constants like 0 (somewhere else) :)


I decided it wasn't worth trying to change years of practice of "let's
cast integers to pointers" by trying to sneak this in.
I'd rathre just watch as all their code explodes for other reasons, like
trying to cast pointers to unsigned int's on a 64 bit machine with LP64
models.