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 (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 j;
 244               for (j = 0; j < PHI_NUM_ARGS (usestmt); j++)
 245                 {
 246                   useblock = PHI_ARG_EDGE (usestmt, j)->src;
 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           else
 257             {
 258               useblock = bb_for_stmt (usestmt);
 259
 260               /* Short circuit. Nothing dominates the entry block.  */
 261               if (useblock == ENTRY_BLOCK_PTR)
 262                 {
 263                   BITMAP_FREE (blocks);
 264                   return NULL;
 265                 }
 266               bitmap_set_bit (blocks, useblock->index);
 267             }
 268         }
 269     }
 270   commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
 271   EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
 272     commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
 273                                           BASIC_BLOCK (j));
 274   BITMAP_FREE (blocks);
 275   return commondom;
 276 }
 277
 278 /* Given a statement (STMT) and the basic block it is currently in (FROMBB),
 279    determine the location to sink the statement to, if any.
 280    Return the basic block to sink it to, or NULL if we should not sink
 281    it.  */
 282
 283 static tree
 284 statement_sink_location (tree stmt, basic_block frombb)
 285 {
 286   tree use, def;
 287   use_operand_p one_use = NULL_USE_OPERAND_P;
 288   basic_block sinkbb;
 289   use_operand_p use_p;
 290   def_operand_p def_p;
 291   ssa_op_iter iter;
 292   stmt_ann_t ann;
 293   tree rhs;
 294   imm_use_iterator imm_iter;
 295
 296   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
 297     {
 298       FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
 299         {
 300           break;
 301         }
 302       if (one_use != NULL_USE_OPERAND_P)
 303         break;
 304     }
 305
 306   /* Return if there are no immediate uses of this stmt.  */
 307   if (one_use == NULL_USE_OPERAND_P)
 308     return NULL;
 309
 310   if (TREE_CODE (stmt) != MODIFY_EXPR)
 311     return NULL;
 312   rhs = TREE_OPERAND (stmt, 1);
 313
 314   /* There are a few classes of things we can't or don't move, some because we
 315      don't have code to handle it, some because it's not profitable and some
 316      because it's not legal.
 317
 318      We can't sink things that may be global stores, at least not without
 319      calculating a lot more information, because we may cause it to no longer
 320      be seen by an external routine that needs it depending on where it gets
 321      moved to.
 322
 323      We don't want to sink loads from memory.
 324
 325      We can't sink statements that end basic blocks without splitting the
 326      incoming edge for the sink location to place it there.
 327
 328      We can't sink statements that have volatile operands.
 329
 330      We don't want to sink dead code, so anything with 0 immediate uses is not
 331      sunk.
 332
 333   */
 334   ann = stmt_ann (stmt);
 335   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) != 0
 336       || stmt_ends_bb_p (stmt)
 337       || TREE_SIDE_EFFECTS (rhs)
 338       || TREE_CODE (rhs) == EXC_PTR_EXPR
 339       || TREE_CODE (rhs) == FILTER_EXPR
 340       || is_hidden_global_store (stmt)
 341       || ann->has_volatile_ops)
 342     return NULL;
 343
 344   FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
 345     {
 346       tree def = DEF_FROM_PTR (def_p);
 347       if (is_global_var (SSA_NAME_VAR (def))
 348           || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
 349         return NULL;
 350     }
 351
 352   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 353     {
 354       tree use = USE_FROM_PTR (use_p);
 355       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
 356         return NULL;
 357     }
 358
 359   /* If all the immediate uses are not in the same place, find the nearest
 360      common dominator of all the immediate uses.  For PHI nodes, we have to
 361      find the nearest common dominator of all of the predecessor blocks, since
 362      that is where insertion would have to take place.  */
 363   if (!all_immediate_uses_same_place (stmt))
 364     {
 365       basic_block commondom = nearest_common_dominator_of_uses (stmt);
 366
 367       if (commondom == frombb)
 368         return NULL;
 369
 370       /* Our common dominator has to be dominated by frombb in order to be a
 371          trivially safe place to put this statement, since it has multiple
 372          uses.  */
 373       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 374         return NULL;
 375
 376       /* It doesn't make sense to move to a dominator that post-dominates
 377          frombb, because it means we've just moved it into a path that always
 378          executes if frombb executes, instead of reducing the number of
 379          executions .  */
 380       if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
 381         {
 382           if (dump_file && (dump_flags & TDF_DETAILS))
 383             fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
 384           return NULL;
 385         }
 386
 387       if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
 388         return NULL;
 389       if (dump_file && (dump_flags & TDF_DETAILS))
 390         {
 391           fprintf (dump_file, "Common dominator of all uses is %d\n",
 392                    commondom->index);
 393         }
 394       return first_stmt (commondom);
 395     }
 396
 397   use = USE_STMT (one_use);
 398   if (TREE_CODE (use) != PHI_NODE)
 399     {
 400       sinkbb = bb_for_stmt (use);
 401       if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 402           || sinkbb->loop_father != frombb->loop_father)
 403         return NULL;
 404       return use;
 405     }
 406
 407   /* Note that at this point, all uses must be in the same statement, so it
 408      doesn't matter which def op we choose.  */
 409   if (STMT_DEF_OPS (stmt) == NULL)
 410     {
 411       if (STMT_V_MAY_DEF_OPS (stmt) != NULL)
 412         def = V_MAY_DEF_RESULT (STMT_V_MAY_DEF_OPS (stmt), 0);
 413       else if (STMT_V_MUST_DEF_OPS (stmt) != NULL)
 414         def = V_MUST_DEF_RESULT (STMT_V_MUST_DEF_OPS (stmt), 0);
 415       else
 416         gcc_unreachable ();
 417     }
 418   else
 419     def = DEF_OP (STMT_DEF_OPS (stmt), 0);
 420
 421   sinkbb = find_bb_for_arg (use, def);
 422   if (!sinkbb)
 423     return NULL;
 424
 425   /* This will happen when you have
 426      a_3 = PHI <a_13, a_26>
 427
 428      a_26 = V_MAY_DEF <a_3>
 429
 430      If the use is a phi, and is in the same bb as the def,
 431      we can't sink it.  */
 432
 433   if (bb_for_stmt (use) == frombb)
 434     return NULL;
 435   if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
 436       || sinkbb->loop_father != frombb->loop_father)
 437     return NULL;
 438
 439   return first_stmt (sinkbb);
 440 }
 441
 442 /* Perform code sinking on BB */
 443
 444 static void
 445 sink_code_in_bb (basic_block bb)
 446 {
 447   basic_block son;
 448   block_stmt_iterator bsi;
 449   edge_iterator ei;
 450   edge e;
 451
 452   /* If this block doesn't dominate anything, there can't be any place to sink
 453      the statements to.  */
 454   if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
 455     goto earlyout;
 456
 457   /* We can't move things across abnormal edges, so don't try.  */
 458   FOR_EACH_EDGE (e, ei, bb->succs)
 459     if (e->flags & EDGE_ABNORMAL)
 460       goto earlyout;
 461
 462   for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
 463     {
 464       tree stmt = bsi_stmt (bsi);
 465       block_stmt_iterator tobsi;
 466       tree sinkstmt;
 467       get_stmt_operands (stmt);
 468
 469       sinkstmt = statement_sink_location (stmt, bb);
 470       if (!sinkstmt)
 471         {
 472           if (!bsi_end_p (bsi))
 473             bsi_prev (&bsi);
 474           continue;
 475         }
 476       if (dump_file)
 477         {
 478           fprintf (dump_file, "Sinking ");
 479           print_generic_expr (dump_file, stmt, TDF_VOPS);
 480           fprintf (dump_file, " from bb %d to bb %d\n",
 481                    bb->index, bb_for_stmt (sinkstmt)->index);
 482         }
 483       tobsi = bsi_for_stmt (sinkstmt);
 484       /* Find the first non-label.  */
 485       while (!bsi_end_p (tobsi)
 486              && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
 487         bsi_next (&tobsi);
 488
 489       /* If this is the end of the basic block, we need to insert at the end
 490          of the basic block.  */
 491       if (bsi_end_p (tobsi))
 492         bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
 493       else
 494         bsi_move_before (&bsi, &tobsi);
 495
 496       sink_stats.sunk++;
 497       if (!bsi_end_p (bsi))
 498         bsi_prev (&bsi);
 499
 500     }
 501  earlyout:
 502   for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
 503        son;
 504        son = next_dom_son (CDI_POST_DOMINATORS, son))
 505     {
 506       sink_code_in_bb (son);
 507     }
 508 }
 509
 510 /* Perform code sinking.
 511    This moves code down the flowgraph when we know it would be
 512    profitable to do so, or it wouldn't increase the number of
 513    executions of the statement.
 514
 515    IE given
 516
 517    a_1 = b + c;
 518    if (<something>)
 519    {
 520    }
 521    else
 522    {
 523      foo (&b, &c);
 524      a_5 = b + c;
 525    }
 526    a_6 = PHI (a_5, a_1);
 527    USE a_6.
 528
 529    we'll transform this into:
 530
 531    if (<something>)
 532    {
 533       a_1 = b + c;
 534    }
 535    else
 536    {
 537       foo (&b, &c);
 538       a_5 = b + c;
 539    }
 540    a_6 = PHI (a_5, a_1);
 541    USE a_6.
 542
 543    Note that this reduces the number of computations of a = b + c to 1
 544    when we take the else edge, instead of 2.
 545 */
 546 static void
 547 execute_sink_code (void)
 548 {
 549   struct loops *loops = loop_optimizer_init (dump_file);
 550   connect_infinite_loops_to_exit ();
 551   memset (&sink_stats, 0, sizeof (sink_stats));
 552   calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
 553   sink_code_in_bb (EXIT_BLOCK_PTR);
 554   if (dump_file && (dump_flags & TDF_STATS))
 555     fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
 556   free_dominance_info (CDI_POST_DOMINATORS);
 557   remove_fake_exit_edges ();
 558   loop_optimizer_finalize (loops, dump_file);
 559 }
 560
 561 /* Gate and execute functions for PRE.  */
 562
 563 static void
 564 do_sink (void)
 565 {
 566   execute_sink_code ();
 567 }
 568
 569 static bool
 570 gate_sink (void)
 571 {
 572   return flag_tree_sink != 0;
 573 }
 574
 575 struct tree_opt_pass pass_sink_code =
 576 {
 577   "sink",                               /* name */
 578   gate_sink,                            /* gate */
 579   do_sink,                              /* execute */
 580   NULL,                                 /* sub */
 581   NULL,                                 /* next */
 582   0,                                    /* static_pass_number */
 583   TV_TREE_SINK,                         /* tv_id */
 584   PROP_no_crit_edges | PROP_cfg
 585     | PROP_ssa | PROP_alias,            /* properties_required */
 586   0,                                    /* properties_provided */
 587   0,                                    /* properties_destroyed */
 588   0,                                    /* todo_flags_start */
 589   TODO_rename_vars | TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
 590   0                                     /* letter */
 591 };