1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2015 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 "double-int.h"
35 #include "fold-const.h"
39 #include "hard-reg-set.h"
42 #include "dominance.h"
44 #include "basic-block.h"
45 #include "gimple-pretty-print.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
52 #include "gimple-iterator.h"
53 #include "gimple-ssa.h"
54 #include "tree-phinodes.h"
55 #include "ssa-iterators.h"
57 #include "tree-inline.h"
58 #include "tree-pass.h"
59 #include "diagnostic-core.h"
63 /* This implements the pass that does predicate aware warning on uses of
64 possibly uninitialized variables. The pass first collects the set of
65 possibly uninitialized SSA names. For each such name, it walks through
66 all its immediate uses. For each immediate use, it rebuilds the condition
67 expression (the predicate) that guards the use. The predicate is then
68 examined to see if the variable is always defined under that same condition.
69 This is done either by pruning the unrealizable paths that lead to the
70 default definitions or by checking if the predicate set that guards the
71 defining paths is a superset of the use predicate. */
74 /* Pointer set of potentially undefined ssa names, i.e.,
75 ssa names that are defined by phi with operands that
76 are not defined or potentially undefined. */
77 static hash_set
<tree
> *possibly_undefined_names
= 0;
79 /* Bit mask handling macros. */
80 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
81 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
82 #define MASK_EMPTY(mask) (mask == 0)
84 /* Returns the first bit position (starting from LSB)
85 in mask that is non zero. Returns -1 if the mask is empty. */
87 get_mask_first_set_bit (unsigned mask
)
93 while ((mask
& (1 << pos
)) == 0)
98 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
100 /* Return true if T, an SSA_NAME, has an undefined value. */
102 has_undefined_value_p (tree t
)
104 return (ssa_undefined_value_p (t
)
105 || (possibly_undefined_names
106 && possibly_undefined_names
->contains (t
)));
111 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
112 is set on SSA_NAME_VAR. */
115 uninit_undefined_value_p (tree t
) {
116 if (!has_undefined_value_p (t
))
118 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
123 /* Emit warnings for uninitialized variables. This is done in two passes.
125 The first pass notices real uses of SSA names with undefined values.
126 Such uses are unconditionally uninitialized, and we can be certain that
127 such a use is a mistake. This pass is run before most optimizations,
128 so that we catch as many as we can.
130 The second pass follows PHI nodes to find uses that are potentially
131 uninitialized. In this case we can't necessarily prove that the use
132 is really uninitialized. This pass is run after most optimizations,
133 so that we thread as many jumps and possible, and delete as much dead
134 code as possible, in order to reduce false positives. We also look
135 again for plain uninitialized variables, since optimization may have
136 changed conditionally uninitialized to unconditionally uninitialized. */
138 /* Emit a warning for EXPR based on variable VAR at the point in the
139 program T, an SSA_NAME, is used being uninitialized. The exact
140 warning text is in MSGID and DATA is the gimple stmt with info about
141 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
142 gives which argument of the phi node to take the location from. WC
143 is the warning code. */
146 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
147 const char *gmsgid
, void *data
, location_t phiarg_loc
)
149 gimple context
= (gimple
) data
;
150 location_t location
, cfun_loc
;
151 expanded_location xloc
, floc
;
153 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
154 turns in a COMPLEX_EXPR with the not initialized part being
155 set to its previous (undefined) value. */
156 if (is_gimple_assign (context
)
157 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
159 if (!has_undefined_value_p (t
))
162 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
163 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
164 created for conversion from scalar to complex. Use the underlying var of
165 the COMPLEX_EXPRs real part in that case. See PR71581. */
166 if (expr
== NULL_TREE
168 && SSA_NAME_VAR (t
) == NULL_TREE
169 && is_gimple_assign (SSA_NAME_DEF_STMT (t
))
170 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t
)) == COMPLEX_EXPR
)
172 tree v
= gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t
));
173 if (TREE_CODE (v
) == SSA_NAME
174 && has_undefined_value_p (v
)
175 && (integer_zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t
)))
176 || real_zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t
)))
177 || fixed_zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t
)))))
179 expr
= SSA_NAME_VAR (v
);
184 if (expr
== NULL_TREE
)
187 /* TREE_NO_WARNING either means we already warned, or the front end
188 wishes to suppress the warning. */
190 && (gimple_no_warning_p (context
)
191 || (gimple_assign_single_p (context
)
192 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
193 || TREE_NO_WARNING (expr
))
196 if (context
!= NULL
&& gimple_has_location (context
))
197 location
= gimple_location (context
);
198 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
199 location
= phiarg_loc
;
201 location
= DECL_SOURCE_LOCATION (var
);
202 location
= linemap_resolve_location (line_table
, location
,
203 LRK_SPELLING_LOCATION
,
205 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
206 xloc
= expand_location (location
);
207 floc
= expand_location (cfun_loc
);
208 if (warning_at (location
, wc
, gmsgid
, expr
))
210 TREE_NO_WARNING (expr
) = 1;
212 if (location
== DECL_SOURCE_LOCATION (var
))
214 if (xloc
.file
!= floc
.file
215 || linemap_location_before_p (line_table
,
217 || linemap_location_before_p (line_table
,
218 cfun
->function_end_locus
,
220 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
225 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
227 gimple_stmt_iterator gsi
;
230 FOR_EACH_BB_FN (bb
, cfun
)
232 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
233 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
234 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
236 gimple stmt
= gsi_stmt (gsi
);
241 if (is_gimple_debug (stmt
))
244 /* We only do data flow with SSA_NAMEs, so that's all we
246 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
248 use
= USE_FROM_PTR (use_p
);
250 warn_uninit (OPT_Wuninitialized
, use
,
251 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
252 "%qD is used uninitialized in this function",
253 stmt
, UNKNOWN_LOCATION
);
254 else if (warn_possibly_uninitialized
)
255 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
256 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
257 "%qD may be used uninitialized in this function",
258 stmt
, UNKNOWN_LOCATION
);
261 /* For memory the only cheap thing we can do is see if we
262 have a use of the default def of the virtual operand.
263 ??? Not so cheap would be to use the alias oracle via
264 walk_aliased_vdefs, if we don't find any aliasing vdef
265 warn as is-used-uninitialized, if we don't find an aliasing
266 vdef that kills our use (stmt_kills_ref_p), warn as
267 may-be-used-uninitialized. But this walk is quadratic and
268 so must be limited which means we would miss warning
270 use
= gimple_vuse (stmt
);
272 && gimple_assign_single_p (stmt
)
273 && !gimple_vdef (stmt
)
274 && SSA_NAME_IS_DEFAULT_DEF (use
))
276 tree rhs
= gimple_assign_rhs1 (stmt
);
277 tree base
= get_base_address (rhs
);
279 /* Do not warn if it can be initialized outside this function. */
280 if (TREE_CODE (base
) != VAR_DECL
281 || DECL_HARD_REGISTER (base
)
282 || is_global_var (base
))
286 warn_uninit (OPT_Wuninitialized
, use
,
287 gimple_assign_rhs1 (stmt
), base
,
288 "%qE is used uninitialized in this function",
289 stmt
, UNKNOWN_LOCATION
);
290 else if (warn_possibly_uninitialized
)
291 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
292 gimple_assign_rhs1 (stmt
), base
,
293 "%qE may be used uninitialized in this function",
294 stmt
, UNKNOWN_LOCATION
);
302 /* Checks if the operand OPND of PHI is defined by
303 another phi with one operand defined by this PHI,
304 but the rest operands are all defined. If yes,
305 returns true to skip this this operand as being
306 redundant. Can be enhanced to be more general. */
309 can_skip_redundant_opnd (tree opnd
, gimple phi
)
315 phi_def
= gimple_phi_result (phi
);
316 op_def
= SSA_NAME_DEF_STMT (opnd
);
317 if (gimple_code (op_def
) != GIMPLE_PHI
)
319 n
= gimple_phi_num_args (op_def
);
320 for (i
= 0; i
< n
; ++i
)
322 tree op
= gimple_phi_arg_def (op_def
, i
);
323 if (TREE_CODE (op
) != SSA_NAME
)
325 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
332 /* Returns a bit mask holding the positions of arguments in PHI
333 that have empty (or possibly empty) definitions. */
336 compute_uninit_opnds_pos (gphi
*phi
)
339 unsigned uninit_opnds
= 0;
341 n
= gimple_phi_num_args (phi
);
342 /* Bail out for phi with too many args. */
346 for (i
= 0; i
< n
; ++i
)
348 tree op
= gimple_phi_arg_def (phi
, i
);
349 if (TREE_CODE (op
) == SSA_NAME
350 && uninit_undefined_value_p (op
)
351 && !can_skip_redundant_opnd (op
, phi
))
353 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
355 /* Ignore SSA_NAMEs that appear on abnormal edges
357 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
360 MASK_SET_BIT (uninit_opnds
, i
);
366 /* Find the immediate postdominator PDOM of the specified
367 basic block BLOCK. */
369 static inline basic_block
370 find_pdom (basic_block block
)
372 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
373 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
377 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
379 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
384 /* Find the immediate DOM of the specified
385 basic block BLOCK. */
387 static inline basic_block
388 find_dom (basic_block block
)
390 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
391 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
394 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
396 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
401 /* Returns true if BB1 is postdominating BB2 and BB1 is
402 not a loop exit bb. The loop exit bb check is simple and does
403 not cover all cases. */
406 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
408 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
411 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
417 /* Find the closest postdominator of a specified BB, which is control
420 static inline basic_block
421 find_control_equiv_block (basic_block bb
)
425 pdom
= find_pdom (bb
);
427 /* Skip the postdominating bb that is also loop exit. */
428 if (!is_non_loop_exit_postdominating (pdom
, bb
))
431 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
437 #define MAX_NUM_CHAINS 8
438 #define MAX_CHAIN_LEN 5
439 #define MAX_POSTDOM_CHECK 8
440 #define MAX_SWITCH_CASES 40
442 /* Computes the control dependence chains (paths of edges)
443 for DEP_BB up to the dominating basic block BB (the head node of a
444 chain should be dominated by it). CD_CHAINS is pointer to an
445 array holding the result chains. CUR_CD_CHAIN is the current
446 chain being computed. *NUM_CHAINS is total number of chains. The
447 function returns true if the information is successfully computed,
448 return false if there is no control dependence or not computed. */
451 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
452 vec
<edge
> *cd_chains
,
454 vec
<edge
> *cur_cd_chain
,
460 bool found_cd_chain
= false;
461 size_t cur_chain_len
= 0;
463 if (EDGE_COUNT (bb
->succs
) < 2)
466 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
470 /* Could use a set instead. */
471 cur_chain_len
= cur_cd_chain
->length ();
472 if (cur_chain_len
> MAX_CHAIN_LEN
)
475 for (i
= 0; i
< cur_chain_len
; i
++)
477 edge e
= (*cur_cd_chain
)[i
];
478 /* Cycle detected. */
483 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
486 int post_dom_check
= 0;
487 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
491 cur_cd_chain
->safe_push (e
);
492 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
496 /* Found a direct control dependence. */
497 if (*num_chains
< MAX_NUM_CHAINS
)
499 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
502 found_cd_chain
= true;
503 /* Check path from next edge. */
507 /* Now check if DEP_BB is indirectly control dependent on BB. */
508 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
509 num_chains
, cur_cd_chain
, num_calls
))
511 found_cd_chain
= true;
515 cd_bb
= find_pdom (cd_bb
);
517 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
521 cur_cd_chain
->pop ();
522 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
524 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
526 return found_cd_chain
;
529 /* The type to represent a simple predicate */
531 typedef struct use_def_pred_info
535 enum tree_code cond_code
;
539 /* The type to represent a sequence of predicates grouped
540 with .AND. operation. */
542 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
544 /* The type to represent a sequence of pred_chains grouped
545 with .OR. operation. */
547 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
549 /* Converts the chains of control dependence edges into a set of
550 predicates. A control dependence chain is represented by a vector
551 edges. DEP_CHAINS points to an array of dependence chains.
552 NUM_CHAINS is the size of the chain array. One edge in a dependence
553 chain is mapped to predicate expression represented by pred_info
554 type. One dependence chain is converted to a composite predicate that
555 is the result of AND operation of pred_info mapped to each edge.
556 A composite predicate is presented by a vector of pred_info. On
557 return, *PREDS points to the resulting array of composite predicates.
558 *NUM_PREDS is the number of composite predictes. */
561 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
563 pred_chain_union
*preds
)
565 bool has_valid_pred
= false;
567 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
570 /* Now convert the control dep chain into a set
572 preds
->reserve (num_chains
);
574 for (i
= 0; i
< num_chains
; i
++)
576 vec
<edge
> one_cd_chain
= dep_chains
[i
];
578 has_valid_pred
= false;
579 pred_chain t_chain
= vNULL
;
580 for (j
= 0; j
< one_cd_chain
.length (); j
++)
583 gimple_stmt_iterator gsi
;
584 basic_block guard_bb
;
590 gsi
= gsi_last_bb (guard_bb
);
593 has_valid_pred
= false;
596 cond_stmt
= gsi_stmt (gsi
);
597 if (is_gimple_call (cond_stmt
)
598 && EDGE_COUNT (e
->src
->succs
) >= 2)
600 /* Ignore EH edge. Can add assertion
601 on the other edge's flag. */
604 /* Skip if there is essentially one succesor. */
605 if (EDGE_COUNT (e
->src
->succs
) == 2)
611 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
613 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
622 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
624 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
625 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
626 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
627 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
628 t_chain
.safe_push (one_pred
);
629 has_valid_pred
= true;
631 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
633 /* Avoid quadratic behavior. */
634 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
636 has_valid_pred
= false;
639 /* Find the case label. */
642 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
644 tree tl
= gimple_switch_label (gs
, idx
);
645 if (e
->dest
== label_to_block (CASE_LABEL (tl
)))
656 /* If more than one label reaches this block or the case
657 label doesn't have a single value (like the default one)
661 || (CASE_HIGH (l
) && !operand_equal_p (CASE_LOW (l
),
664 has_valid_pred
= false;
667 one_pred
.pred_lhs
= gimple_switch_index (gs
);
668 one_pred
.pred_rhs
= CASE_LOW (l
);
669 one_pred
.cond_code
= EQ_EXPR
;
670 one_pred
.invert
= false;
671 t_chain
.safe_push (one_pred
);
672 has_valid_pred
= true;
676 has_valid_pred
= false;
684 preds
->safe_push (t_chain
);
686 return has_valid_pred
;
689 /* Computes all control dependence chains for USE_BB. The control
690 dependence chains are then converted to an array of composite
691 predicates pointed to by PREDS. PHI_BB is the basic block of
692 the phi whose result is used in USE_BB. */
695 find_predicates (pred_chain_union
*preds
,
699 size_t num_chains
= 0, i
;
701 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
702 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
703 bool has_valid_pred
= false;
704 basic_block cd_root
= 0;
706 /* First find the closest bb that is control equivalent to PHI_BB
707 that also dominates USE_BB. */
709 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
711 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
712 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
713 cd_root
= ctrl_eq_bb
;
718 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
719 &cur_chain
, &num_calls
);
722 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
723 for (i
= 0; i
< num_chains
; i
++)
724 dep_chains
[i
].release ();
725 return has_valid_pred
;
728 /* Computes the set of incoming edges of PHI that have non empty
729 definitions of a phi chain. The collection will be done
730 recursively on operands that are defined by phis. CD_ROOT
731 is the control dependence root. *EDGES holds the result, and
732 VISITED_PHIS is a pointer set for detecting cycles. */
735 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
737 hash_set
<gimple
> *visited_phis
)
743 if (visited_phis
->add (phi
))
746 n
= gimple_phi_num_args (phi
);
747 for (i
= 0; i
< n
; i
++)
749 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
750 opnd
= gimple_phi_arg_def (phi
, i
);
752 if (TREE_CODE (opnd
) != SSA_NAME
)
754 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
756 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
757 print_gimple_stmt (dump_file
, phi
, 0, 0);
759 edges
->safe_push (opnd_edge
);
763 gimple def
= SSA_NAME_DEF_STMT (opnd
);
765 if (gimple_code (def
) == GIMPLE_PHI
766 && dominated_by_p (CDI_DOMINATORS
,
767 gimple_bb (def
), cd_root
))
768 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
770 else if (!uninit_undefined_value_p (opnd
))
772 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
774 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
775 print_gimple_stmt (dump_file
, phi
, 0, 0);
777 edges
->safe_push (opnd_edge
);
783 /* For each use edge of PHI, computes all control dependence chains.
784 The control dependence chains are then converted to an array of
785 composite predicates pointed to by PREDS. */
788 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
790 size_t num_chains
= 0, i
, n
;
791 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
792 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
793 vec
<edge
> def_edges
= vNULL
;
794 bool has_valid_pred
= false;
795 basic_block phi_bb
, cd_root
= 0;
797 phi_bb
= gimple_bb (phi
);
798 /* First find the closest dominating bb to be
799 the control dependence root */
800 cd_root
= find_dom (phi_bb
);
804 hash_set
<gimple
> visited_phis
;
805 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
807 n
= def_edges
.length ();
811 for (i
= 0; i
< n
; i
++)
817 opnd_edge
= def_edges
[i
];
818 prev_nc
= num_chains
;
819 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
820 &num_chains
, &cur_chain
, &num_calls
);
822 /* Now update the newly added chains with
823 the phi operand edge: */
824 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
826 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
827 dep_chains
[num_chains
++] = vNULL
;
828 for (j
= prev_nc
; j
< num_chains
; j
++)
829 dep_chains
[j
].safe_push (opnd_edge
);
834 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
835 for (i
= 0; i
< num_chains
; i
++)
836 dep_chains
[i
].release ();
837 return has_valid_pred
;
840 /* Dumps the predicates (PREDS) for USESTMT. */
843 dump_predicates (gimple usestmt
, pred_chain_union preds
,
847 pred_chain one_pred_chain
= vNULL
;
848 fprintf (dump_file
, "%s", msg
);
849 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
850 fprintf (dump_file
, "is guarded by :\n\n");
851 size_t num_preds
= preds
.length ();
852 /* Do some dumping here: */
853 for (i
= 0; i
< num_preds
; i
++)
857 one_pred_chain
= preds
[i
];
858 np
= one_pred_chain
.length ();
860 for (j
= 0; j
< np
; j
++)
862 pred_info one_pred
= one_pred_chain
[j
];
864 fprintf (dump_file
, " (.NOT.) ");
865 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
866 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
867 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
869 fprintf (dump_file
, " (.AND.) ");
871 fprintf (dump_file
, "\n");
873 if (i
< num_preds
- 1)
874 fprintf (dump_file
, "(.OR.)\n");
876 fprintf (dump_file
, "\n\n");
880 /* Destroys the predicate set *PREDS. */
883 destroy_predicate_vecs (pred_chain_union preds
)
887 size_t n
= preds
.length ();
888 for (i
= 0; i
< n
; i
++)
894 /* Computes the 'normalized' conditional code with operand
895 swapping and condition inversion. */
897 static enum tree_code
898 get_cmp_code (enum tree_code orig_cmp_code
,
899 bool swap_cond
, bool invert
)
901 enum tree_code tc
= orig_cmp_code
;
904 tc
= swap_tree_comparison (orig_cmp_code
);
906 tc
= invert_tree_comparison (tc
, false);
923 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
924 all values in the range satisfies (x CMPC BOUNDARY) == true. */
927 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
929 bool inverted
= false;
933 /* Only handle integer constant here. */
934 if (TREE_CODE (val
) != INTEGER_CST
935 || TREE_CODE (boundary
) != INTEGER_CST
)
938 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
940 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
943 cmpc
= invert_tree_comparison (cmpc
, false);
950 result
= tree_int_cst_equal (val
, boundary
);
951 else if (cmpc
== LT_EXPR
)
952 result
= tree_int_cst_lt (val
, boundary
);
955 gcc_assert (cmpc
== LE_EXPR
);
956 result
= tree_int_cst_le (val
, boundary
);
962 result
= tree_int_cst_equal (val
, boundary
);
963 else if (cmpc
== LT_EXPR
)
964 result
= tree_int_cst_lt (val
, boundary
);
967 gcc_assert (cmpc
== LE_EXPR
);
968 result
= (tree_int_cst_equal (val
, boundary
)
969 || tree_int_cst_lt (val
, boundary
));
979 /* Returns true if PRED is common among all the predicate
980 chains (PREDS) (and therefore can be factored out).
981 NUM_PRED_CHAIN is the size of array PREDS. */
984 find_matching_predicate_in_rest_chains (pred_info pred
,
985 pred_chain_union preds
,
986 size_t num_pred_chains
)
991 if (num_pred_chains
== 1)
994 for (i
= 1; i
< num_pred_chains
; i
++)
997 pred_chain one_chain
= preds
[i
];
998 n
= one_chain
.length ();
999 for (j
= 0; j
< n
; j
++)
1001 pred_info pred2
= one_chain
[j
];
1002 /* Can relax the condition comparison to not
1003 use address comparison. However, the most common
1004 case is that multiple control dependent paths share
1005 a common path prefix, so address comparison should
1008 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
1009 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
1010 && pred2
.invert
== pred
.invert
)
1022 /* Forward declaration. */
1024 is_use_properly_guarded (gimple use_stmt
,
1027 unsigned uninit_opnds
,
1028 hash_set
<gphi
*> *visited_phis
);
1030 /* Returns true if all uninitialized opnds are pruned. Returns false
1031 otherwise. PHI is the phi node with uninitialized operands,
1032 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1033 FLAG_DEF is the statement defining the flag guarding the use of the
1034 PHI output, BOUNDARY_CST is the const value used in the predicate
1035 associated with the flag, CMP_CODE is the comparison code used in
1036 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1037 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1043 flag_1 = phi <0, 1> // (1)
1044 var_1 = phi <undef, some_val>
1048 flag_2 = phi <0, flag_1, flag_1> // (2)
1049 var_2 = phi <undef, var_1, var_1>
1056 Because some flag arg in (1) is not constant, if we do not look into the
1057 flag phis recursively, it is conservatively treated as unknown and var_1
1058 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
1059 a false warning will be emitted. Checking recursively into (1), the compiler can
1060 find out that only some_val (which is defined) can flow into (3) which is OK.
1065 prune_uninit_phi_opnds_in_unrealizable_paths (gphi
*phi
,
1066 unsigned uninit_opnds
,
1069 enum tree_code cmp_code
,
1070 hash_set
<gphi
*> *visited_phis
,
1071 bitmap
*visited_flag_phis
)
1075 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
1079 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1082 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1083 if (!is_gimple_constant (flag_arg
))
1085 gphi
*flag_arg_def
, *phi_arg_def
;
1087 unsigned uninit_opnds_arg_phi
;
1089 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1091 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1095 phi_arg
= gimple_phi_arg_def (phi
, i
);
1096 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1099 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1103 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1106 if (!*visited_flag_phis
)
1107 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1109 if (bitmap_bit_p (*visited_flag_phis
,
1110 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1113 bitmap_set_bit (*visited_flag_phis
,
1114 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1116 /* Now recursively prune the uninitialized phi args. */
1117 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1118 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1119 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1120 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1123 bitmap_clear_bit (*visited_flag_phis
,
1124 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1128 /* Now check if the constant is in the guarded range. */
1129 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1134 /* Now that we know that this undefined edge is not
1135 pruned. If the operand is defined by another phi,
1136 we can further prune the incoming edges of that
1137 phi by checking the predicates of this operands. */
1139 opnd
= gimple_phi_arg_def (phi
, i
);
1140 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1141 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1144 unsigned uninit_opnds2
1145 = compute_uninit_opnds_pos (opnd_def_phi
);
1146 if (!MASK_EMPTY (uninit_opnds2
))
1148 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1149 if (!is_use_properly_guarded (phi
,
1165 /* A helper function that determines if the predicate set
1166 of the use is not overlapping with that of the uninit paths.
1167 The most common senario of guarded use is in Example 1:
1180 The real world examples are usually more complicated, but similar
1181 and usually result from inlining:
1183 bool init_func (int * x)
1202 Another possible use scenario is in the following trivial example:
1214 Predicate analysis needs to compute the composite predicate:
1216 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1217 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1218 (the predicate chain for phi operand defs can be computed
1219 starting from a bb that is control equivalent to the phi's
1220 bb and is dominating the operand def.)
1222 and check overlapping:
1223 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1226 This implementation provides framework that can handle
1227 scenarios. (Note that many simple cases are handled properly
1228 without the predicate analysis -- this is due to jump threading
1229 transformation which eliminates the merge point thus makes
1230 path sensitive analysis unnecessary.)
1232 NUM_PREDS is the number is the number predicate chains, PREDS is
1233 the array of chains, PHI is the phi node whose incoming (undefined)
1234 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1235 uninit operand positions. VISITED_PHIS is the pointer set of phi
1236 stmts being checked. */
1240 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1241 gphi
*phi
, unsigned uninit_opnds
,
1242 hash_set
<gphi
*> *visited_phis
)
1245 gimple flag_def
= 0;
1246 tree boundary_cst
= 0;
1247 enum tree_code cmp_code
;
1248 bool swap_cond
= false;
1249 bool invert
= false;
1250 pred_chain the_pred_chain
= vNULL
;
1251 bitmap visited_flag_phis
= NULL
;
1252 bool all_pruned
= false;
1253 size_t num_preds
= preds
.length ();
1255 gcc_assert (num_preds
> 0);
1256 /* Find within the common prefix of multiple predicate chains
1257 a predicate that is a comparison of a flag variable against
1259 the_pred_chain
= preds
[0];
1260 n
= the_pred_chain
.length ();
1261 for (i
= 0; i
< n
; i
++)
1263 tree cond_lhs
, cond_rhs
, flag
= 0;
1265 pred_info the_pred
= the_pred_chain
[i
];
1267 invert
= the_pred
.invert
;
1268 cond_lhs
= the_pred
.pred_lhs
;
1269 cond_rhs
= the_pred
.pred_rhs
;
1270 cmp_code
= the_pred
.cond_code
;
1272 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1273 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1275 boundary_cst
= cond_rhs
;
1278 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1279 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1281 boundary_cst
= cond_lhs
;
1289 flag_def
= SSA_NAME_DEF_STMT (flag
);
1294 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1295 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1296 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1306 /* Now check all the uninit incoming edge has a constant flag value
1307 that is in conflict with the use guard/predicate. */
1308 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1310 if (cmp_code
== ERROR_MARK
)
1313 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1315 as_a
<gphi
*> (flag_def
),
1319 &visited_flag_phis
);
1321 if (visited_flag_phis
)
1322 BITMAP_FREE (visited_flag_phis
);
1327 /* The helper function returns true if two predicates X1 and X2
1328 are equivalent. It assumes the expressions have already
1329 properly re-associated. */
1332 pred_equal_p (pred_info x1
, pred_info x2
)
1334 enum tree_code c1
, c2
;
1335 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1336 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1340 if (x1
.invert
!= x2
.invert
1341 && TREE_CODE_CLASS (x2
.cond_code
) == tcc_comparison
)
1342 c2
= invert_tree_comparison (x2
.cond_code
, false);
1349 /* Returns true if the predication is testing !=. */
1352 is_neq_relop_p (pred_info pred
)
1355 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1356 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1359 /* Returns true if pred is of the form X != 0. */
1362 is_neq_zero_form_p (pred_info pred
)
1364 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1365 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1370 /* The helper function returns true if two predicates X1
1371 is equivalent to X2 != 0. */
1374 pred_expr_equal_p (pred_info x1
, tree x2
)
1376 if (!is_neq_zero_form_p (x1
))
1379 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1382 /* Returns true of the domain of single predicate expression
1383 EXPR1 is a subset of that of EXPR2. Returns false if it
1384 can not be proved. */
1387 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1389 enum tree_code code1
, code2
;
1391 if (pred_equal_p (expr1
, expr2
))
1394 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1395 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1398 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1401 code1
= expr1
.cond_code
;
1403 code1
= invert_tree_comparison (code1
, false);
1404 code2
= expr2
.cond_code
;
1406 code2
= invert_tree_comparison (code2
, false);
1408 if ((code1
== EQ_EXPR
|| code1
== BIT_AND_EXPR
)
1409 && code2
== BIT_AND_EXPR
)
1410 return wi::eq_p (expr1
.pred_rhs
,
1411 wi::bit_and (expr1
.pred_rhs
, expr2
.pred_rhs
));
1413 if (code1
!= code2
&& code2
!= NE_EXPR
)
1416 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1422 /* Returns true if the domain of PRED1 is a subset
1423 of that of PRED2. Returns false if it can not be proved so. */
1426 is_pred_chain_subset_of (pred_chain pred1
,
1429 size_t np1
, np2
, i1
, i2
;
1431 np1
= pred1
.length ();
1432 np2
= pred2
.length ();
1434 for (i2
= 0; i2
< np2
; i2
++)
1437 pred_info info2
= pred2
[i2
];
1438 for (i1
= 0; i1
< np1
; i1
++)
1440 pred_info info1
= pred1
[i1
];
1441 if (is_pred_expr_subset_of (info1
, info2
))
1453 /* Returns true if the domain defined by
1454 one pred chain ONE_PRED is a subset of the domain
1455 of *PREDS. It returns false if ONE_PRED's domain is
1456 not a subset of any of the sub-domains of PREDS
1457 (corresponding to each individual chains in it), even
1458 though it may be still be a subset of whole domain
1459 of PREDS which is the union (ORed) of all its subdomains.
1460 In other words, the result is conservative. */
1463 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1466 size_t n
= preds
.length ();
1468 for (i
= 0; i
< n
; i
++)
1470 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1477 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1478 true if the domain defined by PREDS1 is a superset
1479 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1480 PREDS2 respectively. The implementation chooses not to build
1481 generic trees (and relying on the folding capability of the
1482 compiler), but instead performs brute force comparison of
1483 individual predicate chains (won't be a compile time problem
1484 as the chains are pretty short). When the function returns
1485 false, it does not necessarily mean *PREDS1 is not a superset
1486 of *PREDS2, but mean it may not be so since the analysis can
1487 not prove it. In such cases, false warnings may still be
1491 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1494 pred_chain one_pred_chain
= vNULL
;
1496 n2
= preds2
.length ();
1498 for (i
= 0; i
< n2
; i
++)
1500 one_pred_chain
= preds2
[i
];
1501 if (!is_included_in (one_pred_chain
, preds1
))
1508 /* Returns true if TC is AND or OR. */
1511 is_and_or_or_p (enum tree_code tc
, tree type
)
1513 return (tc
== BIT_IOR_EXPR
1514 || (tc
== BIT_AND_EXPR
1515 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1518 /* Returns true if X1 is the negate of X2. */
1521 pred_neg_p (pred_info x1
, pred_info x2
)
1523 enum tree_code c1
, c2
;
1524 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1525 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1529 if (x1
.invert
== x2
.invert
)
1530 c2
= invert_tree_comparison (x2
.cond_code
, false);
1537 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1538 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1539 3) X OR (!X AND Y) is equivalent to (X OR Y);
1540 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1542 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1545 PREDS is the predicate chains, and N is the number of chains. */
1547 /* Helper function to implement rule 1 above. ONE_CHAIN is
1548 the AND predication to be simplified. */
1551 simplify_pred (pred_chain
*one_chain
)
1554 bool simplified
= false;
1555 pred_chain s_chain
= vNULL
;
1557 n
= one_chain
->length ();
1559 for (i
= 0; i
< n
; i
++)
1561 pred_info
*a_pred
= &(*one_chain
)[i
];
1563 if (!a_pred
->pred_lhs
)
1565 if (!is_neq_zero_form_p (*a_pred
))
1568 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1569 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1571 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1573 for (j
= 0; j
< n
; j
++)
1575 pred_info
*b_pred
= &(*one_chain
)[j
];
1577 if (!b_pred
->pred_lhs
)
1579 if (!is_neq_zero_form_p (*b_pred
))
1582 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1583 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1585 /* Mark a_pred for removal. */
1586 a_pred
->pred_lhs
= NULL
;
1587 a_pred
->pred_rhs
= NULL
;
1598 for (i
= 0; i
< n
; i
++)
1600 pred_info
*a_pred
= &(*one_chain
)[i
];
1601 if (!a_pred
->pred_lhs
)
1603 s_chain
.safe_push (*a_pred
);
1606 one_chain
->release ();
1607 *one_chain
= s_chain
;
1610 /* The helper function implements the rule 2 for the
1613 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1616 simplify_preds_2 (pred_chain_union
*preds
)
1619 bool simplified
= false;
1620 pred_chain_union s_preds
= vNULL
;
1622 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1623 (X AND Y) OR (X AND !Y) is equivalent to X. */
1625 n
= preds
->length ();
1626 for (i
= 0; i
< n
; i
++)
1629 pred_chain
*a_chain
= &(*preds
)[i
];
1631 if (a_chain
->length () != 2)
1637 for (j
= 0; j
< n
; j
++)
1639 pred_chain
*b_chain
;
1645 b_chain
= &(*preds
)[j
];
1646 if (b_chain
->length () != 2)
1652 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1655 a_chain
->release ();
1656 b_chain
->release ();
1657 b_chain
->safe_push (x
);
1661 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1664 a_chain
->release ();
1665 b_chain
->release ();
1666 b_chain
->safe_push (y
);
1672 /* Now clean up the chain. */
1675 for (i
= 0; i
< n
; i
++)
1677 if ((*preds
)[i
].is_empty ())
1679 s_preds
.safe_push ((*preds
)[i
]);
1689 /* The helper function implements the rule 2 for the
1692 3) x OR (!x AND y) is equivalent to x OR y. */
1695 simplify_preds_3 (pred_chain_union
*preds
)
1698 bool simplified
= false;
1700 /* Now iteratively simplify X OR (!X AND Z ..)
1701 into X OR (Z ...). */
1703 n
= preds
->length ();
1707 for (i
= 0; i
< n
; i
++)
1710 pred_chain
*a_chain
= &(*preds
)[i
];
1712 if (a_chain
->length () != 1)
1717 for (j
= 0; j
< n
; j
++)
1719 pred_chain
*b_chain
;
1726 b_chain
= &(*preds
)[j
];
1727 if (b_chain
->length () < 2)
1730 for (k
= 0; k
< b_chain
->length (); k
++)
1733 if (pred_neg_p (x
, x2
))
1735 b_chain
->unordered_remove (k
);
1745 /* The helper function implements the rule 4 for the
1748 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1749 (x != 0 ANd y != 0). */
1752 simplify_preds_4 (pred_chain_union
*preds
)
1755 bool simplified
= false;
1756 pred_chain_union s_preds
= vNULL
;
1759 n
= preds
->length ();
1760 for (i
= 0; i
< n
; i
++)
1763 pred_chain
*a_chain
= &(*preds
)[i
];
1765 if (a_chain
->length () != 1)
1770 if (!is_neq_zero_form_p (z
))
1773 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1774 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1777 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1780 for (j
= 0; j
< n
; j
++)
1782 pred_chain
*b_chain
;
1788 b_chain
= &(*preds
)[j
];
1789 if (b_chain
->length () != 2)
1794 if (!is_neq_zero_form_p (x2
)
1795 || !is_neq_zero_form_p (y2
))
1798 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1799 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1800 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1801 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1804 a_chain
->release ();
1810 /* Now clean up the chain. */
1813 for (i
= 0; i
< n
; i
++)
1815 if ((*preds
)[i
].is_empty ())
1817 s_preds
.safe_push ((*preds
)[i
]);
1828 /* This function simplifies predicates in PREDS. */
1831 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1834 bool changed
= false;
1836 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1838 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1839 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1842 for (i
= 0; i
< preds
->length (); i
++)
1843 simplify_pred (&(*preds
)[i
]);
1845 n
= preds
->length ();
1852 if (simplify_preds_2 (preds
))
1855 /* Now iteratively simplify X OR (!X AND Z ..)
1856 into X OR (Z ...). */
1857 if (simplify_preds_3 (preds
))
1860 if (simplify_preds_4 (preds
))
1868 /* This is a helper function which attempts to normalize predicate chains
1869 by following UD chains. It basically builds up a big tree of either IOR
1870 operations or AND operations, and convert the IOR tree into a
1871 pred_chain_union or BIT_AND tree into a pred_chain.
1881 then _t != 0 will be normalized into a pred_chain_union
1883 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1893 then _t != 0 will be normalized into a pred_chain:
1894 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1898 /* This is a helper function that stores a PRED into NORM_PREDS. */
1901 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1903 pred_chain pred_chain
= vNULL
;
1904 pred_chain
.safe_push (pred
);
1905 norm_preds
->safe_push (pred_chain
);
1908 /* A helper function that creates a predicate of the form
1909 OP != 0 and push it WORK_LIST. */
1912 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1913 hash_set
<tree
> *mark_set
)
1915 if (mark_set
->contains (op
))
1920 arg_pred
.pred_lhs
= op
;
1921 arg_pred
.pred_rhs
= integer_zero_node
;
1922 arg_pred
.cond_code
= NE_EXPR
;
1923 arg_pred
.invert
= false;
1924 work_list
->safe_push (arg_pred
);
1927 /* A helper that generates a pred_info from a gimple assignment
1928 CMP_ASSIGN with comparison rhs. */
1931 get_pred_info_from_cmp (gimple cmp_assign
)
1934 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1935 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1936 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1937 n_pred
.invert
= false;
1941 /* Returns true if the PHI is a degenerated phi with
1942 all args with the same value (relop). In that case, *PRED
1943 will be updated to that value. */
1946 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1953 n
= gimple_phi_num_args (phi
);
1954 op0
= gimple_phi_arg_def (phi
, 0);
1956 if (TREE_CODE (op0
) != SSA_NAME
)
1959 def0
= SSA_NAME_DEF_STMT (op0
);
1960 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1962 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1965 pred0
= get_pred_info_from_cmp (def0
);
1967 for (i
= 1; i
< n
; ++i
)
1971 tree op
= gimple_phi_arg_def (phi
, i
);
1973 if (TREE_CODE (op
) != SSA_NAME
)
1976 def
= SSA_NAME_DEF_STMT (op
);
1977 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1979 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1982 pred
= get_pred_info_from_cmp (def
);
1983 if (!pred_equal_p (pred
, pred0
))
1991 /* Normalize one predicate PRED
1992 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1993 2) otherwise if PRED is of the form x != 0, follow x's definition
1994 and put normalized predicates into WORK_LIST. */
1997 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1998 pred_chain
*norm_chain
,
2000 enum tree_code and_or_code
,
2001 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
2002 hash_set
<tree
> *mark_set
)
2004 if (!is_neq_zero_form_p (pred
))
2006 if (and_or_code
== BIT_IOR_EXPR
)
2007 push_pred (norm_preds
, pred
);
2009 norm_chain
->safe_push (pred
);
2013 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2015 if (gimple_code (def_stmt
) == GIMPLE_PHI
2016 && is_degenerated_phi (def_stmt
, &pred
))
2017 work_list
->safe_push (pred
);
2018 else if (gimple_code (def_stmt
) == GIMPLE_PHI
2019 && and_or_code
== BIT_IOR_EXPR
)
2022 n
= gimple_phi_num_args (def_stmt
);
2024 /* If we see non zero constant, we should punt. The predicate
2025 * should be one guarding the phi edge. */
2026 for (i
= 0; i
< n
; ++i
)
2028 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2029 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
2031 push_pred (norm_preds
, pred
);
2036 for (i
= 0; i
< n
; ++i
)
2038 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2039 if (integer_zerop (op
))
2042 push_to_worklist (op
, work_list
, mark_set
);
2045 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2047 if (and_or_code
== BIT_IOR_EXPR
)
2048 push_pred (norm_preds
, pred
);
2050 norm_chain
->safe_push (pred
);
2052 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2054 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2055 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2057 /* But treat x & 3 as condition. */
2058 if (and_or_code
== BIT_AND_EXPR
)
2061 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2062 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2063 n_pred
.cond_code
= and_or_code
;
2064 n_pred
.invert
= false;
2065 norm_chain
->safe_push (n_pred
);
2070 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2071 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2074 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2077 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2078 if (and_or_code
== BIT_IOR_EXPR
)
2079 push_pred (norm_preds
, n_pred
);
2081 norm_chain
->safe_push (n_pred
);
2085 if (and_or_code
== BIT_IOR_EXPR
)
2086 push_pred (norm_preds
, pred
);
2088 norm_chain
->safe_push (pred
);
2092 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2095 normalize_one_pred (pred_chain_union
*norm_preds
,
2098 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2099 enum tree_code and_or_code
= ERROR_MARK
;
2100 pred_chain norm_chain
= vNULL
;
2102 if (!is_neq_zero_form_p (pred
))
2104 push_pred (norm_preds
, pred
);
2108 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2109 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2110 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2111 if (and_or_code
!= BIT_IOR_EXPR
2112 && and_or_code
!= BIT_AND_EXPR
)
2114 if (TREE_CODE_CLASS (and_or_code
)
2117 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2118 push_pred (norm_preds
, n_pred
);
2121 push_pred (norm_preds
, pred
);
2125 work_list
.safe_push (pred
);
2126 hash_set
<tree
> mark_set
;
2128 while (!work_list
.is_empty ())
2130 pred_info a_pred
= work_list
.pop ();
2131 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2132 and_or_code
, &work_list
, &mark_set
);
2134 if (and_or_code
== BIT_AND_EXPR
)
2135 norm_preds
->safe_push (norm_chain
);
2137 work_list
.release ();
2141 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2142 pred_chain one_chain
)
2144 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2145 hash_set
<tree
> mark_set
;
2146 pred_chain norm_chain
= vNULL
;
2149 for (i
= 0; i
< one_chain
.length (); i
++)
2151 work_list
.safe_push (one_chain
[i
]);
2152 mark_set
.add (one_chain
[i
].pred_lhs
);
2155 while (!work_list
.is_empty ())
2157 pred_info a_pred
= work_list
.pop ();
2158 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2159 BIT_AND_EXPR
, &work_list
, &mark_set
);
2162 norm_preds
->safe_push (norm_chain
);
2163 work_list
.release ();
2166 /* Normalize predicate chains PREDS and returns the normalized one. */
2168 static pred_chain_union
2169 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2171 pred_chain_union norm_preds
= vNULL
;
2172 size_t n
= preds
.length ();
2175 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2177 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2178 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2181 for (i
= 0; i
< n
; i
++)
2183 if (preds
[i
].length () != 1)
2184 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2187 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2188 preds
[i
].release ();
2194 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2195 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2203 /* Computes the predicates that guard the use and checks
2204 if the incoming paths that have empty (or possibly
2205 empty) definition can be pruned/filtered. The function returns
2206 true if it can be determined that the use of PHI's def in
2207 USE_STMT is guarded with a predicate set not overlapping with
2208 predicate sets of all runtime paths that do not have a definition.
2209 Returns false if it is not or it can not be determined. USE_BB is
2210 the bb of the use (for phi operand use, the bb is not the bb of
2211 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2212 is a bit vector. If an operand of PHI is uninitialized, the
2213 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2214 set of phis being visted. */
2217 is_use_properly_guarded (gimple use_stmt
,
2220 unsigned uninit_opnds
,
2221 hash_set
<gphi
*> *visited_phis
)
2224 pred_chain_union preds
= vNULL
;
2225 pred_chain_union def_preds
= vNULL
;
2226 bool has_valid_preds
= false;
2227 bool is_properly_guarded
= false;
2229 if (visited_phis
->add (phi
))
2232 phi_bb
= gimple_bb (phi
);
2234 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2237 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2239 if (!has_valid_preds
)
2241 destroy_predicate_vecs (preds
);
2245 /* Try to prune the dead incoming phi edges. */
2247 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2250 if (is_properly_guarded
)
2252 destroy_predicate_vecs (preds
);
2256 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2258 if (!has_valid_preds
)
2260 destroy_predicate_vecs (preds
);
2261 destroy_predicate_vecs (def_preds
);
2265 simplify_preds (&preds
, use_stmt
, true);
2266 preds
= normalize_preds (preds
, use_stmt
, true);
2268 simplify_preds (&def_preds
, phi
, false);
2269 def_preds
= normalize_preds (def_preds
, phi
, false);
2271 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2273 destroy_predicate_vecs (preds
);
2274 destroy_predicate_vecs (def_preds
);
2275 return is_properly_guarded
;
2278 /* Searches through all uses of a potentially
2279 uninitialized variable defined by PHI and returns a use
2280 statement if the use is not properly guarded. It returns
2281 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2282 holding the position(s) of uninit PHI operands. WORKLIST
2283 is the vector of candidate phis that may be updated by this
2284 function. ADDED_TO_WORKLIST is the pointer set tracking
2285 if the new phi is already in the worklist. */
2288 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2289 vec
<gphi
*> *worklist
,
2290 hash_set
<gphi
*> *added_to_worklist
)
2293 use_operand_p use_p
;
2295 imm_use_iterator iter
;
2297 phi_result
= gimple_phi_result (phi
);
2299 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2303 use_stmt
= USE_STMT (use_p
);
2304 if (is_gimple_debug (use_stmt
))
2307 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2308 use_bb
= gimple_phi_arg_edge (use_phi
,
2309 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2311 use_bb
= gimple_bb (use_stmt
);
2313 hash_set
<gphi
*> visited_phis
;
2314 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2320 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2321 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2323 /* Found one real use, return. */
2324 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2327 /* Found a phi use that is not guarded,
2328 add the phi to the worklist. */
2329 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2331 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2333 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2334 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2337 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2338 possibly_undefined_names
->add (phi_result
);
2345 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2346 and gives warning if there exists a runtime path from the entry to a
2347 use of the PHI def that does not contain a definition. In other words,
2348 the warning is on the real use. The more dead paths that can be pruned
2349 by the compiler, the fewer false positives the warning is. WORKLIST
2350 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2351 a pointer set tracking if the new phi is added to the worklist or not. */
2354 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2355 hash_set
<gphi
*> *added_to_worklist
)
2357 unsigned uninit_opnds
;
2358 gimple uninit_use_stmt
= 0;
2363 /* Don't look at virtual operands. */
2364 if (virtual_operand_p (gimple_phi_result (phi
)))
2367 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2369 if (MASK_EMPTY (uninit_opnds
))
2372 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2374 fprintf (dump_file
, "[CHECK]: examining phi: ");
2375 print_gimple_stmt (dump_file
, phi
, 0, 0);
2378 /* Now check if we have any use of the value without proper guard. */
2379 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2380 worklist
, added_to_worklist
);
2382 /* All uses are properly guarded. */
2383 if (!uninit_use_stmt
)
2386 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2387 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2388 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2390 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2391 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2393 loc
= UNKNOWN_LOCATION
;
2394 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2395 SSA_NAME_VAR (uninit_op
),
2396 "%qD may be used uninitialized in this function",
2397 uninit_use_stmt
, loc
);
2402 gate_warn_uninitialized (void)
2404 return warn_uninitialized
|| warn_maybe_uninitialized
;
2409 const pass_data pass_data_late_warn_uninitialized
=
2411 GIMPLE_PASS
, /* type */
2412 "uninit", /* name */
2413 OPTGROUP_NONE
, /* optinfo_flags */
2414 TV_NONE
, /* tv_id */
2415 PROP_ssa
, /* properties_required */
2416 0, /* properties_provided */
2417 0, /* properties_destroyed */
2418 0, /* todo_flags_start */
2419 0, /* todo_flags_finish */
2422 class pass_late_warn_uninitialized
: public gimple_opt_pass
2425 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2426 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2429 /* opt_pass methods: */
2430 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2431 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2432 virtual unsigned int execute (function
*);
2434 }; // class pass_late_warn_uninitialized
2437 pass_late_warn_uninitialized::execute (function
*fun
)
2441 vec
<gphi
*> worklist
= vNULL
;
2443 calculate_dominance_info (CDI_DOMINATORS
);
2444 calculate_dominance_info (CDI_POST_DOMINATORS
);
2445 /* Re-do the plain uninitialized variable check, as optimization may have
2446 straightened control flow. Do this first so that we don't accidentally
2447 get a "may be" warning when we'd have seen an "is" warning later. */
2448 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2450 timevar_push (TV_TREE_UNINIT
);
2452 possibly_undefined_names
= new hash_set
<tree
>;
2453 hash_set
<gphi
*> added_to_worklist
;
2455 /* Initialize worklist */
2456 FOR_EACH_BB_FN (bb
, fun
)
2457 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2459 gphi
*phi
= gsi
.phi ();
2462 n
= gimple_phi_num_args (phi
);
2464 /* Don't look at virtual operands. */
2465 if (virtual_operand_p (gimple_phi_result (phi
)))
2468 for (i
= 0; i
< n
; ++i
)
2470 tree op
= gimple_phi_arg_def (phi
, i
);
2471 if (TREE_CODE (op
) == SSA_NAME
2472 && uninit_undefined_value_p (op
))
2474 worklist
.safe_push (phi
);
2475 added_to_worklist
.add (phi
);
2476 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2478 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2479 print_gimple_stmt (dump_file
, phi
, 0, 0);
2486 while (worklist
.length () != 0)
2489 cur_phi
= worklist
.pop ();
2490 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2493 worklist
.release ();
2494 delete possibly_undefined_names
;
2495 possibly_undefined_names
= NULL
;
2496 free_dominance_info (CDI_POST_DOMINATORS
);
2497 timevar_pop (TV_TREE_UNINIT
);
2504 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2506 return new pass_late_warn_uninitialized (ctxt
);
2511 execute_early_warn_uninitialized (void)
2513 /* Currently, this pass runs always but
2514 execute_late_warn_uninitialized only runs with optimization. With
2515 optimization we want to warn about possible uninitialized as late
2516 as possible, thus don't do it here. However, without
2517 optimization we need to warn here about "may be uninitialized". */
2518 calculate_dominance_info (CDI_POST_DOMINATORS
);
2520 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2522 /* Post-dominator information can not be reliably updated. Free it
2525 free_dominance_info (CDI_POST_DOMINATORS
);
2532 const pass_data pass_data_early_warn_uninitialized
=
2534 GIMPLE_PASS
, /* type */
2535 "*early_warn_uninitialized", /* name */
2536 OPTGROUP_NONE
, /* optinfo_flags */
2537 TV_TREE_UNINIT
, /* tv_id */
2538 PROP_ssa
, /* properties_required */
2539 0, /* properties_provided */
2540 0, /* properties_destroyed */
2541 0, /* todo_flags_start */
2542 0, /* todo_flags_finish */
2545 class pass_early_warn_uninitialized
: public gimple_opt_pass
2548 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2549 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2552 /* opt_pass methods: */
2553 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2554 virtual unsigned int execute (function
*)
2556 return execute_early_warn_uninitialized ();
2559 }; // class pass_early_warn_uninitialized
2564 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2566 return new pass_early_warn_uninitialized (ctxt
);