PR target/47230
[official-gcc.git] / gcc / tree-ssa-uninit.c
blob64259fbcc5f92eb2f2ea5326ee758a77f5d3e7bf
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)
10 any later version.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "flags.h"
27 #include "tm_p.h"
28 #include "basic-block.h"
29 #include "function.h"
30 #include "gimple-pretty-print.h"
31 #include "bitmap.h"
32 #include "pointer-set.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
36 #include "is-a.h"
37 #include "gimple.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "tree-ssa.h"
43 #include "tree-inline.h"
44 #include "hashtab.h"
45 #include "tree-pass.h"
46 #include "diagnostic-core.h"
47 #include "params.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. */
72 static int
73 get_mask_first_set_bit (unsigned mask)
75 int pos = 0;
76 if (mask == 0)
77 return -1;
79 while ((mask & (1 << pos)) == 0)
80 pos++;
82 return pos;
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. */
87 static bool
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. */
100 static inline bool
101 uninit_undefined_value_p (tree t) {
102 if (!has_undefined_value_p (t))
103 return false;
104 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
105 return false;
106 return true;
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 DATA is the gimple stmt with info about
127 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
128 gives which argument of the phi node to take the location from. WC
129 is the warning code. */
131 static void
132 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
133 const char *gmsgid, void *data, location_t phiarg_loc)
135 gimple context = (gimple) data;
136 location_t location, cfun_loc;
137 expanded_location xloc, floc;
139 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
140 turns in a COMPLEX_EXPR with the not initialized part being
141 set to its previous (undefined) value. */
142 if (is_gimple_assign (context)
143 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
144 return;
145 if (!has_undefined_value_p (t))
146 return;
148 /* TREE_NO_WARNING either means we already warned, or the front end
149 wishes to suppress the warning. */
150 if ((context
151 && (gimple_no_warning_p (context)
152 || (gimple_assign_single_p (context)
153 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
154 || TREE_NO_WARNING (expr))
155 return;
157 if (context != NULL && gimple_has_location (context))
158 location = gimple_location (context);
159 else if (phiarg_loc != UNKNOWN_LOCATION)
160 location = phiarg_loc;
161 else
162 location = DECL_SOURCE_LOCATION (var);
163 location = linemap_resolve_location (line_table, location,
164 LRK_SPELLING_LOCATION,
165 NULL);
166 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
167 xloc = expand_location (location);
168 floc = expand_location (cfun_loc);
169 if (warning_at (location, wc, gmsgid, expr))
171 TREE_NO_WARNING (expr) = 1;
173 if (location == DECL_SOURCE_LOCATION (var))
174 return;
175 if (xloc.file != floc.file
176 || linemap_location_before_p (line_table,
177 location, cfun_loc)
178 || linemap_location_before_p (line_table,
179 cfun->function_end_locus,
180 location))
181 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
185 static unsigned int
186 warn_uninitialized_vars (bool warn_possibly_uninitialized)
188 gimple_stmt_iterator gsi;
189 basic_block bb;
191 FOR_EACH_BB_FN (bb, cfun)
193 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS,
194 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb);
195 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
197 gimple stmt = gsi_stmt (gsi);
198 use_operand_p use_p;
199 ssa_op_iter op_iter;
200 tree use;
202 if (is_gimple_debug (stmt))
203 continue;
205 /* We only do data flow with SSA_NAMEs, so that's all we
206 can warn about. */
207 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
209 use = USE_FROM_PTR (use_p);
210 if (always_executed)
211 warn_uninit (OPT_Wuninitialized, use,
212 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
213 "%qD is used uninitialized in this function",
214 stmt, UNKNOWN_LOCATION);
215 else if (warn_possibly_uninitialized)
216 warn_uninit (OPT_Wmaybe_uninitialized, use,
217 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
218 "%qD may be used uninitialized in this function",
219 stmt, UNKNOWN_LOCATION);
222 /* For memory the only cheap thing we can do is see if we
223 have a use of the default def of the virtual operand.
224 ??? Not so cheap would be to use the alias oracle via
225 walk_aliased_vdefs, if we don't find any aliasing vdef
226 warn as is-used-uninitialized, if we don't find an aliasing
227 vdef that kills our use (stmt_kills_ref_p), warn as
228 may-be-used-uninitialized. But this walk is quadratic and
229 so must be limited which means we would miss warning
230 opportunities. */
231 use = gimple_vuse (stmt);
232 if (use
233 && gimple_assign_single_p (stmt)
234 && !gimple_vdef (stmt)
235 && SSA_NAME_IS_DEFAULT_DEF (use))
237 tree rhs = gimple_assign_rhs1 (stmt);
238 tree base = get_base_address (rhs);
240 /* Do not warn if it can be initialized outside this function. */
241 if (TREE_CODE (base) != VAR_DECL
242 || DECL_HARD_REGISTER (base)
243 || is_global_var (base))
244 continue;
246 if (always_executed)
247 warn_uninit (OPT_Wuninitialized, use,
248 gimple_assign_rhs1 (stmt), base,
249 "%qE is used uninitialized in this function",
250 stmt, UNKNOWN_LOCATION);
251 else if (warn_possibly_uninitialized)
252 warn_uninit (OPT_Wmaybe_uninitialized, use,
253 gimple_assign_rhs1 (stmt), base,
254 "%qE may be used uninitialized in this function",
255 stmt, UNKNOWN_LOCATION);
260 return 0;
263 /* Checks if the operand OPND of PHI is defined by
264 another phi with one operand defined by this PHI,
265 but the rest operands are all defined. If yes,
266 returns true to skip this this operand as being
267 redundant. Can be enhanced to be more general. */
269 static bool
270 can_skip_redundant_opnd (tree opnd, gimple phi)
272 gimple op_def;
273 tree phi_def;
274 int i, n;
276 phi_def = gimple_phi_result (phi);
277 op_def = SSA_NAME_DEF_STMT (opnd);
278 if (gimple_code (op_def) != GIMPLE_PHI)
279 return false;
280 n = gimple_phi_num_args (op_def);
281 for (i = 0; i < n; ++i)
283 tree op = gimple_phi_arg_def (op_def, i);
284 if (TREE_CODE (op) != SSA_NAME)
285 continue;
286 if (op != phi_def && uninit_undefined_value_p (op))
287 return false;
290 return true;
293 /* Returns a bit mask holding the positions of arguments in PHI
294 that have empty (or possibly empty) definitions. */
296 static unsigned
297 compute_uninit_opnds_pos (gimple phi)
299 size_t i, n;
300 unsigned uninit_opnds = 0;
302 n = gimple_phi_num_args (phi);
303 /* Bail out for phi with too many args. */
304 if (n > 32)
305 return 0;
307 for (i = 0; i < n; ++i)
309 tree op = gimple_phi_arg_def (phi, i);
310 if (TREE_CODE (op) == SSA_NAME
311 && uninit_undefined_value_p (op)
312 && !can_skip_redundant_opnd (op, phi))
314 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
316 /* Ignore SSA_NAMEs that appear on abnormal edges
317 somewhere. */
318 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
319 continue;
321 MASK_SET_BIT (uninit_opnds, i);
324 return uninit_opnds;
327 /* Find the immediate postdominator PDOM of the specified
328 basic block BLOCK. */
330 static inline basic_block
331 find_pdom (basic_block block)
333 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
334 return EXIT_BLOCK_PTR_FOR_FN (cfun);
335 else
337 basic_block bb
338 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
339 if (! bb)
340 return EXIT_BLOCK_PTR_FOR_FN (cfun);
341 return bb;
345 /* Find the immediate DOM of the specified
346 basic block BLOCK. */
348 static inline basic_block
349 find_dom (basic_block block)
351 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
352 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
353 else
355 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
356 if (! bb)
357 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
358 return bb;
362 /* Returns true if BB1 is postdominating BB2 and BB1 is
363 not a loop exit bb. The loop exit bb check is simple and does
364 not cover all cases. */
366 static bool
367 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
369 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
370 return false;
372 if (single_pred_p (bb1) && !single_succ_p (bb2))
373 return false;
375 return true;
378 /* Find the closest postdominator of a specified BB, which is control
379 equivalent to BB. */
381 static inline basic_block
382 find_control_equiv_block (basic_block bb)
384 basic_block pdom;
386 pdom = find_pdom (bb);
388 /* Skip the postdominating bb that is also loop exit. */
389 if (!is_non_loop_exit_postdominating (pdom, bb))
390 return NULL;
392 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
393 return pdom;
395 return NULL;
398 #define MAX_NUM_CHAINS 8
399 #define MAX_CHAIN_LEN 5
400 #define MAX_POSTDOM_CHECK 8
402 /* Computes the control dependence chains (paths of edges)
403 for DEP_BB up to the dominating basic block BB (the head node of a
404 chain should be dominated by it). CD_CHAINS is pointer to an
405 array holding the result chains. CUR_CD_CHAIN is the current
406 chain being computed. *NUM_CHAINS is total number of chains. The
407 function returns true if the information is successfully computed,
408 return false if there is no control dependence or not computed. */
410 static bool
411 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
412 vec<edge> *cd_chains,
413 size_t *num_chains,
414 vec<edge> *cur_cd_chain,
415 int *num_calls)
417 edge_iterator ei;
418 edge e;
419 size_t i;
420 bool found_cd_chain = false;
421 size_t cur_chain_len = 0;
423 if (EDGE_COUNT (bb->succs) < 2)
424 return false;
426 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
427 return false;
428 ++*num_calls;
430 /* Could use a set instead. */
431 cur_chain_len = cur_cd_chain->length ();
432 if (cur_chain_len > MAX_CHAIN_LEN)
433 return false;
435 for (i = 0; i < cur_chain_len; i++)
437 edge e = (*cur_cd_chain)[i];
438 /* Cycle detected. */
439 if (e->src == bb)
440 return false;
443 FOR_EACH_EDGE (e, ei, bb->succs)
445 basic_block cd_bb;
446 int post_dom_check = 0;
447 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
448 continue;
450 cd_bb = e->dest;
451 cur_cd_chain->safe_push (e);
452 while (!is_non_loop_exit_postdominating (cd_bb, bb))
454 if (cd_bb == dep_bb)
456 /* Found a direct control dependence. */
457 if (*num_chains < MAX_NUM_CHAINS)
459 cd_chains[*num_chains] = cur_cd_chain->copy ();
460 (*num_chains)++;
462 found_cd_chain = true;
463 /* Check path from next edge. */
464 break;
467 /* Now check if DEP_BB is indirectly control dependent on BB. */
468 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
469 num_chains, cur_cd_chain, num_calls))
471 found_cd_chain = true;
472 break;
475 cd_bb = find_pdom (cd_bb);
476 post_dom_check++;
477 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || post_dom_check >
478 MAX_POSTDOM_CHECK)
479 break;
481 cur_cd_chain->pop ();
482 gcc_assert (cur_cd_chain->length () == cur_chain_len);
484 gcc_assert (cur_cd_chain->length () == cur_chain_len);
486 return found_cd_chain;
489 /* The type to represent a simple predicate */
491 typedef struct use_def_pred_info
493 tree pred_lhs;
494 tree pred_rhs;
495 enum tree_code cond_code;
496 bool invert;
497 } pred_info;
499 /* The type to represent a sequence of predicates grouped
500 with .AND. operation. */
502 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
504 /* The type to represent a sequence of pred_chains grouped
505 with .OR. operation. */
507 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
509 /* Converts the chains of control dependence edges into a set of
510 predicates. A control dependence chain is represented by a vector
511 edges. DEP_CHAINS points to an array of dependence chains.
512 NUM_CHAINS is the size of the chain array. One edge in a dependence
513 chain is mapped to predicate expression represented by pred_info
514 type. One dependence chain is converted to a composite predicate that
515 is the result of AND operation of pred_info mapped to each edge.
516 A composite predicate is presented by a vector of pred_info. On
517 return, *PREDS points to the resulting array of composite predicates.
518 *NUM_PREDS is the number of composite predictes. */
520 static bool
521 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
522 size_t num_chains,
523 pred_chain_union *preds)
525 bool has_valid_pred = false;
526 size_t i, j;
527 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
528 return false;
530 /* Now convert the control dep chain into a set
531 of predicates. */
532 preds->reserve (num_chains);
534 for (i = 0; i < num_chains; i++)
536 vec<edge> one_cd_chain = dep_chains[i];
538 has_valid_pred = false;
539 pred_chain t_chain = vNULL;
540 for (j = 0; j < one_cd_chain.length (); j++)
542 gimple cond_stmt;
543 gimple_stmt_iterator gsi;
544 basic_block guard_bb;
545 pred_info one_pred;
546 edge e;
548 e = one_cd_chain[j];
549 guard_bb = e->src;
550 gsi = gsi_last_bb (guard_bb);
551 if (gsi_end_p (gsi))
553 has_valid_pred = false;
554 break;
556 cond_stmt = gsi_stmt (gsi);
557 if (is_gimple_call (cond_stmt)
558 && EDGE_COUNT (e->src->succs) >= 2)
560 /* Ignore EH edge. Can add assertion
561 on the other edge's flag. */
562 continue;
564 /* Skip if there is essentially one succesor. */
565 if (EDGE_COUNT (e->src->succs) == 2)
567 edge e1;
568 edge_iterator ei1;
569 bool skip = false;
571 FOR_EACH_EDGE (e1, ei1, e->src->succs)
573 if (EDGE_COUNT (e1->dest->succs) == 0)
575 skip = true;
576 break;
579 if (skip)
580 continue;
582 if (gimple_code (cond_stmt) != GIMPLE_COND)
584 has_valid_pred = false;
585 break;
587 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
588 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
589 one_pred.cond_code = gimple_cond_code (cond_stmt);
590 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
591 t_chain.safe_push (one_pred);
592 has_valid_pred = true;
595 if (!has_valid_pred)
596 break;
597 else
598 preds->safe_push (t_chain);
600 return has_valid_pred;
603 /* Computes all control dependence chains for USE_BB. The control
604 dependence chains are then converted to an array of composite
605 predicates pointed to by PREDS. PHI_BB is the basic block of
606 the phi whose result is used in USE_BB. */
608 static bool
609 find_predicates (pred_chain_union *preds,
610 basic_block phi_bb,
611 basic_block use_bb)
613 size_t num_chains = 0, i;
614 int num_calls = 0;
615 vec<edge> dep_chains[MAX_NUM_CHAINS];
616 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
617 bool has_valid_pred = false;
618 basic_block cd_root = 0;
620 /* First find the closest bb that is control equivalent to PHI_BB
621 that also dominates USE_BB. */
622 cd_root = phi_bb;
623 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
625 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
626 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
627 cd_root = ctrl_eq_bb;
628 else
629 break;
632 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
633 &cur_chain, &num_calls);
635 has_valid_pred
636 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
637 for (i = 0; i < num_chains; i++)
638 dep_chains[i].release ();
639 return has_valid_pred;
642 /* Computes the set of incoming edges of PHI that have non empty
643 definitions of a phi chain. The collection will be done
644 recursively on operands that are defined by phis. CD_ROOT
645 is the control dependence root. *EDGES holds the result, and
646 VISITED_PHIS is a pointer set for detecting cycles. */
648 static void
649 collect_phi_def_edges (gimple phi, basic_block cd_root,
650 vec<edge> *edges,
651 pointer_set_t *visited_phis)
653 size_t i, n;
654 edge opnd_edge;
655 tree opnd;
657 if (pointer_set_insert (visited_phis, phi))
658 return;
660 n = gimple_phi_num_args (phi);
661 for (i = 0; i < n; i++)
663 opnd_edge = gimple_phi_arg_edge (phi, i);
664 opnd = gimple_phi_arg_def (phi, i);
666 if (TREE_CODE (opnd) != SSA_NAME)
668 if (dump_file && (dump_flags & TDF_DETAILS))
670 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
671 print_gimple_stmt (dump_file, phi, 0, 0);
673 edges->safe_push (opnd_edge);
675 else
677 gimple def = SSA_NAME_DEF_STMT (opnd);
679 if (gimple_code (def) == GIMPLE_PHI
680 && dominated_by_p (CDI_DOMINATORS,
681 gimple_bb (def), cd_root))
682 collect_phi_def_edges (def, cd_root, edges,
683 visited_phis);
684 else if (!uninit_undefined_value_p (opnd))
686 if (dump_file && (dump_flags & TDF_DETAILS))
688 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
689 print_gimple_stmt (dump_file, phi, 0, 0);
691 edges->safe_push (opnd_edge);
697 /* For each use edge of PHI, computes all control dependence chains.
698 The control dependence chains are then converted to an array of
699 composite predicates pointed to by PREDS. */
701 static bool
702 find_def_preds (pred_chain_union *preds, gimple phi)
704 size_t num_chains = 0, i, n;
705 vec<edge> dep_chains[MAX_NUM_CHAINS];
706 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
707 vec<edge> def_edges = vNULL;
708 bool has_valid_pred = false;
709 basic_block phi_bb, cd_root = 0;
710 pointer_set_t *visited_phis;
712 phi_bb = gimple_bb (phi);
713 /* First find the closest dominating bb to be
714 the control dependence root */
715 cd_root = find_dom (phi_bb);
716 if (!cd_root)
717 return false;
719 visited_phis = pointer_set_create ();
720 collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
721 pointer_set_destroy (visited_phis);
723 n = def_edges.length ();
724 if (n == 0)
725 return false;
727 for (i = 0; i < n; i++)
729 size_t prev_nc, j;
730 int num_calls = 0;
731 edge opnd_edge;
733 opnd_edge = def_edges[i];
734 prev_nc = num_chains;
735 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
736 &num_chains, &cur_chain, &num_calls);
738 /* Now update the newly added chains with
739 the phi operand edge: */
740 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
742 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
743 dep_chains[num_chains++] = vNULL;
744 for (j = prev_nc; j < num_chains; j++)
745 dep_chains[j].safe_push (opnd_edge);
749 has_valid_pred
750 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
751 for (i = 0; i < num_chains; i++)
752 dep_chains[i].release ();
753 return has_valid_pred;
756 /* Dumps the predicates (PREDS) for USESTMT. */
758 static void
759 dump_predicates (gimple usestmt, pred_chain_union preds,
760 const char* msg)
762 size_t i, j;
763 pred_chain one_pred_chain = vNULL;
764 fprintf (dump_file, msg);
765 print_gimple_stmt (dump_file, usestmt, 0, 0);
766 fprintf (dump_file, "is guarded by :\n\n");
767 size_t num_preds = preds.length ();
768 /* Do some dumping here: */
769 for (i = 0; i < num_preds; i++)
771 size_t np;
773 one_pred_chain = preds[i];
774 np = one_pred_chain.length ();
776 for (j = 0; j < np; j++)
778 pred_info one_pred = one_pred_chain[j];
779 if (one_pred.invert)
780 fprintf (dump_file, " (.NOT.) ");
781 print_generic_expr (dump_file, one_pred.pred_lhs, 0);
782 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
783 print_generic_expr (dump_file, one_pred.pred_rhs, 0);
784 if (j < np - 1)
785 fprintf (dump_file, " (.AND.) ");
786 else
787 fprintf (dump_file, "\n");
789 if (i < num_preds - 1)
790 fprintf (dump_file, "(.OR.)\n");
791 else
792 fprintf (dump_file, "\n\n");
796 /* Destroys the predicate set *PREDS. */
798 static void
799 destroy_predicate_vecs (pred_chain_union preds)
801 size_t i;
803 size_t n = preds.length ();
804 for (i = 0; i < n; i++)
805 preds[i].release ();
806 preds.release ();
810 /* Computes the 'normalized' conditional code with operand
811 swapping and condition inversion. */
813 static enum tree_code
814 get_cmp_code (enum tree_code orig_cmp_code,
815 bool swap_cond, bool invert)
817 enum tree_code tc = orig_cmp_code;
819 if (swap_cond)
820 tc = swap_tree_comparison (orig_cmp_code);
821 if (invert)
822 tc = invert_tree_comparison (tc, false);
824 switch (tc)
826 case LT_EXPR:
827 case LE_EXPR:
828 case GT_EXPR:
829 case GE_EXPR:
830 case EQ_EXPR:
831 case NE_EXPR:
832 break;
833 default:
834 return ERROR_MARK;
836 return tc;
839 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
840 all values in the range satisfies (x CMPC BOUNDARY) == true. */
842 static bool
843 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
845 bool inverted = false;
846 bool is_unsigned;
847 bool result;
849 /* Only handle integer constant here. */
850 if (TREE_CODE (val) != INTEGER_CST
851 || TREE_CODE (boundary) != INTEGER_CST)
852 return true;
854 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
856 if (cmpc == GE_EXPR || cmpc == GT_EXPR
857 || cmpc == NE_EXPR)
859 cmpc = invert_tree_comparison (cmpc, false);
860 inverted = true;
863 if (is_unsigned)
865 if (cmpc == EQ_EXPR)
866 result = tree_int_cst_equal (val, boundary);
867 else if (cmpc == LT_EXPR)
868 result = tree_int_cst_lt (val, boundary);
869 else
871 gcc_assert (cmpc == LE_EXPR);
872 result = tree_int_cst_le (val, boundary);
875 else
877 if (cmpc == EQ_EXPR)
878 result = tree_int_cst_equal (val, boundary);
879 else if (cmpc == LT_EXPR)
880 result = tree_int_cst_lt (val, boundary);
881 else
883 gcc_assert (cmpc == LE_EXPR);
884 result = (tree_int_cst_equal (val, boundary)
885 || tree_int_cst_lt (val, boundary));
889 if (inverted)
890 result ^= 1;
892 return result;
895 /* Returns true if PRED is common among all the predicate
896 chains (PREDS) (and therefore can be factored out).
897 NUM_PRED_CHAIN is the size of array PREDS. */
899 static bool
900 find_matching_predicate_in_rest_chains (pred_info pred,
901 pred_chain_union preds,
902 size_t num_pred_chains)
904 size_t i, j, n;
906 /* Trival case. */
907 if (num_pred_chains == 1)
908 return true;
910 for (i = 1; i < num_pred_chains; i++)
912 bool found = false;
913 pred_chain one_chain = preds[i];
914 n = one_chain.length ();
915 for (j = 0; j < n; j++)
917 pred_info pred2 = one_chain[j];
918 /* Can relax the condition comparison to not
919 use address comparison. However, the most common
920 case is that multiple control dependent paths share
921 a common path prefix, so address comparison should
922 be ok. */
924 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
925 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
926 && pred2.invert == pred.invert)
928 found = true;
929 break;
932 if (!found)
933 return false;
935 return true;
938 /* Forward declaration. */
939 static bool
940 is_use_properly_guarded (gimple use_stmt,
941 basic_block use_bb,
942 gimple phi,
943 unsigned uninit_opnds,
944 pointer_set_t *visited_phis);
946 /* Returns true if all uninitialized opnds are pruned. Returns false
947 otherwise. PHI is the phi node with uninitialized operands,
948 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
949 FLAG_DEF is the statement defining the flag guarding the use of the
950 PHI output, BOUNDARY_CST is the const value used in the predicate
951 associated with the flag, CMP_CODE is the comparison code used in
952 the predicate, VISITED_PHIS is the pointer set of phis visited, and
953 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
954 that are also phis.
956 Example scenario:
958 BB1:
959 flag_1 = phi <0, 1> // (1)
960 var_1 = phi <undef, some_val>
963 BB2:
964 flag_2 = phi <0, flag_1, flag_1> // (2)
965 var_2 = phi <undef, var_1, var_1>
966 if (flag_2 == 1)
967 goto BB3;
969 BB3:
970 use of var_2 // (3)
972 Because some flag arg in (1) is not constant, if we do not look into the
973 flag phis recursively, it is conservatively treated as unknown and var_1
974 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
975 a false warning will be emitted. Checking recursively into (1), the compiler can
976 find out that only some_val (which is defined) can flow into (3) which is OK.
980 static bool
981 prune_uninit_phi_opnds_in_unrealizable_paths (gimple phi,
982 unsigned uninit_opnds,
983 gimple flag_def,
984 tree boundary_cst,
985 enum tree_code cmp_code,
986 pointer_set_t *visited_phis,
987 bitmap *visited_flag_phis)
989 unsigned i;
991 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
993 tree flag_arg;
995 if (!MASK_TEST_BIT (uninit_opnds, i))
996 continue;
998 flag_arg = gimple_phi_arg_def (flag_def, i);
999 if (!is_gimple_constant (flag_arg))
1001 gimple flag_arg_def, phi_arg_def;
1002 tree phi_arg;
1003 unsigned uninit_opnds_arg_phi;
1005 if (TREE_CODE (flag_arg) != SSA_NAME)
1006 return false;
1007 flag_arg_def = SSA_NAME_DEF_STMT (flag_arg);
1008 if (gimple_code (flag_arg_def) != GIMPLE_PHI)
1009 return false;
1011 phi_arg = gimple_phi_arg_def (phi, i);
1012 if (TREE_CODE (phi_arg) != SSA_NAME)
1013 return false;
1015 phi_arg_def = SSA_NAME_DEF_STMT (phi_arg);
1016 if (gimple_code (phi_arg_def) != GIMPLE_PHI)
1017 return false;
1019 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1020 return false;
1022 if (!*visited_flag_phis)
1023 *visited_flag_phis = BITMAP_ALLOC (NULL);
1025 if (bitmap_bit_p (*visited_flag_phis,
1026 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
1027 return false;
1029 bitmap_set_bit (*visited_flag_phis,
1030 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1032 /* Now recursively prune the uninitialized phi args. */
1033 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1034 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1035 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def,
1036 boundary_cst, cmp_code, visited_phis, visited_flag_phis))
1037 return false;
1039 bitmap_clear_bit (*visited_flag_phis,
1040 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1041 continue;
1044 /* Now check if the constant is in the guarded range. */
1045 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1047 tree opnd;
1048 gimple opnd_def;
1050 /* Now that we know that this undefined edge is not
1051 pruned. If the operand is defined by another phi,
1052 we can further prune the incoming edges of that
1053 phi by checking the predicates of this operands. */
1055 opnd = gimple_phi_arg_def (phi, i);
1056 opnd_def = SSA_NAME_DEF_STMT (opnd);
1057 if (gimple_code (opnd_def) == GIMPLE_PHI)
1059 edge opnd_edge;
1060 unsigned uninit_opnds2
1061 = compute_uninit_opnds_pos (opnd_def);
1062 gcc_assert (!MASK_EMPTY (uninit_opnds2));
1063 opnd_edge = gimple_phi_arg_edge (phi, i);
1064 if (!is_use_properly_guarded (phi,
1065 opnd_edge->src,
1066 opnd_def,
1067 uninit_opnds2,
1068 visited_phis))
1069 return false;
1071 else
1072 return false;
1076 return true;
1079 /* A helper function that determines if the predicate set
1080 of the use is not overlapping with that of the uninit paths.
1081 The most common senario of guarded use is in Example 1:
1082 Example 1:
1083 if (some_cond)
1085 x = ...;
1086 flag = true;
1089 ... some code ...
1091 if (flag)
1092 use (x);
1094 The real world examples are usually more complicated, but similar
1095 and usually result from inlining:
1097 bool init_func (int * x)
1099 if (some_cond)
1100 return false;
1101 *x = ..
1102 return true;
1105 void foo(..)
1107 int x;
1109 if (!init_func(&x))
1110 return;
1112 .. some_code ...
1113 use (x);
1116 Another possible use scenario is in the following trivial example:
1118 Example 2:
1119 if (n > 0)
1120 x = 1;
1122 if (n > 0)
1124 if (m < 2)
1125 .. = x;
1128 Predicate analysis needs to compute the composite predicate:
1130 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1131 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1132 (the predicate chain for phi operand defs can be computed
1133 starting from a bb that is control equivalent to the phi's
1134 bb and is dominating the operand def.)
1136 and check overlapping:
1137 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1138 <==> false
1140 This implementation provides framework that can handle
1141 scenarios. (Note that many simple cases are handled properly
1142 without the predicate analysis -- this is due to jump threading
1143 transformation which eliminates the merge point thus makes
1144 path sensitive analysis unnecessary.)
1146 NUM_PREDS is the number is the number predicate chains, PREDS is
1147 the array of chains, PHI is the phi node whose incoming (undefined)
1148 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1149 uninit operand positions. VISITED_PHIS is the pointer set of phi
1150 stmts being checked. */
1153 static bool
1154 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1155 gimple phi, unsigned uninit_opnds,
1156 pointer_set_t *visited_phis)
1158 unsigned int i, n;
1159 gimple flag_def = 0;
1160 tree boundary_cst = 0;
1161 enum tree_code cmp_code;
1162 bool swap_cond = false;
1163 bool invert = false;
1164 pred_chain the_pred_chain = vNULL;
1165 bitmap visited_flag_phis = NULL;
1166 bool all_pruned = false;
1167 size_t num_preds = preds.length ();
1169 gcc_assert (num_preds > 0);
1170 /* Find within the common prefix of multiple predicate chains
1171 a predicate that is a comparison of a flag variable against
1172 a constant. */
1173 the_pred_chain = preds[0];
1174 n = the_pred_chain.length ();
1175 for (i = 0; i < n; i++)
1177 tree cond_lhs, cond_rhs, flag = 0;
1179 pred_info the_pred = the_pred_chain[i];
1181 invert = the_pred.invert;
1182 cond_lhs = the_pred.pred_lhs;
1183 cond_rhs = the_pred.pred_rhs;
1184 cmp_code = the_pred.cond_code;
1186 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1187 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1189 boundary_cst = cond_rhs;
1190 flag = cond_lhs;
1192 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1193 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1195 boundary_cst = cond_lhs;
1196 flag = cond_rhs;
1197 swap_cond = true;
1200 if (!flag)
1201 continue;
1203 flag_def = SSA_NAME_DEF_STMT (flag);
1205 if (!flag_def)
1206 continue;
1208 if ((gimple_code (flag_def) == GIMPLE_PHI)
1209 && (gimple_bb (flag_def) == gimple_bb (phi))
1210 && find_matching_predicate_in_rest_chains (the_pred, preds,
1211 num_preds))
1212 break;
1214 flag_def = 0;
1217 if (!flag_def)
1218 return false;
1220 /* Now check all the uninit incoming edge has a constant flag value
1221 that is in conflict with the use guard/predicate. */
1222 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1224 if (cmp_code == ERROR_MARK)
1225 return false;
1227 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
1228 uninit_opnds,
1229 flag_def,
1230 boundary_cst,
1231 cmp_code,
1232 visited_phis,
1233 &visited_flag_phis);
1235 if (visited_flag_phis)
1236 BITMAP_FREE (visited_flag_phis);
1238 return all_pruned;
1241 /* The helper function returns true if two predicates X1 and X2
1242 are equivalent. It assumes the expressions have already
1243 properly re-associated. */
1245 static inline bool
1246 pred_equal_p (pred_info x1, pred_info x2)
1248 enum tree_code c1, c2;
1249 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1250 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1251 return false;
1253 c1 = x1.cond_code;
1254 if (x1.invert != x2.invert)
1255 c2 = invert_tree_comparison (x2.cond_code, false);
1256 else
1257 c2 = x2.cond_code;
1259 return c1 == c2;
1262 /* Returns true if the predication is testing !=. */
1264 static inline bool
1265 is_neq_relop_p (pred_info pred)
1268 return (pred.cond_code == NE_EXPR && !pred.invert)
1269 || (pred.cond_code == EQ_EXPR && pred.invert);
1272 /* Returns true if pred is of the form X != 0. */
1274 static inline bool
1275 is_neq_zero_form_p (pred_info pred)
1277 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1278 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1279 return false;
1280 return true;
1283 /* The helper function returns true if two predicates X1
1284 is equivalent to X2 != 0. */
1286 static inline bool
1287 pred_expr_equal_p (pred_info x1, tree x2)
1289 if (!is_neq_zero_form_p (x1))
1290 return false;
1292 return operand_equal_p (x1.pred_lhs, x2, 0);
1295 /* Returns true of the domain of single predicate expression
1296 EXPR1 is a subset of that of EXPR2. Returns false if it
1297 can not be proved. */
1299 static bool
1300 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1302 enum tree_code code1, code2;
1304 if (pred_equal_p (expr1, expr2))
1305 return true;
1307 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1308 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1309 return false;
1311 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1312 return false;
1314 code1 = expr1.cond_code;
1315 if (expr1.invert)
1316 code1 = invert_tree_comparison (code1, false);
1317 code2 = expr2.cond_code;
1318 if (expr2.invert)
1319 code2 = invert_tree_comparison (code2, false);
1321 if (code1 != code2 && code2 != NE_EXPR)
1322 return false;
1324 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1325 return true;
1327 return false;
1330 /* Returns true if the domain of PRED1 is a subset
1331 of that of PRED2. Returns false if it can not be proved so. */
1333 static bool
1334 is_pred_chain_subset_of (pred_chain pred1,
1335 pred_chain pred2)
1337 size_t np1, np2, i1, i2;
1339 np1 = pred1.length ();
1340 np2 = pred2.length ();
1342 for (i2 = 0; i2 < np2; i2++)
1344 bool found = false;
1345 pred_info info2 = pred2[i2];
1346 for (i1 = 0; i1 < np1; i1++)
1348 pred_info info1 = pred1[i1];
1349 if (is_pred_expr_subset_of (info1, info2))
1351 found = true;
1352 break;
1355 if (!found)
1356 return false;
1358 return true;
1361 /* Returns true if the domain defined by
1362 one pred chain ONE_PRED is a subset of the domain
1363 of *PREDS. It returns false if ONE_PRED's domain is
1364 not a subset of any of the sub-domains of PREDS
1365 (corresponding to each individual chains in it), even
1366 though it may be still be a subset of whole domain
1367 of PREDS which is the union (ORed) of all its subdomains.
1368 In other words, the result is conservative. */
1370 static bool
1371 is_included_in (pred_chain one_pred, pred_chain_union preds)
1373 size_t i;
1374 size_t n = preds.length ();
1376 for (i = 0; i < n; i++)
1378 if (is_pred_chain_subset_of (one_pred, preds[i]))
1379 return true;
1382 return false;
1385 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1386 true if the domain defined by PREDS1 is a superset
1387 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1388 PREDS2 respectively. The implementation chooses not to build
1389 generic trees (and relying on the folding capability of the
1390 compiler), but instead performs brute force comparison of
1391 individual predicate chains (won't be a compile time problem
1392 as the chains are pretty short). When the function returns
1393 false, it does not necessarily mean *PREDS1 is not a superset
1394 of *PREDS2, but mean it may not be so since the analysis can
1395 not prove it. In such cases, false warnings may still be
1396 emitted. */
1398 static bool
1399 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1401 size_t i, n2;
1402 pred_chain one_pred_chain = vNULL;
1404 n2 = preds2.length ();
1406 for (i = 0; i < n2; i++)
1408 one_pred_chain = preds2[i];
1409 if (!is_included_in (one_pred_chain, preds1))
1410 return false;
1413 return true;
1416 /* Returns true if TC is AND or OR. */
1418 static inline bool
1419 is_and_or_or_p (enum tree_code tc, tree type)
1421 return (tc == BIT_IOR_EXPR
1422 || (tc == BIT_AND_EXPR
1423 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1426 /* Returns true if X1 is the negate of X2. */
1428 static inline bool
1429 pred_neg_p (pred_info x1, pred_info x2)
1431 enum tree_code c1, c2;
1432 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1433 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1434 return false;
1436 c1 = x1.cond_code;
1437 if (x1.invert == x2.invert)
1438 c2 = invert_tree_comparison (x2.cond_code, false);
1439 else
1440 c2 = x2.cond_code;
1442 return c1 == c2;
1445 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1446 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1447 3) X OR (!X AND Y) is equivalent to (X OR Y);
1448 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1449 (x != 0 AND y != 0)
1450 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1451 (X AND Y) OR Z
1453 PREDS is the predicate chains, and N is the number of chains. */
1455 /* Helper function to implement rule 1 above. ONE_CHAIN is
1456 the AND predication to be simplified. */
1458 static void
1459 simplify_pred (pred_chain *one_chain)
1461 size_t i, j, n;
1462 bool simplified = false;
1463 pred_chain s_chain = vNULL;
1465 n = one_chain->length ();
1467 for (i = 0; i < n; i++)
1469 pred_info *a_pred = &(*one_chain)[i];
1471 if (!a_pred->pred_lhs)
1472 continue;
1473 if (!is_neq_zero_form_p (*a_pred))
1474 continue;
1476 gimple def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1477 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1478 continue;
1479 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1481 for (j = 0; j < n; j++)
1483 pred_info *b_pred = &(*one_chain)[j];
1485 if (!b_pred->pred_lhs)
1486 continue;
1487 if (!is_neq_zero_form_p (*b_pred))
1488 continue;
1490 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1491 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1493 /* Mark a_pred for removal. */
1494 a_pred->pred_lhs = NULL;
1495 a_pred->pred_rhs = NULL;
1496 simplified = true;
1497 break;
1503 if (!simplified)
1504 return;
1506 for (i = 0; i < n; i++)
1508 pred_info *a_pred = &(*one_chain)[i];
1509 if (!a_pred->pred_lhs)
1510 continue;
1511 s_chain.safe_push (*a_pred);
1514 one_chain->release ();
1515 *one_chain = s_chain;
1518 /* The helper function implements the rule 2 for the
1519 OR predicate PREDS.
1521 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1523 static bool
1524 simplify_preds_2 (pred_chain_union *preds)
1526 size_t i, j, n;
1527 bool simplified = false;
1528 pred_chain_union s_preds = vNULL;
1530 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1531 (X AND Y) OR (X AND !Y) is equivalent to X. */
1533 n = preds->length ();
1534 for (i = 0; i < n; i++)
1536 pred_info x, y;
1537 pred_chain *a_chain = &(*preds)[i];
1539 if (a_chain->length () != 2)
1540 continue;
1542 x = (*a_chain)[0];
1543 y = (*a_chain)[1];
1545 for (j = 0; j < n; j++)
1547 pred_chain *b_chain;
1548 pred_info x2, y2;
1550 if (j == i)
1551 continue;
1553 b_chain = &(*preds)[j];
1554 if (b_chain->length () != 2)
1555 continue;
1557 x2 = (*b_chain)[0];
1558 y2 = (*b_chain)[1];
1560 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1562 /* Kill a_chain. */
1563 a_chain->release ();
1564 b_chain->release ();
1565 b_chain->safe_push (x);
1566 simplified = true;
1567 break;
1569 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1571 /* Kill a_chain. */
1572 a_chain->release ();
1573 b_chain->release ();
1574 b_chain->safe_push (y);
1575 simplified = true;
1576 break;
1580 /* Now clean up the chain. */
1581 if (simplified)
1583 for (i = 0; i < n; i++)
1585 if ((*preds)[i].is_empty ())
1586 continue;
1587 s_preds.safe_push ((*preds)[i]);
1589 preds->release ();
1590 (*preds) = s_preds;
1591 s_preds = vNULL;
1594 return simplified;
1597 /* The helper function implements the rule 2 for the
1598 OR predicate PREDS.
1600 3) x OR (!x AND y) is equivalent to x OR y. */
1602 static bool
1603 simplify_preds_3 (pred_chain_union *preds)
1605 size_t i, j, n;
1606 bool simplified = false;
1608 /* Now iteratively simplify X OR (!X AND Z ..)
1609 into X OR (Z ...). */
1611 n = preds->length ();
1612 if (n < 2)
1613 return false;
1615 for (i = 0; i < n; i++)
1617 pred_info x;
1618 pred_chain *a_chain = &(*preds)[i];
1620 if (a_chain->length () != 1)
1621 continue;
1623 x = (*a_chain)[0];
1625 for (j = 0; j < n; j++)
1627 pred_chain *b_chain;
1628 pred_info x2;
1629 size_t k;
1631 if (j == i)
1632 continue;
1634 b_chain = &(*preds)[j];
1635 if (b_chain->length () < 2)
1636 continue;
1638 for (k = 0; k < b_chain->length (); k++)
1640 x2 = (*b_chain)[k];
1641 if (pred_neg_p (x, x2))
1643 b_chain->unordered_remove (k);
1644 simplified = true;
1645 break;
1650 return simplified;
1653 /* The helper function implements the rule 4 for the
1654 OR predicate PREDS.
1656 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1657 (x != 0 ANd y != 0). */
1659 static bool
1660 simplify_preds_4 (pred_chain_union *preds)
1662 size_t i, j, n;
1663 bool simplified = false;
1664 pred_chain_union s_preds = vNULL;
1665 gimple def_stmt;
1667 n = preds->length ();
1668 for (i = 0; i < n; i++)
1670 pred_info z;
1671 pred_chain *a_chain = &(*preds)[i];
1673 if (a_chain->length () != 1)
1674 continue;
1676 z = (*a_chain)[0];
1678 if (!is_neq_zero_form_p (z))
1679 continue;
1681 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1682 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1683 continue;
1685 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1686 continue;
1688 for (j = 0; j < n; j++)
1690 pred_chain *b_chain;
1691 pred_info x2, y2;
1693 if (j == i)
1694 continue;
1696 b_chain = &(*preds)[j];
1697 if (b_chain->length () != 2)
1698 continue;
1700 x2 = (*b_chain)[0];
1701 y2 = (*b_chain)[1];
1702 if (!is_neq_zero_form_p (x2)
1703 || !is_neq_zero_form_p (y2))
1704 continue;
1706 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1707 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1708 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1709 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1711 /* Kill a_chain. */
1712 a_chain->release ();
1713 simplified = true;
1714 break;
1718 /* Now clean up the chain. */
1719 if (simplified)
1721 for (i = 0; i < n; i++)
1723 if ((*preds)[i].is_empty ())
1724 continue;
1725 s_preds.safe_push ((*preds)[i]);
1727 preds->release ();
1728 (*preds) = s_preds;
1729 s_preds = vNULL;
1732 return simplified;
1736 /* This function simplifies predicates in PREDS. */
1738 static void
1739 simplify_preds (pred_chain_union *preds, gimple use_or_def, bool is_use)
1741 size_t i, n;
1742 bool changed = false;
1744 if (dump_file && dump_flags & TDF_DETAILS)
1746 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1747 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1750 for (i = 0; i < preds->length (); i++)
1751 simplify_pred (&(*preds)[i]);
1753 n = preds->length ();
1754 if (n < 2)
1755 return;
1759 changed = false;
1760 if (simplify_preds_2 (preds))
1761 changed = true;
1763 /* Now iteratively simplify X OR (!X AND Z ..)
1764 into X OR (Z ...). */
1765 if (simplify_preds_3 (preds))
1766 changed = true;
1768 if (simplify_preds_4 (preds))
1769 changed = true;
1771 } while (changed);
1773 return;
1776 /* This is a helper function which attempts to normalize predicate chains
1777 by following UD chains. It basically builds up a big tree of either IOR
1778 operations or AND operations, and convert the IOR tree into a
1779 pred_chain_union or BIT_AND tree into a pred_chain.
1780 Example:
1782 _3 = _2 RELOP1 _1;
1783 _6 = _5 RELOP2 _4;
1784 _9 = _8 RELOP3 _7;
1785 _10 = _3 | _6;
1786 _12 = _9 | _0;
1787 _t = _10 | _12;
1789 then _t != 0 will be normalized into a pred_chain_union
1791 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1793 Similarly given,
1795 _3 = _2 RELOP1 _1;
1796 _6 = _5 RELOP2 _4;
1797 _9 = _8 RELOP3 _7;
1798 _10 = _3 & _6;
1799 _12 = _9 & _0;
1801 then _t != 0 will be normalized into a pred_chain:
1802 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1806 /* This is a helper function that stores a PRED into NORM_PREDS. */
1808 inline static void
1809 push_pred (pred_chain_union *norm_preds, pred_info pred)
1811 pred_chain pred_chain = vNULL;
1812 pred_chain.safe_push (pred);
1813 norm_preds->safe_push (pred_chain);
1816 /* A helper function that creates a predicate of the form
1817 OP != 0 and push it WORK_LIST. */
1819 inline static void
1820 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1821 pointer_set_t *mark_set)
1823 if (pointer_set_contains (mark_set, op))
1824 return;
1825 pointer_set_insert (mark_set, op);
1827 pred_info arg_pred;
1828 arg_pred.pred_lhs = op;
1829 arg_pred.pred_rhs = integer_zero_node;
1830 arg_pred.cond_code = NE_EXPR;
1831 arg_pred.invert = false;
1832 work_list->safe_push (arg_pred);
1835 /* A helper that generates a pred_info from a gimple assignment
1836 CMP_ASSIGN with comparison rhs. */
1838 static pred_info
1839 get_pred_info_from_cmp (gimple cmp_assign)
1841 pred_info n_pred;
1842 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
1843 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
1844 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
1845 n_pred.invert = false;
1846 return n_pred;
1849 /* Returns true if the PHI is a degenerated phi with
1850 all args with the same value (relop). In that case, *PRED
1851 will be updated to that value. */
1853 static bool
1854 is_degenerated_phi (gimple phi, pred_info *pred_p)
1856 int i, n;
1857 tree op0;
1858 gimple def0;
1859 pred_info pred0;
1861 n = gimple_phi_num_args (phi);
1862 op0 = gimple_phi_arg_def (phi, 0);
1864 if (TREE_CODE (op0) != SSA_NAME)
1865 return false;
1867 def0 = SSA_NAME_DEF_STMT (op0);
1868 if (gimple_code (def0) != GIMPLE_ASSIGN)
1869 return false;
1870 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0))
1871 != tcc_comparison)
1872 return false;
1873 pred0 = get_pred_info_from_cmp (def0);
1875 for (i = 1; i < n; ++i)
1877 gimple def;
1878 pred_info pred;
1879 tree op = gimple_phi_arg_def (phi, i);
1881 if (TREE_CODE (op) != SSA_NAME)
1882 return false;
1884 def = SSA_NAME_DEF_STMT (op);
1885 if (gimple_code (def) != GIMPLE_ASSIGN)
1886 return false;
1887 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def))
1888 != tcc_comparison)
1889 return false;
1890 pred = get_pred_info_from_cmp (def);
1891 if (!pred_equal_p (pred, pred0))
1892 return false;
1895 *pred_p = pred0;
1896 return true;
1899 /* Normalize one predicate PRED
1900 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1901 2) otherwise if PRED is of the form x != 0, follow x's definition
1902 and put normalized predicates into WORK_LIST. */
1904 static void
1905 normalize_one_pred_1 (pred_chain_union *norm_preds,
1906 pred_chain *norm_chain,
1907 pred_info pred,
1908 enum tree_code and_or_code,
1909 vec<pred_info, va_heap, vl_ptr> *work_list,
1910 pointer_set_t *mark_set)
1912 if (!is_neq_zero_form_p (pred))
1914 if (and_or_code == BIT_IOR_EXPR)
1915 push_pred (norm_preds, pred);
1916 else
1917 norm_chain->safe_push (pred);
1918 return;
1921 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1923 if (gimple_code (def_stmt) == GIMPLE_PHI
1924 && is_degenerated_phi (def_stmt, &pred))
1925 work_list->safe_push (pred);
1926 else if (gimple_code (def_stmt) == GIMPLE_PHI
1927 && and_or_code == BIT_IOR_EXPR)
1929 int i, n;
1930 n = gimple_phi_num_args (def_stmt);
1932 /* If we see non zero constant, we should punt. The predicate
1933 * should be one guarding the phi edge. */
1934 for (i = 0; i < n; ++i)
1936 tree op = gimple_phi_arg_def (def_stmt, i);
1937 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1939 push_pred (norm_preds, pred);
1940 return;
1944 for (i = 0; i < n; ++i)
1946 tree op = gimple_phi_arg_def (def_stmt, i);
1947 if (integer_zerop (op))
1948 continue;
1950 push_to_worklist (op, work_list, mark_set);
1953 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1955 if (and_or_code == BIT_IOR_EXPR)
1956 push_pred (norm_preds, pred);
1957 else
1958 norm_chain->safe_push (pred);
1960 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
1962 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
1963 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
1965 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1966 == tcc_comparison)
1968 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1969 if (and_or_code == BIT_IOR_EXPR)
1970 push_pred (norm_preds, n_pred);
1971 else
1972 norm_chain->safe_push (n_pred);
1974 else
1976 if (and_or_code == BIT_IOR_EXPR)
1977 push_pred (norm_preds, pred);
1978 else
1979 norm_chain->safe_push (pred);
1983 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1985 static void
1986 normalize_one_pred (pred_chain_union *norm_preds,
1987 pred_info pred)
1989 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
1990 pointer_set_t *mark_set = NULL;
1991 enum tree_code and_or_code = ERROR_MARK;
1992 pred_chain norm_chain = vNULL;
1994 if (!is_neq_zero_form_p (pred))
1996 push_pred (norm_preds, pred);
1997 return;
2000 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2001 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2002 and_or_code = gimple_assign_rhs_code (def_stmt);
2003 if (and_or_code != BIT_IOR_EXPR
2004 && and_or_code != BIT_AND_EXPR)
2006 if (TREE_CODE_CLASS (and_or_code)
2007 == tcc_comparison)
2009 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2010 push_pred (norm_preds, n_pred);
2012 else
2013 push_pred (norm_preds, pred);
2014 return;
2017 work_list.safe_push (pred);
2018 mark_set = pointer_set_create ();
2020 while (!work_list.is_empty ())
2022 pred_info a_pred = work_list.pop ();
2023 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred,
2024 and_or_code, &work_list, mark_set);
2026 if (and_or_code == BIT_AND_EXPR)
2027 norm_preds->safe_push (norm_chain);
2029 work_list.release ();
2030 pointer_set_destroy (mark_set);
2033 static void
2034 normalize_one_pred_chain (pred_chain_union *norm_preds,
2035 pred_chain one_chain)
2037 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2038 pointer_set_t *mark_set = pointer_set_create ();
2039 pred_chain norm_chain = vNULL;
2040 size_t i;
2042 for (i = 0; i < one_chain.length (); i++)
2044 work_list.safe_push (one_chain[i]);
2045 pointer_set_insert (mark_set, one_chain[i].pred_lhs);
2048 while (!work_list.is_empty ())
2050 pred_info a_pred = work_list.pop ();
2051 normalize_one_pred_1 (0, &norm_chain, a_pred,
2052 BIT_AND_EXPR, &work_list, mark_set);
2055 norm_preds->safe_push (norm_chain);
2056 work_list.release ();
2057 pointer_set_destroy (mark_set);
2060 /* Normalize predicate chains PREDS and returns the normalized one. */
2062 static pred_chain_union
2063 normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use)
2065 pred_chain_union norm_preds = vNULL;
2066 size_t n = preds.length ();
2067 size_t i;
2069 if (dump_file && dump_flags & TDF_DETAILS)
2071 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2072 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2075 for (i = 0; i < n; i++)
2077 if (preds[i].length () != 1)
2078 normalize_one_pred_chain (&norm_preds, preds[i]);
2079 else
2081 normalize_one_pred (&norm_preds, preds[i][0]);
2082 preds[i].release ();
2086 if (dump_file)
2088 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2089 dump_predicates (use_or_def, norm_preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2092 preds.release ();
2093 return norm_preds;
2097 /* Computes the predicates that guard the use and checks
2098 if the incoming paths that have empty (or possibly
2099 empty) definition can be pruned/filtered. The function returns
2100 true if it can be determined that the use of PHI's def in
2101 USE_STMT is guarded with a predicate set not overlapping with
2102 predicate sets of all runtime paths that do not have a definition.
2103 Returns false if it is not or it can not be determined. USE_BB is
2104 the bb of the use (for phi operand use, the bb is not the bb of
2105 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2106 is a bit vector. If an operand of PHI is uninitialized, the
2107 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2108 set of phis being visted. */
2110 static bool
2111 is_use_properly_guarded (gimple use_stmt,
2112 basic_block use_bb,
2113 gimple phi,
2114 unsigned uninit_opnds,
2115 pointer_set_t *visited_phis)
2117 basic_block phi_bb;
2118 pred_chain_union preds = vNULL;
2119 pred_chain_union def_preds = vNULL;
2120 bool has_valid_preds = false;
2121 bool is_properly_guarded = false;
2123 if (pointer_set_insert (visited_phis, phi))
2124 return false;
2126 phi_bb = gimple_bb (phi);
2128 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2129 return false;
2131 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2133 if (!has_valid_preds)
2135 destroy_predicate_vecs (preds);
2136 return false;
2139 /* Try to prune the dead incoming phi edges. */
2140 is_properly_guarded
2141 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2142 visited_phis);
2144 if (is_properly_guarded)
2146 destroy_predicate_vecs (preds);
2147 return true;
2150 has_valid_preds = find_def_preds (&def_preds, phi);
2152 if (!has_valid_preds)
2154 destroy_predicate_vecs (preds);
2155 destroy_predicate_vecs (def_preds);
2156 return false;
2159 simplify_preds (&preds, use_stmt, true);
2160 preds = normalize_preds (preds, use_stmt, true);
2162 simplify_preds (&def_preds, phi, false);
2163 def_preds = normalize_preds (def_preds, phi, false);
2165 is_properly_guarded = is_superset_of (def_preds, preds);
2167 destroy_predicate_vecs (preds);
2168 destroy_predicate_vecs (def_preds);
2169 return is_properly_guarded;
2172 /* Searches through all uses of a potentially
2173 uninitialized variable defined by PHI and returns a use
2174 statement if the use is not properly guarded. It returns
2175 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2176 holding the position(s) of uninit PHI operands. WORKLIST
2177 is the vector of candidate phis that may be updated by this
2178 function. ADDED_TO_WORKLIST is the pointer set tracking
2179 if the new phi is already in the worklist. */
2181 static gimple
2182 find_uninit_use (gimple phi, unsigned uninit_opnds,
2183 vec<gimple> *worklist,
2184 pointer_set_t *added_to_worklist)
2186 tree phi_result;
2187 use_operand_p use_p;
2188 gimple use_stmt;
2189 imm_use_iterator iter;
2191 phi_result = gimple_phi_result (phi);
2193 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2195 pointer_set_t *visited_phis;
2196 basic_block use_bb;
2198 use_stmt = USE_STMT (use_p);
2199 if (is_gimple_debug (use_stmt))
2200 continue;
2202 visited_phis = pointer_set_create ();
2204 if (gimple_code (use_stmt) == GIMPLE_PHI)
2205 use_bb = gimple_phi_arg_edge (use_stmt,
2206 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2207 else
2208 use_bb = gimple_bb (use_stmt);
2210 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2211 visited_phis))
2213 pointer_set_destroy (visited_phis);
2214 continue;
2216 pointer_set_destroy (visited_phis);
2218 if (dump_file && (dump_flags & TDF_DETAILS))
2220 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2221 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2223 /* Found one real use, return. */
2224 if (gimple_code (use_stmt) != GIMPLE_PHI)
2225 return use_stmt;
2227 /* Found a phi use that is not guarded,
2228 add the phi to the worklist. */
2229 if (!pointer_set_insert (added_to_worklist, use_stmt))
2231 if (dump_file && (dump_flags & TDF_DETAILS))
2233 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2234 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2237 worklist->safe_push (use_stmt);
2238 pointer_set_insert (possibly_undefined_names, phi_result);
2242 return NULL;
2245 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2246 and gives warning if there exists a runtime path from the entry to a
2247 use of the PHI def that does not contain a definition. In other words,
2248 the warning is on the real use. The more dead paths that can be pruned
2249 by the compiler, the fewer false positives the warning is. WORKLIST
2250 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2251 a pointer set tracking if the new phi is added to the worklist or not. */
2253 static void
2254 warn_uninitialized_phi (gimple phi, vec<gimple> *worklist,
2255 pointer_set_t *added_to_worklist)
2257 unsigned uninit_opnds;
2258 gimple uninit_use_stmt = 0;
2259 tree uninit_op;
2260 int phiarg_index;
2261 location_t loc;
2263 /* Don't look at virtual operands. */
2264 if (virtual_operand_p (gimple_phi_result (phi)))
2265 return;
2267 uninit_opnds = compute_uninit_opnds_pos (phi);
2269 if (MASK_EMPTY (uninit_opnds))
2270 return;
2272 if (dump_file && (dump_flags & TDF_DETAILS))
2274 fprintf (dump_file, "[CHECK]: examining phi: ");
2275 print_gimple_stmt (dump_file, phi, 0, 0);
2278 /* Now check if we have any use of the value without proper guard. */
2279 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2280 worklist, added_to_worklist);
2282 /* All uses are properly guarded. */
2283 if (!uninit_use_stmt)
2284 return;
2286 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2287 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2288 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2289 return;
2290 if (gimple_phi_arg_has_location (phi, phiarg_index))
2291 loc = gimple_phi_arg_location (phi, phiarg_index);
2292 else
2293 loc = UNKNOWN_LOCATION;
2294 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2295 SSA_NAME_VAR (uninit_op),
2296 "%qD may be used uninitialized in this function",
2297 uninit_use_stmt, loc);
2301 static bool
2302 gate_warn_uninitialized (void)
2304 return warn_uninitialized || warn_maybe_uninitialized;
2307 namespace {
2309 const pass_data pass_data_late_warn_uninitialized =
2311 GIMPLE_PASS, /* type */
2312 "uninit", /* name */
2313 OPTGROUP_NONE, /* optinfo_flags */
2314 TV_NONE, /* tv_id */
2315 PROP_ssa, /* properties_required */
2316 0, /* properties_provided */
2317 0, /* properties_destroyed */
2318 0, /* todo_flags_start */
2319 0, /* todo_flags_finish */
2322 class pass_late_warn_uninitialized : public gimple_opt_pass
2324 public:
2325 pass_late_warn_uninitialized (gcc::context *ctxt)
2326 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2329 /* opt_pass methods: */
2330 opt_pass * clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2331 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2332 virtual unsigned int execute (function *);
2334 }; // class pass_late_warn_uninitialized
2336 unsigned int
2337 pass_late_warn_uninitialized::execute (function *fun)
2339 basic_block bb;
2340 gimple_stmt_iterator gsi;
2341 vec<gimple> worklist = vNULL;
2342 pointer_set_t *added_to_worklist;
2344 calculate_dominance_info (CDI_DOMINATORS);
2345 calculate_dominance_info (CDI_POST_DOMINATORS);
2346 /* Re-do the plain uninitialized variable check, as optimization may have
2347 straightened control flow. Do this first so that we don't accidentally
2348 get a "may be" warning when we'd have seen an "is" warning later. */
2349 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2351 timevar_push (TV_TREE_UNINIT);
2353 possibly_undefined_names = pointer_set_create ();
2354 added_to_worklist = pointer_set_create ();
2356 /* Initialize worklist */
2357 FOR_EACH_BB_FN (bb, fun)
2358 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2360 gimple phi = gsi_stmt (gsi);
2361 size_t n, i;
2363 n = gimple_phi_num_args (phi);
2365 /* Don't look at virtual operands. */
2366 if (virtual_operand_p (gimple_phi_result (phi)))
2367 continue;
2369 for (i = 0; i < n; ++i)
2371 tree op = gimple_phi_arg_def (phi, i);
2372 if (TREE_CODE (op) == SSA_NAME
2373 && uninit_undefined_value_p (op))
2375 worklist.safe_push (phi);
2376 pointer_set_insert (added_to_worklist, phi);
2377 if (dump_file && (dump_flags & TDF_DETAILS))
2379 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2380 print_gimple_stmt (dump_file, phi, 0, 0);
2382 break;
2387 while (worklist.length () != 0)
2389 gimple cur_phi = 0;
2390 cur_phi = worklist.pop ();
2391 warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
2394 worklist.release ();
2395 pointer_set_destroy (added_to_worklist);
2396 pointer_set_destroy (possibly_undefined_names);
2397 possibly_undefined_names = NULL;
2398 free_dominance_info (CDI_POST_DOMINATORS);
2399 timevar_pop (TV_TREE_UNINIT);
2400 return 0;
2403 } // anon namespace
2405 gimple_opt_pass *
2406 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2408 return new pass_late_warn_uninitialized (ctxt);
2412 static unsigned int
2413 execute_early_warn_uninitialized (void)
2415 /* Currently, this pass runs always but
2416 execute_late_warn_uninitialized only runs with optimization. With
2417 optimization we want to warn about possible uninitialized as late
2418 as possible, thus don't do it here. However, without
2419 optimization we need to warn here about "may be uninitialized". */
2420 calculate_dominance_info (CDI_POST_DOMINATORS);
2422 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2424 /* Post-dominator information can not be reliably updated. Free it
2425 after the use. */
2427 free_dominance_info (CDI_POST_DOMINATORS);
2428 return 0;
2432 namespace {
2434 const pass_data pass_data_early_warn_uninitialized =
2436 GIMPLE_PASS, /* type */
2437 "*early_warn_uninitialized", /* name */
2438 OPTGROUP_NONE, /* optinfo_flags */
2439 TV_TREE_UNINIT, /* tv_id */
2440 PROP_ssa, /* properties_required */
2441 0, /* properties_provided */
2442 0, /* properties_destroyed */
2443 0, /* todo_flags_start */
2444 0, /* todo_flags_finish */
2447 class pass_early_warn_uninitialized : public gimple_opt_pass
2449 public:
2450 pass_early_warn_uninitialized (gcc::context *ctxt)
2451 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2454 /* opt_pass methods: */
2455 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2456 virtual unsigned int execute (function *)
2458 return execute_early_warn_uninitialized ();
2461 }; // class pass_early_warn_uninitialized
2463 } // anon namespace
2465 gimple_opt_pass *
2466 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2468 return new pass_early_warn_uninitialized (ctxt);