gcc/tree-ssa-sink.c

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