passes.texi revision 132718
1132718Skan@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2132718Skan@c 2000, 2001, 2002, 2003 Free Software Foundation, Inc. 390075Sobrien@c This is part of the GCC manual. 490075Sobrien@c For copying conditions, see the file gcc.texi. 590075Sobrien 690075Sobrien@node Passes 790075Sobrien@chapter Passes and Files of the Compiler 890075Sobrien@cindex passes and files of the compiler 990075Sobrien@cindex files and passes of the compiler 1090075Sobrien@cindex compiler passes and files 1190075Sobrien 1290075Sobrien@cindex top level of compiler 1390075SobrienThe overall control structure of the compiler is in @file{toplev.c}. This 1490075Sobrienfile is responsible for initialization, decoding arguments, opening and 15132718Skanclosing files, and sequencing the passes. Routines for emitting 16132718Skandiagnostic messages are defined in @file{diagnostic.c}. The files 17132718Skan@file{pretty-print.h} and @file{pretty-print.c} provide basic support 18132718Skanfor language-independent pretty-printing. 1990075Sobrien 2090075Sobrien@cindex parsing pass 2190075SobrienThe parsing pass is invoked only once, to parse the entire input. A 2290075Sobrienhigh level tree representation is then generated from the input, 2390075Sobrienone function at a time. This tree code is then transformed into RTL 2490075Sobrienintermediate code, and processed. The files involved in transforming 2590075Sobrienthe trees into RTL are @file{expr.c}, @file{expmed.c}, and 2690075Sobrien@file{stmt.c}. 2790075Sobrien@c Note, the above files aren't strictly the only files involved. It's 2890075Sobrien@c all over the place (function.c, final.c,etc). However, those are 2990075Sobrien@c the files that are supposed to be directly involved, and have 3090075Sobrien@c their purpose listed as such, so i've only listed them. 3190075SobrienThe order of trees that are processed, is not 3290075Sobriennecessarily the same order they are generated from 3390075Sobrienthe input, due to deferred inlining, and other considerations. 3490075Sobrien 3590075Sobrien@findex rest_of_compilation 3690075Sobrien@findex rest_of_decl_compilation 3790075SobrienEach time the parsing pass reads a complete function definition or 3890075Sobrientop-level declaration, it calls either the function 3990075Sobrien@code{rest_of_compilation}, or the function 4090075Sobrien@code{rest_of_decl_compilation} in @file{toplev.c}, which are 4190075Sobrienresponsible for all further processing necessary, ending with output of 4290075Sobrienthe assembler language. All other compiler passes run, in sequence, 4390075Sobrienwithin @code{rest_of_compilation}. When that function returns from 4490075Sobriencompiling a function definition, the storage used for that function 4590075Sobriendefinition's compilation is entirely freed, unless it is an inline 4690075Sobrienfunction, or was deferred for some reason (this can occur in 4790075Sobrientemplates, for example). 4890075Sobrien(@pxref{Inline,,An Inline Function is As Fast As a Macro,gcc,Using the 4990075SobrienGNU Compiler Collection (GCC)}). 5090075Sobrien 5190075SobrienHere is a list of all the passes of the compiler and their source files. 5290075SobrienAlso included is a description of where debugging dumps can be requested 5390075Sobrienwith @option{-d} options. 5490075Sobrien 5590075Sobrien@itemize @bullet 5690075Sobrien@item 5790075SobrienParsing. This pass reads the entire text of a function definition, 5890075Sobrienconstructing a high level tree representation. (Because of the semantic 5990075Sobrienanalysis that takes place during this pass, it does more than is 6090075Sobrienformally considered to be parsing.) 6190075Sobrien 6290075SobrienThe tree representation does not entirely follow C syntax, because it is 6390075Sobrienintended to support other languages as well. 6490075Sobrien 6590075SobrienLanguage-specific data type analysis is also done in this pass, and every 6690075Sobrientree node that represents an expression has a data type attached. 6790075SobrienVariables are represented as declaration nodes. 6890075Sobrien 6990075SobrienThe language-independent source files for parsing are 7090075Sobrien@file{tree.c}, @file{fold-const.c}, and @file{stor-layout.c}. 7190075SobrienThere are also header files @file{tree.h} and @file{tree.def} 7290075Sobrienwhich define the format of the tree representation. 7390075Sobrien 7490075SobrienC preprocessing, for language front ends, that want or require it, is 7590075Sobrienperformed by cpplib, which is covered in separate documentation. In 7690075Sobrienparticular, the internals are covered in @xref{Top, ,Cpplib internals, 7790075Sobriencppinternals, Cpplib Internals}. 7890075Sobrien 79132718SkanThe source files to parse C are found in the toplevel directory, and 80132718Skanby convention are named @file{c-*}. Some of these are also used by 81132718Skanthe other C-like languages: @file{c-common.c}, 8290075Sobrien@file{c-common.def}, 8390075Sobrien@file{c-format.c}, 84117395Skan@file{c-opts.c}, 8590075Sobrien@file{c-pragma.c}, 8690075Sobrien@file{c-semantics.c}, 8790075Sobrien@file{c-lex.c}, 88132718Skan@file{c-incpath.c}, 89132718Skan@file{c-ppoutput.c}, 90132718Skan@file{c-cppbuiltin.c}, 9190075Sobrien@file{c-common.h}, 9290075Sobrien@file{c-dump.h}, 93132718Skan@file{c.opt}, 94132718Skan@file{c-incpath.h} 9590075Sobrienand 9690075Sobrien@file{c-pragma.h}, 9790075Sobrien 98132718SkanFiles specific to each language are in subdirectories named after the 99132718Skanlanguage in question, like @file{ada}, @file{objc}, @file{cp} (for C++). 10090075Sobrien 10190075Sobrien@cindex Tree optimization 10290075Sobrien@item 10390075SobrienTree optimization. This is the optimization of the tree 10490075Sobrienrepresentation, before converting into RTL code. 10590075Sobrien 10690075Sobrien@cindex inline on trees, automatic 10790075SobrienCurrently, the main optimization performed here is tree-based 10890075Sobrieninlining. 10996263SobrienThis is implemented in @file{tree-inline.c} and used by both C and C++. 11090075SobrienNote that tree based inlining turns off rtx based inlining (since it's more 11190075Sobrienpowerful, it would be a waste of time to do rtx based inlining in 11290075Sobrienaddition). 11390075Sobrien 11490075Sobrien@cindex constant folding 11590075Sobrien@cindex arithmetic simplifications 11690075Sobrien@cindex simplifications, arithmetic 11790075SobrienConstant folding and some arithmetic simplifications are also done 11890075Sobrienduring this pass, on the tree representation. 11990075SobrienThe routines that perform these tasks are located in @file{fold-const.c}. 12090075Sobrien 12190075Sobrien@cindex RTL generation 12290075Sobrien@item 12390075SobrienRTL generation. This is the conversion of syntax tree into RTL code. 12490075Sobrien 12590075Sobrien@cindex target-parameter-dependent code 12690075SobrienThis is where the bulk of target-parameter-dependent code is found, 12790075Sobriensince often it is necessary for strategies to apply only when certain 12890075Sobrienstandard kinds of instructions are available. The purpose of named 12990075Sobrieninstruction patterns is to provide this information to the RTL 13090075Sobriengeneration pass. 13190075Sobrien 13290075Sobrien@cindex tail recursion optimization 13390075SobrienOptimization is done in this pass for @code{if}-conditions that are 13490075Sobriencomparisons, boolean operations or conditional expressions. Tail 13590075Sobrienrecursion is detected at this time also. Decisions are made about how 13690075Sobrienbest to arrange loops and how to output @code{switch} statements. 13790075Sobrien 13890075Sobrien@c Avoiding overfull is tricky here. 13990075SobrienThe source files for RTL generation include 14090075Sobrien@file{stmt.c}, 14190075Sobrien@file{calls.c}, 14290075Sobrien@file{expr.c}, 14390075Sobrien@file{explow.c}, 14490075Sobrien@file{expmed.c}, 14590075Sobrien@file{function.c}, 14690075Sobrien@file{optabs.c} 14790075Sobrienand @file{emit-rtl.c}. 14890075SobrienAlso, the file 14990075Sobrien@file{insn-emit.c}, generated from the machine description by the 15090075Sobrienprogram @code{genemit}, is used in this pass. The header file 15190075Sobrien@file{expr.h} is used for communication within this pass. 15290075Sobrien 15390075Sobrien@findex genflags 15490075Sobrien@findex gencodes 15590075SobrienThe header files @file{insn-flags.h} and @file{insn-codes.h}, 15690075Sobriengenerated from the machine description by the programs @code{genflags} 15790075Sobrienand @code{gencodes}, tell this pass which standard names are available 15890075Sobrienfor use and which patterns correspond to them. 15990075Sobrien 16090075SobrienAside from debugging information output, none of the following passes 16190075Sobrienrefers to the tree structure representation of the function (only 16290075Sobrienpart of which is saved). 16390075Sobrien 16490075Sobrien@cindex inline on rtx, automatic 16590075SobrienThe decision of whether the function can and should be expanded inline 16690075Sobrienin its subsequent callers is made at the end of rtl generation. The 16790075Sobrienfunction must meet certain criteria, currently related to the size of 16890075Sobrienthe function and the types and number of parameters it has. Note that 16990075Sobrienthis function may contain loops, recursive calls to itself 17090075Sobrien(tail-recursive functions can be inlined!), gotos, in short, all 17190075Sobrienconstructs supported by GCC@. The file @file{integrate.c} contains 17290075Sobrienthe code to save a function's rtl for later inlining and to inline that 17390075Sobrienrtl when the function is called. The header file @file{integrate.h} 17490075Sobrienis also used for this purpose. 17590075Sobrien 17690075Sobrien@opindex dr 17790075SobrienThe option @option{-dr} causes a debugging dump of the RTL code after 17890075Sobrienthis pass. This dump file's name is made by appending @samp{.rtl} to 17990075Sobrienthe input file name. 18090075Sobrien 18190075Sobrien@c Should the exception handling pass be talked about here? 18290075Sobrien 18390075Sobrien@cindex sibling call optimization 18490075Sobrien@item 185117395SkanSibling call optimization. This pass performs tail recursion 18690075Sobrienelimination, and tail and sibling call optimizations. The purpose of 18790075Sobrienthese optimizations is to reduce the overhead of function calls, 18890075Sobrienwhenever possible. 18990075Sobrien 19090075SobrienThe source file of this pass is @file{sibcall.c} 19190075Sobrien 19290075Sobrien@opindex di 19390075SobrienThe option @option{-di} causes a debugging dump of the RTL code after 19490075Sobrienthis pass is run. This dump file's name is made by appending 19590075Sobrien@samp{.sibling} to the input file name. 19690075Sobrien 19790075Sobrien@cindex jump optimization 19890075Sobrien@cindex unreachable code 19990075Sobrien@cindex dead code 20090075Sobrien@item 20190075SobrienJump optimization. This pass simplifies jumps to the following 20290075Sobrieninstruction, jumps across jumps, and jumps to jumps. It deletes 20390075Sobrienunreferenced labels and unreachable code, except that unreachable code 20490075Sobrienthat contains a loop is not recognized as unreachable in this pass. 20590075Sobrien(Such loops are deleted later in the basic block analysis.) It also 20690075Sobrienconverts some code originally written with jumps into sequences of 20790075Sobrieninstructions that directly set values from the results of comparisons, 20890075Sobrienif the machine has such instructions. 20990075Sobrien 21090075SobrienJump optimization is performed two or three times. The first time is 21190075Sobrienimmediately following RTL generation. The second time is after CSE, 21290075Sobrienbut only if CSE says repeated jump optimization is needed. The 21390075Sobrienlast time is right before the final pass. That time, cross-jumping 21490075Sobrienand deletion of no-op move instructions are done together with the 21590075Sobrienoptimizations described above. 21690075Sobrien 21790075SobrienThe source file of this pass is @file{jump.c}. 21890075Sobrien 21990075Sobrien@opindex dj 22090075SobrienThe option @option{-dj} causes a debugging dump of the RTL code after 22190075Sobrienthis pass is run for the first time. This dump file's name is made by 22290075Sobrienappending @samp{.jump} to the input file name. 22390075Sobrien 22490075Sobrien 22590075Sobrien@cindex register use analysis 22690075Sobrien@item 22790075SobrienRegister scan. This pass finds the first and last use of each 22890075Sobrienregister, as a guide for common subexpression elimination. Its source 22990075Sobrienis in @file{regclass.c}. 23090075Sobrien 23190075Sobrien@cindex jump threading 23290075Sobrien@item 23390075Sobrien@opindex fthread-jumps 23490075SobrienJump threading. This pass detects a condition jump that branches to an 23590075Sobrienidentical or inverse test. Such jumps can be @samp{threaded} through 23690075Sobrienthe second conditional test. The source code for this pass is in 23790075Sobrien@file{jump.c}. This optimization is only performed if 23890075Sobrien@option{-fthread-jumps} is enabled. 23990075Sobrien 24090075Sobrien@cindex common subexpression elimination 24190075Sobrien@cindex constant propagation 24290075Sobrien@item 24390075SobrienCommon subexpression elimination. This pass also does constant 24490075Sobrienpropagation. Its source files are @file{cse.c}, and @file{cselib.c}. 24590075SobrienIf constant propagation causes conditional jumps to become 24690075Sobrienunconditional or to become no-ops, jump optimization is run again when 24790075SobrienCSE is finished. 24890075Sobrien 24990075Sobrien@opindex ds 25090075SobrienThe option @option{-ds} causes a debugging dump of the RTL code after 25190075Sobrienthis pass. This dump file's name is made by appending @samp{.cse} to 25290075Sobrienthe input file name. 25390075Sobrien 25490075Sobrien@cindex global common subexpression elimination 25590075Sobrien@cindex constant propagation 25690075Sobrien@cindex copy propagation 25790075Sobrien@item 25890075SobrienGlobal common subexpression elimination. This pass performs two 25990075Sobriendifferent types of GCSE depending on whether you are optimizing for 26090075Sobriensize or not (LCM based GCSE tends to increase code size for a gain in 26190075Sobrienspeed, while Morel-Renvoise based GCSE does not). 26290075SobrienWhen optimizing for size, GCSE is done using Morel-Renvoise Partial 26390075SobrienRedundancy Elimination, with the exception that it does not try to move 26490075Sobrieninvariants out of loops---that is left to the loop optimization pass. 26590075SobrienIf MR PRE GCSE is done, code hoisting (aka unification) is also done, as 26690075Sobrienwell as load motion. 26790075SobrienIf you are optimizing for speed, LCM (lazy code motion) based GCSE is 26890075Sobriendone. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM 26990075Sobrienbased GCSE also does loop invariant code motion. We also perform load 27090075Sobrienand store motion when optimizing for speed. 27190075SobrienRegardless of which type of GCSE is used, the GCSE pass also performs 27290075Sobrienglobal constant and copy propagation. 27390075Sobrien 27490075SobrienThe source file for this pass is @file{gcse.c}, and the LCM routines 27590075Sobrienare in @file{lcm.c}. 27690075Sobrien 27790075Sobrien@opindex dG 27890075SobrienThe option @option{-dG} causes a debugging dump of the RTL code after 27990075Sobrienthis pass. This dump file's name is made by appending @samp{.gcse} to 28090075Sobrienthe input file name. 28190075Sobrien 28290075Sobrien@cindex loop optimization 28390075Sobrien@cindex code motion 28490075Sobrien@cindex strength-reduction 28590075Sobrien@item 28690075SobrienLoop optimization. This pass moves constant expressions out of loops, 28790075Sobrienand optionally does strength-reduction and loop unrolling as well. 28890075SobrienIts source files are @file{loop.c} and @file{unroll.c}, plus the header 28990075Sobrien@file{loop.h} used for communication between them. Loop unrolling uses 29090075Sobriensome functions in @file{integrate.c} and the header @file{integrate.h}. 29190075SobrienLoop dependency analysis routines are contained in @file{dependence.c}. 29290075Sobrien 293132718SkanSecond loop optimization pass takes care of basic block level optimizations -- 294132718Skanunrolling, peeling and unswitching loops. The source files are 295132718Skan@file{cfgloopanal.c} and @file{cfgloopmanip.c} containing generic loop 296132718Skananalysis and manipulation code, @file{loop-init.c} with initialization and 297132718Skanfinalization code, @file{loop-unswitch.c} for loop unswitching and 298132718Skan@file{loop-unroll.c} for loop unrolling and peeling. 299132718Skan 30090075Sobrien@opindex dL 30190075SobrienThe option @option{-dL} causes a debugging dump of the RTL code after 302132718Skanthese passes. The dump file names are made by appending @samp{.loop} and 303132718Skan@samp{.loop2} to the input file name. 304132718Skan 305132718Skan@cindex jump bypassing 306132718Skan@item 307132718SkanJump bypassing. This pass is an aggressive form of GCSE that transforms 308132718Skanthe control flow graph of a function by propagating constants into 309132718Skanconditional branch instructions. 310132718Skan 311132718SkanThe source file for this pass is @file{gcse.c}. 312132718Skan 313132718Skan@opindex dG 314132718SkanThe option @option{-dG} causes a debugging dump of the RTL code after 315132718Skanthis pass. This dump file's name is made by appending @samp{.bypass} 316132718Skanto the input file name. 317132718Skan 318132718Skan@cindex web construction 319132718Skan@item 320132718SkanSimple optimization pass that splits independent uses of each pseudo 321132718Skanincreasing effect of other optimizations. This can improve effect of the 322132718Skanother transformation, such as CSE or register allocation. 323132718SkanIts source files are @file{web.c}. 324132718Skan 325132718Skan@opindex dZ 326132718SkanThe option @option{-dZ} causes a debugging dump of the RTL code after 327132718Skanthis pass. This dump file's name is made by appending @samp{.web} to 32890075Sobrienthe input file name. 32990075Sobrien 33090075Sobrien@item 33190075Sobrien@opindex frerun-cse-after-loop 33290075SobrienIf @option{-frerun-cse-after-loop} was enabled, a second common 33390075Sobriensubexpression elimination pass is performed after the loop optimization 33490075Sobrienpass. Jump threading is also done again at this time if it was specified. 33590075Sobrien 33690075Sobrien@opindex dt 33790075SobrienThe option @option{-dt} causes a debugging dump of the RTL code after 33890075Sobrienthis pass. This dump file's name is made by appending @samp{.cse2} to 33990075Sobrienthe input file name. 34090075Sobrien 34190075Sobrien@cindex data flow analysis 34290075Sobrien@cindex analysis, data flow 34390075Sobrien@cindex basic blocks 34490075Sobrien@item 34590075SobrienData flow analysis (@file{flow.c}). This pass divides the program 34690075Sobrieninto basic blocks (and in the process deletes unreachable loops); then 34790075Sobrienit computes which pseudo-registers are live at each point in the 34890075Sobrienprogram, and makes the first instruction that uses a value point at 34990075Sobrienthe instruction that computed the value. 35090075Sobrien 35190075Sobrien@cindex autoincrement/decrement analysis 35290075SobrienThis pass also deletes computations whose results are never used, and 35390075Sobriencombines memory references with add or subtract instructions to make 35490075Sobrienautoincrement or autodecrement addressing. 35590075Sobrien 35690075Sobrien@opindex df 35790075SobrienThe option @option{-df} causes a debugging dump of the RTL code after 35890075Sobrienthis pass. This dump file's name is made by appending @samp{.flow} to 35990075Sobrienthe input file name. If stupid register allocation is in use, this 36090075Sobriendump file reflects the full results of such allocation. 36190075Sobrien 36290075Sobrien@cindex instruction combination 36390075Sobrien@item 36490075SobrienInstruction combination (@file{combine.c}). This pass attempts to 36590075Sobriencombine groups of two or three instructions that are related by data 36690075Sobrienflow into single instructions. It combines the RTL expressions for 36790075Sobrienthe instructions by substitution, simplifies the result using algebra, 36890075Sobrienand then attempts to match the result against the machine description. 36990075Sobrien 37090075Sobrien@opindex dc 37190075SobrienThe option @option{-dc} causes a debugging dump of the RTL code after 37290075Sobrienthis pass. This dump file's name is made by appending @samp{.combine} 37390075Sobriento the input file name. 37490075Sobrien 37590075Sobrien@cindex if conversion 37690075Sobrien@item 37790075SobrienIf-conversion is a transformation that transforms control dependencies 37890075Sobrieninto data dependencies (IE it transforms conditional code into a 37990075Sobriensingle control stream). 38090075SobrienIt is implemented in the file @file{ifcvt.c}. 38190075Sobrien 38290075Sobrien@opindex dE 38390075SobrienThe option @option{-dE} causes a debugging dump of the RTL code after 38490075Sobrienthis pass. This dump file's name is made by appending @samp{.ce} to 38590075Sobrienthe input file name. 38690075Sobrien 38790075Sobrien@cindex register movement 38890075Sobrien@item 38990075SobrienRegister movement (@file{regmove.c}). This pass looks for cases where 39090075Sobrienmatching constraints would force an instruction to need a reload, and 39190075Sobrienthis reload would be a register-to-register move. It then attempts 39290075Sobriento change the registers used by the instruction to avoid the move 39390075Sobrieninstruction. 39490075Sobrien 39590075Sobrien@opindex dN 39690075SobrienThe option @option{-dN} causes a debugging dump of the RTL code after 39790075Sobrienthis pass. This dump file's name is made by appending @samp{.regmove} 39890075Sobriento the input file name. 39990075Sobrien 40090075Sobrien@cindex instruction scheduling 40190075Sobrien@cindex scheduling, instruction 40290075Sobrien@item 40390075SobrienInstruction scheduling (@file{sched.c}). This pass looks for 40490075Sobrieninstructions whose output will not be available by the time that it is 40590075Sobrienused in subsequent instructions. (Memory loads and floating point 40690075Sobrieninstructions often have this behavior on RISC machines). It re-orders 40790075Sobrieninstructions within a basic block to try to separate the definition and 40890075Sobrienuse of items that otherwise would cause pipeline stalls. 40990075Sobrien 41090075SobrienInstruction scheduling is performed twice. The first time is immediately 41190075Sobrienafter instruction combination and the second is immediately after reload. 41290075Sobrien 41390075Sobrien@opindex dS 41490075SobrienThe option @option{-dS} causes a debugging dump of the RTL code after this 41590075Sobrienpass is run for the first time. The dump file's name is made by 41690075Sobrienappending @samp{.sched} to the input file name. 41790075Sobrien 418117395Skan@cindex register allocation 419117395Skan@item 420117395SkanRegister allocation. These passes make sure that all occurrences of pseudo 421117395Skanregisters are eliminated, either by allocating them to a hard register, 422117395Skanreplacing them by an equivalent expression (e.g.@: a constant) or by placing 423117395Skanthem on the stack. This is done in several subpasses: 424117395Skan 425117395Skan@itemize @bullet 42690075Sobrien@cindex register class preference pass 42790075Sobrien@item 42890075SobrienRegister class preferencing. The RTL code is scanned to find out 42990075Sobrienwhich register class is best for each pseudo register. The source 43090075Sobrienfile is @file{regclass.c}. 43190075Sobrien 43290075Sobrien@cindex local register allocation 43390075Sobrien@item 43490075SobrienLocal register allocation (@file{local-alloc.c}). This pass allocates 43590075Sobrienhard registers to pseudo registers that are used only within one basic 43690075Sobrienblock. Because the basic block is linear, it can use fast and 43790075Sobrienpowerful techniques to do a very good job. 43890075Sobrien 43990075Sobrien@opindex dl 44090075SobrienThe option @option{-dl} causes a debugging dump of the RTL code after 44190075Sobrienthis pass. This dump file's name is made by appending @samp{.lreg} to 44290075Sobrienthe input file name. 44390075Sobrien 44490075Sobrien@cindex global register allocation 44590075Sobrien@item 44690075SobrienGlobal register allocation (@file{global.c}). This pass 44790075Sobrienallocates hard registers for the remaining pseudo registers (those 44890075Sobrienwhose life spans are not contained in one basic block). 44990075Sobrien 450117395Skan@cindex graph coloring register allocation 451117395Skan@opindex fnew-ra 452117395Skan@opindex dl 453117395Skan@item 454117395SkanGraph coloring register allocator. The files @file{ra.c}, @file{ra-build.c}, 455117395Skan@file{ra-colorize.c}, @file{ra-debug.c}, @file{ra-rewrite.c} together with 456117395Skanthe header @file{ra.h} contain another register allocator, which is used 457117395Skanwhen the option @option{-fnew-ra} is given. In that case it is run instead 458117395Skanof the above mentioned local and global register allocation passes, and the 459117395Skanoption @option{-dl} causes a debugging dump of its work. 460117395Skan 46190075Sobrien@cindex reloading 46290075Sobrien@item 46390075SobrienReloading. This pass renumbers pseudo registers with the hardware 46490075Sobrienregisters numbers they were allocated. Pseudo registers that did not 46590075Sobrienget hard registers are replaced with stack slots. Then it finds 46690075Sobrieninstructions that are invalid because a value has failed to end up in 46790075Sobriena register, or has ended up in a register of the wrong kind. It fixes 46890075Sobrienup these instructions by reloading the problematical values 46990075Sobrientemporarily into registers. Additional instructions are generated to 47090075Sobriendo the copying. 47190075Sobrien 47290075SobrienThe reload pass also optionally eliminates the frame pointer and inserts 47390075Sobrieninstructions to save and restore call-clobbered registers around calls. 47490075Sobrien 47590075SobrienSource files are @file{reload.c} and @file{reload1.c}, plus the header 47690075Sobrien@file{reload.h} used for communication between them. 47790075Sobrien 47890075Sobrien@opindex dg 47990075SobrienThe option @option{-dg} causes a debugging dump of the RTL code after 48090075Sobrienthis pass. This dump file's name is made by appending @samp{.greg} to 48190075Sobrienthe input file name. 482117395Skan@end itemize 48390075Sobrien 48490075Sobrien@cindex instruction scheduling 48590075Sobrien@cindex scheduling, instruction 48690075Sobrien@item 48790075SobrienInstruction scheduling is repeated here to try to avoid pipeline stalls 48890075Sobriendue to memory loads generated for spilled pseudo registers. 48990075Sobrien 49090075Sobrien@opindex dR 49190075SobrienThe option @option{-dR} causes a debugging dump of the RTL code after 49290075Sobrienthis pass. This dump file's name is made by appending @samp{.sched2} 49390075Sobriento the input file name. 49490075Sobrien 49590075Sobrien@cindex basic block reordering 49690075Sobrien@cindex reordering, block 49790075Sobrien@item 49890075SobrienBasic block reordering. This pass implements profile guided code 49990075Sobrienpositioning. If profile information is not available, various types of 50090075Sobrienstatic analysis are performed to make the predictions normally coming 50190075Sobrienfrom the profile feedback (IE execution frequency, branch probability, 50290075Sobrienetc). It is implemented in the file @file{bb-reorder.c}, and the 50390075Sobrienvarious prediction routines are in @file{predict.c}. 50490075Sobrien 50590075Sobrien@opindex dB 50690075SobrienThe option @option{-dB} causes a debugging dump of the RTL code after 50790075Sobrienthis pass. This dump file's name is made by appending @samp{.bbro} to 50890075Sobrienthe input file name. 50990075Sobrien 51090075Sobrien@cindex delayed branch scheduling 51190075Sobrien@cindex scheduling, delayed branch 51290075Sobrien@item 51390075SobrienDelayed branch scheduling. This optional pass attempts to find 51490075Sobrieninstructions that can go into the delay slots of other instructions, 51590075Sobrienusually jumps and calls. The source file name is @file{reorg.c}. 51690075Sobrien 51790075Sobrien@opindex dd 51890075SobrienThe option @option{-dd} causes a debugging dump of the RTL code after 51990075Sobrienthis pass. This dump file's name is made by appending @samp{.dbr} 52090075Sobriento the input file name. 52190075Sobrien 52290075Sobrien@cindex branch shortening 52390075Sobrien@item 52490075SobrienBranch shortening. On many RISC machines, branch instructions have a 52590075Sobrienlimited range. Thus, longer sequences of instructions must be used for 52690075Sobrienlong branches. In this pass, the compiler figures out what how far each 52790075Sobrieninstruction will be from each other instruction, and therefore whether 52890075Sobrienthe usual instructions, or the longer sequences, must be used for each 52990075Sobrienbranch. 53090075Sobrien 53190075Sobrien@cindex register-to-stack conversion 53290075Sobrien@item 53390075SobrienConversion from usage of some hard registers to usage of a register 53490075Sobrienstack may be done at this point. Currently, this is supported only 53590075Sobrienfor the floating-point registers of the Intel 80387 coprocessor. The 53690075Sobriensource file name is @file{reg-stack.c}. 53790075Sobrien 53890075Sobrien@opindex dk 53990075SobrienThe options @option{-dk} causes a debugging dump of the RTL code after 54090075Sobrienthis pass. This dump file's name is made by appending @samp{.stack} 54190075Sobriento the input file name. 54290075Sobrien 54390075Sobrien@cindex final pass 54490075Sobrien@cindex peephole optimization 54590075Sobrien@item 54690075SobrienFinal. This pass outputs the assembler code for the function. It is 54790075Sobrienalso responsible for identifying spurious test and compare 54890075Sobrieninstructions. Machine-specific peephole optimizations are performed 54990075Sobrienat the same time. The function entry and exit sequences are generated 55090075Sobriendirectly as assembler code in this pass; they never exist as RTL@. 55190075Sobrien 55290075SobrienThe source files are @file{final.c} plus @file{insn-output.c}; the 55390075Sobrienlatter is generated automatically from the machine description by the 55490075Sobrientool @file{genoutput}. The header file @file{conditions.h} is used 55590075Sobrienfor communication between these files. 55690075Sobrien 55790075Sobrien@cindex debugging information generation 55890075Sobrien@item 55990075SobrienDebugging information output. This is run after final because it must 56090075Sobrienoutput the stack slot offsets for pseudo registers that did not get 56190075Sobrienhard registers. Source files are @file{dbxout.c} for DBX symbol table 56290075Sobrienformat, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c} 56390075Sobrienfor DWARF symbol table format, files @file{dwarf2out.c} and 56490075Sobrien@file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c} 56590075Sobrienfor VMS debug symbol table format. 56690075Sobrien@end itemize 56790075Sobrien 56890075SobrienSome additional files are used by all or many passes: 56990075Sobrien 57090075Sobrien@itemize @bullet 57190075Sobrien@item 57290075SobrienEvery pass uses @file{machmode.def} and @file{machmode.h} which define 57390075Sobrienthe machine modes. 57490075Sobrien 57590075Sobrien@item 57690075SobrienSeveral passes use @file{real.h}, which defines the default 57790075Sobrienrepresentation of floating point constants and how to operate on them. 57890075Sobrien 57990075Sobrien@item 58090075SobrienAll the passes that work with RTL use the header files @file{rtl.h} 58190075Sobrienand @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools 58290075Sobrien@code{gen*} also use these files to read and work with the machine 58390075Sobriendescription RTL@. 58490075Sobrien 58590075Sobrien@item 58690075SobrienAll the tools that read the machine description use support routines 58790075Sobrienfound in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}. 58890075Sobrien 58990075Sobrien@findex genconfig 59090075Sobrien@item 59190075SobrienSeveral passes refer to the header file @file{insn-config.h} which 59290075Sobriencontains a few parameters (C macro definitions) generated 59390075Sobrienautomatically from the machine description RTL by the tool 59490075Sobrien@code{genconfig}. 59590075Sobrien 59690075Sobrien@cindex instruction recognizer 59790075Sobrien@item 59890075SobrienSeveral passes use the instruction recognizer, which consists of 59990075Sobrien@file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c} 60090075Sobrienand @file{insn-extract.c} that are generated automatically from the 60190075Sobrienmachine description by the tools @file{genrecog} and 60290075Sobrien@file{genextract}. 60390075Sobrien 60490075Sobrien@item 60590075SobrienSeveral passes use the header files @file{regs.h} which defines the 60690075Sobrieninformation recorded about pseudo register usage, and @file{basic-block.h} 60790075Sobrienwhich defines the information recorded about basic blocks. 60890075Sobrien 60990075Sobrien@item 61090075Sobrien@file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector 61190075Sobrienwith a bit for each hard register, and some macros to manipulate it. 61290075SobrienThis type is just @code{int} if the machine has few enough hard registers; 61390075Sobrienotherwise it is an array of @code{int} and some of the macros expand 61490075Sobrieninto loops. 61590075Sobrien 61690075Sobrien@item 61790075SobrienSeveral passes use instruction attributes. A definition of the 61890075Sobrienattributes defined for a particular machine is in file 61990075Sobrien@file{insn-attr.h}, which is generated from the machine description by 62090075Sobrienthe program @file{genattr}. The file @file{insn-attrtab.c} contains 621117395Skansubroutines to obtain the attribute values for insns and information 622117395Skanabout processor pipeline characteristics for the instruction 623117395Skanscheduler. It is generated from the machine description by the 624117395Skanprogram @file{genattrtab}. 62590075Sobrien@end itemize 626