* gcc.dg/guality/guality.exp: Skip on AIX.
[official-gcc.git] / gcc / doc / passes.texi
blob045f964a939d91b8dbeb25f2d92fad61a107440c
1 @c markers: BUG TODO
3 @c Copyright (C) 1988-2013 Free Software Foundation, Inc.
4 @c This is part of the GCC manual.
5 @c For copying conditions, see the file gcc.texi.
7 @node Passes
8 @chapter Passes and Files of the Compiler
9 @cindex passes and files of the compiler
10 @cindex files and passes of the compiler
11 @cindex compiler passes and files
13 This chapter is dedicated to giving an overview of the optimization and
14 code generation passes of the compiler.  In the process, it describes
15 some of the language front end interface, though this description is no
16 where near complete.
18 @menu
19 * Parsing pass::         The language front end turns text into bits.
20 * Cilk Plus Transformation:: Transform Cilk Plus Code to equivalent C/C++.
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.
25 @end menu
27 @node Parsing pass
28 @section Parsing pass
29 @cindex GENERIC
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 (@pxref{GENERIC}), 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.
39 @cindex GIMPLE
40 @cindex gimplification
41 @cindex gimplifier
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 (@pxref{GIMPLE}) on each function,
49 and uses the gimplifier callbacks to convert the language-specific tree
50 nodes directly to GIMPLE before passing the function off to be compiled.
51 The Fortran front end converts from a private representation to GENERIC,
52 which is later lowered to GIMPLE when the function is compiled.  Which
53 route to choose probably depends on how well GENERIC (plus extensions)
54 can be made to match up with the source language and necessary parsing
55 data structures.
57 BUG: Gimplification must occur before nested function lowering,
58 and nested function lowering must be done by the front end before
59 passing the data off to cgraph.
61 TODO: Cgraph should control nested function lowering.  It would
62 only be invoked when it is certain that the outer-most function
63 is used.
65 TODO: Cgraph needs a gimplify_function callback.  It should be
66 invoked when (1) it is certain that the function is used, (2)
67 warning flags specified by the user require some amount of
68 compilation in order to honor, (3) the language indicates that
69 semantic analysis is not complete until gimplification occurs.
70 Hum@dots{} this sounds overly complicated.  Perhaps we should just
71 have the front end gimplify always; in most cases it's only one
72 function call.
74 The front end needs to pass all function definitions and top level
75 declarations off to the middle-end so that they can be compiled and
76 emitted to the object file.  For a simple procedural language, it is
77 usually most convenient to do this as each top level declaration or
78 definition is seen.  There is also a distinction to be made between
79 generating functional code and generating complete debug information.
80 The only thing that is absolutely required for functional code is that
81 function and data @emph{definitions} be passed to the middle-end.  For
82 complete debug information, function, data and type declarations
83 should all be passed as well.
85 @findex rest_of_decl_compilation
86 @findex rest_of_type_compilation
87 @findex cgraph_finalize_function
88 In any case, the front end needs each complete top-level function or
89 data declaration, and each data definition should be passed to
90 @code{rest_of_decl_compilation}.  Each complete type definition should
91 be passed to @code{rest_of_type_compilation}.  Each function definition
92 should be passed to @code{cgraph_finalize_function}.
94 TODO: I know rest_of_compilation currently has all sorts of
95 RTL generation semantics.  I plan to move all code generation
96 bits (both Tree and RTL) to compile_function.  Should we hide
97 cgraph from the front ends and move back to rest_of_compilation
98 as the official interface?  Possibly we should rename all three
99 interfaces such that the names match in some meaningful way and
100 that is more descriptive than "rest_of".
102 The middle-end will, at its option, emit the function and data
103 definitions immediately or queue them for later processing.
105 @node Cilk Plus Transformation
106 @section Cilk Plus Transformation
107 @cindex CILK_PLUS
109 If Cilk Plus generation (flag @option{-fcilkplus}) is enabled, all the Cilk 
110 Plus code is transformed into equivalent C and C++ functions.  Majority of this 
111 transformation occurs toward the end of the parsing and right before the 
112 gimplification pass.  
114 These are the major components to the Cilk Plus language extension:
115 @itemize @bullet
116 @item Array Notations:
117 During parsing phase, all the array notation specific information is stored in 
118 @code{ARRAY_NOTATION_REF} tree using the function 
119 @code{c_parser_array_notation}.  During the end of parsing, we check the entire
120 function to see if there are any array notation specific code (using the 
121 function @code{contains_array_notation_expr}).  If this function returns 
122 true, then we expand them using either @code{expand_array_notation_exprs} or
123 @code{build_array_notation_expr}.  For the cases where array notations are 
124 inside conditions, they are transformed using the function 
125 @code{fix_conditional_array_notations}.  The C language-specific routines are 
126 located in @file{c/c-array-notation.c} and the equivalent C++ routines are in 
127 file @file{cp/cp-array-notation.c}.  Common routines such as functions to 
128 initialize builtin functions are stored in @file{array-notation-common.c}.
129 @end itemize
131 Detailed information about Cilk Plus and language specification is provided in 
132 @w{@uref{http://www.cilkplus.org/}}.  It is worth mentioning that the current 
133 implementation follows ABI 0.9.
135 @node Gimplification pass
136 @section Gimplification pass
138 @cindex gimplification
139 @cindex GIMPLE
140 @dfn{Gimplification} is a whimsical term for the process of converting
141 the intermediate representation of a function into the GIMPLE language
142 (@pxref{GIMPLE}).  The term stuck, and so words like ``gimplification'',
143 ``gimplify'', ``gimplifier'' and the like are sprinkled throughout this
144 section of code.
146 While a front end may certainly choose to generate GIMPLE directly if
147 it chooses, this can be a moderately complex process unless the
148 intermediate language used by the front end is already fairly simple.
149 Usually it is easier to generate GENERIC trees plus extensions
150 and let the language-independent gimplifier do most of the work.
152 @findex gimplify_function_tree
153 @findex gimplify_expr
154 @findex lang_hooks.gimplify_expr
155 The main entry point to this pass is @code{gimplify_function_tree}
156 located in @file{gimplify.c}.  From here we process the entire
157 function gimplifying each statement in turn.  The main workhorse
158 for this pass is @code{gimplify_expr}.  Approximately everything
159 passes through here at least once, and it is from here that we
160 invoke the @code{lang_hooks.gimplify_expr} callback.
162 The callback should examine the expression in question and return
163 @code{GS_UNHANDLED} if the expression is not a language specific
164 construct that requires attention.  Otherwise it should alter the
165 expression in some way to such that forward progress is made toward
166 producing valid GIMPLE@.  If the callback is certain that the
167 transformation is complete and the expression is valid GIMPLE, it
168 should return @code{GS_ALL_DONE}.  Otherwise it should return
169 @code{GS_OK}, which will cause the expression to be processed again.
170 If the callback encounters an error during the transformation (because
171 the front end is relying on the gimplification process to finish
172 semantic checks), it should return @code{GS_ERROR}.
174 @node Pass manager
175 @section Pass manager
177 The pass manager is located in @file{passes.c}, @file{tree-optimize.c}
178 and @file{tree-pass.h}.
179 Its job is to run all of the individual passes in the correct order,
180 and take care of standard bookkeeping that applies to every pass.
182 The theory of operation is that each pass defines a structure that
183 represents everything we need to know about that pass---when it
184 should be run, how it should be run, what intermediate language
185 form or on-the-side data structures it needs.  We register the pass
186 to be run in some particular order, and the pass manager arranges
187 for everything to happen in the correct order.
189 The actuality doesn't completely live up to the theory at present.
190 Command-line switches and @code{timevar_id_t} enumerations must still
191 be defined elsewhere.  The pass manager validates constraints but does
192 not attempt to (re-)generate data structures or lower intermediate
193 language form based on the requirements of the next pass.  Nevertheless,
194 what is present is useful, and a far sight better than nothing at all.
196 Each pass should have a unique name.
197 Each pass may have its own dump file (for GCC debugging purposes).
198 Passes with a name starting with a star do not dump anything.
199 Sometimes passes are supposed to share a dump file / option name.
200 To still give these unique names, you can use a prefix that is delimited
201 by a space from the part that is used for the dump file / option name.
202 E.g. When the pass name is "ud dce", the name used for dump file/options
203 is "dce".
205 TODO: describe the global variables set up by the pass manager,
206 and a brief description of how a new pass should use it.
207 I need to look at what info RTL passes use first@enddots{}
209 @node Tree SSA passes
210 @section Tree SSA passes
212 The following briefly describes the Tree optimization passes that are
213 run after gimplification and what source files they are located in.
215 @itemize @bullet
216 @item Remove useless statements
218 This pass is an extremely simple sweep across the gimple code in which
219 we identify obviously dead code and remove it.  Here we do things like
220 simplify @code{if} statements with constant conditions, remove
221 exception handling constructs surrounding code that obviously cannot
222 throw, remove lexical bindings that contain no variables, and other
223 assorted simplistic cleanups.  The idea is to get rid of the obvious
224 stuff quickly rather than wait until later when it's more work to get
225 rid of it.  This pass is located in @file{tree-cfg.c} and described by
226 @code{pass_remove_useless_stmts}.
228 @item Mudflap declaration registration
230 If mudflap (@pxref{Optimize Options,,-fmudflap -fmudflapth
231 -fmudflapir,gcc,Using the GNU Compiler Collection (GCC)}) is
232 enabled, we generate code to register some variable declarations with
233 the mudflap runtime.  Specifically, the runtime tracks the lifetimes of
234 those variable declarations that have their addresses taken, or whose
235 bounds are unknown at compile time (@code{extern}).  This pass generates
236 new exception handling constructs (@code{try}/@code{finally}), and so
237 must run before those are lowered.  In addition, the pass enqueues
238 declarations of static variables whose lifetimes extend to the entire
239 program.  The pass is located in @file{tree-mudflap.c} and is described
240 by @code{pass_mudflap_1}.
242 @item OpenMP lowering
244 If OpenMP generation (@option{-fopenmp}) is enabled, this pass lowers
245 OpenMP constructs into GIMPLE.
247 Lowering of OpenMP constructs involves creating replacement
248 expressions for local variables that have been mapped using data
249 sharing clauses, exposing the control flow of most synchronization
250 directives and adding region markers to facilitate the creation of the
251 control flow graph.  The pass is located in @file{omp-low.c} and is
252 described by @code{pass_lower_omp}.
254 @item OpenMP expansion
256 If OpenMP generation (@option{-fopenmp}) is enabled, this pass expands
257 parallel regions into their own functions to be invoked by the thread
258 library.  The pass is located in @file{omp-low.c} and is described by
259 @code{pass_expand_omp}.
261 @item Lower control flow
263 This pass flattens @code{if} statements (@code{COND_EXPR})
264 and moves lexical bindings (@code{BIND_EXPR}) out of line.  After
265 this pass, all @code{if} statements will have exactly two @code{goto}
266 statements in its @code{then} and @code{else} arms.  Lexical binding
267 information for each statement will be found in @code{TREE_BLOCK} rather
268 than being inferred from its position under a @code{BIND_EXPR}.  This
269 pass is found in @file{gimple-low.c} and is described by
270 @code{pass_lower_cf}.
272 @item Lower exception handling control flow
274 This pass decomposes high-level exception handling constructs
275 (@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
276 that explicitly represents the control flow involved.  After this
277 pass, @code{lookup_stmt_eh_region} will return a non-negative
278 number for any statement that may have EH control flow semantics;
279 examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
280 for exact semantics.  Exact control flow may be extracted from
281 @code{foreach_reachable_handler}.  The EH region nesting tree is defined
282 in @file{except.h} and built in @file{except.c}.  The lowering pass
283 itself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}.
285 @item Build the control flow graph
287 This pass decomposes a function into basic blocks and creates all of
288 the edges that connect them.  It is located in @file{tree-cfg.c} and
289 is described by @code{pass_build_cfg}.
291 @item Find all referenced variables
293 This pass walks the entire function and collects an array of all
294 variables referenced in the function, @code{referenced_vars}.  The
295 index at which a variable is found in the array is used as a UID
296 for the variable within this function.  This data is needed by the
297 SSA rewriting routines.  The pass is located in @file{tree-dfa.c}
298 and is described by @code{pass_referenced_vars}.
300 @item Enter static single assignment form
302 This pass rewrites the function such that it is in SSA form.  After
303 this pass, all @code{is_gimple_reg} variables will be referenced by
304 @code{SSA_NAME}, and all occurrences of other variables will be
305 annotated with @code{VDEFS} and @code{VUSES}; PHI nodes will have
306 been inserted as necessary for each basic block.  This pass is
307 located in @file{tree-ssa.c} and is described by @code{pass_build_ssa}.
309 @item Warn for uninitialized variables
311 This pass scans the function for uses of @code{SSA_NAME}s that
312 are fed by default definition.  For non-parameter variables, such
313 uses are uninitialized.  The pass is run twice, before and after
314 optimization (if turned on).  In the first pass we only warn for uses that are
315 positively uninitialized; in the second pass we warn for uses that
316 are possibly uninitialized.  The pass is located in @file{tree-ssa.c}
317 and is defined by @code{pass_early_warn_uninitialized} and
318 @code{pass_late_warn_uninitialized}.
320 @item Dead code elimination
322 This pass scans the function for statements without side effects whose
323 result is unused.  It does not do memory life analysis, so any value
324 that is stored in memory is considered used.  The pass is run multiple
325 times throughout the optimization process.  It is located in
326 @file{tree-ssa-dce.c} and is described by @code{pass_dce}.
328 @item Dominator optimizations
330 This pass performs trivial dominator-based copy and constant propagation,
331 expression simplification, and jump threading.  It is run multiple times
332 throughout the optimization process.  It is located in @file{tree-ssa-dom.c}
333 and is described by @code{pass_dominator}.
335 @item Forward propagation of single-use variables
337 This pass attempts to remove redundant computation by substituting
338 variables that are used once into the expression that uses them and
339 seeing if the result can be simplified.  It is located in
340 @file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}.
342 @item Copy Renaming
344 This pass attempts to change the name of compiler temporaries involved in
345 copy operations such that SSA->normal can coalesce the copy away.  When compiler
346 temporaries are copies of user variables, it also renames the compiler
347 temporary to the user variable resulting in better use of user symbols.  It is
348 located in @file{tree-ssa-copyrename.c} and is described by
349 @code{pass_copyrename}.
351 @item PHI node optimizations
353 This pass recognizes forms of PHI inputs that can be represented as
354 conditional expressions and rewrites them into straight line code.
355 It is located in @file{tree-ssa-phiopt.c} and is described by
356 @code{pass_phiopt}.
358 @item May-alias optimization
360 This pass performs a flow sensitive SSA-based points-to analysis.
361 The resulting may-alias, must-alias, and escape analysis information
362 is used to promote variables from in-memory addressable objects to
363 non-aliased variables that can be renamed into SSA form.  We also
364 update the @code{VDEF}/@code{VUSE} memory tags for non-renameable
365 aggregates so that we get fewer false kills.  The pass is located
366 in @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}.
368 Interprocedural points-to information is located in
369 @file{tree-ssa-structalias.c} and described by @code{pass_ipa_pta}.
371 @item Profiling
373 This pass rewrites the function in order to collect runtime block
374 and value profiling data.  Such data may be fed back into the compiler
375 on a subsequent run so as to allow optimization based on expected
376 execution frequencies.  The pass is located in @file{predict.c} and
377 is described by @code{pass_profile}.
379 @item Lower complex arithmetic
381 This pass rewrites complex arithmetic operations into their component
382 scalar arithmetic operations.  The pass is located in @file{tree-complex.c}
383 and is described by @code{pass_lower_complex}.
385 @item Scalar replacement of aggregates
387 This pass rewrites suitable non-aliased local aggregate variables into
388 a set of scalar variables.  The resulting scalar variables are
389 rewritten into SSA form, which allows subsequent optimization passes
390 to do a significantly better job with them.  The pass is located in
391 @file{tree-sra.c} and is described by @code{pass_sra}.
393 @item Dead store elimination
395 This pass eliminates stores to memory that are subsequently overwritten
396 by another store, without any intervening loads.  The pass is located
397 in @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
399 @item Tail recursion elimination
401 This pass transforms tail recursion into a loop.  It is located in
402 @file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
404 @item Forward store motion
406 This pass sinks stores and assignments down the flowgraph closer to their
407 use point.  The pass is located in @file{tree-ssa-sink.c} and is
408 described by @code{pass_sink_code}.
410 @item Partial redundancy elimination
412 This pass eliminates partially redundant computations, as well as
413 performing load motion.  The pass is located in @file{tree-ssa-pre.c}
414 and is described by @code{pass_pre}.
416 Just before partial redundancy elimination, if
417 @option{-funsafe-math-optimizations} is on, GCC tries to convert
418 divisions to multiplications by the reciprocal.  The pass is located
419 in @file{tree-ssa-math-opts.c} and is described by
420 @code{pass_cse_reciprocal}.
422 @item Full redundancy elimination
424 This is a simpler form of PRE that only eliminates redundancies that
425 occur on all paths.  It is located in @file{tree-ssa-pre.c} and
426 described by @code{pass_fre}.
428 @item Loop optimization
430 The main driver of the pass is placed in @file{tree-ssa-loop.c}
431 and described by @code{pass_loop}.
433 The optimizations performed by this pass are:
435 Loop invariant motion.  This pass moves only invariants that
436 would be hard to handle on RTL level (function calls, operations that expand to
437 nontrivial sequences of insns).  With @option{-funswitch-loops} it also moves
438 operands of conditions that are invariant out of the loop, so that we can use
439 just trivial invariantness analysis in loop unswitching.  The pass also includes
440 store motion.  The pass is implemented in @file{tree-ssa-loop-im.c}.
442 Canonical induction variable creation.  This pass creates a simple counter
443 for number of iterations of the loop and replaces the exit condition of the
444 loop using it, in case when a complicated analysis is necessary to determine
445 the number of iterations.  Later optimizations then may determine the number
446 easily.  The pass is implemented in @file{tree-ssa-loop-ivcanon.c}.
448 Induction variable optimizations.  This pass performs standard induction
449 variable optimizations, including strength reduction, induction variable
450 merging and induction variable elimination.  The pass is implemented in
451 @file{tree-ssa-loop-ivopts.c}.
453 Loop unswitching.  This pass moves the conditional jumps that are invariant
454 out of the loops.  To achieve this, a duplicate of the loop is created for
455 each possible outcome of conditional jump(s).  The pass is implemented in
456 @file{tree-ssa-loop-unswitch.c}.  This pass should eventually replace the
457 RTL level loop unswitching in @file{loop-unswitch.c}, but currently
458 the RTL level pass is not completely redundant yet due to deficiencies
459 in tree level alias analysis.
461 The optimizations also use various utility functions contained in
462 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
463 @file{cfgloopmanip.c}.
465 Vectorization.  This pass transforms loops to operate on vector types
466 instead of scalar types.  Data parallelism across loop iterations is exploited
467 to group data elements from consecutive iterations into a vector and operate
468 on them in parallel.  Depending on available target support the loop is
469 conceptually unrolled by a factor @code{VF} (vectorization factor), which is
470 the number of elements operated upon in parallel in each iteration, and the
471 @code{VF} copies of each scalar operation are fused to form a vector operation.
472 Additional loop transformations such as peeling and versioning may take place
473 to align the number of iterations, and to align the memory accesses in the
474 loop.
475 The pass is implemented in @file{tree-vectorizer.c} (the main driver),
476 @file{tree-vect-loop.c} and @file{tree-vect-loop-manip.c} (loop specific parts
477 and general loop utilities), @file{tree-vect-slp} (loop-aware SLP
478 functionality), @file{tree-vect-stmts.c} and @file{tree-vect-data-refs.c}.
479 Analysis of data references is in @file{tree-data-ref.c}.
481 SLP Vectorization.  This pass performs vectorization of straight-line code. The
482 pass is implemented in @file{tree-vectorizer.c} (the main driver),
483 @file{tree-vect-slp.c}, @file{tree-vect-stmts.c} and
484 @file{tree-vect-data-refs.c}.
486 Autoparallelization.  This pass splits the loop iteration space to run
487 into several threads.  The pass is implemented in @file{tree-parloops.c}.
489 Graphite is a loop transformation framework based on the polyhedral
490 model.  Graphite stands for Gimple Represented as Polyhedra.  The
491 internals of this infrastructure are documented in
492 @w{@uref{http://gcc.gnu.org/wiki/Graphite}}.  The passes working on
493 this representation are implemented in the various @file{graphite-*}
494 files.
496 @item Tree level if-conversion for vectorizer
498 This pass applies if-conversion to simple loops to help vectorizer.
499 We identify if convertible loops, if-convert statements and merge
500 basic blocks in one big block.  The idea is to present loop in such
501 form so that vectorizer can have one to one mapping between statements
502 and available vector operations.  This pass is located in
503 @file{tree-if-conv.c} and is described by @code{pass_if_conversion}.
505 @item Conditional constant propagation
507 This pass relaxes a lattice of values in order to identify those
508 that must be constant even in the presence of conditional branches.
509 The pass is located in @file{tree-ssa-ccp.c} and is described
510 by @code{pass_ccp}.
512 A related pass that works on memory loads and stores, and not just
513 register values, is located in @file{tree-ssa-ccp.c} and described by
514 @code{pass_store_ccp}.
516 @item Conditional copy propagation
518 This is similar to constant propagation but the lattice of values is
519 the ``copy-of'' relation.  It eliminates redundant copies from the
520 code.  The pass is located in @file{tree-ssa-copy.c} and described by
521 @code{pass_copy_prop}.
523 A related pass that works on memory copies, and not just register
524 copies, is located in @file{tree-ssa-copy.c} and described by
525 @code{pass_store_copy_prop}.
527 @item Value range propagation
529 This transformation is similar to constant propagation but
530 instead of propagating single constant values, it propagates
531 known value ranges.  The implementation is based on Patterson's
532 range propagation algorithm (Accurate Static Branch Prediction by
533 Value Range Propagation, J. R. C. Patterson, PLDI '95).  In
534 contrast to Patterson's algorithm, this implementation does not
535 propagate branch probabilities nor it uses more than a single
536 range per SSA name. This means that the current implementation
537 cannot be used for branch prediction (though adapting it would
538 not be difficult).  The pass is located in @file{tree-vrp.c} and is
539 described by @code{pass_vrp}.
541 @item Folding built-in functions
543 This pass simplifies built-in functions, as applicable, with constant
544 arguments or with inferable string lengths.  It is located in
545 @file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}.
547 @item Split critical edges
549 This pass identifies critical edges and inserts empty basic blocks
550 such that the edge is no longer critical.  The pass is located in
551 @file{tree-cfg.c} and is described by @code{pass_split_crit_edges}.
553 @item Control dependence dead code elimination
555 This pass is a stronger form of dead code elimination that can
556 eliminate unnecessary control flow statements.   It is located
557 in @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}.
559 @item Tail call elimination
561 This pass identifies function calls that may be rewritten into
562 jumps.  No code transformation is actually applied here, but the
563 data and control flow problem is solved.  The code transformation
564 requires target support, and so is delayed until RTL@.  In the
565 meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
566 The pass is located in @file{tree-tailcall.c} and is described by
567 @code{pass_tail_calls}.  The RTL transformation is handled by
568 @code{fixup_tail_calls} in @file{calls.c}.
570 @item Warn for function return without value
572 For non-void functions, this pass locates return statements that do
573 not specify a value and issues a warning.  Such a statement may have
574 been injected by falling off the end of the function.  This pass is
575 run last so that we have as much time as possible to prove that the
576 statement is not reachable.  It is located in @file{tree-cfg.c} and
577 is described by @code{pass_warn_function_return}.
579 @item Mudflap statement annotation
581 If mudflap is enabled, we rewrite some memory accesses with code to
582 validate that the memory access is correct.  In particular, expressions
583 involving pointer dereferences (@code{INDIRECT_REF}, @code{ARRAY_REF},
584 etc.) are replaced by code that checks the selected address range
585 against the mudflap runtime's database of valid regions.  This check
586 includes an inline lookup into a direct-mapped cache, based on
587 shift/mask operations of the pointer value, with a fallback function
588 call into the runtime.  The pass is located in @file{tree-mudflap.c} and
589 is described by @code{pass_mudflap_2}.
591 @item Leave static single assignment form
593 This pass rewrites the function such that it is in normal form.  At
594 the same time, we eliminate as many single-use temporaries as possible,
595 so the intermediate language is no longer GIMPLE, but GENERIC@.  The
596 pass is located in @file{tree-outof-ssa.c} and is described by
597 @code{pass_del_ssa}.
599 @item Merge PHI nodes that feed into one another
601 This is part of the CFG cleanup passes.  It attempts to join PHI nodes
602 from a forwarder CFG block into another block with PHI nodes.  The
603 pass is located in @file{tree-cfgcleanup.c} and is described by
604 @code{pass_merge_phi}.
606 @item Return value optimization
608 If a function always returns the same local variable, and that local
609 variable is an aggregate type, then the variable is replaced with the
610 return value for the function (i.e., the function's DECL_RESULT).  This
611 is equivalent to the C++ named return value optimization applied to
612 GIMPLE@.  The pass is located in @file{tree-nrv.c} and is described by
613 @code{pass_nrv}.
615 @item Return slot optimization
617 If a function returns a memory object and is called as @code{var =
618 foo()}, this pass tries to change the call so that the address of
619 @code{var} is sent to the caller to avoid an extra memory copy.  This
620 pass is located in @code{tree-nrv.c} and is described by
621 @code{pass_return_slot}.
623 @item Optimize calls to @code{__builtin_object_size}
625 This is a propagation pass similar to CCP that tries to remove calls
626 to @code{__builtin_object_size} when the size of the object can be
627 computed at compile-time.  This pass is located in
628 @file{tree-object-size.c} and is described by
629 @code{pass_object_sizes}.
631 @item Loop invariant motion
633 This pass removes expensive loop-invariant computations out of loops.
634 The pass is located in @file{tree-ssa-loop.c} and described by
635 @code{pass_lim}.
637 @item Loop nest optimizations
639 This is a family of loop transformations that works on loop nests.  It
640 includes loop interchange, scaling, skewing and reversal and they are
641 all geared to the optimization of data locality in array traversals
642 and the removal of dependencies that hamper optimizations such as loop
643 parallelization and vectorization.  The pass is located in
644 @file{tree-loop-linear.c} and described by
645 @code{pass_linear_transform}.
647 @item Removal of empty loops
649 This pass removes loops with no code in them.  The pass is located in
650 @file{tree-ssa-loop-ivcanon.c} and described by
651 @code{pass_empty_loop}.
653 @item Unrolling of small loops
655 This pass completely unrolls loops with few iterations.  The pass
656 is located in @file{tree-ssa-loop-ivcanon.c} and described by
657 @code{pass_complete_unroll}.
659 @item Predictive commoning
661 This pass makes the code reuse the computations from the previous
662 iterations of the loops, especially loads and stores to memory.
663 It does so by storing the values of these computations to a bank
664 of temporary variables that are rotated at the end of loop.  To avoid
665 the need for this rotation, the loop is then unrolled and the copies
666 of the loop body are rewritten to use the appropriate version of
667 the temporary variable.  This pass is located in @file{tree-predcom.c}
668 and described by @code{pass_predcom}.
670 @item Array prefetching
672 This pass issues prefetch instructions for array references inside
673 loops.  The pass is located in @file{tree-ssa-loop-prefetch.c} and
674 described by @code{pass_loop_prefetch}.
676 @item Reassociation
678 This pass rewrites arithmetic expressions to enable optimizations that
679 operate on them, like redundancy elimination and vectorization.  The
680 pass is located in @file{tree-ssa-reassoc.c} and described by
681 @code{pass_reassoc}.
683 @item Optimization of @code{stdarg} functions
685 This pass tries to avoid the saving of register arguments into the
686 stack on entry to @code{stdarg} functions.  If the function doesn't
687 use any @code{va_start} macros, no registers need to be saved.  If
688 @code{va_start} macros are used, the @code{va_list} variables don't
689 escape the function, it is only necessary to save registers that will
690 be used in @code{va_arg} macros.  For instance, if @code{va_arg} is
691 only used with integral types in the function, floating point
692 registers don't need to be saved.  This pass is located in
693 @code{tree-stdarg.c} and described by @code{pass_stdarg}.
695 @end itemize
697 @node RTL passes
698 @section RTL passes
700 The following briefly describes the RTL generation and optimization
701 passes that are run after the Tree optimization passes.
703 @itemize @bullet
704 @item RTL generation
706 @c Avoiding overfull is tricky here.
707 The source files for RTL generation include
708 @file{stmt.c},
709 @file{calls.c},
710 @file{expr.c},
711 @file{explow.c},
712 @file{expmed.c},
713 @file{function.c},
714 @file{optabs.c}
715 and @file{emit-rtl.c}.
716 Also, the file
717 @file{insn-emit.c}, generated from the machine description by the
718 program @code{genemit}, is used in this pass.  The header file
719 @file{expr.h} is used for communication within this pass.
721 @findex genflags
722 @findex gencodes
723 The header files @file{insn-flags.h} and @file{insn-codes.h},
724 generated from the machine description by the programs @code{genflags}
725 and @code{gencodes}, tell this pass which standard names are available
726 for use and which patterns correspond to them.
728 @item Generation of exception landing pads
730 This pass generates the glue that handles communication between the
731 exception handling library routines and the exception handlers within
732 the function.  Entry points in the function that are invoked by the
733 exception handling library are called @dfn{landing pads}.  The code
734 for this pass is located in @file{except.c}.
736 @item Control flow graph cleanup
738 This pass removes unreachable code, simplifies jumps to next, jumps to
739 jump, jumps across jumps, etc.  The pass is run multiple times.
740 For historical reasons, it is occasionally referred to as the ``jump
741 optimization pass''.  The bulk of the code for this pass is in
742 @file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c}
743 and @file{jump.c}.
745 @item Forward propagation of single-def values
747 This pass attempts to remove redundant computation by substituting
748 variables that come from a single definition, and
749 seeing if the result can be simplified.  It performs copy propagation
750 and addressing mode selection.  The pass is run twice, with values
751 being propagated into loops only on the second run.  The code is
752 located in @file{fwprop.c}.
754 @item Common subexpression elimination
756 This pass removes redundant computation within basic blocks, and
757 optimizes addressing modes based on cost.  The pass is run twice.
758 The code for this pass is located in @file{cse.c}.
760 @item Global common subexpression elimination
762 This pass performs two
763 different types of GCSE  depending on whether you are optimizing for
764 size or not (LCM based GCSE tends to increase code size for a gain in
765 speed, while Morel-Renvoise based GCSE does not).
766 When optimizing for size, GCSE is done using Morel-Renvoise Partial
767 Redundancy Elimination, with the exception that it does not try to move
768 invariants out of loops---that is left to  the loop optimization pass.
769 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
770 well as load motion.
771 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
772 done.  LCM is based on the work of Knoop, Ruthing, and Steffen.  LCM
773 based GCSE also does loop invariant code motion.  We also perform load
774 and store motion when optimizing for speed.
775 Regardless of which type of GCSE is used, the GCSE pass also performs
776 global constant and  copy propagation.
777 The source file for this pass is @file{gcse.c}, and the LCM routines
778 are in @file{lcm.c}.
780 @item Loop optimization
782 This pass performs several loop related optimizations.
783 The source files @file{cfgloopanal.c} and @file{cfgloopmanip.c} contain
784 generic loop analysis and manipulation code.  Initialization and finalization
785 of loop structures is handled by @file{loop-init.c}.
786 A loop invariant motion pass is implemented in @file{loop-invariant.c}.
787 Basic block level optimizations---unrolling, peeling and unswitching loops---
788 are implemented in @file{loop-unswitch.c} and @file{loop-unroll.c}.
789 Replacing of the exit condition of loops by special machine-dependent
790 instructions is handled by @file{loop-doloop.c}.
792 @item Jump bypassing
794 This pass is an aggressive form of GCSE that transforms the control
795 flow graph of a function by propagating constants into conditional
796 branch instructions.  The source file for this pass is @file{gcse.c}.
798 @item If conversion
800 This pass attempts to replace conditional branches and surrounding
801 assignments with arithmetic, boolean value producing comparison
802 instructions, and conditional move instructions.  In the very last
803 invocation after reload/LRA, it will generate predicated instructions
804 when supported by the target.  The code is located in @file{ifcvt.c}.
806 @item Web construction
808 This pass splits independent uses of each pseudo-register.  This can
809 improve effect of the other transformation, such as CSE or register
810 allocation.  The code for this pass is located in @file{web.c}.
812 @item Instruction combination
814 This pass attempts to combine groups of two or three instructions that
815 are related by data flow into single instructions.  It combines the
816 RTL expressions for the instructions by substitution, simplifies the
817 result using algebra, and then attempts to match the result against
818 the machine description.  The code is located in @file{combine.c}.
820 @item Register movement
822 This pass looks for cases where matching constraints would force an
823 instruction to need a reload, and this reload would be a
824 register-to-register move.  It then attempts to change the registers
825 used by the instruction to avoid the move instruction.  The code is
826 located in @file{regmove.c}.
828 @item Mode switching optimization
830 This pass looks for instructions that require the processor to be in a
831 specific ``mode'' and minimizes the number of mode changes required to
832 satisfy all users.  What these modes are, and what they apply to are
833 completely target-specific.  The code for this pass is located in
834 @file{mode-switching.c}.
836 @cindex modulo scheduling
837 @cindex sms, swing, software pipelining
838 @item Modulo scheduling
840 This pass looks at innermost loops and reorders their instructions
841 by overlapping different iterations.  Modulo scheduling is performed
842 immediately before instruction scheduling.  The code for this pass is
843 located in @file{modulo-sched.c}.
845 @item Instruction scheduling
847 This pass looks for instructions whose output will not be available by
848 the time that it is used in subsequent instructions.  Memory loads and
849 floating point instructions often have this behavior on RISC machines.
850 It re-orders instructions within a basic block to try to separate the
851 definition and use of items that otherwise would cause pipeline
852 stalls.  This pass is performed twice, before and after register
853 allocation.  The code for this pass is located in @file{haifa-sched.c},
854 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and
855 @file{sched-vis.c}.
857 @item Register allocation
859 These passes make sure that all occurrences of pseudo registers are
860 eliminated, either by allocating them to a hard register, replacing
861 them by an equivalent expression (e.g.@: a constant) or by placing
862 them on the stack.  This is done in several subpasses:
864 @itemize @bullet
865 @item
866 Register move optimizations.  This pass makes some simple RTL code
867 transformations which improve the subsequent register allocation.  The
868 source file is @file{regmove.c}.
870 @item
871 The integrated register allocator (@acronym{IRA}).  It is called
872 integrated because coalescing, register live range splitting, and hard
873 register preferencing are done on-the-fly during coloring.  It also
874 has better integration with the reload/LRA pass.  Pseudo-registers spilled
875 by the allocator or the reload/LRA have still a chance to get
876 hard-registers if the reload/LRA evicts some pseudo-registers from
877 hard-registers.  The allocator helps to choose better pseudos for
878 spilling based on their live ranges and to coalesce stack slots
879 allocated for the spilled pseudo-registers.  IRA is a regional
880 register allocator which is transformed into Chaitin-Briggs allocator
881 if there is one region.  By default, IRA chooses regions using
882 register pressure but the user can force it to use one region or
883 regions corresponding to all loops.
885 Source files of the allocator are @file{ira.c}, @file{ira-build.c},
886 @file{ira-costs.c}, @file{ira-conflicts.c}, @file{ira-color.c},
887 @file{ira-emit.c}, @file{ira-lives}, plus header files @file{ira.h}
888 and @file{ira-int.h} used for the communication between the allocator
889 and the rest of the compiler and between the IRA files.
891 @cindex reloading
892 @item
893 Reloading.  This pass renumbers pseudo registers with the hardware
894 registers numbers they were allocated.  Pseudo registers that did not
895 get hard registers are replaced with stack slots.  Then it finds
896 instructions that are invalid because a value has failed to end up in
897 a register, or has ended up in a register of the wrong kind.  It fixes
898 up these instructions by reloading the problematical values
899 temporarily into registers.  Additional instructions are generated to
900 do the copying.
902 The reload pass also optionally eliminates the frame pointer and inserts
903 instructions to save and restore call-clobbered registers around calls.
905 Source files are @file{reload.c} and @file{reload1.c}, plus the header
906 @file{reload.h} used for communication between them.
908 @cindex Local Register Allocator (LRA)
909 @item
910 This pass is a modern replacement of the reload pass.  Source files
911 are @file{lra.c}, @file{lra-assign.c}, @file{lra-coalesce.c},
912 @file{lra-constraints.c}, @file{lra-eliminations.c},
913 @file{lra-equivs.c}, @file{lra-lives.c}, @file{lra-saves.c},
914 @file{lra-spills.c}, the header @file{lra-int.h} used for
915 communication between them, and the header @file{lra.h} used for
916 communication between LRA and the rest of compiler.
918 Unlike the reload pass, intermediate LRA decisions are reflected in
919 RTL as much as possible.  This reduces the number of target-dependent
920 macros and hooks, leaving instruction constraints as the primary
921 source of control.
923 LRA is run on targets for which TARGET_LRA_P returns true.
924 @end itemize
926 @item Basic block reordering
928 This pass implements profile guided code positioning.  If profile
929 information is not available, various types of static analysis are
930 performed to make the predictions normally coming from the profile
931 feedback (IE execution frequency, branch probability, etc).  It is
932 implemented in the file @file{bb-reorder.c}, and the various
933 prediction routines are in @file{predict.c}.
935 @item Variable tracking
937 This pass computes where the variables are stored at each
938 position in code and generates notes describing the variable locations
939 to RTL code.  The location lists are then generated according to these
940 notes to debug information if the debugging information format supports
941 location lists.  The code is located in @file{var-tracking.c}.
943 @item Delayed branch scheduling
945 This optional pass attempts to find instructions that can go into the
946 delay slots of other instructions, usually jumps and calls.  The code
947 for this pass is located in @file{reorg.c}.
949 @item Branch shortening
951 On many RISC machines, branch instructions have a limited range.
952 Thus, longer sequences of instructions must be used for long branches.
953 In this pass, the compiler figures out what how far each instruction
954 will be from each other instruction, and therefore whether the usual
955 instructions, or the longer sequences, must be used for each branch.
956 The code for this pass is located in @file{final.c}.
958 @item Register-to-stack conversion
960 Conversion from usage of some hard registers to usage of a register
961 stack may be done at this point.  Currently, this is supported only
962 for the floating-point registers of the Intel 80387 coprocessor.  The
963 code for this pass is located in @file{reg-stack.c}.
965 @item Final
967 This pass outputs the assembler code for the function.  The source files
968 are @file{final.c} plus @file{insn-output.c}; the latter is generated
969 automatically from the machine description by the tool @file{genoutput}.
970 The header file @file{conditions.h} is used for communication between
971 these files.  If mudflap is enabled, the queue of deferred declarations
972 and any addressed constants (e.g., string literals) is processed by
973 @code{mudflap_finish_file} into a synthetic constructor function
974 containing calls into the mudflap runtime.
976 @item Debugging information output
978 This is run after final because it must output the stack slot offsets
979 for pseudo registers that did not get hard registers.  Source files
980 are @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for
981 SDB symbol table format, @file{dwarfout.c} for DWARF symbol table
982 format, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2
983 symbol table format, and @file{vmsdbgout.c} for VMS debug symbol table
984 format.
986 @end itemize