Daily bump.
[official-gcc.git] / gcc / tree-ssa-uninit.c
blob8ccbc85970a412552571a1ba65f15bd12cb00036
1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2018 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 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "tree-pass.h"
28 #include "ssa.h"
29 #include "gimple-pretty-print.h"
30 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "gimple-iterator.h"
33 #include "tree-ssa.h"
34 #include "params.h"
35 #include "tree-cfg.h"
36 #include "cfghooks.h"
38 /* This implements the pass that does predicate aware warning on uses of
39 possibly uninitialized variables. The pass first collects the set of
40 possibly uninitialized SSA names. For each such name, it walks through
41 all its immediate uses. For each immediate use, it rebuilds the condition
42 expression (the predicate) that guards the use. The predicate is then
43 examined to see if the variable is always defined under that same condition.
44 This is done either by pruning the unrealizable paths that lead to the
45 default definitions or by checking if the predicate set that guards the
46 defining paths is a superset of the use predicate. */
48 /* Max PHI args we can handle in pass. */
49 const unsigned max_phi_args = 32;
51 /* Pointer set of potentially undefined ssa names, i.e.,
52 ssa names that are defined by phi with operands that
53 are not defined or potentially undefined. */
54 static hash_set<tree> *possibly_undefined_names = 0;
56 /* Bit mask handling macros. */
57 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
58 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
59 #define MASK_EMPTY(mask) (mask == 0)
61 /* Returns the first bit position (starting from LSB)
62 in mask that is non zero. Returns -1 if the mask is empty. */
63 static int
64 get_mask_first_set_bit (unsigned mask)
66 int pos = 0;
67 if (mask == 0)
68 return -1;
70 while ((mask & (1 << pos)) == 0)
71 pos++;
73 return pos;
75 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
77 /* Return true if T, an SSA_NAME, has an undefined value. */
78 static bool
79 has_undefined_value_p (tree t)
81 return (ssa_undefined_value_p (t)
82 || (possibly_undefined_names
83 && possibly_undefined_names->contains (t)));
86 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
87 is set on SSA_NAME_VAR. */
89 static inline bool
90 uninit_undefined_value_p (tree t)
92 if (!has_undefined_value_p (t))
93 return false;
94 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
95 return false;
96 return true;
99 /* Emit warnings for uninitialized variables. This is done in two passes.
101 The first pass notices real uses of SSA names with undefined values.
102 Such uses are unconditionally uninitialized, and we can be certain that
103 such a use is a mistake. This pass is run before most optimizations,
104 so that we catch as many as we can.
106 The second pass follows PHI nodes to find uses that are potentially
107 uninitialized. In this case we can't necessarily prove that the use
108 is really uninitialized. This pass is run after most optimizations,
109 so that we thread as many jumps and possible, and delete as much dead
110 code as possible, in order to reduce false positives. We also look
111 again for plain uninitialized variables, since optimization may have
112 changed conditionally uninitialized to unconditionally uninitialized. */
114 /* Emit a warning for EXPR based on variable VAR at the point in the
115 program T, an SSA_NAME, is used being uninitialized. The exact
116 warning text is in MSGID and DATA is the gimple stmt with info about
117 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
118 gives which argument of the phi node to take the location from. WC
119 is the warning code. */
121 static void
122 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
123 const char *gmsgid, void *data, location_t phiarg_loc)
125 gimple *context = (gimple *) data;
126 location_t location, cfun_loc;
127 expanded_location xloc, floc;
129 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
130 turns in a COMPLEX_EXPR with the not initialized part being
131 set to its previous (undefined) value. */
132 if (is_gimple_assign (context)
133 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
134 return;
135 if (!has_undefined_value_p (t))
136 return;
138 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
139 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
140 created for conversion from scalar to complex. Use the underlying var of
141 the COMPLEX_EXPRs real part in that case. See PR71581. */
142 if (expr == NULL_TREE
143 && var == NULL_TREE
144 && SSA_NAME_VAR (t) == NULL_TREE
145 && is_gimple_assign (SSA_NAME_DEF_STMT (t))
146 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t)) == COMPLEX_EXPR)
148 tree v = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
149 if (TREE_CODE (v) == SSA_NAME
150 && has_undefined_value_p (v)
151 && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t))))
153 expr = SSA_NAME_VAR (v);
154 var = expr;
158 if (expr == NULL_TREE)
159 return;
161 /* TREE_NO_WARNING either means we already warned, or the front end
162 wishes to suppress the warning. */
163 if ((context
164 && (gimple_no_warning_p (context)
165 || (gimple_assign_single_p (context)
166 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
167 || TREE_NO_WARNING (expr))
168 return;
170 if (context != NULL && gimple_has_location (context))
171 location = gimple_location (context);
172 else if (phiarg_loc != UNKNOWN_LOCATION)
173 location = phiarg_loc;
174 else
175 location = DECL_SOURCE_LOCATION (var);
176 location = linemap_resolve_location (line_table, location,
177 LRK_SPELLING_LOCATION, NULL);
178 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
179 xloc = expand_location (location);
180 floc = expand_location (cfun_loc);
181 if (warning_at (location, wc, gmsgid, expr))
183 TREE_NO_WARNING (expr) = 1;
185 if (location == DECL_SOURCE_LOCATION (var))
186 return;
187 if (xloc.file != floc.file
188 || linemap_location_before_p (line_table, location, cfun_loc)
189 || linemap_location_before_p (line_table, cfun->function_end_locus,
190 location))
191 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
195 struct check_defs_data
197 /* If we found any may-defs besides must-def clobbers. */
198 bool found_may_defs;
201 /* Callback for walk_aliased_vdefs. */
203 static bool
204 check_defs (ao_ref *ref, tree vdef, void *data_)
206 check_defs_data *data = (check_defs_data *)data_;
207 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
208 /* If this is a clobber then if it is not a kill walk past it. */
209 if (gimple_clobber_p (def_stmt))
211 if (stmt_kills_ref_p (def_stmt, ref))
212 return true;
213 return false;
215 /* Found a may-def on this path. */
216 data->found_may_defs = true;
217 return true;
220 static unsigned int
221 warn_uninitialized_vars (bool warn_possibly_uninitialized)
223 gimple_stmt_iterator gsi;
224 basic_block bb;
225 unsigned int vdef_cnt = 0;
226 unsigned int oracle_cnt = 0;
227 unsigned limit = 0;
229 FOR_EACH_BB_FN (bb, cfun)
231 basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
232 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS, succ, bb);
233 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
235 gimple *stmt = gsi_stmt (gsi);
236 use_operand_p use_p;
237 ssa_op_iter op_iter;
238 tree use;
240 if (is_gimple_debug (stmt))
241 continue;
243 /* We only do data flow with SSA_NAMEs, so that's all we
244 can warn about. */
245 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
247 /* BIT_INSERT_EXPR first operand should not be considered
248 a use for the purpose of uninit warnings. */
249 if (gassign *ass = dyn_cast <gassign *> (stmt))
251 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
252 && use_p->use == gimple_assign_rhs1_ptr (ass))
253 continue;
255 use = USE_FROM_PTR (use_p);
256 if (always_executed)
257 warn_uninit (OPT_Wuninitialized, use, SSA_NAME_VAR (use),
258 SSA_NAME_VAR (use),
259 "%qD is used uninitialized in this function", stmt,
260 UNKNOWN_LOCATION);
261 else if (warn_possibly_uninitialized)
262 warn_uninit (OPT_Wmaybe_uninitialized, use, SSA_NAME_VAR (use),
263 SSA_NAME_VAR (use),
264 "%qD may be used uninitialized in this function",
265 stmt, UNKNOWN_LOCATION);
268 /* For limiting the alias walk below we count all
269 vdefs in the function. */
270 if (gimple_vdef (stmt))
271 vdef_cnt++;
273 if (gimple_assign_load_p (stmt)
274 && gimple_has_location (stmt))
276 tree rhs = gimple_assign_rhs1 (stmt);
277 tree lhs = gimple_assign_lhs (stmt);
278 bool has_bit_insert = false;
279 use_operand_p luse_p;
280 imm_use_iterator liter;
282 if (TREE_NO_WARNING (rhs))
283 continue;
285 ao_ref ref;
286 ao_ref_init (&ref, rhs);
288 /* Do not warn if the base was marked so or this is a
289 hard register var. */
290 tree base = ao_ref_base (&ref);
291 if ((VAR_P (base)
292 && DECL_HARD_REGISTER (base))
293 || TREE_NO_WARNING (base))
294 continue;
296 /* Do not warn if the access is fully outside of the
297 variable. */
298 poly_int64 decl_size;
299 if (DECL_P (base)
300 && known_size_p (ref.size)
301 && ((known_eq (ref.max_size, ref.size)
302 && known_le (ref.offset + ref.size, 0))
303 || (known_ge (ref.offset, 0)
304 && DECL_SIZE (base)
305 && poly_int_tree_p (DECL_SIZE (base), &decl_size)
306 && known_le (decl_size, ref.offset))))
307 continue;
309 /* Do not warn if the access is then used for a BIT_INSERT_EXPR. */
310 if (TREE_CODE (lhs) == SSA_NAME)
311 FOR_EACH_IMM_USE_FAST (luse_p, liter, lhs)
313 gimple *use_stmt = USE_STMT (luse_p);
314 /* BIT_INSERT_EXPR first operand should not be considered
315 a use for the purpose of uninit warnings. */
316 if (gassign *ass = dyn_cast <gassign *> (use_stmt))
318 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
319 && luse_p->use == gimple_assign_rhs1_ptr (ass))
321 has_bit_insert = true;
322 break;
326 if (has_bit_insert)
327 continue;
329 /* Limit the walking to a constant number of stmts after
330 we overcommit quadratic behavior for small functions
331 and O(n) behavior. */
332 if (oracle_cnt > 128 * 128
333 && oracle_cnt > vdef_cnt * 2)
334 limit = 32;
335 check_defs_data data;
336 bool fentry_reached = false;
337 data.found_may_defs = false;
338 use = gimple_vuse (stmt);
339 int res = walk_aliased_vdefs (&ref, use,
340 check_defs, &data, NULL,
341 &fentry_reached, limit);
342 if (res == -1)
344 oracle_cnt += limit;
345 continue;
347 oracle_cnt += res;
348 if (data.found_may_defs)
349 continue;
350 /* Do not warn if it can be initialized outside this function.
351 If we did not reach function entry then we found killing
352 clobbers on all paths to entry. */
353 if (fentry_reached
354 /* ??? We'd like to use ref_may_alias_global_p but that
355 excludes global readonly memory and thus we get bougs
356 warnings from p = cond ? "a" : "b" for example. */
357 && (!VAR_P (base)
358 || is_global_var (base)))
359 continue;
361 /* We didn't find any may-defs so on all paths either
362 reached function entry or a killing clobber. */
363 location_t location
364 = linemap_resolve_location (line_table, gimple_location (stmt),
365 LRK_SPELLING_LOCATION, NULL);
366 if (always_executed)
368 if (warning_at (location, OPT_Wuninitialized,
369 "%qE is used uninitialized in this function",
370 rhs))
371 /* ??? This is only effective for decls as in
372 gcc.dg/uninit-B-O0.c. Avoid doing this for
373 maybe-uninit uses as it may hide important
374 locations. */
375 TREE_NO_WARNING (rhs) = 1;
377 else if (warn_possibly_uninitialized)
378 warning_at (location, OPT_Wmaybe_uninitialized,
379 "%qE may be used uninitialized in this function",
380 rhs);
385 return 0;
388 /* Checks if the operand OPND of PHI is defined by
389 another phi with one operand defined by this PHI,
390 but the rest operands are all defined. If yes,
391 returns true to skip this operand as being
392 redundant. Can be enhanced to be more general. */
394 static bool
395 can_skip_redundant_opnd (tree opnd, gimple *phi)
397 gimple *op_def;
398 tree phi_def;
399 int i, n;
401 phi_def = gimple_phi_result (phi);
402 op_def = SSA_NAME_DEF_STMT (opnd);
403 if (gimple_code (op_def) != GIMPLE_PHI)
404 return false;
405 n = gimple_phi_num_args (op_def);
406 for (i = 0; i < n; ++i)
408 tree op = gimple_phi_arg_def (op_def, i);
409 if (TREE_CODE (op) != SSA_NAME)
410 continue;
411 if (op != phi_def && uninit_undefined_value_p (op))
412 return false;
415 return true;
418 /* Returns a bit mask holding the positions of arguments in PHI
419 that have empty (or possibly empty) definitions. */
421 static unsigned
422 compute_uninit_opnds_pos (gphi *phi)
424 size_t i, n;
425 unsigned uninit_opnds = 0;
427 n = gimple_phi_num_args (phi);
428 /* Bail out for phi with too many args. */
429 if (n > max_phi_args)
430 return 0;
432 for (i = 0; i < n; ++i)
434 tree op = gimple_phi_arg_def (phi, i);
435 if (TREE_CODE (op) == SSA_NAME
436 && uninit_undefined_value_p (op)
437 && !can_skip_redundant_opnd (op, phi))
439 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
441 /* Ignore SSA_NAMEs that appear on abnormal edges
442 somewhere. */
443 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
444 continue;
446 MASK_SET_BIT (uninit_opnds, i);
449 return uninit_opnds;
452 /* Find the immediate postdominator PDOM of the specified
453 basic block BLOCK. */
455 static inline basic_block
456 find_pdom (basic_block block)
458 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
459 return EXIT_BLOCK_PTR_FOR_FN (cfun);
460 else
462 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
463 if (!bb)
464 return EXIT_BLOCK_PTR_FOR_FN (cfun);
465 return bb;
469 /* Find the immediate DOM of the specified basic block BLOCK. */
471 static inline basic_block
472 find_dom (basic_block block)
474 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
475 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
476 else
478 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
479 if (!bb)
480 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
481 return bb;
485 /* Returns true if BB1 is postdominating BB2 and BB1 is
486 not a loop exit bb. The loop exit bb check is simple and does
487 not cover all cases. */
489 static bool
490 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
492 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
493 return false;
495 if (single_pred_p (bb1) && !single_succ_p (bb2))
496 return false;
498 return true;
501 /* Find the closest postdominator of a specified BB, which is control
502 equivalent to BB. */
504 static inline basic_block
505 find_control_equiv_block (basic_block bb)
507 basic_block pdom;
509 pdom = find_pdom (bb);
511 /* Skip the postdominating bb that is also loop exit. */
512 if (!is_non_loop_exit_postdominating (pdom, bb))
513 return NULL;
515 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
516 return pdom;
518 return NULL;
521 #define MAX_NUM_CHAINS 8
522 #define MAX_CHAIN_LEN 5
523 #define MAX_POSTDOM_CHECK 8
524 #define MAX_SWITCH_CASES 40
526 /* Computes the control dependence chains (paths of edges)
527 for DEP_BB up to the dominating basic block BB (the head node of a
528 chain should be dominated by it). CD_CHAINS is pointer to an
529 array holding the result chains. CUR_CD_CHAIN is the current
530 chain being computed. *NUM_CHAINS is total number of chains. The
531 function returns true if the information is successfully computed,
532 return false if there is no control dependence or not computed. */
534 static bool
535 compute_control_dep_chain (basic_block bb, basic_block dep_bb,
536 vec<edge> *cd_chains,
537 size_t *num_chains,
538 vec<edge> *cur_cd_chain,
539 int *num_calls)
541 edge_iterator ei;
542 edge e;
543 size_t i;
544 bool found_cd_chain = false;
545 size_t cur_chain_len = 0;
547 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
548 return false;
549 ++*num_calls;
551 /* Could use a set instead. */
552 cur_chain_len = cur_cd_chain->length ();
553 if (cur_chain_len > MAX_CHAIN_LEN)
554 return false;
556 for (i = 0; i < cur_chain_len; i++)
558 edge e = (*cur_cd_chain)[i];
559 /* Cycle detected. */
560 if (e->src == bb)
561 return false;
564 FOR_EACH_EDGE (e, ei, bb->succs)
566 basic_block cd_bb;
567 int post_dom_check = 0;
568 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
569 continue;
571 cd_bb = e->dest;
572 cur_cd_chain->safe_push (e);
573 while (!is_non_loop_exit_postdominating (cd_bb, bb))
575 if (cd_bb == dep_bb)
577 /* Found a direct control dependence. */
578 if (*num_chains < MAX_NUM_CHAINS)
580 cd_chains[*num_chains] = cur_cd_chain->copy ();
581 (*num_chains)++;
583 found_cd_chain = true;
584 /* Check path from next edge. */
585 break;
588 /* Now check if DEP_BB is indirectly control dependent on BB. */
589 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains,
590 cur_cd_chain, num_calls))
592 found_cd_chain = true;
593 break;
596 cd_bb = find_pdom (cd_bb);
597 post_dom_check++;
598 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
599 || post_dom_check > MAX_POSTDOM_CHECK)
600 break;
602 cur_cd_chain->pop ();
603 gcc_assert (cur_cd_chain->length () == cur_chain_len);
605 gcc_assert (cur_cd_chain->length () == cur_chain_len);
607 return found_cd_chain;
610 /* The type to represent a simple predicate. */
612 struct pred_info
614 tree pred_lhs;
615 tree pred_rhs;
616 enum tree_code cond_code;
617 bool invert;
620 /* The type to represent a sequence of predicates grouped
621 with .AND. operation. */
623 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
625 /* The type to represent a sequence of pred_chains grouped
626 with .OR. operation. */
628 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
630 /* Converts the chains of control dependence edges into a set of
631 predicates. A control dependence chain is represented by a vector
632 edges. DEP_CHAINS points to an array of dependence chains.
633 NUM_CHAINS is the size of the chain array. One edge in a dependence
634 chain is mapped to predicate expression represented by pred_info
635 type. One dependence chain is converted to a composite predicate that
636 is the result of AND operation of pred_info mapped to each edge.
637 A composite predicate is presented by a vector of pred_info. On
638 return, *PREDS points to the resulting array of composite predicates.
639 *NUM_PREDS is the number of composite predictes. */
641 static bool
642 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
643 size_t num_chains,
644 pred_chain_union *preds)
646 bool has_valid_pred = false;
647 size_t i, j;
648 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
649 return false;
651 /* Now convert the control dep chain into a set
652 of predicates. */
653 preds->reserve (num_chains);
655 for (i = 0; i < num_chains; i++)
657 vec<edge> one_cd_chain = dep_chains[i];
659 has_valid_pred = false;
660 pred_chain t_chain = vNULL;
661 for (j = 0; j < one_cd_chain.length (); j++)
663 gimple *cond_stmt;
664 gimple_stmt_iterator gsi;
665 basic_block guard_bb;
666 pred_info one_pred;
667 edge e;
669 e = one_cd_chain[j];
670 guard_bb = e->src;
671 gsi = gsi_last_bb (guard_bb);
672 /* Ignore empty forwarder blocks. */
673 if (empty_block_p (guard_bb) && single_succ_p (guard_bb))
674 continue;
675 /* An empty basic block here is likely a PHI, and is not one
676 of the cases we handle below. */
677 if (gsi_end_p (gsi))
679 has_valid_pred = false;
680 break;
682 cond_stmt = gsi_stmt (gsi);
683 if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
684 /* Ignore EH edge. Can add assertion on the other edge's flag. */
685 continue;
686 /* Skip if there is essentially one succesor. */
687 if (EDGE_COUNT (e->src->succs) == 2)
689 edge e1;
690 edge_iterator ei1;
691 bool skip = false;
693 FOR_EACH_EDGE (e1, ei1, e->src->succs)
695 if (EDGE_COUNT (e1->dest->succs) == 0)
697 skip = true;
698 break;
701 if (skip)
702 continue;
704 if (gimple_code (cond_stmt) == GIMPLE_COND)
706 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
707 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
708 one_pred.cond_code = gimple_cond_code (cond_stmt);
709 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
710 t_chain.safe_push (one_pred);
711 has_valid_pred = true;
713 else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
715 /* Avoid quadratic behavior. */
716 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
718 has_valid_pred = false;
719 break;
721 /* Find the case label. */
722 tree l = NULL_TREE;
723 unsigned idx;
724 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
726 tree tl = gimple_switch_label (gs, idx);
727 if (e->dest == label_to_block (CASE_LABEL (tl)))
729 if (!l)
730 l = tl;
731 else
733 l = NULL_TREE;
734 break;
738 /* If more than one label reaches this block or the case
739 label doesn't have a single value (like the default one)
740 fail. */
741 if (!l
742 || !CASE_LOW (l)
743 || (CASE_HIGH (l)
744 && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0)))
746 has_valid_pred = false;
747 break;
749 one_pred.pred_lhs = gimple_switch_index (gs);
750 one_pred.pred_rhs = CASE_LOW (l);
751 one_pred.cond_code = EQ_EXPR;
752 one_pred.invert = false;
753 t_chain.safe_push (one_pred);
754 has_valid_pred = true;
756 else
758 has_valid_pred = false;
759 break;
763 if (!has_valid_pred)
764 break;
765 else
766 preds->safe_push (t_chain);
768 return has_valid_pred;
771 /* Computes all control dependence chains for USE_BB. The control
772 dependence chains are then converted to an array of composite
773 predicates pointed to by PREDS. PHI_BB is the basic block of
774 the phi whose result is used in USE_BB. */
776 static bool
777 find_predicates (pred_chain_union *preds,
778 basic_block phi_bb,
779 basic_block use_bb)
781 size_t num_chains = 0, i;
782 int num_calls = 0;
783 vec<edge> dep_chains[MAX_NUM_CHAINS];
784 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
785 bool has_valid_pred = false;
786 basic_block cd_root = 0;
788 /* First find the closest bb that is control equivalent to PHI_BB
789 that also dominates USE_BB. */
790 cd_root = phi_bb;
791 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
793 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
794 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
795 cd_root = ctrl_eq_bb;
796 else
797 break;
800 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
801 &cur_chain, &num_calls);
803 has_valid_pred
804 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
805 for (i = 0; i < num_chains; i++)
806 dep_chains[i].release ();
807 return has_valid_pred;
810 /* Computes the set of incoming edges of PHI that have non empty
811 definitions of a phi chain. The collection will be done
812 recursively on operands that are defined by phis. CD_ROOT
813 is the control dependence root. *EDGES holds the result, and
814 VISITED_PHIS is a pointer set for detecting cycles. */
816 static void
817 collect_phi_def_edges (gphi *phi, basic_block cd_root,
818 auto_vec<edge> *edges,
819 hash_set<gimple *> *visited_phis)
821 size_t i, n;
822 edge opnd_edge;
823 tree opnd;
825 if (visited_phis->add (phi))
826 return;
828 n = gimple_phi_num_args (phi);
829 for (i = 0; i < n; i++)
831 opnd_edge = gimple_phi_arg_edge (phi, i);
832 opnd = gimple_phi_arg_def (phi, i);
834 if (TREE_CODE (opnd) != SSA_NAME)
836 if (dump_file && (dump_flags & TDF_DETAILS))
838 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i);
839 print_gimple_stmt (dump_file, phi, 0);
841 edges->safe_push (opnd_edge);
843 else
845 gimple *def = SSA_NAME_DEF_STMT (opnd);
847 if (gimple_code (def) == GIMPLE_PHI
848 && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
849 collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
850 visited_phis);
851 else if (!uninit_undefined_value_p (opnd))
853 if (dump_file && (dump_flags & TDF_DETAILS))
855 fprintf (dump_file, "\n[CHECK] Found def edge %d in ",
856 (int) i);
857 print_gimple_stmt (dump_file, phi, 0);
859 edges->safe_push (opnd_edge);
865 /* For each use edge of PHI, computes all control dependence chains.
866 The control dependence chains are then converted to an array of
867 composite predicates pointed to by PREDS. */
869 static bool
870 find_def_preds (pred_chain_union *preds, gphi *phi)
872 size_t num_chains = 0, i, n;
873 vec<edge> dep_chains[MAX_NUM_CHAINS];
874 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
875 auto_vec<edge> def_edges;
876 bool has_valid_pred = false;
877 basic_block phi_bb, cd_root = 0;
879 phi_bb = gimple_bb (phi);
880 /* First find the closest dominating bb to be
881 the control dependence root. */
882 cd_root = find_dom (phi_bb);
883 if (!cd_root)
884 return false;
886 hash_set<gimple *> visited_phis;
887 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
889 n = def_edges.length ();
890 if (n == 0)
891 return false;
893 for (i = 0; i < n; i++)
895 size_t prev_nc, j;
896 int num_calls = 0;
897 edge opnd_edge;
899 opnd_edge = def_edges[i];
900 prev_nc = num_chains;
901 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
902 &num_chains, &cur_chain, &num_calls);
904 /* Now update the newly added chains with
905 the phi operand edge: */
906 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
908 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
909 dep_chains[num_chains++] = vNULL;
910 for (j = prev_nc; j < num_chains; j++)
911 dep_chains[j].safe_push (opnd_edge);
915 has_valid_pred
916 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
917 for (i = 0; i < num_chains; i++)
918 dep_chains[i].release ();
919 return has_valid_pred;
922 /* Dump a pred_info. */
924 static void
925 dump_pred_info (pred_info one_pred)
927 if (one_pred.invert)
928 fprintf (dump_file, " (.NOT.) ");
929 print_generic_expr (dump_file, one_pred.pred_lhs);
930 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
931 print_generic_expr (dump_file, one_pred.pred_rhs);
934 /* Dump a pred_chain. */
936 static void
937 dump_pred_chain (pred_chain one_pred_chain)
939 size_t np = one_pred_chain.length ();
940 for (size_t j = 0; j < np; j++)
942 dump_pred_info (one_pred_chain[j]);
943 if (j < np - 1)
944 fprintf (dump_file, " (.AND.) ");
945 else
946 fprintf (dump_file, "\n");
950 /* Dumps the predicates (PREDS) for USESTMT. */
952 static void
953 dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
955 fprintf (dump_file, "%s", msg);
956 if (usestmt)
958 print_gimple_stmt (dump_file, usestmt, 0);
959 fprintf (dump_file, "is guarded by :\n\n");
961 size_t num_preds = preds.length ();
962 for (size_t i = 0; i < num_preds; i++)
964 dump_pred_chain (preds[i]);
965 if (i < num_preds - 1)
966 fprintf (dump_file, "(.OR.)\n");
967 else
968 fprintf (dump_file, "\n\n");
972 /* Destroys the predicate set *PREDS. */
974 static void
975 destroy_predicate_vecs (pred_chain_union *preds)
977 size_t i;
979 size_t n = preds->length ();
980 for (i = 0; i < n; i++)
981 (*preds)[i].release ();
982 preds->release ();
985 /* Computes the 'normalized' conditional code with operand
986 swapping and condition inversion. */
988 static enum tree_code
989 get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
991 enum tree_code tc = orig_cmp_code;
993 if (swap_cond)
994 tc = swap_tree_comparison (orig_cmp_code);
995 if (invert)
996 tc = invert_tree_comparison (tc, false);
998 switch (tc)
1000 case LT_EXPR:
1001 case LE_EXPR:
1002 case GT_EXPR:
1003 case GE_EXPR:
1004 case EQ_EXPR:
1005 case NE_EXPR:
1006 break;
1007 default:
1008 return ERROR_MARK;
1010 return tc;
1013 /* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
1014 all values in the range satisfies (x CMPC BOUNDARY) == true. */
1016 static bool
1017 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
1019 bool inverted = false;
1020 bool is_unsigned;
1021 bool result;
1023 /* Only handle integer constant here. */
1024 if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
1025 return true;
1027 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
1029 if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
1031 cmpc = invert_tree_comparison (cmpc, false);
1032 inverted = true;
1035 if (is_unsigned)
1037 if (cmpc == EQ_EXPR)
1038 result = tree_int_cst_equal (val, boundary);
1039 else if (cmpc == LT_EXPR)
1040 result = tree_int_cst_lt (val, boundary);
1041 else
1043 gcc_assert (cmpc == LE_EXPR);
1044 result = tree_int_cst_le (val, boundary);
1047 else
1049 if (cmpc == EQ_EXPR)
1050 result = tree_int_cst_equal (val, boundary);
1051 else if (cmpc == LT_EXPR)
1052 result = tree_int_cst_lt (val, boundary);
1053 else
1055 gcc_assert (cmpc == LE_EXPR);
1056 result = (tree_int_cst_equal (val, boundary)
1057 || tree_int_cst_lt (val, boundary));
1061 if (inverted)
1062 result ^= 1;
1064 return result;
1067 /* Returns true if PRED is common among all the predicate
1068 chains (PREDS) (and therefore can be factored out).
1069 NUM_PRED_CHAIN is the size of array PREDS. */
1071 static bool
1072 find_matching_predicate_in_rest_chains (pred_info pred,
1073 pred_chain_union preds,
1074 size_t num_pred_chains)
1076 size_t i, j, n;
1078 /* Trival case. */
1079 if (num_pred_chains == 1)
1080 return true;
1082 for (i = 1; i < num_pred_chains; i++)
1084 bool found = false;
1085 pred_chain one_chain = preds[i];
1086 n = one_chain.length ();
1087 for (j = 0; j < n; j++)
1089 pred_info pred2 = one_chain[j];
1090 /* Can relax the condition comparison to not
1091 use address comparison. However, the most common
1092 case is that multiple control dependent paths share
1093 a common path prefix, so address comparison should
1094 be ok. */
1096 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
1097 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
1098 && pred2.invert == pred.invert)
1100 found = true;
1101 break;
1104 if (!found)
1105 return false;
1107 return true;
1110 /* Forward declaration. */
1111 static bool is_use_properly_guarded (gimple *use_stmt,
1112 basic_block use_bb,
1113 gphi *phi,
1114 unsigned uninit_opnds,
1115 pred_chain_union *def_preds,
1116 hash_set<gphi *> *visited_phis);
1118 /* Returns true if all uninitialized opnds are pruned. Returns false
1119 otherwise. PHI is the phi node with uninitialized operands,
1120 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1121 FLAG_DEF is the statement defining the flag guarding the use of the
1122 PHI output, BOUNDARY_CST is the const value used in the predicate
1123 associated with the flag, CMP_CODE is the comparison code used in
1124 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1125 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1126 that are also phis.
1128 Example scenario:
1130 BB1:
1131 flag_1 = phi <0, 1> // (1)
1132 var_1 = phi <undef, some_val>
1135 BB2:
1136 flag_2 = phi <0, flag_1, flag_1> // (2)
1137 var_2 = phi <undef, var_1, var_1>
1138 if (flag_2 == 1)
1139 goto BB3;
1141 BB3:
1142 use of var_2 // (3)
1144 Because some flag arg in (1) is not constant, if we do not look into the
1145 flag phis recursively, it is conservatively treated as unknown and var_1
1146 is thought to be flowed into use at (3). Since var_1 is potentially
1147 uninitialized a false warning will be emitted.
1148 Checking recursively into (1), the compiler can find out that only some_val
1149 (which is defined) can flow into (3) which is OK. */
1151 static bool
1152 prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
1153 tree boundary_cst, enum tree_code cmp_code,
1154 hash_set<gphi *> *visited_phis,
1155 bitmap *visited_flag_phis)
1157 unsigned i;
1159 for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
1161 tree flag_arg;
1163 if (!MASK_TEST_BIT (uninit_opnds, i))
1164 continue;
1166 flag_arg = gimple_phi_arg_def (flag_def, i);
1167 if (!is_gimple_constant (flag_arg))
1169 gphi *flag_arg_def, *phi_arg_def;
1170 tree phi_arg;
1171 unsigned uninit_opnds_arg_phi;
1173 if (TREE_CODE (flag_arg) != SSA_NAME)
1174 return false;
1175 flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
1176 if (!flag_arg_def)
1177 return false;
1179 phi_arg = gimple_phi_arg_def (phi, i);
1180 if (TREE_CODE (phi_arg) != SSA_NAME)
1181 return false;
1183 phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1184 if (!phi_arg_def)
1185 return false;
1187 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1188 return false;
1190 if (!*visited_flag_phis)
1191 *visited_flag_phis = BITMAP_ALLOC (NULL);
1193 tree phi_result = gimple_phi_result (flag_arg_def);
1194 if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
1195 return false;
1197 bitmap_set_bit (*visited_flag_phis,
1198 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1200 /* Now recursively prune the uninitialized phi args. */
1201 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1202 if (!prune_uninit_phi_opnds
1203 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, boundary_cst,
1204 cmp_code, visited_phis, visited_flag_phis))
1205 return false;
1207 phi_result = gimple_phi_result (flag_arg_def);
1208 bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
1209 continue;
1212 /* Now check if the constant is in the guarded range. */
1213 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1215 tree opnd;
1216 gimple *opnd_def;
1218 /* Now that we know that this undefined edge is not
1219 pruned. If the operand is defined by another phi,
1220 we can further prune the incoming edges of that
1221 phi by checking the predicates of this operands. */
1223 opnd = gimple_phi_arg_def (phi, i);
1224 opnd_def = SSA_NAME_DEF_STMT (opnd);
1225 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
1227 edge opnd_edge;
1228 unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi);
1229 if (!MASK_EMPTY (uninit_opnds2))
1231 pred_chain_union def_preds = vNULL;
1232 bool ok;
1233 opnd_edge = gimple_phi_arg_edge (phi, i);
1234 ok = is_use_properly_guarded (phi,
1235 opnd_edge->src,
1236 opnd_def_phi,
1237 uninit_opnds2,
1238 &def_preds,
1239 visited_phis);
1240 destroy_predicate_vecs (&def_preds);
1241 if (!ok)
1242 return false;
1245 else
1246 return false;
1250 return true;
1253 /* A helper function that determines if the predicate set
1254 of the use is not overlapping with that of the uninit paths.
1255 The most common senario of guarded use is in Example 1:
1256 Example 1:
1257 if (some_cond)
1259 x = ...;
1260 flag = true;
1263 ... some code ...
1265 if (flag)
1266 use (x);
1268 The real world examples are usually more complicated, but similar
1269 and usually result from inlining:
1271 bool init_func (int * x)
1273 if (some_cond)
1274 return false;
1275 *x = ..
1276 return true;
1279 void foo (..)
1281 int x;
1283 if (!init_func (&x))
1284 return;
1286 .. some_code ...
1287 use (x);
1290 Another possible use scenario is in the following trivial example:
1292 Example 2:
1293 if (n > 0)
1294 x = 1;
1296 if (n > 0)
1298 if (m < 2)
1299 .. = x;
1302 Predicate analysis needs to compute the composite predicate:
1304 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1305 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1306 (the predicate chain for phi operand defs can be computed
1307 starting from a bb that is control equivalent to the phi's
1308 bb and is dominating the operand def.)
1310 and check overlapping:
1311 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1312 <==> false
1314 This implementation provides framework that can handle
1315 scenarios. (Note that many simple cases are handled properly
1316 without the predicate analysis -- this is due to jump threading
1317 transformation which eliminates the merge point thus makes
1318 path sensitive analysis unnecessary.)
1320 PHI is the phi node whose incoming (undefined) paths need to be
1321 pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
1322 positions. VISITED_PHIS is the pointer set of phi stmts being
1323 checked. */
1325 static bool
1326 use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1327 gphi *phi, unsigned uninit_opnds,
1328 hash_set<gphi *> *visited_phis)
1330 unsigned int i, n;
1331 gimple *flag_def = 0;
1332 tree boundary_cst = 0;
1333 enum tree_code cmp_code;
1334 bool swap_cond = false;
1335 bool invert = false;
1336 pred_chain the_pred_chain = vNULL;
1337 bitmap visited_flag_phis = NULL;
1338 bool all_pruned = false;
1339 size_t num_preds = preds.length ();
1341 gcc_assert (num_preds > 0);
1342 /* Find within the common prefix of multiple predicate chains
1343 a predicate that is a comparison of a flag variable against
1344 a constant. */
1345 the_pred_chain = preds[0];
1346 n = the_pred_chain.length ();
1347 for (i = 0; i < n; i++)
1349 tree cond_lhs, cond_rhs, flag = 0;
1351 pred_info the_pred = the_pred_chain[i];
1353 invert = the_pred.invert;
1354 cond_lhs = the_pred.pred_lhs;
1355 cond_rhs = the_pred.pred_rhs;
1356 cmp_code = the_pred.cond_code;
1358 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1359 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1361 boundary_cst = cond_rhs;
1362 flag = cond_lhs;
1364 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1365 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1367 boundary_cst = cond_lhs;
1368 flag = cond_rhs;
1369 swap_cond = true;
1372 if (!flag)
1373 continue;
1375 flag_def = SSA_NAME_DEF_STMT (flag);
1377 if (!flag_def)
1378 continue;
1380 if ((gimple_code (flag_def) == GIMPLE_PHI)
1381 && (gimple_bb (flag_def) == gimple_bb (phi))
1382 && find_matching_predicate_in_rest_chains (the_pred, preds,
1383 num_preds))
1384 break;
1386 flag_def = 0;
1389 if (!flag_def)
1390 return false;
1392 /* Now check all the uninit incoming edge has a constant flag value
1393 that is in conflict with the use guard/predicate. */
1394 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1396 if (cmp_code == ERROR_MARK)
1397 return false;
1399 all_pruned = prune_uninit_phi_opnds
1400 (phi, uninit_opnds, as_a<gphi *> (flag_def), boundary_cst, cmp_code,
1401 visited_phis, &visited_flag_phis);
1403 if (visited_flag_phis)
1404 BITMAP_FREE (visited_flag_phis);
1406 return all_pruned;
1409 /* The helper function returns true if two predicates X1 and X2
1410 are equivalent. It assumes the expressions have already
1411 properly re-associated. */
1413 static inline bool
1414 pred_equal_p (pred_info x1, pred_info x2)
1416 enum tree_code c1, c2;
1417 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1418 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1419 return false;
1421 c1 = x1.cond_code;
1422 if (x1.invert != x2.invert
1423 && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison)
1424 c2 = invert_tree_comparison (x2.cond_code, false);
1425 else
1426 c2 = x2.cond_code;
1428 return c1 == c2;
1431 /* Returns true if the predication is testing !=. */
1433 static inline bool
1434 is_neq_relop_p (pred_info pred)
1437 return ((pred.cond_code == NE_EXPR && !pred.invert)
1438 || (pred.cond_code == EQ_EXPR && pred.invert));
1441 /* Returns true if pred is of the form X != 0. */
1443 static inline bool
1444 is_neq_zero_form_p (pred_info pred)
1446 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1447 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1448 return false;
1449 return true;
1452 /* The helper function returns true if two predicates X1
1453 is equivalent to X2 != 0. */
1455 static inline bool
1456 pred_expr_equal_p (pred_info x1, tree x2)
1458 if (!is_neq_zero_form_p (x1))
1459 return false;
1461 return operand_equal_p (x1.pred_lhs, x2, 0);
1464 /* Returns true of the domain of single predicate expression
1465 EXPR1 is a subset of that of EXPR2. Returns false if it
1466 can not be proved. */
1468 static bool
1469 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1471 enum tree_code code1, code2;
1473 if (pred_equal_p (expr1, expr2))
1474 return true;
1476 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1477 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1478 return false;
1480 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1481 return false;
1483 code1 = expr1.cond_code;
1484 if (expr1.invert)
1485 code1 = invert_tree_comparison (code1, false);
1486 code2 = expr2.cond_code;
1487 if (expr2.invert)
1488 code2 = invert_tree_comparison (code2, false);
1490 if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) && code2 == BIT_AND_EXPR)
1491 return (wi::to_wide (expr1.pred_rhs)
1492 == (wi::to_wide (expr1.pred_rhs) & wi::to_wide (expr2.pred_rhs)));
1494 if (code1 != code2 && code2 != NE_EXPR)
1495 return false;
1497 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1498 return true;
1500 return false;
1503 /* Returns true if the domain of PRED1 is a subset
1504 of that of PRED2. Returns false if it can not be proved so. */
1506 static bool
1507 is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2)
1509 size_t np1, np2, i1, i2;
1511 np1 = pred1.length ();
1512 np2 = pred2.length ();
1514 for (i2 = 0; i2 < np2; i2++)
1516 bool found = false;
1517 pred_info info2 = pred2[i2];
1518 for (i1 = 0; i1 < np1; i1++)
1520 pred_info info1 = pred1[i1];
1521 if (is_pred_expr_subset_of (info1, info2))
1523 found = true;
1524 break;
1527 if (!found)
1528 return false;
1530 return true;
1533 /* Returns true if the domain defined by
1534 one pred chain ONE_PRED is a subset of the domain
1535 of *PREDS. It returns false if ONE_PRED's domain is
1536 not a subset of any of the sub-domains of PREDS
1537 (corresponding to each individual chains in it), even
1538 though it may be still be a subset of whole domain
1539 of PREDS which is the union (ORed) of all its subdomains.
1540 In other words, the result is conservative. */
1542 static bool
1543 is_included_in (pred_chain one_pred, pred_chain_union preds)
1545 size_t i;
1546 size_t n = preds.length ();
1548 for (i = 0; i < n; i++)
1550 if (is_pred_chain_subset_of (one_pred, preds[i]))
1551 return true;
1554 return false;
1557 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1558 true if the domain defined by PREDS1 is a superset
1559 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1560 PREDS2 respectively. The implementation chooses not to build
1561 generic trees (and relying on the folding capability of the
1562 compiler), but instead performs brute force comparison of
1563 individual predicate chains (won't be a compile time problem
1564 as the chains are pretty short). When the function returns
1565 false, it does not necessarily mean *PREDS1 is not a superset
1566 of *PREDS2, but mean it may not be so since the analysis can
1567 not prove it. In such cases, false warnings may still be
1568 emitted. */
1570 static bool
1571 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1573 size_t i, n2;
1574 pred_chain one_pred_chain = vNULL;
1576 n2 = preds2.length ();
1578 for (i = 0; i < n2; i++)
1580 one_pred_chain = preds2[i];
1581 if (!is_included_in (one_pred_chain, preds1))
1582 return false;
1585 return true;
1588 /* Returns true if TC is AND or OR. */
1590 static inline bool
1591 is_and_or_or_p (enum tree_code tc, tree type)
1593 return (tc == BIT_IOR_EXPR
1594 || (tc == BIT_AND_EXPR
1595 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1598 /* Returns true if X1 is the negate of X2. */
1600 static inline bool
1601 pred_neg_p (pred_info x1, pred_info x2)
1603 enum tree_code c1, c2;
1604 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1605 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1606 return false;
1608 c1 = x1.cond_code;
1609 if (x1.invert == x2.invert)
1610 c2 = invert_tree_comparison (x2.cond_code, false);
1611 else
1612 c2 = x2.cond_code;
1614 return c1 == c2;
1617 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1618 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1619 3) X OR (!X AND Y) is equivalent to (X OR Y);
1620 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1621 (x != 0 AND y != 0)
1622 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1623 (X AND Y) OR Z
1625 PREDS is the predicate chains, and N is the number of chains. */
1627 /* Helper function to implement rule 1 above. ONE_CHAIN is
1628 the AND predication to be simplified. */
1630 static void
1631 simplify_pred (pred_chain *one_chain)
1633 size_t i, j, n;
1634 bool simplified = false;
1635 pred_chain s_chain = vNULL;
1637 n = one_chain->length ();
1639 for (i = 0; i < n; i++)
1641 pred_info *a_pred = &(*one_chain)[i];
1643 if (!a_pred->pred_lhs)
1644 continue;
1645 if (!is_neq_zero_form_p (*a_pred))
1646 continue;
1648 gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1649 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1650 continue;
1651 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1653 for (j = 0; j < n; j++)
1655 pred_info *b_pred = &(*one_chain)[j];
1657 if (!b_pred->pred_lhs)
1658 continue;
1659 if (!is_neq_zero_form_p (*b_pred))
1660 continue;
1662 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1663 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1665 /* Mark a_pred for removal. */
1666 a_pred->pred_lhs = NULL;
1667 a_pred->pred_rhs = NULL;
1668 simplified = true;
1669 break;
1675 if (!simplified)
1676 return;
1678 for (i = 0; i < n; i++)
1680 pred_info *a_pred = &(*one_chain)[i];
1681 if (!a_pred->pred_lhs)
1682 continue;
1683 s_chain.safe_push (*a_pred);
1686 one_chain->release ();
1687 *one_chain = s_chain;
1690 /* The helper function implements the rule 2 for the
1691 OR predicate PREDS.
1693 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1695 static bool
1696 simplify_preds_2 (pred_chain_union *preds)
1698 size_t i, j, n;
1699 bool simplified = false;
1700 pred_chain_union s_preds = vNULL;
1702 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1703 (X AND Y) OR (X AND !Y) is equivalent to X. */
1705 n = preds->length ();
1706 for (i = 0; i < n; i++)
1708 pred_info x, y;
1709 pred_chain *a_chain = &(*preds)[i];
1711 if (a_chain->length () != 2)
1712 continue;
1714 x = (*a_chain)[0];
1715 y = (*a_chain)[1];
1717 for (j = 0; j < n; j++)
1719 pred_chain *b_chain;
1720 pred_info x2, y2;
1722 if (j == i)
1723 continue;
1725 b_chain = &(*preds)[j];
1726 if (b_chain->length () != 2)
1727 continue;
1729 x2 = (*b_chain)[0];
1730 y2 = (*b_chain)[1];
1732 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1734 /* Kill a_chain. */
1735 a_chain->release ();
1736 b_chain->release ();
1737 b_chain->safe_push (x);
1738 simplified = true;
1739 break;
1741 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1743 /* Kill a_chain. */
1744 a_chain->release ();
1745 b_chain->release ();
1746 b_chain->safe_push (y);
1747 simplified = true;
1748 break;
1752 /* Now clean up the chain. */
1753 if (simplified)
1755 for (i = 0; i < n; i++)
1757 if ((*preds)[i].is_empty ())
1758 continue;
1759 s_preds.safe_push ((*preds)[i]);
1761 preds->release ();
1762 (*preds) = s_preds;
1763 s_preds = vNULL;
1766 return simplified;
1769 /* The helper function implements the rule 2 for the
1770 OR predicate PREDS.
1772 3) x OR (!x AND y) is equivalent to x OR y. */
1774 static bool
1775 simplify_preds_3 (pred_chain_union *preds)
1777 size_t i, j, n;
1778 bool simplified = false;
1780 /* Now iteratively simplify X OR (!X AND Z ..)
1781 into X OR (Z ...). */
1783 n = preds->length ();
1784 if (n < 2)
1785 return false;
1787 for (i = 0; i < n; i++)
1789 pred_info x;
1790 pred_chain *a_chain = &(*preds)[i];
1792 if (a_chain->length () != 1)
1793 continue;
1795 x = (*a_chain)[0];
1797 for (j = 0; j < n; j++)
1799 pred_chain *b_chain;
1800 pred_info x2;
1801 size_t k;
1803 if (j == i)
1804 continue;
1806 b_chain = &(*preds)[j];
1807 if (b_chain->length () < 2)
1808 continue;
1810 for (k = 0; k < b_chain->length (); k++)
1812 x2 = (*b_chain)[k];
1813 if (pred_neg_p (x, x2))
1815 b_chain->unordered_remove (k);
1816 simplified = true;
1817 break;
1822 return simplified;
1825 /* The helper function implements the rule 4 for the
1826 OR predicate PREDS.
1828 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1829 (x != 0 ANd y != 0). */
1831 static bool
1832 simplify_preds_4 (pred_chain_union *preds)
1834 size_t i, j, n;
1835 bool simplified = false;
1836 pred_chain_union s_preds = vNULL;
1837 gimple *def_stmt;
1839 n = preds->length ();
1840 for (i = 0; i < n; i++)
1842 pred_info z;
1843 pred_chain *a_chain = &(*preds)[i];
1845 if (a_chain->length () != 1)
1846 continue;
1848 z = (*a_chain)[0];
1850 if (!is_neq_zero_form_p (z))
1851 continue;
1853 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1854 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1855 continue;
1857 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1858 continue;
1860 for (j = 0; j < n; j++)
1862 pred_chain *b_chain;
1863 pred_info x2, y2;
1865 if (j == i)
1866 continue;
1868 b_chain = &(*preds)[j];
1869 if (b_chain->length () != 2)
1870 continue;
1872 x2 = (*b_chain)[0];
1873 y2 = (*b_chain)[1];
1874 if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
1875 continue;
1877 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1878 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1879 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1880 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1882 /* Kill a_chain. */
1883 a_chain->release ();
1884 simplified = true;
1885 break;
1889 /* Now clean up the chain. */
1890 if (simplified)
1892 for (i = 0; i < n; i++)
1894 if ((*preds)[i].is_empty ())
1895 continue;
1896 s_preds.safe_push ((*preds)[i]);
1899 preds->release ();
1900 (*preds) = s_preds;
1901 s_preds = vNULL;
1904 return simplified;
1907 /* This function simplifies predicates in PREDS. */
1909 static void
1910 simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use)
1912 size_t i, n;
1913 bool changed = false;
1915 if (dump_file && dump_flags & TDF_DETAILS)
1917 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1918 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1921 for (i = 0; i < preds->length (); i++)
1922 simplify_pred (&(*preds)[i]);
1924 n = preds->length ();
1925 if (n < 2)
1926 return;
1930 changed = false;
1931 if (simplify_preds_2 (preds))
1932 changed = true;
1934 /* Now iteratively simplify X OR (!X AND Z ..)
1935 into X OR (Z ...). */
1936 if (simplify_preds_3 (preds))
1937 changed = true;
1939 if (simplify_preds_4 (preds))
1940 changed = true;
1942 while (changed);
1944 return;
1947 /* This is a helper function which attempts to normalize predicate chains
1948 by following UD chains. It basically builds up a big tree of either IOR
1949 operations or AND operations, and convert the IOR tree into a
1950 pred_chain_union or BIT_AND tree into a pred_chain.
1951 Example:
1953 _3 = _2 RELOP1 _1;
1954 _6 = _5 RELOP2 _4;
1955 _9 = _8 RELOP3 _7;
1956 _10 = _3 | _6;
1957 _12 = _9 | _0;
1958 _t = _10 | _12;
1960 then _t != 0 will be normalized into a pred_chain_union
1962 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1964 Similarly given,
1966 _3 = _2 RELOP1 _1;
1967 _6 = _5 RELOP2 _4;
1968 _9 = _8 RELOP3 _7;
1969 _10 = _3 & _6;
1970 _12 = _9 & _0;
1972 then _t != 0 will be normalized into a pred_chain:
1973 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1977 /* This is a helper function that stores a PRED into NORM_PREDS. */
1979 inline static void
1980 push_pred (pred_chain_union *norm_preds, pred_info pred)
1982 pred_chain pred_chain = vNULL;
1983 pred_chain.safe_push (pred);
1984 norm_preds->safe_push (pred_chain);
1987 /* A helper function that creates a predicate of the form
1988 OP != 0 and push it WORK_LIST. */
1990 inline static void
1991 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1992 hash_set<tree> *mark_set)
1994 if (mark_set->contains (op))
1995 return;
1996 mark_set->add (op);
1998 pred_info arg_pred;
1999 arg_pred.pred_lhs = op;
2000 arg_pred.pred_rhs = integer_zero_node;
2001 arg_pred.cond_code = NE_EXPR;
2002 arg_pred.invert = false;
2003 work_list->safe_push (arg_pred);
2006 /* A helper that generates a pred_info from a gimple assignment
2007 CMP_ASSIGN with comparison rhs. */
2009 static pred_info
2010 get_pred_info_from_cmp (gimple *cmp_assign)
2012 pred_info n_pred;
2013 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
2014 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
2015 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
2016 n_pred.invert = false;
2017 return n_pred;
2020 /* Returns true if the PHI is a degenerated phi with
2021 all args with the same value (relop). In that case, *PRED
2022 will be updated to that value. */
2024 static bool
2025 is_degenerated_phi (gimple *phi, pred_info *pred_p)
2027 int i, n;
2028 tree op0;
2029 gimple *def0;
2030 pred_info pred0;
2032 n = gimple_phi_num_args (phi);
2033 op0 = gimple_phi_arg_def (phi, 0);
2035 if (TREE_CODE (op0) != SSA_NAME)
2036 return false;
2038 def0 = SSA_NAME_DEF_STMT (op0);
2039 if (gimple_code (def0) != GIMPLE_ASSIGN)
2040 return false;
2041 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
2042 return false;
2043 pred0 = get_pred_info_from_cmp (def0);
2045 for (i = 1; i < n; ++i)
2047 gimple *def;
2048 pred_info pred;
2049 tree op = gimple_phi_arg_def (phi, i);
2051 if (TREE_CODE (op) != SSA_NAME)
2052 return false;
2054 def = SSA_NAME_DEF_STMT (op);
2055 if (gimple_code (def) != GIMPLE_ASSIGN)
2056 return false;
2057 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
2058 return false;
2059 pred = get_pred_info_from_cmp (def);
2060 if (!pred_equal_p (pred, pred0))
2061 return false;
2064 *pred_p = pred0;
2065 return true;
2068 /* Normalize one predicate PRED
2069 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2070 2) otherwise if PRED is of the form x != 0, follow x's definition
2071 and put normalized predicates into WORK_LIST. */
2073 static void
2074 normalize_one_pred_1 (pred_chain_union *norm_preds,
2075 pred_chain *norm_chain,
2076 pred_info pred,
2077 enum tree_code and_or_code,
2078 vec<pred_info, va_heap, vl_ptr> *work_list,
2079 hash_set<tree> *mark_set)
2081 if (!is_neq_zero_form_p (pred))
2083 if (and_or_code == BIT_IOR_EXPR)
2084 push_pred (norm_preds, pred);
2085 else
2086 norm_chain->safe_push (pred);
2087 return;
2090 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2092 if (gimple_code (def_stmt) == GIMPLE_PHI
2093 && is_degenerated_phi (def_stmt, &pred))
2094 work_list->safe_push (pred);
2095 else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
2097 int i, n;
2098 n = gimple_phi_num_args (def_stmt);
2100 /* If we see non zero constant, we should punt. The predicate
2101 * should be one guarding the phi edge. */
2102 for (i = 0; i < n; ++i)
2104 tree op = gimple_phi_arg_def (def_stmt, i);
2105 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
2107 push_pred (norm_preds, pred);
2108 return;
2112 for (i = 0; i < n; ++i)
2114 tree op = gimple_phi_arg_def (def_stmt, i);
2115 if (integer_zerop (op))
2116 continue;
2118 push_to_worklist (op, work_list, mark_set);
2121 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2123 if (and_or_code == BIT_IOR_EXPR)
2124 push_pred (norm_preds, pred);
2125 else
2126 norm_chain->safe_push (pred);
2128 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
2130 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2131 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
2133 /* But treat x & 3 as condition. */
2134 if (and_or_code == BIT_AND_EXPR)
2136 pred_info n_pred;
2137 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
2138 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
2139 n_pred.cond_code = and_or_code;
2140 n_pred.invert = false;
2141 norm_chain->safe_push (n_pred);
2144 else
2146 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
2147 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
2150 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
2151 == tcc_comparison)
2153 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2154 if (and_or_code == BIT_IOR_EXPR)
2155 push_pred (norm_preds, n_pred);
2156 else
2157 norm_chain->safe_push (n_pred);
2159 else
2161 if (and_or_code == BIT_IOR_EXPR)
2162 push_pred (norm_preds, pred);
2163 else
2164 norm_chain->safe_push (pred);
2168 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2170 static void
2171 normalize_one_pred (pred_chain_union *norm_preds, pred_info pred)
2173 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2174 enum tree_code and_or_code = ERROR_MARK;
2175 pred_chain norm_chain = vNULL;
2177 if (!is_neq_zero_form_p (pred))
2179 push_pred (norm_preds, pred);
2180 return;
2183 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2184 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2185 and_or_code = gimple_assign_rhs_code (def_stmt);
2186 if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
2188 if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
2190 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2191 push_pred (norm_preds, n_pred);
2193 else
2194 push_pred (norm_preds, pred);
2195 return;
2198 work_list.safe_push (pred);
2199 hash_set<tree> mark_set;
2201 while (!work_list.is_empty ())
2203 pred_info a_pred = work_list.pop ();
2204 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code,
2205 &work_list, &mark_set);
2207 if (and_or_code == BIT_AND_EXPR)
2208 norm_preds->safe_push (norm_chain);
2210 work_list.release ();
2213 static void
2214 normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain)
2216 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2217 hash_set<tree> mark_set;
2218 pred_chain norm_chain = vNULL;
2219 size_t i;
2221 for (i = 0; i < one_chain.length (); i++)
2223 work_list.safe_push (one_chain[i]);
2224 mark_set.add (one_chain[i].pred_lhs);
2227 while (!work_list.is_empty ())
2229 pred_info a_pred = work_list.pop ();
2230 normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list,
2231 &mark_set);
2234 norm_preds->safe_push (norm_chain);
2235 work_list.release ();
2238 /* Normalize predicate chains PREDS and returns the normalized one. */
2240 static pred_chain_union
2241 normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
2243 pred_chain_union norm_preds = vNULL;
2244 size_t n = preds.length ();
2245 size_t i;
2247 if (dump_file && dump_flags & TDF_DETAILS)
2249 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2250 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2253 for (i = 0; i < n; i++)
2255 if (preds[i].length () != 1)
2256 normalize_one_pred_chain (&norm_preds, preds[i]);
2257 else
2259 normalize_one_pred (&norm_preds, preds[i][0]);
2260 preds[i].release ();
2264 if (dump_file)
2266 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2267 dump_predicates (use_or_def, norm_preds,
2268 is_use ? "[USE]:\n" : "[DEF]:\n");
2271 destroy_predicate_vecs (&preds);
2272 return norm_preds;
2275 /* Return TRUE if PREDICATE can be invalidated by any individual
2276 predicate in USE_GUARD. */
2278 static bool
2279 can_one_predicate_be_invalidated_p (pred_info predicate,
2280 pred_chain use_guard)
2282 if (dump_file && dump_flags & TDF_DETAILS)
2284 fprintf (dump_file, "Testing if this predicate: ");
2285 dump_pred_info (predicate);
2286 fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
2287 dump_pred_chain (use_guard);
2289 for (size_t i = 0; i < use_guard.length (); ++i)
2291 /* NOTE: This is a very simple check, and only understands an
2292 exact opposite. So, [i == 0] is currently only invalidated
2293 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2294 invalidate with say [i > 5] or [i == 8]. There is certainly
2295 room for improvement here. */
2296 if (pred_neg_p (predicate, use_guard[i]))
2298 if (dump_file && dump_flags & TDF_DETAILS)
2300 fprintf (dump_file, " Predicate was invalidated by: ");
2301 dump_pred_info (use_guard[i]);
2302 fputc ('\n', dump_file);
2304 return true;
2307 return false;
2310 /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2311 USE_GUARD being true. */
2313 static bool
2314 can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
2315 pred_chain use_guard)
2317 if (uninit_pred.is_empty ())
2318 return false;
2319 if (dump_file && dump_flags & TDF_DETAILS)
2320 dump_predicates (NULL, uninit_pred,
2321 "Testing if anything here can be invalidated: ");
2322 for (size_t i = 0; i < uninit_pred.length (); ++i)
2324 pred_chain c = uninit_pred[i];
2325 size_t j;
2326 for (j = 0; j < c.length (); ++j)
2327 if (can_one_predicate_be_invalidated_p (c[j], use_guard))
2328 break;
2330 /* If we were unable to invalidate any predicate in C, then there
2331 is a viable path from entry to the PHI where the PHI takes
2332 an uninitialized value and continues to a use of the PHI. */
2333 if (j == c.length ())
2334 return false;
2336 return true;
2339 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2340 can actually happen if we arrived at a use for PHI.
2342 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2344 static bool
2345 uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
2346 pred_chain_union phi_use_guards)
2348 unsigned phi_args = gimple_phi_num_args (phi);
2349 if (phi_args > max_phi_args)
2350 return false;
2352 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2353 possible guard, there's no way of knowing which guard was true.
2354 Since we need to be absolutely sure that the uninitialized
2355 operands will be invalidated, bail. */
2356 if (phi_use_guards.length () != 1)
2357 return false;
2359 /* Look for the control dependencies of all the uninitialized
2360 operands and build guard predicates describing them. */
2361 pred_chain_union uninit_preds;
2362 bool ret = true;
2363 for (unsigned i = 0; i < phi_args; ++i)
2365 if (!MASK_TEST_BIT (uninit_opnds, i))
2366 continue;
2368 edge e = gimple_phi_arg_edge (phi, i);
2369 vec<edge> dep_chains[MAX_NUM_CHAINS];
2370 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
2371 size_t num_chains = 0;
2372 int num_calls = 0;
2374 /* Build the control dependency chain for uninit operand `i'... */
2375 uninit_preds = vNULL;
2376 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
2377 e->src, dep_chains, &num_chains,
2378 &cur_chain, &num_calls))
2380 ret = false;
2381 break;
2383 /* ...and convert it into a set of predicates. */
2384 bool has_valid_preds
2385 = convert_control_dep_chain_into_preds (dep_chains, num_chains,
2386 &uninit_preds);
2387 for (size_t j = 0; j < num_chains; ++j)
2388 dep_chains[j].release ();
2389 if (!has_valid_preds)
2391 ret = false;
2392 break;
2394 simplify_preds (&uninit_preds, NULL, false);
2395 uninit_preds = normalize_preds (uninit_preds, NULL, false);
2397 /* Can the guard for this uninitialized operand be invalidated
2398 by the PHI use? */
2399 if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0]))
2401 ret = false;
2402 break;
2405 destroy_predicate_vecs (&uninit_preds);
2406 return ret;
2409 /* Computes the predicates that guard the use and checks
2410 if the incoming paths that have empty (or possibly
2411 empty) definition can be pruned/filtered. The function returns
2412 true if it can be determined that the use of PHI's def in
2413 USE_STMT is guarded with a predicate set not overlapping with
2414 predicate sets of all runtime paths that do not have a definition.
2416 Returns false if it is not or it can not be determined. USE_BB is
2417 the bb of the use (for phi operand use, the bb is not the bb of
2418 the phi stmt, but the src bb of the operand edge).
2420 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2421 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2422 set of phis being visited.
2424 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2425 If *DEF_PREDS is the empty vector, the defining predicate chains of
2426 PHI will be computed and stored into *DEF_PREDS as needed.
2428 VISITED_PHIS is a pointer set of phis being visited. */
2430 static bool
2431 is_use_properly_guarded (gimple *use_stmt,
2432 basic_block use_bb,
2433 gphi *phi,
2434 unsigned uninit_opnds,
2435 pred_chain_union *def_preds,
2436 hash_set<gphi *> *visited_phis)
2438 basic_block phi_bb;
2439 pred_chain_union preds = vNULL;
2440 bool has_valid_preds = false;
2441 bool is_properly_guarded = false;
2443 if (visited_phis->add (phi))
2444 return false;
2446 phi_bb = gimple_bb (phi);
2448 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2449 return false;
2451 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2453 if (!has_valid_preds)
2455 destroy_predicate_vecs (&preds);
2456 return false;
2459 /* Try to prune the dead incoming phi edges. */
2460 is_properly_guarded
2461 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2462 visited_phis);
2464 /* We might be able to prove that if the control dependencies
2465 for UNINIT_OPNDS are true, that the control dependencies for
2466 USE_STMT can never be true. */
2467 if (!is_properly_guarded)
2468 is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds,
2469 preds);
2471 if (is_properly_guarded)
2473 destroy_predicate_vecs (&preds);
2474 return true;
2477 if (def_preds->is_empty ())
2479 has_valid_preds = find_def_preds (def_preds, phi);
2481 if (!has_valid_preds)
2483 destroy_predicate_vecs (&preds);
2484 return false;
2487 simplify_preds (def_preds, phi, false);
2488 *def_preds = normalize_preds (*def_preds, phi, false);
2491 simplify_preds (&preds, use_stmt, true);
2492 preds = normalize_preds (preds, use_stmt, true);
2494 is_properly_guarded = is_superset_of (*def_preds, preds);
2496 destroy_predicate_vecs (&preds);
2497 return is_properly_guarded;
2500 /* Searches through all uses of a potentially
2501 uninitialized variable defined by PHI and returns a use
2502 statement if the use is not properly guarded. It returns
2503 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2504 holding the position(s) of uninit PHI operands. WORKLIST
2505 is the vector of candidate phis that may be updated by this
2506 function. ADDED_TO_WORKLIST is the pointer set tracking
2507 if the new phi is already in the worklist. */
2509 static gimple *
2510 find_uninit_use (gphi *phi, unsigned uninit_opnds,
2511 vec<gphi *> *worklist,
2512 hash_set<gphi *> *added_to_worklist)
2514 tree phi_result;
2515 use_operand_p use_p;
2516 gimple *use_stmt;
2517 imm_use_iterator iter;
2518 pred_chain_union def_preds = vNULL;
2519 gimple *ret = NULL;
2521 phi_result = gimple_phi_result (phi);
2523 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2525 basic_block use_bb;
2527 use_stmt = USE_STMT (use_p);
2528 if (is_gimple_debug (use_stmt))
2529 continue;
2531 if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
2532 use_bb = gimple_phi_arg_edge (use_phi,
2533 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2534 else
2535 use_bb = gimple_bb (use_stmt);
2537 hash_set<gphi *> visited_phis;
2538 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2539 &def_preds, &visited_phis))
2540 continue;
2542 if (dump_file && (dump_flags & TDF_DETAILS))
2544 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2545 print_gimple_stmt (dump_file, use_stmt, 0);
2547 /* Found one real use, return. */
2548 if (gimple_code (use_stmt) != GIMPLE_PHI)
2550 ret = use_stmt;
2551 break;
2554 /* Found a phi use that is not guarded,
2555 add the phi to the worklist. */
2556 if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
2558 if (dump_file && (dump_flags & TDF_DETAILS))
2560 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2561 print_gimple_stmt (dump_file, use_stmt, 0);
2564 worklist->safe_push (as_a<gphi *> (use_stmt));
2565 possibly_undefined_names->add (phi_result);
2569 destroy_predicate_vecs (&def_preds);
2570 return ret;
2573 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2574 and gives warning if there exists a runtime path from the entry to a
2575 use of the PHI def that does not contain a definition. In other words,
2576 the warning is on the real use. The more dead paths that can be pruned
2577 by the compiler, the fewer false positives the warning is. WORKLIST
2578 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2579 a pointer set tracking if the new phi is added to the worklist or not. */
2581 static void
2582 warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
2583 hash_set<gphi *> *added_to_worklist)
2585 unsigned uninit_opnds;
2586 gimple *uninit_use_stmt = 0;
2587 tree uninit_op;
2588 int phiarg_index;
2589 location_t loc;
2591 /* Don't look at virtual operands. */
2592 if (virtual_operand_p (gimple_phi_result (phi)))
2593 return;
2595 uninit_opnds = compute_uninit_opnds_pos (phi);
2597 if (MASK_EMPTY (uninit_opnds))
2598 return;
2600 if (dump_file && (dump_flags & TDF_DETAILS))
2602 fprintf (dump_file, "[CHECK]: examining phi: ");
2603 print_gimple_stmt (dump_file, phi, 0);
2606 /* Now check if we have any use of the value without proper guard. */
2607 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2608 worklist, added_to_worklist);
2610 /* All uses are properly guarded. */
2611 if (!uninit_use_stmt)
2612 return;
2614 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2615 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2616 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2617 return;
2618 if (gimple_phi_arg_has_location (phi, phiarg_index))
2619 loc = gimple_phi_arg_location (phi, phiarg_index);
2620 else
2621 loc = UNKNOWN_LOCATION;
2622 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2623 SSA_NAME_VAR (uninit_op),
2624 "%qD may be used uninitialized in this function",
2625 uninit_use_stmt, loc);
2628 static bool
2629 gate_warn_uninitialized (void)
2631 return warn_uninitialized || warn_maybe_uninitialized;
2634 namespace {
2636 const pass_data pass_data_late_warn_uninitialized =
2638 GIMPLE_PASS, /* type */
2639 "uninit", /* name */
2640 OPTGROUP_NONE, /* optinfo_flags */
2641 TV_NONE, /* tv_id */
2642 PROP_ssa, /* properties_required */
2643 0, /* properties_provided */
2644 0, /* properties_destroyed */
2645 0, /* todo_flags_start */
2646 0, /* todo_flags_finish */
2649 class pass_late_warn_uninitialized : public gimple_opt_pass
2651 public:
2652 pass_late_warn_uninitialized (gcc::context *ctxt)
2653 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2656 /* opt_pass methods: */
2657 opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2658 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2659 virtual unsigned int execute (function *);
2661 }; // class pass_late_warn_uninitialized
2663 unsigned int
2664 pass_late_warn_uninitialized::execute (function *fun)
2666 basic_block bb;
2667 gphi_iterator gsi;
2668 vec<gphi *> worklist = vNULL;
2670 calculate_dominance_info (CDI_DOMINATORS);
2671 calculate_dominance_info (CDI_POST_DOMINATORS);
2672 /* Re-do the plain uninitialized variable check, as optimization may have
2673 straightened control flow. Do this first so that we don't accidentally
2674 get a "may be" warning when we'd have seen an "is" warning later. */
2675 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2677 timevar_push (TV_TREE_UNINIT);
2679 possibly_undefined_names = new hash_set<tree>;
2680 hash_set<gphi *> added_to_worklist;
2682 /* Initialize worklist */
2683 FOR_EACH_BB_FN (bb, fun)
2684 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2686 gphi *phi = gsi.phi ();
2687 size_t n, i;
2689 n = gimple_phi_num_args (phi);
2691 /* Don't look at virtual operands. */
2692 if (virtual_operand_p (gimple_phi_result (phi)))
2693 continue;
2695 for (i = 0; i < n; ++i)
2697 tree op = gimple_phi_arg_def (phi, i);
2698 if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
2700 worklist.safe_push (phi);
2701 added_to_worklist.add (phi);
2702 if (dump_file && (dump_flags & TDF_DETAILS))
2704 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2705 print_gimple_stmt (dump_file, phi, 0);
2707 break;
2712 while (worklist.length () != 0)
2714 gphi *cur_phi = 0;
2715 cur_phi = worklist.pop ();
2716 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
2719 worklist.release ();
2720 delete possibly_undefined_names;
2721 possibly_undefined_names = NULL;
2722 free_dominance_info (CDI_POST_DOMINATORS);
2723 timevar_pop (TV_TREE_UNINIT);
2724 return 0;
2727 } // anon namespace
2729 gimple_opt_pass *
2730 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2732 return new pass_late_warn_uninitialized (ctxt);
2735 static unsigned int
2736 execute_early_warn_uninitialized (void)
2738 /* Currently, this pass runs always but
2739 execute_late_warn_uninitialized only runs with optimization. With
2740 optimization we want to warn about possible uninitialized as late
2741 as possible, thus don't do it here. However, without
2742 optimization we need to warn here about "may be uninitialized". */
2743 calculate_dominance_info (CDI_POST_DOMINATORS);
2745 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2747 /* Post-dominator information can not be reliably updated. Free it
2748 after the use. */
2750 free_dominance_info (CDI_POST_DOMINATORS);
2751 return 0;
2754 namespace {
2756 const pass_data pass_data_early_warn_uninitialized =
2758 GIMPLE_PASS, /* type */
2759 "*early_warn_uninitialized", /* name */
2760 OPTGROUP_NONE, /* optinfo_flags */
2761 TV_TREE_UNINIT, /* tv_id */
2762 PROP_ssa, /* properties_required */
2763 0, /* properties_provided */
2764 0, /* properties_destroyed */
2765 0, /* todo_flags_start */
2766 0, /* todo_flags_finish */
2769 class pass_early_warn_uninitialized : public gimple_opt_pass
2771 public:
2772 pass_early_warn_uninitialized (gcc::context *ctxt)
2773 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2776 /* opt_pass methods: */
2777 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2778 virtual unsigned int execute (function *)
2780 return execute_early_warn_uninitialized ();
2783 }; // class pass_early_warn_uninitialized
2785 } // anon namespace
2787 gimple_opt_pass *
2788 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2790 return new pass_early_warn_uninitialized (ctxt);