1 /* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2020 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
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 "tree-cfg.h"
35 #include "cfghooks.h"
36
37 /* This implements the pass that does predicate aware warning on uses of
38 possibly uninitialized variables. The pass first collects the set of
39 possibly uninitialized SSA names. For each such name, it walks through
40 all its immediate uses. For each immediate use, it rebuilds the condition
41 expression (the predicate) that guards the use. The predicate is then
42 examined to see if the variable is always defined under that same condition.
43 This is done either by pruning the unrealizable paths that lead to the
44 default definitions or by checking if the predicate set that guards the
45 defining paths is a superset of the use predicate. */
46
47 /* Max PHI args we can handle in pass. */
48 const unsigned max_phi_args = 32;
49
50 /* Pointer set of potentially undefined ssa names, i.e.,
51 ssa names that are defined by phi with operands that
52 are not defined or potentially undefined. */
53 static hash_set<tree> *possibly_undefined_names = 0;
54
55 /* Bit mask handling macros. */
56 #define MASK_SET_BIT(mask, pos) mask |= (1 << pos)
57 #define MASK_TEST_BIT(mask, pos) (mask & (1 << pos))
58 #define MASK_EMPTY(mask) (mask == 0)
59
60 /* Returns the first bit position (starting from LSB)
61 in mask that is non zero. Returns -1 if the mask is empty. */
62 static int
get_mask_first_set_bit(unsigned mask)63 get_mask_first_set_bit (unsigned mask)
64 {
65 int pos = 0;
66 if (mask == 0)
67 return -1;
68
69 while ((mask & (1 << pos)) == 0)
70 pos++;
71
72 return pos;
73 }
74 #define MASK_FIRST_SET_BIT(mask) get_mask_first_set_bit (mask)
75
76 /* Return true if T, an SSA_NAME, has an undefined value. */
77 static bool
has_undefined_value_p(tree t)78 has_undefined_value_p (tree t)
79 {
80 return (ssa_undefined_value_p (t)
81 || (possibly_undefined_names
82 && possibly_undefined_names->contains (t)));
83 }
84
85 /* Like has_undefined_value_p, but don't return true if TREE_NO_WARNING
86 is set on SSA_NAME_VAR. */
87
88 static inline bool
uninit_undefined_value_p(tree t)89 uninit_undefined_value_p (tree t)
90 {
91 if (!has_undefined_value_p (t))
92 return false;
93 if (SSA_NAME_VAR (t) && TREE_NO_WARNING (SSA_NAME_VAR (t)))
94 return false;
95 return true;
96 }
97
98 /* Emit warnings for uninitialized variables. This is done in two passes.
99
100 The first pass notices real uses of SSA names with undefined values.
101 Such uses are unconditionally uninitialized, and we can be certain that
102 such a use is a mistake. This pass is run before most optimizations,
103 so that we catch as many as we can.
104
105 The second pass follows PHI nodes to find uses that are potentially
106 uninitialized. In this case we can't necessarily prove that the use
107 is really uninitialized. This pass is run after most optimizations,
108 so that we thread as many jumps and possible, and delete as much dead
109 code as possible, in order to reduce false positives. We also look
110 again for plain uninitialized variables, since optimization may have
111 changed conditionally uninitialized to unconditionally uninitialized. */
112
113 /* Emit a warning for EXPR based on variable VAR at the point in the
114 program T, an SSA_NAME, is used being uninitialized. The exact
115 warning text is in MSGID and DATA is the gimple stmt with info about
116 the location in source code. When DATA is a GIMPLE_PHI, PHIARG_IDX
117 gives which argument of the phi node to take the location from. WC
118 is the warning code. */
119
120 static void
warn_uninit(enum opt_code wc,tree t,tree expr,tree var,const char * gmsgid,void * data,location_t phiarg_loc)121 warn_uninit (enum opt_code wc, tree t, tree expr, tree var,
122 const char *gmsgid, void *data, location_t phiarg_loc)
123 {
124 gimple *context = (gimple *) data;
125 location_t location, cfun_loc;
126 expanded_location xloc, floc;
127
128 /* Ignore COMPLEX_EXPR as initializing only a part of a complex
129 turns in a COMPLEX_EXPR with the not initialized part being
130 set to its previous (undefined) value. */
131 if (is_gimple_assign (context)
132 && gimple_assign_rhs_code (context) == COMPLEX_EXPR)
133 return;
134 if (!has_undefined_value_p (t))
135 return;
136
137 /* Anonymous SSA_NAMEs shouldn't be uninitialized, but ssa_undefined_value_p
138 can return true if the def stmt of anonymous SSA_NAME is COMPLEX_EXPR
139 created for conversion from scalar to complex. Use the underlying var of
140 the COMPLEX_EXPRs real part in that case. See PR71581. */
141 if (expr == NULL_TREE
142 && var == NULL_TREE
143 && SSA_NAME_VAR (t) == NULL_TREE
144 && is_gimple_assign (SSA_NAME_DEF_STMT (t))
145 && gimple_assign_rhs_code (SSA_NAME_DEF_STMT (t)) == COMPLEX_EXPR)
146 {
147 tree v = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (t));
148 if (TREE_CODE (v) == SSA_NAME
149 && has_undefined_value_p (v)
150 && zerop (gimple_assign_rhs2 (SSA_NAME_DEF_STMT (t))))
151 {
152 expr = SSA_NAME_VAR (v);
153 var = expr;
154 }
155 }
156
157 if (expr == NULL_TREE)
158 return;
159
160 /* TREE_NO_WARNING either means we already warned, or the front end
161 wishes to suppress the warning. */
162 if ((context
163 && (gimple_no_warning_p (context)
164 || (gimple_assign_single_p (context)
165 && TREE_NO_WARNING (gimple_assign_rhs1 (context)))))
166 || TREE_NO_WARNING (expr))
167 return;
168
169 if (context != NULL && gimple_has_location (context))
170 location = gimple_location (context);
171 else if (phiarg_loc != UNKNOWN_LOCATION)
172 location = phiarg_loc;
173 else
174 location = DECL_SOURCE_LOCATION (var);
175 location = linemap_resolve_location (line_table, location,
176 LRK_SPELLING_LOCATION, NULL);
177 cfun_loc = DECL_SOURCE_LOCATION (cfun->decl);
178 xloc = expand_location (location);
179 floc = expand_location (cfun_loc);
180 auto_diagnostic_group d;
181 if (warning_at (location, wc, gmsgid, expr))
182 {
183 TREE_NO_WARNING (expr) = 1;
184
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);
192 }
193 }
194
195 struct check_defs_data
196 {
197 /* If we found any may-defs besides must-def clobbers. */
198 bool found_may_defs;
199 };
200
201 /* Callback for walk_aliased_vdefs. */
202
203 static bool
check_defs(ao_ref * ref,tree vdef,void * data_)204 check_defs (ao_ref *ref, tree vdef, void *data_)
205 {
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))
210 {
211 if (stmt_kills_ref_p (def_stmt, ref))
212 return true;
213 return false;
214 }
215 /* Found a may-def on this path. */
216 data->found_may_defs = true;
217 return true;
218 }
219
220 static unsigned int
warn_uninitialized_vars(bool warn_possibly_uninitialized)221 warn_uninitialized_vars (bool warn_possibly_uninitialized)
222 {
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;
228
229 FOR_EACH_BB_FN (bb, cfun)
230 {
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))
234 {
235 gimple *stmt = gsi_stmt (gsi);
236 use_operand_p use_p;
237 ssa_op_iter op_iter;
238 tree use;
239
240 if (is_gimple_debug (stmt))
241 continue;
242
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)
246 {
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))
250 {
251 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
252 && use_p->use == gimple_assign_rhs1_ptr (ass))
253 continue;
254 }
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);
266 }
267
268 /* For limiting the alias walk below we count all
269 vdefs in the function. */
270 if (gimple_vdef (stmt))
271 vdef_cnt++;
272
273 if (gimple_assign_load_p (stmt)
274 && gimple_has_location (stmt))
275 {
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;
281
282 if (TREE_NO_WARNING (rhs))
283 continue;
284
285 ao_ref ref;
286 ao_ref_init (&ref, rhs);
287
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;
295
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;
308
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)
312 {
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))
317 {
318 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
319 && luse_p->use == gimple_assign_rhs1_ptr (ass))
320 {
321 has_bit_insert = true;
322 break;
323 }
324 }
325 }
326 if (has_bit_insert)
327 continue;
328
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)
343 {
344 oracle_cnt += limit;
345 continue;
346 }
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;
360
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)
367 {
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;
376 }
377 else if (warn_possibly_uninitialized)
378 warning_at (location, OPT_Wmaybe_uninitialized,
379 "%qE may be used uninitialized in this function",
380 rhs);
381 }
382 }
383 }
384
385 return 0;
386 }
387
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. */
393
394 static bool
can_skip_redundant_opnd(tree opnd,gimple * phi)395 can_skip_redundant_opnd (tree opnd, gimple *phi)
396 {
397 gimple *op_def;
398 tree phi_def;
399 int i, n;
400
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)
407 {
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;
413 }
414
415 return true;
416 }
417
418 /* Returns a bit mask holding the positions of arguments in PHI
419 that have empty (or possibly empty) definitions. */
420
421 static unsigned
compute_uninit_opnds_pos(gphi * phi)422 compute_uninit_opnds_pos (gphi *phi)
423 {
424 size_t i, n;
425 unsigned uninit_opnds = 0;
426
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;
431
432 for (i = 0; i < n; ++i)
433 {
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))
438 {
439 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
440 {
441 /* Ignore SSA_NAMEs that appear on abnormal edges
442 somewhere. */
443 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
444 continue;
445 }
446 MASK_SET_BIT (uninit_opnds, i);
447 }
448 }
449 return uninit_opnds;
450 }
451
452 /* Find the immediate postdominator PDOM of the specified
453 basic block BLOCK. */
454
455 static inline basic_block
find_pdom(basic_block block)456 find_pdom (basic_block block)
457 {
458 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
459 return EXIT_BLOCK_PTR_FOR_FN (cfun);
460 else
461 {
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;
466 }
467 }
468
469 /* Find the immediate DOM of the specified basic block BLOCK. */
470
471 static inline basic_block
find_dom(basic_block block)472 find_dom (basic_block block)
473 {
474 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
475 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
476 else
477 {
478 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
479 if (!bb)
480 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
481 return bb;
482 }
483 }
484
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. */
488
489 static bool
is_non_loop_exit_postdominating(basic_block bb1,basic_block bb2)490 is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
491 {
492 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
493 return false;
494
495 if (single_pred_p (bb1) && !single_succ_p (bb2))
496 return false;
497
498 return true;
499 }
500
501 /* Find the closest postdominator of a specified BB, which is control
502 equivalent to BB. */
503
504 static inline basic_block
find_control_equiv_block(basic_block bb)505 find_control_equiv_block (basic_block bb)
506 {
507 basic_block pdom;
508
509 pdom = find_pdom (bb);
510
511 /* Skip the postdominating bb that is also loop exit. */
512 if (!is_non_loop_exit_postdominating (pdom, bb))
513 return NULL;
514
515 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
516 return pdom;
517
518 return NULL;
519 }
520
521 #define MAX_NUM_CHAINS 8
522 #define MAX_CHAIN_LEN 5
523 #define MAX_POSTDOM_CHECK 8
524 #define MAX_SWITCH_CASES 40
525
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. */
533
534 static bool
compute_control_dep_chain(basic_block bb,basic_block dep_bb,vec<edge> * cd_chains,size_t * num_chains,vec<edge> * cur_cd_chain,int * num_calls)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)
540 {
541 edge_iterator ei;
542 edge e;
543 size_t i;
544 bool found_cd_chain = false;
545 size_t cur_chain_len = 0;
546
547 if (*num_calls > param_uninit_control_dep_attempts)
548 return false;
549 ++*num_calls;
550
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;
555
556 for (i = 0; i < cur_chain_len; i++)
557 {
558 edge e = (*cur_cd_chain)[i];
559 /* Cycle detected. */
560 if (e->src == bb)
561 return false;
562 }
563
564 FOR_EACH_EDGE (e, ei, bb->succs)
565 {
566 basic_block cd_bb;
567 int post_dom_check = 0;
568 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
569 continue;
570
571 cd_bb = e->dest;
572 cur_cd_chain->safe_push (e);
573 while (!is_non_loop_exit_postdominating (cd_bb, bb))
574 {
575 if (cd_bb == dep_bb)
576 {
577 /* Found a direct control dependence. */
578 if (*num_chains < MAX_NUM_CHAINS)
579 {
580 cd_chains[*num_chains] = cur_cd_chain->copy ();
581 (*num_chains)++;
582 }
583 found_cd_chain = true;
584 /* Check path from next edge. */
585 break;
586 }
587
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))
591 {
592 found_cd_chain = true;
593 break;
594 }
595
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;
601 }
602 cur_cd_chain->pop ();
603 gcc_assert (cur_cd_chain->length () == cur_chain_len);
604 }
605 gcc_assert (cur_cd_chain->length () == cur_chain_len);
606
607 return found_cd_chain;
608 }
609
610 /* The type to represent a simple predicate. */
611
612 struct pred_info
613 {
614 tree pred_lhs;
615 tree pred_rhs;
616 enum tree_code cond_code;
617 bool invert;
618 };
619
620 /* The type to represent a sequence of predicates grouped
621 with .AND. operation. */
622
623 typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
624
625 /* The type to represent a sequence of pred_chains grouped
626 with .OR. operation. */
627
628 typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
629
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. */
640
641 static bool
convert_control_dep_chain_into_preds(vec<edge> * dep_chains,size_t num_chains,pred_chain_union * preds)642 convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
643 size_t num_chains,
644 pred_chain_union *preds)
645 {
646 bool has_valid_pred = false;
647 size_t i, j;
648 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
649 return false;
650
651 /* Now convert the control dep chain into a set
652 of predicates. */
653 preds->reserve (num_chains);
654
655 for (i = 0; i < num_chains; i++)
656 {
657 vec<edge> one_cd_chain = dep_chains[i];
658
659 has_valid_pred = false;
660 pred_chain t_chain = vNULL;
661 for (j = 0; j < one_cd_chain.length (); j++)
662 {
663 gimple *cond_stmt;
664 gimple_stmt_iterator gsi;
665 basic_block guard_bb;
666 pred_info one_pred;
667 edge e;
668
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))
678 {
679 has_valid_pred = false;
680 break;
681 }
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)
688 {
689 edge e1;
690 edge_iterator ei1;
691 bool skip = false;
692
693 FOR_EACH_EDGE (e1, ei1, e->src->succs)
694 {
695 if (EDGE_COUNT (e1->dest->succs) == 0)
696 {
697 skip = true;
698 break;
699 }
700 }
701 if (skip)
702 continue;
703 }
704 if (gimple_code (cond_stmt) == GIMPLE_COND)
705 {
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;
712 }
713 else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
714 {
715 /* Avoid quadratic behavior. */
716 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
717 {
718 has_valid_pred = false;
719 break;
720 }
721 /* Find the case label. */
722 tree l = NULL_TREE;
723 unsigned idx;
724 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
725 {
726 tree tl = gimple_switch_label (gs, idx);
727 if (e->dest == label_to_block (cfun, CASE_LABEL (tl)))
728 {
729 if (!l)
730 l = tl;
731 else
732 {
733 l = NULL_TREE;
734 break;
735 }
736 }
737 }
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)))
745 {
746 has_valid_pred = false;
747 break;
748 }
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;
755 }
756 else
757 {
758 has_valid_pred = false;
759 break;
760 }
761 }
762
763 if (!has_valid_pred)
764 break;
765 else
766 preds->safe_push (t_chain);
767 }
768 return has_valid_pred;
769 }
770
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. */
775
776 static bool
find_predicates(pred_chain_union * preds,basic_block phi_bb,basic_block use_bb)777 find_predicates (pred_chain_union *preds,
778 basic_block phi_bb,
779 basic_block use_bb)
780 {
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;
787
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))
792 {
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;
798 }
799
800 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
801 &cur_chain, &num_calls);
802
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;
808 }
809
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. */
815
816 static void
collect_phi_def_edges(gphi * phi,basic_block cd_root,auto_vec<edge> * edges,hash_set<gimple * > * visited_phis)817 collect_phi_def_edges (gphi *phi, basic_block cd_root,
818 auto_vec<edge> *edges,
819 hash_set<gimple *> *visited_phis)
820 {
821 size_t i, n;
822 edge opnd_edge;
823 tree opnd;
824
825 if (visited_phis->add (phi))
826 return;
827
828 n = gimple_phi_num_args (phi);
829 for (i = 0; i < n; i++)
830 {
831 opnd_edge = gimple_phi_arg_edge (phi, i);
832 opnd = gimple_phi_arg_def (phi, i);
833
834 if (TREE_CODE (opnd) != SSA_NAME)
835 {
836 if (dump_file && (dump_flags & TDF_DETAILS))
837 {
838 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i);
839 print_gimple_stmt (dump_file, phi, 0);
840 }
841 edges->safe_push (opnd_edge);
842 }
843 else
844 {
845 gimple *def = SSA_NAME_DEF_STMT (opnd);
846
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))
852 {
853 if (dump_file && (dump_flags & TDF_DETAILS))
854 {
855 fprintf (dump_file, "\n[CHECK] Found def edge %d in ",
856 (int) i);
857 print_gimple_stmt (dump_file, phi, 0);
858 }
859 edges->safe_push (opnd_edge);
860 }
861 }
862 }
863 }
864
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. */
868
869 static bool
find_def_preds(pred_chain_union * preds,gphi * phi)870 find_def_preds (pred_chain_union *preds, gphi *phi)
871 {
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;
878
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;
885
886 hash_set<gimple *> visited_phis;
887 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
888
889 n = def_edges.length ();
890 if (n == 0)
891 return false;
892
893 for (i = 0; i < n; i++)
894 {
895 size_t prev_nc, j;
896 int num_calls = 0;
897 edge opnd_edge;
898
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);
903
904 /* Now update the newly added chains with
905 the phi operand edge: */
906 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
907 {
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);
912 }
913 }
914
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;
920 }
921
922 /* Dump a pred_info. */
923
924 static void
dump_pred_info(pred_info one_pred)925 dump_pred_info (pred_info one_pred)
926 {
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);
932 }
933
934 /* Dump a pred_chain. */
935
936 static void
dump_pred_chain(pred_chain one_pred_chain)937 dump_pred_chain (pred_chain one_pred_chain)
938 {
939 size_t np = one_pred_chain.length ();
940 for (size_t j = 0; j < np; j++)
941 {
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");
947 }
948 }
949
950 /* Dumps the predicates (PREDS) for USESTMT. */
951
952 static void
dump_predicates(gimple * usestmt,pred_chain_union preds,const char * msg)953 dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
954 {
955 fprintf (dump_file, "%s", msg);
956 if (usestmt)
957 {
958 print_gimple_stmt (dump_file, usestmt, 0);
959 fprintf (dump_file, "is guarded by :\n\n");
960 }
961 size_t num_preds = preds.length ();
962 for (size_t i = 0; i < num_preds; i++)
963 {
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");
969 }
970 }
971
972 /* Destroys the predicate set *PREDS. */
973
974 static void
destroy_predicate_vecs(pred_chain_union * preds)975 destroy_predicate_vecs (pred_chain_union *preds)
976 {
977 size_t i;
978
979 size_t n = preds->length ();
980 for (i = 0; i < n; i++)
981 (*preds)[i].release ();
982 preds->release ();
983 }
984
985 /* Computes the 'normalized' conditional code with operand
986 swapping and condition inversion. */
987
988 static enum tree_code
get_cmp_code(enum tree_code orig_cmp_code,bool swap_cond,bool invert)989 get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
990 {
991 enum tree_code tc = orig_cmp_code;
992
993 if (swap_cond)
994 tc = swap_tree_comparison (orig_cmp_code);
995 if (invert)
996 tc = invert_tree_comparison (tc, false);
997
998 switch (tc)
999 {
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;
1009 }
1010 return tc;
1011 }
1012
1013 /* Returns whether VAL CMPC BOUNDARY is true. */
1014
1015 static bool
is_value_included_in(tree val,tree boundary,enum tree_code cmpc)1016 is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
1017 {
1018 bool inverted = false;
1019 bool result;
1020
1021 /* Only handle integer constant here. */
1022 if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
1023 return true;
1024
1025 if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
1026 {
1027 cmpc = invert_tree_comparison (cmpc, false);
1028 inverted = true;
1029 }
1030
1031 if (cmpc == EQ_EXPR)
1032 result = tree_int_cst_equal (val, boundary);
1033 else if (cmpc == LT_EXPR)
1034 result = tree_int_cst_lt (val, boundary);
1035 else
1036 {
1037 gcc_assert (cmpc == LE_EXPR);
1038 result = tree_int_cst_le (val, boundary);
1039 }
1040
1041 if (inverted)
1042 result ^= 1;
1043
1044 return result;
1045 }
1046
1047 /* Returns whether VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can be
1048 either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and the like),
1049 or BIT_AND_EXPR. EXACT_P is only meaningful for the latter. It modifies the
1050 question from whether VAL & BOUNDARY != 0 to whether VAL & BOUNDARY == VAL.
1051 For other values of CMPC, EXACT_P is ignored. */
1052
1053 static bool
1054 value_sat_pred_p (tree val, tree boundary, enum tree_code cmpc,
1055 bool exact_p = false)
1056 {
1057 if (cmpc != BIT_AND_EXPR)
1058 return is_value_included_in (val, boundary, cmpc);
1059
1060 wide_int andw = wi::to_wide (val) & wi::to_wide (boundary);
1061 if (exact_p)
1062 return andw == wi::to_wide (val);
1063 else
1064 return andw.to_uhwi ();
1065 }
1066
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. */
1070
1071 static bool
find_matching_predicate_in_rest_chains(pred_info pred,pred_chain_union preds,size_t num_pred_chains)1072 find_matching_predicate_in_rest_chains (pred_info pred,
1073 pred_chain_union preds,
1074 size_t num_pred_chains)
1075 {
1076 size_t i, j, n;
1077
1078 /* Trival case. */
1079 if (num_pred_chains == 1)
1080 return true;
1081
1082 for (i = 1; i < num_pred_chains; i++)
1083 {
1084 bool found = false;
1085 pred_chain one_chain = preds[i];
1086 n = one_chain.length ();
1087 for (j = 0; j < n; j++)
1088 {
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. */
1095
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)
1099 {
1100 found = true;
1101 break;
1102 }
1103 }
1104 if (!found)
1105 return false;
1106 }
1107 return true;
1108 }
1109
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);
1117
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.
1127
1128 Example scenario:
1129
1130 BB1:
1131 flag_1 = phi <0, 1> // (1)
1132 var_1 = phi <undef, some_val>
1133
1134
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;
1140
1141 BB3:
1142 use of var_2 // (3)
1143
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. */
1150
1151 static bool
prune_uninit_phi_opnds(gphi * phi,unsigned uninit_opnds,gphi * flag_def,tree boundary_cst,enum tree_code cmp_code,hash_set<gphi * > * visited_phis,bitmap * visited_flag_phis)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)
1156 {
1157 unsigned i;
1158
1159 for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
1160 {
1161 tree flag_arg;
1162
1163 if (!MASK_TEST_BIT (uninit_opnds, i))
1164 continue;
1165
1166 flag_arg = gimple_phi_arg_def (flag_def, i);
1167 if (!is_gimple_constant (flag_arg))
1168 {
1169 gphi *flag_arg_def, *phi_arg_def;
1170 tree phi_arg;
1171 unsigned uninit_opnds_arg_phi;
1172
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;
1178
1179 phi_arg = gimple_phi_arg_def (phi, i);
1180 if (TREE_CODE (phi_arg) != SSA_NAME)
1181 return false;
1182
1183 phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1184 if (!phi_arg_def)
1185 return false;
1186
1187 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1188 return false;
1189
1190 if (!*visited_flag_phis)
1191 *visited_flag_phis = BITMAP_ALLOC (NULL);
1192
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;
1196
1197 bitmap_set_bit (*visited_flag_phis,
1198 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1199
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;
1206
1207 phi_result = gimple_phi_result (flag_arg_def);
1208 bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
1209 continue;
1210 }
1211
1212 /* Now check if the constant is in the guarded range. */
1213 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1214 {
1215 tree opnd;
1216 gimple *opnd_def;
1217
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. */
1222
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))
1226 {
1227 edge opnd_edge;
1228 unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi);
1229 if (!MASK_EMPTY (uninit_opnds2))
1230 {
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;
1243 }
1244 }
1245 else
1246 return false;
1247 }
1248 }
1249
1250 return true;
1251 }
1252
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)
1258 {
1259 x = ...;
1260 flag = true;
1261 }
1262
1263 ... some code ...
1264
1265 if (flag)
1266 use (x);
1267
1268 The real world examples are usually more complicated, but similar
1269 and usually result from inlining:
1270
1271 bool init_func (int * x)
1272 {
1273 if (some_cond)
1274 return false;
1275 *x = ..
1276 return true;
1277 }
1278
1279 void foo (..)
1280 {
1281 int x;
1282
1283 if (!init_func (&x))
1284 return;
1285
1286 .. some_code ...
1287 use (x);
1288 }
1289
1290 Another possible use scenario is in the following trivial example:
1291
1292 Example 2:
1293 if (n > 0)
1294 x = 1;
1295 ...
1296 if (n > 0)
1297 {
1298 if (m < 2)
1299 .. = x;
1300 }
1301
1302 Predicate analysis needs to compute the composite predicate:
1303
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.)
1309
1310 and check overlapping:
1311 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1312 <==> false
1313
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.)
1319
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. */
1324
1325 static bool
use_pred_not_overlap_with_undef_path_pred(pred_chain_union preds,gphi * phi,unsigned uninit_opnds,hash_set<gphi * > * visited_phis)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)
1329 {
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 ();
1340
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++)
1348 {
1349 tree cond_lhs, cond_rhs, flag = 0;
1350
1351 pred_info the_pred = the_pred_chain[i];
1352
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;
1357
1358 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1359 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1360 {
1361 boundary_cst = cond_rhs;
1362 flag = cond_lhs;
1363 }
1364 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1365 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1366 {
1367 boundary_cst = cond_lhs;
1368 flag = cond_rhs;
1369 swap_cond = true;
1370 }
1371
1372 if (!flag)
1373 continue;
1374
1375 flag_def = SSA_NAME_DEF_STMT (flag);
1376
1377 if (!flag_def)
1378 continue;
1379
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;
1385
1386 flag_def = 0;
1387 }
1388
1389 if (!flag_def)
1390 return false;
1391
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);
1395
1396 if (cmp_code == ERROR_MARK)
1397 return false;
1398
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);
1402
1403 if (visited_flag_phis)
1404 BITMAP_FREE (visited_flag_phis);
1405
1406 return all_pruned;
1407 }
1408
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. */
1412
1413 static inline bool
pred_equal_p(pred_info x1,pred_info x2)1414 pred_equal_p (pred_info x1, pred_info x2)
1415 {
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;
1420
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;
1427
1428 return c1 == c2;
1429 }
1430
1431 /* Returns true if the predication is testing !=. */
1432
1433 static inline bool
is_neq_relop_p(pred_info pred)1434 is_neq_relop_p (pred_info pred)
1435 {
1436
1437 return ((pred.cond_code == NE_EXPR && !pred.invert)
1438 || (pred.cond_code == EQ_EXPR && pred.invert));
1439 }
1440
1441 /* Returns true if pred is of the form X != 0. */
1442
1443 static inline bool
is_neq_zero_form_p(pred_info pred)1444 is_neq_zero_form_p (pred_info pred)
1445 {
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;
1450 }
1451
1452 /* The helper function returns true if two predicates X1
1453 is equivalent to X2 != 0. */
1454
1455 static inline bool
pred_expr_equal_p(pred_info x1,tree x2)1456 pred_expr_equal_p (pred_info x1, tree x2)
1457 {
1458 if (!is_neq_zero_form_p (x1))
1459 return false;
1460
1461 return operand_equal_p (x1.pred_lhs, x2, 0);
1462 }
1463
1464 /* Returns true of the domain of single predicate expression
1465 EXPR1 is a subset of that of EXPR2. Returns false if it
1466 cannot be proved. */
1467
1468 static bool
is_pred_expr_subset_of(pred_info expr1,pred_info expr2)1469 is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1470 {
1471 enum tree_code code1, code2;
1472
1473 if (pred_equal_p (expr1, expr2))
1474 return true;
1475
1476 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1477 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1478 return false;
1479
1480 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1481 return false;
1482
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);
1489
1490 if (code2 == NE_EXPR && code1 == NE_EXPR)
1491 return false;
1492
1493 if (code2 == NE_EXPR)
1494 return !value_sat_pred_p (expr2.pred_rhs, expr1.pred_rhs, code1);
1495
1496 if (code1 == EQ_EXPR)
1497 return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2);
1498
1499 if (code1 == code2)
1500 return value_sat_pred_p (expr1.pred_rhs, expr2.pred_rhs, code2,
1501 code1 == BIT_AND_EXPR);
1502
1503 return false;
1504 }
1505
1506 /* Returns true if the domain of PRED1 is a subset
1507 of that of PRED2. Returns false if it cannot be proved so. */
1508
1509 static bool
is_pred_chain_subset_of(pred_chain pred1,pred_chain pred2)1510 is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2)
1511 {
1512 size_t np1, np2, i1, i2;
1513
1514 np1 = pred1.length ();
1515 np2 = pred2.length ();
1516
1517 for (i2 = 0; i2 < np2; i2++)
1518 {
1519 bool found = false;
1520 pred_info info2 = pred2[i2];
1521 for (i1 = 0; i1 < np1; i1++)
1522 {
1523 pred_info info1 = pred1[i1];
1524 if (is_pred_expr_subset_of (info1, info2))
1525 {
1526 found = true;
1527 break;
1528 }
1529 }
1530 if (!found)
1531 return false;
1532 }
1533 return true;
1534 }
1535
1536 /* Returns true if the domain defined by
1537 one pred chain ONE_PRED is a subset of the domain
1538 of *PREDS. It returns false if ONE_PRED's domain is
1539 not a subset of any of the sub-domains of PREDS
1540 (corresponding to each individual chains in it), even
1541 though it may be still be a subset of whole domain
1542 of PREDS which is the union (ORed) of all its subdomains.
1543 In other words, the result is conservative. */
1544
1545 static bool
is_included_in(pred_chain one_pred,pred_chain_union preds)1546 is_included_in (pred_chain one_pred, pred_chain_union preds)
1547 {
1548 size_t i;
1549 size_t n = preds.length ();
1550
1551 for (i = 0; i < n; i++)
1552 {
1553 if (is_pred_chain_subset_of (one_pred, preds[i]))
1554 return true;
1555 }
1556
1557 return false;
1558 }
1559
1560 /* Compares two predicate sets PREDS1 and PREDS2 and returns
1561 true if the domain defined by PREDS1 is a superset
1562 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1563 PREDS2 respectively. The implementation chooses not to build
1564 generic trees (and relying on the folding capability of the
1565 compiler), but instead performs brute force comparison of
1566 individual predicate chains (won't be a compile time problem
1567 as the chains are pretty short). When the function returns
1568 false, it does not necessarily mean *PREDS1 is not a superset
1569 of *PREDS2, but mean it may not be so since the analysis cannot
1570 prove it. In such cases, false warnings may still be
1571 emitted. */
1572
1573 static bool
is_superset_of(pred_chain_union preds1,pred_chain_union preds2)1574 is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1575 {
1576 size_t i, n2;
1577 pred_chain one_pred_chain = vNULL;
1578
1579 n2 = preds2.length ();
1580
1581 for (i = 0; i < n2; i++)
1582 {
1583 one_pred_chain = preds2[i];
1584 if (!is_included_in (one_pred_chain, preds1))
1585 return false;
1586 }
1587
1588 return true;
1589 }
1590
1591 /* Returns true if X1 is the negate of X2. */
1592
1593 static inline bool
pred_neg_p(pred_info x1,pred_info x2)1594 pred_neg_p (pred_info x1, pred_info x2)
1595 {
1596 enum tree_code c1, c2;
1597 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1598 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1599 return false;
1600
1601 c1 = x1.cond_code;
1602 if (x1.invert == x2.invert)
1603 c2 = invert_tree_comparison (x2.cond_code, false);
1604 else
1605 c2 = x2.cond_code;
1606
1607 return c1 == c2;
1608 }
1609
1610 /* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1611 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1612 3) X OR (!X AND Y) is equivalent to (X OR Y);
1613 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1614 (x != 0 AND y != 0)
1615 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1616 (X AND Y) OR Z
1617
1618 PREDS is the predicate chains, and N is the number of chains. */
1619
1620 /* Helper function to implement rule 1 above. ONE_CHAIN is
1621 the AND predication to be simplified. */
1622
1623 static void
simplify_pred(pred_chain * one_chain)1624 simplify_pred (pred_chain *one_chain)
1625 {
1626 size_t i, j, n;
1627 bool simplified = false;
1628 pred_chain s_chain = vNULL;
1629
1630 n = one_chain->length ();
1631
1632 for (i = 0; i < n; i++)
1633 {
1634 pred_info *a_pred = &(*one_chain)[i];
1635
1636 if (!a_pred->pred_lhs)
1637 continue;
1638 if (!is_neq_zero_form_p (*a_pred))
1639 continue;
1640
1641 gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1642 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1643 continue;
1644 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1645 {
1646 for (j = 0; j < n; j++)
1647 {
1648 pred_info *b_pred = &(*one_chain)[j];
1649
1650 if (!b_pred->pred_lhs)
1651 continue;
1652 if (!is_neq_zero_form_p (*b_pred))
1653 continue;
1654
1655 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1656 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1657 {
1658 /* Mark a_pred for removal. */
1659 a_pred->pred_lhs = NULL;
1660 a_pred->pred_rhs = NULL;
1661 simplified = true;
1662 break;
1663 }
1664 }
1665 }
1666 }
1667
1668 if (!simplified)
1669 return;
1670
1671 for (i = 0; i < n; i++)
1672 {
1673 pred_info *a_pred = &(*one_chain)[i];
1674 if (!a_pred->pred_lhs)
1675 continue;
1676 s_chain.safe_push (*a_pred);
1677 }
1678
1679 one_chain->release ();
1680 *one_chain = s_chain;
1681 }
1682
1683 /* The helper function implements the rule 2 for the
1684 OR predicate PREDS.
1685
1686 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1687
1688 static bool
simplify_preds_2(pred_chain_union * preds)1689 simplify_preds_2 (pred_chain_union *preds)
1690 {
1691 size_t i, j, n;
1692 bool simplified = false;
1693 pred_chain_union s_preds = vNULL;
1694
1695 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1696 (X AND Y) OR (X AND !Y) is equivalent to X. */
1697
1698 n = preds->length ();
1699 for (i = 0; i < n; i++)
1700 {
1701 pred_info x, y;
1702 pred_chain *a_chain = &(*preds)[i];
1703
1704 if (a_chain->length () != 2)
1705 continue;
1706
1707 x = (*a_chain)[0];
1708 y = (*a_chain)[1];
1709
1710 for (j = 0; j < n; j++)
1711 {
1712 pred_chain *b_chain;
1713 pred_info x2, y2;
1714
1715 if (j == i)
1716 continue;
1717
1718 b_chain = &(*preds)[j];
1719 if (b_chain->length () != 2)
1720 continue;
1721
1722 x2 = (*b_chain)[0];
1723 y2 = (*b_chain)[1];
1724
1725 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1726 {
1727 /* Kill a_chain. */
1728 a_chain->release ();
1729 b_chain->release ();
1730 b_chain->safe_push (x);
1731 simplified = true;
1732 break;
1733 }
1734 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1735 {
1736 /* Kill a_chain. */
1737 a_chain->release ();
1738 b_chain->release ();
1739 b_chain->safe_push (y);
1740 simplified = true;
1741 break;
1742 }
1743 }
1744 }
1745 /* Now clean up the chain. */
1746 if (simplified)
1747 {
1748 for (i = 0; i < n; i++)
1749 {
1750 if ((*preds)[i].is_empty ())
1751 continue;
1752 s_preds.safe_push ((*preds)[i]);
1753 }
1754 preds->release ();
1755 (*preds) = s_preds;
1756 s_preds = vNULL;
1757 }
1758
1759 return simplified;
1760 }
1761
1762 /* The helper function implements the rule 2 for the
1763 OR predicate PREDS.
1764
1765 3) x OR (!x AND y) is equivalent to x OR y. */
1766
1767 static bool
simplify_preds_3(pred_chain_union * preds)1768 simplify_preds_3 (pred_chain_union *preds)
1769 {
1770 size_t i, j, n;
1771 bool simplified = false;
1772
1773 /* Now iteratively simplify X OR (!X AND Z ..)
1774 into X OR (Z ...). */
1775
1776 n = preds->length ();
1777 if (n < 2)
1778 return false;
1779
1780 for (i = 0; i < n; i++)
1781 {
1782 pred_info x;
1783 pred_chain *a_chain = &(*preds)[i];
1784
1785 if (a_chain->length () != 1)
1786 continue;
1787
1788 x = (*a_chain)[0];
1789
1790 for (j = 0; j < n; j++)
1791 {
1792 pred_chain *b_chain;
1793 pred_info x2;
1794 size_t k;
1795
1796 if (j == i)
1797 continue;
1798
1799 b_chain = &(*preds)[j];
1800 if (b_chain->length () < 2)
1801 continue;
1802
1803 for (k = 0; k < b_chain->length (); k++)
1804 {
1805 x2 = (*b_chain)[k];
1806 if (pred_neg_p (x, x2))
1807 {
1808 b_chain->unordered_remove (k);
1809 simplified = true;
1810 break;
1811 }
1812 }
1813 }
1814 }
1815 return simplified;
1816 }
1817
1818 /* The helper function implements the rule 4 for the
1819 OR predicate PREDS.
1820
1821 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1822 (x != 0 ANd y != 0). */
1823
1824 static bool
simplify_preds_4(pred_chain_union * preds)1825 simplify_preds_4 (pred_chain_union *preds)
1826 {
1827 size_t i, j, n;
1828 bool simplified = false;
1829 pred_chain_union s_preds = vNULL;
1830 gimple *def_stmt;
1831
1832 n = preds->length ();
1833 for (i = 0; i < n; i++)
1834 {
1835 pred_info z;
1836 pred_chain *a_chain = &(*preds)[i];
1837
1838 if (a_chain->length () != 1)
1839 continue;
1840
1841 z = (*a_chain)[0];
1842
1843 if (!is_neq_zero_form_p (z))
1844 continue;
1845
1846 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1847 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1848 continue;
1849
1850 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1851 continue;
1852
1853 for (j = 0; j < n; j++)
1854 {
1855 pred_chain *b_chain;
1856 pred_info x2, y2;
1857
1858 if (j == i)
1859 continue;
1860
1861 b_chain = &(*preds)[j];
1862 if (b_chain->length () != 2)
1863 continue;
1864
1865 x2 = (*b_chain)[0];
1866 y2 = (*b_chain)[1];
1867 if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
1868 continue;
1869
1870 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1871 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1872 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1873 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1874 {
1875 /* Kill a_chain. */
1876 a_chain->release ();
1877 simplified = true;
1878 break;
1879 }
1880 }
1881 }
1882 /* Now clean up the chain. */
1883 if (simplified)
1884 {
1885 for (i = 0; i < n; i++)
1886 {
1887 if ((*preds)[i].is_empty ())
1888 continue;
1889 s_preds.safe_push ((*preds)[i]);
1890 }
1891
1892 preds->release ();
1893 (*preds) = s_preds;
1894 s_preds = vNULL;
1895 }
1896
1897 return simplified;
1898 }
1899
1900 /* This function simplifies predicates in PREDS. */
1901
1902 static void
simplify_preds(pred_chain_union * preds,gimple * use_or_def,bool is_use)1903 simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use)
1904 {
1905 size_t i, n;
1906 bool changed = false;
1907
1908 if (dump_file && dump_flags & TDF_DETAILS)
1909 {
1910 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1911 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1912 }
1913
1914 for (i = 0; i < preds->length (); i++)
1915 simplify_pred (&(*preds)[i]);
1916
1917 n = preds->length ();
1918 if (n < 2)
1919 return;
1920
1921 do
1922 {
1923 changed = false;
1924 if (simplify_preds_2 (preds))
1925 changed = true;
1926
1927 /* Now iteratively simplify X OR (!X AND Z ..)
1928 into X OR (Z ...). */
1929 if (simplify_preds_3 (preds))
1930 changed = true;
1931
1932 if (simplify_preds_4 (preds))
1933 changed = true;
1934 }
1935 while (changed);
1936
1937 return;
1938 }
1939
1940 /* This is a helper function which attempts to normalize predicate chains
1941 by following UD chains. It basically builds up a big tree of either IOR
1942 operations or AND operations, and convert the IOR tree into a
1943 pred_chain_union or BIT_AND tree into a pred_chain.
1944 Example:
1945
1946 _3 = _2 RELOP1 _1;
1947 _6 = _5 RELOP2 _4;
1948 _9 = _8 RELOP3 _7;
1949 _10 = _3 | _6;
1950 _12 = _9 | _0;
1951 _t = _10 | _12;
1952
1953 then _t != 0 will be normalized into a pred_chain_union
1954
1955 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1956
1957 Similarly given,
1958
1959 _3 = _2 RELOP1 _1;
1960 _6 = _5 RELOP2 _4;
1961 _9 = _8 RELOP3 _7;
1962 _10 = _3 & _6;
1963 _12 = _9 & _0;
1964
1965 then _t != 0 will be normalized into a pred_chain:
1966 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1967
1968 */
1969
1970 /* This is a helper function that stores a PRED into NORM_PREDS. */
1971
1972 inline static void
push_pred(pred_chain_union * norm_preds,pred_info pred)1973 push_pred (pred_chain_union *norm_preds, pred_info pred)
1974 {
1975 pred_chain pred_chain = vNULL;
1976 pred_chain.safe_push (pred);
1977 norm_preds->safe_push (pred_chain);
1978 }
1979
1980 /* A helper function that creates a predicate of the form
1981 OP != 0 and push it WORK_LIST. */
1982
1983 inline static void
push_to_worklist(tree op,vec<pred_info,va_heap,vl_ptr> * work_list,hash_set<tree> * mark_set)1984 push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1985 hash_set<tree> *mark_set)
1986 {
1987 if (mark_set->contains (op))
1988 return;
1989 mark_set->add (op);
1990
1991 pred_info arg_pred;
1992 arg_pred.pred_lhs = op;
1993 arg_pred.pred_rhs = integer_zero_node;
1994 arg_pred.cond_code = NE_EXPR;
1995 arg_pred.invert = false;
1996 work_list->safe_push (arg_pred);
1997 }
1998
1999 /* A helper that generates a pred_info from a gimple assignment
2000 CMP_ASSIGN with comparison rhs. */
2001
2002 static pred_info
get_pred_info_from_cmp(gimple * cmp_assign)2003 get_pred_info_from_cmp (gimple *cmp_assign)
2004 {
2005 pred_info n_pred;
2006 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
2007 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
2008 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
2009 n_pred.invert = false;
2010 return n_pred;
2011 }
2012
2013 /* Returns true if the PHI is a degenerated phi with
2014 all args with the same value (relop). In that case, *PRED
2015 will be updated to that value. */
2016
2017 static bool
is_degenerated_phi(gimple * phi,pred_info * pred_p)2018 is_degenerated_phi (gimple *phi, pred_info *pred_p)
2019 {
2020 int i, n;
2021 tree op0;
2022 gimple *def0;
2023 pred_info pred0;
2024
2025 n = gimple_phi_num_args (phi);
2026 op0 = gimple_phi_arg_def (phi, 0);
2027
2028 if (TREE_CODE (op0) != SSA_NAME)
2029 return false;
2030
2031 def0 = SSA_NAME_DEF_STMT (op0);
2032 if (gimple_code (def0) != GIMPLE_ASSIGN)
2033 return false;
2034 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
2035 return false;
2036 pred0 = get_pred_info_from_cmp (def0);
2037
2038 for (i = 1; i < n; ++i)
2039 {
2040 gimple *def;
2041 pred_info pred;
2042 tree op = gimple_phi_arg_def (phi, i);
2043
2044 if (TREE_CODE (op) != SSA_NAME)
2045 return false;
2046
2047 def = SSA_NAME_DEF_STMT (op);
2048 if (gimple_code (def) != GIMPLE_ASSIGN)
2049 return false;
2050 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
2051 return false;
2052 pred = get_pred_info_from_cmp (def);
2053 if (!pred_equal_p (pred, pred0))
2054 return false;
2055 }
2056
2057 *pred_p = pred0;
2058 return true;
2059 }
2060
2061 /* Normalize one predicate PRED
2062 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2063 2) otherwise if PRED is of the form x != 0, follow x's definition
2064 and put normalized predicates into WORK_LIST. */
2065
2066 static void
normalize_one_pred_1(pred_chain_union * norm_preds,pred_chain * norm_chain,pred_info pred,enum tree_code and_or_code,vec<pred_info,va_heap,vl_ptr> * work_list,hash_set<tree> * mark_set)2067 normalize_one_pred_1 (pred_chain_union *norm_preds,
2068 pred_chain *norm_chain,
2069 pred_info pred,
2070 enum tree_code and_or_code,
2071 vec<pred_info, va_heap, vl_ptr> *work_list,
2072 hash_set<tree> *mark_set)
2073 {
2074 if (!is_neq_zero_form_p (pred))
2075 {
2076 if (and_or_code == BIT_IOR_EXPR)
2077 push_pred (norm_preds, pred);
2078 else
2079 norm_chain->safe_push (pred);
2080 return;
2081 }
2082
2083 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2084
2085 if (gimple_code (def_stmt) == GIMPLE_PHI
2086 && is_degenerated_phi (def_stmt, &pred))
2087 work_list->safe_push (pred);
2088 else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
2089 {
2090 int i, n;
2091 n = gimple_phi_num_args (def_stmt);
2092
2093 /* If we see non zero constant, we should punt. The predicate
2094 * should be one guarding the phi edge. */
2095 for (i = 0; i < n; ++i)
2096 {
2097 tree op = gimple_phi_arg_def (def_stmt, i);
2098 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
2099 {
2100 push_pred (norm_preds, pred);
2101 return;
2102 }
2103 }
2104
2105 for (i = 0; i < n; ++i)
2106 {
2107 tree op = gimple_phi_arg_def (def_stmt, i);
2108 if (integer_zerop (op))
2109 continue;
2110
2111 push_to_worklist (op, work_list, mark_set);
2112 }
2113 }
2114 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2115 {
2116 if (and_or_code == BIT_IOR_EXPR)
2117 push_pred (norm_preds, pred);
2118 else
2119 norm_chain->safe_push (pred);
2120 }
2121 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
2122 {
2123 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2124 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
2125 {
2126 /* But treat x & 3 as condition. */
2127 if (and_or_code == BIT_AND_EXPR)
2128 {
2129 pred_info n_pred;
2130 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
2131 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
2132 n_pred.cond_code = and_or_code;
2133 n_pred.invert = false;
2134 norm_chain->safe_push (n_pred);
2135 }
2136 }
2137 else
2138 {
2139 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
2140 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
2141 }
2142 }
2143 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
2144 == tcc_comparison)
2145 {
2146 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2147 if (and_or_code == BIT_IOR_EXPR)
2148 push_pred (norm_preds, n_pred);
2149 else
2150 norm_chain->safe_push (n_pred);
2151 }
2152 else
2153 {
2154 if (and_or_code == BIT_IOR_EXPR)
2155 push_pred (norm_preds, pred);
2156 else
2157 norm_chain->safe_push (pred);
2158 }
2159 }
2160
2161 /* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2162
2163 static void
normalize_one_pred(pred_chain_union * norm_preds,pred_info pred)2164 normalize_one_pred (pred_chain_union *norm_preds, pred_info pred)
2165 {
2166 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2167 enum tree_code and_or_code = ERROR_MARK;
2168 pred_chain norm_chain = vNULL;
2169
2170 if (!is_neq_zero_form_p (pred))
2171 {
2172 push_pred (norm_preds, pred);
2173 return;
2174 }
2175
2176 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2177 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2178 and_or_code = gimple_assign_rhs_code (def_stmt);
2179 if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
2180 {
2181 if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
2182 {
2183 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2184 push_pred (norm_preds, n_pred);
2185 }
2186 else
2187 push_pred (norm_preds, pred);
2188 return;
2189 }
2190
2191 work_list.safe_push (pred);
2192 hash_set<tree> mark_set;
2193
2194 while (!work_list.is_empty ())
2195 {
2196 pred_info a_pred = work_list.pop ();
2197 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code,
2198 &work_list, &mark_set);
2199 }
2200 if (and_or_code == BIT_AND_EXPR)
2201 norm_preds->safe_push (norm_chain);
2202
2203 work_list.release ();
2204 }
2205
2206 static void
normalize_one_pred_chain(pred_chain_union * norm_preds,pred_chain one_chain)2207 normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain)
2208 {
2209 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2210 hash_set<tree> mark_set;
2211 pred_chain norm_chain = vNULL;
2212 size_t i;
2213
2214 for (i = 0; i < one_chain.length (); i++)
2215 {
2216 work_list.safe_push (one_chain[i]);
2217 mark_set.add (one_chain[i].pred_lhs);
2218 }
2219
2220 while (!work_list.is_empty ())
2221 {
2222 pred_info a_pred = work_list.pop ();
2223 normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list,
2224 &mark_set);
2225 }
2226
2227 norm_preds->safe_push (norm_chain);
2228 work_list.release ();
2229 }
2230
2231 /* Normalize predicate chains PREDS and returns the normalized one. */
2232
2233 static pred_chain_union
normalize_preds(pred_chain_union preds,gimple * use_or_def,bool is_use)2234 normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
2235 {
2236 pred_chain_union norm_preds = vNULL;
2237 size_t n = preds.length ();
2238 size_t i;
2239
2240 if (dump_file && dump_flags & TDF_DETAILS)
2241 {
2242 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2243 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2244 }
2245
2246 for (i = 0; i < n; i++)
2247 {
2248 if (preds[i].length () != 1)
2249 normalize_one_pred_chain (&norm_preds, preds[i]);
2250 else
2251 {
2252 normalize_one_pred (&norm_preds, preds[i][0]);
2253 preds[i].release ();
2254 }
2255 }
2256
2257 if (dump_file)
2258 {
2259 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2260 dump_predicates (use_or_def, norm_preds,
2261 is_use ? "[USE]:\n" : "[DEF]:\n");
2262 }
2263
2264 destroy_predicate_vecs (&preds);
2265 return norm_preds;
2266 }
2267
2268 /* Return TRUE if PREDICATE can be invalidated by any individual
2269 predicate in USE_GUARD. */
2270
2271 static bool
can_one_predicate_be_invalidated_p(pred_info predicate,pred_chain use_guard)2272 can_one_predicate_be_invalidated_p (pred_info predicate,
2273 pred_chain use_guard)
2274 {
2275 if (dump_file && dump_flags & TDF_DETAILS)
2276 {
2277 fprintf (dump_file, "Testing if this predicate: ");
2278 dump_pred_info (predicate);
2279 fprintf (dump_file, "\n...can be invalidated by a USE guard of: ");
2280 dump_pred_chain (use_guard);
2281 }
2282 for (size_t i = 0; i < use_guard.length (); ++i)
2283 {
2284 /* NOTE: This is a very simple check, and only understands an
2285 exact opposite. So, [i == 0] is currently only invalidated
2286 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2287 invalidate with say [i > 5] or [i == 8]. There is certainly
2288 room for improvement here. */
2289 if (pred_neg_p (predicate, use_guard[i]))
2290 {
2291 if (dump_file && dump_flags & TDF_DETAILS)
2292 {
2293 fprintf (dump_file, " Predicate was invalidated by: ");
2294 dump_pred_info (use_guard[i]);
2295 fputc ('\n', dump_file);
2296 }
2297 return true;
2298 }
2299 }
2300 return false;
2301 }
2302
2303 /* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2304 USE_GUARD being true. */
2305
2306 static bool
can_chain_union_be_invalidated_p(pred_chain_union uninit_pred,pred_chain use_guard)2307 can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
2308 pred_chain use_guard)
2309 {
2310 if (uninit_pred.is_empty ())
2311 return false;
2312 if (dump_file && dump_flags & TDF_DETAILS)
2313 dump_predicates (NULL, uninit_pred,
2314 "Testing if anything here can be invalidated: ");
2315 for (size_t i = 0; i < uninit_pred.length (); ++i)
2316 {
2317 pred_chain c = uninit_pred[i];
2318 size_t j;
2319 for (j = 0; j < c.length (); ++j)
2320 if (can_one_predicate_be_invalidated_p (c[j], use_guard))
2321 break;
2322
2323 /* If we were unable to invalidate any predicate in C, then there
2324 is a viable path from entry to the PHI where the PHI takes
2325 an uninitialized value and continues to a use of the PHI. */
2326 if (j == c.length ())
2327 return false;
2328 }
2329 return true;
2330 }
2331
2332 /* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2333 can actually happen if we arrived at a use for PHI.
2334
2335 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2336
2337 static bool
uninit_uses_cannot_happen(gphi * phi,unsigned uninit_opnds,pred_chain_union phi_use_guards)2338 uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
2339 pred_chain_union phi_use_guards)
2340 {
2341 unsigned phi_args = gimple_phi_num_args (phi);
2342 if (phi_args > max_phi_args)
2343 return false;
2344
2345 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2346 possible guard, there's no way of knowing which guard was true.
2347 Since we need to be absolutely sure that the uninitialized
2348 operands will be invalidated, bail. */
2349 if (phi_use_guards.length () != 1)
2350 return false;
2351
2352 /* Look for the control dependencies of all the uninitialized
2353 operands and build guard predicates describing them. */
2354 pred_chain_union uninit_preds;
2355 bool ret = true;
2356 for (unsigned i = 0; i < phi_args; ++i)
2357 {
2358 if (!MASK_TEST_BIT (uninit_opnds, i))
2359 continue;
2360
2361 edge e = gimple_phi_arg_edge (phi, i);
2362 vec<edge> dep_chains[MAX_NUM_CHAINS];
2363 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
2364 size_t num_chains = 0;
2365 int num_calls = 0;
2366
2367 /* Build the control dependency chain for uninit operand `i'... */
2368 uninit_preds = vNULL;
2369 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun),
2370 e->src, dep_chains, &num_chains,
2371 &cur_chain, &num_calls))
2372 {
2373 ret = false;
2374 break;
2375 }
2376 /* ...and convert it into a set of predicates. */
2377 bool has_valid_preds
2378 = convert_control_dep_chain_into_preds (dep_chains, num_chains,
2379 &uninit_preds);
2380 for (size_t j = 0; j < num_chains; ++j)
2381 dep_chains[j].release ();
2382 if (!has_valid_preds)
2383 {
2384 ret = false;
2385 break;
2386 }
2387 simplify_preds (&uninit_preds, NULL, false);
2388 uninit_preds = normalize_preds (uninit_preds, NULL, false);
2389
2390 /* Can the guard for this uninitialized operand be invalidated
2391 by the PHI use? */
2392 if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0]))
2393 {
2394 ret = false;
2395 break;
2396 }
2397 }
2398 destroy_predicate_vecs (&uninit_preds);
2399 return ret;
2400 }
2401
2402 /* Computes the predicates that guard the use and checks
2403 if the incoming paths that have empty (or possibly
2404 empty) definition can be pruned/filtered. The function returns
2405 true if it can be determined that the use of PHI's def in
2406 USE_STMT is guarded with a predicate set not overlapping with
2407 predicate sets of all runtime paths that do not have a definition.
2408
2409 Returns false if it is not or it cannot be determined. USE_BB is
2410 the bb of the use (for phi operand use, the bb is not the bb of
2411 the phi stmt, but the src bb of the operand edge).
2412
2413 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2414 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2415 set of phis being visited.
2416
2417 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2418 If *DEF_PREDS is the empty vector, the defining predicate chains of
2419 PHI will be computed and stored into *DEF_PREDS as needed.
2420
2421 VISITED_PHIS is a pointer set of phis being visited. */
2422
2423 static bool
is_use_properly_guarded(gimple * use_stmt,basic_block use_bb,gphi * phi,unsigned uninit_opnds,pred_chain_union * def_preds,hash_set<gphi * > * visited_phis)2424 is_use_properly_guarded (gimple *use_stmt,
2425 basic_block use_bb,
2426 gphi *phi,
2427 unsigned uninit_opnds,
2428 pred_chain_union *def_preds,
2429 hash_set<gphi *> *visited_phis)
2430 {
2431 basic_block phi_bb;
2432 pred_chain_union preds = vNULL;
2433 bool has_valid_preds = false;
2434 bool is_properly_guarded = false;
2435
2436 if (visited_phis->add (phi))
2437 return false;
2438
2439 phi_bb = gimple_bb (phi);
2440
2441 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2442 return false;
2443
2444 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2445
2446 if (!has_valid_preds)
2447 {
2448 destroy_predicate_vecs (&preds);
2449 return false;
2450 }
2451
2452 /* Try to prune the dead incoming phi edges. */
2453 is_properly_guarded
2454 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2455 visited_phis);
2456
2457 /* We might be able to prove that if the control dependencies
2458 for UNINIT_OPNDS are true, that the control dependencies for
2459 USE_STMT can never be true. */
2460 if (!is_properly_guarded)
2461 is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds,
2462 preds);
2463
2464 if (is_properly_guarded)
2465 {
2466 destroy_predicate_vecs (&preds);
2467 return true;
2468 }
2469
2470 if (def_preds->is_empty ())
2471 {
2472 has_valid_preds = find_def_preds (def_preds, phi);
2473
2474 if (!has_valid_preds)
2475 {
2476 destroy_predicate_vecs (&preds);
2477 return false;
2478 }
2479
2480 simplify_preds (def_preds, phi, false);
2481 *def_preds = normalize_preds (*def_preds, phi, false);
2482 }
2483
2484 simplify_preds (&preds, use_stmt, true);
2485 preds = normalize_preds (preds, use_stmt, true);
2486
2487 is_properly_guarded = is_superset_of (*def_preds, preds);
2488
2489 destroy_predicate_vecs (&preds);
2490 return is_properly_guarded;
2491 }
2492
2493 /* Searches through all uses of a potentially
2494 uninitialized variable defined by PHI and returns a use
2495 statement if the use is not properly guarded. It returns
2496 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2497 holding the position(s) of uninit PHI operands. WORKLIST
2498 is the vector of candidate phis that may be updated by this
2499 function. ADDED_TO_WORKLIST is the pointer set tracking
2500 if the new phi is already in the worklist. */
2501
2502 static gimple *
find_uninit_use(gphi * phi,unsigned uninit_opnds,vec<gphi * > * worklist,hash_set<gphi * > * added_to_worklist)2503 find_uninit_use (gphi *phi, unsigned uninit_opnds,
2504 vec<gphi *> *worklist,
2505 hash_set<gphi *> *added_to_worklist)
2506 {
2507 tree phi_result;
2508 use_operand_p use_p;
2509 gimple *use_stmt;
2510 imm_use_iterator iter;
2511 pred_chain_union def_preds = vNULL;
2512 gimple *ret = NULL;
2513
2514 phi_result = gimple_phi_result (phi);
2515
2516 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2517 {
2518 basic_block use_bb;
2519
2520 use_stmt = USE_STMT (use_p);
2521 if (is_gimple_debug (use_stmt))
2522 continue;
2523
2524 if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
2525 use_bb = gimple_phi_arg_edge (use_phi,
2526 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2527 else
2528 use_bb = gimple_bb (use_stmt);
2529
2530 hash_set<gphi *> visited_phis;
2531 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2532 &def_preds, &visited_phis))
2533 continue;
2534
2535 if (dump_file && (dump_flags & TDF_DETAILS))
2536 {
2537 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2538 print_gimple_stmt (dump_file, use_stmt, 0);
2539 }
2540 /* Found one real use, return. */
2541 if (gimple_code (use_stmt) != GIMPLE_PHI)
2542 {
2543 ret = use_stmt;
2544 break;
2545 }
2546
2547 /* Found a phi use that is not guarded,
2548 add the phi to the worklist. */
2549 if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
2550 {
2551 if (dump_file && (dump_flags & TDF_DETAILS))
2552 {
2553 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2554 print_gimple_stmt (dump_file, use_stmt, 0);
2555 }
2556
2557 worklist->safe_push (as_a<gphi *> (use_stmt));
2558 possibly_undefined_names->add (phi_result);
2559 }
2560 }
2561
2562 destroy_predicate_vecs (&def_preds);
2563 return ret;
2564 }
2565
2566 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2567 and gives warning if there exists a runtime path from the entry to a
2568 use of the PHI def that does not contain a definition. In other words,
2569 the warning is on the real use. The more dead paths that can be pruned
2570 by the compiler, the fewer false positives the warning is. WORKLIST
2571 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2572 a pointer set tracking if the new phi is added to the worklist or not. */
2573
2574 static void
warn_uninitialized_phi(gphi * phi,vec<gphi * > * worklist,hash_set<gphi * > * added_to_worklist)2575 warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
2576 hash_set<gphi *> *added_to_worklist)
2577 {
2578 unsigned uninit_opnds;
2579 gimple *uninit_use_stmt = 0;
2580 tree uninit_op;
2581 int phiarg_index;
2582 location_t loc;
2583
2584 /* Don't look at virtual operands. */
2585 if (virtual_operand_p (gimple_phi_result (phi)))
2586 return;
2587
2588 uninit_opnds = compute_uninit_opnds_pos (phi);
2589
2590 if (MASK_EMPTY (uninit_opnds))
2591 return;
2592
2593 if (dump_file && (dump_flags & TDF_DETAILS))
2594 {
2595 fprintf (dump_file, "[CHECK]: examining phi: ");
2596 print_gimple_stmt (dump_file, phi, 0);
2597 }
2598
2599 /* Now check if we have any use of the value without proper guard. */
2600 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2601 worklist, added_to_worklist);
2602
2603 /* All uses are properly guarded. */
2604 if (!uninit_use_stmt)
2605 return;
2606
2607 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2608 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2609 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2610 return;
2611 if (gimple_phi_arg_has_location (phi, phiarg_index))
2612 loc = gimple_phi_arg_location (phi, phiarg_index);
2613 else
2614 loc = UNKNOWN_LOCATION;
2615 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2616 SSA_NAME_VAR (uninit_op),
2617 "%qD may be used uninitialized in this function",
2618 uninit_use_stmt, loc);
2619 }
2620
2621 static bool
gate_warn_uninitialized(void)2622 gate_warn_uninitialized (void)
2623 {
2624 return warn_uninitialized || warn_maybe_uninitialized;
2625 }
2626
2627 namespace {
2628
2629 const pass_data pass_data_late_warn_uninitialized =
2630 {
2631 GIMPLE_PASS, /* type */
2632 "uninit", /* name */
2633 OPTGROUP_NONE, /* optinfo_flags */
2634 TV_NONE, /* tv_id */
2635 PROP_ssa, /* properties_required */
2636 0, /* properties_provided */
2637 0, /* properties_destroyed */
2638 0, /* todo_flags_start */
2639 0, /* todo_flags_finish */
2640 };
2641
2642 class pass_late_warn_uninitialized : public gimple_opt_pass
2643 {
2644 public:
pass_late_warn_uninitialized(gcc::context * ctxt)2645 pass_late_warn_uninitialized (gcc::context *ctxt)
2646 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2647 {}
2648
2649 /* opt_pass methods: */
clone()2650 opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); }
gate(function *)2651 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2652 virtual unsigned int execute (function *);
2653
2654 }; // class pass_late_warn_uninitialized
2655
2656 unsigned int
execute(function * fun)2657 pass_late_warn_uninitialized::execute (function *fun)
2658 {
2659 basic_block bb;
2660 gphi_iterator gsi;
2661 vec<gphi *> worklist = vNULL;
2662
2663 calculate_dominance_info (CDI_DOMINATORS);
2664 calculate_dominance_info (CDI_POST_DOMINATORS);
2665 /* Re-do the plain uninitialized variable check, as optimization may have
2666 straightened control flow. Do this first so that we don't accidentally
2667 get a "may be" warning when we'd have seen an "is" warning later. */
2668 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2669
2670 timevar_push (TV_TREE_UNINIT);
2671
2672 possibly_undefined_names = new hash_set<tree>;
2673 hash_set<gphi *> added_to_worklist;
2674
2675 /* Initialize worklist */
2676 FOR_EACH_BB_FN (bb, fun)
2677 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2678 {
2679 gphi *phi = gsi.phi ();
2680 size_t n, i;
2681
2682 n = gimple_phi_num_args (phi);
2683
2684 /* Don't look at virtual operands. */
2685 if (virtual_operand_p (gimple_phi_result (phi)))
2686 continue;
2687
2688 for (i = 0; i < n; ++i)
2689 {
2690 tree op = gimple_phi_arg_def (phi, i);
2691 if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
2692 {
2693 worklist.safe_push (phi);
2694 added_to_worklist.add (phi);
2695 if (dump_file && (dump_flags & TDF_DETAILS))
2696 {
2697 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2698 print_gimple_stmt (dump_file, phi, 0);
2699 }
2700 break;
2701 }
2702 }
2703 }
2704
2705 while (worklist.length () != 0)
2706 {
2707 gphi *cur_phi = 0;
2708 cur_phi = worklist.pop ();
2709 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
2710 }
2711
2712 worklist.release ();
2713 delete possibly_undefined_names;
2714 possibly_undefined_names = NULL;
2715 free_dominance_info (CDI_POST_DOMINATORS);
2716 timevar_pop (TV_TREE_UNINIT);
2717 return 0;
2718 }
2719
2720 } // anon namespace
2721
2722 gimple_opt_pass *
make_pass_late_warn_uninitialized(gcc::context * ctxt)2723 make_pass_late_warn_uninitialized (gcc::context *ctxt)
2724 {
2725 return new pass_late_warn_uninitialized (ctxt);
2726 }
2727
2728 static unsigned int
execute_early_warn_uninitialized(void)2729 execute_early_warn_uninitialized (void)
2730 {
2731 /* Currently, this pass runs always but
2732 execute_late_warn_uninitialized only runs with optimization. With
2733 optimization we want to warn about possible uninitialized as late
2734 as possible, thus don't do it here. However, without
2735 optimization we need to warn here about "may be uninitialized". */
2736 calculate_dominance_info (CDI_POST_DOMINATORS);
2737
2738 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2739
2740 /* Post-dominator information cannot be reliably updated. Free it
2741 after the use. */
2742
2743 free_dominance_info (CDI_POST_DOMINATORS);
2744 return 0;
2745 }
2746
2747 namespace {
2748
2749 const pass_data pass_data_early_warn_uninitialized =
2750 {
2751 GIMPLE_PASS, /* type */
2752 "*early_warn_uninitialized", /* name */
2753 OPTGROUP_NONE, /* optinfo_flags */
2754 TV_TREE_UNINIT, /* tv_id */
2755 PROP_ssa, /* properties_required */
2756 0, /* properties_provided */
2757 0, /* properties_destroyed */
2758 0, /* todo_flags_start */
2759 0, /* todo_flags_finish */
2760 };
2761
2762 class pass_early_warn_uninitialized : public gimple_opt_pass
2763 {
2764 public:
pass_early_warn_uninitialized(gcc::context * ctxt)2765 pass_early_warn_uninitialized (gcc::context *ctxt)
2766 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2767 {}
2768
2769 /* opt_pass methods: */
gate(function *)2770 virtual bool gate (function *) { return gate_warn_uninitialized (); }
execute(function *)2771 virtual unsigned int execute (function *)
2772 {
2773 return execute_early_warn_uninitialized ();
2774 }
2775
2776 }; // class pass_early_warn_uninitialized
2777
2778 } // anon namespace
2779
2780 gimple_opt_pass *
make_pass_early_warn_uninitialized(gcc::context * ctxt)2781 make_pass_early_warn_uninitialized (gcc::context *ctxt)
2782 {
2783 return new pass_early_warn_uninitialized (ctxt);
2784 }
2785