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