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.
113 @file{c-semantics.c},
116 along with header files
121 are also used for all of the above languages.
124 @cindex Tree optimization
126 Tree optimization. This is the optimization of the tree
127 representation, before converting into RTL code.
129 @cindex inline on trees, automatic
130 Currently, the main optimization performed here is tree-based
132 This is implemented in @file{tree-inline.c} and used by both C and C++.
133 Note that tree based inlining turns off rtx based inlining (since it's more
134 powerful, it would be a waste of time to do rtx based inlining in
137 @cindex constant folding
138 @cindex arithmetic simplifications
139 @cindex simplifications, arithmetic
140 Constant folding and some arithmetic simplifications are also done
141 during this pass, on the tree representation.
142 The routines that perform these tasks are located in @file{fold-const.c}.
144 @cindex RTL generation
146 RTL generation. This is the conversion of syntax tree into RTL code.
148 @cindex target-parameter-dependent code
149 This is where the bulk of target-parameter-dependent code is found,
150 since often it is necessary for strategies to apply only when certain
151 standard kinds of instructions are available. The purpose of named
152 instruction patterns is to provide this information to the RTL
155 @cindex tail recursion optimization
156 Optimization is done in this pass for @code{if}-conditions that are
157 comparisons, boolean operations or conditional expressions. Tail
158 recursion is detected at this time also. Decisions are made about how
159 best to arrange loops and how to output @code{switch} statements.
161 @c Avoiding overfull is tricky here.
162 The source files for RTL generation include
170 and @file{emit-rtl.c}.
172 @file{insn-emit.c}, generated from the machine description by the
173 program @code{genemit}, is used in this pass. The header file
174 @file{expr.h} is used for communication within this pass.
178 The header files @file{insn-flags.h} and @file{insn-codes.h},
179 generated from the machine description by the programs @code{genflags}
180 and @code{gencodes}, tell this pass which standard names are available
181 for use and which patterns correspond to them.
183 Aside from debugging information output, none of the following passes
184 refers to the tree structure representation of the function (only
185 part of which is saved).
187 @cindex inline on rtx, automatic
188 The decision of whether the function can and should be expanded inline
189 in its subsequent callers is made at the end of rtl generation. The
190 function must meet certain criteria, currently related to the size of
191 the function and the types and number of parameters it has. Note that
192 this function may contain loops, recursive calls to itself
193 (tail-recursive functions can be inlined!), gotos, in short, all
194 constructs supported by GCC@. The file @file{integrate.c} contains
195 the code to save a function's rtl for later inlining and to inline that
196 rtl when the function is called. The header file @file{integrate.h}
197 is also used for this purpose.
200 The option @option{-dr} causes a debugging dump of the RTL code after
201 this pass. This dump file's name is made by appending @samp{.rtl} to
204 @c Should the exception handling pass be talked about here?
206 @cindex sibling call optimization
208 Sibiling call optimization. This pass performs tail recursion
209 elimination, and tail and sibling call optimizations. The purpose of
210 these optimizations is to reduce the overhead of function calls,
213 The source file of this pass is @file{sibcall.c}
216 The option @option{-di} causes a debugging dump of the RTL code after
217 this pass is run. This dump file's name is made by appending
218 @samp{.sibling} to the input file name.
220 @cindex jump optimization
221 @cindex unreachable code
224 Jump optimization. This pass simplifies jumps to the following
225 instruction, jumps across jumps, and jumps to jumps. It deletes
226 unreferenced labels and unreachable code, except that unreachable code
227 that contains a loop is not recognized as unreachable in this pass.
228 (Such loops are deleted later in the basic block analysis.) It also
229 converts some code originally written with jumps into sequences of
230 instructions that directly set values from the results of comparisons,
231 if the machine has such instructions.
233 Jump optimization is performed two or three times. The first time is
234 immediately following RTL generation. The second time is after CSE,
235 but only if CSE says repeated jump optimization is needed. The
236 last time is right before the final pass. That time, cross-jumping
237 and deletion of no-op move instructions are done together with the
238 optimizations described above.
240 The source file of this pass is @file{jump.c}.
243 The option @option{-dj} causes a debugging dump of the RTL code after
244 this pass is run for the first time. This dump file's name is made by
245 appending @samp{.jump} to the input file name.
248 @cindex register use analysis
250 Register scan. This pass finds the first and last use of each
251 register, as a guide for common subexpression elimination. Its source
252 is in @file{regclass.c}.
254 @cindex jump threading
256 @opindex fthread-jumps
257 Jump threading. This pass detects a condition jump that branches to an
258 identical or inverse test. Such jumps can be @samp{threaded} through
259 the second conditional test. The source code for this pass is in
260 @file{jump.c}. This optimization is only performed if
261 @option{-fthread-jumps} is enabled.
263 @cindex SSA optimizations
264 @cindex Single Static Assignment optimizations
267 Static Single Assignment (SSA) based optimization passes. The
268 SSA conversion passes (to/from) are turned on by the @option{-fssa}
269 option (it is also done automatically if you enable an SSA optimization pass).
270 These passes utilize a form called Static Single Assignment. In SSA form,
271 each variable (pseudo register) is only set once, giving you def-use
272 and use-def chains for free, and enabling a lot more optimization
273 passes to be run in linear time.
274 Conversion to and from SSA form is handled by functions in
278 The option @option{-de} causes a debugging dump of the RTL code after
279 this pass. This dump file's name is made by appending @samp{.ssa} to
282 @cindex SSA Conditional Constant Propagation
283 @cindex Conditional Constant Propagation, SSA based
284 @cindex conditional constant propagation
287 SSA Conditional Constant Propagation. Turned on by the @option{-fssa-ccp}
288 SSA Aggressive Dead Code Elimination. Turned on by the @option{-fssa-dce}
289 option. This pass performs conditional constant propagation to simplify
290 instructions including conditional branches. This pass is more aggressive
291 than the constant propgation 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 class preference pass
463 Register class preferencing. The RTL code is scanned to find out
464 which register class is best for each pseudo register. The source
465 file is @file{regclass.c}.
467 @cindex register allocation
468 @cindex local register allocation
470 Local register allocation (@file{local-alloc.c}). This pass allocates
471 hard registers to pseudo registers that are used only within one basic
472 block. Because the basic block is linear, it can use fast and
473 powerful techniques to do a very good job.
476 The option @option{-dl} causes a debugging dump of the RTL code after
477 this pass. This dump file's name is made by appending @samp{.lreg} to
480 @cindex global register allocation
482 Global register allocation (@file{global.c}). This pass
483 allocates hard registers for the remaining pseudo registers (those
484 whose life spans are not contained in one basic block).
488 Reloading. This pass renumbers pseudo registers with the hardware
489 registers numbers they were allocated. Pseudo registers that did not
490 get hard registers are replaced with stack slots. Then it finds
491 instructions that are invalid because a value has failed to end up in
492 a register, or has ended up in a register of the wrong kind. It fixes
493 up these instructions by reloading the problematical values
494 temporarily into registers. Additional instructions are generated to
497 The reload pass also optionally eliminates the frame pointer and inserts
498 instructions to save and restore call-clobbered registers around calls.
500 Source files are @file{reload.c} and @file{reload1.c}, plus the header
501 @file{reload.h} used for communication between them.
504 The option @option{-dg} causes a debugging dump of the RTL code after
505 this pass. This dump file's name is made by appending @samp{.greg} to
508 @cindex instruction scheduling
509 @cindex scheduling, instruction
511 Instruction scheduling is repeated here to try to avoid pipeline stalls
512 due to memory loads generated for spilled pseudo registers.
515 The option @option{-dR} causes a debugging dump of the RTL code after
516 this pass. This dump file's name is made by appending @samp{.sched2}
517 to the input file name.
519 @cindex basic block reordering
520 @cindex reordering, block
522 Basic block reordering. This pass implements profile guided code
523 positioning. If profile information is not available, various types of
524 static analysis are performed to make the predictions normally coming
525 from the profile feedback (IE execution frequency, branch probability,
526 etc). It is implemented in the file @file{bb-reorder.c}, and the
527 various prediction routines are in @file{predict.c}.
530 The option @option{-dB} causes a debugging dump of the RTL code after
531 this pass. This dump file's name is made by appending @samp{.bbro} to
534 @cindex cross-jumping
535 @cindex no-op move instructions
537 Jump optimization is repeated, this time including cross-jumping
538 and deletion of no-op move instructions.
541 The option @option{-dJ} causes a debugging dump of the RTL code after
542 this pass. This dump file's name is made by appending @samp{.jump2}
543 to the input file name.
545 @cindex delayed branch scheduling
546 @cindex scheduling, delayed branch
548 Delayed branch scheduling. This optional pass attempts to find
549 instructions that can go into the delay slots of other instructions,
550 usually jumps and calls. The source file name is @file{reorg.c}.
553 The option @option{-dd} causes a debugging dump of the RTL code after
554 this pass. This dump file's name is made by appending @samp{.dbr}
555 to the input file name.
557 @cindex branch shortening
559 Branch shortening. On many RISC machines, branch instructions have a
560 limited range. Thus, longer sequences of instructions must be used for
561 long branches. In this pass, the compiler figures out what how far each
562 instruction will be from each other instruction, and therefore whether
563 the usual instructions, or the longer sequences, must be used for each
566 @cindex register-to-stack conversion
568 Conversion from usage of some hard registers to usage of a register
569 stack may be done at this point. Currently, this is supported only
570 for the floating-point registers of the Intel 80387 coprocessor. The
571 source file name is @file{reg-stack.c}.
574 The options @option{-dk} causes a debugging dump of the RTL code after
575 this pass. This dump file's name is made by appending @samp{.stack}
576 to the input file name.
579 @cindex peephole optimization
581 Final. This pass outputs the assembler code for the function. It is
582 also responsible for identifying spurious test and compare
583 instructions. Machine-specific peephole optimizations are performed
584 at the same time. The function entry and exit sequences are generated
585 directly as assembler code in this pass; they never exist as RTL@.
587 The source files are @file{final.c} plus @file{insn-output.c}; the
588 latter is generated automatically from the machine description by the
589 tool @file{genoutput}. The header file @file{conditions.h} is used
590 for communication between these files.
592 @cindex debugging information generation
594 Debugging information output. This is run after final because it must
595 output the stack slot offsets for pseudo registers that did not get
596 hard registers. Source files are @file{dbxout.c} for DBX symbol table
597 format, @file{sdbout.c} for SDB symbol table format, @file{dwarfout.c}
598 for DWARF symbol table format, files @file{dwarf2out.c} and
599 @file{dwarf2asm.c} for DWARF2 symbol table format, and @file{vmsdbgout.c}
600 for VMS debug symbol table format.
603 Some additional files are used by all or many passes:
607 Every pass uses @file{machmode.def} and @file{machmode.h} which define
611 Several passes use @file{real.h}, which defines the default
612 representation of floating point constants and how to operate on them.
615 All the passes that work with RTL use the header files @file{rtl.h}
616 and @file{rtl.def}, and subroutines in file @file{rtl.c}. The tools
617 @code{gen*} also use these files to read and work with the machine
621 All the tools that read the machine description use support routines
622 found in @file{gensupport.c}, @file{errors.c}, and @file{read-rtl.c}.
626 Several passes refer to the header file @file{insn-config.h} which
627 contains a few parameters (C macro definitions) generated
628 automatically from the machine description RTL by the tool
631 @cindex instruction recognizer
633 Several passes use the instruction recognizer, which consists of
634 @file{recog.c} and @file{recog.h}, plus the files @file{insn-recog.c}
635 and @file{insn-extract.c} that are generated automatically from the
636 machine description by the tools @file{genrecog} and
640 Several passes use the header files @file{regs.h} which defines the
641 information recorded about pseudo register usage, and @file{basic-block.h}
642 which defines the information recorded about basic blocks.
645 @file{hard-reg-set.h} defines the type @code{HARD_REG_SET}, a bit-vector
646 with a bit for each hard register, and some macros to manipulate it.
647 This type is just @code{int} if the machine has few enough hard registers;
648 otherwise it is an array of @code{int} and some of the macros expand
652 Several passes use instruction attributes. A definition of the
653 attributes defined for a particular machine is in file
654 @file{insn-attr.h}, which is generated from the machine description by
655 the program @file{genattr}. The file @file{insn-attrtab.c} contains
656 subroutines to obtain the attribute values for insns and information
657 about processor pipeline characteristics for the instruction
658 scheduler. It is generated from the machine description by the
659 program @file{genattrtab}.