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, 2005 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@dots{} 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{definitions} 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}, @file{tree-optimize.c}
150 and @file{tree-pass.h}.
151 Its job is to run all of the individual passes in the correct order,
152 and take care of standard bookkeeping that applies to every pass.
154 The theory of operation is that each pass defines a structure that
155 represents everything we need to know about that pass---when it
156 should be run, how it should be run, what intermediate language
157 form or on-the-side data structures it needs. We register the pass
158 to be run in some particular order, and the pass manager arranges
159 for everything to happen in the correct order.
161 The actuality doesn't completely live up to the theory at present.
162 Command-line switches and @code{timevar_id_t} enumerations must still
163 be defined elsewhere. The pass manager validates constraints but does
164 not attempt to (re-)generate data structures or lower intermediate
165 language form based on the requirements of the next pass. Nevertheless,
166 what is present is useful, and a far sight better than nothing at all.
168 TODO: describe the global variables set up by the pass manager,
169 and a brief description of how a new pass should use it.
170 I need to look at what info rtl passes use first...
172 @node Tree-SSA passes
173 @section Tree-SSA passes
175 The following briefly describes the tree optimization passes that are
176 run after gimplification and what source files they are located in.
179 @item Remove useless statements
181 This pass is an extremely simple sweep across the gimple code in which
182 we identify obviously dead code and remove it. Here we do things like
183 simplify @code{if} statements with constant conditions, remove
184 exception handling constructs surrounding code that obviously cannot
185 throw, remove lexical bindings that contain no variables, and other
186 assorted simplistic cleanups. The idea is to get rid of the obvious
187 stuff quickly rather than wait until later when it's more work to get
188 rid of it. This pass is located in @file{tree-cfg.c} and described by
189 @code{pass_remove_useless_stmts}.
191 @item Mudflap declaration registration
193 If mudflap (@pxref{Optimize Options,,-fmudflap -fmudflapth
194 -fmudflapir,gcc.info,Using the GNU Compiler Collection (GCC)}) is
195 enabled, we generate code to register some variable declarations with
196 the mudflap runtime. Specifically, the runtime tracks the lifetimes of
197 those variable declarations that have their addresses taken, or whose
198 bounds are unknown at compile time (@code{extern}). This pass generates
199 new exception handling constructs (@code{try}/@code{finally}), and so
200 must run before those are lowered. In addition, the pass enqueues
201 declarations of static variables whose lifetimes extend to the entire
202 program. The pass is located in @file{tree-mudflap.c} and is described
203 by @code{pass_mudflap_1}.
205 @item OpenMP lowering
207 If OpenMP generation (@option{-fopenmp}) is enabled, this pass lowers
208 OpenMP constructs into GIMPLE.
210 Lowering of OpenMP constructs involves creating replacement
211 expressions for local variables that have been mapped using data
212 sharing clauses, exposing the control flow of most synchronization
213 directives and adding region markers to facilitate the creation of the
214 control flow graph. The pass is located in @file{omp-low.c} and is
215 described by @code{pass_lower_omp}.
217 @item OpenMP expansion
219 If OpenMP generation (@option{-fopenmp}) is enabled, this pass expands
220 parallel regions into their own functions to be invoked by the thread
221 library. The pass is located in @file{omp-low.c} and is described by
222 @code{pass_expand_omp}.
224 @item Lower control flow
226 This pass flattens @code{if} statements (@code{COND_EXPR}) and
227 and moves lexical bindings (@code{BIND_EXPR}) out of line. After
228 this pass, all @code{if} statements will have exactly two @code{goto}
229 statements in its @code{then} and @code{else} arms. Lexical binding
230 information for each statement will be found in @code{TREE_BLOCK} rather
231 than being inferred from its position under a @code{BIND_EXPR}. This
232 pass is found in @file{gimple-low.c} and is described by
233 @code{pass_lower_cf}.
235 @item Lower exception handling control flow
237 This pass decomposes high-level exception handling constructs
238 (@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
239 that explicitly represents the control flow involved. After this
240 pass, @code{lookup_stmt_eh_region} will return a non-negative
241 number for any statement that may have EH control flow semantics;
242 examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
243 for exact semantics. Exact control flow may be extracted from
244 @code{foreach_reachable_handler}. The EH region nesting tree is defined
245 in @file{except.h} and built in @file{except.c}. The lowering pass
246 itself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}.
248 @item Build the control flow graph
250 This pass decomposes a function into basic blocks and creates all of
251 the edges that connect them. It is located in @file{tree-cfg.c} and
252 is described by @code{pass_build_cfg}.
254 @item Find all referenced variables
256 This pass walks the entire function and collects an array of all
257 variables referenced in the function, @code{referenced_vars}. The
258 index at which a variable is found in the array is used as a UID
259 for the variable within this function. This data is needed by the
260 SSA rewriting routines. The pass is located in @file{tree-dfa.c}
261 and is described by @code{pass_referenced_vars}.
263 @item Enter static single assignment form
265 This pass rewrites the function such that it is in SSA form. After
266 this pass, all @code{is_gimple_reg} variables will be referenced by
267 @code{SSA_NAME}, and all occurrences of other variables will be
268 annotated with @code{VDEFS} and @code{VUSES}; PHI nodes will have
269 been inserted as necessary for each basic block. This pass is
270 located in @file{tree-ssa.c} and is described by @code{pass_build_ssa}.
272 @item Warn for uninitialized variables
274 This pass scans the function for uses of @code{SSA_NAME}s that
275 are fed by default definition. For non-parameter variables, such
276 uses are uninitialized. The pass is run twice, before and after
277 optimization. In the first pass we only warn for uses that are
278 positively uninitialized; in the second pass we warn for uses that
279 are possibly uninitialized. The pass is located in @file{tree-ssa.c}
280 and is defined by @code{pass_early_warn_uninitialized} and
281 @code{pass_late_warn_uninitialized}.
283 @item Dead code elimination
285 This pass scans the function for statements without side effects whose
286 result is unused. It does not do memory life analysis, so any value
287 that is stored in memory is considered used. The pass is run multiple
288 times throughout the optimization process. It is located in
289 @file{tree-ssa-dce.c} and is described by @code{pass_dce}.
291 @item Dominator optimizations
293 This pass performs trivial dominator-based copy and constant propagation,
294 expression simplification, and jump threading. It is run multiple times
295 throughout the optimization process. It it located in @file{tree-ssa-dom.c}
296 and is described by @code{pass_dominator}.
298 @item Redundant PHI elimination
300 This pass removes PHI nodes for which all of the arguments are the same
301 value, excluding feedback. Such degenerate forms are typically created
302 by removing unreachable code. The pass is run multiple times throughout
303 the optimization process. It is located in @file{tree-ssa.c} and is
304 described by @code{pass_redundant_phi}.o
306 @item Forward propagation of single-use variables
308 This pass attempts to remove redundant computation by substituting
309 variables that are used once into the expression that uses them and
310 seeing if the result can be simplified. It is located in
311 @file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}.
315 This pass attempts to change the name of compiler temporaries involved in
316 copy operations such that SSA->normal can coalesce the copy away. When compiler
317 temporaries are copies of user variables, it also renames the compiler
318 temporary to the user variable resulting in better use of user symbols. It is
319 located in @file{tree-ssa-copyrename.c} and is described by
320 @code{pass_copyrename}.
322 @item PHI node optimizations
324 This pass recognizes forms of PHI inputs that can be represented as
325 conditional expressions and rewrites them into straight line code.
326 It is located in @file{tree-ssa-phiopt.c} and is described by
329 @item May-alias optimization
331 This pass performs a flow sensitive SSA-based points-to analysis.
332 The resulting may-alias, must-alias, and escape analysis information
333 is used to promote variables from in-memory addressable objects to
334 non-aliased variables that can be renamed into SSA form. We also
335 update the @code{VDEF}/@code{VUSE} memory tags for non-renamable
336 aggregates so that we get fewer false kills. The pass is located
337 in @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}.
339 Interprocedural points-to information is located in
340 @file{tree-ssa-structalias.c} and described by @code{pass_ipa_pta}.
344 This pass rewrites the function in order to collect runtime block
345 and value profiling data. Such data may be fed back into the compiler
346 on a subsequent run so as to allow optimization based on expected
347 execution frequencies. The pass is located in @file{predict.c} and
348 is described by @code{pass_profile}.
350 @item Lower complex arithmetic
352 This pass rewrites complex arithmetic operations into their component
353 scalar arithmetic operations. The pass is located in @file{tree-complex.c}
354 and is described by @code{pass_lower_complex}.
356 @item Scalar replacement of aggregates
358 This pass rewrites suitable non-aliased local aggregate variables into
359 a set of scalar variables. The resulting scalar variables are
360 rewritten into SSA form, which allows subsequent optimization passes
361 to do a significantly better job with them. The pass is located in
362 @file{tree-sra.c} and is described by @code{pass_sra}.
364 @item Dead store elimination
366 This pass eliminates stores to memory that are subsequently overwritten
367 by another store, without any intervening loads. The pass is located
368 in @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
370 @item Tail recursion elimination
372 This pass transforms tail recursion into a loop. It is located in
373 @file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
375 @item Forward store motion
377 This pass sinks stores and assignments down the flowgraph closer to it's
378 use point. The pass is located in @file{tree-ssa-sink.c} and is
379 described by @code{pass_sink_code}.
381 @item Partial redundancy elimination
383 This pass eliminates partially redundant computations, as well as
384 performing load motion. The pass is located in @file{tree-ssa-pre.c}
385 and is described by @code{pass_pre}.
387 Just before partial redundancy elimination, if
388 @option{-funsafe-math-optimizations} is on, GCC tries to convert
389 divisions to multiplications by the reciprocal. The pass is located
390 in @file{tree-ssa-math-opts.c} and is described by
391 @code{pass_cse_reciprocal}.
393 @item Full redundancy elimination
395 This is a simpler form of PRE that only eliminate redundancies that
396 occur an all paths. It is located in @file{tree-ssa-pre.c} and
397 described by @code{pass_fre}.
399 @item Loop optimization
401 The main driver of the pass is placed in @file{tree-ssa-loop.c}
402 and described by @code{pass_loop}.
404 The optimizations performed by this pass are:
406 Loop invariant motion. This pass moves only invariants that
407 would be hard to handle on rtl level (function calls, operations that expand to
408 nontrivial sequences of insns). With @option{-funswitch-loops} it also moves
409 operands of conditions that are invariant out of the loop, so that we can use
410 just trivial invariantness analysis in loop unswitching. The pass also includes
411 store motion. The pass is implemented in @file{tree-ssa-loop-im.c}.
413 Canonical induction variable creation. This pass creates a simple counter
414 for number of iterations of the loop and replaces the exit condition of the
415 loop using it, in case when a complicated analysis is necessary to determine
416 the number of iterations. Later optimizations then may determine the number
417 easily. The pass is implemented in @file{tree-ssa-loop-ivcanon.c}.
419 Induction variable optimizations. This pass performs standard induction
420 variable optimizations, including strength reduction, induction variable
421 merging and induction variable elimination. The pass is implemented in
422 @file{tree-ssa-loop-ivopts.c}.
424 Loop unswitching. This pass moves the conditional jumps that are invariant
425 out of the loops. To achieve this, a duplicate of the loop is created for
426 each possible outcome of conditional jump(s). The pass is implemented in
427 @file{tree-ssa-loop-unswitch.c}. This pass should eventually replace the
428 rtl-level loop unswitching in @file{loop-unswitch.c}, but currently
429 the rtl-level pass is not completely redundant yet due to deficiencies
430 in tree level alias analysis.
432 The optimizations also use various utility functions contained in
433 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
434 @file{cfgloopmanip.c}.
436 Vectorization. This pass transforms loops to operate on vector types
437 instead of scalar types. Data parallelism across loop iterations is exploited
438 to group data elements from consecutive iterations into a vector and operate
439 on them in parallel. Depending on available target support the loop is
440 conceptually unrolled by a factor @code{VF} (vectorization factor), which is
441 the number of elements operated upon in parallel in each iteration, and the
442 @code{VF} copies of each scalar operation are fused to form a vector operation.
443 Additional loop transformations such as peeling and versioning may take place
444 to align the number of iterations, and to align the memory accesses in the loop.
445 The pass is implemented in @file{tree-vectorizer.c} (the main driver and general
446 utilities), @file{tree-vect-analyze.c} and @file{tree-vect-transform.c}.
447 Analysis of data references is in @file{tree-data-ref.c}.
449 @item Tree level if-conversion for vectorizer
451 This pass applies if-conversion to simple loops to help vectorizer.
452 We identify if convertible loops, if-convert statements and merge
453 basic blocks in one big block. The idea is to present loop in such
454 form so that vectorizer can have one to one mapping between statements
455 and available vector operations. This patch re-introduces COND_EXPR
456 at GIMPLE level. This pass is located in @file{tree-if-conv.c} and is
457 described by @code{pass_if_conversion}.
459 @item Conditional constant propagation
461 This pass relaxes a lattice of values in order to identify those
462 that must be constant even in the presence of conditional branches.
463 The pass is located in @file{tree-ssa-ccp.c} and is described
466 A related pass that works on memory loads and stores, and not just
467 register values, is located in @file{tree-ssa-ccp.c} and described by
468 @code{pass_store_ccp}.
470 @item Conditional copy propagation
472 This is similar to constant propagation but the lattice of values is
473 the ``copy-of'' relation. It eliminates redundant copies from the
474 code. The pass is located in @file{tree-ssa-copy.c} and described by
475 @code{pass_copy_prop}.
477 A related pass that works on memory copies, and not just register
478 copies, is located in @file{tree-ssa-copy.c} and described by
479 @code{pass_store_copy_prop}.
481 @item Value range propagation
483 This transformation is similar to constant propagation but
484 instead of propagating single constant values, it propagates
485 known value ranges. The implementation is based on Patterson's
486 range propagation algorithm (Accurate Static Branch Prediction by
487 Value Range Propagation, J. R. C. Patterson, PLDI '95). In
488 contrast to Patterson's algorithm, this implementation does not
489 propagate branch probabilities nor it uses more than a single
490 range per SSA name. This means that the current implementation
491 cannot be used for branch prediction (though adapting it would
492 not be difficult). The pass is located in @file{tree-vrp.c} and is
493 described by @code{pass_vrp}.
495 @item Folding built-in functions
497 This pass simplifies built-in functions, as applicable, with constant
498 arguments or with inferrable string lengths. It is located in
499 @file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}.
501 @item Split critical edges
503 This pass identifies critical edges and inserts empty basic blocks
504 such that the edge is no longer critical. The pass is located in
505 @file{tree-cfg.c} and is described by @code{pass_split_crit_edges}.
507 @item Control dependence dead code elimination
509 This pass is a stronger form of dead code elimination that can
510 eliminate unnecessary control flow statements. It is located
511 in @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}.
513 @item Tail call elimination
515 This pass identifies function calls that may be rewritten into
516 jumps. No code transformation is actually applied here, but the
517 data and control flow problem is solved. The code transformation
518 requires target support, and so is delayed until RTL@. In the
519 meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
520 The pass is located in @file{tree-tailcall.c} and is described by
521 @code{pass_tail_calls}. The RTL transformation is handled by
522 @code{fixup_tail_calls} in @file{calls.c}.
524 @item Warn for function return without value
526 For non-void functions, this pass locates return statements that do
527 not specify a value and issues a warning. Such a statement may have
528 been injected by falling off the end of the function. This pass is
529 run last so that we have as much time as possible to prove that the
530 statement is not reachable. It is located in @file{tree-cfg.c} and
531 is described by @code{pass_warn_function_return}.
533 @item Mudflap statement annotation
535 If mudflap is enabled, we rewrite some memory accesses with code to
536 validate that the memory access is correct. In particular, expressions
537 involving pointer dereferences (@code{INDIRECT_REF}, @code{ARRAY_REF},
538 etc.) are replaced by code that checks the selected address range
539 against the mudflap runtime's database of valid regions. This check
540 includes an inline lookup into a direct-mapped cache, based on
541 shift/mask operations of the pointer value, with a fallback function
542 call into the runtime. The pass is located in @file{tree-mudflap.c} and
543 is described by @code{pass_mudflap_2}.
545 @item Leave static single assignment form
547 This pass rewrites the function such that it is in normal form. At
548 the same time, we eliminate as many single-use temporaries as possible,
549 so the intermediate language is no longer GIMPLE, but GENERIC@. The
550 pass is located in @file{tree-outof-ssa.c} and is described by
553 @item Merge PHI nodes that feed into one another
555 This is part of the CFG cleanup passes. It attempts to join PHI nodes
556 from a forwarder CFG block into another block with PHI nodes. The
557 pass is located in @file{tree-cfgcleanup.c} and is described by
558 @code{pass_merge_phi}.
560 @item Return value optimization
562 If a function always returns the same local variable, and that local
563 variable is an aggregate type, then the variable is replaced with the
564 return value for the function (i.e., the function's DECL_RESULT). This
565 is equivalent to the C++ named return value optimization applied to
566 GIMPLE. The pass is located in @file{tree-nrv.c} and is described by
569 @item Return slot optimization
571 If a function returns a memory object and is called as @code{var =
572 foo()}, this pass tries to change the call so that the address of
573 @code{var} is sent to the caller to avoid an extra memory copy. This
574 pass is located in @code{tree-nrv.c} and is described by
575 @code{pass_return_slot}.
577 @item Optimize calls to @code{__builtin_object_size}
579 This is a propagation pass similar to CCP that tries to remove calls
580 to @code{__builtin_object_size} when the size of the object can be
581 computed at compile-time. This pass is located in
582 @file{tree-object-size.c} and is described by
583 @code{pass_object_sizes}.
585 @item Loop invariant motion
587 This pass removes expensive loop-invariant computations out of loops.
588 The pass is located in @file{tree-ssa-loop.c} and described by
591 @item Loop nest optimizations
593 This is a family of loop transformations that works on loop nests. It
594 includes loop interchange, scaling, skewing and reversal and they are
595 all geared to the optimization of data locality in array traversals
596 and the removal of dependencies that hamper optimizations such as loop
597 parallelization and vectorization. The pass is located in
598 @file{tree-loop-linear.c} and described by
599 @code{pass_linear_transform}.
601 @item Removal of empty loops
603 This pass removes loops with no code in them. The pass is located in
604 @file{tree-ssa-loop-ivcanon.c} and described by
605 @code{pass_empty_loop}.
607 @item Unrolling of small loops
609 This pass completely unrolls loops with few iterations. The pass
610 is located in @file{tree-ssa-loop-ivcanon.c} and described by
611 @code{pass_complete_unroll}.
613 @item Array prefetching
615 This pass issues prefetch instructions for array references inside
616 loops. The pass is located in @file{tree-ssa-loop-prefetch.c} and
617 described by @code{pass_loop_prefetch}.
621 This pass rewrites arithmetic expressions to enable optimizations that
622 operate on them, like redundancy elimination and vectorization. The
623 pass is located in @file{tree-ssa-reassoc.c} and described by
626 @item Optimization of @code{stdarg} functions
628 This pass tries to avoid the saving of register arguments into the
629 stack on entry to @code{stdarg} functions. If the function doesn't
630 use any @code{va_start} macros, no registers need to be saved. If
631 @code{va_start} macros are used, the @code{va_list} variables don't
632 escape the function, it is only necessary to save registers that will
633 be used in @code{va_arg} macros. For instance, if @code{va_arg} is
634 only used with integral types in the function, floating point
635 registers don't need to be saved. This pass is located in
636 @code{tree-stdarg.c} and described by @code{pass_stdarg}.
643 The following briefly describes the rtl generation and optimization
644 passes that are run after tree optimization.
649 @c Avoiding overfull is tricky here.
650 The source files for RTL generation include
658 and @file{emit-rtl.c}.
660 @file{insn-emit.c}, generated from the machine description by the
661 program @code{genemit}, is used in this pass. The header file
662 @file{expr.h} is used for communication within this pass.
666 The header files @file{insn-flags.h} and @file{insn-codes.h},
667 generated from the machine description by the programs @code{genflags}
668 and @code{gencodes}, tell this pass which standard names are available
669 for use and which patterns correspond to them.
671 @item Generate exception handling landing pads
673 This pass generates the glue that handles communication between the
674 exception handling library routines and the exception handlers within
675 the function. Entry points in the function that are invoked by the
676 exception handling library are called @dfn{landing pads}. The code
677 for this pass is located within @file{except.c}.
679 @item Cleanup control flow graph
681 This pass removes unreachable code, simplifies jumps to next, jumps to
682 jump, jumps across jumps, etc. The pass is run multiple times.
683 For historical reasons, it is occasionally referred to as the ``jump
684 optimization pass''. The bulk of the code for this pass is in
685 @file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c}
688 @item Forward propagation of single-def values
690 This pass attempts to remove redundant computation by substituting
691 variables that come from a single definition, and
692 seeing if the result can be simplified. It performs copy propagation
693 and addressing mode selection. The pass is run twice, with values
694 being propagated into loops only on the second run. It is located in
697 @item Common subexpression elimination
699 This pass removes redundant computation within basic blocks, and
700 optimizes addressing modes based on cost. The pass is run twice.
701 The source is located in @file{cse.c}.
703 @item Global common subexpression elimination.
705 This pass performs two
706 different types of GCSE depending on whether you are optimizing for
707 size or not (LCM based GCSE tends to increase code size for a gain in
708 speed, while Morel-Renvoise based GCSE does not).
709 When optimizing for size, GCSE is done using Morel-Renvoise Partial
710 Redundancy Elimination, with the exception that it does not try to move
711 invariants out of loops---that is left to the loop optimization pass.
712 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
714 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
715 done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
716 based GCSE also does loop invariant code motion. We also perform load
717 and store motion when optimizing for speed.
718 Regardless of which type of GCSE is used, the GCSE pass also performs
719 global constant and copy propagation.
720 The source file for this pass is @file{gcse.c}, and the LCM routines
723 @item Loop optimization
725 This pass performs several loop related optimizations.
726 The source files @file{cfgloopanal.c} and @file{cfgloopmanip.c} contain
727 generic loop analysis and manipulation code. Initialization and finalization
728 of loop structures is handled by @file{loop-init.c}.
729 A loop invariant motion pass is implemented in @file{loop-invariant.c}.
730 Basic block level optimizations---unrolling, peeling and unswitching loops---
731 are implemented in @file{loop-unswitch.c} and @file{loop-unroll.c}.
732 Replacing of the exit condition of loops by special machine-dependent
733 instructions is handled by @file{loop-doloop.c}.
737 This pass is an aggressive form of GCSE that transforms the control
738 flow graph of a function by propagating constants into conditional
739 branch instructions. The source file for this pass is @file{gcse.c}.
743 This pass attempts to replace conditional branches and surrounding
744 assignments with arithmetic, boolean value producing comparison
745 instructions, and conditional move instructions. In the very last
746 invocation after reload, it will generate predicated instructions
747 when supported by the target. The pass is located in @file{ifcvt.c}.
749 @item Web construction
751 This pass splits independent uses of each pseudo-register. This can
752 improve effect of the other transformation, such as CSE or register
753 allocation. Its source files are @file{web.c}.
757 This pass computes which pseudo-registers are live at each point in
758 the program, and makes the first instruction that uses a value point
759 at the instruction that computed the value. It then deletes
760 computations whose results are never used, and combines memory
761 references with add or subtract instructions to make autoincrement or
762 autodecrement addressing. The pass is located in @file{flow.c}.
764 @item Instruction combination
766 This pass attempts to combine groups of two or three instructions that
767 are related by data flow into single instructions. It combines the
768 RTL expressions for the instructions by substitution, simplifies the
769 result using algebra, and then attempts to match the result against
770 the machine description. The pass is located in @file{combine.c}.
772 @item Register movement
774 This pass looks for cases where matching constraints would force an
775 instruction to need a reload, and this reload would be a
776 register-to-register move. It then attempts to change the registers
777 used by the instruction to avoid the move instruction.
778 The pass is located in @file{regmove.c}.
780 @item Optimize mode switching
782 This pass looks for instructions that require the processor to be in a
783 specific ``mode'' and minimizes the number of mode changes required to
784 satisfy all users. What these modes are, and what they apply to are
785 completely target-specific.
786 The source is located in @file{mode-switching.c}.
788 @cindex modulo scheduling
789 @cindex sms, swing, software pipelining
790 @item Modulo scheduling
792 This pass looks at innermost loops and reorders their instructions
793 by overlapping different iterations. Modulo scheduling is performed
794 immediately before instruction scheduling.
795 The pass is located in (@file{modulo-sched.c}).
797 @item Instruction scheduling
799 This pass looks for instructions whose output will not be available by
800 the time that it is used in subsequent instructions. Memory loads and
801 floating point instructions often have this behavior on RISC machines.
802 It re-orders instructions within a basic block to try to separate the
803 definition and use of items that otherwise would cause pipeline
804 stalls. This pass is performed twice, before and after register
805 allocation. The pass is located in @file{haifa-sched.c},
806 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and
809 @item Register allocation
811 These passes make sure that all occurrences of pseudo registers are
812 eliminated, either by allocating them to a hard register, replacing
813 them by an equivalent expression (e.g.@: a constant) or by placing
814 them on the stack. This is done in several subpasses:
818 Register class preferencing. The RTL code is scanned to find out
819 which register class is best for each pseudo register. The source
820 file is @file{regclass.c}.
823 Local register allocation. This pass allocates hard registers to
824 pseudo registers that are used only within one basic block. Because
825 the basic block is linear, it can use fast and powerful techniques to
826 do a decent job. The source is located in @file{local-alloc.c}.
829 Global register allocation. This pass allocates hard registers for
830 the remaining pseudo registers (those whose life spans are not
831 contained in one basic block). The pass is located in @file{global.c}.
835 Reloading. This pass renumbers pseudo registers with the hardware
836 registers numbers they were allocated. Pseudo registers that did not
837 get hard registers are replaced with stack slots. Then it finds
838 instructions that are invalid because a value has failed to end up in
839 a register, or has ended up in a register of the wrong kind. It fixes
840 up these instructions by reloading the problematical values
841 temporarily into registers. Additional instructions are generated to
844 The reload pass also optionally eliminates the frame pointer and inserts
845 instructions to save and restore call-clobbered registers around calls.
847 Source files are @file{reload.c} and @file{reload1.c}, plus the header
848 @file{reload.h} used for communication between them.
851 @item Basic block reordering
853 This pass implements profile guided code positioning. If profile
854 information is not available, various types of static analysis are
855 performed to make the predictions normally coming from the profile
856 feedback (IE execution frequency, branch probability, etc). It is
857 implemented in the file @file{bb-reorder.c}, and the various
858 prediction routines are in @file{predict.c}.
860 @item Variable tracking
862 This pass computes where the variables are stored at each
863 position in code and generates notes describing the variable locations
864 to RTL code. The location lists are then generated according to these
865 notes to debug information if the debugging information format supports
868 @item Delayed branch scheduling
870 This optional pass attempts to find instructions that can go into the
871 delay slots of other instructions, usually jumps and calls. The
872 source file name is @file{reorg.c}.
874 @item Branch shortening
876 On many RISC machines, branch instructions have a limited range.
877 Thus, longer sequences of instructions must be used for long branches.
878 In this pass, the compiler figures out what how far each instruction
879 will be from each other instruction, and therefore whether the usual
880 instructions, or the longer sequences, must be used for each branch.
882 @item Register-to-stack conversion
884 Conversion from usage of some hard registers to usage of a register
885 stack may be done at this point. Currently, this is supported only
886 for the floating-point registers of the Intel 80387 coprocessor. The
887 source file name is @file{reg-stack.c}.
891 This pass outputs the assembler code for the function. The source files
892 are @file{final.c} plus @file{insn-output.c}; the latter is generated
893 automatically from the machine description by the tool @file{genoutput}.
894 The header file @file{conditions.h} is used for communication between
895 these files. If mudflap is enabled, the queue of deferred declarations
896 and any addressed constants (e.g., string literals) is processed by
897 @code{mudflap_finish_file} into a synthetic constructor function
898 containing calls into the mudflap runtime.
900 @item Debugging information output
902 This is run after final because it must output the stack slot offsets
903 for pseudo registers that did not get hard registers. Source files
904 are @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for
905 SDB symbol table format, @file{dwarfout.c} for DWARF symbol table
906 format, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2
907 symbol table format, and @file{vmsdbgout.c} for VMS debug symbol table