From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id E8C2338515D4; Wed, 24 Aug 2022 11:16:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E8C2338515D4 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661339764; bh=1yRkjUys8CrOF5ah1kf5j4ms9Jxcyed7QHqEq3ZNYuE=; h=From:To:Subject:Date:From; b=Hozt+RAlMGZUk3WhjGr5+2cLqe4U5iqc9nPWnrI/UejmYthzyMLVvAaKB9VutWKhI Nn39Gq/WWolFyEtPUz775OyvpxynlIukvwP0JAtdHHG9K72p40dfLjoQn3MtE0y3Y7 0bbK/lCVIppPI6RL9/7egbHDZCcycAqvVcnA7YlQ= MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Richard Biener To: gcc-cvs@gcc.gnu.org Subject: [gcc r13-2170] Split uninit analysis from predicate analysis X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: 9e50aebc813477655e0090b7de6578a7b11816ba X-Git-Newrev: cd1216d581b44f14b93a427bf2e95ee37e394b8b Message-Id: <20220824111604.E8C2338515D4@sourceware.org> Date: Wed, 24 Aug 2022 11:16:04 +0000 (GMT) List-Id: https://gcc.gnu.org/g:cd1216d581b44f14b93a427bf2e95ee37e394b8b commit r13-2170-gcd1216d581b44f14b93a427bf2e95ee37e394b8b Author: Richard Biener Date: Wed Aug 24 11:22:55 2022 +0200 Split uninit analysis from predicate analysis This splits the API collected in gimple-predicate-analysis.h into what I'd call a predicate and assorted functionality plus utility used by the uninit pass that happens to use that. I've tried to be minimalistic with refactoring, there's still recursive instantiation of uninit_analysis, the new class encapsulating a series of uninit analysis queries from the uninit pass. But it at least should make the predicate part actually reusable and what predicate is dealt with is a little bit more clear in the uninit_analysis part. I will followup with moving the predicate implementation bits together in the gimple-predicate-analysis.cc file. * gimple-predicate-analysis.h (predicate): Split out non-predicate related functionality into .. (uninit_analysis): .. this new class. * gimple-predicate-analysis.cc: Refactor into two classes. * tree-ssa-uninit.cc (find_uninit_use): Use uninit_analysis. Diff: --- gcc/gimple-predicate-analysis.cc | 116 ++++++++++++++++++++------------------- gcc/gimple-predicate-analysis.h | 101 ++++++++++++++++++++-------------- gcc/tree-ssa-uninit.cc | 6 +- 3 files changed, 121 insertions(+), 102 deletions(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index f7170a8d068..8995c11a45c 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -483,19 +483,18 @@ find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def, Checking recursively into (1), the compiler can find out that only some_val (which is defined) can flow into (3) which is OK. */ -static bool -prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, - tree boundary_cst, tree_code cmp_code, - predicate::func_t &eval, - hash_set *visited_phis, - bitmap *visited_flag_phis) +bool +uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, + tree boundary_cst, tree_code cmp_code, + hash_set *visited_phis, + bitmap *visited_flag_phis) { /* The Boolean predicate guarding the PHI definition. Initialized lazily from PHI in the first call to is_use_guarded() and cached for subsequent iterations. */ - predicate def_preds (eval); + uninit_analysis def_preds (m_eval); - unsigned n = MIN (eval.max_phi_args, gimple_phi_num_args (flag_def)); + unsigned n = MIN (m_eval.max_phi_args, gimple_phi_num_args (flag_def)); for (unsigned i = 0; i < n; i++) { if (!MASK_TEST_BIT (opnds, i)) @@ -532,9 +531,9 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result)); /* Now recursively try to prune the interesting phi args. */ - unsigned opnds_arg_phi = eval.phi_arg_set (phi_arg_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, eval, visited_phis, + boundary_cst, cmp_code, visited_phis, visited_flag_phis)) return false; @@ -554,7 +553,7 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, gimple *opnd_def = SSA_NAME_DEF_STMT (opnd); if (gphi *opnd_def_phi = dyn_cast (opnd_def)) { - unsigned opnds2 = eval.phi_arg_set (opnd_def_phi); + unsigned opnds2 = m_eval.phi_arg_set (opnd_def_phi); if (!MASK_EMPTY (opnds2)) { edge opnd_edge = gimple_phi_arg_edge (phi, i); @@ -578,9 +577,10 @@ prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def, up the CFG nodes that it's dominated by. *EDGES holds the result, and VISITED is used for detecting cycles. */ -static void -collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec *edges, - predicate::func_t &eval, hash_set *visited) +void +uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root, + vec *edges, + hash_set *visited) { if (visited->elements () == 0 && DEBUG_PREDICATE_ANALYZER @@ -607,9 +607,9 @@ collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec *edges, if (gimple_code (def) == GIMPLE_PHI && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root)) - collect_phi_def_edges (as_a (def), cd_root, edges, eval, + collect_phi_def_edges (as_a (def), cd_root, edges, visited); - else if (!eval (opnd)) + else if (!m_eval (opnd)) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -635,7 +635,7 @@ collect_phi_def_edges (gphi *phi, basic_block cd_root, auto_vec *edges, print_gimple_stmt (dump_file, phi, 0); } - if (!eval (opnd)) + if (!m_eval (opnd)) edges->safe_push (opnd_edge); } } @@ -689,7 +689,7 @@ build_pred_expr (const pred_chain_union &preds, bool invert = false) /* Return a bitset of all PHI arguments or zero if there are too many. */ unsigned -predicate::func_t::phi_arg_set (gphi *phi) +uninit_analysis::func_t::phi_arg_set (gphi *phi) { unsigned n = gimple_phi_num_args (phi); @@ -772,7 +772,8 @@ predicate::func_t::phi_arg_set (gphi *phi) checked. */ bool -predicate::overlap (gphi *phi, unsigned opnds, hash_set *visited) +uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set *visited, + const predicate &use_preds) { gimple *flag_def = NULL; tree boundary_cst = NULL_TREE; @@ -781,7 +782,7 @@ predicate::overlap (gphi *phi, unsigned opnds, hash_set *visited) /* Find within the common prefix of multiple predicate chains a predicate that is a comparison of a flag variable against a constant. */ - tree_code cmp_code = find_var_cmp_const (m_preds, phi, &flag_def, + tree_code cmp_code = find_var_cmp_const (use_preds.chain (), phi, &flag_def, &boundary_cst); if (cmp_code == ERROR_MARK) return true; @@ -790,7 +791,7 @@ predicate::overlap (gphi *phi, unsigned opnds, hash_set *visited) value that is in conflict with the use guard/predicate. */ gphi *phi_def = as_a (flag_def); bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst, - cmp_code, m_eval, visited, + cmp_code, visited, &visited_flag_phis); if (visited_flag_phis) @@ -1255,7 +1256,7 @@ can_be_invalidated_p (const pred_chain_union &preds, const pred_chain &guard) the use guards in *THIS that guard the PHI's use. */ bool -predicate::use_cannot_happen (gphi *phi, unsigned opnds) +uninit_analysis::use_cannot_happen (gphi *phi, unsigned opnds, const predicate &use_preds) { if (!m_eval.phi_arg_set (phi)) return false; @@ -1264,22 +1265,22 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) possible guard, there's no way of knowing which guard was true. In that case compute the intersection of all use predicates and use that. */ - const pred_chain_union &phi_use_guards = m_preds; - const pred_chain *use_guard = &phi_use_guards[0]; + const predicate &phi_use_guards = use_preds; + const pred_chain *use_guard = &phi_use_guards.chain() [0]; pred_chain phi_use_guard_intersection = vNULL; - if (phi_use_guards.length () != 1) + if (phi_use_guards.chain ().length () != 1) { phi_use_guard_intersection = use_guard->copy (); - for (unsigned i = 1; i < phi_use_guards.length (); ++i) + for (unsigned i = 1; i < phi_use_guards.chain ().length (); ++i) { for (unsigned j = 0; j < phi_use_guard_intersection.length ();) { unsigned k; - for (k = 0; k < phi_use_guards[i].length (); ++k) - if (pred_equal_p (phi_use_guards[i][k], + for (k = 0; k < phi_use_guards.chain ()[i].length (); ++k) + if (pred_equal_p (phi_use_guards.chain ()[i][k], phi_use_guard_intersection[j])) break; - if (k == phi_use_guards[i].length ()) + if (k == phi_use_guards.chain ()[i].length ()) phi_use_guard_intersection.unordered_remove (j); else j++; @@ -1341,7 +1342,7 @@ predicate::use_cannot_happen (gphi *phi, unsigned opnds) /* ...and convert it into a set of predicates guarding its definition. */ - predicate def_preds (m_eval); + predicate def_preds; def_preds.init_from_control_deps (dep_chains, num_chains); if (def_preds.is_empty ()) /* If there's no predicate there's no basis to rule the use out. */ @@ -1745,13 +1746,16 @@ predicate::dump (gimple *stmt, const char *msg) const fputc ('\n', dump_file); } -/* Initialize *THIS with the predicates of the control dependence chains +/* Initialize USE_PREDS with the predicates of the control dependence chains between the basic block DEF_BB that defines a variable of interst and USE_BB that uses the variable, respectively. */ -predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval) - : m_preds (vNULL), m_eval (eval) +bool +uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb, + basic_block use_bb) { + gcc_assert (use_preds.is_empty ()); + /* Set CD_ROOT to the basic block closest to USE_BB that is the control equivalent of (is guarded by the same predicate as) DEF_BB that also dominates USE_BB. */ @@ -1799,7 +1803,8 @@ predicate::predicate (basic_block def_bb, basic_block use_bb, func_t &eval) condition under which the definition in DEF_BB is used in USE_BB. Each OR subexpression is represented by one element of DEP_CHAINS, where each element consists of a series of AND subexpressions. */ - init_from_control_deps (dep_chains, num_chains); + use_preds.init_from_control_deps (dep_chains, num_chains); + return !use_preds.is_empty (); } /* Release resources in *THIS. */ @@ -1820,9 +1825,6 @@ predicate::operator= (const predicate &rhs) if (this == &rhs) return *this; - /* FIXME: Make this a compile-time constraint? */ - gcc_assert (&m_eval == &rhs.m_eval); - unsigned n = m_preds.length (); for (unsigned i = 0; i != n; ++i) m_preds[i].release (); @@ -1843,9 +1845,9 @@ predicate::operator= (const predicate &rhs) Return true if a nonempty predicate has been obtained. */ bool -predicate::init_from_phi_def (gphi *phi) +uninit_analysis::init_from_phi_def (gphi *phi) { - gcc_assert (is_empty ()); + gcc_assert (m_phi_def_preds.is_empty ()); basic_block phi_bb = gimple_bb (phi); /* Find the closest dominating bb to be the control dependence root. */ @@ -1857,7 +1859,7 @@ predicate::init_from_phi_def (gphi *phi) definitions of each of the PHI operands for which M_EVAL is false. */ auto_vec def_edges; hash_set visited_phis; - collect_phi_def_edges (phi, cd_root, &def_edges, m_eval, &visited_phis); + collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis); unsigned nedges = def_edges.length (); if (nedges == 0) @@ -1887,8 +1889,8 @@ predicate::init_from_phi_def (gphi *phi) /* Convert control dependence chains to the predicate in *THIS under which the PHI operands are defined to values for which M_EVAL is false. */ - init_from_control_deps (dep_chains, num_chains); - return !is_empty (); + m_phi_def_preds.init_from_control_deps (dep_chains, num_chains); + return !m_phi_def_preds.is_empty (); } /* Compute the predicates that guard the use USE_STMT and check if @@ -1911,9 +1913,9 @@ predicate::init_from_phi_def (gphi *phi) VISITED_PHIS is a pointer set of phis being visited. */ bool -predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb, - gphi *phi, unsigned opnds, - hash_set *visited) +uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb, + gphi *phi, unsigned opnds, + hash_set *visited) { if (visited->add (phi)) return false; @@ -1928,12 +1930,12 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb, /* Try to build the predicate expression under which the PHI flows into its use. This will be empty if the PHI is defined and used in the same bb. */ - predicate use_preds (def_bb, use_bb, m_eval); - if (use_preds.is_empty ()) + predicate use_preds; + if (!init_use_preds (use_preds, def_bb, use_bb)) return false; /* Try to prune the dead incoming phi edges. */ - if (!use_preds.overlap (phi, opnds, visited)) + if (!overlap (phi, opnds, visited, use_preds)) { if (DEBUG_PREDICATE_ANALYZER && dump_file) fputs ("found predicate overlap\n", dump_file); @@ -1943,17 +1945,17 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb, /* We might be able to prove that if the control dependencies for OPNDS are true, the control dependencies for USE_STMT can never be true. */ - if (use_preds.use_cannot_happen (phi, opnds)) + if (use_cannot_happen (phi, opnds, use_preds)) return true; - if (is_empty ()) + if (m_phi_def_preds.is_empty ()) { /* Lazily initialize *THIS from PHI. */ if (!init_from_phi_def (phi)) return false; - simplify (phi); - normalize (phi); + m_phi_def_preds.simplify (phi); + m_phi_def_preds.normalize (phi); } use_preds.simplify (use_stmt, /*is_use=*/true); @@ -1962,7 +1964,7 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb, /* Return true if the predicate guarding the valid definition (i.e., *THIS) is a superset of the predicate guarding the use (i.e., USE_PREDS). */ - if (superset_of (use_preds)) + if (m_phi_def_preds.superset_of (use_preds)) return true; return false; @@ -1971,8 +1973,8 @@ predicate::is_use_guarded (gimple *use_stmt, basic_block use_bb, /* Public interface to the above. */ bool -predicate::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi, - unsigned opnds) +uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi, + unsigned opnds) { hash_set visited; return is_use_guarded (stmt, use_bb, phi, opnds, &visited); @@ -2141,7 +2143,7 @@ predicate::normalize (const pred_chain &chain) while (!work_list.is_empty ()) { pred_info pi = work_list.pop (); - predicate pred (m_eval); + predicate pred; /* The predicate object is not modified here, only NORM_CHAIN and WORK_LIST are appended to. */ pred.normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set); @@ -2162,7 +2164,7 @@ predicate::normalize (gimple *use_or_def, bool is_use) dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n"); } - predicate norm_preds (m_eval); + predicate norm_preds; for (unsigned i = 0; i < m_preds.length (); i++) { if (m_preds[i].length () != 1) diff --git a/gcc/gimple-predicate-analysis.h b/gcc/gimple-predicate-analysis.h index 77672291c36..b4aa5de7e7b 100644 --- a/gcc/gimple-predicate-analysis.h +++ b/gcc/gimple-predicate-analysis.h @@ -44,37 +44,11 @@ typedef vec pred_chain_union; class predicate { public: - /* Base function object type used to determine whether an expression - is of interest. */ - struct func_t - { - typedef unsigned phi_arg_set_t; - - /* Return true if the argument is an expression of interest. */ - virtual bool operator()(tree) = 0; - /* Return a bitset of PHI arguments of interest. By default returns - bitset with a bit set for each argument. Should be called in - the overriden function first and, if nonzero, the result then - refined as appropriate. */ - virtual phi_arg_set_t phi_arg_set (gphi *); - - /* Maximum number of PHI arguments supported by phi_arg_set(). */ - static constexpr unsigned max_phi_args = - sizeof (phi_arg_set_t) * CHAR_BIT; - }; - /* Construct with the specified EVAL object. */ - predicate (func_t &eval) - : m_preds (vNULL), m_eval (eval) { } + predicate () : m_preds (vNULL) { } /* Copy. */ - predicate (const predicate &rhs) - : m_preds (vNULL), m_eval (rhs.m_eval) - { - *this = rhs; - } - - predicate (basic_block, basic_block, func_t &); + predicate (const predicate &rhs) : m_preds (vNULL) { *this = rhs; } ~predicate (); @@ -91,10 +65,6 @@ class predicate return m_preds; } - /* Return true if the use by a statement in the basic block of - a PHI operand is ruled out (i.e., guarded) by *THIS. */ - bool is_use_guarded (gimple *, basic_block, gphi *, unsigned); - void init_from_control_deps (const vec *, unsigned); void dump (gimple *, const char *) const; @@ -102,23 +72,16 @@ class predicate void normalize (gimple * = NULL, bool = false); void simplify (gimple * = NULL, bool = false); - bool is_use_guarded (gimple *, basic_block, gphi *, unsigned, - hash_set *); - -private: - bool includes (const pred_chain &) const; bool superset_of (const predicate &) const; - bool overlap (gphi *, unsigned, hash_set *); - bool use_cannot_happen (gphi *, unsigned); - bool init_from_phi_def (gphi *); +private: + bool includes (const pred_chain &) const; void push_pred (const pred_info &); /* Normalization functions. */ void normalize (pred_chain *, pred_info, tree_code, pred_chain *, hash_set *); - void normalize (const pred_info &); void normalize (const pred_chain &); @@ -127,9 +90,63 @@ private: bool simplify_3 (); bool simplify_4 (); -private: /* Representation of the predicate expression(s). */ pred_chain_union m_preds; +}; + +/* Represents a complex Boolean predicate expression. */ +class uninit_analysis +{ + public: + /* Base function object type used to determine whether an expression + is of interest. */ + struct func_t + { + typedef unsigned phi_arg_set_t; + + /* Return true if the argument is an expression of interest. */ + virtual bool operator()(tree) = 0; + /* Return a bitset of PHI arguments of interest. By default returns + bitset with a bit set for each argument. Should be called in + the overriden function first and, if nonzero, the result then + refined as appropriate. */ + virtual phi_arg_set_t phi_arg_set (gphi *); + + /* Maximum number of PHI arguments supported by phi_arg_set(). */ + static constexpr unsigned max_phi_args = + sizeof (phi_arg_set_t) * CHAR_BIT; + }; + + /* Construct with the specified EVAL object. */ + uninit_analysis (func_t &eval) + : m_phi_def_preds (), m_eval (eval) { } + + /* Copy. */ + uninit_analysis (const uninit_analysis &rhs) = delete; + + /* Assign. */ + uninit_analysis& operator= (const uninit_analysis&) = delete; + + /* Return true if the use by a statement in the basic block of + a PHI operand is ruled out (i.e., guarded) by *THIS. */ + bool is_use_guarded (gimple *, basic_block, gphi *, unsigned); + +private: + bool is_use_guarded (gimple *, basic_block, gphi *, unsigned, + hash_set *); + bool prune_phi_opnds (gphi *, unsigned, gphi *, tree, tree_code, + hash_set *, bitmap *); + bool overlap (gphi *, unsigned, hash_set *, const predicate &); + bool use_cannot_happen (gphi *, unsigned, const predicate &); + + void collect_phi_def_edges (gphi *, basic_block, vec *, + hash_set *); + bool init_from_phi_def (gphi *); + bool init_use_preds (predicate &, basic_block, basic_block); + + + /* Representation of the predicate expression(s). */ + predicate m_phi_def_preds; /* Callback to evaluate an operand. Return true if it's interesting. */ func_t &m_eval; }; diff --git a/gcc/tree-ssa-uninit.cc b/gcc/tree-ssa-uninit.cc index 7074c9117b2..450ff0fd062 100644 --- a/gcc/tree-ssa-uninit.cc +++ b/gcc/tree-ssa-uninit.cc @@ -1111,7 +1111,7 @@ compute_uninit_opnds_pos (gphi *phi) unsigned n = gimple_phi_num_args (phi); /* Bail out for phi with too many args. */ - if (n > predicate::func_t::max_phi_args) + if (n > uninit_analysis::func_t::max_phi_args) return 0; for (unsigned i = 0; i < n; ++i) @@ -1137,7 +1137,7 @@ compute_uninit_opnds_pos (gphi *phi) /* Function object type used to determine whether an expression is of interest to the predicate analyzer. */ -struct uninit_undef_val_t: public predicate::func_t +struct uninit_undef_val_t: public uninit_analysis::func_t { virtual bool operator()(tree) override; virtual unsigned phi_arg_set (gphi *) override; @@ -1179,7 +1179,7 @@ find_uninit_use (gphi *phi, unsigned uninit_opnds, lazily from PHI in the first call to is_use_guarded() and cached for subsequent iterations. */ uninit_undef_val_t eval; - predicate def_preds (eval); + uninit_analysis def_preds (eval); use_operand_p use_p; imm_use_iterator iter;