LCOV - code coverage report
Current view: top level - gcc - tree-switch-conversion.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1125 1158 97.2 %
Date: 2020-04-04 11:58:09 Functions: 54 57 94.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Lower GIMPLE_SWITCH expressions to something more efficient than
       2                 :            :    a jump table.
       3                 :            :    Copyright (C) 2006-2020 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                 :            : 
      54                 :            : /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
      55                 :            :    type in the GIMPLE type system that is language-independent?  */
      56                 :            : #include "langhooks.h"
      57                 :            : 
      58                 :            : #include "tree-switch-conversion.h"
      59                 :            : 
      60                 :            : using namespace tree_switch_conversion;
      61                 :            : 
      62                 :            : /* Constructor.  */
      63                 :            : 
      64                 :      16907 : switch_conversion::switch_conversion (): m_final_bb (NULL),
      65                 :            :   m_constructors (NULL), m_default_values (NULL),
      66                 :            :   m_arr_ref_first (NULL), m_arr_ref_last (NULL),
      67                 :      16907 :   m_reason (NULL), m_default_case_nonstandard (false), m_cfg_altered (false)
      68                 :            : {
      69                 :      16907 : }
      70                 :            : 
      71                 :            : /* Collection information about SWTCH statement.  */
      72                 :            : 
      73                 :            : void
      74                 :      16903 : switch_conversion::collect (gswitch *swtch)
      75                 :            : {
      76                 :      16903 :   unsigned int branch_num = gimple_switch_num_labels (swtch);
      77                 :      16903 :   tree min_case, max_case;
      78                 :      16903 :   unsigned int i;
      79                 :      16903 :   edge e, e_default, e_first;
      80                 :      16903 :   edge_iterator ei;
      81                 :            : 
      82                 :      16903 :   m_switch = swtch;
      83                 :            : 
      84                 :            :   /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
      85                 :            :      is a default label which is the first in the vector.
      86                 :            :      Collect the bits we can deduce from the CFG.  */
      87                 :      16903 :   m_index_expr = gimple_switch_index (swtch);
      88                 :      16903 :   m_switch_bb = gimple_bb (swtch);
      89                 :      16903 :   e_default = gimple_switch_default_edge (cfun, swtch);
      90                 :      16903 :   m_default_bb = e_default->dest;
      91                 :      16903 :   m_default_prob = e_default->probability;
      92                 :            : 
      93                 :            :   /* Get upper and lower bounds of case values, and the covered range.  */
      94                 :      16903 :   min_case = gimple_switch_label (swtch, 1);
      95                 :      16903 :   max_case = gimple_switch_label (swtch, branch_num - 1);
      96                 :            : 
      97                 :      16903 :   m_range_min = CASE_LOW (min_case);
      98                 :      16903 :   if (CASE_HIGH (max_case) != NULL_TREE)
      99                 :        914 :     m_range_max = CASE_HIGH (max_case);
     100                 :            :   else
     101                 :      15989 :     m_range_max = CASE_LOW (max_case);
     102                 :            : 
     103                 :      16903 :   m_contiguous_range = true;
     104                 :      16903 :   tree last = CASE_HIGH (min_case) ? CASE_HIGH (min_case) : m_range_min;
     105                 :      53233 :   for (i = 2; i < branch_num; i++)
     106                 :            :     {
     107                 :      43184 :       tree elt = gimple_switch_label (swtch, i);
     108                 :      43184 :       if (wi::to_wide (last) + 1 != wi::to_wide (CASE_LOW (elt)))
     109                 :            :         {
     110                 :       6854 :           m_contiguous_range = false;
     111                 :       6854 :           break;
     112                 :            :         }
     113                 :      89563 :       last = CASE_HIGH (elt) ? CASE_HIGH (elt) : CASE_LOW (elt);
     114                 :            :     }
     115                 :            : 
     116                 :      16903 :   if (m_contiguous_range)
     117                 :      10049 :     e_first = gimple_switch_edge (cfun, swtch, 1);
     118                 :            :   else
     119                 :            :     e_first = e_default;
     120                 :            : 
     121                 :            :   /* See if there is one common successor block for all branch
     122                 :            :      targets.  If it exists, record it in FINAL_BB.
     123                 :            :      Start with the destination of the first non-default case
     124                 :            :      if the range is contiguous and default case otherwise as
     125                 :            :      guess or its destination in case it is a forwarder block.  */
     126                 :      16903 :   if (! single_pred_p (e_first->dest))
     127                 :       3883 :     m_final_bb = e_first->dest;
     128                 :      13020 :   else if (single_succ_p (e_first->dest)
     129                 :      11541 :            && ! single_pred_p (single_succ (e_first->dest)))
     130                 :       8063 :     m_final_bb = single_succ (e_first->dest);
     131                 :            :   /* Require that all switch destinations are either that common
     132                 :            :      FINAL_BB or a forwarder to it, except for the default
     133                 :            :      case if contiguous range.  */
     134                 :      16903 :   if (m_final_bb)
     135                 :      59014 :     FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
     136                 :            :       {
     137                 :      51439 :         if (e->dest == m_final_bb)
     138                 :       7324 :           continue;
     139                 :            : 
     140                 :      44115 :         if (single_pred_p (e->dest)
     141                 :      42602 :             && single_succ_p (e->dest)
     142                 :      83001 :             && single_succ (e->dest) == m_final_bb)
     143                 :      37845 :           continue;
     144                 :            : 
     145                 :       6270 :         if (e == e_default && m_contiguous_range)
     146                 :            :           {
     147                 :       1899 :             m_default_case_nonstandard = true;
     148                 :       1899 :             continue;
     149                 :            :           }
     150                 :            : 
     151                 :       4371 :         m_final_bb = NULL;
     152                 :       4371 :         break;
     153                 :            :       }
     154                 :            : 
     155                 :      16903 :   m_range_size
     156                 :      16903 :     = int_const_binop (MINUS_EXPR, m_range_max, m_range_min);
     157                 :            : 
     158                 :            :   /* Get a count of the number of case labels.  Single-valued case labels
     159                 :            :      simply count as one, but a case range counts double, since it may
     160                 :            :      require two compares if it gets lowered as a branching tree.  */
     161                 :      16903 :   m_count = 0;
     162                 :      93474 :   for (i = 1; i < branch_num; i++)
     163                 :            :     {
     164                 :      76571 :       tree elt = gimple_switch_label (swtch, i);
     165                 :      76571 :       m_count++;
     166                 :      76571 :       if (CASE_HIGH (elt)
     167                 :      76571 :           && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
     168                 :       4489 :         m_count++;
     169                 :            :     }
     170                 :            : 
     171                 :            :   /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
     172                 :            :      block.  Assume a CFG cleanup would have already removed degenerate
     173                 :            :      switch statements, this allows us to just use EDGE_COUNT.  */
     174                 :      16903 :   m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
     175                 :      16903 : }
     176                 :            : 
     177                 :            : /* Checks whether the range given by individual case statements of the switch
     178                 :            :    switch statement isn't too big and whether the number of branches actually
     179                 :            :    satisfies the size of the new array.  */
     180                 :            : 
     181                 :            : bool
     182                 :       3947 : switch_conversion::check_range ()
     183                 :            : {
     184                 :       3947 :   gcc_assert (m_range_size);
     185                 :       3947 :   if (!tree_fits_uhwi_p (m_range_size))
     186                 :            :     {
     187                 :         16 :       m_reason = "index range way too large or otherwise unusable";
     188                 :         16 :       return false;
     189                 :            :     }
     190                 :            : 
     191                 :       3931 :   if (tree_to_uhwi (m_range_size)
     192                 :       3931 :       > ((unsigned) m_count * param_switch_conversion_branch_ratio))
     193                 :            :     {
     194                 :        118 :       m_reason = "the maximum range-branch ratio exceeded";
     195                 :        118 :       return false;
     196                 :            :     }
     197                 :            : 
     198                 :            :   return true;
     199                 :            : }
     200                 :            : 
     201                 :            : /* Checks whether all but the final BB basic blocks are empty.  */
     202                 :            : 
     203                 :            : bool
     204                 :       3813 : switch_conversion::check_all_empty_except_final ()
     205                 :            : {
     206                 :       3813 :   edge e, e_default = find_edge (m_switch_bb, m_default_bb);
     207                 :       3813 :   edge_iterator ei;
     208                 :            : 
     209                 :      14582 :   FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
     210                 :            :     {
     211                 :      14166 :       if (e->dest == m_final_bb)
     212                 :       3294 :         continue;
     213                 :            : 
     214                 :      10872 :       if (!empty_block_p (e->dest))
     215                 :            :         {
     216                 :       3900 :           if (m_contiguous_range && e == e_default)
     217                 :            :             {
     218                 :        503 :               m_default_case_nonstandard = true;
     219                 :        503 :               continue;
     220                 :            :             }
     221                 :            : 
     222                 :       3397 :           m_reason = "bad case - a non-final BB not empty";
     223                 :       3397 :           return false;
     224                 :            :         }
     225                 :            :     }
     226                 :            : 
     227                 :            :   return true;
     228                 :            : }
     229                 :            : 
     230                 :            : /* This function checks whether all required values in phi nodes in final_bb
     231                 :            :    are constants.  Required values are those that correspond to a basic block
     232                 :            :    which is a part of the examined switch statement.  It returns true if the
     233                 :            :    phi nodes are OK, otherwise false.  */
     234                 :            : 
     235                 :            : bool
     236                 :        416 : switch_conversion::check_final_bb ()
     237                 :            : {
     238                 :        416 :   gphi_iterator gsi;
     239                 :            : 
     240                 :        416 :   m_phi_count = 0;
     241                 :        828 :   for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
     242                 :            :     {
     243                 :        494 :       gphi *phi = gsi.phi ();
     244                 :        494 :       unsigned int i;
     245                 :            : 
     246                 :        988 :       if (virtual_operand_p (gimple_phi_result (phi)))
     247                 :         31 :         continue;
     248                 :            : 
     249                 :        463 :       m_phi_count++;
     250                 :            : 
     251                 :       7586 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
     252                 :            :         {
     253                 :       7205 :           basic_block bb = gimple_phi_arg_edge (phi, i)->src;
     254                 :            : 
     255                 :       7205 :           if (bb == m_switch_bb
     256                 :       7205 :               || (single_pred_p (bb)
     257                 :       6695 :                   && single_pred (bb) == m_switch_bb
     258                 :       6548 :                   && (!m_default_case_nonstandard
     259                 :        445 :                       || empty_block_p (bb))))
     260                 :            :             {
     261                 :       6997 :               tree reloc, val;
     262                 :       6997 :               const char *reason = NULL;
     263                 :            : 
     264                 :       6997 :               val = gimple_phi_arg_def (phi, i);
     265                 :       6997 :               if (!is_gimple_ip_invariant (val))
     266                 :            :                 reason = "non-invariant value from a case";
     267                 :            :               else
     268                 :            :                 {
     269                 :       6946 :                   reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
     270                 :       6946 :                   if ((flag_pic && reloc != null_pointer_node)
     271                 :       6893 :                       || (!flag_pic && reloc == NULL_TREE))
     272                 :            :                     {
     273                 :         53 :                       if (reloc)
     274                 :            :                         reason
     275                 :            :                           = "value from a case would need runtime relocations";
     276                 :            :                       else
     277                 :          0 :                         reason
     278                 :          0 :                           = "value from a case is not a valid initializer";
     279                 :            :                     }
     280                 :            :                 }
     281                 :        104 :               if (reason)
     282                 :            :                 {
     283                 :            :                   /* For contiguous range, we can allow non-constant
     284                 :            :                      or one that needs relocation, as long as it is
     285                 :            :                      only reachable from the default case.  */
     286                 :        104 :                   if (bb == m_switch_bb)
     287                 :         90 :                     bb = m_final_bb;
     288                 :        104 :                   if (!m_contiguous_range || bb != m_default_bb)
     289                 :            :                     {
     290                 :         82 :                       m_reason = reason;
     291                 :         82 :                       return false;
     292                 :            :                     }
     293                 :            : 
     294                 :         22 :                   unsigned int branch_num = gimple_switch_num_labels (m_switch);
     295                 :        138 :                   for (unsigned int i = 1; i < branch_num; i++)
     296                 :            :                     {
     297                 :        116 :                       if (gimple_switch_label_bb (cfun, m_switch, i) == bb)
     298                 :            :                         {
     299                 :          0 :                           m_reason = reason;
     300                 :          0 :                           return false;
     301                 :            :                         }
     302                 :            :                     }
     303                 :         22 :                   m_default_case_nonstandard = true;
     304                 :            :                 }
     305                 :            :             }
     306                 :            :         }
     307                 :            :     }
     308                 :            : 
     309                 :            :   return true;
     310                 :            : }
     311                 :            : 
     312                 :            : /* The following function allocates default_values, target_{in,out}_names and
     313                 :            :    constructors arrays.  The last one is also populated with pointers to
     314                 :            :    vectors that will become constructors of new arrays.  */
     315                 :            : 
     316                 :            : void
     317                 :        334 : switch_conversion::create_temp_arrays ()
     318                 :            : {
     319                 :        334 :   int i;
     320                 :            : 
     321                 :        334 :   m_default_values = XCNEWVEC (tree, m_phi_count * 3);
     322                 :            :   /* ??? Macros do not support multi argument templates in their
     323                 :            :      argument list.  We create a typedef to work around that problem.  */
     324                 :        334 :   typedef vec<constructor_elt, va_gc> *vec_constructor_elt_gc;
     325                 :        334 :   m_constructors = XCNEWVEC (vec_constructor_elt_gc, m_phi_count);
     326                 :        334 :   m_target_inbound_names = m_default_values + m_phi_count;
     327                 :        334 :   m_target_outbound_names = m_target_inbound_names + m_phi_count;
     328                 :        713 :   for (i = 0; i < m_phi_count; i++)
     329                 :        379 :     vec_alloc (m_constructors[i], tree_to_uhwi (m_range_size) + 1);
     330                 :        334 : }
     331                 :            : 
     332                 :            : /* Populate the array of default values in the order of phi nodes.
     333                 :            :    DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
     334                 :            :    if the range is non-contiguous or the default case has standard
     335                 :            :    structure, otherwise it is the first non-default case instead.  */
     336                 :            : 
     337                 :            : void
     338                 :        334 : switch_conversion::gather_default_values (tree default_case)
     339                 :            : {
     340                 :        334 :   gphi_iterator gsi;
     341                 :        334 :   basic_block bb = label_to_block (cfun, CASE_LABEL (default_case));
     342                 :        334 :   edge e;
     343                 :        334 :   int i = 0;
     344                 :            : 
     345                 :        334 :   gcc_assert (CASE_LOW (default_case) == NULL_TREE
     346                 :            :               || m_default_case_nonstandard);
     347                 :            : 
     348                 :        334 :   if (bb == m_final_bb)
     349                 :        169 :     e = find_edge (m_switch_bb, bb);
     350                 :            :   else
     351                 :        165 :     e = single_succ_edge (bb);
     352                 :            : 
     353                 :        744 :   for (gsi = gsi_start_phis (m_final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
     354                 :            :     {
     355                 :        410 :       gphi *phi = gsi.phi ();
     356                 :        820 :       if (virtual_operand_p (gimple_phi_result (phi)))
     357                 :         31 :         continue;
     358                 :        379 :       tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
     359                 :        379 :       gcc_assert (val);
     360                 :        379 :       m_default_values[i++] = val;
     361                 :            :     }
     362                 :        334 : }
     363                 :            : 
     364                 :            : /* The following function populates the vectors in the constructors array with
     365                 :            :    future contents of the static arrays.  The vectors are populated in the
     366                 :            :    order of phi nodes.  */
     367                 :            : 
     368                 :            : void
     369                 :        334 : switch_conversion::build_constructors ()
     370                 :            : {
     371                 :        334 :   unsigned i, branch_num = gimple_switch_num_labels (m_switch);
     372                 :        334 :   tree pos = m_range_min;
     373                 :        334 :   tree pos_one = build_int_cst (TREE_TYPE (pos), 1);
     374                 :            : 
     375                 :       6976 :   for (i = 1; i < branch_num; i++)
     376                 :            :     {
     377                 :       6642 :       tree cs = gimple_switch_label (m_switch, i);
     378                 :       6642 :       basic_block bb = label_to_block (cfun, CASE_LABEL (cs));
     379                 :       6642 :       edge e;
     380                 :       6642 :       tree high;
     381                 :       6642 :       gphi_iterator gsi;
     382                 :       6642 :       int j;
     383                 :            : 
     384                 :       6642 :       if (bb == m_final_bb)
     385                 :        233 :         e = find_edge (m_switch_bb, bb);
     386                 :            :       else
     387                 :       6409 :         e = single_succ_edge (bb);
     388                 :       6642 :       gcc_assert (e);
     389                 :            : 
     390                 :       7716 :       while (tree_int_cst_lt (pos, CASE_LOW (cs)))
     391                 :            :         {
     392                 :            :           int k;
     393                 :       3568 :           for (k = 0; k < m_phi_count; k++)
     394                 :            :             {
     395                 :       2494 :               constructor_elt elt;
     396                 :            : 
     397                 :       2494 :               elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
     398                 :       2494 :               elt.value
     399                 :       2494 :                 = unshare_expr_without_location (m_default_values[k]);
     400                 :       2494 :               m_constructors[k]->quick_push (elt);
     401                 :            :             }
     402                 :            : 
     403                 :       1074 :           pos = int_const_binop (PLUS_EXPR, pos, pos_one);
     404                 :            :         }
     405                 :       6642 :       gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
     406                 :            : 
     407                 :       6642 :       j = 0;
     408                 :       6642 :       if (CASE_HIGH (cs))
     409                 :         84 :         high = CASE_HIGH (cs);
     410                 :            :       else
     411                 :       6558 :         high = CASE_LOW (cs);
     412                 :       6642 :       for (gsi = gsi_start_phis (m_final_bb);
     413                 :      13811 :            !gsi_end_p (gsi); gsi_next (&gsi))
     414                 :            :         {
     415                 :       7169 :           gphi *phi = gsi.phi ();
     416                 :      14338 :           if (virtual_operand_p (gimple_phi_result (phi)))
     417                 :        117 :             continue;
     418                 :       7052 :           tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
     419                 :       7052 :           tree low = CASE_LOW (cs);
     420                 :       7052 :           pos = CASE_LOW (cs);
     421                 :            : 
     422                 :       7339 :           do
     423                 :            :             {
     424                 :       7339 :               constructor_elt elt;
     425                 :            : 
     426                 :       7339 :               elt.index = int_const_binop (MINUS_EXPR, pos, m_range_min);
     427                 :       7339 :               elt.value = unshare_expr_without_location (val);
     428                 :       7339 :               m_constructors[j]->quick_push (elt);
     429                 :            : 
     430                 :       7339 :               pos = int_const_binop (PLUS_EXPR, pos, pos_one);
     431                 :       7339 :             } while (!tree_int_cst_lt (high, pos)
     432                 :       7339 :                      && tree_int_cst_lt (low, pos));
     433                 :       7052 :           j++;
     434                 :            :         }
     435                 :            :     }
     436                 :        334 : }
     437                 :            : 
     438                 :            : /* If all values in the constructor vector are products of a linear function
     439                 :            :    a * x + b, then return true.  When true, COEFF_A and COEFF_B and
     440                 :            :    coefficients of the linear function.  Note that equal values are special
     441                 :            :    case of a linear function with a and b equal to zero.  */
     442                 :            : 
     443                 :            : bool
     444                 :        379 : switch_conversion::contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
     445                 :            :                                                wide_int *coeff_a,
     446                 :            :                                                wide_int *coeff_b)
     447                 :            : {
     448                 :        379 :   unsigned int i;
     449                 :        379 :   constructor_elt *elt;
     450                 :            : 
     451                 :        379 :   gcc_assert (vec->length () >= 2);
     452                 :            : 
     453                 :            :   /* Let's try to find any linear function a * x + y that can apply to
     454                 :            :      given values. 'a' can be calculated as follows:
     455                 :            : 
     456                 :            :      a = (y2 - y1) / (x2 - x1) where x2 - x1 = 1 (consecutive case indices)
     457                 :            :      a = y2 - y1
     458                 :            : 
     459                 :            :      and
     460                 :            : 
     461                 :            :      b = y2 - a * x2
     462                 :            : 
     463                 :            :   */
     464                 :            : 
     465                 :        379 :   tree elt0 = (*vec)[0].value;
     466                 :        379 :   tree elt1 = (*vec)[1].value;
     467                 :            : 
     468                 :        379 :   if (TREE_CODE (elt0) != INTEGER_CST || TREE_CODE (elt1) != INTEGER_CST)
     469                 :            :     return false;
     470                 :            : 
     471                 :        295 :   wide_int range_min
     472                 :        295 :     = wide_int::from (wi::to_wide (m_range_min),
     473                 :        295 :                       TYPE_PRECISION (TREE_TYPE (elt0)),
     474                 :        590 :                       TYPE_SIGN (TREE_TYPE (m_range_min)));
     475                 :        295 :   wide_int y1 = wi::to_wide (elt0);
     476                 :        295 :   wide_int y2 = wi::to_wide (elt1);
     477                 :        295 :   wide_int a = y2 - y1;
     478                 :        295 :   wide_int b = y2 - a * (range_min + 1);
     479                 :            : 
     480                 :            :   /* Verify that all values fulfill the linear function.  */
     481                 :       1193 :   FOR_EACH_VEC_SAFE_ELT (vec, i, elt)
     482                 :            :     {
     483                 :       1130 :       if (TREE_CODE (elt->value) != INTEGER_CST)
     484                 :        232 :         return false;
     485                 :            : 
     486                 :       1130 :       wide_int value = wi::to_wide (elt->value);
     487                 :       1130 :       if (a * range_min + b != value)
     488                 :            :         return false;
     489                 :            : 
     490                 :        898 :       ++range_min;
     491                 :            :     }
     492                 :            : 
     493                 :         63 :   *coeff_a = a;
     494                 :         63 :   *coeff_b = b;
     495                 :            : 
     496                 :         63 :   return true;
     497                 :            : }
     498                 :            : 
     499                 :            : /* Return type which should be used for array elements, either TYPE's
     500                 :            :    main variant or, for integral types, some smaller integral type
     501                 :            :    that can still hold all the constants.  */
     502                 :            : 
     503                 :            : tree
     504                 :        316 : switch_conversion::array_value_type (tree type, int num)
     505                 :            : {
     506                 :        316 :   unsigned int i, len = vec_safe_length (m_constructors[num]);
     507                 :        316 :   constructor_elt *elt;
     508                 :        316 :   int sign = 0;
     509                 :        316 :   tree smaller_type;
     510                 :            : 
     511                 :            :   /* Types with alignments greater than their size can reach here, e.g. out of
     512                 :            :      SRA.  We couldn't use these as an array component type so get back to the
     513                 :            :      main variant first, which, for our purposes, is fine for other types as
     514                 :            :      well.  */
     515                 :            : 
     516                 :        316 :   type = TYPE_MAIN_VARIANT (type);
     517                 :            : 
     518                 :        316 :   if (!INTEGRAL_TYPE_P (type))
     519                 :            :     return type;
     520                 :            : 
     521                 :        232 :   scalar_int_mode type_mode = SCALAR_INT_TYPE_MODE (type);
     522                 :        232 :   scalar_int_mode mode = get_narrowest_mode (type_mode);
     523                 :        696 :   if (GET_MODE_SIZE (type_mode) <= GET_MODE_SIZE (mode))
     524                 :            :     return type;
     525                 :            : 
     526                 :        414 :   if (len < (optimize_bb_for_size_p (gimple_bb (m_switch)) ? 2 : 32))
     527                 :            :     return type;
     528                 :            : 
     529                 :       2639 :   FOR_EACH_VEC_SAFE_ELT (m_constructors[num], i, elt)
     530                 :            :     {
     531                 :       2586 :       wide_int cst;
     532                 :            : 
     533                 :       2586 :       if (TREE_CODE (elt->value) != INTEGER_CST)
     534                 :          2 :         return type;
     535                 :            : 
     536                 :       2586 :       cst = wi::to_wide (elt->value);
     537                 :       2606 :       while (1)
     538                 :            :         {
     539                 :       2606 :           unsigned int prec = GET_MODE_BITSIZE (mode);
     540                 :       2606 :           if (prec > HOST_BITS_PER_WIDE_INT)
     541                 :            :             return type;
     542                 :            : 
     543                 :       2606 :           if (sign >= 0 && cst == wi::zext (cst, prec))
     544                 :            :             {
     545                 :       1408 :               if (sign == 0 && cst == wi::sext (cst, prec))
     546                 :            :                 break;
     547                 :            :               sign = 1;
     548                 :            :               break;
     549                 :            :             }
     550                 :       1198 :           if (sign <= 0 && cst == wi::sext (cst, prec))
     551                 :            :             {
     552                 :            :               sign = -1;
     553                 :            :               break;
     554                 :            :             }
     555                 :            : 
     556                 :         22 :           if (sign == 1)
     557                 :          6 :             sign = 0;
     558                 :            : 
     559                 :         22 :           if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
     560                 :         44 :               || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (type_mode))
     561                 :          2 :             return type;
     562                 :            :         }
     563                 :            :     }
     564                 :            : 
     565                 :         53 :   if (sign == 0)
     566                 :         28 :     sign = TYPE_UNSIGNED (type) ? 1 : -1;
     567                 :         53 :   smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
     568                 :         53 :   if (GET_MODE_SIZE (type_mode)
     569                 :        106 :       <= GET_MODE_SIZE (SCALAR_INT_TYPE_MODE (smaller_type)))
     570                 :          0 :     return type;
     571                 :            : 
     572                 :            :   return smaller_type;
     573                 :            : }
     574                 :            : 
     575                 :            : /* Create an appropriate array type and declaration and assemble a static
     576                 :            :    array variable.  Also create a load statement that initializes
     577                 :            :    the variable in question with a value from the static array.  SWTCH is
     578                 :            :    the switch statement being converted, NUM is the index to
     579                 :            :    arrays of constructors, default values and target SSA names
     580                 :            :    for this particular array.  ARR_INDEX_TYPE is the type of the index
     581                 :            :    of the new array, PHI is the phi node of the final BB that corresponds
     582                 :            :    to the value that will be loaded from the created array.  TIDX
     583                 :            :    is an ssa name of a temporary variable holding the index for loads from the
     584                 :            :    new array.  */
     585                 :            : 
     586                 :            : void
     587                 :        379 : switch_conversion::build_one_array (int num, tree arr_index_type,
     588                 :            :                                     gphi *phi, tree tidx)
     589                 :            : {
     590                 :        379 :   tree name;
     591                 :        379 :   gimple *load;
     592                 :        379 :   gimple_stmt_iterator gsi = gsi_for_stmt (m_switch);
     593                 :        379 :   location_t loc = gimple_location (m_switch);
     594                 :            : 
     595                 :        379 :   gcc_assert (m_default_values[num]);
     596                 :            : 
     597                 :        379 :   name = copy_ssa_name (PHI_RESULT (phi));
     598                 :        379 :   m_target_inbound_names[num] = name;
     599                 :            : 
     600                 :        379 :   vec<constructor_elt, va_gc> *constructor = m_constructors[num];
     601                 :        379 :   wide_int coeff_a, coeff_b;
     602                 :        379 :   bool linear_p = contains_linear_function_p (constructor, &coeff_a, &coeff_b);
     603                 :        379 :   tree type;
     604                 :        379 :   if (linear_p
     605                 :        442 :       && (type = range_check_type (TREE_TYPE ((*constructor)[0].value))))
     606                 :            :     {
     607                 :         70 :       if (dump_file && coeff_a.to_uhwi () > 0)
     608                 :          6 :         fprintf (dump_file, "Linear transformation with A = %" PRId64
     609                 :            :                  " and B = %" PRId64 "\n", coeff_a.to_shwi (),
     610                 :            :                  coeff_b.to_shwi ());
     611                 :            : 
     612                 :            :       /* We must use type of constructor values.  */
     613                 :         63 :       gimple_seq seq = NULL;
     614                 :         63 :       tree tmp = gimple_convert (&seq, type, m_index_expr);
     615                 :         63 :       tree tmp2 = gimple_build (&seq, MULT_EXPR, type,
     616                 :            :                                 wide_int_to_tree (type, coeff_a), tmp);
     617                 :         63 :       tree tmp3 = gimple_build (&seq, PLUS_EXPR, type, tmp2,
     618                 :            :                                 wide_int_to_tree (type, coeff_b));
     619                 :         63 :       tree tmp4 = gimple_convert (&seq, TREE_TYPE (name), tmp3);
     620                 :         63 :       gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
     621                 :         63 :       load = gimple_build_assign (name, tmp4);
     622                 :            :     }
     623                 :            :   else
     624                 :            :     {
     625                 :        316 :       tree array_type, ctor, decl, value_type, fetch, default_type;
     626                 :            : 
     627                 :        316 :       default_type = TREE_TYPE (m_default_values[num]);
     628                 :        316 :       value_type = array_value_type (default_type, num);
     629                 :        316 :       array_type = build_array_type (value_type, arr_index_type);
     630                 :        316 :       if (default_type != value_type)
     631                 :            :         {
     632                 :            :           unsigned int i;
     633                 :            :           constructor_elt *elt;
     634                 :            : 
     635                 :       2844 :           FOR_EACH_VEC_SAFE_ELT (constructor, i, elt)
     636                 :       2763 :             elt->value = fold_convert (value_type, elt->value);
     637                 :            :         }
     638                 :        316 :       ctor = build_constructor (array_type, constructor);
     639                 :        316 :       TREE_CONSTANT (ctor) = true;
     640                 :        316 :       TREE_STATIC (ctor) = true;
     641                 :            : 
     642                 :        316 :       decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
     643                 :        316 :       TREE_STATIC (decl) = 1;
     644                 :        316 :       DECL_INITIAL (decl) = ctor;
     645                 :            : 
     646                 :        316 :       DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
     647                 :        316 :       DECL_ARTIFICIAL (decl) = 1;
     648                 :        316 :       DECL_IGNORED_P (decl) = 1;
     649                 :        316 :       TREE_CONSTANT (decl) = 1;
     650                 :        316 :       TREE_READONLY (decl) = 1;
     651                 :        316 :       DECL_IGNORED_P (decl) = 1;
     652                 :        316 :       if (offloading_function_p (cfun->decl))
     653                 :          0 :         DECL_ATTRIBUTES (decl)
     654                 :          0 :           = tree_cons (get_identifier ("omp declare target"), NULL_TREE,
     655                 :            :                        NULL_TREE);
     656                 :        316 :       varpool_node::finalize_decl (decl);
     657                 :            : 
     658                 :        316 :       fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
     659                 :            :                       NULL_TREE);
     660                 :        316 :       if (default_type != value_type)
     661                 :            :         {
     662                 :         81 :           fetch = fold_convert (default_type, fetch);
     663                 :         81 :           fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
     664                 :            :                                             true, GSI_SAME_STMT);
     665                 :            :         }
     666                 :        316 :       load = gimple_build_assign (name, fetch);
     667                 :            :     }
     668                 :            : 
     669                 :        379 :   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
     670                 :        379 :   update_stmt (load);
     671                 :        379 :   m_arr_ref_last = load;
     672                 :        379 : }
     673                 :            : 
     674                 :            : /* Builds and initializes static arrays initialized with values gathered from
     675                 :            :    the switch statement.  Also creates statements that load values from
     676                 :            :    them.  */
     677                 :            : 
     678                 :            : void
     679                 :        334 : switch_conversion::build_arrays ()
     680                 :            : {
     681                 :        334 :   tree arr_index_type;
     682                 :        334 :   tree tidx, sub, utype;
     683                 :        334 :   gimple *stmt;
     684                 :        334 :   gimple_stmt_iterator gsi;
     685                 :        334 :   gphi_iterator gpi;
     686                 :        334 :   int i;
     687                 :        334 :   location_t loc = gimple_location (m_switch);
     688                 :            : 
     689                 :        334 :   gsi = gsi_for_stmt (m_switch);
     690                 :            : 
     691                 :            :   /* Make sure we do not generate arithmetics in a subrange.  */
     692                 :        334 :   utype = TREE_TYPE (m_index_expr);
     693                 :        334 :   if (TREE_TYPE (utype))
     694                 :         25 :     utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
     695                 :            :   else
     696                 :        309 :     utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
     697                 :            : 
     698                 :        334 :   arr_index_type = build_index_type (m_range_size);
     699                 :        334 :   tidx = make_ssa_name (utype);
     700                 :        334 :   sub = fold_build2_loc (loc, MINUS_EXPR, utype,
     701                 :            :                          fold_convert_loc (loc, utype, m_index_expr),
     702                 :            :                          fold_convert_loc (loc, utype, m_range_min));
     703                 :        334 :   sub = force_gimple_operand_gsi (&gsi, sub,
     704                 :            :                                   false, NULL, true, GSI_SAME_STMT);
     705                 :        334 :   stmt = gimple_build_assign (tidx, sub);
     706                 :            : 
     707                 :        334 :   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
     708                 :        334 :   update_stmt (stmt);
     709                 :        334 :   m_arr_ref_first = stmt;
     710                 :            : 
     711                 :        334 :   for (gpi = gsi_start_phis (m_final_bb), i = 0;
     712                 :        744 :        !gsi_end_p (gpi); gsi_next (&gpi))
     713                 :            :     {
     714                 :        410 :       gphi *phi = gpi.phi ();
     715                 :        820 :       if (!virtual_operand_p (gimple_phi_result (phi)))
     716                 :        379 :         build_one_array (i++, arr_index_type, phi, tidx);
     717                 :            :       else
     718                 :            :         {
     719                 :         31 :           edge e;
     720                 :         31 :           edge_iterator ei;
     721                 :         45 :           FOR_EACH_EDGE (e, ei, m_switch_bb->succs)
     722                 :            :             {
     723                 :         45 :               if (e->dest == m_final_bb)
     724                 :            :                 break;
     725                 :         28 :               if (!m_default_case_nonstandard
     726                 :         20 :                   || e->dest != m_default_bb)
     727                 :            :                 {
     728                 :         14 :                   e = single_succ_edge (e->dest);
     729                 :         14 :                   break;
     730                 :            :                 }
     731                 :            :             }
     732                 :         31 :           gcc_assert (e && e->dest == m_final_bb);
     733                 :         31 :           m_target_vop = PHI_ARG_DEF_FROM_EDGE (phi, e);
     734                 :            :         }
     735                 :            :     }
     736                 :        334 : }
     737                 :            : 
     738                 :            : /* Generates and appropriately inserts loads of default values at the position
     739                 :            :    given by GSI.  Returns the last inserted statement.  */
     740                 :            : 
     741                 :            : gassign *
     742                 :        215 : switch_conversion::gen_def_assigns (gimple_stmt_iterator *gsi)
     743                 :            : {
     744                 :        215 :   int i;
     745                 :        215 :   gassign *assign = NULL;
     746                 :            : 
     747                 :        471 :   for (i = 0; i < m_phi_count; i++)
     748                 :            :     {
     749                 :        256 :       tree name = copy_ssa_name (m_target_inbound_names[i]);
     750                 :        256 :       m_target_outbound_names[i] = name;
     751                 :        256 :       assign = gimple_build_assign (name, m_default_values[i]);
     752                 :        256 :       gsi_insert_before (gsi, assign, GSI_SAME_STMT);
     753                 :        512 :       update_stmt (assign);
     754                 :            :     }
     755                 :        215 :   return assign;
     756                 :            : }
     757                 :            : 
     758                 :            : /* Deletes the unused bbs and edges that now contain the switch statement and
     759                 :            :    its empty branch bbs.  BBD is the now dead BB containing
     760                 :            :    the original switch statement, FINAL is the last BB of the converted
     761                 :            :    switch statement (in terms of succession).  */
     762                 :            : 
     763                 :            : void
     764                 :        334 : switch_conversion::prune_bbs (basic_block bbd, basic_block final,
     765                 :            :                               basic_block default_bb)
     766                 :            : {
     767                 :        334 :   edge_iterator ei;
     768                 :        334 :   edge e;
     769                 :            : 
     770                 :       7452 :   for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
     771                 :            :     {
     772                 :       6784 :       basic_block bb;
     773                 :       6784 :       bb = e->dest;
     774                 :       6784 :       remove_edge (e);
     775                 :       6784 :       if (bb != final && bb != default_bb)
     776                 :       6356 :         delete_basic_block (bb);
     777                 :            :     }
     778                 :        334 :   delete_basic_block (bbd);
     779                 :        334 : }
     780                 :            : 
     781                 :            : /* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
     782                 :            :    from the basic block loading values from an array and E2F from the basic
     783                 :            :    block loading default values.  BBF is the last switch basic block (see the
     784                 :            :    bbf description in the comment below).  */
     785                 :            : 
     786                 :            : void
     787                 :        334 : switch_conversion::fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
     788                 :            : {
     789                 :        334 :   gphi_iterator gsi;
     790                 :        334 :   int i;
     791                 :            : 
     792                 :        334 :   for (gsi = gsi_start_phis (bbf), i = 0;
     793                 :        744 :        !gsi_end_p (gsi); gsi_next (&gsi))
     794                 :            :     {
     795                 :        410 :       gphi *phi = gsi.phi ();
     796                 :        410 :       tree inbound, outbound;
     797                 :        820 :       if (virtual_operand_p (gimple_phi_result (phi)))
     798                 :         31 :         inbound = outbound = m_target_vop;
     799                 :            :       else
     800                 :            :         {
     801                 :        379 :           inbound = m_target_inbound_names[i];
     802                 :        379 :           outbound = m_target_outbound_names[i++];
     803                 :            :         }
     804                 :        410 :       add_phi_arg (phi, inbound, e1f, UNKNOWN_LOCATION);
     805                 :        410 :       if (!m_default_case_nonstandard)
     806                 :        273 :         add_phi_arg (phi, outbound, e2f, UNKNOWN_LOCATION);
     807                 :            :     }
     808                 :        334 : }
     809                 :            : 
     810                 :            : /* Creates a check whether the switch expression value actually falls into the
     811                 :            :    range given by all the cases.  If it does not, the temporaries are loaded
     812                 :            :    with default values instead.  */
     813                 :            : 
     814                 :            : void
     815                 :        334 : switch_conversion::gen_inbound_check ()
     816                 :            : {
     817                 :        334 :   tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
     818                 :        334 :   tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
     819                 :        334 :   tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
     820                 :        334 :   glabel *label1, *label2, *label3;
     821                 :        334 :   tree utype, tidx;
     822                 :        334 :   tree bound;
     823                 :            : 
     824                 :        334 :   gcond *cond_stmt;
     825                 :            : 
     826                 :        334 :   gassign *last_assign = NULL;
     827                 :        334 :   gimple_stmt_iterator gsi;
     828                 :        334 :   basic_block bb0, bb1, bb2, bbf, bbd;
     829                 :        334 :   edge e01 = NULL, e02, e21, e1d, e1f, e2f;
     830                 :        334 :   location_t loc = gimple_location (m_switch);
     831                 :            : 
     832                 :        334 :   gcc_assert (m_default_values);
     833                 :            : 
     834                 :        334 :   bb0 = gimple_bb (m_switch);
     835                 :            : 
     836                 :        334 :   tidx = gimple_assign_lhs (m_arr_ref_first);
     837                 :        334 :   utype = TREE_TYPE (tidx);
     838                 :            : 
     839                 :            :   /* (end of) block 0 */
     840                 :        334 :   gsi = gsi_for_stmt (m_arr_ref_first);
     841                 :        334 :   gsi_next (&gsi);
     842                 :            : 
     843                 :        334 :   bound = fold_convert_loc (loc, utype, m_range_size);
     844                 :        334 :   cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
     845                 :        334 :   gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
     846                 :        334 :   update_stmt (cond_stmt);
     847                 :            : 
     848                 :            :   /* block 2 */
     849                 :        334 :   if (!m_default_case_nonstandard)
     850                 :            :     {
     851                 :        215 :       label2 = gimple_build_label (label_decl2);
     852                 :        215 :       gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
     853                 :        215 :       last_assign = gen_def_assigns (&gsi);
     854                 :            :     }
     855                 :            : 
     856                 :            :   /* block 1 */
     857                 :        334 :   label1 = gimple_build_label (label_decl1);
     858                 :        334 :   gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
     859                 :            : 
     860                 :            :   /* block F */
     861                 :        334 :   gsi = gsi_start_bb (m_final_bb);
     862                 :        334 :   label3 = gimple_build_label (label_decl3);
     863                 :        334 :   gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
     864                 :            : 
     865                 :            :   /* cfg fix */
     866                 :        334 :   e02 = split_block (bb0, cond_stmt);
     867                 :        334 :   bb2 = e02->dest;
     868                 :            : 
     869                 :        334 :   if (m_default_case_nonstandard)
     870                 :            :     {
     871                 :        119 :       bb1 = bb2;
     872                 :        119 :       bb2 = m_default_bb;
     873                 :        119 :       e01 = e02;
     874                 :        119 :       e01->flags = EDGE_TRUE_VALUE;
     875                 :        119 :       e02 = make_edge (bb0, bb2, EDGE_FALSE_VALUE);
     876                 :        119 :       edge e_default = find_edge (bb1, bb2);
     877                 :        119 :       for (gphi_iterator gsi = gsi_start_phis (bb2);
     878                 :        153 :            !gsi_end_p (gsi); gsi_next (&gsi))
     879                 :            :         {
     880                 :         34 :           gphi *phi = gsi.phi ();
     881                 :         34 :           tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_default);
     882                 :         34 :           add_phi_arg (phi, arg, e02,
     883                 :            :                        gimple_phi_arg_location_from_edge (phi, e_default));
     884                 :            :         }
     885                 :            :       /* Partially fix the dominator tree, if it is available.  */
     886                 :        119 :       if (dom_info_available_p (CDI_DOMINATORS))
     887                 :        119 :         redirect_immediate_dominators (CDI_DOMINATORS, bb1, bb0);
     888                 :            :     }
     889                 :            :   else
     890                 :            :     {
     891                 :        215 :       e21 = split_block (bb2, last_assign);
     892                 :        215 :       bb1 = e21->dest;
     893                 :        215 :       remove_edge (e21);
     894                 :            :     }
     895                 :            : 
     896                 :        334 :   e1d = split_block (bb1, m_arr_ref_last);
     897                 :        334 :   bbd = e1d->dest;
     898                 :        334 :   remove_edge (e1d);
     899                 :            : 
     900                 :            :   /* Flags and profiles of the edge for in-range values.  */
     901                 :        334 :   if (!m_default_case_nonstandard)
     902                 :        215 :     e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
     903                 :        334 :   e01->probability = m_default_prob.invert ();
     904                 :            : 
     905                 :            :   /* Flags and profiles of the edge taking care of out-of-range values.  */
     906                 :        334 :   e02->flags &= ~EDGE_FALLTHRU;
     907                 :        334 :   e02->flags |= EDGE_FALSE_VALUE;
     908                 :        334 :   e02->probability = m_default_prob;
     909                 :            : 
     910                 :        334 :   bbf = m_final_bb;
     911                 :            : 
     912                 :        334 :   e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
     913                 :        334 :   e1f->probability = profile_probability::always ();
     914                 :            : 
     915                 :        334 :   if (m_default_case_nonstandard)
     916                 :            :     e2f = NULL;
     917                 :            :   else
     918                 :            :     {
     919                 :        215 :       e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
     920                 :        215 :       e2f->probability = profile_probability::always ();
     921                 :            :     }
     922                 :            : 
     923                 :            :   /* frequencies of the new BBs */
     924                 :        334 :   bb1->count = e01->count ();
     925                 :        334 :   bb2->count = e02->count ();
     926                 :        334 :   if (!m_default_case_nonstandard)
     927                 :        215 :     bbf->count = e1f->count () + e2f->count ();
     928                 :            : 
     929                 :            :   /* Tidy blocks that have become unreachable.  */
     930                 :        334 :   prune_bbs (bbd, m_final_bb,
     931                 :        334 :              m_default_case_nonstandard ? m_default_bb : NULL);
     932                 :            : 
     933                 :            :   /* Fixup the PHI nodes in bbF.  */
     934                 :        334 :   fix_phi_nodes (e1f, e2f, bbf);
     935                 :            : 
     936                 :            :   /* Fix the dominator tree, if it is available.  */
     937                 :        334 :   if (dom_info_available_p (CDI_DOMINATORS))
     938                 :            :     {
     939                 :        334 :       vec<basic_block> bbs_to_fix_dom;
     940                 :            : 
     941                 :        334 :       set_immediate_dominator (CDI_DOMINATORS, bb1, bb0);
     942                 :        334 :       if (!m_default_case_nonstandard)
     943                 :        215 :         set_immediate_dominator (CDI_DOMINATORS, bb2, bb0);
     944                 :        334 :       if (! get_immediate_dominator (CDI_DOMINATORS, bbf))
     945                 :            :         /* If bbD was the immediate dominator ...  */
     946                 :        175 :         set_immediate_dominator (CDI_DOMINATORS, bbf, bb0);
     947                 :            : 
     948                 :        334 :       bbs_to_fix_dom.create (3 + (bb2 != bbf));
     949                 :        334 :       bbs_to_fix_dom.quick_push (bb0);
     950                 :        334 :       bbs_to_fix_dom.quick_push (bb1);
     951                 :        334 :       if (bb2 != bbf)
     952                 :        314 :         bbs_to_fix_dom.quick_push (bb2);
     953                 :        334 :       bbs_to_fix_dom.quick_push (bbf);
     954                 :            : 
     955                 :        334 :       iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true);
     956                 :        668 :       bbs_to_fix_dom.release ();
     957                 :            :     }
     958                 :        334 : }
     959                 :            : 
     960                 :            : /* The following function is invoked on every switch statement (the current
     961                 :            :    one is given in SWTCH) and runs the individual phases of switch
     962                 :            :    conversion on it one after another until one fails or the conversion
     963                 :            :    is completed.  On success, NULL is in m_reason, otherwise points
     964                 :            :    to a string with the reason why the conversion failed.  */
     965                 :            : 
     966                 :            : void
     967                 :      16907 : switch_conversion::expand (gswitch *swtch)
     968                 :            : {
     969                 :            :   /* Group case labels so that we get the right results from the heuristics
     970                 :            :      that decide on the code generation approach for this switch.  */
     971                 :      16907 :   m_cfg_altered |= group_case_labels_stmt (swtch);
     972                 :            : 
     973                 :            :   /* If this switch is now a degenerate case with only a default label,
     974                 :            :      there is nothing left for us to do.  */
     975                 :      16907 :   if (gimple_switch_num_labels (swtch) < 2)
     976                 :            :     {
     977                 :          4 :       m_reason = "switch is a degenerate case";
     978                 :          4 :       return;
     979                 :            :     }
     980                 :            : 
     981                 :      16903 :   collect (swtch);
     982                 :            : 
     983                 :            :   /* No error markers should reach here (they should be filtered out
     984                 :            :      during gimplification).  */
     985                 :      16903 :   gcc_checking_assert (TREE_TYPE (m_index_expr) != error_mark_node);
     986                 :            : 
     987                 :            :   /* A switch on a constant should have been optimized in tree-cfg-cleanup.  */
     988                 :      16903 :   gcc_checking_assert (!TREE_CONSTANT (m_index_expr));
     989                 :            : 
     990                 :            :   /* Prefer bit test if possible.  */
     991                 :      16903 :   if (tree_fits_uhwi_p (m_range_size)
     992                 :      16880 :       && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
     993                 :      26442 :       && bit_test_cluster::is_beneficial (m_count, m_uniq))
     994                 :            :     {
     995                 :        816 :       m_reason = "expanding as bit test is preferable";
     996                 :        816 :       return;
     997                 :            :     }
     998                 :            : 
     999                 :      16087 :   if (m_uniq <= 2)
    1000                 :            :     {
    1001                 :            :       /* This will be expanded as a decision tree .  */
    1002                 :       6916 :       m_reason = "expanding as jumps is preferable";
    1003                 :       6916 :       return;
    1004                 :            :     }
    1005                 :            : 
    1006                 :            :   /* If there is no common successor, we cannot do the transformation.  */
    1007                 :       9171 :   if (!m_final_bb)
    1008                 :            :     {
    1009                 :       5224 :       m_reason = "no common successor to all case label target blocks found";
    1010                 :       5224 :       return;
    1011                 :            :     }
    1012                 :            : 
    1013                 :            :   /* Check the case label values are within reasonable range:  */
    1014                 :       3947 :   if (!check_range ())
    1015                 :            :     {
    1016                 :        134 :       gcc_assert (m_reason);
    1017                 :            :       return;
    1018                 :            :     }
    1019                 :            : 
    1020                 :            :   /* For all the cases, see whether they are empty, the assignments they
    1021                 :            :      represent constant and so on...  */
    1022                 :       3813 :   if (!check_all_empty_except_final ())
    1023                 :            :     {
    1024                 :       3397 :       gcc_assert (m_reason);
    1025                 :            :       return;
    1026                 :            :     }
    1027                 :        416 :   if (!check_final_bb ())
    1028                 :            :     {
    1029                 :         82 :       gcc_assert (m_reason);
    1030                 :            :       return;
    1031                 :            :     }
    1032                 :            : 
    1033                 :            :   /* At this point all checks have passed and we can proceed with the
    1034                 :            :      transformation.  */
    1035                 :            : 
    1036                 :        334 :   create_temp_arrays ();
    1037                 :        668 :   gather_default_values (m_default_case_nonstandard
    1038                 :        119 :                          ? gimple_switch_label (swtch, 1)
    1039                 :        215 :                          : gimple_switch_default_label (swtch));
    1040                 :        334 :   build_constructors ();
    1041                 :            : 
    1042                 :        334 :   build_arrays (); /* Build the static arrays and assignments.  */
    1043                 :        334 :   gen_inbound_check (); /* Build the bounds check.  */
    1044                 :            : 
    1045                 :        334 :   m_cfg_altered = true;
    1046                 :            : }
    1047                 :            : 
    1048                 :            : /* Destructor.  */
    1049                 :            : 
    1050                 :      16907 : switch_conversion::~switch_conversion ()
    1051                 :            : {
    1052                 :      16907 :   XDELETEVEC (m_constructors);
    1053                 :      16907 :   XDELETEVEC (m_default_values);
    1054                 :      16907 : }
    1055                 :            : 
    1056                 :            : /* Constructor.  */
    1057                 :            : 
    1058                 :      10417 : group_cluster::group_cluster (vec<cluster *> &clusters,
    1059                 :      10417 :                               unsigned start, unsigned end)
    1060                 :            : {
    1061                 :      10417 :   gcc_checking_assert (end - start + 1 >= 1);
    1062                 :      10417 :   m_prob = profile_probability::never ();
    1063                 :      10417 :   m_cases.create (end - start + 1);
    1064                 :      99312 :   for (unsigned i = start; i <= end; i++)
    1065                 :            :     {
    1066                 :      88895 :       m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
    1067                 :      88895 :       m_prob += clusters[i]->m_prob;
    1068                 :            :     }
    1069                 :      10417 :   m_subtree_prob = m_prob;
    1070                 :      10417 : }
    1071                 :            : 
    1072                 :            : /* Destructor.  */
    1073                 :            : 
    1074                 :      20834 : group_cluster::~group_cluster ()
    1075                 :            : {
    1076                 :     198624 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1077                 :      88895 :     delete m_cases[i];
    1078                 :            : 
    1079                 :      10417 :   m_cases.release ();
    1080                 :      10417 : }
    1081                 :            : 
    1082                 :            : /* Dump content of a cluster.  */
    1083                 :            : 
    1084                 :            : void
    1085                 :         14 : group_cluster::dump (FILE *f, bool details)
    1086                 :            : {
    1087                 :         14 :   unsigned total_values = 0;
    1088                 :        172 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1089                 :        216 :     total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
    1090                 :        144 :                                            m_cases[i]->get_high ());
    1091                 :            : 
    1092                 :            :   unsigned comparison_count = 0;
    1093                 :         86 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1094                 :            :     {
    1095                 :         72 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1096                 :        135 :       comparison_count += sc->m_range_p ? 2 : 1;
    1097                 :            :     }
    1098                 :            : 
    1099                 :         14 :   unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
    1100                 :         17 :   fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
    1101                 :            : 
    1102                 :         14 :   if (details)
    1103                 :          0 :     fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
    1104                 :            :              " density: %.2f%%)", total_values, comparison_count, range,
    1105                 :          0 :              100.0f * comparison_count / range);
    1106                 :            : 
    1107                 :         14 :   fprintf (f, ":");
    1108                 :         14 :   PRINT_CASE (f, get_low ());
    1109                 :         14 :   fprintf (f, "-");
    1110                 :         14 :   PRINT_CASE (f, get_high ());
    1111                 :         14 :   fprintf (f, " ");
    1112                 :         14 : }
    1113                 :            : 
    1114                 :            : /* Emit GIMPLE code to handle the cluster.  */
    1115                 :            : 
    1116                 :            : void
    1117                 :       9871 : jump_table_cluster::emit (tree index_expr, tree,
    1118                 :            :                           tree default_label_expr, basic_block default_bb)
    1119                 :            : {
    1120                 :       9871 :   unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
    1121                 :       9871 :   unsigned HOST_WIDE_INT nondefault_range = 0;
    1122                 :            : 
    1123                 :            :   /* For jump table we just emit a new gswitch statement that will
    1124                 :            :      be latter lowered to jump table.  */
    1125                 :       9871 :   auto_vec <tree> labels;
    1126                 :       9871 :   labels.create (m_cases.length ());
    1127                 :            : 
    1128                 :       9871 :   make_edge (m_case_bb, default_bb, 0);
    1129                 :     193818 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1130                 :            :     {
    1131                 :      87038 :       labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr));
    1132                 :      87038 :       make_edge (m_case_bb, m_cases[i]->m_case_bb, 0);
    1133                 :            :     }
    1134                 :            : 
    1135                 :       9871 :   gswitch *s = gimple_build_switch (index_expr,
    1136                 :            :                                     unshare_expr (default_label_expr), labels);
    1137                 :       9871 :   gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
    1138                 :       9871 :   gsi_insert_after (&gsi, s, GSI_NEW_STMT);
    1139                 :            : 
    1140                 :            :   /* Set up even probabilities for all cases.  */
    1141                 :     193818 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1142                 :            :     {
    1143                 :      87038 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1144                 :      87038 :       edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
    1145                 :      87038 :       unsigned HOST_WIDE_INT case_range
    1146                 :      87038 :         = sc->get_range (sc->get_low (), sc->get_high ());
    1147                 :      87038 :       nondefault_range += case_range;
    1148                 :            : 
    1149                 :            :       /* case_edge->aux is number of values in a jump-table that are covered
    1150                 :            :          by the case_edge.  */
    1151                 :      87038 :       case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + case_range);
    1152                 :            :     }
    1153                 :            : 
    1154                 :       9871 :   edge default_edge = gimple_switch_default_edge (cfun, s);
    1155                 :       9871 :   default_edge->probability = profile_probability::never ();
    1156                 :            : 
    1157                 :     193818 :   for (unsigned i = 0; i < m_cases.length (); i++)
    1158                 :            :     {
    1159                 :      87038 :       simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
    1160                 :      87038 :       edge case_edge = find_edge (m_case_bb, sc->m_case_bb);
    1161                 :      87038 :       case_edge->probability
    1162                 :      87038 :         = profile_probability::always ().apply_scale ((intptr_t)case_edge->aux,
    1163                 :      87038 :                                                       range);
    1164                 :            :     }
    1165                 :            : 
    1166                 :            :   /* Number of non-default values is probability of default edge.  */
    1167                 :       9871 :   default_edge->probability
    1168                 :      19742 :     += profile_probability::always ().apply_scale (nondefault_range,
    1169                 :       9871 :                                                    range).invert ();
    1170                 :            : 
    1171                 :       9871 :   switch_decision_tree::reset_out_edges_aux (s);
    1172                 :       9871 : }
    1173                 :            : 
    1174                 :            : /* Find jump tables of given CLUSTERS, where all members of the vector
    1175                 :            :    are of type simple_cluster.  New clusters are returned.  */
    1176                 :            : 
    1177                 :            : vec<cluster *>
    1178                 :      28489 : jump_table_cluster::find_jump_tables (vec<cluster *> &clusters)
    1179                 :            : {
    1180                 :      28489 :   if (!is_enabled ())
    1181                 :          2 :     return clusters.copy ();
    1182                 :            : 
    1183                 :      28487 :   unsigned l = clusters.length ();
    1184                 :      28487 :   auto_vec<min_cluster_item> min;
    1185                 :      28487 :   min.reserve (l + 1);
    1186                 :            : 
    1187                 :      28487 :   min.quick_push (min_cluster_item (0, 0, 0));
    1188                 :            : 
    1189                 :     162393 :   for (unsigned i = 1; i <= l; i++)
    1190                 :            :     {
    1191                 :            :       /* Set minimal # of clusters with i-th item to infinite.  */
    1192                 :     133906 :       min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
    1193                 :            : 
    1194                 :    2450950 :       for (unsigned j = 0; j < i; j++)
    1195                 :            :         {
    1196                 :    2317040 :           unsigned HOST_WIDE_INT s = min[j].m_non_jt_cases;
    1197                 :    4633860 :           if (i - j < case_values_threshold ())
    1198                 :     379192 :             s += i - j;
    1199                 :            : 
    1200                 :            :           /* Prefer clusters with smaller number of numbers covered.  */
    1201                 :    2317040 :           if ((min[j].m_count + 1 < min[i].m_count
    1202                 :    2160030 :                || (min[j].m_count + 1 == min[i].m_count
    1203                 :        851 :                    && s < min[i].m_non_jt_cases))
    1204                 :    2317090 :               && can_be_handled (clusters, j, i - 1))
    1205                 :     133936 :             min[i] = min_cluster_item (min[j].m_count + 1, j, s);
    1206                 :            :         }
    1207                 :            : 
    1208                 :     133906 :       gcc_checking_assert (min[i].m_count != INT_MAX);
    1209                 :            :     }
    1210                 :            : 
    1211                 :            :   /* No result.  */
    1212                 :      28487 :   if (min[l].m_count == l)
    1213                 :      30708 :     return clusters.copy ();
    1214                 :            : 
    1215                 :      26266 :   vec<cluster *> output;
    1216                 :      26266 :   output.create (4);
    1217                 :            : 
    1218                 :            :   /* Find and build the clusters.  */
    1219                 :      26266 :   for (unsigned int end = l;;)
    1220                 :            :     {
    1221                 :      27590 :       int start = min[end].m_start;
    1222                 :            : 
    1223                 :            :       /* Do not allow clusters with small number of cases.  */
    1224                 :      27590 :       if (is_beneficial (clusters, start, end - 1))
    1225                 :       9871 :         output.safe_push (new jump_table_cluster (clusters, start, end - 1));
    1226                 :            :       else
    1227                 :      60194 :         for (int i = end - 1; i >= start; i--)
    1228                 :      42475 :           output.safe_push (clusters[i]);
    1229                 :            : 
    1230                 :      27590 :       end = start;
    1231                 :            : 
    1232                 :      27590 :       if (start <= 0)
    1233                 :            :         break;
    1234                 :            :     }
    1235                 :            : 
    1236                 :      26266 :   output.reverse ();
    1237                 :      26266 :   return output;
    1238                 :            : }
    1239                 :            : 
    1240                 :            : /* Return true when cluster starting at START and ending at END (inclusive)
    1241                 :            :    can build a jump-table.  */
    1242                 :            : 
    1243                 :            : bool
    1244                 :     157056 : jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
    1245                 :            :                                     unsigned start, unsigned end)
    1246                 :            : {
    1247                 :            :   /* If the switch is relatively small such that the cost of one
    1248                 :            :      indirect jump on the target are higher than the cost of a
    1249                 :            :      decision tree, go with the decision tree.
    1250                 :            : 
    1251                 :            :      If range of values is much bigger than number of values,
    1252                 :            :      or if it is too large to represent in a HOST_WIDE_INT,
    1253                 :            :      make a sequence of conditional branches instead of a dispatch.
    1254                 :            : 
    1255                 :            :      The definition of "much bigger" depends on whether we are
    1256                 :            :      optimizing for size or for speed.
    1257                 :            : 
    1258                 :            :      For algorithm correctness, jump table for a single case must return
    1259                 :            :      true.  We bail out in is_beneficial if it's called just for
    1260                 :            :      a single case.  */
    1261                 :     157056 :   if (start == end)
    1262                 :            :     return true;
    1263                 :            : 
    1264                 :     124885 :   unsigned HOST_WIDE_INT max_ratio
    1265                 :     124885 :     = (optimize_insn_for_size_p ()
    1266                 :     124885 :        ? param_jump_table_max_growth_ratio_for_size
    1267                 :     123210 :        : param_jump_table_max_growth_ratio_for_speed);
    1268                 :     124885 :   unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
    1269                 :     124885 :                                             clusters[end]->get_high ());
    1270                 :            :   /* Check overflow.  */
    1271                 :     124885 :   if (range == 0)
    1272                 :            :     return false;
    1273                 :            : 
    1274                 :            :   unsigned HOST_WIDE_INT comparison_count = 0;
    1275                 :    2698160 :   for (unsigned i = start; i <= end; i++)
    1276                 :            :     {
    1277                 :    2573330 :       simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
    1278                 :    5052060 :       comparison_count += sc->m_range_p ? 2 : 1;
    1279                 :            :     }
    1280                 :            : 
    1281                 :     124831 :   unsigned HOST_WIDE_INT lhs = 100 * range;
    1282                 :     124831 :   if (lhs < range)
    1283                 :            :     return false;
    1284                 :            : 
    1285                 :     124830 :   return lhs <= max_ratio * comparison_count;
    1286                 :            : }
    1287                 :            : 
    1288                 :            : /* Return true if cluster starting at START and ending at END (inclusive)
    1289                 :            :    is profitable transformation.  */
    1290                 :            : 
    1291                 :            : bool
    1292                 :      27590 : jump_table_cluster::is_beneficial (const vec<cluster *> &,
    1293                 :            :                                    unsigned start, unsigned end)
    1294                 :            : {
    1295                 :            :   /* Single case bail out.  */
    1296                 :      27590 :   if (start == end)
    1297                 :            :     return false;
    1298                 :            : 
    1299                 :      53291 :   return end - start + 1 >= case_values_threshold ();
    1300                 :            : }
    1301                 :            : 
    1302                 :            : /* Find bit tests of given CLUSTERS, where all members of the vector
    1303                 :            :    are of type simple_cluster.  New clusters are returned.  */
    1304                 :            : 
    1305                 :            : vec<cluster *>
    1306                 :      18896 : bit_test_cluster::find_bit_tests (vec<cluster *> &clusters)
    1307                 :            : {
    1308                 :      18896 :   unsigned l = clusters.length ();
    1309                 :      18896 :   auto_vec<min_cluster_item> min;
    1310                 :      18896 :   min.reserve (l + 1);
    1311                 :            : 
    1312                 :      18896 :   min.quick_push (min_cluster_item (0, 0, 0));
    1313                 :            : 
    1314                 :      65776 :   for (unsigned i = 1; i <= l; i++)
    1315                 :            :     {
    1316                 :            :       /* Set minimal # of clusters with i-th item to infinite.  */
    1317                 :      46880 :       min.quick_push (min_cluster_item (INT_MAX, INT_MAX, INT_MAX));
    1318                 :            : 
    1319                 :     140927 :       for (unsigned j = 0; j < i; j++)
    1320                 :            :         {
    1321                 :      94047 :           if (min[j].m_count + 1 < min[i].m_count
    1322                 :      94047 :               && can_be_handled (clusters, j, i - 1))
    1323                 :      46880 :             min[i] = min_cluster_item (min[j].m_count + 1, j, INT_MAX);
    1324                 :            :         }
    1325                 :            : 
    1326                 :      46880 :       gcc_checking_assert (min[i].m_count != INT_MAX);
    1327                 :            :     }
    1328                 :            : 
    1329                 :            :   /* No result.  */
    1330                 :      18896 :   if (min[l].m_count == l)
    1331                 :      20729 :     return clusters.copy ();
    1332                 :            : 
    1333                 :      17063 :   vec<cluster *> output;
    1334                 :      17063 :   output.create (4);
    1335                 :            : 
    1336                 :            :   /* Find and build the clusters.  */
    1337                 :      17063 :   for (unsigned end = l;;)
    1338                 :            :     {
    1339                 :      19772 :       int start = min[end].m_start;
    1340                 :            : 
    1341                 :      19772 :       if (is_beneficial (clusters, start, end - 1))
    1342                 :            :         {
    1343                 :       1055 :           bool entire = start == 0 && end == clusters.length ();
    1344                 :        546 :           output.safe_push (new bit_test_cluster (clusters, start, end - 1,
    1345                 :        546 :                                                   entire));
    1346                 :            :         }
    1347                 :            :       else
    1348                 :      61632 :         for (int i = end - 1; i >= start; i--)
    1349                 :      42406 :           output.safe_push (clusters[i]);
    1350                 :            : 
    1351                 :      19772 :       end = start;
    1352                 :            : 
    1353                 :      19772 :       if (start <= 0)
    1354                 :            :         break;
    1355                 :            :     }
    1356                 :            : 
    1357                 :      17063 :   output.reverse ();
    1358                 :      17063 :   return output;
    1359                 :            : }
    1360                 :            : 
    1361                 :            : /* Return true when RANGE of case values with UNIQ labels
    1362                 :            :    can build a bit test.  */
    1363                 :            : 
    1364                 :            : bool
    1365                 :      54416 : bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
    1366                 :            :                                   unsigned int uniq)
    1367                 :            : {
    1368                 :            :   /* Check overflow.  */
    1369                 :      54416 :   if (range == 0)
    1370                 :            :     return 0;
    1371                 :            : 
    1372                 :     108716 :   if (range >= GET_MODE_BITSIZE (word_mode))
    1373                 :            :     return false;
    1374                 :            : 
    1375                 :      43613 :   return uniq <= 3;
    1376                 :            : }
    1377                 :            : 
    1378                 :            : /* Return true when cluster starting at START and ending at END (inclusive)
    1379                 :            :    can build a bit test.  */
    1380                 :            : 
    1381                 :            : bool
    1382                 :      57929 : bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
    1383                 :            :                                   unsigned start, unsigned end)
    1384                 :            : {
    1385                 :            :   /* For algorithm correctness, bit test for a single case must return
    1386                 :            :      true.  We bail out in is_beneficial if it's called just for
    1387                 :            :      a single case.  */
    1388                 :      57929 :   if (start == end)
    1389                 :            :     return true;
    1390                 :            : 
    1391                 :      37536 :   unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
    1392                 :      37536 :                                             clusters[end]->get_high ());
    1393                 :      37536 :   auto_bitmap dest_bbs;
    1394                 :            : 
    1395                 :     184747 :   for (unsigned i = start; i <= end; i++)
    1396                 :            :     {
    1397                 :     147211 :       simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
    1398                 :     147211 :       bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
    1399                 :            :     }
    1400                 :            : 
    1401                 :      37536 :   return can_be_handled (range, bitmap_count_bits (dest_bbs));
    1402                 :            : }
    1403                 :            : 
    1404                 :            : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
    1405                 :            :    transformation.  */
    1406                 :            : 
    1407                 :            : bool
    1408                 :      27175 : bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
    1409                 :            : {
    1410                 :      27175 :   return (((uniq == 1 && count >= 3)
    1411                 :      26065 :            || (uniq == 2 && count >= 5)
    1412                 :      53114 :            || (uniq == 3 && count >= 6)));
    1413                 :            : }
    1414                 :            : 
    1415                 :            : /* Return true if cluster starting at START and ending at END (inclusive)
    1416                 :            :    is profitable transformation.  */
    1417                 :            : 
    1418                 :            : bool
    1419                 :      19772 : bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
    1420                 :            :                                  unsigned start, unsigned end)
    1421                 :            : {
    1422                 :            :   /* Single case bail out.  */
    1423                 :      19772 :   if (start == end)
    1424                 :            :     return false;
    1425                 :            : 
    1426                 :      17636 :   auto_bitmap dest_bbs;
    1427                 :            : 
    1428                 :      59763 :   for (unsigned i = start; i <= end; i++)
    1429                 :            :     {
    1430                 :      42127 :       simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
    1431                 :      42127 :       bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
    1432                 :            :     }
    1433                 :            : 
    1434                 :      17636 :   unsigned uniq = bitmap_count_bits (dest_bbs);
    1435                 :      17636 :   unsigned count = end - start + 1;
    1436                 :      17636 :   return is_beneficial (count, uniq);
    1437                 :            : }
    1438                 :            : 
    1439                 :            : /* Comparison function for qsort to order bit tests by decreasing
    1440                 :            :    probability of execution.  */
    1441                 :            : 
    1442                 :            : int
    1443                 :         49 : case_bit_test::cmp (const void *p1, const void *p2)
    1444                 :            : {
    1445                 :         49 :   const case_bit_test *const d1 = (const case_bit_test *) p1;
    1446                 :         49 :   const case_bit_test *const d2 = (const case_bit_test *) p2;
    1447                 :            : 
    1448                 :         49 :   if (d2->bits != d1->bits)
    1449                 :         16 :     return d2->bits - d1->bits;
    1450                 :            : 
    1451                 :            :   /* Stabilize the sort.  */
    1452                 :         33 :   return (LABEL_DECL_UID (CASE_LABEL (d2->label))
    1453                 :         33 :           - LABEL_DECL_UID (CASE_LABEL (d1->label)));
    1454                 :            : }
    1455                 :            : 
    1456                 :            : /*  Expand a switch statement by a short sequence of bit-wise
    1457                 :            :     comparisons.  "switch(x)" is effectively converted into
    1458                 :            :     "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
    1459                 :            :     integer constants.
    1460                 :            : 
    1461                 :            :     INDEX_EXPR is the value being switched on.
    1462                 :            : 
    1463                 :            :     MINVAL is the lowest case value of in the case nodes,
    1464                 :            :     and RANGE is highest value minus MINVAL.  MINVAL and RANGE
    1465                 :            :     are not guaranteed to be of the same type as INDEX_EXPR
    1466                 :            :     (the gimplifier doesn't change the type of case label values,
    1467                 :            :     and MINVAL and RANGE are derived from those values).
    1468                 :            :     MAXVAL is MINVAL + RANGE.
    1469                 :            : 
    1470                 :            :     There *MUST* be max_case_bit_tests or less unique case
    1471                 :            :     node targets.  */
    1472                 :            : 
    1473                 :            : void
    1474                 :        546 : bit_test_cluster::emit (tree index_expr, tree index_type,
    1475                 :            :                         tree, basic_block default_bb)
    1476                 :            : {
    1477                 :       1638 :   case_bit_test test[m_max_case_bit_tests] = { {} };
    1478                 :        546 :   unsigned int i, j, k;
    1479                 :        546 :   unsigned int count;
    1480                 :            : 
    1481                 :        546 :   tree unsigned_index_type = range_check_type (index_type);
    1482                 :            : 
    1483                 :        546 :   gimple_stmt_iterator gsi;
    1484                 :        546 :   gassign *shift_stmt;
    1485                 :            : 
    1486                 :        546 :   tree idx, tmp, csui;
    1487                 :        546 :   tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
    1488                 :        546 :   tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
    1489                 :        546 :   tree word_mode_one = fold_convert (word_type_node, integer_one_node);
    1490                 :        546 :   int prec = TYPE_PRECISION (word_type_node);
    1491                 :        661 :   wide_int wone = wi::one (prec);
    1492                 :            : 
    1493                 :        546 :   tree minval = get_low ();
    1494                 :        546 :   tree maxval = get_high ();
    1495                 :        546 :   tree range = int_const_binop (MINUS_EXPR, maxval, minval);
    1496                 :        546 :   unsigned HOST_WIDE_INT bt_range = get_range (minval, maxval);
    1497                 :            : 
    1498                 :            :   /* Go through all case labels, and collect the case labels, profile
    1499                 :            :      counts, and other information we need to build the branch tests.  */
    1500                 :        546 :   count = 0;
    1501                 :       4806 :   for (i = 0; i < m_cases.length (); i++)
    1502                 :            :     {
    1503                 :       1857 :       unsigned int lo, hi;
    1504                 :       1857 :       simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
    1505                 :       1885 :       for (k = 0; k < count; k++)
    1506                 :       1329 :         if (n->m_case_bb == test[k].target_bb)
    1507                 :            :           break;
    1508                 :            : 
    1509                 :       1857 :       if (k == count)
    1510                 :            :         {
    1511                 :        556 :           gcc_checking_assert (count < m_max_case_bit_tests);
    1512                 :        556 :           test[k].mask = wi::zero (prec);
    1513                 :        556 :           test[k].target_bb = n->m_case_bb;
    1514                 :        556 :           test[k].label = n->m_case_label_expr;
    1515                 :        556 :           test[k].bits = 0;
    1516                 :        556 :           count++;
    1517                 :            :         }
    1518                 :            : 
    1519                 :       1857 :       test[k].bits += n->get_range (n->get_low (), n->get_high ());
    1520                 :            : 
    1521                 :       1857 :       lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
    1522                 :       1857 :       if (n->get_high () == NULL_TREE)
    1523                 :            :         hi = lo;
    1524                 :            :       else
    1525                 :       1857 :         hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
    1526                 :            :                                             minval));
    1527                 :            : 
    1528                 :       4495 :       for (j = lo; j <= hi; j++)
    1529                 :       2638 :         test[k].mask |= wi::lshift (wone, j);
    1530                 :            :     }
    1531                 :            : 
    1532                 :        546 :   qsort (test, count, sizeof (*test), case_bit_test::cmp);
    1533                 :            : 
    1534                 :            :   /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
    1535                 :            :      the minval subtractions, but it might make the mask constants more
    1536                 :            :      expensive.  So, compare the costs.  */
    1537                 :        546 :   if (compare_tree_int (minval, 0) > 0
    1538                 :       1054 :       && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
    1539                 :            :     {
    1540                 :        357 :       int cost_diff;
    1541                 :        357 :       HOST_WIDE_INT m = tree_to_uhwi (minval);
    1542                 :        357 :       rtx reg = gen_raw_REG (word_mode, 10000);
    1543                 :        357 :       bool speed_p = optimize_insn_for_speed_p ();
    1544                 :        357 :       cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
    1545                 :            :                                               GEN_INT (-m)), speed_p);
    1546                 :        714 :       for (i = 0; i < count; i++)
    1547                 :            :         {
    1548                 :        357 :           rtx r = immed_wide_int_const (test[i].mask, word_mode);
    1549                 :        357 :           cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
    1550                 :            :                                      word_mode, speed_p);
    1551                 :        357 :           r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
    1552                 :        357 :           cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
    1553                 :            :                                      word_mode, speed_p);
    1554                 :            :         }
    1555                 :        357 :       if (cost_diff > 0)
    1556                 :            :         {
    1557                 :        714 :           for (i = 0; i < count; i++)
    1558                 :        357 :             test[i].mask = wi::lshift (test[i].mask, m);
    1559                 :        357 :           minval = build_zero_cst (TREE_TYPE (minval));
    1560                 :        357 :           range = maxval;
    1561                 :            :         }
    1562                 :            :     }
    1563                 :            : 
    1564                 :            :   /* Now build the test-and-branch code.  */
    1565                 :            : 
    1566                 :        546 :   gsi = gsi_last_bb (m_case_bb);
    1567                 :            : 
    1568                 :            :   /* idx = (unsigned)x - minval.  */
    1569                 :        546 :   idx = fold_convert (unsigned_index_type, index_expr);
    1570                 :        546 :   idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
    1571                 :            :                      fold_convert (unsigned_index_type, minval));
    1572                 :        546 :   idx = force_gimple_operand_gsi (&gsi, idx,
    1573                 :            :                                   /*simple=*/true, NULL_TREE,
    1574                 :            :                                   /*before=*/true, GSI_SAME_STMT);
    1575                 :            : 
    1576                 :        546 :   if (m_handles_entire_switch)
    1577                 :            :     {
    1578                 :            :       /* if (idx > range) goto default */
    1579                 :        459 :       range
    1580                 :        459 :         = force_gimple_operand_gsi (&gsi,
    1581                 :            :                                     fold_convert (unsigned_index_type, range),
    1582                 :            :                                     /*simple=*/true, NULL_TREE,
    1583                 :            :                                     /*before=*/true, GSI_SAME_STMT);
    1584                 :        459 :       tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
    1585                 :        459 :       basic_block new_bb
    1586                 :        459 :         = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb,
    1587                 :            :                                          profile_probability::unlikely ());
    1588                 :        918 :       gsi = gsi_last_bb (new_bb);
    1589                 :            :     }
    1590                 :            : 
    1591                 :            :   /* csui = (1 << (word_mode) idx) */
    1592                 :        546 :   csui = make_ssa_name (word_type_node);
    1593                 :        546 :   tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
    1594                 :            :                      fold_convert (word_type_node, idx));
    1595                 :        546 :   tmp = force_gimple_operand_gsi (&gsi, tmp,
    1596                 :            :                                   /*simple=*/false, NULL_TREE,
    1597                 :            :                                   /*before=*/true, GSI_SAME_STMT);
    1598                 :        546 :   shift_stmt = gimple_build_assign (csui, tmp);
    1599                 :        546 :   gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
    1600                 :        546 :   update_stmt (shift_stmt);
    1601                 :            : 
    1602                 :        546 :   profile_probability prob = profile_probability::always ();
    1603                 :            : 
    1604                 :            :   /* for each unique set of cases:
    1605                 :            :        if (const & csui) goto target  */
    1606                 :       1102 :   for (k = 0; k < count; k++)
    1607                 :            :     {
    1608                 :        556 :       prob = profile_probability::always ().apply_scale (test[k].bits,
    1609                 :        556 :                                                          bt_range);
    1610                 :        556 :       bt_range -= test[k].bits;
    1611                 :        556 :       tmp = wide_int_to_tree (word_type_node, test[k].mask);
    1612                 :        556 :       tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
    1613                 :        556 :       tmp = force_gimple_operand_gsi (&gsi, tmp,
    1614                 :            :                                       /*simple=*/true, NULL_TREE,
    1615                 :            :                                       /*before=*/true, GSI_SAME_STMT);
    1616                 :        556 :       tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
    1617                 :        556 :       basic_block new_bb
    1618                 :        556 :         = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb, prob);
    1619                 :       1112 :       gsi = gsi_last_bb (new_bb);
    1620                 :            :     }
    1621                 :            : 
    1622                 :            :   /* We should have removed all edges now.  */
    1623                 :        546 :   gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
    1624                 :            : 
    1625                 :            :   /* If nothing matched, go to the default label.  */
    1626                 :        546 :   edge e = make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
    1627                 :        546 :   e->probability = profile_probability::always ();
    1628                 :        546 : }
    1629                 :            : 
    1630                 :            : /* Split the basic block at the statement pointed to by GSIP, and insert
    1631                 :            :    a branch to the target basic block of E_TRUE conditional on tree
    1632                 :            :    expression COND.
    1633                 :            : 
    1634                 :            :    It is assumed that there is already an edge from the to-be-split
    1635                 :            :    basic block to E_TRUE->dest block.  This edge is removed, and the
    1636                 :            :    profile information on the edge is re-used for the new conditional
    1637                 :            :    jump.
    1638                 :            : 
    1639                 :            :    The CFG is updated.  The dominator tree will not be valid after
    1640                 :            :    this transformation, but the immediate dominators are updated if
    1641                 :            :    UPDATE_DOMINATORS is true.
    1642                 :            : 
    1643                 :            :    Returns the newly created basic block.  */
    1644                 :            : 
    1645                 :            : basic_block
    1646                 :       1015 : bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
    1647                 :            :                                                  tree cond, basic_block case_bb,
    1648                 :            :                                                  profile_probability prob)
    1649                 :            : {
    1650                 :       1015 :   tree tmp;
    1651                 :       1015 :   gcond *cond_stmt;
    1652                 :       1015 :   edge e_false;
    1653                 :       1015 :   basic_block new_bb, split_bb = gsi_bb (*gsip);
    1654                 :            : 
    1655                 :       1015 :   edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
    1656                 :       1015 :   e_true->probability = prob;
    1657                 :       1015 :   gcc_assert (e_true->src == split_bb);
    1658                 :            : 
    1659                 :       1015 :   tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
    1660                 :            :                                   /*before=*/true, GSI_SAME_STMT);
    1661                 :       1015 :   cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
    1662                 :       1015 :   gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
    1663                 :            : 
    1664                 :       1015 :   e_false = split_block (split_bb, cond_stmt);
    1665                 :       1015 :   new_bb = e_false->dest;
    1666                 :       1015 :   redirect_edge_pred (e_true, split_bb);
    1667                 :            : 
    1668                 :       1015 :   e_false->flags &= ~EDGE_FALLTHRU;
    1669                 :       1015 :   e_false->flags |= EDGE_FALSE_VALUE;
    1670                 :       1015 :   e_false->probability = e_true->probability.invert ();
    1671                 :       1015 :   new_bb->count = e_false->count ();
    1672                 :            : 
    1673                 :       1015 :   return new_bb;
    1674                 :            : }
    1675                 :            : 
    1676                 :            : /* Compute the number of case labels that correspond to each outgoing edge of
    1677                 :            :    switch statement.  Record this information in the aux field of the edge.  */
    1678                 :            : 
    1679                 :            : void
    1680                 :      28489 : switch_decision_tree::compute_cases_per_edge ()
    1681                 :            : {
    1682                 :      28489 :   reset_out_edges_aux (m_switch);
    1683                 :      28489 :   int ncases = gimple_switch_num_labels (m_switch);
    1684                 :     162407 :   for (int i = ncases - 1; i >= 1; --i)
    1685                 :            :     {
    1686                 :     133918 :       edge case_edge = gimple_switch_edge (cfun, m_switch, i);
    1687                 :     133918 :       case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
    1688                 :            :     }
    1689                 :      28489 : }
    1690                 :            : 
    1691                 :            : /* Analyze switch statement and return true when the statement is expanded
    1692                 :            :    as decision tree.  */
    1693                 :            : 
    1694                 :            : bool
    1695                 :      28489 : switch_decision_tree::analyze_switch_statement ()
    1696                 :            : {
    1697                 :      28489 :   unsigned l = gimple_switch_num_labels (m_switch);
    1698                 :      28489 :   basic_block bb = gimple_bb (m_switch);
    1699                 :      28489 :   auto_vec<cluster *> clusters;
    1700                 :      28489 :   clusters.create (l - 1);
    1701                 :            : 
    1702                 :      28489 :   basic_block default_bb = gimple_switch_default_bb (cfun, m_switch);
    1703                 :      28489 :   m_case_bbs.reserve (l);
    1704                 :      28489 :   m_case_bbs.quick_push (default_bb);
    1705                 :            : 
    1706                 :      28489 :   compute_cases_per_edge ();
    1707                 :            : 
    1708                 :     162407 :   for (unsigned i = 1; i < l; i++)
    1709                 :            :     {
    1710                 :     133918 :       tree elt = gimple_switch_label (m_switch, i);
    1711                 :     133918 :       tree lab = CASE_LABEL (elt);
    1712                 :     133918 :       basic_block case_bb = label_to_block (cfun, lab);
    1713                 :     133918 :       edge case_edge = find_edge (bb, case_bb);
    1714                 :     133918 :       tree low = CASE_LOW (elt);
    1715                 :     133918 :       tree high = CASE_HIGH (elt);
    1716                 :            : 
    1717                 :     133918 :       profile_probability p
    1718                 :     133918 :         = case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
    1719                 :     133918 :       clusters.quick_push (new simple_cluster (low, high, elt, case_edge->dest,
    1720                 :     133918 :                                                p));
    1721                 :     133918 :       m_case_bbs.quick_push (case_edge->dest);
    1722                 :            :     }
    1723                 :            : 
    1724                 :      28489 :   reset_out_edges_aux (m_switch);
    1725                 :            : 
    1726                 :            :   /* Find jump table clusters.  */
    1727                 :      28489 :   vec<cluster *> output = jump_table_cluster::find_jump_tables (clusters);
    1728                 :            : 
    1729                 :            :   /* Find bit test clusters.  */
    1730                 :      28489 :   vec<cluster *> output2;
    1731                 :      56978 :   auto_vec<cluster *> tmp;
    1732                 :      28489 :   output2.create (1);
    1733                 :      28489 :   tmp.create (1);
    1734                 :            : 
    1735                 :     170480 :   for (unsigned i = 0; i < output.length (); i++)
    1736                 :            :     {
    1737                 :      56751 :       cluster *c = output[i];
    1738                 :      56751 :       if (c->get_type () != SIMPLE_CASE)
    1739                 :            :         {
    1740                 :       9871 :           if (!tmp.is_empty ())
    1741                 :            :             {
    1742                 :        125 :               vec<cluster *> n = bit_test_cluster::find_bit_tests (tmp);
    1743                 :        125 :               output2.safe_splice (n);
    1744                 :        125 :               n.release ();
    1745                 :        125 :               tmp.truncate (0);
    1746                 :            :             }
    1747                 :       9871 :           output2.safe_push (c);
    1748                 :            :         }
    1749                 :            :       else
    1750                 :      46880 :         tmp.safe_push (c);
    1751                 :            :     }
    1752                 :            : 
    1753                 :            :   /* We still can have a temporary vector to test.  */
    1754                 :      28489 :   if (!tmp.is_empty ())
    1755                 :            :     {
    1756                 :      18771 :       vec<cluster *> n = bit_test_cluster::find_bit_tests (tmp);
    1757                 :      18771 :       output2.safe_splice (n);
    1758                 :      37542 :       n.release ();
    1759                 :            :     }
    1760                 :            : 
    1761                 :      28489 :   if (dump_file)
    1762                 :            :     {
    1763                 :         17 :       fprintf (dump_file, ";; GIMPLE switch case clusters: ");
    1764                 :        144 :       for (unsigned i = 0; i < output2.length (); i++)
    1765                 :         55 :         output2[i]->dump (dump_file, dump_flags & TDF_DETAILS);
    1766                 :         17 :       fprintf (dump_file, "\n");
    1767                 :            :     }
    1768                 :            : 
    1769                 :      28489 :   output.release ();
    1770                 :            : 
    1771                 :      28489 :   bool expanded = try_switch_expansion (output2);
    1772                 :            : 
    1773                 :     167858 :   for (unsigned i = 0; i < output2.length (); i++)
    1774                 :      55440 :     delete output2[i];
    1775                 :            : 
    1776                 :      28489 :   output2.release ();
    1777                 :            : 
    1778                 :      28489 :   return expanded;
    1779                 :            : }
    1780                 :            : 
    1781                 :            : /* Attempt to expand CLUSTERS as a decision tree.  Return true when
    1782                 :            :    expanded.  */
    1783                 :            : 
    1784                 :            : bool
    1785                 :      28489 : switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
    1786                 :            : {
    1787                 :      28489 :   tree index_expr = gimple_switch_index (m_switch);
    1788                 :      28489 :   tree index_type = TREE_TYPE (index_expr);
    1789                 :      28489 :   basic_block bb = gimple_bb (m_switch);
    1790                 :            : 
    1791                 :      28489 :   if (gimple_switch_num_labels (m_switch) == 1
    1792                 :      28489 :       || range_check_type (index_type) == NULL_TREE)
    1793                 :          0 :     return false;
    1794                 :            : 
    1795                 :            :   /* Find the default case target label.  */
    1796                 :      28489 :   edge default_edge = gimple_switch_default_edge (cfun, m_switch);
    1797                 :      28489 :   m_default_bb = default_edge->dest;
    1798                 :            : 
    1799                 :            :   /* Do the insertion of a case label into m_case_list.  The labels are
    1800                 :            :      fed to us in descending order from the sorted vector of case labels used
    1801                 :            :      in the tree part of the middle end.  So the list we construct is
    1802                 :            :      sorted in ascending order.  */
    1803                 :            : 
    1804                 :     112418 :   for (int i = clusters.length () - 1; i >= 0; i--)
    1805                 :            :     {
    1806                 :      55440 :       case_tree_node *r = m_case_list;
    1807                 :      55440 :       m_case_list = m_case_node_pool.allocate ();
    1808                 :      55440 :       m_case_list->m_right = r;
    1809                 :      55440 :       m_case_list->m_c = clusters[i];
    1810                 :            :     }
    1811                 :            : 
    1812                 :      28489 :   record_phi_operand_mapping ();
    1813                 :            : 
    1814                 :            :   /* Split basic block that contains the gswitch statement.  */
    1815                 :      28489 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    1816                 :      28489 :   edge e;
    1817                 :      28489 :   if (gsi_end_p (gsi))
    1818                 :          0 :     e = split_block_after_labels (bb);
    1819                 :            :   else
    1820                 :            :     {
    1821                 :      28489 :       gsi_prev (&gsi);
    1822                 :      28489 :       e = split_block (bb, gsi_stmt (gsi));
    1823                 :            :     }
    1824                 :      28489 :   bb = split_edge (e);
    1825                 :            : 
    1826                 :            :   /* Create new basic blocks for non-case clusters where specific expansion
    1827                 :            :      needs to happen.  */
    1828                 :     167858 :   for (unsigned i = 0; i < clusters.length (); i++)
    1829                 :      55440 :     if (clusters[i]->get_type () != SIMPLE_CASE)
    1830                 :            :       {
    1831                 :      10417 :         clusters[i]->m_case_bb = create_empty_bb (bb);
    1832                 :      10417 :         clusters[i]->m_case_bb->count = bb->count;
    1833                 :      10417 :         clusters[i]->m_case_bb->loop_father = bb->loop_father;
    1834                 :            :       }
    1835                 :            : 
    1836                 :            :   /* Do not do an extra work for a single cluster.  */
    1837                 :      28489 :   if (clusters.length () == 1
    1838                 :      28489 :       && clusters[0]->get_type () != SIMPLE_CASE)
    1839                 :            :     {
    1840                 :      10058 :       cluster *c = clusters[0];
    1841                 :      10058 :       c->emit (index_expr, index_type,
    1842                 :      10058 :                gimple_switch_default_label (m_switch), m_default_bb);
    1843                 :      10058 :       redirect_edge_succ (single_succ_edge (bb), c->m_case_bb);
    1844                 :            :     }
    1845                 :            :   else
    1846                 :            :     {
    1847                 :      18431 :       emit (bb, index_expr, default_edge->probability, index_type);
    1848                 :            : 
    1849                 :            :       /* Emit cluster-specific switch handling.  */
    1850                 :     127626 :       for (unsigned i = 0; i < clusters.length (); i++)
    1851                 :      45382 :         if (clusters[i]->get_type () != SIMPLE_CASE)
    1852                 :        718 :           clusters[i]->emit (index_expr, index_type,
    1853                 :        359 :                              gimple_switch_default_label (m_switch),
    1854                 :        359 :                              m_default_bb);
    1855                 :            :     }
    1856                 :            : 
    1857                 :      28489 :   fix_phi_operands_for_edges ();
    1858                 :            : 
    1859                 :      28489 :   return true;
    1860                 :            : }
    1861                 :            : 
    1862                 :            : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
    1863                 :            :    and used in a label basic block.  */
    1864                 :            : 
    1865                 :            : void
    1866                 :      28489 : switch_decision_tree::record_phi_operand_mapping ()
    1867                 :            : {
    1868                 :      28489 :   basic_block switch_bb = gimple_bb (m_switch);
    1869                 :            :   /* Record all PHI nodes that have to be fixed after conversion.  */
    1870                 :     381792 :   for (unsigned i = 0; i < m_case_bbs.length (); i++)
    1871                 :            :     {
    1872                 :     162407 :       gphi_iterator gsi;
    1873                 :     162407 :       basic_block bb = m_case_bbs[i];
    1874                 :     189780 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1875                 :            :         {
    1876                 :      27373 :           gphi *phi = gsi.phi ();
    1877                 :            : 
    1878                 :      93194 :           for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
    1879                 :            :             {
    1880                 :      93194 :               basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
    1881                 :      93194 :               if (phi_src_bb == switch_bb)
    1882                 :            :                 {
    1883                 :      27373 :                   tree def = gimple_phi_arg_def (phi, i);
    1884                 :      27373 :                   tree result = gimple_phi_result (phi);
    1885                 :      27373 :                   m_phi_mapping.put (result, def);
    1886                 :      27373 :                   break;
    1887                 :            :                 }
    1888                 :            :             }
    1889                 :            :         }
    1890                 :            :     }
    1891                 :      28489 : }
    1892                 :            : 
    1893                 :            : /* Append new operands to PHI statements that were introduced due to
    1894                 :            :    addition of new edges to case labels.  */
    1895                 :            : 
    1896                 :            : void
    1897                 :      28489 : switch_decision_tree::fix_phi_operands_for_edges ()
    1898                 :            : {
    1899                 :      28489 :   gphi_iterator gsi;
    1900                 :            : 
    1901                 :     381792 :   for (unsigned i = 0; i < m_case_bbs.length (); i++)
    1902                 :            :     {
    1903                 :     162407 :       basic_block bb = m_case_bbs[i];
    1904                 :     189780 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1905                 :            :         {
    1906                 :      27373 :           gphi *phi = gsi.phi ();
    1907                 :     185339 :           for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
    1908                 :            :             {
    1909                 :     157966 :               tree def = gimple_phi_arg_def (phi, j);
    1910                 :     157966 :               if (def == NULL_TREE)
    1911                 :            :                 {
    1912                 :      29335 :                   edge e = gimple_phi_arg_edge (phi, j);
    1913                 :      29335 :                   tree *definition
    1914                 :      29335 :                     = m_phi_mapping.get (gimple_phi_result (phi));
    1915                 :          0 :                   gcc_assert (definition);
    1916                 :      29335 :                   add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
    1917                 :            :                 }
    1918                 :            :             }
    1919                 :            :         }
    1920                 :            :     }
    1921                 :      28489 : }
    1922                 :            : 
    1923                 :            : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
    1924                 :            :    one of the labels in CASE_LIST or to the DEFAULT_LABEL.
    1925                 :            : 
    1926                 :            :    We generate a binary decision tree to select the appropriate target
    1927                 :            :    code.  */
    1928                 :            : 
    1929                 :            : void
    1930                 :      18431 : switch_decision_tree::emit (basic_block bb, tree index_expr,
    1931                 :            :                             profile_probability default_prob, tree index_type)
    1932                 :            : {
    1933                 :      18431 :   balance_case_nodes (&m_case_list, NULL);
    1934                 :            : 
    1935                 :      18431 :   if (dump_file)
    1936                 :         10 :     dump_function_to_file (current_function_decl, dump_file, dump_flags);
    1937                 :      18431 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1938                 :            :     {
    1939                 :          0 :       int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
    1940                 :          0 :       fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
    1941                 :          0 :       gcc_assert (m_case_list != NULL);
    1942                 :          0 :       dump_case_nodes (dump_file, m_case_list, indent_step, 0);
    1943                 :            :     }
    1944                 :            : 
    1945                 :      36862 :   bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type,
    1946                 :      18431 :                         gimple_location (m_switch));
    1947                 :            : 
    1948                 :      18431 :   if (bb)
    1949                 :      17638 :     emit_jump (bb, m_default_bb);
    1950                 :            : 
    1951                 :            :   /* Remove all edges and do just an edge that will reach default_bb.  */
    1952                 :      18431 :   bb = gimple_bb (m_switch);
    1953                 :      18431 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    1954                 :      18431 :   gsi_remove (&gsi, true);
    1955                 :            : 
    1956                 :      18431 :   delete_basic_block (bb);
    1957                 :      18431 : }
    1958                 :            : 
    1959                 :            : /* Take an ordered list of case nodes
    1960                 :            :    and transform them into a near optimal binary tree,
    1961                 :            :    on the assumption that any target code selection value is as
    1962                 :            :    likely as any other.
    1963                 :            : 
    1964                 :            :    The transformation is performed by splitting the ordered
    1965                 :            :    list into two equal sections plus a pivot.  The parts are
    1966                 :            :    then attached to the pivot as left and right branches.  Each
    1967                 :            :    branch is then transformed recursively.  */
    1968                 :            : 
    1969                 :            : void
    1970                 :      32625 : switch_decision_tree::balance_case_nodes (case_tree_node **head,
    1971                 :            :                                           case_tree_node *parent)
    1972                 :            : {
    1973                 :      32625 :   case_tree_node *np;
    1974                 :            : 
    1975                 :      32625 :   np = *head;
    1976                 :      32625 :   if (np)
    1977                 :            :     {
    1978                 :      30719 :       int i = 0;
    1979                 :      30719 :       int ranges = 0;
    1980                 :      30719 :       case_tree_node **npp;
    1981                 :      30719 :       case_tree_node *left;
    1982                 :      30719 :       profile_probability prob = profile_probability::never ();
    1983                 :            : 
    1984                 :            :       /* Count the number of entries on branch.  Also count the ranges.  */
    1985                 :            : 
    1986                 :      94292 :       while (np)
    1987                 :            :         {
    1988                 :      63573 :           if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ()))
    1989                 :            :             ranges++;
    1990                 :            : 
    1991                 :      63573 :           i++;
    1992                 :      63573 :           prob += np->m_c->m_prob;
    1993                 :      63573 :           np = np->m_right;
    1994                 :            :         }
    1995                 :            : 
    1996                 :      30719 :       if (i > 2)
    1997                 :            :         {
    1998                 :            :           /* Split this list if it is long enough for that to help.  */
    1999                 :       7097 :           npp = head;
    2000                 :       7097 :           left = *npp;
    2001                 :       7097 :           profile_probability pivot_prob = prob.apply_scale (1, 2);
    2002                 :            : 
    2003                 :            :           /* Find the place in the list that bisects the list's total cost,
    2004                 :            :              where ranges count as 2.  */
    2005                 :      30851 :           while (1)
    2006                 :            :             {
    2007                 :            :               /* Skip nodes while their probability does not reach
    2008                 :            :                  that amount.  */
    2009                 :      18974 :               prob -= (*npp)->m_c->m_prob;
    2010                 :      18974 :               if ((prob.initialized_p () && prob < pivot_prob)
    2011                 :      27113 :                   || ! (*npp)->m_right)
    2012                 :            :                 break;
    2013                 :      11877 :               npp = &(*npp)->m_right;
    2014                 :            :             }
    2015                 :            : 
    2016                 :       7097 :           np = *npp;
    2017                 :       7097 :           *npp = 0;
    2018                 :       7097 :           *head = np;
    2019                 :       7097 :           np->m_parent = parent;
    2020                 :       7097 :           np->m_left = left == np ? NULL : left;
    2021                 :            : 
    2022                 :            :           /* Optimize each of the two split parts.  */
    2023                 :       7097 :           balance_case_nodes (&np->m_left, np);
    2024                 :       7097 :           balance_case_nodes (&np->m_right, np);
    2025                 :       7097 :           np->m_c->m_subtree_prob = np->m_c->m_prob;
    2026                 :       7097 :           if (np->m_left)
    2027                 :       7006 :             np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
    2028                 :       7097 :           if (np->m_right)
    2029                 :       5282 :             np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
    2030                 :            :         }
    2031                 :            :       else
    2032                 :            :         {
    2033                 :            :           /* Else leave this branch as one level,
    2034                 :            :              but fill in `parent' fields.  */
    2035                 :      23622 :           np = *head;
    2036                 :      23622 :           np->m_parent = parent;
    2037                 :      23622 :           np->m_c->m_subtree_prob = np->m_c->m_prob;
    2038                 :      38285 :           for (; np->m_right; np = np->m_right)
    2039                 :            :             {
    2040                 :      14663 :               np->m_right->m_parent = np;
    2041                 :      14663 :               (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
    2042                 :            :             }
    2043                 :            :         }
    2044                 :            :     }
    2045                 :      32625 : }
    2046                 :            : 
    2047                 :            : /* Dump ROOT, a list or tree of case nodes, to file.  */
    2048                 :            : 
    2049                 :            : void
    2050                 :          0 : switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
    2051                 :            :                                        int indent_step, int indent_level)
    2052                 :            : {
    2053                 :          0 :   if (root == 0)
    2054                 :          0 :     return;
    2055                 :          0 :   indent_level++;
    2056                 :            : 
    2057                 :          0 :   dump_case_nodes (f, root->m_left, indent_step, indent_level);
    2058                 :            : 
    2059                 :          0 :   fputs (";; ", f);
    2060                 :          0 :   fprintf (f, "%*s", indent_step * indent_level, "");
    2061                 :          0 :   root->m_c->dump (f);
    2062                 :          0 :   root->m_c->m_prob.dump (f);
    2063                 :          0 :   fputs (" subtree: ", f);
    2064                 :          0 :   root->m_c->m_subtree_prob.dump (f);
    2065                 :          0 :   fputs (")\n", f);
    2066                 :            : 
    2067                 :          0 :   dump_case_nodes (f, root->m_right, indent_step, indent_level);
    2068                 :            : }
    2069                 :            : 
    2070                 :            : 
    2071                 :            : /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
    2072                 :            : 
    2073                 :            : void
    2074                 :      21773 : switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
    2075                 :            : {
    2076                 :      21773 :   edge e = single_succ_edge (bb);
    2077                 :      21773 :   redirect_edge_succ (e, case_bb);
    2078                 :      21773 : }
    2079                 :            : 
    2080                 :            : /* Generate code to compare OP0 with OP1 so that the condition codes are
    2081                 :            :    set and to jump to LABEL_BB if the condition is true.
    2082                 :            :    COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
    2083                 :            :    PROB is the probability of jumping to LABEL_BB.  */
    2084                 :            : 
    2085                 :            : basic_block
    2086                 :       7891 : switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
    2087                 :            :                                                tree op1, tree_code comparison,
    2088                 :            :                                                basic_block label_bb,
    2089                 :            :                                                profile_probability prob,
    2090                 :            :                                                location_t loc)
    2091                 :            : {
    2092                 :            :   // TODO: it's once called with lhs != index.
    2093                 :       7891 :   op1 = fold_convert (TREE_TYPE (op0), op1);
    2094                 :            : 
    2095                 :       7891 :   gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
    2096                 :       7891 :   gimple_set_location (cond, loc);
    2097                 :       7891 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2098                 :       7891 :   gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
    2099                 :            : 
    2100                 :       7891 :   gcc_assert (single_succ_p (bb));
    2101                 :            : 
    2102                 :            :   /* Make a new basic block where false branch will take place.  */
    2103                 :       7891 :   edge false_edge = split_block (bb, cond);
    2104                 :       7891 :   false_edge->flags = EDGE_FALSE_VALUE;
    2105                 :       7891 :   false_edge->probability = prob.invert ();
    2106                 :            : 
    2107                 :       7891 :   edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
    2108                 :       7891 :   true_edge->probability = prob;
    2109                 :            : 
    2110                 :       7891 :   return false_edge->dest;
    2111                 :            : }
    2112                 :            : 
    2113                 :            : /* Generate code to jump to LABEL if OP0 and OP1 are equal.
    2114                 :            :    PROB is the probability of jumping to LABEL_BB.
    2115                 :            :    BB is a basic block where the new condition will be placed.  */
    2116                 :            : 
    2117                 :            : basic_block
    2118                 :      43108 : switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
    2119                 :            :                                         basic_block label_bb,
    2120                 :            :                                         profile_probability prob,
    2121                 :            :                                         location_t loc)
    2122                 :            : {
    2123                 :      43108 :   op1 = fold_convert (TREE_TYPE (op0), op1);
    2124                 :            : 
    2125                 :      43108 :   gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
    2126                 :      43108 :   gimple_set_location (cond, loc);
    2127                 :      43108 :   gimple_stmt_iterator gsi = gsi_last_bb (bb);
    2128                 :      43108 :   gsi_insert_before (&gsi, cond, GSI_SAME_STMT);
    2129                 :            : 
    2130                 :      43108 :   gcc_assert (single_succ_p (bb));
    2131                 :            : 
    2132                 :            :   /* Make a new basic block where false branch will take place.  */
    2133                 :      43108 :   edge false_edge = split_block (bb, cond);
    2134                 :      43108 :   false_edge->flags = EDGE_FALSE_VALUE;
    2135                 :      43108 :   false_edge->probability = prob.invert ();
    2136                 :            : 
    2137                 :      43108 :   edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
    2138                 :      43108 :   true_edge->probability = prob;
    2139                 :            : 
    2140                 :      43108 :   return false_edge->dest;
    2141                 :            : }
    2142                 :            : 
    2143                 :            : /* Emit step-by-step code to select a case for the value of INDEX.
    2144                 :            :    The thus generated decision tree follows the form of the
    2145                 :            :    case-node binary tree NODE, whose nodes represent test conditions.
    2146                 :            :    DEFAULT_PROB is probability of cases leading to default BB.
    2147                 :            :    INDEX_TYPE is the type of the index of the switch.  */
    2148                 :            : 
    2149                 :            : basic_block
    2150                 :      27390 : switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
    2151                 :            :                                        case_tree_node *node,
    2152                 :            :                                        profile_probability default_prob,
    2153                 :            :                                        tree index_type, location_t loc)
    2154                 :            : {
    2155                 :      27390 :   profile_probability p;
    2156                 :            : 
    2157                 :            :   /* If node is null, we are done.  */
    2158                 :      27390 :   if (node == NULL)
    2159                 :            :     return bb;
    2160                 :            : 
    2161                 :            :   /* Single value case.  */
    2162                 :      26445 :   if (node->m_c->is_single_value_p ())
    2163                 :            :     {
    2164                 :            :       /* Node is single valued.  First see if the index expression matches
    2165                 :            :          this node and then check our children, if any.  */
    2166                 :      24171 :       p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
    2167                 :      24171 :       bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
    2168                 :            :                              node->m_c->m_case_bb, p, loc);
    2169                 :            :       /* Since this case is taken at this point, reduce its weight from
    2170                 :            :          subtree_weight.  */
    2171                 :      24171 :       node->m_c->m_subtree_prob -= p;
    2172                 :            : 
    2173                 :      24171 :       if (node->m_left != NULL && node->m_right != NULL)
    2174                 :            :         {
    2175                 :            :           /* 1) the node has both children
    2176                 :            : 
    2177                 :            :              If both children are single-valued cases with no
    2178                 :            :              children, finish up all the work.  This way, we can save
    2179                 :            :              one ordered comparison.  */
    2180                 :            : 
    2181                 :       4864 :           if (!node->m_left->has_child ()
    2182                 :       2992 :               && node->m_left->m_c->is_single_value_p ()
    2183                 :       2893 :               && !node->m_right->has_child ()
    2184                 :       2749 :               && node->m_right->m_c->is_single_value_p ())
    2185                 :            :             {
    2186                 :       2685 :               p = (node->m_right->m_c->m_prob
    2187                 :       2685 :                    / (node->m_c->m_subtree_prob + default_prob));
    2188                 :       2685 :               bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
    2189                 :            :                                      node->m_right->m_c->m_case_bb, p, loc);
    2190                 :            : 
    2191                 :       2685 :               p = (node->m_left->m_c->m_prob
    2192                 :       2685 :                    / (node->m_c->m_subtree_prob + default_prob));
    2193                 :       2685 :               bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
    2194                 :            :                                      node->m_left->m_c->m_case_bb, p, loc);
    2195                 :            :             }
    2196                 :            :           else
    2197                 :            :             {
    2198                 :            :               /* Branch to a label where we will handle it later.  */
    2199                 :       2179 :               basic_block test_bb = split_edge (single_succ_edge (bb));
    2200                 :       2179 :               redirect_edge_succ (single_pred_edge (test_bb),
    2201                 :       2179 :                                   single_succ_edge (bb)->dest);
    2202                 :            : 
    2203                 :       4358 :               p = ((node->m_right->m_c->m_subtree_prob
    2204                 :       6537 :                     + default_prob.apply_scale (1, 2))
    2205                 :       2179 :                    / (node->m_c->m_subtree_prob + default_prob));
    2206                 :       2179 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2207                 :            :                                             GT_EXPR, test_bb, p, loc);
    2208                 :       2179 :               default_prob = default_prob.apply_scale (1, 2);
    2209                 :            : 
    2210                 :            :               /* Handle the left-hand subtree.  */
    2211                 :       2179 :               bb = emit_case_nodes (bb, index, node->m_left,
    2212                 :            :                                     default_prob, index_type, loc);
    2213                 :            : 
    2214                 :            :               /* If the left-hand subtree fell through,
    2215                 :            :                  don't let it fall into the right-hand subtree.  */
    2216                 :       2179 :               if (bb && m_default_bb)
    2217                 :       2025 :                 emit_jump (bb, m_default_bb);
    2218                 :            : 
    2219                 :       2179 :               bb = emit_case_nodes (test_bb, index, node->m_right,
    2220                 :            :                                     default_prob, index_type, loc);
    2221                 :            :             }
    2222                 :            :         }
    2223                 :      19307 :       else if (node->m_left == NULL && node->m_right != NULL)
    2224                 :            :         {
    2225                 :            :           /* 2) the node has only right child.  */
    2226                 :            : 
    2227                 :            :           /* Here we have a right child but no left so we issue a conditional
    2228                 :            :              branch to default and process the right child.
    2229                 :            : 
    2230                 :            :              Omit the conditional branch to default if the right child
    2231                 :            :              does not have any children and is single valued; it would
    2232                 :            :              cost too much space to save so little time.  */
    2233                 :            : 
    2234                 :      14095 :           if (node->m_right->has_child ()
    2235                 :      14058 :               || !node->m_right->m_c->is_single_value_p ())
    2236                 :            :             {
    2237                 :       1056 :               p = (default_prob.apply_scale (1, 2)
    2238                 :        528 :                    / (node->m_c->m_subtree_prob + default_prob));
    2239                 :        528 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
    2240                 :            :                                             LT_EXPR, m_default_bb, p, loc);
    2241                 :        528 :               default_prob = default_prob.apply_scale (1, 2);
    2242                 :            : 
    2243                 :        528 :               bb = emit_case_nodes (bb, index, node->m_right, default_prob,
    2244                 :            :                                     index_type, loc);
    2245                 :            :             }
    2246                 :            :           else
    2247                 :            :             {
    2248                 :            :               /* We cannot process node->right normally
    2249                 :            :                  since we haven't ruled out the numbers less than
    2250                 :            :                  this node's value.  So handle node->right explicitly.  */
    2251                 :      13567 :               p = (node->m_right->m_c->m_subtree_prob
    2252                 :      13567 :                    / (node->m_c->m_subtree_prob + default_prob));
    2253                 :      13567 :               bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
    2254                 :            :                                      node->m_right->m_c->m_case_bb, p, loc);
    2255                 :            :             }
    2256                 :            :         }
    2257                 :       5212 :       else if (node->m_left != NULL && node->m_right == NULL)
    2258                 :            :         {
    2259                 :            :           /* 3) just one subtree, on the left.  Similar case as previous.  */
    2260                 :            : 
    2261                 :       1747 :           if (node->m_left->has_child ()
    2262                 :          0 :               || !node->m_left->m_c->is_single_value_p ())
    2263                 :            :             {
    2264                 :       3494 :               p = (default_prob.apply_scale (1, 2)
    2265                 :       1747 :                    / (node->m_c->m_subtree_prob + default_prob));
    2266                 :       1747 :               bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2267                 :            :                                             GT_EXPR, m_default_bb, p, loc);
    2268                 :       1747 :                   default_prob = default_prob.apply_scale (1, 2);
    2269                 :            : 
    2270                 :       1747 :               bb = emit_case_nodes (bb, index, node->m_left, default_prob,
    2271                 :            :                                     index_type, loc);
    2272                 :            :             }
    2273                 :            :           else
    2274                 :            :             {
    2275                 :            :               /* We cannot process node->left normally
    2276                 :            :                  since we haven't ruled out the numbers less than
    2277                 :            :                  this node's value.  So handle node->left explicitly.  */
    2278                 :          0 :               p = (node->m_left->m_c->m_subtree_prob
    2279                 :          0 :                    / (node->m_c->m_subtree_prob + default_prob));
    2280                 :          0 :               bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
    2281                 :            :                                      node->m_left->m_c->m_case_bb, p, loc);
    2282                 :            :             }
    2283                 :            :         }
    2284                 :            :     }
    2285                 :            :   else
    2286                 :            :     {
    2287                 :            :       /* Node is a range.  These cases are very similar to those for a single
    2288                 :            :          value, except that we do not start by testing whether this node
    2289                 :            :          is the one to branch to.  */
    2290                 :       3494 :       if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
    2291                 :            :         {
    2292                 :            :           /* Branch to a label where we will handle it later.  */
    2293                 :       1163 :           basic_block test_bb = split_edge (single_succ_edge (bb));
    2294                 :       1163 :           redirect_edge_succ (single_pred_edge (test_bb),
    2295                 :       1163 :                               single_succ_edge (bb)->dest);
    2296                 :            : 
    2297                 :            : 
    2298                 :       1163 :            profile_probability right_prob = profile_probability::never ();
    2299                 :       1163 :            if (node->m_right)
    2300                 :        986 :              right_prob = node->m_right->m_c->m_subtree_prob;
    2301                 :       3489 :           p = ((right_prob + default_prob.apply_scale (1, 2))
    2302                 :       1163 :                / (node->m_c->m_subtree_prob + default_prob));
    2303                 :            : 
    2304                 :       1163 :           bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
    2305                 :            :                                         GT_EXPR, test_bb, p, loc);
    2306                 :       1163 :           default_prob = default_prob.apply_scale (1, 2);
    2307                 :            : 
    2308                 :            :           /* Value belongs to this node or to the left-hand subtree.  */
    2309                 :       1163 :           p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
    2310                 :       1163 :           bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
    2311                 :            :                                         GE_EXPR, node->m_c->m_case_bb, p, loc);
    2312                 :            : 
    2313                 :            :           /* Handle the left-hand subtree.  */
    2314                 :       1163 :           bb = emit_case_nodes (bb, index, node->m_left,
    2315                 :            :                                 default_prob, index_type, loc);
    2316                 :            : 
    2317                 :            :           /* If the left-hand subtree fell through,
    2318                 :            :              don't let it fall into the right-hand subtree.  */
    2319                 :       1163 :           if (bb && m_default_bb)
    2320                 :        999 :             emit_jump (bb, m_default_bb);
    2321                 :            : 
    2322                 :       1163 :           bb = emit_case_nodes (test_bb, index, node->m_right,
    2323                 :            :                                 default_prob, index_type, loc);
    2324                 :            :         }
    2325                 :            :       else
    2326                 :            :         {
    2327                 :            :           /* Node has no children so we check low and high bounds to remove
    2328                 :            :              redundant tests.  Only one of the bounds can exist,
    2329                 :            :              since otherwise this node is bounded--a case tested already.  */
    2330                 :       1111 :           tree lhs, rhs;
    2331                 :       1111 :           generate_range_test (bb, index, node->m_c->get_low (),
    2332                 :       1111 :                                node->m_c->get_high (), &lhs, &rhs);
    2333                 :       1111 :           p = default_prob / (node->m_c->m_subtree_prob + default_prob);
    2334                 :            : 
    2335                 :       1111 :           bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
    2336                 :            :                                         m_default_bb, p, loc);
    2337                 :            : 
    2338                 :       1111 :           emit_jump (bb, node->m_c->m_case_bb);
    2339                 :       1111 :           return NULL;
    2340                 :            :         }
    2341                 :            :     }
    2342                 :            : 
    2343                 :            :   return bb;
    2344                 :            : }
    2345                 :            : 
    2346                 :            : /* The main function of the pass scans statements for switches and invokes
    2347                 :            :    process_switch on them.  */
    2348                 :            : 
    2349                 :            : namespace {
    2350                 :            : 
    2351                 :            : const pass_data pass_data_convert_switch =
    2352                 :            : {
    2353                 :            :   GIMPLE_PASS, /* type */
    2354                 :            :   "switchconv", /* name */
    2355                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2356                 :            :   TV_TREE_SWITCH_CONVERSION, /* tv_id */
    2357                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2358                 :            :   0, /* properties_provided */
    2359                 :            :   0, /* properties_destroyed */
    2360                 :            :   0, /* todo_flags_start */
    2361                 :            :   TODO_update_ssa, /* todo_flags_finish */
    2362                 :            : };
    2363                 :            : 
    2364                 :            : class pass_convert_switch : public gimple_opt_pass
    2365                 :            : {
    2366                 :            : public:
    2367                 :     200773 :   pass_convert_switch (gcc::context *ctxt)
    2368                 :     401546 :     : gimple_opt_pass (pass_data_convert_switch, ctxt)
    2369                 :            :   {}
    2370                 :            : 
    2371                 :            :   /* opt_pass methods: */
    2372                 :    1590660 :   virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
    2373                 :            :   virtual unsigned int execute (function *);
    2374                 :            : 
    2375                 :            : }; // class pass_convert_switch
    2376                 :            : 
    2377                 :            : unsigned int
    2378                 :    1532860 : pass_convert_switch::execute (function *fun)
    2379                 :            : {
    2380                 :    1532860 :   basic_block bb;
    2381                 :    1532860 :   bool cfg_altered = false;
    2382                 :            : 
    2383                 :    9419790 :   FOR_EACH_BB_FN (bb, fun)
    2384                 :            :   {
    2385                 :    7886930 :     gimple *stmt = last_stmt (bb);
    2386                 :    7886930 :     if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
    2387                 :            :       {
    2388                 :      16907 :         if (dump_file)
    2389                 :            :           {
    2390                 :         30 :             expanded_location loc = expand_location (gimple_location (stmt));
    2391                 :            : 
    2392                 :         30 :             fprintf (dump_file, "beginning to process the following "
    2393                 :            :                      "SWITCH statement (%s:%d) : ------- \n",
    2394                 :            :                      loc.file, loc.line);
    2395                 :         30 :             print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2396                 :         30 :             putc ('\n', dump_file);
    2397                 :            :           }
    2398                 :            : 
    2399                 :      33814 :         switch_conversion sconv;
    2400                 :      16907 :         sconv.expand (as_a <gswitch *> (stmt));
    2401                 :      16907 :         cfg_altered |= sconv.m_cfg_altered;
    2402                 :      16907 :         if (!sconv.m_reason)
    2403                 :            :           {
    2404                 :        334 :             if (dump_file)
    2405                 :            :               {
    2406                 :         28 :                 fputs ("Switch converted\n", dump_file);
    2407                 :         28 :                 fputs ("--------------------------------\n", dump_file);
    2408                 :            :               }
    2409                 :            : 
    2410                 :            :             /* Make no effort to update the post-dominator tree.
    2411                 :            :                It is actually not that hard for the transformations
    2412                 :            :                we have performed, but it is not supported
    2413                 :            :                by iterate_fix_dominators.  */
    2414                 :        334 :             free_dominance_info (CDI_POST_DOMINATORS);
    2415                 :            :           }
    2416                 :            :         else
    2417                 :            :           {
    2418                 :      16573 :             if (dump_file)
    2419                 :            :               {
    2420                 :          2 :                 fputs ("Bailing out - ", dump_file);
    2421                 :          2 :                 fputs (sconv.m_reason, dump_file);
    2422                 :          2 :                 fputs ("\n--------------------------------\n", dump_file);
    2423                 :            :               }
    2424                 :            :           }
    2425                 :            :       }
    2426                 :            :   }
    2427                 :            : 
    2428                 :    1532860 :   return cfg_altered ? TODO_cleanup_cfg : 0;;
    2429                 :            : }
    2430                 :            : 
    2431                 :            : } // anon namespace
    2432                 :            : 
    2433                 :            : gimple_opt_pass *
    2434                 :     200773 : make_pass_convert_switch (gcc::context *ctxt)
    2435                 :            : {
    2436                 :     200773 :   return new pass_convert_switch (ctxt);
    2437                 :            : }
    2438                 :            : 
    2439                 :            : /* The main function of the pass scans statements for switches and invokes
    2440                 :            :    process_switch on them.  */
    2441                 :            : 
    2442                 :            : namespace {
    2443                 :            : 
    2444                 :            : template <bool O0> class pass_lower_switch: public gimple_opt_pass
    2445                 :            : {
    2446                 :            : public:
    2447                 :    1204640 :   pass_lower_switch (gcc::context *ctxt) : gimple_opt_pass (data, ctxt) {}
    2448                 :            : 
    2449                 :            :   static const pass_data data;
    2450                 :            :   opt_pass *
    2451                 :     200773 :   clone ()
    2452                 :            :   {
    2453                 :     200773 :     return new pass_lower_switch<O0> (m_ctxt);
    2454                 :            :   }
    2455                 :            : 
    2456                 :            :   virtual bool
    2457                 :    1633250 :   gate (function *)
    2458                 :            :   {
    2459                 :    1633250 :     return !O0 || !optimize;
    2460                 :            :   }
    2461                 :            : 
    2462                 :            :   virtual unsigned int execute (function *fun);
    2463                 :            : }; // class pass_lower_switch
    2464                 :            : 
    2465                 :            : template <bool O0>
    2466                 :            : const pass_data pass_lower_switch<O0>::data = {
    2467                 :            :   GIMPLE_PASS,                 /* type */
    2468                 :            :   O0 ? "switchlower_O0" : "switchlower", /* name */
    2469                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2470                 :            :   TV_TREE_SWITCH_LOWERING, /* tv_id */
    2471                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    2472                 :            :   0, /* properties_provided */
    2473                 :            :   0, /* properties_destroyed */
    2474                 :            :   0, /* todo_flags_start */
    2475                 :            :   TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
    2476                 :            : };
    2477                 :            : 
    2478                 :            : template <bool O0>
    2479                 :            : unsigned int
    2480                 :     944497 : pass_lower_switch<O0>::execute (function *fun)
    2481                 :            : {
    2482                 :            :   basic_block bb;
    2483                 :     944497 :   bool expanded = false;
    2484                 :            : 
    2485                 :     944497 :   auto_vec<gimple *> switch_statements;
    2486                 :     944497 :   switch_statements.create (1);
    2487                 :            : 
    2488                 :    9670450 :   FOR_EACH_BB_FN (bb, fun)
    2489                 :            :     {
    2490                 :    8725940 :       gimple *stmt = last_stmt (bb);
    2491                 :            :       gswitch *swtch;
    2492                 :   17195240 :       if (stmt && (swtch = dyn_cast<gswitch *> (stmt)))
    2493                 :            :         {
    2494                 :            :           if (!O0)
    2495                 :      17639 :             group_case_labels_stmt (swtch);
    2496                 :      28489 :           switch_statements.safe_push (swtch);
    2497                 :            :         }
    2498                 :            :     }
    2499                 :            : 
    2500                 :    1945976 :   for (unsigned i = 0; i < switch_statements.length (); i++)
    2501                 :            :     {
    2502                 :      28489 :       gimple *stmt = switch_statements[i];
    2503                 :      28489 :       if (dump_file)
    2504                 :            :         {
    2505                 :         17 :           expanded_location loc = expand_location (gimple_location (stmt));
    2506                 :            : 
    2507                 :         17 :           fprintf (dump_file, "beginning to process the following "
    2508                 :            :                    "SWITCH statement (%s:%d) : ------- \n",
    2509                 :            :                    loc.file, loc.line);
    2510                 :         17 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2511                 :         17 :           putc ('\n', dump_file);
    2512                 :            :         }
    2513                 :            : 
    2514                 :      28489 :       gswitch *swtch = dyn_cast<gswitch *> (stmt);
    2515                 :            :       if (swtch)
    2516                 :            :         {
    2517                 :      28489 :           switch_decision_tree dt (swtch);
    2518                 :      28489 :           expanded |= dt.analyze_switch_statement ();
    2519                 :            :         }
    2520                 :            :     }
    2521                 :            : 
    2522                 :     944497 :   if (expanded)
    2523                 :            :     {
    2524                 :      19639 :       free_dominance_info (CDI_DOMINATORS);
    2525                 :      19639 :       free_dominance_info (CDI_POST_DOMINATORS);
    2526                 :      19639 :       mark_virtual_operands_for_renaming (cfun);
    2527                 :            :     }
    2528                 :            : 
    2529                 :     944497 :   return 0;
    2530                 :            : }
    2531                 :            : 
    2532                 :            : } // anon namespace
    2533                 :            : 
    2534                 :            : gimple_opt_pass *
    2535                 :     200773 : make_pass_lower_switch_O0 (gcc::context *ctxt)
    2536                 :            : {
    2537                 :     200773 :   return new pass_lower_switch<true> (ctxt);
    2538                 :            : }
    2539                 :            : gimple_opt_pass *
    2540                 :     200773 : make_pass_lower_switch (gcc::context *ctxt)
    2541                 :            : {
    2542                 :     200773 :   return new pass_lower_switch<false> (ctxt);
    2543                 :            : }
    2544                 :            : 
    2545                 :            : 

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.