1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2015 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "double-int.h"
35 #include "fold-const.h"
39 #include "hard-reg-set.h"
42 #include "dominance.h"
44 #include "basic-block.h"
45 #include "gimple-pretty-print.h"
47 #include "tree-ssa-alias.h"
48 #include "internal-fn.h"
49 #include "gimple-expr.h"
52 #include "gimple-iterator.h"
53 #include "gimple-ssa.h"
54 #include "tree-phinodes.h"
55 #include "ssa-iterators.h"
57 #include "tree-inline.h"
58 #include "tree-pass.h"
59 #include "diagnostic-core.h"
63 /* This implements the pass that does predicate aware warning on uses of
64 possibly uninitialized variables. The pass first collects the set of
65 possibly uninitialized SSA names. For each such name, it walks through
66 all its immediate uses. For each immediate use, it rebuilds the condition
67 expression (the predicate) that guards the use. The predicate is then
68 examined to see if the variable is always defined under that same condition.
69 This is done either by pruning the unrealizable paths that lead to the
70 default definitions or by checking if the predicate set that guards the
71 defining paths is a superset of the use predicate. */
74 /* Pointer set of potentially undefined ssa names, i.e.,
75 ssa names that are defined by phi with operands that
76 are not defined or potentially undefined. */
77 static hash_set
<tree
> *possibly_undefined_names
= 0;
79 /* Bit mask handling macros. */
80 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
81 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
82 #define MASK_EMPTY(mask) (mask == 0)
84 /* Returns the first bit position (starting from LSB)
85 in mask that is non zero. Returns -1 if the mask is empty. */
87 get_mask_first_set_bit (unsigned mask
)
93 while ((mask
& (1 << pos
)) == 0)
98 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
100 /* Return true if T, an SSA_NAME, has an undefined value. */
102 has_undefined_value_p (tree t
)
104 return (ssa_undefined_value_p (t
)
105 || (possibly_undefined_names
106 && possibly_undefined_names
->contains (t
)));
111 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
112 is set on SSA_NAME_VAR. */
115 uninit_undefined_value_p (tree t
) {
116 if (!has_undefined_value_p (t
))
118 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
123 /* Emit warnings for uninitialized variables. This is done in two passes.
125 The first pass notices real uses of SSA names with undefined values.
126 Such uses are unconditionally uninitialized, and we can be certain that
127 such a use is a mistake. This pass is run before most optimizations,
128 so that we catch as many as we can.
130 The second pass follows PHI nodes to find uses that are potentially
131 uninitialized. In this case we can't necessarily prove that the use
132 is really uninitialized. This pass is run after most optimizations,
133 so that we thread as many jumps and possible, and delete as much dead
134 code as possible, in order to reduce false positives. We also look
135 again for plain uninitialized variables, since optimization may have
136 changed conditionally uninitialized to unconditionally uninitialized. */
138 /* Emit a warning for EXPR based on variable VAR at the point in the
139 program T, an SSA_NAME, is used being uninitialized. The exact
140 warning text is in MSGID and DATA is the gimple stmt with info about
141 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
142 gives which argument of the phi node to take the location from. WC
143 is the warning code. */
146 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
147 const char *gmsgid
, void *data
, location_t phiarg_loc
)
149 gimple context
= (gimple
) data
;
150 location_t location
, cfun_loc
;
151 expanded_location xloc
, floc
;
153 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
154 turns in a COMPLEX_EXPR with the not initialized part being
155 set to its previous (undefined) value. */
156 if (is_gimple_assign (context
)
157 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
159 if (!has_undefined_value_p (t
))
162 /* TREE_NO_WARNING either means we already warned, or the front end
163 wishes to suppress the warning. */
165 && (gimple_no_warning_p (context
)
166 || (gimple_assign_single_p (context
)
167 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
168 || TREE_NO_WARNING (expr
))
171 if (context
!= NULL
&& gimple_has_location (context
))
172 location
= gimple_location (context
);
173 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
174 location
= phiarg_loc
;
176 location
= DECL_SOURCE_LOCATION (var
);
177 location
= linemap_resolve_location (line_table
, location
,
178 LRK_SPELLING_LOCATION
,
180 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
181 xloc
= expand_location (location
);
182 floc
= expand_location (cfun_loc
);
183 if (warning_at (location
, wc
, gmsgid
, expr
))
185 TREE_NO_WARNING (expr
) = 1;
187 if (location
== DECL_SOURCE_LOCATION (var
))
189 if (xloc
.file
!= floc
.file
190 || linemap_location_before_p (line_table
,
192 || linemap_location_before_p (line_table
,
193 cfun
->function_end_locus
,
195 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
200 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
202 gimple_stmt_iterator gsi
;
205 FOR_EACH_BB_FN (bb
, cfun
)
207 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
208 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
209 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
211 gimple stmt
= gsi_stmt (gsi
);
216 if (is_gimple_debug (stmt
))
219 /* We only do data flow with SSA_NAMEs, so that's all we
221 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
223 use
= USE_FROM_PTR (use_p
);
225 warn_uninit (OPT_Wuninitialized
, use
,
226 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
227 "%qD is used uninitialized in this function",
228 stmt
, UNKNOWN_LOCATION
);
229 else if (warn_possibly_uninitialized
)
230 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
231 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
232 "%qD may be used uninitialized in this function",
233 stmt
, UNKNOWN_LOCATION
);
236 /* For memory the only cheap thing we can do is see if we
237 have a use of the default def of the virtual operand.
238 ??? Not so cheap would be to use the alias oracle via
239 walk_aliased_vdefs, if we don't find any aliasing vdef
240 warn as is-used-uninitialized, if we don't find an aliasing
241 vdef that kills our use (stmt_kills_ref_p), warn as
242 may-be-used-uninitialized. But this walk is quadratic and
243 so must be limited which means we would miss warning
245 use
= gimple_vuse (stmt
);
247 && gimple_assign_single_p (stmt
)
248 && !gimple_vdef (stmt
)
249 && SSA_NAME_IS_DEFAULT_DEF (use
))
251 tree rhs
= gimple_assign_rhs1 (stmt
);
252 tree base
= get_base_address (rhs
);
254 /* Do not warn if it can be initialized outside this function. */
255 if (TREE_CODE (base
) != VAR_DECL
256 || DECL_HARD_REGISTER (base
)
257 || is_global_var (base
))
261 warn_uninit (OPT_Wuninitialized
, use
,
262 gimple_assign_rhs1 (stmt
), base
,
263 "%qE is used uninitialized in this function",
264 stmt
, UNKNOWN_LOCATION
);
265 else if (warn_possibly_uninitialized
)
266 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
267 gimple_assign_rhs1 (stmt
), base
,
268 "%qE may be used uninitialized in this function",
269 stmt
, UNKNOWN_LOCATION
);
277 /* Checks if the operand OPND of PHI is defined by
278 another phi with one operand defined by this PHI,
279 but the rest operands are all defined. If yes,
280 returns true to skip this this operand as being
281 redundant. Can be enhanced to be more general. */
284 can_skip_redundant_opnd (tree opnd
, gimple phi
)
290 phi_def
= gimple_phi_result (phi
);
291 op_def
= SSA_NAME_DEF_STMT (opnd
);
292 if (gimple_code (op_def
) != GIMPLE_PHI
)
294 n
= gimple_phi_num_args (op_def
);
295 for (i
= 0; i
< n
; ++i
)
297 tree op
= gimple_phi_arg_def (op_def
, i
);
298 if (TREE_CODE (op
) != SSA_NAME
)
300 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
307 /* Returns a bit mask holding the positions of arguments in PHI
308 that have empty (or possibly empty) definitions. */
311 compute_uninit_opnds_pos (gphi
*phi
)
314 unsigned uninit_opnds
= 0;
316 n
= gimple_phi_num_args (phi
);
317 /* Bail out for phi with too many args. */
321 for (i
= 0; i
< n
; ++i
)
323 tree op
= gimple_phi_arg_def (phi
, i
);
324 if (TREE_CODE (op
) == SSA_NAME
325 && uninit_undefined_value_p (op
)
326 && !can_skip_redundant_opnd (op
, phi
))
328 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
330 /* Ignore SSA_NAMEs that appear on abnormal edges
332 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
335 MASK_SET_BIT (uninit_opnds
, i
);
341 /* Find the immediate postdominator PDOM of the specified
342 basic block BLOCK. */
344 static inline basic_block
345 find_pdom (basic_block block
)
347 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
348 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
352 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
354 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
359 /* Find the immediate DOM of the specified
360 basic block BLOCK. */
362 static inline basic_block
363 find_dom (basic_block block
)
365 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
366 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
369 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
371 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
376 /* Returns true if BB1 is postdominating BB2 and BB1 is
377 not a loop exit bb. The loop exit bb check is simple and does
378 not cover all cases. */
381 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
383 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
386 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
392 /* Find the closest postdominator of a specified BB, which is control
395 static inline basic_block
396 find_control_equiv_block (basic_block bb
)
400 pdom
= find_pdom (bb
);
402 /* Skip the postdominating bb that is also loop exit. */
403 if (!is_non_loop_exit_postdominating (pdom
, bb
))
406 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
412 #define MAX_NUM_CHAINS 8
413 #define MAX_CHAIN_LEN 5
414 #define MAX_POSTDOM_CHECK 8
415 #define MAX_SWITCH_CASES 40
417 /* Computes the control dependence chains (paths of edges)
418 for DEP_BB up to the dominating basic block BB (the head node of a
419 chain should be dominated by it). CD_CHAINS is pointer to an
420 array holding the result chains. CUR_CD_CHAIN is the current
421 chain being computed. *NUM_CHAINS is total number of chains. The
422 function returns true if the information is successfully computed,
423 return false if there is no control dependence or not computed. */
426 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
427 vec
<edge
> *cd_chains
,
429 vec
<edge
> *cur_cd_chain
,
435 bool found_cd_chain
= false;
436 size_t cur_chain_len
= 0;
438 if (EDGE_COUNT (bb
->succs
) < 2)
441 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
445 /* Could use a set instead. */
446 cur_chain_len
= cur_cd_chain
->length ();
447 if (cur_chain_len
> MAX_CHAIN_LEN
)
450 for (i
= 0; i
< cur_chain_len
; i
++)
452 edge e
= (*cur_cd_chain
)[i
];
453 /* Cycle detected. */
458 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
461 int post_dom_check
= 0;
462 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
466 cur_cd_chain
->safe_push (e
);
467 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
471 /* Found a direct control dependence. */
472 if (*num_chains
< MAX_NUM_CHAINS
)
474 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
477 found_cd_chain
= true;
478 /* Check path from next edge. */
482 /* Now check if DEP_BB is indirectly control dependent on BB. */
483 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
484 num_chains
, cur_cd_chain
, num_calls
))
486 found_cd_chain
= true;
490 cd_bb
= find_pdom (cd_bb
);
492 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
496 cur_cd_chain
->pop ();
497 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
499 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
501 return found_cd_chain
;
504 /* The type to represent a simple predicate */
506 typedef struct use_def_pred_info
510 enum tree_code cond_code
;
514 /* The type to represent a sequence of predicates grouped
515 with .AND. operation. */
517 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
519 /* The type to represent a sequence of pred_chains grouped
520 with .OR. operation. */
522 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
524 /* Converts the chains of control dependence edges into a set of
525 predicates. A control dependence chain is represented by a vector
526 edges. DEP_CHAINS points to an array of dependence chains.
527 NUM_CHAINS is the size of the chain array. One edge in a dependence
528 chain is mapped to predicate expression represented by pred_info
529 type. One dependence chain is converted to a composite predicate that
530 is the result of AND operation of pred_info mapped to each edge.
531 A composite predicate is presented by a vector of pred_info. On
532 return, *PREDS points to the resulting array of composite predicates.
533 *NUM_PREDS is the number of composite predictes. */
536 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
538 pred_chain_union
*preds
)
540 bool has_valid_pred
= false;
542 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
545 /* Now convert the control dep chain into a set
547 preds
->reserve (num_chains
);
549 for (i
= 0; i
< num_chains
; i
++)
551 vec
<edge
> one_cd_chain
= dep_chains
[i
];
553 has_valid_pred
= false;
554 pred_chain t_chain
= vNULL
;
555 for (j
= 0; j
< one_cd_chain
.length (); j
++)
558 gimple_stmt_iterator gsi
;
559 basic_block guard_bb
;
565 gsi
= gsi_last_bb (guard_bb
);
568 has_valid_pred
= false;
571 cond_stmt
= gsi_stmt (gsi
);
572 if (is_gimple_call (cond_stmt
)
573 && EDGE_COUNT (e
->src
->succs
) >= 2)
575 /* Ignore EH edge. Can add assertion
576 on the other edge's flag. */
579 /* Skip if there is essentially one succesor. */
580 if (EDGE_COUNT (e
->src
->succs
) == 2)
586 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
588 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
597 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
599 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
600 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
601 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
602 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
603 t_chain
.safe_push (one_pred
);
604 has_valid_pred
= true;
606 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
608 /* Avoid quadratic behavior. */
609 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
611 has_valid_pred
= false;
614 /* Find the case label. */
617 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
619 tree tl
= gimple_switch_label (gs
, idx
);
620 if (e
->dest
== label_to_block (CASE_LABEL (tl
)))
631 /* If more than one label reaches this block or the case
632 label doesn't have a single value (like the default one)
636 || (CASE_HIGH (l
) && !operand_equal_p (CASE_LOW (l
),
639 has_valid_pred
= false;
642 one_pred
.pred_lhs
= gimple_switch_index (gs
);
643 one_pred
.pred_rhs
= CASE_LOW (l
);
644 one_pred
.cond_code
= EQ_EXPR
;
645 one_pred
.invert
= false;
646 t_chain
.safe_push (one_pred
);
647 has_valid_pred
= true;
651 has_valid_pred
= false;
659 preds
->safe_push (t_chain
);
661 return has_valid_pred
;
664 /* Computes all control dependence chains for USE_BB. The control
665 dependence chains are then converted to an array of composite
666 predicates pointed to by PREDS. PHI_BB is the basic block of
667 the phi whose result is used in USE_BB. */
670 find_predicates (pred_chain_union
*preds
,
674 size_t num_chains
= 0, i
;
676 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
677 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
678 bool has_valid_pred
= false;
679 basic_block cd_root
= 0;
681 /* First find the closest bb that is control equivalent to PHI_BB
682 that also dominates USE_BB. */
684 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
686 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
687 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
688 cd_root
= ctrl_eq_bb
;
693 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
694 &cur_chain
, &num_calls
);
697 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
698 for (i
= 0; i
< num_chains
; i
++)
699 dep_chains
[i
].release ();
700 return has_valid_pred
;
703 /* Computes the set of incoming edges of PHI that have non empty
704 definitions of a phi chain. The collection will be done
705 recursively on operands that are defined by phis. CD_ROOT
706 is the control dependence root. *EDGES holds the result, and
707 VISITED_PHIS is a pointer set for detecting cycles. */
710 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
712 hash_set
<gimple
> *visited_phis
)
718 if (visited_phis
->add (phi
))
721 n
= gimple_phi_num_args (phi
);
722 for (i
= 0; i
< n
; i
++)
724 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
725 opnd
= gimple_phi_arg_def (phi
, i
);
727 if (TREE_CODE (opnd
) != SSA_NAME
)
729 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
731 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
732 print_gimple_stmt (dump_file
, phi
, 0, 0);
734 edges
->safe_push (opnd_edge
);
738 gimple def
= SSA_NAME_DEF_STMT (opnd
);
740 if (gimple_code (def
) == GIMPLE_PHI
741 && dominated_by_p (CDI_DOMINATORS
,
742 gimple_bb (def
), cd_root
))
743 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
745 else if (!uninit_undefined_value_p (opnd
))
747 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
749 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
750 print_gimple_stmt (dump_file
, phi
, 0, 0);
752 edges
->safe_push (opnd_edge
);
758 /* For each use edge of PHI, computes all control dependence chains.
759 The control dependence chains are then converted to an array of
760 composite predicates pointed to by PREDS. */
763 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
765 size_t num_chains
= 0, i
, n
;
766 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
767 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
768 vec
<edge
> def_edges
= vNULL
;
769 bool has_valid_pred
= false;
770 basic_block phi_bb
, cd_root
= 0;
772 phi_bb
= gimple_bb (phi
);
773 /* First find the closest dominating bb to be
774 the control dependence root */
775 cd_root
= find_dom (phi_bb
);
779 hash_set
<gimple
> visited_phis
;
780 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
782 n
= def_edges
.length ();
786 for (i
= 0; i
< n
; i
++)
792 opnd_edge
= def_edges
[i
];
793 prev_nc
= num_chains
;
794 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
795 &num_chains
, &cur_chain
, &num_calls
);
797 /* Now update the newly added chains with
798 the phi operand edge: */
799 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
801 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
802 dep_chains
[num_chains
++] = vNULL
;
803 for (j
= prev_nc
; j
< num_chains
; j
++)
804 dep_chains
[j
].safe_push (opnd_edge
);
809 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
810 for (i
= 0; i
< num_chains
; i
++)
811 dep_chains
[i
].release ();
812 return has_valid_pred
;
815 /* Dumps the predicates (PREDS) for USESTMT. */
818 dump_predicates (gimple usestmt
, pred_chain_union preds
,
822 pred_chain one_pred_chain
= vNULL
;
823 fprintf (dump_file
, msg
);
824 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
825 fprintf (dump_file
, "is guarded by :\n\n");
826 size_t num_preds
= preds
.length ();
827 /* Do some dumping here: */
828 for (i
= 0; i
< num_preds
; i
++)
832 one_pred_chain
= preds
[i
];
833 np
= one_pred_chain
.length ();
835 for (j
= 0; j
< np
; j
++)
837 pred_info one_pred
= one_pred_chain
[j
];
839 fprintf (dump_file
, " (.NOT.) ");
840 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
841 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
842 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
844 fprintf (dump_file
, " (.AND.) ");
846 fprintf (dump_file
, "\n");
848 if (i
< num_preds
- 1)
849 fprintf (dump_file
, "(.OR.)\n");
851 fprintf (dump_file
, "\n\n");
855 /* Destroys the predicate set *PREDS. */
858 destroy_predicate_vecs (pred_chain_union preds
)
862 size_t n
= preds
.length ();
863 for (i
= 0; i
< n
; i
++)
869 /* Computes the 'normalized' conditional code with operand
870 swapping and condition inversion. */
872 static enum tree_code
873 get_cmp_code (enum tree_code orig_cmp_code
,
874 bool swap_cond
, bool invert
)
876 enum tree_code tc
= orig_cmp_code
;
879 tc
= swap_tree_comparison (orig_cmp_code
);
881 tc
= invert_tree_comparison (tc
, false);
898 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
899 all values in the range satisfies (x CMPC BOUNDARY) == true. */
902 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
904 bool inverted
= false;
908 /* Only handle integer constant here. */
909 if (TREE_CODE (val
) != INTEGER_CST
910 || TREE_CODE (boundary
) != INTEGER_CST
)
913 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
915 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
918 cmpc
= invert_tree_comparison (cmpc
, false);
925 result
= tree_int_cst_equal (val
, boundary
);
926 else if (cmpc
== LT_EXPR
)
927 result
= tree_int_cst_lt (val
, boundary
);
930 gcc_assert (cmpc
== LE_EXPR
);
931 result
= tree_int_cst_le (val
, boundary
);
937 result
= tree_int_cst_equal (val
, boundary
);
938 else if (cmpc
== LT_EXPR
)
939 result
= tree_int_cst_lt (val
, boundary
);
942 gcc_assert (cmpc
== LE_EXPR
);
943 result
= (tree_int_cst_equal (val
, boundary
)
944 || tree_int_cst_lt (val
, boundary
));
954 /* Returns true if PRED is common among all the predicate
955 chains (PREDS) (and therefore can be factored out).
956 NUM_PRED_CHAIN is the size of array PREDS. */
959 find_matching_predicate_in_rest_chains (pred_info pred
,
960 pred_chain_union preds
,
961 size_t num_pred_chains
)
966 if (num_pred_chains
== 1)
969 for (i
= 1; i
< num_pred_chains
; i
++)
972 pred_chain one_chain
= preds
[i
];
973 n
= one_chain
.length ();
974 for (j
= 0; j
< n
; j
++)
976 pred_info pred2
= one_chain
[j
];
977 /* Can relax the condition comparison to not
978 use address comparison. However, the most common
979 case is that multiple control dependent paths share
980 a common path prefix, so address comparison should
983 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
984 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
985 && pred2
.invert
== pred
.invert
)
997 /* Forward declaration. */
999 is_use_properly_guarded (gimple use_stmt
,
1002 unsigned uninit_opnds
,
1003 hash_set
<gphi
*> *visited_phis
);
1005 /* Returns true if all uninitialized opnds are pruned. Returns false
1006 otherwise. PHI is the phi node with uninitialized operands,
1007 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1008 FLAG_DEF is the statement defining the flag guarding the use of the
1009 PHI output, BOUNDARY_CST is the const value used in the predicate
1010 associated with the flag, CMP_CODE is the comparison code used in
1011 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1012 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1018 flag_1 = phi <0, 1> // (1)
1019 var_1 = phi <undef, some_val>
1023 flag_2 = phi <0, flag_1, flag_1> // (2)
1024 var_2 = phi <undef, var_1, var_1>
1031 Because some flag arg in (1) is not constant, if we do not look into the
1032 flag phis recursively, it is conservatively treated as unknown and var_1
1033 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
1034 a false warning will be emitted. Checking recursively into (1), the compiler can
1035 find out that only some_val (which is defined) can flow into (3) which is OK.
1040 prune_uninit_phi_opnds_in_unrealizable_paths (gphi
*phi
,
1041 unsigned uninit_opnds
,
1044 enum tree_code cmp_code
,
1045 hash_set
<gphi
*> *visited_phis
,
1046 bitmap
*visited_flag_phis
)
1050 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
1054 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1057 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1058 if (!is_gimple_constant (flag_arg
))
1060 gphi
*flag_arg_def
, *phi_arg_def
;
1062 unsigned uninit_opnds_arg_phi
;
1064 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1066 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1070 phi_arg
= gimple_phi_arg_def (phi
, i
);
1071 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1074 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1078 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1081 if (!*visited_flag_phis
)
1082 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1084 if (bitmap_bit_p (*visited_flag_phis
,
1085 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1088 bitmap_set_bit (*visited_flag_phis
,
1089 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1091 /* Now recursively prune the uninitialized phi args. */
1092 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1093 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1094 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1095 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1098 bitmap_clear_bit (*visited_flag_phis
,
1099 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1103 /* Now check if the constant is in the guarded range. */
1104 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1109 /* Now that we know that this undefined edge is not
1110 pruned. If the operand is defined by another phi,
1111 we can further prune the incoming edges of that
1112 phi by checking the predicates of this operands. */
1114 opnd
= gimple_phi_arg_def (phi
, i
);
1115 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1116 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1119 unsigned uninit_opnds2
1120 = compute_uninit_opnds_pos (opnd_def_phi
);
1121 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
1122 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1123 if (!is_use_properly_guarded (phi
,
1138 /* A helper function that determines if the predicate set
1139 of the use is not overlapping with that of the uninit paths.
1140 The most common senario of guarded use is in Example 1:
1153 The real world examples are usually more complicated, but similar
1154 and usually result from inlining:
1156 bool init_func (int * x)
1175 Another possible use scenario is in the following trivial example:
1187 Predicate analysis needs to compute the composite predicate:
1189 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1190 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1191 (the predicate chain for phi operand defs can be computed
1192 starting from a bb that is control equivalent to the phi's
1193 bb and is dominating the operand def.)
1195 and check overlapping:
1196 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1199 This implementation provides framework that can handle
1200 scenarios. (Note that many simple cases are handled properly
1201 without the predicate analysis -- this is due to jump threading
1202 transformation which eliminates the merge point thus makes
1203 path sensitive analysis unnecessary.)
1205 NUM_PREDS is the number is the number predicate chains, PREDS is
1206 the array of chains, PHI is the phi node whose incoming (undefined)
1207 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1208 uninit operand positions. VISITED_PHIS is the pointer set of phi
1209 stmts being checked. */
1213 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1214 gphi
*phi
, unsigned uninit_opnds
,
1215 hash_set
<gphi
*> *visited_phis
)
1218 gimple flag_def
= 0;
1219 tree boundary_cst
= 0;
1220 enum tree_code cmp_code
;
1221 bool swap_cond
= false;
1222 bool invert
= false;
1223 pred_chain the_pred_chain
= vNULL
;
1224 bitmap visited_flag_phis
= NULL
;
1225 bool all_pruned
= false;
1226 size_t num_preds
= preds
.length ();
1228 gcc_assert (num_preds
> 0);
1229 /* Find within the common prefix of multiple predicate chains
1230 a predicate that is a comparison of a flag variable against
1232 the_pred_chain
= preds
[0];
1233 n
= the_pred_chain
.length ();
1234 for (i
= 0; i
< n
; i
++)
1236 tree cond_lhs
, cond_rhs
, flag
= 0;
1238 pred_info the_pred
= the_pred_chain
[i
];
1240 invert
= the_pred
.invert
;
1241 cond_lhs
= the_pred
.pred_lhs
;
1242 cond_rhs
= the_pred
.pred_rhs
;
1243 cmp_code
= the_pred
.cond_code
;
1245 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1246 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1248 boundary_cst
= cond_rhs
;
1251 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1252 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1254 boundary_cst
= cond_lhs
;
1262 flag_def
= SSA_NAME_DEF_STMT (flag
);
1267 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1268 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1269 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1279 /* Now check all the uninit incoming edge has a constant flag value
1280 that is in conflict with the use guard/predicate. */
1281 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1283 if (cmp_code
== ERROR_MARK
)
1286 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1288 as_a
<gphi
*> (flag_def
),
1292 &visited_flag_phis
);
1294 if (visited_flag_phis
)
1295 BITMAP_FREE (visited_flag_phis
);
1300 /* The helper function returns true if two predicates X1 and X2
1301 are equivalent. It assumes the expressions have already
1302 properly re-associated. */
1305 pred_equal_p (pred_info x1
, pred_info x2
)
1307 enum tree_code c1
, c2
;
1308 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1309 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1313 if (x1
.invert
!= x2
.invert
)
1314 c2
= invert_tree_comparison (x2
.cond_code
, false);
1321 /* Returns true if the predication is testing !=. */
1324 is_neq_relop_p (pred_info pred
)
1327 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1328 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1331 /* Returns true if pred is of the form X != 0. */
1334 is_neq_zero_form_p (pred_info pred
)
1336 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1337 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1342 /* The helper function returns true if two predicates X1
1343 is equivalent to X2 != 0. */
1346 pred_expr_equal_p (pred_info x1
, tree x2
)
1348 if (!is_neq_zero_form_p (x1
))
1351 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1354 /* Returns true of the domain of single predicate expression
1355 EXPR1 is a subset of that of EXPR2. Returns false if it
1356 can not be proved. */
1359 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1361 enum tree_code code1
, code2
;
1363 if (pred_equal_p (expr1
, expr2
))
1366 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1367 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1370 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1373 code1
= expr1
.cond_code
;
1375 code1
= invert_tree_comparison (code1
, false);
1376 code2
= expr2
.cond_code
;
1378 code2
= invert_tree_comparison (code2
, false);
1380 if (code1
== EQ_EXPR
&& code2
== BIT_AND_EXPR
)
1381 return wi::eq_p (expr1
.pred_rhs
,
1382 wi::bit_and (expr1
.pred_rhs
, expr2
.pred_rhs
));
1384 if (code1
!= code2
&& code2
!= NE_EXPR
)
1387 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1393 /* Returns true if the domain of PRED1 is a subset
1394 of that of PRED2. Returns false if it can not be proved so. */
1397 is_pred_chain_subset_of (pred_chain pred1
,
1400 size_t np1
, np2
, i1
, i2
;
1402 np1
= pred1
.length ();
1403 np2
= pred2
.length ();
1405 for (i2
= 0; i2
< np2
; i2
++)
1408 pred_info info2
= pred2
[i2
];
1409 for (i1
= 0; i1
< np1
; i1
++)
1411 pred_info info1
= pred1
[i1
];
1412 if (is_pred_expr_subset_of (info1
, info2
))
1424 /* Returns true if the domain defined by
1425 one pred chain ONE_PRED is a subset of the domain
1426 of *PREDS. It returns false if ONE_PRED's domain is
1427 not a subset of any of the sub-domains of PREDS
1428 (corresponding to each individual chains in it), even
1429 though it may be still be a subset of whole domain
1430 of PREDS which is the union (ORed) of all its subdomains.
1431 In other words, the result is conservative. */
1434 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1437 size_t n
= preds
.length ();
1439 for (i
= 0; i
< n
; i
++)
1441 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1448 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1449 true if the domain defined by PREDS1 is a superset
1450 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1451 PREDS2 respectively. The implementation chooses not to build
1452 generic trees (and relying on the folding capability of the
1453 compiler), but instead performs brute force comparison of
1454 individual predicate chains (won't be a compile time problem
1455 as the chains are pretty short). When the function returns
1456 false, it does not necessarily mean *PREDS1 is not a superset
1457 of *PREDS2, but mean it may not be so since the analysis can
1458 not prove it. In such cases, false warnings may still be
1462 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1465 pred_chain one_pred_chain
= vNULL
;
1467 n2
= preds2
.length ();
1469 for (i
= 0; i
< n2
; i
++)
1471 one_pred_chain
= preds2
[i
];
1472 if (!is_included_in (one_pred_chain
, preds1
))
1479 /* Returns true if TC is AND or OR. */
1482 is_and_or_or_p (enum tree_code tc
, tree type
)
1484 return (tc
== BIT_IOR_EXPR
1485 || (tc
== BIT_AND_EXPR
1486 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1489 /* Returns true if X1 is the negate of X2. */
1492 pred_neg_p (pred_info x1
, pred_info x2
)
1494 enum tree_code c1
, c2
;
1495 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1496 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1500 if (x1
.invert
== x2
.invert
)
1501 c2
= invert_tree_comparison (x2
.cond_code
, false);
1508 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1509 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1510 3) X OR (!X AND Y) is equivalent to (X OR Y);
1511 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1513 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1516 PREDS is the predicate chains, and N is the number of chains. */
1518 /* Helper function to implement rule 1 above. ONE_CHAIN is
1519 the AND predication to be simplified. */
1522 simplify_pred (pred_chain
*one_chain
)
1525 bool simplified
= false;
1526 pred_chain s_chain
= vNULL
;
1528 n
= one_chain
->length ();
1530 for (i
= 0; i
< n
; i
++)
1532 pred_info
*a_pred
= &(*one_chain
)[i
];
1534 if (!a_pred
->pred_lhs
)
1536 if (!is_neq_zero_form_p (*a_pred
))
1539 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1540 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1542 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1544 for (j
= 0; j
< n
; j
++)
1546 pred_info
*b_pred
= &(*one_chain
)[j
];
1548 if (!b_pred
->pred_lhs
)
1550 if (!is_neq_zero_form_p (*b_pred
))
1553 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1554 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1556 /* Mark a_pred for removal. */
1557 a_pred
->pred_lhs
= NULL
;
1558 a_pred
->pred_rhs
= NULL
;
1569 for (i
= 0; i
< n
; i
++)
1571 pred_info
*a_pred
= &(*one_chain
)[i
];
1572 if (!a_pred
->pred_lhs
)
1574 s_chain
.safe_push (*a_pred
);
1577 one_chain
->release ();
1578 *one_chain
= s_chain
;
1581 /* The helper function implements the rule 2 for the
1584 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1587 simplify_preds_2 (pred_chain_union
*preds
)
1590 bool simplified
= false;
1591 pred_chain_union s_preds
= vNULL
;
1593 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1594 (X AND Y) OR (X AND !Y) is equivalent to X. */
1596 n
= preds
->length ();
1597 for (i
= 0; i
< n
; i
++)
1600 pred_chain
*a_chain
= &(*preds
)[i
];
1602 if (a_chain
->length () != 2)
1608 for (j
= 0; j
< n
; j
++)
1610 pred_chain
*b_chain
;
1616 b_chain
= &(*preds
)[j
];
1617 if (b_chain
->length () != 2)
1623 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1626 a_chain
->release ();
1627 b_chain
->release ();
1628 b_chain
->safe_push (x
);
1632 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1635 a_chain
->release ();
1636 b_chain
->release ();
1637 b_chain
->safe_push (y
);
1643 /* Now clean up the chain. */
1646 for (i
= 0; i
< n
; i
++)
1648 if ((*preds
)[i
].is_empty ())
1650 s_preds
.safe_push ((*preds
)[i
]);
1660 /* The helper function implements the rule 2 for the
1663 3) x OR (!x AND y) is equivalent to x OR y. */
1666 simplify_preds_3 (pred_chain_union
*preds
)
1669 bool simplified
= false;
1671 /* Now iteratively simplify X OR (!X AND Z ..)
1672 into X OR (Z ...). */
1674 n
= preds
->length ();
1678 for (i
= 0; i
< n
; i
++)
1681 pred_chain
*a_chain
= &(*preds
)[i
];
1683 if (a_chain
->length () != 1)
1688 for (j
= 0; j
< n
; j
++)
1690 pred_chain
*b_chain
;
1697 b_chain
= &(*preds
)[j
];
1698 if (b_chain
->length () < 2)
1701 for (k
= 0; k
< b_chain
->length (); k
++)
1704 if (pred_neg_p (x
, x2
))
1706 b_chain
->unordered_remove (k
);
1716 /* The helper function implements the rule 4 for the
1719 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1720 (x != 0 ANd y != 0). */
1723 simplify_preds_4 (pred_chain_union
*preds
)
1726 bool simplified
= false;
1727 pred_chain_union s_preds
= vNULL
;
1730 n
= preds
->length ();
1731 for (i
= 0; i
< n
; i
++)
1734 pred_chain
*a_chain
= &(*preds
)[i
];
1736 if (a_chain
->length () != 1)
1741 if (!is_neq_zero_form_p (z
))
1744 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1745 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1748 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1751 for (j
= 0; j
< n
; j
++)
1753 pred_chain
*b_chain
;
1759 b_chain
= &(*preds
)[j
];
1760 if (b_chain
->length () != 2)
1765 if (!is_neq_zero_form_p (x2
)
1766 || !is_neq_zero_form_p (y2
))
1769 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1770 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1771 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1772 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1775 a_chain
->release ();
1781 /* Now clean up the chain. */
1784 for (i
= 0; i
< n
; i
++)
1786 if ((*preds
)[i
].is_empty ())
1788 s_preds
.safe_push ((*preds
)[i
]);
1799 /* This function simplifies predicates in PREDS. */
1802 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1805 bool changed
= false;
1807 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1809 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1810 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1813 for (i
= 0; i
< preds
->length (); i
++)
1814 simplify_pred (&(*preds
)[i
]);
1816 n
= preds
->length ();
1823 if (simplify_preds_2 (preds
))
1826 /* Now iteratively simplify X OR (!X AND Z ..)
1827 into X OR (Z ...). */
1828 if (simplify_preds_3 (preds
))
1831 if (simplify_preds_4 (preds
))
1839 /* This is a helper function which attempts to normalize predicate chains
1840 by following UD chains. It basically builds up a big tree of either IOR
1841 operations or AND operations, and convert the IOR tree into a
1842 pred_chain_union or BIT_AND tree into a pred_chain.
1852 then _t != 0 will be normalized into a pred_chain_union
1854 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1864 then _t != 0 will be normalized into a pred_chain:
1865 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1869 /* This is a helper function that stores a PRED into NORM_PREDS. */
1872 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1874 pred_chain pred_chain
= vNULL
;
1875 pred_chain
.safe_push (pred
);
1876 norm_preds
->safe_push (pred_chain
);
1879 /* A helper function that creates a predicate of the form
1880 OP != 0 and push it WORK_LIST. */
1883 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1884 hash_set
<tree
> *mark_set
)
1886 if (mark_set
->contains (op
))
1891 arg_pred
.pred_lhs
= op
;
1892 arg_pred
.pred_rhs
= integer_zero_node
;
1893 arg_pred
.cond_code
= NE_EXPR
;
1894 arg_pred
.invert
= false;
1895 work_list
->safe_push (arg_pred
);
1898 /* A helper that generates a pred_info from a gimple assignment
1899 CMP_ASSIGN with comparison rhs. */
1902 get_pred_info_from_cmp (gimple cmp_assign
)
1905 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1906 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1907 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1908 n_pred
.invert
= false;
1912 /* Returns true if the PHI is a degenerated phi with
1913 all args with the same value (relop). In that case, *PRED
1914 will be updated to that value. */
1917 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1924 n
= gimple_phi_num_args (phi
);
1925 op0
= gimple_phi_arg_def (phi
, 0);
1927 if (TREE_CODE (op0
) != SSA_NAME
)
1930 def0
= SSA_NAME_DEF_STMT (op0
);
1931 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1933 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1936 pred0
= get_pred_info_from_cmp (def0
);
1938 for (i
= 1; i
< n
; ++i
)
1942 tree op
= gimple_phi_arg_def (phi
, i
);
1944 if (TREE_CODE (op
) != SSA_NAME
)
1947 def
= SSA_NAME_DEF_STMT (op
);
1948 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1950 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1953 pred
= get_pred_info_from_cmp (def
);
1954 if (!pred_equal_p (pred
, pred0
))
1962 /* Normalize one predicate PRED
1963 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1964 2) otherwise if PRED is of the form x != 0, follow x's definition
1965 and put normalized predicates into WORK_LIST. */
1968 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1969 pred_chain
*norm_chain
,
1971 enum tree_code and_or_code
,
1972 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1973 hash_set
<tree
> *mark_set
)
1975 if (!is_neq_zero_form_p (pred
))
1977 if (and_or_code
== BIT_IOR_EXPR
)
1978 push_pred (norm_preds
, pred
);
1980 norm_chain
->safe_push (pred
);
1984 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1986 if (gimple_code (def_stmt
) == GIMPLE_PHI
1987 && is_degenerated_phi (def_stmt
, &pred
))
1988 work_list
->safe_push (pred
);
1989 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1990 && and_or_code
== BIT_IOR_EXPR
)
1993 n
= gimple_phi_num_args (def_stmt
);
1995 /* If we see non zero constant, we should punt. The predicate
1996 * should be one guarding the phi edge. */
1997 for (i
= 0; i
< n
; ++i
)
1999 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2000 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
2002 push_pred (norm_preds
, pred
);
2007 for (i
= 0; i
< n
; ++i
)
2009 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2010 if (integer_zerop (op
))
2013 push_to_worklist (op
, work_list
, mark_set
);
2016 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2018 if (and_or_code
== BIT_IOR_EXPR
)
2019 push_pred (norm_preds
, pred
);
2021 norm_chain
->safe_push (pred
);
2023 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2025 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2026 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2028 /* But treat x & 3 as condition. */
2029 if (and_or_code
== BIT_AND_EXPR
)
2032 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2033 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2034 n_pred
.cond_code
= and_or_code
;
2035 n_pred
.invert
= false;
2036 norm_chain
->safe_push (n_pred
);
2041 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2042 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2045 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2048 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2049 if (and_or_code
== BIT_IOR_EXPR
)
2050 push_pred (norm_preds
, n_pred
);
2052 norm_chain
->safe_push (n_pred
);
2056 if (and_or_code
== BIT_IOR_EXPR
)
2057 push_pred (norm_preds
, pred
);
2059 norm_chain
->safe_push (pred
);
2063 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2066 normalize_one_pred (pred_chain_union
*norm_preds
,
2069 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2070 enum tree_code and_or_code
= ERROR_MARK
;
2071 pred_chain norm_chain
= vNULL
;
2073 if (!is_neq_zero_form_p (pred
))
2075 push_pred (norm_preds
, pred
);
2079 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2080 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2081 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2082 if (and_or_code
!= BIT_IOR_EXPR
2083 && and_or_code
!= BIT_AND_EXPR
)
2085 if (TREE_CODE_CLASS (and_or_code
)
2088 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2089 push_pred (norm_preds
, n_pred
);
2092 push_pred (norm_preds
, pred
);
2096 work_list
.safe_push (pred
);
2097 hash_set
<tree
> mark_set
;
2099 while (!work_list
.is_empty ())
2101 pred_info a_pred
= work_list
.pop ();
2102 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2103 and_or_code
, &work_list
, &mark_set
);
2105 if (and_or_code
== BIT_AND_EXPR
)
2106 norm_preds
->safe_push (norm_chain
);
2108 work_list
.release ();
2112 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2113 pred_chain one_chain
)
2115 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2116 hash_set
<tree
> mark_set
;
2117 pred_chain norm_chain
= vNULL
;
2120 for (i
= 0; i
< one_chain
.length (); i
++)
2122 work_list
.safe_push (one_chain
[i
]);
2123 mark_set
.add (one_chain
[i
].pred_lhs
);
2126 while (!work_list
.is_empty ())
2128 pred_info a_pred
= work_list
.pop ();
2129 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2130 BIT_AND_EXPR
, &work_list
, &mark_set
);
2133 norm_preds
->safe_push (norm_chain
);
2134 work_list
.release ();
2137 /* Normalize predicate chains PREDS and returns the normalized one. */
2139 static pred_chain_union
2140 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2142 pred_chain_union norm_preds
= vNULL
;
2143 size_t n
= preds
.length ();
2146 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2148 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2149 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2152 for (i
= 0; i
< n
; i
++)
2154 if (preds
[i
].length () != 1)
2155 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2158 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2159 preds
[i
].release ();
2165 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2166 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2174 /* Computes the predicates that guard the use and checks
2175 if the incoming paths that have empty (or possibly
2176 empty) definition can be pruned/filtered. The function returns
2177 true if it can be determined that the use of PHI's def in
2178 USE_STMT is guarded with a predicate set not overlapping with
2179 predicate sets of all runtime paths that do not have a definition.
2180 Returns false if it is not or it can not be determined. USE_BB is
2181 the bb of the use (for phi operand use, the bb is not the bb of
2182 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2183 is a bit vector. If an operand of PHI is uninitialized, the
2184 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2185 set of phis being visted. */
2188 is_use_properly_guarded (gimple use_stmt
,
2191 unsigned uninit_opnds
,
2192 hash_set
<gphi
*> *visited_phis
)
2195 pred_chain_union preds
= vNULL
;
2196 pred_chain_union def_preds
= vNULL
;
2197 bool has_valid_preds
= false;
2198 bool is_properly_guarded
= false;
2200 if (visited_phis
->add (phi
))
2203 phi_bb
= gimple_bb (phi
);
2205 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2208 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2210 if (!has_valid_preds
)
2212 destroy_predicate_vecs (preds
);
2216 /* Try to prune the dead incoming phi edges. */
2218 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2221 if (is_properly_guarded
)
2223 destroy_predicate_vecs (preds
);
2227 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2229 if (!has_valid_preds
)
2231 destroy_predicate_vecs (preds
);
2232 destroy_predicate_vecs (def_preds
);
2236 simplify_preds (&preds
, use_stmt
, true);
2237 preds
= normalize_preds (preds
, use_stmt
, true);
2239 simplify_preds (&def_preds
, phi
, false);
2240 def_preds
= normalize_preds (def_preds
, phi
, false);
2242 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2244 destroy_predicate_vecs (preds
);
2245 destroy_predicate_vecs (def_preds
);
2246 return is_properly_guarded
;
2249 /* Searches through all uses of a potentially
2250 uninitialized variable defined by PHI and returns a use
2251 statement if the use is not properly guarded. It returns
2252 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2253 holding the position(s) of uninit PHI operands. WORKLIST
2254 is the vector of candidate phis that may be updated by this
2255 function. ADDED_TO_WORKLIST is the pointer set tracking
2256 if the new phi is already in the worklist. */
2259 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2260 vec
<gphi
*> *worklist
,
2261 hash_set
<gphi
*> *added_to_worklist
)
2264 use_operand_p use_p
;
2266 imm_use_iterator iter
;
2268 phi_result
= gimple_phi_result (phi
);
2270 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2274 use_stmt
= USE_STMT (use_p
);
2275 if (is_gimple_debug (use_stmt
))
2278 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2279 use_bb
= gimple_phi_arg_edge (use_phi
,
2280 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2282 use_bb
= gimple_bb (use_stmt
);
2284 hash_set
<gphi
*> visited_phis
;
2285 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2289 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2291 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2292 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2294 /* Found one real use, return. */
2295 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2298 /* Found a phi use that is not guarded,
2299 add the phi to the worklist. */
2300 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2305 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2308 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2309 possibly_undefined_names
->add (phi_result
);
2316 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2317 and gives warning if there exists a runtime path from the entry to a
2318 use of the PHI def that does not contain a definition. In other words,
2319 the warning is on the real use. The more dead paths that can be pruned
2320 by the compiler, the fewer false positives the warning is. WORKLIST
2321 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2322 a pointer set tracking if the new phi is added to the worklist or not. */
2325 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2326 hash_set
<gphi
*> *added_to_worklist
)
2328 unsigned uninit_opnds
;
2329 gimple uninit_use_stmt
= 0;
2334 /* Don't look at virtual operands. */
2335 if (virtual_operand_p (gimple_phi_result (phi
)))
2338 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2340 if (MASK_EMPTY (uninit_opnds
))
2343 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2345 fprintf (dump_file
, "[CHECK]: examining phi: ");
2346 print_gimple_stmt (dump_file
, phi
, 0, 0);
2349 /* Now check if we have any use of the value without proper guard. */
2350 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2351 worklist
, added_to_worklist
);
2353 /* All uses are properly guarded. */
2354 if (!uninit_use_stmt
)
2357 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2358 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2359 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2361 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2362 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2364 loc
= UNKNOWN_LOCATION
;
2365 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2366 SSA_NAME_VAR (uninit_op
),
2367 "%qD may be used uninitialized in this function",
2368 uninit_use_stmt
, loc
);
2373 gate_warn_uninitialized (void)
2375 return warn_uninitialized
|| warn_maybe_uninitialized
;
2380 const pass_data pass_data_late_warn_uninitialized
=
2382 GIMPLE_PASS
, /* type */
2383 "uninit", /* name */
2384 OPTGROUP_NONE
, /* optinfo_flags */
2385 TV_NONE
, /* tv_id */
2386 PROP_ssa
, /* properties_required */
2387 0, /* properties_provided */
2388 0, /* properties_destroyed */
2389 0, /* todo_flags_start */
2390 0, /* todo_flags_finish */
2393 class pass_late_warn_uninitialized
: public gimple_opt_pass
2396 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2397 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2400 /* opt_pass methods: */
2401 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2402 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2403 virtual unsigned int execute (function
*);
2405 }; // class pass_late_warn_uninitialized
2408 pass_late_warn_uninitialized::execute (function
*fun
)
2412 vec
<gphi
*> worklist
= vNULL
;
2414 calculate_dominance_info (CDI_DOMINATORS
);
2415 calculate_dominance_info (CDI_POST_DOMINATORS
);
2416 /* Re-do the plain uninitialized variable check, as optimization may have
2417 straightened control flow. Do this first so that we don't accidentally
2418 get a "may be" warning when we'd have seen an "is" warning later. */
2419 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2421 timevar_push (TV_TREE_UNINIT
);
2423 possibly_undefined_names
= new hash_set
<tree
>;
2424 hash_set
<gphi
*> added_to_worklist
;
2426 /* Initialize worklist */
2427 FOR_EACH_BB_FN (bb
, fun
)
2428 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2430 gphi
*phi
= gsi
.phi ();
2433 n
= gimple_phi_num_args (phi
);
2435 /* Don't look at virtual operands. */
2436 if (virtual_operand_p (gimple_phi_result (phi
)))
2439 for (i
= 0; i
< n
; ++i
)
2441 tree op
= gimple_phi_arg_def (phi
, i
);
2442 if (TREE_CODE (op
) == SSA_NAME
2443 && uninit_undefined_value_p (op
))
2445 worklist
.safe_push (phi
);
2446 added_to_worklist
.add (phi
);
2447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2449 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2450 print_gimple_stmt (dump_file
, phi
, 0, 0);
2457 while (worklist
.length () != 0)
2460 cur_phi
= worklist
.pop ();
2461 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2464 worklist
.release ();
2465 delete possibly_undefined_names
;
2466 possibly_undefined_names
= NULL
;
2467 free_dominance_info (CDI_POST_DOMINATORS
);
2468 timevar_pop (TV_TREE_UNINIT
);
2475 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2477 return new pass_late_warn_uninitialized (ctxt
);
2482 execute_early_warn_uninitialized (void)
2484 /* Currently, this pass runs always but
2485 execute_late_warn_uninitialized only runs with optimization. With
2486 optimization we want to warn about possible uninitialized as late
2487 as possible, thus don't do it here. However, without
2488 optimization we need to warn here about "may be uninitialized". */
2489 calculate_dominance_info (CDI_POST_DOMINATORS
);
2491 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2493 /* Post-dominator information can not be reliably updated. Free it
2496 free_dominance_info (CDI_POST_DOMINATORS
);
2503 const pass_data pass_data_early_warn_uninitialized
=
2505 GIMPLE_PASS
, /* type */
2506 "*early_warn_uninitialized", /* name */
2507 OPTGROUP_NONE
, /* optinfo_flags */
2508 TV_TREE_UNINIT
, /* tv_id */
2509 PROP_ssa
, /* properties_required */
2510 0, /* properties_provided */
2511 0, /* properties_destroyed */
2512 0, /* todo_flags_start */
2513 0, /* todo_flags_finish */
2516 class pass_early_warn_uninitialized
: public gimple_opt_pass
2519 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2520 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2523 /* opt_pass methods: */
2524 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2525 virtual unsigned int execute (function
*)
2527 return execute_early_warn_uninitialized ();
2530 }; // class pass_early_warn_uninitialized
2535 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2537 return new pass_early_warn_uninitialized (ctxt
);