https://gcc.gnu.org/g:34bc617b34b62f59dc53ad0de165accb603cb08a
commit r15-10316-g34bc617b34b62f59dc53ad0de165accb603cb08a
Author: Richard Sandiford <rdsandif...@googlemail.com>
Date: Thu Sep 11 17:32:38 2025 +0100
rtl-ssa: Maintain clobber_group invariant [PR121757]
In order to reduce time complexity, rtl-ssa groups consecutive
clobbers together. Each group of clobbers has a splay tree for
lookup and manipulation purposes.
This arrangement means that we might need to split a group (when
inserting a new non-clobber definition between two clobbers) or
to join consecutive groups together (when deleting an intervening
non-clobber definition). To reduce the time complexity of these updates,
the back pointer from a clobber to its group is only updated lazily.
The invariant is supposed to be that the first clobber, last clobber,
and splay tree root have the right group at all times, whereas other
members of the group can have identifiably stale group pointers.
However, a lack of abstraction meant that only some splay tree lookups
correctly maintained this invariant. Others did not update the group
pointer after installing a new root.
This patch adds a helper that maintains the invariant and uses it in
three places, one that was already correct and two that were wrong.
The original lookup_clobber is still used in other code that
manipulates groups as a whole.
gcc/
PR rtl-optimization/121757
* rtl-ssa/accesses.h (clobber_group::lookup_clobber): New member
function.
* rtl-ssa/accesses.cc (clobber_group::lookup_clobber): Likewise.
(clobber_group::prev_clobber, clobber_group::next_clobber)
(function_info::add_clobber): Use it.
gcc/testsuite/
PR rtl-optimization/121757
* g++.dg/pr121757.C: New test.
Diff:
---
gcc/rtl-ssa/accesses.cc | 31 ++++++++++++++++++-------------
gcc/rtl-ssa/accesses.h | 2 ++
gcc/testsuite/g++.dg/pr121757.C | 19 +++++++++++++++++++
3 files changed, 39 insertions(+), 13 deletions(-)
diff --git a/gcc/rtl-ssa/accesses.cc b/gcc/rtl-ssa/accesses.cc
index 3d929971f56a..6e3717aee24a 100644
--- a/gcc/rtl-ssa/accesses.cc
+++ b/gcc/rtl-ssa/accesses.cc
@@ -398,22 +398,20 @@ set_node::print (pretty_printer *pp) const
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);
+ int comparison = lookup_clobber (insn);
if (comparison <= 0)
- return dyn_cast<clobber_info *> (tree.root ()->prev_def ());
- return tree.root ();
+ return dyn_cast<clobber_info *> (m_clobber_tree.root ()->prev_def ());
+ return m_clobber_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);
+ int comparison = lookup_clobber (insn);
if (comparison >= 0)
- return dyn_cast<clobber_info *> (tree.root ()->next_def ());
- return tree.root ();
+ return dyn_cast<clobber_info *> (m_clobber_tree.root ()->next_def ());
+ return m_clobber_tree.root ();
}
// See the comment above the declaration.
@@ -438,6 +436,17 @@ clobber_group::print (pretty_printer *pp) const
pp_indentation (pp) -= 4;
}
+// A wrapper around rtl_ssa::lookup_clobber that ensures that the root
+// of the splay tree always has the correct group.
+int
+clobber_group::lookup_clobber (insn_info *insn) const
+{
+ auto &tree = const_cast<clobber_tree &> (m_clobber_tree);
+ int result = rtl_ssa::lookup_clobber (tree, insn);
+ tree->update_group (const_cast<clobber_group *> (this));
+ return result;
+}
+
// See the comment above the declaration.
def_info *
def_lookup::prev_def (insn_info *insn) const
@@ -659,14 +668,10 @@ function_info::add_clobber (clobber_info *clobber,
clobber_group *group)
// Search for either the previous or next clobber in the group.
// The result is less than zero if CLOBBER should come before NEIGHBOR
// or greater than zero if CLOBBER should come after NEIGHBOR.
- int comparison = lookup_clobber (group->m_clobber_tree, clobber->insn ());
+ int comparison = group->lookup_clobber (clobber->insn ());
gcc_checking_assert (comparison != 0);
clobber_info *neighbor = group->m_clobber_tree.root ();
- // Since HEIGHBOR is now the root of the splay tree, its group needs
- // to be up-to-date.
- neighbor->update_group (group);
-
// If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
// otherwise insert CLOBBER to NEIGHBOR's right.
clobber_info::splay_tree::insert_child (neighbor, comparison > 0, clobber);
diff --git a/gcc/rtl-ssa/accesses.h b/gcc/rtl-ssa/accesses.h
index 98403f78b37b..2fcb48746d1f 100644
--- a/gcc/rtl-ssa/accesses.h
+++ b/gcc/rtl-ssa/accesses.h
@@ -944,6 +944,8 @@ private:
void set_first_clobber (clobber_info *c) { m_clobber_or_set = c; }
void set_last_clobber (clobber_info *c) { m_last_clobber = c; }
+ int lookup_clobber (insn_info *) const;
+
// The value returned by last_clobber ().
clobber_info *m_last_clobber;
diff --git a/gcc/testsuite/g++.dg/pr121757.C b/gcc/testsuite/g++.dg/pr121757.C
new file mode 100644
index 000000000000..3a661fe4be28
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pr121757.C
@@ -0,0 +1,19 @@
+// { dg-require-effective-target shared }
+// { dg-require-effective-target lto }
+// { dg-options "-O2 -flto -shared" }
+
+struct QAbstractFileEngine {
+ virtual bool seek(long long);
+};
+struct QQmlPreviewFileEngine : QAbstractFileEngine {
+ bool seek(long long);
+ int m_contents;
+ QAbstractFileEngine * m_fallback;
+};
+bool f(void*);
+bool QQmlPreviewFileEngine::seek(long long newPos) {
+ if (m_fallback)
+ return m_fallback->seek(newPos);
+ else
+ return f(&m_contents);
+}
