diff options
Diffstat (limited to 'docs/ProgrammersManual.html')
| -rw-r--r-- | docs/ProgrammersManual.html | 2282 |
1 files changed, 2282 insertions, 0 deletions
diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html new file mode 100644 index 0000000000..e4d50039f6 --- /dev/null +++ b/docs/ProgrammersManual.html @@ -0,0 +1,2282 @@ +<!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> + +<ol> + <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> +<!-- + <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> + <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> </li> + </ul> + </li> + <li><a href="#Statistic">The <tt>Statistic</tt> template & <tt>-stats</tt> +option</a></li> +<!-- + <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="#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> + <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> + </ul> + </li> +<!-- + <li>Working with the Control Flow Graph + <ul> + <li>Accessing predecessors and successors of a <tt>BasicBlock</tt> + <li> + <li> + </ul> +--> + </ul> + </li> + + <li><a href="#advanced">Advanced Topics</a> + <ul> + <li><a href="#TypeResolve">LLVM Type Resolution</a> + <ul> + <li><a href="#BuildRecType">Basic Recursive Type Construction</a></li> + <li><a href="#refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a></li> + <li><a href="#PATypeHolder">The PATypeHolder Class</a></li> + <li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li> + </ul></li> + + <li><a href="#SymbolTable">The <tt>SymbolTable</tt> class </a></li> + </ul></li> + + <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a> + <ul> + <li><a href="#Value">The <tt>Value</tt> class</a> + <ul> + <li><a href="#User">The <tt>User</tt> class</a> + <ul> + <li><a href="#Instruction">The <tt>Instruction</tt> class</a> + <ul> + <li><a href="#GetElementPtrInst">The <tt>GetElementPtrInst</tt> class</a></li> + </ul> + </li> + <li><a href="#Module">The <tt>Module</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="#BasicBlock">The <tt>BasicBlock</tt>class</a></li> + <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="#Type">The <tt>Type</tt> class</a> </li> + <li><a href="#Argument">The <tt>Argument</tt> class</a></li> + </ul> + </li> + </ul> + </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> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="introduction">Introduction </a> +</div> +<!-- *********************************************************************** --> + +<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> + +<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>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> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="general">General Information</a> +</div> +<!-- *********************************************************************** --> + +<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> + +<!-- ======================================================================= --> +<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> + +<li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an +O'Reilly book in the making. It has a decent +Standard Library +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></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>.</li> + +<li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++ +Page</a></li> + +<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> + +</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> + +</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> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="apis">Important and useful LLVM APIs</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>Here we highlight some LLVM APIs that are generally useful and good to +know about when writing transformations.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="isa">The isa<>, cast<> and dyn_cast<> 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> + +<dl> + <dt><tt>isa<></tt>: </dt> + + <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).</dd> + + <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: + + <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> + + </dd> + + <dt><tt>dyn_cast<></tt>:</dt> + + <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: + + <pre> + if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast<<a href="#AllocationInst">AllocationInst</a>>(Val)) { + ... + } + </pre> + + <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>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.</dd> + + <dt><tt>dyn_cast_or_null<></tt>: </dt> + + <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.</dd> + + </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> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="DEBUG">The <tt>DEBUG()</tt> macro & <tt>-debug</tt> option</a> +</div> + +<div class="doc_text"> + +<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> + +<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:</p> + + <pre> ... <br> DEBUG(std::cerr << "I am here!\n");<br> ...<br></pre> + +<p>Then you can run your pass like this:</p> + + <pre> $ opt < a.bc > /dev/null -mypass<br> <no output><br> $ opt < a.bc > /dev/null -mypass -debug<br> I am here!<br> $<br></pre> + +<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> + +<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> + +</div> + +<!-- _______________________________________________________________________ --> +<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> + +<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> + + <pre> ...<br> DEBUG(std::cerr << "No debug type\n");<br> #undef DEBUG_TYPE<br> #define DEBUG_TYPE "foo"<br> DEBUG(std::cerr << "'foo' debug type\n");<br> #undef DEBUG_TYPE<br> #define DEBUG_TYPE "bar"<br> DEBUG(std::cerr << "'bar' debug type\n");<br> #undef DEBUG_TYPE<br> #define DEBUG_TYPE ""<br> DEBUG(std::cerr << "No debug type (2)\n");<br> ...<br></pre> + +<p>Then you can run your pass like this:</p> + + <pre> $ opt < a.bc > /dev/null -mypass<br> <no output><br> $ opt < a.bc > /dev/null -mypass -debug<br> No debug type<br> 'foo' debug type<br> 'bar' debug type<br> No debug type (2)<br> $ opt < a.bc > /dev/null -mypass -debug-only=foo<br> 'foo' debug type<br> $ opt < a.bc > /dev/null -mypass -debug-only=bar<br> 'bar' debug type<br> $<br></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 "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> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Statistic">The <tt>Statistic</tt> template & <tt>-stats</tt> + option</a> +</div> + +<div class="doc_text"> + +<p>The "<tt><a +href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file +provides a template 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> + +<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 +keep track of this information, and the calculated information is presented in a +uniform manner with the rest of the passes being executed.</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: + <pre>static Statistic<> NumXForms("mypassname", "The # of times I did stuff");<br></pre> + + <p>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></li> + + <li>Whenever you make a transformation, bump the counter: + <pre> ++NumXForms; // I did stuff<br></pre> + </li> + </ol> + + <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> + + <pre> $ opt -stats -mypassname < program.bc > /dev/null<br> ... statistic output ...<br></pre> + + <p> When running <tt>gccas</tt> on a C file from the SPEC benchmark +suite, it gives a report that looks like this:</p> + + <pre> 7646 bytecodewriter - Number of normal instructions<br> 725 bytecodewriter - Number of oversized instructions<br> 129996 bytecodewriter - Number of bytecode bytes written<br> 2817 raise - Number of insts DCEd or constprop'd<br> 3213 raise - Number of cast-of-self removed<br> 5046 raise - Number of expression trees converted<br> 75 raise - Number of other getelementptr's formed<br> 138 raise - Number of load/store peepholes<br> 42 deadtypeelim - Number of unused typenames removed from symtab<br> 392 funcresolve - Number of varargs functions resolved<br> 27 globaldce - Number of global variables removed<br> 2 adce - Number of basic blocks removed<br> 134 cee - Number of branches revectored<br> 49 cee - Number of setcc instruction eliminated<br> 532 gcse - Number of loads removed<br> 2919 gcse - Number of instructions removed<br> 86 indvars - Number of canonical indvars added<br> 87 indvars - Number of aux indvars removed<br> 25 instcombine - Number of dead inst eliminate<br> 434 instcombine - Number of insts combined<br> 248 licm - Number of load insts hoisted<br> 1298 licm - Number of insts hoisted to a loop pre-header<br> 3 licm - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)<br> 75 mem2reg - Number of alloca's promoted<br> 1444 cfgsimplify - Number of blocks simplified<br></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> + +</div> + +<!-- ======================================================================= --> +<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 whereever 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> + +</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> + + <pre> // func is a pointer to a Function instance<br> for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i) {<br><br> // print out the name of the basic block if it has one, and then the<br> // number of instructions that it contains<br><br> cerr << "Basic block (name=" << i->getName() << ") has " <br> << i->size() << " instructions.\n";<br> }<br></pre> + +<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> + +<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& + std::cerr << *i << "\n"; +</pre> + +<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>std::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> + + <pre>#include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"<br>...<br>// Suppose F is a ptr to a function<br>for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)<br> cerr << *i << "\n";<br></pre> +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: + <pre>std::set<Instruction*> worklist;<br>worklist.insert(inst_begin(F), inst_end(F));<br></pre> + +<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> + + <pre> Instruction& inst = *i; // grab reference to instruction reference<br> Instruction* pinst = &*i; // grab pointer to instruction reference<br> const Instruction& inst = *j;<br></pre> + +<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> + + <pre>Instruction* pinst = &*i;</pre> + +<p>is semantically equivalent to</p> + + <pre>Instruction* pinst = i;</pre> + +<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> + + <pre>void printNextInstruction(Instruction* inst) {<br> BasicBlock::iterator it(inst);<br> ++it; // after this line, it refers to the instruction after *inst.<br> if (it != inst->getParent()->end()) cerr << *it << "\n";<br>}<br></pre> + +</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 pseudocode, this +is what we want to do:</p> + + <pre>initialize callCounter to zero<br>for each Function f in the Module<br> for each BasicBlock b in f<br> for each Instruction i in b<br> if (i is a CallInst and calls the given function)<br> increment callCounter<br></pre> + +<p>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...):</p> + + <pre>Function* targetFunc = ...;<br><br>class OurFunctionPass : public FunctionPass {<br> public:<br> OurFunctionPass(): callCounter(0) { }<br><br> virtual runOnFunction(Function& F) {<br> for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {<br> for (BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) {<br> if (<a + href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a + href="#CallInst">CallInst</a>>(&*i)) {<br> // we know we've encountered a call instruction, so we<br> // need to determine if it's a call to the<br> // function pointed to by m_func or not.<br> <br> if (callInst->getCalledFunction() == targetFunc)<br> ++callCounter;<br> }<br> }<br> }<br> <br> private:<br> unsigned callCounter;<br>};<br></pre> + +</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.cs.uiuc.edu/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/structllvm_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> + + <pre>Function* F = ...;<br><br>for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i) {<br> if (Instruction *Inst = dyn_cast<Instruction>(*i)) {<br> cerr << "F is used in instruction:\n";<br> cerr << *Inst << "\n";<br> }<br>}<br></pre> + +<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> + + <pre>Instruction* pi = ...;<br><br>for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) {<br> Value* v = *i;<br> ...<br>}<br></pre> + +<!-- + 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> + +<pre>AllocaInst* ai = new AllocaInst(Type::IntTy);</pre> + +<p>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/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 +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:</p> + + <pre>AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc");</pre> + +<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 runtime 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> + + <pre> BasicBlock *pb = ...;<br> Instruction *pi = ...;<br> Instruction *newInst = new Instruction(...);<br> pb->getInstList().insert(pi, newInst); // inserts newInst before pi in pb<br></pre> + + <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> + + <pre> BasicBlock *pb = ...;<br> Instruction *newInst = new Instruction(...);<br> pb->getInstList().push_back(newInst); // appends newInst to pb<br></pre> + + <p>becomes: </p> + + <pre> BasicBlock *pb = ...;<br> Instruction *newInst = new Instruction(..., pb);<br></pre> + + <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> + + <pre> Instruction *pi = ...;<br> Instruction *newInst = new Instruction(...);<br> pi->getParent()->getInstList().insert(pi, newInst);<br></pre> + + <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> + + <pre>Instruction* pi = ...;<br>Instruction* newInst = new Instruction(..., pi);<br></pre> + + <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> + + <pre> <a href="#Instruction">Instruction</a> *I = .. ;<br> <a + href="#BasicBlock">BasicBlock</a> *BB = I->getParent();<br> BB->getInstList().erase(I);<br></pre> + +</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> + + <pre>AllocaInst* instToReplace = ...;<br>BasicBlock::iterator ii(instToReplace);<br>ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii,<br> Constant::getNullValue(PointerType::get(Type::IntTy)));<br></pre></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> + + <pre>AllocaInst* instToReplace = ...;<br>BasicBlock::iterator ii(instToReplace);<br>ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii,<br> new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt"));<br></pre></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/structllvm_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_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 bytecode 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, int }</tt>"). +Third, a concrete type is a type that is not an abstract type (e.g. "<tt>[ int, +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> + +<pre> + %mylist = type { %mylist*, int } +</pre> + +<p> +To build this, use the following LLVM APIs: +</p> + +<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*, int }". 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> + +<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 +ref="#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*, int}" 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. The <a href="#SymbolTable">SymbolTable</a> class, for example, needs +move and potentially merge type planes in its representation when a pointer +changes.</p> + +<p> +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 an opaque objects +somewhere) can never be refined. +</p> +</div> + + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="SymbolTable">The <tt>SymbolTable</tt> class</a> +</div> + +<div class="doc_text"> +<p>This 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 definitions. The symbol table can +provide a name for any <a href="#Value"><tt>Value</tt></a> or <a +href="#Type"><tt>Type</tt></a>. <tt>SymbolTable</tt> is an abstract data +type. It hides the data it contains and provides access to it through a +controlled interface.</p> + +<p>Note that the symbol table class is 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> + +<p>To use the <tt>SymbolTable</tt> well, you need to understand the +structure of the information it holds. The class contains two +<tt>std::map</tt> objects. The first, <tt>pmap</tt>, is a map of +<tt>Type*</tt> to maps of name (<tt>std::string</tt>) to <tt>Value*</tt>. +The second, <tt>tmap</tt>, is a map of names to <tt>Type*</tt>. Thus, Values +are stored in two-dimensions and accessed by <tt>Type</tt> and name. Types, +however, are stored in a single dimension and accessed only by name.</p> + +<p>The interface of this class provides three basic types of operations: +<ol> + <li><em>Accessors</em>. Accessors provide read-only access to information + such as finding a value for a name with the + <a href="#SymbolTable_lookup">lookup</a> method.</li> + <li><em>Mutators</em>. Mutators allow the user to add information to the + <tt>SymbolTable</tt> with methods like + <a href="#SymbolTable_insert"><tt>insert</tt></a>.</li> + <li><em>Iterators</em>. Iterators allow the user to traverse the content + of the symbol table in well defined ways, such as the method + <a href="#SymbolTable_type_begin"><tt>type_begin</tt></a>.</li> +</ol> + +<h3>Accessors</h3> +<dl> + <dt><tt>Value* lookup(const Type* Ty, const std::string& name) const</tt>: + </dt> + <dd>The <tt>lookup</tt> method searches the type plane given by the + <tt>Ty</tt> parameter for a <tt>Value</tt> with the provided <tt>name</tt>. + If a suitable <tt>Value</tt> is not found, null is returned.</dd> + + <dt><tt>Type* lookupType( const std::string& name) const</tt>:</dt> + <dd>The <tt>lookupType</tt> method searches through the types for a + <tt>Type</tt> with the provided <tt>name</tt>. If a suitable <tt>Type</tt> + is not found, null is returned.</dd> + + <dt><tt>bool hasTypes() const</tt>:</dt> + <dd>This function returns true if an entry has been made into the type + map.</dd> + + <dt><tt>bool isEmpty() const</tt>:</dt> + <dd>This function returns true if both the value and types maps are + empty</dd> +</dl> + +<h3>Mutators</h3> +<dl> + <dt><tt>void insert(Value *Val)</tt>:</dt> + <dd>This method adds the provided value to the symbol table. The Value must + have both a name and a type which are extracted and used to place the value + in the correct type plane under the value's name.</dd> + + <dt><tt>void insert(const std::string& Name, Value *Val)</tt>:</dt> + <dd> Inserts a constant or type into the symbol table with the specified + name. There can be a many to one mapping between names and constants + or types.</dd> + + <dt><tt>void insert(const std::string& Name, Type *Typ)</tt>:</dt> + <dd> Inserts a type into the symbol table with the specified name. There + can be a many-to-one mapping between names and types. This method + allows a type with an existing entry in the symbol table to get + a new name.</dd> + + <dt><tt>void remove(Value* Val)</tt>:</dt> + <dd> This method removes a named value from the symbol table. The + type and name of the Value are extracted from \p N and used to + lookup the Value in the correct type plane. If the Value is + not in the symbol table, this method silently ignores the + request.</dd> + + <dt><tt>void remove(Type* Typ)</tt>:</dt> + <dd> This method removes a named type from the symbol table. The + name of the type is extracted from \P T and used to look up + the Type in the type map. If the Type is not in the symbol + table, this method silently ignores the request.</dd> + + <dt><tt>Value* remove(const std::string& Name, Value *Val)</tt>:</dt> + <dd> Remove a constant or type with the specified name from the + symbol table.</dd> + + <dt><tt>Type* remove(const std::string& Name, Type* T)</tt>:</dt> + <dd> Remove a type with the specified name from the symbol table. + Returns the removed Type.</dd> + + <dt><tt>Value *value_remove(const value_iterator& It)</tt>:</dt> + <dd> Removes a specific value from the symbol table. + Returns the removed value.</dd> + + <dt><tt>bool strip()</tt>:</dt> + <dd> This method will strip the symbol table of its names leaving + the type and values. </dd> + + <dt><tt>void clear()</tt>:</dt> + <dd>Empty the symbol table completely.</dd> +</dl> + +<h3>Iteration</h3> +<p>The following functions describe three types of iterators you can obtain +the beginning or end of the sequence for both const and non-const. It is +important to keep track of the different kinds of iterators. There are +three idioms worth pointing out:</p> +<table> + <tr><th>Units</th><th>Iterator</th><th>Idiom</th></tr> + <tr> + <td align="left">Planes Of name/Value maps</td><td>PI</td> + <td align="left"><pre><tt> +for (SymbolTable::plane_const_iterator PI = ST.plane_begin(), + PE = ST.plane_end(); PI != PE; ++PI ) { + PI->first // This is the Type* of the plane + PI->second // This is the SymbolTable::ValueMap of name/Value pairs + </tt></pre></td> + </tr> + <tr> + <td align="left">All name/Type Pairs</td><td>TI</td> + <td align="left"><pre><tt> +for (SymbolTable::type_const_iterator TI = ST.type_begin(), + TE = ST.type_end(); TI != TE; ++TI ) + TI->first // This is the name of the type + TI->second // This is the Type* value associated with the name + </tt></pre></td> + </tr> + <tr> + <td align="left">name/Value pairs in a plane</td><td>VI</td> + <td align="left"><pre><tt> +for (SymbolTable::value_const_iterator VI = ST.value_begin(SomeType), + VE = ST.value_end(SomeType); VI != VE; ++VI ) + VI->first // This is the name of the Value + VI->second // This is the Value* value associated with the name + </tt></pre></td> + </tr> +</table> + +<p>Using the recommended iterator names and idioms will help you avoid +making mistakes. Of particular note, make sure that whenever you use +value_begin(SomeType) that you always compare the resulting iterator +with value_end(SomeType) not value_end(SomeOtherType) or else you +will loop infinitely.</p> + +<dl> + + <dt><tt>plane_iterator plane_begin()</tt>:</dt> + <dd>Get an iterator that starts at the beginning of the type planes. + The iterator will iterate over the Type/ValueMap pairs in the + type planes. </dd> + + <dt><tt>plane_const_iterator plane_begin() const</tt>:</dt> + <dd>Get a const_iterator that starts at the beginning of the type + planes. The iterator will iterate over the Type/ValueMap pairs + in the type planes. </dd> + + <dt><tt>plane_iterator plane_end()</tt>:</dt> + <dd>Get an iterator at the end of the type planes. This serves as + the marker for end of iteration over the type planes.</dd> + + <dt><tt>plane_const_iterator plane_end() const</tt>:</dt> + <dd>Get a const_iterator at the end of the type planes. This serves as + the marker for end of iteration over the type planes.</dd> + + <dt><tt>value_iterator value_begin(const Type *Typ)</tt>:</dt> + <dd>Get an iterator that starts at the beginning of a type plane. + The iterator will iterate over the name/value pairs in the type plane. + Note: The type plane must already exist before using this.</dd> + + <dt><tt>value_const_iterator value_begin(const Type *Typ) const</tt>:</dt> + <dd>Get a const_iterator that starts at the beginning of a type plane. + The iterator will iterate over the name/value pairs in the type plane. + Note: The type plane must already exist before using this.</dd> + + <dt><tt>value_iterator value_end(const Type *Typ)</tt>:</dt> + <dd>Get an iterator to the end of a type plane. This serves as the marker + for end of iteration of the type plane. + Note: The type plane must already exist before using this.</dd> + + <dt><tt>value_const_iterator value_end(const Type *Typ) const</tt>:</dt> + <dd>Get a const_iterator to the end of a type plane. This serves as the + marker for end of iteration of the type plane. + Note: the type plane must already exist before using this.</dd> + + <dt><tt>type_iterator type_begin()</tt>:</dt> + <dd>Get an iterator to the start of the name/Type map.</dd> + + <dt><tt>type_const_iterator type_begin() cons</tt>:</dt> + <dd> Get a const_iterator to the start of the name/Type map.</dd> + + <dt><tt>type_iterator type_end()</tt>:</dt> + <dd>Get an iterator to the end of the name/Type map. This serves as the + marker for end of iteration of the types.</dd> + + <dt><tt>type_const_iterator type_end() const</tt>:</dt> + <dd>Get a const-iterator to the end of the name/Type map. This serves + as the marker for end of iteration of the types.</dd> + + <dt><tt>plane_const_iterator find(const Type* Typ ) const</tt>:</dt> + <dd>This method returns a plane_const_iterator for iteration over + the type planes starting at a specific plane, given by \p Ty.</dd> + + <dt><tt>plane_iterator find( const Type* Typ </tt>:</dt> + <dd>This method returns a plane_iterator for iteration over the + type planes starting at a specific plane, given by \p Ty.</dd> + +</dl> +</div> + + + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<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> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Value">The <tt>Value</tt> class</a> +</div> + +<div> + +<p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt> +<br> +doxygen info: <a href="/doxygen/structllvm_1_1Value.html">Value Class</a></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> + +<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> + + <pre> %<b>foo</b> = add int 1, 2<br></pre> + +<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> + +<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> + +</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> + <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> + + <pre> Inst->replaceAllUsesWith(ConstVal);<br></pre> +</ul> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="User">The <tt>User</tt> class</a> +</div> + +<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> + +<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> + +<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> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_User">Important Public Members of the <tt>User</tt> class</a> +</div> + +<div class="doc_text"> + +<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> + +<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> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Instruction">The <tt>Instruction</tt> class</a> +</div> + +<div class="doc_text"> + +<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> + +<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> + +<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::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 confuses doxygen, so these enum values don't show up correctly in the +<a href="/doxygen/classllvm_1_1Instruction.html">doxygen output</a>.</p> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Instruction">Important Public Members of the <tt>Instruction</tt> + class</a> +</div> + +<div class="doc_text"> + +<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> + +</div> + +<!-- ======================================================================= --> +<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> + +<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> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_BasicBlock">Important Public Members of the <tt>BasicBlock</tt> + class</a> +</div> + +<div class="doc_text"> + +<ul> + +<li><tt>BasicBlock(const std::string &Name = "", </tt><tt><a + href="#Function">Function</a> *Parent = 0)</tt> + +<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> + +<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> + +<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> + +<li><tt><a href="#Function">Function</a> *getParent()</tt> + +<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> + +<li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt> + +<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> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="GlobalValue">The <tt>GlobalValue</tt> class</a> +</div> + +<div class="doc_text"> + +<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="#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> + +<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 +int]</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 int]</tt>. The first element's type +is <tt>int.</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> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_GlobalValue">Important Public Members of the <tt>GlobalValue</tt> + class</a> +</div> + +<div class="doc_text"> + +<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> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Function">The <tt>Function</tt> class</a> +</div> + +<div class="doc_text"> + +<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="#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> + +<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> + +<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> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Function">Important Public Members of the <tt>Function</tt> + class</a> +</div> + +<div class="doc_text"> + +<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="#FunctionTypel"><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> + + <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>Function::BasicBlockListType &getBasicBlockList()</tt> + + <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>Function::arg_iterator</tt> - Typedef for the argument list +iterator<br> + <tt>Function::const_arg_iterator</tt> - Typedef for const_iterator.<br> + + <tt>arg_begin()</tt>, <tt>arg_end()</tt> + <tt>arg_size()</tt>, <tt>arg_empty()</tt> + + <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>Function::ArgumentListType &getArgumentList()</tt> + + <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><a href="#BasicBlock">BasicBlock</a> &getEntryBlock()</tt> + + <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> + + <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> Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> + for this <tt>Function</tt>.</p></li> +</ul> + +</div> + +<!-- ======================================================================= --> +<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="#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 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> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_GlobalVariable">Important Public Members of the + <tt>GlobalVariable</tt> class</a> +</div> + +<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> + + <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> + + <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>bool hasInitializer()</tt> + + <p>Returns true if this <tt>GlobalVariable</tt> has an intializer.</p></li> + + <li><tt><a href="#Constant">Constant</a> *getInitializer()</tt> + + <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> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Module">The <tt>Module</tt> class</a> +</div> + +<div class="doc_text"> + +<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> + +<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> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Module">Important Public Members of the <tt>Module</tt> class</a> +</div> + +<div class="doc_text"> + +<ul> + <li><tt>Module::Module(std::string name = "")</tt></li> +</ul> + +<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> + +<ul> + <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>size()</tt>, <tt>empty()</tt> + + <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>Module::FunctionListType &getFunctionList()</tt> + + <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> + + <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> + + <li><tt>Module::GlobalListType &getGlobalList()</tt> + + <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> + +<hr> + +<ul> + <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt> + + <p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> + for this <tt>Module</tt>.</p> + + <p><!-- Convenience methods --></p></li> +</ul> + +<hr> + +<ul> + <li><tt><a href="#Function">Function</a> *getFunction(const std::string + &Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt> + + <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> *getOrInsertFunction(const + std::string &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt> + + <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>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt> + + <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> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Constant">The <tt>Constant</tt> class and subclasses</a> +</div> + +<div class="doc_text"> + +<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> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Constant">Important Public Methods</a> +</div> +<div class="doc_text"> +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection">Important Subclasses of Constant </div> +<div class="doc_text"> +<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. </li> + </ul> + </li> + <li>ConstantUInt : This class represents an unsigned integer. + <ul> + <li><tt>uint64_t getValue() const</tt>: Returns the underlying value of + this constant. </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>ConstantBool : This represents a boolean constant. + <ul> + <li><tt>bool 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> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="Type">The <tt>Type</tt> class and Derived Types</a> +</div> + +<div class="doc_text"> + +<p>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> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Value">Important Public Methods</a> +</div> + +<div class="doc_text"> + +<ul> + + <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> + + <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> + + <li><tt>bool isInteger() const</tt>: Equivalent to isSigned() || isUnsigned().</li> + + <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> + + <li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two + floating point types.</li> + + <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 or one pointer type to another.</li> +</ul> +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="m_Value">Important Derived Types</a> +</div> +<div class="doc_text"> +<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. </li> + </ul> + </li> + <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. </li> + </ul> + </li> + <li>PointerType : Subclass of SequentialType for pointer types. </li> + <li>StructType : subclass of DerivedTypes for struct types </li> + <li>FunctionType : 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> + </li> +</ul> +</div> + +<!-- ======================================================================= --> +<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> + +<!-- *********************************************************************** --> +<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.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br> + Last modified: $Date$ +</address> + +</body> +</html> |