Re: [PATCH v2] Add if-chain to switch conversion pass.

["Martin Liška" <mliska@suse.cz>]

[-- Attachment #1: Type: text/plain, Size: 98 bytes --]

On 11/19/20 3:46 PM, Richard Biener wrote:
> OK, so can you send an updated patch?

Sure.

Martin

[-- Attachment #2: 0001-Add-if-chain-to-switch-conversion-pass.patch --]
[-- Type: text/x-patch, Size: 36604 bytes --]

From 76e8424bd54d15fb3b2a2bdb4179fa8773500381 Mon Sep 17 00:00:00 2001
From: Martin Liska <mliska@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                    | 565 ++++++++++++++++++
 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, 865 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..25ef45175a7
--- /dev/null
+++ b/gcc/gimple-if-to-switch.cc
@@ -0,0 +1,565 @@
+/* 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 ());
+      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 ()))
+	    {
+	      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);
+
+  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;
+	      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 ());
+		}
+	      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);
+  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/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..0f9c8d35ff9
--- /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" } */
+
+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 \\(at .*\\) 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..94a0db649e4
--- /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 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..b114e74ac37
--- /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 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..e157039e75b
--- /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 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..46ea5b627c8
--- /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 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/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