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 550 : pred_neg_p (const pred_info &x1, const pred_info &x2)
60 : {
61 550 : if (!operand_equal_p (x1.pred_lhs, x2.pred_lhs, 0)
62 550 : || !operand_equal_p (x1.pred_rhs, x2.pred_rhs, 0))
63 454 : 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 634 : is_value_included_in (tree val, tree boundary, tree_code cmpc)
78 : {
79 : /* Only handle integer constant here. */
80 634 : if (TREE_CODE (val) != INTEGER_CST || TREE_CODE (boundary) != INTEGER_CST)
81 : return true;
82 :
83 634 : bool inverted = false;
84 634 : if (cmpc == GE_EXPR || cmpc == GT_EXPR || cmpc == NE_EXPR)
85 : {
86 566 : cmpc = invert_tree_comparison (cmpc, false);
87 566 : inverted = true;
88 : }
89 :
90 634 : bool result;
91 634 : if (cmpc == EQ_EXPR)
92 609 : result = tree_int_cst_equal (val, boundary);
93 25 : else if (cmpc == LT_EXPR)
94 14 : result = tree_int_cst_lt (val, boundary);
95 : else
96 : {
97 11 : gcc_assert (cmpc == LE_EXPR);
98 11 : result = tree_int_cst_le (val, boundary);
99 : }
100 :
101 634 : if (inverted)
102 566 : 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 967 : get_cmp_code (tree_code orig_cmp_code, bool swap_cond, bool invert)
182 : {
183 967 : tree_code tc = orig_cmp_code;
184 :
185 967 : if (swap_cond)
186 107 : tc = swap_tree_comparison (orig_cmp_code);
187 967 : if (invert)
188 339 : tc = invert_tree_comparison (tc, false);
189 :
190 967 : switch (tc)
191 : {
192 950 : case LT_EXPR:
193 950 : case LE_EXPR:
194 950 : case GT_EXPR:
195 950 : case GE_EXPR:
196 950 : case EQ_EXPR:
197 950 : case NE_EXPR:
198 950 : break;
199 : default:
200 : return ERROR_MARK;
201 : }
202 950 : 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 : /* Trival 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 defintion
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 457 : find_var_cmp_const (pred_chain_union preds, gphi *phi, gimple **flag_def,
253 : tree *boundary_cst, unsigned &i)
254 : {
255 457 : gcc_assert (preds.length () > 0);
256 457 : pred_chain chain = preds[0];
257 1154 : for (; i < chain.length (); i++)
258 : {
259 860 : const pred_info &pred = chain[i];
260 860 : tree cond_lhs = pred.pred_lhs;
261 860 : tree cond_rhs = pred.pred_rhs;
262 860 : if (cond_lhs == NULL_TREE || cond_rhs == NULL_TREE)
263 697 : continue;
264 :
265 860 : tree_code code = get_cmp_code (pred.cond_code, false, pred.invert);
266 860 : if (code == ERROR_MARK)
267 17 : continue;
268 :
269 : /* Convert to the canonical form SSA_NAME CMP CONSTANT. */
270 843 : if (TREE_CODE (cond_lhs) == SSA_NAME
271 843 : && 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 741 : if ((*flag_def = SSA_NAME_DEF_STMT (cond_lhs)) == NULL)
335 0 : continue;
336 :
337 741 : if (gimple_code (*flag_def) != GIMPLE_PHI
338 164 : || gimple_bb (*flag_def) != gimple_bb (phi)
339 904 : || !find_matching_predicate_in_rest_chains (pred, preds))
340 578 : 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 283 : uninit_analysis::collect_phi_def_edges (gphi *phi, basic_block cd_root,
485 : vec<edge> *edges,
486 : hash_set<gimple *> *visited)
487 : {
488 283 : if (visited->elements () == 0
489 : && DEBUG_PREDICATE_ANALYZER
490 283 : && 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 283 : if (visited->add (phi))
499 : return;
500 :
501 247 : unsigned n = gimple_phi_num_args (phi);
502 247 : unsigned opnds_arg_phi = m_eval.phi_arg_set (phi);
503 877 : for (unsigned i = 0; i < n; i++)
504 : {
505 630 : if (!MASK_TEST_BIT (opnds_arg_phi, i))
506 : {
507 : /* Add the edge for a not maybe-undefined edge value. */
508 254 : edge opnd_edge = gimple_phi_arg_edge (phi, i);
509 254 : 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 254 : edges->safe_push (opnd_edge);
519 254 : continue;
520 254 : }
521 : else
522 : {
523 376 : tree opnd = gimple_phi_arg_def (phi, i);
524 376 : if (TREE_CODE (opnd) == SSA_NAME)
525 : {
526 376 : gimple *def = SSA_NAME_DEF_STMT (opnd);
527 376 : if (gimple_code (def) == GIMPLE_PHI
528 376 : && 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 senario 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 407 : uninit_analysis::overlap (gphi *phi, unsigned opnds, hash_set<gphi *> *visited,
625 : const predicate &use_preds)
626 : {
627 407 : gimple *flag_def = NULL;
628 407 : 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 407 : unsigned i = 0;
634 407 : tree_code cmp_code;
635 457 : while ((cmp_code = find_var_cmp_const (use_preds.chain (), phi, &flag_def,
636 457 : &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 1488 : pred_equal_p (const pred_info &pred1, const pred_info &pred2)
660 : {
661 1488 : if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0)
662 1488 : || !operand_equal_p (pred1.pred_rhs, pred2.pred_rhs, 0))
663 1012 : return false;
664 :
665 476 : tree_code c1 = pred1.cond_code, c2;
666 476 : if (pred1.invert != pred2.invert
667 97 : && TREE_CODE_CLASS (pred2.cond_code) == tcc_comparison)
668 96 : c2 = invert_tree_comparison (pred2.cond_code, false);
669 : else
670 380 : c2 = pred2.cond_code;
671 :
672 476 : return c1 == c2;
673 : }
674 :
675 : /* Return true if PRED tests inequality (i.e., X != Y). */
676 :
677 : static inline bool
678 5895 : is_neq_relop_p (const pred_info &pred)
679 : {
680 :
681 2343 : return ((pred.cond_code == NE_EXPR && !pred.invert)
682 4136 : || (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 5895 : is_neq_zero_form_p (const pred_info &pred)
689 : {
690 9207 : if (!is_neq_relop_p (pred) || !integer_zerop (pred.pred_rhs)
691 5794 : || TREE_CODE (pred.pred_lhs) != SSA_NAME)
692 3255 : 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 23 : value_sat_pred_p (tree val, tree boundary, tree_code cmpc,
715 : bool exact_p = false)
716 : {
717 23 : if (cmpc != BIT_AND_EXPR)
718 16 : 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 919 : subset_of (const pred_info &pred1, const pred_info &pred2)
732 : {
733 919 : if (pred_equal_p (pred1, pred2))
734 : return true;
735 :
736 871 : if ((TREE_CODE (pred1.pred_rhs) != INTEGER_CST)
737 710 : || (TREE_CODE (pred2.pred_rhs) != INTEGER_CST))
738 : return false;
739 :
740 697 : if (!operand_equal_p (pred1.pred_lhs, pred2.pred_lhs, 0))
741 : return false;
742 :
743 34 : tree_code code1 = pred1.cond_code;
744 34 : if (pred1.invert)
745 2 : code1 = invert_tree_comparison (code1, false);
746 34 : tree_code code2 = pred2.cond_code;
747 34 : if (pred2.invert)
748 7 : code2 = invert_tree_comparison (code2, false);
749 :
750 34 : if (code2 == NE_EXPR && code1 == NE_EXPR)
751 : return false;
752 :
753 31 : if (code2 == NE_EXPR)
754 10 : return !value_sat_pred_p (pred2.pred_rhs, pred1.pred_rhs, code1);
755 :
756 21 : if (code1 == EQ_EXPR)
757 2 : return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2);
758 :
759 19 : if (code1 == code2)
760 11 : return value_sat_pred_p (pred1.pred_rhs, pred2.pred_rhs, code2,
761 11 : 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 463 : subset_of (const pred_chain &chain1, const pred_chain &chain2)
771 : {
772 463 : unsigned np1 = chain1.length ();
773 463 : unsigned np2 = chain2.length ();
774 523 : for (unsigned i2 = 0; i2 < np2; i2++)
775 : {
776 479 : bool found = false;
777 479 : const pred_info &info2 = chain2[i2];
778 1338 : for (unsigned i1 = 0; i1 < np1; i1++)
779 : {
780 919 : const pred_info &info1 = chain1[i1];
781 919 : if (subset_of (info1, info2))
782 : {
783 : found = true;
784 : break;
785 : }
786 : }
787 479 : 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 227 : predicate::includes (const pred_chain &chain) const
802 : {
803 646 : for (unsigned i = 0; i < m_preds.length (); i++)
804 463 : 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 222 : predicate::superset_of (const predicate &preds) const
821 : {
822 266 : for (unsigned i = 0; i < preds.m_preds.length (); i++)
823 227 : if (!includes (preds.m_preds[i]))
824 : return false;
825 :
826 : return true;
827 : }
828 :
829 : /* Create a predicate of the form OP != 0 and push it the work list CHAIN. */
830 :
831 : static void
832 56 : push_to_worklist (tree op, pred_chain *chain, hash_set<tree> *mark_set)
833 : {
834 56 : if (mark_set->contains (op))
835 2 : return;
836 54 : mark_set->add (op);
837 :
838 54 : pred_info arg_pred;
839 54 : arg_pred.pred_lhs = op;
840 54 : arg_pred.pred_rhs = integer_zero_node;
841 54 : arg_pred.cond_code = NE_EXPR;
842 54 : arg_pred.invert = false;
843 54 : chain->safe_push (arg_pred);
844 : }
845 :
846 : /* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
847 : rhs. */
848 :
849 : static pred_info
850 36 : get_pred_info_from_cmp (const gimple *cmp_assign)
851 : {
852 36 : pred_info pred;
853 36 : pred.pred_lhs = gimple_assign_rhs1 (cmp_assign);
854 36 : pred.pred_rhs = gimple_assign_rhs2 (cmp_assign);
855 36 : pred.cond_code = gimple_assign_rhs_code (cmp_assign);
856 36 : pred.invert = false;
857 36 : return pred;
858 : }
859 :
860 : /* If PHI is a degenerate phi with all operands having the same value (relop)
861 : update *PRED to that value and return true. Otherwise return false. */
862 :
863 : static bool
864 65 : is_degenerate_phi (gimple *phi, pred_info *pred)
865 : {
866 65 : tree op0 = gimple_phi_arg_def (phi, 0);
867 :
868 65 : if (TREE_CODE (op0) != SSA_NAME)
869 : return false;
870 :
871 34 : gimple *def0 = SSA_NAME_DEF_STMT (op0);
872 34 : if (gimple_code (def0) != GIMPLE_ASSIGN)
873 : return false;
874 :
875 1 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0)) != tcc_comparison)
876 : return false;
877 :
878 1 : pred_info pred0 = get_pred_info_from_cmp (def0);
879 :
880 1 : unsigned n = gimple_phi_num_args (phi);
881 1 : for (unsigned i = 1; i < n; ++i)
882 : {
883 1 : tree op = gimple_phi_arg_def (phi, i);
884 1 : if (TREE_CODE (op) != SSA_NAME)
885 1 : return false;
886 :
887 0 : gimple *def = SSA_NAME_DEF_STMT (op);
888 0 : if (gimple_code (def) != GIMPLE_ASSIGN)
889 : return false;
890 :
891 0 : if (TREE_CODE_CLASS (gimple_assign_rhs_code (def)) != tcc_comparison)
892 : return false;
893 :
894 0 : pred_info pred = get_pred_info_from_cmp (def);
895 0 : if (!pred_equal_p (pred, pred0))
896 : return false;
897 : }
898 :
899 0 : *pred = pred0;
900 0 : return true;
901 : }
902 :
903 : /* If compute_control_dep_chain bailed out due to limits this routine
904 : tries to build a partial sparse path using dominators. Returns
905 : path edges whose predicates are always true when reaching E. */
906 :
907 : static void
908 0 : simple_control_dep_chain (vec<edge>& chain, basic_block from, basic_block to)
909 : {
910 0 : if (!dominated_by_p (CDI_DOMINATORS, to, from))
911 : return;
912 :
913 : basic_block src = to;
914 : while (src != from
915 0 : && chain.length () <= MAX_CHAIN_LEN)
916 : {
917 0 : basic_block dest = src;
918 0 : src = get_immediate_dominator (CDI_DOMINATORS, src);
919 0 : if (single_pred_p (dest))
920 : {
921 0 : edge pred_e = single_pred_edge (dest);
922 0 : gcc_assert (pred_e->src == src);
923 0 : if (!(pred_e->flags & ((EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK)))
924 0 : && !single_succ_p (src))
925 0 : chain.safe_push (pred_e);
926 : }
927 : }
928 : }
929 :
930 : /* Perform a DFS walk on predecessor edges to mark the region denoted
931 : by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
932 : Blocks in the region are marked with FLAG and added to BBS. BBS is
933 : filled up to its capacity only after which the walk is terminated
934 : and false is returned. If the whole region was marked, true is returned. */
935 :
936 : static bool
937 823 : dfs_mark_dominating_region (basic_block exit_src, basic_block dom, int flag,
938 : vec<basic_block> &bbs)
939 : {
940 823 : if (exit_src == dom || exit_src->flags & flag)
941 : return true;
942 668 : if (!bbs.space (1))
943 : return false;
944 668 : bbs.quick_push (exit_src);
945 668 : exit_src->flags |= flag;
946 668 : auto_vec<edge_iterator, 20> stack (bbs.allocated () - bbs.length () + 1);
947 668 : stack.quick_push (ei_start (exit_src->preds));
948 12676 : while (!stack.is_empty ())
949 : {
950 : /* Look at the edge on the top of the stack. */
951 12008 : edge_iterator ei = stack.last ();
952 12008 : basic_block src = ei_edge (ei)->src;
953 :
954 : /* Check if the edge source has been visited yet. */
955 12008 : if (!(src->flags & flag))
956 : {
957 : /* Mark the source if there's still space. If not, return early. */
958 5208 : if (!bbs.space (1))
959 0 : return false;
960 5208 : src->flags |= flag;
961 5208 : bbs.quick_push (src);
962 :
963 : /* Queue its predecessors if we didn't reach DOM. */
964 16700 : if (src != dom && EDGE_COUNT (src->preds) > 0)
965 4692 : stack.quick_push (ei_start (src->preds));
966 : }
967 : else
968 : {
969 6800 : if (!ei_one_before_end_p (ei))
970 1440 : ei_next (&stack.last ());
971 : else
972 5360 : stack.pop ();
973 : }
974 : }
975 : return true;
976 668 : }
977 :
978 : static bool
979 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
980 : vec<edge> cd_chains[], unsigned *num_chains,
981 : vec<edge> &cur_cd_chain, unsigned *num_calls,
982 : unsigned in_region, unsigned depth,
983 : bool *complete_p);
984 :
985 : /* Helper for compute_control_dep_chain that walks the post-dominator
986 : chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB. */
987 :
988 : static bool
989 9537 : compute_control_dep_chain_pdom (basic_block cd_bb, const_basic_block dep_bb,
990 : basic_block target_bb,
991 : vec<edge> cd_chains[], unsigned *num_chains,
992 : vec<edge> &cur_cd_chain, unsigned *num_calls,
993 : unsigned in_region, unsigned depth,
994 : bool *complete_p)
995 : {
996 9537 : bool found_cd_chain = false;
997 15667 : while (cd_bb != target_bb)
998 : {
999 12276 : if (cd_bb == dep_bb)
1000 : {
1001 : /* Found a direct control dependence. */
1002 1061 : if (*num_chains < MAX_NUM_CHAINS)
1003 : {
1004 949 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1005 4 : fprintf (dump_file, "%*s pushing { %s }\n",
1006 8 : depth, "", format_edge_vec (cur_cd_chain).c_str ());
1007 949 : cd_chains[*num_chains] = cur_cd_chain.copy ();
1008 949 : (*num_chains)++;
1009 : }
1010 : found_cd_chain = true;
1011 : /* Check path from next edge. */
1012 : break;
1013 : }
1014 :
1015 : /* If the dominating region has been marked avoid walking outside. */
1016 11215 : if (in_region != 0 && !(cd_bb->flags & in_region))
1017 : break;
1018 :
1019 : /* Count the number of steps we perform to limit compile-time.
1020 : This should cover both recursion and the post-dominator walk. */
1021 8902 : if (*num_calls > (unsigned)param_uninit_control_dep_attempts)
1022 : {
1023 0 : if (dump_file)
1024 0 : fprintf (dump_file, "param_uninit_control_dep_attempts "
1025 : "exceeded: %u\n", *num_calls);
1026 0 : *complete_p = false;
1027 0 : break;
1028 : }
1029 8902 : ++*num_calls;
1030 :
1031 : /* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
1032 8902 : if (!single_succ_p (cd_bb)
1033 8902 : && compute_control_dep_chain (cd_bb, dep_bb, cd_chains,
1034 : num_chains, cur_cd_chain,
1035 : num_calls, in_region, depth + 1,
1036 : complete_p))
1037 : {
1038 : found_cd_chain = true;
1039 : break;
1040 : }
1041 :
1042 : /* The post-dominator walk will reach a backedge only
1043 : from a forwarder, otherwise it should choose to exit
1044 : the SCC. */
1045 6421 : if (single_succ_p (cd_bb)
1046 6421 : && single_succ_edge (cd_bb)->flags & EDGE_DFS_BACK)
1047 : break;
1048 6213 : basic_block prev_cd_bb = cd_bb;
1049 6213 : cd_bb = get_immediate_dominator (CDI_POST_DOMINATORS, cd_bb);
1050 6213 : if (cd_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1051 : break;
1052 : /* Pick up conditions toward the post dominator such like
1053 : loop exit conditions. See gcc.dg/uninit-pred-11.c and
1054 : gcc.dg/unninit-pred-12.c and PR106754. */
1055 12260 : if (single_pred_p (cd_bb))
1056 : {
1057 44 : edge e2 = single_pred_edge (cd_bb);
1058 44 : gcc_assert (e2->src == prev_cd_bb);
1059 : /* But avoid adding fallthru or abnormal edges. */
1060 44 : if (!(e2->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1061 88 : && !single_succ_p (prev_cd_bb))
1062 43 : cur_cd_chain.safe_push (e2);
1063 : }
1064 : }
1065 9537 : return found_cd_chain;
1066 : }
1067 :
1068 :
1069 : /* Recursively compute the control dependence chains (paths of edges)
1070 : from the dependent basic block, DEP_BB, up to the dominating basic
1071 : block, DOM_BB (the head node of a chain should be dominated by it),
1072 : storing them in the CD_CHAINS array.
1073 : CUR_CD_CHAIN is the current chain being computed.
1074 : *NUM_CHAINS is total number of chains in the CD_CHAINS array.
1075 : *NUM_CALLS is the number of recursive calls to control unbounded
1076 : recursion.
1077 : Return true if the information is successfully computed, false if
1078 : there is no control dependence or not computed.
1079 : *COMPLETE_P is set to false if we stopped walking due to limits.
1080 : In this case there might be missing chains. */
1081 :
1082 : static bool
1083 4513 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1084 : vec<edge> cd_chains[], unsigned *num_chains,
1085 : vec<edge> &cur_cd_chain, unsigned *num_calls,
1086 : unsigned in_region, unsigned depth,
1087 : bool *complete_p)
1088 : {
1089 : /* In our recursive calls this doesn't happen. */
1090 4513 : if (single_succ_p (dom_bb))
1091 : return false;
1092 :
1093 : /* FIXME: Use a set instead. */
1094 4513 : unsigned cur_chain_len = cur_cd_chain.length ();
1095 4513 : if (cur_chain_len > MAX_CHAIN_LEN)
1096 : {
1097 204 : if (dump_file)
1098 0 : fprintf (dump_file, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len);
1099 :
1100 204 : *complete_p = false;
1101 204 : return false;
1102 : }
1103 :
1104 4309 : if (cur_chain_len > 5)
1105 : {
1106 2211 : if (dump_file)
1107 0 : fprintf (dump_file, "chain length exceeds 5: %u\n", cur_chain_len);
1108 : }
1109 :
1110 4309 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1111 7 : fprintf (dump_file,
1112 : "%*s%s (dom_bb = %u, dep_bb = %u, ..., "
1113 : "cur_cd_chain = { %s }, ...)\n",
1114 7 : depth, "", __func__, dom_bb->index, dep_bb->index,
1115 14 : format_edge_vec (cur_cd_chain).c_str ());
1116 :
1117 4309 : bool found_cd_chain = false;
1118 :
1119 : /* Iterate over DOM_BB's successors. */
1120 4309 : edge e;
1121 4309 : edge_iterator ei;
1122 13036 : FOR_EACH_EDGE (e, ei, dom_bb->succs)
1123 : {
1124 8727 : if (e->flags & (EDGE_FAKE | EDGE_ABNORMAL | EDGE_DFS_BACK))
1125 13 : continue;
1126 :
1127 8714 : basic_block cd_bb = e->dest;
1128 8714 : unsigned pop_mark = cur_cd_chain.length ();
1129 8714 : cur_cd_chain.safe_push (e);
1130 8714 : basic_block target_bb
1131 8714 : = get_immediate_dominator (CDI_POST_DOMINATORS, dom_bb);
1132 : /* Walk the post-dominator chain up to the CFG merge. */
1133 8714 : found_cd_chain
1134 8714 : |= compute_control_dep_chain_pdom (cd_bb, dep_bb, target_bb,
1135 : cd_chains, num_chains,
1136 : cur_cd_chain, num_calls,
1137 : in_region, depth, complete_p);
1138 8714 : cur_cd_chain.truncate (pop_mark);
1139 17428 : gcc_assert (cur_cd_chain.length () == cur_chain_len);
1140 : }
1141 :
1142 8618 : gcc_assert (cur_cd_chain.length () == cur_chain_len);
1143 : return found_cd_chain;
1144 : }
1145 :
1146 : /* Wrapper around the compute_control_dep_chain worker above. Returns
1147 : true when the collected set of chains in CD_CHAINS is complete. */
1148 :
1149 : static bool
1150 823 : compute_control_dep_chain (basic_block dom_bb, const_basic_block dep_bb,
1151 : vec<edge> cd_chains[], unsigned *num_chains,
1152 : unsigned in_region = 0)
1153 : {
1154 823 : auto_vec<edge, 10> cur_cd_chain;
1155 823 : unsigned num_calls = 0;
1156 823 : unsigned depth = 0;
1157 823 : bool complete_p = true;
1158 : /* Walk the post-dominator chain. */
1159 823 : cur_cd_chain.reserve (MAX_CHAIN_LEN + 1);
1160 823 : compute_control_dep_chain_pdom (dom_bb, dep_bb, NULL, cd_chains,
1161 : num_chains, cur_cd_chain, &num_calls,
1162 : in_region, depth, &complete_p);
1163 823 : return complete_p;
1164 823 : }
1165 :
1166 : /* Implemented simplifications:
1167 :
1168 : 1a) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1169 : 1b) [!](X rel y) AND [!](X rel y') where y == y' or both constant
1170 : can possibly be simplified
1171 : 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1172 : 3) X OR (!X AND Y) is equivalent to (X OR Y);
1173 : 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1174 : (x != 0 AND y != 0)
1175 : 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1176 : (X AND Y) OR Z
1177 :
1178 : PREDS is the predicate chains, and N is the number of chains. */
1179 :
1180 : /* Implement rule 1a above. PREDS is the AND predicate to simplify
1181 : in place. */
1182 :
1183 : static void
1184 785 : simplify_1a (pred_chain &chain)
1185 : {
1186 785 : bool simplified = false;
1187 785 : pred_chain s_chain = vNULL;
1188 :
1189 785 : unsigned n = chain.length ();
1190 3845 : for (unsigned i = 0; i < n; i++)
1191 : {
1192 3060 : pred_info &a_pred = chain[i];
1193 :
1194 4769 : if (!a_pred.pred_lhs
1195 3060 : || !is_neq_zero_form_p (a_pred))
1196 1709 : continue;
1197 :
1198 1351 : gimple *def_stmt = SSA_NAME_DEF_STMT (a_pred.pred_lhs);
1199 1351 : if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1200 344 : continue;
1201 :
1202 1007 : if (gimple_assign_rhs_code (def_stmt) != BIT_IOR_EXPR)
1203 1000 : continue;
1204 :
1205 19 : for (unsigned j = 0; j < n; j++)
1206 : {
1207 12 : const pred_info &b_pred = chain[j];
1208 :
1209 15 : if (!b_pred.pred_lhs
1210 12 : || !is_neq_zero_form_p (b_pred))
1211 3 : continue;
1212 :
1213 9 : if (pred_expr_equal_p (b_pred, gimple_assign_rhs1 (def_stmt))
1214 9 : || pred_expr_equal_p (b_pred, gimple_assign_rhs2 (def_stmt)))
1215 : {
1216 : /* Mark A_PRED for removal from PREDS. */
1217 0 : a_pred.pred_lhs = NULL;
1218 0 : a_pred.pred_rhs = NULL;
1219 0 : simplified = true;
1220 0 : break;
1221 : }
1222 : }
1223 : }
1224 :
1225 785 : if (!simplified)
1226 785 : return;
1227 :
1228 : /* Remove predicates marked above. */
1229 0 : for (unsigned i = 0; i < n; i++)
1230 : {
1231 0 : pred_info &a_pred = chain[i];
1232 0 : if (!a_pred.pred_lhs)
1233 0 : continue;
1234 0 : s_chain.safe_push (a_pred);
1235 : }
1236 :
1237 0 : chain.release ();
1238 0 : chain = s_chain;
1239 : }
1240 :
1241 : /* Implement rule 1b above. PREDS is the AND predicate to simplify
1242 : in place. Returns true if CHAIN simplifies to true or false. */
1243 :
1244 : static bool
1245 785 : simplify_1b (pred_chain &chain)
1246 : {
1247 3642 : for (unsigned i = 0; i < chain.length (); i++)
1248 : {
1249 2861 : pred_info &a_pred = chain[i];
1250 :
1251 10631 : for (unsigned j = i + 1; j < chain.length (); ++j)
1252 : {
1253 7774 : pred_info &b_pred = chain[j];
1254 :
1255 7774 : if (!operand_equal_p (a_pred.pred_lhs, b_pred.pred_lhs)
1256 7774 : || (!operand_equal_p (a_pred.pred_rhs, b_pred.pred_rhs)
1257 218 : && !(CONSTANT_CLASS_P (a_pred.pred_rhs)
1258 214 : && CONSTANT_CLASS_P (b_pred.pred_rhs))))
1259 7565 : continue;
1260 :
1261 209 : tree_code a_code = a_pred.cond_code;
1262 209 : if (a_pred.invert)
1263 199 : a_code = invert_tree_comparison (a_code, false);
1264 209 : tree_code b_code = b_pred.cond_code;
1265 209 : if (b_pred.invert)
1266 37 : b_code = invert_tree_comparison (b_code, false);
1267 : /* Try to combine X a_code Y && X b_code Y'. */
1268 209 : tree comb = maybe_fold_and_comparisons (boolean_type_node,
1269 : a_code,
1270 : a_pred.pred_lhs,
1271 : a_pred.pred_rhs,
1272 : b_code,
1273 : b_pred.pred_lhs,
1274 : b_pred.pred_rhs, NULL);
1275 209 : if (!comb)
1276 : ;
1277 179 : else if (integer_zerop (comb))
1278 : return true;
1279 175 : else if (integer_truep (comb))
1280 : {
1281 0 : chain.ordered_remove (j);
1282 0 : chain.ordered_remove (i);
1283 4 : if (chain.is_empty ())
1284 : return true;
1285 0 : i--;
1286 0 : break;
1287 : }
1288 175 : else if (COMPARISON_CLASS_P (comb)
1289 175 : && operand_equal_p (a_pred.pred_lhs, TREE_OPERAND (comb, 0)))
1290 : {
1291 175 : chain.ordered_remove (j);
1292 175 : a_pred.cond_code = TREE_CODE (comb);
1293 175 : a_pred.pred_rhs = TREE_OPERAND (comb, 1);
1294 175 : a_pred.invert = false;
1295 175 : j--;
1296 : }
1297 : }
1298 : }
1299 :
1300 : return false;
1301 : }
1302 :
1303 : /* Implements rule 2 for the OR predicate PREDS:
1304 :
1305 : 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1306 :
1307 : bool
1308 123 : predicate::simplify_2 ()
1309 : {
1310 123 : bool simplified = false;
1311 :
1312 : /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1313 : (X AND Y) OR (X AND !Y) is equivalent to X. */
1314 :
1315 637 : for (unsigned i = 0; i < m_preds.length (); i++)
1316 : {
1317 391 : pred_chain &a_chain = m_preds[i];
1318 :
1319 1028 : for (unsigned j = i + 1; j < m_preds.length (); j++)
1320 : {
1321 663 : pred_chain &b_chain = m_preds[j];
1322 1989 : if (b_chain.length () != a_chain.length ())
1323 480 : continue;
1324 :
1325 : unsigned neg_idx = -1U;
1326 595 : for (unsigned k = 0; k < a_chain.length (); ++k)
1327 : {
1328 569 : if (pred_equal_p (a_chain[k], b_chain[k]))
1329 331 : continue;
1330 238 : if (neg_idx != -1U)
1331 : {
1332 : neg_idx = -1U;
1333 : break;
1334 : }
1335 183 : if (pred_neg_p (a_chain[k], b_chain[k]))
1336 : neg_idx = k;
1337 : else
1338 : break;
1339 : }
1340 : /* If we found equal chains with one negated predicate
1341 : simplify. */
1342 183 : if (neg_idx != -1U)
1343 : {
1344 26 : a_chain.ordered_remove (neg_idx);
1345 26 : m_preds.ordered_remove (j);
1346 26 : simplified = true;
1347 540 : if (a_chain.is_empty ())
1348 : {
1349 : /* A && !A simplifies to true, wipe the whole predicate. */
1350 2 : for (unsigned k = 0; k < m_preds.length (); ++k)
1351 1 : m_preds[k].release ();
1352 1 : m_preds.truncate (0);
1353 : }
1354 : break;
1355 : }
1356 : }
1357 : }
1358 :
1359 123 : return simplified;
1360 : }
1361 :
1362 : /* Implement rule 3 for the OR predicate PREDS:
1363 :
1364 : 3) x OR (!x AND y) is equivalent to x OR y. */
1365 :
1366 : bool
1367 123 : predicate::simplify_3 ()
1368 : {
1369 : /* Now iteratively simplify X OR (!X AND Z ..)
1370 : into X OR (Z ...). */
1371 :
1372 123 : unsigned n = m_preds.length ();
1373 123 : if (n < 2)
1374 : return false;
1375 :
1376 : bool simplified = false;
1377 499 : for (unsigned i = 0; i < n; i++)
1378 : {
1379 384 : const pred_chain &a_chain = m_preds[i];
1380 :
1381 384 : if (a_chain.length () != 1)
1382 321 : continue;
1383 :
1384 63 : const pred_info &x = a_chain[0];
1385 285 : for (unsigned j = 0; j < n; j++)
1386 : {
1387 222 : if (j == i)
1388 285 : continue;
1389 :
1390 159 : pred_chain b_chain = m_preds[j];
1391 159 : if (b_chain.length () < 2)
1392 104 : continue;
1393 :
1394 407 : for (unsigned k = 0; k < b_chain.length (); k++)
1395 : {
1396 367 : const pred_info &x2 = b_chain[k];
1397 367 : if (pred_neg_p (x, x2))
1398 : {
1399 15 : b_chain.unordered_remove (k);
1400 15 : simplified = true;
1401 15 : break;
1402 : }
1403 : }
1404 : }
1405 : }
1406 : return simplified;
1407 : }
1408 :
1409 : /* Implement rule 4 for the OR predicate PREDS:
1410 :
1411 : 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1412 : (x != 0 AND y != 0). */
1413 :
1414 : bool
1415 123 : predicate::simplify_4 ()
1416 : {
1417 123 : bool simplified = false;
1418 123 : pred_chain_union s_preds = vNULL;
1419 :
1420 123 : unsigned n = m_preds.length ();
1421 513 : for (unsigned i = 0; i < n; i++)
1422 : {
1423 390 : pred_chain a_chain = m_preds[i];
1424 390 : if (a_chain.length () != 1)
1425 390 : continue;
1426 :
1427 69 : const pred_info &z = a_chain[0];
1428 69 : if (!is_neq_zero_form_p (z))
1429 53 : continue;
1430 :
1431 16 : gimple *def_stmt = SSA_NAME_DEF_STMT (z.pred_lhs);
1432 16 : if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1433 3 : continue;
1434 :
1435 13 : if (gimple_assign_rhs_code (def_stmt) != BIT_AND_EXPR)
1436 13 : continue;
1437 :
1438 0 : for (unsigned j = 0; j < n; j++)
1439 : {
1440 0 : if (j == i)
1441 0 : continue;
1442 :
1443 0 : pred_chain b_chain = m_preds[j];
1444 0 : if (b_chain.length () != 2)
1445 0 : continue;
1446 :
1447 0 : const pred_info &x2 = b_chain[0];
1448 0 : const pred_info &y2 = b_chain[1];
1449 0 : if (!is_neq_zero_form_p (x2) || !is_neq_zero_form_p (y2))
1450 0 : continue;
1451 :
1452 0 : if ((pred_expr_equal_p (x2, gimple_assign_rhs1 (def_stmt))
1453 0 : && pred_expr_equal_p (y2, gimple_assign_rhs2 (def_stmt)))
1454 0 : || (pred_expr_equal_p (x2, gimple_assign_rhs2 (def_stmt))
1455 0 : && pred_expr_equal_p (y2, gimple_assign_rhs1 (def_stmt))))
1456 : {
1457 : /* Kill a_chain. */
1458 0 : a_chain.release ();
1459 0 : simplified = true;
1460 0 : break;
1461 : }
1462 : }
1463 : }
1464 : /* Now clean up the chain. */
1465 123 : if (simplified)
1466 : {
1467 0 : for (unsigned i = 0; i < n; i++)
1468 : {
1469 0 : if (m_preds[i].is_empty ())
1470 0 : continue;
1471 0 : s_preds.safe_push (m_preds[i]);
1472 : }
1473 :
1474 0 : m_preds.release ();
1475 0 : m_preds = s_preds;
1476 0 : s_preds = vNULL;
1477 : }
1478 :
1479 123 : return simplified;
1480 : }
1481 :
1482 : /* Simplify predicates in *THIS. */
1483 :
1484 : void
1485 522 : predicate::simplify (gimple *use_or_def, bool is_use)
1486 : {
1487 522 : if (dump_file && dump_flags & TDF_DETAILS)
1488 : {
1489 0 : fprintf (dump_file, "Before simplication ");
1490 0 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1491 : }
1492 :
1493 1307 : for (unsigned i = 0; i < m_preds.length (); i++)
1494 : {
1495 785 : ::simplify_1a (m_preds[i]);
1496 785 : if (::simplify_1b (m_preds[i]))
1497 : {
1498 4 : m_preds[i].release ();
1499 4 : m_preds.ordered_remove (i);
1500 4 : i--;
1501 : }
1502 : }
1503 :
1504 522 : if (m_preds.length () < 2)
1505 : return;
1506 :
1507 123 : bool changed;
1508 123 : do
1509 : {
1510 123 : changed = false;
1511 123 : if (simplify_2 ())
1512 : changed = true;
1513 :
1514 123 : if (simplify_3 ())
1515 9 : changed = true;
1516 :
1517 123 : if (simplify_4 ())
1518 0 : changed = true;
1519 : }
1520 : while (changed);
1521 : }
1522 :
1523 : /* Attempt to normalize predicate chains by following UD chains by
1524 : building up a big tree of either IOR operations or AND operations,
1525 : and converting the IOR tree into a pred_chain_union or the BIT_AND
1526 : tree into a pred_chain.
1527 : Example:
1528 :
1529 : _3 = _2 RELOP1 _1;
1530 : _6 = _5 RELOP2 _4;
1531 : _9 = _8 RELOP3 _7;
1532 : _10 = _3 | _6;
1533 : _12 = _9 | _0;
1534 : _t = _10 | _12;
1535 :
1536 : then _t != 0 will be normalized into a pred_chain_union
1537 :
1538 : (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1539 :
1540 : Similarly given:
1541 :
1542 : _3 = _2 RELOP1 _1;
1543 : _6 = _5 RELOP2 _4;
1544 : _9 = _8 RELOP3 _7;
1545 : _10 = _3 & _6;
1546 : _12 = _9 & _0;
1547 :
1548 : then _t != 0 will be normalized into a pred_chain:
1549 : (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1550 : */
1551 :
1552 : /* Normalize predicate PRED:
1553 : 1) if PRED can no longer be normalized, append it to *THIS.
1554 : 2) otherwise if PRED is of the form x != 0, follow x's definition
1555 : and put normalized predicates into WORK_LIST. */
1556 :
1557 : void
1558 2464 : predicate::normalize (pred_chain *norm_chain,
1559 : pred_info pred,
1560 : tree_code and_or_code,
1561 : pred_chain *work_list,
1562 : hash_set<tree> *mark_set)
1563 : {
1564 2464 : if (!is_neq_zero_form_p (pred))
1565 : {
1566 1333 : if (and_or_code == BIT_IOR_EXPR)
1567 0 : push_pred (pred);
1568 : else
1569 1333 : norm_chain->safe_push (pred);
1570 1333 : return;
1571 : }
1572 :
1573 1131 : gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1574 :
1575 1131 : if (gimple_code (def_stmt) == GIMPLE_PHI
1576 1131 : && is_degenerate_phi (def_stmt, &pred))
1577 : /* PRED has been modified above. */
1578 0 : work_list->safe_push (pred);
1579 1131 : else if (gimple_code (def_stmt) == GIMPLE_PHI && and_or_code == BIT_IOR_EXPR)
1580 : {
1581 3 : unsigned n = gimple_phi_num_args (def_stmt);
1582 :
1583 : /* Punt for a nonzero constant. The predicate should be one guarding
1584 : the phi edge. */
1585 9 : for (unsigned i = 0; i < n; ++i)
1586 : {
1587 6 : tree op = gimple_phi_arg_def (def_stmt, i);
1588 6 : if (TREE_CODE (op) == INTEGER_CST && !integer_zerop (op))
1589 : {
1590 0 : push_pred (pred);
1591 0 : return;
1592 : }
1593 : }
1594 :
1595 9 : for (unsigned i = 0; i < n; ++i)
1596 : {
1597 6 : tree op = gimple_phi_arg_def (def_stmt, i);
1598 6 : if (integer_zerop (op))
1599 0 : continue;
1600 :
1601 6 : push_to_worklist (op, work_list, mark_set);
1602 : }
1603 : }
1604 1128 : else if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
1605 : {
1606 263 : if (and_or_code == BIT_IOR_EXPR)
1607 7 : push_pred (pred);
1608 : else
1609 256 : norm_chain->safe_push (pred);
1610 : }
1611 865 : else if (gimple_assign_rhs_code (def_stmt) == and_or_code)
1612 : {
1613 : /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
1614 59 : if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt)))
1615 : {
1616 : /* But treat x & 3 as a condition. */
1617 34 : if (and_or_code == BIT_AND_EXPR)
1618 : {
1619 34 : pred_info n_pred;
1620 34 : n_pred.pred_lhs = gimple_assign_rhs1 (def_stmt);
1621 34 : n_pred.pred_rhs = gimple_assign_rhs2 (def_stmt);
1622 34 : n_pred.cond_code = and_or_code;
1623 34 : n_pred.invert = false;
1624 34 : norm_chain->safe_push (n_pred);
1625 : }
1626 : }
1627 : else
1628 : {
1629 25 : push_to_worklist (gimple_assign_rhs1 (def_stmt), work_list, mark_set);
1630 25 : push_to_worklist (gimple_assign_rhs2 (def_stmt), work_list, mark_set);
1631 : }
1632 : }
1633 806 : else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt))
1634 : == tcc_comparison)
1635 : {
1636 35 : pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1637 35 : if (and_or_code == BIT_IOR_EXPR)
1638 0 : push_pred (n_pred);
1639 : else
1640 35 : norm_chain->safe_push (n_pred);
1641 : }
1642 : else
1643 : {
1644 771 : if (and_or_code == BIT_IOR_EXPR)
1645 0 : push_pred (pred);
1646 : else
1647 771 : norm_chain->safe_push (pred);
1648 : }
1649 : }
1650 :
1651 : /* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */
1652 :
1653 : void
1654 272 : predicate::normalize (const pred_info &pred)
1655 : {
1656 272 : if (!is_neq_zero_form_p (pred))
1657 : {
1658 157 : push_pred (pred);
1659 403 : return;
1660 : }
1661 :
1662 115 : tree_code and_or_code = ERROR_MARK;
1663 :
1664 115 : gimple *def_stmt = SSA_NAME_DEF_STMT (pred.pred_lhs);
1665 115 : if (gimple_code (def_stmt) == GIMPLE_ASSIGN)
1666 41 : and_or_code = gimple_assign_rhs_code (def_stmt);
1667 115 : if (and_or_code != BIT_IOR_EXPR && and_or_code != BIT_AND_EXPR)
1668 : {
1669 89 : if (TREE_CODE_CLASS (and_or_code) == tcc_comparison)
1670 : {
1671 0 : pred_info n_pred = get_pred_info_from_cmp (def_stmt);
1672 0 : push_pred (n_pred);
1673 : }
1674 : else
1675 89 : push_pred (pred);
1676 89 : return;
1677 : }
1678 :
1679 :
1680 26 : pred_chain norm_chain = vNULL;
1681 26 : pred_chain work_list = vNULL;
1682 26 : work_list.safe_push (pred);
1683 26 : hash_set<tree> mark_set;
1684 :
1685 74 : while (!work_list.is_empty ())
1686 : {
1687 48 : pred_info a_pred = work_list.pop ();
1688 48 : normalize (&norm_chain, a_pred, and_or_code, &work_list, &mark_set);
1689 : }
1690 :
1691 26 : if (and_or_code == BIT_AND_EXPR)
1692 23 : m_preds.safe_push (norm_chain);
1693 :
1694 26 : work_list.release ();
1695 26 : }
1696 :
1697 : /* Normalize a single predicate PRED_CHAIN and append it to *THIS. */
1698 :
1699 : void
1700 482 : predicate::normalize (const pred_chain &chain)
1701 : {
1702 482 : pred_chain work_list = vNULL;
1703 482 : hash_set<tree> mark_set;
1704 2866 : for (unsigned i = 0; i < chain.length (); i++)
1705 : {
1706 2384 : work_list.safe_push (chain[i]);
1707 2384 : mark_set.add (chain[i].pred_lhs);
1708 : }
1709 :
1710 : /* Normalized chain of predicates built up below. */
1711 482 : pred_chain norm_chain = vNULL;
1712 2898 : while (!work_list.is_empty ())
1713 : {
1714 2416 : pred_info pi = work_list.pop ();
1715 : /* The predicate object is not modified here, only NORM_CHAIN and
1716 : WORK_LIST are appended to. */
1717 4832 : unsigned oldlen = m_preds.length ();
1718 2416 : normalize (&norm_chain, pi, BIT_AND_EXPR, &work_list, &mark_set);
1719 3843 : gcc_assert (m_preds.length () == oldlen);
1720 : }
1721 :
1722 482 : m_preds.safe_push (norm_chain);
1723 482 : work_list.release ();
1724 482 : }
1725 :
1726 : /* Normalize predicate chains in THIS. */
1727 :
1728 : void
1729 522 : predicate::normalize (gimple *use_or_def, bool is_use)
1730 : {
1731 522 : if (dump_file && dump_flags & TDF_DETAILS)
1732 : {
1733 0 : fprintf (dump_file, "Before normalization ");
1734 0 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1735 : }
1736 :
1737 522 : predicate norm_preds (empty_val ());
1738 1276 : for (unsigned i = 0; i < m_preds.length (); i++)
1739 : {
1740 754 : if (m_preds[i].length () != 1)
1741 482 : norm_preds.normalize (m_preds[i]);
1742 : else
1743 272 : norm_preds.normalize (m_preds[i][0]);
1744 : }
1745 :
1746 522 : *this = norm_preds;
1747 :
1748 522 : if (dump_file)
1749 : {
1750 4 : fprintf (dump_file, "After normalization ");
1751 6 : dump (dump_file, use_or_def, is_use ? "[USE]:\n" : "[DEF]:\n");
1752 : }
1753 522 : }
1754 :
1755 : /* Convert the chains of control dependence edges into a set of predicates.
1756 : A control dependence chain is represented by a vector edges. DEP_CHAINS
1757 : points to an array of NUM_CHAINS dependence chains. One edge in
1758 : a dependence chain is mapped to predicate expression represented by
1759 : pred_info type. One dependence chain is converted to a composite
1760 : predicate that is the result of AND operation of pred_info mapped to
1761 : each edge. A composite predicate is represented by a vector of
1762 : pred_info. Sets M_PREDS to the resulting composite predicates. */
1763 :
1764 : void
1765 755 : predicate::init_from_control_deps (const vec<edge> *dep_chains,
1766 : unsigned num_chains, bool is_use)
1767 : {
1768 755 : gcc_assert (is_empty ());
1769 :
1770 755 : if (num_chains == 0)
1771 : return;
1772 :
1773 685 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1774 6 : fprintf (dump_file, "init_from_control_deps [%s] {%s}:\n",
1775 : is_use ? "USE" : "DEF",
1776 8 : format_edge_vecs (dep_chains, num_chains).c_str ());
1777 :
1778 : /* Convert the control dependency chain into a set of predicates. */
1779 685 : m_preds.reserve (num_chains);
1780 :
1781 1474 : for (unsigned i = 0; i < num_chains; i++)
1782 : {
1783 : /* One path through the CFG represents a logical conjunction
1784 : of the predicates. */
1785 949 : const vec<edge> &path = dep_chains[i];
1786 :
1787 949 : bool has_valid_pred = false;
1788 : /* The chain of predicates guarding the definition along this path. */
1789 949 : pred_chain t_chain{ };
1790 4028 : for (unsigned j = 0; j < path.length (); j++)
1791 : {
1792 3083 : edge e = path[j];
1793 3083 : basic_block guard_bb = e->src;
1794 :
1795 6166 : gcc_assert (!empty_block_p (guard_bb) && !single_succ_p (guard_bb));
1796 :
1797 : /* Skip this edge if it is bypassing an abort - when the
1798 : condition is not satisfied we are neither reaching the
1799 : definition nor the use so it isn't meaningful. Note if
1800 : we are processing the use predicate the condition is
1801 : meaningful. See PR65244. */
1802 3083 : if (!is_use && EDGE_COUNT (e->src->succs) == 2)
1803 : {
1804 1188 : edge e1;
1805 1188 : edge_iterator ei1;
1806 1188 : bool skip = false;
1807 :
1808 3562 : FOR_EACH_EDGE (e1, ei1, e->src->succs)
1809 : {
1810 2375 : if (EDGE_COUNT (e1->dest->succs) == 0)
1811 : {
1812 : skip = true;
1813 : break;
1814 : }
1815 : }
1816 1188 : if (skip)
1817 : {
1818 1 : has_valid_pred = true;
1819 1 : continue;
1820 : }
1821 : }
1822 : /* Get the conditional controlling the bb exit edge. */
1823 3082 : gimple *cond_stmt = *gsi_last_bb (guard_bb);
1824 3082 : if (gimple_code (cond_stmt) == GIMPLE_COND)
1825 : {
1826 : /* The true edge corresponds to the uninteresting condition.
1827 : Add the negated predicate(s) for the edge to record
1828 : the interesting condition. */
1829 3042 : pred_info one_pred;
1830 3042 : one_pred.pred_lhs = gimple_cond_lhs (cond_stmt);
1831 3042 : one_pred.pred_rhs = gimple_cond_rhs (cond_stmt);
1832 3042 : one_pred.cond_code = gimple_cond_code (cond_stmt);
1833 3042 : one_pred.invert = !!(e->flags & EDGE_FALSE_VALUE);
1834 :
1835 3042 : t_chain.safe_push (one_pred);
1836 :
1837 3042 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1838 : {
1839 6 : fprintf (dump_file, "%d -> %d: one_pred = ",
1840 6 : e->src->index, e->dest->index);
1841 6 : dump_pred_info (dump_file, one_pred);
1842 6 : fputc ('\n', dump_file);
1843 : }
1844 :
1845 3042 : has_valid_pred = true;
1846 : }
1847 40 : else if (gswitch *gs = dyn_cast<gswitch *> (cond_stmt))
1848 : {
1849 : /* Find the case label, but avoid quadratic behavior. */
1850 23 : tree l = get_cases_for_edge (e, gs);
1851 : /* If more than one label reaches this block or the case
1852 : label doesn't have a contiguous range of values (like the
1853 : default one) fail. */
1854 46 : if (!l || CASE_CHAIN (l) || !CASE_LOW (l))
1855 : has_valid_pred = false;
1856 22 : else if (!CASE_HIGH (l)
1857 22 : || operand_equal_p (CASE_LOW (l), CASE_HIGH (l)))
1858 : {
1859 22 : pred_info one_pred;
1860 22 : one_pred.pred_lhs = gimple_switch_index (gs);
1861 22 : one_pred.pred_rhs = CASE_LOW (l);
1862 22 : one_pred.cond_code = EQ_EXPR;
1863 22 : one_pred.invert = false;
1864 22 : t_chain.safe_push (one_pred);
1865 22 : has_valid_pred = true;
1866 : }
1867 : else
1868 : {
1869 : /* Support a case label with a range with
1870 : two predicates. We're overcommitting on
1871 : the MAX_CHAIN_LEN budget by at most a factor
1872 : of two here. */
1873 0 : pred_info one_pred;
1874 0 : one_pred.pred_lhs = gimple_switch_index (gs);
1875 0 : one_pred.pred_rhs = CASE_LOW (l);
1876 0 : one_pred.cond_code = GE_EXPR;
1877 0 : one_pred.invert = false;
1878 0 : t_chain.safe_push (one_pred);
1879 0 : one_pred.pred_rhs = CASE_HIGH (l);
1880 0 : one_pred.cond_code = LE_EXPR;
1881 0 : t_chain.safe_push (one_pred);
1882 0 : has_valid_pred = true;
1883 : }
1884 : }
1885 17 : else if (stmt_can_throw_internal (cfun, cond_stmt)
1886 17 : && !(e->flags & EDGE_EH))
1887 : /* Ignore the exceptional control flow and proceed as if
1888 : E were a fallthru without a controlling predicate for
1889 : both the USE (valid) and DEF (questionable) case. */
1890 : has_valid_pred = true;
1891 : else
1892 : has_valid_pred = false;
1893 :
1894 : /* For USE predicates we can drop components of the
1895 : AND chain. */
1896 3079 : if (!has_valid_pred && !is_use)
1897 : break;
1898 : }
1899 :
1900 : /* For DEF predicates we have to drop components of the OR chain
1901 : on failure. */
1902 949 : if (!has_valid_pred && !is_use)
1903 : {
1904 4 : t_chain.release ();
1905 4 : continue;
1906 : }
1907 :
1908 : /* When we add || 1 simply prune the chain and return. */
1909 945 : if (t_chain.is_empty ())
1910 : {
1911 160 : t_chain.release ();
1912 480 : for (auto chain : m_preds)
1913 0 : chain.release ();
1914 160 : m_preds.truncate (0);
1915 160 : break;
1916 : }
1917 :
1918 785 : m_preds.quick_push (t_chain);
1919 : }
1920 :
1921 685 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1922 4 : dump (dump_file);
1923 : }
1924 :
1925 : /* Store a PRED in *THIS. */
1926 :
1927 : void
1928 253 : predicate::push_pred (const pred_info &pred)
1929 : {
1930 253 : pred_chain chain = vNULL;
1931 253 : chain.safe_push (pred);
1932 253 : m_preds.safe_push (chain);
1933 253 : }
1934 :
1935 : /* Dump predicates in *THIS to F. */
1936 :
1937 : void
1938 8 : predicate::dump (FILE *f) const
1939 : {
1940 8 : unsigned np = m_preds.length ();
1941 8 : if (np == 0)
1942 : {
1943 0 : fprintf (f, "\tTRUE (empty)\n");
1944 0 : return;
1945 : }
1946 :
1947 16 : for (unsigned i = 0; i < np; i++)
1948 : {
1949 8 : if (i > 0)
1950 0 : fprintf (f, "\tOR (");
1951 : else
1952 8 : fprintf (f, "\t(");
1953 8 : dump_pred_chain (f, m_preds[i]);
1954 8 : fprintf (f, ")\n");
1955 : }
1956 : }
1957 :
1958 : /* Dump predicates in *THIS to stderr. */
1959 :
1960 : void
1961 0 : predicate::debug () const
1962 : {
1963 0 : dump (stderr);
1964 0 : }
1965 :
1966 : /* Dump predicates in *THIS for STMT prepended by MSG to F. */
1967 :
1968 : void
1969 4 : predicate::dump (FILE *f, gimple *stmt, const char *msg) const
1970 : {
1971 4 : fprintf (f, "%s", msg);
1972 4 : if (stmt)
1973 : {
1974 4 : fputc ('\t', f);
1975 4 : print_gimple_stmt (f, stmt, 0);
1976 4 : fprintf (f, " is conditional on:\n");
1977 : }
1978 :
1979 4 : dump (f);
1980 4 : }
1981 :
1982 : /* Initialize USE_PREDS with the predicates of the control dependence chains
1983 : between the basic block DEF_BB that defines a variable of interst and
1984 : USE_BB that uses the variable, respectively. */
1985 :
1986 : bool
1987 569 : uninit_analysis::init_use_preds (predicate &use_preds, basic_block def_bb,
1988 : basic_block use_bb)
1989 : {
1990 569 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
1991 2 : fprintf (dump_file, "init_use_preds (def_bb = %u, use_bb = %u)\n",
1992 : def_bb->index, use_bb->index);
1993 :
1994 569 : gcc_assert (use_preds.is_empty ()
1995 : && dominated_by_p (CDI_DOMINATORS, use_bb, def_bb));
1996 :
1997 : /* Set CD_ROOT to the basic block closest to USE_BB that is the control
1998 : equivalent of (is guarded by the same predicate as) DEF_BB that also
1999 : dominates USE_BB. This mimics the inner loop in
2000 : compute_control_dep_chain. */
2001 : basic_block cd_root = def_bb;
2002 749 : do
2003 : {
2004 749 : basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, cd_root);
2005 :
2006 : /* Stop at a loop exit which is also postdominating cd_root. */
2007 919 : if (single_pred_p (pdom) && !single_succ_p (cd_root))
2008 : break;
2009 :
2010 1342 : if (!dominated_by_p (CDI_DOMINATORS, pdom, cd_root)
2011 671 : || !dominated_by_p (CDI_DOMINATORS, use_bb, pdom))
2012 : break;
2013 :
2014 : cd_root = pdom;
2015 : }
2016 : while (1);
2017 :
2018 569 : auto_bb_flag in_region (cfun);
2019 569 : auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2020 569 : param_uninit_control_dep_attempts));
2021 :
2022 : /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
2023 : Each DEP_CHAINS element is a series of edges whose conditions
2024 : are logical conjunctions. Together, the DEP_CHAINS vector is
2025 : used below to initialize an OR expression of the conjunctions. */
2026 569 : unsigned num_chains = 0;
2027 5121 : auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2028 :
2029 569 : if (!dfs_mark_dominating_region (use_bb, cd_root, in_region, region)
2030 1138 : || !compute_control_dep_chain (cd_root, use_bb, dep_chains, &num_chains,
2031 569 : in_region))
2032 : {
2033 : /* If the info in dep_chains is not complete we need to use a
2034 : conservative approximation for the use predicate. */
2035 0 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
2036 0 : fprintf (dump_file, "init_use_preds: dep_chain incomplete, using "
2037 : "conservative approximation\n");
2038 0 : num_chains = 1;
2039 0 : dep_chains[0].truncate (0);
2040 0 : simple_control_dep_chain (dep_chains[0], cd_root, use_bb);
2041 : }
2042 :
2043 : /* Unmark the region. */
2044 3664 : for (auto bb : region)
2045 1957 : bb->flags &= ~in_region;
2046 :
2047 : /* From the set of edges computed above initialize *THIS as the OR
2048 : condition under which the definition in DEF_BB is used in USE_BB.
2049 : Each OR subexpression is represented by one element of DEP_CHAINS,
2050 : where each element consists of a series of AND subexpressions. */
2051 569 : use_preds.init_from_control_deps (dep_chains, num_chains, true);
2052 5690 : delete[] dep_chains;
2053 1138 : return !use_preds.is_empty ();
2054 569 : }
2055 :
2056 : /* Release resources in *THIS. */
2057 :
2058 1852 : predicate::~predicate ()
2059 : {
2060 1852 : unsigned n = m_preds.length ();
2061 3368 : for (unsigned i = 0; i != n; ++i)
2062 1516 : m_preds[i].release ();
2063 1852 : m_preds.release ();
2064 1852 : }
2065 :
2066 : /* Copy-assign RHS to *THIS. */
2067 :
2068 : predicate&
2069 522 : predicate::operator= (const predicate &rhs)
2070 : {
2071 522 : if (this == &rhs)
2072 : return *this;
2073 :
2074 522 : m_cval = rhs.m_cval;
2075 :
2076 522 : unsigned n = m_preds.length ();
2077 1276 : for (unsigned i = 0; i != n; ++i)
2078 754 : m_preds[i].release ();
2079 522 : m_preds.release ();
2080 :
2081 522 : n = rhs.m_preds.length ();
2082 1280 : for (unsigned i = 0; i != n; ++i)
2083 : {
2084 758 : const pred_chain &chain = rhs.m_preds[i];
2085 758 : m_preds.safe_push (chain.copy ());
2086 : }
2087 :
2088 : return *this;
2089 : }
2090 :
2091 : /* For each use edge of PHI, compute all control dependence chains
2092 : and convert those to the composite predicates in M_PREDS.
2093 : Return true if a nonempty predicate has been obtained. */
2094 :
2095 : bool
2096 186 : uninit_analysis::init_from_phi_def (gphi *phi)
2097 : {
2098 186 : gcc_assert (m_phi_def_preds.is_empty ());
2099 :
2100 186 : basic_block phi_bb = gimple_bb (phi);
2101 : /* Find the closest dominating bb to be the control dependence root. */
2102 186 : basic_block cd_root = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
2103 186 : if (!cd_root)
2104 : return false;
2105 :
2106 : /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
2107 : definitions of each of the PHI operands for which M_EVAL is false. */
2108 186 : auto_vec<edge> def_edges;
2109 186 : hash_set<gimple *> visited_phis;
2110 186 : collect_phi_def_edges (phi, cd_root, &def_edges, &visited_phis);
2111 :
2112 372 : unsigned nedges = def_edges.length ();
2113 186 : if (nedges == 0)
2114 : return false;
2115 :
2116 186 : auto_bb_flag in_region (cfun);
2117 186 : auto_vec<basic_block, 20> region (MIN (n_basic_blocks_for_fn (cfun),
2118 186 : param_uninit_control_dep_attempts));
2119 : /* Pre-mark the PHI incoming edges PHI block to make sure we only walk
2120 : interesting edges from there. */
2121 440 : for (unsigned i = 0; i < nedges; i++)
2122 : {
2123 254 : if (!(def_edges[i]->dest->flags & in_region))
2124 : {
2125 217 : if (!region.space (1))
2126 : break;
2127 217 : def_edges[i]->dest->flags |= in_region;
2128 217 : region.quick_push (def_edges[i]->dest);
2129 : }
2130 : }
2131 440 : for (unsigned i = 0; i < nedges; i++)
2132 254 : if (!dfs_mark_dominating_region (def_edges[i]->src, cd_root,
2133 : in_region, region))
2134 : break;
2135 :
2136 186 : unsigned num_chains = 0;
2137 1674 : auto_vec<edge> *dep_chains = new auto_vec<edge>[MAX_NUM_CHAINS];
2138 440 : for (unsigned i = 0; i < nedges; i++)
2139 : {
2140 254 : edge e = def_edges[i];
2141 254 : unsigned prev_nc = num_chains;
2142 254 : bool complete_p = compute_control_dep_chain (cd_root, e->src, dep_chains,
2143 254 : &num_chains, in_region);
2144 :
2145 : /* Update the newly added chains with the phi operand edge. */
2146 254 : if (EDGE_COUNT (e->src->succs) > 1)
2147 : {
2148 0 : if (complete_p
2149 0 : && prev_nc == num_chains
2150 0 : && num_chains < MAX_NUM_CHAINS)
2151 : /* We can only add a chain for the PHI operand edge when the
2152 : collected info was complete, otherwise the predicate may
2153 : not be conservative. */
2154 0 : dep_chains[num_chains++] = vNULL;
2155 0 : for (unsigned j = prev_nc; j < num_chains; j++)
2156 0 : dep_chains[j].safe_push (e);
2157 : }
2158 : }
2159 :
2160 : /* Unmark the region. */
2161 4694 : for (auto bb : region)
2162 4136 : bb->flags &= ~in_region;
2163 :
2164 : /* Convert control dependence chains to the predicate in *THIS under
2165 : which the PHI operands are defined to values for which M_EVAL is
2166 : false. */
2167 186 : m_phi_def_preds.init_from_control_deps (dep_chains, num_chains, false);
2168 1860 : delete[] dep_chains;
2169 372 : return !m_phi_def_preds.is_empty ();
2170 372 : }
2171 :
2172 : /* Compute the predicates that guard the use USE_STMT and check if
2173 : the incoming paths that have an empty (or possibly empty) definition
2174 : can be pruned. Return true if it can be determined that the use of
2175 : PHI's def in USE_STMT is guarded by a predicate set that does not
2176 : overlap with the predicate sets of all runtime paths that do not
2177 : have a definition.
2178 :
2179 : Return false if the use is not guarded or if it cannot be determined.
2180 : USE_BB is the bb of the use (for phi operand use, the bb is not the bb
2181 : of the phi stmt, but the source bb of the operand edge).
2182 :
2183 : OPNDS is a bitmap with a bit set for each PHI operand of interest.
2184 :
2185 : THIS->M_PREDS contains the (memoized) defining predicate chains of
2186 : a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate
2187 : chains are computed and stored into THIS->M_PREDS as needed.
2188 :
2189 : VISITED_PHIS is a pointer set of phis being visited. */
2190 :
2191 : bool
2192 588 : uninit_analysis::is_use_guarded (gimple *use_stmt, basic_block use_bb,
2193 : gphi *phi, unsigned opnds,
2194 : hash_set<gphi *> *visited)
2195 : {
2196 588 : if (visited->add (phi))
2197 : return false;
2198 :
2199 : /* The basic block where the PHI is defined. */
2200 569 : basic_block def_bb = gimple_bb (phi);
2201 :
2202 : /* Try to build the predicate expression under which the PHI flows
2203 : into its use. This will be empty if the PHI is defined and used
2204 : in the same bb. */
2205 569 : predicate use_preds (true);
2206 569 : if (!init_use_preds (use_preds, def_bb, use_bb))
2207 : return false;
2208 :
2209 408 : use_preds.simplify (use_stmt, /*is_use=*/true);
2210 408 : use_preds.normalize (use_stmt, /*is_use=*/true);
2211 560 : if (use_preds.is_false ())
2212 : return true;
2213 408 : if (use_preds.is_true ())
2214 : return false;
2215 :
2216 : /* Try to prune the dead incoming phi edges. */
2217 407 : if (!overlap (phi, opnds, visited, use_preds))
2218 : {
2219 113 : if (DEBUG_PREDICATE_ANALYZER && dump_file)
2220 0 : fputs ("found predicate overlap\n", dump_file);
2221 :
2222 113 : return true;
2223 : }
2224 :
2225 294 : if (m_phi_def_preds.is_empty ())
2226 : {
2227 : /* Lazily initialize *THIS from PHI. */
2228 186 : if (!init_from_phi_def (phi))
2229 : return false;
2230 :
2231 114 : m_phi_def_preds.simplify (phi);
2232 114 : m_phi_def_preds.normalize (phi);
2233 531 : if (m_phi_def_preds.is_false ())
2234 : return false;
2235 114 : if (m_phi_def_preds.is_true ())
2236 : return true;
2237 : }
2238 :
2239 : /* Return true if the predicate guarding the valid definition (i.e.,
2240 : *THIS) is a superset of the predicate guarding the use (i.e.,
2241 : USE_PREDS). */
2242 222 : if (m_phi_def_preds.superset_of (use_preds))
2243 : return true;
2244 :
2245 : return false;
2246 569 : }
2247 :
2248 : /* Public interface to the above. */
2249 :
2250 : bool
2251 548 : uninit_analysis::is_use_guarded (gimple *stmt, basic_block use_bb, gphi *phi,
2252 : unsigned opnds)
2253 : {
2254 548 : hash_set<gphi *> visited;
2255 548 : return is_use_guarded (stmt, use_bb, phi, opnds, &visited);
2256 548 : }
2257 :
|
