-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head><title>LLVM Programmer's Manual</title></head>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
+ "http://www.w3.org/TR/html4/strict.dtd">
+<html>
+<head>
+ <title>LLVM Programmer's Manual</title>
+ <link rel="stylesheet" href="llvm.css" type="text/css">
+</head>
+<body>
+
+<div class="doc_title">
+ LLVM Programmer's Manual
+</div>
-<body bgcolor=white>
-
-<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td> <font size=+3 color="#EEEEFF" face="Georgia,Palatino,Times,Roman"><b>LLVM Programmer's Manual</b></font></td>
-</tr></table>
-
<ol>
- <li><a href="#introduction">Introduction</a>
+ <li><a href="#introduction">Introduction</a></li>
<li><a href="#general">General Information</a>
- <ul>
- <li><a href="#stl">The C++ Standard Template Library</a>
+ <li><a href="#stl">The C++ Standard Template Library</a></li>
<!--
- <li>The <tt>-time-passes</tt> option
- <li>How to use the LLVM Makefile system
- <li>How to write a regression test
--->
- </ul>
+ <li>The <tt>-time-passes</tt> option</li>
+ <li>How to use the LLVM Makefile system</li>
+ <li>How to write a regression test</li>
+
+-->
+ </ul>
+ </li>
<li><a href="#apis">Important and useful LLVM APIs</a>
- <ul>
- <li><a href="#isa">The <tt>isa<></tt>, <tt>cast<></tt> and
- <tt>dyn_cast<></tt> templates</a>
- <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro &
- <tt>-debug</tt> option</a>
<ul>
- <li><a href="#DEBUG_TYPE">Fine grained debug info with
- <tt>DEBUG_TYPE</tt> and the <tt>-debug-only</tt> option</a/>
- </ul>
- <li><a href="#Statistic">The <tt>Statistic</tt> template &
- <tt>-stats</tt> option</a>
+ <li><a href="#isa">The <tt>isa<></tt>, <tt>cast<></tt>
+and <tt>dyn_cast<></tt> templates</a> </li>
+ <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt>
+option</a>
+ <ul>
+ <li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt>
+and the <tt>-debug-only</tt> option</a> </li>
+ </ul>
+ </li>
+ <li><a href="#Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt>
+option</a></li>
<!--
- <li>The <tt>InstVisitor</tt> template
- <li>The general graph API
--->
+ <li>The <tt>InstVisitor</tt> template
+ <li>The general graph API
+-->
+ <li><a href="#ViewGraph">Viewing graphs while debugging code</a></li>
+ </ul>
+ </li>
+ <li><a href="#datastructure">Picking the Right Data Structure for a Task</a>
+ <ul>
+ <li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
+ <ul>
+ <li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li>
+ <li><a href="#dss_heaparrays">Heap Allocated Arrays</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</a></li>
+ <li><a href="#dss_other">Other Sequential Container Options</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_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>
+ </ul></li>
+ <li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
+ <ul>
+ <li><a href="#dss_sortedvectormap">A sorted 'vector'</a></li>
+ <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_map"><map></a></li>
+ <li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
+ </ul></li>
</ul>
+ </li>
<li><a href="#common">Helpful Hints for Common Operations</a>
- <ul>
- <li><a href="#inspection">Basic Inspection and Traversal Routines</a>
- <ul>
- <li><a href="#iterate_function">Iterating over the <tt>BasicBlock</tt>s
- in a <tt>Function</tt></a>
- <li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s
- in a <tt>BasicBlock</tt></a>
- <li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s
- in a <tt>Function</tt></a>
- <li><a href="#iterate_convert">Turning an iterator into a class
- pointer</a>
- <li><a href="#iterate_complex">Finding call sites: a more complex
- example</a>
- <li><a href="#iterate_chains">Iterating over def-use & use-def
- chains</a>
- </ul>
- <li><a href="#simplechanges">Making simple changes</a>
<ul>
- <li><a href="#schanges_creating">Creating and inserting new
- <tt>Instruction</tt>s</a>
- <li><a href="#schanges_deleting">Deleting
- <tt>Instruction</tt>s</a>
- <li><a href="#schanges_replacing">Replacing an
- <tt>Instruction</tt> with another <tt>Value</tt></a>
- </ul>
+ <li><a href="#inspection">Basic Inspection and Traversal Routines</a>
+ <ul>
+ <li><a href="#iterate_function">Iterating over the <tt>BasicBlock</tt>s
+in a <tt>Function</tt></a> </li>
+ <li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s
+in a <tt>BasicBlock</tt></a> </li>
+ <li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s
+in a <tt>Function</tt></a> </li>
+ <li><a href="#iterate_convert">Turning an iterator into a
+class pointer</a> </li>
+ <li><a href="#iterate_complex">Finding call sites: a more
+complex example</a> </li>
+ <li><a href="#calls_and_invokes">Treating calls and invokes
+the same way</a> </li>
+ <li><a href="#iterate_chains">Iterating over def-use &
+use-def chains</a> </li>
+ </ul>
+ </li>
+ <li><a href="#simplechanges">Making simple changes</a>
+ <ul>
+ <li><a href="#schanges_creating">Creating and inserting new
+ <tt>Instruction</tt>s</a> </li>
+ <li><a href="#schanges_deleting">Deleting <tt>Instruction</tt>s</a> </li>
+ <li><a href="#schanges_replacing">Replacing an <tt>Instruction</tt>
+with another <tt>Value</tt></a> </li>
+ <li><a href="#schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a> </li>
+ </ul>
+ </li>
<!--
<li>Working with the Control Flow Graph
<ul>
<li>
<li>
</ul>
--->
- </ul>
- <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
+-->
+ </ul>
+ </li>
+
+ <li><a href="#advanced">Advanced Topics</a>
+ <ul>
+ <li><a href="#TypeResolve">LLVM Type Resolution</a>
<ul>
- <li><a href="#Value">The <tt>Value</tt> class</a>
+ <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>
+ </ul></li>
+
+ <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
<ul>
- <li><a href="#User">The <tt>User</tt> class</a>
+ <li><a href="#Type">The <tt>Type</tt> class</a> </li>
+ <li><a href="#Module">The <tt>Module</tt> class</a></li>
+ <li><a href="#Value">The <tt>Value</tt> class</a>
<ul>
- <li><a href="#Instruction">The <tt>Instruction</tt> class</a>
- <ul>
- <li>
- </ul>
- <li><a href="#GlobalValue">The <tt>GlobalValue</tt> class</a>
- <ul>
- <li><a href="#BasicBlock">The <tt>BasicBlock</tt> class</a>
- <li><a href="#Function">The <tt>Function</tt> class</a>
- <li><a href="#GlobalVariable">The <tt>GlobalVariable</tt> class</a>
- </ul>
- <li><a href="#Module">The <tt>Module</tt> class</a>
- <li><a href="#Constant">The <tt>Constant</tt> class</a>
+ <li><a href="#User">The <tt>User</tt> class</a>
<ul>
- <li>
- <li>
+ <li><a href="#Instruction">The <tt>Instruction</tt> class</a></li>
+ <li><a href="#Constant">The <tt>Constant</tt> class</a>
+ <ul>
+ <li><a href="#GlobalValue">The <tt>GlobalValue</tt> class</a>
+ <ul>
+ <li><a href="#Function">The <tt>Function</tt> class</a></li>
+ <li><a href="#GlobalVariable">The <tt>GlobalVariable</tt> class</a></li>
+ </ul>
+ </li>
+ </ul>
+ </li>
</ul>
+ </li>
+ <li><a href="#BasicBlock">The <tt>BasicBlock</tt> class</a></li>
+ <li><a href="#Argument">The <tt>Argument</tt> class</a></li>
</ul>
- <li><a href="#Type">The <tt>Type</tt> class</a>
- <li><a href="#Argument">The <tt>Argument</tt> class</a>
- </ul>
- <li>The <tt>SymbolTable</tt> class
- <li>The <tt>ilist</tt> and <tt>iplist</tt> classes
- <ul>
- <li>Creating, inserting, moving and deleting from LLVM lists
+ </li>
</ul>
- <li>Important iterator invalidation semantics to be aware of
- </ul>
-
- <p><b>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
- <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>, and
- <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a></b><p>
+ </li>
</ol>
+<div class="doc_author">
+ <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:jstanley@cs.uiuc.edu">Joel Stanley</a>, and
+ <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p>
+</div>
<!-- *********************************************************************** -->
-<table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
-<a name="introduction">Introduction
-</b></font></td></tr></table><ul>
+<div class="doc_section">
+ <a name="introduction">Introduction </a>
+</div>
<!-- *********************************************************************** -->
-This document is meant to highlight some of the important classes and interfaces
-available in the LLVM source-base. This manual is not intended to explain what
-LLVM is, how it works, and what LLVM code looks like. It assumes that you know
-the basics of LLVM and are interested in writing transformations or otherwise
-analyzing or manipulating the code.<p>
+<div class="doc_text">
+
+<p>This document is meant to highlight some of the important classes and
+interfaces available in the LLVM source-base. This manual is not
+intended to explain what LLVM is, how it works, and what LLVM code looks
+like. It assumes that you know the basics of LLVM and are interested
+in writing transformations or otherwise analyzing or manipulating the
+code.</p>
-This document should get you oriented so that you can find your way in the
-continuously growing source code that makes up the LLVM infrastructure. Note
-that this manual is not intended to serve as a replacement for reading the
-source code, so if you think there should be a method in one of these classes to
-do something, but it's not listed, check the source. Links to the <a
-href="/doxygen/">doxygen</a> sources are provided to make this as easy as
-possible.<p>
+<p>This document should get you oriented so that you can find your
+way in the continuously growing source code that makes up the LLVM
+infrastructure. Note that this manual is not intended to serve as a
+replacement for reading the source code, so if you think there should be
+a method in one of these classes to do something, but it's not listed,
+check the source. Links to the <a href="/doxygen/">doxygen</a> sources
+are provided to make this as easy as possible.</p>
-The first section of this document describes general information that is useful
-to know when working in the LLVM infrastructure, and the second describes the
-Core LLVM classes. In the future this manual will be extended with information
-describing how to use extension libraries, such as dominator information, CFG
-traversal routines, and useful utilities like the <tt><a
-href="/doxygen/InstVisitor_8h-source.html">InstVisitor</a></tt> template.<p>
+<p>The first section of this document describes general information that is
+useful to know when working in the LLVM infrastructure, and the second describes
+the Core LLVM classes. In the future this manual will be extended with
+information describing how to use extension libraries, such as dominator
+
information, CFG traversal routines, and useful utilities like the <tt><a
+href="/doxygen/InstVisitor_8h-source.html">InstVisitor</a></tt> template.</p>
+</div>
<!-- *********************************************************************** -->
-</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
-<a name="general">General Information
-</b></font></td></tr></table><ul>
+<div class="doc_section">
+ <a name="general">General Information</a>
+</div>
<!-- *********************************************************************** -->
-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 class="doc_text">
+<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>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="stl">The C++ Standard Template Library</a>
-</b></font></td></tr></table><ul>
-
-LLVM makes heavy use of the C++ Standard Template Library (STL), perhaps much
-more than you are used to, or have seen before. Because of this, you might want
-to do a little background reading in the techniques used and capabilities of the
-library. There are many good pages that discuss the STL, and several books on
-the subject that you can get, so it will not be discussed in this document.<p>
-
-Here are some useful links:<p>
+<div class="doc_subsection">
+ <a name="stl">The C++ Standard Template Library</a>
+</div>
+
+<div class="doc_text">
+
+<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
+this, you might want to do a little background reading in the
+techniques used and capabilities of the library. There are many good
+pages that discuss the STL, and several books on the subject that you
+can get, so it will not be discussed in this document.</p>
+
+<p>Here are some useful links:</p>
+
<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><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.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an
-O'Reilly book in the making. It has a decent <a
-href="http://www.tempest-sw.com/cpp/ch13-libref.html">Standard Library
-Reference</a> that rivals Dinkumware's, and is actually free until the book is
-published.
+O'Reilly book in the making. It has a decent
+Standard Library
+Reference that rivals Dinkumware's, and is unfortunately no longer free since the book has been
+published.</li>
<li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked
-Questions</a>
+Questions</a></li>
<li><a href="http://www.sgi.com/tech/stl/">SGI's STL Programmer's Guide</a> -
Contains a useful <a
href="http://www.sgi.com/tech/stl/stl_introduction.html">Introduction to the
-STL</a>.
+STL</a>.</li>
-<li><a href="http://www.research.att.com/~bs/C++.html">Bjarne Stroustrup's C++
-Page</a>
+<li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++
+Page</a></li>
-</ol><p>
+<li><a href="http://64.78.49.204/">
+Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get
+the book).</a></li>
-You are also encouraged to take a look at the <a
+</ol>
+
+<p>You are also encouraged to take a look at the <a
href="CodingStandards.html">LLVM Coding Standards</a> guide which focuses on how
-to write maintainable code more than where to put your curly braces.<p>
+to write maintainable code more than where to put your curly braces.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="stl">Other useful references</a>
+</div>
+
+<div class="doc_text">
+<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>
<!-- *********************************************************************** -->
-</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
-<a name="apis">Important and useful LLVM APIs
-</b></font></td></tr></table><ul>
+<div class="doc_section">
+ <a name="apis">Important and useful LLVM APIs</a>
+</div>
<!-- *********************************************************************** -->
-Here we highlight some LLVM APIs that are generally useful and good to know
-about when writing transformations.<p>
+<div class="doc_text">
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="isa">The isa<>, cast<> and dyn_cast<> templates</a>
-</b></font></td></tr></table><ul>
-
-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>
-operator, but they don't have some drawbacks (primarily stemming from the fact
-that <tt>dynamic_cast<></tt> only works on classes that have a v-table).
-Because they are used so often, you must know what they do and how they work.
-All of these templates are defined in the <a
-href="/doxygen/Casting_8h-source.html"><tt>Support/Casting.h</tt></a> file (note
-that you very rarely have to include this file directly).<p>
+<p>Here we highlight some LLVM APIs that are generally useful and good to
+know about when writing transformations.</p>
-<dl>
+</div>
-<dt><tt>isa<></tt>:
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="isa">The <tt>isa<></tt>, <tt>cast<></tt> and
+ <tt>dyn_cast<></tt> templates</a>
+</div>
+
+<div class="doc_text">
+
+<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>
+operator, but they don't have some drawbacks (primarily stemming from
+the fact that <tt>dynamic_cast<></tt> only works on classes that
+have a v-table). Because they are used so often, you must know what they
+do and how they work. All of these templates are defined in the <a
+ href="/doxygen/Casting_8h-source.html"><tt>llvm/Support/Casting.h</tt></a>
+file (note that you very rarely have to include this file directly).</p>
-<dd>The <tt>isa<></tt> operator works exactly like the Java
-"<tt>instanceof</tt>" operator. It returns true or false depending on whether a
-reference or pointer points to an instance of the specified class. This can be
-very useful for constraint checking of various sorts (example below).<p>
+<dl>
+ <dt><tt>isa<></tt>: </dt>
+ <dd><p>The <tt>isa<></tt> operator works exactly like the Java
+ "<tt>instanceof</tt>" operator. It returns true or false depending on whether
+ a reference or pointer points to an instance of the specified class. This can
+ be very useful for constraint checking of various sorts (example below).</p>
+ </dd>
-<dt><tt>cast<></tt>:
+ <dt><tt>cast<></tt>: </dt>
-<dd>The <tt>cast<></tt> operator is a "checked cast" operation. It
-converts a pointer or reference from a base class to a derived cast, causing an
-assertion failure if it is not really an instance of the right type. This
-should be used in cases where you have some information that makes you believe
-that something is of the right type. An example of the <tt>isa<></tt> and
-<tt>cast<></tt> template is:<p>
+ <dd><p>The <tt>cast<></tt> operator is a "checked cast" operation. It
+ converts a pointer or reference from a base class to a derived cast, causing
+ an assertion failure if it is not really an instance of the right type. This
+ should be used in cases where you have some information that makes you believe
+ that something is of the right type. An example of the <tt>isa<></tt>
+ and <tt>cast<></tt> template is:</p>
+<div class="doc_code">
<pre>
static bool isLoopInvariant(const <a href="#Value">Value</a> *V, const Loop *L) {
if (isa<<a href="#Constant">Constant</a>>(V) || isa<<a href="#Argument">Argument</a>>(V) || isa<<a href="#GlobalValue">GlobalValue</a>>(V))
return true;
- <i>// Otherwise, it must be an instruction...</i>
- return !L->contains(cast<<a href="#Instruction">Instruction</a>>(V)->getParent());
-</pre><p>
-
-Note that you should <b>not</b> use an <tt>isa<></tt> test followed by a
-<tt>cast<></tt>, for that use the <tt>dyn_cast<></tt> operator.<p>
-
-
-<dt><tt>dyn_cast<></tt>:
+ // <i>Otherwise, it must be an instruction...</i>
+ return !L->contains(cast<<a href="#Instruction">Instruction</a>>(V)->getParent());
+}
+</pre>
+</div>
-<dd>The <tt>dyn_cast<></tt> operator is a "checking cast" operation. It
-checks to see if the operand is of the specified type, and if so, returns a
-pointer to it (this operator does not work with references). If the operand is
-not of the correct type, a null pointer is returned. Thus, this works very much
-like the <tt>dynamic_cast</tt> operator in C++, and should be used in the same
-circumstances. Typically, the <tt>dyn_cast<></tt> operator is used in an
-<tt>if</tt> statement or some other flow control statement like this:<p>
+ <p>Note that you should <b>not</b> use an <tt>isa<></tt> test followed
+ by a <tt>cast<></tt>, for that use the <tt>dyn_cast<></tt>
+ operator.</p>
-<pre>
- if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast<<a href="#AllocationInst">AllocationInst</a>>(Val)) {
- ...
- }
-</pre><p>
+ </dd>
-This form of the <tt>if</tt> statement effectively combines together a call to
-<tt>isa<></tt> and a call to <tt>cast<></tt> into one statement,
-which is very convenient.<p>
+ <dt><tt>dyn_cast<></tt>:</dt>
-Another common example is:<p>
+ <dd><p>The <tt>dyn_cast<></tt> operator is a "checking cast" operation.
+ It checks to see if the operand is of the specified type, and if so, returns a
+ pointer to it (this operator does not work with references). If the operand is
+ not of the correct type, a null pointer is returned. Thus, this works very
+ much like the <tt>dynamic_cast<></tt> operator in C++, and should be
+ used in the same circumstances. Typically, the <tt>dyn_cast<></tt>
+ operator is used in an <tt>if</tt> statement or some other flow control
+ statement like this:</p>
+<div class="doc_code">
<pre>
- <i>// Loop over all of the phi nodes in a basic block</i>
- BasicBlock::iterator BBI = BB->begin();
- for (; <a href="#PhiNode">PHINode</a> *PN = dyn_cast<<a href="#PHINode">PHINode</a>>(BBI); ++BBI)
- cerr << *PN;
-</pre><p>
-
-Note that the <tt>dyn_cast<></tt> operator, like C++'s
-<tt>dynamic_cast</tt> or Java's <tt>instanceof</tt> operator, can be abused. In
-particular you should not use big chained <tt>if/then/else</tt> blocks to check
-for lots of different variants of classes. If you find yourself wanting to do
-this, it is much cleaner and more efficient to use the InstVisitor class to
-dispatch over the instruction type directly.<p>
+if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast<<a href="#AllocationInst">AllocationInst</a>>(Val)) {
+ // <i>...</i>
+}
+</pre>
+</div>
+
+ <p>This form of the <tt>if</tt> statement effectively combines together a call
+ to <tt>isa<></tt> and a call to <tt>cast<></tt> into one
+ statement, which is very convenient.</p>
+
+ <p>Note that the <tt>dyn_cast<></tt> operator, like C++'s
+ <tt>dynamic_cast<></tt> or Java's <tt>instanceof</tt> operator, can be
+ abused. In particular, you should not use big chained <tt>if/then/else</tt>
+ blocks to check for lots of different variants of classes. If you find
+ yourself wanting to do this, it is much cleaner and more efficient to use the
+ <tt>InstVisitor</tt> class to dispatch over the instruction type directly.</p>
+
+ </dd>
+
+ <dt><tt>cast_or_null<></tt>: </dt>
+
+ <dd><p>The <tt>cast_or_null<></tt> operator works just like the
+ <tt>cast<></tt> operator, except that it allows for a null pointer as an
+ argument (which it then propagates). This can sometimes be useful, allowing
+ you to combine several null checks into one.</p></dd>
+ <dt><tt>dyn_cast_or_null<></tt>: </dt>
-<dt><tt>cast_or_null<></tt>:
+ <dd><p>The <tt>dyn_cast_or_null<></tt> operator works just like the
+ <tt>dyn_cast<></tt> operator, except that it allows for a null pointer
+ as an argument (which it then propagates). This can sometimes be useful,
+ allowing you to combine several null checks into one.</p></dd>
-<dd>The <tt>cast_or_null<></tt> operator works just like the
-<tt>cast<></tt> operator, except that it allows for a null pointer as an
-argument (which it then propagates). This can sometimes be useful, allowing you
-to combine several null checks into one.<p>
+</dl>
+<p>These five templates can be used with any classes, whether they have a
+v-table or not. To add support for these templates, you simply need to add
+<tt>classof</tt> static methods to the class you are interested casting
+to. Describing this is currently outside the scope of this document, but there
+are lots of examples in the LLVM source base.</p>
-<dt><tt>dyn_cast_or_null<></tt>:
+</div>
-<dd>The <tt>dyn_cast_or_null<></tt> operator works just like the
-<tt>dyn_cast<></tt> operator, except that it allows for a null pointer as
-an argument (which it then propagates). This can sometimes be useful, allowing
-you to combine several null checks into one.<p>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
+</div>
-</dl>
+<div class="doc_text">
-These five templates can be used with any classes, whether they have a v-table
-or not. To add support for these templates, you simply need to add
-<tt>classof</tt> static methods to the class you are interested casting to.
-Describing this is currently outside the scope of this document, but there are
-lots of examples in the LLVM source base.<p>
+<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
+it, but you may need it again in the future (to work out new bugs that you run
+across).</p>
+<p> Naturally, because of this, you don't want to delete the debug printouts,
+but you don't want them to always be noisy. A standard compromise is to comment
+them out, allowing you to enable them if you need them in the future.</p>
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="DEBUG">The <tt>DEBUG()</tt> macro & <tt>-debug</tt> option</a>
-</b></font></td></tr></table><ul>
-
-Often when working on your pass you will put a bunch of debugging printouts and
-other code into your pass. After you get it working, you want to remove
-it... but you may need it again in the future (to work out new bugs that you run
-across).<p>
-
-Naturally, because of this, you don't want to delete the debug printouts, but
-you don't want them to always be noisy. A standard compromise is to comment
-them out, allowing you to enable them if you need them in the future.<p>
-
-The "<tt><a href="/doxygen/Debug_8h-source.html">Support/Debug.h</a></tt>" file
-provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to this
-problem. Basically, you can put arbitrary code into the argument of the
+<p>The "<tt><a href="/doxygen/Debug_8h-source.html">llvm/Support/Debug.h</a></tt>"
+file provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to
+this problem. Basically, you can put arbitrary code into the argument of the
<tt>DEBUG</tt> macro, and it is only executed if '<tt>opt</tt>' (or any other
-tool) is run with the '<tt>-debug</tt>' command line argument:
+tool) is run with the '<tt>-debug</tt>' command line argument:</p>
+<div class="doc_code">
<pre>
- ...
- DEBUG(std::cerr << "I am here!\n");
- ...
-</pre><p>
+DOUT << "I am here!\n";
+</pre>
+</div>
-Then you can run your pass like this:<p>
+<p>Then you can run your pass like this:</p>
+<div class="doc_code">
<pre>
- $ opt < a.bc > /dev/null -mypass
- <no output>
- $ opt < a.bc > /dev/null -mypass -debug
- I am here!
- $
-</pre><p>
-
-Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you to
-now have to create "yet another" command line option for the debug output for
+$ opt < a.bc > /dev/null -mypass
+<i><no output></i>
+$ opt < a.bc > /dev/null -mypass -debug
+I am here!
+</pre>
+</div>
+
+<p>Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you
+to not have to create "yet another" command line option for the debug output for
your pass. Note that <tt>DEBUG()</tt> macros are disabled for optimized builds,
so they do not cause a performance impact at all (for the same reason, they
-should also not contain side-effects!).<p>
+should also not contain side-effects!).</p>
-One additional nice thing about the <tt>DEBUG()</tt> macro is that you can
+<p>One additional nice thing about the <tt>DEBUG()</tt> macro is that you can
enable or disable it directly in gdb. Just use "<tt>set DebugFlag=0</tt>" or
"<tt>set DebugFlag=1</tt>" from the gdb if the program is running. If the
program hasn't been started yet, you can always just run it with
-<tt>-debug</tt>.<p>
+<tt>-debug</tt>.</p>
+
+</div>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="DEBUG_TYPE"><hr size=0>Fine grained debug info with
- <tt>DEBUG_TYPE()</tt> and the <tt>-debug-only</tt> option</a> </h4><ul>
+<div class="doc_subsubsection">
+ <a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and
+ the <tt>-debug-only</tt> option</a>
+</div>
-Sometimes you may find yourself in a situation where enabling <tt>-debug</tt>
+<div class="doc_text">
+
+<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
generator). If you want to enable debug information with more fine-grained
control, you define the <tt>DEBUG_TYPE</tt> macro and the <tt>-debug</tt> only
-option as follows:<p>
+option as follows:</p>
+<div class="doc_code">
<pre>
- ...
- DEBUG(std::cerr << "No debug type\n");
- #undef DEBUG_TYPE
- #define DEBUG_TYPE "foo"
- DEBUG(std::cerr << "'foo' debug type\n");
- #undef DEBUG_TYPE
- #define DEBUG_TYPE "bar"
- DEBUG(std::cerr << "'bar' debug type\n");
- #undef DEBUG_TYPE
- #define DEBUG_TYPE ""
- DEBUG(std::cerr << "No debug type (2)\n");
- ...
-</pre><p>
-
-Then you can run your pass like this:<p>
+DOUT << "No debug type\n";
+#undef DEBUG_TYPE
+#define DEBUG_TYPE "foo"
+DOUT << "'foo' debug type\n";
+#undef DEBUG_TYPE
+#define DEBUG_TYPE "bar"
+DOUT << "'bar' debug type\n";
+#undef DEBUG_TYPE
+#define DEBUG_TYPE ""
+DOUT << "No debug type (2)\n";
+</pre>
+</div>
+<p>Then you can run your pass like this:</p>
+
+<div class="doc_code">
<pre>
- $ opt < a.bc > /dev/null -mypass
- <no output>
- $ opt < a.bc > /dev/null -mypass -debug
- No debug type
- 'foo' debug type
- 'bar' debug type
- No debug type (2)
- $ opt < a.bc > /dev/null -mypass -debug-only=foo
- 'foo' debug type
- $ opt < a.bc > /dev/null -mypass -debug-only=bar
- 'bar' debug type
- $
-</pre><p>
-
-Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of a
-file, to specify the debug type for the entire module (if you do this before you
-<tt>#include "Support/Debug.h"</tt>, you don't have to insert the ugly
-<tt>#undef</tt>'s). Also, you should use names more meaningful that "foo" and
-"bar", because there is no system in place to ensure that names do not conflict:
-if two different modules use the same string, they will all be turned on when
-the name is specified. This allows all, say, instruction scheduling, debug
-information to be enabled with <tt>-debug-type=InstrSched</tt>, even if the
-source lives in multiple files.<p>
+$ opt < a.bc > /dev/null -mypass
+<i><no output></i>
+$ opt < a.bc > /dev/null -mypass -debug
+No debug type
+'foo' debug type
+'bar' debug type
+No debug type (2)
+$ opt < a.bc > /dev/null -mypass -debug-only=foo
+'foo' debug type
+$ opt < a.bc > /dev/null -mypass -debug-only=bar
+'bar' debug type
+</pre>
+</div>
+<p>Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of
+a file, to specify the debug type for the entire module (if you do this before
+you <tt>#include "llvm/Support/Debug.h"</tt>, you don't have to insert the ugly
+<tt>#undef</tt>'s). Also, you should use names more meaningful than "foo" and
+"bar", because there is no system in place to ensure that names do not
+conflict. If two different modules use the same string, they will all be turned
+on when the name is specified. This allows, for example, all debug information
+for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>,
+even if the source lives in multiple files.</p>
+
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Statistic">The <tt>Statistic</tt> template & <tt>-stats</tt>
-option</a>
-</b></font></td></tr></table><ul>
+<div class="doc_subsection">
+ <a name="Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt>
+ option</a>
+</div>
-The "<tt><a
-href="/doxygen/Statistic_8h-source.html">Support/Statistic.h</a></tt>"
-file provides a template named <tt>Statistic</tt> that is used as a unified way
-to keeping track of what the LLVM compiler is doing and how effective various
+<div class="doc_text">
+
+<p>The "<tt><a
+href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file
+provides a class named <tt>Statistic</tt> that is used as a unified way to
+keep track of what the LLVM compiler is doing and how effective various
optimizations are. It is useful to see what optimizations are contributing to
-making a particular program run faster.<p>
+making a particular program run faster.</p>
-Often you may run your pass on some big program, and you're interested to see
+<p>Often you may run your pass on some big program, and you're interested to see
how many times it makes a certain transformation. Although you can do this with
hand inspection, or some ad-hoc method, this is a real pain and not very useful
-for big programs. Using the <tt>Statistic</tt> template makes it very easy to
+for big programs. Using the <tt>Statistic</tt> class makes it very easy to
keep track of this information, and the calculated information is presented in a
-uniform manner with the rest of the passes being executed.<p>
+uniform manner with the rest of the passes being executed.</p>
-There are many examples of <tt>Statistic</tt> users, but this basics of using it
-are as follows:<p>
+<p>There are many examples of <tt>Statistic</tt> uses, but the basics of using
+it are as follows:</p>
<ol>
-<li>Define your statistic like this:<p>
+ <li><p>Define your statistic like this:</p>
+<div class="doc_code">
<pre>
-static Statistic<> NumXForms("mypassname", "The # of times I did stuff");
-</pre><p>
+#define <a href="#DEBUG_TYPE">DEBUG_TYPE</a> "mypassname" <i>// This goes before any #includes.</i>
+STATISTIC(NumXForms, "The # of times I did stuff");
+</pre>
+</div>
-The <tt>Statistic</tt> template can emulate just about any data-type, but if you
-do not specify a template argument, it defaults to acting like an unsigned int
-counter (this is usually what you want).<p>
+ <p>The <tt>STATISTIC</tt> macro defines a static variable, whose name is
+ specified by the first argument. The pass name is taken from the DEBUG_TYPE
+ macro, and the description is taken from the second argument. The variable
+ defined ("NumXForms" in this case) acts like an unsigned integer.</p></li>
-<li>Whenever you make a transformation, bump the counter:<p>
+ <li><p>Whenever you make a transformation, bump the counter:</p>
+<div class="doc_code">
<pre>
- ++NumXForms; // I did stuff
-</pre><p>
+++NumXForms; // <i>I did stuff!</i>
+</pre>
+</div>
-</ol><p>
+ </li>
+ </ol>
-That's all you have to do. To get '<tt>opt</tt>' to print out the statistics
-gathered, use the '<tt>-stats</tt>' option:<p>
+ <p>That's all you have to do. To get '<tt>opt</tt>' to print out the
+ statistics gathered, use the '<tt>-stats</tt>' option:</p>
+<div class="doc_code">
<pre>
- $ opt -stats -mypassname < program.bc > /dev/null
- ... statistic output ...
-</pre><p>
+$ opt -stats -mypassname < program.bc > /dev/null
+<i>... statistics output ...</i>
+</pre>
+</div>
-When running <tt>gccas</tt> on a C file from the SPEC benchmark suite, it gives
-a report that looks like this:<p>
+ <p> When running <tt>opt</tt> on a C file from the SPEC benchmark
+suite, it gives a report that looks like this:</p>
+<div class="doc_code">
<pre>
- 7646 bytecodewriter - Number of normal instructions
- 725 bytecodewriter - Number of oversized instructions
- 129996 bytecodewriter - Number of bytecode bytes written
+ 7646 bitcodewriter - Number of normal instructions
+ 725 bitcodewriter - Number of oversized instructions
+ 129996 bitcodewriter - Number of bitcode bytes written
2817 raise - Number of insts DCEd or constprop'd
3213 raise - Number of cast-of-self removed
5046 raise - Number of expression trees converted
49 cee - Number of setcc instruction eliminated
532 gcse - Number of loads removed
2919 gcse - Number of instructions removed
- 86 indvars - Number of cannonical indvars added
+ 86 indvars - Number of canonical indvars added
87 indvars - Number of aux indvars removed
25 instcombine - Number of dead inst eliminate
434 instcombine - Number of insts combined
3 licm - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
75 mem2reg - Number of alloca's promoted
1444 cfgsimplify - Number of blocks simplified
-</pre><p>
-
-Obviously, with so many optimizations, having a unified framework for this stuff
-is very nice. Making your pass fit well into the framework makes it more
-maintainable and useful.<p>
-
+</pre>
+</div>
-<!-- *********************************************************************** -->
-</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
-<a name="common">Helpful Hints for Common Operations
-</b></font></td></tr></table><ul> <!--
-*********************************************************************** -->
+<p>Obviously, with so many optimizations, having a unified framework for this
+stuff is very nice. Making your pass fit well into the framework makes it more
+maintainable and useful.</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
-practical side of LLVM transformations.<p>
+</div>
-Because this is a "how-to" section, you should also read about the main classes
-that you will be working with. 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 class="doc_subsection">
+ <a name="ViewGraph">Viewing graphs while debugging code</a>
+</div>
+
+<div class="doc_text">
+
+<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
+LLVM <a href="CodeGenerator.html#machinebasicblock">MachineBasicBlock</a>s, and
+<a href="CodeGenerator.html#selectiondag_intro">Instruction Selection
+DAGs</a>. In many cases, while debugging various parts of the compiler, it is
+nice to instantly visualize these graphs.</p>
+
+<p>LLVM provides several callbacks that are available in a debug build to do
+exactly that. If you call the <tt>Function::viewCFG()</tt> method, for example,
+the current LLVM tool will pop up a window containing the CFG for the function
+where each basic block is a node in the graph, and each node contains the
+instructions in the block. Similarly, there also exists
+<tt>Function::viewCFGOnly()</tt> (does not include the instructions), the
+<tt>MachineFunction::viewCFG()</tt> and <tt>MachineFunction::viewCFGOnly()</tt>,
+and the <tt>SelectionDAG::viewGraph()</tt> methods. Within GDB, for example,
+you can usually use something like <tt>call DAG.viewGraph()</tt> to pop
+up a window. Alternatively, you can sprinkle calls to these functions in your
+code in places you want to debug.</p>
+
+<p>Getting this to work requires a small amount of configuration. On Unix
+systems with X11, install the <a href="http://www.graphviz.org">graphviz</a>
+toolkit, and make sure 'dot' and 'gv' are in your path. If you are running on
+Mac OS/X, download and install the Mac OS/X <a
+href="http://www.pixelglow.com/graphviz/">Graphviz program</a>, and add
+<tt>/Applications/Graphviz.app/Contents/MacOS/</tt> (or wherever you install
+it) to your path. Once in your system and path are set up, rerun the LLVM
+configure script and rebuild LLVM to enable this functionality.</p>
+
+<p><tt>SelectionDAG</tt> has been extended to make it easier to locate
+<i>interesting</i> nodes in large complex graphs. From gdb, if you
+<tt>call DAG.setGraphColor(<i>node</i>, "<i>color</i>")</tt>, then the
+next <tt>call DAG.viewGraph()</tt> would highlight the node in the
+specified color (choices of colors can be found at <a
+href="http://www.graphviz.org/doc/info/colors.html">colors</a>.) More
+complex node attributes can be provided with <tt>call
+DAG.setGraphAttrs(<i>node</i>, "<i>attributes</i>")</tt> (choices can be
+found at <a href="http://www.graphviz.org/doc/info/attrs.html">Graph
+Attributes</a>.) If you want to restart and clear all the current graph
+attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p>
+
+</div>
-<!-- NOTE: this section should be heavy on example code -->
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="datastructure">Picking the Right Data Structure for a Task</a>
+</div>
+<!-- *********************************************************************** -->
+<div class="doc_text">
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="inspection">Basic Inspection and Traversal Routines</a>
-</b></font></td></tr></table><ul>
-
-The LLVM compiler infrastructure have many different data structures that may be
-traversed. Following the example of the C++ standard template library, the
-techniques used to traverse these various data structures are all basically the
-same. For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or
-method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt>
-function returns an iterator pointing to one past the last valid element of the
-sequence, and there is some <tt>XXXiterator</tt> data type that is common
-between the two operations.<p>
+<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
+ you should consider when you pick one.</p>
-Because the pattern for iteration is common across many different aspects of the
-program representation, the standard template library algorithms may be used on
-them, and it is easier to remember how to iterate. First we show a few common
-examples of the data structures that need to be traversed. Other data
-structures are traversed in very similar ways.<p>
+<p>
+The first step is a choose your own adventure: do you want a sequential
+container, a set-like container, or a map-like container? The most important
+thing when choosing a container is the algorithmic properties of how you plan to
+access the container. Based on that, you should use:</p>
+<ul>
+<li>a <a href="#ds_map">map-like</a> container if you need efficient look-up
+ of an value based on another value. Map-like containers also support
+ efficient queries for containment (whether a key is in the map). Map-like
+ containers generally do not support efficient reverse mapping (values to
+ keys). If you need that, use two maps. Some map-like containers also
+ support efficient iteration through the keys in sorted order. Map-like
+ containers are the most expensive sort, only use them if you need one of
+ these capabilities.</li>
+
+<li>a <a href="#ds_set">set-like</a> container if you need to put a bunch of
+ stuff into a container that automatically eliminates duplicates. Some
+ set-like containers support efficient iteration through the elements in
+ sorted order. Set-like containers are more expensive than sequential
+ containers.
+</li>
+
+<li>a <a href="#ds_sequential">sequential</a> container provides
+ the most efficient way to add elements and keeps track of the order they are
+ added to the collection. They permit duplicates and support efficient
+ iteration, but do not support efficient look-up based on a key.
+</li>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="iterate_function"><hr size=0>Iterating over the <a
-href="#BasicBlock"><tt>BasicBlock</tt></a>s in a <a
-href="#Function"><tt>Function</tt></a> </h4><ul>
-
-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
-<tt>BasicBlock</tt>s. To facilitate this, you'll need to iterate over
-all of the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>.
-The following is an example that prints the name of a
-<tt>BasicBlock</tt> and the number of <tt>Instruction</tt>s it
-contains:
+</ul>
-<pre>
- // func is a pointer to a Function instance
- for(Function::iterator i = func->begin(), e = func->end(); i != e; ++i) {
+<p>
+Once the proper category of container is determined, you can fine tune the
+memory use, constant factors, and cache behaviors of access by intelligently
+picking a member of the category. Note that constant factors and cache behavior
+can be a big deal. If you have a vector that usually only contains a few
+elements (but could contain many), for example, it's much better to use
+<a href="#dss_smallvector">SmallVector</a> than <a href="#dss_vector">vector</a>
+. Doing so avoids (relatively) expensive malloc/free calls, which dwarf the
+cost of adding the elements to the container. </p>
- // print out the name of the basic block if it has one, and then the
- // number of instructions that it contains
+</div>
- cerr << "Basic block (name=" << i->getName() << ") has "
- << i->size() << " instructions.\n";
- }
-</pre>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
+</div>
-Note that i can be used as if it were a pointer for the purposes of
-invoking member functions of the <tt>Instruction</tt> class. This is
-because the indirection operator is overloaded for the iterator
-classes. In the above code, the expression <tt>i->size()</tt> is
-exactly equivalent to <tt>(*i).size()</tt> just like you'd expect.
+<div class="doc_text">
+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.
+</div>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="iterate_basicblock"><hr size=0>Iterating over the <a
-href="#Instruction"><tt>Instruction</tt></a>s in a <a
-href="#BasicBlock"><tt>BasicBlock</tt></a> </h4><ul>
+<div class="doc_subsubsection">
+ <a name="dss_fixedarrays">Fixed Size Arrays</a>
+</div>
-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 <tt>BasicBlock</tt>s. Here's a code snippet
-that prints out each instruction in a <tt>BasicBlock</tt>:
+<div class="doc_text">
+<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>
-<pre>
- // blk is a pointer to a BasicBlock instance
- for(BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i)
- // the next statement works since operator<<(ostream&,...)
- // is overloaded for Instruction&
- cerr << *i << "\n";
-</pre>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_heaparrays">Heap Allocated Arrays</a>
+</div>
+
+<div class="doc_text">
+<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,
+consider a <a href="#dss_smallvector">SmallVector</a>). The cost of a heap
+allocated array is the cost of the new/delete (aka malloc/free). Also note that
+if you are allocating an array of a type with a constructor, the constructor and
+destructors will be run for every element in the array (re-sizable vectors only
+construct those elements actually used).</p>
+</div>
-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>cerr << *blk <<
-"\n";</tt>.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a>
+</div>
+
+<div class="doc_text">
+<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
+do pointer arithmetic between elements), supports efficient push_back/pop_back
+operations, supports efficient random access to its elements, etc.</p>
+
+<p>The advantage of SmallVector is that it allocates space for
+some number of elements (N) <b>in the object itself</b>. Because of this, if
+the SmallVector is dynamically smaller than N, no malloc is performed. This can
+be a big win in cases where the malloc/free call is far more expensive than the
+code that fiddles around with the elements.</p>
+
+<p>This is good for vectors that are "usually small" (e.g. the number of
+predecessors/successors of a block is usually less than 8). On the other hand,
+this makes the size of the SmallVector itself large, so you don't want to
+allocate lots of them (doing so will waste a lot of space). As such,
+SmallVectors are most useful when on the stack.</p>
+
+<p>SmallVector also provides a nice portable and efficient replacement for
+<tt>alloca</tt>.</p>
+
+</div>
-Note that currently operator<< is implemented for <tt>Value*</tt>, so it
-will print out the contents of the pointer, instead of
-the pointer value you might expect. This is a deprecated interface that will
-be removed in the future, so it's best not to depend on it. To print out the
-pointer value for now, you must cast to <tt>void*</tt>.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_vector"><vector></a>
+</div>
+<div class="doc_text">
+<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
+rarely be a benefit) or if you will be allocating many instances of the vector
+itself (which would waste space for elements that aren't in the container).
+vector is also useful when interfacing with code that expects vectors :).
+</p>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="iterate_institer"><hr size=0>Iterating over the <a
-href="#Instruction"><tt>Instruction</tt></a>s in a <a
-href="#Function"><tt>Function</tt></a></h4><ul>
-
-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, <tt>InstIterator</tt> should be used instead.
-You'll need to include <a href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>, and then
-instantiate <tt>InstIterator</tt>s explicitly in your code. Here's a
-small example that shows how to dump all instructions in a function to
-stderr (<b>Note:</b> Dereferencing an <tt>InstIterator</tt> yields an
-<tt>Instruction*</tt>, <i>not</i> an <tt>Instruction&</tt>!):
+<p>One worthwhile note about std::vector: avoid code like this:</p>
+<div class="doc_code">
<pre>
-#include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"
-...
-// Suppose F is a ptr to a function
-for(inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)
- cerr << **i << "\n";
+for ( ... ) {
+ std::vector<foo> V;
+ use V;
+}
</pre>
+</div>
-Easy, isn't it? You can also use <tt>InstIterator</tt>s to fill a
-worklist with its initial contents. For example, if you wanted to
-initialize a worklist to contain all instructions in a
-<tt>Function</tt> F, all you would need to do is something like:
+<p>Instead, write this as:</p>
+<div class="doc_code">
<pre>
-std::set<Instruction*> worklist;
-worklist.insert(inst_begin(F), inst_end(F));
+std::vector<foo> V;
+for ( ... ) {
+ use V;
+ V.clear();
+}
</pre>
+</div>
-The STL set <tt>worklist</tt> would now contain all instructions in
-the <tt>Function</tt> pointed to by F.
+<p>Doing so will save (at least) one heap allocation and free per iteration of
+the loop.</p>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="iterate_convert"><hr size=0>Turning an iterator into a class
-pointer (and vice-versa) </h4><ul>
+</div>
-Sometimes, it'll be useful to grab a reference (or pointer) to a class
-instance when all you've got at hand is an iterator. Well, extracting
-a reference or a pointer from an iterator is very straightforward.
-Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and
-<tt>j</tt> is a <tt>BasicBlock::const_iterator</tt>:
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_deque"><deque></a>
+</div>
-<pre>
- Instruction& inst = *i; // grab reference to instruction reference
- Instruction* pinst = &*i; // grab pointer to instruction reference
- const Instruction& inst = *j;
-</pre>
-However, the iterators you'll be working with in the LLVM framework
-are special: they will automatically convert to a ptr-to-instance type
-whenever they need to. Instead of dereferencing the iterator and then
-taking the address of the result, you can simply assign the iterator
-to the proper pointer type and you get the dereference and address-of
-operation as a result of the assignment (behind the scenes, this is a
-result of overloading casting mechanisms). Thus the last line of the
-last example,
+<div class="doc_text">
+<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
+does not guarantee continuity of elements within memory.</p>
-<pre>Instruction* pinst = &*i;</pre>
+<p>In exchange for this extra flexibility, std::deque has significantly higher
+constant factor costs than std::vector. If possible, use std::vector or
+something cheaper.</p>
+</div>
-is semantically equivalent to
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_list"><list></a>
+</div>
+
+<div class="doc_text">
+<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
+also only supports bidirectional iteration, not random access iteration.</p>
+
+<p>In exchange for this high cost, std::list supports efficient access to both
+ends of the list (like std::deque, but unlike std::vector or SmallVector). In
+addition, the iterator invalidation characteristics of std::list are stronger
+than that of a vector class: inserting or removing an element into the list does
+not invalidate iterator or pointers to other elements in the list.</p>
+</div>
-<pre>Instruction* pinst = i;</pre>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_ilist">llvm/ADT/ilist</a>
+</div>
+
+<div class="doc_text">
+<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>
+
+<p>ilist has the same drawbacks as std::list, and additionally requires an
+ilist_traits implementation for the element type, but it provides some novel
+characteristics. In particular, it can efficiently store polymorphic objects,
+the traits class is informed when an element is inserted or removed from the
+list, and ilists are guaranteed to support a constant-time splice operation.
+</p>
-It's also possible to turn a class pointer into the corresponding
-iterator. Usually, this conversion is quite inexpensive. The
-following code snippet illustrates use of the conversion constructors
-provided by LLVM iterators. By using these, you can explicitly grab
-the iterator of something without actually obtaining it via iteration
-over some structure:
+<p>These properties are exactly what we want for things like Instructions and
+basic blocks, which is why these are implemented with ilists.</p>
+</div>
-<pre>
-void printNextInstruction(Instruction* inst) {
- BasicBlock::iterator it(inst);
- ++it; // after this line, it refers to the instruction after *inst.
- if(it != inst->getParent()->end()) cerr << *it << "\n";
-}
-</pre>
-Of course, this example is strictly pedagogical, because it'd be much
-better to explicitly grab the next instruction directly from inst.
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_other">Other Sequential Container options</a>
+</div>
+<div class="doc_text">
+<p>Other STL containers are available, such as std::string.</p>
-<!--_______________________________________________________________________-->
-</ul><h4><a name="iterate_complex"><hr size=0>Finding call sites: a slightly
-more complex example </h4><ul>
-
-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 certain function (i.e., some
-<tt>Function</tt>*) is already in scope. As you'll learn later, you may
-want to use an <tt>InstVisitor</tt> to accomplish this in a much more
-straightforward manner, but this example will allow us to explore how
-you'd do it if you didn't have <tt>InstVisitor</tt> around. In
-pseudocode, this is what we want to do:
+<p>There are also various STL adapter classes such as std::queue,
+std::priority_queue, std::stack, etc. These provide simplified access to an
+underlying container but don't affect the cost of the container itself.</p>
-<pre>
-initialize callCounter to zero
-for each Function f in the Module
- for each BasicBlock b in f
- for each Instruction i in b
- if(i is a CallInst and calls the given function)
- increment callCounter
-</pre>
+</div>
-And the actual code is (remember, since we're writing a
-<tt>FunctionPass</tt>, our <tt>FunctionPass</tt>-derived class simply
-has to override the <tt>runOnFunction</tt> method...):
-<pre>
-Function* targetFunc = ...;
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
+</div>
-class OurFunctionPass : public FunctionPass {
- public:
- OurFunctionPass(): callCounter(0) { }
+<div class="doc_text">
- virtual runOnFunction(Function& F) {
- for(Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
- for(BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) {
- if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a href="#CallInst">CallInst</a>>(&*i)) {
- // we know we've encountered a call instruction, so we
- // need to determine if it's a call to the
- // function pointed to by m_func or not.
-
- if(callInst->getCalledFunction() == targetFunc)
- ++callCounter;
- }
- }
- }
-
- private:
- unsigned callCounter;
-};
-</pre>
+<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>
-<!--_______________________________________________________________________-->
-</ul><h4><a name="iterate_chains"><hr size=0>Iterating over def-use &
-use-def chains</h4><ul>
-
-Frequently, we might have an instance of the <a
-href="/doxygen/classValue.html">Value Class</a> and we want to
-determine which <tt>User</tt>s use the <tt>Value</tt>. The list of
-all <tt>User</tt>s of a particular <tt>Value</tt> is called a
-<i>def-use</i> chain. For example, let's say we have a
-<tt>Function*</tt> named <tt>F</tt> to a particular function
-<tt>foo</tt>. Finding all of the instructions that <i>use</i>
-<tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain of
-<tt>F</tt>:
+</div>
-<pre>
-Function* F = ...;
-for(Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i) {
- if(Instruction* Inst = dyn_cast<Instruction>(*i)) {
- cerr << "F is used in instruction:\n";
- cerr << *Inst << "\n";
- }
-}
-</pre>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_sortedvectorset">A sorted 'vector'</a>
+</div>
-Alternately, it's common to have an instance of the <a
-href="/doxygen/classUser.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 <tt>Instruction</tt> are common <tt>User</tt>s, so we might want
-to iterate over all of the values that a particular instruction uses
-(that is, the operands of the particular <tt>Instruction</tt>):
+<div class="doc_text">
-<pre>
-Instruction* pi = ...;
+<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
+std::sort+std::unique to remove duplicates. This approach works really well if
+your usage pattern has these two distinct phases (insert then query), and can be
+coupled with a good choice of <a href="#ds_sequential">sequential container</a>.
+</p>
-for(User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
- Value* v = *i;
- ...
-}
-</pre>
-
+<p>
+This combination provides the several nice properties: the result data is
+contiguous in memory (good for cache locality), has few allocations, is easy to
+address (iterators in the final vector are just indices or pointers), and can be
+efficiently queried with a standard binary or radix search.</p>
-<!--
- 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]
--->
+</div>
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="simplechanges">Making simple changes</a>
-</b></font></td></tr></table><ul>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_smallset">"llvm/ADT/SmallSet.h"</a>
+</div>
-There are some primitive transformation operations present in the LLVM
-infrastructure that are worth knowing about. When performing
-transformations, it's fairly common to manipulate the contents of
-basic blocks. This section describes some of the common methods for
-doing so and gives example code.
+<div class="doc_text">
-<!--_______________________________________________________________________-->
-</ul><h4><a name="schanges_creating"><hr size=0>Creating and inserting
- new <tt>Instruction</tt>s</h4><ul>
+<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
+has space for N elements in place (thus, if the set is dynamically smaller than
+N, no malloc traffic is required) and accesses them with a simple linear search.
+When the set grows beyond 'N' elements, it allocates a more expensive representation that
+guarantees efficient access (for most types, it falls back to std::set, but for
+pointers it uses something far better, <a
+href="#dss_smallptrset">SmallPtrSet</a>).</p>
-<i>Instantiating Instructions</i>
+<p>The magic of this class is that it handles small sets extremely efficiently,
+but gracefully handles extremely large sets without loss of efficiency. The
+drawback is that the interface is quite small: it supports insertion, queries
+and erasing, but does not support iteration.</p>
-<p>Creation of <tt>Instruction</tt>s is straightforward: simply call the
-constructor for the kind of instruction to instantiate and provide the
-necessary parameters. For example, an <tt>AllocaInst</tt> only
-<i>requires</i> a (const-ptr-to) <tt>Type</tt>. Thus:
+</div>
-<pre>AllocaInst* ai = new AllocaInst(Type::IntTy);</pre>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a>
+</div>
-will create an <tt>AllocaInst</tt> instance that represents the
-allocation of one integer in the current stack frame, at runtime.
-Each <tt>Instruction</tt> subclass is likely to have varying default
-parameters which change the semantics of the instruction, so refer to
-the <a href="/doxygen/classInstruction.html">doxygen documentation for
-the subclass of Instruction</a> that you're interested in
-instantiating.</p>
+<div class="doc_text">
-<p><i>Naming values</i></p>
+<p>SmallPtrSet has all the advantages of SmallSet (and a SmallSet of pointers is
+transparently implemented with a SmallPtrSet), but also supports iterators. If
+more than 'N' insertions are performed, a single quadratically
+probed hash table is allocated and grows as needed, providing extremely
+efficient access (constant time insertion/deleting/queries with low constant
+factors) and is very stingy with malloc traffic.</p>
-<p>
-It is very useful to name the values of instructions when you're able
-to, as this facilitates the debugging of your transformations. If you
-end up looking at generated LLVM machine code, you definitely want to
-have logical names associated with the results of instructions! By
-supplying a value for the <tt>Name</tt> (default) parameter of the
-<tt>Instruction</tt> constructor, you associate a logical name with
-the result of the instruction's execution at runtime. For example,
-say that I'm writing a transformation that dynamically allocates space
-for an integer on the stack, and that integer is going to be used as
-some kind of index by some other code. To accomplish this, I place an
-<tt>AllocaInst</tt> at the first point in the first
-<tt>BasicBlock</tt> of some <tt>Function</tt>, and I'm intending to
-use it within the same <tt>Function</tt>. I might do:
-
-<pre>AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");</pre>
-
-where <tt>indexLoc</tt> is now the logical name of the instruction's
-execution value, which is a pointer to an integer on the runtime
-stack.
-</p>
+<p>Note that, unlike std::set, the iterators of SmallPtrSet are invalidated
+whenever an insertion occurs. Also, the values visited by the iterators are not
+visited in sorted order.</p>
-<p><i>Inserting instructions</i></p>
+</div>
-<p>
-There are essentially two ways to insert an <tt>Instruction</tt> into
-an existing sequence of instructions that form a <tt>BasicBlock</tt>:
-<ul>
-<li>Insertion into an explicit instruction list
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
+</div>
-<p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within
-that <tt>BasicBlock</tt>, and a newly-created instruction
-we wish to insert before <tt>*pi</tt>, we do the following:
+<div class="doc_text">
-<pre>
-BasicBlock* pb = ...;
-Instruction* pi = ...;
-Instruction* newInst = new Instruction(...);
-pb->getInstList().insert(pi, newInst); // inserts newInst before pi in pb
-</pre>
+<p>
+FoldingSet is an aggregate class that is really good at uniquing
+expensive-to-create or polymorphic objects. It is a combination of a chained
+hash table with intrusive links (uniqued objects are required to inherit from
+FoldingSetNode) that uses <a href="#dss_smallvector">SmallVector</a> as part of
+its ID process.</p>
+
+<p>Consider a case where you want to implement a "getOrCreateFoo" method for
+a complex object (for example, a node in the code generator). The client has a
+description of *what* it wants to generate (it knows the opcode and all the
+operands), but we don't want to 'new' a node, then try inserting it into a set
+only to find out it already exists, at which point we would have to delete it
+and return the node that already exists.
</p>
-<li>Insertion into an implicit instruction list
-<p><tt>Instruction</tt> instances that are already in
-<tt>BasicBlock</tt>s are implicitly associated with an existing
-instruction list: the instruction list of the enclosing basic block.
-Thus, we could have accomplished the same thing as the above code
-without being given a <tt>BasicBlock</tt> by doing:
-<pre>
-Instruction* pi = ...;
-Instruction* newInst = new Instruction(...);
-pi->getParent()->getInstList().insert(pi, newInst);
-</pre>
-In fact, this sequence of steps occurs so frequently that the
-<tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes
-provide constructors which take (as a default parameter) a pointer to
-an <tt>Instruction</tt> which the newly-created <tt>Instruction</tt>
-should precede. That is, <tt>Instruction</tt> constructors are
-capable of inserting the newly-created instance into the
-<tt>BasicBlock</tt> of a provided instruction, immediately before that
-instruction. Using an <tt>Instruction</tt> constructor with a
-<tt>insertBefore</tt> (default) parameter, the above code becomes:
-<pre>
-Instruction* pi = ...;
-Instruction* newInst = new Instruction(..., pi);
-</pre>
-which is much cleaner, especially if you're creating a lot of
-instructions and adding them to <tt>BasicBlock</tt>s.
- </p>
+<p>To support this style of client, FoldingSet perform a query with a
+FoldingSetNodeID (which wraps SmallVector) that can be used to describe the
+element that we want to query for. The query either returns the element
+matching the ID or it returns an opaque ID that indicates where insertion should
+take place. Construction of the ID usually does not require heap traffic.</p>
+
+<p>Because FoldingSet uses intrusive links, it can support polymorphic objects
+in the set (for example, you can have SDNode instances mixed with LoadSDNodes).
+Because the elements are individually allocated, pointers to the elements are
+stable: inserting or removing elements does not invalidate any pointers to other
+elements.
</p>
-</ul>
-
-<!--_______________________________________________________________________-->
-</ul><h4><a name="schanges_deleting"><hr size=0>Deleting
-<tt>Instruction</tt>s</h4><ul>
-Deleting an instruction from an existing sequence of instructions that form a <a
-href="#BasicBlock"><tt>BasicBlock</tt></a> is very straightforward. 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.<p>
+</div>
-For example:<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_set"><set></a>
+</div>
+
+<div class="doc_text">
+
+<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
+inserted (thus it is very malloc intensive) and typically stores three pointers
+per element in the set (thus adding a large amount of per-element space
+overhead). It offers guaranteed log(n) performance, which is not particularly
+fast from a complexity standpoint (particularly if the elements of the set are
+expensive to compare, like strings), and has extremely high constant factors for
+lookup, insertion and removal.</p>
+
+<p>The advantages of std::set are that its iterators are stable (deleting or
+inserting an element from the set does not affect iterators or pointers to other
+elements) and that iteration over the set is guaranteed to be in sorted order.
+If the elements in the set are large, then the relative overhead of the pointers
+and malloc traffic is not a big deal, but if the elements of the set are small,
+std::set is almost never a good choice.</p>
+
+</div>
-<pre>
- <a href="#Instruction">Instruction</a> *I = .. ;
- <a href="#BasicBlock">BasicBlock</a> *BB = I->getParent();
- BB->getInstList().erase(I);
-</pre><p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_setvector">"llvm/ADT/SetVector.h"</a>
+</div>
+
+<div class="doc_text">
+<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
+that this provides is efficient insertion with uniquing (duplicate elements are
+ignored) with iteration support. It implements this by inserting elements into
+both a set-like container and the sequential container, using the set-like
+container for uniquing and the sequential container for iteration.
+</p>
-<!--_______________________________________________________________________-->
-</ul><h4><a name="schanges_replacing"><hr size=0>Replacing an
- <tt>Instruction</tt> with another <tt>Value</tt></h4><ul>
+<p>The difference between SetVector and other sets is that the order of
+iteration is guaranteed to match the order of insertion into the SetVector.
+This property is really important for things like sets of pointers. Because
+pointer values are non-deterministic (e.g. vary across runs of the program on
+different machines), iterating over the pointers in the set will
+not be in a well-defined order.</p>
-<p><i>Replacing individual instructions</i></p>
<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>.
+The drawback of SetVector is that it requires twice as much space as a normal
+set and has the sum of constant factors from the set-like container and the
+sequential container that it uses. Use it *only* if you need to iterate over
+the elements in a deterministic order. SetVector is also expensive to delete
+elements out of (linear time), unless you use it's "pop_back" method, which is
+faster.
+</p>
-<ul>
+<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>
-<li><tt>ReplaceInstWithValue</tt>
+</div>
-<p>This function replaces all uses (within a basic block) of a given
-instruction with a value, and then removes the original instruction.
-The following example illustrates the replacement of the result of a
-particular <tt>AllocaInst</tt> that allocates memory for a single
-integer with an null pointer to an integer.</p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_uniquevector">"llvm/ADT/UniqueVector.h"</a>
+</div>
-<pre>
-AllocaInst* instToReplace = ...;
-BasicBlock::iterator ii(instToReplace);
-ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
- Constant::getNullValue(PointerType::get(Type::IntTy)));
-</pre>
+<div class="doc_text">
-<li><tt>ReplaceInstWithInst</tt>
+<p>
+UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it
+retains a unique ID for each element inserted into the set. It internally
+contains a map and a vector, and it assigns a unique ID for each value inserted
+into the set.</p>
-<p>This function replaces a particular instruction with another
-instruction. The following example illustrates the replacement of one
-<tt>AllocaInst</tt> with another.<p>
+<p>UniqueVector is very expensive: its cost is the sum of the cost of
+maintaining both the map and vector, it has high complexity, high constant
+factors, and produces a lot of malloc traffic. It should be avoided.</p>
-<pre>
-AllocaInst* instToReplace = ...;
-BasicBlock::iterator ii(instToReplace);
-ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
- new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt"));
-</pre>
+</div>
-</ul>
-<p><i>Replacing multiple uses of <tt>User</tt>s and
- <tt>Value</tt>s</i></p>
-
-You can use <tt>Value::replaceAllUsesWith</tt> and
-<tt>User::replaceUsesOfWith</tt> to change more than one use at a
-time. See the doxygen documentation for the <a
-href="/doxygen/classValue.html">Value Class</a> and <a
-href="/doxygen/classUser.html">User Class</a>, respectively, for more
-information.
-<!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out:
-include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with:
-ReplaceInstWithValue, ReplaceInstWithInst
--->
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_otherset">Other Set-Like Container Options</a>
+</div>
-<!-- *********************************************************************** -->
-</ul><table width="100%" bgcolor="#330077" border=0 cellpadding=4 cellspacing=0>
-<tr><td align=center><font color="#EEEEFF" size=+2 face="Georgia,Palatino"><b>
-<a name="coreclasses">The Core LLVM Class Hierarchy Reference
-</b></font></td></tr></table><ul>
-<!-- *********************************************************************** -->
+<div class="doc_text">
-The Core LLVM classes are the primary means of representing the program being
-inspected or transformed. The core LLVM classes are defined in header files in
-the <tt>include/llvm/</tt> directory, and implemented in the <tt>lib/VMCore</tt>
-directory.<p>
+<p>
+The STL provides several other options, such as std::multiset and the various
+"hash_set" like containers (whether from C++ TR1 or from the SGI library).</p>
+
+<p>std::multiset is useful if you're not interested in elimination of
+duplicates, but has all the drawbacks of std::set. A sorted vector (where you
+don't delete duplicate entries) or some other approach is almost always
+better.</p>
+<p>The various hash_set implementations (exposed portably by
+"llvm/ADT/hash_set") is a simple chained hashtable. This algorithm is as malloc
+intensive as std::set (performing an allocation for each element inserted,
+thus having really high constant factors) but (usually) provides O(1)
+insertion/deletion of elements. This can be useful if your elements are large
+(thus making the constant-factor cost relatively low) or if comparisons are
+expensive. Element iteration does not visit elements in a useful order.</p>
+
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Value">The <tt>Value</tt> class</a>
-</b></font></td></tr></table><ul>
+<div class="doc_subsection">
+ <a name="ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
+</div>
-<tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classValue.html">Value Class</a><p>
+<div class="doc_text">
+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">
+ <a name="dss_sortedvectormap">A sorted 'vector'</a>
+</div>
-The <tt>Value</tt> class is the most important class in LLVM Source base. It
-represents a typed value that may be used (among other things) as an operand to
-an instruction. There are many different types of <tt>Value</tt>s, such as <a
-href="#Constant"><tt>Constant</tt></a>s, <a
-href="#Argument"><tt>Argument</tt></a>s, and even <a
-href="#Instruction"><tt>Instruction</tt></a>s and <a
-href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.<p>
+<div class="doc_text">
-A particular <tt>Value</tt> may be used many times in the LLVM representation
-for a program. For example, an incoming argument to a function (represented
-with an instance of the <a href="#Argument">Argument</a> class) is "used" by
-every instruction in the function that references the argument. To keep track
-of this relationship, the <tt>Value</tt> class keeps a list of all of the <a
-href="#User"><tt>User</tt></a>s that is using it (the <a
-href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM
-graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents
-def-use information in the program, and is accessible through the <tt>use_</tt>*
-methods, shown below.<p>
+<p>
+If your usage pattern follows a strict insert-then-query approach, you can
+trivially use the same approach as <a href="#dss_sortedvectorset">sorted vectors
+for set-like containers</a>. The only difference is that your query function
+(which uses std::lower_bound to get efficient log(n) lookup) should only compare
+the key, not both the key and value. This yields the same advantages as sorted
+vectors for sets.
+</p>
+</div>
-Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed, and
-this <a href="#Type">Type</a> is available through the <tt>getType()</tt>
-method. <a name="#nameWarning">In addition, all LLVM values can be named. The
-"name" of the <tt>Value</tt> is symbolic string printed in the LLVM code:<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_stringmap">"llvm/ADT/StringMap.h"</a>
+</div>
-<pre>
- %<b>foo</b> = add int 1, 2
-</pre>
+<div class="doc_text">
-The name of this instruction is "foo". <b>NOTE</b> that the name of any value
-may be missing (an empty string), so names should <b>ONLY</b> be used for
-debugging (making the source code easier to read, debugging printouts), they
-should not be used to keep track of values or map between them. For this
-purpose, use a <tt>std::map</tt> of pointers to the <tt>Value</tt> itself
-instead.<p>
+<p>
+Strings are commonly used as keys in maps, and they are difficult to support
+efficiently: they are variable length, inefficient to hash and compare when
+long, expensive to copy, etc. StringMap is a specialized container designed to
+cope with these issues. It supports mapping an arbitrary range of bytes to an
+arbitrary other object.</p>
+
+<p>The StringMap implementation uses a quadratically-probed hash table, where
+the buckets store a pointer to the heap allocated entries (and some other
+stuff). The entries in the map must be heap allocated because the strings are
+variable length. The string data (key) and the element object (value) are
+stored in the same allocation with the string data immediately after the element
+object. This container guarantees the "<tt>(char*)(&Value+1)</tt>" points
+to the key string for a value.</p>
+
+<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
+memory for unrelated objects when looking up a value (even when hash collisions
+happen), hash table growth does not recompute the hash values for strings
+already in the table, and each pair in the map is store in a single allocation
+(the string data is stored in the same allocation as the Value of a pair).</p>
+
+<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>
+</div>
-One important aspect of LLVM is that there is no distinction between an SSA
-variable and the operation that produces it. Because of this, any reference to
-the value produced by an instruction (or the value available as an incoming
-argument, for example) is represented as a direct pointer to the class that
-represents this value. Although this may take some getting used to, it
-simplifies the representation and makes it easier to manipulate.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_indexedmap">"llvm/ADT/IndexedMap.h"</a>
+</div>
+
+<div class="doc_text">
+<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
+internally implemented as a vector with a mapping function that maps the keys to
+the dense integer range.
+</p>
+
+<p>
+This is useful for cases like virtual registers in the LLVM code generator: they
+have a dense mapping that is offset by a compile-time constant (the first
+virtual register ID).</p>
+</div>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Value"><hr size=0>Important Public Members of
-the <tt>Value</tt> class</h4><ul>
+<div class="doc_subsubsection">
+ <a name="dss_densemap">"llvm/ADT/DenseMap.h"</a>
+</div>
-<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 the use-list<br>
- <tt>unsigned use_size()</tt> - Returns the number of users of the value.<br>
- <tt>bool use_empty()</tt> - Returns true if there are no users.<br>
- <tt>use_iterator use_begin()</tt>
- - Get an iterator to the start of the use-list.<br>
- <tt>use_iterator use_end()</tt>
- - Get an iterator to the end of the use-list.<br>
- <tt><a href="#User">User</a> *use_back()</tt>
- - Returns the last element in the list.<p>
+<div class="doc_text">
+
+<p>
+DenseMap is a simple quadratically probed hash table. It excels at supporting
+small keys and values: it uses a single allocation to hold all of the pairs that
+are currently inserted in the map. DenseMap is a great way to map pointers to
+pointers, or map other small types to each other.
+</p>
+
+<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
+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
+DenseMapInfo for the key that you want, if it isn't already supported. This
+is required to tell DenseMap about two special marker values (which can never be
+inserted into the map) that it needs internally.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_map"><map></a>
+</div>
+
+<div class="doc_text">
+
+<p>
+std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses
+a single allocation per pair inserted into the map, it offers log(n) lookup with
+an extremely large constant factor, imposes a space penalty of 3 pointers per
+pair in the map, etc.</p>
+
+<p>std::map is most useful when your keys or values are very large, if you need
+to iterate over the collection in sorted order, or if you need stable iterators
+into the map (i.e. they don't get invalidated if an insertion or deletion of
+another element takes place).</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="dss_othermap">Other Map-Like Container Options</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+The STL provides several other options, such as std::multimap and the various
+"hash_map" like containers (whether from C++ TR1 or from the SGI library).</p>
+
+<p>std::multimap is useful if you want to map a key to multiple values, but has
+all the drawbacks of std::map. A sorted vector or some other approach is almost
+always better.</p>
+
+<p>The various hash_map implementations (exposed portably by
+"llvm/ADT/hash_map") are simple chained hash tables. This algorithm is as
+malloc intensive as std::map (performing an allocation for each element
+inserted, thus having really high constant factors) but (usually) provides O(1)
+insertion/deletion of elements. This can be useful if your elements are large
+(thus making the constant-factor cost relatively low) or if comparisons are
+expensive. Element iteration does not visit elements in a useful order.</p>
+
+</div>
+
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="common">Helpful Hints for Common Operations</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<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
+practical side of LLVM transformations. <p> Because this is a "how-to" section,
+you should also read about the main classes that you will be working with. 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">
+ <a name="inspection">Basic Inspection and Traversal Routines</a>
+</div>
+
+<div class="doc_text">
+
+<p>The LLVM compiler infrastructure have many different data structures that may
+be traversed. Following the example of the C++ standard template library, the
+techniques used to traverse these various data structures are all basically the
+same. For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or
+method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt>
+function returns an iterator pointing to one past the last valid element of the
+sequence, and there is some <tt>XXXiterator</tt> data type that is common
+between the two operations.</p>
+
+<p>Because the pattern for iteration is common across many different aspects of
+the program representation, the standard template library algorithms may be used
+on them, and it is easier to remember how to iterate. First we show a few common
+examples of the data structures that need to be traversed. Other data
+structures are traversed in very similar ways.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <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>
+
+<div class="doc_text">
+
+<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
+<tt>BasicBlock</tt>s. To facilitate this, you'll need to iterate over all of
+the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>. The following is
+an example that prints the name of a <tt>BasicBlock</tt> and the number of
+<tt>Instruction</tt>s it contains:</p>
+
+<div class="doc_code">
+<pre>
+// <i>func is a pointer to a Function instance</i>
+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 "
+ << i->size() << " instructions.\n";
+</pre>
+</div>
+
+<p>Note that i can be used as if it were a pointer for the purposes of
+invoking member functions of the <tt>Instruction</tt> class. This is
+because the indirection operator is overloaded for the iterator
+classes. In the above code, the expression <tt>i->size()</tt> is
+exactly equivalent to <tt>(*i).size()</tt> just like you'd expect.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <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>
+
+<div class="doc_text">
+
+<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
+<tt>BasicBlock</tt>s. Here's a code snippet that prints out each instruction in
+a <tt>BasicBlock</tt>:</p>
+
+<div class="doc_code">
+<pre>
+// <i>blk is a pointer to a BasicBlock instance</i>
+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";
+</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>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <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>
+
+<div class="doc_text">
+
+<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,
+<tt>InstIterator</tt> should be used instead. You'll need to include <a
+href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>,
+and then instantiate <tt>InstIterator</tt>s explicitly in your code. Here's a
+small example that shows how to dump all instructions in a function to the standard error stream:<p>
+
+<div class="doc_code">
+<pre>
+#include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"
+
+// <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";
+</pre>
+</div>
+
+<p>Easy, isn't it? You can also use <tt>InstIterator</tt>s to fill a
+work list with its initial contents. For example, if you wanted to
+initialize a work list to contain all instructions in a <tt>Function</tt>
+F, all you would need to do is something like:</p>
+
+<div class="doc_code">
+<pre>
+std::set<Instruction*> worklist;
+worklist.insert(inst_begin(F), inst_end(F));
+</pre>
+</div>
+
+<p>The STL set <tt>worklist</tt> would now contain all instructions in the
+<tt>Function</tt> pointed to by F.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="iterate_convert">Turning an iterator into a class pointer (and
+ vice-versa)</a>
+</div>
+
+<div class="doc_text">
+
+<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
+a reference or a pointer from an iterator is very straight-forward.
+Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and <tt>j</tt>
+is a <tt>BasicBlock::const_iterator</tt>:</p>
+
+<div class="doc_code">
+<pre>
+Instruction& inst = *i; // <i>Grab reference to instruction reference</i>
+Instruction* pinst = &*i; // <i>Grab pointer to instruction reference</i>
+const Instruction& inst = *j;
+</pre>
+</div>
+
+<p>However, the iterators you'll be working with in the LLVM framework are
+special: they will automatically convert to a ptr-to-instance type whenever they
+need to. Instead of dereferencing the iterator and then taking the address of
+the result, you can simply assign the iterator to the proper pointer type and
+you get the dereference and address-of operation as a result of the assignment
+(behind the scenes, this is a result of overloading casting mechanisms). Thus
+the last line of the last example,</p>
+
+<div class="doc_code">
+<pre>
+Instruction* pinst = &*i;
+</pre>
+</div>
+
+<p>is semantically equivalent to</p>
+
+<div class="doc_code">
+<pre>
+Instruction* pinst = i;
+</pre>
+</div>
+
+<p>It's also possible to turn a class pointer into the corresponding iterator,
+and this is a constant time operation (very efficient). The following code
+snippet illustrates use of the conversion constructors provided by LLVM
+iterators. By using these, you can explicitly grab the iterator of something
+without actually obtaining it via iteration over some structure:</p>
+
+<div class="doc_code">
+<pre>
+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";
+}
+</pre>
+</div>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="iterate_complex">Finding call sites: a slightly more complex
+ example</a>
+</div>
+
+<div class="doc_text">
+
+<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
+certain function (i.e., some <tt>Function</tt>*) is already in scope. As you'll
+learn later, you may want to use an <tt>InstVisitor</tt> to accomplish this in a
+much more straight-forward manner, but this example will allow us to explore how
+you'd do it if you didn't have <tt>InstVisitor</tt> around. In pseudo-code, this
+is what we want to do:</p>
+
+<div class="doc_code">
+<pre>
+initialize callCounter to zero
+for each Function f in the Module
+ for each BasicBlock b in f
+ for each Instruction i in b
+ if (i is a CallInst and calls the given function)
+ increment callCounter
+</pre>
+</div>
+
+<p>And the actual code is (remember, because we're writing a
+<tt>FunctionPass</tt>, our <tt>FunctionPass</tt>-derived class simply has to
+override the <tt>runOnFunction</tt> method):</p>
+
+<div class="doc_code">
+<pre>
+Function* targetFunc = ...;
+
+class OurFunctionPass : public FunctionPass {
+ public:
+ OurFunctionPass(): callCounter(0) { }
+
+ virtual runOnFunction(Function& F) {
+ for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
+ for (BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) {
+ if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a
+ href="#CallInst">CallInst</a>>(&*i)) {
+ // <i>We know we've encountered a call instruction, so we</i>
+ // <i>need to determine if it's a call to the</i>
+ // <i>function pointed to by m_func or not</i>
+
+ if (callInst->getCalledFunction() == targetFunc)
+ ++callCounter;
+ }
+ }
+ }
+ }
+
+ private:
+ unsigned callCounter;
+};
+</pre>
+</div>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="calls_and_invokes">Treating calls and invokes the same way</a>
+</div>
+
+<div class="doc_text">
+
+<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
+this, and in other situations, you may find that you want to treat
+<tt>CallInst</tt>s and <tt>InvokeInst</tt>s the same way, even though their
+most-specific common base class is <tt>Instruction</tt>, which includes lots of
+less closely-related things. For these cases, LLVM provides a handy wrapper
+class called <a
+href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>.
+It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some
+methods that provide functionality common to <tt>CallInst</tt>s and
+<tt>InvokeInst</tt>s.</p>
+
+<p>This class has "value semantics": it should be passed by value, not by
+reference and it should not be dynamically allocated or deallocated using
+<tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable,
+assignable and constructable, with costs equivalents to that of a bare pointer.
+If you look at its definition, it has only a single pointer member.</p>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="iterate_chains">Iterating over def-use & use-def chains</a>
+</div>
+
+<div class="doc_text">
+
+<p>Frequently, we might have an instance of the <a
+href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to
+determine which <tt>User</tt>s use the <tt>Value</tt>. The list of all
+<tt>User</tt>s of a particular <tt>Value</tt> is called a <i>def-use</i> chain.
+For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a
+particular function <tt>foo</tt>. Finding all of the instructions that
+<i>use</i> <tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain
+of <tt>F</tt>:</p>
+
+<div class="doc_code">
+<pre>
+Function* F = ...;
+
+for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i)
+ if (Instruction *Inst = dyn_cast<Instruction>(*i)) {
+ llvm::cerr << "F is used in instruction:\n";
+ llvm::cerr << *Inst << "\n";
+ }
+</pre>
+</div>
+
+<p>Alternately, 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
+<tt>Instruction</tt> are common <tt>User</tt>s, so we might want to iterate over
+all of the values that a particular instruction uses (that is, the operands of
+the particular <tt>Instruction</tt>):</p>
+
+<div class="doc_code">
+<pre>
+Instruction* pi = ...;
+
+for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {
+ Value* v = *i;
+ // <i>...</i>
+}
+</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]
+-->
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="simplechanges">Making simple changes</a>
+</div>
+
+<div class="doc_text">
+
+<p>There are some primitive transformation operations present in the LLVM
+infrastructure that are worth knowing about. When performing
+transformations, it's fairly common to manipulate the contents of basic
+blocks. This section describes some of the common methods for doing so
+and gives example code.</p>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_creating">Creating and inserting new
+ <tt>Instruction</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<p><i>Instantiating Instructions</i></p>
+
+<p>Creation of <tt>Instruction</tt>s is straight-forward: simply call the
+constructor for the kind of instruction to instantiate and provide the necessary
+parameters. For example, an <tt>AllocaInst</tt> only <i>requires</i> a
+(const-ptr-to) <tt>Type</tt>. Thus:</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* ai = new AllocaInst(Type::IntTy);
+</pre>
+</div>
+
+<p>will create an <tt>AllocaInst</tt> instance that represents the allocation of
+one integer in the current stack frame, at run time. Each <tt>Instruction</tt>
+subclass is likely to have varying default parameters which change the semantics
+of the instruction, so refer to the <a
+href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of
+Instruction</a> that you're interested in instantiating.</p>
+
+<p><i>Naming values</i></p>
+
+<p>It is very useful to name the values of instructions when you're able to, as
+this facilitates the debugging of your transformations. If you end up looking
+at generated LLVM machine code, you definitely want to have logical names
+associated with the results of instructions! By supplying a value for the
+<tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you
+associate a logical name with the result of the instruction's execution at
+run time. For example, say that I'm writing a transformation that dynamically
+allocates space for an integer on the stack, and that integer is going to be
+used as some kind of index by some other code. To accomplish this, I place an
+<tt>AllocaInst</tt> at the first point in the first <tt>BasicBlock</tt> of some
+<tt>Function</tt>, and I'm intending to use it within the same
+<tt>Function</tt>. I might do:</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");
+</pre>
+</div>
+
+<p>where <tt>indexLoc</tt> is now the logical name of the instruction's
+execution value, which is a pointer to an integer on the run time stack.</p>
+
+<p><i>Inserting instructions</i></p>
+
+<p>There are essentially two ways to insert an <tt>Instruction</tt>
+into an existing sequence of instructions that form a <tt>BasicBlock</tt>:</p>
+
+<ul>
+ <li>Insertion into an explicit instruction list
+
+ <p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within that
+ <tt>BasicBlock</tt>, and a newly-created instruction we wish to insert
+ before <tt>*pi</tt>, we do the following: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().insert(pi, newInst); // <i>Inserts newInst before pi in pb</i>
+</pre>
+</div>
+
+ <p>Appending to the end of a <tt>BasicBlock</tt> is so common that
+ the <tt>Instruction</tt> class and <tt>Instruction</tt>-derived
+ classes provide constructors which take a pointer to a
+ <tt>BasicBlock</tt> to be appended to. For example code that
+ looked like: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(...);
+
+pb->getInstList().push_back(newInst); // <i>Appends newInst to pb</i>
+</pre>
+</div>
+
+ <p>becomes: </p>
+
+<div class="doc_code">
+<pre>
+BasicBlock *pb = ...;
+Instruction *newInst = new Instruction(..., pb);
+</pre>
+</div>
+
+ <p>which is much cleaner, especially if you are creating
+ long instruction streams.</p></li>
+
+ <li>Insertion into an implicit instruction list
+
+ <p><tt>Instruction</tt> instances that are already in <tt>BasicBlock</tt>s
+ are implicitly associated with an existing instruction list: the instruction
+ list of the enclosing basic block. Thus, we could have accomplished the same
+ thing as the above code without being given a <tt>BasicBlock</tt> by doing:
+ </p>
+
+<div class="doc_code">
+<pre>
+Instruction *pi = ...;
+Instruction *newInst = new Instruction(...);
+
+pi->getParent()->getInstList().insert(pi, newInst);
+</pre>
+</div>
+
+ <p>In fact, this sequence of steps occurs so frequently that the
+ <tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes provide
+ constructors which take (as a default parameter) a pointer to an
+ <tt>Instruction</tt> which the newly-created <tt>Instruction</tt> should
+ precede. That is, <tt>Instruction</tt> constructors are capable of
+ inserting the newly-created instance into the <tt>BasicBlock</tt> of a
+ provided instruction, immediately before that instruction. Using an
+ <tt>Instruction</tt> constructor with a <tt>insertBefore</tt> (default)
+ parameter, the above code becomes:</p>
+
+<div class="doc_code">
+<pre>
+Instruction* pi = ...;
+Instruction* newInst = new Instruction(..., pi);
+</pre>
+</div>
+
+ <p>which is much cleaner, especially if you're creating a lot of
+ instructions and adding them to <tt>BasicBlock</tt>s.</p></li>
+</ul>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<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>
+
+<div class="doc_code">
+<pre>
+<a href="#Instruction">Instruction</a> *I = .. ;
+<a href="#BasicBlock">BasicBlock</a> *BB = I->getParent();
+
+BB->getInstList().erase(I);
+</pre>
+</div>
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another
+ <tt>Value</tt></a>
+</div>
+
+<div class="doc_text">
+
+<p><i>Replacing individual instructions</i></p>
+
+<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>
+
+<ul>
+ <li><tt>ReplaceInstWithValue</tt>
+
+ <p>This function replaces all uses (within a basic block) of a given
+ instruction with a value, and then removes the original instruction. The
+ following example illustrates the replacement of the result of a particular
+ <tt>AllocaInst</tt> that allocates memory for a single integer with a null
+ pointer to an integer.</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,
+ Constant::getNullValue(PointerType::get(Type::IntTy)));
+</pre></div></li>
+
+ <li><tt>ReplaceInstWithInst</tt>
+
+ <p>This function replaces a particular instruction with another
+ instruction. The following example illustrates the replacement of one
+ <tt>AllocaInst</tt> with another.</p>
+
+<div class="doc_code">
+<pre>
+AllocaInst* instToReplace = ...;
+BasicBlock::iterator ii(instToReplace);
+
+ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,
+ new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt"));
+</pre></div></li>
+</ul>
+
+<p><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></p>
+
+<p>You can use <tt>Value::replaceAllUsesWith</tt> and
+<tt>User::replaceUsesOfWith</tt> to change more than one use at a time. See the
+doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a>
+and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more
+information.</p>
+
+<!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out:
+include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with:
+ReplaceInstWithValue, ReplaceInstWithInst -->
+
+</div>
+
+<!--_______________________________________________________________________-->
+<div class="doc_subsubsection">
+ <a name="schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a>
+</div>
+
+<div class="doc_text">
+
+<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
+ to delete. You use this pointer to erase it from its parent, the module.
+ For example:</p>
+
+<div class="doc_code">
+<pre>
+<a href="#GlobalVariable">GlobalVariable</a> *GV = .. ;
+
+GV->eraseFromParent();
+</pre>
+</div>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="advanced">Advanced Topics</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<p>
+This section describes some of the advanced or obscure API's that most clients
+do not need to be aware of. These API's tend manage the inner workings of the
+LLVM system, and only need to be accessed in unusual circumstances.
+</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="TypeResolve">LLVM Type Resolution</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+The LLVM type system has a very simple goal: allow clients to compare types for
+structural equality with a simple pointer comparison (aka a shallow compare).
+This goal makes clients much simpler and faster, and is used throughout the LLVM
+system.
+</p>
+
+<p>
+Unfortunately achieving this goal is not a simple matter. In particular,
+recursive types and late resolution of opaque types makes the situation very
+difficult to handle. Fortunately, for the most part, our implementation makes
+most clients able to be completely unaware of the nasty internal details. The
+primary case where clients are exposed to the inner workings of it are when
+building a recursive type. In addition to this case, the LLVM bitcode reader,
+assembly parser, and linker also have to be aware of the inner workings of this
+system.
+</p>
+
+<p>
+For our purposes below, we need three concepts. First, an "Opaque Type" is
+exactly as defined in the <a href="LangRef.html#t_opaque">language
+reference</a>. Second an "Abstract Type" is any type which includes an
+opaque type as part of its type graph (for example "<tt>{ opaque, i32 }</tt>").
+Third, a concrete type is a type that is not an abstract type (e.g. "<tt>{ i32,
+float }</tt>").
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="BuildRecType">Basic Recursive Type Construction</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+Because the most common question is "how do I build a recursive type with LLVM",
+we answer it now and explain it as we go. Here we include enough to cause this
+to be emitted to an output .ll file:
+</p>
+
+<div class="doc_code">
+<pre>
+%mylist = type { %mylist*, i32 }
+</pre>
+</div>
+
+<p>
+To build this, use the following LLVM APIs:
+</p>
+
+<div class="doc_code">
+<pre>
+// <i>Create the initial outer struct</i>
+<a href="#PATypeHolder">PATypeHolder</a> StructTy = OpaqueType::get();
+std::vector<const Type*> Elts;
+Elts.push_back(PointerType::get(StructTy));
+Elts.push_back(Type::IntTy);
+StructType *NewSTy = StructType::get(Elts);
+
+// <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i>
+// <i>the struct and the opaque type are actually the same.</i>
+cast<OpaqueType>(StructTy.get())-><a href="#refineAbstractTypeTo">refineAbstractTypeTo</a>(NewSTy);
+
+// <i>NewSTy is potentially invalidated, but StructTy (a <a href="#PATypeHolder">PATypeHolder</a>) is</i>
+// <i>kept up-to-date</i>
+NewSTy = cast<StructType>(StructTy.get());
+
+// <i>Add a name for the type to the module symbol table (optional)</i>
+MyModule->addTypeName("mylist", NewSTy);
+</pre>
+</div>
+
+<p>
+This code shows the basic approach used to build recursive types: build a
+non-recursive type using 'opaque', then use type unification to close the cycle.
+The type unification step is performed by the <tt><a
+href="#refineAbstractTypeTo">refineAbstractTypeTo</a></tt> method, which is
+described next. After that, we describe the <a
+href="#PATypeHolder">PATypeHolder class</a>.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a>
+</div>
+
+<div class="doc_text">
+<p>
+The <tt>refineAbstractTypeTo</tt> method starts the type unification process.
+While this method is actually a member of the DerivedType class, it is most
+often used on OpaqueType instances. Type unification is actually a recursive
+process. After unification, types can become structurally isomorphic to
+existing types, and all duplicates are deleted (to preserve pointer equality).
+</p>
+
+<p>
+In the example above, the OpaqueType object is definitely deleted.
+Additionally, if there is an "{ \2*, i32}" type already created in the system,
+the pointer and struct type created are <b>also</b> deleted. Obviously whenever
+a type is deleted, any "Type*" pointers in the program are invalidated. As
+such, it is safest to avoid having <i>any</i> "Type*" pointers to abstract types
+live across a call to <tt>refineAbstractTypeTo</tt> (note that non-abstract
+types can never move or be deleted). To deal with this, the <a
+href="#PATypeHolder">PATypeHolder</a> class is used to maintain a stable
+reference to a possibly refined type, and the <a
+href="#AbstractTypeUser">AbstractTypeUser</a> class is used to update more
+complex datastructures.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="PATypeHolder">The PATypeHolder Class</a>
+</div>
+
+<div class="doc_text">
+<p>
+PATypeHolder is a form of a "smart pointer" for Type objects. When VMCore
+happily goes about nuking types that become isomorphic to existing types, it
+automatically updates all PATypeHolder objects to point to the new type. In the
+example above, this allows the code to maintain a pointer to the resultant
+resolved recursive type, even though the Type*'s are potentially invalidated.
+</p>
+
+<p>
+PATypeHolder is an extremely light-weight object that uses a lazy union-find
+implementation to update pointers. For example the pointer from a Value to its
+Type is maintained by PATypeHolder objects.
+</p>
+
+</div>
+
+<!-- ______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="AbstractTypeUser">The AbstractTypeUser Class</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+Some data structures need more to perform more complex updates when types get
+resolved. To support this, a class can derive from the AbstractTypeUser class.
+This class
+allows it to get callbacks when certain types are resolved. To register to get
+callbacks for a particular type, the DerivedType::{add/remove}AbstractTypeUser
+methods can be called on a type. Note that these methods only work for <i>
+ abstract</i> types. Concrete types (those that do not include any opaque
+objects) can never be refined.
+</p>
+</div>
-These methods are the interface to access the def-use information in LLVM. As with all other iterators in LLVM, the naming conventions follow the conventions defined by the <a href="#stl">STL</a>.<p>
-<li><tt><a href="#Type">Type</a> *getType() const</tt><p>
-This method returns the Type of the Value.
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="SymbolTable">The <tt>ValueSymbolTable</tt> and
+ <tt>TypeSymbolTable</tt> classes</a>
+</div>
+
+<div class="doc_text">
+<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>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
+names themselves are required, which is very special purpose. Note that not
+all LLVM
+<a href="#Value">Value</a>s have names, and those without names (i.e. they have
+an empty name) do not exist in the symbol table.
+</p>
-<li><tt>bool hasName() const</tt><br>
- <tt>std::string getName() const</tt><br>
- <tt>void setName(const std::string &Name)</tt><p>
+<p>These symbol tables support iteration over the values/types 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>
-This family of methods is used to access and assign a name to a <tt>Value</tt>,
-be aware of the <a href="#nameWarning">precaution above</a>.<p>
+</div>
-<li><tt>void replaceAllUsesWith(Value *V)</tt><p>
-This method traverses the use list of a <tt>Value</tt> changing all <a
-href="#User"><tt>User</tt>s</a> of the current value to refer to "<tt>V</tt>"
-instead. For example, if you detect that an instruction always produces a
-constant value (for example through constant folding), you can replace all uses
-of the instruction with the constant like this:<p>
+<!-- *********************************************************************** -->
+<div class="doc_section">
+ <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
+</div>
+<!-- *********************************************************************** -->
-<pre>
- Inst->replaceAllUsesWith(ConstVal);
-</pre><p>
+<div class="doc_text">
+<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>
+<p>The Core LLVM classes are the primary means of representing the program
+being inspected or transformed. The core LLVM classes are defined in
+header files in the <tt>include/llvm/</tt> directory, and implemented in
+the <tt>lib/VMCore</tt> directory.</p>
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="User">The <tt>User</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classUser.html">User Class</a><br>
-Superclass: <a href="#Value"><tt>Value</tt></a><p>
-
+<div class="doc_subsection">
+ <a name="Type">The <tt>Type</tt> class and Derived Types</a>
+</div>
+
+<div class="doc_text">
+
+ <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
+ through its subclasses. Certain primitive types (<tt>VoidType</tt>,
+ <tt>LabelType</tt>, <tt>FloatType</tt> and <tt>DoubleType</tt>) have hidden
+ subclasses. They are hidden because they offer no useful functionality beyond
+ what the <tt>Type</tt> class offers except to distinguish themselves from
+ other subclasses of <tt>Type</tt>.</p>
+ <p>All other types are subclasses of <tt>DerivedType</tt>. Types can be
+ named, but this is not a requirement. There exists exactly
+ one instance of a given shape at any one time. This allows type equality to
+ be performed with address equality of the Type Instance. That is, given two
+ <tt>Type*</tt> values, the types are identical if the pointers are identical.
+ </p>
+</div>
-The <tt>User</tt> class is the common base class of all LLVM nodes that may
-refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands"
-that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is
-referring to. The <tt>User</tt> class itself is a subclass of
-<tt>Value</tt>.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Public Methods</a>
+</div>
-The operands of a <tt>User</tt> point directly to the LLVM <a
-href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static
-Single Assignment (SSA) form, there can only be one definition referred to,
-allowing this direct connection. This connection provides the use-def
-information in LLVM.<p>
+<div class="doc_text">
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_User"><hr size=0>Important Public Members of
-the <tt>User</tt> class</h4><ul>
+<ul>
+ <li><tt>bool isInteger() const</tt>: Returns true for any integer type.</li>
-The <tt>User</tt> class exposes the operand list in two ways: through an index
-access interface and through an iterator based interface.<p>
+ <li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two
+ floating point types.</li>
-<li><tt>Value *getOperand(unsigned i)</tt><br>
- <tt>unsigned getNumOperands()</tt><p>
+ <li><tt>bool isAbstract()</tt>: Return true if the type is abstract (contains
+ an OpaqueType anywhere in its definition).</li>
-These two methods expose the operands of the <tt>User</tt> in a convenient form
-for direct access.<p>
+ <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>
-<li><tt>User::op_iterator</tt> - Typedef for iterator over the operand list<br>
- <tt>User::op_const_iterator</tt>
- <tt>use_iterator op_begin()</tt>
- - Get an iterator to the start of the operand list.<br>
- <tt>use_iterator op_end()</tt>
- - Get an iterator to the end of the operand list.<p>
+</ul>
+</div>
-Together, these methods make up the iterator based interface to the operands of
-a <tt>User</tt>.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Derived Types</a>
+</div>
+<div class="doc_text">
+<dl>
+ <dt><tt>IntegerType</tt></dt>
+ <dd>Subclass of DerivedType that represents integer types of any bit width.
+ Any bit width between <tt>IntegerType::MIN_INT_BITS</tt> (1) and
+ <tt>IntegerType::MAX_INT_BITS</tt> (~8 million) can be represented.
+ <ul>
+ <li><tt>static const IntegerType* get(unsigned NumBits)</tt>: get an integer
+ type of a specific bit width.</li>
+ <li><tt>unsigned getBitWidth() const</tt>: Get the bit width of an integer
+ type.</li>
+ </ul>
+ </dd>
+ <dt><tt>SequentialType</tt></dt>
+ <dd>This is subclassed by ArrayType and PointerType
+ <ul>
+ <li><tt>const Type * getElementType() const</tt>: Returns the type of each
+ of the elements in the sequential type. </li>
+ </ul>
+ </dd>
+ <dt><tt>ArrayType</tt></dt>
+ <dd>This is a subclass of SequentialType and defines the interface for array
+ types.
+ <ul>
+ <li><tt>unsigned getNumElements() const</tt>: Returns the number of
+ elements in the array. </li>
+ </ul>
+ </dd>
+ <dt><tt>PointerType</tt></dt>
+ <dd>Subclass of SequentialType for pointer types.</dd>
+ <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
+ vector operations and are usually small vectors of of an integer or floating
+ point type.</dd>
+ <dt><tt>StructType</tt></dt>
+ <dd>Subclass of DerivedTypes for struct types.</dd>
+ <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
+ function</li>
+ <li><tt> const Type * getReturnType() const</tt>: Returns the
+ return type of the function.</li>
+ <li><tt>const Type * getParamType (unsigned i)</tt>: Returns
+ the type of the ith parameter.</li>
+ <li><tt> const unsigned getNumParams() const</tt>: Returns the
+ 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>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Instruction">The <tt>Instruction</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a
-href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classInstruction.html">Instruction Class</a><br>
-Superclasses: <a href="#User"><tt>User</tt></a>, <a
-href="#Value"><tt>Value</tt></a><p>
+<div class="doc_subsection">
+ <a name="Module">The <tt>Module</tt> class</a>
+</div>
-The <tt>Instruction</tt> class is the common base class for all LLVM
-instructions. It provides only a few methods, but is a very commonly used
-class. The primary data tracked by the <tt>Instruction</tt> class itself is the
-opcode (instruction type) and the parent <a
-href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded
-into. To represent a specific type of instruction, one of many subclasses of
-<tt>Instruction</tt> are used.<p>
+<div class="doc_text">
-Because the <tt>Instruction</tt> class subclasses the <a
-href="#User"><tt>User</tt></a> class, its operands can be accessed in the same
-way as for other <a href="#User"><tt>User</tt></a>s (with the
-<tt>getOperand()</tt>/<tt>getNumOperands()</tt> and
-<tt>op_begin()</tt>/<tt>op_end()</tt> methods).<p>
+<p><tt>#include "<a
+href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info:
+<a href="/doxygen/classllvm_1_1Module.html">Module Class</a></p>
-An important file for the <tt>Instruction</tt> class is the
-<tt>llvm/Instruction.def</tt> file. This file contains some meta-data about the
-various different types of instructions in LLVM. It describes the enum values
-that are used as opcodes (for example <tt>Instruction::Add</tt> and
-<tt>Instruction::SetLE</tt>), as well as the concrete sub-classes of
-<tt>Instruction</tt> that implement the instruction (for example <tt><a
-href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a
-href="#SetCondInst">SetCondInst</a></tt>). Unfortunately, the use of macros in
-this file confused doxygen, so these enum values don't show up correctly in the
-<a href="/doxygen/classInstruction.html">doxygen output</a>.<p>
+<p>The <tt>Module</tt> class represents the top level structure present in LLVM
+programs. An LLVM module is effectively either a translation unit of the
+original program or a combination of several translation units merged by the
+linker. The <tt>Module</tt> class keeps track of a list of <a
+href="#Function"><tt>Function</tt></a>s, a list of <a
+href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a
+href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few
+helpful member functions that try to make common operations easy.</p>
+</div>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Instruction"><hr size=0>Important Public Members of
-the <tt>Instruction</tt> class</h4><ul>
+<div class="doc_subsubsection">
+ <a name="m_Module">Important Public Members of the <tt>Module</tt> class</a>
+</div>
-<li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt><p>
+<div class="doc_text">
-Returns the <a href="#BasicBlock"><tt>BasicBlock</tt></a> that this
-<tt>Instruction</tt> is embedded into.<p>
+<ul>
+ <li><tt>Module::Module(std::string name = "")</tt></li>
+</ul>
-<li><tt>bool mayWriteToMemory()</tt><p>
+<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>
-Returns true if the instruction writes to memory, i.e. it is a <tt>call</tt>,
-<tt>free</tt>, <tt>invoke</tt>, or <tt>store</tt>.<p>
+<ul>
+ <li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
+ <tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
-<li><tt>unsigned getOpcode()</tt><p>
+ <tt>begin()</tt>, <tt>end()</tt>
+ <tt>size()</tt>, <tt>empty()</tt>
-Returns the opcode for the <tt>Instruction</tt>.<p>
+ <p>These are forwarding methods that make it easy to access the contents of
+ a <tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a>
+ list.</p></li>
-<li><tt><a href="#Instruction">Instruction</a> *clone() const</tt><p>
+ <li><tt>Module::FunctionListType &getFunctionList()</tt>
-Returns another instance of the specified instruction, identical in all ways to
-the original except that the instruction has no parent (ie it's not embedded
-into a <a href="#BasicBlock"><tt>BasicBlock</tt></a>), and it has no name.<p>
+ <p> Returns the list of <a href="#Function"><tt>Function</tt></a>s. This is
+ necessary to use when you need to update the list or perform a complex
+ action that doesn't have a forwarding method.</p>
+ <p><!-- Global Variable --></p></li>
+</ul>
+<hr>
-<!--
+<ul>
+ <li><tt>Module::global_iterator</tt> - Typedef for global variable list iterator<br>
-\subsection{Subclasses of Instruction :}
-\begin{itemize}
-<li>BinaryOperator : This subclass of Instruction defines a general interface to the all the instructions involvong binary operators in LLVM.
- \begin{itemize}
- <li><tt>bool swapOperands()</tt>: Exchange the two operands to this instruction. If the instruction cannot be reversed (i.e. if it's a Div), it returns true.
- \end{itemize}
-<li>TerminatorInst : This subclass of Instructions defines an interface for all instructions that can terminate a BasicBlock.
- \begin{itemize}
- <li> <tt>unsigned getNumSuccessors()</tt>: Returns the number of successors for this terminator instruction.
- <li><tt>BasicBlock *getSuccessor(unsigned i)</tt>: As the name suggests returns the ith successor BasicBlock.
- <li><tt>void setSuccessor(unsigned i, BasicBlock *B)</tt>: sets BasicBlock B as the ith succesor to this terminator instruction.
- \end{itemize}
-
-<li>PHINode : This represents the PHI instructions in the SSA form.
- \begin{itemize}
- <li><tt> unsigned getNumIncomingValues()</tt>: Returns the number of incoming edges to this PHI node.
- <li><tt> Value *getIncomingValue(unsigned i)</tt>: Returns the ith incoming Value.
- <li><tt>void setIncomingValue(unsigned i, Value *V)</tt>: Sets the ith incoming Value as V
- <li><tt>BasicBlock *getIncomingBlock(unsigned i)</tt>: Returns the Basic Block corresponding to the ith incoming Value.
- <li><tt> void addIncoming(Value *D, BasicBlock *BB)</tt>:
- Add an incoming value to the end of the PHI list
- <li><tt> int getBasicBlockIndex(const BasicBlock *BB) const</tt>:
- Returns the first index of the specified basic block in the value list for this PHI. Returns -1 if no instance.
- \end{itemize}
-<li>CastInst : In LLVM all casts have to be done through explicit cast instructions. CastInst defines the interface to the cast instructions.
-<li>CallInst : This defines an interface to the call instruction in LLVM. ARguments to the function are nothing but operands of the instruction.
- \begin{itemize}
- <li>: <tt>Function *getCalledFunction()</tt>: Returns a handle to the function that is being called by this Function.
- \end{itemize}
-<li>LoadInst, StoreInst, GetElemPtrInst : These subclasses represent load, store and getelementptr instructions in LLVM.
- \begin{itemize}
- <li><tt>Value * getPointerOperand()</tt>: Returns the Pointer Operand which is typically the 0th operand.
- \end{itemize}
-<li>BranchInst : This is a subclass of TerminatorInst and defines the interface for conditional and unconditional branches in LLVM.
- \begin{itemize}
- <li><tt>bool isConditional()</tt>: Returns true if the branch is a conditional branch else returns false
- <li> <tt>Value *getCondition()</tt>: Returns the condition if it is a conditional branch else returns null.
- <li> <tt>void setUnconditionalDest(BasicBlock *Dest)</tt>: Changes the current branch to an unconditional one targetting the specified block.
- \end{itemize}
-
-\end{itemize}
+ <tt>Module::const_global_iterator</tt> - Typedef for const_iterator.<br>
--->
+ <tt>global_begin()</tt>, <tt>global_end()</tt>
+ <tt>global_size()</tt>, <tt>global_empty()</tt>
+ <p> These are forwarding methods that make it easy to access the contents of
+ a <tt>Module</tt> object's <a
+ href="#GlobalVariable"><tt>GlobalVariable</tt></a> list.</p></li>
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="BasicBlock">The <tt>BasicBlock</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a
-href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classBasicBlock.html">BasicBlock Class</a><br>
-Superclass: <a href="#Value"><tt>Value</tt></a><p>
-
-
-This class represents a single entry multiple 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. Matching the language definition, the last element of
-this list of instructions is always a terminator instruction (a subclass of the
-<a href="#TerminatorInst"><tt>TerminatorInst</tt></a> class).<p>
-
-In addition to tracking the list of instructions that make up the block, the
-<tt>BasicBlock</tt> class also keeps track of the <a
-href="#Function"><tt>Function</tt></a> that it is embedded into.<p>
+ <li><tt>Module::GlobalListType &getGlobalList()</tt>
-
Note that <tt>BasicBlock</tt>s themselves are <a
-href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions
-like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type
-<tt>label</tt>.<p>
+
<p>Returns the list of <a
+ href="#GlobalVariable"><tt>GlobalVariable</tt></a>s. This is necessary to
+ use when you need to update the list or perform a complex action that
+ doesn't have a forwarding method.</p>
+ <p><!-- Symbol table stuff --> </p></li>
+</ul>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_BasicBlock"><hr size=0>Important Public Members of
-the <tt>BasicBlock</tt> class</h4><ul>
+<hr>
-<li><tt>BasicBlock(const std::string &Name = "", <a
-href="#Function">Function</a> *Parent = 0)</tt><p>
+<ul>
+ <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
-The <tt>BasicBlock</tt> constructor is used to create new basic blocks for
-insertion into a function. The constructor simply takes a name for the new
-block, and optionally a <a href="#Function"><tt>Function</tt></a> to insert it
-into. If the <tt>Parent</tt> parameter is specified, the new
-<tt>BasicBlock</tt> is automatically inserted at the end of the specified <a
-href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be
-manually inserted into the <a href="#Function"><tt>Function</tt></a>.<p>
+ <p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
+ for this <tt>Module</tt>.</p>
-<li><tt>BasicBlock::iterator</tt> - Typedef for instruction list iterator<br>
- <tt>BasicBlock::const_iterator</tt> - Typedef for const_iterator.<br>
- <tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
- <tt>size()</tt>, <tt>empty()</tt>, <tt>rbegin()</tt>, <tt>rend()</tt><p>
+ <p><!-- Convenience methods --></p></li>
+</ul>
-These methods and typedefs are forwarding functions that have the same semantics
-as the standard library methods of the same names. These methods expose the
-underlying instruction list of a basic block in a way that is easy to
-manipulate. To get the full complement of container operations (including
-operations to update the list), you must use the <tt>getInstList()</tt>
-method.<p>
+<hr>
-<li><tt>BasicBlock::InstListType &getInstList()</tt><p>
+<ul>
+ <li><tt><a href="#Function">Function</a> *getFunction(const std::string
+ &Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt>
-This method is used to get access to the underlying container that actually
-holds the Instructions. This method must be used when there isn't a forwarding
-function in the <tt>BasicBlock</tt> class for the operation that you would like
-to perform. Because there are no forwarding functions for "updating"
-operations, you need to use this if you want to update the contents of a
-<tt>BasicBlock</tt>.<p>
+ <p>Look up the specified function in the <tt>Module</tt> <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return
+ <tt>null</tt>.</p></li>
-<li><tt><A href="#Function">Function</a> *getParent()</tt><p>
+ <li><tt><a href="#Function">Function</a> *getOrInsertFunction(const
+ std::string &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt>
-Returns a pointer to <a href="#Function"><tt>Function</tt></a> the block is
-embedded into, or a null pointer if it is homeless.<p>
+ <p>Look up the specified function in the <tt>Module</tt> <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an
+ external declaration for the function and return it.</p></li>
-<li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt><p>
+ <li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt>
-Returns a pointer to the terminator instruction that appears at the end of the
-<tt>BasicBlock</tt>. If there is no terminator instruction, or if the last
-instruction in the block is not a terminator, then a null pointer is
-returned.<p>
+ <p>If there is at least one entry in the <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a
+ href="#Type"><tt>Type</tt></a>, return it. Otherwise return the empty
+ string.</p></li>
+
+ <li><tt>bool addTypeName(const std::string &Name, const <a
+ href="#Type">Type</a> *Ty)</tt>
+
+ <p>Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
+ mapping <tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this
+ name, true is returned and the <a
+ href="#SymbolTable"><tt>SymbolTable</tt></a> is not modified.</p></li>
+</ul>
+
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="GlobalValue">The <tt>GlobalValue</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a
-href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classGlobalValue.html">GlobalValue Class</a><br>
-Superclasses: <a href="#User"><tt>User</tt></a>, <a
-href="#Value"><tt>Value</tt></a><p>
+<div class="doc_subsection">
+ <a name="Value">The <tt>Value</tt> class</a>
+</div>
-Global values (<A href="#GlobalVariable"><tt>GlobalVariable</tt></a>s or <a
-href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are
-visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s.
-Because they are visible at global scope, they are also subject to linking with
-other globals defined in different translation units. To control the linking
-process, <tt>GlobalValue</tt>s know their linkage rules. Specifically,
-<tt>GlobalValue</tt>s know whether they have internal or external linkage.<p>
+<div class="doc_text">
-If a <tt>GlobalValue</tt> has internal linkage (equivalent to being
-<tt>static</tt> in C), it is not visible to code outside the current translation
-unit, and does not participate in linking. If it has external linkage, it is
-visible to external code, and does participate in linking. In addition to
-linkage information, <tt>GlobalValue</tt>s keep track of which <a
-href="#Module"><tt>Module</tt></a> they are currently part of.<p>
+<p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt>
+<br>
+doxygen info: <a href="/doxygen/classllvm_1_1Value.html">Value Class</a></p>
-Because <tt>GlobalValue</tt>s are memory objects, they are always referred to by
-their address. As such, the <a href="#Type"><tt>Type</tt></a> of a global is
-always a pointer to its contents. This is explained in the LLVM Language
-Reference Manual.<p>
+<p>The <tt>Value</tt> class is the most important class in the LLVM Source
+base. It represents a typed value that may be used (among other things) as an
+operand to an instruction. There are many different types of <tt>Value</tt>s,
+such as <a href="#Constant"><tt>Constant</tt></a>s,<a
+href="#Argument"><tt>Argument</tt></a>s. Even <a
+href="#Instruction"><tt>Instruction</tt></a>s and <a
+href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.</p>
+<p>A particular <tt>Value</tt> may be used many times in the LLVM representation
+for a program. For example, an incoming argument to a function (represented
+with an instance of the <a href="#Argument">Argument</a> class) is "used" by
+every instruction in the function that references the argument. To keep track
+of this relationship, the <tt>Value</tt> class keeps a list of all of the <a
+href="#User"><tt>User</tt></a>s that is using it (the <a
+href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM
+graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents
+def-use information in the program, and is accessible through the <tt>use_</tt>*
+methods, shown below.</p>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_GlobalValue"><hr size=0>Important Public Members of
-the <tt>GlobalValue</tt> class</h4><ul>
+<p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed,
+and this <a href="#Type">Type</a> is available through the <tt>getType()</tt>
+method. In addition, all LLVM values can be named. The "name" of the
+<tt>Value</tt> is a symbolic string printed in the LLVM code:</p>
-<li><tt>bool hasInternalLinkage() const</tt><br>
- <tt>bool hasExternalLinkage() const</tt><br>
- <tt>void setInternalLinkage(bool HasInternalLinkage)</tt><p>
+<div class="doc_code">
+<pre>
+%<b>foo</b> = add i32 1, 2
+</pre>
+</div>
-These methods manipulate the linkage characteristics of the
-<tt>GlobalValue</tt>.<p>
+<p><a name="nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b>
+that the name of any value may be missing (an empty string), so names should
+<b>ONLY</b> be used for debugging (making the source code easier to read,
+debugging printouts), they should not be used to keep track of values or map
+between them. For this purpose, use a <tt>std::map</tt> of pointers to the
+<tt>Value</tt> itself instead.</p>
-<li><tt><a href="#Module">Module</a> *getParent()</tt><p>
+<p>One important aspect of LLVM is that there is no distinction between an SSA
+variable and the operation that produces it. Because of this, any reference to
+the value produced by an instruction (or the value available as an incoming
+argument, for example) is represented as a direct pointer to the instance of
+the class that
+represents this value. Although this may take some getting used to, it
+simplifies the representation and makes it easier to manipulate.</p>
-This returns the <a href="#Module"><tt>Module</tt></a> that the GlobalValue is
-currently embedded into.<p>
+</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Value">Important Public Members of the <tt>Value</tt> class</a>
+</div>
+<div class="doc_text">
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Function">The <tt>Function</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a
-href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classFunction.html">Function Class</a><br>
-Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>, <a
-href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a><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
-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 <a
-href="#SymbolTable"><tt>SymbolTable</tt></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 layed 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 explicitly branch to this initial
-block. There are no implicit exit nodes, and in fact there may be multiple exit
-nodes from a single <tt>Function</tt>. If the <a
-href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that
-the <tt>Function</tt> is actually a function declaration: the actual body of the
-function hasn't been linked in yet.<p>
+<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
+the use-list<br>
+ <tt>unsigned use_size()</tt> - Returns the number of users of the
+value.<br>
+ <tt>bool use_empty()</tt> - Returns true if there are no users.<br>
+ <tt>use_iterator use_begin()</tt> - Get an iterator to the start of
+the use-list.<br>
+ <tt>use_iterator use_end()</tt> - Get an iterator to the end of the
+use-list.<br>
+ <tt><a href="#User">User</a> *use_back()</tt> - Returns the last
+element in the list.
+ <p> These methods are the interface to access the def-use
+information in LLVM. As with all other iterators in LLVM, the naming
+conventions follow the conventions defined by the <a href="#stl">STL</a>.</p>
+ </li>
+ <li><tt><a href="#Type">Type</a> *getType() const</tt>
+ <p>This method returns the Type of the Value.</p>
+ </li>
+ <li><tt>bool hasName() const</tt><br>
+ <tt>std::string getName() const</tt><br>
+ <tt>void setName(const std::string &Name)</tt>
+ <p> This family of methods is used to access and assign a name to a <tt>Value</tt>,
+be aware of the <a href="#nameWarning">precaution above</a>.</p>
+ </li>
+ <li><tt>void replaceAllUsesWith(Value *V)</tt>
+
+ <p>This method traverses the use list of a <tt>Value</tt> changing all <a
+ href="#User"><tt>User</tt>s</a> of the current value to refer to
+ "<tt>V</tt>" instead. For example, if you detect that an instruction always
+ produces a constant value (for example through constant folding), you can
+ replace all uses of the instruction with the constant like this:</p>
+
+<div class="doc_code">
+<pre>
+Inst->replaceAllUsesWith(ConstVal);
+</pre>
+</div>
-In addition to a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, the
-<tt>Function</tt> class also keeps track of the list of formal <a
-href="#Argument"><tt>Argument</tt></a>s that the function receives. This
-container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a>
-nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for
-the <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.<p>
+</ul>
-The <a href="#SymbolTable"><tt>SymbolTable</tt></a> is a very rarely used LLVM
-feature that is only used when you have to look up a value by name. Aside from
-that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used internally to
-make sure that there are not conflicts between the names of <a
-href="#Instruction"><tt>Instruction</tt></a>s, <a
-href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a
-href="#Argument"><tt>Argument</tt></a>s in the function body.<p>
+</div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="User">The <tt>User</tt> class</a>
+</div>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Function"><hr size=0>Important Public Members of
-the <tt>Function</tt> class</h4><ul>
+<div class="doc_text">
+
+<p>
+<tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br>
+doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br>
+Superclass: <a href="#Value"><tt>Value</tt></a></p>
-<li><tt>Function(const <a href="#FunctionType">FunctionType</a> *Ty, bool isInternal, const std::string &N = "")</tt><p>
+<p>The <tt>User</tt> class is the common base class of all LLVM nodes that may
+refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands"
+that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is
+referring to. The <tt>User</tt> class itself is a subclass of
+<tt>Value</tt>.</p>
-Constructor used when you need to create new <tt>Function</tt>s to add the the
-program. The constructor must specify the type of the function to create and
-whether or not it should start out with internal or external linkage.<p>
+<p>The operands of a <tt>User</tt> point directly to the LLVM <a
+href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static
+Single Assignment (SSA) form, there can only be one definition referred to,
+allowing this direct connection. This connection provides the use-def
+information in LLVM.</p>
-<li><tt>bool isExternal()</tt><p>
+</div>
-Return whether or not the <tt>Function</tt> has a body defined. If the function
-is "external", it does not have a body, and thus must be resolved by linking
-with a function defined in a different translation unit.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_User">Important Public Members of the <tt>User</tt> class</a>
+</div>
+<div class="doc_text">
-<li><tt>Function::iterator</tt> - Typedef for basic block list iterator<br>
- <tt>Function::const_iterator</tt> - Typedef for const_iterator.<br>
- <tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
- <tt>size()</tt>, <tt>empty()</tt>, <tt>rbegin()</tt>, <tt>rend()</tt><p>
+<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>
-These are forwarding methods that make it easy to access the contents of a
-<tt>Function</tt> object's <a href="#BasicBlock"><tt>BasicBlock</tt></a>
-list.<p>
+<ul>
+ <li><tt>Value *getOperand(unsigned i)</tt><br>
+ <tt>unsigned getNumOperands()</tt>
+ <p> These two methods expose the operands of the <tt>User</tt> in a
+convenient form for direct access.</p></li>
+
+ <li><tt>User::op_iterator</tt> - Typedef for iterator over the operand
+list<br>
+ <tt>op_iterator op_begin()</tt> - Get an iterator to the start of
+the operand list.<br>
+ <tt>op_iterator op_end()</tt> - Get an iterator to the end of the
+operand list.
+ <p> Together, these methods make up the iterator based interface to
+the operands of a <tt>User</tt>.</p></li>
+</ul>
-<li><tt>Function::BasicBlockListType &getBasicBlockList()</tt><p>
+</div>
-Returns the list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s. This is
-neccesary to use when you need to update the list or perform a complex action
-that doesn't have a forwarding method.<p>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Instruction">The <tt>Instruction</tt> class</a>
+</div>
+<div class="doc_text">
-<li><tt>Function::aiterator</tt> - Typedef for the argument list iterator<br>
- <tt>Function::const_aiterator</tt> - Typedef for const_iterator.<br>
- <tt>abegin()</tt>, <tt>aend()</tt>, <tt>afront()</tt>, <tt>aback()</tt>,
- <tt>asize()</tt>, <tt>aempty()</tt>, <tt>arbegin()</tt>, <tt>arend()</tt><p>
+<p><tt>#include "</tt><tt><a
+href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br>
+doxygen info: <a href="/doxygen/classllvm_1_1Instruction.html">Instruction Class</a><br>
+Superclasses: <a href="#User"><tt>User</tt></a>, <a
+href="#Value"><tt>Value</tt></a></p>
-These are forwarding methods that make it easy to access the contents of a
-<tt>Function</tt> object's <a href="#Argument"><tt>Argument</tt></a> list.<p>
+<p>The <tt>Instruction</tt> class is the common base class for all LLVM
+instructions. It provides only a few methods, but is a very commonly used
+class. The primary data tracked by the <tt>Instruction</tt> class itself is the
+opcode (instruction type) and the parent <a
+href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded
+into. To represent a specific type of instruction, one of many subclasses of
+<tt>Instruction</tt> are used.</p>
-<li><tt>Function::ArgumentListType &getArgumentList()</tt><p>
+<p> Because the <tt>Instruction</tt> class subclasses the <a
+href="#User"><tt>User</tt></a> class, its operands can be accessed in the same
+way as for other <a href="#User"><tt>User</tt></a>s (with the
+<tt>getOperand()</tt>/<tt>getNumOperands()</tt> and
+<tt>op_begin()</tt>/<tt>op_end()</tt> methods).</p> <p> An important file for
+the <tt>Instruction</tt> class is the <tt>llvm/Instruction.def</tt> file. This
+file contains some meta-data about the various different types of instructions
+in LLVM. It describes the enum values that are used as opcodes (for example
+<tt>Instruction::Add</tt> and <tt>Instruction::ICmp</tt>), as well as the
+concrete sub-classes of <tt>Instruction</tt> that implement the instruction (for
+example <tt><a href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a
+href="#CmpInst">CmpInst</a></tt>). Unfortunately, the use of macros in
+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>
-Returns the list of <a href="#Argument"><tt>Argument</tt></a>s. This is
-neccesary to use when you need to update the list or perform a complex action
-that doesn't have a forwarding method.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="s_Instruction">Important Subclasses of the <tt>Instruction</tt>
+ class</a>
+</div>
+<div class="doc_text">
+ <ul>
+ <li><tt><a name="BinaryOperator">BinaryOperator</a></tt>
+ <p>This subclasses represents all two operand instructions whose operands
+ must be the same type, except for the comparison instructions.</p></li>
+ <li><tt><a name="CastInst">CastInst</a></tt>
+ <p>This subclass is the parent of the 12 casting instructions. It provides
+ common operations on cast instructions.</p>
+ <li><tt><a name="CmpInst">CmpInst</a></tt>
+ <p>This subclass respresents the two comparison instructions,
+ <a href="LangRef.html#i_icmp">ICmpInst</a> (integer opreands), and
+ <a href="LangRef.html#i_fcmp">FCmpInst</a> (floating point operands).</p>
+ <li><tt><a name="TerminatorInst">TerminatorInst</a></tt>
+ <p>This subclass is the parent of all terminator instructions (those which
+ can terminate a block).</p>
+ </ul>
+ </div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Instruction">Important Public Members of the <tt>Instruction</tt>
+ class</a>
+</div>
+<div class="doc_text">
-<li><tt><a href="#BasicBlock">BasicBlock</a> &getEntryNode()</tt><p>
+<ul>
+ <li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt>
+ <p>Returns the <a href="#BasicBlock"><tt>BasicBlock</tt></a> that
+this <tt>Instruction</tt> is embedded into.</p></li>
+ <li><tt>bool mayWriteToMemory()</tt>
+ <p>Returns true if the instruction writes to memory, i.e. it is a
+ <tt>call</tt>,<tt>free</tt>,<tt>invoke</tt>, or <tt>store</tt>.</p></li>
+ <li><tt>unsigned getOpcode()</tt>
+ <p>Returns the opcode for the <tt>Instruction</tt>.</p></li>
+ <li><tt><a href="#Instruction">Instruction</a> *clone() const</tt>
+ <p>Returns another instance of the specified instruction, identical
+in all ways to the original except that the instruction has no parent
+(ie it's not embedded into a <a href="#BasicBlock"><tt>BasicBlock</tt></a>),
+and it has no name</p></li>
+</ul>
-Returns the entry <a href="#BasicBlock"><tt>BasicBlock</tt></a> for the
-function. Because the entry block for the function is always the first block,
-this returns the first block of the <tt>Function</tt>.<p>
+</div>
-<li><tt><a href="#Type">Type</a> *getReturnType()</tt><br>
- <tt><a href="#FunctionType">FunctionType</a> *getFunctionType()</tt><p>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Constant">The <tt>Constant</tt> class and subclasses</a>
+</div>
-This traverses the <a href="#Type"><tt>Type</tt></a> of the <tt>Function</tt>
-and returns the return type of the function, or the <a
-href="#FunctionType"><tt>FunctionType</tt></a> of the actual function.<p>
+<div class="doc_text">
-<li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt><p>
+<p>Constant represents a base class for different types of constants. It
+is subclassed by ConstantInt, ConstantArray, etc. for representing
+the various types of Constants. <a href="#GlobalValue">GlobalValue</a> is also
+a subclass, which represents the address of a global variable or function.
+</p>
-Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> for this
-<tt>Function</tt>.<p>
+</div>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">Important Subclasses of Constant </div>
+<div class="doc_text">
+<ul>
+ <li>ConstantInt : This subclass of Constant represents an integer constant of
+ any width.
+ <ul>
+ <li><tt>const APInt& getValue() const</tt>: Returns the underlying
+ value of this constant, an APInt value.</li>
+ <li><tt>int64_t getSExtValue() const</tt>: Converts the underlying APInt
+ value to an int64_t via sign extension. If the value (not the bit width)
+ of the APInt is too large to fit in an int64_t, an assertion will result.
+ For this reason, use of this method is discouraged.</li>
+ <li><tt>uint64_t getZExtValue() const</tt>: Converts the underlying APInt
+ value to a uint64_t via zero extension. IF the value (not the bit width)
+ of the APInt is too large to fit in a uint64_t, an assertion will result.
+ For this reason, use of this method is discouraged.</li>
+ <li><tt>static ConstantInt* get(const APInt& Val)</tt>: Returns the
+ ConstantInt object that represents the value provided by <tt>Val</tt>.
+ The type is implied as the IntegerType that corresponds to the bit width
+ of <tt>Val</tt>.</li>
+ <li><tt>static ConstantInt* get(const Type *Ty, uint64_t Val)</tt>:
+ Returns the ConstantInt object that represents the value provided by
+ <tt>Val</tt> for integer type <tt>Ty</tt>.</li>
+ </ul>
+ </li>
+ <li>ConstantFP : This class represents a floating point constant.
+ <ul>
+ <li><tt>double getValue() const</tt>: Returns the underlying value of
+ this constant. </li>
+ </ul>
+ </li>
+ <li>ConstantArray : This represents a constant array.
+ <ul>
+ <li><tt>const std::vector<Use> &getValues() const</tt>: Returns
+ a vector of component constants that makeup this array. </li>
+ </ul>
+ </li>
+ <li>ConstantStruct : This represents a constant struct.
+ <ul>
+ <li><tt>const std::vector<Use> &getValues() const</tt>: Returns
+ a vector of component constants that makeup this array. </li>
+ </ul>
+ </li>
+ <li>GlobalValue : This represents either a global variable or a function. In
+ either case, the value is a constant fixed address (after linking).
+ </li>
+</ul>
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a>
-</b></font></td></tr></table><ul>
-
-<tt>#include "<a
-href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classGlobalVariable.html">GlobalVariable Class</a><br>
-Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>, <a
-href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a><p>
-
-Global variables are represented with the (suprise suprise)
-<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 "name" refers to their address). Global variables may have an initial
-value (which must be a <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 class="doc_subsection">
+ <a name="GlobalValue">The <tt>GlobalValue</tt> class</a>
+</div>
+<div class="doc_text">
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_GlobalVariable"><hr size=0>Important Public Members of the
-<tt>GlobalVariable</tt> class</h4><ul>
+<p><tt>#include "<a
+href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br>
+doxygen info: <a href="/doxygen/classllvm_1_1GlobalValue.html">GlobalValue
+Class</a><br>
+Superclasses: <a href="#Constant"><tt>Constant</tt></a>,
+<a href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a></p>
+
+<p>Global values (<a href="#GlobalVariable"><tt>GlobalVariable</tt></a>s or <a
+href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are
+visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s.
+Because they are visible at global scope, they are also subject to linking with
+other globals defined in different translation units. To control the linking
+process, <tt>GlobalValue</tt>s know their linkage rules. Specifically,
+<tt>GlobalValue</tt>s know whether they have internal or external linkage, as
+defined by the <tt>LinkageTypes</tt> enumeration.</p>
-<li><tt>GlobalVariable(const <a href="#Type">Type</a> *Ty, bool isConstant, bool
-isInternal, <a href="#Constant">Constant</a> *Initializer = 0, const std::string
-&Name = "")</tt><p>
+<p>If a <tt>GlobalValue</tt> has internal linkage (equivalent to being
+<tt>static</tt> in C), it is not visible to code outside the current translation
+unit, and does not participate in linking. If it has external linkage, it is
+visible to external code, and does participate in linking. In addition to
+linkage information, <tt>GlobalValue</tt>s keep track of which <a
+href="#Module"><tt>Module</tt></a> they are currently part of.</p>
+
+<p>Because <tt>GlobalValue</tt>s are memory objects, they are always referred to
+by their <b>address</b>. As such, the <a href="#Type"><tt>Type</tt></a> of a
+global is always a pointer to its contents. It is important to remember this
+when using the <tt>GetElementPtrInst</tt> instruction because this pointer must
+be dereferenced first. For example, if you have a <tt>GlobalVariable</tt> (a
+subclass of <tt>GlobalValue)</tt> that is an array of 24 ints, type <tt>[24 x
+i32]</tt>, then the <tt>GlobalVariable</tt> is a pointer to that array. Although
+the address of the first element of this array and the value of the
+<tt>GlobalVariable</tt> are the same, they have different types. The
+<tt>GlobalVariable</tt>'s type is <tt>[24 x i32]</tt>. The first element's type
+is <tt>i32.</tt> Because of this, accessing a global value requires you to
+dereference the pointer with <tt>GetElementPtrInst</tt> first, then its elements
+can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM
+Language Reference Manual</a>.</p>
+
+</div>
-Create a new global variable of the specified type. If <tt>isConstant</tt> is
-true then the global variable will be marked as unchanging for the program, and
-if <tt>isInternal</tt> is true the resultant global variable will have internal
-linkage. Optionally an initializer and name may be specified for the global variable as well.<p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_GlobalValue">Important Public Members of the <tt>GlobalValue</tt>
+ class</a>
+</div>
+<div class="doc_text">
-<li><tt>bool isConstant() const</tt><p>
+<ul>
+ <li><tt>bool hasInternalLinkage() const</tt><br>
+ <tt>bool hasExternalLinkage() const</tt><br>
+ <tt>void setInternalLinkage(bool HasInternalLinkage)</tt>
+ <p> These methods manipulate the linkage characteristics of the <tt>GlobalValue</tt>.</p>
+ <p> </p>
+ </li>
+ <li><tt><a href="#Module">Module</a> *getParent()</tt>
+ <p> This returns the <a href="#Module"><tt>Module</tt></a> that the
+GlobalValue is currently embedded into.</p></li>
+</ul>
-Returns true if this is a global variable is known not to be modified at
-runtime.<p>
+</div>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="Function">The <tt>Function</tt> class</a>
+</div>
-<li><tt>bool hasInitializer()</tt><p>
+<div class="doc_text">
-Returns true if this <tt>GlobalVariable</tt> has an intializer.<p>
+<p><tt>#include "<a
+href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen
+info: <a href="/doxygen/classllvm_1_1Function.html">Function Class</a><br>
+Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
+<a href="#Constant"><tt>Constant</tt></a>,
+<a href="#User"><tt>User</tt></a>,
+<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
+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
+<a href="#SymbolTable"><tt>SymbolTable</tt></a>.</p>
+
+<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
+layed 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
+nodes from a single <tt>Function</tt>. If the <a
+href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that
+the <tt>Function</tt> is actually a function declaration: the actual body of the
+function hasn't been linked in yet.</p>
-<li><tt><a href="#Constant">Constant</a> *getInitializer()</tt><p>
+<p>In addition to a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, the
+<tt>Function</tt> class also keeps track of the list of formal <a
+href="#Argument"><tt>Argument</tt></a>s that the function receives. This
+container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a>
+nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for
+the <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.</p>
-Returns the intial value for a <tt>GlobalVariable</tt>. It is not legal to call
-this method if there is no initializer.<p>
+<p>The <a href="#SymbolTable"><tt>SymbolTable</tt></a> is a very rarely used
+LLVM feature that is only used when you have to look up a value by name. Aside
+from that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used
+internally to make sure that there are not conflicts between the names of <a
+href="#Instruction"><tt>Instruction</tt></a>s, <a
+href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a
+href="#Argument"><tt>Argument</tt></a>s in the function body.</p>
+<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>
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Module">The <tt>Module</tt> class</a>
-</b></font></td></tr></table><ul>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_Function">Important Public Members of the <tt>Function</tt>
+ class</a>
+</div>
-<tt>#include "<a
-href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt></b><br>
-doxygen info: <a href="/doxygen/classModule.html">Module Class</a><p>
+<div class="doc_text">
-The <tt>Module</tt> class represents the top level structure present in LLVM
-programs. An LLVM module is effectively either a translation unit of the
-original program or a combination of several translation units merged by the
-linker. The <tt>Module</tt> class keeps track of a list of <a
-href="#Function"><tt>Function</tt></a>s, a list of <a
-href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a
-href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few
-helpful member functions that try to make common operations easy.<p>
+<ul>
+ <li><tt>Function(const </tt><tt><a href="#FunctionType">FunctionType</a>
+ *Ty, LinkageTypes Linkage, const std::string &N = "", Module* Parent = 0)</tt>
+
+ <p>Constructor used when you need to create new <tt>Function</tt>s to add
+ the the program. The constructor must specify the type of the function to
+ create and what type of linkage the function should have. The <a
+ href="#FunctionType"><tt>FunctionType</tt></a> argument
+ specifies the formal arguments and return value for the function. The same
+ <a href="#FunctionType"><tt>FunctionType</tt></a> value can be used to
+ create multiple functions. The <tt>Parent</tt> argument specifies the Module
+ in which the function is defined. If this argument is provided, the function
+ will automatically be inserted into that module's list of
+ functions.</p></li>
+
+ <li><tt>bool isExternal()</tt>
+
+ <p>Return whether or not the <tt>Function</tt> has a body defined. If the
+ function is "external", it does not have a body, and thus must be resolved
+ by linking with a function defined in a different translation unit.</p></li>
+
+ <li><tt>Function::iterator</tt> - Typedef for basic block list iterator<br>
+ <tt>Function::const_iterator</tt> - Typedef for const_iterator.<br>
+ <tt>begin()</tt>, <tt>end()</tt>
+ <tt>size()</tt>, <tt>empty()</tt>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Module"><hr size=0>Important Public Members of the
-<tt>Module</tt> class</h4><ul>
+ <p>These are forwarding methods that make it easy to access the contents of
+ a <tt>Function</tt> object's <a href="#BasicBlock"><tt>BasicBlock</tt></a>
+ list.</p></li>
-<li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
- <tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
- <tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
- <tt>size()</tt>, <tt>empty()</tt>, <tt>rbegin()</tt>, <tt>rend()</tt><p>
+ <li><tt>Function::BasicBlockListType &getBasicBlockList()</tt>
-These are forwarding methods that make it easy to access the contents of a
-<tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a>
-list.<p>
+ <p>Returns the list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s. This
+ is necessary to use when you need to update the list or perform a complex
+ action that doesn't have a forwarding method.</p></li>
-<li><tt>Module::FunctionListType &getFunctionList()</tt><p>
+ <li><tt>Function::arg_iterator</tt> - Typedef for the argument list
+iterator<br>
+ <tt>Function::const_arg_iterator</tt> - Typedef for const_iterator.<br>
-Returns the list of <a href="#Function"><tt>Function</tt></a>s. This is
-neccesary to use when you need to update the list or perform a complex action
-that doesn't have a forwarding method.<p>
+ <tt>arg_begin()</tt>, <tt>arg_end()</tt>
+ <tt>arg_size()</tt>, <tt>arg_empty()</tt>
-<!-- Global Variable -->
-<hr size=0>
+ <p>These are forwarding methods that make it easy to access the contents of
+ a <tt>Function</tt> object's <a href="#Argument"><tt>Argument</tt></a>
+ list.</p></li>
-<li><tt>Module::giterator</tt> - Typedef for global variable list iterator<br>
- <tt>Module::const_giterator</tt> - Typedef for const_iterator.<br>
- <tt>gbegin()</tt>, <tt>gend()</tt>, <tt>gfront()</tt>, <tt>gback()</tt>,
- <tt>gsize()</tt>, <tt>gempty()</tt>, <tt>grbegin()</tt>, <tt>grend()</tt><p>
+ <li><tt>Function::ArgumentListType &getArgumentList()</tt>
-These are forwarding methods that make it easy to access the contents of a
-<tt>Module</tt> object's <a href="#GlobalVariable"><tt>GlobalVariable</tt></a>
-list.<p>
+ <p>Returns the list of <a href="#Argument"><tt>Argument</tt></a>s. This is
+ necessary to use when you need to update the list or perform a complex
+ action that doesn't have a forwarding method.</p></li>
-<li><tt>Module::GlobalListType &getGlobalList()</tt><p>
+ <li><tt><a href="#BasicBlock">BasicBlock</a> &getEntryBlock()</tt>
-Returns the list of <a href="#GlobalVariable"><tt>GlobalVariable</tt></a>s.
-This is neccesary to use when you need to update the list or perform a complex
-action that doesn't have a forwarding method.<p>
+ <p>Returns the entry <a href="#BasicBlock"><tt>BasicBlock</tt></a> for the
+ function. Because the entry block for the function is always the first
+ block, this returns the first block of the <tt>Function</tt>.</p></li>
+ <li><tt><a href="#Type">Type</a> *getReturnType()</tt><br>
+ <tt><a href="#FunctionType">FunctionType</a> *getFunctionType()</tt>
-<!-- Symbol table stuff -->
-<hr size=0>
+ <p>This traverses the <a href="#Type"><tt>Type</tt></a> of the
+ <tt>Function</tt> and returns the return type of the function, or the <a
+ href="#FunctionType"><tt>FunctionType</tt></a> of the actual
+ function.</p></li>
-<li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt><p>
+ <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
-Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> for
-this <tt>Module</tt>.<p>
+ <p> Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
+ for this <tt>Function</tt>.</p></li>
+</ul>
+</div>
-<!-- Convenience methods -->
-<hr size=0>
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<p><tt>#include "<a
+href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt>
+<br>
+doxygen info: <a href="/doxygen/classllvm_1_1GlobalVariable.html">GlobalVariable
+ Class</a><br>
+Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
+<a href="#Constant"><tt>Constant</tt></a>,
+<a href="#User"><tt>User</tt></a>,
+<a href="#Value"><tt>Value</tt></a></p>
+
+<p>Global variables are represented with the (suprise suprise)
+<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
+"name" refers to their constant address). See
+<a href="#GlobalValue"><tt>GlobalValue</tt></a> for more on this. Global
+variables may have an initial value (which must be a
+<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>
-<li><tt><a href="#Function">Function</a> *getFunction(const std::string &Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt><p>
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection">
+ <a name="m_GlobalVariable">Important Public Members of the
+ <tt>GlobalVariable</tt> class</a>
+</div>
-Look up the specified function in the <tt>Module</tt> <a
-href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return
-<tt>null</tt>.<p>
+<div class="doc_text">
+<ul>
+ <li><tt>GlobalVariable(const </tt><tt><a href="#Type">Type</a> *Ty, bool
+ isConstant, LinkageTypes& Linkage, <a href="#Constant">Constant</a>
+ *Initializer = 0, const std::string &Name = "", Module* Parent = 0)</tt>
-<li><tt><a href="#Function">Function</a> *getOrInsertFunction(const std::string
- &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt><p>
+ <p>Create a new global variable of the specified type. If
+ <tt>isConstant</tt> is true then the global variable will be marked as
+ unchanging for the program. The Linkage parameter specifies the type of
+ linkage (internal, external, weak, linkonce, appending) for the variable. If
+ the linkage is InternalLinkage, WeakLinkage, or LinkOnceLinkage, then
+ the resultant global variable will have internal linkage. AppendingLinkage
+ concatenates together all instances (in different translation units) of the
+ variable into a single variable but is only applicable to arrays. See
+ the <a href="LangRef.html#modulestructure">LLVM Language Reference</a> for
+ further details on linkage types. Optionally an initializer, a name, and the
+ module to put the variable into may be specified for the global variable as
+ well.</p></li>
-Look up the specified function in the <tt>Module</tt> <a
-href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an
-external declaration for the function and return it.<p>
+ <li><tt>bool isConstant() const</tt>
+ <p>Returns true if this is a global variable that is known not to
+ be modified at runtime.</p></li>
-<li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt><p>
+ <li><tt>bool hasInitializer()</tt>
-If there is at least one entry in the <a
-href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a
-href="#Type"><tt>Type</tt></a>, return it. Otherwise return the empty
-string.<p>
+ <p>Returns true if this <tt>GlobalVariable</tt> has an intializer.</p></li>
+ <li><tt><a href="#Constant">Constant</a> *getInitializer()</tt>
-<li><tt>bool addTypeName(const std::string &Name, const <a href="#Type">Type</a>
-*Ty)</tt><p>
+ <p>Returns the intial value for a <tt>GlobalVariable</tt>. It is not legal
+ to call this method if there is no initializer.</p></li>
+</ul>
-Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a> mapping
-<tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this name, true
-is returned and the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is not
-modified.<p>
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Constant">The <tt>Constant</tt> class and subclasses</a>
-</b></font></td></tr></table><ul>
+<div class="doc_subsection">
+ <a name="BasicBlock">The <tt>BasicBlock</tt> class</a>
+</div>
+
+<div class="doc_text">
+
+<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
+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,
+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.
+Matching the language definition, the last element of this list of instructions
+is always a terminator instruction (a subclass of the <a
+href="#TerminatorInst"><tt>TerminatorInst</tt></a> class).</p>
+
+<p>In addition to tracking the list of instructions that make up the block, the
+<tt>BasicBlock</tt> class also keeps track of the <a
+href="#Function"><tt>Function</tt></a> that it is embedded into.</p>
-Constant represents a base class for different types of constants. It is
-subclassed by ConstantBool, ConstantInt, ConstantSInt, ConstantUInt,
-ConstantArray etc for representing the various types of Constants.<p>
+<p>Note that <tt>BasicBlock</tt>s themselves are <a
+href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions
+like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type
+<tt>label</tt>.</p>
+</div>
<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Value"><hr size=0>Important Public Methods</h4><ul>
+<div class="doc_subsubsection">
+ <a name="m_BasicBlock">Important Public Members of the <tt>BasicBlock</tt>
+ class</a>
+</div>
-<li><tt>bool isConstantExpr()</tt>: Returns true if it is a ConstantExpr
+<div class="doc_text">
+<ul>
+<li><tt>BasicBlock(const std::string &Name = "", </tt><tt><a
+ href="#Function">Function</a> *Parent = 0)</tt>
-<hr>
-Important Subclasses of Constant<p>
+<p>The <tt>BasicBlock</tt> constructor is used to create new basic blocks for
+insertion into a function. The constructor optionally takes a name for the new
+block, and a <a href="#Function"><tt>Function</tt></a> to insert it into. If
+the <tt>Parent</tt> parameter is specified, the new <tt>BasicBlock</tt> is
+automatically inserted at the end of the specified <a
+href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be
+manually inserted into the <a href="#Function"><tt>Function</tt></a>.</p></li>
-<ul>
-<li>ConstantSInt : This subclass of Constant represents a signed integer constant.
-<ul>
- <li><tt>int64_t getValue() const</tt>: Returns the underlying value of this constant.
-</ul>
-<li>ConstantUInt : This class represents an unsigned integer.
-<ul>
- <li><tt>uint64_t getValue() const</tt>: Returns the underlying value of this constant.
-</ul>
-<li>ConstantFP : This class represents a floating point constant.
-<ul>
- <li><tt>double getValue() const</tt>: Returns the underlying value of this constant.
-</ul>
-<li>ConstantBool : This represents a boolean constant.
-<ul>
- <li><tt>bool getValue() const</tt>: Returns the underlying value of this constant.
-</ul>
-<li>ConstantArray : This represents a constant array.
-<ul>
- <li><tt>const std::vector<Use> &getValues() const</tt>: Returns a Vecotr of component constants that makeup this array.
-</ul>
-<li>ConstantStruct : This represents a constant struct.
-<ul>
- <li><tt>const std::vector<Use> &getValues() const</tt>: Returns a Vecotr of component constants that makeup this array.
-</ul>
-<li>ConstantPointerRef : This represents a constant pointer value that is initialized to point to a global value, which lies at a constant fixed address.
-<ul>
-<li><tt>GlobalValue *getValue()</tt>: Returns the global value to which this pointer is pointing to.
-</ul>
-</ul>
+<li><tt>BasicBlock::iterator</tt> - Typedef for instruction list iterator<br>
+<tt>BasicBlock::const_iterator</tt> - Typedef for const_iterator.<br>
+<tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
+<tt>size()</tt>, <tt>empty()</tt>
+STL-style functions for accessing the instruction list.
+
+<p>These methods and typedefs are forwarding functions that have the same
+semantics as the standard library methods of the same names. These methods
+expose the underlying instruction list of a basic block in a way that is easy to
+manipulate. To get the full complement of container operations (including
+operations to update the list), you must use the <tt>getInstList()</tt>
+method.</p></li>
+<li><tt>BasicBlock::InstListType &getInstList()</tt>
-<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Type">The <tt>Type</tt> class and Derived Types</a>
-</b></font></td></tr></table><ul>
-
-Type as noted earlier is also a subclass of a Value class. Any primitive
-type (like int, short etc) in LLVM is an instance of Type Class. All
-other types are instances of subclasses of type like FunctionType,
-ArrayType etc. DerivedType is the interface for all such dervied types
-including FunctionType, ArrayType, PointerType, StructType. Types can have
-names. They can be recursive (StructType). There exists exactly one instance
-of any type structure at a time. This allows using pointer equality of Type *s for comparing types.
+<p>This method is used to get access to the underlying container that actually
+holds the Instructions. This method must be used when there isn't a forwarding
+function in the <tt>BasicBlock</tt> class for the operation that you would like
+to perform. Because there are no forwarding functions for "updating"
+operations, you need to use this if you want to update the contents of a
+<tt>BasicBlock</tt>.</p></li>
-<!-- _______________________________________________________________________ -->
-</ul><h4><a name="m_Value"><hr size=0>Important Public Methods</h4><ul>
-
-<li><tt>PrimitiveID getPrimitiveID() const</tt>: Returns the base type of the type.
-<li><tt> bool isSigned() const</tt>: Returns whether an integral numeric type is signed. This is true for SByteTy, ShortTy, IntTy, LongTy. Note that this is not true for Float and Double.
-<li><tt>bool isUnsigned() const</tt>: Returns whether a numeric type is unsigned. This is not quite the complement of isSigned... nonnumeric types return false as they do with isSigned. This returns true for UByteTy, UShortTy, UIntTy, and ULongTy.
-<li><tt> bool isInteger() const</tt>: Equilivent to isSigned() || isUnsigned(), but with only a single virtual function invocation.
-<li><tt>bool isIntegral() const</tt>: Returns true if this is an integral type, which is either Bool type or one of the Integer types.
-
-<li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two floating point types.
-<li><tt>bool isRecursive() const</tt>: Returns rue if the type graph contains a cycle.
-<li><tt>isLosslesslyConvertableTo (const Type *Ty) const</tt>: Return true if this type can be converted to 'Ty' without any reinterpretation of bits. For example, uint to int.
-<li><tt>bool isPrimitiveType() const</tt>: Returns true if it is a primitive type.
-<li><tt>bool isDerivedType() const</tt>: Returns true if it is a derived type.
-<li><tt>const Type * getContainedType (unsigned i) const</tt>:
-This method is used to implement the type iterator. For derived types, this returns the types 'contained' in the derived type, returning 0 when 'i' becomes invalid. This allows the user to iterate over the types in a struct, for example, really easily.
-<li><tt>unsigned getNumContainedTypes() const</tt>: Return the number of types in the derived type.
+<li><tt><a href="#Function">Function</a> *getParent()</tt>
-<p>
+<p> Returns a pointer to <a href="#Function"><tt>Function</tt></a> the block is
+embedded into, or a null pointer if it is homeless.</p></li>
-<hr>
-Derived Types<p>
+<li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt>
-<ul>
-<li>SequentialType : This is subclassed by ArrayType and PointerType
-<ul>
- <li><tt>const Type * getElementType() const</tt>: Returns the type of each of the elements in the sequential type.
-</ul>
-<li>ArrayType : This is a subclass of SequentialType and defines interface for array types.
-<ul>
- <li><tt>unsigned getNumElements() const</tt>: Returns the number of elements in the array.
-</ul>
-<li>PointerType : Subclass of SequentialType for pointer types.
-<li>StructType : subclass of DerivedTypes for struct types
-<li>FunctionType : subclass of DerivedTypes for function types.
+<p> Returns a pointer to the terminator instruction that appears at the end of
+the <tt>BasicBlock</tt>. If there is no terminator instruction, or if the last
+instruction in the block is not a terminator, then a null pointer is
+returned.</p></li>
-<ul>
-
- <li><tt>bool isVarArg() const</tt>: Returns true if its a vararg function
- <li><tt> const Type * getReturnType() const</tt>: Returns the return type of the function.
- <li><tt> const ParamTypes &getParamTypes() const</tt>: Returns a vector of parameter types.
- <li><tt>const Type * getParamType (unsigned i)</tt>: Returns the type of the ith parameter.
- <li><tt> const unsigned getNumParams() const</tt>: Returns the number of formal parameters.
-</ul>
</ul>
-
+</div>
<!-- ======================================================================= -->
-</ul><table width="100%" bgcolor="#441188" border=0 cellpadding=4 cellspacing=0>
-<tr><td> </td><td width="100%">
-<font color="#EEEEFF" face="Georgia,Palatino"><b>
-<a name="Argument">The <tt>Argument</tt> class</a>
-</b></font></td></tr></table><ul>
-
-This subclass of Value defines the interface for incoming formal arguments to a
-function. A Function maitanis a list of its formal arguments. An argument has a
-pointer to the parent Function.
+<div class="doc_subsection">
+ <a name="Argument">The <tt>Argument</tt> class</a>
+</div>
+<div class="doc_text">
+<p>This subclass of Value defines the interface for incoming formal
+arguments to a function. A Function maintains a list of its formal
+arguments. An argument has a pointer to the parent Function.</p>
+</div>
<!-- *********************************************************************** -->
-</ul>
-<!-- *********************************************************************** -->
-
-<hr><font size-1>
-<address>By: <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and
-<a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
-<!-- Created: Tue Aug 6 15:00:33 CDT 2002 -->
-<!-- hhmts start -->
-Last modified: Fri Aug 1 17:26:10 CDT 2003
-<!-- hhmts end -->
-</font></body></html>
+<hr>
+<address>
+ <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
+ src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ <a href="http://validator.w3.org/check/referer"><img
+ src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
+
+ <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>
+ Last modified: $Date$
+</address>
+
+</body>
+</html>
projects / oota-llvm.git / blobdiff