"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
+ <meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>LLVM Programmer's Manual</title>
- <link rel="stylesheet" href="llvm.css" type="text/css">
+ <link rel="stylesheet" href="_static/llvm.css" type="text/css">
</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="#isa">The <tt>isa<></tt>, <tt>cast<></tt>
and <tt>dyn_cast<></tt> templates</a> </li>
+ <li><a href="#string_apis">Passing strings (the <tt>StringRef</tt>
+and <tt>Twine</tt> classes)</a>
+ <ul>
+ <li><a href="#StringRef">The <tt>StringRef</tt> class</a> </li>
+ <li><a href="#Twine">The <tt>Twine</tt> class</a> </li>
+ </ul>
+ </li>
<li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt>
option</a>
<ul>
<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_smallset">"llvm/ADT/SmallSet.h"</a></li>
<li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
<li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
+ <li><a href="#dss_sparseset">"llvm/ADT/SparseSet.h"</a></li>
<li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
<li><a href="#dss_set"><set></a></li>
<li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
<li><a href="#dss_uniquevector">"llvm/ADT/UniqueVector.h"</a></li>
- <li><a href="#dss_otherset">Other Set-Like ContainerOptions</a></li>
+ <li><a href="#dss_immutableset">"llvm/ADT/ImmutableSet.h"</a></li>
+ <li><a href="#dss_otherset">Other Set-Like Container Options</a></li>
</ul></li>
<li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
<ul>
<li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</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_multiimplmap">"llvm/ADT/MultiImplMap.h"</a></li>
+ <li><a href="#dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a></li>
+ <li><a href="#dss_smallmap">"llvm/ADT/SmallMap.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_immutablemap">"llvm/ADT/ImmutableMap.h"</a></li>
<li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
</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="#dss_smallbitvector">A "small" dense bitvector</a></li>
<li><a href="#dss_sparsebitvector">A sparse bitvector</a></li>
</ul></li>
</ul>
</ul>
</li>
- <li><a href="#advanced">Advanced Topics</a>
+ <li><a href="#threading">Threads and LLVM</a>
<ul>
- <li><a href="#TypeResolve">LLVM Type Resolution</a>
+ <li><a href="#startmultithreaded">Entering and Exiting Multithreaded Mode
+ </a></li>
+ <li><a href="#shutdown">Ending execution with <tt>llvm_shutdown()</tt></a></li>
+ <li><a href="#managedstatic">Lazy initialization with <tt>ManagedStatic</tt></a></li>
+ <li><a href="#llvmcontext">Achieving Isolation with <tt>LLVMContext</tt></a></li>
+ <li><a href="#jitthreading">Threads and the JIT</a></li>
+ </ul>
+ </li>
+
+ <li><a href="#advanced">Advanced Topics</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>
<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
<a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>,
<a href="mailto:ggreif@gmail.com">Gabor Greif</a>,
- <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a> and
- <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
+ <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>,
+ <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> and
+ <a href="mailto:owen@apple.com">Owen Anderson</a></p>
</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>
+
<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
+<h3>
+ <a name="string_apis">Passing strings (the <tt>StringRef</tt>
+and <tt>Twine</tt> classes)</a>
+</h3>
+
+<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
+Value class -- which has names for instructions, functions, etc. -- and the
+StringMap class which is used extensively in LLVM and Clang.</p>
+
+<p>These are generic classes, and they need to be able to accept strings which
+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>StringRef</tt> or a <tt>const Twine&</tt> for
+passing strings efficiently.</p>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="StringRef">The <tt>StringRef</tt> class</a>
+</h4>
+
+<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
+on <tt>std:string</tt>, but does not require heap allocation.</p>
+
+<p>It can be implicitly constructed using a C style null-terminated string,
+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>
+
+<pre class="doc_code">
+ iterator find(StringRef Key);
+</pre>
+
+<p>and clients can call it using any one of:</p>
+
+<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>
+
+<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>
+using the <tt>str</tt> member function. See
+"<tt><a href="/doxygen/classllvm_1_1StringRef_8h-source.html">llvm/ADT/StringRef.h</a></tt>"
+for more information.</p>
+
+<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). StringRef is
+small and pervasive enough in LLVM that it should always be passed by value.</p>
+
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="Twine">The <tt>Twine</tt> class</a>
+</h4>
+
+<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
+the name of another instruction with a suffix, for example:</p>
+
+<div class="doc_code">
+<pre>
+ New = CmpInst::Create(<i>...</i>, SO->getName() + ".cmp");
+</pre>
+</div>
+
+<p>The <tt>Twine</tt> class is effectively a
+lightweight <a href="http://en.wikipedia.org/wiki/Rope_(computer_science)">rope</a>
+which points to temporary (stack allocated) objects. Twines can be implicitly
+constructed as the result of the plus operator applied to strings (i.e., a C
+strings, an <tt>std::string</tt>, or a <tt>StringRef</tt>). The twine delays the
+actual concatenation of strings until it is actually required, at which point
+it can be efficiently rendered directly into a character array. This avoids
+unnecessary heap allocation involved in constructing the temporary results of
+string concatenation. See
+"<tt><a href="/doxygen/classllvm_1_1Twine_8h-source.html">llvm/ADT/Twine.h</a></tt>"
+for more information.</p>
+
+<p>As with a <tt>StringRef</tt>, <tt>Twine</tt> objects point to external memory
+and should almost never be stored or mentioned directly. They are intended
+solely for use when defining a function which should be able to efficiently
+accept concatenated strings.</p>
+
+</div>
+
+</div>
+
+<!-- ======================================================================= -->
+<h3>
+ <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
+</h3>
+
+<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
<div class="doc_code">
<pre>
-DOUT << "I am here!\n";
+DEBUG(errs() << "I am here!\n");
</pre>
</div>
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 class="doc_code">
<pre>
-DOUT << "No debug type\n";
#undef DEBUG_TYPE
+DEBUG(errs() << "No debug type\n");
#define DEBUG_TYPE "foo"
-DOUT << "'foo' debug type\n";
+DEBUG(errs() << "'foo' debug type\n");
#undef DEBUG_TYPE
#define DEBUG_TYPE "bar"
-DOUT << "'bar' debug type\n";
+DEBUG(errs() << "'bar' debug type\n"));
#undef DEBUG_TYPE
#define DEBUG_TYPE ""
-DOUT << "No debug type (2)\n";
+DEBUG(errs() << "No debug type (2)\n");
</pre>
</div>
for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>,
even if the source lives in multiple files.</p>
+<p>The <tt>DEBUG_WITH_TYPE</tt> macro is also available for situations where you
+would like to set <tt>DEBUG_TYPE</tt>, but only for one specific <tt>DEBUG</tt>
+statement. It takes an additional first parameter, which is the type to use. For
+example, the preceding example could be written as:</p>
+
+
+<div class="doc_code">
+<pre>
+DEBUG_WITH_TYPE("", errs() << "No debug type\n");
+DEBUG_WITH_TYPE("foo", errs() << "'foo' debug type\n");
+DEBUG_WITH_TYPE("bar", errs() << "'bar' debug type\n"));
+DEBUG_WITH_TYPE("", errs() << "No debug type (2)\n");
+</pre>
+</div>
+
+</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
iteration, but do not support efficient look-up based on a key.
</li>
+<li>a <a href="#ds_string">string</a> container is a specialized sequential
+ container or reference structure that is used for character or byte
+ arrays.</li>
+
<li>a <a href="#ds_bit">bit</a> container provides an efficient way to store and
perform set operations on sets of numeric id's, while automatically
eliminating duplicates. Bit containers require a maximum of 1 bit for each
. Doing so avoids (relatively) expensive malloc/free calls, which dwarf the
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
<pre>
for ( ... ) {
std::vector<foo> V;
- use V;
+ // make use of V.
}
</pre>
</div>
<pre>
std::vector<foo> V;
for ( ... ) {
- use V;
+ // make use of V.
V.clear();
}
</pre>
</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>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<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">
-<p><tt>ilist</tt>s have another speciality that must be considered. To be a good
+<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
<tt>operator--</tt> must work correctly on the <tt>end</tt> iterator in 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">
- <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
+<h4>
+ <a name="dss_sparseset">"llvm/ADT/SparseSet.h"</a>
+</h4>
+
+<div>
+
+<p>SparseSet holds a small number of objects identified by unsigned keys of
+moderate size. It uses a lot of memory, but provides operations that are
+almost as fast as a vector. Typical keys are physical registers, virtual
+registers, or numbered basic blocks.</p>
+
+<p>SparseSet is useful for algorithms that need very fast clear/find/insert/erase
+and fast iteration over small sets. It is not intended for building composite
+data structures.</p>
+
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
+</h4>
+
+<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
faster.
</p>
-<p>SetVector is an adapter class that defaults to using std::vector and std::set
-for the underlying containers, so it is quite expensive. However,
-<tt>"llvm/ADT/SetVector.h"</tt> 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.</p>
+<p><tt>SetVector</tt> is an adapter class that defaults to
+ using <tt>std::vector</tt> and a size 16 <tt>SmallSet</tt> for the underlying
+ containers, so it is quite expensive. However,
+ <tt>"llvm/ADT/SetVector.h"</tt> also provides a <tt>SmallSetVector</tt>
+ class, which defaults to using a <tt>SmallVector</tt> and <tt>SmallSet</tt>
+ of a specified size. If you use this, and if your sets are dynamically
+ smaller than <tt>N</tt>, you will save a lot of heap traffic.</p>
</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>
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_immutableset">"llvm/ADT/ImmutableSet.h"</a>
+</h4>
+
+<div>
+
+<p>
+ImmutableSet is an immutable (functional) set implementation based on an AVL
+tree.
+Adding or removing elements is done through a Factory object and results in the
+creation of a new ImmutableSet object.
+If an ImmutableSet already exists with the given contents, then the existing one
+is returned; equality is compared with a FoldingSetNodeID.
+The time and space complexity of add or remove operations is logarithmic in the
+size of the original set.
+
+<p>
+There is no method for returning an element of the set, you can only check for
+membership.
+
+</div>
+
<!-- _______________________________________________________________________ -->
-<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
<p>StringMap also provides query methods that take byte ranges, so it only ever
copies a string if a value is inserted into the table.</p>
+
+<p>StringMap iteratation order, however, is not guaranteed to be deterministic,
+so any uses which require that should instead use a std::map.</p>
</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
<p>
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
+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
is required to tell DenseMap about two special marker values (which can never be
inserted into the map) that it needs internally.</p>
+<p>
+DenseMap's find_as() method supports lookup operations using an alternate key
+type. This is useful in cases where the normal key type is expensive to
+construct, but cheap to compare against. The DenseMapInfo is responsible for
+defining the appropriate comparison and hashing methods for each alternate
+key type used.
+</p>
+
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_map"><map></a>
+<h4>
+ <a name="dss_valuemap">"llvm/ADT/ValueMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+ValueMap is a wrapper around a <a href="#dss_densemap">DenseMap</a> mapping
+Value*s (or subclasses) to another type. When a Value is deleted or RAUW'ed,
+ValueMap will update itself so the new version of the key is mapped to the same
+value, just as if the key were a WeakVH. You can configure exactly how this
+happens, and what else happens on these two events, by passing
+a <code>Config</code> parameter to the ValueMap template.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_multiimplmap">"llvm/ADT/MultiImplMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+MultiImplMap is map that has two modes, one for small amount of elements and
+one for big amount. User should set map implementation for both of them.
+User also should set the maximum possible number of elements for small mode.
+</p>
+
+<p>
+If user want to use MultiImplMap instead of
+<a href="#dss_densemap">DenseMap</a>, he should pass template parameter
+DenseMapCompatible = true. Note, that in this case map implementations
+should present additional DenseMap specific methods (see below):
+<code>isPointerIntoBucketsArray</code>, <code>getPointerIntoBucketsArray</code>
+and <code>FindAndConstruct</code>.
+</p>
+
+<p>
+Initially MultiImplMap uses small mode and small map implementation. It
+triggered to the big mode when the number of contained elements exceeds
+maximum possible elements for small mode.
+</p>
+
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_flatarraymap">"llvm/ADT/FlatArrayMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+FlatArrayMap optimized for small amount of elements. It uses flat array
+implementation inside:
+</p>
+<pre>[ key0, value0, key1, value1, ... keyN, valueN ]</pre>
+
+
+<p>
+User should pass key type, mapped type (type of value), and maximum
+number of elements.
+</p>
+
+<p>
+After maximum number of elements is reached, map declines any further
+attempts to insert new elements ("insert" method returns <end(),
+false>).
+</p>
+
+<p>
+FlatArrayMap has interface that is compatible with
+<a href="#dss_densemap">DenseMap</a>, so user can replace it with DenseMap
+without any code changing and vice versa.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_smallmap">"llvm/ADT/SmallMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+SmallMap is wrapper around <a href="#dss_multiimplmap">MultiImplMap</a>.
+It uses <a href="#dss_flatarraymap">FlatArrayMap</a> for small mode, and
+<a href="#dss_densemap">DenseMap</a> for big mode.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<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>
+
+<!-- _______________________________________________________________________ -->
+<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_immutablemap">"llvm/ADT/ImmutableMap.h"</a>
+</h4>
+
+<div>
+
+<p>
+ImmutableMap is an immutable (functional) map implementation based on an AVL
+tree.
+Adding or removing elements is done through a Factory object and results in the
+creation of a new ImmutableMap object.
+If an ImmutableMap already exists with the given key set, then the existing one
+is returned; equality is compared with a FoldingSetNodeID.
+The time and space complexity of add or remove operations is logarithmic in the
+size of the original map.
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<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>
+
<!-- ======================================================================= -->
-<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">
-<p> The BitVector container provides a fixed size set of bits for manipulation.
+<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
at a time, instead of one bit at a time. This makes the BitVector very fast for
</div>
<!-- _______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="dss_sparsebitvector">SparseBitVector</a>
+<h4>
+ <a name="dss_smallbitvector">SmallBitVector</a>
+</h4>
+
+<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
+slightly less efficiently than a plain BitVector, so SmallBitVector should
+only be used when larger counts are rare.
+</p>
+
+<p>
+At this time, SmallBitVector does not support set operations (and, or, xor),
+and its operator[] does not provide an assignable lvalue.
+</p>
</div>
-<div class="doc_text">
+<!-- _______________________________________________________________________ -->
+<h4>
+ <a name="dss_sparsebitvector">SparseBitVector</a>
+</h4>
+
+<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
for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i)
// <i>Print out the name of the basic block if it has one, and then the</i>
// <i>number of instructions that it contains</i>
- llvm::cerr << "Basic block (name=" << i->getName() << ") has "
+ errs() << "Basic block (name=" << i->getName() << ") has "
<< i->size() << " instructions.\n";
</pre>
</div>
</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
for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
// <i>The next statement works since operator<<(ostream&,...)</i>
// <i>is overloaded for Instruction&</i>
- llvm::cerr << *i << "\n";
+ errs() << *i << "\n";
</pre>
</div>
<p>However, this isn't really the best way to print out the contents of a
<tt>BasicBlock</tt>! 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: <tt>llvm::cerr << *blk << "\n";</tt>.</p>
+basic block itself: <tt>errs() << *blk << "\n";</tt>.</p>
</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,
// <i>F is a pointer to a Function instance</i>
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
- llvm::cerr << *I << "\n";
+ errs() << *I << "\n";
</pre>
</div>
</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
void printNextInstruction(Instruction* inst) {
BasicBlock::iterator it(inst);
++it; // <i>After this line, it refers to the instruction after *inst</i>
- if (it != inst->getParent()->end()) llvm::cerr << *it << "\n";
+ if (it != inst->getParent()->end()) errs() << *it << "\n";
}
</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
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";
+ errs() << "F is used in instruction:\n";
+ errs() << *Inst << "\n";
}
</pre>
</div>
-<p>Alternately, it's common to have an instance of the <a
+<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
<tt>User</tt> is known as a <i>use-def</i> chain. Instances of class
</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>
+<h5><i>Replacing individual instructions</i></h5>
<p>Including "<a href="/doxygen/BasicBlockUtils_8h-source.html">llvm/Transforms/Utils/BasicBlockUtils.h</a>"
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>
+<div>
<ul>
<li><tt>ReplaceInstWithValue</tt>
</pre></div></li>
</ul>
-<p><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></p>
+</div>
+
+<h5><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></h5>
<p>You can use <tt>Value::replaceAllUsesWith</tt> and
<tt>User::replaceUsesOfWith</tt> to change more than one use at a time. See the
</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
+statically, you can use <tt>TypeBuilder<...>::get()</tt>, defined
in <tt>llvm/Support/TypeBuilder.h</tt>, to retrieve them. <tt>TypeBuilder</tt>
has two forms depending on whether you're building types for cross-compilation
-or native library use. <tt>TypeBuilder<T, true></tt> requires
+or native library use. <tt>TypeBuilder<T, true></tt> requires
that <tt>T</tt> be independent of the host environment, meaning that it's built
out of types from
the <a href="/doxygen/namespacellvm_1_1types.html"><tt>llvm::types</tt></a>
namespace and pointers, functions, arrays, etc. built of
-those. <tt>TypeBuilder<T, false></tt> additionally allows native C types
+those. <tt>TypeBuilder<T, false></tt> additionally allows native C types
whose size may depend on the host compiler. For example,</p>
<div class="doc_code">
<pre>
-FunctionType *ft = TypeBuilder<types::i<8>(types::i<32>*), true>::get();
+FunctionType *ft = TypeBuilder<types::i<8>(types::i<32>*), true>::get();
</pre>
</div>
<div class="doc_code">
<pre>
-std::vector<const Type*> params;
+std::vector<const Type*> params;
params.push_back(PointerType::getUnqual(Type::Int32Ty));
FunctionType *ft = FunctionType::get(Type::Int8Ty, params, false);
</pre>
</div>
-<!-- *********************************************************************** -->
-<div class="doc_section">
- <a name="advanced">Advanced Topics</a>
</div>
+
+<!-- *********************************************************************** -->
+<h2>
+ <a name="threading">Threads and LLVM</a>
+</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.
+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
+application.
+</p>
+
+<p>
+Note that LLVM's support for multithreading is still relatively young. Up
+through version 2.5, the execution of threaded hosted applications was
+supported, but not threaded client access to the APIs. While this use case is
+now supported, clients <em>must</em> adhere to the guidelines specified below to
+ensure proper operation in multithreaded mode.
+</p>
+
+<p>
+Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic
+intrinsics in order to support threaded operation. If you need a
+multhreading-capable LLVM on a platform without a suitably modern system
+compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and
+using the resultant compiler to build a copy of LLVM with multithreading
+support.
</p>
-</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="TypeResolve">LLVM Type Resolution</a>
-</div>
+<h3>
+ <a name="startmultithreaded">Entering and Exiting Multithreaded Mode</a>
+</h3>
-<div class="doc_text">
+<div>
<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.
+In order to properly protect its internal data structures while avoiding
+excessive locking overhead in the single-threaded case, the LLVM must intialize
+certain data structures necessary to provide guards around its internals. To do
+so, the client program must invoke <tt>llvm_start_multithreaded()</tt> before
+making any concurrent LLVM API calls. To subsequently tear down these
+structures, use the <tt>llvm_stop_multithreaded()</tt> call. You can also use
+the <tt>llvm_is_multithreaded()</tt> call to check the status of multithreaded
+mode.
</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.
+Note that both of these calls must be made <em>in isolation</em>. That is to
+say that no other LLVM API calls may be executing at any time during the
+execution of <tt>llvm_start_multithreaded()</tt> or <tt>llvm_stop_multithreaded
+</tt>. It's is the client's responsibility to enforce this isolation.
</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>").
+The return value of <tt>llvm_start_multithreaded()</tt> indicates the success or
+failure of the initialization. Failure typically indicates that your copy of
+LLVM was built without multithreading support, typically because GCC atomic
+intrinsics were not found in your system compiler. In this case, the LLVM API
+will not be safe for concurrent calls. However, it <em>will</em> be safe for
+hosting threaded applications in the JIT, though <a href="#jitthreading">care
+must be taken</a> to ensure that side exits and the like do not accidentally
+result in concurrent LLVM API calls.
</p>
-
</div>
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="BuildRecType">Basic Recursive Type Construction</a>
-</div>
-
-<div class="doc_text">
+<!-- ======================================================================= -->
+<h3>
+ <a name="shutdown">Ending Execution with <tt>llvm_shutdown()</tt></a>
+</h3>
+<div>
<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:
+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
+<tt>llvm_stop_multithreaded()</tt> if LLVM is operating in multithreaded mode.
+As such, <tt>llvm_shutdown()</tt> requires the same isolation guarantees as
+<tt>llvm_stop_multithreaded()</tt>.
</p>
-<div class="doc_code">
-<pre>
-%mylist = type { %mylist*, i32 }
-</pre>
+<p>
+Note that, if you use scope-based shutdown, you can use the
+<tt>llvm_shutdown_obj</tt> class, which calls <tt>llvm_shutdown()</tt> in its
+destructor.
</div>
+<!-- ======================================================================= -->
+<h3>
+ <a name="managedstatic">Lazy Initialization with <tt>ManagedStatic</tt></a>
+</h3>
+
+<div>
<p>
-To build this, use the following LLVM APIs:
+<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
+invocation of <tt>llvm_shutdown()</tt>, it implements a simple lazy
+initialization scheme. Once <tt>llvm_start_multithreaded()</tt> returns,
+however, it uses double-checked locking to implement thread-safe lazy
+initialization.
</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>.
+Note that, because no other threads are allowed to issue LLVM API calls before
+<tt>llvm_start_multithreaded()</tt> returns, it is possible to have
+<tt>ManagedStatic</tt>s of <tt>llvm::sys::Mutex</tt>s.
</p>
+<p>
+The <tt>llvm_acquire_global_lock()</tt> and <tt>llvm_release_global_lock</tt>
+APIs provide access to the global lock used to implement the double-checked
+locking for lazy initialization. These should only be used internally to LLVM,
+and only if you know what you're doing!
+</p>
</div>
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a>
-</div>
+<!-- ======================================================================= -->
+<h3>
+ <a name="llvmcontext">Achieving Isolation with <tt>LLVMContext</tt></a>
+</h3>
-<div class="doc_text">
+<div>
<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).
+<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
+address space. For instance, in a hypothetical compile-server, the compilation
+of an individual translation unit is conceptually independent from all the
+others, and it would be desirable to be able to compile incoming translation
+units concurrently on independent server threads. Fortunately,
+<tt>LLVMContext</tt> exists to enable just this kind of scenario!
</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.
+Conceptually, <tt>LLVMContext</tt> provides isolation. Every LLVM entity
+(<tt>Module</tt>s, <tt>Value</tt>s, <tt>Type</tt>s, <tt>Constant</tt>s, etc.)
+in LLVM's in-memory IR belongs to an <tt>LLVMContext</tt>. Entities in
+different contexts <em>cannot</em> interact with each other: <tt>Module</tt>s in
+different contexts cannot be linked together, <tt>Function</tt>s cannot be added
+to <tt>Module</tt>s in different contexts, etc. What this means is that is is
+safe to compile on multiple threads simultaneously, as long as no two threads
+operate on entities within the same context.
</p>
-</div>
-
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="PATypeHolder">The PATypeHolder Class</a>
-</div>
+<p>
+In practice, very few places in the API require the explicit specification of a
+<tt>LLVMContext</tt>, other than the <tt>Type</tt> creation/lookup APIs.
+Because every <tt>Type</tt> carries a reference to its owning context, most
+other entities can determine what context they belong to by looking at their
+own <tt>Type</tt>. If you are adding new entities to LLVM IR, please try to
+maintain this interface design.
+</p>
-<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.
+For clients that do <em>not</em> require the benefits of isolation, LLVM
+provides a convenience API <tt>getGlobalContext()</tt>. This returns a global,
+lazily initialized <tt>LLVMContext</tt> that may be used in situations where
+isolation is not a concern.
</p>
+</div>
+<!-- ======================================================================= -->
+<h3>
+ <a name="jitthreading">Threads and the JIT</a>
+</h3>
+
+<div>
<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.
+LLVM's "eager" JIT compiler is safe to use in threaded programs. Multiple
+threads can call <tt>ExecutionEngine::getPointerToFunction()</tt> or
+<tt>ExecutionEngine::runFunction()</tt> concurrently, and multiple threads can
+run code output by the JIT concurrently. The user must still ensure that only
+one thread accesses IR in a given <tt>LLVMContext</tt> while another thread
+might be modifying it. One way to do that is to always hold the JIT lock while
+accessing IR outside the JIT (the JIT <em>modifies</em> the IR by adding
+<tt>CallbackVH</tt>s). Another way is to only
+call <tt>getPointerToFunction()</tt> from the <tt>LLVMContext</tt>'s thread.
</p>
+<p>When the JIT is configured to compile lazily (using
+<tt>ExecutionEngine::DisableLazyCompilation(false)</tt>), there is currently a
+<a href="http://llvm.org/bugs/show_bug.cgi?id=5184">race condition</a> in
+updating call sites after a function is lazily-jitted. It's still possible to
+use the lazy JIT in a threaded program if you ensure that only one thread at a
+time can call any particular lazy stub and that the JIT lock guards any IR
+access, but we suggest using only the eager JIT in threaded programs.
+</p>
</div>
-<!-- ______________________________________________________________________ -->
-<div class="doc_subsubsection">
- <a name="AbstractTypeUser">The AbstractTypeUser Class</a>
</div>
-<div class="doc_text">
+<!-- *********************************************************************** -->
+<h2>
+ <a name="advanced">Advanced Topics</a>
+</h2>
+<!-- *********************************************************************** -->
+<div>
<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.
+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="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 isInteger() const</tt>: Returns true for any integer type.</li>
+ <li><tt>bool isIntegerTy() const</tt>: Returns true for any integer type.</li>
- <li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two
+ <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>VectorType</tt></dt>
<dd>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
+ a first class type whereas ArrayType is not. Vector types are used for
vector operations and are usually small vectors of of an integer or floating
point type.</dd>
<dt><tt>StructType</tt></dt>
<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>
-</ul>
+ <li><tt>Module::Module(std::string name = "")</tt>
-<p>Constructing a <a href="#Module">Module</a> is easy. You can optionally
+
<p>Constructing a <a href="#Module">Module</a> is easy. You can optionally
provide a name for it (probably based on the name of the translation unit).</p>
+ </li>
-<ul>
<li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
<tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
</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
<a href="#Value"><tt>Value</tt></a></p>
<p>The <tt>Function</tt> class represents a single procedure in LLVM. It is
-actually one of the more complex classes in the LLVM heirarchy because it must
+actually one of the more complex classes in the LLVM hierarchy because it must
keep track of a large amount of data. The <tt>Function</tt> class keeps track
of a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, a list of formal
<a href="#Argument"><tt>Argument</tt></a>s, and a
<p>The list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s is the most
commonly used part of <tt>Function</tt> objects. The list imposes an implicit
ordering of the blocks in the function, which indicate how the code will be
-la
yed out by the backend. Additionally, the first <a
+la
id out by the backend. Additionally, the first <a
href="#BasicBlock"><tt>BasicBlock</tt></a> is the implicit entry node for the
<tt>Function</tt>. 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
<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="#User"><tt>User</tt></a>,
<a href="#Value"><tt>Value</tt></a></p>
-<p>Global variables are represented with the (suprise suprise)
+<p>Global variables are represented with the (surprise surprise)
<tt>GlobalVariable</tt> class. Like functions, <tt>GlobalVariable</tt>s are also
subclasses of <a href="#GlobalValue"><tt>GlobalValue</tt></a>, and as such are
always referenced by their address (global values must live in memory, so their
<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
<li><tt><a href="#Constant">Constant</a> *getInitializer()</tt>
- <p>Returns the intial value for a <tt>GlobalVariable</tt>. It is not legal
+ <p>Returns the initial value for a <tt>GlobalVariable</tt>. It is not legal
to call this method if there is no initializer.</p></li>
</ul>
</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>
-doxygen info: <a href="/doxygen/structllvm_1_1BasicBlock.html">BasicBlock
+doxygen info: <a href="/doxygen/classllvm_1_1BasicBlock.html">BasicBlock
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