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 V_MAY_DEF'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) == MODIFY_EXPR);
 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 = V_MAY_DEF <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 = TREE_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 = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
 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   return false;
 210 }
 211
 212 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 213
 214 static basic_block
 215 nearest_common_dominator_of_uses (tree stmt)
 216 {
 217   bitmap blocks = BITMAP_ALLOC (NULL);
 218   basic_block commondom;
 219   unsigned int j;
 220   bitmap_iterator bi;
 221   ssa_op_iter op_iter;
 222   imm_use_iterator imm_iter;
 223   use_operand_p use_p;
 224   tree var;
 225
 226   bitmap_clear (blocks);
 227   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 228     {
 229       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 230         {
 231           tree usestmt = USE_STMT (use_p);
 232           basic_block useblock;
 233
 234           if (TREE_CODE (usestmt) == PHI_NODE)
 235             {
 236               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 237
 238               useblock = PHI_ARG_EDGE (usestmt, idx)->src;
 239             }
 240           else
 241             {
 242               useblock = bb_for_stmt (usestmt);
 243             }
 244
 245           /* Short circuit. Nothing dominates the entry block.  */
 246           if (useblock == ENTRY_BLOCK_PTR)
 247             {
 248               BITMAP_FREE (blocks);
 249               return NULL;
 250             }
 251           bitmap_set_bit (blocks, useblock->index);
 252         }
 253     }
 254   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 255   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 256     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 257                                           BASIC_BLOCK (j));
 258   BITMAP_FREE (blocks);
 259   return commondom;
 260 }
 261
 262 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 263    determine the location to sink the statement to, if any.
 264    Return the basic block to sink it to, or NULL if we should not sink
 265    it.  */
 266
 267 static tree
 268 statement_sink_location (tree stmt, basic_block frombb)
 269 {
 270   tree use, def;
 271   use_operand_p one_use = NULL_USE_OPERAND_P;
 272   basic_block sinkbb;
 273   use_operand_p use_p;
 274   def_operand_p def_p;
 275   ssa_op_iter iter;
 276   stmt_ann_t ann;
 277   tree rhs;
 278   imm_use_iterator imm_iter;
 279
 280   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 281     {
 282       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 283         {
 284           break;
 285         }
 286       if (one_use != NULL_USE_OPERAND_P)
 287         break;
 288     }
 289
 290   /* Return if there are no immediate uses of this stmt.  */
 291   if (one_use == NULL_USE_OPERAND_P)
 292     return NULL;
 293
 294   if (TREE_CODE (stmt) != MODIFY_EXPR)
 295     return NULL;
 296   rhs = TREE_OPERAND (stmt, 1);
 297
 298   /* There are a few classes of things we can't or don't move, some because we
 299      don't have code to handle it, some because it's not profitable and some
 300      because it's not legal.
 301
 302      We can't sink things that may be global stores, at least not without
 303      calculating a lot more information, because we may cause it to no longer
 304      be seen by an external routine that needs it depending on where it gets
 305      moved to.
 306
 307      We don't want to sink loads from memory.
 308
 309      We can't sink statements that end basic blocks without splitting the
 310      incoming edge for the sink location to place it there.
 311
 312      We can't sink statements that have volatile operands.
 313
 314      We don't want to sink dead code, so anything with 0 immediate uses is not
 315      sunk.
 316
 317   */
 318   ann = stmt_ann (stmt);
 319   if (stmt_ends_bb_p (stmt)
 320       || TREE_SIDE_EFFECTS (rhs)
 321       || TREE_CODE (rhs) == EXC_PTR_EXPR
 322       || TREE_CODE (rhs) == FILTER_EXPR
 323       || is_hidden_global_store (stmt)
 324       || ann->has_volatile_ops
 325       || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
 326     return NULL;
 327
 328   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 329     {
 330       tree def = DEF_FROM_PTR (def_p);
 331       if (is_global_var (SSA_NAME_VAR (def))
 332           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 333         return NULL;
 334     }
 335
 336   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 337     {
 338       tree use = USE_FROM_PTR (use_p);
 339       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 340         return NULL;
 341     }
 342
 343   /* If all the immediate uses are not in the same place, find the nearest
 344      common dominator of all the immediate uses.  For PHI nodes, we have to
 345      find the nearest common dominator of all of the predecessor blocks, since
 346      that is where insertion would have to take place.  */
 347   if (!all_immediate_uses_same_place (stmt))
 348     {
 349       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 350
 351       if (commondom == frombb)
 352         return NULL;
 353
 354       /* Our common dominator has to be dominated by frombb in order to be a
 355          trivially safe place to put this statement, since it has multiple
 356          uses.  */
 357       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 358         return NULL;
 359
 360       /* It doesn't make sense to move to a dominator that post-dominates
 361          frombb, because it means we've just moved it into a path that always
 362          executes if frombb executes, instead of reducing the number of
 363          executions .  */
 364       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 365         {
 366           if (dump_file && (dump_flags & TDF_DETAILS))
 367             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 368           return NULL;
 369         }
 370
 371       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 372         return NULL;
 373       if (dump_file && (dump_flags & TDF_DETAILS))
 374         {
 375           fprintf (dump_file, "Common dominator of all uses is %d\n",
 376                    commondom->index);
 377         }
 378       return first_stmt (commondom);
 379     }
 380
 381   use = USE_STMT (one_use);
 382   if (TREE_CODE (use) != PHI_NODE)
 383     {
 384       sinkbb = bb_for_stmt (use);
 385       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 386           || sinkbb->loop_father != frombb->loop_father)
 387         return NULL;
 388       return use;
 389     }
 390
 391   /* Note that at this point, all uses must be in the same statement, so it
 392      doesn't matter which def op we choose, pick the first one.  */
 393   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 394     break;
 395
 396
 397   sinkbb = find_bb_for_arg (use, def);
 398   if (!sinkbb)
 399     return NULL;
 400
 401   /* This will happen when you have
 402      a_3 = PHI <a_13, a_26>
 403
 404      a_26 = V_MAY_DEF <a_3>
 405
 406      If the use is a phi, and is in the same bb as the def,
 407      we can't sink it.  */
 408
 409   if (bb_for_stmt (use) == frombb)
 410     return NULL;
 411   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 412       || sinkbb->loop_father != frombb->loop_father)
 413     return NULL;
 414
 415   return first_stmt (sinkbb);
 416 }
 417
 418 /* Perform code sinking on BB */
 419
 420 static void
 421 sink_code_in_bb (basic_block bb)
 422 {
 423   basic_block son;
 424   block_stmt_iterator bsi;
 425   edge_iterator ei;
 426   edge e;
 427
 428   /* If this block doesn't dominate anything, there can't be any place to sink
 429      the statements to.  */
 430   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 431     goto earlyout;
 432
 433   /* We can't move things across abnormal edges, so don't try.  */
 434   FOR_EACH_EDGE (e, ei, bb->succs)
 435     if (e->flags & EDGE_ABNORMAL)
 436       goto earlyout;
 437
 438   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 439     {
 440       tree stmt = bsi_stmt (bsi);
 441       block_stmt_iterator tobsi;
 442       tree sinkstmt;
 443
 444       sinkstmt = statement_sink_location (stmt, bb);
 445       if (!sinkstmt)
 446         {
 447           if (!bsi_end_p (bsi))
 448             bsi_prev (&bsi);
 449           continue;
 450         }
 451       if (dump_file)
 452         {
 453           fprintf (dump_file, "Sinking ");
 454           print_generic_expr (dump_file, stmt, TDF_VOPS);
 455           fprintf (dump_file, " from bb %d to bb %d\n",
 456                    bb->index, bb_for_stmt (sinkstmt)->index);
 457         }
 458       tobsi = bsi_for_stmt (sinkstmt);
 459       /* Find the first non-label.  */
 460       while (!bsi_end_p (tobsi)
 461              && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
 462         bsi_next (&tobsi);
 463
 464       /* If this is the end of the basic block, we need to insert at the end
 465          of the basic block.  */
 466       if (bsi_end_p (tobsi))
 467         bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
 468       else
 469         bsi_move_before (&bsi, &tobsi);
 470
 471       sink_stats.sunk++;
 472       if (!bsi_end_p (bsi))
 473         bsi_prev (&bsi);
 474
 475     }
 476  earlyout:
 477   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 478        son;
 479        son = next_dom_son (CDI_POST_DOMINATORS, son))
 480     {
 481       sink_code_in_bb (son);
 482     }
 483 }
 484
 485 /* Perform code sinking.
 486    This moves code down the flowgraph when we know it would be
 487    profitable to do so, or it wouldn't increase the number of
 488    executions of the statement.
 489
 490    IE given
 491
 492    a_1 = b + c;
 493    if (<something>)
 494    {
 495    }
 496    else
 497    {
 498      foo (&b, &c);
 499      a_5 = b + c;
 500    }
 501    a_6 = PHI (a_5, a_1);
 502    USE a_6.
 503
 504    we'll transform this into:
 505
 506    if (<something>)
 507    {
 508       a_1 = b + c;
 509    }
 510    else
 511    {
 512       foo (&b, &c);
 513       a_5 = b + c;
 514    }
 515    a_6 = PHI (a_5, a_1);
 516    USE a_6.
 517
 518    Note that this reduces the number of computations of a = b + c to 1
 519    when we take the else edge, instead of 2.
 520 */
 521 static void
 522 execute_sink_code (void)
 523 {
 524   struct loops *loops = loop_optimizer_init (LOOPS_NORMAL);
 525
 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);
 535 }
 536
 537 /* Gate and execute functions for PRE.  */
 538
 539 static unsigned int
 540 do_sink (void)
 541 {
 542   execute_sink_code ();
 543   return 0;
 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 };