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 "gimple-pretty-print.h"
  29 #include "tree-inline.h"
  30 #include "tree-flow.h"
  31 #include "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 "alloc-pool.h"
  38 #include "tree-pass.h"
  39 #include "flags.h"
  40 #include "bitmap.h"
  41 #include "langhooks.h"
  42 #include "cfgloop.h"
  43
  44 /* TODO:
  45    1. Sinking store only using scalar promotion (IE without moving the RHS):
  46
  47    *q = p;
  48    p = p + 1;
  49    if (something)
  50      *q = <not p>;
  51    else
  52      y = *q;
  53
  54
  55    should become
  56    sinktemp = p;
  57    p = p + 1;
  58    if (something)
  59      *q = <not p>;
  60    else
  61    {
  62      *q = sinktemp;
  63      y = *q
  64    }
  65    Store copy propagation will take care of the store elimination above.
  66
  67
  68    2. Sinking using Partial Dead Code Elimination.  */
  69
  70
  71 static struct
  72 {
  73   /* The number of statements sunk down the flowgraph by code sinking.  */
  74   int sunk;
  75
  76 } sink_stats;
  77
  78
  79 /* Given a PHI, and one of its arguments (DEF), find the edge for
  80    that argument and return it.  If the argument occurs twice in the PHI node,
  81    we return NULL.  */
  82
  83 static basic_block
  84 find_bb_for_arg (gimple phi, tree def)
  85 {
  86   size_t i;
  87   bool foundone = false;
  88   basic_block result = NULL;
  89   for (i = 0; i < gimple_phi_num_args (phi); i++)
  90     if (PHI_ARG_DEF (phi, i) == def)
  91       {
  92         if (foundone)
  93           return NULL;
  94         foundone = true;
  95         result = gimple_phi_arg_edge (phi, i)->src;
  96       }
  97   return result;
  98 }
  99
 100 /* When the first immediate use is in a statement, then return true if all
 101    immediate uses in IMM are in the same statement.
 102    We could also do the case where  the first immediate use is in a phi node,
 103    and all the other uses are in phis in the same basic block, but this
 104    requires some expensive checking later (you have to make sure no def/vdef
 105    in the statement occurs for multiple edges in the various phi nodes it's
 106    used in, so that you only have one place you can sink it to.  */
 107
 108 static bool
 109 all_immediate_uses_same_place (gimple stmt)
 110 {
 111   gimple firstuse = NULL;
 112   ssa_op_iter op_iter;
 113   imm_use_iterator imm_iter;
 114   use_operand_p use_p;
 115   tree var;
 116
 117   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 118     {
 119       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 120         {
 121           if (is_gimple_debug (USE_STMT (use_p)))
 122             continue;
 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                || TREE_CODE (lhs) == MEM_REF
 195                || TREE_CODE (lhs) == TARGET_MEM_REF)
 196         return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0));
 197       else if (CONSTANT_CLASS_P (lhs))
 198         return true;
 199       else
 200         gcc_unreachable ();
 201     }
 202
 203   return false;
 204 }
 205
 206 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 207
 208 static basic_block
 209 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts)
 210 {
 211   bitmap blocks = BITMAP_ALLOC (NULL);
 212   basic_block commondom;
 213   unsigned int j;
 214   bitmap_iterator bi;
 215   ssa_op_iter op_iter;
 216   imm_use_iterator imm_iter;
 217   use_operand_p use_p;
 218   tree var;
 219
 220   bitmap_clear (blocks);
 221   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 222     {
 223       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 224         {
 225           gimple usestmt = USE_STMT (use_p);
 226           basic_block useblock;
 227
 228           if (gimple_code (usestmt) == GIMPLE_PHI)
 229             {
 230               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 231
 232               useblock = gimple_phi_arg_edge (usestmt, idx)->src;
 233             }
 234           else if (is_gimple_debug (usestmt))
 235             {
 236               *debug_stmts = true;
 237               continue;
 238             }
 239           else
 240             {
 241               useblock = gimple_bb (usestmt);
 242             }
 243
 244           /* Short circuit. Nothing dominates the entry block.  */
 245           if (useblock == ENTRY_BLOCK_PTR)
 246             {
 247               BITMAP_FREE (blocks);
 248               return NULL;
 249             }
 250           bitmap_set_bit (blocks, useblock->index);
 251         }
 252     }
 253   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 254   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 255     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 256                                           BASIC_BLOCK (j));
 257   BITMAP_FREE (blocks);
 258   return commondom;
 259 }
 260
 261 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 262    determine the location to sink the statement to, if any.
 263    Returns true if there is such location; in that case, TOGSI points to the
 264    statement before that STMT should be moved.  */
 265
 266 static bool
 267 statement_sink_location (gimple stmt, basic_block frombb,
 268                          gimple_stmt_iterator *togsi)
 269 {
 270   gimple use;
 271   tree def;
 272   use_operand_p one_use = NULL_USE_OPERAND_P;
 273   basic_block sinkbb;
 274   use_operand_p use_p;
 275   def_operand_p def_p;
 276   ssa_op_iter iter;
 277   imm_use_iterator imm_iter;
 278
 279   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 280     {
 281       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 282         {
 283           if (is_gimple_debug (USE_STMT (one_use)))
 284             continue;
 285
 286           break;
 287         }
 288       if (one_use != NULL_USE_OPERAND_P)
 289         break;
 290     }
 291
 292   /* Return if there are no immediate uses of this stmt.  */
 293   if (one_use == NULL_USE_OPERAND_P)
 294     return false;
 295
 296   if (gimple_code (stmt) != GIMPLE_ASSIGN)
 297     return false;
 298
 299   /* There are a few classes of things we can't or don't move, some because we
 300      don't have code to handle it, some because it's not profitable and some
 301      because it's not legal.
 302
 303      We can't sink things that may be global stores, at least not without
 304      calculating a lot more information, because we may cause it to no longer
 305      be seen by an external routine that needs it depending on where it gets
 306      moved to.
 307
 308      We don't want to sink loads from memory.
 309
 310      We can't sink statements that end basic blocks without splitting the
 311      incoming edge for the sink location to place it there.
 312
 313      We can't sink statements that have volatile operands.
 314
 315      We don't want to sink dead code, so anything with 0 immediate uses is not
 316      sunk.
 317
 318      Don't sink BLKmode assignments if current function has any local explicit
 319      register variables, as BLKmode assignments may involve memcpy or memset
 320      calls or, on some targets, inline expansion thereof that sometimes need
 321      to use specific hard registers.
 322
 323   */
 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       return true;
 389     }
 390
 391   use = USE_STMT (one_use);
 392   if (gimple_code (use) != GIMPLE_PHI)
 393     {
 394       sinkbb = gimple_bb (use);
 395       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 396           || sinkbb->loop_father != frombb->loop_father)
 397         return false;
 398
 399       /* Move the expression to a post dominator can't reduce the number of
 400          executions.  */
 401       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 402         return false;
 403
 404       *togsi = gsi_for_stmt (use);
 405
 406       return true;
 407     }
 408
 409   /* Note that at this point, all uses must be in the same statement, so it
 410      doesn't matter which def op we choose, pick the first one.  */
 411   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 412     break;
 413
 414   sinkbb = find_bb_for_arg (use, def);
 415   if (!sinkbb)
 416     return false;
 417
 418   /* This will happen when you have
 419      a_3 = PHI <a_13, a_26>
 420
 421      a_26 = VDEF <a_3>
 422
 423      If the use is a phi, and is in the same bb as the def,
 424      we can't sink it.  */
 425
 426   if (gimple_bb (use) == frombb)
 427     return false;
 428   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 429       || sinkbb->loop_father != frombb->loop_father)
 430     return false;
 431
 432   /* If the latch block is empty, don't make it non-empty by sinking
 433      something into it.  */
 434   if (sinkbb == frombb->loop_father->latch
 435       && empty_block_p (sinkbb))
 436     return false;
 437
 438   /* Move the expression to a post dominator can't reduce the number of
 439      executions.  */
 440   if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb))
 441     return false;
 442
 443   *togsi = gsi_after_labels (sinkbb);
 444
 445   return true;
 446 }
 447
 448 /* Perform code sinking on BB */
 449
 450 static void
 451 sink_code_in_bb (basic_block bb)
 452 {
 453   basic_block son;
 454   gimple_stmt_iterator gsi;
 455   edge_iterator ei;
 456   edge e;
 457   bool last = true;
 458
 459   /* If this block doesn't dominate anything, there can't be any place to sink
 460      the statements to.  */
 461   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 462     goto earlyout;
 463
 464   /* We can't move things across abnormal edges, so don't try.  */
 465   FOR_EACH_EDGE (e, ei, bb->succs)
 466     if (e->flags & EDGE_ABNORMAL)
 467       goto earlyout;
 468
 469   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
 470     {
 471       gimple stmt = gsi_stmt (gsi);
 472       gimple_stmt_iterator togsi;
 473
 474       if (!statement_sink_location (stmt, bb, &togsi))
 475         {
 476           if (!gsi_end_p (gsi))
 477             gsi_prev (&gsi);
 478           last = false;
 479           continue;
 480         }
 481       if (dump_file)
 482         {
 483           fprintf (dump_file, "Sinking ");
 484           print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS);
 485           fprintf (dump_file, " from bb %d to bb %d\n",
 486                    bb->index, (gsi_bb (togsi))->index);
 487         }
 488
 489       /* If this is the end of the basic block, we need to insert at the end
 490          of the basic block.  */
 491       if (gsi_end_p (togsi))
 492         gsi_move_to_bb_end (&gsi, gsi_bb (togsi));
 493       else
 494         gsi_move_before (&gsi, &togsi);
 495
 496       sink_stats.sunk++;
 497
 498       /* If we've just removed the last statement of the BB, the
 499          gsi_end_p() test below would fail, but gsi_prev() would have
 500          succeeded, and we want it to succeed.  So we keep track of
 501          whether we're at the last statement and pick up the new last
 502          statement.  */
 503       if (last)
 504         {
 505           gsi = gsi_last_bb (bb);
 506           continue;
 507         }
 508
 509       last = false;
 510       if (!gsi_end_p (gsi))
 511         gsi_prev (&gsi);
 512
 513     }
 514  earlyout:
 515   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 516        son;
 517        son = next_dom_son (CDI_POST_DOMINATORS, son))
 518     {
 519       sink_code_in_bb (son);
 520     }
 521 }
 522
 523 /* Perform code sinking.
 524    This moves code down the flowgraph when we know it would be
 525    profitable to do so, or it wouldn't increase the number of
 526    executions of the statement.
 527
 528    IE given
 529
 530    a_1 = b + c;
 531    if (<something>)
 532    {
 533    }
 534    else
 535    {
 536      foo (&b, &c);
 537      a_5 = b + c;
 538    }
 539    a_6 = PHI (a_5, a_1);
 540    USE a_6.
 541
 542    we'll transform this into:
 543
 544    if (<something>)
 545    {
 546       a_1 = b + c;
 547    }
 548    else
 549    {
 550       foo (&b, &c);
 551       a_5 = b + c;
 552    }
 553    a_6 = PHI (a_5, a_1);
 554    USE a_6.
 555
 556    Note that this reduces the number of computations of a = b + c to 1
 557    when we take the else edge, instead of 2.
 558 */
 559 static void
 560 execute_sink_code (void)
 561 {
 562   loop_optimizer_init (LOOPS_NORMAL);
 563
 564   connect_infinite_loops_to_exit ();
 565   memset (&sink_stats, 0, sizeof (sink_stats));
 566   calculate_dominance_info (CDI_DOMINATORS);
 567   calculate_dominance_info (CDI_POST_DOMINATORS);
 568   sink_code_in_bb (EXIT_BLOCK_PTR);
 569   statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk);
 570   free_dominance_info (CDI_POST_DOMINATORS);
 571   remove_fake_exit_edges ();
 572   loop_optimizer_finalize ();
 573 }
 574
 575 /* Gate and execute functions for PRE.  */
 576
 577 static unsigned int
 578 do_sink (void)
 579 {
 580   execute_sink_code ();
 581   return 0;
 582 }
 583
 584 static bool
 585 gate_sink (void)
 586 {
 587   return flag_tree_sink != 0;
 588 }
 589
 590 struct gimple_opt_pass pass_sink_code =
 591 {
 592  {
 593   GIMPLE_PASS,
 594   "sink",                               /* name */
 595   gate_sink,                            /* gate */
 596   do_sink,                              /* execute */
 597   NULL,                                 /* sub */
 598   NULL,                                 /* next */
 599   0,                                    /* static_pass_number */
 600   TV_TREE_SINK,                         /* tv_id */
 601   PROP_no_crit_edges | PROP_cfg
 602     | PROP_ssa,                         /* properties_required */
 603   0,                                    /* properties_provided */
 604   0,                                    /* properties_destroyed */
 605   0,                                    /* todo_flags_start */
 606   TODO_update_ssa
 607     | TODO_verify_ssa
 608     | TODO_verify_flow
 609     | TODO_dump_func
 610     | TODO_ggc_collect                  /* todo_flags_finish */
 611  }
 612 };