This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PING]^2 New if-combining pass
On Mon, 11 Jun 2007, Richard Guenther wrote:
> On Sun, 10 Jun 2007, Richard Guenther wrote:
>
> > On 6/10/07, Mark Mitchell <mark@codesourcery.com> wrote:
> > > Richard Guenther wrote:
> > > > On 5/17/07, Richard Guenther <rguenther@suse.de> wrote:
> > > > >
> > > > > [PATCH] New if-combining pass, addresses PRs 15353 and 31657
> > > > > http://gcc.gnu.org/ml/gcc-patches/2007-04/msg01703.html
> > > > >
> > > > > (with pass-oder swapped)
> > >
> > > This patch is OK.
> > >
> > > What does this patch do for code size on (say) CSiBE when compiling with
> > > -Os? I'm not concerned about the particular benchmark, but I would like
> > > to understand if there's any size impact. (I can well imagine it would
> > > be helpful for -Os: eliminating control flow instructions in lieu of a
> > > logical instruction. However, on an architecture with predication, it
> > > might be harmful if we introduce a logical instruction where we could
> > > otherwise use predication.
> >
> > I'll do a CSiBE compare tomorrow.
>
> Results are (x86_64, -Os) 3473918 bytes with the patch and 3473968 without
> (that's a 0.0015% improvement). Compile and runtimes are slightly better
> with the patch but I consider that noise (the machine was not completely
> idle).
>
> I'll re-post what I commit (I had to do some adjustments due to the cfg
> changes and improved commentary while at it) after the df-branch merge
> settled.
This is what I'll commit shortly. Re-bootstrapped and tested on
x86_64-unknown-linux-gnu (which looks good after the df-branch merge).
Changes vs. previously posted version are comment updates and some
variable renames, two testcase adjustments omitted (that went in
with some other patch) and two checks for CFG structure removed that
turned out to be 1) unnecessary, 2) after cfg_cleanup changes make
the transformation no longer trigger.
Thanks,
Richard.
2007-04-24 Richard Guenther <rguenther@suse.de>
PR tree-optimization/15353
PR tree-optimization/31657
* passes.c (init_optimization_passes): Add pass_tree_ifcombine.
* timevar.def: Add TV_TREE_IFCOMBINE.
* tree-pass.h (pass_tree_ifcombine): Declare.
* tree-ssa-ifcombine.c: New file.
* tree-ssa-phiopt.c (blocks_in_phiopt_order): Export.
* tree-flow.h (blocks_in_phiopt_order): Declare.
* Makefile.in (OBJS-common): Add tree-ssa-ifcombine.o.
(tree-ssa-ifcombine.o): New dependencies.
* gcc.c-torture/execute/20070424-1.c: New testcase.
* gcc.dg/tree-ssa/ssa-ifcombine-1.c: Likewise.
* gcc.dg/tree-ssa/ssa-ifcombine-2.c: Likewise.
* gcc.dg/tree-ssa/ssa-ifcombine-3.c: Likewise.
* gcc.dg/tree-ssa/ssa-ifcombine-4.c: Likewise.
* gcc.dg/tree-ssa/ssa-ifcombine-5.c: Likewise.
Index: gcc/passes.c
===================================================================
*** gcc.orig/passes.c 2007-05-29 11:31:40.000000000 +0200
--- gcc/passes.c 2007-06-11 11:53:26.000000000 +0200
*************** init_optimization_passes (void)
*** 546,551 ****
--- 546,552 ----
opportunities. */
NEXT_PASS (pass_phi_only_cprop);
+ NEXT_PASS (pass_tree_ifcombine);
NEXT_PASS (pass_phiopt);
NEXT_PASS (pass_may_alias);
NEXT_PASS (pass_tail_recursion);
Index: gcc/timevar.def
===================================================================
*** gcc.orig/timevar.def 2007-05-25 11:00:59.000000000 +0200
--- gcc/timevar.def 2007-06-11 11:51:21.000000000 +0200
*************** DEFTIMEVAR (TV_REG_STACK , "
*** 173,178 ****
--- 173,179 ----
DEFTIMEVAR (TV_FINAL , "final")
DEFTIMEVAR (TV_SYMOUT , "symout")
DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
+ DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine")
/* Everything else in rest_of_compilation not included above. */
DEFTIMEVAR (TV_REST_OF_COMPILATION , "rest of compilation")
Index: gcc/tree-pass.h
===================================================================
*** gcc.orig/tree-pass.h 2007-05-29 11:31:39.000000000 +0200
--- gcc/tree-pass.h 2007-06-11 11:51:21.000000000 +0200
*************** extern struct tree_opt_pass pass_warn_fu
*** 293,298 ****
--- 293,299 ----
extern struct tree_opt_pass pass_phiopt;
extern struct tree_opt_pass pass_forwprop;
extern struct tree_opt_pass pass_phiprop;
+ extern struct tree_opt_pass pass_tree_ifcombine;
extern struct tree_opt_pass pass_dse;
extern struct tree_opt_pass pass_nrv;
extern struct tree_opt_pass pass_mark_used_blocks;
Index: gcc/tree-ssa-ifcombine.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/tree-ssa-ifcombine.c 2007-06-11 13:47:00.000000000 +0200
***************
*** 0 ****
--- 1,614 ----
+ /* Combining of if-expressions on trees.
+ Copyright (C) 2007 Free Software Foundation, Inc.
+ Contributed by Richard Guenther <rguenther@suse.de>
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING. If not, write to
+ the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA. */
+
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ #include "basic-block.h"
+ #include "timevar.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-pass.h"
+ #include "tree-dump.h"
+
+ /* 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.
+
+ It does so by walking basic blocks in a approximate reverse
+ post-dominator order and trying to match CFG patterns that
+ represent logical and or logical or of two COND_EXPRs.
+ Transformations are done if the COND_EXPR conditions match
+ either
+
+ 1. two single bit tests X & (1 << Yn) (for logical and)
+
+ 2. two bit tests X & Yn (for logical or)
+
+ 3. two comparisons X OPn Y (for logical or)
+
+ To simplify this pass, removing basic blocks and dead code
+ is left to CFG cleanup and DCE. */
+
+
+ /* Recognize a if-then-else CFG pattern starting to match with the
+ COND_BB basic-block containing the COND_EXPR. The recognized
+ then end else blocks are stored to *THEN_BB and *ELSE_BB. If
+ *THEN_BB and/or *ELSE_BB are already set, they are required to
+ match the then and else basic-blocks to make the pattern match.
+ Returns true if the pattern matched, false otherwise. */
+
+ static bool
+ recognize_if_then_else (basic_block cond_bb,
+ basic_block *then_bb, basic_block *else_bb)
+ {
+ edge t, e;
+
+ if (EDGE_COUNT (cond_bb->succs) != 2)
+ return false;
+
+ /* Find the then/else edges. */
+ t = EDGE_SUCC (cond_bb, 0);
+ e = EDGE_SUCC (cond_bb, 1);
+ if (!(t->flags & EDGE_TRUE_VALUE))
+ {
+ edge tmp = t;
+ t = e;
+ e = tmp;
+ }
+ if (!(t->flags & EDGE_TRUE_VALUE)
+ || !(e->flags & EDGE_FALSE_VALUE))
+ return false;
+
+ /* Check if the edge destinations point to the required block. */
+ if (*then_bb
+ && t->dest != *then_bb)
+ return false;
+ if (*else_bb
+ && e->dest != *else_bb)
+ return false;
+
+ if (!*then_bb)
+ *then_bb = t->dest;
+ if (!*else_bb)
+ *else_bb = e->dest;
+
+ return true;
+ }
+
+ /* Verify if the basic block BB does not have side-effects. Return
+ true in this case, else false. */
+
+ static bool
+ bb_no_side_effects_p (basic_block bb)
+ {
+ block_stmt_iterator bsi;
+
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+ stmt_ann_t ann = stmt_ann (stmt);
+
+ if (ann->has_volatile_ops
+ || !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ 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. */
+
+ static bool
+ same_phi_args_p (basic_block bb1, basic_block bb2, basic_block dest)
+ {
+ edge e1 = find_edge (bb1, dest);
+ edge e2 = find_edge (bb2, dest);
+ tree phi;
+
+ for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
+ if (!operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, e1),
+ PHI_ARG_DEF_FROM_EDGE (phi, e2), 0))
+ return false;
+
+ return true;
+ }
+
+ /* Recognize a single bit test pattern in COND_EXPR and its defining
+ statements. Store the name being tested in *NAME and the bit
+ in *BIT. The COND_EXPR computes *NAME & (1 << *BIT).
+ Returns true if the pattern matched, false otherwise. */
+
+ static bool
+ recognize_single_bit_test (tree cond_expr, tree *name, tree *bit)
+ {
+ tree t;
+
+ /* Get at the definition of the result of the bit test. */
+ t = TREE_OPERAND (cond_expr, 0);
+ if (TREE_CODE (t) == NE_EXPR
+ && integer_zerop (TREE_OPERAND (t, 1)))
+ t = TREE_OPERAND (t, 0);
+ if (TREE_CODE (t) != SSA_NAME)
+ return false;
+ t = SSA_NAME_DEF_STMT (t);
+ if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
+ return false;
+ t = GIMPLE_STMT_OPERAND (t, 1);
+
+ /* 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;
+ D.1987_7 = op0 & 1;
+ if (D.1987_7 != 0) */
+ if (TREE_CODE (t) == BIT_AND_EXPR
+ && integer_onep (TREE_OPERAND (t, 1))
+ && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
+ {
+ t = TREE_OPERAND (t, 0);
+ do {
+ t = SSA_NAME_DEF_STMT (t);
+ if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
+ return false;
+ t = GIMPLE_STMT_OPERAND (t, 1);
+ if (TREE_CODE (t) == NOP_EXPR
+ || TREE_CODE (t) == CONVERT_EXPR)
+ t = TREE_OPERAND (t, 0);
+ } while (TREE_CODE (t) == SSA_NAME);
+
+ if (TREE_CODE (t) == RSHIFT_EXPR)
+ {
+ /* op0 & (1 << op1) */
+ *bit = TREE_OPERAND (t, 1);
+ *name = TREE_OPERAND (t, 0);
+ }
+ else
+ {
+ /* t & 1 */
+ *bit = integer_one_node;
+ *name = t;
+ }
+
+ return true;
+ }
+
+ /* Another form is
+ D.1987_7 = op0 & (1 << CST)
+ if (D.1987_7 != 0) */
+ if (TREE_CODE (t) == BIT_AND_EXPR
+ && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
+ && integer_pow2p (TREE_OPERAND (t, 1)))
+ {
+ *name = TREE_OPERAND (t, 0);
+ *bit = build_int_cst (integer_type_node,
+ tree_log2 (TREE_OPERAND (t, 1)));
+ return true;
+ }
+
+ /* Another form is
+ D.1986_6 = 1 << control1_4(D)
+ D.1987_7 = op0 & D.1986_6
+ if (D.1987_7 != 0) */
+ if (TREE_CODE (t) == BIT_AND_EXPR
+ && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
+ && TREE_CODE (TREE_OPERAND (t, 1)) == SSA_NAME)
+ {
+ tree tmp;
+
+ /* Both arguments of the BIT_AND_EXPR can be the single-bit
+ specifying expression. */
+ tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 0));
+ if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
+ && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
+ {
+ *name = TREE_OPERAND (t, 1);
+ *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
+ return true;
+ }
+
+ tmp = SSA_NAME_DEF_STMT (TREE_OPERAND (t, 1));
+ if (TREE_CODE (tmp) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (tmp, 1)) == LSHIFT_EXPR
+ && integer_onep (TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 0)))
+ {
+ *name = TREE_OPERAND (t, 0);
+ *bit = TREE_OPERAND (GIMPLE_STMT_OPERAND (tmp, 1), 1);
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ /* Recognize a bit test pattern in COND_EXPR and its defining
+ statements. Store the name being tested in *NAME and the bits
+ in *BITS. The COND_EXPR computes *NAME & *BITS.
+ Returns true if the pattern matched, false otherwise. */
+
+ static bool
+ recognize_bits_test (tree cond_expr, tree *name, tree *bits)
+ {
+ tree t;
+
+ /* Get at the definition of the result of the bit test. */
+ t = TREE_OPERAND (cond_expr, 0);
+ if (TREE_CODE (t) == NE_EXPR
+ && integer_zerop (TREE_OPERAND (t, 1)))
+ t = TREE_OPERAND (t, 0);
+ if (TREE_CODE (t) != SSA_NAME)
+ return false;
+ t = SSA_NAME_DEF_STMT (t);
+ if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
+ return false;
+ t = GIMPLE_STMT_OPERAND (t, 1);
+
+ if (TREE_CODE (t) != BIT_AND_EXPR)
+ return false;
+
+ *name = TREE_OPERAND (t, 0);
+ *bits = TREE_OPERAND (t, 1);
+
+ return true;
+ }
+
+ /* 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. */
+
+ static bool
+ ifcombine_ifandif (basic_block inner_cond_bb, basic_block outer_cond_bb)
+ {
+ block_stmt_iterator bsi;
+ tree inner_cond, outer_cond;
+ tree name1, name2, bit1, bit2;
+
+ inner_cond = last_stmt (inner_cond_bb);
+ if (!inner_cond
+ || TREE_CODE (inner_cond) != COND_EXPR)
+ return false;
+
+ outer_cond = last_stmt (outer_cond_bb);
+ if (!outer_cond
+ || TREE_CODE (outer_cond) != COND_EXPR)
+ 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)
+ && name1 == name2)
+ {
+ tree t, t2;
+
+ /* Do it. */
+ bsi = bsi_for_stmt (inner_cond);
+ t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
+ integer_one_node, bit1);
+ t2 = fold_build2 (LSHIFT_EXPR, TREE_TYPE (name1),
+ integer_one_node, bit2);
+ t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), t, t2);
+ t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
+ t2 = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
+ t2 = force_gimple_operand_bsi (&bsi, t2, true, NULL_TREE);
+ COND_EXPR_COND (inner_cond) = fold_build2 (EQ_EXPR, boolean_type_node,
+ t2, t);
+ update_stmt (inner_cond);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ COND_EXPR_COND (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");
+ }
+
+ 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. */
+
+ static bool
+ ifcombine_iforif (basic_block inner_cond_bb, basic_block outer_cond_bb)
+ {
+ tree inner_cond, outer_cond;
+ tree name1, name2, bits1, bits2;
+
+ inner_cond = last_stmt (inner_cond_bb);
+ if (!inner_cond
+ || TREE_CODE (inner_cond) != COND_EXPR)
+ return false;
+
+ outer_cond = last_stmt (outer_cond_bb);
+ if (!outer_cond
+ || TREE_CODE (outer_cond) != COND_EXPR)
+ 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
+ test for name & (bits1 | bits2) != 0. */
+ if (recognize_bits_test (inner_cond, &name1, &bits1)
+ && recognize_bits_test (outer_cond, &name2, &bits2))
+ {
+ block_stmt_iterator bsi;
+ tree t;
+
+ /* Find the common name which is bit-tested. */
+ if (name1 == name2)
+ ;
+ else if (bits1 == bits2)
+ {
+ t = name2;
+ name2 = bits2;
+ bits2 = t;
+ t = name1;
+ name1 = bits1;
+ bits1 = t;
+ }
+ else if (name1 == bits2)
+ {
+ t = name2;
+ name2 = bits2;
+ bits2 = t;
+ }
+ else if (bits1 == name2)
+ {
+ t = name1;
+ name1 = bits1;
+ bits1 = t;
+ }
+ else
+ return false;
+
+ /* Do it. */
+ bsi = bsi_for_stmt (inner_cond);
+ t = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (name1), bits1, bits2);
+ t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
+ t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (name1), name1, t);
+ t = force_gimple_operand_bsi (&bsi, t, true, NULL_TREE);
+ COND_EXPR_COND (inner_cond) = fold_build2 (NE_EXPR, boolean_type_node, t,
+ build_int_cst (TREE_TYPE (t), 0));
+ update_stmt (inner_cond);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ COND_EXPR_COND (outer_cond) = boolean_false_node;
+ update_stmt (outer_cond);
+
+ 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;
+ }
+
+ /* See if we have two comparisons that we can merge into one.
+ This happens for C++ operator overloading where for example
+ GE_EXPR is implemented as GT_EXPR || EQ_EXPR. */
+ else if (COMPARISON_CLASS_P (COND_EXPR_COND (inner_cond))
+ && COMPARISON_CLASS_P (COND_EXPR_COND (outer_cond))
+ && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 0),
+ TREE_OPERAND (COND_EXPR_COND (outer_cond), 0), 0)
+ && operand_equal_p (TREE_OPERAND (COND_EXPR_COND (inner_cond), 1),
+ TREE_OPERAND (COND_EXPR_COND (outer_cond), 1), 0))
+ {
+ tree ccond1 = COND_EXPR_COND (inner_cond);
+ tree ccond2 = COND_EXPR_COND (outer_cond);
+ enum tree_code code1 = TREE_CODE (ccond1);
+ enum tree_code code2 = TREE_CODE (ccond2);
+ enum tree_code code;
+ tree t;
+
+ #define CHK(a,b) ((code1 == a ## _EXPR && code2 == b ## _EXPR) \
+ || (code2 == a ## _EXPR && code1 == b ## _EXPR))
+ /* Merge the two condition codes if possible. */
+ if (code1 == code2)
+ code = code1;
+ else if (CHK (EQ, LT))
+ code = LE_EXPR;
+ else if (CHK (EQ, GT))
+ code = GE_EXPR;
+ else if (CHK (LT, LE))
+ code = LE_EXPR;
+ else if (CHK (GT, GE))
+ code = GE_EXPR;
+ else if (INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (ccond1, 0)))
+ || flag_unsafe_math_optimizations)
+ {
+ if (CHK (LT, GT))
+ code = NE_EXPR;
+ else if (CHK (LT, NE))
+ code = NE_EXPR;
+ else if (CHK (GT, NE))
+ code = NE_EXPR;
+ else
+ return false;
+ }
+ /* We could check for combinations leading to trivial true/false. */
+ else
+ return false;
+ #undef CHK
+
+ /* Do it. */
+ t = fold_build2 (code, boolean_type_node,
+ TREE_OPERAND (ccond2, 0), TREE_OPERAND (ccond2, 1));
+ COND_EXPR_COND (inner_cond) = t;
+ update_stmt (inner_cond);
+
+ /* Leave CFG optimization to cfg_cleanup. */
+ COND_EXPR_COND (outer_cond) = boolean_false_node;
+ update_stmt (outer_cond);
+
+ 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;
+ }
+
+ /* 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_ifcombine_bb (basic_block inner_cond_bb)
+ {
+ basic_block then_bb = NULL, else_bb = NULL;
+
+ 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))
+ {
+ basic_block outer_cond_bb = single_pred (inner_cond_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 (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))
+ {
+ /* We have
+ <outer_cond_bb>
+ if (q) goto inner_cond_bb; else goto else_bb;
+ <inner_cond_bb>
+ if (p) goto ...; else goto else_bb;
+ ...
+ <else_bb>
+ ...
+ */
+ return ifcombine_ifandif (inner_cond_bb, outer_cond_bb);
+ }
+
+ /* 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 (recognize_if_then_else (outer_cond_bb, &then_bb, &inner_cond_bb)
+ && same_phi_args_p (outer_cond_bb, inner_cond_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;
+ <inner_cond_bb>
+ if (q) goto then_bb; else goto ...;
+ <then_bb>
+ ...
+ */
+ return ifcombine_iforif (inner_cond_bb, outer_cond_bb);
+ }
+ }
+
+ return false;
+ }
+
+ /* Main entry for the tree if-conversion pass. */
+
+ static unsigned int
+ tree_ssa_ifcombine (void)
+ {
+ basic_block *bbs;
+ bool cfg_changed = false;
+ int i;
+
+ bbs = blocks_in_phiopt_order ();
+
+ for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; ++i)
+ {
+ basic_block bb = bbs[i];
+ tree stmt = last_stmt (bb);
+
+ if (stmt
+ && TREE_CODE (stmt) == COND_EXPR)
+ cfg_changed |= tree_ssa_ifcombine_bb (bb);
+ }
+
+ free (bbs);
+
+ return cfg_changed ? TODO_cleanup_cfg : 0;
+ }
+
+ static bool
+ gate_ifcombine (void)
+ {
+ return 1;
+ }
+
+ struct tree_opt_pass pass_tree_ifcombine = {
+ "ifcombine", /* name */
+ gate_ifcombine, /* gate */
+ tree_ssa_ifcombine, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_IFCOMBINE, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func
+ | TODO_ggc_collect
+ | TODO_update_ssa
+ | TODO_verify_ssa, /* todo_flags_finish */
+ 0 /* letter */
+ };
Index: gcc/Makefile.in
===================================================================
*** gcc.orig/Makefile.in 2007-06-11 11:47:09.000000000 +0200
--- gcc/Makefile.in 2007-06-11 11:52:20.000000000 +0200
*************** OBJS-common = \
*** 1117,1122 ****
--- 1117,1123 ----
tree-ssa-dom.o \
tree-ssa-dse.o \
tree-ssa-forwprop.o \
+ tree-ssa-ifcombine.o \
tree-ssa-live.o \
tree-ssa-loop-ch.o \
tree-ssa-loop-im.o \
*************** tree-ssa-forwprop.o : tree-ssa-forwprop.
*** 1940,1945 ****
--- 1941,1949 ----
$(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
$(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(TIMEVAR_H) \
langhooks.h $(FLAGS_H)
+ tree-ssa-ifcombine.o : tree-ssa-ifcombine.c $(CONFIG_H) $(SYSTEM_H) \
+ coretypes.h $(TM_H) $(TREE_H) $(BASIC_BLOCK_H) \
+ $(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) $(DIAGNOSTIC_H) $(TIMEVAR_H)
tree-ssa-phiopt.o : tree-ssa-phiopt.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(GGC_H) $(TREE_H) $(RTL_H) $(TM_P_H) $(BASIC_BLOCK_H) \
$(TREE_FLOW_H) tree-pass.h $(TREE_DUMP_H) langhooks.h $(FLAGS_H) \
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-1.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-1.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,16 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ /* Testcase for PR31657. */
+
+ int foo (int x, int a, int b)
+ {
+ if (x & (1 << a))
+ if (x & (1 << b))
+ /* 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/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-2.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-2.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,23 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ /* Testcase for PR31657. */
+
+ int foo (int x, int a, int b)
+ {
+ /* if ((x & a) || (x & b)) */
+ if (x & a)
+ goto doit;
+ if (x & b)
+ goto doit;
+
+ /* else */
+ return 0;
+
+ /* then - returing 1 causes phiopt to trigger */
+ doit:
+ return 2;
+ }
+
+ /* { dg-final { scan-tree-dump "\\|" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-3.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-3.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,23 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ /* Testcase extracted from PR15353. */
+
+ int foo (int x, int a)
+ {
+ /* if ((x > a) || (x == a)) */
+ if (x > a)
+ goto doit;
+ if (x == a)
+ goto doit;
+
+ /* else */
+ return 0;
+
+ /* then - returing 1 causes phiopt to trigger */
+ doit:
+ return 2;
+ }
+
+ /* { dg-final { scan-tree-dump ">=" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-4.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-4.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,21 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ /* Testcase extracted from PR15353. */
+
+ extern void bar(void);
+
+ void foo (int x, int a)
+ {
+ /* if ((x < a) || (x != a)) return; else bar (); */
+ if (x < a)
+ return;
+ if (x != a)
+ return;
+
+ /* else */
+ bar ();
+ }
+
+ /* { dg-final { scan-tree-dump "!=" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/tree-flow.h
===================================================================
*** gcc.orig/tree-flow.h 2007-06-11 11:47:08.000000000 +0200
--- gcc/tree-flow.h 2007-06-11 11:51:21.000000000 +0200
*************** extern tree get_vectype_for_scalar_type
*** 962,967 ****
--- 962,968 ----
/* In tree-ssa-phiopt.c */
bool empty_block_p (basic_block);
+ basic_block *blocks_in_phiopt_order (void);
/* In tree-ssa-loop*.c */
Index: gcc/tree-ssa-phiopt.c
===================================================================
*** gcc.orig/tree-ssa-phiopt.c 2007-06-11 11:47:08.000000000 +0200
--- gcc/tree-ssa-phiopt.c 2007-06-11 11:51:21.000000000 +0200
*************** static bool minmax_replacement (basic_bl
*** 45,51 ****
static bool abs_replacement (basic_block, basic_block,
edge, edge, tree, tree, tree);
static void replace_phi_edge_with_variable (basic_block, edge, tree, tree);
- static basic_block *blocks_in_phiopt_order (void);
/* This pass tries to replaces an if-then-else block with an
assignment. We have four kinds of transformations. Some of these
--- 45,50 ----
*************** tree_ssa_phiopt (void)
*** 247,253 ****
that if a block X has just a single predecessor Y, then Y is after X in the
ordering. */
! static basic_block *
blocks_in_phiopt_order (void)
{
basic_block x, y;
--- 246,252 ----
that if a block X has just a single predecessor Y, then Y is after X in the
ordering. */
! basic_block *
blocks_in_phiopt_order (void)
{
basic_block x, y;
Index: gcc/testsuite/gcc.c-torture/execute/20070424-1.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.c-torture/execute/20070424-1.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,27 ----
+ extern void abort (void);
+ extern void exit (int);
+
+ void do_exit (void) { exit (0); }
+ void do_abort (void) { abort (); }
+
+ void foo (int x, int a)
+ {
+ if (x < a)
+ goto doit;
+ do_exit ();
+ if (x != a)
+ goto doit;
+
+ /* else */
+ do_abort ();
+ return;
+
+ doit:
+ do_abort ();
+ }
+
+ int main()
+ {
+ foo (1, 0);
+ return 0;
+ }
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-5.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-ifcombine-5.c 2007-06-11 11:51:21.000000000 +0200
***************
*** 0 ****
--- 1,20 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-optimized" } */
+
+ /* Testcase from PR15353. */
+
+ int g(void);
+ int h(void);
+ int f(int *i, int *j)
+ {
+ while (1)
+ {
+ if (*i > *j || *i == *j)
+ break;
+ return g();
+ }
+ return h();
+ }
+
+ /* { dg-final { scan-tree-dump ">=" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */