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

dom_oracle::register_transitives contains an unbound dominator walk
which for the testcase in PR114855 dominates the profile.  The following
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 also amended the guard to register_transitives with the
per-basic-block limit for the number of relations registered not
being exhausted.

	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):
	Assing an overall work budget, bounding the dominator walk and
	the number of relations processed.
	(dom_oracle::record): Only register_transitives when the
	number of already registered relations does not yet exceed
	the per-BB limit.

3 files changed, 44 insertions, 18 deletions

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index bdbbea5..bd1208a 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 949b475..a08e4c1 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 d6ad2dd..d8a2ed9 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -1093,7 +1093,9 @@ dom_oracle::record (basic_block bb, relation_kind k, tree op1, tree op2)
       bool check = bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op1))
 		   || bitmap_bit_p (m_relation_set, SSA_NAME_VERSION (op2));
       relation_chain *ptr = set_one_relation (bb, k, op1, op2);
-      if (ptr && check)
+      if (ptr && check
+	  && (m_relations[bb->index].m_num_relations
+	      < param_relation_block_limit))
 	register_transitives (bb, *ptr);
     }
 }
@@ -1204,7 +1206,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 +1255,38 @@ 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))
+	      // 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))
 		{
-		  fprintf (dump_file, "   Registering transitive relation ");
-		  nr.dump (dump_file);
-		  fputc ('\n', dump_file);
+		  // If the new relation is already present we know any
+		  // further processing is already reflected above it.
+		  // When we ran into the limit of relations on root_bb
+		  // we can give up as well.
+		  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);
+		    }
 		}
 	    }
-
+	  /* Processed one relation, abort if we've eaten up our budget.  */
+	  if (--avail_budget == 0)
+	    return;
 	}
     }
 }