https://gcc.gnu.org/g:9919ba13180b34d127c45b97117bae0b9036dc13
commit 9919ba13180b34d127c45b97117bae0b9036dc13
Author: Alexandre Oliva <ol...@gnu.org>
Date: Thu Sep 19 06:43:22 2024 -0300
adjust probs after modified ifcombine
Diff:
---
gcc/tree-ssa-ifcombine.cc | 403 +++++++++++++++++++++++++++++++++++++---------
1 file changed, 323 insertions(+), 80 deletions(-)
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index 79ccc70b2678..79f89570acb6 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa.h"
#include "attribs.h"
#include "asan.h"
+#include "bitmap.h"
#ifndef LOGICAL_OP_NON_SHORT_CIRCUIT
#define LOGICAL_OP_NON_SHORT_CIRCUIT \
@@ -49,6 +50,28 @@ along with GCC; see the file COPYING3. If not see
false) >= 2)
#endif
+/* Return TRUE iff COND is NULL, or the condition in it is constant. */
+
+static bool
+constant_condition_p (gcond *cond)
+{
+ if (!cond)
+ return true;
+
+ return (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
+ && CONSTANT_CLASS_P (gimple_cond_rhs (cond)));
+}
+
+/* Return FALSE iff the condition in the COND stmt that ends COND_BB is not
+ constant. */
+
+static bool
+constant_condition_p (basic_block cond_bb)
+{
+ gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
+ return constant_condition_p (cond);
+}
+
/* This pass combines COND_EXPRs to simplify control flow. It
currently recognizes bit tests and comparisons in chains that
represent logical and or logical or of two COND_EXPRs.
@@ -107,12 +130,7 @@ recognize_if_then_else (basic_block cond_bb,
if (!*else_bb)
*else_bb = e->dest;
- gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (cond_bb));
- if (!cond)
- return false;
-
- if (CONSTANT_CLASS_P (gimple_cond_lhs (cond))
- && CONSTANT_CLASS_P (gimple_cond_rhs (cond)))
+ if (constant_condition_p (cond_bb))
return false;
return true;
@@ -364,14 +382,27 @@ recognize_bits_test (gcond *cond, tree *name, tree *bits,
bool inv)
}
-/* Update profile after code in outer_cond_bb was adjusted so
- outer_cond_bb has no condition. */
+/* Update profile after code in either outer_cond_bb or inner_cond_bb was
+ adjusted so that it has no condition. */
static void
update_profile_after_ifcombine (basic_block inner_cond_bb,
basic_block outer_cond_bb)
{
- edge outer_to_inner = find_edge (outer_cond_bb, inner_cond_bb);
+ /* In the following we assume that inner_cond_bb has single predecessor. */
+ gcc_assert (single_pred_p (inner_cond_bb));
+
+ basic_block outer_to_inner_bb = inner_cond_bb;
+ profile_probability prob = profile_probability::always ();
+ for (basic_block parent = single_pred (outer_to_inner_bb);
+ parent != outer_cond_bb;
+ parent = single_pred (outer_to_inner_bb))
+ {
+ prob *= find_edge (parent, outer_to_inner_bb)->probability;
+ outer_to_inner_bb = parent;
+ }
+
+ edge outer_to_inner = find_edge (outer_cond_bb, outer_to_inner_bb);
edge outer2 = (EDGE_SUCC (outer_cond_bb, 0) == outer_to_inner
? EDGE_SUCC (outer_cond_bb, 1)
: EDGE_SUCC (outer_cond_bb, 0));
@@ -382,29 +413,62 @@ update_profile_after_ifcombine (basic_block inner_cond_bb,
std::swap (inner_taken, inner_not_taken);
gcc_assert (inner_taken->dest == outer2->dest);
- /* In the following we assume that inner_cond_bb has single predecessor. */
- gcc_assert (single_pred_p (inner_cond_bb));
+ if (constant_condition_p (outer_cond_bb))
+ {
+ gcc_checking_assert (outer_to_inner_bb == inner_cond_bb);
- /* Path outer_cond_bb->(outer2) needs to be merged into path
- outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
- and probability of inner_not_taken updated. */
+ /* Path outer_cond_bb->(outer2) needs to be merged into path
+ outer_cond_bb->(outer_to_inner)->inner_cond_bb->(inner_taken)
+ and probability of inner_not_taken updated. */
- inner_cond_bb->count = outer_cond_bb->count;
+ inner_cond_bb->count = outer_cond_bb->count;
- /* Handle special case where inner_taken probability is always. In this case
- we know that the overall outcome will be always as well, but combining
- probabilities will be conservative because it does not know that
- outer2->probability is inverse of outer_to_inner->probability. */
- if (inner_taken->probability == profile_probability::always ())
- ;
- else
- inner_taken->probability = outer2->probability +
outer_to_inner->probability
- * inner_taken->probability;
- inner_not_taken->probability = profile_probability::always ()
- - inner_taken->probability;
+ /* Handle special case where inner_taken probability is always. In this
+ case we know that the overall outcome will be always as well, but
+ combining probabilities will be conservative because it does not know
+ that outer2->probability is inverse of
+ outer_to_inner->probability. */
+ if (inner_taken->probability == profile_probability::always ())
+ ;
+ else
+ inner_taken->probability = outer2->probability
+ + outer_to_inner->probability * inner_taken->probability;
+ inner_not_taken->probability = profile_probability::always ()
+ - inner_taken->probability;
- outer_to_inner->probability = profile_probability::always ();
- outer2->probability = profile_probability::never ();
+ outer_to_inner->probability = profile_probability::always ();
+ outer2->probability = profile_probability::never ();
+ }
+ else if (constant_condition_p (inner_cond_bb))
+ {
+ /* Path inner_cond_bb->(inner_taken) needs to be merged into path
+ outer_cond_bb->(outer2). We've accumulated the probabilities from
+ outer_cond_bb->(outer)->...->inner_cond_bb in prob, so we have to
+ adjust that by inner_taken, and make inner unconditional. */
+
+ prob *= inner_taken->probability;
+ outer2->probability += prob;
+ outer_to_inner->probability = profile_probability::always ()
+ - outer2->probability;
+
+ inner_taken->probability = profile_probability::never ();
+ inner_not_taken->probability = profile_probability::always ();
+ }
+ else
+ {
+ /* We've moved part of the inner cond to outer, but we don't know the
+ probabilities for each part, so estimate the effects by moving half of
+ the odds of inner_taken to outer. */
+
+ inner_taken->probability *= profile_probability::even ();
+ inner_not_taken->probability = profile_probability::always ()
+ - inner_taken->probability;
+
+ prob *= inner_taken->probability;
+ outer2->probability += prob;
+ outer_to_inner->probability = profile_probability::always ()
+ - outer2->probability;
+ }
}
/* FIXME: move to a header file. */
@@ -415,6 +479,42 @@ fold_truth_andor_maybe_separate (location_t loc,
enum tree_code rcode, tree rl_arg, tree rr_arg,
tree *separatep);
+static void
+ifcombine_mark_ssa_name (bitmap used, tree name, basic_block outer)
+{
+ if (SSA_NAME_IS_DEFAULT_DEF (name))
+ return;
+
+ gimple *def = SSA_NAME_DEF_STMT (name);
+ basic_block bb = gimple_bb (def);
+ if (!dominated_by_p (CDI_DOMINATORS, bb, outer))
+ return;
+
+ bitmap_set_bit (used, SSA_NAME_VERSION (name));
+}
+
+/* Data structure passed to ifcombine_mark_ssa_name. */
+struct ifcombine_mark_ssa_name_t
+{
+ /* SSA_NAMEs that have been referenced. */
+ bitmap used;
+ /* Dominating block of DEFs that might need moving. */
+ basic_block outer;
+};
+
+/* Mark in DATA->used any SSA_NAMEs used in *t. */
+
+static tree
+ifcombine_mark_ssa_name_walk (tree *t, int *, void *data_)
+{
+ ifcombine_mark_ssa_name_t *data = (ifcombine_mark_ssa_name_t *)data_;
+
+ if (*t && TREE_CODE (*t) == SSA_NAME)
+ ifcombine_mark_ssa_name (data->used, *t, data->outer);
+
+ return NULL;
+}
+
/* Replace the conditions in INNER_COND and OUTER_COND with COND and COND2.
COND and COND2 are computed for insertion at INNER_COND, with OUTER_COND
replaced with a constant, but if there are intervening blocks, it's best to
@@ -426,41 +526,182 @@ ifcombine_replace_cond (gcond *inner_cond, bool
inner_inv,
tree cond, bool must_canon,
tree cond2)
{
- tree t = cond;
- bool result_inv = inner_inv;
+ tree ret = cond;
- /* ??? Support intervening blocks. */
- if (single_pred (gimple_bb (inner_cond)) != gimple_bb (outer_cond))
- return NULL_TREE;
+ /* Split cond into cond2 if they're contiguous. */
+ if (!cond2
+ && TREE_CODE (cond) == TRUTH_ANDIF_EXPR
+ && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
+ {
+ cond2 = TREE_OPERAND (cond, 1);
+ cond = TREE_OPERAND (cond, 0);
+ }
+ if (!cond2
+ && TREE_CODE (cond) == TRUTH_ORIF_EXPR
+ && single_pred (gimple_bb (inner_cond)) == gimple_bb (outer_cond))
+ {
+ gcc_unreachable (); /* ??? Do we ever hit this? */
+ cond2 = TREE_OPERAND (cond, 1);
+ cond = TREE_OPERAND (cond, 0);
+ inner_inv = !inner_inv;
+ outer_inv = !outer_inv;
+ }
- /* ??? Use both conditions. */
- if (cond2)
- t = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (t), cond, cond2);
+ bool outer_p = true /* for experimentation only. */
+ || cond2 || (single_pred (gimple_bb (inner_cond))
+ != gimple_bb (outer_cond));
+ bool result_inv = outer_p ? outer_inv : inner_inv;
- /* ??? Insert at outer_cond. */
if (result_inv)
- t = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (t), t);
- tree ret = t;
+ cond = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond), cond);
- if (tree tcanon = canonicalize_cond_expr_cond (t))
- ret = t = tcanon;
+ if (tree tcanon = canonicalize_cond_expr_cond (cond))
+ cond = tcanon;
else if (must_canon)
return NULL_TREE;
- if (!is_gimple_condexpr_for_cond (t))
+
+ if (outer_p)
{
- gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
- t = force_gimple_operand_gsi_1 (&gsi, t, is_gimple_condexpr_for_cond,
- NULL, true, GSI_SAME_STMT);
- }
- gimple_cond_set_condition_from_tree (inner_cond, t);
- update_stmt (inner_cond);
+ {
+ auto_bitmap used;
+ basic_block outer_bb = gimple_bb (outer_cond);
+
+ /* Mark SSA DEFs that are referenced by cond and may thus need to be
+ moved to outer. */
+ {
+ ifcombine_mark_ssa_name_t data = { used, outer_bb };
+ walk_tree (&cond, ifcombine_mark_ssa_name_walk, &data, NULL);
+ }
+
+ if (!bitmap_empty_p (used))
+ {
+ /* Iterate up from inner_cond, moving DEFs identified as used by
+ cond, and marking USEs in the DEFs for moving as well. */
+ gimple_stmt_iterator gsins = gsi_for_stmt (outer_cond);
+ for (basic_block bb = gimple_bb (inner_cond);
+ bb != outer_bb; bb = single_pred (bb))
+ {
+ for (gimple_stmt_iterator gsitr = gsi_last_bb (bb);
+ !gsi_end_p (gsitr); gsi_prev (&gsitr))
+ {
+ gimple *stmt = gsi_stmt (gsitr);
+ bool move = false;
+ tree t;
+ ssa_op_iter it;
+
+ FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_DEF)
+ if (bitmap_bit_p (used, SSA_NAME_VERSION (t)))
+ {
+ move = true;
+ break;
+ }
+
+ if (!move)
+ continue;
+
+ /* Mark uses in STMT before moving it. */
+ FOR_EACH_SSA_TREE_OPERAND (t, stmt, it, SSA_OP_USE)
+ ifcombine_mark_ssa_name (used, t, outer_bb);
+
+ gsi_move_before (&gsitr, &gsins, GSI_NEW_STMT);
+ }
+
+ /* Surprisingly, there may be PHI nodes in single-predecessor
+ bocks, as in pr50682.C. Fortunately, since they can't
+ involve back edges, there won't be references to parallel
+ nodes that we'd have to pay special attention to to keep
+ them parallel. We can't move the PHI nodes, but we can turn
+ them into assignments. */
+ for (gphi_iterator gsi = gsi_start_phis (bb);
+ !gsi_end_p (gsi);)
+ {
+ gphi *phi = gsi.phi ();
+
+ gcc_assert (gimple_phi_num_args (phi) == 1);
+ tree def = gimple_phi_result (phi);
+
+ if (!bitmap_bit_p (used, SSA_NAME_VERSION (def)))
+ {
+ gsi_next (&gsi);
+ continue;
+ }
+
+ /* Mark uses in STMT before moving it. */
+ use_operand_p use_p;
+ ssa_op_iter it;
+ FOR_EACH_PHI_ARG (use_p, phi, it, SSA_OP_USE)
+ ifcombine_mark_ssa_name (used, USE_FROM_PTR (use_p),
+ outer_bb);
+
+ tree use = gimple_phi_arg_def (phi, 0);
+ location_t loc = gimple_phi_arg_location (phi, 0);
+
+ remove_phi_node (&gsi, false);
+
+ gassign *a = gimple_build_assign (def, use);
+ gimple_set_location (a, loc);
+ gsi_insert_before (&gsins, a, GSI_NEW_STMT);
+ }
+ }
+ }
+ }
+
+ if (!is_gimple_condexpr_for_cond (cond))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (outer_cond);
+ cond = force_gimple_operand_gsi_1 (&gsi, cond,
+ is_gimple_condexpr_for_cond,
+ NULL, true, GSI_SAME_STMT);
+ }
- /* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond,
- outer_inv
- ? boolean_false_node
- : boolean_true_node);
- update_stmt (outer_cond);
+ /* Leave CFG optimization to cfg_cleanup. */
+ gimple_cond_set_condition_from_tree (outer_cond, cond);
+ update_stmt (outer_cond);
+
+ if (cond2)
+ {
+ ret = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (ret), ret, cond2);
+
+ if (inner_inv)
+ cond2 = fold_build1 (TRUTH_NOT_EXPR, TREE_TYPE (cond2), cond2);
+
+ if (tree tcanon = canonicalize_cond_expr_cond (cond2))
+ cond2 = tcanon;
+ if (!is_gimple_condexpr_for_cond (cond2))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
+ cond2 = force_gimple_operand_gsi_1 (&gsi, cond2,
+ is_gimple_condexpr_for_cond,
+ NULL, true, GSI_SAME_STMT);
+ }
+ gimple_cond_set_condition_from_tree (inner_cond, cond2);
+ }
+ else
+ gimple_cond_set_condition_from_tree (inner_cond,
+ inner_inv
+ ? boolean_false_node
+ : boolean_true_node);
+ update_stmt (inner_cond);
+ }
+ else
+ {
+ if (!is_gimple_condexpr_for_cond (cond))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (inner_cond);
+ cond = force_gimple_operand_gsi_1 (&gsi, cond,
+ is_gimple_condexpr_for_cond,
+ NULL, true, GSI_SAME_STMT);
+ }
+ gimple_cond_set_condition_from_tree (inner_cond, cond);
+ update_stmt (inner_cond);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ gimple_cond_set_condition_from_tree (outer_cond,
+ outer_inv
+ ? boolean_false_node
+ : boolean_true_node);
+ update_stmt (outer_cond);
+ }
update_profile_after_ifcombine (gimple_bb (inner_cond),
gimple_bb (outer_cond));
@@ -611,7 +852,7 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
inner_inv,
else if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
&& TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
{
- tree t, ts = NULL_TREE, ts2 = NULL_TREE;
+ tree t, ts = NULL_TREE;
enum tree_code inner_cond_code = gimple_cond_code (inner_cond);
enum tree_code outer_cond_code = gimple_cond_code (outer_cond);
@@ -635,16 +876,16 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
inner_inv,
gimple_cond_lhs (outer_cond),
gimple_cond_rhs (outer_cond),
gimple_bb (outer_cond)))
- && !(t = ts = (fold_truth_andor_maybe_separate
- (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
- boolean_type_node,
- outer_cond_code,
- gimple_cond_lhs (outer_cond),
- gimple_cond_rhs (outer_cond),
- inner_cond_code,
- gimple_cond_lhs (inner_cond),
- gimple_cond_rhs (inner_cond),
- &ts2))))
+ && !(t = (fold_truth_andor_maybe_separate
+ (UNKNOWN_LOCATION, TRUTH_ANDIF_EXPR,
+ boolean_type_node,
+ outer_cond_code,
+ gimple_cond_lhs (outer_cond),
+ gimple_cond_rhs (outer_cond),
+ inner_cond_code,
+ gimple_cond_lhs (inner_cond),
+ gimple_cond_rhs (inner_cond),
+ &ts))))
{
{
tree t1, t2;
@@ -674,7 +915,7 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
inner_inv,
if (!(t = ifcombine_replace_cond (inner_cond, inner_inv,
outer_cond, outer_inv,
- t, false, ts2)))
+ t, false, ts)))
return false;
if (dump_file)
@@ -693,19 +934,21 @@ ifcombine_ifandif (basic_block inner_cond_bb, bool
inner_inv,
/* Helper function for tree_ssa_ifcombine_bb. Recognize a CFG pattern and
dispatch to the appropriate if-conversion helper for a particular
set of INNER_COND_BB, OUTER_COND_BB, THEN_BB and ELSE_BB.
- PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB. */
+ PHI_PRED_BB should be one of INNER_COND_BB, THEN_BB or ELSE_BB.
+ OUTER_SUCC_BB is the successor of OUTER_COND_BB on the path towards
+ INNER_COND_BB. */
static bool
tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb, basic_block outer_cond_bb,
basic_block then_bb, basic_block else_bb,
- basic_block phi_pred_bb)
+ basic_block phi_pred_bb, basic_block outer_succ_bb)
{
/* The && form is characterized by a common else_bb with
the two edges leading to it mergable. The latter is
guaranteed by matching PHI arguments in the else_bb and
the inner cond_bb having no side-effects. */
if (phi_pred_bb != else_bb
- && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
+ && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &else_bb)
&& same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
{
/* We have
@@ -722,7 +965,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb,
basic_block outer_cond_bb,
/* And a version where the outer condition is negated. */
if (phi_pred_bb != else_bb
- && recognize_if_then_else (outer_cond_bb, &else_bb, &inner_cond_bb)
+ && recognize_if_then_else (outer_cond_bb, &else_bb, &outer_succ_bb)
&& same_phi_args_p (outer_cond_bb, phi_pred_bb, else_bb))
{
/* We have
@@ -742,7 +985,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb,
basic_block outer_cond_bb,
by matching PHI arguments in the then_bb and the inner cond_bb
having no side-effects. */
if (phi_pred_bb != then_bb
- && recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
+ && recognize_if_then_else (outer_cond_bb, &then_bb, &outer_succ_bb)
&& same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
{
/* We have
@@ -758,7 +1001,7 @@ tree_ssa_ifcombine_bb_1 (basic_block inner_cond_bb,
basic_block outer_cond_bb,
/* And a version where the outer condition is negated. */
if (phi_pred_bb != then_bb
- && recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &then_bb)
+ && recognize_if_then_else (outer_cond_bb, &outer_succ_bb, &then_bb)
&& same_phi_args_p (outer_cond_bb, phi_pred_bb, then_bb))
{
/* We have
@@ -795,13 +1038,14 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
if (a && b)
;
This requires a single predecessor of the inner cond_bb. */
- for (basic_block bb = inner_cond_bb;
- single_pred_p (bb) && bb_no_side_effects_p (bb); )
+ for (basic_block bb = inner_cond_bb, outer_cond_bb;
+ single_pred_p (bb) && bb_no_side_effects_p (bb);
+ bb = outer_cond_bb)
{
- basic_block outer_cond_bb = bb = single_pred (bb);
+ outer_cond_bb = single_pred (bb);
if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
- then_bb, else_bb, inner_cond_bb))
+ then_bb, else_bb, inner_cond_bb, bb))
return bb;
if (forwarder_block_to (else_bb, then_bb))
@@ -813,7 +1057,7 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
For same_phi_args_p we look at equality of arguments between
edge from outer_cond_bb and the forwarder block. */
if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
- then_bb, else_bb))
+ then_bb, else_bb, bb))
return bb;
}
else if (forwarder_block_to (then_bb, else_bb))
@@ -825,7 +1069,7 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
For same_phi_args_p we look at equality of arguments between
edge from outer_cond_bb and the forwarder block. */
if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb, else_bb,
- then_bb, then_bb))
+ then_bb, then_bb, bb))
return bb;
}
}
@@ -912,7 +1156,7 @@ pass_tree_ifcombine::execute (function *fun)
else
seen = bb;
/* Go back and check whether the modified outer_bb can be further
- optimized. ??? How could it? */
+ optimized. */
do
i++;
while (bbs[i] != outer_bb);
@@ -921,7 +1165,6 @@ pass_tree_ifcombine::execute (function *fun)
if (bb == seen)
{
- gcc_assert (!changed);
seen = NULL;
changed = false;
}
