gcc/gimple-if-to-switch.cc

   1 /* If-elseif-else to switch conversion pass
   2    Copyright (C) 2020 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 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   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       if (!virtual_operand_p (gimple_phi_result (phi)))
  95         {
  96           tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
  97           vec->safe_push (std::make_pair (phi, arg));
  98         }
  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               continue;
 234             }
 235         }
 236
 237       left = static_cast<simple_cluster *> (clusters[i]);
 238       filtered_clusters.safe_push (left);
 239     }
 240
 241   dump_clusters (&filtered_clusters, "Canonical GIMPLE case clusters");
 242
 243   vec<cluster *> output
 244     = jump_table_cluster::find_jump_tables (filtered_clusters);
 245   bool r = output.length () < filtered_clusters.length ();
 246   if (r)
 247     dump_clusters (&output, "JT can be built");
 248   output.release ();
 249   if (r)
 250     return true;
 251
 252   output = bit_test_cluster::find_bit_tests (filtered_clusters);
 253   r = output.length () < filtered_clusters.length ();
 254   if (r)
 255     dump_clusters (&output, "BT can be built");
 256   output.release ();
 257   return r;
 258 }
 259
 260 /* Build case label with MIN and MAX values of a given basic block DEST.  */
 261
 262 static tree
 263 build_case_label (tree index_type, tree min, tree max, basic_block dest)
 264 {
 265   if (min != NULL_TREE && index_type != TREE_TYPE (min))
 266     min = fold_convert (index_type, min);
 267   if (max != NULL_TREE && index_type != TREE_TYPE (max))
 268     max = fold_convert (index_type, max);
 269
 270   tree label = gimple_block_label (dest);
 271   return build_case_label (min, min == max ? NULL_TREE : max, label);
 272 }
 273
 274 /* Compare two integer constants.  */
 275
 276 static int
 277 label_cmp (const void *a, const void *b)
 278 {
 279   const_tree l1 = *(const const_tree *) a;
 280   const_tree l2 = *(const const_tree *) b;
 281
 282   return tree_int_cst_compare (CASE_LOW (l1), CASE_LOW (l2));
 283 }
 284
 285 /* Convert a given if CHAIN into a switch GIMPLE statement.  */
 286
 287 static void
 288 convert_if_conditions_to_switch (if_chain *chain)
 289 {
 290   if (!dbg_cnt (if_to_switch))
 291     return;
 292
 293   auto_vec<tree> labels;
 294   unsigned entries = chain->m_entries.length ();
 295   condition_info *first_cond = chain->m_entries[0];
 296   condition_info *last_cond = chain->m_entries[entries - 1];
 297
 298   edge default_edge = last_cond->m_false_edge;
 299   basic_block default_bb = default_edge->dest;
 300
 301   gimple_stmt_iterator gsi = gsi_for_stmt (first_cond->m_cond);
 302   tree index_type = TREE_TYPE (first_cond->m_ranges[0].exp);
 303   for (unsigned i = 0; i < entries; i++)
 304     {
 305       condition_info *info = chain->m_entries[i];
 306       basic_block case_bb = info->m_true_edge->dest;
 307
 308       /* Create a forwarder block if needed.  */
 309       if (!info->m_true_edge_phi_mapping.is_empty ())
 310         {
 311           info->m_forwarder_bb = split_edge (info->m_true_edge);
 312           case_bb = info->m_forwarder_bb;
 313         }
 314
 315       for (unsigned j = 0; j < info->m_ranges.length (); j++)
 316         labels.safe_push (build_case_label (index_type,
 317                                             info->m_ranges[j].low,
 318                                             info->m_ranges[j].high,
 319                                             case_bb));
 320       default_bb = info->m_false_edge->dest;
 321
 322       if (i == 0)
 323         {
 324           remove_edge (first_cond->m_true_edge);
 325           remove_edge (first_cond->m_false_edge);
 326         }
 327       else
 328         delete_basic_block (info->m_bb);
 329
 330       make_edge (first_cond->m_bb, case_bb, 0);
 331     }
 332
 333   labels.qsort (label_cmp);
 334
 335   edge e = find_edge (first_cond->m_bb, default_bb);
 336   if (e == NULL)
 337     e = make_edge (first_cond->m_bb, default_bb, 0);
 338   gswitch *s
 339     = gimple_build_switch (first_cond->m_ranges[0].exp,
 340                            build_case_label (index_type, NULL_TREE,
 341                                              NULL_TREE, default_bb),
 342                            labels);
 343
 344   gsi_remove (&gsi, true);
 345   gsi_insert_before (&gsi, s, GSI_NEW_STMT);
 346
 347   if (dump_file)
 348     {
 349       fprintf (dump_file, "Expanded into a new gimple STMT: ");
 350       print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
 351       putc ('\n', dump_file);
 352     }
 353
 354   /* Fill up missing PHI node arguments.  */
 355   for (unsigned i = 0; i < chain->m_entries.length (); ++i)
 356     {
 357       condition_info *info = chain->m_entries[i];
 358       for (unsigned j = 0; j < info->m_true_edge_phi_mapping.length (); ++j)
 359         {
 360           std::pair<gphi *, tree> item = info->m_true_edge_phi_mapping[j];
 361           add_phi_arg (item.first, item.second,
 362                        single_succ_edge (info->m_forwarder_bb),
 363                        UNKNOWN_LOCATION);
 364         }
 365     }
 366
 367   /* Fill up missing PHI nodes for the default BB.  */
 368   for (unsigned j = 0; j < last_cond->m_false_edge_phi_mapping.length (); ++j)
 369     {
 370       std::pair<gphi *, tree> item = last_cond->m_false_edge_phi_mapping[j];
 371       add_phi_arg (item.first, item.second, e, UNKNOWN_LOCATION);
 372     }
 373 }
 374
 375 /* Identify an index variable used in BB in a GIMPLE condition.
 376    Save information about the condition into CONDITIONS_IN_BBS.  */
 377
 378 static void
 379 find_conditions (basic_block bb,
 380                  hash_map<basic_block, condition_info> *conditions_in_bbs)
 381 {
 382   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
 383   if (gsi_end_p (gsi))
 384     return;
 385
 386   gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
 387   if (cond == NULL)
 388     return;
 389
 390   if (!no_side_effect_bb (bb))
 391     return;
 392
 393   tree lhs = gimple_cond_lhs (cond);
 394   tree rhs = gimple_cond_rhs (cond);
 395   tree_code code = gimple_cond_code (cond);
 396
 397   condition_info info (cond);
 398
 399   gassign *def;
 400   if (code == NE_EXPR
 401       && TREE_CODE (lhs) == SSA_NAME
 402       && (def = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (lhs))) != NULL
 403       && integer_zerop (rhs))
 404     {
 405       enum tree_code rhs_code = gimple_assign_rhs_code (def);
 406       if (rhs_code == BIT_IOR_EXPR)
 407         {
 408           info.m_ranges.safe_grow (2, true);
 409           init_range_entry (&info.m_ranges[0], gimple_assign_rhs1 (def), NULL);
 410           init_range_entry (&info.m_ranges[1], gimple_assign_rhs2 (def), NULL);
 411         }
 412     }
 413   else
 414     {
 415       info.m_ranges.safe_grow (1, true);
 416       init_range_entry (&info.m_ranges[0], NULL_TREE, cond);
 417     }
 418
 419   /* All identified ranges must have equal expression and IN_P flag.  */
 420   if (!info.m_ranges.is_empty ())
 421     {
 422       edge true_edge, false_edge;
 423       tree expr = info.m_ranges[0].exp;
 424       bool in_p = info.m_ranges[0].in_p;
 425
 426       extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
 427       info.m_true_edge = in_p ? true_edge : false_edge;
 428       info.m_false_edge = in_p ? false_edge : true_edge;
 429
 430       for (unsigned i = 0; i < info.m_ranges.length (); ++i)
 431         if (info.m_ranges[i].exp == NULL_TREE
 432             || !INTEGRAL_TYPE_P (TREE_TYPE (info.m_ranges[i].exp))
 433             || info.m_ranges[i].low == NULL_TREE
 434             || info.m_ranges[i].high == NULL_TREE)
 435           return;
 436
 437       for (unsigned i = 1; i < info.m_ranges.length (); ++i)
 438         if (info.m_ranges[i].exp != expr
 439             || info.m_ranges[i].in_p != in_p)
 440           return;
 441
 442       info.record_phi_mapping (info.m_true_edge,
 443                                &info.m_true_edge_phi_mapping);
 444       info.record_phi_mapping (info.m_false_edge,
 445                                &info.m_false_edge_phi_mapping);
 446       conditions_in_bbs->put (bb, info);
 447     }
 448
 449 }
 450
 451 namespace {
 452
 453 const pass_data pass_data_if_to_switch =
 454 {
 455   GIMPLE_PASS, /* type */
 456   "iftoswitch", /* name */
 457   OPTGROUP_NONE, /* optinfo_flags */
 458   TV_TREE_IF_TO_SWITCH, /* tv_id */
 459   ( PROP_cfg | PROP_ssa ), /* properties_required */
 460   0, /* properties_provided */
 461   0, /* properties_destroyed */
 462   0, /* todo_flags_start */
 463   TODO_cleanup_cfg | TODO_update_ssa /* todo_flags_finish */
 464 };
 465
 466 class pass_if_to_switch : public gimple_opt_pass
 467 {
 468 public:
 469   pass_if_to_switch (gcc::context *ctxt)
 470     : gimple_opt_pass (pass_data_if_to_switch, ctxt)
 471   {}
 472
 473   /* opt_pass methods: */
 474   virtual bool gate (function *)
 475   {
 476     return (jump_table_cluster::is_enabled ()
 477             || bit_test_cluster::is_enabled ());
 478   }
 479
 480   virtual unsigned int execute (function *);
 481
 482 }; // class pass_if_to_switch
 483
 484 unsigned int
 485 pass_if_to_switch::execute (function *fun)
 486 {
 487   auto_vec<if_chain *> all_candidates;
 488   hash_map<basic_block, condition_info> conditions_in_bbs;
 489
 490   basic_block bb;
 491   FOR_EACH_BB_FN (bb, fun)
 492     find_conditions (bb, &conditions_in_bbs);
 493
 494   if (conditions_in_bbs.is_empty ())
 495     return 0;
 496
 497   int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (fun));
 498   unsigned n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
 499
 500   auto_bitmap seen_bbs;
 501   for (int i = n - 1; i >= 0; --i)
 502     {
 503       basic_block bb = BASIC_BLOCK_FOR_FN (fun, rpo[i]);
 504       if (bitmap_bit_p (seen_bbs, bb->index))
 505         continue;
 506
 507       bitmap_set_bit (seen_bbs, bb->index);
 508       condition_info *info = conditions_in_bbs.get (bb);
 509       if (info)
 510         {
 511           if_chain *chain = new if_chain ();
 512           chain->m_entries.safe_push (info);
 513           /* Try to find a chain starting in this BB.  */
 514           while (true)
 515             {
 516               if (!single_pred_p (gimple_bb (info->m_cond)))
 517                 break;
 518               edge e = single_pred_edge (gimple_bb (info->m_cond));
 519               condition_info *info2 = conditions_in_bbs.get (e->src);
 520               if (!info2 || info->m_ranges[0].exp != info2->m_ranges[0].exp)
 521                 break;
 522
 523               chain->m_entries.safe_push (info2);
 524               bitmap_set_bit (seen_bbs, e->src->index);
 525               info = info2;
 526             }
 527
 528           chain->m_entries.reverse ();
 529           if (chain->m_entries.length () >= 3
 530               && chain->check_non_overlapping_cases ()
 531               && chain->is_beneficial ())
 532             {
 533               gcond *cond = chain->m_entries[0]->m_cond;
 534               if (dump_enabled_p ())
 535                 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, cond,
 536                                  "Condition chain with %d BBs "
 537                                  "transformed into a switch statement.\n",
 538                                  chain->m_entries.length ());
 539               all_candidates.safe_push (chain);
 540             }
 541         }
 542     }
 543
 544   for (unsigned i = 0; i < all_candidates.length (); i++)
 545     {
 546       convert_if_conditions_to_switch (all_candidates[i]);
 547       delete all_candidates[i];
 548     }
 549
 550   free (rpo);
 551
 552   if (!all_candidates.is_empty ())
 553     {
 554       free_dominance_info (CDI_DOMINATORS);
 555       mark_virtual_operands_for_renaming (fun);
 556     }
 557
 558   return 0;
 559 }
 560
 561 } // anon namespace
 562
 563 gimple_opt_pass *
 564 make_pass_if_to_switch (gcc::context *ctxt)
 565 {
 566   return new pass_if_to_switch (ctxt);
 567 }