passes.texi revision 90075
190075Sobrien@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 290075Sobrien@c 1999, 2000, 2001 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 1590075Sobrienclosing files, and sequencing the passes. 1690075Sobrien 1790075Sobrien@cindex parsing pass 1890075SobrienThe parsing pass is invoked only once, to parse the entire input. A 1990075Sobrienhigh level tree representation is then generated from the input, 2090075Sobrienone function at a time. This tree code is then transformed into RTL 2190075Sobrienintermediate code, and processed. The files involved in transforming 2290075Sobrienthe trees into RTL are @file{expr.c}, @file{expmed.c}, and 2390075Sobrien@file{stmt.c}. 2490075Sobrien@c Note, the above files aren't strictly the only files involved. It's 2590075Sobrien@c all over the place (function.c, final.c,etc). However, those are 2690075Sobrien@c the files that are supposed to be directly involved, and have 2790075Sobrien@c their purpose listed as such, so i've only listed them. 2890075SobrienThe order of trees that are processed, is not 2990075Sobriennecessarily the same order they are generated from 3090075Sobrienthe input, due to deferred inlining, and other considerations. 3190075Sobrien 3290075Sobrien@findex rest_of_compilation 3390075Sobrien@findex rest_of_decl_compilation 3490075SobrienEach time the parsing pass reads a complete function definition or 3590075Sobrientop-level declaration, it calls either the function 3690075Sobrien@code{rest_of_compilation}, or the function 3790075Sobrien@code{rest_of_decl_compilation} in @file{toplev.c}, which are 3890075Sobrienresponsible for all further processing necessary, ending with output of 3990075Sobrienthe assembler language. All other compiler passes run, in sequence, 4090075Sobrienwithin @code{rest_of_compilation}. When that function returns from 4190075Sobriencompiling a function definition, the storage used for that function 4290075Sobriendefinition's compilation is entirely freed, unless it is an inline 4390075Sobrienfunction, or was deferred for some reason (this can occur in 4490075Sobrientemplates, for example). 4590075Sobrien(@pxref{Inline,,An Inline Function is As Fast As a Macro,gcc,Using the 4690075SobrienGNU Compiler Collection (GCC)}). 4790075Sobrien 4890075SobrienHere is a list of all the passes of the compiler and their source files. 4990075SobrienAlso included is a description of where debugging dumps can be requested 5090075Sobrienwith @option{-d} options. 5190075Sobrien 5290075Sobrien@itemize @bullet 5390075Sobrien@item 5490075SobrienParsing. This pass reads the entire text of a function definition, 5590075Sobrienconstructing a high level tree representation. (Because of the semantic 5690075Sobrienanalysis that takes place during this pass, it does more than is 5790075Sobrienformally considered to be parsing.) 5890075Sobrien 5990075SobrienThe tree representation does not entirely follow C syntax, because it is 6090075Sobrienintended to support other languages as well. 6190075Sobrien 6290075SobrienLanguage-specific data type analysis is also done in this pass, and every 6390075Sobrientree node that represents an expression has a data type attached. 6490075SobrienVariables are represented as declaration nodes. 6590075Sobrien 6690075SobrienThe language-independent source files for parsing are 6790075Sobrien@file{tree.c}, @file{fold-const.c}, and @file{stor-layout.c}. 6890075SobrienThere are also header files @file{tree.h} and @file{tree.def} 6990075Sobrienwhich define the format of the tree representation. 7090075Sobrien 7190075SobrienC preprocessing, for language front ends, that want or require it, is 7290075Sobrienperformed by cpplib, which is covered in separate documentation. In 7390075Sobrienparticular, the internals are covered in @xref{Top, ,Cpplib internals, 7490075Sobriencppinternals, Cpplib Internals}. 7590075Sobrien 7690075Sobrien@c Avoiding overfull is tricky here. 7790075SobrienThe source files to parse C are 7890075Sobrien@file{c-convert.c}, 7990075Sobrien@file{c-decl.c}, 8090075Sobrien@file{c-errors.c}, 8190075Sobrien@file{c-lang.c}, 8290075Sobrien@file{c-objc-common.c}, 8390075Sobrien@file{c-parse.in}, 8490075Sobrien@file{c-aux-info.c}, 8590075Sobrienand 8690075Sobrien@file{c-typeck.c}, 8790075Sobrienalong with a header file 8890075Sobrien@file{c-tree.h} 8990075Sobrienand some files shared with Objective-C and C++. 9090075Sobrien 9190075SobrienThe source files for parsing C++ are in @file{cp/}. 9290075SobrienThey are @file{parse.y}, 9390075Sobrien@file{class.c}, 9490075Sobrien@file{cvt.c}, @file{decl.c}, @file{decl2.c}, 9590075Sobrien@file{except.c}, 9690075Sobrien@file{expr.c}, @file{init.c}, @file{lex.c}, 9790075Sobrien@file{method.c}, @file{ptree.c}, 9890075Sobrien@file{search.c}, @file{spew.c}, 9990075Sobrien@file{semantics.c}, @file{tree.c}, 10090075Sobrien@file{typeck2.c}, and 10190075Sobrien@file{typeck.c}, along with header files @file{cp-tree.def}, 10290075Sobrien@file{cp-tree.h}, and @file{decl.h}. 10390075Sobrien 10490075SobrienThe special source files for parsing Objective-C are in @file{objc/}. 10590075SobrienThey are @file{objc-act.c}, @file{objc-tree.def}, and @file{objc-act.h}. 10690075SobrienCertain C-specific files are used for this as well. 10790075Sobrien 10890075SobrienThe files 10990075Sobrien@file{c-common.c}, 11090075Sobrien@file{c-common.def}, 11190075Sobrien@file{c-format.c}, 11290075Sobrien@file{c-pragma.c}, 11390075Sobrien@file{c-semantics.c}, 11490075Sobrienand 11590075Sobrien@file{c-lex.c}, 11690075Sobrienalong with header files 11790075Sobrien@file{c-common.h}, 11890075Sobrien@file{c-dump.h}, 11990075Sobrien@file{c-lex.h}, 12090075Sobrienand 12190075Sobrien@file{c-pragma.h}, 12290075Sobrienare also used for all of the above languages. 12390075Sobrien 12490075Sobrien 12590075Sobrien@cindex Tree optimization 12690075Sobrien@item 12790075SobrienTree optimization. This is the optimization of the tree 12890075Sobrienrepresentation, before converting into RTL code. 12990075Sobrien 13090075Sobrien@cindex inline on trees, automatic 13190075SobrienCurrently, the main optimization performed here is tree-based 13290075Sobrieninlining. 13390075SobrienThis is implemented in @file{tree-inline.c} and used by both C and C++. 13490075SobrienNote that tree based inlining turns off rtx based inlining (since it's more 13590075Sobrienpowerful, it would be a waste of time to do rtx based inlining in 13690075Sobrienaddition). 13790075Sobrien 13890075Sobrien@cindex constant folding 13990075Sobrien@cindex arithmetic simplifications 14090075Sobrien@cindex simplifications, arithmetic 14190075SobrienConstant folding and some arithmetic simplifications are also done 14290075Sobrienduring this pass, on the tree representation. 14390075SobrienThe routines that perform these tasks are located in @file{fold-const.c}. 14490075Sobrien 14590075Sobrien@cindex RTL generation 14690075Sobrien@item 14790075SobrienRTL generation. This is the conversion of syntax tree into RTL code. 14890075Sobrien 14990075Sobrien@cindex target-parameter-dependent code 15090075SobrienThis is where the bulk of target-parameter-dependent code is found, 15190075Sobriensince often it is necessary for strategies to apply only when certain 15290075Sobrienstandard kinds of instructions are available. The purpose of named 15390075Sobrieninstruction patterns is to provide this information to the RTL 15490075Sobriengeneration pass. 15590075Sobrien 15690075Sobrien@cindex tail recursion optimization 15790075SobrienOptimization is done in this pass for @code{if}-conditions that are 15890075Sobriencomparisons, boolean operations or conditional expressions. Tail 15990075Sobrienrecursion is detected at this time also. Decisions are made about how 16090075Sobrienbest to arrange loops and how to output @code{switch} statements. 16190075Sobrien 16290075Sobrien@c Avoiding overfull is tricky here. 16390075SobrienThe source files for RTL generation include 16490075Sobrien@file{stmt.c}, 16590075Sobrien@file{calls.c}, 16690075Sobrien@file{expr.c}, 16790075Sobrien@file{explow.c}, 16890075Sobrien@file{expmed.c}, 16990075Sobrien@file{function.c}, 17090075Sobrien@file{optabs.c} 17190075Sobrienand @file{emit-rtl.c}. 17290075SobrienAlso, the file 17390075Sobrien@file{insn-emit.c}, generated from the machine description by the 17490075Sobrienprogram @code{genemit}, is used in this pass. The header file 17590075Sobrien@file{expr.h} is used for communication within this pass. 17690075Sobrien 17790075Sobrien@findex genflags 17890075Sobrien@findex gencodes 17990075SobrienThe header files @file{insn-flags.h} and @file{insn-codes.h}, 18090075Sobriengenerated from the machine description by the programs @code{genflags} 18190075Sobrienand @code{gencodes}, tell this pass which standard names are available 18290075Sobrienfor use and which patterns correspond to them. 18390075Sobrien 18490075SobrienAside from debugging information output, none of the following passes 18590075Sobrienrefers to the tree structure representation of the function (only 18690075Sobrienpart of which is saved). 18790075Sobrien 18890075Sobrien@cindex inline on rtx, automatic 18990075SobrienThe decision of whether the function can and should be expanded inline 19090075Sobrienin its subsequent callers is made at the end of rtl generation. The 19190075Sobrienfunction must meet certain criteria, currently related to the size of 19290075Sobrienthe function and the types and number of parameters it has. Note that 19390075Sobrienthis function may contain loops, recursive calls to itself 19490075Sobrien(tail-recursive functions can be inlined!), gotos, in short, all 19590075Sobrienconstructs supported by GCC@. The file @file{integrate.c} contains 19690075Sobrienthe code to save a function's rtl for later inlining and to inline that 19790075Sobrienrtl when the function is called. The header file @file{integrate.h} 19890075Sobrienis also used for this purpose. 19990075Sobrien 20090075Sobrien@opindex dr 20190075SobrienThe option @option{-dr} causes a debugging dump of the RTL code after 20290075Sobrienthis pass. This dump file's name is made by appending @samp{.rtl} to 20390075Sobrienthe input file name. 20490075Sobrien 20590075Sobrien@c Should the exception handling pass be talked about here? 20690075Sobrien 20790075Sobrien@cindex sibling call optimization 20890075Sobrien@item 20990075SobrienSibiling call optimization. This pass performs tail recursion 21090075Sobrienelimination, and tail and sibling call optimizations. The purpose of 21190075Sobrienthese optimizations is to reduce the overhead of function calls, 21290075Sobrienwhenever possible. 21390075Sobrien 21490075SobrienThe source file of this pass is @file{sibcall.c} 21590075Sobrien 21690075Sobrien@opindex di 21790075SobrienThe option @option{-di} causes a debugging dump of the RTL code after 21890075Sobrienthis pass is run. This dump file's name is made by appending 21990075Sobrien@samp{.sibling} to the input file name. 22090075Sobrien 22190075Sobrien@cindex jump optimization 22290075Sobrien@cindex unreachable code 22390075Sobrien@cindex dead code 22490075Sobrien@item 22590075SobrienJump optimization. This pass simplifies jumps to the following 22690075Sobrieninstruction, jumps across jumps, and jumps to jumps. It deletes 22790075Sobrienunreferenced labels and unreachable code, except that unreachable code 22890075Sobrienthat contains a loop is not recognized as unreachable in this pass. 22990075Sobrien(Such loops are deleted later in the basic block analysis.) It also 23090075Sobrienconverts some code originally written with jumps into sequences of 23190075Sobrieninstructions that directly set values from the results of comparisons, 23290075Sobrienif the machine has such instructions. 23390075Sobrien 23490075SobrienJump optimization is performed two or three times. The first time is 23590075Sobrienimmediately following RTL generation. The second time is after CSE, 23690075Sobrienbut only if CSE says repeated jump optimization is needed. The 23790075Sobrienlast time is right before the final pass. That time, cross-jumping 23890075Sobrienand deletion of no-op move instructions are done together with the 23990075Sobrienoptimizations described above. 24090075Sobrien 24190075SobrienThe source file of this pass is @file{jump.c}. 24290075Sobrien 24390075Sobrien@opindex dj 24490075SobrienThe option @option{-dj} causes a debugging dump of the RTL code after 24590075Sobrienthis pass is run for the first time. This dump file's name is made by 24690075Sobrienappending @samp{.jump} to the input file name. 24790075Sobrien 24890075Sobrien 24990075Sobrien@cindex register use analysis 25090075Sobrien@item 25190075SobrienRegister scan. This pass finds the first and last use of each 25290075Sobrienregister, as a guide for common subexpression elimination. Its source 25390075Sobrienis in @file{regclass.c}. 25490075Sobrien 25590075Sobrien@cindex jump threading 25690075Sobrien@item 25790075Sobrien@opindex fthread-jumps 25890075SobrienJump threading. This pass detects a condition jump that branches to an 25990075Sobrienidentical or inverse test. Such jumps can be @samp{threaded} through 26090075Sobrienthe second conditional test. The source code for this pass is in 26190075Sobrien@file{jump.c}. This optimization is only performed if 26290075Sobrien@option{-fthread-jumps} is enabled. 26390075Sobrien 26490075Sobrien@cindex SSA optimizations 26590075Sobrien@cindex Single Static Assignment optimizations 26690075Sobrien@opindex fssa 26790075Sobrien@item 26890075SobrienStatic Single Assignment (SSA) based optimization passes. The 26990075SobrienSSA conversion passes (to/from) are turned on by the @option{-fssa} 27090075Sobrienoption (it is also done automatically if you enable an SSA optimization pass). 27190075SobrienThese passes utilize a form called Static Single Assignment. In SSA form, 27290075Sobrieneach variable (pseudo register) is only set once, giving you def-use 27390075Sobrienand use-def chains for free, and enabling a lot more optimization 27490075Sobrienpasses to be run in linear time. 27590075SobrienConversion to and from SSA form is handled by functions in 27690075Sobrien@file{ssa.c}. 27790075Sobrien 27890075Sobrien@opindex de 27990075SobrienThe option @option{-de} causes a debugging dump of the RTL code after 28090075Sobrienthis pass. This dump file's name is made by appending @samp{.ssa} to 28190075Sobrienthe input file name. 28290075Sobrien@itemize @bullet 28390075Sobrien@cindex SSA Conditional Constant Propagation 28490075Sobrien@cindex Conditional Constant Propagation, SSA based 28590075Sobrien@cindex conditional constant propagation 28690075Sobrien@opindex fssa-ccp 28790075Sobrien@item 28890075SobrienSSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp} 28990075SobrienSSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce} 29090075Sobrienoption. This pass performs conditional constant propagation to simplify 29190075Sobrieninstructions including conditional branches. This pass is more aggressive 29290075Sobrienthan the constant propgation done by the CSE and GCSE pases, but operates 29390075Sobrienin linear time. 29490075Sobrien 29590075Sobrien@opindex dW 29690075SobrienThe option @option{-dW} causes a debugging dump of the RTL code after 29790075Sobrienthis pass. This dump file's name is made by appending @samp{.ssaccp} to 29890075Sobrienthe input file name. 29990075Sobrien 30090075Sobrien@cindex SSA DCE 30190075Sobrien@cindex DCE, SSA based 30290075Sobrien@cindex dead code elimination 30390075Sobrien@opindex fssa-dce 30490075Sobrien@item 30590075SobrienSSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce} 30690075Sobrienoption. This pass performs elimination of code considered unnecessary because 30790075Sobrienit has no externally visible effects on the program. It operates in 30890075Sobrienlinear time. 30990075Sobrien 31090075Sobrien@opindex dX 31190075SobrienThe option @option{-dX} causes a debugging dump of the RTL code after 31290075Sobrienthis pass. This dump file's name is made by appending @samp{.ssadce} to 31390075Sobrienthe input file name. 31490075Sobrien@end itemize 31590075Sobrien 31690075Sobrien@cindex common subexpression elimination 31790075Sobrien@cindex constant propagation 31890075Sobrien@item 31990075SobrienCommon subexpression elimination. This pass also does constant 32090075Sobrienpropagation. Its source files are @file{cse.c}, and @file{cselib.c}. 32190075SobrienIf constant propagation causes conditional jumps to become 32290075Sobrienunconditional or to become no-ops, jump optimization is run again when 32390075SobrienCSE is finished. 32490075Sobrien 32590075Sobrien@opindex ds 32690075SobrienThe option @option{-ds} causes a debugging dump of the RTL code after 32790075Sobrienthis pass. This dump file's name is made by appending @samp{.cse} to 32890075Sobrienthe input file name. 32990075Sobrien 33090075Sobrien@cindex global common subexpression elimination 33190075Sobrien@cindex constant propagation 33290075Sobrien@cindex copy propagation 33390075Sobrien@item 33490075SobrienGlobal common subexpression elimination. This pass performs two 33590075Sobriendifferent types of GCSE depending on whether you are optimizing for 33690075Sobriensize or not (LCM based GCSE tends to increase code size for a gain in 33790075Sobrienspeed, while Morel-Renvoise based GCSE does not). 33890075SobrienWhen optimizing for size, GCSE is done using Morel-Renvoise Partial 33990075SobrienRedundancy Elimination, with the exception that it does not try to move 34090075Sobrieninvariants out of loops---that is left to the loop optimization pass. 34190075SobrienIf MR PRE GCSE is done, code hoisting (aka unification) is also done, as 34290075Sobrienwell as load motion. 34390075SobrienIf you are optimizing for speed, LCM (lazy code motion) based GCSE is 34490075Sobriendone. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM 34590075Sobrienbased GCSE also does loop invariant code motion. We also perform load 34690075Sobrienand store motion when optimizing for speed. 34790075SobrienRegardless of which type of GCSE is used, the GCSE pass also performs 34890075Sobrienglobal constant and copy propagation. 34990075Sobrien 35090075SobrienThe source file for this pass is @file{gcse.c}, and the LCM routines 35190075Sobrienare in @file{lcm.c}. 35290075Sobrien 35390075Sobrien@opindex dG 35490075SobrienThe option @option{-dG} causes a debugging dump of the RTL code after 35590075Sobrienthis pass. This dump file's name is made by appending @samp{.gcse} to 35690075Sobrienthe input file name. 35790075Sobrien 35890075Sobrien@cindex loop optimization 35990075Sobrien@cindex code motion 36090075Sobrien@cindex strength-reduction 36190075Sobrien@item 36290075SobrienLoop optimization. This pass moves constant expressions out of loops, 36390075Sobrienand optionally does strength-reduction and loop unrolling as well. 36490075SobrienIts source files are @file{loop.c} and @file{unroll.c}, plus the header 36590075Sobrien@file{loop.h} used for communication between them. Loop unrolling uses 36690075Sobriensome functions in @file{integrate.c} and the header @file{integrate.h}. 36790075SobrienLoop dependency analysis routines are contained in @file{dependence.c}. 36890075Sobrien 36990075Sobrien@opindex dL 37090075SobrienThe option @option{-dL} causes a debugging dump of the RTL code after 37190075Sobrienthis pass. This dump file's name is made by appending @samp{.loop} to 37290075Sobrienthe input file name. 37390075Sobrien 37490075Sobrien@item 37590075Sobrien@opindex frerun-cse-after-loop 37690075SobrienIf @option{-frerun-cse-after-loop} was enabled, a second common 37790075Sobriensubexpression elimination pass is performed after the loop optimization 37890075Sobrienpass. Jump threading is also done again at this time if it was specified. 37990075Sobrien 38090075Sobrien@opindex dt 38190075SobrienThe option @option{-dt} causes a debugging dump of the RTL code after 38290075Sobrienthis pass. This dump file's name is made by appending @samp{.cse2} to 38390075Sobrienthe input file name. 38490075Sobrien 38590075Sobrien@cindex data flow analysis 38690075Sobrien@cindex analysis, data flow 38790075Sobrien@cindex basic blocks 38890075Sobrien@item 38990075SobrienData flow analysis (@file{flow.c}). This pass divides the program 39090075Sobrieninto basic blocks (and in the process deletes unreachable loops); then 39190075Sobrienit computes which pseudo-registers are live at each point in the 39290075Sobrienprogram, and makes the first instruction that uses a value point at 39390075Sobrienthe instruction that computed the value. 39490075Sobrien 39590075Sobrien@cindex autoincrement/decrement analysis 39690075SobrienThis pass also deletes computations whose results are never used, and 39790075Sobriencombines memory references with add or subtract instructions to make 39890075Sobrienautoincrement or autodecrement addressing. 39990075Sobrien 40090075Sobrien@opindex df 40190075SobrienThe option @option{-df} causes a debugging dump of the RTL code after 40290075Sobrienthis pass. This dump file's name is made by appending @samp{.flow} to 40390075Sobrienthe input file name. If stupid register allocation is in use, this 40490075Sobriendump file reflects the full results of such allocation. 40590075Sobrien 40690075Sobrien@cindex instruction combination 40790075Sobrien@item 40890075SobrienInstruction combination (@file{combine.c}). This pass attempts to 40990075Sobriencombine groups of two or three instructions that are related by data 41090075Sobrienflow into single instructions. It combines the RTL expressions for 41190075Sobrienthe instructions by substitution, simplifies the result using algebra, 41290075Sobrienand then attempts to match the result against the machine description. 41390075Sobrien 41490075Sobrien@opindex dc 41590075SobrienThe option @option{-dc} causes a debugging dump of the RTL code after 41690075Sobrienthis pass. This dump file's name is made by appending @samp{.combine} 41790075Sobriento the input file name. 41890075Sobrien 41990075Sobrien@cindex if conversion 42090075Sobrien@item 42190075SobrienIf-conversion is a transformation that transforms control dependencies 42290075Sobrieninto data dependencies (IE it transforms conditional code into a 42390075Sobriensingle control stream). 42490075SobrienIt is implemented in the file @file{ifcvt.c}. 42590075Sobrien 42690075Sobrien@opindex dE 42790075SobrienThe option @option{-dE} causes a debugging dump of the RTL code after 42890075Sobrienthis pass. This dump file's name is made by appending @samp{.ce} to 42990075Sobrienthe input file name. 43090075Sobrien 43190075Sobrien@cindex register movement 43290075Sobrien@item 43390075SobrienRegister movement (@file{regmove.c}). This pass looks for cases where 43490075Sobrienmatching constraints would force an instruction to need a reload, and 43590075Sobrienthis reload would be a register-to-register move. It then attempts 43690075Sobriento change the registers used by the instruction to avoid the move 43790075Sobrieninstruction. 43890075Sobrien 43990075Sobrien@opindex dN 44090075SobrienThe option @option{-dN} causes a debugging dump of the RTL code after 44190075Sobrienthis pass. This dump file's name is made by appending @samp{.regmove} 44290075Sobriento the input file name. 44390075Sobrien 44490075Sobrien@cindex instruction scheduling 44590075Sobrien@cindex scheduling, instruction 44690075Sobrien@item 44790075SobrienInstruction scheduling (@file{sched.c}). This pass looks for 44890075Sobrieninstructions whose output will not be available by the time that it is 44990075Sobrienused in subsequent instructions. (Memory loads and floating point 45090075Sobrieninstructions often have this behavior on RISC machines). It re-orders 45190075Sobrieninstructions within a basic block to try to separate the definition and 45290075Sobrienuse of items that otherwise would cause pipeline stalls. 45390075Sobrien 45490075SobrienInstruction scheduling is performed twice. The first time is immediately 45590075Sobrienafter instruction combination and the second is immediately after reload. 45690075Sobrien 45790075Sobrien@opindex dS 45890075SobrienThe option @option{-dS} causes a debugging dump of the RTL code after this 45990075Sobrienpass is run for the first time. The dump file's name is made by 46090075Sobrienappending @samp{.sched} to the input file name. 46190075Sobrien 46290075Sobrien@cindex register class preference pass 46390075Sobrien@item 46490075SobrienRegister class preferencing. The RTL code is scanned to find out 46590075Sobrienwhich register class is best for each pseudo register. The source 46690075Sobrienfile is @file{regclass.c}. 46790075Sobrien 46890075Sobrien@cindex register allocation 46990075Sobrien@cindex local register allocation 47090075Sobrien@item 47190075SobrienLocal register allocation (@file{local-alloc.c}). This pass allocates 47290075Sobrienhard registers to pseudo registers that are used only within one basic 47390075Sobrienblock. Because the basic block is linear, it can use fast and 47490075Sobrienpowerful techniques to do a very good job. 47590075Sobrien 47690075Sobrien@opindex dl 47790075SobrienThe option @option{-dl} causes a debugging dump of the RTL code after 47890075Sobrienthis pass. This dump file's name is made by appending @samp{.lreg} to 47990075Sobrienthe input file name. 48090075Sobrien 48190075Sobrien@cindex global register allocation 48290075Sobrien@item 48390075SobrienGlobal register allocation (@file{global.c}). This pass 48490075Sobrienallocates hard registers for the remaining pseudo registers (those 48590075Sobrienwhose life spans are not contained in one basic block). 48690075Sobrien 48790075Sobrien@cindex reloading 48890075Sobrien@item 48990075SobrienReloading. This pass renumbers pseudo registers with the hardware 49090075Sobrienregisters numbers they were allocated. Pseudo registers that did not 49190075Sobrienget hard registers are replaced with stack slots. Then it finds 49290075Sobrieninstructions that are invalid because a value has failed to end up in 49390075Sobriena register, or has ended up in a register of the wrong kind. It fixes 49490075Sobrienup these instructions by reloading the problematical values 49590075Sobrientemporarily into registers. Additional instructions are generated to 49690075Sobriendo the copying. 49790075Sobrien 49890075SobrienThe reload pass also optionally eliminates the frame pointer and inserts 49990075Sobrieninstructions to save and restore call-clobbered registers around calls. 50090075Sobrien 50190075SobrienSource files are @file{reload.c} and @file{reload1.c}, plus the header 50290075Sobrien@file{reload.h} used for communication between them. 50390075Sobrien 50490075Sobrien@opindex dg 50590075SobrienThe option @option{-dg} causes a debugging dump of the RTL code after 50690075Sobrienthis pass. This dump file's name is made by appending @samp{.greg} to 50790075Sobrienthe input file name. 50890075Sobrien 50990075Sobrien@cindex instruction scheduling 51090075Sobrien@cindex scheduling, instruction 51190075Sobrien@item 51290075SobrienInstruction scheduling is repeated here to try to avoid pipeline stalls 51390075Sobriendue to memory loads generated for spilled pseudo registers. 51490075Sobrien 51590075Sobrien@opindex dR 51690075SobrienThe option @option{-dR} causes a debugging dump of the RTL code after 51790075Sobrienthis pass. This dump file's name is made by appending @samp{.sched2} 51890075Sobriento the input file name. 51990075Sobrien 52090075Sobrien@cindex basic block reordering 52190075Sobrien@cindex reordering, block 52290075Sobrien@item 52390075SobrienBasic block reordering. This pass implements profile guided code 52490075Sobrienpositioning. If profile information is not available, various types of 52590075Sobrienstatic analysis are performed to make the predictions normally coming 52690075Sobrienfrom the profile feedback (IE execution frequency, branch probability, 52790075Sobrienetc). It is implemented in the file @file{bb-reorder.c}, and the 52890075Sobrienvarious prediction routines are in @file{predict.c}. 52990075Sobrien 53090075Sobrien@opindex dB 53190075SobrienThe option @option{-dB} causes a debugging dump of the RTL code after 53290075Sobrienthis pass. This dump file's name is made by appending @samp{.bbro} to 53390075Sobrienthe input file name. 53490075Sobrien 53590075Sobrien@cindex cross-jumping 53690075Sobrien@cindex no-op move instructions 53790075Sobrien@item 53890075SobrienJump optimization is repeated, this time including cross-jumping 53990075Sobrienand deletion of no-op move instructions. 54090075Sobrien 54190075Sobrien@opindex dJ 54290075SobrienThe option @option{-dJ} causes a debugging dump of the RTL code after 54390075Sobrienthis pass. This dump file's name is made by appending @samp{.jump2} 54490075Sobriento the input file name. 54590075Sobrien 54690075Sobrien@cindex delayed branch scheduling 54790075Sobrien@cindex scheduling, delayed branch 54890075Sobrien@item 54990075SobrienDelayed branch scheduling. This optional pass attempts to find 55090075Sobrieninstructions that can go into the delay slots of other instructions, 55190075Sobrienusually jumps and calls. The source file name is @file{reorg.c}. 55290075Sobrien 55390075Sobrien@opindex dd 55490075SobrienThe option @option{-dd} causes a debugging dump of the RTL code after 55590075Sobrienthis pass. This dump file's name is made by appending @samp{.dbr} 55690075Sobriento the input file name. 55790075Sobrien 55890075Sobrien@cindex branch shortening 55990075Sobrien@item 56090075SobrienBranch shortening. On many RISC machines, branch instructions have a 56190075Sobrienlimited range. Thus, longer sequences of instructions must be used for 56290075Sobrienlong branches. In this pass, the compiler figures out what how far each 56390075Sobrieninstruction will be from each other instruction, and therefore whether 56490075Sobrienthe usual instructions, or the longer sequences, must be used for each 56590075Sobrienbranch. 56690075Sobrien 56790075Sobrien@cindex register-to-stack conversion 56890075Sobrien@item 56990075SobrienConversion from usage of some hard registers to usage of a register 57090075Sobrienstack may be done at this point. Currently, this is supported only 57190075Sobrienfor the floating-point registers of the Intel 80387 coprocessor. The 57290075Sobriensource file name is @file{reg-stack.c}. 57390075Sobrien 57490075Sobrien@opindex dk 57590075SobrienThe options @option{-dk} causes a debugging dump of the RTL code after 57690075Sobrienthis pass. This dump file's name is made by appending @samp{.stack} 57790075Sobriento the input file name. 57890075Sobrien 57990075Sobrien@cindex final pass 58090075Sobrien@cindex peephole optimization 58190075Sobrien@item 58290075SobrienFinal. This pass outputs the assembler code for the function. It is 58390075Sobrienalso responsible for identifying spurious test and compare 58490075Sobrieninstructions. Machine-specific peephole optimizations are performed 58590075Sobrienat the same time. The function entry and exit sequences are generated 58690075Sobriendirectly as assembler code in this pass; they never exist as RTL@. 58790075Sobrien 58890075SobrienThe source files are @file{final.c} plus @file{insn-output.c}; the 58990075Sobrienlatter is generated automatically from the machine description by the 59090075Sobrientool @file{genoutput}. The header file @file{conditions.h} is used 59190075Sobrienfor communication between these files. 59290075Sobrien 59390075Sobrien@cindex debugging information generation 59490075Sobrien@item 59590075SobrienDebugging information output. This is run after final because it must 59690075Sobrienoutput the stack slot offsets for pseudo registers that did not get 59790075Sobrienhard registers. Source files are @file{dbxout.c} for DBX symbol table 59890075Sobrienformat, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c} 59990075Sobrienfor DWARF symbol table format, files @file{dwarf2out.c} and 60090075Sobrien@file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c} 60190075Sobrienfor VMS debug symbol table format. 60290075Sobrien@end itemize 60390075Sobrien 60490075SobrienSome additional files are used by all or many passes: 60590075Sobrien 60690075Sobrien@itemize @bullet 60790075Sobrien@item 60890075SobrienEvery pass uses @file{machmode.def} and @file{machmode.h} which define 60990075Sobrienthe machine modes. 61090075Sobrien 61190075Sobrien@item 61290075SobrienSeveral passes use @file{real.h}, which defines the default 61390075Sobrienrepresentation of floating point constants and how to operate on them. 61490075Sobrien 61590075Sobrien@item 61690075SobrienAll the passes that work with RTL use the header files @file{rtl.h} 61790075Sobrienand @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools 61890075Sobrien@code{gen*} also use these files to read and work with the machine 61990075Sobriendescription RTL@. 62090075Sobrien 62190075Sobrien@item 62290075SobrienAll the tools that read the machine description use support routines 62390075Sobrienfound in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}. 62490075Sobrien 62590075Sobrien@findex genconfig 62690075Sobrien@item 62790075SobrienSeveral passes refer to the header file @file{insn-config.h} which 62890075Sobriencontains a few parameters (C macro definitions) generated 62990075Sobrienautomatically from the machine description RTL by the tool 63090075Sobrien@code{genconfig}. 63190075Sobrien 63290075Sobrien@cindex instruction recognizer 63390075Sobrien@item 63490075SobrienSeveral passes use the instruction recognizer, which consists of 63590075Sobrien@file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c} 63690075Sobrienand @file{insn-extract.c} that are generated automatically from the 63790075Sobrienmachine description by the tools @file{genrecog} and 63890075Sobrien@file{genextract}. 63990075Sobrien 64090075Sobrien@item 64190075SobrienSeveral passes use the header files @file{regs.h} which defines the 64290075Sobrieninformation recorded about pseudo register usage, and @file{basic-block.h} 64390075Sobrienwhich defines the information recorded about basic blocks. 64490075Sobrien 64590075Sobrien@item 64690075Sobrien@file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector 64790075Sobrienwith a bit for each hard register, and some macros to manipulate it. 64890075SobrienThis type is just @code{int} if the machine has few enough hard registers; 64990075Sobrienotherwise it is an array of @code{int} and some of the macros expand 65090075Sobrieninto loops. 65190075Sobrien 65290075Sobrien@item 65390075SobrienSeveral passes use instruction attributes. A definition of the 65490075Sobrienattributes defined for a particular machine is in file 65590075Sobrien@file{insn-attr.h}, which is generated from the machine description by 65690075Sobrienthe program @file{genattr}. The file @file{insn-attrtab.c} contains 65790075Sobriensubroutines to obtain the attribute values for insns. It is generated 65890075Sobrienfrom the machine description by the program @file{genattrtab}. 65990075Sobrien@end itemize 660