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 its 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 (tree stmt)
 113 {
 114   tree firstuse = NULL_TREE;
 115   ssa_op_iter op_iter;
 116   imm_use_iterator imm_iter;
 117   use_operand_p use_p;
 118   tree var;
 119
 120   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 121     {
 122       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 123         {
 124           if (firstuse == NULL_TREE)
 125             firstuse = USE_STMT (use_p);
 126           else
 127             if (firstuse != USE_STMT (use_p))
 128               return false;
 129         }
 130     }
 131
 132   return true;
 133 }
 134
 135 /* Some global stores don't necessarily have V_MAY_DEF's of global variables,
 136    but we still must avoid moving them around.  */
 137
 138 bool
 139 is_hidden_global_store (tree stmt)
 140 {
 141   /* Check virtual definitions.  If we get here, the only virtual
 142      definitions we should see are those generated by assignment
 143      statements.  */
 144   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 145     {
 146       tree lhs;
 147
 148       gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
 149
 150       /* Note that we must not check the individual virtual operands
 151          here.  In particular, if this is an aliased store, we could
 152          end up with something like the following (SSA notation
 153          redacted for brevity):
 154
 155                 foo (int *p, int i)
 156                 {
 157                   int x;
 158                   p_1 = (i_2 > 3) ? &x : p;
 159
 160                   # x_4 = V_MAY_DEF <x_3>
 161                   *p_1 = 5;
 162
 163                   return 2;
 164                 }
 165
 166          Notice that the store to '*p_1' should be preserved, if we
 167          were to check the virtual definitions in that store, we would
 168          not mark it needed.  This is because 'x' is not a global
 169          variable.
 170
 171          Therefore, we check the base address of the LHS.  If the
 172          address is a pointer, we check if its name tag or type tag is
 173          a global variable.  Otherwise, we check if the base variable
 174          is a global.  */
 175       lhs = TREE_OPERAND (stmt, 0);
 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         {
 195           tree ptr = TREE_OPERAND (lhs, 0);
 196           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 197           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 198           tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 199
 200           /* If either the name tag or the type tag for PTR is a
 201              global variable, then the store is necessary.  */
 202           if ((nmt && is_global_var (nmt))
 203               || (tmt && is_global_var (tmt)))
 204             {
 205               return true;
 206             }
 207         }
 208       else
 209         gcc_unreachable ();
 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    Return the basic block to sink it to, or NULL if we should not sink
 267    it.  */
 268
 269 static tree
 270 statement_sink_location (tree stmt, basic_block frombb)
 271 {
 272   tree use, def;
 273   use_operand_p one_use = NULL_USE_OPERAND_P;
 274   basic_block sinkbb;
 275   use_operand_p use_p;
 276   def_operand_p def_p;
 277   ssa_op_iter iter;
 278   stmt_ann_t ann;
 279   tree rhs;
 280   imm_use_iterator imm_iter;
 281
 282   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 283     {
 284       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 285         {
 286           break;
 287         }
 288       if (one_use != NULL_USE_OPERAND_P)
 289         break;
 290     }
 291
 292   /* Return if there are no immediate uses of this stmt.  */
 293   if (one_use == NULL_USE_OPERAND_P)
 294     return NULL;
 295
 296   if (TREE_CODE (stmt) != MODIFY_EXPR)
 297     return NULL;
 298   rhs = TREE_OPERAND (stmt, 1);
 299
 300   /* There are a few classes of things we can't or don't move, some because we
 301      don't have code to handle it, some because it's not profitable and some
 302      because it's not legal.
 303
 304      We can't sink things that may be global stores, at least not without
 305      calculating a lot more information, because we may cause it to no longer
 306      be seen by an external routine that needs it depending on where it gets
 307      moved to.
 308
 309      We don't want to sink loads from memory.
 310
 311      We can't sink statements that end basic blocks without splitting the
 312      incoming edge for the sink location to place it there.
 313
 314      We can't sink statements that have volatile operands.
 315
 316      We don't want to sink dead code, so anything with 0 immediate uses is not
 317      sunk.
 318
 319   */
 320   ann = stmt_ann (stmt);
 321   if (stmt_ends_bb_p (stmt)
 322       || TREE_SIDE_EFFECTS (rhs)
 323       || TREE_CODE (rhs) == EXC_PTR_EXPR
 324       || TREE_CODE (rhs) == FILTER_EXPR
 325       || is_hidden_global_store (stmt)
 326       || ann->has_volatile_ops
 327       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 328     return NULL;
 329
 330   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 331     {
 332       tree def = DEF_FROM_PTR (def_p);
 333       if (is_global_var (SSA_NAME_VAR (def))
 334           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 335         return NULL;
 336     }
 337
 338   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 339     {
 340       tree use = USE_FROM_PTR (use_p);
 341       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 342         return NULL;
 343     }
 344
 345   /* If all the immediate uses are not in the same place, find the nearest
 346      common dominator of all the immediate uses.  For PHI nodes, we have to
 347      find the nearest common dominator of all of the predecessor blocks, since
 348      that is where insertion would have to take place.  */
 349   if (!all_immediate_uses_same_place (stmt))
 350     {
 351       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 352
 353       if (commondom == frombb)
 354         return NULL;
 355
 356       /* Our common dominator has to be dominated by frombb in order to be a
 357          trivially safe place to put this statement, since it has multiple
 358          uses.  */
 359       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 360         return NULL;
 361
 362       /* It doesn't make sense to move to a dominator that post-dominates
 363          frombb, because it means we've just moved it into a path that always
 364          executes if frombb executes, instead of reducing the number of
 365          executions .  */
 366       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 367         {
 368           if (dump_file && (dump_flags & TDF_DETAILS))
 369             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 370           return NULL;
 371         }
 372
 373       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 374         return NULL;
 375       if (dump_file && (dump_flags & TDF_DETAILS))
 376         {
 377           fprintf (dump_file, "Common dominator of all uses is %d\n",
 378                    commondom->index);
 379         }
 380       return first_stmt (commondom);
 381     }
 382
 383   use = USE_STMT (one_use);
 384   if (TREE_CODE (use) != PHI_NODE)
 385     {
 386       sinkbb = bb_for_stmt (use);
 387       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 388           || sinkbb->loop_father != frombb->loop_father)
 389         return NULL;
 390       return use;
 391     }
 392
 393   /* Note that at this point, all uses must be in the same statement, so it
 394      doesn't matter which def op we choose, pick the first one.  */
 395   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 396     break;
 397
 398
 399   sinkbb = find_bb_for_arg (use, def);
 400   if (!sinkbb)
 401     return NULL;
 402
 403   /* This will happen when you have
 404      a_3 = PHI <a_13, a_26>
 405
 406      a_26 = V_MAY_DEF <a_3>
 407
 408      If the use is a phi, and is in the same bb as the def,
 409      we can't sink it.  */
 410
 411   if (bb_for_stmt (use) == frombb)
 412     return NULL;
 413   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 414       || sinkbb->loop_father != frombb->loop_father)
 415     return NULL;
 416
 417   return first_stmt (sinkbb);
 418 }
 419
 420 /* Perform code sinking on BB */
 421
 422 static void
 423 sink_code_in_bb (basic_block bb)
 424 {
 425   basic_block son;
 426   block_stmt_iterator bsi;
 427   edge_iterator ei;
 428   edge e;
 429
 430   /* If this block doesn't dominate anything, there can't be any place to sink
 431      the statements to.  */
 432   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 433     goto earlyout;
 434
 435   /* We can't move things across abnormal edges, so don't try.  */
 436   FOR_EACH_EDGE (e, ei, bb->succs)
 437     if (e->flags & EDGE_ABNORMAL)
 438       goto earlyout;
 439
 440   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 441     {
 442       tree stmt = bsi_stmt (bsi);
 443       block_stmt_iterator tobsi;
 444       tree sinkstmt;
 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   sink_code_in_bb (EXIT_BLOCK_PTR);
 531   if (dump_file && (dump_flags & TDF_STATS))
 532     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 533   free_dominance_info (CDI_POST_DOMINATORS);
 534   remove_fake_exit_edges ();
 535   loop_optimizer_finalize (loops, dump_file);
 536 }
 537
 538 /* Gate and execute functions for PRE.  */
 539
 540 static void
 541 do_sink (void)
 542 {
 543   execute_sink_code ();
 544 }
 545
 546 static bool
 547 gate_sink (void)
 548 {
 549   return flag_tree_sink != 0;
 550 }
 551
 552 struct tree_opt_pass pass_sink_code =
 553 {
 554   "sink",                               /* name */
 555   gate_sink,                            /* gate */
 556   do_sink,                              /* execute */
 557   NULL,                                 /* sub */
 558   NULL,                                 /* next */
 559   0,                                    /* static_pass_number */
 560   TV_TREE_SINK,                         /* tv_id */
 561   PROP_no_crit_edges | PROP_cfg
 562     | PROP_ssa | PROP_alias,            /* properties_required */
 563   0,                                    /* properties_provided */
 564   0,                                    /* properties_destroyed */
 565   0,                                    /* todo_flags_start */
 566   TODO_update_ssa
 567     | TODO_dump_func
 568     | TODO_ggc_collect
 569     | TODO_verify_ssa,                  /* todo_flags_finish */
 570   0                                     /* letter */
 571 };