<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="#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="#AbstractTypeUser">The AbstractTypeUser Class</a></li>
</ul></li>
- <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes </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>
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_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
+<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>These properties are exactly what we want for things like Instructions and
-basic blocks, which is why these are implemented with ilists.</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>
<!-- ======================================================================= -->
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>
// <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>
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>
-<!-- *********************************************************************** -->
+<!-- ======================================================================= -->
+<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 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>
+
+<!-- ______________________________________________________________________ -->
+<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>
+
+<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>
+
+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>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="ReferenceImpl">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="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>
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