/* If-elseif-else to switch conversion pass
   Copyright (C) 2020-2021 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 auto_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;
  auto_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 ();
      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 ());
	      delete right;
	      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");
      release_clusters (output);
      return true;
    }
  else
    output.release ();

  output = bit_test_cluster::find_bit_tests (filtered_clusters);
  r = output.length () < filtered_clusters.length ();
  if (r)
    dump_clusters (&output, "BT can be built");

  release_clusters (output);
  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 = new condition_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
	    || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
	    || info->m_ranges[i].low == NULL_TREE
	    || info->m_ranges[i].high == NULL_TREE
	    || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
		!= TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
	  goto exit;

      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)
	  goto exit;

      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);
      return;
    }

exit:
  delete 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_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 **slot = conditions_in_bbs.get (bb);
      if (slot)
	{
	  condition_info *info = *slot;
	  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;

	      /* It is important that the blocks are linked through FALSE_EDGE.
		 For an expression of index != VALUE, true and false edges
		 are flipped.  */
	      if ((*info2)->m_false_edge != e)
		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 () >= 2
	      && 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);
	    }
	  else
	    delete chain;
	}
    }

  for (unsigned i = 0; i < all_candidates.length (); i++)
    {
      convert_if_conditions_to_switch (all_candidates[i]);
      delete all_candidates[i];
    }

  free (rpo);

  for (hash_map<basic_block, condition_info *>::iterator it
       = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
    delete (*it).second;

  if (!all_candidates.is_empty ())
    {
      free_dominance_info (CDI_DOMINATORS);
      return TODO_cleanup_cfg;
    }

  return 0;
}

} // anon namespace

gimple_opt_pass *
make_pass_if_to_switch (gcc::context *ctxt)
{
  return new pass_if_to_switch (ctxt);
}