gcc/gimple-if-to-switch.cc

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