diff mbox series

tree-optimization/114855 - speed up dom_oracle::register_transitives

Message ID 20240925105207.D881B3858C31@sourceware.org
State New
Headers show
Series tree-optimization/114855 - speed up dom_oracle::register_transitives | expand

Commit Message

Richard Biener Sept. 25, 2024, 10:51 a.m. UTC 
dom_oracle::register_transitives contains an unbound dominator walk
which for the testcase in PR114855 dominates the profile.  I've also
noticed odd behavior in the case when set_one_relation returns NULL,
we'd then completely abort processing other relations.  The following
fixes the latter by continuing searching and fixes the unbound work
done by assigning a constant work budget to the loop, bounding the
number of dominators visited but also the number of relations
processed.  This gets both dom_oracle::register_transitives and
get_immediate_dominator off the profile.

I'll note that we're still doing an unbound dominator walk via
equiv_set in find_equiv_dom at the start of the function and when
we register a relation that also looks up the same way.  At least
for the testcase at hand this isn't an issue.

I've wondered whether instead of having a per-BB bitmap of names
we have a relation for in that BB having a bitmap per SSA name of
which BBs have a relation for it would be a way to avoid all those
walks.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

OK for trunk?

Thanks,
Richard.

	PR tree-optimization/114855
	* params.opt (--param transitive-relations-work-bound): New.
	* doc/invoke.texi (--param transitive-relations-work-bound):
	Document.
	* value-relation.cc (dom_oracle::register_transitives):
	Do not stop processing relations when a registration attempt
	did not register a new relation.  Assing an overall work
	budget, bounding the dominator walk and the number of
	relations processed.
---
 gcc/doc/invoke.texi   |  3 +++
 gcc/params.opt        |  4 ++++
 gcc/value-relation.cc | 47 ++++++++++++++++++++++++++-----------------
 3 files changed, 35 insertions(+), 19 deletions(-)
diff mbox series

Patch

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index bdbbea53666..bd1208a62ee 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -17144,6 +17144,9 @@  in the outgoing range calculator.
 @item relation-block-limit
 Maximum number of relations the oracle will register in a basic block.
 
+@item transitive-relations-work-bound
+Work bound when discovering transitive relations from existing relations.
+
 @item min-pagesize
 Minimum page size for warning purposes.
 
diff --git a/gcc/params.opt b/gcc/params.opt
index 949b4754498..a08e4c1042d 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -924,6 +924,10 @@  outgoing range calculator.
 Common Joined UInteger Var(param_relation_block_limit) Init(200) IntegerRange(0, 9999) Param Optimization
 Maximum number of relations the oracle will register in a basic block.
 
+-param=transitive-relations-work-bound=
+Common Joined UInteger Var(param_transitive_relations_work_bound) Init(256) IntegerRange(0, 9999) Param Optimization
+Work bound when discovering transitive relations from existing relations.
+
 -param=rpo-vn-max-loop-depth=
 Common Joined UInteger Var(param_rpo_vn_max_loop_depth) Init(7) IntegerRange(2, 65536) Param Optimization
 Maximum depth of a loop nest to fully value-number optimistically.
diff --git a/gcc/value-relation.cc b/gcc/value-relation.cc
index d6ad2dd984f..b01e2953188 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1204,7 +1204,13 @@  dom_oracle::register_transitives (basic_block root_bb,
   const_bitmap equiv1 = equiv_set (relation.op1 (), root_bb);
   const_bitmap equiv2 = equiv_set (relation.op2 (), root_bb);
 
-  for (bb = root_bb; bb; bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+  const unsigned work_budget = param_transitive_relations_work_bound;
+  unsigned avail_budget = work_budget;
+  for (bb = root_bb; bb;
+       /* Advancing to the next immediate dominator eats from the budget,
+	  if none is left after that there's no point to continue.  */
+       bb = (--avail_budget > 0
+	     ? get_immediate_dominator (CDI_DOMINATORS, bb) : nullptr))
     {
       int bbi = bb->index;
       if (bbi >= (int)m_relations.length())
@@ -1247,27 +1253,30 @@  dom_oracle::register_transitives (basic_block root_bb,
 
 	  // Ignore if both NULL (not relevant relation) or the same,
 	  if (r1 == r2)
-	    continue;
+	    ;
 
-	  // Any operand not an equivalence, just take the real operand.
-	  if (!r1)
-	    r1 = relation.op1 ();
-	  if (!r2)
-	    r2 = relation.op2 ();
-
-	  value_relation nr (relation.kind (), r1, r2);
-	  if (nr.apply_transitive (*ptr))
+	  else
 	    {
-	      if (!set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ()))
-		return;
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		{
-		  fprintf (dump_file, "   Registering transitive relation ");
-		  nr.dump (dump_file);
-		  fputc ('\n', dump_file);
-		}
+	      // Any operand not an equivalence, just take the real operand.
+	      if (!r1)
+		r1 = relation.op1 ();
+	      if (!r2)
+		r2 = relation.op2 ();
+
+	      value_relation nr (relation.kind (), r1, r2);
+	      if (nr.apply_transitive (*ptr)
+		  && set_one_relation (root_bb, nr.kind (),
+				       nr.op1 (), nr.op2 ()))
+		if (dump_file && (dump_flags & TDF_DETAILS))
+		  {
+		    fprintf (dump_file, "   Registering transitive relation ");
+		    nr.dump (dump_file);
+		    fputc ('\n', dump_file);
+		  }
 	    }
-
+	  /* Processed one relation, abort if we've eaten up our budget.  */
+	  if (--avail_budget == 0)
+	    return;
 	}
     }
 }