gcc/gimple-if-to-switch.cc

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