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, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "errors.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "basic-block.h"
  30 #include "diagnostic.h"
  31 #include "tree-inline.h"
  32 #include "tree-flow.h"
  33 #include "tree-gimple.h"
  34 #include "tree-dump.h"
  35 #include "timevar.h"
  36 #include "fibheap.h"
  37 #include "hashtab.h"
  38 #include "tree-iterator.h"
  39 #include "real.h"
  40 #include "alloc-pool.h"
  41 #include "tree-pass.h"
  42 #include "flags.h"
  43 #include "bitmap.h"
  44 #include "langhooks.h"
  45 #include "cfgloop.h"
  46
  47 /* TODO:
  48    1. Sinking store only using scalar promotion (IE without moving the RHS):
  49
  50    *q = p;
  51    p = p + 1;
  52    if (something)
  53      *q = <not p>;
  54    else
  55      y = *q;
  56
  57
  58    should become
  59    sinktemp = p;
  60    p = p + 1;
  61    if (something)
  62      *q = <not p>;
  63    else
  64    {
  65      *q = sinktemp;
  66      y = *q
  67    }
  68    Store copy propagation will take care of the store elimination above.
  69
  70
  71    2. Sinking using Partial Dead Code Elimination.  */
  72
  73
  74 static struct
  75 {
  76   /* The number of statements sunk down the flowgraph by code sinking.  */
  77   int sunk;
  78
  79 } sink_stats;
  80
  81
  82 /* Given a PHI, and one of it's arguments (DEF), find the edge for
  83    that argument and return it.  If the argument occurs twice in the PHI node,
  84    we return NULL.  */
  85
  86 static basic_block
  87 find_bb_for_arg (tree phi, tree def)
  88 {
  89   int i;
  90   bool foundone = false;
  91   basic_block result = NULL;
  92   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
  93     if (PHI_ARG_DEF (phi, i) == def)
  94       {
  95         if (foundone)
  96           return NULL;
  97         foundone = true;
  98         result = PHI_ARG_EDGE (phi, i)->src;
  99       }
 100   return result;
 101 }
 102
 103 /* When the first immediate use is in a statement, then return true if all
 104    immediate uses in IMM are in the same statement.
 105    We could also do the case where  the first immediate use is in a phi node,
 106    and all the other uses are in phis in the same basic block, but this
 107    requires some expensive checking later (you have to make sure no def/vdef
 108    in the statement occurs for multiple edges in the various phi nodes it's
 109    used in, so that you only have one place you can sink it to.  */
 110
 111 static bool
 112 all_immediate_uses_same_place (dataflow_t imm)
 113 {
 114   int i;
 115   tree firstuse;
 116
 117   if (imm == NULL || num_immediate_uses (imm) < 2)
 118     return true;
 119   firstuse = immediate_use (imm, 0);
 120
 121   for (i = 1; i < num_immediate_uses (imm); i++)
 122     {
 123       tree immuse = immediate_use (imm, i);
 124       if (immuse != firstuse)
 125         return false;
 126     }
 127   return true;
 128 }
 129
 130 /* Some global stores don't necessarily have V_MAY_DEF's of global variables,
 131    but we still must avoid moving them around.  */
 132
 133 bool
 134 is_hidden_global_store (tree stmt)
 135 {
 136   stmt_ann_t ann = stmt_ann (stmt);
 137   v_may_def_optype v_may_defs;
 138   v_must_def_optype v_must_defs;
 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   v_may_defs = V_MAY_DEF_OPS (ann);
 144   v_must_defs = V_MUST_DEF_OPS (ann);
 145   if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
 146     {
 147       tree lhs;
 148
 149       gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
 150
 151       /* Note that we must not check the individual virtual operands
 152          here.  In particular, if this is an aliased store, we could
 153          end up with something like the following (SSA notation
 154          redacted for brevity):
 155
 156                 foo (int *p, int i)
 157                 {
 158                   int x;
 159                   p_1 = (i_2 > 3) ? &x : p;
 160
 161                   # x_4 = V_MAY_DEF <x_3>
 162                   *p_1 = 5;
 163
 164                   return 2;
 165                 }
 166
 167          Notice that the store to '*p_1' should be preserved, if we
 168          were to check the virtual definitions in that store, we would
 169          not mark it needed.  This is because 'x' is not a global
 170          variable.
 171
 172          Therefore, we check the base address of the LHS.  If the
 173          address is a pointer, we check if its name tag or type tag is
 174          a global variable.  Otherwise, we check if the base variable
 175          is a global.  */
 176       lhs = TREE_OPERAND (stmt, 0);
 177       if (REFERENCE_CLASS_P (lhs))
 178         lhs = get_base_address (lhs);
 179
 180       if (lhs == NULL_TREE)
 181         {
 182           /* If LHS is NULL, it means that we couldn't get the base
 183              address of the reference.  In which case, we should not
 184              move this store.  */
 185           return true;
 186         }
 187       else if (DECL_P (lhs))
 188         {
 189           /* If the store is to a global symbol, we need to keep it.  */
 190           if (is_global_var (lhs))
 191             return true;
 192
 193         }
 194       else if (INDIRECT_REF_P (lhs))
 195         {
 196           tree ptr = TREE_OPERAND (lhs, 0);
 197           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 198           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 199           tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 200
 201           /* If either the name tag or the type tag for PTR is a
 202              global variable, then the store is necessary.  */
 203           if ((nmt && is_global_var (nmt))
 204               || (tmt && is_global_var (tmt)))
 205             {
 206               return true;
 207             }
 208         }
 209       else
 210         gcc_unreachable ();
 211     }
 212   return false;
 213 }
 214
 215 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 216
 217 static basic_block
 218 nearest_common_dominator_of_uses (dataflow_t imm)
 219 {
 220   bitmap blocks = BITMAP_ALLOC (NULL);
 221   basic_block commondom;
 222   int i;
 223   unsigned int j;
 224   bitmap_iterator bi;
 225   bitmap_clear (blocks);
 226   for (i = 0; i < num_immediate_uses (imm); i++)
 227     {
 228       tree usestmt = immediate_use (imm, i);
 229       basic_block useblock;
 230       if (TREE_CODE (usestmt) == PHI_NODE)
 231         {
 232           int j;
 233           for (j = 0; j < PHI_NUM_ARGS (usestmt); j++)
 234             {
 235               useblock = PHI_ARG_EDGE (usestmt, j)->src;
 236               /* Short circuit. Nothing dominates the entry block.  */
 237               if (useblock == ENTRY_BLOCK_PTR)
 238                 {
 239                   BITMAP_FREE (blocks);
 240                   return NULL;
 241                 }
 242               bitmap_set_bit (blocks, useblock->index);
 243             }
 244         }
 245       else
 246         {
 247           useblock = bb_for_stmt (usestmt);
 248
 249           /* Short circuit. Nothing dominates the entry block.  */
 250           if (useblock == ENTRY_BLOCK_PTR)
 251             {
 252               BITMAP_FREE (blocks);
 253               return NULL;
 254             }
 255           bitmap_set_bit (blocks, useblock->index);
 256         }
 257     }
 258   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 259   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 260     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 261                                           BASIC_BLOCK (j));
 262   BITMAP_FREE (blocks);
 263   return commondom;
 264 }
 265
 266 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 267    determine the location to sink the statement to, if any.
 268    Return the basic block to sink it to, or NULL if we should not sink
 269    it.  */
 270
 271 static tree
 272 statement_sink_location (tree stmt, basic_block frombb)
 273 {
 274   dataflow_t imm = get_immediate_uses (stmt);
 275   tree use, def;
 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
 283   if (imm == NULL)
 284     return NULL;
 285
 286   if (TREE_CODE (stmt) != MODIFY_EXPR)
 287     return NULL;
 288   rhs = TREE_OPERAND (stmt, 1);
 289
 290   /* There are a few classes of things we can't or don't move, some because we
 291      don't have code to handle it, some because it's not profitable and some
 292      because it's not legal.
 293
 294      We can't sink things that may be global stores, at least not without
 295      calculating a lot more information, because we may cause it to no longer
 296      be seen by an external routine that needs it depending on where it gets
 297      moved to.
 298
 299      We don't want to sink loads from memory.
 300
 301      We can't sink statements that end basic blocks without splitting the
 302      incoming edge for the sink location to place it there.
 303
 304      We can't sink statements that have volatile operands.
 305
 306      We don't want to sink dead code, so anything with 0 immediate uses is not
 307      sunk.
 308
 309   */
 310   ann = stmt_ann (stmt);
 311   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) != 0
 312       || stmt_ends_bb_p (stmt)
 313       || TREE_SIDE_EFFECTS (rhs)
 314       || TREE_CODE (rhs) == EXC_PTR_EXPR
 315       || TREE_CODE (rhs) == FILTER_EXPR
 316       || is_hidden_global_store (stmt)
 317       || ann->has_volatile_ops
 318       || num_immediate_uses (imm) == 0)
 319     return NULL;
 320
 321   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 322     {
 323       tree def = DEF_FROM_PTR (def_p);
 324       if (is_global_var (SSA_NAME_VAR (def))
 325           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 326         return NULL;
 327     }
 328
 329   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 330     {
 331       tree use = USE_FROM_PTR (use_p);
 332       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 333         return NULL;
 334     }
 335
 336   /* If all the immediate uses are not in the same place, find the nearest
 337      common dominator of all the immediate uses.  For PHI nodes, we have to
 338      find the nearest common dominator of all of the predecessor blocks, since
 339      that is where insertion would have to take place.  */
 340   if (!all_immediate_uses_same_place (imm))
 341     {
 342       basic_block commondom = nearest_common_dominator_of_uses (imm);
 343
 344       if (commondom == frombb)
 345         return NULL;
 346
 347       /* Our common dominator has to be dominated by frombb in order to be a
 348          trivially safe place to put this statement, since it has multiple
 349          uses.  */
 350       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 351         return NULL;
 352
 353       /* It doesn't make sense to move to a dominator that post-dominates
 354          frombb, because it means we've just moved it into a path that always
 355          executes if frombb executes, instead of reducing the number of
 356          executions .  */
 357       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 358         {
 359           if (dump_file && (dump_flags & TDF_DETAILS))
 360             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 361           return NULL;
 362         }
 363
 364       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 365         return NULL;
 366       if (dump_file && (dump_flags & TDF_DETAILS))
 367         {
 368           fprintf (dump_file, "Common dominator of all uses is %d\n",
 369                    commondom->index);
 370         }
 371       return first_stmt (commondom);
 372     }
 373
 374   use = immediate_use (imm, 0);
 375   if (TREE_CODE (use) != PHI_NODE)
 376     {
 377       sinkbb = bb_for_stmt (use);
 378       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 379           || sinkbb->loop_father != frombb->loop_father)
 380         return NULL;
 381       return use;
 382     }
 383
 384   /* Note that at this point, all uses must be in the same statement, so it
 385      doesn't matter which def op we choose.  */
 386   if (STMT_DEF_OPS (stmt) == NULL)
 387     {
 388       if (STMT_V_MAY_DEF_OPS (stmt) != NULL)
 389         def = V_MAY_DEF_RESULT (STMT_V_MAY_DEF_OPS (stmt), 0);
 390       else if (STMT_V_MUST_DEF_OPS (stmt) != NULL)
 391         def = V_MUST_DEF_RESULT (STMT_V_MUST_DEF_OPS (stmt), 0);
 392       else
 393         gcc_unreachable ();
 394     }
 395   else
 396     def = DEF_OP (STMT_DEF_OPS (stmt), 0);
 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       get_stmt_operands (stmt);
 445
 446       sinkstmt = statement_sink_location (stmt, bb);
 447       if (!sinkstmt)
 448         {
 449           if (!bsi_end_p (bsi))
 450             bsi_prev (&bsi);
 451           continue;
 452         }
 453       if (dump_file)
 454         {
 455           fprintf (dump_file, "Sinking ");
 456           print_generic_expr (dump_file, stmt, TDF_VOPS);
 457           fprintf (dump_file, " from bb %d to bb %d\n",
 458                    bb->index, bb_for_stmt (sinkstmt)->index);
 459         }
 460       tobsi = bsi_for_stmt (sinkstmt);
 461       /* Find the first non-label.  */
 462       while (!bsi_end_p (tobsi)
 463              && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
 464         bsi_next (&tobsi);
 465
 466       /* If this is the end of the basic block, we need to insert at the end
 467          of the basic block.  */
 468       if (bsi_end_p (tobsi))
 469         bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
 470       else
 471         bsi_move_before (&bsi, &tobsi);
 472
 473       sink_stats.sunk++;
 474       if (!bsi_end_p (bsi))
 475         bsi_prev (&bsi);
 476
 477     }
 478  earlyout:
 479   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 480        son;
 481        son = next_dom_son (CDI_POST_DOMINATORS, son))
 482     {
 483       sink_code_in_bb (son);
 484     }
 485 }
 486
 487 /* Perform code sinking.
 488    This moves code down the flowgraph when we know it would be
 489    profitable to do so, or it wouldn't increase the number of
 490    executions of the statement.
 491
 492    IE given
 493
 494    a_1 = b + c;
 495    if (<something>)
 496    {
 497    }
 498    else
 499    {
 500      foo (&b, &c);
 501      a_5 = b + c;
 502    }
 503    a_6 = PHI (a_5, a_1);
 504    USE a_6.
 505
 506    we'll transform this into:
 507
 508    if (<something>)
 509    {
 510       a_1 = b + c;
 511    }
 512    else
 513    {
 514       foo (&b, &c);
 515       a_5 = b + c;
 516    }
 517    a_6 = PHI (a_5, a_1);
 518    USE a_6.
 519
 520    Note that this reduces the number of computations of a = b + c to 1
 521    when we take the else edge, instead of 2.
 522 */
 523 static void
 524 execute_sink_code (void)
 525 {
 526   struct loops *loops = loop_optimizer_init (dump_file);
 527   connect_infinite_loops_to_exit ();
 528   memset (&sink_stats, 0, sizeof (sink_stats));
 529   calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
 530   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 531   sink_code_in_bb (EXIT_BLOCK_PTR);
 532   if (dump_file && (dump_flags & TDF_STATS))
 533     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 534   free_dominance_info (CDI_POST_DOMINATORS);
 535   remove_fake_exit_edges ();
 536   free_df ();
 537   loop_optimizer_finalize (loops, dump_file);
 538 }
 539
 540 /* Gate and execute functions for PRE.  */
 541
 542 static void
 543 do_sink (void)
 544 {
 545   execute_sink_code ();
 546 }
 547
 548 static bool
 549 gate_sink (void)
 550 {
 551   return flag_tree_sink != 0;
 552 }
 553
 554 struct tree_opt_pass pass_sink_code =
 555 {
 556   "sink",                               /* name */
 557   gate_sink,                            /* gate */
 558   do_sink,                              /* execute */
 559   NULL,                                 /* sub */
 560   NULL,                                 /* next */
 561   0,                                    /* static_pass_number */
 562   TV_TREE_SINK,                         /* tv_id */
 563   PROP_no_crit_edges | PROP_cfg
 564     | PROP_ssa | PROP_alias,            /* properties_required */
 565   0,                                    /* properties_provided */
 566   0,                                    /* properties_destroyed */
 567   0,                                    /* todo_flags_start */
 568   TODO_rename_vars | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
 569   0                                     /* letter */
 570 };