| 1 |
@c markers: BUG TODO |
| 2 |
|
| 3 |
@c Copyright (C) 1988-2023 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 Remove useless statements |
| 454 |
|
| 455 |
This pass is an extremely simple sweep across the gimple code in which |
| 456 |
we identify obviously dead code and remove it. Here we do things like |
| 457 |
simplify @code{if} statements with constant conditions, remove |
| 458 |
exception handling constructs surrounding code that obviously cannot |
| 459 |
throw, remove lexical bindings that contain no variables, and other |
| 460 |
assorted simplistic cleanups. The idea is to get rid of the obvious |
| 461 |
stuff quickly rather than wait until later when it's more work to get |
| 462 |
rid of it. This pass is located in @file{tree-cfg.cc} and described by |
| 463 |
@code{pass_remove_useless_stmts}. |
| 464 |
|
| 465 |
@item OpenMP lowering |
| 466 |
|
| 467 |
If OpenMP generation (@option{-fopenmp}) is enabled, this pass lowers |
| 468 |
OpenMP constructs into GIMPLE. |
| 469 |
|
| 470 |
Lowering of OpenMP constructs involves creating replacement |
| 471 |
expressions for local variables that have been mapped using data |
| 472 |
sharing clauses, exposing the control flow of most synchronization |
| 473 |
directives and adding region markers to facilitate the creation of the |
| 474 |
control flow graph. The pass is located in @file{omp-low.cc} and is |
| 475 |
described by @code{pass_lower_omp}. |
| 476 |
|
| 477 |
@item OpenMP expansion |
| 478 |
|
| 479 |
If OpenMP generation (@option{-fopenmp}) is enabled, this pass expands |
| 480 |
parallel regions into their own functions to be invoked by the thread |
| 481 |
library. The pass is located in @file{omp-low.cc} and is described by |
| 482 |
@code{pass_expand_omp}. |
| 483 |
|
| 484 |
@item Lower control flow |
| 485 |
|
| 486 |
This pass flattens @code{if} statements (@code{COND_EXPR}) |
| 487 |
and moves lexical bindings (@code{BIND_EXPR}) out of line. After |
| 488 |
this pass, all @code{if} statements will have exactly two @code{goto} |
| 489 |
statements in its @code{then} and @code{else} arms. Lexical binding |
| 490 |
information for each statement will be found in @code{TREE_BLOCK} rather |
| 491 |
than being inferred from its position under a @code{BIND_EXPR}. This |
| 492 |
pass is found in @file{gimple-low.cc} and is described by |
| 493 |
@code{pass_lower_cf}. |
| 494 |
|
| 495 |
@item Lower exception handling control flow |
| 496 |
|
| 497 |
This pass decomposes high-level exception handling constructs |
| 498 |
(@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form |
| 499 |
that explicitly represents the control flow involved. After this |
| 500 |
pass, @code{lookup_stmt_eh_region} will return a non-negative |
| 501 |
number for any statement that may have EH control flow semantics; |
| 502 |
examine @code{tree_can_throw_internal} or @code{tree_can_throw_external} |
| 503 |
for exact semantics. Exact control flow may be extracted from |
| 504 |
@code{foreach_reachable_handler}. The EH region nesting tree is defined |
| 505 |
in @file{except.h} and built in @file{except.cc}. The lowering pass |
| 506 |
itself is in @file{tree-eh.cc} and is described by @code{pass_lower_eh}. |
| 507 |
|
| 508 |
@item Build the control flow graph |
| 509 |
|
| 510 |
This pass decomposes a function into basic blocks and creates all of |
| 511 |
the edges that connect them. It is located in @file{tree-cfg.cc} and |
| 512 |
is described by @code{pass_build_cfg}. |
| 513 |
|
| 514 |
@item Find all referenced variables |
| 515 |
|
| 516 |
This pass walks the entire function and collects an array of all |
| 517 |
variables referenced in the function, @code{referenced_vars}. The |
| 518 |
index at which a variable is found in the array is used as a UID |
| 519 |
for the variable within this function. This data is needed by the |
| 520 |
SSA rewriting routines. The pass is located in @file{tree-dfa.cc} |
| 521 |
and is described by @code{pass_referenced_vars}. |
| 522 |
|
| 523 |
@item Enter static single assignment form |
| 524 |
|
| 525 |
This pass rewrites the function such that it is in SSA form. After |
| 526 |
this pass, all @code{is_gimple_reg} variables will be referenced by |
| 527 |
@code{SSA_NAME}, and all occurrences of other variables will be |
| 528 |
annotated with @code{VDEFS} and @code{VUSES}; PHI nodes will have |
| 529 |
been inserted as necessary for each basic block. This pass is |
| 530 |
located in @file{tree-ssa.cc} and is described by @code{pass_build_ssa}. |
| 531 |
|
| 532 |
@item Warn for uninitialized variables |
| 533 |
|
| 534 |
This pass scans the function for uses of @code{SSA_NAME}s that |
| 535 |
are fed by default definition. For non-parameter variables, such |
| 536 |
uses are uninitialized. The pass is run twice, before and after |
| 537 |
optimization (if turned on). In the first pass we only warn for uses that are |
| 538 |
positively uninitialized; in the second pass we warn for uses that |
| 539 |
are possibly uninitialized. The pass is located in @file{tree-ssa.cc} |
| 540 |
and is defined by @code{pass_early_warn_uninitialized} and |
| 541 |
@code{pass_late_warn_uninitialized}. |
| 542 |
|
| 543 |
@item Dead code elimination |
| 544 |
|
| 545 |
This pass scans the function for statements without side effects whose |
| 546 |
result is unused. It does not do memory life analysis, so any value |
| 547 |
that is stored in memory is considered used. The pass is run multiple |
| 548 |
times throughout the optimization process. It is located in |
| 549 |
@file{tree-ssa-dce.cc} and is described by @code{pass_dce}. |
| 550 |
|
| 551 |
@item Dominator optimizations |
| 552 |
|
| 553 |
This pass performs trivial dominator-based copy and constant propagation, |
| 554 |
expression simplification, and jump threading. It is run multiple times |
| 555 |
throughout the optimization process. It is located in @file{tree-ssa-dom.cc} |
| 556 |
and is described by @code{pass_dominator}. |
| 557 |
|
| 558 |
@item Forward propagation of single-use variables |
| 559 |
|
| 560 |
This pass attempts to remove redundant computation by substituting |
| 561 |
variables that are used once into the expression that uses them and |
| 562 |
seeing if the result can be simplified. It is located in |
| 563 |
@file{tree-ssa-forwprop.cc} and is described by @code{pass_forwprop}. |
| 564 |
|
| 565 |
@item Copy Renaming |
| 566 |
|
| 567 |
This pass attempts to change the name of compiler temporaries involved in |
| 568 |
copy operations such that SSA->normal can coalesce the copy away. When compiler |
| 569 |
temporaries are copies of user variables, it also renames the compiler |
| 570 |
temporary to the user variable resulting in better use of user symbols. It is |
| 571 |
located in @file{tree-ssa-copyrename.c} and is described by |
| 572 |
@code{pass_copyrename}. |
| 573 |
|
| 574 |
@item PHI node optimizations |
| 575 |
|
| 576 |
This pass recognizes forms of PHI inputs that can be represented as |
| 577 |
conditional expressions and rewrites them into straight line code. |
| 578 |
It is located in @file{tree-ssa-phiopt.cc} and is described by |
| 579 |
@code{pass_phiopt}. |
| 580 |
|
| 581 |
@item May-alias optimization |
| 582 |
|
| 583 |
This pass performs a flow sensitive SSA-based points-to analysis. |
| 584 |
The resulting may-alias, must-alias, and escape analysis information |
| 585 |
is used to promote variables from in-memory addressable objects to |
| 586 |
non-aliased variables that can be renamed into SSA form. We also |
| 587 |
update the @code{VDEF}/@code{VUSE} memory tags for non-renameable |
| 588 |
aggregates so that we get fewer false kills. The pass is located |
| 589 |
in @file{tree-ssa-alias.cc} and is described by @code{pass_may_alias}. |
| 590 |
|
| 591 |
Interprocedural points-to information is located in |
| 592 |
@file{tree-ssa-structalias.cc} and described by @code{pass_ipa_pta}. |
| 593 |
|
| 594 |
@item Profiling |
| 595 |
|
| 596 |
This pass instruments the function in order to collect runtime block |
| 597 |
and value profiling data. Such data may be fed back into the compiler |
| 598 |
on a subsequent run so as to allow optimization based on expected |
| 599 |
execution frequencies. The pass is located in @file{tree-profile.cc} and |
| 600 |
is described by @code{pass_ipa_tree_profile}. |
| 601 |
|
| 602 |
@item Static profile estimation |
| 603 |
|
| 604 |
This pass implements series of heuristics to guess propababilities |
| 605 |
of branches. The resulting predictions are turned into edge profile |
| 606 |
by propagating branches across the control flow graphs. |
| 607 |
The pass is located in @file{tree-profile.cc} and is described by |
| 608 |
@code{pass_profile}. |
| 609 |
|
| 610 |
@item Lower complex arithmetic |
| 611 |
|
| 612 |
This pass rewrites complex arithmetic operations into their component |
| 613 |
scalar arithmetic operations. The pass is located in @file{tree-complex.cc} |
| 614 |
and is described by @code{pass_lower_complex}. |
| 615 |
|
| 616 |
@item Scalar replacement of aggregates |
| 617 |
|
| 618 |
This pass rewrites suitable non-aliased local aggregate variables into |
| 619 |
a set of scalar variables. The resulting scalar variables are |
| 620 |
rewritten into SSA form, which allows subsequent optimization passes |
| 621 |
to do a significantly better job with them. The pass is located in |
| 622 |
@file{tree-sra.cc} and is described by @code{pass_sra}. |
| 623 |
|
| 624 |
@item Dead store elimination |
| 625 |
|
| 626 |
This pass eliminates stores to memory that are subsequently overwritten |
| 627 |
by another store, without any intervening loads. The pass is located |
| 628 |
in @file{tree-ssa-dse.cc} and is described by @code{pass_dse}. |
| 629 |
|
| 630 |
@item Tail recursion elimination |
| 631 |
|
| 632 |
This pass transforms tail recursion into a loop. It is located in |
| 633 |
@file{tree-tailcall.cc} and is described by @code{pass_tail_recursion}. |
| 634 |
|
| 635 |
@item Forward store motion |
| 636 |
|
| 637 |
This pass sinks stores and assignments down the flowgraph closer to their |
| 638 |
use point. The pass is located in @file{tree-ssa-sink.cc} and is |
| 639 |
described by @code{pass_sink_code}. |
| 640 |
|
| 641 |
@item Partial redundancy elimination |
| 642 |
|
| 643 |
This pass eliminates partially redundant computations, as well as |
| 644 |
performing load motion. The pass is located in @file{tree-ssa-pre.cc} |
| 645 |
and is described by @code{pass_pre}. |
| 646 |
|
| 647 |
Just before partial redundancy elimination, if |
| 648 |
@option{-funsafe-math-optimizations} is on, GCC tries to convert |
| 649 |
divisions to multiplications by the reciprocal. The pass is located |
| 650 |
in @file{tree-ssa-math-opts.cc} and is described by |
| 651 |
@code{pass_cse_reciprocal}. |
| 652 |
|
| 653 |
@item Full redundancy elimination |
| 654 |
|
| 655 |
This is a simpler form of PRE that only eliminates redundancies that |
| 656 |
occur on all paths. It is located in @file{tree-ssa-pre.cc} and |
| 657 |
described by @code{pass_fre}. |
| 658 |
|
| 659 |
@item Loop optimization |
| 660 |
|
| 661 |
The main driver of the pass is placed in @file{tree-ssa-loop.cc} |
| 662 |
and described by @code{pass_loop}. |
| 663 |
|
| 664 |
The optimizations performed by this pass are: |
| 665 |
|
| 666 |
Loop invariant motion. This pass moves only invariants that |
| 667 |
would be hard to handle on RTL level (function calls, operations that expand to |
| 668 |
nontrivial sequences of insns). With @option{-funswitch-loops} it also moves |
| 669 |
operands of conditions that are invariant out of the loop, so that we can use |
| 670 |
just trivial invariantness analysis in loop unswitching. The pass also includes |
| 671 |
store motion. The pass is implemented in @file{tree-ssa-loop-im.cc}. |
| 672 |
|
| 673 |
Canonical induction variable creation. This pass creates a simple counter |
| 674 |
for number of iterations of the loop and replaces the exit condition of the |
| 675 |
loop using it, in case when a complicated analysis is necessary to determine |
| 676 |
the number of iterations. Later optimizations then may determine the number |
| 677 |
easily. The pass is implemented in @file{tree-ssa-loop-ivcanon.cc}. |
| 678 |
|
| 679 |
Induction variable optimizations. This pass performs standard induction |
| 680 |
variable optimizations, including strength reduction, induction variable |
| 681 |
merging and induction variable elimination. The pass is implemented in |
| 682 |
@file{tree-ssa-loop-ivopts.cc}. |
| 683 |
|
| 684 |
Loop unswitching. This pass moves the conditional jumps that are invariant |
| 685 |
out of the loops. To achieve this, a duplicate of the loop is created for |
| 686 |
each possible outcome of conditional jump(s). The pass is implemented in |
| 687 |
@file{tree-ssa-loop-unswitch.cc}. |
| 688 |
|
| 689 |
Loop splitting. If a loop contains a conditional statement that is |
| 690 |
always true for one part of the iteration space and false for the other |
| 691 |
this pass splits the loop into two, one dealing with one side the other |
| 692 |
only with the other, thereby removing one inner-loop conditional. The |
| 693 |
pass is implemented in @file{tree-ssa-loop-split.cc}. |
| 694 |
|
| 695 |
The optimizations also use various utility functions contained in |
| 696 |
@file{tree-ssa-loop-manip.cc}, @file{cfgloop.cc}, @file{cfgloopanal.cc} and |
| 697 |
@file{cfgloopmanip.cc}. |
| 698 |
|
| 699 |
Vectorization. This pass transforms loops to operate on vector types |
| 700 |
instead of scalar types. Data parallelism across loop iterations is exploited |
| 701 |
to group data elements from consecutive iterations into a vector and operate |
| 702 |
on them in parallel. Depending on available target support the loop is |
| 703 |
conceptually unrolled by a factor @code{VF} (vectorization factor), which is |
| 704 |
the number of elements operated upon in parallel in each iteration, and the |
| 705 |
@code{VF} copies of each scalar operation are fused to form a vector operation. |
| 706 |
Additional loop transformations such as peeling and versioning may take place |
| 707 |
to align the number of iterations, and to align the memory accesses in the |
| 708 |
loop. |
| 709 |
The pass is implemented in @file{tree-vectorizer.cc} (the main driver), |
| 710 |
@file{tree-vect-loop.cc} and @file{tree-vect-loop-manip.cc} (loop specific parts |
| 711 |
and general loop utilities), @file{tree-vect-slp} (loop-aware SLP |
| 712 |
functionality), @file{tree-vect-stmts.cc}, @file{tree-vect-data-refs.cc} and |
| 713 |
@file{tree-vect-slp-patterns.cc} containing the SLP pattern matcher. |
| 714 |
Analysis of data references is in @file{tree-data-ref.cc}. |
| 715 |
|
| 716 |
SLP Vectorization. This pass performs vectorization of straight-line code. The |
| 717 |
pass is implemented in @file{tree-vectorizer.cc} (the main driver), |
| 718 |
@file{tree-vect-slp.cc}, @file{tree-vect-stmts.cc} and |
| 719 |
@file{tree-vect-data-refs.cc}. |
| 720 |
|
| 721 |
Autoparallelization. This pass splits the loop iteration space to run |
| 722 |
into several threads. The pass is implemented in @file{tree-parloops.cc}. |
| 723 |
|
| 724 |
Graphite is a loop transformation framework based on the polyhedral |
| 725 |
model. Graphite stands for Gimple Represented as Polyhedra. The |
| 726 |
internals of this infrastructure are documented in |
| 727 |
@w{@uref{https://gcc.gnu.org/wiki/Graphite}}. The passes working on |
| 728 |
this representation are implemented in the various @file{graphite-*} |
| 729 |
files. |
| 730 |
|
| 731 |
@item Tree level if-conversion for vectorizer |
| 732 |
|
| 733 |
This pass applies if-conversion to simple loops to help vectorizer. |
| 734 |
We identify if convertible loops, if-convert statements and merge |
| 735 |
basic blocks in one big block. The idea is to present loop in such |
| 736 |
form so that vectorizer can have one to one mapping between statements |
| 737 |
and available vector operations. This pass is located in |
| 738 |
@file{tree-if-conv.cc} and is described by @code{pass_if_conversion}. |
| 739 |
|
| 740 |
@item Conditional constant propagation |
| 741 |
|
| 742 |
This pass relaxes a lattice of values in order to identify those |
| 743 |
that must be constant even in the presence of conditional branches. |
| 744 |
The pass is located in @file{tree-ssa-ccp.cc} and is described |
| 745 |
by @code{pass_ccp}. |
| 746 |
|
| 747 |
A related pass that works on memory loads and stores, and not just |
| 748 |
register values, is located in @file{tree-ssa-ccp.cc} and described by |
| 749 |
@code{pass_store_ccp}. |
| 750 |
|
| 751 |
@item Conditional copy propagation |
| 752 |
|
| 753 |
This is similar to constant propagation but the lattice of values is |
| 754 |
the ``copy-of'' relation. It eliminates redundant copies from the |
| 755 |
code. The pass is located in @file{tree-ssa-copy.cc} and described by |
| 756 |
@code{pass_copy_prop}. |
| 757 |
|
| 758 |
A related pass that works on memory copies, and not just register |
| 759 |
copies, is located in @file{tree-ssa-copy.cc} and described by |
| 760 |
@code{pass_store_copy_prop}. |
| 761 |
|
| 762 |
@item Value range propagation |
| 763 |
|
| 764 |
This transformation is similar to constant propagation but |
| 765 |
instead of propagating single constant values, it propagates |
| 766 |
known value ranges. The implementation is based on Patterson's |
| 767 |
range propagation algorithm (Accurate Static Branch Prediction by |
| 768 |
Value Range Propagation, J. R. C. Patterson, PLDI '95). In |
| 769 |
contrast to Patterson's algorithm, this implementation does not |
| 770 |
propagate branch probabilities nor it uses more than a single |
| 771 |
range per SSA name. This means that the current implementation |
| 772 |
cannot be used for branch prediction (though adapting it would |
| 773 |
not be difficult). The pass is located in @file{tree-vrp.cc} and is |
| 774 |
described by @code{pass_vrp}. |
| 775 |
|
| 776 |
@item Folding built-in functions |
| 777 |
|
| 778 |
This pass simplifies built-in functions, as applicable, with constant |
| 779 |
arguments or with inferable string lengths. It is located in |
| 780 |
@file{tree-ssa-ccp.cc} and is described by @code{pass_fold_builtins}. |
| 781 |
|
| 782 |
@item Split critical edges |
| 783 |
|
| 784 |
This pass identifies critical edges and inserts empty basic blocks |
| 785 |
such that the edge is no longer critical. The pass is located in |
| 786 |
@file{tree-cfg.cc} and is described by @code{pass_split_crit_edges}. |
| 787 |
|
| 788 |
@item Control dependence dead code elimination |
| 789 |
|
| 790 |
This pass is a stronger form of dead code elimination that can |
| 791 |
eliminate unnecessary control flow statements. It is located |
| 792 |
in @file{tree-ssa-dce.cc} and is described by @code{pass_cd_dce}. |
| 793 |
|
| 794 |
@item Tail call elimination |
| 795 |
|
| 796 |
This pass identifies function calls that may be rewritten into |
| 797 |
jumps. No code transformation is actually applied here, but the |
| 798 |
data and control flow problem is solved. The code transformation |
| 799 |
requires target support, and so is delayed until RTL@. In the |
| 800 |
meantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility. |
| 801 |
The pass is located in @file{tree-tailcall.cc} and is described by |
| 802 |
@code{pass_tail_calls}. The RTL transformation is handled by |
| 803 |
@code{fixup_tail_calls} in @file{calls.cc}. |
| 804 |
|
| 805 |
@item Warn for function return without value |
| 806 |
|
| 807 |
For non-void functions, this pass locates return statements that do |
| 808 |
not specify a value and issues a warning. Such a statement may have |
| 809 |
been injected by falling off the end of the function. This pass is |
| 810 |
run last so that we have as much time as possible to prove that the |
| 811 |
statement is not reachable. It is located in @file{tree-cfg.cc} and |
| 812 |
is described by @code{pass_warn_function_return}. |
| 813 |
|
| 814 |
@item Leave static single assignment form |
| 815 |
|
| 816 |
This pass rewrites the function such that it is in normal form. At |
| 817 |
the same time, we eliminate as many single-use temporaries as possible, |
| 818 |
so the intermediate language is no longer GIMPLE, but GENERIC@. The |
| 819 |
pass is located in @file{tree-outof-ssa.cc} and is described by |
| 820 |
@code{pass_del_ssa}. |
| 821 |
|
| 822 |
@item Merge PHI nodes that feed into one another |
| 823 |
|
| 824 |
This is part of the CFG cleanup passes. It attempts to join PHI nodes |
| 825 |
from a forwarder CFG block into another block with PHI nodes. The |
| 826 |
pass is located in @file{tree-cfgcleanup.cc} and is described by |
| 827 |
@code{pass_merge_phi}. |
| 828 |
|
| 829 |
@item Return value optimization |
| 830 |
|
| 831 |
If a function always returns the same local variable, and that local |
| 832 |
variable is an aggregate type, then the variable is replaced with the |
| 833 |
return value for the function (i.e., the function's DECL_RESULT). This |
| 834 |
is equivalent to the C++ named return value optimization applied to |
| 835 |
GIMPLE@. The pass is located in @file{tree-nrv.cc} and is described by |
| 836 |
@code{pass_nrv}. |
| 837 |
|
| 838 |
@item Return slot optimization |
| 839 |
|
| 840 |
If a function returns a memory object and is called as @code{var = |
| 841 |
foo()}, this pass tries to change the call so that the address of |
| 842 |
@code{var} is sent to the caller to avoid an extra memory copy. This |
| 843 |
pass is located in @code{tree-nrv.cc} and is described by |
| 844 |
@code{pass_return_slot}. |
| 845 |
|
| 846 |
@item Optimize calls to @code{__builtin_object_size} or |
| 847 |
@code{__builtin_dynamic_object_size} |
| 848 |
|
| 849 |
This is a propagation pass similar to CCP that tries to remove calls to |
| 850 |
@code{__builtin_object_size} when the upper or lower bound for the size |
| 851 |
of the object can be computed at compile-time. It also tries to replace |
| 852 |
calls to @code{__builtin_dynamic_object_size} with an expression that |
| 853 |
evaluates the upper or lower bound for the size of the object. This |
| 854 |
pass is located in @file{tree-object-size.cc} and is described by |
| 855 |
@code{pass_object_sizes}. |
| 856 |
|
| 857 |
@item Loop invariant motion |
| 858 |
|
| 859 |
This pass removes expensive loop-invariant computations out of loops. |
| 860 |
The pass is located in @file{tree-ssa-loop.cc} and described by |
| 861 |
@code{pass_lim}. |
| 862 |
|
| 863 |
@item Loop nest optimizations |
| 864 |
|
| 865 |
This is a family of loop transformations that works on loop nests. It |
| 866 |
includes loop interchange, scaling, skewing and reversal and they are |
| 867 |
all geared to the optimization of data locality in array traversals |
| 868 |
and the removal of dependencies that hamper optimizations such as loop |
| 869 |
parallelization and vectorization. The pass is located in |
| 870 |
@file{tree-loop-linear.c} and described by |
| 871 |
@code{pass_linear_transform}. |
| 872 |
|
| 873 |
@item Removal of empty loops |
| 874 |
|
| 875 |
This pass removes loops with no code in them. The pass is located in |
| 876 |
@file{tree-ssa-loop-ivcanon.cc} and described by |
| 877 |
@code{pass_empty_loop}. |
| 878 |
|
| 879 |
@item Unrolling of small loops |
| 880 |
|
| 881 |
This pass completely unrolls loops with few iterations. The pass |
| 882 |
is located in @file{tree-ssa-loop-ivcanon.cc} and described by |
| 883 |
@code{pass_complete_unroll}. |
| 884 |
|
| 885 |
@item Predictive commoning |
| 886 |
|
| 887 |
This pass makes the code reuse the computations from the previous |
| 888 |
iterations of the loops, especially loads and stores to memory. |
| 889 |
It does so by storing the values of these computations to a bank |
| 890 |
of temporary variables that are rotated at the end of loop. To avoid |
| 891 |
the need for this rotation, the loop is then unrolled and the copies |
| 892 |
of the loop body are rewritten to use the appropriate version of |
| 893 |
the temporary variable. This pass is located in @file{tree-predcom.cc} |
| 894 |
and described by @code{pass_predcom}. |
| 895 |
|
| 896 |
@item Array prefetching |
| 897 |
|
| 898 |
This pass issues prefetch instructions for array references inside |
| 899 |
loops. The pass is located in @file{tree-ssa-loop-prefetch.cc} and |
| 900 |
described by @code{pass_loop_prefetch}. |
| 901 |
|
| 902 |
@item Reassociation |
| 903 |
|
| 904 |
This pass rewrites arithmetic expressions to enable optimizations that |
| 905 |
operate on them, like redundancy elimination and vectorization. The |
| 906 |
pass is located in @file{tree-ssa-reassoc.cc} and described by |
| 907 |
@code{pass_reassoc}. |
| 908 |
|
| 909 |
@item Optimization of @code{stdarg} functions |
| 910 |
|
| 911 |
This pass tries to avoid the saving of register arguments into the |
| 912 |
stack on entry to @code{stdarg} functions. If the function doesn't |
| 913 |
use any @code{va_start} macros, no registers need to be saved. If |
| 914 |
@code{va_start} macros are used, the @code{va_list} variables don't |
| 915 |
escape the function, it is only necessary to save registers that will |
| 916 |
be used in @code{va_arg} macros. For instance, if @code{va_arg} is |
| 917 |
only used with integral types in the function, floating point |
| 918 |
registers don't need to be saved. This pass is located in |
| 919 |
@code{tree-stdarg.cc} and described by @code{pass_stdarg}. |
| 920 |
|
| 921 |
@end itemize |
| 922 |
|
| 923 |
@node RTL passes |
| 924 |
@section RTL passes |
| 925 |
|
| 926 |
The following briefly describes the RTL generation and optimization |
| 927 |
passes that are run after the Tree optimization passes. |
| 928 |
|
| 929 |
@itemize @bullet |
| 930 |
@item RTL generation |
| 931 |
|
| 932 |
@c Avoiding overfull is tricky here. |
| 933 |
The source files for RTL generation include |
| 934 |
@file{stmt.cc}, |
| 935 |
@file{calls.cc}, |
| 936 |
@file{expr.cc}, |
| 937 |
@file{explow.cc}, |
| 938 |
@file{expmed.cc}, |
| 939 |
@file{function.cc}, |
| 940 |
@file{optabs.cc} |
| 941 |
and @file{emit-rtl.cc}. |
| 942 |
Also, the file |
| 943 |
@file{insn-emit.cc}, generated from the machine description by the |
| 944 |
program @code{genemit}, is used in this pass. The header file |
| 945 |
@file{expr.h} is used for communication within this pass. |
| 946 |
|
| 947 |
@findex genflags |
| 948 |
@findex gencodes |
| 949 |
The header files @file{insn-flags.h} and @file{insn-codes.h}, |
| 950 |
generated from the machine description by the programs @code{genflags} |
| 951 |
and @code{gencodes}, tell this pass which standard names are available |
| 952 |
for use and which patterns correspond to them. |
| 953 |
|
| 954 |
@item Generation of exception landing pads |
| 955 |
|
| 956 |
This pass generates the glue that handles communication between the |
| 957 |
exception handling library routines and the exception handlers within |
| 958 |
the function. Entry points in the function that are invoked by the |
| 959 |
exception handling library are called @dfn{landing pads}. The code |
| 960 |
for this pass is located in @file{except.cc}. |
| 961 |
|
| 962 |
@item Control flow graph cleanup |
| 963 |
|
| 964 |
This pass removes unreachable code, simplifies jumps to next, jumps to |
| 965 |
jump, jumps across jumps, etc. The pass is run multiple times. |
| 966 |
For historical reasons, it is occasionally referred to as the ``jump |
| 967 |
optimization pass''. The bulk of the code for this pass is in |
| 968 |
@file{cfgcleanup.cc}, and there are support routines in @file{cfgrtl.cc} |
| 969 |
and @file{jump.cc}. |
| 970 |
|
| 971 |
@item Forward propagation of single-def values |
| 972 |
|
| 973 |
This pass attempts to remove redundant computation by substituting |
| 974 |
variables that come from a single definition, and |
| 975 |
seeing if the result can be simplified. It performs copy propagation |
| 976 |
and addressing mode selection. The pass is run twice, with values |
| 977 |
being propagated into loops only on the second run. The code is |
| 978 |
located in @file{fwprop.cc}. |
| 979 |
|
| 980 |
@item Common subexpression elimination |
| 981 |
|
| 982 |
This pass removes redundant computation within basic blocks, and |
| 983 |
optimizes addressing modes based on cost. The pass is run twice. |
| 984 |
The code for this pass is located in @file{cse.cc}. |
| 985 |
|
| 986 |
@item Global common subexpression elimination |
| 987 |
|
| 988 |
This pass performs two |
| 989 |
different types of GCSE depending on whether you are optimizing for |
| 990 |
size or not (LCM based GCSE tends to increase code size for a gain in |
| 991 |
speed, while Morel-Renvoise based GCSE does not). |
| 992 |
When optimizing for size, GCSE is done using Morel-Renvoise Partial |
| 993 |
Redundancy Elimination, with the exception that it does not try to move |
| 994 |
invariants out of loops---that is left to the loop optimization pass. |
| 995 |
If MR PRE GCSE is done, code hoisting (aka unification) is also done, as |
| 996 |
well as load motion. |
| 997 |
If you are optimizing for speed, LCM (lazy code motion) based GCSE is |
| 998 |
done. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM |
| 999 |
based GCSE also does loop invariant code motion. We also perform load |
| 1000 |
and store motion when optimizing for speed. |
| 1001 |
Regardless of which type of GCSE is used, the GCSE pass also performs |
| 1002 |
global constant and copy propagation. |
| 1003 |
The source file for this pass is @file{gcse.cc}, and the LCM routines |
| 1004 |
are in @file{lcm.cc}. |
| 1005 |
|
| 1006 |
@item Loop optimization |
| 1007 |
|
| 1008 |
This pass performs several loop related optimizations. |
| 1009 |
The source files @file{cfgloopanal.cc} and @file{cfgloopmanip.cc} contain |
| 1010 |
generic loop analysis and manipulation code. Initialization and finalization |
| 1011 |
of loop structures is handled by @file{loop-init.cc}. |
| 1012 |
A loop invariant motion pass is implemented in @file{loop-invariant.cc}. |
| 1013 |
Basic block level optimizations---unrolling, and peeling loops--- |
| 1014 |
are implemented in @file{loop-unroll.cc}. |
| 1015 |
Replacing of the exit condition of loops by special machine-dependent |
| 1016 |
instructions is handled by @file{loop-doloop.cc}. |
| 1017 |
|
| 1018 |
@item Jump bypassing |
| 1019 |
|
| 1020 |
This pass is an aggressive form of GCSE that transforms the control |
| 1021 |
flow graph of a function by propagating constants into conditional |
| 1022 |
branch instructions. The source file for this pass is @file{gcse.cc}. |
| 1023 |
|
| 1024 |
@item If conversion |
| 1025 |
|
| 1026 |
This pass attempts to replace conditional branches and surrounding |
| 1027 |
assignments with arithmetic, boolean value producing comparison |
| 1028 |
instructions, and conditional move instructions. In the very last |
| 1029 |
invocation after reload/LRA, it will generate predicated instructions |
| 1030 |
when supported by the target. The code is located in @file{ifcvt.cc}. |
| 1031 |
|
| 1032 |
@item Web construction |
| 1033 |
|
| 1034 |
This pass splits independent uses of each pseudo-register. This can |
| 1035 |
improve effect of the other transformation, such as CSE or register |
| 1036 |
allocation. The code for this pass is located in @file{web.cc}. |
| 1037 |
|
| 1038 |
@item Instruction combination |
| 1039 |
|
| 1040 |
This pass attempts to combine groups of two or three instructions that |
| 1041 |
are related by data flow into single instructions. It combines the |
| 1042 |
RTL expressions for the instructions by substitution, simplifies the |
| 1043 |
result using algebra, and then attempts to match the result against |
| 1044 |
the machine description. The code is located in @file{combine.cc}. |
| 1045 |
|
| 1046 |
@item Mode switching optimization |
| 1047 |
|
| 1048 |
This pass looks for instructions that require the processor to be in a |
| 1049 |
specific ``mode'' and minimizes the number of mode changes required to |
| 1050 |
satisfy all users. What these modes are, and what they apply to are |
| 1051 |
completely target-specific. The code for this pass is located in |
| 1052 |
@file{mode-switching.cc}. |
| 1053 |
|
| 1054 |
@cindex modulo scheduling |
| 1055 |
@cindex sms, swing, software pipelining |
| 1056 |
@item Modulo scheduling |
| 1057 |
|
| 1058 |
This pass looks at innermost loops and reorders their instructions |
| 1059 |
by overlapping different iterations. Modulo scheduling is performed |
| 1060 |
immediately before instruction scheduling. The code for this pass is |
| 1061 |
located in @file{modulo-sched.cc}. |
| 1062 |
|
| 1063 |
@item Instruction scheduling |
| 1064 |
|
| 1065 |
This pass looks for instructions whose output will not be available by |
| 1066 |
the time that it is used in subsequent instructions. Memory loads and |
| 1067 |
floating point instructions often have this behavior on RISC machines. |
| 1068 |
It re-orders instructions within a basic block to try to separate the |
| 1069 |
definition and use of items that otherwise would cause pipeline |
| 1070 |
stalls. This pass is performed twice, before and after register |
| 1071 |
allocation. The code for this pass is located in @file{haifa-sched.cc}, |
| 1072 |
@file{sched-deps.cc}, @file{sched-ebb.cc}, @file{sched-rgn.cc} and |
| 1073 |
@file{sched-vis.c}. |
| 1074 |
|
| 1075 |
@item Register allocation |
| 1076 |
|
| 1077 |
These passes make sure that all occurrences of pseudo registers are |
| 1078 |
eliminated, either by allocating them to a hard register, replacing |
| 1079 |
them by an equivalent expression (e.g.@: a constant) or by placing |
| 1080 |
them on the stack. This is done in several subpasses: |
| 1081 |
|
| 1082 |
@itemize @bullet |
| 1083 |
@item |
| 1084 |
The integrated register allocator (@acronym{IRA}). It is called |
| 1085 |
integrated because coalescing, register live range splitting, and hard |
| 1086 |
register preferencing are done on-the-fly during coloring. It also |
| 1087 |
has better integration with the reload/LRA pass. Pseudo-registers spilled |
| 1088 |
by the allocator or the reload/LRA have still a chance to get |
| 1089 |
hard-registers if the reload/LRA evicts some pseudo-registers from |
| 1090 |
hard-registers. The allocator helps to choose better pseudos for |
| 1091 |
spilling based on their live ranges and to coalesce stack slots |
| 1092 |
allocated for the spilled pseudo-registers. IRA is a regional |
| 1093 |
register allocator which is transformed into Chaitin-Briggs allocator |
| 1094 |
if there is one region. By default, IRA chooses regions using |
| 1095 |
register pressure but the user can force it to use one region or |
| 1096 |
regions corresponding to all loops. |
| 1097 |
|
| 1098 |
Source files of the allocator are @file{ira.cc}, @file{ira-build.cc}, |
| 1099 |
@file{ira-costs.cc}, @file{ira-conflicts.cc}, @file{ira-color.cc}, |
| 1100 |
@file{ira-emit.cc}, @file{ira-lives}, plus header files @file{ira.h} |
| 1101 |
and @file{ira-int.h} used for the communication between the allocator |
| 1102 |
and the rest of the compiler and between the IRA files. |
| 1103 |
|
| 1104 |
@cindex reloading |
| 1105 |
@item |
| 1106 |
Reloading. This pass renumbers pseudo registers with the hardware |
| 1107 |
registers numbers they were allocated. Pseudo registers that did not |
| 1108 |
get hard registers are replaced with stack slots. Then it finds |
| 1109 |
instructions that are invalid because a value has failed to end up in |
| 1110 |
a register, or has ended up in a register of the wrong kind. It fixes |
| 1111 |
up these instructions by reloading the problematical values |
| 1112 |
temporarily into registers. Additional instructions are generated to |
| 1113 |
do the copying. |
| 1114 |
|
| 1115 |
The reload pass also optionally eliminates the frame pointer and inserts |
| 1116 |
instructions to save and restore call-clobbered registers around calls. |
| 1117 |
|
| 1118 |
Source files are @file{reload.cc} and @file{reload1.cc}, plus the header |
| 1119 |
@file{reload.h} used for communication between them. |
| 1120 |
|
| 1121 |
@cindex Local Register Allocator (LRA) |
| 1122 |
@item |
| 1123 |
This pass is a modern replacement of the reload pass. Source files |
| 1124 |
are @file{lra.cc}, @file{lra-assign.c}, @file{lra-coalesce.cc}, |
| 1125 |
@file{lra-constraints.cc}, @file{lra-eliminations.cc}, |
| 1126 |
@file{lra-lives.cc}, @file{lra-remat.cc}, @file{lra-spills.cc}, the |
| 1127 |
header @file{lra-int.h} used for communication between them, and the |
| 1128 |
header @file{lra.h} used for communication between LRA and the rest of |
| 1129 |
compiler. |
| 1130 |
|
| 1131 |
Unlike the reload pass, intermediate LRA decisions are reflected in |
| 1132 |
RTL as much as possible. This reduces the number of target-dependent |
| 1133 |
macros and hooks, leaving instruction constraints as the primary |
| 1134 |
source of control. |
| 1135 |
|
| 1136 |
LRA is run on targets for which TARGET_LRA_P returns true. |
| 1137 |
@end itemize |
| 1138 |
|
| 1139 |
@item Basic block reordering |
| 1140 |
|
| 1141 |
This pass implements profile guided code positioning. If profile |
| 1142 |
information is not available, various types of static analysis are |
| 1143 |
performed to make the predictions normally coming from the profile |
| 1144 |
feedback (IE execution frequency, branch probability, etc). It is |
| 1145 |
implemented in the file @file{bb-reorder.cc}, and the various |
| 1146 |
prediction routines are in @file{predict.cc}. |
| 1147 |
|
| 1148 |
@item Variable tracking |
| 1149 |
|
| 1150 |
This pass computes where the variables are stored at each |
| 1151 |
position in code and generates notes describing the variable locations |
| 1152 |
to RTL code. The location lists are then generated according to these |
| 1153 |
notes to debug information if the debugging information format supports |
| 1154 |
location lists. The code is located in @file{var-tracking.cc}. |
| 1155 |
|
| 1156 |
@item Delayed branch scheduling |
| 1157 |
|
| 1158 |
This optional pass attempts to find instructions that can go into the |
| 1159 |
delay slots of other instructions, usually jumps and calls. The code |
| 1160 |
for this pass is located in @file{reorg.cc}. |
| 1161 |
|
| 1162 |
@item Branch shortening |
| 1163 |
|
| 1164 |
On many RISC machines, branch instructions have a limited range. |
| 1165 |
Thus, longer sequences of instructions must be used for long branches. |
| 1166 |
In this pass, the compiler figures out what how far each instruction |
| 1167 |
will be from each other instruction, and therefore whether the usual |
| 1168 |
instructions, or the longer sequences, must be used for each branch. |
| 1169 |
The code for this pass is located in @file{final.cc}. |
| 1170 |
|
| 1171 |
@item Register-to-stack conversion |
| 1172 |
|
| 1173 |
Conversion from usage of some hard registers to usage of a register |
| 1174 |
stack may be done at this point. Currently, this is supported only |
| 1175 |
for the floating-point registers of the Intel 80387 coprocessor. The |
| 1176 |
code for this pass is located in @file{reg-stack.cc}. |
| 1177 |
|
| 1178 |
@item Final |
| 1179 |
|
| 1180 |
This pass outputs the assembler code for the function. The source files |
| 1181 |
are @file{final.cc} plus @file{insn-output.cc}; the latter is generated |
| 1182 |
automatically from the machine description by the tool @file{genoutput}. |
| 1183 |
The header file @file{conditions.h} is used for communication between |
| 1184 |
these files. |
| 1185 |
|
| 1186 |
@item Debugging information output |
| 1187 |
|
| 1188 |
This is run after final because it must output the stack slot offsets |
| 1189 |
for pseudo registers that did not get hard registers. Source files |
| 1190 |
are @file{dwarfout.c} for |
| 1191 |
DWARF symbol table format, files @file{dwarf2out.cc} and @file{dwarf2asm.cc} |
| 1192 |
for DWARF2 symbol table format, and @file{vmsdbgout.cc} for VMS debug |
| 1193 |
symbol table format. |
| 1194 |
|
| 1195 |
@end itemize |
| 1196 |
|
| 1197 |
@node Optimization info |
| 1198 |
@section Optimization info |
| 1199 |
@include optinfo.texi |