+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="calls_and_invokes">Treating calls and invokes the same way</a>
+</div>
+
+<div class="doc_text">
+
+<p>You may have noticed that the previous example was a bit oversimplified in
+that it did not deal with call sites generated by 'invoke' instructions. In
+this, and in other situations, you may find that you want to treat
+<tt>CallInst</tt>s and <tt>InvokeInst</tt>s the same way, even though their
+most-specific common base class is <tt>Instruction</tt>, which includes lots of
+less closely-related things. For these cases, LLVM provides a handy wrapper
+class called <a
+href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>.
+It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some
+methods that provide functionality common to <tt>CallInst</tt>s and
+<tt>InvokeInst</tt>s.</p>
+
+<p>This class has "value semantics": it should be passed by value, not by
+reference and it should not be dynamically allocated or deallocated using
+<tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable,
+assignable and constructable, with costs equivalents to that of a bare pointer.
+If you look at its definition, it has only a single pointer member.</p>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="iterate_chains">Iterating over def-use & use-def chains</a>
+</div>
+
+<div class="doc_text">
+
+<p>Frequently, we might have an instance of the <a
+href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to
+determine which <tt>User</tt>s use the <tt>Value</tt>. The list of all
+<tt>User</tt>s of a particular <tt>Value</tt> is called a <i>def-use</i> chain.
+For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a
+particular function <tt>foo</tt>. Finding all of the instructions that
+<i>use</i> <tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain
+of <tt>F</tt>:</p>
+
+<div class="doc_code">
+<pre>
+Function *F = ...;
+
+for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i)
+ if (Instruction *Inst = dyn_cast<Instruction>(*i)) {
+ llvm::cerr << "F is used in instruction:\n";
+ llvm::cerr << *Inst << "\n";
+ }
+</pre>
+</div>
+
+<p>Alternately, it's common to have an instance of the <a
+href="/doxygen/classllvm_1_1User.html">User Class</a> and need to know what
+<tt>Value</tt>s are used by it. The list of all <tt>Value</tt>s used by a
+<tt>User</tt> is known as a <i>use-def</i> chain. Instances of class
+<tt>Instruction</tt> are common <tt>User</tt>s, so we might want to iterate over
+all of the values that a particular instruction uses (that is, the operands of
+the particular <tt>Instruction</tt>):</p>
+
+<div class="doc_code">
+<pre>
+Instruction *pi = ...;
+
+for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
+ Value *v = *i;
+ // <i>...</i>
+}
+</pre>
+</div>
+
+<!--
+ def-use chains ("finding all users of"): Value::use_begin/use_end
+ use-def chains ("finding all values used"): User::op_begin/op_end [op=operand]
+-->
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="iterate_preds">Iterating over predecessors &
+successors of blocks</a>
+</div>
+
+<div class="doc_text">
+
+<p>Iterating over the predecessors and successors of a block is quite easy
+with the routines defined in <tt>"llvm/Support/CFG.h"</tt>. Just use code like
+this to iterate over all predecessors of BB:</p>
+
+<div class="doc_code">
+<pre>
+#include "llvm/Support/CFG.h"
+BasicBlock *BB = ...;
+
+for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ BasicBlock *Pred = *PI;
+ // <i>...</i>
+}
+</pre>
+</div>
+
+<p>Similarly, to iterate over successors use
+succ_iterator/succ_begin/succ_end.</p>
+
+</div>
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="simplechanges">Making simple changes</a>
+</div>
+
+<div class="doc_text">
+
+<p>There are some primitive transformation operations present in the LLVM
+infrastructure that are worth knowing about. When performing
+transformations, it's fairly common to manipulate the contents of basic
+blocks. This section describes some of the common methods for doing so
+and gives example code.</p>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_creating">Creating and inserting new
+ <tt>Instruction</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<p><i>Instantiating Instructions</i></p>
+
+<p>Creation of <tt>Instruction</tt>s is straight-forward: simply call the
+constructor for the kind of instruction to instantiate and provide the necessary
+parameters. For example, an <tt>AllocaInst</tt> only <i>requires</i> a
+(const-ptr-to) <tt>Type</tt>. Thus:</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* ai = new AllocaInst(Type::Int32Ty);
+</pre>
+</div>
+
+<p>will create an <tt>AllocaInst</tt> instance that represents the allocation of
+one integer in the current stack frame, at run time. Each <tt>Instruction</tt>
+subclass is likely to have varying default parameters which change the semantics
+of the instruction, so refer to the <a
+href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of
+Instruction</a> that you're interested in instantiating.</p>
+
+<p><i>Naming values</i></p>
+
+<p>It is very useful to name the values of instructions when you're able to, as
+this facilitates the debugging of your transformations. If you end up looking
+at generated LLVM machine code, you definitely want to have logical names
+associated with the results of instructions! By supplying a value for the
+<tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you
+associate a logical name with the result of the instruction's execution at
+run time. For example, say that I'm writing a transformation that dynamically
+allocates space for an integer on the stack, and that integer is going to be
+used as some kind of index by some other code. To accomplish this, I place an
+<tt>AllocaInst</tt> at the first point in the first <tt>BasicBlock</tt> of some
+<tt>Function</tt>, and I'm intending to use it within the same
+<tt>Function</tt>. I might do:</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");
+</pre>
+</div>
+
+<p>where <tt>indexLoc</tt> is now the logical name of the instruction's
+execution value, which is a pointer to an integer on the run time stack.</p>
+
+<p><i>Inserting instructions</i></p>
+
+<p>There are essentially two ways to insert an <tt>Instruction</tt>
+into an existing sequence of instructions that form a <tt>BasicBlock</tt>:</p>
+
+<ul>
+ <li>Insertion into an explicit instruction list
+
+ <p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within that
+ <tt>BasicBlock</tt>, and a newly-created instruction we wish to insert
+ before <tt>*pi</tt>, we do the following: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().insert(pi, newInst); // <i>Inserts newInst before pi in pb</i>
+</pre>
+</div>
+
+ <p>Appending to the end of a <tt>BasicBlock</tt> is so common that
+ the <tt>Instruction</tt> class and <tt>Instruction</tt>-derived
+ classes provide constructors which take a pointer to a
+ <tt>BasicBlock</tt> to be appended to. For example code that
+ looked like: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().push_back(newInst); // <i>Appends newInst to pb</i>
+</pre>
+</div>
+
+ <p>becomes: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(..., pb);
+</pre>
+</div>
+
+ <p>which is much cleaner, especially if you are creating
+ long instruction streams.</p></li>
+
+ <li>Insertion into an implicit instruction list
+
+ <p><tt>Instruction</tt> instances that are already in <tt>BasicBlock</tt>s
+ are implicitly associated with an existing instruction list: the instruction
+ list of the enclosing basic block. Thus, we could have accomplished the same
+ thing as the above code without being given a <tt>BasicBlock</tt> by doing:
+ </p>
+
+<div class="doc_code">
+<pre>
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pi->getParent()->getInstList().insert(pi, newInst);
+</pre>
+</div>
+
+ <p>In fact, this sequence of steps occurs so frequently that the
+ <tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes provide
+ constructors which take (as a default parameter) a pointer to an
+ <tt>Instruction</tt> which the newly-created <tt>Instruction</tt> should
+ precede. That is, <tt>Instruction</tt> constructors are capable of
+ inserting the newly-created instance into the <tt>BasicBlock</tt> of a
+ provided instruction, immediately before that instruction. Using an
+ <tt>Instruction</tt> constructor with a <tt>insertBefore</tt> (default)
+ parameter, the above code becomes:</p>
+
+<div class="doc_code">
+<pre>
+Instruction* pi = ...;
+Instruction* newInst = new Instruction(..., pi);
+</pre>
+</div>
+
+ <p>which is much cleaner, especially if you're creating a lot of
+ instructions and adding them to <tt>BasicBlock</tt>s.</p></li>
+</ul>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<p>Deleting an instruction from an existing sequence of instructions that form a
+<a href="#BasicBlock"><tt>BasicBlock</tt></a> is very straight-forward. First,
+you must have a pointer to the instruction that you wish to delete. Second, you
+need to obtain the pointer to that instruction's basic block. You use the
+pointer to the basic block to get its list of instructions and then use the
+erase function to remove your instruction. For example:</p>
+
+<div class="doc_code">
+<pre>
+<a href="#Instruction">Instruction</a> *I = .. ;
+I->eraseFromParent();
+</pre>
+</div>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another
+ <tt>Value</tt></a>
+</div>
+
+<div class="doc_text">
+
+<p><i>Replacing individual instructions</i></p>
+
+<p>Including "<a href="/doxygen/BasicBlockUtils_8h-source.html">llvm/Transforms/Utils/BasicBlockUtils.h</a>"
+permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt>
+and <tt>ReplaceInstWithInst</tt>.</p>
+
+<h4><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h4>
+
+<ul>
+ <li><tt>ReplaceInstWithValue</tt>
+
+ <p>This function replaces all uses (within a basic block) of a given
+ instruction with a value, and then removes the original instruction. The
+ following example illustrates the replacement of the result of a particular
+ <tt>AllocaInst</tt> that allocates memory for a single integer with a null
+ pointer to an integer.</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
+ Constant::getNullValue(PointerType::get(Type::Int32Ty)));
+</pre></div></li>
+
+ <li><tt>ReplaceInstWithInst</tt>
+
+ <p>This function replaces a particular instruction with another
+ instruction. The following example illustrates the replacement of one
+ <tt>AllocaInst</tt> with another.</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
+ new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));
+</pre></div></li>
+</ul>
+
+<p><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></p>
+
+<p>You can use <tt>Value::replaceAllUsesWith</tt> and
+<tt>User::replaceUsesOfWith</tt> to change more than one use at a time. See the
+doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a>
+and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more
+information.</p>
+
+<!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out:
+include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with:
+ReplaceInstWithValue, ReplaceInstWithInst -->
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<p>Deleting a global variable from a module is just as easy as deleting an
+Instruction. First, you must have a pointer to the global variable that you wish
+ to delete. You use this pointer to erase it from its parent, the module.
+ For example:</p>
+
+<div class="doc_code">
+<pre>
+<a href="#GlobalVariable">GlobalVariable</a> *GV = .. ;
+
+GV->eraseFromParent();
+</pre>
+</div>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="advanced">Advanced Topics</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<p>
+This section describes some of the advanced or obscure API's that most clients
+do not need to be aware of. These API's tend manage the inner workings of the
+LLVM system, and only need to be accessed in unusual circumstances.
+</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="TypeResolve">LLVM Type Resolution</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+The LLVM type system has a very simple goal: allow clients to compare types for
+structural equality with a simple pointer comparison (aka a shallow compare).
+This goal makes clients much simpler and faster, and is used throughout the LLVM
+system.
+</p>
+
+<p>
+Unfortunately achieving this goal is not a simple matter. In particular,
+recursive types and late resolution of opaque types makes the situation very
+difficult to handle. Fortunately, for the most part, our implementation makes
+most clients able to be completely unaware of the nasty internal details. The
+primary case where clients are exposed to the inner workings of it are when
+building a recursive type. In addition to this case, the LLVM bitcode reader,
+assembly parser, and linker also have to be aware of the inner workings of this
+system.
+</p>
+
+<p>
+For our purposes below, we need three concepts. First, an "Opaque Type" is
+exactly as defined in the <a href="LangRef.html#t_opaque">language
+reference</a>. Second an "Abstract Type" is any type which includes an
+opaque type as part of its type graph (for example "<tt>{ opaque, i32 }</tt>").
+Third, a concrete type is a type that is not an abstract type (e.g. "<tt>{ i32,
+float }</tt>").
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="BuildRecType">Basic Recursive Type Construction</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+Because the most common question is "how do I build a recursive type with LLVM",
+we answer it now and explain it as we go. Here we include enough to cause this
+to be emitted to an output .ll file:
+</p>
+
+<div class="doc_code">
+<pre>
+%mylist = type { %mylist*, i32 }
+</pre>
+</div>
+
+<p>
+To build this, use the following LLVM APIs:
+</p>
+
+<div class="doc_code">
+<pre>
+// <i>Create the initial outer struct</i>
+<a href="#PATypeHolder">PATypeHolder</a> StructTy = OpaqueType::get();
+std::vector<const Type*> Elts;
+Elts.push_back(PointerType::get(StructTy));
+Elts.push_back(Type::Int32Ty);
+StructType *NewSTy = StructType::get(Elts);
+
+// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
+// <i>the struct and the opaque type are actually the same.</i>
+cast<OpaqueType>(StructTy.get())-><a href="#refineAbstractTypeTo">refineAbstractTypeTo</a>(NewSTy);
+
+// <i>NewSTy is potentially invalidated, but StructTy (a <a href="#PATypeHolder">PATypeHolder</a>) is</i>
+// <i>kept up-to-date</i>
+NewSTy = cast<StructType>(StructTy.get());
+
+// <i>Add a name for the type to the module symbol table (optional)</i>
+MyModule->addTypeName("mylist", NewSTy);
+</pre>
+</div>
+
+<p>
+This code shows the basic approach used to build recursive types: build a
+non-recursive type using 'opaque', then use type unification to close the cycle.
+The type unification step is performed by the <tt><a
+href="#refineAbstractTypeTo">refineAbstractTypeTo</a></tt> method, which is
+described next. After that, we describe the <a
+href="#PATypeHolder">PATypeHolder class</a>.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a>
+</div>
+
+<div class="doc_text">
+<p>
+The <tt>refineAbstractTypeTo</tt> method starts the type unification process.
+While this method is actually a member of the DerivedType class, it is most
+often used on OpaqueType instances. Type unification is actually a recursive
+process. After unification, types can become structurally isomorphic to
+existing types, and all duplicates are deleted (to preserve pointer equality).
+</p>
+
+<p>
+In the example above, the OpaqueType object is definitely deleted.
+Additionally, if there is an "{ \2*, i32}" type already created in the system,
+the pointer and struct type created are <b>also</b> deleted. Obviously whenever
+a type is deleted, any "Type*" pointers in the program are invalidated. As
+such, it is safest to avoid having <i>any</i> "Type*" pointers to abstract types
+live across a call to <tt>refineAbstractTypeTo</tt> (note that non-abstract
+types can never move or be deleted). To deal with this, the <a
+href="#PATypeHolder">PATypeHolder</a> class is used to maintain a stable
+reference to a possibly refined type, and the <a
+href="#AbstractTypeUser">AbstractTypeUser</a> class is used to update more
+complex datastructures.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">The PATypeHolder Class</a>
+</div>
+
+<div class="doc_text">
+<p>
+PATypeHolder is a form of a "smart pointer" for Type objects. When VMCore
+happily goes about nuking types that become isomorphic to existing types, it
+automatically updates all PATypeHolder objects to point to the new type. In the
+example above, this allows the code to maintain a pointer to the resultant
+resolved recursive type, even though the Type*'s are potentially invalidated.
+</p>
+
+<p>
+PATypeHolder is an extremely light-weight object that uses a lazy union-find
+implementation to update pointers. For example the pointer from a Value to its
+Type is maintained by PATypeHolder objects.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="AbstractTypeUser">The AbstractTypeUser Class</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+Some data structures need more to perform more complex updates when types get
+resolved. To support this, a class can derive from the AbstractTypeUser class.
+This class
+allows it to get callbacks when certain types are resolved. To register to get
+callbacks for a particular type, the DerivedType::{add/remove}AbstractTypeUser
+methods can be called on a type. Note that these methods only work for <i>
+ abstract</i> types. Concrete types (those that do not include any opaque
+objects) can never be refined.
+</p>
+</div>
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="SymbolTable">The <tt>ValueSymbolTable</tt> and
+ <tt>TypeSymbolTable</tt> classes</a>
+</div>
+
+<div class="doc_text">
+<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html">
+ValueSymbolTable</a></tt> class provides a symbol table that the <a
+href="#Function"><tt>Function</tt></a> and <a href="#Module">
+<tt>Module</tt></a> classes use for naming value definitions. The symbol table
+can provide a name for any <a href="#Value"><tt>Value</tt></a>.
+The <tt><a href="http://llvm.org/doxygen/classllvm_1_1TypeSymbolTable.html">
+TypeSymbolTable</a></tt> class is used by the <tt>Module</tt> class to store
+names for types.</p>
+
+<p>Note that the <tt>SymbolTable</tt> class should not be directly accessed
+by most clients. It should only be used when iteration over the symbol table
+names themselves are required, which is very special purpose. Note that not
+all LLVM
+<tt><a href="#Value">Value</a></tt>s have names, and those without names (i.e. they have
+an empty name) do not exist in the symbol table.
+</p>
+
+<p>These symbol tables support iteration over the values/types in the symbol
+table with <tt>begin/end/iterator</tt> and supports querying to see if a
+specific name is in the symbol table (with <tt>lookup</tt>). The
+<tt>ValueSymbolTable</tt> class exposes no public mutator methods, instead,
+simply call <tt>setName</tt> on a value, which will autoinsert it into the
+appropriate symbol table. For types, use the Module::addTypeName method to
+insert entries into the symbol table.</p>
+
+</div>
+
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
+</div>
+
+<div class="doc_text">
+<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
+User</a></tt> class provides a base for expressing the ownership of <tt>User</tt>
+towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html">
+Value</a></tt>s. The <tt><a href="http://llvm.org/doxygen/classllvm_1_1Use.html">
+Use</a></tt> helper class is employed to do the bookkeeping and to facilitate <i>O(1)</i>
+addition and removal.</p>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">Interaction and relationship between <tt>User</tt> and <tt>Use</tt> objects</a>
+</div>
+
+<div class="doc_text">
+<p>
+A subclass of <tt>User</tt> can choose between incorporating its <tt>Use</tt> objects
+or refer to them out-of-line by means of a pointer. A mixed variant
+(some <tt>Use</tt>s inline others hung off) is impractical and breaks the invariant
+that the <tt>Use</tt> objects belonging to the same <tt>User</tt> form a contiguous array.
+</p>
+</div>
+
+<p>
+We have 2 different layouts in the <tt>User</tt> (sub)classes:
+<ul>
+<li><p>Layout a)
+The <tt>Use</tt> object(s) are inside (resp. at fixed offset) of the <tt>User</tt>
+object and there are a fixed number of them.</p>
+
+<li><p>Layout b)
+The <tt>Use</tt> object(s) are referenced by a pointer to an
+array from the <tt>User</tt> object and there may be a variable
+number of them.</p>
+</ul>
+<p>
+Initially each layout will possess a direct pointer to the
+start of the array of <tt>Use</tt>s. Though not mandatory for layout a),
+we stick to this redundancy for the sake of simplicity.
+The <tt>User</tt> object will also store the number of <tt>Use</tt> objects it
+has. (Theoretically this information can also be calculated
+given the scheme presented below.)</p>
+<p>
+Special forms of allocation operators (<tt>operator new</tt>)
+will enforce the following memory layouts:</p>
+
+<ul>
+<li><p>Layout a) will be modelled by prepending the <tt>User</tt> object by the <tt>Use[]</tt> array.</p>
+
+<pre>
+...---.---.---.---.-------...
+ | P | P | P | P | User
+'''---'---'---'---'-------'''
+</pre>
+
+<li><p>Layout b) will be modelled by pointing at the Use[] array.</p>
+<pre>
+.-------...
+| User
+'-------'''
+ |
+ v
+ .---.---.---.---...
+ | P | P | P | P |
+ '---'---'---'---'''
+</pre>
+</ul>
+<i>(In the above figures '<tt>P</tt>' stands for the <tt>Use**</tt> that
+ is stored in each <tt>Use</tt> object in the member <tt>Use::Prev</tt>)</i>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">The waymarking algorithm</a>
+</div>
+
+<div class="doc_text">
+<p>
+Since the <tt>Use</tt> objects will be deprived of the direct pointer to
+their <tt>User</tt> objects, there must be a fast and exact method to
+recover it. This is accomplished by the following scheme:</p>
+</div>
+
+A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> will allow to find the
+start of the <tt>User</tt> object:
+<ul>
+<li><tt>00</tt> —> binary digit 0</li>
+<li><tt>01</tt> —> binary digit 1</li>
+<li><tt>10</tt> —> stop and calculate (<tt>s</tt>)</li>
+<li><tt>11</tt> —> full stop (<tt>S</tt>)</li>
+</ul>
+<p>
+Given a <tt>Use*</tt>, all we have to do is to walk till we get
+a stop and we either have a <tt>User</tt> immediately behind or
+we have to walk to the next stop picking up digits
+and calculating the offset:</p>
+<pre>
+.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
+| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
+'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
+ |+15 |+10 |+6 |+3 |+1
+ | | | | |__>
+ | | | |__________>
+ | | |______________________>
+ | |______________________________________>
+ |__________________________________________________________>
+</pre>
+<p>
+Only the significant number of bits need to be stored between the
+stops, so that the <i>worst case is 20 memory accesses</i> when there are
+1000 <tt>Use</tt> objects associated with a <tt>User</tt>.</p>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">Reference implementation</a>
+</div>
+
+<div class="doc_text">
+<p>
+The following literate Haskell fragment demonstrates the concept:</p>
+</div>
+
+<div class="doc_code">
+<pre>
+> import Test.QuickCheck
+>
+> digits :: Int -> [Char] -> [Char]
+> digits 0 acc = '0' : acc
+> digits 1 acc = '1' : acc
+> digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
+>
+> dist :: Int -> [Char] -> [Char]
+> dist 0 [] = ['S']
+> dist 0 acc = acc
+> dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
+> dist n acc = dist (n - 1) $ dist 1 acc
+>
+> takeLast n ss = reverse $ take n $ reverse ss
+>
+> test = takeLast 40 $ dist 20 []
+>
+</pre>
+</div>
+<p>
+Printing <test> gives: <tt>"1s100000s11010s10100s1111s1010s110s11s1S"</tt></p>
+<p>
+The reverse algorithm computes the length of the string just by examining
+a certain prefix:</p>
+
+<div class="doc_code">
+<pre>
+> pref :: [Char] -> Int
+> pref "S" = 1
+> pref ('s':'1':rest) = decode 2 1 rest
+> pref (_:rest) = 1 + pref rest
+>
+> decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
+> decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
+> decode walk acc _ = walk + acc
+>
+</pre>
+</div>
+<p>
+Now, as expected, printing <pref test> gives <tt>40</tt>.</p>
+<p>
+We can <i>quickCheck</i> this with following property:</p>
+
+<div class="doc_code">
+<pre>
+> testcase = dist 2000 []
+> testcaseLength = length testcase
+>
+> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
+> where arr = takeLast n testcase
+>
+</pre>
+</div>
+<p>
+As expected <quickCheck identityProp> gives:</p>
+
+<pre>
+*Main> quickCheck identityProp
+OK, passed 100 tests.
+</pre>
+<p>
+Let's be a bit more exhaustive:</p>
+
+<div class="doc_code">
+<pre>
+>
+> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
+>
+</pre>
+</div>
+<p>
+And here is the result of <deepCheck identityProp>:</p>
+
+<pre>
+*Main> deepCheck identityProp
+OK, passed 500 tests.
+</pre>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">Tagging considerations</a>
+</div>
+
+<p>
+To maintain the invariant that the 2 LSBits of each <tt>Use**</tt> in <tt>Use</tt>
+never change after being set up, setters of <tt>Use::Prev</tt> must re-tag the
+new <tt>Use**</tt> on every modification. Accordingly getters must strip the
+tag bits.</p>
+<p>
+For layout b) instead of the <tt>User</tt> we will find a pointer (<tt>User*</tt> with LSBit set).
+Following this pointer brings us to the <tt>User</tt>. A portable trick will ensure
+that the first bytes of <tt>User</tt> (if interpreted as a pointer) will never have
+the LSBit set.</p>
+
+</div>
+
+ <!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<p><tt>#include "<a href="/doxygen/Type_8h-source.html">llvm/Type.h</a>"</tt>
+<br>doxygen info: <a href="/doxygen/classllvm_1_1Type.html">Type Class</a></p>
+
+<p>The Core LLVM classes are the primary means of representing the program
+being inspected or transformed. The core LLVM classes are defined in
+header files in the <tt>include/llvm/</tt> directory, and implemented in
+the <tt>lib/VMCore</tt> directory.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Type">The <tt>Type</tt> class and Derived Types</a>
+</div>
+
+<div class="doc_text">
+
+ <p><tt>Type</tt> is a superclass of all type classes. Every <tt>Value</tt> has
+ a <tt>Type</tt>. <tt>Type</tt> cannot be instantiated directly but only
+ through its subclasses. Certain primitive types (<tt>VoidType</tt>,
+ <tt>LabelType</tt>, <tt>FloatType</tt> and <tt>DoubleType</tt>) have hidden
+ subclasses. They are hidden because they offer no useful functionality beyond
+ what the <tt>Type</tt> class offers except to distinguish themselves from
+ other subclasses of <tt>Type</tt>.</p>
+ <p>All other types are subclasses of <tt>DerivedType</tt>. Types can be
+ named, but this is not a requirement. There exists exactly
+ one instance of a given shape at any one time. This allows type equality to
+ be performed with address equality of the Type Instance. That is, given two
+ <tt>Type*</tt> values, the types are identical if the pointers are identical.
+ </p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Public Methods</a>
+</div>
+
+<div class="doc_text">
+
+<ul>
+ <li><tt>bool isInteger() const</tt>: Returns true for any integer type.</li>
+
+ <li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two
+ floating point types.</li>
+
+ <li><tt>bool isAbstract()</tt>: Return true if the type is abstract (contains
+ an OpaqueType anywhere in its definition).</li>
+
+ <li><tt>bool isSized()</tt>: Return true if the type has known size. Things
+ that don't have a size are abstract types, labels and void.</li>
+
+</ul>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Derived Types</a>
+</div>
+<div class="doc_text">
+<dl>
+ <dt><tt>IntegerType</tt></dt>
+ <dd>Subclass of DerivedType that represents integer types of any bit width.
+ Any bit width between <tt>IntegerType::MIN_INT_BITS</tt> (1) and
+ <tt>IntegerType::MAX_INT_BITS</tt> (~8 million) can be represented.
+ <ul>
+ <li><tt>static const IntegerType* get(unsigned NumBits)</tt>: get an integer
+ type of a specific bit width.</li>
+ <li><tt>unsigned getBitWidth() const</tt>: Get the bit width of an integer
+ type.</li>
+ </ul>
+ </dd>
+ <dt><tt>SequentialType</tt></dt>
+ <dd>This is subclassed by ArrayType and PointerType
+ <ul>
+ <li><tt>const Type * getElementType() const</tt>: Returns the type of each
+ of the elements in the sequential type. </li>
+ </ul>
+ </dd>
+ <dt><tt>ArrayType</tt></dt>
+ <dd>This is a subclass of SequentialType and defines the interface for array
+ types.
+ <ul>
+ <li><tt>unsigned getNumElements() const</tt>: Returns the number of
+ elements in the array. </li>
+ </ul>
+ </dd>
+ <dt><tt>PointerType</tt></dt>
+ <dd>Subclass of SequentialType for pointer types.</dd>
+ <dt><tt>VectorType</tt></dt>
+ <dd>Subclass of SequentialType for vector types. A
+ vector type is similar to an ArrayType but is distinguished because it is
+ a first class type wherease ArrayType is not. Vector types are used for
+ vector operations and are usually small vectors of of an integer or floating
+ point type.</dd>
+ <dt><tt>StructType</tt></dt>
+ <dd>Subclass of DerivedTypes for struct types.</dd>
+ <dt><tt><a name="FunctionType">FunctionType</a></tt></dt>
+ <dd>Subclass of DerivedTypes for function types.
+ <ul>
+ <li><tt>bool isVarArg() const</tt>: Returns true if its a vararg
+ function</li>
+ <li><tt> const Type * getReturnType() const</tt>: Returns the
+ return type of the function.</li>
+ <li><tt>const Type * getParamType (unsigned i)</tt>: Returns
+ the type of the ith parameter.</li>
+ <li><tt> const unsigned getNumParams() const</tt>: Returns the
+ number of formal parameters.</li>
+ </ul>
+ </dd>
+ <dt><tt>OpaqueType</tt></dt>
+ <dd>Sublcass of DerivedType for abstract types. This class
+ defines no content and is used as a placeholder for some other type. Note
+ that OpaqueType is used (temporarily) during type resolution for forward
+ references of types. Once the referenced type is resolved, the OpaqueType
+ is replaced with the actual type. OpaqueType can also be used for data
+ abstraction. At link time opaque types can be resolved to actual types
+ of the same name.</dd>
+</dl>
+</div>
+
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Module">The <tt>Module</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p><tt>#include "<a
+href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info:
+<a href="/doxygen/classllvm_1_1Module.html">Module Class</a></p>
+
+<p>The <tt>Module</tt> class represents the top level structure present in LLVM
+programs. An LLVM module is effectively either a translation unit of the
+original program or a combination of several translation units merged by the
+linker. The <tt>Module</tt> class keeps track of a list of <a
+href="#Function"><tt>Function</tt></a>s, a list of <a
+href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a
+href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few
+helpful member functions that try to make common operations easy.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Module">Important Public Members of the <tt>Module</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<ul>
+ <li><tt>Module::Module(std::string name = "")</tt></li>
+</ul>
+
+<p>Constructing a <a href="#Module">Module</a> is easy. You can optionally
+provide a name for it (probably based on the name of the translation unit).</p>
+
+<ul>
+ <li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
+ <tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
+
+ <tt>begin()</tt>, <tt>end()</tt>
+ <tt>size()</tt>, <tt>empty()</tt>
+
+ <p>These are forwarding methods that make it easy to access the contents of
+ a <tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a>
+ list.</p></li>
+
+ <li><tt>Module::FunctionListType &getFunctionList()</tt>
+
+ <p> Returns the list of <a href="#Function"><tt>Function</tt></a>s. This is
+ necessary to use when you need to update the list or perform a complex
+ action that doesn't have a forwarding method.</p>
+
+ <p><!-- Global Variable --></p></li>
+</ul>
+
+<hr>
+
+<ul>
+ <li><tt>Module::global_iterator</tt> - Typedef for global variable list iterator<br>
+
+ <tt>Module::const_global_iterator</tt> - Typedef for const_iterator.<br>
+
+ <tt>global_begin()</tt>, <tt>global_end()</tt>
+ <tt>global_size()</tt>, <tt>global_empty()</tt>
+
+ <p> These are forwarding methods that make it easy to access the contents of
+ a <tt>Module</tt> object's <a
+ href="#GlobalVariable"><tt>GlobalVariable</tt></a> list.</p></li>
+
+ <li><tt>Module::GlobalListType &getGlobalList()</tt>
+
+ <p>Returns the list of <a
+ href="#GlobalVariable"><tt>GlobalVariable</tt></a>s. This is necessary to
+ use when you need to update the list or perform a complex action that
+ doesn't have a forwarding method.</p>
+
+ <p><!-- Symbol table stuff --> </p></li>
+</ul>
+
+<hr>
+
+<ul>
+ <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
+
+ <p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
+ for this <tt>Module</tt>.</p>
+
+ <p><!-- Convenience methods --></p></li>
+</ul>
+
+<hr>
+
+<ul>
+ <li><tt><a href="#Function">Function</a> *getFunction(const std::string
+ &Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt>
+
+ <p>Look up the specified function in the <tt>Module</tt> <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return
+ <tt>null</tt>.</p></li>
+
+ <li><tt><a href="#Function">Function</a> *getOrInsertFunction(const
+ std::string &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt>
+
+ <p>Look up the specified function in the <tt>Module</tt> <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an
+ external declaration for the function and return it.</p></li>
+
+ <li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt>
+
+ <p>If there is at least one entry in the <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a
+ href="#Type"><tt>Type</tt></a>, return it. Otherwise return the empty
+ string.</p></li>
+
+ <li><tt>bool addTypeName(const std::string &Name, const <a
+ href="#Type">Type</a> *Ty)</tt>
+
+ <p>Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
+ mapping <tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this
+ name, true is returned and the <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a> is not modified.</p></li>
+</ul>
+
+</div>
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Value">The <tt>Value</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt>
+<br>
+doxygen info: <a href="/doxygen/classllvm_1_1Value.html">Value Class</a></p>
+
+<p>The <tt>Value</tt> class is the most important class in the LLVM Source
+base. It represents a typed value that may be used (among other things) as an
+operand to an instruction. There are many different types of <tt>Value</tt>s,
+such as <a href="#Constant"><tt>Constant</tt></a>s,<a
+href="#Argument"><tt>Argument</tt></a>s. Even <a
+href="#Instruction"><tt>Instruction</tt></a>s and <a
+href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.</p>
+
+<p>A particular <tt>Value</tt> may be used many times in the LLVM representation
+for a program. For example, an incoming argument to a function (represented
+with an instance of the <a href="#Argument">Argument</a> class) is "used" by
+every instruction in the function that references the argument. To keep track
+of this relationship, the <tt>Value</tt> class keeps a list of all of the <a
+href="#User"><tt>User</tt></a>s that is using it (the <a
+href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM
+graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents
+def-use information in the program, and is accessible through the <tt>use_</tt>*
+methods, shown below.</p>
+
+<p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed,
+and this <a href="#Type">Type</a> is available through the <tt>getType()</tt>
+method. In addition, all LLVM values can be named. The "name" of the
+<tt>Value</tt> is a symbolic string printed in the LLVM code:</p>
+
+<div class="doc_code">
+<pre>
+%<b>foo</b> = add i32 1, 2
+</pre>
+</div>
+
+<p><a name="nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b>
+that the name of any value may be missing (an empty string), so names should
+<b>ONLY</b> be used for debugging (making the source code easier to read,
+debugging printouts), they should not be used to keep track of values or map
+between them. For this purpose, use a <tt>std::map</tt> of pointers to the
+<tt>Value</tt> itself instead.</p>
+
+<p>One important aspect of LLVM is that there is no distinction between an SSA
+variable and the operation that produces it. Because of this, any reference to
+the value produced by an instruction (or the value available as an incoming
+argument, for example) is represented as a direct pointer to the instance of
+the class that
+represents this value. Although this may take some getting used to, it
+simplifies the representation and makes it easier to manipulate.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Public Members of the <tt>Value</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<ul>
+ <li><tt>Value::use_iterator</tt> - Typedef for iterator over the
+use-list<br>
+ <tt>Value::use_const_iterator</tt> - Typedef for const_iterator over
+the use-list<br>
+ <tt>unsigned use_size()</tt> - Returns the number of users of the
+value.<br>
+ <tt>bool use_empty()</tt> - Returns true if there are no users.<br>
+ <tt>use_iterator use_begin()</tt> - Get an iterator to the start of
+the use-list.<br>
+ <tt>use_iterator use_end()</tt> - Get an iterator to the end of the
+use-list.<br>
+ <tt><a href="#User">User</a> *use_back()</tt> - Returns the last
+element in the list.
+ <p> These methods are the interface to access the def-use
+information in LLVM. As with all other iterators in LLVM, the naming
+conventions follow the conventions defined by the <a href="#stl">STL</a>.</p>
+ </li>
+ <li><tt><a href="#Type">Type</a> *getType() const</tt>
+ <p>This method returns the Type of the Value.</p>
+ </li>
+ <li><tt>bool hasName() const</tt><br>
+ <tt>std::string getName() const</tt><br>
+ <tt>void setName(const std::string &Name)</tt>
+ <p> This family of methods is used to access and assign a name to a <tt>Value</tt>,
+be aware of the <a href="#nameWarning">precaution above</a>.</p>
+ </li>
+ <li><tt>void replaceAllUsesWith(Value *V)</tt>
+
+ <p>This method traverses the use list of a <tt>Value</tt> changing all <a
+ href="#User"><tt>User</tt>s</a> of the current value to refer to
+ "<tt>V</tt>" instead. For example, if you detect that an instruction always
+ produces a constant value (for example through constant folding), you can
+ replace all uses of the instruction with the constant like this:</p>
+
+<div class="doc_code">
+<pre>
+Inst->replaceAllUsesWith(ConstVal);
+</pre>
+</div>
+
+</ul>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="User">The <tt>User</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+<tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br>
+doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br>
+Superclass: <a href="#Value"><tt>Value</tt></a></p>
+
+<p>The <tt>User</tt> class is the common base class of all LLVM nodes that may
+refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands"
+that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is
+referring to. The <tt>User</tt> class itself is a subclass of
+<tt>Value</tt>.</p>
+
+<p>The operands of a <tt>User</tt> point directly to the LLVM <a
+href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static
+Single Assignment (SSA) form, there can only be one definition referred to,
+allowing this direct connection. This connection provides the use-def
+information in LLVM.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_User">Important Public Members of the <tt>User</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p>The <tt>User</tt> class exposes the operand list in two ways: through
+an index access interface and through an iterator based interface.</p>
+
+<ul>
+ <li><tt>Value *getOperand(unsigned i)</tt><br>
+ <tt>unsigned getNumOperands()</tt>
+ <p> These two methods expose the operands of the <tt>User</tt> in a
+convenient form for direct access.</p></li>
+
+ <li><tt>User::op_iterator</tt> - Typedef for iterator over the operand
+list<br>
+ <tt>op_iterator op_begin()</tt> - Get an iterator to the start of
+the operand list.<br>
+ <tt>op_iterator op_end()</tt> - Get an iterator to the end of the
+operand list.
+ <p> Together, these methods make up the iterator based interface to
+the operands of a <tt>User</tt>.</p></li>
+</ul>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">