Line data Source code
1 : /* Support for simple predicate analysis.
2 :
3 : Copyright (C) 2001-2026 Free Software Foundation, Inc.
4 : Contributed by Xinliang David Li <davidxl@google.com>
5 : Generalized by Martin Sebor <msebor@redhat.com>
6 :
7 : This file is part of GCC.
8 :
9 : GCC is free software; you can redistribute it and/or modify
10 : it under the terms of the GNU General Public License as published by
11 : the Free Software Foundation; either version 3, or (at your option)
12 : any later version.
13 :
14 : GCC is distributed in the hope that it will be useful,
15 : but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : GNU General Public License for more details.
18 :
19 : You should have received a copy of the GNU General Public License
20 : along with GCC; see the file COPYING3. If not see
21 : <http://www.gnu.org/licenses/>. */
22 :
23 : #define INCLUDE_STRING
24 : #include "config.h"
25 : #include "system.h"
26 : #include "coretypes.h"
27 : #include "backend.h"
28 : #include "tree.h"
29 : #include "gimple.h"
30 : #include "tree-pass.h"
31 : #include "ssa.h"
32 : #include "gimple-pretty-print.h"
33 : #include "diagnostic-core.h"
34 : #include "fold-const.h"
35 : #include "gimple-iterator.h"
36 : #include "tree-ssa.h"
37 : #include "tree-cfg.h"
38 : #include "cfghooks.h"
39 : #include "attribs.h"
40 : #include "builtins.h"
41 : #include "calls.h"
42 : #include "value-query.h"
43 : #include "cfganal.h"
44 : #include "tree-eh.h"
45 : #include "gimple-fold.h"
46 :
47 : #include "gimple-predicate-analysis.h"
48 :
49 : #define DEBUG_PREDICATE_ANALYZER 1
50 :
51 : /* In our predicate normal form we have MAX_NUM_CHAINS or predicates
52 : and in those MAX_CHAIN_LEN (inverted) and predicates. */
53 : #define MAX_NUM_CHAINS (unsigned)param_uninit_max_num_chains
54 : #define MAX_CHAIN_LEN (unsigned)param_uninit_max_chain_len
55 :
56 : /* Return true if X1 is the negation of X2. */
57 :
58 : static inline bool
59 547 : pred_neg_p (const pred_info &x1, const pred_info &x2)
60 : {
61 547 : if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
62 547 : || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
63 451 : return false;
64 :
65 96 : tree_code c1 = x1.cond_code, c2;
66 96 : if (x1.invert == x2.invert)
67 0 : c2 = invert_tree_comparison (x2.cond_code, false);
68 : else
69 96 : c2 = x2.cond_code;
70 :
71 96 : return c1 == c2;
72 : }
73 :
74 : /* Return whether the condition (VAL CMPC BOUNDARY) is true. */
75 :
76 : static bool
77 675 : is_value_included_in (tree val, tree boundary, tree_code cmpc)
78 : {
79 : /* Only handle integer constant here. */
80 675 : if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
81 : return true;
82 :
83 675 : bool inverted = false;
84 675 : if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
85 : {
86 568 : cmpc = invert_tree_comparison (cmpc, false);
87 568 : inverted = true;
88 : }
89 :
90 675 : bool result;
91 675 : if (cmpc == EQ_EXPR)
92 646 : result = tree_int_cst_equal (val, boundary);
93 29 : else if (cmpc == LT_EXPR)
94 14 : result = tree_int_cst_lt (val, boundary);
95 : else
96 : {
97 15 : gcc_assert (cmpc == LE_EXPR);
98 15 : result = tree_int_cst_le (val, boundary);
99 : }
100 :
101 675 : if (inverted)
102 568 : result ^= 1;
103 :
104 : return result;
105 : }
106 :
107 : /* Format the vector of edges EV as a string. */
108 :
109 : static std::string
110 15 : format_edge_vec (const vec<edge> &ev)
111 : {
112 15 : std::string str;
113 :
114 15 : unsigned n = ev.length ();
115 32 : for (unsigned i = 0; i < n; ++i)
116 : {
117 17 : char es[32];
118 17 : const_edge e = ev[i];
119 17 : sprintf (es, "%u -> %u", e->src->index, e->dest->index);
120 17 : str += es;
121 17 : if (i + 1 < n)
122 6 : str += ", ";
123 : }
124 15 : return str;
125 : }
126 :
127 : /* Format the first N elements of the array of vector of edges EVA as
128 : a string. */
129 :
130 : static std::string
131 4 : format_edge_vecs (const vec<edge> eva[], unsigned n)
132 : {
133 4 : std::string str;
134 :
135 8 : for (unsigned i = 0; i != n; ++i)
136 : {
137 4 : str += '{';
138 8 : str += format_edge_vec (eva[i]);
139 4 : str += '}';
140 4 : if (i + 1 < n)
141 0 : str += ", ";
142 : }
143 4 : return str;
144 : }
145 :
146 : /* Dump a single pred_info to F. */
147 :
148 : static void
149 18 : dump_pred_info (FILE *f, const pred_info &pred)
150 : {
151 18 : if (pred.invert)
152 6 : fprintf (f, "NOT (");
153 18 : print_generic_expr (f, pred.pred_lhs);
154 18 : fprintf (f, " %s ", op_symbol_code (pred.cond_code));
155 18 : print_generic_expr (f, pred.pred_rhs);
156 18 : if (pred.invert)
157 6 : fputc (')', f);
158 18 : }
159 :
160 : /* Dump a pred_chain to F. */
161 :
162 : static void
163 8 : dump_pred_chain (FILE *f, const pred_chain &chain)
164 : {
165 8 : unsigned np = chain.length ();
166 20 : for (unsigned j = 0; j < np; j++)
167 : {
168 12 : if (j > 0)
169 4 : fprintf (f, " AND (");
170 : else
171 8 : fputc ('(', f);
172 12 : dump_pred_info (f, chain[j]);
173 12 : fputc (')', f);
174 : }
175 8 : }
176 :
177 : /* Return the 'normalized' conditional code with operand swapping
178 : and condition inversion controlled by SWAP_COND and INVERT. */
179 :
180 : static tree_code
181 969 : get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)
182 : {
183 969 : tree_code tc = orig_cmp_code;
184 :
185 969 : if (swap_cond)
186 107 : tc = swap_tree_comparison (orig_cmp_code);
187 969 : if (invert)
188 339 : tc = invert_tree_comparison (tc, false);
189 :
190 969 : switch (tc)
191 : {
192 952 : case LT_EXPR:
193 952 : case LE_EXPR:
194 952 : case GT_EXPR:
195 952 : case GE_EXPR:
196 952 : case EQ_EXPR:
197 952 : case NE_EXPR:
198 952 : break;
199 : default:
200 : return ERROR_MARK;
201 : }
202 952 : return tc;
203 : }
204 :
205 : /* Return true if PRED is common among all predicate chains in PREDS
206 : (and therefore can be factored out). */
207 :
208 : static bool
209 163 : find_matching_predicate_in_rest_chains (const pred_info &pred,
210 : const pred_chain_union &preds)
211 : {
212 : /* Trivial case. */
213 326 : if (preds.length () == 1)
214 : return true;
215 :
216 6 : for (unsigned i = 1; i < preds.length (); i++)
217 : {
218 3 : bool found = false;
219 3 : const pred_chain &chain = preds[i];
220 3 : unsigned n = chain.length ();
221 3 : for (unsigned j = 0; j < n; j++)
222 : {
223 3 : const pred_info &pred2 = chain[j];
224 : /* Can relax the condition comparison to not use address
225 : comparison. However, the most common case is that
226 : multiple control dependent paths share a common path
227 : prefix, so address comparison should be ok. */
228 3 : if (operand_equal_p (pred2.pred_lhs, pred.pred_lhs, 0)
229 3 : && operand_equal_p (pred2.pred_rhs, pred.pred_rhs, 0)
230 6 : && pred2.invert == pred.invert)
231 : {
232 : found = true;
233 : break;
234 : }
235 : }
236 3 : if (!found)
237 : return false;
238 : }
239 : return true;
240 : }
241 :
242 : /* Find a predicate to examine against paths of interest. If there
243 : is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
244 : of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
245 : PHI is the phi node whose incoming (interesting) paths need to be
246 : examined. On success, return the comparison code, set definition
247 : gimple of FLAG_DEF and BOUNDARY_CST. Otherwise return ERROR_MARK.
248 : I is the running iterator so the function can be called repeatedly
249 : to gather all candidates. */
250 :
251 : static tree_code
252 459 : find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
253 : tree *boundary_cst, unsigned &i)
254 : {
255 459 : gcc_assert (preds.length () > 0);
256 459 : pred_chain chain = preds[0];
257 1158 : for (; i < chain.length (); i++)
258 : {
259 862 : const pred_info &pred = chain[i];
260 862 : tree cond_lhs = pred.pred_lhs;
261 862 : tree cond_rhs = pred.pred_rhs;
262 862 : if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
263 699 : continue;
264 :
265 862 : tree_code code = get_cmp_code (pred.cond_code, false, pred.invert);
266 862 : if (code == ERROR_MARK)
267 17 : continue;
268 :
269 : /* Convert to the canonical form SSA_NAME CMP CONSTANT. */
270 845 : if (TREE_CODE (cond_lhs) == SSA_NAME
271 845 : && is_gimple_constant (cond_rhs))
272 : ;
273 114 : else if (TREE_CODE (cond_rhs) == SSA_NAME
274 114 : && is_gimple_constant (cond_lhs))
275 : {
276 0 : std::swap (cond_lhs, cond_rhs);
277 0 : if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
278 0 : continue;
279 : }
280 : /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
281 : with value range info. Note only first of such case is handled. */
282 114 : else if (TREE_CODE (cond_lhs) == SSA_NAME
283 114 : && TREE_CODE (cond_rhs) == SSA_NAME)
284 : {
285 111 : gimple* lhs_def = SSA_NAME_DEF_STMT (cond_lhs);
286 111 : if (!lhs_def || gimple_code (lhs_def) != GIMPLE_PHI
287 115 : || gimple_bb (lhs_def) != gimple_bb (phi))
288 : {
289 107 : std::swap (cond_lhs, cond_rhs);
290 107 : if ((code = get_cmp_code (code, true, false)) == ERROR_MARK)
291 99 : continue;
292 : }
293 :
294 : /* Check value range info of rhs, do following transforms:
295 : flag_var < [min, max] -> flag_var < max
296 : flag_var > [min, max] -> flag_var > min
297 :
298 : We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
299 : flag_var <= [min, max] -> flag_var < [min, max+1]
300 : flag_var >= [min, max] -> flag_var > [min-1, max]
301 : if no overflow/wrap. */
302 111 : tree type = TREE_TYPE (cond_lhs);
303 111 : int_range_max r;
304 206 : if (!INTEGRAL_TYPE_P (type)
305 188 : || !get_range_query (cfun)->range_of_expr (r, cond_rhs)
306 94 : || r.undefined_p ()
307 205 : || r.varying_p ())
308 95 : continue;
309 :
310 16 : wide_int min = r.lower_bound ();
311 16 : wide_int max = r.upper_bound ();
312 32 : if (code == LE_EXPR
313 16 : && max != wi::max_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
314 : {
315 0 : code = LT_EXPR;
316 0 : max = max + 1;
317 : }
318 0 : if (code == GE_EXPR
319 17 : && min != wi::min_value (TYPE_PRECISION (type), TYPE_SIGN (type)))
320 : {
321 0 : code = GT_EXPR;
322 0 : min = min - 1;
323 : }
324 16 : if (code == LT_EXPR)
325 12 : cond_rhs = wide_int_to_tree (type, max);
326 4 : else if (code == GT_EXPR)
327 0 : cond_rhs = wide_int_to_tree (type, min);
328 : else
329 4 : continue;
330 111 : }
331 : else
332 3 : continue;
333 :
334 743 : if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
335 0 : continue;
336 :
337 743 : if (gimple_code (*flag_def) != GIMPLE_PHI
338 164 : || gimple_bb (*flag_def) != gimple_bb (phi)
339 906 : || !find_matching_predicate_in_rest_chains (pred, preds))
340 580 : continue;
341 :
342 : /* Return predicate found. */
343 163 : *boundary_cst = cond_rhs;
344 163 : ++i;
345 163 : return code;
346 : }
347 :
348 : return ERROR_MARK;
349 : }
350 :
351 : /* Return true if all interesting opnds are pruned, false otherwise.
352 : PHI is the phi node with interesting operands, OPNDS is the bitmap
353 : of the interesting operand positions, FLAG_DEF is the statement
354 : defining the flag guarding the use of the PHI output, BOUNDARY_CST
355 : is the const value used in the predicate associated with the flag,
356 : CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
357 : is the pointer set of phis visited, and VISITED_FLAG_PHIS is
358 : the pointer to the pointer set of flag definitions that are also
359 : phis.
360 :
361 : Example scenario:
362 :
363 : BB1:
364 : flag_1 = phi <0, 1> // (1)
365 : var_1 = phi <undef, some_val>
366 :
367 :
368 : BB2:
369 : flag_2 = phi <0, flag_1, flag_1> // (2)
370 : var_2 = phi <undef, var_1, var_1>
371 : if (flag_2 == 1)
372 : goto BB3;
373 :
374 : BB3:
375 : use of var_2 // (3)
376 :
377 : Because some flag arg in (1) is not constant, if we do not look into
378 : the flag phis recursively, it is conservatively treated as unknown and
379 : var_1 is thought to flow into use at (3). Since var_1 is potentially
380 : uninitialized a false warning will be emitted.
381 : Checking recursively into (1), the compiler can find out that only
382 : some_val (which is defined) can flow into (3) which is OK. */
383 :
384 : bool
385 393 : uninit_analysis::prune_phi_opnds (gphi *phi, unsigned opnds, gphi *flag_def,
386 : tree boundary_cst, tree_code cmp_code,
387 : hash_set<gphi *> *visited_phis,
388 : bitmap *visited_flag_phis,
389 : unsigned &max_attempts)
390 : {
391 : /* The Boolean predicate guarding the PHI definition. Initialized
392 : lazily from PHI in the first call to is_use_guarded() and cached
393 : for subsequent iterations. */
394 393 : uninit_analysis def_preds (m_eval);
395 :
396 393 : unsigned n = MIN (m_eval.max_phi_args, gimple_phi_num_args (flag_def));
397 1518 : for (unsigned i = 0; i < n; i++)
398 : {
399 1176 : if (!MASK_TEST_BIT (opnds, i))
400 293 : continue;
401 :
402 883 : if (max_attempts == 0)
403 : return false;
404 883 : --max_attempts;
405 :
406 883 : tree flag_arg = gimple_phi_arg_def (flag_def, i);
407 883 : if (!is_gimple_constant (flag_arg))
408 : {
409 265 : if (TREE_CODE (flag_arg) != SSA_NAME)
410 : return false;
411 :
412 265 : gphi *flag_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (flag_arg));
413 230 : if (!flag_arg_def)
414 : return false;
415 :
416 230 : tree phi_arg = gimple_phi_arg_def (phi, i);
417 230 : if (TREE_CODE (phi_arg) != SSA_NAME)
418 : return false;
419 :
420 230 : gphi *phi_arg_def = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_arg));
421 230 : if (!phi_arg_def)
422 : return false;
423 :
424 230 : if (gimple_bb (phi_arg_def) != gimple_bb (flag_arg_def))
425 : return false;
426 :
427 230 : if (!*visited_flag_phis)
428 36 : *visited_flag_phis = BITMAP_ALLOC (NULL);
429 :
430 230 : tree phi_result = gimple_phi_result (flag_arg_def);
431 230 : if (bitmap_bit_p (*visited_flag_phis, SSA_NAME_VERSION (phi_result)))
432 : return false;
433 :
434 230 : bitmap_set_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
435 :
436 : /* Now recursively try to prune the interesting phi args. */
437 230 : unsigned opnds_arg_phi = m_eval.phi_arg_set (phi_arg_def);
438 230 : if (!prune_phi_opnds (phi_arg_def, opnds_arg_phi, flag_arg_def,
439 : boundary_cst, cmp_code, visited_phis,
440 : visited_flag_phis, max_attempts))
441 : return false;
442 :
443 229 : bitmap_clear_bit (*visited_flag_phis, SSA_NAME_VERSION (phi_result));
444 229 : continue;
445 229 : }
446 :
447 : /* Now check if the constant is in the guarded range. */
448 618 : if (is_value_included_in (flag_arg, boundary_cst, cmp_code))
449 : {
450 : /* Now that we know that this undefined edge is not pruned.
451 : If the operand is defined by another phi, we can further
452 : prune the incoming edges of that phi by checking
453 : the predicates of this operands. */
454 :
455 55 : tree opnd = gimple_phi_arg_def (phi, i);
456 55 : gimple *opnd_def = SSA_NAME_DEF_STMT (opnd);
457 91 : if (gphi *opnd_def_phi = dyn_cast <gphi *> (opnd_def))
458 : {
459 40 : unsigned opnds2 = m_eval.phi_arg_set (opnd_def_phi);
460 40 : if (!MASK_EMPTY (opnds2))
461 : {
462 40 : edge opnd_edge = gimple_phi_arg_edge (phi, i);
463 40 : if (def_preds.is_use_guarded (phi, opnd_edge->src,
464 : opnd_def_phi, opnds2,
465 : visited_phis))
466 : return false;
467 : }
468 : }
469 : else
470 : return false;
471 : }
472 : }
473 :
474 : return true;
475 393 : }
476 :
477 : /* Recursively compute the set PHI's incoming edges with "uninteresting"
478 : operands of a phi chain, i.e., those for which EVAL returns false.
479 : CD_ROOT is the control dependence root from which edges are collected
480 : up the CFG nodes that it's dominated by. *EDGES holds the result, and
481 : VISITED is used for detecting cycles. */
482 :
483 : void
484 285 : uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
485 : vec<edge> *edges,
486 : hash_set<gimple *> *visited)
487 : {
488 285 : if (visited->elements () == 0
489 : && DEBUG_PREDICATE_ANALYZER
490 285 : && dump_file)
491 : {
492 2 : fprintf (dump_file, "%s for cd_root %u and ",
493 : __func__, cd_root->index);
494 2 : print_gimple_stmt (dump_file, phi, 0);
495 :
496 : }
497 :
498 285 : if (visited->add (phi))
499 : return;
500 :
501 249 : unsigned n = gimple_phi_num_args (phi);
502 249 : unsigned opnds_arg_phi = m_eval.phi_arg_set (phi);
503 877 : for (unsigned i = 0; i < n; i++)
504 : {
505 628 : if (!MASK_TEST_BIT (opnds_arg_phi, i))
506 : {
507 : /* Add the edge for a not maybe-undefined edge value. */
508 253 : edge opnd_edge = gimple_phi_arg_edge (phi, i);
509 253 : if (dump_file && (dump_flags & TDF_DETAILS))
510 : {
511 0 : fprintf (dump_file,
512 : "\tFound def edge %i -> %i for cd_root %i "
513 : "and operand %u of: ",
514 0 : opnd_edge->src->index, opnd_edge->dest->index,
515 : cd_root->index, i);
516 0 : print_gimple_stmt (dump_file, phi, 0);
517 : }
518 253 : edges->safe_push (opnd_edge);
519 253 : continue;
520 253 : }
521 : else
522 : {
523 375 : tree opnd = gimple_phi_arg_def (phi, i);
524 375 : if (TREE_CODE (opnd) == SSA_NAME)
525 : {
526 375 : gimple *def = SSA_NAME_DEF_STMT (opnd);
527 375 : if (gimple_code (def) == GIMPLE_PHI
528 375 : && dominated_by_p (CDI_DOMINATORS, gimple_bb (def), cd_root))
529 : /* Process PHI defs of maybe-undefined edge values
530 : recursively. */
531 97 : collect_phi_def_edges (as_a<gphi *> (def), cd_root, edges,
532 : visited);
533 : }
534 : }
535 : }
536 : }
537 :
538 : /* Return a bitset of all PHI arguments or zero if there are too many. */
539 :
540 : unsigned
541 0 : uninit_analysis::func_t::phi_arg_set (gphi *phi)
542 : {
543 0 : unsigned n = gimple_phi_num_args (phi);
544 :
545 0 : if (max_phi_args < n)
546 : return 0;
547 :
548 : /* Set the least significant N bits. */
549 0 : return (1U << n) - 1;
550 : }
551 :
552 : /* Determine if the predicate set of the use does not overlap with that
553 : of the interesting paths. The most common scenario of guarded use is
554 : in Example 1:
555 : Example 1:
556 : if (some_cond)
557 : {
558 : x = ...; // set x to valid
559 : flag = true;
560 : }
561 :
562 : ... some code ...
563 :
564 : if (flag)
565 : use (x); // use when x is valid
566 :
567 : The real world examples are usually more complicated, but similar
568 : and usually result from inlining:
569 :
570 : bool init_func (int * x)
571 : {
572 : if (some_cond)
573 : return false;
574 : *x = ...; // set *x to valid
575 : return true;
576 : }
577 :
578 : void foo (..)
579 : {
580 : int x;
581 :
582 : if (!init_func (&x))
583 : return;
584 :
585 : .. some_code ...
586 : use (x); // use when x is valid
587 : }
588 :
589 : Another possible use scenario is in the following trivial example:
590 :
591 : Example 2:
592 : if (n > 0)
593 : x = 1;
594 : ...
595 : if (n > 0)
596 : {
597 : if (m < 2)
598 : ... = x;
599 : }
600 :
601 : Predicate analysis needs to compute the composite predicate:
602 :
603 : 1) 'x' use predicate: (n > 0) .AND. (m < 2)
604 : 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
605 : (the predicate chain for phi operand defs can be computed
606 : starting from a bb that is control equivalent to the phi's
607 : bb and is dominating the operand def.)
608 :
609 : and check overlapping:
610 : (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
611 : <==> false
612 :
613 : This implementation provides a framework that can handle different
614 : scenarios. (Note that many simple cases are handled properly without
615 : the predicate analysis if jump threading eliminates the merge point
616 : thus makes path-sensitive analysis unnecessary.)
617 :
618 : PHI is the phi node whose incoming (undefined) paths need to be
619 : pruned, and OPNDS is the bitmap holding interesting operand
620 : positions. VISITED is the pointer set of phi stmts being
621 : checked. */
622 :
623 : bool
624 409 : uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited,
625 : const predicate &use_preds)
626 : {
627 409 : gimple *flag_def = NULL;
628 409 : tree boundary_cst = NULL_TREE;
629 :
630 : /* Find within the common prefix of multiple predicate chains
631 : a predicate that is a comparison of a flag variable against
632 : a constant. */
633 409 : unsigned i = 0;
634 409 : tree_code cmp_code;
635 459 : while ((cmp_code = find_var_cmp_const (use_preds.chain (), phi, &flag_def,
636 459 : &boundary_cst, i)) != ERROR_MARK)
637 : {
638 : /* Now check all the uninit incoming edges have a constant flag
639 : value that is in conflict with the use guard/predicate. */
640 163 : bitmap visited_flag_phis = NULL;
641 163 : gphi *phi_def = as_a<gphi *> (flag_def);
642 163 : unsigned max_attempts = param_uninit_max_prune_work;
643 163 : bool all_pruned = prune_phi_opnds (phi, opnds, phi_def, boundary_cst,
644 : cmp_code, visited,
645 : &visited_flag_phis, max_attempts);
646 163 : if (visited_flag_phis)
647 36 : BITMAP_FREE (visited_flag_phis);
648 163 : if (all_pruned)
649 113 : return false;
650 : }
651 :
652 : return true;
653 : }
654 :
655 : /* Return true if two predicates PRED1 and X2 are equivalent. Assume
656 : the expressions have already properly re-associated. */
657 :
658 : static inline bool
659 3147 : pred_equal_p (const pred_info &pred1, const pred_info &pred2)
660 : {
661 3147 : if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0)
662 3147 : || !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, 0))
663 2543 : return false;
664 :
665 604 : tree_code c1 = pred1.cond_code, c2;
666 604 : if (pred1.invert != pred2.invert
667 220 : && TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison)
668 219 : c2 = invert_tree_comparison (pred2.cond_code, false);
669 : else
670 385 : c2 = pred2.cond_code;
671 :
672 604 : return c1 == c2;
673 : }
674 :
675 : /* Return true if PRED tests inequality (i.e., X != Y). */
676 :
677 : static inline bool
678 5876 : is_neq_relop_p (const pred_info &pred)
679 : {
680 :
681 2353 : return ((pred.cond_code == NE_EXPR && !pred.invert)
682 4107 : || (pred.cond_code == EQ_EXPR && pred.invert));
683 : }
684 :
685 : /* Returns true if PRED is of the form X != 0. */
686 :
687 : static inline bool
688 5876 : is_neq_zero_form_p (const pred_info &pred)
689 : {
690 9183 : if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
691 5777 : || TREE_CODE (pred.pred_lhs) != SSA_NAME)
692 3226 : return false;
693 : return true;
694 : }
695 :
696 : /* Return true if PRED is equivalent to X != 0. */
697 :
698 : static inline bool
699 18 : pred_expr_equal_p (const pred_info &pred, tree expr)
700 : {
701 18 : if (!is_neq_zero_form_p (pred))
702 : return false;
703 :
704 18 : return operand_equal_p (pred.pred_lhs, expr, 0);
705 : }
706 :
707 : /* Return true if VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can
708 : be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
709 : the like), or BIT_AND_EXPR. EXACT_P is only meaningful for the latter.
710 : Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
711 : For other values of CMPC, EXACT_P is ignored. */
712 :
713 : static bool
714 64 : value_sat_pred_p (tree val, tree boundary, tree_code cmpc,
715 : bool exact_p = false)
716 : {
717 64 : if (cmpc != BIT_AND_EXPR)
718 57 : return is_value_included_in (val, boundary, cmpc);
719 :
720 7 : widest_int andw = wi::to_widest (val) & wi::to_widest (boundary);
721 7 : if (exact_p)
722 3 : return andw == wi::to_widest (val);
723 :
724 4 : return wi::ne_p (andw, 0);
725 7 : }
726 :
727 : /* Return true if the domain of single predicate expression PRED1
728 : is a subset of that of PRED2, and false if it cannot be proved. */
729 :
730 : static bool
731 2584 : subset_of (const pred_info &pred1, const pred_info &pred2)
732 : {
733 2584 : if (pred_equal_p (pred1, pred2))
734 : return true;
735 :
736 2529 : if ((TREE_CODE (pred1.pred_rhs) != INTEGER_CST)
737 2368 : || (TREE_CODE (pred2.pred_rhs) != INTEGER_CST))
738 : return false;
739 :
740 1988 : if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0))
741 : return false;
742 :
743 163 : tree_code code1 = pred1.cond_code;
744 163 : if (pred1.invert)
745 125 : code1 = invert_tree_comparison (code1, false);
746 163 : tree_code code2 = pred2.cond_code;
747 163 : if (pred2.invert)
748 7 : code2 = invert_tree_comparison (code2, false);
749 :
750 163 : if (code2 == NE_EXPR && code1 == NE_EXPR)
751 : return false;
752 :
753 160 : if (code2 == NE_EXPR)
754 49 : return !value_sat_pred_p (pred2.pred_rhs, pred1.pred_rhs, code1);
755 :
756 111 : if (code1 == EQ_EXPR)
757 2 : return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2);
758 :
759 109 : if (code1 == code2)
760 13 : return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2,
761 13 : code1 == BIT_AND_EXPR);
762 :
763 : return false;
764 : }
765 :
766 : /* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
767 : Return false if it cannot be proven so. */
768 :
769 : static bool
770 466 : subset_of (const pred_chain &chain1, const pred_chain &chain2)
771 : {
772 466 : unsigned np1 = chain1.length ();
773 466 : unsigned np2 = chain2.length ();
774 531 : for (unsigned i2 = 0; i2 < np2; i2++)
775 : {
776 482 : bool found = false;
777 482 : const pred_info &info2 = chain2[i2];
778 1341 : for (unsigned i1 = 0; i1 < np1; i1++)
779 : {
780 924 : const pred_info &info1 = chain1[i1];
781 924 : if (subset_of (info1, info2))
782 : {
783 : found = true;
784 : break;
785 : }
786 : }
787 482 : if (!found)
788 : return false;
789 : }
790 : return true;
791 : }
792 :
793 : /* Return true if the domain defined by the predicate chain PREDS is
794 : a subset of the domain of *THIS. Return false if PREDS's domain
795 : is not a subset of any of the sub-domains of *THIS (corresponding
796 : to each individual chains in it), even though it may be still be
797 : a subset of whole domain of *THIS which is the union (ORed) of all
798 : its subdomains. In other words, the result is conservative. */
799 :
800 : bool
801 233 : predicate::includes (const pred_chain &chain) const
802 : {
803 650 : for (unsigned i = 0; i < m_preds.length (); i++)
804 466 : if (subset_of (chain, m_preds[i]))
805 : return true;
806 :
807 : return false;
808 : }
809 :
810 : /* Return true if the domain defined by *THIS is a superset of PREDS's
811 : domain.
812 : Avoid building generic trees (and rely on the folding capability
813 : of the compiler), and instead perform brute force comparison of
814 : individual predicate chains (this won't be a computationally costly
815 : since the chains are pretty short). Returning false does not
816 : necessarily mean *THIS is not a superset of *PREDS, only that
817 : it need not be since the analysis cannot prove it. */
818 :
819 : bool
820 228 : predicate::superset_of (const predicate &preds) const
821 : {
822 277 : for (unsigned i = 0; i < preds.m_preds.length (); i++)
823 233 : if (!includes (preds.m_preds[i]))
824 : return false;
825 :
826 : return true;
827 : }
828 :
829 : /* Remove from every chain in *THIS any (comparison) conjunct whose domain is
830 : a superset of every predicate in EDGE_CONDS, i.e. a conjunct implied by all
831 : of them. Returns true if any conjunct was removed. */
832 :
833 : bool
834 151 : predicate::drop_conjuncts_implied_by (const vec<pred_info> &edge_conds)
835 : {
836 151 : if (edge_conds.is_empty ())
837 : return false;
838 :
839 : bool changed = false;
840 461 : for (unsigned i = 0; i < m_preds.length (); i++)
841 : {
842 310 : pred_chain &chain = m_preds[i];
843 1974 : for (unsigned j = 0; j < chain.length (); )
844 : {
845 : /* Only reason about comparison conjuncts: subset_of negates the
846 : code for inverted predicates, which is invalid for e.g. the
847 : BIT_AND_EXPR of an "x & mask" predicate. */
848 1664 : bool implied = TREE_CODE_CLASS (chain[j].cond_code) == tcc_comparison;
849 4988 : for (unsigned k = 0; implied && k < edge_conds.length (); k++)
850 1660 : if (!subset_of (edge_conds[k], chain[j]))
851 : implied = false;
852 :
853 1664 : if (implied)
854 : {
855 4 : chain.ordered_remove (j);
856 4 : changed = true;
857 : }
858 : else
859 1660 : j++;
860 : }
861 : }
862 : return changed;
863 : }
864 :
865 : /* Create a predicate of the form OP != 0 and push it the work list CHAIN. */
866 :
867 : static void
868 60 : push_to_worklist (tree op, pred_chain *chain, hash_set<tree> *mark_set)
869 : {
870 60 : if (mark_set->contains (op))
871 2 : return;
872 58 : mark_set->add (op);
873 :
874 58 : pred_info arg_pred;
875 58 : arg_pred.pred_lhs = op;
876 58 : arg_pred.pred_rhs = integer_zero_node;
877 58 : arg_pred.cond_code = NE_EXPR;
878 58 : arg_pred.invert = false;
879 58 : chain->safe_push (arg_pred);
880 : }
881 :
882 : /* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
883 : rhs. */
884 :
885 : static pred_info
886 40 : get_pred_info_from_cmp (const gimple *cmp_assign)
887 : {
888 40 : pred_info pred;
889 40 : pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
890 40 : pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
891 40 : pred.cond_code = gimple_assign_rhs_code (cmp_assign);
892 40 : pred.invert = false;
893 40 : return pred;
894 : }
895 :
896 : /* Return a pred_info for the GIMPLE_COND ending E's source block. The true
897 : edge corresponds to the condition holding, so a false edge yields the
898 : inverted predicate. */
899 :
900 : static pred_info
901 3411 : get_pred_info_from_cond_edge (edge e)
902 : {
903 6822 : gcond *cond = as_a<gcond *> (*gsi_last_bb (e->src));
904 3411 : pred_info pred;
905 3411 : pred.pred_lhs = gimple_cond_lhs (cond);
906 3411 : pred.pred_rhs = gimple_cond_rhs (cond);
907 3411 : pred.cond_code = gimple_cond_code (cond);
908 3411 : pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
909 3411 : return pred;
910 : }
911 :
912 : /* If PHI is a degenerate phi with all operands having the same value (relop)
913 : update *PRED to that value and return true. Otherwise return false. */
914 :
915 : static bool
916 65 : is_degenerate_phi (gimple *phi, pred_info *pred)
917 : {
918 65 : tree op0 = gimple_phi_arg_def (phi, 0);
919 :
920 65 : if (TREE_CODE (op0) != SSA_NAME)
921 : return false;
922 :
923 34 : gimple *def0 = SSA_NAME_DEF_STMT (op0);
924 34 : if (gimple_code (def0) != GIMPLE_ASSIGN)
925 : return false;
926 :
927 1 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
928 : return false;
929 :
930 1 : pred_info pred0 = get_pred_info_from_cmp (def0);
931 :
932 1 : unsigned n = gimple_phi_num_args (phi);
933 1 : for (unsigned i = 1; i < n; ++i)
934 : {
935 1 : tree op = gimple_phi_arg_def (phi, i);
936 1 : if (TREE_CODE (op) != SSA_NAME)
937 1 : return false;
938 :
939 0 : gimple *def = SSA_NAME_DEF_STMT (op);
940 0 : if (gimple_code (def) != GIMPLE_ASSIGN)
941 : return false;
942 :
943 0 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
944 : return false;
945 :
946 0 : pred_info pred = get_pred_info_from_cmp (def);
947 0 : if (!pred_equal_p (pred, pred0))
948 : return false;
949 : }
950 :
951 0 : *pred = pred0;
952 0 : return true;
953 : }
954 :
955 : /* If compute_control_dep_chain bailed out due to limits this routine
956 : tries to build a partial sparse path using dominators. Returns
957 : path edges whose predicates are always true when reaching E. */
958 :
959 : static void
960 0 : simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
961 : {
962 0 : if (!dominated_by_p (CDI_DOMINATORS, to, from))
963 : return;
964 :
965 : basic_block src = to;
966 : while (src != from
967 0 : && chain.length () <= MAX_CHAIN_LEN)
968 : {
969 0 : basic_block dest = src;
970 0 : src = get_immediate_dominator (CDI_DOMINATORS, src);
971 0 : if (single_pred_p (dest))
972 : {
973 0 : edge pred_e = single_pred_edge (dest);
974 0 : gcc_assert (pred_e->src == src);
975 0 : if (!(pred_e->flags & ((EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK)))
976 0 : && !single_succ_p (src))
977 0 : chain.safe_push (pred_e);
978 : }
979 : }
980 : }
981 :
982 : /* Perform a DFS walk on predecessor edges to mark the region denoted
983 : by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
984 : Blocks in the region are marked with FLAG and added to BBS. BBS is
985 : filled up to its capacity only after which the walk is terminated
986 : and false is returned. If the whole region was marked, true is returned. */
987 :
988 : static bool
989 822 : dfs_mark_dominating_region (basic_block exit_src, basic_block dom, int flag,
990 : vec<basic_block> &bbs)
991 : {
992 822 : if (exit_src == dom || exit_src->flags & flag)
993 : return true;
994 669 : if (!bbs.space (1))
995 : return false;
996 669 : bbs.quick_push (exit_src);
997 669 : exit_src->flags |= flag;
998 669 : auto_vec<edge_iterator, 20> stack (bbs.allocated () - bbs.length () + 1);
999 669 : stack.quick_push (ei_start (exit_src->preds));
1000 12672 : while (!stack.is_empty ())
1001 : {
1002 : /* Look at the edge on the top of the stack. */
1003 12003 : edge_iterator ei = stack.last ();
1004 12003 : basic_block src = ei_edge (ei)->src;
1005 :
1006 : /* Check if the edge source has been visited yet. */
1007 12003 : if (!(src->flags & flag))
1008 : {
1009 : /* Mark the source if there's still space. If not, return early. */
1010 5206 : if (!bbs.space (1))
1011 0 : return false;
1012 5206 : src->flags |= flag;
1013 5206 : bbs.quick_push (src);
1014 :
1015 : /* Queue its predecessors if we didn't reach DOM. */
1016 16689 : if (src != dom && EDGE_COUNT (src->preds) > 0)
1017 4686 : stack.quick_push (ei_start (src->preds));
1018 : }
1019 : else
1020 : {
1021 6797 : if (!ei_one_before_end_p (ei))
1022 1442 : ei_next (&stack.last ());
1023 : else
1024 5355 : stack.pop ();
1025 : }
1026 : }
1027 : return true;
1028 669 : }
1029 :
1030 : static bool
1031 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1032 : vec<edge> cd_chains[], unsigned *num_chains,
1033 : vec<edge> &cur_cd_chain, unsigned *num_calls,
1034 : unsigned in_region, unsigned depth,
1035 : bool *complete_p);
1036 :
1037 : /* Helper for compute_control_dep_chain that walks the post-dominator
1038 : chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB. */
1039 :
1040 : static bool
1041 9482 : compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb,
1042 : basic_block target_bb,
1043 : vec<edge> cd_chains[], unsigned *num_chains,
1044 : vec<edge> &cur_cd_chain, unsigned *num_calls,
1045 : unsigned in_region, unsigned depth,
1046 : bool *complete_p)
1047 : {
1048 9482 : bool found_cd_chain = false;
1049 15597 : while (cd_bb != target_bb)
1050 : {
1051 12211 : if (cd_bb == dep_bb)
1052 : {
1053 : /* Found a direct control dependence. */
1054 1060 : if (*num_chains < MAX_NUM_CHAINS)
1055 : {
1056 948 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1057 4 : fprintf (dump_file, "%*s pushing { %s }\n",
1058 8 : depth, "", format_edge_vec (cur_cd_chain).c_str ());
1059 948 : cd_chains[*num_chains] = cur_cd_chain.copy ();
1060 948 : (*num_chains)++;
1061 : }
1062 : found_cd_chain = true;
1063 : /* Check path from next edge. */
1064 : break;
1065 : }
1066 :
1067 : /* If the dominating region has been marked avoid walking outside. */
1068 11151 : if (in_region != 0 && !(cd_bb->flags & in_region))
1069 : break;
1070 :
1071 : /* Count the number of steps we perform to limit compile-time.
1072 : This should cover both recursion and the post-dominator walk. */
1073 8873 : if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
1074 : {
1075 0 : if (dump_file)
1076 0 : fprintf (dump_file, "param_uninit_control_dep_attempts "
1077 : "exceeded: %u\n", *num_calls);
1078 0 : *complete_p = false;
1079 0 : break;
1080 : }
1081 8873 : ++*num_calls;
1082 :
1083 : /* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
1084 8873 : if (!single_succ_p (cd_bb)
1085 8873 : && compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
1086 : num_chains, cur_cd_chain,
1087 : num_calls, in_region, depth + 1,
1088 : complete_p))
1089 : {
1090 : found_cd_chain = true;
1091 : break;
1092 : }
1093 :
1094 : /* The post-dominator walk will reach a backedge only
1095 : from a forwarder, otherwise it should choose to exit
1096 : the SCC. */
1097 6406 : if (single_succ_p (cd_bb)
1098 6406 : && single_succ_edge (cd_bb)->flags & EDGE_DFS_BACK)
1099 : break;
1100 6198 : basic_block prev_cd_bb = cd_bb;
1101 6198 : cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb);
1102 6198 : if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1103 : break;
1104 : /* Pick up conditions toward the post dominator such like
1105 : loop exit conditions. See gcc.dg/uninit-pred-11.c and
1106 : gcc.dg/unninit-pred-12.c and PR106754. */
1107 12230 : if (single_pred_p (cd_bb))
1108 : {
1109 44 : edge e2 = single_pred_edge (cd_bb);
1110 44 : gcc_assert (e2->src == prev_cd_bb);
1111 : /* But avoid adding fallthru or abnormal edges. */
1112 44 : if (!(e2->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1113 88 : && !single_succ_p (prev_cd_bb))
1114 43 : cur_cd_chain.safe_push (e2);
1115 : }
1116 : }
1117 9482 : return found_cd_chain;
1118 : }
1119 :
1120 :
1121 : /* Recursively compute the control dependence chains (paths of edges)
1122 : from the dependent basic block, DEP_BB, up to the dominating basic
1123 : block, DOM_BB (the head node of a chain should be dominated by it),
1124 : storing them in the CD_CHAINS array.
1125 : CUR_CD_CHAIN is the current chain being computed.
1126 : *NUM_CHAINS is total number of chains in the CD_CHAINS array.
1127 : *NUM_CALLS is the number of recursive calls to control unbounded
1128 : recursion.
1129 : Return true if the information is successfully computed, false if
1130 : there is no control dependence or not computed.
1131 : *COMPLETE_P is set to false if we stopped walking due to limits.
1132 : In this case there might be missing chains. */
1133 :
1134 : static bool
1135 4486 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1136 : vec<edge> cd_chains[], unsigned *num_chains,
1137 : vec<edge> &cur_cd_chain, unsigned *num_calls,
1138 : unsigned in_region, unsigned depth,
1139 : bool *complete_p)
1140 : {
1141 : /* In our recursive calls this doesn't happen. */
1142 4486 : if (single_succ_p (dom_bb))
1143 : return false;
1144 :
1145 : /* FIXME: Use a set instead. */
1146 4486 : unsigned cur_chain_len = cur_cd_chain.length ();
1147 4486 : if (cur_chain_len > MAX_CHAIN_LEN)
1148 : {
1149 204 : if (dump_file)
1150 0 : fprintf (dump_file, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);
1151 :
1152 204 : *complete_p = false;
1153 204 : return false;
1154 : }
1155 :
1156 4282 : if (cur_chain_len > 5)
1157 : {
1158 2211 : if (dump_file)
1159 0 : fprintf (dump_file, "chain length exceeds 5: %u\n", cur_chain_len);
1160 : }
1161 :
1162 4282 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1163 7 : fprintf (dump_file,
1164 : "%*s%s (dom_bb = %u, dep_bb = %u, ..., "
1165 : "cur_cd_chain = { %s }, ...)\n",
1166 7 : depth, "", __func__, dom_bb->index, dep_bb->index,
1167 14 : format_edge_vec (cur_cd_chain).c_str ());
1168 :
1169 4282 : bool found_cd_chain = false;
1170 :
1171 : /* Iterate over DOM_BB's successors. */
1172 4282 : edge e;
1173 4282 : edge_iterator ei;
1174 12955 : FOR_EACH_EDGE (e, ei, dom_bb->succs)
1175 : {
1176 8673 : if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1177 13 : continue;
1178 :
1179 8660 : basic_block cd_bb = e->dest;
1180 8660 : unsigned pop_mark = cur_cd_chain.length ();
1181 8660 : cur_cd_chain.safe_push (e);
1182 8660 : basic_block target_bb
1183 8660 : = get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb);
1184 : /* Walk the post-dominator chain up to the CFG merge. */
1185 8660 : found_cd_chain
1186 8660 : |= compute_control_dep_chain_pdom (cd_bb, dep_bb, target_bb,
1187 : cd_chains, num_chains,
1188 : cur_cd_chain, num_calls,
1189 : in_region, depth, complete_p);
1190 8660 : cur_cd_chain.truncate (pop_mark);
1191 17320 : gcc_assert (cur_cd_chain.length () == cur_chain_len);
1192 : }
1193 :
1194 8564 : gcc_assert (cur_cd_chain.length () == cur_chain_len);
1195 : return found_cd_chain;
1196 : }
1197 :
1198 : /* Wrapper around the compute_control_dep_chain worker above. Returns
1199 : true when the collected set of chains in CD_CHAINS is complete. */
1200 :
1201 : static bool
1202 822 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1203 : vec<edge> cd_chains[], unsigned *num_chains,
1204 : unsigned in_region = 0)
1205 : {
1206 822 : auto_vec<edge, 10> cur_cd_chain;
1207 822 : unsigned num_calls = 0;
1208 822 : unsigned depth = 0;
1209 822 : bool complete_p = true;
1210 : /* Walk the post-dominator chain. */
1211 822 : cur_cd_chain.reserve (MAX_CHAIN_LEN + 1);
1212 822 : compute_control_dep_chain_pdom (dom_bb, dep_bb, NULL, cd_chains,
1213 : num_chains, cur_cd_chain, &num_calls,
1214 : in_region, depth, &complete_p);
1215 822 : return complete_p;
1216 822 : }
1217 :
1218 : /* Implemented simplifications:
1219 :
1220 : 1a) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1221 : 1b) [!](X rel y) AND [!](X rel y') where y == y' or both constant
1222 : can possibly be simplified
1223 : 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1224 : 3) X OR (!X AND Y) is equivalent to (X OR Y);
1225 : 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1226 : (x != 0 AND y != 0)
1227 : 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1228 : (X AND Y) OR Z
1229 :
1230 : PREDS is the predicate chains, and N is the number of chains. */
1231 :
1232 : /* Implement rule 1a above. PREDS is the AND predicate to simplify
1233 : in place. */
1234 :
1235 : static void
1236 786 : simplify_1a (pred_chain &chain)
1237 : {
1238 786 : bool simplified = false;
1239 786 : pred_chain s_chain = vNULL;
1240 :
1241 786 : unsigned n = chain.length ();
1242 3832 : for (unsigned i = 0; i < n; i++)
1243 : {
1244 3046 : pred_info &a_pred = chain[i];
1245 :
1246 4739 : if (!a_pred.pred_lhs
1247 3046 : || !is_neq_zero_form_p (a_pred))
1248 1693 : continue;
1249 :
1250 1353 : gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred.pred_lhs);
1251 1353 : if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1252 344 : continue;
1253 :
1254 1009 : if (gimple_assign_rhs_code (def_stmt) != BIT_IOR_EXPR)
1255 1002 : continue;
1256 :
1257 19 : for (unsigned j = 0; j < n; j++)
1258 : {
1259 12 : const pred_info &b_pred = chain[j];
1260 :
1261 15 : if (!b_pred.pred_lhs
1262 12 : || !is_neq_zero_form_p (b_pred))
1263 3 : continue;
1264 :
1265 9 : if (pred_expr_equal_p (b_pred, gimple_assign_rhs1 (def_stmt))
1266 9 : || pred_expr_equal_p (b_pred, gimple_assign_rhs2 (def_stmt)))
1267 : {
1268 : /* Mark A_PRED for removal from PREDS. */
1269 0 : a_pred.pred_lhs = NULL;
1270 0 : a_pred.pred_rhs = NULL;
1271 0 : simplified = true;
1272 0 : break;
1273 : }
1274 : }
1275 : }
1276 :
1277 786 : if (!simplified)
1278 786 : return;
1279 :
1280 : /* Remove predicates marked above. */
1281 0 : for (unsigned i = 0; i < n; i++)
1282 : {
1283 0 : pred_info &a_pred = chain[i];
1284 0 : if (!a_pred.pred_lhs)
1285 0 : continue;
1286 0 : s_chain.safe_push (a_pred);
1287 : }
1288 :
1289 0 : chain.release ();
1290 0 : chain = s_chain;
1291 : }
1292 :
1293 : /* Implement rule 1b above. PREDS is the AND predicate to simplify
1294 : in place. Returns true if CHAIN simplifies to true or false. */
1295 :
1296 : static bool
1297 786 : simplify_1b (pred_chain &chain)
1298 : {
1299 3632 : for (unsigned i = 0; i < chain.length (); i++)
1300 : {
1301 2850 : pred_info &a_pred = chain[i];
1302 :
1303 10596 : for (unsigned j = i + 1; j < chain.length (); ++j)
1304 : {
1305 7750 : pred_info &b_pred = chain[j];
1306 :
1307 7750 : if (!operand_equal_p (a_pred.pred_lhs, b_pred.pred_lhs)
1308 7750 : || (!operand_equal_p (a_pred.pred_rhs, b_pred.pred_rhs)
1309 218 : && !(CONSTANT_CLASS_P (a_pred.pred_rhs)
1310 214 : && CONSTANT_CLASS_P (b_pred.pred_rhs))))
1311 7544 : continue;
1312 :
1313 206 : tree_code a_code = a_pred.cond_code;
1314 206 : if (a_pred.invert)
1315 196 : a_code = invert_tree_comparison (a_code, false);
1316 206 : tree_code b_code = b_pred.cond_code;
1317 206 : if (b_pred.invert)
1318 34 : b_code = invert_tree_comparison (b_code, false);
1319 : /* Try to combine X a_code Y && X b_code Y'. */
1320 206 : tree comb = maybe_fold_and_comparisons (boolean_type_node,
1321 : a_code,
1322 : a_pred.pred_lhs,
1323 : a_pred.pred_rhs,
1324 : b_code,
1325 : b_pred.pred_lhs,
1326 : b_pred.pred_rhs, NULL);
1327 206 : if (!comb)
1328 : ;
1329 176 : else if (integer_zerop (comb))
1330 : return true;
1331 172 : else if (integer_truep (comb))
1332 : {
1333 0 : chain.ordered_remove (j);
1334 0 : chain.ordered_remove (i);
1335 4 : if (chain.is_empty ())
1336 : return true;
1337 0 : i--;
1338 0 : break;
1339 : }
1340 172 : else if (COMPARISON_CLASS_P (comb)
1341 172 : && operand_equal_p (a_pred.pred_lhs, TREE_OPERAND (comb, 0)))
1342 : {
1343 172 : chain.ordered_remove (j);
1344 172 : a_pred.cond_code = TREE_CODE (comb);
1345 172 : a_pred.pred_rhs = TREE_OPERAND (comb, 1);
1346 172 : a_pred.invert = false;
1347 172 : j--;
1348 : }
1349 : }
1350 : }
1351 :
1352 : return false;
1353 : }
1354 :
1355 : /* Implements rule 2 for the OR predicate PREDS:
1356 :
1357 : 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1358 :
1359 : bool
1360 120 : predicate::simplify_2 ()
1361 : {
1362 120 : bool simplified = false;
1363 :
1364 : /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1365 : (X AND Y) OR (X AND !Y) is equivalent to X. */
1366 :
1367 625 : for (unsigned i = 0; i < m_preds.length (); i++)
1368 : {
1369 385 : pred_chain &a_chain = m_preds[i];
1370 :
1371 1019 : for (unsigned j = i + 1; j < m_preds.length (); j++)
1372 : {
1373 660 : pred_chain &b_chain = m_preds[j];
1374 1980 : if (b_chain.length () != a_chain.length ())
1375 480 : continue;
1376 :
1377 : unsigned neg_idx = -1U;
1378 589 : for (unsigned k = 0; k < a_chain.length (); ++k)
1379 : {
1380 563 : if (pred_equal_p (a_chain[k], b_chain[k]))
1381 328 : continue;
1382 235 : if (neg_idx != -1U)
1383 : {
1384 : neg_idx = -1U;
1385 : break;
1386 : }
1387 180 : if (pred_neg_p (a_chain[k], b_chain[k]))
1388 : neg_idx = k;
1389 : else
1390 : break;
1391 : }
1392 : /* If we found equal chains with one negated predicate
1393 : simplify. */
1394 180 : if (neg_idx != -1U)
1395 : {
1396 26 : a_chain.ordered_remove (neg_idx);
1397 26 : m_preds.ordered_remove (j);
1398 26 : simplified = true;
1399 531 : if (a_chain.is_empty ())
1400 : {
1401 : /* A && !A simplifies to true, wipe the whole predicate. */
1402 2 : for (unsigned k = 0; k < m_preds.length (); ++k)
1403 1 : m_preds[k].release ();
1404 1 : m_preds.truncate (0);
1405 : }
1406 : break;
1407 : }
1408 : }
1409 : }
1410 :
1411 120 : return simplified;
1412 : }
1413 :
1414 : /* Implement rule 3 for the OR predicate PREDS:
1415 :
1416 : 3) x OR (!x AND y) is equivalent to x OR y. */
1417 :
1418 : bool
1419 120 : predicate::simplify_3 ()
1420 : {
1421 : /* Now iteratively simplify X OR (!X AND Z ..)
1422 : into X OR (Z ...). */
1423 :
1424 120 : unsigned n = m_preds.length ();
1425 120 : if (n < 2)
1426 : return false;
1427 :
1428 : bool simplified = false;
1429 490 : for (unsigned i = 0; i < n; i++)
1430 : {
1431 378 : const pred_chain &a_chain = m_preds[i];
1432 :
1433 378 : if (a_chain.length () != 1)
1434 315 : continue;
1435 :
1436 63 : const pred_info &x = a_chain[0];
1437 285 : for (unsigned j = 0; j < n; j++)
1438 : {
1439 222 : if (j == i)
1440 285 : continue;
1441 :
1442 159 : pred_chain b_chain = m_preds[j];
1443 159 : if (b_chain.length () < 2)
1444 104 : continue;
1445 :
1446 407 : for (unsigned k = 0; k < b_chain.length (); k++)
1447 : {
1448 367 : const pred_info &x2 = b_chain[k];
1449 367 : if (pred_neg_p (x, x2))
1450 : {
1451 15 : b_chain.unordered_remove (k);
1452 15 : simplified = true;
1453 15 : break;
1454 : }
1455 : }
1456 : }
1457 : }
1458 : return simplified;
1459 : }
1460 :
1461 : /* Implement rule 4 for the OR predicate PREDS:
1462 :
1463 : 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1464 : (x != 0 AND y != 0). */
1465 :
1466 : bool
1467 120 : predicate::simplify_4 ()
1468 : {
1469 120 : bool simplified = false;
1470 120 : pred_chain_union s_preds = vNULL;
1471 :
1472 120 : unsigned n = m_preds.length ();
1473 504 : for (unsigned i = 0; i < n; i++)
1474 : {
1475 384 : pred_chain a_chain = m_preds[i];
1476 384 : if (a_chain.length () != 1)
1477 384 : continue;
1478 :
1479 69 : const pred_info &z = a_chain[0];
1480 69 : if (!is_neq_zero_form_p (z))
1481 53 : continue;
1482 :
1483 16 : gimple *def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1484 16 : if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1485 3 : continue;
1486 :
1487 13 : if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1488 13 : continue;
1489 :
1490 0 : for (unsigned j = 0; j < n; j++)
1491 : {
1492 0 : if (j == i)
1493 0 : continue;
1494 :
1495 0 : pred_chain b_chain = m_preds[j];
1496 0 : if (b_chain.length () != 2)
1497 0 : continue;
1498 :
1499 0 : const pred_info &x2 = b_chain[0];
1500 0 : const pred_info &y2 = b_chain[1];
1501 0 : if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
1502 0 : continue;
1503 :
1504 0 : if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1505 0 : && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1506 0 : || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1507 0 : && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1508 : {
1509 : /* Kill a_chain. */
1510 0 : a_chain.release ();
1511 0 : simplified = true;
1512 0 : break;
1513 : }
1514 : }
1515 : }
1516 : /* Now clean up the chain. */
1517 120 : if (simplified)
1518 : {
1519 0 : for (unsigned i = 0; i < n; i++)
1520 : {
1521 0 : if (m_preds[i].is_empty ())
1522 0 : continue;
1523 0 : s_preds.safe_push (m_preds[i]);
1524 : }
1525 :
1526 0 : m_preds.release ();
1527 0 : m_preds = s_preds;
1528 0 : s_preds = vNULL;
1529 : }
1530 :
1531 120 : return simplified;
1532 : }
1533 :
1534 : /* Simplify predicates in *THIS. */
1535 :
1536 : void
1537 526 : predicate::simplify (gimple *use_or_def, bool is_use)
1538 : {
1539 526 : if (dump_file && dump_flags & TDF_DETAILS)
1540 : {
1541 0 : fprintf (dump_file, "Before simplication ");
1542 0 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1543 : }
1544 :
1545 1312 : for (unsigned i = 0; i < m_preds.length (); i++)
1546 : {
1547 786 : ::simplify_1a (m_preds[i]);
1548 786 : if (::simplify_1b (m_preds[i]))
1549 : {
1550 4 : m_preds[i].release ();
1551 4 : m_preds.ordered_remove (i);
1552 4 : i--;
1553 : }
1554 : }
1555 :
1556 526 : if (m_preds.length () < 2)
1557 : return;
1558 :
1559 120 : bool changed;
1560 120 : do
1561 : {
1562 120 : changed = false;
1563 120 : if (simplify_2 ())
1564 : changed = true;
1565 :
1566 120 : if (simplify_3 ())
1567 9 : changed = true;
1568 :
1569 120 : if (simplify_4 ())
1570 0 : changed = true;
1571 : }
1572 : while (changed);
1573 : }
1574 :
1575 : /* Attempt to normalize predicate chains by following UD chains by
1576 : building up a big tree of either IOR operations or AND operations,
1577 : and converting the IOR tree into a pred_chain_union or the BIT_AND
1578 : tree into a pred_chain.
1579 : Example:
1580 :
1581 : _3 = _2 RELOP1 _1;
1582 : _6 = _5 RELOP2 _4;
1583 : _9 = _8 RELOP3 _7;
1584 : _10 = _3 | _6;
1585 : _12 = _9 | _0;
1586 : _t = _10 | _12;
1587 :
1588 : then _t != 0 will be normalized into a pred_chain_union
1589 :
1590 : (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1591 :
1592 : Similarly given:
1593 :
1594 : _3 = _2 RELOP1 _1;
1595 : _6 = _5 RELOP2 _4;
1596 : _9 = _8 RELOP3 _7;
1597 : _10 = _3 & _6;
1598 : _12 = _9 & _0;
1599 :
1600 : then _t != 0 will be normalized into a pred_chain:
1601 : (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1602 : */
1603 :
1604 : /* Normalize predicate PRED:
1605 : 1) if PRED can no longer be normalized, append it to *THIS.
1606 : 2) otherwise if PRED is of the form x != 0, follow x's definition
1607 : and put normalized predicates into WORK_LIST. */
1608 :
1609 : void
1610 2452 : predicate::normalize (pred_chain *norm_chain,
1611 : pred_info pred,
1612 : tree_code and_or_code,
1613 : pred_chain *work_list,
1614 : hash_set<tree> *mark_set)
1615 : {
1616 2452 : if (!is_neq_zero_form_p (pred))
1617 : {
1618 1315 : if (and_or_code == BIT_IOR_EXPR)
1619 0 : push_pred (pred);
1620 : else
1621 1315 : norm_chain->safe_push (pred);
1622 1315 : return;
1623 : }
1624 :
1625 1137 : gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1626 :
1627 1137 : if (gimple_code (def_stmt) == GIMPLE_PHI
1628 1137 : && is_degenerate_phi (def_stmt, &pred))
1629 : /* PRED has been modified above. */
1630 0 : work_list->safe_push (pred);
1631 1137 : else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
1632 : {
1633 3 : unsigned n = gimple_phi_num_args (def_stmt);
1634 :
1635 : /* Punt for a nonzero constant. The predicate should be one guarding
1636 : the phi edge. */
1637 9 : for (unsigned i = 0; i < n; ++i)
1638 : {
1639 6 : tree op = gimple_phi_arg_def (def_stmt, i);
1640 6 : if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1641 : {
1642 0 : push_pred (pred);
1643 0 : return;
1644 : }
1645 : }
1646 :
1647 9 : for (unsigned i = 0; i < n; ++i)
1648 : {
1649 6 : tree op = gimple_phi_arg_def (def_stmt, i);
1650 6 : if (integer_zerop (op))
1651 0 : continue;
1652 :
1653 6 : push_to_worklist (op, work_list, mark_set);
1654 : }
1655 : }
1656 1134 : else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1657 : {
1658 263 : if (and_or_code == BIT_IOR_EXPR)
1659 7 : push_pred (pred);
1660 : else
1661 256 : norm_chain->safe_push (pred);
1662 : }
1663 871 : else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
1664 : {
1665 : /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
1666 61 : if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
1667 : {
1668 : /* But treat x & 3 as a condition. */
1669 34 : if (and_or_code == BIT_AND_EXPR)
1670 : {
1671 34 : pred_info n_pred;
1672 34 : n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
1673 34 : n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
1674 34 : n_pred.cond_code = and_or_code;
1675 34 : n_pred.invert = false;
1676 34 : norm_chain->safe_push (n_pred);
1677 : }
1678 : }
1679 : else
1680 : {
1681 27 : push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
1682 27 : push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
1683 : }
1684 : }
1685 810 : else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1686 : == tcc_comparison)
1687 : {
1688 39 : pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1689 39 : if (and_or_code == BIT_IOR_EXPR)
1690 0 : push_pred (n_pred);
1691 : else
1692 39 : norm_chain->safe_push (n_pred);
1693 : }
1694 : else
1695 : {
1696 771 : if (and_or_code == BIT_IOR_EXPR)
1697 0 : push_pred (pred);
1698 : else
1699 771 : norm_chain->safe_push (pred);
1700 : }
1701 : }
1702 :
1703 : /* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */
1704 :
1705 : void
1706 279 : predicate::normalize (const pred_info &pred)
1707 : {
1708 279 : if (!is_neq_zero_form_p (pred))
1709 : {
1710 162 : push_pred (pred);
1711 413 : return;
1712 : }
1713 :
1714 117 : tree_code and_or_code = ERROR_MARK;
1715 :
1716 117 : gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1717 117 : if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
1718 43 : and_or_code = gimple_assign_rhs_code (def_stmt);
1719 117 : if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
1720 : {
1721 89 : if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
1722 : {
1723 0 : pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1724 0 : push_pred (n_pred);
1725 : }
1726 : else
1727 89 : push_pred (pred);
1728 89 : return;
1729 : }
1730 :
1731 :
1732 28 : pred_chain norm_chain = vNULL;
1733 28 : pred_chain work_list = vNULL;
1734 28 : work_list.safe_push (pred);
1735 28 : hash_set<tree> mark_set;
1736 :
1737 82 : while (!work_list.is_empty ())
1738 : {
1739 54 : pred_info a_pred = work_list.pop ();
1740 54 : normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
1741 : }
1742 :
1743 28 : if (and_or_code == BIT_AND_EXPR)
1744 25 : m_preds.safe_push (norm_chain);
1745 :
1746 28 : work_list.release ();
1747 28 : }
1748 :
1749 : /* Normalize a single predicate PRED_CHAIN and append it to *THIS. */
1750 :
1751 : void
1752 476 : predicate::normalize (const pred_chain &chain)
1753 : {
1754 476 : pred_chain work_list = vNULL;
1755 476 : hash_set<tree> mark_set;
1756 2842 : for (unsigned i = 0; i < chain.length (); i++)
1757 : {
1758 2366 : work_list.safe_push (chain[i]);
1759 2366 : mark_set.add (chain[i].pred_lhs);
1760 : }
1761 :
1762 : /* Normalized chain of predicates built up below. */
1763 476 : pred_chain norm_chain = vNULL;
1764 2874 : while (!work_list.is_empty ())
1765 : {
1766 2398 : pred_info pi = work_list.pop ();
1767 : /* The predicate object is not modified here, only NORM_CHAIN and
1768 : WORK_LIST are appended to. */
1769 4796 : unsigned oldlen = m_preds.length ();
1770 2398 : normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
1771 3816 : gcc_assert (m_preds.length () == oldlen);
1772 : }
1773 :
1774 476 : m_preds.safe_push (norm_chain);
1775 476 : work_list.release ();
1776 476 : }
1777 :
1778 : /* Normalize predicate chains in THIS. */
1779 :
1780 : void
1781 526 : predicate::normalize (gimple *use_or_def, bool is_use)
1782 : {
1783 526 : if (dump_file && dump_flags & TDF_DETAILS)
1784 : {
1785 0 : fprintf (dump_file, "Before normalization ");
1786 0 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1787 : }
1788 :
1789 526 : predicate norm_preds (empty_val ());
1790 1281 : for (unsigned i = 0; i < m_preds.length (); i++)
1791 : {
1792 755 : if (m_preds[i].length () != 1)
1793 476 : norm_preds.normalize (m_preds[i]);
1794 : else
1795 279 : norm_preds.normalize (m_preds[i][0]);
1796 : }
1797 :
1798 526 : *this = norm_preds;
1799 :
1800 526 : if (dump_file)
1801 : {
1802 4 : fprintf (dump_file, "After normalization ");
1803 6 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1804 : }
1805 526 : }
1806 :
1807 : /* Convert the chains of control dependence edges into a set of predicates.
1808 : A control dependence chain is represented by a vector edges. DEP_CHAINS
1809 : points to an array of NUM_CHAINS dependence chains. One edge in
1810 : a dependence chain is mapped to predicate expression represented by
1811 : pred_info type. One dependence chain is converted to a composite
1812 : predicate that is the result of AND operation of pred_info mapped to
1813 : each edge. A composite predicate is represented by a vector of
1814 : pred_info. Sets M_PREDS to the resulting composite predicates. */
1815 :
1816 : void
1817 757 : predicate::init_from_control_deps (const vec<edge> *dep_chains,
1818 : unsigned num_chains, bool is_use)
1819 : {
1820 757 : gcc_assert (is_empty ());
1821 :
1822 757 : if (num_chains == 0)
1823 : return;
1824 :
1825 687 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1826 6 : fprintf (dump_file, "init_from_control_deps [%s] {%s}:\n",
1827 : is_use ? "USE" : "DEF",
1828 8 : format_edge_vecs (dep_chains, num_chains).c_str ());
1829 :
1830 : /* Convert the control dependency chain into a set of predicates. */
1831 687 : m_preds.reserve (num_chains);
1832 :
1833 1477 : for (unsigned i = 0; i < num_chains; i++)
1834 : {
1835 : /* One path through the CFG represents a logical conjunction
1836 : of the predicates. */
1837 948 : const vec<edge> &path = dep_chains[i];
1838 :
1839 948 : bool has_valid_pred = false;
1840 : /* The chain of predicates guarding the definition along this path. */
1841 948 : pred_chain t_chain{ };
1842 4013 : for (unsigned j = 0; j < path.length (); j++)
1843 : {
1844 3069 : edge e = path[j];
1845 3069 : basic_block guard_bb = e->src;
1846 :
1847 6138 : gcc_assert (!empty_block_p (guard_bb) && !single_succ_p (guard_bb));
1848 :
1849 : /* Skip this edge if it is bypassing an abort - when the
1850 : condition is not satisfied we are neither reaching the
1851 : definition nor the use so it isn't meaningful. Note if
1852 : we are processing the use predicate the condition is
1853 : meaningful. See PR65244. */
1854 3069 : if (!is_use && EDGE_COUNT (e->src->succs) == 2)
1855 : {
1856 1172 : edge e1;
1857 1172 : edge_iterator ei1;
1858 1172 : bool skip = false;
1859 :
1860 3514 : FOR_EACH_EDGE (e1, ei1, e->src->succs)
1861 : {
1862 2343 : if (EDGE_COUNT (e1->dest->succs) == 0)
1863 : {
1864 : skip = true;
1865 : break;
1866 : }
1867 : }
1868 1172 : if (skip)
1869 : {
1870 1 : has_valid_pred = true;
1871 1 : continue;
1872 : }
1873 : }
1874 : /* Get the conditional controlling the bb exit edge. */
1875 3068 : gimple *cond_stmt = *gsi_last_bb (guard_bb);
1876 3068 : if (gimple_code (cond_stmt) == GIMPLE_COND)
1877 : {
1878 : /* The true edge corresponds to the uninteresting condition.
1879 : Add the negated predicate(s) for the edge to record
1880 : the interesting condition. */
1881 3028 : pred_info one_pred = get_pred_info_from_cond_edge (e);
1882 :
1883 3028 : t_chain.safe_push (one_pred);
1884 :
1885 3028 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1886 : {
1887 6 : fprintf (dump_file, "%d -> %d: one_pred = ",
1888 6 : e->src->index, e->dest->index);
1889 6 : dump_pred_info (dump_file, one_pred);
1890 6 : fputc ('\n', dump_file);
1891 : }
1892 :
1893 3028 : has_valid_pred = true;
1894 : }
1895 40 : else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
1896 : {
1897 : /* Find the case label, but avoid quadratic behavior. */
1898 23 : tree l = get_cases_for_edge (e, gs);
1899 : /* If more than one label reaches this block or the case
1900 : label doesn't have a contiguous range of values (like the
1901 : default one) fail. */
1902 46 : if (!l || CASE_CHAIN (l) || !CASE_LOW (l))
1903 : has_valid_pred = false;
1904 22 : else if (!CASE_HIGH (l)
1905 22 : || operand_equal_p (CASE_LOW (l), CASE_HIGH (l)))
1906 : {
1907 22 : pred_info one_pred;
1908 22 : one_pred.pred_lhs = gimple_switch_index (gs);
1909 22 : one_pred.pred_rhs = CASE_LOW (l);
1910 22 : one_pred.cond_code = EQ_EXPR;
1911 22 : one_pred.invert = false;
1912 22 : t_chain.safe_push (one_pred);
1913 22 : has_valid_pred = true;
1914 : }
1915 : else
1916 : {
1917 : /* Support a case label with a range with
1918 : two predicates. We're overcommitting on
1919 : the MAX_CHAIN_LEN budget by at most a factor
1920 : of two here. */
1921 0 : pred_info one_pred;
1922 0 : one_pred.pred_lhs = gimple_switch_index (gs);
1923 0 : one_pred.pred_rhs = CASE_LOW (l);
1924 0 : one_pred.cond_code = GE_EXPR;
1925 0 : one_pred.invert = false;
1926 0 : t_chain.safe_push (one_pred);
1927 0 : one_pred.pred_rhs = CASE_HIGH (l);
1928 0 : one_pred.cond_code = LE_EXPR;
1929 0 : t_chain.safe_push (one_pred);
1930 0 : has_valid_pred = true;
1931 : }
1932 : }
1933 17 : else if (stmt_can_throw_internal (cfun, cond_stmt)
1934 17 : && !(e->flags & EDGE_EH))
1935 : /* Ignore the exceptional control flow and proceed as if
1936 : E were a fallthru without a controlling predicate for
1937 : both the USE (valid) and DEF (questionable) case. */
1938 : has_valid_pred = true;
1939 : else
1940 : has_valid_pred = false;
1941 :
1942 : /* For USE predicates we can drop components of the
1943 : AND chain. */
1944 3065 : if (!has_valid_pred && !is_use)
1945 : break;
1946 : }
1947 :
1948 : /* For DEF predicates we have to drop components of the OR chain
1949 : on failure. */
1950 948 : if (!has_valid_pred && !is_use)
1951 : {
1952 4 : t_chain.release ();
1953 4 : continue;
1954 : }
1955 :
1956 : /* When we add || 1 simply prune the chain and return. */
1957 944 : if (t_chain.is_empty ())
1958 : {
1959 158 : t_chain.release ();
1960 474 : for (auto chain : m_preds)
1961 0 : chain.release ();
1962 158 : m_preds.truncate (0);
1963 158 : break;
1964 : }
1965 :
1966 786 : m_preds.quick_push (t_chain);
1967 : }
1968 :
1969 687 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1970 4 : dump (dump_file);
1971 : }
1972 :
1973 : /* Store a PRED in *THIS. */
1974 :
1975 : void
1976 258 : predicate::push_pred (const pred_info &pred)
1977 : {
1978 258 : pred_chain chain = vNULL;
1979 258 : chain.safe_push (pred);
1980 258 : m_preds.safe_push (chain);
1981 258 : }
1982 :
1983 : /* Dump predicates in *THIS to F. */
1984 :
1985 : void
1986 8 : predicate::dump (FILE *f) const
1987 : {
1988 8 : unsigned np = m_preds.length ();
1989 8 : if (np == 0)
1990 : {
1991 0 : fprintf (f, "\tTRUE (empty)\n");
1992 0 : return;
1993 : }
1994 :
1995 16 : for (unsigned i = 0; i < np; i++)
1996 : {
1997 8 : if (i > 0)
1998 0 : fprintf (f, "\tOR (");
1999 : else
2000 8 : fprintf (f, "\t(");
2001 8 : dump_pred_chain (f, m_preds[i]);
2002 8 : fprintf (f, ")\n");
2003 : }
2004 : }
2005 :
2006 : /* Dump predicates in *THIS to stderr. */
2007 :
2008 : void
2009 0 : predicate::debug () const
2010 : {
2011 0 : dump (stderr);
2012 0 : }
2013 :
2014 : /* Dump predicates in *THIS for STMT prepended by MSG to F. */
2015 :
2016 : void
2017 4 : predicate::dump (FILE *f, gimple *stmt, const char *msg) const
2018 : {
2019 4 : fprintf (f, "%s", msg);
2020 4 : if (stmt)
2021 : {
2022 4 : fputc ('\t', f);
2023 4 : print_gimple_stmt (f, stmt, 0);
2024 4 : fprintf (f, " is conditional on:\n");
2025 : }
2026 :
2027 4 : dump (f);
2028 4 : }
2029 :
2030 : /* Initialize USE_PREDS with the predicates of the control dependence chains
2031 : between the basic block DEF_BB that defines a variable of interest and
2032 : USE_BB that uses the variable, respectively. */
2033 :
2034 : bool
2035 569 : uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
2036 : basic_block use_bb)
2037 : {
2038 569 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
2039 2 : fprintf (dump_file, "init_use_preds (def_bb = %u, use_bb = %u)\n",
2040 : def_bb->index, use_bb->index);
2041 :
2042 569 : gcc_assert (use_preds.is_empty ()
2043 : && dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
2044 :
2045 : /* Set CD_ROOT to the basic block closest to USE_BB that is the control
2046 : equivalent of (is guarded by the same predicate as) DEF_BB that also
2047 : dominates USE_BB. This mimics the inner loop in
2048 : compute_control_dep_chain. */
2049 : basic_block cd_root = def_bb;
2050 749 : do
2051 : {
2052 749 : basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, cd_root);
2053 :
2054 : /* Stop at a loop exit which is also postdominating cd_root. */
2055 919 : if (single_pred_p (pdom) && !single_succ_p (cd_root))
2056 : break;
2057 :
2058 1342 : if (!dominated_by_p (CDI_DOMINATORS, pdom, cd_root)
2059 671 : || !dominated_by_p (CDI_DOMINATORS, use_bb, pdom))
2060 : break;
2061 :
2062 : cd_root = pdom;
2063 : }
2064 : while (1);
2065 :
2066 569 : auto_bb_flag in_region (cfun);
2067 569 : auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2068 569 : param_uninit_control_dep_attempts));
2069 :
2070 : /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
2071 : Each DEP_CHAINS element is a series of edges whose conditions
2072 : are logical conjunctions. Together, the DEP_CHAINS vector is
2073 : used below to initialize an OR expression of the conjunctions. */
2074 569 : unsigned num_chains = 0;
2075 5121 : auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2076 :
2077 569 : if (!dfs_mark_dominating_region (use_bb, cd_root, in_region, region)
2078 1138 : || !compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
2079 569 : in_region))
2080 : {
2081 : /* If the info in dep_chains is not complete we need to use a
2082 : conservative approximation for the use predicate. */
2083 0 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
2084 0 : fprintf (dump_file, "init_use_preds: dep_chain incomplete, using "
2085 : "conservative approximation\n");
2086 0 : num_chains = 1;
2087 0 : dep_chains[0].truncate (0);
2088 0 : simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
2089 : }
2090 :
2091 : /* Unmark the region. */
2092 3668 : for (auto bb : region)
2093 1961 : bb->flags &= ~in_region;
2094 :
2095 : /* From the set of edges computed above initialize *THIS as the OR
2096 : condition under which the definition in DEF_BB is used in USE_BB.
2097 : Each OR subexpression is represented by one element of DEP_CHAINS,
2098 : where each element consists of a series of AND subexpressions. */
2099 569 : use_preds.init_from_control_deps (dep_chains, num_chains, true);
2100 5690 : delete[] dep_chains;
2101 1138 : return !use_preds.is_empty ();
2102 569 : }
2103 :
2104 : /* Release resources in *THIS. */
2105 :
2106 2007 : predicate::~predicate ()
2107 : {
2108 2007 : unsigned n = m_preds.length ();
2109 3835 : for (unsigned i = 0; i != n; ++i)
2110 1828 : m_preds[i].release ();
2111 2007 : m_preds.release ();
2112 2007 : }
2113 :
2114 : /* Copy-assign RHS to *THIS. */
2115 :
2116 : predicate&
2117 677 : predicate::operator= (const predicate &rhs)
2118 : {
2119 677 : if (this == &rhs)
2120 : return *this;
2121 :
2122 677 : m_cval = rhs.m_cval;
2123 :
2124 677 : unsigned n = m_preds.length ();
2125 1432 : for (unsigned i = 0; i != n; ++i)
2126 755 : m_preds[i].release ();
2127 677 : m_preds.release ();
2128 :
2129 677 : n = rhs.m_preds.length ();
2130 1746 : for (unsigned i = 0; i != n; ++i)
2131 : {
2132 1069 : const pred_chain &chain = rhs.m_preds[i];
2133 1069 : m_preds.safe_push (chain.copy ());
2134 : }
2135 :
2136 : return *this;
2137 : }
2138 :
2139 : /* For each use edge of PHI, compute all control dependence chains
2140 : and convert those to the composite predicates in M_PREDS.
2141 : Return true if a nonempty predicate has been obtained. */
2142 :
2143 : bool
2144 188 : uninit_analysis::init_from_phi_def (gphi *phi)
2145 : {
2146 188 : gcc_assert (m_phi_def_preds.is_empty ());
2147 :
2148 188 : basic_block phi_bb = gimple_bb (phi);
2149 : /* Find the closest dominating bb to be the control dependence root. */
2150 188 : basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
2151 188 : if (!cd_root)
2152 : return false;
2153 :
2154 : /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
2155 : definitions of each of the PHI operands for which M_EVAL is false. */
2156 188 : auto_vec<edge> def_edges;
2157 188 : hash_set<gimple *> visited_phis;
2158 188 : collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
2159 :
2160 376 : unsigned nedges = def_edges.length ();
2161 188 : if (nedges == 0)
2162 : return false;
2163 :
2164 188 : auto_bb_flag in_region (cfun);
2165 188 : auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2166 188 : param_uninit_control_dep_attempts));
2167 : /* Pre-mark the PHI incoming edges PHI block to make sure we only walk
2168 : interesting edges from there. */
2169 441 : for (unsigned i = 0; i < nedges; i++)
2170 : {
2171 253 : if (!(def_edges[i]->dest->flags & in_region))
2172 : {
2173 219 : if (!region.space (1))
2174 : break;
2175 219 : def_edges[i]->dest->flags |= in_region;
2176 219 : region.quick_push (def_edges[i]->dest);
2177 : }
2178 : }
2179 441 : for (unsigned i = 0; i < nedges; i++)
2180 253 : if (!dfs_mark_dominating_region (def_edges[i]->src, cd_root,
2181 : in_region, region))
2182 : break;
2183 :
2184 188 : unsigned num_chains = 0;
2185 1692 : auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2186 441 : for (unsigned i = 0; i < nedges; i++)
2187 : {
2188 253 : edge e = def_edges[i];
2189 253 : unsigned prev_nc = num_chains;
2190 253 : bool complete_p = compute_control_dep_chain (cd_root, e->src, dep_chains,
2191 253 : &num_chains, in_region);
2192 :
2193 : /* Update the newly added chains with the phi operand edge. */
2194 253 : if (EDGE_COUNT (e->src->succs) > 1)
2195 : {
2196 0 : if (complete_p
2197 0 : && prev_nc == num_chains
2198 0 : && num_chains < MAX_NUM_CHAINS)
2199 : /* We can only add a chain for the PHI operand edge when the
2200 : collected info was complete, otherwise the predicate may
2201 : not be conservative. */
2202 0 : dep_chains[num_chains++] = vNULL;
2203 0 : for (unsigned j = prev_nc; j < num_chains; j++)
2204 0 : dep_chains[j].safe_push (e);
2205 : }
2206 : }
2207 :
2208 : /* Unmark the region. */
2209 4697 : for (auto bb : region)
2210 4133 : bb->flags &= ~in_region;
2211 :
2212 : /* Convert control dependence chains to the predicate in *THIS under
2213 : which the PHI operands are defined to values for which M_EVAL is
2214 : false. */
2215 188 : m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, false);
2216 1880 : delete[] dep_chains;
2217 376 : return !m_phi_def_preds.is_empty ();
2218 376 : }
2219 :
2220 : /* Compute the predicates that guard the use USE_STMT and check if
2221 : the incoming paths that have an empty (or possibly empty) definition
2222 : can be pruned. Return true if it can be determined that the use of
2223 : PHI's def in USE_STMT is guarded by a predicate set that does not
2224 : overlap with the predicate sets of all runtime paths that do not
2225 : have a definition.
2226 :
2227 : Return false if the use is not guarded or if it cannot be determined.
2228 : USE_BB is the bb of the use (for phi operand use, the bb is not the bb
2229 : of the phi stmt, but the source bb of the operand edge).
2230 :
2231 : OPNDS is a bitmap with a bit set for each PHI operand of interest.
2232 :
2233 : THIS->M_PREDS contains the (memoized) defining predicate chains of
2234 : a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate
2235 : chains are computed and stored into THIS->M_PREDS as needed.
2236 :
2237 : VISITED_PHIS is a pointer set of phis being visited. */
2238 :
2239 : bool
2240 588 : uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
2241 : gphi *phi, unsigned opnds,
2242 : hash_set<gphi *> *visited)
2243 : {
2244 588 : if (visited->add (phi))
2245 : return false;
2246 :
2247 : /* The basic block where the PHI is defined. */
2248 569 : basic_block def_bb = gimple_bb (phi);
2249 :
2250 : /* Try to build the predicate expression under which the PHI flows
2251 : into its use. This will be empty if the PHI is defined and used
2252 : in the same bb. */
2253 569 : predicate use_preds (true);
2254 569 : if (!init_use_preds (use_preds, def_bb, use_bb))
2255 : return false;
2256 :
2257 410 : use_preds.simplify (use_stmt, /*is_use=*/true);
2258 410 : use_preds.normalize (use_stmt, /*is_use=*/true);
2259 565 : if (use_preds.is_false ())
2260 : return true;
2261 410 : if (use_preds.is_true ())
2262 : return false;
2263 :
2264 : /* Try to prune the dead incoming phi edges. */
2265 409 : if (!overlap (phi, opnds, visited, use_preds))
2266 : {
2267 113 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
2268 0 : fputs ("found predicate overlap\n", dump_file);
2269 :
2270 113 : return true;
2271 : }
2272 :
2273 296 : if (m_phi_def_preds.is_empty ())
2274 : {
2275 : /* Lazily initialize *THIS from PHI. */
2276 188 : if (!init_from_phi_def (phi))
2277 : return false;
2278 :
2279 116 : m_phi_def_preds.simplify (phi);
2280 116 : m_phi_def_preds.normalize (phi);
2281 348 : if (m_phi_def_preds.is_false ())
2282 : return false;
2283 116 : if (m_phi_def_preds.is_true ())
2284 : return true;
2285 : }
2286 :
2287 : /* Return true if the predicate guarding the valid definition (i.e.,
2288 : *THIS) is a superset of the predicate guarding the use (i.e.,
2289 : USE_PREDS). */
2290 224 : if (m_phi_def_preds.superset_of (use_preds))
2291 : return true;
2292 :
2293 : /* The superset test fails when a guard that distinguishes the defined from
2294 : the undefined value sits on the PHI's maybe-undef incoming edge rather
2295 : than on the use's control-dependence chain -- e.g. after ifcombine merges
2296 : the conditions guarding the definition. A conjunct of the definition
2297 : predicate that is implied by the incoming-edge condition of every
2298 : maybe-undef operand cannot make the use unsafe: when that conjunct is
2299 : false the maybe-undef edge is not taken either, so no undefined value
2300 : reaches the PHI. Drop such conjuncts from a copy of the definition
2301 : predicate and retry; bail unless every maybe-undef operand arrives on a
2302 : simple conditional edge. */
2303 182 : auto_vec<pred_info, 4> edge_conds;
2304 182 : unsigned nargs = gimple_phi_num_args (phi);
2305 677 : for (unsigned i = 0; i < nargs && i < m_eval.max_phi_args; i++)
2306 : {
2307 526 : if (!MASK_TEST_BIT (opnds, i))
2308 112 : continue;
2309 414 : edge e = gimple_phi_arg_edge (phi, i);
2310 : /* Walk up through forwarder blocks to the controlling conditional; a
2311 : single-predecessor forwarder preserves the implication. */
2312 802 : while (single_pred_p (e->src) && single_succ_p (e->src))
2313 388 : e = single_pred_edge (e->src);
2314 414 : if (EDGE_COUNT (e->src->succs) != 2
2315 797 : || !safe_dyn_cast <gcond *> (*gsi_last_bb (e->src)))
2316 : {
2317 31 : edge_conds.truncate (0);
2318 31 : break;
2319 : }
2320 383 : edge_conds.safe_push (get_pred_info_from_cond_edge (e));
2321 : }
2322 :
2323 364 : if (!edge_conds.is_empty ())
2324 : {
2325 151 : predicate relaxed (m_phi_def_preds);
2326 151 : if (relaxed.drop_conjuncts_implied_by (edge_conds)
2327 151 : && relaxed.superset_of (use_preds))
2328 2 : return true;
2329 151 : }
2330 :
2331 : return false;
2332 569 : }
2333 :
2334 : /* Public interface to the above. */
2335 :
2336 : bool
2337 548 : uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
2338 : unsigned opnds)
2339 : {
2340 548 : hash_set<gphi *> visited;
2341 548 : return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
2342 548 : }
2343 :
|
