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 V_MAY_DEF'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) == MODIFY_EXPR);
 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 = V_MAY_DEF <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 type tag is
 172          a global variable.  Otherwise, we check if the base variable
 173          is a global.  */
 174       lhs = TREE_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 tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 198
 199           /* If either the name tag or the type tag for PTR is a
 200              global variable, then the store is necessary.  */
 201           if ((nmt && is_global_var (nmt))
 202               || (tmt && is_global_var (tmt)))
 203             {
 204               return true;
 205             }
 206         }
 207       else
 208         gcc_unreachable ();
 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    Return the basic block to sink it to, or NULL if we should not sink
 266    it.  */
 267
 268 static tree
 269 statement_sink_location (tree stmt, basic_block frombb)
 270 {
 271   tree use, 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   stmt_ann_t ann;
 278   tree rhs;
 279   imm_use_iterator imm_iter;
 280
 281   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 282     {
 283       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 284         {
 285           break;
 286         }
 287       if (one_use != NULL_USE_OPERAND_P)
 288         break;
 289     }
 290
 291   /* Return if there are no immediate uses of this stmt.  */
 292   if (one_use == NULL_USE_OPERAND_P)
 293     return NULL;
 294
 295   if (TREE_CODE (stmt) != MODIFY_EXPR)
 296     return NULL;
 297   rhs = TREE_OPERAND (stmt, 1);
 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   */
 319   ann = stmt_ann (stmt);
 320   if (stmt_ends_bb_p (stmt)
 321       || TREE_SIDE_EFFECTS (rhs)
 322       || TREE_CODE (rhs) == EXC_PTR_EXPR
 323       || TREE_CODE (rhs) == FILTER_EXPR
 324       || is_hidden_global_store (stmt)
 325       || ann->has_volatile_ops
 326       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 327     return NULL;
 328
 329   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 330     {
 331       tree def = DEF_FROM_PTR (def_p);
 332       if (is_global_var (SSA_NAME_VAR (def))
 333           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 334         return NULL;
 335     }
 336
 337   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 338     {
 339       tree use = USE_FROM_PTR (use_p);
 340       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 341         return NULL;
 342     }
 343
 344   /* If all the immediate uses are not in the same place, find the nearest
 345      common dominator of all the immediate uses.  For PHI nodes, we have to
 346      find the nearest common dominator of all of the predecessor blocks, since
 347      that is where insertion would have to take place.  */
 348   if (!all_immediate_uses_same_place (stmt))
 349     {
 350       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 351
 352       if (commondom == frombb)
 353         return NULL;
 354
 355       /* Our common dominator has to be dominated by frombb in order to be a
 356          trivially safe place to put this statement, since it has multiple
 357          uses.  */
 358       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 359         return NULL;
 360
 361       /* It doesn't make sense to move to a dominator that post-dominates
 362          frombb, because it means we've just moved it into a path that always
 363          executes if frombb executes, instead of reducing the number of
 364          executions .  */
 365       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 366         {
 367           if (dump_file && (dump_flags & TDF_DETAILS))
 368             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 369           return NULL;
 370         }
 371
 372       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 373         return NULL;
 374       if (dump_file && (dump_flags & TDF_DETAILS))
 375         {
 376           fprintf (dump_file, "Common dominator of all uses is %d\n",
 377                    commondom->index);
 378         }
 379       return first_stmt (commondom);
 380     }
 381
 382   use = USE_STMT (one_use);
 383   if (TREE_CODE (use) != PHI_NODE)
 384     {
 385       sinkbb = bb_for_stmt (use);
 386       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 387           || sinkbb->loop_father != frombb->loop_father)
 388         return NULL;
 389       return use;
 390     }
 391
 392   /* Note that at this point, all uses must be in the same statement, so it
 393      doesn't matter which def op we choose, pick the first one.  */
 394   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 395     break;
 396
 397
 398   sinkbb = find_bb_for_arg (use, def);
 399   if (!sinkbb)
 400     return NULL;
 401
 402   /* This will happen when you have
 403      a_3 = PHI <a_13, a_26>
 404
 405      a_26 = V_MAY_DEF <a_3>
 406
 407      If the use is a phi, and is in the same bb as the def,
 408      we can't sink it.  */
 409
 410   if (bb_for_stmt (use) == frombb)
 411     return NULL;
 412   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 413       || sinkbb->loop_father != frombb->loop_father)
 414     return NULL;
 415
 416   return first_stmt (sinkbb);
 417 }
 418
 419 /* Perform code sinking on BB */
 420
 421 static void
 422 sink_code_in_bb (basic_block bb)
 423 {
 424   basic_block son;
 425   block_stmt_iterator bsi;
 426   edge_iterator ei;
 427   edge e;
 428
 429   /* If this block doesn't dominate anything, there can't be any place to sink
 430      the statements to.  */
 431   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 432     goto earlyout;
 433
 434   /* We can't move things across abnormal edges, so don't try.  */
 435   FOR_EACH_EDGE (e, ei, bb->succs)
 436     if (e->flags & EDGE_ABNORMAL)
 437       goto earlyout;
 438
 439   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 440     {
 441       tree stmt = bsi_stmt (bsi);
 442       block_stmt_iterator tobsi;
 443       tree sinkstmt;
 444
 445       sinkstmt = statement_sink_location (stmt, bb);
 446       if (!sinkstmt)
 447         {
 448           if (!bsi_end_p (bsi))
 449             bsi_prev (&bsi);
 450           continue;
 451         }
 452       if (dump_file)
 453         {
 454           fprintf (dump_file, "Sinking ");
 455           print_generic_expr (dump_file, stmt, TDF_VOPS);
 456           fprintf (dump_file, " from bb %d to bb %d\n",
 457                    bb->index, bb_for_stmt (sinkstmt)->index);
 458         }
 459       tobsi = bsi_for_stmt (sinkstmt);
 460       /* Find the first non-label.  */
 461       while (!bsi_end_p (tobsi)
 462              && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
 463         bsi_next (&tobsi);
 464
 465       /* If this is the end of the basic block, we need to insert at the end
 466          of the basic block.  */
 467       if (bsi_end_p (tobsi))
 468         bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
 469       else
 470         bsi_move_before (&bsi, &tobsi);
 471
 472       sink_stats.sunk++;
 473       if (!bsi_end_p (bsi))
 474         bsi_prev (&bsi);
 475
 476     }
 477  earlyout:
 478   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 479        son;
 480        son = next_dom_son (CDI_POST_DOMINATORS, son))
 481     {
 482       sink_code_in_bb (son);
 483     }
 484 }
 485
 486 /* Perform code sinking.
 487    This moves code down the flowgraph when we know it would be
 488    profitable to do so, or it wouldn't increase the number of
 489    executions of the statement.
 490
 491    IE given
 492
 493    a_1 = b + c;
 494    if (<something>)
 495    {
 496    }
 497    else
 498    {
 499      foo (&b, &c);
 500      a_5 = b + c;
 501    }
 502    a_6 = PHI (a_5, a_1);
 503    USE a_6.
 504
 505    we'll transform this into:
 506
 507    if (<something>)
 508    {
 509       a_1 = b + c;
 510    }
 511    else
 512    {
 513       foo (&b, &c);
 514       a_5 = b + c;
 515    }
 516    a_6 = PHI (a_5, a_1);
 517    USE a_6.
 518
 519    Note that this reduces the number of computations of a = b + c to 1
 520    when we take the else edge, instead of 2.
 521 */
 522 static void
 523 execute_sink_code (void)
 524 {
 525   struct loops *loops = loop_optimizer_init (dump_file);
 526   connect_infinite_loops_to_exit ();
 527   memset (&sink_stats, 0, sizeof (sink_stats));
 528   calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
 529   sink_code_in_bb (EXIT_BLOCK_PTR);
 530   if (dump_file && (dump_flags & TDF_STATS))
 531     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 532   free_dominance_info (CDI_POST_DOMINATORS);
 533   remove_fake_exit_edges ();
 534   loop_optimizer_finalize (loops, dump_file);
 535 }
 536
 537 /* Gate and execute functions for PRE.  */
 538
 539 static void
 540 do_sink (void)
 541 {
 542   execute_sink_code ();
 543 }
 544
 545 static bool
 546 gate_sink (void)
 547 {
 548   return flag_tree_sink != 0;
 549 }
 550
 551 struct tree_opt_pass pass_sink_code =
 552 {
 553   "sink",                               /* name */
 554   gate_sink,                            /* gate */
 555   do_sink,                              /* execute */
 556   NULL,                                 /* sub */
 557   NULL,                                 /* next */
 558   0,                                    /* static_pass_number */
 559   TV_TREE_SINK,                         /* tv_id */
 560   PROP_no_crit_edges | PROP_cfg
 561     | PROP_ssa | PROP_alias,            /* properties_required */
 562   0,                                    /* properties_provided */
 563   0,                                    /* properties_destroyed */
 564   0,                                    /* todo_flags_start */
 565   TODO_update_ssa
 566     | TODO_dump_func
 567     | TODO_ggc_collect
 568     | TODO_verify_ssa,                  /* todo_flags_finish */
 569   0                                     /* letter */
 570 };