From c86b67742a3298c0a5a715b57a64f11107b8a3f2 Mon Sep 17 00:00:00 2001 From: Gordon Henriksen Date: Sun, 4 Nov 2007 16:15:04 +0000 Subject: Finishing initial docs for all transformations in Passes.html. Also cleaned up some comments in source files. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@43674 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/Passes.html | 449 +++++++++++++++++++++-- lib/Transforms/IPO/StripSymbols.cpp | 20 +- lib/Transforms/Scalar/LowerPacked.cpp | 4 +- lib/Transforms/Scalar/SimplifyCFG.cpp | 10 +- lib/Transforms/Utils/LowerSwitch.cpp | 6 +- lib/Transforms/Utils/PromoteMemoryToRegister.cpp | 2 +- 6 files changed, 435 insertions(+), 56 deletions(-) diff --git a/docs/Passes.html b/docs/Passes.html index 192f4420bf..c144e2ba63 100644 --- a/docs/Passes.html +++ b/docs/Passes.html @@ -1149,7 +1149,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. +

@@ -1157,7 +1161,13 @@ if (i == j) Interprocedural constant propagation
-

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

@@ -1165,7 +1175,10 @@ if (i == j) Interprocedural Sparse Conditional Constant Propagation
-

Yet to be written.

+

+ An interprocedural variant of Sparse Conditional Constant + Propagation. +

@@ -1173,7 +1186,28 @@ if (i == j) Loop-Closed SSA Form Pass
-

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

@@ -1181,7 +1215,36 @@ if (i == j) Loop Invariant Code Motion
-

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

+ +
@@ -1189,7 +1252,12 @@ if (i == j) Extract loops into new functions
-

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

@@ -1197,7 +1265,11 @@ if (i == j) Extract at most one loop into a new function
-

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

@@ -1205,7 +1277,10 @@ if (i == j) Index Split Loops
-

Yet to be written.

+

+ This pass divides loop's iteration range by spliting loop such that each + individual loop is executed efficiently. +

@@ -1213,7 +1288,13 @@ if (i == j) Loop Strength Reduction
-

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

@@ -1221,7 +1302,7 @@ if (i == j) Rotate Loops
-

Yet to be written.

+

A simple loop rotation transformation.

@@ -1229,7 +1310,11 @@ if (i == j) Unroll loops
-

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

@@ -1237,7 +1322,29 @@ if (i == j) Unswitch loops
-

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

@@ -1245,7 +1352,40 @@ if (i == j) Canonicalize natural loops
-

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

@@ -1253,7 +1393,10 @@ if (i == j) lowers packed operations to operations on smaller packed datatypes
-

Yet to be written.

+

+ Lowers operations on vector datatypes into operations on more primitive vector + datatypes, and finally to scalar operations. +

@@ -1261,7 +1404,15 @@ if (i == j) Lower allocations from instructions to calls
-

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

@@ -1269,7 +1420,22 @@ if (i == j) Lower GC intrinsics, for GCless code generators
-

Yet to be written.

+

+ This file implements lowering for the llvm.gc* intrinsics for targets + that do not natively support them (which includes the C backend). Note that + the code generated is not as efficient as it would be for targets that + natively support the GC intrinsics, but it is useful for getting new targets + up-and-running quickly. +

+ +

+ This pass implements the code transformation described in this paper: +

+ +

+ "Accurate Garbage Collection in an Uncooperative Environment" + Fergus Henderson, ISMM, 2002 +

@@ -1277,7 +1443,40 @@ if (i == j) Lower invoke and unwind, for unwindless code generators
-

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

@@ -1285,7 +1484,18 @@ if (i == j) Lower select instructions to branches
-

Yet to be written.

+

+ Lowers select instructions into conditional branches for targets that do not + have conditional moves or that have not implemented the select instruction + yet. +

+ +

+ Note that this pass could be improved. In particular it turns every select + instruction into a new conditional branch, even though some common cases have + select instructions on the same predicate next to each other. It would be + better to use the same branch for the whole group of selects. +

@@ -1293,7 +1503,28 @@ if (i == j) Lower Set Jump
-

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

@@ -1301,7 +1532,11 @@ if (i == j) Lower SwitchInst's to branches
-

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

@@ -1309,7 +1544,15 @@ if (i == j) Promote Memory to Register
-

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

@@ -1317,7 +1560,10 @@ if (i == j) Unify function exit nodes
-

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

@@ -1325,7 +1571,21 @@ if (i == j) Predicate Simplifier
-

Yet to be written.

+

+ Path-sensitive optimizer. In a branch where x == y, replace uses of + x with y. Permits further optimization, such as the + elimination of the unreachable call: +

+ +
void test(int *p, int *q)
+{
+  if (p != q)
+    return;
+
+  if (*p != *q)
+    foo(); // unreachable
+}
@@ -1333,7 +1593,12 @@ if (i == j) Remove unused exception handling info
-

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

@@ -1341,7 +1606,10 @@ if (i == j) Raise allocations from calls to instructions
-

Yet to be written.

+

+ Converts @malloc and @free calls to malloc and + free instructions. +

@@ -1349,7 +1617,22 @@ if (i == j) Reassociate expressions
-

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

@@ -1357,7 +1640,16 @@ if (i == j) Demote all values to stack slots
-

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

@@ -1365,7 +1657,21 @@ if (i == j) Scalar Replacement of Aggregates
-

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

@@ -1373,7 +1679,22 @@ if (i == j) Sparse Conditional Constant Propagation
-

Yet to be written.

+

+ Sparse conditional constant propagation and merging, which can be summarized + as: +

+ +
    +
  1. Assumes values are constant unless proven otherwise
    2. +
  2. Assumes BasicBlocks are dead unless proven otherwise
    3. +
  3. Proves values to be constant, and replaces them with constants
    4. +
  4. Proves conditional branches to be unconditional
    5. +
+ +

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

@@ -1381,7 +1702,12 @@ if (i == j) Simplify well-known library calls
-

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

@@ -1389,7 +1715,18 @@ if (i == j) Simplify the CFG
-

Yet to be written.

+

+ Performs dead code elimination and basic block merging. Specifically: +

+ +
    +
  1. Removes basic blocks with no predecessors.
    2. +
  2. Merges a basic block into its predecessor if there is only one and the + predecessor only has one successor.
    3. +
  3. Eliminates PHI nodes for basic blocks with a single predecessor.
    4. +
  4. Eliminates a basic block that only contains an unconditional + branch.
    5. +
@@ -1397,7 +1734,21 @@ if (i == j) Strip all symbols from a module
-

Yet to be written.

+

+ Performs code stripping. This transformation can delete: +

+ +
    +
  1. names for virtual registers
    2. +
  2. symbols for internal globals and functions
    3. +
  3. debug information
    4. +
+ +

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

@@ -1405,7 +1756,31 @@ if (i == j) Tail Call Elimination
-

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

+ +
@@ -1413,7 +1788,13 @@ if (i == j) Tail Duplication
-

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

diff --git a/lib/Transforms/IPO/StripSymbols.cpp b/lib/Transforms/IPO/StripSymbols.cpp index aaecc2f252..ee60ba2913 100644 --- a/lib/Transforms/IPO/StripSymbols.cpp +++ b/lib/Transforms/IPO/StripSymbols.cpp @@ -7,18 +7,16 @@ // //===----------------------------------------------------------------------===// // -// This file implements stripping symbols out of symbol tables. +// The StripSymbols transformation implements code stripping. Specifically, it +// can delete: +// +// * names for virtual registers +// * symbols for internal globals and functions +// * debug information // -// Specifically, this allows you to strip all of the symbols out of: -// * All functions in a module -// * All non-essential symbols in a module (all function symbols + all module -// scope symbols) -// * Debug information. -// -// Notice that: -// * This pass 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, and making it harder to reverse engineer code). +// 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. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Scalar/LowerPacked.cpp b/lib/Transforms/Scalar/LowerPacked.cpp index 5e4d9eb89a..c91852b9e5 100644 --- a/lib/Transforms/Scalar/LowerPacked.cpp +++ b/lib/Transforms/Scalar/LowerPacked.cpp @@ -7,8 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file implements lowering Packed datatypes into more primitive -// Packed datatypes, and finally to scalar operations. +// This file implements lowering vector datatypes into more primitive +// vector datatypes, and finally to scalar operations. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Scalar/SimplifyCFG.cpp b/lib/Transforms/Scalar/SimplifyCFG.cpp index 6b47ef7aae..5f0ab19b5e 100644 --- a/lib/Transforms/Scalar/SimplifyCFG.cpp +++ b/lib/Transforms/Scalar/SimplifyCFG.cpp @@ -8,13 +8,13 @@ //===----------------------------------------------------------------------===// // // This file implements dead code elimination and basic block merging. +// Specifically: // -// Specifically, this: -// * removes basic blocks with no predecessors -// * merges a basic block into its predecessor if there is only one and the +// * 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 +// * Eliminates PHI nodes for basic blocks with a single predecessor. +// * Eliminates a basic block that only contains an unconditional branch. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Utils/LowerSwitch.cpp b/lib/Transforms/Utils/LowerSwitch.cpp index 3c08edf0c6..dbf3f65d92 100644 --- a/lib/Transforms/Utils/LowerSwitch.cpp +++ b/lib/Transforms/Utils/LowerSwitch.cpp @@ -7,9 +7,9 @@ // //===----------------------------------------------------------------------===// // -// The LowerSwitch transformation rewrites switch statements with a sequence of -// branches, which allows targets to get away with not implementing the switch -// statement until it is convenient. +// The LowerSwitch transformation rewrites switch instructions with a sequence +// of branches, which allows targets to get away with not implementing the +// switch instruction until it is convenient. // //===----------------------------------------------------------------------===// diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index c32457d670..c84da505c2 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This file promote memory references to be register references. It promotes +// 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. -- cgit v1.2.3