1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2014 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-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
43 #include "tree-inline.h"
45 #include "tree-pass.h"
46 #include "diagnostic-core.h"
49 /* This implements the pass that does predicate aware warning on uses of
50 possibly uninitialized variables. The pass first collects the set of
51 possibly uninitialized SSA names. For each such name, it walks through
52 all its immediate uses. For each immediate use, it rebuilds the condition
53 expression (the predicate) that guards the use. The predicate is then
54 examined to see if the variable is always defined under that same condition.
55 This is done either by pruning the unrealizable paths that lead to the
56 default definitions or by checking if the predicate set that guards the
57 defining paths is a superset of the use predicate. */
60 /* Pointer set of potentially undefined ssa names, i.e.,
61 ssa names that are defined by phi with operands that
62 are not defined or potentially undefined. */
63 static pointer_set_t *possibly_undefined_names = 0;
65 /* Bit mask handling macros. */
66 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
67 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
68 #define MASK_EMPTY(mask) (mask == 0)
70 /* Returns the first bit position (starting from LSB)
71 in mask that is non zero. Returns -1 if the mask is empty. */
73 get_mask_first_set_bit (unsigned mask)
79 while ((mask & (1 << pos)) == 0)
84 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
86 /* Return true if T, an SSA_NAME, has an undefined value. */
88 has_undefined_value_p (tree t)
90 return (ssa_undefined_value_p (t)
91 || (possibly_undefined_names
92 && pointer_set_contains (possibly_undefined_names, t)));
97 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
98 is set on SSA_NAME_VAR. */
101 uninit_undefined_value_p (tree t) {
102 if (!has_undefined_value_p (t))
104 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
109 /* Emit warnings for uninitialized variables. This is done in two passes.
111 The first pass notices real uses of SSA names with undefined values.
112 Such uses are unconditionally uninitialized, and we can be certain that
113 such a use is a mistake. This pass is run before most optimizations,
114 so that we catch as many as we can.
116 The second pass follows PHI nodes to find uses that are potentially
117 uninitialized. In this case we can't necessarily prove that the use
118 is really uninitialized. This pass is run after most optimizations,
119 so that we thread as many jumps and possible, and delete as much dead
120 code as possible, in order to reduce false positives. We also look
121 again for plain uninitialized variables, since optimization may have
122 changed conditionally uninitialized to unconditionally uninitialized. */
124 /* Emit a warning for EXPR based on variable VAR at the point in the
125 program T, an SSA_NAME, is used being uninitialized. The exact
126 warning text is in MSGID and LOCUS may contain a location or be null.
127 WC is the warning code. */
130 warn_uninit (enum opt_code wc, tree t,
131 tree expr, tree var, const char *gmsgid, void *data)
133 gimple context = (gimple) data;
134 location_t location, cfun_loc;
135 expanded_location xloc, floc;
137 if (!has_undefined_value_p (t))
140 /* TREE_NO_WARNING either means we already warned, or the front end
141 wishes to suppress the warning. */
143 && (gimple_no_warning_p (context)
144 || (gimple_assign_single_p (context)
145 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
146 || TREE_NO_WARNING (expr))
149 location = (context != NULL && gimple_has_location (context))
150 ? gimple_location (context)
151 : DECL_SOURCE_LOCATION (var);
152 location = map_discriminator_location (location);
153 location = linemap_resolve_location (line_table, location,
154 LRK_SPELLING_LOCATION,
156 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
157 xloc = expand_location (location);
158 floc = expand_location (cfun_loc);
159 if (warning_at (location, wc, gmsgid, expr))
161 TREE_NO_WARNING (expr) = 1;
163 if (location == DECL_SOURCE_LOCATION (var))
165 if (xloc.file != floc.file
166 || linemap_location_before_p (line_table,
168 || linemap_location_before_p (line_table,
169 cfun->function_end_locus,
171 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
176 warn_uninitialized_vars (bool warn_possibly_uninitialized)
178 gimple_stmt_iterator gsi;
181 FOR_EACH_BB_FN (bb, cfun)
183 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS,
184 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb);
185 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
187 gimple stmt = gsi_stmt (gsi);
192 if (is_gimple_debug (stmt))
195 /* We only do data flow with SSA_NAMEs, so that's all we
197 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
199 use = USE_FROM_PTR (use_p);
201 warn_uninit (OPT_Wuninitialized, use,
202 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
203 "%qD is used uninitialized in this function",
205 else if (warn_possibly_uninitialized)
206 warn_uninit (OPT_Wmaybe_uninitialized, use,
207 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
208 "%qD may be used uninitialized in this function",
212 /* For memory the only cheap thing we can do is see if we
213 have a use of the default def of the virtual operand.
214 ??? Note that at -O0 we do not have virtual operands.
215 ??? Not so cheap would be to use the alias oracle via
216 walk_aliased_vdefs, if we don't find any aliasing vdef
217 warn as is-used-uninitialized, if we don't find an aliasing
218 vdef that kills our use (stmt_kills_ref_p), warn as
219 may-be-used-uninitialized. But this walk is quadratic and
220 so must be limited which means we would miss warning
222 use = gimple_vuse (stmt);
224 && gimple_assign_single_p (stmt)
225 && !gimple_vdef (stmt)
226 && SSA_NAME_IS_DEFAULT_DEF (use))
228 tree rhs = gimple_assign_rhs1 (stmt);
229 tree base = get_base_address (rhs);
231 /* Do not warn if it can be initialized outside this function. */
232 if (TREE_CODE (base) != VAR_DECL
233 || DECL_HARD_REGISTER (base)
234 || is_global_var (base))
238 warn_uninit (OPT_Wuninitialized, use,
239 gimple_assign_rhs1 (stmt), base,
240 "%qE is used uninitialized in this function",
242 else if (warn_possibly_uninitialized)
243 warn_uninit (OPT_Wmaybe_uninitialized, use,
244 gimple_assign_rhs1 (stmt), base,
245 "%qE may be used uninitialized in this function",
254 /* Checks if the operand OPND of PHI is defined by
255 another phi with one operand defined by this PHI,
256 but the rest operands are all defined. If yes,
257 returns true to skip this this operand as being
258 redundant. Can be enhanced to be more general. */
261 can_skip_redundant_opnd (tree opnd, gimple phi)
267 phi_def = gimple_phi_result (phi);
268 op_def = SSA_NAME_DEF_STMT (opnd);
269 if (gimple_code (op_def) != GIMPLE_PHI)
271 n = gimple_phi_num_args (op_def);
272 for (i = 0; i < n; ++i)
274 tree op = gimple_phi_arg_def (op_def, i);
275 if (TREE_CODE (op) != SSA_NAME)
277 if (op != phi_def && uninit_undefined_value_p (op))
284 /* Returns a bit mask holding the positions of arguments in PHI
285 that have empty (or possibly empty) definitions. */
288 compute_uninit_opnds_pos (gimple phi)
291 unsigned uninit_opnds = 0;
293 n = gimple_phi_num_args (phi);
294 /* Bail out for phi with too many args. */
298 for (i = 0; i < n; ++i)
300 tree op = gimple_phi_arg_def (phi, i);
301 if (TREE_CODE (op) == SSA_NAME
302 && uninit_undefined_value_p (op)
303 && !can_skip_redundant_opnd (op, phi))
305 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
307 /* Ignore SSA_NAMEs that appear on abnormal edges
309 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
312 MASK_SET_BIT (uninit_opnds, i);
318 /* Find the immediate postdominator PDOM of the specified
319 basic block BLOCK. */
321 static inline basic_block
322 find_pdom (basic_block block)
324 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
325 return EXIT_BLOCK_PTR_FOR_FN (cfun);
329 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
331 return EXIT_BLOCK_PTR_FOR_FN (cfun);
336 /* Find the immediate DOM of the specified
337 basic block BLOCK. */
339 static inline basic_block
340 find_dom (basic_block block)
342 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
343 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
346 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
348 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
353 /* Returns true if BB1 is postdominating BB2 and BB1 is
354 not a loop exit bb. The loop exit bb check is simple and does
355 not cover all cases. */
358 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
360 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
363 if (single_pred_p (bb1) && !single_succ_p (bb2))
369 /* Find the closest postdominator of a specified BB, which is control
372 static inline basic_block
373 find_control_equiv_block (basic_block bb)
377 pdom = find_pdom (bb);
379 /* Skip the postdominating bb that is also loop exit. */
380 if (!is_non_loop_exit_postdominating (pdom, bb))
383 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
389 #define MAX_NUM_CHAINS 8
390 #define MAX_CHAIN_LEN 5
391 #define MAX_POSTDOM_CHECK 8
393 /* Computes the control dependence chains (paths of edges)
394 for DEP_BB up to the dominating basic block BB (the head node of a
395 chain should be dominated by it). CD_CHAINS is pointer to an
396 array holding the result chains. CUR_CD_CHAIN is the current
397 chain being computed. *NUM_CHAINS is total number of chains. The
398 function returns true if the information is successfully computed,
399 return false if there is no control dependence or not computed. */
402 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
403 vec<edge> *cd_chains,
405 vec<edge> *cur_cd_chain,
411 bool found_cd_chain = false;
412 size_t cur_chain_len = 0;
414 if (EDGE_COUNT (bb->succs) < 2)
417 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
421 /* Could use a set instead. */
422 cur_chain_len = cur_cd_chain->length ();
423 if (cur_chain_len > MAX_CHAIN_LEN)
426 for (i = 0; i < cur_chain_len; i++)
428 edge e = (*cur_cd_chain)[i];
429 /* Cycle detected. */
434 FOR_EACH_EDGE (e, ei, bb->succs)
437 int post_dom_check = 0;
438 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
442 cur_cd_chain->safe_push (e);
443 while (!is_non_loop_exit_postdominating (cd_bb, bb))
447 /* Found a direct control dependence. */
448 if (*num_chains < MAX_NUM_CHAINS)
450 cd_chains[*num_chains] = cur_cd_chain->copy ();
453 found_cd_chain = true;
454 /* Check path from next edge. */
458 /* Now check if DEP_BB is indirectly control dependent on BB. */
459 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
460 num_chains, cur_cd_chain, num_calls))
462 found_cd_chain = true;
466 cd_bb = find_pdom (cd_bb);
468 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || post_dom_check >
472 cur_cd_chain->pop ();
473 gcc_assert (cur_cd_chain->length () == cur_chain_len);
475 gcc_assert (cur_cd_chain->length () == cur_chain_len);
477 return found_cd_chain;
480 /* The type to represent a simple predicate */
482 typedef struct use_def_pred_info
486 enum tree_code cond_code;
490 /* The type to represent a sequence of predicates grouped
491 with .AND. operation. */
493 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
495 /* The type to represent a sequence of pred_chains grouped
496 with .OR. operation. */
498 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
500 /* Converts the chains of control dependence edges into a set of
501 predicates. A control dependence chain is represented by a vector
502 edges. DEP_CHAINS points to an array of dependence chains.
503 NUM_CHAINS is the size of the chain array. One edge in a dependence
504 chain is mapped to predicate expression represented by pred_info
505 type. One dependence chain is converted to a composite predicate that
506 is the result of AND operation of pred_info mapped to each edge.
507 A composite predicate is presented by a vector of pred_info. On
508 return, *PREDS points to the resulting array of composite predicates.
509 *NUM_PREDS is the number of composite predictes. */
512 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
514 pred_chain_union *preds)
516 bool has_valid_pred = false;
518 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
521 /* Now convert the control dep chain into a set
523 preds->reserve (num_chains);
525 for (i = 0; i < num_chains; i++)
527 vec<edge> one_cd_chain = dep_chains[i];
529 has_valid_pred = false;
530 pred_chain t_chain = vNULL;
531 for (j = 0; j < one_cd_chain.length (); j++)
534 gimple_stmt_iterator gsi;
535 basic_block guard_bb;
541 gsi = gsi_last_bb (guard_bb);
544 has_valid_pred = false;
547 cond_stmt = gsi_stmt (gsi);
548 if (is_gimple_call (cond_stmt)
549 && EDGE_COUNT (e->src->succs) >= 2)
551 /* Ignore EH edge. Can add assertion
552 on the other edge's flag. */
555 /* Skip if there is essentially one succesor. */
556 if (EDGE_COUNT (e->src->succs) == 2)
562 FOR_EACH_EDGE (e1, ei1, e->src->succs)
564 if (EDGE_COUNT (e1->dest->succs) == 0)
573 if (gimple_code (cond_stmt) != GIMPLE_COND)
575 has_valid_pred = false;
578 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
579 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
580 one_pred.cond_code = gimple_cond_code (cond_stmt);
581 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
582 t_chain.safe_push (one_pred);
583 has_valid_pred = true;
589 preds->safe_push (t_chain);
591 return has_valid_pred;
594 /* Computes all control dependence chains for USE_BB. The control
595 dependence chains are then converted to an array of composite
596 predicates pointed to by PREDS. PHI_BB is the basic block of
597 the phi whose result is used in USE_BB. */
600 find_predicates (pred_chain_union *preds,
604 size_t num_chains = 0, i;
606 vec<edge> dep_chains[MAX_NUM_CHAINS];
607 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
608 bool has_valid_pred = false;
609 basic_block cd_root = 0;
611 /* First find the closest bb that is control equivalent to PHI_BB
612 that also dominates USE_BB. */
614 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
616 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
617 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
618 cd_root = ctrl_eq_bb;
623 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
624 &cur_chain, &num_calls);
627 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
628 for (i = 0; i < num_chains; i++)
629 dep_chains[i].release ();
630 return has_valid_pred;
633 /* Computes the set of incoming edges of PHI that have non empty
634 definitions of a phi chain. The collection will be done
635 recursively on operands that are defined by phis. CD_ROOT
636 is the control dependence root. *EDGES holds the result, and
637 VISITED_PHIS is a pointer set for detecting cycles. */
640 collect_phi_def_edges (gimple phi, basic_block cd_root,
642 pointer_set_t *visited_phis)
648 if (pointer_set_insert (visited_phis, phi))
651 n = gimple_phi_num_args (phi);
652 for (i = 0; i < n; i++)
654 opnd_edge = gimple_phi_arg_edge (phi, i);
655 opnd = gimple_phi_arg_def (phi, i);
657 if (TREE_CODE (opnd) != SSA_NAME)
659 if (dump_file && (dump_flags & TDF_DETAILS))
661 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
662 print_gimple_stmt (dump_file, phi, 0, 0);
664 edges->safe_push (opnd_edge);
668 gimple def = SSA_NAME_DEF_STMT (opnd);
670 if (gimple_code (def) == GIMPLE_PHI
671 && dominated_by_p (CDI_DOMINATORS,
672 gimple_bb (def), cd_root))
673 collect_phi_def_edges (def, cd_root, edges,
675 else if (!uninit_undefined_value_p (opnd))
677 if (dump_file && (dump_flags & TDF_DETAILS))
679 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
680 print_gimple_stmt (dump_file, phi, 0, 0);
682 edges->safe_push (opnd_edge);
688 /* For each use edge of PHI, computes all control dependence chains.
689 The control dependence chains are then converted to an array of
690 composite predicates pointed to by PREDS. */
693 find_def_preds (pred_chain_union *preds, gimple phi)
695 size_t num_chains = 0, i, n;
696 vec<edge> dep_chains[MAX_NUM_CHAINS];
697 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
698 vec<edge> def_edges = vNULL;
699 bool has_valid_pred = false;
700 basic_block phi_bb, cd_root = 0;
701 pointer_set_t *visited_phis;
703 phi_bb = gimple_bb (phi);
704 /* First find the closest dominating bb to be
705 the control dependence root */
706 cd_root = find_dom (phi_bb);
710 visited_phis = pointer_set_create ();
711 collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
712 pointer_set_destroy (visited_phis);
714 n = def_edges.length ();
718 for (i = 0; i < n; i++)
724 opnd_edge = def_edges[i];
725 prev_nc = num_chains;
726 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
727 &num_chains, &cur_chain, &num_calls);
729 /* Now update the newly added chains with
730 the phi operand edge: */
731 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
733 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
734 dep_chains[num_chains++] = vNULL;
735 for (j = prev_nc; j < num_chains; j++)
736 dep_chains[j].safe_push (opnd_edge);
741 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
742 for (i = 0; i < num_chains; i++)
743 dep_chains[i].release ();
744 return has_valid_pred;
747 /* Dumps the predicates (PREDS) for USESTMT. */
750 dump_predicates (gimple usestmt, pred_chain_union preds,
754 pred_chain one_pred_chain = vNULL;
755 fprintf (dump_file, msg);
756 print_gimple_stmt (dump_file, usestmt, 0, 0);
757 fprintf (dump_file, "is guarded by :\n\n");
758 size_t num_preds = preds.length ();
759 /* Do some dumping here: */
760 for (i = 0; i < num_preds; i++)
764 one_pred_chain = preds[i];
765 np = one_pred_chain.length ();
767 for (j = 0; j < np; j++)
769 pred_info one_pred = one_pred_chain[j];
771 fprintf (dump_file, " (.NOT.) ");
772 print_generic_expr (dump_file, one_pred.pred_lhs, 0);
773 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
774 print_generic_expr (dump_file, one_pred.pred_rhs, 0);
776 fprintf (dump_file, " (.AND.) ");
778 fprintf (dump_file, "\n");
780 if (i < num_preds - 1)
781 fprintf (dump_file, "(.OR.)\n");
783 fprintf (dump_file, "\n\n");
787 /* Destroys the predicate set *PREDS. */
790 destroy_predicate_vecs (pred_chain_union preds)
794 size_t n = preds.length ();
795 for (i = 0; i < n; i++)
801 /* Computes the 'normalized' conditional code with operand
802 swapping and condition inversion. */
804 static enum tree_code
805 get_cmp_code (enum tree_code orig_cmp_code,
806 bool swap_cond, bool invert)
808 enum tree_code tc = orig_cmp_code;
811 tc = swap_tree_comparison (orig_cmp_code);
813 tc = invert_tree_comparison (tc, false);
830 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
831 all values in the range satisfies (x CMPC BOUNDARY) == true. */
834 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
836 bool inverted = false;
840 /* Only handle integer constant here. */
841 if (TREE_CODE (val) != INTEGER_CST
842 || TREE_CODE (boundary) != INTEGER_CST)
845 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
847 if (cmpc == GE_EXPR || cmpc == GT_EXPR
850 cmpc = invert_tree_comparison (cmpc, false);
857 result = tree_int_cst_equal (val, boundary);
858 else if (cmpc == LT_EXPR)
859 result = INT_CST_LT_UNSIGNED (val, boundary);
862 gcc_assert (cmpc == LE_EXPR);
863 result = (tree_int_cst_equal (val, boundary)
864 || INT_CST_LT_UNSIGNED (val, boundary));
870 result = tree_int_cst_equal (val, boundary);
871 else if (cmpc == LT_EXPR)
872 result = INT_CST_LT (val, boundary);
875 gcc_assert (cmpc == LE_EXPR);
876 result = (tree_int_cst_equal (val, boundary)
877 || INT_CST_LT (val, boundary));
887 /* Returns true if PRED is common among all the predicate
888 chains (PREDS) (and therefore can be factored out).
889 NUM_PRED_CHAIN is the size of array PREDS. */
892 find_matching_predicate_in_rest_chains (pred_info pred,
893 pred_chain_union preds,
894 size_t num_pred_chains)
899 if (num_pred_chains == 1)
902 for (i = 1; i < num_pred_chains; i++)
905 pred_chain one_chain = preds[i];
906 n = one_chain.length ();
907 for (j = 0; j < n; j++)
909 pred_info pred2 = one_chain[j];
910 /* Can relax the condition comparison to not
911 use address comparison. However, the most common
912 case is that multiple control dependent paths share
913 a common path prefix, so address comparison should
916 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
917 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
918 && pred2.invert == pred.invert)
930 /* Forward declaration. */
932 is_use_properly_guarded (gimple use_stmt,
935 unsigned uninit_opnds,
936 pointer_set_t *visited_phis);
938 /* Returns true if all uninitialized opnds are pruned. Returns false
939 otherwise. PHI is the phi node with uninitialized operands,
940 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
941 FLAG_DEF is the statement defining the flag guarding the use of the
942 PHI output, BOUNDARY_CST is the const value used in the predicate
943 associated with the flag, CMP_CODE is the comparison code used in
944 the predicate, VISITED_PHIS is the pointer set of phis visited, and
945 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
951 flag_1 = phi <0, 1> // (1)
952 var_1 = phi <undef, some_val>
956 flag_2 = phi <0, flag_1, flag_1> // (2)
957 var_2 = phi <undef, var_1, var_1>
964 Because some flag arg in (1) is not constant, if we do not look into the
965 flag phis recursively, it is conservatively treated as unknown and var_1
966 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
967 a false warning will be emitted. Checking recursively into (1), the compiler can
968 find out that only some_val (which is defined) can flow into (3) which is OK.
973 prune_uninit_phi_opnds_in_unrealizable_paths (gimple phi,
974 unsigned uninit_opnds,
977 enum tree_code cmp_code,
978 pointer_set_t *visited_phis,
979 bitmap *visited_flag_phis)
983 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
987 if (!MASK_TEST_BIT (uninit_opnds, i))
990 flag_arg = gimple_phi_arg_def (flag_def, i);
991 if (!is_gimple_constant (flag_arg))
993 gimple flag_arg_def, phi_arg_def;
995 unsigned uninit_opnds_arg_phi;
997 if (TREE_CODE (flag_arg) != SSA_NAME)
999 flag_arg_def = SSA_NAME_DEF_STMT (flag_arg);
1000 if (gimple_code (flag_arg_def) != GIMPLE_PHI)
1003 phi_arg = gimple_phi_arg_def (phi, i);
1004 if (TREE_CODE (phi_arg) != SSA_NAME)
1007 phi_arg_def = SSA_NAME_DEF_STMT (phi_arg);
1008 if (gimple_code (phi_arg_def) != GIMPLE_PHI)
1011 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1014 if (!*visited_flag_phis)
1015 *visited_flag_phis = BITMAP_ALLOC (NULL);
1017 if (bitmap_bit_p (*visited_flag_phis,
1018 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
1021 bitmap_set_bit (*visited_flag_phis,
1022 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1024 /* Now recursively prune the uninitialized phi args. */
1025 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1026 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1027 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def,
1028 boundary_cst, cmp_code, visited_phis, visited_flag_phis))
1031 bitmap_clear_bit (*visited_flag_phis,
1032 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1036 /* Now check if the constant is in the guarded range. */
1037 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1042 /* Now that we know that this undefined edge is not
1043 pruned. If the operand is defined by another phi,
1044 we can further prune the incoming edges of that
1045 phi by checking the predicates of this operands. */
1047 opnd = gimple_phi_arg_def (phi, i);
1048 opnd_def = SSA_NAME_DEF_STMT (opnd);
1049 if (gimple_code (opnd_def) == GIMPLE_PHI)
1052 unsigned uninit_opnds2
1053 = compute_uninit_opnds_pos (opnd_def);
1054 gcc_assert (!MASK_EMPTY (uninit_opnds2));
1055 opnd_edge = gimple_phi_arg_edge (phi, i);
1056 if (!is_use_properly_guarded (phi,
1071 /* A helper function that determines if the predicate set
1072 of the use is not overlapping with that of the uninit paths.
1073 The most common senario of guarded use is in Example 1:
1086 The real world examples are usually more complicated, but similar
1087 and usually result from inlining:
1089 bool init_func (int * x)
1108 Another possible use scenario is in the following trivial example:
1120 Predicate analysis needs to compute the composite predicate:
1122 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1123 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1124 (the predicate chain for phi operand defs can be computed
1125 starting from a bb that is control equivalent to the phi's
1126 bb and is dominating the operand def.)
1128 and check overlapping:
1129 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1132 This implementation provides framework that can handle
1133 scenarios. (Note that many simple cases are handled properly
1134 without the predicate analysis -- this is due to jump threading
1135 transformation which eliminates the merge point thus makes
1136 path sensitive analysis unnecessary.)
1138 NUM_PREDS is the number is the number predicate chains, PREDS is
1139 the array of chains, PHI is the phi node whose incoming (undefined)
1140 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1141 uninit operand positions. VISITED_PHIS is the pointer set of phi
1142 stmts being checked. */
1146 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1147 gimple phi, unsigned uninit_opnds,
1148 pointer_set_t *visited_phis)
1151 gimple flag_def = 0;
1152 tree boundary_cst = 0;
1153 enum tree_code cmp_code;
1154 bool swap_cond = false;
1155 bool invert = false;
1156 pred_chain the_pred_chain = vNULL;
1157 bitmap visited_flag_phis = NULL;
1158 bool all_pruned = false;
1159 size_t num_preds = preds.length ();
1161 gcc_assert (num_preds > 0);
1162 /* Find within the common prefix of multiple predicate chains
1163 a predicate that is a comparison of a flag variable against
1165 the_pred_chain = preds[0];
1166 n = the_pred_chain.length ();
1167 for (i = 0; i < n; i++)
1169 tree cond_lhs, cond_rhs, flag = 0;
1171 pred_info the_pred = the_pred_chain[i];
1173 invert = the_pred.invert;
1174 cond_lhs = the_pred.pred_lhs;
1175 cond_rhs = the_pred.pred_rhs;
1176 cmp_code = the_pred.cond_code;
1178 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1179 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1181 boundary_cst = cond_rhs;
1184 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1185 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1187 boundary_cst = cond_lhs;
1195 flag_def = SSA_NAME_DEF_STMT (flag);
1200 if ((gimple_code (flag_def) == GIMPLE_PHI)
1201 && (gimple_bb (flag_def) == gimple_bb (phi))
1202 && find_matching_predicate_in_rest_chains (the_pred, preds,
1212 /* Now check all the uninit incoming edge has a constant flag value
1213 that is in conflict with the use guard/predicate. */
1214 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1216 if (cmp_code == ERROR_MARK)
1219 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
1225 &visited_flag_phis);
1227 if (visited_flag_phis)
1228 BITMAP_FREE (visited_flag_phis);
1233 /* The helper function returns true if two predicates X1 and X2
1234 are equivalent. It assumes the expressions have already
1235 properly re-associated. */
1238 pred_equal_p (pred_info x1, pred_info x2)
1240 enum tree_code c1, c2;
1241 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1242 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1246 if (x1.invert != x2.invert)
1247 c2 = invert_tree_comparison (x2.cond_code, false);
1254 /* Returns true if the predication is testing !=. */
1257 is_neq_relop_p (pred_info pred)
1260 return (pred.cond_code == NE_EXPR && !pred.invert)
1261 || (pred.cond_code == EQ_EXPR && pred.invert);
1264 /* Returns true if pred is of the form X != 0. */
1267 is_neq_zero_form_p (pred_info pred)
1269 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1270 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1275 /* The helper function returns true if two predicates X1
1276 is equivalent to X2 != 0. */
1279 pred_expr_equal_p (pred_info x1, tree x2)
1281 if (!is_neq_zero_form_p (x1))
1284 return operand_equal_p (x1.pred_lhs, x2, 0);
1287 /* Returns true of the domain of single predicate expression
1288 EXPR1 is a subset of that of EXPR2. Returns false if it
1289 can not be proved. */
1292 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1294 enum tree_code code1, code2;
1296 if (pred_equal_p (expr1, expr2))
1299 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1300 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1303 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1306 code1 = expr1.cond_code;
1308 code1 = invert_tree_comparison (code1, false);
1309 code2 = expr2.cond_code;
1311 code2 = invert_tree_comparison (code2, false);
1313 if (code1 != code2 && code2 != NE_EXPR)
1316 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1322 /* Returns true if the domain of PRED1 is a subset
1323 of that of PRED2. Returns false if it can not be proved so. */
1326 is_pred_chain_subset_of (pred_chain pred1,
1329 size_t np1, np2, i1, i2;
1331 np1 = pred1.length ();
1332 np2 = pred2.length ();
1334 for (i2 = 0; i2 < np2; i2++)
1337 pred_info info2 = pred2[i2];
1338 for (i1 = 0; i1 < np1; i1++)
1340 pred_info info1 = pred1[i1];
1341 if (is_pred_expr_subset_of (info1, info2))
1353 /* Returns true if the domain defined by
1354 one pred chain ONE_PRED is a subset of the domain
1355 of *PREDS. It returns false if ONE_PRED's domain is
1356 not a subset of any of the sub-domains of PREDS
1357 (corresponding to each individual chains in it), even
1358 though it may be still be a subset of whole domain
1359 of PREDS which is the union (ORed) of all its subdomains.
1360 In other words, the result is conservative. */
1363 is_included_in (pred_chain one_pred, pred_chain_union preds)
1366 size_t n = preds.length ();
1368 for (i = 0; i < n; i++)
1370 if (is_pred_chain_subset_of (one_pred, preds[i]))
1377 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1378 true if the domain defined by PREDS1 is a superset
1379 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1380 PREDS2 respectively. The implementation chooses not to build
1381 generic trees (and relying on the folding capability of the
1382 compiler), but instead performs brute force comparison of
1383 individual predicate chains (won't be a compile time problem
1384 as the chains are pretty short). When the function returns
1385 false, it does not necessarily mean *PREDS1 is not a superset
1386 of *PREDS2, but mean it may not be so since the analysis can
1387 not prove it. In such cases, false warnings may still be
1391 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1394 pred_chain one_pred_chain = vNULL;
1396 n2 = preds2.length ();
1398 for (i = 0; i < n2; i++)
1400 one_pred_chain = preds2[i];
1401 if (!is_included_in (one_pred_chain, preds1))
1408 /* Returns true if TC is AND or OR. */
1411 is_and_or_or_p (enum tree_code tc, tree type)
1413 return (tc == BIT_IOR_EXPR
1414 || (tc == BIT_AND_EXPR
1415 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1418 /* Returns true if X1 is the negate of X2. */
1421 pred_neg_p (pred_info x1, pred_info x2)
1423 enum tree_code c1, c2;
1424 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1425 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1429 if (x1.invert == x2.invert)
1430 c2 = invert_tree_comparison (x2.cond_code, false);
1437 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1438 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1439 3) X OR (!X AND Y) is equivalent to (X OR Y);
1440 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1442 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1445 PREDS is the predicate chains, and N is the number of chains. */
1447 /* Helper function to implement rule 1 above. ONE_CHAIN is
1448 the AND predication to be simplified. */
1451 simplify_pred (pred_chain *one_chain)
1454 bool simplified = false;
1455 pred_chain s_chain = vNULL;
1457 n = one_chain->length ();
1459 for (i = 0; i < n; i++)
1461 pred_info *a_pred = &(*one_chain)[i];
1463 if (!a_pred->pred_lhs)
1465 if (!is_neq_zero_form_p (*a_pred))
1468 gimple def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1469 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1471 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1473 for (j = 0; j < n; j++)
1475 pred_info *b_pred = &(*one_chain)[j];
1477 if (!b_pred->pred_lhs)
1479 if (!is_neq_zero_form_p (*b_pred))
1482 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1483 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1485 /* Mark a_pred for removal. */
1486 a_pred->pred_lhs = NULL;
1487 a_pred->pred_rhs = NULL;
1498 for (i = 0; i < n; i++)
1500 pred_info *a_pred = &(*one_chain)[i];
1501 if (!a_pred->pred_lhs)
1503 s_chain.safe_push (*a_pred);
1506 one_chain->release ();
1507 *one_chain = s_chain;
1510 /* The helper function implements the rule 2 for the
1513 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1516 simplify_preds_2 (pred_chain_union *preds)
1519 bool simplified = false;
1520 pred_chain_union s_preds = vNULL;
1522 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1523 (X AND Y) OR (X AND !Y) is equivalent to X. */
1525 n = preds->length ();
1526 for (i = 0; i < n; i++)
1529 pred_chain *a_chain = &(*preds)[i];
1531 if (a_chain->length () != 2)
1537 for (j = 0; j < n; j++)
1539 pred_chain *b_chain;
1545 b_chain = &(*preds)[j];
1546 if (b_chain->length () != 2)
1552 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1555 a_chain->release ();
1556 b_chain->release ();
1557 b_chain->safe_push (x);
1561 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1564 a_chain->release ();
1565 b_chain->release ();
1566 b_chain->safe_push (y);
1572 /* Now clean up the chain. */
1575 for (i = 0; i < n; i++)
1577 if ((*preds)[i].is_empty ())
1579 s_preds.safe_push ((*preds)[i]);
1589 /* The helper function implements the rule 2 for the
1592 3) x OR (!x AND y) is equivalent to x OR y. */
1595 simplify_preds_3 (pred_chain_union *preds)
1598 bool simplified = false;
1600 /* Now iteratively simplify X OR (!X AND Z ..)
1601 into X OR (Z ...). */
1603 n = preds->length ();
1607 for (i = 0; i < n; i++)
1610 pred_chain *a_chain = &(*preds)[i];
1612 if (a_chain->length () != 1)
1617 for (j = 0; j < n; j++)
1619 pred_chain *b_chain;
1626 b_chain = &(*preds)[j];
1627 if (b_chain->length () < 2)
1630 for (k = 0; k < b_chain->length (); k++)
1633 if (pred_neg_p (x, x2))
1635 b_chain->unordered_remove (k);
1645 /* The helper function implements the rule 4 for the
1648 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1649 (x != 0 ANd y != 0). */
1652 simplify_preds_4 (pred_chain_union *preds)
1655 bool simplified = false;
1656 pred_chain_union s_preds = vNULL;
1659 n = preds->length ();
1660 for (i = 0; i < n; i++)
1663 pred_chain *a_chain = &(*preds)[i];
1665 if (a_chain->length () != 1)
1670 if (!is_neq_zero_form_p (z))
1673 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1674 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1677 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1680 for (j = 0; j < n; j++)
1682 pred_chain *b_chain;
1688 b_chain = &(*preds)[j];
1689 if (b_chain->length () != 2)
1694 if (!is_neq_zero_form_p (x2)
1695 || !is_neq_zero_form_p (y2))
1698 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1699 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1700 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1701 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1704 a_chain->release ();
1710 /* Now clean up the chain. */
1713 for (i = 0; i < n; i++)
1715 if ((*preds)[i].is_empty ())
1717 s_preds.safe_push ((*preds)[i]);
1728 /* This function simplifies predicates in PREDS. */
1731 simplify_preds (pred_chain_union *preds, gimple use_or_def, bool is_use)
1734 bool changed = false;
1736 if (dump_file && dump_flags & TDF_DETAILS)
1738 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1739 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1742 for (i = 0; i < preds->length (); i++)
1743 simplify_pred (&(*preds)[i]);
1745 n = preds->length ();
1752 if (simplify_preds_2 (preds))
1755 /* Now iteratively simplify X OR (!X AND Z ..)
1756 into X OR (Z ...). */
1757 if (simplify_preds_3 (preds))
1760 if (simplify_preds_4 (preds))
1768 /* This is a helper function which attempts to normalize predicate chains
1769 by following UD chains. It basically builds up a big tree of either IOR
1770 operations or AND operations, and convert the IOR tree into a
1771 pred_chain_union or BIT_AND tree into a pred_chain.
1781 then _t != 0 will be normalized into a pred_chain_union
1783 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1793 then _t != 0 will be normalized into a pred_chain:
1794 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1798 /* This is a helper function that stores a PRED into NORM_PREDS. */
1801 push_pred (pred_chain_union *norm_preds, pred_info pred)
1803 pred_chain pred_chain = vNULL;
1804 pred_chain.safe_push (pred);
1805 norm_preds->safe_push (pred_chain);
1808 /* A helper function that creates a predicate of the form
1809 OP != 0 and push it WORK_LIST. */
1812 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1813 pointer_set_t *mark_set)
1815 if (pointer_set_contains (mark_set, op))
1817 pointer_set_insert (mark_set, op);
1820 arg_pred.pred_lhs = op;
1821 arg_pred.pred_rhs = integer_zero_node;
1822 arg_pred.cond_code = NE_EXPR;
1823 arg_pred.invert = false;
1824 work_list->safe_push (arg_pred);
1827 /* A helper that generates a pred_info from a gimple assignment
1828 CMP_ASSIGN with comparison rhs. */
1831 get_pred_info_from_cmp (gimple cmp_assign)
1834 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
1835 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
1836 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
1837 n_pred.invert = false;
1841 /* Returns true if the PHI is a degenerated phi with
1842 all args with the same value (relop). In that case, *PRED
1843 will be updated to that value. */
1846 is_degenerated_phi (gimple phi, pred_info *pred_p)
1853 n = gimple_phi_num_args (phi);
1854 op0 = gimple_phi_arg_def (phi, 0);
1856 if (TREE_CODE (op0) != SSA_NAME)
1859 def0 = SSA_NAME_DEF_STMT (op0);
1860 if (gimple_code (def0) != GIMPLE_ASSIGN)
1862 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0))
1865 pred0 = get_pred_info_from_cmp (def0);
1867 for (i = 1; i < n; ++i)
1871 tree op = gimple_phi_arg_def (phi, i);
1873 if (TREE_CODE (op) != SSA_NAME)
1876 def = SSA_NAME_DEF_STMT (op);
1877 if (gimple_code (def) != GIMPLE_ASSIGN)
1879 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def))
1882 pred = get_pred_info_from_cmp (def);
1883 if (!pred_equal_p (pred, pred0))
1891 /* Normalize one predicate PRED
1892 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1893 2) otherwise if PRED is of the form x != 0, follow x's definition
1894 and put normalized predicates into WORK_LIST. */
1897 normalize_one_pred_1 (pred_chain_union *norm_preds,
1898 pred_chain *norm_chain,
1900 enum tree_code and_or_code,
1901 vec<pred_info, va_heap, vl_ptr> *work_list,
1902 pointer_set_t *mark_set)
1904 if (!is_neq_zero_form_p (pred))
1906 if (and_or_code == BIT_IOR_EXPR)
1907 push_pred (norm_preds, pred);
1909 norm_chain->safe_push (pred);
1913 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1915 if (gimple_code (def_stmt) == GIMPLE_PHI
1916 && is_degenerated_phi (def_stmt, &pred))
1917 work_list->safe_push (pred);
1918 else if (gimple_code (def_stmt) == GIMPLE_PHI
1919 && and_or_code == BIT_IOR_EXPR)
1922 n = gimple_phi_num_args (def_stmt);
1924 /* If we see non zero constant, we should punt. The predicate
1925 * should be one guarding the phi edge. */
1926 for (i = 0; i < n; ++i)
1928 tree op = gimple_phi_arg_def (def_stmt, i);
1929 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1931 push_pred (norm_preds, pred);
1936 for (i = 0; i < n; ++i)
1938 tree op = gimple_phi_arg_def (def_stmt, i);
1939 if (integer_zerop (op))
1942 push_to_worklist (op, work_list, mark_set);
1945 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1947 if (and_or_code == BIT_IOR_EXPR)
1948 push_pred (norm_preds, pred);
1950 norm_chain->safe_push (pred);
1952 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
1954 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
1955 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
1957 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1960 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1961 if (and_or_code == BIT_IOR_EXPR)
1962 push_pred (norm_preds, n_pred);
1964 norm_chain->safe_push (n_pred);
1968 if (and_or_code == BIT_IOR_EXPR)
1969 push_pred (norm_preds, pred);
1971 norm_chain->safe_push (pred);
1975 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1978 normalize_one_pred (pred_chain_union *norm_preds,
1981 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
1982 pointer_set_t *mark_set = NULL;
1983 enum tree_code and_or_code = ERROR_MARK;
1984 pred_chain norm_chain = vNULL;
1986 if (!is_neq_zero_form_p (pred))
1988 push_pred (norm_preds, pred);
1992 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1993 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
1994 and_or_code = gimple_assign_rhs_code (def_stmt);
1995 if (and_or_code != BIT_IOR_EXPR
1996 && and_or_code != BIT_AND_EXPR)
1998 if (TREE_CODE_CLASS (and_or_code)
2001 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2002 push_pred (norm_preds, n_pred);
2005 push_pred (norm_preds, pred);
2009 work_list.safe_push (pred);
2010 mark_set = pointer_set_create ();
2012 while (!work_list.is_empty ())
2014 pred_info a_pred = work_list.pop ();
2015 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred,
2016 and_or_code, &work_list, mark_set);
2018 if (and_or_code == BIT_AND_EXPR)
2019 norm_preds->safe_push (norm_chain);
2021 work_list.release ();
2022 pointer_set_destroy (mark_set);
2026 normalize_one_pred_chain (pred_chain_union *norm_preds,
2027 pred_chain one_chain)
2029 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2030 pointer_set_t *mark_set = pointer_set_create ();
2031 pred_chain norm_chain = vNULL;
2034 for (i = 0; i < one_chain.length (); i++)
2036 work_list.safe_push (one_chain[i]);
2037 pointer_set_insert (mark_set, one_chain[i].pred_lhs);
2040 while (!work_list.is_empty ())
2042 pred_info a_pred = work_list.pop ();
2043 normalize_one_pred_1 (0, &norm_chain, a_pred,
2044 BIT_AND_EXPR, &work_list, mark_set);
2047 norm_preds->safe_push (norm_chain);
2048 work_list.release ();
2049 pointer_set_destroy (mark_set);
2052 /* Normalize predicate chains PREDS and returns the normalized one. */
2054 static pred_chain_union
2055 normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use)
2057 pred_chain_union norm_preds = vNULL;
2058 size_t n = preds.length ();
2061 if (dump_file && dump_flags & TDF_DETAILS)
2063 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2064 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2067 for (i = 0; i < n; i++)
2069 if (preds[i].length () != 1)
2070 normalize_one_pred_chain (&norm_preds, preds[i]);
2073 normalize_one_pred (&norm_preds, preds[i][0]);
2074 preds[i].release ();
2080 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2081 dump_predicates (use_or_def, norm_preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2089 /* Computes the predicates that guard the use and checks
2090 if the incoming paths that have empty (or possibly
2091 empty) definition can be pruned/filtered. The function returns
2092 true if it can be determined that the use of PHI's def in
2093 USE_STMT is guarded with a predicate set not overlapping with
2094 predicate sets of all runtime paths that do not have a definition.
2095 Returns false if it is not or it can not be determined. USE_BB is
2096 the bb of the use (for phi operand use, the bb is not the bb of
2097 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2098 is a bit vector. If an operand of PHI is uninitialized, the
2099 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2100 set of phis being visted. */
2103 is_use_properly_guarded (gimple use_stmt,
2106 unsigned uninit_opnds,
2107 pointer_set_t *visited_phis)
2110 pred_chain_union preds = vNULL;
2111 pred_chain_union def_preds = vNULL;
2112 bool has_valid_preds = false;
2113 bool is_properly_guarded = false;
2115 if (pointer_set_insert (visited_phis, phi))
2118 phi_bb = gimple_bb (phi);
2120 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2123 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2125 if (!has_valid_preds)
2127 destroy_predicate_vecs (preds);
2131 /* Try to prune the dead incoming phi edges. */
2133 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2136 if (is_properly_guarded)
2138 destroy_predicate_vecs (preds);
2142 has_valid_preds = find_def_preds (&def_preds, phi);
2144 if (!has_valid_preds)
2146 destroy_predicate_vecs (preds);
2147 destroy_predicate_vecs (def_preds);
2151 simplify_preds (&preds, use_stmt, true);
2152 preds = normalize_preds (preds, use_stmt, true);
2154 simplify_preds (&def_preds, phi, false);
2155 def_preds = normalize_preds (def_preds, phi, false);
2157 is_properly_guarded = is_superset_of (def_preds, preds);
2159 destroy_predicate_vecs (preds);
2160 destroy_predicate_vecs (def_preds);
2161 return is_properly_guarded;
2164 /* Searches through all uses of a potentially
2165 uninitialized variable defined by PHI and returns a use
2166 statement if the use is not properly guarded. It returns
2167 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2168 holding the position(s) of uninit PHI operands. WORKLIST
2169 is the vector of candidate phis that may be updated by this
2170 function. ADDED_TO_WORKLIST is the pointer set tracking
2171 if the new phi is already in the worklist. */
2174 find_uninit_use (gimple phi, unsigned uninit_opnds,
2175 vec<gimple> *worklist,
2176 pointer_set_t *added_to_worklist)
2179 use_operand_p use_p;
2181 imm_use_iterator iter;
2183 phi_result = gimple_phi_result (phi);
2185 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2187 pointer_set_t *visited_phis;
2190 use_stmt = USE_STMT (use_p);
2191 if (is_gimple_debug (use_stmt))
2194 visited_phis = pointer_set_create ();
2196 if (gimple_code (use_stmt) == GIMPLE_PHI)
2197 use_bb = gimple_phi_arg_edge (use_stmt,
2198 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2200 use_bb = gimple_bb (use_stmt);
2202 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2205 pointer_set_destroy (visited_phis);
2208 pointer_set_destroy (visited_phis);
2210 if (dump_file && (dump_flags & TDF_DETAILS))
2212 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2213 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2215 /* Found one real use, return. */
2216 if (gimple_code (use_stmt) != GIMPLE_PHI)
2219 /* Found a phi use that is not guarded,
2220 add the phi to the worklist. */
2221 if (!pointer_set_insert (added_to_worklist, use_stmt))
2223 if (dump_file && (dump_flags & TDF_DETAILS))
2225 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2226 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2229 worklist->safe_push (use_stmt);
2230 pointer_set_insert (possibly_undefined_names, phi_result);
2237 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2238 and gives warning if there exists a runtime path from the entry to a
2239 use of the PHI def that does not contain a definition. In other words,
2240 the warning is on the real use. The more dead paths that can be pruned
2241 by the compiler, the fewer false positives the warning is. WORKLIST
2242 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2243 a pointer set tracking if the new phi is added to the worklist or not. */
2246 warn_uninitialized_phi (gimple phi, vec<gimple> *worklist,
2247 pointer_set_t *added_to_worklist)
2249 unsigned uninit_opnds;
2250 gimple uninit_use_stmt = 0;
2253 /* Don't look at virtual operands. */
2254 if (virtual_operand_p (gimple_phi_result (phi)))
2257 uninit_opnds = compute_uninit_opnds_pos (phi);
2259 if (MASK_EMPTY (uninit_opnds))
2262 if (dump_file && (dump_flags & TDF_DETAILS))
2264 fprintf (dump_file, "[CHECK]: examining phi: ");
2265 print_gimple_stmt (dump_file, phi, 0, 0);
2268 /* Now check if we have any use of the value without proper guard. */
2269 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2270 worklist, added_to_worklist);
2272 /* All uses are properly guarded. */
2273 if (!uninit_use_stmt)
2276 uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds));
2277 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2279 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2280 SSA_NAME_VAR (uninit_op),
2281 "%qD may be used uninitialized in this function",
2287 /* Entry point to the late uninitialized warning pass. */
2290 execute_late_warn_uninitialized (void)
2293 gimple_stmt_iterator gsi;
2294 vec<gimple> worklist = vNULL;
2295 pointer_set_t *added_to_worklist;
2297 calculate_dominance_info (CDI_DOMINATORS);
2298 calculate_dominance_info (CDI_POST_DOMINATORS);
2299 /* Re-do the plain uninitialized variable check, as optimization may have
2300 straightened control flow. Do this first so that we don't accidentally
2301 get a "may be" warning when we'd have seen an "is" warning later. */
2302 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2304 timevar_push (TV_TREE_UNINIT);
2306 possibly_undefined_names = pointer_set_create ();
2307 added_to_worklist = pointer_set_create ();
2309 /* Initialize worklist */
2310 FOR_EACH_BB_FN (bb, cfun)
2311 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2313 gimple phi = gsi_stmt (gsi);
2316 n = gimple_phi_num_args (phi);
2318 /* Don't look at virtual operands. */
2319 if (virtual_operand_p (gimple_phi_result (phi)))
2322 for (i = 0; i < n; ++i)
2324 tree op = gimple_phi_arg_def (phi, i);
2325 if (TREE_CODE (op) == SSA_NAME
2326 && uninit_undefined_value_p (op))
2328 worklist.safe_push (phi);
2329 pointer_set_insert (added_to_worklist, phi);
2330 if (dump_file && (dump_flags & TDF_DETAILS))
2332 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2333 print_gimple_stmt (dump_file, phi, 0, 0);
2340 while (worklist.length () != 0)
2343 cur_phi = worklist.pop ();
2344 warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
2347 worklist.release ();
2348 pointer_set_destroy (added_to_worklist);
2349 pointer_set_destroy (possibly_undefined_names);
2350 possibly_undefined_names = NULL;
2351 free_dominance_info (CDI_POST_DOMINATORS);
2352 timevar_pop (TV_TREE_UNINIT);
2357 gate_warn_uninitialized (void)
2359 return warn_uninitialized || warn_maybe_uninitialized;
2364 const pass_data pass_data_late_warn_uninitialized =
2366 GIMPLE_PASS, /* type */
2367 "uninit", /* name */
2368 OPTGROUP_NONE, /* optinfo_flags */
2369 true, /* has_gate */
2370 true, /* has_execute */
2371 TV_NONE, /* tv_id */
2372 PROP_ssa, /* properties_required */
2373 0, /* properties_provided */
2374 0, /* properties_destroyed */
2375 0, /* todo_flags_start */
2376 0, /* todo_flags_finish */
2379 class pass_late_warn_uninitialized : public gimple_opt_pass
2382 pass_late_warn_uninitialized (gcc::context *ctxt)
2383 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2386 /* opt_pass methods: */
2387 opt_pass * clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2388 bool gate () { return gate_warn_uninitialized (); }
2389 unsigned int execute () { return execute_late_warn_uninitialized (); }
2391 }; // class pass_late_warn_uninitialized
2396 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2398 return new pass_late_warn_uninitialized (ctxt);
2403 execute_early_warn_uninitialized (void)
2405 /* Currently, this pass runs always but
2406 execute_late_warn_uninitialized only runs with optimization. With
2407 optimization we want to warn about possible uninitialized as late
2408 as possible, thus don't do it here. However, without
2409 optimization we need to warn here about "may be uninitialized". */
2410 calculate_dominance_info (CDI_POST_DOMINATORS);
2412 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2414 /* Post-dominator information can not be reliably updated. Free it
2417 free_dominance_info (CDI_POST_DOMINATORS);
2424 const pass_data pass_data_early_warn_uninitialized =
2426 GIMPLE_PASS, /* type */
2427 "*early_warn_uninitialized", /* name */
2428 OPTGROUP_NONE, /* optinfo_flags */
2429 true, /* has_gate */
2430 true, /* has_execute */
2431 TV_TREE_UNINIT, /* tv_id */
2432 PROP_ssa, /* properties_required */
2433 0, /* properties_provided */
2434 0, /* properties_destroyed */
2435 0, /* todo_flags_start */
2436 0, /* todo_flags_finish */
2439 class pass_early_warn_uninitialized : public gimple_opt_pass
2442 pass_early_warn_uninitialized (gcc::context *ctxt)
2443 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2446 /* opt_pass methods: */
2447 bool gate () { return gate_warn_uninitialized (); }
2448 unsigned int execute () { return execute_early_warn_uninitialized (); }
2450 }; // class pass_early_warn_uninitialized
2455 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2457 return new pass_early_warn_uninitialized (ctxt);