On 11/20/20 3:37 PM, Richard Biener wrote:
On Fri, Nov 20, 2020 at 9:57 AM Martin Liška <mli...@suse.cz> wrote:
On 11/19/20 3:46 PM, Richard Biener wrote:
OK, so can you send an updated patch?
+ tree pos_one = build_int_cst (type, 1);
+ if (!left->m_has_forward_bb
+ && !right->m_has_forward_bb
+ && 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 ()))
can you please avoid tree arithmetic here and use wide_ints?
if (wi::eq (wi::to_wide (right->get_low) - wi::to_wide
(left->get_high), wi::one (TYPE_PRECISION (type))
?
+ info.record_phi_mapping (info.m_true_edge,
+ &info.m_true_edge_phi_mapping);
+ info.record_phi_mapping (info.m_false_edge,
+ &info.m_false_edge_phi_mapping);
you still have this edge mapping stuff, can't you recover the actual
PHI arguments from the PHIs during code generation? I see you removed
the restriction for all-same values, good.
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ auto_vec<if_chain *> all_candidates;
+ hash_map<basic_block, condition_info> conditions_in_bbs;
+
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, fun)
+ find_conditions (bb, &conditions_in_bbs);
+
if we didn't find any suitable conditions we can early out
+ free_dominance_info (CDI_DOMINATORS);
+
+ if (!all_candidates.is_empty ())
+ mark_virtual_operands_for_renaming (fun);
please do not free dominator info when you did nothing
(all_candidates.is_empty ()).
+ gcond *cond = chain->m_entries[0]->m_cond;
+ expanded_location loc = expand_location (gimple_location (cond));
+ if (dump_file)
+ {
+ fprintf (dump_file, "Condition chain (at %s:%d) with %d BBs "
+ "transformed into a switch statement.\n",
+ loc.file, loc.line,
+ chain->m_entries.length ());
+ }
if you use dump_enabled_p () and dump_printf_loc you can
use 'cond' as location itself.
Otherwise looks OK.
Hello.
I fixed all the notes except the PHI mapping map. It's really not simple
to reconstruct PHI nodes during code-gen. Once a BB is removed in transform
phase,
I would need to investigate which PHIs have "holes" (missing PHI argument).
Moreover, I do the very similar thing in
gcc/tree-switch-conversion.c::record_phi_operand_mapping.
Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
And I run SPEC2006 benchmarks, it has done 413 transformations.
Martin
Thanks,
Richard.
Sure.
Martin
>From 9d36dec1109ff9dc6c3a707f976c952c2cd1ddbb Mon Sep 17 00:00:00 2001
From: Martin Liska <mli...@suse.cz>
Date: Fri, 28 Aug 2020 10:26:13 +0200
Subject: [PATCH] Add if-chain to switch conversion pass.
gcc/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* Makefile.in: Add gimple-if-to-switch.o.
* dbgcnt.def (DEBUG_COUNTER): Add new debug counter.
* passes.def: Include new pass_if_to_switch pass.
* timevar.def (TV_TREE_IF_TO_SWITCH): New timevar.
* tree-pass.h (make_pass_if_to_switch): New.
* tree-ssa-reassoc.c (struct operand_entry): Move to the header.
(dump_range_entry): Move to header file.
(debug_range_entry): Likewise.
(no_side_effect_bb): Make it global.
* tree-switch-conversion.h (simple_cluster::simple_cluster):
Add inline for couple of functions in order to prevent error
about multiple defined symbols.
* gimple-if-to-switch.cc: New file.
* tree-ssa-reassoc.h: New file.
gcc/testsuite/ChangeLog:
PR tree-optimization/14799
PR ipa/88702
* gcc.dg/tree-ssa/pr96480.c: Disable if-to-switch conversion.
* gcc.dg/tree-ssa/reassoc-32.c: Likewise.
* g++.dg/tree-ssa/if-to-switch-1.C: New test.
* gcc.dg/tree-ssa/if-to-switch-1.c: New test.
* gcc.dg/tree-ssa/if-to-switch-2.c: New test.
* gcc.dg/tree-ssa/if-to-switch-3.c: New test.
* gcc.dg/tree-ssa/if-to-switch-4.c: New test.
* gcc.dg/tree-ssa/if-to-switch-5.c: New test.
* gcc.dg/tree-ssa/if-to-switch-6.c: New test.
* gcc.dg/tree-ssa/if-to-switch-7.c: New test.
* gcc.dg/tree-ssa/if-to-switch-8.c: New test.
---
gcc/Makefile.in | 1 +
gcc/dbgcnt.def | 1 +
gcc/gimple-if-to-switch.cc | 566 ++++++++++++++++++
gcc/passes.def | 1 +
.../g++.dg/tree-ssa/if-to-switch-1.C | 25 +
.../gcc.dg/tree-ssa/if-to-switch-1.c | 35 ++
.../gcc.dg/tree-ssa/if-to-switch-2.c | 11 +
.../gcc.dg/tree-ssa/if-to-switch-3.c | 11 +
.../gcc.dg/tree-ssa/if-to-switch-4.c | 36 ++
.../gcc.dg/tree-ssa/if-to-switch-5.c | 12 +
.../gcc.dg/tree-ssa/if-to-switch-6.c | 42 ++
.../gcc.dg/tree-ssa/if-to-switch-7.c | 25 +
.../gcc.dg/tree-ssa/if-to-switch-8.c | 27 +
gcc/testsuite/gcc.dg/tree-ssa/pr96480.c | 2 +-
gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c | 2 +-
gcc/timevar.def | 1 +
gcc/tree-pass.h | 1 +
gcc/tree-ssa-reassoc.c | 27 +-
gcc/tree-ssa-reassoc.h | 48 ++
gcc/tree-switch-conversion.h | 24 +-
20 files changed, 866 insertions(+), 32 deletions(-)
create mode 100644 gcc/gimple-if-to-switch.cc
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/if-to-switch-1.C
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-6.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-7.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/if-to-switch-8.c
create mode 100644 gcc/tree-ssa-reassoc.h
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 778ec09c75d..16be66fefc6 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1364,6 +1364,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/dbgcnt.def b/gcc/dbgcnt.def
index a5b6bb66a6c..c0744b23f65 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_cp_values)
DEBUG_COUNTER (ipa_cp_vr)
diff --git a/gcc/gimple-if-to-switch.cc b/gcc/gimple-if-to-switch.cc
new file mode 100644
index 00000000000..d132064fb9b
--- /dev/null
+++ b/gcc/gimple-if-to-switch.cc
@@ -0,0 +1,566 @@
+/* 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"
+#include "tree-ssa-reassoc.h"
+
+using namespace tree_switch_conversion;
+
+struct condition_info
+{
+ typedef vec<std::pair<gphi *, tree>> mapping_vec;
+
+ condition_info (gcond *cond): m_cond (cond), m_bb (gimple_bb (cond)),
+ m_forwarder_bb (NULL), m_ranges (), m_true_edge (NULL), m_false_edge (NULL),
+ m_true_edge_phi_mapping (), m_false_edge_phi_mapping ()
+ {
+ m_ranges.create (0);
+ }
+
+ /* Recond PHI mapping for an original edge E and save these into
+ vector VEC. */
+ void record_phi_mapping (edge e, mapping_vec *vec);
+
+ gcond *m_cond;
+ basic_block m_bb;
+ basic_block m_forwarder_bb;
+ vec<range_entry> m_ranges;
+ edge m_true_edge;
+ edge m_false_edge;
+ mapping_vec m_true_edge_phi_mapping;
+ mapping_vec m_false_edge_phi_mapping;
+};
+
+/* Recond PHI mapping for an original edge E and save these into vector VEC. */
+
+void
+condition_info::record_phi_mapping (edge e, mapping_vec *vec)
+{
+ 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);
+ vec->safe_push (std::make_pair (phi, arg));
+ }
+ }
+}
+
+/* Master structure for one if to switch conversion candidate. */
+
+struct if_chain
+{
+ /* Default constructor. */
+ if_chain (): m_entries ()
+ {
+ m_entries.create (2);
+ }
+
+ /* Default destructor. */
+ ~if_chain ()
+ {
+ m_entries.release ();
+ }
+
+ /* 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 ();
+
+ /* If chain entries. */
+ vec<condition_info *> m_entries;
+};
+
+/* Compare two case ranges by minimum value. */
+
+static int
+range_cmp (const void *a, const void *b)
+{
+ const range_entry *re1 = *(const range_entry * const *) a;
+ const range_entry *re2 = *(const range_entry * const *) b;
+
+ return tree_int_cst_compare (re1->low, re2->low);
+}
+
+/* Verify that all case ranges do not overlap. */
+
+bool
+if_chain::check_non_overlapping_cases ()
+{
+ auto_vec<range_entry *> all_ranges;
+ for (unsigned i = 0; i < m_entries.length (); i++)
+ for (unsigned j = 0; j < m_entries[i]->m_ranges.length (); j++)
+ all_ranges.safe_push (&m_entries[i]->m_ranges[j]);
+
+ all_ranges.qsort (range_cmp);
+
+ for (unsigned i = 0; i < all_ranges.length () - 1; i++)
+ {
+ range_entry *left = all_ranges[i];
+ range_entry *right = all_ranges[i + 1];
+ if (tree_int_cst_le (left->low, right->low)
+ && tree_int_cst_le (right->low, left->high))
+ 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 ());
+}
+
+/* Dump constructed CLUSTERS with prefix MESSAGE. */
+
+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++)
+ {
+ condition_info *info = m_entries[i];
+ for (unsigned j = 0; j < info->m_ranges.length (); j++)
+ {
+ range_entry *range = &info->m_ranges[j];
+ basic_block bb = info->m_true_edge->dest;
+ bool has_forwarder = !info->m_true_edge_phi_mapping.is_empty ();
+ clusters.safe_push (new simple_cluster (range->low, range->high,
+ NULL_TREE, bb, prob,
+ has_forwarder));
+ }
+ }
+
+ /* 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 ());
+ if (!left->m_has_forward_bb
+ && !right->m_has_forward_bb
+ && left->m_case_bb == right->m_case_bb)
+ {
+ if (wi::eq_p (wi::to_wide (right->get_low ()) - wi::to_wide
+ (left->get_high ()), wi::one (TYPE_PRECISION (type))))
+ {
+ 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;
+}
+
+/* Build case label with MIN and MAX values of a given basic block DEST. */
+
+static tree
+build_case_label (tree index_type, tree min, tree max, basic_block dest)
+{
+ if (min != NULL_TREE && index_type != TREE_TYPE (min))
+ min = fold_convert (index_type, min);
+ if (max != NULL_TREE && index_type != TREE_TYPE (max))
+ max = fold_convert (index_type, max);
+
+ 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;
+ unsigned entries = chain->m_entries.length ();
+ condition_info *first_cond = chain->m_entries[0];
+ condition_info *last_cond = chain->m_entries[entries - 1];
+
+ edge default_edge = last_cond->m_false_edge;
+ basic_block default_bb = default_edge->dest;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
+ tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
+ for (unsigned i = 0; i < entries; i++)
+ {
+ condition_info *info = chain->m_entries[i];
+ basic_block case_bb = info->m_true_edge->dest;
+
+ /* Create a forwarder block if needed. */
+ if (!info->m_true_edge_phi_mapping.is_empty ())
+ {
+ info->m_forwarder_bb = split_edge (info->m_true_edge);
+ case_bb = info->m_forwarder_bb;
+ }
+
+ for (unsigned j = 0; j < info->m_ranges.length (); j++)
+ labels.safe_push (build_case_label (index_type,
+ info->m_ranges[j].low,
+ info->m_ranges[j].high,
+ case_bb));
+ default_bb = info->m_false_edge->dest;
+
+ if (i == 0)
+ {
+ remove_edge (first_cond->m_true_edge);
+ remove_edge (first_cond->m_false_edge);
+ }
+ else
+ delete_basic_block (info->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 (first_cond->m_ranges[0].exp,
+ build_case_label (index_type, 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 (unsigned i = 0; i < chain->m_entries.length (); ++i)
+ {
+ condition_info *info = chain->m_entries[i];
+ for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
+ {
+ std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
+ add_phi_arg (item.first, item.second,
+ single_succ_edge (info->m_forwarder_bb),
+ UNKNOWN_LOCATION);
+ }
+ }
+
+ /* Fill up missing PHI nodes for the default BB. */
+ for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
+ {
+ std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
+ add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
+ }
+}
+
+/* Identify an index variable used in BB in a GIMPLE condition.
+ Save information about the condition into CONDITIONS_IN_BBS. */
+
+static void
+find_conditions (basic_block bb,
+ hash_map<basic_block, condition_info> *conditions_in_bbs)
+{
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+ if (gsi_end_p (gsi))
+ return;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (cond == NULL)
+ return;
+
+ if (!no_side_effect_bb (bb))
+ return;
+
+ tree lhs = gimple_cond_lhs (cond);
+ tree rhs = gimple_cond_rhs (cond);
+ tree_code code = gimple_cond_code (cond);
+
+ condition_info info (cond);
+
+ gassign *def;
+ if (code == NE_EXPR
+ && TREE_CODE (lhs) == SSA_NAME
+ && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
+ && integer_zerop (rhs))
+ {
+ enum tree_code rhs_code = gimple_assign_rhs_code (def);
+ if (rhs_code == BIT_IOR_EXPR)
+ {
+ info.m_ranges.safe_grow (2, true);
+ init_range_entry (&info.m_ranges[0], gimple_assign_rhs1 (def), NULL);
+ init_range_entry (&info.m_ranges[1], gimple_assign_rhs2 (def), NULL);
+ }
+ }
+ else
+ {
+ info.m_ranges.safe_grow (1, true);
+ init_range_entry (&info.m_ranges[0], NULL_TREE, cond);
+ }
+
+ /* All identified ranges must have equal expression and IN_P flag. */
+ if (!info.m_ranges.is_empty ())
+ {
+ edge true_edge, false_edge;
+ tree expr = info.m_ranges[0].exp;
+ bool in_p = info.m_ranges[0].in_p;
+
+ extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
+ info.m_true_edge = in_p ? true_edge : false_edge;
+ info.m_false_edge = in_p ? false_edge : true_edge;
+
+ for (unsigned i = 0; i < info.m_ranges.length (); ++i)
+ if (info.m_ranges[i].exp == NULL_TREE
+ || info.m_ranges[i].low == NULL_TREE
+ || info.m_ranges[i].high == NULL_TREE)
+ return;
+
+ for (unsigned i = 1; i < info.m_ranges.length (); ++i)
+ if (info.m_ranges[i].exp != expr
+ || info.m_ranges[i].in_p != in_p)
+ return;
+
+ info.record_phi_mapping (info.m_true_edge,
+ &info.m_true_edge_phi_mapping);
+ info.record_phi_mapping (info.m_false_edge,
+ &info.m_false_edge_phi_mapping);
+ conditions_in_bbs->put (bb, info);
+ }
+
+}
+
+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 (jump_table_cluster::is_enabled ()
+ || bit_test_cluster::is_enabled ());
+ }
+
+ virtual unsigned int execute (function *);
+
+}; // class pass_if_to_switch
+
+unsigned int
+pass_if_to_switch::execute (function *fun)
+{
+ auto_vec<if_chain *> all_candidates;
+ hash_map<basic_block, condition_info> conditions_in_bbs;
+
+ basic_block bb;
+ FOR_EACH_BB_FN (bb, fun)
+ find_conditions (bb, &conditions_in_bbs);
+
+ if (conditions_in_bbs.is_empty ())
+ return 0;
+
+ int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
+ unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
+
+ auto_bitmap seen_bbs;
+ for (int i = n - 1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
+ if (bitmap_bit_p (seen_bbs, bb->index))
+ continue;
+
+ bitmap_set_bit (seen_bbs, bb->index);
+ condition_info *info = conditions_in_bbs.get (bb);
+ if (info)
+ {
+ if_chain *chain = new if_chain ();
+ chain->m_entries.safe_push (info);
+ /* Try to find a chain starting in this BB. */
+ while (true)
+ {
+ if (!single_pred_p (gimple_bb (info->m_cond)))
+ break;
+ edge e = single_pred_edge (gimple_bb (info->m_cond));
+ condition_info *info2 = conditions_in_bbs.get (e->src);
+ if (!info2 || info->m_ranges[0].exp != info2->m_ranges[0].exp)
+ break;
+
+ chain->m_entries.safe_push (info2);
+ bitmap_set_bit (seen_bbs, e->src->index);
+ info = info2;
+ }
+
+ chain->m_entries.reverse ();
+ if (chain->m_entries.length () >= 3
+ && chain->check_non_overlapping_cases ()
+ && chain->is_beneficial ())
+ {
+ gcond *cond = chain->m_entries[0]->m_cond;
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
+ "Condition chain with %d BBs "
+ "transformed into a switch statement.\n",
+ chain->m_entries.length ());
+ all_candidates.safe_push (chain);
+ }
+ }
+ }
+
+ for (unsigned i = 0; i < all_candidates.length (); i++)
+ {
+ convert_if_conditions_to_switch (all_candidates[i]);
+ delete all_candidates[i];
+ }
+
+ free (rpo);
+
+ if (!all_candidates.is_empty ())
+ {
+ free_dominance_info (CDI_DOMINATORS);
+ 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/passes.def b/gcc/passes.def
index fc56e695b60..21b2e2af0f7 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -94,6 +94,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/g++.dg/tree-ssa/if-to-switch-1.C b/gcc/testsuite/g++.dg/tree-ssa/if-to-switch-1.C
new file mode 100644
index 00000000000..88505e8869f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/if-to-switch-1.C
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch-optimized" } */
+
+void fancy_abort(const char *, int, const char *);
+
+enum machine_mode
+{
+ MODE_FLOAT,
+ MODE_DECIMAL_FLOAT,
+ MODE_COMPLEX_INT,
+ MODE_COMPLEX_FLOAT,
+ MODE_VECTOR_BOOL,
+ MODE_VECTOR_FLOAT
+} extern const mode_class;
+
+void tree_node() {
+ if (mode_class)
+ mode_class == MODE_FLOAT || mode_class == MODE_DECIMAL_FLOAT ||
+ mode_class == MODE_COMPLEX_FLOAT || mode_class == MODE_VECTOR_FLOAT
+ ? fancy_abort("aaa", 2, __FUNCTION__),
+ 0 : 0;
+ int g = 0;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain with 3 BBs transformed into a switch statement." "iftoswitch" } } */
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..92df4e93bfa
--- /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-optimized" } */
+
+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 with 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..36e62ae5be1
--- /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-optimized" } */
+
+int IsHTMLWhitespaceNoRange(int aChar)
+{
+ return aChar == 0x0001 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000E ||
+ aChar == 0x0020;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain with 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..9a4ce160238
--- /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-optimized" } */
+
+int IsHTMLWhitespace(int aChar)
+{
+ return aChar == 0x0009 || aChar == 0x000A ||
+ aChar == 0x000C || aChar == 0x000D ||
+ aChar == 0x0020 || aChar == 0x0030;
+}
+
+/* { dg-final { scan-tree-dump "Condition chain with 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..6a035883457
--- /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-optimized" } */
+
+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..7734a58500b
--- /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-optimized" } */
+
+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 with 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..464b1fbd124
--- /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-optimized" } */
+
+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..4a176f1a613
--- /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-optimized" } */
+
+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..f43ce7daf78
--- /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-optimized" } */
+
+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/pr96480.c b/gcc/testsuite/gcc.dg/tree-ssa/pr96480.c
index f2a91ef9909..cc04721c1df 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr96480.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr96480.c
@@ -1,6 +1,6 @@
/* PR tree-optimization/96480 */
/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-options "-O2 -fdump-tree-optimized -fno-bit-tests" } */
/* { dg-final { scan-tree-dump " = _\[0-9]* <= 3;" "optimized" } } */
int v[4];
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-32.c
index 944362ad076..093e7a57a27 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-bit-tests" } */
/* { dg-additional-options "-mbranch-cost=2" { target branch_cost } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index a3031799700..1cf2300ecda 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -293,6 +293,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 cc4870e9711..450a379bac7 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -379,6 +379,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-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 89adafae32c..e594230436d 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -51,6 +51,7 @@ along with GCC; see the file COPYING3. If not see
#include "builtins.h"
#include "gimplify.h"
#include "case-cfn-macros.h"
+#include "tree-ssa-reassoc.h"
/* This is a simple global reassociation pass. It is, in part, based
on the LLVM pass of the same name (They do some things more/less
@@ -188,15 +189,6 @@ static struct
int pows_created;
} reassociate_stats;
-/* Operator, rank pair. */
-struct operand_entry
-{
- unsigned int rank;
- unsigned int id;
- tree op;
- unsigned int count;
- gimple *stmt_to_insert;
-};
static object_allocator<operand_entry> operand_entry_pool
("operand entry pool");
@@ -226,7 +218,7 @@ static bool reassoc_stmt_dominates_stmt_p (gimple *, gimple *);
/* Wrapper around gsi_remove, which adjusts gimple_uid of debug stmts
possibly added by gsi_remove. */
-bool
+static bool
reassoc_remove_stmt (gimple_stmt_iterator *gsi)
{
gimple *stmt = gsi_stmt (*gsi);
@@ -2408,18 +2400,7 @@ optimize_ops_list (enum tree_code opcode,
For more information see comments above fold_test_range in fold-const.c,
this implementation is for GIMPLE. */
-struct range_entry
-{
- tree exp;
- tree low;
- tree high;
- bool in_p;
- bool strict_overflow_p;
- unsigned int idx, next;
-};
-void dump_range_entry (FILE *file, struct range_entry *r);
-void debug_range_entry (struct range_entry *r);
/* Dump the range entry R to FILE, skipping its expression if SKIP_EXP. */
@@ -2449,7 +2430,7 @@ debug_range_entry (struct range_entry *r)
an SSA_NAME and STMT argument is ignored, otherwise STMT
argument should be a GIMPLE_COND. */
-static void
+void
init_range_entry (struct range_entry *r, tree exp, gimple *stmt)
{
int in_p;
@@ -4286,7 +4267,7 @@ suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
range test optimization, all SSA_NAMEs set in the bb are consumed
in the bb and there are no PHIs. */
-static bool
+bool
no_side_effect_bb (basic_block bb)
{
gimple_stmt_iterator gsi;
diff --git a/gcc/tree-ssa-reassoc.h b/gcc/tree-ssa-reassoc.h
new file mode 100644
index 00000000000..dc7f59f1eca
--- /dev/null
+++ b/gcc/tree-ssa-reassoc.h
@@ -0,0 +1,48 @@
+/* Reassociation for trees.
+ 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/>. */
+
+#ifndef GCC_SSA_REASSOC_H
+#define GCC_SSA_REASSOC_H
+
+/* Operator, rank pair. */
+struct operand_entry
+{
+ unsigned int rank;
+ unsigned int id;
+ tree op;
+ unsigned int count;
+ gimple *stmt_to_insert;
+};
+
+struct range_entry
+{
+ tree exp;
+ tree low;
+ tree high;
+ bool in_p;
+ bool strict_overflow_p;
+ unsigned int idx, next;
+};
+
+void dump_range_entry (FILE *file, struct range_entry *r);
+void debug_range_entry (struct range_entry *r);
+void init_range_entry (struct range_entry *r, tree exp, gimple *stmt);
+bool no_side_effect_bb (basic_block bb);
+
+#endif /* GCC_SSA_REASSOC_H */
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 7515e952eb3..62cfde168c8 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,9 @@ 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,
+ bool has_forward_bb = false);
/* Destructor. */
~simple_cluster ()
@@ -146,6 +147,11 @@ public:
return m_high;
}
+ void set_high (tree high)
+ {
+ m_high = high;
+ }
+
void
debug ()
{
@@ -182,12 +188,16 @@ public:
/* True if case is a range. */
bool m_range_p;
+
+ /* True if the case will use a forwarder BB. */
+ bool m_has_forward_bb;
};
simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
- basic_block case_bb, profile_probability prob):
+ basic_block case_bb, profile_probability prob,
+ bool has_forward_bb):
cluster (case_label_expr, case_bb, prob, prob),
- m_low (low), m_high (high)
+ m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
{
m_range_p = m_high != NULL;
if (m_high == NULL)
@@ -271,7 +281,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
--
2.29.2
