* gcc.dg/store-motion-fgcse-sm.c (dg-final): Cleanup
[official-gcc.git] / gcc / tree-ssa-uninit.c
blob9fa3acf2ea3c7f0668c076869cd36e7696442dd1
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 "predict.h"
29 #include "vec.h"
30 #include "hashtab.h"
31 #include "hash-set.h"
32 #include "machmode.h"
33 #include "hard-reg-set.h"
34 #include "input.h"
35 #include "function.h"
36 #include "dominance.h"
37 #include "cfg.h"
38 #include "basic-block.h"
39 #include "gimple-pretty-print.h"
40 #include "bitmap.h"
41 #include "tree-ssa-alias.h"
42 #include "internal-fn.h"
43 #include "gimple-expr.h"
44 #include "is-a.h"
45 #include "gimple.h"
46 #include "gimple-iterator.h"
47 #include "gimple-ssa.h"
48 #include "tree-phinodes.h"
49 #include "ssa-iterators.h"
50 #include "tree-ssa.h"
51 #include "tree-inline.h"
52 #include "tree-pass.h"
53 #include "diagnostic-core.h"
54 #include "params.h"
56 /* This implements the pass that does predicate aware warning on uses of
57 possibly uninitialized variables. The pass first collects the set of
58 possibly uninitialized SSA names. For each such name, it walks through
59 all its immediate uses. For each immediate use, it rebuilds the condition
60 expression (the predicate) that guards the use. The predicate is then
61 examined to see if the variable is always defined under that same condition.
62 This is done either by pruning the unrealizable paths that lead to the
63 default definitions or by checking if the predicate set that guards the
64 defining paths is a superset of the use predicate. */
67 /* Pointer set of potentially undefined ssa names, i.e.,
68 ssa names that are defined by phi with operands that
69 are not defined or potentially undefined. */
70 static hash_set<tree> *possibly_undefined_names = 0;
72 /* Bit mask handling macros. */
73 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
74 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
75 #define MASK_EMPTY(mask) (mask == 0)
77 /* Returns the first bit position (starting from LSB)
78 in mask that is non zero. Returns -1 if the mask is empty. */
79 static int
80 get_mask_first_set_bit (unsigned mask)
82 int pos = 0;
83 if (mask == 0)
84 return -1;
86 while ((mask & (1 << pos)) == 0)
87 pos++;
89 return pos;
91 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
93 /* Return true if T, an SSA_NAME, has an undefined value. */
94 static bool
95 has_undefined_value_p (tree t)
97 return (ssa_undefined_value_p (t)
98 || (possibly_undefined_names
99 && possibly_undefined_names->contains (t)));
104 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
105 is set on SSA_NAME_VAR. */
107 static inline bool
108 uninit_undefined_value_p (tree t) {
109 if (!has_undefined_value_p (t))
110 return false;
111 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
112 return false;
113 return true;
116 /* Emit warnings for uninitialized variables. This is done in two passes.
118 The first pass notices real uses of SSA names with undefined values.
119 Such uses are unconditionally uninitialized, and we can be certain that
120 such a use is a mistake. This pass is run before most optimizations,
121 so that we catch as many as we can.
123 The second pass follows PHI nodes to find uses that are potentially
124 uninitialized. In this case we can't necessarily prove that the use
125 is really uninitialized. This pass is run after most optimizations,
126 so that we thread as many jumps and possible, and delete as much dead
127 code as possible, in order to reduce false positives. We also look
128 again for plain uninitialized variables, since optimization may have
129 changed conditionally uninitialized to unconditionally uninitialized. */
131 /* Emit a warning for EXPR based on variable VAR at the point in the
132 program T, an SSA_NAME, is used being uninitialized. The exact
133 warning text is in MSGID and DATA is the gimple stmt with info about
134 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
135 gives which argument of the phi node to take the location from. WC
136 is the warning code. */
138 static void
139 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
140 const char *gmsgid, void *data, location_t phiarg_loc)
142 gimple context = (gimple) data;
143 location_t location, cfun_loc;
144 expanded_location xloc, floc;
146 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
147 turns in a COMPLEX_EXPR with the not initialized part being
148 set to its previous (undefined) value. */
149 if (is_gimple_assign (context)
150 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
151 return;
152 if (!has_undefined_value_p (t))
153 return;
155 /* TREE_NO_WARNING either means we already warned, or the front end
156 wishes to suppress the warning. */
157 if ((context
158 && (gimple_no_warning_p (context)
159 || (gimple_assign_single_p (context)
160 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
161 || TREE_NO_WARNING (expr))
162 return;
164 if (context != NULL && gimple_has_location (context))
165 location = gimple_location (context);
166 else if (phiarg_loc != UNKNOWN_LOCATION)
167 location = phiarg_loc;
168 else
169 location = DECL_SOURCE_LOCATION (var);
170 location = linemap_resolve_location (line_table, location,
171 LRK_SPELLING_LOCATION,
172 NULL);
173 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
174 xloc = expand_location (location);
175 floc = expand_location (cfun_loc);
176 if (warning_at (location, wc, gmsgid, expr))
178 TREE_NO_WARNING (expr) = 1;
180 if (location == DECL_SOURCE_LOCATION (var))
181 return;
182 if (xloc.file != floc.file
183 || linemap_location_before_p (line_table,
184 location, cfun_loc)
185 || linemap_location_before_p (line_table,
186 cfun->function_end_locus,
187 location))
188 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
192 static unsigned int
193 warn_uninitialized_vars (bool warn_possibly_uninitialized)
195 gimple_stmt_iterator gsi;
196 basic_block bb;
198 FOR_EACH_BB_FN (bb, cfun)
200 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS,
201 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)), bb);
202 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
204 gimple stmt = gsi_stmt (gsi);
205 use_operand_p use_p;
206 ssa_op_iter op_iter;
207 tree use;
209 if (is_gimple_debug (stmt))
210 continue;
212 /* We only do data flow with SSA_NAMEs, so that's all we
213 can warn about. */
214 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
216 use = USE_FROM_PTR (use_p);
217 if (always_executed)
218 warn_uninit (OPT_Wuninitialized, use,
219 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
220 "%qD is used uninitialized in this function",
221 stmt, UNKNOWN_LOCATION);
222 else if (warn_possibly_uninitialized)
223 warn_uninit (OPT_Wmaybe_uninitialized, use,
224 SSA_NAME_VAR (use), SSA_NAME_VAR (use),
225 "%qD may be used uninitialized in this function",
226 stmt, UNKNOWN_LOCATION);
229 /* For memory the only cheap thing we can do is see if we
230 have a use of the default def of the virtual operand.
231 ??? Not so cheap would be to use the alias oracle via
232 walk_aliased_vdefs, if we don't find any aliasing vdef
233 warn as is-used-uninitialized, if we don't find an aliasing
234 vdef that kills our use (stmt_kills_ref_p), warn as
235 may-be-used-uninitialized. But this walk is quadratic and
236 so must be limited which means we would miss warning
237 opportunities. */
238 use = gimple_vuse (stmt);
239 if (use
240 && gimple_assign_single_p (stmt)
241 && !gimple_vdef (stmt)
242 && SSA_NAME_IS_DEFAULT_DEF (use))
244 tree rhs = gimple_assign_rhs1 (stmt);
245 tree base = get_base_address (rhs);
247 /* Do not warn if it can be initialized outside this function. */
248 if (TREE_CODE (base) != VAR_DECL
249 || DECL_HARD_REGISTER (base)
250 || is_global_var (base))
251 continue;
253 if (always_executed)
254 warn_uninit (OPT_Wuninitialized, use,
255 gimple_assign_rhs1 (stmt), base,
256 "%qE is used uninitialized in this function",
257 stmt, UNKNOWN_LOCATION);
258 else if (warn_possibly_uninitialized)
259 warn_uninit (OPT_Wmaybe_uninitialized, use,
260 gimple_assign_rhs1 (stmt), base,
261 "%qE may be used uninitialized in this function",
262 stmt, UNKNOWN_LOCATION);
267 return 0;
270 /* Checks if the operand OPND of PHI is defined by
271 another phi with one operand defined by this PHI,
272 but the rest operands are all defined. If yes,
273 returns true to skip this this operand as being
274 redundant. Can be enhanced to be more general. */
276 static bool
277 can_skip_redundant_opnd (tree opnd, gimple phi)
279 gimple op_def;
280 tree phi_def;
281 int i, n;
283 phi_def = gimple_phi_result (phi);
284 op_def = SSA_NAME_DEF_STMT (opnd);
285 if (gimple_code (op_def) != GIMPLE_PHI)
286 return false;
287 n = gimple_phi_num_args (op_def);
288 for (i = 0; i < n; ++i)
290 tree op = gimple_phi_arg_def (op_def, i);
291 if (TREE_CODE (op) != SSA_NAME)
292 continue;
293 if (op != phi_def && uninit_undefined_value_p (op))
294 return false;
297 return true;
300 /* Returns a bit mask holding the positions of arguments in PHI
301 that have empty (or possibly empty) definitions. */
303 static unsigned
304 compute_uninit_opnds_pos (gphi *phi)
306 size_t i, n;
307 unsigned uninit_opnds = 0;
309 n = gimple_phi_num_args (phi);
310 /* Bail out for phi with too many args. */
311 if (n > 32)
312 return 0;
314 for (i = 0; i < n; ++i)
316 tree op = gimple_phi_arg_def (phi, i);
317 if (TREE_CODE (op) == SSA_NAME
318 && uninit_undefined_value_p (op)
319 && !can_skip_redundant_opnd (op, phi))
321 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
323 /* Ignore SSA_NAMEs that appear on abnormal edges
324 somewhere. */
325 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
326 continue;
328 MASK_SET_BIT (uninit_opnds, i);
331 return uninit_opnds;
334 /* Find the immediate postdominator PDOM of the specified
335 basic block BLOCK. */
337 static inline basic_block
338 find_pdom (basic_block block)
340 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
341 return EXIT_BLOCK_PTR_FOR_FN (cfun);
342 else
344 basic_block bb
345 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
346 if (! bb)
347 return EXIT_BLOCK_PTR_FOR_FN (cfun);
348 return bb;
352 /* Find the immediate DOM of the specified
353 basic block BLOCK. */
355 static inline basic_block
356 find_dom (basic_block block)
358 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
359 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
360 else
362 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
363 if (! bb)
364 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
365 return bb;
369 /* Returns true if BB1 is postdominating BB2 and BB1 is
370 not a loop exit bb. The loop exit bb check is simple and does
371 not cover all cases. */
373 static bool
374 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
376 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
377 return false;
379 if (single_pred_p (bb1) && !single_succ_p (bb2))
380 return false;
382 return true;
385 /* Find the closest postdominator of a specified BB, which is control
386 equivalent to BB. */
388 static inline basic_block
389 find_control_equiv_block (basic_block bb)
391 basic_block pdom;
393 pdom = find_pdom (bb);
395 /* Skip the postdominating bb that is also loop exit. */
396 if (!is_non_loop_exit_postdominating (pdom, bb))
397 return NULL;
399 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
400 return pdom;
402 return NULL;
405 #define MAX_NUM_CHAINS 8
406 #define MAX_CHAIN_LEN 5
407 #define MAX_POSTDOM_CHECK 8
409 /* Computes the control dependence chains (paths of edges)
410 for DEP_BB up to the dominating basic block BB (the head node of a
411 chain should be dominated by it). CD_CHAINS is pointer to an
412 array holding the result chains. CUR_CD_CHAIN is the current
413 chain being computed. *NUM_CHAINS is total number of chains. The
414 function returns true if the information is successfully computed,
415 return false if there is no control dependence or not computed. */
417 static bool
418 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
419 vec<edge> *cd_chains,
420 size_t *num_chains,
421 vec<edge> *cur_cd_chain,
422 int *num_calls)
424 edge_iterator ei;
425 edge e;
426 size_t i;
427 bool found_cd_chain = false;
428 size_t cur_chain_len = 0;
430 if (EDGE_COUNT (bb->succs) < 2)
431 return false;
433 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
434 return false;
435 ++*num_calls;
437 /* Could use a set instead. */
438 cur_chain_len = cur_cd_chain->length ();
439 if (cur_chain_len > MAX_CHAIN_LEN)
440 return false;
442 for (i = 0; i < cur_chain_len; i++)
444 edge e = (*cur_cd_chain)[i];
445 /* Cycle detected. */
446 if (e->src == bb)
447 return false;
450 FOR_EACH_EDGE (e, ei, bb->succs)
452 basic_block cd_bb;
453 int post_dom_check = 0;
454 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
455 continue;
457 cd_bb = e->dest;
458 cur_cd_chain->safe_push (e);
459 while (!is_non_loop_exit_postdominating (cd_bb, bb))
461 if (cd_bb == dep_bb)
463 /* Found a direct control dependence. */
464 if (*num_chains < MAX_NUM_CHAINS)
466 cd_chains[*num_chains] = cur_cd_chain->copy ();
467 (*num_chains)++;
469 found_cd_chain = true;
470 /* Check path from next edge. */
471 break;
474 /* Now check if DEP_BB is indirectly control dependent on BB. */
475 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
476 num_chains, cur_cd_chain, num_calls))
478 found_cd_chain = true;
479 break;
482 cd_bb = find_pdom (cd_bb);
483 post_dom_check++;
484 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || post_dom_check >
485 MAX_POSTDOM_CHECK)
486 break;
488 cur_cd_chain->pop ();
489 gcc_assert (cur_cd_chain->length () == cur_chain_len);
491 gcc_assert (cur_cd_chain->length () == cur_chain_len);
493 return found_cd_chain;
496 /* The type to represent a simple predicate */
498 typedef struct use_def_pred_info
500 tree pred_lhs;
501 tree pred_rhs;
502 enum tree_code cond_code;
503 bool invert;
504 } pred_info;
506 /* The type to represent a sequence of predicates grouped
507 with .AND. operation. */
509 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
511 /* The type to represent a sequence of pred_chains grouped
512 with .OR. operation. */
514 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
516 /* Converts the chains of control dependence edges into a set of
517 predicates. A control dependence chain is represented by a vector
518 edges. DEP_CHAINS points to an array of dependence chains.
519 NUM_CHAINS is the size of the chain array. One edge in a dependence
520 chain is mapped to predicate expression represented by pred_info
521 type. One dependence chain is converted to a composite predicate that
522 is the result of AND operation of pred_info mapped to each edge.
523 A composite predicate is presented by a vector of pred_info. On
524 return, *PREDS points to the resulting array of composite predicates.
525 *NUM_PREDS is the number of composite predictes. */
527 static bool
528 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
529 size_t num_chains,
530 pred_chain_union *preds)
532 bool has_valid_pred = false;
533 size_t i, j;
534 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
535 return false;
537 /* Now convert the control dep chain into a set
538 of predicates. */
539 preds->reserve (num_chains);
541 for (i = 0; i < num_chains; i++)
543 vec<edge> one_cd_chain = dep_chains[i];
545 has_valid_pred = false;
546 pred_chain t_chain = vNULL;
547 for (j = 0; j < one_cd_chain.length (); j++)
549 gimple cond_stmt;
550 gimple_stmt_iterator gsi;
551 basic_block guard_bb;
552 pred_info one_pred;
553 edge e;
555 e = one_cd_chain[j];
556 guard_bb = e->src;
557 gsi = gsi_last_bb (guard_bb);
558 if (gsi_end_p (gsi))
560 has_valid_pred = false;
561 break;
563 cond_stmt = gsi_stmt (gsi);
564 if (is_gimple_call (cond_stmt)
565 && EDGE_COUNT (e->src->succs) >= 2)
567 /* Ignore EH edge. Can add assertion
568 on the other edge's flag. */
569 continue;
571 /* Skip if there is essentially one succesor. */
572 if (EDGE_COUNT (e->src->succs) == 2)
574 edge e1;
575 edge_iterator ei1;
576 bool skip = false;
578 FOR_EACH_EDGE (e1, ei1, e->src->succs)
580 if (EDGE_COUNT (e1->dest->succs) == 0)
582 skip = true;
583 break;
586 if (skip)
587 continue;
589 if (gimple_code (cond_stmt) != GIMPLE_COND)
591 has_valid_pred = false;
592 break;
594 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
595 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
596 one_pred.cond_code = gimple_cond_code (cond_stmt);
597 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
598 t_chain.safe_push (one_pred);
599 has_valid_pred = true;
602 if (!has_valid_pred)
603 break;
604 else
605 preds->safe_push (t_chain);
607 return has_valid_pred;
610 /* Computes all control dependence chains for USE_BB. The control
611 dependence chains are then converted to an array of composite
612 predicates pointed to by PREDS. PHI_BB is the basic block of
613 the phi whose result is used in USE_BB. */
615 static bool
616 find_predicates (pred_chain_union *preds,
617 basic_block phi_bb,
618 basic_block use_bb)
620 size_t num_chains = 0, i;
621 int num_calls = 0;
622 vec<edge> dep_chains[MAX_NUM_CHAINS];
623 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
624 bool has_valid_pred = false;
625 basic_block cd_root = 0;
627 /* First find the closest bb that is control equivalent to PHI_BB
628 that also dominates USE_BB. */
629 cd_root = phi_bb;
630 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
632 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
633 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
634 cd_root = ctrl_eq_bb;
635 else
636 break;
639 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
640 &cur_chain, &num_calls);
642 has_valid_pred
643 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
644 for (i = 0; i < num_chains; i++)
645 dep_chains[i].release ();
646 return has_valid_pred;
649 /* Computes the set of incoming edges of PHI that have non empty
650 definitions of a phi chain. The collection will be done
651 recursively on operands that are defined by phis. CD_ROOT
652 is the control dependence root. *EDGES holds the result, and
653 VISITED_PHIS is a pointer set for detecting cycles. */
655 static void
656 collect_phi_def_edges (gphi *phi, basic_block cd_root,
657 vec<edge> *edges,
658 hash_set<gimple> *visited_phis)
660 size_t i, n;
661 edge opnd_edge;
662 tree opnd;
664 if (visited_phis->add (phi))
665 return;
667 n = gimple_phi_num_args (phi);
668 for (i = 0; i < n; i++)
670 opnd_edge = gimple_phi_arg_edge (phi, i);
671 opnd = gimple_phi_arg_def (phi, i);
673 if (TREE_CODE (opnd) != SSA_NAME)
675 if (dump_file && (dump_flags & TDF_DETAILS))
677 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
678 print_gimple_stmt (dump_file, phi, 0, 0);
680 edges->safe_push (opnd_edge);
682 else
684 gimple def = SSA_NAME_DEF_STMT (opnd);
686 if (gimple_code (def) == GIMPLE_PHI
687 && dominated_by_p (CDI_DOMINATORS,
688 gimple_bb (def), cd_root))
689 collect_phi_def_edges (as_a <gphi *> (def), cd_root, edges,
690 visited_phis);
691 else if (!uninit_undefined_value_p (opnd))
693 if (dump_file && (dump_flags & TDF_DETAILS))
695 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
696 print_gimple_stmt (dump_file, phi, 0, 0);
698 edges->safe_push (opnd_edge);
704 /* For each use edge of PHI, computes all control dependence chains.
705 The control dependence chains are then converted to an array of
706 composite predicates pointed to by PREDS. */
708 static bool
709 find_def_preds (pred_chain_union *preds, gphi *phi)
711 size_t num_chains = 0, i, n;
712 vec<edge> dep_chains[MAX_NUM_CHAINS];
713 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
714 vec<edge> def_edges = vNULL;
715 bool has_valid_pred = false;
716 basic_block phi_bb, cd_root = 0;
718 phi_bb = gimple_bb (phi);
719 /* First find the closest dominating bb to be
720 the control dependence root */
721 cd_root = find_dom (phi_bb);
722 if (!cd_root)
723 return false;
725 hash_set<gimple> visited_phis;
726 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
728 n = def_edges.length ();
729 if (n == 0)
730 return false;
732 for (i = 0; i < n; i++)
734 size_t prev_nc, j;
735 int num_calls = 0;
736 edge opnd_edge;
738 opnd_edge = def_edges[i];
739 prev_nc = num_chains;
740 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
741 &num_chains, &cur_chain, &num_calls);
743 /* Now update the newly added chains with
744 the phi operand edge: */
745 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
747 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
748 dep_chains[num_chains++] = vNULL;
749 for (j = prev_nc; j < num_chains; j++)
750 dep_chains[j].safe_push (opnd_edge);
754 has_valid_pred
755 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
756 for (i = 0; i < num_chains; i++)
757 dep_chains[i].release ();
758 return has_valid_pred;
761 /* Dumps the predicates (PREDS) for USESTMT. */
763 static void
764 dump_predicates (gimple usestmt, pred_chain_union preds,
765 const char* msg)
767 size_t i, j;
768 pred_chain one_pred_chain = vNULL;
769 fprintf (dump_file, msg);
770 print_gimple_stmt (dump_file, usestmt, 0, 0);
771 fprintf (dump_file, "is guarded by :\n\n");
772 size_t num_preds = preds.length ();
773 /* Do some dumping here: */
774 for (i = 0; i < num_preds; i++)
776 size_t np;
778 one_pred_chain = preds[i];
779 np = one_pred_chain.length ();
781 for (j = 0; j < np; j++)
783 pred_info one_pred = one_pred_chain[j];
784 if (one_pred.invert)
785 fprintf (dump_file, " (.NOT.) ");
786 print_generic_expr (dump_file, one_pred.pred_lhs, 0);
787 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
788 print_generic_expr (dump_file, one_pred.pred_rhs, 0);
789 if (j < np - 1)
790 fprintf (dump_file, " (.AND.) ");
791 else
792 fprintf (dump_file, "\n");
794 if (i < num_preds - 1)
795 fprintf (dump_file, "(.OR.)\n");
796 else
797 fprintf (dump_file, "\n\n");
801 /* Destroys the predicate set *PREDS. */
803 static void
804 destroy_predicate_vecs (pred_chain_union preds)
806 size_t i;
808 size_t n = preds.length ();
809 for (i = 0; i < n; i++)
810 preds[i].release ();
811 preds.release ();
815 /* Computes the 'normalized' conditional code with operand
816 swapping and condition inversion. */
818 static enum tree_code
819 get_cmp_code (enum tree_code orig_cmp_code,
820 bool swap_cond, bool invert)
822 enum tree_code tc = orig_cmp_code;
824 if (swap_cond)
825 tc = swap_tree_comparison (orig_cmp_code);
826 if (invert)
827 tc = invert_tree_comparison (tc, false);
829 switch (tc)
831 case LT_EXPR:
832 case LE_EXPR:
833 case GT_EXPR:
834 case GE_EXPR:
835 case EQ_EXPR:
836 case NE_EXPR:
837 break;
838 default:
839 return ERROR_MARK;
841 return tc;
844 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
845 all values in the range satisfies (x CMPC BOUNDARY) == true. */
847 static bool
848 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
850 bool inverted = false;
851 bool is_unsigned;
852 bool result;
854 /* Only handle integer constant here. */
855 if (TREE_CODE (val) != INTEGER_CST
856 || TREE_CODE (boundary) != INTEGER_CST)
857 return true;
859 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
861 if (cmpc == GE_EXPR || cmpc == GT_EXPR
862 || cmpc == NE_EXPR)
864 cmpc = invert_tree_comparison (cmpc, false);
865 inverted = true;
868 if (is_unsigned)
870 if (cmpc == EQ_EXPR)
871 result = tree_int_cst_equal (val, boundary);
872 else if (cmpc == LT_EXPR)
873 result = tree_int_cst_lt (val, boundary);
874 else
876 gcc_assert (cmpc == LE_EXPR);
877 result = tree_int_cst_le (val, boundary);
880 else
882 if (cmpc == EQ_EXPR)
883 result = tree_int_cst_equal (val, boundary);
884 else if (cmpc == LT_EXPR)
885 result = tree_int_cst_lt (val, boundary);
886 else
888 gcc_assert (cmpc == LE_EXPR);
889 result = (tree_int_cst_equal (val, boundary)
890 || tree_int_cst_lt (val, boundary));
894 if (inverted)
895 result ^= 1;
897 return result;
900 /* Returns true if PRED is common among all the predicate
901 chains (PREDS) (and therefore can be factored out).
902 NUM_PRED_CHAIN is the size of array PREDS. */
904 static bool
905 find_matching_predicate_in_rest_chains (pred_info pred,
906 pred_chain_union preds,
907 size_t num_pred_chains)
909 size_t i, j, n;
911 /* Trival case. */
912 if (num_pred_chains == 1)
913 return true;
915 for (i = 1; i < num_pred_chains; i++)
917 bool found = false;
918 pred_chain one_chain = preds[i];
919 n = one_chain.length ();
920 for (j = 0; j < n; j++)
922 pred_info pred2 = one_chain[j];
923 /* Can relax the condition comparison to not
924 use address comparison. However, the most common
925 case is that multiple control dependent paths share
926 a common path prefix, so address comparison should
927 be ok. */
929 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
930 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
931 && pred2.invert == pred.invert)
933 found = true;
934 break;
937 if (!found)
938 return false;
940 return true;
943 /* Forward declaration. */
944 static bool
945 is_use_properly_guarded (gimple use_stmt,
946 basic_block use_bb,
947 gphi *phi,
948 unsigned uninit_opnds,
949 hash_set<gphi *> *visited_phis);
951 /* Returns true if all uninitialized opnds are pruned. Returns false
952 otherwise. PHI is the phi node with uninitialized operands,
953 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
954 FLAG_DEF is the statement defining the flag guarding the use of the
955 PHI output, BOUNDARY_CST is the const value used in the predicate
956 associated with the flag, CMP_CODE is the comparison code used in
957 the predicate, VISITED_PHIS is the pointer set of phis visited, and
958 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
959 that are also phis.
961 Example scenario:
963 BB1:
964 flag_1 = phi <0, 1> // (1)
965 var_1 = phi <undef, some_val>
968 BB2:
969 flag_2 = phi <0, flag_1, flag_1> // (2)
970 var_2 = phi <undef, var_1, var_1>
971 if (flag_2 == 1)
972 goto BB3;
974 BB3:
975 use of var_2 // (3)
977 Because some flag arg in (1) is not constant, if we do not look into the
978 flag phis recursively, it is conservatively treated as unknown and var_1
979 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
980 a false warning will be emitted. Checking recursively into (1), the compiler can
981 find out that only some_val (which is defined) can flow into (3) which is OK.
985 static bool
986 prune_uninit_phi_opnds_in_unrealizable_paths (gphi *phi,
987 unsigned uninit_opnds,
988 gphi *flag_def,
989 tree boundary_cst,
990 enum tree_code cmp_code,
991 hash_set<gphi *> *visited_phis,
992 bitmap *visited_flag_phis)
994 unsigned i;
996 for (i = 0; i < MIN (32, gimple_phi_num_args (flag_def)); i++)
998 tree flag_arg;
1000 if (!MASK_TEST_BIT (uninit_opnds, i))
1001 continue;
1003 flag_arg = gimple_phi_arg_def (flag_def, i);
1004 if (!is_gimple_constant (flag_arg))
1006 gphi *flag_arg_def, *phi_arg_def;
1007 tree phi_arg;
1008 unsigned uninit_opnds_arg_phi;
1010 if (TREE_CODE (flag_arg) != SSA_NAME)
1011 return false;
1012 flag_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (flag_arg));
1013 if (!flag_arg_def)
1014 return false;
1016 phi_arg = gimple_phi_arg_def (phi, i);
1017 if (TREE_CODE (phi_arg) != SSA_NAME)
1018 return false;
1020 phi_arg_def = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1021 if (!phi_arg_def)
1022 return false;
1024 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1025 return false;
1027 if (!*visited_flag_phis)
1028 *visited_flag_phis = BITMAP_ALLOC (NULL);
1030 if (bitmap_bit_p (*visited_flag_phis,
1031 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def))))
1032 return false;
1034 bitmap_set_bit (*visited_flag_phis,
1035 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1037 /* Now recursively prune the uninitialized phi args. */
1038 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1039 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1040 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def,
1041 boundary_cst, cmp_code, visited_phis, visited_flag_phis))
1042 return false;
1044 bitmap_clear_bit (*visited_flag_phis,
1045 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1046 continue;
1049 /* Now check if the constant is in the guarded range. */
1050 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1052 tree opnd;
1053 gimple opnd_def;
1055 /* Now that we know that this undefined edge is not
1056 pruned. If the operand is defined by another phi,
1057 we can further prune the incoming edges of that
1058 phi by checking the predicates of this operands. */
1060 opnd = gimple_phi_arg_def (phi, i);
1061 opnd_def = SSA_NAME_DEF_STMT (opnd);
1062 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
1064 edge opnd_edge;
1065 unsigned uninit_opnds2
1066 = compute_uninit_opnds_pos (opnd_def_phi);
1067 gcc_assert (!MASK_EMPTY (uninit_opnds2));
1068 opnd_edge = gimple_phi_arg_edge (phi, i);
1069 if (!is_use_properly_guarded (phi,
1070 opnd_edge->src,
1071 opnd_def_phi,
1072 uninit_opnds2,
1073 visited_phis))
1074 return false;
1076 else
1077 return false;
1081 return true;
1084 /* A helper function that determines if the predicate set
1085 of the use is not overlapping with that of the uninit paths.
1086 The most common senario of guarded use is in Example 1:
1087 Example 1:
1088 if (some_cond)
1090 x = ...;
1091 flag = true;
1094 ... some code ...
1096 if (flag)
1097 use (x);
1099 The real world examples are usually more complicated, but similar
1100 and usually result from inlining:
1102 bool init_func (int * x)
1104 if (some_cond)
1105 return false;
1106 *x = ..
1107 return true;
1110 void foo(..)
1112 int x;
1114 if (!init_func(&x))
1115 return;
1117 .. some_code ...
1118 use (x);
1121 Another possible use scenario is in the following trivial example:
1123 Example 2:
1124 if (n > 0)
1125 x = 1;
1127 if (n > 0)
1129 if (m < 2)
1130 .. = x;
1133 Predicate analysis needs to compute the composite predicate:
1135 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1136 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1137 (the predicate chain for phi operand defs can be computed
1138 starting from a bb that is control equivalent to the phi's
1139 bb and is dominating the operand def.)
1141 and check overlapping:
1142 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1143 <==> false
1145 This implementation provides framework that can handle
1146 scenarios. (Note that many simple cases are handled properly
1147 without the predicate analysis -- this is due to jump threading
1148 transformation which eliminates the merge point thus makes
1149 path sensitive analysis unnecessary.)
1151 NUM_PREDS is the number is the number predicate chains, PREDS is
1152 the array of chains, PHI is the phi node whose incoming (undefined)
1153 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1154 uninit operand positions. VISITED_PHIS is the pointer set of phi
1155 stmts being checked. */
1158 static bool
1159 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1160 gphi *phi, unsigned uninit_opnds,
1161 hash_set<gphi *> *visited_phis)
1163 unsigned int i, n;
1164 gimple flag_def = 0;
1165 tree boundary_cst = 0;
1166 enum tree_code cmp_code;
1167 bool swap_cond = false;
1168 bool invert = false;
1169 pred_chain the_pred_chain = vNULL;
1170 bitmap visited_flag_phis = NULL;
1171 bool all_pruned = false;
1172 size_t num_preds = preds.length ();
1174 gcc_assert (num_preds > 0);
1175 /* Find within the common prefix of multiple predicate chains
1176 a predicate that is a comparison of a flag variable against
1177 a constant. */
1178 the_pred_chain = preds[0];
1179 n = the_pred_chain.length ();
1180 for (i = 0; i < n; i++)
1182 tree cond_lhs, cond_rhs, flag = 0;
1184 pred_info the_pred = the_pred_chain[i];
1186 invert = the_pred.invert;
1187 cond_lhs = the_pred.pred_lhs;
1188 cond_rhs = the_pred.pred_rhs;
1189 cmp_code = the_pred.cond_code;
1191 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1192 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1194 boundary_cst = cond_rhs;
1195 flag = cond_lhs;
1197 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1198 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1200 boundary_cst = cond_lhs;
1201 flag = cond_rhs;
1202 swap_cond = true;
1205 if (!flag)
1206 continue;
1208 flag_def = SSA_NAME_DEF_STMT (flag);
1210 if (!flag_def)
1211 continue;
1213 if ((gimple_code (flag_def) == GIMPLE_PHI)
1214 && (gimple_bb (flag_def) == gimple_bb (phi))
1215 && find_matching_predicate_in_rest_chains (the_pred, preds,
1216 num_preds))
1217 break;
1219 flag_def = 0;
1222 if (!flag_def)
1223 return false;
1225 /* Now check all the uninit incoming edge has a constant flag value
1226 that is in conflict with the use guard/predicate. */
1227 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1229 if (cmp_code == ERROR_MARK)
1230 return false;
1232 all_pruned = prune_uninit_phi_opnds_in_unrealizable_paths (phi,
1233 uninit_opnds,
1234 as_a <gphi *> (flag_def),
1235 boundary_cst,
1236 cmp_code,
1237 visited_phis,
1238 &visited_flag_phis);
1240 if (visited_flag_phis)
1241 BITMAP_FREE (visited_flag_phis);
1243 return all_pruned;
1246 /* The helper function returns true if two predicates X1 and X2
1247 are equivalent. It assumes the expressions have already
1248 properly re-associated. */
1250 static inline bool
1251 pred_equal_p (pred_info x1, pred_info x2)
1253 enum tree_code c1, c2;
1254 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1255 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1256 return false;
1258 c1 = x1.cond_code;
1259 if (x1.invert != x2.invert)
1260 c2 = invert_tree_comparison (x2.cond_code, false);
1261 else
1262 c2 = x2.cond_code;
1264 return c1 == c2;
1267 /* Returns true if the predication is testing !=. */
1269 static inline bool
1270 is_neq_relop_p (pred_info pred)
1273 return (pred.cond_code == NE_EXPR && !pred.invert)
1274 || (pred.cond_code == EQ_EXPR && pred.invert);
1277 /* Returns true if pred is of the form X != 0. */
1279 static inline bool
1280 is_neq_zero_form_p (pred_info pred)
1282 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1283 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1284 return false;
1285 return true;
1288 /* The helper function returns true if two predicates X1
1289 is equivalent to X2 != 0. */
1291 static inline bool
1292 pred_expr_equal_p (pred_info x1, tree x2)
1294 if (!is_neq_zero_form_p (x1))
1295 return false;
1297 return operand_equal_p (x1.pred_lhs, x2, 0);
1300 /* Returns true of the domain of single predicate expression
1301 EXPR1 is a subset of that of EXPR2. Returns false if it
1302 can not be proved. */
1304 static bool
1305 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1307 enum tree_code code1, code2;
1309 if (pred_equal_p (expr1, expr2))
1310 return true;
1312 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1313 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1314 return false;
1316 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1317 return false;
1319 code1 = expr1.cond_code;
1320 if (expr1.invert)
1321 code1 = invert_tree_comparison (code1, false);
1322 code2 = expr2.cond_code;
1323 if (expr2.invert)
1324 code2 = invert_tree_comparison (code2, false);
1326 if (code1 != code2 && code2 != NE_EXPR)
1327 return false;
1329 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1330 return true;
1332 return false;
1335 /* Returns true if the domain of PRED1 is a subset
1336 of that of PRED2. Returns false if it can not be proved so. */
1338 static bool
1339 is_pred_chain_subset_of (pred_chain pred1,
1340 pred_chain pred2)
1342 size_t np1, np2, i1, i2;
1344 np1 = pred1.length ();
1345 np2 = pred2.length ();
1347 for (i2 = 0; i2 < np2; i2++)
1349 bool found = false;
1350 pred_info info2 = pred2[i2];
1351 for (i1 = 0; i1 < np1; i1++)
1353 pred_info info1 = pred1[i1];
1354 if (is_pred_expr_subset_of (info1, info2))
1356 found = true;
1357 break;
1360 if (!found)
1361 return false;
1363 return true;
1366 /* Returns true if the domain defined by
1367 one pred chain ONE_PRED is a subset of the domain
1368 of *PREDS. It returns false if ONE_PRED's domain is
1369 not a subset of any of the sub-domains of PREDS
1370 (corresponding to each individual chains in it), even
1371 though it may be still be a subset of whole domain
1372 of PREDS which is the union (ORed) of all its subdomains.
1373 In other words, the result is conservative. */
1375 static bool
1376 is_included_in (pred_chain one_pred, pred_chain_union preds)
1378 size_t i;
1379 size_t n = preds.length ();
1381 for (i = 0; i < n; i++)
1383 if (is_pred_chain_subset_of (one_pred, preds[i]))
1384 return true;
1387 return false;
1390 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1391 true if the domain defined by PREDS1 is a superset
1392 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1393 PREDS2 respectively. The implementation chooses not to build
1394 generic trees (and relying on the folding capability of the
1395 compiler), but instead performs brute force comparison of
1396 individual predicate chains (won't be a compile time problem
1397 as the chains are pretty short). When the function returns
1398 false, it does not necessarily mean *PREDS1 is not a superset
1399 of *PREDS2, but mean it may not be so since the analysis can
1400 not prove it. In such cases, false warnings may still be
1401 emitted. */
1403 static bool
1404 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1406 size_t i, n2;
1407 pred_chain one_pred_chain = vNULL;
1409 n2 = preds2.length ();
1411 for (i = 0; i < n2; i++)
1413 one_pred_chain = preds2[i];
1414 if (!is_included_in (one_pred_chain, preds1))
1415 return false;
1418 return true;
1421 /* Returns true if TC is AND or OR. */
1423 static inline bool
1424 is_and_or_or_p (enum tree_code tc, tree type)
1426 return (tc == BIT_IOR_EXPR
1427 || (tc == BIT_AND_EXPR
1428 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1431 /* Returns true if X1 is the negate of X2. */
1433 static inline bool
1434 pred_neg_p (pred_info x1, pred_info x2)
1436 enum tree_code c1, c2;
1437 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1438 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1439 return false;
1441 c1 = x1.cond_code;
1442 if (x1.invert == x2.invert)
1443 c2 = invert_tree_comparison (x2.cond_code, false);
1444 else
1445 c2 = x2.cond_code;
1447 return c1 == c2;
1450 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1451 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1452 3) X OR (!X AND Y) is equivalent to (X OR Y);
1453 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1454 (x != 0 AND y != 0)
1455 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1456 (X AND Y) OR Z
1458 PREDS is the predicate chains, and N is the number of chains. */
1460 /* Helper function to implement rule 1 above. ONE_CHAIN is
1461 the AND predication to be simplified. */
1463 static void
1464 simplify_pred (pred_chain *one_chain)
1466 size_t i, j, n;
1467 bool simplified = false;
1468 pred_chain s_chain = vNULL;
1470 n = one_chain->length ();
1472 for (i = 0; i < n; i++)
1474 pred_info *a_pred = &(*one_chain)[i];
1476 if (!a_pred->pred_lhs)
1477 continue;
1478 if (!is_neq_zero_form_p (*a_pred))
1479 continue;
1481 gimple def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1482 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1483 continue;
1484 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1486 for (j = 0; j < n; j++)
1488 pred_info *b_pred = &(*one_chain)[j];
1490 if (!b_pred->pred_lhs)
1491 continue;
1492 if (!is_neq_zero_form_p (*b_pred))
1493 continue;
1495 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1496 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1498 /* Mark a_pred for removal. */
1499 a_pred->pred_lhs = NULL;
1500 a_pred->pred_rhs = NULL;
1501 simplified = true;
1502 break;
1508 if (!simplified)
1509 return;
1511 for (i = 0; i < n; i++)
1513 pred_info *a_pred = &(*one_chain)[i];
1514 if (!a_pred->pred_lhs)
1515 continue;
1516 s_chain.safe_push (*a_pred);
1519 one_chain->release ();
1520 *one_chain = s_chain;
1523 /* The helper function implements the rule 2 for the
1524 OR predicate PREDS.
1526 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1528 static bool
1529 simplify_preds_2 (pred_chain_union *preds)
1531 size_t i, j, n;
1532 bool simplified = false;
1533 pred_chain_union s_preds = vNULL;
1535 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1536 (X AND Y) OR (X AND !Y) is equivalent to X. */
1538 n = preds->length ();
1539 for (i = 0; i < n; i++)
1541 pred_info x, y;
1542 pred_chain *a_chain = &(*preds)[i];
1544 if (a_chain->length () != 2)
1545 continue;
1547 x = (*a_chain)[0];
1548 y = (*a_chain)[1];
1550 for (j = 0; j < n; j++)
1552 pred_chain *b_chain;
1553 pred_info x2, y2;
1555 if (j == i)
1556 continue;
1558 b_chain = &(*preds)[j];
1559 if (b_chain->length () != 2)
1560 continue;
1562 x2 = (*b_chain)[0];
1563 y2 = (*b_chain)[1];
1565 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1567 /* Kill a_chain. */
1568 a_chain->release ();
1569 b_chain->release ();
1570 b_chain->safe_push (x);
1571 simplified = true;
1572 break;
1574 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1576 /* Kill a_chain. */
1577 a_chain->release ();
1578 b_chain->release ();
1579 b_chain->safe_push (y);
1580 simplified = true;
1581 break;
1585 /* Now clean up the chain. */
1586 if (simplified)
1588 for (i = 0; i < n; i++)
1590 if ((*preds)[i].is_empty ())
1591 continue;
1592 s_preds.safe_push ((*preds)[i]);
1594 preds->release ();
1595 (*preds) = s_preds;
1596 s_preds = vNULL;
1599 return simplified;
1602 /* The helper function implements the rule 2 for the
1603 OR predicate PREDS.
1605 3) x OR (!x AND y) is equivalent to x OR y. */
1607 static bool
1608 simplify_preds_3 (pred_chain_union *preds)
1610 size_t i, j, n;
1611 bool simplified = false;
1613 /* Now iteratively simplify X OR (!X AND Z ..)
1614 into X OR (Z ...). */
1616 n = preds->length ();
1617 if (n < 2)
1618 return false;
1620 for (i = 0; i < n; i++)
1622 pred_info x;
1623 pred_chain *a_chain = &(*preds)[i];
1625 if (a_chain->length () != 1)
1626 continue;
1628 x = (*a_chain)[0];
1630 for (j = 0; j < n; j++)
1632 pred_chain *b_chain;
1633 pred_info x2;
1634 size_t k;
1636 if (j == i)
1637 continue;
1639 b_chain = &(*preds)[j];
1640 if (b_chain->length () < 2)
1641 continue;
1643 for (k = 0; k < b_chain->length (); k++)
1645 x2 = (*b_chain)[k];
1646 if (pred_neg_p (x, x2))
1648 b_chain->unordered_remove (k);
1649 simplified = true;
1650 break;
1655 return simplified;
1658 /* The helper function implements the rule 4 for the
1659 OR predicate PREDS.
1661 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1662 (x != 0 ANd y != 0). */
1664 static bool
1665 simplify_preds_4 (pred_chain_union *preds)
1667 size_t i, j, n;
1668 bool simplified = false;
1669 pred_chain_union s_preds = vNULL;
1670 gimple def_stmt;
1672 n = preds->length ();
1673 for (i = 0; i < n; i++)
1675 pred_info z;
1676 pred_chain *a_chain = &(*preds)[i];
1678 if (a_chain->length () != 1)
1679 continue;
1681 z = (*a_chain)[0];
1683 if (!is_neq_zero_form_p (z))
1684 continue;
1686 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1687 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1688 continue;
1690 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1691 continue;
1693 for (j = 0; j < n; j++)
1695 pred_chain *b_chain;
1696 pred_info x2, y2;
1698 if (j == i)
1699 continue;
1701 b_chain = &(*preds)[j];
1702 if (b_chain->length () != 2)
1703 continue;
1705 x2 = (*b_chain)[0];
1706 y2 = (*b_chain)[1];
1707 if (!is_neq_zero_form_p (x2)
1708 || !is_neq_zero_form_p (y2))
1709 continue;
1711 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1712 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1713 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1714 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1716 /* Kill a_chain. */
1717 a_chain->release ();
1718 simplified = true;
1719 break;
1723 /* Now clean up the chain. */
1724 if (simplified)
1726 for (i = 0; i < n; i++)
1728 if ((*preds)[i].is_empty ())
1729 continue;
1730 s_preds.safe_push ((*preds)[i]);
1732 preds->release ();
1733 (*preds) = s_preds;
1734 s_preds = vNULL;
1737 return simplified;
1741 /* This function simplifies predicates in PREDS. */
1743 static void
1744 simplify_preds (pred_chain_union *preds, gimple use_or_def, bool is_use)
1746 size_t i, n;
1747 bool changed = false;
1749 if (dump_file && dump_flags & TDF_DETAILS)
1751 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1752 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1755 for (i = 0; i < preds->length (); i++)
1756 simplify_pred (&(*preds)[i]);
1758 n = preds->length ();
1759 if (n < 2)
1760 return;
1764 changed = false;
1765 if (simplify_preds_2 (preds))
1766 changed = true;
1768 /* Now iteratively simplify X OR (!X AND Z ..)
1769 into X OR (Z ...). */
1770 if (simplify_preds_3 (preds))
1771 changed = true;
1773 if (simplify_preds_4 (preds))
1774 changed = true;
1776 } while (changed);
1778 return;
1781 /* This is a helper function which attempts to normalize predicate chains
1782 by following UD chains. It basically builds up a big tree of either IOR
1783 operations or AND operations, and convert the IOR tree into a
1784 pred_chain_union or BIT_AND tree into a pred_chain.
1785 Example:
1787 _3 = _2 RELOP1 _1;
1788 _6 = _5 RELOP2 _4;
1789 _9 = _8 RELOP3 _7;
1790 _10 = _3 | _6;
1791 _12 = _9 | _0;
1792 _t = _10 | _12;
1794 then _t != 0 will be normalized into a pred_chain_union
1796 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1798 Similarly given,
1800 _3 = _2 RELOP1 _1;
1801 _6 = _5 RELOP2 _4;
1802 _9 = _8 RELOP3 _7;
1803 _10 = _3 & _6;
1804 _12 = _9 & _0;
1806 then _t != 0 will be normalized into a pred_chain:
1807 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1811 /* This is a helper function that stores a PRED into NORM_PREDS. */
1813 inline static void
1814 push_pred (pred_chain_union *norm_preds, pred_info pred)
1816 pred_chain pred_chain = vNULL;
1817 pred_chain.safe_push (pred);
1818 norm_preds->safe_push (pred_chain);
1821 /* A helper function that creates a predicate of the form
1822 OP != 0 and push it WORK_LIST. */
1824 inline static void
1825 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1826 hash_set<tree> *mark_set)
1828 if (mark_set->contains (op))
1829 return;
1830 mark_set->add (op);
1832 pred_info arg_pred;
1833 arg_pred.pred_lhs = op;
1834 arg_pred.pred_rhs = integer_zero_node;
1835 arg_pred.cond_code = NE_EXPR;
1836 arg_pred.invert = false;
1837 work_list->safe_push (arg_pred);
1840 /* A helper that generates a pred_info from a gimple assignment
1841 CMP_ASSIGN with comparison rhs. */
1843 static pred_info
1844 get_pred_info_from_cmp (gimple cmp_assign)
1846 pred_info n_pred;
1847 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
1848 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
1849 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
1850 n_pred.invert = false;
1851 return n_pred;
1854 /* Returns true if the PHI is a degenerated phi with
1855 all args with the same value (relop). In that case, *PRED
1856 will be updated to that value. */
1858 static bool
1859 is_degenerated_phi (gimple phi, pred_info *pred_p)
1861 int i, n;
1862 tree op0;
1863 gimple def0;
1864 pred_info pred0;
1866 n = gimple_phi_num_args (phi);
1867 op0 = gimple_phi_arg_def (phi, 0);
1869 if (TREE_CODE (op0) != SSA_NAME)
1870 return false;
1872 def0 = SSA_NAME_DEF_STMT (op0);
1873 if (gimple_code (def0) != GIMPLE_ASSIGN)
1874 return false;
1875 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0))
1876 != tcc_comparison)
1877 return false;
1878 pred0 = get_pred_info_from_cmp (def0);
1880 for (i = 1; i < n; ++i)
1882 gimple def;
1883 pred_info pred;
1884 tree op = gimple_phi_arg_def (phi, i);
1886 if (TREE_CODE (op) != SSA_NAME)
1887 return false;
1889 def = SSA_NAME_DEF_STMT (op);
1890 if (gimple_code (def) != GIMPLE_ASSIGN)
1891 return false;
1892 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def))
1893 != tcc_comparison)
1894 return false;
1895 pred = get_pred_info_from_cmp (def);
1896 if (!pred_equal_p (pred, pred0))
1897 return false;
1900 *pred_p = pred0;
1901 return true;
1904 /* Normalize one predicate PRED
1905 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1906 2) otherwise if PRED is of the form x != 0, follow x's definition
1907 and put normalized predicates into WORK_LIST. */
1909 static void
1910 normalize_one_pred_1 (pred_chain_union *norm_preds,
1911 pred_chain *norm_chain,
1912 pred_info pred,
1913 enum tree_code and_or_code,
1914 vec<pred_info, va_heap, vl_ptr> *work_list,
1915 hash_set<tree> *mark_set)
1917 if (!is_neq_zero_form_p (pred))
1919 if (and_or_code == BIT_IOR_EXPR)
1920 push_pred (norm_preds, pred);
1921 else
1922 norm_chain->safe_push (pred);
1923 return;
1926 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1928 if (gimple_code (def_stmt) == GIMPLE_PHI
1929 && is_degenerated_phi (def_stmt, &pred))
1930 work_list->safe_push (pred);
1931 else if (gimple_code (def_stmt) == GIMPLE_PHI
1932 && and_or_code == BIT_IOR_EXPR)
1934 int i, n;
1935 n = gimple_phi_num_args (def_stmt);
1937 /* If we see non zero constant, we should punt. The predicate
1938 * should be one guarding the phi edge. */
1939 for (i = 0; i < n; ++i)
1941 tree op = gimple_phi_arg_def (def_stmt, i);
1942 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1944 push_pred (norm_preds, pred);
1945 return;
1949 for (i = 0; i < n; ++i)
1951 tree op = gimple_phi_arg_def (def_stmt, i);
1952 if (integer_zerop (op))
1953 continue;
1955 push_to_worklist (op, work_list, mark_set);
1958 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1960 if (and_or_code == BIT_IOR_EXPR)
1961 push_pred (norm_preds, pred);
1962 else
1963 norm_chain->safe_push (pred);
1965 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
1967 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
1968 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
1970 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1971 == tcc_comparison)
1973 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1974 if (and_or_code == BIT_IOR_EXPR)
1975 push_pred (norm_preds, n_pred);
1976 else
1977 norm_chain->safe_push (n_pred);
1979 else
1981 if (and_or_code == BIT_IOR_EXPR)
1982 push_pred (norm_preds, pred);
1983 else
1984 norm_chain->safe_push (pred);
1988 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1990 static void
1991 normalize_one_pred (pred_chain_union *norm_preds,
1992 pred_info pred)
1994 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
1995 enum tree_code and_or_code = ERROR_MARK;
1996 pred_chain norm_chain = vNULL;
1998 if (!is_neq_zero_form_p (pred))
2000 push_pred (norm_preds, pred);
2001 return;
2004 gimple def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2005 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2006 and_or_code = gimple_assign_rhs_code (def_stmt);
2007 if (and_or_code != BIT_IOR_EXPR
2008 && and_or_code != BIT_AND_EXPR)
2010 if (TREE_CODE_CLASS (and_or_code)
2011 == tcc_comparison)
2013 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2014 push_pred (norm_preds, n_pred);
2016 else
2017 push_pred (norm_preds, pred);
2018 return;
2021 work_list.safe_push (pred);
2022 hash_set<tree> mark_set;
2024 while (!work_list.is_empty ())
2026 pred_info a_pred = work_list.pop ();
2027 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred,
2028 and_or_code, &work_list, &mark_set);
2030 if (and_or_code == BIT_AND_EXPR)
2031 norm_preds->safe_push (norm_chain);
2033 work_list.release ();
2036 static void
2037 normalize_one_pred_chain (pred_chain_union *norm_preds,
2038 pred_chain one_chain)
2040 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2041 hash_set<tree> mark_set;
2042 pred_chain norm_chain = vNULL;
2043 size_t i;
2045 for (i = 0; i < one_chain.length (); i++)
2047 work_list.safe_push (one_chain[i]);
2048 mark_set.add (one_chain[i].pred_lhs);
2051 while (!work_list.is_empty ())
2053 pred_info a_pred = work_list.pop ();
2054 normalize_one_pred_1 (0, &norm_chain, a_pred,
2055 BIT_AND_EXPR, &work_list, &mark_set);
2058 norm_preds->safe_push (norm_chain);
2059 work_list.release ();
2062 /* Normalize predicate chains PREDS and returns the normalized one. */
2064 static pred_chain_union
2065 normalize_preds (pred_chain_union preds, gimple use_or_def, bool is_use)
2067 pred_chain_union norm_preds = vNULL;
2068 size_t n = preds.length ();
2069 size_t i;
2071 if (dump_file && dump_flags & TDF_DETAILS)
2073 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2074 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2077 for (i = 0; i < n; i++)
2079 if (preds[i].length () != 1)
2080 normalize_one_pred_chain (&norm_preds, preds[i]);
2081 else
2083 normalize_one_pred (&norm_preds, preds[i][0]);
2084 preds[i].release ();
2088 if (dump_file)
2090 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2091 dump_predicates (use_or_def, norm_preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2094 preds.release ();
2095 return norm_preds;
2099 /* Computes the predicates that guard the use and checks
2100 if the incoming paths that have empty (or possibly
2101 empty) definition can be pruned/filtered. The function returns
2102 true if it can be determined that the use of PHI's def in
2103 USE_STMT is guarded with a predicate set not overlapping with
2104 predicate sets of all runtime paths that do not have a definition.
2105 Returns false if it is not or it can not be determined. USE_BB is
2106 the bb of the use (for phi operand use, the bb is not the bb of
2107 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2108 is a bit vector. If an operand of PHI is uninitialized, the
2109 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2110 set of phis being visted. */
2112 static bool
2113 is_use_properly_guarded (gimple use_stmt,
2114 basic_block use_bb,
2115 gphi *phi,
2116 unsigned uninit_opnds,
2117 hash_set<gphi *> *visited_phis)
2119 basic_block phi_bb;
2120 pred_chain_union preds = vNULL;
2121 pred_chain_union def_preds = vNULL;
2122 bool has_valid_preds = false;
2123 bool is_properly_guarded = false;
2125 if (visited_phis->add (phi))
2126 return false;
2128 phi_bb = gimple_bb (phi);
2130 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2131 return false;
2133 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2135 if (!has_valid_preds)
2137 destroy_predicate_vecs (preds);
2138 return false;
2141 /* Try to prune the dead incoming phi edges. */
2142 is_properly_guarded
2143 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2144 visited_phis);
2146 if (is_properly_guarded)
2148 destroy_predicate_vecs (preds);
2149 return true;
2152 has_valid_preds = find_def_preds (&def_preds, phi);
2154 if (!has_valid_preds)
2156 destroy_predicate_vecs (preds);
2157 destroy_predicate_vecs (def_preds);
2158 return false;
2161 simplify_preds (&preds, use_stmt, true);
2162 preds = normalize_preds (preds, use_stmt, true);
2164 simplify_preds (&def_preds, phi, false);
2165 def_preds = normalize_preds (def_preds, phi, false);
2167 is_properly_guarded = is_superset_of (def_preds, preds);
2169 destroy_predicate_vecs (preds);
2170 destroy_predicate_vecs (def_preds);
2171 return is_properly_guarded;
2174 /* Searches through all uses of a potentially
2175 uninitialized variable defined by PHI and returns a use
2176 statement if the use is not properly guarded. It returns
2177 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2178 holding the position(s) of uninit PHI operands. WORKLIST
2179 is the vector of candidate phis that may be updated by this
2180 function. ADDED_TO_WORKLIST is the pointer set tracking
2181 if the new phi is already in the worklist. */
2183 static gimple
2184 find_uninit_use (gphi *phi, unsigned uninit_opnds,
2185 vec<gphi *> *worklist,
2186 hash_set<gphi *> *added_to_worklist)
2188 tree phi_result;
2189 use_operand_p use_p;
2190 gimple use_stmt;
2191 imm_use_iterator iter;
2193 phi_result = gimple_phi_result (phi);
2195 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2197 basic_block use_bb;
2199 use_stmt = USE_STMT (use_p);
2200 if (is_gimple_debug (use_stmt))
2201 continue;
2203 if (gphi *use_phi = dyn_cast <gphi *> (use_stmt))
2204 use_bb = gimple_phi_arg_edge (use_phi,
2205 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2206 else
2207 use_bb = gimple_bb (use_stmt);
2209 hash_set<gphi *> visited_phis;
2210 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2211 &visited_phis))
2212 continue;
2214 if (dump_file && (dump_flags & TDF_DETAILS))
2216 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2217 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2219 /* Found one real use, return. */
2220 if (gimple_code (use_stmt) != GIMPLE_PHI)
2221 return use_stmt;
2223 /* Found a phi use that is not guarded,
2224 add the phi to the worklist. */
2225 if (!added_to_worklist->add (as_a <gphi *> (use_stmt)))
2227 if (dump_file && (dump_flags & TDF_DETAILS))
2229 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2230 print_gimple_stmt (dump_file, use_stmt, 0, 0);
2233 worklist->safe_push (as_a <gphi *> (use_stmt));
2234 possibly_undefined_names->add (phi_result);
2238 return NULL;
2241 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2242 and gives warning if there exists a runtime path from the entry to a
2243 use of the PHI def that does not contain a definition. In other words,
2244 the warning is on the real use. The more dead paths that can be pruned
2245 by the compiler, the fewer false positives the warning is. WORKLIST
2246 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2247 a pointer set tracking if the new phi is added to the worklist or not. */
2249 static void
2250 warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
2251 hash_set<gphi *> *added_to_worklist)
2253 unsigned uninit_opnds;
2254 gimple uninit_use_stmt = 0;
2255 tree uninit_op;
2256 int phiarg_index;
2257 location_t loc;
2259 /* Don't look at virtual operands. */
2260 if (virtual_operand_p (gimple_phi_result (phi)))
2261 return;
2263 uninit_opnds = compute_uninit_opnds_pos (phi);
2265 if (MASK_EMPTY (uninit_opnds))
2266 return;
2268 if (dump_file && (dump_flags & TDF_DETAILS))
2270 fprintf (dump_file, "[CHECK]: examining phi: ");
2271 print_gimple_stmt (dump_file, phi, 0, 0);
2274 /* Now check if we have any use of the value without proper guard. */
2275 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2276 worklist, added_to_worklist);
2278 /* All uses are properly guarded. */
2279 if (!uninit_use_stmt)
2280 return;
2282 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2283 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2284 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2285 return;
2286 if (gimple_phi_arg_has_location (phi, phiarg_index))
2287 loc = gimple_phi_arg_location (phi, phiarg_index);
2288 else
2289 loc = UNKNOWN_LOCATION;
2290 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2291 SSA_NAME_VAR (uninit_op),
2292 "%qD may be used uninitialized in this function",
2293 uninit_use_stmt, loc);
2297 static bool
2298 gate_warn_uninitialized (void)
2300 return warn_uninitialized || warn_maybe_uninitialized;
2303 namespace {
2305 const pass_data pass_data_late_warn_uninitialized =
2307 GIMPLE_PASS, /* type */
2308 "uninit", /* name */
2309 OPTGROUP_NONE, /* optinfo_flags */
2310 TV_NONE, /* tv_id */
2311 PROP_ssa, /* properties_required */
2312 0, /* properties_provided */
2313 0, /* properties_destroyed */
2314 0, /* todo_flags_start */
2315 0, /* todo_flags_finish */
2318 class pass_late_warn_uninitialized : public gimple_opt_pass
2320 public:
2321 pass_late_warn_uninitialized (gcc::context *ctxt)
2322 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2325 /* opt_pass methods: */
2326 opt_pass * clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2327 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2328 virtual unsigned int execute (function *);
2330 }; // class pass_late_warn_uninitialized
2332 unsigned int
2333 pass_late_warn_uninitialized::execute (function *fun)
2335 basic_block bb;
2336 gphi_iterator gsi;
2337 vec<gphi *> worklist = vNULL;
2339 calculate_dominance_info (CDI_DOMINATORS);
2340 calculate_dominance_info (CDI_POST_DOMINATORS);
2341 /* Re-do the plain uninitialized variable check, as optimization may have
2342 straightened control flow. Do this first so that we don't accidentally
2343 get a "may be" warning when we'd have seen an "is" warning later. */
2344 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2346 timevar_push (TV_TREE_UNINIT);
2348 possibly_undefined_names = new hash_set<tree>;
2349 hash_set<gphi *> added_to_worklist;
2351 /* Initialize worklist */
2352 FOR_EACH_BB_FN (bb, fun)
2353 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2355 gphi *phi = gsi.phi ();
2356 size_t n, i;
2358 n = gimple_phi_num_args (phi);
2360 /* Don't look at virtual operands. */
2361 if (virtual_operand_p (gimple_phi_result (phi)))
2362 continue;
2364 for (i = 0; i < n; ++i)
2366 tree op = gimple_phi_arg_def (phi, i);
2367 if (TREE_CODE (op) == SSA_NAME
2368 && uninit_undefined_value_p (op))
2370 worklist.safe_push (phi);
2371 added_to_worklist.add (phi);
2372 if (dump_file && (dump_flags & TDF_DETAILS))
2374 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2375 print_gimple_stmt (dump_file, phi, 0, 0);
2377 break;
2382 while (worklist.length () != 0)
2384 gphi *cur_phi = 0;
2385 cur_phi = worklist.pop ();
2386 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
2389 worklist.release ();
2390 delete possibly_undefined_names;
2391 possibly_undefined_names = NULL;
2392 free_dominance_info (CDI_POST_DOMINATORS);
2393 timevar_pop (TV_TREE_UNINIT);
2394 return 0;
2397 } // anon namespace
2399 gimple_opt_pass *
2400 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2402 return new pass_late_warn_uninitialized (ctxt);
2406 static unsigned int
2407 execute_early_warn_uninitialized (void)
2409 /* Currently, this pass runs always but
2410 execute_late_warn_uninitialized only runs with optimization. With
2411 optimization we want to warn about possible uninitialized as late
2412 as possible, thus don't do it here. However, without
2413 optimization we need to warn here about "may be uninitialized". */
2414 calculate_dominance_info (CDI_POST_DOMINATORS);
2416 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2418 /* Post-dominator information can not be reliably updated. Free it
2419 after the use. */
2421 free_dominance_info (CDI_POST_DOMINATORS);
2422 return 0;
2426 namespace {
2428 const pass_data pass_data_early_warn_uninitialized =
2430 GIMPLE_PASS, /* type */
2431 "*early_warn_uninitialized", /* name */
2432 OPTGROUP_NONE, /* optinfo_flags */
2433 TV_TREE_UNINIT, /* tv_id */
2434 PROP_ssa, /* properties_required */
2435 0, /* properties_provided */
2436 0, /* properties_destroyed */
2437 0, /* todo_flags_start */
2438 0, /* todo_flags_finish */
2441 class pass_early_warn_uninitialized : public gimple_opt_pass
2443 public:
2444 pass_early_warn_uninitialized (gcc::context *ctxt)
2445 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2448 /* opt_pass methods: */
2449 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2450 virtual unsigned int execute (function *)
2452 return execute_early_warn_uninitialized ();
2455 }; // class pass_early_warn_uninitialized
2457 } // anon namespace
2459 gimple_opt_pass *
2460 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2462 return new pass_early_warn_uninitialized (ctxt);