PR target/35491
[official-gcc/alias-decl.git] / gcc / tree-ssa-uninit.c
blob16adde3b070b304bdd51a1bef63a097c2521522b
1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software
3 Foundation, Inc.
4 Contributed by Xinliang David Li <davidxl@google.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "flags.h"
28 #include "tm_p.h"
29 #include "langhooks.h"
30 #include "basic-block.h"
31 #include "output.h"
32 #include "function.h"
33 #include "gimple-pretty-print.h"
34 #include "bitmap.h"
35 #include "pointer-set.h"
36 #include "tree-flow.h"
37 #include "gimple.h"
38 #include "tree-inline.h"
39 #include "timevar.h"
40 #include "hashtab.h"
41 #include "tree-dump.h"
42 #include "tree-pass.h"
43 #include "diagnostic-core.h"
44 #include "toplev.h"
45 #include "timevar.h"
47 /* This implements the pass that does predicate aware warning on uses of
48 possibly uninitialized variables. The pass first collects the set of
49 possibly uninitialized SSA names. For each such name, it walks through
50 all its immediate uses. For each immediate use, it rebuilds the condition
51 expression (the predicate) that guards the use. The predicate is then
52 examined to see if the variable is always defined under that same condition.
53 This is done either by pruning the unrealizable paths that lead to the
54 default definitions or by checking if the predicate set that guards the
55 defining paths is a superset of the use predicate. */
58 /* Pointer set of potentially undefined ssa names, i.e.,
59 ssa names that are defined by phi with operands that
60 are not defined or potentially undefined. */
61 static struct pointer_set_t *possibly_undefined_names = 0;
63 /* Bit mask handling macros. */
64 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
65 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
66 #define MASK_EMPTY(mask) (mask == 0)
68 /* Returns the first bit position (starting from LSB)
69 in mask that is non zero. Returns -1 if the mask is empty. */
70 static int
71 get_mask_first_set_bit (unsigned mask)
73 int pos = 0;
74 if (mask == 0)
75 return -1;
77 while ((mask & (1 << pos)) == 0)
78 pos++;
80 return pos;
82 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
85 /* Return true if T, an SSA_NAME, has an undefined value. */
87 bool
88 ssa_undefined_value_p (tree t)
90 tree var = SSA_NAME_VAR (t);
92 /* Parameters get their initial value from the function entry. */
93 if (TREE_CODE (var) == PARM_DECL)
94 return false;
96 /* When returning by reference the return address is actually a hidden
97 parameter. */
98 if (TREE_CODE (SSA_NAME_VAR (t)) == RESULT_DECL
99 && DECL_BY_REFERENCE (SSA_NAME_VAR (t)))
100 return false;
102 /* Hard register variables get their initial value from the ether. */
103 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
104 return false;
106 /* The value is undefined iff its definition statement is empty. */
107 return (gimple_nop_p (SSA_NAME_DEF_STMT (t))
108 || (possibly_undefined_names
109 && pointer_set_contains (possibly_undefined_names, t)));
112 /* Checks if the operand OPND of PHI is defined by
113 another phi with one operand defined by this PHI,
114 but the rest operands are all defined. If yes,
115 returns true to skip this this operand as being
116 redundant. Can be enhanced to be more general. */
118 static bool
119 can_skip_redundant_opnd (tree opnd, gimple phi)
121 gimple op_def;
122 tree phi_def;
123 int i, n;
125 phi_def = gimple_phi_result (phi);
126 op_def = SSA_NAME_DEF_STMT (opnd);
127 if (gimple_code (op_def) != GIMPLE_PHI)
128 return false;
129 n = gimple_phi_num_args (op_def);
130 for (i = 0; i < n; ++i)
132 tree op = gimple_phi_arg_def (op_def, i);
133 if (TREE_CODE (op) != SSA_NAME)
134 continue;
135 if (op != phi_def && ssa_undefined_value_p (op))
136 return false;
139 return true;
142 /* Returns a bit mask holding the positions of arguments in PHI
143 that have empty (or possibly empty) definitions. */
145 static unsigned
146 compute_uninit_opnds_pos (gimple phi)
148 size_t i, n;
149 unsigned uninit_opnds = 0;
151 n = gimple_phi_num_args (phi);
153 for (i = 0; i < n; ++i)
155 tree op = gimple_phi_arg_def (phi, i);
156 if (TREE_CODE (op) == SSA_NAME
157 && ssa_undefined_value_p (op)
158 && !can_skip_redundant_opnd (op, phi))
159 MASK_SET_BIT (uninit_opnds, i);
161 return uninit_opnds;
164 /* Find the immediate postdominator PDOM of the specified
165 basic block BLOCK. */
167 static inline basic_block
168 find_pdom (basic_block block)
170 if (block == EXIT_BLOCK_PTR)
171 return EXIT_BLOCK_PTR;
172 else
174 basic_block bb
175 = get_immediate_dominator (CDI_POST_DOMINATORS, block);
176 if (! bb)
177 return EXIT_BLOCK_PTR;
178 return bb;
182 /* Find the immediate DOM of the specified
183 basic block BLOCK. */
185 static inline basic_block
186 find_dom (basic_block block)
188 if (block == ENTRY_BLOCK_PTR)
189 return ENTRY_BLOCK_PTR;
190 else
192 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
193 if (! bb)
194 return ENTRY_BLOCK_PTR;
195 return bb;
199 /* Returns true if BB1 is postdominating BB2 and BB1 is
200 not a loop exit bb. The loop exit bb check is simple and does
201 not cover all cases. */
203 static bool
204 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
206 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
207 return false;
209 if (single_pred_p (bb1) && !single_succ_p (bb2))
210 return false;
212 return true;
215 /* Find the closest postdominator of a specified BB, which is control
216 equivalent to BB. */
218 static inline basic_block
219 find_control_equiv_block (basic_block bb)
221 basic_block pdom;
223 pdom = find_pdom (bb);
225 /* Skip the postdominating bb that is also loop exit. */
226 if (!is_non_loop_exit_postdominating (pdom, bb))
227 return NULL;
229 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
230 return pdom;
232 return NULL;
235 #define MAX_NUM_CHAINS 8
236 #define MAX_CHAIN_LEN 5
238 /* Computes the control dependence chains (paths of edges)
239 for DEP_BB up to the dominating basic block BB (the head node of a
240 chain should be dominated by it). CD_CHAINS is pointer to a
241 dynamic array holding the result chains. CUR_CD_CHAIN is the current
242 chain being computed. *NUM_CHAINS is total number of chains. The
243 function returns true if the information is successfully computed,
244 return false if there is no control dependence or not computed. */
246 static bool
247 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
248 VEC(edge, heap) **cd_chains,
249 size_t *num_chains,
250 VEC(edge, heap) **cur_cd_chain)
252 edge_iterator ei;
253 edge e;
254 size_t i;
255 bool found_cd_chain = false;
256 size_t cur_chain_len = 0;
258 if (EDGE_COUNT (bb->succs) < 2)
259 return false;
261 /* Could use a set instead. */
262 cur_chain_len = VEC_length (edge, *cur_cd_chain);
263 if (cur_chain_len > MAX_CHAIN_LEN)
264 return false;
266 for (i = 0; i < cur_chain_len; i++)
268 edge e = VEC_index (edge, *cur_cd_chain, i);
269 /* cycle detected. */
270 if (e->src == bb)
271 return false;
274 FOR_EACH_EDGE (e, ei, bb->succs)
276 basic_block cd_bb;
277 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
278 continue;
280 cd_bb = e->dest;
281 VEC_safe_push (edge, heap, *cur_cd_chain, e);
282 while (!is_non_loop_exit_postdominating (cd_bb, bb))
284 if (cd_bb == dep_bb)
286 /* Found a direct control dependence. */
287 if (*num_chains < MAX_NUM_CHAINS)
289 cd_chains[*num_chains]
290 = VEC_copy (edge, heap, *cur_cd_chain);
291 (*num_chains)++;
293 found_cd_chain = true;
294 /* check path from next edge. */
295 break;
298 /* Now check if DEP_BB is indirectly control dependent on BB. */
299 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
300 num_chains, cur_cd_chain))
302 found_cd_chain = true;
303 break;
306 cd_bb = find_pdom (cd_bb);
307 if (cd_bb == EXIT_BLOCK_PTR)
308 break;
310 VEC_pop (edge, *cur_cd_chain);
311 gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
313 gcc_assert (VEC_length (edge, *cur_cd_chain) == cur_chain_len);
315 return found_cd_chain;
318 typedef struct use_pred_info
320 gimple cond;
321 bool invert;
322 } *use_pred_info_t;
324 DEF_VEC_P(use_pred_info_t);
325 DEF_VEC_ALLOC_P(use_pred_info_t, heap);
328 /* Converts the chains of control dependence edges into a set of
329 predicates. A control dependence chain is represented by a vector
330 edges. DEP_CHAINS points to an array of dependence chains.
331 NUM_CHAINS is the size of the chain array. One edge in a dependence
332 chain is mapped to predicate expression represented by use_pred_info_t
333 type. One dependence chain is converted to a composite predicate that
334 is the result of AND operation of use_pred_info_t mapped to each edge.
335 A composite predicate is presented by a vector of use_pred_info_t. On
336 return, *PREDS points to the resulting array of composite predicates.
337 *NUM_PREDS is the number of composite predictes. */
339 static bool
340 convert_control_dep_chain_into_preds (VEC(edge, heap) **dep_chains,
341 size_t num_chains,
342 VEC(use_pred_info_t, heap) ***preds,
343 size_t *num_preds)
345 bool has_valid_pred = false;
346 size_t i, j;
347 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
348 return false;
350 /* Now convert CD chains into predicates */
351 has_valid_pred = true;
353 /* Now convert the control dep chain into a set
354 of predicates. */
355 *preds = XCNEWVEC (VEC(use_pred_info_t, heap) *,
356 num_chains);
357 *num_preds = num_chains;
359 for (i = 0; i < num_chains; i++)
361 VEC(edge, heap) *one_cd_chain = dep_chains[i];
362 for (j = 0; j < VEC_length (edge, one_cd_chain); j++)
364 gimple cond_stmt;
365 gimple_stmt_iterator gsi;
366 basic_block guard_bb;
367 use_pred_info_t one_pred;
368 edge e;
370 e = VEC_index (edge, one_cd_chain, j);
371 guard_bb = e->src;
372 gsi = gsi_last_bb (guard_bb);
373 if (gsi_end_p (gsi))
375 has_valid_pred = false;
376 break;
378 cond_stmt = gsi_stmt (gsi);
379 if (gimple_code (cond_stmt) == GIMPLE_CALL
380 && EDGE_COUNT (e->src->succs) >= 2)
382 /* Ignore EH edge. Can add assertion
383 on the other edge's flag. */
384 continue;
386 /* Skip if there is essentially one succesor. */
387 if (EDGE_COUNT (e->src->succs) == 2)
389 edge e1;
390 edge_iterator ei1;
391 bool skip = false;
393 FOR_EACH_EDGE (e1, ei1, e->src->succs)
395 if (EDGE_COUNT (e1->dest->succs) == 0)
397 skip = true;
398 break;
401 if (skip)
402 continue;
404 if (gimple_code (cond_stmt) != GIMPLE_COND)
406 has_valid_pred = false;
407 break;
409 one_pred = XNEW (struct use_pred_info);
410 one_pred->cond = cond_stmt;
411 one_pred->invert = !!(e->flags & EDGE_FALSE_VALUE);
412 VEC_safe_push (use_pred_info_t, heap, (*preds)[i], one_pred);
415 if (!has_valid_pred)
416 break;
418 return has_valid_pred;
421 /* Computes all control dependence chains for USE_BB. The control
422 dependence chains are then converted to an array of composite
423 predicates pointed to by PREDS. PHI_BB is the basic block of
424 the phi whose result is used in USE_BB. */
426 static bool
427 find_predicates (VEC(use_pred_info_t, heap) ***preds,
428 size_t *num_preds,
429 basic_block phi_bb,
430 basic_block use_bb)
432 size_t num_chains = 0, i;
433 VEC(edge, heap) **dep_chains = 0;
434 VEC(edge, heap) *cur_chain = 0;
435 bool has_valid_pred = false;
436 basic_block cd_root = 0;
438 dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
440 /* First find the closest bb that is control equivalent to PHI_BB
441 that also dominates USE_BB. */
442 cd_root = phi_bb;
443 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
445 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
446 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
447 cd_root = ctrl_eq_bb;
448 else
449 break;
452 compute_control_dep_chain (cd_root, use_bb,
453 dep_chains, &num_chains,
454 &cur_chain);
456 has_valid_pred
457 = convert_control_dep_chain_into_preds (dep_chains,
458 num_chains,
459 preds,
460 num_preds);
461 /* Free individual chain */
462 VEC_free (edge, heap, cur_chain);
463 for (i = 0; i < num_chains; i++)
464 VEC_free (edge, heap, dep_chains[i]);
465 free (dep_chains);
466 return has_valid_pred;
469 /* Computes the set of incoming edges of PHI that have non empty
470 definitions of a phi chain. The collection will be done
471 recursively on operands that are defined by phis. CD_ROOT
472 is the control dependence root. *EDGES holds the result, and
473 VISITED_PHIS is a pointer set for detecting cycles. */
475 static void
476 collect_phi_def_edges (gimple phi, basic_block cd_root,
477 VEC(edge, heap) **edges,
478 struct pointer_set_t *visited_phis)
480 size_t i, n;
481 edge opnd_edge;
482 tree opnd;
484 if (pointer_set_insert (visited_phis, phi))
485 return;
487 n = gimple_phi_num_args (phi);
488 for (i = 0; i < n; i++)
490 opnd_edge = gimple_phi_arg_edge (phi, i);
491 opnd = gimple_phi_arg_def (phi, i);
493 if (TREE_CODE (opnd) != SSA_NAME)
495 if (dump_file && (dump_flags & TDF_DETAILS))
497 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
498 print_gimple_stmt (dump_file, phi, 0, 0);
500 VEC_safe_push (edge, heap, *edges, opnd_edge);
502 else
504 gimple def = SSA_NAME_DEF_STMT (opnd);
506 if (gimple_code (def) == GIMPLE_PHI
507 && dominated_by_p (CDI_DOMINATORS,
508 gimple_bb (def), cd_root))
509 collect_phi_def_edges (def, cd_root, edges,
510 visited_phis);
511 else if (!ssa_undefined_value_p (opnd))
513 if (dump_file && (dump_flags & TDF_DETAILS))
515 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int)i);
516 print_gimple_stmt (dump_file, phi, 0, 0);
518 VEC_safe_push (edge, heap, *edges, opnd_edge);
524 /* For each use edge of PHI, computes all control dependence chains.
525 The control dependence chains are then converted to an array of
526 composite predicates pointed to by PREDS. */
528 static bool
529 find_def_preds (VEC(use_pred_info_t, heap) ***preds,
530 size_t *num_preds, gimple phi)
532 size_t num_chains = 0, i, n;
533 VEC(edge, heap) **dep_chains = 0;
534 VEC(edge, heap) *cur_chain = 0;
535 VEC(edge, heap) *def_edges = 0;
536 bool has_valid_pred = false;
537 basic_block phi_bb, cd_root = 0;
538 struct pointer_set_t *visited_phis;
540 dep_chains = XCNEWVEC (VEC(edge, heap) *, MAX_NUM_CHAINS);
542 phi_bb = gimple_bb (phi);
543 /* First find the closest dominating bb to be
544 the control dependence root */
545 cd_root = find_dom (phi_bb);
546 if (!cd_root)
547 return false;
549 visited_phis = pointer_set_create ();
550 collect_phi_def_edges (phi, cd_root, &def_edges, visited_phis);
551 pointer_set_destroy (visited_phis);
553 n = VEC_length (edge, def_edges);
554 if (n == 0)
555 return false;
557 for (i = 0; i < n; i++)
559 size_t prev_nc, j;
560 edge opnd_edge;
562 opnd_edge = VEC_index (edge, def_edges, i);
563 prev_nc = num_chains;
564 compute_control_dep_chain (cd_root, opnd_edge->src,
565 dep_chains, &num_chains,
566 &cur_chain);
567 /* Free individual chain */
568 VEC_free (edge, heap, cur_chain);
569 cur_chain = 0;
571 /* Now update the newly added chains with
572 the phi operand edge: */
573 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
575 if (prev_nc == num_chains
576 && num_chains < MAX_NUM_CHAINS)
577 num_chains++;
578 for (j = prev_nc; j < num_chains; j++)
580 VEC_safe_push (edge, heap, dep_chains[j], opnd_edge);
585 has_valid_pred
586 = convert_control_dep_chain_into_preds (dep_chains,
587 num_chains,
588 preds,
589 num_preds);
590 for (i = 0; i < num_chains; i++)
591 VEC_free (edge, heap, dep_chains[i]);
592 free (dep_chains);
593 return has_valid_pred;
596 /* Dumps the predicates (PREDS) for USESTMT. */
598 static void
599 dump_predicates (gimple usestmt, size_t num_preds,
600 VEC(use_pred_info_t, heap) **preds,
601 const char* msg)
603 size_t i, j;
604 VEC(use_pred_info_t, heap) *one_pred_chain;
605 fprintf (dump_file, msg);
606 print_gimple_stmt (dump_file, usestmt, 0, 0);
607 fprintf (dump_file, "is guarded by :\n");
608 /* do some dumping here: */
609 for (i = 0; i < num_preds; i++)
611 size_t np;
613 one_pred_chain = preds[i];
614 np = VEC_length (use_pred_info_t, one_pred_chain);
616 for (j = 0; j < np; j++)
618 use_pred_info_t one_pred
619 = VEC_index (use_pred_info_t, one_pred_chain, j);
620 if (one_pred->invert)
621 fprintf (dump_file, " (.NOT.) ");
622 print_gimple_stmt (dump_file, one_pred->cond, 0, 0);
623 if (j < np - 1)
624 fprintf (dump_file, "(.AND.)\n");
626 if (i < num_preds - 1)
627 fprintf (dump_file, "(.OR.)\n");
631 /* Destroys the predicate set *PREDS. */
633 static void
634 destroy_predicate_vecs (size_t n,
635 VEC(use_pred_info_t, heap) ** preds)
637 size_t i, j;
638 for (i = 0; i < n; i++)
640 for (j = 0; j < VEC_length (use_pred_info_t, preds[i]); j++)
641 free (VEC_index (use_pred_info_t, preds[i], j));
642 VEC_free (use_pred_info_t, heap, preds[i]);
644 free (preds);
648 /* Computes the 'normalized' conditional code with operand
649 swapping and condition inversion. */
651 static enum tree_code
652 get_cmp_code (enum tree_code orig_cmp_code,
653 bool swap_cond, bool invert)
655 enum tree_code tc = orig_cmp_code;
657 if (swap_cond)
658 tc = swap_tree_comparison (orig_cmp_code);
659 if (invert)
660 tc = invert_tree_comparison (tc, false);
662 switch (tc)
664 case LT_EXPR:
665 case LE_EXPR:
666 case GT_EXPR:
667 case GE_EXPR:
668 case EQ_EXPR:
669 case NE_EXPR:
670 break;
671 default:
672 return ERROR_MARK;
674 return tc;
677 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
678 all values in the range satisfies (x CMPC BOUNDARY) == true. */
680 static bool
681 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
683 bool inverted = false;
684 bool is_unsigned;
685 bool result;
687 /* Only handle integer constant here. */
688 if (TREE_CODE (val) != INTEGER_CST
689 || TREE_CODE (boundary) != INTEGER_CST)
690 return true;
692 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
694 if (cmpc == GE_EXPR || cmpc == GT_EXPR
695 || cmpc == NE_EXPR)
697 cmpc = invert_tree_comparison (cmpc, false);
698 inverted = true;
701 if (is_unsigned)
703 if (cmpc == EQ_EXPR)
704 result = tree_int_cst_equal (val, boundary);
705 else if (cmpc == LT_EXPR)
706 result = INT_CST_LT_UNSIGNED (val, boundary);
707 else
709 gcc_assert (cmpc == LE_EXPR);
710 result = (tree_int_cst_equal (val, boundary)
711 || INT_CST_LT_UNSIGNED (val, boundary));
714 else
716 if (cmpc == EQ_EXPR)
717 result = tree_int_cst_equal (val, boundary);
718 else if (cmpc == LT_EXPR)
719 result = INT_CST_LT (val, boundary);
720 else
722 gcc_assert (cmpc == LE_EXPR);
723 result = (tree_int_cst_equal (val, boundary)
724 || INT_CST_LT (val, boundary));
728 if (inverted)
729 result ^= 1;
731 return result;
734 /* Returns true if PRED is common among all the predicate
735 chains (PREDS) (and therefore can be factored out).
736 NUM_PRED_CHAIN is the size of array PREDS. */
738 static bool
739 find_matching_predicate_in_rest_chains (use_pred_info_t pred,
740 VEC(use_pred_info_t, heap) **preds,
741 size_t num_pred_chains)
743 size_t i, j, n;
745 /* trival case */
746 if (num_pred_chains == 1)
747 return true;
749 for (i = 1; i < num_pred_chains; i++)
751 bool found = false;
752 VEC(use_pred_info_t, heap) *one_chain = preds[i];
753 n = VEC_length (use_pred_info_t, one_chain);
754 for (j = 0; j < n; j++)
756 use_pred_info_t pred2
757 = VEC_index (use_pred_info_t, one_chain, j);
758 /* can relax the condition comparison to not
759 use address comparison. However, the most common
760 case is that multiple control dependent paths share
761 a common path prefix, so address comparison should
762 be ok. */
764 if (pred2->cond == pred->cond
765 && pred2->invert == pred->invert)
767 found = true;
768 break;
771 if (!found)
772 return false;
774 return true;
777 /* Forward declaration. */
778 static bool
779 is_use_properly_guarded (gimple use_stmt,
780 basic_block use_bb,
781 gimple phi,
782 unsigned uninit_opnds,
783 struct pointer_set_t *visited_phis);
785 /* A helper function that determines if the predicate set
786 of the use is not overlapping with that of the uninit paths.
787 The most common senario of guarded use is in Example 1:
788 Example 1:
789 if (some_cond)
791 x = ...;
792 flag = true;
795 ... some code ...
797 if (flag)
798 use (x);
800 The real world examples are usually more complicated, but similar
801 and usually result from inlining:
803 bool init_func (int * x)
805 if (some_cond)
806 return false;
807 *x = ..
808 return true;
811 void foo(..)
813 int x;
815 if (!init_func(&x))
816 return;
818 .. some_code ...
819 use (x);
822 Another possible use scenario is in the following trivial example:
824 Example 2:
825 if (n > 0)
826 x = 1;
828 if (n > 0)
830 if (m < 2)
831 .. = x;
834 Predicate analysis needs to compute the composite predicate:
836 1) 'x' use predicate: (n > 0) .AND. (m < 2)
837 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
838 (the predicate chain for phi operand defs can be computed
839 starting from a bb that is control equivalent to the phi's
840 bb and is dominating the operand def.)
842 and check overlapping:
843 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
844 <==> false
846 This implementation provides framework that can handle
847 scenarios. (Note that many simple cases are handled properly
848 without the predicate analysis -- this is due to jump threading
849 transformation which eliminates the merge point thus makes
850 path sensitive analysis unnecessary.)
852 NUM_PREDS is the number is the number predicate chains, PREDS is
853 the array of chains, PHI is the phi node whose incoming (undefined)
854 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
855 uninit operand positions. VISITED_PHIS is the pointer set of phi
856 stmts being checked. */
859 static bool
860 use_pred_not_overlap_with_undef_path_pred (
861 size_t num_preds,
862 VEC(use_pred_info_t, heap) **preds,
863 gimple phi, unsigned uninit_opnds,
864 struct pointer_set_t *visited_phis)
866 unsigned int i, n;
867 gimple flag_def = 0;
868 tree boundary_cst = 0;
869 enum tree_code cmp_code;
870 bool swap_cond = false;
871 bool invert = false;
872 VEC(use_pred_info_t, heap) *the_pred_chain;
874 gcc_assert (num_preds > 0);
875 /* Find within the common prefix of multiple predicate chains
876 a predicate that is a comparison of a flag variable against
877 a constant. */
878 the_pred_chain = preds[0];
879 n = VEC_length (use_pred_info_t, the_pred_chain);
880 for (i = 0; i < n; i++)
882 gimple cond;
883 tree cond_lhs, cond_rhs, flag = 0;
885 use_pred_info_t the_pred
886 = VEC_index (use_pred_info_t, the_pred_chain, i);
888 cond = the_pred->cond;
889 invert = the_pred->invert;
890 cond_lhs = gimple_cond_lhs (cond);
891 cond_rhs = gimple_cond_rhs (cond);
892 cmp_code = gimple_cond_code (cond);
894 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
895 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
897 boundary_cst = cond_rhs;
898 flag = cond_lhs;
900 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
901 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
903 boundary_cst = cond_lhs;
904 flag = cond_rhs;
905 swap_cond = true;
908 if (!flag)
909 continue;
911 flag_def = SSA_NAME_DEF_STMT (flag);
913 if (!flag_def)
914 continue;
916 if ((gimple_code (flag_def) == GIMPLE_PHI)
917 && (gimple_bb (flag_def) == gimple_bb (phi))
918 && find_matching_predicate_in_rest_chains (
919 the_pred, preds, num_preds))
920 break;
922 flag_def = 0;
925 if (!flag_def)
926 return false;
928 /* Now check all the uninit incoming edge has a constant flag value
929 that is in conflict with the use guard/predicate. */
930 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
932 if (cmp_code == ERROR_MARK)
933 return false;
935 for (i = 0; i < sizeof (unsigned); i++)
937 tree flag_arg;
939 if (!MASK_TEST_BIT (uninit_opnds, i))
940 continue;
942 flag_arg = gimple_phi_arg_def (flag_def, i);
943 if (!is_gimple_constant (flag_arg))
944 return false;
946 /* Now check if the constant is in the guarded range. */
947 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
949 tree opnd;
950 gimple opnd_def;
952 /* Now that we know that this undefined edge is not
953 pruned. If the operand is defined by another phi,
954 we can further prune the incoming edges of that
955 phi by checking the predicates of this operands. */
957 opnd = gimple_phi_arg_def (phi, i);
958 opnd_def = SSA_NAME_DEF_STMT (opnd);
959 if (gimple_code (opnd_def) == GIMPLE_PHI)
961 edge opnd_edge;
962 unsigned uninit_opnds2
963 = compute_uninit_opnds_pos (opnd_def);
964 gcc_assert (!MASK_EMPTY (uninit_opnds2));
965 opnd_edge = gimple_phi_arg_edge (phi, i);
966 if (!is_use_properly_guarded (phi,
967 opnd_edge->src,
968 opnd_def,
969 uninit_opnds2,
970 visited_phis))
971 return false;
973 else
974 return false;
978 return true;
981 /* Returns true if TC is AND or OR */
983 static inline bool
984 is_and_or_or (enum tree_code tc, tree typ)
986 return (tc == TRUTH_AND_EXPR
987 || tc == TRUTH_OR_EXPR
988 || tc == BIT_IOR_EXPR
989 || (tc == BIT_AND_EXPR
990 && (typ == 0 || TREE_CODE (typ) == BOOLEAN_TYPE)));
993 typedef struct norm_cond
995 VEC(gimple, heap) *conds;
996 enum tree_code cond_code;
997 bool invert;
998 } *norm_cond_t;
1001 /* Normalizes gimple condition COND. The normalization follows
1002 UD chains to form larger condition expression trees. NORM_COND
1003 holds the normalized result. COND_CODE is the logical opcode
1004 (AND or OR) of the normalized tree. */
1006 static void
1007 normalize_cond_1 (gimple cond,
1008 norm_cond_t norm_cond,
1009 enum tree_code cond_code)
1011 enum gimple_code gc;
1012 enum tree_code cur_cond_code;
1013 tree rhs1, rhs2;
1015 gc = gimple_code (cond);
1016 if (gc != GIMPLE_ASSIGN)
1018 VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1019 return;
1022 cur_cond_code = gimple_assign_rhs_code (cond);
1023 rhs1 = gimple_assign_rhs1 (cond);
1024 rhs2 = gimple_assign_rhs2 (cond);
1025 if (cur_cond_code == NE_EXPR)
1027 if (integer_zerop (rhs2)
1028 && (TREE_CODE (rhs1) == SSA_NAME))
1029 normalize_cond_1 (
1030 SSA_NAME_DEF_STMT (rhs1),
1031 norm_cond, cond_code);
1032 else if (integer_zerop (rhs1)
1033 && (TREE_CODE (rhs2) == SSA_NAME))
1034 normalize_cond_1 (
1035 SSA_NAME_DEF_STMT (rhs2),
1036 norm_cond, cond_code);
1037 else
1038 VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1040 return;
1043 if (is_and_or_or (cur_cond_code, TREE_TYPE (rhs1))
1044 && (cond_code == cur_cond_code || cond_code == ERROR_MARK)
1045 && (TREE_CODE (rhs1) == SSA_NAME && TREE_CODE (rhs2) == SSA_NAME))
1047 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1),
1048 norm_cond, cur_cond_code);
1049 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2),
1050 norm_cond, cur_cond_code);
1051 norm_cond->cond_code = cur_cond_code;
1053 else
1054 VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1057 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1058 if COND needs to be inverted or not. */
1060 static void
1061 normalize_cond (gimple cond, norm_cond_t norm_cond, bool invert)
1063 enum tree_code cond_code;
1065 norm_cond->cond_code = ERROR_MARK;
1066 norm_cond->invert = false;
1067 norm_cond->conds = NULL;
1068 gcc_assert (gimple_code (cond) == GIMPLE_COND);
1069 cond_code = gimple_cond_code (cond);
1070 if (invert)
1071 cond_code = invert_tree_comparison (cond_code, false);
1073 if (cond_code == NE_EXPR)
1075 if (integer_zerop (gimple_cond_rhs (cond))
1076 && (TREE_CODE (gimple_cond_lhs (cond)) == SSA_NAME))
1077 normalize_cond_1 (
1078 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond)),
1079 norm_cond, ERROR_MARK);
1080 else if (integer_zerop (gimple_cond_lhs (cond))
1081 && (TREE_CODE (gimple_cond_rhs (cond)) == SSA_NAME))
1082 normalize_cond_1 (
1083 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond)),
1084 norm_cond, ERROR_MARK);
1085 else
1087 VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1088 norm_cond->invert = invert;
1091 else
1093 VEC_safe_push (gimple, heap, norm_cond->conds, cond);
1094 norm_cond->invert = invert;
1097 gcc_assert (VEC_length (gimple, norm_cond->conds) == 1
1098 || is_and_or_or (norm_cond->cond_code, NULL));
1101 /* Returns true if the domain for condition COND1 is a subset of
1102 COND2. REVERSE is a flag. when it is true the function checks
1103 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1104 to indicate if COND1 and COND2 need to be inverted or not. */
1106 static bool
1107 is_gcond_subset_of (gimple cond1, bool invert1,
1108 gimple cond2, bool invert2,
1109 bool reverse)
1111 enum gimple_code gc1, gc2;
1112 enum tree_code cond1_code, cond2_code;
1113 gimple tmp;
1114 tree cond1_lhs, cond1_rhs, cond2_lhs, cond2_rhs;
1116 /* Take the short cut. */
1117 if (cond1 == cond2)
1118 return true;
1120 if (reverse)
1122 tmp = cond1;
1123 cond1 = cond2;
1124 cond2 = tmp;
1127 gc1 = gimple_code (cond1);
1128 gc2 = gimple_code (cond2);
1130 if ((gc1 != GIMPLE_ASSIGN && gc1 != GIMPLE_COND)
1131 || (gc2 != GIMPLE_ASSIGN && gc2 != GIMPLE_COND))
1132 return cond1 == cond2;
1134 cond1_code = ((gc1 == GIMPLE_ASSIGN)
1135 ? gimple_assign_rhs_code (cond1)
1136 : gimple_cond_code (cond1));
1138 cond2_code = ((gc2 == GIMPLE_ASSIGN)
1139 ? gimple_assign_rhs_code (cond2)
1140 : gimple_cond_code (cond2));
1142 if (TREE_CODE_CLASS (cond1_code) != tcc_comparison
1143 || TREE_CODE_CLASS (cond2_code) != tcc_comparison)
1144 return false;
1146 if (invert1)
1147 cond1_code = invert_tree_comparison (cond1_code, false);
1148 if (invert2)
1149 cond2_code = invert_tree_comparison (cond2_code, false);
1151 cond1_lhs = ((gc1 == GIMPLE_ASSIGN)
1152 ? gimple_assign_rhs1 (cond1)
1153 : gimple_cond_lhs (cond1));
1154 cond1_rhs = ((gc1 == GIMPLE_ASSIGN)
1155 ? gimple_assign_rhs2 (cond1)
1156 : gimple_cond_rhs (cond1));
1157 cond2_lhs = ((gc2 == GIMPLE_ASSIGN)
1158 ? gimple_assign_rhs1 (cond2)
1159 : gimple_cond_lhs (cond2));
1160 cond2_rhs = ((gc2 == GIMPLE_ASSIGN)
1161 ? gimple_assign_rhs2 (cond2)
1162 : gimple_cond_rhs (cond2));
1164 /* Assuming const operands have been swapped to the
1165 rhs at this point of the analysis. */
1167 if (cond1_lhs != cond2_lhs)
1168 return false;
1170 if (!is_gimple_constant (cond1_rhs)
1171 || TREE_CODE (cond1_rhs) != INTEGER_CST)
1172 return (cond1_rhs == cond2_rhs);
1174 if (!is_gimple_constant (cond2_rhs)
1175 || TREE_CODE (cond2_rhs) != INTEGER_CST)
1176 return (cond1_rhs == cond2_rhs);
1178 if (cond1_code == EQ_EXPR)
1179 return is_value_included_in (cond1_rhs,
1180 cond2_rhs, cond2_code);
1181 if (cond1_code == NE_EXPR || cond2_code == EQ_EXPR)
1182 return ((cond2_code == cond1_code)
1183 && tree_int_cst_equal (cond1_rhs, cond2_rhs));
1185 if (((cond1_code == GE_EXPR || cond1_code == GT_EXPR)
1186 && (cond2_code == LE_EXPR || cond2_code == LT_EXPR))
1187 || ((cond1_code == LE_EXPR || cond1_code == LT_EXPR)
1188 && (cond2_code == GE_EXPR || cond2_code == GT_EXPR)))
1189 return false;
1191 if (cond1_code != GE_EXPR && cond1_code != GT_EXPR
1192 && cond1_code != LE_EXPR && cond1_code != LT_EXPR)
1193 return false;
1195 if (cond1_code == GT_EXPR)
1197 cond1_code = GE_EXPR;
1198 cond1_rhs = fold_binary (PLUS_EXPR, TREE_TYPE (cond1_rhs),
1199 cond1_rhs,
1200 fold_convert (TREE_TYPE (cond1_rhs),
1201 integer_one_node));
1203 else if (cond1_code == LT_EXPR)
1205 cond1_code = LE_EXPR;
1206 cond1_rhs = fold_binary (MINUS_EXPR, TREE_TYPE (cond1_rhs),
1207 cond1_rhs,
1208 fold_convert (TREE_TYPE (cond1_rhs),
1209 integer_one_node));
1212 if (!cond1_rhs)
1213 return false;
1215 gcc_assert (cond1_code == GE_EXPR || cond1_code == LE_EXPR);
1217 if (cond2_code == GE_EXPR || cond2_code == GT_EXPR ||
1218 cond2_code == LE_EXPR || cond2_code == LT_EXPR)
1219 return is_value_included_in (cond1_rhs,
1220 cond2_rhs, cond2_code);
1221 else if (cond2_code == NE_EXPR)
1222 return
1223 (is_value_included_in (cond1_rhs,
1224 cond2_rhs, cond2_code)
1225 && !is_value_included_in (cond2_rhs,
1226 cond1_rhs, cond1_code));
1227 return false;
1230 /* Returns true if the domain of the condition expression
1231 in COND is a subset of any of the sub-conditions
1232 of the normalized condtion NORM_COND. INVERT is a flag
1233 to indicate of the COND needs to be inverted.
1234 REVERSE is a flag. When it is true, the check is reversed --
1235 it returns true if COND is a superset of any of the subconditions
1236 of NORM_COND. */
1238 static bool
1239 is_subset_of_any (gimple cond, bool invert,
1240 norm_cond_t norm_cond, bool reverse)
1242 size_t i;
1243 size_t len = VEC_length (gimple, norm_cond->conds);
1245 for (i = 0; i < len; i++)
1247 if (is_gcond_subset_of (cond, invert,
1248 VEC_index (gimple, norm_cond->conds, i),
1249 false, reverse))
1250 return true;
1252 return false;
1255 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1256 expressions (formed by following UD chains not control
1257 dependence chains). The function returns true of domain
1258 of and expression NORM_COND1 is a subset of NORM_COND2's.
1259 The implementation is conservative, and it returns false if
1260 it the inclusion relationship may not hold. */
1262 static bool
1263 is_or_set_subset_of (norm_cond_t norm_cond1,
1264 norm_cond_t norm_cond2)
1266 size_t i;
1267 size_t len = VEC_length (gimple, norm_cond1->conds);
1269 for (i = 0; i < len; i++)
1271 if (!is_subset_of_any (VEC_index (gimple, norm_cond1->conds, i),
1272 false, norm_cond2, false))
1273 return false;
1275 return true;
1278 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1279 expressions (formed by following UD chains not control
1280 dependence chains). The function returns true of domain
1281 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1283 static bool
1284 is_and_set_subset_of (norm_cond_t norm_cond1,
1285 norm_cond_t norm_cond2)
1287 size_t i;
1288 size_t len = VEC_length (gimple, norm_cond2->conds);
1290 for (i = 0; i < len; i++)
1292 if (!is_subset_of_any (VEC_index (gimple, norm_cond2->conds, i),
1293 false, norm_cond1, true))
1294 return false;
1296 return true;
1299 /* Returns true of the domain if NORM_COND1 is a subset
1300 of that of NORM_COND2. Returns false if it can not be
1301 proved to be so. */
1303 static bool
1304 is_norm_cond_subset_of (norm_cond_t norm_cond1,
1305 norm_cond_t norm_cond2)
1307 size_t i;
1308 enum tree_code code1, code2;
1310 code1 = norm_cond1->cond_code;
1311 code2 = norm_cond2->cond_code;
1313 if (code1 == TRUTH_AND_EXPR || code1 == BIT_AND_EXPR)
1315 /* Both conditions are AND expressions. */
1316 if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
1317 return is_and_set_subset_of (norm_cond1, norm_cond2);
1318 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1319 expression. In this case, returns true if any subexpression
1320 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1321 else if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
1323 size_t len1;
1324 len1 = VEC_length (gimple, norm_cond1->conds);
1325 for (i = 0; i < len1; i++)
1327 gimple cond1 = VEC_index (gimple, norm_cond1->conds, i);
1328 if (is_subset_of_any (cond1, false, norm_cond2, false))
1329 return true;
1331 return false;
1333 else
1335 gcc_assert (code2 == ERROR_MARK);
1336 gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
1337 return is_subset_of_any (VEC_index (gimple, norm_cond2->conds, 0),
1338 norm_cond2->invert, norm_cond1, true);
1341 /* NORM_COND1 is an OR expression */
1342 else if (code1 == TRUTH_OR_EXPR || code1 == BIT_IOR_EXPR)
1344 if (code2 != code1)
1345 return false;
1347 return is_or_set_subset_of (norm_cond1, norm_cond2);
1349 else
1351 gcc_assert (code1 == ERROR_MARK);
1352 gcc_assert (VEC_length (gimple, norm_cond1->conds) == 1);
1353 /* Conservatively returns false if NORM_COND1 is non-decomposible
1354 and NORM_COND2 is an AND expression. */
1355 if (code2 == TRUTH_AND_EXPR || code2 == BIT_AND_EXPR)
1356 return false;
1358 if (code2 == TRUTH_OR_EXPR || code2 == BIT_IOR_EXPR)
1359 return is_subset_of_any (VEC_index (gimple, norm_cond1->conds, 0),
1360 norm_cond1->invert, norm_cond2, false);
1362 gcc_assert (code2 == ERROR_MARK);
1363 gcc_assert (VEC_length (gimple, norm_cond2->conds) == 1);
1364 return is_gcond_subset_of (VEC_index (gimple, norm_cond1->conds, 0),
1365 norm_cond1->invert,
1366 VEC_index (gimple, norm_cond2->conds, 0),
1367 norm_cond2->invert, false);
1371 /* Returns true of the domain of single predicate expression
1372 EXPR1 is a subset of that of EXPR2. Returns false if it
1373 can not be proved. */
1375 static bool
1376 is_pred_expr_subset_of (use_pred_info_t expr1,
1377 use_pred_info_t expr2)
1379 gimple cond1, cond2;
1380 enum tree_code code1, code2;
1381 struct norm_cond norm_cond1, norm_cond2;
1382 bool is_subset = false;
1384 cond1 = expr1->cond;
1385 cond2 = expr2->cond;
1386 code1 = gimple_cond_code (cond1);
1387 code2 = gimple_cond_code (cond2);
1389 if (expr1->invert)
1390 code1 = invert_tree_comparison (code1, false);
1391 if (expr2->invert)
1392 code2 = invert_tree_comparison (code2, false);
1394 /* Fast path -- match exactly */
1395 if ((gimple_cond_lhs (cond1) == gimple_cond_lhs (cond2))
1396 && (gimple_cond_rhs (cond1) == gimple_cond_rhs (cond2))
1397 && (code1 == code2))
1398 return true;
1400 /* Normalize conditions. To keep NE_EXPR, do not invert
1401 with both need inversion. */
1402 normalize_cond (cond1, &norm_cond1, (expr1->invert));
1403 normalize_cond (cond2, &norm_cond2, (expr2->invert));
1405 is_subset = is_norm_cond_subset_of (&norm_cond1, &norm_cond2);
1407 /* Free memory */
1408 VEC_free (gimple, heap, norm_cond1.conds);
1409 VEC_free (gimple, heap, norm_cond2.conds);
1410 return is_subset ;
1413 /* Returns true if the domain of PRED1 is a subset
1414 of that of PRED2. Returns false if it can not be proved so. */
1416 static bool
1417 is_pred_chain_subset_of (VEC(use_pred_info_t, heap) *pred1,
1418 VEC(use_pred_info_t, heap) *pred2)
1420 size_t np1, np2, i1, i2;
1422 np1 = VEC_length (use_pred_info_t, pred1);
1423 np2 = VEC_length (use_pred_info_t, pred2);
1425 for (i2 = 0; i2 < np2; i2++)
1427 bool found = false;
1428 use_pred_info_t info2
1429 = VEC_index (use_pred_info_t, pred2, i2);
1430 for (i1 = 0; i1 < np1; i1++)
1432 use_pred_info_t info1
1433 = VEC_index (use_pred_info_t, pred1, i1);
1434 if (is_pred_expr_subset_of (info1, info2))
1436 found = true;
1437 break;
1440 if (!found)
1441 return false;
1443 return true;
1446 /* Returns true if the domain defined by
1447 one pred chain ONE_PRED is a subset of the domain
1448 of *PREDS. It returns false if ONE_PRED's domain is
1449 not a subset of any of the sub-domains of PREDS (
1450 corresponding to each individual chains in it), even
1451 though it may be still be a subset of whole domain
1452 of PREDS which is the union (ORed) of all its subdomains.
1453 In other words, the result is conservative. */
1455 static bool
1456 is_included_in (VEC(use_pred_info_t, heap) *one_pred,
1457 VEC(use_pred_info_t, heap) **preds,
1458 size_t n)
1460 size_t i;
1462 for (i = 0; i < n; i++)
1464 if (is_pred_chain_subset_of (one_pred, preds[i]))
1465 return true;
1468 return false;
1471 /* compares two predicate sets PREDS1 and PREDS2 and returns
1472 true if the domain defined by PREDS1 is a superset
1473 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1474 PREDS2 respectively. The implementation chooses not to build
1475 generic trees (and relying on the folding capability of the
1476 compiler), but instead performs brute force comparison of
1477 individual predicate chains (won't be a compile time problem
1478 as the chains are pretty short). When the function returns
1479 false, it does not necessarily mean *PREDS1 is not a superset
1480 of *PREDS2, but mean it may not be so since the analysis can
1481 not prove it. In such cases, false warnings may still be
1482 emitted. */
1484 static bool
1485 is_superset_of (VEC(use_pred_info_t, heap) **preds1,
1486 size_t n1,
1487 VEC(use_pred_info_t, heap) **preds2,
1488 size_t n2)
1490 size_t i;
1491 VEC(use_pred_info_t, heap) *one_pred_chain;
1493 for (i = 0; i < n2; i++)
1495 one_pred_chain = preds2[i];
1496 if (!is_included_in (one_pred_chain, preds1, n1))
1497 return false;
1500 return true;
1503 /* Computes the predicates that guard the use and checks
1504 if the incoming paths that have empty (or possibly
1505 empty) defintion can be pruned/filtered. The function returns
1506 true if it can be determined that the use of PHI's def in
1507 USE_STMT is guarded with a predicate set not overlapping with
1508 predicate sets of all runtime paths that do not have a definition.
1509 Returns false if it is not or it can not be determined. USE_BB is
1510 the bb of the use (for phi operand use, the bb is not the bb of
1511 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1512 is a bit vector. If an operand of PHI is uninitialized, the
1513 correponding bit in the vector is 1. VISIED_PHIS is a pointer
1514 set of phis being visted. */
1516 static bool
1517 is_use_properly_guarded (gimple use_stmt,
1518 basic_block use_bb,
1519 gimple phi,
1520 unsigned uninit_opnds,
1521 struct pointer_set_t *visited_phis)
1523 basic_block phi_bb;
1524 VEC(use_pred_info_t, heap) **preds = 0;
1525 VEC(use_pred_info_t, heap) **def_preds = 0;
1526 size_t num_preds = 0, num_def_preds = 0;
1527 bool has_valid_preds = false;
1528 bool is_properly_guarded = false;
1530 if (pointer_set_insert (visited_phis, phi))
1531 return false;
1533 phi_bb = gimple_bb (phi);
1535 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
1536 return false;
1538 has_valid_preds = find_predicates (&preds, &num_preds,
1539 phi_bb, use_bb);
1541 if (!has_valid_preds)
1543 destroy_predicate_vecs (num_preds, preds);
1544 return false;
1547 if (dump_file)
1548 dump_predicates (use_stmt, num_preds, preds,
1549 "\nUse in stmt ");
1551 has_valid_preds = find_def_preds (&def_preds,
1552 &num_def_preds, phi);
1554 if (has_valid_preds)
1556 if (dump_file)
1557 dump_predicates (phi, num_def_preds, def_preds,
1558 "Operand defs of phi ");
1559 is_properly_guarded =
1560 is_superset_of (def_preds, num_def_preds,
1561 preds, num_preds);
1564 /* further prune the dead incoming phi edges. */
1565 if (!is_properly_guarded)
1566 is_properly_guarded
1567 = use_pred_not_overlap_with_undef_path_pred (
1568 num_preds, preds, phi, uninit_opnds, visited_phis);
1570 destroy_predicate_vecs (num_preds, preds);
1571 destroy_predicate_vecs (num_def_preds, def_preds);
1572 return is_properly_guarded;
1575 /* Searches through all uses of a potentially
1576 uninitialized variable defined by PHI and returns a use
1577 statement if the use is not properly guarded. It returns
1578 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1579 holding the position(s) of uninit PHI operands. WORKLIST
1580 is the vector of candidate phis that may be updated by this
1581 function. ADDED_TO_WORKLIST is the pointer set tracking
1582 if the new phi is already in the worklist. */
1584 static gimple
1585 find_uninit_use (gimple phi, unsigned uninit_opnds,
1586 VEC(gimple, heap) **worklist,
1587 struct pointer_set_t *added_to_worklist)
1589 tree phi_result;
1590 use_operand_p use_p;
1591 gimple use_stmt;
1592 imm_use_iterator iter;
1594 phi_result = gimple_phi_result (phi);
1596 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
1598 struct pointer_set_t *visited_phis;
1599 basic_block use_bb;
1601 use_stmt = use_p->loc.stmt;
1603 visited_phis = pointer_set_create ();
1605 use_bb = gimple_bb (use_stmt);
1606 if (gimple_code (use_stmt) == GIMPLE_PHI)
1608 unsigned i, n;
1609 n = gimple_phi_num_args (use_stmt);
1611 /* Find the matching phi argument of the use. */
1612 for (i = 0; i < n; ++i)
1614 if (gimple_phi_arg_def_ptr (use_stmt, i) == use_p->use)
1616 edge e = gimple_phi_arg_edge (use_stmt, i);
1617 use_bb = e->src;
1618 break;
1623 if (is_use_properly_guarded (use_stmt,
1624 use_bb,
1625 phi,
1626 uninit_opnds,
1627 visited_phis))
1629 pointer_set_destroy (visited_phis);
1630 continue;
1632 pointer_set_destroy (visited_phis);
1634 if (dump_file && (dump_flags & TDF_DETAILS))
1636 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
1637 print_gimple_stmt (dump_file, use_stmt, 0, 0);
1639 /* Found one real use, return. */
1640 if (gimple_code (use_stmt) != GIMPLE_PHI)
1641 return use_stmt;
1643 /* Found a phi use that is not guarded,
1644 add the phi to the worklist. */
1645 if (!pointer_set_insert (added_to_worklist,
1646 use_stmt))
1648 if (dump_file && (dump_flags & TDF_DETAILS))
1650 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
1651 print_gimple_stmt (dump_file, use_stmt, 0, 0);
1654 VEC_safe_push (gimple, heap, *worklist, use_stmt);
1655 pointer_set_insert (possibly_undefined_names,
1656 phi_result);
1660 return NULL;
1663 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1664 and gives warning if there exists a runtime path from the entry to a
1665 use of the PHI def that does not contain a definition. In other words,
1666 the warning is on the real use. The more dead paths that can be pruned
1667 by the compiler, the fewer false positives the warning is. WORKLIST
1668 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1669 a pointer set tracking if the new phi is added to the worklist or not. */
1671 static void
1672 warn_uninitialized_phi (gimple phi, VEC(gimple, heap) **worklist,
1673 struct pointer_set_t *added_to_worklist)
1675 unsigned uninit_opnds;
1676 gimple uninit_use_stmt = 0;
1677 tree uninit_op;
1679 /* Don't look at memory tags. */
1680 if (!is_gimple_reg (gimple_phi_result (phi)))
1681 return;
1683 uninit_opnds = compute_uninit_opnds_pos (phi);
1685 if (MASK_EMPTY (uninit_opnds))
1686 return;
1688 if (dump_file && (dump_flags & TDF_DETAILS))
1690 fprintf (dump_file, "[CHECK]: examining phi: ");
1691 print_gimple_stmt (dump_file, phi, 0, 0);
1694 /* Now check if we have any use of the value without proper guard. */
1695 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
1696 worklist, added_to_worklist);
1698 /* All uses are properly guarded. */
1699 if (!uninit_use_stmt)
1700 return;
1702 uninit_op = gimple_phi_arg_def (phi, MASK_FIRST_SET_BIT (uninit_opnds));
1703 warn_uninit (uninit_op,
1704 "%qD may be used uninitialized in this function",
1705 uninit_use_stmt);
1710 /* Entry point to the late uninitialized warning pass. */
1712 static unsigned int
1713 execute_late_warn_uninitialized (void)
1715 basic_block bb;
1716 gimple_stmt_iterator gsi;
1717 VEC(gimple, heap) *worklist = 0;
1718 struct pointer_set_t *added_to_worklist;
1720 calculate_dominance_info (CDI_DOMINATORS);
1721 calculate_dominance_info (CDI_POST_DOMINATORS);
1722 /* Re-do the plain uninitialized variable check, as optimization may have
1723 straightened control flow. Do this first so that we don't accidentally
1724 get a "may be" warning when we'd have seen an "is" warning later. */
1725 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1727 timevar_push (TV_TREE_UNINIT);
1729 possibly_undefined_names = pointer_set_create ();
1730 added_to_worklist = pointer_set_create ();
1732 /* Initialize worklist */
1733 FOR_EACH_BB (bb)
1734 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1736 gimple phi = gsi_stmt (gsi);
1737 size_t n, i;
1739 n = gimple_phi_num_args (phi);
1741 /* Don't look at memory tags. */
1742 if (!is_gimple_reg (gimple_phi_result (phi)))
1743 continue;
1745 for (i = 0; i < n; ++i)
1747 tree op = gimple_phi_arg_def (phi, i);
1748 if (TREE_CODE (op) == SSA_NAME
1749 && ssa_undefined_value_p (op))
1751 VEC_safe_push (gimple, heap, worklist, phi);
1752 pointer_set_insert (added_to_worklist, phi);
1753 if (dump_file && (dump_flags & TDF_DETAILS))
1755 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
1756 print_gimple_stmt (dump_file, phi, 0, 0);
1758 break;
1763 while (VEC_length (gimple, worklist) != 0)
1765 gimple cur_phi = 0;
1766 cur_phi = VEC_pop (gimple, worklist);
1767 warn_uninitialized_phi (cur_phi, &worklist, added_to_worklist);
1770 VEC_free (gimple, heap, worklist);
1771 pointer_set_destroy (added_to_worklist);
1772 pointer_set_destroy (possibly_undefined_names);
1773 possibly_undefined_names = NULL;
1774 free_dominance_info (CDI_POST_DOMINATORS);
1775 timevar_pop (TV_TREE_UNINIT);
1776 return 0;
1779 static bool
1780 gate_warn_uninitialized (void)
1782 return warn_uninitialized != 0;
1785 struct gimple_opt_pass pass_late_warn_uninitialized =
1788 GIMPLE_PASS,
1789 "uninit", /* name */
1790 gate_warn_uninitialized, /* gate */
1791 execute_late_warn_uninitialized, /* execute */
1792 NULL, /* sub */
1793 NULL, /* next */
1794 0, /* static_pass_number */
1795 TV_NONE, /* tv_id */
1796 PROP_ssa, /* properties_required */
1797 0, /* properties_provided */
1798 0, /* properties_destroyed */
1799 0, /* todo_flags_start */
1800 0 /* todo_flags_finish */