gcc/tree-ssa-threadupdate.c

   1 /* Thread edges through blocks and update the control flow and SSA graphs.
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "output.h"
  32 #include "errors.h"
  33 #include "expr.h"
  34 #include "function.h"
  35 #include "diagnostic.h"
  36 #include "tree-flow.h"
  37 #include "tree-dump.h"
  38 #include "tree-pass.h"
  39
  40 /* Given a block B, update the CFG and SSA graph to reflect redirecting
  41    one or more in-edges to B to instead reach the destination of an
  42    out-edge from B while preserving any side effects in B.
  43
  44    i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
  45    side effects of executing B.
  46
  47      1. Make a copy of B (including its outgoing edges and statements).  Call
  48         the copy B'.  Note B' has no incoming edges or PHIs at this time.
  49
  50      2. Remove the control statement at the end of B' and all outgoing edges
  51         except B'->C.
  52
  53      3. Add a new argument to each PHI in C with the same value as the existing
  54         argument associated with edge B->C.  Associate the new PHI arguments
  55         with the edge B'->C.
  56
  57      4. For each PHI in B, find or create a PHI in B' with an identical
  58         PHI_RESULT.  Add an argument to the PHI in B' which has the same
  59         value as the PHI in B associated with the edge A->B.  Associate
  60         the new argument in the PHI in B' with the edge A->B.
  61
  62      5. Change the edge A->B to A->B'.
  63
  64         5a. This automatically deletes any PHI arguments associated with the
  65             edge A->B in B.
  66
  67         5b. This automatically associates each new argument added in step 4
  68             with the edge A->B'.
  69
  70      6. Repeat for other incoming edges into B.
  71
  72      7. Put the duplicated resources in B and all the B' blocks into SSA form.
  73
  74    Note that block duplication can be minimized by first collecting the
  75    the set of unique destination blocks that the incoming edges should
  76    be threaded to.  Block duplication can be further minimized by using
  77    B instead of creating B' for one destination if all edges into B are
  78    going to be threaded to a successor of B.  */
  79
  80
  81 /* Main data structure recording information regarding B's duplicate
  82    blocks.  */
  83
  84 struct redirection_data
  85 {
  86   /* A duplicate of B with the trailing control statement removed and which
  87      targets a single successor of B.  */
  88   basic_block dup_block;
  89
  90   /* An outgoing edge from B.  DUP_BLOCK will have OUTGOING_EDGE->dest as
  91      its single successor.  */
  92   edge outgoing_edge;
  93 };
  94
  95 /* Main data structure to hold information for duplicates of BB.  */
  96 static varray_type redirection_data;
  97
  98 /* Add to the destination of edge E those PHI arguments queued on
  99    E.  */
 100
 101 static void
 102 copy_phis_to_block (edge e)
 103 {
 104   basic_block dest = e->dest;
 105   tree var;
 106
 107   for (var = PENDING_STMT (e); var; var = TREE_CHAIN (var))
 108     {
 109       tree result = TREE_PURPOSE (var);
 110       tree arg = TREE_VALUE (var);
 111       tree new_phi;
 112
 113       /* First try to find a PHI node in NEW_BB which has the same
 114          PHI_RESULT as the PHI from BB we are currently processing.  */
 115       for (new_phi = phi_nodes (dest); new_phi;
 116            new_phi = PHI_CHAIN (new_phi))
 117         if (PHI_RESULT (new_phi) == result)
 118           break;
 119
 120       /* If we did not find a suitable PHI in NEW_BB, create one.  */
 121       if (!new_phi)
 122         new_phi = create_phi_node (result, dest);
 123
 124       /* Now add that same argument to the new PHI node in block NEW_BB.  */
 125       add_phi_arg (&new_phi, arg, e);
 126     }
 127
 128   PENDING_STMT (e) = NULL;
 129 }
 130
 131 /* Remove the last statement in block BB if it is a control statement
 132    Also remove all outgoing edges except the edge which reaches DEST_BB.
 133    If DEST_BB is NULL, then remove all outgoing edges.  */
 134
 135 static void
 136 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
 137 {
 138   block_stmt_iterator bsi;
 139   edge e;
 140   edge_iterator ei;
 141
 142   bsi = bsi_last (bb);
 143
 144   /* If the duplicate ends with a control statement, then remove it.
 145
 146      Note that if we are duplicating the template block rather than the
 147      original basic block, then the duplicate might not have any real
 148      statements in it.  */
 149   if (!bsi_end_p (bsi)
 150       && bsi_stmt (bsi)
 151       && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR
 152           || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR))
 153     bsi_remove (&bsi);
 154
 155   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 156     {
 157       if (e->dest != dest_bb)
 158         ssa_remove_edge (e);
 159       else
 160         ei_next (&ei);
 161     }
 162 }
 163
 164 /* Create a duplicate of BB which only reaches the destination of the edge
 165    stored in RD.  Record the duplicate block in RD.  */
 166
 167 static void
 168 create_block_for_threading (basic_block bb, struct redirection_data *rd)
 169 {
 170   /* We can use the generic block duplication code and simply remove
 171      the stuff we do not need.  */
 172   rd->dup_block = duplicate_block (bb, NULL);
 173
 174   /* Zero out the profile, since the block is unreachable for now.  */
 175   rd->dup_block->frequency = 0;
 176   rd->dup_block->count = 0;
 177
 178   /* The call to duplicate_block will copy everything, including the
 179      useless COND_EXPR or SWITCH_EXPR at the end of BB.  We just remove
 180      the useless COND_EXPR or SWITCH_EXPR here rather than having a
 181      specialized block copier.  We also remove all outgoing edges
 182      from the duplicate block.  The appropriate edge will be created
 183      later.  */
 184   remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
 185 }
 186
 187 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
 188    is reached via one or more specific incoming edges, we know which
 189    outgoing edge from BB will be traversed.
 190
 191    We want to redirect those incoming edges to the target of the
 192    appropriate outgoing edge.  Doing so avoids a conditional branch
 193    and may expose new optimization opportunities.  Note that we have
 194    to update dominator tree and SSA graph after such changes.
 195
 196    The key to keeping the SSA graph update manageable is to duplicate
 197    the side effects occurring in BB so that those side effects still
 198    occur on the paths which bypass BB after redirecting edges.
 199
 200    We accomplish this by creating duplicates of BB and arranging for
 201    the duplicates to unconditionally pass control to one specific
 202    successor of BB.  We then revector the incoming edges into BB to
 203    the appropriate duplicate of BB.
 204
 205    BB and its duplicates will have assignments to the same set of
 206    SSA_NAMEs.  Right now, we just call into rewrite_ssa_into_ssa
 207    to update the SSA graph for those names.
 208
 209    We are also going to experiment with a true incremental update
 210    scheme for the duplicated resources.  One of the interesting
 211    properties we can exploit here is that all the resources set
 212    in BB will have the same IDFS, so we have one IDFS computation
 213    per block with incoming threaded edges, which can lower the
 214    cost of the true incremental update algorithm.  */
 215
 216 static void
 217 thread_block (basic_block bb)
 218 {
 219   /* E is an incoming edge into BB that we may or may not want to
 220      redirect to a duplicate of BB.  */
 221   edge e;
 222   edge_iterator ei;
 223   basic_block template_block;
 224
 225   /* ALL indicates whether or not all incoming edges into BB should
 226      be threaded to a duplicate of BB.  */
 227   bool all = true;
 228
 229   unsigned int i;
 230
 231   VARRAY_GENERIC_PTR_INIT (redirection_data, 2, "redirection data");
 232
 233   /* Look at each incoming edge into BB.  Record each unique outgoing
 234      edge that we want to thread an incoming edge to.  Also note if
 235      all incoming edges are threaded or not.  */
 236   FOR_EACH_EDGE (e, ei, bb->preds)
 237     {
 238       if (!e->aux)
 239         {
 240           all = false;
 241         }
 242       else
 243         {
 244           unsigned int i;
 245
 246           /* See if we can find an entry for the destination of this
 247              threaded edge that has already been recorded.  */
 248           for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 249             {
 250               struct redirection_data *rd;
 251               edge e2;
 252
 253               rd = VARRAY_GENERIC_PTR (redirection_data, i);
 254               e2 = e->aux;
 255
 256               if (e2->dest == rd->outgoing_edge->dest)
 257                 break;
 258             }
 259
 260           /* If the loop did not terminate early, then we have a new
 261              destination for the incoming threaded edges.  Record it.  */
 262           if (i == VARRAY_ACTIVE_SIZE (redirection_data))
 263             {
 264               struct redirection_data *rd;
 265
 266               rd = ggc_alloc_cleared (sizeof (struct redirection_data));
 267               rd->outgoing_edge = e->aux;
 268               VARRAY_PUSH_GENERIC_PTR (redirection_data, rd);
 269             }
 270         }
 271     }
 272
 273   /* Now create duplicates of BB.  Note that if all incoming edges are
 274      threaded, then BB is going to become unreachable.  In that case
 275      we use BB for one of the duplicates rather than wasting memory
 276      duplicating BB.  Thus the odd starting condition for the loop.
 277
 278      Note that for a block with a high outgoing degree we can waste
 279      a lot of time and memory creating and destroying useless edges.
 280
 281      So we first duplicate BB and remove the control structure at the
 282      tail of the duplicate as well as all outgoing edges from the
 283      duplicate.  We then use that duplicate block as a template for
 284      the rest of the duplicates.  */
 285   template_block = NULL;
 286   for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 287     {
 288       struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
 289
 290       if (template_block == NULL)
 291         {
 292           create_block_for_threading (bb, rd);
 293           template_block = rd->dup_block;
 294         }
 295       else
 296         {
 297           create_block_for_threading (template_block, rd);
 298         }
 299     }
 300
 301   /* Now created up edges from the duplicate blocks to their new
 302      destinations.  Doing this as a separate loop after block creation
 303      allows us to avoid creating lots of useless edges.  */
 304   for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 305     {
 306       struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
 307       tree phi;
 308       edge e;
 309
 310       e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
 311
 312       /* If there are any PHI nodes at the destination of the outgoing edge
 313          from the duplicate block, then we will need to add a new argument
 314          to them.  The argument should have the same value as the argument
 315          associated with the outgoing edge stored in RD.  */
 316       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 317         {
 318           int indx = phi_arg_from_edge (phi, rd->outgoing_edge);
 319           add_phi_arg (&phi, PHI_ARG_DEF_TREE (phi, indx), e);
 320         }
 321     }
 322
 323   /* The loop above created the duplicate blocks (and the statements
 324      within the duplicate blocks).  This loop creates PHI nodes for the
 325      duplicated blocks and redirects the incoming edges into BB to reach
 326      the duplicates of BB.
 327
 328      Note that redirecting the edge will change e->pred_next, so we have
 329      to hold e->pred_next in a temporary.
 330
 331      If this turns out to be a performance problem, then we could create
 332      a list of incoming edges associated with each entry in
 333      REDIRECTION_DATA and walk over that list of edges instead.  */
 334   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 335     {
 336       edge new_dest = e->aux;
 337
 338       /* E was not threaded, then there is nothing to do.  */
 339       if (!new_dest)
 340         {
 341           ei_next (&ei);
 342           continue;
 343         }
 344
 345       /* Go ahead and clear E->aux.  It's not needed anymore and failure
 346          to clear it will cause all kinds of unpleasant problems later.  */
 347       e->aux = NULL;
 348
 349       /* We know E is an edge we want to thread.  Find the entry associated
 350          with E's new destination in the REDIRECTION_DATA array.  */
 351       for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 352         {
 353           struct redirection_data *rd;
 354
 355           rd = VARRAY_GENERIC_PTR (redirection_data, i);
 356
 357           /* We have found the right entry if the outgoing edge in this
 358              entry matches E's new destination.  Note that if we have not
 359              created a duplicate block (rd->dup_block is NULL), then we
 360              are going to re-use BB as a duplicate and we do not need
 361              to create PHI nodes or redirect the edge.  */
 362           if (rd->outgoing_edge == new_dest && rd->dup_block)
 363             {
 364               edge e2;
 365
 366               if (dump_file && (dump_flags & TDF_DETAILS))
 367                 fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 368                          e->src->index, e->dest->index, rd->dup_block->index);
 369
 370               e2 = redirect_edge_and_branch (e, rd->dup_block);
 371               copy_phis_to_block (e2);
 372
 373               if ((dump_file && (dump_flags & TDF_DETAILS))
 374                   && e->src != e2->src)
 375               fprintf (dump_file, "    basic block %d created\n",
 376                        e2->src->index);
 377               break;
 378             }
 379         }
 380     }
 381
 382   /* If all the incoming edges where threaded, then we used BB as one
 383      of the duplicate blocks.  We need to fixup BB in that case so that
 384      it no longer has a COND_EXPR or SWITCH_EXPR and reaches one destination
 385      unconditionally.  */
 386   if (all)
 387     {
 388       struct redirection_data *rd;
 389
 390       rd = VARRAY_GENERIC_PTR (redirection_data, 0);
 391
 392       if (dump_file && (dump_flags & TDF_DETAILS))
 393         fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 394                  EDGE_PRED (bb, 0)->src->index, bb->index,
 395                  EDGE_SUCC (bb, 0)->dest->index);
 396
 397       remove_ctrl_stmt_and_useless_edges (bb, rd->outgoing_edge->dest);
 398       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 399       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 400     }
 401
 402   /* Done with this block.  Clear REDIRECTION_DATA.  */
 403   VARRAY_CLEAR (redirection_data);
 404 }
 405
 406 /* Walk through all blocks and thread incoming edges to the block's
 407    destinations as requested.  This is the only entry point into this
 408    file.
 409
 410    Blocks which have one or more incoming edges have INCOMING_EDGE_THREADED
 411    set in the block's annotation.
 412    this routine.
 413
 414    Each edge that should be threaded has the new destination edge stored in
 415    the original edge's AUX field.
 416
 417    This routine (or one of its callees) will clear INCOMING_EDGE_THREADED
 418    in the block annotations and the AUX field in the edges.
 419
 420    It is the caller's responsibility to fix the dominance information
 421    and rewrite duplicated SSA_NAMEs back into SSA form.
 422
 423    Returns true if one or more edges were threaded, false otherwise.  */
 424
 425 bool
 426 thread_through_all_blocks (void)
 427 {
 428   basic_block bb;
 429   bool retval = false;
 430
 431   FOR_EACH_BB (bb)
 432     {
 433       if (bb_ann (bb)->incoming_edge_threaded)
 434         {
 435           thread_block (bb);
 436           retval = true;
 437           bb_ann (bb)->incoming_edge_threaded = false;
 438         }
 439     }
 440   return retval;
 441 }