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