[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.2                       |4.5.3

--- Comment #35 from Richard Guenther <rguenth at gcc dot gnu.org> 2010-12-16 13:02:44 UTC ---
GCC 4.5.2 is being released, adjusting target milestone.

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |
      Known to fail|                            |

--- Comment #36 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-01-18 14:43:50 UTC ---
Trunk is now very fast and segfaults the testcase ;)

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |INVALID

--- Comment #37 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-01-18 15:19:05 UTC ---
Ok, with -O1 -fno-tree-loop-im as basic flags -fno-tree-dse makes the
difference for the segfault when we remove

 static void
boost::intrusive::avltree_algorithms<NodeTraits>::rebalance_after_i
nsertion(boost::intrusive::avltree_algorithms<NodeTraits>::node_ptr,
boost::intr
usive::avltree_algorithms<NodeTraits>::node_ptr) [with NodeTraits =
boost::intru
sive::avltree_node_traits<boost::interprocess::offset_ptr<void>, false>,
boost::
intrusive::avltree_algorithms<NodeTraits>::node_ptr =
boost::interprocess::offse
t_ptr<boost::intrusive::avltree_node<boost::interprocess::offset_ptr<void> > >] 
(struct node_ptr & restrict header, struct node_ptr & restrict x)
 {
   long int D.64530;
@@ -8290,7 +7992,6 @@
   p.19_2156 = (long int) D.64522_2154;
   D.64529_2157 = (long int) D.64513_2150;
   D.64530_2158 = p.19_2156 - D.64529_2157;
-  MEM[(struct offset_ptr *)D.64515_2149].m_offset = D.64530_2158;
   if (D.64530_2158 == 1)
     goto <bb 746>;
   else

this pointer is believed to point to

D.64515_2149, points-to NULL, points-to vars: { D.57715 CAST_RESTRICT.445 }
(includes restrict tags)

computed from

<bb 742>:
  n_2143 = (struct node_ptr & restrict) &D.57715;
  p_2144 = (struct node_ptr & restrict) &D.57716;
  D.64517_2145 = D.57715.m_offset;
  D.64516_2147 = (long unsigned int) D.64517_2145;
  D.64515_2148 = n_2143 + D.64516_2147;

<bb 743>:
  # D.64515_2149 = PHI <0B(739), D.64515_2148(742)>

which confirms the points-to calculation.

But the compressed AVL tree thinks it can represent a pointer to
a global object by using the address of a local variable and
the difference between the address of the global and the local.
Which it of course cannot according to the C++ standard.
D.57715.m_offset is set by

<bb 740>:
  p.19_2139 = (long int) D.64504_2137;
  D.64508_2140 = (long int) &D.57715;
  D.64509_2141 = p.19_2139 - D.64508_2140;
  D.57715.m_offset = D.64509_2141;
  if (D.64509_2141 == 1)
    goto <bb 741>;
  else
    goto <bb 742>;

and we have

<bb 737>:
boost::interprocess::offset_ptr<boost::intrusive::avltree_node<boost::interprocess::offset_ptr<void>
> >::offset_ptr (&D.57716, &root);
  D.64502_2134 = MEM[(const struct offset_ptr *)header_2(D)].m_offset;
  if (D.64502_2134 != 1)
    goto <bb 738>;
  else
    goto <bb 739>;

<bb 738>:
  D.64503_2136 = (long unsigned int) D.64502_2134;
  D.64504_2137 = header_2(D) + D.64503_2136;

where header_2(D) is a parameter, struct node_ptr & restrict header.  So
Boost AVL expects us to compute whatever header points-to as points-to
set of D.64515_2149 with no backing from the standard that we are required
to do that.

If we were able to "optimize" the code back to base the address on
header it would of course work (by luck).

For

extern void abort (void);
struct X { unsigned long offset; };
void foo (char *p)
{
  struct X a;
  char tmp, *q;
  a.offset = p - &tmp;
  if (a.offset == 1)
    abort ();
  q = &tmp + a.offset;
  *q = 0;
}

already early DCE kills the store (the above is what compressed AVL does).

Thus, this testcase is invalid.  Resulting performance is irrelevant.

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[igaztanaga at gmail dot com]

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

--- Comment #38 from Ion Gaztañaga <igaztanaga at gmail dot com> 2011-01-18 19:15:22 UTC ---
Thanks Richard for the detailed report. The fact is that the next standard is
trying to support relative pointers for container implementations (much like
Boost.Interprocess does), to be able to place containers in shared memory. In
those cases the relative pointers stores the difference between "this" and the
pointee, which is what boost::interprocess::offset_ptr does.

It is certainly outside the standard right now and the standard won't include
such "relative pointer" class, but it will require to container implementations
to support them as allocator::pointer types. It would be important to find a
way to use smart pointers, maybe with some existing annotation/attribute to
avoid optimizing away that relative addressing, so that there is always away to
compute the pointee address based on "this" + this->m_offset. It is also
important to support smart pointers created on the stack pointing to global
objects (temporaries, function arguments, etc.)

I know this is outside the bug, but it will be certainly a common question when
using GCC and next standard containers. Thanks

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenther at suse dot de]

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

--- Comment #39 from rguenther at suse dot de <rguenther at suse dot de> 2011-01-19 09:54:19 UTC ---
On Tue, 18 Jan 2011, igaztanaga at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36861
> 
> --- Comment #38 from Ion Gaztañaga <igaztanaga at gmail dot com> 2011-01-18 19:15:22 UTC ---
> Thanks Richard for the detailed report. The fact is that the next standard is
> trying to support relative pointers for container implementations (much like
> Boost.Interprocess does), to be able to place containers in shared memory. In
> those cases the relative pointers stores the difference between "this" and the
> pointee, which is what boost::interprocess::offset_ptr does.

But then the pointer arithmetic will not cause the pointer to move
from one object to another - the object will be simply the shared memory
segment (which isn't statically allocated either) - that's perfectly
valid in C and C++ right now.

> It is certainly outside the standard right now and the standard won't include
> such "relative pointer" class, but it will require to container implementations
> to support them as allocator::pointer types. It would be important to find a
> way to use smart pointers, maybe with some existing annotation/attribute to
> avoid optimizing away that relative addressing, so that there is always away to
> compute the pointee address based on "this" + this->m_offset. It is also
> important to support smart pointers created on the stack pointing to global
> objects (temporaries, function arguments, etc.)
> 
> I know this is outside the bug, but it will be certainly a common question when
> using GCC and next standard containers. Thanks

The point with the case in question is that a pointer to a global
object is computed relative to the address _of an automatic variable_.
I hope no standard will ever allow that ;)  It might be a simple
oversight (and thus bug) in Boost AVL though.

If the object were a global one then you wouldn't trigger the particular
bug (though still GCC would conclude that the pointer is pointing to
that global object, which, when in statically allocated storage, can
still lead to "miscompilations").

Richard.

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[igaztanaga at gmail dot com]

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

--- Comment #40 from Ion Gaztañaga <igaztanaga at gmail dot com> 2011-01-19 16:07:01 UTC ---
(In reply to comment #39)
> The point with the case in question is that a pointer to a global
> object is computed relative to the address _of an automatic variable_.
> I hope no standard will ever allow that ;)  It might be a simple
> oversight (and thus bug) in Boost AVL though.

Is not an oversight, it's a basic feature to build easy relative addressing to
be used in shared memory and memory mapped files shared between several
processes. A pointer only stores the distance between the "smart pointer" and
the pointee, so it can be mapped in different addresses in several processes.
Support for automatic storage smart pointers is needed just to support
iterators that could be stored in shared memory (thus, storing smart pointers
in shared memory) and also be used by programmers in a loop (automatic
storage).

Until now, this illegal scheme was working in all known compilers (although
outside the standard, I agree). Since the standard does not support shared
memory, if someday shared memory support is added to the standard, it will
surely require some changes to support this widely used relative addressing.
Until then, I agree, this bug report is invalid.

The only issue I would like to know is if this relative addressing scheme for
automatic variables can be used with GCC with some kind of existing annotation,
anything that could force that automatic variable to have an address that could
be used to point to shared memory elements.

Ion

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenther at suse dot de]

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

--- Comment #41 from rguenther at suse dot de <rguenther at suse dot de> 2011-01-19 16:40:15 UTC ---
On Wed, 19 Jan 2011, igaztanaga at gmail dot com wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36861
> 
> --- Comment #40 from Ion Gaztañaga <igaztanaga at gmail dot com> 2011-01-19 16:07:01 UTC ---
> (In reply to comment #39)
> > The point with the case in question is that a pointer to a global
> > object is computed relative to the address _of an automatic variable_.
> > I hope no standard will ever allow that ;)  It might be a simple
> > oversight (and thus bug) in Boost AVL though.
> 
> Is not an oversight, it's a basic feature to build easy relative addressing to
> be used in shared memory and memory mapped files shared between several
> processes. A pointer only stores the distance between the "smart pointer" and
> the pointee, so it can be mapped in different addresses in several processes.
> Support for automatic storage smart pointers is needed just to support
> iterators that could be stored in shared memory (thus, storing smart pointers
> in shared memory) and also be used by programmers in a loop (automatic
> storage).

The case in question seems to use random automatic storage to represent
a pointer to unrelated storage.  That is never going to work.  And if
it will ever be required to work all points-to analysis will just
be useless which is not something you want.

> Until now, this illegal scheme was working in all known compilers (although
> outside the standard, I agree). Since the standard does not support shared
> memory, if someday shared memory support is added to the standard, it will
> surely require some changes to support this widely used relative addressing.
> Until then, I agree, this bug report is invalid.
> 
> The only issue I would like to know is if this relative addressing scheme for
> automatic variables can be used with GCC with some kind of existing annotation,
> anything that could force that automatic variable to have an address that could
> be used to point to shared memory elements.

No, there is no way to do that.  Sorry, but you really have to
re-design this thing to be standard conformant.

Richard.

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[igaztanaga at gmail dot com]

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

--- Comment #42 from Ion Gaztañaga <igaztanaga at gmail dot com> 2011-01-20 11:52:36 UTC ---
> No, there is no way to do that.  Sorry, but you really have to
> re-design this thing to be standard conformant.

Thanks for your detailed report, I was not aware of this problem so I'll try to
find a solution.

Ion

[Bug c++/36861] New: code generation regression with -O3

[lothar at tradescape dot biz]

gcc 4.3.1 generates code with -O3 that is more than 10 times slower than with
-O0. gcc 4.2.3 does not show this behavior. I am going to attach the test case
that I used to produce these numbers:

with gcc 4.2.3:
( time ./avltest-nn >/dev/null; time ./avltest-no >/dev/null; time ./avltest-on
>/dev/null; time ./avltest-oo >/dev/null; )

real    0m1.112s
user    0m1.028s
sys     0m0.012s

real    0m0.078s
user    0m0.060s
sys     0m0.008s

real    0m0.940s
user    0m0.916s
sys     0m0.008s

real    0m0.088s
user    0m0.072s
sys     0m0.004s


with gcc 4.3.1:
( time ./avltest-nn >/dev/null; time ./avltest-no >/dev/null; time ./avltest-on
>/dev/null; time ./avltest-oo >/dev/null; )

real    0m0.974s
user    0m0.948s
sys     0m0.004s

real    0m12.936s
user    0m12.893s
sys     0m0.016s

real    0m1.128s
user    0m1.012s
sys     0m0.000s

real    0m0.104s
user    0m0.076s
sys     0m0.004s

Here is the information about the compilers used:

$ /opt2/linux/ix86/bin/g++-4.2.3 -v
Using built-in specs.
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-4.2.3/configure --program-suffix=-4.2.3
--enable-__cxa_atexit --enable-languages=c,c++,java --prefix=/opt2/linux/ix86
--target=x86_64-pc-linux-gnu --with-sysroot=/opt2/linux/ix86/gcc-sysroot
--enable-version-specific-runtime-libs --enable-clocale=gnu
Thread model: posix
gcc version 4.2.3

$ /opt2/linux/ix86/bin/g++-4.3.1 -v
Using built-in specs.
Target: x86_64-pc-linux-gnu
Configured with: ../gcc-4.3.1/configure --enable-targets=all --enable-multilib
--enable-__cxa_atexit --enable-languages=c,c++,java
--enable-version-specific-runtime-libs --disable-nls --enable-clocale=gnu
--program-suffix=-4.3.1 --prefix=/opt2/linux/ix86 --target=i686-pc-linux-gnu
--target=x86_64-pc-linux-gnu --with-sysroot=/opt2/linux/ix86/gcc-sysroot
Thread model: posix
gcc version 4.3.1 (GCC)


-- 
           Summary: code generation regression with -O3
           Product: gcc
           Version: 4.3.1
            Status: UNCONFIRMED
          Severity: major
          Priority: P3
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: lothar at tradescape dot biz
GCC target triplet: x86_64-pc-linux-gnu


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

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu dot org]

------- Comment #32 from rguenth at gcc dot gnu dot org  2010-07-05 15:40 -------
Re-confirmed for current 4.5 branch and trunk.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2008-10-22 03:02:05         |2010-07-05 15:40:28
               date|                            |


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

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu dot org]

------- Comment #33 from rguenth at gcc dot gnu dot org  2010-07-05 16:03 -------
Using valgrind there are randomly reported errors, so this is likely either
an invalid testcase or a miscompile that manifests itself as runtime
regression.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|missed-optimization         |wrong-code


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

[Bug target/36861] [4.5/4.6 Regression] boost's compressed avl confuses GCC

[rguenth at gcc dot gnu dot org]

------- Comment #34 from rguenth at gcc dot gnu dot org  2010-07-31 09:29 -------
GCC 4.5.1 is being released, adjusting target milestone.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.1                       |4.5.2


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