gcc/tree-ssa-sink.c

   1 /* Code sinking for trees
   2    Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009
   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 "ggc.h"
  27 #include "tree.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "tree-inline.h"
  31 #include "tree-flow.h"
  32 #include "gimple.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "fibheap.h"
  36 #include "hashtab.h"
  37 #include "tree-iterator.h"
  38 #include "real.h"
  39 #include "alloc-pool.h"
  40 #include "tree-pass.h"
  41 #include "flags.h"
  42 #include "bitmap.h"
  43 #include "langhooks.h"
  44 #include "cfgloop.h"
  45
  46 /* TODO:
  47    1. Sinking store only using scalar promotion (IE without moving the RHS):
  48
  49    *q = p;
  50    p = p + 1;
  51    if (something)
  52      *q = <not p>;
  53    else
  54      y = *q;
  55
  56
  57    should become
  58    sinktemp = p;
  59    p = p + 1;
  60    if (something)
  61      *q = <not p>;
  62    else
  63    {
  64      *q = sinktemp;
  65      y = *q
  66    }
  67    Store copy propagation will take care of the store elimination above.
  68
  69
  70    2. Sinking using Partial Dead Code Elimination.  */
  71
  72
  73 static struct
  74 {
  75   /* The number of statements sunk down the flowgraph by code sinking.  */
  76   int sunk;
  77
  78 } sink_stats;
  79
  80
  81 /* Given a PHI, and one of its arguments (DEF), find the edge for
  82    that argument and return it.  If the argument occurs twice in the PHI node,
  83    we return NULL.  */
  84
  85 static basic_block
  86 find_bb_for_arg (gimple phi, tree def)
  87 {
  88   size_t i;
  89   bool foundone = false;
  90   basic_block result = NULL;
  91   for (i = 0; i < gimple_phi_num_args (phi); i++)
  92     if (PHI_ARG_DEF (phi, i) == def)
  93       {
  94         if (foundone)
  95           return NULL;
  96         foundone = true;
  97         result = gimple_phi_arg_edge (phi, i)->src;
  98       }
  99   return result;
 100 }
 101
 102 /* When the first immediate use is in a statement, then return true if all
 103    immediate uses in IMM are in the same statement.
 104    We could also do the case where  the first immediate use is in a phi node,
 105    and all the other uses are in phis in the same basic block, but this
 106    requires some expensive checking later (you have to make sure no def/vdef
 107    in the statement occurs for multiple edges in the various phi nodes it's
 108    used in, so that you only have one place you can sink it to.  */
 109
 110 static bool
 111 all_immediate_uses_same_place (gimple stmt)
 112 {
 113   gimple firstuse = NULL;
 114   ssa_op_iter op_iter;
 115   imm_use_iterator imm_iter;
 116   use_operand_p use_p;
 117   tree var;
 118
 119   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 120     {
 121       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 122         {
 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)
 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
 231             {
 232               useblock = gimple_bb (usestmt);
 233             }
 234
 235           /* Short circuit. Nothing dominates the entry block.  */
 236           if (useblock == ENTRY_BLOCK_PTR)
 237             {
 238               BITMAP_FREE (blocks);
 239               return NULL;
 240             }
 241           bitmap_set_bit (blocks, useblock->index);
 242         }
 243     }
 244   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 245   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 246     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 247                                           BASIC_BLOCK (j));
 248   BITMAP_FREE (blocks);
 249   return commondom;
 250 }
 251
 252 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 253    determine the location to sink the statement to, if any.
 254    Returns true if there is such location; in that case, TOGSI points to the
 255    statement before that STMT should be moved.  */
 256
 257 static bool
 258 statement_sink_location (gimple stmt, basic_block frombb,
 259                          gimple_stmt_iterator *togsi)
 260 {
 261   gimple use;
 262   tree def;
 263   use_operand_p one_use = NULL_USE_OPERAND_P;
 264   basic_block sinkbb;
 265   use_operand_p use_p;
 266   def_operand_p def_p;
 267   ssa_op_iter iter;
 268   imm_use_iterator imm_iter;
 269   enum tree_code code;
 270
 271   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 272     {
 273       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 274         {
 275           break;
 276         }
 277       if (one_use != NULL_USE_OPERAND_P)
 278         break;
 279     }
 280
 281   /* Return if there are no immediate uses of this stmt.  */
 282   if (one_use == NULL_USE_OPERAND_P)
 283     return false;
 284
 285   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 286     return false;
 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      Don't sink BLKmode assignments if current function has any local explicit
 308      register variables, as BLKmode assignments may involve memcpy or memset
 309      calls or, on some targets, inline expansion thereof that sometimes need
 310      to use specific hard registers.
 311
 312   */
 313   code = gimple_assign_rhs_code (stmt);
 314   if (stmt_ends_bb_p (stmt)
 315       || gimple_has_side_effects (stmt)
 316       || code == EXC_PTR_EXPR
 317       || code == FILTER_EXPR
 318       || is_hidden_global_store (stmt)
 319       || gimple_has_volatile_ops (stmt)
 320       || gimple_vuse (stmt)
 321       || (cfun->has_local_explicit_reg_vars
 322           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 323     return false;
 324
 325   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 326     {
 327       tree def = DEF_FROM_PTR (def_p);
 328       if (is_global_var (SSA_NAME_VAR (def))
 329           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 330         return false;
 331     }
 332
 333   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 334     {
 335       tree use = USE_FROM_PTR (use_p);
 336       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 337         return false;
 338     }
 339
 340   /* If all the immediate uses are not in the same place, find the nearest
 341      common dominator of all the immediate uses.  For PHI nodes, we have to
 342      find the nearest common dominator of all of the predecessor blocks, since
 343      that is where insertion would have to take place.  */
 344   if (!all_immediate_uses_same_place (stmt))
 345     {
 346       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 347
 348       if (commondom == frombb)
 349         return false;
 350
 351       /* Our common dominator has to be dominated by frombb in order to be a
 352          trivially safe place to put this statement, since it has multiple
 353          uses.  */
 354       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 355         return false;
 356
 357       /* It doesn't make sense to move to a dominator that post-dominates
 358          frombb, because it means we've just moved it into a path that always
 359          executes if frombb executes, instead of reducing the number of
 360          executions .  */
 361       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 362         {
 363           if (dump_file && (dump_flags & TDF_DETAILS))
 364             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 365           return false;
 366         }
 367
 368       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 369         return false;
 370       if (dump_file && (dump_flags & TDF_DETAILS))
 371         {
 372           fprintf (dump_file, "Common dominator of all uses is %d\n",
 373                    commondom->index);
 374         }
 375       *togsi = gsi_after_labels (commondom);
 376       return true;
 377     }
 378
 379   use = USE_STMT (one_use);
 380   if (gimple_code (use) != GIMPLE_PHI)
 381     {
 382       sinkbb = gimple_bb (use);
 383       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 384           || sinkbb->loop_father != frombb->loop_father)
 385         return false;
 386
 387       /* Move the expression to a post dominator can't reduce the number of
 388          executions.  */
 389       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 390         return false;
 391
 392       *togsi = gsi_for_stmt (use);
 393       return true;
 394     }
 395
 396   /* Note that at this point, all uses must be in the same statement, so it
 397      doesn't matter which def op we choose, pick the first one.  */
 398   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 399     break;
 400
 401   sinkbb = find_bb_for_arg (use, def);
 402   if (!sinkbb)
 403     return false;
 404
 405   /* This will happen when you have
 406      a_3 = PHI <a_13, a_26>
 407
 408      a_26 = VDEF <a_3>
 409
 410      If the use is a phi, and is in the same bb as the def,
 411      we can't sink it.  */
 412
 413   if (gimple_bb (use) == frombb)
 414     return false;
 415   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 416       || sinkbb->loop_father != frombb->loop_father)
 417     return false;
 418
 419   /* Move the expression to a post dominator can't reduce the number of
 420      executions.  */
 421   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 422     return false;
 423
 424   *togsi = gsi_after_labels (sinkbb);
 425
 426   return true;
 427 }
 428
 429 /* Perform code sinking on BB */
 430
 431 static void
 432 sink_code_in_bb (basic_block bb)
 433 {
 434   basic_block son;
 435   gimple_stmt_iterator gsi;
 436   edge_iterator ei;
 437   edge e;
 438   bool last = true;
 439
 440   /* If this block doesn't dominate anything, there can't be any place to sink
 441      the statements to.  */
 442   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 443     goto earlyout;
 444
 445   /* We can't move things across abnormal edges, so don't try.  */
 446   FOR_EACH_EDGE (e, ei, bb->succs)
 447     if (e->flags & EDGE_ABNORMAL)
 448       goto earlyout;
 449
 450   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 451     {
 452       gimple stmt = gsi_stmt (gsi);
 453       gimple_stmt_iterator togsi;
 454
 455       if (!statement_sink_location (stmt, bb, &togsi))
 456         {
 457           if (!gsi_end_p (gsi))
 458             gsi_prev (&gsi);
 459           last = false;
 460           continue;
 461         }
 462       if (dump_file)
 463         {
 464           fprintf (dump_file, "Sinking ");
 465           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 466           fprintf (dump_file, " from bb %d to bb %d\n",
 467                    bb->index, (gsi_bb (togsi))->index);
 468         }
 469
 470       /* If this is the end of the basic block, we need to insert at the end
 471          of the basic block.  */
 472       if (gsi_end_p (togsi))
 473         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 474       else
 475         gsi_move_before (&gsi, &togsi);
 476
 477       sink_stats.sunk++;
 478
 479       /* If we've just removed the last statement of the BB, the
 480          gsi_end_p() test below would fail, but gsi_prev() would have
 481          succeeded, and we want it to succeed.  So we keep track of
 482          whether we're at the last statement and pick up the new last
 483          statement.  */
 484       if (last)
 485         {
 486           gsi = gsi_last_bb (bb);
 487           continue;
 488         }
 489
 490       last = false;
 491       if (!gsi_end_p (gsi))
 492         gsi_prev (&gsi);
 493
 494     }
 495  earlyout:
 496   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 497        son;
 498        son = next_dom_son (CDI_POST_DOMINATORS, son))
 499     {
 500       sink_code_in_bb (son);
 501     }
 502 }
 503
 504 /* Perform code sinking.
 505    This moves code down the flowgraph when we know it would be
 506    profitable to do so, or it wouldn't increase the number of
 507    executions of the statement.
 508
 509    IE given
 510
 511    a_1 = b + c;
 512    if (<something>)
 513    {
 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    we'll transform this into:
 524
 525    if (<something>)
 526    {
 527       a_1 = b + c;
 528    }
 529    else
 530    {
 531       foo (&b, &c);
 532       a_5 = b + c;
 533    }
 534    a_6 = PHI (a_5, a_1);
 535    USE a_6.
 536
 537    Note that this reduces the number of computations of a = b + c to 1
 538    when we take the else edge, instead of 2.
 539 */
 540 static void
 541 execute_sink_code (void)
 542 {
 543   loop_optimizer_init (LOOPS_NORMAL);
 544
 545   connect_infinite_loops_to_exit ();
 546   memset (&sink_stats, 0, sizeof (sink_stats));
 547   calculate_dominance_info (CDI_DOMINATORS);
 548   calculate_dominance_info (CDI_POST_DOMINATORS);
 549   sink_code_in_bb (EXIT_BLOCK_PTR);
 550   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 551   free_dominance_info (CDI_POST_DOMINATORS);
 552   remove_fake_exit_edges ();
 553   loop_optimizer_finalize ();
 554 }
 555
 556 /* Gate and execute functions for PRE.  */
 557
 558 static unsigned int
 559 do_sink (void)
 560 {
 561   execute_sink_code ();
 562   return 0;
 563 }
 564
 565 static bool
 566 gate_sink (void)
 567 {
 568   return flag_tree_sink != 0;
 569 }
 570
 571 struct gimple_opt_pass pass_sink_code =
 572 {
 573  {
 574   GIMPLE_PASS,
 575   "sink",                               /* name */
 576   gate_sink,                            /* gate */
 577   do_sink,                              /* execute */
 578   NULL,                                 /* sub */
 579   NULL,                                 /* next */
 580   0,                                    /* static_pass_number */
 581   TV_TREE_SINK,                         /* tv_id */
 582   PROP_no_crit_edges | PROP_cfg
 583     | PROP_ssa,                         /* properties_required */
 584   0,                                    /* properties_provided */
 585   0,                                    /* properties_destroyed */
 586   0,                                    /* todo_flags_start */
 587   TODO_update_ssa
 588     | TODO_dump_func
 589     | TODO_ggc_collect
 590     | TODO_verify_ssa                   /* todo_flags_finish */
 591  }
 592 };