1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2010, 2011, 2012
3 Free Software 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)
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/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
33 #include "pointer-set.h"
34 #include "tree-flow.h"
36 #include "tree-inline.h"
38 #include "tree-pass.h"
39 #include "diagnostic-core.h"
41 /* This implements the pass that does predicate aware warning on uses of
42 possibly uninitialized variables. The pass first collects the set of
43 possibly uninitialized SSA names. For each such name, it walks through
44 all its immediate uses. For each immediate use, it rebuilds the condition
45 expression (the predicate) that guards the use. The predicate is then
46 examined to see if the variable is always defined under that same condition.
47 This is done either by pruning the unrealizable paths that lead to the
48 default definitions or by checking if the predicate set that guards the
49 defining paths is a superset of the use predicate. */
52 /* Pointer set of potentially undefined ssa names, i.e.,
53 ssa names that are defined by phi with operands that
54 are not defined or potentially undefined. */
55 static struct pointer_set_t
*possibly_undefined_names
= 0;
57 /* Bit mask handling macros. */
58 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
59 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
60 #define MASK_EMPTY(mask) (mask == 0)
62 /* Returns the first bit position (starting from LSB)
63 in mask that is non zero. Returns -1 if the mask is empty. */
65 get_mask_first_set_bit (unsigned mask
)
71 while ((mask
& (1 << pos
)) == 0)
76 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
79 /* Return true if T, an SSA_NAME, has an undefined value. */
82 ssa_undefined_value_p (tree t
)
84 tree var
= SSA_NAME_VAR (t
);
88 /* Parameters get their initial value from the function entry. */
89 else if (TREE_CODE (var
) == PARM_DECL
)
91 /* When returning by reference the return address is actually a hidden
93 else if (TREE_CODE (var
) == RESULT_DECL
&& DECL_BY_REFERENCE (var
))
95 /* Hard register variables get their initial value from the ether. */
96 else if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
99 /* The value is undefined iff its definition statement is empty. */
100 return (gimple_nop_p (SSA_NAME_DEF_STMT (t
))
101 || (possibly_undefined_names
102 && pointer_set_contains (possibly_undefined_names
, t
)));
105 /* Checks if the operand OPND of PHI is defined by
106 another phi with one operand defined by this PHI,
107 but the rest operands are all defined. If yes,
108 returns true to skip this this operand as being
109 redundant. Can be enhanced to be more general. */
112 can_skip_redundant_opnd (tree opnd
, gimple phi
)
118 phi_def
= gimple_phi_result (phi
);
119 op_def
= SSA_NAME_DEF_STMT (opnd
);
120 if (gimple_code (op_def
) != GIMPLE_PHI
)
122 n
= gimple_phi_num_args (op_def
);
123 for (i
= 0; i
< n
; ++i
)
125 tree op
= gimple_phi_arg_def (op_def
, i
);
126 if (TREE_CODE (op
) != SSA_NAME
)
128 if (op
!= phi_def
&& ssa_undefined_value_p (op
))
135 /* Returns a bit mask holding the positions of arguments in PHI
136 that have empty (or possibly empty) definitions. */
139 compute_uninit_opnds_pos (gimple phi
)
142 unsigned uninit_opnds
= 0;
144 n
= gimple_phi_num_args (phi
);
145 /* Bail out for phi with too many args. */
149 for (i
= 0; i
< n
; ++i
)
151 tree op
= gimple_phi_arg_def (phi
, i
);
152 if (TREE_CODE (op
) == SSA_NAME
153 && ssa_undefined_value_p (op
)
154 && !can_skip_redundant_opnd (op
, phi
))
155 MASK_SET_BIT (uninit_opnds
, i
);
160 /* Find the immediate postdominator PDOM of the specified
161 basic block BLOCK. */
163 static inline basic_block
164 find_pdom (basic_block block
)
166 if (block
== EXIT_BLOCK_PTR
)
167 return EXIT_BLOCK_PTR
;
171 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
173 return EXIT_BLOCK_PTR
;
178 /* Find the immediate DOM of the specified
179 basic block BLOCK. */
181 static inline basic_block
182 find_dom (basic_block block
)
184 if (block
== ENTRY_BLOCK_PTR
)
185 return ENTRY_BLOCK_PTR
;
188 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
190 return ENTRY_BLOCK_PTR
;
195 /* Returns true if BB1 is postdominating BB2 and BB1 is
196 not a loop exit bb. The loop exit bb check is simple and does
197 not cover all cases. */
200 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
202 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
205 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
211 /* Find the closest postdominator of a specified BB, which is control
214 static inline basic_block
215 find_control_equiv_block (basic_block bb
)
219 pdom
= find_pdom (bb
);
221 /* Skip the postdominating bb that is also loop exit. */
222 if (!is_non_loop_exit_postdominating (pdom
, bb
))
225 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
231 #define MAX_NUM_CHAINS 8
232 #define MAX_CHAIN_LEN 5
234 /* Computes the control dependence chains (paths of edges)
235 for DEP_BB up to the dominating basic block BB (the head node of a
236 chain should be dominated by it). CD_CHAINS is pointer to a
237 dynamic array holding the result chains. CUR_CD_CHAIN is the current
238 chain being computed. *NUM_CHAINS is total number of chains. The
239 function returns true if the information is successfully computed,
240 return false if there is no control dependence or not computed. */
243 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
244 vec
<edge
> *cd_chains
,
246 vec
<edge
> *cur_cd_chain
)
251 bool found_cd_chain
= false;
252 size_t cur_chain_len
= 0;
254 if (EDGE_COUNT (bb
->succs
) < 2)
257 /* Could use a set instead. */
258 cur_chain_len
= cur_cd_chain
->length ();
259 if (cur_chain_len
> MAX_CHAIN_LEN
)
262 for (i
= 0; i
< cur_chain_len
; i
++)
264 edge e
= (*cur_cd_chain
)[i
];
265 /* cycle detected. */
270 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
273 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
277 cur_cd_chain
->safe_push (e
);
278 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
282 /* Found a direct control dependence. */
283 if (*num_chains
< MAX_NUM_CHAINS
)
285 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
288 found_cd_chain
= true;
289 /* check path from next edge. */
293 /* Now check if DEP_BB is indirectly control dependent on BB. */
294 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
295 num_chains
, cur_cd_chain
))
297 found_cd_chain
= true;
301 cd_bb
= find_pdom (cd_bb
);
302 if (cd_bb
== EXIT_BLOCK_PTR
)
305 cur_cd_chain
->pop ();
306 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
308 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
310 return found_cd_chain
;
313 typedef struct use_pred_info
321 /* Converts the chains of control dependence edges into a set of
322 predicates. A control dependence chain is represented by a vector
323 edges. DEP_CHAINS points to an array of dependence chains.
324 NUM_CHAINS is the size of the chain array. One edge in a dependence
325 chain is mapped to predicate expression represented by use_pred_info_t
326 type. One dependence chain is converted to a composite predicate that
327 is the result of AND operation of use_pred_info_t mapped to each edge.
328 A composite predicate is presented by a vector of use_pred_info_t. On
329 return, *PREDS points to the resulting array of composite predicates.
330 *NUM_PREDS is the number of composite predictes. */
333 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
335 vec
<use_pred_info_t
> **preds
,
338 bool has_valid_pred
= false;
340 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
343 /* Now convert the control dep chain into a set
345 typedef vec
<use_pred_info_t
> vec_use_pred_info_t_heap
;
346 *preds
= XCNEWVEC (vec_use_pred_info_t_heap
, num_chains
);
347 *num_preds
= num_chains
;
349 for (i
= 0; i
< num_chains
; i
++)
351 vec
<edge
> one_cd_chain
= dep_chains
[i
];
353 has_valid_pred
= false;
354 for (j
= 0; j
< one_cd_chain
.length (); j
++)
357 gimple_stmt_iterator gsi
;
358 basic_block guard_bb
;
359 use_pred_info_t one_pred
;
364 gsi
= gsi_last_bb (guard_bb
);
367 has_valid_pred
= false;
370 cond_stmt
= gsi_stmt (gsi
);
371 if (gimple_code (cond_stmt
) == GIMPLE_CALL
372 && EDGE_COUNT (e
->src
->succs
) >= 2)
374 /* Ignore EH edge. Can add assertion
375 on the other edge's flag. */
378 /* Skip if there is essentially one succesor. */
379 if (EDGE_COUNT (e
->src
->succs
) == 2)
385 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
387 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
396 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
398 has_valid_pred
= false;
401 one_pred
= XNEW (struct use_pred_info
);
402 one_pred
->cond
= cond_stmt
;
403 one_pred
->invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
404 (*preds
)[i
].safe_push (one_pred
);
405 has_valid_pred
= true;
411 return has_valid_pred
;
414 /* Computes all control dependence chains for USE_BB. The control
415 dependence chains are then converted to an array of composite
416 predicates pointed to by PREDS. PHI_BB is the basic block of
417 the phi whose result is used in USE_BB. */
420 find_predicates (vec
<use_pred_info_t
> **preds
,
425 size_t num_chains
= 0, i
;
426 vec
<edge
> *dep_chains
= 0;
427 vec
<edge
> cur_chain
= vNULL
;
428 bool has_valid_pred
= false;
429 basic_block cd_root
= 0;
431 typedef vec
<edge
> vec_edge_heap
;
432 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
434 /* First find the closest bb that is control equivalent to PHI_BB
435 that also dominates USE_BB. */
437 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
439 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
440 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
441 cd_root
= ctrl_eq_bb
;
446 compute_control_dep_chain (cd_root
, use_bb
,
447 dep_chains
, &num_chains
,
451 = convert_control_dep_chain_into_preds (dep_chains
,
455 /* Free individual chain */
456 cur_chain
.release ();
457 for (i
= 0; i
< num_chains
; i
++)
458 dep_chains
[i
].release ();
460 return has_valid_pred
;
463 /* Computes the set of incoming edges of PHI that have non empty
464 definitions of a phi chain. The collection will be done
465 recursively on operands that are defined by phis. CD_ROOT
466 is the control dependence root. *EDGES holds the result, and
467 VISITED_PHIS is a pointer set for detecting cycles. */
470 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
472 struct pointer_set_t
*visited_phis
)
478 if (pointer_set_insert (visited_phis
, phi
))
481 n
= gimple_phi_num_args (phi
);
482 for (i
= 0; i
< n
; i
++)
484 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
485 opnd
= gimple_phi_arg_def (phi
, i
);
487 if (TREE_CODE (opnd
) != SSA_NAME
)
489 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
491 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
492 print_gimple_stmt (dump_file
, phi
, 0, 0);
494 edges
->safe_push (opnd_edge
);
498 gimple def
= SSA_NAME_DEF_STMT (opnd
);
500 if (gimple_code (def
) == GIMPLE_PHI
501 && dominated_by_p (CDI_DOMINATORS
,
502 gimple_bb (def
), cd_root
))
503 collect_phi_def_edges (def
, cd_root
, edges
,
505 else if (!ssa_undefined_value_p (opnd
))
507 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
509 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
510 print_gimple_stmt (dump_file
, phi
, 0, 0);
512 edges
->safe_push (opnd_edge
);
518 /* For each use edge of PHI, computes all control dependence chains.
519 The control dependence chains are then converted to an array of
520 composite predicates pointed to by PREDS. */
523 find_def_preds (vec
<use_pred_info_t
> **preds
,
524 size_t *num_preds
, gimple phi
)
526 size_t num_chains
= 0, i
, n
;
527 vec
<edge
> *dep_chains
= 0;
528 vec
<edge
> cur_chain
= vNULL
;
529 vec
<edge
> def_edges
= vNULL
;
530 bool has_valid_pred
= false;
531 basic_block phi_bb
, cd_root
= 0;
532 struct pointer_set_t
*visited_phis
;
534 typedef vec
<edge
> vec_edge_heap
;
535 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
537 phi_bb
= gimple_bb (phi
);
538 /* First find the closest dominating bb to be
539 the control dependence root */
540 cd_root
= find_dom (phi_bb
);
544 visited_phis
= pointer_set_create ();
545 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
546 pointer_set_destroy (visited_phis
);
548 n
= def_edges
.length ();
552 for (i
= 0; i
< n
; i
++)
557 opnd_edge
= def_edges
[i
];
558 prev_nc
= num_chains
;
559 compute_control_dep_chain (cd_root
, opnd_edge
->src
,
560 dep_chains
, &num_chains
,
562 /* Free individual chain */
563 cur_chain
.release ();
565 /* Now update the newly added chains with
566 the phi operand edge: */
567 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
569 if (prev_nc
== num_chains
570 && num_chains
< MAX_NUM_CHAINS
)
572 for (j
= prev_nc
; j
< num_chains
; j
++)
574 dep_chains
[j
].safe_push (opnd_edge
);
580 = convert_control_dep_chain_into_preds (dep_chains
,
584 for (i
= 0; i
< num_chains
; i
++)
585 dep_chains
[i
].release ();
587 return has_valid_pred
;
590 /* Dumps the predicates (PREDS) for USESTMT. */
593 dump_predicates (gimple usestmt
, size_t num_preds
,
594 vec
<use_pred_info_t
> *preds
,
598 vec
<use_pred_info_t
> one_pred_chain
;
599 fprintf (dump_file
, msg
);
600 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
601 fprintf (dump_file
, "is guarded by :\n");
602 /* do some dumping here: */
603 for (i
= 0; i
< num_preds
; i
++)
607 one_pred_chain
= preds
[i
];
608 np
= one_pred_chain
.length ();
610 for (j
= 0; j
< np
; j
++)
612 use_pred_info_t one_pred
614 if (one_pred
->invert
)
615 fprintf (dump_file
, " (.NOT.) ");
616 print_gimple_stmt (dump_file
, one_pred
->cond
, 0, 0);
618 fprintf (dump_file
, "(.AND.)\n");
620 if (i
< num_preds
- 1)
621 fprintf (dump_file
, "(.OR.)\n");
625 /* Destroys the predicate set *PREDS. */
628 destroy_predicate_vecs (size_t n
,
629 vec
<use_pred_info_t
> * preds
)
632 for (i
= 0; i
< n
; i
++)
634 for (j
= 0; j
< preds
[i
].length (); j
++)
642 /* Computes the 'normalized' conditional code with operand
643 swapping and condition inversion. */
645 static enum tree_code
646 get_cmp_code (enum tree_code orig_cmp_code
,
647 bool swap_cond
, bool invert
)
649 enum tree_code tc
= orig_cmp_code
;
652 tc
= swap_tree_comparison (orig_cmp_code
);
654 tc
= invert_tree_comparison (tc
, false);
671 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
672 all values in the range satisfies (x CMPC BOUNDARY) == true. */
675 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
677 bool inverted
= false;
681 /* Only handle integer constant here. */
682 if (TREE_CODE (val
) != INTEGER_CST
683 || TREE_CODE (boundary
) != INTEGER_CST
)
686 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
688 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
691 cmpc
= invert_tree_comparison (cmpc
, false);
698 result
= tree_int_cst_equal (val
, boundary
);
699 else if (cmpc
== LT_EXPR
)
700 result
= INT_CST_LT_UNSIGNED (val
, boundary
);
703 gcc_assert (cmpc
== LE_EXPR
);
704 result
= (tree_int_cst_equal (val
, boundary
)
705 || INT_CST_LT_UNSIGNED (val
, boundary
));
711 result
= tree_int_cst_equal (val
, boundary
);
712 else if (cmpc
== LT_EXPR
)
713 result
= INT_CST_LT (val
, boundary
);
716 gcc_assert (cmpc
== LE_EXPR
);
717 result
= (tree_int_cst_equal (val
, boundary
)
718 || INT_CST_LT (val
, boundary
));
728 /* Returns true if PRED is common among all the predicate
729 chains (PREDS) (and therefore can be factored out).
730 NUM_PRED_CHAIN is the size of array PREDS. */
733 find_matching_predicate_in_rest_chains (use_pred_info_t pred
,
734 vec
<use_pred_info_t
> *preds
,
735 size_t num_pred_chains
)
740 if (num_pred_chains
== 1)
743 for (i
= 1; i
< num_pred_chains
; i
++)
746 vec
<use_pred_info_t
> one_chain
= preds
[i
];
747 n
= one_chain
.length ();
748 for (j
= 0; j
< n
; j
++)
750 use_pred_info_t pred2
752 /* can relax the condition comparison to not
753 use address comparison. However, the most common
754 case is that multiple control dependent paths share
755 a common path prefix, so address comparison should
758 if (pred2
->cond
== pred
->cond
759 && pred2
->invert
== pred
->invert
)
771 /* Forward declaration. */
773 is_use_properly_guarded (gimple use_stmt
,
776 unsigned uninit_opnds
,
777 struct pointer_set_t
*visited_phis
);
779 /* Returns true if all uninitialized opnds are pruned. Returns false
780 otherwise. PHI is the phi node with uninitialized operands,
781 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
782 FLAG_DEF is the statement defining the flag guarding the use of the
783 PHI output, BOUNDARY_CST is the const value used in the predicate
784 associated with the flag, CMP_CODE is the comparison code used in
785 the predicate, VISITED_PHIS is the pointer set of phis visited, and
786 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
792 flag_1 = phi <0, 1> // (1)
793 var_1 = phi <undef, some_val>
797 flag_2 = phi <0, flag_1, flag_1> // (2)
798 var_2 = phi <undef, var_1, var_1>
805 Because some flag arg in (1) is not constant, if we do not look into the
806 flag phis recursively, it is conservatively treated as unknown and var_1
807 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
808 a false warning will be emitted. Checking recursively into (1), the compiler can
809 find out that only some_val (which is defined) can flow into (3) which is OK.
814 prune_uninit_phi_opnds_in_unrealizable_paths (
815 gimple phi
, unsigned uninit_opnds
,
816 gimple flag_def
, tree boundary_cst
,
817 enum tree_code cmp_code
,
818 struct pointer_set_t
*visited_phis
,
819 bitmap
*visited_flag_phis
)
823 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
827 if (!MASK_TEST_BIT (uninit_opnds
, i
))
830 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
831 if (!is_gimple_constant (flag_arg
))
833 gimple flag_arg_def
, phi_arg_def
;
835 unsigned uninit_opnds_arg_phi
;
837 if (TREE_CODE (flag_arg
) != SSA_NAME
)
839 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
840 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
843 phi_arg
= gimple_phi_arg_def (phi
, i
);
844 if (TREE_CODE (phi_arg
) != SSA_NAME
)
847 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
848 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
851 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
854 if (!*visited_flag_phis
)
855 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
857 if (bitmap_bit_p (*visited_flag_phis
,
858 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
861 bitmap_set_bit (*visited_flag_phis
,
862 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
864 /* Now recursively prune the uninitialized phi args. */
865 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
866 if (!prune_uninit_phi_opnds_in_unrealizable_paths (
867 phi_arg_def
, uninit_opnds_arg_phi
,
868 flag_arg_def
, boundary_cst
, cmp_code
,
869 visited_phis
, visited_flag_phis
))
872 bitmap_clear_bit (*visited_flag_phis
,
873 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
877 /* Now check if the constant is in the guarded range. */
878 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
883 /* Now that we know that this undefined edge is not
884 pruned. If the operand is defined by another phi,
885 we can further prune the incoming edges of that
886 phi by checking the predicates of this operands. */
888 opnd
= gimple_phi_arg_def (phi
, i
);
889 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
890 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
893 unsigned uninit_opnds2
894 = compute_uninit_opnds_pos (opnd_def
);
895 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
896 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
897 if (!is_use_properly_guarded (phi
,
912 /* A helper function that determines if the predicate set
913 of the use is not overlapping with that of the uninit paths.
914 The most common senario of guarded use is in Example 1:
927 The real world examples are usually more complicated, but similar
928 and usually result from inlining:
930 bool init_func (int * x)
949 Another possible use scenario is in the following trivial example:
961 Predicate analysis needs to compute the composite predicate:
963 1) 'x' use predicate: (n > 0) .AND. (m < 2)
964 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
965 (the predicate chain for phi operand defs can be computed
966 starting from a bb that is control equivalent to the phi's
967 bb and is dominating the operand def.)
969 and check overlapping:
970 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
973 This implementation provides framework that can handle
974 scenarios. (Note that many simple cases are handled properly
975 without the predicate analysis -- this is due to jump threading
976 transformation which eliminates the merge point thus makes
977 path sensitive analysis unnecessary.)
979 NUM_PREDS is the number is the number predicate chains, PREDS is
980 the array of chains, PHI is the phi node whose incoming (undefined)
981 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
982 uninit operand positions. VISITED_PHIS is the pointer set of phi
983 stmts being checked. */
987 use_pred_not_overlap_with_undef_path_pred (
989 vec
<use_pred_info_t
> *preds
,
990 gimple phi
, unsigned uninit_opnds
,
991 struct pointer_set_t
*visited_phis
)
995 tree boundary_cst
= 0;
996 enum tree_code cmp_code
;
997 bool swap_cond
= false;
999 vec
<use_pred_info_t
> the_pred_chain
;
1000 bitmap visited_flag_phis
= NULL
;
1001 bool all_pruned
= false;
1003 gcc_assert (num_preds
> 0);
1004 /* Find within the common prefix of multiple predicate chains
1005 a predicate that is a comparison of a flag variable against
1007 the_pred_chain
= preds
[0];
1008 n
= the_pred_chain
.length ();
1009 for (i
= 0; i
< n
; i
++)
1012 tree cond_lhs
, cond_rhs
, flag
= 0;
1014 use_pred_info_t the_pred
1015 = the_pred_chain
[i
];
1017 cond
= the_pred
->cond
;
1018 invert
= the_pred
->invert
;
1019 cond_lhs
= gimple_cond_lhs (cond
);
1020 cond_rhs
= gimple_cond_rhs (cond
);
1021 cmp_code
= gimple_cond_code (cond
);
1023 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1024 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1026 boundary_cst
= cond_rhs
;
1029 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1030 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1032 boundary_cst
= cond_lhs
;
1040 flag_def
= SSA_NAME_DEF_STMT (flag
);
1045 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1046 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1047 && find_matching_predicate_in_rest_chains (
1048 the_pred
, preds
, num_preds
))
1057 /* Now check all the uninit incoming edge has a constant flag value
1058 that is in conflict with the use guard/predicate. */
1059 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1061 if (cmp_code
== ERROR_MARK
)
1064 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1070 &visited_flag_phis
);
1072 if (visited_flag_phis
)
1073 BITMAP_FREE (visited_flag_phis
);
1078 /* Returns true if TC is AND or OR */
1081 is_and_or_or (enum tree_code tc
, tree typ
)
1083 return (tc
== BIT_IOR_EXPR
1084 || (tc
== BIT_AND_EXPR
1085 && (typ
== 0 || TREE_CODE (typ
) == BOOLEAN_TYPE
)));
1088 typedef struct norm_cond
1091 enum tree_code cond_code
;
1096 /* Normalizes gimple condition COND. The normalization follows
1097 UD chains to form larger condition expression trees. NORM_COND
1098 holds the normalized result. COND_CODE is the logical opcode
1099 (AND or OR) of the normalized tree. */
1102 normalize_cond_1 (gimple cond
,
1103 norm_cond_t norm_cond
,
1104 enum tree_code cond_code
)
1106 enum gimple_code gc
;
1107 enum tree_code cur_cond_code
;
1110 gc
= gimple_code (cond
);
1111 if (gc
!= GIMPLE_ASSIGN
)
1113 norm_cond
->conds
.safe_push (cond
);
1117 cur_cond_code
= gimple_assign_rhs_code (cond
);
1118 rhs1
= gimple_assign_rhs1 (cond
);
1119 rhs2
= gimple_assign_rhs2 (cond
);
1120 if (cur_cond_code
== NE_EXPR
)
1122 if (integer_zerop (rhs2
)
1123 && (TREE_CODE (rhs1
) == SSA_NAME
))
1125 SSA_NAME_DEF_STMT (rhs1
),
1126 norm_cond
, cond_code
);
1127 else if (integer_zerop (rhs1
)
1128 && (TREE_CODE (rhs2
) == SSA_NAME
))
1130 SSA_NAME_DEF_STMT (rhs2
),
1131 norm_cond
, cond_code
);
1133 norm_cond
->conds
.safe_push (cond
);
1138 if (is_and_or_or (cur_cond_code
, TREE_TYPE (rhs1
))
1139 && (cond_code
== cur_cond_code
|| cond_code
== ERROR_MARK
)
1140 && (TREE_CODE (rhs1
) == SSA_NAME
&& TREE_CODE (rhs2
) == SSA_NAME
))
1142 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1
),
1143 norm_cond
, cur_cond_code
);
1144 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2
),
1145 norm_cond
, cur_cond_code
);
1146 norm_cond
->cond_code
= cur_cond_code
;
1149 norm_cond
->conds
.safe_push (cond
);
1152 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1153 if COND needs to be inverted or not. */
1156 normalize_cond (gimple cond
, norm_cond_t norm_cond
, bool invert
)
1158 enum tree_code cond_code
;
1160 norm_cond
->cond_code
= ERROR_MARK
;
1161 norm_cond
->invert
= false;
1162 norm_cond
->conds
.create (0);
1163 gcc_assert (gimple_code (cond
) == GIMPLE_COND
);
1164 cond_code
= gimple_cond_code (cond
);
1166 cond_code
= invert_tree_comparison (cond_code
, false);
1168 if (cond_code
== NE_EXPR
)
1170 if (integer_zerop (gimple_cond_rhs (cond
))
1171 && (TREE_CODE (gimple_cond_lhs (cond
)) == SSA_NAME
))
1173 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
)),
1174 norm_cond
, ERROR_MARK
);
1175 else if (integer_zerop (gimple_cond_lhs (cond
))
1176 && (TREE_CODE (gimple_cond_rhs (cond
)) == SSA_NAME
))
1178 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond
)),
1179 norm_cond
, ERROR_MARK
);
1182 norm_cond
->conds
.safe_push (cond
);
1183 norm_cond
->invert
= invert
;
1188 norm_cond
->conds
.safe_push (cond
);
1189 norm_cond
->invert
= invert
;
1192 gcc_assert (norm_cond
->conds
.length () == 1
1193 || is_and_or_or (norm_cond
->cond_code
, NULL
));
1196 /* Returns true if the domain for condition COND1 is a subset of
1197 COND2. REVERSE is a flag. when it is true the function checks
1198 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1199 to indicate if COND1 and COND2 need to be inverted or not. */
1202 is_gcond_subset_of (gimple cond1
, bool invert1
,
1203 gimple cond2
, bool invert2
,
1206 enum gimple_code gc1
, gc2
;
1207 enum tree_code cond1_code
, cond2_code
;
1209 tree cond1_lhs
, cond1_rhs
, cond2_lhs
, cond2_rhs
;
1211 /* Take the short cut. */
1222 gc1
= gimple_code (cond1
);
1223 gc2
= gimple_code (cond2
);
1225 if ((gc1
!= GIMPLE_ASSIGN
&& gc1
!= GIMPLE_COND
)
1226 || (gc2
!= GIMPLE_ASSIGN
&& gc2
!= GIMPLE_COND
))
1227 return cond1
== cond2
;
1229 cond1_code
= ((gc1
== GIMPLE_ASSIGN
)
1230 ? gimple_assign_rhs_code (cond1
)
1231 : gimple_cond_code (cond1
));
1233 cond2_code
= ((gc2
== GIMPLE_ASSIGN
)
1234 ? gimple_assign_rhs_code (cond2
)
1235 : gimple_cond_code (cond2
));
1237 if (TREE_CODE_CLASS (cond1_code
) != tcc_comparison
1238 || TREE_CODE_CLASS (cond2_code
) != tcc_comparison
)
1242 cond1_code
= invert_tree_comparison (cond1_code
, false);
1244 cond2_code
= invert_tree_comparison (cond2_code
, false);
1246 cond1_lhs
= ((gc1
== GIMPLE_ASSIGN
)
1247 ? gimple_assign_rhs1 (cond1
)
1248 : gimple_cond_lhs (cond1
));
1249 cond1_rhs
= ((gc1
== GIMPLE_ASSIGN
)
1250 ? gimple_assign_rhs2 (cond1
)
1251 : gimple_cond_rhs (cond1
));
1252 cond2_lhs
= ((gc2
== GIMPLE_ASSIGN
)
1253 ? gimple_assign_rhs1 (cond2
)
1254 : gimple_cond_lhs (cond2
));
1255 cond2_rhs
= ((gc2
== GIMPLE_ASSIGN
)
1256 ? gimple_assign_rhs2 (cond2
)
1257 : gimple_cond_rhs (cond2
));
1259 /* Assuming const operands have been swapped to the
1260 rhs at this point of the analysis. */
1262 if (cond1_lhs
!= cond2_lhs
)
1265 if (!is_gimple_constant (cond1_rhs
)
1266 || TREE_CODE (cond1_rhs
) != INTEGER_CST
)
1267 return (cond1_rhs
== cond2_rhs
);
1269 if (!is_gimple_constant (cond2_rhs
)
1270 || TREE_CODE (cond2_rhs
) != INTEGER_CST
)
1271 return (cond1_rhs
== cond2_rhs
);
1273 if (cond1_code
== EQ_EXPR
)
1274 return is_value_included_in (cond1_rhs
,
1275 cond2_rhs
, cond2_code
);
1276 if (cond1_code
== NE_EXPR
|| cond2_code
== EQ_EXPR
)
1277 return ((cond2_code
== cond1_code
)
1278 && tree_int_cst_equal (cond1_rhs
, cond2_rhs
));
1280 if (((cond1_code
== GE_EXPR
|| cond1_code
== GT_EXPR
)
1281 && (cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
))
1282 || ((cond1_code
== LE_EXPR
|| cond1_code
== LT_EXPR
)
1283 && (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
)))
1286 if (cond1_code
!= GE_EXPR
&& cond1_code
!= GT_EXPR
1287 && cond1_code
!= LE_EXPR
&& cond1_code
!= LT_EXPR
)
1290 if (cond1_code
== GT_EXPR
)
1292 cond1_code
= GE_EXPR
;
1293 cond1_rhs
= fold_binary (PLUS_EXPR
, TREE_TYPE (cond1_rhs
),
1295 fold_convert (TREE_TYPE (cond1_rhs
),
1298 else if (cond1_code
== LT_EXPR
)
1300 cond1_code
= LE_EXPR
;
1301 cond1_rhs
= fold_binary (MINUS_EXPR
, TREE_TYPE (cond1_rhs
),
1303 fold_convert (TREE_TYPE (cond1_rhs
),
1310 gcc_assert (cond1_code
== GE_EXPR
|| cond1_code
== LE_EXPR
);
1312 if (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
||
1313 cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
)
1314 return is_value_included_in (cond1_rhs
,
1315 cond2_rhs
, cond2_code
);
1316 else if (cond2_code
== NE_EXPR
)
1318 (is_value_included_in (cond1_rhs
,
1319 cond2_rhs
, cond2_code
)
1320 && !is_value_included_in (cond2_rhs
,
1321 cond1_rhs
, cond1_code
));
1325 /* Returns true if the domain of the condition expression
1326 in COND is a subset of any of the sub-conditions
1327 of the normalized condtion NORM_COND. INVERT is a flag
1328 to indicate of the COND needs to be inverted.
1329 REVERSE is a flag. When it is true, the check is reversed --
1330 it returns true if COND is a superset of any of the subconditions
1334 is_subset_of_any (gimple cond
, bool invert
,
1335 norm_cond_t norm_cond
, bool reverse
)
1338 size_t len
= norm_cond
->conds
.length ();
1340 for (i
= 0; i
< len
; i
++)
1342 if (is_gcond_subset_of (cond
, invert
,
1343 norm_cond
->conds
[i
],
1350 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1351 expressions (formed by following UD chains not control
1352 dependence chains). The function returns true of domain
1353 of and expression NORM_COND1 is a subset of NORM_COND2's.
1354 The implementation is conservative, and it returns false if
1355 it the inclusion relationship may not hold. */
1358 is_or_set_subset_of (norm_cond_t norm_cond1
,
1359 norm_cond_t norm_cond2
)
1362 size_t len
= norm_cond1
->conds
.length ();
1364 for (i
= 0; i
< len
; i
++)
1366 if (!is_subset_of_any (norm_cond1
->conds
[i
],
1367 false, norm_cond2
, false))
1373 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1374 expressions (formed by following UD chains not control
1375 dependence chains). The function returns true of domain
1376 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1379 is_and_set_subset_of (norm_cond_t norm_cond1
,
1380 norm_cond_t norm_cond2
)
1383 size_t len
= norm_cond2
->conds
.length ();
1385 for (i
= 0; i
< len
; i
++)
1387 if (!is_subset_of_any (norm_cond2
->conds
[i
],
1388 false, norm_cond1
, true))
1394 /* Returns true of the domain if NORM_COND1 is a subset
1395 of that of NORM_COND2. Returns false if it can not be
1399 is_norm_cond_subset_of (norm_cond_t norm_cond1
,
1400 norm_cond_t norm_cond2
)
1403 enum tree_code code1
, code2
;
1405 code1
= norm_cond1
->cond_code
;
1406 code2
= norm_cond2
->cond_code
;
1408 if (code1
== BIT_AND_EXPR
)
1410 /* Both conditions are AND expressions. */
1411 if (code2
== BIT_AND_EXPR
)
1412 return is_and_set_subset_of (norm_cond1
, norm_cond2
);
1413 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1414 expression. In this case, returns true if any subexpression
1415 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1416 else if (code2
== BIT_IOR_EXPR
)
1419 len1
= norm_cond1
->conds
.length ();
1420 for (i
= 0; i
< len1
; i
++)
1422 gimple cond1
= norm_cond1
->conds
[i
];
1423 if (is_subset_of_any (cond1
, false, norm_cond2
, false))
1430 gcc_assert (code2
== ERROR_MARK
);
1431 gcc_assert (norm_cond2
->conds
.length () == 1);
1432 return is_subset_of_any (norm_cond2
->conds
[0],
1433 norm_cond2
->invert
, norm_cond1
, true);
1436 /* NORM_COND1 is an OR expression */
1437 else if (code1
== BIT_IOR_EXPR
)
1442 return is_or_set_subset_of (norm_cond1
, norm_cond2
);
1446 gcc_assert (code1
== ERROR_MARK
);
1447 gcc_assert (norm_cond1
->conds
.length () == 1);
1448 /* Conservatively returns false if NORM_COND1 is non-decomposible
1449 and NORM_COND2 is an AND expression. */
1450 if (code2
== BIT_AND_EXPR
)
1453 if (code2
== BIT_IOR_EXPR
)
1454 return is_subset_of_any (norm_cond1
->conds
[0],
1455 norm_cond1
->invert
, norm_cond2
, false);
1457 gcc_assert (code2
== ERROR_MARK
);
1458 gcc_assert (norm_cond2
->conds
.length () == 1);
1459 return is_gcond_subset_of (norm_cond1
->conds
[0],
1461 norm_cond2
->conds
[0],
1462 norm_cond2
->invert
, false);
1466 /* Returns true of the domain of single predicate expression
1467 EXPR1 is a subset of that of EXPR2. Returns false if it
1468 can not be proved. */
1471 is_pred_expr_subset_of (use_pred_info_t expr1
,
1472 use_pred_info_t expr2
)
1474 gimple cond1
, cond2
;
1475 enum tree_code code1
, code2
;
1476 struct norm_cond norm_cond1
, norm_cond2
;
1477 bool is_subset
= false;
1479 cond1
= expr1
->cond
;
1480 cond2
= expr2
->cond
;
1481 code1
= gimple_cond_code (cond1
);
1482 code2
= gimple_cond_code (cond2
);
1485 code1
= invert_tree_comparison (code1
, false);
1487 code2
= invert_tree_comparison (code2
, false);
1489 /* Fast path -- match exactly */
1490 if ((gimple_cond_lhs (cond1
) == gimple_cond_lhs (cond2
))
1491 && (gimple_cond_rhs (cond1
) == gimple_cond_rhs (cond2
))
1492 && (code1
== code2
))
1495 /* Normalize conditions. To keep NE_EXPR, do not invert
1496 with both need inversion. */
1497 normalize_cond (cond1
, &norm_cond1
, (expr1
->invert
));
1498 normalize_cond (cond2
, &norm_cond2
, (expr2
->invert
));
1500 is_subset
= is_norm_cond_subset_of (&norm_cond1
, &norm_cond2
);
1503 norm_cond1
.conds
.release ();
1504 norm_cond2
.conds
.release ();
1508 /* Returns true if the domain of PRED1 is a subset
1509 of that of PRED2. Returns false if it can not be proved so. */
1512 is_pred_chain_subset_of (vec
<use_pred_info_t
> pred1
,
1513 vec
<use_pred_info_t
> pred2
)
1515 size_t np1
, np2
, i1
, i2
;
1517 np1
= pred1
.length ();
1518 np2
= pred2
.length ();
1520 for (i2
= 0; i2
< np2
; i2
++)
1523 use_pred_info_t info2
1525 for (i1
= 0; i1
< np1
; i1
++)
1527 use_pred_info_t info1
1529 if (is_pred_expr_subset_of (info1
, info2
))
1541 /* Returns true if the domain defined by
1542 one pred chain ONE_PRED is a subset of the domain
1543 of *PREDS. It returns false if ONE_PRED's domain is
1544 not a subset of any of the sub-domains of PREDS (
1545 corresponding to each individual chains in it), even
1546 though it may be still be a subset of whole domain
1547 of PREDS which is the union (ORed) of all its subdomains.
1548 In other words, the result is conservative. */
1551 is_included_in (vec
<use_pred_info_t
> one_pred
,
1552 vec
<use_pred_info_t
> *preds
,
1557 for (i
= 0; i
< n
; i
++)
1559 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1566 /* compares two predicate sets PREDS1 and PREDS2 and returns
1567 true if the domain defined by PREDS1 is a superset
1568 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1569 PREDS2 respectively. The implementation chooses not to build
1570 generic trees (and relying on the folding capability of the
1571 compiler), but instead performs brute force comparison of
1572 individual predicate chains (won't be a compile time problem
1573 as the chains are pretty short). When the function returns
1574 false, it does not necessarily mean *PREDS1 is not a superset
1575 of *PREDS2, but mean it may not be so since the analysis can
1576 not prove it. In such cases, false warnings may still be
1580 is_superset_of (vec
<use_pred_info_t
> *preds1
,
1582 vec
<use_pred_info_t
> *preds2
,
1586 vec
<use_pred_info_t
> one_pred_chain
;
1588 for (i
= 0; i
< n2
; i
++)
1590 one_pred_chain
= preds2
[i
];
1591 if (!is_included_in (one_pred_chain
, preds1
, n1
))
1598 /* Comparison function used by qsort. It is used to
1599 sort predicate chains to allow predicate
1603 pred_chain_length_cmp (const void *p1
, const void *p2
)
1605 use_pred_info_t i1
, i2
;
1606 vec
<use_pred_info_t
> const *chain1
1607 = (vec
<use_pred_info_t
> const *)p1
;
1608 vec
<use_pred_info_t
> const *chain2
1609 = (vec
<use_pred_info_t
> const *)p2
;
1611 if (chain1
->length () != chain2
->length ())
1612 return (chain1
->length () - chain2
->length ());
1617 /* Allow predicates with similar prefix come together. */
1618 if (!i1
->invert
&& i2
->invert
)
1620 else if (i1
->invert
&& !i2
->invert
)
1623 return gimple_uid (i1
->cond
) - gimple_uid (i2
->cond
);
1626 /* x OR (!x AND y) is equivalent to x OR y.
1627 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
1628 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
1629 the number of chains. Returns true if normalization happens. */
1632 normalize_preds (vec
<use_pred_info_t
> *preds
, size_t *n
)
1635 vec
<use_pred_info_t
> pred_chain
;
1636 vec
<use_pred_info_t
> x
= vNULL
;
1637 use_pred_info_t xj
= 0, nxj
= 0;
1642 /* First sort the chains in ascending order of lengths. */
1643 qsort (preds
, *n
, sizeof (void *), pred_chain_length_cmp
);
1644 pred_chain
= preds
[0];
1645 ll
= pred_chain
.length ();
1650 use_pred_info_t xx
, yy
, xx2
, nyy
;
1651 vec
<use_pred_info_t
> pred_chain2
= preds
[1];
1652 if (pred_chain2
.length () != 2)
1655 /* See if simplification x AND y OR x AND !y is possible. */
1658 xx2
= pred_chain2
[0];
1659 nyy
= pred_chain2
[1];
1660 if (gimple_cond_lhs (xx
->cond
) != gimple_cond_lhs (xx2
->cond
)
1661 || gimple_cond_rhs (xx
->cond
) != gimple_cond_rhs (xx2
->cond
)
1662 || gimple_cond_code (xx
->cond
) != gimple_cond_code (xx2
->cond
)
1663 || (xx
->invert
!= xx2
->invert
))
1665 if (gimple_cond_lhs (yy
->cond
) != gimple_cond_lhs (nyy
->cond
)
1666 || gimple_cond_rhs (yy
->cond
) != gimple_cond_rhs (nyy
->cond
)
1667 || gimple_cond_code (yy
->cond
) != gimple_cond_code (nyy
->cond
)
1668 || (yy
->invert
== nyy
->invert
))
1671 /* Now merge the first two chains. */
1675 pred_chain
.release ();
1676 pred_chain2
.release ();
1677 pred_chain
.safe_push (xx
);
1678 preds
[0] = pred_chain
;
1679 for (i
= 1; i
< *n
- 1; i
++)
1680 preds
[i
] = preds
[i
+ 1];
1682 preds
[*n
- 1].create (0);
1689 x
.safe_push (pred_chain
[0]);
1691 /* The loop extracts x1, x2, x3, etc from chains
1692 x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
1693 for (i
= 1; i
< *n
; i
++)
1695 pred_chain
= preds
[i
];
1696 if (pred_chain
.length () != i
+ 1)
1699 for (j
= 0; j
< i
; j
++)
1702 nxj
= pred_chain
[j
];
1704 /* Check if nxj is !xj */
1705 if (gimple_cond_lhs (xj
->cond
) != gimple_cond_lhs (nxj
->cond
)
1706 || gimple_cond_rhs (xj
->cond
) != gimple_cond_rhs (nxj
->cond
)
1707 || gimple_cond_code (xj
->cond
) != gimple_cond_code (nxj
->cond
)
1708 || (xj
->invert
== nxj
->invert
))
1712 x
.safe_push (pred_chain
[i
]);
1715 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
1716 for (j
= 0; j
< *n
; j
++)
1721 t
= XNEW (struct use_pred_info
);
1727 for (i
= 0; i
< *n
; i
++)
1729 pred_chain
= preds
[i
];
1730 for (j
= 0; j
< pred_chain
.length (); j
++)
1731 free (pred_chain
[j
]);
1732 pred_chain
.release ();
1734 pred_chain
.safe_push (x
[i
]);
1735 preds
[i
] = pred_chain
;
1742 /* Computes the predicates that guard the use and checks
1743 if the incoming paths that have empty (or possibly
1744 empty) definition can be pruned/filtered. The function returns
1745 true if it can be determined that the use of PHI's def in
1746 USE_STMT is guarded with a predicate set not overlapping with
1747 predicate sets of all runtime paths that do not have a definition.
1748 Returns false if it is not or it can not be determined. USE_BB is
1749 the bb of the use (for phi operand use, the bb is not the bb of
1750 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1751 is a bit vector. If an operand of PHI is uninitialized, the
1752 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
1753 set of phis being visted. */
1756 is_use_properly_guarded (gimple use_stmt
,
1759 unsigned uninit_opnds
,
1760 struct pointer_set_t
*visited_phis
)
1763 vec
<use_pred_info_t
> *preds
= 0;
1764 vec
<use_pred_info_t
> *def_preds
= 0;
1765 size_t num_preds
= 0, num_def_preds
= 0;
1766 bool has_valid_preds
= false;
1767 bool is_properly_guarded
= false;
1769 if (pointer_set_insert (visited_phis
, phi
))
1772 phi_bb
= gimple_bb (phi
);
1774 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
1777 has_valid_preds
= find_predicates (&preds
, &num_preds
,
1780 if (!has_valid_preds
)
1782 destroy_predicate_vecs (num_preds
, preds
);
1787 dump_predicates (use_stmt
, num_preds
, preds
,
1790 has_valid_preds
= find_def_preds (&def_preds
,
1791 &num_def_preds
, phi
);
1793 if (has_valid_preds
)
1797 dump_predicates (phi
, num_def_preds
, def_preds
,
1798 "Operand defs of phi ");
1800 normed
= normalize_preds (def_preds
, &num_def_preds
);
1801 if (normed
&& dump_file
)
1803 fprintf (dump_file
, "\nNormalized to\n");
1804 dump_predicates (phi
, num_def_preds
, def_preds
,
1805 "Operand defs of phi ");
1807 is_properly_guarded
=
1808 is_superset_of (def_preds
, num_def_preds
,
1812 /* further prune the dead incoming phi edges. */
1813 if (!is_properly_guarded
)
1815 = use_pred_not_overlap_with_undef_path_pred (
1816 num_preds
, preds
, phi
, uninit_opnds
, visited_phis
);
1818 destroy_predicate_vecs (num_preds
, preds
);
1819 destroy_predicate_vecs (num_def_preds
, def_preds
);
1820 return is_properly_guarded
;
1823 /* Searches through all uses of a potentially
1824 uninitialized variable defined by PHI and returns a use
1825 statement if the use is not properly guarded. It returns
1826 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1827 holding the position(s) of uninit PHI operands. WORKLIST
1828 is the vector of candidate phis that may be updated by this
1829 function. ADDED_TO_WORKLIST is the pointer set tracking
1830 if the new phi is already in the worklist. */
1833 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
1834 vec
<gimple
> *worklist
,
1835 struct pointer_set_t
*added_to_worklist
)
1838 use_operand_p use_p
;
1840 imm_use_iterator iter
;
1842 phi_result
= gimple_phi_result (phi
);
1844 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
1846 struct pointer_set_t
*visited_phis
;
1849 use_stmt
= USE_STMT (use_p
);
1850 if (is_gimple_debug (use_stmt
))
1853 visited_phis
= pointer_set_create ();
1855 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1856 use_bb
= gimple_phi_arg_edge (use_stmt
,
1857 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
1859 use_bb
= gimple_bb (use_stmt
);
1861 if (is_use_properly_guarded (use_stmt
,
1867 pointer_set_destroy (visited_phis
);
1870 pointer_set_destroy (visited_phis
);
1872 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1874 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
1875 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1877 /* Found one real use, return. */
1878 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1881 /* Found a phi use that is not guarded,
1882 add the phi to the worklist. */
1883 if (!pointer_set_insert (added_to_worklist
,
1886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1888 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
1889 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1892 worklist
->safe_push (use_stmt
);
1893 pointer_set_insert (possibly_undefined_names
, phi_result
);
1900 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1901 and gives warning if there exists a runtime path from the entry to a
1902 use of the PHI def that does not contain a definition. In other words,
1903 the warning is on the real use. The more dead paths that can be pruned
1904 by the compiler, the fewer false positives the warning is. WORKLIST
1905 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1906 a pointer set tracking if the new phi is added to the worklist or not. */
1909 warn_uninitialized_phi (gimple phi
, vec
<gimple
> *worklist
,
1910 struct pointer_set_t
*added_to_worklist
)
1912 unsigned uninit_opnds
;
1913 gimple uninit_use_stmt
= 0;
1916 /* Don't look at virtual operands. */
1917 if (virtual_operand_p (gimple_phi_result (phi
)))
1920 uninit_opnds
= compute_uninit_opnds_pos (phi
);
1922 if (MASK_EMPTY (uninit_opnds
))
1925 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1927 fprintf (dump_file
, "[CHECK]: examining phi: ");
1928 print_gimple_stmt (dump_file
, phi
, 0, 0);
1931 /* Now check if we have any use of the value without proper guard. */
1932 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
1933 worklist
, added_to_worklist
);
1935 /* All uses are properly guarded. */
1936 if (!uninit_use_stmt
)
1939 uninit_op
= gimple_phi_arg_def (phi
, MASK_FIRST_SET_BIT (uninit_opnds
));
1940 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
1942 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
1943 SSA_NAME_VAR (uninit_op
),
1944 "%qD may be used uninitialized in this function",
1950 /* Entry point to the late uninitialized warning pass. */
1953 execute_late_warn_uninitialized (void)
1956 gimple_stmt_iterator gsi
;
1957 vec
<gimple
> worklist
= vNULL
;
1958 struct pointer_set_t
*added_to_worklist
;
1960 calculate_dominance_info (CDI_DOMINATORS
);
1961 calculate_dominance_info (CDI_POST_DOMINATORS
);
1962 /* Re-do the plain uninitialized variable check, as optimization may have
1963 straightened control flow. Do this first so that we don't accidentally
1964 get a "may be" warning when we'd have seen an "is" warning later. */
1965 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1967 timevar_push (TV_TREE_UNINIT
);
1969 possibly_undefined_names
= pointer_set_create ();
1970 added_to_worklist
= pointer_set_create ();
1972 /* Initialize worklist */
1974 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1976 gimple phi
= gsi_stmt (gsi
);
1979 n
= gimple_phi_num_args (phi
);
1981 /* Don't look at virtual operands. */
1982 if (virtual_operand_p (gimple_phi_result (phi
)))
1985 for (i
= 0; i
< n
; ++i
)
1987 tree op
= gimple_phi_arg_def (phi
, i
);
1988 if (TREE_CODE (op
) == SSA_NAME
1989 && ssa_undefined_value_p (op
))
1991 worklist
.safe_push (phi
);
1992 pointer_set_insert (added_to_worklist
, phi
);
1993 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1995 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
1996 print_gimple_stmt (dump_file
, phi
, 0, 0);
2003 while (worklist
.length () != 0)
2006 cur_phi
= worklist
.pop ();
2007 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2010 worklist
.release ();
2011 pointer_set_destroy (added_to_worklist
);
2012 pointer_set_destroy (possibly_undefined_names
);
2013 possibly_undefined_names
= NULL
;
2014 free_dominance_info (CDI_POST_DOMINATORS
);
2015 timevar_pop (TV_TREE_UNINIT
);
2020 gate_warn_uninitialized (void)
2022 return warn_uninitialized
!= 0;
2025 struct gimple_opt_pass pass_late_warn_uninitialized
=
2029 "uninit", /* name */
2030 OPTGROUP_NONE
, /* optinfo_flags */
2031 gate_warn_uninitialized
, /* gate */
2032 execute_late_warn_uninitialized
, /* execute */
2035 0, /* static_pass_number */
2036 TV_NONE
, /* tv_id */
2037 PROP_ssa
, /* properties_required */
2038 0, /* properties_provided */
2039 0, /* properties_destroyed */
2040 0, /* todo_flags_start */
2041 0 /* todo_flags_finish */