[PATCH] Speedup path discovery in predicate::use_cannot_happen

[PATCH] Speedup path discovery in predicate::use_cannot_happen

[Richard Biener]

The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that
made compute_control_dep_chain start from function entry rather
than the immediate dominator of the source block of the edge with
the undefined value on the PHI node.  Reverting at that point
does not reveal any testsuite FAIL, in particular the added
testcase still passes.  The following adjusts this to the other
function that computes predicates that hold on the PHI incoming
edges with undefined values, predicate::init_from_phi_def, which
starts at the immediate dominator of the PHI.  That's much less
likely to run into the CFG walking limit.

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

Aldy - you did this change, do you remember anything here?  In
fact the whole thing that's now called predicate::use_cannot_happen
seems to be redundant - the two testcases attributed to its history
do not fail when that's disabled, nor did they fail when it was
introduced.  In principle whats now called predicate::superset_of
should cover this (but different implementation limits might apply).

OK?

	* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
	Start the compute_control_dep_chain walk from the immediate
	dominator of the PHI.
---
 gcc/gimple-predicate-analysis.cc | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index a4291657d0b..ea81daacd4f 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -1293,6 +1293,12 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
       use_guard = &phi_use_guard_intersection;
     }
 
+  basic_block phi_bb = gimple_bb (phi);
+  /* Find the closest dominating bb to be the control dependence root.  */
+  basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
+  if (!cd_root)
+    return false;
+
   /* Look for the control dependencies of all the interesting operands
      and build guard predicates describing them.  */
   unsigned n = gimple_phi_num_args (phi);
@@ -1308,7 +1314,7 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
       unsigned num_calls = 0;
 
       /* Build the control dependency chain for the PHI argument...  */
-      if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
+      if (!compute_control_dep_chain (cd_root,
 				      e->src, dep_chains, &num_chains,
 				      cur_chain, &num_calls))
 	{
-- 
2.35.3

Re: [PATCH] Speedup path discovery in predicate::use_cannot_happen

[Richard Biener]

On Tue, 23 Aug 2022, Aldy Hernandez wrote:

> On Tue, Aug 23, 2022 at 2:16 PM Richard Biener <rguenther@suse.de> wrote:
> >
> > The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that
> > made compute_control_dep_chain start from function entry rather
> > than the immediate dominator of the source block of the edge with
> > the undefined value on the PHI node.  Reverting at that point
> > does not reveal any testsuite FAIL, in particular the added
> > testcase still passes.  The following adjusts this to the other
> > function that computes predicates that hold on the PHI incoming
> > edges with undefined values, predicate::init_from_phi_def, which
> > starts at the immediate dominator of the PHI.  That's much less
> > likely to run into the CFG walking limit.
> >
> > Bootstrapped and tested on x86_64-unknown-linux-gnu.
> >
> > Aldy - you did this change, do you remember anything here?  In
> > fact the whole thing that's now called predicate::use_cannot_happen
> > seems to be redundant - the two testcases attributed to its history
> > do not fail when that's disabled, nor did they fail when it was
> > introduced.  In principle whats now called predicate::superset_of
> > should cover this (but different implementation limits might apply).
> 
> OMG, I'm drawing a complete blank here.  I have no recollection of
> this.  I'm tempted to say either my account was hacked or that old
> code was all wrong ;-).

Eh.

Pushed then.  I'm going to baby-step changes so we can figure out
things when later bisecting regressions ...

Thanks,
Richard.

Re: [PATCH] Speedup path discovery in predicate::use_cannot_happen

[Aldy Hernandez]

On Tue, Aug 23, 2022 at 2:16 PM Richard Biener <rguenther@suse.de> wrote:
>
> The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that
> made compute_control_dep_chain start from function entry rather
> than the immediate dominator of the source block of the edge with
> the undefined value on the PHI node.  Reverting at that point
> does not reveal any testsuite FAIL, in particular the added
> testcase still passes.  The following adjusts this to the other
> function that computes predicates that hold on the PHI incoming
> edges with undefined values, predicate::init_from_phi_def, which
> starts at the immediate dominator of the PHI.  That's much less
> likely to run into the CFG walking limit.
>
> Bootstrapped and tested on x86_64-unknown-linux-gnu.
>
> Aldy - you did this change, do you remember anything here?  In
> fact the whole thing that's now called predicate::use_cannot_happen
> seems to be redundant - the two testcases attributed to its history
> do not fail when that's disabled, nor did they fail when it was
> introduced.  In principle whats now called predicate::superset_of
> should cover this (but different implementation limits might apply).

OMG, I'm drawing a complete blank here.  I have no recollection of
this.  I'm tempted to say either my account was hacked or that old
code was all wrong ;-).

Sorry.
Aldy

[PATCH] Speedup path discovery in predicate::use_cannot_happen

[Richard Biener]

The following reverts a hunk from r8-5789-g11ef0b22d68cd1 that
made compute_control_dep_chain start from function entry rather
than the immediate dominator of the source block of the edge with
the undefined value on the PHI node.  Reverting at that point
does not reveal any testsuite FAIL, in particular the added
testcase still passes.  The following adjusts this to the other
function that computes predicates that hold on the PHI incoming
edges with undefined values, predicate::init_from_phi_def, which
starts at the immediate dominator of the PHI.  That's much less
likely to run into the CFG walking limit.

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

Aldy - you did this change, do you remember anything here?  In
fact the whole thing that's now called predicate::use_cannot_happen
seems to be redundant - the two testcases attributed to its history
do not fail when that's disabled, nor did they fail when it was
introduced.  In principle whats now called predicate::superset_of
should cover this (but different implementation limits might apply).

OK?

	* gimple-predicate-analysis.cc (predicate::use_cannot_happen):
	Start the compute_control_dep_chain walk from the immediate
	dominator of the PHI.
---
 gcc/gimple-predicate-analysis.cc | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index a4291657d0b..ea81daacd4f 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -1293,6 +1293,12 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
       use_guard = &phi_use_guard_intersection;
     }
 
+  basic_block phi_bb = gimple_bb (phi);
+  /* Find the closest dominating bb to be the control dependence root.  */
+  basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
+  if (!cd_root)
+    return false;
+
   /* Look for the control dependencies of all the interesting operands
      and build guard predicates describing them.  */
   unsigned n = gimple_phi_num_args (phi);
@@ -1308,7 +1314,7 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds)
       unsigned num_calls = 0;
 
       /* Build the control dependency chain for the PHI argument...  */
-      if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
+      if (!compute_control_dep_chain (cd_root,
 				      e->src, dep_chains, &num_chains,
 				      cur_chain, &num_calls))
 	{
-- 
2.35.3