LLVM Programmer's Manual

+ +

This document is meant to highlight some of the important classes and +interfaces available in the LLVM source-base. This manual is not +intended to explain what LLVM is, how it works, and what LLVM code looks +like. It assumes that you know the basics of LLVM and are interested +in writing transformations or otherwise analyzing or manipulating the +code.

+ +

This document should get you oriented so that you can find your +way in the continuously growing source code that makes up the LLVM +infrastructure. Note that this manual is not intended to serve as a +replacement for reading the source code, so if you think there should be +a method in one of these classes to do something, but it's not listed, +check the source. Links to the doxygen sources +are provided to make this as easy as possible.

+ +

The first section of this document describes general information that is +useful to know when working in the LLVM infrastructure, and the second describes +the Core LLVM classes. In the future this manual will be extended with +information describing how to use extension libraries, such as dominator +information, CFG traversal routines, and useful utilities like the InstVisitor template.

+ +

This section contains general information that is useful if you are working +in the LLVM source-base, but that isn't specific to any particular API.

+ +

LLVM makes heavy use of the C++ Standard Template Library (STL), +perhaps much more than you are used to, or have seen before. Because of +this, you might want to do a little background reading in the +techniques used and capabilities of the library. There are many good +pages that discuss the STL, and several books on the subject that you +can get, so it will not be discussed in this document.

+ +

Here are some useful links:

+ +

Dinkumware C++ Library +reference - an excellent reference for the STL and other parts of the +standard C++ library.
C++ In a Nutshell - This is an +O'Reilly book in the making. It has a decent +Standard Library +Reference that rivals Dinkumware's, and is unfortunately no longer free since the book has been +published.
C++ Frequently Asked +Questions
SGI's STL Programmer's Guide - +Contains a useful Introduction to the +STL.
Bjarne Stroustrup's C++ +Page
+Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get +the book).

+ +

You are also encouraged to take a look at the LLVM Coding Standards guide which focuses on how +to write maintainable code more than where to put your curly braces.

+ +

Here we highlight some LLVM APIs that are generally useful and good to +know about when writing transformations.

+ +

The LLVM source-base makes extensive use of a custom form of RTTI. +These templates have many similarities to the C++ dynamic_cast<> +operator, but they don't have some drawbacks (primarily stemming from +the fact that dynamic_cast<> only works on classes that +have a v-table). Because they are used so often, you must know what they +do and how they work. All of these templates are defined in the llvm/Support/Casting.h +file (note that you very rarely have to include this file directly).

+ +

isa<>:

The isa<> operator works exactly like the Java + "instanceof" operator. It returns true or false depending on whether + a reference or pointer points to an instance of the specified class. This can + be very useful for constraint checking of various sorts (example below).

cast<>:

The cast<> operator is a "checked cast" operation. It + converts a pointer or reference from a base class to a derived cast, causing + an assertion failure if it is not really an instance of the right type. This + should be used in cases where you have some information that makes you believe + that something is of the right type. An example of the isa<> + and cast<> template is:

+ +

+static bool isLoopInvariant(const Value *V, const Loop *L) {
+  if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V))
+    return true;
+
+  // Otherwise, it must be an instruction...
+  return !L->contains(cast<Instruction>(V)->getParent());
+}
+

+ +

Note that you should not use an isa<> test followed + by a cast<>, for that use the dyn_cast<> + operator.

+ +

dyn_cast<>:

The dyn_cast<> operator is a "checking cast" operation. + It checks to see if the operand is of the specified type, and if so, returns a + pointer to it (this operator does not work with references). If the operand is + not of the correct type, a null pointer is returned. Thus, this works very + much like the dynamic_cast<> operator in C++, and should be + used in the same circumstances. Typically, the dyn_cast<> + operator is used in an if statement or some other flow control + statement like this:

+ +

+if (AllocationInst *AI = dyn_cast<AllocationInst>(Val)) {
+  // ...
+}
+

+ +

This form of the if statement effectively combines together a call + to isa<> and a call to cast<> into one + statement, which is very convenient.

+ +

Note that the dyn_cast<> operator, like C++'s + dynamic_cast<> or Java's instanceof operator, can be + abused. In particular, you should not use big chained if/then/else + blocks to check for lots of different variants of classes. If you find + yourself wanting to do this, it is much cleaner and more efficient to use the + InstVisitor class to dispatch over the instruction type directly.

+ +

cast_or_null<>:

The cast_or_null<> operator works just like the + cast<> operator, except that it allows for a null pointer as an + argument (which it then propagates). This can sometimes be useful, allowing + you to combine several null checks into one.

dyn_cast_or_null<>:

The dyn_cast_or_null<> operator works just like the + dyn_cast<> operator, except that it allows for a null pointer + as an argument (which it then propagates). This can sometimes be useful, + allowing you to combine several null checks into one.

+ +

These five templates can be used with any classes, whether they have a +v-table or not. To add support for these templates, you simply need to add +classof static methods to the class you are interested casting +to. Describing this is currently outside the scope of this document, but there +are lots of examples in the LLVM source base.

+ +

Often when working on your pass you will put a bunch of debugging printouts +and other code into your pass. After you get it working, you want to remove +it, but you may need it again in the future (to work out new bugs that you run +across).

+ +

Naturally, because of this, you don't want to delete the debug printouts, +but you don't want them to always be noisy. A standard compromise is to comment +them out, allowing you to enable them if you need them in the future.

+ +

The "llvm/Support/Debug.h" +file provides a macro named DEBUG() that is a much nicer solution to +this problem. Basically, you can put arbitrary code into the argument of the +DEBUG macro, and it is only executed if 'opt' (or any other +tool) is run with the '-debug' command line argument:

+ +

+DOUT << "I am here!\n";
+

+ +

Then you can run your pass like this:

+ +

+$ opt < a.bc > /dev/null -mypass
+<no output>
+$ opt < a.bc > /dev/null -mypass -debug
+I am here!
+

+ +

Using the DEBUG() macro instead of a home-brewed solution allows you +to not have to create "yet another" command line option for the debug output for +your pass. Note that DEBUG() macros are disabled for optimized builds, +so they do not cause a performance impact at all (for the same reason, they +should also not contain side-effects!).

+ +

One additional nice thing about the DEBUG() macro is that you can +enable or disable it directly in gdb. Just use "set DebugFlag=0" or +"set DebugFlag=1" from the gdb if the program is running. If the +program hasn't been started yet, you can always just run it with +-debug.

+ +

Sometimes you may find yourself in a situation where enabling -debug +just turns on too much information (such as when working on the code +generator). If you want to enable debug information with more fine-grained +control, you define the DEBUG_TYPE macro and the -debug only +option as follows:

+ +

+DOUT << "No debug type\n";
+#undef  DEBUG_TYPE
+#define DEBUG_TYPE "foo"
+DOUT << "'foo' debug type\n";
+#undef  DEBUG_TYPE
+#define DEBUG_TYPE "bar"
+DOUT << "'bar' debug type\n";
+#undef  DEBUG_TYPE
+#define DEBUG_TYPE ""
+DOUT << "No debug type (2)\n";
+

+ +

Then you can run your pass like this:

+ +

+$ opt < a.bc > /dev/null -mypass
+<no output>
+$ opt < a.bc > /dev/null -mypass -debug
+No debug type
+'foo' debug type
+'bar' debug type
+No debug type (2)
+$ opt < a.bc > /dev/null -mypass -debug-only=foo
+'foo' debug type
+$ opt < a.bc > /dev/null -mypass -debug-only=bar
+'bar' debug type
+

+ +

Of course, in practice, you should only set DEBUG_TYPE at the top of +a file, to specify the debug type for the entire module (if you do this before +you #include "llvm/Support/Debug.h", you don't have to insert the ugly +#undef's). Also, you should use names more meaningful than "foo" and +"bar", because there is no system in place to ensure that names do not +conflict. If two different modules use the same string, they will all be turned +on when the name is specified. This allows, for example, all debug information +for instruction scheduling to be enabled with -debug-type=InstrSched, +even if the source lives in multiple files.

+ +

The "llvm/ADT/Statistic.h" file +provides a class named Statistic that is used as a unified way to +keep track of what the LLVM compiler is doing and how effective various +optimizations are. It is useful to see what optimizations are contributing to +making a particular program run faster.

+ +

Often you may run your pass on some big program, and you're interested to see +how many times it makes a certain transformation. Although you can do this with +hand inspection, or some ad-hoc method, this is a real pain and not very useful +for big programs. Using the Statistic class makes it very easy to +keep track of this information, and the calculated information is presented in a +uniform manner with the rest of the passes being executed.

+ +

There are many examples of Statistic uses, but the basics of using +it are as follows:

+ +

Define your statistic like this:
+ +
+
```
+#define DEBUG_TYPE "mypassname"   // This goes before any #includes.
+STATISTIC(NumXForms, "The # of times I did stuff");
+
```
+
+ +
The STATISTIC macro defines a static variable, whose name is + specified by the first argument. The pass name is taken from the DEBUG_TYPE + macro, and the description is taken from the second argument. The variable + defined ("NumXForms" in this case) acts like an unsigned integer.
Whenever you make a transformation, bump the counter:
+ +
+
```
+++NumXForms;   // I did stuff!
+
```
+
+ +

+ +

That's all you have to do. To get 'opt' to print out the + statistics gathered, use the '-stats' option:

+ +

+$ opt -stats -mypassname < program.bc > /dev/null
+... statistics output ...
+

+ +

When running opt on a C file from the SPEC benchmark +suite, it gives a report that looks like this:

+ +

+   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
+     75 raise           - Number of other getelementptr's formed
+    138 raise           - Number of load/store peepholes
+     42 deadtypeelim    - Number of unused typenames removed from symtab
+    392 funcresolve     - Number of varargs functions resolved
+     27 globaldce       - Number of global variables removed
+      2 adce            - Number of basic blocks removed
+    134 cee             - Number of branches revectored
+     49 cee             - Number of setcc instruction eliminated
+    532 gcse            - Number of loads removed
+   2919 gcse            - Number of instructions removed
+     86 indvars         - Number of canonical indvars added
+     87 indvars         - Number of aux indvars removed
+     25 instcombine     - Number of dead inst eliminate
+    434 instcombine     - Number of insts combined
+    248 licm            - Number of load insts hoisted
+   1298 licm            - Number of insts hoisted to a loop pre-header
+      3 licm            - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
+     75 mem2reg         - Number of alloca's promoted
+   1444 cfgsimplify     - Number of blocks simplified
+

+ +

Obviously, with so many optimizations, having a unified framework for this +stuff is very nice. Making your pass fit well into the framework makes it more +maintainable and useful.

+ +

Several of the important data structures in LLVM are graphs: for example +CFGs made out of LLVM BasicBlocks, CFGs made out of +LLVM MachineBasicBlocks, and +Instruction Selection +DAGs. In many cases, while debugging various parts of the compiler, it is +nice to instantly visualize these graphs.

+ +

LLVM provides several callbacks that are available in a debug build to do +exactly that. If you call the Function::viewCFG() method, for example, +the current LLVM tool will pop up a window containing the CFG for the function +where each basic block is a node in the graph, and each node contains the +instructions in the block. Similarly, there also exists +Function::viewCFGOnly() (does not include the instructions), the +MachineFunction::viewCFG() and MachineFunction::viewCFGOnly(), +and the SelectionDAG::viewGraph() methods. Within GDB, for example, +you can usually use something like call DAG.viewGraph() to pop +up a window. Alternatively, you can sprinkle calls to these functions in your +code in places you want to debug.

+ +

Getting this to work requires a small amount of configuration. On Unix +systems with X11, install the graphviz +toolkit, and make sure 'dot' and 'gv' are in your path. If you are running on +Mac OS/X, download and install the Mac OS/X Graphviz program, and add +/Applications/Graphviz.app/Contents/MacOS/ (or wherever you install +it) to your path. Once in your system and path are set up, rerun the LLVM +configure script and rebuild LLVM to enable this functionality.

+ +

SelectionDAG has been extended to make it easier to locate +interesting nodes in large complex graphs. From gdb, if you +call DAG.setGraphColor(node, "color"), then the +next call DAG.viewGraph() would highlight the node in the +specified color (choices of colors can be found at colors.) More +complex node attributes can be provided with call +DAG.setGraphAttrs(node, "attributes") (choices can be +found at Graph +Attributes.) If you want to restart and clear all the current graph +attributes, then you can call DAG.clearGraphAttrs().

+ +

LLVM has a plethora of data structures in the llvm/ADT/ directory, + and we commonly use STL data structures. This section describes the trade-offs + you should consider when you pick one.

+ +

+The first step is a choose your own adventure: do you want a sequential +container, a set-like container, or a map-like container? The most important +thing when choosing a container is the algorithmic properties of how you plan to +access the container. Based on that, you should use:

+ +

a map-like container if you need efficient look-up + of an value based on another value. Map-like containers also support + efficient queries for containment (whether a key is in the map). Map-like + containers generally do not support efficient reverse mapping (values to + keys). If you need that, use two maps. Some map-like containers also + support efficient iteration through the keys in sorted order. Map-like + containers are the most expensive sort, only use them if you need one of + these capabilities.
a set-like container if you need to put a bunch of + stuff into a container that automatically eliminates duplicates. Some + set-like containers support efficient iteration through the elements in + sorted order. Set-like containers are more expensive than sequential + containers. +
a sequential container provides + the most efficient way to add elements and keeps track of the order they are + added to the collection. They permit duplicates and support efficient + iteration, but do not support efficient look-up based on a key. +

+ +

+Once the proper category of container is determined, you can fine tune the +memory use, constant factors, and cache behaviors of access by intelligently +picking a member of the category. Note that constant factors and cache behavior +can be a big deal. If you have a vector that usually only contains a few +elements (but could contain many), for example, it's much better to use +SmallVector than vector +. Doing so avoids (relatively) expensive malloc/free calls, which dwarf the +cost of adding the elements to the container.

+ +

+There are a variety of sequential containers available for you, based on your +needs. Pick the first in this section that will do what you want. +

Fixed size arrays are very simple and very fast. They are good if you know +exactly how many elements you have, or you have a (low) upper bound on how many +you have.

Heap allocated arrays (new[] + delete[]) are also simple. They are good if +the number of elements is variable, if you know how many elements you will need +before the array is allocated, and if the array is usually large (if not, +consider a SmallVector). The cost of a heap +allocated array is the cost of the new/delete (aka malloc/free). Also note that +if you are allocating an array of a type with a constructor, the constructor and +destructors will be run for every element in the array (re-sizable vectors only +construct those elements actually used).

SmallVector<Type, N> is a simple class that looks and smells +just like vector<Type>: +it supports efficient iteration, lays out elements in memory order (so you can +do pointer arithmetic between elements), supports efficient push_back/pop_back +operations, supports efficient random access to its elements, etc.

+ +

The advantage of SmallVector is that it allocates space for +some number of elements (N) in the object itself. Because of this, if +the SmallVector is dynamically smaller than N, no malloc is performed. This can +be a big win in cases where the malloc/free call is far more expensive than the +code that fiddles around with the elements.

+ +

This is good for vectors that are "usually small" (e.g. the number of +predecessors/successors of a block is usually less than 8). On the other hand, +this makes the size of the SmallVector itself large, so you don't want to +allocate lots of them (doing so will waste a lot of space). As such, +SmallVectors are most useful when on the stack.

+ +

SmallVector also provides a nice portable and efficient replacement for +alloca.

+ +

+std::vector is well loved and respected. It is useful when SmallVector isn't: +when the size of the vector is often large (thus the small optimization will +rarely be a benefit) or if you will be allocating many instances of the vector +itself (which would waste space for elements that aren't in the container). +vector is also useful when interfacing with code that expects vectors :). +

+ +

One worthwhile note about std::vector: avoid code like this:

+ +

+for ( ... ) {
+   std::vector<foo> V;
+   use V;
+}
+

+ +

Instead, write this as:

+ +

+std::vector<foo> V;
+for ( ... ) {
+   use V;
+   V.clear();
+}
+

+ +

Doing so will save (at least) one heap allocation and free per iteration of +the loop.

+ +

std::deque is, in some senses, a generalized version of std::vector. Like +std::vector, it provides constant time random access and other similar +properties, but it also provides efficient access to the front of the list. It +does not guarantee continuity of elements within memory.

+ +

In exchange for this extra flexibility, std::deque has significantly higher +constant factor costs than std::vector. If possible, use std::vector or +something cheaper.

std::list is an extremely inefficient class that is rarely useful. +It performs a heap allocation for every element inserted into it, thus having an +extremely high constant factor, particularly for small data types. std::list +also only supports bidirectional iteration, not random access iteration.

+ +

In exchange for this high cost, std::list supports efficient access to both +ends of the list (like std::deque, but unlike std::vector or SmallVector). In +addition, the iterator invalidation characteristics of std::list are stronger +than that of a vector class: inserting or removing an element into the list does +not invalidate iterator or pointers to other elements in the list.

ilist<T> implements an 'intrusive' doubly-linked list. It is +intrusive, because it requires the element to store and provide access to the +prev/next pointers for the list.

+ +

ilist has the same drawbacks as std::list, and additionally requires an +ilist_traits implementation for the element type, but it provides some novel +characteristics. In particular, it can efficiently store polymorphic objects, +the traits class is informed when an element is inserted or removed from the +list, and ilists are guaranteed to support a constant-time splice operation. +

+ +

These properties are exactly what we want for things like Instructions and +basic blocks, which is why these are implemented with ilists.

Other STL containers are available, such as std::string.

+ +

There are also various STL adapter classes such as std::queue, +std::priority_queue, std::stack, etc. These provide simplified access to an +underlying container but don't affect the cost of the container itself.

+ +

Set-like containers are useful when you need to canonicalize multiple values +into a single representation. There are several different choices for how to do +this, providing various trade-offs.

+ +

If you intend to insert a lot of elements, then do a lot of queries, a +great approach is to use a vector (or other sequential container) with +std::sort+std::unique to remove duplicates. This approach works really well if +your usage pattern has these two distinct phases (insert then query), and can be +coupled with a good choice of sequential container. +

+ +

+This combination provides the several nice properties: the result data is +contiguous in memory (good for cache locality), has few allocations, is easy to +address (iterators in the final vector are just indices or pointers), and can be +efficiently queried with a standard binary or radix search.

+ +

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. +When the set grows beyond 'N' elements, it allocates a more expensive representation that +guarantees efficient access (for most types, it falls back to std::set, but for +pointers it uses something far better, SmallPtrSet).

+ +

The magic of this class is that it handles small sets extremely efficiently, +but gracefully handles extremely large sets without loss of efficiency. The +drawback is that the interface is quite small: it supports insertion, queries +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 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 +factors) and is very stingy with malloc traffic.

+ +

Note that, unlike std::set, the iterators of SmallPtrSet are invalidated +whenever an insertion occurs. Also, the values visited by the iterators are not +visited in sorted order.

+ +

+FoldingSet is an aggregate class that is really good at uniquing +expensive-to-create or polymorphic objects. It is a combination of a chained +hash table with intrusive links (uniqued objects are required to inherit from +FoldingSetNode) that uses SmallVector as part of +its ID process.

+ +

Consider a case where you want to implement a "getOrCreateFoo" method for +a complex object (for example, a node in the code generator). The client has a +description of *what* it wants to generate (it knows the opcode and all the +operands), but we don't want to 'new' a node, then try inserting it into a set +only to find out it already exists, at which point we would have to delete it +and return the node that already exists. +

+ +

To support this style of client, FoldingSet perform a query with a +FoldingSetNodeID (which wraps SmallVector) that can be used to describe the +element that we want to query for. The query either returns the element +matching the ID or it returns an opaque ID that indicates where insertion should +take place. Construction of the ID usually does not require heap traffic.

+ +

Because FoldingSet uses intrusive links, it can support polymorphic objects +in the set (for example, you can have SDNode instances mixed with LoadSDNodes). +Because the elements are individually allocated, pointers to the elements are +stable: inserting or removing elements does not invalidate any pointers to other +elements. +

+ +

std::set is a reasonable all-around set class, which is decent at +many things but great at nothing. std::set allocates memory for each element +inserted (thus it is very malloc intensive) and typically stores three pointers +per element in the set (thus adding a large amount of per-element space +overhead). It offers guaranteed log(n) performance, which is not particularly +fast from a complexity standpoint (particularly if the elements of the set are +expensive to compare, like strings), and has extremely high constant factors for +lookup, insertion and removal.

+ +

The advantages of std::set are that its iterators are stable (deleting or +inserting an element from the set does not affect iterators or pointers to other +elements) and that iteration over the set is guaranteed to be in sorted order. +If the elements in the set are large, then the relative overhead of the pointers +and malloc traffic is not a big deal, but if the elements of the set are small, +std::set is almost never a good choice.

+ +

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 +container for uniquing and the sequential container for iteration. +

+ +

The difference between SetVector and other sets is that the order of +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 the set will +not be in a well-defined order.

+ +

+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), 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.

+ +

+UniqueVector is similar to SetVector, but it +retains a unique ID for each element inserted into the set. It internally +contains a map and a vector, and it assigns a unique ID for each value inserted +into the set.

+ +

UniqueVector is very expensive: its cost is the sum of the cost of +maintaining both the map and vector, it has high complexity, high constant +factors, and produces a lot of malloc traffic. It should be avoided.

+ +

+The STL provides several other options, such as std::multiset and the various +"hash_set" like containers (whether from C++ TR1 or from the SGI library).

+ +

std::multiset is useful if you're not interested in elimination of +duplicates, but has all the drawbacks of std::set. A sorted vector (where you +don't delete duplicate entries) or some other approach is almost always +better.

+ +

The various hash_set implementations (exposed portably by +"llvm/ADT/hash_set") is a simple chained hashtable. This algorithm is as malloc +intensive as std::set (performing an allocation for each element inserted, +thus having really high constant factors) but (usually) provides O(1) +insertion/deletion of elements. This can be useful if your elements are large +(thus making the constant-factor cost relatively low) or if comparisons are +expensive. Element iteration does not visit elements in a useful order.

+ +

+Map-like containers are useful when you want to associate data to a key. As +usual, there are a lot of different ways to do this. :) +

+ +

+If your usage pattern follows a strict insert-then-query approach, you can +trivially use the same approach as sorted vectors +for set-like containers. The only difference is that your query function +(which uses std::lower_bound to get efficient log(n) lookup) should only compare +the key, not both the key and value. This yields the same advantages as sorted +vectors for sets. +

+ +

+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. 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 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 +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 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, 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).

+ +

StringMap also provides query methods that take byte ranges, so it only ever +copies a string if a value is inserted into the table.

+IndexedMap is a specialized container for mapping small dense integers (or +values that can be mapped to small dense integers) to some other type. It is +internally implemented as a vector with a mapping function that maps the keys to +the dense integer range. +

+ +

+This is useful for cases like virtual registers in the LLVM code generator: they +have a dense mapping that is offset by a compile-time constant (the first +virtual register ID).

+ +

+DenseMap is a simple quadratically probed hash table. It excels at supporting +small keys and values: it uses a single allocation to hold all of the pairs that +are currently inserted in the map. DenseMap is a great way to map pointers to +pointers, or map other small types to each other. +

+ +

+There are several aspects of DenseMap that you should be aware of, however. The +iterators in a densemap are invalidated whenever an insertion occurs, unlike +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 +is required to tell DenseMap about two special marker values (which can never be +inserted into the map) that it needs internally.

+ +

+std::map has similar characteristics to std::set: it uses +a single allocation per pair inserted into the map, it offers log(n) lookup with +an extremely large constant factor, imposes a space penalty of 3 pointers per +pair in the map, etc.

+ +

std::map is most useful when your keys or values are very large, if you need +to iterate over the collection in sorted order, or if you need stable iterators +into the map (i.e. they don't get invalidated if an insertion or deletion of +another element takes place).

+ +

+The STL provides several other options, such as std::multimap and the various +"hash_map" like containers (whether from C++ TR1 or from the SGI library).

+ +

std::multimap is useful if you want to map a key to multiple values, but has +all the drawbacks of std::map. A sorted vector or some other approach is almost +always better.

+ +

The various hash_map implementations (exposed portably by +"llvm/ADT/hash_map") are simple chained hash tables. This algorithm is as +malloc intensive as std::map (performing an allocation for each element +inserted, thus having really high constant factors) but (usually) provides O(1) +insertion/deletion of elements. This can be useful if your elements are large +(thus making the constant-factor cost relatively low) or if comparisons are +expensive. Element iteration does not visit elements in a useful order.

+ +

This section describes how to perform some very simple transformations of +LLVM code. This is meant to give examples of common idioms used, showing the +practical side of LLVM transformations.

Because this is a "how-to" section, +you should also read about the main classes that you will be working with. The +Core LLVM Class Hierarchy Reference contains details +and descriptions of the main classes that you should know about.

+ +

The LLVM compiler infrastructure have many different data structures that may +be traversed. Following the example of the C++ standard template library, the +techniques used to traverse these various data structures are all basically the +same. For a enumerable sequence of values, the XXXbegin() function (or +method) returns an iterator to the start of the sequence, the XXXend() +function returns an iterator pointing to one past the last valid element of the +sequence, and there is some XXXiterator data type that is common +between the two operations.

+ +

Because the pattern for iteration is common across many different aspects of +the program representation, the standard template library algorithms may be used +on them, and it is easier to remember how to iterate. First we show a few common +examples of the data structures that need to be traversed. Other data +structures are traversed in very similar ways.

+ +

It's quite common to have a Function instance that you'd like to +transform in some way; in particular, you'd like to manipulate its +BasicBlocks. To facilitate this, you'll need to iterate over all of +the BasicBlocks that constitute the Function. The following is +an example that prints the name of a BasicBlock and the number of +Instructions it contains:

+ +

+// func is a pointer to a Function instance
+for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i)
+  // Print out the name of the basic block if it has one, and then the
+  // number of instructions that it contains
+  llvm::cerr << "Basic block (name=" << i->getName() << ") has "
+             << i->size() << " instructions.\n";
+

+ +

Note that i can be used as if it were a pointer for the purposes of +invoking member functions of the Instruction class. This is +because the indirection operator is overloaded for the iterator +classes. In the above code, the expression i->size() is +exactly equivalent to (*i).size() just like you'd expect.

+ +

Just like when dealing with BasicBlocks in Functions, it's +easy to iterate over the individual instructions that make up +BasicBlocks. Here's a code snippet that prints out each instruction in +a BasicBlock:

+ +

+// blk is a pointer to a BasicBlock instance
+for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
+   // The next statement works since operator<<(ostream&,...)
+   // is overloaded for Instruction&
+   llvm::cerr << *i << "\n";
+

+ +

However, this isn't really the best way to print out the contents of a +BasicBlock! Since the ostream operators are overloaded for virtually +anything you'll care about, you could have just invoked the print routine on the +basic block itself: llvm::cerr << *blk << "\n";.

+ +

If you're finding that you commonly iterate over a Function's +BasicBlocks and then that BasicBlock's Instructions, +InstIterator should be used instead. You'll need to include llvm/Support/InstIterator.h, +and then instantiate InstIterators explicitly in your code. Here's a +small example that shows how to dump all instructions in a function to the standard error stream:

+ +

+#include "llvm/Support/InstIterator.h"
+
+// 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 +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));
+

+ +

The STL set worklist would now contain all instructions in the +Function pointed to by F.

+ +

Sometimes, it'll be useful to grab a reference (or pointer) to a class +instance when all you've got at hand is an iterator. Well, extracting +a reference or a pointer from an iterator is very straight-forward. +Assuming that i is a BasicBlock::iterator and j +is a BasicBlock::const_iterator:

+ +

+Instruction& inst = *i;   // Grab reference to instruction reference
+Instruction* pinst = &*i; // Grab pointer to instruction reference
+const Instruction& inst = *j;
+

+ +

However, the iterators you'll be working with in the LLVM framework are +special: they will automatically convert to a ptr-to-instance type whenever they +need to. Instead of dereferencing the iterator and then taking the address of +the result, you can simply assign the iterator to the proper pointer type and +you get the dereference and address-of operation as a result of the assignment +(behind the scenes, this is a result of overloading casting mechanisms). Thus +the last line of the last example,

+ +

+Instruction* pinst = &*i;
+

+ +

is semantically equivalent to

+ +

+Instruction* pinst = i;
+

+ +

It's also possible to turn a class pointer into the corresponding iterator, +and this is a constant time operation (very efficient). The following code +snippet illustrates use of the conversion constructors provided by LLVM +iterators. By using these, you can explicitly grab the iterator of something +without actually obtaining it via iteration over some structure:

+ +

+void printNextInstruction(Instruction* inst) {
+  BasicBlock::iterator it(inst);
+  ++it; // After this line, it refers to the instruction after *inst
+  if (it != inst->getParent()->end()) llvm::cerr << *it << "\n";
+}
+

+ +

Say that you're writing a FunctionPass and would like to count all the +locations in the entire module (that is, across every Function) where a +certain function (i.e., some Function*) is already in scope. As you'll +learn later, you may want to use an InstVisitor to accomplish this in a +much more straight-forward manner, but this example will allow us to explore how +you'd do it if you didn't have InstVisitor around. In pseudo-code, this +is what we want to do:

+ +

+initialize callCounter to zero
+for each Function f in the Module
+  for each BasicBlock b in f
+    for each Instruction i in b
+      if (i is a CallInst and calls the given function)
+        increment callCounter
+

+ +

And the actual code is (remember, because we're writing a +FunctionPass, our FunctionPass-derived class simply has to +override the runOnFunction method):

+ +

+Function* targetFunc = ...;
+
+class OurFunctionPass : public FunctionPass {
+  public:
+    OurFunctionPass(): callCounter(0) { }
+
+    virtual runOnFunction(Function& F) {
+      for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
+        for (BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) {
+          if (CallInst* callInst = dyn_cast<CallInst>(&*i)) {
+            // We know we've encountered a call instruction, so we
+            // need to determine if it's a call to the
+            // function pointed to by m_func or not
+
+            if (callInst->getCalledFunction() == targetFunc)
+              ++callCounter;
+          }
+        }
+      }
+    }
+
+  private:
+    unsigned  callCounter;
+};
+

+ +

You may have noticed that the previous example was a bit oversimplified in +that it did not deal with call sites generated by 'invoke' instructions. In +this, and in other situations, you may find that you want to treat +CallInsts and InvokeInsts the same way, even though their +most-specific common base class is Instruction, which includes lots of +less closely-related things. For these cases, LLVM provides a handy wrapper +class called CallSite. +It is essentially a wrapper around an Instruction pointer, with some +methods that provide functionality common to CallInsts and +InvokeInsts.

+ +

This class has "value semantics": it should be passed by value, not by +reference and it should not be dynamically allocated or deallocated using +operator new or operator delete. It is efficiently copyable, +assignable and constructable, with costs equivalents to that of a bare pointer. +If you look at its definition, it has only a single pointer member.

+ +

Frequently, we might have an instance of the Value Class and we want to +determine which Users use the Value. The list of all +Users of a particular Value is called a def-use chain. +For example, let's say we have a Function* named F to a +particular function foo. Finding all of the instructions that +use foo is as simple as iterating over the def-use chain +of 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)) {
+    llvm::cerr << "F is used in instruction:\n";
+    llvm::cerr << *Inst << "\n";
+  }
+

+ +

Alternately, it's common to have an instance of the User Class and need to know what +Values are used by it. The list of all Values used by a +User is known as a use-def chain. Instances of class +Instruction are common Users, so we might want to iterate over +all of the values that a particular instruction uses (that is, the operands of +the particular Instruction):

+ +

+Instruction* pi = ...;
+
+for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
+  Value* v = *i;
+  // ...
+}
+

+ + + +

+ +

There are some primitive transformation operations present in the LLVM +infrastructure that are worth knowing about. When performing +transformations, it's fairly common to manipulate the contents of basic +blocks. This section describes some of the common methods for doing so +and gives example code.

+ +

Instantiating Instructions

+ +

Creation of Instructions is straight-forward: simply call the +constructor for the kind of instruction to instantiate and provide the necessary +parameters. For example, an AllocaInst only requires a +(const-ptr-to) Type. Thus:

+ +

+AllocaInst* ai = new AllocaInst(Type::IntTy);
+

+ +

will create an AllocaInst instance that represents the allocation of +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 +Instruction that you're interested in instantiating.

+ +

Naming values

+ +

It is very useful to name the values of instructions when you're able to, as +this facilitates the debugging of your transformations. If you end up looking +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 +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 +Function, and I'm intending to use it within the same +Function. I might do:

+ +

+AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");
+

+ +

where indexLoc is now the logical name of the instruction's +execution value, which is a pointer to an integer on the run time stack.

+ +

Inserting instructions

+ +

There are essentially two ways to insert an Instruction +into an existing sequence of instructions that form a BasicBlock:

+ +

Insertion into an explicit instruction list + +
Given a BasicBlock* pb, an Instruction* pi within that + BasicBlock, and a newly-created instruction we wish to insert + before *pi, we do the following:
+ +
+
```
+BasicBlock *pb = ...;
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().insert(pi, newInst); // Inserts newInst before pi in pb
+
```
+
+ +
Appending to the end of a BasicBlock is so common that + the Instruction class and Instruction-derived + classes provide constructors which take a pointer to a + BasicBlock to be appended to. For example code that + looked like:
+ +
+
```
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().push_back(newInst); // Appends newInst to pb
+
```
+
+ +
becomes:
+ +
+
```
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(..., pb);
+
```
+
+ +
which is much cleaner, especially if you are creating + long instruction streams.
Insertion into an implicit instruction list + +
Instruction instances that are already in BasicBlocks + are implicitly associated with an existing instruction list: the instruction + list of the enclosing basic block. Thus, we could have accomplished the same + thing as the above code without being given a BasicBlock by doing: +
+ +
+
```
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pi->getParent()->getInstList().insert(pi, newInst);
+
```
+
+ +
In fact, this sequence of steps occurs so frequently that the + Instruction class and Instruction-derived classes provide + constructors which take (as a default parameter) a pointer to an + Instruction which the newly-created Instruction should + precede. That is, Instruction constructors are capable of + inserting the newly-created instance into the BasicBlock of a + provided instruction, immediately before that instruction. Using an + Instruction constructor with a insertBefore (default) + parameter, the above code becomes:
+ +
+
```
+Instruction* pi = ...;
+Instruction* newInst = new Instruction(..., pi);
+
```
+
+ +
which is much cleaner, especially if you're creating a lot of + instructions and adding them to BasicBlocks.

+ +

Deleting an instruction from an existing sequence of instructions that form a +BasicBlock is very straight-forward. First, +you must have a pointer to the instruction that you wish to delete. Second, you +need to obtain the pointer to that instruction's basic block. You use the +pointer to the basic block to get its list of instructions and then use the +erase function to remove your instruction. For example:

+ +

+Instruction *I = .. ;
+BasicBlock *BB = I->getParent();
+
+BB->getInstList().erase(I);
+

+ +

Replacing individual instructions

+ +

Including "llvm/Transforms/Utils/BasicBlockUtils.h" +permits use of two very useful replace functions: ReplaceInstWithValue +and ReplaceInstWithInst.

+ +

Deleting `Instruction`s

+ +

ReplaceInstWithValue + +
This function replaces all uses (within a basic block) of a given + instruction with a value, and then removes the original instruction. The + following example illustrates the replacement of the result of a particular + AllocaInst that allocates memory for a single integer with a null + pointer to an integer.
+ +
+
```
+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
+                     Constant::getNullValue(PointerType::get(Type::IntTy)));
+
```

ReplaceInstWithInst + +

This function replaces a particular instruction with another + instruction. The following example illustrates the replacement of one + AllocaInst with another.

+ +

+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
+                    new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt"));
+

+ +

Replacing multiple uses of Users and Values

+ +

You can use Value::replaceAllUsesWith and +User::replaceUsesOfWith to change more than one use at a time. See the +doxygen documentation for the Value Class +and User Class, respectively, for more +information.

+ + + +

+ +

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();
+

+ +

+This section describes some of the advanced or obscure API's that most clients +do not need to be aware of. These API's tend manage the inner workings of the +LLVM system, and only need to be accessed in unusual circumstances. +

+ +

+The LLVM type system has a very simple goal: allow clients to compare types for +structural equality with a simple pointer comparison (aka a shallow compare). +This goal makes clients much simpler and faster, and is used throughout the LLVM +system. +

+ +

+Unfortunately achieving this goal is not a simple matter. In particular, +recursive types and late resolution of opaque types makes the situation very +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 bitcode reader, +assembly parser, and linker also have to be aware of the inner workings of this +system. +

+ +

+For our purposes below, we need three concepts. First, an "Opaque Type" is +exactly as defined in the language +reference. Second an "Abstract Type" is any type which includes an +opaque type as part of its type graph (for example "{ opaque, i32 }"). +Third, a concrete type is a type that is not an abstract type (e.g. "{ i32, +float }"). +

+ +

+Because the most common question is "how do I build a recursive type with LLVM", +we answer it now and explain it as we go. Here we include enough to cause this +to be emitted to an output .ll file: +

+ +

+%mylist = type { %mylist*, i32 }
+

+ +

+To build this, use the following LLVM APIs: +

+ +

+// Create the initial outer struct
+PATypeHolder StructTy = OpaqueType::get();
+std::vector<const Type*> Elts;
+Elts.push_back(PointerType::get(StructTy));
+Elts.push_back(Type::IntTy);
+StructType *NewSTy = StructType::get(Elts);
+
+// At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that
+// the struct and the opaque type are actually the same.
+cast<OpaqueType>(StructTy.get())->refineAbstractTypeTo(NewSTy);
+
+// NewSTy is potentially invalidated, but StructTy (a PATypeHolder) is
+// kept up-to-date
+NewSTy = cast<StructType>(StructTy.get());
+
+// Add a name for the type to the module symbol table (optional)
+MyModule->addTypeName("mylist", NewSTy);
+

+ +

+This code shows the basic approach used to build recursive types: build a +non-recursive type using 'opaque', then use type unification to close the cycle. +The type unification step is performed by the refineAbstractTypeTo method, which is +described next. After that, we describe the PATypeHolder class. +

+ +

+The refineAbstractTypeTo method starts the type unification process. +While this method is actually a member of the DerivedType class, it is most +often used on OpaqueType instances. Type unification is actually a recursive +process. After unification, types can become structurally isomorphic to +existing types, and all duplicates are deleted (to preserve pointer equality). +

+ +

+In the example above, the OpaqueType object is definitely deleted. +Additionally, if there is an "{ \2*, i32}" type already created in the system, +the pointer and struct type created are also deleted. Obviously whenever +a type is deleted, any "Type*" pointers in the program are invalidated. As +such, it is safest to avoid having any "Type*" pointers to abstract types +live across a call to refineAbstractTypeTo (note that non-abstract +types can never move or be deleted). To deal with this, the PATypeHolder class is used to maintain a stable +reference to a possibly refined type, and the AbstractTypeUser class is used to update more +complex datastructures. +

+ +

+PATypeHolder is a form of a "smart pointer" for Type objects. When VMCore +happily goes about nuking types that become isomorphic to existing types, it +automatically updates all PATypeHolder objects to point to the new type. In the +example above, this allows the code to maintain a pointer to the resultant +resolved recursive type, even though the Type*'s are potentially invalidated. +

+ +

+PATypeHolder is an extremely light-weight object that uses a lazy union-find +implementation to update pointers. For example the pointer from a Value to its +Type is maintained by PATypeHolder objects. +

+ +

+Some data structures need more to perform more complex updates when types get +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 + abstract types. Concrete types (those that do not include any opaque +objects) can never be refined. +

The +ValueSymbolTable class provides a symbol table that the Function and +Module classes use for naming value definitions. The symbol table +can provide a name for any Value. +The +TypeSymbolTable class is used by the Module class to store +names for types.

+ +

Note that the SymbolTable class should not be directly accessed +by most clients. It should only be used when iteration over the symbol table +names themselves are required, which is very special purpose. Note that not +all LLVM +Values have names, and those without names (i.e. they have +an empty name) do not exist in the symbol table. +

+ +

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.

+ +

#include "llvm/Type.h" +
doxygen info: Type Class

+ +

The Core LLVM classes are the primary means of representing the program +being inspected or transformed. The core LLVM classes are defined in +header files in the include/llvm/ directory, and implemented in +the lib/VMCore directory.

+ +

Type is a superclass of all type classes. Every Value has + a Type. Type cannot be instantiated directly but only + through its subclasses. Certain primitive types (VoidType, + LabelType, FloatType and DoubleType) have hidden + subclasses. They are hidden because they offer no useful functionality beyond + what the Type class offers except to distinguish themselves from + other subclasses of Type.

All other types are subclasses of DerivedType. Types can be + named, but this is not a requirement. There exists exactly + one instance of a given shape at any one time. This allows type equality to + be performed with address equality of the Type Instance. That is, given two + Type* values, the types are identical if the pointers are identical. +

+ +

bool isInteger() const: Returns true for any integer type.
bool isFloatingPoint(): Return true if this is one of the two + floating point types.
bool isAbstract(): Return true if the type is abstract (contains + an OpaqueType anywhere in its definition).
bool isSized(): Return true if the type has known size. Things + that don't have a size are abstract types, labels and void.

IntegerType

Subclass of DerivedType that represents integer types of any bit width. + Any bit width between IntegerType::MIN_INT_BITS (1) and + IntegerType::MAX_INT_BITS (~8 million) can be represented. +

static const IntegerType* get(unsigned NumBits): get an integer + type of a specific bit width.
unsigned getBitWidth() const: Get the bit width of an integer + type.

SequentialType

This is subclassed by ArrayType and PointerType +

const Type * getElementType() const: Returns the type of each + of the elements in the sequential type.

ArrayType

This is a subclass of SequentialType and defines the interface for array + types. +

unsigned getNumElements() const: Returns the number of + elements in the array.

PointerType

Subclass of SequentialType for pointer types.

VectorType

Subclass of SequentialType for vector types. A + vector type is similar to an ArrayType but is distinguished because it is + a first class type wherease ArrayType is not. Vector types are used for + vector operations and are usually small vectors of of an integer or floating + point type.

StructType

Subclass of DerivedTypes for struct types.

FunctionType

Subclass of DerivedTypes for function types. +

bool isVarArg() const: Returns true if its a vararg + function
const Type * getReturnType() const: Returns the + return type of the function.
const Type * getParamType (unsigned i): Returns + the type of the ith parameter.
const unsigned getNumParams() const: Returns the + number of formal parameters.

OpaqueType

Sublcass of DerivedType for abstract types. This class + defines no content and is used as a placeholder for some other type. Note + that OpaqueType is used (temporarily) during type resolution for forward + references of types. Once the referenced type is resolved, the OpaqueType + is replaced with the actual type. OpaqueType can also be used for data + abstraction. At link time opaque types can be resolved to actual types + of the same name.

+ +

#include "llvm/Module.h"
doxygen info: +Module Class

+ +

The Module class represents the top level structure present in LLVM +programs. An LLVM module is effectively either a translation unit of the +original program or a combination of several translation units merged by the +linker. The Module class keeps track of a list of Functions, a list of GlobalVariables, and a SymbolTable. Additionally, it contains a few +helpful member functions that try to make common operations easy.

+ +

Module::Module(std::string name = "")

+ +

Constructing a Module is easy. You can optionally +provide a name for it (probably based on the name of the translation unit).

+ +

Module::iterator - Typedef for function list iterator
+ Module::const_iterator - Typedef for const_iterator.
+ + begin(), end() + size(), empty() + +
These are forwarding methods that make it easy to access the contents of + a Module object's Function + list.
Module::FunctionListType &getFunctionList() + +
Returns the list of Functions. This is + necessary to use when you need to update the list or perform a complex + action that doesn't have a forwarding method.
+ +

+ +

Module::global_iterator - Typedef for global variable list iterator
+ + Module::const_global_iterator - Typedef for const_iterator.
+ + global_begin(), global_end() + global_size(), global_empty() + +
These are forwarding methods that make it easy to access the contents of + a Module object's GlobalVariable list.
Module::GlobalListType &getGlobalList() + +
Returns the list of GlobalVariables. This is necessary to + use when you need to update the list or perform a complex action that + doesn't have a forwarding method.
+ +

+ +

SymbolTable *getSymbolTable() + +
Return a reference to the SymbolTable + for this Module.
+ +

+ +

Function *getFunction(const std::string + &Name, const FunctionType *Ty) + +
Look up the specified function in the Module SymbolTable. If it does not exist, return + null.
Function *getOrInsertFunction(const + std::string &Name, const FunctionType *T) + +
Look up the specified function in the Module SymbolTable. If it does not exist, add an + external declaration for the function and return it.
std::string getTypeName(const Type *Ty) + +
If there is at least one entry in the SymbolTable for the specified Type, return it. Otherwise return the empty + string.
bool addTypeName(const std::string &Name, const Type *Ty) + +
Insert an entry in the SymbolTable + mapping Name to Ty. If there is already an entry for this + name, true is returned and the SymbolTable is not modified.

+ +

#include "llvm/Value.h" +
+doxygen info: Value Class

+ +

The Value class is the most important class in the LLVM Source +base. It represents a typed value that may be used (among other things) as an +operand to an instruction. There are many different types of Values, +such as Constants,Arguments. Even Instructions and Functions are Values.

+ +

A particular Value may be used many times in the LLVM representation +for a program. For example, an incoming argument to a function (represented +with an instance of the Argument class) is "used" by +every instruction in the function that references the argument. To keep track +of this relationship, the Value class keeps a list of all of the Users that is using it (the User class is a base class for all nodes in the LLVM +graph that can refer to Values). This use list is how LLVM represents +def-use information in the program, and is accessible through the use_* +methods, shown below.

+ +

Because LLVM is a typed representation, every LLVM Value is typed, +and this Type is available through the getType() +method. In addition, all LLVM values can be named. The "name" of the +Value is a symbolic string printed in the LLVM code:

+ +

+%foo = add i32 1, 2
+

+ +

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 +between them. For this purpose, use a std::map of pointers to the +Value itself instead.

+ +

One important aspect of LLVM is that there is no distinction between an SSA +variable and the operation that produces it. Because of this, any reference to +the value produced by an instruction (or the value available as an incoming +argument, for example) is represented as a direct pointer to the instance of +the class that +represents this value. Although this may take some getting used to, it +simplifies the representation and makes it easier to manipulate.

+ +

Value::use_iterator - Typedef for iterator over the +use-list
+ Value::use_const_iterator - Typedef for const_iterator over +the use-list
+ unsigned use_size() - Returns the number of users of the +value.
+ bool use_empty() - Returns true if there are no users.
+ use_iterator use_begin() - Get an iterator to the start of +the use-list.
+ use_iterator use_end() - Get an iterator to the end of the +use-list.
+ User *use_back() - Returns the last +element in the list. +
These methods are the interface to access the def-use +information in LLVM. As with all other iterators in LLVM, the naming +conventions follow the conventions defined by the STL.
+
Type *getType() const +
This method returns the Type of the Value.
+
bool hasName() const
+ std::string getName() const
+ void setName(const std::string &Name) +
This family of methods is used to access and assign a name to a Value, +be aware of the precaution above.
+
void replaceAllUsesWith(Value *V) + +
This method traverses the use list of a Value changing all Users of the current value to refer to + "V" instead. For example, if you detect that an instruction always + produces a constant value (for example through constant folding), you can + replace all uses of the instruction with the constant like this:
+ +
+
```
+Inst->replaceAllUsesWith(ConstVal);
+
```
+
+ +

+ +

+#include "llvm/User.h"
+doxygen info: User Class
+Superclass: Value

+ +

The User class is the common base class of all LLVM nodes that may +refer to Values. It exposes a list of "Operands" +that are all of the Values that the User is +referring to. The User class itself is a subclass of +Value.

+ +

The operands of a User point directly to the LLVM Value that it refers to. Because LLVM uses Static +Single Assignment (SSA) form, there can only be one definition referred to, +allowing this direct connection. This connection provides the use-def +information in LLVM.

+ +

The User class exposes the operand list in two ways: through +an index access interface and through an iterator based interface.

+ +

Value *getOperand(unsigned i)
+ unsigned getNumOperands() +
These two methods expose the operands of the User in a +convenient form for direct access.
User::op_iterator - Typedef for iterator over the operand +list
+ op_iterator op_begin() - Get an iterator to the start of +the operand list.
+ op_iterator op_end() - Get an iterator to the end of the +operand list. +
Together, these methods make up the iterator based interface to +the operands of a User.

+ +

#include "llvm/Instruction.h"
+doxygen info: Instruction Class
+Superclasses: User, Value

+ +

The Instruction class is the common base class for all LLVM +instructions. It provides only a few methods, but is a very commonly used +class. The primary data tracked by the Instruction class itself is the +opcode (instruction type) and the parent BasicBlock the Instruction is embedded +into. To represent a specific type of instruction, one of many subclasses of +Instruction are used.

+ +

Because the Instruction class subclasses the User class, its operands can be accessed in the same +way as for other Users (with the +getOperand()/getNumOperands() and +op_begin()/op_end() methods).

An important file for +the Instruction class is the llvm/Instruction.def file. This +file contains some meta-data about the various different types of instructions +in LLVM. It describes the enum values that are used as opcodes (for example +Instruction::Add and Instruction::ICmp), as well as the +concrete sub-classes of Instruction that implement the instruction (for +example BinaryOperator and CmpInst). Unfortunately, the use of macros in +this file confuses doxygen, so these enum values don't show up correctly in the +doxygen output.

+ +

BinaryOperator +
This subclasses represents all two operand instructions whose operands + must be the same type, except for the comparison instructions.
CastInst +
This subclass is the parent of the 12 casting instructions. It provides + common operations on cast instructions.
+
CmpInst +
This subclass respresents the two comparison instructions, + ICmpInst (integer opreands), and + FCmpInst (floating point operands).
+
TerminatorInst +
This subclass is the parent of all terminator instructions (those which + can terminate a block).
+

+ +

BasicBlock *getParent() +
Returns the BasicBlock that +this Instruction is embedded into.
bool mayWriteToMemory() +
Returns true if the instruction writes to memory, i.e. it is a + call,free,invoke, or store.
unsigned getOpcode() +
Returns the opcode for the Instruction.
Instruction *clone() const +
Returns another instance of the specified instruction, identical +in all ways to the original except that the instruction has no parent +(ie it's not embedded into a BasicBlock), +and it has no name

+ +

Constant represents a base class for different types of constants. It +is subclassed by ConstantInt, ConstantArray, etc. for representing +the various types of Constants. GlobalValue is also +a subclass, which represents the address of a global variable or function. +

+ +

ConstantInt : This subclass of Constant represents an integer constant of + any width. +
- const APInt& getValue() const: Returns the underlying + value of this constant, an APInt value.
- int64_t getSExtValue() const: Converts the underlying APInt + value to an int64_t via sign extension. If the value (not the bit width) + of the APInt is too large to fit in an int64_t, an assertion will result. + For this reason, use of this method is discouraged.
- uint64_t getZExtValue() const: Converts the underlying APInt + value to a uint64_t via zero extension. IF the value (not the bit width) + of the APInt is too large to fit in a uint64_t, an assertion will result. + For this reason, use of this method is discouraged.
- static ConstantInt* get(const APInt& Val): Returns the + ConstantInt object that represents the value provided by Val. + The type is implied as the IntegerType that corresponds to the bit width + of Val.
- static ConstantInt* get(const Type *Ty, uint64_t Val): + Returns the ConstantInt object that represents the value provided by + Val for integer type Ty.
+
ConstantFP : This class represents a floating point constant. +
- double getValue() const: Returns the underlying value of + this constant.
+
ConstantArray : This represents a constant array. +
- const std::vector<Use> &getValues() const: Returns + a vector of component constants that makeup this array.
+
ConstantStruct : This represents a constant struct. +
- const std::vector<Use> &getValues() const: Returns + a vector of component constants that makeup this array.
+
GlobalValue : This represents either a global variable or a function. In + either case, the value is a constant fixed address (after linking). +

+ +

#include "llvm/GlobalValue.h"
+doxygen info: GlobalValue +Class
+Superclasses: Constant, +User, Value

+ +

Global values (GlobalVariables or Functions) are the only LLVM values that are +visible in the bodies of all Functions. +Because they are visible at global scope, they are also subject to linking with +other globals defined in different translation units. To control the linking +process, GlobalValues know their linkage rules. Specifically, +GlobalValues know whether they have internal or external linkage, as +defined by the LinkageTypes enumeration.

+ +

If a GlobalValue has internal linkage (equivalent to being +static in C), it is not visible to code outside the current translation +unit, and does not participate in linking. If it has external linkage, it is +visible to external code, and does participate in linking. In addition to +linkage information, GlobalValues keep track of which Module they are currently part of.

+ +

Because GlobalValues are memory objects, they are always referred to +by their address. As such, the Type of a +global is always a pointer to its contents. It is important to remember this +when using the GetElementPtrInst instruction because this pointer must +be dereferenced first. For example, if you have a GlobalVariable (a +subclass of GlobalValue) that is an array of 24 ints, type [24 x +i32], then the GlobalVariable is a pointer to that array. Although +the address of the first element of this array and the value of the +GlobalVariable are the same, they have different types. The +GlobalVariable's type is [24 x i32]. The first element's type +is i32. Because of this, accessing a global value requires you to +dereference the pointer with GetElementPtrInst first, then its elements +can be accessed. This is explained in the LLVM +Language Reference Manual.

+ +

bool hasInternalLinkage() const
+ bool hasExternalLinkage() const
+ void setInternalLinkage(bool HasInternalLinkage) +
These methods manipulate the linkage characteristics of the GlobalValue.
+

+
Module *getParent() +
This returns the Module that the +GlobalValue is currently embedded into.

+ +

#include "llvm/Function.h"
doxygen +info: Function Class
+Superclasses: GlobalValue, +Constant, +User, +Value

+ +

The Function class represents a single procedure in LLVM. It is +actually one of the more complex classes in the LLVM heirarchy because it must +keep track of a large amount of data. The Function class keeps track +of a list of BasicBlocks, a list of formal +Arguments, and a +SymbolTable.

+ +

The list of BasicBlocks is the most +commonly used part of Function objects. The list imposes an implicit +ordering of the blocks in the function, which indicate how the code will be +layed out by the backend. Additionally, the first BasicBlock is the implicit entry node for the +Function. It is not legal in LLVM to explicitly branch to this initial +block. There are no implicit exit nodes, and in fact there may be multiple exit +nodes from a single Function. If the BasicBlock list is empty, this indicates that +the Function is actually a function declaration: the actual body of the +function hasn't been linked in yet.

+ +

In addition to a list of BasicBlocks, the +Function class also keeps track of the list of formal Arguments that the function receives. This +container manages the lifetime of the Argument +nodes, just like the BasicBlock list does for +the BasicBlocks.

+ +

The SymbolTable is a very rarely used +LLVM feature that is only used when you have to look up a value by name. Aside +from that, the SymbolTable is used +internally to make sure that there are not conflicts between the names of Instructions, BasicBlocks, or Arguments in the function body.

+ +

Note that Function is a GlobalValue +and therefore also a Constant. The value of the function +is its address (after linking) which is guaranteed to be constant.

+ +

Function(const FunctionType + *Ty, LinkageTypes Linkage, const std::string &N = "", Module* Parent = 0) + +
Constructor used when you need to create new Functions to add + the the program. The constructor must specify the type of the function to + 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 + 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 + functions.
bool isExternal() + +
Return whether or not the Function has a body defined. If the + function is "external", it does not have a body, and thus must be resolved + by linking with a function defined in a different translation unit.
Function::iterator - Typedef for basic block list iterator
+ Function::const_iterator - Typedef for const_iterator.
+ + begin(), end() + size(), empty() + +
These are forwarding methods that make it easy to access the contents of + a Function object's BasicBlock + list.
Function::BasicBlockListType &getBasicBlockList() + +
Returns the list of BasicBlocks. This + is necessary to use when you need to update the list or perform a complex + action that doesn't have a forwarding method.
Function::arg_iterator - Typedef for the argument list +iterator
+ Function::const_arg_iterator - Typedef for const_iterator.
+ + arg_begin(), arg_end() + arg_size(), arg_empty() + +
These are forwarding methods that make it easy to access the contents of + a Function object's Argument + list.
Function::ArgumentListType &getArgumentList() + +
Returns the list of Arguments. This is + necessary to use when you need to update the list or perform a complex + action that doesn't have a forwarding method.
BasicBlock &getEntryBlock() + +
Returns the entry BasicBlock for the + function. Because the entry block for the function is always the first + block, this returns the first block of the Function.
Type *getReturnType()
+ FunctionType *getFunctionType() + +
This traverses the Type of the + Function and returns the return type of the function, or the FunctionType of the actual + function.
SymbolTable *getSymbolTable() + +
Return a pointer to the SymbolTable + for this Function.

+ +

#include "llvm/GlobalVariable.h" +
+doxygen info: GlobalVariable + Class
+Superclasses: GlobalValue, +Constant, +User, +Value

+ +

Global variables are represented with the (suprise suprise) +GlobalVariable class. Like functions, GlobalVariables are also +subclasses of GlobalValue, and as such are +always referenced by their address (global values must live in memory, so their +"name" refers to their constant address). See +GlobalValue for more on this. Global +variables may have an initial value (which must be a +Constant), and if they have an initializer, +they may be marked as "constant" themselves (indicating that their contents +never change at runtime).

+ +

GlobalVariable(const Type *Ty, bool + isConstant, LinkageTypes& Linkage, Constant + *Initializer = 0, const std::string &Name = "", Module* Parent = 0) + +
Create a new global variable of the specified type. If + isConstant is true then the global variable will be marked as + unchanging for the program. The Linkage parameter specifies the type of + linkage (internal, external, weak, linkonce, appending) for the variable. If + the linkage is InternalLinkage, WeakLinkage, or LinkOnceLinkage, then + the resultant global variable will have internal linkage. AppendingLinkage + concatenates together all instances (in different translation units) of the + variable into a single variable but is only applicable to arrays. See + the LLVM Language Reference for + further details on linkage types. Optionally an initializer, a name, and the + module to put the variable into may be specified for the global variable as + well.
bool isConstant() const + +
Returns true if this is a global variable that is known not to + be modified at runtime.
bool hasInitializer() + +
Returns true if this GlobalVariable has an intializer.
Constant *getInitializer() + +
Returns the intial value for a GlobalVariable. It is not legal + to call this method if there is no initializer.

+ +

#include "llvm/BasicBlock.h"
+doxygen info: BasicBlock +Class
+Superclass: Value

+ +

This class represents a single entry multiple exit section of the code, +commonly known as a basic block by the compiler community. The +BasicBlock class maintains a list of Instructions, which form the body of the block. +Matching the language definition, the last element of this list of instructions +is always a terminator instruction (a subclass of the TerminatorInst class).

+ +

In addition to tracking the list of instructions that make up the block, the +BasicBlock class also keeps track of the Function that it is embedded into.

+ +

Note that BasicBlocks themselves are Values, because they are referenced by instructions +like branches and can go in the switch tables. BasicBlocks have type +label.

+ +

BasicBlock(const std::string &Name = "", Function *Parent = 0) + +
The BasicBlock constructor is used to create new basic blocks for +insertion into a function. The constructor optionally takes a name for the new +block, and a Function to insert it into. If +the Parent parameter is specified, the new BasicBlock is +automatically inserted at the end of the specified Function, if not specified, the BasicBlock must be +manually inserted into the Function.
BasicBlock::iterator - Typedef for instruction list iterator
+BasicBlock::const_iterator - Typedef for const_iterator.
+begin(), end(), front(), back(), +size(), empty() +STL-style functions for accessing the instruction list. + +
These methods and typedefs are forwarding functions that have the same +semantics as the standard library methods of the same names. These methods +expose the underlying instruction list of a basic block in a way that is easy to +manipulate. To get the full complement of container operations (including +operations to update the list), you must use the getInstList() +method.
BasicBlock::InstListType &getInstList() + +
This method is used to get access to the underlying container that actually +holds the Instructions. This method must be used when there isn't a forwarding +function in the BasicBlock class for the operation that you would like +to perform. Because there are no forwarding functions for "updating" +operations, you need to use this if you want to update the contents of a +BasicBlock.
Function *getParent() + +
Returns a pointer to Function the block is +embedded into, or a null pointer if it is homeless.
TerminatorInst *getTerminator() + +
Returns a pointer to the terminator instruction that appears at the end of +the BasicBlock. If there is no terminator instruction, or if the last +instruction in the block is not a terminator, then a null pointer is +returned.

+ +

Deleting Instructions

Deleting `Instruction`s