Bug 19786 - [4.0 Regression] Aliasing optimisation bug
[4.0 Regression] Aliasing optimisation bug
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: tree-optimization
4.0.0
: P2 normal
: 4.0.0
Assigned To: Alexandre Oliva
: alias, wrong-code
: 19782 19783 19784 19785 (view as bug list)
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2005-02-06 10:17 UTC by Sylvain Pion
Modified: 2005-02-22 02:32 UTC (History)
3 users (show)

See Also:
Host: i686-pc-linux-gnu
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-02-18 22:53:33


Attachments
Compile with -O2 and execute (551 bytes, text/plain)
2005-02-06 10:20 UTC, Sylvain Pion
Details
Preprocessed testcase (34.60 KB, application/octet-stream)
2005-02-16 19:47 UTC, Jakub Jelinek
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Sylvain Pion 2005-02-06 10:17:42 UTC
The attached C++ program triggers an assertion violation when compiled with -O2
(it should not).
The assertion is not triggered when adding -fno-strict-aliasing, or when removing
-O2.  It is also working when slight changes to the program are made (see comments
in the source).  It is the smallest version of the program which allowed me to
reproduce the bug, but I did not try to look into the <vector> header.

It might be an aliasing bug in <vector>, I don't know.
Note that g++ 3.4 works fine.
Comment 1 Sylvain Pion 2005-02-06 10:20:11 UTC
Created attachment 8135 [details]
Compile with -O2 and execute

It is not preprocessed, but uses <vector> (and <cassert> for illustration).
I can send a preprocessed version if needed.
Comment 2 Andrew Pinski 2005-02-06 15:29:08 UTC
Hmm, interesting.  On PPC I need -O3.  What is more interesting is that I could not see where the 
problems were in the tree dumps, therfor I am moving this into the rtl optimization component.  It 
might turn out that this is C++ front-end bug or a libstdc++ one.
Comment 3 Andrew Pinski 2005-02-06 18:34:47 UTC
*** Bug 19785 has been marked as a duplicate of this bug. ***
Comment 4 Andrew Pinski 2005-02-06 18:34:57 UTC
*** Bug 19784 has been marked as a duplicate of this bug. ***
Comment 5 Andrew Pinski 2005-02-06 18:34:58 UTC
*** Bug 19783 has been marked as a duplicate of this bug. ***
Comment 6 Andrew Pinski 2005-02-06 18:35:02 UTC
*** Bug 19782 has been marked as a duplicate of this bug. ***
Comment 7 Jakub Jelinek 2005-02-16 16:08:29 UTC
Looking into it.
Comment 8 Jakub Jelinek 2005-02-16 16:58:55 UTC
Actually, I do see problems in the tree dumps already.
Particularly the trees look ok before LIM and are broken afterwards.
loopinit->lim pseudo diff:

 <L97>:;
   D.16409_250 = &this_125->D.11755._M_impl._M_start;
   __i_251 = D.16409_250;
   D.16417_252 = *__i_251;
   *D.16417_252 = 1;
   this_109 = this_125;
   D.16452_108 = this_109->D.11755._M_impl._M_finish;
   SR.568_107 = D.16452_108;
   D.16460_97 = this_109->D.11755._M_impl._M_start;
   SR.571_93 = D.16460_97;
   if (SR.571_93 == SR.568_107) goto <L142>; else goto <L143>;
 <L143>:;
-<L110>:;
   D.16491_352 = &this_125->D.11755._M_impl._M_finish;
   __i_353 = D.16491_352;
   SR.574_354 = *__i_353;
   D.16499_365 = SR.574_354 - 4B;
   D.16061_377 = *D.16499_365;
+<L110>:;
   if (D.16061_377 != 0) goto <L144>; else goto <L117>;
 <L144>:;
   goto <bb 27> (<L136>);
 <L117>:;
   D.16432_339 = this_125->D.11755._M_impl._M_finish;
   D.16433_340 = D.16432_339 - 4B;
   this_125->D.11755._M_impl._M_finish = D.16433_340;
   this_599 = this_125;
   D.16452_598 = this_599->D.11755._M_impl._M_finish;
   SR.568_596 = D.16452_598;
   D.16460_588 = this_599->D.11755._M_impl._M_start;
   SR.571_587 = D.16460_588;
   if (SR.571_587 == SR.568_596) goto <L145>; else goto <L146>;
 <L146>:;
   goto <bb 20> (<L110>);
 <L145>:;
   goto <bb 27> (<L136>);
 ...
 <L142>:;
 <L136>:;
   return <retval>;
*(*&this->D.11755._M_impl._M_finish - 4B) is hoisted before the loop as
invariant, although it is not (each iteration of the loop decreases
this->D.11755._M_impl._M_finish by 4 bytes).
Comment 9 Andrew Pinski 2005-02-16 18:59:37 UTC
(In reply to comment #8)
> Actually, I do see problems in the tree dumps already.
> Particularly the trees look ok before LIM and are broken afterwards.
> loopinit->lim pseudo diff:

Can you look into the vops see why LIM thinks this is invariant?  (-fdump-tree-all-vops is a way to 
dump them).
Comment 10 Jakub Jelinek 2005-02-16 19:14:11 UTC
I'm still looking into it.
While with -fno-strict-aliasing the important part of the dump is:
  # BLOCK 20
  # PRED: 33 [100.0%]  (fallthru) 30 [100.0%]  (fallthru)
  # TMT.382D.16594_470 = PHI <TMT.382D.16594_1015(33), TMT.382D.16594_1010(30)>;
<L110>:;
  D.16463_352 = &thisD.16043_125->D.11755._M_implD.11232._M_finishD.11380;
  __iD.16464_353 = D.16463_352;
  #   VUSE <TMT.382D.16594_470>;
  SR.538D.16754_354 = *__iD.16464_353;
  D.16471_365 = SR.538D.16754_354 - 4B;
  #   VUSE <TMT.382D.16594_470>;
  D.16033_377 = *D.16471_365;
...
<L117>:;
  #   VUSE <TMT.382D.16594_470>;
  D.16404_339 = thisD.16043_125->D.11755._M_implD.11232._M_finishD.11380;
  D.16405_340 = D.16404_339 - 4B;
  #   TMT.382D.16594_1015 = V_MAY_DEF <TMT.382D.16594_470>;
  thisD.16043_125->D.11755._M_implD.11232._M_finishD.11380 = D.16405_340;
...
loop to 110, so TMT.382D.16594_470 = PHI <TMT.382D.16594_1015(33),
TMT.382D.16594_1010(30)> is in the loop, with -fstrict-aliasing we have:
  # BLOCK 19
  # PRED: 17 [100.0%]  (fallthru,exec) 28 [100.0%]  (fallthru)
  # TMT.412D.16624_469 = PHI <TMT.412D.16624_1050(17), TMT.412D.16624_1037(28)>;
  # TMT.411D.16623_22 = PHI <TMT.411D.16623_392(17), TMT.411D.16623_244(28)>;
  # D.16251_470 = PHI <D.16251_380(17), D.16251_242(28)>;
  # D.16077_471 = PHI <D.16077_384(17), D.16077_243(28)>;
<L97>:;
...
  # BLOCK 20
  # PRED: 33 [100.0%]  (fallthru) 30 [100.0%]  (fallthru)
  # TMT.411D.16623_2 = PHI <TMT.411D.16623_260(33), TMT.411D.16623_22(30)>;
<L110>:;
  D.16491_352 = &thisD.16071_125->D.11755._M_implD.11232._M_finishD.11380;
  __iD.16492_353 = D.16491_352;
  #   VUSE <TMT.412D.16624_469>;
  SR.574D.16790_354 = *__iD.16492_353;
  D.16499_365 = SR.574D.16790_354 - 4B;
  #   VUSE <D.16077_280>;
  #   VUSE <D.16251_279>;
  D.16061_377 = *D.16499_365;
...

but TMT.412D.16624_469 = PHI <TMT.412D.16624_1050(17), TMT.412D.16624_1037(28)>
is outside of the loop (loop starts at L110).
Comment 11 Jakub Jelinek 2005-02-16 19:47:58 UTC
Created attachment 8208 [details]
Preprocessed testcase
Comment 12 Jakub Jelinek 2005-02-16 20:04:26 UTC
I wonder if this has something to do with the dereference done through
int * const &.
This is the read from r->v._M_impl._M_finish in the loop.
            D.16053 = &r.52D.16052->vD.11757;
            {
              struct vector<int,std::allocator<int> >D.11215 * const thisD.16479;
              thisD.16479 = D.16053;
              {
                  struct vector<int,std::allocator<int> >D.11215 * const
thisD.16488;
                  thisD.16488 = thisD.16479;
                  {
                    intD.2 * * D.16491;
                    D.16491 =
&thisD.16488->D.11755._M_implD.11232._M_finishD.11380;
                    {
                      intD.2 * const & __iD.16492;
                      __iD.16492 = D.16491;
                      {
                        intD.2 * const D.16494;
                        D.16494 = *__iD.16492;
And is changed within the same loop:
      struct vector<int,std::allocator<int> >D.11215 * D.16053;
            D.16053 = &r.52D.16052->vD.11757;
              struct vector<int,std::allocator<int> >D.11215 * const thisD.16430;
              thisD.16430 = D.16053;
              {
                intD.2 * D.16432;
                intD.2 * D.16433;
                D.16432 = thisD.16430->D.11755._M_implD.11232._M_finishD.11380;
                D.16433 = D.16432 - 4B;
                thisD.16430->D.11755._M_implD.11232._M_finishD.11380 = D.16433;
                D.16432 = thisD.16430->D.11755._M_implD.11232._M_finishD.11380;

But the pointer is really const only in the block that it defines, not in the
whole function.
Comment 13 Alexandre Oliva 2005-02-18 17:45:20 UTC
I can't duplicate this with a tree updated some time earlier today.
Comment 14 Sylvain Pion 2005-02-18 20:48:22 UTC
(In reply to comment #13)
> I can't duplicate this with a tree updated some time earlier today.

It has also disappeared for me on Fedora Core 3.
But I can still reproduce it on Fedora Core 1,
with a g++ which I have just built (20050218).
Comment 15 Alexandre Oliva 2005-02-18 22:53:32 UTC
Very odd...  A rebuild after make clean was enough to trigger the problem. 
Maybe I haven't rebuilt all of libstdc++-v3 lately, but it's odd because I'd
thought all of the relevant libstdc++ code was brought in from headers.  I'll
look into it.

FWIW, it fails on x86_64-linux-gnu-gcc -m32, but not -m64.  Yes, I'd tested both
before :-)
Comment 16 Andrew Pinski 2005-02-21 15:15:52 UTC
This is an aliasing bug:
  #   VUSE <TMT.176_472>;
  D.11241_367 = this_127->D.8251._M_impl._M_finish;

But if we do:
  D.11300_379 = &this_127->D.8251._M_impl._M_finish;
  __i_380 = D.11300_379;
  #   VUSE <TMT.177_189>;
  SR.361_381 = *__i_380;

I think __i is const int * or something like that which causes the problem.
See how we have two different type tags.
Comment 17 Alexandre Oliva 2005-02-21 19:30:43 UTC
Subject: [PR tree-optimization/19786] fix alias grouping lossage

The problem here was that we added type tags to other tag's may-alias
lists without adding them to the corresponding bitmaps.  Later on,
when group_aliases performed an union of the bitmaps and discarded the
lists, we lost information about the aliases, which enabled LIM to
hoist a pointer access out of a loop because it appeared to be
invariant, since the VDEF supposed to modify it was missing.

Thanks to Jakub for having isolated the source of the problem, and
Diego for discussing tree-ssa alias analysis with me for a few hours
today.

Here's the patch I'm testing.  Ok to install if it bootstraps and
regtests successfully?

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

	PR tree-optimization/19786
	* tree-ssa-alias.c (compute_flow_insensitive_aliasing): Add one
	tag to another's may-alias bitmap when adding to the other's list.

Index: gcc/tree-ssa-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-alias.c,v
retrieving revision 2.69
diff -u -p -r2.69 tree-ssa-alias.c
--- gcc/tree-ssa-alias.c 17 Feb 2005 16:19:42 -0000 2.69
+++ gcc/tree-ssa-alias.c 21 Feb 2005 19:15:40 -0000
@@ -1116,6 +1116,7 @@ compute_flow_insensitive_aliasing (struc
 	      /* Since TAG2 does not have any aliases of its own, add
 		 TAG2 itself to the alias set of TAG1.  */
 	      add_may_alias (tag1, tag2);
+	      SET_BIT (may_aliases1, var_ann (tag2)->uid);
 	    }
 	}
     }
Index: gcc/testsuite/ChangeLog
from  Alexandre Oliva  <aoliva@redhat.com>

	PR tree-optimization/19786
	* g++.dg/tree-ssa/pr19786.C: New.

Index: gcc/testsuite/g++.dg/tree-ssa/pr19786.C
===================================================================
RCS file: gcc/testsuite/g++.dg/tree-ssa/pr19786.C
diff -N gcc/testsuite/g++.dg/tree-ssa/pr19786.C
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ gcc/testsuite/g++.dg/tree-ssa/pr19786.C 21 Feb 2005 19:15:54 -0000
@@ -0,0 +1,48 @@
+// { dg-do run }
+/* { dg-options "-O2" } */
+
+// We used to get alias grouping wrong on this one, hoisting accesses
+// to the vector's end out of the loop.
+
+#include <vector>
+#include <cassert>
+
+struct A
+{
+  double unused;      // If I remove it => it works.
+  std::vector<int> v;
+
+  A() : v(1) {}
+};
+
+inline // If not inline => it works.
+A g()
+{
+  A r;
+  r.v.resize(2);
+  r.v[0] = 1;
+
+  while (!r.v.empty() && r.v.back() == 0)
+    r.v.pop_back();
+
+  return r;
+}
+
+A f(const A &a)
+{
+  if (a.v.empty())  return a;
+  if (a.v.empty())  return a;
+
+  // A z = g(); return z;  // If I return like this => it works.
+  return g();
+}
+
+int main()
+{
+  A a;
+  A b;
+  A r = f(a);
+  assert(r.v.size() != 0);
+
+  return 0;
+}

-- 
Alexandre Oliva             http://www.ic.unicamp.br/~oliva/
Red Hat Compiler Engineer   aoliva@{redhat.com, gcc.gnu.org}
Free Software Evangelist  oliva@{lsd.ic.unicamp.br, gnu.org}
Comment 18 Diego Novillo 2005-02-21 19:33:30 UTC
Subject: Re: [PR tree-optimization/19786] fix alias grouping lossage

Alexandre Oliva wrote:

> 	PR tree-optimization/19786
> 	* tree-ssa-alias.c (compute_flow_insensitive_aliasing): Add one
> 	tag to another's may-alias bitmap when adding to the other's list.
> 
OK.  Thanks.


Diego.
Comment 19 CVS Commits 2005-02-22 02:27:42 UTC
Subject: Bug 19786

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	aoliva@gcc.gnu.org	2005-02-22 02:27:37

Modified files:
	gcc            : ChangeLog tree-ssa-alias.c 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/g++.dg/tree-ssa: pr19786.C 

Log message:
	gcc/ChangeLog:
	PR tree-optimization/19786
	* tree-ssa-alias.c (compute_flow_insensitive_aliasing): Add one
	tag to another's may-alias bitmap when adding to the other's list.
	gcc/testsuite/ChangeLog:
	PR tree-optimization/19786
	* g++.dg/tree-ssa/pr19786.C: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.7556&r2=2.7557
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-alias.c.diff?cvsroot=gcc&r1=2.69&r2=2.70
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5063&r2=1.5064
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/g++.dg/tree-ssa/pr19786.C.diff?cvsroot=gcc&r1=NONE&r2=1.1

Comment 20 Andrew Pinski 2005-02-22 02:32:21 UTC
Fixed.