From patchwork Wed Aug 24 11:15:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 56974 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 488C7385417F for ; Wed, 24 Aug 2022 11:15:50 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 488C7385417F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661339750; bh=/GcNxpyX/5wGgm7z3OvRQOJWIubjyPGRMKS7mnXs8Ew=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=wmLFpG1B8ZL3XULbyt1wKZ8KsBYVhdExfzeaipA789KEswIvr703Tbs3lkYIYS5xy L11EzL0wJ3o7C1odQcxdBaVHFqHnFOfSr1mcFDXN1//I36yvYJPo1o0qIyzGdceUno TqpxbBvhXa2MY1B/a6cFePYsB98Zg2h/jdqMPmYs= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out1.suse.de (smtp-out1.suse.de [195.135.220.28]) by sourceware.org (Postfix) with ESMTPS id 650BA385115D for ; Wed, 24 Aug 2022 11:15:18 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 650BA385115D Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out1.suse.de (Postfix) with ESMTPS id 47AFE226D9 for ; Wed, 24 Aug 2022 11:15:17 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 314FC13780 for ; Wed, 24 Aug 2022 11:15:17 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id XdLdCkUIBmPCLwAAMHmgww (envelope-from ) for ; Wed, 24 Aug 2022 11:15:17 +0000 Date: Wed, 24 Aug 2022 13:15:16 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH 1/2] Split uninit analysis from predicate analysis MIME-Version: 1.0 Message-Id: <20220824111517.314FC13780@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" 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. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * 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. --- 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; From patchwork Wed Aug 24 11:15:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 56975 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 07C543852771 for ; Wed, 24 Aug 2022 11:16:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 07C543852771 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661339812; bh=4po1gh+zUqrKawALRKBh2qZmoO76aryYJhgwRPiaeuo=; h=Date:To:Subject:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=va5tFHoiLQG27LNKclaA/jA0gxch9k3TXzxkG1akBSYbSn91KI8Zi1kG5M/G2/Jc1 kPHy7erg/7pgCs4sLk0FDPle2uUq8WyV76XnxlGajzd+rb5zXXzRk5hrpG8trHNVkI qKQufrbLAv/PeoOHwFDPSF7Yomh9c77ddbAcaejY= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 8142D3851167 for ; Wed, 24 Aug 2022 11:15:31 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8142D3851167 Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 825A8204E2 for ; Wed, 24 Aug 2022 11:15:30 +0000 (UTC) Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 6C38013780 for ; Wed, 24 Aug 2022 11:15:30 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id jIcvGVIIBmPnLwAAMHmgww (envelope-from ) for ; Wed, 24 Aug 2022 11:15:30 +0000 Date: Wed, 24 Aug 2022 13:15:30 +0200 (CEST) To: gcc-patches@gcc.gnu.org Subject: [PATCH 2/2] Move things around in predicate analysis MIME-Version: 1.0 Message-Id: <20220824111530.6C38013780@imap2.suse-dmz.suse.de> X-Spam-Status: No, score=-11.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Richard Biener via Gcc-patches From: Richard Biener Reply-To: Richard Biener Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This moves a few functions, notably normalization after a big comment documenting it. I've left the rest unorganized for now. Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed. * gimple-predicate-analysis.cc: Move predicate normalization after the comment documenting it. --- gcc/gimple-predicate-analysis.cc | 996 +++++++++++++++---------------- 1 file changed, 498 insertions(+), 498 deletions(-) diff --git a/gcc/gimple-predicate-analysis.cc b/gcc/gimple-predicate-analysis.cc index 8995c11a45c..079e06009fd 100644 --- a/gcc/gimple-predicate-analysis.cc +++ b/gcc/gimple-predicate-analysis.cc @@ -1694,570 +1694,284 @@ predicate::simplify (gimple *use_or_def, bool is_use) (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0) */ -/* Store a PRED in *THIS. */ - -void -predicate::push_pred (const pred_info &pred) -{ - pred_chain chain = vNULL; - chain.safe_push (pred); - m_preds.safe_push (chain); -} - -/* Dump predicates in *THIS for STMT prepended by MSG. */ +/* Normalize predicate PRED: + 1) if PRED can no longer be normalized, append it to *THIS. + 2) otherwise if PRED is of the form x != 0, follow x's definition + and put normalized predicates into WORK_LIST. */ void -predicate::dump (gimple *stmt, const char *msg) const +predicate::normalize (pred_chain *norm_chain, + pred_info pred, + tree_code and_or_code, + pred_chain *work_list, + hash_set *mark_set) { - fprintf (dump_file, "%s", msg); - if (stmt) + if (!is_neq_zero_form_p (pred)) { - fputc ('\t', dump_file); - print_gimple_stmt (dump_file, stmt, 0); - fprintf (dump_file, " is conditional on:\n"); + if (and_or_code == BIT_IOR_EXPR) + push_pred (pred); + else + norm_chain->safe_push (pred); + return; } - unsigned np = m_preds.length (); - if (np == 0) + gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); + + if (gimple_code (def_stmt) == GIMPLE_PHI + && is_degenerate_phi (def_stmt, &pred)) + /* PRED has been modified above. */ + work_list->safe_push (pred); + else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR) { - fprintf (dump_file, "\t(empty)\n"); - return; - } + unsigned n = gimple_phi_num_args (def_stmt); - { - tree expr = build_pred_expr (m_preds); - char *str = print_generic_expr_to_str (expr); - fprintf (dump_file, "\t%s (expanded)\n", str); - free (str); - } + /* Punt for a nonzero constant. The predicate should be one guarding + the phi edge. */ + for (unsigned i = 0; i < n; ++i) + { + tree op = gimple_phi_arg_def (def_stmt, i); + if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op)) + { + push_pred (pred); + return; + } + } - if (np > 1) - fprintf (dump_file, "\tOR ("); + for (unsigned i = 0; i < n; ++i) + { + tree op = gimple_phi_arg_def (def_stmt, i); + if (integer_zerop (op)) + continue; + + push_to_worklist (op, work_list, mark_set); + } + } + else if (gimple_code (def_stmt) != GIMPLE_ASSIGN) + { + if (and_or_code == BIT_IOR_EXPR) + push_pred (pred); + else + norm_chain->safe_push (pred); + } + else if (gimple_assign_rhs_code (def_stmt) == and_or_code) + { + /* Avoid splitting up bit manipulations like x & 3 or y | 1. */ + if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt))) + { + /* But treat x & 3 as a condition. */ + if (and_or_code == BIT_AND_EXPR) + { + pred_info n_pred; + n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt); + n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt); + n_pred.cond_code = and_or_code; + n_pred.invert = false; + norm_chain->safe_push (n_pred); + } + } + else + { + push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set); + push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set); + } + } + else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) + == tcc_comparison) + { + pred_info n_pred = get_pred_info_from_cmp (def_stmt); + if (and_or_code == BIT_IOR_EXPR) + push_pred (n_pred); + else + norm_chain->safe_push (n_pred); + } else - fputc ('\t', dump_file); - for (unsigned i = 0; i < np; i++) { - dump_pred_chain (m_preds[i]); - if (i < np - 1) - fprintf (dump_file, ", "); - else if (i > 0) - fputc (')', dump_file); + if (and_or_code == BIT_IOR_EXPR) + push_pred (pred); + else + norm_chain->safe_push (pred); } - fputc ('\n', dump_file); } -/* 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. */ +/* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */ -bool -uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb, - basic_block use_bb) +void +predicate::normalize (const pred_info &pred) { - 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. */ - basic_block cd_root = def_bb; - while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) + if (!is_neq_zero_form_p (pred)) { - /* Find CD_ROOT's closest postdominator that's its control - equivalent. */ - if (basic_block bb = find_control_equiv_block (cd_root)) - if (dominated_by_p (CDI_DOMINATORS, use_bb, bb)) - { - cd_root = bb; - continue; - } - - break; + push_pred (pred); + return; } - /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB. - Each DEP_CHAINS element is a series of edges whose conditions - are logical conjunctions. Together, the DEP_CHAINS vector is - used below to initialize an OR expression of the conjunctions. */ - unsigned num_calls = 0; - unsigned num_chains = 0; - auto_vec dep_chains[MAX_NUM_CHAINS]; - auto_vec cur_chain; + tree_code and_or_code = ERROR_MARK; - if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains, - cur_chain, &num_calls)) + gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); + if (gimple_code (def_stmt) == GIMPLE_ASSIGN) + and_or_code = gimple_assign_rhs_code (def_stmt); + if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR) { - gcc_assert (num_chains == 0); - simple_control_dep_chain (dep_chains[0], cd_root, use_bb); - num_chains++; + if (TREE_CODE_CLASS (and_or_code) == tcc_comparison) + { + pred_info n_pred = get_pred_info_from_cmp (def_stmt); + push_pred (n_pred); + } + else + push_pred (pred); + return; } - if (DEBUG_PREDICATE_ANALYZER && dump_file) + + pred_chain norm_chain = vNULL; + pred_chain work_list = vNULL; + work_list.safe_push (pred); + hash_set mark_set; + + while (!work_list.is_empty ()) { - fprintf (dump_file, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) " - "initialized from %u dep_chains:\n\t", - def_bb->index, use_bb->index, num_chains); - dump_dep_chains (dep_chains, num_chains); + pred_info a_pred = work_list.pop (); + normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set); } - /* From the set of edges computed above initialize *THIS as the OR - 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. */ - use_preds.init_from_control_deps (dep_chains, num_chains); - return !use_preds.is_empty (); -} - -/* Release resources in *THIS. */ + if (and_or_code == BIT_AND_EXPR) + m_preds.safe_push (norm_chain); -predicate::~predicate () -{ - unsigned n = m_preds.length (); - for (unsigned i = 0; i != n; ++i) - m_preds[i].release (); - m_preds.release (); + work_list.release (); } -/* Copy-assign RHS to *THIS. */ +/* Normalize a single predicate PRED_CHAIN and append it to *THIS. */ -predicate& -predicate::operator= (const predicate &rhs) +void +predicate::normalize (const pred_chain &chain) { - if (this == &rhs) - return *this; - - unsigned n = m_preds.length (); - for (unsigned i = 0; i != n; ++i) - m_preds[i].release (); - m_preds.release (); + pred_chain work_list = vNULL; + hash_set mark_set; + for (unsigned i = 0; i < chain.length (); i++) + { + work_list.safe_push (chain[i]); + mark_set.add (chain[i].pred_lhs); + } - n = rhs.m_preds.length (); - for (unsigned i = 0; i != n; ++i) + /* Normalized chain of predicates built up below. */ + pred_chain norm_chain = vNULL; + while (!work_list.is_empty ()) { - const pred_chain &chain = rhs.m_preds[i]; - m_preds.safe_push (chain.copy ()); + pred_info pi = work_list.pop (); + 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); } - return *this; + m_preds.safe_push (norm_chain); + work_list.release (); } -/* For each use edge of PHI, compute all control dependence chains - and convert those to the composite predicates in M_PREDS. - Return true if a nonempty predicate has been obtained. */ +/* Normalize predicate chains in THIS. */ -bool -uninit_analysis::init_from_phi_def (gphi *phi) +void +predicate::normalize (gimple *use_or_def, bool is_use) { - 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. */ - basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb); - if (!cd_root) - return false; - - /* Set DEF_EDGES to the edges to the PHI from the bb's that provide - 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, &visited_phis); - - unsigned nedges = def_edges.length (); - if (nedges == 0) - return false; - - unsigned num_chains = 0; - auto_vec dep_chains[MAX_NUM_CHAINS]; - auto_vec cur_chain; - for (unsigned i = 0; i < nedges; i++) + if (dump_file && dump_flags & TDF_DETAILS) { - edge e = def_edges[i]; - unsigned num_calls = 0; - unsigned prev_nc = num_chains; - compute_control_dep_chain (cd_root, e->src, dep_chains, - &num_chains, cur_chain, &num_calls); - - /* Update the newly added chains with the phi operand edge. */ - if (EDGE_COUNT (e->src->succs) > 1) - { - if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS) - dep_chains[num_chains++] = vNULL; - for (unsigned j = prev_nc; j < num_chains; j++) - dep_chains[j].safe_push (e); - } + fprintf (dump_file, "Before normalization "); + dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n"); } - /* Convert control dependence chains to the predicate in *THIS under - which the PHI operands are defined to values for which M_EVAL is - false. */ - 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 - the incoming paths that have an empty (or possibly empty) definition - can be pruned. Return true if it can be determined that the use of - PHI's def in USE_STMT is guarded by a predicate set that does not - overlap with the predicate sets of all runtime paths that do not - have a definition. - - Return false if the use is not guarded or if it cannot be determined. - USE_BB is the bb of the use (for phi operand use, the bb is not the bb - of the phi stmt, but the source bb of the operand edge). - - OPNDS is a bitmap with a bit set for each PHI operand of interest. - - THIS->M_PREDS contains the (memoized) defining predicate chains of - a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate - chains are computed and stored into THIS->M_PREDS as needed. - - VISITED_PHIS is a pointer set of phis being visited. */ - -bool -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; - - /* The basic block where the PHI is defined. */ - basic_block def_bb = gimple_bb (phi); - - if (dominated_by_p (CDI_POST_DOMINATORS, def_bb, use_bb)) - /* The use is not guarded. */ - return false; - - /* 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; - if (!init_use_preds (use_preds, def_bb, use_bb)) - return false; - - /* Try to prune the dead incoming phi edges. */ - if (!overlap (phi, opnds, visited, use_preds)) + predicate norm_preds; + for (unsigned i = 0; i < m_preds.length (); i++) { - if (DEBUG_PREDICATE_ANALYZER && dump_file) - fputs ("found predicate overlap\n", dump_file); - - return true; + if (m_preds[i].length () != 1) + norm_preds.normalize (m_preds[i]); + else + norm_preds.normalize (m_preds[i][0]); } - /* 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_cannot_happen (phi, opnds, use_preds)) - return true; + *this = norm_preds; - if (m_phi_def_preds.is_empty ()) + if (dump_file) { - /* Lazily initialize *THIS from PHI. */ - if (!init_from_phi_def (phi)) - return false; - - m_phi_def_preds.simplify (phi); - m_phi_def_preds.normalize (phi); + fprintf (dump_file, "After normalization "); + dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n"); } - - use_preds.simplify (use_stmt, /*is_use=*/true); - use_preds.normalize (use_stmt, /*is_use=*/true); - - /* 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 (m_phi_def_preds.superset_of (use_preds)) - return true; - - return false; } -/* Public interface to the above. */ +/* Convert the chains of control dependence edges into a set of predicates. + A control dependence chain is represented by a vector edges. DEP_CHAINS + points to an array of NUM_CHAINS dependence chains. One edge in + a dependence chain is mapped to predicate expression represented by + pred_info type. One dependence chain is converted to a composite + predicate that is the result of AND operation of pred_info mapped to + each edge. A composite predicate is represented by a vector of + pred_info. Sets M_PREDS to the resulting composite predicates. */ -bool -uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi, - unsigned opnds) +void +predicate::init_from_control_deps (const vec *dep_chains, + unsigned num_chains) { - hash_set visited; - return is_use_guarded (stmt, use_bb, phi, opnds, &visited); -} + gcc_assert (is_empty ()); -/* Normalize predicate PRED: - 1) if PRED can no longer be normalized, append it to *THIS. - 2) otherwise if PRED is of the form x != 0, follow x's definition - and put normalized predicates into WORK_LIST. */ + bool has_valid_pred = false; + if (num_chains == 0) + return; -void -predicate::normalize (pred_chain *norm_chain, - pred_info pred, - tree_code and_or_code, - pred_chain *work_list, - hash_set *mark_set) -{ - if (!is_neq_zero_form_p (pred)) + if (num_chains >= MAX_NUM_CHAINS) { - if (and_or_code == BIT_IOR_EXPR) - push_pred (pred); - else - norm_chain->safe_push (pred); + if (dump_file) + fprintf (dump_file, "MAX_NUM_CHAINS exceeded: %u\n", num_chains); return; } - gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); + /* Convert the control dependency chain into a set of predicates. */ + m_preds.reserve (num_chains); - if (gimple_code (def_stmt) == GIMPLE_PHI - && is_degenerate_phi (def_stmt, &pred)) - /* PRED has been modified above. */ - work_list->safe_push (pred); - else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR) + for (unsigned i = 0; i < num_chains; i++) { - unsigned n = gimple_phi_num_args (def_stmt); + /* One path through the CFG represents a logical conjunction + of the predicates. */ + const vec &path = dep_chains[i]; - /* Punt for a nonzero constant. The predicate should be one guarding - the phi edge. */ - for (unsigned i = 0; i < n; ++i) + has_valid_pred = false; + /* The chain of predicates guarding the definition along this path. */ + pred_chain t_chain{ }; + for (unsigned j = 0; j < path.length (); j++) { - tree op = gimple_phi_arg_def (def_stmt, i); - if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op)) + edge e = path[j]; + basic_block guard_bb = e->src; + /* Ignore empty forwarder blocks. */ + if (empty_block_p (guard_bb) && single_succ_p (guard_bb)) + continue; + + /* An empty basic block here is likely a PHI, and is not one + of the cases we handle below. */ + gimple_stmt_iterator gsi = gsi_last_bb (guard_bb); + if (gsi_end_p (gsi)) { - push_pred (pred); - return; + has_valid_pred = false; + break; } - } - - for (unsigned i = 0; i < n; ++i) - { - tree op = gimple_phi_arg_def (def_stmt, i); - if (integer_zerop (op)) + /* Get the conditional controlling the bb exit edge. */ + gimple *cond_stmt = gsi_stmt (gsi); + if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2) + /* Ignore EH edge. Can add assertion on the other edge's flag. */ continue; - - push_to_worklist (op, work_list, mark_set); - } - } - else if (gimple_code (def_stmt) != GIMPLE_ASSIGN) - { - if (and_or_code == BIT_IOR_EXPR) - push_pred (pred); - else - norm_chain->safe_push (pred); - } - else if (gimple_assign_rhs_code (def_stmt) == and_or_code) - { - /* Avoid splitting up bit manipulations like x & 3 or y | 1. */ - if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt))) - { - /* But treat x & 3 as a condition. */ - if (and_or_code == BIT_AND_EXPR) + /* Skip if there is essentially one succesor. */ + if (EDGE_COUNT (e->src->succs) == 2) { - pred_info n_pred; - n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt); - n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt); - n_pred.cond_code = and_or_code; - n_pred.invert = false; - norm_chain->safe_push (n_pred); - } - } - else - { - push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set); - push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set); - } - } - else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) - == tcc_comparison) - { - pred_info n_pred = get_pred_info_from_cmp (def_stmt); - if (and_or_code == BIT_IOR_EXPR) - push_pred (n_pred); - else - norm_chain->safe_push (n_pred); - } - else - { - if (and_or_code == BIT_IOR_EXPR) - push_pred (pred); - else - norm_chain->safe_push (pred); - } -} - -/* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */ - -void -predicate::normalize (const pred_info &pred) -{ - if (!is_neq_zero_form_p (pred)) - { - push_pred (pred); - return; - } - - tree_code and_or_code = ERROR_MARK; - - gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs); - if (gimple_code (def_stmt) == GIMPLE_ASSIGN) - and_or_code = gimple_assign_rhs_code (def_stmt); - if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR) - { - if (TREE_CODE_CLASS (and_or_code) == tcc_comparison) - { - pred_info n_pred = get_pred_info_from_cmp (def_stmt); - push_pred (n_pred); - } - else - push_pred (pred); - return; - } - - - pred_chain norm_chain = vNULL; - pred_chain work_list = vNULL; - work_list.safe_push (pred); - hash_set mark_set; - - while (!work_list.is_empty ()) - { - pred_info a_pred = work_list.pop (); - normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set); - } - - if (and_or_code == BIT_AND_EXPR) - m_preds.safe_push (norm_chain); - - work_list.release (); -} - -/* Normalize a single predicate PRED_CHAIN and append it to *THIS. */ - -void -predicate::normalize (const pred_chain &chain) -{ - pred_chain work_list = vNULL; - hash_set mark_set; - for (unsigned i = 0; i < chain.length (); i++) - { - work_list.safe_push (chain[i]); - mark_set.add (chain[i].pred_lhs); - } - - /* Normalized chain of predicates built up below. */ - pred_chain norm_chain = vNULL; - while (!work_list.is_empty ()) - { - pred_info pi = work_list.pop (); - 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); - } - - m_preds.safe_push (norm_chain); - work_list.release (); -} - -/* Normalize predicate chains in THIS. */ - -void -predicate::normalize (gimple *use_or_def, bool is_use) -{ - if (dump_file && dump_flags & TDF_DETAILS) - { - fprintf (dump_file, "Before normalization "); - dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n"); - } - - predicate norm_preds; - for (unsigned i = 0; i < m_preds.length (); i++) - { - if (m_preds[i].length () != 1) - norm_preds.normalize (m_preds[i]); - else - norm_preds.normalize (m_preds[i][0]); - } - - *this = norm_preds; - - if (dump_file) - { - fprintf (dump_file, "After normalization "); - dump (use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n"); - } -} - -/* Convert the chains of control dependence edges into a set of predicates. - A control dependence chain is represented by a vector edges. DEP_CHAINS - points to an array of NUM_CHAINS dependence chains. One edge in - a dependence chain is mapped to predicate expression represented by - pred_info type. One dependence chain is converted to a composite - predicate that is the result of AND operation of pred_info mapped to - each edge. A composite predicate is represented by a vector of - pred_info. Sets M_PREDS to the resulting composite predicates. */ - -void -predicate::init_from_control_deps (const vec *dep_chains, - unsigned num_chains) -{ - gcc_assert (is_empty ()); - - bool has_valid_pred = false; - if (num_chains == 0) - return; - - if (num_chains >= MAX_NUM_CHAINS) - { - if (dump_file) - fprintf (dump_file, "MAX_NUM_CHAINS exceeded: %u\n", num_chains); - return; - } - - /* Convert the control dependency chain into a set of predicates. */ - m_preds.reserve (num_chains); - - for (unsigned i = 0; i < num_chains; i++) - { - /* One path through the CFG represents a logical conjunction - of the predicates. */ - const vec &path = dep_chains[i]; - - has_valid_pred = false; - /* The chain of predicates guarding the definition along this path. */ - pred_chain t_chain{ }; - for (unsigned j = 0; j < path.length (); j++) - { - edge e = path[j]; - basic_block guard_bb = e->src; - /* Ignore empty forwarder blocks. */ - if (empty_block_p (guard_bb) && single_succ_p (guard_bb)) - continue; - - /* An empty basic block here is likely a PHI, and is not one - of the cases we handle below. */ - gimple_stmt_iterator gsi = gsi_last_bb (guard_bb); - if (gsi_end_p (gsi)) - { - has_valid_pred = false; - break; - } - /* Get the conditional controlling the bb exit edge. */ - gimple *cond_stmt = gsi_stmt (gsi); - if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2) - /* Ignore EH edge. Can add assertion on the other edge's flag. */ - continue; - /* Skip if there is essentially one succesor. */ - if (EDGE_COUNT (e->src->succs) == 2) - { - edge e1; - edge_iterator ei1; - bool skip = false; - - FOR_EACH_EDGE (e1, ei1, e->src->succs) - { - if (EDGE_COUNT (e1->dest->succs) == 0) - { - skip = true; - break; - } - } - if (skip) - continue; + edge e1; + edge_iterator ei1; + bool skip = false; + + FOR_EACH_EDGE (e1, ei1, e->src->succs) + { + if (EDGE_COUNT (e1->dest->succs) == 0) + { + skip = true; + break; + } + } + if (skip) + continue; } if (gimple_code (cond_stmt) == GIMPLE_COND) { @@ -2353,3 +2067,289 @@ predicate::init_from_control_deps (const vec *dep_chains, /* Clear M_PREDS to indicate failure. */ m_preds.release (); } +/* Store a PRED in *THIS. */ + +void +predicate::push_pred (const pred_info &pred) +{ + pred_chain chain = vNULL; + chain.safe_push (pred); + m_preds.safe_push (chain); +} + +/* Dump predicates in *THIS for STMT prepended by MSG. */ + +void +predicate::dump (gimple *stmt, const char *msg) const +{ + fprintf (dump_file, "%s", msg); + if (stmt) + { + fputc ('\t', dump_file); + print_gimple_stmt (dump_file, stmt, 0); + fprintf (dump_file, " is conditional on:\n"); + } + + unsigned np = m_preds.length (); + if (np == 0) + { + fprintf (dump_file, "\t(empty)\n"); + return; + } + + { + tree expr = build_pred_expr (m_preds); + char *str = print_generic_expr_to_str (expr); + fprintf (dump_file, "\t%s (expanded)\n", str); + free (str); + } + + if (np > 1) + fprintf (dump_file, "\tOR ("); + else + fputc ('\t', dump_file); + for (unsigned i = 0; i < np; i++) + { + dump_pred_chain (m_preds[i]); + if (i < np - 1) + fprintf (dump_file, ", "); + else if (i > 0) + fputc (')', dump_file); + } + fputc ('\n', dump_file); +} + +/* 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. */ + +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. */ + basic_block cd_root = def_bb; + while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root)) + { + /* Find CD_ROOT's closest postdominator that's its control + equivalent. */ + if (basic_block bb = find_control_equiv_block (cd_root)) + if (dominated_by_p (CDI_DOMINATORS, use_bb, bb)) + { + cd_root = bb; + continue; + } + + break; + } + + /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB. + Each DEP_CHAINS element is a series of edges whose conditions + are logical conjunctions. Together, the DEP_CHAINS vector is + used below to initialize an OR expression of the conjunctions. */ + unsigned num_calls = 0; + unsigned num_chains = 0; + auto_vec dep_chains[MAX_NUM_CHAINS]; + auto_vec cur_chain; + + if (!compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains, + cur_chain, &num_calls)) + { + gcc_assert (num_chains == 0); + simple_control_dep_chain (dep_chains[0], cd_root, use_bb); + num_chains++; + } + + if (DEBUG_PREDICATE_ANALYZER && dump_file) + { + fprintf (dump_file, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) " + "initialized from %u dep_chains:\n\t", + def_bb->index, use_bb->index, num_chains); + dump_dep_chains (dep_chains, num_chains); + } + + /* From the set of edges computed above initialize *THIS as the OR + 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. */ + use_preds.init_from_control_deps (dep_chains, num_chains); + return !use_preds.is_empty (); +} + +/* Release resources in *THIS. */ + +predicate::~predicate () +{ + unsigned n = m_preds.length (); + for (unsigned i = 0; i != n; ++i) + m_preds[i].release (); + m_preds.release (); +} + +/* Copy-assign RHS to *THIS. */ + +predicate& +predicate::operator= (const predicate &rhs) +{ + if (this == &rhs) + return *this; + + unsigned n = m_preds.length (); + for (unsigned i = 0; i != n; ++i) + m_preds[i].release (); + m_preds.release (); + + n = rhs.m_preds.length (); + for (unsigned i = 0; i != n; ++i) + { + const pred_chain &chain = rhs.m_preds[i]; + m_preds.safe_push (chain.copy ()); + } + + return *this; +} + +/* For each use edge of PHI, compute all control dependence chains + and convert those to the composite predicates in M_PREDS. + Return true if a nonempty predicate has been obtained. */ + +bool +uninit_analysis::init_from_phi_def (gphi *phi) +{ + 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. */ + basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb); + if (!cd_root) + return false; + + /* Set DEF_EDGES to the edges to the PHI from the bb's that provide + 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, &visited_phis); + + unsigned nedges = def_edges.length (); + if (nedges == 0) + return false; + + unsigned num_chains = 0; + auto_vec dep_chains[MAX_NUM_CHAINS]; + auto_vec cur_chain; + for (unsigned i = 0; i < nedges; i++) + { + edge e = def_edges[i]; + unsigned num_calls = 0; + unsigned prev_nc = num_chains; + compute_control_dep_chain (cd_root, e->src, dep_chains, + &num_chains, cur_chain, &num_calls); + + /* Update the newly added chains with the phi operand edge. */ + if (EDGE_COUNT (e->src->succs) > 1) + { + if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS) + dep_chains[num_chains++] = vNULL; + for (unsigned j = prev_nc; j < num_chains; j++) + dep_chains[j].safe_push (e); + } + } + + /* Convert control dependence chains to the predicate in *THIS under + which the PHI operands are defined to values for which M_EVAL is + false. */ + 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 + the incoming paths that have an empty (or possibly empty) definition + can be pruned. Return true if it can be determined that the use of + PHI's def in USE_STMT is guarded by a predicate set that does not + overlap with the predicate sets of all runtime paths that do not + have a definition. + + Return false if the use is not guarded or if it cannot be determined. + USE_BB is the bb of the use (for phi operand use, the bb is not the bb + of the phi stmt, but the source bb of the operand edge). + + OPNDS is a bitmap with a bit set for each PHI operand of interest. + + THIS->M_PREDS contains the (memoized) defining predicate chains of + a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate + chains are computed and stored into THIS->M_PREDS as needed. + + VISITED_PHIS is a pointer set of phis being visited. */ + +bool +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; + + /* The basic block where the PHI is defined. */ + basic_block def_bb = gimple_bb (phi); + + if (dominated_by_p (CDI_POST_DOMINATORS, def_bb, use_bb)) + /* The use is not guarded. */ + return false; + + /* 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; + if (!init_use_preds (use_preds, def_bb, use_bb)) + return false; + + /* Try to prune the dead incoming phi edges. */ + if (!overlap (phi, opnds, visited, use_preds)) + { + if (DEBUG_PREDICATE_ANALYZER && dump_file) + fputs ("found predicate overlap\n", dump_file); + + return true; + } + + /* 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_cannot_happen (phi, opnds, use_preds)) + return true; + + if (m_phi_def_preds.is_empty ()) + { + /* Lazily initialize *THIS from PHI. */ + if (!init_from_phi_def (phi)) + return false; + + m_phi_def_preds.simplify (phi); + m_phi_def_preds.normalize (phi); + } + + use_preds.simplify (use_stmt, /*is_use=*/true); + use_preds.normalize (use_stmt, /*is_use=*/true); + + /* 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 (m_phi_def_preds.superset_of (use_preds)) + return true; + + return false; +} + +/* Public interface to the above. */ + +bool +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); +} +