gcc/tree-ssa-sink.c

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