gcc/tree-ssa-sink.c

   1 /* Code sinking for trees
   2    Copyright (C) 2001, 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "ggc.h"
  26 #include "tree.h"
  27 #include "basic-block.h"
  28 #include "diagnostic.h"
  29 #include "tree-inline.h"
  30 #include "tree-flow.h"
  31 #include "tree-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 "real.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 (tree phi, tree def)
  86 {
  87   int i;
  88   bool foundone = false;
  89   basic_block result = NULL;
  90   for (i = 0; i < 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 = 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 (tree stmt)
 111 {
 112   tree firstuse = NULL_TREE;
 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 (firstuse == NULL_TREE)
 123             firstuse = USE_STMT (use_p);
 124           else
 125             if (firstuse != USE_STMT (use_p))
 126               return false;
 127         }
 128     }
 129
 130   return true;
 131 }
 132
 133 /* Some global stores don't necessarily have VDEF's of global variables,
 134    but we still must avoid moving them around.  */
 135
 136 bool
 137 is_hidden_global_store (tree stmt)
 138 {
 139   /* Check virtual definitions.  If we get here, the only virtual
 140      definitions we should see are those generated by assignment
 141      statements.  */
 142   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 143     {
 144       tree lhs;
 145
 146       gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
 147
 148       /* Note that we must not check the individual virtual operands
 149          here.  In particular, if this is an aliased store, we could
 150          end up with something like the following (SSA notation
 151          redacted for brevity):
 152
 153                 foo (int *p, int i)
 154                 {
 155                   int x;
 156                   p_1 = (i_2 > 3) ? &x : p;
 157
 158                   # x_4 = VDEF <x_3>
 159                   *p_1 = 5;
 160
 161                   return 2;
 162                 }
 163
 164          Notice that the store to '*p_1' should be preserved, if we
 165          were to check the virtual definitions in that store, we would
 166          not mark it needed.  This is because 'x' is not a global
 167          variable.
 168
 169          Therefore, we check the base address of the LHS.  If the
 170          address is a pointer, we check if its name tag or symbol tag is
 171          a global variable.  Otherwise, we check if the base variable
 172          is a global.  */
 173       lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 174       if (REFERENCE_CLASS_P (lhs))
 175         lhs = get_base_address (lhs);
 176
 177       if (lhs == NULL_TREE)
 178         {
 179           /* If LHS is NULL, it means that we couldn't get the base
 180              address of the reference.  In which case, we should not
 181              move this store.  */
 182           return true;
 183         }
 184       else if (DECL_P (lhs))
 185         {
 186           /* If the store is to a global symbol, we need to keep it.  */
 187           if (is_global_var (lhs))
 188             return true;
 189
 190         }
 191       else if (INDIRECT_REF_P (lhs))
 192         {
 193           tree ptr = TREE_OPERAND (lhs, 0);
 194           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 195           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 196           tree smt = symbol_mem_tag (SSA_NAME_VAR (ptr));
 197
 198           /* If either the name tag or the symbol tag for PTR is a
 199              global variable, then the store is necessary.  */
 200           if ((nmt && is_global_var (nmt))
 201               || (smt && is_global_var (smt)))
 202             {
 203               return true;
 204             }
 205         }
 206       else
 207         gcc_unreachable ();
 208     }
 209
 210   return false;
 211 }
 212
 213 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 214
 215 static basic_block
 216 nearest_common_dominator_of_uses (tree stmt)
 217 {
 218   bitmap blocks = BITMAP_ALLOC (NULL);
 219   basic_block commondom;
 220   unsigned int j;
 221   bitmap_iterator bi;
 222   ssa_op_iter op_iter;
 223   imm_use_iterator imm_iter;
 224   use_operand_p use_p;
 225   tree var;
 226
 227   bitmap_clear (blocks);
 228   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 229     {
 230       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 231         {
 232           tree usestmt = USE_STMT (use_p);
 233           basic_block useblock;
 234
 235           if (TREE_CODE (usestmt) == PHI_NODE)
 236             {
 237               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 238
 239               useblock = PHI_ARG_EDGE (usestmt, idx)->src;
 240             }
 241           else
 242             {
 243               useblock = bb_for_stmt (usestmt);
 244             }
 245
 246           /* Short circuit. Nothing dominates the entry block.  */
 247           if (useblock == ENTRY_BLOCK_PTR)
 248             {
 249               BITMAP_FREE (blocks);
 250               return NULL;
 251             }
 252           bitmap_set_bit (blocks, useblock->index);
 253         }
 254     }
 255   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 256   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 257     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 258                                           BASIC_BLOCK (j));
 259   BITMAP_FREE (blocks);
 260   return commondom;
 261 }
 262
 263 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 264    determine the location to sink the statement to, if any.
 265    Returns true if there is such location; in that case, TOBB is set to the
 266    basic block of the location, and TOBSI points to the statement before
 267    that STMT should be moved.  */
 268
 269 static bool
 270 statement_sink_location (tree stmt, basic_block frombb, basic_block *tobb,
 271                          block_stmt_iterator *tobsi)
 272 {
 273   tree use, def;
 274   use_operand_p one_use = NULL_USE_OPERAND_P;
 275   basic_block sinkbb;
 276   use_operand_p use_p;
 277   def_operand_p def_p;
 278   ssa_op_iter iter;
 279   stmt_ann_t ann;
 280   tree rhs;
 281   imm_use_iterator imm_iter;
 282
 283   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 284     {
 285       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 286         {
 287           break;
 288         }
 289       if (one_use != NULL_USE_OPERAND_P)
 290         break;
 291     }
 292
 293   /* Return if there are no immediate uses of this stmt.  */
 294   if (one_use == NULL_USE_OPERAND_P)
 295     return false;
 296
 297   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 298     return false;
 299   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 300
 301   /* There are a few classes of things we can't or don't move, some because we
 302      don't have code to handle it, some because it's not profitable and some
 303      because it's not legal.
 304
 305      We can't sink things that may be global stores, at least not without
 306      calculating a lot more information, because we may cause it to no longer
 307      be seen by an external routine that needs it depending on where it gets
 308      moved to.
 309
 310      We don't want to sink loads from memory.
 311
 312      We can't sink statements that end basic blocks without splitting the
 313      incoming edge for the sink location to place it there.
 314
 315      We can't sink statements that have volatile operands.
 316
 317      We don't want to sink dead code, so anything with 0 immediate uses is not
 318      sunk.
 319
 320   */
 321   ann = stmt_ann (stmt);
 322   if (stmt_ends_bb_p (stmt)
 323       || TREE_SIDE_EFFECTS (rhs)
 324       || TREE_CODE (rhs) == EXC_PTR_EXPR
 325       || TREE_CODE (rhs) == FILTER_EXPR
 326       || is_hidden_global_store (stmt)
 327       || ann->has_volatile_ops
 328       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 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       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 353
 354       if (commondom == frombb)
 355         return false;
 356
 357       /* Our common dominator has to be dominated by frombb in order to be a
 358          trivially safe place to put this statement, since it has multiple
 359          uses.  */
 360       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 361         return false;
 362
 363       /* It doesn't make sense to move to a dominator that post-dominates
 364          frombb, because it means we've just moved it into a path that always
 365          executes if frombb executes, instead of reducing the number of
 366          executions .  */
 367       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 368         {
 369           if (dump_file && (dump_flags & TDF_DETAILS))
 370             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 371           return false;
 372         }
 373
 374       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 375         return false;
 376       if (dump_file && (dump_flags & TDF_DETAILS))
 377         {
 378           fprintf (dump_file, "Common dominator of all uses is %d\n",
 379                    commondom->index);
 380         }
 381       *tobb = commondom;
 382       *tobsi = bsi_after_labels (commondom);
 383       return true;
 384     }
 385
 386   use = USE_STMT (one_use);
 387   if (TREE_CODE (use) != PHI_NODE)
 388     {
 389       sinkbb = bb_for_stmt (use);
 390       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 391           || sinkbb->loop_father != frombb->loop_father)
 392         return false;
 393       *tobb = sinkbb;
 394       *tobsi = bsi_for_stmt (use);
 395       return true;
 396     }
 397
 398   /* Note that at this point, all uses must be in the same statement, so it
 399      doesn't matter which def op we choose, pick the first one.  */
 400   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 401     break;
 402
 403   sinkbb = find_bb_for_arg (use, def);
 404   if (!sinkbb)
 405     return false;
 406
 407   /* This will happen when you have
 408      a_3 = PHI <a_13, a_26>
 409
 410      a_26 = VDEF <a_3>
 411
 412      If the use is a phi, and is in the same bb as the def,
 413      we can't sink it.  */
 414
 415   if (bb_for_stmt (use) == frombb)
 416     return false;
 417   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 418       || sinkbb->loop_father != frombb->loop_father)
 419     return false;
 420
 421   *tobb = sinkbb;
 422   *tobsi = bsi_after_labels (sinkbb);
 423
 424   return true;
 425 }
 426
 427 /* Perform code sinking on BB */
 428
 429 static void
 430 sink_code_in_bb (basic_block bb)
 431 {
 432   basic_block son;
 433   block_stmt_iterator bsi;
 434   edge_iterator ei;
 435   edge e;
 436   bool last = true;
 437
 438   /* If this block doesn't dominate anything, there can't be any place to sink
 439      the statements to.  */
 440   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 441     goto earlyout;
 442
 443   /* We can't move things across abnormal edges, so don't try.  */
 444   FOR_EACH_EDGE (e, ei, bb->succs)
 445     if (e->flags & EDGE_ABNORMAL)
 446       goto earlyout;
 447
 448   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 449     {
 450       tree stmt = bsi_stmt (bsi);
 451       block_stmt_iterator tobsi;
 452       basic_block tobb;
 453
 454       if (!statement_sink_location (stmt, bb, &tobb, &tobsi))
 455         {
 456           if (!bsi_end_p (bsi))
 457             bsi_prev (&bsi);
 458           last = false;
 459           continue;
 460         }
 461       if (dump_file)
 462         {
 463           fprintf (dump_file, "Sinking ");
 464           print_generic_expr (dump_file, stmt, TDF_VOPS);
 465           fprintf (dump_file, " from bb %d to bb %d\n",
 466                    bb->index, tobb->index);
 467         }
 468
 469       /* If this is the end of the basic block, we need to insert at the end
 470          of the basic block.  */
 471       if (bsi_end_p (tobsi))
 472         bsi_move_to_bb_end (&bsi, tobb);
 473       else
 474         bsi_move_before (&bsi, &tobsi);
 475
 476       sink_stats.sunk++;
 477
 478       /* If we've just removed the last statement of the BB, the
 479          bsi_end_p() test below would fail, but bsi_prev() would have
 480          succeeded, and we want it to succeed.  So we keep track of
 481          whether we're at the last statement and pick up the new last
 482          statement.  */
 483       if (last)
 484         {
 485           bsi = bsi_last (bb);
 486           continue;
 487         }
 488
 489       last = false;
 490       if (!bsi_end_p (bsi))
 491         bsi_prev (&bsi);
 492
 493     }
 494  earlyout:
 495   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 496        son;
 497        son = next_dom_son (CDI_POST_DOMINATORS, son))
 498     {
 499       sink_code_in_bb (son);
 500     }
 501 }
 502
 503 /* Perform code sinking.
 504    This moves code down the flowgraph when we know it would be
 505    profitable to do so, or it wouldn't increase the number of
 506    executions of the statement.
 507
 508    IE given
 509
 510    a_1 = b + c;
 511    if (<something>)
 512    {
 513    }
 514    else
 515    {
 516      foo (&b, &c);
 517      a_5 = b + c;
 518    }
 519    a_6 = PHI (a_5, a_1);
 520    USE a_6.
 521
 522    we'll transform this into:
 523
 524    if (<something>)
 525    {
 526       a_1 = b + c;
 527    }
 528    else
 529    {
 530       foo (&b, &c);
 531       a_5 = b + c;
 532    }
 533    a_6 = PHI (a_5, a_1);
 534    USE a_6.
 535
 536    Note that this reduces the number of computations of a = b + c to 1
 537    when we take the else edge, instead of 2.
 538 */
 539 static void
 540 execute_sink_code (void)
 541 {
 542   loop_optimizer_init (LOOPS_NORMAL);
 543
 544   connect_infinite_loops_to_exit ();
 545   memset (&sink_stats, 0, sizeof (sink_stats));
 546   calculate_dominance_info (CDI_DOMINATORS);
 547   calculate_dominance_info (CDI_POST_DOMINATORS);
 548   sink_code_in_bb (EXIT_BLOCK_PTR);
 549   if (dump_file && (dump_flags & TDF_STATS))
 550     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 551   free_dominance_info (CDI_POST_DOMINATORS);
 552   remove_fake_exit_edges ();
 553   loop_optimizer_finalize ();
 554 }
 555
 556 /* Gate and execute functions for PRE.  */
 557
 558 static unsigned int
 559 do_sink (void)
 560 {
 561   execute_sink_code ();
 562   return 0;
 563 }
 564
 565 static bool
 566 gate_sink (void)
 567 {
 568   return flag_tree_sink != 0;
 569 }
 570
 571 struct tree_opt_pass pass_sink_code =
 572 {
 573   "sink",                               /* name */
 574   gate_sink,                            /* gate */
 575   do_sink,                              /* execute */
 576   NULL,                                 /* sub */
 577   NULL,                                 /* next */
 578   0,                                    /* static_pass_number */
 579   TV_TREE_SINK,                         /* tv_id */
 580   PROP_no_crit_edges | PROP_cfg
 581     | PROP_ssa | PROP_alias,            /* properties_required */
 582   0,                                    /* properties_provided */
 583   0,                                    /* properties_destroyed */
 584   0,                                    /* todo_flags_start */
 585   TODO_update_ssa
 586     | TODO_dump_func
 587     | TODO_ggc_collect
 588     | TODO_verify_ssa,                  /* todo_flags_finish */
 589   0                                     /* letter */
 590 };