Yet to be written.
@@ -180,255 +257,386 @@Yet to be written.
++ This pass munges the code in the input function to better prepare it for + SelectionDAG-based code generation. This works around limitations in it's + basic-block-at-a-time approach. It should eventually be removed. +
Yet to be written.
++ A pass which can be used to count how many alias queries + are being made and how the alias analysis implementation being used responds. +
Yet to be written.
++ This simple pass checks alias analysis users to ensure that if they + create a new value, they do not query AA without informing it of the value. + It acts as a shim over any other AA pass you want. +
+ ++ Yes keeping track of every value in the program is expensive, but this is + a debugging pass. +
Yet to be written.
++ This pass is a simple dominator construction algorithm for finding forward + dominator frontiers. +
Yet to be written.
++ This pass is a simple dominator construction algorithm for finding forward + dominators. +
Yet to be written.
+
+ This pass, only available in opt, prints the call graph into a
+ .dot graph. This graph can then be processed with the "dot" tool
+ to convert it to postscript or some other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the control flow graph
+ into a .dot graph. This graph can then be processed with the
+ "dot" tool to convert it to postscript or some other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the control flow graph
+ into a .dot graph, omitting the function bodies. This graph can
+ then be processed with the "dot" tool to convert it to postscript or some
+ other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the dominator tree
+ into a .dot graph. This graph can then be processed with the
+ "dot" tool to convert it to postscript or some other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the dominator tree
+ into a .dot graph, omitting the function bodies. This graph can
+ then be processed with the "dot" tool to convert it to postscript or some
+ other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the post dominator tree
+ into a .dot graph. This graph can then be processed with the
+ "dot" tool to convert it to postscript or some other suitable format.
+
Yet to be written.
+
+ This pass, only available in opt, prints the post dominator tree
+ into a .dot graph, omitting the function bodies. This graph can
+ then be processed with the "dot" tool to convert it to postscript or some
+ other suitable format.
+
Yet to be written.
++ This simple pass provides alias and mod/ref information for global values + that do not have their address taken, and keeps track of whether functions + read or write memory (are "pure"). For this simple (but very common) case, + we can provide pretty accurate and useful information. +
Yet to be written.
++ This pass collects the count of all instructions and reports them +
Yet to be written.
+This pass implements a simple N^2 alias analysis accuracy evaluator. + Basically, for each function in the program, it simply queries to see how the + alias analysis implementation answers alias queries between each pair of + pointers in the function. +
Yet to be written.
+This pass defines the default implementation of the Alias Analysis interface + that simply implements a few identities (two different globals cannot alias, + etc), but otherwise does no analysis. +
Yet to be written.
++ This analysis calculates and represents the interval partition of a function, + or a preexisting interval partition. +
+ ++ In this way, the interval partition may be used to reduce a flow graph down + to its degenerate single node interval partition (unless it is irreducible). +
Yet to be written.
+Bookkeeping for "interesting" users of expressions computed from + induction variables.
Yet to be written.
+Interface for lazy computation of value constraint information.
Yet to be written.
+Loop dependence analysis framework, which is used to detect dependences in + memory accesses in loops.
Yet to be written.
+LibCall Alias Analysis.
Yet to be written.
+This pass statically checks for common and easily-identified constructs + which produce undefined or likely unintended behavior in LLVM IR.
+ +It is not a guarantee of correctness, in two ways. First, it isn't + comprehensive. There are checks which could be done statically which are + not yet implemented. Some of these are indicated by TODO comments, but + those aren't comprehensive either. Second, many conditions cannot be + checked statically. This pass does no dynamic instrumentation, so it + can't check for all possible problems.
+ +Another limitation is that it assumes all code will be executed. A store + through a null pointer in a basic block which is never reached is harmless, + but this pass will warn about it anyway.
+ +Optimization passes may make conditions that this pass checks for more or + less obvious. If an optimization pass appears to be introducing a warning, + it may be that the optimization pass is merely exposing an existing + condition in the code.
+ +This code may be run before instcombine. In many cases, instcombine checks + for the same kinds of things and turns instructions with undefined behavior + into unreachable (or equivalent). Because of this, this pass makes some + effort to look through bitcasts and so on. +
Yet to be written.
+LLVM IR Value liveness analysis pass.
Yet to be written.
++ This analysis is used to identify natural loops and determine the loop depth + of various nodes of the CFG. Note that the loops identified may actually be + several natural loops that share the same header node... not just a single + natural loop. +
Yet to be written.
++ An analysis that determines, for a given memory operation, what preceding + memory operations it depends on. It builds on alias analysis information, and + tries to provide a lazy, caching interface to a common kind of alias + information query. +
Yet to be written.
+This pass decodes the debug info metadata in a module and prints in a + (sufficiently-prepared-) human-readable form. + + For example, run this pass from opt along with the -analyze option, and + it'll print to standard output. +
Yet to be written.
++ Always returns "I don't know" for alias queries. NoAA is unlike other alias + analysis implementations, in that it does not chain to a previous analysis. As + such it doesn't follow many of the rules that other alias analyses must. +
Yet to be written.
+
+ The default "no profile" implementation of the abstract
+ ProfileInfo interface.
+
Yet to be written.
+Tracking of pointer bounds. +
Yet to be written.
++ This pass is a simple post-dominator construction algorithm for finding + post-dominator frontiers. +
Yet to be written.
++ This pass is a simple post-dominator construction algorithm for finding + post-dominators. +
Yet to be written.
@@ -436,34 +644,209 @@Yet to be written.
+
+ This pass, only available in opt, prints the call graph to
+ standard error in a human-readable form.
+
Yet to be written.
+
+ This pass, only available in opt, prints the SCCs of the call
+ graph to standard error in a human-readable form.
+
Yet to be written.
+
+ This pass, only available in opt, prints the SCCs of each
+ function CFG to standard error in a human-readable form.
+
Yet to be written.
+Pass that prints instructions, and associated debug info:
+-
+
+
- source/line/col information +
- original variable name +
- original type name +
Dominator Info Printer.
+
+ This pass, only available in opt, prints out call sites to
+ external functions that are called with constant arguments. This can be
+ useful when looking for standard library functions we should constant fold
+ or handle in alias analyses.
+
+ The PrintFunctionPass class is designed to be pipelined with
+ other FunctionPasses, and prints out the functions of the module
+ as they are processed.
+
+ This pass simply prints out the entire module when it is executed. +
++ This pass is used to seek out all of the types in use by the program. Note + that this analysis explicitly does not include types only used by the symbol + table. +
Profiling information that estimates the profiling information + in a very crude and unimaginative way. +
++ A concrete implementation of profiling information that loads the information + from a profile dump file. +
+Pass that checks profiling information for plausibility.
+
+ The RegionInfo pass detects single entry single exit regions in a
+ function, where a region is defined as any subgraph that is connected to the
+ remaining graph at only two spots. Furthermore, an hierarchical region tree is
+ built.
+
+ The ScalarEvolution analysis can be used to analyze and
+ catagorize scalar expressions in loops. It specializes in recognizing general
+ induction variables, representing them with the abstract and opaque
+ SCEV class. Given this analysis, trip counts of loops and other
+ important properties can be obtained.
+
+ This analysis is primarily useful for induction variable substitution and + strength reduction. +
+Simple alias analysis implemented in terms of ScalarEvolution queries. + + This differs from traditional loop dependence analysis in that it tests + for dependencies within a single iteration of a loop, rather than + dependencies between different iterations. + + ScalarEvolution has a more complete understanding of pointer arithmetic + than BasicAliasAnalysis' collection of ad-hoc analyses. +
++ performs code stripping. this transformation can delete: +
+ +-
+
- names for virtual registers +
- symbols for internal globals and functions +
- debug information +
+ note that this transformation makes code much less readable, so it should + only be used in situations where the strip utility would be used, + such as reducing code size or making it harder to reverse engineer code. +
+Provides other passes access to information on how the size and alignment + required by the the target ABI for various data types.
Yet to be written.
+ABCD removes conditional branch instructions that can be proved redundant. + With the SSI representation, each variable has a constraint. By analyzing these + constraints we can prove that a branch is redundant. When a branch is proved + redundant it means that one direction will always be taken; thus, we can change + this branch into an unconditional jump.
+It is advisable to run SimplifyCFG and + Aggressive Dead Code Elimination after ABCD + to clean up the code.
Yet to be written.
+ADCE aggressively tries to eliminate code. This pass is similar to + DCE but it assumes that values are dead until proven + otherwise. This is similar to SCCP, except applied to + the liveness of values.
Yet to be written.
+A custom inliner that handles only functions that are marked as + "always inline".
Yet to be written.
++ This pass promotes "by reference" arguments to be "by value" arguments. In + practice, this means looking for internal functions that have pointer + arguments. If it can prove, through the use of alias analysis, that an + argument is *only* loaded, then it can pass the value into the function + instead of the address of the value. This can cause recursive simplification + of code and lead to the elimination of allocas (especially in C++ template + code like the STL). +
+ ++ This pass also handles aggregate arguments that are passed into a function, + scalarizing them if the elements of the aggregate are only loaded. Note that + it refuses to scalarize aggregates which would require passing in more than + three operands to the function, because passing thousands of operands for a + large array or structure is unprofitable! +
+ ++ Note that this transformation could also be done for arguments that are only + stored to (returning the value instead), but does not currently. This case + would be best handled when and if LLVM starts supporting multiple return + values from functions. +
Yet to be written.
+This pass is a very simple profile guided basic block placement algorithm. + The idea is to put frequently executed blocks together at the start of the + function and hopefully increase the number of fall-through conditional + branches. If there is no profile information for a particular function, this + pass basically orders blocks in depth-first order.
Yet to be written.
++ Break all of the critical edges in the CFG by inserting a dummy basic block. + It may be "required" by passes that cannot deal with critical edges. This + transformation obviously invalidates the CFG, but can update forward dominator + (set, immediate dominators, tree, and frontier) information. +
Yet to be written.
+ This pass munges the code in the input function to better prepare it for + SelectionDAG-based code generation. This works around limitations in it's + basic-block-at-a-time approach. It should eventually be removed.Yet to be written.
++ Merges duplicate global constants together into a single constant that is + shared. This is useful because some passes (ie TraceValues) insert a lot of + string constants into the program, regardless of whether or not an existing + string is available. +
Yet to be written.
+This file implements constant propagation and merging. It looks for + instructions involving only constant operands and replaces them with a + constant value instead of an instruction. For example:
++add i32 1, 2
becomes
++i32 3
NOTE: this pass has a habit of making definitions be dead. It is a good + idea to to run a DIE (Dead Instruction Elimination) pass + sometime after running this pass.
Yet to be written.
++ Dead code elimination is similar to dead instruction + elimination, but it rechecks instructions that were used by removed + instructions to see if they are newly dead. +
Yet to be written.
++ This pass deletes dead arguments from internal functions. Dead argument + elimination removes arguments which are directly dead, as well as arguments + only passed into function calls as dead arguments of other functions. This + pass also deletes dead arguments in a similar way. +
+ ++ This pass is often useful as a cleanup pass to run after aggressive + interprocedural passes, which add possibly-dead arguments. +
Yet to be written.
++ This pass is used to cleanup the output of GCC. It eliminate names for types + that are unused in the entire translation unit, using the find used types pass. +
Yet to be written.
++ Dead instruction elimination performs a single pass over the function, + removing instructions that are obviously dead. +
Yet to be written.
++ A trivial dead store elimination that only considers basic-block local + redundant stores. +
Yet to be written.
+A simple interprocedural pass which walks the call-graph, looking for + functions which do not access or only read non-local memory, and marking them + readnone/readonly. In addition, it marks function arguments (of pointer type) + 'nocapture' if a call to the function does not create any copies of the pointer + value that outlive the call. This more or less means that the pointer is only + dereferenced, and not returned from the function or stored in a global. + This pass is implemented as a bottom-up traversal of the call-graph. +
Yet to be written.
++ This transform is designed to eliminate unreachable internal globals from the + program. It uses an aggressive algorithm, searching out globals that are + known to be alive. After it finds all of the globals which are needed, it + deletes whatever is left over. This allows it to delete recursive chunks of + the program which are unreachable. +
Yet to be written.
++ This pass transforms simple global variables that never have their address + taken. If obviously true, it marks read/write globals as constant, deletes + variables only stored to, etc. +
Yet to be written.
++ This pass performs global value numbering to eliminate fully and partially + redundant instructions. It also performs redundant load elimination. +
Yet to be written.
++ This transformation analyzes and transforms the induction variables (and + computations derived from them) into simpler forms suitable for subsequent + analysis and transformation. +
+ ++ This transformation makes the following changes to each loop with an + identifiable induction variable: +
+ +-
+
- All loops are transformed to have a single canonical + induction variable which starts at zero and steps by one. +
- The canonical induction variable is guaranteed to be the first PHI node + in the loop header block. +
- Any pointer arithmetic recurrences are raised to use array + subscripts. +
+ If the trip count of a loop is computable, this pass also makes the following + changes: +
+ +-
+
- The exit condition for the loop is canonicalized to compare the
+ induction value against the exit value. This turns loops like:
+
+ into +for (i = 7; i*i < 1000; ++i)
for (i = 0; i != 25; ++i)
+ - Any use outside of the loop of an expression derived from the indvar + is changed to compute the derived value outside of the loop, eliminating + the dependence on the exit value of the induction variable. If the only + purpose of the loop is to compute the exit value of some derived + expression, this transformation will make the loop dead. +
+ This transformation should be followed by strength reduction after all of the + desired loop transformations have been performed. Additionally, on targets + where it is profitable, the loop could be transformed to count down to zero + (the "do loop" optimization). +
Yet to be written.
++ Bottom-up inlining of functions into callees. +
Yet to be written.
++ This pass instruments the specified program with counters for edge profiling. + Edge profiling can give a reasonable approximation of the hot paths through a + program, and is used for a wide variety of program transformations. +
+ ++ Note that this implementation is very naïve. It inserts a counter for + every edge in the program, instead of using control flow information + to prune the number of counters inserted. +
Yet to be written.
+This pass instruments the specified program with counters for edge profiling. + Edge profiling can give a reasonable approximation of the hot paths through a + program, and is used for a wide variety of program transformations. +
Yet to be written.
++ Combine instructions to form fewer, simple + instructions. This pass does not modify the CFG This pass is where algebraic + simplification happens. +
+ ++ This pass combines things like: +
+ ++ +%Y = add i32 %X, 1 +%Z = add i32 %Y, 1
+ into: +
+ ++ +%Z = add i32 %X, 2
+ This is a simple worklist driven algorithm. +
+ ++ This pass guarantees that the following canonicalizations are performed on + the program: +
+ +-
+
- If a binary operator has a constant operand, it is moved to the right- + hand side. +
- Bitwise operators with constant operands are always grouped so that
+ shifts are performed first, then
ors, then +ands, thenxors.
+ - Compare instructions are converted from
<, +>,â¤, orâ¥to +=orâif possible.
+ - All
cmpinstructions on boolean values are replaced with + logical operations.
+ add X, Xis represented as +mul X, 2âshl X, 1
+ - Multiplies with a constant power-of-two argument are transformed into + shifts. +
- ⦠etc. +
Yet to be written.
++ This pass loops over all of the functions in the input module, looking for a + main function. If a main function is found, all other functions and all + global variables with initializers are marked as internal. +
Yet to be written.
++ This pass implements an extremely simple interprocedural constant + propagation pass. It could certainly be improved in many different ways, + like using a worklist. This pass makes arguments dead, but does not remove + them. The existing dead argument elimination pass should be run after this + to clean up the mess. +
Yet to be written.
++ An interprocedural variant of Sparse Conditional Constant + Propagation. +
Yet to be written.
++ Jump threading tries to find distinct threads of control flow running through + a basic block. This pass looks at blocks that have multiple predecessors and + multiple successors. If one or more of the predecessors of the block can be + proven to always cause a jump to one of the successors, we forward the edge + from the predecessor to the successor by duplicating the contents of this + block. +
++ An example of when this can occur is code like this: +
+ +if () { ...
+ X = 4;
+}
+if (X < 3) {
+
+ + In this case, the unconditional branch at the end of the first if can be + revectored to the false side of the second if. +
Yet to be written.
++ This pass transforms loops by placing phi nodes at the end of the loops for + all values that are live across the loop boundary. For example, it turns + the left into the right code: +
+ +for (...) for (...) + if (c) if (c) + X1 = ... X1 = ... + else else + X2 = ... X2 = ... + X3 = phi(X1, X2) X3 = phi(X1, X2) +... = X3 + 4 X4 = phi(X3) + ... = X4 + 4+ +
+ This is still valid LLVM; the extra phi nodes are purely redundant, and will
+ be trivially eliminated by InstCombine. The major benefit of
+ this transformation is that it makes many other loop optimizations, such as
+ LoopUnswitching, simpler.
+
Yet to be written.
++ This pass performs loop invariant code motion, attempting to remove as much + code from the body of a loop as possible. It does this by either hoisting + code into the preheader block, or by sinking code to the exit blocks if it is + safe. This pass also promotes must-aliased memory locations in the loop to + live in registers, thus hoisting and sinking "invariant" loads and stores. +
+ ++ This pass uses alias analysis for two purposes: +
+ +-
+
- Moving loop invariant loads and calls out of loops. If we can determine + that a load or call inside of a loop never aliases anything stored to, + we can hoist it or sink it like any other instruction. +
- Scalar Promotion of Memory - If there is a store instruction inside of
+ the loop, we try to move the store to happen AFTER the loop instead of
+ inside of the loop. This can only happen if a few conditions are true:
+
-
+
- The pointer stored through is loop invariant. +
- There are no stores or loads in the loop which may alias + the pointer. There are no calls in the loop which mod/ref the + pointer. +
+
+ This file implements the Dead Loop Deletion Pass. This pass is responsible + for eliminating loops with non-infinite computable trip counts that have no + side effects or volatile instructions, and do not contribute to the + computation of the function's return value. +
Yet to be written.
+
+ A pass wrapper around the ExtractLoop() scalar transformation to
+ extract each top-level loop into its own new function. If the loop is the
+ only loop in a given function, it is not touched. This is a pass most
+ useful for debugging via bugpoint.
+
Yet to be written.
++ Similar to Extract loops into new functions, + this pass extracts one natural loop from the program into a function if it + can. This is used by bugpoint. +
Yet to be written.
++ This pass divides loop's iteration range by spliting loop such that each + individual loop is executed efficiently. +
Yet to be written.
++ This pass performs a strength reduction on array references inside loops that + have as one or more of their components the loop induction variable. This is + accomplished by creating a new value to hold the initial value of the array + access for the first iteration, and then creating a new GEP instruction in + the loop to increment the value by the appropriate amount. +
Yet to be written.
+A simple loop rotation transformation.
Yet to be written.
++ This pass implements a simple loop unroller. It works best when loops have + been canonicalized by the -indvars pass, + allowing it to determine the trip counts of loops easily. +
Yet to be written.
++ This pass transforms loops that contain branches on loop-invariant conditions + to have multiple loops. For example, it turns the left into the right code: +
+ +for (...) if (lic) + A for (...) + if (lic) A; B; C + B else + C for (...) + A; C+ +
+ This can increase the size of the code exponentially (doubling it every time + a loop is unswitched) so we only unswitch if the resultant code will be + smaller than a threshold. +
+ ++ This pass expects LICM to be run before it to hoist invariant conditions out + of the loop, to make the unswitching opportunity obvious. +
Yet to be written.
++ This pass performs several transformations to transform natural loops into a + simpler form, which makes subsequent analyses and transformations simpler and + more effective. +
+ ++ Loop pre-header insertion guarantees that there is a single, non-critical + entry edge from outside of the loop to the loop header. This simplifies a + number of analyses and transformations, such as LICM. +
+ ++ Loop exit-block insertion guarantees that all exit blocks from the loop + (blocks which are outside of the loop that have predecessors inside of the + loop) only have predecessors from inside of the loop (and are thus dominated + by the loop header). This simplifies transformations such as store-sinking + that are built into LICM. +
+ ++ This pass also guarantees that loops will have exactly one backedge. +
+ ++ Note that the simplifycfg pass will clean up blocks which are split out but + end up being unnecessary, so usage of this pass should not pessimize + generated code. +
+ ++ This pass obviously modifies the CFG, but updates loop information and + dominator information. +
Yet to be written.
++ Turn malloc and free instructions into @malloc and + @free calls. +
+ ++ This is a target-dependent tranformation because it depends on the size of + data types and alignment constraints. +
Yet to be written.
++ This pass lowers atomic intrinsics to non-atomic form for use in a known + non-preemptible environment. +
+ ++ The pass does not verify that the environment is non-preemptible (in + general this would require knowledge of the entire call graph of the + program including any libraries which may not be available in bitcode form); + it simply lowers every atomic intrinsic. +
++ This transformation is designed for use by code generators which do not yet + support stack unwinding. This pass supports two models of exception handling + lowering, the 'cheap' support and the 'expensive' support. +
+ ++ 'Cheap' exception handling support gives the program the ability to execute + any program which does not "throw an exception", by turning 'invoke' + instructions into calls and by turning 'unwind' instructions into calls to + abort(). If the program does dynamically use the unwind instruction, the + program will print a message then abort. +
+ ++ 'Expensive' exception handling support gives the full exception handling + support to the program at the cost of making the 'invoke' instruction + really expensive. It basically inserts setjmp/longjmp calls to emulate the + exception handling as necessary. +
+ ++ Because the 'expensive' support slows down programs a lot, and EH is only + used for a subset of the programs, it must be specifically enabled by the + -enable-correct-eh-support option. +
+ ++ Note that after this pass runs the CFG is not entirely accurate (exceptional + control flow edges are not correct anymore) so only very simple things should + be done after the lowerinvoke pass has run (like generation of native code). + This should not be used as a general purpose "my LLVM-to-LLVM pass doesn't + support the invoke instruction yet" lowering pass. +
Yet to be written.
++ Lowers setjmp and longjmp to use the LLVM invoke and unwind + instructions as necessary. +
+ ++ Lowering of longjmp is fairly trivial. We replace the call with a + call to the LLVM library function __llvm_sjljeh_throw_longjmp(). + This unwinds the stack for us calling all of the destructors for + objects allocated on the stack. +
+ ++ At a setjmp call, the basic block is split and the setjmp + removed. The calls in a function that have a setjmp are converted to + invoke where the except part checks to see if it's a longjmp + exception and, if so, if it's handled in the function. If it is, then it gets + the value returned by the longjmp and goes to where the basic block + was split. invoke instructions are handled in a similar fashion with + the original except block being executed if it isn't a longjmp + except that is handled by that function. +
Yet to be written.
++ Rewrites switch instructions with a sequence of branches, which + allows targets to get away with not implementing the switch instruction until + it is convenient. +
Yet to be written.
++ This file promotes memory references to be register references. It promotes + alloca instructions which only have loads and + stores as uses. An alloca is transformed by using dominator + frontiers to place phi nodes, then traversing the function in + depth-first order to rewrite loads and stores as + appropriate. This is just the standard SSA construction algorithm to construct + "pruned" SSA form. +
Yet to be written.
++ This pass performs various transformations related to eliminating memcpy + calls, or transforming sets of stores into memset's. +
Yet to be written.
+This pass looks for equivalent functions that are mergable and folds them. + + A hash is computed from the function, based on its type and number of + basic blocks. + + Once all hashes are computed, we perform an expensive equality comparison + on each function pair. This takes n^2/2 comparisons per bucket, so it's + important that the hash function be high quality. The equality comparison + iterates through each instruction in each basic block. + + When a match is found the functions are folded. If both functions are + overridable, we move the functionality into a new internal function and + leave two overridable thunks to it. +
Yet to be written.
++ Ensure that functions have at most one ret instruction in them. + Additionally, it keeps track of which node is the new exit node of the CFG. +
Yet to be written.
+This pass performs partial inlining, typically by inlining an if + statement that surrounds the body of the function. +
Yet to be written.
+This pass finds function arguments that are often a common constant and + specializes a version of the called function for that constant. + + This pass simply does the cloning for functions it specializes. It depends + on IPSCCP and DAE to clean up the results. + + The initial heuristic favors constant arguments that are used in control + flow. +
Yet to be written.
++ This file implements a simple interprocedural pass which walks the call-graph, + turning invoke instructions into call instructions if and + only if the callee cannot throw an exception. It implements this as a + bottom-up traversal of the call-graph. +
Yet to be written.
++ This pass reassociates commutative expressions in an order that is designed + to promote better constant propagation, GCSE, LICM, PRE, etc. +
+ ++ For example: 4 + (x + 5) â x + (4 + 5) +
+ ++ In the implementation of this algorithm, constants are assigned rank = 0, + function arguments are rank = 1, and other values are assigned ranks + corresponding to the reverse post order traversal of current function + (starting at 2), which effectively gives values in deep loops higher rank + than values not in loops. +
Yet to be written.
++ This file demotes all registers to memory references. It is intented to be + the inverse of -mem2reg. By converting to + load instructions, the only values live across basic blocks are + alloca instructions and load instructions before + phi nodes. It is intended that this should make CFG hacking much + easier. To make later hacking easier, the entry block is split into two, such + that all introduced alloca instructions (and nothing else) are in the + entry block. +
Yet to be written.
++ The well-known scalar replacement of aggregates transformation. This + transform breaks up alloca instructions of aggregate type (structure + or array) into individual alloca instructions for each member if + possible. Then, if possible, it transforms the individual alloca + instructions into nice clean scalar SSA form. +
+ ++ This combines a simple scalar replacement of aggregates algorithm with the mem2reg algorithm because often interact, + especially for C++ programs. As such, iterating between scalarrepl, + then mem2reg until we run out of things to + promote works well. +
Yet to be written.
++ Sparse conditional constant propagation and merging, which can be summarized + as: +
+ +-
+
- Assumes values are constant unless proven otherwise +
- Assumes BasicBlocks are dead unless proven otherwise +
- Proves values to be constant, and replaces them with constants +
- Proves conditional branches to be unconditional +
+ Note that this pass has a habit of making definitions be dead. It is a good + idea to to run a DCE pass sometime after running this pass. +
Yet to be written.
+This pass moves instructions into successor blocks, when possible, so that + they aren't executed on paths where their results aren't needed. +
Yet to be written.
++ Applies a variety of small optimizations for calls to specific well-known + function calls (e.g. runtime library functions). For example, a call + exit(3) that occurs within the main() function can be + transformed into simply return 3. +
Yet to be written.
+Simple pass that applies an experimental transformation on calls + to specific functions. +
Yet to be written.
++ Performs dead code elimination and basic block merging. Specifically: +
+ +-
+
- Removes basic blocks with no predecessors. +
- Merges a basic block into its predecessor if there is only one and the + predecessor only has one successor. +
- Eliminates PHI nodes for basic blocks with a single predecessor. +
- Eliminates a basic block that only contains an unconditional + branch. +
Yet to be written.
+This function breaks GEPs with more than 2 non-zero operands into smaller + GEPs each with no more than 2 non-zero operands. This exposes redundancy + between GEPs with common initial operand sequences. +
+This pass converts a list of variables to the Static Single Information + form. + + We are building an on-demand representation, that is, we do not convert + every single variable in the target function to SSI form. Rather, we receive + a list of target variables that must be converted. We also do not + completely convert a target variable to the SSI format. Instead, we only + change the variable in the points where new information can be attached + to its live range, that is, at branch points. +
+A pass that runs SSI on every non-void variable, intended for debugging. +
++ performs code stripping. this transformation can delete: +
+ +-
+
- names for virtual registers +
- symbols for internal globals and functions +
- debug information +
+ note that this transformation makes code much less readable, so it should + only be used in situations where the strip utility would be used, + such as reducing code size or making it harder to reverse engineer code. +
++ This pass loops over all of the functions in the input module, looking for + dead declarations and removes them. Dead declarations are declarations of + functions for which no implementation is available (i.e., declarations for + unused library functions). +
+This pass implements code stripping. Specifically, it can delete:
+-
+
- names for virtual registers +
- symbols for internal globals and functions +
- debug information +
+ Note that this transformation makes code much less readable, so it should + only be used in situations where the 'strip' utility would be used, such as + reducing code size or making it harder to reverse engineer code. +
+This pass implements code stripping. Specifically, it can delete:
+-
+
- names for virtual registers +
- symbols for internal globals and functions +
- debug information +
+ Note that this transformation makes code much less readable, so it should + only be used in situations where the 'strip' utility would be used, such as + reducing code size or making it harder to reverse engineer code. +
++ This pass finds functions that return a struct (using a pointer to the struct + as the first argument of the function, marked with the 'sret' attribute) and + replaces them with a new function that simply returns each of the elements of + that struct (using multiple return values). +
+ ++ This pass works under a number of conditions: +
+ +-
+
- The returned struct must not contain other structs +
- The returned struct must only be used to load values from +
- The placeholder struct passed in is the result of an alloca +
+ This file transforms calls of the current function (self recursion) followed + by a return instruction with a branch to the entry of the function, creating + a loop. This pass also implements the following extensions to the basic + algorithm: +
+ +-
+
- Trivial instructions between the call and return do not prevent the + transformation from taking place, though currently the analysis cannot + support moving any really useful instructions (only dead ones). +
- This pass transforms functions that are prevented from being tail + recursive by an associative expression to use an accumulator variable, + thus compiling the typical naive factorial or fib implementation + into efficient code. +
- TRE is performed if the function returns void, if the return + returns the result returned by the call, or if the function returns a + run-time constant on all exits from the function. It is possible, though + unlikely, that the return returns something else (like constant 0), and + can still be TRE'd. It can be TRE'd if all other return + instructions in the function return the exact same value. +
- If it can prove that callees do not access theier caller stack frame, + they are marked as eligible for tail call elimination (by the code + generator). +
+ This pass performs a limited form of tail duplication, intended to simplify + CFGs by removing some unconditional branches. This pass is necessary to + straighten out loops created by the C front-end, but also is capable of + making other code nicer. After this pass is run, the CFG simplify pass + should be run to clean up the mess. +
Yet to be written.
++ Same as dead argument elimination, but deletes arguments to functions which + are external. This is only for use by bugpoint.
Yet to be written.
++ This pass is used by bugpoint to extract all blocks from the module into their + own functions.
Yet to be written.
+This is a little utility pass that gives instructions names, this is mostly + useful when diffing the effect of an optimization because deleting an + unnamed instruction can change all other instruction numbering, making the + diff very noisy. +
Yet to be written.
++ Ensures that the module is in the form required by the Module Verifier pass. +
+ ++ Running the verifier runs this pass automatically, so there should be no need + to use it directly. +
++ Verifies an LLVM IR code. This is useful to run after an optimization which is + undergoing testing. Note that llvm-as verifies its input before + emitting bitcode, and also that malformed bitcode is likely to make LLVM + crash. All language front-ends are therefore encouraged to verify their output + before performing optimizing transformations. +
+ +-
+
- Both of a binary operator's parameters are of the same type. +
- Verify that the indices of mem access instructions match other + operands. +
- Verify that arithmetic and other things are only performed on + first-class types. Verify that shifts and logicals only happen on + integrals f.e. +
- All of the constants in a switch statement are of the correct type. +
- The code is in valid SSA form. +
- It is illegal to put a label into any other type (like a structure) or + to return one. +
- Only phi nodes can be self referential: %x = add i32 %x, %x is + invalid. +
- PHI nodes must have an entry for each predecessor, with no extras. +
- PHI nodes must be the first thing in a basic block, all grouped + together. +
- PHI nodes must have at least one entry. +
- All basic blocks should only end with terminator insts, not contain + them. +
- The entry node to a function must not have predecessors. +
- All Instructions must be embedded into a basic block. +
- Functions cannot take a void-typed parameter. +
- Verify that a function's argument list agrees with its declared + type. +
- It is illegal to specify a name for a void value. +
- It is illegal to have a internal global value with no initializer. +
- It is illegal to have a ret instruction that returns a value that does + not agree with the function return value type. +
- Function call argument types match the function prototype. +
- All other things that are tested by asserts spread about the code. +
+ Note that this does not provide full security verification (like Java), but + instead just tries to ensure that code is well-formed. +
++ Displays the control flow graph using the GraphViz tool. +
++ Displays the control flow graph using the GraphViz tool, but omitting function + bodies. +
++ Displays the dominator tree using the GraphViz tool. +
++ Displays the dominator tree using the GraphViz tool, but omitting function + bodies. +
++ Displays the post dominator tree using the GraphViz tool. +
++ Displays the post dominator tree using the GraphViz tool, but omitting + function bodies. +
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS">
LLVM Compiler Infrastructure