public inbox for gcc-cvs@sourceware.org
help / color / mirror / Atom feed
* [gcc(refs/users/marxin/heads/if-to-switch-v4)] Add if-chain to switch conversion pass.
@ 2020-10-09 12:41 Martin Liska
0 siblings, 0 replies; 3+ messages in thread
From: Martin Liska @ 2020-10-09 12:41 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:6f7850dc91938ddb15ef6c6169e10bab247aa7f4
commit 6f7850dc91938ddb15ef6c6169e10bab247aa7f4
Author: Martin Liska <mliska@suse.cz>
Date: Fri Aug 28 10:26:13 2020 +0200
Add if-chain to switch conversion pass.
gcc/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* Makefile.in: Add new gimple-if-to-switch.o.
* common.opt: Add new option.
* dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
* doc/invoke.texi: Document -fconvert-if-to-switch.
* opts.c: Add -fconvert-if-to-switch at OPT_LEVELS_2_PLUS.
* passes.def: Register new pass.
* timevar.def (TV_TREE_IF_TO_SWITCH): Add new time variable.
* tree-pass.h (make_pass_if_to_switch): New.
* tree-switch-conversion.h: New file.
* gimple-if-to-switch.cc: New file.
gcc/testsuite/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* gcc.dg/tree-ssa/reassoc-32.c: Add -fno-convert-if-to-switch.
* gcc.dg/tree-ssa/if-to-switch-1.c: New test.
* gcc.dg/tree-ssa/if-to-switch-2.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-3.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-4.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-5.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-6.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-7.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-8.c: Likewise.
Diff:
---
gcc/Makefile.in | 1 +
gcc/common.opt | 4 +
gcc/dbgcnt.def | 1 +
gcc/doc/invoke.texi | 13 +-
gcc/gimple-if-to-switch.cc | 762 +++++++++++++++++++++++++
gcc/opts.c | 1 +
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c | 35 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c | 36 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c | 12 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c | 42 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c | 25 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c | 27 +
gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-switch-conversion.h | 15 +-
19 files changed, 993 insertions(+), 8 deletions(-)
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5a8fb0d7612..c7ecda54df2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1361,6 +1361,7 @@ OBJS = \
gimple-array-bounds.o \
gimple-builder.o \
gimple-expr.o \
+ gimple-if-to-switch.o \
gimple-iterator.o \
gimple-fold.o \
gimple-laddress.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index aa3d75c2357..c42f1adfffd 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1173,6 +1173,10 @@ fconserve-stack
Common Var(flag_conserve_stack) Optimization
Do not perform optimizations increasing noticeably stack usage.
+fconvert-if-to-switch
+Common Report Var(flag_convert_if_to_switch) Optimization
+Perform conversions of if-elseif chain into a switch statement.
+
fcprop-registers
Common Report Var(flag_cprop_registers) Optimization
Perform a register copy-propagation optimization pass.
diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index 07946a85ecc..c8d41065a94 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -170,6 +170,7 @@ DEBUG_COUNTER (if_after_combine)
DEBUG_COUNTER (if_after_reload)
DEBUG_COUNTER (if_conversion)
DEBUG_COUNTER (if_conversion_tree)
+DEBUG_COUNTER (if_to_switch)
DEBUG_COUNTER (ipa_cp_bits)
DEBUG_COUNTER (ipa_mod_ref)
DEBUG_COUNTER (ipa_sra_params)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 48c4aa1e3a3..a15c4aec6f5 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -471,7 +471,7 @@ Objective-C and Objective-C++ Dialects}.
-fassociative-math -fauto-profile -fauto-profile[=@var{path}] @gol
-fauto-inc-dec -fbranch-probabilities @gol
-fcaller-saves @gol
--fcombine-stack-adjustments -fconserve-stack @gol
+-fcombine-stack-adjustments -fconserve-stack -fconvert-if-to-switch @gol
-fcompare-elim -fcprop-registers -fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks -fcx-fortran-rules @gol
-fcx-limited-range @gol
@@ -538,7 +538,7 @@ Objective-C and Objective-C++ Dialects}.
-fthread-jumps -ftracer -ftree-bit-ccp @gol
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
-ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts @gol
--ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
+-ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
-ftree-loop-if-convert -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
-ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -2654,6 +2654,14 @@ Allow conditional expressions with mismatched types in the second and
third arguments. The value of such an expression is void. This option
is not supported for C++.
+@item -fconvert-if-to-switch
+@opindex fconvert-if-to-switch
+Perform conversion of an if cascade into a switch statement.
+Do so if the switch can be later transformed using a jump table
+or a bit test. The transformation can help to produce faster code for
+the switch statement. This flag is enabled by default
+at @option{-O2} and higher.
+
@item -flax-vector-conversions
@opindex flax-vector-conversions
Allow implicit conversions between vectors with differing numbers of
@@ -9757,6 +9765,7 @@ also turns on the following optimization flags:
-falign-labels -falign-loops @gol
-fcaller-saves @gol
-fcode-hoisting @gol
+-fconvert-if-to-switch @gol
-fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks @gol
-fdelete-null-pointer-checks @gol
diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
new file mode 100644
index 00000000000..d67099cd614
--- /dev/null
+++ b/gcc/gimple-if-to-switch.cc
@@ -0,0 +1,762 @@
+/* If-elseif-else to switch conversion pass
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+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/>. */
+
+/* Algorithm of the pass runs in the following steps:
+ a) We walk basic blocks in DOMINATOR order so that we first reach
+ a first condition of a future switch.
+ b) We follow false edges of a if-else-chain and we record chain
+ of GIMPLE conditions. These blocks are only used for comparison
+ of a common SSA_NAME and we do not allow any side effect.
+ c) We remove all basic blocks (except first) of such chain and
+ GIMPLE switch replaces the condition in the first basic block.
+ d) We move all GIMPLE statements in the removed blocks into the
+ first one. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-dfa.h"
+#include "tree-cfgcleanup.h"
+#include "alias.h"
+#include "tree-ssa-loop.h"
+#include "diagnostic.h"
+#include "cfghooks.h"
+#include "tree-into-ssa.h"
+#include "cfganal.h"
+#include "dbgcnt.h"
+#include "target.h"
+#include "alloc-pool.h"
+#include "tree-switch-conversion.h"
+
+using namespace tree_switch_conversion;
+
+/* Tuple that holds minimum and maximum values in a case. */
+
+struct case_range
+{
+ /* Default constructor. */
+ case_range ():
+ m_min (NULL_TREE), m_max (NULL_TREE)
+ {}
+
+ case_range (tree min, tree max):
+ m_min (min), m_max (max)
+ {}
+
+ /* Minimum case value. */
+ tree m_min;
+ /* Maximum case value. */
+ tree m_max;
+};
+
+/* One entry of a if chain. */
+
+struct if_chain_entry
+{
+ /* Constructor. */
+ if_chain_entry (basic_block bb, edge true_edge, edge false_edge)
+ : m_case_values (), m_bb (bb),
+ m_true_edge (true_edge), m_false_edge (false_edge)
+ {
+ m_case_values.create (2);
+ }
+
+ /* Vector of at maximum 2 case ranges. */
+ vec<case_range> m_case_values;
+ /* Basic block of the original condition. */
+ basic_block m_bb;
+ /* True edge of the gimple condition. */
+ edge m_true_edge;
+ /* False edge of the gimple condition. */
+ edge m_false_edge;
+};
+
+/* Master structure for one if to switch conversion candidate. */
+
+struct if_chain
+{
+ /* Default constructor. */
+ if_chain():
+ m_first_condition (NULL), m_index (NULL_TREE), m_entries (),
+ m_phi_map ()
+ {
+ m_entries.create (2);
+ }
+
+ /* Default destructor. */
+ ~if_chain ()
+ {
+ m_entries.release ();
+ }
+
+ /* Set index and check that it is not a different one. */
+ bool set_and_check_index (tree index);
+
+ /* Verify that all case ranges do not overlap. */
+ bool check_non_overlapping_cases ();
+
+ /* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+ bool is_beneficial ();
+
+ /* Record PHI arguments of a given edge E and return true
+ if GIMPLE switch creation will violate a PHI node. */
+ bool record_phi_arguments (edge e);
+
+ /* First condition of the chain. */
+ gcond *m_first_condition;
+ /* Switch index. */
+ tree m_index;
+ /* If chain entries. */
+ vec<if_chain_entry> m_entries;
+ /* PHI map that is later used for reconstruction of PHI nodes. */
+ hash_map<gphi *, tree> m_phi_map;
+};
+
+bool
+if_chain::set_and_check_index (tree index)
+{
+ if (TREE_CODE (index) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (index)))
+ return false;
+
+ if (m_index == NULL)
+ m_index = index;
+
+ return index == m_index;
+}
+
+/* Compare two case ranges by minimum value. */
+
+static int
+range_cmp (const void *a, const void *b)
+{
+ const case_range *cr1 = *(const case_range * const *) a;
+ const case_range *cr2 = *(const case_range * const *) b;
+
+ return tree_int_cst_compare (cr1->m_min, cr2->m_min);
+}
+
+bool
+if_chain::check_non_overlapping_cases ()
+{
+ auto_vec<case_range *> all_ranges;
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ for (unsigned j = 0; j < m_entries[i].m_case_values.length (); j++)
+ all_ranges.safe_push (&m_entries[i].m_case_values[j]);
+
+ all_ranges.qsort (range_cmp);
+
+ for (unsigned i = 0; i < all_ranges.length () - 1; i++)
+ {
+ case_range *left = all_ranges[i];
+ case_range *right = all_ranges[i + 1];
+ if (tree_int_cst_le (left->m_min, right->m_min)
+ && tree_int_cst_le (right->m_min, left->m_max))
+ return false;
+ }
+
+ return true;
+}
+
+/* Compare clusters by minimum value. */
+
+static int
+cluster_cmp (const void *a, const void *b)
+{
+ simple_cluster *sc1 = *(simple_cluster * const *) a;
+ simple_cluster *sc2 = *(simple_cluster * const *) b;
+
+ return tree_int_cst_compare (sc1->get_low (), sc2->get_high ());
+}
+
+static void
+dump_clusters (vec<cluster *> *clusters, const char *message)
+{
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; %s: ", message);
+ for (unsigned i = 0; i < clusters->length (); i++)
+ (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+
+bool
+if_chain::is_beneficial ()
+{
+ profile_probability prob = profile_probability::uninitialized ();
+
+ auto_vec<cluster *> clusters;
+ clusters.create (m_entries.length ());
+
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ {
+ if_chain_entry *entry = &m_entries[i];
+ for (unsigned j = 0; j < entry->m_case_values.length (); j++)
+ {
+ case_range *range = &entry->m_case_values[j];
+ clusters.safe_push (new simple_cluster (range->m_min, range->m_max,
+ NULL_TREE,
+ entry->m_true_edge->dest,
+ prob));
+ }
+ }
+
+ /* Sort clusters and merge them. */
+ auto_vec<cluster *> filtered_clusters;
+ filtered_clusters.create (16);
+ clusters.qsort (cluster_cmp);
+ simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
+ filtered_clusters.safe_push (left);
+
+ for (unsigned i = 1; i < clusters.length (); i++)
+ {
+ simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
+ tree type = TREE_TYPE (left->get_low ());
+ tree pos_one = build_int_cst (type, 1);
+ if (left->m_case_bb == right->m_case_bb)
+ {
+ tree next = int_const_binop (PLUS_EXPR, left->get_high (), pos_one);
+ if (tree_int_cst_equal (next, right->get_low ()))
+ {
+ left->set_high (right->get_high ());
+ continue;
+ }
+ }
+
+ left = static_cast<simple_cluster *> (clusters[i]);
+ filtered_clusters.safe_push (left);
+ }
+
+ dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
+
+ vec<cluster *> output = jump_table_cluster::find_jump_tables (filtered_clusters);
+ bool r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "JT can be built");
+ output.release ();
+ if (r)
+ return true;
+
+ output = bit_test_cluster::find_bit_tests (filtered_clusters);
+ r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "BT can be built");
+ output.release ();
+ return r;
+}
+
+bool
+if_chain::record_phi_arguments (edge e)
+{
+ for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree *v = m_phi_map.get (phi);
+ if (v != NULL)
+ {
+ if (arg != *v)
+ return false;
+ }
+ else
+ m_phi_map.put (phi, arg);
+ }
+ }
+
+ return true;
+}
+
+/* Build case label with MIN and MAX values of a given basic block DEST. */
+
+static tree
+build_case_label (tree min, tree max, basic_block dest)
+{
+ tree label = gimple_block_label (dest);
+ return build_case_label (min, min == max ? NULL_TREE : max, label);
+}
+
+/* Compare two integer constants. */
+
+static int
+label_cmp (const void *a, const void *b)
+{
+ const_tree l1 = *(const const_tree *) a;
+ const_tree l2 = *(const const_tree *) b;
+
+ return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
+}
+
+/* Convert a given if CHAIN into a switch GIMPLE statement. */
+
+static void
+convert_if_conditions_to_switch (if_chain *chain)
+{
+ if (!dbg_cnt (if_to_switch))
+ return;
+
+ auto_vec<tree> labels;
+ if_chain_entry first_cond = chain->m_entries[0];
+
+ unsigned entries = chain->m_entries.length ();
+ edge default_edge = chain->m_entries[entries - 1].m_false_edge;
+ basic_block default_bb = default_edge->dest;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (chain->m_first_condition);
+ for (unsigned i = 0; i < chain->m_entries.length (); i++)
+ {
+ if_chain_entry entry = chain->m_entries[i];
+
+ basic_block case_bb = entry.m_true_edge->dest;
+
+ for (unsigned j = 0; j < entry.m_case_values.length (); j++)
+ labels.safe_push (build_case_label (entry.m_case_values[j].m_min,
+ entry.m_case_values[j].m_max,
+ case_bb));
+ default_bb = entry.m_false_edge->dest;
+
+ if (i == 0)
+ {
+ remove_edge (first_cond.m_true_edge);
+ remove_edge (first_cond.m_false_edge);
+ }
+ else
+ {
+ /* Move all statements from the BB to the BB with gswitch. */
+ auto_vec<gimple *> stmts;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (entry.m_bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_COND)
+ stmts.safe_push (stmt);
+ }
+
+ for (unsigned i = 0; i < stmts.length (); i++)
+ {
+ gimple_stmt_iterator gsi_from = gsi_for_stmt (stmts[i]);
+ gsi_move_before (&gsi_from, &gsi);
+ }
+
+ delete_basic_block (entry.m_bb);
+ }
+
+ make_edge (first_cond.m_bb, case_bb, 0);
+ }
+
+ labels.qsort (label_cmp);
+
+ edge e = find_edge (first_cond.m_bb, default_bb);
+ if (e == NULL)
+ e = make_edge (first_cond.m_bb, default_bb, 0);
+ gswitch *s
+ = gimple_build_switch (chain->m_index,
+ build_case_label (NULL_TREE, NULL_TREE, default_bb),
+ labels);
+
+ gsi_remove (&gsi, true);
+ gsi_insert_before (&gsi, s, GSI_NEW_STMT);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Expanded into a new gimple STMT: ");
+ print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
+ putc ('\n', dump_file);
+ }
+
+ /* Fill up missing PHI node arguments. */
+ for (hash_map<gphi *, tree>::iterator it = chain->m_phi_map.begin ();
+ it != chain->m_phi_map.end (); ++it)
+ {
+ gphi *phi = (*it).first;
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ if (gimple_phi_arg_def (phi, i) == NULL_TREE)
+ {
+ add_phi_arg (phi, (*it).second, gimple_phi_arg_edge (phi, i),
+ UNKNOWN_LOCATION);
+ break;
+ }
+ }
+ }
+ }
+}
+
+static bool
+extract_case_from_stmt (tree rhs1, tree rhs2, tree_code code,
+ if_chain *chain, if_chain_entry *entry,
+ unsigned *visited_stmt_count)
+{
+ tree index = NULL_TREE;
+ case_range range;
+
+ if (code == EQ_EXPR)
+ {
+ /* Handle situation 2a:
+ _1 = aChar_8(D) == 1; */
+ index = rhs1;
+
+ /* We can meet a readonly type used for a constant. */
+ rhs2 = fold_convert (TREE_TYPE (index), rhs2);
+ if (TREE_CODE (rhs2) != INTEGER_CST)
+ return false;
+
+ range = case_range (rhs2, rhs2);
+ *visited_stmt_count += 1;
+ }
+ else if (code == LE_EXPR)
+ {
+ /* Handle situation 2b:
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1; */
+ tree ssa = rhs1;
+ tree range_size = rhs2;
+ if (TREE_CODE (ssa) != SSA_NAME
+ || TREE_CODE (range_size) != INTEGER_CST)
+ return false;
+
+ gassign *subtraction = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (ssa));
+ if (subtraction == NULL
+ || gimple_assign_rhs_code (subtraction) != PLUS_EXPR)
+ return false;
+
+ tree casted = gimple_assign_rhs1 (subtraction);
+ tree min = gimple_assign_rhs2 (subtraction);
+ if (TREE_CODE (casted) != SSA_NAME
+ || TREE_CODE (min) != INTEGER_CST)
+ return false;
+
+ if (!SSA_NAME_IS_DEFAULT_DEF (casted))
+ {
+ gassign *to_unsigned
+ = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (casted));
+ if (to_unsigned == NULL
+ || !gimple_assign_unary_nop_p (to_unsigned)
+ || !TYPE_UNSIGNED (TREE_TYPE (casted)))
+ return false;
+ index = gimple_assign_rhs1 (to_unsigned);
+ ++(*visited_stmt_count);
+ }
+ else
+ index = casted;
+
+ tree type = TREE_TYPE (index);
+ tree range_min = fold_convert (type, const_unop (NEGATE_EXPR, type, min));
+ range = case_range (range_min, const_binop (PLUS_EXPR, type, range_min,
+ fold_convert (type,
+ range_size)));
+ *visited_stmt_count += 2;
+ }
+ else
+ return false;
+
+ if (!chain->set_and_check_index (index))
+ return false;
+ entry->m_case_values.safe_push (range);
+
+ return true;
+}
+
+static void
+find_switch_in_bb (basic_block bb, auto_vec<if_chain *> *all_candidates,
+ auto_bitmap *visited_bbs)
+{
+ if_chain *chain = new if_chain ();
+ unsigned total_case_values = 0;
+
+ while (true)
+ {
+ bool first = chain->m_entries.is_empty ();
+ if (bitmap_bit_p (*visited_bbs, bb->index))
+ break;
+ bitmap_set_bit (*visited_bbs, bb->index);
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ break;
+
+ if (!chain->m_entries.is_empty () && EDGE_COUNT (bb->preds) != 1)
+ break;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (cond == NULL)
+ break;
+
+ if (first)
+ chain->m_first_condition = cond;
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ /* Prevent loosing information for a PHI node where 2 edges will
+ be folded into one. Note that we must do the same also for false_edge
+ (for last BB in a if-elseif chain). */
+ if (!chain->record_phi_arguments (true_edge)
+ || !chain->record_phi_arguments (false_edge))
+ break;
+
+ if_chain_entry entry (bb, true_edge, false_edge);
+
+ /* Current we support following patterns (situations):
+
+ 1) if condition with equal operation:
+
+ <bb 2> :
+ if (argc_8(D) == 1)
+ goto <bb 3>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 2) if condition with a range check:
+
+ <bb 3> :
+ _4 = c_13(D) + 198;
+ if (_4 <= 1)
+ goto <bb 7>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 3) mixture of 1) and 2) with a or condition:
+
+ <bb 2> :
+ _1 = aChar_8(D) == 1;
+ _2 = aChar_8(D) == 10;
+ _3 = _1 | _2;
+ if (_3 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+
+ or:
+
+ <bb 2> :
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1;
+ _4 = aChar_10(D) == 12;
+ _5 = _3 | _4;
+ if (_5 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+ */
+
+ tree lhs = gimple_cond_lhs (cond);
+ tree rhs = gimple_cond_rhs (cond);
+ tree_code code = gimple_cond_code (cond);
+ unsigned visited_stmt_count = 0;
+ unsigned case_values = 0;
+
+ /* Situation 1. */
+ if (code == EQ_EXPR)
+ {
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 2. */
+ else if (code == LE_EXPR)
+ {
+ case_range range;
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 3. */
+ else if (code == NE_EXPR
+ && integer_zerop (rhs)
+ && TREE_CODE (lhs) == SSA_NAME
+ && TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
+ {
+ gassign *def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs));
+ if (def == NULL
+ || gimple_assign_rhs_code (def) != BIT_IOR_EXPR
+ || gimple_bb (def) != bb)
+ break;
+
+ tree rhs1 = gimple_assign_rhs1 (def);
+ tree rhs2 = gimple_assign_rhs2 (def);
+ if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME)
+ break;
+
+ gassign *def1 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs1));
+ gassign *def2 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs2));
+ if (def1 == NULL
+ || def2 == NULL
+ || def1 == def2
+ || gimple_bb (def1) != bb
+ || gimple_bb (def2) != bb)
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def1),
+ gimple_assign_rhs2 (def1),
+ gimple_assign_rhs_code (def1),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2),
+ gimple_assign_rhs_code (def2),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 2;
+ visited_stmt_count += 2;
+ }
+ else
+ break;
+
+ /* If it's not the first condition, then we need a BB without
+ any statements. */
+ if (!first)
+ {
+ unsigned stmt_count = 0;
+ for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
+ !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+ ++stmt_count;
+
+ if (stmt_count - visited_stmt_count != 0)
+ break;
+ }
+
+ total_case_values += case_values;
+ chain->m_entries.safe_push (entry);
+
+ /* Follow if-elseif-elseif chain. */
+ bb = false_edge->dest;
+ }
+
+ if (total_case_values >= 3
+ && chain->check_non_overlapping_cases ()
+ && chain->is_beneficial ())
+ {
+ expanded_location loc
+ = expand_location (gimple_location (chain->m_first_condition));
+ if (dump_file)
+ {
+ fprintf (dump_file, "Condition chain (at %s:%d) with %d conditions "
+ "(%d BBs) transformed into a switch statement.\n",
+ loc.file, loc.line, total_case_values,
+ chain->m_entries.length ());
+ }
+
+ all_candidates->safe_push (chain);
+ }
+ else
+ {
+ /* Unmark last if chain entry to that it can become a potential beginning
+ of another chain. */
+ if (!chain->m_entries.is_empty ())
+ bitmap_clear_bit (*visited_bbs, bb->index);
+ delete chain;
+ }
+}
+
+namespace {
+
+const pass_data pass_data_if_to_switch =
+{
+ GIMPLE_PASS, /* type */
+ "iftoswitch", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_IF_TO_SWITCH, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_cleanup_cfg | TODO_update_ssa /* todo_flags_finish */
+};
+
+class pass_if_to_switch : public gimple_opt_pass
+{
+public:
+ pass_if_to_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_if_to_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_convert_if_to_switch != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_if_to_switch
+
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ auto_vec<if_chain *> all_candidates;
+ auto_vec<basic_block> worklist;
+ auto_bitmap visited_bbs;
+
+ worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun));
+ while (!worklist.is_empty ())
+ {
+ basic_block bb = worklist.pop ();
+ find_switch_in_bb (bb, &all_candidates, &visited_bbs);
+ for (basic_block son = first_dom_son (CDI_DOMINATORS, bb); son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ if (!bitmap_bit_p (visited_bbs, son->index))
+ worklist.safe_push (son);
+ }
+
+ for (unsigned i = 0; i < all_candidates.length (); i++)
+ {
+ convert_if_conditions_to_switch (all_candidates[i]);
+ delete all_candidates[i];
+ }
+
+ /* For now, just wipe the dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+
+ if (!all_candidates.is_empty ())
+ mark_virtual_operands_for_renaming (fun);
+
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_if_to_switch (gcc::context *ctxt)
+{
+ return new pass_if_to_switch (ctxt);
+}
diff --git a/gcc/opts.c b/gcc/opts.c
index da503c32dd0..63a50b28fce 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -510,6 +510,7 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
{ OPT_LEVELS_2_PLUS, OPT_finline_functions, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_fconvert_if_to_switch, NULL, 1 },
/* -O2 and above optimizations, but not -Os or -Og. */
{ OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_falign_functions, NULL, 1 },
diff --git a/gcc/passes.def b/gcc/passes.def
index f865bdc19ac..10d7eeb091b 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -93,6 +93,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_phiopt, true /* early_p */);
NEXT_PASS (pass_modref);
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);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
new file mode 100644
index 00000000000..bcb8ef2a160
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-1.c:9\\) with 5 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
new file mode 100644
index 00000000000..316e772ec29
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespaceNoRange(int aChar)
+{
+ return aChar == 0x0001 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000E ||
+ aChar == 0x0020;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-2.c:7\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
new file mode 100644
index 00000000000..fd07d909a3c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespace(int aChar)
+{
+ return aChar == 0x0009 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000D ||
+ aChar == 0x0020 || aChar == 0x0030;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-3.c:8\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
new file mode 100644
index 00000000000..3ae006f6ca2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 1)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
new file mode 100644
index 00000000000..acb8b4b1211
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int crud (unsigned char c)
+{
+ return (((((((((((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 "Condition chain \\(at .*if-to-switch-5.c:9\\) with 8 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
new file mode 100644
index 00000000000..7af323ae251
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc >= 1 && argc <= 10)
+ foo ();
+ else if (argc == 12)
+ {
+ global += 1;
+ }
+ else if (argc == 13)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 14)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ /* This will be removed with EVRP. */
+ else if (argc >= 7 && argc <= 9)
+ {
+ global = 2;
+ }
+
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
new file mode 100644
index 00000000000..1a919bf025a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+
+int foo(int a)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (a == 2)
+ {
+ global += 123;
+ x = 1;
+ }
+ else if (a == 3)
+ x = 2;
+ else if (a == 10)
+ x = 3;
+ }
+
+ return x;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain " "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
new file mode 100644
index 00000000000..a5f1a1eae18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int global1;
+int global2;
+int global3;
+
+int foo(int a, int b)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (b == 1)
+ global += 2;
+ else if (a == 2)
+ global = 123;
+ else if (a == 3)
+ global1 = 1234;
+ else if (a == 10)
+ global2 = 12345;
+ else if (a == 1)
+ global2 = 123456;
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
index 944362ad076..8e53620a4df 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -1,6 +1,6 @@
/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* bfin*-*-* v850*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
-/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-convert-if-to-switch" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 08c21c04009..ee87718f3e4 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -292,6 +292,7 @@ DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
DEFTIMEVAR (TV_VAR_TRACKING_DATAFLOW , "var-tracking dataflow")
DEFTIMEVAR (TV_VAR_TRACKING_EMIT , "var-tracking emit")
DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine")
+DEFTIMEVAR (TV_TREE_IF_TO_SWITCH , "if to switch conversion")
DEFTIMEVAR (TV_TREE_UNINIT , "uninit var analysis")
DEFTIMEVAR (TV_PLUGIN_INIT , "plugin initialization")
DEFTIMEVAR (TV_PLUGIN_RUN , "plugin execution")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 62e5b696cab..f8adb902345 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -374,6 +374,7 @@ extern gimple_opt_pass *make_pass_empty_loop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite_transforms (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_if_to_switch (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 7515e952eb3..1e25087a21d 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -48,8 +48,8 @@ class cluster
{
public:
/* Constructor. */
- cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
- profile_probability subtree_prob);
+ inline cluster (tree case_label_expr, basic_block case_bb,
+ profile_probability prob, profile_probability subtree_prob);
/* Destructor. */
virtual ~cluster ()
@@ -121,8 +121,8 @@ class simple_cluster: public cluster
{
public:
/* Constructor. */
- simple_cluster (tree low, tree high, tree case_label_expr,
- basic_block case_bb, profile_probability prob);
+ inline simple_cluster (tree low, tree high, tree case_label_expr,
+ basic_block case_bb, profile_probability prob);
/* Destructor. */
~simple_cluster ()
@@ -146,6 +146,11 @@ public:
return m_high;
}
+ void set_high (tree high)
+ {
+ m_high = high;
+ }
+
void
debug ()
{
@@ -271,7 +276,7 @@ public:
static inline unsigned int case_values_threshold (void);
/* Return whether jump table expansion is allowed. */
- static bool is_enabled (void);
+ static inline bool is_enabled (void);
};
/* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
^ permalink raw reply [flat|nested] 3+ messages in thread
* [gcc(refs/users/marxin/heads/if-to-switch-v4)] Add if-chain to switch conversion pass.
@ 2020-10-12 13:04 Martin Liska
0 siblings, 0 replies; 3+ messages in thread
From: Martin Liska @ 2020-10-12 13:04 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:24b84c1cb5b7711f9a8a9682f1246c313e03a3f3
commit 24b84c1cb5b7711f9a8a9682f1246c313e03a3f3
Author: Martin Liska <mliska@suse.cz>
Date: Fri Aug 28 10:26:13 2020 +0200
Add if-chain to switch conversion pass.
gcc/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* Makefile.in: Add new gimple-if-to-switch.o.
* common.opt: Add new option.
* dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
* doc/invoke.texi: Document -fconvert-if-to-switch.
* opts.c: Add -fconvert-if-to-switch at OPT_LEVELS_2_PLUS.
* passes.def: Register new pass.
* timevar.def (TV_TREE_IF_TO_SWITCH): Add new time variable.
* tree-pass.h (make_pass_if_to_switch): New.
* tree-switch-conversion.h: New file.
* gimple-if-to-switch.cc: New file.
gcc/testsuite/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* gcc.dg/tree-ssa/reassoc-32.c: Add -fno-convert-if-to-switch.
* gcc.dg/tree-ssa/if-to-switch-1.c: New test.
* gcc.dg/tree-ssa/if-to-switch-2.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-3.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-4.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-5.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-6.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-7.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-8.c: Likewise.
Diff:
---
gcc/Makefile.in | 1 +
gcc/common.opt | 4 +
gcc/dbgcnt.def | 1 +
gcc/doc/invoke.texi | 13 +-
gcc/gimple-if-to-switch.cc | 762 +++++++++++++++++++++++++
gcc/opts.c | 1 +
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c | 35 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c | 36 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c | 12 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c | 42 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c | 25 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c | 27 +
gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-switch-conversion.h | 15 +-
19 files changed, 993 insertions(+), 8 deletions(-)
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5a8fb0d7612..c7ecda54df2 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1361,6 +1361,7 @@ OBJS = \
gimple-array-bounds.o \
gimple-builder.o \
gimple-expr.o \
+ gimple-if-to-switch.o \
gimple-iterator.o \
gimple-fold.o \
gimple-laddress.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index aa3d75c2357..c42f1adfffd 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1173,6 +1173,10 @@ fconserve-stack
Common Var(flag_conserve_stack) Optimization
Do not perform optimizations increasing noticeably stack usage.
+fconvert-if-to-switch
+Common Report Var(flag_convert_if_to_switch) Optimization
+Perform conversions of if-elseif chain into a switch statement.
+
fcprop-registers
Common Report Var(flag_cprop_registers) Optimization
Perform a register copy-propagation optimization pass.
diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index 07946a85ecc..c8d41065a94 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -170,6 +170,7 @@ DEBUG_COUNTER (if_after_combine)
DEBUG_COUNTER (if_after_reload)
DEBUG_COUNTER (if_conversion)
DEBUG_COUNTER (if_conversion_tree)
+DEBUG_COUNTER (if_to_switch)
DEBUG_COUNTER (ipa_cp_bits)
DEBUG_COUNTER (ipa_mod_ref)
DEBUG_COUNTER (ipa_sra_params)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 48c4aa1e3a3..a15c4aec6f5 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -471,7 +471,7 @@ Objective-C and Objective-C++ Dialects}.
-fassociative-math -fauto-profile -fauto-profile[=@var{path}] @gol
-fauto-inc-dec -fbranch-probabilities @gol
-fcaller-saves @gol
--fcombine-stack-adjustments -fconserve-stack @gol
+-fcombine-stack-adjustments -fconserve-stack -fconvert-if-to-switch @gol
-fcompare-elim -fcprop-registers -fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks -fcx-fortran-rules @gol
-fcx-limited-range @gol
@@ -538,7 +538,7 @@ Objective-C and Objective-C++ Dialects}.
-fthread-jumps -ftracer -ftree-bit-ccp @gol
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
-ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts @gol
--ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
+-ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
-ftree-loop-if-convert -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
-ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -2654,6 +2654,14 @@ Allow conditional expressions with mismatched types in the second and
third arguments. The value of such an expression is void. This option
is not supported for C++.
+@item -fconvert-if-to-switch
+@opindex fconvert-if-to-switch
+Perform conversion of an if cascade into a switch statement.
+Do so if the switch can be later transformed using a jump table
+or a bit test. The transformation can help to produce faster code for
+the switch statement. This flag is enabled by default
+at @option{-O2} and higher.
+
@item -flax-vector-conversions
@opindex flax-vector-conversions
Allow implicit conversions between vectors with differing numbers of
@@ -9757,6 +9765,7 @@ also turns on the following optimization flags:
-falign-labels -falign-loops @gol
-fcaller-saves @gol
-fcode-hoisting @gol
+-fconvert-if-to-switch @gol
-fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks @gol
-fdelete-null-pointer-checks @gol
diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
new file mode 100644
index 00000000000..d67099cd614
--- /dev/null
+++ b/gcc/gimple-if-to-switch.cc
@@ -0,0 +1,762 @@
+/* If-elseif-else to switch conversion pass
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+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/>. */
+
+/* Algorithm of the pass runs in the following steps:
+ a) We walk basic blocks in DOMINATOR order so that we first reach
+ a first condition of a future switch.
+ b) We follow false edges of a if-else-chain and we record chain
+ of GIMPLE conditions. These blocks are only used for comparison
+ of a common SSA_NAME and we do not allow any side effect.
+ c) We remove all basic blocks (except first) of such chain and
+ GIMPLE switch replaces the condition in the first basic block.
+ d) We move all GIMPLE statements in the removed blocks into the
+ first one. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-dfa.h"
+#include "tree-cfgcleanup.h"
+#include "alias.h"
+#include "tree-ssa-loop.h"
+#include "diagnostic.h"
+#include "cfghooks.h"
+#include "tree-into-ssa.h"
+#include "cfganal.h"
+#include "dbgcnt.h"
+#include "target.h"
+#include "alloc-pool.h"
+#include "tree-switch-conversion.h"
+
+using namespace tree_switch_conversion;
+
+/* Tuple that holds minimum and maximum values in a case. */
+
+struct case_range
+{
+ /* Default constructor. */
+ case_range ():
+ m_min (NULL_TREE), m_max (NULL_TREE)
+ {}
+
+ case_range (tree min, tree max):
+ m_min (min), m_max (max)
+ {}
+
+ /* Minimum case value. */
+ tree m_min;
+ /* Maximum case value. */
+ tree m_max;
+};
+
+/* One entry of a if chain. */
+
+struct if_chain_entry
+{
+ /* Constructor. */
+ if_chain_entry (basic_block bb, edge true_edge, edge false_edge)
+ : m_case_values (), m_bb (bb),
+ m_true_edge (true_edge), m_false_edge (false_edge)
+ {
+ m_case_values.create (2);
+ }
+
+ /* Vector of at maximum 2 case ranges. */
+ vec<case_range> m_case_values;
+ /* Basic block of the original condition. */
+ basic_block m_bb;
+ /* True edge of the gimple condition. */
+ edge m_true_edge;
+ /* False edge of the gimple condition. */
+ edge m_false_edge;
+};
+
+/* Master structure for one if to switch conversion candidate. */
+
+struct if_chain
+{
+ /* Default constructor. */
+ if_chain():
+ m_first_condition (NULL), m_index (NULL_TREE), m_entries (),
+ m_phi_map ()
+ {
+ m_entries.create (2);
+ }
+
+ /* Default destructor. */
+ ~if_chain ()
+ {
+ m_entries.release ();
+ }
+
+ /* Set index and check that it is not a different one. */
+ bool set_and_check_index (tree index);
+
+ /* Verify that all case ranges do not overlap. */
+ bool check_non_overlapping_cases ();
+
+ /* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+ bool is_beneficial ();
+
+ /* Record PHI arguments of a given edge E and return true
+ if GIMPLE switch creation will violate a PHI node. */
+ bool record_phi_arguments (edge e);
+
+ /* First condition of the chain. */
+ gcond *m_first_condition;
+ /* Switch index. */
+ tree m_index;
+ /* If chain entries. */
+ vec<if_chain_entry> m_entries;
+ /* PHI map that is later used for reconstruction of PHI nodes. */
+ hash_map<gphi *, tree> m_phi_map;
+};
+
+bool
+if_chain::set_and_check_index (tree index)
+{
+ if (TREE_CODE (index) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (index)))
+ return false;
+
+ if (m_index == NULL)
+ m_index = index;
+
+ return index == m_index;
+}
+
+/* Compare two case ranges by minimum value. */
+
+static int
+range_cmp (const void *a, const void *b)
+{
+ const case_range *cr1 = *(const case_range * const *) a;
+ const case_range *cr2 = *(const case_range * const *) b;
+
+ return tree_int_cst_compare (cr1->m_min, cr2->m_min);
+}
+
+bool
+if_chain::check_non_overlapping_cases ()
+{
+ auto_vec<case_range *> all_ranges;
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ for (unsigned j = 0; j < m_entries[i].m_case_values.length (); j++)
+ all_ranges.safe_push (&m_entries[i].m_case_values[j]);
+
+ all_ranges.qsort (range_cmp);
+
+ for (unsigned i = 0; i < all_ranges.length () - 1; i++)
+ {
+ case_range *left = all_ranges[i];
+ case_range *right = all_ranges[i + 1];
+ if (tree_int_cst_le (left->m_min, right->m_min)
+ && tree_int_cst_le (right->m_min, left->m_max))
+ return false;
+ }
+
+ return true;
+}
+
+/* Compare clusters by minimum value. */
+
+static int
+cluster_cmp (const void *a, const void *b)
+{
+ simple_cluster *sc1 = *(simple_cluster * const *) a;
+ simple_cluster *sc2 = *(simple_cluster * const *) b;
+
+ return tree_int_cst_compare (sc1->get_low (), sc2->get_high ());
+}
+
+static void
+dump_clusters (vec<cluster *> *clusters, const char *message)
+{
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; %s: ", message);
+ for (unsigned i = 0; i < clusters->length (); i++)
+ (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+
+bool
+if_chain::is_beneficial ()
+{
+ profile_probability prob = profile_probability::uninitialized ();
+
+ auto_vec<cluster *> clusters;
+ clusters.create (m_entries.length ());
+
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ {
+ if_chain_entry *entry = &m_entries[i];
+ for (unsigned j = 0; j < entry->m_case_values.length (); j++)
+ {
+ case_range *range = &entry->m_case_values[j];
+ clusters.safe_push (new simple_cluster (range->m_min, range->m_max,
+ NULL_TREE,
+ entry->m_true_edge->dest,
+ prob));
+ }
+ }
+
+ /* Sort clusters and merge them. */
+ auto_vec<cluster *> filtered_clusters;
+ filtered_clusters.create (16);
+ clusters.qsort (cluster_cmp);
+ simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
+ filtered_clusters.safe_push (left);
+
+ for (unsigned i = 1; i < clusters.length (); i++)
+ {
+ simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
+ tree type = TREE_TYPE (left->get_low ());
+ tree pos_one = build_int_cst (type, 1);
+ if (left->m_case_bb == right->m_case_bb)
+ {
+ tree next = int_const_binop (PLUS_EXPR, left->get_high (), pos_one);
+ if (tree_int_cst_equal (next, right->get_low ()))
+ {
+ left->set_high (right->get_high ());
+ continue;
+ }
+ }
+
+ left = static_cast<simple_cluster *> (clusters[i]);
+ filtered_clusters.safe_push (left);
+ }
+
+ dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
+
+ vec<cluster *> output = jump_table_cluster::find_jump_tables (filtered_clusters);
+ bool r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "JT can be built");
+ output.release ();
+ if (r)
+ return true;
+
+ output = bit_test_cluster::find_bit_tests (filtered_clusters);
+ r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "BT can be built");
+ output.release ();
+ return r;
+}
+
+bool
+if_chain::record_phi_arguments (edge e)
+{
+ for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree *v = m_phi_map.get (phi);
+ if (v != NULL)
+ {
+ if (arg != *v)
+ return false;
+ }
+ else
+ m_phi_map.put (phi, arg);
+ }
+ }
+
+ return true;
+}
+
+/* Build case label with MIN and MAX values of a given basic block DEST. */
+
+static tree
+build_case_label (tree min, tree max, basic_block dest)
+{
+ tree label = gimple_block_label (dest);
+ return build_case_label (min, min == max ? NULL_TREE : max, label);
+}
+
+/* Compare two integer constants. */
+
+static int
+label_cmp (const void *a, const void *b)
+{
+ const_tree l1 = *(const const_tree *) a;
+ const_tree l2 = *(const const_tree *) b;
+
+ return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
+}
+
+/* Convert a given if CHAIN into a switch GIMPLE statement. */
+
+static void
+convert_if_conditions_to_switch (if_chain *chain)
+{
+ if (!dbg_cnt (if_to_switch))
+ return;
+
+ auto_vec<tree> labels;
+ if_chain_entry first_cond = chain->m_entries[0];
+
+ unsigned entries = chain->m_entries.length ();
+ edge default_edge = chain->m_entries[entries - 1].m_false_edge;
+ basic_block default_bb = default_edge->dest;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (chain->m_first_condition);
+ for (unsigned i = 0; i < chain->m_entries.length (); i++)
+ {
+ if_chain_entry entry = chain->m_entries[i];
+
+ basic_block case_bb = entry.m_true_edge->dest;
+
+ for (unsigned j = 0; j < entry.m_case_values.length (); j++)
+ labels.safe_push (build_case_label (entry.m_case_values[j].m_min,
+ entry.m_case_values[j].m_max,
+ case_bb));
+ default_bb = entry.m_false_edge->dest;
+
+ if (i == 0)
+ {
+ remove_edge (first_cond.m_true_edge);
+ remove_edge (first_cond.m_false_edge);
+ }
+ else
+ {
+ /* Move all statements from the BB to the BB with gswitch. */
+ auto_vec<gimple *> stmts;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (entry.m_bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_COND)
+ stmts.safe_push (stmt);
+ }
+
+ for (unsigned i = 0; i < stmts.length (); i++)
+ {
+ gimple_stmt_iterator gsi_from = gsi_for_stmt (stmts[i]);
+ gsi_move_before (&gsi_from, &gsi);
+ }
+
+ delete_basic_block (entry.m_bb);
+ }
+
+ make_edge (first_cond.m_bb, case_bb, 0);
+ }
+
+ labels.qsort (label_cmp);
+
+ edge e = find_edge (first_cond.m_bb, default_bb);
+ if (e == NULL)
+ e = make_edge (first_cond.m_bb, default_bb, 0);
+ gswitch *s
+ = gimple_build_switch (chain->m_index,
+ build_case_label (NULL_TREE, NULL_TREE, default_bb),
+ labels);
+
+ gsi_remove (&gsi, true);
+ gsi_insert_before (&gsi, s, GSI_NEW_STMT);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Expanded into a new gimple STMT: ");
+ print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
+ putc ('\n', dump_file);
+ }
+
+ /* Fill up missing PHI node arguments. */
+ for (hash_map<gphi *, tree>::iterator it = chain->m_phi_map.begin ();
+ it != chain->m_phi_map.end (); ++it)
+ {
+ gphi *phi = (*it).first;
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ if (gimple_phi_arg_def (phi, i) == NULL_TREE)
+ {
+ add_phi_arg (phi, (*it).second, gimple_phi_arg_edge (phi, i),
+ UNKNOWN_LOCATION);
+ break;
+ }
+ }
+ }
+ }
+}
+
+static bool
+extract_case_from_stmt (tree rhs1, tree rhs2, tree_code code,
+ if_chain *chain, if_chain_entry *entry,
+ unsigned *visited_stmt_count)
+{
+ tree index = NULL_TREE;
+ case_range range;
+
+ if (code == EQ_EXPR)
+ {
+ /* Handle situation 2a:
+ _1 = aChar_8(D) == 1; */
+ index = rhs1;
+
+ /* We can meet a readonly type used for a constant. */
+ rhs2 = fold_convert (TREE_TYPE (index), rhs2);
+ if (TREE_CODE (rhs2) != INTEGER_CST)
+ return false;
+
+ range = case_range (rhs2, rhs2);
+ *visited_stmt_count += 1;
+ }
+ else if (code == LE_EXPR)
+ {
+ /* Handle situation 2b:
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1; */
+ tree ssa = rhs1;
+ tree range_size = rhs2;
+ if (TREE_CODE (ssa) != SSA_NAME
+ || TREE_CODE (range_size) != INTEGER_CST)
+ return false;
+
+ gassign *subtraction = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (ssa));
+ if (subtraction == NULL
+ || gimple_assign_rhs_code (subtraction) != PLUS_EXPR)
+ return false;
+
+ tree casted = gimple_assign_rhs1 (subtraction);
+ tree min = gimple_assign_rhs2 (subtraction);
+ if (TREE_CODE (casted) != SSA_NAME
+ || TREE_CODE (min) != INTEGER_CST)
+ return false;
+
+ if (!SSA_NAME_IS_DEFAULT_DEF (casted))
+ {
+ gassign *to_unsigned
+ = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (casted));
+ if (to_unsigned == NULL
+ || !gimple_assign_unary_nop_p (to_unsigned)
+ || !TYPE_UNSIGNED (TREE_TYPE (casted)))
+ return false;
+ index = gimple_assign_rhs1 (to_unsigned);
+ ++(*visited_stmt_count);
+ }
+ else
+ index = casted;
+
+ tree type = TREE_TYPE (index);
+ tree range_min = fold_convert (type, const_unop (NEGATE_EXPR, type, min));
+ range = case_range (range_min, const_binop (PLUS_EXPR, type, range_min,
+ fold_convert (type,
+ range_size)));
+ *visited_stmt_count += 2;
+ }
+ else
+ return false;
+
+ if (!chain->set_and_check_index (index))
+ return false;
+ entry->m_case_values.safe_push (range);
+
+ return true;
+}
+
+static void
+find_switch_in_bb (basic_block bb, auto_vec<if_chain *> *all_candidates,
+ auto_bitmap *visited_bbs)
+{
+ if_chain *chain = new if_chain ();
+ unsigned total_case_values = 0;
+
+ while (true)
+ {
+ bool first = chain->m_entries.is_empty ();
+ if (bitmap_bit_p (*visited_bbs, bb->index))
+ break;
+ bitmap_set_bit (*visited_bbs, bb->index);
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ break;
+
+ if (!chain->m_entries.is_empty () && EDGE_COUNT (bb->preds) != 1)
+ break;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (cond == NULL)
+ break;
+
+ if (first)
+ chain->m_first_condition = cond;
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ /* Prevent loosing information for a PHI node where 2 edges will
+ be folded into one. Note that we must do the same also for false_edge
+ (for last BB in a if-elseif chain). */
+ if (!chain->record_phi_arguments (true_edge)
+ || !chain->record_phi_arguments (false_edge))
+ break;
+
+ if_chain_entry entry (bb, true_edge, false_edge);
+
+ /* Current we support following patterns (situations):
+
+ 1) if condition with equal operation:
+
+ <bb 2> :
+ if (argc_8(D) == 1)
+ goto <bb 3>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 2) if condition with a range check:
+
+ <bb 3> :
+ _4 = c_13(D) + 198;
+ if (_4 <= 1)
+ goto <bb 7>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 3) mixture of 1) and 2) with a or condition:
+
+ <bb 2> :
+ _1 = aChar_8(D) == 1;
+ _2 = aChar_8(D) == 10;
+ _3 = _1 | _2;
+ if (_3 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+
+ or:
+
+ <bb 2> :
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1;
+ _4 = aChar_10(D) == 12;
+ _5 = _3 | _4;
+ if (_5 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+ */
+
+ tree lhs = gimple_cond_lhs (cond);
+ tree rhs = gimple_cond_rhs (cond);
+ tree_code code = gimple_cond_code (cond);
+ unsigned visited_stmt_count = 0;
+ unsigned case_values = 0;
+
+ /* Situation 1. */
+ if (code == EQ_EXPR)
+ {
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 2. */
+ else if (code == LE_EXPR)
+ {
+ case_range range;
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 3. */
+ else if (code == NE_EXPR
+ && integer_zerop (rhs)
+ && TREE_CODE (lhs) == SSA_NAME
+ && TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
+ {
+ gassign *def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs));
+ if (def == NULL
+ || gimple_assign_rhs_code (def) != BIT_IOR_EXPR
+ || gimple_bb (def) != bb)
+ break;
+
+ tree rhs1 = gimple_assign_rhs1 (def);
+ tree rhs2 = gimple_assign_rhs2 (def);
+ if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME)
+ break;
+
+ gassign *def1 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs1));
+ gassign *def2 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs2));
+ if (def1 == NULL
+ || def2 == NULL
+ || def1 == def2
+ || gimple_bb (def1) != bb
+ || gimple_bb (def2) != bb)
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def1),
+ gimple_assign_rhs2 (def1),
+ gimple_assign_rhs_code (def1),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2),
+ gimple_assign_rhs_code (def2),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 2;
+ visited_stmt_count += 2;
+ }
+ else
+ break;
+
+ /* If it's not the first condition, then we need a BB without
+ any statements. */
+ if (!first)
+ {
+ unsigned stmt_count = 0;
+ for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
+ !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+ ++stmt_count;
+
+ if (stmt_count - visited_stmt_count != 0)
+ break;
+ }
+
+ total_case_values += case_values;
+ chain->m_entries.safe_push (entry);
+
+ /* Follow if-elseif-elseif chain. */
+ bb = false_edge->dest;
+ }
+
+ if (total_case_values >= 3
+ && chain->check_non_overlapping_cases ()
+ && chain->is_beneficial ())
+ {
+ expanded_location loc
+ = expand_location (gimple_location (chain->m_first_condition));
+ if (dump_file)
+ {
+ fprintf (dump_file, "Condition chain (at %s:%d) with %d conditions "
+ "(%d BBs) transformed into a switch statement.\n",
+ loc.file, loc.line, total_case_values,
+ chain->m_entries.length ());
+ }
+
+ all_candidates->safe_push (chain);
+ }
+ else
+ {
+ /* Unmark last if chain entry to that it can become a potential beginning
+ of another chain. */
+ if (!chain->m_entries.is_empty ())
+ bitmap_clear_bit (*visited_bbs, bb->index);
+ delete chain;
+ }
+}
+
+namespace {
+
+const pass_data pass_data_if_to_switch =
+{
+ GIMPLE_PASS, /* type */
+ "iftoswitch", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_IF_TO_SWITCH, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_cleanup_cfg | TODO_update_ssa /* todo_flags_finish */
+};
+
+class pass_if_to_switch : public gimple_opt_pass
+{
+public:
+ pass_if_to_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_if_to_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_convert_if_to_switch != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_if_to_switch
+
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ auto_vec<if_chain *> all_candidates;
+ auto_vec<basic_block> worklist;
+ auto_bitmap visited_bbs;
+
+ worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun));
+ while (!worklist.is_empty ())
+ {
+ basic_block bb = worklist.pop ();
+ find_switch_in_bb (bb, &all_candidates, &visited_bbs);
+ for (basic_block son = first_dom_son (CDI_DOMINATORS, bb); son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ if (!bitmap_bit_p (visited_bbs, son->index))
+ worklist.safe_push (son);
+ }
+
+ for (unsigned i = 0; i < all_candidates.length (); i++)
+ {
+ convert_if_conditions_to_switch (all_candidates[i]);
+ delete all_candidates[i];
+ }
+
+ /* For now, just wipe the dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+
+ if (!all_candidates.is_empty ())
+ mark_virtual_operands_for_renaming (fun);
+
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_if_to_switch (gcc::context *ctxt)
+{
+ return new pass_if_to_switch (ctxt);
+}
diff --git a/gcc/opts.c b/gcc/opts.c
index da503c32dd0..63a50b28fce 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -510,6 +510,7 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
{ OPT_LEVELS_2_PLUS, OPT_finline_functions, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_fconvert_if_to_switch, NULL, 1 },
/* -O2 and above optimizations, but not -Os or -Og. */
{ OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_falign_functions, NULL, 1 },
diff --git a/gcc/passes.def b/gcc/passes.def
index f865bdc19ac..10d7eeb091b 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -93,6 +93,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_phiopt, true /* early_p */);
NEXT_PASS (pass_modref);
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);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
new file mode 100644
index 00000000000..bcb8ef2a160
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-1.c:9\\) with 5 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
new file mode 100644
index 00000000000..316e772ec29
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespaceNoRange(int aChar)
+{
+ return aChar == 0x0001 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000E ||
+ aChar == 0x0020;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-2.c:7\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
new file mode 100644
index 00000000000..fd07d909a3c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespace(int aChar)
+{
+ return aChar == 0x0009 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000D ||
+ aChar == 0x0020 || aChar == 0x0030;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-3.c:8\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
new file mode 100644
index 00000000000..3ae006f6ca2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 1)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
new file mode 100644
index 00000000000..acb8b4b1211
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int crud (unsigned char c)
+{
+ return (((((((((((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 "Condition chain \\(at .*if-to-switch-5.c:9\\) with 8 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
new file mode 100644
index 00000000000..7af323ae251
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc >= 1 && argc <= 10)
+ foo ();
+ else if (argc == 12)
+ {
+ global += 1;
+ }
+ else if (argc == 13)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 14)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ /* This will be removed with EVRP. */
+ else if (argc >= 7 && argc <= 9)
+ {
+ global = 2;
+ }
+
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
new file mode 100644
index 00000000000..1a919bf025a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+
+int foo(int a)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (a == 2)
+ {
+ global += 123;
+ x = 1;
+ }
+ else if (a == 3)
+ x = 2;
+ else if (a == 10)
+ x = 3;
+ }
+
+ return x;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain " "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
new file mode 100644
index 00000000000..a5f1a1eae18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int global1;
+int global2;
+int global3;
+
+int foo(int a, int b)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (b == 1)
+ global += 2;
+ else if (a == 2)
+ global = 123;
+ else if (a == 3)
+ global1 = 1234;
+ else if (a == 10)
+ global2 = 12345;
+ else if (a == 1)
+ global2 = 123456;
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
index 944362ad076..8e53620a4df 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -1,6 +1,6 @@
/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* bfin*-*-* v850*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
-/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-convert-if-to-switch" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 08c21c04009..ee87718f3e4 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -292,6 +292,7 @@ DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
DEFTIMEVAR (TV_VAR_TRACKING_DATAFLOW , "var-tracking dataflow")
DEFTIMEVAR (TV_VAR_TRACKING_EMIT , "var-tracking emit")
DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine")
+DEFTIMEVAR (TV_TREE_IF_TO_SWITCH , "if to switch conversion")
DEFTIMEVAR (TV_TREE_UNINIT , "uninit var analysis")
DEFTIMEVAR (TV_PLUGIN_INIT , "plugin initialization")
DEFTIMEVAR (TV_PLUGIN_RUN , "plugin execution")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 62e5b696cab..f8adb902345 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -374,6 +374,7 @@ extern gimple_opt_pass *make_pass_empty_loop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite_transforms (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_if_to_switch (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 7515e952eb3..1e25087a21d 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -48,8 +48,8 @@ class cluster
{
public:
/* Constructor. */
- cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
- profile_probability subtree_prob);
+ inline cluster (tree case_label_expr, basic_block case_bb,
+ profile_probability prob, profile_probability subtree_prob);
/* Destructor. */
virtual ~cluster ()
@@ -121,8 +121,8 @@ class simple_cluster: public cluster
{
public:
/* Constructor. */
- simple_cluster (tree low, tree high, tree case_label_expr,
- basic_block case_bb, profile_probability prob);
+ inline simple_cluster (tree low, tree high, tree case_label_expr,
+ basic_block case_bb, profile_probability prob);
/* Destructor. */
~simple_cluster ()
@@ -146,6 +146,11 @@ public:
return m_high;
}
+ void set_high (tree high)
+ {
+ m_high = high;
+ }
+
void
debug ()
{
@@ -271,7 +276,7 @@ public:
static inline unsigned int case_values_threshold (void);
/* Return whether jump table expansion is allowed. */
- static bool is_enabled (void);
+ static inline bool is_enabled (void);
};
/* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
^ permalink raw reply [flat|nested] 3+ messages in thread
* [gcc(refs/users/marxin/heads/if-to-switch-v4)] Add if-chain to switch conversion pass.
@ 2020-10-06 13:49 Martin Liska
0 siblings, 0 replies; 3+ messages in thread
From: Martin Liska @ 2020-10-06 13:49 UTC (permalink / raw)
To: gcc-cvs
https://gcc.gnu.org/g:2247b390dc18dfaffa4caa4f20633d66b948da79
commit 2247b390dc18dfaffa4caa4f20633d66b948da79
Author: Martin Liska <mliska@suse.cz>
Date: Fri Aug 28 10:26:13 2020 +0200
Add if-chain to switch conversion pass.
gcc/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* Makefile.in: Add new gimple-if-to-switch.o.
* common.opt: Add new option.
* dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
* doc/invoke.texi: Document -fconvert-if-to-switch.
* opts.c: Add -fconvert-if-to-switch at OPT_LEVELS_2_PLUS.
* passes.def: Register new pass.
* timevar.def (TV_TREE_IF_TO_SWITCH): Add new time variable.
* tree-pass.h (make_pass_if_to_switch): New.
* tree-switch-conversion.h: New file.
* gimple-if-to-switch.cc: New file.
gcc/testsuite/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* gcc.dg/tree-ssa/reassoc-32.c: Add -fno-convert-if-to-switch.
* gcc.dg/tree-ssa/if-to-switch-1.c: New test.
* gcc.dg/tree-ssa/if-to-switch-2.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-3.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-4.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-5.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-6.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-7.c: Likewise.
* gcc.dg/tree-ssa/if-to-switch-8.c: Likewise.
Diff:
---
gcc/Makefile.in | 1 +
gcc/common.opt | 4 +
gcc/dbgcnt.def | 1 +
gcc/doc/invoke.texi | 13 +-
gcc/gimple-if-to-switch.cc | 762 +++++++++++++++++++++++++
gcc/opts.c | 1 +
gcc/passes.def | 1 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c | 35 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c | 11 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c | 36 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c | 12 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c | 42 ++
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c | 25 +
gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c | 27 +
gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-switch-conversion.h | 15 +-
19 files changed, 993 insertions(+), 8 deletions(-)
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 50d6c83eb76..ebecd18380e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1361,6 +1361,7 @@ OBJS = \
gimple-array-bounds.o \
gimple-builder.o \
gimple-expr.o \
+ gimple-if-to-switch.o \
gimple-iterator.o \
gimple-fold.o \
gimple-laddress.o \
diff --git a/gcc/common.opt b/gcc/common.opt
index 3169d71cea5..337a30cdac9 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -1173,6 +1173,10 @@ fconserve-stack
Common Var(flag_conserve_stack) Optimization
Do not perform optimizations increasing noticeably stack usage.
+fconvert-if-to-switch
+Common Report Var(flag_convert_if_to_switch) Optimization
+Perform conversions of if-elseif chain into a switch statement.
+
fcprop-registers
Common Report Var(flag_cprop_registers) Optimization
Perform a register copy-propagation optimization pass.
diff --git a/gcc/dbgcnt.def b/gcc/dbgcnt.def
index cf8775b2b66..e393e45deb4 100644
--- a/gcc/dbgcnt.def
+++ b/gcc/dbgcnt.def
@@ -170,6 +170,7 @@ DEBUG_COUNTER (if_after_combine)
DEBUG_COUNTER (if_after_reload)
DEBUG_COUNTER (if_conversion)
DEBUG_COUNTER (if_conversion_tree)
+DEBUG_COUNTER (if_to_switch)
DEBUG_COUNTER (ipa_cp_bits)
DEBUG_COUNTER (ipa_sra_params)
DEBUG_COUNTER (ipa_sra_retvalues)
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index cf9db5bd27d..d1536d8f533 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -471,7 +471,7 @@ Objective-C and Objective-C++ Dialects}.
-fassociative-math -fauto-profile -fauto-profile[=@var{path}] @gol
-fauto-inc-dec -fbranch-probabilities @gol
-fcaller-saves @gol
--fcombine-stack-adjustments -fconserve-stack @gol
+-fcombine-stack-adjustments -fconserve-stack -fconvert-if-to-switch @gol
-fcompare-elim -fcprop-registers -fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks -fcx-fortran-rules @gol
-fcx-limited-range @gol
@@ -538,7 +538,7 @@ Objective-C and Objective-C++ Dialects}.
-fthread-jumps -ftracer -ftree-bit-ccp @gol
-ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
-ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts @gol
--ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
+-ftree-dse -ftree-forwprop -ftree-fre -fcode-hoisting @gol
-ftree-loop-if-convert -ftree-loop-im @gol
-ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
-ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
@@ -2654,6 +2654,14 @@ Allow conditional expressions with mismatched types in the second and
third arguments. The value of such an expression is void. This option
is not supported for C++.
+@item -fconvert-if-to-switch
+@opindex fconvert-if-to-switch
+Perform conversion of an if cascade into a switch statement.
+Do so if the switch can be later transformed using a jump table
+or a bit test. The transformation can help to produce faster code for
+the switch statement. This flag is enabled by default
+at @option{-O2} and higher.
+
@item -flax-vector-conversions
@opindex flax-vector-conversions
Allow implicit conversions between vectors with differing numbers of
@@ -9756,6 +9764,7 @@ also turns on the following optimization flags:
-falign-labels -falign-loops @gol
-fcaller-saves @gol
-fcode-hoisting @gol
+-fconvert-if-to-switch @gol
-fcrossjumping @gol
-fcse-follow-jumps -fcse-skip-blocks @gol
-fdelete-null-pointer-checks @gol
diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
new file mode 100644
index 00000000000..d67099cd614
--- /dev/null
+++ b/gcc/gimple-if-to-switch.cc
@@ -0,0 +1,762 @@
+/* If-elseif-else to switch conversion pass
+ Copyright (C) 2020 Free Software Foundation, Inc.
+
+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/>. */
+
+/* Algorithm of the pass runs in the following steps:
+ a) We walk basic blocks in DOMINATOR order so that we first reach
+ a first condition of a future switch.
+ b) We follow false edges of a if-else-chain and we record chain
+ of GIMPLE conditions. These blocks are only used for comparison
+ of a common SSA_NAME and we do not allow any side effect.
+ c) We remove all basic blocks (except first) of such chain and
+ GIMPLE switch replaces the condition in the first basic block.
+ d) We move all GIMPLE statements in the removed blocks into the
+ first one. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "rtl.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "fold-const.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-dfa.h"
+#include "tree-cfgcleanup.h"
+#include "alias.h"
+#include "tree-ssa-loop.h"
+#include "diagnostic.h"
+#include "cfghooks.h"
+#include "tree-into-ssa.h"
+#include "cfganal.h"
+#include "dbgcnt.h"
+#include "target.h"
+#include "alloc-pool.h"
+#include "tree-switch-conversion.h"
+
+using namespace tree_switch_conversion;
+
+/* Tuple that holds minimum and maximum values in a case. */
+
+struct case_range
+{
+ /* Default constructor. */
+ case_range ():
+ m_min (NULL_TREE), m_max (NULL_TREE)
+ {}
+
+ case_range (tree min, tree max):
+ m_min (min), m_max (max)
+ {}
+
+ /* Minimum case value. */
+ tree m_min;
+ /* Maximum case value. */
+ tree m_max;
+};
+
+/* One entry of a if chain. */
+
+struct if_chain_entry
+{
+ /* Constructor. */
+ if_chain_entry (basic_block bb, edge true_edge, edge false_edge)
+ : m_case_values (), m_bb (bb),
+ m_true_edge (true_edge), m_false_edge (false_edge)
+ {
+ m_case_values.create (2);
+ }
+
+ /* Vector of at maximum 2 case ranges. */
+ vec<case_range> m_case_values;
+ /* Basic block of the original condition. */
+ basic_block m_bb;
+ /* True edge of the gimple condition. */
+ edge m_true_edge;
+ /* False edge of the gimple condition. */
+ edge m_false_edge;
+};
+
+/* Master structure for one if to switch conversion candidate. */
+
+struct if_chain
+{
+ /* Default constructor. */
+ if_chain():
+ m_first_condition (NULL), m_index (NULL_TREE), m_entries (),
+ m_phi_map ()
+ {
+ m_entries.create (2);
+ }
+
+ /* Default destructor. */
+ ~if_chain ()
+ {
+ m_entries.release ();
+ }
+
+ /* Set index and check that it is not a different one. */
+ bool set_and_check_index (tree index);
+
+ /* Verify that all case ranges do not overlap. */
+ bool check_non_overlapping_cases ();
+
+ /* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+ bool is_beneficial ();
+
+ /* Record PHI arguments of a given edge E and return true
+ if GIMPLE switch creation will violate a PHI node. */
+ bool record_phi_arguments (edge e);
+
+ /* First condition of the chain. */
+ gcond *m_first_condition;
+ /* Switch index. */
+ tree m_index;
+ /* If chain entries. */
+ vec<if_chain_entry> m_entries;
+ /* PHI map that is later used for reconstruction of PHI nodes. */
+ hash_map<gphi *, tree> m_phi_map;
+};
+
+bool
+if_chain::set_and_check_index (tree index)
+{
+ if (TREE_CODE (index) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (index)))
+ return false;
+
+ if (m_index == NULL)
+ m_index = index;
+
+ return index == m_index;
+}
+
+/* Compare two case ranges by minimum value. */
+
+static int
+range_cmp (const void *a, const void *b)
+{
+ const case_range *cr1 = *(const case_range * const *) a;
+ const case_range *cr2 = *(const case_range * const *) b;
+
+ return tree_int_cst_compare (cr1->m_min, cr2->m_min);
+}
+
+bool
+if_chain::check_non_overlapping_cases ()
+{
+ auto_vec<case_range *> all_ranges;
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ for (unsigned j = 0; j < m_entries[i].m_case_values.length (); j++)
+ all_ranges.safe_push (&m_entries[i].m_case_values[j]);
+
+ all_ranges.qsort (range_cmp);
+
+ for (unsigned i = 0; i < all_ranges.length () - 1; i++)
+ {
+ case_range *left = all_ranges[i];
+ case_range *right = all_ranges[i + 1];
+ if (tree_int_cst_le (left->m_min, right->m_min)
+ && tree_int_cst_le (right->m_min, left->m_max))
+ return false;
+ }
+
+ return true;
+}
+
+/* Compare clusters by minimum value. */
+
+static int
+cluster_cmp (const void *a, const void *b)
+{
+ simple_cluster *sc1 = *(simple_cluster * const *) a;
+ simple_cluster *sc2 = *(simple_cluster * const *) b;
+
+ return tree_int_cst_compare (sc1->get_low (), sc2->get_high ());
+}
+
+static void
+dump_clusters (vec<cluster *> *clusters, const char *message)
+{
+ if (dump_file)
+ {
+ fprintf (dump_file, ";; %s: ", message);
+ for (unsigned i = 0; i < clusters->length (); i++)
+ (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+ fprintf (dump_file, "\n");
+ }
+}
+
+/* Return true when the switch can be expanded with a jump table or
+ a bit test (at least partially). */
+
+bool
+if_chain::is_beneficial ()
+{
+ profile_probability prob = profile_probability::uninitialized ();
+
+ auto_vec<cluster *> clusters;
+ clusters.create (m_entries.length ());
+
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ {
+ if_chain_entry *entry = &m_entries[i];
+ for (unsigned j = 0; j < entry->m_case_values.length (); j++)
+ {
+ case_range *range = &entry->m_case_values[j];
+ clusters.safe_push (new simple_cluster (range->m_min, range->m_max,
+ NULL_TREE,
+ entry->m_true_edge->dest,
+ prob));
+ }
+ }
+
+ /* Sort clusters and merge them. */
+ auto_vec<cluster *> filtered_clusters;
+ filtered_clusters.create (16);
+ clusters.qsort (cluster_cmp);
+ simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
+ filtered_clusters.safe_push (left);
+
+ for (unsigned i = 1; i < clusters.length (); i++)
+ {
+ simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
+ tree type = TREE_TYPE (left->get_low ());
+ tree pos_one = build_int_cst (type, 1);
+ if (left->m_case_bb == right->m_case_bb)
+ {
+ tree next = int_const_binop (PLUS_EXPR, left->get_high (), pos_one);
+ if (tree_int_cst_equal (next, right->get_low ()))
+ {
+ left->set_high (right->get_high ());
+ continue;
+ }
+ }
+
+ left = static_cast<simple_cluster *> (clusters[i]);
+ filtered_clusters.safe_push (left);
+ }
+
+ dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
+
+ vec<cluster *> output = jump_table_cluster::find_jump_tables (filtered_clusters);
+ bool r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "JT can be built");
+ output.release ();
+ if (r)
+ return true;
+
+ output = bit_test_cluster::find_bit_tests (filtered_clusters);
+ r = output.length () < filtered_clusters.length ();
+ if (r)
+ dump_clusters (&output, "BT can be built");
+ output.release ();
+ return r;
+}
+
+bool
+if_chain::record_phi_arguments (edge e)
+{
+ for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ tree *v = m_phi_map.get (phi);
+ if (v != NULL)
+ {
+ if (arg != *v)
+ return false;
+ }
+ else
+ m_phi_map.put (phi, arg);
+ }
+ }
+
+ return true;
+}
+
+/* Build case label with MIN and MAX values of a given basic block DEST. */
+
+static tree
+build_case_label (tree min, tree max, basic_block dest)
+{
+ tree label = gimple_block_label (dest);
+ return build_case_label (min, min == max ? NULL_TREE : max, label);
+}
+
+/* Compare two integer constants. */
+
+static int
+label_cmp (const void *a, const void *b)
+{
+ const_tree l1 = *(const const_tree *) a;
+ const_tree l2 = *(const const_tree *) b;
+
+ return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
+}
+
+/* Convert a given if CHAIN into a switch GIMPLE statement. */
+
+static void
+convert_if_conditions_to_switch (if_chain *chain)
+{
+ if (!dbg_cnt (if_to_switch))
+ return;
+
+ auto_vec<tree> labels;
+ if_chain_entry first_cond = chain->m_entries[0];
+
+ unsigned entries = chain->m_entries.length ();
+ edge default_edge = chain->m_entries[entries - 1].m_false_edge;
+ basic_block default_bb = default_edge->dest;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (chain->m_first_condition);
+ for (unsigned i = 0; i < chain->m_entries.length (); i++)
+ {
+ if_chain_entry entry = chain->m_entries[i];
+
+ basic_block case_bb = entry.m_true_edge->dest;
+
+ for (unsigned j = 0; j < entry.m_case_values.length (); j++)
+ labels.safe_push (build_case_label (entry.m_case_values[j].m_min,
+ entry.m_case_values[j].m_max,
+ case_bb));
+ default_bb = entry.m_false_edge->dest;
+
+ if (i == 0)
+ {
+ remove_edge (first_cond.m_true_edge);
+ remove_edge (first_cond.m_false_edge);
+ }
+ else
+ {
+ /* Move all statements from the BB to the BB with gswitch. */
+ auto_vec<gimple *> stmts;
+ for (gimple_stmt_iterator gsi = gsi_start_bb (entry.m_bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (gimple_code (stmt) != GIMPLE_COND)
+ stmts.safe_push (stmt);
+ }
+
+ for (unsigned i = 0; i < stmts.length (); i++)
+ {
+ gimple_stmt_iterator gsi_from = gsi_for_stmt (stmts[i]);
+ gsi_move_before (&gsi_from, &gsi);
+ }
+
+ delete_basic_block (entry.m_bb);
+ }
+
+ make_edge (first_cond.m_bb, case_bb, 0);
+ }
+
+ labels.qsort (label_cmp);
+
+ edge e = find_edge (first_cond.m_bb, default_bb);
+ if (e == NULL)
+ e = make_edge (first_cond.m_bb, default_bb, 0);
+ gswitch *s
+ = gimple_build_switch (chain->m_index,
+ build_case_label (NULL_TREE, NULL_TREE, default_bb),
+ labels);
+
+ gsi_remove (&gsi, true);
+ gsi_insert_before (&gsi, s, GSI_NEW_STMT);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Expanded into a new gimple STMT: ");
+ print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
+ putc ('\n', dump_file);
+ }
+
+ /* Fill up missing PHI node arguments. */
+ for (hash_map<gphi *, tree>::iterator it = chain->m_phi_map.begin ();
+ it != chain->m_phi_map.end (); ++it)
+ {
+ gphi *phi = (*it).first;
+ if (!virtual_operand_p (gimple_phi_result (phi)))
+ {
+ for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+ {
+ if (gimple_phi_arg_def (phi, i) == NULL_TREE)
+ {
+ add_phi_arg (phi, (*it).second, gimple_phi_arg_edge (phi, i),
+ UNKNOWN_LOCATION);
+ break;
+ }
+ }
+ }
+ }
+}
+
+static bool
+extract_case_from_stmt (tree rhs1, tree rhs2, tree_code code,
+ if_chain *chain, if_chain_entry *entry,
+ unsigned *visited_stmt_count)
+{
+ tree index = NULL_TREE;
+ case_range range;
+
+ if (code == EQ_EXPR)
+ {
+ /* Handle situation 2a:
+ _1 = aChar_8(D) == 1; */
+ index = rhs1;
+
+ /* We can meet a readonly type used for a constant. */
+ rhs2 = fold_convert (TREE_TYPE (index), rhs2);
+ if (TREE_CODE (rhs2) != INTEGER_CST)
+ return false;
+
+ range = case_range (rhs2, rhs2);
+ *visited_stmt_count += 1;
+ }
+ else if (code == LE_EXPR)
+ {
+ /* Handle situation 2b:
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1; */
+ tree ssa = rhs1;
+ tree range_size = rhs2;
+ if (TREE_CODE (ssa) != SSA_NAME
+ || TREE_CODE (range_size) != INTEGER_CST)
+ return false;
+
+ gassign *subtraction = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (ssa));
+ if (subtraction == NULL
+ || gimple_assign_rhs_code (subtraction) != PLUS_EXPR)
+ return false;
+
+ tree casted = gimple_assign_rhs1 (subtraction);
+ tree min = gimple_assign_rhs2 (subtraction);
+ if (TREE_CODE (casted) != SSA_NAME
+ || TREE_CODE (min) != INTEGER_CST)
+ return false;
+
+ if (!SSA_NAME_IS_DEFAULT_DEF (casted))
+ {
+ gassign *to_unsigned
+ = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (casted));
+ if (to_unsigned == NULL
+ || !gimple_assign_unary_nop_p (to_unsigned)
+ || !TYPE_UNSIGNED (TREE_TYPE (casted)))
+ return false;
+ index = gimple_assign_rhs1 (to_unsigned);
+ ++(*visited_stmt_count);
+ }
+ else
+ index = casted;
+
+ tree type = TREE_TYPE (index);
+ tree range_min = fold_convert (type, const_unop (NEGATE_EXPR, type, min));
+ range = case_range (range_min, const_binop (PLUS_EXPR, type, range_min,
+ fold_convert (type,
+ range_size)));
+ *visited_stmt_count += 2;
+ }
+ else
+ return false;
+
+ if (!chain->set_and_check_index (index))
+ return false;
+ entry->m_case_values.safe_push (range);
+
+ return true;
+}
+
+static void
+find_switch_in_bb (basic_block bb, auto_vec<if_chain *> *all_candidates,
+ auto_bitmap *visited_bbs)
+{
+ if_chain *chain = new if_chain ();
+ unsigned total_case_values = 0;
+
+ while (true)
+ {
+ bool first = chain->m_entries.is_empty ();
+ if (bitmap_bit_p (*visited_bbs, bb->index))
+ break;
+ bitmap_set_bit (*visited_bbs, bb->index);
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ break;
+
+ if (!chain->m_entries.is_empty () && EDGE_COUNT (bb->preds) != 1)
+ break;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (cond == NULL)
+ break;
+
+ if (first)
+ chain->m_first_condition = cond;
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+
+ /* Prevent loosing information for a PHI node where 2 edges will
+ be folded into one. Note that we must do the same also for false_edge
+ (for last BB in a if-elseif chain). */
+ if (!chain->record_phi_arguments (true_edge)
+ || !chain->record_phi_arguments (false_edge))
+ break;
+
+ if_chain_entry entry (bb, true_edge, false_edge);
+
+ /* Current we support following patterns (situations):
+
+ 1) if condition with equal operation:
+
+ <bb 2> :
+ if (argc_8(D) == 1)
+ goto <bb 3>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 2) if condition with a range check:
+
+ <bb 3> :
+ _4 = c_13(D) + 198;
+ if (_4 <= 1)
+ goto <bb 7>; [INV]
+ else
+ goto <bb 4>; [INV]
+
+ 3) mixture of 1) and 2) with a or condition:
+
+ <bb 2> :
+ _1 = aChar_8(D) == 1;
+ _2 = aChar_8(D) == 10;
+ _3 = _1 | _2;
+ if (_3 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+
+ or:
+
+ <bb 2> :
+ aChar.1_1 = (unsigned int) aChar_10(D);
+ _2 = aChar.1_1 + 4294967287;
+ _3 = _2 <= 1;
+ _4 = aChar_10(D) == 12;
+ _5 = _3 | _4;
+ if (_5 != 0)
+ goto <bb 5>; [INV]
+ else
+ goto <bb 3>; [INV]
+ */
+
+ tree lhs = gimple_cond_lhs (cond);
+ tree rhs = gimple_cond_rhs (cond);
+ tree_code code = gimple_cond_code (cond);
+ unsigned visited_stmt_count = 0;
+ unsigned case_values = 0;
+
+ /* Situation 1. */
+ if (code == EQ_EXPR)
+ {
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 2. */
+ else if (code == LE_EXPR)
+ {
+ case_range range;
+ if (!extract_case_from_stmt (lhs, rhs, code, chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 1;
+ }
+ /* Situation 3. */
+ else if (code == NE_EXPR
+ && integer_zerop (rhs)
+ && TREE_CODE (lhs) == SSA_NAME
+ && TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE)
+ {
+ gassign *def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs));
+ if (def == NULL
+ || gimple_assign_rhs_code (def) != BIT_IOR_EXPR
+ || gimple_bb (def) != bb)
+ break;
+
+ tree rhs1 = gimple_assign_rhs1 (def);
+ tree rhs2 = gimple_assign_rhs2 (def);
+ if (TREE_CODE (rhs1) != SSA_NAME || TREE_CODE (rhs2) != SSA_NAME)
+ break;
+
+ gassign *def1 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs1));
+ gassign *def2 = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (rhs2));
+ if (def1 == NULL
+ || def2 == NULL
+ || def1 == def2
+ || gimple_bb (def1) != bb
+ || gimple_bb (def2) != bb)
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def1),
+ gimple_assign_rhs2 (def1),
+ gimple_assign_rhs_code (def1),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+
+ if (!extract_case_from_stmt (gimple_assign_rhs1 (def2),
+ gimple_assign_rhs2 (def2),
+ gimple_assign_rhs_code (def2),
+ chain, &entry,
+ &visited_stmt_count))
+ break;
+ case_values = 2;
+ visited_stmt_count += 2;
+ }
+ else
+ break;
+
+ /* If it's not the first condition, then we need a BB without
+ any statements. */
+ if (!first)
+ {
+ unsigned stmt_count = 0;
+ for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
+ !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+ ++stmt_count;
+
+ if (stmt_count - visited_stmt_count != 0)
+ break;
+ }
+
+ total_case_values += case_values;
+ chain->m_entries.safe_push (entry);
+
+ /* Follow if-elseif-elseif chain. */
+ bb = false_edge->dest;
+ }
+
+ if (total_case_values >= 3
+ && chain->check_non_overlapping_cases ()
+ && chain->is_beneficial ())
+ {
+ expanded_location loc
+ = expand_location (gimple_location (chain->m_first_condition));
+ if (dump_file)
+ {
+ fprintf (dump_file, "Condition chain (at %s:%d) with %d conditions "
+ "(%d BBs) transformed into a switch statement.\n",
+ loc.file, loc.line, total_case_values,
+ chain->m_entries.length ());
+ }
+
+ all_candidates->safe_push (chain);
+ }
+ else
+ {
+ /* Unmark last if chain entry to that it can become a potential beginning
+ of another chain. */
+ if (!chain->m_entries.is_empty ())
+ bitmap_clear_bit (*visited_bbs, bb->index);
+ delete chain;
+ }
+}
+
+namespace {
+
+const pass_data pass_data_if_to_switch =
+{
+ GIMPLE_PASS, /* type */
+ "iftoswitch", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_IF_TO_SWITCH, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_cleanup_cfg | TODO_update_ssa /* todo_flags_finish */
+};
+
+class pass_if_to_switch : public gimple_opt_pass
+{
+public:
+ pass_if_to_switch (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_if_to_switch, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_convert_if_to_switch != 0; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_if_to_switch
+
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ auto_vec<if_chain *> all_candidates;
+ auto_vec<basic_block> worklist;
+ auto_bitmap visited_bbs;
+
+ worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (fun));
+ while (!worklist.is_empty ())
+ {
+ basic_block bb = worklist.pop ();
+ find_switch_in_bb (bb, &all_candidates, &visited_bbs);
+ for (basic_block son = first_dom_son (CDI_DOMINATORS, bb); son;
+ son = next_dom_son (CDI_DOMINATORS, son))
+ if (!bitmap_bit_p (visited_bbs, son->index))
+ worklist.safe_push (son);
+ }
+
+ for (unsigned i = 0; i < all_candidates.length (); i++)
+ {
+ convert_if_conditions_to_switch (all_candidates[i]);
+ delete all_candidates[i];
+ }
+
+ /* For now, just wipe the dominator information. */
+ free_dominance_info (CDI_DOMINATORS);
+
+ if (!all_candidates.is_empty ())
+ mark_virtual_operands_for_renaming (fun);
+
+ return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_if_to_switch (gcc::context *ctxt)
+{
+ return new pass_if_to_switch (ctxt);
+}
diff --git a/gcc/opts.c b/gcc/opts.c
index 3bda59afced..03baf758283 100644
--- a/gcc/opts.c
+++ b/gcc/opts.c
@@ -510,6 +510,7 @@ static const struct default_options default_options_table[] =
{ OPT_LEVELS_2_PLUS, OPT_fvect_cost_model_, NULL, VECT_COST_MODEL_CHEAP },
{ OPT_LEVELS_2_PLUS, OPT_finline_functions, NULL, 1 },
{ OPT_LEVELS_2_PLUS, OPT_ftree_loop_distribute_patterns, NULL, 1 },
+ { OPT_LEVELS_2_PLUS, OPT_fconvert_if_to_switch, NULL, 1 },
/* -O2 and above optimizations, but not -Os or -Og. */
{ OPT_LEVELS_2_PLUS_SPEED_ONLY, OPT_falign_functions, NULL, 1 },
diff --git a/gcc/passes.def b/gcc/passes.def
index f865bdc19ac..10d7eeb091b 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -93,6 +93,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_phiopt, true /* early_p */);
NEXT_PASS (pass_modref);
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);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
new file mode 100644
index 00000000000..bcb8ef2a160
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
@@ -0,0 +1,35 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-1.c:9\\) with 5 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
new file mode 100644
index 00000000000..316e772ec29
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespaceNoRange(int aChar)
+{
+ return aChar == 0x0001 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000E ||
+ aChar == 0x0020;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-2.c:7\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
new file mode 100644
index 00000000000..fd07d909a3c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int IsHTMLWhitespace(int aChar)
+{
+ return aChar == 0x0009 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000D ||
+ aChar == 0x0020 || aChar == 0x0030;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain \\(at .*if-to-switch-3.c:8\\) with 5 conditions \\(3 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
new file mode 100644
index 00000000000..3ae006f6ca2
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
@@ -0,0 +1,36 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc == 1)
+ foo ();
+ else if (argc == 2)
+ {
+ global += 1;
+ }
+ else if (argc == 3)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 4)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 1)
+ {
+ global = 2;
+ }
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
new file mode 100644
index 00000000000..acb8b4b1211
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int crud (unsigned char c)
+{
+ return (((((((((((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 "Condition chain \\(at .*if-to-switch-5.c:9\\) with 8 conditions \\(5 BBs\\) transformed into a switch statement." "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
new file mode 100644
index 00000000000..7af323ae251
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
@@ -0,0 +1,42 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int foo ();
+
+int main(int argc, char **argv)
+{
+ if (argc >= 1 && argc <= 10)
+ foo ();
+ else if (argc == 12)
+ {
+ global += 1;
+ }
+ else if (argc == 13)
+ {
+ foo ();
+ foo ();
+ }
+ else if (argc == 14)
+ {
+ foo ();
+ }
+ /* This will be removed with EVRP. */
+ else if (argc == 5)
+ {
+ global = 2;
+ }
+ /* This will be removed with EVRP. */
+ else if (argc >= 7 && argc <= 9)
+ {
+ global = 2;
+ }
+
+ else
+ global -= 123;
+
+ global -= 12;
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
new file mode 100644
index 00000000000..1a919bf025a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+
+int foo(int a)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (a == 2)
+ {
+ global += 123;
+ x = 1;
+ }
+ else if (a == 3)
+ x = 2;
+ else if (a == 10)
+ x = 3;
+ }
+
+ return x;
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain " "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
new file mode 100644
index 00000000000..a5f1a1eae18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
@@ -0,0 +1,27 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+int global;
+int global1;
+int global2;
+int global3;
+
+int foo(int a, int b)
+{
+ int x = 0;
+ for (unsigned i = 0; i < a; i++)
+ {
+ if (b == 1)
+ global += 2;
+ else if (a == 2)
+ global = 123;
+ else if (a == 3)
+ global1 = 1234;
+ else if (a == 10)
+ global2 = 12345;
+ else if (a == 1)
+ global2 = 123456;
+ }
+}
+
+/* { dg-final { scan-tree-dump-not "Condition chain" "iftoswitch" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
index 944362ad076..8e53620a4df 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
@@ -1,6 +1,6 @@
/* { dg-do run { target { ! "m68k*-*-* mmix*-*-* bfin*-*-* v850*-*-* moxie*-*-* cris*-*-* m32c*-*-* fr30*-*-* mcore*-*-* powerpc*-*-* xtensa*-*-*"} } } */
-/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
+/* { dg-options "-O2 -fno-inline -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-convert-if-to-switch" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 08c21c04009..ee87718f3e4 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -292,6 +292,7 @@ DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking")
DEFTIMEVAR (TV_VAR_TRACKING_DATAFLOW , "var-tracking dataflow")
DEFTIMEVAR (TV_VAR_TRACKING_EMIT , "var-tracking emit")
DEFTIMEVAR (TV_TREE_IFCOMBINE , "tree if-combine")
+DEFTIMEVAR (TV_TREE_IF_TO_SWITCH , "if to switch conversion")
DEFTIMEVAR (TV_TREE_UNINIT , "uninit var analysis")
DEFTIMEVAR (TV_PLUGIN_INIT , "plugin initialization")
DEFTIMEVAR (TV_PLUGIN_RUN , "plugin execution")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 62e5b696cab..f8adb902345 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -374,6 +374,7 @@ extern gimple_opt_pass *make_pass_empty_loop (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_graphite_transforms (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_if_conversion (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_if_to_switch (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_loop_distribution (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_vectorize (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_simduid_cleanup (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 7515e952eb3..1e25087a21d 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -48,8 +48,8 @@ class cluster
{
public:
/* Constructor. */
- cluster (tree case_label_expr, basic_block case_bb, profile_probability prob,
- profile_probability subtree_prob);
+ inline cluster (tree case_label_expr, basic_block case_bb,
+ profile_probability prob, profile_probability subtree_prob);
/* Destructor. */
virtual ~cluster ()
@@ -121,8 +121,8 @@ class simple_cluster: public cluster
{
public:
/* Constructor. */
- simple_cluster (tree low, tree high, tree case_label_expr,
- basic_block case_bb, profile_probability prob);
+ inline simple_cluster (tree low, tree high, tree case_label_expr,
+ basic_block case_bb, profile_probability prob);
/* Destructor. */
~simple_cluster ()
@@ -146,6 +146,11 @@ public:
return m_high;
}
+ void set_high (tree high)
+ {
+ m_high = high;
+ }
+
void
debug ()
{
@@ -271,7 +276,7 @@ public:
static inline unsigned int case_values_threshold (void);
/* Return whether jump table expansion is allowed. */
- static bool is_enabled (void);
+ static inline bool is_enabled (void);
};
/* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2020-10-12 13:04 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-09 12:41 [gcc(refs/users/marxin/heads/if-to-switch-v4)] Add if-chain to switch conversion pass Martin Liska
-- strict thread matches above, loose matches on Subject: below --
2020-10-12 13:04 Martin Liska
2020-10-06 13:49 Martin Liska
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).