<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>
+ <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt>
option</a>
<ul>
<li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt>
<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>
<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>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="isa">The isa<>, cast<> and dyn_cast<> templates</a>
+ <a name="isa">The <tt>isa<></tt>, <tt>cast<></tt> and
+ <tt>dyn_cast<></tt> templates</a>
</div>
<div class="doc_text">
the fact that <tt>dynamic_cast<></tt> only works on classes that
have a v-table). Because they are used so often, you must know what they
do and how they work. All of these templates are defined in the <a
- href="/doxygen/Casting_8h-source.html"><tt>Support/Casting.h</tt></a>
+ 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>
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:
+ 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>
+ </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>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>
+ <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>
+ </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>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>
+ <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>
+ <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>
+</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
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="DEBUG">The <tt>DEBUG()</tt> macro & <tt>-debug</tt> option</a>
+ <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
</div>
<div class="doc_text">
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">Support/Debug.h</a></tt>"
+<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
<!-- _______________________________________________________________________ -->
<div class="doc_subsubsection">
- <a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE()</tt> and
+ <a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and
the <tt>-debug-only</tt> option</a>
</div>
<p>Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of
a file, to specify the debug type for the entire module (if you do this before
-you <tt>#include "Support/Debug.h"</tt>, you don't have to insert the ugly
+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
<div class="doc_text">
<p>The "<tt><a
-href="/doxygen/Statistic_8h-source.html">Support/Statistic.h</a></tt>" file
+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
</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>
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>
+ <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> std::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
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>
+ <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> std::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>
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>
+ <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()) std::cerr << *it << "\n";<br>}<br></pre>
</div>
<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>
+ <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> std::cerr << "F is used in instruction:\n";<br> std::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
<!-- *********************************************************************** -->
<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">
</body>
</html>
-<!-- vim: sw=2 noai
--->
projects / oota-llvm.git / blobdiff