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