1 @c markers: CROSSREF BUG TODO
3 @c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
4 @c 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
5 @c This is part of the GCC manual.
6 @c For copying conditions, see the file gcc.texi.
9 @chapter Passes and Files of the Compiler
10 @cindex passes and files of the compiler
11 @cindex files and passes of the compiler
12 @cindex compiler passes and files
14 This chapter is dedicated to giving an overview of the optimization and
15 code generation passes of the compiler. In the process, it describes
16 some of the language front end interface, though this description is no
20 * Parsing pass:: The language front end turns text into bits.
21 * Gimplification pass:: The bits are turned into something we can optimize.
22 * Pass manager:: Sequencing the optimization passes.
23 * Tree-SSA passes:: Optimizations on a high-level representation.
24 * RTL passes:: Optimizations on a low-level representation.
30 @findex lang_hooks.parse_file
31 The language front end is invoked only once, via
32 @code{lang_hooks.parse_file}, to parse the entire input. The language
33 front end may use any intermediate language representation deemed
34 appropriate. The C front end uses GENERIC trees (CROSSREF), plus
35 a double handful of language specific tree codes defined in
36 @file{c-common.def}. The Fortran front end uses a completely different
37 private representation.
40 @cindex gimplification
42 @cindex language-independent intermediate representation
43 @cindex intermediate representation lowering
44 @cindex lowering, language-dependent intermediate representation
45 At some point the front end must translate the representation used in the
46 front end to a representation understood by the language-independent
47 portions of the compiler. Current practice takes one of two forms.
48 The C front end manually invokes the gimplifier (CROSSREF) on each function,
49 and uses the gimplifier callbacks to convert the language-specific tree
50 nodes directly to GIMPLE (CROSSREF) before passing the function off to
52 The Fortran front end converts from a private representation to GENERIC,
53 which is later lowered to GIMPLE when the function is compiled. Which
54 route to choose probably depends on how well GENERIC (plus extensions)
55 can be made to match up with the source language and necessary parsing
58 BUG: Gimplification must occur before nested function lowering,
59 and nested function lowering must be done by the front end before
60 passing the data off to cgraph.
62 TODO: Cgraph should control nested function lowering. It would
63 only be invoked when it is certain that the outer-most function
66 TODO: Cgraph needs a gimplify_function callback. It should be
67 invoked when (1) it is certain that the function is used, (2)
68 warning flags specified by the user require some amount of
69 compilation in order to honor, (3) the language indicates that
70 semantic analysis is not complete until gimplification occurs.
71 Hum... this sounds overly complicated. Perhaps we should just
72 have the front end gimplify always; in most cases it's only one
75 The front end needs to pass all function definitions and top level
76 declarations off to the middle-end so that they can be compiled and
77 emitted to the object file. For a simple procedural language, it is
78 usually most convenient to do this as each top level declaration or
79 definition is seen. There is also a distinction to be made between
80 generating functional code and generating complete debug information.
81 The only thing that is absolutely required for functional code is that
82 function and data @emph{defintions} be passed to the middle-end. For
83 complete debug information, function, data and type declarations
84 should all be passed as well.
86 @findex rest_of_decl_compilation
87 @findex rest_of_type_compilation
88 @findex cgraph_finalize_function
89 In any case, the front end needs each complete top-level function or
90 data declaration, and each data definition should be passed to
91 @code{rest_of_decl_compilation}. Each complete type definition should
92 be passed to @code{rest_of_type_compilation}. Each function definition
93 should be passed to @code{cgraph_finalize_function}.
95 TODO: I know rest_of_compilation currently has all sorts of
96 rtl-generation semantics. I plan to move all code generation
97 bits (both tree and rtl) to compile_function. Should we hide
98 cgraph from the front ends and move back to rest_of_compilation
99 as the official interface? Possibly we should rename all three
100 interfaces such that the names match in some meaningful way and
101 that is more descriptive than "rest_of".
103 The middle-end will, at its option, emit the function and data
104 definitions immediately or queue them for later processing.
106 @node Gimplification pass
107 @section Gimplification pass
109 @cindex gimplification
111 @dfn{Gimplification} is a whimsical term for the process of converting
112 the intermediate representation of a function into the GIMPLE language
113 (CROSSREF). The term stuck, and so words like ``gimplification,''
114 ``gimplify,'' ``gimplifier'' and the like are sprinkled throughout this
118 While a front end may certainly choose to generate GIMPLE directly if
119 it chooses, this can be a moderately complex process unless the
120 intermediate language used by the front end is already fairly simple.
121 Usually it is easier to generate GENERIC trees plus extensions
122 and let the language-independent gimplifier do most of the work.
124 @findex gimplify_function_tree
125 @findex gimplify_expr
126 @findex lang_hooks.gimplify_expr
127 The main entry point to this pass is @code{gimplify_function_tree}
128 located in @file{gimplify.c}. From here we process the entire
129 function gimplifying each statement in turn. The main workhorse
130 for this pass is @code{gimplify_expr}. Approximately everything
131 passes through here at least once, and it is from here that we
132 invoke the @code{lang_hooks.gimplify_expr} callback.
134 The callback should examine the expression in question and return
135 @code{GS_UNHANDLED} if the expression is not a language specific
136 construct that requires attention. Otherwise it should alter the
137 expression in some way to such that forward progress is made toward
138 producing valid GIMPLE. If the callback is certain that the
139 transformation is complete and the expression is valid GIMPLE, it
140 should return @code{GS_ALL_DONE}. Otherwise it should return
141 @code{GS_OK}, which will cause the expression to be processed again.
142 If the callback encounters an error during the transformation (because
143 the front end is relying on the gimplification process to finish
144 semantic checks), it should return @code{GS_ERROR}.
147 @section Pass manager
149 The pass manager is located in @file{passes.c} and @file{passes.h}.
150 Its job is to run all of the individual passes in the correct order,
151 and take care of standard bookkeeping that applies to every pass.
153 The theory of operation is that each pass defines a structure that
154 represents everything we need to know about that pass --- when it
155 should be run, how it should be run, what intermediate language
156 form or on-the-side data structures it needs. We register the pass
157 to be run in some particular order, and the pass manager arranges
158 for everything to happen in the correct order.
160 The actuality doesn't completely live up to the theory at present.
161 Command-line switches and @code{timevar_id_t} enumerations must still
162 be defined elsewhere. The pass manager validates constraints but does
163 not attempt to (re-)generate data structures or lower intermediate
164 language form based on the requirements of the next pass. Nevertheless,
165 what is present is useful, and a far sight better than nothing at all.
167 TODO: describe the global variables set up by the pass manager,
168 and a brief description of how a new pass should use it.
169 I need to look at what info rtl passes use first...
171 @node Tree-SSA passes
172 @section Tree-SSA passes
174 The following briefly describes the tree optimization passes that are
175 run after gimplification and what source files they are located in.
178 @item Remove useless statements
180 This pass is an extremely simple sweep across the gimple code in which
181 we identify obviously dead code and remove it. Here we do things like
182 simplify @code{if} statements with constant conditions, remove
183 exception handling constructs surrounding code that obviously cannot
184 throw, remove lexical bindings that contain no variables, and other
185 assorted simplistic cleanups. The idea is to get rid of the obvious
186 stuff quickly rather than wait until later when it's more work to get
187 rid of it. This pass is located in @file{tree-cfg.c} and described by
188 @code{pass_remove_useless_stmts}.
190 @item Mudflap declaration registration
192 If mudflap (@pxref{Optimize Options,,-fmudflap -fmudflapth
193 -fmudflapir,gcc.info,Using the GNU Compiler Collection (GCC)}) is
194 enabled, we generate code to register some variable declarations with
195 the mudflap runtime. Specifically, the runtime tracks the lifetimes of
196 those variable declarations that have their addresses taken, or whose
197 bounds are unknown at compile time (@code{extern}). This pass generates
198 new exception handling constructs (@code{try}/@code{finally}), and so
199 must run before those are lowered. In addition, the pass enqueues
200 declarations of static variables whose lifetimes extend to the entire
201 program. The pass is located in @file{tree-mudflap.c} and is described
202 by @code{pass_mudflap_1}.
204 @item Lower control flow
206 This pass flattens @code{if} statements (@code{COND_EXPR}) and
207 and moves lexical bindings (@code{BIND_EXPR}) out of line. After
208 this pass, all @code{if} statements will have exactly two @code{goto}
209 statements in its @code{then} and @code{else} arms. Lexical binding
210 information for each statement will be found in @code{TREE_BLOCK} rather
211 than being inferred from its position under a @code{BIND_EXPR}. This
212 pass is found in @file{gimple-low.c} and is described by
213 @code{pass_lower_cf}.
215 @item Lower exception handling control flow
217 This pass decomposes high-level exception handling constructs
218 (@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
219 that explicitly represents the control flow involved. After this
220 pass, @code{lookup_stmt_eh_region} will return a non-negative
221 number for any statement that may have EH control flow semantics;
222 examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
223 for exact semantics. Exact control flow may be extracted from
224 @code{foreach_reachable_handler}. The EH region nesting tree is defined
225 in @file{except.h} and built in @file{except.c}. The lowering pass
226 itself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}.
228 @item Build the control flow graph
230 This pass decomposes a function into basic blocks and creates all of
231 the edges that connect them. It is located in @file{tree-cfg.c} and
232 is described by @code{pass_build_cfg}.
234 @item Find all referenced variables
236 This pass walks the entire function and collects an array of all
237 variables referenced in the function, @code{referenced_vars}. The
238 index at which a variable is found in the array is used as a UID
239 for the variable within this function. This data is needed by the
240 SSA rewriting routines. The pass is located in @file{tree-dfa.c}
241 and is described by @code{pass_referenced_vars}.
243 @item Points-to analysis
245 This pass constructs flow-insensitive alias analysis information.
246 The pass is located in @file{tree-alias-common.c} and described by
247 @code{pass_build_pta}.
249 @item Enter static single assignment form
251 This pass rewrites the function such that it is in SSA form. After
252 this pass, all @code{is_gimple_reg} variables will be referenced by
253 @code{SSA_NAME}, and all occurences of other variables will be
254 annotated with @code{VDEFS} and @code{VUSES}; phi nodes will have
255 been inserted as necessary for each basic block. This pass is
256 located in @file{tree-ssa.c} and is described by @code{pass_build_ssa}.
258 @item Warn for uninitialized variables
260 This pass scans the function for uses of @code{SSA_NAME}s that
261 are fed by default definition. For non-parameter variables, such
262 uses are uninitialized. The pass is run twice, before and after
263 optimization. In the first pass we only warn for uses that are
264 positively uninitialized; in the second pass we warn for uses that
265 are possibly uninitialized. The pass is located in @file{tree-ssa.c}
266 and is defined by @code{pass_early_warn_uninitialized} and
267 @code{pass_late_warn_uninitialized}.
269 @item Dead code elimination
271 This pass scans the function for statements without side effects whose
272 result is unused. It does not do memory life analysis, so any value
273 that is stored in memory is considered used. The pass is run multiple
274 times throughout the optimization process. It is located in
275 @file{tree-ssa-dce.c} and is described by @code{pass_dce}.
277 @item Dominator optimizations
279 This pass performs trivial dominator-based copy and constant propagation,
280 expression simplification, and jump threading. It is run multiple times
281 throughout the optimization process. It it located in @file{tree-ssa-dom.c}
282 and is described by @code{pass_dominator}.
284 @item Redundant phi elimination
286 This pass removes phi nodes for which all of the arguments are the same
287 value, excluding feedback. Such degenerate forms are typically created
288 by removing unreachable code. The pass is run multiple times throughout
289 the optimization process. It is located in @file{tree-ssa.c} and is
290 described by @code{pass_redundant_phi}.o
292 @item Forward propagation of single-use variables
294 This pass attempts to remove redundant computation by substituting
295 variables that are used once into the expression that uses them and
296 seeing if the result can be simplified. It is located in
297 @file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}.
301 This pass attempts to change the name of compiler temporaries involved in
302 copy operations such that SSA->normal can coalesce the copy away. When compiler
303 temporaries are copies of user variables, it also renames the compiler
304 temporary to the user variable resulting in better use of user symbols. It is
305 located in @file{tree-ssa-copyrename.c} and is described by
306 @code{pass_copyrename}.
308 @item PHI node optimizations
310 This pass recognizes forms of phi inputs that can be represented as
311 conditional expressions and rewrites them into straight line code.
312 It is located in @file{tree-ssa-phiopt.c} and is described by
315 @item May-alias optimization
317 This pass performs a flow sensitive SSA-based points-to analysis.
318 The resulting may-alias, must-alias, and escape analysis information
319 is used to promote variables from in-memory addressable objects to
320 non-aliased variables that can be renamed into SSA form. We also
321 update the @code{VDEF}/@code{VUSE} memory tags for non-renamable
322 aggregates so that we get fewer false kills. The pass is located
323 in @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}.
327 This pass rewrites the function in order to collect runtime block
328 and value profiling data. Such data may be fed back into the compiler
329 on a subsequent run so as to allow optimization based on expected
330 execution frequencies. The pass is located in @file{predict.c} and
331 is described by @code{pass_profile}.
333 @item Lower complex arithmetic
335 This pass rewrites complex arithmetic operations into their component
336 scalar arithmetic operations. The pass is located in @file{tree-complex.c}
337 and is described by @code{pass_lower_complex}.
339 @item Scalar replacement of aggregates
341 This pass rewrites suitable non-aliased local aggregate variables into
342 a set of scalar variables. The resulting scalar variables are
343 rewritten into SSA form, which allows subsequent optimization passes
344 to do a significantly better job with them. The pass is located in
345 @file{tree-sra.c} and is described by @code{pass_sra}.
347 @item Dead store elimination
349 This pass eliminates stores to memory that are subsequently overwritten
350 by another store, without any intervening loads. The pass is located
351 in @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
353 @item Tail recursion elimination
355 This pass transforms tail recursion into a loop. It is located in
356 @file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
358 @item Partial redundancy elimination
360 This pass eliminates partially redundant computations, as well as
361 performing load motion. The pass is located in @file{tree-ssa-pre.c}
362 and is described by @code{pass_pre}.
364 @item Loop optimization
366 The main driver of the pass is placed in @file{tree-ssa-loop.c}
367 and described by @code{pass_loop}.
369 The optimizations performed by this pass are:
371 Loop invariant motion. This pass moves only invariants that
372 would be hard to handle on rtl level (function calls, operations that expand to
373 nontrivial sequences of insns). With @option{-funswitch-loops} it also moves
374 operands of conditions that are invariant out of the loop, so that we can use
375 just trivial invariantness analysis in loop unswitching. The pass also includes
376 store motion. The pass is implemented in @file{tree-ssa-loop-im.c}.
378 The optimizations also use various utility functions contained in
379 @file{cfgloop.c}, @file{cfgloopanal.c} and @file{cfgloopmanip.c}.
381 @item Conditional constant propagation
383 This pass relaxes a lattice of values in order to identify those
384 that must be constant even in the presence of conditional branches.
385 The pass is located in @file{tree-ssa-ccp.c} and is described
388 @item Folding builtin functions
390 This pass simplifies builtin functions, as applicable, with constant
391 arguments or with inferrable string lengths. It is located in
392 @file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}.
394 @item Split critical edges
396 This pass identifies critical edges and inserts empty basic blocks
397 such that the edge is no longer critical. The pass is located in
398 @file{tree-cfg.c} and is described by @code{pass_split_crit_edges}.
400 @item Partial redundancy elimination
402 This pass answers the question ``given a hypothetical temporary
403 variable, what expressions could we eliminate?'' It is located
404 in @file{tree-ssa-pre.c} and is described by @code{pass_pre}.
406 @item Control dependence dead code elimination
408 This pass is a stronger form of dead code elimination that can
409 eliminate unnecessary control flow statements. It is located
410 in @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}.
412 @item Tail call elimination
414 This pass identifies function calls that may be rewritten into
415 jumps. No code transformation is actually applied here, but the
416 data and control flow problem is solved. The code transformation
417 requires target support, and so is delayed until RTL. In the
418 meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
419 The pass is located in @file{tree-tailcall.c} and is described by
420 @code{pass_tail_calls}. The RTL transformation is handled by
421 @code{fixup_tail_calls} in @file{calls.c}.
423 @item Warn for function return without value
425 For non-void functions, this pass locates return statements that do
426 not specify a value and issues a warning. Such a statement may have
427 been injected by falling off the end of the function. This pass is
428 run last so that we have as much time as possible to prove that the
429 statement is not reachable. It is located in @file{tree-cfg.c} and
430 is described by @code{pass_warn_function_return}.
432 @item Mudflap statement annotation
434 If mudflap is enabled, we rewrite some memory accesses with code to
435 validate that the memory access is correct. In particular, expressions
436 involving pointer dereferences (@code{INDIRECT_REF}, @code{ARRAY_REF},
437 etc.) are replaced by code that checks the selected address range
438 against the mudflap runtime's database of valid regions. This check
439 includes an inline lookup into a direct-mapped cache, based on
440 shift/mask operations of the pointer value, with a fallback function
441 call into the runtime. The pass is located in @file{tree-mudflap.c} and
442 is described by @code{pass_mudflap_2}.
444 @item Leave static single assignment form
446 This pass rewrites the function such that it is in normal form. At
447 the same time, we eliminate as many single-use temporaries as possible,
448 so the intermediate language is no longer GIMPLE, but GENERIC. The
449 pass is located in @file{tree-ssa.c} and is described by @code{pass_del_ssa}.
455 The following briefly describes the rtl generation and optimization
456 passes that are run after tree optimization.
461 @c Avoiding overfull is tricky here.
462 The source files for RTL generation include
470 and @file{emit-rtl.c}.
472 @file{insn-emit.c}, generated from the machine description by the
473 program @code{genemit}, is used in this pass. The header file
474 @file{expr.h} is used for communication within this pass.
478 The header files @file{insn-flags.h} and @file{insn-codes.h},
479 generated from the machine description by the programs @code{genflags}
480 and @code{gencodes}, tell this pass which standard names are available
481 for use and which patterns correspond to them.
483 @item Generate exception handling landing pads
485 This pass generates the glue that handles communication between the
486 exception handling library routines and the exception handlers within
487 the function. Entry points in the function that are invoked by the
488 exception handling library are called @dfn{landing pads}. The code
489 for this pass is located within @file{except.c}.
491 @item Cleanup control flow graph
493 This pass removes unreachable code, simplifies jumps to next, jumps to
494 jump, jumps across jumps, etc. The pass is run multiple times.
495 For historical reasons, it is occasionally referred to as the ``jump
496 optimization pass''. The bulk of the code for this pass is in
497 @file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c}
500 @item Common subexpression elimination
502 This pass removes redundant computation within basic blocks, and
503 optimizes addressing modes based on cost. The pass is run twice.
504 The source is located in @file{cse.c}.
506 @item Global common subexpression elimination.
508 This pass performs two
509 different types of GCSE depending on whether you are optimizing for
510 size or not (LCM based GCSE tends to increase code size for a gain in
511 speed, while Morel-Renvoise based GCSE does not).
512 When optimizing for size, GCSE is done using Morel-Renvoise Partial
513 Redundancy Elimination, with the exception that it does not try to move
514 invariants out of loops---that is left to the loop optimization pass.
515 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
517 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
518 done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
519 based GCSE also does loop invariant code motion. We also perform load
520 and store motion when optimizing for speed.
521 Regardless of which type of GCSE is used, the GCSE pass also performs
522 global constant and copy propagation.
523 The source file for this pass is @file{gcse.c}, and the LCM routines
526 @item Loop optimization
528 This pass moves constant expressions out of loops,
529 and optionally does strength-reduction and loop unrolling as well.
530 Its source files are @file{loop.c} and @file{unroll.c}, plus the header
531 @file{loop.h} used for communication between them. Loop unrolling uses
532 some functions in @file{integrate.c} and the header @file{integrate.h}.
533 Loop dependency analysis routines are contained in @file{dependence.c}.
534 This pass is seriously out-of-date and is supposed to be replaced by
535 a new one described below in near future.
537 A second loop optimization pass takes care of basic block level
538 optimizations---unrolling, peeling and unswitching loops. The source
539 files are @file{cfgloopanal.c} and @file{cfgloopmanip.c} containing
540 generic loop analysis and manipulation code, @file{loop-init.c} with
541 initialization and finalization code, @file{loop-unswitch.c} for loop
542 unswitching and @file{loop-unroll.c} for loop unrolling and peeling.
543 It also contains a separate loop invariant motion pass implemented in
544 @file{loop-invariant.c}.
548 This pass is an aggressive form of GCSE that transforms the control
549 flow graph of a function by propagating constants into conditional
550 branch instructions. The source file for this pass is @file{gcse.c}.
554 This pass attempts to replace conditional branches and surrounding
555 assignments with arithmetic, boolean value producing comparison
556 instructions, and conditional move instructions. In the very last
557 invocation after reload, it will generate predicated instructions
558 when supported by the target. The pass is located in @file{ifcvt.c}.
560 @item Web construction
562 This pass splits independent uses of each pseudo-register. This can
563 improve effect of the other transformation, such as CSE or register
564 allocation. Its source files are @file{web.c}.
568 This pass computes which pseudo-registers are live at each point in
569 the program, and makes the first instruction that uses a value point
570 at the instruction that computed the value. It then deletes
571 computations whose results are never used, and combines memory
572 references with add or subtract instructions to make autoincrement or
573 autodecrement addressing. The pass is located in @file{flow.c}.
575 @item Instruction combination
577 This pass attempts to combine groups of two or three instructions that
578 are related by data flow into single instructions. It combines the
579 RTL expressions for the instructions by substitution, simplifies the
580 result using algebra, and then attempts to match the result against
581 the machine description. The pass is located in @file{combine.c}.
583 @item Register movement
585 This pass looks for cases where matching constraints would force an
586 instruction to need a reload, and this reload would be a
587 register-to-register move. It then attempts to change the registers
588 used by the instruction to avoid the move instruction.
589 The pass is located in @file{regmove.c}.
591 @item Optimize mode switching
593 This pass looks for instructions that require the processor to be in a
594 specific ``mode'' and minimizes the number of mode changes required to
595 satisfy all users. What these modes are, and what they apply to are
596 completely target-specific. The source is located in @file{lcm.c}.
598 @cindex modulo scheduling
599 @cindex sms, swing, software pipelining
600 @item Modulo scheduling
602 This pass looks at innermost loops and reorders their instructions
603 by overlapping different iterations. Modulo scheduling is performed
604 immediately before instruction scheduling.
605 The pass is located in (@file{modulo-sched.c}).
607 @item Instruction scheduling
609 This pass looks for instructions whose output will not be available by
610 the time that it is used in subsequent instructions. Memory loads and
611 floating point instructions often have this behavior on RISC machines.
612 It re-orders instructions within a basic block to try to separate the
613 definition and use of items that otherwise would cause pipeline
614 stalls. This pass is performed twice, before and after register
615 allocation. The pass is located in @file{haifa-sched.c},
616 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and
619 @item Register allocation
621 These passes make sure that all occurrences of pseudo registers are
622 eliminated, either by allocating them to a hard register, replacing
623 them by an equivalent expression (e.g.@: a constant) or by placing
624 them on the stack. This is done in several subpasses:
628 Register class preferencing. The RTL code is scanned to find out
629 which register class is best for each pseudo register. The source
630 file is @file{regclass.c}.
633 Local register allocation. This pass allocates hard registers to
634 pseudo registers that are used only within one basic block. Because
635 the basic block is linear, it can use fast and powerful techniques to
636 do a decent job. The source is located in @file{local-alloc.c}.
639 Global register allocation. This pass allocates hard registers for
640 the remaining pseudo registers (those whose life spans are not
641 contained in one basic block). The pass is located in @file{global.c}.
644 Graph coloring register allocator. The files @file{ra.c}, @file{ra-build.c},
645 @file{ra-colorize.c}, @file{ra-debug.c}, @file{ra-rewrite.c} together with
646 the header @file{ra.h} contain another register allocator, which is used
647 when the option @option{-fnew-ra} is given. In that case it is run instead
648 of the above mentioned local and global register allocation passes.
652 Reloading. This pass renumbers pseudo registers with the hardware
653 registers numbers they were allocated. Pseudo registers that did not
654 get hard registers are replaced with stack slots. Then it finds
655 instructions that are invalid because a value has failed to end up in
656 a register, or has ended up in a register of the wrong kind. It fixes
657 up these instructions by reloading the problematical values
658 temporarily into registers. Additional instructions are generated to
661 The reload pass also optionally eliminates the frame pointer and inserts
662 instructions to save and restore call-clobbered registers around calls.
664 Source files are @file{reload.c} and @file{reload1.c}, plus the header
665 @file{reload.h} used for communication between them.
668 @item Basic block reordering
670 This pass implements profile guided code positioning. If profile
671 information is not available, various types of static analysis are
672 performed to make the predictions normally coming from the profile
673 feedback (IE execution frequency, branch probability, etc). It is
674 implemented in the file @file{bb-reorder.c}, and the various
675 prediction routines are in @file{predict.c}.
677 @item Variable tracking
679 This pass computes where the variables are stored at each
680 position in code and generates notes describing the variable locations
681 to RTL code. The location lists are then generated according to these
682 notes to debug information if the debugging information format supports
685 @item Delayed branch scheduling
687 This optional pass attempts to find instructions that can go into the
688 delay slots of other instructions, usually jumps and calls. The
689 source file name is @file{reorg.c}.
691 @item Branch shortening
693 On many RISC machines, branch instructions have a limited range.
694 Thus, longer sequences of instructions must be used for long branches.
695 In this pass, the compiler figures out what how far each instruction
696 will be from each other instruction, and therefore whether the usual
697 instructions, or the longer sequences, must be used for each branch.
699 @item Register-to-stack conversion
701 Conversion from usage of some hard registers to usage of a register
702 stack may be done at this point. Currently, this is supported only
703 for the floating-point registers of the Intel 80387 coprocessor. The
704 source file name is @file{reg-stack.c}.
708 This pass outputs the assembler code for the function. The source files
709 are @file{final.c} plus @file{insn-output.c}; the latter is generated
710 automatically from the machine description by the tool @file{genoutput}.
711 The header file @file{conditions.h} is used for communication between
712 these files. If mudflap is enabled, the queue of deferred declarations
713 and any addressed constants (e.g., string literals) is processed by
714 @code{mudflap_finish_file} into a synthetic constructor function
715 containing calls into the mudflap runtime.
717 @item Debugging information output
719 This is run after final because it must output the stack slot offsets
720 for pseudo registers that did not get hard registers. Source files
721 are @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for
722 SDB symbol table format, @file{dwarfout.c} for DWARF symbol table
723 format, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2
724 symbol table format, and @file{vmsdbgout.c} for VMS debug symbol table