Debian Codegraph @

gcc/doc/passes.texi

raw
1 @c markers: BUG TODO
2
3 @c Copyright (C) 1988-2025 Free Software Foundation, Inc.
4 @c This is part of the GCC manual.
5 @c For copying conditions, see the file gcc.texi.
6
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
12 @cindex pass dumps
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 * IPA passes:: Inter-procedural optimizations.
24 * Tree SSA passes:: Optimizations on a high-level representation.
25 * RTL passes:: Optimizations on a low-level representation.
26 * Optimization info:: Dumping optimization information from passes.
27 @end menu
28
29 @node Parsing pass
30 @section Parsing pass
31 @cindex GENERIC
32 @findex lang_hooks.parse_file
33 The language front end is invoked only once, via
34 @code{lang_hooks.parse_file}, to parse the entire input. The language
35 front end may use any intermediate language representation deemed
36 appropriate. The C front end uses GENERIC trees (@pxref{GENERIC}), plus
37 a double handful of language specific tree codes defined in
38 @file{c-common.def}. The Fortran front end uses a completely different
39 private representation.
40
41 @cindex GIMPLE
42 @cindex gimplification
43 @cindex gimplifier
44 @cindex language-independent intermediate representation
45 @cindex intermediate representation lowering
46 @cindex lowering, language-dependent intermediate representation
47 At some point the front end must translate the representation used in the
48 front end to a representation understood by the language-independent
49 portions of the compiler. Current practice takes one of two forms.
50 The C front end manually invokes the gimplifier (@pxref{GIMPLE}) on each function,
51 and uses the gimplifier callbacks to convert the language-specific tree
52 nodes directly to GIMPLE before passing the function off to be compiled.
53 The Fortran front end converts from a private representation to GENERIC,
54 which is later lowered to GIMPLE when the function is compiled. Which
55 route to choose probably depends on how well GENERIC (plus extensions)
56 can be made to match up with the source language and necessary parsing
57 data structures.
58
59 BUG: Gimplification must occur before nested function lowering,
60 and nested function lowering must be done by the front end before
61 passing the data off to cgraph.
62
63 TODO: Cgraph should control nested function lowering. It would
64 only be invoked when it is certain that the outer-most function
65 is used.
66
67 TODO: Cgraph needs a gimplify_function callback. It should be
68 invoked when (1) it is certain that the function is used, (2)
69 warning flags specified by the user require some amount of
70 compilation in order to honor, (3) the language indicates that
71 semantic analysis is not complete until gimplification occurs.
72 Hum@dots{} this sounds overly complicated. Perhaps we should just
73 have the front end gimplify always; in most cases it's only one
74 function call.
75
76 The front end needs to pass all function definitions and top level
77 declarations off to the middle-end so that they can be compiled and
78 emitted to the object file. For a simple procedural language, it is
79 usually most convenient to do this as each top level declaration or
80 definition is seen. There is also a distinction to be made between
81 generating functional code and generating complete debug information.
82 The only thing that is absolutely required for functional code is that
83 function and data @emph{definitions} be passed to the middle-end. For
84 complete debug information, function, data and type declarations
85 should all be passed as well.
86
87 @findex rest_of_decl_compilation
88 @findex rest_of_type_compilation
89 @findex cgraph_finalize_function
90 In any case, the front end needs each complete top-level function or
91 data declaration, and each data definition should be passed to
92 @code{rest_of_decl_compilation}. Each complete type definition should
93 be passed to @code{rest_of_type_compilation}. Each function definition
94 should be passed to @code{cgraph_finalize_function}.
95
96 TODO: I know rest_of_compilation currently has all sorts of
97 RTL generation semantics. I plan to move all code generation
98 bits (both Tree and RTL) to compile_function. Should we hide
99 cgraph from the front ends and move back to rest_of_compilation
100 as the official interface? Possibly we should rename all three
101 interfaces such that the names match in some meaningful way and
102 that is more descriptive than "rest_of".
103
104 The middle-end will, at its option, emit the function and data
105 definitions immediately or queue them for later processing.
106
107 @node Gimplification pass
108 @section Gimplification pass
109
110 @cindex gimplification
111 @cindex GIMPLE
112 @dfn{Gimplification} is a whimsical term for the process of converting
113 the intermediate representation of a function into the GIMPLE language
114 (@pxref{GIMPLE}). The term stuck, and so words like ``gimplification'',
115 ``gimplify'', ``gimplifier'' and the like are sprinkled throughout this
116 section of code.
117
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.cc}. 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.cc}, @file{tree-optimize.c}
150 and @file{tree-pass.h}.
151 It processes passes as described in @file{passes.def}.
152 Its job is to run all of the individual passes in the correct order,
153 and take care of standard bookkeeping that applies to every pass.
154
155 The theory of operation is that each pass defines a structure that
156 represents everything we need to know about that pass---when it
157 should be run, how it should be run, what intermediate language
158 form or on-the-side data structures it needs. We register the pass
159 to be run in some particular order, and the pass manager arranges
160 for everything to happen in the correct order.
161
162 The actuality doesn't completely live up to the theory at present.
163 Command-line switches and @code{timevar_id_t} enumerations must still
164 be defined elsewhere. The pass manager validates constraints but does
165 not attempt to (re-)generate data structures or lower intermediate
166 language form based on the requirements of the next pass. Nevertheless,
167 what is present is useful, and a far sight better than nothing at all.
168
169 Each pass should have a unique name.
170 Each pass may have its own dump file (for GCC debugging purposes).
171 Passes with a name starting with a star do not dump anything.
172 Sometimes passes are supposed to share a dump file / option name.
173 To still give these unique names, you can use a prefix that is delimited
174 by a space from the part that is used for the dump file / option name.
175 E.g. When the pass name is "ud dce", the name used for dump file/options
176 is "dce".
177
178 TODO: describe the global variables set up by the pass manager,
179 and a brief description of how a new pass should use it.
180 I need to look at what info RTL passes use first@enddots{}
181
182 @node IPA passes
183 @section Inter-procedural optimization passes
184 @cindex IPA passes
185 @cindex inter-procedural optimization passes
186
187 The inter-procedural optimization (IPA) passes use call graph
188 information to perform transformations across function boundaries.
189 IPA is a critical part of link-time optimization (LTO) and
190 whole-program (WHOPR) optimization, and these passes are structured
191 with the needs of LTO and WHOPR in mind by dividing their operations
192 into stages. For detailed discussion of the LTO/WHOPR IPA pass stages
193 and interfaces, see @ref{IPA}.
194
195 The following briefly describes the inter-procedural optimization (IPA)
196 passes, which are split into small IPA passes, regular IPA passes,
197 and late IPA passes, according to the LTO/WHOPR processing model.
198
199 @menu
200 * Small IPA passes::
201 * Regular IPA passes::
202 * Late IPA passes::
203 @end menu
204
205 @node Small IPA passes
206 @subsection Small IPA passes
207 @cindex small IPA passes
208 A small IPA pass is a pass derived from @code{simple_ipa_opt_pass}.
209 As described in @ref{IPA}, it does everything at once and
210 defines only the @emph{Execute} stage. During this
211 stage it accesses and modifies the function bodies.
212 No @code{generate_summary}, @code{read_summary}, or @code{write_summary}
213 hooks are defined.
214
215 @itemize @bullet
216 @item IPA free lang data
217
218 This pass frees resources that are used by the front end but are
219 not needed once it is done. It is located in @file{tree.cc} and is described by
220 @code{pass_ipa_free_lang_data}.
221
222 @item IPA function and variable visibility
223
224 This is a local function pass handling visibilities of all symbols. This
225 happens before LTO streaming, so @option{-fwhole-program} should be ignored
226 at this level. It is located in @file{ipa-visibility.cc} and is described by
227 @code{pass_ipa_function_and_variable_visibility}.
228
229 @item IPA remove symbols
230
231 This pass performs reachability analysis and reclaims all unreachable nodes.
232 It is located in @file{passes.cc} and is described by
233 @code{pass_ipa_remove_symbols}.
234
235 @item IPA OpenACC
236
237 This is a pass group for OpenACC processing. It is located in
238 @file{tree-ssa-loop.cc} and is described by @code{pass_ipa_oacc}.
239
240 @item IPA points-to analysis
241
242 This is a tree-based points-to analysis pass. The idea behind this analyzer
243 is to generate set constraints from the program, then solve the resulting
244 constraints in order to generate the points-to sets. It is located in
245 @file{tree-ssa-structalias.cc} and is described by @code{pass_ipa_pta}.
246
247 @item IPA OpenACC kernels
248
249 This is a pass group for processing OpenACC kernels regions. It is a
250 subpass of the IPA OpenACC pass group that runs on offloaded functions
251 containing OpenACC kernels loops. It is located in
252 @file{tree-ssa-loop.cc} and is described by
253 @code{pass_ipa_oacc_kernels}.
254
255 @item Target clone
256
257 This is a pass for parsing functions with multiple target attributes.
258 It is located in @file{multiple_target.cc} and is described by
259 @code{pass_target_clone}.
260
261 @item IPA auto profile
262
263 This pass uses AutoFDO profiling data to annotate the control flow graph.
264 It is located in @file{auto-profile.cc} and is described by
265 @code{pass_ipa_auto_profile}.
266
267 @item IPA tree profile
268
269 This pass does profiling for all functions in the call graph.
270 It calculates branch
271 probabilities and basic block execution counts. It is located
272 in @file{tree-profile.cc} and is described by @code{pass_ipa_tree_profile}.
273
274 @item IPA free function summary
275
276 This pass is a small IPA pass when argument @code{small_p} is true.
277 It releases inline function summaries and call summaries.
278 It is located in @file{ipa-fnsummary.cc} and is described by
279 @code{pass_ipa_free_free_fn_summary}.
280
281 @item IPA increase alignment
282
283 This pass increases the alignment of global arrays to improve
284 vectorization. It is located in @file{tree-vectorizer.cc}
285 and is described by @code{pass_ipa_increase_alignment}.
286
287 @item IPA transactional memory
288
289 This pass is for transactional memory support.
290 It is located in @file{trans-mem.cc} and is described by
291 @code{pass_ipa_tm}.
292
293 @item IPA lower emulated TLS
294
295 This pass lowers thread-local storage (TLS) operations
296 to emulation functions provided by libgcc.
297 It is located in @file{tree-emutls.cc} and is described by
298 @code{pass_ipa_lower_emutls}.
299
300 @end itemize
301
302 @node Regular IPA passes
303 @subsection Regular IPA passes
304 @cindex regular IPA passes
305
306 A regular IPA pass is a pass derived from @code{ipa_opt_pass_d} that
307 is executed in WHOPR compilation. Regular IPA passes may have summary
308 hooks implemented in any of the LGEN, WPA or LTRANS stages (@pxref{IPA}).
309
310 @itemize @bullet
311 @item IPA whole program visibility
312
313 This pass performs various optimizations involving symbol visibility
314 with @option{-fwhole-program}, including symbol privatization,
315 discovering local functions, and dismantling comdat groups. It is
316 located in @file{ipa-visibility.cc} and is described by
317 @code{pass_ipa_whole_program_visibility}.
318
319 @item IPA profile
320
321 The IPA profile pass propagates profiling frequencies across the call
322 graph. It is located in @file{ipa-profile.cc} and is described by
323 @code{pass_ipa_profile}.
324
325 @item IPA identical code folding
326
327 This is the inter-procedural identical code folding pass.
328 The goal of this transformation is to discover functions
329 and read-only variables that have exactly the same semantics. It is
330 located in @file{ipa-icf.cc} and is described by @code{pass_ipa_icf}.
331
332 @item IPA devirtualization
333
334 This pass performs speculative devirtualization based on the type
335 inheritance graph. When a polymorphic call has only one likely target
336 in the unit, it is turned into a speculative call. It is located in
337 @file{ipa-devirt.cc} and is described by @code{pass_ipa_devirt}.
338
339 @item IPA constant propagation
340
341 The goal of this pass is to discover functions that are always invoked
342 with some arguments with the same known constant values and to modify
343 the functions accordingly. It can also do partial specialization and
344 type-based devirtualization. It is located in @file{ipa-cp.cc} and is
345 described by @code{pass_ipa_cp}.
346
347 @item IPA scalar replacement of aggregates
348
349 This pass can replace an aggregate parameter with a set of other parameters
350 representing part of the original, turning those passed by reference
351 into new ones which pass the value directly. It also removes unused
352 function return values and unused function parameters. This pass is
353 located in @file{ipa-sra.cc} and is described by @code{pass_ipa_sra}.
354
355 @item IPA constructor/destructor merge
356
357 This pass merges multiple constructors and destructors for static
358 objects into single functions. It's only run at LTO time unless the
359 target doesn't support constructors and destructors natively. The
360 pass is located in @file{ipa.cc} and is described by
361 @code{pass_ipa_cdtor_merge}.
362
363 @item IPA function summary
364
365 This pass provides function analysis for inter-procedural passes.
366 It collects estimates of function body size, execution time, and frame
367 size for each function. It also estimates information about function
368 calls: call statement size, time and how often the parameters change
369 for each call. It is located in @file{ipa-fnsummary.cc} and is
370 described by @code{pass_ipa_fn_summary}.
371
372 @item IPA inline
373
374 The IPA inline pass handles function inlining with whole-program
375 knowledge. Small functions that are candidates for inlining are
376 ordered in increasing badness, bounded by unit growth parameters.
377 Unreachable functions are removed from the call graph. Functions called
378 once and not exported from the unit are inlined. This pass is located in
379 @file{ipa-inline.cc} and is described by @code{pass_ipa_inline}.
380
381 @item IPA pure/const analysis
382
383 This pass marks functions as being either const (@code{TREE_READONLY}) or
384 pure (@code{DECL_PURE_P}). The per-function information is produced
385 by @code{pure_const_generate_summary}, then the global information is computed
386 by performing a transitive closure over the call graph. It is located in
387 @file{ipa-pure-const.cc} and is described by @code{pass_ipa_pure_const}.
388
389 @item IPA free function summary
390
391 This pass is a regular IPA pass when argument @code{small_p} is false.
392 It releases inline function summaries and call summaries.
393 It is located in @file{ipa-fnsummary.cc} and is described by
394 @code{pass_ipa_free_fn_summary}.
395
396 @item IPA reference
397
398 This pass gathers information about how variables whose scope is
399 confined to the compilation unit are used. It is located in
400 @file{ipa-reference.cc} and is described by @code{pass_ipa_reference}.
401
402 @item IPA single use
403
404 This pass checks whether variables are used by a single function.
405 It is located in @file{ipa.cc} and is described by
406 @code{pass_ipa_single_use}.
407
408 @item IPA comdats
409
410 This pass looks for static symbols that are used exclusively
411 within one comdat group, and moves them into that comdat group. It is
412 located in @file{ipa-comdats.cc} and is described by
413 @code{pass_ipa_comdats}.
414
415 @end itemize
416
417 @node Late IPA passes
418 @subsection Late IPA passes
419 @cindex late IPA passes
420
421 Late IPA passes are simple IPA passes executed after
422 the regular passes. In WHOPR mode the passes are executed after
423 partitioning and thus see just parts of the compiled unit.
424
425 @itemize @bullet
426 @item Materialize all clones
427
428 Once all functions from compilation unit are in memory, produce all clones
429 and update all calls. It is located in @file{ipa.cc} and is described by
430 @code{pass_materialize_all_clones}.
431
432 @item IPA points-to analysis
433
434 Points-to analysis; this is the same as the points-to-analysis pass
435 run with the small IPA passes (@pxref{Small IPA passes}).
436
437 @item OpenMP simd clone
438
439 This is the OpenMP constructs' SIMD clone pass. It creates the appropriate
440 SIMD clones for functions tagged as elemental SIMD functions.
441 It is located in @file{omp-simd-clone.cc} and is described by
442 @code{pass_omp_simd_clone}.
443
444 @end itemize
445
446 @node Tree SSA passes
447 @section Tree SSA passes
448
449 The following briefly describes the Tree optimization passes that are
450 run after gimplification and what source files they are located in.
451
452 @itemize @bullet
453 @item OpenMP lowering
454
455 If OpenMP generation (@option{-fopenmp}) is enabled, this pass lowers
456 OpenMP constructs into GIMPLE.
457
458 Lowering of OpenMP constructs involves creating replacement
459 expressions for local variables that have been mapped using data
460 sharing clauses, exposing the control flow of most synchronization
461 directives and adding region markers to facilitate the creation of the
462 control flow graph. The pass is located in @file{omp-low.cc} and is
463 described by @code{pass_lower_omp}.
464
465 @item OpenMP expansion
466
467 If OpenMP generation (@option{-fopenmp}) is enabled, this pass expands
468 parallel regions into their own functions to be invoked by the thread
469 library. The pass is located in @file{omp-low.cc} and is described by
470 @code{pass_expand_omp}.
471
472 @item Lower control flow
473
474 This pass flattens @code{if} statements (@code{COND_EXPR})
475 and moves lexical bindings (@code{BIND_EXPR}) out of line. After
476 this pass, all @code{if} statements will have exactly two @code{goto}
477 statements in its @code{then} and @code{else} arms. Lexical binding
478 information for each statement will be found in @code{TREE_BLOCK} rather
479 than being inferred from its position under a @code{BIND_EXPR}. This
480 pass is found in @file{gimple-low.cc} and is described by
481 @code{pass_lower_cf}.
482
483 @item Lower exception handling control flow
484
485 This pass decomposes high-level exception handling constructs
486 (@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form
487 that explicitly represents the control flow involved. After this
488 pass, @code{lookup_stmt_eh_region} will return a non-negative
489 number for any statement that may have EH control flow semantics;
490 examine @code{tree_can_throw_internal} or @code{tree_can_throw_external}
491 for exact semantics. Exact control flow may be extracted from
492 @code{foreach_reachable_handler}. The EH region nesting tree is defined
493 in @file{except.h} and built in @file{except.cc}. The lowering pass
494 itself is in @file{tree-eh.cc} and is described by @code{pass_lower_eh}.
495
496 @item Build the control flow graph
497
498 This pass decomposes a function into basic blocks and creates all of
499 the edges that connect them. It is located in @file{tree-cfg.cc} and
500 is described by @code{pass_build_cfg}.
501
502 @item Enter static single assignment form
503
504 This pass rewrites the function such that it is in SSA form. After
505 this pass, all @code{is_gimple_reg} variables will be referenced by
506 @code{SSA_NAME}, and all occurrences of other variables will be
507 annotated with @code{VDEFS} and @code{VUSES}; PHI nodes will have
508 been inserted as necessary for each basic block. This pass is
509 located in @file{tree-into-ssa.cc} and is described by @code{pass_build_ssa}.
510
511 @item Warn for uninitialized variables
512
513 This pass scans the function for uses of @code{SSA_NAME}s that
514 are fed by default definition. For non-parameter variables, such
515 uses are uninitialized. The pass is run twice, before and after
516 optimization (if turned on). In the first pass we only warn for uses that are
517 positively uninitialized; in the second pass we warn for uses that
518 are possibly uninitialized. The pass is located in @file{tree-ssa-uninit.cc}
519 and is defined by @code{pass_early_warn_uninitialized} and
520 @code{pass_late_warn_uninitialized}.
521
522 @item Dead code elimination
523
524 This pass scans the function for statements without side effects whose
525 result is unused. It does not do memory lifetime analysis, so any value
526 that is stored in memory is considered used. The pass is run multiple
527 times throughout the optimization process. It is located in
528 @file{tree-ssa-dce.cc} and is described by @code{pass_dce}.
529
530 @item Dominator optimizations
531
532 This pass performs trivial dominator-based copy and constant propagation,
533 expression simplification, and jump threading. It is run multiple times
534 throughout the optimization process. It is located in @file{tree-ssa-dom.cc}
535 and is described by @code{pass_dominator}.
536
537 @item Forward propagation of single-use variables
538
539 This pass attempts to remove redundant computation by substituting
540 variables that are used once into the expression that uses them and
541 seeing if the result can be simplified. It is located in
542 @file{tree-ssa-forwprop.cc} and is described by @code{pass_forwprop}.
543
544 @item PHI node optimizations
545
546 This pass recognizes forms of PHI inputs that can be represented as
547 conditional expressions and rewrites them into straight line code.
548 It is located in @file{tree-ssa-phiopt.cc} and is described by
549 @code{pass_phiopt}.
550
551 @item May-alias optimization
552
553 This pass performs a flow sensitive SSA-based points-to analysis.
554 The resulting may-alias, must-alias, and escape analysis information
555 is used to promote variables from in-memory addressable objects to
556 non-aliased variables that can be renamed into SSA form. We also
557 update the @code{VDEF}/@code{VUSE} memory tags for non-renameable
558 aggregates so that we get fewer false kills. The pass is located
559 in @file{tree-ssa-structalias.cc} and is described by @code{pass_may_alias}.
560
561 Interprocedural points-to information is described by @code{pass_ipa_pta}.
562
563 @item Profiling
564
565 This pass instruments the function in order to collect runtime block
566 and value profiling data. Such data may be fed back into the compiler
567 on a subsequent run so as to allow optimization based on expected
568 execution frequencies. The pass is located in @file{tree-profile.cc} and
569 is described by @code{pass_ipa_tree_profile}.
570
571 @item Static profile estimation
572
573 This pass implements series of heuristics to guess propababilities
574 of branches. The resulting predictions are turned into edge profile
575 by propagating branches across the control flow graphs.
576 The pass is located in @file{tree-profile.cc} and is described by
577 @code{pass_profile}.
578
579 @item Lower complex arithmetic
580
581 This pass rewrites complex arithmetic operations into their component
582 scalar arithmetic operations. The pass is located in @file{tree-complex.cc}
583 and is described by @code{pass_lower_complex}.
584
585 @item Scalar replacement of aggregates
586
587 This pass rewrites suitable non-aliased local aggregate variables into
588 a set of scalar variables. The resulting scalar variables are
589 rewritten into SSA form, which allows subsequent optimization passes
590 to do a significantly better job with them. The pass is located in
591 @file{tree-sra.cc} and is described by @code{pass_sra}.
592
593 @item Dead store elimination
594
595 This pass eliminates stores to memory that are subsequently overwritten
596 by another store, without any intervening loads. The pass is located
597 in @file{tree-ssa-dse.cc} and is described by @code{pass_dse}.
598
599 @item Tail recursion elimination
600
601 This pass transforms tail recursion into a loop. It is located in
602 @file{tree-tailcall.cc} and is described by @code{pass_tail_recursion}.
603
604 @item Forward store motion
605
606 This pass sinks stores and assignments down the flowgraph closer to their
607 use point. The pass is located in @file{tree-ssa-sink.cc} and is
608 described by @code{pass_sink_code}.
609
610 @item Partial redundancy elimination
611
612 This pass eliminates partially redundant computations, as well as
613 performing load motion. The pass is located in @file{tree-ssa-pre.cc}
614 and is described by @code{pass_pre}.
615
616 @item CSE of reciprocals
617
618 If @option{-funsafe-math-optimizations} is on, GCC tries to convert
619 divisions to multiplications by the reciprocal. The pass is located
620 in @file{tree-ssa-math-opts.cc} and is described by
621 @code{pass_cse_reciprocal}.
622
623 @item Full redundancy elimination
624
625 This is a simpler form of PRE that only eliminates redundancies that
626 occur on all paths. It is located in @file{tree-ssa-pre.cc} and
627 described by @code{pass_fre}.
628
629 @item Loop optimization
630
631 The main driver of the pass is placed in @file{tree-ssa-loop.cc}
632 and described by @code{pass_loop}.
633
634 The optimizations performed by this pass are:
635
636 Loop invariant motion. This pass moves only invariants that
637 would be hard to handle on RTL level (function calls, operations that expand to
638 nontrivial sequences of insns). With @option{-funswitch-loops} it also moves
639 operands of conditions that are invariant out of the loop, so that we can use
640 just trivial invariantness analysis in loop unswitching. The pass also includes
641 store motion. The pass is implemented in @file{tree-ssa-loop-im.cc}.
642
643 Canonical induction variable creation. This pass creates a simple counter
644 for number of iterations of the loop and replaces the exit condition of the
645 loop using it, in case when a complicated analysis is necessary to determine
646 the number of iterations. Later optimizations then may determine the number
647 easily. The pass is implemented in @file{tree-ssa-loop-ivcanon.cc}.
648
649 Induction variable optimizations. This pass performs standard induction
650 variable optimizations, including strength reduction, induction variable
651 merging and induction variable elimination. The pass is implemented in
652 @file{tree-ssa-loop-ivopts.cc}.
653
654 Loop unswitching. This pass moves the conditional jumps that are invariant
655 out of the loops. To achieve this, a duplicate of the loop is created for
656 each possible outcome of conditional jump(s). The pass is implemented in
657 @file{tree-ssa-loop-unswitch.cc}.
658
659 Loop splitting. If a loop contains a conditional statement that is
660 always true for one part of the iteration space and false for the other
661 this pass splits the loop into two, one dealing with one side the other
662 only with the other, thereby removing one inner-loop conditional. The
663 pass is implemented in @file{tree-ssa-loop-split.cc}.
664
665 The optimizations also use various utility functions contained in
666 @file{tree-ssa-loop-manip.cc}, @file{cfgloop.cc}, @file{cfgloopanal.cc} and
667 @file{cfgloopmanip.cc}.
668
669 Vectorization. This pass transforms loops to operate on vector types
670 instead of scalar types. Data parallelism across loop iterations is exploited
671 to group data elements from consecutive iterations into a vector and operate
672 on them in parallel. Depending on available target support the loop is
673 conceptually unrolled by a factor @code{VF} (vectorization factor), which is
674 the number of elements operated upon in parallel in each iteration, and the
675 @code{VF} copies of each scalar operation are fused to form a vector operation.
676 Additional loop transformations such as peeling and versioning may take place
677 to align the number of iterations, and to align the memory accesses in the
678 loop.
679 The pass is implemented in @file{tree-vectorizer.cc} (the main driver),
680 @file{tree-vect-loop.cc} and @file{tree-vect-loop-manip.cc} (loop specific parts
681 and general loop utilities), @file{tree-vect-slp} (loop-aware SLP
682 functionality), @file{tree-vect-stmts.cc}, @file{tree-vect-data-refs.cc} and
683 @file{tree-vect-slp-patterns.cc} containing the SLP pattern matcher.
684 Analysis of data references is in @file{tree-data-ref.cc}.
685
686 SLP Vectorization. This pass performs vectorization of straight-line code. The
687 pass is implemented in @file{tree-vectorizer.cc} (the main driver),
688 @file{tree-vect-slp.cc}, @file{tree-vect-stmts.cc} and
689 @file{tree-vect-data-refs.cc}.
690
691 Autoparallelization. This pass splits the loop iteration space to run
692 into several threads. The pass is implemented in @file{tree-parloops.cc}.
693
694 Graphite is a loop transformation framework based on the polyhedral
695 model. Graphite stands for Gimple Represented as Polyhedra. The
696 internals of this infrastructure are documented in
697 @w{@uref{https://gcc.gnu.org/wiki/Graphite}}. The passes working on
698 this representation are implemented in the various @file{graphite-*}
699 files.
700
701 @item Tree level if-conversion for vectorizer
702
703 This pass applies if-conversion to simple loops to help vectorizer.
704 We identify if convertible loops, if-convert statements and merge
705 basic blocks in one big block. The idea is to present loop in such
706 form so that vectorizer can have one to one mapping between statements
707 and available vector operations. This pass is located in
708 @file{tree-if-conv.cc} and is described by @code{pass_if_conversion}.
709
710 @item Conditional constant propagation
711
712 This pass relaxes a lattice of values in order to identify those
713 that must be constant even in the presence of conditional branches.
714 The pass is located in @file{tree-ssa-ccp.cc} and is described
715 by @code{pass_ccp}.
716
717 @item Conditional copy propagation
718
719 This is similar to constant propagation but the lattice of values is
720 the ``copy-of'' relation. It eliminates redundant copies from the
721 code. The pass is located in @file{tree-ssa-copy.cc} and described by
722 @code{pass_copy_prop}.
723
724 @item Value range propagation
725
726 This transformation is similar to constant propagation but
727 instead of propagating single constant values, it propagates
728 known value ranges. The implementation is based on Patterson's
729 range propagation algorithm (Accurate Static Branch Prediction by
730 Value Range Propagation, J. R. C. Patterson, PLDI '95). In
731 contrast to Patterson's algorithm, this implementation does not
732 propagate branch probabilities nor it uses more than a single
733 range per SSA name. This means that the current implementation
734 cannot be used for branch prediction (though adapting it would
735 not be difficult). The pass is located in @file{tree-vrp.cc} and is
736 described by @code{pass_vrp}.
737
738 @item Folding built-in functions
739
740 This pass simplifies built-in functions, as applicable, with constant
741 arguments or with inferable string lengths. It is located in
742 @file{tree-ssa-ccp.cc} and is described by @code{pass_fold_builtins}.
743
744 @item Split critical edges
745
746 This pass identifies critical edges and inserts empty basic blocks
747 such that the edge is no longer critical. The pass is located in
748 @file{tree-cfg.cc} and is described by @code{pass_split_crit_edges}.
749
750 @item Control dependence dead code elimination
751
752 This pass is a stronger form of dead code elimination that can
753 eliminate unnecessary control flow statements. It is located
754 in @file{tree-ssa-dce.cc} and is described by @code{pass_cd_dce}.
755
756 @item Tail call elimination
757
758 This pass identifies function calls that may be rewritten into
759 jumps. No code transformation is actually applied here, but the
760 data and control flow problem is solved. The code transformation
761 requires target support, and so is delayed until RTL@. In the
762 meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility.
763 The pass is located in @file{tree-tailcall.cc} and is described by
764 @code{pass_tail_calls}. The RTL transformation is handled by
765 @code{fixup_tail_calls} in @file{calls.cc}.
766
767 @item Warn for function return without value
768
769 For non-void functions, this pass locates return statements that do
770 not specify a value and issues a warning. Such a statement may have
771 been injected by falling off the end of the function. This pass is
772 run last so that we have as much time as possible to prove that the
773 statement is not reachable. It is located in @file{tree-cfg.cc} and
774 is described by @code{pass_warn_function_return}.
775
776 @item Merge PHI nodes that feed into one another
777
778 This is part of the CFG cleanup passes. It attempts to join PHI nodes
779 from a forwarder CFG block into another block with PHI nodes. The
780 pass is located in @file{tree-cfgcleanup.cc} and is described by
781 @code{pass_merge_phi}.
782
783 @item Return value optimization
784
785 If a function always returns the same local variable, and that local
786 variable is an aggregate type, then the variable is replaced with the
787 return value for the function (i.e., the function's DECL_RESULT). This
788 is equivalent to the C++ named return value optimization applied to
789 GIMPLE@. The pass is located in @file{tree-nrv.cc} and is described by
790 @code{pass_nrv}.
791
792 @item Return slot optimization
793
794 If a function returns a memory object and is called as @code{var =
795 foo()}, this pass tries to change the call so that the address of
796 @code{var} is sent to the caller to avoid an extra memory copy. This
797 pass is located in @code{tree-nrv.cc} and is described by
798 @code{pass_return_slot}.
799
800 @item Optimize calls to @code{__builtin_object_size} or
801 @code{__builtin_dynamic_object_size}
802
803 This is a propagation pass similar to CCP that tries to remove calls to
804 @code{__builtin_object_size} when the upper or lower bound for the size
805 of the object can be computed at compile-time. It also tries to replace
806 calls to @code{__builtin_dynamic_object_size} with an expression that
807 evaluates the upper or lower bound for the size of the object. This
808 pass is located in @file{tree-object-size.cc} and is described by
809 @code{pass_object_sizes}.
810
811 @item Loop invariant motion
812
813 This pass removes expensive loop-invariant computations out of loops.
814 The pass is located in @file{tree-ssa-loop.cc} and described by
815 @code{pass_lim}.
816
817 @item Loop nest optimizations
818
819 This is a family of loop transformations that works on loop nests. It
820 includes loop interchange, scaling, skewing and reversal and they are
821 all geared to the optimization of data locality in array traversals
822 and the removal of dependencies that hamper optimizations such as loop
823 parallelization and vectorization. The pass is located in
824 the @file{graphile-*.cc} files and described by
825 @code{pass_graphite}.
826
827 @item Unrolling of small loops
828
829 This pass completely unrolls loops with few iterations. The pass
830 is located in @file{tree-ssa-loop-ivcanon.cc} and described by
831 @code{pass_complete_unroll}.
832
833 @item Predictive commoning
834
835 This pass makes the code reuse the computations from the previous
836 iterations of the loops, especially loads and stores to memory.
837 It does so by storing the values of these computations to a bank
838 of temporary variables that are rotated at the end of loop. To avoid
839 the need for this rotation, the loop is then unrolled and the copies
840 of the loop body are rewritten to use the appropriate version of
841 the temporary variable. This pass is located in @file{tree-predcom.cc}
842 and described by @code{pass_predcom}.
843
844 @item Array prefetching
845
846 This pass issues prefetch instructions for array references inside
847 loops. The pass is located in @file{tree-ssa-loop-prefetch.cc} and
848 described by @code{pass_loop_prefetch}.
849
850 @item Reassociation
851
852 This pass rewrites arithmetic expressions to enable optimizations that
853 operate on them, like redundancy elimination and vectorization. The
854 pass is located in @file{tree-ssa-reassoc.cc} and described by
855 @code{pass_reassoc}.
856
857 @item Optimization of @code{stdarg} functions
858
859 This pass tries to avoid the saving of register arguments into the
860 stack on entry to @code{stdarg} functions. If the function doesn't
861 use any @code{va_start} macros, no registers need to be saved. If
862 @code{va_start} macros are used, the @code{va_list} variables don't
863 escape the function, it is only necessary to save registers that will
864 be used in @code{va_arg} macros. For instance, if @code{va_arg} is
865 only used with integral types in the function, floating point
866 registers don't need to be saved. This pass is located in
867 @code{tree-stdarg.cc} and described by @code{pass_stdarg}.
868
869 @end itemize
870
871 @node RTL passes
872 @section RTL passes
873
874 The following briefly describes the RTL generation and optimization
875 passes that are run after the Tree optimization passes.
876
877 @itemize @bullet
878 @item RTL generation
879
880 @c Avoiding overfull is tricky here.
881 The source files for RTL generation include
882 @file{stmt.cc},
883 @file{calls.cc},
884 @file{expr.cc},
885 @file{explow.cc},
886 @file{expmed.cc},
887 @file{function.cc},
888 @file{optabs.cc}
889 and @file{emit-rtl.cc}.
890 Also, the file
891 @file{insn-emit.cc}, generated from the machine description by the
892 program @code{genemit}, is used in this pass. The header file
893 @file{expr.h} is used for communication within this pass.
894
895 @findex genflags
896 @findex gencodes
897 The header files @file{insn-flags.h} and @file{insn-codes.h},
898 generated from the machine description by the programs @code{genflags}
899 and @code{gencodes}, tell this pass which standard names are available
900 for use and which patterns correspond to them.
901
902 @item Generation of exception landing pads
903
904 This pass generates the glue that handles communication between the
905 exception handling library routines and the exception handlers within
906 the function. Entry points in the function that are invoked by the
907 exception handling library are called @dfn{landing pads}. The code
908 for this pass is located in @file{except.cc}.
909
910 @item Control flow graph cleanup
911
912 This pass removes unreachable code, simplifies jumps to next, jumps to
913 jump, jumps across jumps, etc. The pass is run multiple times.
914 For historical reasons, it is occasionally referred to as the ``jump
915 optimization pass''. The bulk of the code for this pass is in
916 @file{cfgcleanup.cc}, and there are support routines in @file{cfgrtl.cc}
917 and @file{jump.cc}.
918
919 @item Forward propagation of single-def values
920
921 This pass attempts to remove redundant computation by substituting
922 variables that come from a single definition, and
923 seeing if the result can be simplified. It performs copy propagation
924 and addressing mode selection. The pass is run twice, with values
925 being propagated into loops only on the second run. The code is
926 located in @file{fwprop.cc}.
927
928 @item Store forwarding avoidance
929
930 This pass attempts to reduce the overhead of store to load forwarding.
931 It detects when a load reads from one or more previous smaller stores and
932 then rearranges them so that the stores are done after the load. The loaded
933 value is adjusted with a series of bit insert instructions so that it stays
934 the same. The code is located in @file{avoid-store-forwarding.cc}.
935
936 @item Common subexpression elimination
937
938 This pass removes redundant computation within basic blocks, and
939 optimizes addressing modes based on cost. The pass is run twice.
940 The code for this pass is located in @file{cse.cc}.
941
942 @item Global common subexpression elimination
943
944 This pass performs two
945 different types of GCSE depending on whether you are optimizing for
946 size or not (LCM based GCSE tends to increase code size for a gain in
947 speed, while Morel-Renvoise based GCSE does not).
948 When optimizing for size, GCSE is done using Morel-Renvoise Partial
949 Redundancy Elimination, with the exception that it does not try to move
950 invariants out of loops---that is left to the loop optimization pass.
951 If MR PRE GCSE is done, code hoisting (aka unification) is also done, as
952 well as load motion.
953 If you are optimizing for speed, LCM (lazy code motion) based GCSE is
954 done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM
955 based GCSE also does loop invariant code motion. We also perform load
956 and store motion when optimizing for speed.
957 Regardless of which type of GCSE is used, the GCSE pass also performs
958 global constant and copy propagation.
959 The source file for this pass is @file{gcse.cc}, and the LCM routines
960 are in @file{lcm.cc}.
961
962 A third version of this pass is run on some targets to optimise assignments to
963 specific hard registers. This can be used in cases where a register has a
964 single purpose, such as specifying a mode as an extra input for specific
965 instructions (@pxref{mode switching optimization} for another way of handling
966 instruction modes).
967
968 @item Loop optimization
969
970 This pass performs several loop related optimizations.
971 The source files @file{cfgloopanal.cc} and @file{cfgloopmanip.cc} contain
972 generic loop analysis and manipulation code. Initialization and finalization
973 of loop structures is handled by @file{loop-init.cc}.
974 A loop invariant motion pass is implemented in @file{loop-invariant.cc}.
975 Basic block level optimizations---unrolling, and peeling loops---
976 are implemented in @file{loop-unroll.cc}.
977 Replacing of the exit condition of loops by special machine-dependent
978 instructions is handled by @file{loop-doloop.cc}.
979
980 @item Jump bypassing
981
982 This pass is an aggressive form of GCSE that transforms the control
983 flow graph of a function by propagating constants into conditional
984 branch instructions. The source file for this pass is @file{gcse.cc}.
985
986 @item If conversion
987
988 This pass attempts to replace conditional branches and surrounding
989 assignments with arithmetic, boolean value producing comparison
990 instructions, and conditional move instructions. In the very last
991 invocation after reload/LRA, it will generate predicated instructions
992 when supported by the target. The code is located in @file{ifcvt.cc}.
993
994 @item Web construction
995
996 This pass splits independent uses of each pseudo-register. This can
997 improve effect of the other transformation, such as CSE or register
998 allocation. The code for this pass is located in @file{web.cc}.
999
1000 @item Instruction combination
1001
1002 This pass attempts to combine groups of two or three instructions that
1003 are related by data flow into single instructions. It combines the
1004 RTL expressions for the instructions by substitution, simplifies the
1005 result using algebra, and then attempts to match the result against
1006 the machine description. The code is located in @file{combine.cc}.
1007
1008 @item Late instruction combination
1009
1010 This pass attempts to do further instruction combination, on top of
1011 that performed by @file{combine.cc}. Its current purpose is to
1012 substitute definitions into all uses simultaneously, so that the
1013 definition can be removed. This differs from the forward propagation
1014 pass, whose purpose is instead to simplify individual uses on the
1015 assumption that the definition will remain. It differs from
1016 @file{combine.cc} in that there is no hard-coded limit on the number
1017 of instructions that can be combined at once. It also differs from
1018 @file{combine.cc} in that it can move instructions, where necessary.
1019
1020 However, the pass is not in principle limited to this form of
1021 combination. It is intended to be a home for other, future
1022 combination approaches as well.
1023
1024 The pass runs twice, once before register allocation and once after
1025 register allocation. The code is located in @file{late-combine.cc}.
1026
1027 @anchor{mode switching optimization}
1028 @item Mode switching optimization
1029
1030 This pass looks for instructions that require the processor to be in a
1031 specific ``mode'' and minimizes the number of mode changes required to
1032 satisfy all users. What these modes are, and what they apply to are
1033 completely target-specific. The code for this pass is located in
1034 @file{mode-switching.cc}.
1035
1036 @cindex modulo scheduling
1037 @cindex sms, swing, software pipelining
1038 @item Modulo scheduling
1039
1040 This pass looks at innermost loops and reorders their instructions
1041 by overlapping different iterations. Modulo scheduling is performed
1042 immediately before instruction scheduling. The code for this pass is
1043 located in @file{modulo-sched.cc}.
1044
1045 @item Instruction scheduling
1046
1047 This pass looks for instructions whose output will not be available by
1048 the time that it is used in subsequent instructions. Memory loads and
1049 floating point instructions often have this behavior on RISC machines.
1050 It re-orders instructions within a basic block to try to separate the
1051 definition and use of items that otherwise would cause pipeline
1052 stalls. This pass is performed twice, before and after register
1053 allocation. The code for this pass is located in @file{haifa-sched.cc},
1054 @file{sched-deps.cc}, @file{sched-ebb.cc}, @file{sched-rgn.cc} and
1055 @file{sched-vis.c}.
1056
1057 @item Register allocation
1058
1059 These passes make sure that all occurrences of pseudo registers are
1060 eliminated, either by allocating them to a hard register, replacing
1061 them by an equivalent expression (e.g.@: a constant) or by placing
1062 them on the stack. This is done in several subpasses:
1063
1064 @itemize @bullet
1065 @item
1066 The integrated register allocator (@acronym{IRA}). It is called
1067 integrated because coalescing, register live range splitting, and hard
1068 register preferencing are done on-the-fly during coloring. It also
1069 has better integration with the reload/LRA pass. Pseudo-registers spilled
1070 by the allocator or the reload/LRA have still a chance to get
1071 hard-registers if the reload/LRA evicts some pseudo-registers from
1072 hard-registers. The allocator helps to choose better pseudos for
1073 spilling based on their live ranges and to coalesce stack slots
1074 allocated for the spilled pseudo-registers. IRA is a regional
1075 register allocator which is transformed into Chaitin-Briggs allocator
1076 if there is one region. By default, IRA chooses regions using
1077 register pressure but the user can force it to use one region or
1078 regions corresponding to all loops.
1079
1080 Source files of the allocator are @file{ira.cc}, @file{ira-build.cc},
1081 @file{ira-costs.cc}, @file{ira-conflicts.cc}, @file{ira-color.cc},
1082 @file{ira-emit.cc}, @file{ira-lives}, plus header files @file{ira.h}
1083 and @file{ira-int.h} used for the communication between the allocator
1084 and the rest of the compiler and between the IRA files.
1085
1086 @cindex reloading
1087 @item
1088 Reloading. This pass renumbers pseudo registers with the hardware
1089 registers numbers they were allocated. Pseudo registers that did not
1090 get hard registers are replaced with stack slots. Then it finds
1091 instructions that are invalid because a value has failed to end up in
1092 a register, or has ended up in a register of the wrong kind. It fixes
1093 up these instructions by reloading the problematical values
1094 temporarily into registers. Additional instructions are generated to
1095 do the copying.
1096
1097 The reload pass also optionally eliminates the frame pointer and inserts
1098 instructions to save and restore call-clobbered registers around calls.
1099
1100 Source files are @file{reload.cc} and @file{reload1.cc}, plus the header
1101 @file{reload.h} used for communication between them.
1102
1103 @cindex Local Register Allocator (LRA)
1104 @item
1105 This pass is a modern replacement of the reload pass. Source files
1106 are @file{lra.cc}, @file{lra-assign.c}, @file{lra-coalesce.cc},
1107 @file{lra-constraints.cc}, @file{lra-eliminations.cc},
1108 @file{lra-lives.cc}, @file{lra-remat.cc}, @file{lra-spills.cc}, the
1109 header @file{lra-int.h} used for communication between them, and the
1110 header @file{lra.h} used for communication between LRA and the rest of
1111 compiler.
1112
1113 Unlike the reload pass, intermediate LRA decisions are reflected in
1114 RTL as much as possible. This reduces the number of target-dependent
1115 macros and hooks, leaving instruction constraints as the primary
1116 source of control.
1117
1118 LRA is run on targets for which TARGET_LRA_P returns true.
1119 @end itemize
1120
1121 @item Basic block reordering
1122
1123 This pass implements profile guided code positioning. If profile
1124 information is not available, various types of static analysis are
1125 performed to make the predictions normally coming from the profile
1126 feedback (IE execution frequency, branch probability, etc). It is
1127 implemented in the file @file{bb-reorder.cc}, and the various
1128 prediction routines are in @file{predict.cc}.
1129
1130 @item Variable tracking
1131
1132 This pass computes where the variables are stored at each
1133 position in code and generates notes describing the variable locations
1134 to RTL code. The location lists are then generated according to these
1135 notes to debug information if the debugging information format supports
1136 location lists. The code is located in @file{var-tracking.cc}.
1137
1138 @item Delayed branch scheduling
1139
1140 This optional pass attempts to find instructions that can go into the
1141 delay slots of other instructions, usually jumps and calls. The code
1142 for this pass is located in @file{reorg.cc}.
1143
1144 @item Branch shortening
1145
1146 On many RISC machines, branch instructions have a limited range.
1147 Thus, longer sequences of instructions must be used for long branches.
1148 In this pass, the compiler figures out what how far each instruction
1149 will be from each other instruction, and therefore whether the usual
1150 instructions, or the longer sequences, must be used for each branch.
1151 The code for this pass is located in @file{final.cc}.
1152
1153 @item Register-to-stack conversion
1154
1155 Conversion from usage of some hard registers to usage of a register
1156 stack may be done at this point. Currently, this is supported only
1157 for the floating-point registers of the Intel 80387 coprocessor. The
1158 code for this pass is located in @file{reg-stack.cc}.
1159
1160 @item Final
1161
1162 This pass outputs the assembler code for the function. The source files
1163 are @file{final.cc} plus @file{insn-output.cc}; the latter is generated
1164 automatically from the machine description by the tool @file{genoutput}.
1165 The header file @file{conditions.h} is used for communication between
1166 these files.
1167
1168 @item Debugging information output
1169
1170 This is run after final because it must output the stack slot offsets
1171 for pseudo registers that did not get hard registers. Source files
1172 are @file{dwarfout.c} for
1173 DWARF symbol table format, files @file{dwarf2out.cc} and @file{dwarf2asm.cc}
1174 for DWARF2 symbol table format, and @file{vmsdbgout.cc} for VMS debug
1175 symbol table format.
1176
1177 @end itemize
1178
1179 @node Optimization info
1180 @section Optimization info
1181 @include optinfo.texi