+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)) {
@@ -1617,10 +1700,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;
// ...
}
@@ -1633,6 +1716,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
@@ -1665,7 +1778,7 @@ parameters. For example, an AllocaInst only requires a
-AllocaInst* ai = new AllocaInst(Type::IntTy);
+AllocaInst* ai = new AllocaInst(Type::Int32Ty);
@@ -1693,7 +1806,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");
@@ -1806,9 +1919,7 @@ erase function to remove your instruction. For example:
Instruction *I = .. ;
-BasicBlock *BB = I->getParent();
-
-BB->getInstList().erase(I);
+I->eraseFromParent();
@@ -1845,7 +1956,7 @@ AllocaInst* instToReplace = ...;
BasicBlock::iterator ii(instToReplace);
ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
- Constant::getNullValue(PointerType::get(Type::IntTy)));
+ Constant::getNullValue(PointerType::get(Type::Int32Ty)));
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:
+ ++GlobalVariable *GV = .. ; + +GV->eraseFromParent(); ++
The +User class provides a base for expressing the ownership of User +towards other +Values. The +Use helper class is employed to do the bookkeeping and to facilitate O(1) +addition and removal.
+ + + + ++A subclass of User can choose between incorporating its Use objects +or refer to them out-of-line by means of a pointer. A mixed variant +(some Uses inline others hung off) is impractical and breaks the invariant +that the Use objects belonging to the same User form a contiguous array. +
++We have 2 different layouts in the User (sub)classes: +
Layout a) +The Use object(s) are inside (resp. at fixed offset) of the User +object and there are a fixed number of them.
+ +Layout b) +The Use object(s) are referenced by a pointer to an +array from the User object and there may be a variable +number of them.
++As of v2.4 each layout still possesses a direct pointer to the +start of the array of Uses. Though not mandatory for layout a), +we stick to this redundancy for the sake of simplicity. +The User object also stores the number of Use objects it +has. (Theoretically this information can also be calculated +given the scheme presented below.)
++Special forms of allocation operators (operator new) +enforce the following memory layouts:
+ +Layout a) is modelled by prepending the User object by the Use[] array.
+ ++...---.---.---.---.-------... + | P | P | P | P | User +'''---'---'---'---'-------''' ++ +
Layout b) is modelled by pointing at the Use[] array.
++.-------... +| User +'-------''' + | + v + .---.---.---.---... + | P | P | P | P | + '---'---'---'---''' ++
+Since the Use objects are deprived of the direct (back)pointer to +their User objects, there must be a fast and exact method to +recover it. This is accomplished by the following scheme:
++Given a Use*, all we have to do is to walk till we get +a stop and we either have a User immediately behind or +we have to walk to the next stop picking up digits +and calculating the offset:
++.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---------------- +| 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*) +'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---------------- + |+15 |+10 |+6 |+3 |+1 + | | | | |__> + | | | |__________> + | | |______________________> + | |______________________________________> + |__________________________________________________________> ++
+Only the significant number of bits need to be stored between the +stops, so that the worst case is 20 memory accesses when there are +1000 Use objects associated with a User.
+ + + + ++The following literate Haskell fragment demonstrates the concept:
++> 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 [] +> ++
+Printing <test> gives: "1s100000s11010s10100s1111s1010s110s11s1S"
++The reverse algorithm computes the length of the string just by examining +a certain prefix:
+ +
+> 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
+>
+
++Now, as expected, printing <pref test> gives 40.
++We can quickCheck this with following property:
+ ++> testcase = dist 2000 [] +> testcaseLength = length testcase +> +> identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr +> where arr = takeLast n testcase +> ++
+As expected <quickCheck identityProp> gives:
+ ++*Main> quickCheck identityProp +OK, passed 100 tests. ++
+Let's be a bit more exhaustive:
+ +
+>
+> deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
+>
+
++And here is the result of <deepCheck identityProp>:
+ ++*Main> deepCheck identityProp +OK, passed 500 tests. ++ + + + +
+To maintain the invariant that the 2 LSBits of each Use** in Use +never change after being set up, setters of Use::Prev must re-tag the +new Use** on every modification. Accordingly getters must strip the +tag bits.
++For layout b) instead of the User we find a pointer (User* with LSBit set). +Following this pointer brings us to the User. A portable trick ensures +that the first bytes of User (if interpreted as a pointer) never has +the LSBit set.
+ +The name of this instruction is "foo". NOTE +
The name of this instruction is "foo". NOTE that the name of any value may be missing (an empty string), so names should ONLY 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 @@ -2805,7 +3161,7 @@ is its address (after linking) which is guaranteed to be constant.
create and what type of linkage the function should have. The FunctionType argument specifies the formal arguments and return value for the function. The same - FunctionType value can be used to + FunctionType value can be used to create multiple functions. The Parent 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 @@ -3055,7 +3411,7 @@ arguments. An argument has a pointer to the parent Function.