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"
40 /* This implements the pass that does predicate aware warning on uses of
41 possibly uninitialized variables. The pass first collects the set of
42 possibly uninitialized SSA names. For each such name, it walks through
43 all its immediate uses. For each immediate use, it rebuilds the condition
44 expression (the predicate) that guards the use. The predicate is then
45 examined to see if the variable is always defined under that same condition.
46 This is done either by pruning the unrealizable paths that lead to the
47 default definitions or by checking if the predicate set that guards the
48 defining paths is a superset of the use predicate. */
51 /* Pointer set of potentially undefined ssa names, i.e.,
52 ssa names that are defined by phi with operands that
53 are not defined or potentially undefined. */
54 static struct pointer_set_t
*possibly_undefined_names
= 0;
56 /* Bit mask handling macros. */
57 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
58 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
59 #define MASK_EMPTY(mask) (mask == 0)
61 /* Returns the first bit position (starting from LSB)
62 in mask that is non zero. Returns -1 if the mask is empty. */
64 get_mask_first_set_bit (unsigned mask
)
70 while ((mask
& (1 << pos
)) == 0)
75 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
78 /* Return true if T, an SSA_NAME, has an undefined value. */
81 ssa_undefined_value_p (tree t
)
83 tree var
= SSA_NAME_VAR (t
);
87 /* Parameters get their initial value from the function entry. */
88 else if (TREE_CODE (var
) == PARM_DECL
)
90 /* When returning by reference the return address is actually a hidden
92 else if (TREE_CODE (var
) == RESULT_DECL
&& DECL_BY_REFERENCE (var
))
94 /* Hard register variables get their initial value from the ether. */
95 else if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
98 /* The value is undefined iff its definition statement is empty. */
99 return (gimple_nop_p (SSA_NAME_DEF_STMT (t
))
100 || (possibly_undefined_names
101 && pointer_set_contains (possibly_undefined_names
, t
)));
104 /* Checks if the operand OPND of PHI is defined by
105 another phi with one operand defined by this PHI,
106 but the rest operands are all defined. If yes,
107 returns true to skip this this operand as being
108 redundant. Can be enhanced to be more general. */
111 can_skip_redundant_opnd (tree opnd
, gimple phi
)
117 phi_def
= gimple_phi_result (phi
);
118 op_def
= SSA_NAME_DEF_STMT (opnd
);
119 if (gimple_code (op_def
) != GIMPLE_PHI
)
121 n
= gimple_phi_num_args (op_def
);
122 for (i
= 0; i
< n
; ++i
)
124 tree op
= gimple_phi_arg_def (op_def
, i
);
125 if (TREE_CODE (op
) != SSA_NAME
)
127 if (op
!= phi_def
&& ssa_undefined_value_p (op
))
134 /* Returns a bit mask holding the positions of arguments in PHI
135 that have empty (or possibly empty) definitions. */
138 compute_uninit_opnds_pos (gimple phi
)
141 unsigned uninit_opnds
= 0;
143 n
= gimple_phi_num_args (phi
);
144 /* Bail out for phi with too many args. */
148 for (i
= 0; i
< n
; ++i
)
150 tree op
= gimple_phi_arg_def (phi
, i
);
151 if (TREE_CODE (op
) == SSA_NAME
152 && ssa_undefined_value_p (op
)
153 && !can_skip_redundant_opnd (op
, phi
))
155 /* Ignore SSA_NAMEs on abnormal edges to setjmp
156 or nonlocal goto receiver. */
157 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
159 edge e
= gimple_phi_arg_edge (phi
, i
);
160 if (e
->flags
& EDGE_ABNORMAL
)
162 gimple last
= last_stmt (e
->src
);
163 if (last
&& stmt_can_make_abnormal_goto (last
))
167 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 a
251 dynamic 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
)
265 bool found_cd_chain
= false;
266 size_t cur_chain_len
= 0;
268 if (EDGE_COUNT (bb
->succs
) < 2)
271 /* Could use a set instead. */
272 cur_chain_len
= cur_cd_chain
->length ();
273 if (cur_chain_len
> MAX_CHAIN_LEN
)
276 for (i
= 0; i
< cur_chain_len
; i
++)
278 edge e
= (*cur_cd_chain
)[i
];
279 /* cycle detected. */
284 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
287 int post_dom_check
= 0;
288 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
292 cur_cd_chain
->safe_push (e
);
293 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
297 /* Found a direct control dependence. */
298 if (*num_chains
< MAX_NUM_CHAINS
)
300 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
303 found_cd_chain
= true;
304 /* check path from next edge. */
308 /* Now check if DEP_BB is indirectly control dependent on BB. */
309 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
310 num_chains
, cur_cd_chain
))
312 found_cd_chain
= true;
316 cd_bb
= find_pdom (cd_bb
);
318 if (cd_bb
== EXIT_BLOCK_PTR
|| post_dom_check
> MAX_POSTDOM_CHECK
)
321 cur_cd_chain
->pop ();
322 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
324 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
326 return found_cd_chain
;
329 typedef struct use_pred_info
337 /* Converts the chains of control dependence edges into a set of
338 predicates. A control dependence chain is represented by a vector
339 edges. DEP_CHAINS points to an array of dependence chains.
340 NUM_CHAINS is the size of the chain array. One edge in a dependence
341 chain is mapped to predicate expression represented by use_pred_info_t
342 type. One dependence chain is converted to a composite predicate that
343 is the result of AND operation of use_pred_info_t mapped to each edge.
344 A composite predicate is presented by a vector of use_pred_info_t. On
345 return, *PREDS points to the resulting array of composite predicates.
346 *NUM_PREDS is the number of composite predictes. */
349 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
351 vec
<use_pred_info_t
> **preds
,
354 bool has_valid_pred
= false;
356 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
359 /* Now convert the control dep chain into a set
361 typedef vec
<use_pred_info_t
> vec_use_pred_info_t_heap
;
362 *preds
= XCNEWVEC (vec_use_pred_info_t_heap
, num_chains
);
363 *num_preds
= num_chains
;
365 for (i
= 0; i
< num_chains
; i
++)
367 vec
<edge
> one_cd_chain
= dep_chains
[i
];
369 has_valid_pred
= false;
370 for (j
= 0; j
< one_cd_chain
.length (); j
++)
373 gimple_stmt_iterator gsi
;
374 basic_block guard_bb
;
375 use_pred_info_t one_pred
;
380 gsi
= gsi_last_bb (guard_bb
);
383 has_valid_pred
= false;
386 cond_stmt
= gsi_stmt (gsi
);
387 if (gimple_code (cond_stmt
) == GIMPLE_CALL
388 && EDGE_COUNT (e
->src
->succs
) >= 2)
390 /* Ignore EH edge. Can add assertion
391 on the other edge's flag. */
394 /* Skip if there is essentially one succesor. */
395 if (EDGE_COUNT (e
->src
->succs
) == 2)
401 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
403 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
412 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
414 has_valid_pred
= false;
417 one_pred
= XNEW (struct use_pred_info
);
418 one_pred
->cond
= cond_stmt
;
419 one_pred
->invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
420 (*preds
)[i
].safe_push (one_pred
);
421 has_valid_pred
= true;
427 return has_valid_pred
;
430 /* Computes all control dependence chains for USE_BB. The control
431 dependence chains are then converted to an array of composite
432 predicates pointed to by PREDS. PHI_BB is the basic block of
433 the phi whose result is used in USE_BB. */
436 find_predicates (vec
<use_pred_info_t
> **preds
,
441 size_t num_chains
= 0, i
;
442 vec
<edge
> *dep_chains
= 0;
443 vec
<edge
> cur_chain
= vNULL
;
444 bool has_valid_pred
= false;
445 basic_block cd_root
= 0;
447 typedef vec
<edge
> vec_edge_heap
;
448 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
450 /* First find the closest bb that is control equivalent to PHI_BB
451 that also dominates USE_BB. */
453 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
455 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
456 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
457 cd_root
= ctrl_eq_bb
;
462 compute_control_dep_chain (cd_root
, use_bb
,
463 dep_chains
, &num_chains
,
467 = convert_control_dep_chain_into_preds (dep_chains
,
471 /* Free individual chain */
472 cur_chain
.release ();
473 for (i
= 0; i
< num_chains
; i
++)
474 dep_chains
[i
].release ();
476 return has_valid_pred
;
479 /* Computes the set of incoming edges of PHI that have non empty
480 definitions of a phi chain. The collection will be done
481 recursively on operands that are defined by phis. CD_ROOT
482 is the control dependence root. *EDGES holds the result, and
483 VISITED_PHIS is a pointer set for detecting cycles. */
486 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
488 struct pointer_set_t
*visited_phis
)
494 if (pointer_set_insert (visited_phis
, phi
))
497 n
= gimple_phi_num_args (phi
);
498 for (i
= 0; i
< n
; i
++)
500 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
501 opnd
= gimple_phi_arg_def (phi
, i
);
503 if (TREE_CODE (opnd
) != SSA_NAME
)
505 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
507 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
508 print_gimple_stmt (dump_file
, phi
, 0, 0);
510 edges
->safe_push (opnd_edge
);
514 gimple def
= SSA_NAME_DEF_STMT (opnd
);
516 if (gimple_code (def
) == GIMPLE_PHI
517 && dominated_by_p (CDI_DOMINATORS
,
518 gimple_bb (def
), cd_root
))
519 collect_phi_def_edges (def
, cd_root
, edges
,
521 else if (!ssa_undefined_value_p (opnd
))
523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
525 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
526 print_gimple_stmt (dump_file
, phi
, 0, 0);
528 edges
->safe_push (opnd_edge
);
534 /* For each use edge of PHI, computes all control dependence chains.
535 The control dependence chains are then converted to an array of
536 composite predicates pointed to by PREDS. */
539 find_def_preds (vec
<use_pred_info_t
> **preds
,
540 size_t *num_preds
, gimple phi
)
542 size_t num_chains
= 0, i
, n
;
543 vec
<edge
> *dep_chains
= 0;
544 vec
<edge
> cur_chain
= vNULL
;
545 vec
<edge
> def_edges
= vNULL
;
546 bool has_valid_pred
= false;
547 basic_block phi_bb
, cd_root
= 0;
548 struct pointer_set_t
*visited_phis
;
550 typedef vec
<edge
> vec_edge_heap
;
551 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
553 phi_bb
= gimple_bb (phi
);
554 /* First find the closest dominating bb to be
555 the control dependence root */
556 cd_root
= find_dom (phi_bb
);
560 visited_phis
= pointer_set_create ();
561 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
562 pointer_set_destroy (visited_phis
);
564 n
= def_edges
.length ();
568 for (i
= 0; i
< n
; i
++)
573 opnd_edge
= def_edges
[i
];
574 prev_nc
= num_chains
;
575 compute_control_dep_chain (cd_root
, opnd_edge
->src
,
576 dep_chains
, &num_chains
,
578 /* Free individual chain */
579 cur_chain
.release ();
581 /* Now update the newly added chains with
582 the phi operand edge: */
583 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
585 if (prev_nc
== num_chains
586 && num_chains
< MAX_NUM_CHAINS
)
588 for (j
= prev_nc
; j
< num_chains
; j
++)
590 dep_chains
[j
].safe_push (opnd_edge
);
596 = convert_control_dep_chain_into_preds (dep_chains
,
600 for (i
= 0; i
< num_chains
; i
++)
601 dep_chains
[i
].release ();
603 return has_valid_pred
;
606 /* Dumps the predicates (PREDS) for USESTMT. */
609 dump_predicates (gimple usestmt
, size_t num_preds
,
610 vec
<use_pred_info_t
> *preds
,
614 vec
<use_pred_info_t
> one_pred_chain
;
615 fprintf (dump_file
, msg
);
616 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
617 fprintf (dump_file
, "is guarded by :\n");
618 /* do some dumping here: */
619 for (i
= 0; i
< num_preds
; i
++)
623 one_pred_chain
= preds
[i
];
624 np
= one_pred_chain
.length ();
626 for (j
= 0; j
< np
; j
++)
628 use_pred_info_t one_pred
630 if (one_pred
->invert
)
631 fprintf (dump_file
, " (.NOT.) ");
632 print_gimple_stmt (dump_file
, one_pred
->cond
, 0, 0);
634 fprintf (dump_file
, "(.AND.)\n");
636 if (i
< num_preds
- 1)
637 fprintf (dump_file
, "(.OR.)\n");
641 /* Destroys the predicate set *PREDS. */
644 destroy_predicate_vecs (size_t n
,
645 vec
<use_pred_info_t
> * preds
)
648 for (i
= 0; i
< n
; i
++)
650 for (j
= 0; j
< preds
[i
].length (); j
++)
658 /* Computes the 'normalized' conditional code with operand
659 swapping and condition inversion. */
661 static enum tree_code
662 get_cmp_code (enum tree_code orig_cmp_code
,
663 bool swap_cond
, bool invert
)
665 enum tree_code tc
= orig_cmp_code
;
668 tc
= swap_tree_comparison (orig_cmp_code
);
670 tc
= invert_tree_comparison (tc
, false);
687 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
688 all values in the range satisfies (x CMPC BOUNDARY) == true. */
691 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
693 bool inverted
= false;
697 /* Only handle integer constant here. */
698 if (TREE_CODE (val
) != INTEGER_CST
699 || TREE_CODE (boundary
) != INTEGER_CST
)
702 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
704 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
707 cmpc
= invert_tree_comparison (cmpc
, false);
714 result
= tree_int_cst_equal (val
, boundary
);
715 else if (cmpc
== LT_EXPR
)
716 result
= INT_CST_LT_UNSIGNED (val
, boundary
);
719 gcc_assert (cmpc
== LE_EXPR
);
720 result
= (tree_int_cst_equal (val
, boundary
)
721 || INT_CST_LT_UNSIGNED (val
, boundary
));
727 result
= tree_int_cst_equal (val
, boundary
);
728 else if (cmpc
== LT_EXPR
)
729 result
= INT_CST_LT (val
, boundary
);
732 gcc_assert (cmpc
== LE_EXPR
);
733 result
= (tree_int_cst_equal (val
, boundary
)
734 || INT_CST_LT (val
, boundary
));
744 /* Returns true if PRED is common among all the predicate
745 chains (PREDS) (and therefore can be factored out).
746 NUM_PRED_CHAIN is the size of array PREDS. */
749 find_matching_predicate_in_rest_chains (use_pred_info_t pred
,
750 vec
<use_pred_info_t
> *preds
,
751 size_t num_pred_chains
)
756 if (num_pred_chains
== 1)
759 for (i
= 1; i
< num_pred_chains
; i
++)
762 vec
<use_pred_info_t
> one_chain
= preds
[i
];
763 n
= one_chain
.length ();
764 for (j
= 0; j
< n
; j
++)
766 use_pred_info_t pred2
768 /* can relax the condition comparison to not
769 use address comparison. However, the most common
770 case is that multiple control dependent paths share
771 a common path prefix, so address comparison should
774 if (pred2
->cond
== pred
->cond
775 && pred2
->invert
== pred
->invert
)
787 /* Forward declaration. */
789 is_use_properly_guarded (gimple use_stmt
,
792 unsigned uninit_opnds
,
793 struct pointer_set_t
*visited_phis
);
795 /* Returns true if all uninitialized opnds are pruned. Returns false
796 otherwise. PHI is the phi node with uninitialized operands,
797 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
798 FLAG_DEF is the statement defining the flag guarding the use of the
799 PHI output, BOUNDARY_CST is the const value used in the predicate
800 associated with the flag, CMP_CODE is the comparison code used in
801 the predicate, VISITED_PHIS is the pointer set of phis visited, and
802 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
808 flag_1 = phi <0, 1> // (1)
809 var_1 = phi <undef, some_val>
813 flag_2 = phi <0, flag_1, flag_1> // (2)
814 var_2 = phi <undef, var_1, var_1>
821 Because some flag arg in (1) is not constant, if we do not look into the
822 flag phis recursively, it is conservatively treated as unknown and var_1
823 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
824 a false warning will be emitted. Checking recursively into (1), the compiler can
825 find out that only some_val (which is defined) can flow into (3) which is OK.
830 prune_uninit_phi_opnds_in_unrealizable_paths (
831 gimple phi
, unsigned uninit_opnds
,
832 gimple flag_def
, tree boundary_cst
,
833 enum tree_code cmp_code
,
834 struct pointer_set_t
*visited_phis
,
835 bitmap
*visited_flag_phis
)
839 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
843 if (!MASK_TEST_BIT (uninit_opnds
, i
))
846 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
847 if (!is_gimple_constant (flag_arg
))
849 gimple flag_arg_def
, phi_arg_def
;
851 unsigned uninit_opnds_arg_phi
;
853 if (TREE_CODE (flag_arg
) != SSA_NAME
)
855 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
856 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
859 phi_arg
= gimple_phi_arg_def (phi
, i
);
860 if (TREE_CODE (phi_arg
) != SSA_NAME
)
863 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
864 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
867 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
870 if (!*visited_flag_phis
)
871 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
873 if (bitmap_bit_p (*visited_flag_phis
,
874 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
877 bitmap_set_bit (*visited_flag_phis
,
878 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
880 /* Now recursively prune the uninitialized phi args. */
881 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
882 if (!prune_uninit_phi_opnds_in_unrealizable_paths (
883 phi_arg_def
, uninit_opnds_arg_phi
,
884 flag_arg_def
, boundary_cst
, cmp_code
,
885 visited_phis
, visited_flag_phis
))
888 bitmap_clear_bit (*visited_flag_phis
,
889 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
893 /* Now check if the constant is in the guarded range. */
894 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
899 /* Now that we know that this undefined edge is not
900 pruned. If the operand is defined by another phi,
901 we can further prune the incoming edges of that
902 phi by checking the predicates of this operands. */
904 opnd
= gimple_phi_arg_def (phi
, i
);
905 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
906 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
909 unsigned uninit_opnds2
910 = compute_uninit_opnds_pos (opnd_def
);
911 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
912 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
913 if (!is_use_properly_guarded (phi
,
928 /* A helper function that determines if the predicate set
929 of the use is not overlapping with that of the uninit paths.
930 The most common senario of guarded use is in Example 1:
943 The real world examples are usually more complicated, but similar
944 and usually result from inlining:
946 bool init_func (int * x)
965 Another possible use scenario is in the following trivial example:
977 Predicate analysis needs to compute the composite predicate:
979 1) 'x' use predicate: (n > 0) .AND. (m < 2)
980 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
981 (the predicate chain for phi operand defs can be computed
982 starting from a bb that is control equivalent to the phi's
983 bb and is dominating the operand def.)
985 and check overlapping:
986 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
989 This implementation provides framework that can handle
990 scenarios. (Note that many simple cases are handled properly
991 without the predicate analysis -- this is due to jump threading
992 transformation which eliminates the merge point thus makes
993 path sensitive analysis unnecessary.)
995 NUM_PREDS is the number is the number predicate chains, PREDS is
996 the array of chains, PHI is the phi node whose incoming (undefined)
997 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
998 uninit operand positions. VISITED_PHIS is the pointer set of phi
999 stmts being checked. */
1003 use_pred_not_overlap_with_undef_path_pred (
1005 vec
<use_pred_info_t
> *preds
,
1006 gimple phi
, unsigned uninit_opnds
,
1007 struct pointer_set_t
*visited_phis
)
1010 gimple flag_def
= 0;
1011 tree boundary_cst
= 0;
1012 enum tree_code cmp_code
;
1013 bool swap_cond
= false;
1014 bool invert
= false;
1015 vec
<use_pred_info_t
> the_pred_chain
;
1016 bitmap visited_flag_phis
= NULL
;
1017 bool all_pruned
= false;
1019 gcc_assert (num_preds
> 0);
1020 /* Find within the common prefix of multiple predicate chains
1021 a predicate that is a comparison of a flag variable against
1023 the_pred_chain
= preds
[0];
1024 n
= the_pred_chain
.length ();
1025 for (i
= 0; i
< n
; i
++)
1028 tree cond_lhs
, cond_rhs
, flag
= 0;
1030 use_pred_info_t the_pred
1031 = the_pred_chain
[i
];
1033 cond
= the_pred
->cond
;
1034 invert
= the_pred
->invert
;
1035 cond_lhs
= gimple_cond_lhs (cond
);
1036 cond_rhs
= gimple_cond_rhs (cond
);
1037 cmp_code
= gimple_cond_code (cond
);
1039 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1040 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1042 boundary_cst
= cond_rhs
;
1045 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1046 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1048 boundary_cst
= cond_lhs
;
1056 flag_def
= SSA_NAME_DEF_STMT (flag
);
1061 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1062 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1063 && find_matching_predicate_in_rest_chains (
1064 the_pred
, preds
, num_preds
))
1073 /* Now check all the uninit incoming edge has a constant flag value
1074 that is in conflict with the use guard/predicate. */
1075 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1077 if (cmp_code
== ERROR_MARK
)
1080 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1086 &visited_flag_phis
);
1088 if (visited_flag_phis
)
1089 BITMAP_FREE (visited_flag_phis
);
1094 /* Returns true if TC is AND or OR */
1097 is_and_or_or (enum tree_code tc
, tree typ
)
1099 return (tc
== BIT_IOR_EXPR
1100 || (tc
== BIT_AND_EXPR
1101 && (typ
== 0 || TREE_CODE (typ
) == BOOLEAN_TYPE
)));
1104 typedef struct norm_cond
1107 enum tree_code cond_code
;
1112 /* Normalizes gimple condition COND. The normalization follows
1113 UD chains to form larger condition expression trees. NORM_COND
1114 holds the normalized result. COND_CODE is the logical opcode
1115 (AND or OR) of the normalized tree. */
1118 normalize_cond_1 (gimple cond
,
1119 norm_cond_t norm_cond
,
1120 enum tree_code cond_code
)
1122 enum gimple_code gc
;
1123 enum tree_code cur_cond_code
;
1126 gc
= gimple_code (cond
);
1127 if (gc
!= GIMPLE_ASSIGN
)
1129 norm_cond
->conds
.safe_push (cond
);
1133 cur_cond_code
= gimple_assign_rhs_code (cond
);
1134 rhs1
= gimple_assign_rhs1 (cond
);
1135 rhs2
= gimple_assign_rhs2 (cond
);
1136 if (cur_cond_code
== NE_EXPR
)
1138 if (integer_zerop (rhs2
)
1139 && (TREE_CODE (rhs1
) == SSA_NAME
))
1141 SSA_NAME_DEF_STMT (rhs1
),
1142 norm_cond
, cond_code
);
1143 else if (integer_zerop (rhs1
)
1144 && (TREE_CODE (rhs2
) == SSA_NAME
))
1146 SSA_NAME_DEF_STMT (rhs2
),
1147 norm_cond
, cond_code
);
1149 norm_cond
->conds
.safe_push (cond
);
1154 if (is_and_or_or (cur_cond_code
, TREE_TYPE (rhs1
))
1155 && (cond_code
== cur_cond_code
|| cond_code
== ERROR_MARK
)
1156 && (TREE_CODE (rhs1
) == SSA_NAME
&& TREE_CODE (rhs2
) == SSA_NAME
))
1158 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1
),
1159 norm_cond
, cur_cond_code
);
1160 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2
),
1161 norm_cond
, cur_cond_code
);
1162 norm_cond
->cond_code
= cur_cond_code
;
1165 norm_cond
->conds
.safe_push (cond
);
1168 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1169 if COND needs to be inverted or not. */
1172 normalize_cond (gimple cond
, norm_cond_t norm_cond
, bool invert
)
1174 enum tree_code cond_code
;
1176 norm_cond
->cond_code
= ERROR_MARK
;
1177 norm_cond
->invert
= false;
1178 norm_cond
->conds
.create (0);
1179 gcc_assert (gimple_code (cond
) == GIMPLE_COND
);
1180 cond_code
= gimple_cond_code (cond
);
1182 cond_code
= invert_tree_comparison (cond_code
, false);
1184 if (cond_code
== NE_EXPR
)
1186 if (integer_zerop (gimple_cond_rhs (cond
))
1187 && (TREE_CODE (gimple_cond_lhs (cond
)) == SSA_NAME
))
1189 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
)),
1190 norm_cond
, ERROR_MARK
);
1191 else if (integer_zerop (gimple_cond_lhs (cond
))
1192 && (TREE_CODE (gimple_cond_rhs (cond
)) == SSA_NAME
))
1194 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond
)),
1195 norm_cond
, ERROR_MARK
);
1198 norm_cond
->conds
.safe_push (cond
);
1199 norm_cond
->invert
= invert
;
1204 norm_cond
->conds
.safe_push (cond
);
1205 norm_cond
->invert
= invert
;
1208 gcc_assert (norm_cond
->conds
.length () == 1
1209 || is_and_or_or (norm_cond
->cond_code
, NULL
));
1212 /* Returns true if the domain for condition COND1 is a subset of
1213 COND2. REVERSE is a flag. when it is true the function checks
1214 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1215 to indicate if COND1 and COND2 need to be inverted or not. */
1218 is_gcond_subset_of (gimple cond1
, bool invert1
,
1219 gimple cond2
, bool invert2
,
1222 enum gimple_code gc1
, gc2
;
1223 enum tree_code cond1_code
, cond2_code
;
1225 tree cond1_lhs
, cond1_rhs
, cond2_lhs
, cond2_rhs
;
1227 /* Take the short cut. */
1238 gc1
= gimple_code (cond1
);
1239 gc2
= gimple_code (cond2
);
1241 if ((gc1
!= GIMPLE_ASSIGN
&& gc1
!= GIMPLE_COND
)
1242 || (gc2
!= GIMPLE_ASSIGN
&& gc2
!= GIMPLE_COND
))
1243 return cond1
== cond2
;
1245 cond1_code
= ((gc1
== GIMPLE_ASSIGN
)
1246 ? gimple_assign_rhs_code (cond1
)
1247 : gimple_cond_code (cond1
));
1249 cond2_code
= ((gc2
== GIMPLE_ASSIGN
)
1250 ? gimple_assign_rhs_code (cond2
)
1251 : gimple_cond_code (cond2
));
1253 if (TREE_CODE_CLASS (cond1_code
) != tcc_comparison
1254 || TREE_CODE_CLASS (cond2_code
) != tcc_comparison
)
1258 cond1_code
= invert_tree_comparison (cond1_code
, false);
1260 cond2_code
= invert_tree_comparison (cond2_code
, false);
1262 cond1_lhs
= ((gc1
== GIMPLE_ASSIGN
)
1263 ? gimple_assign_rhs1 (cond1
)
1264 : gimple_cond_lhs (cond1
));
1265 cond1_rhs
= ((gc1
== GIMPLE_ASSIGN
)
1266 ? gimple_assign_rhs2 (cond1
)
1267 : gimple_cond_rhs (cond1
));
1268 cond2_lhs
= ((gc2
== GIMPLE_ASSIGN
)
1269 ? gimple_assign_rhs1 (cond2
)
1270 : gimple_cond_lhs (cond2
));
1271 cond2_rhs
= ((gc2
== GIMPLE_ASSIGN
)
1272 ? gimple_assign_rhs2 (cond2
)
1273 : gimple_cond_rhs (cond2
));
1275 /* Assuming const operands have been swapped to the
1276 rhs at this point of the analysis. */
1278 if (cond1_lhs
!= cond2_lhs
)
1281 if (!is_gimple_constant (cond1_rhs
)
1282 || TREE_CODE (cond1_rhs
) != INTEGER_CST
)
1283 return (cond1_rhs
== cond2_rhs
);
1285 if (!is_gimple_constant (cond2_rhs
)
1286 || TREE_CODE (cond2_rhs
) != INTEGER_CST
)
1287 return (cond1_rhs
== cond2_rhs
);
1289 if (cond1_code
== EQ_EXPR
)
1290 return is_value_included_in (cond1_rhs
,
1291 cond2_rhs
, cond2_code
);
1292 if (cond1_code
== NE_EXPR
|| cond2_code
== EQ_EXPR
)
1293 return ((cond2_code
== cond1_code
)
1294 && tree_int_cst_equal (cond1_rhs
, cond2_rhs
));
1296 if (((cond1_code
== GE_EXPR
|| cond1_code
== GT_EXPR
)
1297 && (cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
))
1298 || ((cond1_code
== LE_EXPR
|| cond1_code
== LT_EXPR
)
1299 && (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
)))
1302 if (cond1_code
!= GE_EXPR
&& cond1_code
!= GT_EXPR
1303 && cond1_code
!= LE_EXPR
&& cond1_code
!= LT_EXPR
)
1306 if (cond1_code
== GT_EXPR
)
1308 cond1_code
= GE_EXPR
;
1309 cond1_rhs
= fold_binary (PLUS_EXPR
, TREE_TYPE (cond1_rhs
),
1311 fold_convert (TREE_TYPE (cond1_rhs
),
1314 else if (cond1_code
== LT_EXPR
)
1316 cond1_code
= LE_EXPR
;
1317 cond1_rhs
= fold_binary (MINUS_EXPR
, TREE_TYPE (cond1_rhs
),
1319 fold_convert (TREE_TYPE (cond1_rhs
),
1326 gcc_assert (cond1_code
== GE_EXPR
|| cond1_code
== LE_EXPR
);
1328 if (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
||
1329 cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
)
1330 return is_value_included_in (cond1_rhs
,
1331 cond2_rhs
, cond2_code
);
1332 else if (cond2_code
== NE_EXPR
)
1334 (is_value_included_in (cond1_rhs
,
1335 cond2_rhs
, cond2_code
)
1336 && !is_value_included_in (cond2_rhs
,
1337 cond1_rhs
, cond1_code
));
1341 /* Returns true if the domain of the condition expression
1342 in COND is a subset of any of the sub-conditions
1343 of the normalized condtion NORM_COND. INVERT is a flag
1344 to indicate of the COND needs to be inverted.
1345 REVERSE is a flag. When it is true, the check is reversed --
1346 it returns true if COND is a superset of any of the subconditions
1350 is_subset_of_any (gimple cond
, bool invert
,
1351 norm_cond_t norm_cond
, bool reverse
)
1354 size_t len
= norm_cond
->conds
.length ();
1356 for (i
= 0; i
< len
; i
++)
1358 if (is_gcond_subset_of (cond
, invert
,
1359 norm_cond
->conds
[i
],
1366 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1367 expressions (formed by following UD chains not control
1368 dependence chains). The function returns true of domain
1369 of and expression NORM_COND1 is a subset of NORM_COND2's.
1370 The implementation is conservative, and it returns false if
1371 it the inclusion relationship may not hold. */
1374 is_or_set_subset_of (norm_cond_t norm_cond1
,
1375 norm_cond_t norm_cond2
)
1378 size_t len
= norm_cond1
->conds
.length ();
1380 for (i
= 0; i
< len
; i
++)
1382 if (!is_subset_of_any (norm_cond1
->conds
[i
],
1383 false, norm_cond2
, false))
1389 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1390 expressions (formed by following UD chains not control
1391 dependence chains). The function returns true of domain
1392 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1395 is_and_set_subset_of (norm_cond_t norm_cond1
,
1396 norm_cond_t norm_cond2
)
1399 size_t len
= norm_cond2
->conds
.length ();
1401 for (i
= 0; i
< len
; i
++)
1403 if (!is_subset_of_any (norm_cond2
->conds
[i
],
1404 false, norm_cond1
, true))
1410 /* Returns true of the domain if NORM_COND1 is a subset
1411 of that of NORM_COND2. Returns false if it can not be
1415 is_norm_cond_subset_of (norm_cond_t norm_cond1
,
1416 norm_cond_t norm_cond2
)
1419 enum tree_code code1
, code2
;
1421 code1
= norm_cond1
->cond_code
;
1422 code2
= norm_cond2
->cond_code
;
1424 if (code1
== BIT_AND_EXPR
)
1426 /* Both conditions are AND expressions. */
1427 if (code2
== BIT_AND_EXPR
)
1428 return is_and_set_subset_of (norm_cond1
, norm_cond2
);
1429 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1430 expression. In this case, returns true if any subexpression
1431 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1432 else if (code2
== BIT_IOR_EXPR
)
1435 len1
= norm_cond1
->conds
.length ();
1436 for (i
= 0; i
< len1
; i
++)
1438 gimple cond1
= norm_cond1
->conds
[i
];
1439 if (is_subset_of_any (cond1
, false, norm_cond2
, false))
1446 gcc_assert (code2
== ERROR_MARK
);
1447 gcc_assert (norm_cond2
->conds
.length () == 1);
1448 return is_subset_of_any (norm_cond2
->conds
[0],
1449 norm_cond2
->invert
, norm_cond1
, true);
1452 /* NORM_COND1 is an OR expression */
1453 else if (code1
== BIT_IOR_EXPR
)
1458 return is_or_set_subset_of (norm_cond1
, norm_cond2
);
1462 gcc_assert (code1
== ERROR_MARK
);
1463 gcc_assert (norm_cond1
->conds
.length () == 1);
1464 /* Conservatively returns false if NORM_COND1 is non-decomposible
1465 and NORM_COND2 is an AND expression. */
1466 if (code2
== BIT_AND_EXPR
)
1469 if (code2
== BIT_IOR_EXPR
)
1470 return is_subset_of_any (norm_cond1
->conds
[0],
1471 norm_cond1
->invert
, norm_cond2
, false);
1473 gcc_assert (code2
== ERROR_MARK
);
1474 gcc_assert (norm_cond2
->conds
.length () == 1);
1475 return is_gcond_subset_of (norm_cond1
->conds
[0],
1477 norm_cond2
->conds
[0],
1478 norm_cond2
->invert
, false);
1482 /* Returns true of the domain of single predicate expression
1483 EXPR1 is a subset of that of EXPR2. Returns false if it
1484 can not be proved. */
1487 is_pred_expr_subset_of (use_pred_info_t expr1
,
1488 use_pred_info_t expr2
)
1490 gimple cond1
, cond2
;
1491 enum tree_code code1
, code2
;
1492 struct norm_cond norm_cond1
, norm_cond2
;
1493 bool is_subset
= false;
1495 cond1
= expr1
->cond
;
1496 cond2
= expr2
->cond
;
1497 code1
= gimple_cond_code (cond1
);
1498 code2
= gimple_cond_code (cond2
);
1501 code1
= invert_tree_comparison (code1
, false);
1503 code2
= invert_tree_comparison (code2
, false);
1505 /* Fast path -- match exactly */
1506 if ((gimple_cond_lhs (cond1
) == gimple_cond_lhs (cond2
))
1507 && (gimple_cond_rhs (cond1
) == gimple_cond_rhs (cond2
))
1508 && (code1
== code2
))
1511 /* Normalize conditions. To keep NE_EXPR, do not invert
1512 with both need inversion. */
1513 normalize_cond (cond1
, &norm_cond1
, (expr1
->invert
));
1514 normalize_cond (cond2
, &norm_cond2
, (expr2
->invert
));
1516 is_subset
= is_norm_cond_subset_of (&norm_cond1
, &norm_cond2
);
1519 norm_cond1
.conds
.release ();
1520 norm_cond2
.conds
.release ();
1524 /* Returns true if the domain of PRED1 is a subset
1525 of that of PRED2. Returns false if it can not be proved so. */
1528 is_pred_chain_subset_of (vec
<use_pred_info_t
> pred1
,
1529 vec
<use_pred_info_t
> pred2
)
1531 size_t np1
, np2
, i1
, i2
;
1533 np1
= pred1
.length ();
1534 np2
= pred2
.length ();
1536 for (i2
= 0; i2
< np2
; i2
++)
1539 use_pred_info_t info2
1541 for (i1
= 0; i1
< np1
; i1
++)
1543 use_pred_info_t info1
1545 if (is_pred_expr_subset_of (info1
, info2
))
1557 /* Returns true if the domain defined by
1558 one pred chain ONE_PRED is a subset of the domain
1559 of *PREDS. It returns false if ONE_PRED's domain is
1560 not a subset of any of the sub-domains of PREDS (
1561 corresponding to each individual chains in it), even
1562 though it may be still be a subset of whole domain
1563 of PREDS which is the union (ORed) of all its subdomains.
1564 In other words, the result is conservative. */
1567 is_included_in (vec
<use_pred_info_t
> one_pred
,
1568 vec
<use_pred_info_t
> *preds
,
1573 for (i
= 0; i
< n
; i
++)
1575 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1582 /* compares two predicate sets PREDS1 and PREDS2 and returns
1583 true if the domain defined by PREDS1 is a superset
1584 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1585 PREDS2 respectively. The implementation chooses not to build
1586 generic trees (and relying on the folding capability of the
1587 compiler), but instead performs brute force comparison of
1588 individual predicate chains (won't be a compile time problem
1589 as the chains are pretty short). When the function returns
1590 false, it does not necessarily mean *PREDS1 is not a superset
1591 of *PREDS2, but mean it may not be so since the analysis can
1592 not prove it. In such cases, false warnings may still be
1596 is_superset_of (vec
<use_pred_info_t
> *preds1
,
1598 vec
<use_pred_info_t
> *preds2
,
1602 vec
<use_pred_info_t
> one_pred_chain
;
1604 for (i
= 0; i
< n2
; i
++)
1606 one_pred_chain
= preds2
[i
];
1607 if (!is_included_in (one_pred_chain
, preds1
, n1
))
1614 /* Comparison function used by qsort. It is used to
1615 sort predicate chains to allow predicate
1619 pred_chain_length_cmp (const void *p1
, const void *p2
)
1621 use_pred_info_t i1
, i2
;
1622 vec
<use_pred_info_t
> const *chain1
1623 = (vec
<use_pred_info_t
> const *)p1
;
1624 vec
<use_pred_info_t
> const *chain2
1625 = (vec
<use_pred_info_t
> const *)p2
;
1627 if (chain1
->length () != chain2
->length ())
1628 return (chain1
->length () - chain2
->length ());
1633 /* Allow predicates with similar prefix come together. */
1634 if (!i1
->invert
&& i2
->invert
)
1636 else if (i1
->invert
&& !i2
->invert
)
1639 return gimple_uid (i1
->cond
) - gimple_uid (i2
->cond
);
1642 /* x OR (!x AND y) is equivalent to x OR y.
1643 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
1644 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
1645 the number of chains. Returns true if normalization happens. */
1648 normalize_preds (vec
<use_pred_info_t
> *preds
, size_t *n
)
1651 vec
<use_pred_info_t
> pred_chain
;
1652 vec
<use_pred_info_t
> x
= vNULL
;
1653 use_pred_info_t xj
= 0, nxj
= 0;
1658 /* First sort the chains in ascending order of lengths. */
1659 qsort (preds
, *n
, sizeof (void *), pred_chain_length_cmp
);
1660 pred_chain
= preds
[0];
1661 ll
= pred_chain
.length ();
1666 use_pred_info_t xx
, yy
, xx2
, nyy
;
1667 vec
<use_pred_info_t
> pred_chain2
= preds
[1];
1668 if (pred_chain2
.length () != 2)
1671 /* See if simplification x AND y OR x AND !y is possible. */
1674 xx2
= pred_chain2
[0];
1675 nyy
= pred_chain2
[1];
1676 if (gimple_cond_lhs (xx
->cond
) != gimple_cond_lhs (xx2
->cond
)
1677 || gimple_cond_rhs (xx
->cond
) != gimple_cond_rhs (xx2
->cond
)
1678 || gimple_cond_code (xx
->cond
) != gimple_cond_code (xx2
->cond
)
1679 || (xx
->invert
!= xx2
->invert
))
1681 if (gimple_cond_lhs (yy
->cond
) != gimple_cond_lhs (nyy
->cond
)
1682 || gimple_cond_rhs (yy
->cond
) != gimple_cond_rhs (nyy
->cond
)
1683 || gimple_cond_code (yy
->cond
) != gimple_cond_code (nyy
->cond
)
1684 || (yy
->invert
== nyy
->invert
))
1687 /* Now merge the first two chains. */
1691 pred_chain
.release ();
1692 pred_chain2
.release ();
1693 pred_chain
.safe_push (xx
);
1694 preds
[0] = pred_chain
;
1695 for (i
= 1; i
< *n
- 1; i
++)
1696 preds
[i
] = preds
[i
+ 1];
1698 preds
[*n
- 1].create (0);
1705 x
.safe_push (pred_chain
[0]);
1707 /* The loop extracts x1, x2, x3, etc from chains
1708 x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3) OR ... */
1709 for (i
= 1; i
< *n
; i
++)
1711 pred_chain
= preds
[i
];
1712 if (pred_chain
.length () != i
+ 1)
1715 for (j
= 0; j
< i
; j
++)
1718 nxj
= pred_chain
[j
];
1720 /* Check if nxj is !xj */
1721 if (gimple_cond_lhs (xj
->cond
) != gimple_cond_lhs (nxj
->cond
)
1722 || gimple_cond_rhs (xj
->cond
) != gimple_cond_rhs (nxj
->cond
)
1723 || gimple_cond_code (xj
->cond
) != gimple_cond_code (nxj
->cond
)
1724 || (xj
->invert
== nxj
->invert
))
1728 x
.safe_push (pred_chain
[i
]);
1731 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
1732 for (j
= 0; j
< *n
; j
++)
1737 t
= XNEW (struct use_pred_info
);
1743 for (i
= 0; i
< *n
; i
++)
1745 pred_chain
= preds
[i
];
1746 for (j
= 0; j
< pred_chain
.length (); j
++)
1747 free (pred_chain
[j
]);
1748 pred_chain
.release ();
1750 pred_chain
.safe_push (x
[i
]);
1751 preds
[i
] = pred_chain
;
1758 /* Computes the predicates that guard the use and checks
1759 if the incoming paths that have empty (or possibly
1760 empty) definition can be pruned/filtered. The function returns
1761 true if it can be determined that the use of PHI's def in
1762 USE_STMT is guarded with a predicate set not overlapping with
1763 predicate sets of all runtime paths that do not have a definition.
1764 Returns false if it is not or it can not be determined. USE_BB is
1765 the bb of the use (for phi operand use, the bb is not the bb of
1766 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1767 is a bit vector. If an operand of PHI is uninitialized, the
1768 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
1769 set of phis being visted. */
1772 is_use_properly_guarded (gimple use_stmt
,
1775 unsigned uninit_opnds
,
1776 struct pointer_set_t
*visited_phis
)
1779 vec
<use_pred_info_t
> *preds
= 0;
1780 vec
<use_pred_info_t
> *def_preds
= 0;
1781 size_t num_preds
= 0, num_def_preds
= 0;
1782 bool has_valid_preds
= false;
1783 bool is_properly_guarded
= false;
1785 if (pointer_set_insert (visited_phis
, phi
))
1788 phi_bb
= gimple_bb (phi
);
1790 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
1793 has_valid_preds
= find_predicates (&preds
, &num_preds
,
1796 if (!has_valid_preds
)
1798 destroy_predicate_vecs (num_preds
, preds
);
1803 dump_predicates (use_stmt
, num_preds
, preds
,
1806 has_valid_preds
= find_def_preds (&def_preds
,
1807 &num_def_preds
, phi
);
1809 if (has_valid_preds
)
1813 dump_predicates (phi
, num_def_preds
, def_preds
,
1814 "Operand defs of phi ");
1816 normed
= normalize_preds (def_preds
, &num_def_preds
);
1817 if (normed
&& dump_file
)
1819 fprintf (dump_file
, "\nNormalized to\n");
1820 dump_predicates (phi
, num_def_preds
, def_preds
,
1821 "Operand defs of phi ");
1823 is_properly_guarded
=
1824 is_superset_of (def_preds
, num_def_preds
,
1828 /* further prune the dead incoming phi edges. */
1829 if (!is_properly_guarded
)
1831 = use_pred_not_overlap_with_undef_path_pred (
1832 num_preds
, preds
, phi
, uninit_opnds
, visited_phis
);
1834 destroy_predicate_vecs (num_preds
, preds
);
1835 destroy_predicate_vecs (num_def_preds
, def_preds
);
1836 return is_properly_guarded
;
1839 /* Searches through all uses of a potentially
1840 uninitialized variable defined by PHI and returns a use
1841 statement if the use is not properly guarded. It returns
1842 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1843 holding the position(s) of uninit PHI operands. WORKLIST
1844 is the vector of candidate phis that may be updated by this
1845 function. ADDED_TO_WORKLIST is the pointer set tracking
1846 if the new phi is already in the worklist. */
1849 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
1850 vec
<gimple
> *worklist
,
1851 struct pointer_set_t
*added_to_worklist
)
1854 use_operand_p use_p
;
1856 imm_use_iterator iter
;
1858 phi_result
= gimple_phi_result (phi
);
1860 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
1862 struct pointer_set_t
*visited_phis
;
1865 use_stmt
= USE_STMT (use_p
);
1866 if (is_gimple_debug (use_stmt
))
1869 visited_phis
= pointer_set_create ();
1871 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1872 use_bb
= gimple_phi_arg_edge (use_stmt
,
1873 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
1875 use_bb
= gimple_bb (use_stmt
);
1877 if (is_use_properly_guarded (use_stmt
,
1883 pointer_set_destroy (visited_phis
);
1886 pointer_set_destroy (visited_phis
);
1888 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1890 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
1891 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1893 /* Found one real use, return. */
1894 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1897 /* Found a phi use that is not guarded,
1898 add the phi to the worklist. */
1899 if (!pointer_set_insert (added_to_worklist
,
1902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1904 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
1905 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1908 worklist
->safe_push (use_stmt
);
1909 pointer_set_insert (possibly_undefined_names
, phi_result
);
1916 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1917 and gives warning if there exists a runtime path from the entry to a
1918 use of the PHI def that does not contain a definition. In other words,
1919 the warning is on the real use. The more dead paths that can be pruned
1920 by the compiler, the fewer false positives the warning is. WORKLIST
1921 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1922 a pointer set tracking if the new phi is added to the worklist or not. */
1925 warn_uninitialized_phi (gimple phi
, vec
<gimple
> *worklist
,
1926 struct pointer_set_t
*added_to_worklist
)
1928 unsigned uninit_opnds
;
1929 gimple uninit_use_stmt
= 0;
1932 /* Don't look at virtual operands. */
1933 if (virtual_operand_p (gimple_phi_result (phi
)))
1936 uninit_opnds
= compute_uninit_opnds_pos (phi
);
1938 if (MASK_EMPTY (uninit_opnds
))
1941 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1943 fprintf (dump_file
, "[CHECK]: examining phi: ");
1944 print_gimple_stmt (dump_file
, phi
, 0, 0);
1947 /* Now check if we have any use of the value without proper guard. */
1948 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
1949 worklist
, added_to_worklist
);
1951 /* All uses are properly guarded. */
1952 if (!uninit_use_stmt
)
1955 uninit_op
= gimple_phi_arg_def (phi
, MASK_FIRST_SET_BIT (uninit_opnds
));
1956 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
1958 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
1959 SSA_NAME_VAR (uninit_op
),
1960 "%qD may be used uninitialized in this function",
1966 /* Entry point to the late uninitialized warning pass. */
1969 execute_late_warn_uninitialized (void)
1972 gimple_stmt_iterator gsi
;
1973 vec
<gimple
> worklist
= vNULL
;
1974 struct pointer_set_t
*added_to_worklist
;
1976 calculate_dominance_info (CDI_DOMINATORS
);
1977 calculate_dominance_info (CDI_POST_DOMINATORS
);
1978 /* Re-do the plain uninitialized variable check, as optimization may have
1979 straightened control flow. Do this first so that we don't accidentally
1980 get a "may be" warning when we'd have seen an "is" warning later. */
1981 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1983 timevar_push (TV_TREE_UNINIT
);
1985 possibly_undefined_names
= pointer_set_create ();
1986 added_to_worklist
= pointer_set_create ();
1988 /* Initialize worklist */
1990 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1992 gimple phi
= gsi_stmt (gsi
);
1995 n
= gimple_phi_num_args (phi
);
1997 /* Don't look at virtual operands. */
1998 if (virtual_operand_p (gimple_phi_result (phi
)))
2001 for (i
= 0; i
< n
; ++i
)
2003 tree op
= gimple_phi_arg_def (phi
, i
);
2004 if (TREE_CODE (op
) == SSA_NAME
2005 && ssa_undefined_value_p (op
))
2007 worklist
.safe_push (phi
);
2008 pointer_set_insert (added_to_worklist
, phi
);
2009 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2011 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2012 print_gimple_stmt (dump_file
, phi
, 0, 0);
2019 while (worklist
.length () != 0)
2022 cur_phi
= worklist
.pop ();
2023 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2026 worklist
.release ();
2027 pointer_set_destroy (added_to_worklist
);
2028 pointer_set_destroy (possibly_undefined_names
);
2029 possibly_undefined_names
= NULL
;
2030 free_dominance_info (CDI_POST_DOMINATORS
);
2031 timevar_pop (TV_TREE_UNINIT
);
2036 gate_warn_uninitialized (void)
2038 return warn_uninitialized
!= 0;
2041 struct gimple_opt_pass pass_late_warn_uninitialized
=
2045 "uninit", /* name */
2046 OPTGROUP_NONE
, /* optinfo_flags */
2047 gate_warn_uninitialized
, /* gate */
2048 execute_late_warn_uninitialized
, /* execute */
2051 0, /* static_pass_number */
2052 TV_NONE
, /* tv_id */
2053 PROP_ssa
, /* properties_required */
2054 0, /* properties_provided */
2055 0, /* properties_destroyed */
2056 0, /* todo_flags_start */
2057 0 /* todo_flags_finish */