1 @c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
2 @c 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3 @c This is part of the GCC manual.
4 @c For copying conditions, see the file gcc.texi.
7 @chapter Passes and Files of the Compiler
8 @cindex passes and files of the compiler
9 @cindex files and passes of the compiler
10 @cindex compiler passes and files
12 @cindex top level of compiler
13 The overall control structure of the compiler is in @file{toplev.c}. This
14 file is responsible for initialization, decoding arguments, opening and
15 closing files, and sequencing the passes. Routines for emitting
16 diagnostic messages are defined in @file{diagnostic.c}. The files
17 @file{pretty-print.h} and @file{pretty-print.c} provide basic support
18 for language-independent pretty-printing.
21 The parsing pass is invoked only once, to parse the entire input. A
22 high level tree representation is then generated from the input,
23 one function at a time. This tree code is then transformed into RTL
24 intermediate code, and processed. The files involved in transforming
25 the trees into RTL are @file{expr.c}, @file{expmed.c}, and
27 @c Note, the above files aren't strictly the only files involved. It's
28 @c all over the place (function.c, final.c,etc). However, those are
29 @c the files that are supposed to be directly involved, and have
30 @c their purpose listed as such, so i've only listed them.
31 The order of trees that are processed, is not
32 necessarily the same order they are generated from
33 the input, due to deferred inlining, and other considerations.
35 @findex rest_of_compilation
36 @findex rest_of_decl_compilation
37 Each time the parsing pass reads a complete function definition or
38 top-level declaration, it calls either the function
39 @code{rest_of_compilation}, or the function
40 @code{rest_of_decl_compilation} in @file{toplev.c}, which are
41 responsible for all further processing necessary, ending with output of
42 the assembler language. All other compiler passes run, in sequence,
43 within @code{rest_of_compilation}. When that function returns from
44 compiling a function definition, the storage used for that function
45 definition's compilation is entirely freed, unless it is an inline
46 function, or was deferred for some reason (this can occur in
47 templates, for example).
48 (@pxref{Inline,,An Inline Function is As Fast As a Macro,gcc,Using the
49 GNU Compiler Collection (GCC)}).
51 Here is a list of all the passes of the compiler and their source files.
52 Also included is a description of where debugging dumps can be requested
53 with @option{-d} options.
57 Parsing. This pass reads the entire text of a function definition,
58 constructing a high level tree representation. (Because of the semantic
59 analysis that takes place during this pass, it does more than is
60 formally considered to be parsing.)
62 The tree representation does not entirely follow C syntax, because it is
63 intended to support other languages as well.
65 Language-specific data type analysis is also done in this pass, and every
66 tree node that represents an expression has a data type attached.
67 Variables are represented as declaration nodes.
69 The language-independent source files for parsing are
70 @file{tree.c}, @file{fold-const.c}, and @file{stor-layout.c}.
71 There are also header files @file{tree.h} and @file{tree.def}
72 which define the format of the tree representation.
74 C preprocessing, for language front ends, that want or require it, is
75 performed by cpplib, which is covered in separate documentation. In
76 particular, the internals are covered in @xref{Top, ,Cpplib internals,
77 cppinternals, Cpplib Internals}.
79 The source files to parse C are found in the toplevel directory, and
80 by convention are named @file{c-*}. Some of these are also used by
81 the other C-like languages: @file{c-common.c},
90 @file{c-cppbuiltin.c},
98 Files specific to each language are in subdirectories named after the
99 language in question, like @file{ada}, @file{objc}, @file{cp} (for C++).
101 @cindex Tree optimization
103 Tree optimization. This is the optimization of the tree
104 representation, before converting into RTL code.
106 @cindex inline on trees, automatic
107 Currently, the main optimization performed here is tree-based
109 This is implemented in @file{tree-inline.c} and used by both C and C++.
110 Note that tree based inlining turns off rtx based inlining (since it's more
111 powerful, it would be a waste of time to do rtx based inlining in
114 @cindex constant folding
115 @cindex arithmetic simplifications
116 @cindex simplifications, arithmetic
117 Constant folding and some arithmetic simplifications are also done
118 during this pass, on the tree representation.
119 The routines that perform these tasks are located in @file{fold-const.c}.
121 @cindex RTL generation
123 RTL generation. This is the conversion of syntax tree into RTL code.
125 @cindex target-parameter-dependent code
126 This is where the bulk of target-parameter-dependent code is found,
127 since often it is necessary for strategies to apply only when certain
128 standard kinds of instructions are available. The purpose of named
129 instruction patterns is to provide this information to the RTL
132 @cindex tail recursion optimization
133 Optimization is done in this pass for @code{if}-conditions that are
134 comparisons, boolean operations or conditional expressions. Tail
135 recursion is detected at this time also. Decisions are made about how
136 best to arrange loops and how to output @code{switch} statements.
138 @c Avoiding overfull is tricky here.
139 The source files for RTL generation include
147 and @file{emit-rtl.c}.
149 @file{insn-emit.c}, generated from the machine description by the
150 program @code{genemit}, is used in this pass. The header file
151 @file{expr.h} is used for communication within this pass.
155 The header files @file{insn-flags.h} and @file{insn-codes.h},
156 generated from the machine description by the programs @code{genflags}
157 and @code{gencodes}, tell this pass which standard names are available
158 for use and which patterns correspond to them.
160 Aside from debugging information output, none of the following passes
161 refers to the tree structure representation of the function (only
162 part of which is saved).
164 @cindex inline on rtx, automatic
165 The decision of whether the function can and should be expanded inline
166 in its subsequent callers is made at the end of rtl generation. The
167 function must meet certain criteria, currently related to the size of
168 the function and the types and number of parameters it has. Note that
169 this function may contain loops, recursive calls to itself
170 (tail-recursive functions can be inlined!), gotos, in short, all
171 constructs supported by GCC@. The file @file{integrate.c} contains
172 the code to save a function's rtl for later inlining and to inline that
173 rtl when the function is called. The header file @file{integrate.h}
174 is also used for this purpose.
177 The option @option{-dr} causes a debugging dump of the RTL code after
178 this pass. This dump file's name is made by appending @samp{.rtl} to
181 @c Should the exception handling pass be talked about here?
183 @cindex sibling call optimization
185 Sibling call optimization. This pass performs tail recursion
186 elimination, and tail and sibling call optimizations. The purpose of
187 these optimizations is to reduce the overhead of function calls,
190 The source file of this pass is @file{sibcall.c}
193 The option @option{-di} causes a debugging dump of the RTL code after
194 this pass is run. This dump file's name is made by appending
195 @samp{.sibling} to the input file name.
197 @cindex jump optimization
198 @cindex unreachable code
201 Jump optimization. This pass simplifies jumps to the following
202 instruction, jumps across jumps, and jumps to jumps. It deletes
203 unreferenced labels and unreachable code, except that unreachable code
204 that contains a loop is not recognized as unreachable in this pass.
205 (Such loops are deleted later in the basic block analysis.) It also
206 converts some code originally written with jumps into sequences of
207 instructions that directly set values from the results of comparisons,
208 if the machine has such instructions.
210 Jump optimization is performed two or three times. The first time is
211 immediately following RTL generation. The second time is after CSE,
212 but only if CSE says repeated jump optimization is needed. The
213 last time is right before the final pass. That time, cross-jumping
214 and deletion of no-op move instructions are done together with the
215 optimizations described above.
217 The source file of this pass is @file{jump.c}.
220 The option @option{-dj} causes a debugging dump of the RTL code after
221 this pass is run for the first time. This dump file's name is made by
222 appending @samp{.jump} to the input file name.
225 @cindex register use analysis
227 Register scan. This pass finds the first and last use of each
228 register, as a guide for common subexpression elimination. Its source
229 is in @file{regclass.c}.
231 @cindex jump threading
233 @opindex fthread-jumps
234 Jump threading. This pass detects a condition jump that branches to an
235 identical or inverse test. Such jumps can be @samp{threaded} through
236 the second conditional test. The source code for this pass is in
237 @file{jump.c}. This optimization is only performed if
238 @option{-fthread-jumps} is enabled.
240 @cindex SSA optimizations
241 @cindex Single Static Assignment optimizations
244 Static Single Assignment (SSA) based optimization passes. The
245 SSA conversion passes (to/from) are turned on by the @option{-fssa}
246 option (it is also done automatically if you enable an SSA optimization pass).
247 These passes utilize a form called Static Single Assignment. In SSA form,
248 each variable (pseudo register) is only set once, giving you def-use
249 and use-def chains for free, and enabling a lot more optimization
250 passes to be run in linear time.
251 Conversion to and from SSA form is handled by functions in
255 The option @option{-de} causes a debugging dump of the RTL code after
256 this pass. This dump file's name is made by appending @samp{.ssa} to
259 @cindex SSA Conditional Constant Propagation
260 @cindex Conditional Constant Propagation, SSA based
261 @cindex conditional constant propagation
264 SSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp}
265 option. This pass performs conditional constant propagation to simplify
266 instructions including conditional branches. This pass is more aggressive
267 than the constant propagation done by the CSE and GCSE passes, but operates
271 The option @option{-dW} causes a debugging dump of the RTL code after
272 this pass. This dump file's name is made by appending @samp{.ssaccp} to
276 @cindex DCE, SSA based
277 @cindex dead code elimination
280 SSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce}
281 option. This pass performs elimination of code considered unnecessary because
282 it has no externally visible effects on the program. It operates in
286 The option @option{-dX} causes a debugging dump of the RTL code after
287 this pass. This dump file's name is made by appending @samp{.ssadce} to
291 @cindex common subexpression elimination
292 @cindex constant propagation
294 Common subexpression elimination. This pass also does constant
295 propagation. Its source files are @file{cse.c}, and @file{cselib.c}.
296 If constant propagation causes conditional jumps to become
297 unconditional or to become no-ops, jump optimization is run again when
301 The option @option{-ds} causes a debugging dump of the RTL code after
302 this pass. This dump file's name is made by appending @samp{.cse} to
305 @cindex global common subexpression elimination
306 @cindex constant propagation
307 @cindex copy propagation
309 Global common subexpression elimination. This pass performs two
310 different types of GCSE depending on whether you are optimizing for
311 size or not (LCM based GCSE tends to increase code size for a gain in
312 speed, while Morel-Renvoise based GCSE does not).
313 When optimizing for size, GCSE is done using Morel-Renvoise Partial
314 Redundancy Elimination, with the exception that it does not try to move
315 invariants out of loops---that is left to the loop optimization pass.
316 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
318 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
319 done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
320 based GCSE also does loop invariant code motion. We also perform load
321 and store motion when optimizing for speed.
322 Regardless of which type of GCSE is used, the GCSE pass also performs
323 global constant and copy propagation.
325 The source file for this pass is @file{gcse.c}, and the LCM routines
329 The option @option{-dG} causes a debugging dump of the RTL code after
330 this pass. This dump file's name is made by appending @samp{.gcse} to
333 @cindex loop optimization
335 @cindex strength-reduction
337 Loop optimization. This pass moves constant expressions out of loops,
338 and optionally does strength-reduction and loop unrolling as well.
339 Its source files are @file{loop.c} and @file{unroll.c}, plus the header
340 @file{loop.h} used for communication between them. Loop unrolling uses
341 some functions in @file{integrate.c} and the header @file{integrate.h}.
342 Loop dependency analysis routines are contained in @file{dependence.c}.
344 Second loop optimization pass takes care of basic block level optimizations --
345 unrolling, peeling and unswitching loops. The source files are
346 @file{cfgloopanal.c} and @file{cfgloopmanip.c} containing generic loop
347 analysis and manipulation code, @file{loop-init.c} with initialization and
348 finalization code, @file{loop-unswitch.c} for loop unswitching and
349 @file{loop-unroll.c} for loop unrolling and peeling.
352 The option @option{-dL} causes a debugging dump of the RTL code after
353 these passes. The dump file names are made by appending @samp{.loop} and
354 @samp{.loop2} to the input file name.
356 @cindex jump bypassing
358 Jump bypassing. This pass is an aggressive form of GCSE that transforms
359 the control flow graph of a function by propagating constants into
360 conditional branch instructions.
362 The source file for this pass is @file{gcse.c}.
365 The option @option{-dG} causes a debugging dump of the RTL code after
366 this pass. This dump file's name is made by appending @samp{.bypass}
367 to the input file name.
369 @cindex web construction
371 Simple optimization pass that splits independent uses of each pseudo
372 increasing effect of other optimizations. This can improve effect of the
373 other transformation, such as CSE or register allocation.
374 Its source files are @file{web.c}.
377 The option @option{-dZ} causes a debugging dump of the RTL code after
378 this pass. This dump file's name is made by appending @samp{.web} to
382 @opindex frerun-cse-after-loop
383 If @option{-frerun-cse-after-loop} was enabled, a second common
384 subexpression elimination pass is performed after the loop optimization
385 pass. Jump threading is also done again at this time if it was specified.
388 The option @option{-dt} causes a debugging dump of the RTL code after
389 this pass. This dump file's name is made by appending @samp{.cse2} to
392 @cindex data flow analysis
393 @cindex analysis, data flow
396 Data flow analysis (@file{flow.c}). This pass divides the program
397 into basic blocks (and in the process deletes unreachable loops); then
398 it computes which pseudo-registers are live at each point in the
399 program, and makes the first instruction that uses a value point at
400 the instruction that computed the value.
402 @cindex autoincrement/decrement analysis
403 This pass also deletes computations whose results are never used, and
404 combines memory references with add or subtract instructions to make
405 autoincrement or autodecrement addressing.
408 The option @option{-df} causes a debugging dump of the RTL code after
409 this pass. This dump file's name is made by appending @samp{.flow} to
410 the input file name. If stupid register allocation is in use, this
411 dump file reflects the full results of such allocation.
413 @cindex instruction combination
415 Instruction combination (@file{combine.c}). This pass attempts to
416 combine groups of two or three instructions that are related by data
417 flow into single instructions. It combines the RTL expressions for
418 the instructions by substitution, simplifies the result using algebra,
419 and then attempts to match the result against the machine description.
422 The option @option{-dc} causes a debugging dump of the RTL code after
423 this pass. This dump file's name is made by appending @samp{.combine}
424 to the input file name.
426 @cindex if conversion
428 If-conversion is a transformation that transforms control dependencies
429 into data dependencies (IE it transforms conditional code into a
430 single control stream).
431 It is implemented in the file @file{ifcvt.c}.
434 The option @option{-dE} causes a debugging dump of the RTL code after
435 this pass. This dump file's name is made by appending @samp{.ce} to
438 @cindex register movement
440 Register movement (@file{regmove.c}). This pass looks for cases where
441 matching constraints would force an instruction to need a reload, and
442 this reload would be a register-to-register move. It then attempts
443 to change the registers used by the instruction to avoid the move
447 The option @option{-dN} causes a debugging dump of the RTL code after
448 this pass. This dump file's name is made by appending @samp{.regmove}
449 to the input file name.
451 @cindex instruction scheduling
452 @cindex scheduling, instruction
454 Instruction scheduling (@file{sched.c}). This pass looks for
455 instructions whose output will not be available by the time that it is
456 used in subsequent instructions. (Memory loads and floating point
457 instructions often have this behavior on RISC machines). It re-orders
458 instructions within a basic block to try to separate the definition and
459 use of items that otherwise would cause pipeline stalls.
461 Instruction scheduling is performed twice. The first time is immediately
462 after instruction combination and the second is immediately after reload.
465 The option @option{-dS} causes a debugging dump of the RTL code after this
466 pass is run for the first time. The dump file's name is made by
467 appending @samp{.sched} to the input file name.
469 @cindex register allocation
471 Register allocation. These passes make sure that all occurrences of pseudo
472 registers are eliminated, either by allocating them to a hard register,
473 replacing them by an equivalent expression (e.g.@: a constant) or by placing
474 them on the stack. This is done in several subpasses:
477 @cindex register class preference pass
479 Register class preferencing. The RTL code is scanned to find out
480 which register class is best for each pseudo register. The source
481 file is @file{regclass.c}.
483 @cindex local register allocation
485 Local register allocation (@file{local-alloc.c}). This pass allocates
486 hard registers to pseudo registers that are used only within one basic
487 block. Because the basic block is linear, it can use fast and
488 powerful techniques to do a very good job.
491 The option @option{-dl} causes a debugging dump of the RTL code after
492 this pass. This dump file's name is made by appending @samp{.lreg} to
495 @cindex global register allocation
497 Global register allocation (@file{global.c}). This pass
498 allocates hard registers for the remaining pseudo registers (those
499 whose life spans are not contained in one basic block).
501 @cindex graph coloring register allocation
505 Graph coloring register allocator. The files @file{ra.c}, @file{ra-build.c},
506 @file{ra-colorize.c}, @file{ra-debug.c}, @file{ra-rewrite.c} together with
507 the header @file{ra.h} contain another register allocator, which is used
508 when the option @option{-fnew-ra} is given. In that case it is run instead
509 of the above mentioned local and global register allocation passes, and the
510 option @option{-dl} causes a debugging dump of its work.
514 Reloading. This pass renumbers pseudo registers with the hardware
515 registers numbers they were allocated. Pseudo registers that did not
516 get hard registers are replaced with stack slots. Then it finds
517 instructions that are invalid because a value has failed to end up in
518 a register, or has ended up in a register of the wrong kind. It fixes
519 up these instructions by reloading the problematical values
520 temporarily into registers. Additional instructions are generated to
523 The reload pass also optionally eliminates the frame pointer and inserts
524 instructions to save and restore call-clobbered registers around calls.
526 Source files are @file{reload.c} and @file{reload1.c}, plus the header
527 @file{reload.h} used for communication between them.
530 The option @option{-dg} causes a debugging dump of the RTL code after
531 this pass. This dump file's name is made by appending @samp{.greg} to
535 @cindex instruction scheduling
536 @cindex scheduling, instruction
538 Instruction scheduling is repeated here to try to avoid pipeline stalls
539 due to memory loads generated for spilled pseudo registers.
542 The option @option{-dR} causes a debugging dump of the RTL code after
543 this pass. This dump file's name is made by appending @samp{.sched2}
544 to the input file name.
546 @cindex basic block reordering
547 @cindex reordering, block
549 Basic block reordering. This pass implements profile guided code
550 positioning. If profile information is not available, various types of
551 static analysis are performed to make the predictions normally coming
552 from the profile feedback (IE execution frequency, branch probability,
553 etc). It is implemented in the file @file{bb-reorder.c}, and the
554 various prediction routines are in @file{predict.c}.
557 The option @option{-dB} causes a debugging dump of the RTL code after
558 this pass. This dump file's name is made by appending @samp{.bbro} to
561 @cindex delayed branch scheduling
562 @cindex scheduling, delayed branch
564 Delayed branch scheduling. This optional pass attempts to find
565 instructions that can go into the delay slots of other instructions,
566 usually jumps and calls. The source file name is @file{reorg.c}.
569 The option @option{-dd} causes a debugging dump of the RTL code after
570 this pass. This dump file's name is made by appending @samp{.dbr}
571 to the input file name.
573 @cindex branch shortening
575 Branch shortening. On many RISC machines, branch instructions have a
576 limited range. Thus, longer sequences of instructions must be used for
577 long branches. In this pass, the compiler figures out what how far each
578 instruction will be from each other instruction, and therefore whether
579 the usual instructions, or the longer sequences, must be used for each
582 @cindex register-to-stack conversion
584 Conversion from usage of some hard registers to usage of a register
585 stack may be done at this point. Currently, this is supported only
586 for the floating-point registers of the Intel 80387 coprocessor. The
587 source file name is @file{reg-stack.c}.
590 The options @option{-dk} causes a debugging dump of the RTL code after
591 this pass. This dump file's name is made by appending @samp{.stack}
592 to the input file name.
595 @cindex peephole optimization
597 Final. This pass outputs the assembler code for the function. It is
598 also responsible for identifying spurious test and compare
599 instructions. Machine-specific peephole optimizations are performed
600 at the same time. The function entry and exit sequences are generated
601 directly as assembler code in this pass; they never exist as RTL@.
603 The source files are @file{final.c} plus @file{insn-output.c}; the
604 latter is generated automatically from the machine description by the
605 tool @file{genoutput}. The header file @file{conditions.h} is used
606 for communication between these files.
608 @cindex debugging information generation
610 Debugging information output. This is run after final because it must
611 output the stack slot offsets for pseudo registers that did not get
612 hard registers. Source files are @file{dbxout.c} for DBX symbol table
613 format, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c}
614 for DWARF symbol table format, files @file{dwarf2out.c} and
615 @file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c}
616 for VMS debug symbol table format.
619 Some additional files are used by all or many passes:
623 Every pass uses @file{machmode.def} and @file{machmode.h} which define
627 Several passes use @file{real.h}, which defines the default
628 representation of floating point constants and how to operate on them.
631 All the passes that work with RTL use the header files @file{rtl.h}
632 and @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools
633 @code{gen*} also use these files to read and work with the machine
637 All the tools that read the machine description use support routines
638 found in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}.
642 Several passes refer to the header file @file{insn-config.h} which
643 contains a few parameters (C macro definitions) generated
644 automatically from the machine description RTL by the tool
647 @cindex instruction recognizer
649 Several passes use the instruction recognizer, which consists of
650 @file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c}
651 and @file{insn-extract.c} that are generated automatically from the
652 machine description by the tools @file{genrecog} and
656 Several passes use the header files @file{regs.h} which defines the
657 information recorded about pseudo register usage, and @file{basic-block.h}
658 which defines the information recorded about basic blocks.
661 @file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector
662 with a bit for each hard register, and some macros to manipulate it.
663 This type is just @code{int} if the machine has few enough hard registers;
664 otherwise it is an array of @code{int} and some of the macros expand
668 Several passes use instruction attributes. A definition of the
669 attributes defined for a particular machine is in file
670 @file{insn-attr.h}, which is generated from the machine description by
671 the program @file{genattr}. The file @file{insn-attrtab.c} contains
672 subroutines to obtain the attribute values for insns and information
673 about processor pipeline characteristics for the instruction
674 scheduler. It is generated from the machine description by the
675 program @file{genattrtab}.