[patch optimization]: Improve tree-ssa-ifcombine pass
Kai Tietz
ktietz70@googlemail.com
Thu Oct 13 13:13:00 GMT 2011
Hello,
This patch adds further optimization to gimple's ifcombine pass for single-bit
andif operations.
New patterns recognized are:
* if ((a & 4) == 0) if ((a & 8) == 0) -> if ((a & 12) == 0)
* if ((a & 4) != 0) if ((a & 8) == 0) -> if ((a & 12) == 4)
* if ((a & 4) == 0) if ((a & 8) != 0) -> if ((a & 12) == 8)
To support that, patch adds required additional patterns for
if.and.if, and if.or.if
detection to tree_ssa_ifcombine_bb.
ChangeLog
2011-10-13 Kai Tietz <ktietz@redhat.com>
* tree-ssa-ifcombine.c (same_phi_args_p_2): New
helper for new andif pattern edge PHI comparison.
(recognize_single_bit_test): Add new argument and
allow EQ_EXPR.
(ifcombine_ifandif): Handle == 0 cases.
(tree_ssa_ifcombine_bb): Add new ifandif pattern.
2011-10-13 Kai Tietz <ktietz@redhat.com>
* gcc.dg/tree-ssa/ssa-ifcombine-8.c: New test.
* gcc.dg/tree-ssa/ssa-ifcombine-9.c: New test.
* gcc.dg/tree-ssa/ssa-ifcombine-10.c: New test.
* gcc.dg/tree-ssa/ssa-ifcombine-11.c: New test.
* gcc.dg/tree-ssa/ssa-ifcombine-12.c: New test.
Bootstrapped and regression tested for all languages plus Ada and
Obj-C++ on x86_64-unknown-linux-gnu.
Ok for apply?
Regards,
Kai
Index: gcc/gcc/tree-ssa-ifcombine.c
===================================================================
--- gcc.orig/gcc/tree-ssa-ifcombine.c
+++ gcc/gcc/tree-ssa-ifcombine.c
@@ -138,6 +138,54 @@ 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 be a PHI node
+ in DEST1 and DEST2 has not to have statements or its own PHI node. */
+
+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))
+ return (dest1 == dest2);
+
+ /* 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 +213,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 +233,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,6 +360,7 @@ 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
@@ -321,25 +376,40 @@ ifcombine_ifandif (basic_block inner_con
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 = fold_build2 (EQ_EXPR, boolean_type_node, t2, t1);
t = canonicalize_cond_expr_cond (t);
if (!t)
return false;
@@ -354,11 +424,24 @@ ifcombine_ifandif (basic_block inner_con
{
fprintf (dump_file, "optimizing double bit test to ");
print_generic_expr (dump_file, name1, 0);
- fprintf (dump_file, " & T == T\nwith temporary T = (1 << ");
+ 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;
@@ -571,24 +654,38 @@ tree_ssa_ifcombine_bb (basic_block inner
if (single_pred_p (inner_cond_bb))
{
basic_block outer_cond_bb = single_pred (inner_cond_bb);
+ basic_block outer_else_bb = NULL;
+ basic_block outer_then_bb = NULL;
+
+ if (!recognize_if_then_else (outer_cond_bb, &outer_then_bb,
+ &outer_else_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)
- && bb_no_side_effects_p (inner_cond_bb))
+ if (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))
{
/* 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>
...
- */
+ 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. */
return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
}
@@ -596,18 +693,26 @@ tree_ssa_ifcombine_bb (basic_block inner
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 (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 (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))
{
/* 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>
...
- */
+ 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. */
return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
}
}
Index: gcc/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-8.c
===================================================================
--- /dev/null
+++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-9.c
===================================================================
--- /dev/null
+++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-10.c
===================================================================
--- /dev/null
+++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-11.c
===================================================================
--- /dev/null
+++ gcc/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/gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-12.c
===================================================================
--- /dev/null
+++ gcc/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" } } */
More information about the Gcc-patches
mailing list