tree-switch-conversion.h

Go to the documentation of this file.

/* Tree switch conversion for GNU compiler.
   Copyright (C) 2017-2024 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 TREE_SWITCH_CONVERSION_H
#define TREE_SWITCH_CONVERSION_H
 
namespace tree_switch_conversion {
 
/* Type of cluster.  */
 
enum cluster_type
{
  SIMPLE_CASE,
  JUMP_TABLE,
  BIT_TEST
};
 
#define PRINT_CASE(f,c) print_generic_expr (f, c)
 
/* Abstract base class for representing a cluster of cases.
 
   Here is the inheritance hierarachy, and the enum_cluster_type
   values for the concrete subclasses:
 
   cluster
   |-simple_cluster (SIMPLE_CASE)
   `-group_cluster
     |-jump_table_cluster (JUMP_TABLE)
     `-bit_test_cluster   (BIT_TEST).  */
 
class cluster
{
public:
  /* Constructor.  */
  inline cluster (tree case_label_expr, basic_block case_bb,
                  profile_probability prob, profile_probability subtree_prob);
 
  /* Destructor.  */
  virtual ~cluster ()
  {}
 
  /* Return type.  */
  virtual cluster_type get_type () = 0;
 
  /* Get low value covered by a cluster.  */
  virtual tree get_low () = 0;
 
  /* Get high value covered by a cluster.  */
  virtual tree get_high () = 0;
 
  /* Debug content of a cluster.  */
  virtual void debug () = 0;
 
  /* Dump content of a cluster.  */
  virtual void dump (FILE *f, bool details = false) = 0;
 
  /* Emit GIMPLE code to handle the cluster.  */
  virtual void emit (tree, tree, tree, basic_block, location_t) = 0;
 
  /* Return true if a cluster handles only a single case value and the
     value is not a range.  */
  virtual bool is_single_value_p ()
  {
    return false;
  }
 
  /* Return range of a cluster.  If value would overflow in type of LOW,
     then return 0.  */
  static unsigned HOST_WIDE_INT get_range (tree low, tree high)
  {
    wide_int w = wi::to_wide (high) - wi::to_wide (low);
    if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w))
      return 0;
    return w.to_uhwi () + 1;
  }
 
  /* Case label.  */
  tree m_case_label_expr;
 
  /* Basic block of the case.  */
  basic_block m_case_bb;
 
  /* Probability of taking this cluster.  */
  profile_probability m_prob;
 
  /* Probability of reaching subtree rooted at this node.  */
  profile_probability m_subtree_prob;
 
  /* Probability of default case when reaching the node.
     It is used by bit-test right now.  */
  profile_probability m_default_prob;
 
protected:
  /* Default constructor.  */
  cluster () {}
};
 
cluster::cluster (tree case_label_expr, basic_block case_bb,
                  profile_probability prob, profile_probability subtree_prob):
  m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
  m_subtree_prob (subtree_prob),
  m_default_prob (profile_probability::uninitialized ())
{
}
 
/* Subclass of cluster representing a simple contiguous range
   from [low..high].  */
 
class simple_cluster: public cluster
{
public:
  /* Constructor.  */
  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 ()
  {}
 
  cluster_type
  get_type () final override
  {
    return SIMPLE_CASE;
  }
 
  tree
  get_low () final override
  {
    return m_low;
  }
 
  tree
  get_high () final override
  {
    return m_high;
  }
 
  void set_high (tree high)
  {
    m_high = high;
  }
 
  void
  debug () final override
  {
    dump (stderr);
  }
 
  void
  dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) final override
  {
    PRINT_CASE (f, get_low ());
    if (get_low () != get_high ())
      {
        fprintf (f, "-");
        PRINT_CASE (f, get_high ());
      }
    fprintf (f, " ");
  }
 
  void emit (tree, tree, tree, basic_block, location_t) final override
  {
    gcc_unreachable ();
  }
 
  bool is_single_value_p () final override
  {
    return tree_int_cst_equal (get_low (), get_high ());
  }
 
  /* Return number of comparisons needed for the case.  */
  unsigned
  get_comparison_count ()
  {
    return m_range_p ? 2 : 1;
  }
 
  /* Low value of the case.  */
  tree m_low;
 
  /* High value of the case.  */
  tree m_high;
 
  /* 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,
                                bool has_forward_bb):
  cluster (case_label_expr, case_bb, prob, prob),
  m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
{
  m_range_p = m_high != NULL;
  if (m_high == NULL)
    m_high = m_low;
}
 
/* Abstract subclass of jump table and bit test cluster,
   handling a collection of simple_cluster instances.  */
 
class group_cluster: public cluster
{
public:
  /* Constructor.  */
  group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
 
  /* Destructor.  */
  ~group_cluster ();
 
  tree
  get_low () final override
  {
    return m_cases[0]->get_low ();
  }
 
  tree
  get_high () final override
  {
    return m_cases[m_cases.length () - 1]->get_high ();
  }
 
  void
  debug () final override
  {
    dump (stderr);
  }
 
  void dump (FILE *f, bool details = false) final override;
 
  /* List of simple clusters handled by the group.  */
  vec<simple_cluster *> m_cases;
};
 
/* Concrete subclass of group_cluster representing a collection
   of cases to be implemented as a jump table.
   The "emit" vfunc generates a nested switch statement which
   is later lowered to a jump table.  */
 
class jump_table_cluster: public group_cluster
{
public:
  /* Constructor.  */
  jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
  : group_cluster (clusters, start, end)
  {}
 
  cluster_type
  get_type () final override
  {
    return JUMP_TABLE;
  }
 
  void emit (tree index_expr, tree index_type,
             tree default_label_expr, basic_block default_bb, location_t loc)
    final override;
 
  /* Find jump tables of given CLUSTERS, where all members of the vector
     are of type simple_cluster.  New clusters are returned.  */
  static vec<cluster *> find_jump_tables (vec<cluster *> &clusters);
 
  /* Return true when cluster starting at START and ending at END (inclusive)
     can build a jump-table.  COMPARISON_COUNT is number of comparison
     operations needed if the clusters are expanded as decision tree.
     MAX_RATIO tells about the maximum code growth (in percent).  */
  static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
                              unsigned end, unsigned HOST_WIDE_INT max_ratio,
                              unsigned HOST_WIDE_INT comparison_count);
 
  /* Return true if cluster starting at START and ending at END (inclusive)
     is profitable transformation.  */
  static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
                             unsigned end);
 
  /* Return the smallest number of different values for which it is best
     to use a jump-table instead of a tree of conditional branches.  */
  static inline unsigned int case_values_threshold (void);
 
  /* Return whether jump table expansion is allowed.  */
  static inline bool is_enabled (void);
};
 
/* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
comparisons.  "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
where CST and MINVAL are integer constants.  This is better than a series
of compare-and-branch insns in some cases,  e.g. we can implement:
 
        if ((x==4) || (x==6) || (x==9) || (x==11))
 
as a single bit test:
 
        if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
 
This transformation is only applied if the number of case targets is small,
if CST constains at least 3 bits, and "1 << x" is cheap.  The bit tests are
performed in "word_mode".
 
The following example shows the code the transformation generates:
 
        int bar(int x)
        {
                switch (x)
                {
                case '0':  case '1':  case '2':  case '3':  case '4':
                case '5':  case '6':  case '7':  case '8':  case '9':
                case 'A':  case 'B':  case 'C':  case 'D':  case 'E':
                case 'F':
                        return 1;
                }
                return 0;
        }
 
==>
 
        bar (int x)
        {
                tmp1 = x - 48;
                if (tmp1 > (70 - 48)) goto L2;
                tmp2 = 1 << tmp1;
                tmp3 = 0b11111100000001111111111;
                if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
        L1:
                return 1;
        L2:
                return 0;
        }
 
TODO: There are still some improvements to this transformation that could
be implemented:
 
* A narrower mode than word_mode could be used if that is cheaper, e.g.
  for x86_64 where a narrower-mode shift may result in smaller code.
 
* The compounded constant could be shifted rather than the one.  The
  test would be either on the sign bit or on the least significant bit,
  depending on the direction of the shift.  On some machines, the test
  for the branch would be free if the bit to test is already set by the
  shift operation.
 
This transformation was contributed by Roger Sayle, see this e-mail:
   http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
*/
 
class bit_test_cluster: public group_cluster
{
public:
  /* Constructor.  */
  bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
                    bool handles_entire_switch)
  :group_cluster (clusters, start, end),
  m_handles_entire_switch (handles_entire_switch)
  {}
 
  cluster_type
  get_type () final override
  {
    return BIT_TEST;
  }
 
/*  Expand a switch statement by a short sequence of bit-wise
    comparisons.  "switch(x)" is effectively converted into
    "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
    integer constants.
 
    INDEX_EXPR is the value being switched on.
 
    MINVAL is the lowest case value of in the case nodes,
    and RANGE is highest value minus MINVAL.  MINVAL and RANGE
    are not guaranteed to be of the same type as INDEX_EXPR
    (the gimplifier doesn't change the type of case label values,
    and MINVAL and RANGE are derived from those values).
    MAXVAL is MINVAL + RANGE.
 
    There *MUST* be max_case_bit_tests or less unique case
    node targets.  */
  void emit (tree index_expr, tree index_type,
             tree default_label_expr, basic_block default_bb, location_t loc)
     final override;
 
  /* Find bit tests of given CLUSTERS, where all members of the vector are of
     type simple_cluster.  Use a fast algorithm that might not find the optimal
     solution (minimal number of clusters on the output).  New clusters are
     returned.
 
     You should call find_bit_tests () instead of calling this function
     directly.  */
  static vec<cluster *> find_bit_tests_fast (vec<cluster *> &clusters);
 
  /* Find bit tests of given CLUSTERS, where all members of the vector
     are of type simple_cluster.  Use a slow (quadratic) algorithm that always
     finds the optimal solution (minimal number of clusters on the output).  New
     clusters are returned.
 
     You should call find_bit_tests () instead of calling this function
     directly.  */
  static vec<cluster *> find_bit_tests_slow (vec<cluster *> &clusters);
 
  /* Find bit tests of given CLUSTERS, where all members of the vector
     are of type simple_cluster.  New clusters are returned.  */
  static vec<cluster *> find_bit_tests (vec<cluster *> &clusters, int max_c);
 
  /* Return true when RANGE of case values with UNIQ labels
     can build a bit test.  */
  static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
 
  /* Return true when cluster starting at START and ending at END (inclusive)
     can build a bit test.  */
  static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
                              unsigned end);
 
  /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
     transformation.  */
  static bool is_beneficial (unsigned count, unsigned uniq);
 
  /* Return true if cluster starting at START and ending at END (inclusive)
     is profitable transformation.  */
  static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
                             unsigned end);
 
/* Split the basic block at the statement pointed to by GSIP, and insert
   a branch to the target basic block of E_TRUE conditional on tree
   expression COND.
 
   It is assumed that there is already an edge from the to-be-split
   basic block to E_TRUE->dest block.  This edge is removed, and the
   profile information on the edge is re-used for the new conditional
   jump.
 
   The CFG is updated.  The dominator tree will not be valid after
   this transformation, but the immediate dominators are updated if
   UPDATE_DOMINATORS is true.
 
   Returns the newly created basic block.  */
  static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
                                                    tree cond,
                                                    basic_block case_bb,
                                                    profile_probability prob,
                                                    location_t);
 
  /* Return whether bit test expansion is allowed.  */
  static inline bool is_enabled (void)
  {
    return flag_bit_tests;
  }
 
  /* True when the jump table handles an entire switch statement.  */
  bool m_handles_entire_switch;
 
  /* Maximum number of different basic blocks that can be handled by
     a bit test.  */
  static const int m_max_case_bit_tests = 3;
};
 
/* Helper struct to find minimal clusters.  */
 
class min_cluster_item
{
public:
  /* Constructor.  */
  min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
    m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
  {}
 
  /* Count of clusters.  */
  unsigned m_count;
 
  /* Index where is cluster boundary.  */
  unsigned m_start;
 
  /* Total number of cases that will not be in a jump table.  */
  unsigned m_non_jt_cases;
};
 
/* Helper struct to represent switch decision tree.  */
 
class case_tree_node
{
public:
  /* Empty Constructor.  */
  case_tree_node ();
 
  /* Return true when it has a child.  */
  bool has_child ()
  {
    return m_left != NULL || m_right != NULL;
  }
 
  /* Left son in binary tree.  */
  case_tree_node *m_left;
 
  /* Right son in binary tree; also node chain.  */
  case_tree_node *m_right;
 
  /* Parent of node in binary tree.  */
  case_tree_node *m_parent;
 
  /* Cluster represented by this tree node.  */
  cluster *m_c;
};
 
inline
case_tree_node::case_tree_node ():
  m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
{
}
 
unsigned int
jump_table_cluster::case_values_threshold (void)
{
  unsigned int threshold = param_case_values_threshold;
 
  if (threshold == 0)
    threshold = targetm.case_values_threshold ();
 
  return threshold;
}
 
/* Return whether jump table expansion is allowed.  */
bool jump_table_cluster::is_enabled (void)
{
  /* If neither casesi or tablejump is available, or flag_jump_tables
     over-ruled us, we really have no choice.  */
  if (!targetm.have_casesi () && !targetm.have_tablejump ())
    return false;
  if (!flag_jump_tables)
    return false;
#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
  if (flag_pic)
    return false;
#endif
 
  return true;
}
 
/* A case_bit_test represents a set of case nodes that may be
   selected from using a bit-wise comparison.  HI and LO hold
   the integer to be tested against, TARGET_EDGE contains the
   edge to the basic block to jump to upon success and BITS
   counts the number of case nodes handled by this test,
   typically the number of bits set in HI:LO.  The LABEL field
   is used to quickly identify all cases in this set without
   looking at label_to_block for every case label.  */
 
class case_bit_test
{
public:
  wide_int mask;
  basic_block target_bb;
  tree label;
  int bits;
  profile_probability prob;
 
  /* Comparison function for qsort to order bit tests by decreasing
     probability of execution.  */
  static int cmp (const void *p1, const void *p2);
};
 
class switch_decision_tree
{
public:
  /* Constructor.  */
  switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
    m_case_bbs (), m_case_node_pool ("struct case_node pool"),
    m_case_list (NULL)
  {
  }
 
  /* Analyze switch statement and return true when the statement is expanded
     as decision tree.  */
  bool analyze_switch_statement ();
 
  /* Attempt to expand CLUSTERS as a decision tree.  Return true when
     expanded.  */
  bool try_switch_expansion (vec<cluster *> &clusters);
  /* Compute the number of case labels that correspond to each outgoing edge of
     switch statement.  Record this information in the aux field of the edge.
     Returns approx max number of cases per edge.
     */
  int compute_cases_per_edge ();
 
  /* Before switch transformation, record all SSA_NAMEs defined in switch BB
     and used in a label basic block.  */
  void record_phi_operand_mapping ();
 
  /* Append new operands to PHI statements that were introduced due to
     addition of new edges to case labels.  */
  void fix_phi_operands_for_edges ();
 
  /* Generate a decision tree, switching on INDEX_EXPR and jumping to
     one of the labels in CASE_LIST or to the DEFAULT_LABEL.
 
     We generate a binary decision tree to select the appropriate target
     code.  */
  void emit (basic_block bb, tree index_expr,
             profile_probability default_prob, tree index_type);
 
  /* Emit step-by-step code to select a case for the value of INDEX.
     The thus generated decision tree follows the form of the
     case-node binary tree NODE, whose nodes represent test conditions.
     DEFAULT_PROB is probability of cases leading to default BB.
     INDEX_TYPE is the type of the index of the switch.  */
  basic_block emit_case_nodes (basic_block bb, tree index,
                               case_tree_node *node,
                               profile_probability default_prob,
                               tree index_type, location_t);
 
  /* Take an ordered list of case nodes
     and transform them into a near optimal binary tree,
     on the assumption that any target code selection value is as
     likely as any other.
 
     The transformation is performed by splitting the ordered
     list into two equal sections plus a pivot.  The parts are
     then attached to the pivot as left and right branches.  Each
     branch is then transformed recursively.  */
  static void balance_case_nodes (case_tree_node **head,
                                  case_tree_node *parent);
 
  /* Dump ROOT, a list or tree of case nodes, to file F.  */
  static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
                               int indent_level);
 
  /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
  static void emit_jump (basic_block bb, basic_block case_bb);
 
  /* Generate code to compare OP0 with OP1 so that the condition codes are
     set and to jump to LABEL_BB if the condition is true.
     COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
     PROB is the probability of jumping to LABEL_BB.  */
  static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
                                              tree op1, tree_code comparison,
                                              basic_block label_bb,
                                              profile_probability prob,
                                              location_t);
 
  /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
     PROB is the probability of jumping to LABEL_BB.  */
  static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
                                       basic_block label_bb,
                                       profile_probability prob,
                                       location_t);
 
  /* Reset the aux field of all outgoing edges of switch basic block.  */
  static inline void reset_out_edges_aux (gswitch *swtch);
 
  /* Switch statement.  */
  gswitch *m_switch;
 
  /* Map of PHI nodes that have to be fixed after expansion.  */
  hash_map<tree, tree> m_phi_mapping;
 
  /* List of basic blocks that belong to labels of the switch.  */
  auto_vec<basic_block> m_case_bbs;
 
  /* Basic block with default label.  */
  basic_block m_default_bb;
 
  /* A pool for case nodes.  */
  object_allocator<case_tree_node> m_case_node_pool;
 
  /* Balanced tree of case nodes.  */
  case_tree_node *m_case_list;
};
 
/*
     Switch initialization conversion
 
The following pass changes simple initializations of scalars in a switch
statement into initializations from a static array.  Obviously, the values
must be constant and known at compile time and a default branch must be
provided.  For example, the following code:
 
        int a,b;
 
        switch (argc)
        {
         case 1:
         case 2:
                a_1 = 8;
                b_1 = 6;
                break;
         case 3:
                a_2 = 9;
                b_2 = 5;
                break;
         case 12:
                a_3 = 10;
                b_3 = 4;
                break;
         default:
                a_4 = 16;
                b_4 = 1;
                break;
        }
        a_5 = PHI <a_1, a_2, a_3, a_4>
        b_5 = PHI <b_1, b_2, b_3, b_4>
 
 
is changed into:
 
        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
                                 16, 16, 10};
 
        if (((unsigned) argc) - 1 < 11)
          {
            a_6 = CSWTCH02[argc - 1];
            b_6 = CSWTCH01[argc - 1];
          }
        else
          {
            a_7 = 16;
            b_7 = 1;
          }
        a_5 = PHI <a_6, a_7>
        b_b = PHI <b_6, b_7>
 
There are further constraints.  Specifically, the range of values across all
case labels must not be bigger than param_switch_conversion_branch_ratio
(default eight) times the number of the actual switch branches.
 
This transformation was contributed by Martin Jambor, see this e-mail:
   http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html  */
 
/* The main structure of the pass.  */
class switch_conversion
{
public:
  /* Constructor.  */
  switch_conversion ();
 
  /* Destructor.  */
  ~switch_conversion ();
 
  /* The following function is invoked on every switch statement (the current
     one is given in SWTCH) and runs the individual phases of switch
     conversion on it one after another until one fails or the conversion
     is completed.  On success, NULL is in m_reason, otherwise points
     to a string with the reason why the conversion failed.  */
  void expand (gswitch *swtch);
 
  /* Collection information about SWTCH statement.  */
  void collect (gswitch *swtch);
 
  /* Check that the 'exponential index transform' can be applied.
 
     See the comment at the function definition for more details.  */
  bool is_exp_index_transform_viable (gswitch *swtch);
 
  /* Perform the 'exponential index transform'.
 
     The exponential index transform shrinks the range of case numbers which
     helps switch conversion convert switches it otherwise could not.
 
     See the comment at the function definition for more details.  */
  void exp_index_transform (gswitch *swtch);
 
  /* Checks whether the range given by individual case statements of the switch
     switch statement isn't too big and whether the number of branches actually
     satisfies the size of the new array.  */
  bool check_range ();
 
  /* Checks whether all but the final BB basic blocks are empty.  */
  bool check_all_empty_except_final ();
 
  /* This function checks whether all required values in phi nodes in final_bb
     are constants.  Required values are those that correspond to a basic block
     which is a part of the examined switch statement.  It returns true if the
     phi nodes are OK, otherwise false.  */
  bool check_final_bb ();
 
  /* The following function allocates default_values, target_{in,out}_names and
     constructors arrays.  The last one is also populated with pointers to
     vectors that will become constructors of new arrays.  */
  void create_temp_arrays ();
 
  /* Populate the array of default values in the order of phi nodes.
     DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
     if the range is non-contiguous or the default case has standard
     structure, otherwise it is the first non-default case instead.  */
  void gather_default_values (tree default_case);
 
  /* The following function populates the vectors in the constructors array with
     future contents of the static arrays.  The vectors are populated in the
     order of phi nodes.  */
  void build_constructors ();
 
  /* If all values in the constructor vector are products of a linear function
     a * x + b, then return true.  When true, COEFF_A and COEFF_B and
     coefficients of the linear function.  Note that equal values are special
     case of a linear function with a and b equal to zero.  */
  bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
                                   wide_int *coeff_a, wide_int *coeff_b);
 
  /* Return type which should be used for array elements, either TYPE's
     main variant or, for integral types, some smaller integral type
     that can still hold all the constants.  */
  tree array_value_type (tree type, int num);
 
  /* Create an appropriate array type and declaration and assemble a static
     array variable.  Also create a load statement that initializes
     the variable in question with a value from the static array.  SWTCH is
     the switch statement being converted, NUM is the index to
     arrays of constructors, default values and target SSA names
     for this particular array.  ARR_INDEX_TYPE is the type of the index
     of the new array, PHI is the phi node of the final BB that corresponds
     to the value that will be loaded from the created array.  TIDX
     is an ssa name of a temporary variable holding the index for loads from the
     new array.  */
  void build_one_array (int num, tree arr_index_type,
                        gphi *phi, tree tidx);
 
  /* Builds and initializes static arrays initialized with values gathered from
     the switch statement.  Also creates statements that load values from
     them.  */
  void build_arrays ();
 
  /* Generates and appropriately inserts loads of default values at the position
     given by GSI.  Returns the last inserted statement.  */
  gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
 
  /* Deletes the unused bbs and edges that now contain the switch statement and
     its empty branch bbs.  BBD is the now dead BB containing
     the original switch statement, FINAL is the last BB of the converted
     switch statement (in terms of succession).  */
  void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
 
  /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
     from the basic block loading values from an array and E2F from the basic
     block loading default values.  BBF is the last switch basic block (see the
     bbf description in the comment below).  */
  void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
 
  /* Creates a check whether the switch expression value actually falls into the
     range given by all the cases.  If it does not, the temporaries are loaded
     with default values instead.  */
  void gen_inbound_check ();
 
  /* Switch statement for which switch conversion takes place.  */
  gswitch *m_switch;
 
  /* The expression used to decide the switch branch.  */
  tree m_index_expr;
 
  /* The following integer constants store the minimum and maximum value
     covered by the case labels.  */
  tree m_range_min;
  tree m_range_max;
 
  /* The difference between the above two numbers.  Stored here because it
     is used in all the conversion heuristics, as well as for some of the
     transformation, and it is expensive to re-compute it all the time.  */
  tree m_range_size;
 
  /* Basic block that contains the actual GIMPLE_SWITCH.  */
  basic_block m_switch_bb;
 
  /* Basic block that is the target of the default case.  */
  basic_block m_default_bb;
 
  /* The single successor block of all branches out of the GIMPLE_SWITCH,
     if such a block exists.  Otherwise NULL.  */
  basic_block m_final_bb;
 
  /* The probability of the default edge in the replaced switch.  */
  profile_probability m_default_prob;
 
  /* Number of phi nodes in the final bb (that we'll be replacing).  */
  int m_phi_count;
 
  /* Constructors of new static arrays.  */
  vec<constructor_elt, va_gc> **m_constructors;
 
  /* Array of default values, in the same order as phi nodes.  */
  tree *m_default_values;
 
  /* Array of ssa names that are initialized with a value from a new static
     array.  */
  tree *m_target_inbound_names;
 
  /* Array of ssa names that are initialized with the default value if the
     switch expression is out of range.  */
  tree *m_target_outbound_names;
 
  /* VOP SSA_NAME.  */
  tree m_target_vop;
 
  /* The first load statement that loads a temporary from a new static array.
   */
  gimple *m_arr_ref_first;
 
  /* The last load statement that loads a temporary from a new static array.  */
  gimple *m_arr_ref_last;
 
  /* String reason why the case wasn't a good candidate that is written to the
     dump file, if there is one.  */
  const char *m_reason;
 
  /* True if default case is not used for any value between range_min and
     range_max inclusive.  */
  bool m_contiguous_range;
 
  /* True if default case does not have the required shape for other case
     labels.  */
  bool m_default_case_nonstandard;
 
  /* Number of uniq labels for non-default edges.  */
  unsigned int m_uniq;
 
  /* Count is number of non-default edges.  */
  unsigned int m_count;
 
  /* True if CFG has been changed.  */
  bool m_cfg_altered;
 
  /* True if exponential index transform has been applied.  See the comment at
     the definition of exp_index_transform for details about the
     transformation.  */
  bool m_exp_index_transform_applied;
 
  /* If switch conversion decided exponential index transform is viable, here
     will be stored the type to which index variable has to be converted
     before the logarithm operation which is a part of the transform.  */
  tree m_exp_index_transform_log2_type;
};
 
void
switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
{
  basic_block bb = gimple_bb (swtch);
  edge e;
  edge_iterator ei;
  FOR_EACH_EDGE (e, ei, bb->succs)
    e->aux = (void *) 0;
}
 
/* Release CLUSTERS vector and destruct all dynamically allocated items.  */
 
inline void
release_clusters (vec<cluster *> &clusters)
{
  for (unsigned i = 0; i < clusters.length (); i++)
    delete clusters[i];
  clusters.release ();
}
 
} // tree_switch_conversion namespace
 
#endif // TREE_SWITCH_CONVERSION_H