1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2021 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/>. */
21 #define INCLUDE_STRING
24 #include "coretypes.h"
28 #include "tree-pass.h"
30 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "fold-const.h"
33 #include "gimple-iterator.h"
41 /* This implements the pass that does predicate aware warning on uses of
42 possibly uninitialized variables. The pass first collects the set of
43 possibly uninitialized SSA names. For each such name, it walks through
44 all its immediate uses. For each immediate use, it rebuilds the condition
45 expression (the predicate) that guards the use. The predicate is then
46 examined to see if the variable is always defined under that same condition.
47 This is done either by pruning the unrealizable paths that lead to the
48 default definitions or by checking if the predicate set that guards the
49 defining paths is a superset of the use predicate. */
51 /* Max PHI args we can handle in pass. */
52 const unsigned max_phi_args
= 32;
54 /* Pointer set of potentially undefined ssa names, i.e.,
55 ssa names that are defined by phi with operands that
56 are not defined or potentially undefined. */
57 static hash_set
<tree
> *possibly_undefined_names
= 0;
59 /* Bit mask handling macros. */
60 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
61 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
62 #define MASK_EMPTY(mask) (mask == 0)
64 /* Returns the first bit position (starting from LSB)
65 in mask that is non zero. Returns -1 if the mask is empty. */
67 get_mask_first_set_bit (unsigned mask
)
73 while ((mask
& (1 << pos
)) == 0)
78 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
80 /* Return true if T, an SSA_NAME, has an undefined value. */
82 has_undefined_value_p (tree t
)
84 return (ssa_undefined_value_p (t
)
85 || (possibly_undefined_names
86 && possibly_undefined_names
->contains (t
)));
89 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
90 is set on SSA_NAME_VAR. */
93 uninit_undefined_value_p (tree t
)
95 if (!has_undefined_value_p (t
))
97 if (SSA_NAME_VAR (t
) && TREE_NO_WARNING (SSA_NAME_VAR (t
)))
102 /* Emit warnings for uninitialized variables. This is done in two passes.
104 The first pass notices real uses of SSA names with undefined values.
105 Such uses are unconditionally uninitialized, and we can be certain that
106 such a use is a mistake. This pass is run before most optimizations,
107 so that we catch as many as we can.
109 The second pass follows PHI nodes to find uses that are potentially
110 uninitialized. In this case we can't necessarily prove that the use
111 is really uninitialized. This pass is run after most optimizations,
112 so that we thread as many jumps and possible, and delete as much dead
113 code as possible, in order to reduce false positives. We also look
114 again for plain uninitialized variables, since optimization may have
115 changed conditionally uninitialized to unconditionally uninitialized. */
117 /* Emit a warning for EXPR based on variable VAR at the point in the
118 program T, an SSA_NAME, is used being uninitialized. The exact
119 warning text is in MSGID and DATA is the gimple stmt with info about
120 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
121 gives which argument of the phi node to take the location from. WC
122 is the warning code. */
125 warn_uninit (enum opt_code wc
, tree t
, tree expr
, tree var
,
126 const char *gmsgid
, void *data
, location_t phiarg_loc
)
128 gimple
*context
= (gimple
*) data
;
129 location_t location
, cfun_loc
;
130 expanded_location xloc
, floc
;
132 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
133 turns in a COMPLEX_EXPR with the not initialized part being
134 set to its previous (undefined) value. */
135 if (is_gimple_assign (context
)
136 && gimple_assign_rhs_code (context
) == COMPLEX_EXPR
)
138 if (!has_undefined_value_p (t
))
141 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
142 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
143 created for conversion from scalar to complex. Use the underlying var of
144 the COMPLEX_EXPRs real part in that case. See PR71581. */
145 if (expr
== NULL_TREE
147 && SSA_NAME_VAR (t
) == NULL_TREE
148 && is_gimple_assign (SSA_NAME_DEF_STMT (t
))
149 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t
)) == COMPLEX_EXPR
)
151 tree v
= gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t
));
152 if (TREE_CODE (v
) == SSA_NAME
153 && has_undefined_value_p (v
)
154 && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t
))))
156 expr
= SSA_NAME_VAR (v
);
161 if (expr
== NULL_TREE
)
164 /* TREE_NO_WARNING either means we already warned, or the front end
165 wishes to suppress the warning. */
167 && (gimple_no_warning_p (context
)
168 || (gimple_assign_single_p (context
)
169 && TREE_NO_WARNING (gimple_assign_rhs1 (context
)))))
170 || TREE_NO_WARNING (expr
))
173 if (context
!= NULL
&& gimple_has_location (context
))
174 location
= gimple_location (context
);
175 else if (phiarg_loc
!= UNKNOWN_LOCATION
)
176 location
= phiarg_loc
;
178 location
= DECL_SOURCE_LOCATION (var
);
179 location
= linemap_resolve_location (line_table
, location
,
180 LRK_SPELLING_LOCATION
, NULL
);
181 cfun_loc
= DECL_SOURCE_LOCATION (cfun
->decl
);
182 xloc
= expand_location (location
);
183 floc
= expand_location (cfun_loc
);
184 auto_diagnostic_group d
;
185 if (warning_at (location
, wc
, gmsgid
, expr
))
187 TREE_NO_WARNING (expr
) = 1;
189 if (location
== DECL_SOURCE_LOCATION (var
))
191 if (xloc
.file
!= floc
.file
192 || linemap_location_before_p (line_table
, location
, cfun_loc
)
193 || linemap_location_before_p (line_table
, cfun
->function_end_locus
,
195 inform (DECL_SOURCE_LOCATION (var
), "%qD was declared here", var
);
199 struct check_defs_data
201 /* If we found any may-defs besides must-def clobbers. */
205 /* Callback for walk_aliased_vdefs. */
208 check_defs (ao_ref
*ref
, tree vdef
, void *data_
)
210 check_defs_data
*data
= (check_defs_data
*)data_
;
211 gimple
*def_stmt
= SSA_NAME_DEF_STMT (vdef
);
213 /* The ASAN_MARK intrinsic doesn't modify the variable. */
214 if (is_gimple_call (def_stmt
)
215 && gimple_call_internal_p (def_stmt
, IFN_ASAN_MARK
))
218 /* End of VLA scope is not a kill. */
219 if (gimple_call_builtin_p (def_stmt
, BUILT_IN_STACK_RESTORE
))
222 /* If this is a clobber then if it is not a kill walk past it. */
223 if (gimple_clobber_p (def_stmt
))
225 if (stmt_kills_ref_p (def_stmt
, ref
))
230 /* Found a may-def on this path. */
231 data
->found_may_defs
= true;
235 /* Counters and limits controlling the the depth of analysis and
236 strictness of the warning. */
239 /* Number of VDEFs encountered. */
240 unsigned int vdef_cnt
;
241 /* Number of statements examined by walk_aliased_vdefs. */
242 unsigned int oracle_cnt
;
243 /* Limit on the number of statements visited by walk_aliased_vdefs. */
245 /* Set when basic block with statement is executed unconditionally. */
246 bool always_executed
;
247 /* Set to issue -Wmaybe-uninitialized. */
251 /* Determine if REF references an uninitialized operand and diagnose
255 maybe_warn_operand (ao_ref
&ref
, gimple
*stmt
, tree lhs
, tree rhs
,
258 bool has_bit_insert
= false;
259 use_operand_p luse_p
;
260 imm_use_iterator liter
;
262 if (TREE_NO_WARNING (rhs
))
265 /* Do not warn if the base was marked so or this is a
266 hard register var. */
267 tree base
= ao_ref_base (&ref
);
269 && DECL_HARD_REGISTER (base
))
270 || TREE_NO_WARNING (base
))
273 /* Do not warn if the access is fully outside of the variable. */
274 poly_int64 decl_size
;
276 && ((known_size_p (ref
.size
)
277 && known_eq (ref
.max_size
, ref
.size
)
278 && known_le (ref
.offset
+ ref
.size
, 0))
279 || (known_ge (ref
.offset
, 0)
281 && poly_int_tree_p (DECL_SIZE (base
), &decl_size
)
282 && known_le (decl_size
, ref
.offset
))))
285 /* Do not warn if the result of the access is then used for
286 a BIT_INSERT_EXPR. */
287 if (lhs
&& TREE_CODE (lhs
) == SSA_NAME
)
288 FOR_EACH_IMM_USE_FAST (luse_p
, liter
, lhs
)
290 gimple
*use_stmt
= USE_STMT (luse_p
);
291 /* BIT_INSERT_EXPR first operand should not be considered
292 a use for the purpose of uninit warnings. */
293 if (gassign
*ass
= dyn_cast
<gassign
*> (use_stmt
))
295 if (gimple_assign_rhs_code (ass
) == BIT_INSERT_EXPR
296 && luse_p
->use
== gimple_assign_rhs1_ptr (ass
))
298 has_bit_insert
= true;
307 /* Limit the walking to a constant number of stmts after
308 we overcommit quadratic behavior for small functions
309 and O(n) behavior. */
310 if (wlims
.oracle_cnt
> 128 * 128
311 && wlims
.oracle_cnt
> wlims
.vdef_cnt
* 2)
314 check_defs_data data
;
315 bool fentry_reached
= false;
316 data
.found_may_defs
= false;
317 tree use
= gimple_vuse (stmt
);
320 int res
= walk_aliased_vdefs (&ref
, use
,
321 check_defs
, &data
, NULL
,
322 &fentry_reached
, wlims
.limit
);
325 wlims
.oracle_cnt
+= wlims
.limit
;
329 wlims
.oracle_cnt
+= res
;
330 if (data
.found_may_defs
)
333 bool found_alloc
= false;
337 if (TREE_CODE (base
) == MEM_REF
)
338 base
= TREE_OPERAND (base
, 0);
340 /* Follow the chain of SSA_NAME assignments looking for an alloca
341 call (or VLA) or malloc/realloc, or for decls. If any is found
342 (and in the latter case, the operand is a local variable) issue
344 while (TREE_CODE (base
) == SSA_NAME
)
346 gimple
*def_stmt
= SSA_NAME_DEF_STMT (base
);
348 if (is_gimple_call (def_stmt
)
349 && gimple_call_builtin_p (def_stmt
))
351 /* Detect uses of uninitialized alloca/VLAs. */
352 tree fndecl
= gimple_call_fndecl (def_stmt
);
353 const built_in_function fncode
= DECL_FUNCTION_CODE (fndecl
);
354 if (fncode
== BUILT_IN_ALLOCA
355 || fncode
== BUILT_IN_ALLOCA_WITH_ALIGN
356 || fncode
== BUILT_IN_MALLOC
)
361 if (!is_gimple_assign (def_stmt
))
364 tree_code code
= gimple_assign_rhs_code (def_stmt
);
365 if (code
!= ADDR_EXPR
&& code
!= POINTER_PLUS_EXPR
)
368 base
= gimple_assign_rhs1 (def_stmt
);
369 if (TREE_CODE (base
) == ADDR_EXPR
)
370 base
= TREE_OPERAND (base
, 0);
373 || TREE_CODE (base
) == COMPONENT_REF
)
376 if (TREE_CODE (base
) == MEM_REF
)
377 base
= TREE_OPERAND (base
, 0);
379 if (tree ba
= get_base_address (base
))
383 /* Replace the RHS expression with BASE so that it
384 refers to it in the diagnostic (instead of to
388 && TREE_CODE (rhs
) != COMPONENT_REF
)
392 /* Do not warn if it can be initialized outside this function.
393 If we did not reach function entry then we found killing
394 clobbers on all paths to entry. */
397 /* ??? We'd like to use ref_may_alias_global_p but that
398 excludes global readonly memory and thus we get bogus
399 warnings from p = cond ? "a" : "b" for example. */
401 || is_global_var (base
)))
404 /* Strip the address-of expression from arrays passed to functions. */
405 if (TREE_CODE (rhs
) == ADDR_EXPR
)
406 rhs
= TREE_OPERAND (rhs
, 0);
408 /* Check again since RHS may have changed above. */
409 if (TREE_NO_WARNING (rhs
))
412 /* Avoid warning about empty types such as structs with no members.
413 The first_field() test is important for C++ where the predicate
414 alone isn't always sufficient. */
415 tree rhstype
= TREE_TYPE (rhs
);
416 if (POINTER_TYPE_P (rhstype
))
417 rhstype
= TREE_TYPE (rhstype
);
418 if (is_empty_type (rhstype
))
422 /* We didn't find any may-defs so on all paths either
423 reached function entry or a killing clobber. */
425 = linemap_resolve_location (line_table
, gimple_location (stmt
),
426 LRK_SPELLING_LOCATION
, NULL
);
427 if (wlims
.always_executed
)
429 if (warning_at (location
, OPT_Wuninitialized
,
430 "%G%qE is used uninitialized", stmt
, rhs
))
432 /* ??? This is only effective for decls as in
433 gcc.dg/uninit-B-O0.c. Avoid doing this for maybe-uninit
434 uses or accesses by functions as it may hide important
437 TREE_NO_WARNING (rhs
) = 1;
441 else if (wlims
.wmaybe_uninit
)
442 warned
= warning_at (location
, OPT_Wmaybe_uninitialized
,
443 "%G%qE may be used uninitialized", stmt
, rhs
);
445 return warned
? base
: NULL_TREE
;
449 /* Diagnose passing addresses of uninitialized objects to either const
450 pointer arguments to functions, or to functions declared with attribute
451 access implying read access to those objects. */
454 maybe_warn_pass_by_reference (gcall
*stmt
, wlimits
&wlims
)
456 if (!wlims
.wmaybe_uninit
)
459 unsigned nargs
= gimple_call_num_args (stmt
);
463 tree fndecl
= gimple_call_fndecl (stmt
);
464 tree fntype
= gimple_call_fntype (stmt
);
468 /* Const function do not read their arguments. */
469 if (gimple_call_flags (stmt
) & ECF_CONST
)
472 const built_in_function fncode
473 = (fndecl
&& gimple_call_builtin_p (stmt
, BUILT_IN_NORMAL
)
474 ? DECL_FUNCTION_CODE (fndecl
) : (built_in_function
)BUILT_IN_LAST
);
476 if (fncode
== BUILT_IN_MEMCPY
|| fncode
== BUILT_IN_MEMMOVE
)
477 /* Avoid diagnosing calls to raw memory functions (this is overly
478 permissive; consider tightening it up). */
481 /* Save the current warning setting and replace it either a "maybe"
482 when passing addresses of uninitialized variables to const-qualified
483 pointers or arguments declared with attribute read_write, or with
484 a "certain" when passing them to arguments declared with attribute
486 const bool save_always_executed
= wlims
.always_executed
;
488 /* Initialize a map of attribute access specifications for arguments
489 to the function function call. */
491 init_attr_rdwr_indices (&rdwr_idx
, TYPE_ATTRIBUTES (fntype
));
495 function_args_iterator it
;
497 FOREACH_FUNCTION_ARGS (fntype
, argtype
, it
)
501 if (!POINTER_TYPE_P (argtype
))
504 tree access_size
= NULL_TREE
;
505 const attr_access
* access
= rdwr_idx
.get (argno
- 1);
508 if (access
->mode
== access_none
509 || access
->mode
== access_write_only
)
512 if (access
->mode
== access_deferred
513 && !TYPE_READONLY (TREE_TYPE (argtype
)))
516 if (save_always_executed
&& access
->mode
== access_read_only
)
517 /* Attribute read_only arguments imply read access. */
518 wlims
.always_executed
= true;
520 /* Attribute read_write arguments are documented as requiring
521 initialized objects but it's expected that aggregates may
522 be only partially initialized regardless. */
523 wlims
.always_executed
= false;
525 if (access
->sizarg
< nargs
)
526 access_size
= gimple_call_arg (stmt
, access
->sizarg
);
528 else if (!TYPE_READONLY (TREE_TYPE (argtype
)))
530 else if (save_always_executed
&& fncode
!= BUILT_IN_LAST
)
531 /* Const-qualified arguments to built-ins imply read access. */
532 wlims
.always_executed
= true;
534 /* Const-qualified arguments to ordinary functions imply a likely
535 (but not definitive) read access. */
536 wlims
.always_executed
= false;
538 /* Ignore args we are not going to read from. */
539 if (gimple_call_arg_flags (stmt
, argno
- 1) & EAF_UNUSED
)
542 tree arg
= gimple_call_arg (stmt
, argno
- 1);
545 ao_ref_init_from_ptr_and_size (&ref
, arg
, access_size
);
546 tree argbase
= maybe_warn_operand (ref
, stmt
, NULL_TREE
, arg
, wlims
);
550 if (access
&& access
->mode
!= access_deferred
)
552 const char* const access_str
=
553 TREE_STRING_POINTER (access
->to_external_string ());
557 location_t loc
= DECL_SOURCE_LOCATION (fndecl
);
558 inform (loc
, "in a call to %qD declared with "
559 "attribute %<%s%> here", fndecl
, access_str
);
563 /* Handle calls through function pointers. */
564 location_t loc
= gimple_location (stmt
);
565 inform (loc
, "in a call to %qT declared with "
566 "attribute %<%s%>", fntype
, access_str
);
571 /* For a declaration with no relevant attribute access create
572 a dummy object and use the formatting function to avoid
573 having to complicate things here. */
574 attr_access ptr_access
= { };
576 access
= &ptr_access
;
577 const std::string argtypestr
= access
->array_as_string (argtype
);
580 location_t
loc (DECL_SOURCE_LOCATION (fndecl
));
581 inform (loc
, "by argument %u of type %s to %qD "
583 argno
, argtypestr
.c_str (), fndecl
);
587 /* Handle calls through function pointers. */
588 location_t
loc (gimple_location (stmt
));
589 inform (loc
, "by argument %u of type %s to %qT",
590 argno
, argtypestr
.c_str (), fntype
);
594 if (DECL_P (argbase
))
596 location_t loc
= DECL_SOURCE_LOCATION (argbase
);
597 inform (loc
, "%qD declared here", argbase
);
601 wlims
.always_executed
= save_always_executed
;
606 warn_uninitialized_vars (bool wmaybe_uninit
)
608 /* Counters and limits controlling the the depth of the warning. */
610 wlims
.wmaybe_uninit
= wmaybe_uninit
;
612 gimple_stmt_iterator gsi
;
614 FOR_EACH_BB_FN (bb
, cfun
)
616 basic_block succ
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
617 wlims
.always_executed
= dominated_by_p (CDI_POST_DOMINATORS
, succ
, bb
);
618 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
620 gimple
*stmt
= gsi_stmt (gsi
);
625 if (is_gimple_debug (stmt
))
628 /* We only do data flow with SSA_NAMEs, so that's all we
630 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, op_iter
, SSA_OP_USE
)
632 /* BIT_INSERT_EXPR first operand should not be considered
633 a use for the purpose of uninit warnings. */
634 if (gassign
*ass
= dyn_cast
<gassign
*> (stmt
))
636 if (gimple_assign_rhs_code (ass
) == BIT_INSERT_EXPR
637 && use_p
->use
== gimple_assign_rhs1_ptr (ass
))
640 use
= USE_FROM_PTR (use_p
);
641 if (wlims
.always_executed
)
642 warn_uninit (OPT_Wuninitialized
, use
, SSA_NAME_VAR (use
),
644 "%qD is used uninitialized", stmt
,
646 else if (wmaybe_uninit
)
647 warn_uninit (OPT_Wmaybe_uninitialized
, use
, SSA_NAME_VAR (use
),
649 "%qD may be used uninitialized",
650 stmt
, UNKNOWN_LOCATION
);
653 /* For limiting the alias walk below we count all
654 vdefs in the function. */
655 if (gimple_vdef (stmt
))
658 if (gcall
*call
= dyn_cast
<gcall
*> (stmt
))
659 maybe_warn_pass_by_reference (call
, wlims
);
660 else if (gimple_assign_load_p (stmt
)
661 && gimple_has_location (stmt
))
663 tree rhs
= gimple_assign_rhs1 (stmt
);
664 tree lhs
= gimple_assign_lhs (stmt
);
667 ao_ref_init (&ref
, rhs
);
668 tree var
= maybe_warn_operand (ref
, stmt
, lhs
, rhs
, wlims
);
674 location_t loc
= DECL_SOURCE_LOCATION (var
);
675 inform (loc
, "%qD declared here", var
);
684 /* Checks if the operand OPND of PHI is defined by
685 another phi with one operand defined by this PHI,
686 but the rest operands are all defined. If yes,
687 returns true to skip this operand as being
688 redundant. Can be enhanced to be more general. */
691 can_skip_redundant_opnd (tree opnd
, gimple
*phi
)
697 phi_def
= gimple_phi_result (phi
);
698 op_def
= SSA_NAME_DEF_STMT (opnd
);
699 if (gimple_code (op_def
) != GIMPLE_PHI
)
701 n
= gimple_phi_num_args (op_def
);
702 for (i
= 0; i
< n
; ++i
)
704 tree op
= gimple_phi_arg_def (op_def
, i
);
705 if (TREE_CODE (op
) != SSA_NAME
)
707 if (op
!= phi_def
&& uninit_undefined_value_p (op
))
714 /* Returns a bit mask holding the positions of arguments in PHI
715 that have empty (or possibly empty) definitions. */
718 compute_uninit_opnds_pos (gphi
*phi
)
721 unsigned uninit_opnds
= 0;
723 n
= gimple_phi_num_args (phi
);
724 /* Bail out for phi with too many args. */
725 if (n
> max_phi_args
)
728 for (i
= 0; i
< n
; ++i
)
730 tree op
= gimple_phi_arg_def (phi
, i
);
731 if (TREE_CODE (op
) == SSA_NAME
732 && uninit_undefined_value_p (op
)
733 && !can_skip_redundant_opnd (op
, phi
))
735 if (cfun
->has_nonlocal_label
|| cfun
->calls_setjmp
)
737 /* Ignore SSA_NAMEs that appear on abnormal edges
739 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
742 MASK_SET_BIT (uninit_opnds
, i
);
748 /* Find the immediate postdominator PDOM of the specified
749 basic block BLOCK. */
751 static inline basic_block
752 find_pdom (basic_block block
)
754 if (block
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
755 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
758 basic_block bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, block
);
760 return EXIT_BLOCK_PTR_FOR_FN (cfun
);
765 /* Find the immediate DOM of the specified basic block BLOCK. */
767 static inline basic_block
768 find_dom (basic_block block
)
770 if (block
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
771 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
774 basic_block bb
= get_immediate_dominator (CDI_DOMINATORS
, block
);
776 return ENTRY_BLOCK_PTR_FOR_FN (cfun
);
781 /* Returns true if BB1 is postdominating BB2 and BB1 is
782 not a loop exit bb. The loop exit bb check is simple and does
783 not cover all cases. */
786 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
788 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
791 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
797 /* Find the closest postdominator of a specified BB, which is control
800 static inline basic_block
801 find_control_equiv_block (basic_block bb
)
805 pdom
= find_pdom (bb
);
807 /* Skip the postdominating bb that is also loop exit. */
808 if (!is_non_loop_exit_postdominating (pdom
, bb
))
811 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
817 #define MAX_NUM_CHAINS 8
818 #define MAX_CHAIN_LEN 5
819 #define MAX_POSTDOM_CHECK 8
820 #define MAX_SWITCH_CASES 40
822 /* Computes the control dependence chains (paths of edges)
823 for DEP_BB up to the dominating basic block BB (the head node of a
824 chain should be dominated by it). CD_CHAINS is pointer to an
825 array holding the result chains. CUR_CD_CHAIN is the current
826 chain being computed. *NUM_CHAINS is total number of chains. The
827 function returns true if the information is successfully computed,
828 return false if there is no control dependence or not computed. */
831 compute_control_dep_chain (basic_block bb
, basic_block dep_bb
,
832 vec
<edge
> *cd_chains
,
834 vec
<edge
> *cur_cd_chain
,
840 bool found_cd_chain
= false;
841 size_t cur_chain_len
= 0;
843 if (*num_calls
> param_uninit_control_dep_attempts
)
847 /* Could use a set instead. */
848 cur_chain_len
= cur_cd_chain
->length ();
849 if (cur_chain_len
> MAX_CHAIN_LEN
)
852 for (i
= 0; i
< cur_chain_len
; i
++)
854 edge e
= (*cur_cd_chain
)[i
];
855 /* Cycle detected. */
860 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
863 int post_dom_check
= 0;
864 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
868 cur_cd_chain
->safe_push (e
);
869 while (!is_non_loop_exit_postdominating (cd_bb
, bb
))
873 /* Found a direct control dependence. */
874 if (*num_chains
< MAX_NUM_CHAINS
)
876 cd_chains
[*num_chains
] = cur_cd_chain
->copy ();
879 found_cd_chain
= true;
880 /* Check path from next edge. */
884 /* Now check if DEP_BB is indirectly control dependent on BB. */
885 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
, num_chains
,
886 cur_cd_chain
, num_calls
))
888 found_cd_chain
= true;
892 cd_bb
= find_pdom (cd_bb
);
894 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
895 || post_dom_check
> MAX_POSTDOM_CHECK
)
898 cur_cd_chain
->pop ();
899 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
901 gcc_assert (cur_cd_chain
->length () == cur_chain_len
);
903 return found_cd_chain
;
906 /* The type to represent a simple predicate. */
912 enum tree_code cond_code
;
916 /* The type to represent a sequence of predicates grouped
917 with .AND. operation. */
919 typedef vec
<pred_info
, va_heap
, vl_ptr
> pred_chain
;
921 /* The type to represent a sequence of pred_chains grouped
922 with .OR. operation. */
924 typedef vec
<pred_chain
, va_heap
, vl_ptr
> pred_chain_union
;
926 /* Converts the chains of control dependence edges into a set of
927 predicates. A control dependence chain is represented by a vector
928 edges. DEP_CHAINS points to an array of dependence chains.
929 NUM_CHAINS is the size of the chain array. One edge in a dependence
930 chain is mapped to predicate expression represented by pred_info
931 type. One dependence chain is converted to a composite predicate that
932 is the result of AND operation of pred_info mapped to each edge.
933 A composite predicate is presented by a vector of pred_info. On
934 return, *PREDS points to the resulting array of composite predicates.
935 *NUM_PREDS is the number of composite predictes. */
938 convert_control_dep_chain_into_preds (vec
<edge
> *dep_chains
,
940 pred_chain_union
*preds
)
942 bool has_valid_pred
= false;
944 if (num_chains
== 0 || num_chains
>= MAX_NUM_CHAINS
)
947 /* Now convert the control dep chain into a set
949 preds
->reserve (num_chains
);
951 for (i
= 0; i
< num_chains
; i
++)
953 vec
<edge
> one_cd_chain
= dep_chains
[i
];
955 has_valid_pred
= false;
956 pred_chain t_chain
= vNULL
;
957 for (j
= 0; j
< one_cd_chain
.length (); j
++)
960 gimple_stmt_iterator gsi
;
961 basic_block guard_bb
;
967 gsi
= gsi_last_bb (guard_bb
);
968 /* Ignore empty forwarder blocks. */
969 if (empty_block_p (guard_bb
) && single_succ_p (guard_bb
))
971 /* An empty basic block here is likely a PHI, and is not one
972 of the cases we handle below. */
975 has_valid_pred
= false;
978 cond_stmt
= gsi_stmt (gsi
);
979 if (is_gimple_call (cond_stmt
) && EDGE_COUNT (e
->src
->succs
) >= 2)
980 /* Ignore EH edge. Can add assertion on the other edge's flag. */
982 /* Skip if there is essentially one succesor. */
983 if (EDGE_COUNT (e
->src
->succs
) == 2)
989 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
991 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
1000 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
1002 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
1003 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
1004 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
1005 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
1006 t_chain
.safe_push (one_pred
);
1007 has_valid_pred
= true;
1009 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
1011 /* Avoid quadratic behavior. */
1012 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
1014 has_valid_pred
= false;
1017 /* Find the case label. */
1020 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
1022 tree tl
= gimple_switch_label (gs
, idx
);
1023 if (e
->dest
== label_to_block (cfun
, CASE_LABEL (tl
)))
1034 /* If more than one label reaches this block or the case
1035 label doesn't have a single value (like the default one)
1040 && !operand_equal_p (CASE_LOW (l
), CASE_HIGH (l
), 0)))
1042 has_valid_pred
= false;
1045 one_pred
.pred_lhs
= gimple_switch_index (gs
);
1046 one_pred
.pred_rhs
= CASE_LOW (l
);
1047 one_pred
.cond_code
= EQ_EXPR
;
1048 one_pred
.invert
= false;
1049 t_chain
.safe_push (one_pred
);
1050 has_valid_pred
= true;
1054 has_valid_pred
= false;
1059 if (!has_valid_pred
)
1062 preds
->safe_push (t_chain
);
1064 return has_valid_pred
;
1067 /* Computes all control dependence chains for USE_BB. The control
1068 dependence chains are then converted to an array of composite
1069 predicates pointed to by PREDS. PHI_BB is the basic block of
1070 the phi whose result is used in USE_BB. */
1073 find_predicates (pred_chain_union
*preds
,
1077 size_t num_chains
= 0, i
;
1079 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1080 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
1081 bool has_valid_pred
= false;
1082 basic_block cd_root
= 0;
1084 /* First find the closest bb that is control equivalent to PHI_BB
1085 that also dominates USE_BB. */
1087 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
1089 basic_block ctrl_eq_bb
= find_control_equiv_block (cd_root
);
1090 if (ctrl_eq_bb
&& dominated_by_p (CDI_DOMINATORS
, use_bb
, ctrl_eq_bb
))
1091 cd_root
= ctrl_eq_bb
;
1096 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
1097 &cur_chain
, &num_calls
);
1100 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
1101 for (i
= 0; i
< num_chains
; i
++)
1102 dep_chains
[i
].release ();
1103 return has_valid_pred
;
1106 /* Computes the set of incoming edges of PHI that have non empty
1107 definitions of a phi chain. The collection will be done
1108 recursively on operands that are defined by phis. CD_ROOT
1109 is the control dependence root. *EDGES holds the result, and
1110 VISITED_PHIS is a pointer set for detecting cycles. */
1113 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
1114 auto_vec
<edge
> *edges
,
1115 hash_set
<gimple
*> *visited_phis
)
1121 if (visited_phis
->add (phi
))
1124 n
= gimple_phi_num_args (phi
);
1125 for (i
= 0; i
< n
; i
++)
1127 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1128 opnd
= gimple_phi_arg_def (phi
, i
);
1130 if (TREE_CODE (opnd
) != SSA_NAME
)
1132 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1134 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ", (int) i
);
1135 print_gimple_stmt (dump_file
, phi
, 0);
1137 edges
->safe_push (opnd_edge
);
1141 gimple
*def
= SSA_NAME_DEF_STMT (opnd
);
1143 if (gimple_code (def
) == GIMPLE_PHI
1144 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (def
), cd_root
))
1145 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
1147 else if (!uninit_undefined_value_p (opnd
))
1149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1151 fprintf (dump_file
, "\n[CHECK] Found def edge %d in ",
1153 print_gimple_stmt (dump_file
, phi
, 0);
1155 edges
->safe_push (opnd_edge
);
1161 /* For each use edge of PHI, computes all control dependence chains.
1162 The control dependence chains are then converted to an array of
1163 composite predicates pointed to by PREDS. */
1166 find_def_preds (pred_chain_union
*preds
, gphi
*phi
)
1168 size_t num_chains
= 0, i
, n
;
1169 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1170 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
1171 auto_vec
<edge
> def_edges
;
1172 bool has_valid_pred
= false;
1173 basic_block phi_bb
, cd_root
= 0;
1175 phi_bb
= gimple_bb (phi
);
1176 /* First find the closest dominating bb to be
1177 the control dependence root. */
1178 cd_root
= find_dom (phi_bb
);
1182 hash_set
<gimple
*> visited_phis
;
1183 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
1185 n
= def_edges
.length ();
1189 for (i
= 0; i
< n
; i
++)
1195 opnd_edge
= def_edges
[i
];
1196 prev_nc
= num_chains
;
1197 compute_control_dep_chain (cd_root
, opnd_edge
->src
, dep_chains
,
1198 &num_chains
, &cur_chain
, &num_calls
);
1200 /* Now update the newly added chains with
1201 the phi operand edge: */
1202 if (EDGE_COUNT (opnd_edge
->src
->succs
) > 1)
1204 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
1205 dep_chains
[num_chains
++] = vNULL
;
1206 for (j
= prev_nc
; j
< num_chains
; j
++)
1207 dep_chains
[j
].safe_push (opnd_edge
);
1212 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
, preds
);
1213 for (i
= 0; i
< num_chains
; i
++)
1214 dep_chains
[i
].release ();
1215 return has_valid_pred
;
1218 /* Dump a pred_info. */
1221 dump_pred_info (pred_info one_pred
)
1223 if (one_pred
.invert
)
1224 fprintf (dump_file
, " (.NOT.) ");
1225 print_generic_expr (dump_file
, one_pred
.pred_lhs
);
1226 fprintf (dump_file
, " %s ", op_symbol_code (one_pred
.cond_code
));
1227 print_generic_expr (dump_file
, one_pred
.pred_rhs
);
1230 /* Dump a pred_chain. */
1233 dump_pred_chain (pred_chain one_pred_chain
)
1235 size_t np
= one_pred_chain
.length ();
1236 for (size_t j
= 0; j
< np
; j
++)
1238 dump_pred_info (one_pred_chain
[j
]);
1240 fprintf (dump_file
, " (.AND.) ");
1242 fprintf (dump_file
, "\n");
1246 /* Dumps the predicates (PREDS) for USESTMT. */
1249 dump_predicates (gimple
*usestmt
, pred_chain_union preds
, const char *msg
)
1251 fprintf (dump_file
, "%s", msg
);
1254 print_gimple_stmt (dump_file
, usestmt
, 0);
1255 fprintf (dump_file
, "is guarded by :\n\n");
1257 size_t num_preds
= preds
.length ();
1258 for (size_t i
= 0; i
< num_preds
; i
++)
1260 dump_pred_chain (preds
[i
]);
1261 if (i
< num_preds
- 1)
1262 fprintf (dump_file
, "(.OR.)\n");
1264 fprintf (dump_file
, "\n\n");
1268 /* Destroys the predicate set *PREDS. */
1271 destroy_predicate_vecs (pred_chain_union
*preds
)
1275 size_t n
= preds
->length ();
1276 for (i
= 0; i
< n
; i
++)
1277 (*preds
)[i
].release ();
1281 /* Computes the 'normalized' conditional code with operand
1282 swapping and condition inversion. */
1284 static enum tree_code
1285 get_cmp_code (enum tree_code orig_cmp_code
, bool swap_cond
, bool invert
)
1287 enum tree_code tc
= orig_cmp_code
;
1290 tc
= swap_tree_comparison (orig_cmp_code
);
1292 tc
= invert_tree_comparison (tc
, false);
1309 /* Returns whether VAL CMPC BOUNDARY is true. */
1312 is_value_included_in (tree val
, tree boundary
, enum tree_code cmpc
)
1314 bool inverted
= false;
1317 /* Only handle integer constant here. */
1318 if (TREE_CODE (val
) != INTEGER_CST
|| TREE_CODE (boundary
) != INTEGER_CST
)
1321 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
|| cmpc
== NE_EXPR
)
1323 cmpc
= invert_tree_comparison (cmpc
, false);
1327 if (cmpc
== EQ_EXPR
)
1328 result
= tree_int_cst_equal (val
, boundary
);
1329 else if (cmpc
== LT_EXPR
)
1330 result
= tree_int_cst_lt (val
, boundary
);
1333 gcc_assert (cmpc
== LE_EXPR
);
1334 result
= tree_int_cst_le (val
, boundary
);
1343 /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can be
1344 either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like),
1345 or BIT_AND_EXPR. EXACT_P is only meaningful for the latter. It modifies the
1346 question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL.
1347 For other values of CMPC, EXACT_P is ignored. */
1350 value_sat_pred_p (tree val
, tree boundary
, enum tree_code cmpc
,
1351 bool exact_p
= false)
1353 if (cmpc
!= BIT_AND_EXPR
)
1354 return is_value_included_in (val
, boundary
, cmpc
);
1356 wide_int andw
= wi::to_wide (val
) & wi::to_wide (boundary
);
1358 return andw
== wi::to_wide (val
);
1360 return andw
.to_uhwi ();
1363 /* Returns true if PRED is common among all the predicate
1364 chains (PREDS) (and therefore can be factored out). */
1367 find_matching_predicate_in_rest_chains (pred_info pred
, pred_chain_union preds
)
1372 if (preds
.length () == 1)
1375 for (i
= 1; i
< preds
.length (); i
++)
1378 pred_chain one_chain
= preds
[i
];
1379 n
= one_chain
.length ();
1380 for (j
= 0; j
< n
; j
++)
1382 pred_info pred2
= one_chain
[j
];
1383 /* Can relax the condition comparison to not
1384 use address comparison. However, the most common
1385 case is that multiple control dependent paths share
1386 a common path prefix, so address comparison should
1389 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
1390 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
1391 && pred2
.invert
== pred
.invert
)
1403 /* Forward declaration. */
1404 static bool is_use_properly_guarded (gimple
*use_stmt
,
1407 unsigned uninit_opnds
,
1408 pred_chain_union
*def_preds
,
1409 hash_set
<gphi
*> *visited_phis
);
1411 /* Returns true if all uninitialized opnds are pruned. Returns false
1412 otherwise. PHI is the phi node with uninitialized operands,
1413 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1414 FLAG_DEF is the statement defining the flag guarding the use of the
1415 PHI output, BOUNDARY_CST is the const value used in the predicate
1416 associated with the flag, CMP_CODE is the comparison code used in
1417 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1418 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1424 flag_1 = phi <0, 1> // (1)
1425 var_1 = phi <undef, some_val>
1429 flag_2 = phi <0, flag_1, flag_1> // (2)
1430 var_2 = phi <undef, var_1, var_1>
1437 Because some flag arg in (1) is not constant, if we do not look into the
1438 flag phis recursively, it is conservatively treated as unknown and var_1
1439 is thought to be flowed into use at (3). Since var_1 is potentially
1440 uninitialized a false warning will be emitted.
1441 Checking recursively into (1), the compiler can find out that only some_val
1442 (which is defined) can flow into (3) which is OK. */
1445 prune_uninit_phi_opnds (gphi
*phi
, unsigned uninit_opnds
, gphi
*flag_def
,
1446 tree boundary_cst
, enum tree_code cmp_code
,
1447 hash_set
<gphi
*> *visited_phis
,
1448 bitmap
*visited_flag_phis
)
1452 for (i
= 0; i
< MIN (max_phi_args
, gimple_phi_num_args (flag_def
)); i
++)
1456 if (!MASK_TEST_BIT (uninit_opnds
, i
))
1459 flag_arg
= gimple_phi_arg_def (flag_def
, i
);
1460 if (!is_gimple_constant (flag_arg
))
1462 gphi
*flag_arg_def
, *phi_arg_def
;
1464 unsigned uninit_opnds_arg_phi
;
1466 if (TREE_CODE (flag_arg
) != SSA_NAME
)
1468 flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
1472 phi_arg
= gimple_phi_arg_def (phi
, i
);
1473 if (TREE_CODE (phi_arg
) != SSA_NAME
)
1476 phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
1480 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
1483 if (!*visited_flag_phis
)
1484 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
1486 tree phi_result
= gimple_phi_result (flag_arg_def
);
1487 if (bitmap_bit_p (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
)))
1490 bitmap_set_bit (*visited_flag_phis
,
1491 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def
)));
1493 /* Now recursively prune the uninitialized phi args. */
1494 uninit_opnds_arg_phi
= compute_uninit_opnds_pos (phi_arg_def
);
1495 if (!prune_uninit_phi_opnds
1496 (phi_arg_def
, uninit_opnds_arg_phi
, flag_arg_def
, boundary_cst
,
1497 cmp_code
, visited_phis
, visited_flag_phis
))
1500 phi_result
= gimple_phi_result (flag_arg_def
);
1501 bitmap_clear_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
1505 /* Now check if the constant is in the guarded range. */
1506 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
1511 /* Now that we know that this undefined edge is not
1512 pruned. If the operand is defined by another phi,
1513 we can further prune the incoming edges of that
1514 phi by checking the predicates of this operands. */
1516 opnd
= gimple_phi_arg_def (phi
, i
);
1517 opnd_def
= SSA_NAME_DEF_STMT (opnd
);
1518 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
1521 unsigned uninit_opnds2
= compute_uninit_opnds_pos (opnd_def_phi
);
1522 if (!MASK_EMPTY (uninit_opnds2
))
1524 pred_chain_union def_preds
= vNULL
;
1526 opnd_edge
= gimple_phi_arg_edge (phi
, i
);
1527 ok
= is_use_properly_guarded (phi
,
1533 destroy_predicate_vecs (&def_preds
);
1546 /* A helper function finds predicate which will be examined against uninit
1547 paths. If there is no "flag_var cmp const" form predicate, the function
1548 tries to find predicate of form like "flag_var cmp flag_var" with value
1549 range info. PHI is the phi node whose incoming (undefined) paths need to
1550 be examined. On success, the function returns the comparsion code, sets
1551 defintion gimple of the flag_var to FLAG_DEF, sets boundary_cst to
1552 BOUNDARY_CST. On fail, the function returns ERROR_MARK. */
1554 static enum tree_code
1555 find_var_cmp_const (pred_chain_union preds
, gphi
*phi
, gimple
**flag_def
,
1558 enum tree_code vrinfo_code
= ERROR_MARK
, code
;
1559 gimple
*vrinfo_def
= NULL
;
1560 tree vrinfo_cst
= NULL
, cond_lhs
, cond_rhs
;
1562 gcc_assert (preds
.length () > 0);
1563 pred_chain the_pred_chain
= preds
[0];
1564 for (unsigned i
= 0; i
< the_pred_chain
.length (); i
++)
1566 bool use_vrinfo_p
= false;
1567 pred_info the_pred
= the_pred_chain
[i
];
1568 cond_lhs
= the_pred
.pred_lhs
;
1569 cond_rhs
= the_pred
.pred_rhs
;
1570 if (cond_lhs
== NULL_TREE
|| cond_rhs
== NULL_TREE
)
1573 code
= get_cmp_code (the_pred
.cond_code
, false, the_pred
.invert
);
1574 if (code
== ERROR_MARK
)
1577 if (TREE_CODE (cond_lhs
) == SSA_NAME
&& is_gimple_constant (cond_rhs
))
1579 else if (TREE_CODE (cond_rhs
) == SSA_NAME
1580 && is_gimple_constant (cond_lhs
))
1582 std::swap (cond_lhs
, cond_rhs
);
1583 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
1586 /* Check if we can take advantage of "flag_var comp flag_var" predicate
1587 with value range info. Note only first of such case is handled. */
1588 else if (vrinfo_code
== ERROR_MARK
1589 && TREE_CODE (cond_lhs
) == SSA_NAME
1590 && TREE_CODE (cond_rhs
) == SSA_NAME
)
1592 gimple
* lhs_def
= SSA_NAME_DEF_STMT (cond_lhs
);
1593 if (!lhs_def
|| gimple_code (lhs_def
) != GIMPLE_PHI
1594 || gimple_bb (lhs_def
) != gimple_bb (phi
))
1596 std::swap (cond_lhs
, cond_rhs
);
1597 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
1601 /* Check value range info of rhs, do following transforms:
1602 flag_var < [min, max] -> flag_var < max
1603 flag_var > [min, max] -> flag_var > min
1605 We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
1606 flag_var <= [min, max] -> flag_var < [min, max+1]
1607 flag_var >= [min, max] -> flag_var > [min-1, max]
1608 if no overflow/wrap. */
1610 tree type
= TREE_TYPE (cond_lhs
);
1611 if (!INTEGRAL_TYPE_P (type
)
1612 || get_range_info (cond_rhs
, &min
, &max
) != VR_RANGE
)
1615 && max
!= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
1621 && min
!= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
1626 if (code
== LT_EXPR
)
1627 cond_rhs
= wide_int_to_tree (type
, max
);
1628 else if (code
== GT_EXPR
)
1629 cond_rhs
= wide_int_to_tree (type
, min
);
1633 use_vrinfo_p
= true;
1638 if ((*flag_def
= SSA_NAME_DEF_STMT (cond_lhs
)) == NULL
)
1641 if (gimple_code (*flag_def
) != GIMPLE_PHI
1642 || gimple_bb (*flag_def
) != gimple_bb (phi
)
1643 || !find_matching_predicate_in_rest_chains (the_pred
, preds
))
1646 /* Return if any "flag_var comp const" predicate is found. */
1649 *boundary_cst
= cond_rhs
;
1652 /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */
1653 else if (vrinfo_code
== ERROR_MARK
)
1656 vrinfo_def
= *flag_def
;
1657 vrinfo_cst
= cond_rhs
;
1660 /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */
1661 if (vrinfo_code
!= ERROR_MARK
)
1663 *flag_def
= vrinfo_def
;
1664 *boundary_cst
= vrinfo_cst
;
1669 /* A helper function that determines if the predicate set
1670 of the use is not overlapping with that of the uninit paths.
1671 The most common senario of guarded use is in Example 1:
1684 The real world examples are usually more complicated, but similar
1685 and usually result from inlining:
1687 bool init_func (int * x)
1699 if (!init_func (&x))
1706 Another possible use scenario is in the following trivial example:
1718 Predicate analysis needs to compute the composite predicate:
1720 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1721 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1722 (the predicate chain for phi operand defs can be computed
1723 starting from a bb that is control equivalent to the phi's
1724 bb and is dominating the operand def.)
1726 and check overlapping:
1727 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1730 This implementation provides framework that can handle
1731 scenarios. (Note that many simple cases are handled properly
1732 without the predicate analysis -- this is due to jump threading
1733 transformation which eliminates the merge point thus makes
1734 path sensitive analysis unnecessary.)
1736 PHI is the phi node whose incoming (undefined) paths need to be
1737 pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
1738 positions. VISITED_PHIS is the pointer set of phi stmts being
1742 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds
,
1743 gphi
*phi
, unsigned uninit_opnds
,
1744 hash_set
<gphi
*> *visited_phis
)
1746 gimple
*flag_def
= 0;
1747 tree boundary_cst
= 0;
1748 enum tree_code cmp_code
;
1749 bitmap visited_flag_phis
= NULL
;
1750 bool all_pruned
= false;
1752 /* Find within the common prefix of multiple predicate chains
1753 a predicate that is a comparison of a flag variable against
1755 cmp_code
= find_var_cmp_const (preds
, phi
, &flag_def
, &boundary_cst
);
1756 if (cmp_code
== ERROR_MARK
)
1759 /* Now check all the uninit incoming edge has a constant flag value
1760 that is in conflict with the use guard/predicate. */
1761 all_pruned
= prune_uninit_phi_opnds
1762 (phi
, uninit_opnds
, as_a
<gphi
*> (flag_def
), boundary_cst
, cmp_code
,
1763 visited_phis
, &visited_flag_phis
);
1765 if (visited_flag_phis
)
1766 BITMAP_FREE (visited_flag_phis
);
1771 /* The helper function returns true if two predicates X1 and X2
1772 are equivalent. It assumes the expressions have already
1773 properly re-associated. */
1776 pred_equal_p (pred_info x1
, pred_info x2
)
1778 enum tree_code c1
, c2
;
1779 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1780 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1784 if (x1
.invert
!= x2
.invert
1785 && TREE_CODE_CLASS (x2
.cond_code
) == tcc_comparison
)
1786 c2
= invert_tree_comparison (x2
.cond_code
, false);
1793 /* Returns true if the predication is testing !=. */
1796 is_neq_relop_p (pred_info pred
)
1799 return ((pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
1800 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
));
1803 /* Returns true if pred is of the form X != 0. */
1806 is_neq_zero_form_p (pred_info pred
)
1808 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
1809 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
1814 /* The helper function returns true if two predicates X1
1815 is equivalent to X2 != 0. */
1818 pred_expr_equal_p (pred_info x1
, tree x2
)
1820 if (!is_neq_zero_form_p (x1
))
1823 return operand_equal_p (x1
.pred_lhs
, x2
, 0);
1826 /* Returns true of the domain of single predicate expression
1827 EXPR1 is a subset of that of EXPR2. Returns false if it
1828 cannot be proved. */
1831 is_pred_expr_subset_of (pred_info expr1
, pred_info expr2
)
1833 enum tree_code code1
, code2
;
1835 if (pred_equal_p (expr1
, expr2
))
1838 if ((TREE_CODE (expr1
.pred_rhs
) != INTEGER_CST
)
1839 || (TREE_CODE (expr2
.pred_rhs
) != INTEGER_CST
))
1842 if (!operand_equal_p (expr1
.pred_lhs
, expr2
.pred_lhs
, 0))
1845 code1
= expr1
.cond_code
;
1847 code1
= invert_tree_comparison (code1
, false);
1848 code2
= expr2
.cond_code
;
1850 code2
= invert_tree_comparison (code2
, false);
1852 if (code2
== NE_EXPR
&& code1
== NE_EXPR
)
1855 if (code2
== NE_EXPR
)
1856 return !value_sat_pred_p (expr2
.pred_rhs
, expr1
.pred_rhs
, code1
);
1858 if (code1
== EQ_EXPR
)
1859 return value_sat_pred_p (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
);
1862 return value_sat_pred_p (expr1
.pred_rhs
, expr2
.pred_rhs
, code2
,
1863 code1
== BIT_AND_EXPR
);
1868 /* Returns true if the domain of PRED1 is a subset
1869 of that of PRED2. Returns false if it cannot be proved so. */
1872 is_pred_chain_subset_of (pred_chain pred1
, pred_chain pred2
)
1874 size_t np1
, np2
, i1
, i2
;
1876 np1
= pred1
.length ();
1877 np2
= pred2
.length ();
1879 for (i2
= 0; i2
< np2
; i2
++)
1882 pred_info info2
= pred2
[i2
];
1883 for (i1
= 0; i1
< np1
; i1
++)
1885 pred_info info1
= pred1
[i1
];
1886 if (is_pred_expr_subset_of (info1
, info2
))
1898 /* Returns true if the domain defined by
1899 one pred chain ONE_PRED is a subset of the domain
1900 of *PREDS. It returns false if ONE_PRED's domain is
1901 not a subset of any of the sub-domains of PREDS
1902 (corresponding to each individual chains in it), even
1903 though it may be still be a subset of whole domain
1904 of PREDS which is the union (ORed) of all its subdomains.
1905 In other words, the result is conservative. */
1908 is_included_in (pred_chain one_pred
, pred_chain_union preds
)
1911 size_t n
= preds
.length ();
1913 for (i
= 0; i
< n
; i
++)
1915 if (is_pred_chain_subset_of (one_pred
, preds
[i
]))
1922 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1923 true if the domain defined by PREDS1 is a superset
1924 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1925 PREDS2 respectively. The implementation chooses not to build
1926 generic trees (and relying on the folding capability of the
1927 compiler), but instead performs brute force comparison of
1928 individual predicate chains (won't be a compile time problem
1929 as the chains are pretty short). When the function returns
1930 false, it does not necessarily mean *PREDS1 is not a superset
1931 of *PREDS2, but mean it may not be so since the analysis cannot
1932 prove it. In such cases, false warnings may still be
1936 is_superset_of (pred_chain_union preds1
, pred_chain_union preds2
)
1939 pred_chain one_pred_chain
= vNULL
;
1941 n2
= preds2
.length ();
1943 for (i
= 0; i
< n2
; i
++)
1945 one_pred_chain
= preds2
[i
];
1946 if (!is_included_in (one_pred_chain
, preds1
))
1953 /* Returns true if X1 is the negate of X2. */
1956 pred_neg_p (pred_info x1
, pred_info x2
)
1958 enum tree_code c1
, c2
;
1959 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
1960 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
1964 if (x1
.invert
== x2
.invert
)
1965 c2
= invert_tree_comparison (x2
.cond_code
, false);
1972 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1973 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1974 3) X OR (!X AND Y) is equivalent to (X OR Y);
1975 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1977 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1980 PREDS is the predicate chains, and N is the number of chains. */
1982 /* Helper function to implement rule 1 above. ONE_CHAIN is
1983 the AND predication to be simplified. */
1986 simplify_pred (pred_chain
*one_chain
)
1989 bool simplified
= false;
1990 pred_chain s_chain
= vNULL
;
1992 n
= one_chain
->length ();
1994 for (i
= 0; i
< n
; i
++)
1996 pred_info
*a_pred
= &(*one_chain
)[i
];
1998 if (!a_pred
->pred_lhs
)
2000 if (!is_neq_zero_form_p (*a_pred
))
2003 gimple
*def_stmt
= SSA_NAME_DEF_STMT (a_pred
->pred_lhs
);
2004 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2006 if (gimple_assign_rhs_code (def_stmt
) == BIT_IOR_EXPR
)
2008 for (j
= 0; j
< n
; j
++)
2010 pred_info
*b_pred
= &(*one_chain
)[j
];
2012 if (!b_pred
->pred_lhs
)
2014 if (!is_neq_zero_form_p (*b_pred
))
2017 if (pred_expr_equal_p (*b_pred
, gimple_assign_rhs1 (def_stmt
))
2018 || pred_expr_equal_p (*b_pred
, gimple_assign_rhs2 (def_stmt
)))
2020 /* Mark a_pred for removal. */
2021 a_pred
->pred_lhs
= NULL
;
2022 a_pred
->pred_rhs
= NULL
;
2033 for (i
= 0; i
< n
; i
++)
2035 pred_info
*a_pred
= &(*one_chain
)[i
];
2036 if (!a_pred
->pred_lhs
)
2038 s_chain
.safe_push (*a_pred
);
2041 one_chain
->release ();
2042 *one_chain
= s_chain
;
2045 /* The helper function implements the rule 2 for the
2048 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
2051 simplify_preds_2 (pred_chain_union
*preds
)
2054 bool simplified
= false;
2055 pred_chain_union s_preds
= vNULL
;
2057 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
2058 (X AND Y) OR (X AND !Y) is equivalent to X. */
2060 n
= preds
->length ();
2061 for (i
= 0; i
< n
; i
++)
2064 pred_chain
*a_chain
= &(*preds
)[i
];
2066 if (a_chain
->length () != 2)
2072 for (j
= 0; j
< n
; j
++)
2074 pred_chain
*b_chain
;
2080 b_chain
= &(*preds
)[j
];
2081 if (b_chain
->length () != 2)
2087 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
2090 a_chain
->release ();
2091 b_chain
->release ();
2092 b_chain
->safe_push (x
);
2096 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
2099 a_chain
->release ();
2100 b_chain
->release ();
2101 b_chain
->safe_push (y
);
2107 /* Now clean up the chain. */
2110 for (i
= 0; i
< n
; i
++)
2112 if ((*preds
)[i
].is_empty ())
2114 s_preds
.safe_push ((*preds
)[i
]);
2124 /* The helper function implements the rule 2 for the
2127 3) x OR (!x AND y) is equivalent to x OR y. */
2130 simplify_preds_3 (pred_chain_union
*preds
)
2133 bool simplified
= false;
2135 /* Now iteratively simplify X OR (!X AND Z ..)
2136 into X OR (Z ...). */
2138 n
= preds
->length ();
2142 for (i
= 0; i
< n
; i
++)
2145 pred_chain
*a_chain
= &(*preds
)[i
];
2147 if (a_chain
->length () != 1)
2152 for (j
= 0; j
< n
; j
++)
2154 pred_chain
*b_chain
;
2161 b_chain
= &(*preds
)[j
];
2162 if (b_chain
->length () < 2)
2165 for (k
= 0; k
< b_chain
->length (); k
++)
2168 if (pred_neg_p (x
, x2
))
2170 b_chain
->unordered_remove (k
);
2180 /* The helper function implements the rule 4 for the
2183 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
2184 (x != 0 ANd y != 0). */
2187 simplify_preds_4 (pred_chain_union
*preds
)
2190 bool simplified
= false;
2191 pred_chain_union s_preds
= vNULL
;
2194 n
= preds
->length ();
2195 for (i
= 0; i
< n
; i
++)
2198 pred_chain
*a_chain
= &(*preds
)[i
];
2200 if (a_chain
->length () != 1)
2205 if (!is_neq_zero_form_p (z
))
2208 def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
2209 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2212 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
2215 for (j
= 0; j
< n
; j
++)
2217 pred_chain
*b_chain
;
2223 b_chain
= &(*preds
)[j
];
2224 if (b_chain
->length () != 2)
2229 if (!is_neq_zero_form_p (x2
) || !is_neq_zero_form_p (y2
))
2232 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
2233 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
2234 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
2235 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
2238 a_chain
->release ();
2244 /* Now clean up the chain. */
2247 for (i
= 0; i
< n
; i
++)
2249 if ((*preds
)[i
].is_empty ())
2251 s_preds
.safe_push ((*preds
)[i
]);
2262 /* This function simplifies predicates in PREDS. */
2265 simplify_preds (pred_chain_union
*preds
, gimple
*use_or_def
, bool is_use
)
2268 bool changed
= false;
2270 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2272 fprintf (dump_file
, "[BEFORE SIMPLICATION -- ");
2273 dump_predicates (use_or_def
, *preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2276 for (i
= 0; i
< preds
->length (); i
++)
2277 simplify_pred (&(*preds
)[i
]);
2279 n
= preds
->length ();
2286 if (simplify_preds_2 (preds
))
2289 /* Now iteratively simplify X OR (!X AND Z ..)
2290 into X OR (Z ...). */
2291 if (simplify_preds_3 (preds
))
2294 if (simplify_preds_4 (preds
))
2302 /* This is a helper function which attempts to normalize predicate chains
2303 by following UD chains. It basically builds up a big tree of either IOR
2304 operations or AND operations, and convert the IOR tree into a
2305 pred_chain_union or BIT_AND tree into a pred_chain.
2315 then _t != 0 will be normalized into a pred_chain_union
2317 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
2327 then _t != 0 will be normalized into a pred_chain:
2328 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
2332 /* This is a helper function that stores a PRED into NORM_PREDS. */
2335 push_pred (pred_chain_union
*norm_preds
, pred_info pred
)
2337 pred_chain pred_chain
= vNULL
;
2338 pred_chain
.safe_push (pred
);
2339 norm_preds
->safe_push (pred_chain
);
2342 /* A helper function that creates a predicate of the form
2343 OP != 0 and push it WORK_LIST. */
2346 push_to_worklist (tree op
, vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
2347 hash_set
<tree
> *mark_set
)
2349 if (mark_set
->contains (op
))
2354 arg_pred
.pred_lhs
= op
;
2355 arg_pred
.pred_rhs
= integer_zero_node
;
2356 arg_pred
.cond_code
= NE_EXPR
;
2357 arg_pred
.invert
= false;
2358 work_list
->safe_push (arg_pred
);
2361 /* A helper that generates a pred_info from a gimple assignment
2362 CMP_ASSIGN with comparison rhs. */
2365 get_pred_info_from_cmp (gimple
*cmp_assign
)
2368 n_pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
2369 n_pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
2370 n_pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
2371 n_pred
.invert
= false;
2375 /* Returns true if the PHI is a degenerated phi with
2376 all args with the same value (relop). In that case, *PRED
2377 will be updated to that value. */
2380 is_degenerated_phi (gimple
*phi
, pred_info
*pred_p
)
2387 n
= gimple_phi_num_args (phi
);
2388 op0
= gimple_phi_arg_def (phi
, 0);
2390 if (TREE_CODE (op0
) != SSA_NAME
)
2393 def0
= SSA_NAME_DEF_STMT (op0
);
2394 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
2396 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
)) != tcc_comparison
)
2398 pred0
= get_pred_info_from_cmp (def0
);
2400 for (i
= 1; i
< n
; ++i
)
2404 tree op
= gimple_phi_arg_def (phi
, i
);
2406 if (TREE_CODE (op
) != SSA_NAME
)
2409 def
= SSA_NAME_DEF_STMT (op
);
2410 if (gimple_code (def
) != GIMPLE_ASSIGN
)
2412 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) != tcc_comparison
)
2414 pred
= get_pred_info_from_cmp (def
);
2415 if (!pred_equal_p (pred
, pred0
))
2423 /* Normalize one predicate PRED
2424 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2425 2) otherwise if PRED is of the form x != 0, follow x's definition
2426 and put normalized predicates into WORK_LIST. */
2429 normalize_one_pred_1 (pred_chain_union
*norm_preds
,
2430 pred_chain
*norm_chain
,
2432 enum tree_code and_or_code
,
2433 vec
<pred_info
, va_heap
, vl_ptr
> *work_list
,
2434 hash_set
<tree
> *mark_set
)
2436 if (!is_neq_zero_form_p (pred
))
2438 if (and_or_code
== BIT_IOR_EXPR
)
2439 push_pred (norm_preds
, pred
);
2441 norm_chain
->safe_push (pred
);
2445 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2447 if (gimple_code (def_stmt
) == GIMPLE_PHI
2448 && is_degenerated_phi (def_stmt
, &pred
))
2449 work_list
->safe_push (pred
);
2450 else if (gimple_code (def_stmt
) == GIMPLE_PHI
&& and_or_code
== BIT_IOR_EXPR
)
2453 n
= gimple_phi_num_args (def_stmt
);
2455 /* If we see non zero constant, we should punt. The predicate
2456 * should be one guarding the phi edge. */
2457 for (i
= 0; i
< n
; ++i
)
2459 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2460 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
2462 push_pred (norm_preds
, pred
);
2467 for (i
= 0; i
< n
; ++i
)
2469 tree op
= gimple_phi_arg_def (def_stmt
, i
);
2470 if (integer_zerop (op
))
2473 push_to_worklist (op
, work_list
, mark_set
);
2476 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
2478 if (and_or_code
== BIT_IOR_EXPR
)
2479 push_pred (norm_preds
, pred
);
2481 norm_chain
->safe_push (pred
);
2483 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
2485 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2486 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2488 /* But treat x & 3 as condition. */
2489 if (and_or_code
== BIT_AND_EXPR
)
2492 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2493 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2494 n_pred
.cond_code
= and_or_code
;
2495 n_pred
.invert
= false;
2496 norm_chain
->safe_push (n_pred
);
2501 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2502 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2505 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2508 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2509 if (and_or_code
== BIT_IOR_EXPR
)
2510 push_pred (norm_preds
, n_pred
);
2512 norm_chain
->safe_push (n_pred
);
2516 if (and_or_code
== BIT_IOR_EXPR
)
2517 push_pred (norm_preds
, pred
);
2519 norm_chain
->safe_push (pred
);
2523 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2526 normalize_one_pred (pred_chain_union
*norm_preds
, pred_info pred
)
2528 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2529 enum tree_code and_or_code
= ERROR_MARK
;
2530 pred_chain norm_chain
= vNULL
;
2532 if (!is_neq_zero_form_p (pred
))
2534 push_pred (norm_preds
, pred
);
2538 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2539 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2540 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2541 if (and_or_code
!= BIT_IOR_EXPR
&& and_or_code
!= BIT_AND_EXPR
)
2543 if (TREE_CODE_CLASS (and_or_code
) == tcc_comparison
)
2545 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2546 push_pred (norm_preds
, n_pred
);
2549 push_pred (norm_preds
, pred
);
2553 work_list
.safe_push (pred
);
2554 hash_set
<tree
> mark_set
;
2556 while (!work_list
.is_empty ())
2558 pred_info a_pred
= work_list
.pop ();
2559 normalize_one_pred_1 (norm_preds
, &norm_chain
, a_pred
, and_or_code
,
2560 &work_list
, &mark_set
);
2562 if (and_or_code
== BIT_AND_EXPR
)
2563 norm_preds
->safe_push (norm_chain
);
2565 work_list
.release ();
2569 normalize_one_pred_chain (pred_chain_union
*norm_preds
, pred_chain one_chain
)
2571 vec
<pred_info
, va_heap
, vl_ptr
> work_list
= vNULL
;
2572 hash_set
<tree
> mark_set
;
2573 pred_chain norm_chain
= vNULL
;
2576 for (i
= 0; i
< one_chain
.length (); i
++)
2578 work_list
.safe_push (one_chain
[i
]);
2579 mark_set
.add (one_chain
[i
].pred_lhs
);
2582 while (!work_list
.is_empty ())
2584 pred_info a_pred
= work_list
.pop ();
2585 normalize_one_pred_1 (0, &norm_chain
, a_pred
, BIT_AND_EXPR
, &work_list
,
2589 norm_preds
->safe_push (norm_chain
);
2590 work_list
.release ();
2593 /* Normalize predicate chains PREDS and returns the normalized one. */
2595 static pred_chain_union
2596 normalize_preds (pred_chain_union preds
, gimple
*use_or_def
, bool is_use
)
2598 pred_chain_union norm_preds
= vNULL
;
2599 size_t n
= preds
.length ();
2602 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2604 fprintf (dump_file
, "[BEFORE NORMALIZATION --");
2605 dump_predicates (use_or_def
, preds
, is_use
? "[USE]:\n" : "[DEF]:\n");
2608 for (i
= 0; i
< n
; i
++)
2610 if (preds
[i
].length () != 1)
2611 normalize_one_pred_chain (&norm_preds
, preds
[i
]);
2614 normalize_one_pred (&norm_preds
, preds
[i
][0]);
2615 preds
[i
].release ();
2621 fprintf (dump_file
, "[AFTER NORMALIZATION -- ");
2622 dump_predicates (use_or_def
, norm_preds
,
2623 is_use
? "[USE]:\n" : "[DEF]:\n");
2626 destroy_predicate_vecs (&preds
);
2630 /* Return TRUE if PREDICATE can be invalidated by any individual
2631 predicate in USE_GUARD. */
2634 can_one_predicate_be_invalidated_p (pred_info predicate
,
2635 pred_chain use_guard
)
2637 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2639 fprintf (dump_file
, "Testing if this predicate: ");
2640 dump_pred_info (predicate
);
2641 fprintf (dump_file
, "\n...can be invalidated by a USE guard of: ");
2642 dump_pred_chain (use_guard
);
2644 for (size_t i
= 0; i
< use_guard
.length (); ++i
)
2646 /* NOTE: This is a very simple check, and only understands an
2647 exact opposite. So, [i == 0] is currently only invalidated
2648 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2649 invalidate with say [i > 5] or [i == 8]. There is certainly
2650 room for improvement here. */
2651 if (pred_neg_p (predicate
, use_guard
[i
]))
2653 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2655 fprintf (dump_file
, " Predicate was invalidated by: ");
2656 dump_pred_info (use_guard
[i
]);
2657 fputc ('\n', dump_file
);
2665 /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2666 USE_GUARD being true. */
2669 can_chain_union_be_invalidated_p (pred_chain_union uninit_pred
,
2670 pred_chain use_guard
)
2672 if (uninit_pred
.is_empty ())
2674 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2675 dump_predicates (NULL
, uninit_pred
,
2676 "Testing if anything here can be invalidated: ");
2677 for (size_t i
= 0; i
< uninit_pred
.length (); ++i
)
2679 pred_chain c
= uninit_pred
[i
];
2681 for (j
= 0; j
< c
.length (); ++j
)
2682 if (can_one_predicate_be_invalidated_p (c
[j
], use_guard
))
2685 /* If we were unable to invalidate any predicate in C, then there
2686 is a viable path from entry to the PHI where the PHI takes
2687 an uninitialized value and continues to a use of the PHI. */
2688 if (j
== c
.length ())
2694 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2695 can actually happen if we arrived at a use for PHI.
2697 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2700 uninit_uses_cannot_happen (gphi
*phi
, unsigned uninit_opnds
,
2701 pred_chain_union phi_use_guards
)
2703 unsigned phi_args
= gimple_phi_num_args (phi
);
2704 if (phi_args
> max_phi_args
)
2707 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2708 possible guard, there's no way of knowing which guard was true.
2709 Since we need to be absolutely sure that the uninitialized
2710 operands will be invalidated, bail. */
2711 if (phi_use_guards
.length () != 1)
2714 /* Look for the control dependencies of all the uninitialized
2715 operands and build guard predicates describing them. */
2716 pred_chain_union uninit_preds
;
2718 for (unsigned i
= 0; i
< phi_args
; ++i
)
2720 if (!MASK_TEST_BIT (uninit_opnds
, i
))
2723 edge e
= gimple_phi_arg_edge (phi
, i
);
2724 vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
2725 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
2726 size_t num_chains
= 0;
2729 /* Build the control dependency chain for uninit operand `i'... */
2730 uninit_preds
= vNULL
;
2731 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun
),
2732 e
->src
, dep_chains
, &num_chains
,
2733 &cur_chain
, &num_calls
))
2738 /* ...and convert it into a set of predicates. */
2739 bool has_valid_preds
2740 = convert_control_dep_chain_into_preds (dep_chains
, num_chains
,
2742 for (size_t j
= 0; j
< num_chains
; ++j
)
2743 dep_chains
[j
].release ();
2744 if (!has_valid_preds
)
2749 simplify_preds (&uninit_preds
, NULL
, false);
2750 uninit_preds
= normalize_preds (uninit_preds
, NULL
, false);
2752 /* Can the guard for this uninitialized operand be invalidated
2754 if (!can_chain_union_be_invalidated_p (uninit_preds
, phi_use_guards
[0]))
2760 destroy_predicate_vecs (&uninit_preds
);
2764 /* Computes the predicates that guard the use and checks
2765 if the incoming paths that have empty (or possibly
2766 empty) definition can be pruned/filtered. The function returns
2767 true if it can be determined that the use of PHI's def in
2768 USE_STMT is guarded with a predicate set not overlapping with
2769 predicate sets of all runtime paths that do not have a definition.
2771 Returns false if it is not or it cannot be determined. USE_BB is
2772 the bb of the use (for phi operand use, the bb is not the bb of
2773 the phi stmt, but the src bb of the operand edge).
2775 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2776 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2777 set of phis being visited.
2779 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2780 If *DEF_PREDS is the empty vector, the defining predicate chains of
2781 PHI will be computed and stored into *DEF_PREDS as needed.
2783 VISITED_PHIS is a pointer set of phis being visited. */
2786 is_use_properly_guarded (gimple
*use_stmt
,
2789 unsigned uninit_opnds
,
2790 pred_chain_union
*def_preds
,
2791 hash_set
<gphi
*> *visited_phis
)
2794 pred_chain_union preds
= vNULL
;
2795 bool has_valid_preds
= false;
2796 bool is_properly_guarded
= false;
2798 if (visited_phis
->add (phi
))
2801 phi_bb
= gimple_bb (phi
);
2803 if (is_non_loop_exit_postdominating (use_bb
, phi_bb
))
2806 has_valid_preds
= find_predicates (&preds
, phi_bb
, use_bb
);
2808 if (!has_valid_preds
)
2810 destroy_predicate_vecs (&preds
);
2814 /* Try to prune the dead incoming phi edges. */
2816 = use_pred_not_overlap_with_undef_path_pred (preds
, phi
, uninit_opnds
,
2819 /* We might be able to prove that if the control dependencies
2820 for UNINIT_OPNDS are true, that the control dependencies for
2821 USE_STMT can never be true. */
2822 if (!is_properly_guarded
)
2823 is_properly_guarded
|= uninit_uses_cannot_happen (phi
, uninit_opnds
,
2826 if (is_properly_guarded
)
2828 destroy_predicate_vecs (&preds
);
2832 if (def_preds
->is_empty ())
2834 has_valid_preds
= find_def_preds (def_preds
, phi
);
2836 if (!has_valid_preds
)
2838 destroy_predicate_vecs (&preds
);
2842 simplify_preds (def_preds
, phi
, false);
2843 *def_preds
= normalize_preds (*def_preds
, phi
, false);
2846 simplify_preds (&preds
, use_stmt
, true);
2847 preds
= normalize_preds (preds
, use_stmt
, true);
2849 is_properly_guarded
= is_superset_of (*def_preds
, preds
);
2851 destroy_predicate_vecs (&preds
);
2852 return is_properly_guarded
;
2855 /* Searches through all uses of a potentially
2856 uninitialized variable defined by PHI and returns a use
2857 statement if the use is not properly guarded. It returns
2858 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2859 holding the position(s) of uninit PHI operands. WORKLIST
2860 is the vector of candidate phis that may be updated by this
2861 function. ADDED_TO_WORKLIST is the pointer set tracking
2862 if the new phi is already in the worklist. */
2865 find_uninit_use (gphi
*phi
, unsigned uninit_opnds
,
2866 vec
<gphi
*> *worklist
,
2867 hash_set
<gphi
*> *added_to_worklist
)
2870 use_operand_p use_p
;
2872 imm_use_iterator iter
;
2873 pred_chain_union def_preds
= vNULL
;
2876 phi_result
= gimple_phi_result (phi
);
2878 FOR_EACH_IMM_USE_FAST (use_p
, iter
, phi_result
)
2882 use_stmt
= USE_STMT (use_p
);
2883 if (is_gimple_debug (use_stmt
))
2886 if (gphi
*use_phi
= dyn_cast
<gphi
*> (use_stmt
))
2887 use_bb
= gimple_phi_arg_edge (use_phi
,
2888 PHI_ARG_INDEX_FROM_USE (use_p
))->src
;
2890 use_bb
= gimple_bb (use_stmt
);
2892 hash_set
<gphi
*> visited_phis
;
2893 if (is_use_properly_guarded (use_stmt
, use_bb
, phi
, uninit_opnds
,
2894 &def_preds
, &visited_phis
))
2897 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2899 fprintf (dump_file
, "[CHECK]: Found unguarded use: ");
2900 print_gimple_stmt (dump_file
, use_stmt
, 0);
2902 /* Found one real use, return. */
2903 if (gimple_code (use_stmt
) != GIMPLE_PHI
)
2909 /* Found a phi use that is not guarded,
2910 add the phi to the worklist. */
2911 if (!added_to_worklist
->add (as_a
<gphi
*> (use_stmt
)))
2913 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2915 fprintf (dump_file
, "[WORKLIST]: Update worklist with phi: ");
2916 print_gimple_stmt (dump_file
, use_stmt
, 0);
2919 worklist
->safe_push (as_a
<gphi
*> (use_stmt
));
2920 possibly_undefined_names
->add (phi_result
);
2924 destroy_predicate_vecs (&def_preds
);
2928 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2929 and gives warning if there exists a runtime path from the entry to a
2930 use of the PHI def that does not contain a definition. In other words,
2931 the warning is on the real use. The more dead paths that can be pruned
2932 by the compiler, the fewer false positives the warning is. WORKLIST
2933 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2934 a pointer set tracking if the new phi is added to the worklist or not. */
2937 warn_uninitialized_phi (gphi
*phi
, vec
<gphi
*> *worklist
,
2938 hash_set
<gphi
*> *added_to_worklist
)
2940 unsigned uninit_opnds
;
2941 gimple
*uninit_use_stmt
= 0;
2946 /* Don't look at virtual operands. */
2947 if (virtual_operand_p (gimple_phi_result (phi
)))
2950 uninit_opnds
= compute_uninit_opnds_pos (phi
);
2952 if (MASK_EMPTY (uninit_opnds
))
2955 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2957 fprintf (dump_file
, "[CHECK]: examining phi: ");
2958 print_gimple_stmt (dump_file
, phi
, 0);
2961 /* Now check if we have any use of the value without proper guard. */
2962 uninit_use_stmt
= find_uninit_use (phi
, uninit_opnds
,
2963 worklist
, added_to_worklist
);
2965 /* All uses are properly guarded. */
2966 if (!uninit_use_stmt
)
2969 phiarg_index
= MASK_FIRST_SET_BIT (uninit_opnds
);
2970 uninit_op
= gimple_phi_arg_def (phi
, phiarg_index
);
2971 if (SSA_NAME_VAR (uninit_op
) == NULL_TREE
)
2973 if (gimple_phi_arg_has_location (phi
, phiarg_index
))
2974 loc
= gimple_phi_arg_location (phi
, phiarg_index
);
2976 loc
= UNKNOWN_LOCATION
;
2977 warn_uninit (OPT_Wmaybe_uninitialized
, uninit_op
, SSA_NAME_VAR (uninit_op
),
2978 SSA_NAME_VAR (uninit_op
),
2979 "%qD may be used uninitialized in this function",
2980 uninit_use_stmt
, loc
);
2984 gate_warn_uninitialized (void)
2986 return warn_uninitialized
|| warn_maybe_uninitialized
;
2991 const pass_data pass_data_late_warn_uninitialized
=
2993 GIMPLE_PASS
, /* type */
2994 "uninit", /* name */
2995 OPTGROUP_NONE
, /* optinfo_flags */
2996 TV_NONE
, /* tv_id */
2997 PROP_ssa
, /* properties_required */
2998 0, /* properties_provided */
2999 0, /* properties_destroyed */
3000 0, /* todo_flags_start */
3001 0, /* todo_flags_finish */
3004 class pass_late_warn_uninitialized
: public gimple_opt_pass
3007 pass_late_warn_uninitialized (gcc::context
*ctxt
)
3008 : gimple_opt_pass (pass_data_late_warn_uninitialized
, ctxt
)
3011 /* opt_pass methods: */
3012 opt_pass
*clone () { return new pass_late_warn_uninitialized (m_ctxt
); }
3013 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
3014 virtual unsigned int execute (function
*);
3016 }; // class pass_late_warn_uninitialized
3019 pass_late_warn_uninitialized::execute (function
*fun
)
3023 vec
<gphi
*> worklist
= vNULL
;
3025 calculate_dominance_info (CDI_DOMINATORS
);
3026 calculate_dominance_info (CDI_POST_DOMINATORS
);
3027 /* Re-do the plain uninitialized variable check, as optimization may have
3028 straightened control flow. Do this first so that we don't accidentally
3029 get a "may be" warning when we'd have seen an "is" warning later. */
3030 warn_uninitialized_vars (/*warn_maybe_uninitialized=*/1);
3032 timevar_push (TV_TREE_UNINIT
);
3034 possibly_undefined_names
= new hash_set
<tree
>;
3035 hash_set
<gphi
*> added_to_worklist
;
3037 /* Initialize worklist */
3038 FOR_EACH_BB_FN (bb
, fun
)
3039 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3041 gphi
*phi
= gsi
.phi ();
3044 n
= gimple_phi_num_args (phi
);
3046 /* Don't look at virtual operands. */
3047 if (virtual_operand_p (gimple_phi_result (phi
)))
3050 for (i
= 0; i
< n
; ++i
)
3052 tree op
= gimple_phi_arg_def (phi
, i
);
3053 if (TREE_CODE (op
) == SSA_NAME
&& uninit_undefined_value_p (op
))
3055 worklist
.safe_push (phi
);
3056 added_to_worklist
.add (phi
);
3057 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3059 fprintf (dump_file
, "[WORKLIST]: add to initial list: ");
3060 print_gimple_stmt (dump_file
, phi
, 0);
3067 while (worklist
.length () != 0)
3070 cur_phi
= worklist
.pop ();
3071 warn_uninitialized_phi (cur_phi
, &worklist
, &added_to_worklist
);
3074 worklist
.release ();
3075 delete possibly_undefined_names
;
3076 possibly_undefined_names
= NULL
;
3077 free_dominance_info (CDI_POST_DOMINATORS
);
3078 timevar_pop (TV_TREE_UNINIT
);
3085 make_pass_late_warn_uninitialized (gcc::context
*ctxt
)
3087 return new pass_late_warn_uninitialized (ctxt
);
3091 execute_early_warn_uninitialized (void)
3093 /* Currently, this pass runs always but
3094 execute_late_warn_uninitialized only runs with optimization. With
3095 optimization we want to warn about possible uninitialized as late
3096 as possible, thus don't do it here. However, without
3097 optimization we need to warn here about "may be uninitialized". */
3098 calculate_dominance_info (CDI_POST_DOMINATORS
);
3100 warn_uninitialized_vars (/*warn_maybe_uninitialized=*/!optimize
);
3102 /* Post-dominator information cannot be reliably updated. Free it
3105 free_dominance_info (CDI_POST_DOMINATORS
);
3111 const pass_data pass_data_early_warn_uninitialized
=
3113 GIMPLE_PASS
, /* type */
3114 "*early_warn_uninitialized", /* name */
3115 OPTGROUP_NONE
, /* optinfo_flags */
3116 TV_TREE_UNINIT
, /* tv_id */
3117 PROP_ssa
, /* properties_required */
3118 0, /* properties_provided */
3119 0, /* properties_destroyed */
3120 0, /* todo_flags_start */
3121 0, /* todo_flags_finish */
3124 class pass_early_warn_uninitialized
: public gimple_opt_pass
3127 pass_early_warn_uninitialized (gcc::context
*ctxt
)
3128 : gimple_opt_pass (pass_data_early_warn_uninitialized
, ctxt
)
3131 /* opt_pass methods: */
3132 virtual bool gate (function
*) { return gate_warn_uninitialized (); }
3133 virtual unsigned int execute (function
*)
3135 return execute_early_warn_uninitialized ();
3138 }; // class pass_early_warn_uninitialized
3143 make_pass_early_warn_uninitialized (gcc::context
*ctxt
)
3145 return new pass_early_warn_uninitialized (ctxt
);