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 "tree-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 (tree phi, tree def)
  86 {
  87   int i;
  88   bool foundone = false;
  89   basic_block result = NULL;
  90   for (i = 0; i < 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 = 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 (tree stmt)
 111 {
 112   tree firstuse = NULL_TREE;
 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_TREE)
 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 (tree stmt)
 138 {
 139   /* Check virtual definitions.  If we get here, the only virtual
 140      definitions we should see are those generated by assignment
 141      statements.  */
 142   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 143     {
 144       tree lhs;
 145
 146       gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_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_STMT_OPERAND (stmt, 0);
 174       if (REFERENCE_CLASS_P (lhs))
 175         lhs = get_base_address (lhs);
 176
 177       if (lhs == NULL_TREE)
 178         {
 179           /* If LHS is NULL, it means that we couldn't get the base
 180              address of the reference.  In which case, we should not
 181              move this store.  */
 182           return true;
 183         }
 184       else if (DECL_P (lhs))
 185         {
 186           /* If the store is to a global symbol, we need to keep it.  */
 187           if (is_global_var (lhs))
 188             return true;
 189
 190         }
 191       else if (INDIRECT_REF_P (lhs))
 192         return may_point_to_global_var (TREE_OPERAND (lhs, 0));
 193       else
 194         gcc_unreachable ();
 195     }
 196
 197   return false;
 198 }
 199
 200 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 201
 202 static basic_block
 203 nearest_common_dominator_of_uses (tree stmt)
 204 {
 205   bitmap blocks = BITMAP_ALLOC (NULL);
 206   basic_block commondom;
 207   unsigned int j;
 208   bitmap_iterator bi;
 209   ssa_op_iter op_iter;
 210   imm_use_iterator imm_iter;
 211   use_operand_p use_p;
 212   tree var;
 213
 214   bitmap_clear (blocks);
 215   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 216     {
 217       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 218         {
 219           tree usestmt = USE_STMT (use_p);
 220           basic_block useblock;
 221
 222           if (TREE_CODE (usestmt) == PHI_NODE)
 223             {
 224               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 225
 226               useblock = PHI_ARG_EDGE (usestmt, idx)->src;
 227             }
 228           else
 229             {
 230               useblock = bb_for_stmt (usestmt);
 231             }
 232
 233           /* Short circuit. Nothing dominates the entry block.  */
 234           if (useblock == ENTRY_BLOCK_PTR)
 235             {
 236               BITMAP_FREE (blocks);
 237               return NULL;
 238             }
 239           bitmap_set_bit (blocks, useblock->index);
 240         }
 241     }
 242   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 243   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 244     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 245                                           BASIC_BLOCK (j));
 246   BITMAP_FREE (blocks);
 247   return commondom;
 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, TOBB is set to the
 253    basic block of the location, and TOBSI points to the statement before
 254    that STMT should be moved.  */
 255
 256 static bool
 257 statement_sink_location (tree stmt, basic_block frombb, basic_block *tobb,
 258                          block_stmt_iterator *tobsi)
 259 {
 260   tree use, def;
 261   use_operand_p one_use = NULL_USE_OPERAND_P;
 262   basic_block sinkbb;
 263   use_operand_p use_p;
 264   def_operand_p def_p;
 265   ssa_op_iter iter;
 266   stmt_ann_t ann;
 267   tree rhs;
 268   imm_use_iterator imm_iter;
 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 (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 285     return false;
 286   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 287
 288   /* There are a few classes of things we can't or don't move, some because we
 289      don't have code to handle it, some because it's not profitable and some
 290      because it's not legal.
 291
 292      We can't sink things that may be global stores, at least not without
 293      calculating a lot more information, because we may cause it to no longer
 294      be seen by an external routine that needs it depending on where it gets
 295      moved to.
 296
 297      We don't want to sink loads from memory.
 298
 299      We can't sink statements that end basic blocks without splitting the
 300      incoming edge for the sink location to place it there.
 301
 302      We can't sink statements that have volatile operands.
 303
 304      We don't want to sink dead code, so anything with 0 immediate uses is not
 305      sunk.
 306
 307   */
 308   ann = stmt_ann (stmt);
 309   if (stmt_ends_bb_p (stmt)
 310       || TREE_SIDE_EFFECTS (rhs)
 311       || TREE_CODE (rhs) == EXC_PTR_EXPR
 312       || TREE_CODE (rhs) == FILTER_EXPR
 313       || is_hidden_global_store (stmt)
 314       || ann->has_volatile_ops
 315       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 316     return false;
 317
 318   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 319     {
 320       tree def = DEF_FROM_PTR (def_p);
 321       if (is_global_var (SSA_NAME_VAR (def))
 322           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 323         return false;
 324     }
 325
 326   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 327     {
 328       tree use = USE_FROM_PTR (use_p);
 329       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 330         return false;
 331     }
 332
 333   /* If all the immediate uses are not in the same place, find the nearest
 334      common dominator of all the immediate uses.  For PHI nodes, we have to
 335      find the nearest common dominator of all of the predecessor blocks, since
 336      that is where insertion would have to take place.  */
 337   if (!all_immediate_uses_same_place (stmt))
 338     {
 339       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 340
 341       if (commondom == frombb)
 342         return false;
 343
 344       /* Our common dominator has to be dominated by frombb in order to be a
 345          trivially safe place to put this statement, since it has multiple
 346          uses.  */
 347       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 348         return false;
 349
 350       /* It doesn't make sense to move to a dominator that post-dominates
 351          frombb, because it means we've just moved it into a path that always
 352          executes if frombb executes, instead of reducing the number of
 353          executions .  */
 354       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 355         {
 356           if (dump_file && (dump_flags & TDF_DETAILS))
 357             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 358           return false;
 359         }
 360
 361       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 362         return false;
 363       if (dump_file && (dump_flags & TDF_DETAILS))
 364         {
 365           fprintf (dump_file, "Common dominator of all uses is %d\n",
 366                    commondom->index);
 367         }
 368       *tobb = commondom;
 369       *tobsi = bsi_after_labels (commondom);
 370       return true;
 371     }
 372
 373   use = USE_STMT (one_use);
 374   if (TREE_CODE (use) != PHI_NODE)
 375     {
 376       sinkbb = bb_for_stmt (use);
 377       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 378           || sinkbb->loop_father != frombb->loop_father)
 379         return false;
 380       *tobb = sinkbb;
 381       *tobsi = bsi_for_stmt (use);
 382       return true;
 383     }
 384
 385   /* Note that at this point, all uses must be in the same statement, so it
 386      doesn't matter which def op we choose, pick the first one.  */
 387   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 388     break;
 389
 390   sinkbb = find_bb_for_arg (use, def);
 391   if (!sinkbb)
 392     return false;
 393
 394   /* This will happen when you have
 395      a_3 = PHI <a_13, a_26>
 396
 397      a_26 = VDEF <a_3>
 398
 399      If the use is a phi, and is in the same bb as the def,
 400      we can't sink it.  */
 401
 402   if (bb_for_stmt (use) == frombb)
 403     return false;
 404   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 405       || sinkbb->loop_father != frombb->loop_father)
 406     return false;
 407
 408   *tobb = sinkbb;
 409   *tobsi = bsi_after_labels (sinkbb);
 410
 411   return true;
 412 }
 413
 414 /* Perform code sinking on BB */
 415
 416 static void
 417 sink_code_in_bb (basic_block bb)
 418 {
 419   basic_block son;
 420   block_stmt_iterator bsi;
 421   edge_iterator ei;
 422   edge e;
 423   bool last = true;
 424
 425   /* If this block doesn't dominate anything, there can't be any place to sink
 426      the statements to.  */
 427   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 428     goto earlyout;
 429
 430   /* We can't move things across abnormal edges, so don't try.  */
 431   FOR_EACH_EDGE (e, ei, bb->succs)
 432     if (e->flags & EDGE_ABNORMAL)
 433       goto earlyout;
 434
 435   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 436     {
 437       tree stmt = bsi_stmt (bsi);
 438       block_stmt_iterator tobsi;
 439       basic_block tobb;
 440
 441       if (!statement_sink_location (stmt, bb, &tobb, &tobsi))
 442         {
 443           if (!bsi_end_p (bsi))
 444             bsi_prev (&bsi);
 445           last = false;
 446           continue;
 447         }
 448       if (dump_file)
 449         {
 450           fprintf (dump_file, "Sinking ");
 451           print_generic_expr (dump_file, stmt, TDF_VOPS);
 452           fprintf (dump_file, " from bb %d to bb %d\n",
 453                    bb->index, tobb->index);
 454         }
 455
 456       /* If this is the end of the basic block, we need to insert at the end
 457          of the basic block.  */
 458       if (bsi_end_p (tobsi))
 459         bsi_move_to_bb_end (&bsi, tobb);
 460       else
 461         bsi_move_before (&bsi, &tobsi);
 462
 463       sink_stats.sunk++;
 464
 465       /* If we've just removed the last statement of the BB, the
 466          bsi_end_p() test below would fail, but bsi_prev() would have
 467          succeeded, and we want it to succeed.  So we keep track of
 468          whether we're at the last statement and pick up the new last
 469          statement.  */
 470       if (last)
 471         {
 472           bsi = bsi_last (bb);
 473           continue;
 474         }
 475
 476       last = false;
 477       if (!bsi_end_p (bsi))
 478         bsi_prev (&bsi);
 479
 480     }
 481  earlyout:
 482   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 483        son;
 484        son = next_dom_son (CDI_POST_DOMINATORS, son))
 485     {
 486       sink_code_in_bb (son);
 487     }
 488 }
 489
 490 /* Perform code sinking.
 491    This moves code down the flowgraph when we know it would be
 492    profitable to do so, or it wouldn't increase the number of
 493    executions of the statement.
 494
 495    IE given
 496
 497    a_1 = b + c;
 498    if (<something>)
 499    {
 500    }
 501    else
 502    {
 503      foo (&b, &c);
 504      a_5 = b + c;
 505    }
 506    a_6 = PHI (a_5, a_1);
 507    USE a_6.
 508
 509    we'll transform this into:
 510
 511    if (<something>)
 512    {
 513       a_1 = b + c;
 514    }
 515    else
 516    {
 517       foo (&b, &c);
 518       a_5 = b + c;
 519    }
 520    a_6 = PHI (a_5, a_1);
 521    USE a_6.
 522
 523    Note that this reduces the number of computations of a = b + c to 1
 524    when we take the else edge, instead of 2.
 525 */
 526 static void
 527 execute_sink_code (void)
 528 {
 529   loop_optimizer_init (LOOPS_NORMAL);
 530
 531   connect_infinite_loops_to_exit ();
 532   memset (&sink_stats, 0, sizeof (sink_stats));
 533   calculate_dominance_info (CDI_DOMINATORS);
 534   calculate_dominance_info (CDI_POST_DOMINATORS);
 535   sink_code_in_bb (EXIT_BLOCK_PTR);
 536   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 537   free_dominance_info (CDI_POST_DOMINATORS);
 538   remove_fake_exit_edges ();
 539   loop_optimizer_finalize ();
 540 }
 541
 542 /* Gate and execute functions for PRE.  */
 543
 544 static unsigned int
 545 do_sink (void)
 546 {
 547   execute_sink_code ();
 548   return 0;
 549 }
 550
 551 static bool
 552 gate_sink (void)
 553 {
 554   return flag_tree_sink != 0;
 555 }
 556
 557 struct gimple_opt_pass pass_sink_code =
 558 {
 559  {
 560   GIMPLE_PASS,
 561   "sink",                               /* name */
 562   gate_sink,                            /* gate */
 563   do_sink,                              /* execute */
 564   NULL,                                 /* sub */
 565   NULL,                                 /* next */
 566   0,                                    /* static_pass_number */
 567   TV_TREE_SINK,                         /* tv_id */
 568   PROP_no_crit_edges | PROP_cfg
 569     | PROP_ssa | PROP_alias,            /* properties_required */
 570   0,                                    /* properties_provided */
 571   0,                                    /* properties_destroyed */
 572   0,                                    /* todo_flags_start */
 573   TODO_update_ssa
 574     | TODO_dump_func
 575     | TODO_ggc_collect
 576     | TODO_verify_ssa                   /* todo_flags_finish */
 577  }
 578 };