From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1666) id 130C13851A8E; Wed, 24 Aug 2022 11:16:10 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 130C13851A8E DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1661339770; bh=dHz/S1Y/uBlqz1xEN3NnhNnSDTkZkRnDNnMizHEC1jU=; h=From:To:Subject:Date:From; b=DblLaXN+kTKQW0G4T7UpdbunaknKUsczvPr1a+NF+TnKLlZgm1Inm5F8Ai2ZxO9Hq mN7vWCR8VyI7L3Kl8ege3uWZsIHR2JUJ+Y0SoOqNN0D+JJWoN1eIqxZTgOcsaaVALF W0OxqmIFTn1xR2tNcOUjUYhT4s/tZ7NTce4vBENw= 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-2171] Move things around in predicate analysis X-Act-Checkin: gcc X-Git-Author: Richard Biener X-Git-Refname: refs/heads/master X-Git-Oldrev: cd1216d581b44f14b93a427bf2e95ee37e394b8b X-Git-Newrev: 4a907b15b551becd3145061a8906089267db5a04 Message-Id: <20220824111610.130C13851A8E@sourceware.org> Date: Wed, 24 Aug 2022 11:16:10 +0000 (GMT) List-Id: https://gcc.gnu.org/g:4a907b15b551becd3145061a8906089267db5a04 commit r13-2171-g4a907b15b551becd3145061a8906089267db5a04 Author: Richard Biener Date: Wed Aug 24 11:45:43 2022 +0200 Move things around in predicate analysis This moves a few functions, notably normalization after a big comment documenting it. I've left the rest unorganized for now. * gimple-predicate-analysis.cc: Move predicate normalization after the comment documenting it. Diff: --- 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); +} +