@@ -976,6 +989,25 @@ visited in sorted order.
+ + + ++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 SmallPtrSet for pointers). Note that DenseSet has +the same requirements for the value type that DenseMap has. +
+ +Unlike the other containers, there are only two bit storage containers, and +choosing when to use each is relatively straightforward.
+ +One additional option is +std::vector<bool>: 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.
+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). +
+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). +
+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);
-Instruction* pinst = &*i; +Instruction *pinst = &*i;
-Instruction* pinst = i; +Instruction *pinst = i;
-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)) {
@@ -1618,10 +1698,10 @@ the particular Instruction):
-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;
// ...
}
@@ -1634,6 +1714,36 @@ for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i)
+
+
+
+
+
+Iterating over the predecessors and successors of a block is quite easy
+with the routines defined in "llvm/Support/CFG.h". Just use code like
+this to iterate over all predecessors of BB:
+
+
+
+#include "llvm/Support/CFG.h"
+BasicBlock *BB = ...;
+
+for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ BasicBlock *Pred = *PI;
+ // ...
+}
+
+
+
+Similarly, to iterate over successors use
+succ_iterator/succ_begin/succ_end.
+
+
+
+
Making simple changes
@@ -1666,7 +1776,7 @@ parameters. For example, an AllocaInst only requires a
-AllocaInst* ai = new AllocaInst(Type::IntTy);
+AllocaInst* ai = new AllocaInst(Type::Int32Ty);
@@ -1694,7 +1804,7 @@ used as some kind of index by some other code. To accomplish this, I place an
-AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");
+AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");
@@ -1807,9 +1917,7 @@ erase function to remove your instruction. For example:
Instruction *I = .. ;
-BasicBlock *BB = I->getParent();
-
-BB->getInstList().erase(I);
+I->eraseFromParent();
@@ -1846,7 +1954,7 @@ AllocaInst* instToReplace = ...;
BasicBlock::iterator ii(instToReplace);
ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
- Constant::getNullValue(PointerType::get(Type::IntTy)));
+ Constant::getNullValue(PointerType::get(Type::Int32Ty)));