Re: c/10339: strncmp generates imPure code

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR c/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: bangerth@dealii.org,  gcc-bugs@gcc.gnu.org,  gcc-prs@gcc.gnu.org, 
 nobody@gcc.gnu.org,  ubell@sleepycat.com,  gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 10:01:02 -0700

 It generates a memcmp of 4 bytes when one of the arguments
 is 3 bytes long.
 
 bangerth@dealii.org wrote:
 > Synopsis: strncmp generates imPure code
 > 
 > State-Changed-From-To: open->feedback
 > State-Changed-By: bangerth
 > State-Changed-When: Mon Apr  7 16:48:28 2003
 > State-Changed-Why:
 >     Can you be more specific as to what the program gives for
 >     you, what you expect, and why? The return code for the
 >     program is 244 for me, independent of the flags I use.
 >     
 >     W.
 > 
 > http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10339
 > 
 
 

Re: c/10339: strncmp generates imPure code

[Hans-Peter Nilsson]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Hans-Peter Nilsson <hp@bitrange.com>
To: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
Cc: Wolfgang Bangerth <bangerth@ices.utexas.edu>, 
    Michael Ubell <ubell@mindspring.com>,  <gcc-bugs@gcc.gnu.org>, 
     <gcc-gnats@gcc.gnu.org>
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 7 Apr 2003 21:51:38 -0400 (EDT)

 On 7 Apr 2003, Falk Hueffner wrote:
 > This optimiziation would only be invalid if
 >
 > * it gives a different result,
 > * or the memory read straddles a page boundary and faults.
 
 Or
   * you use a tool such as valgrind to execute the code
     (a variant of the first item).
 
 (yeah, yeah, this wasn't about i*86...  Replace "valgrind"
 with "purify"  or similar.)
 
 brgds, H-P
 

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Andreas Schwab <schwab@suse.de>
Cc: Timothy C Prince <tprince@myrealbox.com>, 
 falk.hueffner@student.uni-tuebingen.de,  bangerth@ices.utexas.edu, 
 gcc-bugs@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 14:43:21 -0700

 I guess memcmp could do anything it wanted so long as it
 does not fetch more than N bytes.  Ok you win.  Or maybe I do?
 
 

Re: c/10339: strncmp generates imPure code

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1906 bytes --]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Andreas Schwab <schwab@suse.de>
To: Michael Ubell <ubell@mindspring.com>
Cc: Timothy C Prince <tprince@myrealbox.com>,
	falk.hueffner@student.uni-tuebingen.de, bangerth@ices.utexas.edu,
	gcc-bugs@gcc.gnu.org, gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 23:38:18 +0200

 Michael Ubell <ubell@mindspring.com> writes:
 
 |> Andreas Schwab wrote:
 |> > Michael Ubell <ubell@mindspring.com> writes:
 |> > |> Attached is a program that reads 831 unaligned unallocated
 |> > |> bytes.  I can't actually get it to segv on Solaris because
 |> > |> I don't know enough about their memory management, but
 |> > |> I cannot believe this is correct code.
 |> > Yes, you are right, I can reproduce that also on ia64-linux.  The
 |> > conversion to memcmp is really invalid here.
 |> > Andreas.
 |> > 
 |> 
 |> Now I get to argue the other side :-)  Was your string properly null
 |> terminated?  If not, then its not the compiler's fault.  I think
 |> memcmp is valid so long as the strings are well formed.  This will
 |> be true because C strings may not contain embedded nulls.
 
 memcmp does not operate on strings, but on arrays of characters.  That's
 an important difference, because memcmp is allowed, eg, to start comparing
 from the upper end of the arrays, independent of the actual contents of
 them; there is no null termination involved here.  On the other hand
 strncmp must not look behind the first nul character (at least
 conceptionally, the actual implementation may do so anyway if it can
 determine that it is safe).
 
 Andreas.
 
 -- 
 Andreas Schwab, SuSE Labs, schwab@suse.de
 SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
 Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
 "And now for something completely different."

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Andreas Schwab <schwab@suse.de>
Cc: Timothy C Prince <tprince@myrealbox.com>, 
 falk.hueffner@student.uni-tuebingen.de,  bangerth@ices.utexas.edu, 
 gcc-bugs@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 14:28:29 -0700

 Andreas Schwab wrote:
 > Michael Ubell <ubell@mindspring.com> writes:
 > 
 > |> Attached is a program that reads 831 unaligned unallocated
 > |> bytes.  I can't actually get it to segv on Solaris because
 > |> I don't know enough about their memory management, but
 > |> I cannot believe this is correct code.
 > 
 > Yes, you are right, I can reproduce that also on ia64-linux.  The
 > conversion to memcmp is really invalid here.
 > 
 > Andreas.
 > 
 
 Now I get to argue the other side :-)  Was your string properly null
 terminated?  If not, then its not the compiler's fault.  I think
 memcmp is valid so long as the strings are well formed.  This will
 be true because C strings may not contain embedded nulls.
 

Re: c/10339: strncmp generates imPure code

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1041 bytes --]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Andreas Schwab <schwab@suse.de>
To: Michael Ubell <ubell@mindspring.com>
Cc: Timothy C Prince <tprince@myrealbox.com>,
	falk.hueffner@student.uni-tuebingen.de, bangerth@ices.utexas.edu,
	gcc-bugs@gcc.gnu.org, gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 23:23:16 +0200

 Michael Ubell <ubell@mindspring.com> writes:
 
 |> Attached is a program that reads 831 unaligned unallocated
 |> bytes.  I can't actually get it to segv on Solaris because
 |> I don't know enough about their memory management, but
 |> I cannot believe this is correct code.
 
 Yes, you are right, I can reproduce that also on ia64-linux.  The
 conversion to memcmp is really invalid here.
 
 Andreas.
 
 -- 
 Andreas Schwab, SuSE Labs, schwab@suse.de
 SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
 Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
 "And now for something completely different."

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Andreas Schwab <schwab@suse.de>
Cc: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>, Wolfgang Bangerth
 <bangerth@ices.utexas.edu>,  gcc-bugs@gcc.gnu.org, 
 gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 13:53:09 -0700

 I think I see what is happening.  I guess computers are smarter ;-)
 
 Andreas Schwab wrote:
 > Michael Ubell <ubell@mindspring.com> writes:
 > 
 > |> Do you mean you want me to set up a case where it runs off the
 > |> end of memory?
 > 
 > Yes.
 
 Can't happen.
 
 > 
 > |> I think it is sufficient that it is reading memory
 > |> that is not allocated, no?
 > 
 > No, it is not.
 
 Well it would be but memcmp does not read the memory.
 
 > 
 > It is.  Memory returned by malloc is required to be correctly aligned for
 > any type.
 > 
 
 I'm still not clear what alignment has to do with it.
 
 The optimization takes advantage of the fact that a properly formatted
 string which is shorter than the constant string cannot compare passed its
 end because there must be a null byte there.
 
 Purify must have a different model of what memcmp does.  I'll send
 it to them.
 
 Thanks
 Mike
 

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Timothy C Prince <tprince@myrealbox.com>
Cc: falk.hueffner@student.uni-tuebingen.de,  bangerth@ices.utexas.edu, 
 gcc-bugs@gcc.gnu.org,  gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 12:59:43 -0700

 This is a multi-part message in MIME format.
 --------------050908010702010409010308
 Content-Type: text/plain; charset=KOI8-U; format=flowed
 Content-Transfer-Encoding: 7bit
 
 Attached is a program that reads 831 unaligned unallocated
 bytes.  I can't actually get it to segv on Solaris because
 I don't know enough about their memory management, but
 I cannot believe this is correct code.
 
 --------------050908010702010409010308
 Content-Type: text/plain;
  name="test.c"
 Content-Transfer-Encoding: 7bit
 Content-Disposition: inline;
  filename="test.c"
 
 char *foo() {
 	char *cp;
 	cp = sbrk(2);
 	*++cp = 0;
 printf("%x\n", cp);
 	return (cp);
 }
 main() {
 	char *name;
 
 	name = foo();
 
 	exit(strncmp("log.\
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 	xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx \
 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", name, 1000));
 	
 }
 
 
 --------------050908010702010409010308--
 

Re: c/10339: strncmp generates imPure code

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1353 bytes --]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Andreas Schwab <schwab@suse.de>
To: Michael Ubell <ubell@mindspring.com>
Cc: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>,
	Wolfgang Bangerth <bangerth@ices.utexas.edu>, gcc-bugs@gcc.gnu.org,
	gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 22:04:08 +0200

 Michael Ubell <ubell@mindspring.com> writes:
 
 |> Do you mean you want me to set up a case where it runs off the
 |> end of memory?
 
 Yes.
 
 |> I think it is sufficient that it is reading memory
 |> that is not allocated, no?
 
 No, it is not.
 
 |>  If you change the length of the string
 |> in the example you can see that it will read more unallocated
 |> memory.
 
 You haven't provided any evidence yet.  The provided test case is
 correctly translated for the given platform.
 
 |>  Do you have some reason why reading arbirary unallocated
 |> memory is acceptable?  I don't see how the alignment is an issue.
 
 It is.  Memory returned by malloc is required to be correctly aligned for
 any type.
 
 Andreas.
 
 -- 
 Andreas Schwab, SuSE Labs, schwab@suse.de
 SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
 Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
 "And now for something completely different."

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Andreas Schwab <schwab@suse.de>
Cc: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>, Wolfgang Bangerth
 <bangerth@ices.utexas.edu>,  gcc-bugs@gcc.gnu.org, 
 gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 12:47:45 -0700

 Do you mean you want me to set up a case where it runs off the
 end of memory?  I think it is sufficient that it is reading memory
 that is not allocated, no?  If you change the length of the string
 in the example you can see that it will read more unallocated
 memory.  Do you have some reason why reading arbirary unallocated
 memory is acceptable?  I don't see how the alignment is an issue.
 

Re: c/10339: strncmp generates imPure code

[Andreas Schwab]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1408 bytes --]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Andreas Schwab <schwab@suse.de>
To: Michael Ubell <ubell@mindspring.com>
Cc: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>,
	Wolfgang Bangerth <bangerth@ices.utexas.edu>, gcc-bugs@gcc.gnu.org,
	gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 21:24:46 +0200

 Michael Ubell <ubell@mindspring.com> writes:
 
 |> > I suspect the extra byte read is actually not relevant for the result,
 |> > and because of alignment, gcc knows the second problem cannot occur,
 |> > but I have neither a SPARC nor SPARC knowledge to test that.
 |> > 
 |> 
 |> Actually if you make the compare string longer you can get it
 |> to look at an arbitrary number of bytes passed the allocated part,
 |> so I think this could fault if you set it up right.  Also in
 |> the original problem, the first argument was not allocated locally
 |> so the compiler would have no idea how big or what its alignment
 |> was.  (In fact it was in a loop comparing strings from an array.)
 
 Could you please provide a test case that actually shows the problem?
 
 Andreas.
 
 -- 
 Andreas Schwab, SuSE Labs, schwab@suse.de
 SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
 Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
 "And now for something completely different."

Re: c/10339: strncmp generates imPure code

[Falk Hueffner]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: Michael Ubell <ubell@mindspring.com>
Cc: Wolfgang Bangerth <bangerth@ices.utexas.edu>, gcc-bugs@gcc.gnu.org,
   gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: 07 Apr 2003 21:27:02 +0200

 Michael Ubell <ubell@mindspring.com> writes:
 
 > > I suspect the extra byte read is actually not relevant for the result,
 > > and because of alignment, gcc knows the second problem cannot occur,
 > > but I have neither a SPARC nor SPARC knowledge to test that.
 > 
 > Actually if you make the compare string longer you can get it to
 > look at an arbitrary number of bytes passed the allocated part, so I
 > think this could fault if you set it up right.  Also in the original
 > problem, the first argument was not allocated locally so the
 > compiler would have no idea how big or what its alignment was.  (In
 > fact it was in a loop comparing strings from an array.)
 
 Could you perhaps provide such an example? For your original example,
 gcc knows that malloc returns only aligned pointers.
 
 -- 
 	Falk

Re: c/10339: strncmp generates imPure code

[Falk Hueffner]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
To: Wolfgang Bangerth <bangerth@ices.utexas.edu>
Cc: Michael Ubell <ubell@mindspring.com>, gcc-bugs@gcc.gnu.org,
   <gcc-gnats@gcc.gnu.org>
Subject: Re: c/10339: strncmp generates imPure code
Date: 07 Apr 2003 20:56:15 +0200

 Wolfgang Bangerth <bangerth@ices.utexas.edu> writes:
 
 > > It generates a memcmp of 4 bytes when one of the arguments
 > > is 3 bytes long.
 > 
 > You're a little terse in your descriptions of the problem :-]
 > 
 > I think I understand now what you mean: with -O, gcc optimizes the strncmp 
 > away and replaces it by a call to memcmp. However, it doesn't take into 
 > account that strncmp compares _at most_ n  characters, but that the actual 
 > number may be less than n if one of the two strings is shorter. memcmp on 
 > the other hand always does n bytes.
 
 Well, just like in real life, we can do anything we like as long as
 nobody notices. This optimiziation would only be invalid if
 
 * it gives a different result,
 * or the memory read straddles a page boundary and faults.
 
 I suspect the extra byte read is actually not relevant for the result,
 and because of alignment, gcc knows the second problem cannot occur,
 but I have neither a SPARC nor SPARC knowledge to test that.
 
 -- 
 	Falk

Re: c/10339: strncmp generates imPure code

[Michael Ubell]

The following reply was made to PR optimization/10339; it has been noted by GNATS.

From: Michael Ubell <ubell@mindspring.com>
To: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
Cc: Wolfgang Bangerth <bangerth@ices.utexas.edu>,  gcc-bugs@gcc.gnu.org, 
 gcc-gnats@gcc.gnu.org
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 12:05:31 -0700

 > I suspect the extra byte read is actually not relevant for the result,
 > and because of alignment, gcc knows the second problem cannot occur,
 > but I have neither a SPARC nor SPARC knowledge to test that.
 > 
 
 Actually if you make the compare string longer you can get it
 to look at an arbitrary number of bytes passed the allocated part,
 so I think this could fault if you set it up right.  Also in
 the original problem, the first argument was not allocated locally
 so the compiler would have no idea how big or what its alignment
 was.  (In fact it was in a loop comparing strings from an array.)
 
 

Re: c/10339: strncmp generates imPure code

[Wolfgang Bangerth]

The following reply was made to PR c/10339; it has been noted by GNATS.

From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: Michael Ubell <ubell@mindspring.com>
Cc: gcc-bugs@gcc.gnu.org, <gcc-gnats@gcc.gnu.org>
Subject: Re: c/10339: strncmp generates imPure code
Date: Mon, 7 Apr 2003 13:11:57 -0500 (CDT)

 > It generates a memcmp of 4 bytes when one of the arguments
 > is 3 bytes long.
 
 You're a little terse in your descriptions of the problem :-]
 
 I think I understand now what you mean: with -O, gcc optimizes the strncmp 
 away and replaces it by a call to memcmp. However, it doesn't take into 
 account that strncmp compares _at most_ n  characters, but that the actual 
 number may be less than n if one of the two strings is shorter. memcmp on 
 the other hand always does n bytes.
 
 Is that what you meant?
 
 Thanks
   Wolfgang
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                                www: http://www.ices.utexas.edu/~bangerth/
 
 

Re: c/10339: strncmp generates imPure code

[bangerth]

Synopsis: strncmp generates imPure code

State-Changed-From-To: open->feedback
State-Changed-By: bangerth
State-Changed-When: Mon Apr  7 16:48:28 2003
State-Changed-Why:
    Can you be more specific as to what the program gives for
    you, what you expect, and why? The return code for the
    program is 244 for me, independent of the flags I use.
    
    W.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10339

c/10339: strncmp generates imPure code

[ubell]

>Number:         10339
>Category:       c
>Synopsis:       strncmp generates imPure code
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon Apr 07 16:16:00 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Michael Ubell
>Release:        gcc (GCC) 3.2.2
>Organization:
>Environment:
SunOS bear 5.8 Generic_108528-03 sun4u sparc SUNW,Ultra-60
>Description:
generated code reads past end of allocated string
>How-To-Repeat:
gcc -O -S test.c
>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: application/octet-stream; name="test.c"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="test.c"

bWFpbigpIHsKCWNoYXIgKm5hbWUxLCAqbmFtZTsKCgluYW1lID0gbWFsbG9jKDMpOwoKCXN0cmNw
eShuYW1lLCAieHgiKTsKCglleGl0KHN0cm5jbXAoImxvZy4iLCBuYW1lLCA0KSk7CgkKfQo=