tree-optimization/104038 - Limit the number of relations registered per basic block.
Commit Message
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
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
>
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.
@@ -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'
@@ -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.
@@ -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 ");
@@ -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;
};