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 /* For each PHI node in BB, find or create a PHI node in NEW_BB for the
  99    same PHI_RESULT.  Add an argument to the PHI node in NEW_BB which
 100    corresponds to the same PHI argument associated with edge E in BB.  */
 101
 102 static void
 103 copy_phis_to_block (basic_block new_bb, basic_block bb, edge e)
 104 {
 105   tree phi, arg;
 106
 107   /* Walk over every PHI in BB.  */
 108   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 109     {
 110       tree new_phi;
 111
 112       /* First try to find a PHI node in NEW_BB which has the same
 113          PHI_RESULT as the PHI from BB we are currently processing.  */
 114       for (new_phi = phi_nodes (new_bb); new_phi;
 115            new_phi = PHI_CHAIN (new_phi))
 116         if (PHI_RESULT (new_phi) == PHI_RESULT (phi))
 117           break;
 118
 119       /* If we did not find a suitable PHI in NEW_BB, create one.  */
 120       if (!new_phi)
 121         new_phi = create_phi_node (PHI_RESULT (phi), new_bb);
 122
 123       /* Extract the argument corresponding to E from the current PHI
 124          node in BB.  */
 125       arg = PHI_ARG_DEF_TREE (phi, phi_arg_from_edge (phi, e));
 126
 127       /* Now add that same argument to the new PHI node in block NEW_BB.  */
 128       add_phi_arg (&new_phi, arg, e);
 129     }
 130 }
 131
 132 /* Remove the last statement in block BB if it is a control statement
 133    Also remove all outgoing edges except the edge which reaches DEST_BB.
 134    If DEST_BB is NULL, then remove all outgoing edges.  */
 135
 136 static void
 137 remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
 138 {
 139   block_stmt_iterator bsi;
 140   edge e;
 141   edge_iterator ei;
 142
 143   bsi = bsi_last (bb);
 144
 145   /* If the duplicate ends with a control statement, then remove it.
 146
 147      Note that if we are duplicating the template block rather than the
 148      original basic block, then the duplicate might not have any real
 149      statements in it.  */
 150   if (!bsi_end_p (bsi)
 151       && bsi_stmt (bsi)
 152       && (TREE_CODE (bsi_stmt (bsi)) == COND_EXPR
 153           || TREE_CODE (bsi_stmt (bsi)) == SWITCH_EXPR))
 154     bsi_remove (&bsi);
 155
 156   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
 157     {
 158       if (e->dest != dest_bb)
 159         ssa_remove_edge (e);
 160       else
 161         ei_next (&ei);
 162     }
 163 }
 164
 165 /* Create a duplicate of BB which only reaches the destination of the edge
 166    stored in RD.  Record the duplicate block in RD.  */
 167
 168 static void
 169 create_block_for_threading (basic_block bb, struct redirection_data *rd)
 170 {
 171   /* We can use the generic block duplication code and simply remove
 172      the stuff we do not need.  */
 173   rd->dup_block = duplicate_block (bb, NULL);
 174
 175   /* Zero out the profile, since the block is unreachable for now.  */
 176   rd->dup_block->frequency = 0;
 177   rd->dup_block->count = 0;
 178
 179   /* The call to duplicate_block will copy everything, including the
 180      useless COND_EXPR or SWITCH_EXPR at the end of BB.  We just remove
 181      the useless COND_EXPR or SWITCH_EXPR here rather than having a
 182      specialized block copier.  We also remove all outgoing edges
 183      from the duplicate block.  The appropriate edge will be created
 184      later.  */
 185   remove_ctrl_stmt_and_useless_edges (rd->dup_block, NULL);
 186 }
 187
 188 /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
 189    is reached via one or more specific incoming edges, we know which
 190    outgoing edge from BB will be traversed.
 191
 192    We want to redirect those incoming edges to the target of the
 193    appropriate outgoing edge.  Doing so avoids a conditional branch
 194    and may expose new optimization opportunities.  Note that we have
 195    to update dominator tree and SSA graph after such changes.
 196
 197    The key to keeping the SSA graph update manageable is to duplicate
 198    the side effects occurring in BB so that those side effects still
 199    occur on the paths which bypass BB after redirecting edges.
 200
 201    We accomplish this by creating duplicates of BB and arranging for
 202    the duplicates to unconditionally pass control to one specific
 203    successor of BB.  We then revector the incoming edges into BB to
 204    the appropriate duplicate of BB.
 205
 206    BB and its duplicates will have assignments to the same set of
 207    SSA_NAMEs.  Right now, we just call into rewrite_ssa_into_ssa
 208    to update the SSA graph for those names.
 209
 210    We are also going to experiment with a true incremental update
 211    scheme for the duplicated resources.  One of the interesting
 212    properties we can exploit here is that all the resources set
 213    in BB will have the same IDFS, so we have one IDFS computation
 214    per block with incoming threaded edges, which can lower the
 215    cost of the true incremental update algorithm.  */
 216
 217 static void
 218 thread_block (basic_block bb)
 219 {
 220   /* E is an incoming edge into BB that we may or may not want to
 221      redirect to a duplicate of BB.  */
 222   edge e;
 223   edge_iterator ei;
 224   basic_block template_block;
 225
 226   /* ALL indicates whether or not all incoming edges into BB should
 227      be threaded to a duplicate of BB.  */
 228   bool all = true;
 229
 230   unsigned int i;
 231
 232   VARRAY_GENERIC_PTR_INIT (redirection_data, 2, "redirection data");
 233
 234   /* Look at each incoming edge into BB.  Record each unique outgoing
 235      edge that we want to thread an incoming edge to.  Also note if
 236      all incoming edges are threaded or not.  */
 237   FOR_EACH_EDGE (e, ei, bb->preds)
 238     {
 239       if (!e->aux)
 240         {
 241           all = false;
 242         }
 243       else
 244         {
 245           unsigned int i;
 246
 247           /* See if we can find an entry for the destination of this
 248              threaded edge that has already been recorded.  */
 249           for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 250             {
 251               struct redirection_data *rd;
 252               edge e2;
 253
 254               rd = VARRAY_GENERIC_PTR (redirection_data, i);
 255               e2 = e->aux;
 256
 257               if (e2->dest == rd->outgoing_edge->dest)
 258                 break;
 259             }
 260
 261           /* If the loop did not terminate early, then we have a new
 262              destination for the incoming threaded edges.  Record it.  */
 263           if (i == VARRAY_ACTIVE_SIZE (redirection_data))
 264             {
 265               struct redirection_data *rd;
 266
 267               rd = ggc_alloc_cleared (sizeof (struct redirection_data));
 268               rd->outgoing_edge = e->aux;
 269               VARRAY_PUSH_GENERIC_PTR (redirection_data, rd);
 270             }
 271         }
 272     }
 273
 274   /* Now create duplicates of BB.  Note that if all incoming edges are
 275      threaded, then BB is going to become unreachable.  In that case
 276      we use BB for one of the duplicates rather than wasting memory
 277      duplicating BB.  Thus the odd starting condition for the loop.
 278
 279      Note that for a block with a high outgoing degree we can waste
 280      a lot of time and memory creating and destroying useless edges.
 281
 282      So we first duplicate BB and remove the control structure at the
 283      tail of the duplicate as well as all outgoing edges from the
 284      duplicate.  We then use that duplicate block as a template for
 285      the rest of the duplicates.  */
 286   template_block = NULL;
 287   for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 288     {
 289       struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
 290
 291       if (template_block == NULL)
 292         {
 293           create_block_for_threading (bb, rd);
 294           template_block = rd->dup_block;
 295         }
 296       else
 297         {
 298           create_block_for_threading (template_block, rd);
 299         }
 300     }
 301
 302   /* Now created up edges from the duplicate blocks to their new
 303      destinations.  Doing this as a separate loop after block creation
 304      allows us to avoid creating lots of useless edges.  */
 305   for (i = (all ? 1 : 0); i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 306     {
 307       struct redirection_data *rd = VARRAY_GENERIC_PTR (redirection_data, i);
 308       tree phi;
 309       edge e;
 310
 311       e = make_edge (rd->dup_block, rd->outgoing_edge->dest, EDGE_FALLTHRU);
 312
 313       /* If there are any PHI nodes at the destination of the outgoing edge
 314          from the duplicate block, then we will need to add a new argument
 315          to them.  The argument should have the same value as the argument
 316          associated with the outgoing edge stored in RD.  */
 317       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 318         {
 319           int indx = phi_arg_from_edge (phi, rd->outgoing_edge);
 320           add_phi_arg (&phi, PHI_ARG_DEF_TREE (phi, indx), e);
 321         }
 322     }
 323
 324   /* The loop above created the duplicate blocks (and the statements
 325      within the duplicate blocks).  This loop creates PHI nodes for the
 326      duplicated blocks and redirects the incoming edges into BB to reach
 327      the duplicates of BB.
 328
 329      Note that redirecting the edge will change e->pred_next, so we have
 330      to hold e->pred_next in a temporary.
 331
 332      If this turns out to be a performance problem, then we could create
 333      a list of incoming edges associated with each entry in
 334      REDIRECTION_DATA and walk over that list of edges instead.  */
 335   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 336     {
 337       edge new_dest = e->aux;
 338
 339       /* E was not threaded, then there is nothing to do.  */
 340       if (!new_dest)
 341         {
 342           ei_next (&ei);
 343           continue;
 344         }
 345
 346       /* Go ahead and clear E->aux.  It's not needed anymore and failure
 347          to clear it will cause all kinds of unpleasant problems later.  */
 348       e->aux = NULL;
 349
 350       /* We know E is an edge we want to thread.  Find the entry associated
 351          with E's new destination in the REDIRECTION_DATA array.  */
 352       for (i = 0; i < VARRAY_ACTIVE_SIZE (redirection_data); i++)
 353         {
 354           struct redirection_data *rd;
 355
 356           rd = VARRAY_GENERIC_PTR (redirection_data, i);
 357
 358           /* We have found the right entry if the outgoing edge in this
 359              entry matches E's new destination.  Note that if we have not
 360              created a duplicate block (rd->dup_block is NULL), then we
 361              are going to re-use BB as a duplicate and we do not need
 362              to create PHI nodes or redirect the edge.  */
 363           if (rd->outgoing_edge == new_dest && rd->dup_block)
 364             {
 365               edge e2;
 366               copy_phis_to_block (rd->dup_block, bb, e);
 367
 368               if (dump_file && (dump_flags & TDF_DETAILS))
 369                 fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 370                          e->src->index, e->dest->index, rd->dup_block->index);
 371
 372               e2 = redirect_edge_and_branch (e, rd->dup_block);
 373               PENDING_STMT (e2) = NULL;
 374
 375               if ((dump_file && (dump_flags & TDF_DETAILS))
 376                   && e->src != e2->src)
 377               fprintf (dump_file, "    basic block %d created\n",
 378                        e2->src->index);
 379               break;
 380             }
 381         }
 382     }
 383
 384   /* If all the incoming edges where threaded, then we used BB as one
 385      of the duplicate blocks.  We need to fixup BB in that case so that
 386      it no longer has a COND_EXPR or SWITCH_EXPR and reaches one destination
 387      unconditionally.  */
 388   if (all)
 389     {
 390       struct redirection_data *rd;
 391
 392       rd = VARRAY_GENERIC_PTR (redirection_data, 0);
 393
 394       if (dump_file && (dump_flags & TDF_DETAILS))
 395         fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
 396                  EDGE_PRED (bb, 0)->src->index, bb->index,
 397                  EDGE_SUCC (bb, 0)->dest->index);
 398
 399       remove_ctrl_stmt_and_useless_edges (bb, rd->outgoing_edge->dest);
 400       EDGE_SUCC (bb, 0)->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 401       EDGE_SUCC (bb, 0)->flags |= EDGE_FALLTHRU;
 402     }
 403
 404   /* Done with this block.  Clear REDIRECTION_DATA.  */
 405   VARRAY_CLEAR (redirection_data);
 406 }
 407
 408 /* Walk through all blocks and thread incoming edges to the block's
 409    destinations as requested.  This is the only entry point into this
 410    file.
 411
 412    Blocks which have one or more incoming edges have INCOMING_EDGE_THREADED
 413    set in the block's annotation.
 414    this routine.
 415
 416    Each edge that should be threaded has the new destination edge stored in
 417    the original edge's AUX field.
 418
 419    This routine (or one of its callees) will clear INCOMING_EDGE_THREADED
 420    in the block annotations and the AUX field in the edges.
 421
 422    It is the caller's responsibility to fix the dominance information
 423    and rewrite duplicated SSA_NAMEs back into SSA form.
 424
 425    Returns true if one or more edges were threaded, false otherwise.   */
 426
 427 bool
 428 thread_through_all_blocks (void)
 429 {
 430   basic_block bb;
 431   bool retval = false;
 432
 433   FOR_EACH_BB (bb)
 434     {
 435       if (bb_ann (bb)->incoming_edge_threaded)
 436         {
 437           thread_block (bb);
 438           retval = true;
 439           bb_ann (bb)->incoming_edge_threaded = false;
 440         }
 441     }
 442   return retval;
 443 }