GCC Middle and Back End API Reference
el Struct Reference
Collaboration diagram for el:

Data Fields

edge e
struct elnext

Detailed Description


Thread edges through blocks and update the control flow and SSA graphs. Copyright (C) 2004-2013 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

   Given a block B, update the CFG and SSA graph to reflect redirecting
   one or more in-edges to B to instead reach the destination of an
   out-edge from B while preserving any side effects in B.

   i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
   side effects of executing B.

     1. Make a copy of B (including its outgoing edges and statements).  Call
        the copy B'.  Note B' has no incoming edges or PHIs at this time.

     2. Remove the control statement at the end of B' and all outgoing edges
        except B'->C.

     3. Add a new argument to each PHI in C with the same value as the existing
        argument associated with edge B->C.  Associate the new PHI arguments
        with the edge B'->C.

     4. For each PHI in B, find or create a PHI in B' with an identical
        PHI_RESULT.  Add an argument to the PHI in B' which has the same
        value as the PHI in B associated with the edge A->B.  Associate
        the new argument in the PHI in B' with the edge A->B.

     5. Change the edge A->B to A->B'.

        5a. This automatically deletes any PHI arguments associated with the
            edge A->B in B.

        5b. This automatically associates each new argument added in step 4
            with the edge A->B'.

     6. Repeat for other incoming edges into B.

     7. Put the duplicated resources in B and all the B' blocks into SSA form.

   Note that block duplication can be minimized by first collecting the
   set of unique destination blocks that the incoming edges should
   be threaded to.

   Block duplication can be further minimized by using B instead of
   creating B' for one destination if all edges into B are going to be
   threaded to a successor of B.  We had code to do this at one time, but
   I'm not convinced it is correct with the changes to avoid mucking up
   the loop structure (which may cancel threading requests, thus a block
   which we thought was going to become unreachable may still be reachable).
   This code was also going to get ugly with the introduction of the ability
   for a single jump thread request to bypass multiple blocks.

   We further reduce the number of edges and statements we create by
   not copying all the outgoing edges and the control statement in
   step #1.  We instead create a template block without the outgoing
   edges and duplicate the template.  
   Steps #5 and #6 of the above algorithm are best implemented by walking
   all the incoming edges which thread to the same destination edge at
   the same time.  That avoids lots of table lookups to get information
   for the destination edge.

   To realize that implementation we create a list of incoming edges
   which thread to the same outgoing edge.  Thus to implement steps
   #5 and #6 we traverse our hash table of outgoing edge information.
   For each entry we walk the list of incoming edges which thread to
   the current outgoing edge.  

Field Documentation

edge el::e

Referenced by lookup_redirection_data().

struct el* el::next

Referenced by lookup_redirection_data().

The documentation for this struct was generated from the following file: