X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FProgrammersManual.html;h=716d364ed5699a2c73ca2c84ca93dbf3aee094be;hb=9eb698b96d8b753b2f5025baae0712167cf7fb03;hp=b5b7a9ccf6aba5b12959dae324b5bb5abdb0db3a;hpb=e6a7a8585e0e6302424caab3bda7bddf7c527d5a;p=oota-llvm.git diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index b5b7a9ccf6a..716d364ed56 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -62,6 +62,7 @@ option
+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. +
+ +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 @@ -1173,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). +
+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@@ -1694,7 +1804,7 @@ used as some kind of index by some other code. To accomplish this, I place an-AllocaInst* ai = new AllocaInst(Type::IntTy); +AllocaInst* ai = new AllocaInst(Type::Int32Ty);@@ -1807,9 +1917,7 @@ erase function to remove your instruction. For example:-AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc"); +AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");@@ -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)));Instruction *I = .. ; -BasicBlock *BB = I->getParent(); - -BB->getInstList().erase(I); +I->eraseFromParent();
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
@@ -2063,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
@@ -2082,140 +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 @@ -2749,10 +2752,20 @@ a subclass, which represents the address of a global variable or function.