loc_mentioned_in_p invokes undefined behavior

loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

[-- Attachment #1: Type: text/plain, Size: 617 bytes --]

I'd noticed that loc_mentioned_in_p() wouldn't find loc if it was
mentioned as one of the XVECEXPs of say a concatn, a parallel or
somesuch.  Debugging this, I realized this function would access every
fld of an RTX as if it was a pointer to an RTX itself.  This is wrong:
it makes room for false positives and it accesses as pointers fields
that might have been initialized as narrower or otherwise non-pointer
values, thus invoking undefined behavior.

This patch, that I've already tested in the vta branch, and I'm not
re-testing in mainline (x86_64-linux-gnu for both), should fix this
problem.  Ok to install?


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: gcc-rtlanal-loc-mentioned-in-vecexp.patch --]
[-- Type: text/x-patch, Size: 968 bytes --]

for  gcc/ChangeLog .vta?
from  Alexandre Oliva  <aoliva@redhat.com>

	* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.

Index: gcc/rtlanal.c
===================================================================
--- gcc/rtlanal.c.orig	2007-11-05 04:26:09.000000000 -0200
+++ gcc/rtlanal.c	2007-11-05 04:27:22.000000000 -0200
@@ -2989,16 +2989,15 @@ loc_mentioned_in_p (rtx *loc, const_rtx 
   fmt = GET_RTX_FORMAT (code);
   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     {
-      if (loc == &in->u.fld[i].rt_rtx)
-	return 1;
       if (fmt[i] == 'e')
 	{
-	  if (loc_mentioned_in_p (loc, XEXP (in, i)))
+	  if (loc == &XEXP (in, i) || loc_mentioned_in_p (loc, XEXP (in, i)))
 	    return 1;
 	}
       else if (fmt[i] == 'E')
 	for (j = XVECLEN (in, i) - 1; j >= 0; j--)
-	  if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
+	  if (loc == &XVECEXP (in, i, j)
+	      || loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
 	    return 1;
     }
   return 0;

[-- Attachment #3: Type: text/plain, Size: 249 bytes --]


-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Eric Botcazou]

> I'd noticed that loc_mentioned_in_p() wouldn't find loc if it was
> mentioned as one of the XVECEXPs of say a concatn, a parallel or
> somesuch.

Indeed, this defect seems to have been there since day #1.

> Debugging this, I realized this function would access every 
> fld of an RTX as if it was a pointer to an RTX itself.  This is wrong:
> it makes room for false positives and it accesses as pointers fields
> that might have been initialized as narrower or otherwise non-pointer
> values, thus invoking undefined behavior.

I don't think there is undefined behavior, the code only takes the address of 
these fields.  As for the semantic correctness, it boils down to what

/* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
int
loc_mentioned_in_p (rtx *loc, const_rtx in)

means exactly.  My interpretation is that the predicate was intended to be 
generic, in the sense that you woudn't need to overload it

rtx_loc_mentioned_in_p (rtx *loc, const_rtx in)
int_loc_mentioned_in_p (int *loc, const_rtx in)
rtvec_loc_mentioned_in_p (rtvec *loc, const_rtx in)

and so on.  If it holds true, then the predicate is correctly written.

AFAICS the code was not questioned when RTL checking was introduced:
  http://gcc.gnu.org/ml/gcc-patches/1999-08n/msg00893.html

> This patch, that I've already tested in the vta branch, and I'm not
> re-testing in mainline (x86_64-linux-gnu for both), should fix this
> problem.  Ok to install?

I don't think that end of Stage 3 is the right time to change the semantics of 
a predicate that is used by the reload pass.  I think that only what

	* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.

describes is acceptable at this point.

-- 
Eric Botcazou

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov  5, 2007, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:

>> Debugging this, I realized this function would access every 
>> fld of an RTX as if it was a pointer to an RTX itself.  This is wrong:
>> it makes room for false positives and it accesses as pointers fields
>> that might have been initialized as narrower or otherwise non-pointer
>> values, thus invoking undefined behavior.

> I don't think there is undefined behavior, the code only takes the address of 
> these fields.

Hmm...  Indeed, since these are fields of a union, taking the address
using a static type different from the dynamic type should work.
Thanks.

> /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
> int
> loc_mentioned_in_p (rtx *loc, const_rtx in)

> means exactly.  My interpretation is that the predicate was intended to be 
> generic, in the sense that you woudn't need to overload it

then it should have taken a void*.  But yes, that makes sense.

>> This patch, that I've already tested in the vta branch, and I'm not
>> re-testing in mainline (x86_64-linux-gnu for both), should fix this
>> problem.  Ok to install?

s/not/now/ sorry

> I don't think that end of Stage 3 is the right time to change the semantics of 
> a predicate that is used by the reload pass.  I think that only what

> 	* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.

> describes is acceptable at this point.

Sounds quite reasonable, under the light of your feedback.  I'll
retest that portion alone.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov  7, 2007, Alexandre Oliva <aoliva@redhat.com> wrote:

>> /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
>> int
>> loc_mentioned_in_p (rtx *loc, const_rtx in)

>> means exactly.  My interpretation is that the predicate was intended to be 
>> generic, in the sense that you woudn't need to overload it

> then it should have taken a void*.  But yes, that makes sense.

Except that all 3 uses thereof are really looking for an rtx.  So
moving the existing pointer compare could even be a (minor)
performance improvement, in addition to being a beyond-pedantic typing
issue.  And then, if we ever want to overload it, it's easy enough to
revert part of this and change the first parameter type to void*.

Given this additional investigation, I propose that the patch goes in
as I first posted it.  Ok?

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Eric Botcazou]

> Given this additional investigation, I propose that the patch goes in
> as I first posted it.

I conducted it too before answering your initial message.  There is no 
undefined behavior, the predicate was written ages ago for reload, let's
not take any gratuitous risk here.

-- 
Eric Botcazou

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov  8, 2007, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:

>> Given this additional investigation, I propose that the patch goes in
>> as I first posted it.

> I conducted it too before answering your initial message.  There is no 
> undefined behavior, the predicate was written ages ago for reload, let's
> not take any gratuitous risk here.

I don't see any risk whatsoever.  All 3 uses are evidently dealing
with rtx.  Do you know of something I don't?  I wouldn't mind turning
the predicate into a void*, if that would make you more comfortable
about risk management, but just changing the XVECEXP test while
leaving a known inconsistency behind seems like bad engineering
practice to me.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Eric Botcazou]

> I don't see any risk whatsoever.  All 3 uses are evidently dealing 
> with rtx.  Do you know of something I don't?

I've already exposed my position.

> I wouldn't mind turning the predicate into a void*, if that would make you
> more comfortable about risk management, but just changing the XVECEXP test
> while leaving a known inconsistency behind seems like bad engineering
> practice to me.

It's your interpretation, I don't see any inconsistency.

-- 
Eric Botcazou

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov  8, 2007, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:

>> I wouldn't mind turning the predicate into a void*, if that would make you
>> more comfortable about risk management, but just changing the XVECEXP test
>> while leaving a known inconsistency behind seems like bad engineering
>> practice to me.

> It's your interpretation, I don't see any inconsistency.

As in, a function that takes an rtx* but that (you say) could be
legitimately passed pointers to other types doesn't hold an
inconsistency?

Either it's polymorphic, and then a void* would be more appropriate,
or it's not, in which case the code is incorrect and performs
sub-optimally.

Which is it going to be?

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov  5, 2007, Alexandre Oliva <aoliva@redhat.com> wrote:

> This patch, that I've already tested in the vta branch, and I'm no[w]
> re-testing in mainline (x86_64-linux-gnu for both), should fix this
> problem.  Ok to install?

> for  gcc/ChangeLog .vta?
> from  Alexandre Oliva  <aoliva@redhat.com>

> 	* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.

:ADDPATCH rtl:

Ping?

http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00166.html

or maybe an answer to the question where the thread died last time
http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00465.html

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Eric Botcazou]

> Ping?
>
> http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00166.html

Not OK at this point.

:REVIEWMAIL:

-- 
Eric Botcazou

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Nov 26, 2007, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:

>> Ping?
>> 
>> http://gcc.gnu.org/ml/gcc-patches/2007-11/msg00166.html

> Not OK at this point.

Ok for 4.4?

:ADDPATCH rtl:

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}

Re: loc_mentioned_in_p invokes undefined behavior

[Eric Botcazou]

> Ok for 4.4?

Yes. :-)

:REVIEWMAIL:

-- 
Eric Botcazou

Re: loc_mentioned_in_p invokes undefined behavior

[Alexandre Oliva]

On Dec 15, 2007, Eric Botcazou <ebotcazou@libertysurf.fr> wrote:

>> Ok for 4.4?
> Yes. :-)

Installed, thanks.

for  gcc/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.

-- 
Alexandre Oliva         http://www.lsd.ic.unicamp.br/~oliva/
FSF Latin America Board Member         http://www.fsfla.org/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}