Mercurial > hg > CbC > CbC_gcc
annotate gcc/doc/cfg.texi @ 131:84e7813d76e9
gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 07:37:49 +0900 |
parents | 04ced10e8804 |
children | 1830386684a0 |
rev | line source |
---|---|
0 | 1 @c -*-texinfo-*- |
131 | 2 @c Copyright (C) 2001-2018 Free Software Foundation, Inc. |
0 | 3 @c This is part of the GCC manual. |
4 @c For copying conditions, see the file gcc.texi. | |
5 | |
6 @c --------------------------------------------------------------------- | |
7 @c Control Flow Graph | |
8 @c --------------------------------------------------------------------- | |
9 | |
10 @node Control Flow | |
11 @chapter Control Flow Graph | |
12 @cindex CFG, Control Flow Graph | |
13 @findex basic-block.h | |
14 | |
15 A control flow graph (CFG) is a data structure built on top of the | |
111 | 16 intermediate code representation (the RTL or @code{GIMPLE} instruction |
0 | 17 stream) abstracting the control flow behavior of a function that is |
18 being compiled. The CFG is a directed graph where the vertices | |
19 represent basic blocks and edges represent possible transfer of | |
20 control flow from one basic block to another. The data structures | |
21 used to represent the control flow graph are defined in | |
22 @file{basic-block.h}. | |
23 | |
111 | 24 In GCC, the representation of control flow is maintained throughout |
25 the compilation process, from constructing the CFG early in | |
26 @code{pass_build_cfg} to @code{pass_free_cfg} (see @file{passes.def}). | |
27 The CFG takes various different modes and may undergo extensive | |
28 manipulations, but the graph is always valid between its construction | |
29 and its release. This way, transfer of information such as data flow, | |
30 a measured profile, or the loop tree, can be propagated through the | |
31 passes pipeline, and even from @code{GIMPLE} to @code{RTL}. | |
32 | |
33 Often the CFG may be better viewed as integral part of instruction | |
34 chain, than structure built on the top of it. Updating the compiler's | |
35 intermediate representation for instructions can not be easily done | |
36 without proper maintenance of the CFG simultaneously. | |
37 | |
0 | 38 @menu |
39 * Basic Blocks:: The definition and representation of basic blocks. | |
40 * Edges:: Types of edges and their representation. | |
41 * Profile information:: Representation of frequencies and probabilities. | |
42 * Maintaining the CFG:: Keeping the control flow graph and up to date. | |
43 * Liveness information:: Using and maintaining liveness information. | |
44 @end menu | |
45 | |
46 | |
47 @node Basic Blocks | |
48 @section Basic Blocks | |
49 | |
50 @cindex basic block | |
51 @findex basic_block | |
52 A basic block is a straight-line sequence of code with only one entry | |
53 point and only one exit. In GCC, basic blocks are represented using | |
54 the @code{basic_block} data type. | |
55 | |
111 | 56 @findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR |
57 Special basic blocks represent possible entry and exit points of a | |
58 function. These blocks are called @code{ENTRY_BLOCK_PTR} and | |
59 @code{EXIT_BLOCK_PTR}. These blocks do not contain any code. | |
0 | 60 |
61 @findex BASIC_BLOCK | |
62 The @code{BASIC_BLOCK} array contains all basic blocks in an | |
63 unspecified order. Each @code{basic_block} structure has a field | |
64 that holds a unique integer identifier @code{index} that is the | |
65 index of the block in the @code{BASIC_BLOCK} array. | |
66 The total number of basic blocks in the function is | |
67 @code{n_basic_blocks}. Both the basic block indices and | |
68 the total number of basic blocks may vary during the compilation | |
69 process, as passes reorder, create, duplicate, and destroy basic | |
70 blocks. The index for any block should never be greater than | |
111 | 71 @code{last_basic_block}. The indices 0 and 1 are special codes |
72 reserved for @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}, the | |
73 indices of @code{ENTRY_BLOCK_PTR} and @code{EXIT_BLOCK_PTR}. | |
0 | 74 |
111 | 75 @findex next_bb, prev_bb, FOR_EACH_BB, FOR_ALL_BB |
76 Two pointer members of the @code{basic_block} structure are the | |
77 pointers @code{next_bb} and @code{prev_bb}. These are used to keep | |
78 doubly linked chain of basic blocks in the same order as the | |
79 underlying instruction stream. The chain of basic blocks is updated | |
80 transparently by the provided API for manipulating the CFG@. The macro | |
81 @code{FOR_EACH_BB} can be used to visit all the basic blocks in | |
82 lexicographical order, except @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. | |
83 The macro @code{FOR_ALL_BB} also visits all basic blocks in | |
84 lexicographical order, including @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. | |
85 | |
86 @findex post_order_compute, inverted_post_order_compute, walk_dominator_tree | |
87 The functions @code{post_order_compute} and @code{inverted_post_order_compute} | |
88 can be used to compute topological orders of the CFG. The orders are | |
89 stored as vectors of basic block indices. The @code{BASIC_BLOCK} array | |
90 can be used to iterate each basic block by index. | |
91 Dominator traversals are also possible using | |
92 @code{walk_dominator_tree}. Given two basic blocks A and B, block A | |
93 dominates block B if A is @emph{always} executed before B@. | |
0 | 94 |
95 Each @code{basic_block} also contains pointers to the first | |
96 instruction (the @dfn{head}) and the last instruction (the @dfn{tail}) | |
97 or @dfn{end} of the instruction stream contained in a basic block. In | |
98 fact, since the @code{basic_block} data type is used to represent | |
111 | 99 blocks in both major intermediate representations of GCC (@code{GIMPLE} |
0 | 100 and RTL), there are pointers to the head and end of a basic block for |
111 | 101 both representations, stored in intermediate representation specific |
102 data in the @code{il} field of @code{struct basic_block_def}. | |
0 | 103 |
111 | 104 @findex CODE_LABEL |
105 @findex NOTE_INSN_BASIC_BLOCK | |
106 For RTL, these pointers are @code{BB_HEAD} and @code{BB_END}. | |
107 | |
108 @cindex insn notes, notes | |
109 @findex NOTE_INSN_BASIC_BLOCK | |
0 | 110 In the RTL representation of a function, the instruction stream |
111 | 111 contains not only the ``real'' instructions, but also @dfn{notes} |
112 or @dfn{insn notes} (to distinguish them from @dfn{reg notes}). | |
0 | 113 Any function that moves or duplicates the basic blocks needs |
114 to take care of updating of these notes. Many of these notes expect | |
111 | 115 that the instruction stream consists of linear regions, so updating |
116 can sometimes be tedious. All types of insn notes are defined | |
117 in @file{insn-notes.def}. | |
118 | |
119 In the RTL function representation, the instructions contained in a | |
120 basic block always follow a @code{NOTE_INSN_BASIC_BLOCK}, but zero | |
121 or more @code{CODE_LABEL} nodes can precede the block note. | |
122 A basic block ends with a control flow instruction or with the last | |
123 instruction before the next @code{CODE_LABEL} or | |
124 @code{NOTE_INSN_BASIC_BLOCK}. | |
125 By definition, a @code{CODE_LABEL} cannot appear in the middle of | |
0 | 126 the instruction stream of a basic block. |
127 | |
128 @findex can_fallthru | |
129 @cindex table jump | |
130 In addition to notes, the jump table vectors are also represented as | |
131 ``pseudo-instructions'' inside the insn stream. These vectors never | |
132 appear in the basic block and should always be placed just after the | |
133 table jump instructions referencing them. After removing the | |
134 table-jump it is often difficult to eliminate the code computing the | |
135 address and referencing the vector, so cleaning up these vectors is | |
136 postponed until after liveness analysis. Thus the jump table vectors | |
137 may appear in the insn stream unreferenced and without any purpose. | |
138 Before any edge is made @dfn{fall-thru}, the existence of such | |
139 construct in the way needs to be checked by calling | |
140 @code{can_fallthru} function. | |
141 | |
111 | 142 @cindex GIMPLE statement iterators |
143 For the @code{GIMPLE} representation, the PHI nodes and statements | |
144 contained in a basic block are in a @code{gimple_seq} pointed to by | |
145 the basic block intermediate language specific pointers. | |
146 Abstract containers and iterators are used to access the PHI nodes | |
147 and statements in a basic blocks. These iterators are called | |
148 @dfn{GIMPLE statement iterators} (GSIs). Grep for @code{^gsi} | |
149 in the various @file{gimple-*} and @file{tree-*} files. | |
150 There is a @code{gimple_stmt_iterator} type for iterating over | |
151 all kinds of statement, and a @code{gphi_iterator} subclass for | |
152 iterating over PHI nodes. | |
153 The following snippet will pretty-print all PHI nodes the statements | |
154 of the current function in the GIMPLE representation. | |
0 | 155 |
156 @smallexample | |
111 | 157 basic_block bb; |
158 | |
0 | 159 FOR_EACH_BB (bb) |
160 @{ | |
111 | 161 gphi_iterator pi; |
162 gimple_stmt_iterator si; | |
0 | 163 |
111 | 164 for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) |
165 @{ | |
166 gphi *phi = pi.phi (); | |
167 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); | |
168 @} | |
169 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) | |
170 @{ | |
171 gimple stmt = gsi_stmt (si); | |
172 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
173 @} | |
0 | 174 @} |
175 @end smallexample | |
176 | |
177 | |
178 @node Edges | |
179 @section Edges | |
180 | |
181 @cindex edge in the flow graph | |
182 @findex edge | |
183 Edges represent possible control flow transfers from the end of some | |
184 basic block A to the head of another basic block B@. We say that A is | |
185 a predecessor of B, and B is a successor of A@. Edges are represented | |
186 in GCC with the @code{edge} data type. Each @code{edge} acts as a | |
111 | 187 link between two basic blocks: The @code{src} member of an edge |
0 | 188 points to the predecessor basic block of the @code{dest} basic block. |
189 The members @code{preds} and @code{succs} of the @code{basic_block} data | |
190 type point to type-safe vectors of edges to the predecessors and | |
191 successors of the block. | |
192 | |
193 @cindex edge iterators | |
194 When walking the edges in an edge vector, @dfn{edge iterators} should | |
195 be used. Edge iterators are constructed using the | |
196 @code{edge_iterator} data structure and several methods are available | |
197 to operate on them: | |
198 | |
199 @ftable @code | |
200 @item ei_start | |
201 This function initializes an @code{edge_iterator} that points to the | |
202 first edge in a vector of edges. | |
203 | |
204 @item ei_last | |
205 This function initializes an @code{edge_iterator} that points to the | |
206 last edge in a vector of edges. | |
207 | |
208 @item ei_end_p | |
209 This predicate is @code{true} if an @code{edge_iterator} represents | |
210 the last edge in an edge vector. | |
211 | |
212 @item ei_one_before_end_p | |
213 This predicate is @code{true} if an @code{edge_iterator} represents | |
214 the second last edge in an edge vector. | |
215 | |
216 @item ei_next | |
217 This function takes a pointer to an @code{edge_iterator} and makes it | |
218 point to the next edge in the sequence. | |
219 | |
220 @item ei_prev | |
221 This function takes a pointer to an @code{edge_iterator} and makes it | |
222 point to the previous edge in the sequence. | |
223 | |
224 @item ei_edge | |
225 This function returns the @code{edge} currently pointed to by an | |
226 @code{edge_iterator}. | |
227 | |
228 @item ei_safe_safe | |
229 This function returns the @code{edge} currently pointed to by an | |
230 @code{edge_iterator}, but returns @code{NULL} if the iterator is | |
231 pointing at the end of the sequence. This function has been provided | |
232 for existing code makes the assumption that a @code{NULL} edge | |
233 indicates the end of the sequence. | |
234 | |
235 @end ftable | |
236 | |
237 The convenience macro @code{FOR_EACH_EDGE} can be used to visit all of | |
238 the edges in a sequence of predecessor or successor edges. It must | |
239 not be used when an element might be removed during the traversal, | |
240 otherwise elements will be missed. Here is an example of how to use | |
241 the macro: | |
242 | |
243 @smallexample | |
244 edge e; | |
245 edge_iterator ei; | |
246 | |
247 FOR_EACH_EDGE (e, ei, bb->succs) | |
248 @{ | |
249 if (e->flags & EDGE_FALLTHRU) | |
250 break; | |
251 @} | |
252 @end smallexample | |
253 | |
254 @findex fall-thru | |
255 There are various reasons why control flow may transfer from one block | |
256 to another. One possibility is that some instruction, for example a | |
257 @code{CODE_LABEL}, in a linearized instruction stream just always | |
258 starts a new basic block. In this case a @dfn{fall-thru} edge links | |
259 the basic block to the first following basic block. But there are | |
260 several other reasons why edges may be created. The @code{flags} | |
261 field of the @code{edge} data type is used to store information | |
262 about the type of edge we are dealing with. Each edge is of one of | |
263 the following types: | |
264 | |
265 @table @emph | |
266 @item jump | |
267 No type flags are set for edges corresponding to jump instructions. | |
268 These edges are used for unconditional or conditional jumps and in | |
269 RTL also for table jumps. They are the easiest to manipulate as they | |
270 may be freely redirected when the flow graph is not in SSA form. | |
271 | |
272 @item fall-thru | |
273 @findex EDGE_FALLTHRU, force_nonfallthru | |
274 Fall-thru edges are present in case where the basic block may continue | |
275 execution to the following one without branching. These edges have | |
276 the @code{EDGE_FALLTHRU} flag set. Unlike other types of edges, these | |
277 edges must come into the basic block immediately following in the | |
278 instruction stream. The function @code{force_nonfallthru} is | |
279 available to insert an unconditional jump in the case that redirection | |
280 is needed. Note that this may require creation of a new basic block. | |
281 | |
282 @item exception handling | |
283 @cindex exception handling | |
284 @findex EDGE_ABNORMAL, EDGE_EH | |
285 Exception handling edges represent possible control transfers from a | |
286 trapping instruction to an exception handler. The definition of | |
287 ``trapping'' varies. In C++, only function calls can throw, but for | |
111 | 288 Ada exceptions like division by zero or segmentation fault are |
0 | 289 defined and thus each instruction possibly throwing this kind of |
290 exception needs to be handled as control flow instruction. Exception | |
291 edges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set. | |
292 | |
293 @findex purge_dead_edges | |
294 When updating the instruction stream it is easy to change possibly | |
295 trapping instruction to non-trapping, by simply removing the exception | |
296 edge. The opposite conversion is difficult, but should not happen | |
297 anyway. The edges can be eliminated via @code{purge_dead_edges} call. | |
298 | |
299 @findex REG_EH_REGION, EDGE_ABNORMAL_CALL | |
300 In the RTL representation, the destination of an exception edge is | |
301 specified by @code{REG_EH_REGION} note attached to the insn. | |
302 In case of a trapping call the @code{EDGE_ABNORMAL_CALL} flag is set | |
111 | 303 too. In the @code{GIMPLE} representation, this extra flag is not set. |
0 | 304 |
305 @findex may_trap_p, tree_could_trap_p | |
306 In the RTL representation, the predicate @code{may_trap_p} may be used | |
307 to check whether instruction still may trap or not. For the tree | |
308 representation, the @code{tree_could_trap_p} predicate is available, | |
309 but this predicate only checks for possible memory traps, as in | |
310 dereferencing an invalid pointer location. | |
311 | |
312 | |
313 @item sibling calls | |
314 @cindex sibling call | |
315 @findex EDGE_ABNORMAL, EDGE_SIBCALL | |
316 Sibling calls or tail calls terminate the function in a non-standard | |
317 way and thus an edge to the exit must be present. | |
318 @code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case. | |
319 These edges only exist in the RTL representation. | |
320 | |
321 @item computed jumps | |
322 @cindex computed jump | |
323 @findex EDGE_ABNORMAL | |
324 Computed jumps contain edges to all labels in the function referenced | |
325 from the code. All those edges have @code{EDGE_ABNORMAL} flag set. | |
326 The edges used to represent computed jumps often cause compile time | |
327 performance problems, since functions consisting of many taken labels | |
328 and many computed jumps may have @emph{very} dense flow graphs, so | |
329 these edges need to be handled with special care. During the earlier | |
330 stages of the compilation process, GCC tries to avoid such dense flow | |
331 graphs by factoring computed jumps. For example, given the following | |
332 series of jumps, | |
333 | |
334 @smallexample | |
335 goto *x; | |
336 [ @dots{} ] | |
337 | |
338 goto *x; | |
339 [ @dots{} ] | |
340 | |
341 goto *x; | |
342 [ @dots{} ] | |
343 @end smallexample | |
344 | |
345 @noindent | |
346 factoring the computed jumps results in the following code sequence | |
347 which has a much simpler flow graph: | |
348 | |
349 @smallexample | |
350 goto y; | |
351 [ @dots{} ] | |
352 | |
353 goto y; | |
354 [ @dots{} ] | |
355 | |
356 goto y; | |
357 [ @dots{} ] | |
358 | |
359 y: | |
360 goto *x; | |
361 @end smallexample | |
362 | |
111 | 363 @findex pass_duplicate_computed_gotos |
0 | 364 However, the classic problem with this transformation is that it has a |
365 runtime cost in there resulting code: An extra jump. Therefore, the | |
111 | 366 computed jumps are un-factored in the later passes of the compiler |
367 (in the pass called @code{pass_duplicate_computed_gotos}). | |
0 | 368 Be aware of that when you work on passes in that area. There have |
369 been numerous examples already where the compile time for code with | |
370 unfactored computed jumps caused some serious headaches. | |
371 | |
372 @item nonlocal goto handlers | |
373 @cindex nonlocal goto handler | |
374 @findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL | |
375 GCC allows nested functions to return into caller using a @code{goto} | |
376 to a label passed to as an argument to the callee. The labels passed | |
377 to nested functions contain special code to cleanup after function | |
378 call. Such sections of code are referred to as ``nonlocal goto | |
379 receivers''. If a function contains such nonlocal goto receivers, an | |
380 edge from the call to the label is created with the | |
381 @code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set. | |
382 | |
383 @item function entry points | |
384 @cindex function entry point, alternate function entry point | |
385 @findex LABEL_ALTERNATE_NAME | |
386 By definition, execution of function starts at basic block 0, so there | |
387 is always an edge from the @code{ENTRY_BLOCK_PTR} to basic block 0. | |
111 | 388 There is no @code{GIMPLE} representation for alternate entry points at |
0 | 389 this moment. In RTL, alternate entry points are specified by |
390 @code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined. This | |
391 feature is currently used for multiple entry point prologues and is | |
392 limited to post-reload passes only. This can be used by back-ends to | |
393 emit alternate prologues for functions called from different contexts. | |
394 In future full support for multiple entry functions defined by Fortran | |
395 90 needs to be implemented. | |
396 | |
397 @item function exits | |
398 In the pre-reload representation a function terminates after the last | |
399 instruction in the insn chain and no explicit return instructions are | |
400 used. This corresponds to the fall-thru edge into exit block. After | |
401 reload, optimal RTL epilogues are used that use explicit (conditional) | |
402 return instructions that are represented by edges with no flags set. | |
403 | |
404 @end table | |
405 | |
406 | |
407 @node Profile information | |
408 @section Profile information | |
409 | |
410 @cindex profile representation | |
411 In many cases a compiler must make a choice whether to trade speed in | |
412 one part of code for speed in another, or to trade code size for code | |
413 speed. In such cases it is useful to know information about how often | |
414 some given block will be executed. That is the purpose for | |
415 maintaining profile within the flow graph. | |
416 GCC can handle profile information obtained through @dfn{profile | |
111 | 417 feedback}, but it can also estimate branch probabilities based on |
0 | 418 statics and heuristics. |
419 | |
420 @cindex profile feedback | |
421 The feedback based profile is produced by compiling the program with | |
422 instrumentation, executing it on a train run and reading the numbers | |
423 of executions of basic blocks and edges back to the compiler while | |
424 re-compiling the program to produce the final executable. This method | |
425 provides very accurate information about where a program spends most | |
426 of its time on the train run. Whether it matches the average run of | |
427 course depends on the choice of train data set, but several studies | |
428 have shown that the behavior of a program usually changes just | |
429 marginally over different data sets. | |
430 | |
431 @cindex Static profile estimation | |
432 @cindex branch prediction | |
433 @findex predict.def | |
434 When profile feedback is not available, the compiler may be asked to | |
435 attempt to predict the behavior of each branch in the program using a | |
436 set of heuristics (see @file{predict.def} for details) and compute | |
437 estimated frequencies of each basic block by propagating the | |
438 probabilities over the graph. | |
439 | |
440 @findex frequency, count, BB_FREQ_BASE | |
441 Each @code{basic_block} contains two integer fields to represent | |
442 profile information: @code{frequency} and @code{count}. The | |
443 @code{frequency} is an estimation how often is basic block executed | |
444 within a function. It is represented as an integer scaled in the | |
445 range from 0 to @code{BB_FREQ_BASE}. The most frequently executed | |
446 basic block in function is initially set to @code{BB_FREQ_BASE} and | |
447 the rest of frequencies are scaled accordingly. During optimization, | |
448 the frequency of the most frequent basic block can both decrease (for | |
449 instance by loop unrolling) or grow (for instance by cross-jumping | |
450 optimization), so scaling sometimes has to be performed multiple | |
451 times. | |
452 | |
453 @findex gcov_type | |
454 The @code{count} contains hard-counted numbers of execution measured | |
455 during training runs and is nonzero only when profile feedback is | |
456 available. This value is represented as the host's widest integer | |
457 (typically a 64 bit integer) of the special type @code{gcov_type}. | |
458 | |
459 Most optimization passes can use only the frequency information of a | |
460 basic block, but a few passes may want to know hard execution counts. | |
461 The frequencies should always match the counts after scaling, however | |
462 during updating of the profile information numerical error may | |
463 accumulate into quite large errors. | |
464 | |
465 @findex REG_BR_PROB_BASE, EDGE_FREQUENCY | |
466 Each edge also contains a branch probability field: an integer in the | |
467 range from 0 to @code{REG_BR_PROB_BASE}. It represents probability of | |
468 passing control from the end of the @code{src} basic block to the | |
469 @code{dest} basic block, i.e.@: the probability that control will flow | |
111 | 470 along this edge. The @code{EDGE_FREQUENCY} macro is available to |
0 | 471 compute how frequently a given edge is taken. There is a @code{count} |
472 field for each edge as well, representing same information as for a | |
473 basic block. | |
474 | |
475 The basic block frequencies are not represented in the instruction | |
476 stream, but in the RTL representation the edge frequencies are | |
477 represented for conditional jumps (via the @code{REG_BR_PROB} | |
478 macro) since they are used when instructions are output to the | |
479 assembly file and the flow graph is no longer maintained. | |
480 | |
481 @cindex reverse probability | |
482 The probability that control flow arrives via a given edge to its | |
483 destination basic block is called @dfn{reverse probability} and is not | |
484 directly represented, but it may be easily computed from frequencies | |
485 of basic blocks. | |
486 | |
487 @findex redirect_edge_and_branch | |
488 Updating profile information is a delicate task that can unfortunately | |
489 not be easily integrated with the CFG manipulation API@. Many of the | |
490 functions and hooks to modify the CFG, such as | |
491 @code{redirect_edge_and_branch}, do not have enough information to | |
492 easily update the profile, so updating it is in the majority of cases | |
493 left up to the caller. It is difficult to uncover bugs in the profile | |
494 updating code, because they manifest themselves only by producing | |
495 worse code, and checking profile consistency is not possible because | |
496 of numeric error accumulation. Hence special attention needs to be | |
497 given to this issue in each pass that modifies the CFG@. | |
498 | |
499 @findex REG_BR_PROB_BASE, BB_FREQ_BASE, count | |
500 It is important to point out that @code{REG_BR_PROB_BASE} and | |
501 @code{BB_FREQ_BASE} are both set low enough to be possible to compute | |
502 second power of any frequency or probability in the flow graph, it is | |
503 not possible to even square the @code{count} field, as modern CPUs are | |
504 fast enough to execute $2^32$ operations quickly. | |
505 | |
506 | |
507 @node Maintaining the CFG | |
508 @section Maintaining the CFG | |
509 @findex cfghooks.h | |
510 | |
511 An important task of each compiler pass is to keep both the control | |
512 flow graph and all profile information up-to-date. Reconstruction of | |
513 the control flow graph after each pass is not an option, since it may be | |
514 very expensive and lost profile information cannot be reconstructed at | |
515 all. | |
516 | |
517 GCC has two major intermediate representations, and both use the | |
518 @code{basic_block} and @code{edge} data types to represent control | |
519 flow. Both representations share as much of the CFG maintenance code | |
520 as possible. For each representation, a set of @dfn{hooks} is defined | |
521 so that each representation can provide its own implementation of CFG | |
522 manipulation routines when necessary. These hooks are defined in | |
523 @file{cfghooks.h}. There are hooks for almost all common CFG | |
524 manipulations, including block splitting and merging, edge redirection | |
525 and creating and deleting basic blocks. These hooks should provide | |
526 everything you need to maintain and manipulate the CFG in both the RTL | |
111 | 527 and @code{GIMPLE} representation. |
0 | 528 |
529 At the moment, the basic block boundaries are maintained transparently | |
530 when modifying instructions, so there rarely is a need to move them | |
531 manually (such as in case someone wants to output instruction outside | |
532 basic block explicitly). | |
533 | |
111 | 534 @findex BLOCK_FOR_INSN, gimple_bb |
0 | 535 In the RTL representation, each instruction has a |
536 @code{BLOCK_FOR_INSN} value that represents pointer to the basic block | |
111 | 537 that contains the instruction. In the @code{GIMPLE} representation, the |
538 function @code{gimple_bb} returns a pointer to the basic block | |
0 | 539 containing the queried statement. |
540 | |
111 | 541 @cindex GIMPLE statement iterators |
542 When changes need to be applied to a function in its @code{GIMPLE} | |
543 representation, @dfn{GIMPLE statement iterators} should be used. These | |
0 | 544 iterators provide an integrated abstraction of the flow graph and the |
545 instruction stream. Block statement iterators are constructed using | |
111 | 546 the @code{gimple_stmt_iterator} data structure and several modifiers are |
0 | 547 available, including the following: |
548 | |
549 @ftable @code | |
111 | 550 @item gsi_start |
551 This function initializes a @code{gimple_stmt_iterator} that points to | |
0 | 552 the first non-empty statement in a basic block. |
553 | |
111 | 554 @item gsi_last |
555 This function initializes a @code{gimple_stmt_iterator} that points to | |
0 | 556 the last statement in a basic block. |
557 | |
111 | 558 @item gsi_end_p |
559 This predicate is @code{true} if a @code{gimple_stmt_iterator} | |
0 | 560 represents the end of a basic block. |
561 | |
111 | 562 @item gsi_next |
563 This function takes a @code{gimple_stmt_iterator} and makes it point to | |
0 | 564 its successor. |
565 | |
111 | 566 @item gsi_prev |
567 This function takes a @code{gimple_stmt_iterator} and makes it point to | |
0 | 568 its predecessor. |
569 | |
111 | 570 @item gsi_insert_after |
571 This function inserts a statement after the @code{gimple_stmt_iterator} | |
0 | 572 passed in. The final parameter determines whether the statement |
573 iterator is updated to point to the newly inserted statement, or left | |
574 pointing to the original statement. | |
575 | |
111 | 576 @item gsi_insert_before |
577 This function inserts a statement before the @code{gimple_stmt_iterator} | |
0 | 578 passed in. The final parameter determines whether the statement |
579 iterator is updated to point to the newly inserted statement, or left | |
580 pointing to the original statement. | |
581 | |
111 | 582 @item gsi_remove |
583 This function removes the @code{gimple_stmt_iterator} passed in and | |
0 | 584 rechains the remaining statements in a basic block, if any. |
585 @end ftable | |
586 | |
587 @findex BB_HEAD, BB_END | |
588 In the RTL representation, the macros @code{BB_HEAD} and @code{BB_END} | |
589 may be used to get the head and end @code{rtx} of a basic block. No | |
590 abstract iterators are defined for traversing the insn chain, but you | |
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
591 can just use @code{NEXT_INSN} and @code{PREV_INSN} instead. @xref{Insns}. |
0 | 592 |
593 @findex purge_dead_edges | |
594 Usually a code manipulating pass simplifies the instruction stream and | |
595 the flow of control, possibly eliminating some edges. This may for | |
596 example happen when a conditional jump is replaced with an | |
111 | 597 unconditional jump. Updating of edges |
0 | 598 is not transparent and each optimization pass is required to do so |
599 manually. However only few cases occur in practice. The pass may | |
600 call @code{purge_dead_edges} on a given basic block to remove | |
601 superfluous edges, if any. | |
602 | |
603 @findex redirect_edge_and_branch, redirect_jump | |
604 Another common scenario is redirection of branch instructions, but | |
605 this is best modeled as redirection of edges in the control flow graph | |
606 and thus use of @code{redirect_edge_and_branch} is preferred over more | |
607 low level functions, such as @code{redirect_jump} that operate on RTL | |
608 chain only. The CFG hooks defined in @file{cfghooks.h} should provide | |
609 the complete API required for manipulating and maintaining the CFG@. | |
610 | |
611 @findex split_block | |
612 It is also possible that a pass has to insert control flow instruction | |
613 into the middle of a basic block, thus creating an entry point in the | |
614 middle of the basic block, which is impossible by definition: The | |
615 block must be split to make sure it only has one entry point, i.e.@: the | |
616 head of the basic block. The CFG hook @code{split_block} may be used | |
617 when an instruction in the middle of a basic block has to become the | |
618 target of a jump or branch instruction. | |
619 | |
620 @findex insert_insn_on_edge | |
621 @findex commit_edge_insertions | |
111 | 622 @findex gsi_insert_on_edge |
623 @findex gsi_commit_edge_inserts | |
0 | 624 @cindex edge splitting |
625 For a global optimizer, a common operation is to split edges in the | |
626 flow graph and insert instructions on them. In the RTL | |
627 representation, this can be easily done using the | |
628 @code{insert_insn_on_edge} function that emits an instruction | |
629 ``on the edge'', caching it for a later @code{commit_edge_insertions} | |
630 call that will take care of moving the inserted instructions off the | |
631 edge into the instruction stream contained in a basic block. This | |
632 includes the creation of new basic blocks where needed. In the | |
111 | 633 @code{GIMPLE} representation, the equivalent functions are |
634 @code{gsi_insert_on_edge} which inserts a block statement | |
635 iterator on an edge, and @code{gsi_commit_edge_inserts} which flushes | |
0 | 636 the instruction to actual instruction stream. |
637 | |
111 | 638 @findex verify_flow_info |
639 @cindex CFG verification | |
640 While debugging the optimization pass, the @code{verify_flow_info} | |
0 | 641 function may be useful to find bugs in the control flow graph updating |
642 code. | |
643 | |
644 | |
645 @node Liveness information | |
646 @section Liveness information | |
647 @cindex Liveness representation | |
648 Liveness information is useful to determine whether some register is | |
649 ``live'' at given point of program, i.e.@: that it contains a value that | |
650 may be used at a later point in the program. This information is | |
651 used, for instance, during register allocation, as the pseudo | |
652 registers only need to be assigned to a unique hard register or to a | |
653 stack slot if they are live. The hard registers and stack slots may | |
111 | 654 be freely reused for other values when a register is dead. |
0 | 655 |
656 Liveness information is available in the back end starting with | |
657 @code{pass_df_initialize} and ending with @code{pass_df_finish}. Three | |
658 flavors of live analysis are available: With @code{LR}, it is possible | |
659 to determine at any point @code{P} in the function if the register may be | |
660 used on some path from @code{P} to the end of the function. With | |
661 @code{UR}, it is possible to determine if there is a path from the | |
111 | 662 beginning of the function to @code{P} that defines the variable. |
0 | 663 @code{LIVE} is the intersection of the @code{LR} and @code{UR} and a |
664 variable is live at @code{P} if there is both an assignment that reaches | |
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
665 it from the beginning of the function and a use that can be reached on |
0 | 666 some path from @code{P} to the end of the function. |
667 | |
668 In general @code{LIVE} is the most useful of the three. The macros | |
669 @code{DF_[LR,UR,LIVE]_[IN,OUT]} can be used to access this information. | |
670 The macros take a basic block number and return a bitmap that is indexed | |
671 by the register number. This information is only guaranteed to be up to | |
672 date after calls are made to @code{df_analyze}. See the file | |
111 | 673 @code{df-core.c} for details on using the dataflow. |
0 | 674 |
675 | |
676 @findex REG_DEAD, REG_UNUSED | |
677 The liveness information is stored partly in the RTL instruction stream | |
678 and partly in the flow graph. Local information is stored in the | |
679 instruction stream: Each instruction may contain @code{REG_DEAD} notes | |
680 representing that the value of a given register is no longer needed, or | |
681 @code{REG_UNUSED} notes representing that the value computed by the | |
682 instruction is never used. The second is useful for instructions | |
683 computing multiple values at once. | |
684 |