docs/ProgrammersManual.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <meta http-equiv="Content-type" content="text/html;charset=UTF-8">
   6   <title>LLVM Programmer's Manual</title>
   7   <link rel="stylesheet" href="_static/llvm.css" type="text/css">
   8 </head>
   9 <body>
  10
  11 <h1>
  12   LLVM Programmer's Manual
  13 </h1>
  14
  15 <ol>
  16   <li><a href="#introduction">Introduction</a></li>
  17   <li><a href="#general">General Information</a>
  18     <ul>
  19       <li><a href="#stl">The C++ Standard Template Library</a></li>
  20 <!--
  21       <li>The <tt>-time-passes</tt> option</li>
  22       <li>How to use the LLVM Makefile system</li>
  23       <li>How to write a regression test</li>
  24
  25 -->
  26     </ul>
  27   </li>
  28   <li><a href="#apis">Important and useful LLVM APIs</a>
  29     <ul>
  30       <li><a href="#isa">The <tt>isa&lt;&gt;</tt>, <tt>cast&lt;&gt;</tt>
  31 and <tt>dyn_cast&lt;&gt;</tt> templates</a> </li>
  32       <li><a href="#string_apis">Passing strings (the <tt>StringRef</tt>
  33 and <tt>Twine</tt> classes)</a>
  34         <ul>
  35           <li><a href="#StringRef">The <tt>StringRef</tt> class</a> </li>
  36           <li><a href="#Twine">The <tt>Twine</tt> class</a> </li>
  37         </ul>
  38       </li>
  39       <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt>
  40 option</a>
  41         <ul>
  42           <li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt>
  43 and the <tt>-debug-only</tt> option</a> </li>
  44         </ul>
  45       </li>
  46       <li><a href="#Statistic">The <tt>Statistic</tt> class &amp; <tt>-stats</tt>
  47 option</a></li>
  48 <!--
  49       <li>The <tt>InstVisitor</tt> template
  50       <li>The general graph API
  51 -->
  52       <li><a href="#ViewGraph">Viewing graphs while debugging code</a></li>
  53     </ul>
  54   </li>
  55   <li><a href="#datastructure">Picking the Right Data Structure for a Task</a>
  56     <ul>
  57     <li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
  58     <ul>
  59       <li><a href="#dss_arrayref">llvm/ADT/ArrayRef.h</a></li>
  60       <li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li>
  61       <li><a href="#dss_heaparrays">Heap Allocated Arrays</a></li>
  62       <li><a href="#dss_tinyptrvector">"llvm/ADT/TinyPtrVector.h"</a></li>
  63       <li><a href="#dss_smallvector">"llvm/ADT/SmallVector.h"</a></li>
  64       <li><a href="#dss_vector">&lt;vector&gt;</a></li>
  65       <li><a href="#dss_deque">&lt;deque&gt;</a></li>
  66       <li><a href="#dss_list">&lt;list&gt;</a></li>
  67       <li><a href="#dss_ilist">llvm/ADT/ilist.h</a></li>
  68       <li><a href="#dss_packedvector">llvm/ADT/PackedVector.h</a></li>
  69       <li><a href="#dss_other">Other Sequential Container Options</a></li>
  70     </ul></li>
  71     <li><a href="#ds_string">String-like containers</a>
  72     <ul>
  73       <li><a href="#dss_stringref">llvm/ADT/StringRef.h</a></li>
  74       <li><a href="#dss_twine">llvm/ADT/Twine.h</a></li>
  75       <li><a href="#dss_smallstring">llvm/ADT/SmallString.h</a></li>
  76       <li><a href="#dss_stdstring">std::string</a></li>
  77     </ul></li>
  78     <li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
  79     <ul>
  80       <li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li>
  81       <li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li>
  82       <li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li>
  83       <li><a href="#dss_denseset">"llvm/ADT/DenseSet.h"</a></li>
  84       <li><a href="#dss_sparseset">"llvm/ADT/SparseSet.h"</a></li>
  85       <li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li>
  86       <li><a href="#dss_set">&lt;set&gt;</a></li>
  87       <li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li>
  88       <li><a href="#dss_uniquevector">"llvm/ADT/UniqueVector.h"</a></li>
  89       <li><a href="#dss_immutableset">"llvm/ADT/ImmutableSet.h"</a></li>
  90       <li><a href="#dss_otherset">Other Set-Like Container Options</a></li>
  91     </ul></li>
  92     <li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
  93     <ul>
  94       <li><a href="#dss_sortedvectormap">A sorted 'vector'</a></li>
  95       <li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li>
  96       <li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li>
  97       <li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li>
  98       <li><a href="#dss_valuemap">"llvm/ADT/ValueMap.h"</a></li>
  99       <li><a href="#dss_intervalmap">"llvm/ADT/IntervalMap.h"</a></li>
 100       <li><a href="#dss_map">&lt;map&gt;</a></li>
 101       <li><a href="#dss_mapvector">"llvm/ADT/MapVector.h"</a></li>
 102       <li><a href="#dss_inteqclasses">"llvm/ADT/IntEqClasses.h"</a></li>
 103       <li><a href="#dss_immutablemap">"llvm/ADT/ImmutableMap.h"</a></li>
 104       <li><a href="#dss_othermap">Other Map-Like Container Options</a></li>
 105     </ul></li>
 106     <li><a href="#ds_bit">BitVector-like containers</a>
 107     <ul>
 108       <li><a href="#dss_bitvector">A dense bitvector</a></li>
 109       <li><a href="#dss_smallbitvector">A "small" dense bitvector</a></li>
 110       <li><a href="#dss_sparsebitvector">A sparse bitvector</a></li>
 111     </ul></li>
 112   </ul>
 113   </li>
 114   <li><a href="#common">Helpful Hints for Common Operations</a>
 115     <ul>
 116       <li><a href="#inspection">Basic Inspection and Traversal Routines</a>
 117         <ul>
 118           <li><a href="#iterate_function">Iterating over the <tt>BasicBlock</tt>s
 119 in a <tt>Function</tt></a> </li>
 120           <li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s
 121 in a <tt>BasicBlock</tt></a> </li>
 122           <li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s
 123 in a <tt>Function</tt></a> </li>
 124           <li><a href="#iterate_convert">Turning an iterator into a
 125 class pointer</a> </li>
 126           <li><a href="#iterate_complex">Finding call sites: a more
 127 complex example</a> </li>
 128           <li><a href="#calls_and_invokes">Treating calls and invokes
 129 the same way</a> </li>
 130           <li><a href="#iterate_chains">Iterating over def-use &amp;
 131 use-def chains</a> </li>
 132           <li><a href="#iterate_preds">Iterating over predecessors &amp;
 133 successors of blocks</a></li>
 134         </ul>
 135       </li>
 136       <li><a href="#simplechanges">Making simple changes</a>
 137         <ul>
 138           <li><a href="#schanges_creating">Creating and inserting new
 139                  <tt>Instruction</tt>s</a> </li>
 140           <li><a href="#schanges_deleting">Deleting              <tt>Instruction</tt>s</a> </li>
 141           <li><a href="#schanges_replacing">Replacing an                 <tt>Instruction</tt>
 142 with another <tt>Value</tt></a> </li>
 143           <li><a href="#schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a> </li>
 144         </ul>
 145       </li>
 146       <li><a href="#create_types">How to Create Types</a></li>
 147 <!--
 148     <li>Working with the Control Flow Graph
 149     <ul>
 150       <li>Accessing predecessors and successors of a <tt>BasicBlock</tt>
 151       <li>
 152       <li>
 153     </ul>
 154 -->
 155     </ul>
 156   </li>
 157
 158   <li><a href="#threading">Threads and LLVM</a>
 159   <ul>
 160     <li><a href="#startmultithreaded">Entering and Exiting Multithreaded Mode
 161         </a></li>
 162     <li><a href="#shutdown">Ending execution with <tt>llvm_shutdown()</tt></a></li>
 163     <li><a href="#managedstatic">Lazy initialization with <tt>ManagedStatic</tt></a></li>
 164     <li><a href="#llvmcontext">Achieving Isolation with <tt>LLVMContext</tt></a></li>
 165     <li><a href="#jitthreading">Threads and the JIT</a></li>
 166   </ul>
 167   </li>
 168
 169   <li><a href="#advanced">Advanced Topics</a>
 170   <ul>
 171
 172   <li><a href="#SymbolTable">The <tt>ValueSymbolTable</tt> class</a></li>
 173   <li><a href="#UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a></li>
 174   </ul></li>
 175
 176   <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a>
 177     <ul>
 178       <li><a href="#Type">The <tt>Type</tt> class</a> </li>
 179       <li><a href="#Module">The <tt>Module</tt> class</a></li>
 180       <li><a href="#Value">The <tt>Value</tt> class</a>
 181       <ul>
 182         <li><a href="#User">The <tt>User</tt> class</a>
 183         <ul>
 184           <li><a href="#Instruction">The <tt>Instruction</tt> class</a></li>
 185           <li><a href="#Constant">The <tt>Constant</tt> class</a>
 186           <ul>
 187             <li><a href="#GlobalValue">The <tt>GlobalValue</tt> class</a>
 188             <ul>
 189               <li><a href="#Function">The <tt>Function</tt> class</a></li>
 190               <li><a href="#GlobalVariable">The <tt>GlobalVariable</tt> class</a></li>
 191             </ul>
 192             </li>
 193           </ul>
 194           </li>
 195         </ul>
 196         </li>
 197         <li><a href="#BasicBlock">The <tt>BasicBlock</tt> class</a></li>
 198         <li><a href="#Argument">The <tt>Argument</tt> class</a></li>
 199       </ul>
 200       </li>
 201     </ul>
 202   </li>
 203 </ol>
 204
 205 <div class="doc_author">
 206   <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>,
 207                 <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>,
 208                 <a href="mailto:ggreif@gmail.com">Gabor Greif</a>,
 209                 <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>,
 210                 <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> and
 211                 <a href="mailto:owen@apple.com">Owen Anderson</a></p>
 212 </div>
 213
 214 <!-- *********************************************************************** -->
 215 <h2>
 216   <a name="introduction">Introduction </a>
 217 </h2>
 218 <!-- *********************************************************************** -->
 219
 220 <div>
 221
 222 <p>This document is meant to highlight some of the important classes and
 223 interfaces available in the LLVM source-base.  This manual is not
 224 intended to explain what LLVM is, how it works, and what LLVM code looks
 225 like.  It assumes that you know the basics of LLVM and are interested
 226 in writing transformations or otherwise analyzing or manipulating the
 227 code.</p>
 228
 229 <p>This document should get you oriented so that you can find your
 230 way in the continuously growing source code that makes up the LLVM
 231 infrastructure. Note that this manual is not intended to serve as a
 232 replacement for reading the source code, so if you think there should be
 233 a method in one of these classes to do something, but it's not listed,
 234 check the source.  Links to the <a href="/doxygen/">doxygen</a> sources
 235 are provided to make this as easy as possible.</p>
 236
 237 <p>The first section of this document describes general information that is
 238 useful to know when working in the LLVM infrastructure, and the second describes
 239 the Core LLVM classes.  In the future this manual will be extended with
 240 information describing how to use extension libraries, such as dominator
 241 information, CFG traversal routines, and useful utilities like the <tt><a
 242 href="/doxygen/InstVisitor_8h-source.html">InstVisitor</a></tt> template.</p>
 243
 244 </div>
 245
 246 <!-- *********************************************************************** -->
 247 <h2>
 248   <a name="general">General Information</a>
 249 </h2>
 250 <!-- *********************************************************************** -->
 251
 252 <div>
 253
 254 <p>This section contains general information that is useful if you are working
 255 in the LLVM source-base, but that isn't specific to any particular API.</p>
 256
 257 <!-- ======================================================================= -->
 258 <h3>
 259   <a name="stl">The C++ Standard Template Library</a>
 260 </h3>
 261
 262 <div>
 263
 264 <p>LLVM makes heavy use of the C++ Standard Template Library (STL),
 265 perhaps much more than you are used to, or have seen before.  Because of
 266 this, you might want to do a little background reading in the
 267 techniques used and capabilities of the library.  There are many good
 268 pages that discuss the STL, and several books on the subject that you
 269 can get, so it will not be discussed in this document.</p>
 270
 271 <p>Here are some useful links:</p>
 272
 273 <ol>
 274
 275 <li><a href="http://www.dinkumware.com/manuals/#Standard C++ Library">Dinkumware
 276 C++ Library reference</a> - an excellent reference for the STL and other parts
 277 of the standard C++ library.</li>
 278
 279 <li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an
 280 O'Reilly book in the making.  It has a decent Standard Library
 281 Reference that rivals Dinkumware's, and is unfortunately no longer free since the
 282 book has been published.</li>
 283
 284 <li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked
 285 Questions</a></li>
 286
 287 <li><a href="http://www.sgi.com/tech/stl/">SGI's STL Programmer's Guide</a> -
 288 Contains a useful <a
 289 href="http://www.sgi.com/tech/stl/stl_introduction.html">Introduction to the
 290 STL</a>.</li>
 291
 292 <li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++
 293 Page</a></li>
 294
 295 <li><a href="http://64.78.49.204/">
 296 Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get
 297 the book).</a></li>
 298
 299 </ol>
 300
 301 <p>You are also encouraged to take a look at the <a
 302 href="CodingStandards.html">LLVM Coding Standards</a> guide which focuses on how
 303 to write maintainable code more than where to put your curly braces.</p>
 304
 305 </div>
 306
 307 <!-- ======================================================================= -->
 308 <h3>
 309   <a name="stl">Other useful references</a>
 310 </h3>
 311
 312 <div>
 313
 314 <ol>
 315 <li><a href="http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html">Using
 316 static and shared libraries across platforms</a></li>
 317 </ol>
 318
 319 </div>
 320
 321 </div>
 322
 323 <!-- *********************************************************************** -->
 324 <h2>
 325   <a name="apis">Important and useful LLVM APIs</a>
 326 </h2>
 327 <!-- *********************************************************************** -->
 328
 329 <div>
 330
 331 <p>Here we highlight some LLVM APIs that are generally useful and good to
 332 know about when writing transformations.</p>
 333
 334 <!-- ======================================================================= -->
 335 <h3>
 336   <a name="isa">The <tt>isa&lt;&gt;</tt>, <tt>cast&lt;&gt;</tt> and
 337   <tt>dyn_cast&lt;&gt;</tt> templates</a>
 338 </h3>
 339
 340 <div>
 341
 342 <p>The LLVM source-base makes extensive use of a custom form of RTTI.
 343 These templates have many similarities to the C++ <tt>dynamic_cast&lt;&gt;</tt>
 344 operator, but they don't have some drawbacks (primarily stemming from
 345 the fact that <tt>dynamic_cast&lt;&gt;</tt> only works on classes that
 346 have a v-table). Because they are used so often, you must know what they
 347 do and how they work. All of these templates are defined in the <a
 348  href="/doxygen/Casting_8h-source.html"><tt>llvm/Support/Casting.h</tt></a>
 349 file (note that you very rarely have to include this file directly).</p>
 350
 351 <dl>
 352   <dt><tt>isa&lt;&gt;</tt>: </dt>
 353
 354   <dd><p>The <tt>isa&lt;&gt;</tt> operator works exactly like the Java
 355   "<tt>instanceof</tt>" operator.  It returns true or false depending on whether
 356   a reference or pointer points to an instance of the specified class.  This can
 357   be very useful for constraint checking of various sorts (example below).</p>
 358   </dd>
 359
 360   <dt><tt>cast&lt;&gt;</tt>: </dt>
 361
 362   <dd><p>The <tt>cast&lt;&gt;</tt> operator is a "checked cast" operation. It
 363   converts a pointer or reference from a base class to a derived class, causing
 364   an assertion failure if it is not really an instance of the right type.  This
 365   should be used in cases where you have some information that makes you believe
 366   that something is of the right type.  An example of the <tt>isa&lt;&gt;</tt>
 367   and <tt>cast&lt;&gt;</tt> template is:</p>
 368
 369 <div class="doc_code">
 370 <pre>
 371 static bool isLoopInvariant(const <a href="#Value">Value</a> *V, const Loop *L) {
 372   if (isa&lt;<a href="#Constant">Constant</a>&gt;(V) || isa&lt;<a href="#Argument">Argument</a>&gt;(V) || isa&lt;<a href="#GlobalValue">GlobalValue</a>&gt;(V))
 373     return true;
 374
 375   // <i>Otherwise, it must be an instruction...</i>
 376   return !L-&gt;contains(cast&lt;<a href="#Instruction">Instruction</a>&gt;(V)-&gt;getParent());
 377 }
 378 </pre>
 379 </div>
 380
 381   <p>Note that you should <b>not</b> use an <tt>isa&lt;&gt;</tt> test followed
 382   by a <tt>cast&lt;&gt;</tt>, for that use the <tt>dyn_cast&lt;&gt;</tt>
 383   operator.</p>
 384
 385   </dd>
 386
 387   <dt><tt>dyn_cast&lt;&gt;</tt>:</dt>
 388
 389   <dd><p>The <tt>dyn_cast&lt;&gt;</tt> operator is a "checking cast" operation.
 390   It checks to see if the operand is of the specified type, and if so, returns a
 391   pointer to it (this operator does not work with references). If the operand is
 392   not of the correct type, a null pointer is returned.  Thus, this works very
 393   much like the <tt>dynamic_cast&lt;&gt;</tt> operator in C++, and should be
 394   used in the same circumstances.  Typically, the <tt>dyn_cast&lt;&gt;</tt>
 395   operator is used in an <tt>if</tt> statement or some other flow control
 396   statement like this:</p>
 397
 398 <div class="doc_code">
 399 <pre>
 400 if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast&lt;<a href="#AllocationInst">AllocationInst</a>&gt;(Val)) {
 401   // <i>...</i>
 402 }
 403 </pre>
 404 </div>
 405
 406   <p>This form of the <tt>if</tt> statement effectively combines together a call
 407   to <tt>isa&lt;&gt;</tt> and a call to <tt>cast&lt;&gt;</tt> into one
 408   statement, which is very convenient.</p>
 409
 410   <p>Note that the <tt>dyn_cast&lt;&gt;</tt> operator, like C++'s
 411   <tt>dynamic_cast&lt;&gt;</tt> or Java's <tt>instanceof</tt> operator, can be
 412   abused.  In particular, you should not use big chained <tt>if/then/else</tt>
 413   blocks to check for lots of different variants of classes.  If you find
 414   yourself wanting to do this, it is much cleaner and more efficient to use the
 415   <tt>InstVisitor</tt> class to dispatch over the instruction type directly.</p>
 416
 417   </dd>
 418
 419   <dt><tt>cast_or_null&lt;&gt;</tt>: </dt>
 420
 421   <dd><p>The <tt>cast_or_null&lt;&gt;</tt> operator works just like the
 422   <tt>cast&lt;&gt;</tt> operator, except that it allows for a null pointer as an
 423   argument (which it then propagates).  This can sometimes be useful, allowing
 424   you to combine several null checks into one.</p></dd>
 425
 426   <dt><tt>dyn_cast_or_null&lt;&gt;</tt>: </dt>
 427
 428   <dd><p>The <tt>dyn_cast_or_null&lt;&gt;</tt> operator works just like the
 429   <tt>dyn_cast&lt;&gt;</tt> operator, except that it allows for a null pointer
 430   as an argument (which it then propagates).  This can sometimes be useful,
 431   allowing you to combine several null checks into one.</p></dd>
 432
 433 </dl>
 434
 435 <p>These five templates can be used with any classes, whether they have a
 436 v-table or not. If you want to add support for these templates, see the
 437 document <a href="HowToSetUpLLVMStyleRTTI.html">How to set up LLVM-style
 438 RTTI for your class hierarchy </a>.
 439 </p>
 440
 441 </div>
 442
 443
 444 <!-- ======================================================================= -->
 445 <h3>
 446   <a name="string_apis">Passing strings (the <tt>StringRef</tt>
 447 and <tt>Twine</tt> classes)</a>
 448 </h3>
 449
 450 <div>
 451
 452 <p>Although LLVM generally does not do much string manipulation, we do have
 453 several important APIs which take strings.  Two important examples are the
 454 Value class -- which has names for instructions, functions, etc. -- and the
 455 StringMap class which is used extensively in LLVM and Clang.</p>
 456
 457 <p>These are generic classes, and they need to be able to accept strings which
 458 may have embedded null characters.  Therefore, they cannot simply take
 459 a <tt>const char *</tt>, and taking a <tt>const std::string&amp;</tt> requires
 460 clients to perform a heap allocation which is usually unnecessary.  Instead,
 461 many LLVM APIs use a <tt>StringRef</tt> or a <tt>const Twine&amp;</tt> for
 462 passing strings efficiently.</p>
 463
 464 <!-- _______________________________________________________________________ -->
 465 <h4>
 466   <a name="StringRef">The <tt>StringRef</tt> class</a>
 467 </h4>
 468
 469 <div>
 470
 471 <p>The <tt>StringRef</tt> data type represents a reference to a constant string
 472 (a character array and a length) and supports the common operations available
 473 on <tt>std:string</tt>, but does not require heap allocation.</p>
 474
 475 <p>It can be implicitly constructed using a C style null-terminated string,
 476 an <tt>std::string</tt>, or explicitly with a character pointer and length.
 477 For example, the <tt>StringRef</tt> find function is declared as:</p>
 478
 479 <pre class="doc_code">
 480   iterator find(StringRef Key);
 481 </pre>
 482
 483 <p>and clients can call it using any one of:</p>
 484
 485 <pre class="doc_code">
 486   Map.find("foo");                 <i>// Lookup "foo"</i>
 487   Map.find(std::string("bar"));    <i>// Lookup "bar"</i>
 488   Map.find(StringRef("\0baz", 4)); <i>// Lookup "\0baz"</i>
 489 </pre>
 490
 491 <p>Similarly, APIs which need to return a string may return a <tt>StringRef</tt>
 492 instance, which can be used directly or converted to an <tt>std::string</tt>
 493 using the <tt>str</tt> member function.  See
 494 "<tt><a href="/doxygen/classllvm_1_1StringRef_8h-source.html">llvm/ADT/StringRef.h</a></tt>"
 495 for more information.</p>
 496
 497 <p>You should rarely use the <tt>StringRef</tt> class directly, because it contains
 498 pointers to external memory it is not generally safe to store an instance of the
 499 class (unless you know that the external storage will not be freed). StringRef is
 500 small and pervasive enough in LLVM that it should always be passed by value.</p>
 501
 502 </div>
 503
 504 <!-- _______________________________________________________________________ -->
 505 <h4>
 506   <a name="Twine">The <tt>Twine</tt> class</a>
 507 </h4>
 508
 509 <div>
 510
 511 <p>The <tt><a href="/doxygen/classllvm_1_1Twine.html">Twine</a></tt> class is an
 512 efficient way for APIs to accept concatenated strings.  For example, a common
 513 LLVM paradigm is to name one instruction based on
 514 the name of another instruction with a suffix, for example:</p>
 515
 516 <div class="doc_code">
 517 <pre>
 518     New = CmpInst::Create(<i>...</i>, SO->getName() + ".cmp");
 519 </pre>
 520 </div>
 521
 522 <p>The <tt>Twine</tt> class is effectively a lightweight
 523 <a href="http://en.wikipedia.org/wiki/Rope_(computer_science)">rope</a>
 524 which points to temporary (stack allocated) objects.  Twines can be implicitly
 525 constructed as the result of the plus operator applied to strings (i.e., a C
 526 strings, an <tt>std::string</tt>, or a <tt>StringRef</tt>).  The twine delays
 527 the actual concatenation of strings until it is actually required, at which
 528 point it can be efficiently rendered directly into a character array.  This
 529 avoids unnecessary heap allocation involved in constructing the temporary
 530 results of string concatenation. See
 531 "<tt><a href="/doxygen/Twine_8h_source.html">llvm/ADT/Twine.h</a></tt>"
 532 and <a href="#dss_twine">here</a> for more information.</p>
 533
 534 <p>As with a <tt>StringRef</tt>, <tt>Twine</tt> objects point to external memory
 535 and should almost never be stored or mentioned directly.  They are intended
 536 solely for use when defining a function which should be able to efficiently
 537 accept concatenated strings.</p>
 538
 539 </div>
 540
 541 </div>
 542
 543 <!-- ======================================================================= -->
 544 <h3>
 545   <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a>
 546 </h3>
 547
 548 <div>
 549
 550 <p>Often when working on your pass you will put a bunch of debugging printouts
 551 and other code into your pass.  After you get it working, you want to remove
 552 it, but you may need it again in the future (to work out new bugs that you run
 553 across).</p>
 554
 555 <p> Naturally, because of this, you don't want to delete the debug printouts,
 556 but you don't want them to always be noisy.  A standard compromise is to comment
 557 them out, allowing you to enable them if you need them in the future.</p>
 558
 559 <p>The "<tt><a href="/doxygen/Debug_8h-source.html">llvm/Support/Debug.h</a></tt>"
 560 file provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to
 561 this problem.  Basically, you can put arbitrary code into the argument of the
 562 <tt>DEBUG</tt> macro, and it is only executed if '<tt>opt</tt>' (or any other
 563 tool) is run with the '<tt>-debug</tt>' command line argument:</p>
 564
 565 <div class="doc_code">
 566 <pre>
 567 DEBUG(errs() &lt;&lt; "I am here!\n");
 568 </pre>
 569 </div>
 570
 571 <p>Then you can run your pass like this:</p>
 572
 573 <div class="doc_code">
 574 <pre>
 575 $ opt &lt; a.bc &gt; /dev/null -mypass
 576 <i>&lt;no output&gt;</i>
 577 $ opt &lt; a.bc &gt; /dev/null -mypass -debug
 578 I am here!
 579 </pre>
 580 </div>
 581
 582 <p>Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you
 583 to not have to create "yet another" command line option for the debug output for
 584 your pass.  Note that <tt>DEBUG()</tt> macros are disabled for optimized builds,
 585 so they do not cause a performance impact at all (for the same reason, they
 586 should also not contain side-effects!).</p>
 587
 588 <p>One additional nice thing about the <tt>DEBUG()</tt> macro is that you can
 589 enable or disable it directly in gdb.  Just use "<tt>set DebugFlag=0</tt>" or
 590 "<tt>set DebugFlag=1</tt>" from the gdb if the program is running.  If the
 591 program hasn't been started yet, you can always just run it with
 592 <tt>-debug</tt>.</p>
 593
 594 <!-- _______________________________________________________________________ -->
 595 <h4>
 596   <a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and
 597   the <tt>-debug-only</tt> option</a>
 598 </h4>
 599
 600 <div>
 601
 602 <p>Sometimes you may find yourself in a situation where enabling <tt>-debug</tt>
 603 just turns on <b>too much</b> information (such as when working on the code
 604 generator).  If you want to enable debug information with more fine-grained
 605 control, you define the <tt>DEBUG_TYPE</tt> macro and the <tt>-debug</tt> only
 606 option as follows:</p>
 607
 608 <div class="doc_code">
 609 <pre>
 610 #undef  DEBUG_TYPE
 611 DEBUG(errs() &lt;&lt; "No debug type\n");
 612 #define DEBUG_TYPE "foo"
 613 DEBUG(errs() &lt;&lt; "'foo' debug type\n");
 614 #undef  DEBUG_TYPE
 615 #define DEBUG_TYPE "bar"
 616 DEBUG(errs() &lt;&lt; "'bar' debug type\n"));
 617 #undef  DEBUG_TYPE
 618 #define DEBUG_TYPE ""
 619 DEBUG(errs() &lt;&lt; "No debug type (2)\n");
 620 </pre>
 621 </div>
 622
 623 <p>Then you can run your pass like this:</p>
 624
 625 <div class="doc_code">
 626 <pre>
 627 $ opt &lt; a.bc &gt; /dev/null -mypass
 628 <i>&lt;no output&gt;</i>
 629 $ opt &lt; a.bc &gt; /dev/null -mypass -debug
 630 No debug type
 631 'foo' debug type
 632 'bar' debug type
 633 No debug type (2)
 634 $ opt &lt; a.bc &gt; /dev/null -mypass -debug-only=foo
 635 'foo' debug type
 636 $ opt &lt; a.bc &gt; /dev/null -mypass -debug-only=bar
 637 'bar' debug type
 638 </pre>
 639 </div>
 640
 641 <p>Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of
 642 a file, to specify the debug type for the entire module (if you do this before
 643 you <tt>#include "llvm/Support/Debug.h"</tt>, you don't have to insert the ugly
 644 <tt>#undef</tt>'s).  Also, you should use names more meaningful than "foo" and
 645 "bar", because there is no system in place to ensure that names do not
 646 conflict. If two different modules use the same string, they will all be turned
 647 on when the name is specified. This allows, for example, all debug information
 648 for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>,
 649 even if the source lives in multiple files.</p>
 650
 651 <p>The <tt>DEBUG_WITH_TYPE</tt> macro is also available for situations where you
 652 would like to set <tt>DEBUG_TYPE</tt>, but only for one specific <tt>DEBUG</tt>
 653 statement. It takes an additional first parameter, which is the type to use. For
 654 example, the preceding example could be written as:</p>
 655
 656
 657 <div class="doc_code">
 658 <pre>
 659 DEBUG_WITH_TYPE("", errs() &lt;&lt; "No debug type\n");
 660 DEBUG_WITH_TYPE("foo", errs() &lt;&lt; "'foo' debug type\n");
 661 DEBUG_WITH_TYPE("bar", errs() &lt;&lt; "'bar' debug type\n"));
 662 DEBUG_WITH_TYPE("", errs() &lt;&lt; "No debug type (2)\n");
 663 </pre>
 664 </div>
 665
 666 </div>
 667
 668 </div>
 669
 670 <!-- ======================================================================= -->
 671 <h3>
 672   <a name="Statistic">The <tt>Statistic</tt> class &amp; <tt>-stats</tt>
 673   option</a>
 674 </h3>
 675
 676 <div>
 677
 678 <p>The "<tt><a
 679 href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file
 680 provides a class named <tt>Statistic</tt> that is used as a unified way to
 681 keep track of what the LLVM compiler is doing and how effective various
 682 optimizations are.  It is useful to see what optimizations are contributing to
 683 making a particular program run faster.</p>
 684
 685 <p>Often you may run your pass on some big program, and you're interested to see
 686 how many times it makes a certain transformation.  Although you can do this with
 687 hand inspection, or some ad-hoc method, this is a real pain and not very useful
 688 for big programs.  Using the <tt>Statistic</tt> class makes it very easy to
 689 keep track of this information, and the calculated information is presented in a
 690 uniform manner with the rest of the passes being executed.</p>
 691
 692 <p>There are many examples of <tt>Statistic</tt> uses, but the basics of using
 693 it are as follows:</p>
 694
 695 <ol>
 696     <li><p>Define your statistic like this:</p>
 697
 698 <div class="doc_code">
 699 <pre>
 700 #define <a href="#DEBUG_TYPE">DEBUG_TYPE</a> "mypassname"   <i>// This goes before any #includes.</i>
 701 STATISTIC(NumXForms, "The # of times I did stuff");
 702 </pre>
 703 </div>
 704
 705   <p>The <tt>STATISTIC</tt> macro defines a static variable, whose name is
 706     specified by the first argument.  The pass name is taken from the DEBUG_TYPE
 707     macro, and the description is taken from the second argument.  The variable
 708     defined ("NumXForms" in this case) acts like an unsigned integer.</p></li>
 709
 710     <li><p>Whenever you make a transformation, bump the counter:</p>
 711
 712 <div class="doc_code">
 713 <pre>
 714 ++NumXForms;   // <i>I did stuff!</i>
 715 </pre>
 716 </div>
 717
 718     </li>
 719   </ol>
 720
 721   <p>That's all you have to do.  To get '<tt>opt</tt>' to print out the
 722   statistics gathered, use the '<tt>-stats</tt>' option:</p>
 723
 724 <div class="doc_code">
 725 <pre>
 726 $ opt -stats -mypassname &lt; program.bc &gt; /dev/null
 727 <i>... statistics output ...</i>
 728 </pre>
 729 </div>
 730
 731   <p> When running <tt>opt</tt> on a C file from the SPEC benchmark
 732 suite, it gives a report that looks like this:</p>
 733
 734 <div class="doc_code">
 735 <pre>
 736    7646 bitcodewriter   - Number of normal instructions
 737     725 bitcodewriter   - Number of oversized instructions
 738  129996 bitcodewriter   - Number of bitcode bytes written
 739    2817 raise           - Number of insts DCEd or constprop'd
 740    3213 raise           - Number of cast-of-self removed
 741    5046 raise           - Number of expression trees converted
 742      75 raise           - Number of other getelementptr's formed
 743     138 raise           - Number of load/store peepholes
 744      42 deadtypeelim    - Number of unused typenames removed from symtab
 745     392 funcresolve     - Number of varargs functions resolved
 746      27 globaldce       - Number of global variables removed
 747       2 adce            - Number of basic blocks removed
 748     134 cee             - Number of branches revectored
 749      49 cee             - Number of setcc instruction eliminated
 750     532 gcse            - Number of loads removed
 751    2919 gcse            - Number of instructions removed
 752      86 indvars         - Number of canonical indvars added
 753      87 indvars         - Number of aux indvars removed
 754      25 instcombine     - Number of dead inst eliminate
 755     434 instcombine     - Number of insts combined
 756     248 licm            - Number of load insts hoisted
 757    1298 licm            - Number of insts hoisted to a loop pre-header
 758       3 licm            - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)
 759      75 mem2reg         - Number of alloca's promoted
 760    1444 cfgsimplify     - Number of blocks simplified
 761 </pre>
 762 </div>
 763
 764 <p>Obviously, with so many optimizations, having a unified framework for this
 765 stuff is very nice.  Making your pass fit well into the framework makes it more
 766 maintainable and useful.</p>
 767
 768 </div>
 769
 770 <!-- ======================================================================= -->
 771 <h3>
 772   <a name="ViewGraph">Viewing graphs while debugging code</a>
 773 </h3>
 774
 775 <div>
 776
 777 <p>Several of the important data structures in LLVM are graphs: for example
 778 CFGs made out of LLVM <a href="#BasicBlock">BasicBlock</a>s, CFGs made out of
 779 LLVM <a href="CodeGenerator.html#machinebasicblock">MachineBasicBlock</a>s, and
 780 <a href="CodeGenerator.html#selectiondag_intro">Instruction Selection
 781 DAGs</a>.  In many cases, while debugging various parts of the compiler, it is
 782 nice to instantly visualize these graphs.</p>
 783
 784 <p>LLVM provides several callbacks that are available in a debug build to do
 785 exactly that.  If you call the <tt>Function::viewCFG()</tt> method, for example,
 786 the current LLVM tool will pop up a window containing the CFG for the function
 787 where each basic block is a node in the graph, and each node contains the
 788 instructions in the block.  Similarly, there also exists
 789 <tt>Function::viewCFGOnly()</tt> (does not include the instructions), the
 790 <tt>MachineFunction::viewCFG()</tt> and <tt>MachineFunction::viewCFGOnly()</tt>,
 791 and the <tt>SelectionDAG::viewGraph()</tt> methods.  Within GDB, for example,
 792 you can usually use something like <tt>call DAG.viewGraph()</tt> to pop
 793 up a window.  Alternatively, you can sprinkle calls to these functions in your
 794 code in places you want to debug.</p>
 795
 796 <p>Getting this to work requires a small amount of configuration.  On Unix
 797 systems with X11, install the <a href="http://www.graphviz.org">graphviz</a>
 798 toolkit, and make sure 'dot' and 'gv' are in your path.  If you are running on
 799 Mac OS/X, download and install the Mac OS/X <a
 800 href="http://www.pixelglow.com/graphviz/">Graphviz program</a>, and add
 801 <tt>/Applications/Graphviz.app/Contents/MacOS/</tt> (or wherever you install
 802 it) to your path.  Once in your system and path are set up, rerun the LLVM
 803 configure script and rebuild LLVM to enable this functionality.</p>
 804
 805 <p><tt>SelectionDAG</tt> has been extended to make it easier to locate
 806 <i>interesting</i> nodes in large complex graphs.  From gdb, if you
 807 <tt>call DAG.setGraphColor(<i>node</i>, "<i>color</i>")</tt>, then the
 808 next <tt>call DAG.viewGraph()</tt> would highlight the node in the
 809 specified color (choices of colors can be found at <a
 810 href="http://www.graphviz.org/doc/info/colors.html">colors</a>.) More
 811 complex node attributes can be provided with <tt>call
 812 DAG.setGraphAttrs(<i>node</i>, "<i>attributes</i>")</tt> (choices can be
 813 found at <a href="http://www.graphviz.org/doc/info/attrs.html">Graph
 814 Attributes</a>.)  If you want to restart and clear all the current graph
 815 attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p>
 816
 817 <p>Note that graph visualization features are compiled out of Release builds
 818 to reduce file size.  This means that you need a Debug+Asserts or
 819 Release+Asserts build to use these features.</p>
 820
 821 </div>
 822
 823 </div>
 824
 825 <!-- *********************************************************************** -->
 826 <h2>
 827   <a name="datastructure">Picking the Right Data Structure for a Task</a>
 828 </h2>
 829 <!-- *********************************************************************** -->
 830
 831 <div>
 832
 833 <p>LLVM has a plethora of data structures in the <tt>llvm/ADT/</tt> directory,
 834  and we commonly use STL data structures.  This section describes the trade-offs
 835  you should consider when you pick one.</p>
 836
 837 <p>
 838 The first step is a choose your own adventure: do you want a sequential
 839 container, a set-like container, or a map-like container?  The most important
 840 thing when choosing a container is the algorithmic properties of how you plan to
 841 access the container.  Based on that, you should use:</p>
 842
 843 <ul>
 844 <li>a <a href="#ds_map">map-like</a> container if you need efficient look-up
 845     of an value based on another value.  Map-like containers also support
 846     efficient queries for containment (whether a key is in the map).  Map-like
 847     containers generally do not support efficient reverse mapping (values to
 848     keys).  If you need that, use two maps.  Some map-like containers also
 849     support efficient iteration through the keys in sorted order.  Map-like
 850     containers are the most expensive sort, only use them if you need one of
 851     these capabilities.</li>
 852
 853 <li>a <a href="#ds_set">set-like</a> container if you need to put a bunch of
 854     stuff into a container that automatically eliminates duplicates.  Some
 855     set-like containers support efficient iteration through the elements in
 856     sorted order.  Set-like containers are more expensive than sequential
 857     containers.
 858 </li>
 859
 860 <li>a <a href="#ds_sequential">sequential</a> container provides
 861     the most efficient way to add elements and keeps track of the order they are
 862     added to the collection.  They permit duplicates and support efficient
 863     iteration, but do not support efficient look-up based on a key.
 864 </li>
 865
 866 <li>a <a href="#ds_string">string</a> container is a specialized sequential
 867     container or reference structure that is used for character or byte
 868     arrays.</li>
 869
 870 <li>a <a href="#ds_bit">bit</a> container provides an efficient way to store and
 871     perform set operations on sets of numeric id's, while automatically
 872     eliminating duplicates.  Bit containers require a maximum of 1 bit for each
 873     identifier you want to store.
 874 </li>
 875 </ul>
 876
 877 <p>
 878 Once the proper category of container is determined, you can fine tune the
 879 memory use, constant factors, and cache behaviors of access by intelligently
 880 picking a member of the category.  Note that constant factors and cache behavior
 881 can be a big deal.  If you have a vector that usually only contains a few
 882 elements (but could contain many), for example, it's much better to use
 883 <a href="#dss_smallvector">SmallVector</a> than <a href="#dss_vector">vector</a>
 884 .  Doing so avoids (relatively) expensive malloc/free calls, which dwarf the
 885 cost of adding the elements to the container. </p>
 886
 887 <!-- ======================================================================= -->
 888 <h3>
 889   <a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a>
 890 </h3>
 891
 892 <div>
 893 There are a variety of sequential containers available for you, based on your
 894 needs.  Pick the first in this section that will do what you want.
 895
 896 <!-- _______________________________________________________________________ -->
 897 <h4>
 898   <a name="dss_arrayref">llvm/ADT/ArrayRef.h</a>
 899 </h4>
 900
 901 <div>
 902 <p>The llvm::ArrayRef class is the preferred class to use in an interface that
 903    accepts a sequential list of elements in memory and just reads from them.  By
 904    taking an ArrayRef, the API can be passed a fixed size array, an std::vector,
 905    an llvm::SmallVector and anything else that is contiguous in memory.
 906 </p>
 907 </div>
 908
 909
 910
 911 <!-- _______________________________________________________________________ -->
 912 <h4>
 913   <a name="dss_fixedarrays">Fixed Size Arrays</a>
 914 </h4>
 915
 916 <div>
 917 <p>Fixed size arrays are very simple and very fast.  They are good if you know
 918 exactly how many elements you have, or you have a (low) upper bound on how many
 919 you have.</p>
 920 </div>
 921
 922 <!-- _______________________________________________________________________ -->
 923 <h4>
 924   <a name="dss_heaparrays">Heap Allocated Arrays</a>
 925 </h4>
 926
 927 <div>
 928 <p>Heap allocated arrays (new[] + delete[]) are also simple.  They are good if
 929 the number of elements is variable, if you know how many elements you will need
 930 before the array is allocated, and if the array is usually large (if not,
 931 consider a <a href="#dss_smallvector">SmallVector</a>).  The cost of a heap
 932 allocated array is the cost of the new/delete (aka malloc/free).  Also note that
 933 if you are allocating an array of a type with a constructor, the constructor and
 934 destructors will be run for every element in the array (re-sizable vectors only
 935 construct those elements actually used).</p>
 936 </div>
 937
 938 <!-- _______________________________________________________________________ -->
 939 <h4>
 940   <a name="dss_tinyptrvector">"llvm/ADT/TinyPtrVector.h"</a>
 941 </h4>
 942
 943
 944 <div>
 945 <p><tt>TinyPtrVector&lt;Type&gt;</tt> is a highly specialized collection class
 946 that is optimized to avoid allocation in the case when a vector has zero or one
 947 elements.  It has two major restrictions: 1) it can only hold values of pointer
 948 type, and 2) it cannot hold a null pointer.</p>
 949
 950 <p>Since this container is highly specialized, it is rarely used.</p>
 951
 952 </div>
 953
 954 <!-- _______________________________________________________________________ -->
 955 <h4>
 956   <a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a>
 957 </h4>
 958
 959 <div>
 960 <p><tt>SmallVector&lt;Type, N&gt;</tt> is a simple class that looks and smells
 961 just like <tt>vector&lt;Type&gt;</tt>:
 962 it supports efficient iteration, lays out elements in memory order (so you can
 963 do pointer arithmetic between elements), supports efficient push_back/pop_back
 964 operations, supports efficient random access to its elements, etc.</p>
 965
 966 <p>The advantage of SmallVector is that it allocates space for
 967 some number of elements (N) <b>in the object itself</b>.  Because of this, if
 968 the SmallVector is dynamically smaller than N, no malloc is performed.  This can
 969 be a big win in cases where the malloc/free call is far more expensive than the
 970 code that fiddles around with the elements.</p>
 971
 972 <p>This is good for vectors that are "usually small" (e.g. the number of
 973 predecessors/successors of a block is usually less than 8).  On the other hand,
 974 this makes the size of the SmallVector itself large, so you don't want to
 975 allocate lots of them (doing so will waste a lot of space).  As such,
 976 SmallVectors are most useful when on the stack.</p>
 977
 978 <p>SmallVector also provides a nice portable and efficient replacement for
 979 <tt>alloca</tt>.</p>
 980
 981 </div>
 982
 983 <!-- _______________________________________________________________________ -->
 984 <h4>
 985   <a name="dss_vector">&lt;vector&gt;</a>
 986 </h4>
 987
 988 <div>
 989 <p>
 990 std::vector is well loved and respected.  It is useful when SmallVector isn't:
 991 when the size of the vector is often large (thus the small optimization will
 992 rarely be a benefit) or if you will be allocating many instances of the vector
 993 itself (which would waste space for elements that aren't in the container).
 994 vector is also useful when interfacing with code that expects vectors :).
 995 </p>
 996
 997 <p>One worthwhile note about std::vector: avoid code like this:</p>
 998
 999 <div class="doc_code">
1000 <pre>
1001 for ( ... ) {
1002    std::vector&lt;foo&gt; V;
1003    // make use of V.
1004 }
1005 </pre>
1006 </div>
1007
1008 <p>Instead, write this as:</p>
1009
1010 <div class="doc_code">
1011 <pre>
1012 std::vector&lt;foo&gt; V;
1013 for ( ... ) {
1014    // make use of V.
1015    V.clear();
1016 }
1017 </pre>
1018 </div>
1019
1020 <p>Doing so will save (at least) one heap allocation and free per iteration of
1021 the loop.</p>
1022
1023 </div>
1024
1025 <!-- _______________________________________________________________________ -->
1026 <h4>
1027   <a name="dss_deque">&lt;deque&gt;</a>
1028 </h4>
1029
1030 <div>
1031 <p>std::deque is, in some senses, a generalized version of std::vector.  Like
1032 std::vector, it provides constant time random access and other similar
1033 properties, but it also provides efficient access to the front of the list.  It
1034 does not guarantee continuity of elements within memory.</p>
1035
1036 <p>In exchange for this extra flexibility, std::deque has significantly higher
1037 constant factor costs than std::vector.  If possible, use std::vector or
1038 something cheaper.</p>
1039 </div>
1040
1041 <!-- _______________________________________________________________________ -->
1042 <h4>
1043   <a name="dss_list">&lt;list&gt;</a>
1044 </h4>
1045
1046 <div>
1047 <p>std::list is an extremely inefficient class that is rarely useful.
1048 It performs a heap allocation for every element inserted into it, thus having an
1049 extremely high constant factor, particularly for small data types.  std::list
1050 also only supports bidirectional iteration, not random access iteration.</p>
1051
1052 <p>In exchange for this high cost, std::list supports efficient access to both
1053 ends of the list (like std::deque, but unlike std::vector or SmallVector).  In
1054 addition, the iterator invalidation characteristics of std::list are stronger
1055 than that of a vector class: inserting or removing an element into the list does
1056 not invalidate iterator or pointers to other elements in the list.</p>
1057 </div>
1058
1059 <!-- _______________________________________________________________________ -->
1060 <h4>
1061   <a name="dss_ilist">llvm/ADT/ilist.h</a>
1062 </h4>
1063
1064 <div>
1065 <p><tt>ilist&lt;T&gt;</tt> implements an 'intrusive' doubly-linked list.  It is
1066 intrusive, because it requires the element to store and provide access to the
1067 prev/next pointers for the list.</p>
1068
1069 <p><tt>ilist</tt> has the same drawbacks as <tt>std::list</tt>, and additionally
1070 requires an <tt>ilist_traits</tt> implementation for the element type, but it
1071 provides some novel characteristics.  In particular, it can efficiently store
1072 polymorphic objects, the traits class is informed when an element is inserted or
1073 removed from the list, and <tt>ilist</tt>s are guaranteed to support a
1074 constant-time splice operation.</p>
1075
1076 <p>These properties are exactly what we want for things like
1077 <tt>Instruction</tt>s and basic blocks, which is why these are implemented with
1078 <tt>ilist</tt>s.</p>
1079
1080 Related classes of interest are explained in the following subsections:
1081     <ul>
1082       <li><a href="#dss_ilist_traits">ilist_traits</a></li>
1083       <li><a href="#dss_iplist">iplist</a></li>
1084       <li><a href="#dss_ilist_node">llvm/ADT/ilist_node.h</a></li>
1085       <li><a href="#dss_ilist_sentinel">Sentinels</a></li>
1086     </ul>
1087 </div>
1088
1089 <!-- _______________________________________________________________________ -->
1090 <h4>
1091   <a name="dss_packedvector">llvm/ADT/PackedVector.h</a>
1092 </h4>
1093
1094 <div>
1095 <p>
1096 Useful for storing a vector of values using only a few number of bits for each
1097 value. Apart from the standard operations of a vector-like container, it can
1098 also perform an 'or' set operation.
1099 </p>
1100
1101 <p>For example:</p>
1102
1103 <div class="doc_code">
1104 <pre>
1105 enum State {
1106     None = 0x0,
1107     FirstCondition = 0x1,
1108     SecondCondition = 0x2,
1109     Both = 0x3
1110 };
1111
1112 State get() {
1113     PackedVector&lt;State, 2&gt; Vec1;
1114     Vec1.push_back(FirstCondition);
1115
1116     PackedVector&lt;State, 2&gt; Vec2;
1117     Vec2.push_back(SecondCondition);
1118
1119     Vec1 |= Vec2;
1120     return Vec1[0]; // returns 'Both'.
1121 }
1122 </pre>
1123 </div>
1124
1125 </div>
1126
1127 <!-- _______________________________________________________________________ -->
1128 <h4>
1129   <a name="dss_ilist_traits">ilist_traits</a>
1130 </h4>
1131
1132 <div>
1133 <p><tt>ilist_traits&lt;T&gt;</tt> is <tt>ilist&lt;T&gt;</tt>'s customization
1134 mechanism. <tt>iplist&lt;T&gt;</tt> (and consequently <tt>ilist&lt;T&gt;</tt>)
1135 publicly derive from this traits class.</p>
1136 </div>
1137
1138 <!-- _______________________________________________________________________ -->
1139 <h4>
1140   <a name="dss_iplist">iplist</a>
1141 </h4>
1142
1143 <div>
1144 <p><tt>iplist&lt;T&gt;</tt> is <tt>ilist&lt;T&gt;</tt>'s base and as such
1145 supports a slightly narrower interface. Notably, inserters from
1146 <tt>T&amp;</tt> are absent.</p>
1147
1148 <p><tt>ilist_traits&lt;T&gt;</tt> is a public base of this class and can be
1149 used for a wide variety of customizations.</p>
1150 </div>
1151
1152 <!-- _______________________________________________________________________ -->
1153 <h4>
1154   <a name="dss_ilist_node">llvm/ADT/ilist_node.h</a>
1155 </h4>
1156
1157 <div>
1158 <p><tt>ilist_node&lt;T&gt;</tt> implements a the forward and backward links
1159 that are expected by the <tt>ilist&lt;T&gt;</tt> (and analogous containers)
1160 in the default manner.</p>
1161
1162 <p><tt>ilist_node&lt;T&gt;</tt>s are meant to be embedded in the node type
1163 <tt>T</tt>, usually <tt>T</tt> publicly derives from
1164 <tt>ilist_node&lt;T&gt;</tt>.</p>
1165 </div>
1166
1167 <!-- _______________________________________________________________________ -->
1168 <h4>
1169   <a name="dss_ilist_sentinel">Sentinels</a>
1170 </h4>
1171
1172 <div>
1173 <p><tt>ilist</tt>s have another specialty that must be considered. To be a good
1174 citizen in the C++ ecosystem, it needs to support the standard container
1175 operations, such as <tt>begin</tt> and <tt>end</tt> iterators, etc. Also, the
1176 <tt>operator--</tt> must work correctly on the <tt>end</tt> iterator in the
1177 case of non-empty <tt>ilist</tt>s.</p>
1178
1179 <p>The only sensible solution to this problem is to allocate a so-called
1180 <i>sentinel</i> along with the intrusive list, which serves as the <tt>end</tt>
1181 iterator, providing the back-link to the last element. However conforming to the
1182 C++ convention it is illegal to <tt>operator++</tt> beyond the sentinel and it
1183 also must not be dereferenced.</p>
1184
1185 <p>These constraints allow for some implementation freedom to the <tt>ilist</tt>
1186 how to allocate and store the sentinel. The corresponding policy is dictated
1187 by <tt>ilist_traits&lt;T&gt;</tt>. By default a <tt>T</tt> gets heap-allocated
1188 whenever the need for a sentinel arises.</p>
1189
1190 <p>While the default policy is sufficient in most cases, it may break down when
1191 <tt>T</tt> does not provide a default constructor. Also, in the case of many
1192 instances of <tt>ilist</tt>s, the memory overhead of the associated sentinels
1193 is wasted. To alleviate the situation with numerous and voluminous
1194 <tt>T</tt>-sentinels, sometimes a trick is employed, leading to <i>ghostly
1195 sentinels</i>.</p>
1196
1197 <p>Ghostly sentinels are obtained by specially-crafted <tt>ilist_traits&lt;T&gt;</tt>
1198 which superpose the sentinel with the <tt>ilist</tt> instance in memory. Pointer
1199 arithmetic is used to obtain the sentinel, which is relative to the
1200 <tt>ilist</tt>'s <tt>this</tt> pointer. The <tt>ilist</tt> is augmented by an
1201 extra pointer, which serves as the back-link of the sentinel. This is the only
1202 field in the ghostly sentinel which can be legally accessed.</p>
1203 </div>
1204
1205 <!-- _______________________________________________________________________ -->
1206 <h4>
1207   <a name="dss_other">Other Sequential Container options</a>
1208 </h4>
1209
1210 <div>
1211 <p>Other STL containers are available, such as std::string.</p>
1212
1213 <p>There are also various STL adapter classes such as std::queue,
1214 std::priority_queue, std::stack, etc.  These provide simplified access to an
1215 underlying container but don't affect the cost of the container itself.</p>
1216
1217 </div>
1218 </div>
1219
1220 <!-- ======================================================================= -->
1221 <h3>
1222   <a name="ds_string">String-like containers</a>
1223 </h3>
1224
1225 <div>
1226
1227 <p>
1228 There are a variety of ways to pass around and use strings in C and C++, and
1229 LLVM adds a few new options to choose from.  Pick the first option on this list
1230 that will do what you need, they are ordered according to their relative cost.
1231 </p>
1232 <p>
1233 Note that is is generally preferred to <em>not</em> pass strings around as
1234 "<tt>const char*</tt>"'s.  These have a number of problems, including the fact
1235 that they cannot represent embedded nul ("\0") characters, and do not have a
1236 length available efficiently.  The general replacement for '<tt>const
1237 char*</tt>' is StringRef.
1238 </p>
1239
1240 <p>For more information on choosing string containers for APIs, please see
1241 <a href="#string_apis">Passing strings</a>.</p>
1242
1243
1244 <!-- _______________________________________________________________________ -->
1245 <h4>
1246   <a name="dss_stringref">llvm/ADT/StringRef.h</a>
1247 </h4>
1248
1249 <div>
1250 <p>
1251 The StringRef class is a simple value class that contains a pointer to a
1252 character and a length, and is quite related to the <a
1253 href="#dss_arrayref">ArrayRef</a> class (but specialized for arrays of
1254 characters).  Because StringRef carries a length with it, it safely handles
1255 strings with embedded nul characters in it, getting the length does not require
1256 a strlen call, and it even has very convenient APIs for slicing and dicing the
1257 character range that it represents.
1258 </p>
1259
1260 <p>
1261 StringRef is ideal for passing simple strings around that are known to be live,
1262 either because they are C string literals, std::string, a C array, or a
1263 SmallVector.  Each of these cases has an efficient implicit conversion to
1264 StringRef, which doesn't result in a dynamic strlen being executed.
1265 </p>
1266
1267 <p>StringRef has a few major limitations which make more powerful string
1268 containers useful:</p>
1269
1270 <ol>
1271 <li>You cannot directly convert a StringRef to a 'const char*' because there is
1272 no way to add a trailing nul (unlike the .c_str() method on various stronger
1273 classes).</li>
1274
1275
1276 <li>StringRef doesn't own or keep alive the underlying string bytes.
1277 As such it can easily lead to dangling pointers, and is not suitable for
1278 embedding in datastructures in most cases (instead, use an std::string or
1279 something like that).</li>
1280
1281 <li>For the same reason, StringRef cannot be used as the return value of a
1282 method if the method "computes" the result string.  Instead, use
1283 std::string.</li>
1284
1285 <li>StringRef's do not allow you to mutate the pointed-to string bytes and it
1286 doesn't allow you to insert or remove bytes from the range.  For editing
1287 operations like this, it interoperates with the <a
1288 href="#dss_twine">Twine</a> class.</li>
1289 </ol>
1290
1291 <p>Because of its strengths and limitations, it is very common for a function to
1292 take a StringRef and for a method on an object to return a StringRef that
1293 points into some string that it owns.</p>
1294
1295 </div>
1296
1297 <!-- _______________________________________________________________________ -->
1298 <h4>
1299   <a name="dss_twine">llvm/ADT/Twine.h</a>
1300 </h4>
1301
1302 <div>
1303   <p>
1304   The Twine class is used as an intermediary datatype for APIs that want to take
1305   a string that can be constructed inline with a series of concatenations.
1306   Twine works by forming recursive instances of the Twine datatype (a simple
1307   value object) on the stack as temporary objects, linking them together into a
1308   tree which is then linearized when the Twine is consumed.  Twine is only safe
1309   to use as the argument to a function, and should always be a const reference,
1310   e.g.:
1311   </p>
1312
1313   <pre>
1314     void foo(const Twine &amp;T);
1315     ...
1316     StringRef X = ...
1317     unsigned i = ...
1318     foo(X + "." + Twine(i));
1319   </pre>
1320
1321   <p>This example forms a string like "blarg.42" by concatenating the values
1322   together, and does not form intermediate strings containing "blarg" or
1323   "blarg.".
1324   </p>
1325
1326   <p>Because Twine is constructed with temporary objects on the stack, and
1327   because these instances are destroyed at the end of the current statement,
1328   it is an inherently dangerous API.  For example, this simple variant contains
1329   undefined behavior and will probably crash:</p>
1330
1331   <pre>
1332     void foo(const Twine &amp;T);
1333     ...
1334     StringRef X = ...
1335     unsigned i = ...
1336     const Twine &amp;Tmp = X + "." + Twine(i);
1337     foo(Tmp);
1338   </pre>
1339
1340   <p>... because the temporaries are destroyed before the call.  That said,
1341   Twine's are much more efficient than intermediate std::string temporaries, and
1342   they work really well with StringRef.  Just be aware of their limitations.</p>
1343
1344 </div>
1345
1346
1347 <!-- _______________________________________________________________________ -->
1348 <h4>
1349   <a name="dss_smallstring">llvm/ADT/SmallString.h</a>
1350 </h4>
1351
1352 <div>
1353
1354 <p>SmallString is a subclass of <a href="#dss_smallvector">SmallVector</a> that
1355 adds some convenience APIs like += that takes StringRef's.  SmallString avoids
1356 allocating memory in the case when the preallocated space is enough to hold its
1357 data, and it calls back to general heap allocation when required.  Since it owns
1358 its data, it is very safe to use and supports full mutation of the string.</p>
1359
1360 <p>Like SmallVector's, the big downside to SmallString is their sizeof.  While
1361 they are optimized for small strings, they themselves are not particularly
1362 small.  This means that they work great for temporary scratch buffers on the
1363 stack, but should not generally be put into the heap: it is very rare to
1364 see a SmallString as the member of a frequently-allocated heap data structure
1365 or returned by-value.
1366 </p>
1367
1368 </div>
1369
1370 <!-- _______________________________________________________________________ -->
1371 <h4>
1372   <a name="dss_stdstring">std::string</a>
1373 </h4>
1374
1375 <div>
1376
1377   <p>The standard C++ std::string class is a very general class that (like
1378   SmallString) owns its underlying data.  sizeof(std::string) is very reasonable
1379   so it can be embedded into heap data structures and returned by-value.
1380   On the other hand, std::string is highly inefficient for inline editing (e.g.
1381   concatenating a bunch of stuff together) and because it is provided by the
1382   standard library, its performance characteristics depend a lot of the host
1383   standard library (e.g. libc++ and MSVC provide a highly optimized string
1384   class, GCC contains a really slow implementation).
1385   </p>
1386
1387   <p>The major disadvantage of std::string is that almost every operation that
1388   makes them larger can allocate memory, which is slow.  As such, it is better
1389   to use SmallVector or Twine as a scratch buffer, but then use std::string to
1390   persist the result.</p>
1391
1392
1393 </div>
1394
1395 <!-- end of strings -->
1396 </div>
1397
1398
1399 <!-- ======================================================================= -->
1400 <h3>
1401   <a name="ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a>
1402 </h3>
1403
1404 <div>
1405
1406 <p>Set-like containers are useful when you need to canonicalize multiple values
1407 into a single representation.  There are several different choices for how to do
1408 this, providing various trade-offs.</p>
1409
1410 <!-- _______________________________________________________________________ -->
1411 <h4>
1412   <a name="dss_sortedvectorset">A sorted 'vector'</a>
1413 </h4>
1414
1415 <div>
1416
1417 <p>If you intend to insert a lot of elements, then do a lot of queries, a
1418 great approach is to use a vector (or other sequential container) with
1419 std::sort+std::unique to remove duplicates.  This approach works really well if
1420 your usage pattern has these two distinct phases (insert then query), and can be
1421 coupled with a good choice of <a href="#ds_sequential">sequential container</a>.
1422 </p>
1423
1424 <p>
1425 This combination provides the several nice properties: the result data is
1426 contiguous in memory (good for cache locality), has few allocations, is easy to
1427 address (iterators in the final vector are just indices or pointers), and can be
1428 efficiently queried with a standard binary or radix search.</p>
1429
1430 </div>
1431
1432 <!-- _______________________________________________________________________ -->
1433 <h4>
1434   <a name="dss_smallset">"llvm/ADT/SmallSet.h"</a>
1435 </h4>
1436
1437 <div>
1438
1439 <p>If you have a set-like data structure that is usually small and whose elements
1440 are reasonably small, a <tt>SmallSet&lt;Type, N&gt;</tt> is a good choice.  This set
1441 has space for N elements in place (thus, if the set is dynamically smaller than
1442 N, no malloc traffic is required) and accesses them with a simple linear search.
1443 When the set grows beyond 'N' elements, it allocates a more expensive representation that
1444 guarantees efficient access (for most types, it falls back to std::set, but for
1445 pointers it uses something far better, <a
1446 href="#dss_smallptrset">SmallPtrSet</a>).</p>
1447
1448 <p>The magic of this class is that it handles small sets extremely efficiently,
1449 but gracefully handles extremely large sets without loss of efficiency.  The
1450 drawback is that the interface is quite small: it supports insertion, queries
1451 and erasing, but does not support iteration.</p>
1452
1453 </div>
1454
1455 <!-- _______________________________________________________________________ -->
1456 <h4>
1457   <a name="dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a>
1458 </h4>
1459
1460 <div>
1461
1462 <p>SmallPtrSet has all the advantages of <tt>SmallSet</tt> (and a <tt>SmallSet</tt> of pointers is
1463 transparently implemented with a <tt>SmallPtrSet</tt>), but also supports iterators.  If
1464 more than 'N' insertions are performed, a single quadratically
1465 probed hash table is allocated and grows as needed, providing extremely
1466 efficient access (constant time insertion/deleting/queries with low constant
1467 factors) and is very stingy with malloc traffic.</p>
1468
1469 <p>Note that, unlike <tt>std::set</tt>, the iterators of <tt>SmallPtrSet</tt> are invalidated
1470 whenever an insertion occurs.  Also, the values visited by the iterators are not
1471 visited in sorted order.</p>
1472
1473 </div>
1474
1475 <!-- _______________________________________________________________________ -->
1476 <h4>
1477   <a name="dss_denseset">"llvm/ADT/DenseSet.h"</a>
1478 </h4>
1479
1480 <div>
1481
1482 <p>
1483 DenseSet is a simple quadratically probed hash table.  It excels at supporting
1484 small values: it uses a single allocation to hold all of the pairs that
1485 are currently inserted in the set.  DenseSet is a great way to unique small
1486 values that are not simple pointers (use <a
1487 href="#dss_smallptrset">SmallPtrSet</a> for pointers).  Note that DenseSet has
1488 the same requirements for the value type that <a
1489 href="#dss_densemap">DenseMap</a> has.
1490 </p>
1491
1492 </div>
1493
1494 <!-- _______________________________________________________________________ -->
1495 <h4>
1496   <a name="dss_sparseset">"llvm/ADT/SparseSet.h"</a>
1497 </h4>
1498
1499 <div>
1500
1501 <p>SparseSet holds a small number of objects identified by unsigned keys of
1502 moderate size. It uses a lot of memory, but provides operations that are
1503 almost as fast as a vector. Typical keys are physical registers, virtual
1504 registers, or numbered basic blocks.</p>
1505
1506 <p>SparseSet is useful for algorithms that need very fast clear/find/insert/erase
1507 and fast iteration over small sets.  It is not intended for building composite
1508 data structures.</p>
1509
1510 </div>
1511
1512 <!-- _______________________________________________________________________ -->
1513 <h4>
1514   <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a>
1515 </h4>
1516
1517 <div>
1518
1519 <p>
1520 FoldingSet is an aggregate class that is really good at uniquing
1521 expensive-to-create or polymorphic objects.  It is a combination of a chained
1522 hash table with intrusive links (uniqued objects are required to inherit from
1523 FoldingSetNode) that uses <a href="#dss_smallvector">SmallVector</a> as part of
1524 its ID process.</p>
1525
1526 <p>Consider a case where you want to implement a "getOrCreateFoo" method for
1527 a complex object (for example, a node in the code generator).  The client has a
1528 description of *what* it wants to generate (it knows the opcode and all the
1529 operands), but we don't want to 'new' a node, then try inserting it into a set
1530 only to find out it already exists, at which point we would have to delete it
1531 and return the node that already exists.
1532 </p>
1533
1534 <p>To support this style of client, FoldingSet perform a query with a
1535 FoldingSetNodeID (which wraps SmallVector) that can be used to describe the
1536 element that we want to query for.  The query either returns the element
1537 matching the ID or it returns an opaque ID that indicates where insertion should
1538 take place.  Construction of the ID usually does not require heap traffic.</p>
1539
1540 <p>Because FoldingSet uses intrusive links, it can support polymorphic objects
1541 in the set (for example, you can have SDNode instances mixed with LoadSDNodes).
1542 Because the elements are individually allocated, pointers to the elements are
1543 stable: inserting or removing elements does not invalidate any pointers to other
1544 elements.
1545 </p>
1546
1547 </div>
1548
1549 <!-- _______________________________________________________________________ -->
1550 <h4>
1551   <a name="dss_set">&lt;set&gt;</a>
1552 </h4>
1553
1554 <div>
1555
1556 <p><tt>std::set</tt> is a reasonable all-around set class, which is decent at
1557 many things but great at nothing.  std::set allocates memory for each element
1558 inserted (thus it is very malloc intensive) and typically stores three pointers
1559 per element in the set (thus adding a large amount of per-element space
1560 overhead).  It offers guaranteed log(n) performance, which is not particularly
1561 fast from a complexity standpoint (particularly if the elements of the set are
1562 expensive to compare, like strings), and has extremely high constant factors for
1563 lookup, insertion and removal.</p>
1564
1565 <p>The advantages of std::set are that its iterators are stable (deleting or
1566 inserting an element from the set does not affect iterators or pointers to other
1567 elements) and that iteration over the set is guaranteed to be in sorted order.
1568 If the elements in the set are large, then the relative overhead of the pointers
1569 and malloc traffic is not a big deal, but if the elements of the set are small,
1570 std::set is almost never a good choice.</p>
1571
1572 </div>
1573
1574 <!-- _______________________________________________________________________ -->
1575 <h4>
1576   <a name="dss_setvector">"llvm/ADT/SetVector.h"</a>
1577 </h4>
1578
1579 <div>
1580 <p>LLVM's SetVector&lt;Type&gt; is an adapter class that combines your choice of
1581 a set-like container along with a <a href="#ds_sequential">Sequential
1582 Container</a>.  The important property
1583 that this provides is efficient insertion with uniquing (duplicate elements are
1584 ignored) with iteration support.  It implements this by inserting elements into
1585 both a set-like container and the sequential container, using the set-like
1586 container for uniquing and the sequential container for iteration.
1587 </p>
1588
1589 <p>The difference between SetVector and other sets is that the order of
1590 iteration is guaranteed to match the order of insertion into the SetVector.
1591 This property is really important for things like sets of pointers.  Because
1592 pointer values are non-deterministic (e.g. vary across runs of the program on
1593 different machines), iterating over the pointers in the set will
1594 not be in a well-defined order.</p>
1595
1596 <p>
1597 The drawback of SetVector is that it requires twice as much space as a normal
1598 set and has the sum of constant factors from the set-like container and the
1599 sequential container that it uses.  Use it *only* if you need to iterate over
1600 the elements in a deterministic order.  SetVector is also expensive to delete
1601 elements out of (linear time), unless you use it's "pop_back" method, which is
1602 faster.
1603 </p>
1604
1605 <p><tt>SetVector</tt> is an adapter class that defaults to
1606    using <tt>std::vector</tt> and a size 16 <tt>SmallSet</tt> for the underlying
1607    containers, so it is quite expensive. However,
1608    <tt>"llvm/ADT/SetVector.h"</tt> also provides a <tt>SmallSetVector</tt>
1609    class, which defaults to using a <tt>SmallVector</tt> and <tt>SmallSet</tt>
1610    of a specified size. If you use this, and if your sets are dynamically
1611    smaller than <tt>N</tt>, you will save a lot of heap traffic.</p>
1612
1613 </div>
1614
1615 <!-- _______________________________________________________________________ -->
1616 <h4>
1617   <a name="dss_uniquevector">"llvm/ADT/UniqueVector.h"</a>
1618 </h4>
1619
1620 <div>
1621
1622 <p>
1623 UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it
1624 retains a unique ID for each element inserted into the set.  It internally
1625 contains a map and a vector, and it assigns a unique ID for each value inserted
1626 into the set.</p>
1627
1628 <p>UniqueVector is very expensive: its cost is the sum of the cost of
1629 maintaining both the map and vector, it has high complexity, high constant
1630 factors, and produces a lot of malloc traffic.  It should be avoided.</p>
1631
1632 </div>
1633
1634 <!-- _______________________________________________________________________ -->
1635 <h4>
1636   <a name="dss_immutableset">"llvm/ADT/ImmutableSet.h"</a>
1637 </h4>
1638
1639 <div>
1640
1641 <p>
1642 ImmutableSet is an immutable (functional) set implementation based on an AVL
1643 tree.
1644 Adding or removing elements is done through a Factory object and results in the
1645 creation of a new ImmutableSet object.
1646 If an ImmutableSet already exists with the given contents, then the existing one
1647 is returned; equality is compared with a FoldingSetNodeID.
1648 The time and space complexity of add or remove operations is logarithmic in the
1649 size of the original set.
1650
1651 <p>
1652 There is no method for returning an element of the set, you can only check for
1653 membership.
1654
1655 </div>
1656
1657
1658 <!-- _______________________________________________________________________ -->
1659 <h4>
1660   <a name="dss_otherset">Other Set-Like Container Options</a>
1661 </h4>
1662
1663 <div>
1664
1665 <p>
1666 The STL provides several other options, such as std::multiset and the various
1667 "hash_set" like containers (whether from C++ TR1 or from the SGI library). We
1668 never use hash_set and unordered_set because they are generally very expensive
1669 (each insertion requires a malloc) and very non-portable.
1670 </p>
1671
1672 <p>std::multiset is useful if you're not interested in elimination of
1673 duplicates, but has all the drawbacks of std::set.  A sorted vector (where you
1674 don't delete duplicate entries) or some other approach is almost always
1675 better.</p>
1676
1677 </div>
1678
1679 </div>
1680
1681 <!-- ======================================================================= -->
1682 <h3>
1683   <a name="ds_map">Map-Like Containers (std::map, DenseMap, etc)</a>
1684 </h3>
1685
1686 <div>
1687 Map-like containers are useful when you want to associate data to a key.  As
1688 usual, there are a lot of different ways to do this. :)
1689
1690 <!-- _______________________________________________________________________ -->
1691 <h4>
1692   <a name="dss_sortedvectormap">A sorted 'vector'</a>
1693 </h4>
1694
1695 <div>
1696
1697 <p>
1698 If your usage pattern follows a strict insert-then-query approach, you can
1699 trivially use the same approach as <a href="#dss_sortedvectorset">sorted vectors
1700 for set-like containers</a>.  The only difference is that your query function
1701 (which uses std::lower_bound to get efficient log(n) lookup) should only compare
1702 the key, not both the key and value.  This yields the same advantages as sorted
1703 vectors for sets.
1704 </p>
1705 </div>
1706
1707 <!-- _______________________________________________________________________ -->
1708 <h4>
1709   <a name="dss_stringmap">"llvm/ADT/StringMap.h"</a>
1710 </h4>
1711
1712 <div>
1713
1714 <p>
1715 Strings are commonly used as keys in maps, and they are difficult to support
1716 efficiently: they are variable length, inefficient to hash and compare when
1717 long, expensive to copy, etc.  StringMap is a specialized container designed to
1718 cope with these issues.  It supports mapping an arbitrary range of bytes to an
1719 arbitrary other object.</p>
1720
1721 <p>The StringMap implementation uses a quadratically-probed hash table, where
1722 the buckets store a pointer to the heap allocated entries (and some other
1723 stuff).  The entries in the map must be heap allocated because the strings are
1724 variable length.  The string data (key) and the element object (value) are
1725 stored in the same allocation with the string data immediately after the element
1726 object.  This container guarantees the "<tt>(char*)(&amp;Value+1)</tt>" points
1727 to the key string for a value.</p>
1728
1729 <p>The StringMap is very fast for several reasons: quadratic probing is very
1730 cache efficient for lookups, the hash value of strings in buckets is not
1731 recomputed when looking up an element, StringMap rarely has to touch the
1732 memory for unrelated objects when looking up a value (even when hash collisions
1733 happen), hash table growth does not recompute the hash values for strings
1734 already in the table, and each pair in the map is store in a single allocation
1735 (the string data is stored in the same allocation as the Value of a pair).</p>
1736
1737 <p>StringMap also provides query methods that take byte ranges, so it only ever
1738 copies a string if a value is inserted into the table.</p>
1739
1740 <p>StringMap iteratation order, however, is not guaranteed to be deterministic,
1741 so any uses which require that should instead use a std::map.</p>
1742 </div>
1743
1744 <!-- _______________________________________________________________________ -->
1745 <h4>
1746   <a name="dss_indexedmap">"llvm/ADT/IndexedMap.h"</a>
1747 </h4>
1748
1749 <div>
1750 <p>
1751 IndexedMap is a specialized container for mapping small dense integers (or
1752 values that can be mapped to small dense integers) to some other type.  It is
1753 internally implemented as a vector with a mapping function that maps the keys to
1754 the dense integer range.
1755 </p>
1756
1757 <p>
1758 This is useful for cases like virtual registers in the LLVM code generator: they
1759 have a dense mapping that is offset by a compile-time constant (the first
1760 virtual register ID).</p>
1761
1762 </div>
1763
1764 <!-- _______________________________________________________________________ -->
1765 <h4>
1766   <a name="dss_densemap">"llvm/ADT/DenseMap.h"</a>
1767 </h4>
1768
1769 <div>
1770
1771 <p>
1772 DenseMap is a simple quadratically probed hash table.  It excels at supporting
1773 small keys and values: it uses a single allocation to hold all of the pairs that
1774 are currently inserted in the map.  DenseMap is a great way to map pointers to
1775 pointers, or map other small types to each other.
1776 </p>
1777
1778 <p>
1779 There are several aspects of DenseMap that you should be aware of, however.  The
1780 iterators in a DenseMap are invalidated whenever an insertion occurs, unlike
1781 map.  Also, because DenseMap allocates space for a large number of key/value
1782 pairs (it starts with 64 by default), it will waste a lot of space if your keys
1783 or values are large.  Finally, you must implement a partial specialization of
1784 DenseMapInfo for the key that you want, if it isn't already supported.  This
1785 is required to tell DenseMap about two special marker values (which can never be
1786 inserted into the map) that it needs internally.</p>
1787
1788 <p>
1789 DenseMap's find_as() method supports lookup operations using an alternate key
1790 type. This is useful in cases where the normal key type is expensive to
1791 construct, but cheap to compare against. The DenseMapInfo is responsible for
1792 defining the appropriate comparison and hashing methods for each alternate
1793 key type used.
1794 </p>
1795
1796 </div>
1797
1798 <!-- _______________________________________________________________________ -->
1799 <h4>
1800   <a name="dss_valuemap">"llvm/ADT/ValueMap.h"</a>
1801 </h4>
1802
1803 <div>
1804
1805 <p>
1806 ValueMap is a wrapper around a <a href="#dss_densemap">DenseMap</a> mapping
1807 Value*s (or subclasses) to another type.  When a Value is deleted or RAUW'ed,
1808 ValueMap will update itself so the new version of the key is mapped to the same
1809 value, just as if the key were a WeakVH.  You can configure exactly how this
1810 happens, and what else happens on these two events, by passing
1811 a <code>Config</code> parameter to the ValueMap template.</p>
1812
1813 </div>
1814
1815 <!-- _______________________________________________________________________ -->
1816 <h4>
1817   <a name="dss_intervalmap">"llvm/ADT/IntervalMap.h"</a>
1818 </h4>
1819
1820 <div>
1821
1822 <p> IntervalMap is a compact map for small keys and values. It maps key
1823 intervals instead of single keys, and it will automatically coalesce adjacent
1824 intervals. When then map only contains a few intervals, they are stored in the
1825 map object itself to avoid allocations.</p>
1826
1827 <p> The IntervalMap iterators are quite big, so they should not be passed around
1828 as STL iterators. The heavyweight iterators allow a smaller data structure.</p>
1829
1830 </div>
1831
1832 <!-- _______________________________________________________________________ -->
1833 <h4>
1834   <a name="dss_map">&lt;map&gt;</a>
1835 </h4>
1836
1837 <div>
1838
1839 <p>
1840 std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses
1841 a single allocation per pair inserted into the map, it offers log(n) lookup with
1842 an extremely large constant factor, imposes a space penalty of 3 pointers per
1843 pair in the map, etc.</p>
1844
1845 <p>std::map is most useful when your keys or values are very large, if you need
1846 to iterate over the collection in sorted order, or if you need stable iterators
1847 into the map (i.e. they don't get invalidated if an insertion or deletion of
1848 another element takes place).</p>
1849
1850 </div>
1851
1852
1853 <!-- _______________________________________________________________________ -->
1854 <h4>
1855   <a name="dss_mapvector">"llvm/ADT/MapVector.h"</a>
1856 </h4>
1857 <div>
1858
1859 <p> MapVector&lt;KeyT,ValueT&gt provides a subset of the DenseMap interface.
1860   The main difference is that the iteration order is guaranteed to be
1861   the insertion order, making it an easy (but somewhat expensive) solution
1862   for non-deterministic iteration over maps of pointers. </p>
1863
1864 <p> It is implemented by mapping from key to an index in a vector of key,value
1865   pairs. This provides fast lookup and iteration, but has two main drawbacks:
1866   The key is stored twice and it doesn't support removing elements. </p>
1867
1868 </div>
1869
1870 <!-- _______________________________________________________________________ -->
1871 <h4>
1872   <a name="dss_inteqclasses">"llvm/ADT/IntEqClasses.h"</a>
1873 </h4>
1874
1875 <div>
1876
1877 <p>IntEqClasses provides a compact representation of equivalence classes of
1878 small integers. Initially, each integer in the range 0..n-1 has its own
1879 equivalence class. Classes can be joined by passing two class representatives to
1880 the join(a, b) method. Two integers are in the same class when findLeader()
1881 returns the same representative.</p>
1882
1883 <p>Once all equivalence classes are formed, the map can be compressed so each
1884 integer 0..n-1 maps to an equivalence class number in the range 0..m-1, where m
1885 is the total number of equivalence classes. The map must be uncompressed before
1886 it can be edited again.</p>
1887
1888 </div>
1889
1890 <!-- _______________________________________________________________________ -->
1891 <h4>
1892   <a name="dss_immutablemap">"llvm/ADT/ImmutableMap.h"</a>
1893 </h4>
1894
1895 <div>
1896
1897 <p>
1898 ImmutableMap is an immutable (functional) map implementation based on an AVL
1899 tree.
1900 Adding or removing elements is done through a Factory object and results in the
1901 creation of a new ImmutableMap object.
1902 If an ImmutableMap already exists with the given key set, then the existing one
1903 is returned; equality is compared with a FoldingSetNodeID.
1904 The time and space complexity of add or remove operations is logarithmic in the
1905 size of the original map.
1906
1907 </div>
1908
1909 <!-- _______________________________________________________________________ -->
1910 <h4>
1911   <a name="dss_othermap">Other Map-Like Container Options</a>
1912 </h4>
1913
1914 <div>
1915
1916 <p>
1917 The STL provides several other options, such as std::multimap and the various
1918 "hash_map" like containers (whether from C++ TR1 or from the SGI library). We
1919 never use hash_set and unordered_set because they are generally very expensive
1920 (each insertion requires a malloc) and very non-portable.</p>
1921
1922 <p>std::multimap is useful if you want to map a key to multiple values, but has
1923 all the drawbacks of std::map.  A sorted vector or some other approach is almost
1924 always better.</p>
1925
1926 </div>
1927
1928 </div>
1929
1930 <!-- ======================================================================= -->
1931 <h3>
1932   <a name="ds_bit">Bit storage containers (BitVector, SparseBitVector)</a>
1933 </h3>
1934
1935 <div>
1936 <p>Unlike the other containers, there are only two bit storage containers, and
1937 choosing when to use each is relatively straightforward.</p>
1938
1939 <p>One additional option is
1940 <tt>std::vector&lt;bool&gt;</tt>: we discourage its use for two reasons 1) the
1941 implementation in many common compilers (e.g. commonly available versions of
1942 GCC) is extremely inefficient and 2) the C++ standards committee is likely to
1943 deprecate this container and/or change it significantly somehow.  In any case,
1944 please don't use it.</p>
1945
1946 <!-- _______________________________________________________________________ -->
1947 <h4>
1948   <a name="dss_bitvector">BitVector</a>
1949 </h4>
1950
1951 <div>
1952 <p> The BitVector container provides a dynamic size set of bits for manipulation.
1953 It supports individual bit setting/testing, as well as set operations.  The set
1954 operations take time O(size of bitvector), but operations are performed one word
1955 at a time, instead of one bit at a time.  This makes the BitVector very fast for
1956 set operations compared to other containers.  Use the BitVector when you expect
1957 the number of set bits to be high (IE a dense set).
1958 </p>
1959 </div>
1960
1961 <!-- _______________________________________________________________________ -->
1962 <h4>
1963   <a name="dss_smallbitvector">SmallBitVector</a>
1964 </h4>
1965
1966 <div>
1967 <p> The SmallBitVector container provides the same interface as BitVector, but
1968 it is optimized for the case where only a small number of bits, less than
1969 25 or so, are needed. It also transparently supports larger bit counts, but
1970 slightly less efficiently than a plain BitVector, so SmallBitVector should
1971 only be used when larger counts are rare.
1972 </p>
1973
1974 <p>
1975 At this time, SmallBitVector does not support set operations (and, or, xor),
1976 and its operator[] does not provide an assignable lvalue.
1977 </p>
1978 </div>
1979
1980 <!-- _______________________________________________________________________ -->
1981 <h4>
1982   <a name="dss_sparsebitvector">SparseBitVector</a>
1983 </h4>
1984
1985 <div>
1986 <p> The SparseBitVector container is much like BitVector, with one major
1987 difference: Only the bits that are set, are stored.  This makes the
1988 SparseBitVector much more space efficient than BitVector when the set is sparse,
1989 as well as making set operations O(number of set bits) instead of O(size of
1990 universe).  The downside to the SparseBitVector is that setting and testing of random bits is O(N), and on large SparseBitVectors, this can be slower than BitVector. In our implementation, setting or testing bits in sorted order
1991 (either forwards or reverse) is O(1) worst case.  Testing and setting bits within 128 bits (depends on size) of the current bit is also O(1).  As a general statement, testing/setting bits in a SparseBitVector is O(distance away from last set bit).
1992 </p>
1993 </div>
1994
1995 </div>
1996
1997 </div>
1998
1999 <!-- *********************************************************************** -->
2000 <h2>
2001   <a name="common">Helpful Hints for Common Operations</a>
2002 </h2>
2003 <!-- *********************************************************************** -->
2004
2005 <div>
2006
2007 <p>This section describes how to perform some very simple transformations of
2008 LLVM code.  This is meant to give examples of common idioms used, showing the
2009 practical side of LLVM transformations.  <p> Because this is a "how-to" section,
2010 you should also read about the main classes that you will be working with.  The
2011 <a href="#coreclasses">Core LLVM Class Hierarchy Reference</a> contains details
2012 and descriptions of the main classes that you should know about.</p>
2013
2014 <!-- NOTE: this section should be heavy on example code -->
2015 <!-- ======================================================================= -->
2016 <h3>
2017   <a name="inspection">Basic Inspection and Traversal Routines</a>
2018 </h3>
2019
2020 <div>
2021
2022 <p>The LLVM compiler infrastructure have many different data structures that may
2023 be traversed.  Following the example of the C++ standard template library, the
2024 techniques used to traverse these various data structures are all basically the
2025 same.  For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or
2026 method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt>
2027 function returns an iterator pointing to one past the last valid element of the
2028 sequence, and there is some <tt>XXXiterator</tt> data type that is common
2029 between the two operations.</p>
2030
2031 <p>Because the pattern for iteration is common across many different aspects of
2032 the program representation, the standard template library algorithms may be used
2033 on them, and it is easier to remember how to iterate. First we show a few common
2034 examples of the data structures that need to be traversed.  Other data
2035 structures are traversed in very similar ways.</p>
2036
2037 <!-- _______________________________________________________________________ -->
2038 <h4>
2039   <a name="iterate_function">Iterating over the </a><a
2040   href="#BasicBlock"><tt>BasicBlock</tt></a>s in a <a
2041   href="#Function"><tt>Function</tt></a>
2042 </h4>
2043
2044 <div>
2045
2046 <p>It's quite common to have a <tt>Function</tt> instance that you'd like to
2047 transform in some way; in particular, you'd like to manipulate its
2048 <tt>BasicBlock</tt>s.  To facilitate this, you'll need to iterate over all of
2049 the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>. The following is
2050 an example that prints the name of a <tt>BasicBlock</tt> and the number of
2051 <tt>Instruction</tt>s it contains:</p>
2052
2053 <div class="doc_code">
2054 <pre>
2055 // <i>func is a pointer to a Function instance</i>
2056 for (Function::iterator i = func-&gt;begin(), e = func-&gt;end(); i != e; ++i)
2057   // <i>Print out the name of the basic block if it has one, and then the</i>
2058   // <i>number of instructions that it contains</i>
2059   errs() &lt;&lt; "Basic block (name=" &lt;&lt; i-&gt;getName() &lt;&lt; ") has "
2060              &lt;&lt; i-&gt;size() &lt;&lt; " instructions.\n";
2061 </pre>
2062 </div>
2063
2064 <p>Note that i can be used as if it were a pointer for the purposes of
2065 invoking member functions of the <tt>Instruction</tt> class.  This is
2066 because the indirection operator is overloaded for the iterator
2067 classes.  In the above code, the expression <tt>i-&gt;size()</tt> is
2068 exactly equivalent to <tt>(*i).size()</tt> just like you'd expect.</p>
2069
2070 </div>
2071
2072 <!-- _______________________________________________________________________ -->
2073 <h4>
2074   <a name="iterate_basicblock">Iterating over the </a><a
2075   href="#Instruction"><tt>Instruction</tt></a>s in a <a
2076   href="#BasicBlock"><tt>BasicBlock</tt></a>
2077 </h4>
2078
2079 <div>
2080
2081 <p>Just like when dealing with <tt>BasicBlock</tt>s in <tt>Function</tt>s, it's
2082 easy to iterate over the individual instructions that make up
2083 <tt>BasicBlock</tt>s. Here's a code snippet that prints out each instruction in
2084 a <tt>BasicBlock</tt>:</p>
2085
2086 <div class="doc_code">
2087 <pre>
2088 // <i>blk is a pointer to a BasicBlock instance</i>
2089 for (BasicBlock::iterator i = blk-&gt;begin(), e = blk-&gt;end(); i != e; ++i)
2090    // <i>The next statement works since operator&lt;&lt;(ostream&amp;,...)</i>
2091    // <i>is overloaded for Instruction&amp;</i>
2092    errs() &lt;&lt; *i &lt;&lt; "\n";
2093 </pre>
2094 </div>
2095
2096 <p>However, this isn't really the best way to print out the contents of a
2097 <tt>BasicBlock</tt>!  Since the ostream operators are overloaded for virtually
2098 anything you'll care about, you could have just invoked the print routine on the
2099 basic block itself: <tt>errs() &lt;&lt; *blk &lt;&lt; "\n";</tt>.</p>
2100
2101 </div>
2102
2103 <!-- _______________________________________________________________________ -->
2104 <h4>
2105   <a name="iterate_institer">Iterating over the </a><a
2106   href="#Instruction"><tt>Instruction</tt></a>s in a <a
2107   href="#Function"><tt>Function</tt></a>
2108 </h4>
2109
2110 <div>
2111
2112 <p>If you're finding that you commonly iterate over a <tt>Function</tt>'s
2113 <tt>BasicBlock</tt>s and then that <tt>BasicBlock</tt>'s <tt>Instruction</tt>s,
2114 <tt>InstIterator</tt> should be used instead. You'll need to include <a
2115 href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>,
2116 and then instantiate <tt>InstIterator</tt>s explicitly in your code.  Here's a
2117 small example that shows how to dump all instructions in a function to the standard error stream:<p>
2118
2119 <div class="doc_code">
2120 <pre>
2121 #include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>"
2122
2123 // <i>F is a pointer to a Function instance</i>
2124 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
2125   errs() &lt;&lt; *I &lt;&lt; "\n";
2126 </pre>
2127 </div>
2128
2129 <p>Easy, isn't it?  You can also use <tt>InstIterator</tt>s to fill a
2130 work list with its initial contents.  For example, if you wanted to
2131 initialize a work list to contain all instructions in a <tt>Function</tt>
2132 F, all you would need to do is something like:</p>
2133
2134 <div class="doc_code">
2135 <pre>
2136 std::set&lt;Instruction*&gt; worklist;
2137 // or better yet, SmallPtrSet&lt;Instruction*, 64&gt; worklist;
2138
2139 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
2140    worklist.insert(&amp;*I);
2141 </pre>
2142 </div>
2143
2144 <p>The STL set <tt>worklist</tt> would now contain all instructions in the
2145 <tt>Function</tt> pointed to by F.</p>
2146
2147 </div>
2148
2149 <!-- _______________________________________________________________________ -->
2150 <h4>
2151   <a name="iterate_convert">Turning an iterator into a class pointer (and
2152   vice-versa)</a>
2153 </h4>
2154
2155 <div>
2156
2157 <p>Sometimes, it'll be useful to grab a reference (or pointer) to a class
2158 instance when all you've got at hand is an iterator.  Well, extracting
2159 a reference or a pointer from an iterator is very straight-forward.
2160 Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and <tt>j</tt>
2161 is a <tt>BasicBlock::const_iterator</tt>:</p>
2162
2163 <div class="doc_code">
2164 <pre>
2165 Instruction&amp; inst = *i;   // <i>Grab reference to instruction reference</i>
2166 Instruction* pinst = &amp;*i; // <i>Grab pointer to instruction reference</i>
2167 const Instruction&amp; inst = *j;
2168 </pre>
2169 </div>
2170
2171 <p>However, the iterators you'll be working with in the LLVM framework are
2172 special: they will automatically convert to a ptr-to-instance type whenever they
2173 need to.  Instead of dereferencing the iterator and then taking the address of
2174 the result, you can simply assign the iterator to the proper pointer type and
2175 you get the dereference and address-of operation as a result of the assignment
2176 (behind the scenes, this is a result of overloading casting mechanisms).  Thus
2177 the last line of the last example,</p>
2178
2179 <div class="doc_code">
2180 <pre>
2181 Instruction *pinst = &amp;*i;
2182 </pre>
2183 </div>
2184
2185 <p>is semantically equivalent to</p>
2186
2187 <div class="doc_code">
2188 <pre>
2189 Instruction *pinst = i;
2190 </pre>
2191 </div>
2192
2193 <p>It's also possible to turn a class pointer into the corresponding iterator,
2194 and this is a constant time operation (very efficient).  The following code
2195 snippet illustrates use of the conversion constructors provided by LLVM
2196 iterators.  By using these, you can explicitly grab the iterator of something
2197 without actually obtaining it via iteration over some structure:</p>
2198
2199 <div class="doc_code">
2200 <pre>
2201 void printNextInstruction(Instruction* inst) {
2202   BasicBlock::iterator it(inst);
2203   ++it; // <i>After this line, it refers to the instruction after *inst</i>
2204   if (it != inst-&gt;getParent()-&gt;end()) errs() &lt;&lt; *it &lt;&lt; "\n";
2205 }
2206 </pre>
2207 </div>
2208
2209 <p>Unfortunately, these implicit conversions come at a cost; they prevent
2210 these iterators from conforming to standard iterator conventions, and thus
2211 from being usable with standard algorithms and containers. For example, they
2212 prevent the following code, where <tt>B</tt> is a <tt>BasicBlock</tt>,
2213 from compiling:</p>
2214
2215 <div class="doc_code">
2216 <pre>
2217   llvm::SmallVector&lt;llvm::Instruction *, 16&gt;(B-&gt;begin(), B-&gt;end());
2218 </pre>
2219 </div>
2220
2221 <p>Because of this, these implicit conversions may be removed some day,
2222 and <tt>operator*</tt> changed to return a pointer instead of a reference.</p>
2223
2224 </div>
2225
2226 <!--_______________________________________________________________________-->
2227 <h4>
2228   <a name="iterate_complex">Finding call sites: a slightly more complex
2229   example</a>
2230 </h4>
2231
2232 <div>
2233
2234 <p>Say that you're writing a FunctionPass and would like to count all the
2235 locations in the entire module (that is, across every <tt>Function</tt>) where a
2236 certain function (i.e., some <tt>Function</tt>*) is already in scope.  As you'll
2237 learn later, you may want to use an <tt>InstVisitor</tt> to accomplish this in a
2238 much more straight-forward manner, but this example will allow us to explore how
2239 you'd do it if you didn't have <tt>InstVisitor</tt> around. In pseudo-code, this
2240 is what we want to do:</p>
2241
2242 <div class="doc_code">
2243 <pre>
2244 initialize callCounter to zero
2245 for each Function f in the Module
2246   for each BasicBlock b in f
2247     for each Instruction i in b
2248       if (i is a CallInst and calls the given function)
2249         increment callCounter
2250 </pre>
2251 </div>
2252
2253 <p>And the actual code is (remember, because we're writing a
2254 <tt>FunctionPass</tt>, our <tt>FunctionPass</tt>-derived class simply has to
2255 override the <tt>runOnFunction</tt> method):</p>
2256
2257 <div class="doc_code">
2258 <pre>
2259 Function* targetFunc = ...;
2260
2261 class OurFunctionPass : public FunctionPass {
2262   public:
2263     OurFunctionPass(): callCounter(0) { }
2264
2265     virtual runOnFunction(Function&amp; F) {
2266       for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) {
2267         for (BasicBlock::iterator i = b-&gt;begin(), ie = b-&gt;end(); i != ie; ++i) {
2268           if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a>&lt;<a
2269  href="#CallInst">CallInst</a>&gt;(&amp;*i)) {
2270             // <i>We know we've encountered a call instruction, so we</i>
2271             // <i>need to determine if it's a call to the</i>
2272             // <i>function pointed to by m_func or not.</i>
2273             if (callInst-&gt;getCalledFunction() == targetFunc)
2274               ++callCounter;
2275           }
2276         }
2277       }
2278     }
2279
2280   private:
2281     unsigned callCounter;
2282 };
2283 </pre>
2284 </div>
2285
2286 </div>
2287
2288 <!--_______________________________________________________________________-->
2289 <h4>
2290   <a name="calls_and_invokes">Treating calls and invokes the same way</a>
2291 </h4>
2292
2293 <div>
2294
2295 <p>You may have noticed that the previous example was a bit oversimplified in
2296 that it did not deal with call sites generated by 'invoke' instructions. In
2297 this, and in other situations, you may find that you want to treat
2298 <tt>CallInst</tt>s and <tt>InvokeInst</tt>s the same way, even though their
2299 most-specific common base class is <tt>Instruction</tt>, which includes lots of
2300 less closely-related things. For these cases, LLVM provides a handy wrapper
2301 class called <a
2302 href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>.
2303 It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some
2304 methods that provide functionality common to <tt>CallInst</tt>s and
2305 <tt>InvokeInst</tt>s.</p>
2306
2307 <p>This class has "value semantics": it should be passed by value, not by
2308 reference and it should not be dynamically allocated or deallocated using
2309 <tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable,
2310 assignable and constructable, with costs equivalents to that of a bare pointer.
2311 If you look at its definition, it has only a single pointer member.</p>
2312
2313 </div>
2314
2315 <!--_______________________________________________________________________-->
2316 <h4>
2317   <a name="iterate_chains">Iterating over def-use &amp; use-def chains</a>
2318 </h4>
2319
2320 <div>
2321
2322 <p>Frequently, we might have an instance of the <a
2323 href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to
2324 determine which <tt>User</tt>s use the <tt>Value</tt>.  The list of all
2325 <tt>User</tt>s of a particular <tt>Value</tt> is called a <i>def-use</i> chain.
2326 For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a
2327 particular function <tt>foo</tt>. Finding all of the instructions that
2328 <i>use</i> <tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain
2329 of <tt>F</tt>:</p>
2330
2331 <div class="doc_code">
2332 <pre>
2333 Function *F = ...;
2334
2335 for (Value::use_iterator i = F-&gt;use_begin(), e = F-&gt;use_end(); i != e; ++i)
2336   if (Instruction *Inst = dyn_cast&lt;Instruction&gt;(*i)) {
2337     errs() &lt;&lt; "F is used in instruction:\n";
2338     errs() &lt;&lt; *Inst &lt;&lt; "\n";
2339   }
2340 </pre>
2341 </div>
2342
2343 <p>Note that dereferencing a <tt>Value::use_iterator</tt> is not a very cheap
2344 operation. Instead of performing <tt>*i</tt> above several times, consider
2345 doing it only once in the loop body and reusing its result.</p>
2346
2347 <p>Alternatively, it's common to have an instance of the <a
2348 href="/doxygen/classllvm_1_1User.html">User Class</a> and need to know what
2349 <tt>Value</tt>s are used by it.  The list of all <tt>Value</tt>s used by a
2350 <tt>User</tt> is known as a <i>use-def</i> chain.  Instances of class
2351 <tt>Instruction</tt> are common <tt>User</tt>s, so we might want to iterate over
2352 all of the values that a particular instruction uses (that is, the operands of
2353 the particular <tt>Instruction</tt>):</p>
2354
2355 <div class="doc_code">
2356 <pre>
2357 Instruction *pi = ...;
2358
2359 for (User::op_iterator i = pi-&gt;op_begin(), e = pi-&gt;op_end(); i != e; ++i) {
2360   Value *v = *i;
2361   // <i>...</i>
2362 }
2363 </pre>
2364 </div>
2365
2366 <p>Declaring objects as <tt>const</tt> is an important tool of enforcing
2367 mutation free algorithms (such as analyses, etc.). For this purpose above
2368 iterators come in constant flavors as <tt>Value::const_use_iterator</tt>
2369 and <tt>Value::const_op_iterator</tt>.  They automatically arise when
2370 calling <tt>use/op_begin()</tt> on <tt>const Value*</tt>s or
2371 <tt>const User*</tt>s respectively.  Upon dereferencing, they return
2372 <tt>const Use*</tt>s. Otherwise the above patterns remain unchanged.</p>
2373
2374 </div>
2375
2376 <!--_______________________________________________________________________-->
2377 <h4>
2378   <a name="iterate_preds">Iterating over predecessors &amp;
2379 successors of blocks</a>
2380 </h4>
2381
2382 <div>
2383
2384 <p>Iterating over the predecessors and successors of a block is quite easy
2385 with the routines defined in <tt>"llvm/Support/CFG.h"</tt>.  Just use code like
2386 this to iterate over all predecessors of BB:</p>
2387
2388 <div class="doc_code">
2389 <pre>
2390 #include "llvm/Support/CFG.h"
2391 BasicBlock *BB = ...;
2392
2393 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
2394   BasicBlock *Pred = *PI;
2395   // <i>...</i>
2396 }
2397 </pre>
2398 </div>
2399
2400 <p>Similarly, to iterate over successors use
2401 succ_iterator/succ_begin/succ_end.</p>
2402
2403 </div>
2404
2405 </div>
2406
2407 <!-- ======================================================================= -->
2408 <h3>
2409   <a name="simplechanges">Making simple changes</a>
2410 </h3>
2411
2412 <div>
2413
2414 <p>There are some primitive transformation operations present in the LLVM
2415 infrastructure that are worth knowing about.  When performing
2416 transformations, it's fairly common to manipulate the contents of basic
2417 blocks. This section describes some of the common methods for doing so
2418 and gives example code.</p>
2419
2420 <!--_______________________________________________________________________-->
2421 <h4>
2422   <a name="schanges_creating">Creating and inserting new
2423   <tt>Instruction</tt>s</a>
2424 </h4>
2425
2426 <div>
2427
2428 <p><i>Instantiating Instructions</i></p>
2429
2430 <p>Creation of <tt>Instruction</tt>s is straight-forward: simply call the
2431 constructor for the kind of instruction to instantiate and provide the necessary
2432 parameters. For example, an <tt>AllocaInst</tt> only <i>requires</i> a
2433 (const-ptr-to) <tt>Type</tt>. Thus:</p>
2434
2435 <div class="doc_code">
2436 <pre>
2437 AllocaInst* ai = new AllocaInst(Type::Int32Ty);
2438 </pre>
2439 </div>
2440
2441 <p>will create an <tt>AllocaInst</tt> instance that represents the allocation of
2442 one integer in the current stack frame, at run time. Each <tt>Instruction</tt>
2443 subclass is likely to have varying default parameters which change the semantics
2444 of the instruction, so refer to the <a
2445 href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of
2446 Instruction</a> that you're interested in instantiating.</p>
2447
2448 <p><i>Naming values</i></p>
2449
2450 <p>It is very useful to name the values of instructions when you're able to, as
2451 this facilitates the debugging of your transformations.  If you end up looking
2452 at generated LLVM machine code, you definitely want to have logical names
2453 associated with the results of instructions!  By supplying a value for the
2454 <tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you
2455 associate a logical name with the result of the instruction's execution at
2456 run time.  For example, say that I'm writing a transformation that dynamically
2457 allocates space for an integer on the stack, and that integer is going to be
2458 used as some kind of index by some other code.  To accomplish this, I place an
2459 <tt>AllocaInst</tt> at the first point in the first <tt>BasicBlock</tt> of some
2460 <tt>Function</tt>, and I'm intending to use it within the same
2461 <tt>Function</tt>. I might do:</p>
2462
2463 <div class="doc_code">
2464 <pre>
2465 AllocaInst* pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");
2466 </pre>
2467 </div>
2468
2469 <p>where <tt>indexLoc</tt> is now the logical name of the instruction's
2470 execution value, which is a pointer to an integer on the run time stack.</p>
2471
2472 <p><i>Inserting instructions</i></p>
2473
2474 <p>There are essentially two ways to insert an <tt>Instruction</tt>
2475 into an existing sequence of instructions that form a <tt>BasicBlock</tt>:</p>
2476
2477 <ul>
2478   <li>Insertion into an explicit instruction list
2479
2480     <p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within that
2481     <tt>BasicBlock</tt>, and a newly-created instruction we wish to insert
2482     before <tt>*pi</tt>, we do the following: </p>
2483
2484 <div class="doc_code">
2485 <pre>
2486 BasicBlock *pb = ...;
2487 Instruction *pi = ...;
2488 Instruction *newInst = new Instruction(...);
2489
2490 pb-&gt;getInstList().insert(pi, newInst); // <i>Inserts newInst before pi in pb</i>
2491 </pre>
2492 </div>
2493
2494     <p>Appending to the end of a <tt>BasicBlock</tt> is so common that
2495     the <tt>Instruction</tt> class and <tt>Instruction</tt>-derived
2496     classes provide constructors which take a pointer to a
2497     <tt>BasicBlock</tt> to be appended to. For example code that
2498     looked like: </p>
2499
2500 <div class="doc_code">
2501 <pre>
2502 BasicBlock *pb = ...;
2503 Instruction *newInst = new Instruction(...);
2504
2505 pb-&gt;getInstList().push_back(newInst); // <i>Appends newInst to pb</i>
2506 </pre>
2507 </div>
2508
2509     <p>becomes: </p>
2510
2511 <div class="doc_code">
2512 <pre>
2513 BasicBlock *pb = ...;
2514 Instruction *newInst = new Instruction(..., pb);
2515 </pre>
2516 </div>
2517
2518     <p>which is much cleaner, especially if you are creating
2519     long instruction streams.</p></li>
2520
2521   <li>Insertion into an implicit instruction list
2522
2523     <p><tt>Instruction</tt> instances that are already in <tt>BasicBlock</tt>s
2524     are implicitly associated with an existing instruction list: the instruction
2525     list of the enclosing basic block. Thus, we could have accomplished the same
2526     thing as the above code without being given a <tt>BasicBlock</tt> by doing:
2527     </p>
2528
2529 <div class="doc_code">
2530 <pre>
2531 Instruction *pi = ...;
2532 Instruction *newInst = new Instruction(...);
2533
2534 pi-&gt;getParent()-&gt;getInstList().insert(pi, newInst);
2535 </pre>
2536 </div>
2537
2538     <p>In fact, this sequence of steps occurs so frequently that the
2539     <tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes provide
2540     constructors which take (as a default parameter) a pointer to an
2541     <tt>Instruction</tt> which the newly-created <tt>Instruction</tt> should
2542     precede.  That is, <tt>Instruction</tt> constructors are capable of
2543     inserting the newly-created instance into the <tt>BasicBlock</tt> of a
2544     provided instruction, immediately before that instruction.  Using an
2545     <tt>Instruction</tt> constructor with a <tt>insertBefore</tt> (default)
2546     parameter, the above code becomes:</p>
2547
2548 <div class="doc_code">
2549 <pre>
2550 Instruction* pi = ...;
2551 Instruction* newInst = new Instruction(..., pi);
2552 </pre>
2553 </div>
2554
2555     <p>which is much cleaner, especially if you're creating a lot of
2556     instructions and adding them to <tt>BasicBlock</tt>s.</p></li>
2557 </ul>
2558
2559 </div>
2560
2561 <!--_______________________________________________________________________-->
2562 <h4>
2563   <a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a>
2564 </h4>
2565
2566 <div>
2567
2568 <p>Deleting an instruction from an existing sequence of instructions that form a
2569 <a href="#BasicBlock"><tt>BasicBlock</tt></a> is very straight-forward: just
2570 call the instruction's eraseFromParent() method.  For example:</p>
2571
2572 <div class="doc_code">
2573 <pre>
2574 <a href="#Instruction">Instruction</a> *I = .. ;
2575 I-&gt;eraseFromParent();
2576 </pre>
2577 </div>
2578
2579 <p>This unlinks the instruction from its containing basic block and deletes
2580 it.  If you'd just like to unlink the instruction from its containing basic
2581 block but not delete it, you can use the <tt>removeFromParent()</tt> method.</p>
2582
2583 </div>
2584
2585 <!--_______________________________________________________________________-->
2586 <h4>
2587   <a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another
2588   <tt>Value</tt></a>
2589 </h4>
2590
2591 <div>
2592
2593 <h5><i>Replacing individual instructions</i></h5>
2594
2595 <p>Including "<a href="/doxygen/BasicBlockUtils_8h-source.html">llvm/Transforms/Utils/BasicBlockUtils.h</a>"
2596 permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt>
2597 and <tt>ReplaceInstWithInst</tt>.</p>
2598
2599 <h5><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h5>
2600
2601 <div>
2602 <ul>
2603   <li><tt>ReplaceInstWithValue</tt>
2604
2605     <p>This function replaces all uses of a given instruction with a value,
2606     and then removes the original instruction. The following example
2607     illustrates the replacement of the result of a particular
2608     <tt>AllocaInst</tt> that allocates memory for a single integer with a null
2609     pointer to an integer.</p>
2610
2611 <div class="doc_code">
2612 <pre>
2613 AllocaInst* instToReplace = ...;
2614 BasicBlock::iterator ii(instToReplace);
2615
2616 ReplaceInstWithValue(instToReplace-&gt;getParent()-&gt;getInstList(), ii,
2617                      Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty)));
2618 </pre></div></li>
2619
2620   <li><tt>ReplaceInstWithInst</tt>
2621
2622     <p>This function replaces a particular instruction with another
2623     instruction, inserting the new instruction into the basic block at the
2624     location where the old instruction was, and replacing any uses of the old
2625     instruction with the new instruction. The following example illustrates
2626     the replacement of one <tt>AllocaInst</tt> with another.</p>
2627
2628 <div class="doc_code">
2629 <pre>
2630 AllocaInst* instToReplace = ...;
2631 BasicBlock::iterator ii(instToReplace);
2632
2633 ReplaceInstWithInst(instToReplace-&gt;getParent()-&gt;getInstList(), ii,
2634                     new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));
2635 </pre></div></li>
2636 </ul>
2637
2638 </div>
2639
2640 <h5><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></h5>
2641
2642 <p>You can use <tt>Value::replaceAllUsesWith</tt> and
2643 <tt>User::replaceUsesOfWith</tt> to change more than one use at a time.  See the
2644 doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a>
2645 and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more
2646 information.</p>
2647
2648 <!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out:
2649 include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with:
2650 ReplaceInstWithValue, ReplaceInstWithInst -->
2651
2652 </div>
2653
2654 <!--_______________________________________________________________________-->
2655 <h4>
2656   <a name="schanges_deletingGV">Deleting <tt>GlobalVariable</tt>s</a>
2657 </h4>
2658
2659 <div>
2660
2661 <p>Deleting a global variable from a module is just as easy as deleting an
2662 Instruction. First, you must have a pointer to the global variable that you wish
2663  to delete.  You use this pointer to erase it from its parent, the module.
2664  For example:</p>
2665
2666 <div class="doc_code">
2667 <pre>
2668 <a href="#GlobalVariable">GlobalVariable</a> *GV = .. ;
2669
2670 GV-&gt;eraseFromParent();
2671 </pre>
2672 </div>
2673
2674 </div>
2675
2676 </div>
2677
2678 <!-- ======================================================================= -->
2679 <h3>
2680   <a name="create_types">How to Create Types</a>
2681 </h3>
2682
2683 <div>
2684
2685 <p>In generating IR, you may need some complex types.  If you know these types
2686 statically, you can use <tt>TypeBuilder&lt;...&gt;::get()</tt>, defined
2687 in <tt>llvm/Support/TypeBuilder.h</tt>, to retrieve them.  <tt>TypeBuilder</tt>
2688 has two forms depending on whether you're building types for cross-compilation
2689 or native library use.  <tt>TypeBuilder&lt;T, true&gt;</tt> requires
2690 that <tt>T</tt> be independent of the host environment, meaning that it's built
2691 out of types from
2692 the <a href="/doxygen/namespacellvm_1_1types.html"><tt>llvm::types</tt></a>
2693 namespace and pointers, functions, arrays, etc. built of
2694 those.  <tt>TypeBuilder&lt;T, false&gt;</tt> additionally allows native C types
2695 whose size may depend on the host compiler.  For example,</p>
2696
2697 <div class="doc_code">
2698 <pre>
2699 FunctionType *ft = TypeBuilder&lt;types::i&lt;8&gt;(types::i&lt;32&gt;*), true&gt;::get();
2700 </pre>
2701 </div>
2702
2703 <p>is easier to read and write than the equivalent</p>
2704
2705 <div class="doc_code">
2706 <pre>
2707 std::vector&lt;const Type*&gt; params;
2708 params.push_back(PointerType::getUnqual(Type::Int32Ty));
2709 FunctionType *ft = FunctionType::get(Type::Int8Ty, params, false);
2710 </pre>
2711 </div>
2712
2713 <p>See the <a href="/doxygen/TypeBuilder_8h-source.html#l00001">class
2714 comment</a> for more details.</p>
2715
2716 </div>
2717
2718 </div>
2719
2720 <!-- *********************************************************************** -->
2721 <h2>
2722   <a name="threading">Threads and LLVM</a>
2723 </h2>
2724 <!-- *********************************************************************** -->
2725
2726 <div>
2727 <p>
2728 This section describes the interaction of the LLVM APIs with multithreading,
2729 both on the part of client applications, and in the JIT, in the hosted
2730 application.
2731 </p>
2732
2733 <p>
2734 Note that LLVM's support for multithreading is still relatively young.  Up
2735 through version 2.5, the execution of threaded hosted applications was
2736 supported, but not threaded client access to the APIs.  While this use case is
2737 now supported, clients <em>must</em> adhere to the guidelines specified below to
2738 ensure proper operation in multithreaded mode.
2739 </p>
2740
2741 <p>
2742 Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic
2743 intrinsics in order to support threaded operation.  If you need a
2744 multhreading-capable LLVM on a platform without a suitably modern system
2745 compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and
2746 using the resultant compiler to build a copy of LLVM with multithreading
2747 support.
2748 </p>
2749
2750 <!-- ======================================================================= -->
2751 <h3>
2752   <a name="startmultithreaded">Entering and Exiting Multithreaded Mode</a>
2753 </h3>
2754
2755 <div>
2756
2757 <p>
2758 In order to properly protect its internal data structures while avoiding
2759 excessive locking overhead in the single-threaded case, the LLVM must intialize
2760 certain data structures necessary to provide guards around its internals.  To do
2761 so, the client program must invoke <tt>llvm_start_multithreaded()</tt> before
2762 making any concurrent LLVM API calls.  To subsequently tear down these
2763 structures, use the <tt>llvm_stop_multithreaded()</tt> call.  You can also use
2764 the <tt>llvm_is_multithreaded()</tt> call to check the status of multithreaded
2765 mode.
2766 </p>
2767
2768 <p>
2769 Note that both of these calls must be made <em>in isolation</em>.  That is to
2770 say that no other LLVM API calls may be executing at any time during the
2771 execution of <tt>llvm_start_multithreaded()</tt> or <tt>llvm_stop_multithreaded
2772 </tt>.  It's is the client's responsibility to enforce this isolation.
2773 </p>
2774
2775 <p>
2776 The return value of <tt>llvm_start_multithreaded()</tt> indicates the success or
2777 failure of the initialization.  Failure typically indicates that your copy of
2778 LLVM was built without multithreading support, typically because GCC atomic
2779 intrinsics were not found in your system compiler.  In this case, the LLVM API
2780 will not be safe for concurrent calls.  However, it <em>will</em> be safe for
2781 hosting threaded applications in the JIT, though <a href="#jitthreading">care
2782 must be taken</a> to ensure that side exits and the like do not accidentally
2783 result in concurrent LLVM API calls.
2784 </p>
2785 </div>
2786
2787 <!-- ======================================================================= -->
2788 <h3>
2789   <a name="shutdown">Ending Execution with <tt>llvm_shutdown()</tt></a>
2790 </h3>
2791
2792 <div>
2793 <p>
2794 When you are done using the LLVM APIs, you should call <tt>llvm_shutdown()</tt>
2795 to deallocate memory used for internal structures.  This will also invoke
2796 <tt>llvm_stop_multithreaded()</tt> if LLVM is operating in multithreaded mode.
2797 As such, <tt>llvm_shutdown()</tt> requires the same isolation guarantees as
2798 <tt>llvm_stop_multithreaded()</tt>.
2799 </p>
2800
2801 <p>
2802 Note that, if you use scope-based shutdown, you can use the
2803 <tt>llvm_shutdown_obj</tt> class, which calls <tt>llvm_shutdown()</tt> in its
2804 destructor.
2805 </div>
2806
2807 <!-- ======================================================================= -->
2808 <h3>
2809   <a name="managedstatic">Lazy Initialization with <tt>ManagedStatic</tt></a>
2810 </h3>
2811
2812 <div>
2813 <p>
2814 <tt>ManagedStatic</tt> is a utility class in LLVM used to implement static
2815 initialization of static resources, such as the global type tables.  Before the
2816 invocation of <tt>llvm_shutdown()</tt>, it implements a simple lazy
2817 initialization scheme.  Once <tt>llvm_start_multithreaded()</tt> returns,
2818 however, it uses double-checked locking to implement thread-safe lazy
2819 initialization.
2820 </p>
2821
2822 <p>
2823 Note that, because no other threads are allowed to issue LLVM API calls before
2824 <tt>llvm_start_multithreaded()</tt> returns, it is possible to have
2825 <tt>ManagedStatic</tt>s of <tt>llvm::sys::Mutex</tt>s.
2826 </p>
2827
2828 <p>
2829 The <tt>llvm_acquire_global_lock()</tt> and <tt>llvm_release_global_lock</tt>
2830 APIs provide access to the global lock used to implement the double-checked
2831 locking for lazy initialization.  These should only be used internally to LLVM,
2832 and only if you know what you're doing!
2833 </p>
2834 </div>
2835
2836 <!-- ======================================================================= -->
2837 <h3>
2838   <a name="llvmcontext">Achieving Isolation with <tt>LLVMContext</tt></a>
2839 </h3>
2840
2841 <div>
2842 <p>
2843 <tt>LLVMContext</tt> is an opaque class in the LLVM API which clients can use
2844 to operate multiple, isolated instances of LLVM concurrently within the same
2845 address space.  For instance, in a hypothetical compile-server, the compilation
2846 of an individual translation unit is conceptually independent from all the
2847 others, and it would be desirable to be able to compile incoming translation
2848 units concurrently on independent server threads.  Fortunately,
2849 <tt>LLVMContext</tt> exists to enable just this kind of scenario!
2850 </p>
2851
2852 <p>
2853 Conceptually, <tt>LLVMContext</tt> provides isolation.  Every LLVM entity
2854 (<tt>Module</tt>s, <tt>Value</tt>s, <tt>Type</tt>s, <tt>Constant</tt>s, etc.)
2855 in LLVM's in-memory IR belongs to an <tt>LLVMContext</tt>.  Entities in
2856 different contexts <em>cannot</em> interact with each other: <tt>Module</tt>s in
2857 different contexts cannot be linked together, <tt>Function</tt>s cannot be added
2858 to <tt>Module</tt>s in different contexts, etc.  What this means is that is is
2859 safe to compile on multiple threads simultaneously, as long as no two threads
2860 operate on entities within the same context.
2861 </p>
2862
2863 <p>
2864 In practice, very few places in the API require the explicit specification of a
2865 <tt>LLVMContext</tt>, other than the <tt>Type</tt> creation/lookup APIs.
2866 Because every <tt>Type</tt> carries a reference to its owning context, most
2867 other entities can determine what context they belong to by looking at their
2868 own <tt>Type</tt>.  If you are adding new entities to LLVM IR, please try to
2869 maintain this interface design.
2870 </p>
2871
2872 <p>
2873 For clients that do <em>not</em> require the benefits of isolation, LLVM
2874 provides a convenience API <tt>getGlobalContext()</tt>.  This returns a global,
2875 lazily initialized <tt>LLVMContext</tt> that may be used in situations where
2876 isolation is not a concern.
2877 </p>
2878 </div>
2879
2880 <!-- ======================================================================= -->
2881 <h3>
2882   <a name="jitthreading">Threads and the JIT</a>
2883 </h3>
2884
2885 <div>
2886 <p>
2887 LLVM's "eager" JIT compiler is safe to use in threaded programs.  Multiple
2888 threads can call <tt>ExecutionEngine::getPointerToFunction()</tt> or
2889 <tt>ExecutionEngine::runFunction()</tt> concurrently, and multiple threads can
2890 run code output by the JIT concurrently.  The user must still ensure that only
2891 one thread accesses IR in a given <tt>LLVMContext</tt> while another thread
2892 might be modifying it.  One way to do that is to always hold the JIT lock while
2893 accessing IR outside the JIT (the JIT <em>modifies</em> the IR by adding
2894 <tt>CallbackVH</tt>s).  Another way is to only
2895 call <tt>getPointerToFunction()</tt> from the <tt>LLVMContext</tt>'s thread.
2896 </p>
2897
2898 <p>When the JIT is configured to compile lazily (using
2899 <tt>ExecutionEngine::DisableLazyCompilation(false)</tt>), there is currently a
2900 <a href="http://llvm.org/bugs/show_bug.cgi?id=5184">race condition</a> in
2901 updating call sites after a function is lazily-jitted.  It's still possible to
2902 use the lazy JIT in a threaded program if you ensure that only one thread at a
2903 time can call any particular lazy stub and that the JIT lock guards any IR
2904 access, but we suggest using only the eager JIT in threaded programs.
2905 </p>
2906 </div>
2907
2908 </div>
2909
2910 <!-- *********************************************************************** -->
2911 <h2>
2912   <a name="advanced">Advanced Topics</a>
2913 </h2>
2914 <!-- *********************************************************************** -->
2915
2916 <div>
2917 <p>
2918 This section describes some of the advanced or obscure API's that most clients
2919 do not need to be aware of.  These API's tend manage the inner workings of the
2920 LLVM system, and only need to be accessed in unusual circumstances.
2921 </p>
2922
2923
2924 <!-- ======================================================================= -->
2925 <h3>
2926   <a name="SymbolTable">The <tt>ValueSymbolTable</tt> class</a>
2927 </h3>
2928
2929 <div>
2930 <p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html">
2931 ValueSymbolTable</a></tt> class provides a symbol table that the <a
2932 href="#Function"><tt>Function</tt></a> and <a href="#Module">
2933 <tt>Module</tt></a> classes use for naming value definitions. The symbol table
2934 can provide a name for any <a href="#Value"><tt>Value</tt></a>.
2935 </p>
2936
2937 <p>Note that the <tt>SymbolTable</tt> class should not be directly accessed
2938 by most clients.  It should only be used when iteration over the symbol table
2939 names themselves are required, which is very special purpose.  Note that not
2940 all LLVM
2941 <tt><a href="#Value">Value</a></tt>s have names, and those without names (i.e. they have
2942 an empty name) do not exist in the symbol table.
2943 </p>
2944
2945 <p>Symbol tables support iteration over the values in the symbol
2946 table with <tt>begin/end/iterator</tt> and supports querying to see if a
2947 specific name is in the symbol table (with <tt>lookup</tt>).  The
2948 <tt>ValueSymbolTable</tt> class exposes no public mutator methods, instead,
2949 simply call <tt>setName</tt> on a value, which will autoinsert it into the
2950 appropriate symbol table.</p>
2951
2952 </div>
2953
2954
2955
2956 <!-- ======================================================================= -->
2957 <h3>
2958   <a name="UserLayout">The <tt>User</tt> and owned <tt>Use</tt> classes' memory layout</a>
2959 </h3>
2960
2961 <div>
2962 <p>The <tt><a href="http://llvm.org/doxygen/classllvm_1_1User.html">
2963 User</a></tt> class provides a basis for expressing the ownership of <tt>User</tt>
2964 towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html">
2965 Value</a></tt>s. The <tt><a href="http://llvm.org/doxygen/classllvm_1_1Use.html">
2966 Use</a></tt> helper class is employed to do the bookkeeping and to facilitate <i>O(1)</i>
2967 addition and removal.</p>
2968
2969 <!-- ______________________________________________________________________ -->
2970 <h4>
2971   <a name="Use2User">
2972     Interaction and relationship between <tt>User</tt> and <tt>Use</tt> objects
2973   </a>
2974 </h4>
2975
2976 <div>
2977 <p>
2978 A subclass of <tt>User</tt> can choose between incorporating its <tt>Use</tt> objects
2979 or refer to them out-of-line by means of a pointer. A mixed variant
2980 (some <tt>Use</tt>s inline others hung off) is impractical and breaks the invariant
2981 that the <tt>Use</tt> objects belonging to the same <tt>User</tt> form a contiguous array.
2982 </p>
2983
2984 <p>
2985 We have 2 different layouts in the <tt>User</tt> (sub)classes:
2986 <ul>
2987 <li><p>Layout a)
2988 The <tt>Use</tt> object(s) are inside (resp. at fixed offset) of the <tt>User</tt>
2989 object and there are a fixed number of them.</p>
2990
2991 <li><p>Layout b)
2992 The <tt>Use</tt> object(s) are referenced by a pointer to an
2993 array from the <tt>User</tt> object and there may be a variable
2994 number of them.</p>
2995 </ul>
2996 <p>
2997 As of v2.4 each layout still possesses a direct pointer to the
2998 start of the array of <tt>Use</tt>s. Though not mandatory for layout a),
2999 we stick to this redundancy for the sake of simplicity.
3000 The <tt>User</tt> object also stores the number of <tt>Use</tt> objects it
3001 has. (Theoretically this information can also be calculated
3002 given the scheme presented below.)</p>
3003 <p>
3004 Special forms of allocation operators (<tt>operator new</tt>)
3005 enforce the following memory layouts:</p>
3006
3007 <ul>
3008 <li><p>Layout a) is modelled by prepending the <tt>User</tt> object by the <tt>Use[]</tt> array.</p>
3009
3010 <pre>
3011 ...---.---.---.---.-------...
3012   | P | P | P | P | User
3013 '''---'---'---'---'-------'''
3014 </pre>
3015
3016 <li><p>Layout b) is modelled by pointing at the <tt>Use[]</tt> array.</p>
3017 <pre>
3018 .-------...
3019 | User
3020 '-------'''
3021     |
3022     v
3023     .---.---.---.---...
3024     | P | P | P | P |
3025     '---'---'---'---'''
3026 </pre>
3027 </ul>
3028 <i>(In the above figures '<tt>P</tt>' stands for the <tt>Use**</tt> that
3029     is stored in each <tt>Use</tt> object in the member <tt>Use::Prev</tt>)</i>
3030
3031 </div>
3032
3033 <!-- ______________________________________________________________________ -->
3034 <h4>
3035   <a name="Waymarking">The waymarking algorithm</a>
3036 </h4>
3037
3038 <div>
3039 <p>
3040 Since the <tt>Use</tt> objects are deprived of the direct (back)pointer to
3041 their <tt>User</tt> objects, there must be a fast and exact method to
3042 recover it. This is accomplished by the following scheme:</p>
3043
3044 A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> allows to find the
3045 start of the <tt>User</tt> object:
3046 <ul>
3047 <li><tt>00</tt> &mdash;&gt; binary digit 0</li>
3048 <li><tt>01</tt> &mdash;&gt; binary digit 1</li>
3049 <li><tt>10</tt> &mdash;&gt; stop and calculate (<tt>s</tt>)</li>
3050 <li><tt>11</tt> &mdash;&gt; full stop (<tt>S</tt>)</li>
3051 </ul>
3052 <p>
3053 Given a <tt>Use*</tt>, all we have to do is to walk till we get
3054 a stop and we either have a <tt>User</tt> immediately behind or
3055 we have to walk to the next stop picking up digits
3056 and calculating the offset:</p>
3057 <pre>
3058 .---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.---.----------------
3059 | 1 | s | 1 | 0 | 1 | 0 | s | 1 | 1 | 0 | s | 1 | 1 | s | 1 | S | User (or User*)
3060 '---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'---'----------------
3061     |+15                |+10            |+6         |+3     |+1
3062     |                   |               |           |       |__>
3063     |                   |               |           |__________>
3064     |                   |               |______________________>
3065     |                   |______________________________________>
3066     |__________________________________________________________>
3067 </pre>
3068 <p>
3069 Only the significant number of bits need to be stored between the
3070 stops, so that the <i>worst case is 20 memory accesses</i> when there are
3071 1000 <tt>Use</tt> objects associated with a <tt>User</tt>.</p>
3072
3073 </div>
3074
3075 <!-- ______________________________________________________________________ -->
3076 <h4>
3077   <a name="ReferenceImpl">Reference implementation</a>
3078 </h4>
3079
3080 <div>
3081 <p>
3082 The following literate Haskell fragment demonstrates the concept:</p>
3083
3084 <div class="doc_code">
3085 <pre>
3086 > import Test.QuickCheck
3087 >
3088 > digits :: Int -> [Char] -> [Char]
3089 > digits 0 acc = '0' : acc
3090 > digits 1 acc = '1' : acc
3091 > digits n acc = digits (n `div` 2) $ digits (n `mod` 2) acc
3092 >
3093 > dist :: Int -> [Char] -> [Char]
3094 > dist 0 [] = ['S']
3095 > dist 0 acc = acc
3096 > dist 1 acc = let r = dist 0 acc in 's' : digits (length r) r
3097 > dist n acc = dist (n - 1) $ dist 1 acc
3098 >
3099 > takeLast n ss = reverse $ take n $ reverse ss
3100 >
3101 > test = takeLast 40 $ dist 20 []
3102 >
3103 </pre>
3104 </div>
3105 <p>
3106 Printing &lt;test&gt; gives: <tt>"1s100000s11010s10100s1111s1010s110s11s1S"</tt></p>
3107 <p>
3108 The reverse algorithm computes the length of the string just by examining
3109 a certain prefix:</p>
3110
3111 <div class="doc_code">
3112 <pre>
3113 > pref :: [Char] -> Int
3114 > pref "S" = 1
3115 > pref ('s':'1':rest) = decode 2 1 rest
3116 > pref (_:rest) = 1 + pref rest
3117 >
3118 > decode walk acc ('0':rest) = decode (walk + 1) (acc * 2) rest
3119 > decode walk acc ('1':rest) = decode (walk + 1) (acc * 2 + 1) rest
3120 > decode walk acc _ = walk + acc
3121 >
3122 </pre>
3123 </div>
3124 <p>
3125 Now, as expected, printing &lt;pref test&gt; gives <tt>40</tt>.</p>
3126 <p>
3127 We can <i>quickCheck</i> this with following property:</p>
3128
3129 <div class="doc_code">
3130 <pre>
3131 > testcase = dist 2000 []
3132 > testcaseLength = length testcase
3133 >
3134 > identityProp n = n > 0 && n <= testcaseLength ==> length arr == pref arr
3135 >     where arr = takeLast n testcase
3136 >
3137 </pre>
3138 </div>
3139 <p>
3140 As expected &lt;quickCheck identityProp&gt; gives:</p>
3141
3142 <pre>
3143 *Main> quickCheck identityProp
3144 OK, passed 100 tests.
3145 </pre>
3146 <p>
3147 Let's be a bit more exhaustive:</p>
3148
3149 <div class="doc_code">
3150 <pre>
3151 >
3152 > deepCheck p = check (defaultConfig { configMaxTest = 500 }) p
3153 >
3154 </pre>
3155 </div>
3156 <p>
3157 And here is the result of &lt;deepCheck identityProp&gt;:</p>
3158
3159 <pre>
3160 *Main> deepCheck identityProp
3161 OK, passed 500 tests.
3162 </pre>
3163
3164 </div>
3165
3166 <!-- ______________________________________________________________________ -->
3167 <h4>
3168   <a name="Tagging">Tagging considerations</a>
3169 </h4>
3170
3171 <div>
3172
3173 <p>
3174 To maintain the invariant that the 2 LSBits of each <tt>Use**</tt> in <tt>Use</tt>
3175 never change after being set up, setters of <tt>Use::Prev</tt> must re-tag the
3176 new <tt>Use**</tt> on every modification. Accordingly getters must strip the
3177 tag bits.</p>
3178 <p>
3179 For layout b) instead of the <tt>User</tt> we find a pointer (<tt>User*</tt> with LSBit set).
3180 Following this pointer brings us to the <tt>User</tt>. A portable trick ensures
3181 that the first bytes of <tt>User</tt> (if interpreted as a pointer) never has
3182 the LSBit set. (Portability is relying on the fact that all known compilers place the
3183 <tt>vptr</tt> in the first word of the instances.)</p>
3184
3185 </div>
3186
3187 </div>
3188
3189 </div>
3190
3191 <!-- *********************************************************************** -->
3192 <h2>
3193   <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a>
3194 </h2>
3195 <!-- *********************************************************************** -->
3196
3197 <div>
3198 <p><tt>#include "<a href="/doxygen/Type_8h-source.html">llvm/Type.h</a>"</tt>
3199 <br>doxygen info: <a href="/doxygen/classllvm_1_1Type.html">Type Class</a></p>
3200
3201 <p>The Core LLVM classes are the primary means of representing the program
3202 being inspected or transformed.  The core LLVM classes are defined in
3203 header files in the <tt>include/llvm/</tt> directory, and implemented in
3204 the <tt>lib/VMCore</tt> directory.</p>
3205
3206 <!-- ======================================================================= -->
3207 <h3>
3208   <a name="Type">The <tt>Type</tt> class and Derived Types</a>
3209 </h3>
3210
3211 <div>
3212
3213   <p><tt>Type</tt> is a superclass of all type classes. Every <tt>Value</tt> has
3214   a <tt>Type</tt>. <tt>Type</tt> cannot be instantiated directly but only
3215   through its subclasses. Certain primitive types (<tt>VoidType</tt>,
3216   <tt>LabelType</tt>, <tt>FloatType</tt> and <tt>DoubleType</tt>) have hidden
3217   subclasses. They are hidden because they offer no useful functionality beyond
3218   what the <tt>Type</tt> class offers except to distinguish themselves from
3219   other subclasses of <tt>Type</tt>.</p>
3220   <p>All other types are subclasses of <tt>DerivedType</tt>.  Types can be
3221   named, but this is not a requirement. There exists exactly
3222   one instance of a given shape at any one time.  This allows type equality to
3223   be performed with address equality of the Type Instance. That is, given two
3224   <tt>Type*</tt> values, the types are identical if the pointers are identical.
3225   </p>
3226
3227 <!-- _______________________________________________________________________ -->
3228 <h4>
3229   <a name="m_Type">Important Public Methods</a>
3230 </h4>
3231
3232 <div>
3233
3234 <ul>
3235   <li><tt>bool isIntegerTy() const</tt>: Returns true for any integer type.</li>
3236
3237   <li><tt>bool isFloatingPointTy()</tt>: Return true if this is one of the five
3238   floating point types.</li>
3239
3240   <li><tt>bool isSized()</tt>: Return true if the type has known size. Things
3241   that don't have a size are abstract types, labels and void.</li>
3242
3243 </ul>
3244 </div>
3245
3246 <!-- _______________________________________________________________________ -->
3247 <h4>
3248   <a name="derivedtypes">Important Derived Types</a>
3249 </h4>
3250 <div>
3251 <dl>
3252   <dt><tt>IntegerType</tt></dt>
3253   <dd>Subclass of DerivedType that represents integer types of any bit width.
3254   Any bit width between <tt>IntegerType::MIN_INT_BITS</tt> (1) and
3255   <tt>IntegerType::MAX_INT_BITS</tt> (~8 million) can be represented.
3256   <ul>
3257     <li><tt>static const IntegerType* get(unsigned NumBits)</tt>: get an integer
3258     type of a specific bit width.</li>
3259     <li><tt>unsigned getBitWidth() const</tt>: Get the bit width of an integer
3260     type.</li>
3261   </ul>
3262   </dd>
3263   <dt><tt>SequentialType</tt></dt>
3264   <dd>This is subclassed by ArrayType, PointerType and VectorType.
3265     <ul>
3266       <li><tt>const Type * getElementType() const</tt>: Returns the type of each
3267       of the elements in the sequential type. </li>
3268     </ul>
3269   </dd>
3270   <dt><tt>ArrayType</tt></dt>
3271   <dd>This is a subclass of SequentialType and defines the interface for array
3272   types.
3273     <ul>
3274       <li><tt>unsigned getNumElements() const</tt>: Returns the number of
3275       elements in the array. </li>
3276     </ul>
3277   </dd>
3278   <dt><tt>PointerType</tt></dt>
3279   <dd>Subclass of SequentialType for pointer types.</dd>
3280   <dt><tt>VectorType</tt></dt>
3281   <dd>Subclass of SequentialType for vector types. A
3282   vector type is similar to an ArrayType but is distinguished because it is
3283   a first class type whereas ArrayType is not. Vector types are used for
3284   vector operations and are usually small vectors of of an integer or floating
3285   point type.</dd>
3286   <dt><tt>StructType</tt></dt>
3287   <dd>Subclass of DerivedTypes for struct types.</dd>
3288   <dt><tt><a name="FunctionType">FunctionType</a></tt></dt>
3289   <dd>Subclass of DerivedTypes for function types.
3290     <ul>
3291       <li><tt>bool isVarArg() const</tt>: Returns true if it's a vararg
3292       function</li>
3293       <li><tt> const Type * getReturnType() const</tt>: Returns the
3294       return type of the function.</li>
3295       <li><tt>const Type * getParamType (unsigned i)</tt>: Returns
3296       the type of the ith parameter.</li>
3297       <li><tt> const unsigned getNumParams() const</tt>: Returns the
3298       number of formal parameters.</li>
3299     </ul>
3300   </dd>
3301 </dl>
3302 </div>
3303
3304 </div>
3305
3306 <!-- ======================================================================= -->
3307 <h3>
3308   <a name="Module">The <tt>Module</tt> class</a>
3309 </h3>
3310
3311 <div>
3312
3313 <p><tt>#include "<a
3314 href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info:
3315 <a href="/doxygen/classllvm_1_1Module.html">Module Class</a></p>
3316
3317 <p>The <tt>Module</tt> class represents the top level structure present in LLVM
3318 programs.  An LLVM module is effectively either a translation unit of the
3319 original program or a combination of several translation units merged by the
3320 linker.  The <tt>Module</tt> class keeps track of a list of <a
3321 href="#Function"><tt>Function</tt></a>s, a list of <a
3322 href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a
3323 href="#SymbolTable"><tt>SymbolTable</tt></a>.  Additionally, it contains a few
3324 helpful member functions that try to make common operations easy.</p>
3325
3326 <!-- _______________________________________________________________________ -->
3327 <h4>
3328   <a name="m_Module">Important Public Members of the <tt>Module</tt> class</a>
3329 </h4>
3330
3331 <div>
3332
3333 <ul>
3334   <li><tt>Module::Module(std::string name = "")</tt>
3335
3336   <p>Constructing a <a href="#Module">Module</a> is easy. You can optionally
3337 provide a name for it (probably based on the name of the translation unit).</p>
3338   </li>
3339
3340   <li><tt>Module::iterator</tt> - Typedef for function list iterator<br>
3341     <tt>Module::const_iterator</tt> - Typedef for const_iterator.<br>
3342
3343     <tt>begin()</tt>, <tt>end()</tt>
3344     <tt>size()</tt>, <tt>empty()</tt>
3345
3346     <p>These are forwarding methods that make it easy to access the contents of
3347     a <tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a>
3348     list.</p></li>
3349
3350   <li><tt>Module::FunctionListType &amp;getFunctionList()</tt>
3351
3352     <p> Returns the list of <a href="#Function"><tt>Function</tt></a>s.  This is
3353     necessary to use when you need to update the list or perform a complex
3354     action that doesn't have a forwarding method.</p>
3355
3356     <p><!--  Global Variable --></p></li>
3357 </ul>
3358
3359 <hr>
3360
3361 <ul>
3362   <li><tt>Module::global_iterator</tt> - Typedef for global variable list iterator<br>
3363
3364     <tt>Module::const_global_iterator</tt> - Typedef for const_iterator.<br>
3365
3366     <tt>global_begin()</tt>, <tt>global_end()</tt>
3367     <tt>global_size()</tt>, <tt>global_empty()</tt>
3368
3369     <p> These are forwarding methods that make it easy to access the contents of
3370     a <tt>Module</tt> object's <a
3371     href="#GlobalVariable"><tt>GlobalVariable</tt></a> list.</p></li>
3372
3373   <li><tt>Module::GlobalListType &amp;getGlobalList()</tt>
3374
3375     <p>Returns the list of <a
3376     href="#GlobalVariable"><tt>GlobalVariable</tt></a>s.  This is necessary to
3377     use when you need to update the list or perform a complex action that
3378     doesn't have a forwarding method.</p>
3379
3380     <p><!--  Symbol table stuff --> </p></li>
3381 </ul>
3382
3383 <hr>
3384
3385 <ul>
3386   <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
3387
3388     <p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
3389     for this <tt>Module</tt>.</p>
3390
3391     <p><!--  Convenience methods --></p></li>
3392 </ul>
3393
3394 <hr>
3395
3396 <ul>
3397
3398   <li><tt><a href="#Function">Function</a> *getFunction(StringRef Name) const
3399     </tt>
3400
3401     <p>Look up the specified function in the <tt>Module</tt> <a
3402     href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return
3403     <tt>null</tt>.</p></li>
3404
3405   <li><tt><a href="#Function">Function</a> *getOrInsertFunction(const
3406   std::string &amp;Name, const <a href="#FunctionType">FunctionType</a> *T)</tt>
3407
3408     <p>Look up the specified function in the <tt>Module</tt> <a
3409     href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an
3410     external declaration for the function and return it.</p></li>
3411
3412   <li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt>
3413
3414     <p>If there is at least one entry in the <a
3415     href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a
3416     href="#Type"><tt>Type</tt></a>, return it.  Otherwise return the empty
3417     string.</p></li>
3418
3419   <li><tt>bool addTypeName(const std::string &amp;Name, const <a
3420   href="#Type">Type</a> *Ty)</tt>
3421
3422     <p>Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
3423     mapping <tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this
3424     name, true is returned and the <a
3425     href="#SymbolTable"><tt>SymbolTable</tt></a> is not modified.</p></li>
3426 </ul>
3427
3428 </div>
3429
3430 </div>
3431
3432 <!-- ======================================================================= -->
3433 <h3>
3434   <a name="Value">The <tt>Value</tt> class</a>
3435 </h3>
3436
3437 <div>
3438
3439 <p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt>
3440 <br>
3441 doxygen info: <a href="/doxygen/classllvm_1_1Value.html">Value Class</a></p>
3442
3443 <p>The <tt>Value</tt> class is the most important class in the LLVM Source
3444 base.  It represents a typed value that may be used (among other things) as an
3445 operand to an instruction.  There are many different types of <tt>Value</tt>s,
3446 such as <a href="#Constant"><tt>Constant</tt></a>s,<a
3447 href="#Argument"><tt>Argument</tt></a>s. Even <a
3448 href="#Instruction"><tt>Instruction</tt></a>s and <a
3449 href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.</p>
3450
3451 <p>A particular <tt>Value</tt> may be used many times in the LLVM representation
3452 for a program.  For example, an incoming argument to a function (represented
3453 with an instance of the <a href="#Argument">Argument</a> class) is "used" by
3454 every instruction in the function that references the argument.  To keep track
3455 of this relationship, the <tt>Value</tt> class keeps a list of all of the <a
3456 href="#User"><tt>User</tt></a>s that is using it (the <a
3457 href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM
3458 graph that can refer to <tt>Value</tt>s).  This use list is how LLVM represents
3459 def-use information in the program, and is accessible through the <tt>use_</tt>*
3460 methods, shown below.</p>
3461
3462 <p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed,
3463 and this <a href="#Type">Type</a> is available through the <tt>getType()</tt>
3464 method. In addition, all LLVM values can be named.  The "name" of the
3465 <tt>Value</tt> is a symbolic string printed in the LLVM code:</p>
3466
3467 <div class="doc_code">
3468 <pre>
3469 %<b>foo</b> = add i32 1, 2
3470 </pre>
3471 </div>
3472
3473 <p><a name="nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b>
3474 that the name of any value may be missing (an empty string), so names should
3475 <b>ONLY</b> be used for debugging (making the source code easier to read,
3476 debugging printouts), they should not be used to keep track of values or map
3477 between them.  For this purpose, use a <tt>std::map</tt> of pointers to the
3478 <tt>Value</tt> itself instead.</p>
3479
3480 <p>One important aspect of LLVM is that there is no distinction between an SSA
3481 variable and the operation that produces it.  Because of this, any reference to
3482 the value produced by an instruction (or the value available as an incoming
3483 argument, for example) is represented as a direct pointer to the instance of
3484 the class that
3485 represents this value.  Although this may take some getting used to, it
3486 simplifies the representation and makes it easier to manipulate.</p>
3487
3488 <!-- _______________________________________________________________________ -->
3489 <h4>
3490   <a name="m_Value">Important Public Members of the <tt>Value</tt> class</a>
3491 </h4>
3492
3493 <div>
3494
3495 <ul>
3496   <li><tt>Value::use_iterator</tt> - Typedef for iterator over the
3497 use-list<br>
3498     <tt>Value::const_use_iterator</tt> - Typedef for const_iterator over
3499 the use-list<br>
3500     <tt>unsigned use_size()</tt> - Returns the number of users of the
3501 value.<br>
3502     <tt>bool use_empty()</tt> - Returns true if there are no users.<br>
3503     <tt>use_iterator use_begin()</tt> - Get an iterator to the start of
3504 the use-list.<br>
3505     <tt>use_iterator use_end()</tt> - Get an iterator to the end of the
3506 use-list.<br>
3507     <tt><a href="#User">User</a> *use_back()</tt> - Returns the last
3508 element in the list.
3509     <p> These methods are the interface to access the def-use
3510 information in LLVM.  As with all other iterators in LLVM, the naming
3511 conventions follow the conventions defined by the <a href="#stl">STL</a>.</p>
3512   </li>
3513   <li><tt><a href="#Type">Type</a> *getType() const</tt>
3514     <p>This method returns the Type of the Value.</p>
3515   </li>
3516   <li><tt>bool hasName() const</tt><br>
3517     <tt>std::string getName() const</tt><br>
3518     <tt>void setName(const std::string &amp;Name)</tt>
3519     <p> This family of methods is used to access and assign a name to a <tt>Value</tt>,
3520 be aware of the <a href="#nameWarning">precaution above</a>.</p>
3521   </li>
3522   <li><tt>void replaceAllUsesWith(Value *V)</tt>
3523
3524     <p>This method traverses the use list of a <tt>Value</tt> changing all <a
3525     href="#User"><tt>User</tt>s</a> of the current value to refer to
3526     "<tt>V</tt>" instead.  For example, if you detect that an instruction always
3527     produces a constant value (for example through constant folding), you can
3528     replace all uses of the instruction with the constant like this:</p>
3529
3530 <div class="doc_code">
3531 <pre>
3532 Inst-&gt;replaceAllUsesWith(ConstVal);
3533 </pre>
3534 </div>
3535
3536 </ul>
3537
3538 </div>
3539
3540 </div>
3541
3542 <!-- ======================================================================= -->
3543 <h3>
3544   <a name="User">The <tt>User</tt> class</a>
3545 </h3>
3546
3547 <div>
3548
3549 <p>
3550 <tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br>
3551 doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br>
3552 Superclass: <a href="#Value"><tt>Value</tt></a></p>
3553
3554 <p>The <tt>User</tt> class is the common base class of all LLVM nodes that may
3555 refer to <a href="#Value"><tt>Value</tt></a>s.  It exposes a list of "Operands"
3556 that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is
3557 referring to.  The <tt>User</tt> class itself is a subclass of
3558 <tt>Value</tt>.</p>
3559
3560 <p>The operands of a <tt>User</tt> point directly to the LLVM <a
3561 href="#Value"><tt>Value</tt></a> that it refers to.  Because LLVM uses Static
3562 Single Assignment (SSA) form, there can only be one definition referred to,
3563 allowing this direct connection.  This connection provides the use-def
3564 information in LLVM.</p>
3565
3566 <!-- _______________________________________________________________________ -->
3567 <h4>
3568   <a name="m_User">Important Public Members of the <tt>User</tt> class</a>
3569 </h4>
3570
3571 <div>
3572
3573 <p>The <tt>User</tt> class exposes the operand list in two ways: through
3574 an index access interface and through an iterator based interface.</p>
3575
3576 <ul>
3577   <li><tt>Value *getOperand(unsigned i)</tt><br>
3578     <tt>unsigned getNumOperands()</tt>
3579     <p> These two methods expose the operands of the <tt>User</tt> in a
3580 convenient form for direct access.</p></li>
3581
3582   <li><tt>User::op_iterator</tt> - Typedef for iterator over the operand
3583 list<br>
3584     <tt>op_iterator op_begin()</tt> - Get an iterator to the start of
3585 the operand list.<br>
3586     <tt>op_iterator op_end()</tt> - Get an iterator to the end of the
3587 operand list.
3588     <p> Together, these methods make up the iterator based interface to
3589 the operands of a <tt>User</tt>.</p></li>
3590 </ul>
3591
3592 </div>
3593
3594 </div>
3595
3596 <!-- ======================================================================= -->
3597 <h3>
3598   <a name="Instruction">The <tt>Instruction</tt> class</a>
3599 </h3>
3600
3601 <div>
3602
3603 <p><tt>#include "</tt><tt><a
3604 href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br>
3605 doxygen info: <a href="/doxygen/classllvm_1_1Instruction.html">Instruction Class</a><br>
3606 Superclasses: <a href="#User"><tt>User</tt></a>, <a
3607 href="#Value"><tt>Value</tt></a></p>
3608
3609 <p>The <tt>Instruction</tt> class is the common base class for all LLVM
3610 instructions.  It provides only a few methods, but is a very commonly used
3611 class.  The primary data tracked by the <tt>Instruction</tt> class itself is the
3612 opcode (instruction type) and the parent <a
3613 href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded
3614 into.  To represent a specific type of instruction, one of many subclasses of
3615 <tt>Instruction</tt> are used.</p>
3616
3617 <p> Because the <tt>Instruction</tt> class subclasses the <a
3618 href="#User"><tt>User</tt></a> class, its operands can be accessed in the same
3619 way as for other <a href="#User"><tt>User</tt></a>s (with the
3620 <tt>getOperand()</tt>/<tt>getNumOperands()</tt> and
3621 <tt>op_begin()</tt>/<tt>op_end()</tt> methods).</p> <p> An important file for
3622 the <tt>Instruction</tt> class is the <tt>llvm/Instruction.def</tt> file. This
3623 file contains some meta-data about the various different types of instructions
3624 in LLVM.  It describes the enum values that are used as opcodes (for example
3625 <tt>Instruction::Add</tt> and <tt>Instruction::ICmp</tt>), as well as the
3626 concrete sub-classes of <tt>Instruction</tt> that implement the instruction (for
3627 example <tt><a href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a
3628 href="#CmpInst">CmpInst</a></tt>).  Unfortunately, the use of macros in
3629 this file confuses doxygen, so these enum values don't show up correctly in the
3630 <a href="/doxygen/classllvm_1_1Instruction.html">doxygen output</a>.</p>
3631
3632 <!-- _______________________________________________________________________ -->
3633 <h4>
3634   <a name="s_Instruction">
3635     Important Subclasses of the <tt>Instruction</tt> class
3636   </a>
3637 </h4>
3638 <div>
3639   <ul>
3640     <li><tt><a name="BinaryOperator">BinaryOperator</a></tt>
3641     <p>This subclasses represents all two operand instructions whose operands
3642     must be the same type, except for the comparison instructions.</p></li>
3643     <li><tt><a name="CastInst">CastInst</a></tt>
3644     <p>This subclass is the parent of the 12 casting instructions. It provides
3645     common operations on cast instructions.</p>
3646     <li><tt><a name="CmpInst">CmpInst</a></tt>
3647     <p>This subclass respresents the two comparison instructions,
3648     <a href="LangRef.html#i_icmp">ICmpInst</a> (integer opreands), and
3649     <a href="LangRef.html#i_fcmp">FCmpInst</a> (floating point operands).</p>
3650     <li><tt><a name="TerminatorInst">TerminatorInst</a></tt>
3651     <p>This subclass is the parent of all terminator instructions (those which
3652     can terminate a block).</p>
3653   </ul>
3654   </div>
3655
3656 <!-- _______________________________________________________________________ -->
3657 <h4>
3658   <a name="m_Instruction">
3659     Important Public Members of the <tt>Instruction</tt> class
3660   </a>
3661 </h4>
3662
3663 <div>
3664
3665 <ul>
3666   <li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt>
3667     <p>Returns the <a href="#BasicBlock"><tt>BasicBlock</tt></a> that
3668 this  <tt>Instruction</tt> is embedded into.</p></li>
3669   <li><tt>bool mayWriteToMemory()</tt>
3670     <p>Returns true if the instruction writes to memory, i.e. it is a
3671       <tt>call</tt>,<tt>free</tt>,<tt>invoke</tt>, or <tt>store</tt>.</p></li>
3672   <li><tt>unsigned getOpcode()</tt>
3673     <p>Returns the opcode for the <tt>Instruction</tt>.</p></li>
3674   <li><tt><a href="#Instruction">Instruction</a> *clone() const</tt>
3675     <p>Returns another instance of the specified instruction, identical
3676 in all ways to the original except that the instruction has no parent
3677 (ie it's not embedded into a <a href="#BasicBlock"><tt>BasicBlock</tt></a>),
3678 and it has no name</p></li>
3679 </ul>
3680
3681 </div>
3682
3683 </div>
3684
3685 <!-- ======================================================================= -->
3686 <h3>
3687   <a name="Constant">The <tt>Constant</tt> class and subclasses</a>
3688 </h3>
3689
3690 <div>
3691
3692 <p>Constant represents a base class for different types of constants. It
3693 is subclassed by ConstantInt, ConstantArray, etc. for representing
3694 the various types of Constants.  <a href="#GlobalValue">GlobalValue</a> is also
3695 a subclass, which represents the address of a global variable or function.
3696 </p>
3697
3698 <!-- _______________________________________________________________________ -->
3699 <h4>Important Subclasses of Constant</h4>
3700 <div>
3701 <ul>
3702   <li>ConstantInt : This subclass of Constant represents an integer constant of
3703   any width.
3704     <ul>
3705       <li><tt>const APInt&amp; getValue() const</tt>: Returns the underlying
3706       value of this constant, an APInt value.</li>
3707       <li><tt>int64_t getSExtValue() const</tt>: Converts the underlying APInt
3708       value to an int64_t via sign extension. If the value (not the bit width)
3709       of the APInt is too large to fit in an int64_t, an assertion will result.
3710       For this reason, use of this method is discouraged.</li>
3711       <li><tt>uint64_t getZExtValue() const</tt>: Converts the underlying APInt
3712       value to a uint64_t via zero extension. IF the value (not the bit width)
3713       of the APInt is too large to fit in a uint64_t, an assertion will result.
3714       For this reason, use of this method is discouraged.</li>
3715       <li><tt>static ConstantInt* get(const APInt&amp; Val)</tt>: Returns the
3716       ConstantInt object that represents the value provided by <tt>Val</tt>.
3717       The type is implied as the IntegerType that corresponds to the bit width
3718       of <tt>Val</tt>.</li>
3719       <li><tt>static ConstantInt* get(const Type *Ty, uint64_t Val)</tt>:
3720       Returns the ConstantInt object that represents the value provided by
3721       <tt>Val</tt> for integer type <tt>Ty</tt>.</li>
3722     </ul>
3723   </li>
3724   <li>ConstantFP : This class represents a floating point constant.
3725     <ul>
3726       <li><tt>double getValue() const</tt>: Returns the underlying value of
3727       this constant. </li>
3728     </ul>
3729   </li>
3730   <li>ConstantArray : This represents a constant array.
3731     <ul>
3732       <li><tt>const std::vector&lt;Use&gt; &amp;getValues() const</tt>: Returns
3733       a vector of component constants that makeup this array. </li>
3734     </ul>
3735   </li>
3736   <li>ConstantStruct : This represents a constant struct.
3737     <ul>
3738       <li><tt>const std::vector&lt;Use&gt; &amp;getValues() const</tt>: Returns
3739       a vector of component constants that makeup this array. </li>
3740     </ul>
3741   </li>
3742   <li>GlobalValue : This represents either a global variable or a function. In
3743   either case, the value is a constant fixed address (after linking).
3744   </li>
3745 </ul>
3746 </div>
3747
3748 </div>
3749
3750 <!-- ======================================================================= -->
3751 <h3>
3752   <a name="GlobalValue">The <tt>GlobalValue</tt> class</a>
3753 </h3>
3754
3755 <div>
3756
3757 <p><tt>#include "<a
3758 href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br>
3759 doxygen info: <a href="/doxygen/classllvm_1_1GlobalValue.html">GlobalValue
3760 Class</a><br>
3761 Superclasses: <a href="#Constant"><tt>Constant</tt></a>,
3762 <a href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a></p>
3763
3764 <p>Global values (<a href="#GlobalVariable"><tt>GlobalVariable</tt></a>s or <a
3765 href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are
3766 visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s.
3767 Because they are visible at global scope, they are also subject to linking with
3768 other globals defined in different translation units.  To control the linking
3769 process, <tt>GlobalValue</tt>s know their linkage rules. Specifically,
3770 <tt>GlobalValue</tt>s know whether they have internal or external linkage, as
3771 defined by the <tt>LinkageTypes</tt> enumeration.</p>
3772
3773 <p>If a <tt>GlobalValue</tt> has internal linkage (equivalent to being
3774 <tt>static</tt> in C), it is not visible to code outside the current translation
3775 unit, and does not participate in linking.  If it has external linkage, it is
3776 visible to external code, and does participate in linking.  In addition to
3777 linkage information, <tt>GlobalValue</tt>s keep track of which <a
3778 href="#Module"><tt>Module</tt></a> they are currently part of.</p>
3779
3780 <p>Because <tt>GlobalValue</tt>s are memory objects, they are always referred to
3781 by their <b>address</b>. As such, the <a href="#Type"><tt>Type</tt></a> of a
3782 global is always a pointer to its contents. It is important to remember this
3783 when using the <tt>GetElementPtrInst</tt> instruction because this pointer must
3784 be dereferenced first. For example, if you have a <tt>GlobalVariable</tt> (a
3785 subclass of <tt>GlobalValue)</tt> that is an array of 24 ints, type <tt>[24 x
3786 i32]</tt>, then the <tt>GlobalVariable</tt> is a pointer to that array. Although
3787 the address of the first element of this array and the value of the
3788 <tt>GlobalVariable</tt> are the same, they have different types. The
3789 <tt>GlobalVariable</tt>'s type is <tt>[24 x i32]</tt>. The first element's type
3790 is <tt>i32.</tt> Because of this, accessing a global value requires you to
3791 dereference the pointer with <tt>GetElementPtrInst</tt> first, then its elements
3792 can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM
3793 Language Reference Manual</a>.</p>
3794
3795 <!-- _______________________________________________________________________ -->
3796 <h4>
3797   <a name="m_GlobalValue">
3798     Important Public Members of the <tt>GlobalValue</tt> class
3799   </a>
3800 </h4>
3801
3802 <div>
3803
3804 <ul>
3805   <li><tt>bool hasInternalLinkage() const</tt><br>
3806     <tt>bool hasExternalLinkage() const</tt><br>
3807     <tt>void setInternalLinkage(bool HasInternalLinkage)</tt>
3808     <p> These methods manipulate the linkage characteristics of the <tt>GlobalValue</tt>.</p>
3809     <p> </p>
3810   </li>
3811   <li><tt><a href="#Module">Module</a> *getParent()</tt>
3812     <p> This returns the <a href="#Module"><tt>Module</tt></a> that the
3813 GlobalValue is currently embedded into.</p></li>
3814 </ul>
3815
3816 </div>
3817
3818 </div>
3819
3820 <!-- ======================================================================= -->
3821 <h3>
3822   <a name="Function">The <tt>Function</tt> class</a>
3823 </h3>
3824
3825 <div>
3826
3827 <p><tt>#include "<a
3828 href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen
3829 info: <a href="/doxygen/classllvm_1_1Function.html">Function Class</a><br>
3830 Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
3831 <a href="#Constant"><tt>Constant</tt></a>,
3832 <a href="#User"><tt>User</tt></a>,
3833 <a href="#Value"><tt>Value</tt></a></p>
3834
3835 <p>The <tt>Function</tt> class represents a single procedure in LLVM.  It is
3836 actually one of the more complex classes in the LLVM hierarchy because it must
3837 keep track of a large amount of data.  The <tt>Function</tt> class keeps track
3838 of a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, a list of formal
3839 <a href="#Argument"><tt>Argument</tt></a>s, and a
3840 <a href="#SymbolTable"><tt>SymbolTable</tt></a>.</p>
3841
3842 <p>The list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s is the most
3843 commonly used part of <tt>Function</tt> objects.  The list imposes an implicit
3844 ordering of the blocks in the function, which indicate how the code will be
3845 laid out by the backend.  Additionally, the first <a
3846 href="#BasicBlock"><tt>BasicBlock</tt></a> is the implicit entry node for the
3847 <tt>Function</tt>.  It is not legal in LLVM to explicitly branch to this initial
3848 block.  There are no implicit exit nodes, and in fact there may be multiple exit
3849 nodes from a single <tt>Function</tt>.  If the <a
3850 href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that
3851 the <tt>Function</tt> is actually a function declaration: the actual body of the
3852 function hasn't been linked in yet.</p>
3853
3854 <p>In addition to a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, the
3855 <tt>Function</tt> class also keeps track of the list of formal <a
3856 href="#Argument"><tt>Argument</tt></a>s that the function receives.  This
3857 container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a>
3858 nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for
3859 the <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.</p>
3860
3861 <p>The <a href="#SymbolTable"><tt>SymbolTable</tt></a> is a very rarely used
3862 LLVM feature that is only used when you have to look up a value by name.  Aside
3863 from that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used
3864 internally to make sure that there are not conflicts between the names of <a
3865 href="#Instruction"><tt>Instruction</tt></a>s, <a
3866 href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a
3867 href="#Argument"><tt>Argument</tt></a>s in the function body.</p>
3868
3869 <p>Note that <tt>Function</tt> is a <a href="#GlobalValue">GlobalValue</a>
3870 and therefore also a <a href="#Constant">Constant</a>. The value of the function
3871 is its address (after linking) which is guaranteed to be constant.</p>
3872
3873 <!-- _______________________________________________________________________ -->
3874 <h4>
3875   <a name="m_Function">
3876     Important Public Members of the <tt>Function</tt> class
3877   </a>
3878 </h4>
3879
3880 <div>
3881
3882 <ul>
3883   <li><tt>Function(const </tt><tt><a href="#FunctionType">FunctionType</a>
3884   *Ty, LinkageTypes Linkage, const std::string &amp;N = "", Module* Parent = 0)</tt>
3885
3886     <p>Constructor used when you need to create new <tt>Function</tt>s to add
3887     the program.  The constructor must specify the type of the function to
3888     create and what type of linkage the function should have. The <a
3889     href="#FunctionType"><tt>FunctionType</tt></a> argument
3890     specifies the formal arguments and return value for the function. The same
3891     <a href="#FunctionType"><tt>FunctionType</tt></a> value can be used to
3892     create multiple functions. The <tt>Parent</tt> argument specifies the Module
3893     in which the function is defined. If this argument is provided, the function
3894     will automatically be inserted into that module's list of
3895     functions.</p></li>
3896
3897   <li><tt>bool isDeclaration()</tt>
3898
3899     <p>Return whether or not the <tt>Function</tt> has a body defined.  If the
3900     function is "external", it does not have a body, and thus must be resolved
3901     by linking with a function defined in a different translation unit.</p></li>
3902
3903   <li><tt>Function::iterator</tt> - Typedef for basic block list iterator<br>
3904     <tt>Function::const_iterator</tt> - Typedef for const_iterator.<br>
3905
3906     <tt>begin()</tt>, <tt>end()</tt>
3907     <tt>size()</tt>, <tt>empty()</tt>
3908
3909     <p>These are forwarding methods that make it easy to access the contents of
3910     a <tt>Function</tt> object's <a href="#BasicBlock"><tt>BasicBlock</tt></a>
3911     list.</p></li>
3912
3913   <li><tt>Function::BasicBlockListType &amp;getBasicBlockList()</tt>
3914
3915     <p>Returns the list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.  This
3916     is necessary to use when you need to update the list or perform a complex
3917     action that doesn't have a forwarding method.</p></li>
3918
3919   <li><tt>Function::arg_iterator</tt> - Typedef for the argument list
3920 iterator<br>
3921     <tt>Function::const_arg_iterator</tt> - Typedef for const_iterator.<br>
3922
3923     <tt>arg_begin()</tt>, <tt>arg_end()</tt>
3924     <tt>arg_size()</tt>, <tt>arg_empty()</tt>
3925
3926     <p>These are forwarding methods that make it easy to access the contents of
3927     a <tt>Function</tt> object's <a href="#Argument"><tt>Argument</tt></a>
3928     list.</p></li>
3929
3930   <li><tt>Function::ArgumentListType &amp;getArgumentList()</tt>
3931
3932     <p>Returns the list of <a href="#Argument"><tt>Argument</tt></a>s.  This is
3933     necessary to use when you need to update the list or perform a complex
3934     action that doesn't have a forwarding method.</p></li>
3935
3936   <li><tt><a href="#BasicBlock">BasicBlock</a> &amp;getEntryBlock()</tt>
3937
3938     <p>Returns the entry <a href="#BasicBlock"><tt>BasicBlock</tt></a> for the
3939     function.  Because the entry block for the function is always the first
3940     block, this returns the first block of the <tt>Function</tt>.</p></li>
3941
3942   <li><tt><a href="#Type">Type</a> *getReturnType()</tt><br>
3943     <tt><a href="#FunctionType">FunctionType</a> *getFunctionType()</tt>
3944
3945     <p>This traverses the <a href="#Type"><tt>Type</tt></a> of the
3946     <tt>Function</tt> and returns the return type of the function, or the <a
3947     href="#FunctionType"><tt>FunctionType</tt></a> of the actual
3948     function.</p></li>
3949
3950   <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt>
3951
3952     <p> Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a>
3953     for this <tt>Function</tt>.</p></li>
3954 </ul>
3955
3956 </div>
3957
3958 </div>
3959
3960 <!-- ======================================================================= -->
3961 <h3>
3962   <a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a>
3963 </h3>
3964
3965 <div>
3966
3967 <p><tt>#include "<a
3968 href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt>
3969 <br>
3970 doxygen info: <a href="/doxygen/classllvm_1_1GlobalVariable.html">GlobalVariable
3971  Class</a><br>
3972 Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>,
3973 <a href="#Constant"><tt>Constant</tt></a>,
3974 <a href="#User"><tt>User</tt></a>,
3975 <a href="#Value"><tt>Value</tt></a></p>
3976
3977 <p>Global variables are represented with the (surprise surprise)
3978 <tt>GlobalVariable</tt> class. Like functions, <tt>GlobalVariable</tt>s are also
3979 subclasses of <a href="#GlobalValue"><tt>GlobalValue</tt></a>, and as such are
3980 always referenced by their address (global values must live in memory, so their
3981 "name" refers to their constant address). See
3982 <a href="#GlobalValue"><tt>GlobalValue</tt></a> for more on this.  Global
3983 variables may have an initial value (which must be a
3984 <a href="#Constant"><tt>Constant</tt></a>), and if they have an initializer,
3985 they may be marked as "constant" themselves (indicating that their contents
3986 never change at runtime).</p>
3987
3988 <!-- _______________________________________________________________________ -->
3989 <h4>
3990   <a name="m_GlobalVariable">
3991     Important Public Members of the <tt>GlobalVariable</tt> class
3992   </a>
3993 </h4>
3994
3995 <div>
3996
3997 <ul>
3998   <li><tt>GlobalVariable(const </tt><tt><a href="#Type">Type</a> *Ty, bool
3999   isConstant, LinkageTypes&amp; Linkage, <a href="#Constant">Constant</a>
4000   *Initializer = 0, const std::string &amp;Name = "", Module* Parent = 0)</tt>
4001
4002     <p>Create a new global variable of the specified type. If
4003     <tt>isConstant</tt> is true then the global variable will be marked as
4004     unchanging for the program. The Linkage parameter specifies the type of
4005     linkage (internal, external, weak, linkonce, appending) for the variable.
4006     If the linkage is InternalLinkage, WeakAnyLinkage, WeakODRLinkage,
4007     LinkOnceAnyLinkage or LinkOnceODRLinkage,&nbsp; then the resultant
4008     global variable will have internal linkage.  AppendingLinkage concatenates
4009     together all instances (in different translation units) of the variable
4010     into a single variable but is only applicable to arrays.  &nbsp;See
4011     the <a href="LangRef.html#modulestructure">LLVM Language Reference</a> for
4012     further details on linkage types. Optionally an initializer, a name, and the
4013     module to put the variable into may be specified for the global variable as
4014     well.</p></li>
4015
4016   <li><tt>bool isConstant() const</tt>
4017
4018     <p>Returns true if this is a global variable that is known not to
4019     be modified at runtime.</p></li>
4020
4021   <li><tt>bool hasInitializer()</tt>
4022
4023     <p>Returns true if this <tt>GlobalVariable</tt> has an intializer.</p></li>
4024
4025   <li><tt><a href="#Constant">Constant</a> *getInitializer()</tt>
4026
4027     <p>Returns the initial value for a <tt>GlobalVariable</tt>.  It is not legal
4028     to call this method if there is no initializer.</p></li>
4029 </ul>
4030
4031 </div>
4032
4033 </div>
4034
4035 <!-- ======================================================================= -->
4036 <h3>
4037   <a name="BasicBlock">The <tt>BasicBlock</tt> class</a>
4038 </h3>
4039
4040 <div>
4041
4042 <p><tt>#include "<a
4043 href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt><br>
4044 doxygen info: <a href="/doxygen/classllvm_1_1BasicBlock.html">BasicBlock
4045 Class</a><br>
4046 Superclass: <a href="#Value"><tt>Value</tt></a></p>
4047
4048 <p>This class represents a single entry single exit section of the code,
4049 commonly known as a basic block by the compiler community.  The
4050 <tt>BasicBlock</tt> class maintains a list of <a
4051 href="#Instruction"><tt>Instruction</tt></a>s, which form the body of the block.
4052 Matching the language definition, the last element of this list of instructions
4053 is always a terminator instruction (a subclass of the <a
4054 href="#TerminatorInst"><tt>TerminatorInst</tt></a> class).</p>
4055
4056 <p>In addition to tracking the list of instructions that make up the block, the
4057 <tt>BasicBlock</tt> class also keeps track of the <a
4058 href="#Function"><tt>Function</tt></a> that it is embedded into.</p>
4059
4060 <p>Note that <tt>BasicBlock</tt>s themselves are <a
4061 href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions
4062 like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type
4063 <tt>label</tt>.</p>
4064
4065 <!-- _______________________________________________________________________ -->
4066 <h4>
4067   <a name="m_BasicBlock">
4068     Important Public Members of the <tt>BasicBlock</tt> class
4069   </a>
4070 </h4>
4071
4072 <div>
4073 <ul>
4074
4075 <li><tt>BasicBlock(const std::string &amp;Name = "", </tt><tt><a
4076  href="#Function">Function</a> *Parent = 0)</tt>
4077
4078 <p>The <tt>BasicBlock</tt> constructor is used to create new basic blocks for
4079 insertion into a function.  The constructor optionally takes a name for the new
4080 block, and a <a href="#Function"><tt>Function</tt></a> to insert it into.  If
4081 the <tt>Parent</tt> parameter is specified, the new <tt>BasicBlock</tt> is
4082 automatically inserted at the end of the specified <a
4083 href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be
4084 manually inserted into the <a href="#Function"><tt>Function</tt></a>.</p></li>
4085
4086 <li><tt>BasicBlock::iterator</tt> - Typedef for instruction list iterator<br>
4087 <tt>BasicBlock::const_iterator</tt> - Typedef for const_iterator.<br>
4088 <tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>,
4089 <tt>size()</tt>, <tt>empty()</tt>
4090 STL-style functions for accessing the instruction list.
4091
4092 <p>These methods and typedefs are forwarding functions that have the same
4093 semantics as the standard library methods of the same names.  These methods
4094 expose the underlying instruction list of a basic block in a way that is easy to
4095 manipulate.  To get the full complement of container operations (including
4096 operations to update the list), you must use the <tt>getInstList()</tt>
4097 method.</p></li>
4098
4099 <li><tt>BasicBlock::InstListType &amp;getInstList()</tt>
4100
4101 <p>This method is used to get access to the underlying container that actually
4102 holds the Instructions.  This method must be used when there isn't a forwarding
4103 function in the <tt>BasicBlock</tt> class for the operation that you would like
4104 to perform.  Because there are no forwarding functions for "updating"
4105 operations, you need to use this if you want to update the contents of a
4106 <tt>BasicBlock</tt>.</p></li>
4107
4108 <li><tt><a href="#Function">Function</a> *getParent()</tt>
4109
4110 <p> Returns a pointer to <a href="#Function"><tt>Function</tt></a> the block is
4111 embedded into, or a null pointer if it is homeless.</p></li>
4112
4113 <li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt>
4114
4115 <p> Returns a pointer to the terminator instruction that appears at the end of
4116 the <tt>BasicBlock</tt>.  If there is no terminator instruction, or if the last
4117 instruction in the block is not a terminator, then a null pointer is
4118 returned.</p></li>
4119
4120 </ul>
4121
4122 </div>
4123
4124 </div>
4125
4126 <!-- ======================================================================= -->
4127 <h3>
4128   <a name="Argument">The <tt>Argument</tt> class</a>
4129 </h3>
4130
4131 <div>
4132
4133 <p>This subclass of Value defines the interface for incoming formal
4134 arguments to a function. A Function maintains a list of its formal
4135 arguments. An argument has a pointer to the parent Function.</p>
4136
4137 </div>
4138
4139 </div>
4140
4141 <!-- *********************************************************************** -->
4142 <hr>
4143 <address>
4144   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
4145   src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
4146   <a href="http://validator.w3.org/check/referer"><img
4147   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Strict"></a>
4148
4149   <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and
4150   <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
4151   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
4152   Last modified: $Date$
4153 </address>
4154
4155 </body>
4156 </html>