1 @c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
2 @c 1999, 2000, 2001 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.
18 The parsing pass is invoked only once, to parse the entire input. A
19 high level tree representation is then generated from the input,
20 one function at a time. This tree code is then transformed into RTL
21 intermediate code, and processed. The files involved in transforming
22 the trees into RTL are @file{expr.c}, @file{expmed.c}, and
24 @c Note, the above files aren't strictly the only files involved. It's
25 @c all over the place (function.c, final.c,etc). However, those are
26 @c the files that are supposed to be directly involved, and have
27 @c their purpose listed as such, so i've only listed them.
28 The order of trees that are processed, is not
29 necessarily the same order they are generated from
30 the input, due to deferred inlining, and other considerations.
32 @findex rest_of_compilation
33 @findex rest_of_decl_compilation
34 Each time the parsing pass reads a complete function definition or
35 top-level declaration, it calls either the function
36 @code{rest_of_compilation}, or the function
37 @code{rest_of_decl_compilation} in @file{toplev.c}, which are
38 responsible for all further processing necessary, ending with output of
39 the assembler language. All other compiler passes run, in sequence,
40 within @code{rest_of_compilation}. When that function returns from
41 compiling a function definition, the storage used for that function
42 definition's compilation is entirely freed, unless it is an inline
43 function, or was deferred for some reason (this can occur in
44 templates, for example).
45 (@pxref{Inline,,An Inline Function is As Fast As a Macro,gcc,Using the
46 GNU Compiler Collection (GCC)}).
48 Here is a list of all the passes of the compiler and their source files.
49 Also included is a description of where debugging dumps can be requested
50 with @option{-d} options.
54 Parsing. This pass reads the entire text of a function definition,
55 constructing a high level tree representation. (Because of the semantic
56 analysis that takes place during this pass, it does more than is
57 formally considered to be parsing.)
59 The tree representation does not entirely follow C syntax, because it is
60 intended to support other languages as well.
62 Language-specific data type analysis is also done in this pass, and every
63 tree node that represents an expression has a data type attached.
64 Variables are represented as declaration nodes.
66 The language-independent source files for parsing are
67 @file{tree.c}, @file{fold-const.c}, and @file{stor-layout.c}.
68 There are also header files @file{tree.h} and @file{tree.def}
69 which define the format of the tree representation.
71 C preprocessing, for language front ends, that want or require it, is
72 performed by cpplib, which is covered in separate documentation. In
73 particular, the internals are covered in @xref{Top, ,Cpplib internals,
74 cppinternals, Cpplib Internals}.
76 @c Avoiding overfull is tricky here.
77 The source files to parse C are
82 @file{c-objc-common.c},
87 along with a header file
89 and some files shared with Objective-C and C++.
91 The source files for parsing C++ are in @file{cp/}.
92 They are @file{parse.y},
94 @file{cvt.c}, @file{decl.c}, @file{decl2.c},
96 @file{expr.c}, @file{init.c}, @file{lex.c},
97 @file{method.c}, @file{ptree.c},
98 @file{search.c}, @file{spew.c},
99 @file{semantics.c}, @file{tree.c},
100 @file{typeck2.c}, and
101 @file{typeck.c}, along with header files @file{cp-tree.def},
102 @file{cp-tree.h}, and @file{decl.h}.
104 The special source files for parsing Objective-C are in @file{objc/}.
105 They are @file{objc-act.c}, @file{objc-tree.def}, and @file{objc-act.h}.
106 Certain C-specific files are used for this as well.
114 @file{c-semantics.c},
117 along with header files
122 are also used for all of the above languages.
125 @cindex Tree optimization
127 Tree optimization. This is the optimization of the tree
128 representation, before converting into RTL code.
130 @cindex inline on trees, automatic
131 Currently, the main optimization performed here is tree-based
133 This is implemented in @file{tree-inline.c} and used by both C and C++.
134 Note that tree based inlining turns off rtx based inlining (since it's more
135 powerful, it would be a waste of time to do rtx based inlining in
138 @cindex constant folding
139 @cindex arithmetic simplifications
140 @cindex simplifications, arithmetic
141 Constant folding and some arithmetic simplifications are also done
142 during this pass, on the tree representation.
143 The routines that perform these tasks are located in @file{fold-const.c}.
145 @cindex RTL generation
147 RTL generation. This is the conversion of syntax tree into RTL code.
149 @cindex target-parameter-dependent code
150 This is where the bulk of target-parameter-dependent code is found,
151 since often it is necessary for strategies to apply only when certain
152 standard kinds of instructions are available. The purpose of named
153 instruction patterns is to provide this information to the RTL
156 @cindex tail recursion optimization
157 Optimization is done in this pass for @code{if}-conditions that are
158 comparisons, boolean operations or conditional expressions. Tail
159 recursion is detected at this time also. Decisions are made about how
160 best to arrange loops and how to output @code{switch} statements.
162 @c Avoiding overfull is tricky here.
163 The source files for RTL generation include
171 and @file{emit-rtl.c}.
173 @file{insn-emit.c}, generated from the machine description by the
174 program @code{genemit}, is used in this pass. The header file
175 @file{expr.h} is used for communication within this pass.
179 The header files @file{insn-flags.h} and @file{insn-codes.h},
180 generated from the machine description by the programs @code{genflags}
181 and @code{gencodes}, tell this pass which standard names are available
182 for use and which patterns correspond to them.
184 Aside from debugging information output, none of the following passes
185 refers to the tree structure representation of the function (only
186 part of which is saved).
188 @cindex inline on rtx, automatic
189 The decision of whether the function can and should be expanded inline
190 in its subsequent callers is made at the end of rtl generation. The
191 function must meet certain criteria, currently related to the size of
192 the function and the types and number of parameters it has. Note that
193 this function may contain loops, recursive calls to itself
194 (tail-recursive functions can be inlined!), gotos, in short, all
195 constructs supported by GCC@. The file @file{integrate.c} contains
196 the code to save a function's rtl for later inlining and to inline that
197 rtl when the function is called. The header file @file{integrate.h}
198 is also used for this purpose.
201 The option @option{-dr} causes a debugging dump of the RTL code after
202 this pass. This dump file's name is made by appending @samp{.rtl} to
205 @c Should the exception handling pass be talked about here?
207 @cindex sibling call optimization
209 Sibiling call optimization. This pass performs tail recursion
210 elimination, and tail and sibling call optimizations. The purpose of
211 these optimizations is to reduce the overhead of function calls,
214 The source file of this pass is @file{sibcall.c}
217 The option @option{-di} causes a debugging dump of the RTL code after
218 this pass is run. This dump file's name is made by appending
219 @samp{.sibling} to the input file name.
221 @cindex jump optimization
222 @cindex unreachable code
225 Jump optimization. This pass simplifies jumps to the following
226 instruction, jumps across jumps, and jumps to jumps. It deletes
227 unreferenced labels and unreachable code, except that unreachable code
228 that contains a loop is not recognized as unreachable in this pass.
229 (Such loops are deleted later in the basic block analysis.) It also
230 converts some code originally written with jumps into sequences of
231 instructions that directly set values from the results of comparisons,
232 if the machine has such instructions.
234 Jump optimization is performed two or three times. The first time is
235 immediately following RTL generation. The second time is after CSE,
236 but only if CSE says repeated jump optimization is needed. The
237 last time is right before the final pass. That time, cross-jumping
238 and deletion of no-op move instructions are done together with the
239 optimizations described above.
241 The source file of this pass is @file{jump.c}.
244 The option @option{-dj} causes a debugging dump of the RTL code after
245 this pass is run for the first time. This dump file's name is made by
246 appending @samp{.jump} to the input file name.
249 @cindex register use analysis
251 Register scan. This pass finds the first and last use of each
252 register, as a guide for common subexpression elimination. Its source
253 is in @file{regclass.c}.
255 @cindex jump threading
257 @opindex fthread-jumps
258 Jump threading. This pass detects a condition jump that branches to an
259 identical or inverse test. Such jumps can be @samp{threaded} through
260 the second conditional test. The source code for this pass is in
261 @file{jump.c}. This optimization is only performed if
262 @option{-fthread-jumps} is enabled.
264 @cindex SSA optimizations
265 @cindex Single Static Assignment optimizations
268 Static Single Assignment (SSA) based optimization passes. The
269 SSA conversion passes (to/from) are turned on by the @option{-fssa}
270 option (it is also done automatically if you enable an SSA optimization pass).
271 These passes utilize a form called Static Single Assignment. In SSA form,
272 each variable (pseudo register) is only set once, giving you def-use
273 and use-def chains for free, and enabling a lot more optimization
274 passes to be run in linear time.
275 Conversion to and from SSA form is handled by functions in
279 The option @option{-de} causes a debugging dump of the RTL code after
280 this pass. This dump file's name is made by appending @samp{.ssa} to
283 @cindex SSA Conditional Constant Propagation
284 @cindex Conditional Constant Propagation, SSA based
285 @cindex conditional constant propagation
288 SSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp}
289 option. This pass performs conditional constant propagation to simplify
290 instructions including conditional branches. This pass is more aggressive
291 than the constant propagation done by the CSE and GCSE pases, but operates
295 The option @option{-dW} causes a debugging dump of the RTL code after
296 this pass. This dump file's name is made by appending @samp{.ssaccp} to
300 @cindex DCE, SSA based
301 @cindex dead code elimination
304 SSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce}
305 option. This pass performs elimination of code considered unnecessary because
306 it has no externally visible effects on the program. It operates in
310 The option @option{-dX} causes a debugging dump of the RTL code after
311 this pass. This dump file's name is made by appending @samp{.ssadce} to
315 @cindex common subexpression elimination
316 @cindex constant propagation
318 Common subexpression elimination. This pass also does constant
319 propagation. Its source files are @file{cse.c}, and @file{cselib.c}.
320 If constant propagation causes conditional jumps to become
321 unconditional or to become no-ops, jump optimization is run again when
325 The option @option{-ds} causes a debugging dump of the RTL code after
326 this pass. This dump file's name is made by appending @samp{.cse} to
329 @cindex global common subexpression elimination
330 @cindex constant propagation
331 @cindex copy propagation
333 Global common subexpression elimination. This pass performs two
334 different types of GCSE depending on whether you are optimizing for
335 size or not (LCM based GCSE tends to increase code size for a gain in
336 speed, while Morel-Renvoise based GCSE does not).
337 When optimizing for size, GCSE is done using Morel-Renvoise Partial
338 Redundancy Elimination, with the exception that it does not try to move
339 invariants out of loops---that is left to the loop optimization pass.
340 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
342 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
343 done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
344 based GCSE also does loop invariant code motion. We also perform load
345 and store motion when optimizing for speed.
346 Regardless of which type of GCSE is used, the GCSE pass also performs
347 global constant and copy propagation.
349 The source file for this pass is @file{gcse.c}, and the LCM routines
353 The option @option{-dG} causes a debugging dump of the RTL code after
354 this pass. This dump file's name is made by appending @samp{.gcse} to
357 @cindex loop optimization
359 @cindex strength-reduction
361 Loop optimization. This pass moves constant expressions out of loops,
362 and optionally does strength-reduction and loop unrolling as well.
363 Its source files are @file{loop.c} and @file{unroll.c}, plus the header
364 @file{loop.h} used for communication between them. Loop unrolling uses
365 some functions in @file{integrate.c} and the header @file{integrate.h}.
366 Loop dependency analysis routines are contained in @file{dependence.c}.
369 The option @option{-dL} causes a debugging dump of the RTL code after
370 this pass. This dump file's name is made by appending @samp{.loop} to
374 @opindex frerun-cse-after-loop
375 If @option{-frerun-cse-after-loop} was enabled, a second common
376 subexpression elimination pass is performed after the loop optimization
377 pass. Jump threading is also done again at this time if it was specified.
380 The option @option{-dt} causes a debugging dump of the RTL code after
381 this pass. This dump file's name is made by appending @samp{.cse2} to
384 @cindex data flow analysis
385 @cindex analysis, data flow
388 Data flow analysis (@file{flow.c}). This pass divides the program
389 into basic blocks (and in the process deletes unreachable loops); then
390 it computes which pseudo-registers are live at each point in the
391 program, and makes the first instruction that uses a value point at
392 the instruction that computed the value.
394 @cindex autoincrement/decrement analysis
395 This pass also deletes computations whose results are never used, and
396 combines memory references with add or subtract instructions to make
397 autoincrement or autodecrement addressing.
400 The option @option{-df} causes a debugging dump of the RTL code after
401 this pass. This dump file's name is made by appending @samp{.flow} to
402 the input file name. If stupid register allocation is in use, this
403 dump file reflects the full results of such allocation.
405 @cindex instruction combination
407 Instruction combination (@file{combine.c}). This pass attempts to
408 combine groups of two or three instructions that are related by data
409 flow into single instructions. It combines the RTL expressions for
410 the instructions by substitution, simplifies the result using algebra,
411 and then attempts to match the result against the machine description.
414 The option @option{-dc} causes a debugging dump of the RTL code after
415 this pass. This dump file's name is made by appending @samp{.combine}
416 to the input file name.
418 @cindex if conversion
420 If-conversion is a transformation that transforms control dependencies
421 into data dependencies (IE it transforms conditional code into a
422 single control stream).
423 It is implemented in the file @file{ifcvt.c}.
426 The option @option{-dE} causes a debugging dump of the RTL code after
427 this pass. This dump file's name is made by appending @samp{.ce} to
430 @cindex register movement
432 Register movement (@file{regmove.c}). This pass looks for cases where
433 matching constraints would force an instruction to need a reload, and
434 this reload would be a register-to-register move. It then attempts
435 to change the registers used by the instruction to avoid the move
439 The option @option{-dN} causes a debugging dump of the RTL code after
440 this pass. This dump file's name is made by appending @samp{.regmove}
441 to the input file name.
443 @cindex instruction scheduling
444 @cindex scheduling, instruction
446 Instruction scheduling (@file{sched.c}). This pass looks for
447 instructions whose output will not be available by the time that it is
448 used in subsequent instructions. (Memory loads and floating point
449 instructions often have this behavior on RISC machines). It re-orders
450 instructions within a basic block to try to separate the definition and
451 use of items that otherwise would cause pipeline stalls.
453 Instruction scheduling is performed twice. The first time is immediately
454 after instruction combination and the second is immediately after reload.
457 The option @option{-dS} causes a debugging dump of the RTL code after this
458 pass is run for the first time. The dump file's name is made by
459 appending @samp{.sched} to the input file name.
461 @cindex register allocation
463 Register allocation. These passes make sure that all occurences of pseudo
464 registers are eliminated, either by allocating them to a hard register,
465 replacing them by an equivalent expression (e.g.@: a constant) or by placing
466 them on the stack. This is done in several subpasses:
469 @cindex register class preference pass
471 Register class preferencing. The RTL code is scanned to find out
472 which register class is best for each pseudo register. The source
473 file is @file{regclass.c}.
475 @cindex local register allocation
477 Local register allocation (@file{local-alloc.c}). This pass allocates
478 hard registers to pseudo registers that are used only within one basic
479 block. Because the basic block is linear, it can use fast and
480 powerful techniques to do a very good job.
483 The option @option{-dl} causes a debugging dump of the RTL code after
484 this pass. This dump file's name is made by appending @samp{.lreg} to
487 @cindex global register allocation
489 Global register allocation (@file{global.c}). This pass
490 allocates hard registers for the remaining pseudo registers (those
491 whose life spans are not contained in one basic block).
493 @cindex graph coloring register allocation
497 Graph coloring register allocator. The files @file{ra.c}, @file{ra-build.c},
498 @file{ra-colorize.c}, @file{ra-debug.c}, @file{ra-rewrite.c} together with
499 the header @file{ra.h} contain another register allocator, which is used
500 when the option @option{-fnew-ra} is given. In that case it is run instead
501 of the above mentioned local and global register allocation passes, and the
502 option @option{-dl} causes a debugging dump of its work.
506 Reloading. This pass renumbers pseudo registers with the hardware
507 registers numbers they were allocated. Pseudo registers that did not
508 get hard registers are replaced with stack slots. Then it finds
509 instructions that are invalid because a value has failed to end up in
510 a register, or has ended up in a register of the wrong kind. It fixes
511 up these instructions by reloading the problematical values
512 temporarily into registers. Additional instructions are generated to
515 The reload pass also optionally eliminates the frame pointer and inserts
516 instructions to save and restore call-clobbered registers around calls.
518 Source files are @file{reload.c} and @file{reload1.c}, plus the header
519 @file{reload.h} used for communication between them.
522 The option @option{-dg} causes a debugging dump of the RTL code after
523 this pass. This dump file's name is made by appending @samp{.greg} to
527 @cindex instruction scheduling
528 @cindex scheduling, instruction
530 Instruction scheduling is repeated here to try to avoid pipeline stalls
531 due to memory loads generated for spilled pseudo registers.
534 The option @option{-dR} causes a debugging dump of the RTL code after
535 this pass. This dump file's name is made by appending @samp{.sched2}
536 to the input file name.
538 @cindex basic block reordering
539 @cindex reordering, block
541 Basic block reordering. This pass implements profile guided code
542 positioning. If profile information is not available, various types of
543 static analysis are performed to make the predictions normally coming
544 from the profile feedback (IE execution frequency, branch probability,
545 etc). It is implemented in the file @file{bb-reorder.c}, and the
546 various prediction routines are in @file{predict.c}.
549 The option @option{-dB} causes a debugging dump of the RTL code after
550 this pass. This dump file's name is made by appending @samp{.bbro} to
553 @cindex cross-jumping
554 @cindex no-op move instructions
556 Jump optimization is repeated, this time including cross-jumping
557 and deletion of no-op move instructions.
560 The option @option{-dJ} causes a debugging dump of the RTL code after
561 this pass. This dump file's name is made by appending @samp{.jump2}
562 to the input file name.
564 @cindex delayed branch scheduling
565 @cindex scheduling, delayed branch
567 Delayed branch scheduling. This optional pass attempts to find
568 instructions that can go into the delay slots of other instructions,
569 usually jumps and calls. The source file name is @file{reorg.c}.
572 The option @option{-dd} causes a debugging dump of the RTL code after
573 this pass. This dump file's name is made by appending @samp{.dbr}
574 to the input file name.
576 @cindex branch shortening
578 Branch shortening. On many RISC machines, branch instructions have a
579 limited range. Thus, longer sequences of instructions must be used for
580 long branches. In this pass, the compiler figures out what how far each
581 instruction will be from each other instruction, and therefore whether
582 the usual instructions, or the longer sequences, must be used for each
585 @cindex register-to-stack conversion
587 Conversion from usage of some hard registers to usage of a register
588 stack may be done at this point. Currently, this is supported only
589 for the floating-point registers of the Intel 80387 coprocessor. The
590 source file name is @file{reg-stack.c}.
593 The options @option{-dk} causes a debugging dump of the RTL code after
594 this pass. This dump file's name is made by appending @samp{.stack}
595 to the input file name.
598 @cindex peephole optimization
600 Final. This pass outputs the assembler code for the function. It is
601 also responsible for identifying spurious test and compare
602 instructions. Machine-specific peephole optimizations are performed
603 at the same time. The function entry and exit sequences are generated
604 directly as assembler code in this pass; they never exist as RTL@.
606 The source files are @file{final.c} plus @file{insn-output.c}; the
607 latter is generated automatically from the machine description by the
608 tool @file{genoutput}. The header file @file{conditions.h} is used
609 for communication between these files.
611 @cindex debugging information generation
613 Debugging information output. This is run after final because it must
614 output the stack slot offsets for pseudo registers that did not get
615 hard registers. Source files are @file{dbxout.c} for DBX symbol table
616 format, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c}
617 for DWARF symbol table format, files @file{dwarf2out.c} and
618 @file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c}
619 for VMS debug symbol table format.
622 Some additional files are used by all or many passes:
626 Every pass uses @file{machmode.def} and @file{machmode.h} which define
630 Several passes use @file{real.h}, which defines the default
631 representation of floating point constants and how to operate on them.
634 All the passes that work with RTL use the header files @file{rtl.h}
635 and @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools
636 @code{gen*} also use these files to read and work with the machine
640 All the tools that read the machine description use support routines
641 found in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}.
645 Several passes refer to the header file @file{insn-config.h} which
646 contains a few parameters (C macro definitions) generated
647 automatically from the machine description RTL by the tool
650 @cindex instruction recognizer
652 Several passes use the instruction recognizer, which consists of
653 @file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c}
654 and @file{insn-extract.c} that are generated automatically from the
655 machine description by the tools @file{genrecog} and
659 Several passes use the header files @file{regs.h} which defines the
660 information recorded about pseudo register usage, and @file{basic-block.h}
661 which defines the information recorded about basic blocks.
664 @file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector
665 with a bit for each hard register, and some macros to manipulate it.
666 This type is just @code{int} if the machine has few enough hard registers;
667 otherwise it is an array of @code{int} and some of the macros expand
671 Several passes use instruction attributes. A definition of the
672 attributes defined for a particular machine is in file
673 @file{insn-attr.h}, which is generated from the machine description by
674 the program @file{genattr}. The file @file{insn-attrtab.c} contains
675 subroutines to obtain the attribute values for insns and information
676 about processor pipeline characteristics for the instruction
677 scheduler. It is generated from the machine description by the
678 program @file{genattrtab}.