LCOV - code coverage report
Current view: top level - gcc - tree-switch-conversion.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.8 % 1420 1375
Test Date: 2026-11-14 16:39:50 Functions: 95.0 % 60 57
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Lower GIMPLE_SWITCH expressions to something more efficient than
       2              :    a jump table.
       3              :    Copyright (C) 2006-2026 Free Software Foundation, Inc.
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it
       8              : under the terms of the GNU General Public License as published by the
       9              : Free Software Foundation; either version 3, or (at your option) any
      10              : later version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but WITHOUT
      13              : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15              : for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not, write to the Free
      19              : Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
      20              : 02110-1301, USA.  */
      21              : 
      22              : /* This file handles the lowering of GIMPLE_SWITCH to an indexed
      23              :    load, or a series of bit-test-and-branch expressions.  */
      24              : 
      25              : #include "config.h"
      26              : #include "system.h"
      27              : #include "coretypes.h"
      28              : #include "backend.h"
      29              : #include "insn-codes.h"
      30              : #include "rtl.h"
      31              : #include "tree.h"
      32              : #include "gimple.h"
      33              : #include "cfghooks.h"
      34              : #include "tree-pass.h"
      35              : #include "ssa.h"
      36              : #include "optabs-tree.h"
      37              : #include "cgraph.h"
      38              : #include "gimple-pretty-print.h"
      39              : #include "fold-const.h"
      40              : #include "varasm.h"
      41              : #include "stor-layout.h"
      42              : #include "cfganal.h"
      43              : #include "gimplify.h"
      44              : #include "gimple-iterator.h"
      45              : #include "gimplify-me.h"
      46              : #include "gimple-fold.h"
      47              : #include "tree-cfg.h"
      48              : #include "cfgloop.h"
      49              : #include "alloc-pool.h"
      50              : #include "target.h"
      51              : #include "tree-into-ssa.h"
      52              : #include "omp-general.h"
      53              : #include "gimple-range.h"
      54              : #include "tree-cfgcleanup.h"
      55              : #include "hwint.h"
      56              : #include "internal-fn.h"
      57              : #include "diagnostic-core.h"
      58              : 
      59              : /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
      60              :    type in the GIMPLE type system that is language-independent?  */
      61              : #include "langhooks.h"
      62              : 
      63              : #include "tree-switch-conversion.h"
      64              : 
      65              : using namespace tree_switch_conversion;
      66              : 
      67              : /* Does the target have optabs needed to efficiently compute exact base two
      68              :    logarithm of a variable with type TYPE?
      69              : 
      70              :    If yes, returns TYPE.  If no, returns NULL_TREE.  May also return another
      71              :    type.  This indicates that logarithm of the variable can be computed but
      72              :    only after it is converted to this type.
      73              : 
      74              :    Also see gen_log2.  */
      75              : 
      76              : static tree
      77         7232 : can_log2 (tree type, optimization_type opt_type)
      78              : {
      79              :   /* Check if target supports FFS for given type.  */
      80         7232 :   if (direct_internal_fn_supported_p (IFN_FFS, type, opt_type))
      81              :     return type;
      82              : 
      83              :   /* Check if target supports FFS for some type we could convert to.  */
      84         2052 :   int prec = TYPE_PRECISION (type);
      85         2052 :   int i_prec = TYPE_PRECISION (integer_type_node);
      86         2052 :   int li_prec = TYPE_PRECISION (long_integer_type_node);
      87         2052 :   int lli_prec = TYPE_PRECISION (long_long_integer_type_node);
      88         2052 :   tree new_type;
      89         2052 :   if (prec <= i_prec
      90         2052 :       && direct_internal_fn_supported_p (IFN_FFS, integer_type_node, opt_type))
      91         2027 :     new_type = integer_type_node;
      92           25 :   else if (prec <= li_prec
      93           25 :            && direct_internal_fn_supported_p (IFN_FFS, long_integer_type_node,
      94              :                                               opt_type))
      95            0 :     new_type = long_integer_type_node;
      96           25 :   else if (prec <= lli_prec
      97           25 :            && direct_internal_fn_supported_p (IFN_FFS,
      98              :                                               long_long_integer_type_node,
      99              :                                               opt_type))
     100            0 :     new_type = long_long_integer_type_node;
     101              :   else
     102              :     return NULL_TREE;
     103              :   return new_type;
     104              : }
     105              : 
     106              : /* Assume that OP is a power of two.  Build a sequence of gimple statements
     107              :    efficiently computing the base two logarithm of OP using special optabs.
     108              :    Return the ssa name representing the result of the logarithm through RESULT.
     109              : 
     110              :    Before computing the logarithm, OP may have to be converted to another type.
     111              :    This should be specified in TYPE.  Use can_log2 to decide what this type
     112              :    should be.
     113              : 
     114              :    Should only be used if can_log2 doesn't reject the type of OP.  */
     115              : 
     116              : static gimple_seq
     117           21 : gen_log2 (tree op, location_t loc, tree *result, tree type)
     118              : {
     119           21 :   gimple_seq stmts = NULL;
     120              : 
     121           21 :   tree orig_type = TREE_TYPE (op);
     122           21 :   tree tmp1;
     123           21 :   if (type != orig_type)
     124            4 :     tmp1 = gimple_convert (&stmts, loc, type, op);
     125              :   else
     126              :     tmp1 = op;
     127              :   /* Build FFS (op) - 1.  */
     128           21 :   tree tmp2 = gimple_build (&stmts, loc, IFN_FFS, orig_type, tmp1);
     129           21 :   tree tmp3 = gimple_build (&stmts, loc, MINUS_EXPR,
     130              :                             orig_type, tmp2, build_one_cst (orig_type));
     131           21 :   *result = tmp3;
     132           21 :   return stmts;
     133              : }
     134              : 
     135              : /* Build a sequence of gimple statements checking that OP is a power of 2.
     136              :    Return the result as a boolean_type_node ssa name through RESULT.  Assumes
     137              :    that OP's value will be non-negative.  The generated check may give
     138              :    arbitrary answer for negative values.  */
     139              : 
     140              : static gimple_seq
     141           21 : gen_pow2p (tree op, location_t loc, tree *result)
     142              : {
     143           21 :   gimple_seq stmts = NULL;
     144              : 
     145           21 :   tree type = TREE_TYPE (op);
     146           21 :   tree utype = unsigned_type_for (type);
     147              : 
     148              :   /* Build (op ^ (op - 1)) > (op - 1).  */
     149           21 :   tree tmp1;
     150           21 :   if (types_compatible_p (type, utype))
     151              :     tmp1 = op;
     152              :   else
     153           13 :     tmp1 = gimple_convert (&stmts, loc, utype, op);
     154           21 :   tree tmp2 = gimple_build (&stmts, loc, MINUS_EXPR, utype,
     155              :                             tmp1, build_one_cst (utype));
     156           21 :   tree tmp3 = gimple_build (&stmts, loc, BIT_XOR_EXPR, utype, tmp1, tmp2);
     157           21 :   *result = gimple_build (&stmts, loc, GT_EXPR, boolean_type_node, tmp3, tmp2);
     158              : 
     159           21 :   return stmts;
     160              : }
     161              : 
     162              : 
     163              : /* Constructor.  */
     164              : 
     165        28100 : switch_conversion::switch_conversion (): m_final_bb (NULL),
     166        28100 :   m_constructors (NULL), m_default_values (NULL),
     167        28100 :   m_arr_ref_first (NULL), m_arr_ref_last (NULL),
     168        28100 :   m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false),
     169        28100 :   m_exp_index_transform_applied (false)
     170              : {
     171        28100 : }
     172              : 
     173              : /* Collection information about SWTCH statement.  */
     174              : 
     175              : void
     176        28100 : switch_conversion::collect (gswitch *swtch)
     177              : {
     178        28100 :   unsigned int branch_num = gimple_switch_num_labels (swtch);
     179        28100 :   tree min_case, max_case;
     180        28100 :   unsigned int i;
     181        28100 :   edge e, e_default, e_first;
     182        28100 :   edge_iterator ei;
     183              : 
     184        28100 :   m_switch = swtch;
     185              : 
     186              :   /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
     187              :      is a default label which is the first in the vector.
     188              :      Collect the bits we can deduce from the CFG.  */
     189        28100 :   m_index_expr = gimple_switch_index (swtch);
     190        28100 :   m_switch_bb = gimple_bb (swtch);
     191        28100 :   e_default = gimple_switch_default_edge (cfun, swtch);
     192        28100 :   m_default_bb = e_default->dest;
     193        28100 :   m_default_prob = e_default->probability;
     194              : 
     195              :   /* Get upper and lower bounds of case values, and the covered range.  */
     196        28100 :   min_case = gimple_switch_label (swtch, 1);
     197        28100 :   max_case = gimple_switch_label (swtch, branch_num - 1);
     198              : 
     199        28100 :   m_range_min = CASE_LOW (min_case);
     200        28100 :   if (CASE_HIGH (max_case) != NULL_TREE)
     201         1871 :     m_range_max = CASE_HIGH (max_case);
     202              :   else
     203        26229 :     m_range_max = CASE_LOW (max_case);
     204              : 
     205        28100 :   m_contiguous_range = true;
     206        28100 :   tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
     207        96899 :   for (i = 2; i < branch_num; i++)
     208              :     {
     209        84013 :       tree elt = gimple_switch_label (swtch, i);
     210        84014 :       if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
     211              :         {
     212        15214 :           m_contiguous_range = false;
     213        15214 :           break;
     214              :         }
     215        68799 :       last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
     216              :     }
     217              : 
     218        28100 :   if (m_contiguous_range)
     219        12886 :     e_first = gimple_switch_edge (cfun, swtch, 1);
     220              :   else
     221              :     e_first = e_default;
     222              : 
     223              :   /* See if there is one common successor block for all branch
     224              :      targets.  If it exists, record it in FINAL_BB.
     225              :      Start with the destination of the first non-default case
     226              :      if the range is contiguous and default case otherwise as
     227              :      guess or its destination in case it is a forwarder block.  */
     228        28100 :   if (! single_pred_p (e_first->dest))
     229         8926 :     m_final_bb = e_first->dest;
     230        19174 :   else if (single_succ_p (e_first->dest)
     231        17742 :            && ! single_pred_p (single_succ (e_first->dest)))
     232        13355 :     m_final_bb = single_succ (e_first->dest);
     233              :   /* Require that all switch destinations are either that common
     234              :      FINAL_BB or a forwarder to it, except for the default
     235              :      case if contiguous range.  */
     236        28100 :   auto_vec<edge, 10> fw_edges;
     237        28100 :   m_uniq = 0;
     238        28100 :   if (m_final_bb)
     239       112786 :     FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
     240              :       {
     241       100674 :         edge phi_e = nullptr;
     242       100674 :         if (e->dest == m_final_bb)
     243        14999 :           phi_e = e;
     244       186349 :         else if (single_pred_p (e->dest)
     245        82625 :                  && single_succ_p (e->dest)
     246       161242 :                  && single_succ (e->dest) == m_final_bb)
     247        72812 :           phi_e = single_succ_edge (e->dest);
     248       100674 :         if (phi_e)
     249              :           {
     250        87811 :             if (e == e_default)
     251              :               ;
     252        68591 :             else if (phi_e == e || empty_block_p (e->dest))
     253              :               {
     254              :                 /* For empty blocks consider forwarders with equal
     255              :                    PHI arguments in m_final_bb as unique.  */
     256              :                 unsigned i;
     257       170638 :                 for (i = 0; i < fw_edges.length (); ++i)
     258       143616 :                   if (phi_alternatives_equal (m_final_bb, fw_edges[i], phi_e))
     259              :                     break;
     260        54276 :                 if (i == fw_edges.length ())
     261              :                   {
     262              :                     /* But limit the above possibly quadratic search.  */
     263        27022 :                     if (fw_edges.length () < 10)
     264        18518 :                       fw_edges.quick_push (phi_e);
     265        27022 :                     m_uniq++;
     266              :                   }
     267              :               }
     268              :             else
     269        41453 :               m_uniq++;
     270        90505 :             continue;
     271        87811 :           }
     272              : 
     273        12863 :         if (e == e_default && m_contiguous_range)
     274              :           {
     275         2694 :             m_default_case_nonstandard = true;
     276         2694 :             continue;
     277              :           }
     278              : 
     279        10169 :         m_final_bb = NULL;
     280        10169 :         break;
     281              :       }
     282              : 
     283              :   /* When there's not a single common successor block conservatively
     284              :      approximate the number of unique non-default targets.  */
     285        28100 :   if (!m_final_bb)
     286        31976 :     m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
     287              : 
     288        28100 :   m_range_size
     289        28100 :     = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
     290              : 
     291              :   /* Get a count of the number of case labels.  Single-valued case labels
     292              :      simply count as one, but a case range counts double, since it may
     293              :      require two compares if it gets lowered as a branching tree.  */
     294        28100 :   m_count = 0;
     295       188195 :   for (i = 1; i < branch_num; i++)
     296              :     {
     297       160095 :       tree elt = gimple_switch_label (swtch, i);
     298       160095 :       m_count++;
     299       160095 :       if (CASE_HIGH (elt)
     300       160095 :           && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
     301         9321 :         m_count++;
     302              :     }
     303        28100 : }
     304              : 
     305              : /* Check that the "exponential index transform" can be applied to this switch.
     306              : 
     307              :    See comment of the exp_index_transform function for details about this
     308              :    transformation.
     309              : 
     310              :    We want:
     311              :    - This form of the switch is more efficient
     312              :    - Cases are powers of 2
     313              : 
     314              :    Expects that SWTCH has at least one case.  */
     315              : 
     316              : bool
     317         7232 : switch_conversion::is_exp_index_transform_viable (gswitch *swtch)
     318              : {
     319         7232 :   tree index = gimple_switch_index (swtch);
     320         7232 :   tree index_type = TREE_TYPE (index);
     321         7232 :   basic_block swtch_bb = gimple_bb (swtch);
     322         7232 :   unsigned num_labels = gimple_switch_num_labels (swtch);
     323              : 
     324         7232 :   optimization_type opt_type = bb_optimization_type (swtch_bb);
     325         7232 :   m_exp_index_transform_log2_type = can_log2 (index_type, opt_type);
     326         7232 :   if (!m_exp_index_transform_log2_type)
     327              :     return false;
     328              : 
     329              :   /* Check that each case label corresponds only to one value
     330              :      (no case 1..3).  */
     331              :   unsigned i;
     332        59677 :   for (i = 1; i < num_labels; i++)
     333              :     {
     334        52894 :       tree label = gimple_switch_label (swtch, i);
     335        52894 :       if (CASE_HIGH (label))
     336              :         return false;
     337              :     }
     338              : 
     339              :   /* Check that each label is nonnegative and a power of 2.  */
     340         9000 :   for (i = 1; i < num_labels; i++)
     341              :     {
     342         8898 :       tree label = gimple_switch_label (swtch, i);
     343         8898 :       wide_int label_wi = wi::to_wide (CASE_LOW (label));
     344         8898 :       if (!wi::ge_p (label_wi, 0, TYPE_SIGN (index_type)))
     345              :         return false;
     346         8788 :       if (wi::exact_log2 (label_wi) == -1)
     347              :         return false;
     348         8898 :     }
     349              : 
     350          102 :   if (dump_file)
     351           12 :     fprintf (dump_file, "Exponential index transform viable\n");
     352              : 
     353              :   return true;
     354              : }
     355              : 
     356              : /* Perform the "exponential index transform".
     357              : 
     358              :    Assume that cases of SWTCH are powers of 2.  The transformation replaces the
     359              :    cases by their exponents (2^k -> k).  It also inserts a statement that
     360              :    computes the exponent of the original index variable (basically taking the
     361              :    logarithm) and then sets the result as the new index variable.
     362              : 
     363              :    The transformation also inserts a conditional statement checking that the
     364              :    incoming original index variable is a power of 2 with the false edge leading
     365              :    to the default case.
     366              : 
     367              :    The exponential index transform shrinks the range of case numbers which
     368              :    helps switch conversion convert switches it otherwise could not.
     369              : 
     370              :    Consider for example:
     371              : 
     372              :    switch (i)
     373              :      {
     374              :        case (1 << 0): return 0;
     375              :        case (1 << 1): return 1;
     376              :        case (1 << 2): return 2;
     377              :        ...
     378              :        case (1 << 30): return 30;
     379              :        default: return 31;
     380              :      }
     381              : 
     382              :    First, exponential index transform gets applied.  Since each case becomes
     383              :    case x: return x;, the rest of switch conversion is then able to get rid of
     384              :    the switch statement.
     385              : 
     386              :    if (i is power of 2)
     387              :      return log2 (i);
     388              :    else
     389              :      return 31;
     390              : 
     391              :    */
     392              : 
     393              : void
     394           21 : switch_conversion::exp_index_transform (gswitch *swtch)
     395              : {
     396           21 :   if (dump_file)
     397           11 :     fprintf (dump_file, "Applying exponential index transform\n");
     398              : 
     399           21 :   tree index = gimple_switch_index (swtch);
     400           21 :   tree index_type = TREE_TYPE (index);
     401           21 :   basic_block swtch_bb = gimple_bb (swtch);
     402           21 :   unsigned num_labels = gimple_switch_num_labels (swtch);
     403              : 
     404              :   /* Insert a cond stmt that checks if the index variable is a power of 2.  */
     405           21 :   gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
     406           21 :   gsi_prev (&gsi);
     407           21 :   gimple *foo = gsi_stmt (gsi);
     408           21 :   edge new_edge1 = split_block (swtch_bb, foo);
     409              : 
     410           21 :   swtch_bb = new_edge1->dest;
     411           21 :   basic_block cond_bb = new_edge1->src;
     412           21 :   new_edge1->flags |= EDGE_TRUE_VALUE;
     413           21 :   new_edge1->flags &= ~EDGE_FALLTHRU;
     414           21 :   new_edge1->probability = profile_probability::even ();
     415              : 
     416           21 :   basic_block default_bb = gimple_switch_default_bb (cfun, swtch);
     417           21 :   edge new_edge2 = make_edge (cond_bb, default_bb, EDGE_FALSE_VALUE);
     418           21 :   new_edge2->probability = profile_probability::even ();
     419              : 
     420           21 :   tree tmp;
     421           21 :   gimple_seq stmts = gen_pow2p (index, UNKNOWN_LOCATION, &tmp);
     422           21 :   gsi = gsi_last_bb (cond_bb);
     423           21 :   gsi_insert_seq_after (&gsi, stmts, GSI_LAST_NEW_STMT);
     424           21 :   gcond *stmt_cond = gimple_build_cond (NE_EXPR, tmp, boolean_false_node,
     425              :                                         NULL, NULL);
     426           21 :   gsi_insert_after (&gsi, stmt_cond, GSI_NEW_STMT);
     427              : 
     428              :   /* We just added an edge going to default bb so fix PHI nodes in that bb:
     429              :      For each PHI add new PHI arg.  It will be the same arg as when coming to
     430              :      the default bb from the switch bb.  */
     431           21 :   edge default_edge = find_edge (swtch_bb, default_bb);
     432           21 :   for (gphi_iterator gsi = gsi_start_phis (default_bb);
     433           33 :        !gsi_end_p (gsi); gsi_next (&gsi))
     434              :     {
     435           12 :       gphi *phi = gsi.phi ();
     436           12 :       tree arg = PHI_ARG_DEF_FROM_EDGE (phi, default_edge);
     437           12 :       location_t loc = gimple_phi_arg_location_from_edge (phi, default_edge);
     438           12 :       add_phi_arg (phi, arg, new_edge2, loc);
     439              :     }
     440              : 
     441              :   /* Insert a sequence of stmts that takes the log of the index variable.  */
     442           21 :   stmts = gen_log2 (index, UNKNOWN_LOCATION, &tmp,
     443              :                     m_exp_index_transform_log2_type);
     444           21 :   gsi = gsi_after_labels (swtch_bb);
     445           21 :   gsi_insert_seq_before (&gsi, stmts, GSI_SAME_STMT);
     446              : 
     447              :   /* Use the result of the logarithm as the new index variable.  */
     448           21 :   gimple_switch_set_index (swtch, tmp);
     449           21 :   update_stmt (swtch);
     450              : 
     451              :   /* Replace each case number with its logarithm.  */
     452           21 :   unsigned i;
     453          155 :   for (i = 1; i < num_labels; i++)
     454              :     {
     455          113 :       tree label = gimple_switch_label (swtch, i);
     456          226 :       CASE_LOW (label) = build_int_cst (index_type,
     457          113 :                                         tree_log2 (CASE_LOW (label)));
     458              :     }
     459              : 
     460              :   /* Fix the dominator tree, if it is available.  */
     461           21 :   if (dom_info_available_p (CDI_DOMINATORS))
     462              :     {
     463              :       /* Analysis of how dominators should look after we add the edge E going
     464              :          from the cond block to the default block.
     465              : 
     466              :          1 For the blocks between the switch block and the final block
     467              :          (excluding the final block itself):  They had the switch block as
     468              :          their immediate dominator.  That shouldn't change.
     469              : 
     470              :          2 The final block may now have the switch block or the cond block as
     471              :          its immediate dominator.  There's no easy way of knowing (consider
     472              :          two cases where in both m_default_case_nonstandard = true, in one a
     473              :          path through default intersects the final block and in one all paths
     474              :          through default avoid the final block but intersect a successor of the
     475              :          final block).
     476              : 
     477              :          3 Other blocks that had the switch block as their immediate dominator
     478              :          should now have the cond block as their immediate dominator.
     479              : 
     480              :          4 Immediate dominators of the rest of the blocks shouldn't change.
     481              : 
     482              :          Reasoning for 3 and 4:
     483              : 
     484              :          We'll only consider blocks that do not fall into 1 or 2.
     485              : 
     486              :          Consider a block X whose original imm dom was the switch block.  All
     487              :          paths to X must also intersect the cond block since it's the only
     488              :          pred of the switch block.  The final block doesn't dominate X so at
     489              :          least one path P must lead through the default block.  Let P' be P but
     490              :          instead of going through the switch block, take E.  The switch block
     491              :          doesn't dominate X so its imm dom must now be the cond block.
     492              : 
     493              :          Consider a block X whose original imm dom was Y != the switch block.
     494              :          We only added an edge so all original paths to X are still present.
     495              :          So X gained no new dominators.  Observe that Y still dominates X.
     496              :          There would have to be a path that avoids Y otherwise.  But any block
     497              :          we can avoid now except for the switch block we were able to avoid
     498              :          before adding E.  */
     499              : 
     500           21 :       redirect_immediate_dominators (CDI_DOMINATORS, swtch_bb, cond_bb);
     501              : 
     502           21 :       edge e;
     503           21 :       edge_iterator ei;
     504          155 :       FOR_EACH_EDGE (e, ei, swtch_bb->succs)
     505              :         {
     506          134 :           basic_block bb = e->dest;
     507          134 :           if (bb == m_final_bb || bb == default_bb)
     508           30 :             continue;
     509          104 :           set_immediate_dominator (CDI_DOMINATORS, bb, swtch_bb);
     510              :         }
     511              : 
     512           21 :       vec<basic_block> v;
     513           21 :       v.create (1);
     514           21 :       v.quick_push (m_final_bb);
     515           21 :       iterate_fix_dominators (CDI_DOMINATORS, v, true);
     516              :     }
     517              : 
     518              :   /* Update information about the switch statement.  */
     519           21 :   tree first_label = gimple_switch_label (swtch, 1);
     520           21 :   tree last_label = gimple_switch_label (swtch, num_labels - 1);
     521              : 
     522           21 :   m_range_min = CASE_LOW (first_label);
     523           21 :   m_range_max = CASE_LOW (last_label);
     524           21 :   m_index_expr = gimple_switch_index (swtch);
     525           21 :   m_switch_bb = swtch_bb;
     526              : 
     527           21 :   m_range_size = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
     528              : 
     529           21 :   m_cfg_altered = true;
     530              : 
     531           21 :   m_contiguous_range = true;
     532           21 :   wide_int last_wi = wi::to_wide (CASE_LOW (first_label));
     533          113 :   for (i = 2; i < num_labels; i++)
     534              :     {
     535           92 :       tree label = gimple_switch_label (swtch, i);
     536           92 :       wide_int label_wi = wi::to_wide (CASE_LOW (label));
     537           92 :       m_contiguous_range &= wi::eq_p (wi::add (last_wi, 1), label_wi);
     538           92 :       last_wi = label_wi;
     539           92 :     }
     540              : 
     541           21 :   m_exp_index_transform_applied = true;
     542           21 : }
     543              : 
     544              : /* Checks whether the range given by individual case statements of the switch
     545              :    switch statement isn't too big and whether the number of branches actually
     546              :    satisfies the size of the new array.  */
     547              : 
     548              : bool
     549         7130 : switch_conversion::check_range ()
     550              : {
     551         7130 :   gcc_assert (m_range_size);
     552         7130 :   if (!tree_fits_uhwi_p (m_range_size))
     553              :     {
     554           18 :       m_reason = "index range way too large or otherwise unusable";
     555           18 :       return false;
     556              :     }
     557              : 
     558         7112 :   if (tree_to_uhwi (m_range_size)
     559         7112 :       > ((unsigned) m_count * param_switch_conversion_branch_ratio))
     560              :     {
     561          436 :       m_reason = "the maximum range-branch ratio exceeded";
     562          436 :       return false;
     563              :     }
     564              : 
     565              :   return true;
     566              : }
     567              : 
     568              : /* Checks whether all but the final BB basic blocks are empty.  */
     569              : 
     570              : bool
     571         6778 : switch_conversion::check_all_empty_except_final ()
     572              : {
     573         6778 :   edge e, e_default = find_edge (m_switch_bb, m_default_bb);
     574         6778 :   edge_iterator ei;
     575              : 
     576        32317 :   FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
     577              :     {
     578        30591 :       if (e->dest == m_final_bb)
     579         5138 :         continue;
     580              : 
     581        25453 :       if (!empty_block_p (e->dest))
     582              :         {
     583         6275 :           if (m_contiguous_range && e == e_default)
     584              :             {
     585         1223 :               m_default_case_nonstandard = true;
     586         1223 :               continue;
     587              :             }
     588              : 
     589         5052 :           m_reason = "bad case - a non-final BB not empty";
     590         5052 :           return false;
     591              :         }
     592              :     }
     593              : 
     594              :   return true;
     595              : }
     596              : 
     597              : /* This function checks whether all required values in phi nodes in final_bb
     598              :    are constants.  Required values are those that correspond to a basic block
     599              :    which is a part of the examined switch statement.  It returns true if the
     600              :    phi nodes are OK, otherwise false.  */
     601              : 
     602              : bool
     603         1726 : switch_conversion::check_final_bb ()
     604              : {
     605         1726 :   gphi_iterator gsi;
     606              : 
     607         1726 :   m_phi_count = 0;
     608         2359 :   for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
     609              :     {
     610         1803 :       gphi *phi = gsi.phi ();
     611         1803 :       unsigned int i;
     612              : 
     613         3606 :       if (virtual_operand_p (gimple_phi_result (phi)))
     614           20 :         continue;
     615              : 
     616         1783 :       m_phi_count++;
     617              : 
     618        21173 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
     619              :         {
     620        20560 :           basic_block bb = gimple_phi_arg_edge (phi, i)->src;
     621              : 
     622        20560 :           if (bb == m_switch_bb
     623        58718 :               || (single_pred_p (bb)
     624        18768 :                   && single_pred (bb) == m_switch_bb
     625        18580 :                   && (!m_default_case_nonstandard
     626          497 :                       || empty_block_p (bb))))
     627              :             {
     628        20337 :               tree reloc, val;
     629        20337 :               const char *reason = NULL;
     630              : 
     631        20337 :               val = gimple_phi_arg_def (phi, i);
     632        20337 :               if (!is_gimple_ip_invariant (val))
     633              :                 reason = "non-invariant value from a case";
     634              :               else
     635              :                 {
     636        19219 :                   reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
     637        19219 :                   if ((flag_pic && reloc != null_pointer_node)
     638        19150 :                       || (!flag_pic && reloc == NULL_TREE))
     639              :                     {
     640           69 :                       if (reloc)
     641              :                         reason
     642              :                           = "value from a case would need runtime relocations";
     643              :                       else
     644              :                         reason
     645              :                           = "value from a case is not a valid initializer";
     646              :                     }
     647              :                 }
     648              :               if (reason)
     649              :                 {
     650              :                   /* For contiguous range, we can allow non-constant
     651              :                      or one that needs relocation, as long as it is
     652              :                      only reachable from the default case.  */
     653         1187 :                   if (bb == m_switch_bb)
     654           90 :                     bb = m_final_bb;
     655         1187 :                   if (!m_contiguous_range || bb != m_default_bb)
     656              :                     {
     657         1170 :                       m_reason = reason;
     658         1170 :                       return false;
     659              :                     }
     660              : 
     661           17 :                   unsigned int branch_num = gimple_switch_num_labels (m_switch);
     662          133 :                   for (unsigned int i = 1; i < branch_num; i++)
     663              :                     {
     664           99 :                       if (gimple_switch_label_bb (cfun, m_switch, i) == bb)
     665              :                         {
     666            0 :                           m_reason = reason;
     667            0 :                           return false;
     668              :                         }
     669              :                     }
     670           17 :                   m_default_case_nonstandard = true;
     671              :                 }
     672              :             }
     673              :         }
     674              :     }
     675              : 
     676              :   return true;
     677              : }
     678              : 
     679              : /* The following function allocates default_values, target_{in,out}_names and
     680              :    constructors arrays.  The last one is also populated with pointers to
     681              :    vectors that will become constructors of new arrays.  */
     682              : 
     683              : void
     684          556 : switch_conversion::create_temp_arrays ()
     685              : {
     686          556 :   int i;
     687              : 
     688          556 :   m_default_values = XCNEWVEC (tree, m_phi_count * 3);
     689              :   /* ??? Macros do not support multi argument templates in their
     690              :      argument list.  We create a typedef to work around that problem.  */
     691          556 :   typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
     692          556 :   m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
     693          556 :   m_target_inbound_names = m_default_values + m_phi_count;
     694          556 :   m_target_outbound_names = m_target_inbound_names + m_phi_count;
     695         1167 :   for (i = 0; i < m_phi_count; i++)
     696          611 :     vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1);
     697          556 : }
     698              : 
     699              : /* Populate the array of default values in the order of phi nodes.
     700              :    DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
     701              :    if the range is non-contiguous or the default case has standard
     702              :    structure, otherwise it is the first non-default case instead.  */
     703              : 
     704              : void
     705          556 : switch_conversion::gather_default_values (tree default_case)
     706              : {
     707          556 :   gphi_iterator gsi;
     708          556 :   basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
     709          556 :   edge e;
     710          556 :   int i = 0;
     711              : 
     712          556 :   gcc_assert (CASE_LOW (default_case) == NULL_TREE
     713              :               || m_default_case_nonstandard);
     714              : 
     715          556 :   if (bb == m_final_bb)
     716          238 :     e = find_edge (m_switch_bb, bb);
     717              :   else
     718          318 :     e = single_succ_edge (bb);
     719              : 
     720         1187 :   for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
     721              :     {
     722          631 :       gphi *phi = gsi.phi ();
     723         1262 :       if (virtual_operand_p (gimple_phi_result (phi)))
     724           20 :         continue;
     725          611 :       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
     726          611 :       gcc_assert (val);
     727          611 :       m_default_values[i++] = val;
     728              :     }
     729          556 : }
     730              : 
     731              : /* The following function populates the vectors in the constructors array with
     732              :    future contents of the static arrays.  The vectors are populated in the
     733              :    order of phi nodes.  */
     734              : 
     735              : void
     736          556 : switch_conversion::build_constructors ()
     737              : {
     738          556 :   unsigned i, branch_num = gimple_switch_num_labels (m_switch);
     739          556 :   tree pos = m_range_min;
     740          556 :   tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
     741              : 
     742         8311 :   for (i = 1; i < branch_num; i++)
     743              :     {
     744         7755 :       tree cs = gimple_switch_label (m_switch, i);
     745         7755 :       basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
     746         7755 :       edge e;
     747         7755 :       tree high;
     748         7755 :       gphi_iterator gsi;
     749         7755 :       int j;
     750              : 
     751         7755 :       if (bb == m_final_bb)
     752          395 :         e = find_edge (m_switch_bb, bb);
     753              :       else
     754         7360 :         e = single_succ_edge (bb);
     755         7755 :       gcc_assert (e);
     756              : 
     757        10224 :       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
     758              :         {
     759              :           int k;
     760         6370 :           for (k = 0; k < m_phi_count; k++)
     761              :             {
     762         3901 :               constructor_elt elt;
     763              : 
     764         3901 :               elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
     765         3901 :               if (TYPE_PRECISION (TREE_TYPE (elt.index))
     766         3901 :                   > TYPE_PRECISION (sizetype))
     767           18 :                 elt.index = fold_convert (sizetype, elt.index);
     768         3901 :               elt.value
     769         3901 :                 = unshare_expr_without_location (m_default_values[k]);
     770         3901 :               m_constructors[k]->quick_push (elt);
     771              :             }
     772              : 
     773         2469 :           pos = int_const_binop (PLUS_EXPR, pos, pos_one);
     774              :         }
     775         7755 :       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
     776              : 
     777         7755 :       j = 0;
     778         7755 :       if (CASE_HIGH (cs))
     779          109 :         high = CASE_HIGH (cs);
     780              :       else
     781         7646 :         high = CASE_LOW (cs);
     782         7755 :       for (gsi = gsi_start_phis (m_final_bb);
     783        16069 :            !gsi_end_p (gsi); gsi_next (&gsi))
     784              :         {
     785         8314 :           gphi *phi = gsi.phi ();
     786        16628 :           if (virtual_operand_p (gimple_phi_result (phi)))
     787          102 :             continue;
     788         8212 :           tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
     789         8212 :           tree low = CASE_LOW (cs);
     790         8212 :           pos = CASE_LOW (cs);
     791              : 
     792         8540 :           do
     793              :             {
     794         8540 :               constructor_elt elt;
     795              : 
     796         8540 :               elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
     797         8540 :               if (TYPE_PRECISION (TREE_TYPE (elt.index))
     798         8540 :                   > TYPE_PRECISION (sizetype))
     799           33 :                 elt.index = fold_convert (sizetype, elt.index);
     800         8540 :               elt.value = unshare_expr_without_location (val);
     801         8540 :               m_constructors[j]->quick_push (elt);
     802              : 
     803         8540 :               pos = int_const_binop (PLUS_EXPR, pos, pos_one);
     804         8540 :             } while (!tree_int_cst_lt (high, pos)
     805        16752 :                      && tree_int_cst_lt (low, pos));
     806         8212 :           j++;
     807              :         }
     808              :     }
     809          556 : }
     810              : 
     811              : /* If all values in the constructor vector are products of a linear function
     812              :    a * x + b, then return true.  When true, COEFF_A and COEFF_B and
     813              :    coefficients of the linear function.  Note that equal values are special
     814              :    case of a linear function with a and b equal to zero.  */
     815              : 
     816              : bool
     817          611 : switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
     818              :                                                wide_int *coeff_a,
     819              :                                                wide_int *coeff_b)
     820              : {
     821          611 :   unsigned int i;
     822          611 :   constructor_elt *elt;
     823              : 
     824          611 :   gcc_assert (vec->length () >= 2);
     825              : 
     826              :   /* Let's try to find any linear function a * x + y that can apply to
     827              :      given values. 'a' can be calculated as follows:
     828              : 
     829              :      a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
     830              :      a = y2 - y1
     831              : 
     832              :      and
     833              : 
     834              :      b = y2 - a * x2
     835              : 
     836              :   */
     837              : 
     838          611 :   tree elt0 = (*vec)[0].value;
     839          611 :   tree elt1 = (*vec)[1].value;
     840              : 
     841          611 :   if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
     842              :     return false;
     843              : 
     844          455 :   wide_int range_min
     845          455 :     = wide_int::from (wi::to_wide (m_range_min),
     846          455 :                       TYPE_PRECISION (TREE_TYPE (elt0)),
     847         1365 :                       TYPE_SIGN (TREE_TYPE (m_range_min)));
     848          455 :   wide_int y1 = wi::to_wide (elt0);
     849          455 :   wide_int y2 = wi::to_wide (elt1);
     850          455 :   wide_int a = y2 - y1;
     851          455 :   wide_int b = y2 - a * (range_min + 1);
     852              : 
     853              :   /* Verify that all values fulfill the linear function.  */
     854         1872 :   FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
     855              :     {
     856         1771 :       if (TREE_CODE (elt->value) != INTEGER_CST)
     857          354 :         return false;
     858              : 
     859         1771 :       wide_int value = wi::to_wide (elt->value);
     860         1771 :       if (a * range_min + b != value)
     861          354 :         return false;
     862              : 
     863         1417 :       ++range_min;
     864         1771 :     }
     865              : 
     866          101 :   *coeff_a = a;
     867          101 :   *coeff_b = b;
     868              : 
     869          101 :   return true;
     870          455 : }
     871              : 
     872              : /* Return type which should be used for array elements, either TYPE's
     873              :    main variant or, for integral types, some smaller integral type
     874              :    that can still hold all the constants.  */
     875              : 
     876              : tree
     877          510 : switch_conversion::array_value_type (tree type, int num)
     878              : {
     879          510 :   unsigned int i, len = vec_safe_length (m_constructors[num]);
     880          510 :   constructor_elt *elt;
     881          510 :   int sign = 0;
     882          510 :   tree smaller_type;
     883              : 
     884              :   /* Types with alignments greater than their size can reach here, e.g. out of
     885              :      SRA.  We couldn't use these as an array component type so get back to the
     886              :      main variant first, which, for our purposes, is fine for other types as
     887              :      well.  */
     888              : 
     889          510 :   type = TYPE_MAIN_VARIANT (type);
     890              : 
     891          510 :   if (!INTEGRAL_TYPE_P (type)
     892          510 :       || (BITINT_TYPE_P (type)
     893            0 :           && (TYPE_PRECISION (type) > MAX_FIXED_MODE_SIZE
     894            0 :               || TYPE_MODE (type) == BLKmode)))
     895              :     return type;
     896              : 
     897          354 :   scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
     898          354 :   scalar_int_mode mode = get_narrowest_mode (type_mode);
     899         1062 :   if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
     900              :     return type;
     901              : 
     902          476 :   if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
     903              :     return type;
     904              : 
     905         2642 :   FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
     906              :     {
     907         2589 :       wide_int cst;
     908              : 
     909         2589 :       if (TREE_CODE (elt->value) != INTEGER_CST)
     910              :         return type;
     911              : 
     912         2589 :       cst = wi::to_wide (elt->value);
     913         2610 :       while (1)
     914              :         {
     915         2612 :           unsigned int prec = GET_MODE_BITSIZE (mode);
     916         2610 :           if (prec > HOST_BITS_PER_WIDE_INT)
     917              :             return type;
     918              : 
     919         2610 :           if (sign >= 0 && cst == wi::zext (cst, prec))
     920              :             {
     921         1411 :               if (sign == 0 && cst == wi::sext (cst, prec))
     922              :                 break;
     923          457 :               sign = 1;
     924          457 :               break;
     925              :             }
     926         1199 :           if (sign <= 0 && cst == wi::sext (cst, prec))
     927              :             {
     928              :               sign = -1;
     929              :               break;
     930              :             }
     931              : 
     932           23 :           if (sign == 1)
     933              :             sign = 0;
     934              : 
     935           46 :           if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
     936           67 :               || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
     937              :             return type;
     938              :         }
     939         2589 :     }
     940              : 
     941           53 :   if (sign == 0)
     942           28 :     sign = TYPE_UNSIGNED (type) ? 1 : -1;
     943           53 :   smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
     944           53 :   if (GET_MODE_SIZE (type_mode)
     945          106 :       <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
     946            0 :     return type;
     947              : 
     948              :   return smaller_type;
     949              : }
     950              : 
     951              : /* Create an appropriate array type and declaration and assemble a static
     952              :    array variable.  Also create a load statement that initializes
     953              :    the variable in question with a value from the static array.  SWTCH is
     954              :    the switch statement being converted, NUM is the index to
     955              :    arrays of constructors, default values and target SSA names
     956              :    for this particular array.  ARR_INDEX_TYPE is the type of the index
     957              :    of the new array, PHI is the phi node of the final BB that corresponds
     958              :    to the value that will be loaded from the created array.  TIDX
     959              :    is an ssa name of a temporary variable holding the index for loads from the
     960              :    new array.  */
     961              : 
     962              : void
     963          611 : switch_conversion::build_one_array (int num, tree arr_index_type,
     964              :                                     gphi *phi, tree tidx)
     965              : {
     966          611 :   tree name;
     967          611 :   gimple *load;
     968          611 :   gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
     969              : 
     970          611 :   gcc_assert (m_default_values[num]);
     971              : 
     972          611 :   name = copy_ssa_name (PHI_RESULT (phi));
     973          611 :   m_target_inbound_names[num] = name;
     974              : 
     975          611 :   vec<constructor_elt, va_gc> *constructor = m_constructors[num];
     976          611 :   wide_int coeff_a, coeff_b;
     977          611 :   bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
     978          611 :   tree type;
     979          611 :   if (linear_p
     980          611 :       && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
     981              :     {
     982          118 :       if (dump_file && coeff_a.to_uhwi () > 0)
     983           16 :         fprintf (dump_file, "Linear transformation with A = %" PRId64
     984              :                  " and B = %" PRId64 "\n", coeff_a.to_shwi (),
     985              :                  coeff_b.to_shwi ());
     986              : 
     987              :       /* We must use type of constructor values.  */
     988          101 :       gimple_seq seq = NULL;
     989          101 :       tree tmp = gimple_convert (&seq, type, m_index_expr);
     990          202 :       tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
     991          101 :                                 wide_int_to_tree (type, coeff_a), tmp);
     992          202 :       tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
     993          101 :                                 wide_int_to_tree (type, coeff_b));
     994          101 :       tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
     995          101 :       gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
     996          101 :       load = gimple_build_assign (name, tmp4);
     997              :     }
     998              :   else
     999              :     {
    1000          510 :       tree array_type, ctor, decl, value_type, fetch, default_type;
    1001              : 
    1002          510 :       default_type = TREE_TYPE (m_default_values[num]);
    1003          510 :       value_type = array_value_type (default_type, num);
    1004          510 :       array_type = build_array_type (value_type, arr_index_type);
    1005          510 :       addr_space_t as
    1006          510 :         = targetm.addr_space.for_artificial_rodata (array_type,
    1007              :                                                     ARTIFICIAL_RODATA_CSWITCH);
    1008          510 :       if (!ADDR_SPACE_GENERIC_P (as))
    1009              :         {
    1010            0 :           qualifier_set quals {TYPE_QUALS_NO_ADDR_SPACE (value_type), as};
    1011            0 :           value_type = build_qualified_type (value_type, quals);
    1012            0 :           array_type = build_array_type (value_type, arr_index_type);
    1013              :         }
    1014          510 :       if (default_type != value_type)
    1015              :         {
    1016              :           unsigned int i;
    1017              :           constructor_elt *elt;
    1018              : 
    1019         3386 :           FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
    1020         3272 :             elt->value = fold_convert (value_type, elt->value);
    1021              :         }
    1022          510 :       ctor = build_constructor (array_type, constructor);
    1023          510 :       TREE_CONSTANT (ctor) = true;
    1024          510 :       TREE_STATIC (ctor) = true;
    1025              : 
    1026          510 :       decl = build_decl (UNKNOWN_LOCATION, VAR_DECL, NULL_TREE, array_type);
    1027          510 :       TREE_STATIC (decl) = 1;
    1028          510 :       DECL_INITIAL (decl) = ctor;
    1029              : 
    1030          510 :       DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
    1031          510 :       DECL_ARTIFICIAL (decl) = 1;
    1032          510 :       DECL_IGNORED_P (decl) = 1;
    1033          510 :       TREE_CONSTANT (decl) = 1;
    1034          510 :       TREE_READONLY (decl) = 1;
    1035          510 :       DECL_IGNORED_P (decl) = 1;
    1036              :       /* The decl is mergeable since we don't take the address ever and
    1037              :          just reading from it. */
    1038          510 :       DECL_MERGEABLE (decl) = 1;
    1039              : 
    1040          510 :       if (offloading_function_p (cfun->decl))
    1041            0 :         DECL_ATTRIBUTES (decl)
    1042            0 :           = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
    1043              :                        NULL_TREE);
    1044          510 :       varpool_node::finalize_decl (decl);
    1045              : 
    1046          510 :       fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
    1047              :                       NULL_TREE);
    1048          510 :       if (default_type != value_type)
    1049              :         {
    1050          114 :           fetch = fold_convert (default_type, fetch);
    1051          114 :           fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
    1052              :                                             true, GSI_SAME_STMT);
    1053              :         }
    1054          510 :       load = gimple_build_assign (name, fetch);
    1055              :     }
    1056              : 
    1057          611 :   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    1058          611 :   update_stmt (load);
    1059          611 :   m_arr_ref_last = load;
    1060          611 : }
    1061              : 
    1062              : /* Builds and initializes static arrays initialized with values gathered from
    1063              :    the switch statement.  Also creates statements that load values from
    1064              :    them.  */
    1065              : 
    1066              : void
    1067          556 : switch_conversion::build_arrays ()
    1068              : {
    1069          556 :   tree arr_index_type;
    1070          556 :   tree tidx, uidx, sub, utype, tidxtype;
    1071          556 :   gimple *stmt;
    1072          556 :   gimple_stmt_iterator gsi;
    1073          556 :   gphi_iterator gpi;
    1074          556 :   int i;
    1075          556 :   location_t loc = gimple_location (m_switch);
    1076              : 
    1077          556 :   gsi = gsi_for_stmt (m_switch);
    1078              : 
    1079              :   /* Make sure we do not generate arithmetics in a subrange.  */
    1080          556 :   utype = TREE_TYPE (m_index_expr);
    1081          556 :   if (TREE_TYPE (utype))
    1082           48 :     utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
    1083          507 :   else if (BITINT_TYPE_P (utype)
    1084          509 :            && (TYPE_PRECISION (utype) > MAX_FIXED_MODE_SIZE
    1085            0 :                || TYPE_MODE (utype) == BLKmode))
    1086            1 :     utype = unsigned_type_for (utype);
    1087              :   else
    1088          507 :     utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
    1089          556 :   if (TYPE_PRECISION (utype) > TYPE_PRECISION (sizetype))
    1090           11 :     tidxtype = sizetype;
    1091              :   else
    1092              :     tidxtype = utype;
    1093              : 
    1094          556 :   arr_index_type = build_index_type (m_range_size);
    1095          556 :   uidx = make_ssa_name (utype);
    1096          556 :   sub = fold_build2_loc (loc, MINUS_EXPR, utype,
    1097              :                          fold_convert_loc (loc, utype, m_index_expr),
    1098              :                          fold_convert_loc (loc, utype, m_range_min));
    1099          556 :   sub = force_gimple_operand_gsi (&gsi, sub,
    1100              :                                   false, NULL, true, GSI_SAME_STMT);
    1101          556 :   stmt = gimple_build_assign (uidx, sub);
    1102              : 
    1103          556 :   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
    1104          556 :   m_arr_ref_first = stmt;
    1105              : 
    1106          556 :   tidx = uidx;
    1107          556 :   if (tidxtype != utype)
    1108              :     {
    1109           11 :       tidx = make_ssa_name (tidxtype);
    1110           11 :       stmt = gimple_build_assign (tidx, NOP_EXPR, uidx);
    1111           11 :       gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
    1112              :     }
    1113              : 
    1114          556 :   for (gpi = gsi_start_phis (m_final_bb), i = 0;
    1115         1187 :        !gsi_end_p (gpi); gsi_next (&gpi))
    1116              :     {
    1117          631 :       gphi *phi = gpi.phi ();
    1118         1262 :       if (!virtual_operand_p (gimple_phi_result (phi)))
    1119          611 :         build_one_array (i++, arr_index_type, phi, tidx);
    1120              :       else
    1121              :         {
    1122           20 :           edge e;
    1123           20 :           edge_iterator ei;
    1124           24 :           FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
    1125              :             {
    1126           24 :               if (e->dest == m_final_bb)
    1127              :                 break;
    1128           14 :               if (!m_default_case_nonstandard
    1129            4 :                   || e->dest != m_default_bb)
    1130              :                 {
    1131           10 :                   e = single_succ_edge (e->dest);
    1132           10 :                   break;
    1133              :                 }
    1134              :             }
    1135           20 :           gcc_assert (e && e->dest == m_final_bb);
    1136           20 :           m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
    1137              :         }
    1138              :     }
    1139          556 : }
    1140              : 
    1141              : /* Generates and appropriately inserts loads of default values at the position
    1142              :    given by GSI.  Returns the last inserted statement.  */
    1143              : 
    1144              : gassign *
    1145          449 : switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
    1146              : {
    1147          449 :   int i;
    1148          449 :   gassign *assign = NULL;
    1149              : 
    1150          941 :   for (i = 0; i < m_phi_count; i++)
    1151              :     {
    1152          492 :       tree name = copy_ssa_name (m_target_inbound_names[i]);
    1153          492 :       m_target_outbound_names[i] = name;
    1154          492 :       assign = gimple_build_assign (name, m_default_values[i]);
    1155          492 :       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
    1156          492 :       update_stmt (assign);
    1157              :     }
    1158          449 :   return assign;
    1159              : }
    1160              : 
    1161              : /* Deletes the unused bbs and edges that now contain the switch statement and
    1162              :    its empty branch bbs.  BBD is the now dead BB containing
    1163              :    the original switch statement, FINAL is the last BB of the converted
    1164              :    switch statement (in terms of succession).  */
    1165              : 
    1166              : void
    1167          556 : switch_conversion::prune_bbs (basic_block bbd, basic_block final,
    1168              :                               basic_block default_bb)
    1169              : {
    1170          556 :   edge_iterator ei;
    1171          556 :   edge e;
    1172              : 
    1173         9282 :   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
    1174              :     {
    1175         8170 :       basic_block bb;
    1176         8170 :       bb = e->dest;
    1177         8170 :       remove_edge (e);
    1178         8170 :       if (bb != final && bb != default_bb)
    1179         7518 :         delete_basic_block (bb);
    1180              :     }
    1181          556 :   delete_basic_block (bbd);
    1182          556 : }
    1183              : 
    1184              : /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
    1185              :    from the basic block loading values from an array and E2F from the basic
    1186              :    block loading default values.  BBF is the last switch basic block (see the
    1187              :    bbf description in the comment below).  */
    1188              : 
    1189              : void
    1190          556 : switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
    1191              : {
    1192          556 :   gphi_iterator gsi;
    1193          556 :   int i;
    1194              : 
    1195          556 :   for (gsi = gsi_start_phis (bbf), i = 0;
    1196         1187 :        !gsi_end_p (gsi); gsi_next (&gsi))
    1197              :     {
    1198          631 :       gphi *phi = gsi.phi ();
    1199          631 :       tree inbound, outbound;
    1200         1262 :       if (virtual_operand_p (gimple_phi_result (phi)))
    1201           20 :         inbound = outbound = m_target_vop;
    1202              :       else
    1203              :         {
    1204          611 :           inbound = m_target_inbound_names[i];
    1205          611 :           outbound = m_target_outbound_names[i++];
    1206              :         }
    1207          631 :       add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
    1208          631 :       if (!m_default_case_nonstandard)
    1209          508 :         add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
    1210              :     }
    1211          556 : }
    1212              : 
    1213              : /* Creates a check whether the switch expression value actually falls into the
    1214              :    range given by all the cases.  If it does not, the temporaries are loaded
    1215              :    with default values instead.  */
    1216              : 
    1217              : void
    1218          556 : switch_conversion::gen_inbound_check ()
    1219              : {
    1220          556 :   tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
    1221          556 :   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
    1222          556 :   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
    1223          556 :   glabel *label1, *label2, *label3;
    1224          556 :   tree utype, tidx;
    1225          556 :   tree bound;
    1226              : 
    1227          556 :   gcond *cond_stmt;
    1228              : 
    1229          556 :   gassign *last_assign = NULL;
    1230          556 :   gimple_stmt_iterator gsi;
    1231          556 :   basic_block bb0, bb1, bb2, bbf, bbd;
    1232          556 :   edge e01 = NULL, e02, e21, e1d, e1f, e2f;
    1233          556 :   location_t loc = gimple_location (m_switch);
    1234              : 
    1235          556 :   gcc_assert (m_default_values);
    1236              : 
    1237          556 :   bb0 = gimple_bb (m_switch);
    1238              : 
    1239          556 :   tidx = gimple_assign_lhs (m_arr_ref_first);
    1240          556 :   utype = TREE_TYPE (tidx);
    1241              : 
    1242              :   /* (end of) block 0 */
    1243          556 :   gsi = gsi_for_stmt (m_arr_ref_first);
    1244          556 :   gsi_next (&gsi);
    1245              : 
    1246          556 :   bound = fold_convert_loc (loc, utype, m_range_size);
    1247          556 :   cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
    1248          556 :   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
    1249          556 :   update_stmt (cond_stmt);
    1250              : 
    1251              :   /* block 2 */
    1252          556 :   if (!m_default_case_nonstandard)
    1253              :     {
    1254          449 :       label2 = gimple_build_label (label_decl2);
    1255          449 :       gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
    1256          449 :       last_assign = gen_def_assigns (&gsi);
    1257              :     }
    1258              : 
    1259              :   /* block 1 */
    1260          556 :   label1 = gimple_build_label (label_decl1);
    1261          556 :   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
    1262              : 
    1263              :   /* block F */
    1264          556 :   gsi = gsi_start_bb (m_final_bb);
    1265          556 :   label3 = gimple_build_label (label_decl3);
    1266          556 :   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
    1267              : 
    1268              :   /* cfg fix */
    1269          556 :   e02 = split_block (bb0, cond_stmt);
    1270          556 :   bb2 = e02->dest;
    1271              : 
    1272          556 :   if (m_default_case_nonstandard)
    1273              :     {
    1274          107 :       bb1 = bb2;
    1275          107 :       bb2 = m_default_bb;
    1276          107 :       e01 = e02;
    1277          107 :       e01->flags = EDGE_TRUE_VALUE;
    1278          107 :       e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
    1279          107 :       edge e_default = find_edge (bb1, bb2);
    1280          107 :       for (gphi_iterator gsi = gsi_start_phis (bb2);
    1281          144 :            !gsi_end_p (gsi); gsi_next (&gsi))
    1282              :         {
    1283           37 :           gphi *phi = gsi.phi ();
    1284           37 :           tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
    1285           37 :           add_phi_arg (phi, arg, e02,
    1286              :                        gimple_phi_arg_location_from_edge (phi, e_default));
    1287              :         }
    1288              :       /* Partially fix the dominator tree, if it is available.  */
    1289          107 :       if (dom_info_available_p (CDI_DOMINATORS))
    1290          107 :         redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
    1291              :     }
    1292              :   else
    1293              :     {
    1294          449 :       e21 = split_block (bb2, last_assign);
    1295          449 :       bb1 = e21->dest;
    1296          449 :       remove_edge (e21);
    1297              :     }
    1298              : 
    1299          556 :   e1d = split_block (bb1, m_arr_ref_last);
    1300          556 :   bbd = e1d->dest;
    1301          556 :   remove_edge (e1d);
    1302              : 
    1303              :   /* Flags and profiles of the edge for in-range values.  */
    1304          556 :   if (!m_default_case_nonstandard)
    1305          449 :     e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
    1306          556 :   e01->probability = m_default_prob.invert ();
    1307              : 
    1308              :   /* Flags and profiles of the edge taking care of out-of-range values.  */
    1309          556 :   e02->flags &= ~EDGE_FALLTHRU;
    1310          556 :   e02->flags |= EDGE_FALSE_VALUE;
    1311          556 :   e02->probability = m_default_prob;
    1312              : 
    1313          556 :   bbf = m_final_bb;
    1314              : 
    1315          556 :   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
    1316          556 :   e1f->probability = profile_probability::always ();
    1317              : 
    1318          556 :   if (m_default_case_nonstandard)
    1319              :     e2f = NULL;
    1320              :   else
    1321              :     {
    1322          449 :       e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
    1323          449 :       e2f->probability = profile_probability::always ();
    1324              :     }
    1325              : 
    1326              :   /* frequencies of the new BBs */
    1327          556 :   bb1->count = e01->count ();
    1328          556 :   bb2->count = e02->count ();
    1329          556 :   if (!m_default_case_nonstandard)
    1330          449 :     bbf->count = e1f->count () + e2f->count ();
    1331              : 
    1332              :   /* Tidy blocks that have become unreachable.  */
    1333         1240 :   bool prune_default_bb = !m_default_case_nonstandard
    1334          556 :     && !m_exp_index_transform_applied;
    1335          556 :   prune_bbs (bbd, m_final_bb, prune_default_bb ? NULL : m_default_bb);
    1336              : 
    1337              :   /* Fixup the PHI nodes in bbF.  */
    1338          556 :   fix_phi_nodes (e1f, e2f, bbf);
    1339              : 
    1340              :   /* Fix the dominator tree, if it is available.  */
    1341          556 :   if (dom_info_available_p (CDI_DOMINATORS))
    1342              :     {
    1343          556 :       vec<basic_block> bbs_to_fix_dom;
    1344              : 
    1345          556 :       set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
    1346          556 :       if (!m_default_case_nonstandard)
    1347          449 :         set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
    1348          556 :       if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
    1349              :         /* If bbD was the immediate dominator ...  */
    1350          332 :         set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
    1351              : 
    1352          571 :       bbs_to_fix_dom.create (3 + (bb2 != bbf));
    1353          556 :       bbs_to_fix_dom.quick_push (bb0);
    1354          556 :       bbs_to_fix_dom.quick_push (bb1);
    1355          556 :       if (bb2 != bbf)
    1356          541 :         bbs_to_fix_dom.quick_push (bb2);
    1357          556 :       bbs_to_fix_dom.quick_push (bbf);
    1358              : 
    1359          556 :       iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
    1360          556 :       bbs_to_fix_dom.release ();
    1361              :     }
    1362          556 : }
    1363              : 
    1364              : /* The following function is invoked on every switch statement (the current
    1365              :    one is given in SWTCH) and runs the individual phases of switch
    1366              :    conversion on it one after another until one fails or the conversion
    1367              :    is completed.  On success, NULL is in m_reason, otherwise points
    1368              :    to a string with the reason why the conversion failed.  */
    1369              : 
    1370              : void
    1371        28100 : switch_conversion::expand (gswitch *swtch)
    1372              : {
    1373              :   /* Group case labels so that we get the right results from the heuristics
    1374              :      that decide on the code generation approach for this switch.  */
    1375        28100 :   m_cfg_altered |= group_case_labels_stmt (swtch);
    1376              : 
    1377              :   /* If this switch is now a degenerate case with only a default label,
    1378              :      there is nothing left for us to do.  */
    1379        28100 :   if (gimple_switch_num_labels (swtch) < 2)
    1380              :     {
    1381            0 :       m_reason = "switch is a degenerate case";
    1382            0 :       return;
    1383              :     }
    1384              : 
    1385        28100 :   collect (swtch);
    1386              : 
    1387              :   /* No error markers should reach here (they should be filtered out
    1388              :      during gimplification).  */
    1389        28100 :   gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
    1390              : 
    1391              :   /* Prefer bit test if possible.  */
    1392        28100 :   if (tree_fits_uhwi_p (m_range_size)
    1393        28030 :       && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
    1394        43127 :       && bit_test_cluster::is_beneficial (m_count, m_uniq))
    1395              :     {
    1396         2534 :       m_reason = "expanding as bit test is preferable";
    1397         2534 :       return;
    1398              :     }
    1399              : 
    1400        25566 :   if (m_uniq <= 2)
    1401              :     {
    1402              :       /* This will be expanded as a decision tree .  */
    1403         8182 :       m_reason = "expanding as jumps is preferable";
    1404         8182 :       return;
    1405              :     }
    1406              : 
    1407              :   /* If there is no common successor, we cannot do the transformation.  */
    1408        17384 :   if (!m_final_bb)
    1409              :     {
    1410        10152 :       m_reason = "no common successor to all case label target blocks found";
    1411        10152 :       return;
    1412              :     }
    1413              : 
    1414              :   /* Sometimes it is possible to use the "exponential index transform" to help
    1415              :      switch conversion convert switches which it otherwise could not convert.
    1416              :      However, we want to do this transform only when we know that switch
    1417              :      conversion will then really be able to convert the switch.  So we first
    1418              :      check if the transformation is applicable and then maybe later do the
    1419              :      transformation.  */
    1420         7232 :   bool exp_transform_viable = is_exp_index_transform_viable (swtch);
    1421              : 
    1422              :   /* Check the case label values are within reasonable range.
    1423              : 
    1424              :      If we will be doing exponential index transform, the range will be always
    1425              :      reasonable.  */
    1426         7232 :   if (!exp_transform_viable && !check_range ())
    1427              :     {
    1428          454 :       gcc_assert (m_reason);
    1429              :       return;
    1430              :     }
    1431              : 
    1432              :   /* For all the cases, see whether they are empty, the assignments they
    1433              :      represent constant and so on...  */
    1434         6778 :   if (!check_all_empty_except_final ())
    1435              :     {
    1436         5052 :       gcc_assert (m_reason);
    1437              :       return;
    1438              :     }
    1439         1726 :   if (!check_final_bb ())
    1440              :     {
    1441         1170 :       gcc_assert (m_reason);
    1442              :       return;
    1443              :     }
    1444              : 
    1445              :   /* At this point all checks have passed and we can proceed with the
    1446              :      transformation.  */
    1447              : 
    1448          556 :   if (exp_transform_viable)
    1449           21 :     exp_index_transform (swtch);
    1450              : 
    1451          556 :   create_temp_arrays ();
    1452         1112 :   gather_default_values (m_default_case_nonstandard
    1453          107 :                          ? gimple_switch_label (swtch, 1)
    1454          449 :                          : gimple_switch_default_label (swtch));
    1455          556 :   build_constructors ();
    1456              : 
    1457          556 :   build_arrays (); /* Build the static arrays and assignments.  */
    1458          556 :   gen_inbound_check (); /* Build the bounds check.  */
    1459              : 
    1460          556 :   m_cfg_altered = true;
    1461              : }
    1462              : 
    1463              : /* Destructor.  */
    1464              : 
    1465        28100 : switch_conversion::~switch_conversion ()
    1466              : {
    1467        28100 :   XDELETEVEC (m_constructors);
    1468        28100 :   XDELETEVEC (m_default_values);
    1469        28100 : }
    1470              : 
    1471              : /* Constructor.  */
    1472              : 
    1473        12267 : group_cluster::group_cluster (vec<cluster *> &clusters,
    1474        12267 :                               unsigned start, unsigned end)
    1475              : {
    1476        12267 :   gcc_checking_assert (end - start + 1 >= 1);
    1477        12267 :   m_prob = profile_probability::never ();
    1478        12267 :   m_cases.create (end - start + 1);
    1479       125512 :   for (unsigned i = start; i <= end; i++)
    1480              :     {
    1481       100978 :       m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
    1482       100978 :       m_prob += clusters[i]->m_prob;
    1483              :     }
    1484        12267 :   m_subtree_prob = m_prob;
    1485        12267 : }
    1486              : 
    1487              : /* Destructor.  */
    1488              : 
    1489        12267 : group_cluster::~group_cluster ()
    1490              : {
    1491       113245 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1492       100978 :     delete m_cases[i];
    1493              : 
    1494        12267 :   m_cases.release ();
    1495        12267 : }
    1496              : 
    1497              : /* Dump content of a cluster.  */
    1498              : 
    1499              : void
    1500           30 : group_cluster::dump (FILE *f, bool details)
    1501              : {
    1502           30 :   unsigned total_values = 0;
    1503          414 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1504          354 :     total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
    1505          177 :                                            m_cases[i]->get_high ());
    1506              : 
    1507              :   unsigned comparison_count = 0;
    1508          207 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1509              :     {
    1510          177 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1511          299 :       comparison_count += sc->get_comparison_count ();
    1512              :     }
    1513              : 
    1514           30 :   unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
    1515           48 :   fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
    1516              : 
    1517           30 :   if (details)
    1518            0 :     fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
    1519              :              " density: %.2f%%)", total_values, comparison_count, range,
    1520            0 :              100.0f * comparison_count / range);
    1521              : 
    1522           30 :   fprintf (f, ":");
    1523           30 :   PRINT_CASE (f, get_low ());
    1524           30 :   fprintf (f, "-");
    1525           30 :   PRINT_CASE (f, get_high ());
    1526           30 :   fprintf (f, " ");
    1527           30 : }
    1528              : 
    1529              : /* Emit GIMPLE code to handle the cluster.  */
    1530              : 
    1531              : void
    1532         6885 : jump_table_cluster::emit (tree index_expr, tree,
    1533              :                           tree default_label_expr, basic_block default_bb,
    1534              :                           location_t loc)
    1535              : {
    1536         6885 :   tree low = get_low ();
    1537         6885 :   unsigned HOST_WIDE_INT range = get_range (low, get_high ());
    1538         6885 :   unsigned HOST_WIDE_INT nondefault_range = 0;
    1539         6885 :   bool bitint = false;
    1540         6885 :   gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
    1541              : 
    1542              :   /* For large/huge _BitInt, subtract low from index_expr, cast to unsigned
    1543              :      DImode type (get_range doesn't support ranges larger than 64-bits)
    1544              :      and subtract low from all case values as well.  */
    1545        13761 :   if (BITINT_TYPE_P (TREE_TYPE (index_expr))
    1546         6885 :       && TYPE_PRECISION (TREE_TYPE (index_expr)) > GET_MODE_PRECISION (DImode))
    1547              :     {
    1548            9 :       bitint = true;
    1549            9 :       tree this_low = low, type;
    1550            9 :       gimple *g;
    1551            9 :       gimple_seq seq = NULL;
    1552            9 :       if (!TYPE_UNSIGNED (TREE_TYPE (index_expr)))
    1553              :         {
    1554            8 :           type = unsigned_type_for (TREE_TYPE (index_expr));
    1555            8 :           index_expr = gimple_convert (&seq, type, index_expr);
    1556            8 :           this_low = fold_convert (type, this_low);
    1557              :         }
    1558            9 :       this_low = const_unop (NEGATE_EXPR, TREE_TYPE (this_low), this_low);
    1559            9 :       index_expr = gimple_build (&seq, PLUS_EXPR, TREE_TYPE (index_expr),
    1560              :                                  index_expr, this_low);
    1561            9 :       type = build_nonstandard_integer_type (GET_MODE_PRECISION (DImode), 1);
    1562            9 :       g = gimple_build_cond (GT_EXPR, index_expr,
    1563            9 :                              fold_convert (TREE_TYPE (index_expr),
    1564              :                                            TYPE_MAX_VALUE (type)),
    1565              :                              NULL_TREE, NULL_TREE);
    1566            9 :       gimple_seq_add_stmt (&seq, g);
    1567            9 :       gimple_seq_set_location (seq, loc);
    1568            9 :       gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
    1569            9 :       edge e1 = split_block (m_case_bb, g);
    1570            9 :       e1->flags = EDGE_FALSE_VALUE;
    1571            9 :       e1->probability = profile_probability::likely ();
    1572            9 :       edge e2 = make_edge (e1->src, default_bb, EDGE_TRUE_VALUE);
    1573            9 :       e2->probability = e1->probability.invert ();
    1574            9 :       gsi = gsi_start_bb (e1->dest);
    1575            9 :       seq = NULL;
    1576            9 :       index_expr = gimple_convert (&seq, type, index_expr);
    1577            9 :       gimple_seq_set_location (seq, loc);
    1578            9 :       gsi_insert_seq_after (&gsi, seq, GSI_NEW_STMT);
    1579              :     }
    1580              : 
    1581              :   /* For jump table we just emit a new gswitch statement that will
    1582              :      be latter lowered to jump table.  */
    1583         6885 :   auto_vec <tree> labels;
    1584        13770 :   labels.create (m_cases.length ());
    1585              : 
    1586         6885 :   basic_block case_bb = gsi_bb (gsi);
    1587         6885 :   make_edge (case_bb, default_bb, 0);
    1588        89891 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1589              :     {
    1590        76121 :       tree lab = unshare_expr (m_cases[i]->m_case_label_expr);
    1591        76121 :       if (bitint)
    1592              :         {
    1593           69 :           CASE_LOW (lab)
    1594           69 :             = fold_convert (TREE_TYPE (index_expr),
    1595              :                             const_binop (MINUS_EXPR,
    1596              :                                          TREE_TYPE (CASE_LOW (lab)),
    1597              :                                          CASE_LOW (lab), low));
    1598           69 :           if (CASE_HIGH (lab))
    1599            0 :             CASE_HIGH (lab)
    1600            0 :               = fold_convert (TREE_TYPE (index_expr),
    1601              :                               const_binop (MINUS_EXPR,
    1602              :                                            TREE_TYPE (CASE_HIGH (lab)),
    1603              :                                            CASE_HIGH (lab), low));
    1604              :         }
    1605        76121 :       labels.quick_push (lab);
    1606        76121 :       make_edge (case_bb, m_cases[i]->m_case_bb, 0);
    1607              :     }
    1608              : 
    1609         6885 :   gswitch *s = gimple_build_switch (index_expr,
    1610              :                                     unshare_expr (default_label_expr), labels);
    1611         6885 :   gimple_set_location (s, loc);
    1612         6885 :   gsi_insert_after (&gsi, s, GSI_NEW_STMT);
    1613              : 
    1614              :   /* Set up even probabilities for all cases.  */
    1615        89891 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1616              :     {
    1617        76121 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1618        76121 :       edge case_edge = find_edge (case_bb, sc->m_case_bb);
    1619        76121 :       unsigned HOST_WIDE_INT case_range
    1620        76121 :         = sc->get_range (sc->get_low (), sc->get_high ());
    1621        76121 :       nondefault_range += case_range;
    1622              : 
    1623              :       /* case_edge->aux is number of values in a jump-table that are covered
    1624              :          by the case_edge.  */
    1625        76121 :       case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
    1626              :     }
    1627              : 
    1628         6885 :   edge default_edge = gimple_switch_default_edge (cfun, s);
    1629         6885 :   default_edge->probability = profile_probability::never ();
    1630              : 
    1631        83006 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1632              :     {
    1633        76121 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1634        76121 :       edge case_edge = find_edge (case_bb, sc->m_case_bb);
    1635        76121 :       case_edge->probability
    1636        76121 :         = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
    1637              :                                                       range);
    1638              :     }
    1639              : 
    1640              :   /* Number of non-default values is probability of default edge.  */
    1641         6885 :   default_edge->probability
    1642         6885 :     += profile_probability::always ().apply_scale (nondefault_range,
    1643         6885 :                                                    range).invert ();
    1644              : 
    1645         6885 :   switch_decision_tree::reset_out_edges_aux (s);
    1646         6885 : }
    1647              : 
    1648              : /* Find jump tables of given CLUSTERS, where all members of the vector
    1649              :    are of type simple_cluster.  New clusters are returned.  */
    1650              : 
    1651              : vec<cluster *>
    1652        70916 : jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
    1653              : {
    1654        70916 :   if (!is_enabled ())
    1655        15694 :     return clusters.copy ();
    1656              : 
    1657        55222 :   unsigned l = clusters.length ();
    1658              : 
    1659        55222 :   auto_vec<min_cluster_item> min;
    1660        55222 :   min.reserve (l + 1);
    1661              : 
    1662        55222 :   min.quick_push (min_cluster_item (0, 0, 0));
    1663              : 
    1664        55222 :   unsigned HOST_WIDE_INT max_ratio
    1665        55222 :     = (optimize_insn_for_size_p ()
    1666        55222 :        ? param_jump_table_max_growth_ratio_for_size
    1667        55222 :        : param_jump_table_max_growth_ratio_for_speed);
    1668              : 
    1669       254236 :   for (unsigned i = 1; i <= l; i++)
    1670              :     {
    1671              :       /* Set minimal # of clusters with i-th item to infinite.  */
    1672       199014 :       min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
    1673              : 
    1674              :       /* Pre-calculate number of comparisons for the clusters.  */
    1675       199014 :       HOST_WIDE_INT comparison_count = 0;
    1676      6911109 :       for (unsigned k = 0; k <= i - 1; k++)
    1677              :         {
    1678      6712095 :           simple_cluster *sc = static_cast<simple_cluster *> (clusters[k]);
    1679     13254734 :           comparison_count += sc->get_comparison_count ();
    1680              :         }
    1681              : 
    1682      6911109 :       for (unsigned j = 0; j < i; j++)
    1683              :         {
    1684      6712095 :           unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
    1685     13411144 :           if (i - j < case_values_threshold ())
    1686       494789 :             s += i - j;
    1687              : 
    1688              :           /* Prefer clusters with smaller number of numbers covered.  */
    1689      6712095 :           if ((min[j].m_count + 1 < min[i].m_count
    1690      1780075 :                || (min[j].m_count + 1 == min[i].m_count
    1691         1024 :                    && s < min[i].m_non_jt_cases))
    1692      6712144 :               && can_be_handled (clusters, j, i - 1, max_ratio,
    1693              :                                  comparison_count))
    1694       199052 :             min[i] = min_cluster_item (min[j].m_count + 1, j, s);
    1695              : 
    1696      6712095 :           simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
    1697     13254734 :           comparison_count -= sc->get_comparison_count ();
    1698              :         }
    1699              : 
    1700       199014 :       gcc_checking_assert (comparison_count == 0);
    1701       199014 :       gcc_checking_assert (min[i].m_count != INT_MAX);
    1702              :     }
    1703              : 
    1704              :   /* No result.  */
    1705        55222 :   if (min[l].m_count == l)
    1706         7436 :     return clusters.copy ();
    1707              : 
    1708        47786 :   vec<cluster *> output;
    1709        47786 :   output.create (4);
    1710              : 
    1711              :   /* Find and build the clusters.  */
    1712        47786 :   for (unsigned int end = l;;)
    1713              :     {
    1714        53040 :       int start = min[end].m_start;
    1715              : 
    1716              :       /* Do not allow clusters with small number of cases.  */
    1717        53040 :       if (is_beneficial (clusters, start, end - 1))
    1718         7585 :         output.safe_push (new jump_table_cluster (clusters, start, end - 1));
    1719              :       else
    1720       143970 :         for (int i = end - 1; i >= start; i--)
    1721        98515 :           output.safe_push (clusters[i]);
    1722              : 
    1723        53040 :       end = start;
    1724              : 
    1725        53040 :       if (start <= 0)
    1726              :         break;
    1727              :     }
    1728              : 
    1729        47786 :   output.reverse ();
    1730        47786 :   return output;
    1731        55222 : }
    1732              : 
    1733              : /* Return true when cluster starting at START and ending at END (inclusive)
    1734              :    can build a jump-table.  */
    1735              : 
    1736              : bool
    1737      4932069 : jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
    1738              :                                     unsigned start, unsigned end,
    1739              :                                     unsigned HOST_WIDE_INT max_ratio,
    1740              :                                     unsigned HOST_WIDE_INT comparison_count)
    1741              : {
    1742              :   /* If the switch is relatively small such that the cost of one
    1743              :      indirect jump on the target are higher than the cost of a
    1744              :      decision tree, go with the decision tree.
    1745              : 
    1746              :      If range of values is much bigger than number of values,
    1747              :      or if it is too large to represent in a HOST_WIDE_INT,
    1748              :      make a sequence of conditional branches instead of a dispatch.
    1749              : 
    1750              :      The definition of "much bigger" depends on whether we are
    1751              :      optimizing for size or for speed.
    1752              : 
    1753              :      For algorithm correctness, jump table for a single case must return
    1754              :      true.  We bail out in is_beneficial if it's called just for
    1755              :      a single case.  */
    1756      4932069 :   if (start == end)
    1757              :     return true;
    1758              : 
    1759      9718898 :   unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
    1760      4859449 :                                             clusters[end]->get_high ());
    1761              :   /* Check overflow.  */
    1762      4859449 :   if (range == 0)
    1763              :     return false;
    1764              : 
    1765      4856217 :   if (range > HOST_WIDE_INT_M1U / 100)
    1766              :     return false;
    1767              : 
    1768       646007 :   unsigned HOST_WIDE_INT lhs = 100 * range;
    1769       646007 :   if (lhs < range)
    1770              :     return false;
    1771              : 
    1772       646007 :   return lhs <= max_ratio * comparison_count;
    1773              : }
    1774              : 
    1775              : /* Return true if cluster starting at START and ending at END (inclusive)
    1776              :    is profitable transformation.  */
    1777              : 
    1778              : bool
    1779        53040 : jump_table_cluster::is_beneficial (const vec<cluster *> &,
    1780              :                                    unsigned start, unsigned end)
    1781              : {
    1782              :   /* Single case bail out.  */
    1783        53040 :   if (start == end)
    1784              :     return false;
    1785              : 
    1786        96741 :   return end - start + 1 >= case_values_threshold ();
    1787              : }
    1788              : 
    1789              : /* Find bit tests of given CLUSTERS, where all members of the vector
    1790              :    are of type simple_cluster.  MAX_C is the approx max number of cases per
    1791              :    label.  New clusters are returned.  */
    1792              : 
    1793              : vec<cluster *>
    1794        72366 : bit_test_cluster::find_bit_tests (vec<cluster *> &clusters, int max_c)
    1795              : {
    1796        72366 :   if (!is_enabled () || max_c == 1)
    1797        37371 :     return clusters.copy ();
    1798              : 
    1799              :   /* Dynamic programming algorithm.
    1800              : 
    1801              :      In: List of simple clusters
    1802              :      Out: List of simple clusters and bit test clusters such that each bit test
    1803              :      cluster can_be_handled() and is_beneficial()
    1804              : 
    1805              :      Merges consecutive clusters into bigger (bit test) clusters.  Produces the
    1806              :      optimal solution -- the number of clusters in the output list is
    1807              :      minimal.  */
    1808              : 
    1809        34995 :   unsigned l = clusters.length ();
    1810              : 
    1811        34995 :   if (l == 0)
    1812            0 :     return clusters.copy ();
    1813        34995 :   gcc_checking_assert (l <= INT_MAX);
    1814              : 
    1815        34995 :   auto_vec<min_cluster_item> min;
    1816        34995 :   min.reserve (l + 1);
    1817              : 
    1818        34995 :   int bits_in_word = GET_MODE_BITSIZE (word_mode);
    1819              : 
    1820              :   /* First phase: Compute the minimum number of clusters for each prefix of the
    1821              :      input list incrementally
    1822              : 
    1823              :      min[i] = (count, j, _) means that the prefix ending with the (i-1)-th
    1824              :      element can be made to contain as few as count clusters and that in such
    1825              :      clustering the last cluster is made up of input clusters [j, i-1]
    1826              :      (inclusive).  */
    1827        34995 :   min.quick_push (min_cluster_item (0, 0, INT_MAX));
    1828        34995 :   min.quick_push (min_cluster_item (1, 0, INT_MAX));
    1829       112950 :   for (int i = 2; i <= (int) l; i++)
    1830              :     {
    1831        77955 :       auto_vec<unsigned, m_max_case_bit_tests> unique_labels;
    1832              : 
    1833              :       /* Since each cluster contains at least one case number and one bit test
    1834              :          cluster can cover at most bits_in_word case numbers, we don't need to
    1835              :          look farther than bits_in_word clusters back.  */
    1836       360316 :       for (int j = i - 1; j >= 0 && j >= i - bits_in_word; j--)
    1837              :         {
    1838              :           /* Consider creating a bit test cluster from input clusters [j, i-1]
    1839              :              (inclusive)  */
    1840              : 
    1841       305796 :           simple_cluster *sc = static_cast<simple_cluster *> (clusters[j]);
    1842       305796 :           unsigned label = sc->m_case_bb->index;
    1843       305796 :           if (!unique_labels.contains (label))
    1844              :             {
    1845       192962 :               if (unique_labels.length () >= m_max_case_bit_tests)
    1846              :                 /* is_beneficial() will be false for this and the following
    1847              :                    iterations.  */
    1848              :                 break;
    1849       169527 :               unique_labels.quick_push (label);
    1850              :             }
    1851              : 
    1852       282361 :           unsigned new_count = min[j].m_count + 1;
    1853              : 
    1854       282361 :           if (j == i - 1)
    1855              :             {
    1856        77955 :               min.quick_push (min_cluster_item (new_count, j, INT_MAX));
    1857        77955 :               continue;
    1858              :             }
    1859              : 
    1860       204406 :           unsigned HOST_WIDE_INT range
    1861       204406 :             = get_range (clusters[j]->get_low (), clusters[i-1]->get_high ());
    1862       204406 :           if (new_count < min[i].m_count
    1863       153185 :               && can_be_handled (range, unique_labels.length ())
    1864       317802 :               && is_beneficial (i - j, unique_labels.length ()))
    1865         8944 :             min[i] = min_cluster_item (new_count, j, INT_MAX);
    1866              :         }
    1867        77955 :     }
    1868              : 
    1869        34995 :   if (min[l].m_count == l)
    1870              :     /* No bit test clustering opportunities.  */
    1871        30753 :     return clusters.copy ();
    1872              : 
    1873         4242 :   vec<cluster *> output;
    1874         4242 :   output.create (4);
    1875              : 
    1876              :   /* Second phase: Find and build the bit test clusters by traversing min
    1877              :      array backwards.  */
    1878         4242 :   for (unsigned end = l;;)
    1879              :     {
    1880         8606 :       unsigned start = min[end].m_start;
    1881         8606 :       gcc_checking_assert (start < end);
    1882              : 
    1883              :       /* This cluster will be made out of input clusters [start, end - 1].  */
    1884              : 
    1885         8606 :       if (start == end - 1)
    1886              :         /* Let the cluster be a simple cluster.  */
    1887         3924 :         output.safe_push (clusters[start]);
    1888              :       else
    1889              :         {
    1890         4682 :           bool entire = start == 0 && end == l;
    1891         4682 :           output.safe_push (new bit_test_cluster (clusters, start, end - 1,
    1892         4682 :                                                   entire));
    1893              :         }
    1894              : 
    1895         8606 :       end = start;
    1896              : 
    1897         8606 :       if (start <= 0)
    1898              :         break;
    1899              :     }
    1900              : 
    1901         4242 :   output.reverse ();
    1902         4242 :   return output;
    1903        34995 : }
    1904              : 
    1905              : /* Return true when RANGE of case values with UNIQ labels
    1906              :    can build a bit test.  */
    1907              : 
    1908              : bool
    1909       181215 : bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
    1910              :                                   unsigned int uniq)
    1911              : {
    1912              :   /* Check overflow.  */
    1913       181215 :   if (range == 0)
    1914              :     return false;
    1915              : 
    1916       358552 :   if (range > GET_MODE_BITSIZE (word_mode))
    1917              :     return false;
    1918              : 
    1919       138562 :   return uniq <= m_max_case_bit_tests;
    1920              : }
    1921              : 
    1922              : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
    1923              :    transformation.  */
    1924              : 
    1925              : bool
    1926       128423 : bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
    1927              : {
    1928              :   /* NOTE: When modifying this, keep in mind the value of
    1929              :      m_max_case_bit_tests.  */
    1930       128423 :   return (((uniq == 1 && count >= 3)
    1931       119561 :            || (uniq == 2 && count >= 5)
    1932       246705 :            || (uniq == 3 && count >= 6)));
    1933              : }
    1934              : 
    1935              : /* Comparison function for qsort to order bit tests by decreasing
    1936              :    probability of execution.  */
    1937              : 
    1938              : int
    1939         7076 : case_bit_test::cmp (const void *p1, const void *p2)
    1940              : {
    1941         7076 :   const case_bit_test *const d1 = (const case_bit_test *) p1;
    1942         7076 :   const case_bit_test *const d2 = (const case_bit_test *) p2;
    1943              : 
    1944         7076 :   if (d2->bits != d1->bits)
    1945         5966 :     return d2->bits - d1->bits;
    1946              : 
    1947              :   /* Stabilize the sort.  */
    1948         1110 :   return (d2->target_bb->index
    1949         1110 :           - d1->target_bb->index);
    1950              : }
    1951              : 
    1952              : /*  Expand a switch statement by a short sequence of bit-wise
    1953              :     comparisons.  "switch(x)" is effectively converted into
    1954              :     "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
    1955              :     integer constants.
    1956              : 
    1957              :     INDEX_EXPR is the value being switched on.
    1958              : 
    1959              :     MINVAL is the lowest case value of in the case nodes,
    1960              :     and RANGE is highest value minus MINVAL.  MINVAL and RANGE
    1961              :     are not guaranteed to be of the same type as INDEX_EXPR
    1962              :     (the gimplifier doesn't change the type of case label values,
    1963              :     and MINVAL and RANGE are derived from those values).
    1964              :     MAXVAL is MINVAL + RANGE.
    1965              : 
    1966              :     There *MUST* be max_case_bit_tests or less unique case
    1967              :     node targets.  */
    1968              : 
    1969              : void
    1970         3848 : bit_test_cluster::emit (tree index_expr, tree index_type,
    1971              :                         tree, basic_block default_bb, location_t loc)
    1972              : {
    1973        23088 :   case_bit_test test[m_max_case_bit_tests] = { {} };
    1974         3848 :   unsigned int i, j, k;
    1975         3848 :   unsigned int count;
    1976              : 
    1977         3848 :   tree unsigned_index_type = range_check_type (index_type);
    1978              : 
    1979         3848 :   gimple_stmt_iterator gsi;
    1980         3848 :   gassign *shift_stmt;
    1981              : 
    1982         3848 :   tree idx, tmp, csui;
    1983         3848 :   tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
    1984         3848 :   tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
    1985         3848 :   tree word_mode_one = fold_convert (word_type_node, integer_one_node);
    1986         3848 :   int prec = TYPE_PRECISION (word_type_node);
    1987         3848 :   wide_int wone = wi::one (prec);
    1988              : 
    1989         3848 :   tree minval = get_low ();
    1990         3848 :   tree maxval = get_high ();
    1991              : 
    1992              :   /* Go through all case labels, and collect the case labels, profile
    1993              :      counts, and other information we need to build the branch tests.  */
    1994         3848 :   count = 0;
    1995        24574 :   for (i = 0; i < m_cases.length (); i++)
    1996              :     {
    1997        16878 :       unsigned int lo, hi;
    1998        16878 :       simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
    1999        20700 :       for (k = 0; k < count; k++)
    2000        15464 :         if (n->m_case_bb == test[k].target_bb)
    2001              :           break;
    2002              : 
    2003        16878 :       if (k == count)
    2004              :         {
    2005         5236 :           gcc_checking_assert (count < m_max_case_bit_tests);
    2006         5236 :           test[k].mask = wi::zero (prec);
    2007         5236 :           test[k].target_bb = n->m_case_bb;
    2008         5236 :           test[k].bits = 0;
    2009         5236 :           test[k].prob = profile_probability::never ();
    2010         5236 :           count++;
    2011              :         }
    2012              : 
    2013        16878 :       test[k].bits += n->get_range (n->get_low (), n->get_high ());
    2014        16878 :       test[k].prob += n->m_prob;
    2015              : 
    2016        16878 :       lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
    2017        16878 :       if (n->get_high () == NULL_TREE)
    2018              :         hi = lo;
    2019              :       else
    2020        16878 :         hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
    2021              :                                             minval));
    2022              : 
    2023        40220 :       for (j = lo; j <= hi; j++)
    2024        23342 :         test[k].mask |= wi::lshift (wone, j);
    2025              :     }
    2026              : 
    2027         3848 :   qsort (test, count, sizeof (*test), case_bit_test::cmp);
    2028              : 
    2029              :   /* If every possible relative value of the index expression is a valid shift
    2030              :      amount, then we can merge the entry test in the bit test.  */
    2031         3848 :   bool entry_test_needed;
    2032         3848 :   int_range_max r;
    2033         7696 :   if (TREE_CODE (index_expr) == SSA_NAME
    2034         7696 :       && get_range_query (cfun)->range_of_expr (r, index_expr)
    2035         3848 :       && !r.undefined_p ()
    2036         3847 :       && !r.varying_p ()
    2037         8995 :       && wi::leu_p (r.upper_bound () - r.lower_bound (), prec - 1))
    2038              :     {
    2039           62 :       wide_int min = r.lower_bound ();
    2040           62 :       wide_int max = r.upper_bound ();
    2041           62 :       tree index_type = TREE_TYPE (index_expr);
    2042           62 :       minval = fold_convert (index_type, minval);
    2043           62 :       wide_int iminval = wi::to_wide (minval);
    2044           62 :       if (wi::lt_p (min, iminval, TYPE_SIGN (index_type)))
    2045              :         {
    2046           57 :           minval = wide_int_to_tree (index_type, min);
    2047          181 :           for (i = 0; i < count; i++)
    2048          124 :             test[i].mask = wi::lshift (test[i].mask, iminval - min);
    2049              :         }
    2050            5 :       else if (wi::gt_p (min, iminval, TYPE_SIGN (index_type)))
    2051              :         {
    2052            0 :           minval = wide_int_to_tree (index_type, min);
    2053            0 :           for (i = 0; i < count; i++)
    2054            0 :             test[i].mask = wi::lrshift (test[i].mask, min - iminval);
    2055              :         }
    2056           62 :       maxval = wide_int_to_tree (index_type, max);
    2057           62 :       entry_test_needed = false;
    2058           62 :     }
    2059              :   else
    2060              :     entry_test_needed = true;
    2061              : 
    2062              :   /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
    2063              :      the minval subtractions, but it might make the mask constants more
    2064              :      expensive.  So, compare the costs.  */
    2065         3848 :   if (compare_tree_int (minval, 0) > 0 && compare_tree_int (maxval, prec) < 0)
    2066              :     {
    2067         2092 :       int cost_diff;
    2068         2092 :       HOST_WIDE_INT m = tree_to_uhwi (minval);
    2069         2092 :       rtx reg = gen_raw_REG (word_mode, 10000);
    2070         2092 :       bool speed_p = optimize_insn_for_speed_p ();
    2071         2092 :       cost_diff = set_src_cost (gen_rtx_PLUS (word_mode, reg,
    2072              :                                               GEN_INT (-m)),
    2073              :                                 word_mode, speed_p);
    2074         6634 :       for (i = 0; i < count; i++)
    2075              :         {
    2076         2450 :           rtx r = immed_wide_int_const (test[i].mask, word_mode);
    2077         2450 :           cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
    2078              :                                      word_mode, speed_p);
    2079         2450 :           r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
    2080         2450 :           cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
    2081              :                                      word_mode, speed_p);
    2082              :         }
    2083         2092 :       if (cost_diff > 0)
    2084              :         {
    2085         4162 :           for (i = 0; i < count; i++)
    2086         2226 :             test[i].mask = wi::lshift (test[i].mask, m);
    2087         1936 :           minval = build_zero_cst (TREE_TYPE (minval));
    2088              :         }
    2089              :     }
    2090              : 
    2091              :   /* Now build the test-and-branch code.  */
    2092              : 
    2093         3848 :   gsi = gsi_last_bb (m_case_bb);
    2094              : 
    2095              :   /* idx = (unsigned)x - minval.  */
    2096         3848 :   idx = fold_convert_loc (loc, unsigned_index_type, index_expr);
    2097         3848 :   idx = fold_build2_loc (loc, MINUS_EXPR, unsigned_index_type, idx,
    2098              :                          fold_convert_loc (loc, unsigned_index_type, minval));
    2099         3848 :   idx = force_gimple_operand_gsi (&gsi, idx,
    2100              :                                   /*simple=*/true, NULL_TREE,
    2101              :                                   /*before=*/true, GSI_SAME_STMT);
    2102              : 
    2103         3848 :   profile_probability subtree_prob = m_subtree_prob;
    2104         3848 :   profile_probability default_prob = m_default_prob;
    2105         3848 :   if (!default_prob.initialized_p ())
    2106         2504 :     default_prob = m_subtree_prob.invert ();
    2107              : 
    2108         3848 :   if (m_handles_entire_switch && entry_test_needed)
    2109              :     {
    2110         2462 :       tree range = int_const_binop (MINUS_EXPR, maxval, minval);
    2111              :       /* if (idx > range) goto default */
    2112         2462 :       range
    2113         2462 :         = force_gimple_operand_gsi (&gsi,
    2114              :                                     fold_convert (unsigned_index_type, range),
    2115              :                                     /*simple=*/true, NULL_TREE,
    2116              :                                     /*before=*/true, GSI_SAME_STMT);
    2117         2462 :       tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
    2118         2462 :       default_prob = default_prob / 2;
    2119         2462 :       basic_block new_bb
    2120         2462 :         = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
    2121              :                                          default_prob, loc);
    2122         4924 :       gsi = gsi_last_bb (new_bb);
    2123              :     }
    2124              : 
    2125         3848 :   tmp = fold_build2_loc (loc, LSHIFT_EXPR, word_type_node, word_mode_one,
    2126              :                          fold_convert_loc (loc, word_type_node, idx));
    2127              : 
    2128              :   /* csui = (1 << (word_mode) idx) */
    2129         3848 :   if (count > 1)
    2130              :     {
    2131          880 :       csui = make_ssa_name (word_type_node);
    2132          880 :       tmp = force_gimple_operand_gsi (&gsi, tmp,
    2133              :                                      /*simple=*/false, NULL_TREE,
    2134              :                                      /*before=*/true, GSI_SAME_STMT);
    2135          880 :       shift_stmt = gimple_build_assign (csui, tmp);
    2136          880 :       gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
    2137          880 :       update_stmt (shift_stmt);
    2138              :     }
    2139              :   else
    2140              :     csui = tmp;
    2141              : 
    2142              :   /* for each unique set of cases:
    2143              :        if (const & csui) goto target  */
    2144         9084 :   for (k = 0; k < count; k++)
    2145              :     {
    2146         5236 :       profile_probability prob = test[k].prob / (subtree_prob + default_prob);
    2147         5236 :       subtree_prob -= test[k].prob;
    2148         5236 :       tmp = wide_int_to_tree (word_type_node, test[k].mask);
    2149         5236 :       tmp = fold_build2_loc (loc, BIT_AND_EXPR, word_type_node, csui, tmp);
    2150         5236 :       tmp = fold_build2_loc (loc, NE_EXPR, boolean_type_node,
    2151              :                              tmp, word_mode_zero);
    2152         5236 :       tmp = force_gimple_operand_gsi (&gsi, tmp,
    2153              :                                       /*simple=*/true, NULL_TREE,
    2154              :                                       /*before=*/true, GSI_SAME_STMT);
    2155         5236 :       basic_block new_bb
    2156         5236 :         = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb,
    2157              :                                          prob, loc);
    2158        10472 :       gsi = gsi_last_bb (new_bb);
    2159              :     }
    2160              : 
    2161              :   /* We should have removed all edges now.  */
    2162         3848 :   gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
    2163              : 
    2164              :   /* If nothing matched, go to the default label.  */
    2165         3848 :   edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
    2166         3848 :   e->probability = profile_probability::always ();
    2167        15392 : }
    2168              : 
    2169              : /* Split the basic block at the statement pointed to by GSIP, and insert
    2170              :    a branch to the target basic block of E_TRUE conditional on tree
    2171              :    expression COND.
    2172              : 
    2173              :    It is assumed that there is already an edge from the to-be-split
    2174              :    basic block to E_TRUE->dest block.  This edge is removed, and the
    2175              :    profile information on the edge is re-used for the new conditional
    2176              :    jump.
    2177              : 
    2178              :    The CFG is updated.  The dominator tree will not be valid after
    2179              :    this transformation, but the immediate dominators are updated if
    2180              :    UPDATE_DOMINATORS is true.
    2181              : 
    2182              :    Returns the newly created basic block.  */
    2183              : 
    2184              : basic_block
    2185         7698 : bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
    2186              :                                                  tree cond, basic_block case_bb,
    2187              :                                                  profile_probability prob,
    2188              :                                                  location_t loc)
    2189              : {
    2190         7698 :   tree tmp;
    2191         7698 :   gcond *cond_stmt;
    2192         7698 :   edge e_false;
    2193         7698 :   basic_block new_bb, split_bb = gsi_bb (*gsip);
    2194              : 
    2195         7698 :   edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
    2196         7698 :   e_true->probability = prob;
    2197         7698 :   gcc_assert (e_true->src == split_bb);
    2198              : 
    2199         7698 :   tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
    2200              :                                   /*before=*/true, GSI_SAME_STMT);
    2201         7698 :   cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
    2202         7698 :   gimple_set_location (cond_stmt, loc);
    2203         7698 :   gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
    2204              : 
    2205         7698 :   e_false = split_block (split_bb, cond_stmt);
    2206         7698 :   new_bb = e_false->dest;
    2207         7698 :   redirect_edge_pred (e_true, split_bb);
    2208              : 
    2209         7698 :   e_false->flags &= ~EDGE_FALLTHRU;
    2210         7698 :   e_false->flags |= EDGE_FALSE_VALUE;
    2211         7698 :   e_false->probability = e_true->probability.invert ();
    2212         7698 :   new_bb->count = e_false->count ();
    2213              : 
    2214         7698 :   return new_bb;
    2215              : }
    2216              : 
    2217              : /* Compute the number of case labels that correspond to each outgoing edge of
    2218              :    switch statement.  Record this information in the aux field of the edge.
    2219              :    Return the approx max number of cases per edge.  */
    2220              : 
    2221              : int
    2222        45907 : switch_decision_tree::compute_cases_per_edge ()
    2223              : {
    2224        45907 :   int max_c = 0;
    2225        45907 :   reset_out_edges_aux (m_switch);
    2226        45907 :   int ncases = gimple_switch_num_labels (m_switch);
    2227       299172 :   for (int i = ncases - 1; i >= 1; --i)
    2228              :     {
    2229       253265 :       edge case_edge = gimple_switch_edge (cfun, m_switch, i);
    2230       253265 :       case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
    2231              :       /* For a range case add one extra. That's enough for the bit
    2232              :          cluster heuristic.  */
    2233       253265 :       if ((intptr_t)case_edge->aux > max_c)
    2234       141990 :         max_c = (intptr_t)case_edge->aux +
    2235        70995 :                 !!CASE_HIGH (gimple_switch_label (m_switch, i));
    2236              :     }
    2237        45907 :   return max_c;
    2238              : }
    2239              : 
    2240              : /* Analyze switch statement and return true when the statement is expanded
    2241              :    as decision tree.  */
    2242              : 
    2243              : bool
    2244        45907 : switch_decision_tree::analyze_switch_statement ()
    2245              : {
    2246        45907 :   unsigned l = gimple_switch_num_labels (m_switch);
    2247        45907 :   basic_block bb = gimple_bb (m_switch);
    2248        45907 :   auto_vec<cluster *> clusters;
    2249        45907 :   clusters.create (l - 1);
    2250              : 
    2251        45907 :   basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
    2252        45907 :   m_case_bbs.reserve (l);
    2253        45907 :   m_case_bbs.quick_push (default_bb);
    2254              : 
    2255        45907 :   int max_c = compute_cases_per_edge ();
    2256              : 
    2257       345079 :   for (unsigned i = 1; i < l; i++)
    2258              :     {
    2259       253265 :       tree elt = gimple_switch_label (m_switch, i);
    2260       253265 :       tree lab = CASE_LABEL (elt);
    2261       253265 :       basic_block case_bb = label_to_block (cfun, lab);
    2262       253265 :       edge case_edge = find_edge (bb, case_bb);
    2263       253265 :       tree low = CASE_LOW (elt);
    2264       253265 :       tree high = CASE_HIGH (elt);
    2265              : 
    2266       253265 :       profile_probability p
    2267       253265 :         = case_edge->probability / ((intptr_t) (case_edge->aux));
    2268       253265 :       clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
    2269       253265 :                                                p));
    2270       253265 :       m_case_bbs.quick_push (case_edge->dest);
    2271              :     }
    2272              : 
    2273        45907 :   reset_out_edges_aux (m_switch);
    2274              : 
    2275              :   /* Find bit-test clusters.  */
    2276        45907 :   vec<cluster *> output = bit_test_cluster::find_bit_tests (clusters, max_c);
    2277              : 
    2278              :   /* Find jump table clusters.  We are looking for these in the sequences of
    2279              :      simple clusters which we didn't manage to convert into bit-test
    2280              :      clusters.  */
    2281        45907 :   vec<cluster *> output2;
    2282        45907 :   auto_vec<cluster *> tmp;
    2283        45907 :   output2.create (1);
    2284        45907 :   tmp.create (1);
    2285              : 
    2286       332049 :   for (unsigned i = 0; i < output.length (); i++)
    2287              :     {
    2288       240235 :       cluster *c = output[i];
    2289       240235 :       if (c->get_type () != SIMPLE_CASE)
    2290              :         {
    2291         3848 :           if (!tmp.is_empty ())
    2292              :             {
    2293          749 :               vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
    2294          749 :               output2.safe_splice (n);
    2295          749 :               n.release ();
    2296          749 :               tmp.truncate (0);
    2297              :             }
    2298         3848 :           output2.safe_push (c);
    2299              :         }
    2300              :       else
    2301       236387 :         tmp.safe_push (c);
    2302              :     }
    2303              : 
    2304              :   /* We still can have a temporary vector to test.  */
    2305        45907 :   if (!tmp.is_empty ())
    2306              :     {
    2307        43014 :       vec<cluster *> n = jump_table_cluster::find_jump_tables (tmp);
    2308        43014 :       output2.safe_splice (n);
    2309        43014 :       n.release ();
    2310              :     }
    2311              : 
    2312        45907 :   if (dump_file)
    2313              :     {
    2314           24 :       fprintf (dump_file, ";; GIMPLE switch case clusters: ");
    2315          127 :       for (unsigned i = 0; i < output2.length (); i++)
    2316           79 :         output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
    2317           24 :       fprintf (dump_file, "\n");
    2318              :     }
    2319              : 
    2320        45907 :   output.release ();
    2321              : 
    2322        45907 :   bool expanded = try_switch_expansion (output2);
    2323        45907 :   release_clusters (output2);
    2324        45907 :   return expanded;
    2325        45907 : }
    2326              : 
    2327              : /* Attempt to expand CLUSTERS as a decision tree.  Return true when
    2328              :    expanded.  */
    2329              : 
    2330              : bool
    2331        45907 : switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
    2332              : {
    2333        45907 :   tree index_expr = gimple_switch_index (m_switch);
    2334        45907 :   tree index_type = TREE_TYPE (index_expr);
    2335        45907 :   basic_block bb = gimple_bb (m_switch);
    2336              : 
    2337        45907 :   if (gimple_switch_num_labels (m_switch) == 1
    2338        45907 :       || range_check_type (index_type) == NULL_TREE)
    2339              :     return false;
    2340              : 
    2341              :   /* Find the default case target label.  */
    2342        45828 :   edge default_edge = gimple_switch_default_edge (cfun, m_switch);
    2343        45828 :   m_default_bb = default_edge->dest;
    2344              : 
    2345              :   /* Do the insertion of a case label into m_case_list.  The labels are
    2346              :      fed to us in descending order from the sorted vector of case labels used
    2347              :      in the tree part of the middle end.  So the list we construct is
    2348              :      sorted in ascending order.  */
    2349              : 
    2350       262477 :   for (int i = clusters.length () - 1; i >= 0; i--)
    2351              :     {
    2352       170821 :       case_tree_node *r = m_case_list;
    2353       170821 :       m_case_list = m_case_node_pool.allocate ();
    2354       170821 :       m_case_list->m_right = r;
    2355       170821 :       m_case_list->m_c = clusters[i];
    2356              :     }
    2357              : 
    2358        45828 :   record_phi_operand_mapping ();
    2359              : 
    2360              :   /* Split basic block that contains the gswitch statement.  */
    2361        45828 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2362        45828 :   edge e;
    2363        45828 :   if (gsi_end_p (gsi))
    2364            0 :     e = split_block_after_labels (bb);
    2365              :   else
    2366              :     {
    2367        45828 :       gsi_prev (&gsi);
    2368        45828 :       e = split_block (bb, gsi_stmt (gsi));
    2369              :     }
    2370        45828 :   bb = split_edge (e);
    2371              : 
    2372              :   /* Create new basic blocks for non-case clusters where specific expansion
    2373              :      needs to happen.  */
    2374       262477 :   for (unsigned i = 0; i < clusters.length (); i++)
    2375       170821 :     if (clusters[i]->get_type () != SIMPLE_CASE)
    2376              :       {
    2377        10733 :         clusters[i]->m_case_bb = create_empty_bb (bb);
    2378        10733 :         clusters[i]->m_case_bb->count = bb->count;
    2379        10733 :         clusters[i]->m_case_bb->loop_father = bb->loop_father;
    2380              :       }
    2381              : 
    2382              :   /* Do not do an extra work for a single cluster.  */
    2383        45828 :   if (clusters.length () == 1
    2384        55894 :       && clusters[0]->get_type () != SIMPLE_CASE)
    2385              :     {
    2386         8842 :       cluster *c = clusters[0];
    2387         8842 :       c->emit (index_expr, index_type,
    2388              :                gimple_switch_default_label (m_switch), m_default_bb,
    2389         8842 :                gimple_location (m_switch));
    2390         8842 :       redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
    2391              :     }
    2392              :   else
    2393              :     {
    2394        36986 :       emit (bb, index_expr, default_edge->probability, index_type);
    2395              : 
    2396              :       /* Emit cluster-specific switch handling.  */
    2397       235951 :       for (unsigned i = 0; i < clusters.length (); i++)
    2398       161979 :         if (clusters[i]->get_type () != SIMPLE_CASE)
    2399              :           {
    2400         1891 :             edge e = single_pred_edge (clusters[i]->m_case_bb);
    2401         1891 :             e->dest->count = e->src->count.apply_probability (e->probability);
    2402         3782 :             clusters[i]->emit (index_expr, index_type,
    2403              :                                gimple_switch_default_label (m_switch),
    2404         1891 :                                m_default_bb, gimple_location (m_switch));
    2405              :           }
    2406              :     }
    2407              : 
    2408        45828 :   fix_phi_operands_for_edges ();
    2409              : 
    2410        45828 :   return true;
    2411              : }
    2412              : 
    2413              : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
    2414              :    and used in a label basic block.  */
    2415              : 
    2416              : void
    2417        45828 : switch_decision_tree::record_phi_operand_mapping ()
    2418              : {
    2419        45828 :   basic_block switch_bb = gimple_bb (m_switch);
    2420              :   /* Record all PHI nodes that have to be fixed after conversion.  */
    2421       344743 :   for (unsigned i = 0; i < m_case_bbs.length (); i++)
    2422              :     {
    2423       298915 :       gphi_iterator gsi;
    2424       298915 :       basic_block bb = m_case_bbs[i];
    2425       368002 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2426              :         {
    2427        69087 :           gphi *phi = gsi.phi ();
    2428              : 
    2429       305439 :           for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
    2430              :             {
    2431       236352 :               basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
    2432       236352 :               if (phi_src_bb == switch_bb)
    2433              :                 {
    2434        69087 :                   tree def = gimple_phi_arg_def (phi, i);
    2435        69087 :                   tree result = gimple_phi_result (phi);
    2436        69087 :                   m_phi_mapping.put (result, def);
    2437        69087 :                   break;
    2438              :                 }
    2439              :             }
    2440              :         }
    2441              :     }
    2442        45828 : }
    2443              : 
    2444              : /* Append new operands to PHI statements that were introduced due to
    2445              :    addition of new edges to case labels.  */
    2446              : 
    2447              : void
    2448        45828 : switch_decision_tree::fix_phi_operands_for_edges ()
    2449              : {
    2450        45828 :   gphi_iterator gsi;
    2451              : 
    2452       344743 :   for (unsigned i = 0; i < m_case_bbs.length (); i++)
    2453              :     {
    2454       298915 :       basic_block bb = m_case_bbs[i];
    2455       368002 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2456              :         {
    2457        69087 :           gphi *phi = gsi.phi ();
    2458       665478 :           for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
    2459              :             {
    2460       527304 :               tree def = gimple_phi_arg_def (phi, j);
    2461       527304 :               if (def == NULL_TREE)
    2462              :                 {
    2463        73410 :                   edge e = gimple_phi_arg_edge (phi, j);
    2464        73410 :                   tree *definition
    2465        73410 :                     = m_phi_mapping.get (gimple_phi_result (phi));
    2466        73410 :                   gcc_assert (definition);
    2467        73410 :                   add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
    2468              :                 }
    2469              :             }
    2470              :         }
    2471              :     }
    2472        45828 : }
    2473              : 
    2474              : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
    2475              :    one of the labels in CASE_LIST or to the DEFAULT_LABEL.
    2476              : 
    2477              :    We generate a binary decision tree to select the appropriate target
    2478              :    code.  */
    2479              : 
    2480              : void
    2481        36986 : switch_decision_tree::emit (basic_block bb, tree index_expr,
    2482              :                             profile_probability default_prob, tree index_type)
    2483              : {
    2484        36986 :   balance_case_nodes (&m_case_list, NULL);
    2485              : 
    2486        36986 :   if (dump_file)
    2487           15 :     dump_function_to_file (current_function_decl, dump_file, dump_flags);
    2488        36986 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2489              :     {
    2490            0 :       int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
    2491            0 :       fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
    2492            0 :       gcc_assert (m_case_list != NULL);
    2493            0 :       dump_case_nodes (dump_file, m_case_list, indent_step, 0);
    2494              :     }
    2495              : 
    2496        73972 :   bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
    2497        36986 :                         gimple_location (m_switch));
    2498              : 
    2499        36986 :   if (bb)
    2500        35131 :     emit_jump (bb, m_default_bb);
    2501              : 
    2502              :   /* Remove all edges and do just an edge that will reach default_bb.  */
    2503        36986 :   bb = gimple_bb (m_switch);
    2504        36986 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2505        36986 :   gsi_remove (&gsi, true);
    2506              : 
    2507        36986 :   delete_basic_block (bb);
    2508        36986 : }
    2509              : 
    2510              : /* Take an ordered list of case nodes
    2511              :    and transform them into a near optimal binary tree,
    2512              :    on the assumption that any target code selection value is as
    2513              :    likely as any other.
    2514              : 
    2515              :    The transformation is performed by splitting the ordered
    2516              :    list into two equal sections plus a pivot.  The parts are
    2517              :    then attached to the pivot as left and right branches.  Each
    2518              :    branch is then transformed recursively.  */
    2519              : 
    2520              : void
    2521       202114 : switch_decision_tree::balance_case_nodes (case_tree_node **head,
    2522              :                                           case_tree_node *parent)
    2523              : {
    2524       202114 :   case_tree_node *np;
    2525              : 
    2526       202114 :   np = *head;
    2527       202114 :   if (np)
    2528              :     {
    2529       131262 :       int i = 0;
    2530       131262 :       case_tree_node **npp;
    2531       131262 :       case_tree_node *left;
    2532       131262 :       profile_probability prob = profile_probability::never ();
    2533              : 
    2534              :       /* Count the number of entries on branch.  */
    2535              : 
    2536      2359544 :       while (np)
    2537              :         {
    2538      2228282 :           i++;
    2539      2228282 :           prob += np->m_c->m_prob;
    2540      2228282 :           np = np->m_right;
    2541              :         }
    2542              : 
    2543       131262 :       if (i > 2)
    2544              :         {
    2545              :           /* Split this list if it is long enough for that to help.  */
    2546        82564 :           npp = head;
    2547        82564 :           left = *npp;
    2548        82564 :           profile_probability pivot_prob = prob / 2;
    2549              : 
    2550              :           /* Find the place in the list that bisects the list's total cost
    2551              :              by probability.  */
    2552      4157970 :           while (1)
    2553              :             {
    2554              :               /* Skip nodes while their probability does not reach
    2555              :                  that amount.  */
    2556      2120267 :               prob -= (*npp)->m_c->m_prob;
    2557      2120267 :               if ((prob.initialized_p () && prob < pivot_prob)
    2558      2151411 :                   || ! (*npp)->m_right)
    2559              :                 break;
    2560      2037703 :               npp = &(*npp)->m_right;
    2561              :             }
    2562              : 
    2563        82564 :           np = *npp;
    2564        82564 :           *npp = 0;
    2565        82564 :           *head = np;
    2566        82564 :           np->m_parent = parent;
    2567        82564 :           np->m_left = left == np ? NULL : left;
    2568              : 
    2569              :           /* Optimize each of the two split parts.  */
    2570        82564 :           balance_case_nodes (&np->m_left, np);
    2571        82564 :           balance_case_nodes (&np->m_right, np);
    2572        82564 :           np->m_c->m_subtree_prob = np->m_c->m_prob;
    2573        82564 :           if (np->m_left)
    2574        82084 :             np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
    2575        82564 :           if (np->m_right)
    2576        12192 :             np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
    2577              :         }
    2578              :       else
    2579              :         {
    2580              :           /* Else leave this branch as one level,
    2581              :              but fill in `parent' fields.  */
    2582        48698 :           np = *head;
    2583        48698 :           np->m_parent = parent;
    2584        48698 :           np->m_c->m_subtree_prob = np->m_c->m_prob;
    2585        79415 :           for (; np->m_right; np = np->m_right)
    2586              :             {
    2587        30717 :               np->m_right->m_parent = np;
    2588        30717 :               (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
    2589              :             }
    2590              :         }
    2591              :     }
    2592       202114 : }
    2593              : 
    2594              : /* Dump ROOT, a list or tree of case nodes, to file.  */
    2595              : 
    2596              : void
    2597            0 : switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
    2598              :                                        int indent_step, int indent_level)
    2599              : {
    2600            0 :   if (root == 0)
    2601            0 :     return;
    2602            0 :   indent_level++;
    2603              : 
    2604            0 :   dump_case_nodes (f, root->m_left, indent_step, indent_level);
    2605              : 
    2606            0 :   fputs (";; ", f);
    2607            0 :   fprintf (f, "%*s", indent_step * indent_level, "");
    2608            0 :   root->m_c->dump (f);
    2609            0 :   root->m_c->m_prob.dump (f);
    2610            0 :   fputs (" subtree: ", f);
    2611            0 :   root->m_c->m_subtree_prob.dump (f);
    2612            0 :   fputs (")\n", f);
    2613              : 
    2614            0 :   dump_case_nodes (f, root->m_right, indent_step, indent_level);
    2615              : }
    2616              : 
    2617              : 
    2618              : /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
    2619              : 
    2620              : void
    2621        64539 : switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
    2622              : {
    2623        64539 :   edge e = single_succ_edge (bb);
    2624        64539 :   redirect_edge_succ (e, case_bb);
    2625        64539 : }
    2626              : 
    2627              : /* Generate code to compare OP0 with OP1 so that the condition codes are
    2628              :    set and to jump to LABEL_BB if the condition is true.
    2629              :    COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
    2630              :    PROB is the probability of jumping to LABEL_BB.  */
    2631              : 
    2632              : basic_block
    2633       105994 : switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
    2634              :                                                tree op1, tree_code comparison,
    2635              :                                                basic_block label_bb,
    2636              :                                                profile_probability prob,
    2637              :                                                location_t loc)
    2638              : {
    2639              :   // TODO: it's once called with lhs != index.
    2640       105994 :   op1 = fold_convert (TREE_TYPE (op0), op1);
    2641              : 
    2642       105994 :   gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
    2643       105994 :   gimple_set_location (cond, loc);
    2644       105994 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2645       105994 :   gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
    2646              : 
    2647       105994 :   gcc_assert (single_succ_p (bb));
    2648              : 
    2649              :   /* Make a new basic block where false branch will take place.  */
    2650       105994 :   edge false_edge = split_block (bb, cond);
    2651       105994 :   false_edge->flags = EDGE_FALSE_VALUE;
    2652       105994 :   false_edge->probability = prob.invert ();
    2653       105994 :   false_edge->dest->count = bb->count.apply_probability (prob.invert ());
    2654              : 
    2655       105994 :   edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
    2656       105994 :   true_edge->probability = prob;
    2657              : 
    2658       105994 :   return false_edge->dest;
    2659              : }
    2660              : 
    2661              : /* Generate code to jump to LABEL if OP0 and OP1 are equal.
    2662              :    PROB is the probability of jumping to LABEL_BB.
    2663              :    BB is a basic block where the new condition will be placed.  */
    2664              : 
    2665              : basic_block
    2666       136608 : switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
    2667              :                                         basic_block label_bb,
    2668              :                                         profile_probability prob,
    2669              :                                         location_t loc)
    2670              : {
    2671       136608 :   op1 = fold_convert (TREE_TYPE (op0), op1);
    2672              : 
    2673       136608 :   gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
    2674       136608 :   gimple_set_location (cond, loc);
    2675       136608 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2676       136608 :   gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
    2677              : 
    2678       136608 :   gcc_assert (single_succ_p (bb));
    2679              : 
    2680              :   /* Make a new basic block where false branch will take place.  */
    2681       136608 :   edge false_edge = split_block (bb, cond);
    2682       136608 :   false_edge->flags = EDGE_FALSE_VALUE;
    2683       136608 :   false_edge->probability = prob.invert ();
    2684       136608 :   false_edge->dest->count = bb->count.apply_probability (prob.invert ());
    2685              : 
    2686       136608 :   edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
    2687       136608 :   true_edge->probability = prob;
    2688              : 
    2689       136608 :   return false_edge->dest;
    2690              : }
    2691              : 
    2692              : /* Emit step-by-step code to select a case for the value of INDEX.
    2693              :    The thus generated decision tree follows the form of the
    2694              :    case-node binary tree NODE, whose nodes represent test conditions.
    2695              :    DEFAULT_PROB is probability of cases leading to default BB.
    2696              :    INDEX_TYPE is the type of the index of the switch.  */
    2697              : 
    2698              : basic_block
    2699        64539 : switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
    2700              :                                        case_tree_node *node,
    2701              :                                        profile_probability default_prob,
    2702              :                                        tree index_type, location_t loc)
    2703              : {
    2704       145162 :   profile_probability p;
    2705              : 
    2706              :   /* If node is null, we are done.  */
    2707       145162 :   if (node == NULL)
    2708              :     return bb;
    2709              : 
    2710              :   /* Single value case.  */
    2711       123387 :   if (node->m_c->is_single_value_p ())
    2712              :     {
    2713              :       /* Node is single valued.  First see if the index expression matches
    2714              :          this node and then check our children, if any.  */
    2715        98016 :       p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
    2716        98016 :       bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
    2717              :                              node->m_c->m_case_bb, p, loc);
    2718              :       /* Since this case is taken at this point, reduce its weight from
    2719              :          subtree_weight.  */
    2720        98016 :       node->m_c->m_subtree_prob -= node->m_c->m_prob;
    2721              : 
    2722        98016 :       if (node->m_left != NULL && node->m_right != NULL)
    2723              :         {
    2724              :           /* 1) the node has both children
    2725              : 
    2726              :              If both children are single-valued cases with no
    2727              :              children, finish up all the work.  This way, we can save
    2728              :              one ordered comparison.  */
    2729              : 
    2730        11041 :           if (!node->m_left->has_child ()
    2731         6959 :               && node->m_left->m_c->is_single_value_p ()
    2732         5537 :               && !node->m_right->has_child ()
    2733         5377 :               && node->m_right->m_c->is_single_value_p ())
    2734              :             {
    2735        10572 :               p = (node->m_right->m_c->m_prob
    2736         5286 :                    / (node->m_c->m_subtree_prob + default_prob));
    2737         5286 :               bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
    2738              :                                      node->m_right->m_c->m_case_bb, p, loc);
    2739         5286 :               node->m_c->m_subtree_prob -= node->m_right->m_c->m_prob;
    2740              : 
    2741        10572 :               p = (node->m_left->m_c->m_prob
    2742         5286 :                    / (node->m_c->m_subtree_prob + default_prob));
    2743         5286 :               bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
    2744              :                                      node->m_left->m_c->m_case_bb, p, loc);
    2745              :             }
    2746              :           else
    2747              :             {
    2748              :               /* Branch to a label where we will handle it later.  */
    2749         5755 :               basic_block test_bb = split_edge (single_succ_edge (bb));
    2750         5755 :               redirect_edge_succ (single_pred_edge (test_bb),
    2751         5755 :                                   single_succ_edge (bb)->dest);
    2752              : 
    2753         5755 :               p = ((node->m_right->m_c->m_subtree_prob + default_prob / 2)
    2754        11510 :                    / (node->m_c->m_subtree_prob + default_prob));
    2755         5755 :               test_bb->count = bb->count.apply_probability (p);
    2756         5755 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2757              :                                             GT_EXPR, test_bb, p, loc);
    2758         5755 :               default_prob /= 2;
    2759              : 
    2760              :               /* Handle the left-hand subtree.  */
    2761         5755 :               bb = emit_case_nodes (bb, index, node->m_left,
    2762              :                                     default_prob, index_type, loc);
    2763              : 
    2764              :               /* If the left-hand subtree fell through,
    2765              :                  don't let it fall into the right-hand subtree.  */
    2766         5755 :               if (bb && m_default_bb)
    2767         4338 :                 emit_jump (bb, m_default_bb);
    2768              : 
    2769         5755 :               bb = emit_case_nodes (test_bb, index, node->m_right,
    2770              :                                     default_prob, index_type, loc);
    2771              :             }
    2772              :         }
    2773        86975 :       else if (node->m_left == NULL && node->m_right != NULL)
    2774              :         {
    2775              :           /* 2) the node has only right child.  */
    2776              : 
    2777              :           /* Here we have a right child but no left so we issue a conditional
    2778              :              branch to default and process the right child.
    2779              : 
    2780              :              Omit the conditional branch to default if the right child
    2781              :              does not have any children and is single valued; it would
    2782              :              cost too much space to save so little time.  */
    2783              : 
    2784        29126 :           if (node->m_right->has_child ()
    2785        28819 :               || !node->m_right->m_c->is_single_value_p ())
    2786              :             {
    2787         3318 :               p = ((default_prob / 2)
    2788         1106 :                    / (node->m_c->m_subtree_prob + default_prob));
    2789         1106 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
    2790              :                                             LT_EXPR, m_default_bb, p, loc);
    2791         1106 :               default_prob /= 2;
    2792              : 
    2793         1106 :               bb = emit_case_nodes (bb, index, node->m_right, default_prob,
    2794              :                                     index_type, loc);
    2795              :             }
    2796              :           else
    2797              :             {
    2798              :               /* We cannot process node->right normally
    2799              :                  since we haven't ruled out the numbers less than
    2800              :                  this node's value.  So handle node->right explicitly.  */
    2801        56040 :               p = (node->m_right->m_c->m_subtree_prob
    2802        28020 :                    / (node->m_c->m_subtree_prob + default_prob));
    2803        28020 :               bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
    2804              :                                      node->m_right->m_c->m_case_bb, p, loc);
    2805              :             }
    2806              :         }
    2807        57849 :       else if (node->m_left != NULL && node->m_right == NULL)
    2808              :         {
    2809              :           /* 3) just one subtree, on the left.  Similar case as previous.  */
    2810              : 
    2811        51964 :           if (node->m_left->has_child ()
    2812            0 :               || !node->m_left->m_c->is_single_value_p ())
    2813              :             {
    2814       155892 :               p = ((default_prob / 2)
    2815        51964 :                    / (node->m_c->m_subtree_prob + default_prob));
    2816        51964 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2817              :                                             GT_EXPR, m_default_bb, p, loc);
    2818        51964 :               default_prob /= 2;
    2819              : 
    2820        51964 :               bb = emit_case_nodes (bb, index, node->m_left, default_prob,
    2821              :                                     index_type, loc);
    2822              :             }
    2823              :           else
    2824              :             {
    2825              :               /* We cannot process node->left normally
    2826              :                  since we haven't ruled out the numbers less than
    2827              :                  this node's value.  So handle node->left explicitly.  */
    2828            0 :               p = (node->m_left->m_c->m_subtree_prob
    2829            0 :                    / (node->m_c->m_subtree_prob + default_prob));
    2830            0 :               bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
    2831              :                                      node->m_left->m_c->m_case_bb, p, loc);
    2832              :             }
    2833              :         }
    2834              :     }
    2835              :   else
    2836              :     {
    2837              :       /* Node is a range.  These cases are very similar to those for a single
    2838              :          value, except that we do not start by testing whether this node
    2839              :          is the one to branch to.  */
    2840        29592 :       if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
    2841              :         {
    2842        21798 :           bool is_bt = node->m_c->get_type () == BIT_TEST;
    2843        21798 :           int parts = is_bt ? 3 : 2;
    2844              : 
    2845              :           /* Branch to a label where we will handle it later.  */
    2846        21798 :           basic_block test_bb = split_edge (single_succ_edge (bb));
    2847        21798 :           redirect_edge_succ (single_pred_edge (test_bb),
    2848        21798 :                               single_succ_edge (bb)->dest);
    2849              : 
    2850        21798 :           profile_probability right_prob = profile_probability::never ();
    2851        21798 :           if (node->m_right)
    2852         2742 :             right_prob = node->m_right->m_c->m_subtree_prob;
    2853        21798 :           p = ((right_prob + default_prob / parts)
    2854        43596 :                / (node->m_c->m_subtree_prob + default_prob));
    2855        21798 :           test_bb->count = bb->count.apply_probability (p);
    2856              : 
    2857        21798 :           bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2858              :                                         GT_EXPR, test_bb, p, loc);
    2859              : 
    2860        21798 :           default_prob /= parts;
    2861        21798 :           node->m_c->m_subtree_prob -= right_prob;
    2862        21798 :           if (is_bt)
    2863         1344 :             node->m_c->m_default_prob = default_prob;
    2864              : 
    2865              :            /* Value belongs to this node or to the left-hand subtree.  */
    2866        21798 :            p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
    2867        21798 :            bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
    2868              :                                          GE_EXPR, node->m_c->m_case_bb, p, loc);
    2869              : 
    2870              :            /* Handle the left-hand subtree.  */
    2871        21798 :            bb = emit_case_nodes (bb, index, node->m_left, default_prob,
    2872              :                                  index_type, loc);
    2873              : 
    2874              :            /* If the left-hand subtree fell through,
    2875              :               don't let it fall into the right-hand subtree.  */
    2876        21798 :            if (bb && m_default_bb)
    2877        21497 :              emit_jump (bb, m_default_bb);
    2878              : 
    2879        21798 :            bb = emit_case_nodes (test_bb, index, node->m_right, default_prob,
    2880              :                                  index_type, loc);
    2881              :         }
    2882              :       else
    2883              :         {
    2884              :           /* Node has no children so we check low and high bounds to remove
    2885              :              redundant tests.  Only one of the bounds can exist,
    2886              :              since otherwise this node is bounded--a case tested already.  */
    2887         3573 :           tree lhs, rhs;
    2888         3573 :           generate_range_test (bb, index, node->m_c->get_low (),
    2889         3573 :                                node->m_c->get_high (), &lhs, &rhs);
    2890         3573 :           p = default_prob / (node->m_c->m_subtree_prob + default_prob);
    2891              : 
    2892         3573 :           bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
    2893              :                                         m_default_bb, p, loc);
    2894              : 
    2895         3573 :           emit_jump (bb, node->m_c->m_case_bb);
    2896         3573 :           return NULL;
    2897              :         }
    2898              :     }
    2899              : 
    2900              :   return bb;
    2901              : }
    2902              : 
    2903              : /* The main function of the pass scans statements for switches and invokes
    2904              :    process_switch on them.  */
    2905              : 
    2906              : namespace {
    2907              : 
    2908              : const pass_data pass_data_convert_switch =
    2909              : {
    2910              :   GIMPLE_PASS, /* type */
    2911              :   "switchconv", /* name */
    2912              :   OPTGROUP_NONE, /* optinfo_flags */
    2913              :   TV_TREE_SWITCH_CONVERSION, /* tv_id */
    2914              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2915              :   0, /* properties_provided */
    2916              :   0, /* properties_destroyed */
    2917              :   0, /* todo_flags_start */
    2918              :   TODO_update_ssa, /* todo_flags_finish */
    2919              : };
    2920              : 
    2921              : class pass_convert_switch : public gimple_opt_pass
    2922              : {
    2923              : public:
    2924       297180 :   pass_convert_switch (gcc::context *ctxt)
    2925       594360 :     : gimple_opt_pass (pass_data_convert_switch, ctxt)
    2926              :   {}
    2927              : 
    2928              :   /* opt_pass methods: */
    2929      2524717 :   bool gate (function *) final override
    2930              :   {
    2931      2524717 :     return flag_tree_switch_conversion != 0;
    2932              :   }
    2933              :   unsigned int execute (function *) final override;
    2934              : 
    2935              : }; // class pass_convert_switch
    2936              : 
    2937              : unsigned int
    2938      2414927 : pass_convert_switch::execute (function *fun)
    2939              : {
    2940      2414927 :   basic_block bb;
    2941      2414927 :   bool cfg_altered = false;
    2942              : 
    2943     13289044 :   FOR_EACH_BB_FN (bb, fun)
    2944              :   {
    2945     32305152 :     if (gswitch *stmt = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
    2946              :       {
    2947        28100 :         if (dump_file)
    2948              :           {
    2949           43 :             expanded_location loc = expand_location (gimple_location (stmt));
    2950              : 
    2951           43 :             fprintf (dump_file, "beginning to process the following "
    2952              :                      "SWITCH statement (%s:%d) : ------- \n",
    2953              :                      loc.file, loc.line);
    2954           43 :             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2955           43 :             putc ('\n', dump_file);
    2956              :           }
    2957              : 
    2958        28100 :         switch_conversion sconv;
    2959        28100 :         sconv.expand (stmt);
    2960        28100 :         cfg_altered |= sconv.m_cfg_altered;
    2961        28100 :         if (!sconv.m_reason)
    2962              :           {
    2963          556 :             if (dump_file)
    2964              :               {
    2965           39 :                 fputs ("Switch converted\n", dump_file);
    2966           39 :                 fputs ("--------------------------------\n", dump_file);
    2967              :               }
    2968              : 
    2969              :             /* Make no effort to update the post-dominator tree.
    2970              :                It is actually not that hard for the transformations
    2971              :                we have performed, but it is not supported
    2972              :                by iterate_fix_dominators.  */
    2973          556 :             free_dominance_info (CDI_POST_DOMINATORS);
    2974              :           }
    2975              :         else
    2976              :           {
    2977        27544 :             if (dump_file)
    2978              :               {
    2979            4 :                 fputs ("Bailing out - ", dump_file);
    2980            4 :                 fputs (sconv.m_reason, dump_file);
    2981            4 :                 fputs ("\n--------------------------------\n", dump_file);
    2982              :               }
    2983              :           }
    2984        28100 :       }
    2985              :   }
    2986              : 
    2987      2414927 :   return cfg_altered ? TODO_cleanup_cfg : 0;;
    2988              : }
    2989              : 
    2990              : } // anon namespace
    2991              : 
    2992              : gimple_opt_pass *
    2993       297180 : make_pass_convert_switch (gcc::context *ctxt)
    2994              : {
    2995       297180 :   return new pass_convert_switch (ctxt);
    2996              : }
    2997              : 
    2998              : /* The main function of the pass scans statements for switches and invokes
    2999              :    process_switch on them.  */
    3000              : 
    3001              : namespace {
    3002              : 
    3003              : template <bool O0> class pass_lower_switch: public gimple_opt_pass
    3004              : {
    3005              : public:
    3006      1783080 :   pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
    3007              : 
    3008              :   static const pass_data data;
    3009              :   opt_pass *
    3010       297180 :   clone () final override
    3011              :   {
    3012       297180 :     return new pass_lower_switch<O0> (m_ctxt);
    3013              :   }
    3014              : 
    3015              :   bool
    3016      2583369 :   gate (function *) final override
    3017              :   {
    3018      2583369 :     return !O0 || !optimize;
    3019              :   }
    3020              : 
    3021              :   unsigned int execute (function *fun) final override;
    3022              : }; // class pass_lower_switch
    3023              : 
    3024              : template <bool O0>
    3025              : const pass_data pass_lower_switch<O0>::data = {
    3026              :   GIMPLE_PASS,                 /* type */
    3027              :   O0 ? "switchlower_O0" : "switchlower", /* name */
    3028              :   OPTGROUP_NONE, /* optinfo_flags */
    3029              :   TV_TREE_SWITCH_LOWERING, /* tv_id */
    3030              :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3031              :   0, /* properties_provided */
    3032              :   0, /* properties_destroyed */
    3033              :   0, /* todo_flags_start */
    3034              :   TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
    3035              : };
    3036              : 
    3037              : template <bool O0>
    3038              : unsigned int
    3039      1518008 : pass_lower_switch<O0>::execute (function *fun)
    3040              : {
    3041              :   basic_block bb;
    3042      1518008 :   bool expanded = false;
    3043              : 
    3044      1518008 :   auto_vec<gimple *> switch_statements;
    3045      1518008 :   switch_statements.create (1);
    3046              : 
    3047     15191660 :   FOR_EACH_BB_FN (bb, fun)
    3048              :     {
    3049     27126457 :       if (gswitch *swtch = safe_dyn_cast <gswitch *> (*gsi_last_bb (bb)))
    3050              :         {
    3051              :           if (!O0)
    3052        30209 :             group_case_labels_stmt (swtch);
    3053        45896 :           switch_statements.safe_push (swtch);
    3054              :         }
    3055              :     }
    3056              : 
    3057      1563904 :   for (unsigned i = 0; i < switch_statements.length (); i++)
    3058              :     {
    3059        45896 :       gimple *stmt = switch_statements[i];
    3060        45896 :       if (dump_file)
    3061              :         {
    3062           24 :           expanded_location loc = expand_location (gimple_location (stmt));
    3063              : 
    3064           24 :           fprintf (dump_file, "beginning to process the following "
    3065              :                    "SWITCH statement (%s:%d) : ------- \n",
    3066              :                    loc.file, loc.line);
    3067           24 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    3068           24 :           putc ('\n', dump_file);
    3069              :         }
    3070              : 
    3071        45896 :       gswitch *swtch = dyn_cast<gswitch *> (stmt);
    3072              :       if (swtch)
    3073              :         {
    3074        45896 :           switch_decision_tree dt (swtch);
    3075        45896 :           expanded |= dt.analyze_switch_statement ();
    3076        45896 :         }
    3077              :     }
    3078              : 
    3079      1518008 :   if (expanded)
    3080              :     {
    3081        32640 :       free_dominance_info (CDI_DOMINATORS);
    3082        32640 :       free_dominance_info (CDI_POST_DOMINATORS);
    3083        32640 :       mark_virtual_operands_for_renaming (cfun);
    3084              :     }
    3085              : 
    3086      1518008 :   return 0;
    3087      1518008 : }
    3088              : 
    3089              : } // anon namespace
    3090              : 
    3091              : gimple_opt_pass *
    3092       297180 : make_pass_lower_switch_O0 (gcc::context *ctxt)
    3093              : {
    3094       297180 :   return new pass_lower_switch<true> (ctxt);
    3095              : }
    3096              : gimple_opt_pass *
    3097       297180 : make_pass_lower_switch (gcc::context *ctxt)
    3098              : {
    3099       297180 :   return new pass_lower_switch<false> (ctxt);
    3100              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.