<li><a href="#dss_vector"><vector></a></li>
<li><a href="#dss_deque"><deque></a></li>
<li><a href="#dss_list"><list></a></li>
- <li><a href="#dss_ilist">llvm/ADT/ilist</a></li>
+ <li><a href="#dss_ilist">llvm/ADT/ilist.h</a></li>
<li><a href="#dss_other">Other Sequential Container Options</a></li>
</ul></li>
<li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
<li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li>
<li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li>
<li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
+ <li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
<li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
<li><a href="#dss_set"><set></a></li>
<li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
<li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
<ul>
<li><a href="#dss_sortedvectormap">A sorted 'vector'</a></li>
- <li><a href="#dss_cstringmap">"llvm/ADT/CStringMap.h"</a></li>
+ <li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li>
<li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li>
<li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li>
<li><a href="#dss_map"><map></a></li>
<li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
</ul></li>
+ <li><a href="#ds_bit">BitVector-like containers</a>
+ <ul>
+ <li><a href="#dss_bitvector">A dense bitvector</a></li>
+ <li><a href="#dss_sparsebitvector">A sparse bitvector</a></li>
+ </ul></li>
</ul>
</li>
<li><a href="#common">Helpful Hints for Common Operations</a>
the same way</a> </li>
<li><a href="#iterate_chains">Iterating over def-use &
use-def chains</a> </li>
+ <li><a href="#iterate_preds">Iterating over predecessors &
+successors of blocks</a></li>
</ul>
</li>
<li><a href="#simplechanges">Making simple changes</a>
<li><a href="#schanges_deleting">Deleting <tt>Instruction</tt>s</a> </li>
<li><a href="#schanges_replacing">Replacing an <tt>Instruction</tt>
with another <tt>Value</tt></a> </li>
+ <li><a href="#schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a> </li>
</ul>
</li>
<!--
<li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li>
</ul></li>
- <li><a href="#SymbolTable">The <tt>SymbolTable</tt> class </a></li>
+ <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes</a></li>
+ <li><a href="#UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a></li>
</ul></li>
<li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
<div class="doc_author">
<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>,
- <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>, and
+ <a href="mailto:ggreif@gmail.com">Gabor Greif</a>,
+ <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a> and
<a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
</div>
standard C++ library.</li>
<li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an
-O'Reilly book in the making. It has a decent
-Standard Library
-Reference that rivals Dinkumware's, and is unfortunately no longer free since the book has been
-published.</li>
+O'Reilly book in the making. It has a decent Standard Library
+Reference that rivals Dinkumware's, and is unfortunately no longer free since the
+book has been published.</li>
<li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked
Questions</a></li>
<dt><tt>cast<></tt>: </dt>
<dd><p>The <tt>cast<></tt> operator is a "checked cast" operation. It
- converts a pointer or reference from a base class to a derived cast, causing
+ converts a pointer or reference from a base class to a derived class, causing
an assertion failure if it is not really an instance of the right type. This
should be used in cases where you have some information that makes you believe
that something is of the right type. An example of the <tt>isa<></tt>
</pre>
</div>
- <p> When running <tt>gccas</tt> on a C file from the SPEC benchmark
+ <p> When running <tt>opt</tt> on a C file from the SPEC benchmark
suite, it gives a report that looks like this:</p>
<div class="doc_code">
<pre>
- 7646 bytecodewriter - Number of normal instructions
- 725 bytecodewriter - Number of oversized instructions
- 129996 bytecodewriter - Number of bytecode bytes written
+ 7646 bitcodewriter - Number of normal instructions
+ 725 bitcodewriter - Number of oversized instructions
+ 129996 bitcodewriter - Number of bitcode bytes written
2817 raise - Number of insts DCEd or constprop'd
3213 raise - Number of cast-of-self removed
5046 raise - Number of expression trees converted
iteration, but do not support efficient look-up based on a key.
</li>
+<li>a <a href="#ds_bit">bit</a> container provides an efficient way to store and
+ perform set operations on sets of numeric id's, while automatically
+ eliminating duplicates. Bit containers require a maximum of 1 bit for each
+ identifier you want to store.
+</li>
</ul>
<p>
<div class="doc_code">
<pre>
for ( ... ) {
- std::vector<foo> V;
+ std::vector<foo> V;
use V;
}
</pre>
<div class="doc_code">
<pre>
-std::vector<foo> V;
+std::vector<foo> V;
for ( ... ) {
use V;
V.clear();
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="dss_ilist">llvm/ADT/ilist</a>
+ <a name="dss_ilist">llvm/ADT/ilist.h</a>
</div>
<div class="doc_text">
intrusive, because it requires the element to store and provide access to the
prev/next pointers for the list.</p>
-<p>ilist has the same drawbacks as std::list, and additionally requires an
-ilist_traits implementation for the element type, but it provides some novel
-characteristics. In particular, it can efficiently store polymorphic objects,
-the traits class is informed when an element is inserted or removed from the
-list, and ilists are guaranteed to support a constant-time splice operation.
-</p>
+<p><tt>ilist</tt> has the same drawbacks as <tt>std::list</tt>, and additionally
+requires an <tt>ilist_traits</tt> implementation for the element type, but it
+provides some novel characteristics. In particular, it can efficiently store
+polymorphic objects, the traits class is informed when an element is inserted or
+removed from the list, and <tt>ilist</tt>s are guaranteed to support a
+constant-time splice operation.</p>
-<p>These properties are exactly what we want for things like Instructions and
-basic blocks, which is why these are implemented with ilists.</p>
+<p>These properties are exactly what we want for things like
+<tt>Instruction</tt>s and basic blocks, which is why these are implemented with
+<tt>ilist</tt>s.</p>
+
+Related classes of interest are explained in the following subsections:
+ <ul>
+ <li><a href="#dss_ilist_traits">ilist_traits</a></li>
+ <li><a href="#dss_iplist">iplist</a></li>
+ <li><a href="#dss_ilist_node">llvm/ADT/ilist_node.h</a></li>
+ </ul>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_ilist_traits">ilist_traits</a>
+</div>
+
+<div class="doc_text">
+<p><tt>ilist_traits<T></tt> is <tt>ilist<T></tt>'s customization
+mechanism. <tt>iplist<T></tt> (and consequently <tt>ilist<T></tt>)
+publicly derive from this traits class.</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_iplist">iplist</a>
+</div>
+
+<div class="doc_text">
+<p><tt>iplist<T></tt> is <tt>ilist<T></tt>'s base and as such
+supports a slightly narrower interface. Notably, inserters from
+<tt>T&</tt> are absent.</p>
+
+<p><tt>ilist_traits<T></tt> is a public base of this class and can be
+used for a wide variety of customizations.</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_ilist_node">llvm/ADT/ilist_node.h</a>
+</div>
+
+<div class="doc_text">
+<p><tt>ilist_node<T></tt> implements a the forward and backward links
+that are expected by the <tt>ilist<T></tt> (and analogous containers)
+in the default manner.</p>
+
+<p><tt>ilist_node<T></tt>s are meant to be embedded in the node type
+<tt>T</tt>, usually <tt>T</tt> publicly derives from
+<tt>ilist_node<T></tt>.</p>
</div>
<!-- _______________________________________________________________________ -->
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_denseset">"llvm/ADT/DenseSet.h"</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+DenseSet is a simple quadratically probed hash table. It excels at supporting
+small values: it uses a single allocation to hold all of the pairs that
+are currently inserted in the set. DenseSet is a great way to unique small
+values that are not simple pointers (use <a
+href="#dss_smallptrset">SmallPtrSet</a> for pointers). Note that DenseSet has
+the same requirements for the value type that <a
+href="#dss_densemap">DenseMap</a> has.
+</p>
+
+</div>
+
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
<a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
<p>
The STL provides several other options, such as std::multiset and the various
-"hash_set" like containers (whether from C++ TR1 or from the SGI library).</p>
+"hash_set" like containers (whether from C++ TR1 or from the SGI library). We
+never use hash_set and unordered_set because they are generally very expensive
+(each insertion requires a malloc) and very non-portable.
+</p>
<p>std::multiset is useful if you're not interested in elimination of
duplicates, but has all the drawbacks of std::set. A sorted vector (where you
don't delete duplicate entries) or some other approach is almost always
better.</p>
-<p>The various hash_set implementations (exposed portably by
-"llvm/ADT/hash_set") is a simple chained hashtable. This algorithm is as malloc
-intensive as std::set (performing an allocation for each element inserted,
-thus having really high constant factors) but (usually) provides O(1)
-insertion/deletion of elements. This can be useful if your elements are large
-(thus making the constant-factor cost relatively low) or if comparisons are
-expensive. Element iteration does not visit elements in a useful order.</p>
-
</div>
<!-- ======================================================================= -->
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="dss_cstringmap">"llvm/ADT/CStringMap.h"</a>
+ <a name="dss_stringmap">"llvm/ADT/StringMap.h"</a>
</div>
<div class="doc_text">
<p>
Strings are commonly used as keys in maps, and they are difficult to support
efficiently: they are variable length, inefficient to hash and compare when
-long, expensive to copy, etc. CStringMap is a specialized container designed to
-cope with these issues. It supports mapping an arbitrary range of bytes that
-does not have an embedded nul character in it ("C strings") to an arbitrary
-other object.</p>
+long, expensive to copy, etc. StringMap is a specialized container designed to
+cope with these issues. It supports mapping an arbitrary range of bytes to an
+arbitrary other object.</p>
-<p>The CStringMap implementation uses a quadratically-probed hash table, where
+<p>The StringMap implementation uses a quadratically-probed hash table, where
the buckets store a pointer to the heap allocated entries (and some other
stuff). The entries in the map must be heap allocated because the strings are
variable length. The string data (key) and the element object (value) are
object. This container guarantees the "<tt>(char*)(&Value+1)</tt>" points
to the key string for a value.</p>
-<p>The CStringMap is very fast for several reasons: quadratic probing is very
+<p>The StringMap is very fast for several reasons: quadratic probing is very
cache efficient for lookups, the hash value of strings in buckets is not
-recomputed when lookup up an element, CStringMap rarely has to touch the
+recomputed when lookup up an element, StringMap rarely has to touch the
memory for unrelated objects when looking up a value (even when hash collisions
happen), hash table growth does not recompute the hash values for strings
already in the table, and each pair in the map is store in a single allocation
(the string data is stored in the same allocation as the Value of a pair).</p>
-<p>CStringMap also provides query methods that take byte ranges, so it only ever
+<p>StringMap also provides query methods that take byte ranges, so it only ever
copies a string if a value is inserted into the table.</p>
</div>
map. Also, because DenseMap allocates space for a large number of key/value
pairs (it starts with 64 by default), it will waste a lot of space if your keys
or values are large. Finally, you must implement a partial specialization of
-DenseMapKeyInfo for the key that you want, if it isn't already supported. This
+DenseMapInfo for the key that you want, if it isn't already supported. This
is required to tell DenseMap about two special marker values (which can never be
inserted into the map) that it needs internally.</p>
<p>
The STL provides several other options, such as std::multimap and the various
-"hash_map" like containers (whether from C++ TR1 or from the SGI library).</p>
+"hash_map" like containers (whether from C++ TR1 or from the SGI library). We
+never use hash_set and unordered_set because they are generally very expensive
+(each insertion requires a malloc) and very non-portable.</p>
<p>std::multimap is useful if you want to map a key to multiple values, but has
all the drawbacks of std::map. A sorted vector or some other approach is almost
always better.</p>
-<p>The various hash_map implementations (exposed portably by
-"llvm/ADT/hash_map") are simple chained hash tables. This algorithm is as
-malloc intensive as std::map (performing an allocation for each element
-inserted, thus having really high constant factors) but (usually) provides O(1)
-insertion/deletion of elements. This can be useful if your elements are large
-(thus making the constant-factor cost relatively low) or if comparisons are
-expensive. Element iteration does not visit elements in a useful order.</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="ds_bit">Bit storage containers (BitVector, SparseBitVector)</a>
+</div>
+
+<div class="doc_text">
+<p>Unlike the other containers, there are only two bit storage containers, and
+choosing when to use each is relatively straightforward.</p>
+<p>One additional option is
+<tt>std::vector<bool></tt>: we discourage its use for two reasons 1) the
+implementation in many common compilers (e.g. commonly available versions of
+GCC) is extremely inefficient and 2) the C++ standards committee is likely to
+deprecate this container and/or change it significantly somehow. In any case,
+please don't use it.</p>
</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_bitvector">BitVector</a>
+</div>
+
+<div class="doc_text">
+<p> The BitVector container provides a fixed size set of bits for manipulation.
+It supports individual bit setting/testing, as well as set operations. The set
+operations take time O(size of bitvector), but operations are performed one word
+at a time, instead of one bit at a time. This makes the BitVector very fast for
+set operations compared to other containers. Use the BitVector when you expect
+the number of set bits to be high (IE a dense set).
+</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_sparsebitvector">SparseBitVector</a>
+</div>
+
+<div class="doc_text">
+<p> The SparseBitVector container is much like BitVector, with one major
+difference: Only the bits that are set, are stored. This makes the
+SparseBitVector much more space efficient than BitVector when the set is sparse,
+as well as making set operations O(number of set bits) instead of O(size of
+universe). The downside to the SparseBitVector is that setting and testing of random bits is O(N), and on large SparseBitVectors, this can be slower than BitVector. In our implementation, setting or testing bits in sorted order
+(either forwards or reverse) is O(1) worst case. Testing and setting bits within 128 bits (depends on size) of the current bit is also O(1). As a general statement, testing/setting bits in a SparseBitVector is O(distance away from last set bit).
+</p>
+</div>
<!-- *********************************************************************** -->
<div class="doc_section">
#include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"
// <i>F is a pointer to a Function instance</i>
-for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)
- llvm::cerr << *i << "\n";
+for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
+ llvm::cerr << *I << "\n";
</pre>
</div>
<div class="doc_code">
<pre>
std::set<Instruction*> worklist;
-worklist.insert(inst_begin(F), inst_end(F));
+// or better yet, SmallPtrSet<Instruction*, 64> worklist;
+
+for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
+ worklist.insert(&*I);
</pre>
</div>
<div class="doc_code">
<pre>
-Instruction* pinst = &*i;
+Instruction *pinst = &*i;
</pre>
</div>
<div class="doc_code">
<pre>
-Instruction* pinst = i;
+Instruction *pinst = i;
</pre>
</div>
virtual runOnFunction(Function& F) {
for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
- for (BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) {
+ for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a
href="#CallInst">CallInst</a>>(&*i)) {
// <i>We know we've encountered a call instruction, so we</i>
// <i>need to determine if it's a call to the</i>
- // <i>function pointed to by m_func or not</i>
-
+ // <i>function pointed to by m_func or not.</i>
if (callInst->getCalledFunction() == targetFunc)
++callCounter;
}
}
private:
- unsigned callCounter;
+ unsigned callCounter;
};
</pre>
</div>
<div class="doc_code">
<pre>
-Function* F = ...;
+Function *F = ...;
for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i)
if (Instruction *Inst = dyn_cast<Instruction>(*i)) {
<div class="doc_code">
<pre>
-Instruction* pi = ...;
+Instruction *pi = ...;
for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
- Value* v = *i;
+ Value *v = *i;
// <i>...</i>
}
</pre>
</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 class="doc_code">
<pre>
-AllocaInst* ai = new AllocaInst(Type::IntTy);
+AllocaInst* ai = new AllocaInst(Type::Int32Ty);
</pre>
</div>
<div class="doc_code">
<pre>
-AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");
+AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");
</pre>
</div>
<div class="doc_code">
<pre>
<a href="#Instruction">Instruction</a> *I = .. ;
-<a href="#BasicBlock">BasicBlock</a> *BB = I->getParent();
-
-BB->getInstList().erase(I);
+I->eraseFromParent();
</pre>
</div>
<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
+ <p>This function replaces all uses 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>
BasicBlock::iterator ii(instToReplace);
ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
- Constant::getNullValue(PointerType::get(Type::IntTy)));
+ Constant::getNullValue(PointerType::getUnqual(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>
+ instruction, inserting the new instruction into the basic block at the
+ location where the old instruction was, and replacing any uses of the old
+ instruction with the new instruction. The following example illustrates
+ the replacement of one <tt>AllocaInst</tt> with another.</p>
<div class="doc_code">
<pre>
BasicBlock::iterator ii(instToReplace);
ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
- new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt"));
+ new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));
</pre></div></li>
</ul>
</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>
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 bytecode reader,
+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>
// <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::IntTy);
+Elts.push_back(PointerType::getUnqual(StructTy));
+Elts.push_back(Type::Int32Ty);
StructType *NewSTy = StructType::get(Elts);
// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
<p>
Some data structures need more to perform more complex updates when types get
-resolved. The <a href="#SymbolTable">SymbolTable</a> class, for example, needs
-move and potentially merge type planes in its representation when a pointer
-changes.</p>
-
-<p>
-To support this, a class can derive from the AbstractTypeUser class. This class
+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>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="SymbolTable">The <tt>SymbolTable</tt> class</a>
+ <a name="SymbolTable">The <tt>ValueSymbolTable</tt> and
+ <tt>TypeSymbolTable</tt> classes</a>
</div>
<div class="doc_text">
-<p>This class provides a symbol table that the <a
+<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 definitions. The symbol table can
-provide a name for any <a href="#Value"><tt>Value</tt></a>.
-<tt>SymbolTable</tt> is an abstract data type. It hides the data it contains
-and provides access to it through a controlled interface.</p>
+<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
-<a href="#Value">Value</a>s have names, and those without names (i.e. they have
+<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>To use the <tt>SymbolTable</tt> well, you need to understand the
-structure of the information it holds. The class contains two
-<tt>std::map</tt> objects. The first, <tt>pmap</tt>, is a map of
-<tt>Type*</tt> to maps of name (<tt>std::string</tt>) to <tt>Value*</tt>.
-Thus, Values are stored in two-dimensions and accessed by <tt>Type</tt> and
-name.</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>
-<p>The interface of this class provides three basic types of operations:
-<ol>
- <li><em>Accessors</em>. Accessors provide read-only access to information
- such as finding a value for a name with the
- <a href="#SymbolTable_lookup">lookup</a> method.</li>
- <li><em>Mutators</em>. Mutators allow the user to add information to the
- <tt>SymbolTable</tt> with methods like
- <a href="#SymbolTable_insert"><tt>insert</tt></a>.</li>
- <li><em>Iterators</em>. Iterators allow the user to traverse the content
- of the symbol table in well defined ways, such as the method
- <a href="#SymbolTable_plane_begin"><tt>plane_begin</tt></a>.</li>
-</ol>
+</div>
-<h3>Accessors</h3>
-<dl>
- <dt><tt>Value* lookup(const Type* Ty, const std::string& name) const</tt>:
- </dt>
- <dd>The <tt>lookup</tt> method searches the type plane given by the
- <tt>Ty</tt> parameter for a <tt>Value</tt> with the provided <tt>name</tt>.
- If a suitable <tt>Value</tt> is not found, null is returned.</dd>
-
- <dt><tt>bool isEmpty() const</tt>:</dt>
- <dd>This function returns true if both the value and types maps are
- empty</dd>
-</dl>
-<h3>Mutators</h3>
-<dl>
- <dt><tt>void insert(Value *Val)</tt>:</dt>
- <dd>This method adds the provided value to the symbol table. The Value must
- have both a name and a type which are extracted and used to place the value
- in the correct type plane under the value's name.</dd>
-
- <dt><tt>void insert(const std::string& Name, Value *Val)</tt>:</dt>
- <dd> Inserts a constant or type into the symbol table with the specified
- name. There can be a many to one mapping between names and constants
- or types.</dd>
-
- <dt><tt>void remove(Value* Val)</tt>:</dt>
- <dd> This method removes a named value from the symbol table. The
- type and name of the Value are extracted from \p N and used to
- lookup the Value in the correct type plane. If the Value is
- not in the symbol table, this method silently ignores the
- request.</dd>
-
- <dt><tt>Value* remove(const std::string& Name, Value *Val)</tt>:</dt>
- <dd> Remove a constant or type with the specified name from the
- symbol table.</dd>
-
- <dt><tt>Value *remove(const value_iterator& It)</tt>:</dt>
- <dd> Removes a specific value from the symbol table.
- Returns the removed value.</dd>
-
- <dt><tt>bool strip()</tt>:</dt>
- <dd> This method will strip the symbol table of its names leaving
- the type and values. </dd>
-
- <dt><tt>void clear()</tt>:</dt>
- <dd>Empty the symbol table completely.</dd>
-</dl>
-<h3>Iteration</h3>
-<p>The following functions describe three types of iterators you can obtain
-the beginning or end of the sequence for both const and non-const. It is
-important to keep track of the different kinds of iterators. There are
-three idioms worth pointing out:</p>
-
-<table>
- <tr><th>Units</th><th>Iterator</th><th>Idiom</th></tr>
- <tr>
- <td align="left">Planes Of name/Value maps</td><td>PI</td>
- <td align="left"><pre><tt>
-for (SymbolTable::plane_const_iterator PI = ST.plane_begin(),
- PE = ST.plane_end(); PI != PE; ++PI ) {
- PI->first // <i>This is the Type* of the plane</i>
- PI->second // <i>This is the SymbolTable::ValueMap of name/Value pairs</i>
-}
- </tt></pre></td>
- </tr>
- <tr>
- <td align="left">name/Value pairs in a plane</td><td>VI</td>
- <td align="left"><pre><tt>
-for (SymbolTable::value_const_iterator VI = ST.value_begin(SomeType),
- VE = ST.value_end(SomeType); VI != VE; ++VI ) {
- VI->first // <i>This is the name of the Value</i>
- VI->second // <i>This is the Value* value associated with the name</i>
-}
- </tt></pre></td>
- </tr>
-</table>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
+</div>
-<p>Using the recommended iterator names and idioms will help you avoid
-making mistakes. Of particular note, make sure that whenever you use
-value_begin(SomeType) that you always compare the resulting iterator
-with value_end(SomeType) not value_end(SomeOtherType) or else you
-will loop infinitely.</p>
+<div class="doc_text">
+<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
+User</a></tt> class provides a basis 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>
-<dl>
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="Use2User">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>
+As of v2.4 each layout still possesses 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 also stores 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>)
+enforce the following memory layouts:</p>
+
+<ul>
+<li><p>Layout a) is 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) is modelled by pointing at the <tt>Use[]</tt> 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="Waymarking">The waymarking algorithm</a>
+</div>
- <dt><tt>plane_iterator plane_begin()</tt>:</dt>
- <dd>Get an iterator that starts at the beginning of the type planes.
- The iterator will iterate over the Type/ValueMap pairs in the
- type planes. </dd>
+<div class="doc_text">
+<p>
+Since the <tt>Use</tt> objects are deprived of the direct (back)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>
- <dt><tt>plane_const_iterator plane_begin() const</tt>:</dt>
- <dd>Get a const_iterator that starts at the beginning of the type
- planes. The iterator will iterate over the Type/ValueMap pairs
- in the type planes. </dd>
+A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> allows 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>
- <dt><tt>plane_iterator plane_end()</tt>:</dt>
- <dd>Get an iterator at the end of the type planes. This serves as
- the marker for end of iteration over the type planes.</dd>
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="ReferenceImpl">Reference implementation</a>
+</div>
- <dt><tt>plane_const_iterator plane_end() const</tt>:</dt>
- <dd>Get a const_iterator at the end of the type planes. This serves as
- the marker for end of iteration over the type planes.</dd>
+<div class="doc_text">
+<p>
+The following literate Haskell fragment demonstrates the concept:</p>
+</div>
- <dt><tt>value_iterator value_begin(const Type *Typ)</tt>:</dt>
- <dd>Get an iterator that starts at the beginning of a type plane.
- The iterator will iterate over the name/value pairs in the type plane.
- Note: The type plane must already exist before using this.</dd>
+<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>
- <dt><tt>value_const_iterator value_begin(const Type *Typ) const</tt>:</dt>
- <dd>Get a const_iterator that starts at the beginning of a type plane.
- The iterator will iterate over the name/value pairs in the type plane.
- Note: The type plane must already exist before using this.</dd>
+<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>
- <dt><tt>value_iterator value_end(const Type *Typ)</tt>:</dt>
- <dd>Get an iterator to the end of a type plane. This serves as the marker
- for end of iteration of the type plane.
- Note: The type plane must already exist before using this.</dd>
+<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>
- <dt><tt>value_const_iterator value_end(const Type *Typ) const</tt>:</dt>
- <dd>Get a const_iterator to the end of a type plane. This serves as the
- marker for end of iteration of the type plane.
- Note: the type plane must already exist before using this.</dd>
+<pre>
+*Main> quickCheck identityProp
+OK, passed 100 tests.
+</pre>
+<p>
+Let's be a bit more exhaustive:</p>
- <dt><tt>plane_const_iterator find(const Type* Typ ) const</tt>:</dt>
- <dd>This method returns a plane_const_iterator for iteration over
- the type planes starting at a specific plane, given by \p Ty.</dd>
+<div class="doc_code">
+<pre>
+>
+> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
+>
+</pre>
+</div>
+<p>
+And here is the result of <deepCheck identityProp>:</p>
- <dt><tt>plane_iterator find( const Type* Typ </tt>:</dt>
- <dd>This method returns a plane_iterator for iteration over the
- type planes starting at a specific plane, given by \p Ty.</dd>
+<pre>
+*Main> deepCheck identityProp
+OK, passed 500 tests.
+</pre>
-</dl>
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="Tagging">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 find a pointer (<tt>User*</tt> with LSBit set).
+Following this pointer brings us to the <tt>User</tt>. A portable trick ensures
+that the first bytes of <tt>User</tt> (if interpreted as a pointer) never has
+the LSBit set. (Portability is relying on the fact that all known compilers place the
+<tt>vptr</tt> in the first word of the instances.)</p>
+</div>
-<!-- *********************************************************************** -->
+ <!-- *********************************************************************** -->
<div class="doc_section">
<a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
</div>
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="m_Value">Important Public Methods</a>
+ <a name="m_Type">Important Public Methods</a>
</div>
<div class="doc_text">
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="m_Value">Important Derived Types</a>
+ <a name="derivedtypes">Important Derived Types</a>
</div>
<div class="doc_text">
<dl>
</dd>
<dt><tt>PointerType</tt></dt>
<dd>Subclass of SequentialType for pointer types.</dd>
- <dt><tt>PackedType</tt></dt>
- <dd>Subclass of SequentialType for packed (vector) types. A
- packed type is similar to an ArrayType but is distinguished because it is
- a first class type wherease ArrayType is not. Packed types are used for
+ <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>FunctionType</tt></dt>
+ <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
</pre>
</div>
-<p><a name="#nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b>
+<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
<li>ConstantInt : This subclass of Constant represents an integer constant of
any width.
<ul>
- <li><tt>int64_t getSExtValue() const</tt>: Returns the underlying value of
- this constant as a sign extended signed integer value.</li>
- <li><tt>uint64_t getZExtValue() const</tt>: Returns the underlying value
- of this constant as a zero extended unsigned integer value.</li>
+ <li><tt>const APInt& getValue() const</tt>: Returns the underlying
+ value of this constant, an APInt value.</li>
+ <li><tt>int64_t getSExtValue() const</tt>: Converts the underlying APInt
+ value to an int64_t via sign extension. If the value (not the bit width)
+ of the APInt is too large to fit in an int64_t, an assertion will result.
+ For this reason, use of this method is discouraged.</li>
+ <li><tt>uint64_t getZExtValue() const</tt>: Converts the underlying APInt
+ value to a uint64_t via zero extension. IF the value (not the bit width)
+ of the APInt is too large to fit in a uint64_t, an assertion will result.
+ For this reason, use of this method is discouraged.</li>
+ <li><tt>static ConstantInt* get(const APInt& Val)</tt>: Returns the
+ ConstantInt object that represents the value provided by <tt>Val</tt>.
+ The type is implied as the IntegerType that corresponds to the bit width
+ of <tt>Val</tt>.</li>
<li><tt>static ConstantInt* get(const Type *Ty, uint64_t Val)</tt>:
Returns the ConstantInt object that represents the value provided by
<tt>Val</tt> for integer type <tt>Ty</tt>.</li>
create and what type of linkage the function should have. The <a
href="#FunctionType"><tt>FunctionType</tt></a> argument
specifies the formal arguments and return value for the function. The same
- <a href="#FunctionTypel"><tt>FunctionType</tt></a> value can be used to
+ <a href="#FunctionType"><tt>FunctionType</tt></a> value can be used to
create multiple functions. The <tt>Parent</tt> argument specifies the Module
in which the function is defined. If this argument is provided, the function
will automatically be inserted into that module's list of
functions.</p></li>
- <li><tt>bool isExternal()</tt>
+ <li><tt>bool isDeclaration()</tt>
<p>Return whether or not the <tt>Function</tt> has a body defined. If the
function is "external", it does not have a body, and thus must be resolved
<p>Create a new global variable of the specified type. If
<tt>isConstant</tt> is true then the global variable will be marked as
unchanging for the program. The Linkage parameter specifies the type of
- linkage (internal, external, weak, linkonce, appending) for the variable. If
- the linkage is InternalLinkage, WeakLinkage, or LinkOnceLinkage, then
- the resultant global variable will have internal linkage. AppendingLinkage
- concatenates together all instances (in different translation units) of the
- variable into a single variable but is only applicable to arrays. See
+ linkage (internal, external, weak, linkonce, appending) for the variable.
+ If the linkage is InternalLinkage, WeakAnyLinkage, WeakODRLinkage,
+ LinkOnceAnyLinkage or LinkOnceODRLinkage, then the resultant
+ global variable will have internal linkage. AppendingLinkage concatenates
+ together all instances (in different translation units) of the variable
+ into a single variable but is only applicable to arrays. See
the <a href="LangRef.html#modulestructure">LLVM Language Reference</a> for
further details on linkage types. Optionally an initializer, a name, and the
module to put the variable into may be specified for the global variable as
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
<a href="http://validator.w3.org/check/referer"><img
- src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
+ src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Strict"></a>
<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
projects / oota-llvm.git / blobdiff