1 /* Support for simple predicate analysis.
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>
7 This file is part of GCC.
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)
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.
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/>. */
23 #define INCLUDE_STRING
26 #include "coretypes.h"
30 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "diagnostic-core.h"
34 #include "fold-const.h"
35 #include "gimple-iterator.h"
42 #include "value-query.h"
46 #include "gimple-predicate-analysis.h"
48 #define DEBUG_PREDICATE_ANALYZER 1
50 /* In our predicate normal form we have MAX_NUM_CHAINS or predicates
51 and in those MAX_CHAIN_LEN (inverted) and predicates. */
52 #define MAX_NUM_CHAINS 8
53 #define MAX_CHAIN_LEN 5
55 /* Return true if X1 is the negation of X2. */
58 pred_neg_p (const pred_info
&x1
, const pred_info
&x2
)
60 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
61 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
64 tree_code c1
= x1
.cond_code
, c2
;
65 if (x1
.invert
== x2
.invert
)
66 c2
= invert_tree_comparison (x2
.cond_code
, false);
73 /* Return whether the condition (VAL CMPC BOUNDARY) is true. */
76 is_value_included_in (tree val
, tree boundary
, tree_code cmpc
)
78 /* Only handle integer constant here. */
79 if (TREE_CODE (val
) != INTEGER_CST
|| TREE_CODE (boundary
) != INTEGER_CST
)
82 bool inverted
= false;
83 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
|| cmpc
== NE_EXPR
)
85 cmpc
= invert_tree_comparison (cmpc
, false);
91 result
= tree_int_cst_equal (val
, boundary
);
92 else if (cmpc
== LT_EXPR
)
93 result
= tree_int_cst_lt (val
, boundary
);
96 gcc_assert (cmpc
== LE_EXPR
);
97 result
= tree_int_cst_le (val
, boundary
);
106 /* Format the vector of edges EV as a string. */
109 format_edge_vec (const vec
<edge
> &ev
)
113 unsigned n
= ev
.length ();
114 for (unsigned i
= 0; i
< n
; ++i
)
117 const_edge e
= ev
[i
];
118 sprintf (es
, "%u -> %u", e
->src
->index
, e
->dest
->index
);
126 /* Format the first N elements of the array of vector of edges EVA as
130 format_edge_vecs (const vec
<edge
> eva
[], unsigned n
)
134 for (unsigned i
= 0; i
!= n
; ++i
)
137 str
+= format_edge_vec (eva
[i
]);
145 /* Dump a single pred_info to F. */
148 dump_pred_info (FILE *f
, const pred_info
&pred
)
151 fprintf (f
, "NOT (");
152 print_generic_expr (f
, pred
.pred_lhs
);
153 fprintf (f
, " %s ", op_symbol_code (pred
.cond_code
));
154 print_generic_expr (f
, pred
.pred_rhs
);
159 /* Dump a pred_chain to F. */
162 dump_pred_chain (FILE *f
, const pred_chain
&chain
)
164 unsigned np
= chain
.length ();
165 for (unsigned j
= 0; j
< np
; j
++)
168 fprintf (f
, " AND (");
171 dump_pred_info (f
, chain
[j
]);
176 /* Return the 'normalized' conditional code with operand swapping
177 and condition inversion controlled by SWAP_COND and INVERT. */
180 get_cmp_code (tree_code orig_cmp_code
, bool swap_cond
, bool invert
)
182 tree_code tc
= orig_cmp_code
;
185 tc
= swap_tree_comparison (orig_cmp_code
);
187 tc
= invert_tree_comparison (tc
, false);
204 /* Return true if PRED is common among all predicate chains in PREDS
205 (and therefore can be factored out). */
208 find_matching_predicate_in_rest_chains (const pred_info
&pred
,
209 const pred_chain_union
&preds
)
212 if (preds
.length () == 1)
215 for (unsigned i
= 1; i
< preds
.length (); i
++)
218 const pred_chain
&chain
= preds
[i
];
219 unsigned n
= chain
.length ();
220 for (unsigned j
= 0; j
< n
; j
++)
222 const pred_info
&pred2
= chain
[j
];
223 /* Can relax the condition comparison to not use address
224 comparison. However, the most common case is that
225 multiple control dependent paths share a common path
226 prefix, so address comparison should be ok. */
227 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
228 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
229 && pred2
.invert
== pred
.invert
)
241 /* Find a predicate to examine against paths of interest. If there
242 is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
243 of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
244 PHI is the phi node whose incoming (interesting) paths need to be
245 examined. On success, return the comparison code, set defintion
246 gimple of FLAG_DEF and BOUNDARY_CST. Otherwise return ERROR_MARK. */
249 find_var_cmp_const (pred_chain_union preds
, gphi
*phi
, gimple
**flag_def
,
252 tree_code vrinfo_code
= ERROR_MARK
;
253 gimple
*vrinfo_def
= NULL
;
254 tree vrinfo_cst
= NULL
;
256 gcc_assert (preds
.length () > 0);
257 pred_chain chain
= preds
[0];
258 for (unsigned i
= 0; i
< chain
.length (); i
++)
260 bool use_vrinfo_p
= false;
261 const pred_info
&pred
= chain
[i
];
262 tree cond_lhs
= pred
.pred_lhs
;
263 tree cond_rhs
= pred
.pred_rhs
;
264 if (cond_lhs
== NULL_TREE
|| cond_rhs
== NULL_TREE
)
267 tree_code code
= get_cmp_code (pred
.cond_code
, false, pred
.invert
);
268 if (code
== ERROR_MARK
)
271 /* Convert to the canonical form SSA_NAME CMP CONSTANT. */
272 if (TREE_CODE (cond_lhs
) == SSA_NAME
273 && is_gimple_constant (cond_rhs
))
275 else if (TREE_CODE (cond_rhs
) == SSA_NAME
276 && is_gimple_constant (cond_lhs
))
278 std::swap (cond_lhs
, cond_rhs
);
279 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
282 /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
283 with value range info. Note only first of such case is handled. */
284 else if (vrinfo_code
== ERROR_MARK
285 && TREE_CODE (cond_lhs
) == SSA_NAME
286 && TREE_CODE (cond_rhs
) == SSA_NAME
)
288 gimple
* lhs_def
= SSA_NAME_DEF_STMT (cond_lhs
);
289 if (!lhs_def
|| gimple_code (lhs_def
) != GIMPLE_PHI
290 || gimple_bb (lhs_def
) != gimple_bb (phi
))
292 std::swap (cond_lhs
, cond_rhs
);
293 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
297 /* Check value range info of rhs, do following transforms:
298 flag_var < [min, max] -> flag_var < max
299 flag_var > [min, max] -> flag_var > min
301 We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
302 flag_var <= [min, max] -> flag_var < [min, max+1]
303 flag_var >= [min, max] -> flag_var > [min-1, max]
304 if no overflow/wrap. */
305 tree type
= TREE_TYPE (cond_lhs
);
307 if (!INTEGRAL_TYPE_P (type
)
308 || !get_range_query (cfun
)->range_of_expr (r
, cond_rhs
)
309 || r
.kind () != VR_RANGE
)
312 wide_int min
= r
.lower_bound ();
313 wide_int max
= r
.upper_bound ();
315 && max
!= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
321 && min
!= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
327 cond_rhs
= wide_int_to_tree (type
, max
);
328 else if (code
== GT_EXPR
)
329 cond_rhs
= wide_int_to_tree (type
, min
);
338 if ((*flag_def
= SSA_NAME_DEF_STMT (cond_lhs
)) == NULL
)
341 if (gimple_code (*flag_def
) != GIMPLE_PHI
342 || gimple_bb (*flag_def
) != gimple_bb (phi
)
343 || !find_matching_predicate_in_rest_chains (pred
, preds
))
346 /* Return if any "flag_var comp const" predicate is found. */
349 *boundary_cst
= cond_rhs
;
352 /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */
353 else if (vrinfo_code
== ERROR_MARK
)
356 vrinfo_def
= *flag_def
;
357 vrinfo_cst
= cond_rhs
;
360 /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */
361 if (vrinfo_code
!= ERROR_MARK
)
363 *flag_def
= vrinfo_def
;
364 *boundary_cst
= vrinfo_cst
;
369 /* Return true if all interesting opnds are pruned, false otherwise.
370 PHI is the phi node with interesting operands, OPNDS is the bitmap
371 of the interesting operand positions, FLAG_DEF is the statement
372 defining the flag guarding the use of the PHI output, BOUNDARY_CST
373 is the const value used in the predicate associated with the flag,
374 CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
375 is the pointer set of phis visited, and VISITED_FLAG_PHIS is
376 the pointer to the pointer set of flag definitions that are also
382 flag_1 = phi <0, 1> // (1)
383 var_1 = phi <undef, some_val>
387 flag_2 = phi <0, flag_1, flag_1> // (2)
388 var_2 = phi <undef, var_1, var_1>
395 Because some flag arg in (1) is not constant, if we do not look into
396 the flag phis recursively, it is conservatively treated as unknown and
397 var_1 is thought to flow into use at (3). Since var_1 is potentially
398 uninitialized a false warning will be emitted.
399 Checking recursively into (1), the compiler can find out that only
400 some_val (which is defined) can flow into (3) which is OK. */
403 uninit_analysis::prune_phi_opnds (gphi
*phi
, unsigned opnds
, gphi
*flag_def
,
404 tree boundary_cst
, tree_code cmp_code
,
405 hash_set
<gphi
*> *visited_phis
,
406 bitmap
*visited_flag_phis
)
408 /* The Boolean predicate guarding the PHI definition. Initialized
409 lazily from PHI in the first call to is_use_guarded() and cached
410 for subsequent iterations. */
411 uninit_analysis
def_preds (m_eval
);
413 unsigned n
= MIN (m_eval
.max_phi_args
, gimple_phi_num_args (flag_def
));
414 for (unsigned i
= 0; i
< n
; i
++)
416 if (!MASK_TEST_BIT (opnds
, i
))
419 tree flag_arg
= gimple_phi_arg_def (flag_def
, i
);
420 if (!is_gimple_constant (flag_arg
))
422 if (TREE_CODE (flag_arg
) != SSA_NAME
)
425 gphi
*flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
429 tree phi_arg
= gimple_phi_arg_def (phi
, i
);
430 if (TREE_CODE (phi_arg
) != SSA_NAME
)
433 gphi
*phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
437 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
440 if (!*visited_flag_phis
)
441 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
443 tree phi_result
= gimple_phi_result (flag_arg_def
);
444 if (bitmap_bit_p (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
)))
447 bitmap_set_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
449 /* Now recursively try to prune the interesting phi args. */
450 unsigned opnds_arg_phi
= m_eval
.phi_arg_set (phi_arg_def
);
451 if (!prune_phi_opnds (phi_arg_def
, opnds_arg_phi
, flag_arg_def
,
452 boundary_cst
, cmp_code
, visited_phis
,
456 bitmap_clear_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
460 /* Now check if the constant is in the guarded range. */
461 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
463 /* Now that we know that this undefined edge is not pruned.
464 If the operand is defined by another phi, we can further
465 prune the incoming edges of that phi by checking
466 the predicates of this operands. */
468 tree opnd
= gimple_phi_arg_def (phi
, i
);
469 gimple
*opnd_def
= SSA_NAME_DEF_STMT (opnd
);
470 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
472 unsigned opnds2
= m_eval
.phi_arg_set (opnd_def_phi
);
473 if (!MASK_EMPTY (opnds2
))
475 edge opnd_edge
= gimple_phi_arg_edge (phi
, i
);
476 if (def_preds
.is_use_guarded (phi
, opnd_edge
->src
,
477 opnd_def_phi
, opnds2
,
490 /* Recursively compute the set PHI's incoming edges with "uninteresting"
491 operands of a phi chain, i.e., those for which EVAL returns false.
492 CD_ROOT is the control dependence root from which edges are collected
493 up the CFG nodes that it's dominated by. *EDGES holds the result, and
494 VISITED is used for detecting cycles. */
497 uninit_analysis::collect_phi_def_edges (gphi
*phi
, basic_block cd_root
,
499 hash_set
<gimple
*> *visited
)
501 if (visited
->elements () == 0
502 && DEBUG_PREDICATE_ANALYZER
505 fprintf (dump_file
, "%s for cd_root %u and ",
506 __func__
, cd_root
->index
);
507 print_gimple_stmt (dump_file
, phi
, 0);
511 if (visited
->add (phi
))
514 unsigned n
= gimple_phi_num_args (phi
);
515 unsigned opnds_arg_phi
= m_eval
.phi_arg_set (phi
);
516 for (unsigned i
= 0; i
< n
; i
++)
518 if (!MASK_TEST_BIT (opnds_arg_phi
, i
))
520 /* Add the edge for a not maybe-undefined edge value. */
521 edge opnd_edge
= gimple_phi_arg_edge (phi
, i
);
522 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
525 "\tFound def edge %i -> %i for cd_root %i "
526 "and operand %u of: ",
527 opnd_edge
->src
->index
, opnd_edge
->dest
->index
,
529 print_gimple_stmt (dump_file
, phi
, 0);
531 edges
->safe_push (opnd_edge
);
536 tree opnd
= gimple_phi_arg_def (phi
, i
);
537 if (TREE_CODE (opnd
) == SSA_NAME
)
539 gimple
*def
= SSA_NAME_DEF_STMT (opnd
);
540 if (gimple_code (def
) == GIMPLE_PHI
541 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (def
), cd_root
))
542 /* Process PHI defs of maybe-undefined edge values
544 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
,
551 /* Return a bitset of all PHI arguments or zero if there are too many. */
554 uninit_analysis::func_t::phi_arg_set (gphi
*phi
)
556 unsigned n
= gimple_phi_num_args (phi
);
558 if (max_phi_args
< n
)
561 /* Set the least significant N bits. */
562 return (1U << n
) - 1;
565 /* Determine if the predicate set of the use does not overlap with that
566 of the interesting paths. The most common senario of guarded use is
571 x = ...; // set x to valid
578 use (x); // use when x is valid
580 The real world examples are usually more complicated, but similar
581 and usually result from inlining:
583 bool init_func (int * x)
587 *x = ...; // set *x to valid
599 use (x); // use when x is valid
602 Another possible use scenario is in the following trivial example:
614 Predicate analysis needs to compute the composite predicate:
616 1) 'x' use predicate: (n > 0) .AND. (m < 2)
617 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
618 (the predicate chain for phi operand defs can be computed
619 starting from a bb that is control equivalent to the phi's
620 bb and is dominating the operand def.)
622 and check overlapping:
623 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
626 This implementation provides a framework that can handle different
627 scenarios. (Note that many simple cases are handled properly without
628 the predicate analysis if jump threading eliminates the merge point
629 thus makes path-sensitive analysis unnecessary.)
631 PHI is the phi node whose incoming (undefined) paths need to be
632 pruned, and OPNDS is the bitmap holding interesting operand
633 positions. VISITED is the pointer set of phi stmts being
637 uninit_analysis::overlap (gphi
*phi
, unsigned opnds
, hash_set
<gphi
*> *visited
,
638 const predicate
&use_preds
)
640 gimple
*flag_def
= NULL
;
641 tree boundary_cst
= NULL_TREE
;
642 bitmap visited_flag_phis
= NULL
;
644 /* Find within the common prefix of multiple predicate chains
645 a predicate that is a comparison of a flag variable against
647 tree_code cmp_code
= find_var_cmp_const (use_preds
.chain (), phi
, &flag_def
,
649 if (cmp_code
== ERROR_MARK
)
652 /* Now check all the uninit incoming edges have a constant flag
653 value that is in conflict with the use guard/predicate. */
654 gphi
*phi_def
= as_a
<gphi
*> (flag_def
);
655 bool all_pruned
= prune_phi_opnds (phi
, opnds
, phi_def
, boundary_cst
,
659 if (visited_flag_phis
)
660 BITMAP_FREE (visited_flag_phis
);
665 /* Return true if two predicates PRED1 and X2 are equivalent. Assume
666 the expressions have already properly re-associated. */
669 pred_equal_p (const pred_info
&pred1
, const pred_info
&pred2
)
671 if (!operand_equal_p (pred1
.pred_lhs
, pred2
.pred_lhs
, 0)
672 || !operand_equal_p (pred1
.pred_rhs
, pred2
.pred_rhs
, 0))
675 tree_code c1
= pred1
.cond_code
, c2
;
676 if (pred1
.invert
!= pred2
.invert
677 && TREE_CODE_CLASS (pred2
.cond_code
) == tcc_comparison
)
678 c2
= invert_tree_comparison (pred2
.cond_code
, false);
680 c2
= pred2
.cond_code
;
685 /* Return true if PRED tests inequality (i.e., X != Y). */
688 is_neq_relop_p (const pred_info
&pred
)
691 return ((pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
692 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
));
695 /* Returns true if PRED is of the form X != 0. */
698 is_neq_zero_form_p (const pred_info
&pred
)
700 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
701 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
706 /* Return true if PRED is equivalent to X != 0. */
709 pred_expr_equal_p (const pred_info
&pred
, tree expr
)
711 if (!is_neq_zero_form_p (pred
))
714 return operand_equal_p (pred
.pred_lhs
, expr
, 0);
717 /* Return true if VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can
718 be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
719 the like), or BIT_AND_EXPR. EXACT_P is only meaningful for the latter.
720 Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
721 For other values of CMPC, EXACT_P is ignored. */
724 value_sat_pred_p (tree val
, tree boundary
, tree_code cmpc
,
725 bool exact_p
= false)
727 if (cmpc
!= BIT_AND_EXPR
)
728 return is_value_included_in (val
, boundary
, cmpc
);
730 wide_int andw
= wi::to_wide (val
) & wi::to_wide (boundary
);
732 return andw
== wi::to_wide (val
);
734 return andw
.to_uhwi ();
737 /* Return true if the domain of single predicate expression PRED1
738 is a subset of that of PRED2, and false if it cannot be proved. */
741 subset_of (const pred_info
&pred1
, const pred_info
&pred2
)
743 if (pred_equal_p (pred1
, pred2
))
746 if ((TREE_CODE (pred1
.pred_rhs
) != INTEGER_CST
)
747 || (TREE_CODE (pred2
.pred_rhs
) != INTEGER_CST
))
750 if (!operand_equal_p (pred1
.pred_lhs
, pred2
.pred_lhs
, 0))
753 tree_code code1
= pred1
.cond_code
;
755 code1
= invert_tree_comparison (code1
, false);
756 tree_code code2
= pred2
.cond_code
;
758 code2
= invert_tree_comparison (code2
, false);
760 if (code2
== NE_EXPR
&& code1
== NE_EXPR
)
763 if (code2
== NE_EXPR
)
764 return !value_sat_pred_p (pred2
.pred_rhs
, pred1
.pred_rhs
, code1
);
766 if (code1
== EQ_EXPR
)
767 return value_sat_pred_p (pred1
.pred_rhs
, pred2
.pred_rhs
, code2
);
770 return value_sat_pred_p (pred1
.pred_rhs
, pred2
.pred_rhs
, code2
,
771 code1
== BIT_AND_EXPR
);
776 /* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
777 Return false if it cannot be proven so. */
780 subset_of (const pred_chain
&chain1
, const pred_chain
&chain2
)
782 unsigned np1
= chain1
.length ();
783 unsigned np2
= chain2
.length ();
784 for (unsigned i2
= 0; i2
< np2
; i2
++)
787 const pred_info
&info2
= chain2
[i2
];
788 for (unsigned i1
= 0; i1
< np1
; i1
++)
790 const pred_info
&info1
= chain1
[i1
];
791 if (subset_of (info1
, info2
))
803 /* Return true if the domain defined by the predicate chain PREDS is
804 a subset of the domain of *THIS. Return false if PREDS's domain
805 is not a subset of any of the sub-domains of *THIS (corresponding
806 to each individual chains in it), even though it may be still be
807 a subset of whole domain of *THIS which is the union (ORed) of all
808 its subdomains. In other words, the result is conservative. */
811 predicate::includes (const pred_chain
&chain
) const
813 for (unsigned i
= 0; i
< m_preds
.length (); i
++)
814 if (subset_of (chain
, m_preds
[i
]))
820 /* Return true if the domain defined by *THIS is a superset of PREDS's
822 Avoid building generic trees (and rely on the folding capability
823 of the compiler), and instead perform brute force comparison of
824 individual predicate chains (this won't be a computationally costly
825 since the chains are pretty short). Returning false does not
826 necessarily mean *THIS is not a superset of *PREDS, only that
827 it need not be since the analysis cannot prove it. */
830 predicate::superset_of (const predicate
&preds
) const
832 for (unsigned i
= 0; i
< preds
.m_preds
.length (); i
++)
833 if (!includes (preds
.m_preds
[i
]))
839 /* Create a predicate of the form OP != 0 and push it the work list CHAIN. */
842 push_to_worklist (tree op
, pred_chain
*chain
, hash_set
<tree
> *mark_set
)
844 if (mark_set
->contains (op
))
849 arg_pred
.pred_lhs
= op
;
850 arg_pred
.pred_rhs
= integer_zero_node
;
851 arg_pred
.cond_code
= NE_EXPR
;
852 arg_pred
.invert
= false;
853 chain
->safe_push (arg_pred
);
856 /* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
860 get_pred_info_from_cmp (const gimple
*cmp_assign
)
863 pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
864 pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
865 pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
870 /* If PHI is a degenerate phi with all operands having the same value (relop)
871 update *PRED to that value and return true. Otherwise return false. */
874 is_degenerate_phi (gimple
*phi
, pred_info
*pred
)
876 tree op0
= gimple_phi_arg_def (phi
, 0);
878 if (TREE_CODE (op0
) != SSA_NAME
)
881 gimple
*def0
= SSA_NAME_DEF_STMT (op0
);
882 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
885 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
)) != tcc_comparison
)
888 pred_info pred0
= get_pred_info_from_cmp (def0
);
890 unsigned n
= gimple_phi_num_args (phi
);
891 for (unsigned i
= 1; i
< n
; ++i
)
893 tree op
= gimple_phi_arg_def (phi
, i
);
894 if (TREE_CODE (op
) != SSA_NAME
)
897 gimple
*def
= SSA_NAME_DEF_STMT (op
);
898 if (gimple_code (def
) != GIMPLE_ASSIGN
)
901 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) != tcc_comparison
)
904 pred_info pred
= get_pred_info_from_cmp (def
);
905 if (!pred_equal_p (pred
, pred0
))
913 /* If compute_control_dep_chain bailed out due to limits this routine
914 tries to build a partial sparse path using dominators. Returns
915 path edges whose predicates are always true when reaching E. */
918 simple_control_dep_chain (vec
<edge
>& chain
, basic_block from
, basic_block to
)
920 if (!dominated_by_p (CDI_DOMINATORS
, to
, from
))
923 basic_block src
= to
;
925 && chain
.length () <= MAX_CHAIN_LEN
)
927 basic_block dest
= src
;
928 src
= get_immediate_dominator (CDI_DOMINATORS
, src
);
930 if (single_pred_p (dest
)
931 && (pred_e
= find_edge (src
, dest
)))
932 chain
.safe_push (pred_e
);
936 /* Perform a DFS walk on predecessor edges to mark the region denoted
937 by the EXIT_SRC block and DOM which dominates EXIT_SRC, including DOM.
938 Blocks in the region are marked with FLAG and added to BBS. BBS is
939 filled up to its capacity only after which the walk is terminated
940 and false is returned. If the whole region was marked, true is returned. */
943 dfs_mark_dominating_region (basic_block exit_src
, basic_block dom
, int flag
,
944 vec
<basic_block
> &bbs
)
946 if (exit_src
== dom
|| exit_src
->flags
& flag
)
950 bbs
.quick_push (exit_src
);
951 exit_src
->flags
|= flag
;
952 auto_vec
<edge_iterator
, 20> stack (bbs
.allocated () - bbs
.length () + 1);
953 stack
.quick_push (ei_start (exit_src
->preds
));
954 while (!stack
.is_empty ())
956 /* Look at the edge on the top of the stack. */
957 edge_iterator ei
= stack
.last ();
958 basic_block src
= ei_edge (ei
)->src
;
960 /* Check if the edge source has been visited yet. */
961 if (!(src
->flags
& flag
))
963 /* Mark the source if there's still space. If not, return early. */
967 bbs
.quick_push (src
);
969 /* Queue its predecessors if we didn't reach DOM. */
970 if (src
!= dom
&& EDGE_COUNT (src
->preds
) > 0)
971 stack
.quick_push (ei_start (src
->preds
));
975 if (!ei_one_before_end_p (ei
))
976 ei_next (&stack
.last ());
985 compute_control_dep_chain (basic_block dom_bb
, const_basic_block dep_bb
,
986 vec
<edge
> cd_chains
[], unsigned *num_chains
,
987 vec
<edge
> &cur_cd_chain
, unsigned *num_calls
,
988 unsigned in_region
, unsigned depth
,
991 /* Helper for compute_control_dep_chain that walks the post-dominator
992 chain from CD_BB up unto TARGET_BB looking for paths to DEP_BB. */
995 compute_control_dep_chain_pdom (basic_block cd_bb
, const_basic_block dep_bb
,
996 basic_block target_bb
,
997 vec
<edge
> cd_chains
[], unsigned *num_chains
,
998 vec
<edge
> &cur_cd_chain
, unsigned *num_calls
,
999 unsigned in_region
, unsigned depth
,
1002 bool found_cd_chain
= false;
1003 while (cd_bb
!= target_bb
)
1005 if (cd_bb
== dep_bb
)
1007 /* Found a direct control dependence. */
1008 if (*num_chains
< MAX_NUM_CHAINS
)
1010 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1011 fprintf (dump_file
, "%*s pushing { %s }\n",
1012 depth
, "", format_edge_vec (cur_cd_chain
).c_str ());
1013 cd_chains
[*num_chains
] = cur_cd_chain
.copy ();
1016 found_cd_chain
= true;
1017 /* Check path from next edge. */
1021 /* If the dominating region has been marked avoid walking outside. */
1022 if (in_region
!= 0 && !(cd_bb
->flags
& in_region
))
1025 /* Count the number of steps we perform to limit compile-time.
1026 This should cover both recursion and the post-dominator walk. */
1027 if (*num_calls
> (unsigned)param_uninit_control_dep_attempts
)
1030 fprintf (dump_file
, "param_uninit_control_dep_attempts "
1031 "exceeded: %u\n", *num_calls
);
1032 *complete_p
= false;
1037 /* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
1038 if (!single_succ_p (cd_bb
)
1039 && compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
1040 num_chains
, cur_cd_chain
,
1041 num_calls
, in_region
, depth
+ 1,
1044 found_cd_chain
= true;
1048 /* The post-dominator walk will reach a backedge only
1049 from a forwarder, otherwise it should choose to exit
1051 if (single_succ_p (cd_bb
)
1052 && single_succ_edge (cd_bb
)->flags
& EDGE_DFS_BACK
)
1054 basic_block prev_cd_bb
= cd_bb
;
1055 cd_bb
= get_immediate_dominator (CDI_POST_DOMINATORS
, cd_bb
);
1056 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1058 /* Pick up conditions toward the post dominator such like
1059 loop exit conditions. See gcc.dg/uninit-pred-11.c and
1060 gcc.dg/unninit-pred-12.c and PR106754. */
1061 if (single_pred_p (cd_bb
))
1063 edge e2
= find_edge (prev_cd_bb
, cd_bb
);
1065 cur_cd_chain
.safe_push (e2
);
1068 return found_cd_chain
;
1072 /* Recursively compute the control dependence chains (paths of edges)
1073 from the dependent basic block, DEP_BB, up to the dominating basic
1074 block, DOM_BB (the head node of a chain should be dominated by it),
1075 storing them in the CD_CHAINS array.
1076 CUR_CD_CHAIN is the current chain being computed.
1077 *NUM_CHAINS is total number of chains in the CD_CHAINS array.
1078 *NUM_CALLS is the number of recursive calls to control unbounded
1080 Return true if the information is successfully computed, false if
1081 there is no control dependence or not computed.
1082 *COMPLETE_P is set to false if we stopped walking due to limits.
1083 In this case there might be missing chains. */
1086 compute_control_dep_chain (basic_block dom_bb
, const_basic_block dep_bb
,
1087 vec
<edge
> cd_chains
[], unsigned *num_chains
,
1088 vec
<edge
> &cur_cd_chain
, unsigned *num_calls
,
1089 unsigned in_region
, unsigned depth
,
1092 /* In our recursive calls this doesn't happen. */
1093 if (single_succ_p (dom_bb
))
1096 /* FIXME: Use a set instead. */
1097 unsigned cur_chain_len
= cur_cd_chain
.length ();
1098 if (cur_chain_len
> MAX_CHAIN_LEN
)
1101 fprintf (dump_file
, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len
);
1103 *complete_p
= false;
1107 if (cur_chain_len
> 5)
1110 fprintf (dump_file
, "chain length exceeds 5: %u\n", cur_chain_len
);
1113 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1115 "%*s%s (dom_bb = %u, dep_bb = %u, ..., "
1116 "cur_cd_chain = { %s }, ...)\n",
1117 depth
, "", __func__
, dom_bb
->index
, dep_bb
->index
,
1118 format_edge_vec (cur_cd_chain
).c_str ());
1120 bool found_cd_chain
= false;
1122 /* Iterate over DOM_BB's successors. */
1125 FOR_EACH_EDGE (e
, ei
, dom_bb
->succs
)
1127 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
| EDGE_DFS_BACK
))
1130 basic_block cd_bb
= e
->dest
;
1131 unsigned pop_mark
= cur_cd_chain
.length ();
1132 cur_cd_chain
.safe_push (e
);
1133 basic_block target_bb
1134 = get_immediate_dominator (CDI_POST_DOMINATORS
, dom_bb
);
1135 /* Walk the post-dominator chain up to the CFG merge. */
1137 |= compute_control_dep_chain_pdom (cd_bb
, dep_bb
, target_bb
,
1138 cd_chains
, num_chains
,
1139 cur_cd_chain
, num_calls
,
1140 in_region
, depth
, complete_p
);
1141 cur_cd_chain
.truncate (pop_mark
);
1142 gcc_assert (cur_cd_chain
.length () == cur_chain_len
);
1145 gcc_assert (cur_cd_chain
.length () == cur_chain_len
);
1146 return found_cd_chain
;
1149 /* Wrapper around the compute_control_dep_chain worker above. Returns
1150 true when the collected set of chains in CD_CHAINS is complete. */
1153 compute_control_dep_chain (basic_block dom_bb
, const_basic_block dep_bb
,
1154 vec
<edge
> cd_chains
[], unsigned *num_chains
,
1155 unsigned in_region
= 0)
1157 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_cd_chain
;
1158 unsigned num_calls
= 0;
1160 bool complete_p
= true;
1161 /* Walk the post-dominator chain. */
1162 compute_control_dep_chain_pdom (dom_bb
, dep_bb
, NULL
, cd_chains
,
1163 num_chains
, cur_cd_chain
, &num_calls
,
1164 in_region
, depth
, &complete_p
);
1168 /* Implemented simplifications:
1170 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1171 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1172 3) X OR (!X AND Y) is equivalent to (X OR Y);
1173 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1175 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1178 PREDS is the predicate chains, and N is the number of chains. */
1180 /* Implement rule 1 above. PREDS is the AND predicate to simplify
1184 simplify_1 (pred_chain
&chain
)
1186 bool simplified
= false;
1187 pred_chain s_chain
= vNULL
;
1189 unsigned n
= chain
.length ();
1190 for (unsigned i
= 0; i
< n
; i
++)
1192 pred_info
&a_pred
= chain
[i
];
1194 if (!a_pred
.pred_lhs
1195 || !is_neq_zero_form_p (a_pred
))
1198 gimple
*def_stmt
= SSA_NAME_DEF_STMT (a_pred
.pred_lhs
);
1199 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1202 if (gimple_assign_rhs_code (def_stmt
) != BIT_IOR_EXPR
)
1205 for (unsigned j
= 0; j
< n
; j
++)
1207 const pred_info
&b_pred
= chain
[j
];
1209 if (!b_pred
.pred_lhs
1210 || !is_neq_zero_form_p (b_pred
))
1213 if (pred_expr_equal_p (b_pred
, gimple_assign_rhs1 (def_stmt
))
1214 || pred_expr_equal_p (b_pred
, gimple_assign_rhs2 (def_stmt
)))
1216 /* Mark A_PRED for removal from PREDS. */
1217 a_pred
.pred_lhs
= NULL
;
1218 a_pred
.pred_rhs
= NULL
;
1228 /* Remove predicates marked above. */
1229 for (unsigned i
= 0; i
< n
; i
++)
1231 pred_info
&a_pred
= chain
[i
];
1232 if (!a_pred
.pred_lhs
)
1234 s_chain
.safe_push (a_pred
);
1241 /* Implements rule 2 for the OR predicate PREDS:
1243 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1246 predicate::simplify_2 ()
1248 bool simplified
= false;
1250 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1251 (X AND Y) OR (X AND !Y) is equivalent to X. */
1253 unsigned n
= m_preds
.length ();
1254 for (unsigned i
= 0; i
< n
; i
++)
1256 pred_chain
&a_chain
= m_preds
[i
];
1257 if (a_chain
.length () != 2)
1260 /* Create copies since the chain may be released below before
1261 the copy is added to the other chain. */
1262 const pred_info x
= a_chain
[0];
1263 const pred_info y
= a_chain
[1];
1265 for (unsigned j
= 0; j
< n
; j
++)
1270 pred_chain
&b_chain
= m_preds
[j
];
1271 if (b_chain
.length () != 2)
1274 const pred_info
&x2
= b_chain
[0];
1275 const pred_info
&y2
= b_chain
[1];
1277 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1282 b_chain
.safe_push (x
);
1286 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1291 b_chain
.safe_push (y
);
1297 /* Now clean up the chain. */
1300 pred_chain_union s_preds
= vNULL
;
1301 for (unsigned i
= 0; i
< n
; i
++)
1303 if (m_preds
[i
].is_empty ())
1305 s_preds
.safe_push (m_preds
[i
]);
1315 /* Implement rule 3 for the OR predicate PREDS:
1317 3) x OR (!x AND y) is equivalent to x OR y. */
1320 predicate::simplify_3 ()
1322 /* Now iteratively simplify X OR (!X AND Z ..)
1323 into X OR (Z ...). */
1325 unsigned n
= m_preds
.length ();
1329 bool simplified
= false;
1330 for (unsigned i
= 0; i
< n
; i
++)
1332 const pred_chain
&a_chain
= m_preds
[i
];
1334 if (a_chain
.length () != 1)
1337 const pred_info
&x
= a_chain
[0];
1338 for (unsigned j
= 0; j
< n
; j
++)
1343 pred_chain b_chain
= m_preds
[j
];
1344 if (b_chain
.length () < 2)
1347 for (unsigned k
= 0; k
< b_chain
.length (); k
++)
1349 const pred_info
&x2
= b_chain
[k
];
1350 if (pred_neg_p (x
, x2
))
1352 b_chain
.unordered_remove (k
);
1362 /* Implement rule 4 for the OR predicate PREDS:
1364 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1365 (x != 0 ANd y != 0). */
1368 predicate::simplify_4 ()
1370 bool simplified
= false;
1371 pred_chain_union s_preds
= vNULL
;
1373 unsigned n
= m_preds
.length ();
1374 for (unsigned i
= 0; i
< n
; i
++)
1376 pred_chain a_chain
= m_preds
[i
];
1377 if (a_chain
.length () != 1)
1380 const pred_info
&z
= a_chain
[0];
1381 if (!is_neq_zero_form_p (z
))
1384 gimple
*def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1385 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1388 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1391 for (unsigned j
= 0; j
< n
; j
++)
1396 pred_chain b_chain
= m_preds
[j
];
1397 if (b_chain
.length () != 2)
1400 const pred_info
&x2
= b_chain
[0];
1401 const pred_info
&y2
= b_chain
[1];
1402 if (!is_neq_zero_form_p (x2
) || !is_neq_zero_form_p (y2
))
1405 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1406 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1407 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1408 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1417 /* Now clean up the chain. */
1420 for (unsigned i
= 0; i
< n
; i
++)
1422 if (m_preds
[i
].is_empty ())
1424 s_preds
.safe_push (m_preds
[i
]);
1435 /* Simplify predicates in *THIS. */
1438 predicate::simplify (gimple
*use_or_def
, bool is_use
)
1440 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1442 fprintf (dump_file
, "Before simplication ");
1443 dump (dump_file
, use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
1446 unsigned n
= m_preds
.length ();
1447 for (unsigned i
= 0; i
< n
; i
++)
1448 ::simplify_1 (m_preds
[i
]);
1469 /* Attempt to normalize predicate chains by following UD chains by
1470 building up a big tree of either IOR operations or AND operations,
1471 and converting the IOR tree into a pred_chain_union or the BIT_AND
1472 tree into a pred_chain.
1482 then _t != 0 will be normalized into a pred_chain_union
1484 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1494 then _t != 0 will be normalized into a pred_chain:
1495 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1498 /* Normalize predicate PRED:
1499 1) if PRED can no longer be normalized, append it to *THIS.
1500 2) otherwise if PRED is of the form x != 0, follow x's definition
1501 and put normalized predicates into WORK_LIST. */
1504 predicate::normalize (pred_chain
*norm_chain
,
1506 tree_code and_or_code
,
1507 pred_chain
*work_list
,
1508 hash_set
<tree
> *mark_set
)
1510 if (!is_neq_zero_form_p (pred
))
1512 if (and_or_code
== BIT_IOR_EXPR
)
1515 norm_chain
->safe_push (pred
);
1519 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1521 if (gimple_code (def_stmt
) == GIMPLE_PHI
1522 && is_degenerate_phi (def_stmt
, &pred
))
1523 /* PRED has been modified above. */
1524 work_list
->safe_push (pred
);
1525 else if (gimple_code (def_stmt
) == GIMPLE_PHI
&& and_or_code
== BIT_IOR_EXPR
)
1527 unsigned n
= gimple_phi_num_args (def_stmt
);
1529 /* Punt for a nonzero constant. The predicate should be one guarding
1531 for (unsigned i
= 0; i
< n
; ++i
)
1533 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1534 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1541 for (unsigned i
= 0; i
< n
; ++i
)
1543 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1544 if (integer_zerop (op
))
1547 push_to_worklist (op
, work_list
, mark_set
);
1550 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1552 if (and_or_code
== BIT_IOR_EXPR
)
1555 norm_chain
->safe_push (pred
);
1557 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
1559 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
1560 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
1562 /* But treat x & 3 as a condition. */
1563 if (and_or_code
== BIT_AND_EXPR
)
1566 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
1567 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
1568 n_pred
.cond_code
= and_or_code
;
1569 n_pred
.invert
= false;
1570 norm_chain
->safe_push (n_pred
);
1575 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
1576 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
1579 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
1582 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
1583 if (and_or_code
== BIT_IOR_EXPR
)
1586 norm_chain
->safe_push (n_pred
);
1590 if (and_or_code
== BIT_IOR_EXPR
)
1593 norm_chain
->safe_push (pred
);
1597 /* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */
1600 predicate::normalize (const pred_info
&pred
)
1602 if (!is_neq_zero_form_p (pred
))
1608 tree_code and_or_code
= ERROR_MARK
;
1610 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1611 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
1612 and_or_code
= gimple_assign_rhs_code (def_stmt
);
1613 if (and_or_code
!= BIT_IOR_EXPR
&& and_or_code
!= BIT_AND_EXPR
)
1615 if (TREE_CODE_CLASS (and_or_code
) == tcc_comparison
)
1617 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
1626 pred_chain norm_chain
= vNULL
;
1627 pred_chain work_list
= vNULL
;
1628 work_list
.safe_push (pred
);
1629 hash_set
<tree
> mark_set
;
1631 while (!work_list
.is_empty ())
1633 pred_info a_pred
= work_list
.pop ();
1634 normalize (&norm_chain
, a_pred
, and_or_code
, &work_list
, &mark_set
);
1637 if (and_or_code
== BIT_AND_EXPR
)
1638 m_preds
.safe_push (norm_chain
);
1640 work_list
.release ();
1643 /* Normalize a single predicate PRED_CHAIN and append it to *THIS. */
1646 predicate::normalize (const pred_chain
&chain
)
1648 pred_chain work_list
= vNULL
;
1649 hash_set
<tree
> mark_set
;
1650 for (unsigned i
= 0; i
< chain
.length (); i
++)
1652 work_list
.safe_push (chain
[i
]);
1653 mark_set
.add (chain
[i
].pred_lhs
);
1656 /* Normalized chain of predicates built up below. */
1657 pred_chain norm_chain
= vNULL
;
1658 while (!work_list
.is_empty ())
1660 pred_info pi
= work_list
.pop ();
1662 /* The predicate object is not modified here, only NORM_CHAIN and
1663 WORK_LIST are appended to. */
1664 pred
.normalize (&norm_chain
, pi
, BIT_AND_EXPR
, &work_list
, &mark_set
);
1667 m_preds
.safe_push (norm_chain
);
1668 work_list
.release ();
1671 /* Normalize predicate chains in THIS. */
1674 predicate::normalize (gimple
*use_or_def
, bool is_use
)
1676 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1678 fprintf (dump_file
, "Before normalization ");
1679 dump (dump_file
, use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
1682 predicate norm_preds
;
1683 for (unsigned i
= 0; i
< m_preds
.length (); i
++)
1685 if (m_preds
[i
].length () != 1)
1686 norm_preds
.normalize (m_preds
[i
]);
1688 norm_preds
.normalize (m_preds
[i
][0]);
1695 fprintf (dump_file
, "After normalization ");
1696 dump (dump_file
, use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
1700 /* Convert the chains of control dependence edges into a set of predicates.
1701 A control dependence chain is represented by a vector edges. DEP_CHAINS
1702 points to an array of NUM_CHAINS dependence chains. One edge in
1703 a dependence chain is mapped to predicate expression represented by
1704 pred_info type. One dependence chain is converted to a composite
1705 predicate that is the result of AND operation of pred_info mapped to
1706 each edge. A composite predicate is represented by a vector of
1707 pred_info. Sets M_PREDS to the resulting composite predicates. */
1710 predicate::init_from_control_deps (const vec
<edge
> *dep_chains
,
1711 unsigned num_chains
, bool is_use
)
1713 gcc_assert (is_empty ());
1715 if (num_chains
== 0)
1718 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1719 fprintf (dump_file
, "init_from_control_deps [%s] {%s}:\n",
1720 is_use
? "USE" : "DEF",
1721 format_edge_vecs (dep_chains
, num_chains
).c_str ());
1723 /* Convert the control dependency chain into a set of predicates. */
1724 m_preds
.reserve (num_chains
);
1726 for (unsigned i
= 0; i
< num_chains
; i
++)
1728 /* One path through the CFG represents a logical conjunction
1729 of the predicates. */
1730 const vec
<edge
> &path
= dep_chains
[i
];
1732 bool has_valid_pred
= false;
1733 /* The chain of predicates guarding the definition along this path. */
1734 pred_chain t_chain
{ };
1735 for (unsigned j
= 0; j
< path
.length (); j
++)
1738 basic_block guard_bb
= e
->src
;
1740 gcc_assert (!empty_block_p (guard_bb
) && !single_succ_p (guard_bb
));
1742 /* Skip this edge if it is bypassing an abort - when the
1743 condition is not satisfied we are neither reaching the
1744 definition nor the use so it isn't meaningful. Note if
1745 we are processing the use predicate the condition is
1746 meaningful. See PR65244. */
1747 if (!is_use
&& EDGE_COUNT (e
->src
->succs
) == 2)
1753 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
1755 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
1763 has_valid_pred
= true;
1767 /* Get the conditional controlling the bb exit edge. */
1768 gimple
*cond_stmt
= last_stmt (guard_bb
);
1769 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
1771 /* The true edge corresponds to the uninteresting condition.
1772 Add the negated predicate(s) for the edge to record
1773 the interesting condition. */
1775 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
1776 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
1777 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
1778 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
1780 t_chain
.safe_push (one_pred
);
1782 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1784 fprintf (dump_file
, "%d -> %d: one_pred = ",
1785 e
->src
->index
, e
->dest
->index
);
1786 dump_pred_info (dump_file
, one_pred
);
1787 fputc ('\n', dump_file
);
1790 has_valid_pred
= true;
1792 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
1794 /* Find the case label, but avoid quadratic behavior. */
1795 tree l
= get_cases_for_edge (e
, gs
);
1796 /* If more than one label reaches this block or the case
1797 label doesn't have a contiguous range of values (like the
1798 default one) fail. */
1799 if (!l
|| CASE_CHAIN (l
) || !CASE_LOW (l
))
1800 has_valid_pred
= false;
1801 else if (!CASE_HIGH (l
)
1802 || operand_equal_p (CASE_LOW (l
), CASE_HIGH (l
)))
1805 one_pred
.pred_lhs
= gimple_switch_index (gs
);
1806 one_pred
.pred_rhs
= CASE_LOW (l
);
1807 one_pred
.cond_code
= EQ_EXPR
;
1808 one_pred
.invert
= false;
1809 t_chain
.safe_push (one_pred
);
1810 has_valid_pred
= true;
1814 /* Support a case label with a range with
1815 two predicates. We're overcommitting on
1816 the MAX_CHAIN_LEN budget by at most a factor
1819 one_pred
.pred_lhs
= gimple_switch_index (gs
);
1820 one_pred
.pred_rhs
= CASE_LOW (l
);
1821 one_pred
.cond_code
= GE_EXPR
;
1822 one_pred
.invert
= false;
1823 t_chain
.safe_push (one_pred
);
1824 one_pred
.pred_rhs
= CASE_HIGH (l
);
1825 one_pred
.cond_code
= LE_EXPR
;
1826 t_chain
.safe_push (one_pred
);
1827 has_valid_pred
= true;
1830 else if (stmt_can_throw_internal (cfun
, cond_stmt
)
1831 && !(e
->flags
& EDGE_EH
))
1832 /* Ignore the exceptional control flow and proceed as if
1833 E were a fallthru without a controlling predicate for
1834 both the USE (valid) and DEF (questionable) case. */
1835 has_valid_pred
= true;
1837 has_valid_pred
= false;
1839 /* For USE predicates we can drop components of the
1841 if (!has_valid_pred
&& !is_use
)
1845 /* For DEF predicates we have to drop components of the OR chain
1847 if (!has_valid_pred
&& !is_use
)
1853 /* When we add || 1 simply prune the chain and return. */
1854 if (t_chain
.is_empty ())
1857 for (auto chain
: m_preds
)
1859 m_preds
.truncate (0);
1863 m_preds
.quick_push (t_chain
);
1866 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1870 /* Store a PRED in *THIS. */
1873 predicate::push_pred (const pred_info
&pred
)
1875 pred_chain chain
= vNULL
;
1876 chain
.safe_push (pred
);
1877 m_preds
.safe_push (chain
);
1880 /* Dump predicates in *THIS to F. */
1883 predicate::dump (FILE *f
) const
1885 unsigned np
= m_preds
.length ();
1888 fprintf (f
, "\tTRUE (empty)\n");
1892 for (unsigned i
= 0; i
< np
; i
++)
1895 fprintf (f
, "\tOR (");
1898 dump_pred_chain (f
, m_preds
[i
]);
1903 /* Dump predicates in *THIS to stderr. */
1906 predicate::debug () const
1911 /* Dump predicates in *THIS for STMT prepended by MSG to F. */
1914 predicate::dump (FILE *f
, gimple
*stmt
, const char *msg
) const
1916 fprintf (f
, "%s", msg
);
1920 print_gimple_stmt (f
, stmt
, 0);
1921 fprintf (f
, " is conditional on:\n");
1927 /* Initialize USE_PREDS with the predicates of the control dependence chains
1928 between the basic block DEF_BB that defines a variable of interst and
1929 USE_BB that uses the variable, respectively. */
1932 uninit_analysis::init_use_preds (predicate
&use_preds
, basic_block def_bb
,
1935 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1936 fprintf (dump_file
, "init_use_preds (def_bb = %u, use_bb = %u)\n",
1937 def_bb
->index
, use_bb
->index
);
1939 gcc_assert (use_preds
.is_empty ()
1940 && dominated_by_p (CDI_DOMINATORS
, use_bb
, def_bb
));
1942 /* Set CD_ROOT to the basic block closest to USE_BB that is the control
1943 equivalent of (is guarded by the same predicate as) DEF_BB that also
1944 dominates USE_BB. This mimics the inner loop in
1945 compute_control_dep_chain. */
1946 basic_block cd_root
= def_bb
;
1949 basic_block pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, cd_root
);
1951 /* Stop at a loop exit which is also postdominating cd_root. */
1952 if (single_pred_p (pdom
) && !single_succ_p (cd_root
))
1955 if (!dominated_by_p (CDI_DOMINATORS
, pdom
, cd_root
)
1956 || !dominated_by_p (CDI_DOMINATORS
, use_bb
, pdom
))
1963 auto_bb_flag
in_region (cfun
);
1964 auto_vec
<basic_block
, 20> region (MIN (n_basic_blocks_for_fn (cfun
),
1965 param_uninit_control_dep_attempts
));
1967 /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
1968 Each DEP_CHAINS element is a series of edges whose conditions
1969 are logical conjunctions. Together, the DEP_CHAINS vector is
1970 used below to initialize an OR expression of the conjunctions. */
1971 unsigned num_chains
= 0;
1972 auto_vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1974 if (!dfs_mark_dominating_region (use_bb
, cd_root
, in_region
, region
)
1975 || !compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
1978 /* If the info in dep_chains is not complete we need to use a
1979 conservative approximation for the use predicate. */
1980 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1981 fprintf (dump_file
, "init_use_preds: dep_chain incomplete, using "
1982 "conservative approximation\n");
1984 dep_chains
[0].truncate (0);
1985 simple_control_dep_chain (dep_chains
[0], cd_root
, use_bb
);
1988 /* Unmark the region. */
1989 for (auto bb
: region
)
1990 bb
->flags
&= ~in_region
;
1992 /* From the set of edges computed above initialize *THIS as the OR
1993 condition under which the definition in DEF_BB is used in USE_BB.
1994 Each OR subexpression is represented by one element of DEP_CHAINS,
1995 where each element consists of a series of AND subexpressions. */
1996 use_preds
.init_from_control_deps (dep_chains
, num_chains
, true);
1997 return !use_preds
.is_empty ();
2000 /* Release resources in *THIS. */
2002 predicate::~predicate ()
2004 unsigned n
= m_preds
.length ();
2005 for (unsigned i
= 0; i
!= n
; ++i
)
2006 m_preds
[i
].release ();
2010 /* Copy-assign RHS to *THIS. */
2013 predicate::operator= (const predicate
&rhs
)
2018 unsigned n
= m_preds
.length ();
2019 for (unsigned i
= 0; i
!= n
; ++i
)
2020 m_preds
[i
].release ();
2023 n
= rhs
.m_preds
.length ();
2024 for (unsigned i
= 0; i
!= n
; ++i
)
2026 const pred_chain
&chain
= rhs
.m_preds
[i
];
2027 m_preds
.safe_push (chain
.copy ());
2033 /* For each use edge of PHI, compute all control dependence chains
2034 and convert those to the composite predicates in M_PREDS.
2035 Return true if a nonempty predicate has been obtained. */
2038 uninit_analysis::init_from_phi_def (gphi
*phi
)
2040 gcc_assert (m_phi_def_preds
.is_empty ());
2042 basic_block phi_bb
= gimple_bb (phi
);
2043 /* Find the closest dominating bb to be the control dependence root. */
2044 basic_block cd_root
= get_immediate_dominator (CDI_DOMINATORS
, phi_bb
);
2048 /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
2049 definitions of each of the PHI operands for which M_EVAL is false. */
2050 auto_vec
<edge
> def_edges
;
2051 hash_set
<gimple
*> visited_phis
;
2052 collect_phi_def_edges (phi
, cd_root
, &def_edges
, &visited_phis
);
2054 unsigned nedges
= def_edges
.length ();
2058 auto_bb_flag
in_region (cfun
);
2059 auto_vec
<basic_block
, 20> region (MIN (n_basic_blocks_for_fn (cfun
),
2060 param_uninit_control_dep_attempts
));
2061 /* Pre-mark the PHI incoming edges PHI block to make sure we only walk
2062 interesting edges from there. */
2063 for (unsigned i
= 0; i
< nedges
; i
++)
2065 if (!(def_edges
[i
]->dest
->flags
& in_region
))
2067 if (!region
.space (1))
2069 def_edges
[i
]->dest
->flags
|= in_region
;
2070 region
.quick_push (def_edges
[i
]->dest
);
2073 for (unsigned i
= 0; i
< nedges
; i
++)
2074 if (!dfs_mark_dominating_region (def_edges
[i
]->src
, cd_root
,
2078 unsigned num_chains
= 0;
2079 auto_vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
2080 for (unsigned i
= 0; i
< nedges
; i
++)
2082 edge e
= def_edges
[i
];
2083 unsigned prev_nc
= num_chains
;
2084 bool complete_p
= compute_control_dep_chain (cd_root
, e
->src
, dep_chains
,
2085 &num_chains
, in_region
);
2087 /* Update the newly added chains with the phi operand edge. */
2088 if (EDGE_COUNT (e
->src
->succs
) > 1)
2091 && prev_nc
== num_chains
2092 && num_chains
< MAX_NUM_CHAINS
)
2093 /* We can only add a chain for the PHI operand edge when the
2094 collected info was complete, otherwise the predicate may
2095 not be conservative. */
2096 dep_chains
[num_chains
++] = vNULL
;
2097 for (unsigned j
= prev_nc
; j
< num_chains
; j
++)
2098 dep_chains
[j
].safe_push (e
);
2102 /* Unmark the region. */
2103 for (auto bb
: region
)
2104 bb
->flags
&= ~in_region
;
2106 /* Convert control dependence chains to the predicate in *THIS under
2107 which the PHI operands are defined to values for which M_EVAL is
2109 m_phi_def_preds
.init_from_control_deps (dep_chains
, num_chains
, false);
2110 return !m_phi_def_preds
.is_empty ();
2113 /* Compute the predicates that guard the use USE_STMT and check if
2114 the incoming paths that have an empty (or possibly empty) definition
2115 can be pruned. Return true if it can be determined that the use of
2116 PHI's def in USE_STMT is guarded by a predicate set that does not
2117 overlap with the predicate sets of all runtime paths that do not
2120 Return false if the use is not guarded or if it cannot be determined.
2121 USE_BB is the bb of the use (for phi operand use, the bb is not the bb
2122 of the phi stmt, but the source bb of the operand edge).
2124 OPNDS is a bitmap with a bit set for each PHI operand of interest.
2126 THIS->M_PREDS contains the (memoized) defining predicate chains of
2127 a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate
2128 chains are computed and stored into THIS->M_PREDS as needed.
2130 VISITED_PHIS is a pointer set of phis being visited. */
2133 uninit_analysis::is_use_guarded (gimple
*use_stmt
, basic_block use_bb
,
2134 gphi
*phi
, unsigned opnds
,
2135 hash_set
<gphi
*> *visited
)
2137 if (visited
->add (phi
))
2140 /* The basic block where the PHI is defined. */
2141 basic_block def_bb
= gimple_bb (phi
);
2143 /* Try to build the predicate expression under which the PHI flows
2144 into its use. This will be empty if the PHI is defined and used
2146 predicate use_preds
;
2147 if (!init_use_preds (use_preds
, def_bb
, use_bb
))
2150 use_preds
.simplify (use_stmt
, /*is_use=*/true);
2151 use_preds
.normalize (use_stmt
, /*is_use=*/true);
2153 /* Try to prune the dead incoming phi edges. */
2154 if (!overlap (phi
, opnds
, visited
, use_preds
))
2156 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
2157 fputs ("found predicate overlap\n", dump_file
);
2162 if (m_phi_def_preds
.is_empty ())
2164 /* Lazily initialize *THIS from PHI. */
2165 if (!init_from_phi_def (phi
))
2168 m_phi_def_preds
.simplify (phi
);
2169 m_phi_def_preds
.normalize (phi
);
2172 /* Return true if the predicate guarding the valid definition (i.e.,
2173 *THIS) is a superset of the predicate guarding the use (i.e.,
2175 if (m_phi_def_preds
.superset_of (use_preds
))
2181 /* Public interface to the above. */
2184 uninit_analysis::is_use_guarded (gimple
*stmt
, basic_block use_bb
, gphi
*phi
,
2187 hash_set
<gphi
*> visited
;
2188 return is_use_guarded (stmt
, use_bb
, phi
, opnds
, &visited
);