1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2014 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-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
43 #include "tree-inline.h"
45 #include "tree-pass.h"
46 #include "diagnostic-core.h"
48 /* This implements the pass that does predicate aware warning on uses of
49 possibly uninitialized variables. The pass first collects the set of
50 possibly uninitialized SSA names. For each such name, it walks through
51 all its immediate uses. For each immediate use, it rebuilds the condition
52 expression (the predicate) that guards the use. The predicate is then
53 examined to see if the variable is always defined under that same condition.
54 This is done either by pruning the unrealizable paths that lead to the
55 default definitions or by checking if the predicate set that guards the
56 defining paths is a superset of the use predicate. */
59 /* Pointer set of potentially undefined ssa names, i.e.,
60 ssa names that are defined by phi with operands that
61 are not defined or potentially undefined. */
62 static pointer_set_t
*possibly_undefined_names
= 0;
64 /* Bit mask handling macros. */
65 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
66 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
67 #define MASK_EMPTY(mask) (mask == 0)
69 /* Returns the first bit position (starting from LSB)
70 in mask that is non zero. Returns -1 if the mask is empty. */
72 get_mask_first_set_bit (unsigned mask
)
78 while ((mask
& (1 << pos
)) == 0)
83 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
85 /* Return true if T, an SSA_NAME, has an undefined value. */
87 has_undefined_value_p (tree t
)
89 return (ssa_undefined_value_p (t
)
90 || (possibly_undefined_names
91 && pointer_set_contains (possibly_undefined_names
, t
)));
96 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
97 is set on SSA_NAME_VAR. */
100 uninit_undefined_value_p (tree t
) {
101 if (!has_undefined_value_p (t
))
103 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
108 /* Emit warnings for uninitialized variables. This is done in two passes.
110 The first pass notices real uses of SSA names with undefined values.
111 Such uses are unconditionally uninitialized, and we can be certain that
112 such a use is a mistake. This pass is run before most optimizations,
113 so that we catch as many as we can.
115 The second pass follows PHI nodes to find uses that are potentially
116 uninitialized. In this case we can't necessarily prove that the use
117 is really uninitialized. This pass is run after most optimizations,
118 so that we thread as many jumps and possible, and delete as much dead
119 code as possible, in order to reduce false positives. We also look
120 again for plain uninitialized variables, since optimization may have
121 changed conditionally uninitialized to unconditionally uninitialized. */
123 /* Emit a warning for EXPR based on variable VAR at the point in the
124 program T, an SSA_NAME, is used being uninitialized. The exact
125 warning text is in MSGID and LOCUS may contain a location or be null.
126 WC is the warning code. */
129 warn_uninit (enum opt_code wc
, tree t
,
130 tree expr
, tree var
, const char *gmsgid
, void *data
)
132 gimple context
= (gimple
) data
;
133 location_t location
, cfun_loc
;
134 expanded_location xloc
, floc
;
136 if (!has_undefined_value_p (t
))
139 /* TREE_NO_WARNING either means we already warned, or the front end
140 wishes to suppress the warning. */
142 && (gimple_no_warning_p (context
)
143 || (gimple_assign_single_p (context
)
144 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
145 || TREE_NO_WARNING (expr
))
148 location
= (context
!= NULL
&& gimple_has_location (context
))
149 ? gimple_location (context
)
150 : DECL_SOURCE_LOCATION (var
);
151 location
= linemap_resolve_location (line_table
, location
,
152 LRK_SPELLING_LOCATION
,
154 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
155 xloc
= expand_location (location
);
156 floc
= expand_location (cfun_loc
);
157 if (warning_at (location
, wc
, gmsgid
, expr
))
159 TREE_NO_WARNING (expr
) = 1;
161 if (location
== DECL_SOURCE_LOCATION (var
))
163 if (xloc
.file
!= floc
.file
164 || linemap_location_before_p (line_table
,
166 || linemap_location_before_p (line_table
,
167 cfun
->function_end_locus
,
169 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
174 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
176 gimple_stmt_iterator gsi
;
179 FOR_EACH_BB_FN (bb
, cfun
)
181 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
182 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
183 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
185 gimple stmt
= gsi_stmt (gsi
);
190 if (is_gimple_debug (stmt
))
193 /* We only do data flow with SSA_NAMEs, so that's all we
195 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
197 use
= USE_FROM_PTR (use_p
);
199 warn_uninit (OPT_Wuninitialized
, use
,
200 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
201 "%qD is used uninitialized in this function",
203 else if (warn_possibly_uninitialized
)
204 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
205 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
206 "%qD may be used uninitialized in this function",
210 /* For memory the only cheap thing we can do is see if we
211 have a use of the default def of the virtual operand.
212 ??? Note that at -O0 we do not have virtual operands.
213 ??? Not so cheap would be to use the alias oracle via
214 walk_aliased_vdefs, if we don't find any aliasing vdef
215 warn as is-used-uninitialized, if we don't find an aliasing
216 vdef that kills our use (stmt_kills_ref_p), warn as
217 may-be-used-uninitialized. But this walk is quadratic and
218 so must be limited which means we would miss warning
220 use
= gimple_vuse (stmt
);
222 && gimple_assign_single_p (stmt
)
223 && !gimple_vdef (stmt
)
224 && SSA_NAME_IS_DEFAULT_DEF (use
))
226 tree rhs
= gimple_assign_rhs1 (stmt
);
227 tree base
= get_base_address (rhs
);
229 /* Do not warn if it can be initialized outside this function. */
230 if (TREE_CODE (base
) != VAR_DECL
231 || DECL_HARD_REGISTER (base
)
232 || is_global_var (base
))
236 warn_uninit (OPT_Wuninitialized
, use
,
237 gimple_assign_rhs1 (stmt
), base
,
238 "%qE is used uninitialized in this function",
240 else if (warn_possibly_uninitialized
)
241 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
242 gimple_assign_rhs1 (stmt
), base
,
243 "%qE may be used uninitialized in this function",
252 /* Checks if the operand OPND of PHI is defined by
253 another phi with one operand defined by this PHI,
254 but the rest operands are all defined. If yes,
255 returns true to skip this this operand as being
256 redundant. Can be enhanced to be more general. */
259 can_skip_redundant_opnd (tree opnd
, gimple phi
)
265 phi_def
= gimple_phi_result (phi
);
266 op_def
= SSA_NAME_DEF_STMT (opnd
);
267 if (gimple_code (op_def
) != GIMPLE_PHI
)
269 n
= gimple_phi_num_args (op_def
);
270 for (i
= 0; i
< n
; ++i
)
272 tree op
= gimple_phi_arg_def (op_def
, i
);
273 if (TREE_CODE (op
) != SSA_NAME
)
275 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
282 /* Returns a bit mask holding the positions of arguments in PHI
283 that have empty (or possibly empty) definitions. */
286 compute_uninit_opnds_pos (gimple phi
)
289 unsigned uninit_opnds
= 0;
291 n
= gimple_phi_num_args (phi
);
292 /* Bail out for phi with too many args. */
296 for (i
= 0; i
< n
; ++i
)
298 tree op
= gimple_phi_arg_def (phi
, i
);
299 if (TREE_CODE (op
) == SSA_NAME
300 && uninit_undefined_value_p (op
)
301 && !can_skip_redundant_opnd (op
, phi
))
303 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
305 /* Ignore SSA_NAMEs that appear on abnormal edges
307 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
310 MASK_SET_BIT (uninit_opnds
, i
);
316 /* Find the immediate postdominator PDOM of the specified
317 basic block BLOCK. */
319 static inline basic_block
320 find_pdom (basic_block block
)
322 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
323 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
327 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
329 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
334 /* Find the immediate DOM of the specified
335 basic block BLOCK. */
337 static inline basic_block
338 find_dom (basic_block block
)
340 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
341 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
344 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
346 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
351 /* Returns true if BB1 is postdominating BB2 and BB1 is
352 not a loop exit bb. The loop exit bb check is simple and does
353 not cover all cases. */
356 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
358 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
361 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
367 /* Find the closest postdominator of a specified BB, which is control
370 static inline basic_block
371 find_control_equiv_block (basic_block bb
)
375 pdom
= find_pdom (bb
);
377 /* Skip the postdominating bb that is also loop exit. */
378 if (!is_non_loop_exit_postdominating (pdom
, bb
))
381 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
387 #define MAX_NUM_CHAINS 8
388 #define MAX_CHAIN_LEN 5
389 #define MAX_POSTDOM_CHECK 8
391 /* Computes the control dependence chains (paths of edges)
392 for DEP_BB up to the dominating basic block BB (the head node of a
393 chain should be dominated by it). CD_CHAINS is pointer to a
394 dynamic array holding the result chains. CUR_CD_CHAIN is the current
395 chain being computed. *NUM_CHAINS is total number of chains. The
396 function returns true if the information is successfully computed,
397 return false if there is no control dependence or not computed. */
400 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
401 vec
<edge
> *cd_chains
,
403 vec
<edge
> *cur_cd_chain
)
408 bool found_cd_chain
= false;
409 size_t cur_chain_len
= 0;
411 if (EDGE_COUNT (bb
->succs
) < 2)
414 /* Could use a set instead. */
415 cur_chain_len
= cur_cd_chain
->length ();
416 if (cur_chain_len
> MAX_CHAIN_LEN
)
419 for (i
= 0; i
< cur_chain_len
; i
++)
421 edge e
= (*cur_cd_chain
)[i
];
422 /* Cycle detected. */
427 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
430 int post_dom_check
= 0;
431 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
435 cur_cd_chain
->safe_push (e
);
436 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
440 /* Found a direct control dependence. */
441 if (*num_chains
< MAX_NUM_CHAINS
)
443 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
446 found_cd_chain
= true;
447 /* Check path from next edge. */
451 /* Now check if DEP_BB is indirectly control dependent on BB. */
452 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
453 num_chains
, cur_cd_chain
))
455 found_cd_chain
= true;
459 cd_bb
= find_pdom (cd_bb
);
461 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
465 cur_cd_chain
->pop ();
466 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
468 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
470 return found_cd_chain
;
473 /* The type to represent a simple predicate */
475 typedef struct use_def_pred_info
479 enum tree_code cond_code
;
483 /* The type to represent a sequence of predicates grouped
484 with .AND. operation. */
486 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
488 /* The type to represent a sequence of pred_chains grouped
489 with .OR. operation. */
491 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
493 /* Converts the chains of control dependence edges into a set of
494 predicates. A control dependence chain is represented by a vector
495 edges. DEP_CHAINS points to an array of dependence chains.
496 NUM_CHAINS is the size of the chain array. One edge in a dependence
497 chain is mapped to predicate expression represented by pred_info
498 type. One dependence chain is converted to a composite predicate that
499 is the result of AND operation of pred_info mapped to each edge.
500 A composite predicate is presented by a vector of pred_info. On
501 return, *PREDS points to the resulting array of composite predicates.
502 *NUM_PREDS is the number of composite predictes. */
505 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
507 pred_chain_union
*preds
)
509 bool has_valid_pred
= false;
511 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
514 /* Now convert the control dep chain into a set
516 preds
->reserve (num_chains
);
518 for (i
= 0; i
< num_chains
; i
++)
520 vec
<edge
> one_cd_chain
= dep_chains
[i
];
522 has_valid_pred
= false;
523 pred_chain t_chain
= vNULL
;
524 for (j
= 0; j
< one_cd_chain
.length (); j
++)
527 gimple_stmt_iterator gsi
;
528 basic_block guard_bb
;
534 gsi
= gsi_last_bb (guard_bb
);
537 has_valid_pred
= false;
540 cond_stmt
= gsi_stmt (gsi
);
541 if (is_gimple_call (cond_stmt
)
542 && EDGE_COUNT (e
->src
->succs
) >= 2)
544 /* Ignore EH edge. Can add assertion
545 on the other edge's flag. */
548 /* Skip if there is essentially one succesor. */
549 if (EDGE_COUNT (e
->src
->succs
) == 2)
555 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
557 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
566 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
568 has_valid_pred
= false;
571 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
572 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
573 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
574 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
575 t_chain
.safe_push (one_pred
);
576 has_valid_pred
= true;
582 preds
->safe_push (t_chain
);
584 return has_valid_pred
;
587 /* Computes all control dependence chains for USE_BB. The control
588 dependence chains are then converted to an array of composite
589 predicates pointed to by PREDS. PHI_BB is the basic block of
590 the phi whose result is used in USE_BB. */
593 find_predicates (pred_chain_union
*preds
,
597 size_t num_chains
= 0, i
;
598 vec
<edge
> *dep_chains
= 0;
599 vec
<edge
> cur_chain
= vNULL
;
600 bool has_valid_pred
= false;
601 basic_block cd_root
= 0;
603 typedef vec
<edge
> vec_edge_heap
;
604 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
606 /* First find the closest bb that is control equivalent to PHI_BB
607 that also dominates USE_BB. */
609 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
611 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
612 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
613 cd_root
= ctrl_eq_bb
;
618 compute_control_dep_chain (cd_root
, use_bb
,
619 dep_chains
, &num_chains
,
623 = convert_control_dep_chain_into_preds (dep_chains
,
626 /* Free individual chain */
627 cur_chain
.release ();
628 for (i
= 0; i
< num_chains
; i
++)
629 dep_chains
[i
].release ();
631 return has_valid_pred
;
634 /* Computes the set of incoming edges of PHI that have non empty
635 definitions of a phi chain. The collection will be done
636 recursively on operands that are defined by phis. CD_ROOT
637 is the control dependence root. *EDGES holds the result, and
638 VISITED_PHIS is a pointer set for detecting cycles. */
641 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
643 pointer_set_t
*visited_phis
)
649 if (pointer_set_insert (visited_phis
, phi
))
652 n
= gimple_phi_num_args (phi
);
653 for (i
= 0; i
< n
; i
++)
655 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
656 opnd
= gimple_phi_arg_def (phi
, i
);
658 if (TREE_CODE (opnd
) != SSA_NAME
)
660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
662 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
663 print_gimple_stmt (dump_file
, phi
, 0, 0);
665 edges
->safe_push (opnd_edge
);
669 gimple def
= SSA_NAME_DEF_STMT (opnd
);
671 if (gimple_code (def
) == GIMPLE_PHI
672 && dominated_by_p (CDI_DOMINATORS
,
673 gimple_bb (def
), cd_root
))
674 collect_phi_def_edges (def
, cd_root
, edges
,
676 else if (!uninit_undefined_value_p (opnd
))
678 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
680 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
681 print_gimple_stmt (dump_file
, phi
, 0, 0);
683 edges
->safe_push (opnd_edge
);
689 /* For each use edge of PHI, computes all control dependence chains.
690 The control dependence chains are then converted to an array of
691 composite predicates pointed to by PREDS. */
694 find_def_preds (pred_chain_union
*preds
, gimple phi
)
696 size_t num_chains
= 0, i
, n
;
697 vec
<edge
> *dep_chains
= 0;
698 vec
<edge
> cur_chain
= vNULL
;
699 vec
<edge
> def_edges
= vNULL
;
700 bool has_valid_pred
= false;
701 basic_block phi_bb
, cd_root
= 0;
702 pointer_set_t
*visited_phis
;
704 typedef vec
<edge
> vec_edge_heap
;
705 dep_chains
= XCNEWVEC (vec_edge_heap
, MAX_NUM_CHAINS
);
707 phi_bb
= gimple_bb (phi
);
708 /* First find the closest dominating bb to be
709 the control dependence root */
710 cd_root
= find_dom (phi_bb
);
714 visited_phis
= pointer_set_create ();
715 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
716 pointer_set_destroy (visited_phis
);
718 n
= def_edges
.length ();
722 for (i
= 0; i
< n
; i
++)
727 opnd_edge
= def_edges
[i
];
728 prev_nc
= num_chains
;
729 compute_control_dep_chain (cd_root
, opnd_edge
->src
,
730 dep_chains
, &num_chains
,
732 /* Free individual chain */
733 cur_chain
.release ();
735 /* Now update the newly added chains with
736 the phi operand edge: */
737 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
739 if (prev_nc
== num_chains
740 && num_chains
< MAX_NUM_CHAINS
)
742 for (j
= prev_nc
; j
< num_chains
; j
++)
744 dep_chains
[j
].safe_push (opnd_edge
);
750 = convert_control_dep_chain_into_preds (dep_chains
,
753 for (i
= 0; i
< num_chains
; i
++)
754 dep_chains
[i
].release ();
756 return has_valid_pred
;
759 /* Dumps the predicates (PREDS) for USESTMT. */
762 dump_predicates (gimple usestmt
, pred_chain_union preds
,
766 pred_chain one_pred_chain
= vNULL
;
767 fprintf (dump_file
, msg
);
768 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
769 fprintf (dump_file
, "is guarded by :\n\n");
770 size_t num_preds
= preds
.length ();
771 /* Do some dumping here: */
772 for (i
= 0; i
< num_preds
; i
++)
776 one_pred_chain
= preds
[i
];
777 np
= one_pred_chain
.length ();
779 for (j
= 0; j
< np
; j
++)
781 pred_info one_pred
= one_pred_chain
[j
];
783 fprintf (dump_file
, " (.NOT.) ");
784 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
785 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
786 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
788 fprintf (dump_file
, " (.AND.) ");
790 fprintf (dump_file
, "\n");
792 if (i
< num_preds
- 1)
793 fprintf (dump_file
, "(.OR.)\n");
795 fprintf (dump_file
, "\n\n");
799 /* Destroys the predicate set *PREDS. */
802 destroy_predicate_vecs (pred_chain_union preds
)
806 size_t n
= preds
.length ();
807 for (i
= 0; i
< n
; i
++)
813 /* Computes the 'normalized' conditional code with operand
814 swapping and condition inversion. */
816 static enum tree_code
817 get_cmp_code (enum tree_code orig_cmp_code
,
818 bool swap_cond
, bool invert
)
820 enum tree_code tc
= orig_cmp_code
;
823 tc
= swap_tree_comparison (orig_cmp_code
);
825 tc
= invert_tree_comparison (tc
, false);
842 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
843 all values in the range satisfies (x CMPC BOUNDARY) == true. */
846 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
848 bool inverted
= false;
852 /* Only handle integer constant here. */
853 if (TREE_CODE (val
) != INTEGER_CST
854 || TREE_CODE (boundary
) != INTEGER_CST
)
857 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
859 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
862 cmpc
= invert_tree_comparison (cmpc
, false);
869 result
= tree_int_cst_equal (val
, boundary
);
870 else if (cmpc
== LT_EXPR
)
871 result
= INT_CST_LT_UNSIGNED (val
, boundary
);
874 gcc_assert (cmpc
== LE_EXPR
);
875 result
= (tree_int_cst_equal (val
, boundary
)
876 || INT_CST_LT_UNSIGNED (val
, boundary
));
882 result
= tree_int_cst_equal (val
, boundary
);
883 else if (cmpc
== LT_EXPR
)
884 result
= INT_CST_LT (val
, boundary
);
887 gcc_assert (cmpc
== LE_EXPR
);
888 result
= (tree_int_cst_equal (val
, boundary
)
889 || INT_CST_LT (val
, boundary
));
899 /* Returns true if PRED is common among all the predicate
900 chains (PREDS) (and therefore can be factored out).
901 NUM_PRED_CHAIN is the size of array PREDS. */
904 find_matching_predicate_in_rest_chains (pred_info pred
,
905 pred_chain_union preds
,
906 size_t num_pred_chains
)
911 if (num_pred_chains
== 1)
914 for (i
= 1; i
< num_pred_chains
; i
++)
917 pred_chain one_chain
= preds
[i
];
918 n
= one_chain
.length ();
919 for (j
= 0; j
< n
; j
++)
921 pred_info pred2
= one_chain
[j
];
922 /* Can relax the condition comparison to not
923 use address comparison. However, the most common
924 case is that multiple control dependent paths share
925 a common path prefix, so address comparison should
928 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
929 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
930 && pred2
.invert
== pred
.invert
)
942 /* Forward declaration. */
944 is_use_properly_guarded (gimple use_stmt
,
947 unsigned uninit_opnds
,
948 pointer_set_t
*visited_phis
);
950 /* Returns true if all uninitialized opnds are pruned. Returns false
951 otherwise. PHI is the phi node with uninitialized operands,
952 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
953 FLAG_DEF is the statement defining the flag guarding the use of the
954 PHI output, BOUNDARY_CST is the const value used in the predicate
955 associated with the flag, CMP_CODE is the comparison code used in
956 the predicate, VISITED_PHIS is the pointer set of phis visited, and
957 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
963 flag_1 = phi <0, 1> // (1)
964 var_1 = phi <undef, some_val>
968 flag_2 = phi <0, flag_1, flag_1> // (2)
969 var_2 = phi <undef, var_1, var_1>
976 Because some flag arg in (1) is not constant, if we do not look into the
977 flag phis recursively, it is conservatively treated as unknown and var_1
978 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
979 a false warning will be emitted. Checking recursively into (1), the compiler can
980 find out that only some_val (which is defined) can flow into (3) which is OK.
985 prune_uninit_phi_opnds_in_unrealizable_paths (gimple phi
,
986 unsigned uninit_opnds
,
989 enum tree_code cmp_code
,
990 pointer_set_t
*visited_phis
,
991 bitmap
*visited_flag_phis
)
995 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
999 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1002 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1003 if (!is_gimple_constant (flag_arg
))
1005 gimple flag_arg_def
, phi_arg_def
;
1007 unsigned uninit_opnds_arg_phi
;
1009 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1011 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
1012 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
1015 phi_arg
= gimple_phi_arg_def (phi
, i
);
1016 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1019 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
1020 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
1023 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1026 if (!*visited_flag_phis
)
1027 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1029 if (bitmap_bit_p (*visited_flag_phis
,
1030 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1033 bitmap_set_bit (*visited_flag_phis
,
1034 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1036 /* Now recursively prune the uninitialized phi args. */
1037 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1038 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1039 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1040 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1043 bitmap_clear_bit (*visited_flag_phis
,
1044 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1048 /* Now check if the constant is in the guarded range. */
1049 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1054 /* Now that we know that this undefined edge is not
1055 pruned. If the operand is defined by another phi,
1056 we can further prune the incoming edges of that
1057 phi by checking the predicates of this operands. */
1059 opnd
= gimple_phi_arg_def (phi
, i
);
1060 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1061 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
1064 unsigned uninit_opnds2
1065 = compute_uninit_opnds_pos (opnd_def
);
1066 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
1067 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1068 if (!is_use_properly_guarded (phi
,
1083 /* A helper function that determines if the predicate set
1084 of the use is not overlapping with that of the uninit paths.
1085 The most common senario of guarded use is in Example 1:
1098 The real world examples are usually more complicated, but similar
1099 and usually result from inlining:
1101 bool init_func (int * x)
1120 Another possible use scenario is in the following trivial example:
1132 Predicate analysis needs to compute the composite predicate:
1134 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1135 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1136 (the predicate chain for phi operand defs can be computed
1137 starting from a bb that is control equivalent to the phi's
1138 bb and is dominating the operand def.)
1140 and check overlapping:
1141 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1144 This implementation provides framework that can handle
1145 scenarios. (Note that many simple cases are handled properly
1146 without the predicate analysis -- this is due to jump threading
1147 transformation which eliminates the merge point thus makes
1148 path sensitive analysis unnecessary.)
1150 NUM_PREDS is the number is the number predicate chains, PREDS is
1151 the array of chains, PHI is the phi node whose incoming (undefined)
1152 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1153 uninit operand positions. VISITED_PHIS is the pointer set of phi
1154 stmts being checked. */
1158 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1159 gimple phi
, unsigned uninit_opnds
,
1160 pointer_set_t
*visited_phis
)
1163 gimple flag_def
= 0;
1164 tree boundary_cst
= 0;
1165 enum tree_code cmp_code
;
1166 bool swap_cond
= false;
1167 bool invert
= false;
1168 pred_chain the_pred_chain
= vNULL
;
1169 bitmap visited_flag_phis
= NULL
;
1170 bool all_pruned
= false;
1171 size_t num_preds
= preds
.length ();
1173 gcc_assert (num_preds
> 0);
1174 /* Find within the common prefix of multiple predicate chains
1175 a predicate that is a comparison of a flag variable against
1177 the_pred_chain
= preds
[0];
1178 n
= the_pred_chain
.length ();
1179 for (i
= 0; i
< n
; i
++)
1181 tree cond_lhs
, cond_rhs
, flag
= 0;
1183 pred_info the_pred
= the_pred_chain
[i
];
1185 invert
= the_pred
.invert
;
1186 cond_lhs
= the_pred
.pred_lhs
;
1187 cond_rhs
= the_pred
.pred_rhs
;
1188 cmp_code
= the_pred
.cond_code
;
1190 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1191 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1193 boundary_cst
= cond_rhs
;
1196 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1197 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1199 boundary_cst
= cond_lhs
;
1207 flag_def
= SSA_NAME_DEF_STMT (flag
);
1212 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1213 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1214 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1224 /* Now check all the uninit incoming edge has a constant flag value
1225 that is in conflict with the use guard/predicate. */
1226 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1228 if (cmp_code
== ERROR_MARK
)
1231 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1237 &visited_flag_phis
);
1239 if (visited_flag_phis
)
1240 BITMAP_FREE (visited_flag_phis
);
1245 /* The helper function returns true if two predicates X1 and X2
1246 are equivalent. It assumes the expressions have already
1247 properly re-associated. */
1250 pred_equal_p (pred_info x1
, pred_info x2
)
1252 enum tree_code c1
, c2
;
1253 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1254 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1258 if (x1
.invert
!= x2
.invert
)
1259 c2
= invert_tree_comparison (x2
.cond_code
, false);
1266 /* Returns true if the predication is testing !=. */
1269 is_neq_relop_p (pred_info pred
)
1272 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1273 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1276 /* Returns true if pred is of the form X != 0. */
1279 is_neq_zero_form_p (pred_info pred
)
1281 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1282 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1287 /* The helper function returns true if two predicates X1
1288 is equivalent to X2 != 0. */
1291 pred_expr_equal_p (pred_info x1
, tree x2
)
1293 if (!is_neq_zero_form_p (x1
))
1296 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1299 /* Returns true of the domain of single predicate expression
1300 EXPR1 is a subset of that of EXPR2. Returns false if it
1301 can not be proved. */
1304 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1306 enum tree_code code1
, code2
;
1308 if (pred_equal_p (expr1
, expr2
))
1311 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1312 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1315 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1318 code1
= expr1
.cond_code
;
1320 code1
= invert_tree_comparison (code1
, false);
1321 code2
= expr2
.cond_code
;
1323 code2
= invert_tree_comparison (code2
, false);
1325 if (code1
!= code2
&& code2
!= NE_EXPR
)
1328 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1334 /* Returns true if the domain of PRED1 is a subset
1335 of that of PRED2. Returns false if it can not be proved so. */
1338 is_pred_chain_subset_of (pred_chain pred1
,
1341 size_t np1
, np2
, i1
, i2
;
1343 np1
= pred1
.length ();
1344 np2
= pred2
.length ();
1346 for (i2
= 0; i2
< np2
; i2
++)
1349 pred_info info2
= pred2
[i2
];
1350 for (i1
= 0; i1
< np1
; i1
++)
1352 pred_info info1
= pred1
[i1
];
1353 if (is_pred_expr_subset_of (info1
, info2
))
1365 /* Returns true if the domain defined by
1366 one pred chain ONE_PRED is a subset of the domain
1367 of *PREDS. It returns false if ONE_PRED's domain is
1368 not a subset of any of the sub-domains of PREDS
1369 (corresponding to each individual chains in it), even
1370 though it may be still be a subset of whole domain
1371 of PREDS which is the union (ORed) of all its subdomains.
1372 In other words, the result is conservative. */
1375 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1378 size_t n
= preds
.length ();
1380 for (i
= 0; i
< n
; i
++)
1382 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1389 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1390 true if the domain defined by PREDS1 is a superset
1391 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1392 PREDS2 respectively. The implementation chooses not to build
1393 generic trees (and relying on the folding capability of the
1394 compiler), but instead performs brute force comparison of
1395 individual predicate chains (won't be a compile time problem
1396 as the chains are pretty short). When the function returns
1397 false, it does not necessarily mean *PREDS1 is not a superset
1398 of *PREDS2, but mean it may not be so since the analysis can
1399 not prove it. In such cases, false warnings may still be
1403 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1406 pred_chain one_pred_chain
= vNULL
;
1408 n2
= preds2
.length ();
1410 for (i
= 0; i
< n2
; i
++)
1412 one_pred_chain
= preds2
[i
];
1413 if (!is_included_in (one_pred_chain
, preds1
))
1420 /* Returns true if TC is AND or OR. */
1423 is_and_or_or_p (enum tree_code tc
, tree type
)
1425 return (tc
== BIT_IOR_EXPR
1426 || (tc
== BIT_AND_EXPR
1427 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1430 /* Returns true if X1 is the negate of X2. */
1433 pred_neg_p (pred_info x1
, pred_info x2
)
1435 enum tree_code c1
, c2
;
1436 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1437 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1441 if (x1
.invert
== x2
.invert
)
1442 c2
= invert_tree_comparison (x2
.cond_code
, false);
1449 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1450 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1451 3) X OR (!X AND Y) is equivalent to (X OR Y);
1452 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1454 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1457 PREDS is the predicate chains, and N is the number of chains. */
1459 /* Helper function to implement rule 1 above. ONE_CHAIN is
1460 the AND predication to be simplified. */
1463 simplify_pred (pred_chain
*one_chain
)
1466 bool simplified
= false;
1467 pred_chain s_chain
= vNULL
;
1469 n
= one_chain
->length ();
1471 for (i
= 0; i
< n
; i
++)
1473 pred_info
*a_pred
= &(*one_chain
)[i
];
1475 if (!a_pred
->pred_lhs
)
1477 if (!is_neq_zero_form_p (*a_pred
))
1480 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1481 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1483 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1485 for (j
= 0; j
< n
; j
++)
1487 pred_info
*b_pred
= &(*one_chain
)[j
];
1489 if (!b_pred
->pred_lhs
)
1491 if (!is_neq_zero_form_p (*b_pred
))
1494 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1495 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1497 /* Mark a_pred for removal. */
1498 a_pred
->pred_lhs
= NULL
;
1499 a_pred
->pred_rhs
= NULL
;
1510 for (i
= 0; i
< n
; i
++)
1512 pred_info
*a_pred
= &(*one_chain
)[i
];
1513 if (!a_pred
->pred_lhs
)
1515 s_chain
.safe_push (*a_pred
);
1518 one_chain
->release ();
1519 *one_chain
= s_chain
;
1522 /* The helper function implements the rule 2 for the
1525 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1528 simplify_preds_2 (pred_chain_union
*preds
)
1531 bool simplified
= false;
1532 pred_chain_union s_preds
= vNULL
;
1534 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1535 (X AND Y) OR (X AND !Y) is equivalent to X. */
1537 n
= preds
->length ();
1538 for (i
= 0; i
< n
; i
++)
1541 pred_chain
*a_chain
= &(*preds
)[i
];
1543 if (a_chain
->length () != 2)
1549 for (j
= 0; j
< n
; j
++)
1551 pred_chain
*b_chain
;
1557 b_chain
= &(*preds
)[j
];
1558 if (b_chain
->length () != 2)
1564 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1567 a_chain
->release ();
1568 b_chain
->release ();
1569 b_chain
->safe_push (x
);
1573 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1576 a_chain
->release ();
1577 b_chain
->release ();
1578 b_chain
->safe_push (y
);
1584 /* Now clean up the chain. */
1587 for (i
= 0; i
< n
; i
++)
1589 if ((*preds
)[i
].is_empty ())
1591 s_preds
.safe_push ((*preds
)[i
]);
1601 /* The helper function implements the rule 2 for the
1604 3) x OR (!x AND y) is equivalent to x OR y. */
1607 simplify_preds_3 (pred_chain_union
*preds
)
1610 bool simplified
= false;
1612 /* Now iteratively simplify X OR (!X AND Z ..)
1613 into X OR (Z ...). */
1615 n
= preds
->length ();
1619 for (i
= 0; i
< n
; i
++)
1622 pred_chain
*a_chain
= &(*preds
)[i
];
1624 if (a_chain
->length () != 1)
1629 for (j
= 0; j
< n
; j
++)
1631 pred_chain
*b_chain
;
1638 b_chain
= &(*preds
)[j
];
1639 if (b_chain
->length () < 2)
1642 for (k
= 0; k
< b_chain
->length (); k
++)
1645 if (pred_neg_p (x
, x2
))
1647 b_chain
->unordered_remove (k
);
1657 /* The helper function implements the rule 4 for the
1660 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1661 (x != 0 ANd y != 0). */
1664 simplify_preds_4 (pred_chain_union
*preds
)
1667 bool simplified
= false;
1668 pred_chain_union s_preds
= vNULL
;
1671 n
= preds
->length ();
1672 for (i
= 0; i
< n
; i
++)
1675 pred_chain
*a_chain
= &(*preds
)[i
];
1677 if (a_chain
->length () != 1)
1682 if (!is_neq_zero_form_p (z
))
1685 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1686 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1689 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1692 for (j
= 0; j
< n
; j
++)
1694 pred_chain
*b_chain
;
1700 b_chain
= &(*preds
)[j
];
1701 if (b_chain
->length () != 2)
1706 if (!is_neq_zero_form_p (x2
)
1707 || !is_neq_zero_form_p (y2
))
1710 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1711 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1712 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1713 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1716 a_chain
->release ();
1722 /* Now clean up the chain. */
1725 for (i
= 0; i
< n
; i
++)
1727 if ((*preds
)[i
].is_empty ())
1729 s_preds
.safe_push ((*preds
)[i
]);
1740 /* This function simplifies predicates in PREDS. */
1743 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1746 bool changed
= false;
1748 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1750 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1751 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1754 for (i
= 0; i
< preds
->length (); i
++)
1755 simplify_pred (&(*preds
)[i
]);
1757 n
= preds
->length ();
1764 if (simplify_preds_2 (preds
))
1767 /* Now iteratively simplify X OR (!X AND Z ..)
1768 into X OR (Z ...). */
1769 if (simplify_preds_3 (preds
))
1772 if (simplify_preds_4 (preds
))
1780 /* This is a helper function which attempts to normalize predicate chains
1781 by following UD chains. It basically builds up a big tree of either IOR
1782 operations or AND operations, and convert the IOR tree into a
1783 pred_chain_union or BIT_AND tree into a pred_chain.
1793 then _t != 0 will be normalized into a pred_chain_union
1795 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1805 then _t != 0 will be normalized into a pred_chain:
1806 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1810 /* This is a helper function that stores a PRED into NORM_PREDS. */
1813 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1815 pred_chain pred_chain
= vNULL
;
1816 pred_chain
.safe_push (pred
);
1817 norm_preds
->safe_push (pred_chain
);
1820 /* A helper function that creates a predicate of the form
1821 OP != 0 and push it WORK_LIST. */
1824 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
)
1827 arg_pred
.pred_lhs
= op
;
1828 arg_pred
.pred_rhs
= integer_zero_node
;
1829 arg_pred
.cond_code
= NE_EXPR
;
1830 arg_pred
.invert
= false;
1831 work_list
->safe_push (arg_pred
);
1834 /* A helper that generates a pred_info from a gimple assignment
1835 CMP_ASSIGN with comparison rhs. */
1838 get_pred_info_from_cmp (gimple cmp_assign
)
1841 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1842 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1843 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1844 n_pred
.invert
= false;
1848 /* Returns true if the PHI is a degenerated phi with
1849 all args with the same value (relop). In that case, *PRED
1850 will be updated to that value. */
1853 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1860 n
= gimple_phi_num_args (phi
);
1861 op0
= gimple_phi_arg_def (phi
, 0);
1863 if (TREE_CODE (op0
) != SSA_NAME
)
1866 def0
= SSA_NAME_DEF_STMT (op0
);
1867 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1869 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1872 pred0
= get_pred_info_from_cmp (def0
);
1874 for (i
= 1; i
< n
; ++i
)
1878 tree op
= gimple_phi_arg_def (phi
, i
);
1880 if (TREE_CODE (op
) != SSA_NAME
)
1883 def
= SSA_NAME_DEF_STMT (op
);
1884 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1886 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1889 pred
= get_pred_info_from_cmp (def
);
1890 if (!pred_equal_p (pred
, pred0
))
1898 /* Normalize one predicate PRED
1899 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1900 2) otherwise if PRED is of the form x != 0, follow x's definition
1901 and put normalized predicates into WORK_LIST. */
1904 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1905 pred_chain
*norm_chain
,
1907 enum tree_code and_or_code
,
1908 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
)
1910 if (!is_neq_zero_form_p (pred
))
1912 if (and_or_code
== BIT_IOR_EXPR
)
1913 push_pred (norm_preds
, pred
);
1915 norm_chain
->safe_push (pred
);
1919 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1921 if (gimple_code (def_stmt
) == GIMPLE_PHI
1922 && is_degenerated_phi (def_stmt
, &pred
))
1923 work_list
->safe_push (pred
);
1924 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1925 && and_or_code
== BIT_IOR_EXPR
)
1928 n
= gimple_phi_num_args (def_stmt
);
1930 /* If we see non zero constant, we should punt. The predicate
1931 * should be one guarding the phi edge. */
1932 for (i
= 0; i
< n
; ++i
)
1934 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1935 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1937 push_pred (norm_preds
, pred
);
1942 for (i
= 0; i
< n
; ++i
)
1944 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1945 if (integer_zerop (op
))
1948 push_to_worklist (op
, work_list
);
1951 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1953 if (and_or_code
== BIT_IOR_EXPR
)
1954 push_pred (norm_preds
, pred
);
1956 norm_chain
->safe_push (pred
);
1958 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
1960 push_to_worklist (gimple_assign_rhs1 (def_stmt
),
1962 push_to_worklist (gimple_assign_rhs2 (def_stmt
),
1965 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
1968 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
1969 if (and_or_code
== BIT_IOR_EXPR
)
1970 push_pred (norm_preds
, n_pred
);
1972 norm_chain
->safe_push (n_pred
);
1976 if (and_or_code
== BIT_IOR_EXPR
)
1977 push_pred (norm_preds
, pred
);
1979 norm_chain
->safe_push (pred
);
1983 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1986 normalize_one_pred (pred_chain_union
*norm_preds
,
1989 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
1990 enum tree_code and_or_code
= ERROR_MARK
;
1991 pred_chain norm_chain
= vNULL
;
1993 if (!is_neq_zero_form_p (pred
))
1995 push_pred (norm_preds
, pred
);
1999 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2000 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2001 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2002 if (and_or_code
!= BIT_IOR_EXPR
2003 && and_or_code
!= BIT_AND_EXPR
)
2005 if (TREE_CODE_CLASS (and_or_code
)
2008 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2009 push_pred (norm_preds
, n_pred
);
2012 push_pred (norm_preds
, pred
);
2016 work_list
.safe_push (pred
);
2017 while (!work_list
.is_empty ())
2019 pred_info a_pred
= work_list
.pop ();
2020 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2021 and_or_code
, &work_list
);
2023 if (and_or_code
== BIT_AND_EXPR
)
2024 norm_preds
->safe_push (norm_chain
);
2026 work_list
.release ();
2030 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2031 pred_chain one_chain
)
2033 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2034 pred_chain norm_chain
= vNULL
;
2037 for (i
= 0; i
< one_chain
.length (); i
++)
2038 work_list
.safe_push (one_chain
[i
]);
2040 while (!work_list
.is_empty ())
2042 pred_info a_pred
= work_list
.pop ();
2043 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2044 BIT_AND_EXPR
, &work_list
);
2047 norm_preds
->safe_push (norm_chain
);
2048 work_list
.release ();
2051 /* Normalize predicate chains PREDS and returns the normalized one. */
2053 static pred_chain_union
2054 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2056 pred_chain_union norm_preds
= vNULL
;
2057 size_t n
= preds
.length ();
2060 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2062 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2063 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2066 for (i
= 0; i
< n
; i
++)
2068 if (preds
[i
].length () != 1)
2069 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2072 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2073 preds
[i
].release ();
2079 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2080 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2088 /* Computes the predicates that guard the use and checks
2089 if the incoming paths that have empty (or possibly
2090 empty) definition can be pruned/filtered. The function returns
2091 true if it can be determined that the use of PHI's def in
2092 USE_STMT is guarded with a predicate set not overlapping with
2093 predicate sets of all runtime paths that do not have a definition.
2094 Returns false if it is not or it can not be determined. USE_BB is
2095 the bb of the use (for phi operand use, the bb is not the bb of
2096 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2097 is a bit vector. If an operand of PHI is uninitialized, the
2098 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2099 set of phis being visted. */
2102 is_use_properly_guarded (gimple use_stmt
,
2105 unsigned uninit_opnds
,
2106 pointer_set_t
*visited_phis
)
2109 pred_chain_union preds
= vNULL
;
2110 pred_chain_union def_preds
= vNULL
;
2111 bool has_valid_preds
= false;
2112 bool is_properly_guarded
= false;
2114 if (pointer_set_insert (visited_phis
, phi
))
2117 phi_bb
= gimple_bb (phi
);
2119 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2122 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2124 if (!has_valid_preds
)
2126 destroy_predicate_vecs (preds
);
2130 /* Try to prune the dead incoming phi edges. */
2132 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2135 if (is_properly_guarded
)
2137 destroy_predicate_vecs (preds
);
2141 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2143 if (!has_valid_preds
)
2145 destroy_predicate_vecs (preds
);
2146 destroy_predicate_vecs (def_preds
);
2150 simplify_preds (&preds
, use_stmt
, true);
2151 preds
= normalize_preds (preds
, use_stmt
, true);
2153 simplify_preds (&def_preds
, phi
, false);
2154 def_preds
= normalize_preds (def_preds
, phi
, false);
2156 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2158 destroy_predicate_vecs (preds
);
2159 destroy_predicate_vecs (def_preds
);
2160 return is_properly_guarded
;
2163 /* Searches through all uses of a potentially
2164 uninitialized variable defined by PHI and returns a use
2165 statement if the use is not properly guarded. It returns
2166 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2167 holding the position(s) of uninit PHI operands. WORKLIST
2168 is the vector of candidate phis that may be updated by this
2169 function. ADDED_TO_WORKLIST is the pointer set tracking
2170 if the new phi is already in the worklist. */
2173 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
2174 vec
<gimple
> *worklist
,
2175 pointer_set_t
*added_to_worklist
)
2178 use_operand_p use_p
;
2180 imm_use_iterator iter
;
2182 phi_result
= gimple_phi_result (phi
);
2184 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2186 pointer_set_t
*visited_phis
;
2189 use_stmt
= USE_STMT (use_p
);
2190 if (is_gimple_debug (use_stmt
))
2193 visited_phis
= pointer_set_create ();
2195 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2196 use_bb
= gimple_phi_arg_edge (use_stmt
,
2197 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2199 use_bb
= gimple_bb (use_stmt
);
2201 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2204 pointer_set_destroy (visited_phis
);
2207 pointer_set_destroy (visited_phis
);
2209 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2211 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2212 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2214 /* Found one real use, return. */
2215 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2218 /* Found a phi use that is not guarded,
2219 add the phi to the worklist. */
2220 if (!pointer_set_insert (added_to_worklist
, use_stmt
))
2222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2224 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2225 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2228 worklist
->safe_push (use_stmt
);
2229 pointer_set_insert (possibly_undefined_names
, phi_result
);
2236 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2237 and gives warning if there exists a runtime path from the entry to a
2238 use of the PHI def that does not contain a definition. In other words,
2239 the warning is on the real use. The more dead paths that can be pruned
2240 by the compiler, the fewer false positives the warning is. WORKLIST
2241 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2242 a pointer set tracking if the new phi is added to the worklist or not. */
2245 warn_uninitialized_phi (gimple phi
, vec
<gimple
> *worklist
,
2246 pointer_set_t
*added_to_worklist
)
2248 unsigned uninit_opnds
;
2249 gimple uninit_use_stmt
= 0;
2252 /* Don't look at virtual operands. */
2253 if (virtual_operand_p (gimple_phi_result (phi
)))
2256 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2258 if (MASK_EMPTY (uninit_opnds
))
2261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2263 fprintf (dump_file
, "[CHECK]: examining phi: ");
2264 print_gimple_stmt (dump_file
, phi
, 0, 0);
2267 /* Now check if we have any use of the value without proper guard. */
2268 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2269 worklist
, added_to_worklist
);
2271 /* All uses are properly guarded. */
2272 if (!uninit_use_stmt
)
2275 uninit_op
= gimple_phi_arg_def (phi
, MASK_FIRST_SET_BIT (uninit_opnds
));
2276 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2278 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2279 SSA_NAME_VAR (uninit_op
),
2280 "%qD may be used uninitialized in this function",
2286 /* Entry point to the late uninitialized warning pass. */
2289 execute_late_warn_uninitialized (void)
2292 gimple_stmt_iterator gsi
;
2293 vec
<gimple
> worklist
= vNULL
;
2294 pointer_set_t
*added_to_worklist
;
2296 calculate_dominance_info (CDI_DOMINATORS
);
2297 calculate_dominance_info (CDI_POST_DOMINATORS
);
2298 /* Re-do the plain uninitialized variable check, as optimization may have
2299 straightened control flow. Do this first so that we don't accidentally
2300 get a "may be" warning when we'd have seen an "is" warning later. */
2301 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2303 timevar_push (TV_TREE_UNINIT
);
2305 possibly_undefined_names
= pointer_set_create ();
2306 added_to_worklist
= pointer_set_create ();
2308 /* Initialize worklist */
2309 FOR_EACH_BB_FN (bb
, cfun
)
2310 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2312 gimple phi
= gsi_stmt (gsi
);
2315 n
= gimple_phi_num_args (phi
);
2317 /* Don't look at virtual operands. */
2318 if (virtual_operand_p (gimple_phi_result (phi
)))
2321 for (i
= 0; i
< n
; ++i
)
2323 tree op
= gimple_phi_arg_def (phi
, i
);
2324 if (TREE_CODE (op
) == SSA_NAME
2325 && uninit_undefined_value_p (op
))
2327 worklist
.safe_push (phi
);
2328 pointer_set_insert (added_to_worklist
, phi
);
2329 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2331 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2332 print_gimple_stmt (dump_file
, phi
, 0, 0);
2339 while (worklist
.length () != 0)
2342 cur_phi
= worklist
.pop ();
2343 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2346 worklist
.release ();
2347 pointer_set_destroy (added_to_worklist
);
2348 pointer_set_destroy (possibly_undefined_names
);
2349 possibly_undefined_names
= NULL
;
2350 free_dominance_info (CDI_POST_DOMINATORS
);
2351 timevar_pop (TV_TREE_UNINIT
);
2356 gate_warn_uninitialized (void)
2358 return warn_uninitialized
!= 0;
2363 const pass_data pass_data_late_warn_uninitialized
=
2365 GIMPLE_PASS
, /* type */
2366 "uninit", /* name */
2367 OPTGROUP_NONE
, /* optinfo_flags */
2368 true, /* has_gate */
2369 true, /* has_execute */
2370 TV_NONE
, /* tv_id */
2371 PROP_ssa
, /* properties_required */
2372 0, /* properties_provided */
2373 0, /* properties_destroyed */
2374 0, /* todo_flags_start */
2375 0, /* todo_flags_finish */
2378 class pass_late_warn_uninitialized
: public gimple_opt_pass
2381 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2382 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2385 /* opt_pass methods: */
2386 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2387 bool gate () { return gate_warn_uninitialized (); }
2388 unsigned int execute () { return execute_late_warn_uninitialized (); }
2390 }; // class pass_late_warn_uninitialized
2395 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2397 return new pass_late_warn_uninitialized (ctxt
);
2402 execute_early_warn_uninitialized (void)
2404 /* Currently, this pass runs always but
2405 execute_late_warn_uninitialized only runs with optimization. With
2406 optimization we want to warn about possible uninitialized as late
2407 as possible, thus don't do it here. However, without
2408 optimization we need to warn here about "may be uninitialized". */
2409 calculate_dominance_info (CDI_POST_DOMINATORS
);
2411 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2413 /* Post-dominator information can not be reliably updated. Free it
2416 free_dominance_info (CDI_POST_DOMINATORS
);
2423 const pass_data pass_data_early_warn_uninitialized
=
2425 GIMPLE_PASS
, /* type */
2426 "*early_warn_uninitialized", /* name */
2427 OPTGROUP_NONE
, /* optinfo_flags */
2428 true, /* has_gate */
2429 true, /* has_execute */
2430 TV_TREE_UNINIT
, /* tv_id */
2431 PROP_ssa
, /* properties_required */
2432 0, /* properties_provided */
2433 0, /* properties_destroyed */
2434 0, /* todo_flags_start */
2435 0, /* todo_flags_finish */
2438 class pass_early_warn_uninitialized
: public gimple_opt_pass
2441 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2442 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2445 /* opt_pass methods: */
2446 bool gate () { return gate_warn_uninitialized (); }
2447 unsigned int execute () { return execute_early_warn_uninitialized (); }
2449 }; // class pass_early_warn_uninitialized
2454 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2456 return new pass_early_warn_uninitialized (ctxt
);