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               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   if (!no_side_effect_bb (bb))
 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);
 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   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 }