gcc/gimple-if-to-switch.cc

   1 /* If-elseif-else to switch conversion pass
   2    Copyright (C) 2020-2023 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 /* Algorithm of the pass runs in the following steps:
  21    a) We walk basic blocks in DOMINATOR order so that we first reach
  22       a first condition of a future switch.
  23    b) We follow false edges of a if-else-chain and we record chain
  24       of GIMPLE conditions.  These blocks are only used for comparison
  25       of a common SSA_NAME and we do not allow any side effect.
  26    c) We remove all basic blocks (except first) of such chain and
  27       GIMPLE switch replaces the condition in the first basic block.
  28    d) We move all GIMPLE statements in the removed blocks into the
  29       first one.  */
  30
  31 #include "config.h"
  32 #include "system.h"
  33 #include "coretypes.h"
  34 #include "backend.h"
  35 #include "rtl.h"
  36 #include "tree.h"
  37 #include "gimple.h"
  38 #include "tree-pass.h"
  39 #include "ssa.h"
  40 #include "gimple-pretty-print.h"
  41 #include "fold-const.h"
  42 #include "gimple-iterator.h"
  43 #include "tree-cfg.h"
  44 #include "tree-dfa.h"
  45 #include "tree-cfgcleanup.h"
  46 #include "alias.h"
  47 #include "tree-ssa-loop.h"
  48 #include "diagnostic.h"
  49 #include "cfghooks.h"
  50 #include "tree-into-ssa.h"
  51 #include "cfganal.h"
  52 #include "dbgcnt.h"
  53 #include "target.h"
  54 #include "alloc-pool.h"
  55 #include "tree-switch-conversion.h"
  56 #include "tree-ssa-reassoc.h"
  57
  58 using namespace tree_switch_conversion;
  59
  60 struct condition_info
  61 {
  62   typedef auto_vec<std::pair<gphi *, tree>> mapping_vec;
  63
  64   condition_info (gcond *cond, bool has_side_effect): m_cond (cond),
  65     m_bb (gimple_bb (cond)), m_forwarder_bb (NULL), m_ranges (),
  66     m_true_edge (NULL), m_false_edge (NULL),
  67     m_true_edge_phi_mapping (), m_false_edge_phi_mapping (),
  68     m_has_side_effect (has_side_effect)
  69   {
  70     m_ranges.create (0);
  71   }
  72
  73   /* Recond PHI mapping for an original edge E and save these into
  74      vector VEC.  */
  75   void record_phi_mapping (edge e, mapping_vec *vec);
  76
  77   gcond *m_cond;
  78   basic_block m_bb;
  79   basic_block m_forwarder_bb;
  80   auto_vec<range_entry> m_ranges;
  81   edge m_true_edge;
  82   edge m_false_edge;
  83   mapping_vec m_true_edge_phi_mapping;
  84   mapping_vec m_false_edge_phi_mapping;
  85   bool m_has_side_effect;
  86 };
  87
  88 /* Recond PHI mapping for an original edge E and save these into vector VEC.  */
  89
  90 void
  91 condition_info::record_phi_mapping (edge e, mapping_vec *vec)
  92 {
  93   for (gphi_iterator gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
  94        gsi_next (&gsi))
  95     {
  96       gphi *phi = gsi.phi ();
  97       tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
  98       vec->safe_push (std::make_pair (phi, arg));
  99     }
 100 }
 101
 102 /* Master structure for one if to switch conversion candidate.  */
 103
 104 struct if_chain
 105 {
 106   /* Default constructor.  */
 107   if_chain (): m_entries ()
 108   {
 109     m_entries.create (2);
 110   }
 111
 112   /* Default destructor.  */
 113   ~if_chain ()
 114   {
 115     m_entries.release ();
 116   }
 117
 118   /* Verify that all case ranges do not overlap.  */
 119   bool check_non_overlapping_cases ();
 120
 121   /* Return true when the switch can be expanded with a jump table or
 122      a bit test (at least partially).  */
 123   bool is_beneficial ();
 124
 125   /* If chain entries.  */
 126   vec<condition_info *> m_entries;
 127 };
 128
 129 /* Compare two case ranges by minimum value.  */
 130
 131 static int
 132 range_cmp (const void *a, const void *b)
 133 {
 134   const range_entry *re1 = *(const range_entry * const *) a;
 135   const range_entry *re2 = *(const range_entry * const *) b;
 136
 137   return tree_int_cst_compare (re1->low, re2->low);
 138 }
 139
 140 /* Verify that all case ranges do not overlap.  */
 141
 142 bool
 143 if_chain::check_non_overlapping_cases ()
 144 {
 145   auto_vec<range_entry *> all_ranges;
 146   for (unsigned i = 0; i < m_entries.length (); i++)
 147     for (unsigned j = 0; j < m_entries[i]->m_ranges.length (); j++)
 148       all_ranges.safe_push (&m_entries[i]->m_ranges[j]);
 149
 150   all_ranges.qsort (range_cmp);
 151
 152   for (unsigned i = 0; i < all_ranges.length () - 1; i++)
 153     {
 154       range_entry *left = all_ranges[i];
 155       range_entry *right = all_ranges[i + 1];
 156       if (tree_int_cst_le (left->low, right->low)
 157           && tree_int_cst_le (right->low, left->high))
 158         return false;
 159     }
 160
 161   return true;
 162 }
 163
 164 /* Compare clusters by minimum value.  */
 165
 166 static int
 167 cluster_cmp (const void *a, const void *b)
 168 {
 169   simple_cluster *sc1 = *(simple_cluster * const *) a;
 170   simple_cluster *sc2 = *(simple_cluster * const *) b;
 171
 172   return tree_int_cst_compare (sc1->get_low (), sc2->get_high ());
 173 }
 174
 175 /* Dump constructed CLUSTERS with prefix MESSAGE.  */
 176
 177 static void
 178 dump_clusters (vec<cluster *> *clusters, const char *message)
 179 {
 180   if (dump_file)
 181     {
 182       fprintf (dump_file, ";; %s: ", message);
 183       for (unsigned i = 0; i < clusters->length (); i++)
 184         (*clusters)[i]->dump (dump_file, dump_flags & TDF_DETAILS);
 185       fprintf (dump_file, "\n");
 186     }
 187 }
 188
 189 /* Return true when the switch can be expanded with a jump table or
 190    a bit test (at least partially).  */
 191
 192 bool
 193 if_chain::is_beneficial ()
 194 {
 195   profile_probability prob = profile_probability::uninitialized ();
 196
 197   auto_vec<cluster *> clusters;
 198   clusters.create (m_entries.length ());
 199
 200   for (unsigned i = 0; i < m_entries.length (); i++)
 201     {
 202       condition_info *info = m_entries[i];
 203       for (unsigned j = 0; j < info->m_ranges.length (); j++)
 204         {
 205           range_entry *range = &info->m_ranges[j];
 206           basic_block bb = info->m_true_edge->dest;
 207           bool has_forwarder = !info->m_true_edge_phi_mapping.is_empty ();
 208           clusters.safe_push (new simple_cluster (range->low, range->high,
 209                                                   NULL_TREE, bb, prob,
 210                                                   has_forwarder));
 211         }
 212     }
 213
 214   /* Sort clusters and merge them.  */
 215   auto_vec<cluster *> filtered_clusters;
 216   filtered_clusters.create (16);
 217   clusters.qsort (cluster_cmp);
 218   simple_cluster *left = static_cast<simple_cluster *> (clusters[0]);
 219   filtered_clusters.safe_push (left);
 220
 221   for (unsigned i = 1; i < clusters.length (); i++)
 222     {
 223       simple_cluster *right = static_cast<simple_cluster *> (clusters[i]);
 224       tree type = TREE_TYPE (left->get_low ());
 225       if (!left->m_has_forward_bb
 226           && !right->m_has_forward_bb
 227           && left->m_case_bb == right->m_case_bb)
 228         {
 229           if (wi::eq_p (wi::to_wide (right->get_low ()) - wi::to_wide
 230                         (left->get_high ()), wi::one (TYPE_PRECISION (type))))
 231             {
 232               left->set_high (right->get_high ());
 233               delete right;
 234               continue;
 235             }
 236         }
 237
 238       left = static_cast<simple_cluster *> (clusters[i]);
 239       filtered_clusters.safe_push (left);
 240     }
 241
 242   dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
 243
 244   vec<cluster *> output
 245     = jump_table_cluster::find_jump_tables (filtered_clusters);
 246   bool r = output.length () < filtered_clusters.length ();
 247   if (r)
 248     {
 249       dump_clusters (&output, "JT can be built");
 250       release_clusters (output);
 251       return true;
 252     }
 253   else
 254     output.release ();
 255
 256   output = bit_test_cluster::find_bit_tests (filtered_clusters);
 257   r = output.length () < filtered_clusters.length ();
 258   if (r)
 259     dump_clusters (&output, "BT can be built");
 260
 261   release_clusters (output);
 262   return r;
 263 }
 264
 265 /* Build case label with MIN and MAX values of a given basic block DEST.  */
 266
 267 static tree
 268 build_case_label (tree index_type, tree min, tree max, basic_block dest)
 269 {
 270   if (min != NULL_TREE && index_type != TREE_TYPE (min))
 271     min = fold_convert (index_type, min);
 272   if (max != NULL_TREE && index_type != TREE_TYPE (max))
 273     max = fold_convert (index_type, max);
 274
 275   tree label = gimple_block_label (dest);
 276   return build_case_label (min, min == max ? NULL_TREE : max, label);
 277 }
 278
 279 /* Compare two integer constants.  */
 280
 281 static int
 282 label_cmp (const void *a, const void *b)
 283 {
 284   const_tree l1 = *(const const_tree *) a;
 285   const_tree l2 = *(const const_tree *) b;
 286
 287   return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
 288 }
 289
 290 /* Convert a given if CHAIN into a switch GIMPLE statement.  */
 291
 292 static void
 293 convert_if_conditions_to_switch (if_chain *chain)
 294 {
 295   if (!dbg_cnt (if_to_switch))
 296     return;
 297
 298   auto_vec<tree> labels;
 299   unsigned entries = chain->m_entries.length ();
 300   condition_info *first_cond = chain->m_entries[0];
 301   condition_info *last_cond = chain->m_entries[entries - 1];
 302
 303   edge default_edge = last_cond->m_false_edge;
 304   basic_block default_bb = default_edge->dest;
 305
 306   gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
 307   tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
 308   for (unsigned i = 0; i < entries; i++)
 309     {
 310       condition_info *info = chain->m_entries[i];
 311       basic_block case_bb = info->m_true_edge->dest;
 312
 313       /* Create a forwarder block if needed.  */
 314       if (!info->m_true_edge_phi_mapping.is_empty ())
 315         {
 316           info->m_forwarder_bb = split_edge (info->m_true_edge);
 317           case_bb = info->m_forwarder_bb;
 318         }
 319
 320       for (unsigned j = 0; j < info->m_ranges.length (); j++)
 321         labels.safe_push (build_case_label (index_type,
 322                                             info->m_ranges[j].low,
 323                                             info->m_ranges[j].high,
 324                                             case_bb));
 325       default_bb = info->m_false_edge->dest;
 326
 327       if (i == 0)
 328         {
 329           remove_edge (first_cond->m_true_edge);
 330           remove_edge (first_cond->m_false_edge);
 331         }
 332       else
 333         delete_basic_block (info->m_bb);
 334
 335       make_edge (first_cond->m_bb, case_bb, 0);
 336     }
 337
 338   labels.qsort (label_cmp);
 339
 340   edge e = find_edge (first_cond->m_bb, default_bb);
 341   if (e == NULL)
 342     e = make_edge (first_cond->m_bb, default_bb, 0);
 343   gswitch *s
 344     = gimple_build_switch (first_cond->m_ranges[0].exp,
 345                            build_case_label (index_type, NULL_TREE,
 346                                              NULL_TREE, default_bb),
 347                            labels);
 348
 349   gsi_remove (&gsi, true);
 350   gsi_insert_before (&gsi, s, GSI_NEW_STMT);
 351
 352   if (dump_file)
 353     {
 354       fprintf (dump_file, "Expanded into a new gimple STMT: ");
 355       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 356       putc ('\n', dump_file);
 357     }
 358
 359   /* Fill up missing PHI node arguments.  */
 360   for (unsigned i = 0; i < chain->m_entries.length (); ++i)
 361     {
 362       condition_info *info = chain->m_entries[i];
 363       for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
 364         {
 365           std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
 366           add_phi_arg (item.first, item.second,
 367                        single_succ_edge (info->m_forwarder_bb),
 368                        UNKNOWN_LOCATION);
 369         }
 370     }
 371
 372   /* Fill up missing PHI nodes for the default BB.  */
 373   for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
 374     {
 375       std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
 376       add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
 377     }
 378 }
 379
 380 /* Identify an index variable used in BB in a GIMPLE condition.
 381    Save information about the condition into CONDITIONS_IN_BBS.  */
 382
 383 static void
 384 find_conditions (basic_block bb,
 385                  hash_map<basic_block, condition_info *> *conditions_in_bbs)
 386 {
 387   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
 388   if (gsi_end_p (gsi))
 389     return;
 390
 391   gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
 392   if (cond == NULL)
 393     return;
 394
 395   tree lhs = gimple_cond_lhs (cond);
 396   tree rhs = gimple_cond_rhs (cond);
 397   tree_code code = gimple_cond_code (cond);
 398
 399   condition_info *info = new condition_info (cond, !no_side_effect_bb (bb));
 400
 401   gassign *def;
 402   if (code == NE_EXPR
 403       && TREE_CODE (lhs) == SSA_NAME
 404       && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
 405       && integer_zerop (rhs))
 406     {
 407       enum tree_code rhs_code = gimple_assign_rhs_code (def);
 408       if (rhs_code == BIT_IOR_EXPR)
 409         {
 410           info->m_ranges.safe_grow (2, true);
 411           init_range_entry (&info->m_ranges[0], gimple_assign_rhs1 (def), NULL);
 412           init_range_entry (&info->m_ranges[1], gimple_assign_rhs2 (def), NULL);
 413         }
 414     }
 415   else
 416     {
 417       info->m_ranges.safe_grow (1, true);
 418       init_range_entry (&info->m_ranges[0], NULL_TREE, cond);
 419     }
 420
 421   /* All identified ranges must have equal expression and IN_P flag.  */
 422   if (!info->m_ranges.is_empty ())
 423     {
 424       edge true_edge, false_edge;
 425       tree expr = info->m_ranges[0].exp;
 426       bool in_p = info->m_ranges[0].in_p;
 427
 428       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 429       info->m_true_edge = in_p ? true_edge : false_edge;
 430       info->m_false_edge = in_p ? false_edge : true_edge;
 431
 432       for (unsigned i = 0; i < info->m_ranges.length (); ++i)
 433         if (info->m_ranges[i].exp == NULL_TREE
 434             || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
 435             || info->m_ranges[i].low == NULL_TREE
 436             || info->m_ranges[i].high == NULL_TREE
 437             || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
 438                 != TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
 439           goto exit;
 440
 441       for (unsigned i = 1; i < info->m_ranges.length (); ++i)
 442         if (info->m_ranges[i].exp != expr
 443             || info->m_ranges[i].in_p != in_p)
 444           goto exit;
 445
 446       info->record_phi_mapping (info->m_true_edge,
 447                                 &info->m_true_edge_phi_mapping);
 448       info->record_phi_mapping (info->m_false_edge,
 449                                 &info->m_false_edge_phi_mapping);
 450       conditions_in_bbs->put (bb, info);
 451       return;
 452     }
 453
 454 exit:
 455   delete info;
 456 }
 457
 458 namespace {
 459
 460 const pass_data pass_data_if_to_switch =
 461 {
 462   GIMPLE_PASS, /* type */
 463   "iftoswitch", /* name */
 464   OPTGROUP_NONE, /* optinfo_flags */
 465   TV_TREE_IF_TO_SWITCH, /* tv_id */
 466   ( PROP_cfg | PROP_ssa ), /* properties_required */
 467   0, /* properties_provided */
 468   0, /* properties_destroyed */
 469   0, /* todo_flags_start */
 470   TODO_update_ssa /* todo_flags_finish */
 471 };
 472
 473 class pass_if_to_switch : public gimple_opt_pass
 474 {
 475 public:
 476   pass_if_to_switch (gcc::context *ctxt)
 477     : gimple_opt_pass (pass_data_if_to_switch, ctxt)
 478   {}
 479
 480   /* opt_pass methods: */
 481   bool gate (function *) final override
 482   {
 483     return (jump_table_cluster::is_enabled ()
 484             || bit_test_cluster::is_enabled ());
 485   }
 486
 487   unsigned int execute (function *) final override;
 488
 489 }; // class pass_if_to_switch
 490
 491 unsigned int
 492 pass_if_to_switch::execute (function *fun)
 493 {
 494   auto_vec<if_chain *> all_candidates;
 495   hash_map<basic_block, condition_info *> conditions_in_bbs;
 496
 497   basic_block bb;
 498   FOR_EACH_BB_FN (bb, fun)
 499     find_conditions (bb, &conditions_in_bbs);
 500
 501   if (conditions_in_bbs.is_empty ())
 502     return 0;
 503
 504   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
 505   unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
 506
 507   auto_bitmap seen_bbs;
 508   for (int i = n - 1; i >= 0; --i)
 509     {
 510       basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
 511       if (bitmap_bit_p (seen_bbs, bb->index))
 512         continue;
 513
 514       bitmap_set_bit (seen_bbs, bb->index);
 515       condition_info **slot = conditions_in_bbs.get (bb);
 516       if (slot)
 517         {
 518           condition_info *info = *slot;
 519           if_chain *chain = new if_chain ();
 520           chain->m_entries.safe_push (info);
 521           /* Try to find a chain starting in this BB.  */
 522           while (true)
 523             {
 524               if (!single_pred_p (gimple_bb (info->m_cond)))
 525                 break;
 526               edge e = single_pred_edge (gimple_bb (info->m_cond));
 527               condition_info **info2 = conditions_in_bbs.get (e->src);
 528               if (!info2 || info->m_ranges[0].exp != (*info2)->m_ranges[0].exp)
 529                 break;
 530
 531               /* It is important that the blocks are linked through FALSE_EDGE.
 532                  For an expression of index != VALUE, true and false edges
 533                  are flipped.  */
 534               if ((*info2)->m_false_edge != e)
 535                 break;
 536
 537               /* Only the first BB in a chain can have a side effect.  */
 538               if (info->m_has_side_effect)
 539                 break;
 540
 541               chain->m_entries.safe_push (*info2);
 542               bitmap_set_bit (seen_bbs, e->src->index);
 543               info = *info2;
 544             }
 545
 546           chain->m_entries.reverse ();
 547           if (chain->m_entries.length () >= 2
 548               && chain->check_non_overlapping_cases ()
 549               && chain->is_beneficial ())
 550             {
 551               gcond *cond = chain->m_entries[0]->m_cond;
 552               if (dump_enabled_p ())
 553                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
 554                                  "Condition chain with %d BBs "
 555                                  "transformed into a switch statement.\n",
 556                                  chain->m_entries.length ());
 557               all_candidates.safe_push (chain);
 558             }
 559           else
 560             delete chain;
 561         }
 562     }
 563
 564   for (unsigned i = 0; i < all_candidates.length (); i++)
 565     {
 566       convert_if_conditions_to_switch (all_candidates[i]);
 567       delete all_candidates[i];
 568     }
 569
 570   free (rpo);
 571
 572   for (hash_map<basic_block, condition_info *>::iterator it
 573        = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
 574     delete (*it).second;
 575
 576   if (!all_candidates.is_empty ())
 577     {
 578       free_dominance_info (CDI_DOMINATORS);
 579       return TODO_cleanup_cfg;
 580     }
 581
 582   return 0;
 583 }
 584
 585 } // anon namespace
 586
 587 gimple_opt_pass *
 588 make_pass_if_to_switch (gcc::context *ctxt)
 589 {
 590   return new pass_if_to_switch (ctxt);
 591 }