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