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