</head>
<body>
-<div class="doc_title">
+<h1>
LLVM Programmer's Manual
-</div>
+</h1>
<ol>
<li><a href="#introduction">Introduction</a></li>
<ul>
<li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
<ul>
+ <li><a href="#dss_arrayref">llvm/ADT/ArrayRef.h</a></li>
<li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li>
<li><a href="#dss_heaparrays">Heap Allocated Arrays</a></li>
+ <li><a href="#dss_tinyptrvector">"llvm/ADT/TinyPtrVector.h"</a></li>
<li><a href="#dss_smallvector">"llvm/ADT/SmallVector.h"</a></li>
<li><a href="#dss_vector"><vector></a></li>
<li><a href="#dss_deque"><deque></a></li>
<li><a href="#dss_list"><list></a></li>
<li><a href="#dss_ilist">llvm/ADT/ilist.h</a></li>
+ <li><a href="#dss_packedvector">llvm/ADT/PackedVector.h</a></li>
<li><a href="#dss_other">Other Sequential Container Options</a></li>
</ul></li>
+ <li><a href="#ds_string">String-like containers</a>
+ <ul>
+ <li><a href="#dss_stringref">llvm/ADT/StringRef.h</a></li>
+ <li><a href="#dss_twine">llvm/ADT/Twine.h</a></li>
+ <li><a href="#dss_smallstring">llvm/ADT/SmallString.h</a></li>
+ <li><a href="#dss_stdstring">std::string</a></li>
+ </ul></li>
<li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
<ul>
<li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li>
<li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li>
<li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li>
<li><a href="#dss_valuemap">"llvm/ADT/ValueMap.h"</a></li>
+ <li><a href="#dss_intervalmap">"llvm/ADT/IntervalMap.h"</a></li>
<li><a href="#dss_map"><map></a></li>
+ <li><a href="#dss_inteqclasses">"llvm/ADT/IntEqClasses.h"</a></li>
<li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
</ul></li>
- <li><a href="#ds_string">String-like containers</a>
- <!--<ul>
- todo
- </ul>--></li>
<li><a href="#ds_bit">BitVector-like containers</a>
<ul>
<li><a href="#dss_bitvector">A dense bitvector</a></li>
<li><a href="#advanced">Advanced Topics</a>
<ul>
- <li><a href="#TypeResolve">LLVM Type Resolution</a>
- <ul>
- <li><a href="#BuildRecType">Basic Recursive Type Construction</a></li>
- <li><a href="#refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a></li>
- <li><a href="#PATypeHolder">The PATypeHolder Class</a></li>
- <li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li>
- </ul></li>
- <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> and <tt>TypeSymbolTable</tt> classes</a></li>
+ <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> class</a></li>
<li><a href="#UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a></li>
</ul></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="introduction">Introduction </a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>This document is meant to highlight some of the important classes and
interfaces available in the LLVM source-base. This manual is not
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="general">General Information</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>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.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="stl">The C++ Standard Template Library</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>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
<ol>
-<li><a href="http://www.dinkumware.com/refxcpp.html">Dinkumware C++ Library
-reference</a> - an excellent reference for the STL and other parts of the
-standard C++ library.</li>
+<li><a href="http://www.dinkumware.com/manuals/#Standard C++ Library">Dinkumware
+C++ Library reference</a> - an excellent reference for the STL and other parts
+of the standard C++ library.</li>
<li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an
O'Reilly book in the making. It has a decent Standard Library
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="stl">Other useful references</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<ol>
-<li><a href="http://www.psc.edu/%7Esemke/cvs_branches.html">CVS
-Branch and Tag Primer</a></li>
<li><a href="http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html">Using
static and shared libraries across platforms</a></li>
</ol>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="apis">Important and useful LLVM APIs</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Here we highlight some LLVM APIs that are generally useful and good to
know about when writing transformations.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="isa">The <tt>isa<></tt>, <tt>cast<></tt> and
<tt>dyn_cast<></tt> templates</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>The LLVM source-base makes extensive use of a custom form of RTTI.
These templates have many similarities to the C++ <tt>dynamic_cast<></tt>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="string_apis">Passing strings (the <tt>StringRef</tt>
and <tt>Twine</tt> classes)</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Although LLVM generally does not do much string manipulation, we do have
several important APIs which take strings. Two important examples are the
may have embedded null characters. Therefore, they cannot simply take
a <tt>const char *</tt>, and taking a <tt>const std::string&</tt> requires
clients to perform a heap allocation which is usually unnecessary. Instead,
-many LLVM APIs use a <tt>const StringRef&</tt> or a <tt>const
-Twine&</tt> for passing strings efficiently.</p>
-
-</div>
+many LLVM APIs use a <tt>StringRef</tt> or a <tt>const Twine&</tt> for
+passing strings efficiently.</p>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="StringRef">The <tt>StringRef</tt> class</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>The <tt>StringRef</tt> data type represents a reference to a constant string
(a character array and a length) and supports the common operations available
an <tt>std::string</tt>, or explicitly with a character pointer and length.
For example, the <tt>StringRef</tt> find function is declared as:</p>
-<div class="doc_code">
- iterator find(const StringRef &Key);
-</div>
+<pre class="doc_code">
+ iterator find(StringRef Key);
+</pre>
<p>and clients can call it using any one of:</p>
-<div class="doc_code">
-<pre>
+<pre class="doc_code">
Map.find("foo"); <i>// Lookup "foo"</i>
Map.find(std::string("bar")); <i>// Lookup "bar"</i>
Map.find(StringRef("\0baz", 4)); <i>// Lookup "\0baz"</i>
</pre>
-</div>
<p>Similarly, APIs which need to return a string may return a <tt>StringRef</tt>
instance, which can be used directly or converted to an <tt>std::string</tt>
<p>You should rarely use the <tt>StringRef</tt> class directly, because it contains
pointers to external memory it is not generally safe to store an instance of the
-class (unless you know that the external storage will not be freed).</p>
+class (unless you know that the external storage will not be freed). StringRef is
+small and pervasive enough in LLVM that it should always be passed by value.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="Twine">The <tt>Twine</tt> class</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>The <tt>Twine</tt> class is an efficient way for APIs to accept concatenated
strings. For example, a common LLVM paradigm is to name one instruction based on
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>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
program hasn't been started yet, you can always just run it with
<tt>-debug</tt>.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and
the <tt>-debug-only</tt> option</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Sometimes you may find yourself in a situation where enabling <tt>-debug</tt>
just turns on <b>too much</b> information (such as when working on the code
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt>
option</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>The "<tt><a
href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="ViewGraph">Viewing graphs while debugging code</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Several of the important data structures in LLVM are graphs: for example
CFGs made out of LLVM <a href="#BasicBlock">BasicBlock</a>s, CFGs made out of
Attributes</a>.) If you want to restart and clear all the current graph
attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p>
+<p>Note that graph visualization features are compiled out of Release builds
+to reduce file size. This means that you need a Debug+Asserts or
+Release+Asserts build to use these features.</p>
+
+</div>
+
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="datastructure">Picking the Right Data Structure for a Task</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>LLVM has a plethora of data structures in the <tt>llvm/ADT/</tt> directory,
and we commonly use STL data structures. This section describes the trade-offs
cost of adding the elements to the container. </p>
</div>
-
+
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
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.
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_arrayref">llvm/ADT/ArrayRef.h</a>
+</h4>
+
+<div>
+<p>The llvm::ArrayRef class is the preferred class to use in an interface that
+ accepts a sequential list of elements in memory and just reads from them. By
+ taking an ArrayRef, the API can be passed a fixed size array, an std::vector,
+ an llvm::SmallVector and anything else that is contiguous in memory.
+</p>
</div>
+
+
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_fixedarrays">Fixed Size Arrays</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_heaparrays">Heap Allocated Arrays</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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,
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a>
+<h4>
+ <a name="dss_tinyptrvector">"llvm/ADT/TinyPtrVector.h"</a>
+</h4>
+
+
+<div>
+<p><tt>TinyPtrVector<Type></tt> is a highly specialized collection class
+that is optimized to avoid allocation in the case when a vector has zero or one
+elements. It has two major restrictions: 1) it can only hold values of pointer
+type, and 2) it cannot hold a null pointer.</p>
+
+<p>Since this container is highly specialized, it is rarely used.</p>
+
</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>SmallVector<Type, N></tt> is a simple class that looks and smells
just like <tt>vector<Type></tt>:
it supports efficient iteration, lays out elements in memory order (so you can
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_vector"><vector></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_deque"><deque></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_list"><list></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_ilist">llvm/ADT/ilist.h</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>ilist<T></tt> 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.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_ilist_traits">ilist_traits</a>
+<h4>
+ <a name="dss_packedvector">llvm/ADT/PackedVector.h</a>
+</h4>
+
+<div>
+<p>
+Useful for storing a vector of values using only a few number of bits for each
+value. Apart from the standard operations of a vector-like container, it can
+also perform an 'or' set operation.
+</p>
+
+<p>For example:</p>
+
+<div class="doc_code">
+<pre>
+enum State {
+ None = 0x0,
+ FirstCondition = 0x1,
+ SecondCondition = 0x2,
+ Both = 0x3
+};
+
+State get() {
+ PackedVector<State, 2> Vec1;
+ Vec1.push_back(FirstCondition);
+
+ PackedVector<State, 2> Vec2;
+ Vec2.push_back(SecondCondition);
+
+ Vec1 |= Vec2;
+ return Vec1[0]; // returns 'Both'.
+}
+</pre>
</div>
-<div class="doc_text">
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_ilist_traits">ilist_traits</a>
+</h4>
+
+<div>
<p><tt>ilist_traits<T></tt> is <tt>ilist<T></tt>'s customization
mechanism. <tt>iplist<T></tt> (and consequently <tt>ilist<T></tt>)
publicly derive from this traits class.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_iplist">iplist</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>iplist<T></tt> is <tt>ilist<T></tt>'s base and as such
supports a slightly narrower interface. Notably, inserters from
<tt>T&</tt> are absent.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_ilist_node">llvm/ADT/ilist_node.h</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>ilist_node<T></tt> implements a the forward and backward links
that are expected by the <tt>ilist<T></tt> (and analogous containers)
in the default manner.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_ilist_sentinel">Sentinels</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>ilist</tt>s have another specialty that must be considered. To be a good
citizen in the C++ ecosystem, it needs to support the standard container
operations, such as <tt>begin</tt> and <tt>end</tt> iterators, etc. Also, the
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_other">Other Sequential Container options</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Other STL containers are available, such as std::string.</p>
<p>There are also various STL adapter classes such as std::queue,
underlying container but don't affect the cost of the container itself.</p>
</div>
+</div>
+
+<!-- ======================================================================= -->
+<h3>
+ <a name="ds_string">String-like containers</a>
+</h3>
+
+<div>
+
+<p>
+There are a variety of ways to pass around and use strings in C and C++, and
+LLVM adds a few new options to choose from. Pick the first option on this list
+that will do what you need, they are ordered according to their relative cost.
+</p>
+<p>
+Note that is is generally preferred to <em>not</em> pass strings around as
+"<tt>const char*</tt>"'s. These have a number of problems, including the fact
+that they cannot represent embedded nul ("\0") characters, and do not have a
+length available efficiently. The general replacement for '<tt>const
+char*</tt>' is StringRef.
+</p>
+
+<p>For more information on choosing string containers for APIs, please see
+<a href="#string_apis">Passing strings</a>.</p>
+
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_stringref">llvm/ADT/StringRef.h</a>
+</h4>
+
+<div>
+<p>
+The StringRef class is a simple value class that contains a pointer to a
+character and a length, and is quite related to the <a
+href="#dss_arrayref">ArrayRef</a> class (but specialized for arrays of
+characters). Because StringRef carries a length with it, it safely handles
+strings with embedded nul characters in it, getting the length does not require
+a strlen call, and it even has very convenient APIs for slicing and dicing the
+character range that it represents.
+</p>
+
+<p>
+StringRef is ideal for passing simple strings around that are known to be live,
+either because they are C string literals, std::string, a C array, or a
+SmallVector. Each of these cases has an efficient implicit conversion to
+StringRef, which doesn't result in a dynamic strlen being executed.
+</p>
+
+<p>StringRef has a few major limitations which make more powerful string
+containers useful:</p>
+
+<ol>
+<li>You cannot directly convert a StringRef to a 'const char*' because there is
+no way to add a trailing nul (unlike the .c_str() method on various stronger
+classes).</li>
+
+
+<li>StringRef doesn't own or keep alive the underlying string bytes.
+As such it can easily lead to dangling pointers, and is not suitable for
+embedding in datastructures in most cases (instead, use an std::string or
+something like that).</li>
+
+<li>For the same reason, StringRef cannot be used as the return value of a
+method if the method "computes" the result string. Instead, use
+std::string.</li>
+
+<li>StringRef's do not allow you to mutate the pointed-to string bytes and it
+doesn't allow you to insert or remove bytes from the range. For editing
+operations like this, it interoperates with the <a
+href="#dss_twine">Twine</a> class.</li>
+</ol>
+
+<p>Because of its strengths and limitations, it is very common for a function to
+take a StringRef and for a method on an object to return a StringRef that
+points into some string that it owns.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_twine">llvm/ADT/Twine.h</a>
+</h4>
+
+<div>
+ <p>
+ The Twine class is used as an intermediary datatype for APIs that want to take
+ a string that can be constructed inline with a series of concatenations.
+ Twine works by forming recursive instances of the Twine datatype (a simple
+ value object) on the stack as temporary objects, linking them together into a
+ tree which is then linearized when the Twine is consumed. Twine is only safe
+ to use as the argument to a function, and should always be a const reference,
+ e.g.:
+ </p>
+
+ <pre>
+ void foo(const Twine &T);
+ ...
+ StringRef X = ...
+ unsigned i = ...
+ foo(X + "." + Twine(i));
+ </pre>
+
+ <p>This example forms a string like "blarg.42" by concatenating the values
+ together, and does not form intermediate strings containing "blarg" or
+ "blarg.".
+ </p>
+
+ <p>Because Twine is constructed with temporary objects on the stack, and
+ because these instances are destroyed at the end of the current statement,
+ it is an inherently dangerous API. For example, this simple variant contains
+ undefined behavior and will probably crash:</p>
+
+ <pre>
+ void foo(const Twine &T);
+ ...
+ StringRef X = ...
+ unsigned i = ...
+ const Twine &Tmp = X + "." + Twine(i);
+ foo(Tmp);
+ </pre>
+
+ <p>... because the temporaries are destroyed before the call. That said,
+ Twine's are much more efficient than intermediate std::string temporaries, and
+ they work really well with StringRef. Just be aware of their limitations.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_smallstring">llvm/ADT/SmallString.h</a>
+</h4>
+
+<div>
+
+<p>SmallString is a subclass of <a href="#dss_smallvector">SmallVector</a> that
+adds some convenience APIs like += that takes StringRef's. SmallString avoids
+allocating memory in the case when the preallocated space is enough to hold its
+data, and it calls back to general heap allocation when required. Since it owns
+its data, it is very safe to use and supports full mutation of the string.</p>
+
+<p>Like SmallVector's, the big downside to SmallString is their sizeof. While
+they are optimized for small strings, they themselves are not particularly
+small. This means that they work great for temporary scratch buffers on the
+stack, but should not generally be put into the heap: it is very rare to
+see a SmallString as the member of a frequently-allocated heap data structure
+or returned by-value.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_stdstring">std::string</a>
+</h4>
+
+<div>
+
+ <p>The standard C++ std::string class is a very general class that (like
+ SmallString) owns its underlying data. sizeof(std::string) is very reasonable
+ so it can be embedded into heap data structures and returned by-value.
+ On the other hand, std::string is highly inefficient for inline editing (e.g.
+ concatenating a bunch of stuff together) and because it is provided by the
+ standard library, its performance characteristics depend a lot of the host
+ standard library (e.g. libc++ and MSVC provide a highly optimized string
+ class, GCC contains a really slow implementation).
+ </p>
+
+ <p>The major disadvantage of std::string is that almost every operation that
+ makes them larger can allocate memory, which is slow. As such, it is better
+ to use SmallVector or Twine as a scratch buffer, but then use std::string to
+ persist the result.</p>
+
+</div>
+
+<!-- end of strings -->
+</div>
+
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>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.</p>
-</div>
-
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_sortedvectorset">A sorted 'vector'</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_smallset">"llvm/ADT/SmallSet.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>If you have a set-like data structure that is usually small and whose elements
are reasonably small, a <tt>SmallSet<Type, N></tt> is a good choice. This set
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
-<p>SmallPtrSet has all the advantages of SmallSet (and a SmallSet of pointers is
-transparently implemented with a SmallPtrSet), but also supports iterators. If
+<p>SmallPtrSet has all the advantages of <tt>SmallSet</tt> (and a <tt>SmallSet</tt> of pointers is
+transparently implemented with a <tt>SmallPtrSet</tt>), 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.</p>
-<p>Note that, unlike std::set, the iterators of SmallPtrSet are invalidated
+<p>Note that, unlike <tt>std::set</tt>, the iterators of <tt>SmallPtrSet</tt> are invalidated
whenever an insertion occurs. Also, the values visited by the iterators are not
visited in sorted order.</p>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_denseset">"llvm/ADT/DenseSet.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
DenseSet is a simple quadratically probed hash table. It excels at supporting
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
FoldingSet is an aggregate class that is really good at uniquing
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_set"><set></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><tt>std::set</tt> is a reasonable all-around set class, which is decent at
many things but great at nothing. std::set allocates memory for each element
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_setvector">"llvm/ADT/SetVector.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>LLVM's SetVector<Type> is an adapter class that combines your choice of
a set-like container along with a <a href="#ds_sequential">Sequential
Container</a>. The important property
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_uniquevector">"llvm/ADT/UniqueVector.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_otherset">Other Set-Like Container Options</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
The STL provides several other options, such as std::multiset and the various
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
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. :)
-</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_sortedvectormap">A sorted 'vector'</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
If your usage pattern follows a strict insert-then-query approach, you can
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_stringmap">"llvm/ADT/StringMap.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
Strings are commonly used as keys in maps, and they are difficult to support
<p>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
+recomputed when looking 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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_indexedmap">"llvm/ADT/IndexedMap.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_densemap">"llvm/ADT/DenseMap.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
DenseMap is a simple quadratically probed hash table. It excels at supporting
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_valuemap">"llvm/ADT/ValueMap.h"</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
ValueMap is a wrapper around a <a href="#dss_densemap">DenseMap</a> mapping
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_map"><map></a>
+<h4>
+ <a name="dss_intervalmap">"llvm/ADT/IntervalMap.h"</a>
+</h4>
+
+<div>
+
+<p> IntervalMap is a compact map for small keys and values. It maps key
+intervals instead of single keys, and it will automatically coalesce adjacent
+intervals. When then map only contains a few intervals, they are stored in the
+map object itself to avoid allocations.</p>
+
+<p> The IntervalMap iterators are quite big, so they should not be passed around
+as STL iterators. The heavyweight iterators allow a smaller data structure.</p>
+
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_map"><map></a>
+</h4>
+
+<div>
<p>
std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_othermap">Other Map-Like Container Options</a>
+<h4>
+ <a name="dss_inteqclasses">"llvm/ADT/IntEqClasses.h"</a>
+</h4>
+
+<div>
+
+<p>IntEqClasses provides a compact representation of equivalence classes of
+small integers. Initially, each integer in the range 0..n-1 has its own
+equivalence class. Classes can be joined by passing two class representatives to
+the join(a, b) method. Two integers are in the same class when findLeader()
+returns the same representative.</p>
+
+<p>Once all equivalence classes are formed, the map can be compressed so each
+integer 0..n-1 maps to an equivalence class number in the range 0..m-1, where m
+is the total number of equivalence classes. The map must be uncompressed before
+it can be edited again.</p>
+
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_othermap">Other Map-Like Container Options</a>
+</h4>
+
+<div>
<p>
The STL provides several other options, such as std::multimap and the various
</div>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="ds_string">String-like containers</a>
-</div>
-
-<div class="doc_text">
-
-<p>
-TODO: const char* vs stringref vs smallstring vs std::string. Describe twine,
-xref to #string_apis.
-</p>
-
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="ds_bit">Bit storage containers (BitVector, SparseBitVector)</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Unlike the other containers, there are only two bit storage containers, and
choosing when to use each is relatively straightforward.</p>
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.</p>
-</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_bitvector">BitVector</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p> The BitVector container provides a dynamic 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
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_smallbitvector">SmallBitVector</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p> The SmallBitVector container provides the same interface as BitVector, but
it is optimized for the case where only a small number of bits, less than
25 or so, are needed. It also transparently supports larger bit counts, but
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="dss_sparsebitvector">SparseBitVector</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p> 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,
</p>
</div>
+</div>
+
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="common">Helpful Hints for Common Operations</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>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
<a href="#coreclasses">Core LLVM Class Hierarchy Reference</a> contains details
and descriptions of the main classes that you should know about.</p>
-</div>
-
<!-- NOTE: this section should be heavy on example code -->
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="inspection">Basic Inspection and Traversal Routines</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>The LLVM compiler infrastructure have many different data structures that may
be traversed. Following the example of the C++ standard template library, the
examples of the data structures that need to be traversed. Other data
structures are traversed in very similar ways.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_function">Iterating over the </a><a
href="#BasicBlock"><tt>BasicBlock</tt></a>s in a <a
href="#Function"><tt>Function</tt></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>It's quite common to have a <tt>Function</tt> instance that you'd like to
transform in some way; in particular, you'd like to manipulate its
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_basicblock">Iterating over the </a><a
href="#Instruction"><tt>Instruction</tt></a>s in a <a
href="#BasicBlock"><tt>BasicBlock</tt></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Just like when dealing with <tt>BasicBlock</tt>s in <tt>Function</tt>s, it's
easy to iterate over the individual instructions that make up
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_institer">Iterating over the </a><a
href="#Instruction"><tt>Instruction</tt></a>s in a <a
href="#Function"><tt>Function</tt></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>If you're finding that you commonly iterate over a <tt>Function</tt>'s
<tt>BasicBlock</tt>s and then that <tt>BasicBlock</tt>'s <tt>Instruction</tt>s,
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_convert">Turning an iterator into a class pointer (and
vice-versa)</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</pre>
</div>
+<p>Unfortunately, these implicit conversions come at a cost; they prevent
+these iterators from conforming to standard iterator conventions, and thus
+from being usable with standard algorithms and containers. For example, they
+prevent the following code, where <tt>B</tt> is a <tt>BasicBlock</tt>,
+from compiling:</p>
+
+<div class="doc_code">
+<pre>
+ llvm::SmallVector<llvm::Instruction *, 16>(B->begin(), B->end());
+</pre>
+</div>
+
+<p>Because of this, these implicit conversions may be removed some day,
+and <tt>operator*</tt> changed to return a pointer instead of a reference.</p>
+
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_complex">Finding call sites: a slightly more complex
example</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Say that you're writing a FunctionPass and would like to count all the
locations in the entire module (that is, across every <tt>Function</tt>) where a
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="calls_and_invokes">Treating calls and invokes the same way</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_chains">Iterating over def-use & use-def chains</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Frequently, we might have an instance of the <a
href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to
</pre>
</div>
+<p>Note that dereferencing a <tt>Value::use_iterator</tt> is not a very cheap
+operation. Instead of performing <tt>*i</tt> above several times, consider
+doing it only once in the loop body and reusing its result.</p>
+
<p>Alternatively, it's common to have an instance of the <a
href="/doxygen/classllvm_1_1User.html">User Class</a> and need to know what
<tt>Value</tt>s are used by it. The list of all <tt>Value</tt>s used by a
</pre>
</div>
-<!--
- def-use chains ("finding all users of"): Value::use_begin/use_end
- use-def chains ("finding all values used"): User::op_begin/op_end [op=operand]
--->
+<p>Declaring objects as <tt>const</tt> is an important tool of enforcing
+mutation free algorithms (such as analyses, etc.). For this purpose above
+iterators come in constant flavors as <tt>Value::const_use_iterator</tt>
+and <tt>Value::const_op_iterator</tt>. They automatically arise when
+calling <tt>use/op_begin()</tt> on <tt>const Value*</tt>s or
+<tt>const User*</tt>s respectively. Upon dereferencing, they return
+<tt>const Use*</tt>s. Otherwise the above patterns remain unchanged.</p>
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="iterate_preds">Iterating over predecessors &
successors of blocks</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Iterating over the predecessors and successors of a block is quite easy
with the routines defined in <tt>"llvm/Support/CFG.h"</tt>. Just use code like
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="simplechanges">Making simple changes</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>There are some primitive transformation operations present in the LLVM
infrastructure that are worth knowing about. When performing
blocks. This section describes some of the common methods for doing so
and gives example code.</p>
-</div>
-
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="schanges_creating">Creating and inserting new
<tt>Instruction</tt>s</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><i>Instantiating Instructions</i></p>
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>Deleting an instruction from an existing sequence of instructions that form a
-<a href="#BasicBlock"><tt>BasicBlock</tt></a> 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:</p>
+<a href="#BasicBlock"><tt>BasicBlock</tt></a> is very straight-forward: just
+call the instruction's eraseFromParent() method. For example:</p>
<div class="doc_code">
<pre>
</pre>
</div>
+<p>This unlinks the instruction from its containing basic block and deletes
+it. If you'd just like to unlink the instruction from its containing basic
+block but not delete it, you can use the <tt>removeFromParent()</tt> method.</p>
+
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another
<tt>Value</tt></a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p><i>Replacing individual instructions</i></p>
permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt>
and <tt>ReplaceInstWithInst</tt>.</p>
-<h4><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h4>
+<h5><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h5>
<ul>
<li><tt>ReplaceInstWithValue</tt>
</div>
<!--_______________________________________________________________________-->
-<div class="doc_subsubsection">
+<h4>
<a name="schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>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
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="create_types">How to Create Types</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>In generating IR, you may need some complex types. If you know these types
statically, you can use <tt>TypeBuilder<...>::get()</tt>, defined
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="threading">Threads and LLVM</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
This section describes the interaction of the LLVM APIs with multithreading,
both on the part of client applications, and in the JIT, in the hosted
using the resultant compiler to build a copy of LLVM with multithreading
support.
</p>
-</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="startmultithreaded">Entering and Exiting Multithreaded Mode</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
In order to properly protect its internal data structures while avoiding
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="shutdown">Ending Execution with <tt>llvm_shutdown()</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
When you are done using the LLVM APIs, you should call <tt>llvm_shutdown()</tt>
to deallocate memory used for internal structures. This will also invoke
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="managedstatic">Lazy Initialization with <tt>ManagedStatic</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
<tt>ManagedStatic</tt> is a utility class in LLVM used to implement static
initialization of static resources, such as the global type tables. Before the
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="llvmcontext">Achieving Isolation with <tt>LLVMContext</tt></a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
<tt>LLVMContext</tt> is an opaque class in the LLVM API which clients can use
to operate multiple, isolated instances of LLVM concurrently within the same
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="jitthreading">Threads and the JIT</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
LLVM's "eager" JIT compiler is safe to use in threaded programs. Multiple
threads can call <tt>ExecutionEngine::getPointerToFunction()</tt> or
</p>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="advanced">Advanced Topics</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
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.
</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="TypeResolve">LLVM Type Resolution</a>
-</div>
-
-<div class="doc_text">
-
-<p>
-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.
-</p>
-
-<p>
-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.
-</p>
-
-<p>
-For our purposes below, we need three concepts. First, an "Opaque Type" is
-exactly as defined in the <a href="LangRef.html#t_opaque">language
-reference</a>. Second an "Abstract Type" is any type which includes an
-opaque type as part of its type graph (for example "<tt>{ opaque, i32 }</tt>").
-Third, a concrete type is a type that is not an abstract type (e.g. "<tt>{ i32,
-float }</tt>").
-</p>
-
-</div>
-
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="BuildRecType">Basic Recursive Type Construction</a>
-</div>
-
-<div class="doc_text">
-
-<p>
-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:
-</p>
-
-<div class="doc_code">
-<pre>
-%mylist = type { %mylist*, i32 }
-</pre>
-</div>
-
-<p>
-To build this, use the following LLVM APIs:
-</p>
-
-<div class="doc_code">
-<pre>
-// <i>Create the initial outer struct</i>
-<a href="#PATypeHolder">PATypeHolder</a> StructTy = OpaqueType::get();
-std::vector<const Type*> Elts;
-Elts.push_back(PointerType::getUnqual(StructTy));
-Elts.push_back(Type::Int32Ty);
-StructType *NewSTy = StructType::get(Elts);
-
-// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
-// <i>the struct and the opaque type are actually the same.</i>
-cast<OpaqueType>(StructTy.get())-><a href="#refineAbstractTypeTo">refineAbstractTypeTo</a>(NewSTy);
-
-// <i>NewSTy is potentially invalidated, but StructTy (a <a href="#PATypeHolder">PATypeHolder</a>) is</i>
-// <i>kept up-to-date</i>
-NewSTy = cast<StructType>(StructTy.get());
-
-// <i>Add a name for the type to the module symbol table (optional)</i>
-MyModule->addTypeName("mylist", NewSTy);
-</pre>
-</div>
-
-<p>
-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 <tt><a
-href="#refineAbstractTypeTo">refineAbstractTypeTo</a></tt> method, which is
-described next. After that, we describe the <a
-href="#PATypeHolder">PATypeHolder class</a>.
-</p>
-
-</div>
-
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a>
-</div>
-
-<div class="doc_text">
-<p>
-The <tt>refineAbstractTypeTo</tt> 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).
-</p>
-
-<p>
-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 <b>also</b> deleted. Obviously whenever
-a type is deleted, any "Type*" pointers in the program are invalidated. As
-such, it is safest to avoid having <i>any</i> "Type*" pointers to abstract types
-live across a call to <tt>refineAbstractTypeTo</tt> (note that non-abstract
-types can never move or be deleted). To deal with this, the <a
-href="#PATypeHolder">PATypeHolder</a> class is used to maintain a stable
-reference to a possibly refined type, and the <a
-href="#AbstractTypeUser">AbstractTypeUser</a> class is used to update more
-complex datastructures.
-</p>
-
-</div>
-
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="PATypeHolder">The PATypeHolder Class</a>
-</div>
-
-<div class="doc_text">
-<p>
-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.
-</p>
-
-<p>
-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.
-</p>
-
-</div>
-
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="AbstractTypeUser">The AbstractTypeUser Class</a>
-</div>
-
-<div class="doc_text">
-
-<p>
-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 <i>
- abstract</i> types. Concrete types (those that do not include any opaque
-objects) can never be refined.
-</p>
-</div>
-
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="SymbolTable">The <tt>ValueSymbolTable</tt> and
- <tt>TypeSymbolTable</tt> classes</a>
-</div>
+<h3>
+ <a name="SymbolTable">The <tt>ValueSymbolTable</tt> class</a>
+</h3>
-<div class="doc_text">
+<div>
<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html">
ValueSymbolTable</a></tt> class provides a symbol table that the <a
href="#Function"><tt>Function</tt></a> and <a href="#Module">
<tt>Module</tt></a> classes use for naming value definitions. The symbol table
can provide a name for any <a href="#Value"><tt>Value</tt></a>.
-The <tt><a href="http://llvm.org/doxygen/classllvm_1_1TypeSymbolTable.html">
-TypeSymbolTable</a></tt> class is used by the <tt>Module</tt> class to store
-names for types.</p>
+</p>
<p>Note that the <tt>SymbolTable</tt> class should not be directly accessed
by most clients. It should only be used when iteration over the symbol table
an empty name) do not exist in the symbol table.
</p>
-<p>These symbol tables support iteration over the values/types in the symbol
+<p>Symbol tables support iteration over the values in the symbol
table with <tt>begin/end/iterator</tt> and supports querying to see if a
specific name is in the symbol table (with <tt>lookup</tt>). The
<tt>ValueSymbolTable</tt> class exposes no public mutator methods, instead,
simply call <tt>setName</tt> 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.</p>
+appropriate symbol table.</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
User</a></tt> class provides a basis for expressing the ownership of <tt>User</tt>
towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html">
addition and removal.</p>
<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="Use2User">Interaction and relationship between <tt>User</tt> and <tt>Use</tt> objects</a>
-</div>
+<h4>
+ <a name="Use2User">
+ Interaction and relationship between <tt>User</tt> and <tt>Use</tt> objects
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<p>
A subclass of <tt>User</tt> can choose between incorporating its <tt>Use</tt> objects
or refer to them out-of-line by means of a pointer. A mixed variant
(some <tt>Use</tt>s inline others hung off) is impractical and breaks the invariant
that the <tt>Use</tt> objects belonging to the same <tt>User</tt> form a contiguous array.
</p>
-</div>
<p>
We have 2 different layouts in the <tt>User</tt> (sub)classes:
<i>(In the above figures '<tt>P</tt>' stands for the <tt>Use**</tt> that
is stored in each <tt>Use</tt> object in the member <tt>Use::Prev</tt>)</i>
+</div>
+
<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="Waymarking">The waymarking algorithm</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
Since the <tt>Use</tt> objects are deprived of the direct (back)pointer to
their <tt>User</tt> objects, there must be a fast and exact method to
recover it. This is accomplished by the following scheme:</p>
-</div>
A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> allows to find the
start of the <tt>User</tt> object:
stops, so that the <i>worst case is 20 memory accesses</i> when there are
1000 <tt>Use</tt> objects associated with a <tt>User</tt>.</p>
+</div>
+
<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="ReferenceImpl">Reference implementation</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>
The following literate Haskell fragment demonstrates the concept:</p>
-</div>
<div class="doc_code">
<pre>
OK, passed 500 tests.
</pre>
+</div>
+
<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="Tagging">Tagging considerations</a>
-</div>
+</h4>
+
+<div>
<p>
To maintain the invariant that the 2 LSBits of each <tt>Use**</tt> in <tt>Use</tt>
</div>
- <!-- *********************************************************************** -->
-<div class="doc_section">
- <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
</div>
+
+</div>
+
+<!-- *********************************************************************** -->
+<h2>
+ <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p><tt>#include "<a href="/doxygen/Type_8h-source.html">llvm/Type.h</a>"</tt>
<br>doxygen info: <a href="/doxygen/classllvm_1_1Type.html">Type Class</a></p>
header files in the <tt>include/llvm/</tt> directory, and implemented in
the <tt>lib/VMCore</tt> directory.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Type">The <tt>Type</tt> class and Derived Types</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>Type</tt> is a superclass of all type classes. Every <tt>Value</tt> has
a <tt>Type</tt>. <tt>Type</tt> cannot be instantiated directly but only
be performed with address equality of the Type Instance. That is, given two
<tt>Type*</tt> values, the types are identical if the pointers are identical.
</p>
-</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="m_Type">Important Public Methods</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>bool isIntegerTy() const</tt>: Returns true for any integer type.</li>
<li><tt>bool isFloatingPointTy()</tt>: Return true if this is one of the five
floating point types.</li>
- <li><tt>bool isAbstract()</tt>: Return true if the type is abstract (contains
- an OpaqueType anywhere in its definition).</li>
-
<li><tt>bool isSized()</tt>: Return true if the type has known size. Things
that don't have a size are abstract types, labels and void.</li>
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="derivedtypes">Important Derived Types</a>
-</div>
-<div class="doc_text">
+</h4>
+<div>
<dl>
<dt><tt>IntegerType</tt></dt>
<dd>Subclass of DerivedType that represents integer types of any bit width.
</ul>
</dd>
<dt><tt>SequentialType</tt></dt>
- <dd>This is subclassed by ArrayType and PointerType
+ <dd>This is subclassed by ArrayType, PointerType and VectorType.
<ul>
<li><tt>const Type * getElementType() const</tt>: Returns the type of each
of the elements in the sequential type. </li>
<dt><tt><a name="FunctionType">FunctionType</a></tt></dt>
<dd>Subclass of DerivedTypes for function types.
<ul>
- <li><tt>bool isVarArg() const</tt>: Returns true if its a vararg
+ <li><tt>bool isVarArg() const</tt>: Returns true if it's a vararg
function</li>
<li><tt> const Type * getReturnType() const</tt>: Returns the
return type of the function.</li>
number of formal parameters.</li>
</ul>
</dd>
- <dt><tt>OpaqueType</tt></dt>
- <dd>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.</dd>
</dl>
</div>
-
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Module">The <tt>Module</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a
href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info:
href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few
helpful member functions that try to make common operations easy.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="m_Module">Important Public Members of the <tt>Module</tt> class</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>Module::Module(std::string name = "")</tt></li>
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Value">The <tt>Value</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt>
<br>
represents this value. Although this may take some getting used to, it
simplifies the representation and makes it easier to manipulate.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="m_Value">Important Public Members of the <tt>Value</tt> class</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>Value::use_iterator</tt> - Typedef for iterator over the
use-list<br>
- <tt>Value::use_const_iterator</tt> - Typedef for const_iterator over
+ <tt>Value::const_use_iterator</tt> - Typedef for const_iterator over
the use-list<br>
<tt>unsigned use_size()</tt> - Returns the number of users of the
value.<br>
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="User">The <tt>User</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>
<tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br>
allowing this direct connection. This connection provides the use-def
information in LLVM.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
+<h4>
<a name="m_User">Important Public Members of the <tt>User</tt> class</a>
-</div>
+</h4>
-<div class="doc_text">
+<div>
<p>The <tt>User</tt> class exposes the operand list in two ways: through
an index access interface and through an iterator based interface.</p>
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Instruction">The <tt>Instruction</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "</tt><tt><a
href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br>
this file confuses doxygen, so these enum values don't show up correctly in the
<a href="/doxygen/classllvm_1_1Instruction.html">doxygen output</a>.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="s_Instruction">Important Subclasses of the <tt>Instruction</tt>
- class</a>
-</div>
-<div class="doc_text">
+<h4>
+ <a name="s_Instruction">
+ Important Subclasses of the <tt>Instruction</tt> class
+ </a>
+</h4>
+<div>
<ul>
<li><tt><a name="BinaryOperator">BinaryOperator</a></tt>
<p>This subclasses represents all two operand instructions whose operands
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="m_Instruction">Important Public Members of the <tt>Instruction</tt>
- class</a>
-</div>
+<h4>
+ <a name="m_Instruction">
+ Important Public Members of the <tt>Instruction</tt> class
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt>
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Constant">The <tt>Constant</tt> class and subclasses</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>Constant represents a base class for different types of constants. It
is subclassed by ConstantInt, ConstantArray, etc. for representing
a subclass, which represents the address of a global variable or function.
</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">Important Subclasses of Constant </div>
-<div class="doc_text">
+<h4>Important Subclasses of Constant</h4>
+<div>
<ul>
<li>ConstantInt : This subclass of Constant represents an integer constant of
any width.
</ul>
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="GlobalValue">The <tt>GlobalValue</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a
href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br>
can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM
Language Reference Manual</a>.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="m_GlobalValue">Important Public Members of the <tt>GlobalValue</tt>
- class</a>
-</div>
+<h4>
+ <a name="m_GlobalValue">
+ Important Public Members of the <tt>GlobalValue</tt> class
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>bool hasInternalLinkage() const</tt><br>
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Function">The <tt>Function</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a
href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen
<p>Note that <tt>Function</tt> is a <a href="#GlobalValue">GlobalValue</a>
and therefore also a <a href="#Constant">Constant</a>. The value of the function
is its address (after linking) which is guaranteed to be constant.</p>
-</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="m_Function">Important Public Members of the <tt>Function</tt>
- class</a>
-</div>
+<h4>
+ <a name="m_Function">
+ Important Public Members of the <tt>Function</tt> class
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>Function(const </tt><tt><a href="#FunctionType">FunctionType</a>
</div>
+</div>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a
href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt>
<a href="#Constant"><tt>Constant</tt></a>), and if they have an initializer,
they may be marked as "constant" themselves (indicating that their contents
never change at runtime).</p>
-</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="m_GlobalVariable">Important Public Members of the
- <tt>GlobalVariable</tt> class</a>
-</div>
+<h4>
+ <a name="m_GlobalVariable">
+ Important Public Members of the <tt>GlobalVariable</tt> class
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>GlobalVariable(const </tt><tt><a href="#Type">Type</a> *Ty, bool
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="BasicBlock">The <tt>BasicBlock</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p><tt>#include "<a
href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt><br>
Class</a><br>
Superclass: <a href="#Value"><tt>Value</tt></a></p>
-<p>This class represents a single entry multiple exit section of the code,
+<p>This class represents a single entry single exit section of the code,
commonly known as a basic block by the compiler community. The
<tt>BasicBlock</tt> class maintains a list of <a
href="#Instruction"><tt>Instruction</tt></a>s, which form the body of the block.
like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type
<tt>label</tt>.</p>
-</div>
-
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="m_BasicBlock">Important Public Members of the <tt>BasicBlock</tt>
- class</a>
-</div>
+<h4>
+ <a name="m_BasicBlock">
+ Important Public Members of the <tt>BasicBlock</tt> class
+ </a>
+</h4>
-<div class="doc_text">
+<div>
<ul>
<li><tt>BasicBlock(const std::string &Name = "", </tt><tt><a
</div>
+</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="Argument">The <tt>Argument</tt> class</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<p>This subclass of Value defines the interface for incoming formal
arguments to a function. A Function maintains a list of its formal
</div>
+</div>
+
<!-- *********************************************************************** -->
<hr>
<address>
<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff