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