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 (def_operand_p def_p)
 114 {
 115   tree var = DEF_FROM_PTR (def_p);
 116   imm_use_iterator imm_iter;
 117   use_operand_p use_p;
 118
 119   gimple firstuse = NULL;
 120   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 121     {
 122       if (is_gimple_debug (USE_STMT (use_p)))
 123         continue;
 124       if (firstuse == NULL)
 125         firstuse = USE_STMT (use_p);
 126       else
 127         if (firstuse != USE_STMT (use_p))
 128           return false;
 129     }
 130
 131   return true;
 132 }
 133
 134 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 135
 136 static basic_block
 137 nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
 138 {
 139   tree var = DEF_FROM_PTR (def_p);
 140   bitmap blocks = BITMAP_ALLOC (NULL);
 141   basic_block commondom;
 142   unsigned int j;
 143   bitmap_iterator bi;
 144   imm_use_iterator imm_iter;
 145   use_operand_p use_p;
 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_FOR_FN (cfun))
 170         {
 171           BITMAP_FREE (blocks);
 172           return NULL;
 173         }
 174       bitmap_set_bit (blocks, useblock->index);
 175     }
 176   commondom = BASIC_BLOCK_FOR_FN (cfun, bitmap_first_set_bit (blocks));
 177   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 178     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 179                                           BASIC_BLOCK_FOR_FN (cfun, j));
 180   BITMAP_FREE (blocks);
 181   return commondom;
 182 }
 183
 184 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
 185    tree, return the best basic block between them (inclusive) to place
 186    statements.
 187
 188    We want the most control dependent block in the shallowest loop nest.
 189
 190    If the resulting block is in a shallower loop nest, then use it.  Else
 191    only use the resulting block if it has significantly lower execution
 192    frequency than EARLY_BB to avoid gratutious statement movement.  We
 193    consider statements with VOPS more desirable to move.
 194
 195    This pass would obviously benefit from PDO as it utilizes block
 196    frequencies.  It would also benefit from recomputing frequencies
 197    if profile data is not available since frequencies often get out
 198    of sync with reality.  */
 199
 200 static basic_block
 201 select_best_block (basic_block early_bb,
 202                    basic_block late_bb,
 203                    gimple stmt)
 204 {
 205   basic_block best_bb = late_bb;
 206   basic_block temp_bb = late_bb;
 207   int threshold;
 208
 209   while (temp_bb != early_bb)
 210     {
 211       /* If we've moved into a lower loop nest, then that becomes
 212          our best block.  */
 213       if (bb_loop_depth (temp_bb) < bb_loop_depth (best_bb))
 214         best_bb = temp_bb;
 215
 216       /* Walk up the dominator tree, hopefully we'll find a shallower
 217          loop nest.  */
 218       temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
 219     }
 220
 221   /* If we found a shallower loop nest, then we always consider that
 222      a win.  This will always give us the most control dependent block
 223      within that loop nest.  */
 224   if (bb_loop_depth (best_bb) < bb_loop_depth (early_bb))
 225     return best_bb;
 226
 227   /* Get the sinking threshold.  If the statement to be moved has memory
 228      operands, then increase the threshold by 7% as those are even more
 229      profitable to avoid, clamping at 100%.  */
 230   threshold = PARAM_VALUE (PARAM_SINK_FREQUENCY_THRESHOLD);
 231   if (gimple_vuse (stmt) || gimple_vdef (stmt))
 232     {
 233       threshold += 7;
 234       if (threshold > 100)
 235         threshold = 100;
 236     }
 237
 238   /* If BEST_BB is at the same nesting level, then require it to have
 239      significantly lower execution frequency to avoid gratutious movement.  */
 240   if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
 241       && best_bb->frequency < (early_bb->frequency * threshold / 100.0))
 242     return best_bb;
 243
 244   /* No better block found, so return EARLY_BB, which happens to be the
 245      statement's original block.  */
 246   return early_bb;
 247 }
 248
 249 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 250    determine the location to sink the statement to, if any.
 251    Returns true if there is such location; in that case, TOGSI points to the
 252    statement before that STMT should be moved.  */
 253
 254 static bool
 255 statement_sink_location (gimple stmt, basic_block frombb,
 256                          gimple_stmt_iterator *togsi)
 257 {
 258   gimple use;
 259   use_operand_p one_use = NULL_USE_OPERAND_P;
 260   basic_block sinkbb;
 261   use_operand_p use_p;
 262   def_operand_p def_p;
 263   ssa_op_iter iter;
 264   imm_use_iterator imm_iter;
 265
 266   /* We only can sink assignments.  */
 267   if (!is_gimple_assign (stmt))
 268     return false;
 269
 270   /* We only can sink stmts with a single definition.  */
 271   def_p = single_ssa_def_operand (stmt, SSA_OP_ALL_DEFS);
 272   if (def_p == NULL_DEF_OPERAND_P)
 273     return false;
 274
 275   /* Return if there are no immediate uses of this stmt.  */
 276   if (has_zero_uses (DEF_FROM_PTR (def_p)))
 277     return false;
 278
 279   /* There are a few classes of things we can't or don't move, some because we
 280      don't have code to handle it, some because it's not profitable and some
 281      because it's not legal.
 282
 283      We can't sink things that may be global stores, at least not without
 284      calculating a lot more information, because we may cause it to no longer
 285      be seen by an external routine that needs it depending on where it gets
 286      moved to.
 287
 288      We can't sink statements that end basic blocks without splitting the
 289      incoming edge for the sink location to place it there.
 290
 291      We can't sink statements that have volatile operands.
 292
 293      We don't want to sink dead code, so anything with 0 immediate uses is not
 294      sunk.
 295
 296      Don't sink BLKmode assignments if current function has any local explicit
 297      register variables, as BLKmode assignments may involve memcpy or memset
 298      calls or, on some targets, inline expansion thereof that sometimes need
 299      to use specific hard registers.
 300
 301   */
 302   if (stmt_ends_bb_p (stmt)
 303       || gimple_has_side_effects (stmt)
 304       || gimple_has_volatile_ops (stmt)
 305       || (cfun->has_local_explicit_reg_vars
 306           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 307     return false;
 308
 309   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (DEF_FROM_PTR (def_p)))
 310     return false;
 311
 312   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 313     {
 314       tree use = USE_FROM_PTR (use_p);
 315       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 316         return false;
 317     }
 318
 319   use = NULL;
 320
 321   /* If stmt is a store the one and only use needs to be the VOP
 322      merging PHI node.  */
 323   if (virtual_operand_p (DEF_FROM_PTR (def_p)))
 324     {
 325       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
 326         {
 327           gimple use_stmt = USE_STMT (use_p);
 328
 329           /* A killing definition is not a use.  */
 330           if ((gimple_has_lhs (use_stmt)
 331                && operand_equal_p (gimple_assign_lhs (stmt),
 332                                    gimple_get_lhs (use_stmt), 0))
 333               || stmt_kills_ref_p (use_stmt, gimple_assign_lhs (stmt)))
 334             {
 335               /* If use_stmt is or might be a nop assignment then USE_STMT
 336                  acts as a use as well as definition.  */
 337               if (stmt != use_stmt
 338                   && ref_maybe_used_by_stmt_p (use_stmt,
 339                                                gimple_assign_lhs (stmt)))
 340                 return false;
 341               continue;
 342             }
 343
 344           if (gimple_code (use_stmt) != GIMPLE_PHI)
 345             return false;
 346
 347           if (use
 348               && use != use_stmt)
 349             return false;
 350
 351           use = use_stmt;
 352         }
 353       if (!use)
 354         return false;
 355     }
 356   /* If all the immediate uses are not in the same place, find the nearest
 357      common dominator of all the immediate uses.  For PHI nodes, we have to
 358      find the nearest common dominator of all of the predecessor blocks, since
 359      that is where insertion would have to take place.  */
 360   else if (gimple_vuse (stmt)
 361            || !all_immediate_uses_same_place (def_p))
 362     {
 363       bool debug_stmts = false;
 364       basic_block commondom = nearest_common_dominator_of_uses (def_p,
 365                                                                 &debug_stmts);
 366
 367       if (commondom == frombb)
 368         return false;
 369
 370       /* If this is a load then do not sink past any stores.
 371          ???  This is overly simple but cheap.  We basically look
 372          for an existing load with the same VUSE in the path to one
 373          of the sink candidate blocks and we adjust commondom to the
 374          nearest to commondom.  */
 375       if (gimple_vuse (stmt))
 376         {
 377           imm_use_iterator imm_iter;
 378           use_operand_p use_p;
 379           basic_block found = NULL;
 380           FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_vuse (stmt))
 381             {
 382               gimple use_stmt = USE_STMT (use_p);
 383               basic_block bb = gimple_bb (use_stmt);
 384               /* For PHI nodes the block we know sth about
 385                  is the incoming block with the use.  */
 386               if (gimple_code (use_stmt) == GIMPLE_PHI)
 387                 bb = EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src;
 388               /* Any dominator of commondom would be ok with
 389                  adjusting commondom to that block.  */
 390               bb = nearest_common_dominator (CDI_DOMINATORS, bb, commondom);
 391               if (!found)
 392                 found = bb;
 393               else if (dominated_by_p (CDI_DOMINATORS, bb, found))
 394                 found = bb;
 395               /* If we can't improve, stop.  */
 396               if (found == commondom)
 397                 break;
 398             }
 399           commondom = found;
 400           if (commondom == frombb)
 401             return false;
 402         }
 403
 404       /* Our common dominator has to be dominated by frombb in order to be a
 405          trivially safe place to put this statement, since it has multiple
 406          uses.  */
 407       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 408         return false;
 409
 410       commondom = select_best_block (frombb, commondom, stmt);
 411
 412       if (commondom == frombb)
 413         return false;
 414
 415       *togsi = gsi_after_labels (commondom);
 416
 417       return true;
 418     }
 419   else
 420     {
 421       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, DEF_FROM_PTR (def_p))
 422         {
 423           if (is_gimple_debug (USE_STMT (one_use)))
 424             continue;
 425           break;
 426         }
 427       use = USE_STMT (one_use);
 428
 429       if (gimple_code (use) != GIMPLE_PHI)
 430         {
 431           sinkbb = gimple_bb (use);
 432           sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
 433
 434           if (sinkbb == frombb)
 435             return false;
 436
 437           *togsi = gsi_for_stmt (use);
 438
 439           return true;
 440         }
 441     }
 442
 443   sinkbb = find_bb_for_arg (use, DEF_FROM_PTR (def_p));
 444
 445   /* This can happen if there are multiple uses in a PHI.  */
 446   if (!sinkbb)
 447     return false;
 448
 449   sinkbb = select_best_block (frombb, sinkbb, stmt);
 450   if (!sinkbb || sinkbb == frombb)
 451     return false;
 452
 453   /* If the latch block is empty, don't make it non-empty by sinking
 454      something into it.  */
 455   if (sinkbb == frombb->loop_father->latch
 456       && empty_block_p (sinkbb))
 457     return false;
 458
 459   *togsi = gsi_after_labels (sinkbb);
 460
 461   return true;
 462 }
 463
 464 /* Perform code sinking on BB */
 465
 466 static void
 467 sink_code_in_bb (basic_block bb)
 468 {
 469   basic_block son;
 470   gimple_stmt_iterator gsi;
 471   edge_iterator ei;
 472   edge e;
 473   bool last = true;
 474
 475   /* If this block doesn't dominate anything, there can't be any place to sink
 476      the statements to.  */
 477   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 478     goto earlyout;
 479
 480   /* We can't move things across abnormal edges, so don't try.  */
 481   FOR_EACH_EDGE (e, ei, bb->succs)
 482     if (e->flags & EDGE_ABNORMAL)
 483       goto earlyout;
 484
 485   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 486     {
 487       gimple stmt = gsi_stmt (gsi);
 488       gimple_stmt_iterator togsi;
 489
 490       if (!statement_sink_location (stmt, bb, &togsi))
 491         {
 492           if (!gsi_end_p (gsi))
 493             gsi_prev (&gsi);
 494           last = false;
 495           continue;
 496         }
 497       if (dump_file)
 498         {
 499           fprintf (dump_file, "Sinking ");
 500           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 501           fprintf (dump_file, " from bb %d to bb %d\n",
 502                    bb->index, (gsi_bb (togsi))->index);
 503         }
 504
 505       /* Update virtual operands of statements in the path we
 506          do not sink to.  */
 507       if (gimple_vdef (stmt))
 508         {
 509           imm_use_iterator iter;
 510           use_operand_p use_p;
 511           gimple vuse_stmt;
 512
 513           FOR_EACH_IMM_USE_STMT (vuse_stmt, iter, gimple_vdef (stmt))
 514             if (gimple_code (vuse_stmt) != GIMPLE_PHI)
 515               FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 516                 SET_USE (use_p, gimple_vuse (stmt));
 517         }
 518
 519       /* If this is the end of the basic block, we need to insert at the end
 520          of the basic block.  */
 521       if (gsi_end_p (togsi))
 522         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 523       else
 524         gsi_move_before (&gsi, &togsi);
 525
 526       sink_stats.sunk++;
 527
 528       /* If we've just removed the last statement of the BB, the
 529          gsi_end_p() test below would fail, but gsi_prev() would have
 530          succeeded, and we want it to succeed.  So we keep track of
 531          whether we're at the last statement and pick up the new last
 532          statement.  */
 533       if (last)
 534         {
 535           gsi = gsi_last_bb (bb);
 536           continue;
 537         }
 538
 539       last = false;
 540       if (!gsi_end_p (gsi))
 541         gsi_prev (&gsi);
 542
 543     }
 544  earlyout:
 545   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 546        son;
 547        son = next_dom_son (CDI_POST_DOMINATORS, son))
 548     {
 549       sink_code_in_bb (son);
 550     }
 551 }
 552
 553 /* Perform code sinking.
 554    This moves code down the flowgraph when we know it would be
 555    profitable to do so, or it wouldn't increase the number of
 556    executions of the statement.
 557
 558    IE given
 559
 560    a_1 = b + c;
 561    if (<something>)
 562    {
 563    }
 564    else
 565    {
 566      foo (&b, &c);
 567      a_5 = b + c;
 568    }
 569    a_6 = PHI (a_5, a_1);
 570    USE a_6.
 571
 572    we'll transform this into:
 573
 574    if (<something>)
 575    {
 576       a_1 = b + c;
 577    }
 578    else
 579    {
 580       foo (&b, &c);
 581       a_5 = b + c;
 582    }
 583    a_6 = PHI (a_5, a_1);
 584    USE a_6.
 585
 586    Note that this reduces the number of computations of a = b + c to 1
 587    when we take the else edge, instead of 2.
 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_execute */
 597   TV_TREE_SINK, /* tv_id */
 598   /* PROP_no_crit_edges is ensured by running split_critical_edges in
 599      pass_data_sink_code::execute ().  */
 600   ( PROP_cfg | PROP_ssa ), /* properties_required */
 601   0, /* properties_provided */
 602   0, /* properties_destroyed */
 603   0, /* todo_flags_start */
 604   TODO_update_ssa, /* 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   virtual bool gate (function *) { return flag_tree_sink != 0; }
 616   virtual unsigned int execute (function *);
 617
 618 }; // class pass_sink_code
 619
 620 unsigned int
 621 pass_sink_code::execute (function *fun)
 622 {
 623   loop_optimizer_init (LOOPS_NORMAL);
 624   split_critical_edges ();
 625   connect_infinite_loops_to_exit ();
 626   memset (&sink_stats, 0, sizeof (sink_stats));
 627   calculate_dominance_info (CDI_DOMINATORS);
 628   calculate_dominance_info (CDI_POST_DOMINATORS);
 629   sink_code_in_bb (EXIT_BLOCK_PTR_FOR_FN (fun));
 630   statistics_counter_event (fun, "Sunk statements", sink_stats.sunk);
 631   free_dominance_info (CDI_POST_DOMINATORS);
 632   remove_fake_exit_edges ();
 633   loop_optimizer_finalize ();
 634
 635   return 0;
 636 }
 637
 638 } // anon namespace
 639
 640 gimple_opt_pass *
 641 make_pass_sink_code (gcc::context *ctxt)
 642 {
 643   return new pass_sink_code (ctxt);
 644 }