1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2014 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 "basic-block.h"
30 #include "gimple-pretty-print.h"
32 #include "pointer-set.h"
33 #include "tree-ssa-alias.h"
34 #include "internal-fn.h"
35 #include "gimple-expr.h"
38 #include "gimple-iterator.h"
39 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
43 #include "tree-inline.h"
45 #include "tree-pass.h"
46 #include "diagnostic-core.h"
49 /* This implements the pass that does predicate aware warning on uses of
50 possibly uninitialized variables. The pass first collects the set of
51 possibly uninitialized SSA names. For each such name, it walks through
52 all its immediate uses. For each immediate use, it rebuilds the condition
53 expression (the predicate) that guards the use. The predicate is then
54 examined to see if the variable is always defined under that same condition.
55 This is done either by pruning the unrealizable paths that lead to the
56 default definitions or by checking if the predicate set that guards the
57 defining paths is a superset of the use predicate. */
60 /* Pointer set of potentially undefined ssa names, i.e.,
61 ssa names that are defined by phi with operands that
62 are not defined or potentially undefined. */
63 static pointer_set_t
*possibly_undefined_names
= 0;
65 /* Bit mask handling macros. */
66 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
67 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
68 #define MASK_EMPTY(mask) (mask == 0)
70 /* Returns the first bit position (starting from LSB)
71 in mask that is non zero. Returns -1 if the mask is empty. */
73 get_mask_first_set_bit (unsigned mask
)
79 while ((mask
& (1 << pos
)) == 0)
84 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
86 /* Return true if T, an SSA_NAME, has an undefined value. */
88 has_undefined_value_p (tree t
)
90 return (ssa_undefined_value_p (t
)
91 || (possibly_undefined_names
92 && pointer_set_contains (possibly_undefined_names
, t
)));
97 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
98 is set on SSA_NAME_VAR. */
101 uninit_undefined_value_p (tree t
) {
102 if (!has_undefined_value_p (t
))
104 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
109 /* Emit warnings for uninitialized variables. This is done in two passes.
111 The first pass notices real uses of SSA names with undefined values.
112 Such uses are unconditionally uninitialized, and we can be certain that
113 such a use is a mistake. This pass is run before most optimizations,
114 so that we catch as many as we can.
116 The second pass follows PHI nodes to find uses that are potentially
117 uninitialized. In this case we can't necessarily prove that the use
118 is really uninitialized. This pass is run after most optimizations,
119 so that we thread as many jumps and possible, and delete as much dead
120 code as possible, in order to reduce false positives. We also look
121 again for plain uninitialized variables, since optimization may have
122 changed conditionally uninitialized to unconditionally uninitialized. */
124 /* Emit a warning for EXPR based on variable VAR at the point in the
125 program T, an SSA_NAME, is used being uninitialized. The exact
126 warning text is in MSGID and DATA is the gimple stmt with info about
127 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
128 gives which argument of the phi node to take the location from. WC
129 is the warning code. */
132 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
133 const char *gmsgid
, void *data
, location_t phiarg_loc
)
135 gimple context
= (gimple
) data
;
136 location_t location
, cfun_loc
;
137 expanded_location xloc
, floc
;
139 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
140 turns in a COMPLEX_EXPR with the not initialized part being
141 set to its previous (undefined) value. */
142 if (is_gimple_assign (context
)
143 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
145 if (!has_undefined_value_p (t
))
148 /* TREE_NO_WARNING either means we already warned, or the front end
149 wishes to suppress the warning. */
151 && (gimple_no_warning_p (context
)
152 || (gimple_assign_single_p (context
)
153 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
154 || TREE_NO_WARNING (expr
))
157 if (context
!= NULL
&& gimple_has_location (context
))
158 location
= gimple_location (context
);
159 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
160 location
= phiarg_loc
;
162 location
= DECL_SOURCE_LOCATION (var
);
163 location
= linemap_resolve_location (line_table
, location
,
164 LRK_SPELLING_LOCATION
,
166 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
167 xloc
= expand_location (location
);
168 floc
= expand_location (cfun_loc
);
169 if (warning_at (location
, wc
, gmsgid
, expr
))
171 TREE_NO_WARNING (expr
) = 1;
173 if (location
== DECL_SOURCE_LOCATION (var
))
175 if (xloc
.file
!= floc
.file
176 || linemap_location_before_p (line_table
,
178 || linemap_location_before_p (line_table
,
179 cfun
->function_end_locus
,
181 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
186 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
188 gimple_stmt_iterator gsi
;
191 FOR_EACH_BB_FN (bb
, cfun
)
193 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
194 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
195 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
197 gimple stmt
= gsi_stmt (gsi
);
202 if (is_gimple_debug (stmt
))
205 /* We only do data flow with SSA_NAMEs, so that's all we
207 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
209 use
= USE_FROM_PTR (use_p
);
211 warn_uninit (OPT_Wuninitialized
, use
,
212 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
213 "%qD is used uninitialized in this function",
214 stmt
, UNKNOWN_LOCATION
);
215 else if (warn_possibly_uninitialized
)
216 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
217 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
218 "%qD may be used uninitialized in this function",
219 stmt
, UNKNOWN_LOCATION
);
222 /* For memory the only cheap thing we can do is see if we
223 have a use of the default def of the virtual operand.
224 ??? Not so cheap would be to use the alias oracle via
225 walk_aliased_vdefs, if we don't find any aliasing vdef
226 warn as is-used-uninitialized, if we don't find an aliasing
227 vdef that kills our use (stmt_kills_ref_p), warn as
228 may-be-used-uninitialized. But this walk is quadratic and
229 so must be limited which means we would miss warning
231 use
= gimple_vuse (stmt
);
233 && gimple_assign_single_p (stmt
)
234 && !gimple_vdef (stmt
)
235 && SSA_NAME_IS_DEFAULT_DEF (use
))
237 tree rhs
= gimple_assign_rhs1 (stmt
);
238 tree base
= get_base_address (rhs
);
240 /* Do not warn if it can be initialized outside this function. */
241 if (TREE_CODE (base
) != VAR_DECL
242 || DECL_HARD_REGISTER (base
)
243 || is_global_var (base
))
247 warn_uninit (OPT_Wuninitialized
, use
,
248 gimple_assign_rhs1 (stmt
), base
,
249 "%qE is used uninitialized in this function",
250 stmt
, UNKNOWN_LOCATION
);
251 else if (warn_possibly_uninitialized
)
252 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
253 gimple_assign_rhs1 (stmt
), base
,
254 "%qE may be used uninitialized in this function",
255 stmt
, UNKNOWN_LOCATION
);
263 /* Checks if the operand OPND of PHI is defined by
264 another phi with one operand defined by this PHI,
265 but the rest operands are all defined. If yes,
266 returns true to skip this this operand as being
267 redundant. Can be enhanced to be more general. */
270 can_skip_redundant_opnd (tree opnd
, gimple phi
)
276 phi_def
= gimple_phi_result (phi
);
277 op_def
= SSA_NAME_DEF_STMT (opnd
);
278 if (gimple_code (op_def
) != GIMPLE_PHI
)
280 n
= gimple_phi_num_args (op_def
);
281 for (i
= 0; i
< n
; ++i
)
283 tree op
= gimple_phi_arg_def (op_def
, i
);
284 if (TREE_CODE (op
) != SSA_NAME
)
286 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
293 /* Returns a bit mask holding the positions of arguments in PHI
294 that have empty (or possibly empty) definitions. */
297 compute_uninit_opnds_pos (gimple phi
)
300 unsigned uninit_opnds
= 0;
302 n
= gimple_phi_num_args (phi
);
303 /* Bail out for phi with too many args. */
307 for (i
= 0; i
< n
; ++i
)
309 tree op
= gimple_phi_arg_def (phi
, i
);
310 if (TREE_CODE (op
) == SSA_NAME
311 && uninit_undefined_value_p (op
)
312 && !can_skip_redundant_opnd (op
, phi
))
314 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
316 /* Ignore SSA_NAMEs that appear on abnormal edges
318 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
321 MASK_SET_BIT (uninit_opnds
, i
);
327 /* Find the immediate postdominator PDOM of the specified
328 basic block BLOCK. */
330 static inline basic_block
331 find_pdom (basic_block block
)
333 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
334 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
338 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
340 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
345 /* Find the immediate DOM of the specified
346 basic block BLOCK. */
348 static inline basic_block
349 find_dom (basic_block block
)
351 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
352 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
355 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
357 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
362 /* Returns true if BB1 is postdominating BB2 and BB1 is
363 not a loop exit bb. The loop exit bb check is simple and does
364 not cover all cases. */
367 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
369 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
372 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
378 /* Find the closest postdominator of a specified BB, which is control
381 static inline basic_block
382 find_control_equiv_block (basic_block bb
)
386 pdom
= find_pdom (bb
);
388 /* Skip the postdominating bb that is also loop exit. */
389 if (!is_non_loop_exit_postdominating (pdom
, bb
))
392 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
398 #define MAX_NUM_CHAINS 8
399 #define MAX_CHAIN_LEN 5
400 #define MAX_POSTDOM_CHECK 8
402 /* Computes the control dependence chains (paths of edges)
403 for DEP_BB up to the dominating basic block BB (the head node of a
404 chain should be dominated by it). CD_CHAINS is pointer to an
405 array holding the result chains. CUR_CD_CHAIN is the current
406 chain being computed. *NUM_CHAINS is total number of chains. The
407 function returns true if the information is successfully computed,
408 return false if there is no control dependence or not computed. */
411 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
412 vec
<edge
> *cd_chains
,
414 vec
<edge
> *cur_cd_chain
,
420 bool found_cd_chain
= false;
421 size_t cur_chain_len
= 0;
423 if (EDGE_COUNT (bb
->succs
) < 2)
426 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
430 /* Could use a set instead. */
431 cur_chain_len
= cur_cd_chain
->length ();
432 if (cur_chain_len
> MAX_CHAIN_LEN
)
435 for (i
= 0; i
< cur_chain_len
; i
++)
437 edge e
= (*cur_cd_chain
)[i
];
438 /* Cycle detected. */
443 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
446 int post_dom_check
= 0;
447 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
451 cur_cd_chain
->safe_push (e
);
452 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
456 /* Found a direct control dependence. */
457 if (*num_chains
< MAX_NUM_CHAINS
)
459 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
462 found_cd_chain
= true;
463 /* Check path from next edge. */
467 /* Now check if DEP_BB is indirectly control dependent on BB. */
468 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
469 num_chains
, cur_cd_chain
, num_calls
))
471 found_cd_chain
= true;
475 cd_bb
= find_pdom (cd_bb
);
477 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
481 cur_cd_chain
->pop ();
482 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
484 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
486 return found_cd_chain
;
489 /* The type to represent a simple predicate */
491 typedef struct use_def_pred_info
495 enum tree_code cond_code
;
499 /* The type to represent a sequence of predicates grouped
500 with .AND. operation. */
502 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
504 /* The type to represent a sequence of pred_chains grouped
505 with .OR. operation. */
507 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
509 /* Converts the chains of control dependence edges into a set of
510 predicates. A control dependence chain is represented by a vector
511 edges. DEP_CHAINS points to an array of dependence chains.
512 NUM_CHAINS is the size of the chain array. One edge in a dependence
513 chain is mapped to predicate expression represented by pred_info
514 type. One dependence chain is converted to a composite predicate that
515 is the result of AND operation of pred_info mapped to each edge.
516 A composite predicate is presented by a vector of pred_info. On
517 return, *PREDS points to the resulting array of composite predicates.
518 *NUM_PREDS is the number of composite predictes. */
521 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
523 pred_chain_union
*preds
)
525 bool has_valid_pred
= false;
527 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
530 /* Now convert the control dep chain into a set
532 preds
->reserve (num_chains
);
534 for (i
= 0; i
< num_chains
; i
++)
536 vec
<edge
> one_cd_chain
= dep_chains
[i
];
538 has_valid_pred
= false;
539 pred_chain t_chain
= vNULL
;
540 for (j
= 0; j
< one_cd_chain
.length (); j
++)
543 gimple_stmt_iterator gsi
;
544 basic_block guard_bb
;
550 gsi
= gsi_last_bb (guard_bb
);
553 has_valid_pred
= false;
556 cond_stmt
= gsi_stmt (gsi
);
557 if (is_gimple_call (cond_stmt
)
558 && EDGE_COUNT (e
->src
->succs
) >= 2)
560 /* Ignore EH edge. Can add assertion
561 on the other edge's flag. */
564 /* Skip if there is essentially one succesor. */
565 if (EDGE_COUNT (e
->src
->succs
) == 2)
571 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
573 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
582 if (gimple_code (cond_stmt
) != GIMPLE_COND
)
584 has_valid_pred
= false;
587 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
588 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
589 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
590 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
591 t_chain
.safe_push (one_pred
);
592 has_valid_pred
= true;
598 preds
->safe_push (t_chain
);
600 return has_valid_pred
;
603 /* Computes all control dependence chains for USE_BB. The control
604 dependence chains are then converted to an array of composite
605 predicates pointed to by PREDS. PHI_BB is the basic block of
606 the phi whose result is used in USE_BB. */
609 find_predicates (pred_chain_union
*preds
,
613 size_t num_chains
= 0, i
;
615 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
616 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
617 bool has_valid_pred
= false;
618 basic_block cd_root
= 0;
620 /* First find the closest bb that is control equivalent to PHI_BB
621 that also dominates USE_BB. */
623 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
625 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
626 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
627 cd_root
= ctrl_eq_bb
;
632 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
633 &cur_chain
, &num_calls
);
636 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
637 for (i
= 0; i
< num_chains
; i
++)
638 dep_chains
[i
].release ();
639 return has_valid_pred
;
642 /* Computes the set of incoming edges of PHI that have non empty
643 definitions of a phi chain. The collection will be done
644 recursively on operands that are defined by phis. CD_ROOT
645 is the control dependence root. *EDGES holds the result, and
646 VISITED_PHIS is a pointer set for detecting cycles. */
649 collect_phi_def_edges (gimple phi
, basic_block cd_root
,
651 pointer_set_t
*visited_phis
)
657 if (pointer_set_insert (visited_phis
, phi
))
660 n
= gimple_phi_num_args (phi
);
661 for (i
= 0; i
< n
; i
++)
663 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
664 opnd
= gimple_phi_arg_def (phi
, i
);
666 if (TREE_CODE (opnd
) != SSA_NAME
)
668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
670 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
671 print_gimple_stmt (dump_file
, phi
, 0, 0);
673 edges
->safe_push (opnd_edge
);
677 gimple def
= SSA_NAME_DEF_STMT (opnd
);
679 if (gimple_code (def
) == GIMPLE_PHI
680 && dominated_by_p (CDI_DOMINATORS
,
681 gimple_bb (def
), cd_root
))
682 collect_phi_def_edges (def
, cd_root
, edges
,
684 else if (!uninit_undefined_value_p (opnd
))
686 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
688 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
689 print_gimple_stmt (dump_file
, phi
, 0, 0);
691 edges
->safe_push (opnd_edge
);
697 /* For each use edge of PHI, computes all control dependence chains.
698 The control dependence chains are then converted to an array of
699 composite predicates pointed to by PREDS. */
702 find_def_preds (pred_chain_union
*preds
, gimple phi
)
704 size_t num_chains
= 0, i
, n
;
705 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
706 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
707 vec
<edge
> def_edges
= vNULL
;
708 bool has_valid_pred
= false;
709 basic_block phi_bb
, cd_root
= 0;
710 pointer_set_t
*visited_phis
;
712 phi_bb
= gimple_bb (phi
);
713 /* First find the closest dominating bb to be
714 the control dependence root */
715 cd_root
= find_dom (phi_bb
);
719 visited_phis
= pointer_set_create ();
720 collect_phi_def_edges (phi
, cd_root
, &def_edges
, visited_phis
);
721 pointer_set_destroy (visited_phis
);
723 n
= def_edges
.length ();
727 for (i
= 0; i
< n
; i
++)
733 opnd_edge
= def_edges
[i
];
734 prev_nc
= num_chains
;
735 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
736 &num_chains
, &cur_chain
, &num_calls
);
738 /* Now update the newly added chains with
739 the phi operand edge: */
740 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
742 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
743 dep_chains
[num_chains
++] = vNULL
;
744 for (j
= prev_nc
; j
< num_chains
; j
++)
745 dep_chains
[j
].safe_push (opnd_edge
);
750 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
751 for (i
= 0; i
< num_chains
; i
++)
752 dep_chains
[i
].release ();
753 return has_valid_pred
;
756 /* Dumps the predicates (PREDS) for USESTMT. */
759 dump_predicates (gimple usestmt
, pred_chain_union preds
,
763 pred_chain one_pred_chain
= vNULL
;
764 fprintf (dump_file
, msg
);
765 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
766 fprintf (dump_file
, "is guarded by :\n\n");
767 size_t num_preds
= preds
.length ();
768 /* Do some dumping here: */
769 for (i
= 0; i
< num_preds
; i
++)
773 one_pred_chain
= preds
[i
];
774 np
= one_pred_chain
.length ();
776 for (j
= 0; j
< np
; j
++)
778 pred_info one_pred
= one_pred_chain
[j
];
780 fprintf (dump_file
, " (.NOT.) ");
781 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
782 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
783 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
785 fprintf (dump_file
, " (.AND.) ");
787 fprintf (dump_file
, "\n");
789 if (i
< num_preds
- 1)
790 fprintf (dump_file
, "(.OR.)\n");
792 fprintf (dump_file
, "\n\n");
796 /* Destroys the predicate set *PREDS. */
799 destroy_predicate_vecs (pred_chain_union preds
)
803 size_t n
= preds
.length ();
804 for (i
= 0; i
< n
; i
++)
810 /* Computes the 'normalized' conditional code with operand
811 swapping and condition inversion. */
813 static enum tree_code
814 get_cmp_code (enum tree_code orig_cmp_code
,
815 bool swap_cond
, bool invert
)
817 enum tree_code tc
= orig_cmp_code
;
820 tc
= swap_tree_comparison (orig_cmp_code
);
822 tc
= invert_tree_comparison (tc
, false);
839 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
840 all values in the range satisfies (x CMPC BOUNDARY) == true. */
843 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
845 bool inverted
= false;
849 /* Only handle integer constant here. */
850 if (TREE_CODE (val
) != INTEGER_CST
851 || TREE_CODE (boundary
) != INTEGER_CST
)
854 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
856 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
859 cmpc
= invert_tree_comparison (cmpc
, false);
866 result
= tree_int_cst_equal (val
, boundary
);
867 else if (cmpc
== LT_EXPR
)
868 result
= tree_int_cst_lt (val
, boundary
);
871 gcc_assert (cmpc
== LE_EXPR
);
872 result
= tree_int_cst_le (val
, boundary
);
878 result
= tree_int_cst_equal (val
, boundary
);
879 else if (cmpc
== LT_EXPR
)
880 result
= tree_int_cst_lt (val
, boundary
);
883 gcc_assert (cmpc
== LE_EXPR
);
884 result
= (tree_int_cst_equal (val
, boundary
)
885 || tree_int_cst_lt (val
, boundary
));
895 /* Returns true if PRED is common among all the predicate
896 chains (PREDS) (and therefore can be factored out).
897 NUM_PRED_CHAIN is the size of array PREDS. */
900 find_matching_predicate_in_rest_chains (pred_info pred
,
901 pred_chain_union preds
,
902 size_t num_pred_chains
)
907 if (num_pred_chains
== 1)
910 for (i
= 1; i
< num_pred_chains
; i
++)
913 pred_chain one_chain
= preds
[i
];
914 n
= one_chain
.length ();
915 for (j
= 0; j
< n
; j
++)
917 pred_info pred2
= one_chain
[j
];
918 /* Can relax the condition comparison to not
919 use address comparison. However, the most common
920 case is that multiple control dependent paths share
921 a common path prefix, so address comparison should
924 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
925 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
926 && pred2
.invert
== pred
.invert
)
938 /* Forward declaration. */
940 is_use_properly_guarded (gimple use_stmt
,
943 unsigned uninit_opnds
,
944 pointer_set_t
*visited_phis
);
946 /* Returns true if all uninitialized opnds are pruned. Returns false
947 otherwise. PHI is the phi node with uninitialized operands,
948 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
949 FLAG_DEF is the statement defining the flag guarding the use of the
950 PHI output, BOUNDARY_CST is the const value used in the predicate
951 associated with the flag, CMP_CODE is the comparison code used in
952 the predicate, VISITED_PHIS is the pointer set of phis visited, and
953 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
959 flag_1 = phi <0, 1> // (1)
960 var_1 = phi <undef, some_val>
964 flag_2 = phi <0, flag_1, flag_1> // (2)
965 var_2 = phi <undef, var_1, var_1>
972 Because some flag arg in (1) is not constant, if we do not look into the
973 flag phis recursively, it is conservatively treated as unknown and var_1
974 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
975 a false warning will be emitted. Checking recursively into (1), the compiler can
976 find out that only some_val (which is defined) can flow into (3) which is OK.
981 prune_uninit_phi_opnds_in_unrealizable_paths (gimple phi
,
982 unsigned uninit_opnds
,
985 enum tree_code cmp_code
,
986 pointer_set_t
*visited_phis
,
987 bitmap
*visited_flag_phis
)
991 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
995 if (!MASK_TEST_BIT (uninit_opnds
, i
))
998 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
999 if (!is_gimple_constant (flag_arg
))
1001 gimple flag_arg_def
, phi_arg_def
;
1003 unsigned uninit_opnds_arg_phi
;
1005 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1007 flag_arg_def
= SSA_NAME_DEF_STMT (flag_arg
);
1008 if (gimple_code (flag_arg_def
) != GIMPLE_PHI
)
1011 phi_arg
= gimple_phi_arg_def (phi
, i
);
1012 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1015 phi_arg_def
= SSA_NAME_DEF_STMT (phi_arg
);
1016 if (gimple_code (phi_arg_def
) != GIMPLE_PHI
)
1019 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1022 if (!*visited_flag_phis
)
1023 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1025 if (bitmap_bit_p (*visited_flag_phis
,
1026 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1029 bitmap_set_bit (*visited_flag_phis
,
1030 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1032 /* Now recursively prune the uninitialized phi args. */
1033 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1034 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1035 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1036 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1039 bitmap_clear_bit (*visited_flag_phis
,
1040 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1044 /* Now check if the constant is in the guarded range. */
1045 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1050 /* Now that we know that this undefined edge is not
1051 pruned. If the operand is defined by another phi,
1052 we can further prune the incoming edges of that
1053 phi by checking the predicates of this operands. */
1055 opnd
= gimple_phi_arg_def (phi
, i
);
1056 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1057 if (gimple_code (opnd_def
) == GIMPLE_PHI
)
1060 unsigned uninit_opnds2
1061 = compute_uninit_opnds_pos (opnd_def
);
1062 gcc_assert (!MASK_EMPTY (uninit_opnds2
));
1063 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1064 if (!is_use_properly_guarded (phi
,
1079 /* A helper function that determines if the predicate set
1080 of the use is not overlapping with that of the uninit paths.
1081 The most common senario of guarded use is in Example 1:
1094 The real world examples are usually more complicated, but similar
1095 and usually result from inlining:
1097 bool init_func (int * x)
1116 Another possible use scenario is in the following trivial example:
1128 Predicate analysis needs to compute the composite predicate:
1130 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1131 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1132 (the predicate chain for phi operand defs can be computed
1133 starting from a bb that is control equivalent to the phi's
1134 bb and is dominating the operand def.)
1136 and check overlapping:
1137 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1140 This implementation provides framework that can handle
1141 scenarios. (Note that many simple cases are handled properly
1142 without the predicate analysis -- this is due to jump threading
1143 transformation which eliminates the merge point thus makes
1144 path sensitive analysis unnecessary.)
1146 NUM_PREDS is the number is the number predicate chains, PREDS is
1147 the array of chains, PHI is the phi node whose incoming (undefined)
1148 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1149 uninit operand positions. VISITED_PHIS is the pointer set of phi
1150 stmts being checked. */
1154 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1155 gimple phi
, unsigned uninit_opnds
,
1156 pointer_set_t
*visited_phis
)
1159 gimple flag_def
= 0;
1160 tree boundary_cst
= 0;
1161 enum tree_code cmp_code
;
1162 bool swap_cond
= false;
1163 bool invert
= false;
1164 pred_chain the_pred_chain
= vNULL
;
1165 bitmap visited_flag_phis
= NULL
;
1166 bool all_pruned
= false;
1167 size_t num_preds
= preds
.length ();
1169 gcc_assert (num_preds
> 0);
1170 /* Find within the common prefix of multiple predicate chains
1171 a predicate that is a comparison of a flag variable against
1173 the_pred_chain
= preds
[0];
1174 n
= the_pred_chain
.length ();
1175 for (i
= 0; i
< n
; i
++)
1177 tree cond_lhs
, cond_rhs
, flag
= 0;
1179 pred_info the_pred
= the_pred_chain
[i
];
1181 invert
= the_pred
.invert
;
1182 cond_lhs
= the_pred
.pred_lhs
;
1183 cond_rhs
= the_pred
.pred_rhs
;
1184 cmp_code
= the_pred
.cond_code
;
1186 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1187 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1189 boundary_cst
= cond_rhs
;
1192 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1193 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1195 boundary_cst
= cond_lhs
;
1203 flag_def
= SSA_NAME_DEF_STMT (flag
);
1208 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1209 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1210 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1220 /* Now check all the uninit incoming edge has a constant flag value
1221 that is in conflict with the use guard/predicate. */
1222 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1224 if (cmp_code
== ERROR_MARK
)
1227 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1233 &visited_flag_phis
);
1235 if (visited_flag_phis
)
1236 BITMAP_FREE (visited_flag_phis
);
1241 /* The helper function returns true if two predicates X1 and X2
1242 are equivalent. It assumes the expressions have already
1243 properly re-associated. */
1246 pred_equal_p (pred_info x1
, pred_info x2
)
1248 enum tree_code c1
, c2
;
1249 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1250 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1254 if (x1
.invert
!= x2
.invert
)
1255 c2
= invert_tree_comparison (x2
.cond_code
, false);
1262 /* Returns true if the predication is testing !=. */
1265 is_neq_relop_p (pred_info pred
)
1268 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1269 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1272 /* Returns true if pred is of the form X != 0. */
1275 is_neq_zero_form_p (pred_info pred
)
1277 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1278 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1283 /* The helper function returns true if two predicates X1
1284 is equivalent to X2 != 0. */
1287 pred_expr_equal_p (pred_info x1
, tree x2
)
1289 if (!is_neq_zero_form_p (x1
))
1292 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1295 /* Returns true of the domain of single predicate expression
1296 EXPR1 is a subset of that of EXPR2. Returns false if it
1297 can not be proved. */
1300 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1302 enum tree_code code1
, code2
;
1304 if (pred_equal_p (expr1
, expr2
))
1307 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1308 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1311 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1314 code1
= expr1
.cond_code
;
1316 code1
= invert_tree_comparison (code1
, false);
1317 code2
= expr2
.cond_code
;
1319 code2
= invert_tree_comparison (code2
, false);
1321 if (code1
!= code2
&& code2
!= NE_EXPR
)
1324 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1330 /* Returns true if the domain of PRED1 is a subset
1331 of that of PRED2. Returns false if it can not be proved so. */
1334 is_pred_chain_subset_of (pred_chain pred1
,
1337 size_t np1
, np2
, i1
, i2
;
1339 np1
= pred1
.length ();
1340 np2
= pred2
.length ();
1342 for (i2
= 0; i2
< np2
; i2
++)
1345 pred_info info2
= pred2
[i2
];
1346 for (i1
= 0; i1
< np1
; i1
++)
1348 pred_info info1
= pred1
[i1
];
1349 if (is_pred_expr_subset_of (info1
, info2
))
1361 /* Returns true if the domain defined by
1362 one pred chain ONE_PRED is a subset of the domain
1363 of *PREDS. It returns false if ONE_PRED's domain is
1364 not a subset of any of the sub-domains of PREDS
1365 (corresponding to each individual chains in it), even
1366 though it may be still be a subset of whole domain
1367 of PREDS which is the union (ORed) of all its subdomains.
1368 In other words, the result is conservative. */
1371 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1374 size_t n
= preds
.length ();
1376 for (i
= 0; i
< n
; i
++)
1378 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1385 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1386 true if the domain defined by PREDS1 is a superset
1387 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1388 PREDS2 respectively. The implementation chooses not to build
1389 generic trees (and relying on the folding capability of the
1390 compiler), but instead performs brute force comparison of
1391 individual predicate chains (won't be a compile time problem
1392 as the chains are pretty short). When the function returns
1393 false, it does not necessarily mean *PREDS1 is not a superset
1394 of *PREDS2, but mean it may not be so since the analysis can
1395 not prove it. In such cases, false warnings may still be
1399 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1402 pred_chain one_pred_chain
= vNULL
;
1404 n2
= preds2
.length ();
1406 for (i
= 0; i
< n2
; i
++)
1408 one_pred_chain
= preds2
[i
];
1409 if (!is_included_in (one_pred_chain
, preds1
))
1416 /* Returns true if TC is AND or OR. */
1419 is_and_or_or_p (enum tree_code tc
, tree type
)
1421 return (tc
== BIT_IOR_EXPR
1422 || (tc
== BIT_AND_EXPR
1423 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1426 /* Returns true if X1 is the negate of X2. */
1429 pred_neg_p (pred_info x1
, pred_info x2
)
1431 enum tree_code c1
, c2
;
1432 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1433 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1437 if (x1
.invert
== x2
.invert
)
1438 c2
= invert_tree_comparison (x2
.cond_code
, false);
1445 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1446 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1447 3) X OR (!X AND Y) is equivalent to (X OR Y);
1448 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1450 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1453 PREDS is the predicate chains, and N is the number of chains. */
1455 /* Helper function to implement rule 1 above. ONE_CHAIN is
1456 the AND predication to be simplified. */
1459 simplify_pred (pred_chain
*one_chain
)
1462 bool simplified
= false;
1463 pred_chain s_chain
= vNULL
;
1465 n
= one_chain
->length ();
1467 for (i
= 0; i
< n
; i
++)
1469 pred_info
*a_pred
= &(*one_chain
)[i
];
1471 if (!a_pred
->pred_lhs
)
1473 if (!is_neq_zero_form_p (*a_pred
))
1476 gimple def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1477 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1479 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1481 for (j
= 0; j
< n
; j
++)
1483 pred_info
*b_pred
= &(*one_chain
)[j
];
1485 if (!b_pred
->pred_lhs
)
1487 if (!is_neq_zero_form_p (*b_pred
))
1490 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1491 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1493 /* Mark a_pred for removal. */
1494 a_pred
->pred_lhs
= NULL
;
1495 a_pred
->pred_rhs
= NULL
;
1506 for (i
= 0; i
< n
; i
++)
1508 pred_info
*a_pred
= &(*one_chain
)[i
];
1509 if (!a_pred
->pred_lhs
)
1511 s_chain
.safe_push (*a_pred
);
1514 one_chain
->release ();
1515 *one_chain
= s_chain
;
1518 /* The helper function implements the rule 2 for the
1521 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1524 simplify_preds_2 (pred_chain_union
*preds
)
1527 bool simplified
= false;
1528 pred_chain_union s_preds
= vNULL
;
1530 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1531 (X AND Y) OR (X AND !Y) is equivalent to X. */
1533 n
= preds
->length ();
1534 for (i
= 0; i
< n
; i
++)
1537 pred_chain
*a_chain
= &(*preds
)[i
];
1539 if (a_chain
->length () != 2)
1545 for (j
= 0; j
< n
; j
++)
1547 pred_chain
*b_chain
;
1553 b_chain
= &(*preds
)[j
];
1554 if (b_chain
->length () != 2)
1560 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1563 a_chain
->release ();
1564 b_chain
->release ();
1565 b_chain
->safe_push (x
);
1569 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1572 a_chain
->release ();
1573 b_chain
->release ();
1574 b_chain
->safe_push (y
);
1580 /* Now clean up the chain. */
1583 for (i
= 0; i
< n
; i
++)
1585 if ((*preds
)[i
].is_empty ())
1587 s_preds
.safe_push ((*preds
)[i
]);
1597 /* The helper function implements the rule 2 for the
1600 3) x OR (!x AND y) is equivalent to x OR y. */
1603 simplify_preds_3 (pred_chain_union
*preds
)
1606 bool simplified
= false;
1608 /* Now iteratively simplify X OR (!X AND Z ..)
1609 into X OR (Z ...). */
1611 n
= preds
->length ();
1615 for (i
= 0; i
< n
; i
++)
1618 pred_chain
*a_chain
= &(*preds
)[i
];
1620 if (a_chain
->length () != 1)
1625 for (j
= 0; j
< n
; j
++)
1627 pred_chain
*b_chain
;
1634 b_chain
= &(*preds
)[j
];
1635 if (b_chain
->length () < 2)
1638 for (k
= 0; k
< b_chain
->length (); k
++)
1641 if (pred_neg_p (x
, x2
))
1643 b_chain
->unordered_remove (k
);
1653 /* The helper function implements the rule 4 for the
1656 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1657 (x != 0 ANd y != 0). */
1660 simplify_preds_4 (pred_chain_union
*preds
)
1663 bool simplified
= false;
1664 pred_chain_union s_preds
= vNULL
;
1667 n
= preds
->length ();
1668 for (i
= 0; i
< n
; i
++)
1671 pred_chain
*a_chain
= &(*preds
)[i
];
1673 if (a_chain
->length () != 1)
1678 if (!is_neq_zero_form_p (z
))
1681 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1682 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1685 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1688 for (j
= 0; j
< n
; j
++)
1690 pred_chain
*b_chain
;
1696 b_chain
= &(*preds
)[j
];
1697 if (b_chain
->length () != 2)
1702 if (!is_neq_zero_form_p (x2
)
1703 || !is_neq_zero_form_p (y2
))
1706 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1707 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1708 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1709 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1712 a_chain
->release ();
1718 /* Now clean up the chain. */
1721 for (i
= 0; i
< n
; i
++)
1723 if ((*preds
)[i
].is_empty ())
1725 s_preds
.safe_push ((*preds
)[i
]);
1736 /* This function simplifies predicates in PREDS. */
1739 simplify_preds (pred_chain_union
*preds
, gimple use_or_def
, bool is_use
)
1742 bool changed
= false;
1744 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1746 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1747 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1750 for (i
= 0; i
< preds
->length (); i
++)
1751 simplify_pred (&(*preds
)[i
]);
1753 n
= preds
->length ();
1760 if (simplify_preds_2 (preds
))
1763 /* Now iteratively simplify X OR (!X AND Z ..)
1764 into X OR (Z ...). */
1765 if (simplify_preds_3 (preds
))
1768 if (simplify_preds_4 (preds
))
1776 /* This is a helper function which attempts to normalize predicate chains
1777 by following UD chains. It basically builds up a big tree of either IOR
1778 operations or AND operations, and convert the IOR tree into a
1779 pred_chain_union or BIT_AND tree into a pred_chain.
1789 then _t != 0 will be normalized into a pred_chain_union
1791 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1801 then _t != 0 will be normalized into a pred_chain:
1802 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1806 /* This is a helper function that stores a PRED into NORM_PREDS. */
1809 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1811 pred_chain pred_chain
= vNULL
;
1812 pred_chain
.safe_push (pred
);
1813 norm_preds
->safe_push (pred_chain
);
1816 /* A helper function that creates a predicate of the form
1817 OP != 0 and push it WORK_LIST. */
1820 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1821 pointer_set_t
*mark_set
)
1823 if (pointer_set_contains (mark_set
, op
))
1825 pointer_set_insert (mark_set
, op
);
1828 arg_pred
.pred_lhs
= op
;
1829 arg_pred
.pred_rhs
= integer_zero_node
;
1830 arg_pred
.cond_code
= NE_EXPR
;
1831 arg_pred
.invert
= false;
1832 work_list
->safe_push (arg_pred
);
1835 /* A helper that generates a pred_info from a gimple assignment
1836 CMP_ASSIGN with comparison rhs. */
1839 get_pred_info_from_cmp (gimple cmp_assign
)
1842 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1843 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1844 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1845 n_pred
.invert
= false;
1849 /* Returns true if the PHI is a degenerated phi with
1850 all args with the same value (relop). In that case, *PRED
1851 will be updated to that value. */
1854 is_degenerated_phi (gimple phi
, pred_info
*pred_p
)
1861 n
= gimple_phi_num_args (phi
);
1862 op0
= gimple_phi_arg_def (phi
, 0);
1864 if (TREE_CODE (op0
) != SSA_NAME
)
1867 def0
= SSA_NAME_DEF_STMT (op0
);
1868 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1870 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1873 pred0
= get_pred_info_from_cmp (def0
);
1875 for (i
= 1; i
< n
; ++i
)
1879 tree op
= gimple_phi_arg_def (phi
, i
);
1881 if (TREE_CODE (op
) != SSA_NAME
)
1884 def
= SSA_NAME_DEF_STMT (op
);
1885 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1887 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1890 pred
= get_pred_info_from_cmp (def
);
1891 if (!pred_equal_p (pred
, pred0
))
1899 /* Normalize one predicate PRED
1900 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1901 2) otherwise if PRED is of the form x != 0, follow x's definition
1902 and put normalized predicates into WORK_LIST. */
1905 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1906 pred_chain
*norm_chain
,
1908 enum tree_code and_or_code
,
1909 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1910 pointer_set_t
*mark_set
)
1912 if (!is_neq_zero_form_p (pred
))
1914 if (and_or_code
== BIT_IOR_EXPR
)
1915 push_pred (norm_preds
, pred
);
1917 norm_chain
->safe_push (pred
);
1921 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1923 if (gimple_code (def_stmt
) == GIMPLE_PHI
1924 && is_degenerated_phi (def_stmt
, &pred
))
1925 work_list
->safe_push (pred
);
1926 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1927 && and_or_code
== BIT_IOR_EXPR
)
1930 n
= gimple_phi_num_args (def_stmt
);
1932 /* If we see non zero constant, we should punt. The predicate
1933 * should be one guarding the phi edge. */
1934 for (i
= 0; i
< n
; ++i
)
1936 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1937 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1939 push_pred (norm_preds
, pred
);
1944 for (i
= 0; i
< n
; ++i
)
1946 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1947 if (integer_zerop (op
))
1950 push_to_worklist (op
, work_list
, mark_set
);
1953 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1955 if (and_or_code
== BIT_IOR_EXPR
)
1956 push_pred (norm_preds
, pred
);
1958 norm_chain
->safe_push (pred
);
1960 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
1962 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
1963 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
1965 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
1968 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
1969 if (and_or_code
== BIT_IOR_EXPR
)
1970 push_pred (norm_preds
, n_pred
);
1972 norm_chain
->safe_push (n_pred
);
1976 if (and_or_code
== BIT_IOR_EXPR
)
1977 push_pred (norm_preds
, pred
);
1979 norm_chain
->safe_push (pred
);
1983 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
1986 normalize_one_pred (pred_chain_union
*norm_preds
,
1989 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
1990 pointer_set_t
*mark_set
= NULL
;
1991 enum tree_code and_or_code
= ERROR_MARK
;
1992 pred_chain norm_chain
= vNULL
;
1994 if (!is_neq_zero_form_p (pred
))
1996 push_pred (norm_preds
, pred
);
2000 gimple def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2001 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2002 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2003 if (and_or_code
!= BIT_IOR_EXPR
2004 && and_or_code
!= BIT_AND_EXPR
)
2006 if (TREE_CODE_CLASS (and_or_code
)
2009 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2010 push_pred (norm_preds
, n_pred
);
2013 push_pred (norm_preds
, pred
);
2017 work_list
.safe_push (pred
);
2018 mark_set
= pointer_set_create ();
2020 while (!work_list
.is_empty ())
2022 pred_info a_pred
= work_list
.pop ();
2023 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2024 and_or_code
, &work_list
, mark_set
);
2026 if (and_or_code
== BIT_AND_EXPR
)
2027 norm_preds
->safe_push (norm_chain
);
2029 work_list
.release ();
2030 pointer_set_destroy (mark_set
);
2034 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2035 pred_chain one_chain
)
2037 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2038 pointer_set_t
*mark_set
= pointer_set_create ();
2039 pred_chain norm_chain
= vNULL
;
2042 for (i
= 0; i
< one_chain
.length (); i
++)
2044 work_list
.safe_push (one_chain
[i
]);
2045 pointer_set_insert (mark_set
, one_chain
[i
].pred_lhs
);
2048 while (!work_list
.is_empty ())
2050 pred_info a_pred
= work_list
.pop ();
2051 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2052 BIT_AND_EXPR
, &work_list
, mark_set
);
2055 norm_preds
->safe_push (norm_chain
);
2056 work_list
.release ();
2057 pointer_set_destroy (mark_set
);
2060 /* Normalize predicate chains PREDS and returns the normalized one. */
2062 static pred_chain_union
2063 normalize_preds (pred_chain_union preds
, gimple use_or_def
, bool is_use
)
2065 pred_chain_union norm_preds
= vNULL
;
2066 size_t n
= preds
.length ();
2069 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2071 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2072 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2075 for (i
= 0; i
< n
; i
++)
2077 if (preds
[i
].length () != 1)
2078 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2081 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2082 preds
[i
].release ();
2088 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2089 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2097 /* Computes the predicates that guard the use and checks
2098 if the incoming paths that have empty (or possibly
2099 empty) definition can be pruned/filtered. The function returns
2100 true if it can be determined that the use of PHI's def in
2101 USE_STMT is guarded with a predicate set not overlapping with
2102 predicate sets of all runtime paths that do not have a definition.
2103 Returns false if it is not or it can not be determined. USE_BB is
2104 the bb of the use (for phi operand use, the bb is not the bb of
2105 the phi stmt, but the src bb of the operand edge). UNINIT_OPNDS
2106 is a bit vector. If an operand of PHI is uninitialized, the
2107 corresponding bit in the vector is 1. VISIED_PHIS is a pointer
2108 set of phis being visted. */
2111 is_use_properly_guarded (gimple use_stmt
,
2114 unsigned uninit_opnds
,
2115 pointer_set_t
*visited_phis
)
2118 pred_chain_union preds
= vNULL
;
2119 pred_chain_union def_preds
= vNULL
;
2120 bool has_valid_preds
= false;
2121 bool is_properly_guarded
= false;
2123 if (pointer_set_insert (visited_phis
, phi
))
2126 phi_bb
= gimple_bb (phi
);
2128 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2131 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2133 if (!has_valid_preds
)
2135 destroy_predicate_vecs (preds
);
2139 /* Try to prune the dead incoming phi edges. */
2141 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2144 if (is_properly_guarded
)
2146 destroy_predicate_vecs (preds
);
2150 has_valid_preds
= find_def_preds (&def_preds
, phi
);
2152 if (!has_valid_preds
)
2154 destroy_predicate_vecs (preds
);
2155 destroy_predicate_vecs (def_preds
);
2159 simplify_preds (&preds
, use_stmt
, true);
2160 preds
= normalize_preds (preds
, use_stmt
, true);
2162 simplify_preds (&def_preds
, phi
, false);
2163 def_preds
= normalize_preds (def_preds
, phi
, false);
2165 is_properly_guarded
= is_superset_of (def_preds
, preds
);
2167 destroy_predicate_vecs (preds
);
2168 destroy_predicate_vecs (def_preds
);
2169 return is_properly_guarded
;
2172 /* Searches through all uses of a potentially
2173 uninitialized variable defined by PHI and returns a use
2174 statement if the use is not properly guarded. It returns
2175 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2176 holding the position(s) of uninit PHI operands. WORKLIST
2177 is the vector of candidate phis that may be updated by this
2178 function. ADDED_TO_WORKLIST is the pointer set tracking
2179 if the new phi is already in the worklist. */
2182 find_uninit_use (gimple phi
, unsigned uninit_opnds
,
2183 vec
<gimple
> *worklist
,
2184 pointer_set_t
*added_to_worklist
)
2187 use_operand_p use_p
;
2189 imm_use_iterator iter
;
2191 phi_result
= gimple_phi_result (phi
);
2193 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2195 pointer_set_t
*visited_phis
;
2198 use_stmt
= USE_STMT (use_p
);
2199 if (is_gimple_debug (use_stmt
))
2202 visited_phis
= pointer_set_create ();
2204 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2205 use_bb
= gimple_phi_arg_edge (use_stmt
,
2206 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2208 use_bb
= gimple_bb (use_stmt
);
2210 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2213 pointer_set_destroy (visited_phis
);
2216 pointer_set_destroy (visited_phis
);
2218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2221 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2223 /* Found one real use, return. */
2224 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2227 /* Found a phi use that is not guarded,
2228 add the phi to the worklist. */
2229 if (!pointer_set_insert (added_to_worklist
, use_stmt
))
2231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2233 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2234 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2237 worklist
->safe_push (use_stmt
);
2238 pointer_set_insert (possibly_undefined_names
, phi_result
);
2245 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2246 and gives warning if there exists a runtime path from the entry to a
2247 use of the PHI def that does not contain a definition. In other words,
2248 the warning is on the real use. The more dead paths that can be pruned
2249 by the compiler, the fewer false positives the warning is. WORKLIST
2250 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2251 a pointer set tracking if the new phi is added to the worklist or not. */
2254 warn_uninitialized_phi (gimple phi
, vec
<gimple
> *worklist
,
2255 pointer_set_t
*added_to_worklist
)
2257 unsigned uninit_opnds
;
2258 gimple uninit_use_stmt
= 0;
2263 /* Don't look at virtual operands. */
2264 if (virtual_operand_p (gimple_phi_result (phi
)))
2267 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2269 if (MASK_EMPTY (uninit_opnds
))
2272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2274 fprintf (dump_file
, "[CHECK]: examining phi: ");
2275 print_gimple_stmt (dump_file
, phi
, 0, 0);
2278 /* Now check if we have any use of the value without proper guard. */
2279 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2280 worklist
, added_to_worklist
);
2282 /* All uses are properly guarded. */
2283 if (!uninit_use_stmt
)
2286 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2287 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2288 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2290 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2291 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2293 loc
= UNKNOWN_LOCATION
;
2294 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2295 SSA_NAME_VAR (uninit_op
),
2296 "%qD may be used uninitialized in this function",
2297 uninit_use_stmt
, loc
);
2302 gate_warn_uninitialized (void)
2304 return warn_uninitialized
|| warn_maybe_uninitialized
;
2309 const pass_data pass_data_late_warn_uninitialized
=
2311 GIMPLE_PASS
, /* type */
2312 "uninit", /* name */
2313 OPTGROUP_NONE
, /* optinfo_flags */
2314 TV_NONE
, /* tv_id */
2315 PROP_ssa
, /* properties_required */
2316 0, /* properties_provided */
2317 0, /* properties_destroyed */
2318 0, /* todo_flags_start */
2319 0, /* todo_flags_finish */
2322 class pass_late_warn_uninitialized
: public gimple_opt_pass
2325 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2326 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2329 /* opt_pass methods: */
2330 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2331 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2332 virtual unsigned int execute (function
*);
2334 }; // class pass_late_warn_uninitialized
2337 pass_late_warn_uninitialized::execute (function
*fun
)
2340 gimple_stmt_iterator gsi
;
2341 vec
<gimple
> worklist
= vNULL
;
2342 pointer_set_t
*added_to_worklist
;
2344 calculate_dominance_info (CDI_DOMINATORS
);
2345 calculate_dominance_info (CDI_POST_DOMINATORS
);
2346 /* Re-do the plain uninitialized variable check, as optimization may have
2347 straightened control flow. Do this first so that we don't accidentally
2348 get a "may be" warning when we'd have seen an "is" warning later. */
2349 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2351 timevar_push (TV_TREE_UNINIT
);
2353 possibly_undefined_names
= pointer_set_create ();
2354 added_to_worklist
= pointer_set_create ();
2356 /* Initialize worklist */
2357 FOR_EACH_BB_FN (bb
, fun
)
2358 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2360 gimple phi
= gsi_stmt (gsi
);
2363 n
= gimple_phi_num_args (phi
);
2365 /* Don't look at virtual operands. */
2366 if (virtual_operand_p (gimple_phi_result (phi
)))
2369 for (i
= 0; i
< n
; ++i
)
2371 tree op
= gimple_phi_arg_def (phi
, i
);
2372 if (TREE_CODE (op
) == SSA_NAME
2373 && uninit_undefined_value_p (op
))
2375 worklist
.safe_push (phi
);
2376 pointer_set_insert (added_to_worklist
, phi
);
2377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2379 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2380 print_gimple_stmt (dump_file
, phi
, 0, 0);
2387 while (worklist
.length () != 0)
2390 cur_phi
= worklist
.pop ();
2391 warn_uninitialized_phi (cur_phi
, &worklist
, added_to_worklist
);
2394 worklist
.release ();
2395 pointer_set_destroy (added_to_worklist
);
2396 pointer_set_destroy (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
);