Data Fields | |
| edge | e |
| struct el * | next |
Detailed Description
@verbatim
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:
