gcc/tree-ssa-sink.c

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