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