1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2013 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "basic-block.h"
30 #include "gimple-pretty-print.h"
32 #include "pointer-set.h"
33 #include "tree-flow.h"
35 #include "tree-inline.h"
37 #include "tree-pass.h"
38 #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 /* Like ssa_undefined_value_p, but don't return true if TREE_NO_WARNING
106 is set on SSA_NAME_VAR. */
109 uninit_undefined_value_p (tree t
)
111 if (!ssa_undefined_value_p (t
))
113 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
118 /* Checks if the operand OPND of PHI is defined by
119 another phi with one operand defined by this PHI,
120 but the rest operands are all defined. If yes,
121 returns true to skip this this operand as being
122 redundant. Can be enhanced to be more general. */
125 can_skip_redundant_opnd (tree opnd
, gimple phi
)
131 phi_def
= gimple_phi_result (phi
);
132 op_def
= SSA_NAME_DEF_STMT (opnd
);
133 if (gimple_code (op_def
) != GIMPLE_PHI
)
135 n
= gimple_phi_num_args (op_def
);
136 for (i
= 0; i
< n
; ++i
)
138 tree op
= gimple_phi_arg_def (op_def
, i
);
139 if (TREE_CODE (op
) != SSA_NAME
)
141 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
148 /* Returns a bit mask holding the positions of arguments in PHI
149 that have empty (or possibly empty) definitions. */
152 compute_uninit_opnds_pos (gimple phi
)
155 unsigned uninit_opnds
= 0;
157 n
= gimple_phi_num_args (phi
);
158 /* Bail out for phi with too many args. */
162 for (i
= 0; i
< n
; ++i
)
164 tree op
= gimple_phi_arg_def (phi
, i
);
165 if (TREE_CODE (op
) == SSA_NAME
166 && uninit_undefined_value_p (op
)
167 && !can_skip_redundant_opnd (op
, phi
))
168 MASK_SET_BIT (uninit_opnds
, i
);
173 /* Find the immediate postdominator PDOM of the specified
174 basic block BLOCK. */
176 static inline basic_block
177 find_pdom (basic_block block
)
179 if (block
== EXIT_BLOCK_PTR
)
180 return EXIT_BLOCK_PTR
;
184 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
186 return EXIT_BLOCK_PTR
;
191 /* Find the immediate DOM of the specified
192 basic block BLOCK. */
194 static inline basic_block
195 find_dom (basic_block block
)
197 if (block
== ENTRY_BLOCK_PTR
)
198 return ENTRY_BLOCK_PTR
;
201 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
203 return ENTRY_BLOCK_PTR
;
208 /* Returns true if BB1 is postdominating BB2 and BB1 is
209 not a loop exit bb. The loop exit bb check is simple and does
210 not cover all cases. */
213 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
215 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
218 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
224 /* Find the closest postdominator of a specified BB, which is control
227 static inline basic_block
228 find_control_equiv_block (basic_block bb
)
232 pdom
= find_pdom (bb
);
234 /* Skip the postdominating bb that is also loop exit. */
235 if (!is_non_loop_exit_postdominating (pdom
, bb
))
238 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
244 #define MAX_NUM_CHAINS 8
245 #define MAX_CHAIN_LEN 5
246 #define MAX_POSTDOM_CHECK 8
248 /* Computes the control dependence chains (paths of edges)
249 for DEP_BB up to the dominating basic block BB (the head node of a
250 chain should be dominated by it). CD_CHAINS is pointer to an
251 array holding the result chains. CUR_CD_CHAIN is the current
252 chain being computed. *NUM_CHAINS is total number of chains. The
253 function returns true if the information is successfully computed,
254 return false if there is no control dependence or not computed. */
257 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
258 vec
<edge
> *cd_chains
,
260 vec
<edge
> *cur_cd_chain
,
266 bool found_cd_chain
= false;
267 size_t cur_chain_len
= 0;
269 if (EDGE_COUNT (bb
->succs
) < 2)
272 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
276 /* Could use a set instead. */
277 cur_chain_len
= cur_cd_chain
->length ();
278 if (cur_chain_len
> MAX_CHAIN_LEN
)
281 for (i
= 0; i
< cur_chain_len
; i
++)
283 edge e
= (*cur_cd_chain
)[i
];
284 /* cycle detected. */
289 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
292 int post_dom_check
= 0;
293 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
297 cur_cd_chain
->safe_push (e
);
298 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
302 /* Found a direct control dependence. */
303 if (*num_chains
< MAX_NUM_CHAINS
)
305 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
308 found_cd_chain
= true;
309 /* check path from next edge. */
313 /* Now check if DEP_BB is indirectly control dependent on BB. */
314 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
315 num_chains
, cur_cd_chain
, num_calls
))
317 found_cd_chain
= true;
321 cd_bb
= find_pdom (cd_bb
);
323 if (cd_bb
== EXIT_BLOCK_PTR
|| post_dom_check
> MAX_POSTDOM_CHECK
)
326 cur_cd_chain
->pop ();
327 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
329 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
331 return found_cd_chain
;
334 typedef struct use_pred_info
342 /* Converts the chains of control dependence edges into a set of
343 predicates. A control dependence chain is represented by a vector
344 edges. DEP_CHAINS points to an array of dependence chains.
345 NUM_CHAINS is the size of the chain array. One edge in a dependence
346 chain is mapped to predicate expression represented by use_pred_info_t
347 type. One dependence chain is converted to a composite predicate that
348 is the result of AND operation of use_pred_info_t mapped to each edge.
349 A composite predicate is presented by a vector of use_pred_info_t. On
350 return, *PREDS points to the resulting array of composite predicates.
351 *NUM_PREDS is the number of composite predictes. */
354 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
356 vec
<use_pred_info_t
> **preds
,
359 bool has_valid_pred
= false;
361 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
364 /* Now convert the control dep chain into a set
366 typedef vec
<use_pred_info_t
> vec_use_pred_info_t_heap
;
367 *preds
= XCNEWVEC (vec_use_pred_info_t_heap
, num_chains
);
368 *num_preds
= num_chains
;
370 for (i
= 0; i
< num_chains
; i
++)
372 vec
<edge
> one_cd_chain
= dep_chains
[i
];
374 has_valid_pred
= false;
375 for (j
= 0; j
< one_cd_chain
.length (); j
++)
378 gimple_stmt_iterator gsi
;
379 basic_block guard_bb
;
380 use_pred_info_t one_pred
;
385 gsi
= gsi_last_bb (guard_bb
);
388 has_valid_pred
= false;
391 cond_stmt
= gsi_stmt (gsi
);
392 if (gimple_code (cond_stmt
) == GIMPLE_CALL
393 && EDGE_COUNT (e
->src
->succs
) >= 2)
395 /* Ignore EH edge. Can add assertion
396 on the other edge's flag. */
399 /* Skip if there is essentially one succesor. */
400 if (EDGE_COUNT (e
->src
->succs
) == 2)
406 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
408 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
417 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
419 has_valid_pred
= false;
422 one_pred
= XNEW (struct use_pred_info
);
423 one_pred
->cond
= cond_stmt
;
424 one_pred
->invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
425 (*preds
)[i
].safe_push (one_pred
);
426 has_valid_pred
= true;
432 return has_valid_pred
;
435 /* Computes all control dependence chains for USE_BB. The control
436 dependence chains are then converted to an array of composite
437 predicates pointed to by PREDS. PHI_BB is the basic block of
438 the phi whose result is used in USE_BB. */
441 find_predicates (vec
<use_pred_info_t
> **preds
,
446 size_t num_chains
= 0, i
;
448 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
449 vec
<edge
> cur_chain
= vNULL
;
450 bool has_valid_pred
= false;
451 basic_block cd_root
= 0;
453 /* First find the closest bb that is control equivalent to PHI_BB
454 that also dominates USE_BB. */
456 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
458 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
459 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
460 cd_root
= ctrl_eq_bb
;
465 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
466 &cur_chain
, &num_calls
);
469 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
,
471 /* Free individual chain */
472 cur_chain
.release ();
473 for (i
= 0; i
< num_chains
; i
++)
474 dep_chains
[i
].release ();
475 return has_valid_pred
;
478 /* Computes the set of incoming edges of PHI that have non empty
479 definitions of a phi chain. The collection will be done
480 recursively on operands that are defined by phis. CD_ROOT
481 is the control dependence root. *EDGES holds the result, and
482 VISITED_PHIS is a pointer set for detecting cycles. */
485 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
487 struct pointer_set_t
*visited_phis
)
493 if (pointer_set_insert (visited_phis
, phi
))
496 n
= gimple_phi_num_args (phi
);
497 for (i
= 0; i
< n
; i
++)
499 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
500 opnd
= gimple_phi_arg_def (phi
, i
);
502 if (TREE_CODE (opnd
) != SSA_NAME
)
504 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
506 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
507 print_gimple_stmt (dump_file
, phi
, 0, 0);
509 edges
->safe_push (opnd_edge
);
513 gimple def
= SSA_NAME_DEF_STMT (opnd
);
515 if (gimple_code (def
) == GIMPLE_PHI
516 && dominated_by_p (CDI_DOMINATORS
,
517 gimple_bb (def
), cd_root
))
518 collect_phi_def_edges (def
, cd_root
, edges
,
520 else if (!uninit_undefined_value_p (opnd
))
522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
524 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
525 print_gimple_stmt (dump_file
, phi
, 0, 0);
527 edges
->safe_push (opnd_edge
);
533 /* For each use edge of PHI, computes all control dependence chains.
534 The control dependence chains are then converted to an array of
535 composite predicates pointed to by PREDS. */
538 find_def_preds (vec
<use_pred_info_t
> **preds
,
539 size_t *num_preds
, gimple phi
)
541 size_t num_chains
= 0, i
, n
;
542 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
543 vec
<edge
> cur_chain
= vNULL
;
544 vec
<edge
> def_edges
= vNULL
;
545 bool has_valid_pred
= false;
546 basic_block phi_bb
, cd_root
= 0;
547 struct pointer_set_t
*visited_phis
;
549 phi_bb
= gimple_bb (phi
);
550 /* First find the closest dominating bb to be
551 the control dependence root */
552 cd_root
= find_dom (phi_bb
);
556 visited_phis
= pointer_set_create ();
557 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
558 pointer_set_destroy (visited_phis
);
560 n
= def_edges
.length ();
564 for (i
= 0; i
< n
; i
++)
570 opnd_edge
= def_edges
[i
];
571 prev_nc
= num_chains
;
572 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
573 &num_chains
, &cur_chain
, &num_calls
);
575 /* Now update the newly added chains with
576 the phi operand edge: */
577 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
579 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
580 dep_chains
[num_chains
++] = vNULL
;
581 for (j
= prev_nc
; j
< num_chains
; j
++)
582 dep_chains
[j
].safe_push (opnd_edge
);
586 /* Free individual chain */
587 cur_chain
.release ();
590 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
,
592 for (i
= 0; i
< num_chains
; i
++)
593 dep_chains
[i
].release ();
594 return has_valid_pred
;
597 /* Dumps the predicates (PREDS) for USESTMT. */
600 dump_predicates (gimple usestmt
, size_t num_preds
,
601 vec
<use_pred_info_t
> *preds
,
605 vec
<use_pred_info_t
> one_pred_chain
;
606 fprintf (dump_file
, msg
);
607 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
608 fprintf (dump_file
, "is guarded by :\n");
609 /* do some dumping here: */
610 for (i
= 0; i
< num_preds
; i
++)
614 one_pred_chain
= preds
[i
];
615 np
= one_pred_chain
.length ();
617 for (j
= 0; j
< np
; j
++)
619 use_pred_info_t one_pred
621 if (one_pred
->invert
)
622 fprintf (dump_file
, " (.NOT.) ");
623 print_gimple_stmt (dump_file
, one_pred
->cond
, 0, 0);
625 fprintf (dump_file
, "(.AND.)\n");
627 if (i
< num_preds
- 1)
628 fprintf (dump_file
, "(.OR.)\n");
632 /* Destroys the predicate set *PREDS. */
635 destroy_predicate_vecs (size_t n
,
636 vec
<use_pred_info_t
> * preds
)
639 for (i
= 0; i
< n
; i
++)
641 for (j
= 0; j
< preds
[i
].length (); j
++)
649 /* Computes the 'normalized' conditional code with operand
650 swapping and condition inversion. */
652 static enum tree_code
653 get_cmp_code (enum tree_code orig_cmp_code
,
654 bool swap_cond
, bool invert
)
656 enum tree_code tc
= orig_cmp_code
;
659 tc
= swap_tree_comparison (orig_cmp_code
);
661 tc
= invert_tree_comparison (tc
, false);
678 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
679 all values in the range satisfies (x CMPC BOUNDARY) == true. */
682 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
684 bool inverted
= false;
688 /* Only handle integer constant here. */
689 if (TREE_CODE (val
) != INTEGER_CST
690 || TREE_CODE (boundary
) != INTEGER_CST
)
693 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
695 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
698 cmpc
= invert_tree_comparison (cmpc
, false);
705 result
= tree_int_cst_equal (val
, boundary
);
706 else if (cmpc
== LT_EXPR
)
707 result
= INT_CST_LT_UNSIGNED (val
, boundary
);
710 gcc_assert (cmpc
== LE_EXPR
);
711 result
= (tree_int_cst_equal (val
, boundary
)
712 || INT_CST_LT_UNSIGNED (val
, boundary
));
718 result
= tree_int_cst_equal (val
, boundary
);
719 else if (cmpc
== LT_EXPR
)
720 result
= INT_CST_LT (val
, boundary
);
723 gcc_assert (cmpc
== LE_EXPR
);
724 result
= (tree_int_cst_equal (val
, boundary
)
725 || INT_CST_LT (val
, boundary
));
735 /* Returns true if PRED is common among all the predicate
736 chains (PREDS) (and therefore can be factored out).
737 NUM_PRED_CHAIN is the size of array PREDS. */
740 find_matching_predicate_in_rest_chains (use_pred_info_t pred
,
741 vec
<use_pred_info_t
> *preds
,
742 size_t num_pred_chains
)
747 if (num_pred_chains
== 1)
750 for (i
= 1; i
< num_pred_chains
; i
++)
753 vec
<use_pred_info_t
> one_chain
= preds
[i
];
754 n
= one_chain
.length ();
755 for (j
= 0; j
< n
; j
++)
757 use_pred_info_t pred2
759 /* can relax the condition comparison to not
760 use address comparison. However, the most common
761 case is that multiple control dependent paths share
762 a common path prefix, so address comparison should
765 if (pred2
->cond
== pred
->cond
766 && pred2
->invert
== pred
->invert
)
778 /* Forward declaration. */
780 is_use_properly_guarded (gimple use_stmt
,
783 unsigned uninit_opnds
,
784 struct pointer_set_t
*visited_phis
);
786 /* Returns true if all uninitialized opnds are pruned. Returns false
787 otherwise. PHI is the phi node with uninitialized operands,
788 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
789 FLAG_DEF is the statement defining the flag guarding the use of the
790 PHI output, BOUNDARY_CST is the const value used in the predicate
791 associated with the flag, CMP_CODE is the comparison code used in
792 the predicate, VISITED_PHIS is the pointer set of phis visited, and
793 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
799 flag_1 = phi <0, 1> // (1)
800 var_1 = phi <undef, some_val>
804 flag_2 = phi <0, flag_1, flag_1> // (2)
805 var_2 = phi <undef, var_1, var_1>
812 Because some flag arg in (1) is not constant, if we do not look into the
813 flag phis recursively, it is conservatively treated as unknown and var_1
814 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
815 a false warning will be emitted. Checking recursively into (1), the compiler can
816 find out that only some_val (which is defined) can flow into (3) which is OK.
821 prune_uninit_phi_opnds_in_unrealizable_paths (
822 gimple phi
, unsigned uninit_opnds
,
823 gimple flag_def
, tree boundary_cst
,
824 enum tree_code cmp_code
,
825 struct pointer_set_t
*visited_phis
,
826 bitmap
*visited_flag_phis
)
830 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
834 if (!MASK_TEST_BIT (uninit_opnds
, i
))
837 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
838 if (!is_gimple_constant (flag_arg
))
840 gimple flag_arg_def
, phi_arg_def
;
842 unsigned uninit_opnds_arg_phi
;
844 if (TREE_CODE (flag_arg
) != SSA_NAME
)
846 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
847 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
850 phi_arg
= gimple_phi_arg_def (phi
, i
);
851 if (TREE_CODE (phi_arg
) != SSA_NAME
)
854 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
855 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
858 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
861 if (!*visited_flag_phis
)
862 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
864 if (bitmap_bit_p (*visited_flag_phis
,
865 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
868 bitmap_set_bit (*visited_flag_phis
,
869 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
871 /* Now recursively prune the uninitialized phi args. */
872 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
873 if (!prune_uninit_phi_opnds_in_unrealizable_paths (
874 phi_arg_def
, uninit_opnds_arg_phi
,
875 flag_arg_def
, boundary_cst
, cmp_code
,
876 visited_phis
, visited_flag_phis
))
879 bitmap_clear_bit (*visited_flag_phis
,
880 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
884 /* Now check if the constant is in the guarded range. */
885 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
890 /* Now that we know that this undefined edge is not
891 pruned. If the operand is defined by another phi,
892 we can further prune the incoming edges of that
893 phi by checking the predicates of this operands. */
895 opnd
= gimple_phi_arg_def (phi
, i
);
896 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
897 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
900 unsigned uninit_opnds2
901 = compute_uninit_opnds_pos (opnd_def
);
902 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
903 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
904 if (!is_use_properly_guarded (phi
,
919 /* A helper function that determines if the predicate set
920 of the use is not overlapping with that of the uninit paths.
921 The most common senario of guarded use is in Example 1:
934 The real world examples are usually more complicated, but similar
935 and usually result from inlining:
937 bool init_func (int * x)
956 Another possible use scenario is in the following trivial example:
968 Predicate analysis needs to compute the composite predicate:
970 1) 'x' use predicate: (n > 0) .AND. (m < 2)
971 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
972 (the predicate chain for phi operand defs can be computed
973 starting from a bb that is control equivalent to the phi's
974 bb and is dominating the operand def.)
976 and check overlapping:
977 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
980 This implementation provides framework that can handle
981 scenarios. (Note that many simple cases are handled properly
982 without the predicate analysis -- this is due to jump threading
983 transformation which eliminates the merge point thus makes
984 path sensitive analysis unnecessary.)
986 NUM_PREDS is the number is the number predicate chains, PREDS is
987 the array of chains, PHI is the phi node whose incoming (undefined)
988 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
989 uninit operand positions. VISITED_PHIS is the pointer set of phi
990 stmts being checked. */
994 use_pred_not_overlap_with_undef_path_pred (
996 vec
<use_pred_info_t
> *preds
,
997 gimple phi
, unsigned uninit_opnds
,
998 struct pointer_set_t
*visited_phis
)
1001 gimple flag_def
= 0;
1002 tree boundary_cst
= 0;
1003 enum tree_code cmp_code
;
1004 bool swap_cond
= false;
1005 bool invert
= false;
1006 vec
<use_pred_info_t
> the_pred_chain
;
1007 bitmap visited_flag_phis
= NULL
;
1008 bool all_pruned
= false;
1010 gcc_assert (num_preds
> 0);
1011 /* Find within the common prefix of multiple predicate chains
1012 a predicate that is a comparison of a flag variable against
1014 the_pred_chain
= preds
[0];
1015 n
= the_pred_chain
.length ();
1016 for (i
= 0; i
< n
; i
++)
1019 tree cond_lhs
, cond_rhs
, flag
= 0;
1021 use_pred_info_t the_pred
1022 = the_pred_chain
[i
];
1024 cond
= the_pred
->cond
;
1025 invert
= the_pred
->invert
;
1026 cond_lhs
= gimple_cond_lhs (cond
);
1027 cond_rhs
= gimple_cond_rhs (cond
);
1028 cmp_code
= gimple_cond_code (cond
);
1030 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1031 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1033 boundary_cst
= cond_rhs
;
1036 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1037 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1039 boundary_cst
= cond_lhs
;
1047 flag_def
= SSA_NAME_DEF_STMT (flag
);
1052 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1053 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1054 && find_matching_predicate_in_rest_chains (
1055 the_pred
, preds
, num_preds
))
1064 /* Now check all the uninit incoming edge has a constant flag value
1065 that is in conflict with the use guard/predicate. */
1066 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1068 if (cmp_code
== ERROR_MARK
)
1071 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1077 &visited_flag_phis
);
1079 if (visited_flag_phis
)
1080 BITMAP_FREE (visited_flag_phis
);
1085 /* Returns true if TC is AND or OR */
1088 is_and_or_or (enum tree_code tc
, tree typ
)
1090 return (tc
== BIT_IOR_EXPR
1091 || (tc
== BIT_AND_EXPR
1092 && (typ
== 0 || TREE_CODE (typ
) == BOOLEAN_TYPE
)));
1095 typedef struct norm_cond
1098 enum tree_code cond_code
;
1103 /* Normalizes gimple condition COND. The normalization follows
1104 UD chains to form larger condition expression trees. NORM_COND
1105 holds the normalized result. COND_CODE is the logical opcode
1106 (AND or OR) of the normalized tree. */
1109 normalize_cond_1 (gimple cond
,
1110 norm_cond_t norm_cond
,
1111 enum tree_code cond_code
)
1113 enum gimple_code gc
;
1114 enum tree_code cur_cond_code
;
1117 gc
= gimple_code (cond
);
1118 if (gc
!= GIMPLE_ASSIGN
)
1120 norm_cond
->conds
.safe_push (cond
);
1124 cur_cond_code
= gimple_assign_rhs_code (cond
);
1125 rhs1
= gimple_assign_rhs1 (cond
);
1126 rhs2
= gimple_assign_rhs2 (cond
);
1127 if (cur_cond_code
== NE_EXPR
)
1129 if (integer_zerop (rhs2
)
1130 && (TREE_CODE (rhs1
) == SSA_NAME
))
1132 SSA_NAME_DEF_STMT (rhs1
),
1133 norm_cond
, cond_code
);
1134 else if (integer_zerop (rhs1
)
1135 && (TREE_CODE (rhs2
) == SSA_NAME
))
1137 SSA_NAME_DEF_STMT (rhs2
),
1138 norm_cond
, cond_code
);
1140 norm_cond
->conds
.safe_push (cond
);
1145 if (is_and_or_or (cur_cond_code
, TREE_TYPE (rhs1
))
1146 && (cond_code
== cur_cond_code
|| cond_code
== ERROR_MARK
)
1147 && (TREE_CODE (rhs1
) == SSA_NAME
&& TREE_CODE (rhs2
) == SSA_NAME
))
1149 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1
),
1150 norm_cond
, cur_cond_code
);
1151 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2
),
1152 norm_cond
, cur_cond_code
);
1153 norm_cond
->cond_code
= cur_cond_code
;
1156 norm_cond
->conds
.safe_push (cond
);
1159 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1160 if COND needs to be inverted or not. */
1163 normalize_cond (gimple cond
, norm_cond_t norm_cond
, bool invert
)
1165 enum tree_code cond_code
;
1167 norm_cond
->cond_code
= ERROR_MARK
;
1168 norm_cond
->invert
= false;
1169 norm_cond
->conds
.create (0);
1170 gcc_assert (gimple_code (cond
) == GIMPLE_COND
);
1171 cond_code
= gimple_cond_code (cond
);
1173 cond_code
= invert_tree_comparison (cond_code
, false);
1175 if (cond_code
== NE_EXPR
)
1177 if (integer_zerop (gimple_cond_rhs (cond
))
1178 && (TREE_CODE (gimple_cond_lhs (cond
)) == SSA_NAME
))
1180 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
)),
1181 norm_cond
, ERROR_MARK
);
1182 else if (integer_zerop (gimple_cond_lhs (cond
))
1183 && (TREE_CODE (gimple_cond_rhs (cond
)) == SSA_NAME
))
1185 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond
)),
1186 norm_cond
, ERROR_MARK
);
1189 norm_cond
->conds
.safe_push (cond
);
1190 norm_cond
->invert
= invert
;
1195 norm_cond
->conds
.safe_push (cond
);
1196 norm_cond
->invert
= invert
;
1199 gcc_assert (norm_cond
->conds
.length () == 1
1200 || is_and_or_or (norm_cond
->cond_code
, NULL
));
1203 /* Returns true if the domain for condition COND1 is a subset of
1204 COND2. REVERSE is a flag. when it is true the function checks
1205 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1206 to indicate if COND1 and COND2 need to be inverted or not. */
1209 is_gcond_subset_of (gimple cond1
, bool invert1
,
1210 gimple cond2
, bool invert2
,
1213 enum gimple_code gc1
, gc2
;
1214 enum tree_code cond1_code
, cond2_code
;
1216 tree cond1_lhs
, cond1_rhs
, cond2_lhs
, cond2_rhs
;
1218 /* Take the short cut. */
1229 gc1
= gimple_code (cond1
);
1230 gc2
= gimple_code (cond2
);
1232 if ((gc1
!= GIMPLE_ASSIGN
&& gc1
!= GIMPLE_COND
)
1233 || (gc2
!= GIMPLE_ASSIGN
&& gc2
!= GIMPLE_COND
))
1234 return cond1
== cond2
;
1236 cond1_code
= ((gc1
== GIMPLE_ASSIGN
)
1237 ? gimple_assign_rhs_code (cond1
)
1238 : gimple_cond_code (cond1
));
1240 cond2_code
= ((gc2
== GIMPLE_ASSIGN
)
1241 ? gimple_assign_rhs_code (cond2
)
1242 : gimple_cond_code (cond2
));
1244 if (TREE_CODE_CLASS (cond1_code
) != tcc_comparison
1245 || TREE_CODE_CLASS (cond2_code
) != tcc_comparison
)
1249 cond1_code
= invert_tree_comparison (cond1_code
, false);
1251 cond2_code
= invert_tree_comparison (cond2_code
, false);
1253 cond1_lhs
= ((gc1
== GIMPLE_ASSIGN
)
1254 ? gimple_assign_rhs1 (cond1
)
1255 : gimple_cond_lhs (cond1
));
1256 cond1_rhs
= ((gc1
== GIMPLE_ASSIGN
)
1257 ? gimple_assign_rhs2 (cond1
)
1258 : gimple_cond_rhs (cond1
));
1259 cond2_lhs
= ((gc2
== GIMPLE_ASSIGN
)
1260 ? gimple_assign_rhs1 (cond2
)
1261 : gimple_cond_lhs (cond2
));
1262 cond2_rhs
= ((gc2
== GIMPLE_ASSIGN
)
1263 ? gimple_assign_rhs2 (cond2
)
1264 : gimple_cond_rhs (cond2
));
1266 /* Assuming const operands have been swapped to the
1267 rhs at this point of the analysis. */
1269 if (cond1_lhs
!= cond2_lhs
)
1272 if (!is_gimple_constant (cond1_rhs
)
1273 || TREE_CODE (cond1_rhs
) != INTEGER_CST
)
1274 return (cond1_rhs
== cond2_rhs
);
1276 if (!is_gimple_constant (cond2_rhs
)
1277 || TREE_CODE (cond2_rhs
) != INTEGER_CST
)
1278 return (cond1_rhs
== cond2_rhs
);
1280 if (cond1_code
== EQ_EXPR
)
1281 return is_value_included_in (cond1_rhs
,
1282 cond2_rhs
, cond2_code
);
1283 if (cond1_code
== NE_EXPR
|| cond2_code
== EQ_EXPR
)
1284 return ((cond2_code
== cond1_code
)
1285 && tree_int_cst_equal (cond1_rhs
, cond2_rhs
));
1287 if (((cond1_code
== GE_EXPR
|| cond1_code
== GT_EXPR
)
1288 && (cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
))
1289 || ((cond1_code
== LE_EXPR
|| cond1_code
== LT_EXPR
)
1290 && (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
)))
1293 if (cond1_code
!= GE_EXPR
&& cond1_code
!= GT_EXPR
1294 && cond1_code
!= LE_EXPR
&& cond1_code
!= LT_EXPR
)
1297 if (cond1_code
== GT_EXPR
)
1299 cond1_code
= GE_EXPR
;
1300 cond1_rhs
= fold_binary (PLUS_EXPR
, TREE_TYPE (cond1_rhs
),
1302 fold_convert (TREE_TYPE (cond1_rhs
),
1305 else if (cond1_code
== LT_EXPR
)
1307 cond1_code
= LE_EXPR
;
1308 cond1_rhs
= fold_binary (MINUS_EXPR
, TREE_TYPE (cond1_rhs
),
1310 fold_convert (TREE_TYPE (cond1_rhs
),
1317 gcc_assert (cond1_code
== GE_EXPR
|| cond1_code
== LE_EXPR
);
1319 if (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
||
1320 cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
)
1321 return is_value_included_in (cond1_rhs
,
1322 cond2_rhs
, cond2_code
);
1323 else if (cond2_code
== NE_EXPR
)
1325 (is_value_included_in (cond1_rhs
,
1326 cond2_rhs
, cond2_code
)
1327 && !is_value_included_in (cond2_rhs
,
1328 cond1_rhs
, cond1_code
));
1332 /* Returns true if the domain of the condition expression
1333 in COND is a subset of any of the sub-conditions
1334 of the normalized condtion NORM_COND. INVERT is a flag
1335 to indicate of the COND needs to be inverted.
1336 REVERSE is a flag. When it is true, the check is reversed --
1337 it returns true if COND is a superset of any of the subconditions
1341 is_subset_of_any (gimple cond
, bool invert
,
1342 norm_cond_t norm_cond
, bool reverse
)
1345 size_t len
= norm_cond
->conds
.length ();
1347 for (i
= 0; i
< len
; i
++)
1349 if (is_gcond_subset_of (cond
, invert
,
1350 norm_cond
->conds
[i
],
1357 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1358 expressions (formed by following UD chains not control
1359 dependence chains). The function returns true of domain
1360 of and expression NORM_COND1 is a subset of NORM_COND2's.
1361 The implementation is conservative, and it returns false if
1362 it the inclusion relationship may not hold. */
1365 is_or_set_subset_of (norm_cond_t norm_cond1
,
1366 norm_cond_t norm_cond2
)
1369 size_t len
= norm_cond1
->conds
.length ();
1371 for (i
= 0; i
< len
; i
++)
1373 if (!is_subset_of_any (norm_cond1
->conds
[i
],
1374 false, norm_cond2
, false))
1380 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1381 expressions (formed by following UD chains not control
1382 dependence chains). The function returns true of domain
1383 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1386 is_and_set_subset_of (norm_cond_t norm_cond1
,
1387 norm_cond_t norm_cond2
)
1390 size_t len
= norm_cond2
->conds
.length ();
1392 for (i
= 0; i
< len
; i
++)
1394 if (!is_subset_of_any (norm_cond2
->conds
[i
],
1395 false, norm_cond1
, true))
1401 /* Returns true of the domain if NORM_COND1 is a subset
1402 of that of NORM_COND2. Returns false if it can not be
1406 is_norm_cond_subset_of (norm_cond_t norm_cond1
,
1407 norm_cond_t norm_cond2
)
1410 enum tree_code code1
, code2
;
1412 code1
= norm_cond1
->cond_code
;
1413 code2
= norm_cond2
->cond_code
;
1415 if (code1
== BIT_AND_EXPR
)
1417 /* Both conditions are AND expressions. */
1418 if (code2
== BIT_AND_EXPR
)
1419 return is_and_set_subset_of (norm_cond1
, norm_cond2
);
1420 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1421 expression. In this case, returns true if any subexpression
1422 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1423 else if (code2
== BIT_IOR_EXPR
)
1426 len1
= norm_cond1
->conds
.length ();
1427 for (i
= 0; i
< len1
; i
++)
1429 gimple cond1
= norm_cond1
->conds
[i
];
1430 if (is_subset_of_any (cond1
, false, norm_cond2
, false))
1437 gcc_assert (code2
== ERROR_MARK
);
1438 gcc_assert (norm_cond2
->conds
.length () == 1);
1439 return is_subset_of_any (norm_cond2
->conds
[0],
1440 norm_cond2
->invert
, norm_cond1
, true);
1443 /* NORM_COND1 is an OR expression */
1444 else if (code1
== BIT_IOR_EXPR
)
1449 return is_or_set_subset_of (norm_cond1
, norm_cond2
);
1453 gcc_assert (code1
== ERROR_MARK
);
1454 gcc_assert (norm_cond1
->conds
.length () == 1);
1455 /* Conservatively returns false if NORM_COND1 is non-decomposible
1456 and NORM_COND2 is an AND expression. */
1457 if (code2
== BIT_AND_EXPR
)
1460 if (code2
== BIT_IOR_EXPR
)
1461 return is_subset_of_any (norm_cond1
->conds
[0],
1462 norm_cond1
->invert
, norm_cond2
, false);
1464 gcc_assert (code2
== ERROR_MARK
);
1465 gcc_assert (norm_cond2
->conds
.length () == 1);
1466 return is_gcond_subset_of (norm_cond1
->conds
[0],
1468 norm_cond2
->conds
[0],
1469 norm_cond2
->invert
, false);
1473 /* Returns true of the domain of single predicate expression
1474 EXPR1 is a subset of that of EXPR2. Returns false if it
1475 can not be proved. */
1478 is_pred_expr_subset_of (use_pred_info_t expr1
,
1479 use_pred_info_t expr2
)
1481 gimple cond1
, cond2
;
1482 enum tree_code code1
, code2
;
1483 struct norm_cond norm_cond1
, norm_cond2
;
1484 bool is_subset
= false;
1486 cond1
= expr1
->cond
;
1487 cond2
= expr2
->cond
;
1488 code1
= gimple_cond_code (cond1
);
1489 code2
= gimple_cond_code (cond2
);
1492 code1
= invert_tree_comparison (code1
, false);
1494 code2
= invert_tree_comparison (code2
, false);
1496 /* Fast path -- match exactly */
1497 if ((gimple_cond_lhs (cond1
) == gimple_cond_lhs (cond2
))
1498 && (gimple_cond_rhs (cond1
) == gimple_cond_rhs (cond2
))
1499 && (code1
== code2
))
1502 /* Normalize conditions. To keep NE_EXPR, do not invert
1503 with both need inversion. */
1504 normalize_cond (cond1
, &norm_cond1
, (expr1
->invert
));
1505 normalize_cond (cond2
, &norm_cond2
, (expr2
->invert
));
1507 is_subset
= is_norm_cond_subset_of (&norm_cond1
, &norm_cond2
);
1510 norm_cond1
.conds
.release ();
1511 norm_cond2
.conds
.release ();
1515 /* Returns true if the domain of PRED1 is a subset
1516 of that of PRED2. Returns false if it can not be proved so. */
1519 is_pred_chain_subset_of (vec
<use_pred_info_t
> pred1
,
1520 vec
<use_pred_info_t
> pred2
)
1522 size_t np1
, np2
, i1
, i2
;
1524 np1
= pred1
.length ();
1525 np2
= pred2
.length ();
1527 for (i2
= 0; i2
< np2
; i2
++)
1530 use_pred_info_t info2
1532 for (i1
= 0; i1
< np1
; i1
++)
1534 use_pred_info_t info1
1536 if (is_pred_expr_subset_of (info1
, info2
))
1548 /* Returns true if the domain defined by
1549 one pred chain ONE_PRED is a subset of the domain
1550 of *PREDS. It returns false if ONE_PRED's domain is
1551 not a subset of any of the sub-domains of PREDS (
1552 corresponding to each individual chains in it), even
1553 though it may be still be a subset of whole domain
1554 of PREDS which is the union (ORed) of all its subdomains.
1555 In other words, the result is conservative. */
1558 is_included_in (vec
<use_pred_info_t
> one_pred
,
1559 vec
<use_pred_info_t
> *preds
,
1564 for (i
= 0; i
< n
; i
++)
1566 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1573 /* compares two predicate sets PREDS1 and PREDS2 and returns
1574 true if the domain defined by PREDS1 is a superset
1575 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1576 PREDS2 respectively. The implementation chooses not to build
1577 generic trees (and relying on the folding capability of the
1578 compiler), but instead performs brute force comparison of
1579 individual predicate chains (won't be a compile time problem
1580 as the chains are pretty short). When the function returns
1581 false, it does not necessarily mean *PREDS1 is not a superset
1582 of *PREDS2, but mean it may not be so since the analysis can
1583 not prove it. In such cases, false warnings may still be
1587 is_superset_of (vec
<use_pred_info_t
> *preds1
,
1589 vec
<use_pred_info_t
> *preds2
,
1593 vec
<use_pred_info_t
> one_pred_chain
;
1595 for (i
= 0; i
< n2
; i
++)
1597 one_pred_chain
= preds2
[i
];
1598 if (!is_included_in (one_pred_chain
, preds1
, n1
))
1605 /* Comparison function used by qsort. It is used to
1606 sort predicate chains to allow predicate
1610 pred_chain_length_cmp (const void *p1
, const void *p2
)
1612 use_pred_info_t i1
, i2
;
1613 vec
<use_pred_info_t
> const *chain1
1614 = (vec
<use_pred_info_t
> const *)p1
;
1615 vec
<use_pred_info_t
> const *chain2
1616 = (vec
<use_pred_info_t
> const *)p2
;
1618 if (chain1
->length () != chain2
->length ())
1619 return (chain1
->length () - chain2
->length ());
1624 /* Allow predicates with similar prefix come together. */
1625 if (!i1
->invert
&& i2
->invert
)
1627 else if (i1
->invert
&& !i2
->invert
)
1630 return gimple_uid (i1
->cond
) - gimple_uid (i2
->cond
);
1633 /* x OR (!x AND y) is equivalent to x OR y.
1634 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
1635 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
1636 the number of chains. Returns true if normalization happens. */
1639 normalize_preds (vec
<use_pred_info_t
> *preds
, size_t *n
)
1642 vec
<use_pred_info_t
> pred_chain
;
1643 vec
<use_pred_info_t
> x
= vNULL
;
1644 use_pred_info_t xj
= 0, nxj
= 0;
1649 /* First sort the chains in ascending order of lengths. */
1650 qsort (preds
, *n
, sizeof (void *), pred_chain_length_cmp
);
1651 pred_chain
= preds
[0];
1652 ll
= pred_chain
.length ();
1657 use_pred_info_t xx
, yy
, xx2
, nyy
;
1658 vec
<use_pred_info_t
> pred_chain2
= preds
[1];
1659 if (pred_chain2
.length () != 2)
1662 /* See if simplification x AND y OR x AND !y is possible. */
1665 xx2
= pred_chain2
[0];
1666 nyy
= pred_chain2
[1];
1667 if (gimple_cond_lhs (xx
->cond
) != gimple_cond_lhs (xx2
->cond
)
1668 || gimple_cond_rhs (xx
->cond
) != gimple_cond_rhs (xx2
->cond
)
1669 || gimple_cond_code (xx
->cond
) != gimple_cond_code (xx2
->cond
)
1670 || (xx
->invert
!= xx2
->invert
))
1672 if (gimple_cond_lhs (yy
->cond
) != gimple_cond_lhs (nyy
->cond
)
1673 || gimple_cond_rhs (yy
->cond
) != gimple_cond_rhs (nyy
->cond
)
1674 || gimple_cond_code (yy
->cond
) != gimple_cond_code (nyy
->cond
)
1675 || (yy
->invert
== nyy
->invert
))
1678 /* Now merge the first two chains. */
1682 pred_chain
.release ();
1683 pred_chain2
.release ();
1684 pred_chain
.safe_push (xx
);
1685 preds
[0] = pred_chain
;
1686 for (i
= 1; i
< *n
- 1; i
++)
1687 preds
[i
] = preds
[i
+ 1];
1689 preds
[*n
- 1].create (0);
1696 x
.safe_push (pred_chain
[0]);
1698 /* The loop extracts x1, x2, x3, etc from chains
1699 x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
1700 for (i
= 1; i
< *n
; i
++)
1702 pred_chain
= preds
[i
];
1703 if (pred_chain
.length () != i
+ 1)
1706 for (j
= 0; j
< i
; j
++)
1709 nxj
= pred_chain
[j
];
1711 /* Check if nxj is !xj */
1712 if (gimple_cond_lhs (xj
->cond
) != gimple_cond_lhs (nxj
->cond
)
1713 || gimple_cond_rhs (xj
->cond
) != gimple_cond_rhs (nxj
->cond
)
1714 || gimple_cond_code (xj
->cond
) != gimple_cond_code (nxj
->cond
)
1715 || (xj
->invert
== nxj
->invert
))
1719 x
.safe_push (pred_chain
[i
]);
1722 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
1723 for (j
= 0; j
< *n
; j
++)
1728 t
= XNEW (struct use_pred_info
);
1734 for (i
= 0; i
< *n
; i
++)
1736 pred_chain
= preds
[i
];
1737 for (j
= 0; j
< pred_chain
.length (); j
++)
1738 free (pred_chain
[j
]);
1739 pred_chain
.release ();
1741 pred_chain
.safe_push (x
[i
]);
1742 preds
[i
] = pred_chain
;
1749 /* Computes the predicates that guard the use and checks
1750 if the incoming paths that have empty (or possibly
1751 empty) definition can be pruned/filtered. The function returns
1752 true if it can be determined that the use of PHI's def in
1753 USE_STMT is guarded with a predicate set not overlapping with
1754 predicate sets of all runtime paths that do not have a definition.
1755 Returns false if it is not or it can not be determined. USE_BB is
1756 the bb of the use (for phi operand use, the bb is not the bb of
1757 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1758 is a bit vector. If an operand of PHI is uninitialized, the
1759 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
1760 set of phis being visted. */
1763 is_use_properly_guarded (gimple use_stmt
,
1766 unsigned uninit_opnds
,
1767 struct pointer_set_t
*visited_phis
)
1770 vec
<use_pred_info_t
> *preds
= 0;
1771 vec
<use_pred_info_t
> *def_preds
= 0;
1772 size_t num_preds
= 0, num_def_preds
= 0;
1773 bool has_valid_preds
= false;
1774 bool is_properly_guarded
= false;
1776 if (pointer_set_insert (visited_phis
, phi
))
1779 phi_bb
= gimple_bb (phi
);
1781 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
1784 has_valid_preds
= find_predicates (&preds
, &num_preds
,
1787 if (!has_valid_preds
)
1789 destroy_predicate_vecs (num_preds
, preds
);
1794 dump_predicates (use_stmt
, num_preds
, preds
,
1797 has_valid_preds
= find_def_preds (&def_preds
,
1798 &num_def_preds
, phi
);
1800 if (has_valid_preds
)
1804 dump_predicates (phi
, num_def_preds
, def_preds
,
1805 "Operand defs of phi ");
1807 normed
= normalize_preds (def_preds
, &num_def_preds
);
1808 if (normed
&& dump_file
)
1810 fprintf (dump_file
, "\nNormalized to\n");
1811 dump_predicates (phi
, num_def_preds
, def_preds
,
1812 "Operand defs of phi ");
1814 is_properly_guarded
=
1815 is_superset_of (def_preds
, num_def_preds
,
1819 /* further prune the dead incoming phi edges. */
1820 if (!is_properly_guarded
)
1822 = use_pred_not_overlap_with_undef_path_pred (
1823 num_preds
, preds
, phi
, uninit_opnds
, visited_phis
);
1825 destroy_predicate_vecs (num_preds
, preds
);
1826 destroy_predicate_vecs (num_def_preds
, def_preds
);
1827 return is_properly_guarded
;
1830 /* Searches through all uses of a potentially
1831 uninitialized variable defined by PHI and returns a use
1832 statement if the use is not properly guarded. It returns
1833 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1834 holding the position(s) of uninit PHI operands. WORKLIST
1835 is the vector of candidate phis that may be updated by this
1836 function. ADDED_TO_WORKLIST is the pointer set tracking
1837 if the new phi is already in the worklist. */
1840 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
1841 vec
<gimple
> *worklist
,
1842 struct pointer_set_t
*added_to_worklist
)
1845 use_operand_p use_p
;
1847 imm_use_iterator iter
;
1849 phi_result
= gimple_phi_result (phi
);
1851 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
1853 struct pointer_set_t
*visited_phis
;
1856 use_stmt
= USE_STMT (use_p
);
1857 if (is_gimple_debug (use_stmt
))
1860 visited_phis
= pointer_set_create ();
1862 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1863 use_bb
= gimple_phi_arg_edge (use_stmt
,
1864 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
1866 use_bb
= gimple_bb (use_stmt
);
1868 if (is_use_properly_guarded (use_stmt
,
1874 pointer_set_destroy (visited_phis
);
1877 pointer_set_destroy (visited_phis
);
1879 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1881 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
1882 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1884 /* Found one real use, return. */
1885 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1888 /* Found a phi use that is not guarded,
1889 add the phi to the worklist. */
1890 if (!pointer_set_insert (added_to_worklist
,
1893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1895 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
1896 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1899 worklist
->safe_push (use_stmt
);
1900 pointer_set_insert (possibly_undefined_names
, phi_result
);
1907 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1908 and gives warning if there exists a runtime path from the entry to a
1909 use of the PHI def that does not contain a definition. In other words,
1910 the warning is on the real use. The more dead paths that can be pruned
1911 by the compiler, the fewer false positives the warning is. WORKLIST
1912 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1913 a pointer set tracking if the new phi is added to the worklist or not. */
1916 warn_uninitialized_phi (gimple phi
, vec
<gimple
> *worklist
,
1917 struct pointer_set_t
*added_to_worklist
)
1919 unsigned uninit_opnds
;
1920 gimple uninit_use_stmt
= 0;
1923 /* Don't look at virtual operands. */
1924 if (virtual_operand_p (gimple_phi_result (phi
)))
1927 uninit_opnds
= compute_uninit_opnds_pos (phi
);
1929 if (MASK_EMPTY (uninit_opnds
))
1932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1934 fprintf (dump_file
, "[CHECK]: examining phi: ");
1935 print_gimple_stmt (dump_file
, phi
, 0, 0);
1938 /* Now check if we have any use of the value without proper guard. */
1939 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
1940 worklist
, added_to_worklist
);
1942 /* All uses are properly guarded. */
1943 if (!uninit_use_stmt
)
1946 uninit_op
= gimple_phi_arg_def (phi
, MASK_FIRST_SET_BIT (uninit_opnds
));
1947 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
1949 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
1950 SSA_NAME_VAR (uninit_op
),
1951 "%qD may be used uninitialized in this function",
1957 /* Entry point to the late uninitialized warning pass. */
1960 execute_late_warn_uninitialized (void)
1963 gimple_stmt_iterator gsi
;
1964 vec
<gimple
> worklist
= vNULL
;
1965 struct pointer_set_t
*added_to_worklist
;
1967 calculate_dominance_info (CDI_DOMINATORS
);
1968 calculate_dominance_info (CDI_POST_DOMINATORS
);
1969 /* Re-do the plain uninitialized variable check, as optimization may have
1970 straightened control flow. Do this first so that we don't accidentally
1971 get a "may be" warning when we'd have seen an "is" warning later. */
1972 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1974 timevar_push (TV_TREE_UNINIT
);
1976 possibly_undefined_names
= pointer_set_create ();
1977 added_to_worklist
= pointer_set_create ();
1979 /* Initialize worklist */
1981 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1983 gimple phi
= gsi_stmt (gsi
);
1986 n
= gimple_phi_num_args (phi
);
1988 /* Don't look at virtual operands. */
1989 if (virtual_operand_p (gimple_phi_result (phi
)))
1992 for (i
= 0; i
< n
; ++i
)
1994 tree op
= gimple_phi_arg_def (phi
, i
);
1995 if (TREE_CODE (op
) == SSA_NAME
1996 && uninit_undefined_value_p (op
))
1998 worklist
.safe_push (phi
);
1999 pointer_set_insert (added_to_worklist
, phi
);
2000 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2002 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2003 print_gimple_stmt (dump_file
, phi
, 0, 0);
2010 while (worklist
.length () != 0)
2013 cur_phi
= worklist
.pop ();
2014 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2017 worklist
.release ();
2018 pointer_set_destroy (added_to_worklist
);
2019 pointer_set_destroy (possibly_undefined_names
);
2020 possibly_undefined_names
= NULL
;
2021 free_dominance_info (CDI_POST_DOMINATORS
);
2022 timevar_pop (TV_TREE_UNINIT
);
2027 gate_warn_uninitialized (void)
2029 return warn_uninitialized
!= 0;
2032 struct gimple_opt_pass pass_late_warn_uninitialized
=
2036 "uninit", /* name */
2037 OPTGROUP_NONE
, /* optinfo_flags */
2038 gate_warn_uninitialized
, /* gate */
2039 execute_late_warn_uninitialized
, /* execute */
2042 0, /* static_pass_number */
2043 TV_NONE
, /* tv_id */
2044 PROP_ssa
, /* properties_required */
2045 0, /* properties_provided */
2046 0, /* properties_destroyed */
2047 0, /* todo_flags_start */
2048 0 /* todo_flags_finish */