Bug 22167 - [3.4/4.0/4.1 regression] Strange optimization bug when using -Os
Summary: [3.4/4.0/4.1 regression] Strange optimization bug when using -Os
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: rtl-optimization (show other bugs)
Version: 3.4.4
: P2 normal
Target Milestone: 3.4.5
Assignee: rsandifo@gcc.gnu.org
URL:
Keywords: wrong-code
Depends on:
Blocks:
 
Reported: 2005-06-23 23:37 UTC by Daniel Howell
Modified: 2005-07-21 06:58 UTC (History)
3 users (show)

See Also:
Host:
Target: powerpc-linux
Build:
Known to work: 3.2.3
Known to fail: 3.3 3.4.4 4.1.0 4.0.0
Last reconfirmed: 2005-07-14 13:49:01


Attachments
Short test file which demonstrates optimization failure (346 bytes, text/plain)
2005-06-23 23:48 UTC, Daniel Howell
Details
Candidate patch (392 bytes, patch)
2005-07-14 13:50 UTC, rsandifo@gcc.gnu.org
Details | Diff
Reduced testcase (358 bytes, text/plain)
2005-07-14 17:53 UTC, rsandifo@gcc.gnu.org
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Daniel Howell 2005-06-23 23:37:22 UTC
The attached file osbugs.cpp will print a "BUG!!!!" message when compiled with 
the -Os switch with g++ 3.4.4 on powerpc.  This is due to the optimizer 
generating incorrect code, by apparently incorrectly determining that S::p is 
not being changed by the method S::init() before S::~S() is called.

I found this bug originally in the 3.3.5 version of the compiler, and it was 
causing a strange crash down in the basic_string code, but I've been able 
strip the code down to what I think is about the minimum needed to reproduce 
the optimization failure.  No pre-processor directives are in the attached 
source file.

The bug has been reproduced in mips-linux 3.3.5, and i386-linux 3.3.2 and 
3.3.5.  The bug does not appear in i386-linux 3.4.4.

Sample output, showing that this bug occurs across several different 
distributions of GCC:

powerpc, 3.4.4:

$ g++-3.4 --version | head -n1
g++-3.4 (GCC) 3.4.4 20050314 (prerelease) (Debian 3.4.3-13)
$ g++-3.4 -O2 osbugs.cpp -o osbugs
$ ./osbugs
p is 0x10011050 and p2 is 0x10011050 (should be non-zero and equal)
$ g++-3.4 -Os osbugs.cpp -o osbugs
$ ./osbugs
p is 0x0 and p2 is 0x0 (should be non-zero and equal)
BUG!!!! p is 0x10011050 and p2 is 0x0

i386, 3.3.5:

$ g++ --version | head -n1
g++ (GCC) 3.3.5 (Debian 1:3.3.5-13)
$ g++ -O2 osbugs.cpp -o osbugs
$ ./osbugs
p is 0x804a008 and p2 is 0x804a008 (should be non-zero and equal)
$ g++ -Os osbugs.cpp -o osbugs
$ ./osbugs
p is 0x0 and p2 is 0x0 (should be non-zero and equal)
BUG!!!! p is 0x804a008 and p2 is 0x0

i386, 3.3.2:

$ g++ --version | head -n1
g++ (GCC) 3.3.2 (Red Hat Linux 3.3.2-1)
$ g++ -O2 osbugs.cpp -o osbugs
$ ./osbugs
p is 0x8f0f008 and p2 is 0x8f0f008 (should be non-zero and equal)
$ g++ -Os osbugs.cpp -o osbugs
$ ./osbugs
p is 0x0 and p2 is 0x0 (should be non-zero and equal)
BUG!!!! p is 0x8497008 and p2 is 0x0

mips, 3.3.5:

$ mips-linux-g++ --version | head -n1
mips-linux-g++ (GCC) 3.3.5
$ mips-linux-g++ -O2 osbugs.cpp -o osbugs

[mipsbox]$ ./osbugs
p is 0x10000240 and p2 is 0x10000240 (should be non-zero and equal)

$ mips-linux-g++ -Os osbugs.cpp -o osbugs

[mipsbox]$ ./osbugs
p is 0x10000240 and p2 is 0x0 (should be non-zero and equal)
BUG!!!! p is 0x10000240 and p2 is 0x0
Comment 1 Daniel Howell 2005-06-23 23:48:19 UTC
Created attachment 9138 [details]
Short test file which demonstrates optimization failure

This is pretty much what was left of basic_string.h after I removed all the
code which was not needed to cause the bug to happen.  For the curious, S was
derived from the basic_string template, A was derived from the allocator
object, and p used to be the _M_rep pointer to the basic_string::_Rep
structure.  S::init was once basic_string::append.

The function do_nothing was once the allocator's dispose method, but as you can
see it now truly should do nothing.  But it doesn't quite do nothing, it causes
the optimizer to fail when optimizing for size.  The seemingly pointless
static_cast<A> also is needed to cause the bug.  Inlining either S::init or
do_nothing will also make the bug magically disappear.
Comment 2 Volker Reichelt 2005-06-29 14:40:53 UTC
I can confirm the bug on mips-sgi-irix6.5 (GCC 3.3.x, 3.4.x).
I can't test whether the bug is also present on gcc 4.0.0 and later.

The same bug also appears on i686-pc-linux-gnu, but only with GCC 3.3.x.
Comment 3 Andrew Pinski 2005-06-29 15:14:54 UTC
It works for me on powerpc-darwin with 4.0.0, 4.1.0 but does not work with 3.3.3 and 3.4.0, so 
removing the 4.0, 4.1 regression markers.
Comment 4 rsandifo@gcc.gnu.org 2005-07-14 13:49:00 UTC
I think this is a bug in gcse.c:hoist_code.  It appears to date back
to when the code was first added.

The function is supposed to be doing the following:

  for each block BB
    for each expr E
      HOISTABLE := 0
A:    if (E is very busy at the end of BB
          && E is transparent at the end of BB)
        for each block BB' that is dominated by BB
          if (BB' uses E
              && a computation of E at the end of BB would reach that use)
            HOISTABLE := HOISTABLE + 1
      HOIST_EXPRS[E] := HOISTABLE > 1
    if there exists an E such that HOIST_EXPRS[E] > 0
      for each expr E
B:      if HOIST_EXPRS[E]
	  for each block BB' that is dominated by BB
	    if (BB' uses E
	        && a computation of E at the end of BB would reach that use)
	      replace the use with the reaching reg

Unfortunately, the implementation of condition B is checking the wrong
bitmap (hoist_vbeout instead of hoist_exprs).  In other words, the code
is effectively doing:

B:      if E is very busy at the end of BB

Thus hoist_code() would do nothing for a function that has no candidate
expressions with two or more suitable uses.  However, if a function
_does_ have such an expression, hoist_code() would hoist all candidate
expressions, even if they have only one use.  And it would effectively
drop the all-important "E is transparent at the end of BB" condition
when doing this.

So what happens on MIPS (and presumably powerpc) is this: we have two
candidate expressions that are of interest:

  1. (mem s.p)
  2. (high "p is 0x%x and p2 ...")

Both expressions are very busy on the output from block 0, which ends
with the call to S::init().  And both expressions have more than one
suitable use.  However, expression 1 is not entered in HOIST_EXPRS
because it is not transparent at the end of block 0.  We'd have to
insert the load _before_ the call to S::init(), and that would change
its value.  Expression 2 _is_ transparent at the end of block 0 and
so HOIST_EXPRS[2] is correctly set to true.

So we have one expression that we want to hoist -- expression 2 -- and
we therefore enter the second loop.  This then ignores the fact that
expression 1 is not transparent at the end of block 0 and hoists it
anyway.

Although I haven't checked, I think the reason this doesn't show up
on i686 is because there's no equivalent of (high ...) that would
cause the second loop to be executed.

Richard
Comment 5 rsandifo@gcc.gnu.org 2005-07-14 13:50:30 UTC
Created attachment 9271 [details]
Candidate patch

Here's the patch I'm testing.  There are a few people on the cc: line
of this bug, so please let me know if it solves the problem on your
favourite target.
Comment 6 rsandifo@gcc.gnu.org 2005-07-14 17:53:30 UTC
Created attachment 9275 [details]
Reduced testcase
Comment 7 rsandifo@gcc.gnu.org 2005-07-14 17:55:16 UTC
The reduced testcase that I've just attached fails for 4.1 as
well as 3.4 on mips64-elf.  I haven't yet tried 4.0.
Comment 8 Andrew Pinski 2005-07-14 18:57:02 UTC
The reduced testcase also fails on ppc-darwin with 4.0.0.
Comment 9 Daniel Howell 2005-07-15 00:04:30 UTC
(In reply to comment #5)
> Created an attachment (id=9271)
> Candidate patch
> Here's the patch I'm testing.  There are a few people on the cc: line
> of this bug, so please let me know if it solves the problem on your
> favourite target.

I applied this patch to the 3.3.5 compiler in my MIPS cross-compiler toolchain 
and I verified that it fixes the osbugs.cpp testcase.  Haven't had a chance to 
see if this fixes the full app that was failing, but I'm pretty confident.  
Thank you!
Comment 13 rsandifo@gcc.gnu.org 2005-07-21 06:58:03 UTC
Patch committed.