aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.4.0/gcc/tree-ssa-uninit.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.4.0/gcc/tree-ssa-uninit.c')
-rw-r--r--gcc-4.4.0/gcc/tree-ssa-uninit.c1720
1 files changed, 1720 insertions, 0 deletions
diff --git a/gcc-4.4.0/gcc/tree-ssa-uninit.c b/gcc-4.4.0/gcc/tree-ssa-uninit.c
new file mode 100644
index 000000000..8bfabcb50
--- /dev/null
+++ b/gcc-4.4.0/gcc/tree-ssa-uninit.c
@@ -0,0 +1,1720 @@
+/* Predicate aware uninitialized variable warning.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
+ Foundation, Inc.
+ Contributed by Xinliang David Li <davidxl@google.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "flags.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "ggc.h"
+#include "langhooks.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "expr.h"
+#include "function.h"
+#include "diagnostic.h"
+#include "bitmap.h"
+#include "pointer-set.h"
+#include "tree-flow.h"
+#include "gimple.h"
+#include "tree-inline.h"
+#include "varray.h"
+#include "timevar.h"
+#include "hashtab.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+#include "toplev.h"
+#include "timevar.h"
+
+/* This implements the pass that does predicate aware warning on uses of
+ possibly uninitialized variables. The pass first collects the set of
+ possibly uninitialized SSA names. For each such name, it walks through
+ all its immediate uses. For each immediate use, it rebuilds the condition
+ expression (the predicate) that guards the use. The predicate is then
+ examined to see if the variable is always defined under that same condition.
+ This is done either by pruning the unrealizable paths that lead to the
+ default definitions or by checking if the predicate set that guards the
+ defining paths is a superset of the use predicate. */
+
+
+/* Pointer set of potentially undefined ssa names, i.e.,
+ ssa names that are defined by phi with operands that
+ are not defined or potentially undefined. */
+static struct pointer_set_t *possibly_undefined_names = 0;
+
+/* Return true if T, an SSA_NAME, has an undefined value. */
+
+bool
+ssa_undefined_value_p (tree t)
+{
+ tree var = SSA_NAME_VAR (t);
+
+ /* Parameters get their initial value from the function entry. */
+ if (TREE_CODE (var) == PARM_DECL)
+ return false;
+
+ /* Hard register variables get their initial value from the ether. */
+ if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
+ return false;
+
+ /* The value is undefined iff its definition statement is empty. */
+ return (gimple_nop_p (SSA_NAME_DEF_STMT (t))
+ || (possibly_undefined_names
+ && pointer_set_contains (possibly_undefined_names, t)));
+}
+
+/* Checks if the operand OPND of PHI is defined by
+ another phi with one operand defined by this PHI,
+ but the rest operands are all defined. If yes,
+ returns true to skip this this operand as being
+ redundant. Can be enhanced to be more general. */
+
+static bool
+can_skip_redundant_opnd (tree opnd, gimple phi)
+{
+ gimple op_def;
+ tree phi_def;
+ int i, n;
+
+ phi_def = gimple_phi_result (phi);
+ op_def = SSA_NAME_DEF_STMT (opnd);
+ if (gimple_code (op_def) != GIMPLE_PHI)
+ return false;
+ n = gimple_phi_num_args (op_def);
+ for (i = 0; i < n; ++i)
+ {
+ tree op = gimple_phi_arg_def (op_def, i);
+ if (TREE_CODE (op) != SSA_NAME)
+ continue;
+ if (op != phi_def && ssa_undefined_value_p (op))
+ return false;
+ }
+
+ return true;
+}
+
+/* Returns an sbitmap holding the positions of arguments in PHI
+ that have empty (or possibly empty) definitions. */
+
+static sbitmap
+compute_uninit_opnds_pos (gimple phi)
+{
+ size_t i, n;
+ sbitmap uninit_opnds;
+
+ n = gimple_phi_num_args (phi);
+ uninit_opnds = sbitmap_alloc (n);
+ sbitmap_zero (uninit_opnds);
+
+ for (i = 0; i < n; ++i)
+ {
+ tree op = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (op) == SSA_NAME
+ && ssa_undefined_value_p (op)
+ && !can_skip_redundant_opnd (op, phi))
+ SET_BIT (uninit_opnds, i);
+ }
+ return uninit_opnds;
+}
+
+/* Find the immediate postdominator PDOM of the specified
+ basic block BLOCK. */
+
+static inline basic_block
+find_pdom (basic_block block)
+{
+ if (block == EXIT_BLOCK_PTR)
+ return EXIT_BLOCK_PTR;
+ else
+ {
+ basic_block bb
+ = get_immediate_dominator (CDI_POST_DOMINATORS, block);
+ if (! bb)
+ return EXIT_BLOCK_PTR;
+ return bb;
+ }
+}
+
+/* Find the immediate DOM of the specified
+ basic block BLOCK. */
+
+static inline basic_block
+find_dom (basic_block block)
+{
+ if (block == ENTRY_BLOCK_PTR)
+ return ENTRY_BLOCK_PTR;
+ else
+ {
+ basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
+ if (! bb)
+ return ENTRY_BLOCK_PTR;
+ return bb;
+ }
+}
+
+/* Returns true if BB1 is postdominating BB2 and BB1 is
+ not a loop exit bb. The loop exit bb check is simple and does
+ not cover all cases. */
+
+static bool
+is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
+{
+ bool is_postdom = false;
+
+ is_postdom = dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1);
+
+ if (!is_postdom)
+ return false;
+
+ if (single_pred_p (bb1) && !single_succ_p (bb2))
+ return false;
+
+ return true;
+}
+
+/* Find the closest postdominator of a specified BB, which is control
+ equivalent to BB. */
+
+static inline basic_block
+find_control_equiv_block (basic_block bb)
+{
+ basic_block pdom;
+
+ pdom = find_pdom (bb);
+
+ /* Skip the postdominating bb that is also loop exit. */
+ if (!is_non_loop_exit_postdominating (pdom, bb))
+ return NULL;
+
+ if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
+ return pdom;
+
+ return NULL;
+}
+
+#define MAX_NUM_CHAINS 8
+#define MAX_CHAIN_LEN 5
+
+/* Computes the control dependence chains (paths of edges)
+ for DEP_BB up to the dominating basic block BB (the head node of a
+ chain should be dominated by it). CD_CHAINS is pointer to a
+ dynamic array holding the result chains. CUR_CD_CHAIN is the current
+ chain being computed. *NUM_CHAINS is total number of chains. The
+ function returns true if the information is successfully computed,
+ return false if there is no control dependence or not computed. */
+
+static bool
+compute_control_dep_chain (basic_block bb, basic_block dep_bb,
+ VEC(edge, heap) **cd_chains,
+ size_t *num_chains,
+ VEC(edge, heap) **cur_cd_chain)
+{
+ edge_iterator ei;
+ edge e;
+ size_t i;
+ bool found_cd_chain = false;
+ size_t cur_chain_len = 0;
+
+ if (EDGE_COUNT (bb->succs) < 2)
+ return false;
+
+ /* Could use a set instead. */
+ cur_chain_len = VEC_length (edge, *cur_cd_chain);
+ if (cur_chain_len > MAX_CHAIN_LEN)
+ return false;
+
+ for (i = 0; i < cur_chain_len; i++)
+ {
+ edge e = VEC_index (edge, *cur_cd_chain, i);
+ /* cycle detected. */
+ if (e->src == bb)
+ return false;
+ }
+
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ basic_block cd_bb;
+ if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
+ continue;
+
+ cd_bb = e->dest;
+ VEC_safe_push (edge, heap, *cur_cd_chain, e);
+ while (!is_non_loop_exit_postdominating (cd_bb, bb))
+ {
+ if (cd_bb == dep_bb)
+ {
+ /* Found a direct control dependence. */
+ if (*num_chains < MAX_NUM_CHAINS)
+ {
+ cd_chains[*num_chains]
+ = VEC_copy (edge, heap, *cur_cd_chain);
+ (*num_chains)++;
+ }
+ found_cd_chain = true;
+ /* check path from next edge. */
+ break;
+ }
+
+ /* Now check if DEP_BB is indirectly control dependent on BB. */
+ if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
+ num_chains, cur_cd_chain))
+ {
+ found_cd_chain = true;
+ break;
+ }
+
+ cd_bb = find_pdom (cd_bb);
+ if (cd_bb == EXIT_BLOCK_PTR)
+ break;
+ }
+ VEC_pop (edge, *cur_cd_chain);
+ gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
+ }
+ gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
+
+ return found_cd_chain;
+}
+
+typedef struct use_pred_info
+{
+ gimple cond;
+ bool invert;
+} *use_pred_info_t;
+
+DEF_VEC_P(use_pred_info_t);
+DEF_VEC_ALLOC_P(use_pred_info_t, heap);
+
+
+/* Converts 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 dependence chains.
+ NUM_CHAINS is the size of the chain array. One edge in a dependence
+ chain is mapped to predicate expression represented by use_pred_info_t
+ type. One dependence chain is converted to a composite predicate that
+ is the result of AND operation of use_pred_info_t mapped to each edge.
+ A composite predicate is presented by a vector of use_pred_info_t. On
+ return, *PREDS points to the resulting array of composite predicates.
+ *NUM_PREDS is the number of composite predictes. */
+
+static bool
+convert_control_dep_chain_into_preds (VEC(edge, heap) **dep_chains,
+ size_t num_chains,
+ VEC(use_pred_info_t, heap) ***preds,
+ size_t *num_preds)
+{
+ bool has_valid_pred = false;
+ size_t i, j;
+ 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) *,
+ num_chains);
+ *num_preds = num_chains;
+
+ for (i = 0; i < num_chains; i++)
+ {
+ VEC(edge, heap) *one_cd_chain = dep_chains[i];
+ for (j = 0; j < VEC_length (edge, one_cd_chain); j++)
+ {
+ gimple cond_stmt;
+ gimple_stmt_iterator gsi;
+ basic_block guard_bb;
+ use_pred_info_t one_pred;
+ edge e;
+
+ e = VEC_index (edge, one_cd_chain, j);
+ guard_bb = e->src;
+ gsi = gsi_last_bb (guard_bb);
+ if (gsi_end_p (gsi))
+ {
+ has_valid_pred = false;
+ break;
+ }
+ cond_stmt = gsi_stmt (gsi);
+ if (gimple_code (cond_stmt) == GIMPLE_CALL
+ && EDGE_COUNT (e->src->succs) >= 2)
+ {
+ /* Ignore EH edge. Can add assertion
+ on the other edge's flag. */
+ continue;
+ }
+ if (gimple_code (cond_stmt) != GIMPLE_COND)
+ {
+ has_valid_pred = false;
+ break;
+ }
+ one_pred = XNEW (struct use_pred_info);
+ 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);
+ }
+
+ if (!has_valid_pred)
+ break;
+ }
+ return has_valid_pred;
+}
+
+/* Computes all control dependence chains for USE_BB. The control
+ dependence chains are then converted to an array of composite
+ predicates pointed to by PREDS. PHI_BB is the basic block of
+ the phi whose result is used in USE_BB. */
+
+static bool
+find_predicates (VEC(use_pred_info_t, heap) ***preds,
+ size_t *num_preds,
+ basic_block phi_bb,
+ basic_block use_bb)
+{
+ size_t num_chains = 0, i;
+ VEC(edge, heap) **dep_chains = 0;
+ VEC(edge, heap) *cur_chain = 0;
+ bool has_valid_pred = false;
+ basic_block cd_root = 0;
+
+ dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
+
+ /* First find the closest bb that is control equivalent to PHI_BB
+ that also dominates USE_BB. */
+ cd_root = phi_bb;
+ while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
+ {
+ basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
+ if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
+ cd_root = ctrl_eq_bb;
+ else
+ break;
+ }
+
+ compute_control_dep_chain (cd_root, use_bb,
+ dep_chains, &num_chains,
+ &cur_chain);
+
+ has_valid_pred
+ = convert_control_dep_chain_into_preds (dep_chains,
+ num_chains,
+ preds,
+ num_preds);
+ /* Free individual chain */
+ VEC_free (edge, heap, cur_chain);
+ for (i = 0; i < num_chains; i++)
+ VEC_free (edge, heap, dep_chains[i]);
+ free (dep_chains);
+ return has_valid_pred;
+}
+
+/* Computes the set of incoming edges of PHI that have non empty
+ definitions of a phi chain. The collection will be done
+ recursively on operands that are defined by phis. CD_ROOT
+ is the control dependence root. *EDGES holds the result, and
+ VISITED_PHIS is a pointer set for detecting cycles. */
+
+static void
+collect_phi_def_edges (gimple phi, basic_block cd_root,
+ VEC(edge, heap) **edges,
+ struct pointer_set_t *visited_phis)
+{
+ size_t i, n;
+ edge opnd_edge;
+ tree opnd;
+
+ if (pointer_set_insert (visited_phis, phi))
+ return;
+
+ n = gimple_phi_num_args (phi);
+ for (i = 0; i < n; i++)
+ {
+ 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);
+ 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);
+ }
+ }
+}
+
+/* For each use edge of PHI, computes all control dependence chains.
+ The control dependence chains are then converted to an array of
+ composite predicates pointed to by PREDS. */
+
+static bool
+find_def_preds (VEC(use_pred_info_t, heap) ***preds,
+ size_t *num_preds, gimple phi)
+{
+ size_t num_chains = 0, i, n;
+ VEC(edge, heap) **dep_chains = 0;
+ VEC(edge, heap) *cur_chain = 0;
+ VEC(edge, heap) *def_edges = 0;
+ bool has_valid_pred = false;
+ basic_block phi_bb, cd_root = 0;
+ struct pointer_set_t *visited_phis;
+
+ dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
+
+ phi_bb = gimple_bb (phi);
+ /* First find the closest dominating bb to be
+ the control dependence root */
+ cd_root = find_dom (phi_bb);
+ if (!cd_root)
+ return false;
+
+ visited_phis = pointer_set_create ();
+ collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
+ pointer_set_destroy (visited_phis);
+
+ n = VEC_length (edge, def_edges);
+ if (n == 0)
+ return false;
+
+ for (i = 0; i < n; i++)
+ {
+ size_t prev_nc, j;
+ edge opnd_edge;
+
+ opnd_edge = VEC_index (edge, def_edges, i);
+ prev_nc = num_chains;
+ compute_control_dep_chain (cd_root, opnd_edge->src,
+ dep_chains, &num_chains,
+ &cur_chain);
+ /* Free individual chain */
+ VEC_free (edge, heap, cur_chain);
+ cur_chain = 0;
+
+ /* Now update the newly added chains with
+ the phi operand edge: */
+ if (EDGE_COUNT (opnd_edge->src->succs) > 1)
+ {
+ if (prev_nc == num_chains
+ && num_chains < MAX_NUM_CHAINS)
+ num_chains++;
+ for (j = prev_nc; j < num_chains; j++)
+ {
+ VEC_safe_push (edge, heap, dep_chains[j], opnd_edge);
+ }
+ }
+ }
+
+ has_valid_pred
+ = convert_control_dep_chain_into_preds (dep_chains,
+ num_chains,
+ preds,
+ num_preds);
+ for (i = 0; i < num_chains; i++)
+ VEC_free (edge, heap, dep_chains[i]);
+ free (dep_chains);
+ return has_valid_pred;
+}
+
+/* Dumps the predicates (PREDS) for USESTMT. */
+
+static void
+dump_predicates (gimple usestmt, size_t num_preds,
+ VEC(use_pred_info_t, heap) **preds,
+ const char* msg)
+{
+ size_t i, j;
+ VEC(use_pred_info_t, heap) *one_pred_chain;
+ fprintf (dump_file, msg);
+ print_gimple_stmt (dump_file, usestmt, 0, 0);
+ fprintf (dump_file, "is guarded by :\n");
+ /* do some dumping here: */
+ for (i = 0; i < num_preds; i++)
+ {
+ size_t np;
+
+ one_pred_chain = preds[i];
+ np = VEC_length (use_pred_info_t, one_pred_chain);
+
+ for (j = 0; j < np; j++)
+ {
+ use_pred_info_t one_pred
+ = VEC_index (use_pred_info_t, one_pred_chain, j);
+ if (one_pred->invert)
+ fprintf (dump_file, " (.NOT.) ");
+ print_gimple_stmt (dump_file, one_pred->cond, 0, 0);
+ if (j < np - 1)
+ fprintf (dump_file, "(.AND.)\n");
+ }
+ if (i < num_preds - 1)
+ fprintf (dump_file, "(.OR.)\n");
+ }
+}
+
+/* Destroys the predicate set *PREDS. */
+
+static void
+destroy_predicate_vecs (size_t n,
+ VEC(use_pred_info_t, heap) ** preds)
+{
+ size_t i, j;
+ for (i = 0; i < n; i++)
+ {
+ for (j = 0; j < VEC_length (use_pred_info_t, preds[i]); j++)
+ free (VEC_index (use_pred_info_t, preds[i], j));
+ VEC_free (use_pred_info_t, heap, preds[i]);
+ }
+ free (preds);
+}
+
+
+/* Computes the 'normalized' conditional code with operand
+ swapping and condition inversion. */
+
+static enum tree_code
+get_cmp_code (enum tree_code orig_cmp_code,
+ bool swap_cond, bool invert)
+{
+ enum tree_code tc = orig_cmp_code;
+
+ if (swap_cond)
+ tc = swap_tree_comparison (orig_cmp_code);
+ if (invert)
+ tc = invert_tree_comparison (tc, false);
+
+ switch (tc)
+ {
+ case LT_EXPR:
+ case LE_EXPR:
+ case GT_EXPR:
+ case GE_EXPR:
+ case EQ_EXPR:
+ case NE_EXPR:
+ break;
+ default:
+ return ERROR_MARK;
+ }
+ return tc;
+}
+
+/* Returns true if VAL falls in the region defined by BOUNDARY and CMPC. */
+
+static bool
+is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
+{
+ bool inverted = false;
+ bool is_unsigned;
+ bool result;
+ /* Only handle integer constant here. */
+ if (TREE_CODE (val) != INTEGER_CST
+ || TREE_CODE (boundary) != INTEGER_CST)
+ return true;
+
+ is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
+
+ if (cmpc == GE_EXPR || cmpc == GT_EXPR
+ || cmpc == NE_EXPR)
+ {
+ cmpc = invert_tree_comparison (cmpc, false);
+ inverted = true;
+ }
+
+ if (is_unsigned)
+ {
+ if (cmpc == EQ_EXPR)
+ result = tree_int_cst_equal (val, boundary);
+ else if (cmpc == LT_EXPR)
+ result = INT_CST_LT_UNSIGNED (val, boundary);
+ else
+ {
+ gcc_assert (cmpc == LE_EXPR);
+ result = (tree_int_cst_equal (val, boundary)
+ || INT_CST_LT_UNSIGNED (val, boundary));
+ }
+ }
+ else
+ {
+ if (cmpc == EQ_EXPR)
+ result = tree_int_cst_equal (val, boundary);
+ else if (cmpc == LT_EXPR)
+ result = INT_CST_LT (val, boundary);
+ else
+ {
+ gcc_assert (cmpc == LE_EXPR);
+ result = (tree_int_cst_equal (val, boundary)
+ || INT_CST_LT (val, boundary));
+ }
+ }
+
+ if (inverted)
+ result ^= 1;
+
+ return result;
+}
+
+/* Returns true if PRED is common among all the predicate
+ chains (PREDS) (and therefore can be factored out).
+ NUM_PRED_CHAIN is the size of array PREDS. */
+
+static bool
+find_matching_predicate_in_rest_chains (use_pred_info_t pred,
+ VEC(use_pred_info_t, heap) **preds,
+ size_t num_pred_chains)
+{
+ size_t i, j, n;
+
+ /* trival case */
+ if (num_pred_chains == 1)
+ return true;
+
+ for (i = 1; i < num_pred_chains; i++)
+ {
+ bool found = false;
+ VEC(use_pred_info_t, heap) *one_chain = preds[i];
+ n = VEC_length (use_pred_info_t, one_chain);
+ for (j = 0; j < n; j++)
+ {
+ use_pred_info_t pred2
+ = VEC_index (use_pred_info_t, one_chain, j);
+ /* can relax the condition comparison to not
+ use address comparison. However, the most common
+ case is that multiple control dependent paths share
+ a common path prefix, so address comparison should
+ be ok. */
+
+ if (pred2->cond == pred->cond
+ && pred2->invert == pred->invert)
+ {
+ found = true;
+ break;
+ }
+ }
+ if (!found)
+ return false;
+ }
+ return true;
+}
+
+/* Forward declaration. */
+static bool
+is_use_properly_guarded (gimple use_stmt,
+ basic_block use_bb,
+ gimple phi,
+ sbitmap uninit_opnds,
+ struct pointer_set_t *visited_phis);
+
+/* 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:
+ Example 1:
+ if (some_cond)
+ {
+ x = ...;
+ flag = true;
+ }
+
+ ... some code ...
+
+ if (flag)
+ use (x);
+
+ The real world examples are usually more complicated, but similar
+ and usually result from inlining:
+
+ bool init_func (int * x)
+ {
+ if (some_cond)
+ return false;
+ *x = ..
+ return true;
+ }
+
+ void foo(..)
+ {
+ int x;
+
+ if (!init_func(&x))
+ return;
+
+ .. some_code ...
+ use (x);
+ }
+
+ Another possible use scenario is in the following trivial example:
+
+ Example 2:
+ if (n > 0)
+ x = 1;
+ ...
+ if (n > 0)
+ {
+ if (m < 2)
+ .. = x;
+ }
+
+ Predicate analysis needs to compute the composite predicate:
+
+ 1) 'x' use predicate: (n > 0) .AND. (m < 2)
+ 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
+ (the predicate chain for phi operand defs can be computed
+ starting from a bb that is control equivalent to the phi's
+ bb and is dominating the operand def.)
+
+ and check overlapping:
+ (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
+ <==> false
+
+ This implementation provides framework that can handle
+ scenarios. (Note that many simple cases are handled properly
+ without the predicate analysis -- this is due to jump threading
+ transformation which eliminates the merge point thus makes
+ path sensitive analysis unnecessary.)
+
+ NUM_PREDS is the number is the number predicate chains, PREDS is
+ the array of chains, PHI is the phi node whose incoming (undefined)
+ paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
+ uninit operand positions. VISITED_PHIS is the pointer set of phi
+ stmts being checked. */
+
+
+static bool
+use_pred_not_overlap_with_undef_path_pred (
+ size_t num_preds,
+ VEC(use_pred_info_t, heap) **preds,
+ gimple phi, sbitmap uninit_opnds,
+ struct pointer_set_t *visited_phis)
+{
+ unsigned int i, n;
+ gimple flag_def = 0;
+ tree boundary_cst = 0;
+ enum tree_code cmp_code;
+ bool swap_cond = false;
+ bool invert = false;
+ VEC(use_pred_info_t, heap) *the_pred_chain;
+ sbitmap_iterator sbi;
+
+ gcc_assert (num_preds > 0);
+ /* Find within the common prefix of multiple predicate chains
+ a predicate that is a comparison of a flag variable against
+ a constant. */
+ the_pred_chain = preds[0];
+ n = VEC_length (use_pred_info_t, the_pred_chain);
+ for (i = 0; i < n; i++)
+ {
+ gimple cond;
+ tree cond_lhs, cond_rhs, flag = 0;
+
+ use_pred_info_t the_pred
+ = VEC_index (use_pred_info_t, the_pred_chain, i);
+
+ cond = the_pred->cond;
+ invert = the_pred->invert;
+ cond_lhs = gimple_cond_lhs (cond);
+ cond_rhs = gimple_cond_rhs (cond);
+ cmp_code = gimple_cond_code (cond);
+
+ if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
+ && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
+ {
+ boundary_cst = cond_rhs;
+ flag = cond_lhs;
+ }
+ else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
+ && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
+ {
+ boundary_cst = cond_lhs;
+ flag = cond_rhs;
+ swap_cond = true;
+ }
+
+ if (!flag)
+ continue;
+
+ flag_def = SSA_NAME_DEF_STMT (flag);
+
+ if (!flag_def)
+ continue;
+
+ if ((gimple_code (flag_def) == GIMPLE_PHI)
+ && (gimple_bb (flag_def) == gimple_bb (phi))
+ && find_matching_predicate_in_rest_chains (
+ the_pred, preds, num_preds))
+ break;
+
+ flag_def = 0;
+ }
+
+ if (!flag_def)
+ return false;
+
+ /* Now check all the uninit incoming edge has a constant flag value
+ that is inconflict with the use guard/predicate. */
+ cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
+
+ if (cmp_code == ERROR_MARK)
+ return false;
+
+ EXECUTE_IF_SET_IN_SBITMAP (uninit_opnds, 0, i, sbi)
+ {
+ tree flag_arg;
+
+ 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;
+ sbitmap uninit_opnds2
+ = compute_uninit_opnds_pos (opnd_def);
+ gcc_assert (!sbitmap_empty_p (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))
+ {
+ sbitmap_free (uninit_opnds2);
+ return false;
+ }
+ sbitmap_free (uninit_opnds2);
+ }
+ else
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* 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
+ || (tc == BIT_AND_EXPR
+ && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE)));
+}
+
+typedef struct norm_cond
+{
+ VEC(gimple, heap) *conds;
+ enum tree_code cond_code;
+ bool invert;
+} *norm_cond_t;
+
+
+/* Normalizes gimple condition COND. The normalization follows
+ UD chains to form larger condition expression trees. NORM_COND
+ holds the normalized result. COND_CODE is the logical opcode
+ (AND or OR) of the normalized tree. */
+
+static void
+normalize_cond_1 (gimple cond,
+ norm_cond_t norm_cond,
+ enum tree_code cond_code)
+{
+ enum gimple_code gc;
+ enum tree_code cur_cond_code;
+
+ gc = gimple_code (cond);
+ if (gc != GIMPLE_ASSIGN)
+ {
+ VEC_safe_push (gimple, heap, norm_cond->conds, cond);
+ return;
+ }
+
+ cur_cond_code = gimple_assign_rhs_code (cond);
+ if (cur_cond_code == NE_EXPR)
+ {
+ if (integer_zerop (gimple_assign_rhs2 (cond))
+ && (TREE_CODE (gimple_assign_rhs1 (cond)) == SSA_NAME))
+ normalize_cond_1 (
+ SSA_NAME_DEF_STMT (gimple_assign_rhs1 (cond)),
+ norm_cond, cond_code);
+ else if (integer_zerop (gimple_assign_rhs1 (cond))
+ && (TREE_CODE (gimple_assign_rhs2 (cond)) == SSA_NAME))
+ normalize_cond_1 (
+ SSA_NAME_DEF_STMT (gimple_assign_rhs2 (cond)),
+ norm_cond, cond_code);
+ else
+ VEC_safe_push (gimple, heap, norm_cond->conds, cond);
+
+ return;
+ }
+
+ if (is_and_or_or (cur_cond_code, TREE_TYPE (gimple_assign_rhs1 (cond)))
+ && (cond_code == cur_cond_code || cond_code == ERROR_MARK))
+ {
+ normalize_cond_1 (SSA_NAME_DEF_STMT (gimple_assign_rhs1 (cond)),
+ norm_cond, cur_cond_code);
+ normalize_cond_1 (SSA_NAME_DEF_STMT (gimple_assign_rhs2 (cond)),
+ norm_cond, cur_cond_code);
+ norm_cond->cond_code = cur_cond_code;
+ }
+ else
+ VEC_safe_push (gimple, heap, norm_cond->conds, cond);
+}
+
+/* See normalize_cond_1 for details. INVERT is a flag to indicate
+ if COND needs to be inverted or not. */
+
+static void
+normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert)
+{
+ enum tree_code cond_code;
+
+ norm_cond->cond_code = ERROR_MARK;
+ norm_cond->invert = false;
+ norm_cond->conds = NULL;
+ gcc_assert (gimple_code (cond) == GIMPLE_COND);
+ cond_code = gimple_cond_code (cond);
+ if (invert)
+ cond_code = invert_tree_comparison (cond_code, false);
+
+ if (cond_code == NE_EXPR)
+ {
+ if (integer_zerop (gimple_cond_rhs (cond))
+ && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME))
+ normalize_cond_1 (
+ SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)),
+ norm_cond, ERROR_MARK);
+ else if (integer_zerop (gimple_cond_lhs (cond))
+ && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME))
+ normalize_cond_1 (
+ SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)),
+ norm_cond, ERROR_MARK);
+ else
+ {
+ VEC_safe_push (gimple, heap, norm_cond->conds, cond);
+ norm_cond->invert = invert;
+ }
+ }
+ else
+ {
+ VEC_safe_push (gimple, heap, norm_cond->conds, cond);
+ norm_cond->invert = invert;
+ }
+
+ gcc_assert (VEC_length (gimple, norm_cond->conds) == 1
+ || is_and_or_or (norm_cond->cond_code, NULL));
+}
+
+/* Returns true if the domain for condition COND1 is a subset of
+ COND2. REVERSE is a flag. when it is true the function checks
+ if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
+ to indicate if COND1 and COND2 need to be inverted or not. */
+
+static bool
+is_gcond_subset_of (gimple cond1, bool invert1,
+ gimple cond2, bool invert2,
+ bool reverse)
+{
+ enum gimple_code gc1, gc2;
+ enum tree_code cond1_code, cond2_code;
+ gimple tmp;
+ tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs;
+
+ /* Take the short cut. */
+ if (cond1 == cond2)
+ return true;
+
+ if (reverse)
+ {
+ tmp = cond1;
+ cond1 = cond2;
+ cond2 = tmp;
+ }
+
+ gc1 = gimple_code (cond1);
+ gc2 = gimple_code (cond2);
+
+ if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND)
+ || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND))
+ return cond1 == cond2;
+
+ cond1_code = ((gc1 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs_code (cond1)
+ : gimple_cond_code (cond1));
+
+ cond2_code = ((gc2 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs_code (cond2)
+ : gimple_cond_code (cond2));
+
+ if (TREE_CODE_CLASS (cond1_code) != tcc_comparison
+ || TREE_CODE_CLASS (cond2_code) != tcc_comparison)
+ return false;
+
+ if (invert1)
+ cond1_code = invert_tree_comparison (cond1_code, false);
+ if (invert2)
+ cond2_code = invert_tree_comparison (cond2_code, false);
+
+ cond1_lhs = ((gc1 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs1 (cond1)
+ : gimple_cond_lhs (cond1));
+ cond1_rhs = ((gc1 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs2 (cond1)
+ : gimple_cond_rhs (cond1));
+ cond2_lhs = ((gc2 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs1 (cond2)
+ : gimple_cond_lhs (cond2));
+ cond2_rhs = ((gc2 == GIMPLE_ASSIGN)
+ ? gimple_assign_rhs2 (cond2)
+ : gimple_cond_rhs (cond2));
+
+ /* Assuming const operands have been swapped to the
+ rhs at this point of the analysis. */
+
+ if (cond1_lhs != cond2_lhs)
+ return false;
+
+ if (!is_gimple_constant (cond1_rhs)
+ || TREE_CODE (cond1_rhs) != INTEGER_CST)
+ return (cond1_rhs == cond2_rhs);
+
+ if (!is_gimple_constant (cond2_rhs)
+ || TREE_CODE (cond2_rhs) != INTEGER_CST)
+ return (cond1_rhs == cond2_rhs);
+
+ if (cond1_code == EQ_EXPR)
+ return is_value_included_in (cond1_rhs,
+ cond2_rhs, cond2_code);
+ if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR)
+ return ((cond2_code == cond1_code)
+ && tree_int_cst_equal (cond1_rhs, cond2_rhs));
+
+ if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR)
+ && (cond2_code == LE_EXPR || cond2_code == LT_EXPR))
+ || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR)
+ && (cond2_code == GE_EXPR || cond2_code == GT_EXPR)))
+ return false;
+
+ if (cond1_code != GE_EXPR && cond1_code != GT_EXPR
+ && cond1_code != LE_EXPR && cond1_code != LT_EXPR)
+ return false;
+
+ if (cond1_code == GT_EXPR)
+ {
+ cond1_code = GE_EXPR;
+ cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs),
+ cond1_rhs,
+ fold_convert (TREE_TYPE (cond1_rhs),
+ integer_one_node));
+ }
+ else if (cond1_code == LT_EXPR)
+ {
+ cond1_code = LE_EXPR;
+ cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs),
+ cond1_rhs,
+ fold_convert (TREE_TYPE (cond1_rhs),
+ integer_one_node));
+ }
+
+ if (!cond1_rhs)
+ return false;
+
+ gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR);
+
+ if (cond2_code == GE_EXPR || cond2_code == GT_EXPR ||
+ cond2_code == LE_EXPR || cond2_code == LT_EXPR)
+ return is_value_included_in (cond1_rhs,
+ cond2_rhs, cond2_code);
+ else if (cond2_code == NE_EXPR)
+ return
+ (is_value_included_in (cond1_rhs,
+ cond2_rhs, cond2_code)
+ && !is_value_included_in (cond2_rhs,
+ cond1_rhs, cond1_code));
+ return false;
+}
+
+/* Returns true if the domain of the condition expression
+ in COND is a subset of any of the sub-conditions
+ of the normalized condtion NORM_COND. INVERT is a flag
+ to indicate of the COND needs to be inverted.
+ REVERSE is a flag. When it is true, the check is reversed --
+ it returns true if COND is a superset of any of the subconditions
+ of NORM_COND. */
+
+static bool
+is_subset_of_any (gimple cond, bool invert,
+ norm_cond_t norm_cond, bool reverse)
+{
+ size_t i;
+ size_t len = VEC_length (gimple, norm_cond->conds);
+
+ for (i = 0; i < len; i++)
+ {
+ if (is_gcond_subset_of (cond, invert,
+ VEC_index (gimple, norm_cond->conds, i),
+ false, reverse))
+ return true;
+ }
+ return false;
+}
+
+/* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
+ expressions (formed by following UD chains not control
+ dependence chains). The function returns true of domain
+ of and expression NORM_COND1 is a subset of NORM_COND2's.
+ The implementation is conservative, and it returns false if
+ it the inclusion relationship may not hold. */
+
+static bool
+is_or_set_subset_of (norm_cond_t norm_cond1,
+ norm_cond_t norm_cond2)
+{
+ size_t i;
+ size_t len = VEC_length (gimple, norm_cond1->conds);
+
+ for (i = 0; i < len; i++)
+ {
+ if (!is_subset_of_any (VEC_index (gimple, norm_cond1->conds, i),
+ false, norm_cond2, false))
+ return false;
+ }
+ return true;
+}
+
+/* NORM_COND1 and NORM_COND2 are normalized logical AND
+ expressions (formed by following UD chains not control
+ dependence chains). The function returns true of domain
+ of and expression NORM_COND1 is a subset of NORM_COND2's. */
+
+static bool
+is_and_set_subset_of (norm_cond_t norm_cond1,
+ norm_cond_t norm_cond2)
+{
+ size_t i;
+ size_t len = VEC_length (gimple, norm_cond2->conds);
+
+ for (i = 0; i < len; i++)
+ {
+ if (!is_subset_of_any (VEC_index (gimple, norm_cond2->conds, i),
+ false, norm_cond1, true))
+ return false;
+ }
+ return true;
+}
+
+/* Returns true of the domain if NORM_COND1 is a subset
+ of that of NORM_COND2. Returns false if it can not be
+ proved to be so. */
+
+static bool
+is_norm_cond_subset_of (norm_cond_t norm_cond1,
+ norm_cond_t norm_cond2)
+{
+ size_t i;
+ enum tree_code code1, code2;
+
+ code1 = norm_cond1->cond_code;
+ code2 = norm_cond2->cond_code;
+
+ if (code1 == TRUTH_AND_EXPR || code1 == BIT_AND_EXPR)
+ {
+ /* Both conditions are AND expressions. */
+ if (code2 == TRUTH_AND_EXPR || 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)
+ {
+ size_t len1;
+ len1 = VEC_length (gimple, norm_cond1->conds);
+ for (i = 0; i < len1; i++)
+ {
+ gimple cond1 = VEC_index (gimple, norm_cond1->conds, i);
+ if (is_subset_of_any (cond1, false, norm_cond2, false))
+ return true;
+ }
+ return false;
+ }
+ else
+ {
+ gcc_assert (code2 == ERROR_MARK);
+ gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
+ return is_subset_of_any (VEC_index (gimple, norm_cond2->conds, 0),
+ norm_cond2->invert, norm_cond1, true);
+ }
+ }
+ /* NORM_COND1 is an OR expression */
+ else if (code1 == TRUTH_OR_EXPR || code1 == BIT_IOR_EXPR)
+ {
+ if (code2 != code1)
+ return false;
+
+ return is_or_set_subset_of (norm_cond1, norm_cond2);
+ }
+ else
+ {
+ gcc_assert (code1 == ERROR_MARK);
+ 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)
+ return false;
+
+ if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
+ return is_subset_of_any (VEC_index (gimple, norm_cond1->conds, 0),
+ norm_cond1->invert, norm_cond2, false);
+
+ gcc_assert (code2 == ERROR_MARK);
+ gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
+ return is_gcond_subset_of (VEC_index (gimple, norm_cond1->conds, 0),
+ norm_cond1->invert,
+ VEC_index (gimple, norm_cond2->conds, 0),
+ norm_cond2->invert, false);
+ }
+}
+
+/* Returns true of the domain of single predicate expression
+ EXPR1 is a subset of that of EXPR2. Returns false if it
+ can not be proved. */
+
+static bool
+is_pred_expr_subset_of (use_pred_info_t expr1,
+ use_pred_info_t expr2)
+{
+ gimple cond1, cond2;
+ enum tree_code code1, code2;
+ struct norm_cond norm_cond1, norm_cond2;
+ bool is_subset = false;
+
+ cond1 = expr1->cond;
+ cond2 = expr2->cond;
+ code1 = gimple_cond_code (cond1);
+ code2 = gimple_cond_code (cond2);
+
+ if (expr1->invert)
+ code1 = invert_tree_comparison (code1, false);
+ if (expr2->invert)
+ code2 = invert_tree_comparison (code2, false);
+
+ /* Fast path -- match exactly */
+ if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2))
+ && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2))
+ && (code1 == code2))
+ return true;
+
+ /* Normalize conditions. To keep NE_EXPR, do not invert
+ with both need inversion. */
+ normalize_cond (cond1, &norm_cond1, (expr1->invert));
+ normalize_cond (cond2, &norm_cond2, (expr2->invert));
+
+ is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2);
+
+ /* Free memory */
+ VEC_free (gimple, heap, norm_cond1.conds);
+ VEC_free (gimple, heap, norm_cond2.conds);
+ return is_subset ;
+}
+
+/* Returns true if the domain of PRED1 is a subset
+ of that of PRED2. Returns false if it can not be proved so. */
+
+static bool
+is_pred_chain_subset_of (VEC(use_pred_info_t, heap) *pred1,
+ VEC(use_pred_info_t, heap) *pred2)
+{
+ size_t np1, np2, i1, i2;
+
+ np1 = VEC_length (use_pred_info_t, pred1);
+ np2 = VEC_length (use_pred_info_t, pred2);
+
+ for (i2 = 0; i2 < np2; i2++)
+ {
+ bool found = false;
+ use_pred_info_t info2
+ = VEC_index (use_pred_info_t, pred2, i2);
+ for (i1 = 0; i1 < np1; i1++)
+ {
+ use_pred_info_t info1
+ = VEC_index (use_pred_info_t, pred1, i1);
+ if (is_pred_expr_subset_of (info1, info2))
+ {
+ found = true;
+ break;
+ }
+ }
+ if (!found)
+ return false;
+ }
+ return true;
+}
+
+/* Returns true if the domain defined by
+ one pred chain ONE_PRED is a subset of the domain
+ of *PREDS. It returns false if ONE_PRED's domain is
+ not a subset of any of the sub-domains of PREDS (
+ corresponding to each individual chains in it), even
+ though it may be still be a subset of whole domain
+ of PREDS which is the union (ORed) of all its subdomains.
+ In other words, the result is conservative. */
+
+static bool
+is_included_in (VEC(use_pred_info_t, heap) *one_pred,
+ VEC(use_pred_info_t, heap) **preds,
+ size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; i++)
+ {
+ if (is_pred_chain_subset_of (one_pred, preds[i]))
+ return true;
+ }
+
+ return false;
+}
+
+/* compares two predicate sets PREDS1 and PREDS2 and returns
+ true if the domain defined by PREDS1 is a superset
+ of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
+ PREDS2 respectively. The implementation chooses not to build
+ generic trees (and relying on the folding capability of the
+ compiler), but instead performs brute force comparison of
+ individual predicate chains (won't be a compile time problem
+ as the chains are pretty short). When the function returns
+ false, it does not necessarily mean *PREDS1 is not a superset
+ of *PREDS2, but mean it may not be so since the analysis can
+ not prove it. In such cases, false warnings may still be
+ emitted. */
+
+static bool
+is_superset_of (VEC(use_pred_info_t, heap) **preds1,
+ size_t n1,
+ VEC(use_pred_info_t, heap) **preds2,
+ size_t n2)
+{
+ size_t i;
+ VEC(use_pred_info_t, heap) *one_pred_chain;
+
+ for (i = 0; i < n2; i++)
+ {
+ one_pred_chain = preds2[i];
+ if (!is_included_in (one_pred_chain, preds1, n1))
+ return false;
+ }
+
+ 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
+ true if it can be determined that the use of PHI's def in
+ USE_STMT is guarded with a predicate set not overlapping with
+ predicate sets of all runtime paths that do not have a definition.
+ Returns false if it is not or it can not 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 src bb of the operand edge). UNINIT_OPNDS
+ is a bit vector. If an operand of PHI is uninitialized, the
+ correponding bit in the vector is 1. VISIED_PHIS is a pointer
+ set of phis being visted. */
+
+static bool
+is_use_properly_guarded (gimple use_stmt,
+ basic_block use_bb,
+ gimple phi,
+ sbitmap uninit_opnds,
+ struct pointer_set_t *visited_phis)
+{
+ basic_block phi_bb;
+ VEC(use_pred_info_t, heap) **preds = 0;
+ VEC(use_pred_info_t, heap) **def_preds = 0;
+ size_t num_preds = 0, num_def_preds = 0;
+ bool has_valid_preds = false;
+ bool is_properly_guarded = false;
+
+ if (pointer_set_insert (visited_phis, phi))
+ return false;
+
+ phi_bb = gimple_bb (phi);
+
+ if (is_non_loop_exit_postdominating (use_bb, phi_bb))
+ return false;
+
+ has_valid_preds = find_predicates (&preds, &num_preds,
+ phi_bb, use_bb);
+
+ if (!has_valid_preds)
+ {
+ destroy_predicate_vecs (num_preds, preds);
+ return false;
+ }
+
+ if (dump_file)
+ dump_predicates (use_stmt, num_preds, preds,
+ "Use in stmt ");
+
+ has_valid_preds = find_def_preds (&def_preds,
+ &num_def_preds, phi);
+
+ if (has_valid_preds)
+ {
+ if (dump_file)
+ 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);
+ }
+
+ /* further prune the dead incoming phi edges. */
+ if (!is_properly_guarded)
+ is_properly_guarded
+ = use_pred_not_overlap_with_undef_path_pred (
+ num_preds, preds, phi, uninit_opnds, visited_phis);
+
+ destroy_predicate_vecs (num_preds, preds);
+ destroy_predicate_vecs (num_def_preds, def_preds);
+ return is_properly_guarded;
+}
+
+/* Searches through all uses of a potentially
+ uninitialized variable defined by PHI and returns a use
+ statement if the use is not properly guarded. It returns
+ NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
+ holding the position(s) of uninit PHI operands. */
+
+static gimple
+find_uninit_use (gimple phi, sbitmap uninit_opnds)
+{
+ tree phi_result;
+ use_operand_p use_p;
+ gimple use_stmt;
+ imm_use_iterator iter;
+
+ phi_result = gimple_phi_result (phi);
+
+ FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
+ {
+ struct pointer_set_t *visited_phis;
+ use_stmt = use_p->loc.stmt;
+
+ visited_phis = pointer_set_create ();
+
+ if (gimple_code (use_stmt) == GIMPLE_PHI
+ || is_use_properly_guarded (use_stmt,
+ gimple_bb (use_stmt),
+ phi,
+ uninit_opnds,
+ visited_phis))
+ {
+ pointer_set_destroy (visited_phis);
+ continue;
+ }
+
+ pointer_set_destroy (visited_phis);
+
+ return use_stmt;
+ }
+
+ return NULL;
+}
+
+/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
+ and gives warning if there exists a runtime path from the entry to a
+ use of the PHI def that does not contain a definition. In other words,
+ the warning is on the real use. The more dead paths that can be pruned
+ by the compiler, the fewer false positives the warning is. */
+
+static void
+warn_uninitialized_phi (gimple phi)
+{
+ size_t n;
+ sbitmap uninit_opnds;
+ gimple uninit_use_stmt = 0;
+
+ n = gimple_phi_num_args (phi);
+ /* Don't look at memory tags. */
+ if (!is_gimple_reg (gimple_phi_result (phi)))
+ return;
+
+ uninit_opnds = compute_uninit_opnds_pos (phi);
+
+ if (sbitmap_empty_p (uninit_opnds))
+ {
+ sbitmap_free (uninit_opnds);
+ return;
+ }
+
+ /* Now check if we have any use of the value without proper guard. */
+ uninit_use_stmt = find_uninit_use (phi, uninit_opnds);
+
+ /* All uses are properly guarded. */
+ if (!uninit_use_stmt)
+ {
+ sbitmap_free (uninit_opnds);
+ return;
+ }
+
+ warn_uninit (gimple_phi_arg_def (phi, sbitmap_first_set_bit (uninit_opnds)),
+ "%qD may be used uninitialized in this function",
+ uninit_use_stmt);
+
+ sbitmap_free (uninit_opnds);
+
+}
+
+/* Computes the set of SSA names that are possibly undefined. A SSA name is
+ considered possibly undefined if it is defined by a PHI with at least one
+ operand that is not defined or possibly not defined (the definition is
+ recursive). */
+
+static void
+compute_possibly_undefined_names (void)
+{
+ basic_block bb = 0;
+ VEC(gimple, heap) *worklist = 0;
+ gimple_stmt_iterator gsi;
+
+ possibly_undefined_names = pointer_set_create ();
+
+ FOR_EACH_BB (bb)
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ size_t n, i;
+
+ n = gimple_phi_num_args (phi);
+
+ /* Don't look at memory tags. */
+ if (!is_gimple_reg (gimple_phi_result (phi)))
+ continue;
+
+ for (i = 0; i < n; ++i)
+ {
+ tree op = gimple_phi_arg_def (phi, i);
+ if (TREE_CODE (op) == SSA_NAME
+ && ssa_undefined_value_p (op))
+ {
+ VEC_safe_push (gimple, heap, worklist, phi);
+ pointer_set_insert (possibly_undefined_names,
+ gimple_phi_result (phi));
+ break;
+ }
+ }
+ }
+
+ while (VEC_length (gimple, worklist) != 0)
+ {
+ gimple cur_phi = 0;
+ use_operand_p use_p = 0;
+ gimple use_stmt = 0;
+ imm_use_iterator iter;
+ tree phi_result = 0;
+
+ cur_phi = VEC_pop (gimple, worklist);
+ phi_result = gimple_phi_result (cur_phi);
+ FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
+ {
+ use_stmt = use_p->loc.stmt;
+ if (gimple_code (use_stmt) == GIMPLE_PHI
+ && !pointer_set_insert (possibly_undefined_names,
+ gimple_phi_result (use_stmt)))
+ VEC_safe_push (gimple, heap, worklist, use_stmt);
+ }
+ }
+}
+
+
+/* Entry point to the late uninitialized warning pass. */
+
+static unsigned int
+execute_late_warn_uninitialized (void)
+{
+ basic_block bb;
+ gimple_stmt_iterator gsi;
+
+ calculate_dominance_info (CDI_DOMINATORS);
+ calculate_dominance_info (CDI_POST_DOMINATORS);
+ /* Re-do the plain uninitialized variable check, as optimization may have
+ straightened control flow. Do this first so that we don't accidentally
+ get a "may be" warning when we'd have seen an "is" warning later. */
+ warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
+
+ timevar_push (TV_TREE_UNINIT);
+ /* Now compute the possibly uninitialized variable set. */
+ compute_possibly_undefined_names ();
+
+ FOR_EACH_BB (bb)
+ for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ warn_uninitialized_phi (gsi_stmt (gsi));
+
+ pointer_set_destroy (possibly_undefined_names);
+ possibly_undefined_names = NULL;
+ free_dominance_info (CDI_POST_DOMINATORS);
+ timevar_pop (TV_TREE_UNINIT);
+ return 0;
+}
+
+static bool
+gate_warn_uninitialized (void)
+{
+ return warn_uninitialized != 0;
+}
+
+struct gimple_opt_pass pass_late_warn_uninitialized =
+{
+ {
+ GIMPLE_PASS,
+ "uninit", /* name */
+ gate_warn_uninitialized, /* gate */
+ execute_late_warn_uninitialized, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+ }
+};