From patchwork Tue Jul 17 11:21:00 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tom de Vries X-Patchwork-Id: 171394 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id C28CA2C01C6 for ; Tue, 17 Jul 2012 21:21:42 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1343128903; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC: Subject:Content-Type:Mailing-List:Precedence:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:Sender: Delivered-To; bh=fPUBeEgRBNzDiSiHycPPc4r/HbQ=; b=R/qOIx1FBuW5Joy /951/InplWlSY66zH2AQOBDBl9X3MiBfXADm1gjxHk0IoCy1QK9UYa3T6mGS/dDH 6rOoP8q0AvLiiXBHgybD03bu9iqM25C0o25YIgQ52hHt542wb2DmxV24GdHmwzHC 1pdvFRF6/ffwIurKCN9n9z55K4Lo= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:Received:Received:Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=YTRJlN3BcmmbOndMZX7VMbvk9abMShoXseZY6t1nAwoiWQcNY24XYwF/BBhU+1 e1XOqsKivXOfNT0CLM4YKIxvkJBXqTpY9/H1Cj23u0u74aE8NVqyr28lT042azaq MVJ4hN8tVBi+NTecMC4DtTXTgp3xlzlRK64sFHsXkxTpE=; Received: (qmail 28897 invoked by alias); 17 Jul 2012 11:21:35 -0000 Received: (qmail 28883 invoked by uid 22791); 17 Jul 2012 11:21:29 -0000 X-SWARE-Spam-Status: No, hits=-3.5 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_HOSTKARMA_W, RCVD_IN_HOSTKARMA_WL, TW_CF, TW_IV, TW_TM X-Spam-Check-By: sourceware.org Received: from relay1.mentorg.com (HELO relay1.mentorg.com) (192.94.38.131) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 17 Jul 2012 11:21:10 +0000 Received: from svr-orw-fem-01.mgc.mentorg.com ([147.34.98.93]) by relay1.mentorg.com with esmtp id 1Sr5pz-0003G3-Tk from Tom_deVries@mentor.com ; Tue, 17 Jul 2012 04:21:07 -0700 Received: from SVR-IES-FEM-01.mgc.mentorg.com ([137.202.0.104]) by svr-orw-fem-01.mgc.mentorg.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Tue, 17 Jul 2012 04:21:07 -0700 Received: from [127.0.0.1] (137.202.0.76) by SVR-IES-FEM-01.mgc.mentorg.com (137.202.0.104) with Microsoft SMTP Server id 14.1.289.1; Tue, 17 Jul 2012 12:21:04 +0100 Message-ID: <50054A9C.4030404@mentor.com> Date: Tue, 17 Jul 2012 13:21:00 +0200 From: Tom de Vries User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:13.0) Gecko/20120615 Thunderbird/13.0.1 MIME-Version: 1.0 To: Richard Guenther CC: "gcc-patches@gcc.gnu.org" , Jakub Jelinek , Steven Bosscher , Jan Hubicka Subject: [PATCH 1/2] if-to-switch conversion pass Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Richard, attached patch implements an if-to-switch conversion tree pass pass_if_to_switch. I will follow up this email with an infrastructure patch that provides double_int_popcount and popcount_hwi. The pass detects chains of ifs like this: ... : ... if (D.1993_3 == 32) goto ; else goto ; : if (D.1993_3 == 13) goto ; else goto ; : if (D.1993_3 == 10) goto ; else goto ; : if (D.1993_3 == 9) goto ; else goto ; ... and converts them into a switch statement: ... : ... switch (D.1993_3) , case 9: , case 10: , case 13: , case 32: > ... There are 2 motivations to convert chains of ifs to switches (as discussed in http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46935 ): - to reduce the control flow graph - to take advantage of the efficient shift-and-bit-test implementations of switches This pass takes the first approach as optimization measure, so it doesn't test if the resulting switch can be converted into a shift-and-bit-test implementation. pass_if_to_switch is on by default at O2 and higher, and controlled by -ftree-if-to-switch-conversion. The pass works as follows: - it analyzes all bbs - it forms if-chains out of bbs - it transforms if-chains into switches The pass is run twice, once before pass_convert_switch, and once after pass_pre. By running it before pass_convert_switch, we take advantage of the shift-and-bit-test implementation of switches (the conversion has recently been moved from pass_expand to pass_convert_switch). By running it after pass_pre, we take advantage of blocks collapsed by tail merging, creating opportunities for if-to-switch conversion. Test-case if-to-switch-5.c (the example from PR14799) is transformed into a switch by the second run of the pass, not the first. Perhaps instead of the second run of pass_if_to_switch, we could run tail-merge (maybe without using gvn?) before the first run of pass_if_to_switch. That would also allow if-to-switch-5.c to be converted to a shift-and-bit-test. For all the new test-cases, the if-chain is transformed into a switch by the pass. For test-cases if-to-switch.c, if-to-switch-2.c and if-to-switch-4.c the if-chains are subsequently transformed into shift-and-bit-tests. The if-chain from the test-case if-to-switch-3.c (the example from PR46935) is transformed into the following switch: ... switch (cD.1707_2(D)) , case 0 ... 32: , case 34: , case 39: , case 44: , case 46: , case 58: , case 59 ... 60: , case 62: , case 92: > ... This switch is currently not transformed into a shift-and-bit-test since the resulting range is too large, but the divide-and-conquer approach mentioned in http://gcc.gnu.org/ml/gcc-patches/2012-06/msg01960.html could split off the 0..32 test and implement the rest as shift-and-bit-test. Bootstrapped and reg-tested (Ada inclusive) on x86_64. OK for trunk? Thanks, - Tom 2012-07-17 Tom de Vries * 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. * 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/if-to-switch.c-4: Same. * gcc.dg/if-to-switch.c-5: 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. Index: gcc/tree-pass.h =================================================================== --- gcc/tree-pass.h (revision 189508) +++ gcc/tree-pass.h (working copy) @@ -577,6 +577,7 @@ extern struct gimple_opt_pass pass_early 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/tree-if-switch-conversion.c =================================================================== --- /dev/null (new file) +++ gcc/tree-if-switch-conversion.c (revision 0) @@ -0,0 +1,1218 @@ +/* Convert a chain of if statements into a switch statement. + Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. + Contributed by Tom de Vries + +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 +. */ + +/* 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: + ... + : + ... + if (D.1993_3 == 32) + goto ; + else + goto ; + + : + if (D.1993_3 == 13) + goto ; + else + goto ; + + : + if (D.1993_3 == 10) + goto ; + else + goto ; + + : + if (D.1993_3 == 9) + goto ; + else + goto ; + ... + + The pass will report this if-chain like this: + ... + var: D.1993_3 + first: + true: + last: + constants: 9 10 13 32 + ... + + and then convert the if-chain into a switch: + ... + : + ... + switch (D.1993_3) , + case 9: , + case 10: , + case 13: , + case 32: > + ... + + 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)'. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" + +#include "params.h" +#include "flags.h" +#include "tree.h" +#include "basic-block.h" +#include "tree-flow.h" +#include "tree-flow-inline.h" +#include "tree-ssa-operands.h" +#include "diagnostic.h" +#include "tree-pass.h" +#include "tree-dump.h" +#include "timevar.h" +#include "tree-pretty-print.h" + +/* Struct to describe a range [low, high]. */ + +struct range_def +{ + tree high; + tree low; +}; +typedef struct range_def *range; + +DEF_VEC_P (range); +DEF_VEC_ALLOC_P (range, gc); + +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, 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, gc) *ranges; + /* Same as previous, but sorted and with duplicates removed. */ + VEC (range, gc) *sorted_ranges; +}; +typedef struct if_chain_def *if_chain; + +DEF_VEC_P (if_chain); +DEF_VEC_ALLOC_P (if_chain, gc); + +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); + chain->ranges = VEC_alloc (range, gc, 8); + chain->sorted_ranges = VEC_alloc (range, gc, 8); + return chain; +} + +/* Forward declarations. */ + +static void +refine_ranges (basic_block, tree *, VEC (range, gc) **, bool *, + unsigned int *); + + +/* Dump RS to dump_file. */ + +static void +dump_range_vector (VEC (range, gc) *rs) +{ + unsigned int ix; + range r; + + for (ix = 0; VEC_iterate (range, rs, ix, r); ix++) + { + if (ix != 0) + fprintf (dump_file, " "); + print_generic_expr (dump_file, r->low, 0); + if (r->high) + { + fprintf (dump_file, "-"); + print_generic_expr (dump_file, r->high, 0); + } + } + fprintf (dump_file, "\n"); +} + +/* Add a range of [LOW, HIGH] to RS. */ + +static void +push_range (VEC (range, gc) **rs, tree high, tree low) +{ + range r = range_alloc (high, low); + VEC_safe_push (range, gc, *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 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)) + 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, gc) *ranges, VEC (range, gc) **sorted_ranges) +{ + size_t len = VEC_length (range, ranges); + unsigned int ix; + range prev = NULL, r; + + /* Sort ranges. */ + qsort (VEC_address (range, ranges), len, sizeof (range), + compare_ranges); + + for (ix = 0; VEC_iterate (range, ranges, ix, r); ix++) + { + range m = combine_ranges (prev, r); + if (m) + { + prev = m; + continue; + } + if (prev) + VEC_safe_push (range, gc, *sorted_ranges, prev); + prev = r; + } + if (prev) + VEC_safe_push (range, gc, *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; + 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))) + 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 = (*high == NULL_TREE + ? NULL_TREE + : fold_binary (MINUS_EXPR, TREE_TYPE (new_var), *high, offset)); + + *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, 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, gc) *op_ranges1 = NULL; + VEC (range, gc) *op_ranges2 = NULL; + + 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; + + 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; + + 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_truncate (range, *ranges, 0); + VEC_safe_splice (range, gc, *ranges, op_ranges1); + VEC_safe_splice (range, gc, *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, 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 - double_int_popcount (tree_to_double_int (cst)); + + if (zero_bits != 1) + return false; + + if (VEC_length (range, *ranges) != 1) + return false; + + r = VEC_index (range, *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, 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 (VEC_length (range, *ranges) == 1) + { + r = VEC_index (range, *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, gc) *ranges) +{ + unsigned int ix; + range r; + + for (ix = 0; VEC_iterate (range, ranges, ix, r); ix++) + { + 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->low) != type) + return false; + } + + return true; +} + +/* Return true if the amount of nondebug statments 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, gc) *ranges = NULL; + 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 (); + } + + 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 (range, gc, 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 (range, gc, 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 (range, gc, 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: \n", chain->first->index); + fprintf (dump_file, "true: \n", true_edge->dest->index); + fprintf (dump_file, "last: \n",chain->last->index); + + fprintf (dump_file, "ranges: "); + dump_range_vector (chain->ranges); + + if (VEC_length (range, chain->sorted_ranges) + != VEC_length (range, chain->ranges)) + { + fprintf (dump_file, "sorted_ranges: "); + dump_range_vector (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, heap) *labels; + range r; + edge true_edge = BB_IFSC_TRUE_EDGE (chain->first); + + labels = VEC_alloc (tree, heap, 8); + + /* 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. */ + for (ix = 0; VEC_iterate (range, chain->sorted_ranges, ix, r); ix++) + { + other_case = build4 (CASE_LABEL_EXPR, void_type_node, r->low, r->high, + label_decl_true, NULL_TREE); + VEC_safe_push (tree, heap, labels, other_case); + } + + /* Create and insert switch. */ + gimple_switch = gimple_build_switch_vec (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); + + VEC_free (tree, heap, labels); +} + +/* Convert every if-chain in CHAINS into a switch statement. */ + +static void +convert_chains (VEC (if_chain, gc) *chains) +{ + unsigned int ix; + if_chain chain; + + if (VEC_empty (if_chain, chains)) + return; + + for (ix = 0; VEC_iterate (if_chain, chains, ix, chain); ix++) + { + 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); +} + +/* Return true if CHAIN should be transformed into a switch statement. */ + +static bool +transform_if_chain_p (if_chain chain) +{ + /* Don't transform if the cfg doesn't get reduced. */ + if (chain->first == chain->last) + return false; + + /* It should be possible to represent a single range by an if statement. */ + if (VEC_length (range, chain->sorted_ranges) == 1) + return false; + + return true; +} + +/* Find if-chains and convert them to switch statements. */ + +static unsigned int +do_if_to_switch (void) +{ + basic_block bb; + if_chain chain; + VEC (if_chain, gc) *chains = NULL; + + 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 (!transform_if_chain_p (chain)) + continue; + + VEC_safe_push (if_chain, gc, chains, chain); + } + + convert_chains (chains); + + finish_pass (); + + return 0; +} + +/* Returns true if the pass should be run. */ + +static bool +if_to_switch_gate (void) +{ + return flag_tree_if_to_switch_conversion; +} + +/* The pass definition. */ + +struct gimple_opt_pass pass_if_to_switch = +{ + { + GIMPLE_PASS, + "iftoswitch", /* name */ + if_to_switch_gate, /* gate */ + do_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_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ + } +}; Index: gcc/opts.c =================================================================== --- gcc/opts.c (revision 189508) +++ gcc/opts.c (working copy) @@ -476,6 +476,7 @@ static const struct default_options defa { 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/common.opt =================================================================== --- gcc/common.opt (revision 189508) +++ gcc/common.opt (working copy) @@ -1996,6 +1996,10 @@ ftree-switch-conversion 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/Makefile.in =================================================================== --- gcc/Makefile.in (revision 189508) +++ gcc/Makefile.in (working copy) @@ -1391,6 +1391,7 @@ OBJS = \ 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 \ @@ -3013,7 +3014,12 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY $(IPA_PROP_H) $(DIAGNOSTIC_H) statistics.h $(TREE_DUMP_H) $(TIMEVAR_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) $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) \ + $(TREE_INLINE_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \ + $(GIMPLE_H) $(TREE_PASS_H) $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \ + $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_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) \ $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(GIMPLE_H) \ /* Compute the absolute value of X. */ Index: gcc/passes.c =================================================================== --- gcc/passes.c (revision 189508) +++ gcc/passes.c (working copy) @@ -1312,6 +1312,7 @@ init_optimization_passes (void) 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); @@ -1421,6 +1422,7 @@ init_optimization_passes (void) NEXT_PASS (pass_optimize_bswap); NEXT_PASS (pass_split_crit_edges); NEXT_PASS (pass_pre); + NEXT_PASS (pass_if_to_switch); NEXT_PASS (pass_sink_code); NEXT_PASS (pass_tree_loop); { Index: gcc/doc/invoke.texi =================================================================== --- gcc/doc/invoke.texi (revision 189508) +++ gcc/doc/invoke.texi (working copy) @@ -408,8 +408,8 @@ Objective-C and Objective-C++ Dialects}. -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 @@ -6298,6 +6298,7 @@ also turns on the following optimization -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} @@ -7224,6 +7225,10 @@ in this pass can 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/testsuite/gcc.dg/if-to-switch-2.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/if-to-switch-2.c (revision 0) @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */ + +/* 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 "iftoswitch1"} } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */ +/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */ Index: gcc/testsuite/gcc.dg/if-to-switch-3.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/if-to-switch-3.c (revision 0) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */ + +/* Example from PR 46935. */ + +int crud (unsigned char c) +{ + return (((((((((((int) c <= 32 || (int) c == 46) || (int) c == 44) + || (int) c == 58) || (int) c == 59) || (int) c == 60) + || (int) c == 62) || (int) c == 34) || (int) c == 92) + || (int) c == 39) != 0); +} + +/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch1"} } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */ +/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */ Index: gcc/testsuite/gcc.dg/if-to-switch-4.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/if-to-switch-4.c (revision 0) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */ + +/* 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 "iftoswitch1"} } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */ +/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */ Index: gcc/testsuite/gcc.dg/if-to-switch-5.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/if-to-switch-5.c (revision 0) @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-iftoswitch2" } */ + +/* This is the example from PR14799. This example is handled by the second + if-to-switch pass. Only after pre are the different blocks with the call to + bar collapsed, and then if-to-switch conversion can do it's work. */ + +void bar (void); + +void +foo (int a) +{ + if (a == 30) + bar (); + else if (a == 31) + bar (); + else if (a == 53) + bar (); + else if (a == 23) + bar (); +} + +/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch2"} } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch2"} } */ +/* { dg-final { cleanup-tree-dump "iftoswitch2" } } */ Index: gcc/testsuite/gcc.dg/if-to-switch.c =================================================================== --- /dev/null (new file) +++ gcc/testsuite/gcc.dg/if-to-switch.c (revision 0) @@ -0,0 +1,14 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */ + +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 "iftoswitch1"} } */ +/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */ +/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */ Index: gcc/testsuite/gcc.dg/tree-ssa/vrp63.c =================================================================== --- gcc/testsuite/gcc.dg/tree-ssa/vrp63.c (revision 189508) +++ 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 189508) +++ 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 189508) +++ 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. */