1169689Skan@c markers: CROSSREF BUG TODO 2169689Skan 3132718Skan@c Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 4169689Skan@c 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 590075Sobrien@c This is part of the GCC manual. 690075Sobrien@c For copying conditions, see the file gcc.texi. 790075Sobrien 890075Sobrien@node Passes 990075Sobrien@chapter Passes and Files of the Compiler 1090075Sobrien@cindex passes and files of the compiler 1190075Sobrien@cindex files and passes of the compiler 1290075Sobrien@cindex compiler passes and files 1390075Sobrien 14169689SkanThis chapter is dedicated to giving an overview of the optimization and 15169689Skancode generation passes of the compiler. In the process, it describes 16169689Skansome of the language front end interface, though this description is no 17169689Skanwhere near complete. 1890075Sobrien 19169689Skan@menu 20169689Skan* Parsing pass:: The language front end turns text into bits. 21169689Skan* Gimplification pass:: The bits are turned into something we can optimize. 22169689Skan* Pass manager:: Sequencing the optimization passes. 23169689Skan* Tree-SSA passes:: Optimizations on a high-level representation. 24169689Skan* RTL passes:: Optimizations on a low-level representation. 25169689Skan@end menu 2690075Sobrien 27169689Skan@node Parsing pass 28169689Skan@section Parsing pass 29169689Skan@cindex GENERIC 30169689Skan@findex lang_hooks.parse_file 31169689SkanThe language front end is invoked only once, via 32169689Skan@code{lang_hooks.parse_file}, to parse the entire input. The language 33169689Skanfront end may use any intermediate language representation deemed 34169689Skanappropriate. The C front end uses GENERIC trees (CROSSREF), plus 35169689Skana double handful of language specific tree codes defined in 36169689Skan@file{c-common.def}. The Fortran front end uses a completely different 37169689Skanprivate representation. 38169689Skan 39169689Skan@cindex GIMPLE 40169689Skan@cindex gimplification 41169689Skan@cindex gimplifier 42169689Skan@cindex language-independent intermediate representation 43169689Skan@cindex intermediate representation lowering 44169689Skan@cindex lowering, language-dependent intermediate representation 45169689SkanAt some point the front end must translate the representation used in the 46169689Skanfront end to a representation understood by the language-independent 47169689Skanportions of the compiler. Current practice takes one of two forms. 48169689SkanThe C front end manually invokes the gimplifier (CROSSREF) on each function, 49169689Skanand uses the gimplifier callbacks to convert the language-specific tree 50169689Skannodes directly to GIMPLE (CROSSREF) before passing the function off to 51169689Skanbe compiled. 52169689SkanThe Fortran front end converts from a private representation to GENERIC, 53169689Skanwhich is later lowered to GIMPLE when the function is compiled. Which 54169689Skanroute to choose probably depends on how well GENERIC (plus extensions) 55169689Skancan be made to match up with the source language and necessary parsing 56169689Skandata structures. 57169689Skan 58169689SkanBUG: Gimplification must occur before nested function lowering, 59169689Skanand nested function lowering must be done by the front end before 60169689Skanpassing the data off to cgraph. 61169689Skan 62169689SkanTODO: Cgraph should control nested function lowering. It would 63169689Skanonly be invoked when it is certain that the outer-most function 64169689Skanis used. 65169689Skan 66169689SkanTODO: Cgraph needs a gimplify_function callback. It should be 67169689Skaninvoked when (1) it is certain that the function is used, (2) 68169689Skanwarning flags specified by the user require some amount of 69169689Skancompilation in order to honor, (3) the language indicates that 70169689Skansemantic analysis is not complete until gimplification occurs. 71169689SkanHum@dots{} this sounds overly complicated. Perhaps we should just 72169689Skanhave the front end gimplify always; in most cases it's only one 73169689Skanfunction call. 74169689Skan 75169689SkanThe front end needs to pass all function definitions and top level 76169689Skandeclarations off to the middle-end so that they can be compiled and 77169689Skanemitted to the object file. For a simple procedural language, it is 78169689Skanusually most convenient to do this as each top level declaration or 79169689Skandefinition is seen. There is also a distinction to be made between 80169689Skangenerating functional code and generating complete debug information. 81169689SkanThe only thing that is absolutely required for functional code is that 82169689Skanfunction and data @emph{definitions} be passed to the middle-end. For 83169689Skancomplete debug information, function, data and type declarations 84169689Skanshould all be passed as well. 85169689Skan 8690075Sobrien@findex rest_of_decl_compilation 87169689Skan@findex rest_of_type_compilation 88169689Skan@findex cgraph_finalize_function 89169689SkanIn any case, the front end needs each complete top-level function or 90169689Skandata declaration, and each data definition should be passed to 91169689Skan@code{rest_of_decl_compilation}. Each complete type definition should 92169689Skanbe passed to @code{rest_of_type_compilation}. Each function definition 93169689Skanshould be passed to @code{cgraph_finalize_function}. 9490075Sobrien 95169689SkanTODO: I know rest_of_compilation currently has all sorts of 96169689Skanrtl-generation semantics. I plan to move all code generation 97169689Skanbits (both tree and rtl) to compile_function. Should we hide 98169689Skancgraph from the front ends and move back to rest_of_compilation 99169689Skanas the official interface? Possibly we should rename all three 100169689Skaninterfaces such that the names match in some meaningful way and 101169689Skanthat is more descriptive than "rest_of". 10290075Sobrien 103169689SkanThe middle-end will, at its option, emit the function and data 104169689Skandefinitions immediately or queue them for later processing. 105169689Skan 106169689Skan@node Gimplification pass 107169689Skan@section Gimplification pass 108169689Skan 109169689Skan@cindex gimplification 110169689Skan@cindex GIMPLE 111169689Skan@dfn{Gimplification} is a whimsical term for the process of converting 112169689Skanthe intermediate representation of a function into the GIMPLE language 113169689Skan(CROSSREF). The term stuck, and so words like ``gimplification'', 114169689Skan``gimplify'', ``gimplifier'' and the like are sprinkled throughout this 115169689Skansection of code. 116169689Skan 117169689Skan@cindex GENERIC 118169689SkanWhile a front end may certainly choose to generate GIMPLE directly if 119169689Skanit chooses, this can be a moderately complex process unless the 120169689Skanintermediate language used by the front end is already fairly simple. 121169689SkanUsually it is easier to generate GENERIC trees plus extensions 122169689Skanand let the language-independent gimplifier do most of the work. 123169689Skan 124169689Skan@findex gimplify_function_tree 125169689Skan@findex gimplify_expr 126169689Skan@findex lang_hooks.gimplify_expr 127169689SkanThe main entry point to this pass is @code{gimplify_function_tree} 128169689Skanlocated in @file{gimplify.c}. From here we process the entire 129169689Skanfunction gimplifying each statement in turn. The main workhorse 130169689Skanfor this pass is @code{gimplify_expr}. Approximately everything 131169689Skanpasses through here at least once, and it is from here that we 132169689Skaninvoke the @code{lang_hooks.gimplify_expr} callback. 133169689Skan 134169689SkanThe callback should examine the expression in question and return 135169689Skan@code{GS_UNHANDLED} if the expression is not a language specific 136169689Skanconstruct that requires attention. Otherwise it should alter the 137169689Skanexpression in some way to such that forward progress is made toward 138169689Skanproducing valid GIMPLE@. If the callback is certain that the 139169689Skantransformation is complete and the expression is valid GIMPLE, it 140169689Skanshould return @code{GS_ALL_DONE}. Otherwise it should return 141169689Skan@code{GS_OK}, which will cause the expression to be processed again. 142169689SkanIf the callback encounters an error during the transformation (because 143169689Skanthe front end is relying on the gimplification process to finish 144169689Skansemantic checks), it should return @code{GS_ERROR}. 145169689Skan 146169689Skan@node Pass manager 147169689Skan@section Pass manager 148169689Skan 149169689SkanThe pass manager is located in @file{passes.c}, @file{tree-optimize.c} 150169689Skanand @file{tree-pass.h}. 151169689SkanIts job is to run all of the individual passes in the correct order, 152169689Skanand take care of standard bookkeeping that applies to every pass. 153169689Skan 154169689SkanThe theory of operation is that each pass defines a structure that 155169689Skanrepresents everything we need to know about that pass---when it 156169689Skanshould be run, how it should be run, what intermediate language 157169689Skanform or on-the-side data structures it needs. We register the pass 158169689Skanto be run in some particular order, and the pass manager arranges 159169689Skanfor everything to happen in the correct order. 160169689Skan 161169689SkanThe actuality doesn't completely live up to the theory at present. 162169689SkanCommand-line switches and @code{timevar_id_t} enumerations must still 163169689Skanbe defined elsewhere. The pass manager validates constraints but does 164169689Skannot attempt to (re-)generate data structures or lower intermediate 165169689Skanlanguage form based on the requirements of the next pass. Nevertheless, 166169689Skanwhat is present is useful, and a far sight better than nothing at all. 167169689Skan 168169689SkanTODO: describe the global variables set up by the pass manager, 169169689Skanand a brief description of how a new pass should use it. 170169689SkanI need to look at what info rtl passes use first... 171169689Skan 172169689Skan@node Tree-SSA passes 173169689Skan@section Tree-SSA passes 174169689Skan 175169689SkanThe following briefly describes the tree optimization passes that are 176169689Skanrun after gimplification and what source files they are located in. 177169689Skan 17890075Sobrien@itemize @bullet 179169689Skan@item Remove useless statements 18090075Sobrien 181169689SkanThis pass is an extremely simple sweep across the gimple code in which 182169689Skanwe identify obviously dead code and remove it. Here we do things like 183169689Skansimplify @code{if} statements with constant conditions, remove 184169689Skanexception handling constructs surrounding code that obviously cannot 185169689Skanthrow, remove lexical bindings that contain no variables, and other 186169689Skanassorted simplistic cleanups. The idea is to get rid of the obvious 187169689Skanstuff quickly rather than wait until later when it's more work to get 188169689Skanrid of it. This pass is located in @file{tree-cfg.c} and described by 189169689Skan@code{pass_remove_useless_stmts}. 19090075Sobrien 191169689Skan@item Mudflap declaration registration 19290075Sobrien 193169689SkanIf mudflap (@pxref{Optimize Options,,-fmudflap -fmudflapth 194169689Skan-fmudflapir,gcc,Using the GNU Compiler Collection (GCC)}) is 195169689Skanenabled, we generate code to register some variable declarations with 196169689Skanthe mudflap runtime. Specifically, the runtime tracks the lifetimes of 197169689Skanthose variable declarations that have their addresses taken, or whose 198169689Skanbounds are unknown at compile time (@code{extern}). This pass generates 199169689Skannew exception handling constructs (@code{try}/@code{finally}), and so 200169689Skanmust run before those are lowered. In addition, the pass enqueues 201169689Skandeclarations of static variables whose lifetimes extend to the entire 202169689Skanprogram. The pass is located in @file{tree-mudflap.c} and is described 203169689Skanby @code{pass_mudflap_1}. 20490075Sobrien 205169689Skan@item OpenMP lowering 20690075Sobrien 207169689SkanIf OpenMP generation (@option{-fopenmp}) is enabled, this pass lowers 208169689SkanOpenMP constructs into GIMPLE. 20990075Sobrien 210169689SkanLowering of OpenMP constructs involves creating replacement 211169689Skanexpressions for local variables that have been mapped using data 212169689Skansharing clauses, exposing the control flow of most synchronization 213169689Skandirectives and adding region markers to facilitate the creation of the 214169689Skancontrol flow graph. The pass is located in @file{omp-low.c} and is 215169689Skandescribed by @code{pass_lower_omp}. 21690075Sobrien 217169689Skan@item OpenMP expansion 21890075Sobrien 219169689SkanIf OpenMP generation (@option{-fopenmp}) is enabled, this pass expands 220169689Skanparallel regions into their own functions to be invoked by the thread 221169689Skanlibrary. The pass is located in @file{omp-low.c} and is described by 222169689Skan@code{pass_expand_omp}. 22390075Sobrien 224169689Skan@item Lower control flow 22590075Sobrien 226169689SkanThis pass flattens @code{if} statements (@code{COND_EXPR}) 227169689Skanand moves lexical bindings (@code{BIND_EXPR}) out of line. After 228169689Skanthis pass, all @code{if} statements will have exactly two @code{goto} 229169689Skanstatements in its @code{then} and @code{else} arms. Lexical binding 230169689Skaninformation for each statement will be found in @code{TREE_BLOCK} rather 231169689Skanthan being inferred from its position under a @code{BIND_EXPR}. This 232169689Skanpass is found in @file{gimple-low.c} and is described by 233169689Skan@code{pass_lower_cf}. 23490075Sobrien 235169689Skan@item Lower exception handling control flow 23690075Sobrien 237169689SkanThis pass decomposes high-level exception handling constructs 238169689Skan(@code{TRY_FINALLY_EXPR} and @code{TRY_CATCH_EXPR}) into a form 239169689Skanthat explicitly represents the control flow involved. After this 240169689Skanpass, @code{lookup_stmt_eh_region} will return a non-negative 241169689Skannumber for any statement that may have EH control flow semantics; 242169689Skanexamine @code{tree_can_throw_internal} or @code{tree_can_throw_external} 243169689Skanfor exact semantics. Exact control flow may be extracted from 244169689Skan@code{foreach_reachable_handler}. The EH region nesting tree is defined 245169689Skanin @file{except.h} and built in @file{except.c}. The lowering pass 246169689Skanitself is in @file{tree-eh.c} and is described by @code{pass_lower_eh}. 24790075Sobrien 248169689Skan@item Build the control flow graph 249169689Skan 250169689SkanThis pass decomposes a function into basic blocks and creates all of 251169689Skanthe edges that connect them. It is located in @file{tree-cfg.c} and 252169689Skanis described by @code{pass_build_cfg}. 253169689Skan 254169689Skan@item Find all referenced variables 255169689Skan 256169689SkanThis pass walks the entire function and collects an array of all 257169689Skanvariables referenced in the function, @code{referenced_vars}. The 258169689Skanindex at which a variable is found in the array is used as a UID 259169689Skanfor the variable within this function. This data is needed by the 260169689SkanSSA rewriting routines. The pass is located in @file{tree-dfa.c} 261169689Skanand is described by @code{pass_referenced_vars}. 262169689Skan 263169689Skan@item Enter static single assignment form 264169689Skan 265169689SkanThis pass rewrites the function such that it is in SSA form. After 266169689Skanthis pass, all @code{is_gimple_reg} variables will be referenced by 267169689Skan@code{SSA_NAME}, and all occurrences of other variables will be 268169689Skanannotated with @code{VDEFS} and @code{VUSES}; PHI nodes will have 269169689Skanbeen inserted as necessary for each basic block. This pass is 270169689Skanlocated in @file{tree-ssa.c} and is described by @code{pass_build_ssa}. 271169689Skan 272169689Skan@item Warn for uninitialized variables 273169689Skan 274169689SkanThis pass scans the function for uses of @code{SSA_NAME}s that 275169689Skanare fed by default definition. For non-parameter variables, such 276169689Skanuses are uninitialized. The pass is run twice, before and after 277169689Skanoptimization. In the first pass we only warn for uses that are 278169689Skanpositively uninitialized; in the second pass we warn for uses that 279169689Skanare possibly uninitialized. The pass is located in @file{tree-ssa.c} 280169689Skanand is defined by @code{pass_early_warn_uninitialized} and 281169689Skan@code{pass_late_warn_uninitialized}. 282169689Skan 283169689Skan@item Dead code elimination 284169689Skan 285169689SkanThis pass scans the function for statements without side effects whose 286169689Skanresult is unused. It does not do memory life analysis, so any value 287169689Skanthat is stored in memory is considered used. The pass is run multiple 288169689Skantimes throughout the optimization process. It is located in 289169689Skan@file{tree-ssa-dce.c} and is described by @code{pass_dce}. 290169689Skan 291169689Skan@item Dominator optimizations 292169689Skan 293169689SkanThis pass performs trivial dominator-based copy and constant propagation, 294169689Skanexpression simplification, and jump threading. It is run multiple times 295169689Skanthroughout the optimization process. It it located in @file{tree-ssa-dom.c} 296169689Skanand is described by @code{pass_dominator}. 297169689Skan 298169689Skan@item Redundant PHI elimination 299169689Skan 300169689SkanThis pass removes PHI nodes for which all of the arguments are the same 301169689Skanvalue, excluding feedback. Such degenerate forms are typically created 302169689Skanby removing unreachable code. The pass is run multiple times throughout 303169689Skanthe optimization process. It is located in @file{tree-ssa.c} and is 304169689Skandescribed by @code{pass_redundant_phi}.o 305169689Skan 306169689Skan@item Forward propagation of single-use variables 307169689Skan 308169689SkanThis pass attempts to remove redundant computation by substituting 309169689Skanvariables that are used once into the expression that uses them and 310169689Skanseeing if the result can be simplified. It is located in 311169689Skan@file{tree-ssa-forwprop.c} and is described by @code{pass_forwprop}. 312169689Skan 313169689Skan@item Copy Renaming 314169689Skan 315169689SkanThis pass attempts to change the name of compiler temporaries involved in 316169689Skancopy operations such that SSA->normal can coalesce the copy away. When compiler 317169689Skantemporaries are copies of user variables, it also renames the compiler 318169689Skantemporary to the user variable resulting in better use of user symbols. It is 319169689Skanlocated in @file{tree-ssa-copyrename.c} and is described by 320169689Skan@code{pass_copyrename}. 321169689Skan 322169689Skan@item PHI node optimizations 323169689Skan 324169689SkanThis pass recognizes forms of PHI inputs that can be represented as 325169689Skanconditional expressions and rewrites them into straight line code. 326169689SkanIt is located in @file{tree-ssa-phiopt.c} and is described by 327169689Skan@code{pass_phiopt}. 328169689Skan 329169689Skan@item May-alias optimization 330169689Skan 331169689SkanThis pass performs a flow sensitive SSA-based points-to analysis. 332169689SkanThe resulting may-alias, must-alias, and escape analysis information 333169689Skanis used to promote variables from in-memory addressable objects to 334169689Skannon-aliased variables that can be renamed into SSA form. We also 335169689Skanupdate the @code{VDEF}/@code{VUSE} memory tags for non-renameable 336169689Skanaggregates so that we get fewer false kills. The pass is located 337169689Skanin @file{tree-ssa-alias.c} and is described by @code{pass_may_alias}. 338169689Skan 339169689SkanInterprocedural points-to information is located in 340169689Skan@file{tree-ssa-structalias.c} and described by @code{pass_ipa_pta}. 341169689Skan 342169689Skan@item Profiling 343169689Skan 344169689SkanThis pass rewrites the function in order to collect runtime block 345169689Skanand value profiling data. Such data may be fed back into the compiler 346169689Skanon a subsequent run so as to allow optimization based on expected 347169689Skanexecution frequencies. The pass is located in @file{predict.c} and 348169689Skanis described by @code{pass_profile}. 349169689Skan 350169689Skan@item Lower complex arithmetic 351169689Skan 352169689SkanThis pass rewrites complex arithmetic operations into their component 353169689Skanscalar arithmetic operations. The pass is located in @file{tree-complex.c} 354169689Skanand is described by @code{pass_lower_complex}. 355169689Skan 356169689Skan@item Scalar replacement of aggregates 357169689Skan 358169689SkanThis pass rewrites suitable non-aliased local aggregate variables into 359169689Skana set of scalar variables. The resulting scalar variables are 360169689Skanrewritten into SSA form, which allows subsequent optimization passes 361169689Skanto do a significantly better job with them. The pass is located in 362169689Skan@file{tree-sra.c} and is described by @code{pass_sra}. 363169689Skan 364169689Skan@item Dead store elimination 365169689Skan 366169689SkanThis pass eliminates stores to memory that are subsequently overwritten 367169689Skanby another store, without any intervening loads. The pass is located 368169689Skanin @file{tree-ssa-dse.c} and is described by @code{pass_dse}. 369169689Skan 370169689Skan@item Tail recursion elimination 371169689Skan 372169689SkanThis pass transforms tail recursion into a loop. It is located in 373169689Skan@file{tree-tailcall.c} and is described by @code{pass_tail_recursion}. 374169689Skan 375169689Skan@item Forward store motion 376169689Skan 377169689SkanThis pass sinks stores and assignments down the flowgraph closer to it's 378169689Skanuse point. The pass is located in @file{tree-ssa-sink.c} and is 379169689Skandescribed by @code{pass_sink_code}. 380169689Skan 381169689Skan@item Partial redundancy elimination 382169689Skan 383169689SkanThis pass eliminates partially redundant computations, as well as 384169689Skanperforming load motion. The pass is located in @file{tree-ssa-pre.c} 385169689Skanand is described by @code{pass_pre}. 386169689Skan 387169689SkanJust before partial redundancy elimination, if 388169689Skan@option{-funsafe-math-optimizations} is on, GCC tries to convert 389169689Skandivisions to multiplications by the reciprocal. The pass is located 390169689Skanin @file{tree-ssa-math-opts.c} and is described by 391169689Skan@code{pass_cse_reciprocal}. 392169689Skan 393169689Skan@item Full redundancy elimination 394169689Skan 395169689SkanThis is a simpler form of PRE that only eliminate redundancies that 396169689Skanoccur an all paths. It is located in @file{tree-ssa-pre.c} and 397169689Skandescribed by @code{pass_fre}. 398169689Skan 399169689Skan@item Loop optimization 400169689Skan 401169689SkanThe main driver of the pass is placed in @file{tree-ssa-loop.c} 402169689Skanand described by @code{pass_loop}. 403169689Skan 404169689SkanThe optimizations performed by this pass are: 405169689Skan 406169689SkanLoop invariant motion. This pass moves only invariants that 407169689Skanwould be hard to handle on rtl level (function calls, operations that expand to 408169689Skannontrivial sequences of insns). With @option{-funswitch-loops} it also moves 409169689Skanoperands of conditions that are invariant out of the loop, so that we can use 410169689Skanjust trivial invariantness analysis in loop unswitching. The pass also includes 411169689Skanstore motion. The pass is implemented in @file{tree-ssa-loop-im.c}. 412169689Skan 413169689SkanCanonical induction variable creation. This pass creates a simple counter 414169689Skanfor number of iterations of the loop and replaces the exit condition of the 415169689Skanloop using it, in case when a complicated analysis is necessary to determine 416169689Skanthe number of iterations. Later optimizations then may determine the number 417169689Skaneasily. The pass is implemented in @file{tree-ssa-loop-ivcanon.c}. 418169689Skan 419169689SkanInduction variable optimizations. This pass performs standard induction 420169689Skanvariable optimizations, including strength reduction, induction variable 421169689Skanmerging and induction variable elimination. The pass is implemented in 422169689Skan@file{tree-ssa-loop-ivopts.c}. 423169689Skan 424169689SkanLoop unswitching. This pass moves the conditional jumps that are invariant 425169689Skanout of the loops. To achieve this, a duplicate of the loop is created for 426169689Skaneach possible outcome of conditional jump(s). The pass is implemented in 427169689Skan@file{tree-ssa-loop-unswitch.c}. This pass should eventually replace the 428169689Skanrtl-level loop unswitching in @file{loop-unswitch.c}, but currently 429169689Skanthe rtl-level pass is not completely redundant yet due to deficiencies 430169689Skanin tree level alias analysis. 431169689Skan 432169689SkanThe optimizations also use various utility functions contained in 433169689Skan@file{tree-ssa-loop-manip.c}, @file{cfgloop.c}, @file{cfgloopanal.c} and 434169689Skan@file{cfgloopmanip.c}. 435169689Skan 436169689SkanVectorization. This pass transforms loops to operate on vector types 437169689Skaninstead of scalar types. Data parallelism across loop iterations is exploited 438169689Skanto group data elements from consecutive iterations into a vector and operate 439169689Skanon them in parallel. Depending on available target support the loop is 440169689Skanconceptually unrolled by a factor @code{VF} (vectorization factor), which is 441169689Skanthe number of elements operated upon in parallel in each iteration, and the 442169689Skan@code{VF} copies of each scalar operation are fused to form a vector operation. 443169689SkanAdditional loop transformations such as peeling and versioning may take place 444169689Skanto align the number of iterations, and to align the memory accesses in the loop. 445169689SkanThe pass is implemented in @file{tree-vectorizer.c} (the main driver and general 446169689Skanutilities), @file{tree-vect-analyze.c} and @file{tree-vect-transform.c}. 447169689SkanAnalysis of data references is in @file{tree-data-ref.c}. 448169689Skan 449169689Skan@item Tree level if-conversion for vectorizer 450169689Skan 451169689SkanThis pass applies if-conversion to simple loops to help vectorizer. 452169689SkanWe identify if convertible loops, if-convert statements and merge 453169689Skanbasic blocks in one big block. The idea is to present loop in such 454169689Skanform so that vectorizer can have one to one mapping between statements 455169689Skanand available vector operations. This patch re-introduces COND_EXPR 456169689Skanat GIMPLE level. This pass is located in @file{tree-if-conv.c} and is 457169689Skandescribed by @code{pass_if_conversion}. 458169689Skan 459169689Skan@item Conditional constant propagation 460169689Skan 461169689SkanThis pass relaxes a lattice of values in order to identify those 462169689Skanthat must be constant even in the presence of conditional branches. 463169689SkanThe pass is located in @file{tree-ssa-ccp.c} and is described 464169689Skanby @code{pass_ccp}. 465169689Skan 466169689SkanA related pass that works on memory loads and stores, and not just 467169689Skanregister values, is located in @file{tree-ssa-ccp.c} and described by 468169689Skan@code{pass_store_ccp}. 469169689Skan 470169689Skan@item Conditional copy propagation 471169689Skan 472169689SkanThis is similar to constant propagation but the lattice of values is 473169689Skanthe ``copy-of'' relation. It eliminates redundant copies from the 474169689Skancode. The pass is located in @file{tree-ssa-copy.c} and described by 475169689Skan@code{pass_copy_prop}. 476169689Skan 477169689SkanA related pass that works on memory copies, and not just register 478169689Skancopies, is located in @file{tree-ssa-copy.c} and described by 479169689Skan@code{pass_store_copy_prop}. 480169689Skan 481169689Skan@item Value range propagation 482169689Skan 483169689SkanThis transformation is similar to constant propagation but 484169689Skaninstead of propagating single constant values, it propagates 485169689Skanknown value ranges. The implementation is based on Patterson's 486169689Skanrange propagation algorithm (Accurate Static Branch Prediction by 487169689SkanValue Range Propagation, J. R. C. Patterson, PLDI '95). In 488169689Skancontrast to Patterson's algorithm, this implementation does not 489169689Skanpropagate branch probabilities nor it uses more than a single 490169689Skanrange per SSA name. This means that the current implementation 491169689Skancannot be used for branch prediction (though adapting it would 492169689Skannot be difficult). The pass is located in @file{tree-vrp.c} and is 493169689Skandescribed by @code{pass_vrp}. 494169689Skan 495169689Skan@item Folding built-in functions 496169689Skan 497169689SkanThis pass simplifies built-in functions, as applicable, with constant 498169689Skanarguments or with inferrable string lengths. It is located in 499169689Skan@file{tree-ssa-ccp.c} and is described by @code{pass_fold_builtins}. 500169689Skan 501169689Skan@item Split critical edges 502169689Skan 503169689SkanThis pass identifies critical edges and inserts empty basic blocks 504169689Skansuch that the edge is no longer critical. The pass is located in 505169689Skan@file{tree-cfg.c} and is described by @code{pass_split_crit_edges}. 506169689Skan 507169689Skan@item Control dependence dead code elimination 508169689Skan 509169689SkanThis pass is a stronger form of dead code elimination that can 510169689Skaneliminate unnecessary control flow statements. It is located 511169689Skanin @file{tree-ssa-dce.c} and is described by @code{pass_cd_dce}. 512169689Skan 513169689Skan@item Tail call elimination 514169689Skan 515169689SkanThis pass identifies function calls that may be rewritten into 516169689Skanjumps. No code transformation is actually applied here, but the 517169689Skandata and control flow problem is solved. The code transformation 518169689Skanrequires target support, and so is delayed until RTL@. In the 519169689Skanmeantime @code{CALL_EXPR_TAILCALL} is set indicating the possibility. 520169689SkanThe pass is located in @file{tree-tailcall.c} and is described by 521169689Skan@code{pass_tail_calls}. The RTL transformation is handled by 522169689Skan@code{fixup_tail_calls} in @file{calls.c}. 523169689Skan 524169689Skan@item Warn for function return without value 525169689Skan 526169689SkanFor non-void functions, this pass locates return statements that do 527169689Skannot specify a value and issues a warning. Such a statement may have 528169689Skanbeen injected by falling off the end of the function. This pass is 529169689Skanrun last so that we have as much time as possible to prove that the 530169689Skanstatement is not reachable. It is located in @file{tree-cfg.c} and 531169689Skanis described by @code{pass_warn_function_return}. 532169689Skan 533169689Skan@item Mudflap statement annotation 534169689Skan 535169689SkanIf mudflap is enabled, we rewrite some memory accesses with code to 536169689Skanvalidate that the memory access is correct. In particular, expressions 537169689Skaninvolving pointer dereferences (@code{INDIRECT_REF}, @code{ARRAY_REF}, 538169689Skanetc.) are replaced by code that checks the selected address range 539169689Skanagainst the mudflap runtime's database of valid regions. This check 540169689Skanincludes an inline lookup into a direct-mapped cache, based on 541169689Skanshift/mask operations of the pointer value, with a fallback function 542169689Skancall into the runtime. The pass is located in @file{tree-mudflap.c} and 543169689Skanis described by @code{pass_mudflap_2}. 544169689Skan 545169689Skan@item Leave static single assignment form 546169689Skan 547169689SkanThis pass rewrites the function such that it is in normal form. At 548169689Skanthe same time, we eliminate as many single-use temporaries as possible, 549169689Skanso the intermediate language is no longer GIMPLE, but GENERIC@. The 550169689Skanpass is located in @file{tree-outof-ssa.c} and is described by 551169689Skan@code{pass_del_ssa}. 552169689Skan 553169689Skan@item Merge PHI nodes that feed into one another 554169689Skan 555169689SkanThis is part of the CFG cleanup passes. It attempts to join PHI nodes 556169689Skanfrom a forwarder CFG block into another block with PHI nodes. The 557169689Skanpass is located in @file{tree-cfgcleanup.c} and is described by 558169689Skan@code{pass_merge_phi}. 559169689Skan 560169689Skan@item Return value optimization 561169689Skan 562169689SkanIf a function always returns the same local variable, and that local 563169689Skanvariable is an aggregate type, then the variable is replaced with the 564169689Skanreturn value for the function (i.e., the function's DECL_RESULT). This 565169689Skanis equivalent to the C++ named return value optimization applied to 566169689SkanGIMPLE. The pass is located in @file{tree-nrv.c} and is described by 567169689Skan@code{pass_nrv}. 568169689Skan 569169689Skan@item Return slot optimization 570169689Skan 571169689SkanIf a function returns a memory object and is called as @code{var = 572169689Skanfoo()}, this pass tries to change the call so that the address of 573169689Skan@code{var} is sent to the caller to avoid an extra memory copy. This 574169689Skanpass is located in @code{tree-nrv.c} and is described by 575169689Skan@code{pass_return_slot}. 576169689Skan 577169689Skan@item Optimize calls to @code{__builtin_object_size} 578169689Skan 579169689SkanThis is a propagation pass similar to CCP that tries to remove calls 580169689Skanto @code{__builtin_object_size} when the size of the object can be 581169689Skancomputed at compile-time. This pass is located in 582169689Skan@file{tree-object-size.c} and is described by 583169689Skan@code{pass_object_sizes}. 584169689Skan 585169689Skan@item Loop invariant motion 586169689Skan 587169689SkanThis pass removes expensive loop-invariant computations out of loops. 588169689SkanThe pass is located in @file{tree-ssa-loop.c} and described by 589169689Skan@code{pass_lim}. 590169689Skan 591169689Skan@item Loop nest optimizations 592169689Skan 593169689SkanThis is a family of loop transformations that works on loop nests. It 594169689Skanincludes loop interchange, scaling, skewing and reversal and they are 595169689Skanall geared to the optimization of data locality in array traversals 596169689Skanand the removal of dependencies that hamper optimizations such as loop 597169689Skanparallelization and vectorization. The pass is located in 598169689Skan@file{tree-loop-linear.c} and described by 599169689Skan@code{pass_linear_transform}. 600169689Skan 601169689Skan@item Removal of empty loops 602169689Skan 603169689SkanThis pass removes loops with no code in them. The pass is located in 604169689Skan@file{tree-ssa-loop-ivcanon.c} and described by 605169689Skan@code{pass_empty_loop}. 606169689Skan 607169689Skan@item Unrolling of small loops 608169689Skan 609169689SkanThis pass completely unrolls loops with few iterations. The pass 610169689Skanis located in @file{tree-ssa-loop-ivcanon.c} and described by 611169689Skan@code{pass_complete_unroll}. 612169689Skan 613169689Skan@item Array prefetching 614169689Skan 615169689SkanThis pass issues prefetch instructions for array references inside 616169689Skanloops. The pass is located in @file{tree-ssa-loop-prefetch.c} and 617169689Skandescribed by @code{pass_loop_prefetch}. 618169689Skan 619169689Skan@item Reassociation 620169689Skan 621169689SkanThis pass rewrites arithmetic expressions to enable optimizations that 622169689Skanoperate on them, like redundancy elimination and vectorization. The 623169689Skanpass is located in @file{tree-ssa-reassoc.c} and described by 624169689Skan@code{pass_reassoc}. 625169689Skan 626169689Skan@item Optimization of @code{stdarg} functions 627169689Skan 628169689SkanThis pass tries to avoid the saving of register arguments into the 629169689Skanstack on entry to @code{stdarg} functions. If the function doesn't 630169689Skanuse any @code{va_start} macros, no registers need to be saved. If 631169689Skan@code{va_start} macros are used, the @code{va_list} variables don't 632169689Skanescape the function, it is only necessary to save registers that will 633169689Skanbe used in @code{va_arg} macros. For instance, if @code{va_arg} is 634169689Skanonly used with integral types in the function, floating point 635169689Skanregisters don't need to be saved. This pass is located in 636169689Skan@code{tree-stdarg.c} and described by @code{pass_stdarg}. 637169689Skan 638169689Skan@end itemize 639169689Skan 640169689Skan@node RTL passes 641169689Skan@section RTL passes 642169689Skan 643169689SkanThe following briefly describes the rtl generation and optimization 644169689Skanpasses that are run after tree optimization. 645169689Skan 646169689Skan@itemize @bullet 647169689Skan@item RTL generation 648169689Skan 64990075Sobrien@c Avoiding overfull is tricky here. 65090075SobrienThe source files for RTL generation include 65190075Sobrien@file{stmt.c}, 65290075Sobrien@file{calls.c}, 65390075Sobrien@file{expr.c}, 65490075Sobrien@file{explow.c}, 65590075Sobrien@file{expmed.c}, 65690075Sobrien@file{function.c}, 65790075Sobrien@file{optabs.c} 65890075Sobrienand @file{emit-rtl.c}. 65990075SobrienAlso, the file 66090075Sobrien@file{insn-emit.c}, generated from the machine description by the 66190075Sobrienprogram @code{genemit}, is used in this pass. The header file 66290075Sobrien@file{expr.h} is used for communication within this pass. 66390075Sobrien 66490075Sobrien@findex genflags 66590075Sobrien@findex gencodes 66690075SobrienThe header files @file{insn-flags.h} and @file{insn-codes.h}, 66790075Sobriengenerated from the machine description by the programs @code{genflags} 66890075Sobrienand @code{gencodes}, tell this pass which standard names are available 66990075Sobrienfor use and which patterns correspond to them. 67090075Sobrien 671169689Skan@item Generate exception handling landing pads 67290075Sobrien 673169689SkanThis pass generates the glue that handles communication between the 674169689Skanexception handling library routines and the exception handlers within 675169689Skanthe function. Entry points in the function that are invoked by the 676169689Skanexception handling library are called @dfn{landing pads}. The code 677169689Skanfor this pass is located within @file{except.c}. 67890075Sobrien 679169689Skan@item Cleanup control flow graph 68090075Sobrien 681169689SkanThis pass removes unreachable code, simplifies jumps to next, jumps to 682169689Skanjump, jumps across jumps, etc. The pass is run multiple times. 683169689SkanFor historical reasons, it is occasionally referred to as the ``jump 684169689Skanoptimization pass''. The bulk of the code for this pass is in 685169689Skan@file{cfgcleanup.c}, and there are support routines in @file{cfgrtl.c} 686169689Skanand @file{jump.c}. 68790075Sobrien 688169689Skan@item Common subexpression elimination 68990075Sobrien 690169689SkanThis pass removes redundant computation within basic blocks, and 691169689Skanoptimizes addressing modes based on cost. The pass is run twice. 692169689SkanThe source is located in @file{cse.c}. 69390075Sobrien 694169689Skan@item Global common subexpression elimination. 69590075Sobrien 696169689SkanThis pass performs two 69790075Sobriendifferent types of GCSE depending on whether you are optimizing for 69890075Sobriensize or not (LCM based GCSE tends to increase code size for a gain in 69990075Sobrienspeed, while Morel-Renvoise based GCSE does not). 70090075SobrienWhen optimizing for size, GCSE is done using Morel-Renvoise Partial 70190075SobrienRedundancy Elimination, with the exception that it does not try to move 70290075Sobrieninvariants out of loops---that is left to the loop optimization pass. 70390075SobrienIf MR PRE GCSE is done, code hoisting (aka unification) is also done, as 70490075Sobrienwell as load motion. 70590075SobrienIf you are optimizing for speed, LCM (lazy code motion) based GCSE is 70690075Sobriendone. LCM is based on the work of Knoop, Ruthing, and Steffen. LCM 70790075Sobrienbased GCSE also does loop invariant code motion. We also perform load 70890075Sobrienand store motion when optimizing for speed. 70990075SobrienRegardless of which type of GCSE is used, the GCSE pass also performs 71090075Sobrienglobal constant and copy propagation. 71190075SobrienThe source file for this pass is @file{gcse.c}, and the LCM routines 71290075Sobrienare in @file{lcm.c}. 71390075Sobrien 714169689Skan@item Loop optimization 71590075Sobrien 716169689SkanThis pass performs several loop related optimizations. 717169689SkanThe source files @file{cfgloopanal.c} and @file{cfgloopmanip.c} contain 718169689Skangeneric loop analysis and manipulation code. Initialization and finalization 719169689Skanof loop structures is handled by @file{loop-init.c}. 720169689SkanA loop invariant motion pass is implemented in @file{loop-invariant.c}. 721169689SkanBasic block level optimizations---unrolling, peeling and unswitching loops--- 722169689Skanare implemented in @file{loop-unswitch.c} and @file{loop-unroll.c}. 723169689SkanReplacing of the exit condition of loops by special machine-dependent 724169689Skaninstructions is handled by @file{loop-doloop.c}. 72590075Sobrien 726169689Skan@item Jump bypassing 727132718Skan 728169689SkanThis pass is an aggressive form of GCSE that transforms the control 729169689Skanflow graph of a function by propagating constants into conditional 730169689Skanbranch instructions. The source file for this pass is @file{gcse.c}. 731132718Skan 732169689Skan@item If conversion 733132718Skan 734169689SkanThis pass attempts to replace conditional branches and surrounding 735169689Skanassignments with arithmetic, boolean value producing comparison 736169689Skaninstructions, and conditional move instructions. In the very last 737169689Skaninvocation after reload, it will generate predicated instructions 738169689Skanwhen supported by the target. The pass is located in @file{ifcvt.c}. 739132718Skan 740169689Skan@item Web construction 741132718Skan 742169689SkanThis pass splits independent uses of each pseudo-register. This can 743169689Skanimprove effect of the other transformation, such as CSE or register 744169689Skanallocation. Its source files are @file{web.c}. 745132718Skan 746169689Skan@item Life analysis 74790075Sobrien 748169689SkanThis pass computes which pseudo-registers are live at each point in 749169689Skanthe program, and makes the first instruction that uses a value point 750169689Skanat the instruction that computed the value. It then deletes 751169689Skancomputations whose results are never used, and combines memory 752169689Skanreferences with add or subtract instructions to make autoincrement or 753169689Skanautodecrement addressing. The pass is located in @file{flow.c}. 75490075Sobrien 755169689Skan@item Instruction combination 75690075Sobrien 757169689SkanThis pass attempts to combine groups of two or three instructions that 758169689Skanare related by data flow into single instructions. It combines the 759169689SkanRTL expressions for the instructions by substitution, simplifies the 760169689Skanresult using algebra, and then attempts to match the result against 761169689Skanthe machine description. The pass is located in @file{combine.c}. 76290075Sobrien 763169689Skan@item Register movement 76490075Sobrien 765169689SkanThis pass looks for cases where matching constraints would force an 766169689Skaninstruction to need a reload, and this reload would be a 767169689Skanregister-to-register move. It then attempts to change the registers 768169689Skanused by the instruction to avoid the move instruction. 769169689SkanThe pass is located in @file{regmove.c}. 77090075Sobrien 771169689Skan@item Optimize mode switching 77290075Sobrien 773169689SkanThis pass looks for instructions that require the processor to be in a 774169689Skanspecific ``mode'' and minimizes the number of mode changes required to 775169689Skansatisfy all users. What these modes are, and what they apply to are 776169689Skancompletely target-specific. 777169689SkanThe source is located in @file{mode-switching.c}. 77890075Sobrien 779169689Skan@cindex modulo scheduling 780169689Skan@cindex sms, swing, software pipelining 781169689Skan@item Modulo scheduling 78290075Sobrien 783169689SkanThis pass looks at innermost loops and reorders their instructions 784169689Skanby overlapping different iterations. Modulo scheduling is performed 785169689Skanimmediately before instruction scheduling. 786169689SkanThe pass is located in (@file{modulo-sched.c}). 78790075Sobrien 788169689Skan@item Instruction scheduling 78990075Sobrien 790169689SkanThis pass looks for instructions whose output will not be available by 791169689Skanthe time that it is used in subsequent instructions. Memory loads and 792169689Skanfloating point instructions often have this behavior on RISC machines. 793169689SkanIt re-orders instructions within a basic block to try to separate the 794169689Skandefinition and use of items that otherwise would cause pipeline 795169689Skanstalls. This pass is performed twice, before and after register 796169689Skanallocation. The pass is located in @file{haifa-sched.c}, 797169689Skan@file{sched-deps.c}, @file{sched-ebb.c}, @file{sched-rgn.c} and 798169689Skan@file{sched-vis.c}. 79990075Sobrien 800169689Skan@item Register allocation 80190075Sobrien 802169689SkanThese passes make sure that all occurrences of pseudo registers are 803169689Skaneliminated, either by allocating them to a hard register, replacing 804169689Skanthem by an equivalent expression (e.g.@: a constant) or by placing 805117395Skanthem on the stack. This is done in several subpasses: 806117395Skan 807117395Skan@itemize @bullet 80890075Sobrien@item 80990075SobrienRegister class preferencing. The RTL code is scanned to find out 81090075Sobrienwhich register class is best for each pseudo register. The source 81190075Sobrienfile is @file{regclass.c}. 81290075Sobrien 81390075Sobrien@item 814169689SkanLocal register allocation. This pass allocates hard registers to 815169689Skanpseudo registers that are used only within one basic block. Because 816169689Skanthe basic block is linear, it can use fast and powerful techniques to 817169689Skando a decent job. The source is located in @file{local-alloc.c}. 81890075Sobrien 81990075Sobrien@item 820169689SkanGlobal register allocation. This pass allocates hard registers for 821169689Skanthe remaining pseudo registers (those whose life spans are not 822169689Skancontained in one basic block). The pass is located in @file{global.c}. 82390075Sobrien 82490075Sobrien@cindex reloading 82590075Sobrien@item 82690075SobrienReloading. This pass renumbers pseudo registers with the hardware 82790075Sobrienregisters numbers they were allocated. Pseudo registers that did not 82890075Sobrienget hard registers are replaced with stack slots. Then it finds 82990075Sobrieninstructions that are invalid because a value has failed to end up in 83090075Sobriena register, or has ended up in a register of the wrong kind. It fixes 83190075Sobrienup these instructions by reloading the problematical values 83290075Sobrientemporarily into registers. Additional instructions are generated to 83390075Sobriendo the copying. 83490075Sobrien 83590075SobrienThe reload pass also optionally eliminates the frame pointer and inserts 83690075Sobrieninstructions to save and restore call-clobbered registers around calls. 83790075Sobrien 83890075SobrienSource files are @file{reload.c} and @file{reload1.c}, plus the header 83990075Sobrien@file{reload.h} used for communication between them. 840117395Skan@end itemize 84190075Sobrien 842169689Skan@item Basic block reordering 84390075Sobrien 844169689SkanThis pass implements profile guided code positioning. If profile 845169689Skaninformation is not available, various types of static analysis are 846169689Skanperformed to make the predictions normally coming from the profile 847169689Skanfeedback (IE execution frequency, branch probability, etc). It is 848169689Skanimplemented in the file @file{bb-reorder.c}, and the various 849169689Skanprediction routines are in @file{predict.c}. 85090075Sobrien 851169689Skan@item Variable tracking 85290075Sobrien 853169689SkanThis pass computes where the variables are stored at each 854169689Skanposition in code and generates notes describing the variable locations 855169689Skanto RTL code. The location lists are then generated according to these 856169689Skannotes to debug information if the debugging information format supports 857169689Skanlocation lists. 85890075Sobrien 859169689Skan@item Delayed branch scheduling 86090075Sobrien 861169689SkanThis optional pass attempts to find instructions that can go into the 862169689Skandelay slots of other instructions, usually jumps and calls. The 863169689Skansource file name is @file{reorg.c}. 86490075Sobrien 865169689Skan@item Branch shortening 86690075Sobrien 867169689SkanOn many RISC machines, branch instructions have a limited range. 868169689SkanThus, longer sequences of instructions must be used for long branches. 869169689SkanIn this pass, the compiler figures out what how far each instruction 870169689Skanwill be from each other instruction, and therefore whether the usual 871169689Skaninstructions, or the longer sequences, must be used for each branch. 872169689Skan 873169689Skan@item Register-to-stack conversion 874169689Skan 87590075SobrienConversion from usage of some hard registers to usage of a register 87690075Sobrienstack may be done at this point. Currently, this is supported only 87790075Sobrienfor the floating-point registers of the Intel 80387 coprocessor. The 87890075Sobriensource file name is @file{reg-stack.c}. 87990075Sobrien 880169689Skan@item Final 88190075Sobrien 882169689SkanThis pass outputs the assembler code for the function. The source files 883169689Skanare @file{final.c} plus @file{insn-output.c}; the latter is generated 884169689Skanautomatically from the machine description by the tool @file{genoutput}. 885169689SkanThe header file @file{conditions.h} is used for communication between 886169689Skanthese files. If mudflap is enabled, the queue of deferred declarations 887169689Skanand any addressed constants (e.g., string literals) is processed by 888169689Skan@code{mudflap_finish_file} into a synthetic constructor function 889169689Skancontaining calls into the mudflap runtime. 89090075Sobrien 891169689Skan@item Debugging information output 89290075Sobrien 893169689SkanThis is run after final because it must output the stack slot offsets 894169689Skanfor pseudo registers that did not get hard registers. Source files 895169689Skanare @file{dbxout.c} for DBX symbol table format, @file{sdbout.c} for 896169689SkanSDB symbol table format, @file{dwarfout.c} for DWARF symbol table 897169689Skanformat, files @file{dwarf2out.c} and @file{dwarf2asm.c} for DWARF2 898169689Skansymbol table format, and @file{vmsdbgout.c} for VMS debug symbol table 899169689Skanformat. 90090075Sobrien 90190075Sobrien@end itemize 902