X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FPasses.html;h=bbf6b3dc943b217bdb50e8661d94e9b68faed3d6;hb=6c7e8a02d81be9b66a8cfc6f8b6f20d48088d915;hp=192f4420bf74296463faf5adfc67a3a0c806d370;hpb=55cbec317d9c30c8ae1d35eaa008ca63d1f2fce9;p=oota-llvm.git diff --git a/docs/Passes.html b/docs/Passes.html index 192f4420bf7..bbf6b3dc943 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -78,33 +78,31 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "
\n" if !
\n" if !
\n" if !
\n" if !
\n" if !
\n" if !
\n" if !
\n" if !
located at getNode(F) + CallReturnPos
. The arguments
start at getNode(F) + CallArgPos
.
+ Please keep in mind that the current andersen's pass has many known + problems and bugs. It should be considered "research quality". +
+ @@ -294,52 +296,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "\n" if !
Yet to be written.
- - -
- This is the default implementation of the ValueNumbering
- interface. It walks the SSA def-use chains to trivially identify
- lexically identical expressions. This does not require any ahead of time
- analysis, so it is a very fast default implementation.
-
- This pass, only available in opt
, prints the call graph to
- standard output in a human-readable form.
-
- This pass, only available in opt
, prints the SCCs of the call
- graph to standard output in a human-readable form.
-
- This pass, only available in opt
, prints the SCCs of each
- function CFG to standard output in a human-readable form.
-
\n" if !
- 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.
+ 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.
+
+ 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.
+
+ 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.
\n" if !
- This pass value numbers load and call instructions. To do this, it finds - lexically identical load instructions, and uses alias analysis to determine - which loads are guaranteed to produce the same value. To value number call - instructions, it looks for calls to functions that do not write to memory - which do not have intervening instructions that clobber the memory that is - read from. -
- -- This pass builds off of another value numbering pass to implement value - numbering for non-load and non-call instructions. It uses Alias Analysis so - that it can disambiguate the load instructions. The more powerful these base - analyses are, the more powerful the resultant value numbering will be. -
-\n" if !
+Yet to be written.
+
- The PrintFunctionPass
class is designed to be pipelined with
- other FunctionPass
es, and prints out the functions of the module
- as they are processed.
+ This pass, only available in opt
, prints the call graph to
+ standard output in a human-readable form.
Yet to be written.
+
+ This pass, only available in opt
, prints the SCCs of the call
+ graph to standard output in a human-readable form.
+
- 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.
+ This pass, only available in opt
, prints the SCCs of each
+ function CFG to standard output in a human-readable form.
- 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.
+ 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.
- 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.
+ The PrintFunctionPass
class is designed to be pipelined with
+ other FunctionPass
es, and prints out the functions of the module
+ as they are processed.
@@ -616,7 +583,7 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "
\n" if !
@@ -739,27 +706,12 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "
\n" if !
Correlated Expression Elimination propagates information from conditional - branches to blocks dominated by destinations of the branch. It propagates - information from the condition check itself into the body of the branch, - allowing transformations like these for example:
- -- --if (i == 7) - ... 4*i; // constant propagation - -M = i+1; N = j+1; -if (i == j) - X = M-N; // = M-M == 0; -
This is called Correlated Expression Elimination because we eliminate or - simplify expressions that are correlated with the direction of a branch. In - this way we use static information to give us some information about the - dynamic value of a variable.
+ 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.- This pass is designed to be a very quick global transformation that - eliminates global common subexpressions from a function. It does this by - using an existing value numbering implementation to identify the common - subexpressions, eliminating them when possible. -
-- This pass performs global value numbering to eliminate fully redundant - instructions. It also performs simple dead load elimination. + This pass performs global value numbering to eliminate fully and partially + redundant instructions. It also performs redundant load elimination.
- This pass performs a hybrid of global value numbering and partial redundancy - elimination, known as GVN-PRE. It performs partial redundancy elimination on - values, rather than lexical expressions, allowing a more comprehensive view - the optimization. It replaces redundant values with uses of earlier - occurences of the same value. While this is beneficial in that it eliminates - unneeded computation, it also increases register pressure by creating large - live ranges, and should be used with caution on platforms that are very - sensitive to register pressure. -
-This transformation should be followed by strength reduction after all of the @@ -1149,7 +1072,11 @@ if (i == j) Internalize Global Symbols
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. +
++ 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: +
+ ++ 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.
-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. +
- - -Yet to be written.
++ This is a target-dependent tranformation because it depends on the size of + data types and alignment constraints. +
Yet to be written.
++ 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.
++ 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 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: +
+ ++ 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.
++ 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.
++ Performs dead code elimination and basic block merging. Specifically: +
+ +Yet to be written.
++ Performs code stripping. This transformation can delete: +
+ ++ 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. +
Yet to be written.
++ 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). +
Yet to be written.
++ 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: +
+ +Yet to be written.
++ 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: +
+ +Yet to be written.
++ 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.
++ 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. +
Yet to be written.
++ 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. +
+ ++ Note that this does not provide full security verification (like Java), but + instead just tries to ensure that code is well-formed. +
Yet to be written.
++ Displays the control flow graph using the GraphViz tool. +
Yet to be written.
++ Displays the control flow graph using the GraphViz tool, but omitting function + bodies. +