]>
Commit | Line | Data |
---|---|---|
c63539ff ML |
1 | .. |
2 | Copyright 1988-2022 Free Software Foundation, Inc. | |
3 | This is part of the GCC manual. | |
4 | For copying conditions, see the copyright.rst file. | |
5 | ||
6 | .. index:: edge in the flow graph, edge | |
7 | ||
8 | .. _edges: | |
9 | ||
10 | Edges | |
11 | ***** | |
12 | ||
13 | Edges represent possible control flow transfers from the end of some | |
14 | basic block A to the head of another basic block B. We say that A is | |
15 | a predecessor of B, and B is a successor of A. Edges are represented | |
16 | in GCC with the ``edge`` data type. Each ``edge`` acts as a | |
17 | link between two basic blocks: The ``src`` member of an edge | |
18 | points to the predecessor basic block of the ``dest`` basic block. | |
19 | The members ``preds`` and ``succs`` of the ``basic_block`` data | |
20 | type point to type-safe vectors of edges to the predecessors and | |
21 | successors of the block. | |
22 | ||
23 | .. index:: edge iterators | |
24 | ||
25 | When walking the edges in an edge vector, :dfn:`edge iterators` should | |
26 | be used. Edge iterators are constructed using the | |
27 | ``edge_iterator`` data structure and several methods are available | |
28 | to operate on them: | |
29 | ||
30 | ``ei_start`` | |
31 | This function initializes an ``edge_iterator`` that points to the | |
32 | first edge in a vector of edges. | |
33 | ||
34 | ``ei_last`` | |
35 | This function initializes an ``edge_iterator`` that points to the | |
36 | last edge in a vector of edges. | |
37 | ||
38 | ``ei_end_p`` | |
39 | This predicate is ``true`` if an ``edge_iterator`` represents | |
40 | the last edge in an edge vector. | |
41 | ||
42 | ``ei_one_before_end_p`` | |
43 | This predicate is ``true`` if an ``edge_iterator`` represents | |
44 | the second last edge in an edge vector. | |
45 | ||
46 | ``ei_next`` | |
47 | This function takes a pointer to an ``edge_iterator`` and makes it | |
48 | point to the next edge in the sequence. | |
49 | ||
50 | ``ei_prev`` | |
51 | This function takes a pointer to an ``edge_iterator`` and makes it | |
52 | point to the previous edge in the sequence. | |
53 | ||
54 | ``ei_edge`` | |
55 | This function returns the ``edge`` currently pointed to by an | |
56 | ``edge_iterator``. | |
57 | ||
58 | ``ei_safe_edge`` | |
59 | This function returns the ``edge`` currently pointed to by an | |
60 | ``edge_iterator``, but returns ``NULL`` if the iterator is | |
61 | pointing at the end of the sequence. This function has been provided | |
62 | for existing code makes the assumption that a ``NULL`` edge | |
63 | indicates the end of the sequence. | |
64 | ||
65 | The convenience macro ``FOR_EACH_EDGE`` can be used to visit all of | |
66 | the edges in a sequence of predecessor or successor edges. It must | |
67 | not be used when an element might be removed during the traversal, | |
68 | otherwise elements will be missed. Here is an example of how to use | |
69 | the macro: | |
70 | ||
71 | .. code-block:: c++ | |
72 | ||
73 | edge e; | |
74 | edge_iterator ei; | |
75 | ||
76 | FOR_EACH_EDGE (e, ei, bb->succs) | |
77 | { | |
78 | if (e->flags & EDGE_FALLTHRU) | |
79 | break; | |
80 | } | |
81 | ||
82 | .. index:: fall-thru | |
83 | ||
84 | There are various reasons why control flow may transfer from one block | |
85 | to another. One possibility is that some instruction, for example a | |
86 | ``CODE_LABEL``, in a linearized instruction stream just always | |
87 | starts a new basic block. In this case a :dfn:`fall-thru` edge links | |
88 | the basic block to the first following basic block. But there are | |
89 | several other reasons why edges may be created. The ``flags`` | |
90 | field of the ``edge`` data type is used to store information | |
91 | about the type of edge we are dealing with. Each edge is of one of | |
92 | the following types: | |
93 | ||
94 | **jump** | |
95 | ||
96 | No type flags are set for edges corresponding to jump instructions. | |
97 | These edges are used for unconditional or conditional jumps and in | |
98 | RTL also for table jumps. They are the easiest to manipulate as they | |
99 | may be freely redirected when the flow graph is not in SSA form. | |
100 | ||
101 | **fall-thru** | |
102 | ||
103 | .. index:: EDGE_FALLTHRU, force_nonfallthru | |
104 | ||
105 | Fall-thru edges are present in case where the basic block may continue | |
106 | execution to the following one without branching. These edges have | |
107 | the ``EDGE_FALLTHRU`` flag set. Unlike other types of edges, these | |
108 | edges must come into the basic block immediately following in the | |
109 | instruction stream. The function ``force_nonfallthru`` is | |
110 | available to insert an unconditional jump in the case that redirection | |
111 | is needed. Note that this may require creation of a new basic block. | |
112 | ||
113 | **exception handling** | |
114 | ||
115 | .. index:: exception handling, EDGE_ABNORMAL, EDGE_EH | |
116 | ||
117 | Exception handling edges represent possible control transfers from a | |
118 | trapping instruction to an exception handler. The definition of | |
119 | 'trapping' varies. In C++, only function calls can throw, but for | |
120 | Ada exceptions like division by zero or segmentation fault are | |
121 | defined and thus each instruction possibly throwing this kind of | |
122 | exception needs to be handled as control flow instruction. Exception | |
123 | edges have the ``EDGE_ABNORMAL`` and ``EDGE_EH`` flags set. | |
124 | ||
125 | .. index:: purge_dead_edges | |
126 | ||
127 | When updating the instruction stream it is easy to change possibly | |
128 | trapping instruction to non-trapping, by simply removing the exception | |
129 | edge. The opposite conversion is difficult, but should not happen | |
130 | anyway. The edges can be eliminated via ``purge_dead_edges`` call. | |
131 | ||
132 | .. index:: REG_EH_REGION, EDGE_ABNORMAL_CALL | |
133 | ||
134 | In the RTL representation, the destination of an exception edge is | |
135 | specified by ``REG_EH_REGION`` note attached to the insn. | |
136 | In case of a trapping call the ``EDGE_ABNORMAL_CALL`` flag is set | |
137 | too. In the ``GIMPLE`` representation, this extra flag is not set. | |
138 | ||
139 | .. index:: may_trap_p, tree_could_trap_p | |
140 | ||
141 | In the RTL representation, the predicate ``may_trap_p`` may be used | |
142 | to check whether instruction still may trap or not. For the tree | |
143 | representation, the ``tree_could_trap_p`` predicate is available, | |
144 | but this predicate only checks for possible memory traps, as in | |
145 | dereferencing an invalid pointer location. | |
146 | ||
147 | **sibling calls** | |
148 | ||
149 | .. index:: sibling call, EDGE_ABNORMAL, EDGE_SIBCALL | |
150 | ||
151 | Sibling calls or tail calls terminate the function in a non-standard | |
152 | way and thus an edge to the exit must be present. | |
153 | ``EDGE_SIBCALL`` and ``EDGE_ABNORMAL`` are set in such case. | |
154 | These edges only exist in the RTL representation. | |
155 | ||
156 | **computed jumps** | |
157 | ||
158 | .. index:: computed jump, EDGE_ABNORMAL | |
159 | ||
160 | Computed jumps contain edges to all labels in the function referenced | |
161 | from the code. All those edges have ``EDGE_ABNORMAL`` flag set. | |
162 | The edges used to represent computed jumps often cause compile time | |
163 | performance problems, since functions consisting of many taken labels | |
164 | and many computed jumps may have *very* dense flow graphs, so | |
165 | these edges need to be handled with special care. During the earlier | |
166 | stages of the compilation process, GCC tries to avoid such dense flow | |
167 | graphs by factoring computed jumps. For example, given the following | |
168 | series of jumps, | |
169 | ||
170 | .. code-block:: c++ | |
171 | ||
172 | goto *x; | |
173 | [ ... ] | |
174 | ||
175 | goto *x; | |
176 | [ ... ] | |
177 | ||
178 | goto *x; | |
179 | [ ... ] | |
180 | ||
181 | factoring the computed jumps results in the following code sequence | |
182 | which has a much simpler flow graph: | |
183 | ||
184 | .. code-block:: c++ | |
185 | ||
186 | goto y; | |
187 | [ ... ] | |
188 | ||
189 | goto y; | |
190 | [ ... ] | |
191 | ||
192 | goto y; | |
193 | [ ... ] | |
194 | ||
195 | y: | |
196 | goto *x; | |
197 | ||
198 | .. index:: pass_duplicate_computed_gotos | |
199 | ||
200 | However, the classic problem with this transformation is that it has a | |
201 | runtime cost in there resulting code: An extra jump. Therefore, the | |
202 | computed jumps are un-factored in the later passes of the compiler | |
203 | (in the pass called ``pass_duplicate_computed_gotos``). | |
204 | Be aware of that when you work on passes in that area. There have | |
205 | been numerous examples already where the compile time for code with | |
206 | unfactored computed jumps caused some serious headaches. | |
207 | ||
208 | **nonlocal goto handlers** | |
209 | ||
210 | .. index:: nonlocal goto handler, EDGE_ABNORMAL, EDGE_ABNORMAL_CALL | |
211 | ||
212 | GCC allows nested functions to return into caller using a ``goto`` | |
213 | to a label passed to as an argument to the callee. The labels passed | |
214 | to nested functions contain special code to cleanup after function | |
215 | call. Such sections of code are referred to as 'nonlocal goto | |
216 | receivers'. If a function contains such nonlocal goto receivers, an | |
217 | edge from the call to the label is created with the | |
218 | ``EDGE_ABNORMAL`` and ``EDGE_ABNORMAL_CALL`` flags set. | |
219 | ||
220 | **function entry points** | |
221 | ||
222 | .. index:: function entry point, alternate function entry point, LABEL_ALTERNATE_NAME | |
223 | ||
224 | By definition, execution of function starts at basic block 0, so there | |
225 | is always an edge from the ``ENTRY_BLOCK_PTR`` to basic block 0. | |
226 | There is no ``GIMPLE`` representation for alternate entry points at | |
227 | this moment. In RTL, alternate entry points are specified by | |
228 | ``CODE_LABEL`` with ``LABEL_ALTERNATE_NAME`` defined. This | |
229 | feature is currently used for multiple entry point prologues and is | |
230 | limited to post-reload passes only. This can be used by back-ends to | |
231 | emit alternate prologues for functions called from different contexts. | |
232 | In future full support for multiple entry functions defined by Fortran | |
233 | 90 needs to be implemented. | |
234 | ||
235 | **function exits** | |
236 | ||
237 | In the pre-reload representation a function terminates after the last | |
238 | instruction in the insn chain and no explicit return instructions are | |
239 | used. This corresponds to the fall-thru edge into exit block. After | |
240 | reload, optimal RTL epilogues are used that use explicit (conditional) | |
3ed1b4ce | 241 | return instructions that are represented by edges with no flags set. |