The dom oracle also maintains a bitmap indicating which blocks have
relations involving for each name. When related are added, a bit is set.
clear() then simply visits the basic blocks which have relations
involving the ssa-name and removes them.
Bootstraps on x86_64-pc-linux-gnu with no regressions. Pushed.
Andrew
From d77d2fbb681b56a12367fb3ea8e4788776fc9b7e Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <[email protected]>
Date: Thu, 20 Aug 2026 13:53:06 -0400
Subject: [PATCH 3/3] Improve dom_oracle::clear performance.
Add a mnaged list of blocks that contain a relation involving an ssa-name.
PR tree-optimization/126856
* value-relation.cc (dom_oracle::dom_oracle): Create m_block_list.
(dom_oracle::~dom_oracle): Free m_block_list.
(relation_chain_head::clear): Decrease the number of relations.
(dom_oracle::clear): Walk the block_list looking for relations.
(dom_oracle::record_relation_block): New.
(dom_oracle::create_relation_in_bb): call record_relation_block.
* value-relation.h (dom_oracle::m_block_list): New.
(record_relation_block): Declare.
---
gcc/value-relation.cc | 32 +++++++++++++++++++++++++++-----
gcc/value-relation.h | 2 ++
2 files changed, 29 insertions(+), 5 deletions(-)
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index 9bb0aab7fa1..2e95d12b578 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1137,6 +1137,8 @@ dom_oracle::dom_oracle (bool do_trans_p)
m_relations.create (0);
m_relations.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
m_relation_set = BITMAP_ALLOC (&m_bitmaps);
+ m_block_list.create (0);
+ m_block_list.safe_grow_cleared (num_ssa_names + 1);
m_tmp = BITMAP_ALLOC (&m_bitmaps);
m_tmp2 = BITMAP_ALLOC (&m_bitmaps);
}
@@ -1145,6 +1147,7 @@ dom_oracle::dom_oracle (bool do_trans_p)
dom_oracle::~dom_oracle ()
{
+ m_block_list.release ();
m_relations.release ();
}
@@ -1170,6 +1173,7 @@ relation_chain_head::clear (tree name)
m_head = ptr->m_next;
else
last->m_next = ptr->m_next;
+ m_num_relations--;
}
else
last = ptr;
@@ -1187,14 +1191,18 @@ dom_oracle::clear (tree name)
unsigned v = SSA_NAME_VERSION (name);
if (bitmap_bit_p (m_relation_set, v))
{
- basic_block bb;
- FOR_EACH_BB_FN (bb, cfun)
+ gcc_checking_assert (m_block_list[v]);
+ bitmap_iterator bi;
+ unsigned bbi;
+
+ EXECUTE_IF_SET_IN_BITMAP (m_block_list[v], 0, bbi, bi)
{
- if (bb->index >= (int)m_relations.length())
- continue;
- m_relations[bb->index].clear (name);
+ if (bbi >= m_relations.length())
+ break;
+ m_relations[bbi].clear (name);
}
bitmap_clear_bit (m_relation_set, v);
+ bitmap_clear (m_block_list[v]);
}
}
@@ -1304,6 +1312,18 @@ dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
}
}
+void
+dom_oracle::record_relation_block (unsigned v, unsigned bbi)
+{
+ if (v>= m_block_list.length ())
+ m_block_list.safe_grow_cleared (num_ssa_names + 1);
+
+ if (!m_block_list[v])
+ m_block_list[v] = BITMAP_ALLOC (&m_bitmaps);
+
+ bitmap_set_bit (m_block_list[v], bbi);
+}
+
// Register relation K between OP1 and OP2 in block BB by creating a new
// record. It is an error for there to be an existing record.
// Return the record, or NULL if no record was created.
@@ -1341,6 +1361,8 @@ dom_oracle::create_relation_in_bb (basic_block bb, relation_kind k, tree op1,
bitmap_set_bit (bm, v2);
bitmap_set_bit (m_relation_set, v1);
bitmap_set_bit (m_relation_set, v2);
+ record_relation_block (v1, bbi);
+ record_relation_block (v2, bbi);
ptr = (relation_chain *) obstack_alloc (&m_chain_obstack,
sizeof (relation_chain));
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index d57d0717b3e..927f8e6d6e7 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -261,6 +261,7 @@ protected:
bitmap m_tmp, m_tmp2;
bitmap m_relation_set; // Index by ssa-name. True if a relation exists
vec <relation_chain_head> m_relations; // Index by BB, list of relations.
+ vec <bitmap> m_block_list; // Index by ssa-name. Blocks with relations.
relation_kind find_relation_block (unsigned bb, const_bitmap b1,
const_bitmap b2) const;
relation_kind find_relation_block (int bb, tree ssa1, tree ssa2,
@@ -270,6 +271,7 @@ protected:
tree op1, tree op2);
relation_chain *search_and_merge_relation (basic_block bb, relation_kind k,
tree op1, tree op2);
+ void record_relation_block (unsigned v, unsigned bbi);
void register_transitives (basic_block, const class value_relation &);
relation_kind recomputed_relation (basic_block, edge, tree, tree) const;
};
--
2.45.0
