[Bug tree-optimization/19786] New: Aliasing optimisation bug

[Bug tree-optimization/19786] New: Aliasing optimisation bug

[sylvain.pion@sophia.inria.fr]

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.

-- 
           Summary: Aliasing optimisation bug
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Severity: critical
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: sylvain dot pion at sophia dot inria dot fr
                CC: gcc-bugs at gcc dot gnu dot org
  GCC host triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] Aliasing optimisation bug

[sylvain.pion@sophia.inria.fr]

------- Additional Comments From sylvain dot pion at sophia dot inria dot fr  2005-02-06 10:20 -------
Created an attachment (id=8135)
 --> ( http://gcc.gnu.org/bugzilla/attachment.cgi?id=8135&action=view )
Compile with -O2 and execute

It is not preprocessed, but uses <vector> (and <cassert> for illustration).
I can send a preprocessed version if needed.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] Aliasing optimisation bug

[pinskia@gcc.gnu.org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #8135|application/octet-stream    |text/plain
          mime type|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia@gcc.gnu.org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 15:29 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|critical                    |normal
             Status|UNCONFIRMED                 |NEW
          Component|tree-optimization           |rtl-optimization
     Ever Confirmed|                            |1
           Keywords|                            |wrong-code
   Last reconfirmed|0000-00-00 00:00:00         |2005-02-06 15:29:08
               date|                            |
            Summary|Aliasing optimisation bug   |[4.0 Regression] Aliasing
                   |                            |optimisation bug
   Target Milestone|---                         |4.0.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 18:35 -------
*** Bug 19782 has been marked as a duplicate of this bug. ***

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 18:34 -------
*** Bug 19785 has been marked as a duplicate of this bug. ***

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 18:34 -------
*** Bug 19784 has been marked as a duplicate of this bug. ***

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 18:34 -------
*** Bug 19784 has been marked as a duplicate of this bug. ***
------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-06 18:34 -------
*** Bug 19783 has been marked as a duplicate of this bug. ***

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-16 16:08 -------
Looking into it.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |jakub at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-02-06 15:29:08         |2005-02-16 16:08:29
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug rtl-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-16 16:58 -------
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).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-16 18:59 -------
(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).

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |tree-optimization


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-16 19:14 -------
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).

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[jakub at gcc dot gnu dot org]

------- Additional Comments From jakub at gcc dot gnu dot org  2005-02-16 20:04 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at redhat dot com
         AssignedTo|jakub at gcc dot gnu dot org|unassigned at gcc dot gnu
                   |                            |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[aoliva at gcc dot gnu dot org]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-02-18 17:45 -------
I can't duplicate this with a tree updated some time earlier today.

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[sylvain dot pion at sophia dot inria dot fr]

------- Additional Comments From sylvain dot pion at sophia dot inria dot fr  2005-02-18 20:48 -------
(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).

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[aoliva at gcc dot gnu dot org]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-02-18 22:53 -------
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 :-)

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |aoliva at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-02-16 16:08:29         |2005-02-18 22:53:33
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-21 15:15 -------
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.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org
           Keywords|                            |alias


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[aoliva at redhat dot com]

------- Additional Comments From aoliva at gcc dot gnu dot org  2005-02-21 19:30 -------
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}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[dnovillo at redhat dot com]

------- Additional Comments From dnovillo at redhat dot com  2005-02-21 19:33 -------
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.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-02-22 02:27 -------
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



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786

[Bug tree-optimization/19786] [4.0 Regression] Aliasing optimisation bug

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-22 02:32 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19786