1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
32 #include "pointer-set.h"
33 #include "tree-flow.h"
35 #include "tree-inline.h"
37 #include "tree-pass.h"
38 #include "diagnostic-core.h"
40 /* This implements the pass that does predicate aware warning on uses of
41 possibly uninitialized variables. The pass first collects the set of
42 possibly uninitialized SSA names. For each such name, it walks through
43 all its immediate uses. For each immediate use, it rebuilds the condition
44 expression (the predicate) that guards the use. The predicate is then
45 examined to see if the variable is always defined under that same condition.
46 This is done either by pruning the unrealizable paths that lead to the
47 default definitions or by checking if the predicate set that guards the
48 defining paths is a superset of the use predicate. */
51 /* Pointer set of potentially undefined ssa names, i.e.,
52 ssa names that are defined by phi with operands that
53 are not defined or potentially undefined. */
54 static struct pointer_set_t *possibly_undefined_names = 0;
56 /* Bit mask handling macros. */
57 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
58 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
59 #define MASK_EMPTY(mask) (mask == 0)
61 /* Returns the first bit position (starting from LSB)
62 in mask that is non zero. Returns -1 if the mask is empty. */
64 get_mask_first_set_bit (unsigned mask)
70 while ((mask & (1 << pos)) == 0)
75 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
78 /* Return true if T, an SSA_NAME, has an undefined value. */
81 ssa_undefined_value_p (tree t)
83 tree var = SSA_NAME_VAR (t);
87 /* Parameters get their initial value from the function entry. */
88 else if (TREE_CODE (var) == PARM_DECL)
90 /* When returning by reference the return address is actually a hidden
92 else if (TREE_CODE (var) == RESULT_DECL && DECL_BY_REFERENCE (var))
94 /* Hard register variables get their initial value from the ether. */
95 else if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
98 /* The value is undefined iff its definition statement is empty. */
99 return (gimple_nop_p (SSA_NAME_DEF_STMT (t))
100 || (possibly_undefined_names
101 && pointer_set_contains (possibly_undefined_names, t)));
104 /* Like ssa_undefined_value_p, but don't return true if TREE_NO_WARNING
105 is set on SSA_NAME_VAR. */
108 uninit_undefined_value_p (tree t)
110 if (!ssa_undefined_value_p (t))
112 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
117 /* Checks if the operand OPND of PHI is defined by
118 another phi with one operand defined by this PHI,
119 but the rest operands are all defined. If yes,
120 returns true to skip this this operand as being
121 redundant. Can be enhanced to be more general. */
124 can_skip_redundant_opnd (tree opnd, gimple phi)
130 phi_def = gimple_phi_result (phi);
131 op_def = SSA_NAME_DEF_STMT (opnd);
132 if (gimple_code (op_def) != GIMPLE_PHI)
134 n = gimple_phi_num_args (op_def);
135 for (i = 0; i < n; ++i)
137 tree op = gimple_phi_arg_def (op_def, i);
138 if (TREE_CODE (op) != SSA_NAME)
140 if (op != phi_def && uninit_undefined_value_p (op))
147 /* Returns a bit mask holding the positions of arguments in PHI
148 that have empty (or possibly empty) definitions. */
151 compute_uninit_opnds_pos (gimple phi)
154 unsigned uninit_opnds = 0;
156 n = gimple_phi_num_args (phi);
157 /* Bail out for phi with too many args. */
161 for (i = 0; i < n; ++i)
163 tree op = gimple_phi_arg_def (phi, i);
164 if (TREE_CODE (op) == SSA_NAME
165 && uninit_undefined_value_p (op)
166 && !can_skip_redundant_opnd (op, phi))
167 MASK_SET_BIT (uninit_opnds, i);
172 /* Find the immediate postdominator PDOM of the specified
173 basic block BLOCK. */
175 static inline basic_block
176 find_pdom (basic_block block)
178 if (block == EXIT_BLOCK_PTR)
179 return EXIT_BLOCK_PTR;
183 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
185 return EXIT_BLOCK_PTR;
190 /* Find the immediate DOM of the specified
191 basic block BLOCK. */
193 static inline basic_block
194 find_dom (basic_block block)
196 if (block == ENTRY_BLOCK_PTR)
197 return ENTRY_BLOCK_PTR;
200 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
202 return ENTRY_BLOCK_PTR;
207 /* Returns true if BB1 is postdominating BB2 and BB1 is
208 not a loop exit bb. The loop exit bb check is simple and does
209 not cover all cases. */
212 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
214 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
217 if (single_pred_p (bb1) && !single_succ_p (bb2))
223 /* Find the closest postdominator of a specified BB, which is control
226 static inline basic_block
227 find_control_equiv_block (basic_block bb)
231 pdom = find_pdom (bb);
233 /* Skip the postdominating bb that is also loop exit. */
234 if (!is_non_loop_exit_postdominating (pdom, bb))
237 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
243 #define MAX_NUM_CHAINS 8
244 #define MAX_CHAIN_LEN 5
245 #define MAX_POSTDOM_CHECK 8
247 /* Computes the control dependence chains (paths of edges)
248 for DEP_BB up to the dominating basic block BB (the head node of a
249 chain should be dominated by it). CD_CHAINS is pointer to a
250 dynamic array holding the result chains. CUR_CD_CHAIN is the current
251 chain being computed. *NUM_CHAINS is total number of chains. The
252 function returns true if the information is successfully computed,
253 return false if there is no control dependence or not computed. */
256 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
257 vec<edge> *cd_chains,
259 vec<edge> *cur_cd_chain)
264 bool found_cd_chain = false;
265 size_t cur_chain_len = 0;
267 if (EDGE_COUNT (bb->succs) < 2)
270 /* Could use a set instead. */
271 cur_chain_len = cur_cd_chain->length ();
272 if (cur_chain_len > MAX_CHAIN_LEN)
275 for (i = 0; i < cur_chain_len; i++)
277 edge e = (*cur_cd_chain)[i];
278 /* cycle detected. */
283 FOR_EACH_EDGE (e, ei, bb->succs)
286 int post_dom_check = 0;
287 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
291 cur_cd_chain->safe_push (e);
292 while (!is_non_loop_exit_postdominating (cd_bb, bb))
296 /* Found a direct control dependence. */
297 if (*num_chains < MAX_NUM_CHAINS)
299 cd_chains[*num_chains] = cur_cd_chain->copy ();
302 found_cd_chain = true;
303 /* check path from next edge. */
307 /* Now check if DEP_BB is indirectly control dependent on BB. */
308 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
309 num_chains, cur_cd_chain))
311 found_cd_chain = true;
315 cd_bb = find_pdom (cd_bb);
317 if (cd_bb == EXIT_BLOCK_PTR || post_dom_check > MAX_POSTDOM_CHECK)
320 cur_cd_chain->pop ();
321 gcc_assert (cur_cd_chain->length () == cur_chain_len);
323 gcc_assert (cur_cd_chain->length () == cur_chain_len);
325 return found_cd_chain;
328 typedef struct use_pred_info
336 /* Converts the chains of control dependence edges into a set of
337 predicates. A control dependence chain is represented by a vector
338 edges. DEP_CHAINS points to an array of dependence chains.
339 NUM_CHAINS is the size of the chain array. One edge in a dependence
340 chain is mapped to predicate expression represented by use_pred_info_t
341 type. One dependence chain is converted to a composite predicate that
342 is the result of AND operation of use_pred_info_t mapped to each edge.
343 A composite predicate is presented by a vector of use_pred_info_t. On
344 return, *PREDS points to the resulting array of composite predicates.
345 *NUM_PREDS is the number of composite predictes. */
348 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
350 vec<use_pred_info_t> **preds,
353 bool has_valid_pred = false;
355 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
358 /* Now convert the control dep chain into a set
360 typedef vec<use_pred_info_t> vec_use_pred_info_t_heap;
361 *preds = XCNEWVEC (vec_use_pred_info_t_heap, num_chains);
362 *num_preds = num_chains;
364 for (i = 0; i < num_chains; i++)
366 vec<edge> one_cd_chain = dep_chains[i];
368 has_valid_pred = false;
369 for (j = 0; j < one_cd_chain.length (); j++)
372 gimple_stmt_iterator gsi;
373 basic_block guard_bb;
374 use_pred_info_t one_pred;
379 gsi = gsi_last_bb (guard_bb);
382 has_valid_pred = false;
385 cond_stmt = gsi_stmt (gsi);
386 if (gimple_code (cond_stmt) == GIMPLE_CALL
387 && EDGE_COUNT (e->src->succs) >= 2)
389 /* Ignore EH edge. Can add assertion
390 on the other edge's flag. */
393 /* Skip if there is essentially one succesor. */
394 if (EDGE_COUNT (e->src->succs) == 2)
400 FOR_EACH_EDGE (e1, ei1, e->src->succs)
402 if (EDGE_COUNT (e1->dest->succs) == 0)
411 if (gimple_code (cond_stmt) != GIMPLE_COND)
413 has_valid_pred = false;
416 one_pred = XNEW (struct use_pred_info);
417 one_pred->cond = cond_stmt;
418 one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE);
419 (*preds)[i].safe_push (one_pred);
420 has_valid_pred = true;
426 return has_valid_pred;
429 /* Computes all control dependence chains for USE_BB. The control
430 dependence chains are then converted to an array of composite
431 predicates pointed to by PREDS. PHI_BB is the basic block of
432 the phi whose result is used in USE_BB. */
435 find_predicates (vec<use_pred_info_t> **preds,
440 size_t num_chains = 0, i;
441 vec<edge> *dep_chains = 0;
442 vec<edge> cur_chain = vNULL;
443 bool has_valid_pred = false;
444 basic_block cd_root = 0;
446 typedef vec<edge> vec_edge_heap;
447 dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS);
449 /* First find the closest bb that is control equivalent to PHI_BB
450 that also dominates USE_BB. */
452 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
454 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
455 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
456 cd_root = ctrl_eq_bb;
461 compute_control_dep_chain (cd_root, use_bb,
462 dep_chains, &num_chains,
466 = convert_control_dep_chain_into_preds (dep_chains,
470 /* Free individual chain */
471 cur_chain.release ();
472 for (i = 0; i < num_chains; i++)
473 dep_chains[i].release ();
475 return has_valid_pred;
478 /* Computes the set of incoming edges of PHI that have non empty
479 definitions of a phi chain. The collection will be done
480 recursively on operands that are defined by phis. CD_ROOT
481 is the control dependence root. *EDGES holds the result, and
482 VISITED_PHIS is a pointer set for detecting cycles. */
485 collect_phi_def_edges (gimple phi, basic_block cd_root,
487 struct pointer_set_t *visited_phis)
493 if (pointer_set_insert (visited_phis, phi))
496 n = gimple_phi_num_args (phi);
497 for (i = 0; i < n; i++)
499 opnd_edge = gimple_phi_arg_edge (phi, i);
500 opnd = gimple_phi_arg_def (phi, i);
502 if (TREE_CODE (opnd) != SSA_NAME)
504 if (dump_file && (dump_flags & TDF_DETAILS))
506 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
507 print_gimple_stmt (dump_file, phi, 0, 0);
509 edges->safe_push (opnd_edge);
513 gimple def = SSA_NAME_DEF_STMT (opnd);
515 if (gimple_code (def) == GIMPLE_PHI
516 && dominated_by_p (CDI_DOMINATORS,
517 gimple_bb (def), cd_root))
518 collect_phi_def_edges (def, cd_root, edges,
520 else if (!uninit_undefined_value_p (opnd))
522 if (dump_file && (dump_flags & TDF_DETAILS))
524 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
525 print_gimple_stmt (dump_file, phi, 0, 0);
527 edges->safe_push (opnd_edge);
533 /* For each use edge of PHI, computes all control dependence chains.
534 The control dependence chains are then converted to an array of
535 composite predicates pointed to by PREDS. */
538 find_def_preds (vec<use_pred_info_t> **preds,
539 size_t *num_preds, gimple phi)
541 size_t num_chains = 0, i, n;
542 vec<edge> *dep_chains = 0;
543 vec<edge> cur_chain = vNULL;
544 vec<edge> def_edges = vNULL;
545 bool has_valid_pred = false;
546 basic_block phi_bb, cd_root = 0;
547 struct pointer_set_t *visited_phis;
549 typedef vec<edge> vec_edge_heap;
550 dep_chains = XCNEWVEC (vec_edge_heap, MAX_NUM_CHAINS);
552 phi_bb = gimple_bb (phi);
553 /* First find the closest dominating bb to be
554 the control dependence root */
555 cd_root = find_dom (phi_bb);
559 visited_phis = pointer_set_create ();
560 collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
561 pointer_set_destroy (visited_phis);
563 n = def_edges.length ();
567 for (i = 0; i < n; i++)
572 opnd_edge = def_edges[i];
573 prev_nc = num_chains;
574 compute_control_dep_chain (cd_root, opnd_edge->src,
575 dep_chains, &num_chains,
577 /* Free individual chain */
578 cur_chain.release ();
580 /* Now update the newly added chains with
581 the phi operand edge: */
582 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
584 if (prev_nc == num_chains
585 && num_chains < MAX_NUM_CHAINS)
587 for (j = prev_nc; j < num_chains; j++)
589 dep_chains[j].safe_push (opnd_edge);
595 = convert_control_dep_chain_into_preds (dep_chains,
599 for (i = 0; i < num_chains; i++)
600 dep_chains[i].release ();
602 return has_valid_pred;
605 /* Dumps the predicates (PREDS) for USESTMT. */
608 dump_predicates (gimple usestmt, size_t num_preds,
609 vec<use_pred_info_t> *preds,
613 vec<use_pred_info_t> one_pred_chain;
614 fprintf (dump_file, msg);
615 print_gimple_stmt (dump_file, usestmt, 0, 0);
616 fprintf (dump_file, "is guarded by :\n");
617 /* do some dumping here: */
618 for (i = 0; i < num_preds; i++)
622 one_pred_chain = preds[i];
623 np = one_pred_chain.length ();
625 for (j = 0; j < np; j++)
627 use_pred_info_t one_pred
629 if (one_pred->invert)
630 fprintf (dump_file, " (.NOT.) ");
631 print_gimple_stmt (dump_file, one_pred->cond, 0, 0);
633 fprintf (dump_file, "(.AND.)\n");
635 if (i < num_preds - 1)
636 fprintf (dump_file, "(.OR.)\n");
640 /* Destroys the predicate set *PREDS. */
643 destroy_predicate_vecs (size_t n,
644 vec<use_pred_info_t> * preds)
647 for (i = 0; i < n; i++)
649 for (j = 0; j < preds[i].length (); j++)
657 /* Computes the 'normalized' conditional code with operand
658 swapping and condition inversion. */
660 static enum tree_code
661 get_cmp_code (enum tree_code orig_cmp_code,
662 bool swap_cond, bool invert)
664 enum tree_code tc = orig_cmp_code;
667 tc = swap_tree_comparison (orig_cmp_code);
669 tc = invert_tree_comparison (tc, false);
686 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
687 all values in the range satisfies (x CMPC BOUNDARY) == true. */
690 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
692 bool inverted = false;
696 /* Only handle integer constant here. */
697 if (TREE_CODE (val) != INTEGER_CST
698 || TREE_CODE (boundary) != INTEGER_CST)
701 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
703 if (cmpc == GE_EXPR || cmpc == GT_EXPR
706 cmpc = invert_tree_comparison (cmpc, false);
713 result = tree_int_cst_equal (val, boundary);
714 else if (cmpc == LT_EXPR)
715 result = INT_CST_LT_UNSIGNED (val, boundary);
718 gcc_assert (cmpc == LE_EXPR);
719 result = (tree_int_cst_equal (val, boundary)
720 || INT_CST_LT_UNSIGNED (val, boundary));
726 result = tree_int_cst_equal (val, boundary);
727 else if (cmpc == LT_EXPR)
728 result = INT_CST_LT (val, boundary);
731 gcc_assert (cmpc == LE_EXPR);
732 result = (tree_int_cst_equal (val, boundary)
733 || INT_CST_LT (val, boundary));
743 /* Returns true if PRED is common among all the predicate
744 chains (PREDS) (and therefore can be factored out).
745 NUM_PRED_CHAIN is the size of array PREDS. */
748 find_matching_predicate_in_rest_chains (use_pred_info_t pred,
749 vec<use_pred_info_t> *preds,
750 size_t num_pred_chains)
755 if (num_pred_chains == 1)
758 for (i = 1; i < num_pred_chains; i++)
761 vec<use_pred_info_t> one_chain = preds[i];
762 n = one_chain.length ();
763 for (j = 0; j < n; j++)
765 use_pred_info_t pred2
767 /* can relax the condition comparison to not
768 use address comparison. However, the most common
769 case is that multiple control dependent paths share
770 a common path prefix, so address comparison should
773 if (pred2->cond == pred->cond
774 && pred2->invert == pred->invert)
786 /* Forward declaration. */
788 is_use_properly_guarded (gimple use_stmt,
791 unsigned uninit_opnds,
792 struct pointer_set_t *visited_phis);
794 /* Returns true if all uninitialized opnds are pruned. Returns false
795 otherwise. PHI is the phi node with uninitialized operands,
796 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
797 FLAG_DEF is the statement defining the flag guarding the use of the
798 PHI output, BOUNDARY_CST is the const value used in the predicate
799 associated with the flag, CMP_CODE is the comparison code used in
800 the predicate, VISITED_PHIS is the pointer set of phis visited, and
801 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
807 flag_1 = phi <0, 1> // (1)
808 var_1 = phi <undef, some_val>
812 flag_2 = phi <0, flag_1, flag_1> // (2)
813 var_2 = phi <undef, var_1, var_1>
820 Because some flag arg in (1) is not constant, if we do not look into the
821 flag phis recursively, it is conservatively treated as unknown and var_1
822 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
823 a false warning will be emitted. Checking recursively into (1), the compiler can
824 find out that only some_val (which is defined) can flow into (3) which is OK.
829 prune_uninit_phi_opnds_in_unrealizable_paths (
830 gimple phi, unsigned uninit_opnds,
831 gimple flag_def, tree boundary_cst,
832 enum tree_code cmp_code,
833 struct pointer_set_t *visited_phis,
834 bitmap *visited_flag_phis)
838 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
842 if (!MASK_TEST_BIT (uninit_opnds, i))
845 flag_arg = gimple_phi_arg_def (flag_def, i);
846 if (!is_gimple_constant (flag_arg))
848 gimple flag_arg_def, phi_arg_def;
850 unsigned uninit_opnds_arg_phi;
852 if (TREE_CODE (flag_arg) != SSA_NAME)
854 flag_arg_def = SSA_NAME_DEF_STMT (flag_arg);
855 if (gimple_code (flag_arg_def) != GIMPLE_PHI)
858 phi_arg = gimple_phi_arg_def (phi, i);
859 if (TREE_CODE (phi_arg) != SSA_NAME)
862 phi_arg_def = SSA_NAME_DEF_STMT (phi_arg);
863 if (gimple_code (phi_arg_def) != GIMPLE_PHI)
866 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
869 if (!*visited_flag_phis)
870 *visited_flag_phis = BITMAP_ALLOC (NULL);
872 if (bitmap_bit_p (*visited_flag_phis,
873 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
876 bitmap_set_bit (*visited_flag_phis,
877 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
879 /* Now recursively prune the uninitialized phi args. */
880 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
881 if (!prune_uninit_phi_opnds_in_unrealizable_paths (
882 phi_arg_def, uninit_opnds_arg_phi,
883 flag_arg_def, boundary_cst, cmp_code,
884 visited_phis, visited_flag_phis))
887 bitmap_clear_bit (*visited_flag_phis,
888 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
892 /* Now check if the constant is in the guarded range. */
893 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
898 /* Now that we know that this undefined edge is not
899 pruned. If the operand is defined by another phi,
900 we can further prune the incoming edges of that
901 phi by checking the predicates of this operands. */
903 opnd = gimple_phi_arg_def (phi, i);
904 opnd_def = SSA_NAME_DEF_STMT (opnd);
905 if (gimple_code (opnd_def) == GIMPLE_PHI)
908 unsigned uninit_opnds2
909 = compute_uninit_opnds_pos (opnd_def);
910 gcc_assert (!MASK_EMPTY (uninit_opnds2));
911 opnd_edge = gimple_phi_arg_edge (phi, i);
912 if (!is_use_properly_guarded (phi,
927 /* A helper function that determines if the predicate set
928 of the use is not overlapping with that of the uninit paths.
929 The most common senario of guarded use is in Example 1:
942 The real world examples are usually more complicated, but similar
943 and usually result from inlining:
945 bool init_func (int * x)
964 Another possible use scenario is in the following trivial example:
976 Predicate analysis needs to compute the composite predicate:
978 1) 'x' use predicate: (n > 0) .AND. (m < 2)
979 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
980 (the predicate chain for phi operand defs can be computed
981 starting from a bb that is control equivalent to the phi's
982 bb and is dominating the operand def.)
984 and check overlapping:
985 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
988 This implementation provides framework that can handle
989 scenarios. (Note that many simple cases are handled properly
990 without the predicate analysis -- this is due to jump threading
991 transformation which eliminates the merge point thus makes
992 path sensitive analysis unnecessary.)
994 NUM_PREDS is the number is the number predicate chains, PREDS is
995 the array of chains, PHI is the phi node whose incoming (undefined)
996 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
997 uninit operand positions. VISITED_PHIS is the pointer set of phi
998 stmts being checked. */
1002 use_pred_not_overlap_with_undef_path_pred (
1004 vec<use_pred_info_t> *preds,
1005 gimple phi, unsigned uninit_opnds,
1006 struct pointer_set_t *visited_phis)
1009 gimple flag_def = 0;
1010 tree boundary_cst = 0;
1011 enum tree_code cmp_code;
1012 bool swap_cond = false;
1013 bool invert = false;
1014 vec<use_pred_info_t> the_pred_chain;
1015 bitmap visited_flag_phis = NULL;
1016 bool all_pruned = false;
1018 gcc_assert (num_preds > 0);
1019 /* Find within the common prefix of multiple predicate chains
1020 a predicate that is a comparison of a flag variable against
1022 the_pred_chain = preds[0];
1023 n = the_pred_chain.length ();
1024 for (i = 0; i < n; i++)
1027 tree cond_lhs, cond_rhs, flag = 0;
1029 use_pred_info_t the_pred
1030 = the_pred_chain[i];
1032 cond = the_pred->cond;
1033 invert = the_pred->invert;
1034 cond_lhs = gimple_cond_lhs (cond);
1035 cond_rhs = gimple_cond_rhs (cond);
1036 cmp_code = gimple_cond_code (cond);
1038 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1039 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1041 boundary_cst = cond_rhs;
1044 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1045 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1047 boundary_cst = cond_lhs;
1055 flag_def = SSA_NAME_DEF_STMT (flag);
1060 if ((gimple_code (flag_def) == GIMPLE_PHI)
1061 && (gimple_bb (flag_def) == gimple_bb (phi))
1062 && find_matching_predicate_in_rest_chains (
1063 the_pred, preds, num_preds))
1072 /* Now check all the uninit incoming edge has a constant flag value
1073 that is in conflict with the use guard/predicate. */
1074 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1076 if (cmp_code == ERROR_MARK)
1079 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
1085 &visited_flag_phis);
1087 if (visited_flag_phis)
1088 BITMAP_FREE (visited_flag_phis);
1093 /* Returns true if TC is AND or OR */
1096 is_and_or_or (enum tree_code tc, tree typ)
1098 return (tc == BIT_IOR_EXPR
1099 || (tc == BIT_AND_EXPR
1100 && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE)));
1103 typedef struct norm_cond
1106 enum tree_code cond_code;
1111 /* Normalizes gimple condition COND. The normalization follows
1112 UD chains to form larger condition expression trees. NORM_COND
1113 holds the normalized result. COND_CODE is the logical opcode
1114 (AND or OR) of the normalized tree. */
1117 normalize_cond_1 (gimple cond,
1118 norm_cond_t norm_cond,
1119 enum tree_code cond_code)
1121 enum gimple_code gc;
1122 enum tree_code cur_cond_code;
1125 gc = gimple_code (cond);
1126 if (gc != GIMPLE_ASSIGN)
1128 norm_cond->conds.safe_push (cond);
1132 cur_cond_code = gimple_assign_rhs_code (cond);
1133 rhs1 = gimple_assign_rhs1 (cond);
1134 rhs2 = gimple_assign_rhs2 (cond);
1135 if (cur_cond_code == NE_EXPR)
1137 if (integer_zerop (rhs2)
1138 && (TREE_CODE (rhs1) == SSA_NAME))
1140 SSA_NAME_DEF_STMT (rhs1),
1141 norm_cond, cond_code);
1142 else if (integer_zerop (rhs1)
1143 && (TREE_CODE (rhs2) == SSA_NAME))
1145 SSA_NAME_DEF_STMT (rhs2),
1146 norm_cond, cond_code);
1148 norm_cond->conds.safe_push (cond);
1153 if (is_and_or_or (cur_cond_code, TREE_TYPE (rhs1))
1154 && (cond_code == cur_cond_code || cond_code == ERROR_MARK)
1155 && (TREE_CODE (rhs1) == SSA_NAME && TREE_CODE (rhs2) == SSA_NAME))
1157 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1),
1158 norm_cond, cur_cond_code);
1159 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2),
1160 norm_cond, cur_cond_code);
1161 norm_cond->cond_code = cur_cond_code;
1164 norm_cond->conds.safe_push (cond);
1167 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1168 if COND needs to be inverted or not. */
1171 normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert)
1173 enum tree_code cond_code;
1175 norm_cond->cond_code = ERROR_MARK;
1176 norm_cond->invert = false;
1177 norm_cond->conds.create (0);
1178 gcc_assert (gimple_code (cond) == GIMPLE_COND);
1179 cond_code = gimple_cond_code (cond);
1181 cond_code = invert_tree_comparison (cond_code, false);
1183 if (cond_code == NE_EXPR)
1185 if (integer_zerop (gimple_cond_rhs (cond))
1186 && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME))
1188 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)),
1189 norm_cond, ERROR_MARK);
1190 else if (integer_zerop (gimple_cond_lhs (cond))
1191 && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME))
1193 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)),
1194 norm_cond, ERROR_MARK);
1197 norm_cond->conds.safe_push (cond);
1198 norm_cond->invert = invert;
1203 norm_cond->conds.safe_push (cond);
1204 norm_cond->invert = invert;
1207 gcc_assert (norm_cond->conds.length () == 1
1208 || is_and_or_or (norm_cond->cond_code, NULL));
1211 /* Returns true if the domain for condition COND1 is a subset of
1212 COND2. REVERSE is a flag. when it is true the function checks
1213 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1214 to indicate if COND1 and COND2 need to be inverted or not. */
1217 is_gcond_subset_of (gimple cond1, bool invert1,
1218 gimple cond2, bool invert2,
1221 enum gimple_code gc1, gc2;
1222 enum tree_code cond1_code, cond2_code;
1224 tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs;
1226 /* Take the short cut. */
1237 gc1 = gimple_code (cond1);
1238 gc2 = gimple_code (cond2);
1240 if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND)
1241 || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND))
1242 return cond1 == cond2;
1244 cond1_code = ((gc1 == GIMPLE_ASSIGN)
1245 ? gimple_assign_rhs_code (cond1)
1246 : gimple_cond_code (cond1));
1248 cond2_code = ((gc2 == GIMPLE_ASSIGN)
1249 ? gimple_assign_rhs_code (cond2)
1250 : gimple_cond_code (cond2));
1252 if (TREE_CODE_CLASS (cond1_code) != tcc_comparison
1253 || TREE_CODE_CLASS (cond2_code) != tcc_comparison)
1257 cond1_code = invert_tree_comparison (cond1_code, false);
1259 cond2_code = invert_tree_comparison (cond2_code, false);
1261 cond1_lhs = ((gc1 == GIMPLE_ASSIGN)
1262 ? gimple_assign_rhs1 (cond1)
1263 : gimple_cond_lhs (cond1));
1264 cond1_rhs = ((gc1 == GIMPLE_ASSIGN)
1265 ? gimple_assign_rhs2 (cond1)
1266 : gimple_cond_rhs (cond1));
1267 cond2_lhs = ((gc2 == GIMPLE_ASSIGN)
1268 ? gimple_assign_rhs1 (cond2)
1269 : gimple_cond_lhs (cond2));
1270 cond2_rhs = ((gc2 == GIMPLE_ASSIGN)
1271 ? gimple_assign_rhs2 (cond2)
1272 : gimple_cond_rhs (cond2));
1274 /* Assuming const operands have been swapped to the
1275 rhs at this point of the analysis. */
1277 if (cond1_lhs != cond2_lhs)
1280 if (!is_gimple_constant (cond1_rhs)
1281 || TREE_CODE (cond1_rhs) != INTEGER_CST)
1282 return (cond1_rhs == cond2_rhs);
1284 if (!is_gimple_constant (cond2_rhs)
1285 || TREE_CODE (cond2_rhs) != INTEGER_CST)
1286 return (cond1_rhs == cond2_rhs);
1288 if (cond1_code == EQ_EXPR)
1289 return is_value_included_in (cond1_rhs,
1290 cond2_rhs, cond2_code);
1291 if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR)
1292 return ((cond2_code == cond1_code)
1293 && tree_int_cst_equal (cond1_rhs, cond2_rhs));
1295 if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR)
1296 && (cond2_code == LE_EXPR || cond2_code == LT_EXPR))
1297 || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR)
1298 && (cond2_code == GE_EXPR || cond2_code == GT_EXPR)))
1301 if (cond1_code != GE_EXPR && cond1_code != GT_EXPR
1302 && cond1_code != LE_EXPR && cond1_code != LT_EXPR)
1305 if (cond1_code == GT_EXPR)
1307 cond1_code = GE_EXPR;
1308 cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs),
1310 fold_convert (TREE_TYPE (cond1_rhs),
1313 else if (cond1_code == LT_EXPR)
1315 cond1_code = LE_EXPR;
1316 cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs),
1318 fold_convert (TREE_TYPE (cond1_rhs),
1325 gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR);
1327 if (cond2_code == GE_EXPR || cond2_code == GT_EXPR ||
1328 cond2_code == LE_EXPR || cond2_code == LT_EXPR)
1329 return is_value_included_in (cond1_rhs,
1330 cond2_rhs, cond2_code);
1331 else if (cond2_code == NE_EXPR)
1333 (is_value_included_in (cond1_rhs,
1334 cond2_rhs, cond2_code)
1335 && !is_value_included_in (cond2_rhs,
1336 cond1_rhs, cond1_code));
1340 /* Returns true if the domain of the condition expression
1341 in COND is a subset of any of the sub-conditions
1342 of the normalized condtion NORM_COND. INVERT is a flag
1343 to indicate of the COND needs to be inverted.
1344 REVERSE is a flag. When it is true, the check is reversed --
1345 it returns true if COND is a superset of any of the subconditions
1349 is_subset_of_any (gimple cond, bool invert,
1350 norm_cond_t norm_cond, bool reverse)
1353 size_t len = norm_cond->conds.length ();
1355 for (i = 0; i < len; i++)
1357 if (is_gcond_subset_of (cond, invert,
1358 norm_cond->conds[i],
1365 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1366 expressions (formed by following UD chains not control
1367 dependence chains). The function returns true of domain
1368 of and expression NORM_COND1 is a subset of NORM_COND2's.
1369 The implementation is conservative, and it returns false if
1370 it the inclusion relationship may not hold. */
1373 is_or_set_subset_of (norm_cond_t norm_cond1,
1374 norm_cond_t norm_cond2)
1377 size_t len = norm_cond1->conds.length ();
1379 for (i = 0; i < len; i++)
1381 if (!is_subset_of_any (norm_cond1->conds[i],
1382 false, norm_cond2, false))
1388 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1389 expressions (formed by following UD chains not control
1390 dependence chains). The function returns true of domain
1391 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1394 is_and_set_subset_of (norm_cond_t norm_cond1,
1395 norm_cond_t norm_cond2)
1398 size_t len = norm_cond2->conds.length ();
1400 for (i = 0; i < len; i++)
1402 if (!is_subset_of_any (norm_cond2->conds[i],
1403 false, norm_cond1, true))
1409 /* Returns true of the domain if NORM_COND1 is a subset
1410 of that of NORM_COND2. Returns false if it can not be
1414 is_norm_cond_subset_of (norm_cond_t norm_cond1,
1415 norm_cond_t norm_cond2)
1418 enum tree_code code1, code2;
1420 code1 = norm_cond1->cond_code;
1421 code2 = norm_cond2->cond_code;
1423 if (code1 == BIT_AND_EXPR)
1425 /* Both conditions are AND expressions. */
1426 if (code2 == BIT_AND_EXPR)
1427 return is_and_set_subset_of (norm_cond1, norm_cond2);
1428 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1429 expression. In this case, returns true if any subexpression
1430 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1431 else if (code2 == BIT_IOR_EXPR)
1434 len1 = norm_cond1->conds.length ();
1435 for (i = 0; i < len1; i++)
1437 gimple cond1 = norm_cond1->conds[i];
1438 if (is_subset_of_any (cond1, false, norm_cond2, false))
1445 gcc_assert (code2 == ERROR_MARK);
1446 gcc_assert (norm_cond2->conds.length () == 1);
1447 return is_subset_of_any (norm_cond2->conds[0],
1448 norm_cond2->invert, norm_cond1, true);
1451 /* NORM_COND1 is an OR expression */
1452 else if (code1 == BIT_IOR_EXPR)
1457 return is_or_set_subset_of (norm_cond1, norm_cond2);
1461 gcc_assert (code1 == ERROR_MARK);
1462 gcc_assert (norm_cond1->conds.length () == 1);
1463 /* Conservatively returns false if NORM_COND1 is non-decomposible
1464 and NORM_COND2 is an AND expression. */
1465 if (code2 == BIT_AND_EXPR)
1468 if (code2 == BIT_IOR_EXPR)
1469 return is_subset_of_any (norm_cond1->conds[0],
1470 norm_cond1->invert, norm_cond2, false);
1472 gcc_assert (code2 == ERROR_MARK);
1473 gcc_assert (norm_cond2->conds.length () == 1);
1474 return is_gcond_subset_of (norm_cond1->conds[0],
1476 norm_cond2->conds[0],
1477 norm_cond2->invert, false);
1481 /* Returns true of the domain of single predicate expression
1482 EXPR1 is a subset of that of EXPR2. Returns false if it
1483 can not be proved. */
1486 is_pred_expr_subset_of (use_pred_info_t expr1,
1487 use_pred_info_t expr2)
1489 gimple cond1, cond2;
1490 enum tree_code code1, code2;
1491 struct norm_cond norm_cond1, norm_cond2;
1492 bool is_subset = false;
1494 cond1 = expr1->cond;
1495 cond2 = expr2->cond;
1496 code1 = gimple_cond_code (cond1);
1497 code2 = gimple_cond_code (cond2);
1500 code1 = invert_tree_comparison (code1, false);
1502 code2 = invert_tree_comparison (code2, false);
1504 /* Fast path -- match exactly */
1505 if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2))
1506 && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2))
1507 && (code1 == code2))
1510 /* Normalize conditions. To keep NE_EXPR, do not invert
1511 with both need inversion. */
1512 normalize_cond (cond1, &norm_cond1, (expr1->invert));
1513 normalize_cond (cond2, &norm_cond2, (expr2->invert));
1515 is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2);
1518 norm_cond1.conds.release ();
1519 norm_cond2.conds.release ();
1523 /* Returns true if the domain of PRED1 is a subset
1524 of that of PRED2. Returns false if it can not be proved so. */
1527 is_pred_chain_subset_of (vec<use_pred_info_t> pred1,
1528 vec<use_pred_info_t> pred2)
1530 size_t np1, np2, i1, i2;
1532 np1 = pred1.length ();
1533 np2 = pred2.length ();
1535 for (i2 = 0; i2 < np2; i2++)
1538 use_pred_info_t info2
1540 for (i1 = 0; i1 < np1; i1++)
1542 use_pred_info_t info1
1544 if (is_pred_expr_subset_of (info1, info2))
1556 /* Returns true if the domain defined by
1557 one pred chain ONE_PRED is a subset of the domain
1558 of *PREDS. It returns false if ONE_PRED's domain is
1559 not a subset of any of the sub-domains of PREDS (
1560 corresponding to each individual chains in it), even
1561 though it may be still be a subset of whole domain
1562 of PREDS which is the union (ORed) of all its subdomains.
1563 In other words, the result is conservative. */
1566 is_included_in (vec<use_pred_info_t> one_pred,
1567 vec<use_pred_info_t> *preds,
1572 for (i = 0; i < n; i++)
1574 if (is_pred_chain_subset_of (one_pred, preds[i]))
1581 /* compares two predicate sets PREDS1 and PREDS2 and returns
1582 true if the domain defined by PREDS1 is a superset
1583 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1584 PREDS2 respectively. The implementation chooses not to build
1585 generic trees (and relying on the folding capability of the
1586 compiler), but instead performs brute force comparison of
1587 individual predicate chains (won't be a compile time problem
1588 as the chains are pretty short). When the function returns
1589 false, it does not necessarily mean *PREDS1 is not a superset
1590 of *PREDS2, but mean it may not be so since the analysis can
1591 not prove it. In such cases, false warnings may still be
1595 is_superset_of (vec<use_pred_info_t> *preds1,
1597 vec<use_pred_info_t> *preds2,
1601 vec<use_pred_info_t> one_pred_chain;
1603 for (i = 0; i < n2; i++)
1605 one_pred_chain = preds2[i];
1606 if (!is_included_in (one_pred_chain, preds1, n1))
1613 /* Comparison function used by qsort. It is used to
1614 sort predicate chains to allow predicate
1618 pred_chain_length_cmp (const void *p1, const void *p2)
1620 use_pred_info_t i1, i2;
1621 vec<use_pred_info_t> const *chain1
1622 = (vec<use_pred_info_t> const *)p1;
1623 vec<use_pred_info_t> const *chain2
1624 = (vec<use_pred_info_t> const *)p2;
1626 if (chain1->length () != chain2->length ())
1627 return (chain1->length () - chain2->length ());
1632 /* Allow predicates with similar prefix come together. */
1633 if (!i1->invert && i2->invert)
1635 else if (i1->invert && !i2->invert)
1638 return gimple_uid (i1->cond) - gimple_uid (i2->cond);
1641 /* x OR (!x AND y) is equivalent to x OR y.
1642 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
1643 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
1644 the number of chains. Returns true if normalization happens. */
1647 normalize_preds (vec<use_pred_info_t> *preds, size_t *n)
1650 vec<use_pred_info_t> pred_chain;
1651 vec<use_pred_info_t> x = vNULL;
1652 use_pred_info_t xj = 0, nxj = 0;
1657 /* First sort the chains in ascending order of lengths. */
1658 qsort (preds, *n, sizeof (void *), pred_chain_length_cmp);
1659 pred_chain = preds[0];
1660 ll = pred_chain.length ();
1665 use_pred_info_t xx, yy, xx2, nyy;
1666 vec<use_pred_info_t> pred_chain2 = preds[1];
1667 if (pred_chain2.length () != 2)
1670 /* See if simplification x AND y OR x AND !y is possible. */
1673 xx2 = pred_chain2[0];
1674 nyy = pred_chain2[1];
1675 if (gimple_cond_lhs (xx->cond) != gimple_cond_lhs (xx2->cond)
1676 || gimple_cond_rhs (xx->cond) != gimple_cond_rhs (xx2->cond)
1677 || gimple_cond_code (xx->cond) != gimple_cond_code (xx2->cond)
1678 || (xx->invert != xx2->invert))
1680 if (gimple_cond_lhs (yy->cond) != gimple_cond_lhs (nyy->cond)
1681 || gimple_cond_rhs (yy->cond) != gimple_cond_rhs (nyy->cond)
1682 || gimple_cond_code (yy->cond) != gimple_cond_code (nyy->cond)
1683 || (yy->invert == nyy->invert))
1686 /* Now merge the first two chains. */
1690 pred_chain.release ();
1691 pred_chain2.release ();
1692 pred_chain.safe_push (xx);
1693 preds[0] = pred_chain;
1694 for (i = 1; i < *n - 1; i++)
1695 preds[i] = preds[i + 1];
1697 preds[*n - 1].create (0);
1704 x.safe_push (pred_chain[0]);
1706 /* The loop extracts x1, x2, x3, etc from chains
1707 x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
1708 for (i = 1; i < *n; i++)
1710 pred_chain = preds[i];
1711 if (pred_chain.length () != i + 1)
1714 for (j = 0; j < i; j++)
1717 nxj = pred_chain[j];
1719 /* Check if nxj is !xj */
1720 if (gimple_cond_lhs (xj->cond) != gimple_cond_lhs (nxj->cond)
1721 || gimple_cond_rhs (xj->cond) != gimple_cond_rhs (nxj->cond)
1722 || gimple_cond_code (xj->cond) != gimple_cond_code (nxj->cond)
1723 || (xj->invert == nxj->invert))
1727 x.safe_push (pred_chain[i]);
1730 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
1731 for (j = 0; j < *n; j++)
1736 t = XNEW (struct use_pred_info);
1742 for (i = 0; i < *n; i++)
1744 pred_chain = preds[i];
1745 for (j = 0; j < pred_chain.length (); j++)
1746 free (pred_chain[j]);
1747 pred_chain.release ();
1749 pred_chain.safe_push (x[i]);
1750 preds[i] = pred_chain;
1757 /* Computes the predicates that guard the use and checks
1758 if the incoming paths that have empty (or possibly
1759 empty) definition can be pruned/filtered. The function returns
1760 true if it can be determined that the use of PHI's def in
1761 USE_STMT is guarded with a predicate set not overlapping with
1762 predicate sets of all runtime paths that do not have a definition.
1763 Returns false if it is not or it can not be determined. USE_BB is
1764 the bb of the use (for phi operand use, the bb is not the bb of
1765 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1766 is a bit vector. If an operand of PHI is uninitialized, the
1767 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
1768 set of phis being visted. */
1771 is_use_properly_guarded (gimple use_stmt,
1774 unsigned uninit_opnds,
1775 struct pointer_set_t *visited_phis)
1778 vec<use_pred_info_t> *preds = 0;
1779 vec<use_pred_info_t> *def_preds = 0;
1780 size_t num_preds = 0, num_def_preds = 0;
1781 bool has_valid_preds = false;
1782 bool is_properly_guarded = false;
1784 if (pointer_set_insert (visited_phis, phi))
1787 phi_bb = gimple_bb (phi);
1789 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
1792 has_valid_preds = find_predicates (&preds, &num_preds,
1795 if (!has_valid_preds)
1797 destroy_predicate_vecs (num_preds, preds);
1802 dump_predicates (use_stmt, num_preds, preds,
1805 has_valid_preds = find_def_preds (&def_preds,
1806 &num_def_preds, phi);
1808 if (has_valid_preds)
1812 dump_predicates (phi, num_def_preds, def_preds,
1813 "Operand defs of phi ");
1815 normed = normalize_preds (def_preds, &num_def_preds);
1816 if (normed && dump_file)
1818 fprintf (dump_file, "\nNormalized to\n");
1819 dump_predicates (phi, num_def_preds, def_preds,
1820 "Operand defs of phi ");
1822 is_properly_guarded =
1823 is_superset_of (def_preds, num_def_preds,
1827 /* further prune the dead incoming phi edges. */
1828 if (!is_properly_guarded)
1830 = use_pred_not_overlap_with_undef_path_pred (
1831 num_preds, preds, phi, uninit_opnds, visited_phis);
1833 destroy_predicate_vecs (num_preds, preds);
1834 destroy_predicate_vecs (num_def_preds, def_preds);
1835 return is_properly_guarded;
1838 /* Searches through all uses of a potentially
1839 uninitialized variable defined by PHI and returns a use
1840 statement if the use is not properly guarded. It returns
1841 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1842 holding the position(s) of uninit PHI operands. WORKLIST
1843 is the vector of candidate phis that may be updated by this
1844 function. ADDED_TO_WORKLIST is the pointer set tracking
1845 if the new phi is already in the worklist. */
1848 find_uninit_use (gimple phi, unsigned uninit_opnds,
1849 vec<gimple> *worklist,
1850 struct pointer_set_t *added_to_worklist)
1853 use_operand_p use_p;
1855 imm_use_iterator iter;
1857 phi_result = gimple_phi_result (phi);
1859 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
1861 struct pointer_set_t *visited_phis;
1864 use_stmt = USE_STMT (use_p);
1865 if (is_gimple_debug (use_stmt))
1868 visited_phis = pointer_set_create ();
1870 if (gimple_code (use_stmt) == GIMPLE_PHI)
1871 use_bb = gimple_phi_arg_edge (use_stmt,
1872 PHI_ARG_INDEX_FROM_USE (use_p))->src;
1874 use_bb = gimple_bb (use_stmt);
1876 if (is_use_properly_guarded (use_stmt,
1882 pointer_set_destroy (visited_phis);
1885 pointer_set_destroy (visited_phis);
1887 if (dump_file && (dump_flags & TDF_DETAILS))
1889 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
1890 print_gimple_stmt (dump_file, use_stmt, 0, 0);
1892 /* Found one real use, return. */
1893 if (gimple_code (use_stmt) != GIMPLE_PHI)
1896 /* Found a phi use that is not guarded,
1897 add the phi to the worklist. */
1898 if (!pointer_set_insert (added_to_worklist,
1901 if (dump_file && (dump_flags & TDF_DETAILS))
1903 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
1904 print_gimple_stmt (dump_file, use_stmt, 0, 0);
1907 worklist->safe_push (use_stmt);
1908 pointer_set_insert (possibly_undefined_names, phi_result);
1915 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1916 and gives warning if there exists a runtime path from the entry to a
1917 use of the PHI def that does not contain a definition. In other words,
1918 the warning is on the real use. The more dead paths that can be pruned
1919 by the compiler, the fewer false positives the warning is. WORKLIST
1920 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1921 a pointer set tracking if the new phi is added to the worklist or not. */
1924 warn_uninitialized_phi (gimple phi, vec<gimple> *worklist,
1925 struct pointer_set_t *added_to_worklist)
1927 unsigned uninit_opnds;
1928 gimple uninit_use_stmt = 0;
1931 /* Don't look at virtual operands. */
1932 if (virtual_operand_p (gimple_phi_result (phi)))
1935 uninit_opnds = compute_uninit_opnds_pos (phi);
1937 if (MASK_EMPTY (uninit_opnds))
1940 if (dump_file && (dump_flags & TDF_DETAILS))
1942 fprintf (dump_file, "[CHECK]: examining phi: ");
1943 print_gimple_stmt (dump_file, phi, 0, 0);
1946 /* Now check if we have any use of the value without proper guard. */
1947 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
1948 worklist, added_to_worklist);
1950 /* All uses are properly guarded. */
1951 if (!uninit_use_stmt)
1954 uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds));
1955 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
1957 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
1958 SSA_NAME_VAR (uninit_op),
1959 "%qD may be used uninitialized in this function",
1965 /* Entry point to the late uninitialized warning pass. */
1968 execute_late_warn_uninitialized (void)
1971 gimple_stmt_iterator gsi;
1972 vec<gimple> worklist = vNULL;
1973 struct pointer_set_t *added_to_worklist;
1975 calculate_dominance_info (CDI_DOMINATORS);
1976 calculate_dominance_info (CDI_POST_DOMINATORS);
1977 /* Re-do the plain uninitialized variable check, as optimization may have
1978 straightened control flow. Do this first so that we don't accidentally
1979 get a "may be" warning when we'd have seen an "is" warning later. */
1980 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1982 timevar_push (TV_TREE_UNINIT);
1984 possibly_undefined_names = pointer_set_create ();
1985 added_to_worklist = pointer_set_create ();
1987 /* Initialize worklist */
1989 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1991 gimple phi = gsi_stmt (gsi);
1994 n = gimple_phi_num_args (phi);
1996 /* Don't look at virtual operands. */
1997 if (virtual_operand_p (gimple_phi_result (phi)))
2000 for (i = 0; i < n; ++i)
2002 tree op = gimple_phi_arg_def (phi, i);
2003 if (TREE_CODE (op) == SSA_NAME
2004 && uninit_undefined_value_p (op))
2006 worklist.safe_push (phi);
2007 pointer_set_insert (added_to_worklist, phi);
2008 if (dump_file && (dump_flags & TDF_DETAILS))
2010 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2011 print_gimple_stmt (dump_file, phi, 0, 0);
2018 while (worklist.length () != 0)
2021 cur_phi = worklist.pop ();
2022 warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
2025 worklist.release ();
2026 pointer_set_destroy (added_to_worklist);
2027 pointer_set_destroy (possibly_undefined_names);
2028 possibly_undefined_names = NULL;
2029 free_dominance_info (CDI_POST_DOMINATORS);
2030 timevar_pop (TV_TREE_UNINIT);
2035 gate_warn_uninitialized (void)
2037 return warn_uninitialized != 0;
2040 struct gimple_opt_pass pass_late_warn_uninitialized =
2044 "uninit", /* name */
2045 OPTGROUP_NONE, /* optinfo_flags */
2046 gate_warn_uninitialized, /* gate */
2047 execute_late_warn_uninitialized, /* execute */
2050 0, /* static_pass_number */
2051 TV_NONE, /* tv_id */
2052 PROP_ssa, /* properties_required */
2053 0, /* properties_provided */
2054 0, /* properties_destroyed */
2055 0, /* todo_flags_start */
2056 0 /* todo_flags_finish */