110d565efSmrg@c -*-texinfo-*- 2*ec02198aSmrg@c Copyright (C) 2001-2020 Free Software Foundation, Inc. 310d565efSmrg@c This is part of the GCC manual. 410d565efSmrg@c For copying conditions, see the file gcc.texi. 510d565efSmrg 610d565efSmrg@c --------------------------------------------------------------------- 710d565efSmrg@c Control Flow Graph 810d565efSmrg@c --------------------------------------------------------------------- 910d565efSmrg 1010d565efSmrg@node Control Flow 1110d565efSmrg@chapter Control Flow Graph 1210d565efSmrg@cindex CFG, Control Flow Graph 1310d565efSmrg@findex basic-block.h 1410d565efSmrg 1510d565efSmrgA control flow graph (CFG) is a data structure built on top of the 1610d565efSmrgintermediate code representation (the RTL or @code{GIMPLE} instruction 1710d565efSmrgstream) abstracting the control flow behavior of a function that is 1810d565efSmrgbeing compiled. The CFG is a directed graph where the vertices 1910d565efSmrgrepresent basic blocks and edges represent possible transfer of 2010d565efSmrgcontrol flow from one basic block to another. The data structures 2110d565efSmrgused to represent the control flow graph are defined in 2210d565efSmrg@file{basic-block.h}. 2310d565efSmrg 2410d565efSmrgIn GCC, the representation of control flow is maintained throughout 2510d565efSmrgthe compilation process, from constructing the CFG early in 2610d565efSmrg@code{pass_build_cfg} to @code{pass_free_cfg} (see @file{passes.def}). 2710d565efSmrgThe CFG takes various different modes and may undergo extensive 2810d565efSmrgmanipulations, but the graph is always valid between its construction 2910d565efSmrgand its release. This way, transfer of information such as data flow, 3010d565efSmrga measured profile, or the loop tree, can be propagated through the 3110d565efSmrgpasses pipeline, and even from @code{GIMPLE} to @code{RTL}. 3210d565efSmrg 3310d565efSmrgOften the CFG may be better viewed as integral part of instruction 3410d565efSmrgchain, than structure built on the top of it. Updating the compiler's 3510d565efSmrgintermediate representation for instructions cannot be easily done 3610d565efSmrgwithout proper maintenance of the CFG simultaneously. 3710d565efSmrg 3810d565efSmrg@menu 3910d565efSmrg* Basic Blocks:: The definition and representation of basic blocks. 4010d565efSmrg* Edges:: Types of edges and their representation. 4110d565efSmrg* Profile information:: Representation of frequencies and probabilities. 4210d565efSmrg* Maintaining the CFG:: Keeping the control flow graph and up to date. 4310d565efSmrg* Liveness information:: Using and maintaining liveness information. 4410d565efSmrg@end menu 4510d565efSmrg 4610d565efSmrg 4710d565efSmrg@node Basic Blocks 4810d565efSmrg@section Basic Blocks 4910d565efSmrg 5010d565efSmrg@cindex basic block 5110d565efSmrg@findex basic_block 5210d565efSmrgA basic block is a straight-line sequence of code with only one entry 5310d565efSmrgpoint and only one exit. In GCC, basic blocks are represented using 5410d565efSmrgthe @code{basic_block} data type. 5510d565efSmrg 5610d565efSmrg@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR 5710d565efSmrgSpecial basic blocks represent possible entry and exit points of a 5810d565efSmrgfunction. These blocks are called @code{ENTRY_BLOCK_PTR} and 5910d565efSmrg@code{EXIT_BLOCK_PTR}. These blocks do not contain any code. 6010d565efSmrg 6110d565efSmrg@findex BASIC_BLOCK 6210d565efSmrgThe @code{BASIC_BLOCK} array contains all basic blocks in an 6310d565efSmrgunspecified order. Each @code{basic_block} structure has a field 6410d565efSmrgthat holds a unique integer identifier @code{index} that is the 6510d565efSmrgindex of the block in the @code{BASIC_BLOCK} array. 6610d565efSmrgThe total number of basic blocks in the function is 6710d565efSmrg@code{n_basic_blocks}. Both the basic block indices and 6810d565efSmrgthe total number of basic blocks may vary during the compilation 6910d565efSmrgprocess, as passes reorder, create, duplicate, and destroy basic 7010d565efSmrgblocks. The index for any block should never be greater than 7110d565efSmrg@code{last_basic_block}. The indices 0 and 1 are special codes 7210d565efSmrgreserved for @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}, the 7310d565efSmrgindices of @code{ENTRY_BLOCK_PTR} and @code{EXIT_BLOCK_PTR}. 7410d565efSmrg 7510d565efSmrg@findex next_bb, prev_bb, FOR_EACH_BB, FOR_ALL_BB 7610d565efSmrgTwo pointer members of the @code{basic_block} structure are the 7710d565efSmrgpointers @code{next_bb} and @code{prev_bb}. These are used to keep 7810d565efSmrgdoubly linked chain of basic blocks in the same order as the 7910d565efSmrgunderlying instruction stream. The chain of basic blocks is updated 8010d565efSmrgtransparently by the provided API for manipulating the CFG@. The macro 8110d565efSmrg@code{FOR_EACH_BB} can be used to visit all the basic blocks in 8210d565efSmrglexicographical order, except @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. 8310d565efSmrgThe macro @code{FOR_ALL_BB} also visits all basic blocks in 8410d565efSmrglexicographical order, including @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}. 8510d565efSmrg 8610d565efSmrg@findex post_order_compute, inverted_post_order_compute, walk_dominator_tree 8710d565efSmrgThe functions @code{post_order_compute} and @code{inverted_post_order_compute} 8810d565efSmrgcan be used to compute topological orders of the CFG. The orders are 8910d565efSmrgstored as vectors of basic block indices. The @code{BASIC_BLOCK} array 9010d565efSmrgcan be used to iterate each basic block by index. 9110d565efSmrgDominator traversals are also possible using 9210d565efSmrg@code{walk_dominator_tree}. Given two basic blocks A and B, block A 9310d565efSmrgdominates block B if A is @emph{always} executed before B@. 9410d565efSmrg 9510d565efSmrgEach @code{basic_block} also contains pointers to the first 9610d565efSmrginstruction (the @dfn{head}) and the last instruction (the @dfn{tail}) 9710d565efSmrgor @dfn{end} of the instruction stream contained in a basic block. In 9810d565efSmrgfact, since the @code{basic_block} data type is used to represent 9910d565efSmrgblocks in both major intermediate representations of GCC (@code{GIMPLE} 10010d565efSmrgand RTL), there are pointers to the head and end of a basic block for 10110d565efSmrgboth representations, stored in intermediate representation specific 10210d565efSmrgdata in the @code{il} field of @code{struct basic_block_def}. 10310d565efSmrg 10410d565efSmrg@findex CODE_LABEL 10510d565efSmrg@findex NOTE_INSN_BASIC_BLOCK 10610d565efSmrgFor RTL, these pointers are @code{BB_HEAD} and @code{BB_END}. 10710d565efSmrg 10810d565efSmrg@cindex insn notes, notes 10910d565efSmrg@findex NOTE_INSN_BASIC_BLOCK 11010d565efSmrgIn the RTL representation of a function, the instruction stream 11110d565efSmrgcontains not only the ``real'' instructions, but also @dfn{notes} 11210d565efSmrgor @dfn{insn notes} (to distinguish them from @dfn{reg notes}). 11310d565efSmrgAny function that moves or duplicates the basic blocks needs 11410d565efSmrgto take care of updating of these notes. Many of these notes expect 11510d565efSmrgthat the instruction stream consists of linear regions, so updating 11610d565efSmrgcan sometimes be tedious. All types of insn notes are defined 11710d565efSmrgin @file{insn-notes.def}. 11810d565efSmrg 11910d565efSmrgIn the RTL function representation, the instructions contained in a 12010d565efSmrgbasic block always follow a @code{NOTE_INSN_BASIC_BLOCK}, but zero 12110d565efSmrgor more @code{CODE_LABEL} nodes can precede the block note. 12210d565efSmrgA basic block ends with a control flow instruction or with the last 12310d565efSmrginstruction before the next @code{CODE_LABEL} or 12410d565efSmrg@code{NOTE_INSN_BASIC_BLOCK}. 12510d565efSmrgBy definition, a @code{CODE_LABEL} cannot appear in the middle of 12610d565efSmrgthe instruction stream of a basic block. 12710d565efSmrg 12810d565efSmrg@findex can_fallthru 12910d565efSmrg@cindex table jump 13010d565efSmrgIn addition to notes, the jump table vectors are also represented as 13110d565efSmrg``pseudo-instructions'' inside the insn stream. These vectors never 13210d565efSmrgappear in the basic block and should always be placed just after the 13310d565efSmrgtable jump instructions referencing them. After removing the 13410d565efSmrgtable-jump it is often difficult to eliminate the code computing the 13510d565efSmrgaddress and referencing the vector, so cleaning up these vectors is 13610d565efSmrgpostponed until after liveness analysis. Thus the jump table vectors 13710d565efSmrgmay appear in the insn stream unreferenced and without any purpose. 13810d565efSmrgBefore any edge is made @dfn{fall-thru}, the existence of such 13910d565efSmrgconstruct in the way needs to be checked by calling 14010d565efSmrg@code{can_fallthru} function. 14110d565efSmrg 14210d565efSmrg@cindex GIMPLE statement iterators 14310d565efSmrgFor the @code{GIMPLE} representation, the PHI nodes and statements 14410d565efSmrgcontained in a basic block are in a @code{gimple_seq} pointed to by 14510d565efSmrgthe basic block intermediate language specific pointers. 14610d565efSmrgAbstract containers and iterators are used to access the PHI nodes 14710d565efSmrgand statements in a basic blocks. These iterators are called 14810d565efSmrg@dfn{GIMPLE statement iterators} (GSIs). Grep for @code{^gsi} 14910d565efSmrgin the various @file{gimple-*} and @file{tree-*} files. 15010d565efSmrgThere is a @code{gimple_stmt_iterator} type for iterating over 15110d565efSmrgall kinds of statement, and a @code{gphi_iterator} subclass for 15210d565efSmrgiterating over PHI nodes. 15310d565efSmrgThe following snippet will pretty-print all PHI nodes the statements 15410d565efSmrgof the current function in the GIMPLE representation. 15510d565efSmrg 15610d565efSmrg@smallexample 15710d565efSmrgbasic_block bb; 15810d565efSmrg 15910d565efSmrgFOR_EACH_BB (bb) 16010d565efSmrg @{ 16110d565efSmrg gphi_iterator pi; 16210d565efSmrg gimple_stmt_iterator si; 16310d565efSmrg 16410d565efSmrg for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi)) 16510d565efSmrg @{ 16610d565efSmrg gphi *phi = pi.phi (); 16710d565efSmrg print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); 16810d565efSmrg @} 16910d565efSmrg for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 17010d565efSmrg @{ 17110d565efSmrg gimple stmt = gsi_stmt (si); 17210d565efSmrg print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 17310d565efSmrg @} 17410d565efSmrg @} 17510d565efSmrg@end smallexample 17610d565efSmrg 17710d565efSmrg 17810d565efSmrg@node Edges 17910d565efSmrg@section Edges 18010d565efSmrg 18110d565efSmrg@cindex edge in the flow graph 18210d565efSmrg@findex edge 18310d565efSmrgEdges represent possible control flow transfers from the end of some 18410d565efSmrgbasic block A to the head of another basic block B@. We say that A is 18510d565efSmrga predecessor of B, and B is a successor of A@. Edges are represented 18610d565efSmrgin GCC with the @code{edge} data type. Each @code{edge} acts as a 18710d565efSmrglink between two basic blocks: The @code{src} member of an edge 18810d565efSmrgpoints to the predecessor basic block of the @code{dest} basic block. 18910d565efSmrgThe members @code{preds} and @code{succs} of the @code{basic_block} data 19010d565efSmrgtype point to type-safe vectors of edges to the predecessors and 19110d565efSmrgsuccessors of the block. 19210d565efSmrg 19310d565efSmrg@cindex edge iterators 19410d565efSmrgWhen walking the edges in an edge vector, @dfn{edge iterators} should 19510d565efSmrgbe used. Edge iterators are constructed using the 19610d565efSmrg@code{edge_iterator} data structure and several methods are available 19710d565efSmrgto operate on them: 19810d565efSmrg 19910d565efSmrg@ftable @code 20010d565efSmrg@item ei_start 20110d565efSmrgThis function initializes an @code{edge_iterator} that points to the 20210d565efSmrgfirst edge in a vector of edges. 20310d565efSmrg 20410d565efSmrg@item ei_last 20510d565efSmrgThis function initializes an @code{edge_iterator} that points to the 20610d565efSmrglast edge in a vector of edges. 20710d565efSmrg 20810d565efSmrg@item ei_end_p 20910d565efSmrgThis predicate is @code{true} if an @code{edge_iterator} represents 21010d565efSmrgthe last edge in an edge vector. 21110d565efSmrg 21210d565efSmrg@item ei_one_before_end_p 21310d565efSmrgThis predicate is @code{true} if an @code{edge_iterator} represents 21410d565efSmrgthe second last edge in an edge vector. 21510d565efSmrg 21610d565efSmrg@item ei_next 21710d565efSmrgThis function takes a pointer to an @code{edge_iterator} and makes it 21810d565efSmrgpoint to the next edge in the sequence. 21910d565efSmrg 22010d565efSmrg@item ei_prev 22110d565efSmrgThis function takes a pointer to an @code{edge_iterator} and makes it 22210d565efSmrgpoint to the previous edge in the sequence. 22310d565efSmrg 22410d565efSmrg@item ei_edge 22510d565efSmrgThis function returns the @code{edge} currently pointed to by an 22610d565efSmrg@code{edge_iterator}. 22710d565efSmrg 22810d565efSmrg@item ei_safe_safe 22910d565efSmrgThis function returns the @code{edge} currently pointed to by an 23010d565efSmrg@code{edge_iterator}, but returns @code{NULL} if the iterator is 23110d565efSmrgpointing at the end of the sequence. This function has been provided 23210d565efSmrgfor existing code makes the assumption that a @code{NULL} edge 23310d565efSmrgindicates the end of the sequence. 23410d565efSmrg 23510d565efSmrg@end ftable 23610d565efSmrg 23710d565efSmrgThe convenience macro @code{FOR_EACH_EDGE} can be used to visit all of 23810d565efSmrgthe edges in a sequence of predecessor or successor edges. It must 23910d565efSmrgnot be used when an element might be removed during the traversal, 24010d565efSmrgotherwise elements will be missed. Here is an example of how to use 24110d565efSmrgthe macro: 24210d565efSmrg 24310d565efSmrg@smallexample 24410d565efSmrgedge e; 24510d565efSmrgedge_iterator ei; 24610d565efSmrg 24710d565efSmrgFOR_EACH_EDGE (e, ei, bb->succs) 24810d565efSmrg @{ 24910d565efSmrg if (e->flags & EDGE_FALLTHRU) 25010d565efSmrg break; 25110d565efSmrg @} 25210d565efSmrg@end smallexample 25310d565efSmrg 25410d565efSmrg@findex fall-thru 25510d565efSmrgThere are various reasons why control flow may transfer from one block 25610d565efSmrgto another. One possibility is that some instruction, for example a 25710d565efSmrg@code{CODE_LABEL}, in a linearized instruction stream just always 25810d565efSmrgstarts a new basic block. In this case a @dfn{fall-thru} edge links 25910d565efSmrgthe basic block to the first following basic block. But there are 26010d565efSmrgseveral other reasons why edges may be created. The @code{flags} 26110d565efSmrgfield of the @code{edge} data type is used to store information 26210d565efSmrgabout the type of edge we are dealing with. Each edge is of one of 26310d565efSmrgthe following types: 26410d565efSmrg 26510d565efSmrg@table @emph 26610d565efSmrg@item jump 26710d565efSmrgNo type flags are set for edges corresponding to jump instructions. 26810d565efSmrgThese edges are used for unconditional or conditional jumps and in 26910d565efSmrgRTL also for table jumps. They are the easiest to manipulate as they 27010d565efSmrgmay be freely redirected when the flow graph is not in SSA form. 27110d565efSmrg 27210d565efSmrg@item fall-thru 27310d565efSmrg@findex EDGE_FALLTHRU, force_nonfallthru 27410d565efSmrgFall-thru edges are present in case where the basic block may continue 27510d565efSmrgexecution to the following one without branching. These edges have 27610d565efSmrgthe @code{EDGE_FALLTHRU} flag set. Unlike other types of edges, these 27710d565efSmrgedges must come into the basic block immediately following in the 27810d565efSmrginstruction stream. The function @code{force_nonfallthru} is 27910d565efSmrgavailable to insert an unconditional jump in the case that redirection 28010d565efSmrgis needed. Note that this may require creation of a new basic block. 28110d565efSmrg 28210d565efSmrg@item exception handling 28310d565efSmrg@cindex exception handling 28410d565efSmrg@findex EDGE_ABNORMAL, EDGE_EH 28510d565efSmrgException handling edges represent possible control transfers from a 28610d565efSmrgtrapping instruction to an exception handler. The definition of 28710d565efSmrg``trapping'' varies. In C++, only function calls can throw, but for 28810d565efSmrgAda exceptions like division by zero or segmentation fault are 28910d565efSmrgdefined and thus each instruction possibly throwing this kind of 29010d565efSmrgexception needs to be handled as control flow instruction. Exception 29110d565efSmrgedges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set. 29210d565efSmrg 29310d565efSmrg@findex purge_dead_edges 29410d565efSmrgWhen updating the instruction stream it is easy to change possibly 29510d565efSmrgtrapping instruction to non-trapping, by simply removing the exception 29610d565efSmrgedge. The opposite conversion is difficult, but should not happen 29710d565efSmrganyway. The edges can be eliminated via @code{purge_dead_edges} call. 29810d565efSmrg 29910d565efSmrg@findex REG_EH_REGION, EDGE_ABNORMAL_CALL 30010d565efSmrgIn the RTL representation, the destination of an exception edge is 30110d565efSmrgspecified by @code{REG_EH_REGION} note attached to the insn. 30210d565efSmrgIn case of a trapping call the @code{EDGE_ABNORMAL_CALL} flag is set 30310d565efSmrgtoo. In the @code{GIMPLE} representation, this extra flag is not set. 30410d565efSmrg 30510d565efSmrg@findex may_trap_p, tree_could_trap_p 30610d565efSmrgIn the RTL representation, the predicate @code{may_trap_p} may be used 30710d565efSmrgto check whether instruction still may trap or not. For the tree 30810d565efSmrgrepresentation, the @code{tree_could_trap_p} predicate is available, 30910d565efSmrgbut this predicate only checks for possible memory traps, as in 31010d565efSmrgdereferencing an invalid pointer location. 31110d565efSmrg 31210d565efSmrg 31310d565efSmrg@item sibling calls 31410d565efSmrg@cindex sibling call 31510d565efSmrg@findex EDGE_ABNORMAL, EDGE_SIBCALL 31610d565efSmrgSibling calls or tail calls terminate the function in a non-standard 31710d565efSmrgway and thus an edge to the exit must be present. 31810d565efSmrg@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case. 31910d565efSmrgThese edges only exist in the RTL representation. 32010d565efSmrg 32110d565efSmrg@item computed jumps 32210d565efSmrg@cindex computed jump 32310d565efSmrg@findex EDGE_ABNORMAL 32410d565efSmrgComputed jumps contain edges to all labels in the function referenced 32510d565efSmrgfrom the code. All those edges have @code{EDGE_ABNORMAL} flag set. 32610d565efSmrgThe edges used to represent computed jumps often cause compile time 32710d565efSmrgperformance problems, since functions consisting of many taken labels 32810d565efSmrgand many computed jumps may have @emph{very} dense flow graphs, so 32910d565efSmrgthese edges need to be handled with special care. During the earlier 33010d565efSmrgstages of the compilation process, GCC tries to avoid such dense flow 33110d565efSmrggraphs by factoring computed jumps. For example, given the following 33210d565efSmrgseries of jumps, 33310d565efSmrg 33410d565efSmrg@smallexample 33510d565efSmrg goto *x; 33610d565efSmrg [ @dots{} ] 33710d565efSmrg 33810d565efSmrg goto *x; 33910d565efSmrg [ @dots{} ] 34010d565efSmrg 34110d565efSmrg goto *x; 34210d565efSmrg [ @dots{} ] 34310d565efSmrg@end smallexample 34410d565efSmrg 34510d565efSmrg@noindent 34610d565efSmrgfactoring the computed jumps results in the following code sequence 34710d565efSmrgwhich has a much simpler flow graph: 34810d565efSmrg 34910d565efSmrg@smallexample 35010d565efSmrg goto y; 35110d565efSmrg [ @dots{} ] 35210d565efSmrg 35310d565efSmrg goto y; 35410d565efSmrg [ @dots{} ] 35510d565efSmrg 35610d565efSmrg goto y; 35710d565efSmrg [ @dots{} ] 35810d565efSmrg 35910d565efSmrgy: 36010d565efSmrg goto *x; 36110d565efSmrg@end smallexample 36210d565efSmrg 36310d565efSmrg@findex pass_duplicate_computed_gotos 36410d565efSmrgHowever, the classic problem with this transformation is that it has a 36510d565efSmrgruntime cost in there resulting code: An extra jump. Therefore, the 36610d565efSmrgcomputed jumps are un-factored in the later passes of the compiler 36710d565efSmrg(in the pass called @code{pass_duplicate_computed_gotos}). 36810d565efSmrgBe aware of that when you work on passes in that area. There have 36910d565efSmrgbeen numerous examples already where the compile time for code with 37010d565efSmrgunfactored computed jumps caused some serious headaches. 37110d565efSmrg 37210d565efSmrg@item nonlocal goto handlers 37310d565efSmrg@cindex nonlocal goto handler 37410d565efSmrg@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL 37510d565efSmrgGCC allows nested functions to return into caller using a @code{goto} 37610d565efSmrgto a label passed to as an argument to the callee. The labels passed 37710d565efSmrgto nested functions contain special code to cleanup after function 37810d565efSmrgcall. Such sections of code are referred to as ``nonlocal goto 37910d565efSmrgreceivers''. If a function contains such nonlocal goto receivers, an 38010d565efSmrgedge from the call to the label is created with the 38110d565efSmrg@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set. 38210d565efSmrg 38310d565efSmrg@item function entry points 38410d565efSmrg@cindex function entry point, alternate function entry point 38510d565efSmrg@findex LABEL_ALTERNATE_NAME 38610d565efSmrgBy definition, execution of function starts at basic block 0, so there 38710d565efSmrgis always an edge from the @code{ENTRY_BLOCK_PTR} to basic block 0. 38810d565efSmrgThere is no @code{GIMPLE} representation for alternate entry points at 38910d565efSmrgthis moment. In RTL, alternate entry points are specified by 39010d565efSmrg@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined. This 39110d565efSmrgfeature is currently used for multiple entry point prologues and is 39210d565efSmrglimited to post-reload passes only. This can be used by back-ends to 39310d565efSmrgemit alternate prologues for functions called from different contexts. 39410d565efSmrgIn future full support for multiple entry functions defined by Fortran 39510d565efSmrg90 needs to be implemented. 39610d565efSmrg 39710d565efSmrg@item function exits 39810d565efSmrgIn the pre-reload representation a function terminates after the last 39910d565efSmrginstruction in the insn chain and no explicit return instructions are 40010d565efSmrgused. This corresponds to the fall-thru edge into exit block. After 40110d565efSmrgreload, optimal RTL epilogues are used that use explicit (conditional) 40210d565efSmrgreturn instructions that are represented by edges with no flags set. 40310d565efSmrg 40410d565efSmrg@end table 40510d565efSmrg 40610d565efSmrg 40710d565efSmrg@node Profile information 40810d565efSmrg@section Profile information 40910d565efSmrg 41010d565efSmrg@cindex profile representation 41110d565efSmrgIn many cases a compiler must make a choice whether to trade speed in 41210d565efSmrgone part of code for speed in another, or to trade code size for code 41310d565efSmrgspeed. In such cases it is useful to know information about how often 41410d565efSmrgsome given block will be executed. That is the purpose for 41510d565efSmrgmaintaining profile within the flow graph. 41610d565efSmrgGCC can handle profile information obtained through @dfn{profile 41710d565efSmrgfeedback}, but it can also estimate branch probabilities based on 41810d565efSmrgstatics and heuristics. 41910d565efSmrg 42010d565efSmrg@cindex profile feedback 42110d565efSmrgThe feedback based profile is produced by compiling the program with 42210d565efSmrginstrumentation, executing it on a train run and reading the numbers 42310d565efSmrgof executions of basic blocks and edges back to the compiler while 42410d565efSmrgre-compiling the program to produce the final executable. This method 42510d565efSmrgprovides very accurate information about where a program spends most 42610d565efSmrgof its time on the train run. Whether it matches the average run of 42710d565efSmrgcourse depends on the choice of train data set, but several studies 42810d565efSmrghave shown that the behavior of a program usually changes just 42910d565efSmrgmarginally over different data sets. 43010d565efSmrg 43110d565efSmrg@cindex Static profile estimation 43210d565efSmrg@cindex branch prediction 43310d565efSmrg@findex predict.def 43410d565efSmrgWhen profile feedback is not available, the compiler may be asked to 43510d565efSmrgattempt to predict the behavior of each branch in the program using a 43610d565efSmrgset of heuristics (see @file{predict.def} for details) and compute 43710d565efSmrgestimated frequencies of each basic block by propagating the 43810d565efSmrgprobabilities over the graph. 43910d565efSmrg 44010d565efSmrg@findex frequency, count, BB_FREQ_BASE 44110d565efSmrgEach @code{basic_block} contains two integer fields to represent 44210d565efSmrgprofile information: @code{frequency} and @code{count}. The 44310d565efSmrg@code{frequency} is an estimation how often is basic block executed 44410d565efSmrgwithin a function. It is represented as an integer scaled in the 44510d565efSmrgrange from 0 to @code{BB_FREQ_BASE}. The most frequently executed 44610d565efSmrgbasic block in function is initially set to @code{BB_FREQ_BASE} and 44710d565efSmrgthe rest of frequencies are scaled accordingly. During optimization, 44810d565efSmrgthe frequency of the most frequent basic block can both decrease (for 44910d565efSmrginstance by loop unrolling) or grow (for instance by cross-jumping 45010d565efSmrgoptimization), so scaling sometimes has to be performed multiple 45110d565efSmrgtimes. 45210d565efSmrg 45310d565efSmrg@findex gcov_type 45410d565efSmrgThe @code{count} contains hard-counted numbers of execution measured 45510d565efSmrgduring training runs and is nonzero only when profile feedback is 45610d565efSmrgavailable. This value is represented as the host's widest integer 45710d565efSmrg(typically a 64 bit integer) of the special type @code{gcov_type}. 45810d565efSmrg 45910d565efSmrgMost optimization passes can use only the frequency information of a 46010d565efSmrgbasic block, but a few passes may want to know hard execution counts. 46110d565efSmrgThe frequencies should always match the counts after scaling, however 46210d565efSmrgduring updating of the profile information numerical error may 46310d565efSmrgaccumulate into quite large errors. 46410d565efSmrg 46510d565efSmrg@findex REG_BR_PROB_BASE, EDGE_FREQUENCY 46610d565efSmrgEach edge also contains a branch probability field: an integer in the 46710d565efSmrgrange from 0 to @code{REG_BR_PROB_BASE}. It represents probability of 46810d565efSmrgpassing control from the end of the @code{src} basic block to the 46910d565efSmrg@code{dest} basic block, i.e.@: the probability that control will flow 47010d565efSmrgalong this edge. The @code{EDGE_FREQUENCY} macro is available to 47110d565efSmrgcompute how frequently a given edge is taken. There is a @code{count} 47210d565efSmrgfield for each edge as well, representing same information as for a 47310d565efSmrgbasic block. 47410d565efSmrg 47510d565efSmrgThe basic block frequencies are not represented in the instruction 47610d565efSmrgstream, but in the RTL representation the edge frequencies are 47710d565efSmrgrepresented for conditional jumps (via the @code{REG_BR_PROB} 47810d565efSmrgmacro) since they are used when instructions are output to the 47910d565efSmrgassembly file and the flow graph is no longer maintained. 48010d565efSmrg 48110d565efSmrg@cindex reverse probability 48210d565efSmrgThe probability that control flow arrives via a given edge to its 48310d565efSmrgdestination basic block is called @dfn{reverse probability} and is not 48410d565efSmrgdirectly represented, but it may be easily computed from frequencies 48510d565efSmrgof basic blocks. 48610d565efSmrg 48710d565efSmrg@findex redirect_edge_and_branch 48810d565efSmrgUpdating profile information is a delicate task that can unfortunately 48910d565efSmrgnot be easily integrated with the CFG manipulation API@. Many of the 49010d565efSmrgfunctions and hooks to modify the CFG, such as 49110d565efSmrg@code{redirect_edge_and_branch}, do not have enough information to 49210d565efSmrgeasily update the profile, so updating it is in the majority of cases 49310d565efSmrgleft up to the caller. It is difficult to uncover bugs in the profile 49410d565efSmrgupdating code, because they manifest themselves only by producing 49510d565efSmrgworse code, and checking profile consistency is not possible because 49610d565efSmrgof numeric error accumulation. Hence special attention needs to be 49710d565efSmrggiven to this issue in each pass that modifies the CFG@. 49810d565efSmrg 49910d565efSmrg@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count 50010d565efSmrgIt is important to point out that @code{REG_BR_PROB_BASE} and 50110d565efSmrg@code{BB_FREQ_BASE} are both set low enough to be possible to compute 50210d565efSmrgsecond power of any frequency or probability in the flow graph, it is 50310d565efSmrgnot possible to even square the @code{count} field, as modern CPUs are 50410d565efSmrgfast enough to execute $2^32$ operations quickly. 50510d565efSmrg 50610d565efSmrg 50710d565efSmrg@node Maintaining the CFG 50810d565efSmrg@section Maintaining the CFG 50910d565efSmrg@findex cfghooks.h 51010d565efSmrg 51110d565efSmrgAn important task of each compiler pass is to keep both the control 51210d565efSmrgflow graph and all profile information up-to-date. Reconstruction of 51310d565efSmrgthe control flow graph after each pass is not an option, since it may be 51410d565efSmrgvery expensive and lost profile information cannot be reconstructed at 51510d565efSmrgall. 51610d565efSmrg 51710d565efSmrgGCC has two major intermediate representations, and both use the 51810d565efSmrg@code{basic_block} and @code{edge} data types to represent control 51910d565efSmrgflow. Both representations share as much of the CFG maintenance code 52010d565efSmrgas possible. For each representation, a set of @dfn{hooks} is defined 52110d565efSmrgso that each representation can provide its own implementation of CFG 52210d565efSmrgmanipulation routines when necessary. These hooks are defined in 52310d565efSmrg@file{cfghooks.h}. There are hooks for almost all common CFG 52410d565efSmrgmanipulations, including block splitting and merging, edge redirection 52510d565efSmrgand creating and deleting basic blocks. These hooks should provide 52610d565efSmrgeverything you need to maintain and manipulate the CFG in both the RTL 52710d565efSmrgand @code{GIMPLE} representation. 52810d565efSmrg 52910d565efSmrgAt the moment, the basic block boundaries are maintained transparently 53010d565efSmrgwhen modifying instructions, so there rarely is a need to move them 53110d565efSmrgmanually (such as in case someone wants to output instruction outside 53210d565efSmrgbasic block explicitly). 53310d565efSmrg 53410d565efSmrg@findex BLOCK_FOR_INSN, gimple_bb 53510d565efSmrgIn the RTL representation, each instruction has a 53610d565efSmrg@code{BLOCK_FOR_INSN} value that represents pointer to the basic block 53710d565efSmrgthat contains the instruction. In the @code{GIMPLE} representation, the 53810d565efSmrgfunction @code{gimple_bb} returns a pointer to the basic block 53910d565efSmrgcontaining the queried statement. 54010d565efSmrg 54110d565efSmrg@cindex GIMPLE statement iterators 54210d565efSmrgWhen changes need to be applied to a function in its @code{GIMPLE} 54310d565efSmrgrepresentation, @dfn{GIMPLE statement iterators} should be used. These 54410d565efSmrgiterators provide an integrated abstraction of the flow graph and the 54510d565efSmrginstruction stream. Block statement iterators are constructed using 54610d565efSmrgthe @code{gimple_stmt_iterator} data structure and several modifiers are 54710d565efSmrgavailable, including the following: 54810d565efSmrg 54910d565efSmrg@ftable @code 55010d565efSmrg@item gsi_start 55110d565efSmrgThis function initializes a @code{gimple_stmt_iterator} that points to 55210d565efSmrgthe first non-empty statement in a basic block. 55310d565efSmrg 55410d565efSmrg@item gsi_last 55510d565efSmrgThis function initializes a @code{gimple_stmt_iterator} that points to 55610d565efSmrgthe last statement in a basic block. 55710d565efSmrg 55810d565efSmrg@item gsi_end_p 55910d565efSmrgThis predicate is @code{true} if a @code{gimple_stmt_iterator} 56010d565efSmrgrepresents the end of a basic block. 56110d565efSmrg 56210d565efSmrg@item gsi_next 56310d565efSmrgThis function takes a @code{gimple_stmt_iterator} and makes it point to 56410d565efSmrgits successor. 56510d565efSmrg 56610d565efSmrg@item gsi_prev 56710d565efSmrgThis function takes a @code{gimple_stmt_iterator} and makes it point to 56810d565efSmrgits predecessor. 56910d565efSmrg 57010d565efSmrg@item gsi_insert_after 57110d565efSmrgThis function inserts a statement after the @code{gimple_stmt_iterator} 57210d565efSmrgpassed in. The final parameter determines whether the statement 57310d565efSmrgiterator is updated to point to the newly inserted statement, or left 57410d565efSmrgpointing to the original statement. 57510d565efSmrg 57610d565efSmrg@item gsi_insert_before 57710d565efSmrgThis function inserts a statement before the @code{gimple_stmt_iterator} 57810d565efSmrgpassed in. The final parameter determines whether the statement 57910d565efSmrgiterator is updated to point to the newly inserted statement, or left 58010d565efSmrgpointing to the original statement. 58110d565efSmrg 58210d565efSmrg@item gsi_remove 58310d565efSmrgThis function removes the @code{gimple_stmt_iterator} passed in and 58410d565efSmrgrechains the remaining statements in a basic block, if any. 58510d565efSmrg@end ftable 58610d565efSmrg 58710d565efSmrg@findex BB_HEAD, BB_END 58810d565efSmrgIn the RTL representation, the macros @code{BB_HEAD} and @code{BB_END} 58910d565efSmrgmay be used to get the head and end @code{rtx} of a basic block. No 59010d565efSmrgabstract iterators are defined for traversing the insn chain, but you 59110d565efSmrgcan just use @code{NEXT_INSN} and @code{PREV_INSN} instead. @xref{Insns}. 59210d565efSmrg 59310d565efSmrg@findex purge_dead_edges 59410d565efSmrgUsually a code manipulating pass simplifies the instruction stream and 59510d565efSmrgthe flow of control, possibly eliminating some edges. This may for 59610d565efSmrgexample happen when a conditional jump is replaced with an 59710d565efSmrgunconditional jump. Updating of edges 59810d565efSmrgis not transparent and each optimization pass is required to do so 59910d565efSmrgmanually. However only few cases occur in practice. The pass may 60010d565efSmrgcall @code{purge_dead_edges} on a given basic block to remove 60110d565efSmrgsuperfluous edges, if any. 60210d565efSmrg 60310d565efSmrg@findex redirect_edge_and_branch, redirect_jump 60410d565efSmrgAnother common scenario is redirection of branch instructions, but 60510d565efSmrgthis is best modeled as redirection of edges in the control flow graph 60610d565efSmrgand thus use of @code{redirect_edge_and_branch} is preferred over more 60710d565efSmrglow level functions, such as @code{redirect_jump} that operate on RTL 60810d565efSmrgchain only. The CFG hooks defined in @file{cfghooks.h} should provide 60910d565efSmrgthe complete API required for manipulating and maintaining the CFG@. 61010d565efSmrg 61110d565efSmrg@findex split_block 61210d565efSmrgIt is also possible that a pass has to insert control flow instruction 61310d565efSmrginto the middle of a basic block, thus creating an entry point in the 61410d565efSmrgmiddle of the basic block, which is impossible by definition: The 61510d565efSmrgblock must be split to make sure it only has one entry point, i.e.@: the 61610d565efSmrghead of the basic block. The CFG hook @code{split_block} may be used 61710d565efSmrgwhen an instruction in the middle of a basic block has to become the 61810d565efSmrgtarget of a jump or branch instruction. 61910d565efSmrg 62010d565efSmrg@findex insert_insn_on_edge 62110d565efSmrg@findex commit_edge_insertions 62210d565efSmrg@findex gsi_insert_on_edge 62310d565efSmrg@findex gsi_commit_edge_inserts 62410d565efSmrg@cindex edge splitting 62510d565efSmrgFor a global optimizer, a common operation is to split edges in the 62610d565efSmrgflow graph and insert instructions on them. In the RTL 62710d565efSmrgrepresentation, this can be easily done using the 62810d565efSmrg@code{insert_insn_on_edge} function that emits an instruction 62910d565efSmrg``on the edge'', caching it for a later @code{commit_edge_insertions} 63010d565efSmrgcall that will take care of moving the inserted instructions off the 63110d565efSmrgedge into the instruction stream contained in a basic block. This 63210d565efSmrgincludes the creation of new basic blocks where needed. In the 63310d565efSmrg@code{GIMPLE} representation, the equivalent functions are 63410d565efSmrg@code{gsi_insert_on_edge} which inserts a block statement 63510d565efSmrgiterator on an edge, and @code{gsi_commit_edge_inserts} which flushes 63610d565efSmrgthe instruction to actual instruction stream. 63710d565efSmrg 63810d565efSmrg@findex verify_flow_info 63910d565efSmrg@cindex CFG verification 64010d565efSmrgWhile debugging the optimization pass, the @code{verify_flow_info} 64110d565efSmrgfunction may be useful to find bugs in the control flow graph updating 64210d565efSmrgcode. 64310d565efSmrg 64410d565efSmrg 64510d565efSmrg@node Liveness information 64610d565efSmrg@section Liveness information 64710d565efSmrg@cindex Liveness representation 64810d565efSmrgLiveness information is useful to determine whether some register is 64910d565efSmrg``live'' at given point of program, i.e.@: that it contains a value that 65010d565efSmrgmay be used at a later point in the program. This information is 65110d565efSmrgused, for instance, during register allocation, as the pseudo 65210d565efSmrgregisters only need to be assigned to a unique hard register or to a 65310d565efSmrgstack slot if they are live. The hard registers and stack slots may 65410d565efSmrgbe freely reused for other values when a register is dead. 65510d565efSmrg 65610d565efSmrgLiveness information is available in the back end starting with 65710d565efSmrg@code{pass_df_initialize} and ending with @code{pass_df_finish}. Three 65810d565efSmrgflavors of live analysis are available: With @code{LR}, it is possible 65910d565efSmrgto determine at any point @code{P} in the function if the register may be 66010d565efSmrgused on some path from @code{P} to the end of the function. With 66110d565efSmrg@code{UR}, it is possible to determine if there is a path from the 66210d565efSmrgbeginning of the function to @code{P} that defines the variable. 66310d565efSmrg@code{LIVE} is the intersection of the @code{LR} and @code{UR} and a 66410d565efSmrgvariable is live at @code{P} if there is both an assignment that reaches 66510d565efSmrgit from the beginning of the function and a use that can be reached on 66610d565efSmrgsome path from @code{P} to the end of the function. 66710d565efSmrg 66810d565efSmrgIn general @code{LIVE} is the most useful of the three. The macros 66910d565efSmrg@code{DF_[LR,UR,LIVE]_[IN,OUT]} can be used to access this information. 67010d565efSmrgThe macros take a basic block number and return a bitmap that is indexed 67110d565efSmrgby the register number. This information is only guaranteed to be up to 67210d565efSmrgdate after calls are made to @code{df_analyze}. See the file 67310d565efSmrg@code{df-core.c} for details on using the dataflow. 67410d565efSmrg 67510d565efSmrg 67610d565efSmrg@findex REG_DEAD, REG_UNUSED 67710d565efSmrgThe liveness information is stored partly in the RTL instruction stream 67810d565efSmrgand partly in the flow graph. Local information is stored in the 67910d565efSmrginstruction stream: Each instruction may contain @code{REG_DEAD} notes 68010d565efSmrgrepresenting that the value of a given register is no longer needed, or 68110d565efSmrg@code{REG_UNUSED} notes representing that the value computed by the 68210d565efSmrginstruction is never used. The second is useful for instructions 68310d565efSmrgcomputing multiple values at once. 68410d565efSmrg 685