diff mbox series

[COMMITTED,2/2] Resolve complicated join nodes in range_from_dom.

Message ID 61469f5a-5706-c7b4-50ea-a83b6cec27e8@redhat.com
State New
Headers show
Series [COMMITTED,1/2] Remove recursion from range_from_dom. | expand

Commit Message

Andrew MacLeod July 19, 2022, 10:11 p.m. UTC 
The main time a dominator search in the cache fails to produce an 
accurate range is when we have a "complicated" join node.

ie

bb4:
    if (a > 200) goto bb5 ; else goto bb9
bb5
    if (b > 400) goto bb6 ; else goto bb7
bb6
    foo (b)
bb7
    onward()
    goto bb200;
bb9:
   if (b > 200) goto bb6; else goto bb200

in this case bb6  is a complicated join node by ranger standards. It has 
2 incoming edges which carry range information for b:
    9->6 has [201, +INF] and
    5->6 has[401, +INF]
The immediate dominator of bb6 is bb4.  When asking bb6 for a range from 
its dominator, there is no sign of any outgoing ranges for b, and 
range_from_dom would simply return VARYING.

This patch tweaks range_from_dom()  so that we calculate the range for 
any block in which either
   1) The dominator has an outgoing range    (this was the old behaviour 
only)
   2) The current block sees an outgoing range on an incoming edge.
The addition of 2) allows us to capture the above case with minimal cost 
which gets use very very close to the results from the old style full 
cache value propagation.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  pushed.

Andrew
diff mbox series

Patch

From dbb093f4f15ea66f2ce5cd2dc1903a6894563356 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 18 Jul 2022 15:04:23 -0400
Subject: [PATCH 2/2] Resolve complicated join nodes in range_from_dom.

Join nodes which carry outgoing ranges on incoming edges are uncommon,
but can still be resolved by setting the dominator range, and then
calculating incoming edges.  Avoid doing so if one of the incoing edges
is not dominated by the same dominator.

	* gimple-range-cache.cc (ranger_cache::range_from_dom): Check
	  for incoming ranges on join nodes and add to worklist.
---
 gcc/gimple-range-cache.cc | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 20dd5ead3bc..f3292fccaee 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1384,6 +1384,32 @@  ranger_cache::range_from_dom (vrange &r, tree name, basic_block start_bb,
       // This block has an outgoing range.
       if (m_gori.has_edge_range_p (name, bb))
 	m_workback.quick_push (prev_bb);
+      else
+	{
+	  // Normally join blocks don't carry any new range information on
+	  // incoming edges.  If the first incoming edge to this block does
+	  // generate a range, calculate the ranges if all incoming edges
+	  // are also dominated by the dominator.  (Avoids backedges which
+	  // will break the rule of moving only upward in the domniator tree).
+	  // If the first pred does not generate a range, then we will be
+	  // using the dominator range anyway, so thats all the check needed.
+	  if (EDGE_COUNT (prev_bb->preds) > 1
+	      && m_gori.has_edge_range_p (name, EDGE_PRED (prev_bb, 0)->src))
+	    {
+	      edge e;
+	      edge_iterator ei;
+	      bool all_dom = true;
+	      FOR_EACH_EDGE (e, ei, prev_bb->preds)
+		if (e->src != bb
+		    && !dominated_by_p (CDI_DOMINATORS, e->src, bb))
+		  {
+		    all_dom = false;
+		    break;
+		  }
+	      if (all_dom)
+		m_workback.quick_push (prev_bb);
+	    }
+	}
 
       if (def_bb == bb)
 	break;
-- 
2.36.1