1 /* Support for simple predicate analysis.
3 Copyright (C) 2001-2021 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"
44 #include "gimple-predicate-analysis.h"
46 #define DEBUG_PREDICATE_ANALYZER 1
48 /* Find the immediate postdominator of the specified basic block BB. */
50 static inline basic_block
51 find_pdom (basic_block bb
)
53 basic_block exit_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
57 if (basic_block pdom
= get_immediate_dominator (CDI_POST_DOMINATORS
, bb
))
63 /* Find the immediate dominator of the specified basic block BB. */
65 static inline basic_block
66 find_dom (basic_block bb
)
68 basic_block entry_bb
= ENTRY_BLOCK_PTR_FOR_FN (cfun
);
72 if (basic_block dom
= get_immediate_dominator (CDI_DOMINATORS
, bb
))
78 /* Return true if BB1 is postdominating BB2 and BB1 is not a loop exit
79 bb. The loop exit bb check is simple and does not cover all cases. */
82 is_non_loop_exit_postdominating (basic_block bb1
, basic_block bb2
)
84 if (!dominated_by_p (CDI_POST_DOMINATORS
, bb2
, bb1
))
87 if (single_pred_p (bb1
) && !single_succ_p (bb2
))
93 /* Find BB's closest postdominator that is its control equivalent (i.e.,
94 that's controlled by the same predicate). */
96 static inline basic_block
97 find_control_equiv_block (basic_block bb
)
99 basic_block pdom
= find_pdom (bb
);
101 /* Skip the postdominating bb that is also a loop exit. */
102 if (!is_non_loop_exit_postdominating (pdom
, bb
))
105 /* If the postdominator is dominated by BB, return it. */
106 if (dominated_by_p (CDI_DOMINATORS
, pdom
, bb
))
112 /* Return true if X1 is the negation of X2. */
115 pred_neg_p (const pred_info
&x1
, const pred_info
&x2
)
117 if (!operand_equal_p (x1
.pred_lhs
, x2
.pred_lhs
, 0)
118 || !operand_equal_p (x1
.pred_rhs
, x2
.pred_rhs
, 0))
121 tree_code c1
= x1
.cond_code
, c2
;
122 if (x1
.invert
== x2
.invert
)
123 c2
= invert_tree_comparison (x2
.cond_code
, false);
130 /* Return whether the condition (VAL CMPC BOUNDARY) is true. */
133 is_value_included_in (tree val
, tree boundary
, tree_code cmpc
)
135 /* Only handle integer constant here. */
136 if (TREE_CODE (val
) != INTEGER_CST
|| TREE_CODE (boundary
) != INTEGER_CST
)
139 bool inverted
= false;
140 if (cmpc
== GE_EXPR
|| cmpc
== GT_EXPR
|| cmpc
== NE_EXPR
)
142 cmpc
= invert_tree_comparison (cmpc
, false);
148 result
= tree_int_cst_equal (val
, boundary
);
149 else if (cmpc
== LT_EXPR
)
150 result
= tree_int_cst_lt (val
, boundary
);
153 gcc_assert (cmpc
== LE_EXPR
);
154 result
= tree_int_cst_le (val
, boundary
);
163 /* Format the vector of edges EV as a string. */
166 format_edge_vec (const vec
<edge
> &ev
)
170 unsigned n
= ev
.length ();
171 for (unsigned i
= 0; i
< n
; ++i
)
174 const_edge e
= ev
[i
];
175 sprintf (es
, "%u", e
->src
->index
);
183 /* Format the first N elements of the array of vector of edges EVA as
187 format_edge_vecs (const vec
<edge
> eva
[], unsigned n
)
191 for (unsigned i
= 0; i
!= n
; ++i
)
194 str
+= format_edge_vec (eva
[i
]);
202 /* Dump a single pred_info to DUMP_FILE. */
205 dump_pred_info (const pred_info
&pred
)
208 fprintf (dump_file
, "NOT (");
209 print_generic_expr (dump_file
, pred
.pred_lhs
);
210 fprintf (dump_file
, " %s ", op_symbol_code (pred
.cond_code
));
211 print_generic_expr (dump_file
, pred
.pred_rhs
);
213 fputc (')', dump_file
);
216 /* Dump a pred_chain to DUMP_FILE. */
219 dump_pred_chain (const pred_chain
&chain
)
221 unsigned np
= chain
.length ();
223 fprintf (dump_file
, "AND (");
225 for (unsigned j
= 0; j
< np
; j
++)
227 dump_pred_info (chain
[j
]);
229 fprintf (dump_file
, ", ");
231 fputc (')', dump_file
);
235 /* Dump the predicate chain PREDS for STMT, prefixed by MSG. */
238 dump_predicates (gimple
*stmt
, const pred_chain_union
&preds
, const char *msg
)
240 fprintf (dump_file
, "%s", msg
);
243 print_gimple_stmt (dump_file
, stmt
, 0);
244 fprintf (dump_file
, "is guarded by:\n");
247 unsigned np
= preds
.length ();
249 fprintf (dump_file
, "OR (");
250 for (unsigned i
= 0; i
< np
; i
++)
252 dump_pred_chain (preds
[i
]);
254 fprintf (dump_file
, ", ");
256 fputc (')', dump_file
);
258 fputc ('\n', dump_file
);
261 /* Dump the first NCHAINS elements of the DEP_CHAINS array into DUMP_FILE. */
264 dump_dep_chains (const auto_vec
<edge
> dep_chains
[], unsigned nchains
)
269 for (unsigned i
= 0; i
!= nchains
; ++i
)
271 const auto_vec
<edge
> &v
= dep_chains
[i
];
272 unsigned n
= v
.length ();
273 for (unsigned j
= 0; j
!= n
; ++j
)
275 fprintf (dump_file
, "%u", v
[j
]->src
->index
);
277 fprintf (dump_file
, " -> ");
279 fputc ('\n', dump_file
);
283 /* Return the 'normalized' conditional code with operand swapping
284 and condition inversion controlled by SWAP_COND and INVERT. */
287 get_cmp_code (tree_code orig_cmp_code
, bool swap_cond
, bool invert
)
289 tree_code tc
= orig_cmp_code
;
292 tc
= swap_tree_comparison (orig_cmp_code
);
294 tc
= invert_tree_comparison (tc
, false);
311 /* Return true if PRED is common among all predicate chains in PREDS
312 (and therefore can be factored out). */
315 find_matching_predicate_in_rest_chains (const pred_info
&pred
,
316 const pred_chain_union
&preds
)
319 if (preds
.length () == 1)
322 for (unsigned i
= 1; i
< preds
.length (); i
++)
325 const pred_chain
&chain
= preds
[i
];
326 unsigned n
= chain
.length ();
327 for (unsigned j
= 0; j
< n
; j
++)
329 const pred_info
&pred2
= chain
[j
];
330 /* Can relax the condition comparison to not use address
331 comparison. However, the most common case is that
332 multiple control dependent paths share a common path
333 prefix, so address comparison should be ok. */
334 if (operand_equal_p (pred2
.pred_lhs
, pred
.pred_lhs
, 0)
335 && operand_equal_p (pred2
.pred_rhs
, pred
.pred_rhs
, 0)
336 && pred2
.invert
== pred
.invert
)
348 /* Find a predicate to examine against paths of interest. If there
349 is no predicate of the "FLAG_VAR CMP CONST" form, try to find one
350 of that's the form "FLAG_VAR CMP FLAG_VAR" with value range info.
351 PHI is the phi node whose incoming (interesting) paths need to be
352 examined. On success, return the comparison code, set defintion
353 gimple of FLAG_DEF and BOUNDARY_CST. Otherwise return ERROR_MARK. */
356 find_var_cmp_const (pred_chain_union preds
, gphi
*phi
, gimple
**flag_def
,
359 tree_code vrinfo_code
= ERROR_MARK
;
360 gimple
*vrinfo_def
= NULL
;
361 tree vrinfo_cst
= NULL
;
363 gcc_assert (preds
.length () > 0);
364 pred_chain chain
= preds
[0];
365 for (unsigned i
= 0; i
< chain
.length (); i
++)
367 bool use_vrinfo_p
= false;
368 const pred_info
&pred
= chain
[i
];
369 tree cond_lhs
= pred
.pred_lhs
;
370 tree cond_rhs
= pred
.pred_rhs
;
371 if (cond_lhs
== NULL_TREE
|| cond_rhs
== NULL_TREE
)
374 tree_code code
= get_cmp_code (pred
.cond_code
, false, pred
.invert
);
375 if (code
== ERROR_MARK
)
378 /* Convert to the canonical form SSA_NAME CMP CONSTANT. */
379 if (TREE_CODE (cond_lhs
) == SSA_NAME
380 && is_gimple_constant (cond_rhs
))
382 else if (TREE_CODE (cond_rhs
) == SSA_NAME
383 && is_gimple_constant (cond_lhs
))
385 std::swap (cond_lhs
, cond_rhs
);
386 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
389 /* Check if we can take advantage of FLAG_VAR COMP FLAG_VAR predicate
390 with value range info. Note only first of such case is handled. */
391 else if (vrinfo_code
== ERROR_MARK
392 && TREE_CODE (cond_lhs
) == SSA_NAME
393 && TREE_CODE (cond_rhs
) == SSA_NAME
)
395 gimple
* lhs_def
= SSA_NAME_DEF_STMT (cond_lhs
);
396 if (!lhs_def
|| gimple_code (lhs_def
) != GIMPLE_PHI
397 || gimple_bb (lhs_def
) != gimple_bb (phi
))
399 std::swap (cond_lhs
, cond_rhs
);
400 if ((code
= get_cmp_code (code
, true, false)) == ERROR_MARK
)
404 /* Check value range info of rhs, do following transforms:
405 flag_var < [min, max] -> flag_var < max
406 flag_var > [min, max] -> flag_var > min
408 We can also transform LE_EXPR/GE_EXPR to LT_EXPR/GT_EXPR:
409 flag_var <= [min, max] -> flag_var < [min, max+1]
410 flag_var >= [min, max] -> flag_var > [min-1, max]
411 if no overflow/wrap. */
412 tree type
= TREE_TYPE (cond_lhs
);
414 if (!INTEGRAL_TYPE_P (type
)
415 || !get_range_query (cfun
)->range_of_expr (r
, cond_rhs
)
416 || r
.kind () != VR_RANGE
)
419 wide_int min
= r
.lower_bound ();
420 wide_int max
= r
.upper_bound ();
422 && max
!= wi::max_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
428 && min
!= wi::min_value (TYPE_PRECISION (type
), TYPE_SIGN (type
)))
434 cond_rhs
= wide_int_to_tree (type
, max
);
435 else if (code
== GT_EXPR
)
436 cond_rhs
= wide_int_to_tree (type
, min
);
445 if ((*flag_def
= SSA_NAME_DEF_STMT (cond_lhs
)) == NULL
)
448 if (gimple_code (*flag_def
) != GIMPLE_PHI
449 || gimple_bb (*flag_def
) != gimple_bb (phi
)
450 || !find_matching_predicate_in_rest_chains (pred
, preds
))
453 /* Return if any "flag_var comp const" predicate is found. */
456 *boundary_cst
= cond_rhs
;
459 /* Record if any "flag_var comp flag_var[vinfo]" predicate is found. */
460 else if (vrinfo_code
== ERROR_MARK
)
463 vrinfo_def
= *flag_def
;
464 vrinfo_cst
= cond_rhs
;
467 /* Return the "flag_var cmp flag_var[vinfo]" predicate we found. */
468 if (vrinfo_code
!= ERROR_MARK
)
470 *flag_def
= vrinfo_def
;
471 *boundary_cst
= vrinfo_cst
;
476 /* Return true if all interesting opnds are pruned, false otherwise.
477 PHI is the phi node with interesting operands, OPNDS is the bitmap
478 of the interesting operand positions, FLAG_DEF is the statement
479 defining the flag guarding the use of the PHI output, BOUNDARY_CST
480 is the const value used in the predicate associated with the flag,
481 CMP_CODE is the comparison code used in the predicate, VISITED_PHIS
482 is the pointer set of phis visited, and VISITED_FLAG_PHIS is
483 the pointer to the pointer set of flag definitions that are also
489 flag_1 = phi <0, 1> // (1)
490 var_1 = phi <undef, some_val>
494 flag_2 = phi <0, flag_1, flag_1> // (2)
495 var_2 = phi <undef, var_1, var_1>
502 Because some flag arg in (1) is not constant, if we do not look into
503 the flag phis recursively, it is conservatively treated as unknown and
504 var_1 is thought to flow into use at (3). Since var_1 is potentially
505 uninitialized a false warning will be emitted.
506 Checking recursively into (1), the compiler can find out that only
507 some_val (which is defined) can flow into (3) which is OK. */
510 prune_phi_opnds (gphi
*phi
, unsigned opnds
, gphi
*flag_def
,
511 tree boundary_cst
, tree_code cmp_code
,
512 predicate::func_t
&eval
,
513 hash_set
<gphi
*> *visited_phis
,
514 bitmap
*visited_flag_phis
)
516 /* The Boolean predicate guarding the PHI definition. Initialized
517 lazily from PHI in the first call to is_use_guarded() and cached
518 for subsequent iterations. */
519 predicate
def_preds (eval
);
521 unsigned n
= MIN (eval
.max_phi_args
, gimple_phi_num_args (flag_def
));
522 for (unsigned i
= 0; i
< n
; i
++)
524 if (!MASK_TEST_BIT (opnds
, i
))
527 tree flag_arg
= gimple_phi_arg_def (flag_def
, i
);
528 if (!is_gimple_constant (flag_arg
))
530 if (TREE_CODE (flag_arg
) != SSA_NAME
)
533 gphi
*flag_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (flag_arg
));
537 tree phi_arg
= gimple_phi_arg_def (phi
, i
);
538 if (TREE_CODE (phi_arg
) != SSA_NAME
)
541 gphi
*phi_arg_def
= dyn_cast
<gphi
*> (SSA_NAME_DEF_STMT (phi_arg
));
545 if (gimple_bb (phi_arg_def
) != gimple_bb (flag_arg_def
))
548 if (!*visited_flag_phis
)
549 *visited_flag_phis
= BITMAP_ALLOC (NULL
);
551 tree phi_result
= gimple_phi_result (flag_arg_def
);
552 if (bitmap_bit_p (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
)))
555 bitmap_set_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
557 /* Now recursively try to prune the interesting phi args. */
558 unsigned opnds_arg_phi
= eval
.phi_arg_set (phi_arg_def
);
559 if (!prune_phi_opnds (phi_arg_def
, opnds_arg_phi
, flag_arg_def
,
560 boundary_cst
, cmp_code
, eval
, visited_phis
,
564 bitmap_clear_bit (*visited_flag_phis
, SSA_NAME_VERSION (phi_result
));
568 /* Now check if the constant is in the guarded range. */
569 if (is_value_included_in (flag_arg
, boundary_cst
, cmp_code
))
571 /* Now that we know that this undefined edge is not pruned.
572 If the operand is defined by another phi, we can further
573 prune the incoming edges of that phi by checking
574 the predicates of this operands. */
576 tree opnd
= gimple_phi_arg_def (phi
, i
);
577 gimple
*opnd_def
= SSA_NAME_DEF_STMT (opnd
);
578 if (gphi
*opnd_def_phi
= dyn_cast
<gphi
*> (opnd_def
))
580 unsigned opnds2
= eval
.phi_arg_set (opnd_def_phi
);
581 if (!MASK_EMPTY (opnds2
))
583 edge opnd_edge
= gimple_phi_arg_edge (phi
, i
);
584 if (def_preds
.is_use_guarded (phi
, opnd_edge
->src
,
585 opnd_def_phi
, opnds2
,
598 /* Recursively compute the set PHI's incoming edges with "uninteresting"
599 operands of a phi chain, i.e., those for which EVAL returns false.
600 CD_ROOT is the control dependence root from which edges are collected
601 up the CFG nodes that it's dominated by. *EDGES holds the result, and
602 VISITED is used for detecting cycles. */
605 collect_phi_def_edges (gphi
*phi
, basic_block cd_root
, auto_vec
<edge
> *edges
,
606 predicate::func_t
&eval
, hash_set
<gimple
*> *visited
)
608 if (visited
->elements () == 0
609 && DEBUG_PREDICATE_ANALYZER
612 fprintf (dump_file
, "%s for cd_root %u and ",
613 __func__
, cd_root
->index
);
614 print_gimple_stmt (dump_file
, phi
, 0);
618 if (visited
->add (phi
))
621 unsigned n
= gimple_phi_num_args (phi
);
622 for (unsigned i
= 0; i
< n
; i
++)
624 edge opnd_edge
= gimple_phi_arg_edge (phi
, i
);
625 tree opnd
= gimple_phi_arg_def (phi
, i
);
627 if (TREE_CODE (opnd
) == SSA_NAME
)
629 gimple
*def
= SSA_NAME_DEF_STMT (opnd
);
631 if (gimple_code (def
) == GIMPLE_PHI
632 && dominated_by_p (CDI_DOMINATORS
, gimple_bb (def
), cd_root
))
633 collect_phi_def_edges (as_a
<gphi
*> (def
), cd_root
, edges
, eval
,
635 else if (!eval (opnd
))
637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
640 "\tFound def edge %i -> %i for cd_root %i "
641 "and operand %u of: ",
642 opnd_edge
->src
->index
, opnd_edge
->dest
->index
,
644 print_gimple_stmt (dump_file
, phi
, 0);
646 edges
->safe_push (opnd_edge
);
651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
654 "\tFound def edge %i -> %i for cd_root %i "
655 "and operand %u of: ",
656 opnd_edge
->src
->index
, opnd_edge
->dest
->index
,
658 print_gimple_stmt (dump_file
, phi
, 0);
662 edges
->safe_push (opnd_edge
);
667 /* Return an expression corresponding to the predicate PRED. */
670 build_pred_expr (const pred_info
&pred
)
672 tree_code cond_code
= pred
.cond_code
;
673 tree lhs
= pred
.pred_lhs
;
674 tree rhs
= pred
.pred_rhs
;
677 cond_code
= invert_tree_comparison (cond_code
, false);
679 return build2 (cond_code
, TREE_TYPE (lhs
), lhs
, rhs
);
682 /* Return an expression corresponding to PREDS. */
685 build_pred_expr (const pred_chain_union
&preds
, bool invert
= false)
687 tree_code code
= invert
? TRUTH_AND_EXPR
: TRUTH_OR_EXPR
;
688 tree_code subcode
= invert
? TRUTH_OR_EXPR
: TRUTH_AND_EXPR
;
690 tree expr
= NULL_TREE
;
691 for (unsigned i
= 0; i
!= preds
.length (); ++i
)
693 tree subexpr
= NULL_TREE
;
694 for (unsigned j
= 0; j
!= preds
[i
].length (); ++j
)
696 const pred_info
&pi
= preds
[i
][j
];
697 tree cond
= build_pred_expr (pi
);
699 cond
= invert_truthvalue (cond
);
700 subexpr
= subexpr
? build2 (subcode
, boolean_type_node
,
701 subexpr
, cond
) : cond
;
704 expr
= build2 (code
, boolean_type_node
, expr
, subexpr
);
712 /* Return a bitset of all PHI arguments or zero if there are too many. */
715 predicate::func_t::phi_arg_set (gphi
*phi
)
717 unsigned n
= gimple_phi_num_args (phi
);
719 if (max_phi_args
< n
)
722 /* Set the least significant N bits. */
723 return (1U << n
) - 1;
726 /* Determine if the predicate set of the use does not overlap with that
727 of the interesting paths. The most common senario of guarded use is
732 x = ...; // set x to valid
739 use (x); // use when x is valid
741 The real world examples are usually more complicated, but similar
742 and usually result from inlining:
744 bool init_func (int * x)
748 *x = ...; // set *x to valid
760 use (x); // use when x is valid
763 Another possible use scenario is in the following trivial example:
775 Predicate analysis needs to compute the composite predicate:
777 1) 'x' use predicate: (n > 0) .AND. (m < 2)
778 2) 'x' default value (non-def) predicate: .NOT. (n > 0)
779 (the predicate chain for phi operand defs can be computed
780 starting from a bb that is control equivalent to the phi's
781 bb and is dominating the operand def.)
783 and check overlapping:
784 (n > 0) .AND. (m < 2) .AND. (.NOT. (n > 0))
787 This implementation provides a framework that can handle different
788 scenarios. (Note that many simple cases are handled properly without
789 the predicate analysis if jump threading eliminates the merge point
790 thus makes path-sensitive analysis unnecessary.)
792 PHI is the phi node whose incoming (undefined) paths need to be
793 pruned, and OPNDS is the bitmap holding interesting operand
794 positions. VISITED is the pointer set of phi stmts being
798 predicate::overlap (gphi
*phi
, unsigned opnds
, hash_set
<gphi
*> *visited
)
800 gimple
*flag_def
= NULL
;
801 tree boundary_cst
= NULL_TREE
;
802 bitmap visited_flag_phis
= NULL
;
804 /* Find within the common prefix of multiple predicate chains
805 a predicate that is a comparison of a flag variable against
807 tree_code cmp_code
= find_var_cmp_const (m_preds
, phi
, &flag_def
,
809 if (cmp_code
== ERROR_MARK
)
812 /* Now check all the uninit incoming edges have a constant flag
813 value that is in conflict with the use guard/predicate. */
814 gphi
*phi_def
= as_a
<gphi
*> (flag_def
);
815 bool all_pruned
= prune_phi_opnds (phi
, opnds
, phi_def
, boundary_cst
,
816 cmp_code
, m_eval
, visited
,
819 if (visited_flag_phis
)
820 BITMAP_FREE (visited_flag_phis
);
825 /* Return true if two predicates PRED1 and X2 are equivalent. Assume
826 the expressions have already properly re-associated. */
829 pred_equal_p (const pred_info
&pred1
, const pred_info
&pred2
)
831 if (!operand_equal_p (pred1
.pred_lhs
, pred2
.pred_lhs
, 0)
832 || !operand_equal_p (pred1
.pred_rhs
, pred2
.pred_rhs
, 0))
835 tree_code c1
= pred1
.cond_code
, c2
;
836 if (pred1
.invert
!= pred2
.invert
837 && TREE_CODE_CLASS (pred2
.cond_code
) == tcc_comparison
)
838 c2
= invert_tree_comparison (pred2
.cond_code
, false);
840 c2
= pred2
.cond_code
;
845 /* Return true if PRED tests inequality (i.e., X != Y). */
848 is_neq_relop_p (const pred_info
&pred
)
851 return ((pred
.cond_code
== NE_EXPR
&& !pred
.invert
)
852 || (pred
.cond_code
== EQ_EXPR
&& pred
.invert
));
855 /* Returns true if PRED is of the form X != 0. */
858 is_neq_zero_form_p (const pred_info
&pred
)
860 if (!is_neq_relop_p (pred
) || !integer_zerop (pred
.pred_rhs
)
861 || TREE_CODE (pred
.pred_lhs
) != SSA_NAME
)
866 /* Return true if PRED is equivalent to X != 0. */
869 pred_expr_equal_p (const pred_info
&pred
, tree expr
)
871 if (!is_neq_zero_form_p (pred
))
874 return operand_equal_p (pred
.pred_lhs
, expr
, 0);
877 /* Return true if VAL satisfies (x CMPC BOUNDARY) predicate. CMPC can
878 be either one of the range comparison codes ({GE,LT,EQ,NE}_EXPR and
879 the like), or BIT_AND_EXPR. EXACT_P is only meaningful for the latter.
880 Modify the question from VAL & BOUNDARY != 0 to VAL & BOUNDARY == VAL.
881 For other values of CMPC, EXACT_P is ignored. */
884 value_sat_pred_p (tree val
, tree boundary
, tree_code cmpc
,
885 bool exact_p
= false)
887 if (cmpc
!= BIT_AND_EXPR
)
888 return is_value_included_in (val
, boundary
, cmpc
);
890 wide_int andw
= wi::to_wide (val
) & wi::to_wide (boundary
);
892 return andw
== wi::to_wide (val
);
894 return andw
.to_uhwi ();
897 /* Return true if the domain of single predicate expression PRED1
898 is a subset of that of PRED2, and false if it cannot be proved. */
901 subset_of (const pred_info
&pred1
, const pred_info
&pred2
)
903 if (pred_equal_p (pred1
, pred2
))
906 if ((TREE_CODE (pred1
.pred_rhs
) != INTEGER_CST
)
907 || (TREE_CODE (pred2
.pred_rhs
) != INTEGER_CST
))
910 if (!operand_equal_p (pred1
.pred_lhs
, pred2
.pred_lhs
, 0))
913 tree_code code1
= pred1
.cond_code
;
915 code1
= invert_tree_comparison (code1
, false);
916 tree_code code2
= pred2
.cond_code
;
918 code2
= invert_tree_comparison (code2
, false);
920 if (code2
== NE_EXPR
&& code1
== NE_EXPR
)
923 if (code2
== NE_EXPR
)
924 return !value_sat_pred_p (pred2
.pred_rhs
, pred1
.pred_rhs
, code1
);
926 if (code1
== EQ_EXPR
)
927 return value_sat_pred_p (pred1
.pred_rhs
, pred2
.pred_rhs
, code2
);
930 return value_sat_pred_p (pred1
.pred_rhs
, pred2
.pred_rhs
, code2
,
931 code1
== BIT_AND_EXPR
);
936 /* Return true if the domain of CHAIN1 is a subset of that of CHAIN2.
937 Return false if it cannot be proven so. */
940 subset_of (const pred_chain
&chain1
, const pred_chain
&chain2
)
942 unsigned np1
= chain1
.length ();
943 unsigned np2
= chain2
.length ();
944 for (unsigned i2
= 0; i2
< np2
; i2
++)
947 const pred_info
&info2
= chain2
[i2
];
948 for (unsigned i1
= 0; i1
< np1
; i1
++)
950 const pred_info
&info1
= chain1
[i1
];
951 if (subset_of (info1
, info2
))
963 /* Return true if the domain defined by the predicate chain PREDS is
964 a subset of the domain of *THIS. Return false if PREDS's domain
965 is not a subset of any of the sub-domains of *THIS (corresponding
966 to each individual chains in it), even though it may be still be
967 a subset of whole domain of *THIS which is the union (ORed) of all
968 its subdomains. In other words, the result is conservative. */
971 predicate::includes (const pred_chain
&chain
) const
973 for (unsigned i
= 0; i
< m_preds
.length (); i
++)
974 if (subset_of (chain
, m_preds
[i
]))
980 /* Return true if the domain defined by *THIS is a superset of PREDS's
982 Avoid building generic trees (and rely on the folding capability
983 of the compiler), and instead perform brute force comparison of
984 individual predicate chains (this won't be a computationally costly
985 since the chains are pretty short). Returning false does not
986 necessarily mean *THIS is not a superset of *PREDS, only that
987 it need not be since the analysis cannot prove it. */
990 predicate::superset_of (const predicate
&preds
) const
992 for (unsigned i
= 0; i
< preds
.m_preds
.length (); i
++)
993 if (!includes (preds
.m_preds
[i
]))
999 /* Create a predicate of the form OP != 0 and push it the work list CHAIN. */
1002 push_to_worklist (tree op
, pred_chain
*chain
, hash_set
<tree
> *mark_set
)
1004 if (mark_set
->contains (op
))
1009 arg_pred
.pred_lhs
= op
;
1010 arg_pred
.pred_rhs
= integer_zero_node
;
1011 arg_pred
.cond_code
= NE_EXPR
;
1012 arg_pred
.invert
= false;
1013 chain
->safe_push (arg_pred
);
1016 /* Return a pred_info for a gimple assignment CMP_ASSIGN with comparison
1020 get_pred_info_from_cmp (const gimple
*cmp_assign
)
1023 pred
.pred_lhs
= gimple_assign_rhs1 (cmp_assign
);
1024 pred
.pred_rhs
= gimple_assign_rhs2 (cmp_assign
);
1025 pred
.cond_code
= gimple_assign_rhs_code (cmp_assign
);
1026 pred
.invert
= false;
1030 /* If PHI is a degenerate phi with all operands having the same value (relop)
1031 update *PRED to that value and return true. Otherwise return false. */
1034 is_degenerate_phi (gimple
*phi
, pred_info
*pred
)
1036 tree op0
= gimple_phi_arg_def (phi
, 0);
1038 if (TREE_CODE (op0
) != SSA_NAME
)
1041 gimple
*def0
= SSA_NAME_DEF_STMT (op0
);
1042 if (gimple_code (def0
) != GIMPLE_ASSIGN
)
1045 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def0
)) != tcc_comparison
)
1048 pred_info pred0
= get_pred_info_from_cmp (def0
);
1050 unsigned n
= gimple_phi_num_args (phi
);
1051 for (unsigned i
= 1; i
< n
; ++i
)
1053 tree op
= gimple_phi_arg_def (phi
, i
);
1054 if (TREE_CODE (op
) != SSA_NAME
)
1057 gimple
*def
= SSA_NAME_DEF_STMT (op
);
1058 if (gimple_code (def
) != GIMPLE_ASSIGN
)
1061 if (TREE_CODE_CLASS (gimple_assign_rhs_code (def
)) != tcc_comparison
)
1064 pred_info pred
= get_pred_info_from_cmp (def
);
1065 if (!pred_equal_p (pred
, pred0
))
1073 /* Recursively compute the control dependence chains (paths of edges)
1074 from the dependent basic block, DEP_BB, up to the dominating basic
1075 block, DOM_BB (the head node of a chain should be dominated by it),
1076 storing them in the CD_CHAINS array.
1077 CUR_CD_CHAIN is the current chain being computed.
1078 *NUM_CHAINS is total number of chains in the CD_CHAINS array.
1079 *NUM_CALLS is the number of recursive calls to control unbounded
1081 Return true if the information is successfully computed, false if
1082 there is no control dependence or not computed. */
1085 compute_control_dep_chain (basic_block dom_bb
, const_basic_block dep_bb
,
1086 vec
<edge
> cd_chains
[], unsigned *num_chains
,
1087 vec
<edge
> &cur_cd_chain
, unsigned *num_calls
,
1090 if (*num_calls
> (unsigned)param_uninit_control_dep_attempts
)
1093 fprintf (dump_file
, "param_uninit_control_dep_attempts exceeded: %u\n",
1099 /* FIXME: Use a set instead. */
1100 unsigned cur_chain_len
= cur_cd_chain
.length ();
1101 if (cur_chain_len
> MAX_CHAIN_LEN
)
1104 fprintf (dump_file
, "MAX_CHAIN_LEN exceeded: %u\n", cur_chain_len
);
1109 if (cur_chain_len
> 5)
1112 fprintf (dump_file
, "chain length exceeds 5: %u\n", cur_chain_len
);
1115 for (unsigned i
= 0; i
< cur_chain_len
; i
++)
1117 edge e
= cur_cd_chain
[i
];
1118 /* Cycle detected. */
1119 if (e
->src
== dom_bb
)
1122 fprintf (dump_file
, "cycle detected\n");
1127 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1129 "%*s%s (dom_bb = %u, dep_bb = %u, cd_chains = { %s }, ...)\n",
1130 depth
, "", __func__
, dom_bb
->index
, dep_bb
->index
,
1131 format_edge_vecs (cd_chains
, *num_chains
).c_str ());
1133 bool found_cd_chain
= false;
1135 /* Iterate over DOM_BB's successors. */
1138 FOR_EACH_EDGE (e
, ei
, dom_bb
->succs
)
1140 int post_dom_check
= 0;
1141 if (e
->flags
& (EDGE_FAKE
| EDGE_ABNORMAL
))
1144 basic_block cd_bb
= e
->dest
;
1145 cur_cd_chain
.safe_push (e
);
1146 while (!is_non_loop_exit_postdominating (cd_bb
, dom_bb
))
1148 if (cd_bb
== dep_bb
)
1150 /* Found a direct control dependence. */
1151 if (*num_chains
< MAX_NUM_CHAINS
)
1153 cd_chains
[*num_chains
] = cur_cd_chain
.copy ();
1156 found_cd_chain
= true;
1157 /* Check path from next edge. */
1161 /* Check if DEP_BB is indirectly control-dependent on DOM_BB. */
1162 if (compute_control_dep_chain (cd_bb
, dep_bb
, cd_chains
,
1163 num_chains
, cur_cd_chain
,
1164 num_calls
, depth
+ 1))
1166 found_cd_chain
= true;
1170 cd_bb
= find_pdom (cd_bb
);
1172 if (cd_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1173 || post_dom_check
> MAX_POSTDOM_CHECK
)
1176 cur_cd_chain
.pop ();
1177 gcc_assert (cur_cd_chain
.length () == cur_chain_len
);
1180 gcc_assert (cur_cd_chain
.length () == cur_chain_len
);
1181 return found_cd_chain
;
1184 /* Return true if PRED can be invalidated by any predicate in GUARD. */
1187 can_be_invalidated_p (const pred_info
&pred
, const pred_chain
&guard
)
1189 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1191 fprintf (dump_file
, "Testing if predicate: ");
1192 dump_pred_info (pred
);
1193 fprintf (dump_file
, "\n...can be invalidated by a USE guard of: ");
1194 dump_pred_chain (guard
);
1195 fputc ('\n', dump_file
);
1198 unsigned n
= guard
.length ();
1199 for (unsigned i
= 0; i
< n
; ++i
)
1201 if (pred_neg_p (pred
, guard
[i
]))
1203 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1205 fprintf (dump_file
, " Predicate invalidated by: ");
1206 dump_pred_info (guard
[i
]);
1207 fputc ('\n', dump_file
);
1216 /* Return true if all predicates in PREDS are invalidated by GUARD being
1220 can_be_invalidated_p (const pred_chain_union
&preds
, const pred_chain
&guard
)
1222 if (preds
.is_empty ())
1225 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1226 dump_predicates (NULL
, preds
,
1227 "Testing if anything here can be invalidated: ");
1229 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1231 const pred_chain
&chain
= preds
[i
];
1232 for (unsigned j
= 0; j
< chain
.length (); ++j
)
1233 if (can_be_invalidated_p (chain
[j
], guard
))
1236 /* If we were unable to invalidate any predicate in C, then there
1237 is a viable path from entry to the PHI where the PHI takes
1238 an interesting value and continues to a use of the PHI. */
1244 /* Return true if none of the PHI arguments in OPNDS is used given
1245 the use guards in *THIS that guard the PHI's use. */
1248 predicate::use_cannot_happen (gphi
*phi
, unsigned opnds
)
1250 if (!m_eval
.phi_arg_set (phi
))
1253 /* PHI_USE_GUARDS are OR'ed together. If we have more than one
1254 possible guard, there's no way of knowing which guard was true.
1255 Since we need to be absolutely sure that the uninitialized
1256 operands will be invalidated, bail. */
1257 const pred_chain_union
&phi_use_guards
= m_preds
;
1258 if (phi_use_guards
.length () != 1)
1261 const pred_chain
&use_guard
= phi_use_guards
[0];
1263 /* Look for the control dependencies of all the interesting operands
1264 and build guard predicates describing them. */
1265 unsigned n
= gimple_phi_num_args (phi
);
1266 for (unsigned i
= 0; i
< n
; ++i
)
1268 if (!MASK_TEST_BIT (opnds
, i
))
1271 edge e
= gimple_phi_arg_edge (phi
, i
);
1272 auto_vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1273 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
1274 unsigned num_chains
= 0;
1275 unsigned num_calls
= 0;
1277 /* Build the control dependency chain for the PHI argument... */
1278 if (!compute_control_dep_chain (ENTRY_BLOCK_PTR_FOR_FN (cfun
),
1279 e
->src
, dep_chains
, &num_chains
,
1280 cur_chain
, &num_calls
))
1283 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1285 fprintf (dump_file
, "predicate::use_cannot_happen (...) "
1286 "dep_chains for arg %u:\n\t", i
);
1287 dump_dep_chains (dep_chains
, num_chains
);
1290 /* ...and convert it into a set of predicates guarding its
1292 predicate
def_preds (m_eval
);
1293 def_preds
.init_from_control_deps (dep_chains
, num_chains
);
1294 if (def_preds
.is_empty ())
1295 /* If there's no predicate there's no basis to rule the use out. */
1298 def_preds
.simplify ();
1299 def_preds
.normalize ();
1301 /* Can the guard for this PHI argument be negated by the one
1302 guarding the PHI use? */
1303 if (!can_be_invalidated_p (def_preds
.chain (), use_guard
))
1310 /* Implemented simplifications:
1312 1) ((x IOR y) != 0) AND (x != 0) is equivalent to (x != 0);
1313 2) (X AND Y) OR (!X AND Y) is equivalent to Y;
1314 3) X OR (!X AND Y) is equivalent to (X OR Y);
1315 4) ((x IAND y) != 0) || (x != 0 AND y != 0)) is equivalent to
1317 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
1320 PREDS is the predicate chains, and N is the number of chains. */
1322 /* Implement rule 1 above. PREDS is the AND predicate to simplify
1326 simplify_1 (pred_chain
&chain
)
1328 bool simplified
= false;
1329 pred_chain s_chain
= vNULL
;
1331 unsigned n
= chain
.length ();
1332 for (unsigned i
= 0; i
< n
; i
++)
1334 pred_info
&a_pred
= chain
[i
];
1336 if (!a_pred
.pred_lhs
1337 || !is_neq_zero_form_p (a_pred
))
1340 gimple
*def_stmt
= SSA_NAME_DEF_STMT (a_pred
.pred_lhs
);
1341 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1344 if (gimple_assign_rhs_code (def_stmt
) != BIT_IOR_EXPR
)
1347 for (unsigned j
= 0; j
< n
; j
++)
1349 const pred_info
&b_pred
= chain
[j
];
1351 if (!b_pred
.pred_lhs
1352 || !is_neq_zero_form_p (b_pred
))
1355 if (pred_expr_equal_p (b_pred
, gimple_assign_rhs1 (def_stmt
))
1356 || pred_expr_equal_p (b_pred
, gimple_assign_rhs2 (def_stmt
)))
1358 /* Mark A_PRED for removal from PREDS. */
1359 a_pred
.pred_lhs
= NULL
;
1360 a_pred
.pred_rhs
= NULL
;
1370 /* Remove predicates marked above. */
1371 for (unsigned i
= 0; i
< n
; i
++)
1373 pred_info
&a_pred
= chain
[i
];
1374 if (!a_pred
.pred_lhs
)
1376 s_chain
.safe_push (a_pred
);
1383 /* Implements rule 2 for the OR predicate PREDS:
1385 2) (X AND Y) OR (!X AND Y) is equivalent to Y. */
1388 predicate::simplify_2 ()
1390 bool simplified
= false;
1392 /* (X AND Y) OR (!X AND Y) is equivalent to Y.
1393 (X AND Y) OR (X AND !Y) is equivalent to X. */
1395 unsigned n
= m_preds
.length ();
1396 for (unsigned i
= 0; i
< n
; i
++)
1398 pred_chain
&a_chain
= m_preds
[i
];
1399 if (a_chain
.length () != 2)
1402 /* Create copies since the chain may be released below before
1403 the copy is added to the other chain. */
1404 const pred_info x
= a_chain
[0];
1405 const pred_info y
= a_chain
[1];
1407 for (unsigned j
= 0; j
< n
; j
++)
1412 pred_chain
&b_chain
= m_preds
[j
];
1413 if (b_chain
.length () != 2)
1416 const pred_info
&x2
= b_chain
[0];
1417 const pred_info
&y2
= b_chain
[1];
1419 if (pred_equal_p (x
, x2
) && pred_neg_p (y
, y2
))
1424 b_chain
.safe_push (x
);
1428 if (pred_neg_p (x
, x2
) && pred_equal_p (y
, y2
))
1433 b_chain
.safe_push (y
);
1439 /* Now clean up the chain. */
1442 pred_chain_union s_preds
= vNULL
;
1443 for (unsigned i
= 0; i
< n
; i
++)
1445 if (m_preds
[i
].is_empty ())
1447 s_preds
.safe_push (m_preds
[i
]);
1457 /* Implement rule 3 for the OR predicate PREDS:
1459 3) x OR (!x AND y) is equivalent to x OR y. */
1462 predicate::simplify_3 ()
1464 /* Now iteratively simplify X OR (!X AND Z ..)
1465 into X OR (Z ...). */
1467 unsigned n
= m_preds
.length ();
1471 bool simplified
= false;
1472 for (unsigned i
= 0; i
< n
; i
++)
1474 const pred_chain
&a_chain
= m_preds
[i
];
1476 if (a_chain
.length () != 1)
1479 const pred_info
&x
= a_chain
[0];
1480 for (unsigned j
= 0; j
< n
; j
++)
1485 pred_chain b_chain
= m_preds
[j
];
1486 if (b_chain
.length () < 2)
1489 for (unsigned k
= 0; k
< b_chain
.length (); k
++)
1491 const pred_info
&x2
= b_chain
[k
];
1492 if (pred_neg_p (x
, x2
))
1494 b_chain
.unordered_remove (k
);
1504 /* Implement rule 4 for the OR predicate PREDS:
1506 2) ((x AND y) != 0) OR (x != 0 AND y != 0) is equivalent to
1507 (x != 0 ANd y != 0). */
1510 predicate::simplify_4 ()
1512 bool simplified
= false;
1513 pred_chain_union s_preds
= vNULL
;
1515 unsigned n
= m_preds
.length ();
1516 for (unsigned i
= 0; i
< n
; i
++)
1518 pred_chain a_chain
= m_preds
[i
];
1519 if (a_chain
.length () != 1)
1522 const pred_info
&z
= a_chain
[0];
1523 if (!is_neq_zero_form_p (z
))
1526 gimple
*def_stmt
= SSA_NAME_DEF_STMT (z
.pred_lhs
);
1527 if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1530 if (gimple_assign_rhs_code (def_stmt
) != BIT_AND_EXPR
)
1533 for (unsigned j
= 0; j
< n
; j
++)
1538 pred_chain b_chain
= m_preds
[j
];
1539 if (b_chain
.length () != 2)
1542 const pred_info
&x2
= b_chain
[0];
1543 const pred_info
&y2
= b_chain
[1];
1544 if (!is_neq_zero_form_p (x2
) || !is_neq_zero_form_p (y2
))
1547 if ((pred_expr_equal_p (x2
, gimple_assign_rhs1 (def_stmt
))
1548 && pred_expr_equal_p (y2
, gimple_assign_rhs2 (def_stmt
)))
1549 || (pred_expr_equal_p (x2
, gimple_assign_rhs2 (def_stmt
))
1550 && pred_expr_equal_p (y2
, gimple_assign_rhs1 (def_stmt
))))
1559 /* Now clean up the chain. */
1562 for (unsigned i
= 0; i
< n
; i
++)
1564 if (m_preds
[i
].is_empty ())
1566 s_preds
.safe_push (m_preds
[i
]);
1577 /* Simplify predicates in *THIS. */
1580 predicate::simplify (gimple
*use_or_def
, bool is_use
)
1582 if (dump_file
&& dump_flags
& TDF_DETAILS
)
1584 fprintf (dump_file
, "Before simplication ");
1585 dump (use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
1588 unsigned n
= m_preds
.length ();
1589 for (unsigned i
= 0; i
< n
; i
++)
1590 ::simplify_1 (m_preds
[i
]);
1611 /* Attempt to normalize predicate chains by following UD chains by
1612 building up a big tree of either IOR operations or AND operations,
1613 and converting the IOR tree into a pred_chain_union or the BIT_AND
1614 tree into a pred_chain.
1624 then _t != 0 will be normalized into a pred_chain_union
1626 (_2 RELOP1 _1) OR (_5 RELOP2 _4) OR (_8 RELOP3 _7) OR (_0 != 0)
1636 then _t != 0 will be normalized into a pred_chain:
1637 (_2 RELOP1 _1) AND (_5 RELOP2 _4) AND (_8 RELOP3 _7) AND (_0 != 0)
1640 /* Store a PRED in *THIS. */
1643 predicate::push_pred (const pred_info
&pred
)
1645 pred_chain chain
= vNULL
;
1646 chain
.safe_push (pred
);
1647 m_preds
.safe_push (chain
);
1650 /* Dump predicates in *THIS for STMT prepended by MSG. */
1653 predicate::dump (gimple
*stmt
, const char *msg
) const
1655 fprintf (dump_file
, "%s", msg
);
1658 fputc ('\t', dump_file
);
1659 print_gimple_stmt (dump_file
, stmt
, 0);
1660 fprintf (dump_file
, " is conditional on:\n");
1663 unsigned np
= m_preds
.length ();
1666 fprintf (dump_file
, "\t(empty)\n");
1671 tree expr
= build_pred_expr (m_preds
);
1672 char *str
= print_generic_expr_to_str (expr
);
1673 fprintf (dump_file
, "\t%s (expanded)\n", str
);
1678 fprintf (dump_file
, "\tOR (");
1680 fputc ('\t', dump_file
);
1681 for (unsigned i
= 0; i
< np
; i
++)
1683 dump_pred_chain (m_preds
[i
]);
1685 fprintf (dump_file
, ", ");
1687 fputc (')', dump_file
);
1689 fputc ('\n', dump_file
);
1692 /* Initialize *THIS with the predicates of the control dependence chains
1693 between the basic block DEF_BB that defines a variable of interst and
1694 USE_BB that uses the variable, respectively. */
1696 predicate::predicate (basic_block def_bb
, basic_block use_bb
, func_t
&eval
)
1697 : m_preds (vNULL
), m_eval (eval
)
1699 /* Set CD_ROOT to the basic block closest to USE_BB that is the control
1700 equivalent of (is guarded by the same predicate as) DEF_BB that also
1701 dominates USE_BB. */
1702 basic_block cd_root
= def_bb
;
1703 while (dominated_by_p (CDI_DOMINATORS
, use_bb
, cd_root
))
1705 /* Find CD_ROOT's closest postdominator that's its control
1707 if (basic_block bb
= find_control_equiv_block (cd_root
))
1708 if (dominated_by_p (CDI_DOMINATORS
, use_bb
, bb
))
1717 /* Set DEP_CHAINS to the set of edges between CD_ROOT and USE_BB.
1718 Each DEP_CHAINS element is a series of edges whose conditions
1719 are logical conjunctions. Together, the DEP_CHAINS vector is
1720 used below to initialize an OR expression of the conjunctions. */
1721 unsigned num_calls
= 0;
1722 unsigned num_chains
= 0;
1723 auto_vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1724 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
1726 compute_control_dep_chain (cd_root
, use_bb
, dep_chains
, &num_chains
,
1727 cur_chain
, &num_calls
);
1729 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1731 fprintf (dump_file
, "predicate::predicate (def_bb = %u, use_bb = %u, func_t) "
1732 "initialized from %u dep_chains:\n\t",
1733 def_bb
->index
, use_bb
->index
, num_chains
);
1734 dump_dep_chains (dep_chains
, num_chains
);
1737 /* From the set of edges computed above initialize *THIS as the OR
1738 condition under which the definition in DEF_BB is used in USE_BB.
1739 Each OR subexpression is represented by one element of DEP_CHAINS,
1740 where each element consists of a series of AND subexpressions. */
1741 init_from_control_deps (dep_chains
, num_chains
);
1744 /* Release resources in *THIS. */
1746 predicate::~predicate ()
1748 unsigned n
= m_preds
.length ();
1749 for (unsigned i
= 0; i
!= n
; ++i
)
1750 m_preds
[i
].release ();
1754 /* Copy-assign RHS to *THIS. */
1757 predicate::operator= (const predicate
&rhs
)
1762 /* FIXME: Make this a compile-time constraint? */
1763 gcc_assert (&m_eval
== &rhs
.m_eval
);
1765 unsigned n
= m_preds
.length ();
1766 for (unsigned i
= 0; i
!= n
; ++i
)
1767 m_preds
[i
].release ();
1770 n
= rhs
.m_preds
.length ();
1771 for (unsigned i
= 0; i
!= n
; ++i
)
1773 const pred_chain
&chain
= rhs
.m_preds
[i
];
1774 m_preds
.safe_push (chain
.copy ());
1780 /* For each use edge of PHI, compute all control dependence chains
1781 and convert those to the composite predicates in M_PREDS.
1782 Return true if a nonempty predicate has been obtained. */
1785 predicate::init_from_phi_def (gphi
*phi
)
1787 gcc_assert (is_empty ());
1789 basic_block phi_bb
= gimple_bb (phi
);
1790 /* Find the closest dominating bb to be the control dependence root. */
1791 basic_block cd_root
= find_dom (phi_bb
);
1795 /* Set DEF_EDGES to the edges to the PHI from the bb's that provide
1796 definitions of each of the PHI operands for which M_EVAL is false. */
1797 auto_vec
<edge
> def_edges
;
1798 hash_set
<gimple
*> visited_phis
;
1799 collect_phi_def_edges (phi
, cd_root
, &def_edges
, m_eval
, &visited_phis
);
1801 unsigned nedges
= def_edges
.length ();
1805 unsigned num_chains
= 0;
1806 auto_vec
<edge
> dep_chains
[MAX_NUM_CHAINS
];
1807 auto_vec
<edge
, MAX_CHAIN_LEN
+ 1> cur_chain
;
1808 for (unsigned i
= 0; i
< nedges
; i
++)
1810 edge e
= def_edges
[i
];
1811 unsigned num_calls
= 0;
1812 unsigned prev_nc
= num_chains
;
1813 compute_control_dep_chain (cd_root
, e
->src
, dep_chains
,
1814 &num_chains
, cur_chain
, &num_calls
);
1816 /* Update the newly added chains with the phi operand edge. */
1817 if (EDGE_COUNT (e
->src
->succs
) > 1)
1819 if (prev_nc
== num_chains
&& num_chains
< MAX_NUM_CHAINS
)
1820 dep_chains
[num_chains
++] = vNULL
;
1821 for (unsigned j
= prev_nc
; j
< num_chains
; j
++)
1822 dep_chains
[j
].safe_push (e
);
1826 /* Convert control dependence chains to the predicate in *THIS under
1827 which the PHI operands are defined to values for which M_EVAL is
1829 init_from_control_deps (dep_chains
, num_chains
);
1830 return !is_empty ();
1833 /* Compute the predicates that guard the use USE_STMT and check if
1834 the incoming paths that have an empty (or possibly empty) definition
1835 can be pruned. Return true if it can be determined that the use of
1836 PHI's def in USE_STMT is guarded by a predicate set that does not
1837 overlap with the predicate sets of all runtime paths that do not
1840 Return false if the use is not guarded or if it cannot be determined.
1841 USE_BB is the bb of the use (for phi operand use, the bb is not the bb
1842 of the phi stmt, but the source bb of the operand edge).
1844 OPNDS is a bitmap with a bit set for each PHI operand of interest.
1846 THIS->M_PREDS contains the (memoized) defining predicate chains of
1847 a PHI. If THIS->M_PREDS is empty, the PHI's defining predicate
1848 chains are computed and stored into THIS->M_PREDS as needed.
1850 VISITED_PHIS is a pointer set of phis being visited. */
1853 predicate::is_use_guarded (gimple
*use_stmt
, basic_block use_bb
,
1854 gphi
*phi
, unsigned opnds
,
1855 hash_set
<gphi
*> *visited
)
1857 if (visited
->add (phi
))
1860 /* The basic block where the PHI is defined. */
1861 basic_block def_bb
= gimple_bb (phi
);
1863 /* Try to build the predicate expression under which the PHI flows
1864 into its use. This will be empty if the PHI is defined and used
1866 predicate
use_preds (def_bb
, use_bb
, m_eval
);
1868 if (is_non_loop_exit_postdominating (use_bb
, def_bb
))
1872 /* Lazily initialize *THIS from the PHI and build its use
1874 init_from_phi_def (phi
);
1875 m_use_expr
= build_pred_expr (use_preds
.m_preds
);
1878 /* The use is not guarded. */
1882 if (use_preds
.is_empty ())
1885 /* Try to prune the dead incoming phi edges. */
1886 if (!use_preds
.overlap (phi
, opnds
, visited
))
1888 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
1889 fputs ("found predicate overlap\n", dump_file
);
1894 /* We might be able to prove that if the control dependencies for OPNDS
1895 are true, the control dependencies for USE_STMT can never be true. */
1896 if (use_preds
.use_cannot_happen (phi
, opnds
))
1901 /* Lazily initialize *THIS from PHI. */
1902 if (!init_from_phi_def (phi
))
1904 m_use_expr
= build_pred_expr (use_preds
.m_preds
);
1912 use_preds
.simplify (use_stmt
, /*is_use=*/true);
1913 use_preds
.normalize (use_stmt
, /*is_use=*/true);
1915 /* Return true if the predicate guarding the valid definition (i.e.,
1916 *THIS) is a superset of the predicate guarding the use (i.e.,
1918 if (superset_of (use_preds
))
1921 m_use_expr
= build_pred_expr (use_preds
.m_preds
);
1926 /* Public interface to the above. */
1929 predicate::is_use_guarded (gimple
*stmt
, basic_block use_bb
, gphi
*phi
,
1932 hash_set
<gphi
*> visited
;
1933 return is_use_guarded (stmt
, use_bb
, phi
, opnds
, &visited
);
1936 /* Normalize predicate PRED:
1937 1) if PRED can no longer be normalized, append it to *THIS.
1938 2) otherwise if PRED is of the form x != 0, follow x's definition
1939 and put normalized predicates into WORK_LIST. */
1942 predicate::normalize (pred_chain
*norm_chain
,
1944 tree_code and_or_code
,
1945 pred_chain
*work_list
,
1946 hash_set
<tree
> *mark_set
)
1948 if (!is_neq_zero_form_p (pred
))
1950 if (and_or_code
== BIT_IOR_EXPR
)
1953 norm_chain
->safe_push (pred
);
1957 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
1959 if (gimple_code (def_stmt
) == GIMPLE_PHI
1960 && is_degenerate_phi (def_stmt
, &pred
))
1961 /* PRED has been modified above. */
1962 work_list
->safe_push (pred
);
1963 else if (gimple_code (def_stmt
) == GIMPLE_PHI
&& and_or_code
== BIT_IOR_EXPR
)
1965 unsigned n
= gimple_phi_num_args (def_stmt
);
1967 /* Punt for a nonzero constant. The predicate should be one guarding
1969 for (unsigned i
= 0; i
< n
; ++i
)
1971 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1972 if (TREE_CODE (op
) == INTEGER_CST
&& !integer_zerop (op
))
1979 for (unsigned i
= 0; i
< n
; ++i
)
1981 tree op
= gimple_phi_arg_def (def_stmt
, i
);
1982 if (integer_zerop (op
))
1985 push_to_worklist (op
, work_list
, mark_set
);
1988 else if (gimple_code (def_stmt
) != GIMPLE_ASSIGN
)
1990 if (and_or_code
== BIT_IOR_EXPR
)
1993 norm_chain
->safe_push (pred
);
1995 else if (gimple_assign_rhs_code (def_stmt
) == and_or_code
)
1997 /* Avoid splitting up bit manipulations like x & 3 or y | 1. */
1998 if (is_gimple_min_invariant (gimple_assign_rhs2 (def_stmt
)))
2000 /* But treat x & 3 as a condition. */
2001 if (and_or_code
== BIT_AND_EXPR
)
2004 n_pred
.pred_lhs
= gimple_assign_rhs1 (def_stmt
);
2005 n_pred
.pred_rhs
= gimple_assign_rhs2 (def_stmt
);
2006 n_pred
.cond_code
= and_or_code
;
2007 n_pred
.invert
= false;
2008 norm_chain
->safe_push (n_pred
);
2013 push_to_worklist (gimple_assign_rhs1 (def_stmt
), work_list
, mark_set
);
2014 push_to_worklist (gimple_assign_rhs2 (def_stmt
), work_list
, mark_set
);
2017 else if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt
))
2020 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2021 if (and_or_code
== BIT_IOR_EXPR
)
2024 norm_chain
->safe_push (n_pred
);
2028 if (and_or_code
== BIT_IOR_EXPR
)
2031 norm_chain
->safe_push (pred
);
2035 /* Normalize PRED and store the normalized predicates in THIS->M_PREDS. */
2038 predicate::normalize (const pred_info
&pred
)
2040 if (!is_neq_zero_form_p (pred
))
2046 tree_code and_or_code
= ERROR_MARK
;
2048 gimple
*def_stmt
= SSA_NAME_DEF_STMT (pred
.pred_lhs
);
2049 if (gimple_code (def_stmt
) == GIMPLE_ASSIGN
)
2050 and_or_code
= gimple_assign_rhs_code (def_stmt
);
2051 if (and_or_code
!= BIT_IOR_EXPR
&& and_or_code
!= BIT_AND_EXPR
)
2053 if (TREE_CODE_CLASS (and_or_code
) == tcc_comparison
)
2055 pred_info n_pred
= get_pred_info_from_cmp (def_stmt
);
2064 pred_chain norm_chain
= vNULL
;
2065 pred_chain work_list
= vNULL
;
2066 work_list
.safe_push (pred
);
2067 hash_set
<tree
> mark_set
;
2069 while (!work_list
.is_empty ())
2071 pred_info a_pred
= work_list
.pop ();
2072 normalize (&norm_chain
, a_pred
, and_or_code
, &work_list
, &mark_set
);
2075 if (and_or_code
== BIT_AND_EXPR
)
2076 m_preds
.safe_push (norm_chain
);
2078 work_list
.release ();
2081 /* Normalize a single predicate PRED_CHAIN and append it to *THIS. */
2084 predicate::normalize (const pred_chain
&chain
)
2086 pred_chain work_list
= vNULL
;
2087 hash_set
<tree
> mark_set
;
2088 for (unsigned i
= 0; i
< chain
.length (); i
++)
2090 work_list
.safe_push (chain
[i
]);
2091 mark_set
.add (chain
[i
].pred_lhs
);
2094 /* Normalized chain of predicates built up below. */
2095 pred_chain norm_chain
= vNULL
;
2096 while (!work_list
.is_empty ())
2098 pred_info pi
= work_list
.pop ();
2099 predicate
pred (m_eval
);
2100 /* The predicate object is not modified here, only NORM_CHAIN and
2101 WORK_LIST are appended to. */
2102 pred
.normalize (&norm_chain
, pi
, BIT_AND_EXPR
, &work_list
, &mark_set
);
2105 m_preds
.safe_push (norm_chain
);
2106 work_list
.release ();
2109 /* Normalize predicate chains in THIS. */
2112 predicate::normalize (gimple
*use_or_def
, bool is_use
)
2114 if (dump_file
&& dump_flags
& TDF_DETAILS
)
2116 fprintf (dump_file
, "Before normalization ");
2117 dump (use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
2120 predicate
norm_preds (m_eval
);
2121 for (unsigned i
= 0; i
< m_preds
.length (); i
++)
2123 if (m_preds
[i
].length () != 1)
2124 norm_preds
.normalize (m_preds
[i
]);
2126 norm_preds
.normalize (m_preds
[i
][0]);
2133 fprintf (dump_file
, "After normalization ");
2134 dump (use_or_def
, is_use
? "[USE]:\n" : "[DEF]:\n");
2138 /* Add a predicate for the condition or logical assignment STMT to CHAIN.
2139 Expand SSA_NAME into constituent subexpressions. Invert the result
2140 if INVERT is true. Return true if the predicate has been added. */
2143 add_pred (pred_chain
*chain
, gimple
*stmt
, bool invert
)
2145 if (gimple_code (stmt
) == GIMPLE_COND
)
2147 tree lhs
= gimple_cond_lhs (stmt
);
2148 if (TREE_CODE (lhs
) == SSA_NAME
)
2150 gimple
*def
= SSA_NAME_DEF_STMT (lhs
);
2151 if (is_gimple_assign (def
)
2152 && add_pred (chain
, def
, invert
))
2157 pred
.pred_lhs
= lhs
;
2158 pred
.pred_rhs
= gimple_cond_rhs (stmt
);
2159 pred
.cond_code
= gimple_cond_code (stmt
);
2160 pred
.invert
= invert
;
2161 chain
->safe_push (pred
);
2165 if (!is_gimple_assign (stmt
))
2168 if (gimple_assign_single_p (stmt
))
2169 // FIXME: handle this?
2172 if (TREE_TYPE (gimple_assign_lhs (stmt
)) != boolean_type_node
)
2175 tree rhs1
= gimple_assign_rhs1 (stmt
);
2176 tree rhs2
= gimple_assign_rhs2 (stmt
);
2177 tree_code code
= gimple_assign_rhs_code (stmt
);
2178 if (code
== BIT_AND_EXPR
)
2180 if (TREE_CODE (rhs1
) == SSA_NAME
2181 && add_pred (chain
, SSA_NAME_DEF_STMT (rhs1
), invert
)
2182 && TREE_CODE (rhs2
) == SSA_NAME
2183 /* FIXME: Need to handle failure below! */
2184 && add_pred (chain
, SSA_NAME_DEF_STMT (rhs2
), invert
))
2187 else if (TREE_CODE_CLASS (code
) != tcc_comparison
)
2191 pred
.pred_lhs
= rhs1
;
2192 pred
.pred_rhs
= rhs2
;
2193 pred
.cond_code
= code
;
2194 pred
.invert
= invert
;
2195 chain
->safe_push (pred
);
2199 /* Convert the chains of control dependence edges into a set of predicates.
2200 A control dependence chain is represented by a vector edges. DEP_CHAINS
2201 points to an array of NUM_CHAINS dependence chains. One edge in
2202 a dependence chain is mapped to predicate expression represented by
2203 pred_info type. One dependence chain is converted to a composite
2204 predicate that is the result of AND operation of pred_info mapped to
2205 each edge. A composite predicate is represented by a vector of
2206 pred_info. Sets M_PREDS to the resulting composite predicates. */
2209 predicate::init_from_control_deps (const vec
<edge
> *dep_chains
,
2210 unsigned num_chains
)
2212 gcc_assert (is_empty ());
2214 bool has_valid_pred
= false;
2215 if (num_chains
== 0)
2218 if (num_chains
>= MAX_NUM_CHAINS
)
2221 fprintf (dump_file
, "MAX_NUM_CHAINS exceeded: %u\n", num_chains
);
2225 /* Convert the control dependency chain into a set of predicates. */
2226 m_preds
.reserve (num_chains
);
2228 for (unsigned i
= 0; i
< num_chains
; i
++)
2230 /* One path through the CFG represents a logical conjunction
2231 of the predicates. */
2232 const vec
<edge
> &path
= dep_chains
[i
];
2234 has_valid_pred
= false;
2235 /* The chain of predicates guarding the definition along this path. */
2236 pred_chain t_chain
{ };
2237 for (unsigned j
= 0; j
< path
.length (); j
++)
2240 basic_block guard_bb
= e
->src
;
2241 /* Ignore empty forwarder blocks. */
2242 if (empty_block_p (guard_bb
) && single_succ_p (guard_bb
))
2245 /* An empty basic block here is likely a PHI, and is not one
2246 of the cases we handle below. */
2247 gimple_stmt_iterator gsi
= gsi_last_bb (guard_bb
);
2248 if (gsi_end_p (gsi
))
2250 has_valid_pred
= false;
2253 /* Get the conditional controlling the bb exit edge. */
2254 gimple
*cond_stmt
= gsi_stmt (gsi
);
2255 if (is_gimple_call (cond_stmt
) && EDGE_COUNT (e
->src
->succs
) >= 2)
2256 /* Ignore EH edge. Can add assertion on the other edge's flag. */
2258 /* Skip if there is essentially one succesor. */
2259 if (EDGE_COUNT (e
->src
->succs
) == 2)
2265 FOR_EACH_EDGE (e1
, ei1
, e
->src
->succs
)
2267 if (EDGE_COUNT (e1
->dest
->succs
) == 0)
2276 if (gimple_code (cond_stmt
) == GIMPLE_COND
)
2278 /* The true edge corresponds to the uninteresting condition.
2279 Add the negated predicate(s) for the edge to record
2280 the interesting condition. */
2282 one_pred
.pred_lhs
= gimple_cond_lhs (cond_stmt
);
2283 one_pred
.pred_rhs
= gimple_cond_rhs (cond_stmt
);
2284 one_pred
.cond_code
= gimple_cond_code (cond_stmt
);
2285 one_pred
.invert
= !!(e
->flags
& EDGE_FALSE_VALUE
);
2287 t_chain
.safe_push (one_pred
);
2289 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
2291 fprintf (dump_file
, "one_pred = ");
2292 dump_pred_info (one_pred
);
2293 fputc ('\n', dump_file
);
2296 has_valid_pred
= true;
2298 else if (gswitch
*gs
= dyn_cast
<gswitch
*> (cond_stmt
))
2300 /* Avoid quadratic behavior. */
2301 if (gimple_switch_num_labels (gs
) > MAX_SWITCH_CASES
)
2303 has_valid_pred
= false;
2306 /* Find the case label. */
2309 for (idx
= 0; idx
< gimple_switch_num_labels (gs
); ++idx
)
2311 tree tl
= gimple_switch_label (gs
, idx
);
2312 if (e
->dest
== label_to_block (cfun
, CASE_LABEL (tl
)))
2323 /* If more than one label reaches this block or the case
2324 label doesn't have a single value (like the default one)
2329 && !operand_equal_p (CASE_LOW (l
), CASE_HIGH (l
), 0)))
2331 has_valid_pred
= false;
2336 one_pred
.pred_lhs
= gimple_switch_index (gs
);
2337 one_pred
.pred_rhs
= CASE_LOW (l
);
2338 one_pred
.cond_code
= EQ_EXPR
;
2339 one_pred
.invert
= false;
2340 t_chain
.safe_push (one_pred
);
2341 has_valid_pred
= true;
2345 /* Disabled. See PR 90994.
2346 has_valid_pred = false; */
2351 if (!has_valid_pred
)
2354 m_preds
.safe_push (t_chain
);
2357 if (DEBUG_PREDICATE_ANALYZER
&& dump_file
)
2359 fprintf (dump_file
, "init_from_control_deps {%s}:\n",
2360 format_edge_vecs (dep_chains
, num_chains
).c_str ());
2365 gcc_assert (m_preds
.length () != 0);
2367 /* Clear M_PREDS to indicate failure. */
2371 /* Return the predicate expression guarding the definition of
2372 the interesting variable. When INVERT is set, return the logical
2373 NOT of the predicate. */
2376 predicate::def_expr (bool invert
/* = false */) const
2378 /* The predicate is stored in an inverted form. */
2379 return build_pred_expr (m_preds
, !invert
);
2382 /* Return the predicate expression guarding the use of the interesting
2383 variable or null if the use predicate hasn't been determined yet. */
2386 predicate::use_expr () const
2391 /* Return a logical AND expression with the (optionally inverted) predicate
2392 expression guarding the definition of the interesting variable and one
2393 guarding its use. Return null if the use predicate hasn't yet been
2397 predicate::expr (bool invert
/* = false */) const
2402 tree expr
= build_pred_expr (m_preds
, !invert
);
2403 return build2 (TRUTH_AND_EXPR
, boolean_type_node
, expr
, m_use_expr
);