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