gcc/gimple-if-to-switch.cc

   1 /* If-elseif-else to switch conversion pass
   2    Copyright (C) 2020-2021 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               continue;
 231             }
 232         }
 233
 234       left = static_cast<simple_cluster *> (clusters[i]);
 235       filtered_clusters.safe_push (left);
 236     }
 237
 238   dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
 239
 240   vec<cluster *> output
 241     = jump_table_cluster::find_jump_tables (filtered_clusters);
 242   bool r = output.length () < filtered_clusters.length ();
 243   if (r)
 244     dump_clusters (&output, "JT can be built");
 245   output.release ();
 246   if (r)
 247     return true;
 248
 249   output = bit_test_cluster::find_bit_tests (filtered_clusters);
 250   r = output.length () < filtered_clusters.length ();
 251   if (r)
 252     dump_clusters (&output, "BT can be built");
 253
 254   for (unsigned i = 0; i < output.length (); i++)
 255     delete output[i];
 256
 257   output.release ();
 258   return r;
 259 }
 260
 261 /* Build case label with MIN and MAX values of a given basic block DEST.  */
 262
 263 static tree
 264 build_case_label (tree index_type, tree min, tree max, basic_block dest)
 265 {
 266   if (min != NULL_TREE && index_type != TREE_TYPE (min))
 267     min = fold_convert (index_type, min);
 268   if (max != NULL_TREE && index_type != TREE_TYPE (max))
 269     max = fold_convert (index_type, max);
 270
 271   tree label = gimple_block_label (dest);
 272   return build_case_label (min, min == max ? NULL_TREE : max, label);
 273 }
 274
 275 /* Compare two integer constants.  */
 276
 277 static int
 278 label_cmp (const void *a, const void *b)
 279 {
 280   const_tree l1 = *(const const_tree *) a;
 281   const_tree l2 = *(const const_tree *) b;
 282
 283   return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
 284 }
 285
 286 /* Convert a given if CHAIN into a switch GIMPLE statement.  */
 287
 288 static void
 289 convert_if_conditions_to_switch (if_chain *chain)
 290 {
 291   if (!dbg_cnt (if_to_switch))
 292     return;
 293
 294   auto_vec<tree> labels;
 295   unsigned entries = chain->m_entries.length ();
 296   condition_info *first_cond = chain->m_entries[0];
 297   condition_info *last_cond = chain->m_entries[entries - 1];
 298
 299   edge default_edge = last_cond->m_false_edge;
 300   basic_block default_bb = default_edge->dest;
 301
 302   gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
 303   tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
 304   for (unsigned i = 0; i < entries; i++)
 305     {
 306       condition_info *info = chain->m_entries[i];
 307       basic_block case_bb = info->m_true_edge->dest;
 308
 309       /* Create a forwarder block if needed.  */
 310       if (!info->m_true_edge_phi_mapping.is_empty ())
 311         {
 312           info->m_forwarder_bb = split_edge (info->m_true_edge);
 313           case_bb = info->m_forwarder_bb;
 314         }
 315
 316       for (unsigned j = 0; j < info->m_ranges.length (); j++)
 317         labels.safe_push (build_case_label (index_type,
 318                                             info->m_ranges[j].low,
 319                                             info->m_ranges[j].high,
 320                                             case_bb));
 321       default_bb = info->m_false_edge->dest;
 322
 323       if (i == 0)
 324         {
 325           remove_edge (first_cond->m_true_edge);
 326           remove_edge (first_cond->m_false_edge);
 327         }
 328       else
 329         delete_basic_block (info->m_bb);
 330
 331       make_edge (first_cond->m_bb, case_bb, 0);
 332     }
 333
 334   labels.qsort (label_cmp);
 335
 336   edge e = find_edge (first_cond->m_bb, default_bb);
 337   if (e == NULL)
 338     e = make_edge (first_cond->m_bb, default_bb, 0);
 339   gswitch *s
 340     = gimple_build_switch (first_cond->m_ranges[0].exp,
 341                            build_case_label (index_type, NULL_TREE,
 342                                              NULL_TREE, default_bb),
 343                            labels);
 344
 345   gsi_remove (&gsi, true);
 346   gsi_insert_before (&gsi, s, GSI_NEW_STMT);
 347
 348   if (dump_file)
 349     {
 350       fprintf (dump_file, "Expanded into a new gimple STMT: ");
 351       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 352       putc ('\n', dump_file);
 353     }
 354
 355   /* Fill up missing PHI node arguments.  */
 356   for (unsigned i = 0; i < chain->m_entries.length (); ++i)
 357     {
 358       condition_info *info = chain->m_entries[i];
 359       for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
 360         {
 361           std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
 362           add_phi_arg (item.first, item.second,
 363                        single_succ_edge (info->m_forwarder_bb),
 364                        UNKNOWN_LOCATION);
 365         }
 366     }
 367
 368   /* Fill up missing PHI nodes for the default BB.  */
 369   for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
 370     {
 371       std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
 372       add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
 373     }
 374 }
 375
 376 /* Identify an index variable used in BB in a GIMPLE condition.
 377    Save information about the condition into CONDITIONS_IN_BBS.  */
 378
 379 static void
 380 find_conditions (basic_block bb,
 381                  hash_map<basic_block, condition_info *> *conditions_in_bbs)
 382 {
 383   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
 384   if (gsi_end_p (gsi))
 385     return;
 386
 387   gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
 388   if (cond == NULL)
 389     return;
 390
 391   if (!no_side_effect_bb (bb))
 392     return;
 393
 394   tree lhs = gimple_cond_lhs (cond);
 395   tree rhs = gimple_cond_rhs (cond);
 396   tree_code code = gimple_cond_code (cond);
 397
 398   condition_info *info = new condition_info (cond);
 399
 400   gassign *def;
 401   if (code == NE_EXPR
 402       && TREE_CODE (lhs) == SSA_NAME
 403       && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
 404       && integer_zerop (rhs))
 405     {
 406       enum tree_code rhs_code = gimple_assign_rhs_code (def);
 407       if (rhs_code == BIT_IOR_EXPR)
 408         {
 409           info->m_ranges.safe_grow (2, true);
 410           init_range_entry (&info->m_ranges[0], gimple_assign_rhs1 (def), NULL);
 411           init_range_entry (&info->m_ranges[1], gimple_assign_rhs2 (def), NULL);
 412         }
 413     }
 414   else
 415     {
 416       info->m_ranges.safe_grow (1, true);
 417       init_range_entry (&info->m_ranges[0], NULL_TREE, cond);
 418     }
 419
 420   /* All identified ranges must have equal expression and IN_P flag.  */
 421   if (!info->m_ranges.is_empty ())
 422     {
 423       edge true_edge, false_edge;
 424       tree expr = info->m_ranges[0].exp;
 425       bool in_p = info->m_ranges[0].in_p;
 426
 427       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 428       info->m_true_edge = in_p ? true_edge : false_edge;
 429       info->m_false_edge = in_p ? false_edge : true_edge;
 430
 431       for (unsigned i = 0; i < info->m_ranges.length (); ++i)
 432         if (info->m_ranges[i].exp == NULL_TREE
 433             || !INTEGRAL_TYPE_P (TREE_TYPE (info->m_ranges[i].exp))
 434             || info->m_ranges[i].low == NULL_TREE
 435             || info->m_ranges[i].high == NULL_TREE
 436             || (TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].low))
 437                 != TYPE_PRECISION (TREE_TYPE (info->m_ranges[i].high))))
 438           goto exit;
 439
 440       for (unsigned i = 1; i < info->m_ranges.length (); ++i)
 441         if (info->m_ranges[i].exp != expr
 442             || info->m_ranges[i].in_p != in_p)
 443           goto exit;
 444
 445       info->record_phi_mapping (info->m_true_edge,
 446                                 &info->m_true_edge_phi_mapping);
 447       info->record_phi_mapping (info->m_false_edge,
 448                                 &info->m_false_edge_phi_mapping);
 449       conditions_in_bbs->put (bb, info);
 450     }
 451
 452   return;
 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   virtual bool gate (function *)
 482   {
 483     return (jump_table_cluster::is_enabled ()
 484             || bit_test_cluster::is_enabled ());
 485   }
 486
 487   virtual unsigned int execute (function *);
 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               chain->m_entries.safe_push (*info2);
 538               bitmap_set_bit (seen_bbs, e->src->index);
 539               info = *info2;
 540             }
 541
 542           chain->m_entries.reverse ();
 543           if (chain->m_entries.length () >= 2
 544               && chain->check_non_overlapping_cases ()
 545               && chain->is_beneficial ())
 546             {
 547               gcond *cond = chain->m_entries[0]->m_cond;
 548               if (dump_enabled_p ())
 549                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
 550                                  "Condition chain with %d BBs "
 551                                  "transformed into a switch statement.\n",
 552                                  chain->m_entries.length ());
 553               all_candidates.safe_push (chain);
 554             }
 555           else
 556             delete chain;
 557         }
 558     }
 559
 560   for (unsigned i = 0; i < all_candidates.length (); i++)
 561     {
 562       convert_if_conditions_to_switch (all_candidates[i]);
 563       delete all_candidates[i];
 564     }
 565
 566   free (rpo);
 567
 568   for (hash_map<basic_block, condition_info *>::iterator it
 569        = conditions_in_bbs.begin (); it != conditions_in_bbs.end (); ++it)
 570     delete (*it).second;
 571
 572   if (!all_candidates.is_empty ())
 573     {
 574       free_dominance_info (CDI_DOMINATORS);
 575       return TODO_cleanup_cfg;
 576     }
 577
 578   return 0;
 579 }
 580
 581 } // anon namespace
 582
 583 gimple_opt_pass *
 584 make_pass_if_to_switch (gcc::context *ctxt)
 585 {
 586   return new pass_if_to_switch (ctxt);
 587 }