1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2020 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"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
37 /* This implements the pass that does predicate aware warning on uses of
38 possibly uninitialized variables. The pass first collects the set of
39 possibly uninitialized SSA names. For each such name, it walks through
40 all its immediate uses. For each immediate use, it rebuilds the condition
41 expression (the predicate) that guards the use. The predicate is then
42 examined to see if the variable is always defined under that same condition.
43 This is done either by pruning the unrealizable paths that lead to the
44 default definitions or by checking if the predicate set that guards the
45 defining paths is a superset of the use predicate. */
47 /* Max PHI args we can handle in pass. */
48 const unsigned max_phi_args
= 32;
50 /* Pointer set of potentially undefined ssa names, i.e.,
51 ssa names that are defined by phi with operands that
52 are not defined or potentially undefined. */
53 static hash_set
<tree
> *possibly_undefined_names
= 0;
55 /* Bit mask handling macros. */
56 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
57 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
58 #define MASK_EMPTY(mask) (mask == 0)
60 /* Returns the first bit position (starting from LSB)
61 in mask that is non zero. Returns -1 if the mask is empty. */
63 get_mask_first_set_bit (unsigned mask
)
69 while ((mask
& (1 << pos
)) == 0)
74 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
76 /* Return true if T, an SSA_NAME, has an undefined value. */
78 has_undefined_value_p (tree t
)
80 return (ssa_undefined_value_p (t
)
81 || (possibly_undefined_names
82 && possibly_undefined_names
->contains (t
)));
85 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
86 is set on SSA_NAME_VAR. */
89 uninit_undefined_value_p (tree t
)
91 if (!has_undefined_value_p (t
))
93 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
98 /* Emit warnings for uninitialized variables. This is done in two passes.
100 The first pass notices real uses of SSA names with undefined values.
101 Such uses are unconditionally uninitialized, and we can be certain that
102 such a use is a mistake. This pass is run before most optimizations,
103 so that we catch as many as we can.
105 The second pass follows PHI nodes to find uses that are potentially
106 uninitialized. In this case we can't necessarily prove that the use
107 is really uninitialized. This pass is run after most optimizations,
108 so that we thread as many jumps and possible, and delete as much dead
109 code as possible, in order to reduce false positives. We also look
110 again for plain uninitialized variables, since optimization may have
111 changed conditionally uninitialized to unconditionally uninitialized. */
113 /* Emit a warning for EXPR based on variable VAR at the point in the
114 program T, an SSA_NAME, is used being uninitialized. The exact
115 warning text is in MSGID and DATA is the gimple stmt with info about
116 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
117 gives which argument of the phi node to take the location from. WC
118 is the warning code. */
121 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
122 const char *gmsgid
, void *data
, location_t phiarg_loc
)
124 gimple
*context
= (gimple
*) data
;
125 location_t location
, cfun_loc
;
126 expanded_location xloc
, floc
;
128 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
129 turns in a COMPLEX_EXPR with the not initialized part being
130 set to its previous (undefined) value. */
131 if (is_gimple_assign (context
)
132 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
134 if (!has_undefined_value_p (t
))
137 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
138 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
139 created for conversion from scalar to complex. Use the underlying var of
140 the COMPLEX_EXPRs real part in that case. See PR71581. */
141 if (expr
== NULL_TREE
143 && SSA_NAME_VAR (t
) == NULL_TREE
144 && is_gimple_assign (SSA_NAME_DEF_STMT (t
))
145 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t
)) == COMPLEX_EXPR
)
147 tree v
= gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t
));
148 if (TREE_CODE (v
) == SSA_NAME
149 && has_undefined_value_p (v
)
150 && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t
))))
152 expr
= SSA_NAME_VAR (v
);
157 if (expr
== NULL_TREE
)
160 /* TREE_NO_WARNING either means we already warned, or the front end
161 wishes to suppress the warning. */
163 && (gimple_no_warning_p (context
)
164 || (gimple_assign_single_p (context
)
165 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
166 || TREE_NO_WARNING (expr
))
169 if (context
!= NULL
&& gimple_has_location (context
))
170 location
= gimple_location (context
);
171 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
172 location
= phiarg_loc
;
174 location
= DECL_SOURCE_LOCATION (var
);
175 location
= linemap_resolve_location (line_table
, location
,
176 LRK_SPELLING_LOCATION
, NULL
);
177 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
178 xloc
= expand_location (location
);
179 floc
= expand_location (cfun_loc
);
180 auto_diagnostic_group d
;
181 if (warning_at (location
, wc
, gmsgid
, expr
))
183 TREE_NO_WARNING (expr
) = 1;
185 if (location
== DECL_SOURCE_LOCATION (var
))
187 if (xloc
.file
!= floc
.file
188 || linemap_location_before_p (line_table
, location
, cfun_loc
)
189 || linemap_location_before_p (line_table
, cfun
->function_end_locus
,
191 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
195 struct check_defs_data
197 /* If we found any may-defs besides must-def clobbers. */
201 /* Callback for walk_aliased_vdefs. */
204 check_defs (ao_ref
*ref
, tree vdef
, void *data_
)
206 check_defs_data
*data
= (check_defs_data
*)data_
;
207 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vdef
);
208 /* If this is a clobber then if it is not a kill walk past it. */
209 if (gimple_clobber_p (def_stmt
))
211 if (stmt_kills_ref_p (def_stmt
, ref
))
215 /* Found a may-def on this path. */
216 data
->found_may_defs
= true;
221 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
223 gimple_stmt_iterator gsi
;
225 unsigned int vdef_cnt
= 0;
226 unsigned int oracle_cnt
= 0;
229 FOR_EACH_BB_FN (bb
, cfun
)
231 basic_block succ
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
232 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
, succ
, bb
);
233 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
235 gimple
*stmt
= gsi_stmt (gsi
);
240 if (is_gimple_debug (stmt
))
243 /* We only do data flow with SSA_NAMEs, so that's all we
245 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
247 /* BIT_INSERT_EXPR first operand should not be considered
248 a use for the purpose of uninit warnings. */
249 if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
251 if (gimple_assign_rhs_code (ass
) == BIT_INSERT_EXPR
252 && use_p
->use
== gimple_assign_rhs1_ptr (ass
))
255 use
= USE_FROM_PTR (use_p
);
257 warn_uninit (OPT_Wuninitialized
, use
, SSA_NAME_VAR (use
),
259 "%qD is used uninitialized in this function", stmt
,
261 else if (warn_possibly_uninitialized
)
262 warn_uninit (OPT_Wmaybe_uninitialized
, use
, SSA_NAME_VAR (use
),
264 "%qD may be used uninitialized in this function",
265 stmt
, UNKNOWN_LOCATION
);
268 /* For limiting the alias walk below we count all
269 vdefs in the function. */
270 if (gimple_vdef (stmt
))
273 if (gimple_assign_load_p (stmt
)
274 && gimple_has_location (stmt
))
276 tree rhs
= gimple_assign_rhs1 (stmt
);
277 tree lhs
= gimple_assign_lhs (stmt
);
278 bool has_bit_insert
= false;
279 use_operand_p luse_p
;
280 imm_use_iterator liter
;
282 if (TREE_NO_WARNING (rhs
))
286 ao_ref_init (&ref
, rhs
);
288 /* Do not warn if the base was marked so or this is a
289 hard register var. */
290 tree base
= ao_ref_base (&ref
);
292 && DECL_HARD_REGISTER (base
))
293 || TREE_NO_WARNING (base
))
296 /* Do not warn if the access is fully outside of the
298 poly_int64 decl_size
;
300 && known_size_p (ref
.size
)
301 && ((known_eq (ref
.max_size
, ref
.size
)
302 && known_le (ref
.offset
+ ref
.size
, 0))
303 || (known_ge (ref
.offset
, 0)
305 && poly_int_tree_p (DECL_SIZE (base
), &decl_size
)
306 && known_le (decl_size
, ref
.offset
))))
309 /* Do not warn if the access is then used for a BIT_INSERT_EXPR. */
310 if (TREE_CODE (lhs
) == SSA_NAME
)
311 FOR_EACH_IMM_USE_FAST (luse_p
, liter
, lhs
)
313 gimple
*use_stmt
= USE_STMT (luse_p
);
314 /* BIT_INSERT_EXPR first operand should not be considered
315 a use for the purpose of uninit warnings. */
316 if (gassign
*ass
= dyn_cast
<gassign
*> (use_stmt
))
318 if (gimple_assign_rhs_code (ass
) == BIT_INSERT_EXPR
319 && luse_p
->use
== gimple_assign_rhs1_ptr (ass
))
321 has_bit_insert
= true;
329 /* Limit the walking to a constant number of stmts after
330 we overcommit quadratic behavior for small functions
331 and O(n) behavior. */
332 if (oracle_cnt
> 128 * 128
333 && oracle_cnt
> vdef_cnt
* 2)
335 check_defs_data data
;
336 bool fentry_reached
= false;
337 data
.found_may_defs
= false;
338 use
= gimple_vuse (stmt
);
339 int res
= walk_aliased_vdefs (&ref
, use
,
340 check_defs
, &data
, NULL
,
341 &fentry_reached
, limit
);
348 if (data
.found_may_defs
)
350 /* Do not warn if it can be initialized outside this function.
351 If we did not reach function entry then we found killing
352 clobbers on all paths to entry. */
354 /* ??? We'd like to use ref_may_alias_global_p but that
355 excludes global readonly memory and thus we get bougs
356 warnings from p = cond ? "a" : "b" for example. */
358 || is_global_var (base
)))
361 /* We didn't find any may-defs so on all paths either
362 reached function entry or a killing clobber. */
364 = linemap_resolve_location (line_table
, gimple_location (stmt
),
365 LRK_SPELLING_LOCATION
, NULL
);
368 if (warning_at (location
, OPT_Wuninitialized
,
369 "%qE is used uninitialized in this function",
371 /* ??? This is only effective for decls as in
372 gcc.dg/uninit-B-O0.c. Avoid doing this for
373 maybe-uninit uses as it may hide important
375 TREE_NO_WARNING (rhs
) = 1;
377 else if (warn_possibly_uninitialized
)
378 warning_at (location
, OPT_Wmaybe_uninitialized
,
379 "%qE may be used uninitialized in this function",
388 /* Checks if the operand OPND of PHI is defined by
389 another phi with one operand defined by this PHI,
390 but the rest operands are all defined. If yes,
391 returns true to skip this operand as being
392 redundant. Can be enhanced to be more general. */
395 can_skip_redundant_opnd (tree opnd
, gimple
*phi
)
401 phi_def
= gimple_phi_result (phi
);
402 op_def
= SSA_NAME_DEF_STMT (opnd
);
403 if (gimple_code (op_def
) != GIMPLE_PHI
)
405 n
= gimple_phi_num_args (op_def
);
406 for (i
= 0; i
< n
; ++i
)
408 tree op
= gimple_phi_arg_def (op_def
, i
);
409 if (TREE_CODE (op
) != SSA_NAME
)
411 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
418 /* Returns a bit mask holding the positions of arguments in PHI
419 that have empty (or possibly empty) definitions. */
422 compute_uninit_opnds_pos (gphi
*phi
)
425 unsigned uninit_opnds
= 0;
427 n
= gimple_phi_num_args (phi
);
428 /* Bail out for phi with too many args. */
429 if (n
> max_phi_args
)
432 for (i
= 0; i
< n
; ++i
)
434 tree op
= gimple_phi_arg_def (phi
, i
);
435 if (TREE_CODE (op
) == SSA_NAME
436 && uninit_undefined_value_p (op
)
437 && !can_skip_redundant_opnd (op
, phi
))
439 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
441 /* Ignore SSA_NAMEs that appear on abnormal edges
443 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
446 MASK_SET_BIT (uninit_opnds
, i
);
452 /* Find the immediate postdominator PDOM of the specified
453 basic block BLOCK. */
455 static inline basic_block
456 find_pdom (basic_block block
)
458 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
459 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
462 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
464 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
469 /* Find the immediate DOM of the specified basic block BLOCK. */
471 static inline basic_block
472 find_dom (basic_block block
)
474 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
475 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
478 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
480 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
485 /* Returns true if BB1 is postdominating BB2 and BB1 is
486 not a loop exit bb. The loop exit bb check is simple and does
487 not cover all cases. */
490 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
492 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
495 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
501 /* Find the closest postdominator of a specified BB, which is control
504 static inline basic_block
505 find_control_equiv_block (basic_block bb
)
509 pdom
= find_pdom (bb
);
511 /* Skip the postdominating bb that is also loop exit. */
512 if (!is_non_loop_exit_postdominating (pdom
, bb
))
515 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
521 #define MAX_NUM_CHAINS 8
522 #define MAX_CHAIN_LEN 5
523 #define MAX_POSTDOM_CHECK 8
524 #define MAX_SWITCH_CASES 40
526 /* Computes the control dependence chains (paths of edges)
527 for DEP_BB up to the dominating basic block BB (the head node of a
528 chain should be dominated by it). CD_CHAINS is pointer to an
529 array holding the result chains. CUR_CD_CHAIN is the current
530 chain being computed. *NUM_CHAINS is total number of chains. The
531 function returns true if the information is successfully computed,
532 return false if there is no control dependence or not computed. */
535 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
536 vec
<edge
> *cd_chains
,
538 vec
<edge
> *cur_cd_chain
,
544 bool found_cd_chain
= false;
545 size_t cur_chain_len
= 0;
547 if (*num_calls
> param_uninit_control_dep_attempts
)
551 /* Could use a set instead. */
552 cur_chain_len
= cur_cd_chain
->length ();
553 if (cur_chain_len
> MAX_CHAIN_LEN
)
556 for (i
= 0; i
< cur_chain_len
; i
++)
558 edge e
= (*cur_cd_chain
)[i
];
559 /* Cycle detected. */
564 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
567 int post_dom_check
= 0;
568 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
572 cur_cd_chain
->safe_push (e
);
573 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
577 /* Found a direct control dependence. */
578 if (*num_chains
< MAX_NUM_CHAINS
)
580 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
583 found_cd_chain
= true;
584 /* Check path from next edge. */
588 /* Now check if DEP_BB is indirectly control dependent on BB. */
589 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
, num_chains
,
590 cur_cd_chain
, num_calls
))
592 found_cd_chain
= true;
596 cd_bb
= find_pdom (cd_bb
);
598 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
599 || post_dom_check
> MAX_POSTDOM_CHECK
)
602 cur_cd_chain
->pop ();
603 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
605 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
607 return found_cd_chain
;
610 /* The type to represent a simple predicate. */
616 enum tree_code cond_code
;
620 /* The type to represent a sequence of predicates grouped
621 with .AND. operation. */
623 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
625 /* The type to represent a sequence of pred_chains grouped
626 with .OR. operation. */
628 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
630 /* Converts the chains of control dependence edges into a set of
631 predicates. A control dependence chain is represented by a vector
632 edges. DEP_CHAINS points to an array of dependence chains.
633 NUM_CHAINS is the size of the chain array. One edge in a dependence
634 chain is mapped to predicate expression represented by pred_info
635 type. One dependence chain is converted to a composite predicate that
636 is the result of AND operation of pred_info mapped to each edge.
637 A composite predicate is presented by a vector of pred_info. On
638 return, *PREDS points to the resulting array of composite predicates.
639 *NUM_PREDS is the number of composite predictes. */
642 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
644 pred_chain_union
*preds
)
646 bool has_valid_pred
= false;
648 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
651 /* Now convert the control dep chain into a set
653 preds
->reserve (num_chains
);
655 for (i
= 0; i
< num_chains
; i
++)
657 vec
<edge
> one_cd_chain
= dep_chains
[i
];
659 has_valid_pred
= false;
660 pred_chain t_chain
= vNULL
;
661 for (j
= 0; j
< one_cd_chain
.length (); j
++)
664 gimple_stmt_iterator gsi
;
665 basic_block guard_bb
;
671 gsi
= gsi_last_bb (guard_bb
);
672 /* Ignore empty forwarder blocks. */
673 if (empty_block_p (guard_bb
) && single_succ_p (guard_bb
))
675 /* An empty basic block here is likely a PHI, and is not one
676 of the cases we handle below. */
679 has_valid_pred
= false;
682 cond_stmt
= gsi_stmt (gsi
);
683 if (is_gimple_call (cond_stmt
) && EDGE_COUNT (e
->src
->succs
) >= 2)
684 /* Ignore EH edge. Can add assertion on the other edge's flag. */
686 /* Skip if there is essentially one succesor. */
687 if (EDGE_COUNT (e
->src
->succs
) == 2)
693 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
695 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
704 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
706 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
707 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
708 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
709 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
710 t_chain
.safe_push (one_pred
);
711 has_valid_pred
= true;
713 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
715 /* Avoid quadratic behavior. */
716 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
718 has_valid_pred
= false;
721 /* Find the case label. */
724 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
726 tree tl
= gimple_switch_label (gs
, idx
);
727 if (e
->dest
== label_to_block (cfun
, CASE_LABEL (tl
)))
738 /* If more than one label reaches this block or the case
739 label doesn't have a single value (like the default one)
744 && !operand_equal_p (CASE_LOW (l
), CASE_HIGH (l
), 0)))
746 has_valid_pred
= false;
749 one_pred
.pred_lhs
= gimple_switch_index (gs
);
750 one_pred
.pred_rhs
= CASE_LOW (l
);
751 one_pred
.cond_code
= EQ_EXPR
;
752 one_pred
.invert
= false;
753 t_chain
.safe_push (one_pred
);
754 has_valid_pred
= true;
758 has_valid_pred
= false;
766 preds
->safe_push (t_chain
);
768 return has_valid_pred
;
771 /* Computes all control dependence chains for USE_BB. The control
772 dependence chains are then converted to an array of composite
773 predicates pointed to by PREDS. PHI_BB is the basic block of
774 the phi whose result is used in USE_BB. */
777 find_predicates (pred_chain_union
*preds
,
781 size_t num_chains
= 0, i
;
783 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
784 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
785 bool has_valid_pred
= false;
786 basic_block cd_root
= 0;
788 /* First find the closest bb that is control equivalent to PHI_BB
789 that also dominates USE_BB. */
791 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
793 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
794 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
795 cd_root
= ctrl_eq_bb
;
800 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
801 &cur_chain
, &num_calls
);
804 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
805 for (i
= 0; i
< num_chains
; i
++)
806 dep_chains
[i
].release ();
807 return has_valid_pred
;
810 /* Computes the set of incoming edges of PHI that have non empty
811 definitions of a phi chain. The collection will be done
812 recursively on operands that are defined by phis. CD_ROOT
813 is the control dependence root. *EDGES holds the result, and
814 VISITED_PHIS is a pointer set for detecting cycles. */
817 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
818 auto_vec
<edge
> *edges
,
819 hash_set
<gimple
*> *visited_phis
)
825 if (visited_phis
->add (phi
))
828 n
= gimple_phi_num_args (phi
);
829 for (i
= 0; i
< n
; i
++)
831 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
832 opnd
= gimple_phi_arg_def (phi
, i
);
834 if (TREE_CODE (opnd
) != SSA_NAME
)
836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
838 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int) i
);
839 print_gimple_stmt (dump_file
, phi
, 0);
841 edges
->safe_push (opnd_edge
);
845 gimple
*def
= SSA_NAME_DEF_STMT (opnd
);
847 if (gimple_code (def
) == GIMPLE_PHI
848 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (def
), cd_root
))
849 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
851 else if (!uninit_undefined_value_p (opnd
))
853 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
855 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ",
857 print_gimple_stmt (dump_file
, phi
, 0);
859 edges
->safe_push (opnd_edge
);
865 /* For each use edge of PHI, computes all control dependence chains.
866 The control dependence chains are then converted to an array of
867 composite predicates pointed to by PREDS. */
870 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
872 size_t num_chains
= 0, i
, n
;
873 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
874 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
875 auto_vec
<edge
> def_edges
;
876 bool has_valid_pred
= false;
877 basic_block phi_bb
, cd_root
= 0;
879 phi_bb
= gimple_bb (phi
);
880 /* First find the closest dominating bb to be
881 the control dependence root. */
882 cd_root
= find_dom (phi_bb
);
886 hash_set
<gimple
*> visited_phis
;
887 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
889 n
= def_edges
.length ();
893 for (i
= 0; i
< n
; i
++)
899 opnd_edge
= def_edges
[i
];
900 prev_nc
= num_chains
;
901 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
902 &num_chains
, &cur_chain
, &num_calls
);
904 /* Now update the newly added chains with
905 the phi operand edge: */
906 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
908 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
909 dep_chains
[num_chains
++] = vNULL
;
910 for (j
= prev_nc
; j
< num_chains
; j
++)
911 dep_chains
[j
].safe_push (opnd_edge
);
916 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
917 for (i
= 0; i
< num_chains
; i
++)
918 dep_chains
[i
].release ();
919 return has_valid_pred
;
922 /* Dump a pred_info. */
925 dump_pred_info (pred_info one_pred
)
928 fprintf (dump_file
, " (.NOT.) ");
929 print_generic_expr (dump_file
, one_pred
.pred_lhs
);
930 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
931 print_generic_expr (dump_file
, one_pred
.pred_rhs
);
934 /* Dump a pred_chain. */
937 dump_pred_chain (pred_chain one_pred_chain
)
939 size_t np
= one_pred_chain
.length ();
940 for (size_t j
= 0; j
< np
; j
++)
942 dump_pred_info (one_pred_chain
[j
]);
944 fprintf (dump_file
, " (.AND.) ");
946 fprintf (dump_file
, "\n");
950 /* Dumps the predicates (PREDS) for USESTMT. */
953 dump_predicates (gimple
*usestmt
, pred_chain_union preds
, const char *msg
)
955 fprintf (dump_file
, "%s", msg
);
958 print_gimple_stmt (dump_file
, usestmt
, 0);
959 fprintf (dump_file
, "is guarded by :\n\n");
961 size_t num_preds
= preds
.length ();
962 for (size_t i
= 0; i
< num_preds
; i
++)
964 dump_pred_chain (preds
[i
]);
965 if (i
< num_preds
- 1)
966 fprintf (dump_file
, "(.OR.)\n");
968 fprintf (dump_file
, "\n\n");
972 /* Destroys the predicate set *PREDS. */
975 destroy_predicate_vecs (pred_chain_union
*preds
)
979 size_t n
= preds
->length ();
980 for (i
= 0; i
< n
; i
++)
981 (*preds
)[i
].release ();
985 /* Computes the 'normalized' conditional code with operand
986 swapping and condition inversion. */
988 static enum tree_code
989 get_cmp_code (enum tree_code orig_cmp_code
, bool swap_cond
, bool invert
)
991 enum tree_code tc
= orig_cmp_code
;
994 tc
= swap_tree_comparison (orig_cmp_code
);
996 tc
= invert_tree_comparison (tc
, false);
1013 /* Returns whether VAL CMPC BOUNDARY is true. */
1016 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
1018 bool inverted
= false;
1021 /* Only handle integer constant here. */
1022 if (TREE_CODE (val
) != INTEGER_CST
|| TREE_CODE (boundary
) != INTEGER_CST
)
1025 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
|| cmpc
== NE_EXPR
)
1027 cmpc
= invert_tree_comparison (cmpc
, false);
1031 if (cmpc
== EQ_EXPR
)
1032 result
= tree_int_cst_equal (val
, boundary
);
1033 else if (cmpc
== LT_EXPR
)
1034 result
= tree_int_cst_lt (val
, boundary
);
1037 gcc_assert (cmpc
== LE_EXPR
);
1038 result
= tree_int_cst_le (val
, boundary
);
1047 /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can be
1048 either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like),
1049 or BIT_AND_EXPR. EXACT_P is only meaningful for the latter. It modifies the
1050 question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL.
1051 For other values of CMPC, EXACT_P is ignored. */
1054 value_sat_pred_p (tree val
, tree boundary
, enum tree_code cmpc
,
1055 bool exact_p
= false)
1057 if (cmpc
!= BIT_AND_EXPR
)
1058 return is_value_included_in (val
, boundary
, cmpc
);
1060 wide_int andw
= wi::to_wide (val
) & wi::to_wide (boundary
);
1062 return andw
== wi::to_wide (val
);
1064 return andw
.to_uhwi ();
1067 /* Returns true if PRED is common among all the predicate
1068 chains (PREDS) (and therefore can be factored out).
1069 NUM_PRED_CHAIN is the size of array PREDS. */
1072 find_matching_predicate_in_rest_chains (pred_info pred
,
1073 pred_chain_union preds
,
1074 size_t num_pred_chains
)
1079 if (num_pred_chains
== 1)
1082 for (i
= 1; i
< num_pred_chains
; i
++)
1085 pred_chain one_chain
= preds
[i
];
1086 n
= one_chain
.length ();
1087 for (j
= 0; j
< n
; j
++)
1089 pred_info pred2
= one_chain
[j
];
1090 /* Can relax the condition comparison to not
1091 use address comparison. However, the most common
1092 case is that multiple control dependent paths share
1093 a common path prefix, so address comparison should
1096 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
1097 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
1098 && pred2
.invert
== pred
.invert
)
1110 /* Forward declaration. */
1111 static bool is_use_properly_guarded (gimple
*use_stmt
,
1114 unsigned uninit_opnds
,
1115 pred_chain_union
*def_preds
,
1116 hash_set
<gphi
*> *visited_phis
);
1118 /* Returns true if all uninitialized opnds are pruned. Returns false
1119 otherwise. PHI is the phi node with uninitialized operands,
1120 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1121 FLAG_DEF is the statement defining the flag guarding the use of the
1122 PHI output, BOUNDARY_CST is the const value used in the predicate
1123 associated with the flag, CMP_CODE is the comparison code used in
1124 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1125 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1131 flag_1 = phi <0, 1> // (1)
1132 var_1 = phi <undef, some_val>
1136 flag_2 = phi <0, flag_1, flag_1> // (2)
1137 var_2 = phi <undef, var_1, var_1>
1144 Because some flag arg in (1) is not constant, if we do not look into the
1145 flag phis recursively, it is conservatively treated as unknown and var_1
1146 is thought to be flowed into use at (3). Since var_1 is potentially
1147 uninitialized a false warning will be emitted.
1148 Checking recursively into (1), the compiler can find out that only some_val
1149 (which is defined) can flow into (3) which is OK. */
1152 prune_uninit_phi_opnds (gphi
*phi
, unsigned uninit_opnds
, gphi
*flag_def
,
1153 tree boundary_cst
, enum tree_code cmp_code
,
1154 hash_set
<gphi
*> *visited_phis
,
1155 bitmap
*visited_flag_phis
)
1159 for (i
= 0; i
< MIN (max_phi_args
, gimple_phi_num_args (flag_def
)); i
++)
1163 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1166 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1167 if (!is_gimple_constant (flag_arg
))
1169 gphi
*flag_arg_def
, *phi_arg_def
;
1171 unsigned uninit_opnds_arg_phi
;
1173 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1175 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1179 phi_arg
= gimple_phi_arg_def (phi
, i
);
1180 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1183 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1187 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1190 if (!*visited_flag_phis
)
1191 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1193 tree phi_result
= gimple_phi_result (flag_arg_def
);
1194 if (bitmap_bit_p (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
)))
1197 bitmap_set_bit (*visited_flag_phis
,
1198 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1200 /* Now recursively prune the uninitialized phi args. */
1201 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1202 if (!prune_uninit_phi_opnds
1203 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
, boundary_cst
,
1204 cmp_code
, visited_phis
, visited_flag_phis
))
1207 phi_result
= gimple_phi_result (flag_arg_def
);
1208 bitmap_clear_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
1212 /* Now check if the constant is in the guarded range. */
1213 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1218 /* Now that we know that this undefined edge is not
1219 pruned. If the operand is defined by another phi,
1220 we can further prune the incoming edges of that
1221 phi by checking the predicates of this operands. */
1223 opnd
= gimple_phi_arg_def (phi
, i
);
1224 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1225 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1228 unsigned uninit_opnds2
= compute_uninit_opnds_pos (opnd_def_phi
);
1229 if (!MASK_EMPTY (uninit_opnds2
))
1231 pred_chain_union def_preds
= vNULL
;
1233 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1234 ok
= is_use_properly_guarded (phi
,
1240 destroy_predicate_vecs (&def_preds
);
1253 /* A helper function that determines if the predicate set
1254 of the use is not overlapping with that of the uninit paths.
1255 The most common senario of guarded use is in Example 1:
1268 The real world examples are usually more complicated, but similar
1269 and usually result from inlining:
1271 bool init_func (int * x)
1283 if (!init_func (&x))
1290 Another possible use scenario is in the following trivial example:
1302 Predicate analysis needs to compute the composite predicate:
1304 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1305 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1306 (the predicate chain for phi operand defs can be computed
1307 starting from a bb that is control equivalent to the phi's
1308 bb and is dominating the operand def.)
1310 and check overlapping:
1311 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1314 This implementation provides framework that can handle
1315 scenarios. (Note that many simple cases are handled properly
1316 without the predicate analysis -- this is due to jump threading
1317 transformation which eliminates the merge point thus makes
1318 path sensitive analysis unnecessary.)
1320 PHI is the phi node whose incoming (undefined) paths need to be
1321 pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
1322 positions. VISITED_PHIS is the pointer set of phi stmts being
1326 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1327 gphi
*phi
, unsigned uninit_opnds
,
1328 hash_set
<gphi
*> *visited_phis
)
1331 gimple
*flag_def
= 0;
1332 tree boundary_cst
= 0;
1333 enum tree_code cmp_code
;
1334 bool swap_cond
= false;
1335 bool invert
= false;
1336 pred_chain the_pred_chain
= vNULL
;
1337 bitmap visited_flag_phis
= NULL
;
1338 bool all_pruned
= false;
1339 size_t num_preds
= preds
.length ();
1341 gcc_assert (num_preds
> 0);
1342 /* Find within the common prefix of multiple predicate chains
1343 a predicate that is a comparison of a flag variable against
1345 the_pred_chain
= preds
[0];
1346 n
= the_pred_chain
.length ();
1347 for (i
= 0; i
< n
; i
++)
1349 tree cond_lhs
, cond_rhs
, flag
= 0;
1351 pred_info the_pred
= the_pred_chain
[i
];
1353 invert
= the_pred
.invert
;
1354 cond_lhs
= the_pred
.pred_lhs
;
1355 cond_rhs
= the_pred
.pred_rhs
;
1356 cmp_code
= the_pred
.cond_code
;
1358 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1359 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1361 boundary_cst
= cond_rhs
;
1364 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1365 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1367 boundary_cst
= cond_lhs
;
1375 flag_def
= SSA_NAME_DEF_STMT (flag
);
1380 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1381 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1382 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1392 /* Now check all the uninit incoming edge has a constant flag value
1393 that is in conflict with the use guard/predicate. */
1394 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1396 if (cmp_code
== ERROR_MARK
)
1399 all_pruned
= prune_uninit_phi_opnds
1400 (phi
, uninit_opnds
, as_a
<gphi
*> (flag_def
), boundary_cst
, cmp_code
,
1401 visited_phis
, &visited_flag_phis
);
1403 if (visited_flag_phis
)
1404 BITMAP_FREE (visited_flag_phis
);
1409 /* The helper function returns true if two predicates X1 and X2
1410 are equivalent. It assumes the expressions have already
1411 properly re-associated. */
1414 pred_equal_p (pred_info x1
, pred_info x2
)
1416 enum tree_code c1
, c2
;
1417 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1418 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1422 if (x1
.invert
!= x2
.invert
1423 && TREE_CODE_CLASS (x2
.cond_code
) == tcc_comparison
)
1424 c2
= invert_tree_comparison (x2
.cond_code
, false);
1431 /* Returns true if the predication is testing !=. */
1434 is_neq_relop_p (pred_info pred
)
1437 return ((pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1438 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
));
1441 /* Returns true if pred is of the form X != 0. */
1444 is_neq_zero_form_p (pred_info pred
)
1446 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1447 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1452 /* The helper function returns true if two predicates X1
1453 is equivalent to X2 != 0. */
1456 pred_expr_equal_p (pred_info x1
, tree x2
)
1458 if (!is_neq_zero_form_p (x1
))
1461 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1464 /* Returns true of the domain of single predicate expression
1465 EXPR1 is a subset of that of EXPR2. Returns false if it
1466 cannot be proved. */
1469 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1471 enum tree_code code1
, code2
;
1473 if (pred_equal_p (expr1
, expr2
))
1476 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1477 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1480 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1483 code1
= expr1
.cond_code
;
1485 code1
= invert_tree_comparison (code1
, false);
1486 code2
= expr2
.cond_code
;
1488 code2
= invert_tree_comparison (code2
, false);
1490 if (code2
== NE_EXPR
&& code1
== NE_EXPR
)
1493 if (code2
== NE_EXPR
)
1494 return !value_sat_pred_p (expr2
.pred_rhs
, expr1
.pred_rhs
, code1
);
1496 if (code1
== EQ_EXPR
)
1497 return value_sat_pred_p (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
);
1500 return value_sat_pred_p (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
,
1501 code1
== BIT_AND_EXPR
);
1506 /* Returns true if the domain of PRED1 is a subset
1507 of that of PRED2. Returns false if it cannot be proved so. */
1510 is_pred_chain_subset_of (pred_chain pred1
, pred_chain pred2
)
1512 size_t np1
, np2
, i1
, i2
;
1514 np1
= pred1
.length ();
1515 np2
= pred2
.length ();
1517 for (i2
= 0; i2
< np2
; i2
++)
1520 pred_info info2
= pred2
[i2
];
1521 for (i1
= 0; i1
< np1
; i1
++)
1523 pred_info info1
= pred1
[i1
];
1524 if (is_pred_expr_subset_of (info1
, info2
))
1536 /* Returns true if the domain defined by
1537 one pred chain ONE_PRED is a subset of the domain
1538 of *PREDS. It returns false if ONE_PRED's domain is
1539 not a subset of any of the sub-domains of PREDS
1540 (corresponding to each individual chains in it), even
1541 though it may be still be a subset of whole domain
1542 of PREDS which is the union (ORed) of all its subdomains.
1543 In other words, the result is conservative. */
1546 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1549 size_t n
= preds
.length ();
1551 for (i
= 0; i
< n
; i
++)
1553 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1560 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1561 true if the domain defined by PREDS1 is a superset
1562 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1563 PREDS2 respectively. The implementation chooses not to build
1564 generic trees (and relying on the folding capability of the
1565 compiler), but instead performs brute force comparison of
1566 individual predicate chains (won't be a compile time problem
1567 as the chains are pretty short). When the function returns
1568 false, it does not necessarily mean *PREDS1 is not a superset
1569 of *PREDS2, but mean it may not be so since the analysis cannot
1570 prove it. In such cases, false warnings may still be
1574 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1577 pred_chain one_pred_chain
= vNULL
;
1579 n2
= preds2
.length ();
1581 for (i
= 0; i
< n2
; i
++)
1583 one_pred_chain
= preds2
[i
];
1584 if (!is_included_in (one_pred_chain
, preds1
))
1591 /* Returns true if X1 is the negate of X2. */
1594 pred_neg_p (pred_info x1
, pred_info x2
)
1596 enum tree_code c1
, c2
;
1597 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1598 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1602 if (x1
.invert
== x2
.invert
)
1603 c2
= invert_tree_comparison (x2
.cond_code
, false);
1610 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1611 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1612 3) X OR (!X AND Y) is equivalent to (X OR Y);
1613 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1615 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1618 PREDS is the predicate chains, and N is the number of chains. */
1620 /* Helper function to implement rule 1 above. ONE_CHAIN is
1621 the AND predication to be simplified. */
1624 simplify_pred (pred_chain
*one_chain
)
1627 bool simplified
= false;
1628 pred_chain s_chain
= vNULL
;
1630 n
= one_chain
->length ();
1632 for (i
= 0; i
< n
; i
++)
1634 pred_info
*a_pred
= &(*one_chain
)[i
];
1636 if (!a_pred
->pred_lhs
)
1638 if (!is_neq_zero_form_p (*a_pred
))
1641 gimple
*def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1642 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1644 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1646 for (j
= 0; j
< n
; j
++)
1648 pred_info
*b_pred
= &(*one_chain
)[j
];
1650 if (!b_pred
->pred_lhs
)
1652 if (!is_neq_zero_form_p (*b_pred
))
1655 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1656 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1658 /* Mark a_pred for removal. */
1659 a_pred
->pred_lhs
= NULL
;
1660 a_pred
->pred_rhs
= NULL
;
1671 for (i
= 0; i
< n
; i
++)
1673 pred_info
*a_pred
= &(*one_chain
)[i
];
1674 if (!a_pred
->pred_lhs
)
1676 s_chain
.safe_push (*a_pred
);
1679 one_chain
->release ();
1680 *one_chain
= s_chain
;
1683 /* The helper function implements the rule 2 for the
1686 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1689 simplify_preds_2 (pred_chain_union
*preds
)
1692 bool simplified
= false;
1693 pred_chain_union s_preds
= vNULL
;
1695 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1696 (X AND Y) OR (X AND !Y) is equivalent to X. */
1698 n
= preds
->length ();
1699 for (i
= 0; i
< n
; i
++)
1702 pred_chain
*a_chain
= &(*preds
)[i
];
1704 if (a_chain
->length () != 2)
1710 for (j
= 0; j
< n
; j
++)
1712 pred_chain
*b_chain
;
1718 b_chain
= &(*preds
)[j
];
1719 if (b_chain
->length () != 2)
1725 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1728 a_chain
->release ();
1729 b_chain
->release ();
1730 b_chain
->safe_push (x
);
1734 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1737 a_chain
->release ();
1738 b_chain
->release ();
1739 b_chain
->safe_push (y
);
1745 /* Now clean up the chain. */
1748 for (i
= 0; i
< n
; i
++)
1750 if ((*preds
)[i
].is_empty ())
1752 s_preds
.safe_push ((*preds
)[i
]);
1762 /* The helper function implements the rule 2 for the
1765 3) x OR (!x AND y) is equivalent to x OR y. */
1768 simplify_preds_3 (pred_chain_union
*preds
)
1771 bool simplified
= false;
1773 /* Now iteratively simplify X OR (!X AND Z ..)
1774 into X OR (Z ...). */
1776 n
= preds
->length ();
1780 for (i
= 0; i
< n
; i
++)
1783 pred_chain
*a_chain
= &(*preds
)[i
];
1785 if (a_chain
->length () != 1)
1790 for (j
= 0; j
< n
; j
++)
1792 pred_chain
*b_chain
;
1799 b_chain
= &(*preds
)[j
];
1800 if (b_chain
->length () < 2)
1803 for (k
= 0; k
< b_chain
->length (); k
++)
1806 if (pred_neg_p (x
, x2
))
1808 b_chain
->unordered_remove (k
);
1818 /* The helper function implements the rule 4 for the
1821 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1822 (x != 0 ANd y != 0). */
1825 simplify_preds_4 (pred_chain_union
*preds
)
1828 bool simplified
= false;
1829 pred_chain_union s_preds
= vNULL
;
1832 n
= preds
->length ();
1833 for (i
= 0; i
< n
; i
++)
1836 pred_chain
*a_chain
= &(*preds
)[i
];
1838 if (a_chain
->length () != 1)
1843 if (!is_neq_zero_form_p (z
))
1846 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1847 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1850 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1853 for (j
= 0; j
< n
; j
++)
1855 pred_chain
*b_chain
;
1861 b_chain
= &(*preds
)[j
];
1862 if (b_chain
->length () != 2)
1867 if (!is_neq_zero_form_p (x2
) || !is_neq_zero_form_p (y2
))
1870 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1871 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1872 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1873 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1876 a_chain
->release ();
1882 /* Now clean up the chain. */
1885 for (i
= 0; i
< n
; i
++)
1887 if ((*preds
)[i
].is_empty ())
1889 s_preds
.safe_push ((*preds
)[i
]);
1900 /* This function simplifies predicates in PREDS. */
1903 simplify_preds (pred_chain_union
*preds
, gimple
*use_or_def
, bool is_use
)
1906 bool changed
= false;
1908 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1910 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1911 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1914 for (i
= 0; i
< preds
->length (); i
++)
1915 simplify_pred (&(*preds
)[i
]);
1917 n
= preds
->length ();
1924 if (simplify_preds_2 (preds
))
1927 /* Now iteratively simplify X OR (!X AND Z ..)
1928 into X OR (Z ...). */
1929 if (simplify_preds_3 (preds
))
1932 if (simplify_preds_4 (preds
))
1940 /* This is a helper function which attempts to normalize predicate chains
1941 by following UD chains. It basically builds up a big tree of either IOR
1942 operations or AND operations, and convert the IOR tree into a
1943 pred_chain_union or BIT_AND tree into a pred_chain.
1953 then _t != 0 will be normalized into a pred_chain_union
1955 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1965 then _t != 0 will be normalized into a pred_chain:
1966 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1970 /* This is a helper function that stores a PRED into NORM_PREDS. */
1973 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1975 pred_chain pred_chain
= vNULL
;
1976 pred_chain
.safe_push (pred
);
1977 norm_preds
->safe_push (pred_chain
);
1980 /* A helper function that creates a predicate of the form
1981 OP != 0 and push it WORK_LIST. */
1984 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1985 hash_set
<tree
> *mark_set
)
1987 if (mark_set
->contains (op
))
1992 arg_pred
.pred_lhs
= op
;
1993 arg_pred
.pred_rhs
= integer_zero_node
;
1994 arg_pred
.cond_code
= NE_EXPR
;
1995 arg_pred
.invert
= false;
1996 work_list
->safe_push (arg_pred
);
1999 /* A helper that generates a pred_info from a gimple assignment
2000 CMP_ASSIGN with comparison rhs. */
2003 get_pred_info_from_cmp (gimple
*cmp_assign
)
2006 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
2007 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
2008 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
2009 n_pred
.invert
= false;
2013 /* Returns true if the PHI is a degenerated phi with
2014 all args with the same value (relop). In that case, *PRED
2015 will be updated to that value. */
2018 is_degenerated_phi (gimple
*phi
, pred_info
*pred_p
)
2025 n
= gimple_phi_num_args (phi
);
2026 op0
= gimple_phi_arg_def (phi
, 0);
2028 if (TREE_CODE (op0
) != SSA_NAME
)
2031 def0
= SSA_NAME_DEF_STMT (op0
);
2032 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
2034 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
)) != tcc_comparison
)
2036 pred0
= get_pred_info_from_cmp (def0
);
2038 for (i
= 1; i
< n
; ++i
)
2042 tree op
= gimple_phi_arg_def (phi
, i
);
2044 if (TREE_CODE (op
) != SSA_NAME
)
2047 def
= SSA_NAME_DEF_STMT (op
);
2048 if (gimple_code (def
) != GIMPLE_ASSIGN
)
2050 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) != tcc_comparison
)
2052 pred
= get_pred_info_from_cmp (def
);
2053 if (!pred_equal_p (pred
, pred0
))
2061 /* Normalize one predicate PRED
2062 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2063 2) otherwise if PRED is of the form x != 0, follow x's definition
2064 and put normalized predicates into WORK_LIST. */
2067 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
2068 pred_chain
*norm_chain
,
2070 enum tree_code and_or_code
,
2071 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
2072 hash_set
<tree
> *mark_set
)
2074 if (!is_neq_zero_form_p (pred
))
2076 if (and_or_code
== BIT_IOR_EXPR
)
2077 push_pred (norm_preds
, pred
);
2079 norm_chain
->safe_push (pred
);
2083 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2085 if (gimple_code (def_stmt
) == GIMPLE_PHI
2086 && is_degenerated_phi (def_stmt
, &pred
))
2087 work_list
->safe_push (pred
);
2088 else if (gimple_code (def_stmt
) == GIMPLE_PHI
&& and_or_code
== BIT_IOR_EXPR
)
2091 n
= gimple_phi_num_args (def_stmt
);
2093 /* If we see non zero constant, we should punt. The predicate
2094 * should be one guarding the phi edge. */
2095 for (i
= 0; i
< n
; ++i
)
2097 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2098 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
2100 push_pred (norm_preds
, pred
);
2105 for (i
= 0; i
< n
; ++i
)
2107 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2108 if (integer_zerop (op
))
2111 push_to_worklist (op
, work_list
, mark_set
);
2114 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2116 if (and_or_code
== BIT_IOR_EXPR
)
2117 push_pred (norm_preds
, pred
);
2119 norm_chain
->safe_push (pred
);
2121 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2123 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2124 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2126 /* But treat x & 3 as condition. */
2127 if (and_or_code
== BIT_AND_EXPR
)
2130 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2131 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2132 n_pred
.cond_code
= and_or_code
;
2133 n_pred
.invert
= false;
2134 norm_chain
->safe_push (n_pred
);
2139 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2140 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2143 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2146 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2147 if (and_or_code
== BIT_IOR_EXPR
)
2148 push_pred (norm_preds
, n_pred
);
2150 norm_chain
->safe_push (n_pred
);
2154 if (and_or_code
== BIT_IOR_EXPR
)
2155 push_pred (norm_preds
, pred
);
2157 norm_chain
->safe_push (pred
);
2161 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2164 normalize_one_pred (pred_chain_union
*norm_preds
, pred_info pred
)
2166 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2167 enum tree_code and_or_code
= ERROR_MARK
;
2168 pred_chain norm_chain
= vNULL
;
2170 if (!is_neq_zero_form_p (pred
))
2172 push_pred (norm_preds
, pred
);
2176 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2177 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2178 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2179 if (and_or_code
!= BIT_IOR_EXPR
&& and_or_code
!= BIT_AND_EXPR
)
2181 if (TREE_CODE_CLASS (and_or_code
) == tcc_comparison
)
2183 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2184 push_pred (norm_preds
, n_pred
);
2187 push_pred (norm_preds
, pred
);
2191 work_list
.safe_push (pred
);
2192 hash_set
<tree
> mark_set
;
2194 while (!work_list
.is_empty ())
2196 pred_info a_pred
= work_list
.pop ();
2197 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
, and_or_code
,
2198 &work_list
, &mark_set
);
2200 if (and_or_code
== BIT_AND_EXPR
)
2201 norm_preds
->safe_push (norm_chain
);
2203 work_list
.release ();
2207 normalize_one_pred_chain (pred_chain_union
*norm_preds
, pred_chain one_chain
)
2209 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2210 hash_set
<tree
> mark_set
;
2211 pred_chain norm_chain
= vNULL
;
2214 for (i
= 0; i
< one_chain
.length (); i
++)
2216 work_list
.safe_push (one_chain
[i
]);
2217 mark_set
.add (one_chain
[i
].pred_lhs
);
2220 while (!work_list
.is_empty ())
2222 pred_info a_pred
= work_list
.pop ();
2223 normalize_one_pred_1 (0, &norm_chain
, a_pred
, BIT_AND_EXPR
, &work_list
,
2227 norm_preds
->safe_push (norm_chain
);
2228 work_list
.release ();
2231 /* Normalize predicate chains PREDS and returns the normalized one. */
2233 static pred_chain_union
2234 normalize_preds (pred_chain_union preds
, gimple
*use_or_def
, bool is_use
)
2236 pred_chain_union norm_preds
= vNULL
;
2237 size_t n
= preds
.length ();
2240 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2242 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2243 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2246 for (i
= 0; i
< n
; i
++)
2248 if (preds
[i
].length () != 1)
2249 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2252 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2253 preds
[i
].release ();
2259 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2260 dump_predicates (use_or_def
, norm_preds
,
2261 is_use
? "[USE]:\n" : "[DEF]:\n");
2264 destroy_predicate_vecs (&preds
);
2268 /* Return TRUE if PREDICATE can be invalidated by any individual
2269 predicate in USE_GUARD. */
2272 can_one_predicate_be_invalidated_p (pred_info predicate
,
2273 pred_chain use_guard
)
2275 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2277 fprintf (dump_file
, "Testing if this predicate: ");
2278 dump_pred_info (predicate
);
2279 fprintf (dump_file
, "\n...can be invalidated by a USE guard of: ");
2280 dump_pred_chain (use_guard
);
2282 for (size_t i
= 0; i
< use_guard
.length (); ++i
)
2284 /* NOTE: This is a very simple check, and only understands an
2285 exact opposite. So, [i == 0] is currently only invalidated
2286 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2287 invalidate with say [i > 5] or [i == 8]. There is certainly
2288 room for improvement here. */
2289 if (pred_neg_p (predicate
, use_guard
[i
]))
2291 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2293 fprintf (dump_file
, " Predicate was invalidated by: ");
2294 dump_pred_info (use_guard
[i
]);
2295 fputc ('\n', dump_file
);
2303 /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2304 USE_GUARD being true. */
2307 can_chain_union_be_invalidated_p (pred_chain_union uninit_pred
,
2308 pred_chain use_guard
)
2310 if (uninit_pred
.is_empty ())
2312 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2313 dump_predicates (NULL
, uninit_pred
,
2314 "Testing if anything here can be invalidated: ");
2315 for (size_t i
= 0; i
< uninit_pred
.length (); ++i
)
2317 pred_chain c
= uninit_pred
[i
];
2319 for (j
= 0; j
< c
.length (); ++j
)
2320 if (can_one_predicate_be_invalidated_p (c
[j
], use_guard
))
2323 /* If we were unable to invalidate any predicate in C, then there
2324 is a viable path from entry to the PHI where the PHI takes
2325 an uninitialized value and continues to a use of the PHI. */
2326 if (j
== c
.length ())
2332 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2333 can actually happen if we arrived at a use for PHI.
2335 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2338 uninit_uses_cannot_happen (gphi
*phi
, unsigned uninit_opnds
,
2339 pred_chain_union phi_use_guards
)
2341 unsigned phi_args
= gimple_phi_num_args (phi
);
2342 if (phi_args
> max_phi_args
)
2345 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2346 possible guard, there's no way of knowing which guard was true.
2347 Since we need to be absolutely sure that the uninitialized
2348 operands will be invalidated, bail. */
2349 if (phi_use_guards
.length () != 1)
2352 /* Look for the control dependencies of all the uninitialized
2353 operands and build guard predicates describing them. */
2354 pred_chain_union uninit_preds
;
2356 for (unsigned i
= 0; i
< phi_args
; ++i
)
2358 if (!MASK_TEST_BIT (uninit_opnds
, i
))
2361 edge e
= gimple_phi_arg_edge (phi
, i
);
2362 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
2363 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
2364 size_t num_chains
= 0;
2367 /* Build the control dependency chain for uninit operand `i'... */
2368 uninit_preds
= vNULL
;
2369 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2370 e
->src
, dep_chains
, &num_chains
,
2371 &cur_chain
, &num_calls
))
2376 /* ...and convert it into a set of predicates. */
2377 bool has_valid_preds
2378 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
,
2380 for (size_t j
= 0; j
< num_chains
; ++j
)
2381 dep_chains
[j
].release ();
2382 if (!has_valid_preds
)
2387 simplify_preds (&uninit_preds
, NULL
, false);
2388 uninit_preds
= normalize_preds (uninit_preds
, NULL
, false);
2390 /* Can the guard for this uninitialized operand be invalidated
2392 if (!can_chain_union_be_invalidated_p (uninit_preds
, phi_use_guards
[0]))
2398 destroy_predicate_vecs (&uninit_preds
);
2402 /* Computes the predicates that guard the use and checks
2403 if the incoming paths that have empty (or possibly
2404 empty) definition can be pruned/filtered. The function returns
2405 true if it can be determined that the use of PHI's def in
2406 USE_STMT is guarded with a predicate set not overlapping with
2407 predicate sets of all runtime paths that do not have a definition.
2409 Returns false if it is not or it cannot be determined. USE_BB is
2410 the bb of the use (for phi operand use, the bb is not the bb of
2411 the phi stmt, but the src bb of the operand edge).
2413 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2414 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2415 set of phis being visited.
2417 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2418 If *DEF_PREDS is the empty vector, the defining predicate chains of
2419 PHI will be computed and stored into *DEF_PREDS as needed.
2421 VISITED_PHIS is a pointer set of phis being visited. */
2424 is_use_properly_guarded (gimple
*use_stmt
,
2427 unsigned uninit_opnds
,
2428 pred_chain_union
*def_preds
,
2429 hash_set
<gphi
*> *visited_phis
)
2432 pred_chain_union preds
= vNULL
;
2433 bool has_valid_preds
= false;
2434 bool is_properly_guarded
= false;
2436 if (visited_phis
->add (phi
))
2439 phi_bb
= gimple_bb (phi
);
2441 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2444 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2446 if (!has_valid_preds
)
2448 destroy_predicate_vecs (&preds
);
2452 /* Try to prune the dead incoming phi edges. */
2454 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2457 /* We might be able to prove that if the control dependencies
2458 for UNINIT_OPNDS are true, that the control dependencies for
2459 USE_STMT can never be true. */
2460 if (!is_properly_guarded
)
2461 is_properly_guarded
|= uninit_uses_cannot_happen (phi
, uninit_opnds
,
2464 if (is_properly_guarded
)
2466 destroy_predicate_vecs (&preds
);
2470 if (def_preds
->is_empty ())
2472 has_valid_preds
= find_def_preds (def_preds
, phi
);
2474 if (!has_valid_preds
)
2476 destroy_predicate_vecs (&preds
);
2480 simplify_preds (def_preds
, phi
, false);
2481 *def_preds
= normalize_preds (*def_preds
, phi
, false);
2484 simplify_preds (&preds
, use_stmt
, true);
2485 preds
= normalize_preds (preds
, use_stmt
, true);
2487 is_properly_guarded
= is_superset_of (*def_preds
, preds
);
2489 destroy_predicate_vecs (&preds
);
2490 return is_properly_guarded
;
2493 /* Searches through all uses of a potentially
2494 uninitialized variable defined by PHI and returns a use
2495 statement if the use is not properly guarded. It returns
2496 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2497 holding the position(s) of uninit PHI operands. WORKLIST
2498 is the vector of candidate phis that may be updated by this
2499 function. ADDED_TO_WORKLIST is the pointer set tracking
2500 if the new phi is already in the worklist. */
2503 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2504 vec
<gphi
*> *worklist
,
2505 hash_set
<gphi
*> *added_to_worklist
)
2508 use_operand_p use_p
;
2510 imm_use_iterator iter
;
2511 pred_chain_union def_preds
= vNULL
;
2514 phi_result
= gimple_phi_result (phi
);
2516 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2520 use_stmt
= USE_STMT (use_p
);
2521 if (is_gimple_debug (use_stmt
))
2524 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2525 use_bb
= gimple_phi_arg_edge (use_phi
,
2526 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2528 use_bb
= gimple_bb (use_stmt
);
2530 hash_set
<gphi
*> visited_phis
;
2531 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2532 &def_preds
, &visited_phis
))
2535 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2537 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2538 print_gimple_stmt (dump_file
, use_stmt
, 0);
2540 /* Found one real use, return. */
2541 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2547 /* Found a phi use that is not guarded,
2548 add the phi to the worklist. */
2549 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2551 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2553 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2554 print_gimple_stmt (dump_file
, use_stmt
, 0);
2557 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2558 possibly_undefined_names
->add (phi_result
);
2562 destroy_predicate_vecs (&def_preds
);
2566 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2567 and gives warning if there exists a runtime path from the entry to a
2568 use of the PHI def that does not contain a definition. In other words,
2569 the warning is on the real use. The more dead paths that can be pruned
2570 by the compiler, the fewer false positives the warning is. WORKLIST
2571 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2572 a pointer set tracking if the new phi is added to the worklist or not. */
2575 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2576 hash_set
<gphi
*> *added_to_worklist
)
2578 unsigned uninit_opnds
;
2579 gimple
*uninit_use_stmt
= 0;
2584 /* Don't look at virtual operands. */
2585 if (virtual_operand_p (gimple_phi_result (phi
)))
2588 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2590 if (MASK_EMPTY (uninit_opnds
))
2593 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2595 fprintf (dump_file
, "[CHECK]: examining phi: ");
2596 print_gimple_stmt (dump_file
, phi
, 0);
2599 /* Now check if we have any use of the value without proper guard. */
2600 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2601 worklist
, added_to_worklist
);
2603 /* All uses are properly guarded. */
2604 if (!uninit_use_stmt
)
2607 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2608 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2609 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2611 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2612 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2614 loc
= UNKNOWN_LOCATION
;
2615 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2616 SSA_NAME_VAR (uninit_op
),
2617 "%qD may be used uninitialized in this function",
2618 uninit_use_stmt
, loc
);
2622 gate_warn_uninitialized (void)
2624 return warn_uninitialized
|| warn_maybe_uninitialized
;
2629 const pass_data pass_data_late_warn_uninitialized
=
2631 GIMPLE_PASS
, /* type */
2632 "uninit", /* name */
2633 OPTGROUP_NONE
, /* optinfo_flags */
2634 TV_NONE
, /* tv_id */
2635 PROP_ssa
, /* properties_required */
2636 0, /* properties_provided */
2637 0, /* properties_destroyed */
2638 0, /* todo_flags_start */
2639 0, /* todo_flags_finish */
2642 class pass_late_warn_uninitialized
: public gimple_opt_pass
2645 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2646 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2649 /* opt_pass methods: */
2650 opt_pass
*clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2651 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2652 virtual unsigned int execute (function
*);
2654 }; // class pass_late_warn_uninitialized
2657 pass_late_warn_uninitialized::execute (function
*fun
)
2661 vec
<gphi
*> worklist
= vNULL
;
2663 calculate_dominance_info (CDI_DOMINATORS
);
2664 calculate_dominance_info (CDI_POST_DOMINATORS
);
2665 /* Re-do the plain uninitialized variable check, as optimization may have
2666 straightened control flow. Do this first so that we don't accidentally
2667 get a "may be" warning when we'd have seen an "is" warning later. */
2668 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2670 timevar_push (TV_TREE_UNINIT
);
2672 possibly_undefined_names
= new hash_set
<tree
>;
2673 hash_set
<gphi
*> added_to_worklist
;
2675 /* Initialize worklist */
2676 FOR_EACH_BB_FN (bb
, fun
)
2677 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2679 gphi
*phi
= gsi
.phi ();
2682 n
= gimple_phi_num_args (phi
);
2684 /* Don't look at virtual operands. */
2685 if (virtual_operand_p (gimple_phi_result (phi
)))
2688 for (i
= 0; i
< n
; ++i
)
2690 tree op
= gimple_phi_arg_def (phi
, i
);
2691 if (TREE_CODE (op
) == SSA_NAME
&& uninit_undefined_value_p (op
))
2693 worklist
.safe_push (phi
);
2694 added_to_worklist
.add (phi
);
2695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2697 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2698 print_gimple_stmt (dump_file
, phi
, 0);
2705 while (worklist
.length () != 0)
2708 cur_phi
= worklist
.pop ();
2709 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2712 worklist
.release ();
2713 delete possibly_undefined_names
;
2714 possibly_undefined_names
= NULL
;
2715 free_dominance_info (CDI_POST_DOMINATORS
);
2716 timevar_pop (TV_TREE_UNINIT
);
2723 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2725 return new pass_late_warn_uninitialized (ctxt
);
2729 execute_early_warn_uninitialized (void)
2731 /* Currently, this pass runs always but
2732 execute_late_warn_uninitialized only runs with optimization. With
2733 optimization we want to warn about possible uninitialized as late
2734 as possible, thus don't do it here. However, without
2735 optimization we need to warn here about "may be uninitialized". */
2736 calculate_dominance_info (CDI_POST_DOMINATORS
);
2738 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2740 /* Post-dominator information cannot be reliably updated. Free it
2743 free_dominance_info (CDI_POST_DOMINATORS
);
2749 const pass_data pass_data_early_warn_uninitialized
=
2751 GIMPLE_PASS
, /* type */
2752 "*early_warn_uninitialized", /* name */
2753 OPTGROUP_NONE
, /* optinfo_flags */
2754 TV_TREE_UNINIT
, /* tv_id */
2755 PROP_ssa
, /* properties_required */
2756 0, /* properties_provided */
2757 0, /* properties_destroyed */
2758 0, /* todo_flags_start */
2759 0, /* todo_flags_finish */
2762 class pass_early_warn_uninitialized
: public gimple_opt_pass
2765 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2766 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2769 /* opt_pass methods: */
2770 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2771 virtual unsigned int execute (function
*)
2773 return execute_early_warn_uninitialized ();
2776 }; // class pass_early_warn_uninitialized
2781 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2783 return new pass_early_warn_uninitialized (ctxt
);