1169689Skan@c -*-texinfo-*- 2169689Skan@c Copyright (C) 2001, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan@c This is part of the GCC manual. 4169689Skan@c For copying conditions, see the file gcc.texi. 5169689Skan 6169689Skan@c --------------------------------------------------------------------- 7169689Skan@c Control Flow Graph 8169689Skan@c --------------------------------------------------------------------- 9169689Skan 10169689Skan@node Control Flow 11169689Skan@chapter Control Flow Graph 12169689Skan@cindex CFG, Control Flow Graph 13169689Skan@findex basic-block.h 14169689Skan 15169689SkanA control flow graph (CFG) is a data structure built on top of the 16169689Skanintermediate code representation (the RTL or @code{tree} instruction 17169689Skanstream) abstracting the control flow behavior of a function that is 18169689Skanbeing compiled. The CFG is a directed graph where the vertices 19169689Skanrepresent basic blocks and edges represent possible transfer of 20169689Skancontrol flow from one basic block to another. The data structures 21169689Skanused to represent the control flow graph are defined in 22169689Skan@file{basic-block.h}. 23169689Skan 24169689Skan@menu 25169689Skan* Basic Blocks:: The definition and representation of basic blocks. 26169689Skan* Edges:: Types of edges and their representation. 27169689Skan* Profile information:: Representation of frequencies and probabilities. 28169689Skan* Maintaining the CFG:: Keeping the control flow graph and up to date. 29169689Skan* Liveness information:: Using and maintaining liveness information. 30169689Skan@end menu 31169689Skan 32169689Skan 33169689Skan@node Basic Blocks 34169689Skan@section Basic Blocks 35169689Skan 36169689Skan@cindex basic block 37169689Skan@findex basic_block 38169689SkanA basic block is a straight-line sequence of code with only one entry 39169689Skanpoint and only one exit. In GCC, basic blocks are represented using 40169689Skanthe @code{basic_block} data type. 41169689Skan 42169689Skan@findex next_bb, prev_bb, FOR_EACH_BB 43169689SkanTwo pointer members of the @code{basic_block} structure are the 44169689Skanpointers @code{next_bb} and @code{prev_bb}. These are used to keep 45169689Skandoubly linked chain of basic blocks in the same order as the 46169689Skanunderlying instruction stream. The chain of basic blocks is updated 47169689Skantransparently by the provided API for manipulating the CFG@. The macro 48169689Skan@code{FOR_EACH_BB} can be used to visit all the basic blocks in 49169689Skanlexicographical order. Dominator traversals are also possible using 50169689Skan@code{walk_dominator_tree}. Given two basic blocks A and B, block A 51169689Skandominates block B if A is @emph{always} executed before B@. 52169689Skan 53169689Skan@findex BASIC_BLOCK 54169689SkanThe @code{BASIC_BLOCK} array contains all basic blocks in an 55169689Skanunspecified order. Each @code{basic_block} structure has a field 56169689Skanthat holds a unique integer identifier @code{index} that is the 57169689Skanindex of the block in the @code{BASIC_BLOCK} array. 58169689SkanThe total number of basic blocks in the function is 59169689Skan@code{n_basic_blocks}. Both the basic block indices and 60169689Skanthe total number of basic blocks may vary during the compilation 61169689Skanprocess, as passes reorder, create, duplicate, and destroy basic 62169689Skanblocks. The index for any block should never be greater than 63169689Skan@code{last_basic_block}. 64169689Skan 65169689Skan@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR 66169689SkanSpecial basic blocks represent possible entry and exit points of a 67169689Skanfunction. These blocks are called @code{ENTRY_BLOCK_PTR} and 68169689Skan@code{EXIT_BLOCK_PTR}. These blocks do not contain any code, and are 69169689Skannot elements of the @code{BASIC_BLOCK} array. Therefore they have 70169689Skanbeen assigned unique, negative index numbers. 71169689Skan 72169689SkanEach @code{basic_block} also contains pointers to the first 73169689Skaninstruction (the @dfn{head}) and the last instruction (the @dfn{tail}) 74169689Skanor @dfn{end} of the instruction stream contained in a basic block. In 75169689Skanfact, since the @code{basic_block} data type is used to represent 76169689Skanblocks in both major intermediate representations of GCC (@code{tree} 77169689Skanand RTL), there are pointers to the head and end of a basic block for 78169689Skanboth representations. 79169689Skan 80169689Skan@findex NOTE_INSN_BASIC_BLOCK, CODE_LABEL, notes 81169689SkanFor RTL, these pointers are @code{rtx head, end}. In the RTL function 82169689Skanrepresentation, the head pointer always points either to a 83169689Skan@code{NOTE_INSN_BASIC_BLOCK} or to a @code{CODE_LABEL}, if present. 84169689SkanIn the RTL representation of a function, the instruction stream 85169689Skancontains not only the ``real'' instructions, but also @dfn{notes}. 86169689SkanAny function that moves or duplicates the basic blocks needs 87169689Skanto take care of updating of these notes. Many of these notes expect 88169689Skanthat the instruction stream consists of linear regions, making such 89169689Skanupdates difficult. The @code{NOTE_INSN_BASIC_BLOCK} note is the only 90169689Skankind of note that may appear in the instruction stream contained in a 91169689Skanbasic block. The instruction stream of a basic block always follows a 92169689Skan@code{NOTE_INSN_BASIC_BLOCK}, but zero or more @code{CODE_LABEL} 93169689Skannodes can precede the block note. A basic block ends by control flow 94169689Skaninstruction or last instruction before following @code{CODE_LABEL} or 95169689Skan@code{NOTE_INSN_BASIC_BLOCK}. A @code{CODE_LABEL} cannot appear in 96169689Skanthe instruction stream of a basic block. 97169689Skan 98169689Skan@findex can_fallthru 99169689Skan@cindex table jump 100169689SkanIn addition to notes, the jump table vectors are also represented as 101169689Skan``pseudo-instructions'' inside the insn stream. These vectors never 102169689Skanappear in the basic block and should always be placed just after the 103169689Skantable jump instructions referencing them. After removing the 104169689Skantable-jump it is often difficult to eliminate the code computing the 105169689Skanaddress and referencing the vector, so cleaning up these vectors is 106169689Skanpostponed until after liveness analysis. Thus the jump table vectors 107169689Skanmay appear in the insn stream unreferenced and without any purpose. 108169689SkanBefore any edge is made @dfn{fall-thru}, the existence of such 109169689Skanconstruct in the way needs to be checked by calling 110169689Skan@code{can_fallthru} function. 111169689Skan 112169689Skan@cindex block statement iterators 113169689SkanFor the @code{tree} representation, the head and end of the basic block 114169689Skanare being pointed to by the @code{stmt_list} field, but this special 115169689Skan@code{tree} should never be referenced directly. Instead, at the tree 116169689Skanlevel abstract containers and iterators are used to access statements 117169689Skanand expressions in basic blocks. These iterators are called 118169689Skan@dfn{block statement iterators} (BSIs). Grep for @code{^bsi} 119169689Skanin the various @file{tree-*} files. 120169689SkanThe following snippet will pretty-print all the statements of the 121169689Skanprogram in the GIMPLE representation. 122169689Skan 123169689Skan@smallexample 124169689SkanFOR_EACH_BB (bb) 125169689Skan @{ 126169689Skan block_stmt_iterator si; 127169689Skan 128169689Skan for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 129169689Skan @{ 130169689Skan tree stmt = bsi_stmt (si); 131169689Skan print_generic_stmt (stderr, stmt, 0); 132169689Skan @} 133169689Skan @} 134169689Skan@end smallexample 135169689Skan 136169689Skan 137169689Skan@node Edges 138169689Skan@section Edges 139169689Skan 140169689Skan@cindex edge in the flow graph 141169689Skan@findex edge 142169689SkanEdges represent possible control flow transfers from the end of some 143169689Skanbasic block A to the head of another basic block B@. We say that A is 144169689Skana predecessor of B, and B is a successor of A@. Edges are represented 145169689Skanin GCC with the @code{edge} data type. Each @code{edge} acts as a 146169689Skanlink between two basic blocks: the @code{src} member of an edge 147169689Skanpoints to the predecessor basic block of the @code{dest} basic block. 148169689SkanThe members @code{preds} and @code{succs} of the @code{basic_block} data 149169689Skantype point to type-safe vectors of edges to the predecessors and 150169689Skansuccessors of the block. 151169689Skan 152169689Skan@cindex edge iterators 153169689SkanWhen walking the edges in an edge vector, @dfn{edge iterators} should 154169689Skanbe used. Edge iterators are constructed using the 155169689Skan@code{edge_iterator} data structure and several methods are available 156169689Skanto operate on them: 157169689Skan 158169689Skan@ftable @code 159169689Skan@item ei_start 160169689SkanThis function initializes an @code{edge_iterator} that points to the 161169689Skanfirst edge in a vector of edges. 162169689Skan 163169689Skan@item ei_last 164169689SkanThis function initializes an @code{edge_iterator} that points to the 165169689Skanlast edge in a vector of edges. 166169689Skan 167169689Skan@item ei_end_p 168169689SkanThis predicate is @code{true} if an @code{edge_iterator} represents 169169689Skanthe last edge in an edge vector. 170169689Skan 171169689Skan@item ei_one_before_end_p 172169689SkanThis predicate is @code{true} if an @code{edge_iterator} represents 173169689Skanthe second last edge in an edge vector. 174169689Skan 175169689Skan@item ei_next 176169689SkanThis function takes a pointer to an @code{edge_iterator} and makes it 177169689Skanpoint to the next edge in the sequence. 178169689Skan 179169689Skan@item ei_prev 180169689SkanThis function takes a pointer to an @code{edge_iterator} and makes it 181169689Skanpoint to the previous edge in the sequence. 182169689Skan 183169689Skan@item ei_edge 184169689SkanThis function returns the @code{edge} currently pointed to by an 185169689Skan@code{edge_iterator}. 186169689Skan 187169689Skan@item ei_safe_safe 188169689SkanThis function returns the @code{edge} currently pointed to by an 189169689Skan@code{edge_iterator}, but returns @code{NULL} if the iterator is 190169689Skanpointing at the end of the sequence. This function has been provided 191169689Skanfor existing code makes the assumption that a @code{NULL} edge 192169689Skanindicates the end of the sequence. 193169689Skan 194169689Skan@end ftable 195169689Skan 196169689SkanThe convenience macro @code{FOR_EACH_EDGE} can be used to visit all of 197169689Skanthe edges in a sequence of predecessor or successor edges. It must 198169689Skannot be used when an element might be removed during the traversal, 199169689Skanotherwise elements will be missed. Here is an example of how to use 200169689Skanthe macro: 201169689Skan 202169689Skan@smallexample 203169689Skanedge e; 204169689Skanedge_iterator ei; 205169689Skan 206169689SkanFOR_EACH_EDGE (e, ei, bb->succs) 207169689Skan @{ 208169689Skan if (e->flags & EDGE_FALLTHRU) 209169689Skan break; 210169689Skan @} 211169689Skan@end smallexample 212169689Skan 213169689Skan@findex fall-thru 214169689SkanThere are various reasons why control flow may transfer from one block 215169689Skanto another. One possibility is that some instruction, for example a 216169689Skan@code{CODE_LABEL}, in a linearized instruction stream just always 217169689Skanstarts a new basic block. In this case a @dfn{fall-thru} edge links 218169689Skanthe basic block to the first following basic block. But there are 219169689Skanseveral other reasons why edges may be created. The @code{flags} 220169689Skanfield of the @code{edge} data type is used to store information 221169689Skanabout the type of edge we are dealing with. Each edge is of one of 222169689Skanthe following types: 223169689Skan 224169689Skan@table @emph 225169689Skan@item jump 226169689SkanNo type flags are set for edges corresponding to jump instructions. 227169689SkanThese edges are used for unconditional or conditional jumps and in 228169689SkanRTL also for table jumps. They are the easiest to manipulate as they 229169689Skanmay be freely redirected when the flow graph is not in SSA form. 230169689Skan 231169689Skan@item fall-thru 232169689Skan@findex EDGE_FALLTHRU, force_nonfallthru 233169689SkanFall-thru edges are present in case where the basic block may continue 234169689Skanexecution to the following one without branching. These edges have 235169689Skanthe @code{EDGE_FALLTHRU} flag set. Unlike other types of edges, these 236169689Skanedges must come into the basic block immediately following in the 237169689Skaninstruction stream. The function @code{force_nonfallthru} is 238169689Skanavailable to insert an unconditional jump in the case that redirection 239169689Skanis needed. Note that this may require creation of a new basic block. 240169689Skan 241169689Skan@item exception handling 242169689Skan@cindex exception handling 243169689Skan@findex EDGE_ABNORMAL, EDGE_EH 244169689SkanException handling edges represent possible control transfers from a 245169689Skantrapping instruction to an exception handler. The definition of 246169689Skan``trapping'' varies. In C++, only function calls can throw, but for 247169689SkanJava, exceptions like division by zero or segmentation fault are 248169689Skandefined and thus each instruction possibly throwing this kind of 249169689Skanexception needs to be handled as control flow instruction. Exception 250169689Skanedges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set. 251169689Skan 252169689Skan@findex purge_dead_edges 253169689SkanWhen updating the instruction stream it is easy to change possibly 254169689Skantrapping instruction to non-trapping, by simply removing the exception 255169689Skanedge. The opposite conversion is difficult, but should not happen 256169689Skananyway. The edges can be eliminated via @code{purge_dead_edges} call. 257169689Skan 258169689Skan@findex REG_EH_REGION, EDGE_ABNORMAL_CALL 259169689SkanIn the RTL representation, the destination of an exception edge is 260169689Skanspecified by @code{REG_EH_REGION} note attached to the insn. 261169689SkanIn case of a trapping call the @code{EDGE_ABNORMAL_CALL} flag is set 262169689Skantoo. In the @code{tree} representation, this extra flag is not set. 263169689Skan 264169689Skan@findex may_trap_p, tree_could_trap_p 265169689SkanIn the RTL representation, the predicate @code{may_trap_p} may be used 266169689Skanto check whether instruction still may trap or not. For the tree 267169689Skanrepresentation, the @code{tree_could_trap_p} predicate is available, 268169689Skanbut this predicate only checks for possible memory traps, as in 269169689Skandereferencing an invalid pointer location. 270169689Skan 271169689Skan 272169689Skan@item sibling calls 273169689Skan@cindex sibling call 274169689Skan@findex EDGE_ABNORMAL, EDGE_SIBCALL 275169689SkanSibling calls or tail calls terminate the function in a non-standard 276169689Skanway and thus an edge to the exit must be present. 277169689Skan@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case. 278169689SkanThese edges only exist in the RTL representation. 279169689Skan 280169689Skan@item computed jumps 281169689Skan@cindex computed jump 282169689Skan@findex EDGE_ABNORMAL 283169689SkanComputed jumps contain edges to all labels in the function referenced 284169689Skanfrom the code. All those edges have @code{EDGE_ABNORMAL} flag set. 285169689SkanThe edges used to represent computed jumps often cause compile time 286169689Skanperformance problems, since functions consisting of many taken labels 287169689Skanand many computed jumps may have @emph{very} dense flow graphs, so 288169689Skanthese edges need to be handled with special care. During the earlier 289169689Skanstages of the compilation process, GCC tries to avoid such dense flow 290169689Skangraphs by factoring computed jumps. For example, given the following 291169689Skanseries of jumps, 292169689Skan 293169689Skan@smallexample 294169689Skan goto *x; 295169689Skan [ ... ] 296169689Skan 297169689Skan goto *x; 298169689Skan [ ... ] 299169689Skan 300169689Skan goto *x; 301169689Skan [ ... ] 302169689Skan@end smallexample 303169689Skan 304169689Skan@noindent 305169689Skanfactoring the computed jumps results in the following code sequence 306169689Skanwhich has a much simpler flow graph: 307169689Skan 308169689Skan@smallexample 309169689Skan goto y; 310169689Skan [ ... ] 311169689Skan 312169689Skan goto y; 313169689Skan [ ... ] 314169689Skan 315169689Skan goto y; 316169689Skan [ ... ] 317169689Skan 318169689Skany: 319169689Skan goto *x; 320169689Skan@end smallexample 321169689Skan 322169689SkanHowever, the classic problem with this transformation is that it has a 323169689Skanruntime cost in there resulting code: An extra jump. Therefore, the 324169689Skancomputed jumps are un-factored in the later passes of the compiler. 325169689SkanBe aware of that when you work on passes in that area. There have 326169689Skanbeen numerous examples already where the compile time for code with 327169689Skanunfactored computed jumps caused some serious headaches. 328169689Skan 329169689Skan@item nonlocal goto handlers 330169689Skan@cindex nonlocal goto handler 331169689Skan@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL 332169689SkanGCC allows nested functions to return into caller using a @code{goto} 333169689Skanto a label passed to as an argument to the callee. The labels passed 334169689Skanto nested functions contain special code to cleanup after function 335169689Skancall. Such sections of code are referred to as ``nonlocal goto 336169689Skanreceivers''. If a function contains such nonlocal goto receivers, an 337169689Skanedge from the call to the label is created with the 338169689Skan@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set. 339169689Skan 340169689Skan@item function entry points 341169689Skan@cindex function entry point, alternate function entry point 342169689Skan@findex LABEL_ALTERNATE_NAME 343169689SkanBy definition, execution of function starts at basic block 0, so there 344169689Skanis always an edge from the @code{ENTRY_BLOCK_PTR} to basic block 0. 345169689SkanThere is no @code{tree} representation for alternate entry points at 346169689Skanthis moment. In RTL, alternate entry points are specified by 347169689Skan@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined. This 348169689Skanfeature is currently used for multiple entry point prologues and is 349169689Skanlimited to post-reload passes only. This can be used by back-ends to 350169689Skanemit alternate prologues for functions called from different contexts. 351169689SkanIn future full support for multiple entry functions defined by Fortran 352169689Skan90 needs to be implemented. 353169689Skan 354169689Skan@item function exits 355169689SkanIn the pre-reload representation a function terminates after the last 356169689Skaninstruction in the insn chain and no explicit return instructions are 357169689Skanused. This corresponds to the fall-thru edge into exit block. After 358169689Skanreload, optimal RTL epilogues are used that use explicit (conditional) 359169689Skanreturn instructions that are represented by edges with no flags set. 360169689Skan 361169689Skan@end table 362169689Skan 363169689Skan 364169689Skan@node Profile information 365169689Skan@section Profile information 366169689Skan 367169689Skan@cindex profile representation 368169689SkanIn many cases a compiler must make a choice whether to trade speed in 369169689Skanone part of code for speed in another, or to trade code size for code 370169689Skanspeed. In such cases it is useful to know information about how often 371169689Skansome given block will be executed. That is the purpose for 372169689Skanmaintaining profile within the flow graph. 373169689SkanGCC can handle profile information obtained through @dfn{profile 374169689Skanfeedback}, but it can also estimate branch probabilities based on 375169689Skanstatics and heuristics. 376169689Skan 377169689Skan@cindex profile feedback 378169689SkanThe feedback based profile is produced by compiling the program with 379169689Skaninstrumentation, executing it on a train run and reading the numbers 380169689Skanof executions of basic blocks and edges back to the compiler while 381169689Skanre-compiling the program to produce the final executable. This method 382169689Skanprovides very accurate information about where a program spends most 383169689Skanof its time on the train run. Whether it matches the average run of 384169689Skancourse depends on the choice of train data set, but several studies 385169689Skanhave shown that the behavior of a program usually changes just 386169689Skanmarginally over different data sets. 387169689Skan 388169689Skan@cindex Static profile estimation 389169689Skan@cindex branch prediction 390169689Skan@findex predict.def 391169689SkanWhen profile feedback is not available, the compiler may be asked to 392169689Skanattempt to predict the behavior of each branch in the program using a 393169689Skanset of heuristics (see @file{predict.def} for details) and compute 394169689Skanestimated frequencies of each basic block by propagating the 395169689Skanprobabilities over the graph. 396169689Skan 397169689Skan@findex frequency, count, BB_FREQ_BASE 398169689SkanEach @code{basic_block} contains two integer fields to represent 399169689Skanprofile information: @code{frequency} and @code{count}. The 400169689Skan@code{frequency} is an estimation how often is basic block executed 401169689Skanwithin a function. It is represented as an integer scaled in the 402169689Skanrange from 0 to @code{BB_FREQ_BASE}. The most frequently executed 403169689Skanbasic block in function is initially set to @code{BB_FREQ_BASE} and 404169689Skanthe rest of frequencies are scaled accordingly. During optimization, 405169689Skanthe frequency of the most frequent basic block can both decrease (for 406169689Skaninstance by loop unrolling) or grow (for instance by cross-jumping 407169689Skanoptimization), so scaling sometimes has to be performed multiple 408169689Skantimes. 409169689Skan 410169689Skan@findex gcov_type 411169689SkanThe @code{count} contains hard-counted numbers of execution measured 412169689Skanduring training runs and is nonzero only when profile feedback is 413169689Skanavailable. This value is represented as the host's widest integer 414169689Skan(typically a 64 bit integer) of the special type @code{gcov_type}. 415169689Skan 416169689SkanMost optimization passes can use only the frequency information of a 417169689Skanbasic block, but a few passes may want to know hard execution counts. 418169689SkanThe frequencies should always match the counts after scaling, however 419169689Skanduring updating of the profile information numerical error may 420169689Skanaccumulate into quite large errors. 421169689Skan 422169689Skan@findex REG_BR_PROB_BASE, EDGE_FREQUENCY 423169689SkanEach edge also contains a branch probability field: an integer in the 424169689Skanrange from 0 to @code{REG_BR_PROB_BASE}. It represents probability of 425169689Skanpassing control from the end of the @code{src} basic block to the 426169689Skan@code{dest} basic block, i.e.@: the probability that control will flow 427169689Skanalong this edge. The @code{EDGE_FREQUENCY} macro is available to 428169689Skancompute how frequently a given edge is taken. There is a @code{count} 429169689Skanfield for each edge as well, representing same information as for a 430169689Skanbasic block. 431169689Skan 432169689SkanThe basic block frequencies are not represented in the instruction 433169689Skanstream, but in the RTL representation the edge frequencies are 434169689Skanrepresented for conditional jumps (via the @code{REG_BR_PROB} 435169689Skanmacro) since they are used when instructions are output to the 436169689Skanassembly file and the flow graph is no longer maintained. 437169689Skan 438169689Skan@cindex reverse probability 439169689SkanThe probability that control flow arrives via a given edge to its 440169689Skandestination basic block is called @dfn{reverse probability} and is not 441169689Skandirectly represented, but it may be easily computed from frequencies 442169689Skanof basic blocks. 443169689Skan 444169689Skan@findex redirect_edge_and_branch 445169689SkanUpdating profile information is a delicate task that can unfortunately 446169689Skannot be easily integrated with the CFG manipulation API@. Many of the 447169689Skanfunctions and hooks to modify the CFG, such as 448169689Skan@code{redirect_edge_and_branch}, do not have enough information to 449169689Skaneasily update the profile, so updating it is in the majority of cases 450169689Skanleft up to the caller. It is difficult to uncover bugs in the profile 451169689Skanupdating code, because they manifest themselves only by producing 452169689Skanworse code, and checking profile consistency is not possible because 453169689Skanof numeric error accumulation. Hence special attention needs to be 454169689Skangiven to this issue in each pass that modifies the CFG@. 455169689Skan 456169689Skan@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count 457169689SkanIt is important to point out that @code{REG_BR_PROB_BASE} and 458169689Skan@code{BB_FREQ_BASE} are both set low enough to be possible to compute 459169689Skansecond power of any frequency or probability in the flow graph, it is 460169689Skannot possible to even square the @code{count} field, as modern CPUs are 461169689Skanfast enough to execute $2^32$ operations quickly. 462169689Skan 463169689Skan 464169689Skan@node Maintaining the CFG 465169689Skan@section Maintaining the CFG 466169689Skan@findex cfghooks.h 467169689Skan 468169689SkanAn important task of each compiler pass is to keep both the control 469169689Skanflow graph and all profile information up-to-date. Reconstruction of 470169689Skanthe control flow graph after each pass is not an option, since it may be 471169689Skanvery expensive and lost profile information cannot be reconstructed at 472169689Skanall. 473169689Skan 474169689SkanGCC has two major intermediate representations, and both use the 475169689Skan@code{basic_block} and @code{edge} data types to represent control 476169689Skanflow. Both representations share as much of the CFG maintenance code 477169689Skanas possible. For each representation, a set of @dfn{hooks} is defined 478169689Skanso that each representation can provide its own implementation of CFG 479169689Skanmanipulation routines when necessary. These hooks are defined in 480169689Skan@file{cfghooks.h}. There are hooks for almost all common CFG 481169689Skanmanipulations, including block splitting and merging, edge redirection 482169689Skanand creating and deleting basic blocks. These hooks should provide 483169689Skaneverything you need to maintain and manipulate the CFG in both the RTL 484169689Skanand @code{tree} representation. 485169689Skan 486169689SkanAt the moment, the basic block boundaries are maintained transparently 487169689Skanwhen modifying instructions, so there rarely is a need to move them 488169689Skanmanually (such as in case someone wants to output instruction outside 489169689Skanbasic block explicitly). 490169689SkanOften the CFG may be better viewed as integral part of instruction 491169689Skanchain, than structure built on the top of it. However, in principle 492169689Skanthe control flow graph for the @code{tree} representation is 493169689Skan@emph{not} an integral part of the representation, in that a function 494169689Skantree may be expanded without first building a flow graph for the 495169689Skan@code{tree} representation at all. This happens when compiling 496169689Skanwithout any @code{tree} optimization enabled. When the @code{tree} 497169689Skanoptimizations are enabled and the instruction stream is rewritten in 498169689SkanSSA form, the CFG is very tightly coupled with the instruction stream. 499169689SkanIn particular, statement insertion and removal has to be done with 500169689Skancare. In fact, the whole @code{tree} representation can not be easily 501169689Skanused or maintained without proper maintenance of the CFG 502169689Skansimultaneously. 503169689Skan 504169689Skan@findex BLOCK_FOR_INSN, bb_for_stmt 505169689SkanIn the RTL representation, each instruction has a 506169689Skan@code{BLOCK_FOR_INSN} value that represents pointer to the basic block 507169689Skanthat contains the instruction. In the @code{tree} representation, the 508169689Skanfunction @code{bb_for_stmt} returns a pointer to the basic block 509169689Skancontaining the queried statement. 510169689Skan 511169689Skan@cindex block statement iterators 512169689SkanWhen changes need to be applied to a function in its @code{tree} 513169689Skanrepresentation, @dfn{block statement iterators} should be used. These 514169689Skaniterators provide an integrated abstraction of the flow graph and the 515169689Skaninstruction stream. Block statement iterators iterators are 516169689Skanconstructed using the @code{block_stmt_iterator} data structure and 517169689Skanseveral modifier are available, including the following: 518169689Skan 519169689Skan@ftable @code 520169689Skan@item bsi_start 521169689SkanThis function initializes a @code{block_stmt_iterator} that points to 522169689Skanthe first non-empty statement in a basic block. 523169689Skan 524169689Skan@item bsi_last 525169689SkanThis function initializes a @code{block_stmt_iterator} that points to 526169689Skanthe last statement in a basic block. 527169689Skan 528169689Skan@item bsi_end_p 529169689SkanThis predicate is @code{true} if a @code{block_stmt_iterator} 530169689Skanrepresents the end of a basic block. 531169689Skan 532169689Skan@item bsi_next 533169689SkanThis function takes a @code{block_stmt_iterator} and makes it point to 534169689Skanits successor. 535169689Skan 536169689Skan@item bsi_prev 537169689SkanThis function takes a @code{block_stmt_iterator} and makes it point to 538169689Skanits predecessor. 539169689Skan 540169689Skan@item bsi_insert_after 541169689SkanThis function inserts a statement after the @code{block_stmt_iterator} 542169689Skanpassed in. The final parameter determines whether the statement 543169689Skaniterator is updated to point to the newly inserted statement, or left 544169689Skanpointing to the original statement. 545169689Skan 546169689Skan@item bsi_insert_before 547169689SkanThis function inserts a statement before the @code{block_stmt_iterator} 548169689Skanpassed in. The final parameter determines whether the statement 549169689Skaniterator is updated to point to the newly inserted statement, or left 550169689Skanpointing to the original statement. 551169689Skan 552169689Skan@item bsi_remove 553169689SkanThis function removes the @code{block_stmt_iterator} passed in and 554169689Skanrechains the remaining statements in a basic block, if any. 555169689Skan@end ftable 556169689Skan 557169689Skan@findex BB_HEAD, BB_END 558169689SkanIn the RTL representation, the macros @code{BB_HEAD} and @code{BB_END} 559169689Skanmay be used to get the head and end @code{rtx} of a basic block. No 560169689Skanabstract iterators are defined for traversing the insn chain, but you 561169689Skancan just use @code{NEXT_INSN} and @code{PREV_INSN} instead. See 562169689Skan@xref{Insns}. 563169689Skan 564169689Skan@findex purge_dead_edges 565169689SkanUsually a code manipulating pass simplifies the instruction stream and 566169689Skanthe flow of control, possibly eliminating some edges. This may for 567169689Skanexample happen when a conditional jump is replaced with an 568169689Skanunconditional jump, but also when simplifying possibly trapping 569169689Skaninstruction to non-trapping while compiling Java. Updating of edges 570169689Skanis not transparent and each optimization pass is required to do so 571169689Skanmanually. However only few cases occur in practice. The pass may 572169689Skancall @code{purge_dead_edges} on a given basic block to remove 573169689Skansuperfluous edges, if any. 574169689Skan 575169689Skan@findex redirect_edge_and_branch, redirect_jump 576169689SkanAnother common scenario is redirection of branch instructions, but 577169689Skanthis is best modeled as redirection of edges in the control flow graph 578169689Skanand thus use of @code{redirect_edge_and_branch} is preferred over more 579169689Skanlow level functions, such as @code{redirect_jump} that operate on RTL 580169689Skanchain only. The CFG hooks defined in @file{cfghooks.h} should provide 581169689Skanthe complete API required for manipulating and maintaining the CFG@. 582169689Skan 583169689Skan@findex split_block 584169689SkanIt is also possible that a pass has to insert control flow instruction 585169689Skaninto the middle of a basic block, thus creating an entry point in the 586169689Skanmiddle of the basic block, which is impossible by definition: The 587169689Skanblock must be split to make sure it only has one entry point, i.e.@: the 588169689Skanhead of the basic block. The CFG hook @code{split_block} may be used 589169689Skanwhen an instruction in the middle of a basic block has to become the 590169689Skantarget of a jump or branch instruction. 591169689Skan 592169689Skan@findex insert_insn_on_edge 593169689Skan@findex commit_edge_insertions 594169689Skan@findex bsi_insert_on_edge 595169689Skan@findex bsi_commit_edge_inserts 596169689Skan@cindex edge splitting 597169689SkanFor a global optimizer, a common operation is to split edges in the 598169689Skanflow graph and insert instructions on them. In the RTL 599169689Skanrepresentation, this can be easily done using the 600169689Skan@code{insert_insn_on_edge} function that emits an instruction 601169689Skan``on the edge'', caching it for a later @code{commit_edge_insertions} 602169689Skancall that will take care of moving the inserted instructions off the 603169689Skanedge into the instruction stream contained in a basic block. This 604169689Skanincludes the creation of new basic blocks where needed. In the 605169689Skan@code{tree} representation, the equivalent functions are 606169689Skan@code{bsi_insert_on_edge} which inserts a block statement 607169689Skaniterator on an edge, and @code{bsi_commit_edge_inserts} which flushes 608169689Skanthe instruction to actual instruction stream. 609169689Skan 610169689SkanWhile debugging the optimization pass, an @code{verify_flow_info} 611169689Skanfunction may be useful to find bugs in the control flow graph updating 612169689Skancode. 613169689Skan 614169689SkanNote that at present, the representation of control flow in the 615169689Skan@code{tree} representation is discarded before expanding to RTL@. 616169689SkanLong term the CFG should be maintained and ``expanded'' to the 617169689SkanRTL representation along with the function @code{tree} itself. 618169689Skan 619169689Skan 620169689Skan@node Liveness information 621169689Skan@section Liveness information 622169689Skan@cindex Liveness representation 623169689SkanLiveness information is useful to determine whether some register is 624169689Skan``live'' at given point of program, i.e.@: that it contains a value that 625169689Skanmay be used at a later point in the program. This information is 626169689Skanused, for instance, during register allocation, as the pseudo 627169689Skanregisters only need to be assigned to a unique hard register or to a 628169689Skanstack slot if they are live. The hard registers and stack slots may 629169689Skanbe freely reused for other values when a register is dead. 630169689Skan 631169689Skan@findex REG_DEAD, REG_UNUSED 632169689SkanThe liveness information is stored partly in the RTL instruction 633169689Skanstream and partly in the flow graph. Local information is stored in 634169689Skanthe instruction stream: 635169689SkanEach instruction may contain @code{REG_DEAD} notes representing that 636169689Skanthe value of a given register is no longer needed, or 637169689Skan@code{REG_UNUSED} notes representing that the value computed by the 638169689Skaninstruction is never used. The second is useful for instructions 639169689Skancomputing multiple values at once. 640169689Skan 641169689Skan@findex global_live_at_start, global_live_at_end 642169689SkanGlobal liveness information is stored in the control flow graph. 643169689SkanEach basic block contains two bitmaps, @code{global_live_at_start} and 644169689Skan@code{global_live_at_end} representing liveness of each register at 645169689Skanthe entry and exit of the basic block. The file @code{flow.c} 646169689Skancontains functions to compute liveness of each register at any given 647169689Skanplace in the instruction stream using this information. 648169689Skan 649169689Skan@findex BB_DIRTY, clear_bb_flags, update_life_info_in_dirty_blocks 650169689SkanLiveness is expensive to compute and thus it is desirable to keep it 651169689Skanup to date during code modifying passes. This can be easily 652169689Skanaccomplished using the @code{flags} field of a basic block. Functions 653169689Skanmodifying the instruction stream automatically set the @code{BB_DIRTY} 654169689Skanflag of a modifies basic block, so the pass may simply 655169689Skanuse@code{clear_bb_flags} before doing any modifications and then ask 656169689Skanthe data flow module to have liveness updated via the 657169689Skan@code{update_life_info_in_dirty_blocks} function. 658169689Skan 659169689SkanThis scheme works reliably as long as no control flow graph 660169689Skantransformations are done. The task of updating liveness after control 661169689Skanflow graph changes is more difficult as normal iterative data flow 662169689Skananalysis may produce invalid results or get into an infinite cycle 663169689Skanwhen the initial solution is not below the desired one. Only simple 664169689Skantransformations, like splitting basic blocks or inserting on edges, 665169689Skanare safe, as functions to implement them already know how to update 666169689Skanliveness information locally. 667