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 <t...@codesourcery.com> Cesar Philippidis <ce...@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.
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 <t...@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);