1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2015 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 "double-int.h"
35 #include "fold-const.h"
39 #include "hard-reg-set.h"
42 #include "dominance.h"
44 #include "basic-block.h"
45 #include "gimple-pretty-print.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
52 #include "gimple-iterator.h"
53 #include "gimple-ssa.h"
54 #include "tree-phinodes.h"
55 #include "ssa-iterators.h"
57 #include "tree-inline.h"
58 #include "tree-pass.h"
59 #include "diagnostic-core.h"
63 /* This implements the pass that does predicate aware warning on uses of
64 possibly uninitialized variables. The pass first collects the set of
65 possibly uninitialized SSA names. For each such name, it walks through
66 all its immediate uses. For each immediate use, it rebuilds the condition
67 expression (the predicate) that guards the use. The predicate is then
68 examined to see if the variable is always defined under that same condition.
69 This is done either by pruning the unrealizable paths that lead to the
70 default definitions or by checking if the predicate set that guards the
71 defining paths is a superset of the use predicate. */
74 /* Pointer set of potentially undefined ssa names, i.e.,
75 ssa names that are defined by phi with operands that
76 are not defined or potentially undefined. */
77 static hash_set<tree> *possibly_undefined_names = 0;
79 /* Bit mask handling macros. */
80 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
81 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
82 #define MASK_EMPTY(mask) (mask == 0)
84 /* Returns the first bit position (starting from LSB)
85 in mask that is non zero. Returns -1 if the mask is empty. */
87 get_mask_first_set_bit (unsigned mask)
93 while ((mask & (1 << pos)) == 0)
98 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
100 /* Return true if T, an SSA_NAME, has an undefined value. */
102 has_undefined_value_p (tree t)
104 return (ssa_undefined_value_p (t)
105 || (possibly_undefined_names
106 && possibly_undefined_names->contains (t)));
111 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
112 is set on SSA_NAME_VAR. */
115 uninit_undefined_value_p (tree t) {
116 if (!has_undefined_value_p (t))
118 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
123 /* Emit warnings for uninitialized variables. This is done in two passes.
125 The first pass notices real uses of SSA names with undefined values.
126 Such uses are unconditionally uninitialized, and we can be certain that
127 such a use is a mistake. This pass is run before most optimizations,
128 so that we catch as many as we can.
130 The second pass follows PHI nodes to find uses that are potentially
131 uninitialized. In this case we can't necessarily prove that the use
132 is really uninitialized. This pass is run after most optimizations,
133 so that we thread as many jumps and possible, and delete as much dead
134 code as possible, in order to reduce false positives. We also look
135 again for plain uninitialized variables, since optimization may have
136 changed conditionally uninitialized to unconditionally uninitialized. */
138 /* Emit a warning for EXPR based on variable VAR at the point in the
139 program T, an SSA_NAME, is used being uninitialized. The exact
140 warning text is in MSGID and DATA is the gimple stmt with info about
141 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
142 gives which argument of the phi node to take the location from. WC
143 is the warning code. */
146 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
147 const char *gmsgid, void *data, location_t phiarg_loc)
149 gimple context = (gimple) data;
150 location_t location, cfun_loc;
151 expanded_location xloc, floc;
153 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
154 turns in a COMPLEX_EXPR with the not initialized part being
155 set to its previous (undefined) value. */
156 if (is_gimple_assign (context)
157 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
159 if (!has_undefined_value_p (t))
162 /* TREE_NO_WARNING either means we already warned, or the front end
163 wishes to suppress the warning. */
165 && (gimple_no_warning_p (context)
166 || (gimple_assign_single_p (context)
167 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
168 || TREE_NO_WARNING (expr))
171 if (context != NULL && gimple_has_location (context))
172 location = gimple_location (context);
173 else if (phiarg_loc != UNKNOWN_LOCATION)
174 location = phiarg_loc;
176 location = DECL_SOURCE_LOCATION (var);
177 location = linemap_resolve_location (line_table, location,
178 LRK_SPELLING_LOCATION,
180 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
181 xloc = expand_location (location);
182 floc = expand_location (cfun_loc);
183 if (warning_at (location, wc, gmsgid, expr))
185 TREE_NO_WARNING (expr) = 1;
187 if (location == DECL_SOURCE_LOCATION (var))
189 if (xloc.file != floc.file
190 || linemap_location_before_p (line_table,
192 || linemap_location_before_p (line_table,
193 cfun->function_end_locus,
195 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
200 warn_uninitialized_vars (bool warn_possibly_uninitialized)
202 gimple_stmt_iterator gsi;
205 FOR_EACH_BB_FN (bb, cfun)
207 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS,
208 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb);
209 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
211 gimple stmt = gsi_stmt (gsi);
216 if (is_gimple_debug (stmt))
219 /* We only do data flow with SSA_NAMEs, so that's all we
221 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
223 use = USE_FROM_PTR (use_p);
225 warn_uninit (OPT_Wuninitialized, use,
226 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
227 "%qD is used uninitialized in this function",
228 stmt, UNKNOWN_LOCATION);
229 else if (warn_possibly_uninitialized)
230 warn_uninit (OPT_Wmaybe_uninitialized, use,
231 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
232 "%qD may be used uninitialized in this function",
233 stmt, UNKNOWN_LOCATION);
236 /* For memory the only cheap thing we can do is see if we
237 have a use of the default def of the virtual operand.
238 ??? Not so cheap would be to use the alias oracle via
239 walk_aliased_vdefs, if we don't find any aliasing vdef
240 warn as is-used-uninitialized, if we don't find an aliasing
241 vdef that kills our use (stmt_kills_ref_p), warn as
242 may-be-used-uninitialized. But this walk is quadratic and
243 so must be limited which means we would miss warning
245 use = gimple_vuse (stmt);
247 && gimple_assign_single_p (stmt)
248 && !gimple_vdef (stmt)
249 && SSA_NAME_IS_DEFAULT_DEF (use))
251 tree rhs = gimple_assign_rhs1 (stmt);
252 tree base = get_base_address (rhs);
254 /* Do not warn if it can be initialized outside this function. */
255 if (TREE_CODE (base) != VAR_DECL
256 || DECL_HARD_REGISTER (base)
257 || is_global_var (base))
261 warn_uninit (OPT_Wuninitialized, use,
262 gimple_assign_rhs1 (stmt), base,
263 "%qE is used uninitialized in this function",
264 stmt, UNKNOWN_LOCATION);
265 else if (warn_possibly_uninitialized)
266 warn_uninit (OPT_Wmaybe_uninitialized, use,
267 gimple_assign_rhs1 (stmt), base,
268 "%qE may be used uninitialized in this function",
269 stmt, UNKNOWN_LOCATION);
277 /* Checks if the operand OPND of PHI is defined by
278 another phi with one operand defined by this PHI,
279 but the rest operands are all defined. If yes,
280 returns true to skip this this operand as being
281 redundant. Can be enhanced to be more general. */
284 can_skip_redundant_opnd (tree opnd, gimple phi)
290 phi_def = gimple_phi_result (phi);
291 op_def = SSA_NAME_DEF_STMT (opnd);
292 if (gimple_code (op_def) != GIMPLE_PHI)
294 n = gimple_phi_num_args (op_def);
295 for (i = 0; i < n; ++i)
297 tree op = gimple_phi_arg_def (op_def, i);
298 if (TREE_CODE (op) != SSA_NAME)
300 if (op != phi_def && uninit_undefined_value_p (op))
307 /* Returns a bit mask holding the positions of arguments in PHI
308 that have empty (or possibly empty) definitions. */
311 compute_uninit_opnds_pos (gphi *phi)
314 unsigned uninit_opnds = 0;
316 n = gimple_phi_num_args (phi);
317 /* Bail out for phi with too many args. */
321 for (i = 0; i < n; ++i)
323 tree op = gimple_phi_arg_def (phi, i);
324 if (TREE_CODE (op) == SSA_NAME
325 && uninit_undefined_value_p (op)
326 && !can_skip_redundant_opnd (op, phi))
328 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
330 /* Ignore SSA_NAMEs that appear on abnormal edges
332 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
335 MASK_SET_BIT (uninit_opnds, i);
341 /* Find the immediate postdominator PDOM of the specified
342 basic block BLOCK. */
344 static inline basic_block
345 find_pdom (basic_block block)
347 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
348 return EXIT_BLOCK_PTR_FOR_FN (cfun);
352 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
354 return EXIT_BLOCK_PTR_FOR_FN (cfun);
359 /* Find the immediate DOM of the specified
360 basic block BLOCK. */
362 static inline basic_block
363 find_dom (basic_block block)
365 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
366 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
369 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
371 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
376 /* Returns true if BB1 is postdominating BB2 and BB1 is
377 not a loop exit bb. The loop exit bb check is simple and does
378 not cover all cases. */
381 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
383 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
386 if (single_pred_p (bb1) && !single_succ_p (bb2))
392 /* Find the closest postdominator of a specified BB, which is control
395 static inline basic_block
396 find_control_equiv_block (basic_block bb)
400 pdom = find_pdom (bb);
402 /* Skip the postdominating bb that is also loop exit. */
403 if (!is_non_loop_exit_postdominating (pdom, bb))
406 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
412 #define MAX_NUM_CHAINS 8
413 #define MAX_CHAIN_LEN 5
414 #define MAX_POSTDOM_CHECK 8
415 #define MAX_SWITCH_CASES 40
417 /* Computes the control dependence chains (paths of edges)
418 for DEP_BB up to the dominating basic block BB (the head node of a
419 chain should be dominated by it). CD_CHAINS is pointer to an
420 array holding the result chains. CUR_CD_CHAIN is the current
421 chain being computed. *NUM_CHAINS is total number of chains. The
422 function returns true if the information is successfully computed,
423 return false if there is no control dependence or not computed. */
426 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
427 vec<edge> *cd_chains,
429 vec<edge> *cur_cd_chain,
435 bool found_cd_chain = false;
436 size_t cur_chain_len = 0;
438 if (EDGE_COUNT (bb->succs) < 2)
441 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
445 /* Could use a set instead. */
446 cur_chain_len = cur_cd_chain->length ();
447 if (cur_chain_len > MAX_CHAIN_LEN)
450 for (i = 0; i < cur_chain_len; i++)
452 edge e = (*cur_cd_chain)[i];
453 /* Cycle detected. */
458 FOR_EACH_EDGE (e, ei, bb->succs)
461 int post_dom_check = 0;
462 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
466 cur_cd_chain->safe_push (e);
467 while (!is_non_loop_exit_postdominating (cd_bb, bb))
471 /* Found a direct control dependence. */
472 if (*num_chains < MAX_NUM_CHAINS)
474 cd_chains[*num_chains] = cur_cd_chain->copy ();
477 found_cd_chain = true;
478 /* Check path from next edge. */
482 /* Now check if DEP_BB is indirectly control dependent on BB. */
483 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
484 num_chains, cur_cd_chain, num_calls))
486 found_cd_chain = true;
490 cd_bb = find_pdom (cd_bb);
492 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || post_dom_check >
496 cur_cd_chain->pop ();
497 gcc_assert (cur_cd_chain->length () == cur_chain_len);
499 gcc_assert (cur_cd_chain->length () == cur_chain_len);
501 return found_cd_chain;
504 /* The type to represent a simple predicate */
506 typedef struct use_def_pred_info
510 enum tree_code cond_code;
514 /* The type to represent a sequence of predicates grouped
515 with .AND. operation. */
517 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
519 /* The type to represent a sequence of pred_chains grouped
520 with .OR. operation. */
522 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
524 /* Converts the chains of control dependence edges into a set of
525 predicates. A control dependence chain is represented by a vector
526 edges. DEP_CHAINS points to an array of dependence chains.
527 NUM_CHAINS is the size of the chain array. One edge in a dependence
528 chain is mapped to predicate expression represented by pred_info
529 type. One dependence chain is converted to a composite predicate that
530 is the result of AND operation of pred_info mapped to each edge.
531 A composite predicate is presented by a vector of pred_info. On
532 return, *PREDS points to the resulting array of composite predicates.
533 *NUM_PREDS is the number of composite predictes. */
536 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
538 pred_chain_union *preds)
540 bool has_valid_pred = false;
542 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
545 /* Now convert the control dep chain into a set
547 preds->reserve (num_chains);
549 for (i = 0; i < num_chains; i++)
551 vec<edge> one_cd_chain = dep_chains[i];
553 has_valid_pred = false;
554 pred_chain t_chain = vNULL;
555 for (j = 0; j < one_cd_chain.length (); j++)
558 gimple_stmt_iterator gsi;
559 basic_block guard_bb;
565 gsi = gsi_last_bb (guard_bb);
568 has_valid_pred = false;
571 cond_stmt = gsi_stmt (gsi);
572 if (is_gimple_call (cond_stmt)
573 && EDGE_COUNT (e->src->succs) >= 2)
575 /* Ignore EH edge. Can add assertion
576 on the other edge's flag. */
579 /* Skip if there is essentially one succesor. */
580 if (EDGE_COUNT (e->src->succs) == 2)
586 FOR_EACH_EDGE (e1, ei1, e->src->succs)
588 if (EDGE_COUNT (e1->dest->succs) == 0)
597 if (gimple_code (cond_stmt) == GIMPLE_COND)
599 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
600 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
601 one_pred.cond_code = gimple_cond_code (cond_stmt);
602 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
603 t_chain.safe_push (one_pred);
604 has_valid_pred = true;
606 else if (gswitch *gs = dyn_cast <gswitch *> (cond_stmt))
608 /* Avoid quadratic behavior. */
609 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
611 has_valid_pred = false;
614 /* Find the case label. */
617 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
619 tree tl = gimple_switch_label (gs, idx);
620 if (e->dest == label_to_block (CASE_LABEL (tl)))
631 /* If more than one label reaches this block or the case
632 label doesn't have a single value (like the default one)
636 || (CASE_HIGH (l) && !operand_equal_p (CASE_LOW (l),
639 has_valid_pred = false;
642 one_pred.pred_lhs = gimple_switch_index (gs);
643 one_pred.pred_rhs = CASE_LOW (l);
644 one_pred.cond_code = EQ_EXPR;
645 one_pred.invert = false;
646 t_chain.safe_push (one_pred);
647 has_valid_pred = true;
651 has_valid_pred = false;
659 preds->safe_push (t_chain);
661 return has_valid_pred;
664 /* Computes all control dependence chains for USE_BB. The control
665 dependence chains are then converted to an array of composite
666 predicates pointed to by PREDS. PHI_BB is the basic block of
667 the phi whose result is used in USE_BB. */
670 find_predicates (pred_chain_union *preds,
674 size_t num_chains = 0, i;
676 vec<edge> dep_chains[MAX_NUM_CHAINS];
677 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
678 bool has_valid_pred = false;
679 basic_block cd_root = 0;
681 /* First find the closest bb that is control equivalent to PHI_BB
682 that also dominates USE_BB. */
684 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
686 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
687 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
688 cd_root = ctrl_eq_bb;
693 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
694 &cur_chain, &num_calls);
697 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
698 for (i = 0; i < num_chains; i++)
699 dep_chains[i].release ();
700 return has_valid_pred;
703 /* Computes the set of incoming edges of PHI that have non empty
704 definitions of a phi chain. The collection will be done
705 recursively on operands that are defined by phis. CD_ROOT
706 is the control dependence root. *EDGES holds the result, and
707 VISITED_PHIS is a pointer set for detecting cycles. */
710 collect_phi_def_edges (gphi *phi, basic_block cd_root,
712 hash_set<gimple> *visited_phis)
718 if (visited_phis->add (phi))
721 n = gimple_phi_num_args (phi);
722 for (i = 0; i < n; i++)
724 opnd_edge = gimple_phi_arg_edge (phi, i);
725 opnd = gimple_phi_arg_def (phi, i);
727 if (TREE_CODE (opnd) != SSA_NAME)
729 if (dump_file && (dump_flags & TDF_DETAILS))
731 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
732 print_gimple_stmt (dump_file, phi, 0, 0);
734 edges->safe_push (opnd_edge);
738 gimple def = SSA_NAME_DEF_STMT (opnd);
740 if (gimple_code (def) == GIMPLE_PHI
741 && dominated_by_p (CDI_DOMINATORS,
742 gimple_bb (def), cd_root))
743 collect_phi_def_edges (as_a <gphi *> (def), cd_root, edges,
745 else if (!uninit_undefined_value_p (opnd))
747 if (dump_file && (dump_flags & TDF_DETAILS))
749 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
750 print_gimple_stmt (dump_file, phi, 0, 0);
752 edges->safe_push (opnd_edge);
758 /* For each use edge of PHI, computes all control dependence chains.
759 The control dependence chains are then converted to an array of
760 composite predicates pointed to by PREDS. */
763 find_def_preds (pred_chain_union *preds, gphi *phi)
765 size_t num_chains = 0, i, n;
766 vec<edge> dep_chains[MAX_NUM_CHAINS];
767 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
768 vec<edge> def_edges = vNULL;
769 bool has_valid_pred = false;
770 basic_block phi_bb, cd_root = 0;
772 phi_bb = gimple_bb (phi);
773 /* First find the closest dominating bb to be
774 the control dependence root */
775 cd_root = find_dom (phi_bb);
779 hash_set<gimple> visited_phis;
780 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
782 n = def_edges.length ();
786 for (i = 0; i < n; i++)
792 opnd_edge = def_edges[i];
793 prev_nc = num_chains;
794 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
795 &num_chains, &cur_chain, &num_calls);
797 /* Now update the newly added chains with
798 the phi operand edge: */
799 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
801 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
802 dep_chains[num_chains++] = vNULL;
803 for (j = prev_nc; j < num_chains; j++)
804 dep_chains[j].safe_push (opnd_edge);
809 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
810 for (i = 0; i < num_chains; i++)
811 dep_chains[i].release ();
812 return has_valid_pred;
815 /* Dumps the predicates (PREDS) for USESTMT. */
818 dump_predicates (gimple usestmt, pred_chain_union preds,
822 pred_chain one_pred_chain = vNULL;
823 fprintf (dump_file, "%s", msg);
824 print_gimple_stmt (dump_file, usestmt, 0, 0);
825 fprintf (dump_file, "is guarded by :\n\n");
826 size_t num_preds = preds.length ();
827 /* Do some dumping here: */
828 for (i = 0; i < num_preds; i++)
832 one_pred_chain = preds[i];
833 np = one_pred_chain.length ();
835 for (j = 0; j < np; j++)
837 pred_info one_pred = one_pred_chain[j];
839 fprintf (dump_file, " (.NOT.) ");
840 print_generic_expr (dump_file, one_pred.pred_lhs, 0);
841 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
842 print_generic_expr (dump_file, one_pred.pred_rhs, 0);
844 fprintf (dump_file, " (.AND.) ");
846 fprintf (dump_file, "\n");
848 if (i < num_preds - 1)
849 fprintf (dump_file, "(.OR.)\n");
851 fprintf (dump_file, "\n\n");
855 /* Destroys the predicate set *PREDS. */
858 destroy_predicate_vecs (pred_chain_union preds)
862 size_t n = preds.length ();
863 for (i = 0; i < n; i++)
869 /* Computes the 'normalized' conditional code with operand
870 swapping and condition inversion. */
872 static enum tree_code
873 get_cmp_code (enum tree_code orig_cmp_code,
874 bool swap_cond, bool invert)
876 enum tree_code tc = orig_cmp_code;
879 tc = swap_tree_comparison (orig_cmp_code);
881 tc = invert_tree_comparison (tc, false);
898 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
899 all values in the range satisfies (x CMPC BOUNDARY) == true. */
902 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
904 bool inverted = false;
908 /* Only handle integer constant here. */
909 if (TREE_CODE (val) != INTEGER_CST
910 || TREE_CODE (boundary) != INTEGER_CST)
913 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
915 if (cmpc == GE_EXPR || cmpc == GT_EXPR
918 cmpc = invert_tree_comparison (cmpc, false);
925 result = tree_int_cst_equal (val, boundary);
926 else if (cmpc == LT_EXPR)
927 result = tree_int_cst_lt (val, boundary);
930 gcc_assert (cmpc == LE_EXPR);
931 result = tree_int_cst_le (val, boundary);
937 result = tree_int_cst_equal (val, boundary);
938 else if (cmpc == LT_EXPR)
939 result = tree_int_cst_lt (val, boundary);
942 gcc_assert (cmpc == LE_EXPR);
943 result = (tree_int_cst_equal (val, boundary)
944 || tree_int_cst_lt (val, boundary));
954 /* Returns true if PRED is common among all the predicate
955 chains (PREDS) (and therefore can be factored out).
956 NUM_PRED_CHAIN is the size of array PREDS. */
959 find_matching_predicate_in_rest_chains (pred_info pred,
960 pred_chain_union preds,
961 size_t num_pred_chains)
966 if (num_pred_chains == 1)
969 for (i = 1; i < num_pred_chains; i++)
972 pred_chain one_chain = preds[i];
973 n = one_chain.length ();
974 for (j = 0; j < n; j++)
976 pred_info pred2 = one_chain[j];
977 /* Can relax the condition comparison to not
978 use address comparison. However, the most common
979 case is that multiple control dependent paths share
980 a common path prefix, so address comparison should
983 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
984 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
985 && pred2.invert == pred.invert)
997 /* Forward declaration. */
999 is_use_properly_guarded (gimple use_stmt,
1002 unsigned uninit_opnds,
1003 hash_set<gphi *> *visited_phis);
1005 /* Returns true if all uninitialized opnds are pruned. Returns false
1006 otherwise. PHI is the phi node with uninitialized operands,
1007 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1008 FLAG_DEF is the statement defining the flag guarding the use of the
1009 PHI output, BOUNDARY_CST is the const value used in the predicate
1010 associated with the flag, CMP_CODE is the comparison code used in
1011 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1012 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1018 flag_1 = phi <0, 1> // (1)
1019 var_1 = phi <undef, some_val>
1023 flag_2 = phi <0, flag_1, flag_1> // (2)
1024 var_2 = phi <undef, var_1, var_1>
1031 Because some flag arg in (1) is not constant, if we do not look into the
1032 flag phis recursively, it is conservatively treated as unknown and var_1
1033 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
1034 a false warning will be emitted. Checking recursively into (1), the compiler can
1035 find out that only some_val (which is defined) can flow into (3) which is OK.
1040 prune_uninit_phi_opnds_in_unrealizable_paths (gphi *phi,
1041 unsigned uninit_opnds,
1044 enum tree_code cmp_code,
1045 hash_set<gphi *> *visited_phis,
1046 bitmap *visited_flag_phis)
1050 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
1054 if (!MASK_TEST_BIT (uninit_opnds, i))
1057 flag_arg = gimple_phi_arg_def (flag_def, i);
1058 if (!is_gimple_constant (flag_arg))
1060 gphi *flag_arg_def, *phi_arg_def;
1062 unsigned uninit_opnds_arg_phi;
1064 if (TREE_CODE (flag_arg) != SSA_NAME)
1066 flag_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (flag_arg));
1070 phi_arg = gimple_phi_arg_def (phi, i);
1071 if (TREE_CODE (phi_arg) != SSA_NAME)
1074 phi_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1078 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1081 if (!*visited_flag_phis)
1082 *visited_flag_phis = BITMAP_ALLOC (NULL);
1084 if (bitmap_bit_p (*visited_flag_phis,
1085 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
1088 bitmap_set_bit (*visited_flag_phis,
1089 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1091 /* Now recursively prune the uninitialized phi args. */
1092 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1093 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1094 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def,
1095 boundary_cst, cmp_code, visited_phis, visited_flag_phis))
1098 bitmap_clear_bit (*visited_flag_phis,
1099 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1103 /* Now check if the constant is in the guarded range. */
1104 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1109 /* Now that we know that this undefined edge is not
1110 pruned. If the operand is defined by another phi,
1111 we can further prune the incoming edges of that
1112 phi by checking the predicates of this operands. */
1114 opnd = gimple_phi_arg_def (phi, i);
1115 opnd_def = SSA_NAME_DEF_STMT (opnd);
1116 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
1119 unsigned uninit_opnds2
1120 = compute_uninit_opnds_pos (opnd_def_phi);
1121 gcc_assert (!MASK_EMPTY (uninit_opnds2));
1122 opnd_edge = gimple_phi_arg_edge (phi, i);
1123 if (!is_use_properly_guarded (phi,
1138 /* A helper function that determines if the predicate set
1139 of the use is not overlapping with that of the uninit paths.
1140 The most common senario of guarded use is in Example 1:
1153 The real world examples are usually more complicated, but similar
1154 and usually result from inlining:
1156 bool init_func (int * x)
1175 Another possible use scenario is in the following trivial example:
1187 Predicate analysis needs to compute the composite predicate:
1189 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1190 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1191 (the predicate chain for phi operand defs can be computed
1192 starting from a bb that is control equivalent to the phi's
1193 bb and is dominating the operand def.)
1195 and check overlapping:
1196 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1199 This implementation provides framework that can handle
1200 scenarios. (Note that many simple cases are handled properly
1201 without the predicate analysis -- this is due to jump threading
1202 transformation which eliminates the merge point thus makes
1203 path sensitive analysis unnecessary.)
1205 NUM_PREDS is the number is the number predicate chains, PREDS is
1206 the array of chains, PHI is the phi node whose incoming (undefined)
1207 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1208 uninit operand positions. VISITED_PHIS is the pointer set of phi
1209 stmts being checked. */
1213 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1214 gphi *phi, unsigned uninit_opnds,
1215 hash_set<gphi *> *visited_phis)
1218 gimple flag_def = 0;
1219 tree boundary_cst = 0;
1220 enum tree_code cmp_code;
1221 bool swap_cond = false;
1222 bool invert = false;
1223 pred_chain the_pred_chain = vNULL;
1224 bitmap visited_flag_phis = NULL;
1225 bool all_pruned = false;
1226 size_t num_preds = preds.length ();
1228 gcc_assert (num_preds > 0);
1229 /* Find within the common prefix of multiple predicate chains
1230 a predicate that is a comparison of a flag variable against
1232 the_pred_chain = preds[0];
1233 n = the_pred_chain.length ();
1234 for (i = 0; i < n; i++)
1236 tree cond_lhs, cond_rhs, flag = 0;
1238 pred_info the_pred = the_pred_chain[i];
1240 invert = the_pred.invert;
1241 cond_lhs = the_pred.pred_lhs;
1242 cond_rhs = the_pred.pred_rhs;
1243 cmp_code = the_pred.cond_code;
1245 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1246 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1248 boundary_cst = cond_rhs;
1251 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1252 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1254 boundary_cst = cond_lhs;
1262 flag_def = SSA_NAME_DEF_STMT (flag);
1267 if ((gimple_code (flag_def) == GIMPLE_PHI)
1268 && (gimple_bb (flag_def) == gimple_bb (phi))
1269 && find_matching_predicate_in_rest_chains (the_pred, preds,
1279 /* Now check all the uninit incoming edge has a constant flag value
1280 that is in conflict with the use guard/predicate. */
1281 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1283 if (cmp_code == ERROR_MARK)
1286 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
1288 as_a <gphi *> (flag_def),
1292 &visited_flag_phis);
1294 if (visited_flag_phis)
1295 BITMAP_FREE (visited_flag_phis);
1300 /* The helper function returns true if two predicates X1 and X2
1301 are equivalent. It assumes the expressions have already
1302 properly re-associated. */
1305 pred_equal_p (pred_info x1, pred_info x2)
1307 enum tree_code c1, c2;
1308 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1309 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1313 if (x1.invert != x2.invert
1314 && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison)
1315 c2 = invert_tree_comparison (x2.cond_code, false);
1322 /* Returns true if the predication is testing !=. */
1325 is_neq_relop_p (pred_info pred)
1328 return (pred.cond_code == NE_EXPR && !pred.invert)
1329 || (pred.cond_code == EQ_EXPR && pred.invert);
1332 /* Returns true if pred is of the form X != 0. */
1335 is_neq_zero_form_p (pred_info pred)
1337 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1338 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1343 /* The helper function returns true if two predicates X1
1344 is equivalent to X2 != 0. */
1347 pred_expr_equal_p (pred_info x1, tree x2)
1349 if (!is_neq_zero_form_p (x1))
1352 return operand_equal_p (x1.pred_lhs, x2, 0);
1355 /* Returns true of the domain of single predicate expression
1356 EXPR1 is a subset of that of EXPR2. Returns false if it
1357 can not be proved. */
1360 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1362 enum tree_code code1, code2;
1364 if (pred_equal_p (expr1, expr2))
1367 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1368 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1371 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1374 code1 = expr1.cond_code;
1376 code1 = invert_tree_comparison (code1, false);
1377 code2 = expr2.cond_code;
1379 code2 = invert_tree_comparison (code2, false);
1381 if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR)
1382 && code2 == BIT_AND_EXPR)
1383 return wi::eq_p (expr1.pred_rhs,
1384 wi::bit_and (expr1.pred_rhs, expr2.pred_rhs));
1386 if (code1 != code2 && code2 != NE_EXPR)
1389 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1395 /* Returns true if the domain of PRED1 is a subset
1396 of that of PRED2. Returns false if it can not be proved so. */
1399 is_pred_chain_subset_of (pred_chain pred1,
1402 size_t np1, np2, i1, i2;
1404 np1 = pred1.length ();
1405 np2 = pred2.length ();
1407 for (i2 = 0; i2 < np2; i2++)
1410 pred_info info2 = pred2[i2];
1411 for (i1 = 0; i1 < np1; i1++)
1413 pred_info info1 = pred1[i1];
1414 if (is_pred_expr_subset_of (info1, info2))
1426 /* Returns true if the domain defined by
1427 one pred chain ONE_PRED is a subset of the domain
1428 of *PREDS. It returns false if ONE_PRED's domain is
1429 not a subset of any of the sub-domains of PREDS
1430 (corresponding to each individual chains in it), even
1431 though it may be still be a subset of whole domain
1432 of PREDS which is the union (ORed) of all its subdomains.
1433 In other words, the result is conservative. */
1436 is_included_in (pred_chain one_pred, pred_chain_union preds)
1439 size_t n = preds.length ();
1441 for (i = 0; i < n; i++)
1443 if (is_pred_chain_subset_of (one_pred, preds[i]))
1450 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1451 true if the domain defined by PREDS1 is a superset
1452 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1453 PREDS2 respectively. The implementation chooses not to build
1454 generic trees (and relying on the folding capability of the
1455 compiler), but instead performs brute force comparison of
1456 individual predicate chains (won't be a compile time problem
1457 as the chains are pretty short). When the function returns
1458 false, it does not necessarily mean *PREDS1 is not a superset
1459 of *PREDS2, but mean it may not be so since the analysis can
1460 not prove it. In such cases, false warnings may still be
1464 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1467 pred_chain one_pred_chain = vNULL;
1469 n2 = preds2.length ();
1471 for (i = 0; i < n2; i++)
1473 one_pred_chain = preds2[i];
1474 if (!is_included_in (one_pred_chain, preds1))
1481 /* Returns true if TC is AND or OR. */
1484 is_and_or_or_p (enum tree_code tc, tree type)
1486 return (tc == BIT_IOR_EXPR
1487 || (tc == BIT_AND_EXPR
1488 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1491 /* Returns true if X1 is the negate of X2. */
1494 pred_neg_p (pred_info x1, pred_info x2)
1496 enum tree_code c1, c2;
1497 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1498 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1502 if (x1.invert == x2.invert)
1503 c2 = invert_tree_comparison (x2.cond_code, false);
1510 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1511 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1512 3) X OR (!X AND Y) is equivalent to (X OR Y);
1513 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1515 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1518 PREDS is the predicate chains, and N is the number of chains. */
1520 /* Helper function to implement rule 1 above. ONE_CHAIN is
1521 the AND predication to be simplified. */
1524 simplify_pred (pred_chain *one_chain)
1527 bool simplified = false;
1528 pred_chain s_chain = vNULL;
1530 n = one_chain->length ();
1532 for (i = 0; i < n; i++)
1534 pred_info *a_pred = &(*one_chain)[i];
1536 if (!a_pred->pred_lhs)
1538 if (!is_neq_zero_form_p (*a_pred))
1541 gimple def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1542 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1544 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1546 for (j = 0; j < n; j++)
1548 pred_info *b_pred = &(*one_chain)[j];
1550 if (!b_pred->pred_lhs)
1552 if (!is_neq_zero_form_p (*b_pred))
1555 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1556 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1558 /* Mark a_pred for removal. */
1559 a_pred->pred_lhs = NULL;
1560 a_pred->pred_rhs = NULL;
1571 for (i = 0; i < n; i++)
1573 pred_info *a_pred = &(*one_chain)[i];
1574 if (!a_pred->pred_lhs)
1576 s_chain.safe_push (*a_pred);
1579 one_chain->release ();
1580 *one_chain = s_chain;
1583 /* The helper function implements the rule 2 for the
1586 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1589 simplify_preds_2 (pred_chain_union *preds)
1592 bool simplified = false;
1593 pred_chain_union s_preds = vNULL;
1595 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1596 (X AND Y) OR (X AND !Y) is equivalent to X. */
1598 n = preds->length ();
1599 for (i = 0; i < n; i++)
1602 pred_chain *a_chain = &(*preds)[i];
1604 if (a_chain->length () != 2)
1610 for (j = 0; j < n; j++)
1612 pred_chain *b_chain;
1618 b_chain = &(*preds)[j];
1619 if (b_chain->length () != 2)
1625 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1628 a_chain->release ();
1629 b_chain->release ();
1630 b_chain->safe_push (x);
1634 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1637 a_chain->release ();
1638 b_chain->release ();
1639 b_chain->safe_push (y);
1645 /* Now clean up the chain. */
1648 for (i = 0; i < n; i++)
1650 if ((*preds)[i].is_empty ())
1652 s_preds.safe_push ((*preds)[i]);
1662 /* The helper function implements the rule 2 for the
1665 3) x OR (!x AND y) is equivalent to x OR y. */
1668 simplify_preds_3 (pred_chain_union *preds)
1671 bool simplified = false;
1673 /* Now iteratively simplify X OR (!X AND Z ..)
1674 into X OR (Z ...). */
1676 n = preds->length ();
1680 for (i = 0; i < n; i++)
1683 pred_chain *a_chain = &(*preds)[i];
1685 if (a_chain->length () != 1)
1690 for (j = 0; j < n; j++)
1692 pred_chain *b_chain;
1699 b_chain = &(*preds)[j];
1700 if (b_chain->length () < 2)
1703 for (k = 0; k < b_chain->length (); k++)
1706 if (pred_neg_p (x, x2))
1708 b_chain->unordered_remove (k);
1718 /* The helper function implements the rule 4 for the
1721 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1722 (x != 0 ANd y != 0). */
1725 simplify_preds_4 (pred_chain_union *preds)
1728 bool simplified = false;
1729 pred_chain_union s_preds = vNULL;
1732 n = preds->length ();
1733 for (i = 0; i < n; i++)
1736 pred_chain *a_chain = &(*preds)[i];
1738 if (a_chain->length () != 1)
1743 if (!is_neq_zero_form_p (z))
1746 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1747 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1750 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1753 for (j = 0; j < n; j++)
1755 pred_chain *b_chain;
1761 b_chain = &(*preds)[j];
1762 if (b_chain->length () != 2)
1767 if (!is_neq_zero_form_p (x2)
1768 || !is_neq_zero_form_p (y2))
1771 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1772 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1773 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1774 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1777 a_chain->release ();
1783 /* Now clean up the chain. */
1786 for (i = 0; i < n; i++)
1788 if ((*preds)[i].is_empty ())
1790 s_preds.safe_push ((*preds)[i]);
1801 /* This function simplifies predicates in PREDS. */
1804 simplify_preds (pred_chain_union *preds, gimple use_or_def, bool is_use)
1807 bool changed = false;
1809 if (dump_file && dump_flags & TDF_DETAILS)
1811 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1812 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1815 for (i = 0; i < preds->length (); i++)
1816 simplify_pred (&(*preds)[i]);
1818 n = preds->length ();
1825 if (simplify_preds_2 (preds))
1828 /* Now iteratively simplify X OR (!X AND Z ..)
1829 into X OR (Z ...). */
1830 if (simplify_preds_3 (preds))
1833 if (simplify_preds_4 (preds))
1841 /* This is a helper function which attempts to normalize predicate chains
1842 by following UD chains. It basically builds up a big tree of either IOR
1843 operations or AND operations, and convert the IOR tree into a
1844 pred_chain_union or BIT_AND tree into a pred_chain.
1854 then _t != 0 will be normalized into a pred_chain_union
1856 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1866 then _t != 0 will be normalized into a pred_chain:
1867 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1871 /* This is a helper function that stores a PRED into NORM_PREDS. */
1874 push_pred (pred_chain_union *norm_preds, pred_info pred)
1876 pred_chain pred_chain = vNULL;
1877 pred_chain.safe_push (pred);
1878 norm_preds->safe_push (pred_chain);
1881 /* A helper function that creates a predicate of the form
1882 OP != 0 and push it WORK_LIST. */
1885 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1886 hash_set<tree> *mark_set)
1888 if (mark_set->contains (op))
1893 arg_pred.pred_lhs = op;
1894 arg_pred.pred_rhs = integer_zero_node;
1895 arg_pred.cond_code = NE_EXPR;
1896 arg_pred.invert = false;
1897 work_list->safe_push (arg_pred);
1900 /* A helper that generates a pred_info from a gimple assignment
1901 CMP_ASSIGN with comparison rhs. */
1904 get_pred_info_from_cmp (gimple cmp_assign)
1907 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
1908 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
1909 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
1910 n_pred.invert = false;
1914 /* Returns true if the PHI is a degenerated phi with
1915 all args with the same value (relop). In that case, *PRED
1916 will be updated to that value. */
1919 is_degenerated_phi (gimple phi, pred_info *pred_p)
1926 n = gimple_phi_num_args (phi);
1927 op0 = gimple_phi_arg_def (phi, 0);
1929 if (TREE_CODE (op0) != SSA_NAME)
1932 def0 = SSA_NAME_DEF_STMT (op0);
1933 if (gimple_code (def0) != GIMPLE_ASSIGN)
1935 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0))
1938 pred0 = get_pred_info_from_cmp (def0);
1940 for (i = 1; i < n; ++i)
1944 tree op = gimple_phi_arg_def (phi, i);
1946 if (TREE_CODE (op) != SSA_NAME)
1949 def = SSA_NAME_DEF_STMT (op);
1950 if (gimple_code (def) != GIMPLE_ASSIGN)
1952 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def))
1955 pred = get_pred_info_from_cmp (def);
1956 if (!pred_equal_p (pred, pred0))
1964 /* Normalize one predicate PRED
1965 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1966 2) otherwise if PRED is of the form x != 0, follow x's definition
1967 and put normalized predicates into WORK_LIST. */
1970 normalize_one_pred_1 (pred_chain_union *norm_preds,
1971 pred_chain *norm_chain,
1973 enum tree_code and_or_code,
1974 vec<pred_info, va_heap, vl_ptr> *work_list,
1975 hash_set<tree> *mark_set)
1977 if (!is_neq_zero_form_p (pred))
1979 if (and_or_code == BIT_IOR_EXPR)
1980 push_pred (norm_preds, pred);
1982 norm_chain->safe_push (pred);
1986 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1988 if (gimple_code (def_stmt) == GIMPLE_PHI
1989 && is_degenerated_phi (def_stmt, &pred))
1990 work_list->safe_push (pred);
1991 else if (gimple_code (def_stmt) == GIMPLE_PHI
1992 && and_or_code == BIT_IOR_EXPR)
1995 n = gimple_phi_num_args (def_stmt);
1997 /* If we see non zero constant, we should punt. The predicate
1998 * should be one guarding the phi edge. */
1999 for (i = 0; i < n; ++i)
2001 tree op = gimple_phi_arg_def (def_stmt, i);
2002 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
2004 push_pred (norm_preds, pred);
2009 for (i = 0; i < n; ++i)
2011 tree op = gimple_phi_arg_def (def_stmt, i);
2012 if (integer_zerop (op))
2015 push_to_worklist (op, work_list, mark_set);
2018 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2020 if (and_or_code == BIT_IOR_EXPR)
2021 push_pred (norm_preds, pred);
2023 norm_chain->safe_push (pred);
2025 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
2027 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2028 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
2030 /* But treat x & 3 as condition. */
2031 if (and_or_code == BIT_AND_EXPR)
2034 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
2035 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
2036 n_pred.cond_code = and_or_code;
2037 n_pred.invert = false;
2038 norm_chain->safe_push (n_pred);
2043 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
2044 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
2047 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
2050 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2051 if (and_or_code == BIT_IOR_EXPR)
2052 push_pred (norm_preds, n_pred);
2054 norm_chain->safe_push (n_pred);
2058 if (and_or_code == BIT_IOR_EXPR)
2059 push_pred (norm_preds, pred);
2061 norm_chain->safe_push (pred);
2065 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2068 normalize_one_pred (pred_chain_union *norm_preds,
2071 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2072 enum tree_code and_or_code = ERROR_MARK;
2073 pred_chain norm_chain = vNULL;
2075 if (!is_neq_zero_form_p (pred))
2077 push_pred (norm_preds, pred);
2081 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2082 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2083 and_or_code = gimple_assign_rhs_code (def_stmt);
2084 if (and_or_code != BIT_IOR_EXPR
2085 && and_or_code != BIT_AND_EXPR)
2087 if (TREE_CODE_CLASS (and_or_code)
2090 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2091 push_pred (norm_preds, n_pred);
2094 push_pred (norm_preds, pred);
2098 work_list.safe_push (pred);
2099 hash_set<tree> mark_set;
2101 while (!work_list.is_empty ())
2103 pred_info a_pred = work_list.pop ();
2104 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred,
2105 and_or_code, &work_list, &mark_set);
2107 if (and_or_code == BIT_AND_EXPR)
2108 norm_preds->safe_push (norm_chain);
2110 work_list.release ();
2114 normalize_one_pred_chain (pred_chain_union *norm_preds,
2115 pred_chain one_chain)
2117 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2118 hash_set<tree> mark_set;
2119 pred_chain norm_chain = vNULL;
2122 for (i = 0; i < one_chain.length (); i++)
2124 work_list.safe_push (one_chain[i]);
2125 mark_set.add (one_chain[i].pred_lhs);
2128 while (!work_list.is_empty ())
2130 pred_info a_pred = work_list.pop ();
2131 normalize_one_pred_1 (0, &norm_chain, a_pred,
2132 BIT_AND_EXPR, &work_list, &mark_set);
2135 norm_preds->safe_push (norm_chain);
2136 work_list.release ();
2139 /* Normalize predicate chains PREDS and returns the normalized one. */
2141 static pred_chain_union
2142 normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use)
2144 pred_chain_union norm_preds = vNULL;
2145 size_t n = preds.length ();
2148 if (dump_file && dump_flags & TDF_DETAILS)
2150 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2151 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2154 for (i = 0; i < n; i++)
2156 if (preds[i].length () != 1)
2157 normalize_one_pred_chain (&norm_preds, preds[i]);
2160 normalize_one_pred (&norm_preds, preds[i][0]);
2161 preds[i].release ();
2167 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2168 dump_predicates (use_or_def, norm_preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2176 /* Computes the predicates that guard the use and checks
2177 if the incoming paths that have empty (or possibly
2178 empty) definition can be pruned/filtered. The function returns
2179 true if it can be determined that the use of PHI's def in
2180 USE_STMT is guarded with a predicate set not overlapping with
2181 predicate sets of all runtime paths that do not have a definition.
2182 Returns false if it is not or it can not be determined. USE_BB is
2183 the bb of the use (for phi operand use, the bb is not the bb of
2184 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2185 is a bit vector. If an operand of PHI is uninitialized, the
2186 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2187 set of phis being visted. */
2190 is_use_properly_guarded (gimple use_stmt,
2193 unsigned uninit_opnds,
2194 hash_set<gphi *> *visited_phis)
2197 pred_chain_union preds = vNULL;
2198 pred_chain_union def_preds = vNULL;
2199 bool has_valid_preds = false;
2200 bool is_properly_guarded = false;
2202 if (visited_phis->add (phi))
2205 phi_bb = gimple_bb (phi);
2207 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2210 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2212 if (!has_valid_preds)
2214 destroy_predicate_vecs (preds);
2218 /* Try to prune the dead incoming phi edges. */
2220 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2223 if (is_properly_guarded)
2225 destroy_predicate_vecs (preds);
2229 has_valid_preds = find_def_preds (&def_preds, phi);
2231 if (!has_valid_preds)
2233 destroy_predicate_vecs (preds);
2234 destroy_predicate_vecs (def_preds);
2238 simplify_preds (&preds, use_stmt, true);
2239 preds = normalize_preds (preds, use_stmt, true);
2241 simplify_preds (&def_preds, phi, false);
2242 def_preds = normalize_preds (def_preds, phi, false);
2244 is_properly_guarded = is_superset_of (def_preds, preds);
2246 destroy_predicate_vecs (preds);
2247 destroy_predicate_vecs (def_preds);
2248 return is_properly_guarded;
2251 /* Searches through all uses of a potentially
2252 uninitialized variable defined by PHI and returns a use
2253 statement if the use is not properly guarded. It returns
2254 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2255 holding the position(s) of uninit PHI operands. WORKLIST
2256 is the vector of candidate phis that may be updated by this
2257 function. ADDED_TO_WORKLIST is the pointer set tracking
2258 if the new phi is already in the worklist. */
2261 find_uninit_use (gphi *phi, unsigned uninit_opnds,
2262 vec<gphi *> *worklist,
2263 hash_set<gphi *> *added_to_worklist)
2266 use_operand_p use_p;
2268 imm_use_iterator iter;
2270 phi_result = gimple_phi_result (phi);
2272 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2276 use_stmt = USE_STMT (use_p);
2277 if (is_gimple_debug (use_stmt))
2280 if (gphi *use_phi = dyn_cast <gphi *> (use_stmt))
2281 use_bb = gimple_phi_arg_edge (use_phi,
2282 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2284 use_bb = gimple_bb (use_stmt);
2286 hash_set<gphi *> visited_phis;
2287 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2291 if (dump_file && (dump_flags & TDF_DETAILS))
2293 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2294 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2296 /* Found one real use, return. */
2297 if (gimple_code (use_stmt) != GIMPLE_PHI)
2300 /* Found a phi use that is not guarded,
2301 add the phi to the worklist. */
2302 if (!added_to_worklist->add (as_a <gphi *> (use_stmt)))
2304 if (dump_file && (dump_flags & TDF_DETAILS))
2306 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2307 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2310 worklist->safe_push (as_a <gphi *> (use_stmt));
2311 possibly_undefined_names->add (phi_result);
2318 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2319 and gives warning if there exists a runtime path from the entry to a
2320 use of the PHI def that does not contain a definition. In other words,
2321 the warning is on the real use. The more dead paths that can be pruned
2322 by the compiler, the fewer false positives the warning is. WORKLIST
2323 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2324 a pointer set tracking if the new phi is added to the worklist or not. */
2327 warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
2328 hash_set<gphi *> *added_to_worklist)
2330 unsigned uninit_opnds;
2331 gimple uninit_use_stmt = 0;
2336 /* Don't look at virtual operands. */
2337 if (virtual_operand_p (gimple_phi_result (phi)))
2340 uninit_opnds = compute_uninit_opnds_pos (phi);
2342 if (MASK_EMPTY (uninit_opnds))
2345 if (dump_file && (dump_flags & TDF_DETAILS))
2347 fprintf (dump_file, "[CHECK]: examining phi: ");
2348 print_gimple_stmt (dump_file, phi, 0, 0);
2351 /* Now check if we have any use of the value without proper guard. */
2352 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2353 worklist, added_to_worklist);
2355 /* All uses are properly guarded. */
2356 if (!uninit_use_stmt)
2359 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2360 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2361 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2363 if (gimple_phi_arg_has_location (phi, phiarg_index))
2364 loc = gimple_phi_arg_location (phi, phiarg_index);
2366 loc = UNKNOWN_LOCATION;
2367 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2368 SSA_NAME_VAR (uninit_op),
2369 "%qD may be used uninitialized in this function",
2370 uninit_use_stmt, loc);
2375 gate_warn_uninitialized (void)
2377 return warn_uninitialized || warn_maybe_uninitialized;
2382 const pass_data pass_data_late_warn_uninitialized =
2384 GIMPLE_PASS, /* type */
2385 "uninit", /* name */
2386 OPTGROUP_NONE, /* optinfo_flags */
2387 TV_NONE, /* tv_id */
2388 PROP_ssa, /* properties_required */
2389 0, /* properties_provided */
2390 0, /* properties_destroyed */
2391 0, /* todo_flags_start */
2392 0, /* todo_flags_finish */
2395 class pass_late_warn_uninitialized : public gimple_opt_pass
2398 pass_late_warn_uninitialized (gcc::context *ctxt)
2399 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2402 /* opt_pass methods: */
2403 opt_pass * clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2404 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2405 virtual unsigned int execute (function *);
2407 }; // class pass_late_warn_uninitialized
2410 pass_late_warn_uninitialized::execute (function *fun)
2414 vec<gphi *> worklist = vNULL;
2416 calculate_dominance_info (CDI_DOMINATORS);
2417 calculate_dominance_info (CDI_POST_DOMINATORS);
2418 /* Re-do the plain uninitialized variable check, as optimization may have
2419 straightened control flow. Do this first so that we don't accidentally
2420 get a "may be" warning when we'd have seen an "is" warning later. */
2421 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2423 timevar_push (TV_TREE_UNINIT);
2425 possibly_undefined_names = new hash_set<tree>;
2426 hash_set<gphi *> added_to_worklist;
2428 /* Initialize worklist */
2429 FOR_EACH_BB_FN (bb, fun)
2430 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2432 gphi *phi = gsi.phi ();
2435 n = gimple_phi_num_args (phi);
2437 /* Don't look at virtual operands. */
2438 if (virtual_operand_p (gimple_phi_result (phi)))
2441 for (i = 0; i < n; ++i)
2443 tree op = gimple_phi_arg_def (phi, i);
2444 if (TREE_CODE (op) == SSA_NAME
2445 && uninit_undefined_value_p (op))
2447 worklist.safe_push (phi);
2448 added_to_worklist.add (phi);
2449 if (dump_file && (dump_flags & TDF_DETAILS))
2451 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2452 print_gimple_stmt (dump_file, phi, 0, 0);
2459 while (worklist.length () != 0)
2462 cur_phi = worklist.pop ();
2463 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
2466 worklist.release ();
2467 delete possibly_undefined_names;
2468 possibly_undefined_names = NULL;
2469 free_dominance_info (CDI_POST_DOMINATORS);
2470 timevar_pop (TV_TREE_UNINIT);
2477 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2479 return new pass_late_warn_uninitialized (ctxt);
2484 execute_early_warn_uninitialized (void)
2486 /* Currently, this pass runs always but
2487 execute_late_warn_uninitialized only runs with optimization. With
2488 optimization we want to warn about possible uninitialized as late
2489 as possible, thus don't do it here. However, without
2490 optimization we need to warn here about "may be uninitialized". */
2491 calculate_dominance_info (CDI_POST_DOMINATORS);
2493 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2495 /* Post-dominator information can not be reliably updated. Free it
2498 free_dominance_info (CDI_POST_DOMINATORS);
2505 const pass_data pass_data_early_warn_uninitialized =
2507 GIMPLE_PASS, /* type */
2508 "*early_warn_uninitialized", /* name */
2509 OPTGROUP_NONE, /* optinfo_flags */
2510 TV_TREE_UNINIT, /* tv_id */
2511 PROP_ssa, /* properties_required */
2512 0, /* properties_provided */
2513 0, /* properties_destroyed */
2514 0, /* todo_flags_start */
2515 0, /* todo_flags_finish */
2518 class pass_early_warn_uninitialized : public gimple_opt_pass
2521 pass_early_warn_uninitialized (gcc::context *ctxt)
2522 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2525 /* opt_pass methods: */
2526 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2527 virtual unsigned int execute (function *)
2529 return execute_early_warn_uninitialized ();
2532 }; // class pass_early_warn_uninitialized
2537 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2539 return new pass_early_warn_uninitialized (ctxt);