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> 31 and <tt>dyn_cast<></tt> templates</a> </li> 32 <li><a href="#string_apis">Passing strings (the <tt>StringRef</tt> 33 and <tt>Twine</tt> classes)</a> 34 <ul> 35 <li><a href="#StringRef">The <tt>StringRef</tt> class</a> </li> 36 <li><a href="#Twine">The <tt>Twine</tt> class</a> </li> 37 </ul> 38 </li> 39 <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> 40 option</a> 41 <ul> 42 <li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> 43 and the <tt>-debug-only</tt> option</a> </li> 44 </ul> 45 </li> 46 <li><a href="#Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt> 47 option</a></li> 48 <!-- 49 <li>The <tt>InstVisitor</tt> template 50 <li>The general graph API 51 --> 52 <li><a href="#ViewGraph">Viewing graphs while debugging code</a></li> 53 </ul> 54 </li> 55 <li><a href="#datastructure">Picking the Right Data Structure for a Task</a> 56 <ul> 57 <li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a> 58 <ul> 59 <li><a href="#dss_arrayref">llvm/ADT/ArrayRef.h</a></li> 60 <li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li> 61 <li><a href="#dss_heaparrays">Heap Allocated Arrays</a></li> 62 <li><a href="#dss_tinyptrvector">"llvm/ADT/TinyPtrVector.h"</a></li> 63 <li><a href="#dss_smallvector">"llvm/ADT/SmallVector.h"</a></li> 64 <li><a href="#dss_vector"><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 112 in a <tt>Function</tt></a> </li> 113 <li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s 114 in a <tt>BasicBlock</tt></a> </li> 115 <li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s 116 in a <tt>Function</tt></a> </li> 117 <li><a href="#iterate_convert">Turning an iterator into a 118 class pointer</a> </li> 119 <li><a href="#iterate_complex">Finding call sites: a more 120 complex example</a> </li> 121 <li><a href="#calls_and_invokes">Treating calls and invokes 122 the same way</a> </li> 123 <li><a href="#iterate_chains">Iterating over def-use & 124 use-def chains</a> </li> 125 <li><a href="#iterate_preds">Iterating over predecessors & 126 successors 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> 135 with 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 (a] nondot.org">Chris Lattner</a>, 200 <a href="mailto:dhurjati (a] cs.uiuc.edu">Dinakar Dhurjati</a>, 201 <a href="mailto:ggreif (a] gmail.com">Gabor Greif</a>, 202 <a href="mailto:jstanley (a] cs.uiuc.edu">Joel Stanley</a>, 203 <a href="mailto:rspencer (a] x10sys.com">Reid Spencer</a> and 204 <a href="mailto:owen (a] 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 216 interfaces available in the LLVM source-base. This manual is not 217 intended to explain what LLVM is, how it works, and what LLVM code looks 218 like. It assumes that you know the basics of LLVM and are interested 219 in writing transformations or otherwise analyzing or manipulating the 220 code.</p> 221 222 <p>This document should get you oriented so that you can find your 223 way in the continuously growing source code that makes up the LLVM 224 infrastructure. Note that this manual is not intended to serve as a 225 replacement for reading the source code, so if you think there should be 226 a method in one of these classes to do something, but it's not listed, 227 check the source. Links to the <a href="/doxygen/">doxygen</a> sources 228 are provided to make this as easy as possible.</p> 229 230 <p>The first section of this document describes general information that is 231 useful to know when working in the LLVM infrastructure, and the second describes 232 the Core LLVM classes. In the future this manual will be extended with 233 information describing how to use extension libraries, such as dominator 234 information, CFG traversal routines, and useful utilities like the <tt><a 235 href="/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 248 in 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), 258 perhaps much more than you are used to, or have seen before. Because of 259 this, you might want to do a little background reading in the 260 techniques used and capabilities of the library. There are many good 261 pages that discuss the STL, and several books on the subject that you 262 can 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 269 C++ Library reference</a> - an excellent reference for the STL and other parts 270 of the standard C++ library.</li> 271 272 <li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an 273 O'Reilly book in the making. It has a decent Standard Library 274 Reference that rivals Dinkumware's, and is unfortunately no longer free since the 275 book has been published.</li> 276 277 <li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked 278 Questions</a></li> 279 280 <li><a href="http://www.sgi.com/tech/stl/">SGI's STL Programmer's Guide</a> - 281 Contains a useful <a 282 href="http://www.sgi.com/tech/stl/stl_introduction.html">Introduction to the 283 STL</a>.</li> 284 285 <li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++ 286 Page</a></li> 287 288 <li><a href="http://64.78.49.204/"> 289 Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get 290 the book).</a></li> 291 292 </ol> 293 294 <p>You are also encouraged to take a look at the <a 295 href="CodingStandards.html">LLVM Coding Standards</a> guide which focuses on how 296 to 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 309 static 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 325 know 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. 336 These templates have many similarities to the C++ <tt>dynamic_cast<></tt> 337 operator, but they don't have some drawbacks (primarily stemming from 338 the fact that <tt>dynamic_cast<></tt> only works on classes that 339 have a v-table). Because they are used so often, you must know what they 340 do 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> 342 file (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> 364 static 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> 393 if (<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 429 v-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 431 to. Describing this is currently outside the scope of this document, but there 432 are 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> 440 and <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 446 several important APIs which take strings. Two important examples are the 447 Value class -- which has names for instructions, functions, etc. -- and the 448 StringMap 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 451 may have embedded null characters. Therefore, they cannot simply take 452 a <tt>const char *</tt>, and taking a <tt>const std::string&</tt> requires 453 clients to perform a heap allocation which is usually unnecessary. Instead, 454 many LLVM APIs use a <tt>StringRef</tt> or a <tt>const Twine&</tt> for 455 passing 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 466 on <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, 469 an <tt>std::string</tt>, or explicitly with a character pointer and length. 470 For 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> 485 instance, which can be used directly or converted to an <tt>std::string</tt> 486 using the <tt>str</tt> member function. See 487 "<tt><a href="/doxygen/classllvm_1_1StringRef_8h-source.html">llvm/ADT/StringRef.h</a></tt>" 488 for more information.</p> 489 490 <p>You should rarely use the <tt>StringRef</tt> class directly, because it contains 491 pointers to external memory it is not generally safe to store an instance of the 492 class (unless you know that the external storage will not be freed). StringRef is 493 small 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 505 strings. For example, a common LLVM paradigm is to name one instruction based on 506 the 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 515 lightweight <a href="http://en.wikipedia.org/wiki/Rope_(computer_science)">rope</a> 516 which points to temporary (stack allocated) objects. Twines can be implicitly 517 constructed as the result of the plus operator applied to strings (i.e., a C 518 strings, an <tt>std::string</tt>, or a <tt>StringRef</tt>). The twine delays the 519 actual concatenation of strings until it is actually required, at which point 520 it can be efficiently rendered directly into a character array. This avoids 521 unnecessary heap allocation involved in constructing the temporary results of 522 string concatenation. See 523 "<tt><a href="/doxygen/classllvm_1_1Twine_8h-source.html">llvm/ADT/Twine.h</a></tt>" 524 for more information.</p> 525 526 <p>As with a <tt>StringRef</tt>, <tt>Twine</tt> objects point to external memory 527 and should almost never be stored or mentioned directly. They are intended 528 solely for use when defining a function which should be able to efficiently 529 accept 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 543 and other code into your pass. After you get it working, you want to remove 544 it, but you may need it again in the future (to work out new bugs that you run 545 across).</p> 546 547 <p> Naturally, because of this, you don't want to delete the debug printouts, 548 but you don't want them to always be noisy. A standard compromise is to comment 549 them 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>" 552 file provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to 553 this 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 555 tool) is run with the '<tt>-debug</tt>' command line argument:</p> 556 557 <div class="doc_code"> 558 <pre> 559 DEBUG(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 570 I am here! 571 </pre> 572 </div> 573 574 <p>Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you 575 to not have to create "yet another" command line option for the debug output for 576 your pass. Note that <tt>DEBUG()</tt> macros are disabled for optimized builds, 577 so they do not cause a performance impact at all (for the same reason, they 578 should also not contain side-effects!).</p> 579 580 <p>One additional nice thing about the <tt>DEBUG()</tt> macro is that you can 581 enable 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 583 program 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> 595 just turns on <b>too much</b> information (such as when working on the code 596 generator). If you want to enable debug information with more fine-grained 597 control, you define the <tt>DEBUG_TYPE</tt> macro and the <tt>-debug</tt> only 598 option as follows:</p> 599 600 <div class="doc_code"> 601 <pre> 602 #undef DEBUG_TYPE 603 DEBUG(errs() << "No debug type\n"); 604 #define DEBUG_TYPE "foo" 605 DEBUG(errs() << "'foo' debug type\n"); 606 #undef DEBUG_TYPE 607 #define DEBUG_TYPE "bar" 608 DEBUG(errs() << "'bar' debug type\n")); 609 #undef DEBUG_TYPE 610 #define DEBUG_TYPE "" 611 DEBUG(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 622 No debug type 623 'foo' debug type 624 'bar' debug type 625 No 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 634 a file, to specify the debug type for the entire module (if you do this before 635 you <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 638 conflict. If two different modules use the same string, they will all be turned 639 on when the name is specified. This allows, for example, all debug information 640 for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>, 641 even 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 644 would like to set <tt>DEBUG_TYPE</tt>, but only for one specific <tt>DEBUG</tt> 645 statement. It takes an additional first parameter, which is the type to use. For 646 example, the preceding example could be written as:</p> 647 648 649 <div class="doc_code"> 650 <pre> 651 DEBUG_WITH_TYPE("", errs() << "No debug type\n"); 652 DEBUG_WITH_TYPE("foo", errs() << "'foo' debug type\n"); 653 DEBUG_WITH_TYPE("bar", errs() << "'bar' debug type\n")); 654 DEBUG_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 671 href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file 672 provides a class named <tt>Statistic</tt> that is used as a unified way to 673 keep track of what the LLVM compiler is doing and how effective various 674 optimizations are. It is useful to see what optimizations are contributing to 675 making 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 678 how many times it makes a certain transformation. Although you can do this with 679 hand inspection, or some ad-hoc method, this is a real pain and not very useful 680 for big programs. Using the <tt>Statistic</tt> class makes it very easy to 681 keep track of this information, and the calculated information is presented in a 682 uniform 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 685 it 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> 693 STATISTIC(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 724 suite, 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 757 stuff is very nice. Making your pass fit well into the framework makes it more 758 maintainable 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 770 CFGs made out of LLVM <a href="#BasicBlock">BasicBlock</a>s, CFGs made out of 771 LLVM <a href="CodeGenerator.html#machinebasicblock">MachineBasicBlock</a>s, and 772 <a href="CodeGenerator.html#selectiondag_intro">Instruction Selection 773 DAGs</a>. In many cases, while debugging various parts of the compiler, it is 774 nice to instantly visualize these graphs.</p> 775 776 <p>LLVM provides several callbacks that are available in a debug build to do 777 exactly that. If you call the <tt>Function::viewCFG()</tt> method, for example, 778 the current LLVM tool will pop up a window containing the CFG for the function 779 where each basic block is a node in the graph, and each node contains the 780 instructions 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>, 783 and the <tt>SelectionDAG::viewGraph()</tt> methods. Within GDB, for example, 784 you can usually use something like <tt>call DAG.viewGraph()</tt> to pop 785 up a window. Alternatively, you can sprinkle calls to these functions in your 786 code in places you want to debug.</p> 787 788 <p>Getting this to work requires a small amount of configuration. On Unix 789 systems with X11, install the <a href="http://www.graphviz.org">graphviz</a> 790 toolkit, and make sure 'dot' and 'gv' are in your path. If you are running on 791 Mac OS/X, download and install the Mac OS/X <a 792 href="http://www.pixelglow.com/graphviz/">Graphviz program</a>, and add 793 <tt>/Applications/Graphviz.app/Contents/MacOS/</tt> (or wherever you install 794 it) to your path. Once in your system and path are set up, rerun the LLVM 795 configure 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 800 next <tt>call DAG.viewGraph()</tt> would highlight the node in the 801 specified color (choices of colors can be found at <a 802 href="http://www.graphviz.org/doc/info/colors.html">colors</a>.) More 803 complex node attributes can be provided with <tt>call 804 DAG.setGraphAttrs(<i>node</i>, "<i>attributes</i>")</tt> (choices can be 805 found at <a href="http://www.graphviz.org/doc/info/attrs.html">Graph 806 Attributes</a>.) If you want to restart and clear all the current graph 807 attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p> 808 809 <p>Note that graph visualization features are compiled out of Release builds 810 to reduce file size. This means that you need a Debug+Asserts or 811 Release+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> 830 The first step is a choose your own adventure: do you want a sequential 831 container, a set-like container, or a map-like container? The most important 832 thing when choosing a container is the algorithmic properties of how you plan to 833 access 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> 870 Once the proper category of container is determined, you can fine tune the 871 memory use, constant factors, and cache behaviors of access by intelligently 872 picking a member of the category. Note that constant factors and cache behavior 873 can be a big deal. If you have a vector that usually only contains a few 874 elements (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 877 cost 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> 885 There are a variety of sequential containers available for you, based on your 886 needs. 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 910 exactly how many elements you have, or you have a (low) upper bound on how many 911 you 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 921 the number of elements is variable, if you know how many elements you will need 922 before the array is allocated, and if the array is usually large (if not, 923 consider a <a href="#dss_smallvector">SmallVector</a>). The cost of a heap 924 allocated array is the cost of the new/delete (aka malloc/free). Also note that 925 if you are allocating an array of a type with a constructor, the constructor and 926 destructors will be run for every element in the array (re-sizable vectors only 927 construct 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 938 that is optimized to avoid allocation in the case when a vector has zero or one 939 elements. It has two major restrictions: 1) it can only hold values of pointer 940 type, 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 955 just like <tt>vector<Type></tt>: 956 it supports efficient iteration, lays out elements in memory order (so you can 957 do pointer arithmetic between elements), supports efficient push_back/pop_back 958 operations, supports efficient random access to its elements, etc.</p> 959 960 <p>The advantage of SmallVector is that it allocates space for 961 some number of elements (N) <b>in the object itself</b>. Because of this, if 962 the SmallVector is dynamically smaller than N, no malloc is performed. This can 963 be a big win in cases where the malloc/free call is far more expensive than the 964 code that fiddles around with the elements.</p> 965 966 <p>This is good for vectors that are "usually small" (e.g. the number of 967 predecessors/successors of a block is usually less than 8). On the other hand, 968 this makes the size of the SmallVector itself large, so you don't want to 969 allocate lots of them (doing so will waste a lot of space). As such, 970 SmallVectors 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> 984 std::vector is well loved and respected. It is useful when SmallVector isn't: 985 when the size of the vector is often large (thus the small optimization will 986 rarely be a benefit) or if you will be allocating many instances of the vector 987 itself (which would waste space for elements that aren't in the container). 988 vector 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> 995 for ( ... ) { 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> 1006 std::vector<foo> V; 1007 for ( ... ) { 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 1015 the 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 1026 std::vector, it provides constant time random access and other similar 1027 properties, but it also provides efficient access to the front of the list. It 1028 does not guarantee continuity of elements within memory.</p> 1029 1030 <p>In exchange for this extra flexibility, std::deque has significantly higher 1031 constant factor costs than std::vector. If possible, use std::vector or 1032 something 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. 1042 It performs a heap allocation for every element inserted into it, thus having an 1043 extremely high constant factor, particularly for small data types. std::list 1044 also 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 1047 ends of the list (like std::deque, but unlike std::vector or SmallVector). In 1048 addition, the iterator invalidation characteristics of std::list are stronger 1049 than that of a vector class: inserting or removing an element into the list does 1050 not 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 1060 intrusive, because it requires the element to store and provide access to the 1061 prev/next pointers for the list.</p> 1062 1063 <p><tt>ilist</tt> has the same drawbacks as <tt>std::list</tt>, and additionally 1064 requires an <tt>ilist_traits</tt> implementation for the element type, but it 1065 provides some novel characteristics. In particular, it can efficiently store 1066 polymorphic objects, the traits class is informed when an element is inserted or 1067 removed from the list, and <tt>ilist</tt>s are guaranteed to support a 1068 constant-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 1074 Related 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> 1090 Useful for storing a vector of values using only a few number of bits for each 1091 value. Apart from the standard operations of a vector-like container, it can 1092 also perform an 'or' set operation. 1093 </p> 1094 1095 <p>For example:</p> 1096 1097 <div class="doc_code"> 1098 <pre> 1099 enum State { 1100 None = 0x0, 1101 FirstCondition = 0x1, 1102 SecondCondition = 0x2, 1103 Both = 0x3 1104 }; 1105 1106 State 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 1128 mechanism. <tt>iplist<T></tt> (and consequently <tt>ilist<T></tt>) 1129 publicly 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 1139 supports 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 1143 used 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 1153 that are expected by the <tt>ilist<T></tt> (and analogous containers) 1154 in 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 1168 citizen in the C++ ecosystem, it needs to support the standard container 1169 operations, 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 1171 case 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> 1175 iterator, providing the back-link to the last element. However conforming to the 1176 C++ convention it is illegal to <tt>operator++</tt> beyond the sentinel and it 1177 also must not be dereferenced.</p> 1178 1179 <p>These constraints allow for some implementation freedom to the <tt>ilist</tt> 1180 how to allocate and store the sentinel. The corresponding policy is dictated 1181 by <tt>ilist_traits<T></tt>. By default a <tt>T</tt> gets heap-allocated 1182 whenever 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 1186 instances of <tt>ilist</tt>s, the memory overhead of the associated sentinels 1187 is wasted. To alleviate the situation with numerous and voluminous 1188 <tt>T</tt>-sentinels, sometimes a trick is employed, leading to <i>ghostly 1189 sentinels</i>.</p> 1190 1191 <p>Ghostly sentinels are obtained by specially-crafted <tt>ilist_traits<T></tt> 1192 which superpose the sentinel with the <tt>ilist</tt> instance in memory. Pointer 1193 arithmetic 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 1195 extra pointer, which serves as the back-link of the sentinel. This is the only 1196 field 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, 1208 std::priority_queue, std::stack, etc. These provide simplified access to an 1209 underlying 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 1223 into a single representation. There are several different choices for how to do 1224 this, 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 1234 great approach is to use a vector (or other sequential container) with 1235 std::sort+std::unique to remove duplicates. This approach works really well if 1236 your usage pattern has these two distinct phases (insert then query), and can be 1237 coupled with a good choice of <a href="#ds_sequential">sequential container</a>. 1238 </p> 1239 1240 <p> 1241 This combination provides the several nice properties: the result data is 1242 contiguous in memory (good for cache locality), has few allocations, is easy to 1243 address (iterators in the final vector are just indices or pointers), and can be 1244 efficiently 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 1256 are reasonably small, a <tt>SmallSet<Type, N></tt> is a good choice. This set 1257 has space for N elements in place (thus, if the set is dynamically smaller than 1258 N, no malloc traffic is required) and accesses them with a simple linear search. 1259 When the set grows beyond 'N' elements, it allocates a more expensive representation that 1260 guarantees efficient access (for most types, it falls back to std::set, but for 1261 pointers it uses something far better, <a 1262 href="#dss_smallptrset">SmallPtrSet</a>).</p> 1263 1264 <p>The magic of this class is that it handles small sets extremely efficiently, 1265 but gracefully handles extremely large sets without loss of efficiency. The 1266 drawback is that the interface is quite small: it supports insertion, queries 1267 and 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 1279 transparently implemented with a <tt>SmallPtrSet</tt>), but also supports iterators. If 1280 more than 'N' insertions are performed, a single quadratically 1281 probed hash table is allocated and grows as needed, providing extremely 1282 efficient access (constant time insertion/deleting/queries with low constant 1283 factors) 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 1286 whenever an insertion occurs. Also, the values visited by the iterators are not 1287 visited 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> 1299 DenseSet is a simple quadratically probed hash table. It excels at supporting 1300 small values: it uses a single allocation to hold all of the pairs that 1301 are currently inserted in the set. DenseSet is a great way to unique small 1302 values that are not simple pointers (use <a 1303 href="#dss_smallptrset">SmallPtrSet</a> for pointers). Note that DenseSet has 1304 the same requirements for the value type that <a 1305 href="#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> 1318 FoldingSet is an aggregate class that is really good at uniquing 1319 expensive-to-create or polymorphic objects. It is a combination of a chained 1320 hash table with intrusive links (uniqued objects are required to inherit from 1321 FoldingSetNode) that uses <a href="#dss_smallvector">SmallVector</a> as part of 1322 its ID process.</p> 1323 1324 <p>Consider a case where you want to implement a "getOrCreateFoo" method for 1325 a complex object (for example, a node in the code generator). The client has a 1326 description of *what* it wants to generate (it knows the opcode and all the 1327 operands), but we don't want to 'new' a node, then try inserting it into a set 1328 only to find out it already exists, at which point we would have to delete it 1329 and return the node that already exists. 1330 </p> 1331 1332 <p>To support this style of client, FoldingSet perform a query with a 1333 FoldingSetNodeID (which wraps SmallVector) that can be used to describe the 1334 element that we want to query for. The query either returns the element 1335 matching the ID or it returns an opaque ID that indicates where insertion should 1336 take 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 1339 in the set (for example, you can have SDNode instances mixed with LoadSDNodes). 1340 Because the elements are individually allocated, pointers to the elements are 1341 stable: inserting or removing elements does not invalidate any pointers to other 1342 elements. 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 1355 many things but great at nothing. std::set allocates memory for each element 1356 inserted (thus it is very malloc intensive) and typically stores three pointers 1357 per element in the set (thus adding a large amount of per-element space 1358 overhead). It offers guaranteed log(n) performance, which is not particularly 1359 fast from a complexity standpoint (particularly if the elements of the set are 1360 expensive to compare, like strings), and has extremely high constant factors for 1361 lookup, insertion and removal.</p> 1362 1363 <p>The advantages of std::set are that its iterators are stable (deleting or 1364 inserting an element from the set does not affect iterators or pointers to other 1365 elements) and that iteration over the set is guaranteed to be in sorted order. 1366 If the elements in the set are large, then the relative overhead of the pointers 1367 and malloc traffic is not a big deal, but if the elements of the set are small, 1368 std::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 1379 a set-like container along with a <a href="#ds_sequential">Sequential 1380 Container</a>. The important property 1381 that this provides is efficient insertion with uniquing (duplicate elements are 1382 ignored) with iteration support. It implements this by inserting elements into 1383 both a set-like container and the sequential container, using the set-like 1384 container 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 1388 iteration is guaranteed to match the order of insertion into the SetVector. 1389 This property is really important for things like sets of pointers. Because 1390 pointer values are non-deterministic (e.g. vary across runs of the program on 1391 different machines), iterating over the pointers in the set will 1392 not be in a well-defined order.</p> 1393 1394 <p> 1395 The drawback of SetVector is that it requires twice as much space as a normal 1396 set and has the sum of constant factors from the set-like container and the 1397 sequential container that it uses. Use it *only* if you need to iterate over 1398 the elements in a deterministic order. SetVector is also expensive to delete 1399 elements out of (linear time), unless you use it's "pop_back" method, which is 1400 faster. 1401 </p> 1402 1403 <p>SetVector is an adapter class that defaults to using std::vector and std::set 1404 for the underlying containers, so it is quite expensive. However, 1405 <tt>"llvm/ADT/SetVector.h"</tt> also provides a SmallSetVector class, which 1406 defaults to using a SmallVector and SmallSet of a specified size. If you use 1407 this, and if your sets are dynamically smaller than N, you will save a lot of 1408 heap 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> 1420 UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it 1421 retains a unique ID for each element inserted into the set. It internally 1422 contains a map and a vector, and it assigns a unique ID for each value inserted 1423 into the set.</p> 1424 1425 <p>UniqueVector is very expensive: its cost is the sum of the cost of 1426 maintaining both the map and vector, it has high complexity, high constant 1427 factors, 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> 1440 The 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 1442 never 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 1447 duplicates, but has all the drawbacks of std::set. A sorted vector (where you 1448 don't delete duplicate entries) or some other approach is almost always 1449 better.</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> 1461 Map-like containers are useful when you want to associate data to a key. As 1462 usual, 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> 1472 If your usage pattern follows a strict insert-then-query approach, you can 1473 trivially use the same approach as <a href="#dss_sortedvectorset">sorted vectors 1474 for 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 1476 the key, not both the key and value. This yields the same advantages as sorted 1477 vectors 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> 1489 Strings are commonly used as keys in maps, and they are difficult to support 1490 efficiently: they are variable length, inefficient to hash and compare when 1491 long, expensive to copy, etc. StringMap is a specialized container designed to 1492 cope with these issues. It supports mapping an arbitrary range of bytes to an 1493 arbitrary other object.</p> 1494 1495 <p>The StringMap implementation uses a quadratically-probed hash table, where 1496 the buckets store a pointer to the heap allocated entries (and some other 1497 stuff). The entries in the map must be heap allocated because the strings are 1498 variable length. The string data (key) and the element object (value) are 1499 stored in the same allocation with the string data immediately after the element 1500 object. This container guarantees the "<tt>(char*)(&Value+1)</tt>" points 1501 to the key string for a value.</p> 1502 1503 <p>The StringMap is very fast for several reasons: quadratic probing is very 1504 cache efficient for lookups, the hash value of strings in buckets is not 1505 recomputed when looking up an element, StringMap rarely has to touch the 1506 memory for unrelated objects when looking up a value (even when hash collisions 1507 happen), hash table growth does not recompute the hash values for strings 1508 already 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 1512 copies 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> 1522 IndexedMap is a specialized container for mapping small dense integers (or 1523 values that can be mapped to small dense integers) to some other type. It is 1524 internally implemented as a vector with a mapping function that maps the keys to 1525 the dense integer range. 1526 </p> 1527 1528 <p> 1529 This is useful for cases like virtual registers in the LLVM code generator: they 1530 have a dense mapping that is offset by a compile-time constant (the first 1531 virtual 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> 1543 DenseMap is a simple quadratically probed hash table. It excels at supporting 1544 small keys and values: it uses a single allocation to hold all of the pairs that 1545 are currently inserted in the map. DenseMap is a great way to map pointers to 1546 pointers, or map other small types to each other. 1547 </p> 1548 1549 <p> 1550 There are several aspects of DenseMap that you should be aware of, however. The 1551 iterators in a densemap are invalidated whenever an insertion occurs, unlike 1552 map. Also, because DenseMap allocates space for a large number of key/value 1553 pairs (it starts with 64 by default), it will waste a lot of space if your keys 1554 or values are large. Finally, you must implement a partial specialization of 1555 DenseMapInfo for the key that you want, if it isn't already supported. This 1556 is required to tell DenseMap about two special marker values (which can never be 1557 inserted 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> 1569 ValueMap is a wrapper around a <a href="#dss_densemap">DenseMap</a> mapping 1570 Value*s (or subclasses) to another type. When a Value is deleted or RAUW'ed, 1571 ValueMap will update itself so the new version of the key is mapped to the same 1572 value, just as if the key were a WeakVH. You can configure exactly how this 1573 happens, and what else happens on these two events, by passing 1574 a <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 1586 intervals instead of single keys, and it will automatically coalesce adjacent 1587 intervals. When then map only contains a few intervals, they are stored in the 1588 map object itself to avoid allocations.</p> 1589 1590 <p> The IntervalMap iterators are quite big, so they should not be passed around 1591 as 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> 1603 std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses 1604 a single allocation per pair inserted into the map, it offers log(n) lookup with 1605 an extremely large constant factor, imposes a space penalty of 3 pointers per 1606 pair in the map, etc.</p> 1607 1608 <p>std::map is most useful when your keys or values are very large, if you need 1609 to iterate over the collection in sorted order, or if you need stable iterators 1610 into the map (i.e. they don't get invalidated if an insertion or deletion of 1611 another 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 1623 small integers. Initially, each integer in the range 0..n-1 has its own 1624 equivalence class. Classes can be joined by passing two class representatives to 1625 the join(a, b) method. Two integers are in the same class when findLeader() 1626 returns the same representative.</p> 1627 1628 <p>Once all equivalence classes are formed, the map can be compressed so each 1629 integer 0..n-1 maps to an equivalence class number in the range 0..m-1, where m 1630 is the total number of equivalence classes. The map must be uncompressed before 1631 it 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> 1643 The 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 1645 never 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 1649 all the drawbacks of std::map. A sorted vector or some other approach is almost 1650 always 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> 1664 TODO: const char* vs stringref vs smallstring vs std::string. Describe twine, 1665 xref 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 1677 choosing 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 1681 implementation in many common compilers (e.g. commonly available versions of 1682 GCC) is extremely inefficient and 2) the C++ standards committee is likely to 1683 deprecate this container and/or change it significantly somehow. In any case, 1684 please 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. 1693 It supports individual bit setting/testing, as well as set operations. The set 1694 operations take time O(size of bitvector), but operations are performed one word 1695 at a time, instead of one bit at a time. This makes the BitVector very fast for 1696 set operations compared to other containers. Use the BitVector when you expect 1697 the 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 1708 it is optimized for the case where only a small number of bits, less than 1709 25 or so, are needed. It also transparently supports larger bit counts, but 1710 slightly less efficiently than a plain BitVector, so SmallBitVector should 1711 only be used when larger counts are rare. 1712 </p> 1713 1714 <p> 1715 At this time, SmallBitVector does not support set operations (and, or, xor), 1716 and 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 1727 difference: Only the bits that are set, are stored. This makes the 1728 SparseBitVector much more space efficient than BitVector when the set is sparse, 1729 as well as making set operations O(number of set bits) instead of O(size of 1730 universe). The downside to the SparseBitVector is that setting and testing of random bits is O(N), and on large SparseBitVectors, this can be slower than BitVector. In our implementation, setting or testing bits in sorted order 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 1748 LLVM code. This is meant to give examples of common idioms used, showing the 1749 practical side of LLVM transformations. <p> Because this is a "how-to" section, 1750 you 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 1752 and 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 1763 be traversed. Following the example of the C++ standard template library, the 1764 techniques used to traverse these various data structures are all basically the 1765 same. For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or 1766 method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt> 1767 function returns an iterator pointing to one past the last valid element of the 1768 sequence, and there is some <tt>XXXiterator</tt> data type that is common 1769 between the two operations.</p> 1770 1771 <p>Because the pattern for iteration is common across many different aspects of 1772 the program representation, the standard template library algorithms may be used 1773 on them, and it is easier to remember how to iterate. First we show a few common 1774 examples of the data structures that need to be traversed. Other data 1775 structures 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 1787 transform 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 1789 the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>. The following is 1790 an 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> 1796 for (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 1805 invoking member functions of the <tt>Instruction</tt> class. This is 1806 because the indirection operator is overloaded for the iterator 1807 classes. In the above code, the expression <tt>i->size()</tt> is 1808 exactly 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 1822 easy 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 1824 a <tt>BasicBlock</tt>:</p> 1825 1826 <div class="doc_code"> 1827 <pre> 1828 // <i>blk is a pointer to a BasicBlock instance</i> 1829 for (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 1838 anything you'll care about, you could have just invoked the print routine on the 1839 basic 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 1855 href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>, 1856 and then instantiate <tt>InstIterator</tt>s explicitly in your code. Here's a 1857 small 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> 1864 for (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 1870 work list with its initial contents. For example, if you wanted to 1871 initialize a work list to contain all instructions in a <tt>Function</tt> 1872 F, all you would need to do is something like:</p> 1873 1874 <div class="doc_code"> 1875 <pre> 1876 std::set<Instruction*> worklist; 1877 // or better yet, SmallPtrSet<Instruction*, 64> worklist; 1878 1879 for (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 1898 instance when all you've got at hand is an iterator. Well, extracting 1899 a reference or a pointer from an iterator is very straight-forward. 1900 Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and <tt>j</tt> 1901 is a <tt>BasicBlock::const_iterator</tt>:</p> 1902 1903 <div class="doc_code"> 1904 <pre> 1905 Instruction& inst = *i; // <i>Grab reference to instruction reference</i> 1906 Instruction* pinst = &*i; // <i>Grab pointer to instruction reference</i> 1907 const Instruction& inst = *j; 1908 </pre> 1909 </div> 1910 1911 <p>However, the iterators you'll be working with in the LLVM framework are 1912 special: they will automatically convert to a ptr-to-instance type whenever they 1913 need to. Instead of dereferencing the iterator and then taking the address of 1914 the result, you can simply assign the iterator to the proper pointer type and 1915 you 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 1917 the last line of the last example,</p> 1918 1919 <div class="doc_code"> 1920 <pre> 1921 Instruction *pinst = &*i; 1922 </pre> 1923 </div> 1924 1925 <p>is semantically equivalent to</p> 1926 1927 <div class="doc_code"> 1928 <pre> 1929 Instruction *pinst = i; 1930 </pre> 1931 </div> 1932 1933 <p>It's also possible to turn a class pointer into the corresponding iterator, 1934 and this is a constant time operation (very efficient). The following code 1935 snippet illustrates use of the conversion constructors provided by LLVM 1936 iterators. By using these, you can explicitly grab the iterator of something 1937 without actually obtaining it via iteration over some structure:</p> 1938 1939 <div class="doc_code"> 1940 <pre> 1941 void 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 1950 these iterators from conforming to standard iterator conventions, and thus 1951 from being usable with standard algorithms and containers. For example, they 1952 prevent the following code, where <tt>B</tt> is a <tt>BasicBlock</tt>, 1953 from 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, 1962 and <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 1975 locations in the entire module (that is, across every <tt>Function</tt>) where a 1976 certain function (i.e., some <tt>Function</tt>*) is already in scope. As you'll 1977 learn later, you may want to use an <tt>InstVisitor</tt> to accomplish this in a 1978 much more straight-forward manner, but this example will allow us to explore how 1979 you'd do it if you didn't have <tt>InstVisitor</tt> around. In pseudo-code, this 1980 is what we want to do:</p> 1981 1982 <div class="doc_code"> 1983 <pre> 1984 initialize callCounter to zero 1985 for 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 1995 override the <tt>runOnFunction</tt> method):</p> 1996 1997 <div class="doc_code"> 1998 <pre> 1999 Function* targetFunc = ...; 2000 2001 class 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 2036 that it did not deal with call sites generated by 'invoke' instructions. In 2037 this, 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 2039 most-specific common base class is <tt>Instruction</tt>, which includes lots of 2040 less closely-related things. For these cases, LLVM provides a handy wrapper 2041 class called <a 2042 href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>. 2043 It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some 2044 methods 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 2048 reference and it should not be dynamically allocated or deallocated using 2049 <tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable, 2050 assignable and constructable, with costs equivalents to that of a bare pointer. 2051 If 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 2063 href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to 2064 determine 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. 2066 For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a 2067 particular 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 2069 of <tt>F</tt>:</p> 2070 2071 <div class="doc_code"> 2072 <pre> 2073 Function *F = ...; 2074 2075 for (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 2084 operation. Instead of performing <tt>*i</tt> above several times, consider 2085 doing 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 2088 href="/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 2092 all of the values that a particular instruction uses (that is, the operands of 2093 the particular <tt>Instruction</tt>):</p> 2094 2095 <div class="doc_code"> 2096 <pre> 2097 Instruction *pi = ...; 2098 2099 for (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 2107 mutation free algorithms (such as analyses, etc.). For this purpose above 2108 iterators come in constant flavors as <tt>Value::const_use_iterator</tt> 2109 and <tt>Value::const_op_iterator</tt>. They automatically arise when 2110 calling <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 & 2119 successors of blocks</a> 2120 </h4> 2121 2122 <div> 2123 2124 <p>Iterating over the predecessors and successors of a block is quite easy 2125 with the routines defined in <tt>"llvm/Support/CFG.h"</tt>. Just use code like 2126 this to iterate over all predecessors of BB:</p> 2127 2128 <div class="doc_code"> 2129 <pre> 2130 #include "llvm/Support/CFG.h" 2131 BasicBlock *BB = ...; 2132 2133 for (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 2141 succ_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 2155 infrastructure that are worth knowing about. When performing 2156 transformations, it's fairly common to manipulate the contents of basic 2157 blocks. This section describes some of the common methods for doing so 2158 and 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 2171 constructor for the kind of instruction to instantiate and provide the necessary 2172 parameters. 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> 2177 AllocaInst* ai = new AllocaInst(Type::Int32Ty); 2178 </pre> 2179 </div> 2180 2181 <p>will create an <tt>AllocaInst</tt> instance that represents the allocation of 2182 one integer in the current stack frame, at run time. Each <tt>Instruction</tt> 2183 subclass is likely to have varying default parameters which change the semantics 2184 of the instruction, so refer to the <a 2185 href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of 2186 Instruction</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 2191 this facilitates the debugging of your transformations. If you end up looking 2192 at generated LLVM machine code, you definitely want to have logical names 2193 associated with the results of instructions! By supplying a value for the 2194 <tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you 2195 associate a logical name with the result of the instruction's execution at 2196 run time. For example, say that I'm writing a transformation that dynamically 2197 allocates space for an integer on the stack, and that integer is going to be 2198 used 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> 2205 AllocaInst* 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 2210 execution 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> 2215 into 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> 2226 BasicBlock *pb = ...; 2227 Instruction *pi = ...; 2228 Instruction *newInst = new Instruction(...); 2229 2230 pb->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> 2242 BasicBlock *pb = ...; 2243 Instruction *newInst = new Instruction(...); 2244 2245 pb->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> 2253 BasicBlock *pb = ...; 2254 Instruction *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> 2271 Instruction *pi = ...; 2272 Instruction *newInst = new Instruction(...); 2273 2274 pi->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> 2290 Instruction* pi = ...; 2291 Instruction* 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 2310 call the instruction's eraseFromParent() method. For example:</p> 2311 2312 <div class="doc_code"> 2313 <pre> 2314 <a href="#Instruction">Instruction</a> *I = .. ; 2315 I->eraseFromParent(); 2316 </pre> 2317 </div> 2318 2319 <p>This unlinks the instruction from its containing basic block and deletes 2320 it. If you'd just like to unlink the instruction from its containing basic 2321 block 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>" 2336 permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt> 2337 and <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> 2352 AllocaInst* instToReplace = ...; 2353 BasicBlock::iterator ii(instToReplace); 2354 2355 ReplaceInstWithValue(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> 2369 AllocaInst* instToReplace = ...; 2370 BasicBlock::iterator ii(instToReplace); 2371 2372 ReplaceInstWithInst(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 2381 doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a> 2382 and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more 2383 information.</p> 2384 2385 <!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out: 2386 include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with: 2387 ReplaceInstWithValue, 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 2399 Instruction. 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 2407 GV->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 2423 statically, you can use <tt>TypeBuilder<...>::get()</tt>, defined 2424 in <tt>llvm/Support/TypeBuilder.h</tt>, to retrieve them. <tt>TypeBuilder</tt> 2425 has two forms depending on whether you're building types for cross-compilation 2426 or native library use. <tt>TypeBuilder<T, true></tt> requires 2427 that <tt>T</tt> be independent of the host environment, meaning that it's built 2428 out of types from 2429 the <a href="/doxygen/namespacellvm_1_1types.html"><tt>llvm::types</tt></a> 2430 namespace and pointers, functions, arrays, etc. built of 2431 those. <tt>TypeBuilder<T, false></tt> additionally allows native C types 2432 whose size may depend on the host compiler. For example,</p> 2433 2434 <div class="doc_code"> 2435 <pre> 2436 FunctionType *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> 2444 std::vector<const Type*> params; 2445 params.push_back(PointerType::getUnqual(Type::Int32Ty)); 2446 FunctionType *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 2451 comment</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> 2465 This section describes the interaction of the LLVM APIs with multithreading, 2466 both on the part of client applications, and in the JIT, in the hosted 2467 application. 2468 </p> 2469 2470 <p> 2471 Note that LLVM's support for multithreading is still relatively young. Up 2472 through version 2.5, the execution of threaded hosted applications was 2473 supported, but not threaded client access to the APIs. While this use case is 2474 now supported, clients <em>must</em> adhere to the guidelines specified below to 2475 ensure proper operation in multithreaded mode. 2476 </p> 2477 2478 <p> 2479 Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic 2480 intrinsics in order to support threaded operation. If you need a 2481 multhreading-capable LLVM on a platform without a suitably modern system 2482 compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and 2483 using the resultant compiler to build a copy of LLVM with multithreading 2484 support. 2485 </p> 2486 2487 <!-- ======================================================================= --> 2488 <h3> 2489 <a name="startmultithreaded">Entering and Exiting Multithreaded Mode</a> 2490 </h3> 2491 2492 <div> 2493 2494 <p> 2495 In order to properly protect its internal data structures while avoiding 2496 excessive locking overhead in the single-threaded case, the LLVM must intialize 2497 certain data structures necessary to provide guards around its internals. To do 2498 so, the client program must invoke <tt>llvm_start_multithreaded()</tt> before 2499 making any concurrent LLVM API calls. To subsequently tear down these 2500 structures, use the <tt>llvm_stop_multithreaded()</tt> call. You can also use 2501 the <tt>llvm_is_multithreaded()</tt> call to check the status of multithreaded 2502 mode. 2503 </p> 2504 2505 <p> 2506 Note that both of these calls must be made <em>in isolation</em>. That is to 2507 say that no other LLVM API calls may be executing at any time during the 2508 execution 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> 2513 The return value of <tt>llvm_start_multithreaded()</tt> indicates the success or 2514 failure of the initialization. Failure typically indicates that your copy of 2515 LLVM was built without multithreading support, typically because GCC atomic 2516 intrinsics were not found in your system compiler. In this case, the LLVM API 2517 will not be safe for concurrent calls. However, it <em>will</em> be safe for 2518 hosting threaded applications in the JIT, though <a href="#jitthreading">care 2519 must be taken</a> to ensure that side exits and the like do not accidentally 2520 result 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> 2531 When you are done using the LLVM APIs, you should call <tt>llvm_shutdown()</tt> 2532 to deallocate memory used for internal structures. This will also invoke 2533 <tt>llvm_stop_multithreaded()</tt> if LLVM is operating in multithreaded mode. 2534 As such, <tt>llvm_shutdown()</tt> requires the same isolation guarantees as 2535 <tt>llvm_stop_multithreaded()</tt>. 2536 </p> 2537 2538 <p> 2539 Note 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 2541 destructor. 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 2552 initialization of static resources, such as the global type tables. Before the 2553 invocation of <tt>llvm_shutdown()</tt>, it implements a simple lazy 2554 initialization scheme. Once <tt>llvm_start_multithreaded()</tt> returns, 2555 however, it uses double-checked locking to implement thread-safe lazy 2556 initialization. 2557 </p> 2558 2559 <p> 2560 Note 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> 2566 The <tt>llvm_acquire_global_lock()</tt> and <tt>llvm_release_global_lock</tt> 2567 APIs provide access to the global lock used to implement the double-checked 2568 locking for lazy initialization. These should only be used internally to LLVM, 2569 and 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 2581 to operate multiple, isolated instances of LLVM concurrently within the same 2582 address space. For instance, in a hypothetical compile-server, the compilation 2583 of an individual translation unit is conceptually independent from all the 2584 others, and it would be desirable to be able to compile incoming translation 2585 units concurrently on independent server threads. Fortunately, 2586 <tt>LLVMContext</tt> exists to enable just this kind of scenario! 2587 </p> 2588 2589 <p> 2590 Conceptually, <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.) 2592 in LLVM's in-memory IR belongs to an <tt>LLVMContext</tt>. Entities in 2593 different contexts <em>cannot</em> interact with each other: <tt>Module</tt>s in 2594 different contexts cannot be linked together, <tt>Function</tt>s cannot be added 2595 to <tt>Module</tt>s in different contexts, etc. What this means is that is is 2596 safe to compile on multiple threads simultaneously, as long as no two threads 2597 operate on entities within the same context. 2598 </p> 2599 2600 <p> 2601 In 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. 2603 Because every <tt>Type</tt> carries a reference to its owning context, most 2604 other entities can determine what context they belong to by looking at their 2605 own <tt>Type</tt>. If you are adding new entities to LLVM IR, please try to 2606 maintain this interface design. 2607 </p> 2608 2609 <p> 2610 For clients that do <em>not</em> require the benefits of isolation, LLVM 2611 provides a convenience API <tt>getGlobalContext()</tt>. This returns a global, 2612 lazily initialized <tt>LLVMContext</tt> that may be used in situations where 2613 isolation 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> 2624 LLVM's "eager" JIT compiler is safe to use in threaded programs. Multiple 2625 threads can call <tt>ExecutionEngine::getPointerToFunction()</tt> or 2626 <tt>ExecutionEngine::runFunction()</tt> concurrently, and multiple threads can 2627 run code output by the JIT concurrently. The user must still ensure that only 2628 one thread accesses IR in a given <tt>LLVMContext</tt> while another thread 2629 might be modifying it. One way to do that is to always hold the JIT lock while 2630 accessing IR outside the JIT (the JIT <em>modifies</em> the IR by adding 2631 <tt>CallbackVH</tt>s). Another way is to only 2632 call <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 2638 updating call sites after a function is lazily-jitted. It's still possible to 2639 use the lazy JIT in a threaded program if you ensure that only one thread at a 2640 time can call any particular lazy stub and that the JIT lock guards any IR 2641 access, 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> 2655 This section describes some of the advanced or obscure API's that most clients 2656 do not need to be aware of. These API's tend manage the inner workings of the 2657 LLVM 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"> 2668 ValueSymbolTable</a></tt> class provides a symbol table that the <a 2669 href="#Function"><tt>Function</tt></a> and <a href="#Module"> 2670 <tt>Module</tt></a> classes use for naming value definitions. The symbol table 2671 can 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 2675 by most clients. It should only be used when iteration over the symbol table 2676 names themselves are required, which is very special purpose. Note that not 2677 all LLVM 2678 <tt><a href="#Value">Value</a></tt>s have names, and those without names (i.e. they have 2679 an empty name) do not exist in the symbol table. 2680 </p> 2681 2682 <p>Symbol tables support iteration over the values in the symbol 2683 table with <tt>begin/end/iterator</tt> and supports querying to see if a 2684 specific name is in the symbol table (with <tt>lookup</tt>). The 2685 <tt>ValueSymbolTable</tt> class exposes no public mutator methods, instead, 2686 simply call <tt>setName</tt> on a value, which will autoinsert it into the 2687 appropriate 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"> 2700 User</a></tt> class provides a basis for expressing the ownership of <tt>User</tt> 2701 towards other <tt><a href="http://llvm.org/doxygen/classllvm_1_1Value.html"> 2702 Value</a></tt>s. The <tt><a href="http://llvm.org/doxygen/classllvm_1_1Use.html"> 2703 Use</a></tt> helper class is employed to do the bookkeeping and to facilitate <i>O(1)</i> 2704 addition 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> 2715 A subclass of <tt>User</tt> can choose between incorporating its <tt>Use</tt> objects 2716 or 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 2718 that the <tt>Use</tt> objects belonging to the same <tt>User</tt> form a contiguous array. 2719 </p> 2720 2721 <p> 2722 We have 2 different layouts in the <tt>User</tt> (sub)classes: 2723 <ul> 2724 <li><p>Layout a) 2725 The <tt>Use</tt> object(s) are inside (resp. at fixed offset) of the <tt>User</tt> 2726 object and there are a fixed number of them.</p> 2727 2728 <li><p>Layout b) 2729 The <tt>Use</tt> object(s) are referenced by a pointer to an 2730 array from the <tt>User</tt> object and there may be a variable 2731 number of them.</p> 2732 </ul> 2733 <p> 2734 As of v2.4 each layout still possesses a direct pointer to the 2735 start of the array of <tt>Use</tt>s. Though not mandatory for layout a), 2736 we stick to this redundancy for the sake of simplicity. 2737 The <tt>User</tt> object also stores the number of <tt>Use</tt> objects it 2738 has. (Theoretically this information can also be calculated 2739 given the scheme presented below.)</p> 2740 <p> 2741 Special forms of allocation operators (<tt>operator new</tt>) 2742 enforce 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> 2777 Since the <tt>Use</tt> objects are deprived of the direct (back)pointer to 2778 their <tt>User</tt> objects, there must be a fast and exact method to 2779 recover it. This is accomplished by the following scheme:</p> 2780 2781 A bit-encoding in the 2 LSBits (least significant bits) of the <tt>Use::Prev</tt> allows to find the 2782 start 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> 2790 Given a <tt>Use*</tt>, all we have to do is to walk till we get 2791 a stop and we either have a <tt>User</tt> immediately behind or 2792 we have to walk to the next stop picking up digits 2793 and 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> 2806 Only the significant number of bits need to be stored between the 2807 stops, so that the <i>worst case is 20 memory accesses</i> when there are 2808 1000 <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> 2819 The 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> 2843 Printing <test> gives: <tt>"1s100000s11010s10100s1111s1010s110s11s1S"</tt></p> 2844 <p> 2845 The reverse algorithm computes the length of the string just by examining 2846 a 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> 2862 Now, as expected, printing <pref test> gives <tt>40</tt>.</p> 2863 <p> 2864 We 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> 2877 As expected <quickCheck identityProp> gives:</p> 2878 2879 <pre> 2880 *Main> quickCheck identityProp 2881 OK, passed 100 tests. 2882 </pre> 2883 <p> 2884 Let'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> 2894 And here is the result of <deepCheck identityProp>:</p> 2895 2896 <pre> 2897 *Main> deepCheck identityProp 2898 OK, 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> 2911 To maintain the invariant that the 2 LSBits of each <tt>Use**</tt> in <tt>Use</tt> 2912 never change after being set up, setters of <tt>Use::Prev</tt> must re-tag the 2913 new <tt>Use**</tt> on every modification. Accordingly getters must strip the 2914 tag bits.</p> 2915 <p> 2916 For layout b) instead of the <tt>User</tt> we find a pointer (<tt>User*</tt> with LSBit set). 2917 Following this pointer brings us to the <tt>User</tt>. A portable trick ensures 2918 that the first bytes of <tt>User</tt> (if interpreted as a pointer) never has 2919 the 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 2939 being inspected or transformed. The core LLVM classes are defined in 2940 header files in the <tt>include/llvm/</tt> directory, and implemented in 2941 the <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 3051 href="/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 3055 programs. An LLVM module is effectively either a translation unit of the 3056 original program or a combination of several translation units merged by the 3057 linker. The <tt>Module</tt> class keeps track of a list of <a 3058 href="#Function"><tt>Function</tt></a>s, a list of <a 3059 href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a 3060 href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few 3061 helpful 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 3075 provide 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> 3178 doxygen 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 3181 base. It represents a typed value that may be used (among other things) as an 3182 operand to an instruction. There are many different types of <tt>Value</tt>s, 3183 such as <a href="#Constant"><tt>Constant</tt></a>s,<a 3184 href="#Argument"><tt>Argument</tt></a>s. Even <a 3185 href="#Instruction"><tt>Instruction</tt></a>s and <a 3186 href="#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 3189 for a program. For example, an incoming argument to a function (represented 3190 with an instance of the <a href="#Argument">Argument</a> class) is "used" by 3191 every instruction in the function that references the argument. To keep track 3192 of this relationship, the <tt>Value</tt> class keeps a list of all of the <a 3193 href="#User"><tt>User</tt></a>s that is using it (the <a 3194 href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM 3195 graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents 3196 def-use information in the program, and is accessible through the <tt>use_</tt>* 3197 methods, shown below.</p> 3198 3199 <p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed, 3200 and this <a href="#Type">Type</a> is available through the <tt>getType()</tt> 3201 method. 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> 3211 that 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, 3213 debugging printouts), they should not be used to keep track of values or map 3214 between 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 3218 variable and the operation that produces it. Because of this, any reference to 3219 the value produced by an instruction (or the value available as an incoming 3220 argument, for example) is represented as a direct pointer to the instance of 3221 the class that 3222 represents this value. Although this may take some getting used to, it 3223 simplifies 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 3234 use-list<br> 3235 <tt>Value::const_use_iterator</tt> - Typedef for const_iterator over 3236 the use-list<br> 3237 <tt>unsigned use_size()</tt> - Returns the number of users of the 3238 value.<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 3241 the use-list.<br> 3242 <tt>use_iterator use_end()</tt> - Get an iterator to the end of the 3243 use-list.<br> 3244 <tt><a href="#User">User</a> *use_back()</tt> - Returns the last 3245 element in the list. 3246 <p> These methods are the interface to access the def-use 3247 information in LLVM. As with all other iterators in LLVM, the naming 3248 conventions 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>, 3257 be 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> 3269 Inst->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> 3288 doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br> 3289 Superclass: <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 3292 refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands" 3293 that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is 3294 referring 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 3298 href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static 3299 Single Assignment (SSA) form, there can only be one definition referred to, 3300 allowing this direct connection. This connection provides the use-def 3301 information 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 3311 an 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 3317 convenient form for direct access.</p></li> 3318 3319 <li><tt>User::op_iterator</tt> - Typedef for iterator over the operand 3320 list<br> 3321 <tt>op_iterator op_begin()</tt> - Get an iterator to the start of 3322 the operand list.<br> 3323 <tt>op_iterator op_end()</tt> - Get an iterator to the end of the 3324 operand list. 3325 <p> Together, these methods make up the iterator based interface to 3326 the 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 3341 href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br> 3342 doxygen info: <a href="/doxygen/classllvm_1_1Instruction.html">Instruction Class</a><br> 3343 Superclasses: <a href="#User"><tt>User</tt></a>, <a 3344 href="#Value"><tt>Value</tt></a></p> 3345 3346 <p>The <tt>Instruction</tt> class is the common base class for all LLVM 3347 instructions. It provides only a few methods, but is a very commonly used 3348 class. The primary data tracked by the <tt>Instruction</tt> class itself is the 3349 opcode (instruction type) and the parent <a 3350 href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded 3351 into. 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 3355 href="#User"><tt>User</tt></a> class, its operands can be accessed in the same 3356 way 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 3359 the <tt>Instruction</tt> class is the <tt>llvm/Instruction.def</tt> file. This 3360 file contains some meta-data about the various different types of instructions 3361 in 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 3363 concrete sub-classes of <tt>Instruction</tt> that implement the instruction (for 3364 example <tt><a href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a 3365 href="#CmpInst">CmpInst</a></tt>). Unfortunately, the use of macros in 3366 this 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 3405 this <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 3413 in 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>), 3415 and 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 3430 is subclassed by ConstantInt, ConstantArray, etc. for representing 3431 the various types of Constants. <a href="#GlobalValue">GlobalValue</a> is also 3432 a 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 3495 href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br> 3496 doxygen info: <a href="/doxygen/classllvm_1_1GlobalValue.html">GlobalValue 3497 Class</a><br> 3498 Superclasses: <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 3502 href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are 3503 visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s. 3504 Because they are visible at global scope, they are also subject to linking with 3505 other globals defined in different translation units. To control the linking 3506 process, <tt>GlobalValue</tt>s know their linkage rules. Specifically, 3507 <tt>GlobalValue</tt>s know whether they have internal or external linkage, as 3508 defined 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 3512 unit, and does not participate in linking. If it has external linkage, it is 3513 visible to external code, and does participate in linking. In addition to 3514 linkage information, <tt>GlobalValue</tt>s keep track of which <a 3515 href="#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 3518 by their <b>address</b>. As such, the <a href="#Type"><tt>Type</tt></a> of a 3519 global is always a pointer to its contents. It is important to remember this 3520 when using the <tt>GetElementPtrInst</tt> instruction because this pointer must 3521 be dereferenced first. For example, if you have a <tt>GlobalVariable</tt> (a 3522 subclass of <tt>GlobalValue)</tt> that is an array of 24 ints, type <tt>[24 x 3523 i32]</tt>, then the <tt>GlobalVariable</tt> is a pointer to that array. Although 3524 the 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 3527 is <tt>i32.</tt> Because of this, accessing a global value requires you to 3528 dereference the pointer with <tt>GetElementPtrInst</tt> first, then its elements 3529 can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM 3530 Language 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 3550 GlobalValue 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 3565 href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen 3566 info: <a href="/doxygen/classllvm_1_1Function.html">Function Class</a><br> 3567 Superclasses: <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 3573 actually one of the more complex classes in the LLVM hierarchy because it must 3574 keep track of a large amount of data. The <tt>Function</tt> class keeps track 3575 of 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 3580 commonly used part of <tt>Function</tt> objects. The list imposes an implicit 3581 ordering of the blocks in the function, which indicate how the code will be 3582 laid out by the backend. Additionally, the first <a 3583 href="#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 3585 block. There are no implicit exit nodes, and in fact there may be multiple exit 3586 nodes from a single <tt>Function</tt>. If the <a 3587 href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that 3588 the <tt>Function</tt> is actually a function declaration: the actual body of the 3589 function 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 3593 href="#Argument"><tt>Argument</tt></a>s that the function receives. This 3594 container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a> 3595 nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for 3596 the <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 3599 LLVM feature that is only used when you have to look up a value by name. Aside 3600 from that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used 3601 internally to make sure that there are not conflicts between the names of <a 3602 href="#Instruction"><tt>Instruction</tt></a>s, <a 3603 href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a 3604 href="#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> 3607 and therefore also a <a href="#Constant">Constant</a>. The value of the function 3608 is 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 3657 iterator<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 3705 href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt> 3706 <br> 3707 doxygen info: <a href="/doxygen/classllvm_1_1GlobalVariable.html">GlobalVariable 3708 Class</a><br> 3709 Superclasses: <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 3716 subclasses of <a href="#GlobalValue"><tt>GlobalValue</tt></a>, and as such are 3717 always 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 3720 variables may have an initial value (which must be a 3721 <a href="#Constant"><tt>Constant</tt></a>), and if they have an initializer, 3722 they may be marked as "constant" themselves (indicating that their contents 3723 never 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 3780 href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt><br> 3781 doxygen info: <a href="/doxygen/classllvm_1_1BasicBlock.html">BasicBlock 3782 Class</a><br> 3783 Superclass: <a href="#Value"><tt>Value</tt></a></p> 3784 3785 <p>This class represents a single entry single exit section of the code, 3786 commonly known as a basic block by the compiler community. The 3787 <tt>BasicBlock</tt> class maintains a list of <a 3788 href="#Instruction"><tt>Instruction</tt></a>s, which form the body of the block. 3789 Matching the language definition, the last element of this list of instructions 3790 is always a terminator instruction (a subclass of the <a 3791 href="#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 3795 href="#Function"><tt>Function</tt></a> that it is embedded into.</p> 3796 3797 <p>Note that <tt>BasicBlock</tt>s themselves are <a 3798 href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions 3799 like 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 3816 insertion into a function. The constructor optionally takes a name for the new 3817 block, and a <a href="#Function"><tt>Function</tt></a> to insert it into. If 3818 the <tt>Parent</tt> parameter is specified, the new <tt>BasicBlock</tt> is 3819 automatically inserted at the end of the specified <a 3820 href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be 3821 manually 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> 3827 STL-style functions for accessing the instruction list. 3828 3829 <p>These methods and typedefs are forwarding functions that have the same 3830 semantics as the standard library methods of the same names. These methods 3831 expose the underlying instruction list of a basic block in a way that is easy to 3832 manipulate. To get the full complement of container operations (including 3833 operations to update the list), you must use the <tt>getInstList()</tt> 3834 method.</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 3839 holds the Instructions. This method must be used when there isn't a forwarding 3840 function in the <tt>BasicBlock</tt> class for the operation that you would like 3841 to perform. Because there are no forwarding functions for "updating" 3842 operations, 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 3848 embedded 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 3853 the <tt>BasicBlock</tt>. If there is no terminator instruction, or if the last 3854 instruction in the block is not a terminator, then a null pointer is 3855 returned.</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 3871 arguments to a function. A Function maintains a list of its formal 3872 arguments. 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 (a] cs.uiuc.edu">Dinakar Dhurjati</a> and 3887 <a href="mailto:sabre (a] 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
