gcc/tree-ssa-sink.c

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