gcc/tree-ssa-sink.c

   1 /* Code sinking for trees
   2    Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Daniel Berlin <dan@dberlin.org>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "basic-block.h"
  28 #include "gimple-pretty-print.h"
  29 #include "tree-inline.h"
  30 #include "tree-flow.h"
  31 #include "gimple.h"
  32 #include "tree-dump.h"
  33 #include "timevar.h"
  34 #include "fibheap.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 "bitmap.h"
  41 #include "langhooks.h"
  42 #include "cfgloop.h"
  43
  44 /* TODO:
  45    1. Sinking store only using scalar promotion (IE without moving the RHS):
  46
  47    *q = p;
  48    p = p + 1;
  49    if (something)
  50      *q = <not p>;
  51    else
  52      y = *q;
  53
  54
  55    should become
  56    sinktemp = p;
  57    p = p + 1;
  58    if (something)
  59      *q = <not p>;
  60    else
  61    {
  62      *q = sinktemp;
  63      y = *q
  64    }
  65    Store copy propagation will take care of the store elimination above.
  66
  67
  68    2. Sinking using Partial Dead Code Elimination.  */
  69
  70
  71 static struct
  72 {
  73   /* The number of statements sunk down the flowgraph by code sinking.  */
  74   int sunk;
  75
  76 } sink_stats;
  77
  78
  79 /* Given a PHI, and one of its arguments (DEF), find the edge for
  80    that argument and return it.  If the argument occurs twice in the PHI node,
  81    we return NULL.  */
  82
  83 static basic_block
  84 find_bb_for_arg (gimple phi, tree def)
  85 {
  86   size_t i;
  87   bool foundone = false;
  88   basic_block result = NULL;
  89   for (i = 0; i < gimple_phi_num_args (phi); i++)
  90     if (PHI_ARG_DEF (phi, i) == def)
  91       {
  92         if (foundone)
  93           return NULL;
  94         foundone = true;
  95         result = gimple_phi_arg_edge (phi, i)->src;
  96       }
  97   return result;
  98 }
  99
 100 /* When the first immediate use is in a statement, then return true if all
 101    immediate uses in IMM are in the same statement.
 102    We could also do the case where  the first immediate use is in a phi node,
 103    and all the other uses are in phis in the same basic block, but this
 104    requires some expensive checking later (you have to make sure no def/vdef
 105    in the statement occurs for multiple edges in the various phi nodes it's
 106    used in, so that you only have one place you can sink it to.  */
 107
 108 static bool
 109 all_immediate_uses_same_place (gimple stmt)
 110 {
 111   gimple firstuse = NULL;
 112   ssa_op_iter op_iter;
 113   imm_use_iterator imm_iter;
 114   use_operand_p use_p;
 115   tree var;
 116
 117   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 118     {
 119       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 120         {
 121           if (is_gimple_debug (USE_STMT (use_p)))
 122             continue;
 123           if (firstuse == NULL)
 124             firstuse = USE_STMT (use_p);
 125           else
 126             if (firstuse != USE_STMT (use_p))
 127               return false;
 128         }
 129     }
 130
 131   return true;
 132 }
 133
 134 /* Some global stores don't necessarily have VDEF's of global variables,
 135    but we still must avoid moving them around.  */
 136
 137 bool
 138 is_hidden_global_store (gimple stmt)
 139 {
 140   /* Check virtual definitions.  If we get here, the only virtual
 141      definitions we should see are those generated by assignment or call
 142      statements.  */
 143   if (gimple_vdef (stmt))
 144     {
 145       tree lhs;
 146
 147       gcc_assert (is_gimple_assign (stmt) || is_gimple_call (stmt));
 148
 149       /* Note that we must not check the individual virtual operands
 150          here.  In particular, if this is an aliased store, we could
 151          end up with something like the following (SSA notation
 152          redacted for brevity):
 153
 154                 foo (int *p, int i)
 155                 {
 156                   int x;
 157                   p_1 = (i_2 > 3) ? &x : p;
 158
 159                   # x_4 = VDEF <x_3>
 160                   *p_1 = 5;
 161
 162                   return 2;
 163                 }
 164
 165          Notice that the store to '*p_1' should be preserved, if we
 166          were to check the virtual definitions in that store, we would
 167          not mark it needed.  This is because 'x' is not a global
 168          variable.
 169
 170          Therefore, we check the base address of the LHS.  If the
 171          address is a pointer, we check if its name tag or symbol tag is
 172          a global variable.  Otherwise, we check if the base variable
 173          is a global.  */
 174       lhs = gimple_get_lhs (stmt);
 175
 176       if (REFERENCE_CLASS_P (lhs))
 177         lhs = get_base_address (lhs);
 178
 179       if (lhs == NULL_TREE)
 180         {
 181           /* If LHS is NULL, it means that we couldn't get the base
 182              address of the reference.  In which case, we should not
 183              move this store.  */
 184           return true;
 185         }
 186       else if (DECL_P (lhs))
 187         {
 188           /* If the store is to a global symbol, we need to keep it.  */
 189           if (is_global_var (lhs))
 190             return true;
 191
 192         }
 193       else if (INDIRECT_REF_P (lhs))
 194         return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0));
 195       else
 196         gcc_unreachable ();
 197     }
 198
 199   return false;
 200 }
 201
 202 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 203
 204 static basic_block
 205 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
 206 {
 207   bitmap blocks = BITMAP_ALLOC (NULL);
 208   basic_block commondom;
 209   unsigned int j;
 210   bitmap_iterator bi;
 211   ssa_op_iter op_iter;
 212   imm_use_iterator imm_iter;
 213   use_operand_p use_p;
 214   tree var;
 215
 216   bitmap_clear (blocks);
 217   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 218     {
 219       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 220         {
 221           gimple usestmt = USE_STMT (use_p);
 222           basic_block useblock;
 223
 224           if (gimple_code (usestmt) == GIMPLE_PHI)
 225             {
 226               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 227
 228               useblock = gimple_phi_arg_edge (usestmt, idx)->src;
 229             }
 230           else if (is_gimple_debug (usestmt))
 231             {
 232               *debug_stmts = true;
 233               continue;
 234             }
 235           else
 236             {
 237               useblock = gimple_bb (usestmt);
 238             }
 239
 240           /* Short circuit. Nothing dominates the entry block.  */
 241           if (useblock == ENTRY_BLOCK_PTR)
 242             {
 243               BITMAP_FREE (blocks);
 244               return NULL;
 245             }
 246           bitmap_set_bit (blocks, useblock->index);
 247         }
 248     }
 249   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 250   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 251     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 252                                           BASIC_BLOCK (j));
 253   BITMAP_FREE (blocks);
 254   return commondom;
 255 }
 256
 257 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 258    determine the location to sink the statement to, if any.
 259    Returns true if there is such location; in that case, TOGSI points to the
 260    statement before that STMT should be moved.  */
 261
 262 static bool
 263 statement_sink_location (gimple stmt, basic_block frombb,
 264                          gimple_stmt_iterator *togsi)
 265 {
 266   gimple use;
 267   tree def;
 268   use_operand_p one_use = NULL_USE_OPERAND_P;
 269   basic_block sinkbb;
 270   use_operand_p use_p;
 271   def_operand_p def_p;
 272   ssa_op_iter iter;
 273   imm_use_iterator imm_iter;
 274
 275   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 276     {
 277       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 278         {
 279           if (is_gimple_debug (USE_STMT (one_use)))
 280             continue;
 281
 282           break;
 283         }
 284       if (one_use != NULL_USE_OPERAND_P)
 285         break;
 286     }
 287
 288   /* Return if there are no immediate uses of this stmt.  */
 289   if (one_use == NULL_USE_OPERAND_P)
 290     return false;
 291
 292   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 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 don't want to sink loads from memory.
 305
 306      We can't sink statements that end basic blocks without splitting the
 307      incoming edge for the sink location to place it there.
 308
 309      We can't sink statements that have volatile operands.
 310
 311      We don't want to sink dead code, so anything with 0 immediate uses is not
 312      sunk.
 313
 314      Don't sink BLKmode assignments if current function has any local explicit
 315      register variables, as BLKmode assignments may involve memcpy or memset
 316      calls or, on some targets, inline expansion thereof that sometimes need
 317      to use specific hard registers.
 318
 319   */
 320   if (stmt_ends_bb_p (stmt)
 321       || gimple_has_side_effects (stmt)
 322       || is_hidden_global_store (stmt)
 323       || gimple_has_volatile_ops (stmt)
 324       || gimple_vuse (stmt)
 325       || (cfun->has_local_explicit_reg_vars
 326           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 327     return false;
 328
 329   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 330     {
 331       tree def = DEF_FROM_PTR (def_p);
 332       if (is_global_var (SSA_NAME_VAR (def))
 333           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 334         return false;
 335     }
 336
 337   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 338     {
 339       tree use = USE_FROM_PTR (use_p);
 340       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 341         return false;
 342     }
 343
 344   /* If all the immediate uses are not in the same place, find the nearest
 345      common dominator of all the immediate uses.  For PHI nodes, we have to
 346      find the nearest common dominator of all of the predecessor blocks, since
 347      that is where insertion would have to take place.  */
 348   if (!all_immediate_uses_same_place (stmt))
 349     {
 350       bool debug_stmts = false;
 351       basic_block commondom = nearest_common_dominator_of_uses (stmt,
 352                                                                 &debug_stmts);
 353
 354       if (commondom == frombb)
 355         return false;
 356
 357       /* Our common dominator has to be dominated by frombb in order to be a
 358          trivially safe place to put this statement, since it has multiple
 359          uses.  */
 360       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 361         return false;
 362
 363       /* It doesn't make sense to move to a dominator that post-dominates
 364          frombb, because it means we've just moved it into a path that always
 365          executes if frombb executes, instead of reducing the number of
 366          executions .  */
 367       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 368         {
 369           if (dump_file && (dump_flags & TDF_DETAILS))
 370             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 371           return false;
 372         }
 373
 374       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 375         return false;
 376       if (dump_file && (dump_flags & TDF_DETAILS))
 377         {
 378           fprintf (dump_file, "Common dominator of all uses is %d\n",
 379                    commondom->index);
 380         }
 381
 382       *togsi = gsi_after_labels (commondom);
 383
 384       return true;
 385     }
 386
 387   use = USE_STMT (one_use);
 388   if (gimple_code (use) != GIMPLE_PHI)
 389     {
 390       sinkbb = gimple_bb (use);
 391       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 392           || sinkbb->loop_father != frombb->loop_father)
 393         return false;
 394
 395       /* Move the expression to a post dominator can't reduce the number of
 396          executions.  */
 397       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 398         return false;
 399
 400       *togsi = gsi_for_stmt (use);
 401
 402       return true;
 403     }
 404
 405   /* Note that at this point, all uses must be in the same statement, so it
 406      doesn't matter which def op we choose, pick the first one.  */
 407   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 408     break;
 409
 410   sinkbb = find_bb_for_arg (use, def);
 411   if (!sinkbb)
 412     return false;
 413
 414   /* This will happen when you have
 415      a_3 = PHI <a_13, a_26>
 416
 417      a_26 = VDEF <a_3>
 418
 419      If the use is a phi, and is in the same bb as the def,
 420      we can't sink it.  */
 421
 422   if (gimple_bb (use) == frombb)
 423     return false;
 424   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 425       || sinkbb->loop_father != frombb->loop_father)
 426     return false;
 427
 428   /* Move the expression to a post dominator can't reduce the number of
 429      executions.  */
 430   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 431     return false;
 432
 433   *togsi = gsi_after_labels (sinkbb);
 434
 435   return true;
 436 }
 437
 438 /* Perform code sinking on BB */
 439
 440 static void
 441 sink_code_in_bb (basic_block bb)
 442 {
 443   basic_block son;
 444   gimple_stmt_iterator gsi;
 445   edge_iterator ei;
 446   edge e;
 447   bool last = true;
 448
 449   /* If this block doesn't dominate anything, there can't be any place to sink
 450      the statements to.  */
 451   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 452     goto earlyout;
 453
 454   /* We can't move things across abnormal edges, so don't try.  */
 455   FOR_EACH_EDGE (e, ei, bb->succs)
 456     if (e->flags & EDGE_ABNORMAL)
 457       goto earlyout;
 458
 459   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 460     {
 461       gimple stmt = gsi_stmt (gsi);
 462       gimple_stmt_iterator togsi;
 463
 464       if (!statement_sink_location (stmt, bb, &togsi))
 465         {
 466           if (!gsi_end_p (gsi))
 467             gsi_prev (&gsi);
 468           last = false;
 469           continue;
 470         }
 471       if (dump_file)
 472         {
 473           fprintf (dump_file, "Sinking ");
 474           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 475           fprintf (dump_file, " from bb %d to bb %d\n",
 476                    bb->index, (gsi_bb (togsi))->index);
 477         }
 478
 479       /* If this is the end of the basic block, we need to insert at the end
 480          of the basic block.  */
 481       if (gsi_end_p (togsi))
 482         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 483       else
 484         gsi_move_before (&gsi, &togsi);
 485
 486       sink_stats.sunk++;
 487
 488       /* If we've just removed the last statement of the BB, the
 489          gsi_end_p() test below would fail, but gsi_prev() would have
 490          succeeded, and we want it to succeed.  So we keep track of
 491          whether we're at the last statement and pick up the new last
 492          statement.  */
 493       if (last)
 494         {
 495           gsi = gsi_last_bb (bb);
 496           continue;
 497         }
 498
 499       last = false;
 500       if (!gsi_end_p (gsi))
 501         gsi_prev (&gsi);
 502
 503     }
 504  earlyout:
 505   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 506        son;
 507        son = next_dom_son (CDI_POST_DOMINATORS, son))
 508     {
 509       sink_code_in_bb (son);
 510     }
 511 }
 512
 513 /* Perform code sinking.
 514    This moves code down the flowgraph when we know it would be
 515    profitable to do so, or it wouldn't increase the number of
 516    executions of the statement.
 517
 518    IE given
 519
 520    a_1 = b + c;
 521    if (<something>)
 522    {
 523    }
 524    else
 525    {
 526      foo (&b, &c);
 527      a_5 = b + c;
 528    }
 529    a_6 = PHI (a_5, a_1);
 530    USE a_6.
 531
 532    we'll transform this into:
 533
 534    if (<something>)
 535    {
 536       a_1 = b + c;
 537    }
 538    else
 539    {
 540       foo (&b, &c);
 541       a_5 = b + c;
 542    }
 543    a_6 = PHI (a_5, a_1);
 544    USE a_6.
 545
 546    Note that this reduces the number of computations of a = b + c to 1
 547    when we take the else edge, instead of 2.
 548 */
 549 static void
 550 execute_sink_code (void)
 551 {
 552   loop_optimizer_init (LOOPS_NORMAL);
 553
 554   connect_infinite_loops_to_exit ();
 555   memset (&sink_stats, 0, sizeof (sink_stats));
 556   calculate_dominance_info (CDI_DOMINATORS);
 557   calculate_dominance_info (CDI_POST_DOMINATORS);
 558   sink_code_in_bb (EXIT_BLOCK_PTR);
 559   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 560   free_dominance_info (CDI_POST_DOMINATORS);
 561   remove_fake_exit_edges ();
 562   loop_optimizer_finalize ();
 563 }
 564
 565 /* Gate and execute functions for PRE.  */
 566
 567 static unsigned int
 568 do_sink (void)
 569 {
 570   execute_sink_code ();
 571   return 0;
 572 }
 573
 574 static bool
 575 gate_sink (void)
 576 {
 577   return flag_tree_sink != 0;
 578 }
 579
 580 struct gimple_opt_pass pass_sink_code =
 581 {
 582  {
 583   GIMPLE_PASS,
 584   "sink",                               /* name */
 585   gate_sink,                            /* gate */
 586   do_sink,                              /* execute */
 587   NULL,                                 /* sub */
 588   NULL,                                 /* next */
 589   0,                                    /* static_pass_number */
 590   TV_TREE_SINK,                         /* tv_id */
 591   PROP_no_crit_edges | PROP_cfg
 592     | PROP_ssa,                         /* properties_required */
 593   0,                                    /* properties_provided */
 594   0,                                    /* properties_destroyed */
 595   0,                                    /* todo_flags_start */
 596   TODO_update_ssa
 597     | TODO_dump_func
 598     | TODO_ggc_collect
 599     | TODO_verify_ssa                   /* todo_flags_finish */
 600  }
 601 };