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