Hello,
the second patch extends the tree-ssa-ifcombine pass so, that it chains up
simple if-and/or-if patterns via associative bitwise-and/or operations. This
allows for example optimization for cases like:
if (c == 0) return 2;
if (c == 1) return 2;
if (c == 2) return 2;
...
as now reassociation-pass can optimize on them.
ChangeLog
2011-11-06 Kai Tietz <kti...@redhat.com>
* tree-ssa-ifcombine.c (remove_stmt_chain): New helper.
(update_gimple_cond_condtion_from_tree): Likewise.
(stmt_no_side_effects_p): Likewise.
(bb_no_side_effects_p): Use stmt_no_side_effects_p.
(bb_no_side_effects_p_2): New helper function.
(same_phi_args_p_2): Likewise.
(recognize_single_bit_test): Allow equal and not-equal
comparison handling.
(ifcombine_ifandif): Handle equal and not-equal
(X & CST) !=/== 0 optimization.
(ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb.
(ifcombine_iforif_merge): Likewise.
(ifcombine_iforif): Simplify routine.
(tree_ssa_ifmerge_bb): New helper for doing if-branch merging.
(tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif
and ifandif.
(tree_ssa_ifcombine): Add if-branch merging and allow
multiple folding for if-combining.
ChangeLog testsuite
2011-11-06 Kai Tietz <kti...@redhat.com>
* gcc.dg/tree-ssa/phi-opt-2.c: Adjust test.
* gcc.dg/tree-ssa/ifcombine-8.c: New test.
* gcc.dg/tree-ssa/ifcombine-9.c: New test.
* gcc.dg/tree-ssa/ifcombine-10.c: New test.
* gcc.dg/tree-ssa/ifcombine-11.c: New test.
* gcc.dg/tree-ssa/ifcombine-12.c: New test.
Bootstrapped and regression-tested for x86_64-unknown-linux-gnu for all
languages (include Ada and Obj-C++). Ok for apply?
Regards,
Kai
ChangeLog
2011-11-06 Kai Tietz <kti...@redhat.com>
* tree-ssa-ifcombine.c (remove_stmt_chain): New helper.
(update_gimple_cond_condtion_from_tree): Likewise.
(stmt_no_side_effects_p): Likewise.
(bb_no_side_effects_p): Use stmt_no_side_effects_p.
(bb_no_side_effects_p_2): New helper function.
(same_phi_args_p_2): Likewise.
(recognize_single_bit_test): Allow equal and not-equal
comparison handling.
(ifcombine_ifandif): Handle equal and not-equal
(X & CST) !=/== 0 optimization.
(ifcombine_ifandif_merge): New helper for tree_ssa_ifmerge_bb.
(ifcombine_iforif_merge): Likewise.
(ifcombine_iforif): Simplify routine.
(tree_ssa_ifmerge_bb): New helper for doing if-branch merging.
(tree_ssa_ifcombine_bb): Adjust pattern-searching for iforif
and ifandif.
(tree_ssa_ifcombine): Add if-branch merging and allow
multiple folding for if-combining.
ChangeLog testsuite
2011-11-06 Kai Tietz <kti...@redhat.com>
* gcc.dg/tree-ssa/phi-opt-2.c: Adjust test.
* gcc.dg/tree-ssa/ifcombine-8.c: New test.
* gcc.dg/tree-ssa/ifcombine-9.c: New test.
* gcc.dg/tree-ssa/ifcombine-10.c: New test.
* gcc.dg/tree-ssa/ifcombine-11.c: New test.
* gcc.dg/tree-ssa/ifcombine-12.c: New test.
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
===================================================================
--- gcc-trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/phi-opt-2.c
@@ -10,7 +10,7 @@ _Bool f1(_Bool a, _Bool b)
else
return 0;
}
- return 0;
+ return 2;
}
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+ if ((x & 4) == 0)
+ if ((x & 8) != 0)
+ /* returning 1 causes phiopt to trigger in */
+ return 2;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 8" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+ if ((x & 4) != 0)
+ if ((x & 8) == 0)
+ /* returning 1 causes phiopt to trigger in */
+ return 2;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "== 4" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+ if ((x & 4) != 0)
+ return 2;
+ if ((x & 8) != 0)
+ /* returning 1 causes phiopt to trigger in */
+ return 2;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { scan-tree-dump "!= 0" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-optimized" } */
+
+int foo (int x, int a, int b)
+{
+ int c = 1 << a;
+ if ((x & c) == 0)
+ if ((x & (1 << b)) == 0)
+ /* returning 1 causes phiopt to trigger in */
+ return 2;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\|" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
===================================================================
--- /dev/null
+++ gcc-trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O -fdump-tree-ifcombine" } */
+
+int foo (int x)
+{
+ if ((x & 4) == 0)
+ if ((x & 8) == 0)
+ /* returning 1 causes phiopt to trigger in */
+ return 2;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "\\& 12" "ifcombine" } } */
+/* { dg-final { cleanup-tree-dump "ifcombine" } } */
Index: gcc-trunk/gcc/tree-ssa-ifcombine.c
===================================================================
--- gcc-trunk.orig/gcc/tree-ssa-ifcombine.c
+++ gcc-trunk/gcc/tree-ssa-ifcombine.c
@@ -49,6 +49,65 @@ along with GCC; see the file COPYING3.
To simplify this pass, removing basic blocks and dead code
is left to CFG cleanup and DCE. */
+/* Remove def stmt of VAR if VAR has zero uses and recurse
+ on rhs1, rhs2, and rhs3 operand if so. */
+
+static void
+remove_stmt_chain (tree var)
+{
+ gimple stmt;
+ gimple_stmt_iterator gsi;
+ tree var2, var3;
+
+ while (1)
+ {
+ if (TREE_CODE (var) != SSA_NAME || !has_zero_uses (var))
+ return;
+ stmt = SSA_NAME_DEF_STMT (var);
+ if (!stmt || !is_gimple_assign (stmt))
+ return;
+ var = gimple_assign_rhs1 (stmt);
+ var2 = var3 = NULL_TREE;
+
+ switch (get_gimple_rhs_class (gimple_assign_rhs_code (stmt)))
+ {
+ case GIMPLE_TERNARY_RHS:
+ var3 = gimple_assign_rhs3 (stmt);
+ /* Fall through. */
+ case GIMPLE_BINARY_RHS:
+ var2 = gimple_assign_rhs2 (stmt);
+ break;
+ default:
+ break;
+ }
+ gsi = gsi_for_stmt (stmt);
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ /* Recurse on optional second and third operand,
+ if those arguments are of kind SSA_NAME. */
+ if (var2 && TREE_CODE (var2) == SSA_NAME)
+ remove_stmt_chain (var2);
+ if (var3 && TREE_CODE (var3) == SSA_NAME)
+ remove_stmt_chain (var3);
+ }
+}
+
+/* Helper to update a gimple_cond condition by tree
+ and remove use-chains of old condition. */
+
+static void
+update_gimple_cond_condition_from_tree (gimple cond, tree t)
+{
+ tree l, r;
+ l = gimple_cond_lhs (cond);
+ r = gimple_cond_rhs (cond);
+ gimple_cond_set_condition_from_tree (cond, t);
+ update_stmt (cond);
+ if (l)
+ remove_stmt_chain (l);
+ if (r)
+ remove_stmt_chain (r);
+}
/* Recognize a if-then-else CFG pattern starting to match with the
COND_BB basic-block containing the COND_EXPR. The recognized
@@ -95,6 +154,25 @@ recognize_if_then_else (basic_block cond
return true;
}
+/* Check that a statement STMT doesn't have sider-effect.
+ and it doesn't have VUSE.
+ If CHECK_TRAP is true, then additional STMT gets checked
+ for trapping. */
+
+static bool
+stmt_no_side_effects_p (gimple stmt, bool check_trap)
+{
+ if (!stmt)
+ return true;
+ if (gimple_code (stmt) == GIMPLE_LABEL)
+ return false;
+ if (gimple_has_side_effects (stmt)
+ || (check_trap && gimple_could_trap_p (stmt))
+ || gimple_vuse (stmt))
+ return false;
+ return true;
+}
+
/* Verify if the basic block BB does not have side-effects. Return
true in this case, else false. */
@@ -105,16 +183,31 @@ bb_no_side_effects_p (basic_block bb)
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
-
- if (gimple_has_side_effects (stmt)
- || gimple_vuse (stmt))
+ if (!stmt_no_side_effects_p (gsi_stmt (gsi), false))
return false;
}
return true;
}
+/* Verify if the basic block BB does not have side-effects, or trapping.
+ Return true in this case, else false. */
+
+static bool
+bb_no_side_effects_p_2 (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ if (!stmt_no_side_effects_p (gsi_stmt (gsi), true))
+ return false;
+ }
+
+ return true;
+}
+
+
/* Verify if all PHI node arguments in DEST for edges from BB1 or
BB2 to DEST are the same. This makes the CFG merge point
free from side-effects. Return true in this case, else false. */
@@ -138,6 +231,59 @@ same_phi_args_p (basic_block bb1, basic_
return true;
}
+/* Verify if all PHI node arguments in DEST1 for edges from BB1, BB2
+ or DEST2 to DEST1 are the same. This makes the CFG merge point
+ free from side-effects. Return true in this case, else false.
+ If DEST1 is not equal to DEST2, then DEST2 has to have a PHI node
+ in DEST1 and DEST2 has not hold statements or its own PHI node.
+ In contrast to same_phi_args_p, function returns for no-PHI valued
+ branches FALSE. */
+
+static bool
+same_phi_args_p_2 (basic_block bb1, basic_block bb2, basic_block dest1,
basic_block dest2)
+{
+ edge e1 = find_edge (bb1, dest1);
+ edge e2 = find_edge (bb2, dest2);
+ gimple_stmt_iterator gsi1;
+ gimple_stmt_iterator gsi2;
+ gimple phi;
+
+ gsi1 = gsi_start_phis (dest1);
+ if (gsi_end_p (gsi1))
+ {
+ gsi2 = gsi_start_phis (dest2);
+ return false;
+ }
+
+ /* See if we can't find a PHI in DEST2 and that we find
+ a PHI edge in DEST1 for DEST2. */
+ gsi2 = gsi_start_phis (dest2);
+ if (gsi_end_p (gsi2))
+ {
+ /* If DEST2 has no PHI, then it also has not to contain
+ any statements. */
+ if (last_stmt (dest2) != NULL)
+ return false;
+ gsi2 = gsi1;
+ /* See if we can find DEST2 within PHI of DEST1. */
+ e2 = find_edge (dest2, dest1);
+ if (!e2)
+ return false;
+ }
+ else if (dest1 != dest2)
+ return false;
+
+ for (; !gsi_end_p (gsi1); gsi_next (&gsi1))
+ {
+ phi = gsi_stmt (gsi1);
+ if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
+ PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
+ return false;
+ }
+
+ return true;
+}
+
/* Return the best representative SSA name for CANDIDATE which is used
in a bit test. */
@@ -165,15 +311,19 @@ get_name_for_bit_test (tree candidate)
/* Recognize a single bit test pattern in GIMPLE_COND and its defining
statements. Store the name being tested in *NAME and the bit
in *BIT. The GIMPLE_COND computes *NAME & (1 << *BIT).
+ The GIMPLE_COND code is either NE_EXPR or EQ_EXPR.
+ IS_CMPEQ will be set to true, if comparison is EQ_EXPR, otherwise
+ to false.
Returns true if the pattern matched, false otherwise. */
static bool
-recognize_single_bit_test (gimple cond, tree *name, tree *bit)
+recognize_single_bit_test (gimple cond, tree *name, tree *bit, bool *is_cmpeq)
{
gimple stmt;
/* Get at the definition of the result of the bit test. */
- if (gimple_cond_code (cond) != NE_EXPR
+ if ((gimple_cond_code (cond) != NE_EXPR
+ && gimple_cond_code (cond) != EQ_EXPR)
|| TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
|| !integer_zerop (gimple_cond_rhs (cond)))
return false;
@@ -181,6 +331,8 @@ recognize_single_bit_test (gimple cond,
if (!is_gimple_assign (stmt))
return false;
+ *is_cmpeq = (gimple_cond_code (cond) == EQ_EXPR);
+
/* Look at which bit is tested. One form to recognize is
D.1985_5 = state_3(D) >> control1_4(D);
D.1986_6 = (int) D.1985_5;
@@ -306,62 +458,82 @@ ifcombine_ifandif (basic_block inner_con
gimple_stmt_iterator gsi;
gimple inner_cond, outer_cond;
tree name1, name2, bit1, bit2;
+ bool is_cmpeq1, is_cmpeq2;
inner_cond = last_stmt (inner_cond_bb);
- if (!inner_cond
- || gimple_code (inner_cond) != GIMPLE_COND)
- return false;
-
outer_cond = last_stmt (outer_cond_bb);
- if (!outer_cond
- || gimple_code (outer_cond) != GIMPLE_COND)
- return false;
/* See if we test a single bit of the same name in both tests. In
that case remove the outer test, merging both else edges,
and change the inner one to test for
name & (bit1 | bit2) == (bit1 | bit2). */
- if (recognize_single_bit_test (inner_cond, &name1, &bit1)
- && recognize_single_bit_test (outer_cond, &name2, &bit2)
+ if (recognize_single_bit_test (inner_cond, &name1, &bit1, &is_cmpeq1)
+ && recognize_single_bit_test (outer_cond, &name2, &bit2, &is_cmpeq2)
&& name1 == name2)
{
- tree t, t2;
+ tree t, t1, t2;
/* Do it. */
gsi = gsi_for_stmt (inner_cond);
- t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
+ t1 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
build_int_cst (TREE_TYPE (name1), 1), bit1);
t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
build_int_cst (TREE_TYPE (name1), 1), bit2);
- t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
+ t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t1, t2);
t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
true, GSI_SAME_STMT);
+ if (!is_cmpeq1 && !is_cmpeq2)
+ t1 = t;
+ else if (is_cmpeq1 && is_cmpeq2)
+ t1 = build_int_cst (TREE_TYPE (name1), 0);
+ else if (!is_cmpeq1)
+ {
+ t1 = force_gimple_operand_gsi (&gsi, t1, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
+ else if (!is_cmpeq2)
+ {
+ t1 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+ }
+
t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
t2 = force_gimple_operand_gsi (&gsi, t2, true, NULL_TREE,
true, GSI_SAME_STMT);
- t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t);
- t = canonicalize_cond_expr_cond (t);
- if (!t)
- return false;
- gimple_cond_set_condition_from_tree (inner_cond, t);
- update_stmt (inner_cond);
-
- /* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
- update_stmt (outer_cond);
-
- if (dump_file)
- {
- fprintf (dump_file, "optimizing double bit test to ");
- print_generic_expr (dump_file, name1, 0);
- fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
- print_generic_expr (dump_file, bit1, 0);
- fprintf (dump_file, ") | (1 << ");
- print_generic_expr (dump_file, bit2, 0);
- fprintf (dump_file, ")\n");
+ t = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1);
+
+ if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE)
+ {
+ update_gimple_cond_condition_from_tree (inner_cond, t);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ update_gimple_cond_condition_from_tree (outer_cond,
boolean_true_node);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "optimizing double bit test to ");
+ print_generic_expr (dump_file, name1, 0);
+ fprintf (dump_file, " & T == %s\n",
+ (!is_cmpeq1 && !is_cmpeq2 ? "T"
+ : (is_cmpeq1 == is_cmpeq2
+ ? "0" : "Q")));
+ fprintf (dump_file, "with temporary T = (1 << ");
+ print_generic_expr (dump_file, bit1, 0);
+ fprintf (dump_file, ") | (1 << ");
+ print_generic_expr (dump_file, bit2, 0);
+ fprintf (dump_file, ")\n");
+ if (is_cmpeq1 != is_cmpeq2)
+ {
+ fprintf (dump_file, "with temporary Q = (1 << ");
+ if (!is_cmpeq1)
+ print_generic_expr (dump_file, bit1, 0);
+ else
+ print_generic_expr (dump_file, bit2, 0);
+ fprintf (dump_file, ")\n");
+ }
+ }
+ return true;
}
-
- return true;
}
/* See if we have two comparisons that we can merge into one. */
@@ -370,27 +542,96 @@ ifcombine_ifandif (basic_block inner_con
{
tree t;
- if (!(t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
- gimple_cond_lhs (inner_cond),
- gimple_cond_rhs (inner_cond),
- gimple_cond_code (outer_cond),
- gimple_cond_lhs (outer_cond),
- gimple_cond_rhs (outer_cond))))
- return false;
- t = canonicalize_cond_expr_cond (t);
- if (!t)
- return false;
- gimple_cond_set_condition_from_tree (inner_cond, t);
+ if ((t = maybe_fold_and_comparisons (gimple_cond_code (inner_cond),
+ gimple_cond_lhs (inner_cond),
+ gimple_cond_rhs (inner_cond),
+ gimple_cond_code (outer_cond),
+ gimple_cond_lhs (outer_cond),
+ gimple_cond_rhs (outer_cond)))
+ != NULL
+ && (t = canonicalize_cond_expr_cond (t)) != NULL)
+ {
+ update_gimple_cond_condition_from_tree (inner_cond, t);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ update_gimple_cond_condition_from_tree (outer_cond,
boolean_true_node);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "optimizing two comparisons to ");
+ print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* If-convert on a and pattern with a common else block. The inner
+ if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+ Returns true if the edges to the common else basic-block were merged
+ via binary-and. */
+
+static bool
+ifcombine_ifandif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb)
+{
+ gimple_stmt_iterator gsi;
+ gimple inner_cond, outer_cond;
+
+ inner_cond = last_stmt (inner_cond_bb);
+ outer_cond = last_stmt (outer_cond_bb);
+
+ if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+ && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
+ {
+ tree t_l, t_r, t, l, r;
+ location_t loc;
+
+ loc = gimple_location (outer_cond);
+ t_l = fold_build2_loc (loc,
+ gimple_cond_code (outer_cond),
+ boolean_type_node,
+ gimple_cond_lhs (outer_cond),
+ gimple_cond_rhs (outer_cond));
+ if (tree_could_trap_p (t_l))
+ return false;
+ loc = gimple_location (inner_cond);
+ t_r = fold_build2_loc (loc,
+ gimple_cond_code (inner_cond),
+ boolean_type_node,
+ gimple_cond_lhs (inner_cond),
+ gimple_cond_rhs (inner_cond));
+
+ if (tree_could_trap_p (t_r))
+ return false;
+ gsi = gsi_for_stmt (inner_cond);
+ t = fold_build2 (BIT_AND_EXPR, boolean_type_node,
+ t_l, t_r);
+ t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+
+ gsi = gsi_for_stmt (inner_cond);
+
+ l = gimple_cond_lhs (inner_cond);
+ r = gimple_cond_rhs (inner_cond);
+ gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node);
update_stmt (inner_cond);
+ remove_stmt_chain (l);
+ if (r)
+ remove_stmt_chain (r);
/* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_true_node);
- update_stmt (outer_cond);
+ update_gimple_cond_condition_from_tree (outer_cond, boolean_true_node);
if (dump_file)
{
- fprintf (dump_file, "optimizing two comparisons to ");
- print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, "branching if.and.if to ");
+ print_generic_expr (dump_file, t_l, 0);
+ fprintf (dump_file, " & ");
+ print_generic_expr (dump_file, t_r, 0);
fprintf (dump_file, "\n");
}
@@ -408,18 +649,12 @@ ifcombine_ifandif (basic_block inner_con
static bool
ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
{
+ gimple_stmt_iterator gsi;
gimple inner_cond, outer_cond;
tree name1, name2, bits1, bits2;
inner_cond = last_stmt (inner_cond_bb);
- if (!inner_cond
- || gimple_code (inner_cond) != GIMPLE_COND)
- return false;
-
outer_cond = last_stmt (outer_cond_bb);
- if (!outer_cond
- || gimple_code (outer_cond) != GIMPLE_COND)
- return false;
/* See if we have two bit tests of the same name in both tests.
In that case remove the outer test and change the inner one to
@@ -427,7 +662,6 @@ ifcombine_iforif (basic_block inner_cond
if (recognize_bits_test (inner_cond, &name1, &bits1)
&& recognize_bits_test (outer_cond, &name2, &bits2))
{
- gimple_stmt_iterator gsi;
tree t;
/* Find the common name which is bit-tested. */
@@ -486,28 +720,26 @@ ifcombine_iforif (basic_block inner_cond
true, GSI_SAME_STMT);
t = fold_build2 (NE_EXPR, boolean_type_node, t,
build_int_cst (TREE_TYPE (t), 0));
- t = canonicalize_cond_expr_cond (t);
- if (!t)
- return false;
- gimple_cond_set_condition_from_tree (inner_cond, t);
- update_stmt (inner_cond);
-
- /* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
- update_stmt (outer_cond);
+ if ((t = canonicalize_cond_expr_cond (t)) != NULL_TREE)
+ {
+ update_gimple_cond_condition_from_tree (inner_cond, t);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ update_gimple_cond_condition_from_tree (outer_cond,
boolean_false_node);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "optimizing bits or bits test to ");
+ print_generic_expr (dump_file, name1, 0);
+ fprintf (dump_file, " & T != 0\nwith temporary T = ");
+ print_generic_expr (dump_file, bits1, 0);
+ fprintf (dump_file, " | ");
+ print_generic_expr (dump_file, bits2, 0);
+ fprintf (dump_file, "\n");
+ }
- if (dump_file)
- {
- fprintf (dump_file, "optimizing bits or bits test to ");
- print_generic_expr (dump_file, name1, 0);
- fprintf (dump_file, " & T != 0\nwith temporary T = ");
- print_generic_expr (dump_file, bits1, 0);
- fprintf (dump_file, " | ");
- print_generic_expr (dump_file, bits2, 0);
- fprintf (dump_file, "\n");
+ return true;
}
-
- return true;
}
/* See if we have two comparisons that we can merge into one.
@@ -518,27 +750,97 @@ ifcombine_iforif (basic_block inner_cond
{
tree t;
- if (!(t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
- gimple_cond_lhs (inner_cond),
- gimple_cond_rhs (inner_cond),
- gimple_cond_code (outer_cond),
- gimple_cond_lhs (outer_cond),
- gimple_cond_rhs (outer_cond))))
- return false;
- t = canonicalize_cond_expr_cond (t);
- if (!t)
- return false;
- gimple_cond_set_condition_from_tree (inner_cond, t);
+ if ((t = maybe_fold_or_comparisons (gimple_cond_code (inner_cond),
+ gimple_cond_lhs (inner_cond),
+ gimple_cond_rhs (inner_cond),
+ gimple_cond_code (outer_cond),
+ gimple_cond_lhs (outer_cond),
+ gimple_cond_rhs (outer_cond)))
+ != NULL
+ && (t = canonicalize_cond_expr_cond (t)) != NULL)
+ {
+ update_gimple_cond_condition_from_tree (inner_cond, t);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ update_gimple_cond_condition_from_tree (outer_cond,
boolean_false_node);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "optimizing two comparisons to ");
+ print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* If-convert on a or pattern with a common then block. The inner
+ if is specified by its INNER_COND_BB, the outer by OUTER_COND_BB.
+ Returns true, if the edges leading to the common then basic-block
+ were merged via binary-or. */
+
+static bool
+ifcombine_iforif_merge (basic_block inner_cond_bb, basic_block outer_cond_bb)
+{
+ gimple_stmt_iterator gsi;
+ gimple inner_cond, outer_cond;
+
+ inner_cond = last_stmt (inner_cond_bb);
+ outer_cond = last_stmt (outer_cond_bb);
+
+ if (TREE_CODE_CLASS (gimple_cond_code (inner_cond)) == tcc_comparison
+ && TREE_CODE_CLASS (gimple_cond_code (outer_cond)) == tcc_comparison)
+ {
+ tree t_l, t_r, t, l, r;
+ location_t loc;
+
+ loc = gimple_location (outer_cond);
+ t_l = fold_build2_loc (loc,
+ gimple_cond_code (outer_cond),
+ boolean_type_node,
+ gimple_cond_lhs (outer_cond),
+ gimple_cond_rhs (outer_cond));
+
+ if (tree_could_trap_p (t_l))
+ return false;
+ loc = gimple_location (inner_cond);
+ t_r = fold_build2_loc (loc,
+ gimple_cond_code (inner_cond),
+ boolean_type_node,
+ gimple_cond_lhs (inner_cond),
+ gimple_cond_rhs (inner_cond));
+
+ if (tree_could_trap_p (t_r))
+ return false;
+ gsi = gsi_for_stmt (inner_cond);
+ t = fold_build2 (BIT_IOR_EXPR, boolean_type_node,
+ t_l, t_r);
+ t = force_gimple_operand_gsi (&gsi, t, true, NULL_TREE,
+ true, GSI_SAME_STMT);
+
+ gsi = gsi_for_stmt (inner_cond);
+ l = gimple_cond_lhs (inner_cond);
+ r = gimple_cond_rhs (inner_cond);
+ gimple_cond_set_condition (inner_cond, NE_EXPR, t, boolean_false_node);
update_stmt (inner_cond);
+ if (l)
+ remove_stmt_chain (l);
+ if (r)
+ remove_stmt_chain (r);
/* Leave CFG optimization to cfg_cleanup. */
- gimple_cond_set_condition_from_tree (outer_cond, boolean_false_node);
- update_stmt (outer_cond);
+ update_gimple_cond_condition_from_tree (outer_cond, boolean_false_node);
if (dump_file)
{
- fprintf (dump_file, "optimizing two comparisons to ");
- print_generic_expr (dump_file, t, 0);
+ fprintf (dump_file, "branching if.or.if to ");
+ print_generic_expr (dump_file, t_l, 0);
+ fprintf (dump_file, " | ");
+ print_generic_expr (dump_file, t_r, 0);
fprintf (dump_file, "\n");
}
@@ -549,68 +851,326 @@ ifcombine_iforif (basic_block inner_cond
}
/* Recognize a CFG pattern and dispatch to the appropriate
+ if-combine helper. We start with BB as the innermost
+ worker basic-block. Returns true if a transformation was done. */
+
+/* Recognize a CFG pattern and dispatch to the appropriate
if-conversion helper. We start with BB as the innermost
worker basic-block. Returns true if a transformation was done. */
static bool
+tree_ssa_ifmerge_bb (basic_block inner_cond_bb)
+{
+ basic_block outer_cond_bb, outer_else_bb, outer_then_bb;
+ basic_block then_bb = NULL, else_bb = NULL;
+ basic_block last_inner_cond_bb;
+ gimple excond;
+ bool cfg_changed = false, in_and_seq = false, in_or_seq = false;
+
+ if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
+ return false;
+
+ /* Has inner bb side-effects? */
+ if (!bb_no_side_effects_p_2 (inner_cond_bb))
+ return false;
+ last_inner_cond_bb = inner_cond_bb;
+
+ do
+ {
+ /* Recognize && and || of two conditions with a common
+ then/else block which entry edges we can merge. That is:
+ if (a || b)
+ ;
+ and
+ if (a && b)
+ ;
+ This requires a single predecessor of the inner cond_bb. */
+ if (!single_pred_p (last_inner_cond_bb))
+ return cfg_changed;
+
+ outer_cond_bb = single_pred (last_inner_cond_bb);
+ outer_else_bb = NULL;
+ outer_then_bb = NULL;
+
+ if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+ &outer_else_bb))
+ return cfg_changed;
+
+ /* Check that last_inner_cond_bb doesn't have side-effects. */
+ if (last_inner_cond_bb != inner_cond_bb
+ && !bb_no_side_effects_p_2 (last_inner_cond_bb))
+ return cfg_changed;
+
+ if (!bb_no_side_effects_p_2 (outer_cond_bb))
+ return cfg_changed;
+
+ /* 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 (last_inner_cond_bb == outer_then_bb
+ && ((else_bb == outer_else_bb
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb))
+ || (outer_else_bb == then_bb
+ && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_else_bb, then_bb)
+ && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_else_bb, else_bb)))
+ && bb_no_side_effects_p_2 (inner_cond_bb))
+ {
+ excond = last_stmt (inner_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND
+ || gimple_cond_true_p (excond)
+ || gimple_cond_false_p (excond))
+ return cfg_changed;
+
+ excond = last_stmt (outer_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND)
+ return cfg_changed;
+
+ if (gimple_cond_true_p (excond))
+ {
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+ else if (gimple_cond_false_p (excond))
+ return cfg_changed;
+
+ if (in_or_seq)
+ return cfg_changed;
+
+ /* We have
+ <outer_cond_bb>
+ if (q) goto inner_cond_bb; else goto outer_else_bb;
+ <inner_cond_bb>
+ if (p) goto ...; else goto else_bb;
+ ...
+ <else_bb>
+ <outer_else_bb>
+ ...
+ If the else_bb,is not equal to outer_else_bb, then the
+ else_bb needs to be empty (no PHIs, no statments) and
+ and the PHI in outer_else_bb for else_bb has to be the
+ same value as PHI value for outer_else_bb. */
+
+ if (!ifcombine_ifandif_merge (inner_cond_bb, outer_cond_bb))
+ return cfg_changed;
+
+ cfg_changed = true;
+ in_and_seq = true;
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+
+ /* The || form is characterized by a common then_bb with the
+ two edges leading to it mergable. The latter is guaranteed
+ by matching PHI arguments in the then_bb and the inner cond_bb
+ having no side-effects. */
+ if (last_inner_cond_bb == outer_else_bb
+ && ((then_bb == outer_then_bb
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb))
+ || (outer_then_bb == else_bb
+ && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_then_bb, else_bb)
+ && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_then_bb, then_bb)))
+ && bb_no_side_effects_p_2 (inner_cond_bb))
+ {
+ excond = last_stmt (inner_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND
+ || gimple_cond_false_p (excond)
+ || gimple_cond_true_p (excond))
+ return cfg_changed;
+
+ excond = last_stmt (outer_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND)
+ return cfg_changed;
+
+ if (gimple_cond_false_p (excond))
+ {
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+ else if (gimple_cond_true_p (excond))
+ return cfg_changed;
+
+ if (in_and_seq)
+ return cfg_changed;
+
+ /* We have
+ <outer_cond_bb>
+ if (q) goto outer_then_bb; else goto inner_cond_bb;
+ <inner_cond_bb>
+ if (q) goto then_bb; else goto ...;
+ <then_bb>
+ <outer-then_bb>
+ ...
+ If the then_bb,is not equal to outer_then_bb, then the
+ then_bb needs to be empty (no PHIs, no statments) and
+ the PHI in outer_then_bb for then_bb has to be the same value
+ as PHI value for outer_then_bb. */
+ if (!ifcombine_iforif_merge (inner_cond_bb, outer_cond_bb))
+ return cfg_changed;
+
+ cfg_changed = true;
+ in_or_seq = true;
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+ }
+ while (0);
+
+ return cfg_changed;
+}
+
+static bool
tree_ssa_ifcombine_bb (basic_block inner_cond_bb)
{
+ basic_block outer_cond_bb, outer_else_bb, outer_then_bb;
basic_block then_bb = NULL, else_bb = NULL;
+ basic_block last_inner_cond_bb;
+ gimple excond;
+ bool in_and_seq = false, in_or_seq = false;
if (!recognize_if_then_else (inner_cond_bb, &then_bb, &else_bb))
return false;
- /* Recognize && and || of two conditions with a common
- then/else block which entry edges we can merge. That is:
- if (a || b)
- ;
- and
- if (a && b)
- ;
- This requires a single predecessor of the inner cond_bb. */
- if (single_pred_p (inner_cond_bb))
+ last_inner_cond_bb = inner_cond_bb;
+ do
{
- basic_block outer_cond_bb = single_pred (inner_cond_bb);
+ /* Recognize && and || of two conditions with a common
+ then/else block which entry edges we can merge. That is:
+ if (a || b)
+ ;
+ and
+ if (a && b)
+ ;
+ This requires a single predecessor of the inner cond_bb. */
+ if (!single_pred_p (last_inner_cond_bb))
+ return false;
+
+ outer_cond_bb = single_pred (last_inner_cond_bb);
+ outer_else_bb = NULL;
+ outer_then_bb = NULL;
+
+ if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+ &outer_else_bb))
+ return false;
+
+ /* Check that last_inner_cond_bb doesn't have side-effects. */
+ if (last_inner_cond_bb != inner_cond_bb
+ && !bb_no_side_effects_p (last_inner_cond_bb))
+ return false;
/* 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 (recognize_if_then_else (outer_cond_bb, &inner_cond_bb, &else_bb)
- && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb)
+ if (last_inner_cond_bb == outer_then_bb
+ && ((else_bb == outer_else_bb
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, else_bb))
+ || (outer_else_bb == then_bb
+ && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_else_bb, then_bb)
+ && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_else_bb, else_bb)))
&& bb_no_side_effects_p (inner_cond_bb))
{
+ excond = last_stmt (inner_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND
+ || gimple_cond_true_p (excond))
+ return false;
+
+ excond = last_stmt (outer_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND)
+ return false;
+
+ if (gimple_cond_true_p (excond))
+ {
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+ else if (gimple_cond_false_p (excond))
+ return false;
+
+ if (in_or_seq)
+ return false;
+
/* We have
<outer_cond_bb>
- if (q) goto inner_cond_bb; else goto else_bb;
+ if (q) goto inner_cond_bb; else goto outer_else_bb;
<inner_cond_bb>
if (p) goto ...; else goto else_bb;
...
<else_bb>
+ <outer_else_bb>
...
- */
- return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+ If the else_bb,is not equal to outer_else_bb, then the
+ else_bb needs to be empty (no PHIs, no statments) and
+ and the PHI in outer_else_bb for else_bb has to be the
+ same value as PHI value for outer_else_bb. */
+ if (ifcombine_ifandif (inner_cond_bb, outer_cond_bb))
+ return true;
+ in_and_seq = true;
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
}
/* The || form is characterized by a common then_bb with the
two edges leading to it mergable. The latter is guaranteed
- by matching PHI arguments in the then_bb and the inner cond_bb
+ by matching PHI arguments in the then_bb and the inner cond_bb
having no side-effects. */
- if (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
- && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb)
+ if (last_inner_cond_bb == outer_else_bb
+ && ((then_bb == outer_then_bb
+ && same_phi_args_p (outer_cond_bb, inner_cond_bb, then_bb))
+ || (outer_then_bb == else_bb
+ && !same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_then_bb, else_bb)
+ && same_phi_args_p_2 (outer_cond_bb, inner_cond_bb,
+ outer_then_bb, then_bb)))
&& bb_no_side_effects_p (inner_cond_bb))
{
+ excond = last_stmt (inner_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND
+ || gimple_cond_false_p (excond))
+ return false;
+
+ excond = last_stmt (outer_cond_bb);
+ if (!excond || gimple_code (excond) != GIMPLE_COND)
+ return false;
+
+ if (gimple_cond_false_p (excond))
+ {
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
+ }
+ else if (gimple_cond_true_p (excond))
+ return false;
+
+ if (in_and_seq)
+ return false;
+
/* We have
<outer_cond_bb>
- if (q) goto then_bb; else goto inner_cond_bb;
+ if (q) goto outer_then_bb; else goto inner_cond_bb;
<inner_cond_bb>
if (q) goto then_bb; else goto ...;
<then_bb>
+ <outer-then_bb>
...
- */
- return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
+ If the then_bb,is not equal to outer_then_bb, then the
+ then_bb needs to be empty (no PHIs, no statments) and
+ the PHI in outer_then_bb for then_bb has to be the same value
+ as PHI value for outer_then_bb. */
+ if (ifcombine_iforif (inner_cond_bb, outer_cond_bb))
+ return true;
+
+ in_or_seq = true;
+ last_inner_cond_bb = outer_cond_bb;
+ continue;
}
}
+ while (0);
return false;
}
@@ -627,6 +1187,7 @@ tree_ssa_ifcombine (void)
bbs = blocks_in_phiopt_order ();
calculate_dominance_info (CDI_DOMINATORS);
+ /* Try to optimize if.and/or.if conditions. */
for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
{
basic_block bb = bbs[i];
@@ -634,7 +1195,27 @@ tree_ssa_ifcombine (void)
if (stmt
&& gimple_code (stmt) == GIMPLE_COND)
- cfg_changed |= tree_ssa_ifcombine_bb (bb);
+ {
+ if (tree_ssa_ifcombine_bb (bb))
+ {
+ cfg_changed = true;
+ --i;
+ }
+ }
+ }
+
+ /* Try to merge if.and/or.if chains. */
+ for (i = n_basic_blocks - NUM_FIXED_BLOCKS; i > 0; --i)
+ {
+ basic_block bb = bbs[i-1];
+ gimple stmt = last_stmt (bb);
+
+ if (stmt
+ && gimple_code (stmt) == GIMPLE_COND)
+ {
+ if (tree_ssa_ifmerge_bb (bb))
+ cfg_changed = true;
+ }
}
free (bbs);
