<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>
<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>
+<!-- _______________________________________________________________________ -->
+<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>
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>
</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">
<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>
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>
BasicBlock::iterator ii(instToReplace);
ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
- Constant::getNullValue(PointerType::get(Type::IntTy)));
+ Constant::getNullValue(PointerType::get(Type::Int32Ty)));
</pre></div></li>
<li><tt>ReplaceInstWithInst</tt>
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 class="doc_text">
-<p>Deleting a global variable from a module is similar to deleting an
-instruction. First, you must have a pointer to the global variable that you wish
- to delete. Second, you must have a pointer to the module the global variable
- belongs to. You use the pointer to the module to get its list of global
- variables and then use the erase function to remove your global variable.
+<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 = .. ;
-<a href="#Module">Module</a> *M = GV->getParent();
-M->getGlobaleList().erase(GV);
+GV->eraseFromParent();
</pre>
</div>
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>
<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(Type::Int32Ty);
StructType *NewSTy = StructType::get(Elts);
// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
projects / oota-llvm.git / blobdiff