Don't warn when alignment of global common data exceeds maximum alignment.
[official-gcc.git] / gcc / tree-ssa-uninit.c
blobad2cf48819b3abbca9f0d925e98ad4d90c9b666f
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)
10 any later version.
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
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "tree.h"
27 #include "gimple.h"
28 #include "tree-pass.h"
29 #include "ssa.h"
30 #include "gimple-pretty-print.h"
31 #include "diagnostic-core.h"
32 #include "fold-const.h"
33 #include "gimple-iterator.h"
34 #include "tree-ssa.h"
35 #include "tree-cfg.h"
36 #include "cfghooks.h"
37 #include "attribs.h"
38 #include "builtins.h"
39 #include "calls.h"
40 #include "gimple-range.h"
42 /* This implements the pass that does predicate aware warning on uses of
43 possibly uninitialized variables. The pass first collects the set of
44 possibly uninitialized SSA names. For each such name, it walks through
45 all its immediate uses. For each immediate use, it rebuilds the condition
46 expression (the predicate) that guards the use. The predicate is then
47 examined to see if the variable is always defined under that same condition.
48 This is done either by pruning the unrealizable paths that lead to the
49 default definitions or by checking if the predicate set that guards the
50 defining paths is a superset of the use predicate. */
52 /* Max PHI args we can handle in pass. */
53 const unsigned max_phi_args = 32;
55 /* Pointer set of potentially undefined ssa names, i.e.,
56 ssa names that are defined by phi with operands that
57 are not defined or potentially undefined. */
58 static hash_set<tree> *possibly_undefined_names = 0;
60 /* Bit mask handling macros. */
61 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
62 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
63 #define MASK_EMPTY(mask) (mask == 0)
65 /* Returns the first bit position (starting from LSB)
66 in mask that is non zero. Returns -1 if the mask is empty. */
67 static int
68 get_mask_first_set_bit (unsigned mask)
70 int pos = 0;
71 if (mask == 0)
72 return -1;
74 while ((mask & (1 << pos)) == 0)
75 pos++;
77 return pos;
79 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
81 /* Return true if T, an SSA_NAME, has an undefined value. */
82 static bool
83 has_undefined_value_p (tree t)
85 return (ssa_undefined_value_p (t)
86 || (possibly_undefined_names
87 && possibly_undefined_names->contains (t)));
90 /* Return true if EXPR should suppress either uninitialized warning. */
92 static inline bool
93 get_no_uninit_warning (tree expr)
95 return warning_suppressed_p (expr, OPT_Wuninitialized);
98 /* Suppress both uninitialized warnings for EXPR. */
100 static inline void
101 set_no_uninit_warning (tree expr)
103 suppress_warning (expr, OPT_Wuninitialized);
106 /* Like has_undefined_value_p, but don't return true if the no-warning
107 bit is set on SSA_NAME_VAR for either uninit warning. */
109 static inline bool
110 uninit_undefined_value_p (tree t)
112 if (!has_undefined_value_p (t))
113 return false;
114 if (!SSA_NAME_VAR (t))
115 return true;
116 return !get_no_uninit_warning (SSA_NAME_VAR (t));
119 /* Emit warnings for uninitialized variables. This is done in two passes.
121 The first pass notices real uses of SSA names with undefined values.
122 Such uses are unconditionally uninitialized, and we can be certain that
123 such a use is a mistake. This pass is run before most optimizations,
124 so that we catch as many as we can.
126 The second pass follows PHI nodes to find uses that are potentially
127 uninitialized. In this case we can't necessarily prove that the use
128 is really uninitialized. This pass is run after most optimizations,
129 so that we thread as many jumps and possible, and delete as much dead
130 code as possible, in order to reduce false positives. We also look
131 again for plain uninitialized variables, since optimization may have
132 changed conditionally uninitialized to unconditionally uninitialized. */
134 /* Emit a warning for EXPR based on variable VAR at the point in the
135 program T, an SSA_NAME, is used being uninitialized. The exact
136 warning text is in MSGID and DATA is the gimple stmt with info about
137 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
138 gives which argument of the phi node to take the location from. WC
139 is the warning code. */
141 static void
142 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
143 const char *gmsgid, void *data, location_t phiarg_loc)
145 gimple *context = (gimple *) data;
146 location_t location, cfun_loc;
147 expanded_location xloc, floc;
149 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
150 turns in a COMPLEX_EXPR with the not initialized part being
151 set to its previous (undefined) value. */
152 if (is_gimple_assign (context)
153 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
154 return;
155 if (!has_undefined_value_p (t))
156 return;
158 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
159 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
160 created for conversion from scalar to complex. Use the underlying var of
161 the COMPLEX_EXPRs real part in that case. See PR71581. */
162 if (expr == NULL_TREE
163 && var == NULL_TREE
164 && SSA_NAME_VAR (t) == NULL_TREE
165 && is_gimple_assign (SSA_NAME_DEF_STMT (t))
166 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t)) == COMPLEX_EXPR)
168 tree v = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
169 if (TREE_CODE (v) == SSA_NAME
170 && has_undefined_value_p (v)
171 && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t))))
173 expr = SSA_NAME_VAR (v);
174 var = expr;
178 if (expr == NULL_TREE)
179 return;
181 /* TREE_NO_WARNING either means we already warned, or the front end
182 wishes to suppress the warning. */
183 if ((context
184 && (warning_suppressed_p (context, OPT_Wuninitialized)
185 || (gimple_assign_single_p (context)
186 && get_no_uninit_warning (gimple_assign_rhs1 (context)))))
187 || get_no_uninit_warning (expr))
188 return;
190 if (context != NULL && gimple_has_location (context))
191 location = gimple_location (context);
192 else if (phiarg_loc != UNKNOWN_LOCATION)
193 location = phiarg_loc;
194 else
195 location = DECL_SOURCE_LOCATION (var);
196 location = linemap_resolve_location (line_table, location,
197 LRK_SPELLING_LOCATION, NULL);
198 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
199 xloc = expand_location (location);
200 floc = expand_location (cfun_loc);
201 auto_diagnostic_group d;
202 if (warning_at (location, wc, gmsgid, expr))
204 suppress_warning (expr, wc);
206 if (location == DECL_SOURCE_LOCATION (var))
207 return;
208 if (xloc.file != floc.file
209 || linemap_location_before_p (line_table, location, cfun_loc)
210 || linemap_location_before_p (line_table, cfun->function_end_locus,
211 location))
212 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
216 struct check_defs_data
218 /* If we found any may-defs besides must-def clobbers. */
219 bool found_may_defs;
222 /* Return true if STMT is a call to built-in function all of whose
223 by-reference arguments are const-qualified (i.e., the function can
224 be assumed not to modify them). */
226 static bool
227 builtin_call_nomodifying_p (gimple *stmt)
229 if (!gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
230 return false;
232 tree fndecl = gimple_call_fndecl (stmt);
233 if (!fndecl)
234 return false;
236 tree fntype = TREE_TYPE (fndecl);
237 if (!fntype)
238 return false;
240 /* Check the called function's signature for non-constc pointers.
241 If one is found, return false. */
242 unsigned argno = 0;
243 tree argtype;
244 function_args_iterator it;
245 FOREACH_FUNCTION_ARGS (fntype, argtype, it)
247 if (VOID_TYPE_P (argtype))
248 return true;
250 ++argno;
252 if (!POINTER_TYPE_P (argtype))
253 continue;
255 if (TYPE_READONLY (TREE_TYPE (argtype)))
256 continue;
258 return false;
261 /* If the number of actual arguments to the call is less than or
262 equal to the number of parameters, return false. */
263 unsigned nargs = gimple_call_num_args (stmt);
264 if (nargs <= argno)
265 return false;
267 /* Check arguments passed through the ellipsis in calls to variadic
268 functions for pointers. If one is found that's a non-constant
269 pointer, return false. */
270 for (; argno < nargs; ++argno)
272 tree arg = gimple_call_arg (stmt, argno);
273 argtype = TREE_TYPE (arg);
274 if (!POINTER_TYPE_P (argtype))
275 continue;
277 if (TYPE_READONLY (TREE_TYPE (argtype)))
278 continue;
280 return false;
283 return true;
286 /* If ARG is a FNDECL parameter declared with attribute access none or
287 write_only issue a warning for its read access via PTR. */
289 static void
290 maybe_warn_read_write_only (tree fndecl, gimple *stmt, tree arg, tree ptr)
292 if (!fndecl)
293 return;
295 if (get_no_uninit_warning (arg))
296 return;
298 tree fntype = TREE_TYPE (fndecl);
299 if (!fntype)
300 return;
302 /* Initialize a map of attribute access specifications for arguments
303 to the function function call. */
304 rdwr_map rdwr_idx;
305 init_attr_rdwr_indices (&rdwr_idx, TYPE_ATTRIBUTES (fntype));
307 unsigned argno = 0;
308 tree parms = DECL_ARGUMENTS (fndecl);
309 for (tree parm = parms; parm; parm = TREE_CHAIN (parm), ++argno)
311 if (parm != arg)
312 continue;
314 const attr_access* access = rdwr_idx.get (argno);
315 if (!access)
316 break;
318 if (access->mode != access_none
319 && access->mode != access_write_only)
320 continue;
322 location_t stmtloc
323 = linemap_resolve_location (line_table, gimple_location (stmt),
324 LRK_SPELLING_LOCATION, NULL);
326 if (!warning_at (stmtloc, OPT_Wmaybe_uninitialized,
327 "%qE may be used uninitialized", ptr))
328 break;
330 suppress_warning (arg, OPT_Wmaybe_uninitialized);
332 const char* const access_str =
333 TREE_STRING_POINTER (access->to_external_string ());
335 location_t parmloc = DECL_SOURCE_LOCATION (parm);
336 inform (parmloc, "accessing argument %u of a function declared with "
337 "attribute %<%s%>",
338 argno + 1, access_str);
340 break;
344 /* Callback for walk_aliased_vdefs. */
346 static bool
347 check_defs (ao_ref *ref, tree vdef, void *data_)
349 check_defs_data *data = (check_defs_data *)data_;
350 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
352 /* The ASAN_MARK intrinsic doesn't modify the variable. */
353 if (is_gimple_call (def_stmt))
355 if (gimple_call_internal_p (def_stmt)
356 && gimple_call_internal_fn (def_stmt) == IFN_ASAN_MARK)
357 return false;
359 if (tree fndecl = gimple_call_fndecl (def_stmt))
361 /* Some sanitizer calls pass integer arguments to built-ins
362 that expect pointers. Avoid using gimple_call_builtin_p()
363 which fails for such calls. */
364 if (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)
366 built_in_function fncode = DECL_FUNCTION_CODE (fndecl);
367 if (fncode > BEGIN_SANITIZER_BUILTINS
368 && fncode < END_SANITIZER_BUILTINS)
369 return false;
374 /* End of VLA scope is not a kill. */
375 if (gimple_call_builtin_p (def_stmt, BUILT_IN_STACK_RESTORE))
376 return false;
378 /* If this is a clobber then if it is not a kill walk past it. */
379 if (gimple_clobber_p (def_stmt))
381 if (stmt_kills_ref_p (def_stmt, ref))
382 return true;
383 return false;
386 if (builtin_call_nomodifying_p (def_stmt))
387 return false;
389 /* Found a may-def on this path. */
390 data->found_may_defs = true;
391 return true;
394 /* Counters and limits controlling the the depth of analysis and
395 strictness of the warning. */
396 struct wlimits
398 /* Number of VDEFs encountered. */
399 unsigned int vdef_cnt;
400 /* Number of statements examined by walk_aliased_vdefs. */
401 unsigned int oracle_cnt;
402 /* Limit on the number of statements visited by walk_aliased_vdefs. */
403 unsigned limit;
404 /* Set when basic block with statement is executed unconditionally. */
405 bool always_executed;
406 /* Set to issue -Wmaybe-uninitialized. */
407 bool wmaybe_uninit;
410 /* Determine if REF references an uninitialized operand and diagnose
411 it if so. STMS is the referencing statement. LHS is the result
412 of the access and may be null. RHS is the variable referenced by
413 the access; it may not be null. */
415 static tree
416 maybe_warn_operand (ao_ref &ref, gimple *stmt, tree lhs, tree rhs,
417 wlimits &wlims)
419 bool has_bit_insert = false;
420 use_operand_p luse_p;
421 imm_use_iterator liter;
423 if (get_no_uninit_warning (rhs))
424 return NULL_TREE;
426 /* Do not warn if the base was marked so or this is a
427 hard register var. */
428 tree base = ao_ref_base (&ref);
429 if ((VAR_P (base)
430 && DECL_HARD_REGISTER (base))
431 || get_no_uninit_warning (base))
432 return NULL_TREE;
434 /* Do not warn if the access is zero size or if it's fully outside
435 the object. */
436 poly_int64 decl_size;
437 if (known_size_p (ref.size)
438 && known_eq (ref.max_size, ref.size)
439 && (known_eq (ref.size, 0)
440 || known_le (ref.offset + ref.size, 0)))
441 return NULL_TREE;
443 if (DECL_P (base)
444 && known_ge (ref.offset, 0)
445 && DECL_SIZE (base)
446 && poly_int_tree_p (DECL_SIZE (base), &decl_size)
447 && known_le (decl_size, ref.offset))
448 return NULL_TREE;
450 /* Do not warn if the result of the access is then used for
451 a BIT_INSERT_EXPR. */
452 if (lhs && TREE_CODE (lhs) == SSA_NAME)
453 FOR_EACH_IMM_USE_FAST (luse_p, liter, lhs)
455 gimple *use_stmt = USE_STMT (luse_p);
456 /* BIT_INSERT_EXPR first operand should not be considered
457 a use for the purpose of uninit warnings. */
458 if (gassign *ass = dyn_cast <gassign *> (use_stmt))
460 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
461 && luse_p->use == gimple_assign_rhs1_ptr (ass))
463 has_bit_insert = true;
464 break;
469 if (has_bit_insert)
470 return NULL_TREE;
472 /* Limit the walking to a constant number of stmts after
473 we overcommit quadratic behavior for small functions
474 and O(n) behavior. */
475 if (wlims.oracle_cnt > 128 * 128
476 && wlims.oracle_cnt > wlims.vdef_cnt * 2)
477 wlims.limit = 32;
479 check_defs_data data;
480 bool fentry_reached = false;
481 data.found_may_defs = false;
482 tree use = gimple_vuse (stmt);
483 if (!use)
484 return NULL_TREE;
485 int res = walk_aliased_vdefs (&ref, use,
486 check_defs, &data, NULL,
487 &fentry_reached, wlims.limit);
488 if (res == -1)
490 wlims.oracle_cnt += wlims.limit;
491 return NULL_TREE;
494 wlims.oracle_cnt += res;
495 if (data.found_may_defs)
496 return NULL_TREE;
498 bool found_alloc = false;
500 if (fentry_reached)
502 if (TREE_CODE (base) == MEM_REF)
503 base = TREE_OPERAND (base, 0);
505 /* Follow the chain of SSA_NAME assignments looking for an alloca
506 call (or VLA) or malloc/realloc, or for decls. If any is found
507 (and in the latter case, the operand is a local variable) issue
508 a warning. */
509 while (TREE_CODE (base) == SSA_NAME)
511 gimple *def_stmt = SSA_NAME_DEF_STMT (base);
513 if (is_gimple_call (def_stmt)
514 && gimple_call_builtin_p (def_stmt))
516 /* Detect uses of uninitialized alloca/VLAs. */
517 tree fndecl = gimple_call_fndecl (def_stmt);
518 const built_in_function fncode = DECL_FUNCTION_CODE (fndecl);
519 if (fncode == BUILT_IN_ALLOCA
520 || fncode == BUILT_IN_ALLOCA_WITH_ALIGN
521 || fncode == BUILT_IN_MALLOC)
522 found_alloc = true;
523 break;
526 if (!is_gimple_assign (def_stmt))
527 break;
529 tree_code code = gimple_assign_rhs_code (def_stmt);
530 if (code != ADDR_EXPR && code != POINTER_PLUS_EXPR)
531 break;
533 base = gimple_assign_rhs1 (def_stmt);
534 if (TREE_CODE (base) == ADDR_EXPR)
535 base = TREE_OPERAND (base, 0);
537 if (DECL_P (base)
538 || TREE_CODE (base) == COMPONENT_REF)
539 rhs = base;
541 if (TREE_CODE (base) == MEM_REF)
542 base = TREE_OPERAND (base, 0);
544 if (tree ba = get_base_address (base))
545 base = ba;
548 /* Replace the RHS expression with BASE so that it
549 refers to it in the diagnostic (instead of to
550 '<unknown>'). */
551 if (DECL_P (base)
552 && EXPR_P (rhs)
553 && TREE_CODE (rhs) != COMPONENT_REF)
554 rhs = base;
557 /* Do not warn if it can be initialized outside this function.
558 If we did not reach function entry then we found killing
559 clobbers on all paths to entry. */
560 if (!found_alloc && fentry_reached)
562 if (TREE_CODE (base) == SSA_NAME)
564 tree var = SSA_NAME_VAR (base);
565 if (var && TREE_CODE (var) == PARM_DECL)
567 maybe_warn_read_write_only (cfun->decl, stmt, var, rhs);
568 return NULL_TREE;
572 if (!VAR_P (base)
573 || is_global_var (base))
574 /* ??? We'd like to use ref_may_alias_global_p but that
575 excludes global readonly memory and thus we get bogus
576 warnings from p = cond ? "a" : "b" for example. */
577 return NULL_TREE;
580 /* Strip the address-of expression from arrays passed to functions. */
581 if (TREE_CODE (rhs) == ADDR_EXPR)
582 rhs = TREE_OPERAND (rhs, 0);
584 /* Check again since RHS may have changed above. */
585 if (get_no_uninit_warning (rhs))
586 return NULL_TREE;
588 /* Avoid warning about empty types such as structs with no members.
589 The first_field() test is important for C++ where the predicate
590 alone isn't always sufficient. */
591 tree rhstype = TREE_TYPE (rhs);
592 if (POINTER_TYPE_P (rhstype))
593 rhstype = TREE_TYPE (rhstype);
594 if (is_empty_type (rhstype))
595 return NULL_TREE;
597 bool warned = false;
598 /* We didn't find any may-defs so on all paths either
599 reached function entry or a killing clobber. */
600 location_t location
601 = linemap_resolve_location (line_table, gimple_location (stmt),
602 LRK_SPELLING_LOCATION, NULL);
603 if (wlims.always_executed)
605 if (warning_at (location, OPT_Wuninitialized,
606 "%qE is used uninitialized", rhs))
608 /* ??? This is only effective for decls as in
609 gcc.dg/uninit-B-O0.c. Avoid doing this for maybe-uninit
610 uses or accesses by functions as it may hide important
611 locations. */
612 if (lhs)
613 set_no_uninit_warning (rhs);
614 warned = true;
617 else if (wlims.wmaybe_uninit)
618 warned = warning_at (location, OPT_Wmaybe_uninitialized,
619 "%qE may be used uninitialized", rhs);
621 return warned ? base : NULL_TREE;
625 /* Diagnose passing addresses of uninitialized objects to either const
626 pointer arguments to functions, or to functions declared with attribute
627 access implying read access to those objects. */
629 static void
630 maybe_warn_pass_by_reference (gcall *stmt, wlimits &wlims)
632 if (!wlims.wmaybe_uninit)
633 return;
635 unsigned nargs = gimple_call_num_args (stmt);
636 if (!nargs)
637 return;
639 tree fndecl = gimple_call_fndecl (stmt);
640 tree fntype = gimple_call_fntype (stmt);
641 if (!fntype)
642 return;
644 /* Const function do not read their arguments. */
645 if (gimple_call_flags (stmt) & ECF_CONST)
646 return;
648 const built_in_function fncode
649 = (fndecl && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)
650 ? DECL_FUNCTION_CODE (fndecl) : (built_in_function)BUILT_IN_LAST);
652 if (fncode == BUILT_IN_MEMCPY || fncode == BUILT_IN_MEMMOVE)
653 /* Avoid diagnosing calls to raw memory functions (this is overly
654 permissive; consider tightening it up). */
655 return;
657 /* Save the current warning setting and replace it either a "maybe"
658 when passing addresses of uninitialized variables to const-qualified
659 pointers or arguments declared with attribute read_write, or with
660 a "certain" when passing them to arguments declared with attribute
661 read_only. */
662 const bool save_always_executed = wlims.always_executed;
664 /* Initialize a map of attribute access specifications for arguments
665 to the function function call. */
666 rdwr_map rdwr_idx;
667 init_attr_rdwr_indices (&rdwr_idx, TYPE_ATTRIBUTES (fntype));
669 tree argtype;
670 unsigned argno = 0;
671 function_args_iterator it;
673 FOREACH_FUNCTION_ARGS (fntype, argtype, it)
675 ++argno;
677 if (!POINTER_TYPE_P (argtype))
678 continue;
680 tree access_size = NULL_TREE;
681 const attr_access* access = rdwr_idx.get (argno - 1);
682 if (access)
684 if (access->mode == access_none
685 || access->mode == access_write_only)
686 continue;
688 if (access->mode == access_deferred
689 && !TYPE_READONLY (TREE_TYPE (argtype)))
690 continue;
692 if (save_always_executed && access->mode == access_read_only)
693 /* Attribute read_only arguments imply read access. */
694 wlims.always_executed = true;
695 else
696 /* Attribute read_write arguments are documented as requiring
697 initialized objects but it's expected that aggregates may
698 be only partially initialized regardless. */
699 wlims.always_executed = false;
701 if (access->sizarg < nargs)
702 access_size = gimple_call_arg (stmt, access->sizarg);
704 else if (!TYPE_READONLY (TREE_TYPE (argtype)))
705 continue;
706 else if (save_always_executed && fncode != BUILT_IN_LAST)
707 /* Const-qualified arguments to built-ins imply read access. */
708 wlims.always_executed = true;
709 else
710 /* Const-qualified arguments to ordinary functions imply a likely
711 (but not definitive) read access. */
712 wlims.always_executed = false;
714 /* Ignore args we are not going to read from. */
715 if (gimple_call_arg_flags (stmt, argno - 1) & (EAF_UNUSED | EAF_NOREAD))
716 continue;
718 tree arg = gimple_call_arg (stmt, argno - 1);
719 if (!POINTER_TYPE_P (TREE_TYPE (arg)))
720 /* Avoid actual arguments with invalid types. */
721 continue;
723 ao_ref ref;
724 ao_ref_init_from_ptr_and_size (&ref, arg, access_size);
725 tree argbase = maybe_warn_operand (ref, stmt, NULL_TREE, arg, wlims);
726 if (!argbase)
727 continue;
729 if (access && access->mode != access_deferred)
731 const char* const access_str =
732 TREE_STRING_POINTER (access->to_external_string ());
734 if (fndecl)
736 location_t loc = DECL_SOURCE_LOCATION (fndecl);
737 inform (loc, "in a call to %qD declared with "
738 "attribute %<%s%> here", fndecl, access_str);
740 else
742 /* Handle calls through function pointers. */
743 location_t loc = gimple_location (stmt);
744 inform (loc, "in a call to %qT declared with "
745 "attribute %<%s%>", fntype, access_str);
748 else
750 /* For a declaration with no relevant attribute access create
751 a dummy object and use the formatting function to avoid
752 having to complicate things here. */
753 attr_access ptr_access = { };
754 if (!access)
755 access = &ptr_access;
756 const std::string argtypestr = access->array_as_string (argtype);
757 if (fndecl)
759 location_t loc (DECL_SOURCE_LOCATION (fndecl));
760 inform (loc, "by argument %u of type %s to %qD "
761 "declared here",
762 argno, argtypestr.c_str (), fndecl);
764 else
766 /* Handle calls through function pointers. */
767 location_t loc (gimple_location (stmt));
768 inform (loc, "by argument %u of type %s to %qT",
769 argno, argtypestr.c_str (), fntype);
773 if (DECL_P (argbase))
775 location_t loc = DECL_SOURCE_LOCATION (argbase);
776 inform (loc, "%qD declared here", argbase);
780 wlims.always_executed = save_always_executed;
783 /* Warn about an uninitialized PHI argument on the fallthru path to
784 an always executed block BB. */
786 static void
787 warn_uninit_phi_uses (basic_block bb)
789 edge_iterator ei;
790 edge e, found = NULL, found_back = NULL;
791 /* Look for a fallthru and possibly a single backedge. */
792 FOR_EACH_EDGE (e, ei, bb->preds)
794 /* Ignore backedges. */
795 if (dominated_by_p (CDI_DOMINATORS, e->src, bb))
797 if (found_back)
799 found = NULL;
800 break;
802 found_back = e;
803 continue;
805 if (found)
807 found = NULL;
808 break;
810 found = e;
812 if (!found)
813 return;
815 basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
816 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
817 gsi_next (&si))
819 gphi *phi = si.phi ();
820 tree def = PHI_ARG_DEF_FROM_EDGE (phi, found);
821 if (TREE_CODE (def) != SSA_NAME
822 || !SSA_NAME_IS_DEFAULT_DEF (def)
823 || virtual_operand_p (def))
824 continue;
825 /* If there's a default def on the fallthru edge PHI
826 value and there's a use that post-dominates entry
827 then that use is uninitialized and we can warn. */
828 imm_use_iterator iter;
829 use_operand_p use_p;
830 gimple *use_stmt = NULL;
831 FOR_EACH_IMM_USE_FAST (use_p, iter, gimple_phi_result (phi))
833 use_stmt = USE_STMT (use_p);
834 if (gimple_location (use_stmt) != UNKNOWN_LOCATION
835 && dominated_by_p (CDI_POST_DOMINATORS, succ,
836 gimple_bb (use_stmt))
837 /* If we found a non-fallthru edge make sure the
838 use is inside the loop, otherwise the backedge
839 can serve as initialization. */
840 && (!found_back
841 || dominated_by_p (CDI_DOMINATORS, found_back->src,
842 gimple_bb (use_stmt))))
843 break;
844 use_stmt = NULL;
846 if (use_stmt)
847 warn_uninit (OPT_Wuninitialized, def, SSA_NAME_VAR (def),
848 SSA_NAME_VAR (def),
849 "%qD is used uninitialized", use_stmt,
850 UNKNOWN_LOCATION);
854 static unsigned int
855 warn_uninitialized_vars (bool wmaybe_uninit)
857 /* Counters and limits controlling the the depth of the warning. */
858 wlimits wlims = { };
859 wlims.wmaybe_uninit = wmaybe_uninit;
861 gimple_stmt_iterator gsi;
862 basic_block bb;
863 FOR_EACH_BB_FN (bb, cfun)
865 basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
866 wlims.always_executed = dominated_by_p (CDI_POST_DOMINATORS, succ, bb);
868 if (wlims.always_executed)
869 warn_uninit_phi_uses (bb);
871 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
873 gimple *stmt = gsi_stmt (gsi);
874 use_operand_p use_p;
875 ssa_op_iter op_iter;
876 tree use;
878 if (is_gimple_debug (stmt))
879 continue;
881 /* We only do data flow with SSA_NAMEs, so that's all we
882 can warn about. */
883 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
885 /* BIT_INSERT_EXPR first operand should not be considered
886 a use for the purpose of uninit warnings. */
887 if (gassign *ass = dyn_cast <gassign *> (stmt))
889 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
890 && use_p->use == gimple_assign_rhs1_ptr (ass))
891 continue;
893 use = USE_FROM_PTR (use_p);
894 if (wlims.always_executed)
895 warn_uninit (OPT_Wuninitialized, use, SSA_NAME_VAR (use),
896 SSA_NAME_VAR (use),
897 "%qD is used uninitialized", stmt,
898 UNKNOWN_LOCATION);
899 else if (wmaybe_uninit)
900 warn_uninit (OPT_Wmaybe_uninitialized, use, SSA_NAME_VAR (use),
901 SSA_NAME_VAR (use),
902 "%qD may be used uninitialized",
903 stmt, UNKNOWN_LOCATION);
906 /* For limiting the alias walk below we count all
907 vdefs in the function. */
908 if (gimple_vdef (stmt))
909 wlims.vdef_cnt++;
911 if (gcall *call = dyn_cast <gcall *> (stmt))
912 maybe_warn_pass_by_reference (call, wlims);
913 else if (gimple_assign_load_p (stmt)
914 && gimple_has_location (stmt))
916 tree rhs = gimple_assign_rhs1 (stmt);
917 tree lhs = gimple_assign_lhs (stmt);
919 ao_ref ref;
920 ao_ref_init (&ref, rhs);
921 tree var = maybe_warn_operand (ref, stmt, lhs, rhs, wlims);
922 if (!var)
923 continue;
925 if (DECL_P (var))
927 location_t loc = DECL_SOURCE_LOCATION (var);
928 inform (loc, "%qD declared here", var);
934 return 0;
937 /* Checks if the operand OPND of PHI is defined by
938 another phi with one operand defined by this PHI,
939 but the rest operands are all defined. If yes,
940 returns true to skip this operand as being
941 redundant. Can be enhanced to be more general. */
943 static bool
944 can_skip_redundant_opnd (tree opnd, gimple *phi)
946 gimple *op_def;
947 tree phi_def;
948 int i, n;
950 phi_def = gimple_phi_result (phi);
951 op_def = SSA_NAME_DEF_STMT (opnd);
952 if (gimple_code (op_def) != GIMPLE_PHI)
953 return false;
954 n = gimple_phi_num_args (op_def);
955 for (i = 0; i < n; ++i)
957 tree op = gimple_phi_arg_def (op_def, i);
958 if (TREE_CODE (op) != SSA_NAME)
959 continue;
960 if (op != phi_def && uninit_undefined_value_p (op))
961 return false;
964 return true;
967 /* Returns a bit mask holding the positions of arguments in PHI
968 that have empty (or possibly empty) definitions. */
970 static unsigned
971 compute_uninit_opnds_pos (gphi *phi)
973 size_t i, n;
974 unsigned uninit_opnds = 0;
976 n = gimple_phi_num_args (phi);
977 /* Bail out for phi with too many args. */
978 if (n > max_phi_args)
979 return 0;
981 for (i = 0; i < n; ++i)
983 tree op = gimple_phi_arg_def (phi, i);
984 if (TREE_CODE (op) == SSA_NAME
985 && uninit_undefined_value_p (op)
986 && !can_skip_redundant_opnd (op, phi))
988 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
990 /* Ignore SSA_NAMEs that appear on abnormal edges
991 somewhere. */
992 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
993 continue;
995 MASK_SET_BIT (uninit_opnds, i);
998 return uninit_opnds;
1001 /* Find the immediate postdominator PDOM of the specified
1002 basic block BLOCK. */
1004 static inline basic_block
1005 find_pdom (basic_block block)
1007 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
1008 return EXIT_BLOCK_PTR_FOR_FN (cfun);
1009 else
1011 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
1012 if (!bb)
1013 return EXIT_BLOCK_PTR_FOR_FN (cfun);
1014 return bb;
1018 /* Find the immediate DOM of the specified basic block BLOCK. */
1020 static inline basic_block
1021 find_dom (basic_block block)
1023 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1024 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
1025 else
1027 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
1028 if (!bb)
1029 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
1030 return bb;
1034 /* Returns true if BB1 is postdominating BB2 and BB1 is
1035 not a loop exit bb. The loop exit bb check is simple and does
1036 not cover all cases. */
1038 static bool
1039 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
1041 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
1042 return false;
1044 if (single_pred_p (bb1) && !single_succ_p (bb2))
1045 return false;
1047 return true;
1050 /* Find the closest postdominator of a specified BB, which is control
1051 equivalent to BB. */
1053 static inline basic_block
1054 find_control_equiv_block (basic_block bb)
1056 basic_block pdom;
1058 pdom = find_pdom (bb);
1060 /* Skip the postdominating bb that is also loop exit. */
1061 if (!is_non_loop_exit_postdominating (pdom, bb))
1062 return NULL;
1064 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
1065 return pdom;
1067 return NULL;
1070 #define MAX_NUM_CHAINS 8
1071 #define MAX_CHAIN_LEN 5
1072 #define MAX_POSTDOM_CHECK 8
1073 #define MAX_SWITCH_CASES 40
1075 /* Computes the control dependence chains (paths of edges)
1076 for DEP_BB up to the dominating basic block BB (the head node of a
1077 chain should be dominated by it). CD_CHAINS is pointer to an
1078 array holding the result chains. CUR_CD_CHAIN is the current
1079 chain being computed. *NUM_CHAINS is total number of chains. The
1080 function returns true if the information is successfully computed,
1081 return false if there is no control dependence or not computed. */
1083 static bool
1084 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
1085 vec<edge> *cd_chains,
1086 size_t *num_chains,
1087 vec<edge> *cur_cd_chain,
1088 int *num_calls)
1090 edge_iterator ei;
1091 edge e;
1092 size_t i;
1093 bool found_cd_chain = false;
1094 size_t cur_chain_len = 0;
1096 if (*num_calls > param_uninit_control_dep_attempts)
1097 return false;
1098 ++*num_calls;
1100 /* Could use a set instead. */
1101 cur_chain_len = cur_cd_chain->length ();
1102 if (cur_chain_len > MAX_CHAIN_LEN)
1103 return false;
1105 for (i = 0; i < cur_chain_len; i++)
1107 edge e = (*cur_cd_chain)[i];
1108 /* Cycle detected. */
1109 if (e->src == bb)
1110 return false;
1113 FOR_EACH_EDGE (e, ei, bb->succs)
1115 basic_block cd_bb;
1116 int post_dom_check = 0;
1117 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
1118 continue;
1120 cd_bb = e->dest;
1121 cur_cd_chain->safe_push (e);
1122 while (!is_non_loop_exit_postdominating (cd_bb, bb))
1124 if (cd_bb == dep_bb)
1126 /* Found a direct control dependence. */
1127 if (*num_chains < MAX_NUM_CHAINS)
1129 cd_chains[*num_chains] = cur_cd_chain->copy ();
1130 (*num_chains)++;
1132 found_cd_chain = true;
1133 /* Check path from next edge. */
1134 break;
1137 /* Now check if DEP_BB is indirectly control dependent on BB. */
1138 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains,
1139 cur_cd_chain, num_calls))
1141 found_cd_chain = true;
1142 break;
1145 cd_bb = find_pdom (cd_bb);
1146 post_dom_check++;
1147 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1148 || post_dom_check > MAX_POSTDOM_CHECK)
1149 break;
1151 cur_cd_chain->pop ();
1152 gcc_assert (cur_cd_chain->length () == cur_chain_len);
1154 gcc_assert (cur_cd_chain->length () == cur_chain_len);
1156 return found_cd_chain;
1159 /* The type to represent a simple predicate. */
1161 struct pred_info
1163 tree pred_lhs;
1164 tree pred_rhs;
1165 enum tree_code cond_code;
1166 bool invert;
1169 /* The type to represent a sequence of predicates grouped
1170 with .AND. operation. */
1172 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
1174 /* The type to represent a sequence of pred_chains grouped
1175 with .OR. operation. */
1177 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
1179 /* Converts the chains of control dependence edges into a set of
1180 predicates. A control dependence chain is represented by a vector
1181 edges. DEP_CHAINS points to an array of dependence chains.
1182 NUM_CHAINS is the size of the chain array. One edge in a dependence
1183 chain is mapped to predicate expression represented by pred_info
1184 type. One dependence chain is converted to a composite predicate that
1185 is the result of AND operation of pred_info mapped to each edge.
1186 A composite predicate is presented by a vector of pred_info. On
1187 return, *PREDS points to the resulting array of composite predicates.
1188 *NUM_PREDS is the number of composite predictes. */
1190 static bool
1191 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
1192 size_t num_chains,
1193 pred_chain_union *preds)
1195 bool has_valid_pred = false;
1196 size_t i, j;
1197 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
1198 return false;
1200 /* Now convert the control dep chain into a set
1201 of predicates. */
1202 preds->reserve (num_chains);
1204 for (i = 0; i < num_chains; i++)
1206 vec<edge> one_cd_chain = dep_chains[i];
1208 has_valid_pred = false;
1209 pred_chain t_chain = vNULL;
1210 for (j = 0; j < one_cd_chain.length (); j++)
1212 gimple *cond_stmt;
1213 gimple_stmt_iterator gsi;
1214 basic_block guard_bb;
1215 pred_info one_pred;
1216 edge e;
1218 e = one_cd_chain[j];
1219 guard_bb = e->src;
1220 gsi = gsi_last_bb (guard_bb);
1221 /* Ignore empty forwarder blocks. */
1222 if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
1223 continue;
1224 /* An empty basic block here is likely a PHI, and is not one
1225 of the cases we handle below. */
1226 if (gsi_end_p (gsi))
1228 has_valid_pred = false;
1229 break;
1231 cond_stmt = gsi_stmt (gsi);
1232 if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
1233 /* Ignore EH edge. Can add assertion on the other edge's flag. */
1234 continue;
1235 /* Skip if there is essentially one succesor. */
1236 if (EDGE_COUNT (e->src->succs) == 2)
1238 edge e1;
1239 edge_iterator ei1;
1240 bool skip = false;
1242 FOR_EACH_EDGE (e1, ei1, e->src->succs)
1244 if (EDGE_COUNT (e1->dest->succs) == 0)
1246 skip = true;
1247 break;
1250 if (skip)
1251 continue;
1253 if (gimple_code (cond_stmt) == GIMPLE_COND)
1255 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
1256 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
1257 one_pred.cond_code = gimple_cond_code (cond_stmt);
1258 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
1259 t_chain.safe_push (one_pred);
1260 has_valid_pred = true;
1262 else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
1264 /* Avoid quadratic behavior. */
1265 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
1267 has_valid_pred = false;
1268 break;
1270 /* Find the case label. */
1271 tree l = NULL_TREE;
1272 unsigned idx;
1273 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
1275 tree tl = gimple_switch_label (gs, idx);
1276 if (e->dest == label_to_block (cfun, CASE_LABEL (tl)))
1278 if (!l)
1279 l = tl;
1280 else
1282 l = NULL_TREE;
1283 break;
1287 /* If more than one label reaches this block or the case
1288 label doesn't have a single value (like the default one)
1289 fail. */
1290 if (!l
1291 || !CASE_LOW (l)
1292 || (CASE_HIGH (l)
1293 && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0)))
1295 has_valid_pred = false;
1296 break;
1298 one_pred.pred_lhs = gimple_switch_index (gs);
1299 one_pred.pred_rhs = CASE_LOW (l);
1300 one_pred.cond_code = EQ_EXPR;
1301 one_pred.invert = false;
1302 t_chain.safe_push (one_pred);
1303 has_valid_pred = true;
1305 else
1307 has_valid_pred = false;
1308 break;
1312 if (!has_valid_pred)
1313 break;
1314 else
1315 preds->safe_push (t_chain);
1317 return has_valid_pred;
1320 /* Computes all control dependence chains for USE_BB. The control
1321 dependence chains are then converted to an array of composite
1322 predicates pointed to by PREDS. PHI_BB is the basic block of
1323 the phi whose result is used in USE_BB. */
1325 static bool
1326 find_predicates (pred_chain_union *preds,
1327 basic_block phi_bb,
1328 basic_block use_bb)
1330 size_t num_chains = 0, i;
1331 int num_calls = 0;
1332 vec<edge> dep_chains[MAX_NUM_CHAINS];
1333 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
1334 bool has_valid_pred = false;
1335 basic_block cd_root = 0;
1337 /* First find the closest bb that is control equivalent to PHI_BB
1338 that also dominates USE_BB. */
1339 cd_root = phi_bb;
1340 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
1342 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
1343 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
1344 cd_root = ctrl_eq_bb;
1345 else
1346 break;
1349 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
1350 &cur_chain, &num_calls);
1352 has_valid_pred
1353 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
1354 for (i = 0; i < num_chains; i++)
1355 dep_chains[i].release ();
1356 return has_valid_pred;
1359 /* Computes the set of incoming edges of PHI that have non empty
1360 definitions of a phi chain. The collection will be done
1361 recursively on operands that are defined by phis. CD_ROOT
1362 is the control dependence root. *EDGES holds the result, and
1363 VISITED_PHIS is a pointer set for detecting cycles. */
1365 static void
1366 collect_phi_def_edges (gphi *phi, basic_block cd_root,
1367 auto_vec<edge> *edges,
1368 hash_set<gimple *> *visited_phis)
1370 size_t i, n;
1371 edge opnd_edge;
1372 tree opnd;
1374 if (visited_phis->add (phi))
1375 return;
1377 n = gimple_phi_num_args (phi);
1378 for (i = 0; i < n; i++)
1380 opnd_edge = gimple_phi_arg_edge (phi, i);
1381 opnd = gimple_phi_arg_def (phi, i);
1383 if (TREE_CODE (opnd) != SSA_NAME)
1385 if (dump_file && (dump_flags & TDF_DETAILS))
1387 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i);
1388 print_gimple_stmt (dump_file, phi, 0);
1390 edges->safe_push (opnd_edge);
1392 else
1394 gimple *def = SSA_NAME_DEF_STMT (opnd);
1396 if (gimple_code (def) == GIMPLE_PHI
1397 && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
1398 collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
1399 visited_phis);
1400 else if (!uninit_undefined_value_p (opnd))
1402 if (dump_file && (dump_flags & TDF_DETAILS))
1404 fprintf (dump_file, "\n[CHECK] Found def edge %d in ",
1405 (int) i);
1406 print_gimple_stmt (dump_file, phi, 0);
1408 edges->safe_push (opnd_edge);
1414 /* For each use edge of PHI, computes all control dependence chains.
1415 The control dependence chains are then converted to an array of
1416 composite predicates pointed to by PREDS. */
1418 static bool
1419 find_def_preds (pred_chain_union *preds, gphi *phi)
1421 size_t num_chains = 0, i, n;
1422 vec<edge> dep_chains[MAX_NUM_CHAINS];
1423 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
1424 auto_vec<edge> def_edges;
1425 bool has_valid_pred = false;
1426 basic_block phi_bb, cd_root = 0;
1428 phi_bb = gimple_bb (phi);
1429 /* First find the closest dominating bb to be
1430 the control dependence root. */
1431 cd_root = find_dom (phi_bb);
1432 if (!cd_root)
1433 return false;
1435 hash_set<gimple *> visited_phis;
1436 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
1438 n = def_edges.length ();
1439 if (n == 0)
1440 return false;
1442 for (i = 0; i < n; i++)
1444 size_t prev_nc, j;
1445 int num_calls = 0;
1446 edge opnd_edge;
1448 opnd_edge = def_edges[i];
1449 prev_nc = num_chains;
1450 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
1451 &num_chains, &cur_chain, &num_calls);
1453 /* Now update the newly added chains with
1454 the phi operand edge: */
1455 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
1457 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
1458 dep_chains[num_chains++] = vNULL;
1459 for (j = prev_nc; j < num_chains; j++)
1460 dep_chains[j].safe_push (opnd_edge);
1464 has_valid_pred
1465 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
1466 for (i = 0; i < num_chains; i++)
1467 dep_chains[i].release ();
1468 return has_valid_pred;
1471 /* Dump a pred_info. */
1473 static void
1474 dump_pred_info (pred_info one_pred)
1476 if (one_pred.invert)
1477 fprintf (dump_file, " (.NOT.) ");
1478 print_generic_expr (dump_file, one_pred.pred_lhs);
1479 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
1480 print_generic_expr (dump_file, one_pred.pred_rhs);
1483 /* Dump a pred_chain. */
1485 static void
1486 dump_pred_chain (pred_chain one_pred_chain)
1488 size_t np = one_pred_chain.length ();
1489 for (size_t j = 0; j < np; j++)
1491 dump_pred_info (one_pred_chain[j]);
1492 if (j < np - 1)
1493 fprintf (dump_file, " (.AND.) ");
1494 else
1495 fprintf (dump_file, "\n");
1499 /* Dumps the predicates (PREDS) for USESTMT. */
1501 static void
1502 dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
1504 fprintf (dump_file, "%s", msg);
1505 if (usestmt)
1507 print_gimple_stmt (dump_file, usestmt, 0);
1508 fprintf (dump_file, "is guarded by :\n\n");
1510 size_t num_preds = preds.length ();
1511 for (size_t i = 0; i < num_preds; i++)
1513 dump_pred_chain (preds[i]);
1514 if (i < num_preds - 1)
1515 fprintf (dump_file, "(.OR.)\n");
1516 else
1517 fprintf (dump_file, "\n\n");
1521 /* Destroys the predicate set *PREDS. */
1523 static void
1524 destroy_predicate_vecs (pred_chain_union *preds)
1526 size_t i;
1528 size_t n = preds->length ();
1529 for (i = 0; i < n; i++)
1530 (*preds)[i].release ();
1531 preds->release ();
1534 /* Computes the 'normalized' conditional code with operand
1535 swapping and condition inversion. */
1537 static enum tree_code
1538 get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
1540 enum tree_code tc = orig_cmp_code;
1542 if (swap_cond)
1543 tc = swap_tree_comparison (orig_cmp_code);
1544 if (invert)
1545 tc = invert_tree_comparison (tc, false);
1547 switch (tc)
1549 case LT_EXPR:
1550 case LE_EXPR:
1551 case GT_EXPR:
1552 case GE_EXPR:
1553 case EQ_EXPR:
1554 case NE_EXPR:
1555 break;
1556 default:
1557 return ERROR_MARK;
1559 return tc;
1562 /* Returns whether VAL CMPC BOUNDARY is true. */
1564 static bool
1565 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
1567 bool inverted = false;
1568 bool result;
1570 /* Only handle integer constant here. */
1571 if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
1572 return true;
1574 if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
1576 cmpc = invert_tree_comparison (cmpc, false);
1577 inverted = true;
1580 if (cmpc == EQ_EXPR)
1581 result = tree_int_cst_equal (val, boundary);
1582 else if (cmpc == LT_EXPR)
1583 result = tree_int_cst_lt (val, boundary);
1584 else
1586 gcc_assert (cmpc == LE_EXPR);
1587 result = tree_int_cst_le (val, boundary);
1590 if (inverted)
1591 result ^= 1;
1593 return result;
1596 /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can be
1597 either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like),
1598 or BIT_AND_EXPR. EXACT_P is only meaningful for the latter. It modifies the
1599 question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL.
1600 For other values of CMPC, EXACT_P is ignored. */
1602 static bool
1603 value_sat_pred_p (tree val, tree boundary, enum tree_code cmpc,
1604 bool exact_p = false)
1606 if (cmpc != BIT_AND_EXPR)
1607 return is_value_included_in (val, boundary, cmpc);
1609 wide_int andw = wi::to_wide (val) & wi::to_wide (boundary);
1610 if (exact_p)
1611 return andw == wi::to_wide (val);
1612 else
1613 return andw.to_uhwi ();
1616 /* Returns true if PRED is common among all the predicate
1617 chains (PREDS) (and therefore can be factored out). */
1619 static bool
1620 find_matching_predicate_in_rest_chains (pred_info pred, pred_chain_union preds)
1622 size_t i, j, n;
1624 /* Trival case. */
1625 if (preds.length () == 1)
1626 return true;
1628 for (i = 1; i < preds.length (); i++)
1630 bool found = false;
1631 pred_chain one_chain = preds[i];
1632 n = one_chain.length ();
1633 for (j = 0; j < n; j++)
1635 pred_info pred2 = one_chain[j];
1636 /* Can relax the condition comparison to not
1637 use address comparison. However, the most common
1638 case is that multiple control dependent paths share
1639 a common path prefix, so address comparison should
1640 be ok. */
1642 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
1643 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
1644 && pred2.invert == pred.invert)
1646 found = true;
1647 break;
1650 if (!found)
1651 return false;
1653 return true;
1656 /* Forward declaration. */
1657 static bool is_use_properly_guarded (gimple *use_stmt,
1658 basic_block use_bb,
1659 gphi *phi,
1660 unsigned uninit_opnds,
1661 pred_chain_union *def_preds,
1662 hash_set<gphi *> *visited_phis);
1664 /* Returns true if all uninitialized opnds are pruned. Returns false
1665 otherwise. PHI is the phi node with uninitialized operands,
1666 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1667 FLAG_DEF is the statement defining the flag guarding the use of the
1668 PHI output, BOUNDARY_CST is the const value used in the predicate
1669 associated with the flag, CMP_CODE is the comparison code used in
1670 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1671 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1672 that are also phis.
1674 Example scenario:
1676 BB1:
1677 flag_1 = phi <0, 1> // (1)
1678 var_1 = phi <undef, some_val>
1681 BB2:
1682 flag_2 = phi <0, flag_1, flag_1> // (2)
1683 var_2 = phi <undef, var_1, var_1>
1684 if (flag_2 == 1)
1685 goto BB3;
1687 BB3:
1688 use of var_2 // (3)
1690 Because some flag arg in (1) is not constant, if we do not look into the
1691 flag phis recursively, it is conservatively treated as unknown and var_1
1692 is thought to be flowed into use at (3). Since var_1 is potentially
1693 uninitialized a false warning will be emitted.
1694 Checking recursively into (1), the compiler can find out that only some_val
1695 (which is defined) can flow into (3) which is OK. */
1697 static bool
1698 prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
1699 tree boundary_cst, enum tree_code cmp_code,
1700 hash_set<gphi *> *visited_phis,
1701 bitmap *visited_flag_phis)
1703 unsigned i;
1705 for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
1707 tree flag_arg;
1709 if (!MASK_TEST_BIT (uninit_opnds, i))
1710 continue;
1712 flag_arg = gimple_phi_arg_def (flag_def, i);
1713 if (!is_gimple_constant (flag_arg))
1715 gphi *flag_arg_def, *phi_arg_def;
1716 tree phi_arg;
1717 unsigned uninit_opnds_arg_phi;
1719 if (TREE_CODE (flag_arg) != SSA_NAME)
1720 return false;
1721 flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
1722 if (!flag_arg_def)
1723 return false;
1725 phi_arg = gimple_phi_arg_def (phi, i);
1726 if (TREE_CODE (phi_arg) != SSA_NAME)
1727 return false;
1729 phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1730 if (!phi_arg_def)
1731 return false;
1733 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1734 return false;
1736 if (!*visited_flag_phis)
1737 *visited_flag_phis = BITMAP_ALLOC (NULL);
1739 tree phi_result = gimple_phi_result (flag_arg_def);
1740 if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
1741 return false;
1743 bitmap_set_bit (*visited_flag_phis,
1744 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1746 /* Now recursively prune the uninitialized phi args. */
1747 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1748 if (!prune_uninit_phi_opnds
1749 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, boundary_cst,
1750 cmp_code, visited_phis, visited_flag_phis))
1751 return false;
1753 phi_result = gimple_phi_result (flag_arg_def);
1754 bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
1755 continue;
1758 /* Now check if the constant is in the guarded range. */
1759 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1761 tree opnd;
1762 gimple *opnd_def;
1764 /* Now that we know that this undefined edge is not
1765 pruned. If the operand is defined by another phi,
1766 we can further prune the incoming edges of that
1767 phi by checking the predicates of this operands. */
1769 opnd = gimple_phi_arg_def (phi, i);
1770 opnd_def = SSA_NAME_DEF_STMT (opnd);
1771 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
1773 edge opnd_edge;
1774 unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi);
1775 if (!MASK_EMPTY (uninit_opnds2))
1777 pred_chain_union def_preds = vNULL;
1778 bool ok;
1779 opnd_edge = gimple_phi_arg_edge (phi, i);
1780 ok = is_use_properly_guarded (phi,
1781 opnd_edge->src,
1782 opnd_def_phi,
1783 uninit_opnds2,
1784 &def_preds,
1785 visited_phis);
1786 destroy_predicate_vecs (&def_preds);
1787 if (!ok)
1788 return false;
1791 else
1792 return false;
1796 return true;
1799 /* A helper function finds predicate which will be examined against uninit
1800 paths. If there is no "flag_var cmp const" form predicate, the function
1801 tries to find predicate of form like "flag_var cmp flag_var" with value
1802 range info. PHI is the phi node whose incoming (undefined) paths need to
1803 be examined. On success, the function returns the comparsion code, sets
1804 defintion gimple of the flag_var to FLAG_DEF, sets boundary_cst to
1805 BOUNDARY_CST. On fail, the function returns ERROR_MARK. */
1807 static enum tree_code
1808 find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
1809 tree *boundary_cst)
1811 enum tree_code vrinfo_code = ERROR_MARK, code;
1812 gimple *vrinfo_def = NULL;
1813 tree vrinfo_cst = NULL, cond_lhs, cond_rhs;
1815 gcc_assert (preds.length () > 0);
1816 pred_chain the_pred_chain = preds[0];
1817 for (unsigned i = 0; i < the_pred_chain.length (); i++)
1819 bool use_vrinfo_p = false;
1820 pred_info the_pred = the_pred_chain[i];
1821 cond_lhs = the_pred.pred_lhs;
1822 cond_rhs = the_pred.pred_rhs;
1823 if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
1824 continue;
1826 code = get_cmp_code (the_pred.cond_code, false, the_pred.invert);
1827 if (code == ERROR_MARK)
1828 continue;
1830 if (TREE_CODE (cond_lhs) == SSA_NAME && is_gimple_constant (cond_rhs))
1832 else if (TREE_CODE (cond_rhs) == SSA_NAME
1833 && is_gimple_constant (cond_lhs))
1835 std::swap (cond_lhs, cond_rhs);
1836 if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
1837 continue;
1839 /* Check if we can take advantage of "flag_var comp flag_var" predicate
1840 with value range info. Note only first of such case is handled. */
1841 else if (vrinfo_code == ERROR_MARK
1842 && TREE_CODE (cond_lhs) == SSA_NAME
1843 && TREE_CODE (cond_rhs) == SSA_NAME)
1845 gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
1846 if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI
1847 || gimple_bb (lhs_def) != gimple_bb (phi))
1849 std::swap (cond_lhs, cond_rhs);
1850 if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
1851 continue;
1854 /* Check value range info of rhs, do following transforms:
1855 flag_var < [min, max] -> flag_var < max
1856 flag_var > [min, max] -> flag_var > min
1858 We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
1859 flag_var <= [min, max] -> flag_var < [min, max+1]
1860 flag_var >= [min, max] -> flag_var > [min-1, max]
1861 if no overflow/wrap. */
1862 tree type = TREE_TYPE (cond_lhs);
1863 value_range r;
1864 if (!INTEGRAL_TYPE_P (type)
1865 || !get_range_query (cfun)->range_of_expr (r, cond_rhs)
1866 || r.kind () != VR_RANGE)
1867 continue;
1868 wide_int min = r.lower_bound ();
1869 wide_int max = r.upper_bound ();
1870 if (code == LE_EXPR
1871 && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
1873 code = LT_EXPR;
1874 max = max + 1;
1876 if (code == GE_EXPR
1877 && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
1879 code = GT_EXPR;
1880 min = min - 1;
1882 if (code == LT_EXPR)
1883 cond_rhs = wide_int_to_tree (type, max);
1884 else if (code == GT_EXPR)
1885 cond_rhs = wide_int_to_tree (type, min);
1886 else
1887 continue;
1889 use_vrinfo_p = true;
1891 else
1892 continue;
1894 if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
1895 continue;
1897 if (gimple_code (*flag_def) != GIMPLE_PHI
1898 || gimple_bb (*flag_def) != gimple_bb (phi)
1899 || !find_matching_predicate_in_rest_chains (the_pred, preds))
1900 continue;
1902 /* Return if any "flag_var comp const" predicate is found. */
1903 if (!use_vrinfo_p)
1905 *boundary_cst = cond_rhs;
1906 return code;
1908 /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */
1909 else if (vrinfo_code == ERROR_MARK)
1911 vrinfo_code = code;
1912 vrinfo_def = *flag_def;
1913 vrinfo_cst = cond_rhs;
1916 /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */
1917 if (vrinfo_code != ERROR_MARK)
1919 *flag_def = vrinfo_def;
1920 *boundary_cst = vrinfo_cst;
1922 return vrinfo_code;
1925 /* A helper function that determines if the predicate set
1926 of the use is not overlapping with that of the uninit paths.
1927 The most common senario of guarded use is in Example 1:
1928 Example 1:
1929 if (some_cond)
1931 x = ...;
1932 flag = true;
1935 ... some code ...
1937 if (flag)
1938 use (x);
1940 The real world examples are usually more complicated, but similar
1941 and usually result from inlining:
1943 bool init_func (int * x)
1945 if (some_cond)
1946 return false;
1947 *x = ..
1948 return true;
1951 void foo (..)
1953 int x;
1955 if (!init_func (&x))
1956 return;
1958 .. some_code ...
1959 use (x);
1962 Another possible use scenario is in the following trivial example:
1964 Example 2:
1965 if (n > 0)
1966 x = 1;
1968 if (n > 0)
1970 if (m < 2)
1971 .. = x;
1974 Predicate analysis needs to compute the composite predicate:
1976 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1977 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1978 (the predicate chain for phi operand defs can be computed
1979 starting from a bb that is control equivalent to the phi's
1980 bb and is dominating the operand def.)
1982 and check overlapping:
1983 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1984 <==> false
1986 This implementation provides framework that can handle
1987 scenarios. (Note that many simple cases are handled properly
1988 without the predicate analysis -- this is due to jump threading
1989 transformation which eliminates the merge point thus makes
1990 path sensitive analysis unnecessary.)
1992 PHI is the phi node whose incoming (undefined) paths need to be
1993 pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
1994 positions. VISITED_PHIS is the pointer set of phi stmts being
1995 checked. */
1997 static bool
1998 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1999 gphi *phi, unsigned uninit_opnds,
2000 hash_set<gphi *> *visited_phis)
2002 gimple *flag_def = 0;
2003 tree boundary_cst = 0;
2004 enum tree_code cmp_code;
2005 bitmap visited_flag_phis = NULL;
2006 bool all_pruned = false;
2008 /* Find within the common prefix of multiple predicate chains
2009 a predicate that is a comparison of a flag variable against
2010 a constant. */
2011 cmp_code = find_var_cmp_const (preds, phi, &flag_def, &boundary_cst);
2012 if (cmp_code == ERROR_MARK)
2013 return false;
2015 /* Now check all the uninit incoming edge has a constant flag value
2016 that is in conflict with the use guard/predicate. */
2017 all_pruned = prune_uninit_phi_opnds
2018 (phi, uninit_opnds, as_a<gphi *> (flag_def), boundary_cst, cmp_code,
2019 visited_phis, &visited_flag_phis);
2021 if (visited_flag_phis)
2022 BITMAP_FREE (visited_flag_phis);
2024 return all_pruned;
2027 /* The helper function returns true if two predicates X1 and X2
2028 are equivalent. It assumes the expressions have already
2029 properly re-associated. */
2031 static inline bool
2032 pred_equal_p (pred_info x1, pred_info x2)
2034 enum tree_code c1, c2;
2035 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
2036 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
2037 return false;
2039 c1 = x1.cond_code;
2040 if (x1.invert != x2.invert
2041 && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison)
2042 c2 = invert_tree_comparison (x2.cond_code, false);
2043 else
2044 c2 = x2.cond_code;
2046 return c1 == c2;
2049 /* Returns true if the predication is testing !=. */
2051 static inline bool
2052 is_neq_relop_p (pred_info pred)
2055 return ((pred.cond_code == NE_EXPR && !pred.invert)
2056 || (pred.cond_code == EQ_EXPR && pred.invert));
2059 /* Returns true if pred is of the form X != 0. */
2061 static inline bool
2062 is_neq_zero_form_p (pred_info pred)
2064 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
2065 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
2066 return false;
2067 return true;
2070 /* The helper function returns true if two predicates X1
2071 is equivalent to X2 != 0. */
2073 static inline bool
2074 pred_expr_equal_p (pred_info x1, tree x2)
2076 if (!is_neq_zero_form_p (x1))
2077 return false;
2079 return operand_equal_p (x1.pred_lhs, x2, 0);
2082 /* Returns true of the domain of single predicate expression
2083 EXPR1 is a subset of that of EXPR2. Returns false if it
2084 cannot be proved. */
2086 static bool
2087 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
2089 enum tree_code code1, code2;
2091 if (pred_equal_p (expr1, expr2))
2092 return true;
2094 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
2095 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
2096 return false;
2098 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
2099 return false;
2101 code1 = expr1.cond_code;
2102 if (expr1.invert)
2103 code1 = invert_tree_comparison (code1, false);
2104 code2 = expr2.cond_code;
2105 if (expr2.invert)
2106 code2 = invert_tree_comparison (code2, false);
2108 if (code2 == NE_EXPR && code1 == NE_EXPR)
2109 return false;
2111 if (code2 == NE_EXPR)
2112 return !value_sat_pred_p (expr2.pred_rhs, expr1.pred_rhs, code1);
2114 if (code1 == EQ_EXPR)
2115 return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2);
2117 if (code1 == code2)
2118 return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2,
2119 code1 == BIT_AND_EXPR);
2121 return false;
2124 /* Returns true if the domain of PRED1 is a subset
2125 of that of PRED2. Returns false if it cannot be proved so. */
2127 static bool
2128 is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2)
2130 size_t np1, np2, i1, i2;
2132 np1 = pred1.length ();
2133 np2 = pred2.length ();
2135 for (i2 = 0; i2 < np2; i2++)
2137 bool found = false;
2138 pred_info info2 = pred2[i2];
2139 for (i1 = 0; i1 < np1; i1++)
2141 pred_info info1 = pred1[i1];
2142 if (is_pred_expr_subset_of (info1, info2))
2144 found = true;
2145 break;
2148 if (!found)
2149 return false;
2151 return true;
2154 /* Returns true if the domain defined by
2155 one pred chain ONE_PRED is a subset of the domain
2156 of *PREDS. It returns false if ONE_PRED's domain is
2157 not a subset of any of the sub-domains of PREDS
2158 (corresponding to each individual chains in it), even
2159 though it may be still be a subset of whole domain
2160 of PREDS which is the union (ORed) of all its subdomains.
2161 In other words, the result is conservative. */
2163 static bool
2164 is_included_in (pred_chain one_pred, pred_chain_union preds)
2166 size_t i;
2167 size_t n = preds.length ();
2169 for (i = 0; i < n; i++)
2171 if (is_pred_chain_subset_of (one_pred, preds[i]))
2172 return true;
2175 return false;
2178 /* Compares two predicate sets PREDS1 and PREDS2 and returns
2179 true if the domain defined by PREDS1 is a superset
2180 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
2181 PREDS2 respectively. The implementation chooses not to build
2182 generic trees (and relying on the folding capability of the
2183 compiler), but instead performs brute force comparison of
2184 individual predicate chains (won't be a compile time problem
2185 as the chains are pretty short). When the function returns
2186 false, it does not necessarily mean *PREDS1 is not a superset
2187 of *PREDS2, but mean it may not be so since the analysis cannot
2188 prove it. In such cases, false warnings may still be
2189 emitted. */
2191 static bool
2192 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
2194 size_t i, n2;
2195 pred_chain one_pred_chain = vNULL;
2197 n2 = preds2.length ();
2199 for (i = 0; i < n2; i++)
2201 one_pred_chain = preds2[i];
2202 if (!is_included_in (one_pred_chain, preds1))
2203 return false;
2206 return true;
2209 /* Returns true if X1 is the negate of X2. */
2211 static inline bool
2212 pred_neg_p (pred_info x1, pred_info x2)
2214 enum tree_code c1, c2;
2215 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
2216 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
2217 return false;
2219 c1 = x1.cond_code;
2220 if (x1.invert == x2.invert)
2221 c2 = invert_tree_comparison (x2.cond_code, false);
2222 else
2223 c2 = x2.cond_code;
2225 return c1 == c2;
2228 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
2229 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
2230 3) X OR (!X AND Y) is equivalent to (X OR Y);
2231 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
2232 (x != 0 AND y != 0)
2233 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
2234 (X AND Y) OR Z
2236 PREDS is the predicate chains, and N is the number of chains. */
2238 /* Helper function to implement rule 1 above. ONE_CHAIN is
2239 the AND predication to be simplified. */
2241 static void
2242 simplify_pred (pred_chain *one_chain)
2244 size_t i, j, n;
2245 bool simplified = false;
2246 pred_chain s_chain = vNULL;
2248 n = one_chain->length ();
2250 for (i = 0; i < n; i++)
2252 pred_info *a_pred = &(*one_chain)[i];
2254 if (!a_pred->pred_lhs)
2255 continue;
2256 if (!is_neq_zero_form_p (*a_pred))
2257 continue;
2259 gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
2260 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2261 continue;
2262 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
2264 for (j = 0; j < n; j++)
2266 pred_info *b_pred = &(*one_chain)[j];
2268 if (!b_pred->pred_lhs)
2269 continue;
2270 if (!is_neq_zero_form_p (*b_pred))
2271 continue;
2273 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
2274 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
2276 /* Mark a_pred for removal. */
2277 a_pred->pred_lhs = NULL;
2278 a_pred->pred_rhs = NULL;
2279 simplified = true;
2280 break;
2286 if (!simplified)
2287 return;
2289 for (i = 0; i < n; i++)
2291 pred_info *a_pred = &(*one_chain)[i];
2292 if (!a_pred->pred_lhs)
2293 continue;
2294 s_chain.safe_push (*a_pred);
2297 one_chain->release ();
2298 *one_chain = s_chain;
2301 /* The helper function implements the rule 2 for the
2302 OR predicate PREDS.
2304 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
2306 static bool
2307 simplify_preds_2 (pred_chain_union *preds)
2309 size_t i, j, n;
2310 bool simplified = false;
2311 pred_chain_union s_preds = vNULL;
2313 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
2314 (X AND Y) OR (X AND !Y) is equivalent to X. */
2316 n = preds->length ();
2317 for (i = 0; i < n; i++)
2319 pred_info x, y;
2320 pred_chain *a_chain = &(*preds)[i];
2322 if (a_chain->length () != 2)
2323 continue;
2325 x = (*a_chain)[0];
2326 y = (*a_chain)[1];
2328 for (j = 0; j < n; j++)
2330 pred_chain *b_chain;
2331 pred_info x2, y2;
2333 if (j == i)
2334 continue;
2336 b_chain = &(*preds)[j];
2337 if (b_chain->length () != 2)
2338 continue;
2340 x2 = (*b_chain)[0];
2341 y2 = (*b_chain)[1];
2343 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
2345 /* Kill a_chain. */
2346 a_chain->release ();
2347 b_chain->release ();
2348 b_chain->safe_push (x);
2349 simplified = true;
2350 break;
2352 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
2354 /* Kill a_chain. */
2355 a_chain->release ();
2356 b_chain->release ();
2357 b_chain->safe_push (y);
2358 simplified = true;
2359 break;
2363 /* Now clean up the chain. */
2364 if (simplified)
2366 for (i = 0; i < n; i++)
2368 if ((*preds)[i].is_empty ())
2369 continue;
2370 s_preds.safe_push ((*preds)[i]);
2372 preds->release ();
2373 (*preds) = s_preds;
2374 s_preds = vNULL;
2377 return simplified;
2380 /* The helper function implements the rule 2 for the
2381 OR predicate PREDS.
2383 3) x OR (!x AND y) is equivalent to x OR y. */
2385 static bool
2386 simplify_preds_3 (pred_chain_union *preds)
2388 size_t i, j, n;
2389 bool simplified = false;
2391 /* Now iteratively simplify X OR (!X AND Z ..)
2392 into X OR (Z ...). */
2394 n = preds->length ();
2395 if (n < 2)
2396 return false;
2398 for (i = 0; i < n; i++)
2400 pred_info x;
2401 pred_chain *a_chain = &(*preds)[i];
2403 if (a_chain->length () != 1)
2404 continue;
2406 x = (*a_chain)[0];
2408 for (j = 0; j < n; j++)
2410 pred_chain *b_chain;
2411 pred_info x2;
2412 size_t k;
2414 if (j == i)
2415 continue;
2417 b_chain = &(*preds)[j];
2418 if (b_chain->length () < 2)
2419 continue;
2421 for (k = 0; k < b_chain->length (); k++)
2423 x2 = (*b_chain)[k];
2424 if (pred_neg_p (x, x2))
2426 b_chain->unordered_remove (k);
2427 simplified = true;
2428 break;
2433 return simplified;
2436 /* The helper function implements the rule 4 for the
2437 OR predicate PREDS.
2439 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
2440 (x != 0 ANd y != 0). */
2442 static bool
2443 simplify_preds_4 (pred_chain_union *preds)
2445 size_t i, j, n;
2446 bool simplified = false;
2447 pred_chain_union s_preds = vNULL;
2448 gimple *def_stmt;
2450 n = preds->length ();
2451 for (i = 0; i < n; i++)
2453 pred_info z;
2454 pred_chain *a_chain = &(*preds)[i];
2456 if (a_chain->length () != 1)
2457 continue;
2459 z = (*a_chain)[0];
2461 if (!is_neq_zero_form_p (z))
2462 continue;
2464 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
2465 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2466 continue;
2468 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
2469 continue;
2471 for (j = 0; j < n; j++)
2473 pred_chain *b_chain;
2474 pred_info x2, y2;
2476 if (j == i)
2477 continue;
2479 b_chain = &(*preds)[j];
2480 if (b_chain->length () != 2)
2481 continue;
2483 x2 = (*b_chain)[0];
2484 y2 = (*b_chain)[1];
2485 if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
2486 continue;
2488 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
2489 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
2490 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
2491 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
2493 /* Kill a_chain. */
2494 a_chain->release ();
2495 simplified = true;
2496 break;
2500 /* Now clean up the chain. */
2501 if (simplified)
2503 for (i = 0; i < n; i++)
2505 if ((*preds)[i].is_empty ())
2506 continue;
2507 s_preds.safe_push ((*preds)[i]);
2510 preds->release ();
2511 (*preds) = s_preds;
2512 s_preds = vNULL;
2515 return simplified;
2518 /* This function simplifies predicates in PREDS. */
2520 static void
2521 simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use)
2523 size_t i, n;
2524 bool changed = false;
2526 if (dump_file && dump_flags & TDF_DETAILS)
2528 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
2529 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2532 for (i = 0; i < preds->length (); i++)
2533 simplify_pred (&(*preds)[i]);
2535 n = preds->length ();
2536 if (n < 2)
2537 return;
2541 changed = false;
2542 if (simplify_preds_2 (preds))
2543 changed = true;
2545 /* Now iteratively simplify X OR (!X AND Z ..)
2546 into X OR (Z ...). */
2547 if (simplify_preds_3 (preds))
2548 changed = true;
2550 if (simplify_preds_4 (preds))
2551 changed = true;
2553 while (changed);
2555 return;
2558 /* This is a helper function which attempts to normalize predicate chains
2559 by following UD chains. It basically builds up a big tree of either IOR
2560 operations or AND operations, and convert the IOR tree into a
2561 pred_chain_union or BIT_AND tree into a pred_chain.
2562 Example:
2564 _3 = _2 RELOP1 _1;
2565 _6 = _5 RELOP2 _4;
2566 _9 = _8 RELOP3 _7;
2567 _10 = _3 | _6;
2568 _12 = _9 | _0;
2569 _t = _10 | _12;
2571 then _t != 0 will be normalized into a pred_chain_union
2573 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
2575 Similarly given,
2577 _3 = _2 RELOP1 _1;
2578 _6 = _5 RELOP2 _4;
2579 _9 = _8 RELOP3 _7;
2580 _10 = _3 & _6;
2581 _12 = _9 & _0;
2583 then _t != 0 will be normalized into a pred_chain:
2584 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
2588 /* This is a helper function that stores a PRED into NORM_PREDS. */
2590 inline static void
2591 push_pred (pred_chain_union *norm_preds, pred_info pred)
2593 pred_chain pred_chain = vNULL;
2594 pred_chain.safe_push (pred);
2595 norm_preds->safe_push (pred_chain);
2598 /* A helper function that creates a predicate of the form
2599 OP != 0 and push it WORK_LIST. */
2601 inline static void
2602 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
2603 hash_set<tree> *mark_set)
2605 if (mark_set->contains (op))
2606 return;
2607 mark_set->add (op);
2609 pred_info arg_pred;
2610 arg_pred.pred_lhs = op;
2611 arg_pred.pred_rhs = integer_zero_node;
2612 arg_pred.cond_code = NE_EXPR;
2613 arg_pred.invert = false;
2614 work_list->safe_push (arg_pred);
2617 /* A helper that generates a pred_info from a gimple assignment
2618 CMP_ASSIGN with comparison rhs. */
2620 static pred_info
2621 get_pred_info_from_cmp (gimple *cmp_assign)
2623 pred_info n_pred;
2624 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
2625 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
2626 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
2627 n_pred.invert = false;
2628 return n_pred;
2631 /* Returns true if the PHI is a degenerated phi with
2632 all args with the same value (relop). In that case, *PRED
2633 will be updated to that value. */
2635 static bool
2636 is_degenerated_phi (gimple *phi, pred_info *pred_p)
2638 int i, n;
2639 tree op0;
2640 gimple *def0;
2641 pred_info pred0;
2643 n = gimple_phi_num_args (phi);
2644 op0 = gimple_phi_arg_def (phi, 0);
2646 if (TREE_CODE (op0) != SSA_NAME)
2647 return false;
2649 def0 = SSA_NAME_DEF_STMT (op0);
2650 if (gimple_code (def0) != GIMPLE_ASSIGN)
2651 return false;
2652 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
2653 return false;
2654 pred0 = get_pred_info_from_cmp (def0);
2656 for (i = 1; i < n; ++i)
2658 gimple *def;
2659 pred_info pred;
2660 tree op = gimple_phi_arg_def (phi, i);
2662 if (TREE_CODE (op) != SSA_NAME)
2663 return false;
2665 def = SSA_NAME_DEF_STMT (op);
2666 if (gimple_code (def) != GIMPLE_ASSIGN)
2667 return false;
2668 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
2669 return false;
2670 pred = get_pred_info_from_cmp (def);
2671 if (!pred_equal_p (pred, pred0))
2672 return false;
2675 *pred_p = pred0;
2676 return true;
2679 /* Normalize one predicate PRED
2680 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2681 2) otherwise if PRED is of the form x != 0, follow x's definition
2682 and put normalized predicates into WORK_LIST. */
2684 static void
2685 normalize_one_pred_1 (pred_chain_union *norm_preds,
2686 pred_chain *norm_chain,
2687 pred_info pred,
2688 enum tree_code and_or_code,
2689 vec<pred_info, va_heap, vl_ptr> *work_list,
2690 hash_set<tree> *mark_set)
2692 if (!is_neq_zero_form_p (pred))
2694 if (and_or_code == BIT_IOR_EXPR)
2695 push_pred (norm_preds, pred);
2696 else
2697 norm_chain->safe_push (pred);
2698 return;
2701 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2703 if (gimple_code (def_stmt) == GIMPLE_PHI
2704 && is_degenerated_phi (def_stmt, &pred))
2705 work_list->safe_push (pred);
2706 else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
2708 int i, n;
2709 n = gimple_phi_num_args (def_stmt);
2711 /* If we see non zero constant, we should punt. The predicate
2712 * should be one guarding the phi edge. */
2713 for (i = 0; i < n; ++i)
2715 tree op = gimple_phi_arg_def (def_stmt, i);
2716 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
2718 push_pred (norm_preds, pred);
2719 return;
2723 for (i = 0; i < n; ++i)
2725 tree op = gimple_phi_arg_def (def_stmt, i);
2726 if (integer_zerop (op))
2727 continue;
2729 push_to_worklist (op, work_list, mark_set);
2732 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2734 if (and_or_code == BIT_IOR_EXPR)
2735 push_pred (norm_preds, pred);
2736 else
2737 norm_chain->safe_push (pred);
2739 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
2741 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2742 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
2744 /* But treat x & 3 as condition. */
2745 if (and_or_code == BIT_AND_EXPR)
2747 pred_info n_pred;
2748 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
2749 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
2750 n_pred.cond_code = and_or_code;
2751 n_pred.invert = false;
2752 norm_chain->safe_push (n_pred);
2755 else
2757 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
2758 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
2761 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
2762 == tcc_comparison)
2764 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2765 if (and_or_code == BIT_IOR_EXPR)
2766 push_pred (norm_preds, n_pred);
2767 else
2768 norm_chain->safe_push (n_pred);
2770 else
2772 if (and_or_code == BIT_IOR_EXPR)
2773 push_pred (norm_preds, pred);
2774 else
2775 norm_chain->safe_push (pred);
2779 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2781 static void
2782 normalize_one_pred (pred_chain_union *norm_preds, pred_info pred)
2784 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2785 enum tree_code and_or_code = ERROR_MARK;
2786 pred_chain norm_chain = vNULL;
2788 if (!is_neq_zero_form_p (pred))
2790 push_pred (norm_preds, pred);
2791 return;
2794 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2795 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2796 and_or_code = gimple_assign_rhs_code (def_stmt);
2797 if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
2799 if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
2801 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2802 push_pred (norm_preds, n_pred);
2804 else
2805 push_pred (norm_preds, pred);
2806 return;
2809 work_list.safe_push (pred);
2810 hash_set<tree> mark_set;
2812 while (!work_list.is_empty ())
2814 pred_info a_pred = work_list.pop ();
2815 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code,
2816 &work_list, &mark_set);
2818 if (and_or_code == BIT_AND_EXPR)
2819 norm_preds->safe_push (norm_chain);
2821 work_list.release ();
2824 static void
2825 normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain)
2827 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2828 hash_set<tree> mark_set;
2829 pred_chain norm_chain = vNULL;
2830 size_t i;
2832 for (i = 0; i < one_chain.length (); i++)
2834 work_list.safe_push (one_chain[i]);
2835 mark_set.add (one_chain[i].pred_lhs);
2838 while (!work_list.is_empty ())
2840 pred_info a_pred = work_list.pop ();
2841 normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list,
2842 &mark_set);
2845 norm_preds->safe_push (norm_chain);
2846 work_list.release ();
2849 /* Normalize predicate chains PREDS and returns the normalized one. */
2851 static pred_chain_union
2852 normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
2854 pred_chain_union norm_preds = vNULL;
2855 size_t n = preds.length ();
2856 size_t i;
2858 if (dump_file && dump_flags & TDF_DETAILS)
2860 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2861 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2864 for (i = 0; i < n; i++)
2866 if (preds[i].length () != 1)
2867 normalize_one_pred_chain (&norm_preds, preds[i]);
2868 else
2870 normalize_one_pred (&norm_preds, preds[i][0]);
2871 preds[i].release ();
2875 if (dump_file)
2877 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2878 dump_predicates (use_or_def, norm_preds,
2879 is_use ? "[USE]:\n" : "[DEF]:\n");
2882 destroy_predicate_vecs (&preds);
2883 return norm_preds;
2886 /* Return TRUE if PREDICATE can be invalidated by any individual
2887 predicate in USE_GUARD. */
2889 static bool
2890 can_one_predicate_be_invalidated_p (pred_info predicate,
2891 pred_chain use_guard)
2893 if (dump_file && dump_flags & TDF_DETAILS)
2895 fprintf (dump_file, "Testing if this predicate: ");
2896 dump_pred_info (predicate);
2897 fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
2898 dump_pred_chain (use_guard);
2900 for (size_t i = 0; i < use_guard.length (); ++i)
2902 /* NOTE: This is a very simple check, and only understands an
2903 exact opposite. So, [i == 0] is currently only invalidated
2904 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2905 invalidate with say [i > 5] or [i == 8]. There is certainly
2906 room for improvement here. */
2907 if (pred_neg_p (predicate, use_guard[i]))
2909 if (dump_file && dump_flags & TDF_DETAILS)
2911 fprintf (dump_file, " Predicate was invalidated by: ");
2912 dump_pred_info (use_guard[i]);
2913 fputc ('\n', dump_file);
2915 return true;
2918 return false;
2921 /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2922 USE_GUARD being true. */
2924 static bool
2925 can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
2926 pred_chain use_guard)
2928 if (uninit_pred.is_empty ())
2929 return false;
2930 if (dump_file && dump_flags & TDF_DETAILS)
2931 dump_predicates (NULL, uninit_pred,
2932 "Testing if anything here can be invalidated: ");
2933 for (size_t i = 0; i < uninit_pred.length (); ++i)
2935 pred_chain c = uninit_pred[i];
2936 size_t j;
2937 for (j = 0; j < c.length (); ++j)
2938 if (can_one_predicate_be_invalidated_p (c[j], use_guard))
2939 break;
2941 /* If we were unable to invalidate any predicate in C, then there
2942 is a viable path from entry to the PHI where the PHI takes
2943 an uninitialized value and continues to a use of the PHI. */
2944 if (j == c.length ())
2945 return false;
2947 return true;
2950 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2951 can actually happen if we arrived at a use for PHI.
2953 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2955 static bool
2956 uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
2957 pred_chain_union phi_use_guards)
2959 unsigned phi_args = gimple_phi_num_args (phi);
2960 if (phi_args > max_phi_args)
2961 return false;
2963 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2964 possible guard, there's no way of knowing which guard was true.
2965 Since we need to be absolutely sure that the uninitialized
2966 operands will be invalidated, bail. */
2967 if (phi_use_guards.length () != 1)
2968 return false;
2970 /* Look for the control dependencies of all the uninitialized
2971 operands and build guard predicates describing them. */
2972 pred_chain_union uninit_preds;
2973 bool ret = true;
2974 for (unsigned i = 0; i < phi_args; ++i)
2976 if (!MASK_TEST_BIT (uninit_opnds, i))
2977 continue;
2979 edge e = gimple_phi_arg_edge (phi, i);
2980 vec<edge> dep_chains[MAX_NUM_CHAINS];
2981 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
2982 size_t num_chains = 0;
2983 int num_calls = 0;
2985 /* Build the control dependency chain for uninit operand `i'... */
2986 uninit_preds = vNULL;
2987 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
2988 e->src, dep_chains, &num_chains,
2989 &cur_chain, &num_calls))
2991 ret = false;
2992 break;
2994 /* ...and convert it into a set of predicates. */
2995 bool has_valid_preds
2996 = convert_control_dep_chain_into_preds (dep_chains, num_chains,
2997 &uninit_preds);
2998 for (size_t j = 0; j < num_chains; ++j)
2999 dep_chains[j].release ();
3000 if (!has_valid_preds)
3002 ret = false;
3003 break;
3005 simplify_preds (&uninit_preds, NULL, false);
3006 uninit_preds = normalize_preds (uninit_preds, NULL, false);
3008 /* Can the guard for this uninitialized operand be invalidated
3009 by the PHI use? */
3010 if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0]))
3012 ret = false;
3013 break;
3016 destroy_predicate_vecs (&uninit_preds);
3017 return ret;
3020 /* Computes the predicates that guard the use and checks
3021 if the incoming paths that have empty (or possibly
3022 empty) definition can be pruned/filtered. The function returns
3023 true if it can be determined that the use of PHI's def in
3024 USE_STMT is guarded with a predicate set not overlapping with
3025 predicate sets of all runtime paths that do not have a definition.
3027 Returns false if it is not or it cannot be determined. USE_BB is
3028 the bb of the use (for phi operand use, the bb is not the bb of
3029 the phi stmt, but the src bb of the operand edge).
3031 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
3032 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
3033 set of phis being visited.
3035 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
3036 If *DEF_PREDS is the empty vector, the defining predicate chains of
3037 PHI will be computed and stored into *DEF_PREDS as needed.
3039 VISITED_PHIS is a pointer set of phis being visited. */
3041 static bool
3042 is_use_properly_guarded (gimple *use_stmt,
3043 basic_block use_bb,
3044 gphi *phi,
3045 unsigned uninit_opnds,
3046 pred_chain_union *def_preds,
3047 hash_set<gphi *> *visited_phis)
3049 basic_block phi_bb;
3050 pred_chain_union preds = vNULL;
3051 bool has_valid_preds = false;
3052 bool is_properly_guarded = false;
3054 if (visited_phis->add (phi))
3055 return false;
3057 phi_bb = gimple_bb (phi);
3059 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
3060 return false;
3062 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
3064 if (!has_valid_preds)
3066 destroy_predicate_vecs (&preds);
3067 return false;
3070 /* Try to prune the dead incoming phi edges. */
3071 is_properly_guarded
3072 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
3073 visited_phis);
3075 /* We might be able to prove that if the control dependencies
3076 for UNINIT_OPNDS are true, that the control dependencies for
3077 USE_STMT can never be true. */
3078 if (!is_properly_guarded)
3079 is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds,
3080 preds);
3082 if (is_properly_guarded)
3084 destroy_predicate_vecs (&preds);
3085 return true;
3088 if (def_preds->is_empty ())
3090 has_valid_preds = find_def_preds (def_preds, phi);
3092 if (!has_valid_preds)
3094 destroy_predicate_vecs (&preds);
3095 return false;
3098 simplify_preds (def_preds, phi, false);
3099 *def_preds = normalize_preds (*def_preds, phi, false);
3102 simplify_preds (&preds, use_stmt, true);
3103 preds = normalize_preds (preds, use_stmt, true);
3105 is_properly_guarded = is_superset_of (*def_preds, preds);
3107 destroy_predicate_vecs (&preds);
3108 return is_properly_guarded;
3111 /* Searches through all uses of a potentially
3112 uninitialized variable defined by PHI and returns a use
3113 statement if the use is not properly guarded. It returns
3114 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
3115 holding the position(s) of uninit PHI operands. WORKLIST
3116 is the vector of candidate phis that may be updated by this
3117 function. ADDED_TO_WORKLIST is the pointer set tracking
3118 if the new phi is already in the worklist. */
3120 static gimple *
3121 find_uninit_use (gphi *phi, unsigned uninit_opnds,
3122 vec<gphi *> *worklist,
3123 hash_set<gphi *> *added_to_worklist)
3125 tree phi_result;
3126 use_operand_p use_p;
3127 gimple *use_stmt;
3128 imm_use_iterator iter;
3129 pred_chain_union def_preds = vNULL;
3130 gimple *ret = NULL;
3132 phi_result = gimple_phi_result (phi);
3134 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
3136 basic_block use_bb;
3138 use_stmt = USE_STMT (use_p);
3139 if (is_gimple_debug (use_stmt))
3140 continue;
3142 if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
3143 use_bb = gimple_phi_arg_edge (use_phi,
3144 PHI_ARG_INDEX_FROM_USE (use_p))->src;
3145 else
3146 use_bb = gimple_bb (use_stmt);
3148 hash_set<gphi *> visited_phis;
3149 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
3150 &def_preds, &visited_phis))
3151 continue;
3153 if (dump_file && (dump_flags & TDF_DETAILS))
3155 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
3156 print_gimple_stmt (dump_file, use_stmt, 0);
3158 /* Found one real use, return. */
3159 if (gimple_code (use_stmt) != GIMPLE_PHI)
3161 ret = use_stmt;
3162 break;
3165 /* Found a phi use that is not guarded,
3166 add the phi to the worklist. */
3167 if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
3169 if (dump_file && (dump_flags & TDF_DETAILS))
3171 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
3172 print_gimple_stmt (dump_file, use_stmt, 0);
3175 worklist->safe_push (as_a<gphi *> (use_stmt));
3176 possibly_undefined_names->add (phi_result);
3180 destroy_predicate_vecs (&def_preds);
3181 return ret;
3184 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
3185 and gives warning if there exists a runtime path from the entry to a
3186 use of the PHI def that does not contain a definition. In other words,
3187 the warning is on the real use. The more dead paths that can be pruned
3188 by the compiler, the fewer false positives the warning is. WORKLIST
3189 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
3190 a pointer set tracking if the new phi is added to the worklist or not. */
3192 static void
3193 warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
3194 hash_set<gphi *> *added_to_worklist)
3196 unsigned uninit_opnds;
3197 gimple *uninit_use_stmt = 0;
3198 tree uninit_op;
3199 int phiarg_index;
3200 location_t loc;
3202 /* Don't look at virtual operands. */
3203 if (virtual_operand_p (gimple_phi_result (phi)))
3204 return;
3206 uninit_opnds = compute_uninit_opnds_pos (phi);
3208 if (MASK_EMPTY (uninit_opnds))
3209 return;
3211 if (dump_file && (dump_flags & TDF_DETAILS))
3213 fprintf (dump_file, "[CHECK]: examining phi: ");
3214 print_gimple_stmt (dump_file, phi, 0);
3217 /* Now check if we have any use of the value without proper guard. */
3218 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
3219 worklist, added_to_worklist);
3221 /* All uses are properly guarded. */
3222 if (!uninit_use_stmt)
3223 return;
3225 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
3226 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
3227 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
3228 return;
3229 if (gimple_phi_arg_has_location (phi, phiarg_index))
3230 loc = gimple_phi_arg_location (phi, phiarg_index);
3231 else
3232 loc = UNKNOWN_LOCATION;
3233 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
3234 SSA_NAME_VAR (uninit_op),
3235 "%qD may be used uninitialized in this function",
3236 uninit_use_stmt, loc);
3239 static bool
3240 gate_warn_uninitialized (void)
3242 return warn_uninitialized || warn_maybe_uninitialized;
3245 namespace {
3247 const pass_data pass_data_late_warn_uninitialized =
3249 GIMPLE_PASS, /* type */
3250 "uninit", /* name */
3251 OPTGROUP_NONE, /* optinfo_flags */
3252 TV_NONE, /* tv_id */
3253 PROP_ssa, /* properties_required */
3254 0, /* properties_provided */
3255 0, /* properties_destroyed */
3256 0, /* todo_flags_start */
3257 0, /* todo_flags_finish */
3260 class pass_late_warn_uninitialized : public gimple_opt_pass
3262 public:
3263 pass_late_warn_uninitialized (gcc::context *ctxt)
3264 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
3267 /* opt_pass methods: */
3268 opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); }
3269 virtual bool gate (function *) { return gate_warn_uninitialized (); }
3270 virtual unsigned int execute (function *);
3272 }; // class pass_late_warn_uninitialized
3274 unsigned int
3275 pass_late_warn_uninitialized::execute (function *fun)
3277 basic_block bb;
3278 gphi_iterator gsi;
3279 vec<gphi *> worklist = vNULL;
3281 calculate_dominance_info (CDI_DOMINATORS);
3282 calculate_dominance_info (CDI_POST_DOMINATORS);
3283 /* Re-do the plain uninitialized variable check, as optimization may have
3284 straightened control flow. Do this first so that we don't accidentally
3285 get a "may be" warning when we'd have seen an "is" warning later. */
3286 warn_uninitialized_vars (/*warn_maybe_uninitialized=*/1);
3288 timevar_push (TV_TREE_UNINIT);
3290 possibly_undefined_names = new hash_set<tree>;
3291 hash_set<gphi *> added_to_worklist;
3293 /* Initialize worklist */
3294 FOR_EACH_BB_FN (bb, fun)
3295 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3297 gphi *phi = gsi.phi ();
3298 size_t n, i;
3300 n = gimple_phi_num_args (phi);
3302 /* Don't look at virtual operands. */
3303 if (virtual_operand_p (gimple_phi_result (phi)))
3304 continue;
3306 for (i = 0; i < n; ++i)
3308 tree op = gimple_phi_arg_def (phi, i);
3309 if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
3311 worklist.safe_push (phi);
3312 added_to_worklist.add (phi);
3313 if (dump_file && (dump_flags & TDF_DETAILS))
3315 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
3316 print_gimple_stmt (dump_file, phi, 0);
3318 break;
3323 while (worklist.length () != 0)
3325 gphi *cur_phi = 0;
3326 cur_phi = worklist.pop ();
3327 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
3330 worklist.release ();
3331 delete possibly_undefined_names;
3332 possibly_undefined_names = NULL;
3333 free_dominance_info (CDI_POST_DOMINATORS);
3334 timevar_pop (TV_TREE_UNINIT);
3335 return 0;
3338 } // anon namespace
3340 gimple_opt_pass *
3341 make_pass_late_warn_uninitialized (gcc::context *ctxt)
3343 return new pass_late_warn_uninitialized (ctxt);
3346 static unsigned int
3347 execute_early_warn_uninitialized (void)
3349 /* Currently, this pass runs always but
3350 execute_late_warn_uninitialized only runs with optimization. With
3351 optimization we want to warn about possible uninitialized as late
3352 as possible, thus don't do it here. However, without
3353 optimization we need to warn here about "may be uninitialized". */
3354 calculate_dominance_info (CDI_DOMINATORS);
3355 calculate_dominance_info (CDI_POST_DOMINATORS);
3357 warn_uninitialized_vars (/*warn_maybe_uninitialized=*/!optimize);
3359 /* Post-dominator information cannot be reliably updated. Free it
3360 after the use. */
3362 free_dominance_info (CDI_POST_DOMINATORS);
3363 return 0;
3366 namespace {
3368 const pass_data pass_data_early_warn_uninitialized =
3370 GIMPLE_PASS, /* type */
3371 "*early_warn_uninitialized", /* name */
3372 OPTGROUP_NONE, /* optinfo_flags */
3373 TV_TREE_UNINIT, /* tv_id */
3374 PROP_ssa, /* properties_required */
3375 0, /* properties_provided */
3376 0, /* properties_destroyed */
3377 0, /* todo_flags_start */
3378 0, /* todo_flags_finish */
3381 class pass_early_warn_uninitialized : public gimple_opt_pass
3383 public:
3384 pass_early_warn_uninitialized (gcc::context *ctxt)
3385 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
3388 /* opt_pass methods: */
3389 virtual bool gate (function *) { return gate_warn_uninitialized (); }
3390 virtual unsigned int execute (function *)
3392 return execute_early_warn_uninitialized ();
3395 }; // class pass_early_warn_uninitialized
3397 } // anon namespace
3399 gimple_opt_pass *
3400 make_pass_early_warn_uninitialized (gcc::context *ctxt)
3402 return new pass_early_warn_uninitialized (ctxt);