| Dmitri Gribenko | e4b3e94 | 2012-12-11 15:29:37 +0000 | [diff] [blame] | 1 | .. |
| 2 | If Passes.html is up to date, the following "one-liner" should print |
| 3 | an empty diff. |
| 4 | |
| 5 | egrep -e '^<tr><td><a href="#.*">-.*</a></td><td>.*</td></tr>$' \ |
| 6 | -e '^ <a name=".*">.*</a>$' < Passes.html >html; \ |
| 7 | perl >help <<'EOT' && diff -u help html; rm -f help html |
| 8 | open HTML, "<Passes.html" or die "open: Passes.html: $!\n"; |
| 9 | while (<HTML>) { |
| 10 | m:^<tr><td><a href="#(.*)">-.*</a></td><td>.*</td></tr>$: or next; |
| 11 | $order{$1} = sprintf("%03d", 1 + int %order); |
| 12 | } |
| 13 | open HELP, "../Release/bin/opt -help|" or die "open: opt -help: $!\n"; |
| 14 | while (<HELP>) { |
| 15 | m:^ -([^ ]+) +- (.*)$: or next; |
| 16 | my $o = $order{$1}; |
| 17 | $o = "000" unless defined $o; |
| 18 | push @x, "$o<tr><td><a href=\"#$1\">-$1</a></td><td>$2</td></tr>\n"; |
| 19 | push @y, "$o <a name=\"$1\">-$1: $2</a>\n"; |
| 20 | } |
| 21 | @x = map { s/^\d\d\d//; $_ } sort @x; |
| 22 | @y = map { s/^\d\d\d//; $_ } sort @y; |
| 23 | print @x, @y; |
| 24 | EOT |
| 25 | |
| 26 | This (real) one-liner can also be helpful when converting comments to HTML: |
| 27 | |
| 28 | perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print " <p>\n" if !$on && $_ =~ /\S/; print " </p>\n" if $on && $_ =~ /^\s*$/; print " $_\n"; $on = ($_ =~ /\S/); } print " </p>\n" if $on' |
| 29 | |
| 30 | ==================================== |
| 31 | LLVM's Analysis and Transform Passes |
| 32 | ==================================== |
| 33 | |
| 34 | .. contents:: |
| 35 | :local: |
| 36 | |
| 37 | Written by `Reid Spencer <mailto:rspencer@x10sys.com>`_ |
| 38 | and Gordon Henriksen |
| 39 | |
| 40 | Introduction |
| 41 | ============ |
| 42 | |
| 43 | This document serves as a high level summary of the optimization features that |
| 44 | LLVM provides. Optimizations are implemented as Passes that traverse some |
| 45 | portion of a program to either collect information or transform the program. |
| 46 | The table below divides the passes that LLVM provides into three categories. |
| 47 | Analysis passes compute information that other passes can use or for debugging |
| 48 | or program visualization purposes. Transform passes can use (or invalidate) |
| 49 | the analysis passes. Transform passes all mutate the program in some way. |
| 50 | Utility passes provides some utility but don't otherwise fit categorization. |
| 51 | For example passes to extract functions to bitcode or write a module to bitcode |
| 52 | are neither analysis nor transform passes. The table of contents above |
| 53 | provides a quick summary of each pass and links to the more complete pass |
| 54 | description later in the document. |
| 55 | |
| 56 | Analysis Passes |
| 57 | =============== |
| 58 | |
| 59 | This section describes the LLVM Analysis Passes. |
| 60 | |
| 61 | ``-aa-eval``: Exhaustive Alias Analysis Precision Evaluator |
| 62 | ----------------------------------------------------------- |
| 63 | |
| 64 | This is a simple N^2 alias analysis accuracy evaluator. Basically, for each |
| 65 | function in the program, it simply queries to see how the alias analysis |
| 66 | implementation answers alias queries between each pair of pointers in the |
| 67 | function. |
| 68 | |
| 69 | This is inspired and adapted from code by: Naveen Neelakantam, Francesco |
| 70 | Spadini, and Wojciech Stryjewski. |
| 71 | |
| 72 | ``-basicaa``: Basic Alias Analysis (stateless AA impl) |
| 73 | ------------------------------------------------------ |
| 74 | |
| 75 | A basic alias analysis pass that implements identities (two different globals |
| 76 | cannot alias, etc), but does no stateful analysis. |
| 77 | |
| 78 | ``-basiccg``: Basic CallGraph Construction |
| 79 | ------------------------------------------ |
| 80 | |
| 81 | Yet to be written. |
| 82 | |
| 83 | ``-count-aa``: Count Alias Analysis Query Responses |
| 84 | --------------------------------------------------- |
| 85 | |
| 86 | A pass which can be used to count how many alias queries are being made and how |
| 87 | the alias analysis implementation being used responds. |
| 88 | |
| 89 | ``-da``: Dependence Analysis |
| 90 | ---------------------------- |
| 91 | |
| 92 | Dependence analysis framework, which is used to detect dependences in memory |
| 93 | accesses. |
| 94 | |
| 95 | ``-debug-aa``: AA use debugger |
| 96 | ------------------------------ |
| 97 | |
| 98 | This simple pass checks alias analysis users to ensure that if they create a |
| 99 | new value, they do not query AA without informing it of the value. It acts as |
| 100 | a shim over any other AA pass you want. |
| 101 | |
| 102 | Yes keeping track of every value in the program is expensive, but this is a |
| 103 | debugging pass. |
| 104 | |
| 105 | ``-domfrontier``: Dominance Frontier Construction |
| 106 | ------------------------------------------------- |
| 107 | |
| 108 | This pass is a simple dominator construction algorithm for finding forward |
| 109 | dominator frontiers. |
| 110 | |
| 111 | ``-domtree``: Dominator Tree Construction |
| 112 | ----------------------------------------- |
| 113 | |
| 114 | This pass is a simple dominator construction algorithm for finding forward |
| 115 | dominators. |
| 116 | |
| 117 | |
| 118 | ``-dot-callgraph``: Print Call Graph to "dot" file |
| 119 | -------------------------------------------------- |
| 120 | |
| 121 | This pass, only available in ``opt``, prints the call graph into a ``.dot`` |
| 122 | graph. This graph can then be processed with the "dot" tool to convert it to |
| 123 | postscript or some other suitable format. |
| 124 | |
| 125 | ``-dot-cfg``: Print CFG of function to "dot" file |
| 126 | ------------------------------------------------- |
| 127 | |
| 128 | This pass, only available in ``opt``, prints the control flow graph into a |
| 129 | ``.dot`` graph. This graph can then be processed with the :program:`dot` tool |
| 130 | to convert it to postscript or some other suitable format. |
| 131 | |
| 132 | ``-dot-cfg-only``: Print CFG of function to "dot" file (with no function bodies) |
| 133 | -------------------------------------------------------------------------------- |
| 134 | |
| 135 | This pass, only available in ``opt``, prints the control flow graph into a |
| 136 | ``.dot`` graph, omitting the function bodies. This graph can then be processed |
| 137 | with the :program:`dot` tool to convert it to postscript or some other suitable |
| 138 | format. |
| 139 | |
| 140 | ``-dot-dom``: Print dominance tree of function to "dot" file |
| 141 | ------------------------------------------------------------ |
| 142 | |
| 143 | This pass, only available in ``opt``, prints the dominator tree into a ``.dot`` |
| 144 | graph. This graph can then be processed with the :program:`dot` tool to |
| 145 | convert it to postscript or some other suitable format. |
| 146 | |
| 147 | ``-dot-dom-only``: Print dominance tree of function to "dot" file (with no function bodies) |
| 148 | ------------------------------------------------------------------------------------------- |
| 149 | |
| 150 | This pass, only available in ``opt``, prints the dominator tree into a ``.dot`` |
| 151 | graph, omitting the function bodies. This graph can then be processed with the |
| 152 | :program:`dot` tool to convert it to postscript or some other suitable format. |
| 153 | |
| 154 | ``-dot-postdom``: Print postdominance tree of function to "dot" file |
| 155 | -------------------------------------------------------------------- |
| 156 | |
| 157 | This pass, only available in ``opt``, prints the post dominator tree into a |
| 158 | ``.dot`` graph. This graph can then be processed with the :program:`dot` tool |
| 159 | to convert it to postscript or some other suitable format. |
| 160 | |
| 161 | ``-dot-postdom-only``: Print postdominance tree of function to "dot" file (with no function bodies) |
| 162 | --------------------------------------------------------------------------------------------------- |
| 163 | |
| 164 | This pass, only available in ``opt``, prints the post dominator tree into a |
| 165 | ``.dot`` graph, omitting the function bodies. This graph can then be processed |
| 166 | with the :program:`dot` tool to convert it to postscript or some other suitable |
| 167 | format. |
| 168 | |
| 169 | ``-globalsmodref-aa``: Simple mod/ref analysis for globals |
| 170 | ---------------------------------------------------------- |
| 171 | |
| 172 | This simple pass provides alias and mod/ref information for global values that |
| 173 | do not have their address taken, and keeps track of whether functions read or |
| 174 | write memory (are "pure"). For this simple (but very common) case, we can |
| 175 | provide pretty accurate and useful information. |
| 176 | |
| 177 | ``-instcount``: Counts the various types of ``Instruction``\ s |
| 178 | -------------------------------------------------------------- |
| 179 | |
| 180 | This pass collects the count of all instructions and reports them. |
| 181 | |
| 182 | ``-intervals``: Interval Partition Construction |
| 183 | ----------------------------------------------- |
| 184 | |
| 185 | This analysis calculates and represents the interval partition of a function, |
| 186 | or a preexisting interval partition. |
| 187 | |
| 188 | In this way, the interval partition may be used to reduce a flow graph down to |
| 189 | its degenerate single node interval partition (unless it is irreducible). |
| 190 | |
| 191 | ``-iv-users``: Induction Variable Users |
| 192 | --------------------------------------- |
| 193 | |
| 194 | Bookkeeping for "interesting" users of expressions computed from induction |
| 195 | variables. |
| 196 | |
| 197 | ``-lazy-value-info``: Lazy Value Information Analysis |
| 198 | ----------------------------------------------------- |
| 199 | |
| 200 | Interface for lazy computation of value constraint information. |
| 201 | |
| 202 | ``-libcall-aa``: LibCall Alias Analysis |
| 203 | --------------------------------------- |
| 204 | |
| 205 | LibCall Alias Analysis. |
| 206 | |
| 207 | ``-lint``: Statically lint-checks LLVM IR |
| 208 | ----------------------------------------- |
| 209 | |
| 210 | This pass statically checks for common and easily-identified constructs which |
| 211 | produce undefined or likely unintended behavior in LLVM IR. |
| 212 | |
| 213 | It is not a guarantee of correctness, in two ways. First, it isn't |
| 214 | comprehensive. There are checks which could be done statically which are not |
| 215 | yet implemented. Some of these are indicated by TODO comments, but those |
| 216 | aren't comprehensive either. Second, many conditions cannot be checked |
| 217 | statically. This pass does no dynamic instrumentation, so it can't check for |
| 218 | all possible problems. |
| 219 | |
| 220 | Another limitation is that it assumes all code will be executed. A store |
| 221 | through a null pointer in a basic block which is never reached is harmless, but |
| 222 | this pass will warn about it anyway. |
| 223 | |
| 224 | Optimization passes may make conditions that this pass checks for more or less |
| 225 | obvious. If an optimization pass appears to be introducing a warning, it may |
| 226 | be that the optimization pass is merely exposing an existing condition in the |
| 227 | code. |
| 228 | |
| 229 | This code may be run before :ref:`instcombine <passes-instcombine>`. In many |
| 230 | cases, instcombine checks for the same kinds of things and turns instructions |
| 231 | with undefined behavior into unreachable (or equivalent). Because of this, |
| 232 | this pass makes some effort to look through bitcasts and so on. |
| 233 | |
| 234 | ``-loops``: Natural Loop Information |
| 235 | ------------------------------------ |
| 236 | |
| 237 | This analysis is used to identify natural loops and determine the loop depth of |
| 238 | various nodes of the CFG. Note that the loops identified may actually be |
| 239 | several natural loops that share the same header node... not just a single |
| 240 | natural loop. |
| 241 | |
| 242 | ``-memdep``: Memory Dependence Analysis |
| 243 | --------------------------------------- |
| 244 | |
| 245 | An analysis that determines, for a given memory operation, what preceding |
| 246 | memory operations it depends on. It builds on alias analysis information, and |
| 247 | tries to provide a lazy, caching interface to a common kind of alias |
| 248 | information query. |
| 249 | |
| 250 | ``-module-debuginfo``: Decodes module-level debug info |
| 251 | ------------------------------------------------------ |
| 252 | |
| 253 | This pass decodes the debug info metadata in a module and prints in a |
| 254 | (sufficiently-prepared-) human-readable form. |
| 255 | |
| 256 | For example, run this pass from ``opt`` along with the ``-analyze`` option, and |
| 257 | it'll print to standard output. |
| 258 | |
| 259 | ``-no-aa``: No Alias Analysis (always returns 'may' alias) |
| 260 | ---------------------------------------------------------- |
| 261 | |
| 262 | This is the default implementation of the Alias Analysis interface. It always |
| 263 | returns "I don't know" for alias queries. NoAA is unlike other alias analysis |
| 264 | implementations, in that it does not chain to a previous analysis. As such it |
| 265 | doesn't follow many of the rules that other alias analyses must. |
| 266 | |
| 267 | ``-no-profile``: No Profile Information |
| 268 | --------------------------------------- |
| 269 | |
| 270 | The default "no profile" implementation of the abstract ``ProfileInfo`` |
| 271 | interface. |
| 272 | |
| 273 | ``-postdomfrontier``: Post-Dominance Frontier Construction |
| 274 | ---------------------------------------------------------- |
| 275 | |
| 276 | This pass is a simple post-dominator construction algorithm for finding |
| 277 | post-dominator frontiers. |
| 278 | |
| 279 | ``-postdomtree``: Post-Dominator Tree Construction |
| 280 | -------------------------------------------------- |
| 281 | |
| 282 | This pass is a simple post-dominator construction algorithm for finding |
| 283 | post-dominators. |
| 284 | |
| 285 | ``-print-alias-sets``: Alias Set Printer |
| 286 | ---------------------------------------- |
| 287 | |
| 288 | Yet to be written. |
| 289 | |
| 290 | ``-print-callgraph``: Print a call graph |
| 291 | ---------------------------------------- |
| 292 | |
| 293 | This pass, only available in ``opt``, prints the call graph to standard error |
| 294 | in a human-readable form. |
| 295 | |
| 296 | ``-print-callgraph-sccs``: Print SCCs of the Call Graph |
| 297 | ------------------------------------------------------- |
| 298 | |
| 299 | This pass, only available in ``opt``, prints the SCCs of the call graph to |
| 300 | standard error in a human-readable form. |
| 301 | |
| 302 | ``-print-cfg-sccs``: Print SCCs of each function CFG |
| 303 | ---------------------------------------------------- |
| 304 | |
| 305 | This pass, only available in ``opt``, printsthe SCCs of each function CFG to |
| 306 | standard error in a human-readable fom. |
| 307 | |
| 308 | ``-print-dbginfo``: Print debug info in human readable form |
| 309 | ----------------------------------------------------------- |
| 310 | |
| 311 | Pass that prints instructions, and associated debug info: |
| 312 | |
| 313 | #. source/line/col information |
| 314 | #. original variable name |
| 315 | #. original type name |
| 316 | |
| 317 | ``-print-dom-info``: Dominator Info Printer |
| 318 | ------------------------------------------- |
| 319 | |
| 320 | Dominator Info Printer. |
| 321 | |
| 322 | ``-print-externalfnconstants``: Print external fn callsites passed constants |
| 323 | ---------------------------------------------------------------------------- |
| 324 | |
| 325 | This pass, only available in ``opt``, prints out call sites to external |
| 326 | functions that are called with constant arguments. This can be useful when |
| 327 | looking for standard library functions we should constant fold or handle in |
| 328 | alias analyses. |
| 329 | |
| 330 | ``-print-function``: Print function to stderr |
| 331 | --------------------------------------------- |
| 332 | |
| 333 | The ``PrintFunctionPass`` class is designed to be pipelined with other |
| 334 | ``FunctionPasses``, and prints out the functions of the module as they are |
| 335 | processed. |
| 336 | |
| 337 | ``-print-module``: Print module to stderr |
| 338 | ----------------------------------------- |
| 339 | |
| 340 | This pass simply prints out the entire module when it is executed. |
| 341 | |
| 342 | .. _passes-print-used-types: |
| 343 | |
| 344 | ``-print-used-types``: Find Used Types |
| 345 | -------------------------------------- |
| 346 | |
| 347 | This pass is used to seek out all of the types in use by the program. Note |
| 348 | that this analysis explicitly does not include types only used by the symbol |
| 349 | table. |
| 350 | |
| 351 | ``-profile-estimator``: Estimate profiling information |
| 352 | ------------------------------------------------------ |
| 353 | |
| 354 | Profiling information that estimates the profiling information in a very crude |
| 355 | and unimaginative way. |
| 356 | |
| 357 | ``-profile-loader``: Load profile information from ``llvmprof.out`` |
| 358 | ------------------------------------------------------------------- |
| 359 | |
| 360 | A concrete implementation of profiling information that loads the information |
| 361 | from a profile dump file. |
| 362 | |
| 363 | ``-profile-verifier``: Verify profiling information |
| 364 | --------------------------------------------------- |
| 365 | |
| 366 | Pass that checks profiling information for plausibility. |
| 367 | |
| 368 | ``-regions``: Detect single entry single exit regions |
| 369 | ----------------------------------------------------- |
| 370 | |
| 371 | The ``RegionInfo`` pass detects single entry single exit regions in a function, |
| 372 | where a region is defined as any subgraph that is connected to the remaining |
| 373 | graph at only two spots. Furthermore, an hierarchical region tree is built. |
| 374 | |
| 375 | ``-scalar-evolution``: Scalar Evolution Analysis |
| 376 | ------------------------------------------------ |
| 377 | |
| 378 | The ``ScalarEvolution`` analysis can be used to analyze and catagorize scalar |
| 379 | expressions in loops. It specializes in recognizing general induction |
| 380 | variables, representing them with the abstract and opaque ``SCEV`` class. |
| 381 | Given this analysis, trip counts of loops and other important properties can be |
| 382 | obtained. |
| 383 | |
| 384 | This analysis is primarily useful for induction variable substitution and |
| 385 | strength reduction. |
| 386 | |
| 387 | ``-scev-aa``: ScalarEvolution-based Alias Analysis |
| 388 | -------------------------------------------------- |
| 389 | |
| 390 | Simple alias analysis implemented in terms of ``ScalarEvolution`` queries. |
| 391 | |
| 392 | This differs from traditional loop dependence analysis in that it tests for |
| 393 | dependencies within a single iteration of a loop, rather than dependencies |
| 394 | between different iterations. |
| 395 | |
| 396 | ``ScalarEvolution`` has a more complete understanding of pointer arithmetic |
| 397 | than ``BasicAliasAnalysis``' collection of ad-hoc analyses. |
| 398 | |
| 399 | ``-targetdata``: Target Data Layout |
| 400 | ----------------------------------- |
| 401 | |
| 402 | Provides other passes access to information on how the size and alignment |
| 403 | required by the target ABI for various data types. |
| 404 | |
| 405 | Transform Passes |
| 406 | ================ |
| 407 | |
| 408 | This section describes the LLVM Transform Passes. |
| 409 | |
| 410 | ``-adce``: Aggressive Dead Code Elimination |
| 411 | ------------------------------------------- |
| 412 | |
| 413 | ADCE aggressively tries to eliminate code. This pass is similar to :ref:`DCE |
| 414 | <passes-dce>` but it assumes that values are dead until proven otherwise. This |
| 415 | is similar to :ref:`SCCP <passes-sccp>`, except applied to the liveness of |
| 416 | values. |
| 417 | |
| 418 | ``-always-inline``: Inliner for ``always_inline`` functions |
| 419 | ----------------------------------------------------------- |
| 420 | |
| 421 | A custom inliner that handles only functions that are marked as "always |
| 422 | inline". |
| 423 | |
| 424 | ``-argpromotion``: Promote 'by reference' arguments to scalars |
| 425 | -------------------------------------------------------------- |
| 426 | |
| 427 | This pass promotes "by reference" arguments to be "by value" arguments. In |
| 428 | practice, this means looking for internal functions that have pointer |
| 429 | arguments. If it can prove, through the use of alias analysis, that an |
| 430 | argument is *only* loaded, then it can pass the value into the function instead |
| 431 | of the address of the value. This can cause recursive simplification of code |
| 432 | and lead to the elimination of allocas (especially in C++ template code like |
| 433 | the STL). |
| 434 | |
| 435 | This pass also handles aggregate arguments that are passed into a function, |
| 436 | scalarizing them if the elements of the aggregate are only loaded. Note that |
| 437 | it refuses to scalarize aggregates which would require passing in more than |
| 438 | three operands to the function, because passing thousands of operands for a |
| 439 | large array or structure is unprofitable! |
| 440 | |
| 441 | Note that this transformation could also be done for arguments that are only |
| 442 | stored to (returning the value instead), but does not currently. This case |
| 443 | would be best handled when and if LLVM starts supporting multiple return values |
| 444 | from functions. |
| 445 | |
| 446 | ``-bb-vectorize``: Basic-Block Vectorization |
| 447 | -------------------------------------------- |
| 448 | |
| 449 | This pass combines instructions inside basic blocks to form vector |
| 450 | instructions. It iterates over each basic block, attempting to pair compatible |
| 451 | instructions, repeating this process until no additional pairs are selected for |
| 452 | vectorization. When the outputs of some pair of compatible instructions are |
| 453 | used as inputs by some other pair of compatible instructions, those pairs are |
| 454 | part of a potential vectorization chain. Instruction pairs are only fused into |
| 455 | vector instructions when they are part of a chain longer than some threshold |
| 456 | length. Moreover, the pass attempts to find the best possible chain for each |
| 457 | pair of compatible instructions. These heuristics are intended to prevent |
| 458 | vectorization in cases where it would not yield a performance increase of the |
| 459 | resulting code. |
| 460 | |
| 461 | ``-block-placement``: Profile Guided Basic Block Placement |
| 462 | ---------------------------------------------------------- |
| 463 | |
| 464 | This pass is a very simple profile guided basic block placement algorithm. The |
| 465 | idea is to put frequently executed blocks together at the start of the function |
| 466 | and hopefully increase the number of fall-through conditional branches. If |
| 467 | there is no profile information for a particular function, this pass basically |
| 468 | orders blocks in depth-first order. |
| 469 | |
| 470 | ``-break-crit-edges``: Break critical edges in CFG |
| 471 | -------------------------------------------------- |
| 472 | |
| 473 | Break all of the critical edges in the CFG by inserting a dummy basic block. |
| 474 | It may be "required" by passes that cannot deal with critical edges. This |
| 475 | transformation obviously invalidates the CFG, but can update forward dominator |
| 476 | (set, immediate dominators, tree, and frontier) information. |
| 477 | |
| 478 | ``-codegenprepare``: Optimize for code generation |
| 479 | ------------------------------------------------- |
| 480 | |
| 481 | This pass munges the code in the input function to better prepare it for |
| 482 | SelectionDAG-based code generation. This works around limitations in it's |
| 483 | basic-block-at-a-time approach. It should eventually be removed. |
| 484 | |
| 485 | ``-constmerge``: Merge Duplicate Global Constants |
| 486 | ------------------------------------------------- |
| 487 | |
| 488 | Merges duplicate global constants together into a single constant that is |
| 489 | shared. This is useful because some passes (i.e., TraceValues) insert a lot of |
| 490 | string constants into the program, regardless of whether or not an existing |
| 491 | string is available. |
| 492 | |
| 493 | ``-constprop``: Simple constant propagation |
| 494 | ------------------------------------------- |
| 495 | |
| 496 | This file implements constant propagation and merging. It looks for |
| 497 | instructions involving only constant operands and replaces them with a constant |
| 498 | value instead of an instruction. For example: |
| 499 | |
| 500 | .. code-block:: llvm |
| 501 | |
| 502 | add i32 1, 2 |
| 503 | |
| 504 | becomes |
| 505 | |
| 506 | .. code-block:: llvm |
| 507 | |
| 508 | i32 3 |
| 509 | |
| 510 | NOTE: this pass has a habit of making definitions be dead. It is a good idea |
| 511 | to to run a :ref:`Dead Instruction Elimination <passes-die>` pass sometime |
| 512 | after running this pass. |
| 513 | |
| 514 | .. _passes-dce: |
| 515 | |
| 516 | ``-dce``: Dead Code Elimination |
| 517 | ------------------------------- |
| 518 | |
| 519 | Dead code elimination is similar to :ref:`dead instruction elimination |
| 520 | <passes-die>`, but it rechecks instructions that were used by removed |
| 521 | instructions to see if they are newly dead. |
| 522 | |
| 523 | ``-deadargelim``: Dead Argument Elimination |
| 524 | ------------------------------------------- |
| 525 | |
| 526 | This pass deletes dead arguments from internal functions. Dead argument |
| 527 | elimination removes arguments which are directly dead, as well as arguments |
| 528 | only passed into function calls as dead arguments of other functions. This |
| 529 | pass also deletes dead arguments in a similar way. |
| 530 | |
| 531 | This pass is often useful as a cleanup pass to run after aggressive |
| 532 | interprocedural passes, which add possibly-dead arguments. |
| 533 | |
| 534 | ``-deadtypeelim``: Dead Type Elimination |
| 535 | ---------------------------------------- |
| 536 | |
| 537 | This pass is used to cleanup the output of GCC. It eliminate names for types |
| 538 | that are unused in the entire translation unit, using the :ref:`find used types |
| 539 | <passes-print-used-types>` pass. |
| 540 | |
| 541 | .. _passes-die: |
| 542 | |
| 543 | ``-die``: Dead Instruction Elimination |
| 544 | -------------------------------------- |
| 545 | |
| 546 | Dead instruction elimination performs a single pass over the function, removing |
| 547 | instructions that are obviously dead. |
| 548 | |
| 549 | ``-dse``: Dead Store Elimination |
| 550 | -------------------------------- |
| 551 | |
| 552 | A trivial dead store elimination that only considers basic-block local |
| 553 | redundant stores. |
| 554 | |
| 555 | ``-functionattrs``: Deduce function attributes |
| 556 | ---------------------------------------------- |
| 557 | |
| 558 | A simple interprocedural pass which walks the call-graph, looking for functions |
| 559 | which do not access or only read non-local memory, and marking them |
| 560 | ``readnone``/``readonly``. In addition, it marks function arguments (of |
| 561 | pointer type) "``nocapture``" if a call to the function does not create any |
| 562 | copies of the pointer value that outlive the call. This more or less means |
| 563 | that the pointer is only dereferenced, and not returned from the function or |
| 564 | stored in a global. This pass is implemented as a bottom-up traversal of the |
| 565 | call-graph. |
| 566 | |
| 567 | ``-globaldce``: Dead Global Elimination |
| 568 | --------------------------------------- |
| 569 | |
| 570 | This transform is designed to eliminate unreachable internal globals from the |
| 571 | program. It uses an aggressive algorithm, searching out globals that are known |
| 572 | to be alive. After it finds all of the globals which are needed, it deletes |
| 573 | whatever is left over. This allows it to delete recursive chunks of the |
| 574 | program which are unreachable. |
| 575 | |
| 576 | ``-globalopt``: Global Variable Optimizer |
| 577 | ----------------------------------------- |
| 578 | |
| 579 | This pass transforms simple global variables that never have their address |
| 580 | taken. If obviously true, it marks read/write globals as constant, deletes |
| 581 | variables only stored to, etc. |
| 582 | |
| 583 | ``-gvn``: Global Value Numbering |
| 584 | -------------------------------- |
| 585 | |
| 586 | This pass performs global value numbering to eliminate fully and partially |
| 587 | redundant instructions. It also performs redundant load elimination. |
| 588 | |
| 589 | .. _passes-indvars: |
| 590 | |
| 591 | ``-indvars``: Canonicalize Induction Variables |
| 592 | ---------------------------------------------- |
| 593 | |
| 594 | This transformation analyzes and transforms the induction variables (and |
| 595 | computations derived from them) into simpler forms suitable for subsequent |
| 596 | analysis and transformation. |
| 597 | |
| 598 | This transformation makes the following changes to each loop with an |
| 599 | identifiable induction variable: |
| 600 | |
| 601 | * All loops are transformed to have a *single* canonical induction variable |
| 602 | which starts at zero and steps by one. |
| 603 | * The canonical induction variable is guaranteed to be the first PHI node in |
| 604 | the loop header block. |
| 605 | * Any pointer arithmetic recurrences are raised to use array subscripts. |
| 606 | |
| 607 | If the trip count of a loop is computable, this pass also makes the following |
| 608 | changes: |
| 609 | |
| 610 | * The exit condition for the loop is canonicalized to compare the induction |
| 611 | value against the exit value. This turns loops like: |
| 612 | |
| 613 | .. code-block:: c++ |
| 614 | |
| 615 | for (i = 7; i*i < 1000; ++i) |
| 616 | |
| 617 | into |
| 618 | |
| 619 | .. code-block:: c++ |
| 620 | |
| 621 | for (i = 0; i != 25; ++i) |
| 622 | |
| 623 | * Any use outside of the loop of an expression derived from the indvar is |
| 624 | changed to compute the derived value outside of the loop, eliminating the |
| 625 | dependence on the exit value of the induction variable. If the only purpose |
| 626 | of the loop is to compute the exit value of some derived expression, this |
| 627 | transformation will make the loop dead. |
| 628 | |
| 629 | This transformation should be followed by strength reduction after all of the |
| 630 | desired loop transformations have been performed. Additionally, on targets |
| 631 | where it is profitable, the loop could be transformed to count down to zero |
| 632 | (the "do loop" optimization). |
| 633 | |
| 634 | ``-inline``: Function Integration/Inlining |
| 635 | ------------------------------------------ |
| 636 | |
| 637 | Bottom-up inlining of functions into callees. |
| 638 | |
| 639 | ``-insert-edge-profiling``: Insert instrumentation for edge profiling |
| 640 | --------------------------------------------------------------------- |
| 641 | |
| 642 | This pass instruments the specified program with counters for edge profiling. |
| 643 | Edge profiling can give a reasonable approximation of the hot paths through a |
| 644 | program, and is used for a wide variety of program transformations. |
| 645 | |
| 646 | Note that this implementation is very naïve. It inserts a counter for *every* |
| 647 | edge in the program, instead of using control flow information to prune the |
| 648 | number of counters inserted. |
| 649 | |
| 650 | ``-insert-optimal-edge-profiling``: Insert optimal instrumentation for edge profiling |
| 651 | ------------------------------------------------------------------------------------- |
| 652 | |
| 653 | This pass instruments the specified program with counters for edge profiling. |
| 654 | Edge profiling can give a reasonable approximation of the hot paths through a |
| 655 | program, and is used for a wide variety of program transformations. |
| 656 | |
| 657 | .. _passes-instcombine: |
| 658 | |
| 659 | ``-instcombine``: Combine redundant instructions |
| 660 | ------------------------------------------------ |
| 661 | |
| 662 | Combine instructions to form fewer, simple instructions. This pass does not |
| 663 | modify the CFG This pass is where algebraic simplification happens. |
| 664 | |
| 665 | This pass combines things like: |
| 666 | |
| 667 | .. code-block:: llvm |
| 668 | |
| 669 | %Y = add i32 %X, 1 |
| 670 | %Z = add i32 %Y, 1 |
| 671 | |
| 672 | into: |
| 673 | |
| 674 | .. code-block:: llvm |
| 675 | |
| 676 | %Z = add i32 %X, 2 |
| 677 | |
| 678 | This is a simple worklist driven algorithm. |
| 679 | |
| 680 | This pass guarantees that the following canonicalizations are performed on the |
| 681 | program: |
| 682 | |
| 683 | #. If a binary operator has a constant operand, it is moved to the right-hand |
| 684 | side. |
| 685 | #. Bitwise operators with constant operands are always grouped so that shifts |
| 686 | are performed first, then ``or``\ s, then ``and``\ s, then ``xor``\ s. |
| 687 | #. Compare instructions are converted from ``<``, ``>``, ``≤``, or ``≥`` to |
| 688 | ``=`` or ``≠`` if possible. |
| 689 | #. All ``cmp`` instructions on boolean values are replaced with logical |
| 690 | operations. |
| 691 | #. ``add X, X`` is represented as ``mul X, 2`` ⇒ ``shl X, 1`` |
| 692 | #. Multiplies with a constant power-of-two argument are transformed into |
| 693 | shifts. |
| 694 | #. … etc. |
| 695 | |
| 696 | ``-internalize``: Internalize Global Symbols |
| 697 | -------------------------------------------- |
| 698 | |
| 699 | This pass loops over all of the functions in the input module, looking for a |
| 700 | main function. If a main function is found, all other functions and all global |
| 701 | variables with initializers are marked as internal. |
| 702 | |
| 703 | ``-ipconstprop``: Interprocedural constant propagation |
| 704 | ------------------------------------------------------ |
| 705 | |
| 706 | This pass implements an *extremely* simple interprocedural constant propagation |
| 707 | pass. It could certainly be improved in many different ways, like using a |
| 708 | worklist. This pass makes arguments dead, but does not remove them. The |
| 709 | existing dead argument elimination pass should be run after this to clean up |
| 710 | the mess. |
| 711 | |
| 712 | ``-ipsccp``: Interprocedural Sparse Conditional Constant Propagation |
| 713 | -------------------------------------------------------------------- |
| 714 | |
| 715 | An interprocedural variant of :ref:`Sparse Conditional Constant Propagation |
| 716 | <passes-sccp>`. |
| 717 | |
| 718 | ``-jump-threading``: Jump Threading |
| 719 | ----------------------------------- |
| 720 | |
| 721 | Jump threading tries to find distinct threads of control flow running through a |
| 722 | basic block. This pass looks at blocks that have multiple predecessors and |
| 723 | multiple successors. If one or more of the predecessors of the block can be |
| 724 | proven to always cause a jump to one of the successors, we forward the edge |
| 725 | from the predecessor to the successor by duplicating the contents of this |
| 726 | block. |
| 727 | |
| 728 | An example of when this can occur is code like this: |
| 729 | |
| 730 | .. code-block:: c++ |
| 731 | |
| 732 | if () { ... |
| 733 | X = 4; |
| 734 | } |
| 735 | if (X < 3) { |
| 736 | |
| 737 | In this case, the unconditional branch at the end of the first if can be |
| 738 | revectored to the false side of the second if. |
| 739 | |
| 740 | ``-lcssa``: Loop-Closed SSA Form Pass |
| 741 | ------------------------------------- |
| 742 | |
| 743 | This pass transforms loops by placing phi nodes at the end of the loops for all |
| 744 | values that are live across the loop boundary. For example, it turns the left |
| 745 | into the right code: |
| 746 | |
| 747 | .. code-block:: c++ |
| 748 | |
| 749 | for (...) for (...) |
| 750 | if (c) if (c) |
| 751 | X1 = ... X1 = ... |
| 752 | else else |
| 753 | X2 = ... X2 = ... |
| 754 | X3 = phi(X1, X2) X3 = phi(X1, X2) |
| 755 | ... = X3 + 4 X4 = phi(X3) |
| 756 | ... = X4 + 4 |
| 757 | |
| 758 | This is still valid LLVM; the extra phi nodes are purely redundant, and will be |
| 759 | trivially eliminated by ``InstCombine``. The major benefit of this |
| 760 | transformation is that it makes many other loop optimizations, such as |
| 761 | ``LoopUnswitch``\ ing, simpler. |
| 762 | |
| 763 | .. _passes-licm: |
| 764 | |
| 765 | ``-licm``: Loop Invariant Code Motion |
| 766 | ------------------------------------- |
| 767 | |
| 768 | This pass performs loop invariant code motion, attempting to remove as much |
| 769 | code from the body of a loop as possible. It does this by either hoisting code |
| 770 | into the preheader block, or by sinking code to the exit blocks if it is safe. |
| 771 | This pass also promotes must-aliased memory locations in the loop to live in |
| 772 | registers, thus hoisting and sinking "invariant" loads and stores. |
| 773 | |
| 774 | This pass uses alias analysis for two purposes: |
| 775 | |
| 776 | #. Moving loop invariant loads and calls out of loops. If we can determine |
| 777 | that a load or call inside of a loop never aliases anything stored to, we |
| 778 | can hoist it or sink it like any other instruction. |
| 779 | |
| 780 | #. Scalar Promotion of Memory. If there is a store instruction inside of the |
| 781 | loop, we try to move the store to happen AFTER the loop instead of inside of |
| 782 | the loop. This can only happen if a few conditions are true: |
| 783 | |
| 784 | #. The pointer stored through is loop invariant. |
| 785 | #. There are no stores or loads in the loop which *may* alias the pointer. |
| 786 | There are no calls in the loop which mod/ref the pointer. |
| 787 | |
| 788 | If these conditions are true, we can promote the loads and stores in the |
| 789 | loop of the pointer to use a temporary alloca'd variable. We then use the |
| 790 | :ref:`mem2reg <passes-mem2reg>` functionality to construct the appropriate |
| 791 | SSA form for the variable. |
| 792 | |
| 793 | ``-loop-deletion``: Delete dead loops |
| 794 | ------------------------------------- |
| 795 | |
| 796 | This file implements the Dead Loop Deletion Pass. This pass is responsible for |
| 797 | eliminating loops with non-infinite computable trip counts that have no side |
| 798 | effects or volatile instructions, and do not contribute to the computation of |
| 799 | the function's return value. |
| 800 | |
| 801 | .. _passes-loop-extract: |
| 802 | |
| 803 | ``-loop-extract``: Extract loops into new functions |
| 804 | --------------------------------------------------- |
| 805 | |
| 806 | A pass wrapper around the ``ExtractLoop()`` scalar transformation to extract |
| 807 | each top-level loop into its own new function. If the loop is the *only* loop |
| 808 | in a given function, it is not touched. This is a pass most useful for |
| 809 | debugging via bugpoint. |
| 810 | |
| 811 | ``-loop-extract-single``: Extract at most one loop into a new function |
| 812 | ---------------------------------------------------------------------- |
| 813 | |
| 814 | Similar to :ref:`Extract loops into new functions <passes-loop-extract>`, this |
| 815 | pass extracts one natural loop from the program into a function if it can. |
| 816 | This is used by :program:`bugpoint`. |
| 817 | |
| 818 | ``-loop-reduce``: Loop Strength Reduction |
| 819 | ----------------------------------------- |
| 820 | |
| 821 | This pass performs a strength reduction on array references inside loops that |
| 822 | have as one or more of their components the loop induction variable. This is |
| 823 | accomplished by creating a new value to hold the initial value of the array |
| 824 | access for the first iteration, and then creating a new GEP instruction in the |
| 825 | loop to increment the value by the appropriate amount. |
| 826 | |
| 827 | ``-loop-rotate``: Rotate Loops |
| 828 | ------------------------------ |
| 829 | |
| 830 | A simple loop rotation transformation. |
| 831 | |
| 832 | ``-loop-simplify``: Canonicalize natural loops |
| 833 | ---------------------------------------------- |
| 834 | |
| 835 | This pass performs several transformations to transform natural loops into a |
| 836 | simpler form, which makes subsequent analyses and transformations simpler and |
| 837 | more effective. |
| 838 | |
| 839 | Loop pre-header insertion guarantees that there is a single, non-critical entry |
| 840 | edge from outside of the loop to the loop header. This simplifies a number of |
| 841 | analyses and transformations, such as :ref:`LICM <passes-licm>`. |
| 842 | |
| 843 | Loop exit-block insertion guarantees that all exit blocks from the loop (blocks |
| 844 | which are outside of the loop that have predecessors inside of the loop) only |
| 845 | have predecessors from inside of the loop (and are thus dominated by the loop |
| 846 | header). This simplifies transformations such as store-sinking that are built |
| 847 | into LICM. |
| 848 | |
| 849 | This pass also guarantees that loops will have exactly one backedge. |
| 850 | |
| 851 | Note that the :ref:`simplifycfg <passes-simplifycfg>` pass will clean up blocks |
| 852 | which are split out but end up being unnecessary, so usage of this pass should |
| 853 | not pessimize generated code. |
| 854 | |
| 855 | This pass obviously modifies the CFG, but updates loop information and |
| 856 | dominator information. |
| 857 | |
| 858 | ``-loop-unroll``: Unroll loops |
| 859 | ------------------------------ |
| 860 | |
| 861 | This pass implements a simple loop unroller. It works best when loops have |
| 862 | been canonicalized by the :ref:`indvars <passes-indvars>` pass, allowing it to |
| 863 | determine the trip counts of loops easily. |
| 864 | |
| 865 | ``-loop-unswitch``: Unswitch loops |
| 866 | ---------------------------------- |
| 867 | |
| 868 | This pass transforms loops that contain branches on loop-invariant conditions |
| 869 | to have multiple loops. For example, it turns the left into the right code: |
| 870 | |
| 871 | .. code-block:: c++ |
| 872 | |
| 873 | for (...) if (lic) |
| 874 | A for (...) |
| 875 | if (lic) A; B; C |
| 876 | B else |
| 877 | C for (...) |
| 878 | A; C |
| 879 | |
| 880 | This can increase the size of the code exponentially (doubling it every time a |
| 881 | loop is unswitched) so we only unswitch if the resultant code will be smaller |
| 882 | than a threshold. |
| 883 | |
| 884 | This pass expects :ref:`LICM <passes-licm>` to be run before it to hoist |
| 885 | invariant conditions out of the loop, to make the unswitching opportunity |
| 886 | obvious. |
| 887 | |
| 888 | ``-loweratomic``: Lower atomic intrinsics to non-atomic form |
| 889 | ------------------------------------------------------------ |
| 890 | |
| 891 | This pass lowers atomic intrinsics to non-atomic form for use in a known |
| 892 | non-preemptible environment. |
| 893 | |
| 894 | The pass does not verify that the environment is non-preemptible (in general |
| 895 | this would require knowledge of the entire call graph of the program including |
| 896 | any libraries which may not be available in bitcode form); it simply lowers |
| 897 | every atomic intrinsic. |
| 898 | |
| 899 | ``-lowerinvoke``: Lower invoke and unwind, for unwindless code generators |
| 900 | ------------------------------------------------------------------------- |
| 901 | |
| 902 | This transformation is designed for use by code generators which do not yet |
| 903 | support stack unwinding. This pass supports two models of exception handling |
| 904 | lowering, the "cheap" support and the "expensive" support. |
| 905 | |
| 906 | "Cheap" exception handling support gives the program the ability to execute any |
| 907 | program which does not "throw an exception", by turning "``invoke``" |
| 908 | instructions into calls and by turning "``unwind``" instructions into calls to |
| 909 | ``abort()``. If the program does dynamically use the "``unwind``" instruction, |
| 910 | the program will print a message then abort. |
| 911 | |
| 912 | "Expensive" exception handling support gives the full exception handling |
| 913 | support to the program at the cost of making the "``invoke``" instruction |
| 914 | really expensive. It basically inserts ``setjmp``/``longjmp`` calls to emulate |
| 915 | the exception handling as necessary. |
| 916 | |
| 917 | Because the "expensive" support slows down programs a lot, and EH is only used |
| 918 | for a subset of the programs, it must be specifically enabled by the |
| 919 | ``-enable-correct-eh-support`` option. |
| 920 | |
| 921 | Note that after this pass runs the CFG is not entirely accurate (exceptional |
| 922 | control flow edges are not correct anymore) so only very simple things should |
| 923 | be done after the ``lowerinvoke`` pass has run (like generation of native |
| 924 | code). This should not be used as a general purpose "my LLVM-to-LLVM pass |
| 925 | doesn't support the ``invoke`` instruction yet" lowering pass. |
| 926 | |
| 927 | ``-lowerswitch``: Lower ``SwitchInst``\ s to branches |
| 928 | ----------------------------------------------------- |
| 929 | |
| 930 | Rewrites switch instructions with a sequence of branches, which allows targets |
| 931 | to get away with not implementing the switch instruction until it is |
| 932 | convenient. |
| 933 | |
| 934 | .. _passes-mem2reg: |
| 935 | |
| 936 | ``-mem2reg``: Promote Memory to Register |
| 937 | ---------------------------------------- |
| 938 | |
| 939 | This file promotes memory references to be register references. It promotes |
| 940 | alloca instructions which only have loads and stores as uses. An ``alloca`` is |
| 941 | transformed by using dominator frontiers to place phi nodes, then traversing |
| 942 | the function in depth-first order to rewrite loads and stores as appropriate. |
| 943 | This is just the standard SSA construction algorithm to construct "pruned" SSA |
| 944 | form. |
| 945 | |
| 946 | ``-memcpyopt``: MemCpy Optimization |
| 947 | ----------------------------------- |
| 948 | |
| 949 | This pass performs various transformations related to eliminating ``memcpy`` |
| 950 | calls, or transforming sets of stores into ``memset``\ s. |
| 951 | |
| 952 | ``-mergefunc``: Merge Functions |
| 953 | ------------------------------- |
| 954 | |
| 955 | This pass looks for equivalent functions that are mergable and folds them. |
| 956 | |
| 957 | A hash is computed from the function, based on its type and number of basic |
| 958 | blocks. |
| 959 | |
| 960 | Once all hashes are computed, we perform an expensive equality comparison on |
| 961 | each function pair. This takes n^2/2 comparisons per bucket, so it's important |
| 962 | that the hash function be high quality. The equality comparison iterates |
| 963 | through each instruction in each basic block. |
| 964 | |
| 965 | When a match is found the functions are folded. If both functions are |
| 966 | overridable, we move the functionality into a new internal function and leave |
| 967 | two overridable thunks to it. |
| 968 | |
| 969 | ``-mergereturn``: Unify function exit nodes |
| 970 | ------------------------------------------- |
| 971 | |
| 972 | Ensure that functions have at most one ``ret`` instruction in them. |
| 973 | Additionally, it keeps track of which node is the new exit node of the CFG. |
| 974 | |
| 975 | ``-partial-inliner``: Partial Inliner |
| 976 | ------------------------------------- |
| 977 | |
| 978 | This pass performs partial inlining, typically by inlining an ``if`` statement |
| 979 | that surrounds the body of the function. |
| 980 | |
| 981 | ``-prune-eh``: Remove unused exception handling info |
| 982 | ---------------------------------------------------- |
| 983 | |
| 984 | This file implements a simple interprocedural pass which walks the call-graph, |
| 985 | turning invoke instructions into call instructions if and only if the callee |
| 986 | cannot throw an exception. It implements this as a bottom-up traversal of the |
| 987 | call-graph. |
| 988 | |
| 989 | ``-reassociate``: Reassociate expressions |
| 990 | ----------------------------------------- |
| 991 | |
| 992 | This pass reassociates commutative expressions in an order that is designed to |
| 993 | promote better constant propagation, GCSE, :ref:`LICM <passes-licm>`, PRE, etc. |
| 994 | |
| 995 | For example: 4 + (x + 5) ⇒ x + (4 + 5) |
| 996 | |
| 997 | In the implementation of this algorithm, constants are assigned rank = 0, |
| 998 | function arguments are rank = 1, and other values are assigned ranks |
| 999 | corresponding to the reverse post order traversal of current function (starting |
| 1000 | at 2), which effectively gives values in deep loops higher rank than values not |
| 1001 | in loops. |
| 1002 | |
| 1003 | ``-reg2mem``: Demote all values to stack slots |
| 1004 | ---------------------------------------------- |
| 1005 | |
| 1006 | This file demotes all registers to memory references. It is intended to be the |
| 1007 | inverse of :ref:`mem2reg <passes-mem2reg>`. By converting to ``load`` |
| 1008 | instructions, the only values live across basic blocks are ``alloca`` |
| 1009 | instructions and ``load`` instructions before ``phi`` nodes. It is intended |
| 1010 | that this should make CFG hacking much easier. To make later hacking easier, |
| 1011 | the entry block is split into two, such that all introduced ``alloca`` |
| 1012 | instructions (and nothing else) are in the entry block. |
| 1013 | |
| 1014 | ``-scalarrepl``: Scalar Replacement of Aggregates (DT) |
| 1015 | ------------------------------------------------------ |
| 1016 | |
| 1017 | The well-known scalar replacement of aggregates transformation. This transform |
| 1018 | breaks up ``alloca`` instructions of aggregate type (structure or array) into |
| 1019 | individual ``alloca`` instructions for each member if possible. Then, if |
| 1020 | possible, it transforms the individual ``alloca`` instructions into nice clean |
| 1021 | scalar SSA form. |
| 1022 | |
| 1023 | This combines a simple scalar replacement of aggregates algorithm with the |
| 1024 | :ref:`mem2reg <passes-mem2reg>` algorithm because often interact, especially |
| 1025 | for C++ programs. As such, iterating between ``scalarrepl``, then |
| 1026 | :ref:`mem2reg <passes-mem2reg>` until we run out of things to promote works |
| 1027 | well. |
| 1028 | |
| 1029 | .. _passes-sccp: |
| 1030 | |
| 1031 | ``-sccp``: Sparse Conditional Constant Propagation |
| 1032 | -------------------------------------------------- |
| 1033 | |
| 1034 | Sparse conditional constant propagation and merging, which can be summarized |
| 1035 | as: |
| 1036 | |
| 1037 | * Assumes values are constant unless proven otherwise |
| 1038 | * Assumes BasicBlocks are dead unless proven otherwise |
| 1039 | * Proves values to be constant, and replaces them with constants |
| 1040 | * Proves conditional branches to be unconditional |
| 1041 | |
| 1042 | Note that this pass has a habit of making definitions be dead. It is a good |
| 1043 | idea to to run a :ref:`DCE <passes-dce>` pass sometime after running this pass. |
| 1044 | |
| 1045 | ``-simplify-libcalls``: Simplify well-known library calls |
| 1046 | --------------------------------------------------------- |
| 1047 | |
| 1048 | Applies a variety of small optimizations for calls to specific well-known |
| 1049 | function calls (e.g. runtime library functions). For example, a call |
| 1050 | ``exit(3)`` that occurs within the ``main()`` function can be transformed into |
| 1051 | simply ``return 3``. |
| 1052 | |
| 1053 | .. _passes-simplifycfg: |
| 1054 | |
| 1055 | ``-simplifycfg``: Simplify the CFG |
| 1056 | ---------------------------------- |
| 1057 | |
| 1058 | Performs dead code elimination and basic block merging. Specifically: |
| 1059 | |
| 1060 | * Removes basic blocks with no predecessors. |
| 1061 | * Merges a basic block into its predecessor if there is only one and the |
| 1062 | predecessor only has one successor. |
| 1063 | * Eliminates PHI nodes for basic blocks with a single predecessor. |
| 1064 | * Eliminates a basic block that only contains an unconditional branch. |
| 1065 | |
| 1066 | ``-sink``: Code sinking |
| 1067 | ----------------------- |
| 1068 | |
| 1069 | This pass moves instructions into successor blocks, when possible, so that they |
| 1070 | aren't executed on paths where their results aren't needed. |
| 1071 | |
| 1072 | ``-strip``: Strip all symbols from a module |
| 1073 | ------------------------------------------- |
| 1074 | |
| 1075 | Performs code stripping. This transformation can delete: |
| 1076 | |
| 1077 | * names for virtual registers |
| 1078 | * symbols for internal globals and functions |
| 1079 | * debug information |
| 1080 | |
| 1081 | Note that this transformation makes code much less readable, so it should only |
| 1082 | be used in situations where the strip utility would be used, such as reducing |
| 1083 | code size or making it harder to reverse engineer code. |
| 1084 | |
| 1085 | ``-strip-dead-debug-info``: Strip debug info for unused symbols |
| 1086 | --------------------------------------------------------------- |
| 1087 | |
| 1088 | .. FIXME: this description is the same as for -strip |
| 1089 | |
| 1090 | performs code stripping. this transformation can delete: |
| 1091 | |
| 1092 | * names for virtual registers |
| 1093 | * symbols for internal globals and functions |
| 1094 | * debug information |
| 1095 | |
| 1096 | note that this transformation makes code much less readable, so it should only |
| 1097 | be used in situations where the strip utility would be used, such as reducing |
| 1098 | code size or making it harder to reverse engineer code. |
| 1099 | |
| 1100 | ``-strip-dead-prototypes``: Strip Unused Function Prototypes |
| 1101 | ------------------------------------------------------------ |
| 1102 | |
| 1103 | This pass loops over all of the functions in the input module, looking for dead |
| 1104 | declarations and removes them. Dead declarations are declarations of functions |
| 1105 | for which no implementation is available (i.e., declarations for unused library |
| 1106 | functions). |
| 1107 | |
| 1108 | ``-strip-debug-declare``: Strip all ``llvm.dbg.declare`` intrinsics |
| 1109 | ------------------------------------------------------------------- |
| 1110 | |
| 1111 | .. FIXME: this description is the same as for -strip |
| 1112 | |
| 1113 | This pass implements code stripping. Specifically, it can delete: |
| 1114 | |
| 1115 | #. names for virtual registers |
| 1116 | #. symbols for internal globals and functions |
| 1117 | #. debug information |
| 1118 | |
| 1119 | Note that this transformation makes code much less readable, so it should only |
| 1120 | be used in situations where the 'strip' utility would be used, such as reducing |
| 1121 | code size or making it harder to reverse engineer code. |
| 1122 | |
| 1123 | ``-strip-nondebug``: Strip all symbols, except dbg symbols, from a module |
| 1124 | ------------------------------------------------------------------------- |
| 1125 | |
| 1126 | .. FIXME: this description is the same as for -strip |
| 1127 | |
| 1128 | This pass implements code stripping. Specifically, it can delete: |
| 1129 | |
| 1130 | #. names for virtual registers |
| 1131 | #. symbols for internal globals and functions |
| 1132 | #. debug information |
| 1133 | |
| 1134 | Note that this transformation makes code much less readable, so it should only |
| 1135 | be used in situations where the 'strip' utility would be used, such as reducing |
| 1136 | code size or making it harder to reverse engineer code. |
| 1137 | |
| 1138 | ``-tailcallelim``: Tail Call Elimination |
| 1139 | ---------------------------------------- |
| 1140 | |
| 1141 | This file transforms calls of the current function (self recursion) followed by |
| 1142 | a return instruction with a branch to the entry of the function, creating a |
| 1143 | loop. This pass also implements the following extensions to the basic |
| 1144 | algorithm: |
| 1145 | |
| 1146 | #. Trivial instructions between the call and return do not prevent the |
| 1147 | transformation from taking place, though currently the analysis cannot |
| 1148 | support moving any really useful instructions (only dead ones). |
| 1149 | #. This pass transforms functions that are prevented from being tail recursive |
| 1150 | by an associative expression to use an accumulator variable, thus compiling |
| 1151 | the typical naive factorial or fib implementation into efficient code. |
| 1152 | #. TRE is performed if the function returns void, if the return returns the |
| 1153 | result returned by the call, or if the function returns a run-time constant |
| 1154 | on all exits from the function. It is possible, though unlikely, that the |
| 1155 | return returns something else (like constant 0), and can still be TRE'd. It |
| 1156 | can be TRE'd if *all other* return instructions in the function return the |
| 1157 | exact same value. |
| 1158 | #. If it can prove that callees do not access theier caller stack frame, they |
| 1159 | are marked as eligible for tail call elimination (by the code generator). |
| 1160 | |
| 1161 | Utility Passes |
| 1162 | ============== |
| 1163 | |
| 1164 | This section describes the LLVM Utility Passes. |
| 1165 | |
| 1166 | ``-deadarghaX0r``: Dead Argument Hacking (BUGPOINT USE ONLY; DO NOT USE) |
| 1167 | ------------------------------------------------------------------------ |
| 1168 | |
| 1169 | Same as dead argument elimination, but deletes arguments to functions which are |
| 1170 | external. This is only for use by :doc:`bugpoint <Bugpoint>`. |
| 1171 | |
| 1172 | ``-extract-blocks``: Extract Basic Blocks From Module (for bugpoint use) |
| 1173 | ------------------------------------------------------------------------ |
| 1174 | |
| 1175 | This pass is used by bugpoint to extract all blocks from the module into their |
| 1176 | own functions. |
| 1177 | |
| 1178 | ``-instnamer``: Assign names to anonymous instructions |
| 1179 | ------------------------------------------------------ |
| 1180 | |
| 1181 | This is a little utility pass that gives instructions names, this is mostly |
| 1182 | useful when diffing the effect of an optimization because deleting an unnamed |
| 1183 | instruction can change all other instruction numbering, making the diff very |
| 1184 | noisy. |
| 1185 | |
| 1186 | ``-preverify``: Preliminary module verification |
| 1187 | ----------------------------------------------- |
| 1188 | |
| 1189 | Ensures that the module is in the form required by the :ref:`Module Verifier |
| 1190 | <passes-verify>` pass. Running the verifier runs this pass automatically, so |
| 1191 | there should be no need to use it directly. |
| 1192 | |
| 1193 | .. _passes-verify: |
| 1194 | |
| 1195 | ``-verify``: Module Verifier |
| 1196 | ---------------------------- |
| 1197 | |
| 1198 | Verifies an LLVM IR code. This is useful to run after an optimization which is |
| 1199 | undergoing testing. Note that llvm-as verifies its input before emitting |
| 1200 | bitcode, and also that malformed bitcode is likely to make LLVM crash. All |
| 1201 | language front-ends are therefore encouraged to verify their output before |
| 1202 | performing optimizing transformations. |
| 1203 | |
| 1204 | #. Both of a binary operator's parameters are of the same type. |
| 1205 | #. Verify that the indices of mem access instructions match other operands. |
| 1206 | #. Verify that arithmetic and other things are only performed on first-class |
| 1207 | types. Verify that shifts and logicals only happen on integrals f.e. |
| 1208 | #. All of the constants in a switch statement are of the correct type. |
| 1209 | #. The code is in valid SSA form. |
| 1210 | #. It is illegal to put a label into any other type (like a structure) or to |
| 1211 | return one. |
| 1212 | #. Only phi nodes can be self referential: ``%x = add i32 %x``, ``%x`` is |
| 1213 | invalid. |
| 1214 | #. PHI nodes must have an entry for each predecessor, with no extras. |
| 1215 | #. PHI nodes must be the first thing in a basic block, all grouped together. |
| 1216 | #. PHI nodes must have at least one entry. |
| 1217 | #. All basic blocks should only end with terminator insts, not contain them. |
| 1218 | #. The entry node to a function must not have predecessors. |
| 1219 | #. All Instructions must be embedded into a basic block. |
| 1220 | #. Functions cannot take a void-typed parameter. |
| 1221 | #. Verify that a function's argument list agrees with its declared type. |
| 1222 | #. It is illegal to specify a name for a void value. |
| 1223 | #. It is illegal to have an internal global value with no initializer. |
| 1224 | #. It is illegal to have a ``ret`` instruction that returns a value that does |
| 1225 | not agree with the function return value type. |
| 1226 | #. Function call argument types match the function prototype. |
| 1227 | #. All other things that are tested by asserts spread about the code. |
| 1228 | |
| 1229 | Note that this does not provide full security verification (like Java), but |
| 1230 | instead just tries to ensure that code is well-formed. |
| 1231 | |
| 1232 | ``-view-cfg``: View CFG of function |
| 1233 | ----------------------------------- |
| 1234 | |
| 1235 | Displays the control flow graph using the GraphViz tool. |
| 1236 | |
| 1237 | ``-view-cfg-only``: View CFG of function (with no function bodies) |
| 1238 | ------------------------------------------------------------------ |
| 1239 | |
| 1240 | Displays the control flow graph using the GraphViz tool, but omitting function |
| 1241 | bodies. |
| 1242 | |
| 1243 | ``-view-dom``: View dominance tree of function |
| 1244 | ---------------------------------------------- |
| 1245 | |
| 1246 | Displays the dominator tree using the GraphViz tool. |
| 1247 | |
| 1248 | ``-view-dom-only``: View dominance tree of function (with no function bodies) |
| 1249 | ----------------------------------------------------------------------------- |
| 1250 | |
| 1251 | Displays the dominator tree using the GraphViz tool, but omitting function |
| 1252 | bodies. |
| 1253 | |
| 1254 | ``-view-postdom``: View postdominance tree of function |
| 1255 | ------------------------------------------------------ |
| 1256 | |
| 1257 | Displays the post dominator tree using the GraphViz tool. |
| 1258 | |
| 1259 | ``-view-postdom-only``: View postdominance tree of function (with no function bodies) |
| 1260 | ------------------------------------------------------------------------------------- |
| 1261 | |
| 1262 | Displays the post dominator tree using the GraphViz tool, but omitting function |
| 1263 | bodies. |
| 1264 | |