diff mbox series

tree-optimization/104038 - Limit the number of relations registered per basic block.

Message ID 665ba9fb-f543-1ed6-b54d-fea57dda1dd8@redhat.com
State New
Headers show
Series tree-optimization/104038 - Limit the number of relations registered per basic block. | expand

Commit Message

Andrew MacLeod Jan. 17, 2022, 7:55 p.m. UTC 
As mentioned in the PR, this demonstrates the potentially quadratic 
performance behaviour of adding transitive relations over a series of 
cascading calculations.

As the lookup in a basic block is also linear in nature, I think for 
this release it makes sense to simply limit the number of relations we 
can register in any given block.

I compiled all the c++ files in gcc, and there was only one BB in 
fold-const that had more than 30 relations.. and it was a smaller case 
of this sort of transitive behaviour..  and it capped out at 120 relations.

I added a new --param, and defaulted it to 200.  It has a range of 
0-9999, choosing 0 would in effect turn off relations.. which is also 
handy.  Caveat: this flag does not affect equivalences since they are 
processed in a completely different way.

I ran the testcase with the max 9999 and it finished fine.

I couldn't create  a simple/smallish testcase to run, so I didn't 
include one.

Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk?

Andrew

Comments

Richard Biener Jan. 18, 2022, 8:46 a.m. UTC | #1 
On Mon, Jan 17, 2022 at 8:56 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> As mentioned in the PR, this demonstrates the potentially quadratic
> performance behaviour of adding transitive relations over a series of
> cascading calculations.
>
> As the lookup in a basic block is also linear in nature, I think for
> this release it makes sense to simply limit the number of relations we
> can register in any given block.
>
> I compiled all the c++ files in gcc, and there was only one BB in
> fold-const that had more than 30 relations.. and it was a smaller case
> of this sort of transitive behaviour..  and it capped out at 120 relations.
>
> I added a new --param, and defaulted it to 200.  It has a range of
> 0-9999, choosing 0 would in effect turn off relations.. which is also
> handy.  Caveat: this flag does not affect equivalences since they are
> processed in a completely different way.
>
> I ran the testcase with the max 9999 and it finished fine.
>
> I couldn't create  a simple/smallish testcase to run, so I didn't
> include one.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions. OK for trunk?

OK.

Thanks,
Richard.

> Andrew
>
diff mbox series

Patch

commit 33149a818e8ef25691a159b6f7903c982b22b541
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Jan 17 12:03:18 2022 -0500

    Limit the number of relations registered per basic block.
    
    In pathological cases, the number of transitive relations being added is
    potentially quadratic.  Lookups for relations in a block is linear in
    nature, so simply limit the number of relations to some reasonable number.
    
            PR tree-optimization/104038
            * doc/invoke.texi (relation-block-limit): New.
            * params.opt (relation-block-limit): New.
            * value-relation.cc (dom_oracle::register_relation): Check for NULL
            record before invoking transitive registery.
            (dom_oracle::set_one_relation): Check limit before creating record.
            (dom_oracle::register_transitives): Stop when no record created.
            * value-relation.h (relation_chain_head::m_num_relations): New.

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 7f2205e4a85..106f535dc51 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -15088,6 +15088,9 @@  per supernode, before terminating analysis.
 Maximum depth of logical expression evaluation ranger will look through
 when evaluating outgoing edge ranges.
 
+@item relation-block-limit
+Maximum number of relations the oracle will register in a basic block.
+
 @item openacc-kernels
 Specify mode of OpenACC `kernels' constructs handling.
 With @option{--param=openacc-kernels=decompose}, OpenACC `kernels'
diff --git a/gcc/params.opt b/gcc/params.opt
index 665071fbed1..b07663daa05 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -915,6 +915,10 @@  Common Joined UInteger Var(param_ranger_logical_depth) Init(6) IntegerRange(1, 9
 Maximum depth of logical expression evaluation ranger will look through when
 evaluating outgoing edge ranges.
 
+-param=relation-block-limit=
+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=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 1e495bdf94c..32ca693c464 100644
--- a/gcc/value-relation.cc
+++ b/gcc/value-relation.cc
@@ -889,13 +889,14 @@  dom_oracle::register_relation (basic_block bb, relation_kind k, tree op1,
   else
     {
       relation_chain *ptr = set_one_relation (bb, k, op1, op2);
-      register_transitives (bb, *ptr);
+      if (ptr)
+	register_transitives (bb, *ptr);
     }
 }
 
 // Register relation K between OP! and OP2 in block BB.
 // This creates the record and searches for existing records in the dominator
-// tree to merge with.
+// tree to merge with.  Return the record, or NULL if no record was created.
 
 relation_chain *
 dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
@@ -940,6 +941,13 @@  dom_oracle::set_one_relation (basic_block bb, relation_kind k, tree op1,
     }
   else
     {
+      if (m_relations[bbi].m_num_relations >= param_relation_block_limit)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  Not registered due to bb being full\n");
+	  return NULL;
+	}
+      m_relations[bbi].m_num_relations++;
       // Check for an existing relation further up the DOM chain.
       // By including dominating relations, The first one found in any search
       // will be the aggregate of all the previous ones.
@@ -1040,7 +1048,8 @@  dom_oracle::register_transitives (basic_block root_bb,
 	  value_relation nr (relation.kind (), r1, r2);
 	  if (nr.apply_transitive (*ptr))
 	    {
-	      set_one_relation (root_bb, nr.kind (), nr.op1 (), nr.op2 ());
+	      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 ");
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index 207defa4b8e..44d0796d939 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -157,6 +157,7 @@  class relation_chain_head
 public:
   bitmap m_names;		// ssa_names with relations in this block.
   class relation_chain *m_head; // List of relations in block.
+  int m_num_relations;		// Number of relations in block.
   relation_kind find_relation (const_bitmap b1, const_bitmap b2) const;
 };