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