gcc/tree-ssa-sink.c

   1 /* Code sinking for trees
   2    Copyright (C) 2001, 2002, 2003, 2004 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 2, 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 COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  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 "tree-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 (tree phi, tree def)
  87 {
  88   int i;
  89   bool foundone = false;
  90   basic_block result = NULL;
  91   for (i = 0; i < 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 = 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 (tree stmt)
 112 {
 113   tree firstuse = NULL_TREE;
 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 (firstuse == NULL_TREE)
 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 (tree stmt)
 139 {
 140   /* Check virtual definitions.  If we get here, the only virtual
 141      definitions we should see are those generated by assignment
 142      statements.  */
 143   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 144     {
 145       tree lhs;
 146
 147       gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_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_STMT_OPERAND (stmt, 0);
 175       if (REFERENCE_CLASS_P (lhs))
 176         lhs = get_base_address (lhs);
 177
 178       if (lhs == NULL_TREE)
 179         {
 180           /* If LHS is NULL, it means that we couldn't get the base
 181              address of the reference.  In which case, we should not
 182              move this store.  */
 183           return true;
 184         }
 185       else if (DECL_P (lhs))
 186         {
 187           /* If the store is to a global symbol, we need to keep it.  */
 188           if (is_global_var (lhs))
 189             return true;
 190
 191         }
 192       else if (INDIRECT_REF_P (lhs))
 193         {
 194           tree ptr = TREE_OPERAND (lhs, 0);
 195           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 196           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 197           tree smt = symbol_mem_tag (SSA_NAME_VAR (ptr));
 198
 199           /* If either the name tag or the symbol tag for PTR is a
 200              global variable, then the store is necessary.  */
 201           if ((nmt && is_global_var (nmt))
 202               || (smt && is_global_var (smt)))
 203             {
 204               return true;
 205             }
 206         }
 207       else
 208         gcc_unreachable ();
 209     }
 210
 211   return false;
 212 }
 213
 214 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 215
 216 static basic_block
 217 nearest_common_dominator_of_uses (tree stmt)
 218 {
 219   bitmap blocks = BITMAP_ALLOC (NULL);
 220   basic_block commondom;
 221   unsigned int j;
 222   bitmap_iterator bi;
 223   ssa_op_iter op_iter;
 224   imm_use_iterator imm_iter;
 225   use_operand_p use_p;
 226   tree var;
 227
 228   bitmap_clear (blocks);
 229   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 230     {
 231       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 232         {
 233           tree usestmt = USE_STMT (use_p);
 234           basic_block useblock;
 235
 236           if (TREE_CODE (usestmt) == PHI_NODE)
 237             {
 238               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 239
 240               useblock = PHI_ARG_EDGE (usestmt, idx)->src;
 241             }
 242           else
 243             {
 244               useblock = bb_for_stmt (usestmt);
 245             }
 246
 247           /* Short circuit. Nothing dominates the entry block.  */
 248           if (useblock == ENTRY_BLOCK_PTR)
 249             {
 250               BITMAP_FREE (blocks);
 251               return NULL;
 252             }
 253           bitmap_set_bit (blocks, useblock->index);
 254         }
 255     }
 256   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 257   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 258     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 259                                           BASIC_BLOCK (j));
 260   BITMAP_FREE (blocks);
 261   return commondom;
 262 }
 263
 264 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 265    determine the location to sink the statement to, if any.
 266    Returns true if there is such location; in that case, TOBB is set to the
 267    basic block of the location, and TOBSI points to the statement before
 268    that STMT should be moved.  */
 269
 270 static bool
 271 statement_sink_location (tree stmt, basic_block frombb, basic_block *tobb,
 272                          block_stmt_iterator *tobsi)
 273 {
 274   tree use, def;
 275   use_operand_p one_use = NULL_USE_OPERAND_P;
 276   basic_block sinkbb;
 277   use_operand_p use_p;
 278   def_operand_p def_p;
 279   ssa_op_iter iter;
 280   stmt_ann_t ann;
 281   tree rhs;
 282   imm_use_iterator imm_iter;
 283
 284   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 285     {
 286       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 287         {
 288           break;
 289         }
 290       if (one_use != NULL_USE_OPERAND_P)
 291         break;
 292     }
 293
 294   /* Return if there are no immediate uses of this stmt.  */
 295   if (one_use == NULL_USE_OPERAND_P)
 296     return false;
 297
 298   if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
 299     return false;
 300   rhs = GIMPLE_STMT_OPERAND (stmt, 1);
 301
 302   /* There are a few classes of things we can't or don't move, some because we
 303      don't have code to handle it, some because it's not profitable and some
 304      because it's not legal.
 305
 306      We can't sink things that may be global stores, at least not without
 307      calculating a lot more information, because we may cause it to no longer
 308      be seen by an external routine that needs it depending on where it gets
 309      moved to.
 310
 311      We don't want to sink loads from memory.
 312
 313      We can't sink statements that end basic blocks without splitting the
 314      incoming edge for the sink location to place it there.
 315
 316      We can't sink statements that have volatile operands.
 317
 318      We don't want to sink dead code, so anything with 0 immediate uses is not
 319      sunk.
 320
 321   */
 322   ann = stmt_ann (stmt);
 323   if (stmt_ends_bb_p (stmt)
 324       || TREE_SIDE_EFFECTS (rhs)
 325       || TREE_CODE (rhs) == EXC_PTR_EXPR
 326       || TREE_CODE (rhs) == FILTER_EXPR
 327       || is_hidden_global_store (stmt)
 328       || ann->has_volatile_ops
 329       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 330     return false;
 331
 332   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 333     {
 334       tree def = DEF_FROM_PTR (def_p);
 335       if (is_global_var (SSA_NAME_VAR (def))
 336           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 337         return false;
 338     }
 339
 340   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 341     {
 342       tree use = USE_FROM_PTR (use_p);
 343       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 344         return false;
 345     }
 346
 347   /* If all the immediate uses are not in the same place, find the nearest
 348      common dominator of all the immediate uses.  For PHI nodes, we have to
 349      find the nearest common dominator of all of the predecessor blocks, since
 350      that is where insertion would have to take place.  */
 351   if (!all_immediate_uses_same_place (stmt))
 352     {
 353       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 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       *tobb = commondom;
 383       *tobsi = bsi_after_labels (commondom);
 384       return true;
 385     }
 386
 387   use = USE_STMT (one_use);
 388   if (TREE_CODE (use) != PHI_NODE)
 389     {
 390       sinkbb = bb_for_stmt (use);
 391       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 392           || sinkbb->loop_father != frombb->loop_father)
 393         return false;
 394       *tobb = sinkbb;
 395       *tobsi = bsi_for_stmt (use);
 396       return true;
 397     }
 398
 399   /* Note that at this point, all uses must be in the same statement, so it
 400      doesn't matter which def op we choose, pick the first one.  */
 401   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 402     break;
 403
 404   sinkbb = find_bb_for_arg (use, def);
 405   if (!sinkbb)
 406     return false;
 407
 408   /* This will happen when you have
 409      a_3 = PHI <a_13, a_26>
 410
 411      a_26 = VDEF <a_3>
 412
 413      If the use is a phi, and is in the same bb as the def,
 414      we can't sink it.  */
 415
 416   if (bb_for_stmt (use) == frombb)
 417     return false;
 418   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 419       || sinkbb->loop_father != frombb->loop_father)
 420     return false;
 421
 422   *tobb = sinkbb;
 423   *tobsi = bsi_after_labels (sinkbb);
 424
 425   return true;
 426 }
 427
 428 /* Perform code sinking on BB */
 429
 430 static void
 431 sink_code_in_bb (basic_block bb)
 432 {
 433   basic_block son;
 434   block_stmt_iterator bsi;
 435   edge_iterator ei;
 436   edge e;
 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           continue;
 459         }
 460       if (dump_file)
 461         {
 462           fprintf (dump_file, "Sinking ");
 463           print_generic_expr (dump_file, stmt, TDF_VOPS);
 464           fprintf (dump_file, " from bb %d to bb %d\n",
 465                    bb->index, tobb->index);
 466         }
 467
 468       /* If this is the end of the basic block, we need to insert at the end
 469          of the basic block.  */
 470       if (bsi_end_p (tobsi))
 471         bsi_move_to_bb_end (&bsi, tobb);
 472       else
 473         bsi_move_before (&bsi, &tobsi);
 474
 475       sink_stats.sunk++;
 476       if (!bsi_end_p (bsi))
 477         bsi_prev (&bsi);
 478
 479     }
 480  earlyout:
 481   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 482        son;
 483        son = next_dom_son (CDI_POST_DOMINATORS, son))
 484     {
 485       sink_code_in_bb (son);
 486     }
 487 }
 488
 489 /* Perform code sinking.
 490    This moves code down the flowgraph when we know it would be
 491    profitable to do so, or it wouldn't increase the number of
 492    executions of the statement.
 493
 494    IE given
 495
 496    a_1 = b + c;
 497    if (<something>)
 498    {
 499    }
 500    else
 501    {
 502      foo (&b, &c);
 503      a_5 = b + c;
 504    }
 505    a_6 = PHI (a_5, a_1);
 506    USE a_6.
 507
 508    we'll transform this into:
 509
 510    if (<something>)
 511    {
 512       a_1 = b + c;
 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    Note that this reduces the number of computations of a = b + c to 1
 523    when we take the else edge, instead of 2.
 524 */
 525 static void
 526 execute_sink_code (void)
 527 {
 528   loop_optimizer_init (LOOPS_NORMAL);
 529
 530   connect_infinite_loops_to_exit ();
 531   memset (&sink_stats, 0, sizeof (sink_stats));
 532   calculate_dominance_info (CDI_DOMINATORS);
 533   calculate_dominance_info (CDI_POST_DOMINATORS);
 534   sink_code_in_bb (EXIT_BLOCK_PTR);
 535   if (dump_file && (dump_flags & TDF_STATS))
 536     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 537   free_dominance_info (CDI_POST_DOMINATORS);
 538   remove_fake_exit_edges ();
 539   loop_optimizer_finalize ();
 540 }
 541
 542 /* Gate and execute functions for PRE.  */
 543
 544 static unsigned int
 545 do_sink (void)
 546 {
 547   execute_sink_code ();
 548   return 0;
 549 }
 550
 551 static bool
 552 gate_sink (void)
 553 {
 554   return flag_tree_sink != 0;
 555 }
 556
 557 struct tree_opt_pass pass_sink_code =
 558 {
 559   "sink",                               /* name */
 560   gate_sink,                            /* gate */
 561   do_sink,                              /* execute */
 562   NULL,                                 /* sub */
 563   NULL,                                 /* next */
 564   0,                                    /* static_pass_number */
 565   TV_TREE_SINK,                         /* tv_id */
 566   PROP_no_crit_edges | PROP_cfg
 567     | PROP_ssa | PROP_alias,            /* properties_required */
 568   0,                                    /* properties_provided */
 569   0,                                    /* properties_destroyed */
 570   0,                                    /* todo_flags_start */
 571   TODO_update_ssa
 572     | TODO_dump_func
 573     | TODO_ggc_collect
 574     | TODO_verify_ssa,                  /* todo_flags_finish */
 575   0                                     /* letter */
 576 };