From: Gordon Henriksen Date: Fri, 26 Oct 2007 03:03:51 +0000 (+0000) Subject: More fleshing out of docs/Passes.html, plus some typo fixes and X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=55cbec317d9c30c8ae1d35eaa008ca63d1f2fce9 More fleshing out of docs/Passes.html, plus some typo fixes and improved wording in source files. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43377 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/docs/Passes.html b/docs/Passes.html index fb1359ff858..192f4420bf7 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -313,9 +313,8 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if !

- 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 call graph to + standard output in a human-readable form.

@@ -325,8 +324,8 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if !

- 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 the call + graph to standard output in a human-readable form.

@@ -336,8 +335,8 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if !

- 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 SCCs of each + function CFG to standard output in a human-readable form.

@@ -495,7 +494,12 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Memory Dependence Analysis

-

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. +

@@ -503,7 +507,11 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! No Alias Analysis (always returns 'may' alias)

-

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. +

@@ -511,7 +519,10 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! No Profile Information

-

Yet to be written.

+

+ The default "no profile" implementation of the abstract + ProfileInfo interface. +

@@ -519,7 +530,10 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Post-Dominance Frontier Construction

-

Yet to be written.

+

+ This pass is a simple post-dominator construction algorithm for finding + post-dominator frontiers. +

@@ -527,7 +541,10 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Post-Dominator Tree Construction

-

Yet to be written.

+

+ This pass is a simple post-dominator construction algorithm for finding + post-dominators. +

@@ -535,7 +552,11 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Print function to stderr

-

Yet to be written.

+

+ The PrintFunctionPass class is designed to be pipelined with + other FunctionPasses, and prints out the functions of the module + as they are processed. +

@@ -551,7 +572,11 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Print Call Graph to 'dot' file

-

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. +

@@ -559,7 +584,11 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Print CFG of function to 'dot' file

-

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. +

@@ -567,7 +596,12 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Print CFG of function to 'dot' file (with no function bodies)

-

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. +

@@ -575,7 +609,9 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Print module to stderr

-

Yet to be written.

+

+ This pass simply prints out the entire module when it is executed. +

@@ -583,7 +619,10 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Find Used Types

-

Yet to be written.

+

+ 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.

@@ -591,7 +630,10 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Load profile information from llvmprof.out

-

Yet to be written.

+

+ A concrete implementation of profiling information that loads the information + from a profile dump file. +

@@ -599,7 +641,18 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Scalar Evolution Analysis

-

Yet to be written.

+

+ 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. +

@@ -607,7 +660,8 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Target Data Layout

-

Yet to be written.

+

Provides other passes access to information on how the size and alignment + required by the the target ABI for various data types.

@@ -632,7 +686,30 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Promote 'by reference' arguments to scalars

-

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. +

@@ -640,22 +717,11 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Profile Guided Basic Block Placement

-

This pass implements 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.

-

The algorithm implemented here is basically "Algo1" from "Profile Guided - Code Positioning" by Pettis and Hansen, except that it uses basic block - counts instead of edge counts. This could be improved in many ways, but is - very simple for now.

- -

Basically we "place" the entry block, then loop over all successors in a - DFO, placing the most frequently executed successor until we run out of - blocks. Did we mention that this was extremely simplistic? This is - also much slower than it could be. When it becomes important, this pass - will be rewritten to use a better algorithm, and then we can worry about - efficiency.

+

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.

@@ -663,7 +729,12 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "

\n" if ! Break critical edges in CFG

-

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. +

@@ -705,7 +776,12 @@ if (i == j) Merge Duplicate Global Constants
-

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. +

@@ -729,7 +805,11 @@ if (i == j) Dead Code Elimination
-

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. +

@@ -737,7 +817,17 @@ if (i == j) Dead Argument Elimination
-

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. +

@@ -745,7 +835,11 @@ if (i == j) Dead Type Elimination
-

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. +

@@ -753,7 +847,10 @@ if (i == j) Dead Instruction Elimination
-

Yet to be written.

+

+ Dead instruction elimination performs a single pass over the function, + removing instructions that are obviously dead. +

@@ -761,7 +858,10 @@ if (i == j) Dead Store Elimination
-

Yet to be written.

+

+ A trivial dead store elimination that only considers basic-block local + redundant stores. +

@@ -769,7 +869,12 @@ if (i == j) Global Common Subexpression Elimination
-

Yet to be written.

+

+ 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. +

@@ -777,7 +882,13 @@ if (i == j) Dead Global Elimination
-

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. +

@@ -785,7 +896,11 @@ if (i == j) Global Variable Optimizer
-

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. +

@@ -821,7 +936,16 @@ if (i == j) Indirect Malloc and Free Removal
-

Yet to be written.

+

+ This pass finds places where memory allocation functions may escape into + indirect land. Some transforms are much easier (aka possible) only if free + or malloc are not called indirectly. +

+ +

+ Thus find places where the address of memory functions are taken and construct + bounce functions with direct calls of those functions. +

@@ -829,7 +953,50 @@ if (i == j) Canonicalize Induction Variables
-

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: +

+ +
    +
  1. All loops are transformed to have a single canonical + induction variable which starts at zero and steps by one.
    2. +
  2. The canonical induction variable is guaranteed to be the first PHI node + in the loop header block.
    3. +
  3. Any pointer arithmetic recurrences are raised to use array + subscripts.
    4. +
+ +

+ If the trip count of a loop is computable, this pass also makes the following + changes: +

+ +
    +
  1. The exit condition for the loop is canonicalized to compare the + induction value against the exit value. This turns loops like: + 
    for (i = 7; i*i < 1000; ++i)
    + into + 
    for (i = 0; i != 25; ++i)
    2. +
  2. 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.
    3. +

    + +

    + 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). +

@@ -837,7 +1004,9 @@ if (i == j) Function Integration/Inlining
-

Yet to be written.

+

+ Bottom-up inlining of functions into callees. +

@@ -845,7 +1014,18 @@ if (i == j) Insert instrumentation for block profiling
-

Yet to be written.

+

+ This pass instruments the specified program with counters for basic block + profiling, which counts the number of times each basic block executes. This + is the most basic form of profiling, which can tell which blocks are hot, but + cannot reliably detect hot paths through the CFG. +

+ +

+ Note that this implementation is very naïve. Control equivalent regions of + the CFG should not require duplicate counters, but it does put duplicate + counters in. +

@@ -853,7 +1033,17 @@ if (i == j) Insert instrumentation for edge profiling
-

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. +

@@ -861,7 +1051,10 @@ if (i == j) Insert instrumentation for function profiling
-

Yet to be written.

+

+ This pass instruments the specified program with counters for function + profiling, which counts the number of times each function is called. +

@@ -869,7 +1062,11 @@ if (i == j) Measure profiling framework overhead
-

Yet to be written.

+

+ The basic profiler that does nothing. It is the default profiler and thus + terminates RSProfiler chains. It is useful for measuring + framework overhead. +

@@ -877,7 +1074,20 @@ if (i == j) Insert random sampling instrumentation framework
-

Yet to be written.

+

+ The second stage of the random-sampling instrumentation framework, duplicates + all instructions in a function, ignoring the profiling code, then connects the + two versions together at the entry and at backedges. At each connection point + a choice is made as to whether to jump to the profiled code (take a sample) or + execute the unprofiled code. +

+ +

+ After this pass, it is highly recommended to runmem2reg + and adce. instcombine, + load-vn, gdce, and + dse also are good to run afterwards. +

@@ -885,7 +1095,53 @@ if (i == j) Combine redundant instructions
-

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: +

+ +
diff --git a/include/llvm/Assembly/PrintModulePass.h b/include/llvm/Assembly/PrintModulePass.h index ed70e9dc3bb..3c4176dfdad 100644 --- a/include/llvm/Assembly/PrintModulePass.h +++ b/include/llvm/Assembly/PrintModulePass.h @@ -10,7 +10,7 @@ // This file defines two passes to print out a module. The PrintModulePass pass // simply prints out the entire module when it is executed. The // PrintFunctionPass class is designed to be pipelined with other -// FunctionPass's, and prints out the functions of the class as they are +// FunctionPass's, and prints out the functions of the module as they are // processed. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/IPO/ArgumentPromotion.cpp b/lib/Transforms/IPO/ArgumentPromotion.cpp index 93a7af68a0d..85b29f871fc 100644 --- a/lib/Transforms/IPO/ArgumentPromotion.cpp +++ b/lib/Transforms/IPO/ArgumentPromotion.cpp @@ -9,22 +9,22 @@ // // This pass promotes "by reference" arguments to be "by value" arguments. In // practice, this means looking for internal functions that have pointer -// arguments. If we can prove, through the use of alias analysis, that an -// argument is *only* loaded, then we can pass the value into the function +// 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 -// we refuse to scalarize aggregates which would require passing in more than -// three operands to the function, because we don't want to pass thousands of -// operands for a large array or structure! +// 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 we do not currently handle that -// case. This case would be best handled when and if we start supporting -// multiple return values from functions. +// stored to (returning the value instead), but does not currently. This case +// would be best handled when and if LLVM begins supporting multiple return +// values from functions. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Instrumentation/RSProfiling.cpp b/lib/Transforms/Instrumentation/RSProfiling.cpp index 3c7efb1ba3c..ac45d79513a 100644 --- a/lib/Transforms/Instrumentation/RSProfiling.cpp +++ b/lib/Transforms/Instrumentation/RSProfiling.cpp @@ -18,7 +18,7 @@ // backedges. At each connection point a choice is made as to whether to jump // to the profiled code (take a sample) or execute the unprofiled code. // -// It is highly recommeneded that after this pass one runs mem2reg and adce +// It is highly recommended that after this pass one runs mem2reg and adce // (instcombine load-vn gdce dse also are good to run afterwards) // // This design is intended to make the profiling passes independent of the RS