1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2016 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "tree-pass.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
37 /* This implements the pass that does predicate aware warning on uses of
38 possibly uninitialized variables. The pass first collects the set of
39 possibly uninitialized SSA names. For each such name, it walks through
40 all its immediate uses. For each immediate use, it rebuilds the condition
41 expression (the predicate) that guards the use. The predicate is then
42 examined to see if the variable is always defined under that same condition.
43 This is done either by pruning the unrealizable paths that lead to the
44 default definitions or by checking if the predicate set that guards the
45 defining paths is a superset of the use predicate. */
48 /* Pointer set of potentially undefined ssa names, i.e.,
49 ssa names that are defined by phi with operands that
50 are not defined or potentially undefined. */
51 static hash_set
<tree
> *possibly_undefined_names
= 0;
53 /* Bit mask handling macros. */
54 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
55 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
56 #define MASK_EMPTY(mask) (mask == 0)
58 /* Returns the first bit position (starting from LSB)
59 in mask that is non zero. Returns -1 if the mask is empty. */
61 get_mask_first_set_bit (unsigned mask
)
67 while ((mask
& (1 << pos
)) == 0)
72 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
74 /* Return true if T, an SSA_NAME, has an undefined value. */
76 has_undefined_value_p (tree t
)
78 return (ssa_undefined_value_p (t
)
79 || (possibly_undefined_names
80 && possibly_undefined_names
->contains (t
)));
85 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
86 is set on SSA_NAME_VAR. */
89 uninit_undefined_value_p (tree t
) {
90 if (!has_undefined_value_p (t
))
92 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
97 /* Emit warnings for uninitialized variables. This is done in two passes.
99 The first pass notices real uses of SSA names with undefined values.
100 Such uses are unconditionally uninitialized, and we can be certain that
101 such a use is a mistake. This pass is run before most optimizations,
102 so that we catch as many as we can.
104 The second pass follows PHI nodes to find uses that are potentially
105 uninitialized. In this case we can't necessarily prove that the use
106 is really uninitialized. This pass is run after most optimizations,
107 so that we thread as many jumps and possible, and delete as much dead
108 code as possible, in order to reduce false positives. We also look
109 again for plain uninitialized variables, since optimization may have
110 changed conditionally uninitialized to unconditionally uninitialized. */
112 /* Emit a warning for EXPR based on variable VAR at the point in the
113 program T, an SSA_NAME, is used being uninitialized. The exact
114 warning text is in MSGID and DATA is the gimple stmt with info about
115 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
116 gives which argument of the phi node to take the location from. WC
117 is the warning code. */
120 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
121 const char *gmsgid
, void *data
, location_t phiarg_loc
)
123 gimple
*context
= (gimple
*) data
;
124 location_t location
, cfun_loc
;
125 expanded_location xloc
, floc
;
127 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
128 turns in a COMPLEX_EXPR with the not initialized part being
129 set to its previous (undefined) value. */
130 if (is_gimple_assign (context
)
131 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
133 if (!has_undefined_value_p (t
))
136 /* TREE_NO_WARNING either means we already warned, or the front end
137 wishes to suppress the warning. */
139 && (gimple_no_warning_p (context
)
140 || (gimple_assign_single_p (context
)
141 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
142 || TREE_NO_WARNING (expr
))
145 if (context
!= NULL
&& gimple_has_location (context
))
146 location
= gimple_location (context
);
147 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
148 location
= phiarg_loc
;
150 location
= DECL_SOURCE_LOCATION (var
);
151 location
= linemap_resolve_location (line_table
, location
,
152 LRK_SPELLING_LOCATION
,
154 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
155 xloc
= expand_location (location
);
156 floc
= expand_location (cfun_loc
);
157 if (warning_at (location
, wc
, gmsgid
, expr
))
159 TREE_NO_WARNING (expr
) = 1;
161 if (location
== DECL_SOURCE_LOCATION (var
))
163 if (xloc
.file
!= floc
.file
164 || linemap_location_before_p (line_table
,
166 || linemap_location_before_p (line_table
,
167 cfun
->function_end_locus
,
169 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
174 warn_uninitialized_vars (bool warn_possibly_uninitialized
)
176 gimple_stmt_iterator gsi
;
179 FOR_EACH_BB_FN (bb
, cfun
)
181 bool always_executed
= dominated_by_p (CDI_POST_DOMINATORS
,
182 single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)), bb
);
183 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
185 gimple
*stmt
= gsi_stmt (gsi
);
190 if (is_gimple_debug (stmt
))
193 /* We only do data flow with SSA_NAMEs, so that's all we
195 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
197 use
= USE_FROM_PTR (use_p
);
199 warn_uninit (OPT_Wuninitialized
, use
,
200 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
201 "%qD is used uninitialized in this function",
202 stmt
, UNKNOWN_LOCATION
);
203 else if (warn_possibly_uninitialized
)
204 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
205 SSA_NAME_VAR (use
), SSA_NAME_VAR (use
),
206 "%qD may be used uninitialized in this function",
207 stmt
, UNKNOWN_LOCATION
);
210 /* For memory the only cheap thing we can do is see if we
211 have a use of the default def of the virtual operand.
212 ??? Not so cheap would be to use the alias oracle via
213 walk_aliased_vdefs, if we don't find any aliasing vdef
214 warn as is-used-uninitialized, if we don't find an aliasing
215 vdef that kills our use (stmt_kills_ref_p), warn as
216 may-be-used-uninitialized. But this walk is quadratic and
217 so must be limited which means we would miss warning
219 use
= gimple_vuse (stmt
);
221 && gimple_assign_single_p (stmt
)
222 && !gimple_vdef (stmt
)
223 && SSA_NAME_IS_DEFAULT_DEF (use
))
225 tree rhs
= gimple_assign_rhs1 (stmt
);
226 tree base
= get_base_address (rhs
);
228 /* Do not warn if it can be initialized outside this function. */
229 if (TREE_CODE (base
) != VAR_DECL
230 || DECL_HARD_REGISTER (base
)
231 || is_global_var (base
))
235 warn_uninit (OPT_Wuninitialized
, use
,
236 gimple_assign_rhs1 (stmt
), base
,
237 "%qE is used uninitialized in this function",
238 stmt
, UNKNOWN_LOCATION
);
239 else if (warn_possibly_uninitialized
)
240 warn_uninit (OPT_Wmaybe_uninitialized
, use
,
241 gimple_assign_rhs1 (stmt
), base
,
242 "%qE may be used uninitialized in this function",
243 stmt
, UNKNOWN_LOCATION
);
251 /* Checks if the operand OPND of PHI is defined by
252 another phi with one operand defined by this PHI,
253 but the rest operands are all defined. If yes,
254 returns true to skip this operand as being
255 redundant. Can be enhanced to be more general. */
258 can_skip_redundant_opnd (tree opnd
, gimple
*phi
)
264 phi_def
= gimple_phi_result (phi
);
265 op_def
= SSA_NAME_DEF_STMT (opnd
);
266 if (gimple_code (op_def
) != GIMPLE_PHI
)
268 n
= gimple_phi_num_args (op_def
);
269 for (i
= 0; i
< n
; ++i
)
271 tree op
= gimple_phi_arg_def (op_def
, i
);
272 if (TREE_CODE (op
) != SSA_NAME
)
274 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
281 /* Returns a bit mask holding the positions of arguments in PHI
282 that have empty (or possibly empty) definitions. */
285 compute_uninit_opnds_pos (gphi
*phi
)
288 unsigned uninit_opnds
= 0;
290 n
= gimple_phi_num_args (phi
);
291 /* Bail out for phi with too many args. */
295 for (i
= 0; i
< n
; ++i
)
297 tree op
= gimple_phi_arg_def (phi
, i
);
298 if (TREE_CODE (op
) == SSA_NAME
299 && uninit_undefined_value_p (op
)
300 && !can_skip_redundant_opnd (op
, phi
))
302 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
304 /* Ignore SSA_NAMEs that appear on abnormal edges
306 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
309 MASK_SET_BIT (uninit_opnds
, i
);
315 /* Find the immediate postdominator PDOM of the specified
316 basic block BLOCK. */
318 static inline basic_block
319 find_pdom (basic_block block
)
321 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
322 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
326 = get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
328 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
333 /* Find the immediate DOM of the specified
334 basic block BLOCK. */
336 static inline basic_block
337 find_dom (basic_block block
)
339 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
340 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
343 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
345 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
350 /* Returns true if BB1 is postdominating BB2 and BB1 is
351 not a loop exit bb. The loop exit bb check is simple and does
352 not cover all cases. */
355 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
357 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
360 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
366 /* Find the closest postdominator of a specified BB, which is control
369 static inline basic_block
370 find_control_equiv_block (basic_block bb
)
374 pdom
= find_pdom (bb
);
376 /* Skip the postdominating bb that is also loop exit. */
377 if (!is_non_loop_exit_postdominating (pdom
, bb
))
380 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
386 #define MAX_NUM_CHAINS 8
387 #define MAX_CHAIN_LEN 5
388 #define MAX_POSTDOM_CHECK 8
389 #define MAX_SWITCH_CASES 40
391 /* Computes the control dependence chains (paths of edges)
392 for DEP_BB up to the dominating basic block BB (the head node of a
393 chain should be dominated by it). CD_CHAINS is pointer to an
394 array holding the result chains. CUR_CD_CHAIN is the current
395 chain being computed. *NUM_CHAINS is total number of chains. The
396 function returns true if the information is successfully computed,
397 return false if there is no control dependence or not computed. */
400 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
401 vec
<edge
> *cd_chains
,
403 vec
<edge
> *cur_cd_chain
,
409 bool found_cd_chain
= false;
410 size_t cur_chain_len
= 0;
412 if (EDGE_COUNT (bb
->succs
) < 2)
415 if (*num_calls
> PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS
))
419 /* Could use a set instead. */
420 cur_chain_len
= cur_cd_chain
->length ();
421 if (cur_chain_len
> MAX_CHAIN_LEN
)
424 for (i
= 0; i
< cur_chain_len
; i
++)
426 edge e
= (*cur_cd_chain
)[i
];
427 /* Cycle detected. */
432 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
435 int post_dom_check
= 0;
436 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
440 cur_cd_chain
->safe_push (e
);
441 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
445 /* Found a direct control dependence. */
446 if (*num_chains
< MAX_NUM_CHAINS
)
448 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
451 found_cd_chain
= true;
452 /* Check path from next edge. */
456 /* Now check if DEP_BB is indirectly control dependent on BB. */
457 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
458 num_chains
, cur_cd_chain
, num_calls
))
460 found_cd_chain
= true;
464 cd_bb
= find_pdom (cd_bb
);
466 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
) || post_dom_check
>
470 cur_cd_chain
->pop ();
471 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
473 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
475 return found_cd_chain
;
478 /* The type to represent a simple predicate */
484 enum tree_code cond_code
;
488 /* The type to represent a sequence of predicates grouped
489 with .AND. operation. */
491 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
493 /* The type to represent a sequence of pred_chains grouped
494 with .OR. operation. */
496 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
498 /* Converts the chains of control dependence edges into a set of
499 predicates. A control dependence chain is represented by a vector
500 edges. DEP_CHAINS points to an array of dependence chains.
501 NUM_CHAINS is the size of the chain array. One edge in a dependence
502 chain is mapped to predicate expression represented by pred_info
503 type. One dependence chain is converted to a composite predicate that
504 is the result of AND operation of pred_info mapped to each edge.
505 A composite predicate is presented by a vector of pred_info. On
506 return, *PREDS points to the resulting array of composite predicates.
507 *NUM_PREDS is the number of composite predictes. */
510 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
512 pred_chain_union
*preds
)
514 bool has_valid_pred
= false;
516 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
519 /* Now convert the control dep chain into a set
521 preds
->reserve (num_chains
);
523 for (i
= 0; i
< num_chains
; i
++)
525 vec
<edge
> one_cd_chain
= dep_chains
[i
];
527 has_valid_pred
= false;
528 pred_chain t_chain
= vNULL
;
529 for (j
= 0; j
< one_cd_chain
.length (); j
++)
532 gimple_stmt_iterator gsi
;
533 basic_block guard_bb
;
539 gsi
= gsi_last_bb (guard_bb
);
542 has_valid_pred
= false;
545 cond_stmt
= gsi_stmt (gsi
);
546 if (is_gimple_call (cond_stmt
)
547 && EDGE_COUNT (e
->src
->succs
) >= 2)
549 /* Ignore EH edge. Can add assertion
550 on the other edge's flag. */
553 /* Skip if there is essentially one succesor. */
554 if (EDGE_COUNT (e
->src
->succs
) == 2)
560 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
562 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
571 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
573 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
574 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
575 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
576 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
577 t_chain
.safe_push (one_pred
);
578 has_valid_pred
= true;
580 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
582 /* Avoid quadratic behavior. */
583 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
585 has_valid_pred
= false;
588 /* Find the case label. */
591 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
593 tree tl
= gimple_switch_label (gs
, idx
);
594 if (e
->dest
== label_to_block (CASE_LABEL (tl
)))
605 /* If more than one label reaches this block or the case
606 label doesn't have a single value (like the default one)
610 || (CASE_HIGH (l
) && !operand_equal_p (CASE_LOW (l
),
613 has_valid_pred
= false;
616 one_pred
.pred_lhs
= gimple_switch_index (gs
);
617 one_pred
.pred_rhs
= CASE_LOW (l
);
618 one_pred
.cond_code
= EQ_EXPR
;
619 one_pred
.invert
= false;
620 t_chain
.safe_push (one_pred
);
621 has_valid_pred
= true;
625 has_valid_pred
= false;
633 preds
->safe_push (t_chain
);
635 return has_valid_pred
;
638 /* Computes all control dependence chains for USE_BB. The control
639 dependence chains are then converted to an array of composite
640 predicates pointed to by PREDS. PHI_BB is the basic block of
641 the phi whose result is used in USE_BB. */
644 find_predicates (pred_chain_union
*preds
,
648 size_t num_chains
= 0, i
;
650 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
651 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
652 bool has_valid_pred
= false;
653 basic_block cd_root
= 0;
655 /* First find the closest bb that is control equivalent to PHI_BB
656 that also dominates USE_BB. */
658 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
660 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
661 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
662 cd_root
= ctrl_eq_bb
;
667 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
668 &cur_chain
, &num_calls
);
671 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
672 for (i
= 0; i
< num_chains
; i
++)
673 dep_chains
[i
].release ();
674 return has_valid_pred
;
677 /* Computes the set of incoming edges of PHI that have non empty
678 definitions of a phi chain. The collection will be done
679 recursively on operands that are defined by phis. CD_ROOT
680 is the control dependence root. *EDGES holds the result, and
681 VISITED_PHIS is a pointer set for detecting cycles. */
684 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
685 auto_vec
<edge
> *edges
,
686 hash_set
<gimple
*> *visited_phis
)
692 if (visited_phis
->add (phi
))
695 n
= gimple_phi_num_args (phi
);
696 for (i
= 0; i
< n
; i
++)
698 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
699 opnd
= gimple_phi_arg_def (phi
, i
);
701 if (TREE_CODE (opnd
) != SSA_NAME
)
703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
705 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
706 print_gimple_stmt (dump_file
, phi
, 0, 0);
708 edges
->safe_push (opnd_edge
);
712 gimple
*def
= SSA_NAME_DEF_STMT (opnd
);
714 if (gimple_code (def
) == GIMPLE_PHI
715 && dominated_by_p (CDI_DOMINATORS
,
716 gimple_bb (def
), cd_root
))
717 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
719 else if (!uninit_undefined_value_p (opnd
))
721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
723 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int)i
);
724 print_gimple_stmt (dump_file
, phi
, 0, 0);
726 edges
->safe_push (opnd_edge
);
732 /* For each use edge of PHI, computes all control dependence chains.
733 The control dependence chains are then converted to an array of
734 composite predicates pointed to by PREDS. */
737 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
739 size_t num_chains
= 0, i
, n
;
740 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
741 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
742 auto_vec
<edge
> def_edges
;
743 bool has_valid_pred
= false;
744 basic_block phi_bb
, cd_root
= 0;
746 phi_bb
= gimple_bb (phi
);
747 /* First find the closest dominating bb to be
748 the control dependence root */
749 cd_root
= find_dom (phi_bb
);
753 hash_set
<gimple
*> visited_phis
;
754 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
756 n
= def_edges
.length ();
760 for (i
= 0; i
< n
; i
++)
766 opnd_edge
= def_edges
[i
];
767 prev_nc
= num_chains
;
768 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
769 &num_chains
, &cur_chain
, &num_calls
);
771 /* Now update the newly added chains with
772 the phi operand edge: */
773 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
775 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
776 dep_chains
[num_chains
++] = vNULL
;
777 for (j
= prev_nc
; j
< num_chains
; j
++)
778 dep_chains
[j
].safe_push (opnd_edge
);
783 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
784 for (i
= 0; i
< num_chains
; i
++)
785 dep_chains
[i
].release ();
786 return has_valid_pred
;
789 /* Dumps the predicates (PREDS) for USESTMT. */
792 dump_predicates (gimple
*usestmt
, pred_chain_union preds
,
796 pred_chain one_pred_chain
= vNULL
;
797 fprintf (dump_file
, "%s", msg
);
798 print_gimple_stmt (dump_file
, usestmt
, 0, 0);
799 fprintf (dump_file
, "is guarded by :\n\n");
800 size_t num_preds
= preds
.length ();
801 /* Do some dumping here: */
802 for (i
= 0; i
< num_preds
; i
++)
806 one_pred_chain
= preds
[i
];
807 np
= one_pred_chain
.length ();
809 for (j
= 0; j
< np
; j
++)
811 pred_info one_pred
= one_pred_chain
[j
];
813 fprintf (dump_file
, " (.NOT.) ");
814 print_generic_expr (dump_file
, one_pred
.pred_lhs
, 0);
815 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
816 print_generic_expr (dump_file
, one_pred
.pred_rhs
, 0);
818 fprintf (dump_file
, " (.AND.) ");
820 fprintf (dump_file
, "\n");
822 if (i
< num_preds
- 1)
823 fprintf (dump_file
, "(.OR.)\n");
825 fprintf (dump_file
, "\n\n");
829 /* Destroys the predicate set *PREDS. */
832 destroy_predicate_vecs (pred_chain_union
*preds
)
836 size_t n
= preds
->length ();
837 for (i
= 0; i
< n
; i
++)
838 (*preds
)[i
].release ();
843 /* Computes the 'normalized' conditional code with operand
844 swapping and condition inversion. */
846 static enum tree_code
847 get_cmp_code (enum tree_code orig_cmp_code
,
848 bool swap_cond
, bool invert
)
850 enum tree_code tc
= orig_cmp_code
;
853 tc
= swap_tree_comparison (orig_cmp_code
);
855 tc
= invert_tree_comparison (tc
, false);
872 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
873 all values in the range satisfies (x CMPC BOUNDARY) == true. */
876 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
878 bool inverted
= false;
882 /* Only handle integer constant here. */
883 if (TREE_CODE (val
) != INTEGER_CST
884 || TREE_CODE (boundary
) != INTEGER_CST
)
887 is_unsigned
= TYPE_UNSIGNED (TREE_TYPE (val
));
889 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
892 cmpc
= invert_tree_comparison (cmpc
, false);
899 result
= tree_int_cst_equal (val
, boundary
);
900 else if (cmpc
== LT_EXPR
)
901 result
= tree_int_cst_lt (val
, boundary
);
904 gcc_assert (cmpc
== LE_EXPR
);
905 result
= tree_int_cst_le (val
, boundary
);
911 result
= tree_int_cst_equal (val
, boundary
);
912 else if (cmpc
== LT_EXPR
)
913 result
= tree_int_cst_lt (val
, boundary
);
916 gcc_assert (cmpc
== LE_EXPR
);
917 result
= (tree_int_cst_equal (val
, boundary
)
918 || tree_int_cst_lt (val
, boundary
));
928 /* Returns true if PRED is common among all the predicate
929 chains (PREDS) (and therefore can be factored out).
930 NUM_PRED_CHAIN is the size of array PREDS. */
933 find_matching_predicate_in_rest_chains (pred_info pred
,
934 pred_chain_union preds
,
935 size_t num_pred_chains
)
940 if (num_pred_chains
== 1)
943 for (i
= 1; i
< num_pred_chains
; i
++)
946 pred_chain one_chain
= preds
[i
];
947 n
= one_chain
.length ();
948 for (j
= 0; j
< n
; j
++)
950 pred_info pred2
= one_chain
[j
];
951 /* Can relax the condition comparison to not
952 use address comparison. However, the most common
953 case is that multiple control dependent paths share
954 a common path prefix, so address comparison should
957 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
958 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
959 && pred2
.invert
== pred
.invert
)
971 /* Forward declaration. */
973 is_use_properly_guarded (gimple
*use_stmt
,
976 unsigned uninit_opnds
,
977 pred_chain_union
*def_preds
,
978 hash_set
<gphi
*> *visited_phis
);
980 /* Returns true if all uninitialized opnds are pruned. Returns false
981 otherwise. PHI is the phi node with uninitialized operands,
982 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
983 FLAG_DEF is the statement defining the flag guarding the use of the
984 PHI output, BOUNDARY_CST is the const value used in the predicate
985 associated with the flag, CMP_CODE is the comparison code used in
986 the predicate, VISITED_PHIS is the pointer set of phis visited, and
987 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
993 flag_1 = phi <0, 1> // (1)
994 var_1 = phi <undef, some_val>
998 flag_2 = phi <0, flag_1, flag_1> // (2)
999 var_2 = phi <undef, var_1, var_1>
1006 Because some flag arg in (1) is not constant, if we do not look into the
1007 flag phis recursively, it is conservatively treated as unknown and var_1
1008 is thought to be flowed into use at (3). Since var_1 is potentially uninitialized
1009 a false warning will be emitted. Checking recursively into (1), the compiler can
1010 find out that only some_val (which is defined) can flow into (3) which is OK.
1015 prune_uninit_phi_opnds_in_unrealizable_paths (gphi
*phi
,
1016 unsigned uninit_opnds
,
1019 enum tree_code cmp_code
,
1020 hash_set
<gphi
*> *visited_phis
,
1021 bitmap
*visited_flag_phis
)
1025 for (i
= 0; i
< MIN (32, gimple_phi_num_args (flag_def
)); i
++)
1029 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1032 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1033 if (!is_gimple_constant (flag_arg
))
1035 gphi
*flag_arg_def
, *phi_arg_def
;
1037 unsigned uninit_opnds_arg_phi
;
1039 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1041 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1045 phi_arg
= gimple_phi_arg_def (phi
, i
);
1046 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1049 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1053 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1056 if (!*visited_flag_phis
)
1057 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1059 if (bitmap_bit_p (*visited_flag_phis
,
1060 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
))))
1063 bitmap_set_bit (*visited_flag_phis
,
1064 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1066 /* Now recursively prune the uninitialized phi args. */
1067 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1068 if (!prune_uninit_phi_opnds_in_unrealizable_paths
1069 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
,
1070 boundary_cst
, cmp_code
, visited_phis
, visited_flag_phis
))
1073 bitmap_clear_bit (*visited_flag_phis
,
1074 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1078 /* Now check if the constant is in the guarded range. */
1079 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1084 /* Now that we know that this undefined edge is not
1085 pruned. If the operand is defined by another phi,
1086 we can further prune the incoming edges of that
1087 phi by checking the predicates of this operands. */
1089 opnd
= gimple_phi_arg_def (phi
, i
);
1090 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1091 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1094 unsigned uninit_opnds2
1095 = compute_uninit_opnds_pos (opnd_def_phi
);
1096 if (!MASK_EMPTY (uninit_opnds2
))
1098 pred_chain_union def_preds
= vNULL
;
1100 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1101 ok
= is_use_properly_guarded (phi
,
1107 destroy_predicate_vecs (&def_preds
);
1120 /* A helper function that determines if the predicate set
1121 of the use is not overlapping with that of the uninit paths.
1122 The most common senario of guarded use is in Example 1:
1135 The real world examples are usually more complicated, but similar
1136 and usually result from inlining:
1138 bool init_func (int * x)
1157 Another possible use scenario is in the following trivial example:
1169 Predicate analysis needs to compute the composite predicate:
1171 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1172 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1173 (the predicate chain for phi operand defs can be computed
1174 starting from a bb that is control equivalent to the phi's
1175 bb and is dominating the operand def.)
1177 and check overlapping:
1178 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1181 This implementation provides framework that can handle
1182 scenarios. (Note that many simple cases are handled properly
1183 without the predicate analysis -- this is due to jump threading
1184 transformation which eliminates the merge point thus makes
1185 path sensitive analysis unnecessary.)
1187 NUM_PREDS is the number is the number predicate chains, PREDS is
1188 the array of chains, PHI is the phi node whose incoming (undefined)
1189 paths need to be pruned, and UNINIT_OPNDS is the bitmap holding
1190 uninit operand positions. VISITED_PHIS is the pointer set of phi
1191 stmts being checked. */
1195 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1196 gphi
*phi
, unsigned uninit_opnds
,
1197 hash_set
<gphi
*> *visited_phis
)
1200 gimple
*flag_def
= 0;
1201 tree boundary_cst
= 0;
1202 enum tree_code cmp_code
;
1203 bool swap_cond
= false;
1204 bool invert
= false;
1205 pred_chain the_pred_chain
= vNULL
;
1206 bitmap visited_flag_phis
= NULL
;
1207 bool all_pruned
= false;
1208 size_t num_preds
= preds
.length ();
1210 gcc_assert (num_preds
> 0);
1211 /* Find within the common prefix of multiple predicate chains
1212 a predicate that is a comparison of a flag variable against
1214 the_pred_chain
= preds
[0];
1215 n
= the_pred_chain
.length ();
1216 for (i
= 0; i
< n
; i
++)
1218 tree cond_lhs
, cond_rhs
, flag
= 0;
1220 pred_info the_pred
= the_pred_chain
[i
];
1222 invert
= the_pred
.invert
;
1223 cond_lhs
= the_pred
.pred_lhs
;
1224 cond_rhs
= the_pred
.pred_rhs
;
1225 cmp_code
= the_pred
.cond_code
;
1227 if (cond_lhs
!= NULL_TREE
&& TREE_CODE (cond_lhs
) == SSA_NAME
1228 && cond_rhs
!= NULL_TREE
&& is_gimple_constant (cond_rhs
))
1230 boundary_cst
= cond_rhs
;
1233 else if (cond_rhs
!= NULL_TREE
&& TREE_CODE (cond_rhs
) == SSA_NAME
1234 && cond_lhs
!= NULL_TREE
&& is_gimple_constant (cond_lhs
))
1236 boundary_cst
= cond_lhs
;
1244 flag_def
= SSA_NAME_DEF_STMT (flag
);
1249 if ((gimple_code (flag_def
) == GIMPLE_PHI
)
1250 && (gimple_bb (flag_def
) == gimple_bb (phi
))
1251 && find_matching_predicate_in_rest_chains (the_pred
, preds
,
1261 /* Now check all the uninit incoming edge has a constant flag value
1262 that is in conflict with the use guard/predicate. */
1263 cmp_code
= get_cmp_code (cmp_code
, swap_cond
, invert
);
1265 if (cmp_code
== ERROR_MARK
)
1268 all_pruned
= prune_uninit_phi_opnds_in_unrealizable_paths (phi
,
1270 as_a
<gphi
*> (flag_def
),
1274 &visited_flag_phis
);
1276 if (visited_flag_phis
)
1277 BITMAP_FREE (visited_flag_phis
);
1282 /* The helper function returns true if two predicates X1 and X2
1283 are equivalent. It assumes the expressions have already
1284 properly re-associated. */
1287 pred_equal_p (pred_info x1
, pred_info x2
)
1289 enum tree_code c1
, c2
;
1290 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1291 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1295 if (x1
.invert
!= x2
.invert
1296 && TREE_CODE_CLASS (x2
.cond_code
) == tcc_comparison
)
1297 c2
= invert_tree_comparison (x2
.cond_code
, false);
1304 /* Returns true if the predication is testing !=. */
1307 is_neq_relop_p (pred_info pred
)
1310 return (pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1311 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
);
1314 /* Returns true if pred is of the form X != 0. */
1317 is_neq_zero_form_p (pred_info pred
)
1319 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1320 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1325 /* The helper function returns true if two predicates X1
1326 is equivalent to X2 != 0. */
1329 pred_expr_equal_p (pred_info x1
, tree x2
)
1331 if (!is_neq_zero_form_p (x1
))
1334 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1337 /* Returns true of the domain of single predicate expression
1338 EXPR1 is a subset of that of EXPR2. Returns false if it
1339 can not be proved. */
1342 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1344 enum tree_code code1
, code2
;
1346 if (pred_equal_p (expr1
, expr2
))
1349 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1350 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1353 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1356 code1
= expr1
.cond_code
;
1358 code1
= invert_tree_comparison (code1
, false);
1359 code2
= expr2
.cond_code
;
1361 code2
= invert_tree_comparison (code2
, false);
1363 if ((code1
== EQ_EXPR
|| code1
== BIT_AND_EXPR
)
1364 && code2
== BIT_AND_EXPR
)
1365 return wi::eq_p (expr1
.pred_rhs
,
1366 wi::bit_and (expr1
.pred_rhs
, expr2
.pred_rhs
));
1368 if (code1
!= code2
&& code2
!= NE_EXPR
)
1371 if (is_value_included_in (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
))
1377 /* Returns true if the domain of PRED1 is a subset
1378 of that of PRED2. Returns false if it can not be proved so. */
1381 is_pred_chain_subset_of (pred_chain pred1
,
1384 size_t np1
, np2
, i1
, i2
;
1386 np1
= pred1
.length ();
1387 np2
= pred2
.length ();
1389 for (i2
= 0; i2
< np2
; i2
++)
1392 pred_info info2
= pred2
[i2
];
1393 for (i1
= 0; i1
< np1
; i1
++)
1395 pred_info info1
= pred1
[i1
];
1396 if (is_pred_expr_subset_of (info1
, info2
))
1408 /* Returns true if the domain defined by
1409 one pred chain ONE_PRED is a subset of the domain
1410 of *PREDS. It returns false if ONE_PRED's domain is
1411 not a subset of any of the sub-domains of PREDS
1412 (corresponding to each individual chains in it), even
1413 though it may be still be a subset of whole domain
1414 of PREDS which is the union (ORed) of all its subdomains.
1415 In other words, the result is conservative. */
1418 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1421 size_t n
= preds
.length ();
1423 for (i
= 0; i
< n
; i
++)
1425 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1432 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1433 true if the domain defined by PREDS1 is a superset
1434 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1435 PREDS2 respectively. The implementation chooses not to build
1436 generic trees (and relying on the folding capability of the
1437 compiler), but instead performs brute force comparison of
1438 individual predicate chains (won't be a compile time problem
1439 as the chains are pretty short). When the function returns
1440 false, it does not necessarily mean *PREDS1 is not a superset
1441 of *PREDS2, but mean it may not be so since the analysis can
1442 not prove it. In such cases, false warnings may still be
1446 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1449 pred_chain one_pred_chain
= vNULL
;
1451 n2
= preds2
.length ();
1453 for (i
= 0; i
< n2
; i
++)
1455 one_pred_chain
= preds2
[i
];
1456 if (!is_included_in (one_pred_chain
, preds1
))
1463 /* Returns true if TC is AND or OR. */
1466 is_and_or_or_p (enum tree_code tc
, tree type
)
1468 return (tc
== BIT_IOR_EXPR
1469 || (tc
== BIT_AND_EXPR
1470 && (type
== 0 || TREE_CODE (type
) == BOOLEAN_TYPE
)));
1473 /* Returns true if X1 is the negate of X2. */
1476 pred_neg_p (pred_info x1
, pred_info x2
)
1478 enum tree_code c1
, c2
;
1479 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1480 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1484 if (x1
.invert
== x2
.invert
)
1485 c2
= invert_tree_comparison (x2
.cond_code
, false);
1492 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1493 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1494 3) X OR (!X AND Y) is equivalent to (X OR Y);
1495 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1497 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1500 PREDS is the predicate chains, and N is the number of chains. */
1502 /* Helper function to implement rule 1 above. ONE_CHAIN is
1503 the AND predication to be simplified. */
1506 simplify_pred (pred_chain
*one_chain
)
1509 bool simplified
= false;
1510 pred_chain s_chain
= vNULL
;
1512 n
= one_chain
->length ();
1514 for (i
= 0; i
< n
; i
++)
1516 pred_info
*a_pred
= &(*one_chain
)[i
];
1518 if (!a_pred
->pred_lhs
)
1520 if (!is_neq_zero_form_p (*a_pred
))
1523 gimple
*def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
1524 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1526 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
1528 for (j
= 0; j
< n
; j
++)
1530 pred_info
*b_pred
= &(*one_chain
)[j
];
1532 if (!b_pred
->pred_lhs
)
1534 if (!is_neq_zero_form_p (*b_pred
))
1537 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
1538 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
1540 /* Mark a_pred for removal. */
1541 a_pred
->pred_lhs
= NULL
;
1542 a_pred
->pred_rhs
= NULL
;
1553 for (i
= 0; i
< n
; i
++)
1555 pred_info
*a_pred
= &(*one_chain
)[i
];
1556 if (!a_pred
->pred_lhs
)
1558 s_chain
.safe_push (*a_pred
);
1561 one_chain
->release ();
1562 *one_chain
= s_chain
;
1565 /* The helper function implements the rule 2 for the
1568 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1571 simplify_preds_2 (pred_chain_union
*preds
)
1574 bool simplified
= false;
1575 pred_chain_union s_preds
= vNULL
;
1577 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1578 (X AND Y) OR (X AND !Y) is equivalent to X. */
1580 n
= preds
->length ();
1581 for (i
= 0; i
< n
; i
++)
1584 pred_chain
*a_chain
= &(*preds
)[i
];
1586 if (a_chain
->length () != 2)
1592 for (j
= 0; j
< n
; j
++)
1594 pred_chain
*b_chain
;
1600 b_chain
= &(*preds
)[j
];
1601 if (b_chain
->length () != 2)
1607 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1610 a_chain
->release ();
1611 b_chain
->release ();
1612 b_chain
->safe_push (x
);
1616 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1619 a_chain
->release ();
1620 b_chain
->release ();
1621 b_chain
->safe_push (y
);
1627 /* Now clean up the chain. */
1630 for (i
= 0; i
< n
; i
++)
1632 if ((*preds
)[i
].is_empty ())
1634 s_preds
.safe_push ((*preds
)[i
]);
1644 /* The helper function implements the rule 2 for the
1647 3) x OR (!x AND y) is equivalent to x OR y. */
1650 simplify_preds_3 (pred_chain_union
*preds
)
1653 bool simplified
= false;
1655 /* Now iteratively simplify X OR (!X AND Z ..)
1656 into X OR (Z ...). */
1658 n
= preds
->length ();
1662 for (i
= 0; i
< n
; i
++)
1665 pred_chain
*a_chain
= &(*preds
)[i
];
1667 if (a_chain
->length () != 1)
1672 for (j
= 0; j
< n
; j
++)
1674 pred_chain
*b_chain
;
1681 b_chain
= &(*preds
)[j
];
1682 if (b_chain
->length () < 2)
1685 for (k
= 0; k
< b_chain
->length (); k
++)
1688 if (pred_neg_p (x
, x2
))
1690 b_chain
->unordered_remove (k
);
1700 /* The helper function implements the rule 4 for the
1703 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1704 (x != 0 ANd y != 0). */
1707 simplify_preds_4 (pred_chain_union
*preds
)
1710 bool simplified
= false;
1711 pred_chain_union s_preds
= vNULL
;
1714 n
= preds
->length ();
1715 for (i
= 0; i
< n
; i
++)
1718 pred_chain
*a_chain
= &(*preds
)[i
];
1720 if (a_chain
->length () != 1)
1725 if (!is_neq_zero_form_p (z
))
1728 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1729 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1732 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1735 for (j
= 0; j
< n
; j
++)
1737 pred_chain
*b_chain
;
1743 b_chain
= &(*preds
)[j
];
1744 if (b_chain
->length () != 2)
1749 if (!is_neq_zero_form_p (x2
)
1750 || !is_neq_zero_form_p (y2
))
1753 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1754 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1755 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1756 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1759 a_chain
->release ();
1765 /* Now clean up the chain. */
1768 for (i
= 0; i
< n
; i
++)
1770 if ((*preds
)[i
].is_empty ())
1772 s_preds
.safe_push ((*preds
)[i
]);
1775 destroy_predicate_vecs (preds
);
1784 /* This function simplifies predicates in PREDS. */
1787 simplify_preds (pred_chain_union
*preds
, gimple
*use_or_def
, bool is_use
)
1790 bool changed
= false;
1792 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1794 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
1795 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
1798 for (i
= 0; i
< preds
->length (); i
++)
1799 simplify_pred (&(*preds
)[i
]);
1801 n
= preds
->length ();
1808 if (simplify_preds_2 (preds
))
1811 /* Now iteratively simplify X OR (!X AND Z ..)
1812 into X OR (Z ...). */
1813 if (simplify_preds_3 (preds
))
1816 if (simplify_preds_4 (preds
))
1824 /* This is a helper function which attempts to normalize predicate chains
1825 by following UD chains. It basically builds up a big tree of either IOR
1826 operations or AND operations, and convert the IOR tree into a
1827 pred_chain_union or BIT_AND tree into a pred_chain.
1837 then _t != 0 will be normalized into a pred_chain_union
1839 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1849 then _t != 0 will be normalized into a pred_chain:
1850 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1854 /* This is a helper function that stores a PRED into NORM_PREDS. */
1857 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
1859 pred_chain pred_chain
= vNULL
;
1860 pred_chain
.safe_push (pred
);
1861 norm_preds
->safe_push (pred_chain
);
1864 /* A helper function that creates a predicate of the form
1865 OP != 0 and push it WORK_LIST. */
1868 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1869 hash_set
<tree
> *mark_set
)
1871 if (mark_set
->contains (op
))
1876 arg_pred
.pred_lhs
= op
;
1877 arg_pred
.pred_rhs
= integer_zero_node
;
1878 arg_pred
.cond_code
= NE_EXPR
;
1879 arg_pred
.invert
= false;
1880 work_list
->safe_push (arg_pred
);
1883 /* A helper that generates a pred_info from a gimple assignment
1884 CMP_ASSIGN with comparison rhs. */
1887 get_pred_info_from_cmp (gimple
*cmp_assign
)
1890 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1891 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1892 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1893 n_pred
.invert
= false;
1897 /* Returns true if the PHI is a degenerated phi with
1898 all args with the same value (relop). In that case, *PRED
1899 will be updated to that value. */
1902 is_degenerated_phi (gimple
*phi
, pred_info
*pred_p
)
1909 n
= gimple_phi_num_args (phi
);
1910 op0
= gimple_phi_arg_def (phi
, 0);
1912 if (TREE_CODE (op0
) != SSA_NAME
)
1915 def0
= SSA_NAME_DEF_STMT (op0
);
1916 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1918 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
))
1921 pred0
= get_pred_info_from_cmp (def0
);
1923 for (i
= 1; i
< n
; ++i
)
1927 tree op
= gimple_phi_arg_def (phi
, i
);
1929 if (TREE_CODE (op
) != SSA_NAME
)
1932 def
= SSA_NAME_DEF_STMT (op
);
1933 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1935 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
))
1938 pred
= get_pred_info_from_cmp (def
);
1939 if (!pred_equal_p (pred
, pred0
))
1947 /* Normalize one predicate PRED
1948 1) if PRED can no longer be normlized, put it into NORM_PREDS.
1949 2) otherwise if PRED is of the form x != 0, follow x's definition
1950 and put normalized predicates into WORK_LIST. */
1953 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
1954 pred_chain
*norm_chain
,
1956 enum tree_code and_or_code
,
1957 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
1958 hash_set
<tree
> *mark_set
)
1960 if (!is_neq_zero_form_p (pred
))
1962 if (and_or_code
== BIT_IOR_EXPR
)
1963 push_pred (norm_preds
, pred
);
1965 norm_chain
->safe_push (pred
);
1969 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1971 if (gimple_code (def_stmt
) == GIMPLE_PHI
1972 && is_degenerated_phi (def_stmt
, &pred
))
1973 work_list
->safe_push (pred
);
1974 else if (gimple_code (def_stmt
) == GIMPLE_PHI
1975 && and_or_code
== BIT_IOR_EXPR
)
1978 n
= gimple_phi_num_args (def_stmt
);
1980 /* If we see non zero constant, we should punt. The predicate
1981 * should be one guarding the phi edge. */
1982 for (i
= 0; i
< n
; ++i
)
1984 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1985 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1987 push_pred (norm_preds
, pred
);
1992 for (i
= 0; i
< n
; ++i
)
1994 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1995 if (integer_zerop (op
))
1998 push_to_worklist (op
, work_list
, mark_set
);
2001 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2003 if (and_or_code
== BIT_IOR_EXPR
)
2004 push_pred (norm_preds
, pred
);
2006 norm_chain
->safe_push (pred
);
2008 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2010 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2011 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2013 /* But treat x & 3 as condition. */
2014 if (and_or_code
== BIT_AND_EXPR
)
2017 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2018 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2019 n_pred
.cond_code
= and_or_code
;
2020 n_pred
.invert
= false;
2021 norm_chain
->safe_push (n_pred
);
2026 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2027 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2030 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2033 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2034 if (and_or_code
== BIT_IOR_EXPR
)
2035 push_pred (norm_preds
, n_pred
);
2037 norm_chain
->safe_push (n_pred
);
2041 if (and_or_code
== BIT_IOR_EXPR
)
2042 push_pred (norm_preds
, pred
);
2044 norm_chain
->safe_push (pred
);
2048 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2051 normalize_one_pred (pred_chain_union
*norm_preds
,
2054 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2055 enum tree_code and_or_code
= ERROR_MARK
;
2056 pred_chain norm_chain
= vNULL
;
2058 if (!is_neq_zero_form_p (pred
))
2060 push_pred (norm_preds
, pred
);
2064 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2065 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2066 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2067 if (and_or_code
!= BIT_IOR_EXPR
2068 && and_or_code
!= BIT_AND_EXPR
)
2070 if (TREE_CODE_CLASS (and_or_code
)
2073 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2074 push_pred (norm_preds
, n_pred
);
2077 push_pred (norm_preds
, pred
);
2081 work_list
.safe_push (pred
);
2082 hash_set
<tree
> mark_set
;
2084 while (!work_list
.is_empty ())
2086 pred_info a_pred
= work_list
.pop ();
2087 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
,
2088 and_or_code
, &work_list
, &mark_set
);
2090 if (and_or_code
== BIT_AND_EXPR
)
2091 norm_preds
->safe_push (norm_chain
);
2093 work_list
.release ();
2097 normalize_one_pred_chain (pred_chain_union
*norm_preds
,
2098 pred_chain one_chain
)
2100 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2101 hash_set
<tree
> mark_set
;
2102 pred_chain norm_chain
= vNULL
;
2105 for (i
= 0; i
< one_chain
.length (); i
++)
2107 work_list
.safe_push (one_chain
[i
]);
2108 mark_set
.add (one_chain
[i
].pred_lhs
);
2111 while (!work_list
.is_empty ())
2113 pred_info a_pred
= work_list
.pop ();
2114 normalize_one_pred_1 (0, &norm_chain
, a_pred
,
2115 BIT_AND_EXPR
, &work_list
, &mark_set
);
2118 norm_preds
->safe_push (norm_chain
);
2119 work_list
.release ();
2122 /* Normalize predicate chains PREDS and returns the normalized one. */
2124 static pred_chain_union
2125 normalize_preds (pred_chain_union preds
, gimple
*use_or_def
, bool is_use
)
2127 pred_chain_union norm_preds
= vNULL
;
2128 size_t n
= preds
.length ();
2131 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2133 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2134 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2137 for (i
= 0; i
< n
; i
++)
2139 if (preds
[i
].length () != 1)
2140 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2143 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2144 preds
[i
].release ();
2150 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2151 dump_predicates (use_or_def
, norm_preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2154 destroy_predicate_vecs (&preds
);
2159 /* Computes the predicates that guard the use and checks
2160 if the incoming paths that have empty (or possibly
2161 empty) definition can be pruned/filtered. The function returns
2162 true if it can be determined that the use of PHI's def in
2163 USE_STMT is guarded with a predicate set not overlapping with
2164 predicate sets of all runtime paths that do not have a definition.
2166 Returns false if it is not or it can not be determined. USE_BB is
2167 the bb of the use (for phi operand use, the bb is not the bb of
2168 the phi stmt, but the src bb of the operand edge).
2170 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2171 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2172 set of phis being visited.
2174 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2175 If *DEF_PREDS is the empty vector, the defining predicate chains of
2176 PHI will be computed and stored into *DEF_PREDS as needed.
2178 VISITED_PHIS is a pointer set of phis being visited. */
2181 is_use_properly_guarded (gimple
*use_stmt
,
2184 unsigned uninit_opnds
,
2185 pred_chain_union
*def_preds
,
2186 hash_set
<gphi
*> *visited_phis
)
2189 pred_chain_union preds
= vNULL
;
2190 bool has_valid_preds
= false;
2191 bool is_properly_guarded
= false;
2193 if (visited_phis
->add (phi
))
2196 phi_bb
= gimple_bb (phi
);
2198 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2201 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2203 if (!has_valid_preds
)
2205 destroy_predicate_vecs (&preds
);
2209 /* Try to prune the dead incoming phi edges. */
2211 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2214 if (is_properly_guarded
)
2216 destroy_predicate_vecs (&preds
);
2220 if (def_preds
->is_empty ())
2222 has_valid_preds
= find_def_preds (def_preds
, phi
);
2224 if (!has_valid_preds
)
2226 destroy_predicate_vecs (&preds
);
2230 simplify_preds (def_preds
, phi
, false);
2231 *def_preds
= normalize_preds (*def_preds
, phi
, false);
2234 simplify_preds (&preds
, use_stmt
, true);
2235 preds
= normalize_preds (preds
, use_stmt
, true);
2237 is_properly_guarded
= is_superset_of (*def_preds
, preds
);
2239 destroy_predicate_vecs (&preds
);
2240 return is_properly_guarded
;
2243 /* Searches through all uses of a potentially
2244 uninitialized variable defined by PHI and returns a use
2245 statement if the use is not properly guarded. It returns
2246 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2247 holding the position(s) of uninit PHI operands. WORKLIST
2248 is the vector of candidate phis that may be updated by this
2249 function. ADDED_TO_WORKLIST is the pointer set tracking
2250 if the new phi is already in the worklist. */
2253 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2254 vec
<gphi
*> *worklist
,
2255 hash_set
<gphi
*> *added_to_worklist
)
2258 use_operand_p use_p
;
2260 imm_use_iterator iter
;
2261 pred_chain_union def_preds
= vNULL
;
2264 phi_result
= gimple_phi_result (phi
);
2266 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2270 use_stmt
= USE_STMT (use_p
);
2271 if (is_gimple_debug (use_stmt
))
2274 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2275 use_bb
= gimple_phi_arg_edge (use_phi
,
2276 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2278 use_bb
= gimple_bb (use_stmt
);
2280 hash_set
<gphi
*> visited_phis
;
2281 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2282 &def_preds
, &visited_phis
))
2285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2287 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2288 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2290 /* Found one real use, return. */
2291 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2297 /* Found a phi use that is not guarded,
2298 add the phi to the worklist. */
2299 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2303 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2304 print_gimple_stmt (dump_file
, use_stmt
, 0, 0);
2307 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2308 possibly_undefined_names
->add (phi_result
);
2312 destroy_predicate_vecs (&def_preds
);
2316 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2317 and gives warning if there exists a runtime path from the entry to a
2318 use of the PHI def that does not contain a definition. In other words,
2319 the warning is on the real use. The more dead paths that can be pruned
2320 by the compiler, the fewer false positives the warning is. WORKLIST
2321 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2322 a pointer set tracking if the new phi is added to the worklist or not. */
2325 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2326 hash_set
<gphi
*> *added_to_worklist
)
2328 unsigned uninit_opnds
;
2329 gimple
*uninit_use_stmt
= 0;
2334 /* Don't look at virtual operands. */
2335 if (virtual_operand_p (gimple_phi_result (phi
)))
2338 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2340 if (MASK_EMPTY (uninit_opnds
))
2343 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2345 fprintf (dump_file
, "[CHECK]: examining phi: ");
2346 print_gimple_stmt (dump_file
, phi
, 0, 0);
2349 /* Now check if we have any use of the value without proper guard. */
2350 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2351 worklist
, added_to_worklist
);
2353 /* All uses are properly guarded. */
2354 if (!uninit_use_stmt
)
2357 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2358 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2359 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2361 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2362 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2364 loc
= UNKNOWN_LOCATION
;
2365 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2366 SSA_NAME_VAR (uninit_op
),
2367 "%qD may be used uninitialized in this function",
2368 uninit_use_stmt
, loc
);
2373 gate_warn_uninitialized (void)
2375 return warn_uninitialized
|| warn_maybe_uninitialized
;
2380 const pass_data pass_data_late_warn_uninitialized
=
2382 GIMPLE_PASS
, /* type */
2383 "uninit", /* name */
2384 OPTGROUP_NONE
, /* optinfo_flags */
2385 TV_NONE
, /* tv_id */
2386 PROP_ssa
, /* properties_required */
2387 0, /* properties_provided */
2388 0, /* properties_destroyed */
2389 0, /* todo_flags_start */
2390 0, /* todo_flags_finish */
2393 class pass_late_warn_uninitialized
: public gimple_opt_pass
2396 pass_late_warn_uninitialized (gcc::context
*ctxt
)
2397 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
2400 /* opt_pass methods: */
2401 opt_pass
* clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
2402 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2403 virtual unsigned int execute (function
*);
2405 }; // class pass_late_warn_uninitialized
2408 pass_late_warn_uninitialized::execute (function
*fun
)
2412 vec
<gphi
*> worklist
= vNULL
;
2414 calculate_dominance_info (CDI_DOMINATORS
);
2415 calculate_dominance_info (CDI_POST_DOMINATORS
);
2416 /* Re-do the plain uninitialized variable check, as optimization may have
2417 straightened control flow. Do this first so that we don't accidentally
2418 get a "may be" warning when we'd have seen an "is" warning later. */
2419 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2421 timevar_push (TV_TREE_UNINIT
);
2423 possibly_undefined_names
= new hash_set
<tree
>;
2424 hash_set
<gphi
*> added_to_worklist
;
2426 /* Initialize worklist */
2427 FOR_EACH_BB_FN (bb
, fun
)
2428 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2430 gphi
*phi
= gsi
.phi ();
2433 n
= gimple_phi_num_args (phi
);
2435 /* Don't look at virtual operands. */
2436 if (virtual_operand_p (gimple_phi_result (phi
)))
2439 for (i
= 0; i
< n
; ++i
)
2441 tree op
= gimple_phi_arg_def (phi
, i
);
2442 if (TREE_CODE (op
) == SSA_NAME
2443 && uninit_undefined_value_p (op
))
2445 worklist
.safe_push (phi
);
2446 added_to_worklist
.add (phi
);
2447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2449 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
2450 print_gimple_stmt (dump_file
, phi
, 0, 0);
2457 while (worklist
.length () != 0)
2460 cur_phi
= worklist
.pop ();
2461 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
2464 worklist
.release ();
2465 delete possibly_undefined_names
;
2466 possibly_undefined_names
= NULL
;
2467 free_dominance_info (CDI_POST_DOMINATORS
);
2468 timevar_pop (TV_TREE_UNINIT
);
2475 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
2477 return new pass_late_warn_uninitialized (ctxt
);
2482 execute_early_warn_uninitialized (void)
2484 /* Currently, this pass runs always but
2485 execute_late_warn_uninitialized only runs with optimization. With
2486 optimization we want to warn about possible uninitialized as late
2487 as possible, thus don't do it here. However, without
2488 optimization we need to warn here about "may be uninitialized". */
2489 calculate_dominance_info (CDI_POST_DOMINATORS
);
2491 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize
);
2493 /* Post-dominator information can not be reliably updated. Free it
2496 free_dominance_info (CDI_POST_DOMINATORS
);
2503 const pass_data pass_data_early_warn_uninitialized
=
2505 GIMPLE_PASS
, /* type */
2506 "*early_warn_uninitialized", /* name */
2507 OPTGROUP_NONE
, /* optinfo_flags */
2508 TV_TREE_UNINIT
, /* tv_id */
2509 PROP_ssa
, /* properties_required */
2510 0, /* properties_provided */
2511 0, /* properties_destroyed */
2512 0, /* todo_flags_start */
2513 0, /* todo_flags_finish */
2516 class pass_early_warn_uninitialized
: public gimple_opt_pass
2519 pass_early_warn_uninitialized (gcc::context
*ctxt
)
2520 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
2523 /* opt_pass methods: */
2524 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
2525 virtual unsigned int execute (function
*)
2527 return execute_early_warn_uninitialized ();
2530 }; // class pass_early_warn_uninitialized
2535 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
2537 return new pass_early_warn_uninitialized (ctxt
);