[gcc(refs/users/aoliva/heads/testme)] adjust probs after modified ifcombine
Alexandre Oliva
aoliva@gcc.gnu.org
Thu Sep 19 10:20:54 GMT 2024
https://gcc.gnu.org/g:04f96e7c8ce32b3a198fd8d3e9c5a929d3a713f1
commit 04f96e7c8ce32b3a198fd8d3e9c5a929d3a713f1
Author: Alexandre Oliva <oliva@gnu.org>
Date: Thu Sep 19 06:43:22 2024 -0300
adjust probs after modified ifcombine
Diff:
---
gcc/tree-ssa-ifcombine.cc | 248 +++++++++++++++++++++++++++++++++-------------
1 file changed, 180 insertions(+), 68 deletions(-)
diff --git a/gcc/tree-ssa-ifcombine.cc b/gcc/tree-ssa-ifcombine.cc
index 79ccc70b2678..4c5f39d9b3e1 100644
--- a/gcc/tree-ssa-ifcombine.cc
+++ b/gcc/tree-ssa-ifcombine.cc
@@ -49,6 +49,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 +129,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 +381,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 +412,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. */
@@ -426,41 +489,86 @@ 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;
+ bool outer_p = cond2 || (single_pred (gimple_bb (inner_cond))
+ != gimple_bb (outer_cond));
+ bool result_inv = outer_p ? outer_inv : inner_inv;
- /* ??? Support intervening blocks. */
- if (single_pred (gimple_bb (inner_cond)) != gimple_bb (outer_cond))
- return NULL_TREE;
-
- /* ??? Use both conditions. */
- if (cond2)
- t = fold_build2 (TRUTH_AND_EXPR, TREE_TYPE (t), cond, cond2);
-
- /* ??? 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);
+ /* ??? Check cond for any SSA_NAMEs that need to be pulled ahead of
+ outer_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);
+ 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);
+ }
+ gimple_cond_set_condition_from_tree (outer_cond, cond);
+ update_stmt (outer_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);
+
+ 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 +719,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 +743,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 +782,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)
@@ -700,6 +808,8 @@ 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)
{
+ /* ??? Check the blocks for non-continuous configurations. */
+
/* 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
@@ -800,6 +910,8 @@ tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
{
basic_block outer_cond_bb = bb = single_pred (bb);
+ /* ??? Pass bb down? */
+
if (tree_ssa_ifcombine_bb_1 (inner_cond_bb, outer_cond_bb,
then_bb, else_bb, inner_cond_bb))
return bb;
More information about the Gcc-cvs
mailing list