Data Fields | |
| edge | e |
| struct el * | next |
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.
- 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.
- Remove the control statement at the end of B' and all outgoing edges except B'->C.
- 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.
- 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.
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'.
- Repeat for other incoming edges into B.
- 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:
