llvm/docs/Passes.rst

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