@@ -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<tree> *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<edge> dep_chains[MAX_NUM_CHAINS];
- auto_vec<edge, MAX_CHAIN_LEN + 1> 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<tree> 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<tree> 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<edge> def_edges;
- hash_set<gimple *> 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<edge> dep_chains[MAX_NUM_CHAINS];
- auto_vec<edge, MAX_CHAIN_LEN + 1> 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<gphi *> *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<edge> *dep_chains,
+ unsigned num_chains)
{
- hash_set<gphi *> 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<tree> *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<edge> &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<tree> 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<tree> 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<edge> *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<edge> &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<edge> *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<edge> dep_chains[MAX_NUM_CHAINS];
+ auto_vec<edge, MAX_CHAIN_LEN + 1> 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<edge> def_edges;
+ hash_set<gimple *> 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<edge> dep_chains[MAX_NUM_CHAINS];
+ auto_vec<edge, MAX_CHAIN_LEN + 1> 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<gphi *> *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<gphi *> visited;
+ return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
+}
+