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   stmt_ann_t ann = stmt_ann (stmt);
 142   v_may_def_optype v_may_defs;
 143   v_must_def_optype v_must_defs;
 144
 145   /* Check virtual definitions.  If we get here, the only virtual
 146      definitions we should see are those generated by assignment
 147      statements.  */
 148   v_may_defs = V_MAY_DEF_OPS (ann);
 149   v_must_defs = V_MUST_DEF_OPS (ann);
 150   if (NUM_V_MAY_DEFS (v_may_defs) > 0 || NUM_V_MUST_DEFS (v_must_defs) > 0)
 151     {
 152       tree lhs;
 153
 154       gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
 155
 156       /* Note that we must not check the individual virtual operands
 157          here.  In particular, if this is an aliased store, we could
 158          end up with something like the following (SSA notation
 159          redacted for brevity):
 160
 161                 foo (int *p, int i)
 162                 {
 163                   int x;
 164                   p_1 = (i_2 > 3) ? &x : p;
 165
 166                   # x_4 = V_MAY_DEF <x_3>
 167                   *p_1 = 5;
 168
 169                   return 2;
 170                 }
 171
 172          Notice that the store to '*p_1' should be preserved, if we
 173          were to check the virtual definitions in that store, we would
 174          not mark it needed.  This is because 'x' is not a global
 175          variable.
 176
 177          Therefore, we check the base address of the LHS.  If the
 178          address is a pointer, we check if its name tag or type tag is
 179          a global variable.  Otherwise, we check if the base variable
 180          is a global.  */
 181       lhs = TREE_OPERAND (stmt, 0);
 182       if (REFERENCE_CLASS_P (lhs))
 183         lhs = get_base_address (lhs);
 184
 185       if (lhs == NULL_TREE)
 186         {
 187           /* If LHS is NULL, it means that we couldn't get the base
 188              address of the reference.  In which case, we should not
 189              move this store.  */
 190           return true;
 191         }
 192       else if (DECL_P (lhs))
 193         {
 194           /* If the store is to a global symbol, we need to keep it.  */
 195           if (is_global_var (lhs))
 196             return true;
 197
 198         }
 199       else if (INDIRECT_REF_P (lhs))
 200         {
 201           tree ptr = TREE_OPERAND (lhs, 0);
 202           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 203           tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
 204           tree tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 205
 206           /* If either the name tag or the type tag for PTR is a
 207              global variable, then the store is necessary.  */
 208           if ((nmt && is_global_var (nmt))
 209               || (tmt && is_global_var (tmt)))
 210             {
 211               return true;
 212             }
 213         }
 214       else
 215         gcc_unreachable ();
 216     }
 217   return false;
 218 }
 219
 220 /* Find the nearest common dominator of all of the immediate uses in IMM.  */
 221
 222 static basic_block
 223 nearest_common_dominator_of_uses (tree stmt)
 224 {
 225   bitmap blocks = BITMAP_ALLOC (NULL);
 226   basic_block commondom;
 227   unsigned int j;
 228   bitmap_iterator bi;
 229   ssa_op_iter op_iter;
 230   imm_use_iterator imm_iter;
 231   use_operand_p use_p;
 232   tree var;
 233
 234   bitmap_clear (blocks);
 235   FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
 236     {
 237       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
 238         {
 239           tree usestmt = USE_STMT (use_p);
 240           basic_block useblock;
 241           if (TREE_CODE (usestmt) == PHI_NODE)
 242             {
 243               int idx = PHI_ARG_INDEX_FROM_USE (use_p);
 244
 245               useblock = PHI_ARG_EDGE (usestmt, idx)->src;
 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           else
 255             {
 256               useblock = bb_for_stmt (usestmt);
 257
 258               /* Short circuit. Nothing dominates the entry block.  */
 259               if (useblock == ENTRY_BLOCK_PTR)
 260                 {
 261                   BITMAP_FREE (blocks);
 262                   return NULL;
 263                 }
 264               bitmap_set_bit (blocks, useblock->index);
 265             }
 266         }
 267     }
 268   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 269   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 270     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 271                                           BASIC_BLOCK (j));
 272   BITMAP_FREE (blocks);
 273   return commondom;
 274 }
 275
 276 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 277    determine the location to sink the statement to, if any.
 278    Return the basic block to sink it to, or NULL if we should not sink
 279    it.  */
 280
 281 static tree
 282 statement_sink_location (tree stmt, basic_block frombb)
 283 {
 284   tree use, def;
 285   use_operand_p one_use = NULL_USE_OPERAND_P;
 286   basic_block sinkbb;
 287   use_operand_p use_p;
 288   def_operand_p def_p;
 289   ssa_op_iter iter;
 290   stmt_ann_t ann;
 291   tree rhs;
 292   imm_use_iterator imm_iter;
 293
 294   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 295     {
 296       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 297         {
 298           break;
 299         }
 300       if (one_use != NULL_USE_OPERAND_P)
 301         break;
 302     }
 303
 304   /* Return if there are no immediate uses of this stmt.  */
 305   if (one_use == NULL_USE_OPERAND_P)
 306     return NULL;
 307
 308   if (TREE_CODE (stmt) != MODIFY_EXPR)
 309     return NULL;
 310   rhs = TREE_OPERAND (stmt, 1);
 311
 312   /* There are a few classes of things we can't or don't move, some because we
 313      don't have code to handle it, some because it's not profitable and some
 314      because it's not legal.
 315
 316      We can't sink things that may be global stores, at least not without
 317      calculating a lot more information, because we may cause it to no longer
 318      be seen by an external routine that needs it depending on where it gets
 319      moved to.
 320
 321      We don't want to sink loads from memory.
 322
 323      We can't sink statements that end basic blocks without splitting the
 324      incoming edge for the sink location to place it there.
 325
 326      We can't sink statements that have volatile operands.
 327
 328      We don't want to sink dead code, so anything with 0 immediate uses is not
 329      sunk.
 330
 331   */
 332   ann = stmt_ann (stmt);
 333   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) != 0
 334       || stmt_ends_bb_p (stmt)
 335       || TREE_SIDE_EFFECTS (rhs)
 336       || TREE_CODE (rhs) == EXC_PTR_EXPR
 337       || TREE_CODE (rhs) == FILTER_EXPR
 338       || is_hidden_global_store (stmt)
 339       || ann->has_volatile_ops)
 340     return NULL;
 341
 342   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 343     {
 344       tree def = DEF_FROM_PTR (def_p);
 345       if (is_global_var (SSA_NAME_VAR (def))
 346           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 347         return NULL;
 348     }
 349
 350   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 351     {
 352       tree use = USE_FROM_PTR (use_p);
 353       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 354         return NULL;
 355     }
 356
 357   /* If all the immediate uses are not in the same place, find the nearest
 358      common dominator of all the immediate uses.  For PHI nodes, we have to
 359      find the nearest common dominator of all of the predecessor blocks, since
 360      that is where insertion would have to take place.  */
 361   if (!all_immediate_uses_same_place (stmt))
 362     {
 363       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 364
 365       if (commondom == frombb)
 366         return NULL;
 367
 368       /* Our common dominator has to be dominated by frombb in order to be a
 369          trivially safe place to put this statement, since it has multiple
 370          uses.  */
 371       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 372         return NULL;
 373
 374       /* It doesn't make sense to move to a dominator that post-dominates
 375          frombb, because it means we've just moved it into a path that always
 376          executes if frombb executes, instead of reducing the number of
 377          executions .  */
 378       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 379         {
 380           if (dump_file && (dump_flags & TDF_DETAILS))
 381             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 382           return NULL;
 383         }
 384
 385       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 386         return NULL;
 387       if (dump_file && (dump_flags & TDF_DETAILS))
 388         {
 389           fprintf (dump_file, "Common dominator of all uses is %d\n",
 390                    commondom->index);
 391         }
 392       return first_stmt (commondom);
 393     }
 394
 395   use = USE_STMT (one_use);
 396   if (TREE_CODE (use) != PHI_NODE)
 397     {
 398       sinkbb = bb_for_stmt (use);
 399       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 400           || sinkbb->loop_father != frombb->loop_father)
 401         return NULL;
 402       return use;
 403     }
 404
 405   /* Note that at this point, all uses must be in the same statement, so it
 406      doesn't matter which def op we choose.  */
 407   if (STMT_DEF_OPS (stmt) == NULL)
 408     {
 409       if (STMT_V_MAY_DEF_OPS (stmt) != NULL)
 410         def = V_MAY_DEF_RESULT (STMT_V_MAY_DEF_OPS (stmt), 0);
 411       else if (STMT_V_MUST_DEF_OPS (stmt) != NULL)
 412         def = V_MUST_DEF_RESULT (STMT_V_MUST_DEF_OPS (stmt), 0);
 413       else
 414         gcc_unreachable ();
 415     }
 416   else
 417     def = DEF_OP (STMT_DEF_OPS (stmt), 0);
 418
 419   sinkbb = find_bb_for_arg (use, def);
 420   if (!sinkbb)
 421     return NULL;
 422
 423   /* This will happen when you have
 424      a_3 = PHI <a_13, a_26>
 425
 426      a_26 = V_MAY_DEF <a_3>
 427
 428      If the use is a phi, and is in the same bb as the def,
 429      we can't sink it.  */
 430
 431   if (bb_for_stmt (use) == frombb)
 432     return NULL;
 433   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 434       || sinkbb->loop_father != frombb->loop_father)
 435     return NULL;
 436
 437   return first_stmt (sinkbb);
 438 }
 439
 440 /* Perform code sinking on BB */
 441
 442 static void
 443 sink_code_in_bb (basic_block bb)
 444 {
 445   basic_block son;
 446   block_stmt_iterator bsi;
 447   edge_iterator ei;
 448   edge e;
 449
 450   /* If this block doesn't dominate anything, there can't be any place to sink
 451      the statements to.  */
 452   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 453     goto earlyout;
 454
 455   /* We can't move things across abnormal edges, so don't try.  */
 456   FOR_EACH_EDGE (e, ei, bb->succs)
 457     if (e->flags & EDGE_ABNORMAL)
 458       goto earlyout;
 459
 460   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 461     {
 462       tree stmt = bsi_stmt (bsi);
 463       block_stmt_iterator tobsi;
 464       tree sinkstmt;
 465
 466       sinkstmt = statement_sink_location (stmt, bb);
 467       if (!sinkstmt)
 468         {
 469           if (!bsi_end_p (bsi))
 470             bsi_prev (&bsi);
 471           continue;
 472         }
 473       if (dump_file)
 474         {
 475           fprintf (dump_file, "Sinking ");
 476           print_generic_expr (dump_file, stmt, TDF_VOPS);
 477           fprintf (dump_file, " from bb %d to bb %d\n",
 478                    bb->index, bb_for_stmt (sinkstmt)->index);
 479         }
 480       tobsi = bsi_for_stmt (sinkstmt);
 481       /* Find the first non-label.  */
 482       while (!bsi_end_p (tobsi)
 483              && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
 484         bsi_next (&tobsi);
 485
 486       /* If this is the end of the basic block, we need to insert at the end
 487          of the basic block.  */
 488       if (bsi_end_p (tobsi))
 489         bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
 490       else
 491         bsi_move_before (&bsi, &tobsi);
 492
 493       sink_stats.sunk++;
 494       if (!bsi_end_p (bsi))
 495         bsi_prev (&bsi);
 496
 497     }
 498  earlyout:
 499   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 500        son;
 501        son = next_dom_son (CDI_POST_DOMINATORS, son))
 502     {
 503       sink_code_in_bb (son);
 504     }
 505 }
 506
 507 /* Perform code sinking.
 508    This moves code down the flowgraph when we know it would be
 509    profitable to do so, or it wouldn't increase the number of
 510    executions of the statement.
 511
 512    IE given
 513
 514    a_1 = b + c;
 515    if (<something>)
 516    {
 517    }
 518    else
 519    {
 520      foo (&b, &c);
 521      a_5 = b + c;
 522    }
 523    a_6 = PHI (a_5, a_1);
 524    USE a_6.
 525
 526    we'll transform this into:
 527
 528    if (<something>)
 529    {
 530       a_1 = b + c;
 531    }
 532    else
 533    {
 534       foo (&b, &c);
 535       a_5 = b + c;
 536    }
 537    a_6 = PHI (a_5, a_1);
 538    USE a_6.
 539
 540    Note that this reduces the number of computations of a = b + c to 1
 541    when we take the else edge, instead of 2.
 542 */
 543 static void
 544 execute_sink_code (void)
 545 {
 546   struct loops *loops = loop_optimizer_init (dump_file);
 547   connect_infinite_loops_to_exit ();
 548   memset (&sink_stats, 0, sizeof (sink_stats));
 549   calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
 550   sink_code_in_bb (EXIT_BLOCK_PTR);
 551   if (dump_file && (dump_flags & TDF_STATS))
 552     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 553   free_dominance_info (CDI_POST_DOMINATORS);
 554   remove_fake_exit_edges ();
 555   loop_optimizer_finalize (loops, dump_file);
 556 }
 557
 558 /* Gate and execute functions for PRE.  */
 559
 560 static void
 561 do_sink (void)
 562 {
 563   execute_sink_code ();
 564 }
 565
 566 static bool
 567 gate_sink (void)
 568 {
 569   return flag_tree_sink != 0;
 570 }
 571
 572 struct tree_opt_pass pass_sink_code =
 573 {
 574   "sink",                               /* name */
 575   gate_sink,                            /* gate */
 576   do_sink,                              /* execute */
 577   NULL,                                 /* sub */
 578   NULL,                                 /* next */
 579   0,                                    /* static_pass_number */
 580   TV_TREE_SINK,                         /* tv_id */
 581   PROP_no_crit_edges | PROP_cfg
 582     | PROP_ssa | PROP_alias,            /* properties_required */
 583   0,                                    /* properties_provided */
 584   0,                                    /* properties_destroyed */
 585   0,                                    /* todo_flags_start */
 586   TODO_update_ssa
 587     | TODO_dump_func
 588     | TODO_ggc_collect
 589     | TODO_verify_ssa,                  /* todo_flags_finish */
 590   0                                     /* letter */
 591 };