1/* Predicate aware uninitialized variable warning.
2 Copyright (C) 2001-2017 Free Software Foundation, Inc.
3 Contributed by Xinliang David Li <davidxl@google.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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 "params.h"
35#include "tree-cfg.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. */
48const 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. */
53static 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. */
62static int
63get_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. */
77static bool
78has_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
88static inline bool
89uninit_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
120static void
121warn_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 if (warning_at (location, wc, gmsgid, expr))
181 {
182 TREE_NO_WARNING (expr) = 1;
183
184 if (location == DECL_SOURCE_LOCATION (var))
185 return;
186 if (xloc.file != floc.file
187 || linemap_location_before_p (line_table, location, cfun_loc)
188 || linemap_location_before_p (line_table, cfun->function_end_locus,
189 location))
190 inform (DECL_SOURCE_LOCATION (var), "%qD was declared here", var);
191 }
192}
193
194struct check_defs_data
195{
196 /* If we found any may-defs besides must-def clobbers. */
197 bool found_may_defs;
198};
199
200/* Callback for walk_aliased_vdefs. */
201
202static bool
203check_defs (ao_ref *ref, tree vdef, void *data_)
204{
205 check_defs_data *data = (check_defs_data *)data_;
206 gimple *def_stmt = SSA_NAME_DEF_STMT (vdef);
207 /* If this is a clobber then if it is not a kill walk past it. */
208 if (gimple_clobber_p (def_stmt))
209 {
210 if (stmt_kills_ref_p (def_stmt, ref))
211 return true;
212 return false;
213 }
214 /* Found a may-def on this path. */
215 data->found_may_defs = true;
216 return true;
217}
218
219static unsigned int
220warn_uninitialized_vars (bool warn_possibly_uninitialized)
221{
222 gimple_stmt_iterator gsi;
223 basic_block bb;
224 unsigned int vdef_cnt = 0;
225 unsigned int oracle_cnt = 0;
226 unsigned limit = 0;
227
228 FOR_EACH_BB_FN (bb, cfun)
229 {
230 basic_block succ = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
231 bool always_executed = dominated_by_p (CDI_POST_DOMINATORS, succ, bb);
232 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
233 {
234 gimple *stmt = gsi_stmt (gsi);
235 use_operand_p use_p;
236 ssa_op_iter op_iter;
237 tree use;
238
239 if (is_gimple_debug (stmt))
240 continue;
241
242 /* We only do data flow with SSA_NAMEs, so that's all we
243 can warn about. */
244 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, op_iter, SSA_OP_USE)
245 {
246 /* BIT_INSERT_EXPR first operand should not be considered
247 a use for the purpose of uninit warnings. */
248 if (gassign *ass = dyn_cast <gassign *> (stmt))
249 {
250 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
251 && use_p->use == gimple_assign_rhs1_ptr (ass))
252 continue;
253 }
254 use = USE_FROM_PTR (use_p);
255 if (always_executed)
256 warn_uninit (OPT_Wuninitialized, use, SSA_NAME_VAR (use),
257 SSA_NAME_VAR (use),
258 "%qD is used uninitialized in this function", stmt,
259 UNKNOWN_LOCATION);
260 else if (warn_possibly_uninitialized)
261 warn_uninit (OPT_Wmaybe_uninitialized, use, SSA_NAME_VAR (use),
262 SSA_NAME_VAR (use),
263 "%qD may be used uninitialized in this function",
264 stmt, UNKNOWN_LOCATION);
265 }
266
267 /* For limiting the alias walk below we count all
268 vdefs in the function. */
269 if (gimple_vdef (stmt))
270 vdef_cnt++;
271
272 if (gimple_assign_load_p (stmt)
273 && gimple_has_location (stmt))
274 {
275 tree rhs = gimple_assign_rhs1 (stmt);
276 tree lhs = gimple_assign_lhs (stmt);
277 bool has_bit_insert = false;
278 use_operand_p luse_p;
279 imm_use_iterator liter;
280
281 if (TREE_NO_WARNING (rhs))
282 continue;
283
284 ao_ref ref;
285 ao_ref_init (&ref, rhs);
286
287 /* Do not warn if the base was marked so or this is a
288 hard register var. */
289 tree base = ao_ref_base (&ref);
290 if ((VAR_P (base)
291 && DECL_HARD_REGISTER (base))
292 || TREE_NO_WARNING (base))
293 continue;
294
295 /* Do not warn if the access is fully outside of the
296 variable. */
297 if (DECL_P (base)
298 && ref.size != -1
299 && ((ref.max_size == ref.size
300 && ref.offset + ref.size <= 0)
301 || (ref.offset >= 0
302 && DECL_SIZE (base)
303 && TREE_CODE (DECL_SIZE (base)) == INTEGER_CST
304 && compare_tree_int (DECL_SIZE (base),
305 ref.offset) <= 0)))
306 continue;
307
308 /* Do not warn if the access is then used for a BIT_INSERT_EXPR. */
309 if (TREE_CODE (lhs) == SSA_NAME)
310 FOR_EACH_IMM_USE_FAST (luse_p, liter, lhs)
311 {
312 gimple *use_stmt = USE_STMT (luse_p);
313 /* BIT_INSERT_EXPR first operand should not be considered
314 a use for the purpose of uninit warnings. */
315 if (gassign *ass = dyn_cast <gassign *> (use_stmt))
316 {
317 if (gimple_assign_rhs_code (ass) == BIT_INSERT_EXPR
318 && luse_p->use == gimple_assign_rhs1_ptr (ass))
319 {
320 has_bit_insert = true;
321 break;
322 }
323 }
324 }
325 if (has_bit_insert)
326 continue;
327
328 /* Limit the walking to a constant number of stmts after
329 we overcommit quadratic behavior for small functions
330 and O(n) behavior. */
331 if (oracle_cnt > 128 * 128
332 && oracle_cnt > vdef_cnt * 2)
333 limit = 32;
334 check_defs_data data;
335 bool fentry_reached = false;
336 data.found_may_defs = false;
337 use = gimple_vuse (stmt);
338 int res = walk_aliased_vdefs (&ref, use,
339 check_defs, &data, NULL,
340 &fentry_reached, limit);
341 if (res == -1)
342 {
343 oracle_cnt += limit;
344 continue;
345 }
346 oracle_cnt += res;
347 if (data.found_may_defs)
348 continue;
349 /* Do not warn if it can be initialized outside this function.
350 If we did not reach function entry then we found killing
351 clobbers on all paths to entry. */
352 if (fentry_reached
353 /* ??? We'd like to use ref_may_alias_global_p but that
354 excludes global readonly memory and thus we get bougs
355 warnings from p = cond ? "a" : "b" for example. */
356 && (!VAR_P (base)
357 || is_global_var (base)))
358 continue;
359
360 /* We didn't find any may-defs so on all paths either
361 reached function entry or a killing clobber. */
362 location_t location
363 = linemap_resolve_location (line_table, gimple_location (stmt),
364 LRK_SPELLING_LOCATION, NULL);
365 if (always_executed)
366 {
367 if (warning_at (location, OPT_Wuninitialized,
368 "%qE is used uninitialized in this function",
369 rhs))
370 /* ??? This is only effective for decls as in
371 gcc.dg/uninit-B-O0.c. Avoid doing this for
372 maybe-uninit uses as it may hide important
373 locations. */
374 TREE_NO_WARNING (rhs) = 1;
375 }
376 else if (warn_possibly_uninitialized)
377 warning_at (location, OPT_Wmaybe_uninitialized,
378 "%qE may be used uninitialized in this function",
379 rhs);
380 }
381 }
382 }
383
384 return 0;
385}
386
387/* Checks if the operand OPND of PHI is defined by
388 another phi with one operand defined by this PHI,
389 but the rest operands are all defined. If yes,
390 returns true to skip this operand as being
391 redundant. Can be enhanced to be more general. */
392
393static bool
394can_skip_redundant_opnd (tree opnd, gimple *phi)
395{
396 gimple *op_def;
397 tree phi_def;
398 int i, n;
399
400 phi_def = gimple_phi_result (phi);
401 op_def = SSA_NAME_DEF_STMT (opnd);
402 if (gimple_code (op_def) != GIMPLE_PHI)
403 return false;
404 n = gimple_phi_num_args (op_def);
405 for (i = 0; i < n; ++i)
406 {
407 tree op = gimple_phi_arg_def (op_def, i);
408 if (TREE_CODE (op) != SSA_NAME)
409 continue;
410 if (op != phi_def && uninit_undefined_value_p (op))
411 return false;
412 }
413
414 return true;
415}
416
417/* Returns a bit mask holding the positions of arguments in PHI
418 that have empty (or possibly empty) definitions. */
419
420static unsigned
421compute_uninit_opnds_pos (gphi *phi)
422{
423 size_t i, n;
424 unsigned uninit_opnds = 0;
425
426 n = gimple_phi_num_args (phi);
427 /* Bail out for phi with too many args. */
428 if (n > max_phi_args)
429 return 0;
430
431 for (i = 0; i < n; ++i)
432 {
433 tree op = gimple_phi_arg_def (phi, i);
434 if (TREE_CODE (op) == SSA_NAME
435 && uninit_undefined_value_p (op)
436 && !can_skip_redundant_opnd (op, phi))
437 {
438 if (cfun->has_nonlocal_label || cfun->calls_setjmp)
439 {
440 /* Ignore SSA_NAMEs that appear on abnormal edges
441 somewhere. */
442 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
443 continue;
444 }
445 MASK_SET_BIT (uninit_opnds, i);
446 }
447 }
448 return uninit_opnds;
449}
450
451/* Find the immediate postdominator PDOM of the specified
452 basic block BLOCK. */
453
454static inline basic_block
455find_pdom (basic_block block)
456{
457 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
458 return EXIT_BLOCK_PTR_FOR_FN (cfun);
459 else
460 {
461 basic_block bb = get_immediate_dominator (CDI_POST_DOMINATORS, block);
462 if (!bb)
463 return EXIT_BLOCK_PTR_FOR_FN (cfun);
464 return bb;
465 }
466}
467
468/* Find the immediate DOM of the specified basic block BLOCK. */
469
470static inline basic_block
471find_dom (basic_block block)
472{
473 if (block == ENTRY_BLOCK_PTR_FOR_FN (cfun))
474 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
475 else
476 {
477 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, block);
478 if (!bb)
479 return ENTRY_BLOCK_PTR_FOR_FN (cfun);
480 return bb;
481 }
482}
483
484/* Returns true if BB1 is postdominating BB2 and BB1 is
485 not a loop exit bb. The loop exit bb check is simple and does
486 not cover all cases. */
487
488static bool
489is_non_loop_exit_postdominating (basic_block bb1, basic_block bb2)
490{
491 if (!dominated_by_p (CDI_POST_DOMINATORS, bb2, bb1))
492 return false;
493
494 if (single_pred_p (bb1) && !single_succ_p (bb2))
495 return false;
496
497 return true;
498}
499
500/* Find the closest postdominator of a specified BB, which is control
501 equivalent to BB. */
502
503static inline basic_block
504find_control_equiv_block (basic_block bb)
505{
506 basic_block pdom;
507
508 pdom = find_pdom (bb);
509
510 /* Skip the postdominating bb that is also loop exit. */
511 if (!is_non_loop_exit_postdominating (pdom, bb))
512 return NULL;
513
514 if (dominated_by_p (CDI_DOMINATORS, pdom, bb))
515 return pdom;
516
517 return NULL;
518}
519
520#define MAX_NUM_CHAINS 8
521#define MAX_CHAIN_LEN 5
522#define MAX_POSTDOM_CHECK 8
523#define MAX_SWITCH_CASES 40
524
525/* Computes the control dependence chains (paths of edges)
526 for DEP_BB up to the dominating basic block BB (the head node of a
527 chain should be dominated by it). CD_CHAINS is pointer to an
528 array holding the result chains. CUR_CD_CHAIN is the current
529 chain being computed. *NUM_CHAINS is total number of chains. The
530 function returns true if the information is successfully computed,
531 return false if there is no control dependence or not computed. */
532
533static bool
534compute_control_dep_chain (basic_block bb, basic_block dep_bb,
535 vec<edge> *cd_chains,
536 size_t *num_chains,
537 vec<edge> *cur_cd_chain,
538 int *num_calls)
539{
540 edge_iterator ei;
541 edge e;
542 size_t i;
543 bool found_cd_chain = false;
544 size_t cur_chain_len = 0;
545
546 if (EDGE_COUNT (bb->succs) < 2)
547 return false;
548
549 if (*num_calls > PARAM_VALUE (PARAM_UNINIT_CONTROL_DEP_ATTEMPTS))
550 return false;
551 ++*num_calls;
552
553 /* Could use a set instead. */
554 cur_chain_len = cur_cd_chain->length ();
555 if (cur_chain_len > MAX_CHAIN_LEN)
556 return false;
557
558 for (i = 0; i < cur_chain_len; i++)
559 {
560 edge e = (*cur_cd_chain)[i];
561 /* Cycle detected. */
562 if (e->src == bb)
563 return false;
564 }
565
566 FOR_EACH_EDGE (e, ei, bb->succs)
567 {
568 basic_block cd_bb;
569 int post_dom_check = 0;
570 if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL))
571 continue;
572
573 cd_bb = e->dest;
574 cur_cd_chain->safe_push (e);
575 while (!is_non_loop_exit_postdominating (cd_bb, bb))
576 {
577 if (cd_bb == dep_bb)
578 {
579 /* Found a direct control dependence. */
580 if (*num_chains < MAX_NUM_CHAINS)
581 {
582 cd_chains[*num_chains] = cur_cd_chain->copy ();
583 (*num_chains)++;
584 }
585 found_cd_chain = true;
586 /* Check path from next edge. */
587 break;
588 }
589
590 /* Now check if DEP_BB is indirectly control dependent on BB. */
591 if (compute_control_dep_chain (cd_bb, dep_bb, cd_chains, num_chains,
592 cur_cd_chain, num_calls))
593 {
594 found_cd_chain = true;
595 break;
596 }
597
598 cd_bb = find_pdom (cd_bb);
599 post_dom_check++;
600 if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
601 || post_dom_check > MAX_POSTDOM_CHECK)
602 break;
603 }
604 cur_cd_chain->pop ();
605 gcc_assert (cur_cd_chain->length () == cur_chain_len);
606 }
607 gcc_assert (cur_cd_chain->length () == cur_chain_len);
608
609 return found_cd_chain;
610}
611
612/* The type to represent a simple predicate. */
613
614struct pred_info
615{
616 tree pred_lhs;
617 tree pred_rhs;
618 enum tree_code cond_code;
619 bool invert;
620};
621
622/* The type to represent a sequence of predicates grouped
623 with .AND. operation. */
624
625typedef vec<pred_info, va_heap, vl_ptr> pred_chain;
626
627/* The type to represent a sequence of pred_chains grouped
628 with .OR. operation. */
629
630typedef vec<pred_chain, va_heap, vl_ptr> pred_chain_union;
631
632/* Converts the chains of control dependence edges into a set of
633 predicates. A control dependence chain is represented by a vector
634 edges. DEP_CHAINS points to an array of dependence chains.
635 NUM_CHAINS is the size of the chain array. One edge in a dependence
636 chain is mapped to predicate expression represented by pred_info
637 type. One dependence chain is converted to a composite predicate that
638 is the result of AND operation of pred_info mapped to each edge.
639 A composite predicate is presented by a vector of pred_info. On
640 return, *PREDS points to the resulting array of composite predicates.
641 *NUM_PREDS is the number of composite predictes. */
642
643static bool
644convert_control_dep_chain_into_preds (vec<edge> *dep_chains,
645 size_t num_chains,
646 pred_chain_union *preds)
647{
648 bool has_valid_pred = false;
649 size_t i, j;
650 if (num_chains == 0 || num_chains >= MAX_NUM_CHAINS)
651 return false;
652
653 /* Now convert the control dep chain into a set
654 of predicates. */
655 preds->reserve (num_chains);
656
657 for (i = 0; i < num_chains; i++)
658 {
659 vec<edge> one_cd_chain = dep_chains[i];
660
661 has_valid_pred = false;
662 pred_chain t_chain = vNULL;
663 for (j = 0; j < one_cd_chain.length (); j++)
664 {
665 gimple *cond_stmt;
666 gimple_stmt_iterator gsi;
667 basic_block guard_bb;
668 pred_info one_pred;
669 edge e;
670
671 e = one_cd_chain[j];
672 guard_bb = e->src;
673 gsi = gsi_last_bb (guard_bb);
674 if (gsi_end_p (gsi))
675 {
676 has_valid_pred = false;
677 break;
678 }
679 cond_stmt = gsi_stmt (gsi);
680 if (is_gimple_call (cond_stmt) && EDGE_COUNT (e->src->succs) >= 2)
681 /* Ignore EH edge. Can add assertion on the other edge's flag. */
682 continue;
683 /* Skip if there is essentially one succesor. */
684 if (EDGE_COUNT (e->src->succs) == 2)
685 {
686 edge e1;
687 edge_iterator ei1;
688 bool skip = false;
689
690 FOR_EACH_EDGE (e1, ei1, e->src->succs)
691 {
692 if (EDGE_COUNT (e1->dest->succs) == 0)
693 {
694 skip = true;
695 break;
696 }
697 }
698 if (skip)
699 continue;
700 }
701 if (gimple_code (cond_stmt) == GIMPLE_COND)
702 {
703 one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
704 one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
705 one_pred.cond_code = gimple_cond_code (cond_stmt);
706 one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
707 t_chain.safe_push (one_pred);
708 has_valid_pred = true;
709 }
710 else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
711 {
712 /* Avoid quadratic behavior. */
713 if (gimple_switch_num_labels (gs) > MAX_SWITCH_CASES)
714 {
715 has_valid_pred = false;
716 break;
717 }
718 /* Find the case label. */
719 tree l = NULL_TREE;
720 unsigned idx;
721 for (idx = 0; idx < gimple_switch_num_labels (gs); ++idx)
722 {
723 tree tl = gimple_switch_label (gs, idx);
724 if (e->dest == label_to_block (CASE_LABEL (tl)))
725 {
726 if (!l)
727 l = tl;
728 else
729 {
730 l = NULL_TREE;
731 break;
732 }
733 }
734 }
735 /* If more than one label reaches this block or the case
736 label doesn't have a single value (like the default one)
737 fail. */
738 if (!l
739 || !CASE_LOW (l)
740 || (CASE_HIGH (l)
741 && !operand_equal_p (CASE_LOW (l), CASE_HIGH (l), 0)))
742 {
743 has_valid_pred = false;
744 break;
745 }
746 one_pred.pred_lhs = gimple_switch_index (gs);
747 one_pred.pred_rhs = CASE_LOW (l);
748 one_pred.cond_code = EQ_EXPR;
749 one_pred.invert = false;
750 t_chain.safe_push (one_pred);
751 has_valid_pred = true;
752 }
753 else
754 {
755 has_valid_pred = false;
756 break;
757 }
758 }
759
760 if (!has_valid_pred)
761 break;
762 else
763 preds->safe_push (t_chain);
764 }
765 return has_valid_pred;
766}
767
768/* Computes all control dependence chains for USE_BB. The control
769 dependence chains are then converted to an array of composite
770 predicates pointed to by PREDS. PHI_BB is the basic block of
771 the phi whose result is used in USE_BB. */
772
773static bool
774find_predicates (pred_chain_union *preds,
775 basic_block phi_bb,
776 basic_block use_bb)
777{
778 size_t num_chains = 0, i;
779 int num_calls = 0;
780 vec<edge> dep_chains[MAX_NUM_CHAINS];
781 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
782 bool has_valid_pred = false;
783 basic_block cd_root = 0;
784
785 /* First find the closest bb that is control equivalent to PHI_BB
786 that also dominates USE_BB. */
787 cd_root = phi_bb;
788 while (dominated_by_p (CDI_DOMINATORS, use_bb, cd_root))
789 {
790 basic_block ctrl_eq_bb = find_control_equiv_block (cd_root);
791 if (ctrl_eq_bb && dominated_by_p (CDI_DOMINATORS, use_bb, ctrl_eq_bb))
792 cd_root = ctrl_eq_bb;
793 else
794 break;
795 }
796
797 compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
798 &cur_chain, &num_calls);
799
800 has_valid_pred
801 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
802 for (i = 0; i < num_chains; i++)
803 dep_chains[i].release ();
804 return has_valid_pred;
805}
806
807/* Computes the set of incoming edges of PHI that have non empty
808 definitions of a phi chain. The collection will be done
809 recursively on operands that are defined by phis. CD_ROOT
810 is the control dependence root. *EDGES holds the result, and
811 VISITED_PHIS is a pointer set for detecting cycles. */
812
813static void
814collect_phi_def_edges (gphi *phi, basic_block cd_root,
815 auto_vec<edge> *edges,
816 hash_set<gimple *> *visited_phis)
817{
818 size_t i, n;
819 edge opnd_edge;
820 tree opnd;
821
822 if (visited_phis->add (phi))
823 return;
824
825 n = gimple_phi_num_args (phi);
826 for (i = 0; i < n; i++)
827 {
828 opnd_edge = gimple_phi_arg_edge (phi, i);
829 opnd = gimple_phi_arg_def (phi, i);
830
831 if (TREE_CODE (opnd) != SSA_NAME)
832 {
833 if (dump_file && (dump_flags & TDF_DETAILS))
834 {
835 fprintf (dump_file, "\n[CHECK] Found def edge %d in ", (int) i);
836 print_gimple_stmt (dump_file, phi, 0);
837 }
838 edges->safe_push (opnd_edge);
839 }
840 else
841 {
842 gimple *def = SSA_NAME_DEF_STMT (opnd);
843
844 if (gimple_code (def) == GIMPLE_PHI
845 && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
846 collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
847 visited_phis);
848 else if (!uninit_undefined_value_p (opnd))
849 {
850 if (dump_file && (dump_flags & TDF_DETAILS))
851 {
852 fprintf (dump_file, "\n[CHECK] Found def edge %d in ",
853 (int) i);
854 print_gimple_stmt (dump_file, phi, 0);
855 }
856 edges->safe_push (opnd_edge);
857 }
858 }
859 }
860}
861
862/* For each use edge of PHI, computes all control dependence chains.
863 The control dependence chains are then converted to an array of
864 composite predicates pointed to by PREDS. */
865
866static bool
867find_def_preds (pred_chain_union *preds, gphi *phi)
868{
869 size_t num_chains = 0, i, n;
870 vec<edge> dep_chains[MAX_NUM_CHAINS];
871 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
872 auto_vec<edge> def_edges;
873 bool has_valid_pred = false;
874 basic_block phi_bb, cd_root = 0;
875
876 phi_bb = gimple_bb (phi);
877 /* First find the closest dominating bb to be
878 the control dependence root. */
879 cd_root = find_dom (phi_bb);
880 if (!cd_root)
881 return false;
882
883 hash_set<gimple *> visited_phis;
884 collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
885
886 n = def_edges.length ();
887 if (n == 0)
888 return false;
889
890 for (i = 0; i < n; i++)
891 {
892 size_t prev_nc, j;
893 int num_calls = 0;
894 edge opnd_edge;
895
896 opnd_edge = def_edges[i];
897 prev_nc = num_chains;
898 compute_control_dep_chain (cd_root, opnd_edge->src, dep_chains,
899 &num_chains, &cur_chain, &num_calls);
900
901 /* Now update the newly added chains with
902 the phi operand edge: */
903 if (EDGE_COUNT (opnd_edge->src->succs) > 1)
904 {
905 if (prev_nc == num_chains && num_chains < MAX_NUM_CHAINS)
906 dep_chains[num_chains++] = vNULL;
907 for (j = prev_nc; j < num_chains; j++)
908 dep_chains[j].safe_push (opnd_edge);
909 }
910 }
911
912 has_valid_pred
913 = convert_control_dep_chain_into_preds (dep_chains, num_chains, preds);
914 for (i = 0; i < num_chains; i++)
915 dep_chains[i].release ();
916 return has_valid_pred;
917}
918
919/* Dumps the predicates (PREDS) for USESTMT. */
920
921static void
922dump_predicates (gimple *usestmt, pred_chain_union preds, const char *msg)
923{
924 size_t i, j;
925 pred_chain one_pred_chain = vNULL;
926 fprintf (dump_file, "%s", msg);
927 print_gimple_stmt (dump_file, usestmt, 0);
928 fprintf (dump_file, "is guarded by :\n\n");
929 size_t num_preds = preds.length ();
930 /* Do some dumping here: */
931 for (i = 0; i < num_preds; i++)
932 {
933 size_t np;
934
935 one_pred_chain = preds[i];
936 np = one_pred_chain.length ();
937
938 for (j = 0; j < np; j++)
939 {
940 pred_info one_pred = one_pred_chain[j];
941 if (one_pred.invert)
942 fprintf (dump_file, " (.NOT.) ");
943 print_generic_expr (dump_file, one_pred.pred_lhs);
944 fprintf (dump_file, " %s ", op_symbol_code (one_pred.cond_code));
945 print_generic_expr (dump_file, one_pred.pred_rhs);
946 if (j < np - 1)
947 fprintf (dump_file, " (.AND.) ");
948 else
949 fprintf (dump_file, "\n");
950 }
951 if (i < num_preds - 1)
952 fprintf (dump_file, "(.OR.)\n");
953 else
954 fprintf (dump_file, "\n\n");
955 }
956}
957
958/* Destroys the predicate set *PREDS. */
959
960static void
961destroy_predicate_vecs (pred_chain_union *preds)
962{
963 size_t i;
964
965 size_t n = preds->length ();
966 for (i = 0; i < n; i++)
967 (*preds)[i].release ();
968 preds->release ();
969}
970
971/* Computes the 'normalized' conditional code with operand
972 swapping and condition inversion. */
973
974static enum tree_code
975get_cmp_code (enum tree_code orig_cmp_code, bool swap_cond, bool invert)
976{
977 enum tree_code tc = orig_cmp_code;
978
979 if (swap_cond)
980 tc = swap_tree_comparison (orig_cmp_code);
981 if (invert)
982 tc = invert_tree_comparison (tc, false);
983
984 switch (tc)
985 {
986 case LT_EXPR:
987 case LE_EXPR:
988 case GT_EXPR:
989 case GE_EXPR:
990 case EQ_EXPR:
991 case NE_EXPR:
992 break;
993 default:
994 return ERROR_MARK;
995 }
996 return tc;
997}
998
999/* Returns true if VAL falls in the range defined by BOUNDARY and CMPC, i.e.
1000 all values in the range satisfies (x CMPC BOUNDARY) == true. */
1001
1002static bool
1003is_value_included_in (tree val, tree boundary, enum tree_code cmpc)
1004{
1005 bool inverted = false;
1006 bool is_unsigned;
1007 bool result;
1008
1009 /* Only handle integer constant here. */
1010 if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
1011 return true;
1012
1013 is_unsigned = TYPE_UNSIGNED (TREE_TYPE (val));
1014
1015 if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
1016 {
1017 cmpc = invert_tree_comparison (cmpc, false);
1018 inverted = true;
1019 }
1020
1021 if (is_unsigned)
1022 {
1023 if (cmpc == EQ_EXPR)
1024 result = tree_int_cst_equal (val, boundary);
1025 else if (cmpc == LT_EXPR)
1026 result = tree_int_cst_lt (val, boundary);
1027 else
1028 {
1029 gcc_assert (cmpc == LE_EXPR);
1030 result = tree_int_cst_le (val, boundary);
1031 }
1032 }
1033 else
1034 {
1035 if (cmpc == EQ_EXPR)
1036 result = tree_int_cst_equal (val, boundary);
1037 else if (cmpc == LT_EXPR)
1038 result = tree_int_cst_lt (val, boundary);
1039 else
1040 {
1041 gcc_assert (cmpc == LE_EXPR);
1042 result = (tree_int_cst_equal (val, boundary)
1043 || tree_int_cst_lt (val, boundary));
1044 }
1045 }
1046
1047 if (inverted)
1048 result ^= 1;
1049
1050 return result;
1051}
1052
1053/* Returns true if PRED is common among all the predicate
1054 chains (PREDS) (and therefore can be factored out).
1055 NUM_PRED_CHAIN is the size of array PREDS. */
1056
1057static bool
1058find_matching_predicate_in_rest_chains (pred_info pred,
1059 pred_chain_union preds,
1060 size_t num_pred_chains)
1061{
1062 size_t i, j, n;
1063
1064 /* Trival case. */
1065 if (num_pred_chains == 1)
1066 return true;
1067
1068 for (i = 1; i < num_pred_chains; i++)
1069 {
1070 bool found = false;
1071 pred_chain one_chain = preds[i];
1072 n = one_chain.length ();
1073 for (j = 0; j < n; j++)
1074 {
1075 pred_info pred2 = one_chain[j];
1076 /* Can relax the condition comparison to not
1077 use address comparison. However, the most common
1078 case is that multiple control dependent paths share
1079 a common path prefix, so address comparison should
1080 be ok. */
1081
1082 if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
1083 && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
1084 && pred2.invert == pred.invert)
1085 {
1086 found = true;
1087 break;
1088 }
1089 }
1090 if (!found)
1091 return false;
1092 }
1093 return true;
1094}
1095
1096/* Forward declaration. */
1097static bool is_use_properly_guarded (gimple *use_stmt,
1098 basic_block use_bb,
1099 gphi *phi,
1100 unsigned uninit_opnds,
1101 pred_chain_union *def_preds,
1102 hash_set<gphi *> *visited_phis);
1103
1104/* Returns true if all uninitialized opnds are pruned. Returns false
1105 otherwise. PHI is the phi node with uninitialized operands,
1106 UNINIT_OPNDS is the bitmap of the uninitialize operand positions,
1107 FLAG_DEF is the statement defining the flag guarding the use of the
1108 PHI output, BOUNDARY_CST is the const value used in the predicate
1109 associated with the flag, CMP_CODE is the comparison code used in
1110 the predicate, VISITED_PHIS is the pointer set of phis visited, and
1111 VISITED_FLAG_PHIS is the pointer to the pointer set of flag definitions
1112 that are also phis.
1113
1114 Example scenario:
1115
1116 BB1:
1117 flag_1 = phi <0, 1> // (1)
1118 var_1 = phi <undef, some_val>
1119
1120
1121 BB2:
1122 flag_2 = phi <0, flag_1, flag_1> // (2)
1123 var_2 = phi <undef, var_1, var_1>
1124 if (flag_2 == 1)
1125 goto BB3;
1126
1127 BB3:
1128 use of var_2 // (3)
1129
1130 Because some flag arg in (1) is not constant, if we do not look into the
1131 flag phis recursively, it is conservatively treated as unknown and var_1
1132 is thought to be flowed into use at (3). Since var_1 is potentially
1133 uninitialized a false warning will be emitted.
1134 Checking recursively into (1), the compiler can find out that only some_val
1135 (which is defined) can flow into (3) which is OK. */
1136
1137static bool
1138prune_uninit_phi_opnds (gphi *phi, unsigned uninit_opnds, gphi *flag_def,
1139 tree boundary_cst, enum tree_code cmp_code,
1140 hash_set<gphi *> *visited_phis,
1141 bitmap *visited_flag_phis)
1142{
1143 unsigned i;
1144
1145 for (i = 0; i < MIN (max_phi_args, gimple_phi_num_args (flag_def)); i++)
1146 {
1147 tree flag_arg;
1148
1149 if (!MASK_TEST_BIT (uninit_opnds, i))
1150 continue;
1151
1152 flag_arg = gimple_phi_arg_def (flag_def, i);
1153 if (!is_gimple_constant (flag_arg))
1154 {
1155 gphi *flag_arg_def, *phi_arg_def;
1156 tree phi_arg;
1157 unsigned uninit_opnds_arg_phi;
1158
1159 if (TREE_CODE (flag_arg) != SSA_NAME)
1160 return false;
1161 flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
1162 if (!flag_arg_def)
1163 return false;
1164
1165 phi_arg = gimple_phi_arg_def (phi, i);
1166 if (TREE_CODE (phi_arg) != SSA_NAME)
1167 return false;
1168
1169 phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
1170 if (!phi_arg_def)
1171 return false;
1172
1173 if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
1174 return false;
1175
1176 if (!*visited_flag_phis)
1177 *visited_flag_phis = BITMAP_ALLOC (NULL);
1178
1179 tree phi_result = gimple_phi_result (flag_arg_def);
1180 if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
1181 return false;
1182
1183 bitmap_set_bit (*visited_flag_phis,
1184 SSA_NAME_VERSION (gimple_phi_result (flag_arg_def)));
1185
1186 /* Now recursively prune the uninitialized phi args. */
1187 uninit_opnds_arg_phi = compute_uninit_opnds_pos (phi_arg_def);
1188 if (!prune_uninit_phi_opnds
1189 (phi_arg_def, uninit_opnds_arg_phi, flag_arg_def, boundary_cst,
1190 cmp_code, visited_phis, visited_flag_phis))
1191 return false;
1192
1193 phi_result = gimple_phi_result (flag_arg_def);
1194 bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
1195 continue;
1196 }
1197
1198 /* Now check if the constant is in the guarded range. */
1199 if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
1200 {
1201 tree opnd;
1202 gimple *opnd_def;
1203
1204 /* Now that we know that this undefined edge is not
1205 pruned. If the operand is defined by another phi,
1206 we can further prune the incoming edges of that
1207 phi by checking the predicates of this operands. */
1208
1209 opnd = gimple_phi_arg_def (phi, i);
1210 opnd_def = SSA_NAME_DEF_STMT (opnd);
1211 if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
1212 {
1213 edge opnd_edge;
1214 unsigned uninit_opnds2 = compute_uninit_opnds_pos (opnd_def_phi);
1215 if (!MASK_EMPTY (uninit_opnds2))
1216 {
1217 pred_chain_union def_preds = vNULL;
1218 bool ok;
1219 opnd_edge = gimple_phi_arg_edge (phi, i);
1220 ok = is_use_properly_guarded (phi,
1221 opnd_edge->src,
1222 opnd_def_phi,
1223 uninit_opnds2,
1224 &def_preds,
1225 visited_phis);
1226 destroy_predicate_vecs (&def_preds);
1227 if (!ok)
1228 return false;
1229 }
1230 }
1231 else
1232 return false;
1233 }
1234 }
1235
1236 return true;
1237}
1238
1239/* A helper function that determines if the predicate set
1240 of the use is not overlapping with that of the uninit paths.
1241 The most common senario of guarded use is in Example 1:
1242 Example 1:
1243 if (some_cond)
1244 {
1245 x = ...;
1246 flag = true;
1247 }
1248
1249 ... some code ...
1250
1251 if (flag)
1252 use (x);
1253
1254 The real world examples are usually more complicated, but similar
1255 and usually result from inlining:
1256
1257 bool init_func (int * x)
1258 {
1259 if (some_cond)
1260 return false;
1261 *x = ..
1262 return true;
1263 }
1264
1265 void foo (..)
1266 {
1267 int x;
1268
1269 if (!init_func (&x))
1270 return;
1271
1272 .. some_code ...
1273 use (x);
1274 }
1275
1276 Another possible use scenario is in the following trivial example:
1277
1278 Example 2:
1279 if (n > 0)
1280 x = 1;
1281 ...
1282 if (n > 0)
1283 {
1284 if (m < 2)
1285 .. = x;
1286 }
1287
1288 Predicate analysis needs to compute the composite predicate:
1289
1290 1) 'x' use predicate: (n > 0) .AND. (m < 2)
1291 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
1292 (the predicate chain for phi operand defs can be computed
1293 starting from a bb that is control equivalent to the phi's
1294 bb and is dominating the operand def.)
1295
1296 and check overlapping:
1297 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
1298 <==> false
1299
1300 This implementation provides framework that can handle
1301 scenarios. (Note that many simple cases are handled properly
1302 without the predicate analysis -- this is due to jump threading
1303 transformation which eliminates the merge point thus makes
1304 path sensitive analysis unnecessary.)
1305
1306 PHI is the phi node whose incoming (undefined) paths need to be
1307 pruned, and UNINIT_OPNDS is the bitmap holding uninit operand
1308 positions. VISITED_PHIS is the pointer set of phi stmts being
1309 checked. */
1310
1311static bool
1312use_pred_not_overlap_with_undef_path_pred (pred_chain_union preds,
1313 gphi *phi, unsigned uninit_opnds,
1314 hash_set<gphi *> *visited_phis)
1315{
1316 unsigned int i, n;
1317 gimple *flag_def = 0;
1318 tree boundary_cst = 0;
1319 enum tree_code cmp_code;
1320 bool swap_cond = false;
1321 bool invert = false;
1322 pred_chain the_pred_chain = vNULL;
1323 bitmap visited_flag_phis = NULL;
1324 bool all_pruned = false;
1325 size_t num_preds = preds.length ();
1326
1327 gcc_assert (num_preds > 0);
1328 /* Find within the common prefix of multiple predicate chains
1329 a predicate that is a comparison of a flag variable against
1330 a constant. */
1331 the_pred_chain = preds[0];
1332 n = the_pred_chain.length ();
1333 for (i = 0; i < n; i++)
1334 {
1335 tree cond_lhs, cond_rhs, flag = 0;
1336
1337 pred_info the_pred = the_pred_chain[i];
1338
1339 invert = the_pred.invert;
1340 cond_lhs = the_pred.pred_lhs;
1341 cond_rhs = the_pred.pred_rhs;
1342 cmp_code = the_pred.cond_code;
1343
1344 if (cond_lhs != NULL_TREE && TREE_CODE (cond_lhs) == SSA_NAME
1345 && cond_rhs != NULL_TREE && is_gimple_constant (cond_rhs))
1346 {
1347 boundary_cst = cond_rhs;
1348 flag = cond_lhs;
1349 }
1350 else if (cond_rhs != NULL_TREE && TREE_CODE (cond_rhs) == SSA_NAME
1351 && cond_lhs != NULL_TREE && is_gimple_constant (cond_lhs))
1352 {
1353 boundary_cst = cond_lhs;
1354 flag = cond_rhs;
1355 swap_cond = true;
1356 }
1357
1358 if (!flag)
1359 continue;
1360
1361 flag_def = SSA_NAME_DEF_STMT (flag);
1362
1363 if (!flag_def)
1364 continue;
1365
1366 if ((gimple_code (flag_def) == GIMPLE_PHI)
1367 && (gimple_bb (flag_def) == gimple_bb (phi))
1368 && find_matching_predicate_in_rest_chains (the_pred, preds,
1369 num_preds))
1370 break;
1371
1372 flag_def = 0;
1373 }
1374
1375 if (!flag_def)
1376 return false;
1377
1378 /* Now check all the uninit incoming edge has a constant flag value
1379 that is in conflict with the use guard/predicate. */
1380 cmp_code = get_cmp_code (cmp_code, swap_cond, invert);
1381
1382 if (cmp_code == ERROR_MARK)
1383 return false;
1384
1385 all_pruned = prune_uninit_phi_opnds
1386 (phi, uninit_opnds, as_a<gphi *> (flag_def), boundary_cst, cmp_code,
1387 visited_phis, &visited_flag_phis);
1388
1389 if (visited_flag_phis)
1390 BITMAP_FREE (visited_flag_phis);
1391
1392 return all_pruned;
1393}
1394
1395/* The helper function returns true if two predicates X1 and X2
1396 are equivalent. It assumes the expressions have already
1397 properly re-associated. */
1398
1399static inline bool
1400pred_equal_p (pred_info x1, pred_info x2)
1401{
1402 enum tree_code c1, c2;
1403 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1404 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1405 return false;
1406
1407 c1 = x1.cond_code;
1408 if (x1.invert != x2.invert
1409 && TREE_CODE_CLASS (x2.cond_code) == tcc_comparison)
1410 c2 = invert_tree_comparison (x2.cond_code, false);
1411 else
1412 c2 = x2.cond_code;
1413
1414 return c1 == c2;
1415}
1416
1417/* Returns true if the predication is testing !=. */
1418
1419static inline bool
1420is_neq_relop_p (pred_info pred)
1421{
1422
1423 return ((pred.cond_code == NE_EXPR && !pred.invert)
1424 || (pred.cond_code == EQ_EXPR && pred.invert));
1425}
1426
1427/* Returns true if pred is of the form X != 0. */
1428
1429static inline bool
1430is_neq_zero_form_p (pred_info pred)
1431{
1432 if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
1433 || TREE_CODE (pred.pred_lhs) != SSA_NAME)
1434 return false;
1435 return true;
1436}
1437
1438/* The helper function returns true if two predicates X1
1439 is equivalent to X2 != 0. */
1440
1441static inline bool
1442pred_expr_equal_p (pred_info x1, tree x2)
1443{
1444 if (!is_neq_zero_form_p (x1))
1445 return false;
1446
1447 return operand_equal_p (x1.pred_lhs, x2, 0);
1448}
1449
1450/* Returns true of the domain of single predicate expression
1451 EXPR1 is a subset of that of EXPR2. Returns false if it
1452 can not be proved. */
1453
1454static bool
1455is_pred_expr_subset_of (pred_info expr1, pred_info expr2)
1456{
1457 enum tree_code code1, code2;
1458
1459 if (pred_equal_p (expr1, expr2))
1460 return true;
1461
1462 if ((TREE_CODE (expr1.pred_rhs) != INTEGER_CST)
1463 || (TREE_CODE (expr2.pred_rhs) != INTEGER_CST))
1464 return false;
1465
1466 if (!operand_equal_p (expr1.pred_lhs, expr2.pred_lhs, 0))
1467 return false;
1468
1469 code1 = expr1.cond_code;
1470 if (expr1.invert)
1471 code1 = invert_tree_comparison (code1, false);
1472 code2 = expr2.cond_code;
1473 if (expr2.invert)
1474 code2 = invert_tree_comparison (code2, false);
1475
1476 if ((code1 == EQ_EXPR || code1 == BIT_AND_EXPR) && code2 == BIT_AND_EXPR)
1477 return (wi::to_wide (expr1.pred_rhs)
1478 == (wi::to_wide (expr1.pred_rhs) & wi::to_wide (expr2.pred_rhs)));
1479
1480 if (code1 != code2 && code2 != NE_EXPR)
1481 return false;
1482
1483 if (is_value_included_in (expr1.pred_rhs, expr2.pred_rhs, code2))
1484 return true;
1485
1486 return false;
1487}
1488
1489/* Returns true if the domain of PRED1 is a subset
1490 of that of PRED2. Returns false if it can not be proved so. */
1491
1492static bool
1493is_pred_chain_subset_of (pred_chain pred1, pred_chain pred2)
1494{
1495 size_t np1, np2, i1, i2;
1496
1497 np1 = pred1.length ();
1498 np2 = pred2.length ();
1499
1500 for (i2 = 0; i2 < np2; i2++)
1501 {
1502 bool found = false;
1503 pred_info info2 = pred2[i2];
1504 for (i1 = 0; i1 < np1; i1++)
1505 {
1506 pred_info info1 = pred1[i1];
1507 if (is_pred_expr_subset_of (info1, info2))
1508 {
1509 found = true;
1510 break;
1511 }
1512 }
1513 if (!found)
1514 return false;
1515 }
1516 return true;
1517}
1518
1519/* Returns true if the domain defined by
1520 one pred chain ONE_PRED is a subset of the domain
1521 of *PREDS. It returns false if ONE_PRED's domain is
1522 not a subset of any of the sub-domains of PREDS
1523 (corresponding to each individual chains in it), even
1524 though it may be still be a subset of whole domain
1525 of PREDS which is the union (ORed) of all its subdomains.
1526 In other words, the result is conservative. */
1527
1528static bool
1529is_included_in (pred_chain one_pred, pred_chain_union preds)
1530{
1531 size_t i;
1532 size_t n = preds.length ();
1533
1534 for (i = 0; i < n; i++)
1535 {
1536 if (is_pred_chain_subset_of (one_pred, preds[i]))
1537 return true;
1538 }
1539
1540 return false;
1541}
1542
1543/* Compares two predicate sets PREDS1 and PREDS2 and returns
1544 true if the domain defined by PREDS1 is a superset
1545 of PREDS2's domain. N1 and N2 are array sizes of PREDS1 and
1546 PREDS2 respectively. The implementation chooses not to build
1547 generic trees (and relying on the folding capability of the
1548 compiler), but instead performs brute force comparison of
1549 individual predicate chains (won't be a compile time problem
1550 as the chains are pretty short). When the function returns
1551 false, it does not necessarily mean *PREDS1 is not a superset
1552 of *PREDS2, but mean it may not be so since the analysis can
1553 not prove it. In such cases, false warnings may still be
1554 emitted. */
1555
1556static bool
1557is_superset_of (pred_chain_union preds1, pred_chain_union preds2)
1558{
1559 size_t i, n2;
1560 pred_chain one_pred_chain = vNULL;
1561
1562 n2 = preds2.length ();
1563
1564 for (i = 0; i < n2; i++)
1565 {
1566 one_pred_chain = preds2[i];
1567 if (!is_included_in (one_pred_chain, preds1))
1568 return false;
1569 }
1570
1571 return true;
1572}
1573
1574/* Returns true if TC is AND or OR. */
1575
1576static inline bool
1577is_and_or_or_p (enum tree_code tc, tree type)
1578{
1579 return (tc == BIT_IOR_EXPR
1580 || (tc == BIT_AND_EXPR
1581 && (type == 0 || TREE_CODE (type) == BOOLEAN_TYPE)));
1582}
1583
1584/* Returns true if X1 is the negate of X2. */
1585
1586static inline bool
1587pred_neg_p (pred_info x1, pred_info x2)
1588{
1589 enum tree_code c1, c2;
1590 if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
1591 || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
1592 return false;
1593
1594 c1 = x1.cond_code;
1595 if (x1.invert == x2.invert)
1596 c2 = invert_tree_comparison (x2.cond_code, false);
1597 else
1598 c2 = x2.cond_code;
1599
1600 return c1 == c2;
1601}
1602
1603/* 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1604 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1605 3) X OR (!X AND Y) is equivalent to (X OR Y);
1606 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1607 (x != 0 AND y != 0)
1608 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1609 (X AND Y) OR Z
1610
1611 PREDS is the predicate chains, and N is the number of chains. */
1612
1613/* Helper function to implement rule 1 above. ONE_CHAIN is
1614 the AND predication to be simplified. */
1615
1616static void
1617simplify_pred (pred_chain *one_chain)
1618{
1619 size_t i, j, n;
1620 bool simplified = false;
1621 pred_chain s_chain = vNULL;
1622
1623 n = one_chain->length ();
1624
1625 for (i = 0; i < n; i++)
1626 {
1627 pred_info *a_pred = &(*one_chain)[i];
1628
1629 if (!a_pred->pred_lhs)
1630 continue;
1631 if (!is_neq_zero_form_p (*a_pred))
1632 continue;
1633
1634 gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
1635 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1636 continue;
1637 if (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
1638 {
1639 for (j = 0; j < n; j++)
1640 {
1641 pred_info *b_pred = &(*one_chain)[j];
1642
1643 if (!b_pred->pred_lhs)
1644 continue;
1645 if (!is_neq_zero_form_p (*b_pred))
1646 continue;
1647
1648 if (pred_expr_equal_p (*b_pred, gimple_assign_rhs1 (def_stmt))
1649 || pred_expr_equal_p (*b_pred, gimple_assign_rhs2 (def_stmt)))
1650 {
1651 /* Mark a_pred for removal. */
1652 a_pred->pred_lhs = NULL;
1653 a_pred->pred_rhs = NULL;
1654 simplified = true;
1655 break;
1656 }
1657 }
1658 }
1659 }
1660
1661 if (!simplified)
1662 return;
1663
1664 for (i = 0; i < n; i++)
1665 {
1666 pred_info *a_pred = &(*one_chain)[i];
1667 if (!a_pred->pred_lhs)
1668 continue;
1669 s_chain.safe_push (*a_pred);
1670 }
1671
1672 one_chain->release ();
1673 *one_chain = s_chain;
1674}
1675
1676/* The helper function implements the rule 2 for the
1677 OR predicate PREDS.
1678
1679 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1680
1681static bool
1682simplify_preds_2 (pred_chain_union *preds)
1683{
1684 size_t i, j, n;
1685 bool simplified = false;
1686 pred_chain_union s_preds = vNULL;
1687
1688 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1689 (X AND Y) OR (X AND !Y) is equivalent to X. */
1690
1691 n = preds->length ();
1692 for (i = 0; i < n; i++)
1693 {
1694 pred_info x, y;
1695 pred_chain *a_chain = &(*preds)[i];
1696
1697 if (a_chain->length () != 2)
1698 continue;
1699
1700 x = (*a_chain)[0];
1701 y = (*a_chain)[1];
1702
1703 for (j = 0; j < n; j++)
1704 {
1705 pred_chain *b_chain;
1706 pred_info x2, y2;
1707
1708 if (j == i)
1709 continue;
1710
1711 b_chain = &(*preds)[j];
1712 if (b_chain->length () != 2)
1713 continue;
1714
1715 x2 = (*b_chain)[0];
1716 y2 = (*b_chain)[1];
1717
1718 if (pred_equal_p (x, x2) && pred_neg_p (y, y2))
1719 {
1720 /* Kill a_chain. */
1721 a_chain->release ();
1722 b_chain->release ();
1723 b_chain->safe_push (x);
1724 simplified = true;
1725 break;
1726 }
1727 if (pred_neg_p (x, x2) && pred_equal_p (y, y2))
1728 {
1729 /* Kill a_chain. */
1730 a_chain->release ();
1731 b_chain->release ();
1732 b_chain->safe_push (y);
1733 simplified = true;
1734 break;
1735 }
1736 }
1737 }
1738 /* Now clean up the chain. */
1739 if (simplified)
1740 {
1741 for (i = 0; i < n; i++)
1742 {
1743 if ((*preds)[i].is_empty ())
1744 continue;
1745 s_preds.safe_push ((*preds)[i]);
1746 }
1747 preds->release ();
1748 (*preds) = s_preds;
1749 s_preds = vNULL;
1750 }
1751
1752 return simplified;
1753}
1754
1755/* The helper function implements the rule 2 for the
1756 OR predicate PREDS.
1757
1758 3) x OR (!x AND y) is equivalent to x OR y. */
1759
1760static bool
1761simplify_preds_3 (pred_chain_union *preds)
1762{
1763 size_t i, j, n;
1764 bool simplified = false;
1765
1766 /* Now iteratively simplify X OR (!X AND Z ..)
1767 into X OR (Z ...). */
1768
1769 n = preds->length ();
1770 if (n < 2)
1771 return false;
1772
1773 for (i = 0; i < n; i++)
1774 {
1775 pred_info x;
1776 pred_chain *a_chain = &(*preds)[i];
1777
1778 if (a_chain->length () != 1)
1779 continue;
1780
1781 x = (*a_chain)[0];
1782
1783 for (j = 0; j < n; j++)
1784 {
1785 pred_chain *b_chain;
1786 pred_info x2;
1787 size_t k;
1788
1789 if (j == i)
1790 continue;
1791
1792 b_chain = &(*preds)[j];
1793 if (b_chain->length () < 2)
1794 continue;
1795
1796 for (k = 0; k < b_chain->length (); k++)
1797 {
1798 x2 = (*b_chain)[k];
1799 if (pred_neg_p (x, x2))
1800 {
1801 b_chain->unordered_remove (k);
1802 simplified = true;
1803 break;
1804 }
1805 }
1806 }
1807 }
1808 return simplified;
1809}
1810
1811/* The helper function implements the rule 4 for the
1812 OR predicate PREDS.
1813
1814 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1815 (x != 0 ANd y != 0). */
1816
1817static bool
1818simplify_preds_4 (pred_chain_union *preds)
1819{
1820 size_t i, j, n;
1821 bool simplified = false;
1822 pred_chain_union s_preds = vNULL;
1823 gimple *def_stmt;
1824
1825 n = preds->length ();
1826 for (i = 0; i < n; i++)
1827 {
1828 pred_info z;
1829 pred_chain *a_chain = &(*preds)[i];
1830
1831 if (a_chain->length () != 1)
1832 continue;
1833
1834 z = (*a_chain)[0];
1835
1836 if (!is_neq_zero_form_p (z))
1837 continue;
1838
1839 def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1840 if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1841 continue;
1842
1843 if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1844 continue;
1845
1846 for (j = 0; j < n; j++)
1847 {
1848 pred_chain *b_chain;
1849 pred_info x2, y2;
1850
1851 if (j == i)
1852 continue;
1853
1854 b_chain = &(*preds)[j];
1855 if (b_chain->length () != 2)
1856 continue;
1857
1858 x2 = (*b_chain)[0];
1859 y2 = (*b_chain)[1];
1860 if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
1861 continue;
1862
1863 if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1864 && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1865 || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1866 && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1867 {
1868 /* Kill a_chain. */
1869 a_chain->release ();
1870 simplified = true;
1871 break;
1872 }
1873 }
1874 }
1875 /* Now clean up the chain. */
1876 if (simplified)
1877 {
1878 for (i = 0; i < n; i++)
1879 {
1880 if ((*preds)[i].is_empty ())
1881 continue;
1882 s_preds.safe_push ((*preds)[i]);
1883 }
1884
1885 preds->release ();
1886 (*preds) = s_preds;
1887 s_preds = vNULL;
1888 }
1889
1890 return simplified;
1891}
1892
1893/* This function simplifies predicates in PREDS. */
1894
1895static void
1896simplify_preds (pred_chain_union *preds, gimple *use_or_def, bool is_use)
1897{
1898 size_t i, n;
1899 bool changed = false;
1900
1901 if (dump_file && dump_flags & TDF_DETAILS)
1902 {
1903 fprintf (dump_file, "[BEFORE SIMPLICATION -- ");
1904 dump_predicates (use_or_def, *preds, is_use ? "[USE]:\n" : "[DEF]:\n");
1905 }
1906
1907 for (i = 0; i < preds->length (); i++)
1908 simplify_pred (&(*preds)[i]);
1909
1910 n = preds->length ();
1911 if (n < 2)
1912 return;
1913
1914 do
1915 {
1916 changed = false;
1917 if (simplify_preds_2 (preds))
1918 changed = true;
1919
1920 /* Now iteratively simplify X OR (!X AND Z ..)
1921 into X OR (Z ...). */
1922 if (simplify_preds_3 (preds))
1923 changed = true;
1924
1925 if (simplify_preds_4 (preds))
1926 changed = true;
1927 }
1928 while (changed);
1929
1930 return;
1931}
1932
1933/* This is a helper function which attempts to normalize predicate chains
1934 by following UD chains. It basically builds up a big tree of either IOR
1935 operations or AND operations, and convert the IOR tree into a
1936 pred_chain_union or BIT_AND tree into a pred_chain.
1937 Example:
1938
1939 _3 = _2 RELOP1 _1;
1940 _6 = _5 RELOP2 _4;
1941 _9 = _8 RELOP3 _7;
1942 _10 = _3 | _6;
1943 _12 = _9 | _0;
1944 _t = _10 | _12;
1945
1946 then _t != 0 will be normalized into a pred_chain_union
1947
1948 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1949
1950 Similarly given,
1951
1952 _3 = _2 RELOP1 _1;
1953 _6 = _5 RELOP2 _4;
1954 _9 = _8 RELOP3 _7;
1955 _10 = _3 & _6;
1956 _12 = _9 & _0;
1957
1958 then _t != 0 will be normalized into a pred_chain:
1959 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1960
1961 */
1962
1963/* This is a helper function that stores a PRED into NORM_PREDS. */
1964
1965inline static void
1966push_pred (pred_chain_union *norm_preds, pred_info pred)
1967{
1968 pred_chain pred_chain = vNULL;
1969 pred_chain.safe_push (pred);
1970 norm_preds->safe_push (pred_chain);
1971}
1972
1973/* A helper function that creates a predicate of the form
1974 OP != 0 and push it WORK_LIST. */
1975
1976inline static void
1977push_to_worklist (tree op, vec<pred_info, va_heap, vl_ptr> *work_list,
1978 hash_set<tree> *mark_set)
1979{
1980 if (mark_set->contains (op))
1981 return;
1982 mark_set->add (op);
1983
1984 pred_info arg_pred;
1985 arg_pred.pred_lhs = op;
1986 arg_pred.pred_rhs = integer_zero_node;
1987 arg_pred.cond_code = NE_EXPR;
1988 arg_pred.invert = false;
1989 work_list->safe_push (arg_pred);
1990}
1991
1992/* A helper that generates a pred_info from a gimple assignment
1993 CMP_ASSIGN with comparison rhs. */
1994
1995static pred_info
1996get_pred_info_from_cmp (gimple *cmp_assign)
1997{
1998 pred_info n_pred;
1999 n_pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
2000 n_pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
2001 n_pred.cond_code = gimple_assign_rhs_code (cmp_assign);
2002 n_pred.invert = false;
2003 return n_pred;
2004}
2005
2006/* Returns true if the PHI is a degenerated phi with
2007 all args with the same value (relop). In that case, *PRED
2008 will be updated to that value. */
2009
2010static bool
2011is_degenerated_phi (gimple *phi, pred_info *pred_p)
2012{
2013 int i, n;
2014 tree op0;
2015 gimple *def0;
2016 pred_info pred0;
2017
2018 n = gimple_phi_num_args (phi);
2019 op0 = gimple_phi_arg_def (phi, 0);
2020
2021 if (TREE_CODE (op0) != SSA_NAME)
2022 return false;
2023
2024 def0 = SSA_NAME_DEF_STMT (op0);
2025 if (gimple_code (def0) != GIMPLE_ASSIGN)
2026 return false;
2027 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
2028 return false;
2029 pred0 = get_pred_info_from_cmp (def0);
2030
2031 for (i = 1; i < n; ++i)
2032 {
2033 gimple *def;
2034 pred_info pred;
2035 tree op = gimple_phi_arg_def (phi, i);
2036
2037 if (TREE_CODE (op) != SSA_NAME)
2038 return false;
2039
2040 def = SSA_NAME_DEF_STMT (op);
2041 if (gimple_code (def) != GIMPLE_ASSIGN)
2042 return false;
2043 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
2044 return false;
2045 pred = get_pred_info_from_cmp (def);
2046 if (!pred_equal_p (pred, pred0))
2047 return false;
2048 }
2049
2050 *pred_p = pred0;
2051 return true;
2052}
2053
2054/* Normalize one predicate PRED
2055 1) if PRED can no longer be normlized, put it into NORM_PREDS.
2056 2) otherwise if PRED is of the form x != 0, follow x's definition
2057 and put normalized predicates into WORK_LIST. */
2058
2059static void
2060normalize_one_pred_1 (pred_chain_union *norm_preds,
2061 pred_chain *norm_chain,
2062 pred_info pred,
2063 enum tree_code and_or_code,
2064 vec<pred_info, va_heap, vl_ptr> *work_list,
2065 hash_set<tree> *mark_set)
2066{
2067 if (!is_neq_zero_form_p (pred))
2068 {
2069 if (and_or_code == BIT_IOR_EXPR)
2070 push_pred (norm_preds, pred);
2071 else
2072 norm_chain->safe_push (pred);
2073 return;
2074 }
2075
2076 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2077
2078 if (gimple_code (def_stmt) == GIMPLE_PHI
2079 && is_degenerated_phi (def_stmt, &pred))
2080 work_list->safe_push (pred);
2081 else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
2082 {
2083 int i, n;
2084 n = gimple_phi_num_args (def_stmt);
2085
2086 /* If we see non zero constant, we should punt. The predicate
2087 * should be one guarding the phi edge. */
2088 for (i = 0; i < n; ++i)
2089 {
2090 tree op = gimple_phi_arg_def (def_stmt, i);
2091 if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
2092 {
2093 push_pred (norm_preds, pred);
2094 return;
2095 }
2096 }
2097
2098 for (i = 0; i < n; ++i)
2099 {
2100 tree op = gimple_phi_arg_def (def_stmt, i);
2101 if (integer_zerop (op))
2102 continue;
2103
2104 push_to_worklist (op, work_list, mark_set);
2105 }
2106 }
2107 else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
2108 {
2109 if (and_or_code == BIT_IOR_EXPR)
2110 push_pred (norm_preds, pred);
2111 else
2112 norm_chain->safe_push (pred);
2113 }
2114 else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
2115 {
2116 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
2117 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
2118 {
2119 /* But treat x & 3 as condition. */
2120 if (and_or_code == BIT_AND_EXPR)
2121 {
2122 pred_info n_pred;
2123 n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
2124 n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
2125 n_pred.cond_code = and_or_code;
2126 n_pred.invert = false;
2127 norm_chain->safe_push (n_pred);
2128 }
2129 }
2130 else
2131 {
2132 push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
2133 push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
2134 }
2135 }
2136 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
2137 == tcc_comparison)
2138 {
2139 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2140 if (and_or_code == BIT_IOR_EXPR)
2141 push_pred (norm_preds, n_pred);
2142 else
2143 norm_chain->safe_push (n_pred);
2144 }
2145 else
2146 {
2147 if (and_or_code == BIT_IOR_EXPR)
2148 push_pred (norm_preds, pred);
2149 else
2150 norm_chain->safe_push (pred);
2151 }
2152}
2153
2154/* Normalize PRED and store the normalized predicates into NORM_PREDS. */
2155
2156static void
2157normalize_one_pred (pred_chain_union *norm_preds, pred_info pred)
2158{
2159 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2160 enum tree_code and_or_code = ERROR_MARK;
2161 pred_chain norm_chain = vNULL;
2162
2163 if (!is_neq_zero_form_p (pred))
2164 {
2165 push_pred (norm_preds, pred);
2166 return;
2167 }
2168
2169 gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
2170 if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
2171 and_or_code = gimple_assign_rhs_code (def_stmt);
2172 if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
2173 {
2174 if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
2175 {
2176 pred_info n_pred = get_pred_info_from_cmp (def_stmt);
2177 push_pred (norm_preds, n_pred);
2178 }
2179 else
2180 push_pred (norm_preds, pred);
2181 return;
2182 }
2183
2184 work_list.safe_push (pred);
2185 hash_set<tree> mark_set;
2186
2187 while (!work_list.is_empty ())
2188 {
2189 pred_info a_pred = work_list.pop ();
2190 normalize_one_pred_1 (norm_preds, &norm_chain, a_pred, and_or_code,
2191 &work_list, &mark_set);
2192 }
2193 if (and_or_code == BIT_AND_EXPR)
2194 norm_preds->safe_push (norm_chain);
2195
2196 work_list.release ();
2197}
2198
2199static void
2200normalize_one_pred_chain (pred_chain_union *norm_preds, pred_chain one_chain)
2201{
2202 vec<pred_info, va_heap, vl_ptr> work_list = vNULL;
2203 hash_set<tree> mark_set;
2204 pred_chain norm_chain = vNULL;
2205 size_t i;
2206
2207 for (i = 0; i < one_chain.length (); i++)
2208 {
2209 work_list.safe_push (one_chain[i]);
2210 mark_set.add (one_chain[i].pred_lhs);
2211 }
2212
2213 while (!work_list.is_empty ())
2214 {
2215 pred_info a_pred = work_list.pop ();
2216 normalize_one_pred_1 (0, &norm_chain, a_pred, BIT_AND_EXPR, &work_list,
2217 &mark_set);
2218 }
2219
2220 norm_preds->safe_push (norm_chain);
2221 work_list.release ();
2222}
2223
2224/* Normalize predicate chains PREDS and returns the normalized one. */
2225
2226static pred_chain_union
2227normalize_preds (pred_chain_union preds, gimple *use_or_def, bool is_use)
2228{
2229 pred_chain_union norm_preds = vNULL;
2230 size_t n = preds.length ();
2231 size_t i;
2232
2233 if (dump_file && dump_flags & TDF_DETAILS)
2234 {
2235 fprintf (dump_file, "[BEFORE NORMALIZATION --");
2236 dump_predicates (use_or_def, preds, is_use ? "[USE]:\n" : "[DEF]:\n");
2237 }
2238
2239 for (i = 0; i < n; i++)
2240 {
2241 if (preds[i].length () != 1)
2242 normalize_one_pred_chain (&norm_preds, preds[i]);
2243 else
2244 {
2245 normalize_one_pred (&norm_preds, preds[i][0]);
2246 preds[i].release ();
2247 }
2248 }
2249
2250 if (dump_file)
2251 {
2252 fprintf (dump_file, "[AFTER NORMALIZATION -- ");
2253 dump_predicates (use_or_def, norm_preds,
2254 is_use ? "[USE]:\n" : "[DEF]:\n");
2255 }
2256
2257 destroy_predicate_vecs (&preds);
2258 return norm_preds;
2259}
2260
2261/* Return TRUE if PREDICATE can be invalidated by any individual
2262 predicate in WORKLIST. */
2263
2264static bool
2265can_one_predicate_be_invalidated_p (pred_info predicate,
2266 pred_chain use_guard)
2267{
2268 for (size_t i = 0; i < use_guard.length (); ++i)
2269 {
2270 /* NOTE: This is a very simple check, and only understands an
2271 exact opposite. So, [i == 0] is currently only invalidated
2272 by [.NOT. i == 0] or [i != 0]. Ideally we should also
2273 invalidate with say [i > 5] or [i == 8]. There is certainly
2274 room for improvement here. */
2275 if (pred_neg_p (predicate, use_guard[i]))
2276 return true;
2277 }
2278 return false;
2279}
2280
2281/* Return TRUE if all predicates in UNINIT_PRED are invalidated by
2282 USE_GUARD being true. */
2283
2284static bool
2285can_chain_union_be_invalidated_p (pred_chain_union uninit_pred,
2286 pred_chain use_guard)
2287{
2288 if (uninit_pred.is_empty ())
2289 return false;
2290 for (size_t i = 0; i < uninit_pred.length (); ++i)
2291 {
2292 pred_chain c = uninit_pred[i];
2293 for (size_t j = 0; j < c.length (); ++j)
2294 if (!can_one_predicate_be_invalidated_p (c[j], use_guard))
2295 return false;
2296 }
2297 return true;
2298}
2299
2300/* Return TRUE if none of the uninitialized operands in UNINT_OPNDS
2301 can actually happen if we arrived at a use for PHI.
2302
2303 PHI_USE_GUARDS are the guard conditions for the use of the PHI. */
2304
2305static bool
2306uninit_uses_cannot_happen (gphi *phi, unsigned uninit_opnds,
2307 pred_chain_union phi_use_guards)
2308{
2309 unsigned phi_args = gimple_phi_num_args (phi);
2310 if (phi_args > max_phi_args)
2311 return false;
2312
2313 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
2314 possible guard, there's no way of knowing which guard was true.
2315 Since we need to be absolutely sure that the uninitialized
2316 operands will be invalidated, bail. */
2317 if (phi_use_guards.length () != 1)
2318 return false;
2319
2320 /* Look for the control dependencies of all the uninitialized
2321 operands and build guard predicates describing them. */
2322 pred_chain_union uninit_preds;
2323 bool ret = true;
2324 for (unsigned i = 0; i < phi_args; ++i)
2325 {
2326 if (!MASK_TEST_BIT (uninit_opnds, i))
2327 continue;
2328
2329 edge e = gimple_phi_arg_edge (phi, i);
2330 vec<edge> dep_chains[MAX_NUM_CHAINS];
2331 auto_vec<edge, MAX_CHAIN_LEN + 1> cur_chain;
2332 size_t num_chains = 0;
2333 int num_calls = 0;
2334
2335 /* Build the control dependency chain for uninit operand `i'... */
2336 uninit_preds = vNULL;
2337 if (!compute_control_dep_chain (find_dom (e->src),
2338 e->src, dep_chains, &num_chains,
2339 &cur_chain, &num_calls))
2340 {
2341 ret = false;
2342 break;
2343 }
2344 /* ...and convert it into a set of predicates. */
2345 convert_control_dep_chain_into_preds (dep_chains, num_chains,
2346 &uninit_preds);
2347 for (size_t j = 0; j < num_chains; ++j)
2348 dep_chains[j].release ();
2349 simplify_preds (&uninit_preds, NULL, false);
2350 uninit_preds = normalize_preds (uninit_preds, NULL, false);
2351
2352 /* Can the guard for this uninitialized operand be invalidated
2353 by the PHI use? */
2354 if (!can_chain_union_be_invalidated_p (uninit_preds, phi_use_guards[0]))
2355 {
2356 ret = false;
2357 break;
2358 }
2359 }
2360 destroy_predicate_vecs (&uninit_preds);
2361 return ret;
2362}
2363
2364/* Computes the predicates that guard the use and checks
2365 if the incoming paths that have empty (or possibly
2366 empty) definition can be pruned/filtered. The function returns
2367 true if it can be determined that the use of PHI's def in
2368 USE_STMT is guarded with a predicate set not overlapping with
2369 predicate sets of all runtime paths that do not have a definition.
2370
2371 Returns false if it is not or it can not be determined. USE_BB is
2372 the bb of the use (for phi operand use, the bb is not the bb of
2373 the phi stmt, but the src bb of the operand edge).
2374
2375 UNINIT_OPNDS is a bit vector. If an operand of PHI is uninitialized, the
2376 corresponding bit in the vector is 1. VISITED_PHIS is a pointer
2377 set of phis being visited.
2378
2379 *DEF_PREDS contains the (memoized) defining predicate chains of PHI.
2380 If *DEF_PREDS is the empty vector, the defining predicate chains of
2381 PHI will be computed and stored into *DEF_PREDS as needed.
2382
2383 VISITED_PHIS is a pointer set of phis being visited. */
2384
2385static bool
2386is_use_properly_guarded (gimple *use_stmt,
2387 basic_block use_bb,
2388 gphi *phi,
2389 unsigned uninit_opnds,
2390 pred_chain_union *def_preds,
2391 hash_set<gphi *> *visited_phis)
2392{
2393 basic_block phi_bb;
2394 pred_chain_union preds = vNULL;
2395 bool has_valid_preds = false;
2396 bool is_properly_guarded = false;
2397
2398 if (visited_phis->add (phi))
2399 return false;
2400
2401 phi_bb = gimple_bb (phi);
2402
2403 if (is_non_loop_exit_postdominating (use_bb, phi_bb))
2404 return false;
2405
2406 has_valid_preds = find_predicates (&preds, phi_bb, use_bb);
2407
2408 if (!has_valid_preds)
2409 {
2410 destroy_predicate_vecs (&preds);
2411 return false;
2412 }
2413
2414 /* Try to prune the dead incoming phi edges. */
2415 is_properly_guarded
2416 = use_pred_not_overlap_with_undef_path_pred (preds, phi, uninit_opnds,
2417 visited_phis);
2418
2419 /* We might be able to prove that if the control dependencies
2420 for UNINIT_OPNDS are true, that the control dependencies for
2421 USE_STMT can never be true. */
2422 if (!is_properly_guarded)
2423 is_properly_guarded |= uninit_uses_cannot_happen (phi, uninit_opnds,
2424 preds);
2425
2426 if (is_properly_guarded)
2427 {
2428 destroy_predicate_vecs (&preds);
2429 return true;
2430 }
2431
2432 if (def_preds->is_empty ())
2433 {
2434 has_valid_preds = find_def_preds (def_preds, phi);
2435
2436 if (!has_valid_preds)
2437 {
2438 destroy_predicate_vecs (&preds);
2439 return false;
2440 }
2441
2442 simplify_preds (def_preds, phi, false);
2443 *def_preds = normalize_preds (*def_preds, phi, false);
2444 }
2445
2446 simplify_preds (&preds, use_stmt, true);
2447 preds = normalize_preds (preds, use_stmt, true);
2448
2449 is_properly_guarded = is_superset_of (*def_preds, preds);
2450
2451 destroy_predicate_vecs (&preds);
2452 return is_properly_guarded;
2453}
2454
2455/* Searches through all uses of a potentially
2456 uninitialized variable defined by PHI and returns a use
2457 statement if the use is not properly guarded. It returns
2458 NULL if all uses are guarded. UNINIT_OPNDS is a bitvector
2459 holding the position(s) of uninit PHI operands. WORKLIST
2460 is the vector of candidate phis that may be updated by this
2461 function. ADDED_TO_WORKLIST is the pointer set tracking
2462 if the new phi is already in the worklist. */
2463
2464static gimple *
2465find_uninit_use (gphi *phi, unsigned uninit_opnds,
2466 vec<gphi *> *worklist,
2467 hash_set<gphi *> *added_to_worklist)
2468{
2469 tree phi_result;
2470 use_operand_p use_p;
2471 gimple *use_stmt;
2472 imm_use_iterator iter;
2473 pred_chain_union def_preds = vNULL;
2474 gimple *ret = NULL;
2475
2476 phi_result = gimple_phi_result (phi);
2477
2478 FOR_EACH_IMM_USE_FAST (use_p, iter, phi_result)
2479 {
2480 basic_block use_bb;
2481
2482 use_stmt = USE_STMT (use_p);
2483 if (is_gimple_debug (use_stmt))
2484 continue;
2485
2486 if (gphi *use_phi = dyn_cast<gphi *> (use_stmt))
2487 use_bb = gimple_phi_arg_edge (use_phi,
2488 PHI_ARG_INDEX_FROM_USE (use_p))->src;
2489 else
2490 use_bb = gimple_bb (use_stmt);
2491
2492 hash_set<gphi *> visited_phis;
2493 if (is_use_properly_guarded (use_stmt, use_bb, phi, uninit_opnds,
2494 &def_preds, &visited_phis))
2495 continue;
2496
2497 if (dump_file && (dump_flags & TDF_DETAILS))
2498 {
2499 fprintf (dump_file, "[CHECK]: Found unguarded use: ");
2500 print_gimple_stmt (dump_file, use_stmt, 0);
2501 }
2502 /* Found one real use, return. */
2503 if (gimple_code (use_stmt) != GIMPLE_PHI)
2504 {
2505 ret = use_stmt;
2506 break;
2507 }
2508
2509 /* Found a phi use that is not guarded,
2510 add the phi to the worklist. */
2511 if (!added_to_worklist->add (as_a<gphi *> (use_stmt)))
2512 {
2513 if (dump_file && (dump_flags & TDF_DETAILS))
2514 {
2515 fprintf (dump_file, "[WORKLIST]: Update worklist with phi: ");
2516 print_gimple_stmt (dump_file, use_stmt, 0);
2517 }
2518
2519 worklist->safe_push (as_a<gphi *> (use_stmt));
2520 possibly_undefined_names->add (phi_result);
2521 }
2522 }
2523
2524 destroy_predicate_vecs (&def_preds);
2525 return ret;
2526}
2527
2528/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
2529 and gives warning if there exists a runtime path from the entry to a
2530 use of the PHI def that does not contain a definition. In other words,
2531 the warning is on the real use. The more dead paths that can be pruned
2532 by the compiler, the fewer false positives the warning is. WORKLIST
2533 is a vector of candidate phis to be examined. ADDED_TO_WORKLIST is
2534 a pointer set tracking if the new phi is added to the worklist or not. */
2535
2536static void
2537warn_uninitialized_phi (gphi *phi, vec<gphi *> *worklist,
2538 hash_set<gphi *> *added_to_worklist)
2539{
2540 unsigned uninit_opnds;
2541 gimple *uninit_use_stmt = 0;
2542 tree uninit_op;
2543 int phiarg_index;
2544 location_t loc;
2545
2546 /* Don't look at virtual operands. */
2547 if (virtual_operand_p (gimple_phi_result (phi)))
2548 return;
2549
2550 uninit_opnds = compute_uninit_opnds_pos (phi);
2551
2552 if (MASK_EMPTY (uninit_opnds))
2553 return;
2554
2555 if (dump_file && (dump_flags & TDF_DETAILS))
2556 {
2557 fprintf (dump_file, "[CHECK]: examining phi: ");
2558 print_gimple_stmt (dump_file, phi, 0);
2559 }
2560
2561 /* Now check if we have any use of the value without proper guard. */
2562 uninit_use_stmt = find_uninit_use (phi, uninit_opnds,
2563 worklist, added_to_worklist);
2564
2565 /* All uses are properly guarded. */
2566 if (!uninit_use_stmt)
2567 return;
2568
2569 phiarg_index = MASK_FIRST_SET_BIT (uninit_opnds);
2570 uninit_op = gimple_phi_arg_def (phi, phiarg_index);
2571 if (SSA_NAME_VAR (uninit_op) == NULL_TREE)
2572 return;
2573 if (gimple_phi_arg_has_location (phi, phiarg_index))
2574 loc = gimple_phi_arg_location (phi, phiarg_index);
2575 else
2576 loc = UNKNOWN_LOCATION;
2577 warn_uninit (OPT_Wmaybe_uninitialized, uninit_op, SSA_NAME_VAR (uninit_op),
2578 SSA_NAME_VAR (uninit_op),
2579 "%qD may be used uninitialized in this function",
2580 uninit_use_stmt, loc);
2581}
2582
2583static bool
2584gate_warn_uninitialized (void)
2585{
2586 return warn_uninitialized || warn_maybe_uninitialized;
2587}
2588
2589namespace {
2590
2591const pass_data pass_data_late_warn_uninitialized =
2592{
2593 GIMPLE_PASS, /* type */
2594 "uninit", /* name */
2595 OPTGROUP_NONE, /* optinfo_flags */
2596 TV_NONE, /* tv_id */
2597 PROP_ssa, /* properties_required */
2598 0, /* properties_provided */
2599 0, /* properties_destroyed */
2600 0, /* todo_flags_start */
2601 0, /* todo_flags_finish */
2602};
2603
2604class pass_late_warn_uninitialized : public gimple_opt_pass
2605{
2606public:
2607 pass_late_warn_uninitialized (gcc::context *ctxt)
2608 : gimple_opt_pass (pass_data_late_warn_uninitialized, ctxt)
2609 {}
2610
2611 /* opt_pass methods: */
2612 opt_pass *clone () { return new pass_late_warn_uninitialized (m_ctxt); }
2613 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2614 virtual unsigned int execute (function *);
2615
2616}; // class pass_late_warn_uninitialized
2617
2618unsigned int
2619pass_late_warn_uninitialized::execute (function *fun)
2620{
2621 basic_block bb;
2622 gphi_iterator gsi;
2623 vec<gphi *> worklist = vNULL;
2624
2625 calculate_dominance_info (CDI_DOMINATORS);
2626 calculate_dominance_info (CDI_POST_DOMINATORS);
2627 /* Re-do the plain uninitialized variable check, as optimization may have
2628 straightened control flow. Do this first so that we don't accidentally
2629 get a "may be" warning when we'd have seen an "is" warning later. */
2630 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
2631
2632 timevar_push (TV_TREE_UNINIT);
2633
2634 possibly_undefined_names = new hash_set<tree>;
2635 hash_set<gphi *> added_to_worklist;
2636
2637 /* Initialize worklist */
2638 FOR_EACH_BB_FN (bb, fun)
2639 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2640 {
2641 gphi *phi = gsi.phi ();
2642 size_t n, i;
2643
2644 n = gimple_phi_num_args (phi);
2645
2646 /* Don't look at virtual operands. */
2647 if (virtual_operand_p (gimple_phi_result (phi)))
2648 continue;
2649
2650 for (i = 0; i < n; ++i)
2651 {
2652 tree op = gimple_phi_arg_def (phi, i);
2653 if (TREE_CODE (op) == SSA_NAME && uninit_undefined_value_p (op))
2654 {
2655 worklist.safe_push (phi);
2656 added_to_worklist.add (phi);
2657 if (dump_file && (dump_flags & TDF_DETAILS))
2658 {
2659 fprintf (dump_file, "[WORKLIST]: add to initial list: ");
2660 print_gimple_stmt (dump_file, phi, 0);
2661 }
2662 break;
2663 }
2664 }
2665 }
2666
2667 while (worklist.length () != 0)
2668 {
2669 gphi *cur_phi = 0;
2670 cur_phi = worklist.pop ();
2671 warn_uninitialized_phi (cur_phi, &worklist, &added_to_worklist);
2672 }
2673
2674 worklist.release ();
2675 delete possibly_undefined_names;
2676 possibly_undefined_names = NULL;
2677 free_dominance_info (CDI_POST_DOMINATORS);
2678 timevar_pop (TV_TREE_UNINIT);
2679 return 0;
2680}
2681
2682} // anon namespace
2683
2684gimple_opt_pass *
2685make_pass_late_warn_uninitialized (gcc::context *ctxt)
2686{
2687 return new pass_late_warn_uninitialized (ctxt);
2688}
2689
2690static unsigned int
2691execute_early_warn_uninitialized (void)
2692{
2693 /* Currently, this pass runs always but
2694 execute_late_warn_uninitialized only runs with optimization. With
2695 optimization we want to warn about possible uninitialized as late
2696 as possible, thus don't do it here. However, without
2697 optimization we need to warn here about "may be uninitialized". */
2698 calculate_dominance_info (CDI_POST_DOMINATORS);
2699
2700 warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
2701
2702 /* Post-dominator information can not be reliably updated. Free it
2703 after the use. */
2704
2705 free_dominance_info (CDI_POST_DOMINATORS);
2706 return 0;
2707}
2708
2709namespace {
2710
2711const pass_data pass_data_early_warn_uninitialized =
2712{
2713 GIMPLE_PASS, /* type */
2714 "*early_warn_uninitialized", /* name */
2715 OPTGROUP_NONE, /* optinfo_flags */
2716 TV_TREE_UNINIT, /* tv_id */
2717 PROP_ssa, /* properties_required */
2718 0, /* properties_provided */
2719 0, /* properties_destroyed */
2720 0, /* todo_flags_start */
2721 0, /* todo_flags_finish */
2722};
2723
2724class pass_early_warn_uninitialized : public gimple_opt_pass
2725{
2726public:
2727 pass_early_warn_uninitialized (gcc::context *ctxt)
2728 : gimple_opt_pass (pass_data_early_warn_uninitialized, ctxt)
2729 {}
2730
2731 /* opt_pass methods: */
2732 virtual bool gate (function *) { return gate_warn_uninitialized (); }
2733 virtual unsigned int execute (function *)
2734 {
2735 return execute_early_warn_uninitialized ();
2736 }
2737
2738}; // class pass_early_warn_uninitialized
2739
2740} // anon namespace
2741
2742gimple_opt_pass *
2743make_pass_early_warn_uninitialized (gcc::context *ctxt)
2744{
2745 return new pass_early_warn_uninitialized (ctxt);
2746}
2747