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 (is_gimple_debug (USE_STMT (use_p)))
 124             continue;
 125           if (firstuse == NULL)
 126             firstuse = USE_STMT (use_p);
 127           else
 128             if (firstuse != USE_STMT (use_p))
 129               return false;
 130         }
 131     }
 132
 133   return true;
 134 }
 135
 136 /* Some global stores don't necessarily have VDEF's of global variables,
 137    but we still must avoid moving them around.  */
 138
 139 bool
 140 is_hidden_global_store (gimple stmt)
 141 {
 142   /* Check virtual definitions.  If we get here, the only virtual
 143      definitions we should see are those generated by assignment or call
 144      statements.  */
 145   if (gimple_vdef (stmt))
 146     {
 147       tree lhs;
 148
 149       gcc_assert (is_gimple_assign (stmt) || is_gimple_call (stmt));
 150
 151       /* Note that we must not check the individual virtual operands
 152          here.  In particular, if this is an aliased store, we could
 153          end up with something like the following (SSA notation
 154          redacted for brevity):
 155
 156                 foo (int *p, int i)
 157                 {
 158                   int x;
 159                   p_1 = (i_2 > 3) ? &x : p;
 160
 161                   # x_4 = VDEF <x_3>
 162                   *p_1 = 5;
 163
 164                   return 2;
 165                 }
 166
 167          Notice that the store to '*p_1' should be preserved, if we
 168          were to check the virtual definitions in that store, we would
 169          not mark it needed.  This is because 'x' is not a global
 170          variable.
 171
 172          Therefore, we check the base address of the LHS.  If the
 173          address is a pointer, we check if its name tag or symbol tag is
 174          a global variable.  Otherwise, we check if the base variable
 175          is a global.  */
 176       lhs = gimple_get_lhs (stmt);
 177
 178       if (REFERENCE_CLASS_P (lhs))
 179         lhs = get_base_address (lhs);
 180
 181       if (lhs == NULL_TREE)
 182         {
 183           /* If LHS is NULL, it means that we couldn't get the base
 184              address of the reference.  In which case, we should not
 185              move this store.  */
 186           return true;
 187         }
 188       else if (DECL_P (lhs))
 189         {
 190           /* If the store is to a global symbol, we need to keep it.  */
 191           if (is_global_var (lhs))
 192             return true;
 193
 194         }
 195       else if (INDIRECT_REF_P (lhs))
 196         return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0));
 197       else
 198         gcc_unreachable ();
 199     }
 200
 201   return false;
 202 }
 203
 204 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 205
 206 static basic_block
 207 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
 208 {
 209   bitmap blocks = BITMAP_ALLOC (NULL);
 210   basic_block commondom;
 211   unsigned int j;
 212   bitmap_iterator bi;
 213   ssa_op_iter op_iter;
 214   imm_use_iterator imm_iter;
 215   use_operand_p use_p;
 216   tree var;
 217
 218   bitmap_clear (blocks);
 219   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 220     {
 221       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 222         {
 223           gimple usestmt = USE_STMT (use_p);
 224           basic_block useblock;
 225
 226           if (gimple_code (usestmt) == GIMPLE_PHI)
 227             {
 228               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 229
 230               useblock = gimple_phi_arg_edge (usestmt, idx)->src;
 231             }
 232           else if (is_gimple_debug (usestmt))
 233             {
 234               *debug_stmts = true;
 235               continue;
 236             }
 237           else
 238             {
 239               useblock = gimple_bb (usestmt);
 240             }
 241
 242           /* Short circuit. Nothing dominates the entry block.  */
 243           if (useblock == ENTRY_BLOCK_PTR)
 244             {
 245               BITMAP_FREE (blocks);
 246               return NULL;
 247             }
 248           bitmap_set_bit (blocks, useblock->index);
 249         }
 250     }
 251   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 252   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 253     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 254                                           BASIC_BLOCK (j));
 255   BITMAP_FREE (blocks);
 256   return commondom;
 257 }
 258
 259 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 260    determine the location to sink the statement to, if any.
 261    Returns true if there is such location; in that case, TOGSI points to the
 262    statement before that STMT should be moved.  */
 263
 264 static bool
 265 statement_sink_location (gimple stmt, basic_block frombb,
 266                          gimple_stmt_iterator *togsi)
 267 {
 268   gimple use;
 269   tree def;
 270   use_operand_p one_use = NULL_USE_OPERAND_P;
 271   basic_block sinkbb;
 272   use_operand_p use_p;
 273   def_operand_p def_p;
 274   ssa_op_iter iter;
 275   imm_use_iterator imm_iter;
 276   enum tree_code code;
 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   code = gimple_assign_rhs_code (stmt);
 324   if (stmt_ends_bb_p (stmt)
 325       || gimple_has_side_effects (stmt)
 326       || is_hidden_global_store (stmt)
 327       || gimple_has_volatile_ops (stmt)
 328       || gimple_vuse (stmt)
 329       || (cfun->has_local_explicit_reg_vars
 330           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 331     return false;
 332
 333   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 334     {
 335       tree def = DEF_FROM_PTR (def_p);
 336       if (is_global_var (SSA_NAME_VAR (def))
 337           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 338         return false;
 339     }
 340
 341   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 342     {
 343       tree use = USE_FROM_PTR (use_p);
 344       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 345         return false;
 346     }
 347
 348   /* If all the immediate uses are not in the same place, find the nearest
 349      common dominator of all the immediate uses.  For PHI nodes, we have to
 350      find the nearest common dominator of all of the predecessor blocks, since
 351      that is where insertion would have to take place.  */
 352   if (!all_immediate_uses_same_place (stmt))
 353     {
 354       bool debug_stmts = false;
 355       basic_block commondom = nearest_common_dominator_of_uses (stmt,
 356                                                                 &debug_stmts);
 357
 358       if (commondom == frombb)
 359         return false;
 360
 361       /* Our common dominator has to be dominated by frombb in order to be a
 362          trivially safe place to put this statement, since it has multiple
 363          uses.  */
 364       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 365         return false;
 366
 367       /* It doesn't make sense to move to a dominator that post-dominates
 368          frombb, because it means we've just moved it into a path that always
 369          executes if frombb executes, instead of reducing the number of
 370          executions .  */
 371       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 372         {
 373           if (dump_file && (dump_flags & TDF_DETAILS))
 374             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 375           return false;
 376         }
 377
 378       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 379         return false;
 380       if (dump_file && (dump_flags & TDF_DETAILS))
 381         {
 382           fprintf (dump_file, "Common dominator of all uses is %d\n",
 383                    commondom->index);
 384         }
 385
 386       *togsi = gsi_after_labels (commondom);
 387
 388       if (debug_stmts)
 389         propagate_defs_into_debug_stmts (stmt, commondom, togsi);
 390
 391       return true;
 392     }
 393
 394   use = USE_STMT (one_use);
 395   if (gimple_code (use) != GIMPLE_PHI)
 396     {
 397       sinkbb = gimple_bb (use);
 398       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 399           || sinkbb->loop_father != frombb->loop_father)
 400         return false;
 401
 402       /* Move the expression to a post dominator can't reduce the number of
 403          executions.  */
 404       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 405         return false;
 406
 407       *togsi = gsi_for_stmt (use);
 408
 409       propagate_defs_into_debug_stmts (stmt, sinkbb, togsi);
 410
 411       return true;
 412     }
 413
 414   /* Note that at this point, all uses must be in the same statement, so it
 415      doesn't matter which def op we choose, pick the first one.  */
 416   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 417     break;
 418
 419   sinkbb = find_bb_for_arg (use, def);
 420   if (!sinkbb)
 421     return false;
 422
 423   /* This will happen when you have
 424      a_3 = PHI <a_13, a_26>
 425
 426      a_26 = VDEF <a_3>
 427
 428      If the use is a phi, and is in the same bb as the def,
 429      we can't sink it.  */
 430
 431   if (gimple_bb (use) == frombb)
 432     return false;
 433   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 434       || sinkbb->loop_father != frombb->loop_father)
 435     return false;
 436
 437   /* Move the expression to a post dominator can't reduce the number of
 438      executions.  */
 439   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 440     return false;
 441
 442   *togsi = gsi_after_labels (sinkbb);
 443
 444   propagate_defs_into_debug_stmts (stmt, sinkbb, togsi);
 445
 446   return true;
 447 }
 448
 449 /* Perform code sinking on BB */
 450
 451 static void
 452 sink_code_in_bb (basic_block bb)
 453 {
 454   basic_block son;
 455   gimple_stmt_iterator gsi;
 456   edge_iterator ei;
 457   edge e;
 458   bool last = true;
 459
 460   /* If this block doesn't dominate anything, there can't be any place to sink
 461      the statements to.  */
 462   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 463     goto earlyout;
 464
 465   /* We can't move things across abnormal edges, so don't try.  */
 466   FOR_EACH_EDGE (e, ei, bb->succs)
 467     if (e->flags & EDGE_ABNORMAL)
 468       goto earlyout;
 469
 470   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 471     {
 472       gimple stmt = gsi_stmt (gsi);
 473       gimple_stmt_iterator togsi;
 474
 475       if (!statement_sink_location (stmt, bb, &togsi))
 476         {
 477           if (!gsi_end_p (gsi))
 478             gsi_prev (&gsi);
 479           last = false;
 480           continue;
 481         }
 482       if (dump_file)
 483         {
 484           fprintf (dump_file, "Sinking ");
 485           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 486           fprintf (dump_file, " from bb %d to bb %d\n",
 487                    bb->index, (gsi_bb (togsi))->index);
 488         }
 489
 490       /* If this is the end of the basic block, we need to insert at the end
 491          of the basic block.  */
 492       if (gsi_end_p (togsi))
 493         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 494       else
 495         gsi_move_before (&gsi, &togsi);
 496
 497       sink_stats.sunk++;
 498
 499       /* If we've just removed the last statement of the BB, the
 500          gsi_end_p() test below would fail, but gsi_prev() would have
 501          succeeded, and we want it to succeed.  So we keep track of
 502          whether we're at the last statement and pick up the new last
 503          statement.  */
 504       if (last)
 505         {
 506           gsi = gsi_last_bb (bb);
 507           continue;
 508         }
 509
 510       last = false;
 511       if (!gsi_end_p (gsi))
 512         gsi_prev (&gsi);
 513
 514     }
 515  earlyout:
 516   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 517        son;
 518        son = next_dom_son (CDI_POST_DOMINATORS, son))
 519     {
 520       sink_code_in_bb (son);
 521     }
 522 }
 523
 524 /* Perform code sinking.
 525    This moves code down the flowgraph when we know it would be
 526    profitable to do so, or it wouldn't increase the number of
 527    executions of the statement.
 528
 529    IE given
 530
 531    a_1 = b + c;
 532    if (<something>)
 533    {
 534    }
 535    else
 536    {
 537      foo (&b, &c);
 538      a_5 = b + c;
 539    }
 540    a_6 = PHI (a_5, a_1);
 541    USE a_6.
 542
 543    we'll transform this into:
 544
 545    if (<something>)
 546    {
 547       a_1 = b + c;
 548    }
 549    else
 550    {
 551       foo (&b, &c);
 552       a_5 = b + c;
 553    }
 554    a_6 = PHI (a_5, a_1);
 555    USE a_6.
 556
 557    Note that this reduces the number of computations of a = b + c to 1
 558    when we take the else edge, instead of 2.
 559 */
 560 static void
 561 execute_sink_code (void)
 562 {
 563   loop_optimizer_init (LOOPS_NORMAL);
 564
 565   connect_infinite_loops_to_exit ();
 566   memset (&sink_stats, 0, sizeof (sink_stats));
 567   calculate_dominance_info (CDI_DOMINATORS);
 568   calculate_dominance_info (CDI_POST_DOMINATORS);
 569   sink_code_in_bb (EXIT_BLOCK_PTR);
 570   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 571   free_dominance_info (CDI_POST_DOMINATORS);
 572   remove_fake_exit_edges ();
 573   loop_optimizer_finalize ();
 574 }
 575
 576 /* Gate and execute functions for PRE.  */
 577
 578 static unsigned int
 579 do_sink (void)
 580 {
 581   execute_sink_code ();
 582   return 0;
 583 }
 584
 585 static bool
 586 gate_sink (void)
 587 {
 588   return flag_tree_sink != 0;
 589 }
 590
 591 struct gimple_opt_pass pass_sink_code =
 592 {
 593  {
 594   GIMPLE_PASS,
 595   "sink",                               /* name */
 596   gate_sink,                            /* gate */
 597   do_sink,                              /* execute */
 598   NULL,                                 /* sub */
 599   NULL,                                 /* next */
 600   0,                                    /* static_pass_number */
 601   TV_TREE_SINK,                         /* tv_id */
 602   PROP_no_crit_edges | PROP_cfg
 603     | PROP_ssa,                         /* properties_required */
 604   0,                                    /* properties_provided */
 605   0,                                    /* properties_destroyed */
 606   0,                                    /* todo_flags_start */
 607   TODO_update_ssa
 608     | TODO_dump_func
 609     | TODO_ggc_collect
 610     | TODO_verify_ssa                   /* todo_flags_finish */
 611  }
 612 };