rtl-ssa: Fix prev/next_def confusion [PR104869]

rtl-ssa chains definitions into an RPO list.  It also groups
sequences of clobbers together into a single node, so that it's
possible to skip over the clobbers in constant time in order to
get the next or previous set.

When adding a clobber to an insn, the main DF barriers for that
clobber are the last use of the previous set (if any) and the next
set (if any); adding a new clobber to a sea of clobbers is fine.
def_lookup provided the basis for these barriers as prev_def ()
and next_def ().

But of course, in hindsight, those were bad names, since they
implied that the returned values were literally the previous
definition (of any kind) or the next definition (of any kind).
And function_info::make_use_available was using the same routines
assuming that they had that meaning. :-(

This made a difference for the case where the start of a BB
occurs in the middle of an (RPO) clobber group: we then want
the previous and next clobbers in the group, rather than the
set before the clobber group and the set after the clobber group.

This patch renames the existing routines to something that's hopefully
clearer (though also more long-winded).  It then adds routines that
really do provide the previous and next definitions.

This complication is supposed to be internal to rtl-ssa and, as
mentioned above, is part of trying to reduce time complexity.

Tested on aarch64-linux-gnu and powerpc64le-linux-gnu.  OK to install?

This will be latent on GCC 11, so it should probably be backported there.

Richard


gcc/
	* rtl-ssa/accesses.h (clobber_group::prev_clobber): Declare.
	(clobber_group::next_clobber): Likewise.
	(def_lookup::prev_def): Rename to...
	(def_lookup::last_def_of_prev_group): ...this.
	(def_lookup::next_def): Rename to...
	(def_lookup::first_def_of_next_group): ...this.
	(def_lookup::matching_or_prev_def): Rename to...
	(def_lookup::matching_set_or_last_def_of_prev_group): ...this.
	(def_lookup::matching_or_next_def): Rename to...
	(def_lookup::matching_set_or_first_def_of_next_group): ...this.
	(def_lookup::prev_def): New function, taking the lookup insn as
	argument.
	(def_lookup::next_def): Likewise.
	* rtl-ssa/member-fns.inl (def_lookup::prev_def): Rename to...
	(def_lookup::last_def_of_prev_group): ...this.
	(def_lookup::next_def): Rename to...
	(def_lookup::first_def_of_next_group): ...this.
	(def_lookup::matching_or_prev_def): Rename to...
	(def_lookup::matching_set_or_last_def_of_prev_group): ...this.
	(def_lookup::matching_or_next_def): Rename to...
	(def_lookup::matching_set_or_first_def_of_next_group): ...this.
	* rtl-ssa/movement.h (restrict_movement_for_dead_range): Update after
	above renaming.
	* rtl-ssa/accesses.cc (clobber_group::prev_clobber): New function.
	(clobber_group::next_clobber): Likewise.
	(def_lookup::prev_def): Likewise.
	(def_lookup::next_def): Likewise.
	(function_info::make_use_available): Pass the lookup insn to
	def_lookup::prev_def and def_lookup::next_def.

gcc/testsuite/
	* g++.dg/pr104869.C: New test.
---
 gcc/rtl-ssa/accesses.cc         | 52 +++++++++++++++++++++-
 gcc/rtl-ssa/accesses.h          | 22 ++++++++--
 gcc/rtl-ssa/member-fns.inl      | 12 ++---
 gcc/rtl-ssa/movement.h          |  6 +--
 gcc/testsuite/g++.dg/pr104869.C | 78 +++++++++++++++++++++++++++++++++
 5 files changed, 155 insertions(+), 15 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/pr104869.C

On Sun, Mar 20, 2022 at 10:41 PM Richard Sandiford via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> rtl-ssa chains definitions into an RPO list.  It also groups
> sequences of clobbers together into a single node, so that it's
> possible to skip over the clobbers in constant time in order to
> get the next or previous set.
>
> When adding a clobber to an insn, the main DF barriers for that
> clobber are the last use of the previous set (if any) and the next
> set (if any); adding a new clobber to a sea of clobbers is fine.
> def_lookup provided the basis for these barriers as prev_def ()
> and next_def ().
>
> But of course, in hindsight, those were bad names, since they
> implied that the returned values were literally the previous
> definition (of any kind) or the next definition (of any kind).
> And function_info::make_use_available was using the same routines
> assuming that they had that meaning. :-(
>
> This made a difference for the case where the start of a BB
> occurs in the middle of an (RPO) clobber group: we then want
> the previous and next clobbers in the group, rather than the
> set before the clobber group and the set after the clobber group.
>
> This patch renames the existing routines to something that's hopefully
> clearer (though also more long-winded).  It then adds routines that
> really do provide the previous and next definitions.
>
> This complication is supposed to be internal to rtl-ssa and, as
> mentioned above, is part of trying to reduce time complexity.
>
> Tested on aarch64-linux-gnu and powerpc64le-linux-gnu.  OK to install?

OK.

> This will be latent on GCC 11, so it should probably be backported there.

Agreed, maybe after a short soaking time.

Richard.

> Richard
>
>
> gcc/
>         * rtl-ssa/accesses.h (clobber_group::prev_clobber): Declare.
>         (clobber_group::next_clobber): Likewise.
>         (def_lookup::prev_def): Rename to...
>         (def_lookup::last_def_of_prev_group): ...this.
>         (def_lookup::next_def): Rename to...
>         (def_lookup::first_def_of_next_group): ...this.
>         (def_lookup::matching_or_prev_def): Rename to...
>         (def_lookup::matching_set_or_last_def_of_prev_group): ...this.
>         (def_lookup::matching_or_next_def): Rename to...
>         (def_lookup::matching_set_or_first_def_of_next_group): ...this.
>         (def_lookup::prev_def): New function, taking the lookup insn as
>         argument.
>         (def_lookup::next_def): Likewise.
>         * rtl-ssa/member-fns.inl (def_lookup::prev_def): Rename to...
>         (def_lookup::last_def_of_prev_group): ...this.
>         (def_lookup::next_def): Rename to...
>         (def_lookup::first_def_of_next_group): ...this.
>         (def_lookup::matching_or_prev_def): Rename to...
>         (def_lookup::matching_set_or_last_def_of_prev_group): ...this.
>         (def_lookup::matching_or_next_def): Rename to...
>         (def_lookup::matching_set_or_first_def_of_next_group): ...this.
>         * rtl-ssa/movement.h (restrict_movement_for_dead_range): Update after
>         above renaming.
>         * rtl-ssa/accesses.cc (clobber_group::prev_clobber): New function.
>         (clobber_group::next_clobber): Likewise.
>         (def_lookup::prev_def): Likewise.
>         (def_lookup::next_def): Likewise.
>         (function_info::make_use_available): Pass the lookup insn to
>         def_lookup::prev_def and def_lookup::next_def.
>
> gcc/testsuite/
>         * g++.dg/pr104869.C: New test.
> ---
>  gcc/rtl-ssa/accesses.cc         | 52 +++++++++++++++++++++-
>  gcc/rtl-ssa/accesses.h          | 22 ++++++++--
>  gcc/rtl-ssa/member-fns.inl      | 12 ++---
>  gcc/rtl-ssa/movement.h          |  6 +--
>  gcc/testsuite/g++.dg/pr104869.C | 78 +++++++++++++++++++++++++++++++++
>  5 files changed, 155 insertions(+), 15 deletions(-)
>  create mode 100644 gcc/testsuite/g++.dg/pr104869.C
>
> diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
> index 47f2aea05db..dcf2335056b 100644
> --- a/gcc/rtl-ssa/accesses.cc
> +++ b/gcc/rtl-ssa/accesses.cc
> @@ -393,6 +393,28 @@ set_node::print (pretty_printer *pp) const
>    pp_access (pp, first_def ());
>  }
>
> +// See the comment above the declaration.
> +clobber_info *
> +clobber_group::prev_clobber (insn_info *insn) const
> +{
> +  auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
> +  int comparison = lookup_clobber (tree, insn);
> +  if (comparison <= 0)
> +    return dyn_cast<clobber_info *> (tree.root ()->prev_def ());
> +  return tree.root ();
> +}
> +
> +// See the comment above the declaration.
> +clobber_info *
> +clobber_group::next_clobber (insn_info *insn) const
> +{
> +  auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
> +  int comparison = lookup_clobber (tree, insn);
> +  if (comparison >= 0)
> +    return dyn_cast<clobber_info *> (tree.root ()->next_def ());
> +  return tree.root ();
> +}
> +
>  // See the comment above the declaration.
>  void
>  clobber_group::print (pretty_printer *pp) const
> @@ -415,6 +437,32 @@ clobber_group::print (pretty_printer *pp) const
>    pp_indentation (pp) -= 4;
>  }
>
> +// See the comment above the declaration.
> +def_info *
> +def_lookup::prev_def (insn_info *insn) const
> +{
> +  if (mux && comparison == 0)
> +    if (auto *node = mux.dyn_cast<def_node *> ())
> +      if (auto *group = dyn_cast<clobber_group *> (node))
> +       if (clobber_info *clobber = group->prev_clobber (insn))
> +         return clobber;
> +
> +  return last_def_of_prev_group ();
> +}
> +
> +// See the comment above the declaration.
> +def_info *
> +def_lookup::next_def (insn_info *insn) const
> +{
> +  if (mux && comparison == 0)
> +    if (auto *node = mux.dyn_cast<def_node *> ())
> +      if (auto *group = dyn_cast<clobber_group *> (node))
> +       if (clobber_info *clobber = group->next_clobber (insn))
> +         return clobber;
> +
> +  return first_def_of_next_group ();
> +}
> +
>  // Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
>  // already belong to a group.
>  clobber_group *
> @@ -1299,9 +1347,9 @@ function_info::make_use_available (use_info *use, bb_info *bb,
>           input->m_is_temp = true;
>           phi->m_is_temp = true;
>           phi->make_degenerate (input);
> -         if (def_info *prev = dl.prev_def ())
> +         if (def_info *prev = dl.prev_def (phi_insn))
>             phi->set_prev_def (prev);
> -         if (def_info *next = dl.next_def ())
> +         if (def_info *next = dl.next_def (phi_insn))
>             phi->set_next_def (next);
>         }
>
> diff --git a/gcc/rtl-ssa/accesses.h b/gcc/rtl-ssa/accesses.h
> index 9b5d3eec56e..85c8b2cfdf3 100644
> --- a/gcc/rtl-ssa/accesses.h
> +++ b/gcc/rtl-ssa/accesses.h
> @@ -909,6 +909,12 @@ public:
>    clobber_info *first_clobber () const;
>    clobber_info *last_clobber () const { return m_last_clobber; }
>
> +  // Return the last clobber before INSN in the group, or null if none.
> +  clobber_info *prev_clobber (insn_info *insn) const;
> +
> +  // Return the next clobber after INSN in the group, or null if none.
> +  clobber_info *next_clobber (insn_info *insn) const;
> +
>    // Return true if this group has been replaced by new clobber_groups.
>    bool has_been_superceded () const { return !m_last_clobber; }
>
> @@ -993,25 +999,33 @@ public:
>    //
>    // Otherwise, return the last definition that occurs before P,
>    // or null if none.
> -  def_info *prev_def () const;
> +  def_info *last_def_of_prev_group () const;
>
>    // If we found a clobber_group that spans P, return the definition
>    // that follows the end of the group, or null if none.
>    //
>    // Otherwise, return the first definition that occurs after P,
>    // or null if none.
> -  def_info *next_def () const;
> +  def_info *first_def_of_next_group () const;
>
>    // If we found a set_info at P, return that set_info, otherwise return null.
>    set_info *matching_set () const;
>
>    // If we found a set_info at P, return that set_info, otherwise return
>    // prev_def ().
> -  def_info *matching_or_prev_def () const;
> +  def_info *matching_set_or_last_def_of_prev_group () const;
>
>    // If we found a set_info at P, return that set_info, otherwise return
>    // next_def ().
> -  def_info *matching_or_next_def () const;
> +  def_info *matching_set_or_first_def_of_next_group () const;
> +
> +  // P is the location of INSN.  Return the last definition (of any kind)
> +  // that occurs before INSN, or null if none.
> +  def_info *prev_def (insn_info *insn) const;
> +
> +  // P is the location of INSN.  Return the next definition (of any kind)
> +  // that occurs after INSN, or null if none.
> +  def_info *next_def (insn_info *insn) const;
>
>    def_mux mux;
>    int comparison;
> diff --git a/gcc/rtl-ssa/member-fns.inl b/gcc/rtl-ssa/member-fns.inl
> index efc4e8ce113..eea20b9c4c0 100644
> --- a/gcc/rtl-ssa/member-fns.inl
> +++ b/gcc/rtl-ssa/member-fns.inl
> @@ -401,7 +401,7 @@ def_mux::set () const
>  }
>
>  inline def_info *
> -def_lookup::prev_def () const
> +def_lookup::last_def_of_prev_group () const
>  {
>    if (!mux)
>      return nullptr;
> @@ -413,7 +413,7 @@ def_lookup::prev_def () const
>  }
>
>  inline def_info *
> -def_lookup::next_def () const
> +def_lookup::first_def_of_next_group () const
>  {
>    if (!mux)
>      return nullptr;
> @@ -433,19 +433,19 @@ def_lookup::matching_set () const
>  }
>
>  inline def_info *
> -def_lookup::matching_or_prev_def () const
> +def_lookup::matching_set_or_last_def_of_prev_group () const
>  {
>    if (set_info *set = matching_set ())
>      return set;
> -  return prev_def ();
> +  return last_def_of_prev_group ();
>  }
>
>  inline def_info *
> -def_lookup::matching_or_next_def () const
> +def_lookup::matching_set_or_first_def_of_next_group () const
>  {
>    if (set_info *set = matching_set ())
>      return set;
> -  return next_def ();
> +  return first_def_of_next_group ();
>  }
>
>  inline insn_note::insn_note (insn_note_kind kind)
> diff --git a/gcc/rtl-ssa/movement.h b/gcc/rtl-ssa/movement.h
> index d36926e5b01..98a0ac3a5b9 100644
> --- a/gcc/rtl-ssa/movement.h
> +++ b/gcc/rtl-ssa/movement.h
> @@ -103,7 +103,7 @@ restrict_movement_for_dead_range (insn_range_info &move_range,
>    resource_info resource = full_register (regno);
>    def_lookup dl = crtl->ssa->find_def (resource, insn);
>
> -  def_info *prev = dl.prev_def ();
> +  def_info *prev = dl.last_def_of_prev_group ();
>    ebb_info *ebb = insn->ebb ();
>    if (!prev || prev->ebb () != ebb)
>      {
> @@ -143,8 +143,8 @@ restrict_movement_for_dead_range (insn_range_info &move_range,
>      }
>
>    // Stop the instruction moving beyond the next relevant definition of REGNO.
> -  def_info *next = first_def_ignoring (dl.matching_or_next_def (),
> -                                      ignore_clobbers::YES, ignore);
> +  def_info *next = dl.matching_set_or_first_def_of_next_group ();
> +  next = first_def_ignoring (next, ignore_clobbers::YES, ignore);
>    if (next)
>      move_range = move_earlier_than (move_range, next->insn ());
>
> diff --git a/gcc/testsuite/g++.dg/pr104869.C b/gcc/testsuite/g++.dg/pr104869.C
> new file mode 100644
> index 00000000000..9a6ef88adbd
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/pr104869.C
> @@ -0,0 +1,78 @@
> +// PR rtl-optimization/104869
> +// { dg-do run }
> +// { dg-options "-O2 -fvisibility=hidden -std=c++11" }
> +// { dg-require-visibility "" }
> +
> +struct QBasicAtomicInteger {
> +  [[gnu::noipa]] int loadRelaxed() { return 1; }
> +};
> +struct RefCount {
> +  bool deref() {
> +    int count = atomic.loadRelaxed();
> +    if (count)
> +      return false;
> +    return deref();
> +  }
> +  QBasicAtomicInteger atomic;
> +};
> +struct QArrayData {
> +  RefCount ref;
> +};
> +struct QString {
> +  ~QString();
> +  QArrayData d;
> +};
> +int ok;
> +QString::~QString() { d.ref.deref(); }
> +struct Label {
> +  bool isValid() { return generator; }
> +  int *generator;
> +  int index;
> +};
> +struct ControlFlow;
> +struct Codegen {
> +  [[gnu::noipa]] bool visit();
> +  ControlFlow *controlFlow;
> +};
> +struct ControlFlow {
> +  enum UnwindType { EE };
> +  struct UnwindTarget {
> +    Label linkLabel;
> +  };
> +  ControlFlow *parent;
> +  UnwindType unwindTarget_type;
> +  UnwindTarget unwindTarget() {
> +    QString label;
> +    ControlFlow *flow = this;
> +    while (flow) {
> +      Label l = getUnwindTarget(unwindTarget_type, label);
> +      if (l.isValid())
> +        return {l};
> +      flow = flow->parent;
> +    }
> +    return UnwindTarget();
> +  }
> +  [[gnu::noipa]] Label getUnwindTarget(UnwindType, QString &) {
> +    Label l = { &ok, 0 };
> +    return l;
> +  }
> +};
> +[[gnu::noipa]] void foo(int) {
> +  ok = 1;
> +}
> +[[gnu::noipa]] bool Codegen::visit() {
> +  if (!controlFlow)
> +    return false;
> +  ControlFlow::UnwindTarget target = controlFlow->unwindTarget();
> +  if (target.linkLabel.isValid())
> +    foo(2);
> +  return false;
> +}
> +int
> +main() {
> +  ControlFlow cf = { nullptr, ControlFlow::UnwindType::EE };
> +  Codegen c = { &cf };
> +  c.visit();
> +  if (!ok)
> +    __builtin_abort ();
> +}
> --
> 2.25.1
>