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
 277   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 278     {
 279       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 280         {
 281           if (is_gimple_debug (USE_STMT (one_use)))
 282             continue;
 283
 284           break;
 285         }
 286       if (one_use != NULL_USE_OPERAND_P)
 287         break;
 288     }
 289
 290   /* Return if there are no immediate uses of this stmt.  */
 291   if (one_use == NULL_USE_OPERAND_P)
 292     return false;
 293
 294   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 295     return false;
 296
 297   /* There are a few classes of things we can't or don't move, some because we
 298      don't have code to handle it, some because it's not profitable and some
 299      because it's not legal.
 300
 301      We can't sink things that may be global stores, at least not without
 302      calculating a lot more information, because we may cause it to no longer
 303      be seen by an external routine that needs it depending on where it gets
 304      moved to.
 305
 306      We don't want to sink loads from memory.
 307
 308      We can't sink statements that end basic blocks without splitting the
 309      incoming edge for the sink location to place it there.
 310
 311      We can't sink statements that have volatile operands.
 312
 313      We don't want to sink dead code, so anything with 0 immediate uses is not
 314      sunk.
 315
 316      Don't sink BLKmode assignments if current function has any local explicit
 317      register variables, as BLKmode assignments may involve memcpy or memset
 318      calls or, on some targets, inline expansion thereof that sometimes need
 319      to use specific hard registers.
 320
 321   */
 322   if (stmt_ends_bb_p (stmt)
 323       || gimple_has_side_effects (stmt)
 324       || is_hidden_global_store (stmt)
 325       || gimple_has_volatile_ops (stmt)
 326       || gimple_vuse (stmt)
 327       || (cfun->has_local_explicit_reg_vars
 328           && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode))
 329     return false;
 330
 331   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 332     {
 333       tree def = DEF_FROM_PTR (def_p);
 334       if (is_global_var (SSA_NAME_VAR (def))
 335           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 336         return false;
 337     }
 338
 339   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 340     {
 341       tree use = USE_FROM_PTR (use_p);
 342       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 343         return false;
 344     }
 345
 346   /* If all the immediate uses are not in the same place, find the nearest
 347      common dominator of all the immediate uses.  For PHI nodes, we have to
 348      find the nearest common dominator of all of the predecessor blocks, since
 349      that is where insertion would have to take place.  */
 350   if (!all_immediate_uses_same_place (stmt))
 351     {
 352       bool debug_stmts = false;
 353       basic_block commondom = nearest_common_dominator_of_uses (stmt,
 354                                                                 &debug_stmts);
 355
 356       if (commondom == frombb)
 357         return false;
 358
 359       /* Our common dominator has to be dominated by frombb in order to be a
 360          trivially safe place to put this statement, since it has multiple
 361          uses.  */
 362       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 363         return false;
 364
 365       /* It doesn't make sense to move to a dominator that post-dominates
 366          frombb, because it means we've just moved it into a path that always
 367          executes if frombb executes, instead of reducing the number of
 368          executions .  */
 369       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 370         {
 371           if (dump_file && (dump_flags & TDF_DETAILS))
 372             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 373           return false;
 374         }
 375
 376       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 377         return false;
 378       if (dump_file && (dump_flags & TDF_DETAILS))
 379         {
 380           fprintf (dump_file, "Common dominator of all uses is %d\n",
 381                    commondom->index);
 382         }
 383
 384       *togsi = gsi_after_labels (commondom);
 385
 386       return true;
 387     }
 388
 389   use = USE_STMT (one_use);
 390   if (gimple_code (use) != GIMPLE_PHI)
 391     {
 392       sinkbb = gimple_bb (use);
 393       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 394           || sinkbb->loop_father != frombb->loop_father)
 395         return false;
 396
 397       /* Move the expression to a post dominator can't reduce the number of
 398          executions.  */
 399       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 400         return false;
 401
 402       *togsi = gsi_for_stmt (use);
 403
 404       return true;
 405     }
 406
 407   /* Note that at this point, all uses must be in the same statement, so it
 408      doesn't matter which def op we choose, pick the first one.  */
 409   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 410     break;
 411
 412   sinkbb = find_bb_for_arg (use, def);
 413   if (!sinkbb)
 414     return false;
 415
 416   /* This will happen when you have
 417      a_3 = PHI <a_13, a_26>
 418
 419      a_26 = VDEF <a_3>
 420
 421      If the use is a phi, and is in the same bb as the def,
 422      we can't sink it.  */
 423
 424   if (gimple_bb (use) == frombb)
 425     return false;
 426   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 427       || sinkbb->loop_father != frombb->loop_father)
 428     return false;
 429
 430   /* Move the expression to a post dominator can't reduce the number of
 431      executions.  */
 432   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 433     return false;
 434
 435   *togsi = gsi_after_labels (sinkbb);
 436
 437   return true;
 438 }
 439
 440 /* Perform code sinking on BB */
 441
 442 static void
 443 sink_code_in_bb (basic_block bb)
 444 {
 445   basic_block son;
 446   gimple_stmt_iterator gsi;
 447   edge_iterator ei;
 448   edge e;
 449   bool last = true;
 450
 451   /* If this block doesn't dominate anything, there can't be any place to sink
 452      the statements to.  */
 453   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 454     goto earlyout;
 455
 456   /* We can't move things across abnormal edges, so don't try.  */
 457   FOR_EACH_EDGE (e, ei, bb->succs)
 458     if (e->flags & EDGE_ABNORMAL)
 459       goto earlyout;
 460
 461   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 462     {
 463       gimple stmt = gsi_stmt (gsi);
 464       gimple_stmt_iterator togsi;
 465
 466       if (!statement_sink_location (stmt, bb, &togsi))
 467         {
 468           if (!gsi_end_p (gsi))
 469             gsi_prev (&gsi);
 470           last = false;
 471           continue;
 472         }
 473       if (dump_file)
 474         {
 475           fprintf (dump_file, "Sinking ");
 476           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 477           fprintf (dump_file, " from bb %d to bb %d\n",
 478                    bb->index, (gsi_bb (togsi))->index);
 479         }
 480
 481       /* If this is the end of the basic block, we need to insert at the end
 482          of the basic block.  */
 483       if (gsi_end_p (togsi))
 484         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 485       else
 486         gsi_move_before (&gsi, &togsi);
 487
 488       sink_stats.sunk++;
 489
 490       /* If we've just removed the last statement of the BB, the
 491          gsi_end_p() test below would fail, but gsi_prev() would have
 492          succeeded, and we want it to succeed.  So we keep track of
 493          whether we're at the last statement and pick up the new last
 494          statement.  */
 495       if (last)
 496         {
 497           gsi = gsi_last_bb (bb);
 498           continue;
 499         }
 500
 501       last = false;
 502       if (!gsi_end_p (gsi))
 503         gsi_prev (&gsi);
 504
 505     }
 506  earlyout:
 507   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 508        son;
 509        son = next_dom_son (CDI_POST_DOMINATORS, son))
 510     {
 511       sink_code_in_bb (son);
 512     }
 513 }
 514
 515 /* Perform code sinking.
 516    This moves code down the flowgraph when we know it would be
 517    profitable to do so, or it wouldn't increase the number of
 518    executions of the statement.
 519
 520    IE given
 521
 522    a_1 = b + c;
 523    if (<something>)
 524    {
 525    }
 526    else
 527    {
 528      foo (&b, &c);
 529      a_5 = b + c;
 530    }
 531    a_6 = PHI (a_5, a_1);
 532    USE a_6.
 533
 534    we'll transform this into:
 535
 536    if (<something>)
 537    {
 538       a_1 = b + c;
 539    }
 540    else
 541    {
 542       foo (&b, &c);
 543       a_5 = b + c;
 544    }
 545    a_6 = PHI (a_5, a_1);
 546    USE a_6.
 547
 548    Note that this reduces the number of computations of a = b + c to 1
 549    when we take the else edge, instead of 2.
 550 */
 551 static void
 552 execute_sink_code (void)
 553 {
 554   loop_optimizer_init (LOOPS_NORMAL);
 555
 556   connect_infinite_loops_to_exit ();
 557   memset (&sink_stats, 0, sizeof (sink_stats));
 558   calculate_dominance_info (CDI_DOMINATORS);
 559   calculate_dominance_info (CDI_POST_DOMINATORS);
 560   sink_code_in_bb (EXIT_BLOCK_PTR);
 561   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 562   free_dominance_info (CDI_POST_DOMINATORS);
 563   remove_fake_exit_edges ();
 564   loop_optimizer_finalize ();
 565 }
 566
 567 /* Gate and execute functions for PRE.  */
 568
 569 static unsigned int
 570 do_sink (void)
 571 {
 572   execute_sink_code ();
 573   return 0;
 574 }
 575
 576 static bool
 577 gate_sink (void)
 578 {
 579   return flag_tree_sink != 0;
 580 }
 581
 582 struct gimple_opt_pass pass_sink_code =
 583 {
 584  {
 585   GIMPLE_PASS,
 586   "sink",                               /* name */
 587   gate_sink,                            /* gate */
 588   do_sink,                              /* execute */
 589   NULL,                                 /* sub */
 590   NULL,                                 /* next */
 591   0,                                    /* static_pass_number */
 592   TV_TREE_SINK,                         /* tv_id */
 593   PROP_no_crit_edges | PROP_cfg
 594     | PROP_ssa,                         /* properties_required */
 595   0,                                    /* properties_provided */
 596   0,                                    /* properties_destroyed */
 597   0,                                    /* todo_flags_start */
 598   TODO_update_ssa
 599     | TODO_dump_func
 600     | TODO_ggc_collect
 601     | TODO_verify_ssa                   /* todo_flags_finish */
 602  }
 603 };