The testcase in this PR shows, on the GCC 14 branch, that in some
degenerate cases we can spend exponential time pruning always
initialized paths through a web of PHIs. The following adds
--param uninit-max-prune-work, defaulted to 100000, to limit that
to effectively O(1).
Bootstrap and regtest running on x86_64-unknown-linux-gnu.
Note the issue only reproduces on the GCC 14 branch, GCC 15 and
trunk are fine (though the code is exponential everywhere).
PR tree-optimization/120729
* gimple-predicate-analysis.h (uninit_analysis::prune_phi_opnds):
Add argument of work budget remaining.
* gimple-predicate-analysis.cc (uninit_analysis::prune_phi_opnds):
Likewise. Maintain and honor it throughout the recursion.
* params.opt (uninit-max-prune-work): New.
* doc/invoke.texi (uninit-max-prune-work): Document.
---
gcc/doc/invoke.texi | 3 +++
gcc/gimple-predicate-analysis.cc | 12 +++++++++---
gcc/gimple-predicate-analysis.h | 2 +-
gcc/params.opt | 4 ++++
4 files changed, 17 insertions(+), 4 deletions(-)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index dec3c7a1b80..91b0a201e1b 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -17420,6 +17420,9 @@ predicate chain.
@item uninit-max-num-chains
Maximum number of predicates ored in the normalized predicate chain.
+@item uninit-max-prune-work
+Maximum amount of work done to prune paths where the variable is always
initialized.
+
@item sched-autopref-queue-depth
Hardware autoprefetcher scheduler model control flag.
Number of lookahead cycles the model looks into; at '
diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc
index 76f6ab61310..b056b42a17e 100644
--- a/gcc/gimple-predicate-analysis.cc
+++ b/gcc/gimple-predicate-analysis.cc
@@ -385,7 +385,8 @@ bool
uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
tree boundary_cst, tree_code cmp_code,
hash_set<gphi *> *visited_phis,
- bitmap *visited_flag_phis)
+ bitmap *visited_flag_phis,
+ unsigned &max_attempts)
{
/* The Boolean predicate guarding the PHI definition. Initialized
lazily from PHI in the first call to is_use_guarded() and cached
@@ -398,6 +399,10 @@ uninit_analysis::prune_phi_opnds (gphi *phi, unsigned
opnds, gphi *flag_def,
if (!MASK_TEST_BIT (opnds, i))
continue;
+ if (max_attempts == 0)
+ return false;
+ --max_attempts;
+
tree flag_arg = gimple_phi_arg_def (flag_def, i);
if (!is_gimple_constant (flag_arg))
{
@@ -432,7 +437,7 @@ uninit_analysis::prune_phi_opnds (gphi *phi, unsigned
opnds, gphi *flag_def,
unsigned opnds_arg_phi = m_eval.phi_arg_set (phi_arg_def);
if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def,
boundary_cst, cmp_code, visited_phis,
- visited_flag_phis))
+ visited_flag_phis, max_attempts))
return false;
bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
@@ -634,9 +639,10 @@ uninit_analysis::overlap (gphi *phi, unsigned opnds,
hash_set<gphi *> *visited,
value that is in conflict with the use guard/predicate. */
bitmap visited_flag_phis = NULL;
gphi *phi_def = as_a<gphi *> (flag_def);
+ unsigned max_attempts = param_uninit_max_prune_work;
bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst,
cmp_code, visited,
- &visited_flag_phis);
+ &visited_flag_phis, max_attempts);
if (visited_flag_phis)
BITMAP_FREE (visited_flag_phis);
if (all_pruned)
diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h
index f71061ec283..67a19aa0905 100644
--- a/gcc/gimple-predicate-analysis.h
+++ b/gcc/gimple-predicate-analysis.h
@@ -152,7 +152,7 @@ private:
bool is_use_guarded (gimple *, basic_block, gphi *, unsigned,
hash_set<gphi *> *);
bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code,
- hash_set<gphi *> *, bitmap *);
+ hash_set<gphi *> *, bitmap *, unsigned &);
bool overlap (gphi *, unsigned, hash_set<gphi *> *, const predicate &);
void collect_phi_def_edges (gphi *, basic_block, vec<edge> *,
diff --git a/gcc/params.opt b/gcc/params.opt
index a67f900a63f..31aa0bd5753 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -1185,6 +1185,10 @@ predicate chain.
Common Joined UInteger Var(param_uninit_max_num_chains) Init(8)
IntegerRange(1, 128) Param Optimization
Maximum number of predicates ored in the normalized predicate chain.
+-param=uninit-max-prune-work=
+Common Joined UInteger Var(param_uninit_max_prune_work) Init(100000) Param
Optimization
+Maximum amount of work done to prune paths where the variable is always
initialized.
+
-param=uninlined-function-insns=
Common Joined UInteger Var(param_uninlined_function_insns) Init(2)
Optimization IntegerRange(0, 1000000) Param
Instruction accounted for function prologue, epilogue and other overhead.
--
2.43.0
