OSDN Git Service

bb6a3f0056d0c71dcbcac5391822a3be1a925d07
[pf3gnuchains/gcc-fork.git] / gcc / doc / passes.texi
1 @c markers: CROSSREF BUG TODO
2
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.
7
8 @node Passes
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
13
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
17 where near complete.
18
19 @menu
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.
25 @end menu
26
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 (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.
38
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 (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
51 be compiled.
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
56 data structures.
57
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.
61
62 TODO: Cgraph should control nested function lowering.  It would
63 only be invoked when it is certain that the outer-most function
64 is used.
65
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
73 function call.
74
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.
85
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}.
94
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".
102
103 The middle-end will, at its option, emit the function and data
104 definitions immediately or queue them for later processing.
105
106 @node Gimplification pass
107 @section Gimplification pass
108
109 @cindex gimplification
110 @cindex GIMPLE
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
115 section of code.
116
117 @cindex GENERIC
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.
123
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.
133
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}.
145
146 @node Pass manager
147 @section Pass manager
148
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.
153
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.
160
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.
167
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...
171
172 @node Tree-SSA passes
173 @section Tree-SSA passes
174
175 The following briefly describes the tree optimization passes that are
176 run after gimplification and what source files they are located in.
177
178 @itemize @bullet
179 @item Remove useless statements
180
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}.
190
191 @item Mudflap declaration registration
192
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}.
204
205 @item Lower control flow
206
207 This pass flattens @code{if} statements (@code{COND_EXPR}) and
208 and moves lexical bindings (@code{BIND_EXPR}) out of line.  After
209 this pass, all @code{if} statements will have exactly two @code{goto}
210 statements in its @code{then} and @code{else} arms.  Lexical binding
211 information for each statement will be found in @code{TREE_BLOCK} rather
212 than being inferred from its position under a @code{BIND_EXPR}.  This
213 pass is found in @file{gimple-low.c} and is described by
214 @code{pass_lower_cf}.
215
216 @item Lower exception handling control flow
217
218 This pass decomposes high-level exception handling constructs
219 (@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
220 that explicitly represents the control flow involved.  After this
221 pass, @code{lookup_stmt_eh_region} will return a non-negative
222 number for any statement that may have EH control flow semantics;
223 examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
224 for exact semantics.  Exact control flow may be extracted from
225 @code{foreach_reachable_handler}.  The EH region nesting tree is defined
226 in @file{except.h} and built in @file{except.c}.  The lowering pass
227 itself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}.
228
229 @item Build the control flow graph
230
231 This pass decomposes a function into basic blocks and creates all of
232 the edges that connect them.  It is located in @file{tree-cfg.c} and
233 is described by @code{pass_build_cfg}.
234
235 @item Find all referenced variables
236
237 This pass walks the entire function and collects an array of all
238 variables referenced in the function, @code{referenced_vars}.  The
239 index at which a variable is found in the array is used as a UID
240 for the variable within this function.  This data is needed by the
241 SSA rewriting routines.  The pass is located in @file{tree-dfa.c}
242 and is described by @code{pass_referenced_vars}.
243
244 @item Enter static single assignment form
245
246 This pass rewrites the function such that it is in SSA form.  After
247 this pass, all @code{is_gimple_reg} variables will be referenced by
248 @code{SSA_NAME}, and all occurrences of other variables will be
249 annotated with @code{VDEFS} and @code{VUSES}; phi nodes will have
250 been inserted as necessary for each basic block.  This pass is
251 located in @file{tree-ssa.c} and is described by @code{pass_build_ssa}.
252
253 @item Warn for uninitialized variables
254
255 This pass scans the function for uses of @code{SSA_NAME}s that
256 are fed by default definition.  For non-parameter variables, such
257 uses are uninitialized.  The pass is run twice, before and after
258 optimization.  In the first pass we only warn for uses that are
259 positively uninitialized; in the second pass we warn for uses that
260 are possibly uninitialized.  The pass is located in @file{tree-ssa.c}
261 and is defined by @code{pass_early_warn_uninitialized} and
262 @code{pass_late_warn_uninitialized}.
263
264 @item Dead code elimination
265
266 This pass scans the function for statements without side effects whose
267 result is unused.  It does not do memory life analysis, so any value
268 that is stored in memory is considered used.  The pass is run multiple
269 times throughout the optimization process.  It is located in
270 @file{tree-ssa-dce.c} and is described by @code{pass_dce}.
271
272 @item Dominator optimizations
273
274 This pass performs trivial dominator-based copy and constant propagation,
275 expression simplification, and jump threading.  It is run multiple times
276 throughout the optimization process.  It it located in @file{tree-ssa-dom.c}
277 and is described by @code{pass_dominator}.
278
279 @item Redundant phi elimination
280
281 This pass removes phi nodes for which all of the arguments are the same
282 value, excluding feedback.  Such degenerate forms are typically created
283 by removing unreachable code.  The pass is run multiple times throughout
284 the optimization process.  It is located in @file{tree-ssa.c} and is
285 described by @code{pass_redundant_phi}.o
286
287 @item Forward propagation of single-use variables
288
289 This pass attempts to remove redundant computation by substituting
290 variables that are used once into the expression that uses them and
291 seeing if the result can be simplified.  It is located in
292 @file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}.
293
294 @item Copy Renaming
295
296 This pass attempts to change the name of compiler temporaries involved in
297 copy operations such that SSA->normal can coalesce the copy away.  When compiler
298 temporaries are copies of user variables, it also renames the compiler
299 temporary to the user variable resulting in better use of user symbols.  It is
300 located in @file{tree-ssa-copyrename.c} and is described by
301 @code{pass_copyrename}.
302
303 @item PHI node optimizations
304
305 This pass recognizes forms of phi inputs that can be represented as
306 conditional expressions and rewrites them into straight line code.
307 It is located in @file{tree-ssa-phiopt.c} and is described by
308 @code{pass_phiopt}.
309
310 @item May-alias optimization
311
312 This pass performs a flow sensitive SSA-based points-to analysis.
313 The resulting may-alias, must-alias, and escape analysis information
314 is used to promote variables from in-memory addressable objects to
315 non-aliased variables that can be renamed into SSA form.  We also
316 update the @code{VDEF}/@code{VUSE} memory tags for non-renamable
317 aggregates so that we get fewer false kills.  The pass is located
318 in @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}.
319
320 @item Profiling
321
322 This pass rewrites the function in order to collect runtime block
323 and value profiling data.  Such data may be fed back into the compiler
324 on a subsequent run so as to allow optimization based on expected
325 execution frequencies.  The pass is located in @file{predict.c} and
326 is described by @code{pass_profile}.
327
328 @item Lower complex arithmetic
329
330 This pass rewrites complex arithmetic operations into their component
331 scalar arithmetic operations.  The pass is located in @file{tree-complex.c}
332 and is described by @code{pass_lower_complex}.
333
334 @item Scalar replacement of aggregates
335
336 This pass rewrites suitable non-aliased local aggregate variables into
337 a set of scalar variables.  The resulting scalar variables are
338 rewritten into SSA form, which allows subsequent optimization passes
339 to do a significantly better job with them.  The pass is located in
340 @file{tree-sra.c} and is described by @code{pass_sra}.
341
342 @item Dead store elimination
343
344 This pass eliminates stores to memory that are subsequently overwritten
345 by another store, without any intervening loads.  The pass is located
346 in @file{tree-ssa-dse.c} and is described by @code{pass_dse}.
347
348 @item Tail recursion elimination
349
350 This pass transforms tail recursion into a loop.  It is located in
351 @file{tree-tailcall.c} and is described by @code{pass_tail_recursion}.
352
353 @item Forward store motion
354
355 This pass sinks stores and assignments down the flowgraph closer to it's
356 use point.  The pass is located in @file{tree-ssa-sink.c} and is
357 described by @code{pass_sink_code}.
358
359 @item Partial redundancy elimination
360
361 This pass eliminates partially redundant computations, as well as
362 performing load motion.  The pass is located in @file{tree-ssa-pre.c}
363 and is described by @code{pass_pre}.
364
365 Just before partial redundancy elimination, if
366 @option{-funsafe-math-optimizations} is on, GCC tries to convert
367 divisions to multiplications by the reciprocal.  The pass is located
368 in @file{tree-ssa-math-opts.c} and is described by
369 @code{pass_cse_reciprocal}.
370
371 @item Loop optimization
372
373 The main driver of the pass is placed in @file{tree-ssa-loop.c}
374 and described by @code{pass_loop}.
375
376 The optimizations performed by this pass are:
377
378 Loop invariant motion.  This pass moves only invariants that
379 would be hard to handle on rtl level (function calls, operations that expand to
380 nontrivial sequences of insns).  With @option{-funswitch-loops} it also moves
381 operands of conditions that are invariant out of the loop, so that we can use
382 just trivial invariantness analysis in loop unswitching.  The pass also includes
383 store motion.  The pass is implemented in @file{tree-ssa-loop-im.c}.
384
385 Canonical induction variable creation.  This pass creates a simple counter
386 for number of iterations of the loop and replaces the exit condition of the
387 loop using it, in case when a complicated analysis is necessary to determine
388 the number of iterations.  Later optimizations then may determine the number
389 easily.  The pass is implemented in @file{tree-ssa-loop-ivcanon.c}.
390
391 Induction variable optimizations.  This pass performs standard induction
392 variable optimizations, including strength reduction, induction variable
393 merging and induction variable elimination.  The pass is implemented in
394 @file{tree-ssa-loop-ivopts.c}.
395
396 Loop unswitching.  This pass moves the conditional jumps that are invariant
397 out of the loops.  To achieve this, a duplicate of the loop is created for
398 each possible outcome of conditional jump(s).  The pass is implemented in
399 @file{tree-ssa-loop-unswitch.c}.  This pass should eventually replace the
400 rtl-level loop unswitching in @file{loop-unswitch.c}, but currently
401 the rtl-level pass is not completely redundant yet due to deficiencies
402 in tree level alias analysis.
403
404 The optimizations also use various utility functions contained in
405 @file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and
406 @file{cfgloopmanip.c}.
407
408 Vectorization.  This pass transforms loops to operate on vector types
409 instead of scalar types.  Data parallelism across loop iterations is exploited
410 to group data elements from consecutive iterations into a vector and operate 
411 on them in parallel.  Depending on available target support the loop is 
412 conceptually unrolled by a factor @code{VF} (vectorization factor), which is
413 the number of elements operated upon in parallel in each iteration, and the 
414 @code{VF} copies of each scalar operation are fused to form a vector operation.
415 Additional loop transformations such as peeling and versioning may take place
416 to align the number of iterations, and to align the memory accesses in the loop.
417 The pass is implemented in @file{tree-vectorizer.c} (the main driver and general
418 utilities), @file{tree-vect-analyze.c} and @file{tree-vect-transform.c}.
419 Analysis of data references is in @file{tree-data-ref.c}.
420
421 @item Tree level if-conversion for vectorizer
422
423 This pass applies if-conversion to simple loops to help vectorizer.
424 We identify if convertable loops, if-convert statements and merge
425 basic blocks in one big block.  The idea is to present loop in such
426 form so that vectorizer can have one to one mapping between statements
427 and available vector operations.  This patch re-introduces COND_EXPR
428 at GIMPLE level.  This pass is located in @file{tree-if-conv.c}.
429
430 @item Conditional constant propagation
431
432 This pass relaxes a lattice of values in order to identify those
433 that must be constant even in the presence of conditional branches.
434 The pass is located in @file{tree-ssa-ccp.c} and is described
435 by @code{pass_ccp}.
436
437 @item Folding builtin functions
438
439 This pass simplifies builtin functions, as applicable, with constant
440 arguments or with inferrable string lengths.  It is located in
441 @file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}.
442
443 @item Split critical edges
444
445 This pass identifies critical edges and inserts empty basic blocks
446 such that the edge is no longer critical.  The pass is located in
447 @file{tree-cfg.c} and is described by @code{pass_split_crit_edges}.
448
449 @item Partial redundancy elimination
450
451 This pass answers the question ``given a hypothetical temporary
452 variable, what expressions could we eliminate?''  It is located
453 in @file{tree-ssa-pre.c} and is described by @code{pass_pre}.
454
455 @item Control dependence dead code elimination
456
457 This pass is a stronger form of dead code elimination that can
458 eliminate unnecessary control flow statements.   It is located
459 in @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}.
460
461 @item Tail call elimination
462
463 This pass identifies function calls that may be rewritten into
464 jumps.  No code transformation is actually applied here, but the
465 data and control flow problem is solved.  The code transformation
466 requires target support, and so is delayed until RTL@.  In the
467 meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
468 The pass is located in @file{tree-tailcall.c} and is described by
469 @code{pass_tail_calls}.  The RTL transformation is handled by
470 @code{fixup_tail_calls} in @file{calls.c}.
471
472 @item Warn for function return without value
473
474 For non-void functions, this pass locates return statements that do
475 not specify a value and issues a warning.  Such a statement may have
476 been injected by falling off the end of the function.  This pass is
477 run last so that we have as much time as possible to prove that the
478 statement is not reachable.  It is located in @file{tree-cfg.c} and
479 is described by @code{pass_warn_function_return}.
480
481 @item Mudflap statement annotation
482
483 If mudflap is enabled, we rewrite some memory accesses with code to
484 validate that the memory access is correct.  In particular, expressions
485 involving pointer dereferences (@code{INDIRECT_REF}, @code{ARRAY_REF},
486 etc.) are replaced by code that checks the selected address range
487 against the mudflap runtime's database of valid regions.  This check
488 includes an inline lookup into a direct-mapped cache, based on
489 shift/mask operations of the pointer value, with a fallback function
490 call into the runtime.  The pass is located in @file{tree-mudflap.c} and
491 is described by @code{pass_mudflap_2}.
492
493 @item Leave static single assignment form
494
495 This pass rewrites the function such that it is in normal form.  At
496 the same time, we eliminate as many single-use temporaries as possible,
497 so the intermediate language is no longer GIMPLE, but GENERIC@.  The
498 pass is located in @file{tree-ssa.c} and is described by @code{pass_del_ssa}.
499 @end itemize
500
501 @node RTL passes
502 @section RTL passes
503
504 The following briefly describes the rtl generation and optimization
505 passes that are run after tree optimization.
506
507 @itemize @bullet
508 @item RTL generation
509
510 @c Avoiding overfull is tricky here.
511 The source files for RTL generation include
512 @file{stmt.c},
513 @file{calls.c},
514 @file{expr.c},
515 @file{explow.c},
516 @file{expmed.c},
517 @file{function.c},
518 @file{optabs.c}
519 and @file{emit-rtl.c}.
520 Also, the file
521 @file{insn-emit.c}, generated from the machine description by the
522 program @code{genemit}, is used in this pass.  The header file
523 @file{expr.h} is used for communication within this pass.
524
525 @findex genflags
526 @findex gencodes
527 The header files @file{insn-flags.h} and @file{insn-codes.h},
528 generated from the machine description by the programs @code{genflags}
529 and @code{gencodes}, tell this pass which standard names are available
530 for use and which patterns correspond to them.
531
532 @item Generate exception handling landing pads
533
534 This pass generates the glue that handles communication between the
535 exception handling library routines and the exception handlers within
536 the function.  Entry points in the function that are invoked by the
537 exception handling library are called @dfn{landing pads}.  The code
538 for this pass is located within @file{except.c}.
539
540 @item Cleanup control flow graph
541
542 This pass removes unreachable code, simplifies jumps to next, jumps to
543 jump, jumps across jumps, etc.  The pass is run multiple times.
544 For historical reasons, it is occasionally referred to as the ``jump
545 optimization pass''.  The bulk of the code for this pass is in
546 @file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c}
547 and @file{jump.c}.
548
549 @item Common subexpression elimination
550
551 This pass removes redundant computation within basic blocks, and
552 optimizes addressing modes based on cost.  The pass is run twice.
553 The source is located in @file{cse.c}.
554
555 @item Global common subexpression elimination.
556
557 This pass performs two
558 different types of GCSE  depending on whether you are optimizing for
559 size or not (LCM based GCSE tends to increase code size for a gain in
560 speed, while Morel-Renvoise based GCSE does not).
561 When optimizing for size, GCSE is done using Morel-Renvoise Partial
562 Redundancy Elimination, with the exception that it does not try to move
563 invariants out of loops---that is left to  the loop optimization pass.
564 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
565 well as load motion.
566 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
567 done.  LCM is based on the work of Knoop, Ruthing, and Steffen.  LCM
568 based GCSE also does loop invariant code motion.  We also perform load
569 and store motion when optimizing for speed.
570 Regardless of which type of GCSE is used, the GCSE pass also performs
571 global constant and  copy propagation.
572 The source file for this pass is @file{gcse.c}, and the LCM routines
573 are in @file{lcm.c}.
574
575 @item Loop optimization
576
577 This pass performs several loop related optimizations.
578 The source files @file{cfgloopanal.c} and @file{cfgloopmanip.c} contain
579 generic loop analysis and manipulation code.  Initialization and finalization
580 of loop structures is handled by @file{loop-init.c}.
581 A loop invariant motion pass is implemented in @file{loop-invariant.c}.
582 Basic block level optimizations---unrolling, peeling and unswitching loops---
583 are implemented in @file{loop-unswitch.c} and @file{loop-unroll.c}.
584 Replacing of the exit condition of loops by special machine-dependent
585 instructions is handled by @file{loop-doloop.c}.
586
587 @item Jump bypassing
588
589 This pass is an aggressive form of GCSE that transforms the control
590 flow graph of a function by propagating constants into conditional
591 branch instructions.  The source file for this pass is @file{gcse.c}.
592
593 @item If conversion
594
595 This pass attempts to replace conditional branches and surrounding
596 assignments with arithmetic, boolean value producing comparison
597 instructions, and conditional move instructions.  In the very last
598 invocation after reload, it will generate predicated instructions
599 when supported by the target.  The pass is located in @file{ifcvt.c}.
600
601 @item Web construction
602
603 This pass splits independent uses of each pseudo-register.  This can
604 improve effect of the other transformation, such as CSE or register
605 allocation.  Its source files are @file{web.c}.
606
607 @item Life analysis
608
609 This pass computes which pseudo-registers are live at each point in
610 the program, and makes the first instruction that uses a value point
611 at the instruction that computed the value.  It then deletes
612 computations whose results are never used, and combines memory
613 references with add or subtract instructions to make autoincrement or
614 autodecrement addressing.  The pass is located in @file{flow.c}.
615
616 @item Instruction combination
617
618 This pass attempts to combine groups of two or three instructions that
619 are related by data flow into single instructions.  It combines the
620 RTL expressions for the instructions by substitution, simplifies the
621 result using algebra, and then attempts to match the result against
622 the machine description.  The pass is located in @file{combine.c}.
623
624 @item Register movement
625
626 This pass looks for cases where matching constraints would force an
627 instruction to need a reload, and this reload would be a
628 register-to-register move.  It then attempts to change the registers
629 used by the instruction to avoid the move instruction.
630 The pass is located in @file{regmove.c}.
631
632 @item Optimize mode switching
633
634 This pass looks for instructions that require the processor to be in a
635 specific ``mode'' and minimizes the number of mode changes required to
636 satisfy all users.  What these modes are, and what they apply to are
637 completely target-specific.
638 The source is located in @file{mode-switching.c}.
639
640 @cindex modulo scheduling
641 @cindex sms, swing, software pipelining
642 @item Modulo scheduling
643
644 This pass looks at innermost loops and reorders their instructions
645 by overlapping different iterations.  Modulo scheduling is performed
646 immediately before instruction scheduling.
647 The pass is located in (@file{modulo-sched.c}).
648
649 @item Instruction scheduling
650
651 This pass looks for instructions whose output will not be available by
652 the time that it is used in subsequent instructions.  Memory loads and
653 floating point instructions often have this behavior on RISC machines.
654 It re-orders instructions within a basic block to try to separate the
655 definition and use of items that otherwise would cause pipeline
656 stalls.  This pass is performed twice, before and after register
657 allocation.  The pass is located in @file{haifa-sched.c},
658 @file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and
659 @file{sched-vis.c}.
660
661 @item Register allocation
662
663 These passes make sure that all occurrences of pseudo registers are
664 eliminated, either by allocating them to a hard register, replacing
665 them by an equivalent expression (e.g.@: a constant) or by placing
666 them on the stack.  This is done in several subpasses:
667
668 @itemize @bullet
669 @item
670 Register class preferencing.  The RTL code is scanned to find out
671 which register class is best for each pseudo register.  The source
672 file is @file{regclass.c}.
673
674 @item
675 Local register allocation.  This pass allocates hard registers to
676 pseudo registers that are used only within one basic block.  Because
677 the basic block is linear, it can use fast and powerful techniques to
678 do a decent job.  The source is located in @file{local-alloc.c}.
679
680 @item
681 Global register allocation.  This pass allocates hard registers for
682 the remaining pseudo registers (those whose life spans are not
683 contained in one basic block).  The pass is located in @file{global.c}.
684
685 @cindex reloading
686 @item
687 Reloading.  This pass renumbers pseudo registers with the hardware
688 registers numbers they were allocated.  Pseudo registers that did not
689 get hard registers are replaced with stack slots.  Then it finds
690 instructions that are invalid because a value has failed to end up in
691 a register, or has ended up in a register of the wrong kind.  It fixes
692 up these instructions by reloading the problematical values
693 temporarily into registers.  Additional instructions are generated to
694 do the copying.
695
696 The reload pass also optionally eliminates the frame pointer and inserts
697 instructions to save and restore call-clobbered registers around calls.
698
699 Source files are @file{reload.c} and @file{reload1.c}, plus the header
700 @file{reload.h} used for communication between them.
701 @end itemize
702
703 @item Basic block reordering
704
705 This pass implements profile guided code positioning.  If profile
706 information is not available, various types of static analysis are
707 performed to make the predictions normally coming from the profile
708 feedback (IE execution frequency, branch probability, etc).  It is
709 implemented in the file @file{bb-reorder.c}, and the various
710 prediction routines are in @file{predict.c}.
711
712 @item Variable tracking
713
714 This pass computes where the variables are stored at each
715 position in code and generates notes describing the variable locations
716 to RTL code.  The location lists are then generated according to these
717 notes to debug information if the debugging information format supports
718 location lists.
719
720 @item Delayed branch scheduling
721
722 This optional pass attempts to find instructions that can go into the
723 delay slots of other instructions, usually jumps and calls.  The
724 source file name is @file{reorg.c}.
725
726 @item Branch shortening
727
728 On many RISC machines, branch instructions have a limited range.
729 Thus, longer sequences of instructions must be used for long branches.
730 In this pass, the compiler figures out what how far each instruction
731 will be from each other instruction, and therefore whether the usual
732 instructions, or the longer sequences, must be used for each branch.
733
734 @item Register-to-stack conversion
735
736 Conversion from usage of some hard registers to usage of a register
737 stack may be done at this point.  Currently, this is supported only
738 for the floating-point registers of the Intel 80387 coprocessor.   The
739 source file name is @file{reg-stack.c}.
740
741 @item Final
742
743 This pass outputs the assembler code for the function.  The source files
744 are @file{final.c} plus @file{insn-output.c}; the latter is generated
745 automatically from the machine description by the tool @file{genoutput}.
746 The header file @file{conditions.h} is used for communication between
747 these files.  If mudflap is enabled, the queue of deferred declarations
748 and any addressed constants (e.g., string literals) is processed by
749 @code{mudflap_finish_file} into a synthetic constructor function
750 containing calls into the mudflap runtime.
751
752 @item Debugging information output
753
754 This is run after final because it must output the stack slot offsets
755 for pseudo registers that did not get hard registers.  Source files
756 are @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for
757 SDB symbol table format, @file{dwarfout.c} for DWARF symbol table
758 format, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2
759 symbol table format, and @file{vmsdbgout.c} for VMS debug symbol table
760 format.
761
762 @end itemize