If you have a set-like datastructure that is usually small and whose elements +
If you have a set-like data structure that is usually small and whose elements are reasonably small, a SmallSet<Type, N> is a good choice. This set has space for N elements in place (thus, if the set is dynamically smaller than N, no malloc traffic is required) and accesses them with a simple linear search. @@ -936,7 +977,7 @@ and erasing, but does not support iteration.
SmallPtrSet has all the advantages of SmallSet (and a SmallSet of pointers is -transparently implemented with a SmallPtrSet), but also suports iterators. If +transparently implemented with a SmallPtrSet), but also supports iterators. If more than 'N' insertions are performed, a single quadratically probed hash table is allocated and grows as needed, providing extremely efficient access (constant time insertion/deleting/queries with low constant @@ -948,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. +
+ +LLVM's SetVector<Type> is actually a combination of a set along with -a Sequential Container. The important property +
LLVM's SetVector<Type> is an adapter class that combines your choice of +a set-like container along with a Sequential +Container. The important property that this provides is efficient insertion with uniquing (duplicate elements are ignored) with iteration support. It implements this by inserting elements into both a set-like container and the sequential container, using the set-like @@ -1028,7 +1089,7 @@ container for uniquing and the sequential container for iteration. iteration is guaranteed to match the order of insertion into the SetVector. This property is really important for things like sets of pointers. Because pointer values are non-deterministic (e.g. vary across runs of the program on -different machines), iterating over the pointers in a std::set or other set will +different machines), iterating over the pointers in the set will not be in a well-defined order.
@@ -1036,9 +1097,17 @@ The drawback of SetVector is that it requires twice as much space as a normal set and has the sum of constant factors from the set-like container and the sequential container that it uses. Use it *only* if you need to iterate over the elements in a deterministic order. SetVector is also expensive to delete -elements out of (linear time). +elements out of (linear time), unless you use it's "pop_back" method, which is +faster.
+SetVector is an adapter class that defaults to using std::vector and std::set +for the underlying containers, so it is quite expensive. However, +"llvm/ADT/SetVector.h" also provides a SmallSetVector class, which +defaults to using a SmallVector and SmallSet of a specified size. If you use +this, and if your sets are dynamically smaller than N, you will save a lot of +heap traffic.
+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.
+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. -The CStringMap implementation uses a quadratically-probed hash table, where +
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 @@ -1137,15 +1205,15 @@ stored in the same allocation with the string data immediately after the element object. This container guarantees the "(char*)(&Value+1)" points to the key string for a value.
-The CStringMap is very fast for several reasons: quadratic probing is very +
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).
-CStringMap also provides query methods that take byte ranges, so it only ever +
StringMap also provides query methods that take byte ranges, so it only ever copies a string if a value is inserted into the table.
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). +
+#include "llvm/Support/InstIterator.h" -// F is a ptr to a Function instance -for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) - llvm::cerr << *i << "\n"; +// F is a pointer to a Function instance +for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) + llvm::cerr << *I << "\n";
Easy, isn't it? You can also use InstIterators to fill a -worklist with its initial contents. For example, if you wanted to -initialize a worklist to contain all instructions in a Function +work list with its initial contents. For example, if you wanted to +initialize a work list to contain all instructions in a Function F, all you would need to do is something like:
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)) {
@@ -1582,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;
// ...
}
@@ -1598,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
@@ -1630,12 +1776,12 @@ parameters. For example, an AllocaInst only requires a
-AllocaInst* ai = new AllocaInst(Type::IntTy);
+AllocaInst* ai = new AllocaInst(Type::Int32Ty);
will create an AllocaInst instance that represents the allocation of
-one integer in the current stack frame, at runtime. Each Instruction
+one integer in the current stack frame, at run time. Each Instruction
subclass is likely to have varying default parameters which change the semantics
of the instruction, so refer to the doxygen documentation for the subclass of
@@ -1649,7 +1795,7 @@ at generated LLVM machine code, you definitely want to have logical names
associated with the results of instructions! By supplying a value for the
Name (default) parameter of the Instruction constructor, you
associate a logical name with the result of the instruction's execution at
-runtime. For example, say that I'm writing a transformation that dynamically
+run time. For example, say that I'm writing a transformation that dynamically
allocates space for an integer on the stack, and that integer is going to be
used as some kind of index by some other code. To accomplish this, I place an
AllocaInst at the first point in the first BasicBlock of some
@@ -1658,12 +1804,12 @@ 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");
where indexLoc is now the logical name of the instruction's
-execution value, which is a pointer to an integer on the runtime stack.
+execution value, which is a pointer to an integer on the run time stack.
Inserting instructions
@@ -1771,9 +1917,7 @@ erase function to remove your instruction. For example:
Instruction *I = .. ;
-BasicBlock *BB = I->getParent();
-
-BB->getInstList().erase(I);
+I->eraseFromParent();
@@ -1810,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)));
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(); ++
Some data structures need more to perform more complex updates when types get -resolved. The SymbolTable class, for example, needs -move and potentially merge type planes in its representation when a pointer -changes.
- -
-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
@@ -2027,16 +2189,19 @@ objects) can never be refined.
This class provides a symbol table that the The
+ValueSymbolTable class provides a symbol table that the Function and
-Module classes use for naming definitions. The symbol table can
-provide a name for any Value.
-SymbolTable is an abstract data type. It hides the data it contains
-and provides access to it through a controlled interface. Note that the SymbolTable class should not be directly accessed
by most clients. It should only be used when iteration over the symbol table
@@ -2046,159 +2211,14 @@ all LLVM
an empty name) do not exist in the symbol table.
To use the SymbolTable well, you need to understand the
-structure of the information it holds. The class contains two
-std::map objects. The first, pmap, is a map of
-Type* to maps of name (std::string) to Value*.
-Thus, Values are stored in two-dimensions and accessed by Type and
-name. The interface of this class provides three basic types of operations:
- 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: 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. These symbol tables support iteration over the values/types in the symbol
+table with begin/end/iterator and supports querying to see if a
+specific name is in the symbol table (with lookup). The
+ValueSymbolTable class exposes no public mutator methods, instead,
+simply call setName 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.
-
-
-Accessors
-
-
-
-Mutators
-
-
-
-Iteration
-
-
-
-Units Iterator Idiom
-
- Planes Of name/Value maps PI
-
-for (SymbolTable::plane_const_iterator PI = ST.plane_begin(),
- PE = ST.plane_end(); PI != PE; ++PI ) {
- PI->first // This is the Type* of the plane
- PI->second // This is the SymbolTable::ValueMap of name/Value pairs
-}
-
-
-name/Value pairs in a plane VI
-
-for (SymbolTable::value_const_iterator VI = ST.value_begin(SomeType),
- VE = ST.value_end(SomeType); VI != VE; ++VI ) {
- VI->first // This is the name of the Value
- VI->second // This is the Value* value associated with the name
-}
-
-
-
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 @@ -2732,10 +2752,20 @@ a subclass, which represents the address of a global variable or function.