1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2010 Free Software
4 Contributed by Xinliang David Li <davidxl@google.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "basic-block.h"
31 #include "gimple-pretty-print.h"
33 #include "pointer-set.h"
34 #include "tree-flow.h"
36 #include "tree-inline.h"
38 #include "tree-pass.h"
39 #include "diagnostic-core.h"
41 /* This implements the pass that does predicate aware warning on uses of
42 possibly uninitialized variables. The pass first collects the set of
43 possibly uninitialized SSA names. For each such name, it walks through
44 all its immediate uses. For each immediate use, it rebuilds the condition
45 expression (the predicate) that guards the use. The predicate is then
46 examined to see if the variable is always defined under that same condition.
47 This is done either by pruning the unrealizable paths that lead to the
48 default definitions or by checking if the predicate set that guards the
49 defining paths is a superset of the use predicate. */
52 /* Pointer set of potentially undefined ssa names, i.e.,
53 ssa names that are defined by phi with operands that
54 are not defined or potentially undefined. */
55 static struct pointer_set_t
*possibly_undefined_names
= 0;
57 /* Bit mask handling macros. */
58 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
59 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
60 #define MASK_EMPTY(mask) (mask == 0)
62 /* Returns the first bit position (starting from LSB)
63 in mask that is non zero. Returns -1 if the mask is empty. */
65 get_mask_first_set_bit (unsigned mask
)
71 while ((mask
& (1 << pos
)) == 0)
76 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
79 /* Return true if T, an SSA_NAME, has an undefined value. */
82 ssa_undefined_value_p (tree t
)
84 tree var
= SSA_NAME_VAR (t
);
86 /* Parameters get their initial value from the function entry. */
87 if (TREE_CODE (var
) == PARM_DECL
)
90 /* When returning by reference the return address is actually a hidden
92 if (TREE_CODE (SSA_NAME_VAR (t
)) == RESULT_DECL
93 && DECL_BY_REFERENCE (SSA_NAME_VAR (t
)))
96 /* Hard register variables get their initial value from the ether. */
97 if (TREE_CODE (var
) == VAR_DECL
&& DECL_HARD_REGISTER (var
))
100 /* The value is undefined iff its definition statement is empty. */
101 return (gimple_nop_p (SSA_NAME_DEF_STMT (t
))
102 || (possibly_undefined_names
103 && pointer_set_contains (possibly_undefined_names
, t
)));
106 /* Checks if the operand OPND of PHI is defined by
107 another phi with one operand defined by this PHI,
108 but the rest operands are all defined. If yes,
109 returns true to skip this this operand as being
110 redundant. Can be enhanced to be more general. */
113 can_skip_redundant_opnd (tree opnd
, gimple phi
)
119 phi_def
= gimple_phi_result (phi
);
120 op_def
= SSA_NAME_DEF_STMT (opnd
);
121 if (gimple_code (op_def
) != GIMPLE_PHI
)
123 n
= gimple_phi_num_args (op_def
);
124 for (i
= 0; i
< n
; ++i
)
126 tree op
= gimple_phi_arg_def (op_def
, i
);
127 if (TREE_CODE (op
) != SSA_NAME
)
129 if (op
!= phi_def
&& ssa_undefined_value_p (op
))
136 /* Returns a bit mask holding the positions of arguments in PHI
137 that have empty (or possibly empty) definitions. */
140 compute_uninit_opnds_pos (gimple phi
)
143 unsigned uninit_opnds
= 0;
145 n
= gimple_phi_num_args (phi
);
146 /* Bail out for phi with too many args. */
150 for (i
= 0; i
< n
; ++i
)
152 tree op
= gimple_phi_arg_def (phi
, i
);
153 if (TREE_CODE (op
) == SSA_NAME
154 && ssa_undefined_value_p (op
)
155 && !can_skip_redundant_opnd (op
, phi
))
156 MASK_SET_BIT (uninit_opnds
, i
);
161 /* Find the immediate postdominator PDOM of the specified
162 basic block BLOCK. */
164 static inline basic_block
165 find_pdom (basic_block block
)
167 if (block
== EXIT_BLOCK_PTR
)
168 return EXIT_BLOCK_PTR
;
172 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
174 return EXIT_BLOCK_PTR
;
179 /* Find the immediate DOM of the specified
180 basic block BLOCK. */
182 static inline basic_block
183 find_dom (basic_block block
)
185 if (block
== ENTRY_BLOCK_PTR
)
186 return ENTRY_BLOCK_PTR
;
189 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
191 return ENTRY_BLOCK_PTR
;
196 /* Returns true if BB1 is postdominating BB2 and BB1 is
197 not a loop exit bb. The loop exit bb check is simple and does
198 not cover all cases. */
201 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
203 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
206 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
212 /* Find the closest postdominator of a specified BB, which is control
215 static inline basic_block
216 find_control_equiv_block (basic_block bb
)
220 pdom
= find_pdom (bb
);
222 /* Skip the postdominating bb that is also loop exit. */
223 if (!is_non_loop_exit_postdominating (pdom
, bb
))
226 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
232 #define MAX_NUM_CHAINS 8
233 #define MAX_CHAIN_LEN 5
235 /* Computes the control dependence chains (paths of edges)
236 for DEP_BB up to the dominating basic block BB (the head node of a
237 chain should be dominated by it). CD_CHAINS is pointer to a
238 dynamic array holding the result chains. CUR_CD_CHAIN is the current
239 chain being computed. *NUM_CHAINS is total number of chains. The
240 function returns true if the information is successfully computed,
241 return false if there is no control dependence or not computed. */
244 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
245 VEC(edge
, heap
) **cd_chains
,
247 VEC(edge
, heap
) **cur_cd_chain
)
252 bool found_cd_chain
= false;
253 size_t cur_chain_len
= 0;
255 if (EDGE_COUNT (bb
->succs
) < 2)
258 /* Could use a set instead. */
259 cur_chain_len
= VEC_length (edge
, *cur_cd_chain
);
260 if (cur_chain_len
> MAX_CHAIN_LEN
)
263 for (i
= 0; i
< cur_chain_len
; i
++)
265 edge e
= VEC_index (edge
, *cur_cd_chain
, i
);
266 /* cycle detected. */
271 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
274 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
278 VEC_safe_push (edge
, heap
, *cur_cd_chain
, e
);
279 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
283 /* Found a direct control dependence. */
284 if (*num_chains
< MAX_NUM_CHAINS
)
286 cd_chains
[*num_chains
]
287 = VEC_copy (edge
, heap
, *cur_cd_chain
);
290 found_cd_chain
= true;
291 /* check path from next edge. */
295 /* Now check if DEP_BB is indirectly control dependent on BB. */
296 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
297 num_chains
, cur_cd_chain
))
299 found_cd_chain
= true;
303 cd_bb
= find_pdom (cd_bb
);
304 if (cd_bb
== EXIT_BLOCK_PTR
)
307 VEC_pop (edge
, *cur_cd_chain
);
308 gcc_assert (VEC_length (edge
, *cur_cd_chain
) == cur_chain_len
);
310 gcc_assert (VEC_length (edge
, *cur_cd_chain
) == cur_chain_len
);
312 return found_cd_chain
;
315 typedef struct use_pred_info
321 DEF_VEC_P(use_pred_info_t
);
322 DEF_VEC_ALLOC_P(use_pred_info_t
, heap
);
325 /* Converts the chains of control dependence edges into a set of
326 predicates. A control dependence chain is represented by a vector
327 edges. DEP_CHAINS points to an array of dependence chains.
328 NUM_CHAINS is the size of the chain array. One edge in a dependence
329 chain is mapped to predicate expression represented by use_pred_info_t
330 type. One dependence chain is converted to a composite predicate that
331 is the result of AND operation of use_pred_info_t mapped to each edge.
332 A composite predicate is presented by a vector of use_pred_info_t. On
333 return, *PREDS points to the resulting array of composite predicates.
334 *NUM_PREDS is the number of composite predictes. */
337 convert_control_dep_chain_into_preds (VEC(edge
, heap
) **dep_chains
,
339 VEC(use_pred_info_t
, heap
) ***preds
,
342 bool has_valid_pred
= false;
344 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
347 /* Now convert the control dep chain into a set
349 *preds
= XCNEWVEC (VEC(use_pred_info_t
, heap
) *,
351 *num_preds
= num_chains
;
353 for (i
= 0; i
< num_chains
; i
++)
355 VEC(edge
, heap
) *one_cd_chain
= dep_chains
[i
];
357 has_valid_pred
= false;
358 for (j
= 0; j
< VEC_length (edge
, one_cd_chain
); j
++)
361 gimple_stmt_iterator gsi
;
362 basic_block guard_bb
;
363 use_pred_info_t one_pred
;
366 e
= VEC_index (edge
, one_cd_chain
, j
);
368 gsi
= gsi_last_bb (guard_bb
);
371 has_valid_pred
= false;
374 cond_stmt
= gsi_stmt (gsi
);
375 if (gimple_code (cond_stmt
) == GIMPLE_CALL
376 && EDGE_COUNT (e
->src
->succs
) >= 2)
378 /* Ignore EH edge. Can add assertion
379 on the other edge's flag. */
382 /* Skip if there is essentially one succesor. */
383 if (EDGE_COUNT (e
->src
->succs
) == 2)
389 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
391 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
400 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
402 has_valid_pred
= false;
405 one_pred
= XNEW (struct use_pred_info
);
406 one_pred
->cond
= cond_stmt
;
407 one_pred
->invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
408 VEC_safe_push (use_pred_info_t
, heap
, (*preds
)[i
], one_pred
);
409 has_valid_pred
= true;
415 return has_valid_pred
;
418 /* Computes all control dependence chains for USE_BB. The control
419 dependence chains are then converted to an array of composite
420 predicates pointed to by PREDS. PHI_BB is the basic block of
421 the phi whose result is used in USE_BB. */
424 find_predicates (VEC(use_pred_info_t
, heap
) ***preds
,
429 size_t num_chains
= 0, i
;
430 VEC(edge
, heap
) **dep_chains
= 0;
431 VEC(edge
, heap
) *cur_chain
= 0;
432 bool has_valid_pred
= false;
433 basic_block cd_root
= 0;
435 dep_chains
= XCNEWVEC (VEC(edge
, heap
) *, MAX_NUM_CHAINS
);
437 /* First find the closest bb that is control equivalent to PHI_BB
438 that also dominates USE_BB. */
440 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
442 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
443 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
444 cd_root
= ctrl_eq_bb
;
449 compute_control_dep_chain (cd_root
, use_bb
,
450 dep_chains
, &num_chains
,
454 = convert_control_dep_chain_into_preds (dep_chains
,
458 /* Free individual chain */
459 VEC_free (edge
, heap
, cur_chain
);
460 for (i
= 0; i
< num_chains
; i
++)
461 VEC_free (edge
, heap
, dep_chains
[i
]);
463 return has_valid_pred
;
466 /* Computes the set of incoming edges of PHI that have non empty
467 definitions of a phi chain. The collection will be done
468 recursively on operands that are defined by phis. CD_ROOT
469 is the control dependence root. *EDGES holds the result, and
470 VISITED_PHIS is a pointer set for detecting cycles. */
473 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
474 VEC(edge
, heap
) **edges
,
475 struct pointer_set_t
*visited_phis
)
481 if (pointer_set_insert (visited_phis
, phi
))
484 n
= gimple_phi_num_args (phi
);
485 for (i
= 0; i
< n
; i
++)
487 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
488 opnd
= gimple_phi_arg_def (phi
, i
);
490 if (TREE_CODE (opnd
) != SSA_NAME
)
492 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
494 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
495 print_gimple_stmt (dump_file
, phi
, 0, 0);
497 VEC_safe_push (edge
, heap
, *edges
, opnd_edge
);
501 gimple def
= SSA_NAME_DEF_STMT (opnd
);
503 if (gimple_code (def
) == GIMPLE_PHI
504 && dominated_by_p (CDI_DOMINATORS
,
505 gimple_bb (def
), cd_root
))
506 collect_phi_def_edges (def
, cd_root
, edges
,
508 else if (!ssa_undefined_value_p (opnd
))
510 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
513 print_gimple_stmt (dump_file
, phi
, 0, 0);
515 VEC_safe_push (edge
, heap
, *edges
, opnd_edge
);
521 /* For each use edge of PHI, computes all control dependence chains.
522 The control dependence chains are then converted to an array of
523 composite predicates pointed to by PREDS. */
526 find_def_preds (VEC(use_pred_info_t
, heap
) ***preds
,
527 size_t *num_preds
, gimple phi
)
529 size_t num_chains
= 0, i
, n
;
530 VEC(edge
, heap
) **dep_chains
= 0;
531 VEC(edge
, heap
) *cur_chain
= 0;
532 VEC(edge
, heap
) *def_edges
= 0;
533 bool has_valid_pred
= false;
534 basic_block phi_bb
, cd_root
= 0;
535 struct pointer_set_t
*visited_phis
;
537 dep_chains
= XCNEWVEC (VEC(edge
, heap
) *, MAX_NUM_CHAINS
);
539 phi_bb
= gimple_bb (phi
);
540 /* First find the closest dominating bb to be
541 the control dependence root */
542 cd_root
= find_dom (phi_bb
);
546 visited_phis
= pointer_set_create ();
547 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
548 pointer_set_destroy (visited_phis
);
550 n
= VEC_length (edge
, def_edges
);
554 for (i
= 0; i
< n
; i
++)
559 opnd_edge
= VEC_index (edge
, def_edges
, i
);
560 prev_nc
= num_chains
;
561 compute_control_dep_chain (cd_root
, opnd_edge
->src
,
562 dep_chains
, &num_chains
,
564 /* Free individual chain */
565 VEC_free (edge
, heap
, cur_chain
);
568 /* Now update the newly added chains with
569 the phi operand edge: */
570 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
572 if (prev_nc
== num_chains
573 && num_chains
< MAX_NUM_CHAINS
)
575 for (j
= prev_nc
; j
< num_chains
; j
++)
577 VEC_safe_push (edge
, heap
, dep_chains
[j
], opnd_edge
);
583 = convert_control_dep_chain_into_preds (dep_chains
,
587 for (i
= 0; i
< num_chains
; i
++)
588 VEC_free (edge
, heap
, dep_chains
[i
]);
590 return has_valid_pred
;
593 /* Dumps the predicates (PREDS) for USESTMT. */
596 dump_predicates (gimple usestmt
, size_t num_preds
,
597 VEC(use_pred_info_t
, heap
) **preds
,
601 VEC(use_pred_info_t
, heap
) *one_pred_chain
;
602 fprintf (dump_file
, msg
);
603 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
604 fprintf (dump_file
, "is guarded by :\n");
605 /* do some dumping here: */
606 for (i
= 0; i
< num_preds
; i
++)
610 one_pred_chain
= preds
[i
];
611 np
= VEC_length (use_pred_info_t
, one_pred_chain
);
613 for (j
= 0; j
< np
; j
++)
615 use_pred_info_t one_pred
616 = VEC_index (use_pred_info_t
, one_pred_chain
, j
);
617 if (one_pred
->invert
)
618 fprintf (dump_file
, " (.NOT.) ");
619 print_gimple_stmt (dump_file
, one_pred
->cond
, 0, 0);
621 fprintf (dump_file
, "(.AND.)\n");
623 if (i
< num_preds
- 1)
624 fprintf (dump_file
, "(.OR.)\n");
628 /* Destroys the predicate set *PREDS. */
631 destroy_predicate_vecs (size_t n
,
632 VEC(use_pred_info_t
, heap
) ** preds
)
635 for (i
= 0; i
< n
; i
++)
637 for (j
= 0; j
< VEC_length (use_pred_info_t
, preds
[i
]); j
++)
638 free (VEC_index (use_pred_info_t
, preds
[i
], j
));
639 VEC_free (use_pred_info_t
, heap
, preds
[i
]);
645 /* Computes the 'normalized' conditional code with operand
646 swapping and condition inversion. */
648 static enum tree_code
649 get_cmp_code (enum tree_code orig_cmp_code
,
650 bool swap_cond
, bool invert
)
652 enum tree_code tc
= orig_cmp_code
;
655 tc
= swap_tree_comparison (orig_cmp_code
);
657 tc
= invert_tree_comparison (tc
, false);
674 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
675 all values in the range satisfies (x CMPC BOUNDARY) == true. */
678 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
680 bool inverted
= false;
684 /* Only handle integer constant here. */
685 if (TREE_CODE (val
) != INTEGER_CST
686 || TREE_CODE (boundary
) != INTEGER_CST
)
689 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
691 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
694 cmpc
= invert_tree_comparison (cmpc
, false);
701 result
= tree_int_cst_equal (val
, boundary
);
702 else if (cmpc
== LT_EXPR
)
703 result
= INT_CST_LT_UNSIGNED (val
, boundary
);
706 gcc_assert (cmpc
== LE_EXPR
);
707 result
= (tree_int_cst_equal (val
, boundary
)
708 || INT_CST_LT_UNSIGNED (val
, boundary
));
714 result
= tree_int_cst_equal (val
, boundary
);
715 else if (cmpc
== LT_EXPR
)
716 result
= INT_CST_LT (val
, boundary
);
719 gcc_assert (cmpc
== LE_EXPR
);
720 result
= (tree_int_cst_equal (val
, boundary
)
721 || INT_CST_LT (val
, boundary
));
731 /* Returns true if PRED is common among all the predicate
732 chains (PREDS) (and therefore can be factored out).
733 NUM_PRED_CHAIN is the size of array PREDS. */
736 find_matching_predicate_in_rest_chains (use_pred_info_t pred
,
737 VEC(use_pred_info_t
, heap
) **preds
,
738 size_t num_pred_chains
)
743 if (num_pred_chains
== 1)
746 for (i
= 1; i
< num_pred_chains
; i
++)
749 VEC(use_pred_info_t
, heap
) *one_chain
= preds
[i
];
750 n
= VEC_length (use_pred_info_t
, one_chain
);
751 for (j
= 0; j
< n
; j
++)
753 use_pred_info_t pred2
754 = VEC_index (use_pred_info_t
, one_chain
, j
);
755 /* can relax the condition comparison to not
756 use address comparison. However, the most common
757 case is that multiple control dependent paths share
758 a common path prefix, so address comparison should
761 if (pred2
->cond
== pred
->cond
762 && pred2
->invert
== pred
->invert
)
774 /* Forward declaration. */
776 is_use_properly_guarded (gimple use_stmt
,
779 unsigned uninit_opnds
,
780 struct pointer_set_t
*visited_phis
);
782 /* Returns true if all uninitialized opnds are pruned. Returns false
783 otherwise. PHI is the phi node with uninitialized operands,
784 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
785 FLAG_DEF is the statement defining the flag guarding the use of the
786 PHI output, BOUNDARY_CST is the const value used in the predicate
787 associated with the flag, CMP_CODE is the comparison code used in
788 the predicate, VISITED_PHIS is the pointer set of phis visited, and
789 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
795 flag_1 = phi <0, 1> // (1)
796 var_1 = phi <undef, some_val>
800 flag_2 = phi <0, flag_1, flag_1> // (2)
801 var_2 = phi <undef, var_1, var_1>
808 Because some flag arg in (1) is not constant, if we do not look into the
809 flag phis recursively, it is conservatively treated as unknown and var_1
810 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
811 a false warning will be emitted. Checking recursively into (1), the compiler can
812 find out that only some_val (which is defined) can flow into (3) which is OK.
817 prune_uninit_phi_opnds_in_unrealizable_paths (
818 gimple phi
, unsigned uninit_opnds
,
819 gimple flag_def
, tree boundary_cst
,
820 enum tree_code cmp_code
,
821 struct pointer_set_t
*visited_phis
,
822 bitmap
*visited_flag_phis
)
826 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
830 if (!MASK_TEST_BIT (uninit_opnds
, i
))
833 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
834 if (!is_gimple_constant (flag_arg
))
836 gimple flag_arg_def
, phi_arg_def
;
838 unsigned uninit_opnds_arg_phi
;
840 if (TREE_CODE (flag_arg
) != SSA_NAME
)
842 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
843 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
846 phi_arg
= gimple_phi_arg_def (phi
, i
);
847 if (TREE_CODE (phi_arg
) != SSA_NAME
)
850 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
851 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
854 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
857 if (!*visited_flag_phis
)
858 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
860 if (bitmap_bit_p (*visited_flag_phis
,
861 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
864 bitmap_set_bit (*visited_flag_phis
,
865 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
867 /* Now recursively prune the uninitialized phi args. */
868 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
869 if (!prune_uninit_phi_opnds_in_unrealizable_paths (
870 phi_arg_def
, uninit_opnds_arg_phi
,
871 flag_arg_def
, boundary_cst
, cmp_code
,
872 visited_phis
, visited_flag_phis
))
875 bitmap_clear_bit (*visited_flag_phis
,
876 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
880 /* Now check if the constant is in the guarded range. */
881 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
886 /* Now that we know that this undefined edge is not
887 pruned. If the operand is defined by another phi,
888 we can further prune the incoming edges of that
889 phi by checking the predicates of this operands. */
891 opnd
= gimple_phi_arg_def (phi
, i
);
892 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
893 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
896 unsigned uninit_opnds2
897 = compute_uninit_opnds_pos (opnd_def
);
898 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
899 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
900 if (!is_use_properly_guarded (phi
,
915 /* A helper function that determines if the predicate set
916 of the use is not overlapping with that of the uninit paths.
917 The most common senario of guarded use is in Example 1:
930 The real world examples are usually more complicated, but similar
931 and usually result from inlining:
933 bool init_func (int * x)
952 Another possible use scenario is in the following trivial example:
964 Predicate analysis needs to compute the composite predicate:
966 1) 'x' use predicate: (n > 0) .AND. (m < 2)
967 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
968 (the predicate chain for phi operand defs can be computed
969 starting from a bb that is control equivalent to the phi's
970 bb and is dominating the operand def.)
972 and check overlapping:
973 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
976 This implementation provides framework that can handle
977 scenarios. (Note that many simple cases are handled properly
978 without the predicate analysis -- this is due to jump threading
979 transformation which eliminates the merge point thus makes
980 path sensitive analysis unnecessary.)
982 NUM_PREDS is the number is the number predicate chains, PREDS is
983 the array of chains, PHI is the phi node whose incoming (undefined)
984 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
985 uninit operand positions. VISITED_PHIS is the pointer set of phi
986 stmts being checked. */
990 use_pred_not_overlap_with_undef_path_pred (
992 VEC(use_pred_info_t
, heap
) **preds
,
993 gimple phi
, unsigned uninit_opnds
,
994 struct pointer_set_t
*visited_phis
)
998 tree boundary_cst
= 0;
999 enum tree_code cmp_code
;
1000 bool swap_cond
= false;
1001 bool invert
= false;
1002 VEC(use_pred_info_t
, heap
) *the_pred_chain
;
1003 bitmap visited_flag_phis
= NULL
;
1004 bool all_pruned
= false;
1006 gcc_assert (num_preds
> 0);
1007 /* Find within the common prefix of multiple predicate chains
1008 a predicate that is a comparison of a flag variable against
1010 the_pred_chain
= preds
[0];
1011 n
= VEC_length (use_pred_info_t
, the_pred_chain
);
1012 for (i
= 0; i
< n
; i
++)
1015 tree cond_lhs
, cond_rhs
, flag
= 0;
1017 use_pred_info_t the_pred
1018 = VEC_index (use_pred_info_t
, the_pred_chain
, i
);
1020 cond
= the_pred
->cond
;
1021 invert
= the_pred
->invert
;
1022 cond_lhs
= gimple_cond_lhs (cond
);
1023 cond_rhs
= gimple_cond_rhs (cond
);
1024 cmp_code
= gimple_cond_code (cond
);
1026 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1027 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1029 boundary_cst
= cond_rhs
;
1032 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1033 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1035 boundary_cst
= cond_lhs
;
1043 flag_def
= SSA_NAME_DEF_STMT (flag
);
1048 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1049 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1050 && find_matching_predicate_in_rest_chains (
1051 the_pred
, preds
, num_preds
))
1060 /* Now check all the uninit incoming edge has a constant flag value
1061 that is in conflict with the use guard/predicate. */
1062 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1064 if (cmp_code
== ERROR_MARK
)
1067 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1073 &visited_flag_phis
);
1075 if (visited_flag_phis
)
1076 BITMAP_FREE (visited_flag_phis
);
1081 /* Returns true if TC is AND or OR */
1084 is_and_or_or (enum tree_code tc
, tree typ
)
1086 return (tc
== BIT_IOR_EXPR
1087 || (tc
== BIT_AND_EXPR
1088 && (typ
== 0 || TREE_CODE (typ
) == BOOLEAN_TYPE
)));
1091 typedef struct norm_cond
1093 VEC(gimple
, heap
) *conds
;
1094 enum tree_code cond_code
;
1099 /* Normalizes gimple condition COND. The normalization follows
1100 UD chains to form larger condition expression trees. NORM_COND
1101 holds the normalized result. COND_CODE is the logical opcode
1102 (AND or OR) of the normalized tree. */
1105 normalize_cond_1 (gimple cond
,
1106 norm_cond_t norm_cond
,
1107 enum tree_code cond_code
)
1109 enum gimple_code gc
;
1110 enum tree_code cur_cond_code
;
1113 gc
= gimple_code (cond
);
1114 if (gc
!= GIMPLE_ASSIGN
)
1116 VEC_safe_push (gimple
, heap
, norm_cond
->conds
, cond
);
1120 cur_cond_code
= gimple_assign_rhs_code (cond
);
1121 rhs1
= gimple_assign_rhs1 (cond
);
1122 rhs2
= gimple_assign_rhs2 (cond
);
1123 if (cur_cond_code
== NE_EXPR
)
1125 if (integer_zerop (rhs2
)
1126 && (TREE_CODE (rhs1
) == SSA_NAME
))
1128 SSA_NAME_DEF_STMT (rhs1
),
1129 norm_cond
, cond_code
);
1130 else if (integer_zerop (rhs1
)
1131 && (TREE_CODE (rhs2
) == SSA_NAME
))
1133 SSA_NAME_DEF_STMT (rhs2
),
1134 norm_cond
, cond_code
);
1136 VEC_safe_push (gimple
, heap
, norm_cond
->conds
, cond
);
1141 if (is_and_or_or (cur_cond_code
, TREE_TYPE (rhs1
))
1142 && (cond_code
== cur_cond_code
|| cond_code
== ERROR_MARK
)
1143 && (TREE_CODE (rhs1
) == SSA_NAME
&& TREE_CODE (rhs2
) == SSA_NAME
))
1145 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs1
),
1146 norm_cond
, cur_cond_code
);
1147 normalize_cond_1 (SSA_NAME_DEF_STMT (rhs2
),
1148 norm_cond
, cur_cond_code
);
1149 norm_cond
->cond_code
= cur_cond_code
;
1152 VEC_safe_push (gimple
, heap
, norm_cond
->conds
, cond
);
1155 /* See normalize_cond_1 for details. INVERT is a flag to indicate
1156 if COND needs to be inverted or not. */
1159 normalize_cond (gimple cond
, norm_cond_t norm_cond
, bool invert
)
1161 enum tree_code cond_code
;
1163 norm_cond
->cond_code
= ERROR_MARK
;
1164 norm_cond
->invert
= false;
1165 norm_cond
->conds
= NULL
;
1166 gcc_assert (gimple_code (cond
) == GIMPLE_COND
);
1167 cond_code
= gimple_cond_code (cond
);
1169 cond_code
= invert_tree_comparison (cond_code
, false);
1171 if (cond_code
== NE_EXPR
)
1173 if (integer_zerop (gimple_cond_rhs (cond
))
1174 && (TREE_CODE (gimple_cond_lhs (cond
)) == SSA_NAME
))
1176 SSA_NAME_DEF_STMT (gimple_cond_lhs (cond
)),
1177 norm_cond
, ERROR_MARK
);
1178 else if (integer_zerop (gimple_cond_lhs (cond
))
1179 && (TREE_CODE (gimple_cond_rhs (cond
)) == SSA_NAME
))
1181 SSA_NAME_DEF_STMT (gimple_cond_rhs (cond
)),
1182 norm_cond
, ERROR_MARK
);
1185 VEC_safe_push (gimple
, heap
, norm_cond
->conds
, cond
);
1186 norm_cond
->invert
= invert
;
1191 VEC_safe_push (gimple
, heap
, norm_cond
->conds
, cond
);
1192 norm_cond
->invert
= invert
;
1195 gcc_assert (VEC_length (gimple
, norm_cond
->conds
) == 1
1196 || is_and_or_or (norm_cond
->cond_code
, NULL
));
1199 /* Returns true if the domain for condition COND1 is a subset of
1200 COND2. REVERSE is a flag. when it is true the function checks
1201 if COND1 is a superset of COND2. INVERT1 and INVERT2 are flags
1202 to indicate if COND1 and COND2 need to be inverted or not. */
1205 is_gcond_subset_of (gimple cond1
, bool invert1
,
1206 gimple cond2
, bool invert2
,
1209 enum gimple_code gc1
, gc2
;
1210 enum tree_code cond1_code
, cond2_code
;
1212 tree cond1_lhs
, cond1_rhs
, cond2_lhs
, cond2_rhs
;
1214 /* Take the short cut. */
1225 gc1
= gimple_code (cond1
);
1226 gc2
= gimple_code (cond2
);
1228 if ((gc1
!= GIMPLE_ASSIGN
&& gc1
!= GIMPLE_COND
)
1229 || (gc2
!= GIMPLE_ASSIGN
&& gc2
!= GIMPLE_COND
))
1230 return cond1
== cond2
;
1232 cond1_code
= ((gc1
== GIMPLE_ASSIGN
)
1233 ? gimple_assign_rhs_code (cond1
)
1234 : gimple_cond_code (cond1
));
1236 cond2_code
= ((gc2
== GIMPLE_ASSIGN
)
1237 ? gimple_assign_rhs_code (cond2
)
1238 : gimple_cond_code (cond2
));
1240 if (TREE_CODE_CLASS (cond1_code
) != tcc_comparison
1241 || TREE_CODE_CLASS (cond2_code
) != tcc_comparison
)
1245 cond1_code
= invert_tree_comparison (cond1_code
, false);
1247 cond2_code
= invert_tree_comparison (cond2_code
, false);
1249 cond1_lhs
= ((gc1
== GIMPLE_ASSIGN
)
1250 ? gimple_assign_rhs1 (cond1
)
1251 : gimple_cond_lhs (cond1
));
1252 cond1_rhs
= ((gc1
== GIMPLE_ASSIGN
)
1253 ? gimple_assign_rhs2 (cond1
)
1254 : gimple_cond_rhs (cond1
));
1255 cond2_lhs
= ((gc2
== GIMPLE_ASSIGN
)
1256 ? gimple_assign_rhs1 (cond2
)
1257 : gimple_cond_lhs (cond2
));
1258 cond2_rhs
= ((gc2
== GIMPLE_ASSIGN
)
1259 ? gimple_assign_rhs2 (cond2
)
1260 : gimple_cond_rhs (cond2
));
1262 /* Assuming const operands have been swapped to the
1263 rhs at this point of the analysis. */
1265 if (cond1_lhs
!= cond2_lhs
)
1268 if (!is_gimple_constant (cond1_rhs
)
1269 || TREE_CODE (cond1_rhs
) != INTEGER_CST
)
1270 return (cond1_rhs
== cond2_rhs
);
1272 if (!is_gimple_constant (cond2_rhs
)
1273 || TREE_CODE (cond2_rhs
) != INTEGER_CST
)
1274 return (cond1_rhs
== cond2_rhs
);
1276 if (cond1_code
== EQ_EXPR
)
1277 return is_value_included_in (cond1_rhs
,
1278 cond2_rhs
, cond2_code
);
1279 if (cond1_code
== NE_EXPR
|| cond2_code
== EQ_EXPR
)
1280 return ((cond2_code
== cond1_code
)
1281 && tree_int_cst_equal (cond1_rhs
, cond2_rhs
));
1283 if (((cond1_code
== GE_EXPR
|| cond1_code
== GT_EXPR
)
1284 && (cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
))
1285 || ((cond1_code
== LE_EXPR
|| cond1_code
== LT_EXPR
)
1286 && (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
)))
1289 if (cond1_code
!= GE_EXPR
&& cond1_code
!= GT_EXPR
1290 && cond1_code
!= LE_EXPR
&& cond1_code
!= LT_EXPR
)
1293 if (cond1_code
== GT_EXPR
)
1295 cond1_code
= GE_EXPR
;
1296 cond1_rhs
= fold_binary (PLUS_EXPR
, TREE_TYPE (cond1_rhs
),
1298 fold_convert (TREE_TYPE (cond1_rhs
),
1301 else if (cond1_code
== LT_EXPR
)
1303 cond1_code
= LE_EXPR
;
1304 cond1_rhs
= fold_binary (MINUS_EXPR
, TREE_TYPE (cond1_rhs
),
1306 fold_convert (TREE_TYPE (cond1_rhs
),
1313 gcc_assert (cond1_code
== GE_EXPR
|| cond1_code
== LE_EXPR
);
1315 if (cond2_code
== GE_EXPR
|| cond2_code
== GT_EXPR
||
1316 cond2_code
== LE_EXPR
|| cond2_code
== LT_EXPR
)
1317 return is_value_included_in (cond1_rhs
,
1318 cond2_rhs
, cond2_code
);
1319 else if (cond2_code
== NE_EXPR
)
1321 (is_value_included_in (cond1_rhs
,
1322 cond2_rhs
, cond2_code
)
1323 && !is_value_included_in (cond2_rhs
,
1324 cond1_rhs
, cond1_code
));
1328 /* Returns true if the domain of the condition expression
1329 in COND is a subset of any of the sub-conditions
1330 of the normalized condtion NORM_COND. INVERT is a flag
1331 to indicate of the COND needs to be inverted.
1332 REVERSE is a flag. When it is true, the check is reversed --
1333 it returns true if COND is a superset of any of the subconditions
1337 is_subset_of_any (gimple cond
, bool invert
,
1338 norm_cond_t norm_cond
, bool reverse
)
1341 size_t len
= VEC_length (gimple
, norm_cond
->conds
);
1343 for (i
= 0; i
< len
; i
++)
1345 if (is_gcond_subset_of (cond
, invert
,
1346 VEC_index (gimple
, norm_cond
->conds
, i
),
1353 /* NORM_COND1 and NORM_COND2 are normalized logical/BIT OR
1354 expressions (formed by following UD chains not control
1355 dependence chains). The function returns true of domain
1356 of and expression NORM_COND1 is a subset of NORM_COND2's.
1357 The implementation is conservative, and it returns false if
1358 it the inclusion relationship may not hold. */
1361 is_or_set_subset_of (norm_cond_t norm_cond1
,
1362 norm_cond_t norm_cond2
)
1365 size_t len
= VEC_length (gimple
, norm_cond1
->conds
);
1367 for (i
= 0; i
< len
; i
++)
1369 if (!is_subset_of_any (VEC_index (gimple
, norm_cond1
->conds
, i
),
1370 false, norm_cond2
, false))
1376 /* NORM_COND1 and NORM_COND2 are normalized logical AND
1377 expressions (formed by following UD chains not control
1378 dependence chains). The function returns true of domain
1379 of and expression NORM_COND1 is a subset of NORM_COND2's. */
1382 is_and_set_subset_of (norm_cond_t norm_cond1
,
1383 norm_cond_t norm_cond2
)
1386 size_t len
= VEC_length (gimple
, norm_cond2
->conds
);
1388 for (i
= 0; i
< len
; i
++)
1390 if (!is_subset_of_any (VEC_index (gimple
, norm_cond2
->conds
, i
),
1391 false, norm_cond1
, true))
1397 /* Returns true of the domain if NORM_COND1 is a subset
1398 of that of NORM_COND2. Returns false if it can not be
1402 is_norm_cond_subset_of (norm_cond_t norm_cond1
,
1403 norm_cond_t norm_cond2
)
1406 enum tree_code code1
, code2
;
1408 code1
= norm_cond1
->cond_code
;
1409 code2
= norm_cond2
->cond_code
;
1411 if (code1
== BIT_AND_EXPR
)
1413 /* Both conditions are AND expressions. */
1414 if (code2
== BIT_AND_EXPR
)
1415 return is_and_set_subset_of (norm_cond1
, norm_cond2
);
1416 /* NORM_COND1 is an AND expression, and NORM_COND2 is an OR
1417 expression. In this case, returns true if any subexpression
1418 of NORM_COND1 is a subset of any subexpression of NORM_COND2. */
1419 else if (code2
== BIT_IOR_EXPR
)
1422 len1
= VEC_length (gimple
, norm_cond1
->conds
);
1423 for (i
= 0; i
< len1
; i
++)
1425 gimple cond1
= VEC_index (gimple
, norm_cond1
->conds
, i
);
1426 if (is_subset_of_any (cond1
, false, norm_cond2
, false))
1433 gcc_assert (code2
== ERROR_MARK
);
1434 gcc_assert (VEC_length (gimple
, norm_cond2
->conds
) == 1);
1435 return is_subset_of_any (VEC_index (gimple
, norm_cond2
->conds
, 0),
1436 norm_cond2
->invert
, norm_cond1
, true);
1439 /* NORM_COND1 is an OR expression */
1440 else if (code1
== BIT_IOR_EXPR
)
1445 return is_or_set_subset_of (norm_cond1
, norm_cond2
);
1449 gcc_assert (code1
== ERROR_MARK
);
1450 gcc_assert (VEC_length (gimple
, norm_cond1
->conds
) == 1);
1451 /* Conservatively returns false if NORM_COND1 is non-decomposible
1452 and NORM_COND2 is an AND expression. */
1453 if (code2
== BIT_AND_EXPR
)
1456 if (code2
== BIT_IOR_EXPR
)
1457 return is_subset_of_any (VEC_index (gimple
, norm_cond1
->conds
, 0),
1458 norm_cond1
->invert
, norm_cond2
, false);
1460 gcc_assert (code2
== ERROR_MARK
);
1461 gcc_assert (VEC_length (gimple
, norm_cond2
->conds
) == 1);
1462 return is_gcond_subset_of (VEC_index (gimple
, norm_cond1
->conds
, 0),
1464 VEC_index (gimple
, norm_cond2
->conds
, 0),
1465 norm_cond2
->invert
, false);
1469 /* Returns true of the domain of single predicate expression
1470 EXPR1 is a subset of that of EXPR2. Returns false if it
1471 can not be proved. */
1474 is_pred_expr_subset_of (use_pred_info_t expr1
,
1475 use_pred_info_t expr2
)
1477 gimple cond1
, cond2
;
1478 enum tree_code code1
, code2
;
1479 struct norm_cond norm_cond1
, norm_cond2
;
1480 bool is_subset
= false;
1482 cond1
= expr1
->cond
;
1483 cond2
= expr2
->cond
;
1484 code1
= gimple_cond_code (cond1
);
1485 code2
= gimple_cond_code (cond2
);
1488 code1
= invert_tree_comparison (code1
, false);
1490 code2
= invert_tree_comparison (code2
, false);
1492 /* Fast path -- match exactly */
1493 if ((gimple_cond_lhs (cond1
) == gimple_cond_lhs (cond2
))
1494 && (gimple_cond_rhs (cond1
) == gimple_cond_rhs (cond2
))
1495 && (code1
== code2
))
1498 /* Normalize conditions. To keep NE_EXPR, do not invert
1499 with both need inversion. */
1500 normalize_cond (cond1
, &norm_cond1
, (expr1
->invert
));
1501 normalize_cond (cond2
, &norm_cond2
, (expr2
->invert
));
1503 is_subset
= is_norm_cond_subset_of (&norm_cond1
, &norm_cond2
);
1506 VEC_free (gimple
, heap
, norm_cond1
.conds
);
1507 VEC_free (gimple
, heap
, norm_cond2
.conds
);
1511 /* Returns true if the domain of PRED1 is a subset
1512 of that of PRED2. Returns false if it can not be proved so. */
1515 is_pred_chain_subset_of (VEC(use_pred_info_t
, heap
) *pred1
,
1516 VEC(use_pred_info_t
, heap
) *pred2
)
1518 size_t np1
, np2
, i1
, i2
;
1520 np1
= VEC_length (use_pred_info_t
, pred1
);
1521 np2
= VEC_length (use_pred_info_t
, pred2
);
1523 for (i2
= 0; i2
< np2
; i2
++)
1526 use_pred_info_t info2
1527 = VEC_index (use_pred_info_t
, pred2
, i2
);
1528 for (i1
= 0; i1
< np1
; i1
++)
1530 use_pred_info_t info1
1531 = VEC_index (use_pred_info_t
, pred1
, i1
);
1532 if (is_pred_expr_subset_of (info1
, info2
))
1544 /* Returns true if the domain defined by
1545 one pred chain ONE_PRED is a subset of the domain
1546 of *PREDS. It returns false if ONE_PRED's domain is
1547 not a subset of any of the sub-domains of PREDS (
1548 corresponding to each individual chains in it), even
1549 though it may be still be a subset of whole domain
1550 of PREDS which is the union (ORed) of all its subdomains.
1551 In other words, the result is conservative. */
1554 is_included_in (VEC(use_pred_info_t
, heap
) *one_pred
,
1555 VEC(use_pred_info_t
, heap
) **preds
,
1560 for (i
= 0; i
< n
; i
++)
1562 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1569 /* compares two predicate sets PREDS1 and PREDS2 and returns
1570 true if the domain defined by PREDS1 is a superset
1571 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1572 PREDS2 respectively. The implementation chooses not to build
1573 generic trees (and relying on the folding capability of the
1574 compiler), but instead performs brute force comparison of
1575 individual predicate chains (won't be a compile time problem
1576 as the chains are pretty short). When the function returns
1577 false, it does not necessarily mean *PREDS1 is not a superset
1578 of *PREDS2, but mean it may not be so since the analysis can
1579 not prove it. In such cases, false warnings may still be
1583 is_superset_of (VEC(use_pred_info_t
, heap
) **preds1
,
1585 VEC(use_pred_info_t
, heap
) **preds2
,
1589 VEC(use_pred_info_t
, heap
) *one_pred_chain
;
1591 for (i
= 0; i
< n2
; i
++)
1593 one_pred_chain
= preds2
[i
];
1594 if (!is_included_in (one_pred_chain
, preds1
, n1
))
1601 /* Comparison function used by qsort. It is used to
1602 sort predicate chains to allow predicate
1606 pred_chain_length_cmp (const void *p1
, const void *p2
)
1608 use_pred_info_t i1
, i2
;
1609 VEC(use_pred_info_t
, heap
) * const *chain1
1610 = (VEC(use_pred_info_t
, heap
) * const *)p1
;
1611 VEC(use_pred_info_t
, heap
) * const *chain2
1612 = (VEC(use_pred_info_t
, heap
) * const *)p2
;
1614 if (VEC_length (use_pred_info_t
, *chain1
)
1615 != VEC_length (use_pred_info_t
, *chain2
))
1616 return (VEC_length (use_pred_info_t
, *chain1
)
1617 - VEC_length (use_pred_info_t
, *chain2
));
1619 i1
= VEC_index (use_pred_info_t
, *chain1
, 0);
1620 i2
= VEC_index (use_pred_info_t
, *chain2
, 0);
1622 /* Allow predicates with similar prefix come together. */
1623 if (!i1
->invert
&& i2
->invert
)
1625 else if (i1
->invert
&& !i2
->invert
)
1628 return gimple_uid (i1
->cond
) - gimple_uid (i2
->cond
);
1631 /* x OR (!x AND y) is equivalent to x OR y.
1632 This function normalizes x1 OR (!x1 AND x2) OR (!x1 AND !x2 AND x3)
1633 into x1 OR x2 OR x3. PREDS is the predicate chains, and N is
1634 the number of chains. Returns true if normalization happens. */
1637 normalize_preds (VEC(use_pred_info_t
, heap
) **preds
, size_t *n
)
1640 VEC(use_pred_info_t
, heap
) *pred_chain
;
1641 VEC(use_pred_info_t
, heap
) *x
= 0;
1642 use_pred_info_t xj
= 0, nxj
= 0;
1647 /* First sort the chains in ascending order of lengths. */
1648 qsort (preds
, *n
, sizeof (void *), pred_chain_length_cmp
);
1649 pred_chain
= preds
[0];
1650 ll
= VEC_length (use_pred_info_t
, pred_chain
);
1655 use_pred_info_t xx
, yy
, xx2
, nyy
;
1656 VEC(use_pred_info_t
, heap
) *pred_chain2
= preds
[1];
1657 if (VEC_length (use_pred_info_t
, pred_chain2
) != 2)
1660 /* See if simplification x AND y OR x AND !y is possible. */
1661 xx
= VEC_index (use_pred_info_t
, pred_chain
, 0);
1662 yy
= VEC_index (use_pred_info_t
, pred_chain
, 1);
1663 xx2
= VEC_index (use_pred_info_t
, pred_chain2
, 0);
1664 nyy
= VEC_index (use_pred_info_t
, pred_chain2
, 1);
1665 if (gimple_cond_lhs (xx
->cond
) != gimple_cond_lhs (xx2
->cond
)
1666 || gimple_cond_rhs (xx
->cond
) != gimple_cond_rhs (xx2
->cond
)
1667 || gimple_cond_code (xx
->cond
) != gimple_cond_code (xx2
->cond
)
1668 || (xx
->invert
!= xx2
->invert
))
1670 if (gimple_cond_lhs (yy
->cond
) != gimple_cond_lhs (nyy
->cond
)
1671 || gimple_cond_rhs (yy
->cond
) != gimple_cond_rhs (nyy
->cond
)
1672 || gimple_cond_code (yy
->cond
) != gimple_cond_code (nyy
->cond
)
1673 || (yy
->invert
== nyy
->invert
))
1676 /* Now merge the first two chains. */
1680 VEC_free (use_pred_info_t
, heap
, pred_chain
);
1681 VEC_free (use_pred_info_t
, heap
, pred_chain2
);
1683 VEC_safe_push (use_pred_info_t
, heap
, pred_chain
, xx
);
1684 preds
[0] = pred_chain
;
1685 for (i
= 1; i
< *n
- 1; i
++)
1686 preds
[i
] = preds
[i
+ 1];
1695 VEC_safe_push (use_pred_info_t
, heap
, x
,
1696 VEC_index (use_pred_info_t
, 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 (VEC_length (use_pred_info_t
, pred_chain
) != i
+ 1)
1706 for (j
= 0; j
< i
; j
++)
1708 xj
= VEC_index (use_pred_info_t
, x
, j
);
1709 nxj
= VEC_index (use_pred_info_t
, 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 VEC_safe_push (use_pred_info_t
, heap
, x
,
1720 VEC_index (use_pred_info_t
, pred_chain
, i
));
1723 /* Now normalize the pred chains using the extraced x1, x2, x3 etc. */
1724 for (j
= 0; j
< *n
; j
++)
1727 xj
= VEC_index (use_pred_info_t
, x
, j
);
1729 t
= XNEW (struct use_pred_info
);
1732 VEC_replace (use_pred_info_t
, x
, j
, t
);
1735 for (i
= 0; i
< *n
; i
++)
1737 pred_chain
= preds
[i
];
1738 for (j
= 0; j
< VEC_length (use_pred_info_t
, pred_chain
); j
++)
1739 free (VEC_index (use_pred_info_t
, pred_chain
, j
));
1740 VEC_free (use_pred_info_t
, heap
, pred_chain
);
1743 VEC_safe_push (use_pred_info_t
, heap
, pred_chain
,
1744 VEC_index (use_pred_info_t
, x
, i
));
1745 preds
[i
] = pred_chain
;
1752 /* Computes the predicates that guard the use and checks
1753 if the incoming paths that have empty (or possibly
1754 empty) definition can be pruned/filtered. The function returns
1755 true if it can be determined that the use of PHI's def in
1756 USE_STMT is guarded with a predicate set not overlapping with
1757 predicate sets of all runtime paths that do not have a definition.
1758 Returns false if it is not or it can not be determined. USE_BB is
1759 the bb of the use (for phi operand use, the bb is not the bb of
1760 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
1761 is a bit vector. If an operand of PHI is uninitialized, the
1762 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
1763 set of phis being visted. */
1766 is_use_properly_guarded (gimple use_stmt
,
1769 unsigned uninit_opnds
,
1770 struct pointer_set_t
*visited_phis
)
1773 VEC(use_pred_info_t
, heap
) **preds
= 0;
1774 VEC(use_pred_info_t
, heap
) **def_preds
= 0;
1775 size_t num_preds
= 0, num_def_preds
= 0;
1776 bool has_valid_preds
= false;
1777 bool is_properly_guarded
= false;
1779 if (pointer_set_insert (visited_phis
, phi
))
1782 phi_bb
= gimple_bb (phi
);
1784 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
1787 has_valid_preds
= find_predicates (&preds
, &num_preds
,
1790 if (!has_valid_preds
)
1792 destroy_predicate_vecs (num_preds
, preds
);
1797 dump_predicates (use_stmt
, num_preds
, preds
,
1800 has_valid_preds
= find_def_preds (&def_preds
,
1801 &num_def_preds
, phi
);
1803 if (has_valid_preds
)
1807 dump_predicates (phi
, num_def_preds
, def_preds
,
1808 "Operand defs of phi ");
1810 normed
= normalize_preds (def_preds
, &num_def_preds
);
1811 if (normed
&& dump_file
)
1813 fprintf (dump_file
, "\nNormalized to\n");
1814 dump_predicates (phi
, num_def_preds
, def_preds
,
1815 "Operand defs of phi ");
1817 is_properly_guarded
=
1818 is_superset_of (def_preds
, num_def_preds
,
1822 /* further prune the dead incoming phi edges. */
1823 if (!is_properly_guarded
)
1825 = use_pred_not_overlap_with_undef_path_pred (
1826 num_preds
, preds
, phi
, uninit_opnds
, visited_phis
);
1828 destroy_predicate_vecs (num_preds
, preds
);
1829 destroy_predicate_vecs (num_def_preds
, def_preds
);
1830 return is_properly_guarded
;
1833 /* Searches through all uses of a potentially
1834 uninitialized variable defined by PHI and returns a use
1835 statement if the use is not properly guarded. It returns
1836 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
1837 holding the position(s) of uninit PHI operands. WORKLIST
1838 is the vector of candidate phis that may be updated by this
1839 function. ADDED_TO_WORKLIST is the pointer set tracking
1840 if the new phi is already in the worklist. */
1843 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
1844 VEC(gimple
, heap
) **worklist
,
1845 struct pointer_set_t
*added_to_worklist
)
1848 use_operand_p use_p
;
1850 imm_use_iterator iter
;
1852 phi_result
= gimple_phi_result (phi
);
1854 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
1856 struct pointer_set_t
*visited_phis
;
1859 use_stmt
= USE_STMT (use_p
);
1860 if (is_gimple_debug (use_stmt
))
1863 visited_phis
= pointer_set_create ();
1865 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
1866 use_bb
= gimple_phi_arg_edge (use_stmt
,
1867 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
1869 use_bb
= gimple_bb (use_stmt
);
1871 if (is_use_properly_guarded (use_stmt
,
1877 pointer_set_destroy (visited_phis
);
1880 pointer_set_destroy (visited_phis
);
1882 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1884 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
1885 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1887 /* Found one real use, return. */
1888 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
1891 /* Found a phi use that is not guarded,
1892 add the phi to the worklist. */
1893 if (!pointer_set_insert (added_to_worklist
,
1896 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1898 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
1899 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
1902 VEC_safe_push (gimple
, heap
, *worklist
, use_stmt
);
1903 pointer_set_insert (possibly_undefined_names
,
1911 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1912 and gives warning if there exists a runtime path from the entry to a
1913 use of the PHI def that does not contain a definition. In other words,
1914 the warning is on the real use. The more dead paths that can be pruned
1915 by the compiler, the fewer false positives the warning is. WORKLIST
1916 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
1917 a pointer set tracking if the new phi is added to the worklist or not. */
1920 warn_uninitialized_phi (gimple phi
, VEC(gimple
, heap
) **worklist
,
1921 struct pointer_set_t
*added_to_worklist
)
1923 unsigned uninit_opnds
;
1924 gimple uninit_use_stmt
= 0;
1927 /* Don't look at memory tags. */
1928 if (!is_gimple_reg (gimple_phi_result (phi
)))
1931 uninit_opnds
= compute_uninit_opnds_pos (phi
);
1933 if (MASK_EMPTY (uninit_opnds
))
1936 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1938 fprintf (dump_file
, "[CHECK]: examining phi: ");
1939 print_gimple_stmt (dump_file
, phi
, 0, 0);
1942 /* Now check if we have any use of the value without proper guard. */
1943 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
1944 worklist
, added_to_worklist
);
1946 /* All uses are properly guarded. */
1947 if (!uninit_use_stmt
)
1950 uninit_op
= gimple_phi_arg_def (phi
, MASK_FIRST_SET_BIT (uninit_opnds
));
1951 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
1952 SSA_NAME_VAR (uninit_op
),
1953 "%qD may be used uninitialized in this function",
1959 /* Entry point to the late uninitialized warning pass. */
1962 execute_late_warn_uninitialized (void)
1965 gimple_stmt_iterator gsi
;
1966 VEC(gimple
, heap
) *worklist
= 0;
1967 struct pointer_set_t
*added_to_worklist
;
1969 calculate_dominance_info (CDI_DOMINATORS
);
1970 calculate_dominance_info (CDI_POST_DOMINATORS
);
1971 /* Re-do the plain uninitialized variable check, as optimization may have
1972 straightened control flow. Do this first so that we don't accidentally
1973 get a "may be" warning when we'd have seen an "is" warning later. */
1974 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1976 timevar_push (TV_TREE_UNINIT
);
1978 possibly_undefined_names
= pointer_set_create ();
1979 added_to_worklist
= pointer_set_create ();
1981 /* Initialize worklist */
1983 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1985 gimple phi
= gsi_stmt (gsi
);
1988 n
= gimple_phi_num_args (phi
);
1990 /* Don't look at memory tags. */
1991 if (!is_gimple_reg (gimple_phi_result (phi
)))
1994 for (i
= 0; i
< n
; ++i
)
1996 tree op
= gimple_phi_arg_def (phi
, i
);
1997 if (TREE_CODE (op
) == SSA_NAME
1998 && ssa_undefined_value_p (op
))
2000 VEC_safe_push (gimple
, heap
, worklist
, phi
);
2001 pointer_set_insert (added_to_worklist
, phi
);
2002 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2004 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2005 print_gimple_stmt (dump_file
, phi
, 0, 0);
2012 while (VEC_length (gimple
, worklist
) != 0)
2015 cur_phi
= VEC_pop (gimple
, worklist
);
2016 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2019 VEC_free (gimple
, heap
, worklist
);
2020 pointer_set_destroy (added_to_worklist
);
2021 pointer_set_destroy (possibly_undefined_names
);
2022 possibly_undefined_names
= NULL
;
2023 free_dominance_info (CDI_POST_DOMINATORS
);
2024 timevar_pop (TV_TREE_UNINIT
);
2029 gate_warn_uninitialized (void)
2031 return warn_uninitialized
!= 0;
2034 struct gimple_opt_pass pass_late_warn_uninitialized
=
2038 "uninit", /* name */
2039 gate_warn_uninitialized
, /* gate */
2040 execute_late_warn_uninitialized
, /* execute */
2043 0, /* static_pass_number */
2044 TV_NONE
, /* tv_id */
2045 PROP_ssa
, /* properties_required */
2046 0, /* properties_provided */
2047 0, /* properties_destroyed */
2048 0, /* todo_flags_start */
2049 0 /* todo_flags_finish */