gcc/tree-ssa-sink.c

   1 /* Code sinking for trees
   2    Copyright (C) 2001-2013 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "basic-block.h"
  27 #include "gimple-pretty-print.h"
  28 #include "tree-inline.h"
  29 #include "tree-flow.h"
  30 #include "gimple.h"
  31 #include "hashtab.h"
  32 #include "tree-iterator.h"
  33 #include "alloc-pool.h"
  34 #include "tree-pass.h"
  35 #include "flags.h"
  36 #include "bitmap.h"
  37 #include "cfgloop.h"
  38 #include "params.h"
  39
  40 /* TODO:
  41    1. Sinking store only using scalar promotion (IE without moving the RHS):
  42
  43    *q = p;
  44    p = p + 1;
  45    if (something)
  46      *q = <not p>;
  47    else
  48      y = *q;
  49
  50
  51    should become
  52    sinktemp = p;
  53    p = p + 1;
  54    if (something)
  55      *q = <not p>;
  56    else
  57    {
  58      *q = sinktemp;
  59      y = *q
  60    }
  61    Store copy propagation will take care of the store elimination above.
  62
  63
  64    2. Sinking using Partial Dead Code Elimination.  */
  65
  66
  67 static struct
  68 {
  69   /* The number of statements sunk down the flowgraph by code sinking.  */
  70   int sunk;
  71
  72 } sink_stats;
  73
  74
  75 /* Given a PHI, and one of its arguments (DEF), find the edge for
  76    that argument and return it.  If the argument occurs twice in the PHI node,
  77    we return NULL.  */
  78
  79 static basic_block
  80 find_bb_for_arg (gimple phi, tree def)
  81 {
  82   size_t i;
  83   bool foundone = false;
  84   basic_block result = NULL;
  85   for (i = 0; i < gimple_phi_num_args (phi); i++)
  86     if (PHI_ARG_DEF (phi, i) == def)
  87       {
  88         if (foundone)
  89           return NULL;
  90         foundone = true;
  91         result = gimple_phi_arg_edge (phi, i)->src;
  92       }
  93   return result;
  94 }
  95
  96 /* When the first immediate use is in a statement, then return true if all
  97    immediate uses in IMM are in the same statement.
  98    We could also do the case where  the first immediate use is in a phi node,
  99    and all the other uses are in phis in the same basic block, but this
 100    requires some expensive checking later (you have to make sure no def/vdef
 101    in the statement occurs for multiple edges in the various phi nodes it's
 102    used in, so that you only have one place you can sink it to.  */
 103
 104 static bool
 105 all_immediate_uses_same_place (gimple stmt)
 106 {
 107   gimple firstuse = NULL;
 108   ssa_op_iter op_iter;
 109   imm_use_iterator imm_iter;
 110   use_operand_p use_p;
 111   tree var;
 112
 113   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 114     {
 115       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 116         {
 117           if (is_gimple_debug (USE_STMT (use_p)))
 118             continue;
 119           if (firstuse == NULL)
 120             firstuse = USE_STMT (use_p);
 121           else
 122             if (firstuse != USE_STMT (use_p))
 123               return false;
 124         }
 125     }
 126
 127   return true;
 128 }
 129
 130 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 131
 132 static basic_block
 133 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
 134 {
 135   bitmap blocks = BITMAP_ALLOC (NULL);
 136   basic_block commondom;
 137   unsigned int j;
 138   bitmap_iterator bi;
 139   ssa_op_iter op_iter;
 140   imm_use_iterator imm_iter;
 141   use_operand_p use_p;
 142   tree var;
 143
 144   bitmap_clear (blocks);
 145   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 146     {
 147       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 148         {
 149           gimple usestmt = USE_STMT (use_p);
 150           basic_block useblock;
 151
 152           if (gimple_code (usestmt) == GIMPLE_PHI)
 153             {
 154               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 155
 156               useblock = gimple_phi_arg_edge (usestmt, idx)->src;
 157             }
 158           else if (is_gimple_debug (usestmt))
 159             {
 160               *debug_stmts = true;
 161               continue;
 162             }
 163           else
 164             {
 165               useblock = gimple_bb (usestmt);
 166             }
 167
 168           /* Short circuit. Nothing dominates the entry block.  */
 169           if (useblock == ENTRY_BLOCK_PTR)
 170             {
 171               BITMAP_FREE (blocks);
 172               return NULL;
 173             }
 174           bitmap_set_bit (blocks, useblock->index);
 175         }
 176     }
 177   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 178   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 179     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 180                                           BASIC_BLOCK (j));
 181   BITMAP_FREE (blocks);
 182   return commondom;
 183 }
 184
 185 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
 186    tree, return the best basic block between them (inclusive) to place
 187    statements.
 188
 189    We want the most control dependent block in the shallowest loop nest.
 190
 191    If the resulting block is in a shallower loop nest, then use it.  Else
 192    only use the resulting block if it has significantly lower execution
 193    frequency than EARLY_BB to avoid gratutious statement movement.  We
 194    consider statements with VOPS more desirable to move.
 195
 196    This pass would obviously benefit from PDO as it utilizes block
 197    frequencies.  It would also benefit from recomputing frequencies
 198    if profile data is not available since frequencies often get out
 199    of sync with reality.  */
 200
 201 static basic_block
 202 select_best_block (basic_block early_bb,
 203                    basic_block late_bb,
 204                    gimple stmt)
 205 {
 206   basic_block best_bb = late_bb;
 207   basic_block temp_bb = late_bb;
 208   int threshold;
 209
 210   while (temp_bb != early_bb)
 211     {
 212       /* If we've moved into a lower loop nest, then that becomes
 213          our best block.  */
 214       if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
 215         best_bb = temp_bb;
 216
 217       /* Walk up the dominator tree, hopefully we'll find a shallower
 218          loop nest.  */
 219       temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
 220     }
 221
 222   /* If we found a shallower loop nest, then we always consider that
 223      a win.  This will always give us the most control dependent block
 224      within that loop nest.  */
 225   if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
 226     return best_bb;
 227
 228   /* Get the sinking threshold.  If the statement to be moved has memory
 229      operands, then increase the threshold by 7% as those are even more
 230      profitable to avoid, clamping at 100%.  */
 231   threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
 232   if (gimple_vuse (stmt) || gimple_vdef (stmt))
 233     {
 234       threshold += 7;
 235       if (threshold > 100)
 236         threshold = 100;
 237     }
 238
 239   /* If BEST_BB is at the same nesting level, then require it to have
 240      significantly lower execution frequency to avoid gratutious movement.  */
 241   if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
 242       && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
 243     return best_bb;
 244
 245   /* No better block found, so return EARLY_BB, which happens to be the
 246      statement's original block.  */
 247   return early_bb;
 248 }
 249
 250 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 251    determine the location to sink the statement to, if any.
 252    Returns true if there is such location; in that case, TOGSI points to the
 253    statement before that STMT should be moved.  */
 254
 255 static bool
 256 statement_sink_location (gimple stmt, basic_block frombb,
 257                          gimple_stmt_iterator *togsi)
 258 {
 259   gimple use;
 260   use_operand_p one_use = NULL_USE_OPERAND_P;
 261   basic_block sinkbb;
 262   use_operand_p use_p;
 263   def_operand_p def_p;
 264   ssa_op_iter iter;
 265   imm_use_iterator imm_iter;
 266
 267   /* We only can sink assignments.  */
 268   if (!is_gimple_assign (stmt))
 269     return false;
 270
 271   /* We only can sink stmts with a single definition.  */
 272   def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
 273   if (def_p == NULL_DEF_OPERAND_P)
 274     return false;
 275
 276   /* Return if there are no immediate uses of this stmt.  */
 277   if (has_zero_uses (DEF_FROM_PTR (def_p)))
 278     return false;
 279
 280   /* There are a few classes of things we can't or don't move, some because we
 281      don't have code to handle it, some because it's not profitable and some
 282      because it's not legal.
 283
 284      We can't sink things that may be global stores, at least not without
 285      calculating a lot more information, because we may cause it to no longer
 286      be seen by an external routine that needs it depending on where it gets
 287      moved to.
 288
 289      We don't want to sink loads from memory.
 290
 291      We can't sink statements that end basic blocks without splitting the
 292      incoming edge for the sink location to place it there.
 293
 294      We can't sink statements that have volatile operands.
 295
 296      We don't want to sink dead code, so anything with 0 immediate uses is not
 297      sunk.
 298
 299      Don't sink BLKmode assignments if current function has any local explicit
 300      register variables, as BLKmode assignments may involve memcpy or memset
 301      calls or, on some targets, inline expansion thereof that sometimes need
 302      to use specific hard registers.
 303
 304   */
 305   if (stmt_ends_bb_p (stmt)
 306       || gimple_has_side_effects (stmt)
 307       || gimple_has_volatile_ops (stmt)
 308       || (gimple_vuse (stmt) && !gimple_vdef (stmt))
 309       || (cfun->has_local_explicit_reg_vars
 310           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 311     return false;
 312
 313   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
 314     return false;
 315
 316   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 317     {
 318       tree use = USE_FROM_PTR (use_p);
 319       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 320         return false;
 321     }
 322
 323   use = NULL;
 324
 325   /* If stmt is a store the one and only use needs to be the VOP
 326      merging PHI node.  */
 327   if (gimple_vdef (stmt))
 328     {
 329       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
 330         {
 331           gimple use_stmt = USE_STMT (use_p);
 332
 333           /* A killing definition is not a use.  */
 334           if ((gimple_has_lhs (use_stmt)
 335                && operand_equal_p (gimple_assign_lhs (stmt),
 336                                    gimple_get_lhs (use_stmt), 0))
 337               || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt)))
 338             {
 339               /* If use_stmt is or might be a nop assignment then USE_STMT
 340                  acts as a use as well as definition.  */
 341               if (stmt != use_stmt
 342                   && ref_maybe_used_by_stmt_p (use_stmt,
 343                                                gimple_assign_lhs (stmt)))
 344                 return false;
 345               continue;
 346             }
 347
 348           if (gimple_code (use_stmt) != GIMPLE_PHI)
 349             return false;
 350
 351           if (use
 352               && use != use_stmt)
 353             return false;
 354
 355           use = use_stmt;
 356         }
 357       if (!use)
 358         return false;
 359     }
 360   /* If all the immediate uses are not in the same place, find the nearest
 361      common dominator of all the immediate uses.  For PHI nodes, we have to
 362      find the nearest common dominator of all of the predecessor blocks, since
 363      that is where insertion would have to take place.  */
 364   else if (!all_immediate_uses_same_place (stmt))
 365     {
 366       bool debug_stmts = false;
 367       basic_block commondom = nearest_common_dominator_of_uses (stmt,
 368                                                                 &debug_stmts);
 369
 370       if (commondom == frombb)
 371         return false;
 372
 373       /* Our common dominator has to be dominated by frombb in order to be a
 374          trivially safe place to put this statement, since it has multiple
 375          uses.  */
 376       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 377         return false;
 378
 379       commondom = select_best_block (frombb, commondom, stmt);
 380
 381       if (commondom == frombb)
 382         return false;
 383
 384       *togsi = gsi_after_labels (commondom);
 385
 386       return true;
 387     }
 388   else
 389     {
 390       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
 391         {
 392           if (is_gimple_debug (USE_STMT (one_use)))
 393             continue;
 394           break;
 395         }
 396       use = USE_STMT (one_use);
 397
 398       if (gimple_code (use) != GIMPLE_PHI)
 399         {
 400           sinkbb = gimple_bb (use);
 401           sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
 402
 403           if (sinkbb == frombb)
 404             return false;
 405
 406           *togsi = gsi_for_stmt (use);
 407
 408           return true;
 409         }
 410     }
 411
 412   sinkbb = find_bb_for_arg (use, DEF_FROM_PTR (def_p));
 413
 414   /* This can happen if there are multiple uses in a PHI.  */
 415   if (!sinkbb)
 416     return false;
 417
 418   sinkbb = select_best_block (frombb, sinkbb, stmt);
 419   if (!sinkbb || sinkbb == frombb)
 420     return false;
 421
 422   /* If the latch block is empty, don't make it non-empty by sinking
 423      something into it.  */
 424   if (sinkbb == frombb->loop_father->latch
 425       && empty_block_p (sinkbb))
 426     return false;
 427
 428   *togsi = gsi_after_labels (sinkbb);
 429
 430   return true;
 431 }
 432
 433 /* Perform code sinking on BB */
 434
 435 static void
 436 sink_code_in_bb (basic_block bb)
 437 {
 438   basic_block son;
 439   gimple_stmt_iterator gsi;
 440   edge_iterator ei;
 441   edge e;
 442   bool last = true;
 443
 444   /* If this block doesn't dominate anything, there can't be any place to sink
 445      the statements to.  */
 446   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 447     goto earlyout;
 448
 449   /* We can't move things across abnormal edges, so don't try.  */
 450   FOR_EACH_EDGE (e, ei, bb->succs)
 451     if (e->flags & EDGE_ABNORMAL)
 452       goto earlyout;
 453
 454   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 455     {
 456       gimple stmt = gsi_stmt (gsi);
 457       gimple_stmt_iterator togsi;
 458
 459       if (!statement_sink_location (stmt, bb, &togsi))
 460         {
 461           if (!gsi_end_p (gsi))
 462             gsi_prev (&gsi);
 463           last = false;
 464           continue;
 465         }
 466       if (dump_file)
 467         {
 468           fprintf (dump_file, "Sinking ");
 469           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 470           fprintf (dump_file, " from bb %d to bb %d\n",
 471                    bb->index, (gsi_bb (togsi))->index);
 472         }
 473
 474       /* Update virtual operands of statements in the path we
 475          do not sink to.  */
 476       if (gimple_vdef (stmt))
 477         {
 478           imm_use_iterator iter;
 479           use_operand_p use_p;
 480           gimple vuse_stmt;
 481
 482           FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
 483             if (gimple_code (vuse_stmt) != GIMPLE_PHI)
 484               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 485                 SET_USE (use_p, gimple_vuse (stmt));
 486         }
 487
 488       /* If this is the end of the basic block, we need to insert at the end
 489          of the basic block.  */
 490       if (gsi_end_p (togsi))
 491         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 492       else
 493         gsi_move_before (&gsi, &togsi);
 494
 495       sink_stats.sunk++;
 496
 497       /* If we've just removed the last statement of the BB, the
 498          gsi_end_p() test below would fail, but gsi_prev() would have
 499          succeeded, and we want it to succeed.  So we keep track of
 500          whether we're at the last statement and pick up the new last
 501          statement.  */
 502       if (last)
 503         {
 504           gsi = gsi_last_bb (bb);
 505           continue;
 506         }
 507
 508       last = false;
 509       if (!gsi_end_p (gsi))
 510         gsi_prev (&gsi);
 511
 512     }
 513  earlyout:
 514   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 515        son;
 516        son = next_dom_son (CDI_POST_DOMINATORS, son))
 517     {
 518       sink_code_in_bb (son);
 519     }
 520 }
 521
 522 /* Perform code sinking.
 523    This moves code down the flowgraph when we know it would be
 524    profitable to do so, or it wouldn't increase the number of
 525    executions of the statement.
 526
 527    IE given
 528
 529    a_1 = b + c;
 530    if (<something>)
 531    {
 532    }
 533    else
 534    {
 535      foo (&b, &c);
 536      a_5 = b + c;
 537    }
 538    a_6 = PHI (a_5, a_1);
 539    USE a_6.
 540
 541    we'll transform this into:
 542
 543    if (<something>)
 544    {
 545       a_1 = b + c;
 546    }
 547    else
 548    {
 549       foo (&b, &c);
 550       a_5 = b + c;
 551    }
 552    a_6 = PHI (a_5, a_1);
 553    USE a_6.
 554
 555    Note that this reduces the number of computations of a = b + c to 1
 556    when we take the else edge, instead of 2.
 557 */
 558 static void
 559 execute_sink_code (void)
 560 {
 561   loop_optimizer_init (LOOPS_NORMAL);
 562
 563   connect_infinite_loops_to_exit ();
 564   memset (&sink_stats, 0, sizeof (sink_stats));
 565   calculate_dominance_info (CDI_DOMINATORS);
 566   calculate_dominance_info (CDI_POST_DOMINATORS);
 567   sink_code_in_bb (EXIT_BLOCK_PTR);
 568   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 569   free_dominance_info (CDI_POST_DOMINATORS);
 570   remove_fake_exit_edges ();
 571   loop_optimizer_finalize ();
 572 }
 573
 574 /* Gate and execute functions for PRE.  */
 575
 576 static unsigned int
 577 do_sink (void)
 578 {
 579   execute_sink_code ();
 580   return 0;
 581 }
 582
 583 static bool
 584 gate_sink (void)
 585 {
 586   return flag_tree_sink != 0;
 587 }
 588
 589 namespace {
 590
 591 const pass_data pass_data_sink_code =
 592 {
 593   GIMPLE_PASS, /* type */
 594   "sink", /* name */
 595   OPTGROUP_NONE, /* optinfo_flags */
 596   true, /* has_gate */
 597   true, /* has_execute */
 598   TV_TREE_SINK, /* tv_id */
 599   ( PROP_no_crit_edges | PROP_cfg | PROP_ssa ), /* properties_required */
 600   0, /* properties_provided */
 601   0, /* properties_destroyed */
 602   0, /* todo_flags_start */
 603   ( TODO_update_ssa | TODO_verify_ssa
 604     | TODO_verify_flow ), /* todo_flags_finish */
 605 };
 606
 607 class pass_sink_code : public gimple_opt_pass
 608 {
 609 public:
 610   pass_sink_code(gcc::context *ctxt)
 611     : gimple_opt_pass(pass_data_sink_code, ctxt)
 612   {}
 613
 614   /* opt_pass methods: */
 615   bool gate () { return gate_sink (); }
 616   unsigned int execute () { return do_sink (); }
 617
 618 }; // class pass_sink_code
 619
 620 } // anon namespace
 621
 622 gimple_opt_pass *
 623 make_pass_sink_code (gcc::context *ctxt)
 624 {
 625   return new pass_sink_code (ctxt);
 626 }