Bug 10339 - [3.2/3.3/3.4 regression] [sparc,ppc,ppc64] Invalid optimization: replacing strncmp by memcmp
Summary: [3.2/3.3/3.4 regression] [sparc,ppc,ppc64] Invalid optimization: replacing st...
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: rtl-optimization (show other bugs)
Version: 3.2.2
: P3 normal
Target Milestone: 3.3.3
Assignee: Roger Sayle
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2003-04-07 16:16 UTC by ubell
Modified: 2004-01-17 04:22 UTC (History)
12 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments
test.c (97 bytes, application/octet-stream)
2003-05-21 15:17 UTC, ubell
Details

Note You need to log in before you can comment on or make changes to this bug.
Description ubell 2003-04-07 10:01:02 UTC
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
 > 
 
 

Comment 1 ubell 2003-04-07 12:05:31 UTC
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.)
 
 

Comment 2 ubell 2003-04-07 12:47:45 UTC
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.
 

Comment 3 ubell 2003-04-07 12:59:43 UTC
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--
 

Comment 4 Wolfgang Bangerth 2003-04-07 13:11:57 UTC
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/
 
 
Comment 5 Wolfgang Bangerth 2003-04-07 13:41:28 UTC
From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/10339: strncmp generates imPure code (fwd)
Date: Mon, 7 Apr 2003 13:41:28 -0500 (CDT)

 ---------- Forwarded message ----------
 Date: Mon, 07 Apr 2003 11:19:33 -0700
 From: Michael Ubell <ubell@mindspring.com>
 To: Wolfgang Bangerth <bangerth@ices.utexas.edu>
 Subject: Re: c/10339: strncmp generates imPure code
 
 I am sorry for the tersness.  I guess I have been looking at the generated code 
 too much so that it becomes obvious to me.  Yes that is exactly the problem.
 
 Note that in this case the compiler could actually figure out the
 maximum number of bytes, but in a more general case (the original problem
 we saw under Purify) it cannot.
 

Comment 6 Wolfgang Bangerth 2003-04-07 13:46:32 UTC
From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: optimization/10339
Date: Mon, 7 Apr 2003 13:46:32 -0500 (CDT)

 Actually, the use of memcmp didn't happen in 3.0, so this is a regression. 
 I don't have 3.3 or mainline installed on this platform, so can't say 
 anything about the problem in these branches.
 
 W.
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                                www: http://www.ices.utexas.edu/~bangerth/
 
 

Comment 7 Wolfgang Bangerth 2003-04-07 13:52:25 UTC
From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: ebotcazou@libertysurf.fr
Cc: gcc-gnats@gcc.gnu.org
Subject: c/10339
Date: Mon, 7 Apr 2003 13:52:25 -0500 (CDT)

 Hi Eric,
 as resident sparc optimization expert: would you mind taking a look at 
 10339, which is kind of a miscompilation on sparc? It would be nice if you 
 could confirm/reject whether this is a regression also in 3.3 and 
 mainline, since I don't have these branches on our sparc boxes. You can 
 see the problem by looking at the assembler output when using -O: it calls 
 memcmp with an argument 4 in %o2 (the "mov 4, %o2" happens _after_ the 
 call, but I think the instruction after the call is something like a delay 
 slot, so %o2 will be set at the time we get into memcmp).
 
 What exactly goes wrong should be understandable from the audit trail.
 
 Thanks
   Wolfgang
 
 PS: Again, my interest is just to know whether this is a regression also 
 on 3.3 and mainline, but if you should want to fix it then...
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                                www: http://www.ices.utexas.edu/~bangerth/
 
 

Comment 8 ubell 2003-04-07 13:53:09 UTC
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
 

Comment 9 ubell 2003-04-07 14:28:29 UTC
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.
 

Comment 10 ubell 2003-04-07 14:43:21 UTC
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?
 
 

Comment 11 Wolfgang Bangerth 2003-04-07 15:28:37 UTC
From: Wolfgang Bangerth <bangerth@ices.utexas.edu>
To: Eric Botcazou <ebotcazou@libertysurf.fr>
Cc: gcc-gnats@gcc.gnu.org
Subject: Re: c/10339
Date: Mon, 7 Apr 2003 15:28:37 -0500 (CDT)

 > > PS: Again, my interest is just to know whether this is a regression also
 > > on 3.3 and mainline, but if you should want to fix it then...
 > 
 > Does the same problem (if there is a problem) not happen on x86 too?
 
 The x86 backend doesn't seem to use memcmp in this case (maybe it does for 
 different values of string lengths, etc, but I haven't checked that).
 
 W.
 
 -------------------------------------------------------------------------
 Wolfgang Bangerth              email:            bangerth@ices.utexas.edu
                                www: http://www.ices.utexas.edu/~bangerth/
 
 

Comment 12 ubell 2003-04-07 16:16:00 UTC
generated code reads past end of allocated string

Release:
gcc (GCC) 3.2.2

Environment:
SunOS bear 5.8 Generic_108528-03 sun4u sparc SUNW,Ultra-60

How-To-Repeat:
gcc -O -S test.c
Comment 13 Wolfgang Bangerth 2003-04-07 16:48:28 UTC
State-Changed-From-To: open->feedback
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.
Comment 14 Wolfgang Bangerth 2003-04-07 18:42:46 UTC
State-Changed-From-To: feedback->analyzed
State-Changed-Why: Confirmed. See audit trail for more information
Comment 15 tprince 2003-04-07 19:45:04 UTC
From: "Timothy C Prince" <tprince@myrealbox.com>
To: falk.hueffner@student.uni-tuebingen.de
Cc: ubell@mindspring.com,
	bangerth@ices.utexas.edu,
	gcc-bugs@gcc.gnu.org,
	gcc-gnats@gcc.gnu.org
Subject: Re: Re: c/10339: strncmp generates imPure code
Date: Mon, 07 Apr 2003 19:45:04 +0000

 -----Original Message-----
 From: Falk Hueffner <falk.hueffner@student.uni-tuebingen.de>
 To: Michael Ubell <ubell@mindspring.com>
 Date: 07 Apr 2003 21:27:02 +0200
 Subject: Re: c/10339: strncmp generates imPure code
 
 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.
 >=20
 > 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.
 
 -- 
 =09Falk
 _________________________________________________
 I'm sure that gcc doesn't treat malloc specially to know that its pointers =
 are (almost) certainly more than byte-aligned. Nor would I expect it disc=
 riminate between a strncmp() which starts at the beginning of allocated m=
 emory and one which starts a variable number of bytes further along.  Sev=
 eral widespread implementations of gcc run on implementations where mallo=
 c() doesn't even provide a pointer sufficiently aligned for types wider t=
 han int.
 
 Tim Prince

Comment 16 falk.hueffner 2003-04-07 20:56:15 UTC
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

Comment 17 Eric Botcazou 2003-04-07 21:17:51 UTC
From: Eric Botcazou <ebotcazou@libertysurf.fr>
To: Wolfgang Bangerth <bangerth@ices.utexas.edu>
Cc: gcc-gnats@gcc.gnu.org
Subject: Re: c/10339
Date: Mon, 7 Apr 2003 21:17:51 +0200

 > You can see the problem by looking at the assembler output when using -O:
 > it calls memcmp with an argument 4 in %o2 (the "mov 4, %o2" happens _after_
 > the call, but I think the instruction after the call is something like a
 > delay slot, so %o2 will be set at the time we get into memcmp).
 
 Yep, the insn has been put in a delay slot.
 
 > PS: Again, my interest is just to know whether this is a regression also
 > on 3.3 and mainline, but if you should want to fix it then...
 
 Does the same problem (if there is a problem) not happen on x86 too?
 
 -- 
 Eric Botcazou

Comment 18 Andreas Schwab 2003-04-07 21:24:46 UTC
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."

Comment 19 falk.hueffner 2003-04-07 21:27:02 UTC
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

Comment 20 Hans-Peter Nilsson 2003-04-07 21:51:38 UTC
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
 

Comment 21 Andreas Schwab 2003-04-07 22:04:08 UTC
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."

Comment 22 Andreas Schwab 2003-04-07 23:23:16 UTC
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."

Comment 23 Andreas Schwab 2003-04-07 23:38:18 UTC
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."

Comment 24 Eric Botcazou 2003-04-08 08:40:04 UTC
From: Eric Botcazou <ebotcazou@libertysurf.fr>
To: Wolfgang Bangerth <bangerth@ices.utexas.edu>
Cc: gcc-gnats@gcc.gnu.org
Subject: Re: c/10339
Date: Tue, 8 Apr 2003 08:40:04 +0200

 > The x86 backend doesn't seem to use memcmp in this case (maybe it does for
 > different values of string lengths, etc, but I haven't checked that).
 
 Actually, it does the transformation strncmp->memcmp but the builtin memcmp 
 has the nice property to stop on the first NULL character ("repz cmpsb").
 
 Anyway, this is not a Sparc-specific problem.
 
 -- 
 Eric Botcazou

Comment 25 Alan Modra 2003-04-08 10:43:36 UTC
From: Alan Modra <amodra@bigpond.net.au>
To: bangerth@dealii.org, gcc-bugs@gcc.gnu.org, ubell@sleepycat.com,
 gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/10339: [sparc] Invalid optimization: replacing strncmp by memcmp
Date: Tue, 08 Apr 2003 10:43:36 +0930

 On Mon, Apr 07, 2003 at 06:42:47PM -0000, bangerth@dealii.org wrote:
 > Old Synopsis: strncmp generates imPure code
 > New Synopsis: [sparc] Invalid optimization: replacing strncmp by memcmp
 
 Also happens on powerpc-linux and powerpc64-linux.  Incidentally,
 I think Andreas' suggestion that memcmp is allowed to compare from
 the upper end of the arrays is not very likely to happen given
 memcmp's return value.  A more reasonable objection to the
 strncmp -> memcmp transformation is that a memcmp implementation
 might load multiple words into registers (say a cache-line worth),
 before comparing.
 
 -- 
 Alan Modra
 IBM OzLabs - Linux Technology Centre

Comment 26 Richard Henderson 2003-04-08 22:47:08 UTC
From: Richard Henderson <rth@redhat.com>
To: bangerth@dealii.org, gcc-bugs@gcc.gnu.org, ubell@sleepycat.com,
   gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/10339: [sparc] Invalid optimization: replacing strncmp by memcmp
Date: Tue, 8 Apr 2003 22:47:08 -0700

 On Tue, Apr 08, 2003 at 10:43:36AM +0930, Alan Modra wrote:
 > A more reasonable objection to the
 > strncmp -> memcmp transformation is that a memcmp implementation
 > might load multiple words into registers (say a cache-line worth),
 > before comparing.
 
 Agreed.
 
 
 r~
Comment 27 Eric Botcazou 2003-04-15 07:45:35 UTC
Responsible-Changed-From-To: unassigned->sayle
Responsible-Changed-Why: Author of the patch.
Comment 28 Roger Sayle 2003-04-23 13:09:39 UTC
From: sayle@gcc.gnu.org
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: optimization/10339
Date: 23 Apr 2003 13:09:39 -0000

 CVSROOT:	/cvs/gcc
 Module name:	gcc
 Changes by:	sayle@gcc.gnu.org	2003-04-23 13:09:39
 
 Modified files:
 	gcc            : ChangeLog builtins.c 
 
 Log message:
 	PR optimization/10339
 	* builtins.c (expand_builtin_strcmp): Try to emit cmpstrsi insn
 	directly instead of unsafely transforming call into a memcmp.
 	(expand_builtin_strncmp): Likewise.
 
 Patches:
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=1.17575&r2=1.17576
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtins.c.diff?cvsroot=gcc&r1=1.190&r2=1.191
 
Comment 29 Kaveh Ghazi 2003-04-29 14:00:03 UTC
State-Changed-From-To: analyzed->closed
State-Changed-Why: fixed
Comment 30 Jakub Jelinek 2003-05-20 13:02:12 UTC
From: jakub@gcc.gnu.org
To: gcc-gnats@gcc.gnu.org
Cc:  
Subject: optimization/10339
Date: 20 May 2003 13:02:12 -0000

 CVSROOT:	/cvs/gcc
 Module name:	gcc
 Branch: 	gcc-3_3-rhl-branch
 Changes by:	jakub@gcc.gnu.org	2003-05-20 13:02:12
 
 Modified files:
 	gcc            : ChangeLog builtin-types.def builtins.c 
 	                 builtins.def c-decl.c expr.c expr.h 
 
 Log message:
 	2003-05-08  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 	
 	* builtins.c (readonly_data_expr): New function.
 	(expand_builtin_memmove): Optimize any rodata source, not just
 	strings.
 	
 	2003-05-05  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 	
 	* builtins.c (expand_builtin_stpcpy): Only expand when the length
 	of the source string can be evaluated at compile-time.
 	
 	2003-05-05  Jakub Jelinek  <jakub@redhat.com>
 	
 	* builtins.c (expand_builtin_mempcpy): New function.
 	(expand_builtin_stpcpy): Optimize stpcpy whose return value is
 	ignored into strcpy no matter what arguments it has.
 	(expand_builtin) <case BUILT_IN_MEMPCPY>: Call
 	expand_builtin_mempcpy.
 	
 	2003-05-02  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 	
 	* builtins.c (expand_builtin_stpcpy): Copy `arglist' before
 	modifying it.
 	
 	2003-04-28  Jakub Jelinek  <jakub@redhat.com>
 	
 	* c-decl.c (finish_decl): When prototype with asmspec is found
 	for built-in, adjust built_in_decls as well as expr.c decls.
 	* expr.c (init_block_move_fn, init_block_clear_fn): New functions.
 	(emit_block_move_libcall_fn, clear_storage_libcall_fn): Use it.
 	* expr.h (init_block_move_fn, init_block_clear_fn): New prototypes.
 	
 	2003-04-28  Jakub Jelinek  <jakub@redhat.com>
 	
 	* builtins.def (BUILT_IN_BCOPY, BUILT_IN_MEMMOVE): New.
 	* builtin-types.def (BT_FN_VOID_CONST_PTR_PTR_SIZE): New.
 	* builtins.c (expand_builtin_memmove, expand_builtin_bcopy): New
 	functions.
 	(expand_builtin): Handle BUILT_IN_BCOPY and BUILT_IN_MEMMOVE.
 	
 	2003-04-23  Roger Sayle  <roger@eyesopen.com>
 	
 	PR optimization/10339
 	* builtins.c (expand_builtin_strcmp): Try to emit cmpstrsi insn
 	directly instead of unsafely transforming call into a memcmp.
 	(expand_builtin_strncmp): Likewise.
 	
 	2003-04-19  Roger Sayle  <roger@eyesopen.com>
 	
 	* builtins.c (expand_builtin):  Don't expand a pure or const
 	built-in function if the result will be ignored and none of
 	its arguments are volatile.
 	
 	2003-04-13  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 	
 	* builtins.c (expand_builtin_memcpy): Add `endp' argument, use it.
 	(expand_builtin_stpcpy): New.
 	(expand_builtin): Add BUILT_IN_MEMPCPY & BUILT_IN_STPCPY.
 	* builtins.def: Add mempcpy & stpcpy support.
 
 Patches:
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.16114.2.523.2.13&r2=1.16114.2.523.2.14
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtin-types.def.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.10.2.1&r2=1.10.2.1.4.1
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtins.c.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.165.2.4&r2=1.165.2.4.2.1
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtins.def.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.39.2.2&r2=1.39.2.2.2.1
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/c-decl.c.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.356.2.8&r2=1.356.2.8.2.1
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/expr.c.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.498.2.17&r2=1.498.2.17.2.1
 http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/expr.h.diff?cvsroot=gcc&only_with_tag=gcc-3_3-rhl-branch&r1=1.124.2.1&r2=1.124.2.1.4.1
Comment 31 CVS Commits 2003-07-10 19:41:22 UTC
Subject: Bug 10339

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-3_2-rhl8-branch
Changes by:	jakub@gcc.gnu.org	2003-07-10 19:41:20

Modified files:
	gcc            : ChangeLog builtins.c 

Log message:
	PR optimization/10339
	* builtins.c (expand_builtin_strcmp): Try to emit cmpstrsi insn
	directly instead of unsafely transforming call into a memcmp.
	(expand_builtin_strncmp): Likewise.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-3_2-rhl8-branch&r1=1.13152.2.657.2.27.2.134&r2=1.13152.2.657.2.27.2.135
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtins.c.diff?cvsroot=gcc&only_with_tag=gcc-3_2-rhl8-branch&r1=1.142.2.2.8.8&r2=1.142.2.2.8.9

Comment 32 CVS Commits 2003-11-06 04:47:42 UTC
Subject: Bug 10339

CVSROOT:	/cvs/gcc
Module name:	gcc
Branch: 	gcc-3_3-branch
Changes by:	sayle@gcc.gnu.org	2003-11-06 04:47:36

Modified files:
	gcc            : ChangeLog builtins.c 

Log message:
	Backport from mainline
	PR optimization/10339
	* builtins.c (expand_builtin_strcmp): Try to emit cmpstrsi insn
	directly instead of unsafely transforming call into a memcmp.
	(expand_builtin_strncmp): Likewise.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&only_with_tag=gcc-3_3-branch&r1=1.16114.2.797&r2=1.16114.2.798
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/builtins.c.diff?cvsroot=gcc&only_with_tag=gcc-3_3-branch&r1=1.165.2.7&r2=1.165.2.8

Comment 33 Andrew Pinski 2003-11-06 15:35:29 UTC
Fixed for 3.3.3 and 3.4.