[PATCH] if-to-switch pass
Cesar Philippidis
cesar_philippidis@mentor.com
Fri Jun 21 20:37:00 GMT 2013
Here is an updated version of Tom's if-to-switch conversion pass that
was originally posted here:
<http://gcc.gnu.org/ml/gcc-patches/2013-01/msg01210.html>.
I corrected a build problem with ARM by including "tm_p.h" and an ICE
caused by NULL_TREE argument being passed to fold_binary () inside
refine_range_plus (). Also, TODO_ggc_collect has been removed in the
gimple_opt_pass struct.
I bootstrapped and regression tested on x86_64-unknown-linux-gnu and
arm-none-linux-gnueabi. OK for trunk?
Cesar
2013-06-21 Tom de Vries <tom@codesourcery.com>
Cesar Philippidis <cesar@codesourcery.com>
* tree-if-switch-conversion.c: New pass.
* tree-pass.h (pass_if_to_switch): Declare.
* common.opt (ftree-if-to-switch-conversion): New switch.
* opts.c (default_options_table): Set flag_tree_if_to_switch_conversion
at -O2 and higher.
* passes.c (init_optimization_passes): Use new pass.
* doc/invoke.texi (-ftree-if-to-switch-conversion): New item.
(Optimization Options, option -O2): Add -ftree-if-to-switch-conversion.
* Makefile.in (OBJS): Add tree-if-switch-conversion.o.
(tree-if-switch-conversion.o): New rule.
* tree.h (expand_switch_using_bit_tests_p): Declare as extern.
* tree-switch-conversion.c (expand_switch_using_bit_tests_p): Remove
static from definition.
* gcc.dg/if-to-switch.c: New test.
* gcc.dg/if-to-switch.c-2: Same.
* gcc.dg/if-to-switch.c-3: Same.
* gcc.dg/tree-ssa/vrp33.c: Run with -fno-tree-if-to-switch-conversion.
* gcc.dg/tree-ssa/vrp63.c: Same.
* gcc.dg/tree-ssa/vrp64.c: Same.
* gcc.dg/pr21643.c: Same.
-------------- next part --------------
Index: gcc/tree.h
===================================================================
--- gcc/tree.h (revision 200261)
+++ gcc/tree.h (working copy)
@@ -5656,6 +5656,10 @@
extern void expand_stack_restore (tree);
extern void expand_return (tree);
+/* In tree-switch-conversion.c */
+
+extern bool expand_switch_using_bit_tests_p (tree, unsigned int, unsigned int);
+
/* In tree-eh.c */
extern void using_eh_for_cleanups (void);
Index: gcc/tree-if-switch-conversion.c
===================================================================
--- gcc/tree-if-switch-conversion.c (revision 0)
+++ gcc/tree-if-switch-conversion.c (revision 0)
@@ -0,0 +1,1367 @@
+/* Convert a chain of if statements into a switch statement.
+ Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
+ Contributed by Tom de Vries <tom@codesourcery.com>
+
+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 3, 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 COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
+
+/* The following pass converts a chain of ifs into a switch.
+
+ The if-chain has the following properties:
+ - all bbs end in a GIMPLE_COND.
+ - all but the first bb are empty, apart from the GIMPLE_COND.
+ - the GIMPLE_CONDs compare the same variable against integer constants.
+ - the true gotos all target the same bb.
+ - the false gotos target the next in the if-chain.
+
+ F.i., consider the following if-chain:
+ ...
+ <bb 4>:
+ ...
+ if (D.1993_3 == 32)
+ goto <bb 3>;
+ else
+ goto <bb 5>;
+
+ <bb 5>:
+ if (D.1993_3 == 13)
+ goto <bb 3>;
+ else
+ goto <bb 6>;
+
+ <bb 6>:
+ if (D.1993_3 == 10)
+ goto <bb 3>;
+ else
+ goto <bb 7>;
+
+ <bb 7>:
+ if (D.1993_3 == 9)
+ goto <bb 3>;
+ else
+ goto <bb 8>;
+ ...
+
+ The pass will report this if-chain like this:
+ ...
+ var: D.1993_3
+ first: <bb 4>
+ true: <bb 3>
+ last: <bb 7>
+ constants: 9 10 13 32
+ ...
+
+ and then convert the if-chain into a switch:
+ ...
+ <bb 4>:
+ ...
+ switch (D.1993_3) <default: <L8>,
+ case 9: <L7>,
+ case 10: <L7>,
+ case 13: <L7>,
+ case 32: <L7>>
+ ...
+
+ The pass will try to construct a chain for each bb, unless the bb it is
+ already contained in a chain. This ensures that all chains will be found,
+ and that no chain will be constructed twice.
+
+ The pass detect range-checks in analyze_bb as well, and handles them.
+ Simple ones, like 'c <= 5', and more complex ones, like
+ '(unsigned char) c + 247 <= 1', which is generated by the C front-end from
+ code like '(c == 9 || c == 10)' or '(9 <= c && c <= 10)'.
+
+ The if-chain is conceptually similar to a 'reorderable sequence of range
+ conditions' as described in "Efficient and effective branch reordering using
+ profile data" (Yang et. al., 2002).
+ The difference is that for an if-chain the true gotos all target the same bb,
+ such that it is eligible for conversion into a single bit test.
+
+ A few known limitations of the pass:
+ - it does not analyze switch statements as part of an if-chain
+ - it does not analyze if-trees
+ - it does not create larger if-chains by moving a side-effects from a block
+ to it's successor blocks (See 'Making sequences reorderable' in the paper
+ mentioned above). */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+
+#include "gimple.h"
+#include "gimple-pretty-print.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "expr.h"
+#include "tm_p.h"
+
+/* Struct to describe a range [low, high]. */
+
+struct range_def
+{
+ tree high;
+ tree low;
+};
+typedef struct range_def *range;
+
+static struct obstack range_obstack;
+
+static range
+range_alloc (tree high, tree low)
+{
+ size_t obsize = sizeof (struct range_def);
+ range r = (range)obstack_alloc (&range_obstack, obsize);
+ r->high = high;
+ r->low = low;
+ return r;
+}
+
+/* Information we collect about a single bb. */
+
+struct ifsc_info_def
+{
+ /* Variable that is tested to determine the control-flow. */
+ tree var;
+ /* Ranges of constants the variable is compared to. */
+ vec<range, va_gc> *ranges;
+ /* Successor edge of the bb if the comparison is successful. */
+ edge true_edge;
+ /* Successor edge of the bb if the comparison is not successful. */
+ edge false_edge;
+ /* Set if the all the operations in the bb are only used to determine the
+ control-flow. */
+ bool empty;
+ /* Set if the bb is part of a chain. */
+ bool chained;
+};
+typedef struct ifsc_info_def *ifsc_info;
+
+/* Macros to access the fields of struct ifsc_info. */
+
+#define BB_IFSC_VAR(bb) (((ifsc_info)bb->aux)->var)
+#define BB_IFSC_RANGES(bb) (((ifsc_info)bb->aux)->ranges)
+#define BB_IFSC_TRUE_EDGE(bb) (((ifsc_info)bb->aux)->true_edge)
+#define BB_IFSC_FALSE_EDGE(bb) (((ifsc_info)bb->aux)->false_edge)
+#define BB_IFSC_EMPTY(bb) (((ifsc_info)bb->aux)->empty)
+#define BB_IFSC_CHAINED(bb) (((ifsc_info)bb->aux)->chained)
+
+/* Data-type describing an if-chain. */
+
+struct if_chain_def
+{
+ /* First bb in the chain. */
+ basic_block first;
+ /* Last bb in the chain. */
+ basic_block last;
+ /* Variable that all bbs in the chain test to determine control-flow. */
+ tree var;
+ /* Ranges of constants the variable is compared to. */
+ vec<range, va_gc> *ranges;
+ /* Same as previous, but sorted and with duplicates removed. */
+ vec<range, va_gc> *sorted_ranges;
+};
+typedef struct if_chain_def *if_chain;
+
+static struct obstack chain_obstack;
+
+/* Return allocated if_chain. */
+
+static if_chain
+chain_alloc (void)
+{
+ size_t obsize = sizeof (struct if_chain_def);
+ if_chain chain = (if_chain)obstack_alloc (&range_obstack, obsize);
+ vec_alloc (chain->ranges, 8);
+ vec_alloc (chain->sorted_ranges, 8);
+ return chain;
+}
+
+/* Forward declarations. */
+
+static void
+refine_ranges (basic_block, tree *, vec<range, va_gc> **, bool *,
+ unsigned int *);
+
+/* Print RS to F. */
+
+static void
+print_range_vector (FILE *f, vec<range, va_gc> *rs)
+{
+ unsigned int ix;
+ range r;
+
+ FOR_EACH_VEC_ELT (*rs, ix, r)
+ {
+ if (ix != 0)
+ fprintf (f, " ");
+ print_generic_expr (f, r->low, 0);
+ if (r->high)
+ {
+ fprintf (f, "-");
+ print_generic_expr (f, r->high, 0);
+ }
+ }
+ fprintf (f, "\n");
+}
+
+/* Add a range of [LOW, HIGH] to RS. */
+
+static void
+push_range (vec<range, va_gc> **rs, tree high, tree low)
+{
+ range r = range_alloc (high, low);
+ vec_safe_push (*rs, r);
+}
+
+/* Helper function for sort_ranges. */
+
+static int
+compare_ranges (const void *p1, const void *p2)
+{
+ const range r1 = *(const range *const)p1;
+ const range r2 = *(const range *const)p2;
+ bool r1_before_r2, r2_before_r1;
+ tree r1_high, r1_low, r2_high, r2_low;
+
+ r1_low = r1->low;
+ r2_low = r2->low;
+ r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+ r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+ r1_before_r2 = tree_int_cst_compare (r1_high, r2_low) < 0;
+ if (r1_before_r2)
+ return -1;
+
+ r2_before_r1 = tree_int_cst_compare (r2_high, r1_low) < 0;
+ if (r2_before_r1)
+ return 1;
+
+ return tree_int_cst_compare (r1_low, r2_low);
+}
+
+/* Return true if ranges R1 and R2 overlap. */
+
+static bool
+range_overlap (range r1, range r2)
+{
+ tree r1_high, r1_low, r2_high, r2_low;
+ tree f;
+
+ r1_low = r1->low;
+ r2_low = r2->low;
+ r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+ r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+ /* r1 before r2. */
+ f = fold_binary (LT_EXPR, boolean_type_node, r1_high, r2_low);
+ if (tree_int_cst_equal (f, integer_one_node))
+ return false;
+
+ /* r2 before r1. */
+ f = fold_binary (LT_EXPR, boolean_type_node, r2_high, r1_low);
+ if (tree_int_cst_equal (f, integer_one_node))
+ return false;
+
+ return true;
+}
+
+/* Return true if R1 and R2 are adjacent ranges. */
+
+static bool
+range_adjacent (range r1, range r2)
+{
+ tree r1_high, r1_low, r2_high, r2_low;
+ tree r1_high_plus_1, r2_high_plus_1;
+ tree type = TREE_TYPE (r1->low);
+
+ r1_low = r1->low;
+ r2_low = r2->low;
+ r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+ r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+ if (!tree_int_cst_equal (r1_high, TYPE_MAXVAL (type)))
+ {
+ r1_high_plus_1 = fold_binary (PLUS_EXPR, type, r1_high, integer_one_node);
+ if (tree_int_cst_equal (r1_high_plus_1, r2_low))
+ return true;
+ }
+
+ if (!tree_int_cst_equal (r2_high, TYPE_MAXVAL (type)))
+ {
+ r2_high_plus_1 = fold_binary (PLUS_EXPR, type, r2_high, integer_one_node);
+ if (tree_int_cst_equal (r2_high_plus_1, r1_low))
+ return true;
+ }
+
+ return false;
+}
+
+/* Return combined range if R1 and R2 overlap, otherwise return NULL. */
+
+static range
+combine_ranges (range r1, range r2)
+{
+ tree low, high;
+ tree r1_high, r1_low, r2_high, r2_low;
+
+ if (!r1 || !r2
+ || (!range_overlap (r1, r2)
+ && !range_adjacent (r1, r2)))
+ return NULL;
+
+ r1_low = r1->low;
+ r2_low = r2->low;
+ r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+ r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+ low = fold_binary (MIN_EXPR, TREE_TYPE (r1_low), r1_low, r2_low);
+ high = fold_binary (MAX_EXPR, TREE_TYPE (r1_high), r1_high, r2_high);
+
+ if (tree_int_cst_equal (low, high))
+ high = NULL_TREE;
+
+ return range_alloc (high, low);
+}
+
+/* Sort ranges in RANGES and copy to sorted_ranges, while combining overlapping
+ ranges. */
+
+static void
+sort_ranges (vec<range, va_gc> *ranges, vec<range, va_gc> **sorted_ranges)
+{
+ unsigned int ix;
+ range prev = NULL, r;
+
+ /* Sort ranges. */
+ ranges->qsort (compare_ranges);
+
+ FOR_EACH_VEC_ELT (*ranges, ix, r)
+ {
+ range m = combine_ranges (prev, r);
+ if (m)
+ {
+ prev = m;
+ continue;
+ }
+ if (prev)
+ vec_safe_push (*sorted_ranges, prev);
+ prev = r;
+ }
+ if (prev)
+ vec_safe_push (*sorted_ranges, prev);
+}
+
+/* Find the true and false edge of a GIMPLE_COND bb BB and return them in
+ TRUE_EDGE and FALSE_EDGE. */
+
+static void
+get_edges (basic_block bb, edge *true_edge, edge *false_edge)
+{
+ edge e0, e1;
+ int e0_true;
+
+ e0 = EDGE_SUCC (bb, 0);
+ e1 = EDGE_SUCC (bb, 1);
+
+ e0_true = e0->flags & EDGE_TRUE_VALUE;
+
+ *true_edge = e0_true ? e0 : e1;
+ *false_edge = e0_true ? e1 : e0;
+}
+
+/* Attempt to express the comparison of VAR against range [LOW, HIGH] in terms
+ of another var, if the defining stmt of VAR is a cast, and return true
+ if successful. Increment NR_STMTS with the number of stmts in BB that were
+ used to implement the comparison. */
+
+static bool
+refine_range_cast (tree *var, tree high, tree low, unsigned int *nr_stmts)
+{
+ tree op1;
+ tree f1, f2;
+ gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+ if (!is_gimple_assign (stmt)
+ || gimple_assign_rhs_code (stmt) != NOP_EXPR)
+ return false;
+
+ /* Gimple stmt is a signed to unsigned cast. */
+ op1 = gimple_assign_rhs1 (stmt);
+ if (TREE_TYPE (*var) != unsigned_type_for (TREE_TYPE (op1)))
+ return false;
+
+ /* Test if the low-high range is representable in the signed type. */
+ f1 = fold_binary (GE_EXPR, boolean_type_node, low, integer_zero_node);
+ if (!tree_int_cst_equal (f1, integer_one_node))
+ return false;
+ f2 = fold_binary (LE_EXPR, boolean_type_node, high ? high : low,
+ TYPE_MAXVAL (TREE_TYPE (op1)));
+ if (!tree_int_cst_equal (f2, integer_one_node))
+ return false;
+
+ *var = op1;
+ (*nr_stmts)++;
+ return true;
+}
+
+/* Attempt to express the comparison of VAR against range [LOW, HIGH] in terms
+ of another var, if the defining stmt of VAR is a PLUS_EXPR, and return true
+ if successful. Increment NR_STMTS with the number of stmts in BB that were
+ used to implement the comparison. */
+
+static bool
+refine_range_plus (tree *var, tree *high, tree *low,
+ unsigned int *nr_stmts)
+{
+ tree op1, op2, offset;
+ tree new_low, new_high, new_var, cmp;
+ gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+ if (!stmt
+ || !is_gimple_assign (stmt)
+ || gimple_assign_rhs_code (stmt) != PLUS_EXPR
+ || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (*var))
+ || *high == NULL_TREE)
+ return false;
+
+ op1 = gimple_assign_rhs1 (stmt);
+ op2 = gimple_assign_rhs2 (stmt);
+
+ if (!TREE_CONSTANT (op1)
+ && !TREE_CONSTANT (op2))
+ return false;
+
+ new_var = TREE_CONSTANT (op1) ? op2 : op1;
+ offset = TREE_CONSTANT (op1) ? op1 : op2;
+
+ /* Need integral switch var. */
+ if (TREE_CODE (new_var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (new_var)))
+ return false;
+
+ new_low = fold_binary (MINUS_EXPR, TREE_TYPE (new_var), *low, offset);
+ new_high = (fold_binary (MINUS_EXPR, TREE_TYPE (new_var), *high, offset));
+
+ cmp = fold_binary (LE_EXPR, TREE_TYPE (new_var), new_low, new_high);
+
+ if (!tree_int_cst_equal (cmp, integer_one_node))
+ {
+ /* Todo: Represent this as 2 ranges. */
+ return false;
+ }
+
+ *high = new_high;
+ *low = new_low;
+ *var = new_var;
+
+ (*nr_stmts)++;
+ return true;
+}
+
+/* Analyze comparison STMT, and if successful, return true. Returns in VAR the
+ comparison var, and in [LOW, HIGH] the comparison range. Increment NR_STMTS
+ with the number of stmts in BB that were used to implement the
+ comparison. */
+
+static bool
+get_constant_comparison (gimple stmt, tree *var, tree *high, tree *low,
+ unsigned int *nr_stmts)
+{
+ tree op1, op2;
+ enum tree_code code;
+
+ if (!stmt || !is_gimple_assign (stmt))
+ return false;
+
+ code = gimple_assign_rhs_code (stmt);
+ switch (code)
+ {
+ case EQ_EXPR:
+ case LE_EXPR:
+ case GE_EXPR:
+ break;
+ case LT_EXPR:
+ case GT_EXPR:
+ /* Todo. */
+ return false;
+ default:
+ return false;
+ }
+
+ *var = NULL_TREE;
+ *high = NULL_TREE;
+ *low = NULL_TREE;
+
+ op1 = gimple_assign_rhs1 (stmt);
+ op2 = gimple_assign_rhs2 (stmt);
+
+ if (!TREE_CONSTANT (op1)
+ && !TREE_CONSTANT (op2))
+ return false;
+
+ /* Normalize comparison into (var code constant). */
+ *var = TREE_CONSTANT (op1) ? op2 : op1;
+ *low = TREE_CONSTANT (op1) ? op1 : op2;
+ code = TREE_CONSTANT (op1) ? swap_tree_comparison (code) : code;
+
+ /* Need integral switch var. */
+ if (TREE_CODE (*var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (*var)))
+ return false;
+
+ if (code == GE_EXPR)
+ *high = TYPE_MAXVAL (TREE_TYPE (*var));
+ else if (code == LE_EXPR)
+ {
+ *high = *low;
+ *low = TYPE_MINVAL (TREE_TYPE (*var));
+ }
+
+ (*nr_stmts)++;
+ return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in terms of another
+ var, if the defining stmt of VAR is and BIT_IOR_EXPR, and return true if
+ successful. Increment NR_STMTS with the number of stmts in BB that were used
+ to implement the comparison. */
+
+static bool
+refine_range_bit_ior (tree *var, vec<range, va_gc> **ranges,
+ unsigned int *nr_stmts)
+{
+ tree op1, op2;
+ tree op1_var, op2_var, op_const_high, op_const_low;
+ gimple op_def;
+ gimple stmt = SSA_NAME_DEF_STMT (*var);
+ basic_block bb;
+ vec<range, va_gc> *op_ranges1;
+ vec<range, va_gc> *op_ranges2;
+
+ if (!stmt
+ || !is_gimple_assign (stmt)
+ || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
+ return false;
+
+ bb = gimple_bb (stmt);
+
+ op1 = gimple_assign_rhs1 (stmt);
+ op2 = gimple_assign_rhs2 (stmt);
+
+ if (TREE_CODE (op1) != SSA_NAME
+ || TREE_CODE (op2) != SSA_NAME)
+ return false;
+
+ if (!has_single_use (op1) || !has_single_use (op2))
+ return false;
+
+ vec_alloc (op_ranges1, 1);
+ op_def = SSA_NAME_DEF_STMT (op1);
+ if (gimple_bb (stmt) == gimple_bb (op_def)
+ && get_constant_comparison (op_def, &op1_var, &op_const_high,
+ &op_const_low, nr_stmts))
+ {
+ push_range (&op_ranges1, op_const_high, op_const_low);
+ refine_ranges (bb, &op1_var, &op_ranges1, NULL, nr_stmts);
+ }
+ else
+ return false;
+
+ vec_alloc (op_ranges2, 1);
+ op_def = SSA_NAME_DEF_STMT (op2);
+ if (gimple_bb (stmt) == gimple_bb (op_def)
+ && get_constant_comparison (op_def, &op2_var, &op_const_high,
+ &op_const_low,nr_stmts))
+ {
+ push_range (&op_ranges2, op_const_high, op_const_low);
+ refine_ranges (bb, &op2_var, &op_ranges2, NULL, nr_stmts);
+ if (op1_var != op2_var)
+ return false;
+ }
+ else
+ return false;
+
+ *var = op1_var;
+ vec_safe_truncate (*ranges, 0);
+ vec_safe_splice (*ranges, op_ranges1);
+ vec_safe_splice (*ranges, op_ranges2);
+
+ (*nr_stmts)++;
+ return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in terms of another
+ var, if the defining stmt of VAR is and BIT_AND_EXPR, and return true if
+ successful. Increment NR_STMTS with the number of stmts in BB that were used
+ to implement the comparison. */
+
+static bool
+refine_range_bit_and (tree *var, vec<range, va_gc> **ranges,
+ unsigned int *nr_stmts)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (*var);
+ tree new_var, cst;
+ tree op1, op2;
+ range r;
+ tree cst2, inv_mask;
+ unsigned int zero_bits;
+
+ if (!stmt
+ || !is_gimple_assign (stmt)
+ || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
+ return false;
+
+ op1 = gimple_assign_rhs1 (stmt);
+ op2 = gimple_assign_rhs2 (stmt);
+
+ if (!TREE_CONSTANT (op1)
+ && !TREE_CONSTANT (op2))
+ return false;
+
+ new_var = TREE_CONSTANT (op1) ? op2 : op1;
+ cst = TREE_CONSTANT (op1) ? op1 : op2;
+
+ /* Need integral switch var. */
+ if (TREE_CODE (new_var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (new_var)))
+ return false;
+
+ zero_bits
+ = HOST_BITS_PER_DOUBLE_INT - tree_to_double_int (cst).popcount ();
+
+ if (zero_bits != 1)
+ return false;
+
+ if ((*ranges)->length () != 1)
+ return false;
+
+ r = (**ranges)[0];
+ if (r->high != NULL_TREE)
+ return false;
+
+ inv_mask = fold_unary (BIT_NOT_EXPR, TREE_TYPE (cst), cst);
+ cst2 = fold_binary (BIT_IOR_EXPR, TREE_TYPE (cst), r->low, inv_mask);
+
+ push_range (ranges, NULL_TREE, cst2);
+
+ *var = new_var;
+
+ (*nr_stmts)++;
+ return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in BB
+ in terms of another var. Invert swap_edges if that means reverting the
+ logic of the comparison, and increment NR_STMTS with the number of stmts in
+ BB that were used to implement the comparison. */
+
+static void
+refine_ranges (basic_block bb, tree *var, vec<range, va_gc> **ranges,
+ bool *swap_edges, unsigned int *nr_stmts)
+{
+ range r = NULL;
+ gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+ if (!stmt || gimple_bb (stmt) != bb)
+ return;
+
+ if (!has_single_use (*var))
+ return;
+
+ if ((*ranges)->length () == 1)
+ {
+ r = (**ranges)[0];
+
+ if (refine_range_cast (var, r->high, r->low, nr_stmts))
+ {
+ refine_ranges (bb, var, ranges, NULL, nr_stmts);
+ return;
+ }
+
+ if (refine_range_plus (var, &r->high, &r->low, nr_stmts))
+ {
+ refine_ranges (bb, var, ranges, NULL, nr_stmts);
+ return;
+ }
+
+ if (r->high != NULL_TREE)
+ return;
+
+ if (tree_int_cst_equal (r->low, integer_zero_node)
+ && refine_range_bit_ior (var, ranges, nr_stmts))
+ {
+ *swap_edges = !*swap_edges;
+ refine_ranges (bb, var, ranges, NULL, nr_stmts);
+ return;
+ }
+
+ if (refine_range_bit_and (var, ranges, nr_stmts))
+ {
+ refine_ranges (bb, var, ranges, NULL, nr_stmts);
+ return;
+ }
+ }
+
+}
+
+/* Convert all trees in RANGES to TYPE. */
+
+static bool
+convert_ranges (tree type, vec<range, va_gc> *ranges)
+{
+ unsigned int ix;
+ range r;
+
+ FOR_EACH_VEC_ELT (*ranges, ix, r)
+ {
+ r->low = fold_convert (type, r->low);
+ if (TREE_TYPE (r->low) != type)
+ return false;
+
+ if (r->high == NULL_TREE)
+ continue;
+
+ r->high = fold_convert (type, r->high);
+ if (TREE_TYPE (r->high) != type)
+ return false;
+ }
+
+ return true;
+}
+
+/* Return true if the amount of nondebug statements in BB is EXPECTED_NR. */
+
+static bool
+nr_nondebug_stmts_equal_to (basic_block bb, unsigned int expected_nr)
+{
+ gimple_stmt_iterator gsi;
+ unsigned int nr = 0;
+
+ for (gsi = gsi_start_nondebug_bb (bb);
+ !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+ {
+ nr++;
+ if (nr > expected_nr)
+ return false;
+ }
+
+ return nr == expected_nr;
+}
+
+/* Analyze BB and store results in ifsc_info_def struct. */
+
+static void
+analyze_bb (basic_block bb)
+{
+ gimple stmt = last_stmt (bb);
+ tree lhs, rhs, var, constant;
+ edge true_edge, false_edge;
+ enum tree_code cond_code;
+ vec<range, va_gc> *ranges;
+ unsigned int nr_stmts = 0;
+ bool swap_edges = false;
+ tree low, high;
+
+ /* We currently only handle bbs with GIMPLE_COND. */
+ if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+ return;
+
+ cond_code = gimple_cond_code (stmt);
+ switch (cond_code)
+ {
+ case EQ_EXPR:
+ case NE_EXPR:
+ case LE_EXPR:
+ case GE_EXPR:
+ break;
+ case LT_EXPR:
+ case GT_EXPR:
+ /* Todo. */
+ return;
+ default:
+ return;
+ }
+
+ lhs = gimple_cond_lhs (stmt);
+ rhs = gimple_cond_rhs (stmt);
+
+ /* The comparison needs to be against a constant. */
+ if (!TREE_CONSTANT (lhs)
+ && !TREE_CONSTANT (rhs))
+ return;
+
+ /* Normalize comparison into (var cond_code constant). */
+ var = TREE_CONSTANT (lhs) ? rhs : lhs;
+ constant = TREE_CONSTANT (lhs) ? lhs : rhs;
+ cond_code = (TREE_CONSTANT (lhs)
+ ? swap_tree_comparison (cond_code)
+ : cond_code);
+
+ if (cond_code == NE_EXPR)
+ {
+ cond_code = EQ_EXPR;
+ swap_edges = true;
+ }
+
+ /* The switch var needs to be integral. */
+ if (TREE_CODE (var) != SSA_NAME || !INTEGRAL_TYPE_P(TREE_TYPE (var)))
+ return;
+
+ switch (cond_code)
+ {
+ case GE_EXPR:
+ low = constant;
+ high = TYPE_MAXVAL (TREE_TYPE (var));
+ break;
+ case LE_EXPR:
+ low = TYPE_MINVAL (TREE_TYPE (var));
+ high = constant;
+ break;
+ case EQ_EXPR:
+ low = constant;
+ high = NULL_TREE;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ vec_alloc (ranges, 8);
+ push_range (&ranges, high, low);
+ refine_ranges (bb, &var, &ranges, &swap_edges, &nr_stmts);
+
+ /* Store analysis in ifsc_info_def struct. */
+ BB_IFSC_VAR (bb) = var;
+ BB_IFSC_RANGES (bb) = ranges;
+ BB_IFSC_EMPTY (bb) = nr_nondebug_stmts_equal_to (bb, nr_stmts + 1);
+
+ get_edges (bb, &true_edge, &false_edge);
+ BB_IFSC_TRUE_EDGE (bb) = swap_edges ? false_edge : true_edge;
+ BB_IFSC_FALSE_EDGE (bb) = swap_edges ? true_edge: false_edge;
+
+ /* Bail out if verify_gimple_switch would fail. */
+ if (!convert_ranges (TREE_TYPE (var), ranges))
+ BB_IFSC_VAR (bb) = NULL_TREE;
+}
+
+/* Return true if all the phis in the dest block of edges E1 and E2 have the
+ same values for the two edges. */
+
+static bool
+same_phi_nodes_values (edge e1, edge e2)
+{
+ gimple_stmt_iterator gsi;
+ gcc_assert (e1->dest == e2->dest);
+
+ for (gsi = gsi_start_phis (e1->dest);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple phi = gsi_stmt (gsi);
+ tree val1 = PHI_ARG_DEF_FROM_EDGE (phi, e1);
+ tree val2 = PHI_ARG_DEF_FROM_EDGE (phi, e2);
+ if (!operand_equal_for_phi_arg_p (val1, val2))
+ return false;
+ }
+ return true;
+}
+
+/* Returns true if BB cannot be chained to other bbs. */
+
+static bool
+cannot_be_chained (basic_block bb)
+{
+ return (BB_IFSC_VAR (bb) == NULL_TREE
+ || BB_IFSC_CHAINED (bb));
+}
+
+/* Returns true if BB can be a part of CHAIN. */
+
+static bool
+bb_fits_in_chain (basic_block bb, if_chain chain)
+{
+ edge chain_true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+ edge bb_true_edge = BB_IFSC_TRUE_EDGE (bb);
+
+ return (BB_IFSC_VAR (bb) == chain->var
+ && bb_true_edge->dest == chain_true_edge->dest
+ && same_phi_nodes_values (bb_true_edge, chain_true_edge));
+}
+
+/* Grow CHAIN forward. */
+
+static void
+grow_if_chain_forward (if_chain chain)
+{
+ basic_block next_bb;
+
+ while (1)
+ {
+ next_bb = BB_IFSC_FALSE_EDGE (chain->last)->dest;
+
+ if (cannot_be_chained (next_bb))
+ break;
+
+ /* Each bb in the chain needs to be the only predecessor. */
+ if (!single_pred_p (next_bb))
+ break;
+
+ if (!bb_fits_in_chain (next_bb, chain))
+ break;
+
+ /* We can only add empty bbs at the end of the chain. */
+ if (!BB_IFSC_EMPTY (next_bb))
+ break;
+
+ /* Add next_bb at end of chain. */
+ vec_safe_splice (chain->ranges, BB_IFSC_RANGES (next_bb));
+ BB_IFSC_CHAINED (next_bb) = true;
+ chain->last = next_bb;
+ }
+}
+
+/* Grow CHAIN backward. */
+
+static void
+grow_if_chain_backward (if_chain chain)
+{
+ basic_block prev_bb;
+
+ while (1)
+ {
+ /* First bb is not empty, cannot grow backwards. */
+ if (!BB_IFSC_EMPTY (chain->first))
+ break;
+
+ /* First bb has no single predecessor, cannot grow backwards. */
+ if (!single_pred_p (chain->first))
+ break;
+
+ prev_bb = single_pred (chain->first);
+ if (cannot_be_chained (prev_bb)
+ || !bb_fits_in_chain (prev_bb, chain))
+ break;
+
+ /* Add prev_bb at beginning of chain. */
+ vec_safe_splice (chain->ranges, BB_IFSC_RANGES (prev_bb));
+ BB_IFSC_CHAINED (prev_bb) = true;
+ chain->first = prev_bb;
+ }
+}
+
+/* Seed chain with BB, try to grow it forward and backward and return it. */
+
+static if_chain
+grow_if_chain (basic_block bb)
+{
+ if_chain chain = chain_alloc ();
+
+ /* Set bb as initial part of the chain. */
+ vec_safe_splice (chain->ranges, BB_IFSC_RANGES (bb));
+ chain->first = chain->last = bb;
+ chain->var = BB_IFSC_VAR (bb);
+
+ /* bb is part of a chain now. */
+ BB_IFSC_CHAINED (bb) = true;
+
+ /* Grow chain to its maximum size. */
+ grow_if_chain_forward (chain);
+ grow_if_chain_backward (chain);
+
+ /* Sort ranges and skip duplicates. */
+ sort_ranges (chain->ranges, &chain->sorted_ranges);
+ return chain;
+}
+
+/* Dump CHAIN to dump_file. */
+
+static void
+dump_if_chain (if_chain chain)
+{
+ edge true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+
+ fprintf (dump_file, "var: ");
+ print_generic_expr (dump_file, chain->var, 0);
+ fprintf (dump_file, "\n");
+ fprintf (dump_file, "first: <bb %d>\n", chain->first->index);
+ fprintf (dump_file, "true: <bb %d>\n", true_edge->dest->index);
+ fprintf (dump_file, "last: <bb %d>\n",chain->last->index);
+
+ fprintf (dump_file, "ranges: ");
+ print_range_vector (dump_file, chain->ranges);
+
+ if (chain->sorted_ranges->length ()
+ != chain->ranges->length ())
+ {
+ fprintf (dump_file, "sorted_ranges: ");
+ print_range_vector (dump_file, chain->sorted_ranges);
+ }
+}
+
+/* Remove redundant bbs and edges after turning CHAIN into a switch statement.
+ Accumulate the probabilities on the path following the false edges in
+ FALSE_PROB. */
+
+static void
+remove_redundant_bbs_and_edges (if_chain chain, int *false_prob)
+{
+ basic_block bb, next;
+ edge true_edge, false_edge;
+
+ for (bb = chain->first;; bb = next)
+ {
+ true_edge = BB_IFSC_TRUE_EDGE (bb);
+ false_edge = BB_IFSC_FALSE_EDGE (bb);
+
+ /* Determine next, before we delete false_edge. */
+ next = false_edge->dest;
+
+ /* Accumulate probability. */
+ *false_prob = (*false_prob * false_edge->probability) / REG_BR_PROB_BASE;
+
+ /* Don't remove the new true_edge. */
+ if (bb != chain->first)
+ remove_edge (true_edge);
+
+ /* Don't remove the new false_edge. */
+ if (bb != chain->last)
+ remove_edge (false_edge);
+
+ /* Don't remove the first bb. */
+ if (bb != chain->first)
+ delete_basic_block (bb);
+
+ /* Stop after last. */
+ if (bb == chain->last)
+ break;
+ }
+}
+
+/* Update the control flow graph after turning CHAIN into a switch
+ statement. */
+
+static void
+update_cfg (if_chain chain)
+{
+ edge true_edge, false_edge;
+ int false_prob;
+ int flags_mask = ~(EDGE_FALLTHRU|EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
+
+ /* We keep these 2 edges, and remove the rest. We need this specific
+ false_edge, because a phi in chain->last->dest might reference (the index
+ of) this edge. For true_edge, we could pick any of them. */
+ true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+ false_edge = BB_IFSC_FALSE_EDGE (chain->last);
+
+ /* Update true edge. */
+ true_edge->flags &= flags_mask;
+
+ /* Update false edge. */
+ redirect_edge_pred (false_edge, chain->first);
+ false_edge->flags &= flags_mask;
+
+ false_prob = REG_BR_PROB_BASE;
+ remove_redundant_bbs_and_edges (chain, &false_prob);
+
+ /* Repair probabilities. */
+ true_edge->probability = REG_BR_PROB_BASE - false_prob;
+ false_edge->probability = false_prob;
+}
+
+/* Create switch statement corresponding to CHAIN. Borrows from
+ gimplify_switch_expr. */
+
+static void
+convert_if_chain_to_switch (if_chain chain)
+{
+ tree label_decl_true, label_decl_false;
+ gimple label_true, label_false, gimple_switch;
+ gimple_stmt_iterator gsi;
+ tree default_case, other_case;
+ unsigned int ix;
+ vec<tree> labels;
+ range r;
+ edge true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+
+ /* Create and insert true jump label. */
+ label_decl_true = create_artificial_label (UNKNOWN_LOCATION);
+ label_true = gimple_build_label (label_decl_true);
+ gsi = gsi_start_bb (true_edge->dest);
+ gsi_insert_before (&gsi, label_true, GSI_SAME_STMT);
+
+ /* Create and insert false jump label. */
+ label_decl_false = create_artificial_label (UNKNOWN_LOCATION);
+ label_false = gimple_build_label (label_decl_false);
+ gsi = gsi_start_bb (BB_IFSC_FALSE_EDGE (chain->last)->dest);
+ gsi_insert_before (&gsi, label_false, GSI_SAME_STMT);
+
+ /* Create default case label. */
+ default_case = build4 (CASE_LABEL_EXPR, void_type_node,
+ NULL_TREE, NULL_TREE,
+ label_decl_false, NULL_TREE);
+
+ /* Create case labels. */
+ labels.create (chain->sorted_ranges->length ());
+ FOR_EACH_VEC_ELT (*chain->sorted_ranges, ix, r)
+ {
+ other_case = build4 (CASE_LABEL_EXPR, void_type_node, r->low, r->high,
+ label_decl_true, NULL_TREE);
+ labels.safe_push (other_case);
+ }
+
+ /* Create and insert switch. */
+ gimple_switch = gimple_build_switch (chain->var, default_case, labels);
+ gsi = gsi_for_stmt (last_stmt (chain->first));
+ gsi_insert_before (&gsi, gimple_switch, GSI_SAME_STMT);
+
+ /* Remove now obsolete if. */
+ gsi_remove (&gsi, true);
+
+ labels.release ();
+}
+
+/* Convert every if-chain in CHAINS into a switch statement. */
+
+static void
+convert_chains (vec<if_chain> chains)
+{
+ unsigned int ix;
+ if_chain chain;
+
+ if (chains.is_empty ())
+ return;
+
+ FOR_EACH_VEC_ELT (chains, ix, chain)
+ {
+ if (dump_file)
+ dump_if_chain (chain);
+
+ convert_if_chain_to_switch (chain);
+
+ update_cfg (chain);
+ }
+
+ /* Force recalculation of dominance info. */
+ free_dominance_info (CDI_DOMINATORS);
+ free_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* Allocate memory used by the pass. */
+
+static void
+init_pass (void)
+{
+ size_t aux_size = sizeof (struct ifsc_info_def);
+ alloc_aux_for_blocks (aux_size);
+ gcc_obstack_init (&range_obstack);
+ gcc_obstack_init (&chain_obstack);
+}
+
+/* Deallocate memory used by the pass. */
+
+static void
+finish_pass (void)
+{
+ free_aux_for_blocks ();
+ obstack_free (&range_obstack, NULL);
+ obstack_free (&chain_obstack, NULL);
+}
+
+/* For CHAIN, return in:
+ - RANGE the difference between highest and lowest case.
+ - UNIQ the number of unique case node targets, not counting the default case.
+ - COUNT the number of comparisons needed, not counting the default case. */
+
+static void
+chain_get_switch_parameters (if_chain chain, tree *tree_range,
+ unsigned int *uniq, unsigned int *count)
+{
+ range f = (*chain->sorted_ranges)[0];
+ range l = chain->sorted_ranges->last ();
+ tree high, low;
+ unsigned int i;
+ range r;
+
+ low = f->low;
+ high = l->high;
+ if (high == NULL_TREE)
+ high = l->low;
+
+ *tree_range = fold_binary (MINUS_EXPR, TREE_TYPE (low), high, low);
+
+ /* An if-chain has only 1 target. */
+ *uniq = 1;
+
+ *count = 0;
+ FOR_EACH_VEC_ELT_REVERSE (*chain->sorted_ranges, i, r)
+ {
+ tree low, high;
+
+ low = r->low;
+ gcc_assert (low);
+ high = r->high;
+ gcc_assert (! high || tree_int_cst_lt (low, high));
+
+ /* Count the elements.
+ A range counts double, since it requires two compares. */
+ /* Todo: A range [type_min, a] or [b, type_max] should maybe count as
+ one. */
+ *count += 1;
+ if (high)
+ *count += 1;
+ }
+}
+
+/* Return the relative cost of mispredicting a branch. */
+
+static int
+branch_mispredict_penalty (void)
+{
+ int well_predicted_branch_cost = BRANCH_COST (true, true);
+ int branch_cost = BRANCH_COST (true, false);
+ return branch_cost - well_predicted_branch_cost;
+}
+
+/* Return true if CHAIN should be converted into a switch statement. If
+ CAN_EXPAND_AS_BIT_TEST, we can expand switches as bit test. */
+
+static bool
+convert_if_chain_p (if_chain chain, bool can_expand_as_bit_test)
+{
+ tree tree_range;
+ unsigned int uniq;
+ unsigned int count;
+ bool expand_as_bit_test;
+ int bmp = branch_mispredict_penalty ();
+ int bmp_threshold = 1;
+
+ /* Avoid converting really small chains. */
+ if (chain->first == chain->last
+ || chain->sorted_ranges->length () == 1)
+ return false;
+
+ chain_get_switch_parameters (chain, &tree_range, &uniq, &count);
+
+ expand_as_bit_test
+ = (can_expand_as_bit_test
+ ? expand_switch_using_bit_tests_p (tree_range, uniq, count)
+ : false);
+
+ if (optimize_function_for_speed_p (cfun))
+ {
+ if (expand_as_bit_test)
+ {
+ /* We are limited here in our decision making by the absence of
+ accurate profile info. If we expand_as_bit_test it means
+ we're before pass_convert_switch, which is before
+ pass_ipa_tree_profile. */
+
+ if (bmp < bmp_threshold)
+ {
+ /* Converting the if-chain to a bit-test might slow the first jump
+ of the chain down because the condition testing is more
+ expensive. So we only do this if we expect a benificial effect
+ from an increased likelihood of the collapsed jump, in other
+ words there's significant branch mispredict penalty. */
+ return false;
+ }
+
+ return true;
+ }
+
+ /* By converting an if-chain into a switch, and later into a decision
+ tree, we effectively reorder the branches. We shouldn't reorder
+ without using profile info.
+ And if we don't convert into a decision tree it'll be a table jump
+ which is generally slow, so we take the conservative choice here. */
+ return false;
+ }
+
+ /* We're not optimizing, bail out. */
+ return false;
+}
+
+/* Find if-chains and convert them to switch statements. If
+ CAN_EXPAND_AS_BIT_TEST, we can expand switches as bit test. */
+
+static unsigned int
+find_and_convert_if_chains (bool can_expand_as_bit_test)
+{
+ basic_block bb;
+ if_chain chain;
+ vec<if_chain> chains;
+
+ chains.create (0);
+ init_pass ();
+
+ FOR_EACH_BB (bb)
+ analyze_bb (bb);
+
+ FOR_EACH_BB (bb)
+ {
+ if (cannot_be_chained (bb))
+ continue;
+
+ chain = grow_if_chain (bb);
+
+ if (!convert_if_chain_p (chain, can_expand_as_bit_test))
+ continue;
+
+ chains.safe_push (chain);
+ }
+
+ convert_chains (chains);
+
+ finish_pass ();
+ chains.release ();
+
+ return 0;
+}
+
+/* Find if-chains and convert them to switch statements, which may be
+ transformed into bit tests. */
+
+static unsigned int
+if_to_switch (void)
+{
+ /* The argument should correspond to the location of the pass relative to
+ pass_convert_switch. */
+ return find_and_convert_if_chains (true);
+}
+
+/* Returns true if the pass should be run. */
+
+static bool
+if_to_switch_gate (void)
+{
+ return (flag_tree_if_to_switch_conversion
+ && !profile_flag);
+}
+
+struct gimple_opt_pass pass_if_to_switch =
+{
+ {
+ GIMPLE_PASS,
+ "iftoswitch", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ if_to_switch_gate, /* gate */
+ if_to_switch, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_TREE_SWITCH_CONVERSION, /* tv_id */
+ PROP_cfg | PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa | TODO_verify_ssa /* todo_flags_finish */
+ }
+};
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi (revision 200261)
+++ gcc/doc/invoke.texi (working copy)
@@ -412,8 +412,8 @@
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
-ftree-coalesce-inline-vars -ftree-coalesce-vars -ftree-copy-prop @gol
-ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse @gol
--ftree-forwprop -ftree-fre -ftree-loop-if-convert @gol
--ftree-loop-if-convert-stores -ftree-loop-im @gol
+-ftree-forwprop -ftree-fre -ftree-if-to-switch-conversion @gol
+-ftree-loop-if-convert -ftree-loop-if-convert-stores -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
-ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
-ftree-parallelize-loops=@var{n} -ftree-pre -ftree-partial-pre -ftree-pta @gol
@@ -6652,6 +6652,7 @@
-fsched-interblock -fsched-spec @gol
-fschedule-insns -fschedule-insns2 @gol
-fstrict-aliasing -fstrict-overflow @gol
+-ftree-if-to-switch-conversion @gol
-ftree-switch-conversion -ftree-tail-merge @gol
-ftree-pre @gol
-ftree-vrp}
@@ -7601,6 +7602,10 @@
be limited using @option{max-tail-merge-comparisons} parameter and
@option{max-tail-merge-iterations} parameter.
+@item -ftree-if-to-switch-conversion
+Perform conversion of chains of ifs into switches. This flag is enabled by
+default at @option{-O2} and higher.
+
@item -ftree-dce
@opindex ftree-dce
Perform dead code elimination (DCE) on trees. This flag is enabled by
Index: gcc/opts.c
===================================================================
--- gcc/opts.c (revision 200261)
+++ gcc/opts.c (working copy)
@@ -473,6 +473,7 @@
{ OPT_LEVELS_2_PLUS, OPT_fstrict_overflow, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_freorder_blocks, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_freorder_functions, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_ftree_if_to_switch_conversion, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_builtin_call_dce, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_pre, NULL, 1 },
Index: gcc/tree-switch-conversion.c
===================================================================
--- gcc/tree-switch-conversion.c (revision 200261)
+++ gcc/tree-switch-conversion.c (working copy)
@@ -149,7 +149,7 @@
UNIQ is number of unique case node targets, not counting the default case.
COUNT is the number of comparisons needed, not counting the default case. */
-static bool
+bool
expand_switch_using_bit_tests_p (tree range,
unsigned int uniq,
unsigned int count)
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in (revision 200261)
+++ gcc/Makefile.in (working copy)
@@ -1406,6 +1406,7 @@
tree-profile.o \
tree-scalar-evolution.o \
tree-sra.o \
+ tree-if-switch-conversion.o \
tree-switch-conversion.o \
tree-ssa-address.o \
tree-ssa-alias.o \
@@ -3067,6 +3068,9 @@
$(IPA_PROP_H) $(DIAGNOSTIC_H) statistics.h \
$(PARAMS_H) $(TARGET_H) $(FLAGS_H) \
$(DBGCNT_H) $(TREE_INLINE_H) $(GIMPLE_PRETTY_PRINT_H)
+tree-if-switch-conversion.o : tree-if-switch-conversion.c $(CONFIG_H) \
+ $(SYSTEM_H) coretypes.h \
+ $(GIMPLE_H) $(GIMPLE_PRETTY_PRINT_H) $(TREE_FLOW_H) $(TREE_PASS_H)
tree-switch-conversion.o : tree-switch-conversion.c $(CONFIG_H) $(SYSTEM_H) \
$(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
$(TM_H) coretypes.h $(GIMPLE_H) $(CFGLOOP_H) \
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h (revision 200261)
+++ gcc/tree-pass.h (working copy)
@@ -489,6 +489,7 @@
extern struct gimple_opt_pass pass_inline_parameters;
extern struct gimple_opt_pass pass_update_address_taken;
extern struct gimple_opt_pass pass_convert_switch;
+extern struct gimple_opt_pass pass_if_to_switch;
/* The root of the compilation pass tree, once constructed. */
extern struct opt_pass *all_passes, *all_small_ipa_passes, *all_lowering_passes,
Index: gcc/common.opt
===================================================================
--- gcc/common.opt (revision 200261)
+++ gcc/common.opt (working copy)
@@ -2068,6 +2068,10 @@
Common Report Var(flag_tree_switch_conversion) Optimization
Perform conversions of switch initializations.
+ftree-if-to-switch-conversion
+Common Report Var(flag_tree_if_to_switch_conversion) Optimization
+Perform conversions of chains of ifs into switches.
+
ftree-dce
Common Report Var(flag_tree_dce) Optimization
Enable SSA dead code elimination optimization on trees
Index: gcc/testsuite/gcc.dg/pr21643.c
===================================================================
--- gcc/testsuite/gcc.dg/pr21643.c (revision 200261)
+++ gcc/testsuite/gcc.dg/pr21643.c (working copy)
@@ -1,6 +1,6 @@
/* PR tree-optimization/21643 */
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details -fno-tree-if-to-switch-conversion" } */
int
f1 (unsigned char c)
Index: gcc/testsuite/gcc.dg/if-to-switch-2.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch-2.c (revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch-2.c (revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+/* Example with (*src >= 9 && *src <= 10). The front-end turns this into
+ (((unsigned char) *src) + 247) <= 1. */
+
+const char *
+f (const char *src)
+{
+ while (*src == 13 || (*src >= 9 && *src <= 10) || *src == 32)
+ ++src;
+ return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch-3.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch-3.c (revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch-3.c (revision 0)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+/* Contains duplicate test for 9. */
+
+const char *
+f (const char *src)
+{
+ while (*src == 13 || (*src >= 9 && *src <= 10) || *src == 32 || *src == 9)
+ ++src;
+ return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp63.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp63.c (revision 200261)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp63.c (working copy)
@@ -1,6 +1,6 @@
/* PR tree-optimization/51721 */
/* { dg-do link } */
-/* { dg-options "-O2" } */
+/* { dg-options "-O2 -fno-tree-if-to-switch-conversion" } */
extern void link_error (void);
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp64.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp64.c (revision 200261)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp64.c (working copy)
@@ -1,6 +1,6 @@
/* PR tree-optimization/51721 */
/* { dg-do link } */
-/* { dg-options "-O2" } */
+/* { dg-options "-O2 -fno-tree-if-to-switch-conversion" } */
extern void link_error (void);
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp33.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp33.c (revision 200261)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp33.c (working copy)
@@ -1,5 +1,5 @@
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-if-to-switch-conversion" } */
/* This is from PR14052. */
Index: gcc/testsuite/gcc.dg/if-to-switch.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch.c (revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch.c (revision 0)
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+const char *
+f (const char *src)
+{
+ while (*src == 13 || *src == 9 || *src == 10 || *src == 32)
+ ++src;
+ return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/passes.c
===================================================================
--- gcc/passes.c (revision 200261)
+++ gcc/passes.c (working copy)
@@ -1338,6 +1338,7 @@
NEXT_PASS (pass_cd_dce);
NEXT_PASS (pass_early_ipa_sra);
NEXT_PASS (pass_tail_recursion);
+ NEXT_PASS (pass_if_to_switch);
NEXT_PASS (pass_convert_switch);
NEXT_PASS (pass_cleanup_eh);
NEXT_PASS (pass_profile);
More information about the Gcc-patches
mailing list