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                || TREE_CODE (lhs) == MEM_REF)
 195         return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0));
 196       else if (CONSTANT_CLASS_P (lhs))
 197         return true;
 198       else
 199         gcc_unreachable ();
 200     }
 201
 202   return false;
 203 }
 204
 205 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 206
 207 static basic_block
 208 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
 209 {
 210   bitmap blocks = BITMAP_ALLOC (NULL);
 211   basic_block commondom;
 212   unsigned int j;
 213   bitmap_iterator bi;
 214   ssa_op_iter op_iter;
 215   imm_use_iterator imm_iter;
 216   use_operand_p use_p;
 217   tree var;
 218
 219   bitmap_clear (blocks);
 220   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 221     {
 222       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 223         {
 224           gimple usestmt = USE_STMT (use_p);
 225           basic_block useblock;
 226
 227           if (gimple_code (usestmt) == GIMPLE_PHI)
 228             {
 229               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 230
 231               useblock = gimple_phi_arg_edge (usestmt, idx)->src;
 232             }
 233           else if (is_gimple_debug (usestmt))
 234             {
 235               *debug_stmts = true;
 236               continue;
 237             }
 238           else
 239             {
 240               useblock = gimple_bb (usestmt);
 241             }
 242
 243           /* Short circuit. Nothing dominates the entry block.  */
 244           if (useblock == ENTRY_BLOCK_PTR)
 245             {
 246               BITMAP_FREE (blocks);
 247               return NULL;
 248             }
 249           bitmap_set_bit (blocks, useblock->index);
 250         }
 251     }
 252   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 253   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 254     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 255                                           BASIC_BLOCK (j));
 256   BITMAP_FREE (blocks);
 257   return commondom;
 258 }
 259
 260 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 261    determine the location to sink the statement to, if any.
 262    Returns true if there is such location; in that case, TOGSI points to the
 263    statement before that STMT should be moved.  */
 264
 265 static bool
 266 statement_sink_location (gimple stmt, basic_block frombb,
 267                          gimple_stmt_iterator *togsi)
 268 {
 269   gimple use;
 270   tree def;
 271   use_operand_p one_use = NULL_USE_OPERAND_P;
 272   basic_block sinkbb;
 273   use_operand_p use_p;
 274   def_operand_p def_p;
 275   ssa_op_iter iter;
 276   imm_use_iterator imm_iter;
 277
 278   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 279     {
 280       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 281         {
 282           if (is_gimple_debug (USE_STMT (one_use)))
 283             continue;
 284
 285           break;
 286         }
 287       if (one_use != NULL_USE_OPERAND_P)
 288         break;
 289     }
 290
 291   /* Return if there are no immediate uses of this stmt.  */
 292   if (one_use == NULL_USE_OPERAND_P)
 293     return false;
 294
 295   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 296     return false;
 297
 298   /* There are a few classes of things we can't or don't move, some because we
 299      don't have code to handle it, some because it's not profitable and some
 300      because it's not legal.
 301
 302      We can't sink things that may be global stores, at least not without
 303      calculating a lot more information, because we may cause it to no longer
 304      be seen by an external routine that needs it depending on where it gets
 305      moved to.
 306
 307      We don't want to sink loads from memory.
 308
 309      We can't sink statements that end basic blocks without splitting the
 310      incoming edge for the sink location to place it there.
 311
 312      We can't sink statements that have volatile operands.
 313
 314      We don't want to sink dead code, so anything with 0 immediate uses is not
 315      sunk.
 316
 317      Don't sink BLKmode assignments if current function has any local explicit
 318      register variables, as BLKmode assignments may involve memcpy or memset
 319      calls or, on some targets, inline expansion thereof that sometimes need
 320      to use specific hard registers.
 321
 322   */
 323   if (stmt_ends_bb_p (stmt)
 324       || gimple_has_side_effects (stmt)
 325       || is_hidden_global_store (stmt)
 326       || gimple_has_volatile_ops (stmt)
 327       || gimple_vuse (stmt)
 328       || (cfun->has_local_explicit_reg_vars
 329           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 330     return false;
 331
 332   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 333     {
 334       tree def = DEF_FROM_PTR (def_p);
 335       if (is_global_var (SSA_NAME_VAR (def))
 336           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 337         return false;
 338     }
 339
 340   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 341     {
 342       tree use = USE_FROM_PTR (use_p);
 343       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 344         return false;
 345     }
 346
 347   /* If all the immediate uses are not in the same place, find the nearest
 348      common dominator of all the immediate uses.  For PHI nodes, we have to
 349      find the nearest common dominator of all of the predecessor blocks, since
 350      that is where insertion would have to take place.  */
 351   if (!all_immediate_uses_same_place (stmt))
 352     {
 353       bool debug_stmts = false;
 354       basic_block commondom = nearest_common_dominator_of_uses (stmt,
 355                                                                 &debug_stmts);
 356
 357       if (commondom == frombb)
 358         return false;
 359
 360       /* Our common dominator has to be dominated by frombb in order to be a
 361          trivially safe place to put this statement, since it has multiple
 362          uses.  */
 363       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 364         return false;
 365
 366       /* It doesn't make sense to move to a dominator that post-dominates
 367          frombb, because it means we've just moved it into a path that always
 368          executes if frombb executes, instead of reducing the number of
 369          executions .  */
 370       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 371         {
 372           if (dump_file && (dump_flags & TDF_DETAILS))
 373             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 374           return false;
 375         }
 376
 377       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 378         return false;
 379       if (dump_file && (dump_flags & TDF_DETAILS))
 380         {
 381           fprintf (dump_file, "Common dominator of all uses is %d\n",
 382                    commondom->index);
 383         }
 384
 385       *togsi = gsi_after_labels (commondom);
 386
 387       return true;
 388     }
 389
 390   use = USE_STMT (one_use);
 391   if (gimple_code (use) != GIMPLE_PHI)
 392     {
 393       sinkbb = gimple_bb (use);
 394       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 395           || sinkbb->loop_father != frombb->loop_father)
 396         return false;
 397
 398       /* Move the expression to a post dominator can't reduce the number of
 399          executions.  */
 400       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 401         return false;
 402
 403       *togsi = gsi_for_stmt (use);
 404
 405       return true;
 406     }
 407
 408   /* Note that at this point, all uses must be in the same statement, so it
 409      doesn't matter which def op we choose, pick the first one.  */
 410   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 411     break;
 412
 413   sinkbb = find_bb_for_arg (use, def);
 414   if (!sinkbb)
 415     return false;
 416
 417   /* This will happen when you have
 418      a_3 = PHI <a_13, a_26>
 419
 420      a_26 = VDEF <a_3>
 421
 422      If the use is a phi, and is in the same bb as the def,
 423      we can't sink it.  */
 424
 425   if (gimple_bb (use) == frombb)
 426     return false;
 427   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 428       || sinkbb->loop_father != frombb->loop_father)
 429     return false;
 430
 431   /* Move the expression to a post dominator can't reduce the number of
 432      executions.  */
 433   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 434     return false;
 435
 436   *togsi = gsi_after_labels (sinkbb);
 437
 438   return true;
 439 }
 440
 441 /* Perform code sinking on BB */
 442
 443 static void
 444 sink_code_in_bb (basic_block bb)
 445 {
 446   basic_block son;
 447   gimple_stmt_iterator gsi;
 448   edge_iterator ei;
 449   edge e;
 450   bool last = true;
 451
 452   /* If this block doesn't dominate anything, there can't be any place to sink
 453      the statements to.  */
 454   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 455     goto earlyout;
 456
 457   /* We can't move things across abnormal edges, so don't try.  */
 458   FOR_EACH_EDGE (e, ei, bb->succs)
 459     if (e->flags & EDGE_ABNORMAL)
 460       goto earlyout;
 461
 462   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 463     {
 464       gimple stmt = gsi_stmt (gsi);
 465       gimple_stmt_iterator togsi;
 466
 467       if (!statement_sink_location (stmt, bb, &togsi))
 468         {
 469           if (!gsi_end_p (gsi))
 470             gsi_prev (&gsi);
 471           last = false;
 472           continue;
 473         }
 474       if (dump_file)
 475         {
 476           fprintf (dump_file, "Sinking ");
 477           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 478           fprintf (dump_file, " from bb %d to bb %d\n",
 479                    bb->index, (gsi_bb (togsi))->index);
 480         }
 481
 482       /* If this is the end of the basic block, we need to insert at the end
 483          of the basic block.  */
 484       if (gsi_end_p (togsi))
 485         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 486       else
 487         gsi_move_before (&gsi, &togsi);
 488
 489       sink_stats.sunk++;
 490
 491       /* If we've just removed the last statement of the BB, the
 492          gsi_end_p() test below would fail, but gsi_prev() would have
 493          succeeded, and we want it to succeed.  So we keep track of
 494          whether we're at the last statement and pick up the new last
 495          statement.  */
 496       if (last)
 497         {
 498           gsi = gsi_last_bb (bb);
 499           continue;
 500         }
 501
 502       last = false;
 503       if (!gsi_end_p (gsi))
 504         gsi_prev (&gsi);
 505
 506     }
 507  earlyout:
 508   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 509        son;
 510        son = next_dom_son (CDI_POST_DOMINATORS, son))
 511     {
 512       sink_code_in_bb (son);
 513     }
 514 }
 515
 516 /* Perform code sinking.
 517    This moves code down the flowgraph when we know it would be
 518    profitable to do so, or it wouldn't increase the number of
 519    executions of the statement.
 520
 521    IE given
 522
 523    a_1 = b + c;
 524    if (<something>)
 525    {
 526    }
 527    else
 528    {
 529      foo (&b, &c);
 530      a_5 = b + c;
 531    }
 532    a_6 = PHI (a_5, a_1);
 533    USE a_6.
 534
 535    we'll transform this into:
 536
 537    if (<something>)
 538    {
 539       a_1 = b + c;
 540    }
 541    else
 542    {
 543       foo (&b, &c);
 544       a_5 = b + c;
 545    }
 546    a_6 = PHI (a_5, a_1);
 547    USE a_6.
 548
 549    Note that this reduces the number of computations of a = b + c to 1
 550    when we take the else edge, instead of 2.
 551 */
 552 static void
 553 execute_sink_code (void)
 554 {
 555   loop_optimizer_init (LOOPS_NORMAL);
 556
 557   connect_infinite_loops_to_exit ();
 558   memset (&sink_stats, 0, sizeof (sink_stats));
 559   calculate_dominance_info (CDI_DOMINATORS);
 560   calculate_dominance_info (CDI_POST_DOMINATORS);
 561   sink_code_in_bb (EXIT_BLOCK_PTR);
 562   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 563   free_dominance_info (CDI_POST_DOMINATORS);
 564   remove_fake_exit_edges ();
 565   loop_optimizer_finalize ();
 566 }
 567
 568 /* Gate and execute functions for PRE.  */
 569
 570 static unsigned int
 571 do_sink (void)
 572 {
 573   execute_sink_code ();
 574   return 0;
 575 }
 576
 577 static bool
 578 gate_sink (void)
 579 {
 580   return flag_tree_sink != 0;
 581 }
 582
 583 struct gimple_opt_pass pass_sink_code =
 584 {
 585  {
 586   GIMPLE_PASS,
 587   "sink",                               /* name */
 588   gate_sink,                            /* gate */
 589   do_sink,                              /* execute */
 590   NULL,                                 /* sub */
 591   NULL,                                 /* next */
 592   0,                                    /* static_pass_number */
 593   TV_TREE_SINK,                         /* tv_id */
 594   PROP_no_crit_edges | PROP_cfg
 595     | PROP_ssa,                         /* properties_required */
 596   0,                                    /* properties_provided */
 597   0,                                    /* properties_destroyed */
 598   0,                                    /* todo_flags_start */
 599   TODO_update_ssa
 600     | TODO_dump_func
 601     | TODO_ggc_collect
 602     | TODO_verify_ssa                   /* todo_flags_finish */
 603  }
 604 };