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