diff mbox series

[5/6] rtl-ssa: Calculate dominance frontiers for the exit block

Message ID 20231024105006.3337671-6-richard.sandiford@arm.com
State New
Headers show
Series rtl-ssa: Various fixes needed for the late-combine pass | expand

Commit Message

Richard Sandiford Oct. 24, 2023, 10:50 a.m. UTC 
The exit block can have multiple predecessors, for example if the
function calls __builtin_eh_return.  We might then need PHI nodes
for values that are live on exit.

RTL-SSA uses the normal dominance frontiers approach for calculating
where PHI nodes are needed.  However, dominannce.cc only calculates
dominators for normal blocks, not the exit block.
calculate_dominance_frontiers likewise only calculates dominance
frontiers for normal blocks.

This patch fills in the “missing” frontiers manually.

gcc/
	* rtl-ssa/internals.h (build_info::exit_block_dominator): New
	member variable.
	* rtl-ssa/blocks.cc (build_info::build_info): Initialize it.
	(bb_walker::bb_walker): Use it, moving the computation of the
	dominator to...
	(function_info::process_all_blocks): ...here.
	(function_info::place_phis): Add dominance frontiers for the
	exit block.
---
 gcc/rtl-ssa/blocks.cc   | 41 ++++++++++++++++++++++++++---------------
 gcc/rtl-ssa/internals.h |  4 ++++
 2 files changed, 30 insertions(+), 15 deletions(-)

Comments

Jeff Law Oct. 24, 2023, 5:28 p.m. UTC | #1 
On 10/24/23 04:50, Richard Sandiford wrote:
> The exit block can have multiple predecessors, for example if the
> function calls __builtin_eh_return.  We might then need PHI nodes
> for values that are live on exit.
> 
> RTL-SSA uses the normal dominance frontiers approach for calculating
> where PHI nodes are needed.  However, dominannce.cc only calculates
> dominators for normal blocks, not the exit block.
> calculate_dominance_frontiers likewise only calculates dominance
> frontiers for normal blocks.
> 
> This patch fills in the “missing” frontiers manually.
> 
> gcc/
> 	* rtl-ssa/internals.h (build_info::exit_block_dominator): New
> 	member variable.
> 	* rtl-ssa/blocks.cc (build_info::build_info): Initialize it.
> 	(bb_walker::bb_walker): Use it, moving the computation of the
> 	dominator to...
> 	(function_info::process_all_blocks): ...here.
> 	(function_info::place_phis): Add dominance frontiers for the
> 	exit block.
OK
jeff
diff mbox series

Patch

diff --git a/gcc/rtl-ssa/blocks.cc b/gcc/rtl-ssa/blocks.cc
index 49c0d15b3cf..0ce798e21b7 100644
--- a/gcc/rtl-ssa/blocks.cc
+++ b/gcc/rtl-ssa/blocks.cc
@@ -47,7 +47,8 @@  function_info::build_info::build_info (unsigned int num_regs,
     potential_phi_regs (num_regs),
     bb_phis (num_bb_indices),
     bb_mem_live_out (num_bb_indices),
-    bb_to_rpo (num_bb_indices)
+    bb_to_rpo (num_bb_indices),
+    exit_block_dominator (nullptr)
 {
   last_access.safe_grow_cleared (num_regs + 1);
 
@@ -103,21 +104,8 @@  function_info::bb_walker::bb_walker (function_info *function, build_info &bi)
   : dom_walker (CDI_DOMINATORS, ALL_BLOCKS, bi.bb_to_rpo.address ()),
     m_function (function),
     m_bi (bi),
-    m_exit_block_dominator (nullptr)
+    m_exit_block_dominator (bi.exit_block_dominator)
 {
-  // ??? There is no dominance information associated with the exit block,
-  // so work out its immediate dominator using predecessor blocks.  We then
-  // walk the exit block just before popping its immediate dominator.
-  edge e;
-  edge_iterator ei;
-  FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn)->preds)
-    if (m_exit_block_dominator)
-      m_exit_block_dominator
-	= nearest_common_dominator (CDI_DOMINATORS,
-				    m_exit_block_dominator, e->src);
-    else
-      m_exit_block_dominator = e->src;
-
   // If the exit block is unreachable, process it last.
   if (!m_exit_block_dominator)
     m_exit_block_dominator = ENTRY_BLOCK_PTR_FOR_FN (m_function->m_fn);
@@ -624,6 +612,19 @@  function_info::place_phis (build_info &bi)
     bitmap_initialize (&frontiers[i], &bitmap_default_obstack);
   compute_dominance_frontiers (frontiers.address ());
 
+  // The normal dominance information doesn't calculate dominators for
+  // the exit block, so we don't get dominance frontiers for them either.
+  // Calculate them by hand.
+  for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds)
+    {
+      basic_block bb = e->src;
+      while (bb != bi.exit_block_dominator)
+	{
+	  bitmap_set_bit (&frontiers[bb->index], EXIT_BLOCK);
+	  bb = get_immediate_dominator (CDI_DOMINATORS, bb);
+	}
+    }
+
   // In extreme cases, the number of live-in registers can be much
   // greater than the number of phi nodes needed in a block (see PR98863).
   // Try to reduce the number of operations involving live-in sets by using
@@ -1264,6 +1265,16 @@  function_info::process_all_blocks ()
 
   build_info bi (m_num_regs, num_bb_indices);
 
+  // ??? There is no dominance information associated with the exit block,
+  // so work out its immediate dominator using predecessor blocks.
+  for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds)
+    if (bi.exit_block_dominator)
+      bi.exit_block_dominator
+	= nearest_common_dominator (CDI_DOMINATORS,
+				    bi.exit_block_dominator, e->src);
+    else
+      bi.exit_block_dominator = e->src;
+
   calculate_potential_phi_regs (bi);
   create_ebbs (bi);
   place_phis (bi);
diff --git a/gcc/rtl-ssa/internals.h b/gcc/rtl-ssa/internals.h
index 6ed957754e2..e65ba9fe038 100644
--- a/gcc/rtl-ssa/internals.h
+++ b/gcc/rtl-ssa/internals.h
@@ -135,6 +135,10 @@  public:
   // The top of this stack records the start of the current block's
   // section in DEF_STACK.
   auto_vec<unsigned int> old_def_stack_limit;
+
+  // The block that dominates the exit block, or null if the exit block
+  // is unreachable.
+  basic_block exit_block_dominator;
 };
 
 }