[Bug c++/112307] New: Segmentation fault with -O1 -fcode-hoisting

[Bug c++/112307] New: Segmentation fault with -O1 -fcode-hoisting

[raffael at casagrande dot ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

            Bug ID: 112307
           Summary: Segmentation fault with -O1 -fcode-hoisting
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: raffael at casagrande dot ch
  Target Milestone: ---

*Affected Versions*: 10.0 - current (14.0.0 20231031). Earlier versions cannot
compile the code because it uses c++20.

*System*: Linux
*Command Line*: g++ main.cc -std=c++20 -O1 -fcode-hoisting

*Compiler Output*:

<source>:48:87: warning: friend declaration 'bool operator==(const
EnumeratorRange<ENUMERATOR>::Sentinel&, const
EnumeratorRange<ENUMERATOR>::Iterator&)' declares a non-template function
[-Wnon-template-friend]
   48 |     friend auto operator==(const Sentinel& /*unused*/, const Iterator&
i) noexcept -> bool;
      |                                                                        
              ^~~~
<source>:48:87: note: (if this is not what you intended, make sure the function
template has already been declared and add '<>' after the function name here)

*Runtime Output*: Segmentation fault, "boundary" is printed many times.


*Source File*:
#include <ranges>
#include <iostream>
#include <optional>
#include <cassert>



template <class ENUMERATOR>
class EnumeratorRange {
 public:
  struct Sentinel {
    Sentinel() noexcept = default;
    Sentinel(const Sentinel&) noexcept = default;
    Sentinel(Sentinel&&) noexcept = default;
    auto operator=(const Sentinel&) noexcept -> Sentinel& = default;
    auto operator=(Sentinel&&) noexcept -> Sentinel& = default;
    ~Sentinel() noexcept = default;
  };

  class Iterator {
   public:
    using value_type = typename ENUMERATOR::value_type;
    using difference_type = std::ptrdiff_t;
    explicit Iterator(EnumeratorRange* range) : range_(range) {}
    Iterator() noexcept = default;
    Iterator(const Iterator&) = delete;
    Iterator(Iterator&&) noexcept = default;
    ~Iterator() noexcept = default;
    auto operator=(const Iterator&) = delete;
    auto operator=(Iterator&&) noexcept -> Iterator& = default;

    auto operator*() const noexcept {
      assert(!range_->end_reached_);

      return *range_->enumerator_;
    }
    auto operator++() noexcept -> Iterator& {
      assert(!range_->end_reached_);
      range_->end_reached_ = !range_->enumerator_.Next();
      return *this;
    }

    auto operator++(int) noexcept -> void { ++*this; }

   private:
    EnumeratorRange* range_;

    friend auto operator==(const Sentinel& /*unused*/, const Iterator& i)
noexcept -> bool;
  };

  explicit EnumeratorRange(ENUMERATOR&& e)
      : enumerator_(std::move(e)), end_reached_(!enumerator_.Next()) {}

  auto begin() const noexcept {
    // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
    return Iterator(const_cast<EnumeratorRange*>(this));
  }

  auto end() const noexcept { return Sentinel(); }

 private:
  ENUMERATOR enumerator_;
  bool end_reached_;

  friend auto operator==(const Sentinel&, const Iterator& i) noexcept -> bool {
    return i.range_->end_reached_;
  }
  friend auto operator==(const Iterator& i, const Sentinel& s) noexcept -> bool
{ return s == i; }
  friend auto operator!=(const Sentinel& s, const Iterator& i) noexcept -> bool
{
    return !(s == i);
  }
  friend auto operator!=(const Iterator& i, const Sentinel& s) noexcept -> bool
{
    return !(s == i);
  }
};

class Intersection {
 public:

  auto Boundary() const noexcept -> bool { return is_boundary_; }

 private:
  bool is_boundary_ = true;
};


class CompositeMesh {
 public:

  auto Intersections() const noexcept -> std::ranges::input_range auto;

};


auto CompositeMesh::Intersections() const noexcept -> std::ranges::input_range
auto {
  class Enumerator {
   public:
    using wrapped_range_t = decltype(std::views::single(Intersection()));
    explicit Enumerator(wrapped_range_t&& range) : range_(std::move(range)),
begin_{} {}

    using value_type = Intersection;

    auto operator*() const noexcept -> value_type { return *begin_.value(); }

    auto Next() noexcept -> bool {
      if (!begin_.has_value()) {
        auto b = range_.begin();
        bool result = (b != range_.end());
        begin_ = std::move(b);
        return result;
      } else {
        auto& b = *begin_;
        if ((*b).Boundary()) {
          std::cout << "boundary" << std::endl;
        }

        ++b;
        return b != range_.end();
      }
    }

   private:
    wrapped_range_t range_;
    std::optional<std::ranges::iterator_t<wrapped_range_t>> begin_;
  };

  return EnumeratorRange(Enumerator(std::views::single(Intersection())));
}

int main() {
  auto mesh = CompositeMesh();

  decltype(auto) intersections = mesh.Intersections();
  for (auto intersection : intersections) {
  }
}

*Additional Notes*
- It works if we use `-O2` (which includes -fcode-hoisting)
- Godbolt: https://godbolt.org/z/1PqTKz33Y
- One can disable the following compiler options from `-O1` and still reproduce
the bug: -fno-auto-inc-dec -fno-branch-count-reg -fno-combine-stack-adjustments
-fno-compare-elim -fno-cprop-registers -fno-dce -fno-defer-pop
-fno-delayed-branch -fno-dse -fno-forward-propagate -fno-if-conversion
-fno-if-conversion2 -fno-inline-functions-called-once -fno-ipa-modref
-fno-ipa-profile -fno-ipa-pure-const -fno-ipa-reference
-fno-ipa-reference-addressable -fno-merge-constants -fno-move-loop-invariants
-fno-move-loop-stores -fno-omit-frame-pointer -fno-reorder-blocks
-fno-shrink-wrap -fno-shrink-wrap-separate -fno-split-wide-types
-fno-ssa-backprop -fno-ssa-phiopt -fno-tree-bit-ccp -fno-tree-ccp -fno-tree-ch
-fno-tree-coalesce-vars -fno-tree-copy-prop -fno-tree-dce
-fno-tree-dominator-opts -fno-tree-phiprop -fno-tree-scev-cprop -fno-tree-sink
-fno-tree-slsr -fno-tree-sra -fno-tree-ter -fno-unit-at-a-time

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu.org
   Last reconfirmed|                            |2023-10-31
             Status|UNCONFIRMED                 |NEW
          Component|c++                         |tree-optimization
     Ever confirmed|0                           |1
      Known to fail|                            |11.4.1, 12.3.1, 13.2.1,
                   |                            |14.0
           Keywords|                            |needs-reduction, wrong-code

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fails everywhere.  Complicated maze of C++ makes it difficult to look at.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jamborm at gcc dot gnu.org

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
There is no actual code-hoisting happening, the only effect of -fcode-hoisting
is that we perform a round of value-numbering which does perform quite a bit
of simplification in the program.  In particular it simplifies
CompositeMesh::Intersections down to just

  <bb 2> [local count: 1073741826]:
  D.72649 ={v} {CLOBBER};
  MEM[(struct optional *)&D.72649 + 8B] ={v} {CLOBBER};
  MEM[(union _Storage *)&D.72649 + 8B] ={v} {CLOBBER};
  MEM[(struct __as_base  &)&<retval>] ={v} {CLOBBER};
  MEM <unsigned char> [(struct Enumerator *)&<retval>] = 1;
  MEM <unsigned char> [(struct Enumerator *)&<retval> + 16B] = 0;
  MEM <struct Intersection *> [(struct Enumerator *)&<retval> + 8B] =
&MEM[(struct __box *)&<retval>]._M_value;
  MEM <unsigned char> [(struct Enumerator *)&<retval> + 16B] = 1;
  <retval>.end_reached_ = 0;
  D.72649 ={v} {CLOBBER(eol)};
  return <retval>;

by optimizing a leading condition:

+  <bb 2> [local count: 1073741826]:
   D.72649 ={v} {CLOBBER};
   MEM[(struct optional *)&D.72649 + 8B] ={v} {CLOBBER};
   MEM[(union _Storage *)&D.72649 + 8B] ={v} {CLOBBER};
   MEM[(struct __as_base  &)&<retval>] ={v} {CLOBBER};
   MEM <unsigned char> [(struct Enumerator *)&<retval>] = 1;
   MEM <unsigned char> [(struct Enumerator *)&<retval> + 16B] = 0;
-  _12 = MEM[(const struct _Optional_base *)&<retval> +
8B]._M_payload.D.71902._M_engaged;
-  if (_12 != 0)
-    goto <bb 4>; [66.00%]
-  else
-    goto <bb 3>; [34.00%]
-
-  <bb 3> [local count: 365072225]:
   MEM <struct Intersection *> [(struct Enumerator *)&<retval> + 8B] =
&MEM[(struct __box *)&<retval>]._M_value;
   MEM <unsigned char> [(struct Enumerator *)&<retval> + 16B] = 1;
-  goto <bb 12>; [100.00%]

the load ligns up exactly with the immediately preceeding store.

A preceeding value-numbering pass still sees

<bb 2> [local count: 1073741824]:
D.72600 ={v} {CLOBBER};
MEM[(struct single_view *)&D.72600] = 1;
MEM[(struct optional *)&D.72600 + 8B] ={v} {CLOBBER};
MEM[(union _Storage *)&D.72600 + 8B] ={v} {CLOBBER};
MEM[(struct _Optional_payload_base *)&D.72600 + 8B]._M_engaged = 0;
MEM[(struct __as_base  &)&<retval>] ={v} {CLOBBER};
<retval>.enumerator_ = D.72600;
_12 = MEM[(const struct _Optional_base *)&<retval> +
8B]._M_payload.D.71853._M_engaged;
if (_12 != 0)

but SRA then wrecks this I think:

Created a replacement for D.72600 offset: 0, size: 8: SR.74D.80925
Created a replacement for D.72600 offset: 128, size: 8: SR.75D.80926
Removing load: <retval>.enumerator_ = D.72600;
...
  <bb 2> [local count: 1073741824]:
  D.72600 ={v} {CLOBBER};
  SR.74_13 = 1;
  MEM[(struct optional *)&D.72600 + 8B] ={v} {CLOBBER};
  MEM[(union _Storage *)&D.72600 + 8B] ={v} {CLOBBER};
  SR.75_68 = 0;
  MEM[(struct __as_base  &)&<retval>] ={v} {CLOBBER};
  MEM <unsigned char> [(struct Enumerator *)&<retval>] = SR.74_13;
  MEM <unsigned char> [(struct Enumerator *)&<retval> + 16B] = SR.75_68;
  _12 = MEM[(const struct _Optional_base *)&<retval> +
8B]._M_payload.D.71853._M_engaged;
  if (_12 != 0)

that's

#1  0x0000000001c186f1 in sra_modify_assign (
    stmt=<gimple_assign 0x7ffff383b1e0>, gsi=0x7fffffffd9d0)
    at /home/rguenther/src/trunk/gcc/tree-sra.cc:4490
4490                  generate_subtree_copies (racc->first_child, lhs,
(gdb) l
4485                  if (dump_file)
4486                    {
4487                      fprintf (dump_file, "Removing load: ");
4488                      print_gimple_stmt (dump_file, stmt, 0);
4489                    }
4490                  generate_subtree_copies (racc->first_child, lhs,
4491                                           racc->offset, 0, 0, gsi,
4492                                           false, false, loc);

note we pass "write" as false here, and 'lacc' is null.  But if we cannot
analyze the LHS I wonder why we haven't disqualified the RHS here?

I'll note that while this does look like a serious issue -fno-tree-sra
fixes that but that doesn't seem to fix the testcase :/

The difference in main() remains though:

@@ -195,9 +305,7 @@
   if (_16 != 0)
     goto <bb 13>; [11.00%]
   else
-    goto <bb 14>; [89.00%]
-
-  <bb 14> [local count: 105119324]:
+    goto <bb 3>; [89.00%]

   <bb 3> [local count: 955247973]:
   _25 = MEM[(const struct _Optional_base *)&intersections +
8B]._M_payload.D.71902._M_engaged;
@@ -261,15 +369,7 @@
   <bb 12> [local count: 955630224]:
   _34 = _26 + 1;
   MEM[(struct Intersection * &)&intersections + 8] = _34;
-  _36 = &MEM <struct EnumeratorRange> [(void *)&intersections + 1B] != _34;
-  _22 = &MEM <struct EnumeratorRange> [(void *)&intersections + 1B] == _34;
-  intersections.end_reached_ = _22;
-  if (&MEM <struct EnumeratorRange> [(void *)&intersections + 1B] == _34)
-    goto <bb 13>; [11.00%]
-  else
-    goto <bb 15>; [89.00%]
-
-  <bb 15> [local count: 850510900]:
+  intersections.end_reached_ = 0;
   goto <bb 3>; [100.00%]

   <bb 13> [local count: 118111600]:

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=109945

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
The transform in main is because we do

Value numbering stmt = _22 = &MEM <struct EnumeratorRange> [(void
*)&intersections + 1B] == _34;
Applying pattern match.pd:6940, gimple-match-5.cc:1815
Match-and-simplified &MEM <struct EnumeratorRange> [(void *)&intersections +
1B] == _34 to 0
RHS &MEM <struct EnumeratorRange> [(void *)&intersections + 1B] == _34
simplified to 0
Setting value number of _22 to 0 (changed)
Value numbering stmt = intersections.end_reached_ = _22;
No store match
Value numbering store intersections.end_reached_ to 0
Setting value number of .MEM_93 to .MEM_93 (changed)
Value numbering stmt = if (&MEM <struct EnumeratorRange> [(void
*)&intersections + 1B] == _34)
marking known outgoing edge 12 -> 15 executable

and that's using

/* Simplify pointer equality compares using PTA.  */
(for neeq (ne eq)
 (simplify
  (neeq @0 @1)
  (if (POINTER_TYPE_P (TREE_TYPE (@0))
       && ptrs_compare_unequal (@0, @1))
   { constant_boolean_node (neeq != EQ_EXPR, type); })))

which makes it really a similar issue as PR109945 - _34 points to
nonlocal/escaped but 'intersections' isn't part of that set though it
probably "escapes" at

<bb 2> [local count: 118111600]:
intersections = CompositeMesh::Intersections (&mesh); [return slot
optimization]

-fno-tree-pta is a (quite heavy) workaround.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |redi at gcc dot gnu.org

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> ---
I don't quite see how

  return EnumeratorRange(Enumerator(std::views::single(Intersection())));

makes CompositeMesh::Intersections() return an object that refers to itself
but points-to doesn't consider it could:

callarg(12) = &mesh
...
ESCAPED = &mesh
intersections = NONLOCAL
intersections = callarg(12)

debugging at -O0 shows

(gdb) p intersections
$1 = {enumerator_ = {
    range_ =
{<std::ranges::view_interface<std::ranges::single_view<Intersection> >> = {<No
data fields>}, _M_value = {_M_value = {is_boundary_ = true}}}, 
    begin_ = std::optional<Intersection *> = {
      [contained value] = 0x7fffffffde80}}, end_reached_ = false}
(gdb) p &intersections
$2 = (EnumeratorRange<CompositeMesh::Intersections() const::Enumerator> *)
0x7fffffffde80

so it contains a reference to itself.  As said this feels like those other
issues which are maybe invalid because of object lifetimes.

But maybe there's sth special here.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #5 from Jonathan Wakely <redi at gcc dot gnu.org> ---
  return EnumeratorRange(Enumerator(std::views::single(Intersection())));

This creates a temporary Intersection object, then copies that into a
single_view object. Then that is copied into an Enumerator object which looks
like:

Enumerator {
  single_view<Intersection> range_;
  optional<single_view<Intersection>::_Iterator> begin_;
};

The range_ member is the copy of std::views::single(Intersection()) and the
begin_ member is initially empty.

Then that Enumerator is copied into an EnumeratorRange which calls Next() on
the new copy, which sets its begin_ member to point to the range_ member. Then
the EnumeratorRange is returned.

So I think it's expected that the Enumerator points to itself, because of the
call to its Next() member.

BUT, the self-referential pointer is set to the address of the range_ member
before the return value is copied, and so goes out of scope when that object is
copied via registers and then copied again into the automatic variable in
main().

So yes, I think it's invalid for the same reason as PR 109945 comment 25
explains, and indeed giving any of the objects a non-trivial destructor
prevents it being copied via registers and so the pointer isn't invalidated.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
Thanks, so keeping this open but it will likely end up INVALID.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[raffael at casagrande dot ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #7 from Raffael Casagrande <raffael at casagrande dot ch> ---
@Jonathan Wakely Thanks very much for the detailed analysis. But there is one
point which I don't understand:

> BUT, the self-referential pointer is set to the address of the range_ member 
> before the return value is copied, and so goes out of scope when that object
> is copied via registers and then copied again into the automatic variable
> in main().


I can't follow/understand how Next() is called before the return value is
copied.
If we look at the constructor of EnumeratorRange, we see that `enumerator_` is
initialized before end_reached_.

And afterwards the enumerator_ is not moved/copied anymore because of copy
elision? This can be verified by adding some extra print statements to the
copy/move constructor of Enumerator.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #8 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I explained this in PR 109945 comment 25

There is no guaranteed copy elision for objects with a trivial copy constructor
and trivial (or deleted) destructor. The compiler is allowed to make temporary
copies, to allow passing the object in registers (which has been what the ABI
requires for decades longer than the guaranteed copy elision rules have
existed).

If you want to have self-referential pointers in your object then you need to
ensure copies really are elided. And so it should not be trivially copyable,
because that removes the guarantee of copy elision.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Ironically, writing a user-provided (and so non-trivial) copy constructor which
fixes up the self-referential pointer (or iterator, in your case) will restore
guaranteed elision, and that copy constructor isn't actually used.

But with a trivial copy constructor, your object gets copied, and the
self-referential pointer gets invalidated because it points to a temporary that
has gone out of scope, not to the final object after the copies are done.

[Bug tree-optimization/112307] Segmentation fault with -O1 -fcode-hoisting

[raffael at casagrande dot ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=112307

--- Comment #10 from Raffael Casagrande <raffael at casagrande dot ch> ---
(In reply to Jonathan Wakely from comment #9)

Thanks very much! I missed the part with the trivial copy constructor and
learned again an important lesson. That explains why it works when I defined
the copy constructors manually.