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"
62 /* This implements the pass that does predicate aware warning on uses of
63 possibly uninitialized variables. The pass first collects the set of
64 possibly uninitialized SSA names. For each such name, it walks through
65 all its immediate uses. For each immediate use, it rebuilds the condition
66 expression (the predicate) that guards the use. The predicate is then
67 examined to see if the variable is always defined under that same condition.
68 This is done either by pruning the unrealizable paths that lead to the
69 default definitions or by checking if the predicate set that guards the
70 defining paths is a superset of the use predicate. */
73 /* Pointer set of potentially undefined ssa names, i.e.,
74 ssa names that are defined by phi with operands that
75 are not defined or potentially undefined. */
76 static hash_set
<tree
> *possibly_undefined_names
= 0;
78 /* Bit mask handling macros. */
79 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
80 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
81 #define MASK_EMPTY(mask) (mask == 0)
83 /* Returns the first bit position (starting from LSB)
84 in mask that is non zero. Returns -1 if the mask is empty. */
86 get_mask_first_set_bit (unsigned mask
)
92 while ((mask
& (1 << pos
)) == 0)
97 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
99 /* Return true if T, an SSA_NAME, has an undefined value. */
101 has_undefined_value_p (tree t
)
103 return (ssa_undefined_value_p (t
)
104 || (possibly_undefined_names
105 && possibly_undefined_names
->contains (t
)));
110 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
111 is set on SSA_NAME_VAR. */
114 uninit_undefined_value_p (tree t
) {
115 if (!has_undefined_value_p (t
))
117 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
122 /* Emit warnings for uninitialized variables. This is done in two passes.
124 The first pass notices real uses of SSA names with undefined values.
125 Such uses are unconditionally uninitialized, and we can be certain that
126 such a use is a mistake. This pass is run before most optimizations,
127 so that we catch as many as we can.
129 The second pass follows PHI nodes to find uses that are potentially
130 uninitialized. In this case we can't necessarily prove that the use
131 is really uninitialized. This pass is run after most optimizations,
132 so that we thread as many jumps and possible, and delete as much dead
133 code as possible, in order to reduce false positives. We also look
134 again for plain uninitialized variables, since optimization may have
135 changed conditionally uninitialized to unconditionally uninitialized. */
137 /* Emit a warning for EXPR based on variable VAR at the point in the
138 program T, an SSA_NAME, is used being uninitialized. The exact
139 warning text is in MSGID and DATA is the gimple stmt with info about
140 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
141 gives which argument of the phi node to take the location from. WC
142 is the warning code. */
145 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
146 const char *gmsgid
, void *data
, location_t phiarg_loc
)
148 gimple context
= (gimple
) data
;
149 location_t location
, cfun_loc
;
150 expanded_location xloc
, floc
;
152 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
153 turns in a COMPLEX_EXPR with the not initialized part being
154 set to its previous (undefined) value. */
155 if (is_gimple_assign (context
)
156 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
158 if (!has_undefined_value_p (t
))
161 /* TREE_NO_WARNING either means we already warned, or the front end
162 wishes to suppress the warning. */
164 && (gimple_no_warning_p (context
)
165 || (gimple_assign_single_p (context
)
166 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
167 || TREE_NO_WARNING (expr
))
170 if (context
!= NULL
&& gimple_has_location (context
))
171 location
= gimple_location (context
);
172 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
173 location
= phiarg_loc
;
175 location
= DECL_SOURCE_LOCATION (var
);
176 location
= linemap_resolve_location (line_table
, location
,
177 LRK_SPELLING_LOCATION
,
179 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
180 xloc
= expand_location (location
);
181 floc
= expand_location (cfun_loc
);
182 if (warning_at (location
, wc
, gmsgid
, expr
))
184 TREE_NO_WARNING (expr
) = 1;
186 if (location
== DECL_SOURCE_LOCATION (var
))
188 if (xloc
.file
!= floc
.file
189 || linemap_location_before_p (line_table
,
191 || linemap_location_before_p (line_table
,
192 cfun
->function_end_locus
,
194 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
199 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
201 gimple_stmt_iterator gsi
;
204 FOR_EACH_BB_FN (bb
, cfun
)
206 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
207 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
208 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
210 gimple stmt
= gsi_stmt (gsi
);
215 if (is_gimple_debug (stmt
))
218 /* We only do data flow with SSA_NAMEs, so that's all we
220 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
222 use
= USE_FROM_PTR (use_p
);
224 warn_uninit (OPT_Wuninitialized
, use
,
225 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
226 "%qD is used uninitialized in this function",
227 stmt
, UNKNOWN_LOCATION
);
228 else if (warn_possibly_uninitialized
)
229 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
230 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
231 "%qD may be used uninitialized in this function",
232 stmt
, UNKNOWN_LOCATION
);
235 /* For memory the only cheap thing we can do is see if we
236 have a use of the default def of the virtual operand.
237 ??? Not so cheap would be to use the alias oracle via
238 walk_aliased_vdefs, if we don't find any aliasing vdef
239 warn as is-used-uninitialized, if we don't find an aliasing
240 vdef that kills our use (stmt_kills_ref_p), warn as
241 may-be-used-uninitialized. But this walk is quadratic and
242 so must be limited which means we would miss warning
244 use
= gimple_vuse (stmt
);
246 && gimple_assign_single_p (stmt
)
247 && !gimple_vdef (stmt
)
248 && SSA_NAME_IS_DEFAULT_DEF (use
))
250 tree rhs
= gimple_assign_rhs1 (stmt
);
251 tree base
= get_base_address (rhs
);
253 /* Do not warn if it can be initialized outside this function. */
254 if (TREE_CODE (base
) != VAR_DECL
255 || DECL_HARD_REGISTER (base
)
256 || is_global_var (base
))
260 warn_uninit (OPT_Wuninitialized
, use
,
261 gimple_assign_rhs1 (stmt
), base
,
262 "%qE is used uninitialized in this function",
263 stmt
, UNKNOWN_LOCATION
);
264 else if (warn_possibly_uninitialized
)
265 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
266 gimple_assign_rhs1 (stmt
), base
,
267 "%qE may be used uninitialized in this function",
268 stmt
, UNKNOWN_LOCATION
);
276 /* Checks if the operand OPND of PHI is defined by
277 another phi with one operand defined by this PHI,
278 but the rest operands are all defined. If yes,
279 returns true to skip this this operand as being
280 redundant. Can be enhanced to be more general. */
283 can_skip_redundant_opnd (tree opnd
, gimple phi
)
289 phi_def
= gimple_phi_result (phi
);
290 op_def
= SSA_NAME_DEF_STMT (opnd
);
291 if (gimple_code (op_def
) != GIMPLE_PHI
)
293 n
= gimple_phi_num_args (op_def
);
294 for (i
= 0; i
< n
; ++i
)
296 tree op
= gimple_phi_arg_def (op_def
, i
);
297 if (TREE_CODE (op
) != SSA_NAME
)
299 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
306 /* Returns a bit mask holding the positions of arguments in PHI
307 that have empty (or possibly empty) definitions. */
310 compute_uninit_opnds_pos (gphi
*phi
)
313 unsigned uninit_opnds
= 0;
315 n
= gimple_phi_num_args (phi
);
316 /* Bail out for phi with too many args. */
320 for (i
= 0; i
< n
; ++i
)
322 tree op
= gimple_phi_arg_def (phi
, i
);
323 if (TREE_CODE (op
) == SSA_NAME
324 && uninit_undefined_value_p (op
)
325 && !can_skip_redundant_opnd (op
, phi
))
327 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
329 /* Ignore SSA_NAMEs that appear on abnormal edges
331 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
334 MASK_SET_BIT (uninit_opnds
, i
);
340 /* Find the immediate postdominator PDOM of the specified
341 basic block BLOCK. */
343 static inline basic_block
344 find_pdom (basic_block block
)
346 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
347 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
351 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
353 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
358 /* Find the immediate DOM of the specified
359 basic block BLOCK. */
361 static inline basic_block
362 find_dom (basic_block block
)
364 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
365 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
368 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
370 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
375 /* Returns true if BB1 is postdominating BB2 and BB1 is
376 not a loop exit bb. The loop exit bb check is simple and does
377 not cover all cases. */
380 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
382 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
385 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
391 /* Find the closest postdominator of a specified BB, which is control
394 static inline basic_block
395 find_control_equiv_block (basic_block bb
)
399 pdom
= find_pdom (bb
);
401 /* Skip the postdominating bb that is also loop exit. */
402 if (!is_non_loop_exit_postdominating (pdom
, bb
))
405 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
411 #define MAX_NUM_CHAINS 8
412 #define MAX_CHAIN_LEN 5
413 #define MAX_POSTDOM_CHECK 8
415 /* Computes the control dependence chains (paths of edges)
416 for DEP_BB up to the dominating basic block BB (the head node of a
417 chain should be dominated by it). CD_CHAINS is pointer to an
418 array holding the result chains. CUR_CD_CHAIN is the current
419 chain being computed. *NUM_CHAINS is total number of chains. The
420 function returns true if the information is successfully computed,
421 return false if there is no control dependence or not computed. */
424 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
425 vec
<edge
> *cd_chains
,
427 vec
<edge
> *cur_cd_chain
,
433 bool found_cd_chain
= false;
434 size_t cur_chain_len
= 0;
436 if (EDGE_COUNT (bb
->succs
) < 2)
439 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
443 /* Could use a set instead. */
444 cur_chain_len
= cur_cd_chain
->length ();
445 if (cur_chain_len
> MAX_CHAIN_LEN
)
448 for (i
= 0; i
< cur_chain_len
; i
++)
450 edge e
= (*cur_cd_chain
)[i
];
451 /* Cycle detected. */
456 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
459 int post_dom_check
= 0;
460 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
464 cur_cd_chain
->safe_push (e
);
465 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
469 /* Found a direct control dependence. */
470 if (*num_chains
< MAX_NUM_CHAINS
)
472 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
475 found_cd_chain
= true;
476 /* Check path from next edge. */
480 /* Now check if DEP_BB is indirectly control dependent on BB. */
481 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
482 num_chains
, cur_cd_chain
, num_calls
))
484 found_cd_chain
= true;
488 cd_bb
= find_pdom (cd_bb
);
490 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
494 cur_cd_chain
->pop ();
495 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
497 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
499 return found_cd_chain
;
502 /* The type to represent a simple predicate */
504 typedef struct use_def_pred_info
508 enum tree_code cond_code
;
512 /* The type to represent a sequence of predicates grouped
513 with .AND. operation. */
515 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
517 /* The type to represent a sequence of pred_chains grouped
518 with .OR. operation. */
520 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
522 /* Converts the chains of control dependence edges into a set of
523 predicates. A control dependence chain is represented by a vector
524 edges. DEP_CHAINS points to an array of dependence chains.
525 NUM_CHAINS is the size of the chain array. One edge in a dependence
526 chain is mapped to predicate expression represented by pred_info
527 type. One dependence chain is converted to a composite predicate that
528 is the result of AND operation of pred_info mapped to each edge.
529 A composite predicate is presented by a vector of pred_info. On
530 return, *PREDS points to the resulting array of composite predicates.
531 *NUM_PREDS is the number of composite predictes. */
534 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
536 pred_chain_union
*preds
)
538 bool has_valid_pred
= false;
540 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
543 /* Now convert the control dep chain into a set
545 preds
->reserve (num_chains
);
547 for (i
= 0; i
< num_chains
; i
++)
549 vec
<edge
> one_cd_chain
= dep_chains
[i
];
551 has_valid_pred
= false;
552 pred_chain t_chain
= vNULL
;
553 for (j
= 0; j
< one_cd_chain
.length (); j
++)
556 gimple_stmt_iterator gsi
;
557 basic_block guard_bb
;
563 gsi
= gsi_last_bb (guard_bb
);
566 has_valid_pred
= false;
569 cond_stmt
= gsi_stmt (gsi
);
570 if (is_gimple_call (cond_stmt
)
571 && EDGE_COUNT (e
->src
->succs
) >= 2)
573 /* Ignore EH edge. Can add assertion
574 on the other edge's flag. */
577 /* Skip if there is essentially one succesor. */
578 if (EDGE_COUNT (e
->src
->succs
) == 2)
584 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
586 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
595 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
597 has_valid_pred
= false;
600 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
601 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
602 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
603 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
604 t_chain
.safe_push (one_pred
);
605 has_valid_pred
= true;
611 preds
->safe_push (t_chain
);
613 return has_valid_pred
;
616 /* Computes all control dependence chains for USE_BB. The control
617 dependence chains are then converted to an array of composite
618 predicates pointed to by PREDS. PHI_BB is the basic block of
619 the phi whose result is used in USE_BB. */
622 find_predicates (pred_chain_union
*preds
,
626 size_t num_chains
= 0, i
;
628 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
629 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
630 bool has_valid_pred
= false;
631 basic_block cd_root
= 0;
633 /* First find the closest bb that is control equivalent to PHI_BB
634 that also dominates USE_BB. */
636 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
638 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
639 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
640 cd_root
= ctrl_eq_bb
;
645 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
646 &cur_chain
, &num_calls
);
649 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
650 for (i
= 0; i
< num_chains
; i
++)
651 dep_chains
[i
].release ();
652 return has_valid_pred
;
655 /* Computes the set of incoming edges of PHI that have non empty
656 definitions of a phi chain. The collection will be done
657 recursively on operands that are defined by phis. CD_ROOT
658 is the control dependence root. *EDGES holds the result, and
659 VISITED_PHIS is a pointer set for detecting cycles. */
662 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
664 hash_set
<gimple
> *visited_phis
)
670 if (visited_phis
->add (phi
))
673 n
= gimple_phi_num_args (phi
);
674 for (i
= 0; i
< n
; i
++)
676 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
677 opnd
= gimple_phi_arg_def (phi
, i
);
679 if (TREE_CODE (opnd
) != SSA_NAME
)
681 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
683 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
684 print_gimple_stmt (dump_file
, phi
, 0, 0);
686 edges
->safe_push (opnd_edge
);
690 gimple def
= SSA_NAME_DEF_STMT (opnd
);
692 if (gimple_code (def
) == GIMPLE_PHI
693 && dominated_by_p (CDI_DOMINATORS
,
694 gimple_bb (def
), cd_root
))
695 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
697 else if (!uninit_undefined_value_p (opnd
))
699 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
701 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
702 print_gimple_stmt (dump_file
, phi
, 0, 0);
704 edges
->safe_push (opnd_edge
);
710 /* For each use edge of PHI, computes all control dependence chains.
711 The control dependence chains are then converted to an array of
712 composite predicates pointed to by PREDS. */
715 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
717 size_t num_chains
= 0, i
, n
;
718 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
719 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
720 vec
<edge
> def_edges
= vNULL
;
721 bool has_valid_pred
= false;
722 basic_block phi_bb
, cd_root
= 0;
724 phi_bb
= gimple_bb (phi
);
725 /* First find the closest dominating bb to be
726 the control dependence root */
727 cd_root
= find_dom (phi_bb
);
731 hash_set
<gimple
> visited_phis
;
732 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
734 n
= def_edges
.length ();
738 for (i
= 0; i
< n
; i
++)
744 opnd_edge
= def_edges
[i
];
745 prev_nc
= num_chains
;
746 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
747 &num_chains
, &cur_chain
, &num_calls
);
749 /* Now update the newly added chains with
750 the phi operand edge: */
751 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
753 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
754 dep_chains
[num_chains
++] = vNULL
;
755 for (j
= prev_nc
; j
< num_chains
; j
++)
756 dep_chains
[j
].safe_push (opnd_edge
);
761 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
762 for (i
= 0; i
< num_chains
; i
++)
763 dep_chains
[i
].release ();
764 return has_valid_pred
;
767 /* Dumps the predicates (PREDS) for USESTMT. */
770 dump_predicates (gimple usestmt
, pred_chain_union preds
,
774 pred_chain one_pred_chain
= vNULL
;
775 fprintf (dump_file
, msg
);
776 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
777 fprintf (dump_file
, "is guarded by :\n\n");
778 size_t num_preds
= preds
.length ();
779 /* Do some dumping here: */
780 for (i
= 0; i
< num_preds
; i
++)
784 one_pred_chain
= preds
[i
];
785 np
= one_pred_chain
.length ();
787 for (j
= 0; j
< np
; j
++)
789 pred_info one_pred
= one_pred_chain
[j
];
791 fprintf (dump_file
, " (.NOT.) ");
792 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
793 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
794 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
796 fprintf (dump_file
, " (.AND.) ");
798 fprintf (dump_file
, "\n");
800 if (i
< num_preds
- 1)
801 fprintf (dump_file
, "(.OR.)\n");
803 fprintf (dump_file
, "\n\n");
807 /* Destroys the predicate set *PREDS. */
810 destroy_predicate_vecs (pred_chain_union preds
)
814 size_t n
= preds
.length ();
815 for (i
= 0; i
< n
; i
++)
821 /* Computes the 'normalized' conditional code with operand
822 swapping and condition inversion. */
824 static enum tree_code
825 get_cmp_code (enum tree_code orig_cmp_code
,
826 bool swap_cond
, bool invert
)
828 enum tree_code tc
= orig_cmp_code
;
831 tc
= swap_tree_comparison (orig_cmp_code
);
833 tc
= invert_tree_comparison (tc
, false);
850 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
851 all values in the range satisfies (x CMPC BOUNDARY) == true. */
854 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
856 bool inverted
= false;
860 /* Only handle integer constant here. */
861 if (TREE_CODE (val
) != INTEGER_CST
862 || TREE_CODE (boundary
) != INTEGER_CST
)
865 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
867 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
870 cmpc
= invert_tree_comparison (cmpc
, false);
877 result
= tree_int_cst_equal (val
, boundary
);
878 else if (cmpc
== LT_EXPR
)
879 result
= tree_int_cst_lt (val
, boundary
);
882 gcc_assert (cmpc
== LE_EXPR
);
883 result
= tree_int_cst_le (val
, boundary
);
889 result
= tree_int_cst_equal (val
, boundary
);
890 else if (cmpc
== LT_EXPR
)
891 result
= tree_int_cst_lt (val
, boundary
);
894 gcc_assert (cmpc
== LE_EXPR
);
895 result
= (tree_int_cst_equal (val
, boundary
)
896 || tree_int_cst_lt (val
, boundary
));
906 /* Returns true if PRED is common among all the predicate
907 chains (PREDS) (and therefore can be factored out).
908 NUM_PRED_CHAIN is the size of array PREDS. */
911 find_matching_predicate_in_rest_chains (pred_info pred
,
912 pred_chain_union preds
,
913 size_t num_pred_chains
)
918 if (num_pred_chains
== 1)
921 for (i
= 1; i
< num_pred_chains
; i
++)
924 pred_chain one_chain
= preds
[i
];
925 n
= one_chain
.length ();
926 for (j
= 0; j
< n
; j
++)
928 pred_info pred2
= one_chain
[j
];
929 /* Can relax the condition comparison to not
930 use address comparison. However, the most common
931 case is that multiple control dependent paths share
932 a common path prefix, so address comparison should
935 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
936 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
937 && pred2
.invert
== pred
.invert
)
949 /* Forward declaration. */
951 is_use_properly_guarded (gimple use_stmt
,
954 unsigned uninit_opnds
,
955 hash_set
<gphi
*> *visited_phis
);
957 /* Returns true if all uninitialized opnds are pruned. Returns false
958 otherwise. PHI is the phi node with uninitialized operands,
959 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
960 FLAG_DEF is the statement defining the flag guarding the use of the
961 PHI output, BOUNDARY_CST is the const value used in the predicate
962 associated with the flag, CMP_CODE is the comparison code used in
963 the predicate, VISITED_PHIS is the pointer set of phis visited, and
964 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
970 flag_1 = phi <0, 1> // (1)
971 var_1 = phi <undef, some_val>
975 flag_2 = phi <0, flag_1, flag_1> // (2)
976 var_2 = phi <undef, var_1, var_1>
983 Because some flag arg in (1) is not constant, if we do not look into the
984 flag phis recursively, it is conservatively treated as unknown and var_1
985 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
986 a false warning will be emitted. Checking recursively into (1), the compiler can
987 find out that only some_val (which is defined) can flow into (3) which is OK.
992 prune_uninit_phi_opnds_in_unrealizable_paths (gphi
*phi
,
993 unsigned uninit_opnds
,
996 enum tree_code cmp_code
,
997 hash_set
<gphi
*> *visited_phis
,
998 bitmap
*visited_flag_phis
)
1002 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
1006 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1009 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1010 if (!is_gimple_constant (flag_arg
))
1012 gphi
*flag_arg_def
, *phi_arg_def
;
1014 unsigned uninit_opnds_arg_phi
;
1016 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1018 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1022 phi_arg
= gimple_phi_arg_def (phi
, i
);
1023 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1026 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1030 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1033 if (!*visited_flag_phis
)
1034 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1036 if (bitmap_bit_p (*visited_flag_phis
,
1037 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1040 bitmap_set_bit (*visited_flag_phis
,
1041 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1043 /* Now recursively prune the uninitialized phi args. */
1044 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1045 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1046 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1047 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1050 bitmap_clear_bit (*visited_flag_phis
,
1051 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1055 /* Now check if the constant is in the guarded range. */
1056 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1061 /* Now that we know that this undefined edge is not
1062 pruned. If the operand is defined by another phi,
1063 we can further prune the incoming edges of that
1064 phi by checking the predicates of this operands. */
1066 opnd
= gimple_phi_arg_def (phi
, i
);
1067 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1068 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1071 unsigned uninit_opnds2
1072 = compute_uninit_opnds_pos (opnd_def_phi
);
1073 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
1074 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1075 if (!is_use_properly_guarded (phi
,
1090 /* A helper function that determines if the predicate set
1091 of the use is not overlapping with that of the uninit paths.
1092 The most common senario of guarded use is in Example 1:
1105 The real world examples are usually more complicated, but similar
1106 and usually result from inlining:
1108 bool init_func (int * x)
1127 Another possible use scenario is in the following trivial example:
1139 Predicate analysis needs to compute the composite predicate:
1141 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1142 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1143 (the predicate chain for phi operand defs can be computed
1144 starting from a bb that is control equivalent to the phi's
1145 bb and is dominating the operand def.)
1147 and check overlapping:
1148 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1151 This implementation provides framework that can handle
1152 scenarios. (Note that many simple cases are handled properly
1153 without the predicate analysis -- this is due to jump threading
1154 transformation which eliminates the merge point thus makes
1155 path sensitive analysis unnecessary.)
1157 NUM_PREDS is the number is the number predicate chains, PREDS is
1158 the array of chains, PHI is the phi node whose incoming (undefined)
1159 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1160 uninit operand positions. VISITED_PHIS is the pointer set of phi
1161 stmts being checked. */
1165 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1166 gphi
*phi
, unsigned uninit_opnds
,
1167 hash_set
<gphi
*> *visited_phis
)
1170 gimple flag_def
= 0;
1171 tree boundary_cst
= 0;
1172 enum tree_code cmp_code
;
1173 bool swap_cond
= false;
1174 bool invert
= false;
1175 pred_chain the_pred_chain
= vNULL
;
1176 bitmap visited_flag_phis
= NULL
;
1177 bool all_pruned
= false;
1178 size_t num_preds
= preds
.length ();
1180 gcc_assert (num_preds
> 0);
1181 /* Find within the common prefix of multiple predicate chains
1182 a predicate that is a comparison of a flag variable against
1184 the_pred_chain
= preds
[0];
1185 n
= the_pred_chain
.length ();
1186 for (i
= 0; i
< n
; i
++)
1188 tree cond_lhs
, cond_rhs
, flag
= 0;
1190 pred_info the_pred
= the_pred_chain
[i
];
1192 invert
= the_pred
.invert
;
1193 cond_lhs
= the_pred
.pred_lhs
;
1194 cond_rhs
= the_pred
.pred_rhs
;
1195 cmp_code
= the_pred
.cond_code
;
1197 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1198 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1200 boundary_cst
= cond_rhs
;
1203 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1204 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1206 boundary_cst
= cond_lhs
;
1214 flag_def
= SSA_NAME_DEF_STMT (flag
);
1219 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1220 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1221 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1231 /* Now check all the uninit incoming edge has a constant flag value
1232 that is in conflict with the use guard/predicate. */
1233 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1235 if (cmp_code
== ERROR_MARK
)
1238 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1240 as_a
<gphi
*> (flag_def
),
1244 &visited_flag_phis
);
1246 if (visited_flag_phis
)
1247 BITMAP_FREE (visited_flag_phis
);
1252 /* The helper function returns true if two predicates X1 and X2
1253 are equivalent. It assumes the expressions have already
1254 properly re-associated. */
1257 pred_equal_p (pred_info x1
, pred_info x2
)
1259 enum tree_code c1
, c2
;
1260 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1261 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1265 if (x1
.invert
!= x2
.invert
)
1266 c2
= invert_tree_comparison (x2
.cond_code
, false);
1273 /* Returns true if the predication is testing !=. */
1276 is_neq_relop_p (pred_info pred
)
1279 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1280 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1283 /* Returns true if pred is of the form X != 0. */
1286 is_neq_zero_form_p (pred_info pred
)
1288 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1289 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1294 /* The helper function returns true if two predicates X1
1295 is equivalent to X2 != 0. */
1298 pred_expr_equal_p (pred_info x1
, tree x2
)
1300 if (!is_neq_zero_form_p (x1
))
1303 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1306 /* Returns true of the domain of single predicate expression
1307 EXPR1 is a subset of that of EXPR2. Returns false if it
1308 can not be proved. */
1311 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1313 enum tree_code code1
, code2
;
1315 if (pred_equal_p (expr1
, expr2
))
1318 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1319 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1322 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1325 code1
= expr1
.cond_code
;
1327 code1
= invert_tree_comparison (code1
, false);
1328 code2
= expr2
.cond_code
;
1330 code2
= invert_tree_comparison (code2
, false);
1332 if (code1
!= code2
&& code2
!= NE_EXPR
)
1335 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1341 /* Returns true if the domain of PRED1 is a subset
1342 of that of PRED2. Returns false if it can not be proved so. */
1345 is_pred_chain_subset_of (pred_chain pred1
,
1348 size_t np1
, np2
, i1
, i2
;
1350 np1
= pred1
.length ();
1351 np2
= pred2
.length ();
1353 for (i2
= 0; i2
< np2
; i2
++)
1356 pred_info info2
= pred2
[i2
];
1357 for (i1
= 0; i1
< np1
; i1
++)
1359 pred_info info1
= pred1
[i1
];
1360 if (is_pred_expr_subset_of (info1
, info2
))
1372 /* Returns true if the domain defined by
1373 one pred chain ONE_PRED is a subset of the domain
1374 of *PREDS. It returns false if ONE_PRED's domain is
1375 not a subset of any of the sub-domains of PREDS
1376 (corresponding to each individual chains in it), even
1377 though it may be still be a subset of whole domain
1378 of PREDS which is the union (ORed) of all its subdomains.
1379 In other words, the result is conservative. */
1382 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1385 size_t n
= preds
.length ();
1387 for (i
= 0; i
< n
; i
++)
1389 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1396 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1397 true if the domain defined by PREDS1 is a superset
1398 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1399 PREDS2 respectively. The implementation chooses not to build
1400 generic trees (and relying on the folding capability of the
1401 compiler), but instead performs brute force comparison of
1402 individual predicate chains (won't be a compile time problem
1403 as the chains are pretty short). When the function returns
1404 false, it does not necessarily mean *PREDS1 is not a superset
1405 of *PREDS2, but mean it may not be so since the analysis can
1406 not prove it. In such cases, false warnings may still be
1410 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1413 pred_chain one_pred_chain
= vNULL
;
1415 n2
= preds2
.length ();
1417 for (i
= 0; i
< n2
; i
++)
1419 one_pred_chain
= preds2
[i
];
1420 if (!is_included_in (one_pred_chain
, preds1
))
1427 /* Returns true if TC is AND or OR. */
1430 is_and_or_or_p (enum tree_code tc
, tree type
)
1432 return (tc
== BIT_IOR_EXPR
1433 || (tc
== BIT_AND_EXPR
1434 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1437 /* Returns true if X1 is the negate of X2. */
1440 pred_neg_p (pred_info x1
, pred_info x2
)
1442 enum tree_code c1
, c2
;
1443 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1444 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1448 if (x1
.invert
== x2
.invert
)
1449 c2
= invert_tree_comparison (x2
.cond_code
, false);
1456 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1457 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1458 3) X OR (!X AND Y) is equivalent to (X OR Y);
1459 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1461 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1464 PREDS is the predicate chains, and N is the number of chains. */
1466 /* Helper function to implement rule 1 above. ONE_CHAIN is
1467 the AND predication to be simplified. */
1470 simplify_pred (pred_chain
*one_chain
)
1473 bool simplified
= false;
1474 pred_chain s_chain
= vNULL
;
1476 n
= one_chain
->length ();
1478 for (i
= 0; i
< n
; i
++)
1480 pred_info
*a_pred
= &(*one_chain
)[i
];
1482 if (!a_pred
->pred_lhs
)
1484 if (!is_neq_zero_form_p (*a_pred
))
1487 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1488 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1490 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1492 for (j
= 0; j
< n
; j
++)
1494 pred_info
*b_pred
= &(*one_chain
)[j
];
1496 if (!b_pred
->pred_lhs
)
1498 if (!is_neq_zero_form_p (*b_pred
))
1501 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1502 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1504 /* Mark a_pred for removal. */
1505 a_pred
->pred_lhs
= NULL
;
1506 a_pred
->pred_rhs
= NULL
;
1517 for (i
= 0; i
< n
; i
++)
1519 pred_info
*a_pred
= &(*one_chain
)[i
];
1520 if (!a_pred
->pred_lhs
)
1522 s_chain
.safe_push (*a_pred
);
1525 one_chain
->release ();
1526 *one_chain
= s_chain
;
1529 /* The helper function implements the rule 2 for the
1532 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1535 simplify_preds_2 (pred_chain_union
*preds
)
1538 bool simplified
= false;
1539 pred_chain_union s_preds
= vNULL
;
1541 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1542 (X AND Y) OR (X AND !Y) is equivalent to X. */
1544 n
= preds
->length ();
1545 for (i
= 0; i
< n
; i
++)
1548 pred_chain
*a_chain
= &(*preds
)[i
];
1550 if (a_chain
->length () != 2)
1556 for (j
= 0; j
< n
; j
++)
1558 pred_chain
*b_chain
;
1564 b_chain
= &(*preds
)[j
];
1565 if (b_chain
->length () != 2)
1571 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1574 a_chain
->release ();
1575 b_chain
->release ();
1576 b_chain
->safe_push (x
);
1580 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1583 a_chain
->release ();
1584 b_chain
->release ();
1585 b_chain
->safe_push (y
);
1591 /* Now clean up the chain. */
1594 for (i
= 0; i
< n
; i
++)
1596 if ((*preds
)[i
].is_empty ())
1598 s_preds
.safe_push ((*preds
)[i
]);
1608 /* The helper function implements the rule 2 for the
1611 3) x OR (!x AND y) is equivalent to x OR y. */
1614 simplify_preds_3 (pred_chain_union
*preds
)
1617 bool simplified
= false;
1619 /* Now iteratively simplify X OR (!X AND Z ..)
1620 into X OR (Z ...). */
1622 n
= preds
->length ();
1626 for (i
= 0; i
< n
; i
++)
1629 pred_chain
*a_chain
= &(*preds
)[i
];
1631 if (a_chain
->length () != 1)
1636 for (j
= 0; j
< n
; j
++)
1638 pred_chain
*b_chain
;
1645 b_chain
= &(*preds
)[j
];
1646 if (b_chain
->length () < 2)
1649 for (k
= 0; k
< b_chain
->length (); k
++)
1652 if (pred_neg_p (x
, x2
))
1654 b_chain
->unordered_remove (k
);
1664 /* The helper function implements the rule 4 for the
1667 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1668 (x != 0 ANd y != 0). */
1671 simplify_preds_4 (pred_chain_union
*preds
)
1674 bool simplified
= false;
1675 pred_chain_union s_preds
= vNULL
;
1678 n
= preds
->length ();
1679 for (i
= 0; i
< n
; i
++)
1682 pred_chain
*a_chain
= &(*preds
)[i
];
1684 if (a_chain
->length () != 1)
1689 if (!is_neq_zero_form_p (z
))
1692 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1693 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1696 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1699 for (j
= 0; j
< n
; j
++)
1701 pred_chain
*b_chain
;
1707 b_chain
= &(*preds
)[j
];
1708 if (b_chain
->length () != 2)
1713 if (!is_neq_zero_form_p (x2
)
1714 || !is_neq_zero_form_p (y2
))
1717 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1718 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1719 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1720 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1723 a_chain
->release ();
1729 /* Now clean up the chain. */
1732 for (i
= 0; i
< n
; i
++)
1734 if ((*preds
)[i
].is_empty ())
1736 s_preds
.safe_push ((*preds
)[i
]);
1747 /* This function simplifies predicates in PREDS. */
1750 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1753 bool changed
= false;
1755 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1757 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1758 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1761 for (i
= 0; i
< preds
->length (); i
++)
1762 simplify_pred (&(*preds
)[i
]);
1764 n
= preds
->length ();
1771 if (simplify_preds_2 (preds
))
1774 /* Now iteratively simplify X OR (!X AND Z ..)
1775 into X OR (Z ...). */
1776 if (simplify_preds_3 (preds
))
1779 if (simplify_preds_4 (preds
))
1787 /* This is a helper function which attempts to normalize predicate chains
1788 by following UD chains. It basically builds up a big tree of either IOR
1789 operations or AND operations, and convert the IOR tree into a
1790 pred_chain_union or BIT_AND tree into a pred_chain.
1800 then _t != 0 will be normalized into a pred_chain_union
1802 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1812 then _t != 0 will be normalized into a pred_chain:
1813 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1817 /* This is a helper function that stores a PRED into NORM_PREDS. */
1820 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1822 pred_chain pred_chain
= vNULL
;
1823 pred_chain
.safe_push (pred
);
1824 norm_preds
->safe_push (pred_chain
);
1827 /* A helper function that creates a predicate of the form
1828 OP != 0 and push it WORK_LIST. */
1831 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1832 hash_set
<tree
> *mark_set
)
1834 if (mark_set
->contains (op
))
1839 arg_pred
.pred_lhs
= op
;
1840 arg_pred
.pred_rhs
= integer_zero_node
;
1841 arg_pred
.cond_code
= NE_EXPR
;
1842 arg_pred
.invert
= false;
1843 work_list
->safe_push (arg_pred
);
1846 /* A helper that generates a pred_info from a gimple assignment
1847 CMP_ASSIGN with comparison rhs. */
1850 get_pred_info_from_cmp (gimple cmp_assign
)
1853 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1854 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1855 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1856 n_pred
.invert
= false;
1860 /* Returns true if the PHI is a degenerated phi with
1861 all args with the same value (relop). In that case, *PRED
1862 will be updated to that value. */
1865 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1872 n
= gimple_phi_num_args (phi
);
1873 op0
= gimple_phi_arg_def (phi
, 0);
1875 if (TREE_CODE (op0
) != SSA_NAME
)
1878 def0
= SSA_NAME_DEF_STMT (op0
);
1879 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1881 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1884 pred0
= get_pred_info_from_cmp (def0
);
1886 for (i
= 1; i
< n
; ++i
)
1890 tree op
= gimple_phi_arg_def (phi
, i
);
1892 if (TREE_CODE (op
) != SSA_NAME
)
1895 def
= SSA_NAME_DEF_STMT (op
);
1896 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1898 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1901 pred
= get_pred_info_from_cmp (def
);
1902 if (!pred_equal_p (pred
, pred0
))
1910 /* Normalize one predicate PRED
1911 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1912 2) otherwise if PRED is of the form x != 0, follow x's definition
1913 and put normalized predicates into WORK_LIST. */
1916 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1917 pred_chain
*norm_chain
,
1919 enum tree_code and_or_code
,
1920 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1921 hash_set
<tree
> *mark_set
)
1923 if (!is_neq_zero_form_p (pred
))
1925 if (and_or_code
== BIT_IOR_EXPR
)
1926 push_pred (norm_preds
, pred
);
1928 norm_chain
->safe_push (pred
);
1932 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1934 if (gimple_code (def_stmt
) == GIMPLE_PHI
1935 && is_degenerated_phi (def_stmt
, &pred
))
1936 work_list
->safe_push (pred
);
1937 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1938 && and_or_code
== BIT_IOR_EXPR
)
1941 n
= gimple_phi_num_args (def_stmt
);
1943 /* If we see non zero constant, we should punt. The predicate
1944 * should be one guarding the phi edge. */
1945 for (i
= 0; i
< n
; ++i
)
1947 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1948 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1950 push_pred (norm_preds
, pred
);
1955 for (i
= 0; i
< n
; ++i
)
1957 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1958 if (integer_zerop (op
))
1961 push_to_worklist (op
, work_list
, mark_set
);
1964 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1966 if (and_or_code
== BIT_IOR_EXPR
)
1967 push_pred (norm_preds
, pred
);
1969 norm_chain
->safe_push (pred
);
1971 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
1973 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
1974 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
1976 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
1979 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
1980 if (and_or_code
== BIT_IOR_EXPR
)
1981 push_pred (norm_preds
, n_pred
);
1983 norm_chain
->safe_push (n_pred
);
1987 if (and_or_code
== BIT_IOR_EXPR
)
1988 push_pred (norm_preds
, pred
);
1990 norm_chain
->safe_push (pred
);
1994 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1997 normalize_one_pred (pred_chain_union
*norm_preds
,
2000 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2001 enum tree_code and_or_code
= ERROR_MARK
;
2002 pred_chain norm_chain
= vNULL
;
2004 if (!is_neq_zero_form_p (pred
))
2006 push_pred (norm_preds
, pred
);
2010 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2011 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2012 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2013 if (and_or_code
!= BIT_IOR_EXPR
2014 && and_or_code
!= BIT_AND_EXPR
)
2016 if (TREE_CODE_CLASS (and_or_code
)
2019 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2020 push_pred (norm_preds
, n_pred
);
2023 push_pred (norm_preds
, pred
);
2027 work_list
.safe_push (pred
);
2028 hash_set
<tree
> mark_set
;
2030 while (!work_list
.is_empty ())
2032 pred_info a_pred
= work_list
.pop ();
2033 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2034 and_or_code
, &work_list
, &mark_set
);
2036 if (and_or_code
== BIT_AND_EXPR
)
2037 norm_preds
->safe_push (norm_chain
);
2039 work_list
.release ();
2043 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2044 pred_chain one_chain
)
2046 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2047 hash_set
<tree
> mark_set
;
2048 pred_chain norm_chain
= vNULL
;
2051 for (i
= 0; i
< one_chain
.length (); i
++)
2053 work_list
.safe_push (one_chain
[i
]);
2054 mark_set
.add (one_chain
[i
].pred_lhs
);
2057 while (!work_list
.is_empty ())
2059 pred_info a_pred
= work_list
.pop ();
2060 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2061 BIT_AND_EXPR
, &work_list
, &mark_set
);
2064 norm_preds
->safe_push (norm_chain
);
2065 work_list
.release ();
2068 /* Normalize predicate chains PREDS and returns the normalized one. */
2070 static pred_chain_union
2071 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2073 pred_chain_union norm_preds
= vNULL
;
2074 size_t n
= preds
.length ();
2077 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2079 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2080 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2083 for (i
= 0; i
< n
; i
++)
2085 if (preds
[i
].length () != 1)
2086 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2089 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2090 preds
[i
].release ();
2096 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2097 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2105 /* Computes the predicates that guard the use and checks
2106 if the incoming paths that have empty (or possibly
2107 empty) definition can be pruned/filtered. The function returns
2108 true if it can be determined that the use of PHI's def in
2109 USE_STMT is guarded with a predicate set not overlapping with
2110 predicate sets of all runtime paths that do not have a definition.
2111 Returns false if it is not or it can not be determined. USE_BB is
2112 the bb of the use (for phi operand use, the bb is not the bb of
2113 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2114 is a bit vector. If an operand of PHI is uninitialized, the
2115 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2116 set of phis being visted. */
2119 is_use_properly_guarded (gimple use_stmt
,
2122 unsigned uninit_opnds
,
2123 hash_set
<gphi
*> *visited_phis
)
2126 pred_chain_union preds
= vNULL
;
2127 pred_chain_union def_preds
= vNULL
;
2128 bool has_valid_preds
= false;
2129 bool is_properly_guarded
= false;
2131 if (visited_phis
->add (phi
))
2134 phi_bb
= gimple_bb (phi
);
2136 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2139 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2141 if (!has_valid_preds
)
2143 destroy_predicate_vecs (preds
);
2147 /* Try to prune the dead incoming phi edges. */
2149 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2152 if (is_properly_guarded
)
2154 destroy_predicate_vecs (preds
);
2158 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2160 if (!has_valid_preds
)
2162 destroy_predicate_vecs (preds
);
2163 destroy_predicate_vecs (def_preds
);
2167 simplify_preds (&preds
, use_stmt
, true);
2168 preds
= normalize_preds (preds
, use_stmt
, true);
2170 simplify_preds (&def_preds
, phi
, false);
2171 def_preds
= normalize_preds (def_preds
, phi
, false);
2173 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2175 destroy_predicate_vecs (preds
);
2176 destroy_predicate_vecs (def_preds
);
2177 return is_properly_guarded
;
2180 /* Searches through all uses of a potentially
2181 uninitialized variable defined by PHI and returns a use
2182 statement if the use is not properly guarded. It returns
2183 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2184 holding the position(s) of uninit PHI operands. WORKLIST
2185 is the vector of candidate phis that may be updated by this
2186 function. ADDED_TO_WORKLIST is the pointer set tracking
2187 if the new phi is already in the worklist. */
2190 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2191 vec
<gphi
*> *worklist
,
2192 hash_set
<gphi
*> *added_to_worklist
)
2195 use_operand_p use_p
;
2197 imm_use_iterator iter
;
2199 phi_result
= gimple_phi_result (phi
);
2201 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2205 use_stmt
= USE_STMT (use_p
);
2206 if (is_gimple_debug (use_stmt
))
2209 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2210 use_bb
= gimple_phi_arg_edge (use_phi
,
2211 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2213 use_bb
= gimple_bb (use_stmt
);
2215 hash_set
<gphi
*> visited_phis
;
2216 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2222 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2223 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2225 /* Found one real use, return. */
2226 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2229 /* Found a phi use that is not guarded,
2230 add the phi to the worklist. */
2231 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2235 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2236 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2239 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2240 possibly_undefined_names
->add (phi_result
);
2247 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2248 and gives warning if there exists a runtime path from the entry to a
2249 use of the PHI def that does not contain a definition. In other words,
2250 the warning is on the real use. The more dead paths that can be pruned
2251 by the compiler, the fewer false positives the warning is. WORKLIST
2252 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2253 a pointer set tracking if the new phi is added to the worklist or not. */
2256 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2257 hash_set
<gphi
*> *added_to_worklist
)
2259 unsigned uninit_opnds
;
2260 gimple uninit_use_stmt
= 0;
2265 /* Don't look at virtual operands. */
2266 if (virtual_operand_p (gimple_phi_result (phi
)))
2269 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2271 if (MASK_EMPTY (uninit_opnds
))
2274 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2276 fprintf (dump_file
, "[CHECK]: examining phi: ");
2277 print_gimple_stmt (dump_file
, phi
, 0, 0);
2280 /* Now check if we have any use of the value without proper guard. */
2281 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2282 worklist
, added_to_worklist
);
2284 /* All uses are properly guarded. */
2285 if (!uninit_use_stmt
)
2288 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2289 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2290 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2292 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2293 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2295 loc
= UNKNOWN_LOCATION
;
2296 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2297 SSA_NAME_VAR (uninit_op
),
2298 "%qD may be used uninitialized in this function",
2299 uninit_use_stmt
, loc
);
2304 gate_warn_uninitialized (void)
2306 return warn_uninitialized
|| warn_maybe_uninitialized
;
2311 const pass_data pass_data_late_warn_uninitialized
=
2313 GIMPLE_PASS
, /* type */
2314 "uninit", /* name */
2315 OPTGROUP_NONE
, /* optinfo_flags */
2316 TV_NONE
, /* tv_id */
2317 PROP_ssa
, /* properties_required */
2318 0, /* properties_provided */
2319 0, /* properties_destroyed */
2320 0, /* todo_flags_start */
2321 0, /* todo_flags_finish */
2324 class pass_late_warn_uninitialized
: public gimple_opt_pass
2327 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2328 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2331 /* opt_pass methods: */
2332 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2333 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2334 virtual unsigned int execute (function
*);
2336 }; // class pass_late_warn_uninitialized
2339 pass_late_warn_uninitialized::execute (function
*fun
)
2343 vec
<gphi
*> worklist
= vNULL
;
2345 calculate_dominance_info (CDI_DOMINATORS
);
2346 calculate_dominance_info (CDI_POST_DOMINATORS
);
2347 /* Re-do the plain uninitialized variable check, as optimization may have
2348 straightened control flow. Do this first so that we don't accidentally
2349 get a "may be" warning when we'd have seen an "is" warning later. */
2350 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2352 timevar_push (TV_TREE_UNINIT
);
2354 possibly_undefined_names
= new hash_set
<tree
>;
2355 hash_set
<gphi
*> added_to_worklist
;
2357 /* Initialize worklist */
2358 FOR_EACH_BB_FN (bb
, fun
)
2359 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2361 gphi
*phi
= gsi
.phi ();
2364 n
= gimple_phi_num_args (phi
);
2366 /* Don't look at virtual operands. */
2367 if (virtual_operand_p (gimple_phi_result (phi
)))
2370 for (i
= 0; i
< n
; ++i
)
2372 tree op
= gimple_phi_arg_def (phi
, i
);
2373 if (TREE_CODE (op
) == SSA_NAME
2374 && uninit_undefined_value_p (op
))
2376 worklist
.safe_push (phi
);
2377 added_to_worklist
.add (phi
);
2378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2380 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2381 print_gimple_stmt (dump_file
, phi
, 0, 0);
2388 while (worklist
.length () != 0)
2391 cur_phi
= worklist
.pop ();
2392 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2395 worklist
.release ();
2396 delete possibly_undefined_names
;
2397 possibly_undefined_names
= NULL
;
2398 free_dominance_info (CDI_POST_DOMINATORS
);
2399 timevar_pop (TV_TREE_UNINIT
);
2406 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2408 return new pass_late_warn_uninitialized (ctxt
);
2413 execute_early_warn_uninitialized (void)
2415 /* Currently, this pass runs always but
2416 execute_late_warn_uninitialized only runs with optimization. With
2417 optimization we want to warn about possible uninitialized as late
2418 as possible, thus don't do it here. However, without
2419 optimization we need to warn here about "may be uninitialized". */
2420 calculate_dominance_info (CDI_POST_DOMINATORS
);
2422 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2424 /* Post-dominator information can not be reliably updated. Free it
2427 free_dominance_info (CDI_POST_DOMINATORS
);
2434 const pass_data pass_data_early_warn_uninitialized
=
2436 GIMPLE_PASS
, /* type */
2437 "*early_warn_uninitialized", /* name */
2438 OPTGROUP_NONE
, /* optinfo_flags */
2439 TV_TREE_UNINIT
, /* tv_id */
2440 PROP_ssa
, /* properties_required */
2441 0, /* properties_provided */
2442 0, /* properties_destroyed */
2443 0, /* todo_flags_start */
2444 0, /* todo_flags_finish */
2447 class pass_early_warn_uninitialized
: public gimple_opt_pass
2450 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2451 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2454 /* opt_pass methods: */
2455 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2456 virtual unsigned int execute (function
*)
2458 return execute_early_warn_uninitialized ();
2461 }; // class pass_early_warn_uninitialized
2466 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2468 return new pass_early_warn_uninitialized (ctxt
);