#include "tree-dump.h"
#include "tree-pass.h"
#include "diagnostic-core.h"
-#include "toplev.h"
#include "timevar.h"
/* This implements the pass that does predicate aware warning on uses of
unsigned uninit_opnds = 0;
n = gimple_phi_num_args (phi);
+ /* Bail out for phi with too many args. */
+ if (n > 32)
+ return 0;
for (i = 0; i < n; ++i)
{
if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
return false;
- /* Now convert CD chains into predicates */
- has_valid_pred = true;
-
/* Now convert the control dep chain into a set
of predicates. */
*preds = XCNEWVEC (VEC(use_pred_info_t, heap) *,
for (i = 0; i < num_chains; i++)
{
VEC(edge, heap) *one_cd_chain = dep_chains[i];
+
+ has_valid_pred = false;
for (j = 0; j < VEC_length (edge, one_cd_chain); j++)
{
gimple cond_stmt;
one_pred->cond = cond_stmt;
one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE);
VEC_safe_push (use_pred_info_t, heap, (*preds)[i], one_pred);
+ has_valid_pred = true;
}
if (!has_valid_pred)
opnd_edge = gimple_phi_arg_edge (phi, i);
opnd = gimple_phi_arg_def (phi, i);
- if (TREE_CODE (opnd) != SSA_NAME
- || !ssa_undefined_value_p (opnd))
- VEC_safe_push (edge, heap, *edges, opnd_edge);
+ if (TREE_CODE (opnd) != SSA_NAME)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
+ print_gimple_stmt (dump_file, phi, 0, 0);
+ }
+ VEC_safe_push (edge, heap, *edges, opnd_edge);
+ }
else
{
gimple def = SSA_NAME_DEF_STMT (opnd);
+
if (gimple_code (def) == GIMPLE_PHI
&& dominated_by_p (CDI_DOMINATORS,
gimple_bb (def), cd_root))
collect_phi_def_edges (def, cd_root, edges,
visited_phis);
+ else if (!ssa_undefined_value_p (opnd))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
+ print_gimple_stmt (dump_file, phi, 0, 0);
+ }
+ VEC_safe_push (edge, heap, *edges, opnd_edge);
+ }
}
}
}
unsigned uninit_opnds,
struct pointer_set_t *visited_phis);
+/* Returns true if all uninitialized opnds are pruned. Returns false
+ otherwise. PHI is the phi node with uninitialized operands,
+ UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
+ FLAG_DEF is the statement defining the flag guarding the use of the
+ PHI output, BOUNDARY_CST is the const value used in the predicate
+ associated with the flag, CMP_CODE is the comparison code used in
+ the predicate, VISITED_PHIS is the pointer set of phis visited, and
+ VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
+ that are also phis.
+
+ Example scenario:
+
+ BB1:
+ flag_1 = phi <0, 1> // (1)
+ var_1 = phi <undef, some_val>
+
+
+ BB2:
+ flag_2 = phi <0, flag_1, flag_1> // (2)
+ var_2 = phi <undef, var_1, var_1>
+ if (flag_2 == 1)
+ goto BB3;
+
+ BB3:
+ use of var_2 // (3)
+
+ Because some flag arg in (1) is not constant, if we do not look into the
+ flag phis recursively, it is conservatively treated as unknown and var_1
+ is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
+ a false warning will be emitted. 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_uninit_phi_opnds_in_unrealizable_paths (
+ gimple phi, unsigned uninit_opnds,
+ gimple flag_def, tree boundary_cst,
+ enum tree_code cmp_code,
+ struct pointer_set_t *visited_phis,
+ bitmap *visited_flag_phis)
+{
+ unsigned i;
+
+ for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
+ {
+ tree flag_arg;
+
+ if (!MASK_TEST_BIT (uninit_opnds, i))
+ continue;
+
+ flag_arg = gimple_phi_arg_def (flag_def, i);
+ if (!is_gimple_constant (flag_arg))
+ {
+ gimple flag_arg_def, phi_arg_def;
+ tree phi_arg;
+ unsigned uninit_opnds_arg_phi;
+
+ if (TREE_CODE (flag_arg) != SSA_NAME)
+ return false;
+ flag_arg_def = SSA_NAME_DEF_STMT (flag_arg);
+ if (gimple_code (flag_arg_def) != GIMPLE_PHI)
+ return false;
+
+ phi_arg = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (phi_arg) != SSA_NAME)
+ return false;
+
+ phi_arg_def = SSA_NAME_DEF_STMT (phi_arg);
+ if (gimple_code (phi_arg_def) != GIMPLE_PHI)
+ return false;
+
+ if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
+ return false;
+
+ if (!*visited_flag_phis)
+ *visited_flag_phis = BITMAP_ALLOC (NULL);
+
+ if (bitmap_bit_p (*visited_flag_phis,
+ SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
+ return false;
+
+ bitmap_set_bit (*visited_flag_phis,
+ SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
+
+ /* Now recursively prune the uninitialized phi args. */
+ uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
+ if (!prune_uninit_phi_opnds_in_unrealizable_paths (
+ phi_arg_def, uninit_opnds_arg_phi,
+ flag_arg_def, boundary_cst, cmp_code,
+ visited_phis, visited_flag_phis))
+ return false;
+
+ bitmap_clear_bit (*visited_flag_phis,
+ SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
+ continue;
+ }
+
+ /* Now check if the constant is in the guarded range. */
+ if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
+ {
+ tree opnd;
+ gimple opnd_def;
+
+ /* Now that we know that this undefined edge is not
+ pruned. If the operand is defined by another phi,
+ we can further prune the incoming edges of that
+ phi by checking the predicates of this operands. */
+
+ opnd = gimple_phi_arg_def (phi, i);
+ opnd_def = SSA_NAME_DEF_STMT (opnd);
+ if (gimple_code (opnd_def) == GIMPLE_PHI)
+ {
+ edge opnd_edge;
+ unsigned uninit_opnds2
+ = compute_uninit_opnds_pos (opnd_def);
+ gcc_assert (!MASK_EMPTY (uninit_opnds2));
+ opnd_edge = gimple_phi_arg_edge (phi, i);
+ if (!is_use_properly_guarded (phi,
+ opnd_edge->src,
+ opnd_def,
+ uninit_opnds2,
+ visited_phis))
+ return false;
+ }
+ else
+ return false;
+ }
+ }
+
+ return true;
+}
+
/* A helper function that determines if the predicate set
of the use is not overlapping with that of the uninit paths.
The most common senario of guarded use is in Example 1:
bool swap_cond = false;
bool invert = false;
VEC(use_pred_info_t, heap) *the_pred_chain;
+ bitmap visited_flag_phis = NULL;
+ bool all_pruned = false;
gcc_assert (num_preds > 0);
/* Find within the common prefix of multiple predicate chains
if (cmp_code == ERROR_MARK)
return false;
- for (i = 0; i < sizeof (unsigned); i++)
- {
- tree flag_arg;
+ all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
+ uninit_opnds,
+ flag_def,
+ boundary_cst,
+ cmp_code,
+ visited_phis,
+ &visited_flag_phis);
- if (!MASK_TEST_BIT (uninit_opnds, i))
- continue;
-
- flag_arg = gimple_phi_arg_def (flag_def, i);
- if (!is_gimple_constant (flag_arg))
- return false;
-
- /* Now check if the constant is in the guarded range. */
- if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
- {
- tree opnd;
- gimple opnd_def;
-
- /* Now that we know that this undefined edge is not
- pruned. If the operand is defined by another phi,
- we can further prune the incoming edges of that
- phi by checking the predicates of this operands. */
-
- opnd = gimple_phi_arg_def (phi, i);
- opnd_def = SSA_NAME_DEF_STMT (opnd);
- if (gimple_code (opnd_def) == GIMPLE_PHI)
- {
- edge opnd_edge;
- unsigned uninit_opnds2
- = compute_uninit_opnds_pos (opnd_def);
- gcc_assert (!MASK_EMPTY (uninit_opnds2));
- opnd_edge = gimple_phi_arg_edge (phi, i);
- if (!is_use_properly_guarded (phi,
- opnd_edge->src,
- opnd_def,
- uninit_opnds2,
- visited_phis))
- return false;
- }
- else
- return false;
- }
- }
+ if (visited_flag_phis)
+ BITMAP_FREE (visited_flag_phis);
- return true;
+ return all_pruned;
}
/* Returns true if TC is AND or OR */
static inline bool
is_and_or_or (enum tree_code tc, tree typ)
{
- return (tc == TRUTH_AND_EXPR
- || tc == TRUTH_OR_EXPR
- || tc == BIT_IOR_EXPR
+ return (tc == BIT_IOR_EXPR
|| (tc == BIT_AND_EXPR
&& (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE)));
}
code1 = norm_cond1->cond_code;
code2 = norm_cond2->cond_code;
- if (code1 == TRUTH_AND_EXPR || code1 == BIT_AND_EXPR)
+ if (code1 == BIT_AND_EXPR)
{
/* Both conditions are AND expressions. */
- if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
+ if (code2 == BIT_AND_EXPR)
return is_and_set_subset_of (norm_cond1, norm_cond2);
/* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
expression. In this case, returns true if any subexpression
of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
- else if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
+ else if (code2 == BIT_IOR_EXPR)
{
size_t len1;
len1 = VEC_length (gimple, norm_cond1->conds);
}
}
/* NORM_COND1 is an OR expression */
- else if (code1 == TRUTH_OR_EXPR || code1 == BIT_IOR_EXPR)
+ else if (code1 == BIT_IOR_EXPR)
{
if (code2 != code1)
return false;
gcc_assert (VEC_length (gimple, norm_cond1->conds) == 1);
/* Conservatively returns false if NORM_COND1 is non-decomposible
and NORM_COND2 is an AND expression. */
- if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
+ if (code2 == BIT_AND_EXPR)
return false;
- if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
+ if (code2 == BIT_IOR_EXPR)
return is_subset_of_any (VEC_index (gimple, norm_cond1->conds, 0),
norm_cond1->invert, norm_cond2, false);
return true;
}
+/* Comparison function used by qsort. It is used to
+ sort predicate chains to allow predicate
+ simplification. */
+
+static int
+pred_chain_length_cmp (const void *p1, const void *p2)
+{
+ use_pred_info_t i1, i2;
+ VEC(use_pred_info_t, heap) * const *chain1
+ = (VEC(use_pred_info_t, heap) * const *)p1;
+ VEC(use_pred_info_t, heap) * const *chain2
+ = (VEC(use_pred_info_t, heap) * const *)p2;
+
+ if (VEC_length (use_pred_info_t, *chain1)
+ != VEC_length (use_pred_info_t, *chain2))
+ return (VEC_length (use_pred_info_t, *chain1)
+ - VEC_length (use_pred_info_t, *chain2));
+
+ i1 = VEC_index (use_pred_info_t, *chain1, 0);
+ i2 = VEC_index (use_pred_info_t, *chain2, 0);
+
+ /* Allow predicates with similar prefix come together. */
+ if (!i1->invert && i2->invert)
+ return -1;
+ else if (i1->invert && !i2->invert)
+ return 1;
+
+ return gimple_uid (i1->cond) - gimple_uid (i2->cond);
+}
+
+/* x OR (!x AND y) is equivalent to x OR y.
+ This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
+ into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
+ the number of chains. Returns true if normalization happens. */
+
+static bool
+normalize_preds (VEC(use_pred_info_t, heap) **preds, size_t *n)
+{
+ size_t i, j, ll;
+ VEC(use_pred_info_t, heap) *pred_chain;
+ VEC(use_pred_info_t, heap) *x = 0;
+ use_pred_info_t xj = 0, nxj = 0;
+
+ if (*n < 2)
+ return false;
+
+ /* First sort the chains in ascending order of lengths. */
+ qsort (preds, *n, sizeof (void *), pred_chain_length_cmp);
+ pred_chain = preds[0];
+ ll = VEC_length (use_pred_info_t, pred_chain);
+ if (ll != 1)
+ {
+ if (ll == 2)
+ {
+ use_pred_info_t xx, yy, xx2, nyy;
+ VEC(use_pred_info_t, heap) *pred_chain2 = preds[1];
+ if (VEC_length (use_pred_info_t, pred_chain2) != 2)
+ return false;
+
+ /* See if simplification x AND y OR x AND !y is possible. */
+ xx = VEC_index (use_pred_info_t, pred_chain, 0);
+ yy = VEC_index (use_pred_info_t, pred_chain, 1);
+ xx2 = VEC_index (use_pred_info_t, pred_chain2, 0);
+ nyy = VEC_index (use_pred_info_t, pred_chain2, 1);
+ if (gimple_cond_lhs (xx->cond) != gimple_cond_lhs (xx2->cond)
+ || gimple_cond_rhs (xx->cond) != gimple_cond_rhs (xx2->cond)
+ || gimple_cond_code (xx->cond) != gimple_cond_code (xx2->cond)
+ || (xx->invert != xx2->invert))
+ return false;
+ if (gimple_cond_lhs (yy->cond) != gimple_cond_lhs (nyy->cond)
+ || gimple_cond_rhs (yy->cond) != gimple_cond_rhs (nyy->cond)
+ || gimple_cond_code (yy->cond) != gimple_cond_code (nyy->cond)
+ || (yy->invert == nyy->invert))
+ return false;
+
+ /* Now merge the first two chains. */
+ free (yy);
+ free (nyy);
+ free (xx2);
+ VEC_free (use_pred_info_t, heap, pred_chain);
+ VEC_free (use_pred_info_t, heap, pred_chain2);
+ pred_chain = 0;
+ VEC_safe_push (use_pred_info_t, heap, pred_chain, xx);
+ preds[0] = pred_chain;
+ for (i = 1; i < *n - 1; i++)
+ preds[i] = preds[i + 1];
+
+ preds[*n - 1] = 0;
+ *n = *n - 1;
+ }
+ else
+ return false;
+ }
+
+ VEC_safe_push (use_pred_info_t, heap, x,
+ VEC_index (use_pred_info_t, pred_chain, 0));
+
+ /* The loop extracts x1, x2, x3, etc from chains
+ x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
+ for (i = 1; i < *n; i++)
+ {
+ pred_chain = preds[i];
+ if (VEC_length (use_pred_info_t, pred_chain) != i + 1)
+ return false;
+
+ for (j = 0; j < i; j++)
+ {
+ xj = VEC_index (use_pred_info_t, x, j);
+ nxj = VEC_index (use_pred_info_t, pred_chain, j);
+
+ /* Check if nxj is !xj */
+ if (gimple_cond_lhs (xj->cond) != gimple_cond_lhs (nxj->cond)
+ || gimple_cond_rhs (xj->cond) != gimple_cond_rhs (nxj->cond)
+ || gimple_cond_code (xj->cond) != gimple_cond_code (nxj->cond)
+ || (xj->invert == nxj->invert))
+ return false;
+ }
+
+ VEC_safe_push (use_pred_info_t, heap, x,
+ VEC_index (use_pred_info_t, pred_chain, i));
+ }
+
+ /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
+ for (j = 0; j < *n; j++)
+ {
+ use_pred_info_t t;
+ xj = VEC_index (use_pred_info_t, x, j);
+
+ t = XNEW (struct use_pred_info);
+ *t = *xj;
+
+ VEC_replace (use_pred_info_t, x, j, t);
+ }
+
+ for (i = 0; i < *n; i++)
+ {
+ pred_chain = preds[i];
+ for (j = 0; j < VEC_length (use_pred_info_t, pred_chain); j++)
+ free (VEC_index (use_pred_info_t, pred_chain, j));
+ VEC_free (use_pred_info_t, heap, pred_chain);
+ pred_chain = 0;
+ /* A new chain. */
+ VEC_safe_push (use_pred_info_t, heap, pred_chain,
+ VEC_index (use_pred_info_t, x, i));
+ preds[i] = pred_chain;
+ }
+ return true;
+}
+
+
+
/* Computes the predicates that guard the use and checks
if the incoming paths that have empty (or possibly
empty) defintion can be pruned/filtered. The function returns
if (dump_file)
dump_predicates (use_stmt, num_preds, preds,
- "Use in stmt ");
+ "\nUse in stmt ");
has_valid_preds = find_def_preds (&def_preds,
&num_def_preds, phi);
if (has_valid_preds)
{
+ bool normed;
if (dump_file)
dump_predicates (phi, num_def_preds, def_preds,
"Operand defs of phi ");
+
+ normed = normalize_preds (def_preds, &num_def_preds);
+ if (normed && dump_file)
+ {
+ fprintf (dump_file, "\nNormalized to\n");
+ dump_predicates (phi, num_def_preds, def_preds,
+ "Operand defs of phi ");
+ }
is_properly_guarded =
is_superset_of (def_preds, num_def_preds,
preds, num_preds);
struct pointer_set_t *visited_phis;
basic_block use_bb;
- use_stmt = use_p->loc.stmt;
+ use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
visited_phis = pointer_set_create ();
- use_bb = gimple_bb (use_stmt);
if (gimple_code (use_stmt) == GIMPLE_PHI)
- {
- unsigned i, n;
- n = gimple_phi_num_args (use_stmt);
-
- /* Find the matching phi argument of the use. */
- for (i = 0; i < n; ++i)
- {
- if (gimple_phi_arg_def_ptr (use_stmt, i) == use_p->use)
- {
- edge e = gimple_phi_arg_edge (use_stmt, i);
- use_bb = e->src;
- break;
- }
- }
- }
+ use_bb = gimple_phi_arg_edge (use_stmt,
+ PHI_ARG_INDEX_FROM_USE (use_p))->src;
+ else
+ use_bb = gimple_bb (use_stmt);
if (is_use_properly_guarded (use_stmt,
use_bb,
}
pointer_set_destroy (visited_phis);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "[CHECK]: Found unguarded use: ");
+ print_gimple_stmt (dump_file, use_stmt, 0, 0);
+ }
/* Found one real use, return. */
if (gimple_code (use_stmt) != GIMPLE_PHI)
- return use_stmt;
+ return use_stmt;
/* Found a phi use that is not guarded,
add the phi to the worklist. */
if (!pointer_set_insert (added_to_worklist,
use_stmt))
{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
+ print_gimple_stmt (dump_file, use_stmt, 0, 0);
+ }
+
VEC_safe_push (gimple, heap, *worklist, use_stmt);
pointer_set_insert (possibly_undefined_names,
phi_result);
if (MASK_EMPTY (uninit_opnds))
return;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "[CHECK]: examining phi: ");
+ print_gimple_stmt (dump_file, phi, 0, 0);
+ }
+
/* Now check if we have any use of the value without proper guard. */
uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
worklist, added_to_worklist);
return;
uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds));
- warn_uninit (uninit_op,
+ warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
+ SSA_NAME_VAR (uninit_op),
"%qD may be used uninitialized in this function",
uninit_use_stmt);
{
VEC_safe_push (gimple, heap, worklist, phi);
pointer_set_insert (added_to_worklist, phi);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "[WORKLIST]: add to initial list: ");
+ print_gimple_stmt (dump_file, phi, 0, 0);
+ }
break;
}
}
cur_phi = VEC_pop (gimple, worklist);
warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
}
-
+
VEC_free (gimple, heap, worklist);
pointer_set_destroy (added_to_worklist);
pointer_set_destroy (possibly_undefined_names);
OSDN Git Service
