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"
32 #include "fold-const.h"
36 #include "hard-reg-set.h"
39 #include "dominance.h"
41 #include "basic-block.h"
42 #include "gimple-pretty-print.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-expr.h"
49 #include "gimple-iterator.h"
50 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
54 #include "tree-inline.h"
55 #include "tree-pass.h"
56 #include "diagnostic-core.h"
60 /* This implements the pass that does predicate aware warning on uses of
61 possibly uninitialized variables. The pass first collects the set of
62 possibly uninitialized SSA names. For each such name, it walks through
63 all its immediate uses. For each immediate use, it rebuilds the condition
64 expression (the predicate) that guards the use. The predicate is then
65 examined to see if the variable is always defined under that same condition.
66 This is done either by pruning the unrealizable paths that lead to the
67 default definitions or by checking if the predicate set that guards the
68 defining paths is a superset of the use predicate. */
71 /* Pointer set of potentially undefined ssa names, i.e.,
72 ssa names that are defined by phi with operands that
73 are not defined or potentially undefined. */
74 static hash_set
<tree
> *possibly_undefined_names
= 0;
76 /* Bit mask handling macros. */
77 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
78 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
79 #define MASK_EMPTY(mask) (mask == 0)
81 /* Returns the first bit position (starting from LSB)
82 in mask that is non zero. Returns -1 if the mask is empty. */
84 get_mask_first_set_bit (unsigned mask
)
90 while ((mask
& (1 << pos
)) == 0)
95 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
97 /* Return true if T, an SSA_NAME, has an undefined value. */
99 has_undefined_value_p (tree t
)
101 return (ssa_undefined_value_p (t
)
102 || (possibly_undefined_names
103 && possibly_undefined_names
->contains (t
)));
108 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
109 is set on SSA_NAME_VAR. */
112 uninit_undefined_value_p (tree t
) {
113 if (!has_undefined_value_p (t
))
115 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
120 /* Emit warnings for uninitialized variables. This is done in two passes.
122 The first pass notices real uses of SSA names with undefined values.
123 Such uses are unconditionally uninitialized, and we can be certain that
124 such a use is a mistake. This pass is run before most optimizations,
125 so that we catch as many as we can.
127 The second pass follows PHI nodes to find uses that are potentially
128 uninitialized. In this case we can't necessarily prove that the use
129 is really uninitialized. This pass is run after most optimizations,
130 so that we thread as many jumps and possible, and delete as much dead
131 code as possible, in order to reduce false positives. We also look
132 again for plain uninitialized variables, since optimization may have
133 changed conditionally uninitialized to unconditionally uninitialized. */
135 /* Emit a warning for EXPR based on variable VAR at the point in the
136 program T, an SSA_NAME, is used being uninitialized. The exact
137 warning text is in MSGID and DATA is the gimple stmt with info about
138 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
139 gives which argument of the phi node to take the location from. WC
140 is the warning code. */
143 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
144 const char *gmsgid
, void *data
, location_t phiarg_loc
)
146 gimple context
= (gimple
) data
;
147 location_t location
, cfun_loc
;
148 expanded_location xloc
, floc
;
150 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
151 turns in a COMPLEX_EXPR with the not initialized part being
152 set to its previous (undefined) value. */
153 if (is_gimple_assign (context
)
154 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
156 if (!has_undefined_value_p (t
))
159 /* TREE_NO_WARNING either means we already warned, or the front end
160 wishes to suppress the warning. */
162 && (gimple_no_warning_p (context
)
163 || (gimple_assign_single_p (context
)
164 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
165 || TREE_NO_WARNING (expr
))
168 if (context
!= NULL
&& gimple_has_location (context
))
169 location
= gimple_location (context
);
170 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
171 location
= phiarg_loc
;
173 location
= DECL_SOURCE_LOCATION (var
);
174 location
= linemap_resolve_location (line_table
, location
,
175 LRK_SPELLING_LOCATION
,
177 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
178 xloc
= expand_location (location
);
179 floc
= expand_location (cfun_loc
);
180 if (warning_at (location
, wc
, gmsgid
, expr
))
182 TREE_NO_WARNING (expr
) = 1;
184 if (location
== DECL_SOURCE_LOCATION (var
))
186 if (xloc
.file
!= floc
.file
187 || linemap_location_before_p (line_table
,
189 || linemap_location_before_p (line_table
,
190 cfun
->function_end_locus
,
192 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
197 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
199 gimple_stmt_iterator gsi
;
202 FOR_EACH_BB_FN (bb
, cfun
)
204 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
205 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
206 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
208 gimple stmt
= gsi_stmt (gsi
);
213 if (is_gimple_debug (stmt
))
216 /* We only do data flow with SSA_NAMEs, so that's all we
218 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
220 use
= USE_FROM_PTR (use_p
);
222 warn_uninit (OPT_Wuninitialized
, use
,
223 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
224 "%qD is used uninitialized in this function",
225 stmt
, UNKNOWN_LOCATION
);
226 else if (warn_possibly_uninitialized
)
227 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
228 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
229 "%qD may be used uninitialized in this function",
230 stmt
, UNKNOWN_LOCATION
);
233 /* For memory the only cheap thing we can do is see if we
234 have a use of the default def of the virtual operand.
235 ??? Not so cheap would be to use the alias oracle via
236 walk_aliased_vdefs, if we don't find any aliasing vdef
237 warn as is-used-uninitialized, if we don't find an aliasing
238 vdef that kills our use (stmt_kills_ref_p), warn as
239 may-be-used-uninitialized. But this walk is quadratic and
240 so must be limited which means we would miss warning
242 use
= gimple_vuse (stmt
);
244 && gimple_assign_single_p (stmt
)
245 && !gimple_vdef (stmt
)
246 && SSA_NAME_IS_DEFAULT_DEF (use
))
248 tree rhs
= gimple_assign_rhs1 (stmt
);
249 tree base
= get_base_address (rhs
);
251 /* Do not warn if it can be initialized outside this function. */
252 if (TREE_CODE (base
) != VAR_DECL
253 || DECL_HARD_REGISTER (base
)
254 || is_global_var (base
))
258 warn_uninit (OPT_Wuninitialized
, use
,
259 gimple_assign_rhs1 (stmt
), base
,
260 "%qE is used uninitialized in this function",
261 stmt
, UNKNOWN_LOCATION
);
262 else if (warn_possibly_uninitialized
)
263 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
264 gimple_assign_rhs1 (stmt
), base
,
265 "%qE may be used uninitialized in this function",
266 stmt
, UNKNOWN_LOCATION
);
274 /* Checks if the operand OPND of PHI is defined by
275 another phi with one operand defined by this PHI,
276 but the rest operands are all defined. If yes,
277 returns true to skip this this operand as being
278 redundant. Can be enhanced to be more general. */
281 can_skip_redundant_opnd (tree opnd
, gimple phi
)
287 phi_def
= gimple_phi_result (phi
);
288 op_def
= SSA_NAME_DEF_STMT (opnd
);
289 if (gimple_code (op_def
) != GIMPLE_PHI
)
291 n
= gimple_phi_num_args (op_def
);
292 for (i
= 0; i
< n
; ++i
)
294 tree op
= gimple_phi_arg_def (op_def
, i
);
295 if (TREE_CODE (op
) != SSA_NAME
)
297 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
304 /* Returns a bit mask holding the positions of arguments in PHI
305 that have empty (or possibly empty) definitions. */
308 compute_uninit_opnds_pos (gphi
*phi
)
311 unsigned uninit_opnds
= 0;
313 n
= gimple_phi_num_args (phi
);
314 /* Bail out for phi with too many args. */
318 for (i
= 0; i
< n
; ++i
)
320 tree op
= gimple_phi_arg_def (phi
, i
);
321 if (TREE_CODE (op
) == SSA_NAME
322 && uninit_undefined_value_p (op
)
323 && !can_skip_redundant_opnd (op
, phi
))
325 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
327 /* Ignore SSA_NAMEs that appear on abnormal edges
329 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
332 MASK_SET_BIT (uninit_opnds
, i
);
338 /* Find the immediate postdominator PDOM of the specified
339 basic block BLOCK. */
341 static inline basic_block
342 find_pdom (basic_block block
)
344 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
345 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
349 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
351 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
356 /* Find the immediate DOM of the specified
357 basic block BLOCK. */
359 static inline basic_block
360 find_dom (basic_block block
)
362 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
363 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
366 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
368 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
373 /* Returns true if BB1 is postdominating BB2 and BB1 is
374 not a loop exit bb. The loop exit bb check is simple and does
375 not cover all cases. */
378 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
380 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
383 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
389 /* Find the closest postdominator of a specified BB, which is control
392 static inline basic_block
393 find_control_equiv_block (basic_block bb
)
397 pdom
= find_pdom (bb
);
399 /* Skip the postdominating bb that is also loop exit. */
400 if (!is_non_loop_exit_postdominating (pdom
, bb
))
403 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
409 #define MAX_NUM_CHAINS 8
410 #define MAX_CHAIN_LEN 5
411 #define MAX_POSTDOM_CHECK 8
412 #define MAX_SWITCH_CASES 40
414 /* Computes the control dependence chains (paths of edges)
415 for DEP_BB up to the dominating basic block BB (the head node of a
416 chain should be dominated by it). CD_CHAINS is pointer to an
417 array holding the result chains. CUR_CD_CHAIN is the current
418 chain being computed. *NUM_CHAINS is total number of chains. The
419 function returns true if the information is successfully computed,
420 return false if there is no control dependence or not computed. */
423 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
424 vec
<edge
> *cd_chains
,
426 vec
<edge
> *cur_cd_chain
,
432 bool found_cd_chain
= false;
433 size_t cur_chain_len
= 0;
435 if (EDGE_COUNT (bb
->succs
) < 2)
438 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
442 /* Could use a set instead. */
443 cur_chain_len
= cur_cd_chain
->length ();
444 if (cur_chain_len
> MAX_CHAIN_LEN
)
447 for (i
= 0; i
< cur_chain_len
; i
++)
449 edge e
= (*cur_cd_chain
)[i
];
450 /* Cycle detected. */
455 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
458 int post_dom_check
= 0;
459 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
463 cur_cd_chain
->safe_push (e
);
464 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
468 /* Found a direct control dependence. */
469 if (*num_chains
< MAX_NUM_CHAINS
)
471 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
474 found_cd_chain
= true;
475 /* Check path from next edge. */
479 /* Now check if DEP_BB is indirectly control dependent on BB. */
480 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
481 num_chains
, cur_cd_chain
, num_calls
))
483 found_cd_chain
= true;
487 cd_bb
= find_pdom (cd_bb
);
489 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
493 cur_cd_chain
->pop ();
494 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
496 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
498 return found_cd_chain
;
501 /* The type to represent a simple predicate */
503 typedef struct use_def_pred_info
507 enum tree_code cond_code
;
511 /* The type to represent a sequence of predicates grouped
512 with .AND. operation. */
514 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
516 /* The type to represent a sequence of pred_chains grouped
517 with .OR. operation. */
519 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
521 /* Converts the chains of control dependence edges into a set of
522 predicates. A control dependence chain is represented by a vector
523 edges. DEP_CHAINS points to an array of dependence chains.
524 NUM_CHAINS is the size of the chain array. One edge in a dependence
525 chain is mapped to predicate expression represented by pred_info
526 type. One dependence chain is converted to a composite predicate that
527 is the result of AND operation of pred_info mapped to each edge.
528 A composite predicate is presented by a vector of pred_info. On
529 return, *PREDS points to the resulting array of composite predicates.
530 *NUM_PREDS is the number of composite predictes. */
533 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
535 pred_chain_union
*preds
)
537 bool has_valid_pred
= false;
539 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
542 /* Now convert the control dep chain into a set
544 preds
->reserve (num_chains
);
546 for (i
= 0; i
< num_chains
; i
++)
548 vec
<edge
> one_cd_chain
= dep_chains
[i
];
550 has_valid_pred
= false;
551 pred_chain t_chain
= vNULL
;
552 for (j
= 0; j
< one_cd_chain
.length (); j
++)
555 gimple_stmt_iterator gsi
;
556 basic_block guard_bb
;
562 gsi
= gsi_last_bb (guard_bb
);
565 has_valid_pred
= false;
568 cond_stmt
= gsi_stmt (gsi
);
569 if (is_gimple_call (cond_stmt
)
570 && EDGE_COUNT (e
->src
->succs
) >= 2)
572 /* Ignore EH edge. Can add assertion
573 on the other edge's flag. */
576 /* Skip if there is essentially one succesor. */
577 if (EDGE_COUNT (e
->src
->succs
) == 2)
583 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
585 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
594 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
596 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
597 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
598 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
599 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
600 t_chain
.safe_push (one_pred
);
601 has_valid_pred
= true;
603 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
605 /* Avoid quadratic behavior. */
606 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
608 has_valid_pred
= false;
611 /* Find the case label. */
614 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
616 tree tl
= gimple_switch_label (gs
, idx
);
617 if (e
->dest
== label_to_block (CASE_LABEL (tl
)))
628 /* If more than one label reaches this block or the case
629 label doesn't have a single value (like the default one)
633 || (CASE_HIGH (l
) && !operand_equal_p (CASE_LOW (l
),
636 has_valid_pred
= false;
639 one_pred
.pred_lhs
= gimple_switch_index (gs
);
640 one_pred
.pred_rhs
= CASE_LOW (l
);
641 one_pred
.cond_code
= EQ_EXPR
;
642 one_pred
.invert
= false;
643 t_chain
.safe_push (one_pred
);
644 has_valid_pred
= true;
648 has_valid_pred
= false;
656 preds
->safe_push (t_chain
);
658 return has_valid_pred
;
661 /* Computes all control dependence chains for USE_BB. The control
662 dependence chains are then converted to an array of composite
663 predicates pointed to by PREDS. PHI_BB is the basic block of
664 the phi whose result is used in USE_BB. */
667 find_predicates (pred_chain_union
*preds
,
671 size_t num_chains
= 0, i
;
673 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
674 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
675 bool has_valid_pred
= false;
676 basic_block cd_root
= 0;
678 /* First find the closest bb that is control equivalent to PHI_BB
679 that also dominates USE_BB. */
681 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
683 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
684 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
685 cd_root
= ctrl_eq_bb
;
690 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
691 &cur_chain
, &num_calls
);
694 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
695 for (i
= 0; i
< num_chains
; i
++)
696 dep_chains
[i
].release ();
697 return has_valid_pred
;
700 /* Computes the set of incoming edges of PHI that have non empty
701 definitions of a phi chain. The collection will be done
702 recursively on operands that are defined by phis. CD_ROOT
703 is the control dependence root. *EDGES holds the result, and
704 VISITED_PHIS is a pointer set for detecting cycles. */
707 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
709 hash_set
<gimple
> *visited_phis
)
715 if (visited_phis
->add (phi
))
718 n
= gimple_phi_num_args (phi
);
719 for (i
= 0; i
< n
; i
++)
721 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
722 opnd
= gimple_phi_arg_def (phi
, i
);
724 if (TREE_CODE (opnd
) != SSA_NAME
)
726 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
728 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
729 print_gimple_stmt (dump_file
, phi
, 0, 0);
731 edges
->safe_push (opnd_edge
);
735 gimple def
= SSA_NAME_DEF_STMT (opnd
);
737 if (gimple_code (def
) == GIMPLE_PHI
738 && dominated_by_p (CDI_DOMINATORS
,
739 gimple_bb (def
), cd_root
))
740 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
742 else if (!uninit_undefined_value_p (opnd
))
744 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
746 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
747 print_gimple_stmt (dump_file
, phi
, 0, 0);
749 edges
->safe_push (opnd_edge
);
755 /* For each use edge of PHI, computes all control dependence chains.
756 The control dependence chains are then converted to an array of
757 composite predicates pointed to by PREDS. */
760 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
762 size_t num_chains
= 0, i
, n
;
763 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
764 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
765 vec
<edge
> def_edges
= vNULL
;
766 bool has_valid_pred
= false;
767 basic_block phi_bb
, cd_root
= 0;
769 phi_bb
= gimple_bb (phi
);
770 /* First find the closest dominating bb to be
771 the control dependence root */
772 cd_root
= find_dom (phi_bb
);
776 hash_set
<gimple
> visited_phis
;
777 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
779 n
= def_edges
.length ();
783 for (i
= 0; i
< n
; i
++)
789 opnd_edge
= def_edges
[i
];
790 prev_nc
= num_chains
;
791 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
792 &num_chains
, &cur_chain
, &num_calls
);
794 /* Now update the newly added chains with
795 the phi operand edge: */
796 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
798 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
799 dep_chains
[num_chains
++] = vNULL
;
800 for (j
= prev_nc
; j
< num_chains
; j
++)
801 dep_chains
[j
].safe_push (opnd_edge
);
806 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
807 for (i
= 0; i
< num_chains
; i
++)
808 dep_chains
[i
].release ();
809 return has_valid_pred
;
812 /* Dumps the predicates (PREDS) for USESTMT. */
815 dump_predicates (gimple usestmt
, pred_chain_union preds
,
819 pred_chain one_pred_chain
= vNULL
;
820 fprintf (dump_file
, "%s", msg
);
821 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
822 fprintf (dump_file
, "is guarded by :\n\n");
823 size_t num_preds
= preds
.length ();
824 /* Do some dumping here: */
825 for (i
= 0; i
< num_preds
; i
++)
829 one_pred_chain
= preds
[i
];
830 np
= one_pred_chain
.length ();
832 for (j
= 0; j
< np
; j
++)
834 pred_info one_pred
= one_pred_chain
[j
];
836 fprintf (dump_file
, " (.NOT.) ");
837 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
838 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
839 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
841 fprintf (dump_file
, " (.AND.) ");
843 fprintf (dump_file
, "\n");
845 if (i
< num_preds
- 1)
846 fprintf (dump_file
, "(.OR.)\n");
848 fprintf (dump_file
, "\n\n");
852 /* Destroys the predicate set *PREDS. */
855 destroy_predicate_vecs (pred_chain_union preds
)
859 size_t n
= preds
.length ();
860 for (i
= 0; i
< n
; i
++)
866 /* Computes the 'normalized' conditional code with operand
867 swapping and condition inversion. */
869 static enum tree_code
870 get_cmp_code (enum tree_code orig_cmp_code
,
871 bool swap_cond
, bool invert
)
873 enum tree_code tc
= orig_cmp_code
;
876 tc
= swap_tree_comparison (orig_cmp_code
);
878 tc
= invert_tree_comparison (tc
, false);
895 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
896 all values in the range satisfies (x CMPC BOUNDARY) == true. */
899 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
901 bool inverted
= false;
905 /* Only handle integer constant here. */
906 if (TREE_CODE (val
) != INTEGER_CST
907 || TREE_CODE (boundary
) != INTEGER_CST
)
910 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
912 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
915 cmpc
= invert_tree_comparison (cmpc
, false);
922 result
= tree_int_cst_equal (val
, boundary
);
923 else if (cmpc
== LT_EXPR
)
924 result
= tree_int_cst_lt (val
, boundary
);
927 gcc_assert (cmpc
== LE_EXPR
);
928 result
= tree_int_cst_le (val
, boundary
);
934 result
= tree_int_cst_equal (val
, boundary
);
935 else if (cmpc
== LT_EXPR
)
936 result
= tree_int_cst_lt (val
, boundary
);
939 gcc_assert (cmpc
== LE_EXPR
);
940 result
= (tree_int_cst_equal (val
, boundary
)
941 || tree_int_cst_lt (val
, boundary
));
951 /* Returns true if PRED is common among all the predicate
952 chains (PREDS) (and therefore can be factored out).
953 NUM_PRED_CHAIN is the size of array PREDS. */
956 find_matching_predicate_in_rest_chains (pred_info pred
,
957 pred_chain_union preds
,
958 size_t num_pred_chains
)
963 if (num_pred_chains
== 1)
966 for (i
= 1; i
< num_pred_chains
; i
++)
969 pred_chain one_chain
= preds
[i
];
970 n
= one_chain
.length ();
971 for (j
= 0; j
< n
; j
++)
973 pred_info pred2
= one_chain
[j
];
974 /* Can relax the condition comparison to not
975 use address comparison. However, the most common
976 case is that multiple control dependent paths share
977 a common path prefix, so address comparison should
980 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
981 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
982 && pred2
.invert
== pred
.invert
)
994 /* Forward declaration. */
996 is_use_properly_guarded (gimple use_stmt
,
999 unsigned uninit_opnds
,
1000 hash_set
<gphi
*> *visited_phis
);
1002 /* Returns true if all uninitialized opnds are pruned. Returns false
1003 otherwise. PHI is the phi node with uninitialized operands,
1004 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1005 FLAG_DEF is the statement defining the flag guarding the use of the
1006 PHI output, BOUNDARY_CST is the const value used in the predicate
1007 associated with the flag, CMP_CODE is the comparison code used in
1008 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1009 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1015 flag_1 = phi <0, 1> // (1)
1016 var_1 = phi <undef, some_val>
1020 flag_2 = phi <0, flag_1, flag_1> // (2)
1021 var_2 = phi <undef, var_1, var_1>
1028 Because some flag arg in (1) is not constant, if we do not look into the
1029 flag phis recursively, it is conservatively treated as unknown and var_1
1030 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
1031 a false warning will be emitted. Checking recursively into (1), the compiler can
1032 find out that only some_val (which is defined) can flow into (3) which is OK.
1037 prune_uninit_phi_opnds_in_unrealizable_paths (gphi
*phi
,
1038 unsigned uninit_opnds
,
1041 enum tree_code cmp_code
,
1042 hash_set
<gphi
*> *visited_phis
,
1043 bitmap
*visited_flag_phis
)
1047 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
1051 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1054 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1055 if (!is_gimple_constant (flag_arg
))
1057 gphi
*flag_arg_def
, *phi_arg_def
;
1059 unsigned uninit_opnds_arg_phi
;
1061 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1063 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1067 phi_arg
= gimple_phi_arg_def (phi
, i
);
1068 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1071 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1075 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1078 if (!*visited_flag_phis
)
1079 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1081 if (bitmap_bit_p (*visited_flag_phis
,
1082 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1085 bitmap_set_bit (*visited_flag_phis
,
1086 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1088 /* Now recursively prune the uninitialized phi args. */
1089 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1090 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1091 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1092 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1095 bitmap_clear_bit (*visited_flag_phis
,
1096 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1100 /* Now check if the constant is in the guarded range. */
1101 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1106 /* Now that we know that this undefined edge is not
1107 pruned. If the operand is defined by another phi,
1108 we can further prune the incoming edges of that
1109 phi by checking the predicates of this operands. */
1111 opnd
= gimple_phi_arg_def (phi
, i
);
1112 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1113 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1116 unsigned uninit_opnds2
1117 = compute_uninit_opnds_pos (opnd_def_phi
);
1118 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
1119 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1120 if (!is_use_properly_guarded (phi
,
1135 /* A helper function that determines if the predicate set
1136 of the use is not overlapping with that of the uninit paths.
1137 The most common senario of guarded use is in Example 1:
1150 The real world examples are usually more complicated, but similar
1151 and usually result from inlining:
1153 bool init_func (int * x)
1172 Another possible use scenario is in the following trivial example:
1184 Predicate analysis needs to compute the composite predicate:
1186 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1187 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1188 (the predicate chain for phi operand defs can be computed
1189 starting from a bb that is control equivalent to the phi's
1190 bb and is dominating the operand def.)
1192 and check overlapping:
1193 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1196 This implementation provides framework that can handle
1197 scenarios. (Note that many simple cases are handled properly
1198 without the predicate analysis -- this is due to jump threading
1199 transformation which eliminates the merge point thus makes
1200 path sensitive analysis unnecessary.)
1202 NUM_PREDS is the number is the number predicate chains, PREDS is
1203 the array of chains, PHI is the phi node whose incoming (undefined)
1204 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1205 uninit operand positions. VISITED_PHIS is the pointer set of phi
1206 stmts being checked. */
1210 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1211 gphi
*phi
, unsigned uninit_opnds
,
1212 hash_set
<gphi
*> *visited_phis
)
1215 gimple flag_def
= 0;
1216 tree boundary_cst
= 0;
1217 enum tree_code cmp_code
;
1218 bool swap_cond
= false;
1219 bool invert
= false;
1220 pred_chain the_pred_chain
= vNULL
;
1221 bitmap visited_flag_phis
= NULL
;
1222 bool all_pruned
= false;
1223 size_t num_preds
= preds
.length ();
1225 gcc_assert (num_preds
> 0);
1226 /* Find within the common prefix of multiple predicate chains
1227 a predicate that is a comparison of a flag variable against
1229 the_pred_chain
= preds
[0];
1230 n
= the_pred_chain
.length ();
1231 for (i
= 0; i
< n
; i
++)
1233 tree cond_lhs
, cond_rhs
, flag
= 0;
1235 pred_info the_pred
= the_pred_chain
[i
];
1237 invert
= the_pred
.invert
;
1238 cond_lhs
= the_pred
.pred_lhs
;
1239 cond_rhs
= the_pred
.pred_rhs
;
1240 cmp_code
= the_pred
.cond_code
;
1242 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1243 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1245 boundary_cst
= cond_rhs
;
1248 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1249 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1251 boundary_cst
= cond_lhs
;
1259 flag_def
= SSA_NAME_DEF_STMT (flag
);
1264 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1265 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1266 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1276 /* Now check all the uninit incoming edge has a constant flag value
1277 that is in conflict with the use guard/predicate. */
1278 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1280 if (cmp_code
== ERROR_MARK
)
1283 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1285 as_a
<gphi
*> (flag_def
),
1289 &visited_flag_phis
);
1291 if (visited_flag_phis
)
1292 BITMAP_FREE (visited_flag_phis
);
1297 /* The helper function returns true if two predicates X1 and X2
1298 are equivalent. It assumes the expressions have already
1299 properly re-associated. */
1302 pred_equal_p (pred_info x1
, pred_info x2
)
1304 enum tree_code c1
, c2
;
1305 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1306 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1310 if (x1
.invert
!= x2
.invert
)
1311 c2
= invert_tree_comparison (x2
.cond_code
, false);
1318 /* Returns true if the predication is testing !=. */
1321 is_neq_relop_p (pred_info pred
)
1324 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1325 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1328 /* Returns true if pred is of the form X != 0. */
1331 is_neq_zero_form_p (pred_info pred
)
1333 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1334 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1339 /* The helper function returns true if two predicates X1
1340 is equivalent to X2 != 0. */
1343 pred_expr_equal_p (pred_info x1
, tree x2
)
1345 if (!is_neq_zero_form_p (x1
))
1348 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1351 /* Returns true of the domain of single predicate expression
1352 EXPR1 is a subset of that of EXPR2. Returns false if it
1353 can not be proved. */
1356 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1358 enum tree_code code1
, code2
;
1360 if (pred_equal_p (expr1
, expr2
))
1363 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1364 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1367 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1370 code1
= expr1
.cond_code
;
1372 code1
= invert_tree_comparison (code1
, false);
1373 code2
= expr2
.cond_code
;
1375 code2
= invert_tree_comparison (code2
, false);
1377 if ((code1
== EQ_EXPR
|| code1
== BIT_AND_EXPR
)
1378 && code2
== BIT_AND_EXPR
)
1379 return wi::eq_p (expr1
.pred_rhs
,
1380 wi::bit_and (expr1
.pred_rhs
, expr2
.pred_rhs
));
1382 if (code1
!= code2
&& code2
!= NE_EXPR
)
1385 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1391 /* Returns true if the domain of PRED1 is a subset
1392 of that of PRED2. Returns false if it can not be proved so. */
1395 is_pred_chain_subset_of (pred_chain pred1
,
1398 size_t np1
, np2
, i1
, i2
;
1400 np1
= pred1
.length ();
1401 np2
= pred2
.length ();
1403 for (i2
= 0; i2
< np2
; i2
++)
1406 pred_info info2
= pred2
[i2
];
1407 for (i1
= 0; i1
< np1
; i1
++)
1409 pred_info info1
= pred1
[i1
];
1410 if (is_pred_expr_subset_of (info1
, info2
))
1422 /* Returns true if the domain defined by
1423 one pred chain ONE_PRED is a subset of the domain
1424 of *PREDS. It returns false if ONE_PRED's domain is
1425 not a subset of any of the sub-domains of PREDS
1426 (corresponding to each individual chains in it), even
1427 though it may be still be a subset of whole domain
1428 of PREDS which is the union (ORed) of all its subdomains.
1429 In other words, the result is conservative. */
1432 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1435 size_t n
= preds
.length ();
1437 for (i
= 0; i
< n
; i
++)
1439 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1446 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1447 true if the domain defined by PREDS1 is a superset
1448 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1449 PREDS2 respectively. The implementation chooses not to build
1450 generic trees (and relying on the folding capability of the
1451 compiler), but instead performs brute force comparison of
1452 individual predicate chains (won't be a compile time problem
1453 as the chains are pretty short). When the function returns
1454 false, it does not necessarily mean *PREDS1 is not a superset
1455 of *PREDS2, but mean it may not be so since the analysis can
1456 not prove it. In such cases, false warnings may still be
1460 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1463 pred_chain one_pred_chain
= vNULL
;
1465 n2
= preds2
.length ();
1467 for (i
= 0; i
< n2
; i
++)
1469 one_pred_chain
= preds2
[i
];
1470 if (!is_included_in (one_pred_chain
, preds1
))
1477 /* Returns true if TC is AND or OR. */
1480 is_and_or_or_p (enum tree_code tc
, tree type
)
1482 return (tc
== BIT_IOR_EXPR
1483 || (tc
== BIT_AND_EXPR
1484 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1487 /* Returns true if X1 is the negate of X2. */
1490 pred_neg_p (pred_info x1
, pred_info x2
)
1492 enum tree_code c1
, c2
;
1493 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1494 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1498 if (x1
.invert
== x2
.invert
)
1499 c2
= invert_tree_comparison (x2
.cond_code
, false);
1506 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1507 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1508 3) X OR (!X AND Y) is equivalent to (X OR Y);
1509 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1511 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1514 PREDS is the predicate chains, and N is the number of chains. */
1516 /* Helper function to implement rule 1 above. ONE_CHAIN is
1517 the AND predication to be simplified. */
1520 simplify_pred (pred_chain
*one_chain
)
1523 bool simplified
= false;
1524 pred_chain s_chain
= vNULL
;
1526 n
= one_chain
->length ();
1528 for (i
= 0; i
< n
; i
++)
1530 pred_info
*a_pred
= &(*one_chain
)[i
];
1532 if (!a_pred
->pred_lhs
)
1534 if (!is_neq_zero_form_p (*a_pred
))
1537 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1538 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1540 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1542 for (j
= 0; j
< n
; j
++)
1544 pred_info
*b_pred
= &(*one_chain
)[j
];
1546 if (!b_pred
->pred_lhs
)
1548 if (!is_neq_zero_form_p (*b_pred
))
1551 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1552 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1554 /* Mark a_pred for removal. */
1555 a_pred
->pred_lhs
= NULL
;
1556 a_pred
->pred_rhs
= NULL
;
1567 for (i
= 0; i
< n
; i
++)
1569 pred_info
*a_pred
= &(*one_chain
)[i
];
1570 if (!a_pred
->pred_lhs
)
1572 s_chain
.safe_push (*a_pred
);
1575 one_chain
->release ();
1576 *one_chain
= s_chain
;
1579 /* The helper function implements the rule 2 for the
1582 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1585 simplify_preds_2 (pred_chain_union
*preds
)
1588 bool simplified
= false;
1589 pred_chain_union s_preds
= vNULL
;
1591 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1592 (X AND Y) OR (X AND !Y) is equivalent to X. */
1594 n
= preds
->length ();
1595 for (i
= 0; i
< n
; i
++)
1598 pred_chain
*a_chain
= &(*preds
)[i
];
1600 if (a_chain
->length () != 2)
1606 for (j
= 0; j
< n
; j
++)
1608 pred_chain
*b_chain
;
1614 b_chain
= &(*preds
)[j
];
1615 if (b_chain
->length () != 2)
1621 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1624 a_chain
->release ();
1625 b_chain
->release ();
1626 b_chain
->safe_push (x
);
1630 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1633 a_chain
->release ();
1634 b_chain
->release ();
1635 b_chain
->safe_push (y
);
1641 /* Now clean up the chain. */
1644 for (i
= 0; i
< n
; i
++)
1646 if ((*preds
)[i
].is_empty ())
1648 s_preds
.safe_push ((*preds
)[i
]);
1658 /* The helper function implements the rule 2 for the
1661 3) x OR (!x AND y) is equivalent to x OR y. */
1664 simplify_preds_3 (pred_chain_union
*preds
)
1667 bool simplified
= false;
1669 /* Now iteratively simplify X OR (!X AND Z ..)
1670 into X OR (Z ...). */
1672 n
= preds
->length ();
1676 for (i
= 0; i
< n
; i
++)
1679 pred_chain
*a_chain
= &(*preds
)[i
];
1681 if (a_chain
->length () != 1)
1686 for (j
= 0; j
< n
; j
++)
1688 pred_chain
*b_chain
;
1695 b_chain
= &(*preds
)[j
];
1696 if (b_chain
->length () < 2)
1699 for (k
= 0; k
< b_chain
->length (); k
++)
1702 if (pred_neg_p (x
, x2
))
1704 b_chain
->unordered_remove (k
);
1714 /* The helper function implements the rule 4 for the
1717 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1718 (x != 0 ANd y != 0). */
1721 simplify_preds_4 (pred_chain_union
*preds
)
1724 bool simplified
= false;
1725 pred_chain_union s_preds
= vNULL
;
1728 n
= preds
->length ();
1729 for (i
= 0; i
< n
; i
++)
1732 pred_chain
*a_chain
= &(*preds
)[i
];
1734 if (a_chain
->length () != 1)
1739 if (!is_neq_zero_form_p (z
))
1742 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1743 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1746 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1749 for (j
= 0; j
< n
; j
++)
1751 pred_chain
*b_chain
;
1757 b_chain
= &(*preds
)[j
];
1758 if (b_chain
->length () != 2)
1763 if (!is_neq_zero_form_p (x2
)
1764 || !is_neq_zero_form_p (y2
))
1767 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1768 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1769 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1770 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1773 a_chain
->release ();
1779 /* Now clean up the chain. */
1782 for (i
= 0; i
< n
; i
++)
1784 if ((*preds
)[i
].is_empty ())
1786 s_preds
.safe_push ((*preds
)[i
]);
1797 /* This function simplifies predicates in PREDS. */
1800 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1803 bool changed
= false;
1805 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1807 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1808 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1811 for (i
= 0; i
< preds
->length (); i
++)
1812 simplify_pred (&(*preds
)[i
]);
1814 n
= preds
->length ();
1821 if (simplify_preds_2 (preds
))
1824 /* Now iteratively simplify X OR (!X AND Z ..)
1825 into X OR (Z ...). */
1826 if (simplify_preds_3 (preds
))
1829 if (simplify_preds_4 (preds
))
1837 /* This is a helper function which attempts to normalize predicate chains
1838 by following UD chains. It basically builds up a big tree of either IOR
1839 operations or AND operations, and convert the IOR tree into a
1840 pred_chain_union or BIT_AND tree into a pred_chain.
1850 then _t != 0 will be normalized into a pred_chain_union
1852 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1862 then _t != 0 will be normalized into a pred_chain:
1863 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1867 /* This is a helper function that stores a PRED into NORM_PREDS. */
1870 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1872 pred_chain pred_chain
= vNULL
;
1873 pred_chain
.safe_push (pred
);
1874 norm_preds
->safe_push (pred_chain
);
1877 /* A helper function that creates a predicate of the form
1878 OP != 0 and push it WORK_LIST. */
1881 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1882 hash_set
<tree
> *mark_set
)
1884 if (mark_set
->contains (op
))
1889 arg_pred
.pred_lhs
= op
;
1890 arg_pred
.pred_rhs
= integer_zero_node
;
1891 arg_pred
.cond_code
= NE_EXPR
;
1892 arg_pred
.invert
= false;
1893 work_list
->safe_push (arg_pred
);
1896 /* A helper that generates a pred_info from a gimple assignment
1897 CMP_ASSIGN with comparison rhs. */
1900 get_pred_info_from_cmp (gimple cmp_assign
)
1903 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1904 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1905 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1906 n_pred
.invert
= false;
1910 /* Returns true if the PHI is a degenerated phi with
1911 all args with the same value (relop). In that case, *PRED
1912 will be updated to that value. */
1915 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1922 n
= gimple_phi_num_args (phi
);
1923 op0
= gimple_phi_arg_def (phi
, 0);
1925 if (TREE_CODE (op0
) != SSA_NAME
)
1928 def0
= SSA_NAME_DEF_STMT (op0
);
1929 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1931 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1934 pred0
= get_pred_info_from_cmp (def0
);
1936 for (i
= 1; i
< n
; ++i
)
1940 tree op
= gimple_phi_arg_def (phi
, i
);
1942 if (TREE_CODE (op
) != SSA_NAME
)
1945 def
= SSA_NAME_DEF_STMT (op
);
1946 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1948 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1951 pred
= get_pred_info_from_cmp (def
);
1952 if (!pred_equal_p (pred
, pred0
))
1960 /* Normalize one predicate PRED
1961 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1962 2) otherwise if PRED is of the form x != 0, follow x's definition
1963 and put normalized predicates into WORK_LIST. */
1966 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1967 pred_chain
*norm_chain
,
1969 enum tree_code and_or_code
,
1970 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1971 hash_set
<tree
> *mark_set
)
1973 if (!is_neq_zero_form_p (pred
))
1975 if (and_or_code
== BIT_IOR_EXPR
)
1976 push_pred (norm_preds
, pred
);
1978 norm_chain
->safe_push (pred
);
1982 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1984 if (gimple_code (def_stmt
) == GIMPLE_PHI
1985 && is_degenerated_phi (def_stmt
, &pred
))
1986 work_list
->safe_push (pred
);
1987 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1988 && and_or_code
== BIT_IOR_EXPR
)
1991 n
= gimple_phi_num_args (def_stmt
);
1993 /* If we see non zero constant, we should punt. The predicate
1994 * should be one guarding the phi edge. */
1995 for (i
= 0; i
< n
; ++i
)
1997 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1998 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
2000 push_pred (norm_preds
, pred
);
2005 for (i
= 0; i
< n
; ++i
)
2007 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2008 if (integer_zerop (op
))
2011 push_to_worklist (op
, work_list
, mark_set
);
2014 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2016 if (and_or_code
== BIT_IOR_EXPR
)
2017 push_pred (norm_preds
, pred
);
2019 norm_chain
->safe_push (pred
);
2021 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2023 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2024 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2026 /* But treat x & 3 as condition. */
2027 if (and_or_code
== BIT_AND_EXPR
)
2030 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2031 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2032 n_pred
.cond_code
= and_or_code
;
2033 n_pred
.invert
= false;
2034 norm_chain
->safe_push (n_pred
);
2039 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2040 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2043 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2046 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2047 if (and_or_code
== BIT_IOR_EXPR
)
2048 push_pred (norm_preds
, n_pred
);
2050 norm_chain
->safe_push (n_pred
);
2054 if (and_or_code
== BIT_IOR_EXPR
)
2055 push_pred (norm_preds
, pred
);
2057 norm_chain
->safe_push (pred
);
2061 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2064 normalize_one_pred (pred_chain_union
*norm_preds
,
2067 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2068 enum tree_code and_or_code
= ERROR_MARK
;
2069 pred_chain norm_chain
= vNULL
;
2071 if (!is_neq_zero_form_p (pred
))
2073 push_pred (norm_preds
, pred
);
2077 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2078 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2079 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2080 if (and_or_code
!= BIT_IOR_EXPR
2081 && and_or_code
!= BIT_AND_EXPR
)
2083 if (TREE_CODE_CLASS (and_or_code
)
2086 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2087 push_pred (norm_preds
, n_pred
);
2090 push_pred (norm_preds
, pred
);
2094 work_list
.safe_push (pred
);
2095 hash_set
<tree
> mark_set
;
2097 while (!work_list
.is_empty ())
2099 pred_info a_pred
= work_list
.pop ();
2100 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2101 and_or_code
, &work_list
, &mark_set
);
2103 if (and_or_code
== BIT_AND_EXPR
)
2104 norm_preds
->safe_push (norm_chain
);
2106 work_list
.release ();
2110 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2111 pred_chain one_chain
)
2113 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2114 hash_set
<tree
> mark_set
;
2115 pred_chain norm_chain
= vNULL
;
2118 for (i
= 0; i
< one_chain
.length (); i
++)
2120 work_list
.safe_push (one_chain
[i
]);
2121 mark_set
.add (one_chain
[i
].pred_lhs
);
2124 while (!work_list
.is_empty ())
2126 pred_info a_pred
= work_list
.pop ();
2127 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2128 BIT_AND_EXPR
, &work_list
, &mark_set
);
2131 norm_preds
->safe_push (norm_chain
);
2132 work_list
.release ();
2135 /* Normalize predicate chains PREDS and returns the normalized one. */
2137 static pred_chain_union
2138 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2140 pred_chain_union norm_preds
= vNULL
;
2141 size_t n
= preds
.length ();
2144 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2146 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2147 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2150 for (i
= 0; i
< n
; i
++)
2152 if (preds
[i
].length () != 1)
2153 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2156 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2157 preds
[i
].release ();
2163 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2164 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2172 /* Computes the predicates that guard the use and checks
2173 if the incoming paths that have empty (or possibly
2174 empty) definition can be pruned/filtered. The function returns
2175 true if it can be determined that the use of PHI's def in
2176 USE_STMT is guarded with a predicate set not overlapping with
2177 predicate sets of all runtime paths that do not have a definition.
2178 Returns false if it is not or it can not be determined. USE_BB is
2179 the bb of the use (for phi operand use, the bb is not the bb of
2180 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2181 is a bit vector. If an operand of PHI is uninitialized, the
2182 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2183 set of phis being visted. */
2186 is_use_properly_guarded (gimple use_stmt
,
2189 unsigned uninit_opnds
,
2190 hash_set
<gphi
*> *visited_phis
)
2193 pred_chain_union preds
= vNULL
;
2194 pred_chain_union def_preds
= vNULL
;
2195 bool has_valid_preds
= false;
2196 bool is_properly_guarded
= false;
2198 if (visited_phis
->add (phi
))
2201 phi_bb
= gimple_bb (phi
);
2203 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2206 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2208 if (!has_valid_preds
)
2210 destroy_predicate_vecs (preds
);
2214 /* Try to prune the dead incoming phi edges. */
2216 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2219 if (is_properly_guarded
)
2221 destroy_predicate_vecs (preds
);
2225 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2227 if (!has_valid_preds
)
2229 destroy_predicate_vecs (preds
);
2230 destroy_predicate_vecs (def_preds
);
2234 simplify_preds (&preds
, use_stmt
, true);
2235 preds
= normalize_preds (preds
, use_stmt
, true);
2237 simplify_preds (&def_preds
, phi
, false);
2238 def_preds
= normalize_preds (def_preds
, phi
, false);
2240 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2242 destroy_predicate_vecs (preds
);
2243 destroy_predicate_vecs (def_preds
);
2244 return is_properly_guarded
;
2247 /* Searches through all uses of a potentially
2248 uninitialized variable defined by PHI and returns a use
2249 statement if the use is not properly guarded. It returns
2250 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2251 holding the position(s) of uninit PHI operands. WORKLIST
2252 is the vector of candidate phis that may be updated by this
2253 function. ADDED_TO_WORKLIST is the pointer set tracking
2254 if the new phi is already in the worklist. */
2257 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2258 vec
<gphi
*> *worklist
,
2259 hash_set
<gphi
*> *added_to_worklist
)
2262 use_operand_p use_p
;
2264 imm_use_iterator iter
;
2266 phi_result
= gimple_phi_result (phi
);
2268 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2272 use_stmt
= USE_STMT (use_p
);
2273 if (is_gimple_debug (use_stmt
))
2276 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2277 use_bb
= gimple_phi_arg_edge (use_phi
,
2278 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2280 use_bb
= gimple_bb (use_stmt
);
2282 hash_set
<gphi
*> visited_phis
;
2283 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2289 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2290 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2292 /* Found one real use, return. */
2293 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2296 /* Found a phi use that is not guarded,
2297 add the phi to the worklist. */
2298 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2302 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2303 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2306 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2307 possibly_undefined_names
->add (phi_result
);
2314 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2315 and gives warning if there exists a runtime path from the entry to a
2316 use of the PHI def that does not contain a definition. In other words,
2317 the warning is on the real use. The more dead paths that can be pruned
2318 by the compiler, the fewer false positives the warning is. WORKLIST
2319 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2320 a pointer set tracking if the new phi is added to the worklist or not. */
2323 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2324 hash_set
<gphi
*> *added_to_worklist
)
2326 unsigned uninit_opnds
;
2327 gimple uninit_use_stmt
= 0;
2332 /* Don't look at virtual operands. */
2333 if (virtual_operand_p (gimple_phi_result (phi
)))
2336 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2338 if (MASK_EMPTY (uninit_opnds
))
2341 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2343 fprintf (dump_file
, "[CHECK]: examining phi: ");
2344 print_gimple_stmt (dump_file
, phi
, 0, 0);
2347 /* Now check if we have any use of the value without proper guard. */
2348 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2349 worklist
, added_to_worklist
);
2351 /* All uses are properly guarded. */
2352 if (!uninit_use_stmt
)
2355 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2356 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2357 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2359 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2360 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2362 loc
= UNKNOWN_LOCATION
;
2363 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2364 SSA_NAME_VAR (uninit_op
),
2365 "%qD may be used uninitialized in this function",
2366 uninit_use_stmt
, loc
);
2371 gate_warn_uninitialized (void)
2373 return warn_uninitialized
|| warn_maybe_uninitialized
;
2378 const pass_data pass_data_late_warn_uninitialized
=
2380 GIMPLE_PASS
, /* type */
2381 "uninit", /* name */
2382 OPTGROUP_NONE
, /* optinfo_flags */
2383 TV_NONE
, /* tv_id */
2384 PROP_ssa
, /* properties_required */
2385 0, /* properties_provided */
2386 0, /* properties_destroyed */
2387 0, /* todo_flags_start */
2388 0, /* todo_flags_finish */
2391 class pass_late_warn_uninitialized
: public gimple_opt_pass
2394 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2395 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2398 /* opt_pass methods: */
2399 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2400 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2401 virtual unsigned int execute (function
*);
2403 }; // class pass_late_warn_uninitialized
2406 pass_late_warn_uninitialized::execute (function
*fun
)
2410 vec
<gphi
*> worklist
= vNULL
;
2412 calculate_dominance_info (CDI_DOMINATORS
);
2413 calculate_dominance_info (CDI_POST_DOMINATORS
);
2414 /* Re-do the plain uninitialized variable check, as optimization may have
2415 straightened control flow. Do this first so that we don't accidentally
2416 get a "may be" warning when we'd have seen an "is" warning later. */
2417 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2419 timevar_push (TV_TREE_UNINIT
);
2421 possibly_undefined_names
= new hash_set
<tree
>;
2422 hash_set
<gphi
*> added_to_worklist
;
2424 /* Initialize worklist */
2425 FOR_EACH_BB_FN (bb
, fun
)
2426 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2428 gphi
*phi
= gsi
.phi ();
2431 n
= gimple_phi_num_args (phi
);
2433 /* Don't look at virtual operands. */
2434 if (virtual_operand_p (gimple_phi_result (phi
)))
2437 for (i
= 0; i
< n
; ++i
)
2439 tree op
= gimple_phi_arg_def (phi
, i
);
2440 if (TREE_CODE (op
) == SSA_NAME
2441 && uninit_undefined_value_p (op
))
2443 worklist
.safe_push (phi
);
2444 added_to_worklist
.add (phi
);
2445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2447 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2448 print_gimple_stmt (dump_file
, phi
, 0, 0);
2455 while (worklist
.length () != 0)
2458 cur_phi
= worklist
.pop ();
2459 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2462 worklist
.release ();
2463 delete possibly_undefined_names
;
2464 possibly_undefined_names
= NULL
;
2465 free_dominance_info (CDI_POST_DOMINATORS
);
2466 timevar_pop (TV_TREE_UNINIT
);
2473 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2475 return new pass_late_warn_uninitialized (ctxt
);
2480 execute_early_warn_uninitialized (void)
2482 /* Currently, this pass runs always but
2483 execute_late_warn_uninitialized only runs with optimization. With
2484 optimization we want to warn about possible uninitialized as late
2485 as possible, thus don't do it here. However, without
2486 optimization we need to warn here about "may be uninitialized". */
2487 calculate_dominance_info (CDI_POST_DOMINATORS
);
2489 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2491 /* Post-dominator information can not be reliably updated. Free it
2494 free_dominance_info (CDI_POST_DOMINATORS
);
2501 const pass_data pass_data_early_warn_uninitialized
=
2503 GIMPLE_PASS
, /* type */
2504 "*early_warn_uninitialized", /* name */
2505 OPTGROUP_NONE
, /* optinfo_flags */
2506 TV_TREE_UNINIT
, /* tv_id */
2507 PROP_ssa
, /* properties_required */
2508 0, /* properties_provided */
2509 0, /* properties_destroyed */
2510 0, /* todo_flags_start */
2511 0, /* todo_flags_finish */
2514 class pass_early_warn_uninitialized
: public gimple_opt_pass
2517 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2518 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2521 /* opt_pass methods: */
2522 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2523 virtual unsigned int execute (function
*)
2525 return execute_early_warn_uninitialized ();
2528 }; // class pass_early_warn_uninitialized
2533 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2535 return new pass_early_warn_uninitialized (ctxt
);