brintos / llvm-project-archived public Read only

1========================2LLVM Programmer's Manual3========================4 5.. contents::6   :local:7 8.. warning::9   This is always a work in progress.10 11.. _introduction:12 13Introduction14============15 16This document is meant to highlight some of the important classes and interfaces17available in the LLVM source-base.  This manual is not intended to explain what18LLVM is, how it works, and what LLVM code looks like.  It assumes that you know19the basics of LLVM and are interested in writing transformations or otherwise20analyzing or manipulating the code.21 22This document should get you oriented so that you can find your way in the23continuously growing source code that makes up the LLVM infrastructure.  Note24that this manual is not intended to serve as a replacement for reading the25source code, so if you think there should be a method in one of these classes to26do something, but it's not listed, check the source.  Links to the `doxygen27<https://llvm.org/doxygen/>`__ sources are provided to make this as easy as28possible.29 30The first section of this document describes general information that is useful31to know when working in the LLVM infrastructure, and the second describes the32Core LLVM classes.  In the future this manual will be extended with information33describing how to use extension libraries, such as dominator information, CFG34traversal routines, and useful utilities like the ``InstVisitor`` (`doxygen35<https://llvm.org/doxygen/InstVisitor_8h_source.html>`__) template.36 37.. _general:38 39General Information40===================41 42This section contains general information that is useful if you are working in43the LLVM source-base, but that isn't specific to any particular API.44 45.. _stl:46 47The C++ Standard Template Library48---------------------------------49 50LLVM makes heavy use of the C++ Standard Template Library (STL), perhaps much51more than you are used to, or have seen before.  Because of this, you might want52to do a little background reading in the techniques used and capabilities of the53library.  There are many good pages that discuss the STL, and several books on54the subject that you can get, so it will not be discussed in this document.55 56Here are some useful links:57 58#. `cppreference.com59   <https://en.cppreference.com/w/>`_ - an excellent60   reference for the STL and other parts of the standard C++ library.61 62#. `cplusplus.com63   <https://cplusplus.com/reference/>`_ - another excellent64   reference like the one above.65 66#. `C++ In a Nutshell <http://www.tempest-sw.com/cpp/>`_ - This is an O'Reilly67   book in the making.  It has a decent Standard Library Reference that rivals68   Dinkumware's, and is unfortunately no longer free since the book has been69   published.70 71#. `C++ Frequently Asked Questions <https://www.parashift.com/c++-faq-lite/>`_.72 73#. `Bjarne Stroustrup's C++ Page74   <https://www.stroustrup.com/C++.html>`_.75 76#. `Bruce Eckel's Thinking in C++, 2nd ed. Volume 2.77   (even better, get the book)78   <https://archive.org/details/TICPP2ndEdVolTwo>`_.79 80You are also encouraged to take a look at the :doc:`LLVM Coding Standards81<CodingStandards>` guide which focuses on how to write maintainable code more82than where to put your curly braces.83 84.. _resources:85 86Other useful references87-----------------------88 89#. `Using static and shared libraries across platforms90   <http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html>`_91 92.. _apis:93 94Important and useful LLVM APIs95==============================96 97Here we highlight some LLVM APIs that are generally useful and good to know98about when writing transformations.99 100.. _isa:101 102The ``isa<>``, ``cast<>`` and ``dyn_cast<>`` templates103------------------------------------------------------104 105The LLVM source-base makes extensive use of a custom form of RTTI.  These106templates have many similarities to the C++ ``dynamic_cast<>`` operator, but107they don't have some drawbacks (primarily stemming from the fact that108``dynamic_cast<>`` only works on classes that have a v-table).  Because they are109used so often, you must know what they do and how they work.  All of these110templates are defined in the ``llvm/Support/Casting.h`` (`doxygen111<https://llvm.org/doxygen/Casting_8h_source.html>`__) file (note that you very112rarely 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 to117  an instance of the specified class.  This can be very useful for constraint118  checking of various sorts (example below).119 120``cast<>``:121  The ``cast<>`` operator is a "checked cast" operation.  It converts a pointer122  or reference from a base class to a derived class, causing an assertion123  failure if it is not really an instance of the right type.  This should be124  used in cases where you have some information that makes you believe that125  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 see143  if the operand is of the specified type, and if so, returns a pointer to it144  (this operator does not work with references).  If the operand is not of the145  correct type, a null pointer is returned.  Thus, this works very much like146  the ``dynamic_cast<>`` operator in C++, and should be used in the same147  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 to157  ``isa<>`` and a call to ``cast<>`` into one statement, which is very158  convenient.159 160  Note that the ``dyn_cast<>`` operator, like C++'s ``dynamic_cast<>`` or Java's161  ``instanceof`` operator, can be abused.  In particular, you should not use big162  chained ``if/then/else`` blocks to check for lots of different variants of163  classes.  If you find yourself wanting to do this, it is much cleaner and more164  efficient to use the ``InstVisitor`` class to dispatch over the instruction165  type directly.166 167``isa_and_present<>``:168  The ``isa_and_present<>`` operator works just like the ``isa<>`` operator,169  except that it allows for a null pointer as an argument (which it then170  returns ``false``).  This can sometimes be useful, allowing you to combine several171  null checks into one.172 173``cast_if_present<>``:174  The ``cast_if_present<>`` operator works just like the ``cast<>`` operator,175  except that it allows for a null pointer as an argument (which it then176  propagates).  This can sometimes be useful, allowing you to combine several177  null checks into one.178 179``dyn_cast_if_present<>``:180  The ``dyn_cast_if_present<>`` operator works just like the ``dyn_cast<>``181  operator, except that it allows for a null pointer as an argument (which it182  then propagates).  This can sometimes be useful, allowing you to combine183  several null checks into one.184 185These five templates can be used with any classes, whether they have a v-table186or not.  If you want to add support for these templates, see the document187:doc:`How to set up LLVM-style RTTI for your class hierarchy188<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 several196important APIs which take strings.  Two important examples are the Value class197-- 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 may201have embedded null characters.  Therefore, they cannot simply take a ``const202char *``, and taking a ``const std::string&`` requires clients to perform a heap203allocation which is usually unnecessary.  Instead, many LLVM APIs use a204``StringRef`` or a ``const Twine&`` for passing strings efficiently.205 206.. _StringRef:207 208The ``StringRef`` class209^^^^^^^^^^^^^^^^^^^^^^^^^^^^210 211The ``StringRef`` data type represents a reference to a constant string (a212character array and a length) and supports the common operations available on213``std::string``, but does not require heap allocation.214 215It can be implicitly constructed using a C style null-terminated string, an216``std::string``, or explicitly with a character pointer and length.  For217example, the ``StringMap`` 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`` using233the ``str`` member function.  See ``llvm/ADT/StringRef.h`` (`doxygen234<https://llvm.org/doxygen/StringRef_8h_source.html>`__) for more235information.236 237You should rarely use the ``StringRef`` class directly. Because it contains238pointers to external memory, it is not generally safe to store an instance of the239class (unless you know that the external storage will not be freed).240``StringRef`` is small and pervasive enough in LLVM that it should always be241passed by value.242 243The ``Twine`` class244^^^^^^^^^^^^^^^^^^^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 another249instruction 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 `rope256<http://en.wikipedia.org/wiki/Rope_(computer_science)>`_ which points to257temporary (stack allocated) objects.  Twines can be implicitly constructed as258the result of the plus operator applied to strings (i.e., a C strings, an259``std::string``, or a ``StringRef``).  The twine delays the actual concatenation260of strings until it is actually required, at which point it can be efficiently261rendered directly into a character array.  This avoids unnecessary heap262allocation involved in constructing the temporary results of string263concatenation.  See ``llvm/ADT/Twine.h`` (`doxygen264<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 should268almost never be stored or mentioned directly.  They are intended solely for use269when defining a function which should be able to efficiently accept concatenated270strings.271 272.. _formatting_strings:273 274Formatting strings (the ``formatv`` function)275---------------------------------------------276While LLVM doesn't necessarily do a lot of string manipulation and parsing, it277does do a lot of string formatting.  From diagnostic messages, to llvm tool278outputs such as ``llvm-readobj`` to printing verbose disassembly listings and279LLDB runtime logging, the need for string formatting is pervasive.280 281The ``formatv`` is similar in spirit to ``printf``, but uses a different syntax282which borrows heavily from Python and C#.  Unlike ``printf`` it deduces the type283to be formatted at compile time, so it does not need a format specifier such as284``%d``.  This reduces the mental overhead of trying to construct portable format285strings, especially for platform-specific types like ``size_t`` or pointer types.286Unlike both ``printf`` and Python, it additionally fails to compile if LLVM does287not know how to format the type.  These two properties ensure that the function288is both safer and simpler to use than traditional formatting methods such as289the ``printf`` family of functions.290 291Simple formatting292^^^^^^^^^^^^^^^^^293 294A call to ``formatv`` involves a single **format string** consisting of 0 or more295**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 replacement299values.  Note that this means it is possible to reference the same parameter300multiple 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 format303the value into, and the alignment of the value within the field.  It is specified as304an optional **alignment style** followed by a positive integral **field width**.  The305alignment 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 the309formatting of the value.  For example, to format a floating point value as a percentage,310you can use the style option ``P``.311 312Custom formatting313^^^^^^^^^^^^^^^^^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 your318   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 own336  custom types with your own custom Style options.  But it does not help when you want337  to extend the mechanism for formatting a type that the library already knows how to338  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 the360  ``format`` method on the argument passing in the specified style.  This allows361  one to provide custom formatting of any type, including one which already has362  a builtin format provider.363 364``formatv`` Examples365^^^^^^^^^^^^^^^^^^^^366Below is intended to provide an incomplete set of examples demonstrating367the usage of ``formatv``.  More information can be found by reading the368doxygen 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-referencing378  outs() << formatv("{0} {2} {1} {0}", 1, "test", 3); // prints "1 3 test 1"379 380  // Left, right, and center alignment381  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 styles387  S = formatv("{0:N} - {0:x} - {1:E}", 12345, 123908342); // S == "12,345 - 0x3039 - 1.24E8"388 389  // Adapters390  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  // Ranges395  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 handling403--------------404 405Proper error handling helps us identify bugs in our code, and helps end users406understand errors in their tool usage. Errors fall into two broad categories:407*programmatic* and *recoverable*, with different strategies for handling and408reporting.409 410Programmatic Errors411^^^^^^^^^^^^^^^^^^^412 413Programmatic errors are violations of program invariants or API contracts, and414represent bugs within the program itself. Our aim is to document invariants, and415to abort quickly at the point of failure (providing some basic diagnostic) when416invariants are broken at runtime.417 418The fundamental tools for handling programmatic errors are assertions and the419``llvm_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 flow427that 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 440Additionally, ``reportFatalInternalError`` can be used to report invariant441violations even in builds that do not enable assertions:442 443.. code-block:: c++444 445  if (VerifyFooAnalysis && !Foo.verify()) {446    reportFatalInternalError("Analysis 'foo' not preserved");447  }448 449Recoverable Errors450^^^^^^^^^^^^^^^^^^451 452Recoverable errors represent an error in the program's environment, for example,453a resource failure (a missing file, a dropped network connection, etc.), or454malformed input. These errors should be detected and communicated to a level of455the program that can handle them appropriately. Handling the error may be456as simple as reporting the issue to the user, or it may involve attempts at457recovery.458 459.. note::460 461   While it would be ideal to use this error handling scheme throughout462   LLVM, there are places where this hasn't been practical to apply. In463   situations where you absolutely must emit a non-programmatic error and464   the ``Error`` model isn't workable you can call ``reportFatalUsageError``,465   which will call installed error handlers, print a message, and exit the466   program. The use of ``reportFatalUsageError`` in this case is discouraged.467 468Recoverable errors are modeled using LLVM's ``Error`` scheme. This scheme469represents errors using function return values, similar to classic C integer470error codes, or C++'s ``std::error_code``. However, the ``Error`` class is471actually a lightweight wrapper for user-defined error types, allowing arbitrary472information to be attached to describe the error. This is similar to the way C++473exceptions allow throwing of user-defined types.474 475Success values are created by calling ``Error::success()``, E.g.:476 477.. code-block:: c++478 479  Error foo() {480    // Do something.481    // Return success.482    return Error::success();483  }484 485Success values are very cheap to construct and return - they have minimal486impact on program performance.487 488Failure values are constructed using ``make_error<T>``, where ``T`` is any class489that inherits from the ``ErrorInfo`` utility, E.g.:490 491.. code-block:: c++492 493  class BadFileFormat : public ErrorInfo<BadFileFormat> {494  public:495    static char ID;496    std::string Path;497 498    BadFileFormat(StringRef Path) : Path(Path.str()) {}499 500    void log(raw_ostream &OS) const override {501      OS << Path << " is malformed";502    }503 504    std::error_code convertToErrorCode() const override {505      return make_error_code(object_error::parse_failed);506    }507  };508 509  char BadFileFormat::ID; // This should be declared in the C++ file.510 511  Error printFormattedFile(StringRef Path) {512    if (<check for valid format>)513      return make_error<BadFileFormat>(Path);514    // print file contents.515    return Error::success();516  }517 518Error values can be implicitly converted to bool: true for error, false for519success, enabling the following idiom:520 521.. code-block:: c++522 523  Error mayFail();524 525  Error foo() {526    if (auto Err = mayFail())527      return Err;528    // Success! We can proceed.529    ...530 531For functions that can fail but need to return a value the ``Expected<T>``532utility can be used. Values of this type can be constructed with either a533``T``, or an ``Error``. Expected<T> values are also implicitly convertible to534boolean, but with the opposite convention to ``Error``: true for success, false535for error. If success, the ``T`` value can be accessed via the dereference536operator. If failure, the ``Error`` value can be extracted using the537``takeError()`` method. Idiomatic usage looks like:538 539.. code-block:: c++540 541  Expected<FormattedFile> openFormattedFile(StringRef Path) {542    // If badly formatted, return an error.543    if (auto Err = checkFormat(Path))544      return std::move(Err);545    // Otherwise return a FormattedFile instance.546    return FormattedFile(Path);547  }548 549  Error processFormattedFile(StringRef Path) {550    // Try to open a formatted file551    if (auto FileOrErr = openFormattedFile(Path)) {552      // On success, grab a reference to the file and continue.553      auto &File = *FileOrErr;554      ...555    } else556      // On error, extract the Error value and return it.557      return FileOrErr.takeError();558  }559 560If an ``Expected<T>`` value is in success mode then the ``takeError()`` method561will return a success value. Using this fact, the above function can be562rewritten as:563 564.. code-block:: c++565 566  Error processFormattedFile(StringRef Path) {567    // Try to open a formatted file568    auto FileOrErr = openFormattedFile(Path);569    if (auto Err = FileOrErr.takeError())570      // On error, extract the Error value and return it.571      return Err;572    // On success, grab a reference to the file and continue.573    auto &File = *FileOrErr;574    ...575  }576 577This second form is often more readable for functions that involve multiple578``Expected<T>`` values as it limits the indentation required.579 580If an ``Expected<T>`` value will be moved into an existing variable then the581``moveInto()`` method avoids the need to name an extra variable.  This is582useful to enable ``operator->()`` if the ``Expected<T>`` value has pointer-like583semantics.  For example:584 585.. code-block:: c++586 587  Expected<std::unique_ptr<MemoryBuffer>> openBuffer(StringRef Path);588  Error processBuffer(StringRef Buffer);589 590  Error processBufferAtPath(StringRef Path) {591    // Try to open a buffer.592    std::unique_ptr<MemoryBuffer> MB;593    if (auto Err = openBuffer(Path).moveInto(MB))594      // On error, return the Error value.595      return Err;596    // On success, use MB.597    return processBuffer(MB->getBuffer());598  }599 600This third form works with any type that can be assigned to from ``T&&``. This601can be useful if the ``Expected<T>`` value needs to be stored in an already-declared602``std::optional<T>``. For example:603 604.. code-block:: c++605 606  Expected<StringRef> extractClassName(StringRef Definition);607  struct ClassData {608    StringRef Definition;609    std::optional<StringRef> LazyName;610    ...611    Error initialize() {612      if (auto Err = extractClassName(Path).moveInto(LazyName))613        // On error, return the Error value.614        return Err;615      // On success, LazyName has been initialized.616      ...617    }618  };619 620All ``Error`` instances, whether success or failure, must be either checked or621moved from (via ``std::move`` or a return) before they are destructed.622Accidentally discarding an unchecked error will cause a program to abort at the623point where the unchecked value's destructor is run, making it easy to identify624and fix violations of this rule.625 626Success values are considered checked once they have been tested (by invoking627the boolean conversion operator):628 629.. code-block:: c++630 631  if (auto Err = mayFail(...))632    return Err; // Failure value - move error to caller.633 634  // Safe to continue: Err was checked.635 636In contrast, the following code will always cause an abort, even if ``mayFail``637returns a success value:638 639.. code-block:: c++640 641    mayFail();642    // Program will always abort here, even if mayFail() returns Success, since643    // the value is not checked.644 645Failure values are considered checked once a handler for the error type has646been activated:647 648.. code-block:: c++649 650  handleErrors(651    processFormattedFile(...),652    [](const BadFileFormat &BFF) {653      report("Unable to process " + BFF.Path + ": bad format");654    },655    [](const FileNotFound &FNF) {656      report("File not found " + FNF.Path);657    });658 659The ``handleErrors`` function takes an error as its first argument, followed by660a variadic list of "handlers", each of which must be a callable type (a661function, lambda, or class with a call operator) with one argument. The662``handleErrors`` function will visit each handler in the sequence and check its663argument type against the dynamic type of the error, running the first handler664that matches. This is the same decision process that is used to decide which catch665clause to run for a C++ exception.666 667Since the list of handlers passed to ``handleErrors`` may not cover every error668type that can occur, the ``handleErrors`` function also returns an Error value669that must be checked or propagated. If the error value that is passed to670``handleErrors`` does not match any of the handlers it will be returned from671``handleErrors``. Idiomatic use of ``handleErrors`` thus looks like:672 673.. code-block:: c++674 675  if (auto Err =676        handleErrors(677          processFormattedFile(...),678          [](const BadFileFormat &BFF) {679            report("Unable to process " + BFF.Path + ": bad format");680          },681          [](const FileNotFound &FNF) {682            report("File not found " + FNF.Path);683          }))684    return Err;685 686In cases where you truly know that the handler list is exhaustive, the687``handleAllErrors`` function can be used instead. This is identical to688``handleErrors`` except that it will terminate the program if an unhandled689error is passed in, and can therefore return void. The ``handleAllErrors``690function should generally be avoided: the introduction of a new error type691elsewhere in the program can easily turn a formerly exhaustive list of errors692into a non-exhaustive list, risking unexpected program termination. Where693possible, use ``handleErrors`` and propagate unknown errors up the stack instead.694 695For tool code, where errors can be handled by printing an error message then696exiting with an error code, the :ref:`ExitOnError <err_exitonerr>` utility697may be a better choice than ``handleErrors``, as it simplifies control flow when698calling fallible functions.699 700In situations where it is known that a particular call to a fallible function701will always succeed (for example, a call to a function that can only fail on a702subset of inputs with an input that is known to be safe) the703:ref:`cantFail <err_cantfail>` functions can be used to remove the error type,704simplifying control flow.705 706StringError707"""""""""""708 709Many kinds of errors have no recovery strategy; the only action that can be710taken is to report them to the user so that the user can attempt to fix the711environment. In this case, representing the error as a string makes perfect712sense. LLVM provides the ``StringError`` class for this purpose. It takes two713arguments: A string error message, and an equivalent ``std::error_code`` for714interoperability. It also provides a ``createStringError`` function to simplify715common usage of this class:716 717.. code-block:: c++718 719  // These two lines of code are equivalent:720  make_error<StringError>("Bad executable", errc::executable_format_error);721  createStringError(errc::executable_format_error, "Bad executable");722 723If you're certain that the error you're building will never need to be converted724to a ``std::error_code``, you can use the ``inconvertibleErrorCode()`` function:725 726.. code-block:: c++727 728  createStringError(inconvertibleErrorCode(), "Bad executable");729 730This should be done only after careful consideration. If any attempt is made to731convert this error to a ``std::error_code`` it will trigger immediate program732termination. Unless you are certain that your errors will not need733interoperability you should look for an existing ``std::error_code`` that you734can convert to, and even (as painful as it is) consider introducing a new one as735a stopgap measure.736 737``createStringError`` can take ``printf`` style format specifiers to provide a738formatted message:739 740.. code-block:: c++741 742  createStringError(errc::executable_format_error,743                    "Bad executable: %s", FileName);744 745Interoperability with std::error_code and ErrorOr746"""""""""""""""""""""""""""""""""""""""""""""""""747 748Many existing LLVM APIs use ``std::error_code`` and its partner ``ErrorOr<T>``749(which plays the same role as ``Expected<T>``, but wraps a ``std::error_code``750rather than an ``Error``). The infectious nature of error types means that an751attempt to change one of these functions to return ``Error`` or ``Expected<T>``752instead often results in an avalanche of changes to callers, callers of callers,753and so on. (The first such attempt, returning an ``Error`` from754MachOObjectFile's constructor, was abandoned after the diff reached 3000 lines,755impacted half a dozen libraries, and was still growing).756 757To solve this problem, the ``Error``/``std::error_code`` interoperability requirement was758introduced. Two pairs of functions allow any ``Error`` value to be converted to a759``std::error_code``, any ``Expected<T>`` to be converted to an ``ErrorOr<T>``, and vice760versa:761 762.. code-block:: c++763 764  std::error_code errorToErrorCode(Error Err);765  Error errorCodeToError(std::error_code EC);766 767  template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> TOrErr);768  template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> TOrEC);769 770 771Using these APIs it is easy to make surgical patches that update individual772functions from ``std::error_code`` to ``Error``, and from ``ErrorOr<T>`` to773``Expected<T>``.774 775Returning Errors from error handlers776""""""""""""""""""""""""""""""""""""777 778Error recovery attempts may themselves fail. For that reason, ``handleErrors``779actually recognises three different forms of handler signature:780 781.. code-block:: c++782 783  // Error must be handled, no new errors produced:784  void(UserDefinedError &E);785 786  // Error must be handled, new errors can be produced:787  Error(UserDefinedError &E);788 789  // Original error can be inspected, then re-wrapped and returned (or a new790  // error can be produced):791  Error(std::unique_ptr<UserDefinedError> E);792 793Any error returned from a handler will be returned from the ``handleErrors``794function so that it can be handled itself or propagated up the stack.795 796.. _err_exitonerr:797 798Using ExitOnError to simplify tool code799"""""""""""""""""""""""""""""""""""""""800 801Library code should never call ``exit`` for a recoverable error; however, in tool802code (especially command line tools) this can be a reasonable approach. Calling803``exit`` upon encountering an error dramatically simplifies control flow as the804error no longer needs to be propagated up the stack. This allows code to be805written in a straight-line style, as long as each fallible call is wrapped in a806check and call to exit. The ``ExitOnError`` class supports this pattern by807providing call operators that inspect ``Error`` values, stripping the error away808in the success case and logging to ``stderr`` then exiting in the failure case.809 810To use this class, declare a global ``ExitOnError`` variable in your program:811 812.. code-block:: c++813 814  ExitOnError ExitOnErr;815 816Calls to fallible functions can then be wrapped with a call to ``ExitOnErr``,817turning them into non-failing calls:818 819.. code-block:: c++820 821  Error mayFail();822  Expected<int> mayFail2();823 824  void foo() {825    ExitOnErr(mayFail());826    int X = ExitOnErr(mayFail2());827  }828 829On failure, the error's log message will be written to ``stderr``, optionally830preceded by a string "banner" that can be set by calling the ``setBanner`` method. A831mapping can also be supplied from ``Error`` values to exit codes using the832``setExitCodeMapper`` method:833 834.. code-block:: c++835 836  int main(int argc, char *argv[]) {837    ExitOnErr.setBanner(std::string(argv[0]) + " error:");838    ExitOnErr.setExitCodeMapper(839      [](const Error &Err) {840        if (Err.isA<BadFileFormat>())841          return 2;842        return 1;843      });844 845Use ``ExitOnError`` in your tool code where possible as it can greatly improve846readability.847 848.. _err_cantfail:849 850Using cantFail to simplify safe callsites851"""""""""""""""""""""""""""""""""""""""""852 853Some functions may only fail for a subset of their inputs, so calls using known854safe inputs can be assumed to succeed.855 856The cantFail functions encapsulate this by wrapping an assertion that their857argument is a success value and, in the case of ``Expected<T>``, unwrapping the858``T`` value:859 860.. code-block:: c++861 862  Error onlyFailsForSomeXValues(int X);863  Expected<int> onlyFailsForSomeXValues2(int X);864 865  void foo() {866    cantFail(onlyFailsForSomeXValues(KnownSafeValue));867    int Y = cantFail(onlyFailsForSomeXValues2(KnownSafeValue));868    ...869  }870 871Like the ExitOnError utility, ``cantFail`` simplifies control flow. Their treatment872of error cases is very different, however: Where ExitOnError is guaranteed to873terminate the program on an error input, ``cantFail`` simply asserts that the result874is success. In debug builds this will result in an assertion failure if an error875is encountered. In release builds, the behavior of ``cantFail`` for failure values is876undefined. As such, care must be taken in the use of ``cantFail``: clients must be877certain that a ``cantFail`` wrapped call really can not fail with the given878arguments.879 880Use of the ``cantFail`` functions should be rare in library code, but they are881likely to be of more use in tool and unit-test code where inputs and/or882mocked-up classes or functions may be known to be safe.883 884Fallible constructors885"""""""""""""""""""""886 887Some classes require resource acquisition or other complex initialization that888can fail during construction. Unfortunately constructors can't return errors,889and having clients test objects after they're constructed to ensure that they're890valid is error prone as it's all too easy to forget the test. To work around891this, use the named constructor idiom and return an ``Expected<T>``:892 893.. code-block:: c++894 895  class Foo {896  public:897 898    static Expected<Foo> Create(Resource R1, Resource R2) {899      Error Err = Error::success();900      Foo F(R1, R2, Err);901      if (Err)902        return std::move(Err);903      return std::move(F);904    }905 906  private:907 908    Foo(Resource R1, Resource R2, Error &Err) {909      ErrorAsOutParameter EAO(&Err);910      if (auto Err2 = R1.acquire()) {911        Err = std::move(Err2);912        return;913      }914      Err = R2.acquire();915    }916  };917 918 919Here, the named constructor passes an ``Error`` by reference into the actual920constructor, which the constructor can then use to return errors. The921``ErrorAsOutParameter`` utility sets the ``Error`` value's checked flag on entry922to the constructor so that the error can be assigned to, then resets it on exit923to force the client (the named constructor) to check the error.924 925By using this idiom, clients attempting to construct a Foo receive either a926well-formed Foo or an Error, never an object in an invalid state.927 928Propagating and consuming errors based on types929"""""""""""""""""""""""""""""""""""""""""""""""930 931In some contexts, certain types of errors are known to be benign. For example,932when walking an archive, some clients may be happy to skip over badly formatted933object files rather than terminating the walk immediately. Skipping badly934formatted objects could be achieved using an elaborate handler method, but the935``Error.h`` header provides two utilities that make this idiom much cleaner: the936type inspection method, ``isA``, and the ``consumeError`` function:937 938.. code-block:: c++939 940  Error walkArchive(Archive A) {941    for (unsigned I = 0; I != A.numMembers(); ++I) {942      auto ChildOrErr = A.getMember(I);943      if (auto Err = ChildOrErr.takeError()) {944        if (Err.isA<BadFileFormat>())945          consumeError(std::move(Err))946        else947          return Err;948      }949      auto &Child = *ChildOrErr;950      // Use Child951      ...952    }953    return Error::success();954  }955 956Concatenating Errors with joinErrors957""""""""""""""""""""""""""""""""""""958 959In the archive walking example above, ``BadFileFormat`` errors are simply960consumed and ignored. If the client had wanted to report these errors after961completing the walk over the archive they could use the ``joinErrors`` utility:962 963.. code-block:: c++964 965  Error walkArchive(Archive A) {966    Error DeferredErrs = Error::success();967    for (unsigned I = 0; I != A.numMembers(); ++I) {968      auto ChildOrErr = A.getMember(I);969      if (auto Err = ChildOrErr.takeError())970        if (Err.isA<BadFileFormat>())971          DeferredErrs = joinErrors(std::move(DeferredErrs), std::move(Err));972        else973          return Err;974      auto &Child = *ChildOrErr;975      // Use Child976      ...977    }978    return DeferredErrs;979  }980 981The ``joinErrors`` routine builds a special error type called ``ErrorList``,982which holds a list of user-defined errors. The ``handleErrors`` routine983recognizes this type and will attempt to handle each of the contained errors in984order. If all contained errors can be handled, ``handleErrors`` will return985``Error::success()``; otherwise, ``handleErrors`` will concatenate the remaining986errors and return the resulting ``ErrorList``.987 988Building fallible iterators and iterator ranges989"""""""""""""""""""""""""""""""""""""""""""""""990 991The archive walking examples above retrieve archive members by index; however,992this requires considerable boilerplate for iteration and error checking. We can993clean this up by using the "fallible iterator" pattern, which supports the994following natural iteration idiom for fallible containers like Archive:995 996.. code-block:: c++997 998  Error Err = Error::success();999  for (auto &Child : Ar->children(Err)) {1000    // Use Child - only enter the loop when it's valid1001 1002    // Allow early exit from the loop body, since we know that Err is success1003    // when we're inside the loop.1004    if (BailOutOn(Child))1005      return;1006 1007    ...1008  }1009  // Check Err after the loop to ensure it didn't break due to an error.1010  if (Err)1011    return Err;1012 1013To enable this idiom, iterators over fallible containers are written in a1014natural style, with their ``++`` and ``--`` operators replaced with fallible1015``Error inc()`` and ``Error dec()`` functions. E.g.:1016 1017.. code-block:: c++1018 1019  class FallibleChildIterator {1020  public:1021    FallibleChildIterator(Archive &A, unsigned ChildIdx);1022    Archive::Child &operator*();1023    friend bool operator==(const ArchiveIterator &LHS,1024                           const ArchiveIterator &RHS);1025 1026    // operator++/operator-- replaced with fallible increment / decrement:1027    Error inc() {1028      if (!A.childValid(ChildIdx + 1))1029        return make_error<BadArchiveMember>(...);1030      ++ChildIdx;1031      return Error::success();1032    }1033 1034    Error dec() { ... }1035  };1036 1037Instances of this kind of fallible iterator interface are then wrapped with the1038fallible_iterator utility which provides ``operator++`` and ``operator--``,1039returning any errors via a reference passed in to the wrapper at construction1040time. The fallible_iterator wrapper takes care of (a) jumping to the end of the1041range on error, and (b) marking the error as checked whenever an iterator is1042compared to ``end`` and found to be unequal (in particular, this marks the1043error as checked throughout the body of a range-based for loop), enabling early1044exit from the loop without redundant error checking.1045 1046Instances of the fallible iterator interface (e.g., FallibleChildIterator above)1047are wrapped using the ``make_fallible_itr`` and ``make_fallible_end``1048functions. E.g.:1049 1050.. code-block:: c++1051 1052  class Archive {1053  public:1054    using child_iterator = fallible_iterator<FallibleChildIterator>;1055 1056    child_iterator child_begin(Error &Err) {1057      return make_fallible_itr(FallibleChildIterator(*this, 0), Err);1058    }1059 1060    child_iterator child_end() {1061      return make_fallible_end(FallibleChildIterator(*this, size()));1062    }1063 1064    iterator_range<child_iterator> children(Error &Err) {1065      return make_range(child_begin(Err), child_end());1066    }1067  };1068 1069Using the fallible_iterator utility allows for both natural construction of1070fallible iterators (using failing ``inc`` and ``dec`` operations) and1071relatively natural use of C++ iterator/loop idioms.1072 1073.. _function_apis:1074 1075More information on Error and its related utilities can be found in the1076``Error.h`` header file.1077 1078Passing functions and other callable objects1079--------------------------------------------1080 1081Sometimes you may want a function to be passed a callback object. In order to1082support lambda expressions and other function objects, you should not use the1083traditional C approach of taking a function pointer and an opaque cookie:1084 1085.. code-block:: c++1086 1087    void takeCallback(bool (*Callback)(Function *, void *), void *Cookie);1088 1089Instead, use one of the following approaches:1090 1091Function template1092^^^^^^^^^^^^^^^^^1093 1094If you don't mind putting the definition of your function into a header file,1095make it a function template that is templated on the callable type.1096 1097.. code-block:: c++1098 1099    template<typename Callable>1100    void takeCallback(Callable Callback) {1101      Callback(1, 2, 3);1102    }1103 1104The ``function_ref`` class template1105^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1106 1107The ``function_ref``1108(`doxygen <https://llvm.org/doxygen/classllvm_1_1function__ref_3_01Ret_07Params_8_8_8_08_4.html>`__) class1109template represents a reference to a callable object, templated over the type1110of the callable. This is a good choice for passing a callback to a function,1111if you don't need to hold onto the callback after the function returns. In this1112way, ``function_ref`` is to ``std::function`` as ``StringRef`` is to1113``std::string``.1114 1115``function_ref<Ret(Param1, Param2, ...)>`` can be implicitly constructed from1116any callable object that can be called with arguments of type ``Param1``,1117``Param2``, ..., and returns a value that can be converted to type ``Ret``.1118For example:1119 1120.. code-block:: c++1121 1122    void visitBasicBlocks(Function *F, function_ref<bool (BasicBlock*)> Callback) {1123      for (BasicBlock &BB : *F)1124        if (Callback(&BB))1125          return;1126    }1127 1128can be called using:1129 1130.. code-block:: c++1131 1132    visitBasicBlocks(F, [&](BasicBlock *BB) {1133      if (process(BB))1134        return isEmpty(BB);1135      return false;1136    });1137 1138Note that a ``function_ref`` object contains pointers to external memory, so it1139is not generally safe to store an instance of the class (unless you know that1140the external storage will not be freed). If you need this ability, consider1141using ``std::function``. ``function_ref`` is small enough that it should always1142be passed by value.1143 1144.. _DEBUG:1145 1146The ``LDBG`` and ``LLVM_DEBUG()`` macros and ``-debug`` option1147--------------------------------------------------------------1148 1149Often, when working on your pass, you will put a bunch of debugging printouts and1150other code into your pass.  After you get it working, you want to remove it, but1151you may need it again in the future (to work out new bugs that you run across).1152 1153Naturally, because of this, you don't want to delete the debug printouts, but1154you don't want them to always be noisy.  A standard compromise is to comment1155them out, allowing you to enable them if you need them in the future.1156 1157The ``llvm/Support/DebugLog.h`` file provides a macro named ``LDBG`` that is a1158more convenient way to add debug output to your code. It is a macro that1159provides a raw_ostream that is used to write the debug output.1160 1161.. code-block:: c++1162 1163  LDBG() << "I am here!";1164 1165It'll only print the output if the debug output is enabled.1166It also supports a `level` argument to control the verbosity of the output.1167 1168.. code-block:: c++1169 1170  LDBG(2) << "I am here!";1171 1172A ``DEBUG_TYPE`` macro may optionally be defined in the file before using1173``LDBG()``, otherwise the file name is used as the debug type.1174The file name and line number are automatically added to the output, as well as1175a terminating newline.1176 1177The debug output can be enabled by passing the ``-debug`` command line argument.1178 1179.. code-block:: none1180 1181  $ opt < a.bc > /dev/null -mypass1182  <no output>1183  $ opt < a.bc > /dev/null -mypass -debug1184  [my-pass MyPass.cpp:123 2] I am here!1185 1186While ``LDBG()`` is useful to add debug output to your code, there are cases1187where you may need to guard a block of code with a debug check. The1188``llvm/Support/Debug.h`` (`doxygen1189<https://llvm.org/doxygen/Debug_8h_source.html>`__) file provides a macro named1190``LLVM_DEBUG()`` that offers a solution to this problem.  You can put arbitrary1191code into the argument of the ``LLVM_DEBUG`` macro, and it is only executed if1192'``opt``' (or any other tool) is run with the '``-debug``' command1193line argument.1194 1195.. code-block:: c++1196 1197  LLVM_DEBUG({1198    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> logBuffer =1199        llvm::MemoryBuffer::getFile(logFile->first);1200    if (logBuffer && !(*logBuffer)->getBuffer().empty()) {1201      LDBG() << "Output:\n" << (*logBuffer)->getBuffer();1202    }1203  });1204 1205 1206Using these macros instead of a home-brewed solution allows you to not have to1207create "yet another" command-line option for the debug output for your pass.1208Note that ``LDBG()`` and ``LLVM_DEBUG()`` macros are disabled for non-asserts1209builds, so they do not cause a performance impact at all (for the same reason,1210they should also not contain side-effects!).1211 1212One additional nice thing about the ``LDBG()`` and ``LLVM_DEBUG()`` macros is1213that you can enable or disable it directly in gdb.  Just use1214"``set DebugFlag=0``" or "``set DebugFlag=1``" from the gdb if the program is1215running.  If the program hasn't been started yet, you can always just run it1216with ``-debug``.1217 1218.. _DEBUG_TYPE:1219 1220Fine grained debug info with ``DEBUG_TYPE`` and the ``-debug-only`` option1221^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1222 1223Sometimes, you may find yourself in a situation where enabling ``-debug`` just1224turns on **too much** information (such as when working on the code generator).1225If you want to enable debug information with more fine-grained control, you1226can control the debug type and level with associate with each logging statement1227as follows:1228 1229.. code-block:: c++1230 1231  #define DEBUG_TYPE "foo" // Optional: the file name is used instead if not defined1232  LDBG(2) << "Hello,";1233  // DEBUG_TYPE can be overridden locally, here with "bar"1234  LDBG("bar", 3) << "'bar' debug type";1235 1236 1237A more fine-grained control of the output can be achieved by passing the1238``-debug-only`` command line argument:1239 1240.. code-block:: none1241 1242  $ opt < a.bc > /dev/null -mypass -debug-only=foo1243  [foo MyPass.cpp:123 2] Hello,1244  $ opt < a.bc > /dev/null -mypass -debug-only=foo,bar1245  [foo MyPass.cpp:123 2] Hello,1246  [bar MyPass.cpp:124 3] World!1247  $ opt < a.bc > /dev/null -mypass -debug-only=bar1248  [bar MyPass.cpp:124 3] World!1249 1250The debug-only argument is a comma separated list of debug types and levels.1251The level is an optional integer setting the maximum debug level to enable:1252 1253.. code-block:: none1254 1255  $ opt < a.bc > /dev/null -mypass -debug-only=foo:2,bar:21256  [foo MyPass.cpp:123 2] Hello,1257  $ opt < a.bc > /dev/null -mypass -debug-only=foo:1,bar:31258  [bar MyPass.cpp:124 3] World!1259 1260Instead of opting in specific debug types, the ``-debug-only`` option also1261works to filter out debug output for specific debug types, by omitting the1262level (or setting it to 0):1263 1264.. code-block:: none1265 1266  $ opt < a.bc > /dev/null -mypass -debug-only=foo:1267  [bar MyPass.cpp:124 3] World!1268  $ opt < a.bc > /dev/null -mypass -debug-only=bar:0,foo:1269 1270 1271In practice, you should only set ``DEBUG_TYPE`` at the top of a file, to1272specify the debug type for the entire module. Be careful that you only do1273this after you're done including headers (in particular ``Debug.h``/``DebugLog.h``).1274Also, you should use names more meaningful than "foo" and "bar", because there1275is no system in place to ensure that names do not conflict. If two different1276modules use the same string, they will all be turned on when the name is specified.1277This allows, for example, all debug information for instruction scheduling to be1278enabled with ``-debug-only=InstrSched``, even if the source lives in multiple1279files. The name must not include a comma (,) as that is used to separate the1280arguments of the ``-debug-only`` option.1281 1282For performance reasons, -debug-only is not available in non-asserts build1283of LLVM.1284 1285The ``DEBUG_WITH_TYPE`` macro is an alternative to the ``LLVM_DEBUG()`` macro1286for situations where you would like to set ``DEBUG_TYPE``, but only for one1287specific ``LLVM_DEBUG`` statement.  It takes an additional first parameter,1288which is the type to use. The example from the previous section could be1289written as:1290 1291.. code-block:: c++1292 1293  DEBUG_WITH_TYPE("special-type", {1294    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> logBuffer =1295        llvm::MemoryBuffer::getFile(logFile->first);1296    if (logBuffer && !(*logBuffer)->getBuffer().empty()) {1297      LDBG("special-type") << "Output:\n" << (*logBuffer)->getBuffer();1298    }1299  });1300 1301.. _Statistic:1302 1303The ``Statistic`` class & ``-stats`` option1304-------------------------------------------1305 1306The ``llvm/ADT/Statistic.h`` (`doxygen1307<https://llvm.org/doxygen/Statistic_8h_source.html>`__) file provides a class1308named ``Statistic`` that is used as a unified way to keep track of what the LLVM1309compiler is doing and how effective various optimizations are.  It is useful to1310see what optimizations are contributing to making a particular program run1311faster.1312 1313Often you may run your pass on some big program, and you're interested to see1314how many times it makes a certain transformation.  Although you can do this with1315hand inspection, or some ad-hoc method, this is a real pain and not very useful1316for big programs.  Using the ``Statistic`` class makes it very easy to keep1317track of this information, and the calculated information is presented in a1318uniform manner with the rest of the passes being executed.1319 1320There are many examples of ``Statistic`` uses, but the basics of using it are as1321follows:1322 1323Define your statistic like this:1324 1325.. code-block:: c++1326 1327  #define DEBUG_TYPE "mypassname"   // This goes after any #includes.1328  STATISTIC(NumXForms, "The # of times I did stuff");1329 1330The ``STATISTIC`` macro defines a static variable, whose name is specified by1331the first argument.  The pass name is taken from the ``DEBUG_TYPE`` macro, and1332the description is taken from the second argument.  The variable defined1333("NumXForms" in this case) acts like an unsigned integer.1334 1335Whenever you make a transformation, bump the counter:1336 1337.. code-block:: c++1338 1339  ++NumXForms;   // I did stuff!1340 1341That's all you have to do.  To get '``opt``' to print out the statistics1342gathered, use the '``-stats``' option:1343 1344.. code-block:: none1345 1346  $ opt -stats -mypassname < program.bc > /dev/null1347  ... statistics output ...1348 1349Note that in order to use the '``-stats``' option, LLVM must be1350compiled with assertions enabled.1351 1352When running ``opt`` on a C file from the SPEC benchmark suite, it gives a1353report that looks like this:1354 1355.. code-block:: none1356 1357   7646 bitcodewriter   - Number of normal instructions1358    725 bitcodewriter   - Number of oversized instructions1359 129996 bitcodewriter   - Number of bitcode bytes written1360   2817 raise           - Number of insts DCEd or constprop'd1361   3213 raise           - Number of cast-of-self removed1362   5046 raise           - Number of expression trees converted1363     75 raise           - Number of other getelementptr's formed1364    138 raise           - Number of load/store peepholes1365     42 deadtypeelim    - Number of unused typenames removed from symtab1366    392 funcresolve     - Number of varargs functions resolved1367     27 globaldce       - Number of global variables removed1368      2 adce            - Number of basic blocks removed1369    134 cee             - Number of branches revectored1370     49 cee             - Number of setcc instruction eliminated1371    532 gcse            - Number of loads removed1372   2919 gcse            - Number of instructions removed1373     86 indvars         - Number of canonical indvars added1374     87 indvars         - Number of aux indvars removed1375     25 instcombine     - Number of dead inst eliminate1376    434 instcombine     - Number of insts combined1377    248 licm            - Number of load insts hoisted1378   1298 licm            - Number of insts hoisted to a loop pre-header1379      3 licm            - Number of insts hoisted to multiple loop preds (bad, no loop pre-header)1380     75 mem2reg         - Number of alloca's promoted1381   1444 cfgsimplify     - Number of blocks simplified1382 1383Obviously, with so many optimizations, having a unified framework for this stuff1384is very nice.  Making your pass fit well into the framework makes it more1385maintainable and useful.1386 1387.. _DebugCounters:1388 1389Adding debug counters to aid in debugging your code1390---------------------------------------------------1391 1392Sometimes, when writing new passes or trying to track down bugs, it1393is useful to be able to control whether certain things in your pass1394happen or not.  For example, there are times the minimization tooling1395can only easily give you large testcases.  You would like to narrow1396your bug down to a specific transformation happening or not happening,1397automatically, using bisection.  This is where debug counters help.1398They provide a framework for making parts of your code only execute a1399certain number of times.1400 1401The ``llvm/Support/DebugCounter.h`` (`doxygen1402<https://llvm.org/doxygen/DebugCounter_8h_source.html>`__) file1403provides a class named ``DebugCounter`` that can be used to create1404command-line counter options that control execution of parts of your code.1405 1406Define your ``DebugCounter`` like this:1407 1408.. code-block:: c++1409 1410  DEBUG_COUNTER(DeleteAnInstruction, "passname-delete-instruction",1411		"Controls which instructions get delete");1412 1413The ``DEBUG_COUNTER`` macro defines a static variable, whose name1414is specified by the first argument.  The name of the counter1415(which is used on the command line) is specified by the second1416argument, and the description used in the help is specified by the1417third argument.1418 1419Whatever code you want to control, use ``DebugCounter::shouldExecute`` to control it.1420 1421.. code-block:: c++1422 1423  if (DebugCounter::shouldExecute(DeleteAnInstruction))1424    I->eraseFromParent();1425 1426That's all you have to do. Now, using opt, you can control when this code triggers using1427the '``--debug-counter``' Options. To specify when to execute the codepath.1428 1429.. code-block:: none1430 1431  $ opt --debug-counter=passname-delete-instruction=2-3 -passname1432 1433This will skip the above code the first two times we hit it, then execute it 2 times, then skip the rest of the executions.1434 1435So if executed on the following code:1436 1437.. code-block:: llvm1438 1439  %1 = add i32 %a, %b1440  %2 = add i32 %a, %b1441  %3 = add i32 %a, %b1442  %4 = add i32 %a, %b1443 1444It would delete number ``%2`` and ``%3``.1445 1446A utility is provided in `utils/bisect-skip-count` to binary search1447the begin and end of the range argument. It can be used to automatically minimize the1448range for a debug-counter variable.1449 1450A more general utility is provided in `llvm/tools/reduce-chunk-list/reduce-chunk-list.cpp` to minimize debug counter chunks lists.1451 1452How to use reduce-chunk-list:1453First, Figure out the number of calls to the debug counter you want to minimize.1454To do so, run the compilation command causing you want to minimize with `-print-debug-counter` adding a `-mllvm` if needed.1455Then find the line with the counter of interest. it should look like:1456 1457.. code-block:: none1458 1459  my-counter               : {5678,empty}1460 1461The number of calls to `my-counter` is 56781462 1463Then find the minimum set of chunks that is interesting, with `reduce-chunk-list`.1464Build a reproducer script like:1465 1466.. code-block:: bash1467 1468  #! /bin/bash1469  opt -debug-counter=my-counter=$11470  # ... Test result of the command. Failure of the script is considered interesting1471 1472Then run `reduce-chunk-list my-script.sh 0-5678 2>&1 | tee dump_bisect`1473This command may take some time.1474but when it is done, it will print the result like: `Minimal Chunks = 0:1:5:11-12:33-34`1475 1476.. _ViewGraph:1477 1478Viewing graphs while debugging code1479-----------------------------------1480 1481Several of the important data structures in LLVM are graphs: for example CFGs1482made out of LLVM :ref:`BasicBlocks <BasicBlock>`, CFGs made out of LLVM1483:ref:`MachineBasicBlocks <MachineBasicBlock>`, and :ref:`Instruction Selection1484DAGs <SelectionDAG>`.  In many cases, while debugging various parts of the1485compiler, it is nice to instantly visualize these graphs.1486 1487LLVM provides several callbacks that are available in a debug build to do1488exactly that.  If you call the ``Function::viewCFG()`` method, for example, the1489current LLVM tool will pop up a window containing the CFG for the function where1490each basic block is a node in the graph, and each node contains the instructions1491in the block.  Similarly, there also exists ``Function::viewCFGOnly()`` (does1492not include the instructions), the ``MachineFunction::viewCFG()`` and1493``MachineFunction::viewCFGOnly()``, and the ``SelectionDAG::viewGraph()``1494methods.  Within GDB, for example, you can usually use something like ``call1495DAG.viewGraph()`` to pop up a window.  Alternatively, you can sprinkle calls to1496these functions in your code in places you want to debug.1497 1498Getting this to work requires a small amount of setup.  On Unix systems1499with X11, install the `graphviz <http://www.graphviz.org>`_ toolkit, and make1500sure 'dot' and 'gv' are in your path.  If you are running on macOS, download1501and install the macOS `Graphviz program1502<http://www.pixelglow.com/graphviz/>`_ and add1503``/Applications/Graphviz.app/Contents/MacOS/`` (or wherever you install it) to1504your path. The programs need not be present when configuring, building or1505running LLVM and can simply be installed when needed during an active debug1506session.1507 1508``SelectionDAG`` has been extended to make it easier to locate *interesting*1509nodes in large complex graphs.  From gdb, if you ``call DAG.setGraphColor(node,1510"color")``, then the next ``call DAG.viewGraph()`` would highlight the node in1511the specified color (choices of colors can be found at `colors1512<http://www.graphviz.org/doc/info/colors.html>`_.) More complex node attributes1513can be provided with ``call DAG.setGraphAttrs(node, "attributes")`` (choices can1514be found at `Graph attributes <http://www.graphviz.org/doc/info/attrs.html>`_.)1515If you want to restart and clear all the current graph attributes, then you can1516``call DAG.clearGraphAttrs()``.1517 1518Note that graph visualization features are compiled out of Release builds to1519reduce file size.  This means that you need a Debug+Asserts or Release+Asserts1520build to use these features.1521 1522.. _datastructure:1523 1524Picking the Right Data Structure for a Task1525===========================================1526 1527LLVM has a plethora of data structures in the ``llvm/ADT/`` directory, and we1528commonly use STL data structures.  This section describes the trade-offs you1529should consider when you pick one.1530 1531The first step is to choose your own adventure: do you want a sequential1532container, a set-like container, or a map-like container?  The most important1533thing when choosing a container is the algorithmic properties of how you plan to1534access the container.  Based on that, you should use:1535 1536 1537* a :ref:`map-like <ds_map>` container if you need efficient look-up of a1538  value based on another value.  Map-like containers also support efficient1539  queries for containment (whether a key is in the map).  Map-like containers1540  generally do not support efficient reverse mapping (values to keys).  If you1541  need that, use two maps.  Some map-like containers also support efficient1542  iteration through the keys in sorted order.  Map-like containers are the most1543  expensive sort, only use them if you need one of these capabilities.1544 1545* a :ref:`set-like <ds_set>` container if you need to put a bunch of stuff into1546  a container that automatically eliminates duplicates.  Some set-like1547  containers support efficient iteration through the elements in sorted order.1548  Set-like containers are more expensive than sequential containers.1549 1550* a :ref:`sequential <ds_sequential>` container provides the most efficient way1551  to add elements and keeps track of the order they are added to the collection.1552  They permit duplicates and support efficient iteration, but do not support1553  efficient look-up based on a key.1554 1555* a :ref:`string <ds_string>` container is a specialized sequential container or1556  reference structure that is used for character or byte arrays.1557 1558* a :ref:`bit <ds_bit>` container provides an efficient way to store and1559  perform set operations on sets of numeric id's, while automatically1560  eliminating duplicates.  Bit containers require a maximum of 1 bit for each1561  identifier you want to store.1562 1563Once the proper category of container is determined, you can fine tune the1564memory use, constant factors, and cache behaviors of access by intelligently1565picking a member of the category.  Note that constant factors and cache behavior1566can be a big deal.  If you have a vector that usually only contains a few1567elements (but could contain many), for example, it's much better to use1568:ref:`SmallVector <dss_smallvector>` than :ref:`vector <dss_vector>`.  Doing so1569avoids (relatively) expensive malloc/free calls, which dwarf the cost of adding1570the elements to the container.1571 1572.. _ds_sequential:1573 1574Sequential Containers (std::vector, std::list, etc)1575---------------------------------------------------1576 1577There are a variety of sequential containers available for you, based on your1578needs.  Pick the first in this section that will do what you want.1579 1580.. _dss_arrayref:1581 1582llvm/ADT/ArrayRef.h1583^^^^^^^^^^^^^^^^^^^1584 1585The ``llvm::ArrayRef`` class is the preferred class to use in an interface that1586accepts a sequential list of elements in memory and just reads from them.  By1587taking an ``ArrayRef``, the API can be passed a fixed size array, an1588``std::vector``, an ``llvm::SmallVector`` and anything else that is contiguous1589in memory.1590 1591.. _dss_fixedarrays:1592 1593Fixed Size Arrays1594^^^^^^^^^^^^^^^^^1595 1596Fixed size arrays are very simple and very fast.  They are good if you know1597exactly how many elements you have, or you have a (low) upper bound on how many1598you have.1599 1600.. _dss_heaparrays:1601 1602Heap Allocated Arrays1603^^^^^^^^^^^^^^^^^^^^^1604 1605Heap allocated arrays (``new[]`` + ``delete[]``) are also simple.  They are good1606if the number of elements is variable, if you know how many elements you will1607need before the array is allocated, and if the array is usually large (if not,1608consider a :ref:`SmallVector <dss_smallvector>`).  The cost of a heap allocated1609array is the cost of the new/delete (aka malloc/free).  Also note that if you1610are allocating an array of a type with a constructor, the constructor and1611destructors will be run for every element in the array (re-sizable vectors only1612construct those elements actually used).1613 1614.. _dss_tinyptrvector:1615 1616llvm/ADT/TinyPtrVector.h1617^^^^^^^^^^^^^^^^^^^^^^^^1618 1619``TinyPtrVector<Type>`` is a highly specialized collection class that is1620optimized to avoid allocation in the case when a vector has zero or one1621elements.  It has two major restrictions: 1) it can only hold values of pointer1622type, and 2) it cannot hold a null pointer.1623 1624Since this container is highly specialized, it is rarely used.1625 1626.. _dss_smallvector:1627 1628llvm/ADT/SmallVector.h1629^^^^^^^^^^^^^^^^^^^^^^1630 1631``SmallVector<Type, N>`` is a simple class that looks and smells just like1632``vector<Type>``: it supports efficient iteration, lays out elements in memory1633order (so you can do pointer arithmetic between elements), supports efficient1634``push_back``/``pop_back`` operations, supports efficient random access to its elements,1635etc.1636 1637The main advantage of ``SmallVector`` is that it allocates space for some number of1638elements (N) **in the object itself**.  Because of this, if the ``SmallVector`` is1639dynamically smaller than N, no malloc is performed.  This can be a big win in1640cases where the malloc/free call is far more expensive than the code that1641fiddles around with the elements.1642 1643This is good for vectors that are "usually small" (e.g., the number of1644predecessors/successors of a block is usually less than 8).  On the other hand,1645this makes the size of the ``SmallVector`` itself large, so you don't want to1646allocate lots of them (doing so will waste a lot of space).  As such,1647SmallVectors are most useful when on the stack.1648 1649In the absence of a well-motivated choice for the number of1650inlined elements ``N``, it is recommended to use ``SmallVector<T>`` (that is,1651omitting the ``N``). This will choose a default number of1652inlined elements reasonable for allocation on the stack (for example, trying1653to keep ``sizeof(SmallVector<T>)`` around 64 bytes).1654 1655``SmallVector`` also provides a nice portable and efficient replacement for1656``alloca``.1657 1658``SmallVector`` has grown a few other minor advantages over ``std::vector``, causing1659``SmallVector<Type, 0>`` to be preferred over ``std::vector<Type>``.1660 1661#. ``std::vector`` is exception-safe, and some implementations have pessimizations1662   that copy elements when ``SmallVector`` would move them.1663 1664#. ``SmallVector`` understands ``std::is_trivially_copyable<Type>`` and uses realloc aggressively.1665 1666#. Many LLVM APIs take a ``SmallVectorImpl`` as an out parameter (see the note1667   below).1668 1669#. ``SmallVector`` with N equal to 0 is smaller than ``std::vector`` on 64-bit1670   platforms, since it uses ``unsigned`` (instead of ``void*``) for its size1671   and capacity.1672 1673.. note::1674 1675   Prefer to use ``ArrayRef<T>`` or ``SmallVectorImpl<T>`` as a parameter type.1676 1677   It's rarely appropriate to use ``SmallVector<T, N>`` as a parameter type.1678   If an API only reads from the vector, it should use :ref:`ArrayRef1679   <dss_arrayref>`.  Even if an API updates the vector the "small size" is1680   unlikely to be relevant; such an API should use the ``SmallVectorImpl<T>``1681   class, which is the "vector header" (and methods) without the elements1682   allocated after it. Note that ``SmallVector<T, N>`` inherits from1683   ``SmallVectorImpl<T>`` so the conversion is implicit and costs nothing. E.g.1684 1685   .. code-block:: c++1686 1687      // DISCOURAGED: Clients cannot pass e.g., raw arrays.1688      hardcodedContiguousStorage(const SmallVectorImpl<Foo> &In);1689      // ENCOURAGED: Clients can pass any contiguous storage of Foo.1690      allowsAnyContiguousStorage(ArrayRef<Foo> In);1691 1692      void someFunc1() {1693        Foo Vec[] = { /* ... */ };1694        hardcodedContiguousStorage(Vec); // Error.1695        allowsAnyContiguousStorage(Vec); // Works.1696      }1697 1698      // DISCOURAGED: Clients cannot pass e.g., SmallVector<Foo, 8>.1699      hardcodedSmallSize(SmallVector<Foo, 2> &Out);1700      // ENCOURAGED: Clients can pass any SmallVector<Foo, N>.1701      allowsAnySmallSize(SmallVectorImpl<Foo> &Out);1702 1703      void someFunc2() {1704        SmallVector<Foo, 8> Vec;1705        hardcodedSmallSize(Vec); // Error.1706        allowsAnySmallSize(Vec); // Works.1707      }1708 1709   Even though it has "``Impl``" in the name, SmallVectorImpl is widely used1710   and is no longer "private to the implementation". A name like1711   ``SmallVectorHeader`` might be more appropriate.1712 1713.. _dss_pagedvector:1714 1715llvm/ADT/PagedVector.h1716^^^^^^^^^^^^^^^^^^^^^^1717 1718``PagedVector<Type, PageSize>`` is a random access container that allocates1719``PageSize`` elements of type ``Type`` when the first element of a page is1720accessed via the ``operator[]``.  This is useful for cases where the number of1721elements is known in advance; their actual initialization is expensive; and1722they are sparsely used. This utility uses page-granular lazy initialization1723when the element is accessed. When the number of used pages is small1724significant memory savings can be achieved.1725 1726The main advantage is that a ``PagedVector`` allows to delay the actual1727allocation of the page until it's needed, at the extra cost of one pointer per1728page and one extra indirection when accessing elements with their positional1729index.1730 1731In order to minimise the memory footprint of this container, it's important to1732balance the ``PageSize`` so that it's not too small (otherwise, the overhead of the1733pointer per page might become too high) and not too big (otherwise, the memory1734is wasted if the page is not fully used).1735 1736Moreover, while retaining the order of the elements based on their insertion1737index, like a vector, iterating over the elements via ``begin()`` and ``end()``1738is not provided in the API, due to the fact that accessing the elements in order1739would allocate all the iterated pages, defeating memory savings and the purpose1740of the ``PagedVector``.1741 1742Finally, ``materialized_begin()`` and ``materialized_end`` iterators are1743provided to access the elements associated to the accessed pages, which could1744speed up operations that need to iterate over initialized elements in a1745non-ordered manner.1746 1747.. _dss_vector:1748 1749<vector>1750^^^^^^^^1751 1752``std::vector<T>`` is well loved and respected.  However, ``SmallVector<T, 0>``1753is often a better option due to the advantages listed above.  ``std::vector`` is1754still useful when you need to store more than ``UINT32_MAX`` elements or when1755interfacing with code that expects vectors :).1756 1757One worthwhile note about ``std::vector``: avoid code like this:1758 1759.. code-block:: c++1760 1761  for ( ... ) {1762     std::vector<foo> V;1763     // make use of V.1764  }1765 1766Instead, write this as:1767 1768.. code-block:: c++1769 1770  std::vector<foo> V;1771  for ( ... ) {1772     // make use of V.1773     V.clear();1774  }1775 1776Doing so will save (at least) one heap allocation and free per iteration of the1777loop.1778 1779.. _dss_deque:1780 1781<deque>1782^^^^^^^1783 1784``std::deque`` is, in some senses, a generalized version of ``std::vector``.1785Like ``std::vector``, it provides constant-time random access and other similar1786properties, but it also provides efficient access to the front of the list.  It1787does not guarantee the continuity of elements within memory.1788 1789In exchange for this extra flexibility, ``std::deque`` has significantly higher1790constant factor costs than ``std::vector``.  If possible, use ``std::vector`` or1791something cheaper.1792 1793.. _dss_list:1794 1795<list>1796^^^^^^1797 1798``std::list`` is an extremely inefficient class that is rarely useful.  It1799performs a heap allocation for every element inserted into it, thus having an1800extremely high constant factor, particularly for small data types.1801``std::list`` also only supports bidirectional iteration, not random access1802iteration.1803 1804In exchange for this high cost, ``std::list`` supports efficient access to both ends1805of the list (like ``std::deque``, but unlike ``std::vector`` or1806``SmallVector``).  In addition, the iterator invalidation characteristics of1807``std::list`` are stronger than that of a vector class: inserting or removing an1808element into the list does not invalidate iterator or pointers to other elements1809in the list.1810 1811.. _dss_ilist:1812 1813llvm/ADT/ilist.h1814^^^^^^^^^^^^^^^^1815 1816``ilist<T>`` implements an 'intrusive' doubly-linked list.  It is intrusive,1817because it requires the element to store and provide access to the prev/next1818pointers for the list.1819 1820``ilist`` has the same drawbacks as ``std::list``, and additionally requires an1821``ilist_traits`` implementation for the element type, but it provides some novel1822characteristics.  In particular, it can efficiently store polymorphic objects,1823the traits class is informed when an element is inserted or removed from the1824list, and ``ilist``\ s are guaranteed to support a constant-time splice1825operation.1826 1827An ``ilist`` and an ``iplist`` are ``using`` aliases to one another and the1828latter only currently exists for historical purposes.1829 1830These properties are exactly what we want for things like ``Instruction``\ s and1831basic blocks, which is why these are implemented with ``ilist``\ s.1832 1833Related classes of interest are explained in the following subsections:1834 1835* :ref:`ilist_traits <dss_ilist_traits>`1836 1837* :ref:`llvm/ADT/ilist_node.h <dss_ilist_node>`1838 1839* :ref:`Sentinels <dss_ilist_sentinel>`1840 1841.. _dss_packedvector:1842 1843llvm/ADT/PackedVector.h1844^^^^^^^^^^^^^^^^^^^^^^^1845 1846Useful for storing a vector of values using only a few bits for each1847value.  Apart from the standard operations of a vector-like container, it can1848also perform an 'or' set operation.1849 1850For example:1851 1852.. code-block:: c++1853 1854  enum State {1855      None = 0x0,1856      FirstCondition = 0x1,1857      SecondCondition = 0x2,1858      Both = 0x31859  };1860 1861  State get() {1862      PackedVector<State, 2> Vec1;1863      Vec1.push_back(FirstCondition);1864 1865      PackedVector<State, 2> Vec2;1866      Vec2.push_back(SecondCondition);1867 1868      Vec1 |= Vec2;1869      return Vec1[0]; // returns 'Both'.1870  }1871 1872.. _dss_ilist_traits:1873 1874ilist_traits1875^^^^^^^^^^^^1876 1877``ilist_traits<T>`` is ``ilist<T>``'s customization mechanism. ``ilist<T>``1878publicly derives from this traits class.1879 1880.. _dss_ilist_node:1881 1882llvm/ADT/ilist_node.h1883^^^^^^^^^^^^^^^^^^^^^1884 1885``ilist_node<T>`` implements the forward and backward links that are expected1886by the ``ilist<T>`` (and analogous containers) in the default manner.1887 1888``ilist_node<T>``\ s are meant to be embedded in the node type ``T``, usually1889``T`` publicly derives from ``ilist_node<T>``.1890 1891.. _dss_ilist_sentinel:1892 1893Sentinels1894^^^^^^^^^1895 1896``ilist``\ s have another specialty that must be considered.  To be a good1897citizen in the C++ ecosystem, it needs to support the standard container1898operations, such as ``begin`` and ``end`` iterators, etc.  Also, the1899``operator--`` must work correctly on the ``end`` iterator in the case of1900non-empty ``ilist``\ s.1901 1902The only sensible solution to this problem is to allocate a so-called *sentinel*1903along with the intrusive list, which serves as the ``end`` iterator, providing1904the back-link to the last element.  However, conforming to the C++ convention it1905is illegal to ``operator++`` beyond the sentinel and it also must not be1906dereferenced.1907 1908These constraints allow for some implementation freedom to the ``ilist`` how to1909allocate and store the sentinel.  The corresponding policy is dictated by1910``ilist_traits<T>``.  By default, a ``T`` gets heap-allocated whenever the need1911for a sentinel arises.1912 1913While the default policy is sufficient in most cases, it may break down when1914``T`` does not provide a default constructor.  Also, in the case of many1915instances of ``ilist``\ s, the memory overhead of the associated sentinels is1916wasted.  To alleviate the situation with numerous and voluminous1917``T``-sentinels, sometimes a trick is employed, leading to *ghostly sentinels*.1918 1919Ghostly sentinels are obtained by specially-crafted ``ilist_traits<T>`` which1920superpose the sentinel with the ``ilist`` instance in memory.  Pointer1921arithmetic is used to obtain the sentinel, which is relative to the ``ilist``'s1922``this`` pointer.  The ``ilist`` is augmented by an extra pointer, which serves1923as the back-link of the sentinel.  This is the only field in the ghostly1924sentinel which can be legally accessed.1925 1926.. _dss_other:1927 1928Other Sequential Container options1929^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1930 1931Other STL containers are available, such as ``std::string``.1932 1933There are also various STL adapter classes such as ``std::queue``,1934``std::priority_queue``, ``std::stack``, etc.  These provide simplified access1935to an underlying container but don't affect the cost of the container itself.1936 1937.. _ds_string:1938 1939String-like containers1940----------------------1941 1942There are a variety of ways to pass around and use strings in C and C++, and1943LLVM adds a few new options to choose from.  Pick the first option on this list1944that will do what you need; they are ordered according to their relative cost.1945 1946Note that it is generally preferred to *not* pass strings around as ``const1947char*``'s.  These have a number of problems, including the fact that they1948cannot represent embedded nul ("\0") characters, and do not have a length1949available efficiently.  The general replacement for '``const char*``' is1950``StringRef``.1951 1952For more information on choosing string containers for APIs, please see1953:ref:`Passing Strings <string_apis>`.1954 1955.. _dss_stringref:1956 1957llvm/ADT/StringRef.h1958^^^^^^^^^^^^^^^^^^^^1959 1960The ``StringRef`` class is a simple value class that contains a pointer to a1961character and a length, and is quite related to the :ref:`ArrayRef1962<dss_arrayref>` class (but specialized for arrays of characters).  Because1963``StringRef`` carries a length with it, it safely handles strings with embedded nul1964characters in it, getting the length does not require a strlen call, and it even1965has very convenient APIs for slicing and dicing the character range that it1966represents.1967 1968``StringRef`` is ideal for passing simple strings around that are known to be live,1969either because they are C string literals, ``std::string``, a C array, or a1970``SmallVector``.  Each of these cases has an efficient implicit conversion to1971``StringRef``, which doesn't result in a dynamic ``strlen`` being executed.1972 1973``StringRef`` has a few major limitations which make more powerful string containers1974useful:1975 1976#. You cannot directly convert a ``StringRef`` to a ``const char*`` because there is1977   no way to add a trailing nul (unlike the ``.c_str()`` method on various stronger1978   classes).1979 1980#. ``StringRef`` doesn't own or keep alive the underlying string bytes.1981   As such, it can easily lead to dangling pointers, and is not suitable for1982   embedding in datastructures in most cases (instead, use an ``std::string`` or1983   something like that).1984 1985#. For the same reason, ``StringRef`` cannot be used as the return value of a1986   method if the method "computes" the result string.  Instead, use ``std::string``.1987 1988#. ``StringRef``'s do not allow you to mutate the pointed-to string bytes and it1989   doesn't allow you to insert or remove bytes from the range.  For editing1990   operations like this, it interoperates with the :ref:`Twine <dss_twine>`1991   class.1992 1993Because of its strengths and limitations, it is very common for a function to1994take a ``StringRef`` and for a method on an object to return a ``StringRef`` that points1995into some string that it owns.1996 1997.. _dss_twine:1998 1999llvm/ADT/Twine.h2000^^^^^^^^^^^^^^^^2001 2002The Twine class is used as an intermediary datatype for APIs that want to take a2003string that can be constructed inline with a series of concatenations.  Twine2004works by forming recursive instances of the Twine datatype (a simple value2005object) on the stack as temporary objects, linking them together into a tree2006which is then linearized when the Twine is consumed.  Twine is only safe to use2007as the argument to a function, and should always be a const reference, e.g.:2008 2009.. code-block:: c++2010 2011  void foo(const Twine &T);2012  ...2013  StringRef X = ...2014  unsigned i = ...2015  foo(X + "." + Twine(i));2016 2017This example forms a string like "blarg.42" by concatenating the values2018together, and does not form intermediate strings containing "blarg" or "blarg.".2019 2020Because Twine is constructed with temporary objects on the stack, and because2021these instances are destroyed at the end of the current statement, it is an2022inherently dangerous API.  For example, this simple variant contains undefined2023behavior and will probably crash:2024 2025.. code-block:: c++2026 2027  void foo(const Twine &T);2028  ...2029  StringRef X = ...2030  unsigned i = ...2031  const Twine &Tmp = X + "." + Twine(i);2032  foo(Tmp);2033 2034... because the temporaries are destroyed before the call.  That said, ``Twine``'s2035are much more efficient than intermediate ``std::string`` temporaries, and they work2036really well with ``StringRef``.  Just be aware of their limitations.2037 2038.. _dss_smallstring:2039 2040llvm/ADT/SmallString.h2041^^^^^^^^^^^^^^^^^^^^^^2042 2043``SmallString`` is a subclass of :ref:`SmallVector <dss_smallvector>` that adds some2044convenience APIs like += that takes ``StringRef``'s.  ``SmallString`` avoids allocating2045memory in the case when the preallocated space is enough to hold its data, and2046it calls back to general heap allocation when required.  Since it owns its data,2047it is very safe to use and supports full mutation of the string.2048 2049Like ``SmallVector``'s, the big downside to ``SmallString`` is their sizeof.  While they2050are optimized for small strings, they themselves are not particularly small.2051This means that they work great for temporary scratch buffers on the stack, but2052should not generally be put into the heap: it is very rare to see a ``SmallString``2053as the member of a frequently-allocated heap data structure or returned2054by-value.2055 2056.. _dss_stdstring:2057 2058std::string2059^^^^^^^^^^^2060 2061The standard C++ ``std::string`` class is a very general class that (like2062``SmallString``) owns its underlying data.  sizeof(std::string) is very reasonable2063so it can be embedded into heap data structures and returned by-value.  On the2064other hand, ``std::string`` is highly inefficient for inline editing (e.g.2065concatenating a bunch of stuff together) and because it is provided by the2066standard library, its performance characteristics depend a lot of the host2067standard library (e.g., libc++ and MSVC provide a highly optimized string class,2068GCC contains a really slow implementation).2069 2070The major disadvantage of ``std::string`` is that almost every operation that makes2071them larger can allocate memory, which is slow.  As such, it is better to use2072``SmallVector`` or ``Twine`` as a scratch buffer, but then use ``std::string`` to persist2073the result.2074 2075.. _ds_set:2076 2077Set-Like Containers (std::set, SmallSet, SetVector, etc)2078--------------------------------------------------------2079 2080Set-like containers are useful when you need to canonicalize multiple values2081into a single representation.  There are several different choices for how to do2082this, providing various trade-offs.2083 2084.. _dss_sortedvectorset:2085 2086A sorted 'vector'2087^^^^^^^^^^^^^^^^^2088 2089If you intend to insert a lot of elements, then do a lot of queries, a great2090approach is to use an ``std::vector`` (or other sequential container) with2091``std::sort``+``std::unique`` to remove duplicates.  This approach works really well if2092your usage pattern has these two distinct phases (insert then query), and can be2093coupled with a good choice of :ref:`sequential container <ds_sequential>`.2094 2095This combination provides the several nice properties: the result data is2096contiguous in memory (good for cache locality), has few allocations, is easy to2097address (iterators in the final vector are just indices or pointers), and can be2098efficiently queried with a standard binary search (e.g.2099``std::lower_bound``; if you want the whole range of elements comparing2100equal, use ``std::equal_range``).2101 2102.. _dss_smallset:2103 2104llvm/ADT/SmallSet.h2105^^^^^^^^^^^^^^^^^^^2106 2107If you have a set-like data structure that is usually small and whose elements2108are reasonably small, a ``SmallSet<Type, N>`` is a good choice.  This set has2109space for N elements in place (thus, if the set is dynamically smaller than N,2110no malloc traffic is required) and accesses them with a simple linear search.2111When the set grows beyond N elements, it allocates a more expensive2112representation that guarantees efficient access (for most types, it falls back2113to :ref:`std::set <dss_set>`, but for pointers it uses something far better,2114:ref:`SmallPtrSet <dss_smallptrset>`.2115 2116The magic of this class is that it handles small sets extremely efficiently, but2117gracefully handles extremely large sets without loss of efficiency.2118 2119.. _dss_smallptrset:2120 2121llvm/ADT/SmallPtrSet.h2122^^^^^^^^^^^^^^^^^^^^^^2123 2124``SmallPtrSet`` has all the advantages of ``SmallSet`` (and a ``SmallSet`` of2125pointers is transparently implemented with a ``SmallPtrSet``). If more than N2126insertions are performed, a single quadratically probed hash table is allocated2127and grows as needed, providing extremely efficient access (constant time2128insertion/deleting/queries with low constant factors) and is very stingy with2129malloc traffic.2130 2131Note that, unlike :ref:`std::set <dss_set>`, the iterators of ``SmallPtrSet``2132are invalidated whenever an insertion or erasure occurs. The ``remove_if``2133method can be used to remove elements while iterating over the set.2134 2135Also, the values visited by the iterators are not visited in sorted order.2136 2137.. _dss_stringset:2138 2139llvm/ADT/StringSet.h2140^^^^^^^^^^^^^^^^^^^^2141 2142``StringSet`` is a thin wrapper around :ref:`StringMap\<char\> <dss_stringmap>`,2143and it allows efficient storage and retrieval of unique strings.2144 2145Functionally analogous to ``SmallSet<StringRef>``, ``StringSet`` also supports2146iteration. (The iterator dereferences to a ``StringMapEntry<char>``, so you2147need to call ``i->getKey()`` to access the item of the StringSet.)  On the2148other hand, ``StringSet`` doesn't support range-insertion and2149copy-construction, which :ref:`SmallSet <dss_smallset>` and :ref:`SmallPtrSet2150<dss_smallptrset>` do support.2151 2152.. _dss_denseset:2153 2154llvm/ADT/DenseSet.h2155^^^^^^^^^^^^^^^^^^^2156 2157``DenseSet`` is a simple quadratically probed hash table.  It excels at supporting2158small values: it uses a single allocation to hold all of the pairs that are2159currently inserted in the set.  ``DenseSet`` is a great way to unique small values2160that are not simple pointers (use :ref:`SmallPtrSet <dss_smallptrset>` for2161pointers).  Note that ``DenseSet`` has the same requirements for the value type that2162:ref:`DenseMap <dss_densemap>` has.2163 2164.. _dss_radixtree:2165 2166llvm/ADT/RadixTree.h2167^^^^^^^^^^^^^^^^^^^^2168 2169``RadixTree`` is a trie-based data structure that stores range-like keys and2170their associated values. It is particularly efficient for storing keys that2171share common prefixes, as it can compress these prefixes to save memory. It2172supports efficient search of matching prefixes.2173 2174.. _dss_sparseset:2175 2176llvm/ADT/SparseSet.h2177^^^^^^^^^^^^^^^^^^^^2178 2179SparseSet holds a small number of objects identified by unsigned keys of2180moderate size.  It uses a lot of memory, but provides operations that are almost2181as fast as a vector.  Typical keys are physical registers, virtual registers, or2182numbered basic blocks.2183 2184SparseSet is useful for algorithms that need very fast clear/find/insert/erase2185and fast iteration over small sets.  It is not intended for building composite2186data structures.2187 2188.. _dss_sparsemultiset:2189 2190llvm/ADT/SparseMultiSet.h2191^^^^^^^^^^^^^^^^^^^^^^^^^^^^2192 2193``SparseMultiSet`` adds multiset behavior to ``SparseSet``, while retaining ``SparseSet``'s2194desirable attributes. Like ``SparseSet``, it typically uses a lot of memory, but2195provides operations that are almost as fast as a vector.  Typical keys are2196physical registers, virtual registers, or numbered basic blocks.2197 2198``SparseMultiSet`` is useful for algorithms that need very fast2199clear/find/insert/erase of the entire collection, and iteration over sets of2200elements sharing a key. It is often a more efficient choice than using composite2201data structures (e.g., vector-of-vectors, map-of-vectors). It is not intended for2202building composite data structures.2203 2204.. _dss_FoldingSet:2205 2206llvm/ADT/FoldingSet.h2207^^^^^^^^^^^^^^^^^^^^^2208 2209``FoldingSet`` is an aggregate class that is really good at uniquing2210expensive-to-create or polymorphic objects.  It is a combination of a chained2211hash table with intrusive links (uniqued objects are required to inherit from2212``FoldingSetNode``) that uses :ref:`SmallVector <dss_smallvector>` as part of its ID2213process.2214 2215Consider a case where you want to implement a "getOrCreateFoo" method for a2216complex object (for example, a node in the code generator).  The client has a2217description of **what** it wants to generate (it knows the opcode and all the2218operands), but we don't want to 'new' a node, then try inserting it into a set2219only to find out it already exists, at which point we would have to delete it2220and return the node that already exists.2221 2222To support this style of client, ``FoldingSet`` perform a query with a2223``FoldingSetNodeID`` (which wraps ``SmallVector``) that can be used to describe the2224element that we want to query for.  The query either returns the element2225matching the ID or it returns an opaque ID that indicates where insertion should2226take place.  Construction of the ID usually does not require heap traffic.2227 2228Because ``FoldingSet`` uses intrusive links, it can support polymorphic objects in2229the set (for example, you can have ``SDNode`` instances mixed with ``LoadSDNodes``).2230Because the elements are individually allocated, pointers to the elements are2231stable: inserting or removing elements does not invalidate any pointers to other2232elements.2233 2234.. _dss_set:2235 2236<set>2237^^^^^2238 2239``std::set`` is a reasonable all-around set class, which is decent at many2240things but great at nothing.  ``std::set`` allocates memory for each element2241inserted (thus it is very malloc intensive) and typically stores three pointers2242per element in the set (thus adding a large amount of per-element space2243overhead).  It offers guaranteed log(n) performance, which is not particularly2244fast from a complexity standpoint (particularly if the elements of the set are2245expensive to compare, like strings), and has extremely high constant factors for2246lookup, insertion and removal.2247 2248The advantages of ``std::set`` are that its iterators are stable (deleting or2249inserting an element from the set does not affect iterators or pointers to other2250elements) and that iteration over the set is guaranteed to be in sorted order.2251If the elements in the set are large, then the relative overhead of the pointers2252and malloc traffic is not a big deal, but if the elements of the set are small,2253``std::set`` is almost never a good choice.2254 2255.. _dss_setvector:2256 2257llvm/ADT/SetVector.h2258^^^^^^^^^^^^^^^^^^^^2259 2260LLVM's ``SetVector<Type>`` is an adapter class that combines your choice of a2261set-like container along with a :ref:`Sequential Container <ds_sequential>` The2262important property that this provides is efficient insertion with uniquing2263(duplicate elements are ignored) with iteration support.  It implements this by2264inserting elements into both a set-like container and the sequential container,2265using the set-like container for uniquing and the sequential container for2266iteration.2267 2268The difference between ``SetVector`` and other sets is that the order of iteration2269is guaranteed to match the order of insertion into the ``SetVector``.  This property2270is really important for things like sets of pointers.  Because pointer values2271are non-deterministic (e.g., vary across runs of the program on different2272machines), iterating over the pointers in the set will not be in a well-defined2273order.2274 2275The drawback of ``SetVector`` is that it requires twice as much space as a normal2276set and has the sum of constant factors from the set-like container and the2277sequential container that it uses.  Use it **only** if you need to iterate over2278the elements in a deterministic order.  ``SetVector`` is also expensive to delete2279elements out of (linear time), unless you use its "pop_back" method, which is2280faster.2281 2282``SetVector`` is an adapter class that defaults to using ``std::vector`` and a2283size 16 ``SmallSet`` for the underlying containers, so it is quite expensive.2284However, ``"llvm/ADT/SetVector.h"`` also provides a ``SmallSetVector`` class,2285which defaults to using a ``SmallVector`` and ``SmallSet`` of a specified size.2286If you use this, and if your sets are dynamically smaller than ``N``, you will2287save a lot of heap traffic.2288 2289.. _dss_uniquevector:2290 2291llvm/ADT/UniqueVector.h2292^^^^^^^^^^^^^^^^^^^^^^^2293 2294UniqueVector is similar to :ref:`SetVector <dss_setvector>` but it retains a2295unique ID for each element inserted into the set.  It internally contains a map2296and a vector, and it assigns a unique ID for each value inserted into the set.2297 2298UniqueVector is very expensive: its cost is the sum of the cost of maintaining2299both the map and vector, it has high complexity, high constant factors, and2300produces a lot of malloc traffic.  It should be avoided.2301 2302.. _dss_immutableset:2303 2304llvm/ADT/ImmutableSet.h2305^^^^^^^^^^^^^^^^^^^^^^^2306 2307``ImmutableSet`` is an immutable (functional) set implementation based on an AVL2308tree.  Adding or removing elements is done through a Factory object and results2309in the creation of a new ``ImmutableSet`` object.  If an ``ImmutableSet`` already exists2310with the given contents, then the existing one is returned; equality is compared2311with a ``FoldingSetNodeID``.  The time and space complexity of add or remove2312operations is logarithmic in the size of the original set.2313 2314There is no method for returning an element of the set, you can only check for2315membership.2316 2317.. _dss_otherset:2318 2319Other Set-Like Container Options2320^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2321 2322The STL provides several other options, such as ``std::multiset`` and2323``std::unordered_set``.  We never use containers like ``unordered_set`` because2324they are generally very expensive (each insertion requires a malloc).2325 2326``std::multiset`` is useful if you're not interested in elimination of duplicates,2327but has all the drawbacks of :ref:`std::set <dss_set>`.  A sorted vector2328(where you don't delete duplicate entries) or some other approach is almost2329always better.2330 2331.. _ds_map:2332 2333Map-Like Containers (std::map, DenseMap, etc)2334---------------------------------------------2335 2336Map-like containers are useful when you want to associate data to a key.  As2337usual, there are a lot of different ways to do this. :)2338 2339.. _dss_sortedvectormap:2340 2341A sorted 'vector'2342^^^^^^^^^^^^^^^^^2343 2344If your usage pattern follows a strict insert-then-query approach, you can2345trivially use the same approach as :ref:`sorted vectors for set-like containers2346<dss_sortedvectorset>`.  The only difference is that your query function (which2347uses ``std::lower_bound`` to get efficient log(n) lookup) should only compare the2348key, not both the key and value.  This yields the same advantages as sorted2349vectors for sets.2350 2351.. _dss_stringmap:2352 2353llvm/ADT/StringMap.h2354^^^^^^^^^^^^^^^^^^^^2355 2356Strings are commonly used as keys in maps, and they are difficult to support2357efficiently: they are variable length, inefficient to hash and compare when2358long, expensive to copy, etc.  ``StringMap`` is a specialized container designed to2359cope with these issues.  It supports mapping an arbitrary range of bytes to an2360arbitrary other object.2361 2362The ``StringMap`` implementation uses a quadratically-probed hash table, where the2363buckets store a pointer to the heap allocated entries (and some other stuff).2364The entries in the map must be heap allocated because the strings are variable2365length.  The string data (key) and the element object (value) are stored in the2366same allocation with the string data immediately after the element object.2367This container guarantees the "``(char*)(&Value+1)``" points to the key string2368for a value.2369 2370The ``StringMap`` is very fast for several reasons: quadratic probing is very cache2371efficient for lookups, the hash value of strings in buckets is not recomputed2372when looking up an element, ``StringMap`` rarely has to touch the memory for2373unrelated objects when looking up a value (even when hash collisions happen),2374hash table growth does not recompute the hash values for strings already in the2375table, and each pair in the map is store in a single allocation (the string data2376is stored in the same allocation as the Value of a pair).2377 2378``StringMap`` also provides query methods that take byte ranges, so it only ever2379copies a string if a value is inserted into the table.2380 2381``StringMap`` iteration order, however, is not guaranteed to be deterministic, so2382any uses which require that should instead use a ``std::map``.2383 2384.. _dss_indexmap:2385 2386llvm/ADT/IndexedMap.h2387^^^^^^^^^^^^^^^^^^^^^2388 2389``IndexedMap`` is a specialized container for mapping small dense integers (or2390values that can be mapped to small dense integers) to some other type.  It is2391internally implemented as a vector with a mapping function that maps the keys2392to the dense integer range.2393 2394This is useful for cases like virtual registers in the LLVM code generator: they2395have a dense mapping that is offset by a compile-time constant (the first2396virtual register ID).2397 2398.. _dss_densemap:2399 2400llvm/ADT/DenseMap.h2401^^^^^^^^^^^^^^^^^^^2402 2403``DenseMap`` is a simple quadratically probed hash table.  It excels at supporting2404small keys and values: it uses a single allocation to hold all of the pairs2405that are currently inserted in the map.  ``DenseMap`` is a great way to map2406pointers to pointers, or map other small types to each other.2407 2408There are several aspects of ``DenseMap`` that you should be aware of, however.2409The iterators in a ``DenseMap`` are invalidated whenever an insertion occurs,2410unlike ``map``.  Also, because ``DenseMap`` allocates space for a large number of2411key/value pairs (it starts with 64 by default), it will waste a lot of space if2412your keys or values are large.  Finally, you must implement a partial2413specialization of ``DenseMapInfo`` for the key that you want, if it isn't already2414supported.  This is required to tell ``DenseMap`` about two special marker values2415(which can never be inserted into the map) that it needs internally.2416 2417``DenseMap``'s ``find_as()`` method supports lookup operations using an alternate key2418type.  This is useful in cases where the normal key type is expensive to2419construct, but cheap to compare against.  The ``DenseMapInfo`` is responsible for2420defining the appropriate comparison and hashing methods for each alternate key2421type used.2422 2423``DenseMap.h`` also contains a ``SmallDenseMap`` variant, that similar to2424:ref:`SmallVector <dss_smallvector>` performs no heap allocation until the2425number of elements in the template parameter N are exceeded.2426 2427.. _dss_valuemap:2428 2429llvm/IR/ValueMap.h2430^^^^^^^^^^^^^^^^^^^2431 2432ValueMap is a wrapper around a :ref:`DenseMap <dss_densemap>` mapping2433``Value*``\ s (or subclasses) to another type.  When a Value is deleted or2434RAUW'ed, ``ValueMap`` will update itself so the new version of the key is mapped to2435the same value, just as if the key were a WeakVH.  You can configure exactly how2436this happens, and what else happens on these two events, by passing a ``Config``2437parameter to the ``ValueMap`` template.2438 2439.. _dss_intervalmap:2440 2441llvm/ADT/IntervalMap.h2442^^^^^^^^^^^^^^^^^^^^^^2443 2444``IntervalMap`` is a compact map for small keys and values.  It maps key intervals2445instead of single keys, and it will automatically coalesce adjacent intervals.2446When the map only contains a few intervals, they are stored in the map object2447itself to avoid allocations.2448 2449The ``IntervalMap`` iterators are quite big, so they should not be passed around as2450STL iterators.  The heavyweight iterators allow a smaller data structure.2451 2452.. _dss_intervaltree:2453 2454llvm/ADT/IntervalTree.h2455^^^^^^^^^^^^^^^^^^^^^^^2456 2457``llvm::IntervalTree`` is a light tree data structure to hold intervals. It2458allows finding all intervals that overlap with any given point. At this time,2459it does not support any deletion or rebalancing operations.2460 2461The ``IntervalTree`` is designed to be set up once, and then queried without any2462further additions.2463 2464.. _dss_map:2465 2466<map>2467^^^^^2468 2469``std::map`` has similar characteristics to :ref:`std::set <dss_set>`: it uses a2470single allocation per pair inserted into the map, it offers log(n) lookup with2471an extremely large constant factor, imposes a space penalty of 3 pointers per2472pair in the map, etc.2473 2474``std::map`` is most useful when your keys or values are very large, if you need to2475iterate over the collection in sorted order, or if you need stable iterators2476into the map (i.e., they don't get invalidated if an insertion or deletion of2477another element takes place).2478 2479.. _dss_mapvector:2480 2481llvm/ADT/MapVector.h2482^^^^^^^^^^^^^^^^^^^^2483 2484``MapVector<KeyT,ValueT>`` provides a subset of the ``DenseMap`` interface.  The2485main difference is that the iteration order is guaranteed to be the insertion2486order, making it an easy (but somewhat expensive) solution for non-deterministic2487iteration over maps of pointers.2488 2489It is implemented by mapping from key to an index in a vector of key,value2490pairs.  This provides fast lookup and iteration, but has two main drawbacks:2491the key is stored twice and removing elements takes linear time.  If it is2492necessary to remove elements, it's best to remove them in bulk using2493``remove_if()``.2494 2495.. _dss_inteqclasses:2496 2497llvm/ADT/IntEqClasses.h2498^^^^^^^^^^^^^^^^^^^^^^^2499 2500``IntEqClasses`` provides a compact representation of equivalence classes of small2501integers.  Initially, each integer in the range 0..n-1 has its own equivalence2502class.  Classes can be joined by passing two class representatives to the2503``join(a, b)`` method.  Two integers are in the same class when ``findLeader()`` returns2504the same representative.2505 2506Once all equivalence classes are formed, the map can be compressed so each2507integer 0..n-1 maps to an equivalence class number in the range 0..m-1, where m2508is the total number of equivalence classes.  The map must be uncompressed before2509it can be edited again.2510 2511.. _dss_immutablemap:2512 2513llvm/ADT/ImmutableMap.h2514^^^^^^^^^^^^^^^^^^^^^^^2515 2516``ImmutableMap`` is an immutable (functional) map implementation based on an AVL2517tree.  Adding or removing elements is done through a Factory object and results2518in the creation of a new ``ImmutableMap`` object.  If an ``ImmutableMap`` already exists2519with the given key set, then the existing one is returned; equality is compared2520with a ``FoldingSetNodeID``.  The time and space complexity of add or remove2521operations is logarithmic in the size of the original map.2522 2523.. _dss_othermap:2524 2525Other Map-Like Container Options2526^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2527 2528The STL provides several other options, such as ``std::multimap`` and2529``std::unordered_map``.  We never use containers like ``unordered_map`` because2530they are generally very expensive (each insertion requires a malloc).2531 2532``std::multimap`` is useful if you want to map a key to multiple values, but has all2533the drawbacks of ``std::map``.  A sorted vector or some other approach is almost2534always better.2535 2536.. _ds_bit:2537 2538Bit storage containers2539------------------------------------------------------------------------2540 2541There are several bit storage containers, and choosing when to use each is2542relatively straightforward.2543 2544One additional option is ``std::vector<bool>``: we discourage its use for two2545reasons 1) the implementation in many common compilers (e.g.,  commonly2546available versions of GCC) is extremely inefficient and 2) the C++ standards2547committee is likely to deprecate this container and/or change it significantly2548somehow.  In any case, please don't use it.2549 2550.. _dss_bitvector:2551 2552BitVector2553^^^^^^^^^2554 2555The ``BitVector`` container provides a dynamic size set of bits for manipulation.2556It supports individual bit setting/testing, as well as set operations.  The set2557operations take time O(size of bitvector), but operations are performed one word2558at a time, instead of one bit at a time.  This makes the ``BitVector`` very fast for2559set operations compared to other containers.  Use the ``BitVector`` when you expect2560the number of set bits to be high (i.e., a dense set).2561 2562.. _dss_smallbitvector:2563 2564SmallBitVector2565^^^^^^^^^^^^^^2566 2567The SmallBitVector container provides the same interface as BitVector, but it is2568optimized for the case where only a small number of bits, less than 25 or so,2569are needed.  It also transparently supports larger bit counts, but slightly less2570efficiently than a plain BitVector, so SmallBitVector should only be used when2571larger counts are rare.2572 2573At this time, SmallBitVector does not support set operations (and, or, xor), and2574its operator[] does not provide an assignable lvalue.2575 2576.. _dss_sparsebitvector:2577 2578SparseBitVector2579^^^^^^^^^^^^^^^2580 2581The ``SparseBitVector`` container is much like ``BitVector``, with one major difference:2582Only the bits that are set, are stored.  This makes the ``SparseBitVector`` much2583more space efficient than ``BitVector`` when the set is sparse, as well as making2584set operations O(number of set bits) instead of O(size of universe).  The2585downside to the ``SparseBitVector`` is that setting and testing of random bits is2586O(N), and on large ``SparseBitVectors``, this can be slower than ``BitVector``.  In our2587implementation, setting or testing bits in sorted order (either forwards or2588reverse) is O(1) worst case.  Testing and setting bits within 128 bits (depends2589on size) of the current bit is also O(1).  As a general statement,2590testing/setting bits in a ``SparseBitVector`` is O(distance away from last set bit).2591 2592.. _dss_coalescingbitvector:2593 2594CoalescingBitVector2595^^^^^^^^^^^^^^^^^^^2596 2597The ``CoalescingBitVector`` container is similar in principle to a ``SparseBitVector``,2598but is optimized to represent large contiguous ranges of set bits compactly. It2599does this by coalescing contiguous ranges of set bits into intervals. Searching2600for a bit in a ``CoalescingBitVector`` is O(log(gaps between contiguous ranges)).2601 2602``CoalescingBitVector`` is a better choice than ``BitVector`` when gaps between ranges2603of set bits are large. It's a better choice than ``SparseBitVector`` when find()2604operations must have fast, predictable performance. However, it's not a good2605choice for representing sets which have lots of very short ranges. E.g. the set2606`{2*x : x \in [0, n)}` would be a pathological input.2607 2608.. _utility_functions:2609 2610Useful Utility Functions2611========================2612 2613LLVM implements a number of general utility functions used across the2614codebase. You can find the most common ones in ``STLExtras.h``2615(`doxygen <https://llvm.org/doxygen/STLExtras_8h.html>`__). Some of these wrap2616well-known C++ standard library functions, while others are unique to LLVM.2617 2618.. _uf_iteration:2619 2620Iterating over ranges2621---------------------2622 2623Sometimes you may want to iterate over more than range at a time or know the2624index of the index. LLVM provides custom utility functions to make that easier,2625without having to manually manage all iterators and/or indices:2626 2627.. _uf_zip:2628 2629The ``zip``\ * functions2630^^^^^^^^^^^^^^^^^^^^^^^^2631 2632``zip``\ * functions allow for iterating over elements from two or more ranges2633at the same time. For example:2634 2635.. code-block:: c++2636 2637    SmallVector<size_t> Counts = ...;2638    char Letters[26] = ...;2639    for (auto [Letter, Count] : zip_equal(Letters, Counts))2640      errs() << Letter << ": " << Count << "\n";2641 2642Note that the elements are provided through a 'reference wrapper' proxy type2643(tuple of references), which combined with the structured bindings declaration2644makes ``Letter`` and ``Count`` references to range elements. Any modification2645to these references will affect the elements of ``Letters`` or ``Counts``.2646 2647The ``zip``\ * functions support temporary ranges, for example:2648 2649.. code-block:: c++2650 2651    for (auto [Letter, Count] : zip(SmallVector<char>{'a', 'b', 'c'}, Counts))2652      errs() << Letter << ": " << Count << "\n";2653 2654The difference between the functions in the ``zip`` family is how they behave2655when the supplied ranges have different lengths:2656 2657* ``zip_equal`` -- requires all input ranges have the same length.2658* ``zip`` -- iteration stops when the end of the shortest range is reached.2659* ``zip_first`` -- requires the first range is the shortest one.2660* ``zip_longest`` -- iteration continues until the end of the longest range is2661  reached. The non-existent elements of shorter ranges are replaced with2662  ``std::nullopt``.2663 2664The length requirements are checked with ``assert``\ s.2665 2666As a rule of thumb, prefer to use ``zip_equal`` when you expect all2667ranges to have the same lengths, and consider alternative ``zip`` functions only2668when this is not the case. This is because ``zip_equal`` clearly communicates2669this same-length assumption and has the best (release-mode) runtime performance.2670 2671.. _uf_enumerate:2672 2673``enumerate``2674^^^^^^^^^^^^^2675 2676The ``enumerate`` functions allows to iterate over one or more ranges while2677keeping track of the index of the current loop iteration. For example:2678 2679.. code-block:: c++2680 2681    for (auto [Idx, BB, Value] : enumerate(Phi->blocks(),2682                                           Phi->incoming_values()))2683      errs() << "#" << Idx << " " << BB->getName() << ": " << *Value << "\n";2684 2685The current element index is provided as the first structured bindings element.2686Alternatively, the index and the element value can be obtained with the2687``index()`` and ``value()`` member functions:2688 2689.. code-block:: c++2690 2691    char Letters[26] = ...;2692    for (auto En : enumerate(Letters))2693      errs() << "#" << En.index() << " " << En.value() << "\n";2694 2695Note that ``enumerate`` has ``zip_equal`` semantics and provides elements2696through a 'reference wrapper' proxy, which makes them modifiable when accessed2697through structured bindings or the ``value()`` member function. When two or more2698ranges are passed, ``enumerate`` requires them to have equal lengths (checked2699with an ``assert``).2700 2701.. _debugging:2702 2703Debugging2704=========2705 2706See :doc:`Debugging LLVM <DebuggingLLVM>`.2707 2708.. _common:2709 2710Helpful Hints for Common Operations2711===================================2712 2713This section describes how to perform some very simple transformations of LLVM2714code.  This is meant to give examples of common idioms used, showing the2715practical side of LLVM transformations.2716 2717Because this is a "how-to" section, you should also read about the main classes2718that you will be working with.  The :ref:`Core LLVM Class Hierarchy Reference2719<coreclasses>` contains details and descriptions of the main classes that you2720should know about.2721 2722.. _inspection:2723 2724Basic Inspection and Traversal Routines2725---------------------------------------2726 2727The LLVM compiler infrastructure have many different data structures that may be2728traversed.  Following the example of the C++ standard template library, the2729techniques used to traverse these various data structures are all basically the2730same.  For an enumerable sequence of values, the ``XXXbegin()`` function (or2731method) returns an iterator to the start of the sequence, the ``XXXend()``2732function returns an iterator pointing to one past the last valid element of the2733sequence, and there is some ``XXXiterator`` data type that is common between the2734two operations.2735 2736Because the pattern for iteration is common across many different aspects of the2737program representation, the standard template library algorithms may be used on2738them, and it is easier to remember how to iterate.  First we show a few common2739examples of the data structures that need to be traversed.  Other data2740structures are traversed in very similar ways.2741 2742.. _iterate_function:2743 2744Iterating over the ``BasicBlock`` in a ``Function``2745^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2746 2747It's quite common to have a ``Function`` instance that you'd like to transform2748in some way; in particular, you'd like to manipulate its ``BasicBlock``\ s.  To2749facilitate this, you'll need to iterate over all of the ``BasicBlock``\ s that2750constitute the ``Function``.  The following is an example that prints the name2751of a ``BasicBlock`` and the number of ``Instruction``\ s it contains:2752 2753.. code-block:: c++2754 2755  Function &Func = ...2756  for (BasicBlock &BB : Func)2757    // Print out the name of the basic block if it has one, and then the2758    // number of instructions that it contains2759    errs() << "Basic block (name=" << BB.getName() << ") has "2760               << BB.size() << " instructions.\n";2761 2762.. _iterate_basicblock:2763 2764Iterating over the ``Instruction`` in a ``BasicBlock``2765^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2766 2767Just like when dealing with ``BasicBlock``\ s in ``Function``\ s, it's easy to2768iterate over the individual instructions that make up ``BasicBlock``\ s.  Here's2769a code snippet that prints out each instruction in a ``BasicBlock``:2770 2771.. code-block:: c++2772 2773  BasicBlock& BB = ...2774  for (Instruction &I : BB)2775     // The next statement works since operator<<(ostream&,...)2776     // is overloaded for Instruction&2777     errs() << I << "\n";2778 2779 2780However, this isn't really the best way to print out the contents of a2781``BasicBlock``!  Since the ostream operators are overloaded for virtually2782anything you'll care about, you could have just invoked the print routine on the2783basic block itself: ``errs() << BB << "\n";``.2784 2785.. _iterate_insiter:2786 2787Iterating over the ``Instruction`` in a ``Function``2788^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2789 2790If you're finding that you commonly iterate over a ``Function``'s2791``BasicBlock``\ s and then that ``BasicBlock``'s ``Instruction``\ s,2792``InstIterator`` should be used instead.  You'll need to include2793``llvm/IR/InstIterator.h`` (`doxygen2794<https://llvm.org/doxygen/InstIterator_8h.html>`__) and then instantiate2795``InstIterator``\ s explicitly in your code.  Here's a small example that shows2796how to dump all instructions in a function to the standard error stream:2797 2798.. code-block:: c++2799 2800  #include "llvm/IR/InstIterator.h"2801 2802  // F is a pointer to a Function instance2803  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)2804    errs() << *I << "\n";2805 2806Easy, isn't it?  You can also use ``InstIterator``\ s to fill a work list with2807its initial contents.  For example, if you wanted to initialize a work list to2808contain all instructions in a ``Function`` F, all you would need to do is2809something like:2810 2811.. code-block:: c++2812 2813  std::set<Instruction*> worklist;2814  // or better yet, SmallPtrSet<Instruction*, 64> worklist;2815 2816  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)2817    worklist.insert(&*I);2818 2819The STL set ``worklist`` would now contain all instructions in the ``Function``2820pointed to by F.2821 2822.. _iterate_convert:2823 2824Turning an iterator into a class pointer (and vice-versa)2825^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2826 2827Sometimes, it'll be useful to grab a reference (or pointer) to a class instance2828when all you've got at hand is an iterator.  Well, extracting a reference or a2829pointer from an iterator is very straightforward.  Assuming that ``i`` is a2830``BasicBlock::iterator`` and ``j`` is a ``BasicBlock::const_iterator``:2831 2832.. code-block:: c++2833 2834  Instruction& inst = *i;   // Grab reference to instruction reference2835  Instruction* pinst = &*i; // Grab pointer to instruction reference2836  const Instruction& inst = *j;2837 2838It's also possible to turn a class pointer into the corresponding iterator, and2839this is a constant time operation (very efficient).  The following code snippet2840illustrates use of the conversion constructors provided by LLVM iterators.  By2841using these, you can explicitly grab the iterator of something without actually2842obtaining it via iteration over some structure:2843 2844.. code-block:: c++2845 2846  void printNextInstruction(Instruction* inst) {2847    BasicBlock::iterator it(inst);2848    ++it; // After this line, it refers to the instruction after *inst2849    if (it != inst->getParent()->end()) errs() << *it << "\n";2850  }2851 2852.. _iterate_complex:2853 2854Finding call sites: a slightly more complex example2855^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2856 2857Say that you're writing a FunctionPass and would like to count all the locations2858in the entire module (that is, across every ``Function``) where a certain2859function (i.e., some ``Function *``) is already in scope.  As you'll learn2860later, you may want to use an ``InstVisitor`` to accomplish this in a much more2861straightforward manner, but this example will allow us to explore how you'd do2862it if you didn't have ``InstVisitor`` around.  In pseudo-code, this is what we2863want to do:2864 2865.. code-block:: none2866 2867  initialize callCounter to zero2868  for each Function f in the Module2869    for each BasicBlock b in f2870      for each Instruction i in b2871        if (i a Call and calls the given function)2872          increment callCounter2873 2874And the actual code is (remember, because we're writing a ``FunctionPass``, our2875``FunctionPass``-derived class simply has to override the ``runOnFunction``2876method):2877 2878.. code-block:: c++2879 2880  Function* targetFunc = ...;2881 2882  class OurFunctionPass : public FunctionPass {2883    public:2884      OurFunctionPass(): callCounter(0) { }2885 2886      virtual runOnFunction(Function& F) {2887        for (BasicBlock &B : F) {2888          for (Instruction &I: B) {2889            if (auto *CB = dyn_cast<CallBase>(&I)) {2890              // We know we've encountered some kind of call instruction (call,2891              // invoke, or callbr), so we need to determine if it's a call to2892              // the function pointed to by m_func or not.2893              if (CB->getCalledFunction() == targetFunc)2894                ++callCounter;2895            }2896          }2897        }2898      }2899 2900    private:2901      unsigned callCounter;2902  };2903 2904.. _iterate_chains:2905 2906Iterating over def-use & use-def chains2907^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2908 2909Frequently, we might have an instance of the ``Value`` class (`doxygen2910<https://llvm.org/doxygen/classllvm_1_1Value.html>`__) and we want to determine2911which ``User``\ s use the ``Value``.  The list of all ``User``\ s of a particular2912``Value`` is called a *def-use* chain.  For example, let's say we have a2913``Function*`` named ``F`` to a particular function ``foo``.  Finding all of the2914instructions that *use* ``foo`` is as simple as iterating over the *def-use*2915chain of ``F``:2916 2917.. code-block:: c++2918 2919  Function *F = ...;2920 2921  for (User *U : F->users()) {2922    if (Instruction *Inst = dyn_cast<Instruction>(U)) {2923      errs() << "F is used in instruction:\n";2924      errs() << *Inst << "\n";2925    }2926 2927Alternatively, it's common to have an instance of the ``User`` Class (`doxygen2928<https://llvm.org/doxygen/classllvm_1_1User.html>`__) and need to know what2929``Value``\ s are used by it.  The list of all ``Value``\ s used by a ``User`` is2930known as a *use-def* chain.  Instances of class ``Instruction`` are common2931``User`` s, so we might want to iterate over all of the values that a particular2932instruction uses (that is, the operands of the particular ``Instruction``):2933 2934.. code-block:: c++2935 2936  Instruction *pi = ...;2937 2938  for (Use &U : pi->operands()) {2939    Value *v = U.get();2940    // ...2941  }2942 2943Declaring objects as ``const`` is an important tool of enforcing mutation free2944algorithms (such as analyses, etc.).  For this purpose above iterators come in2945constant flavors as ``Value::const_use_iterator`` and2946``Value::const_op_iterator``.  They automatically arise when calling2947``use/op_begin()`` on ``const Value*``\ s or ``const User*``\ s respectively.2948Upon dereferencing, they return ``const Use*``\ s.  Otherwise the above patterns2949remain unchanged.2950 2951.. _iterate_preds:2952 2953Iterating over predecessors & successors of blocks2954^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2955 2956Iterating over the predecessors and successors of a block is quite easy with the2957routines defined in ``"llvm/IR/CFG.h"``.  Just use code like this to2958iterate over all predecessors of BB:2959 2960.. code-block:: c++2961 2962  #include "llvm/IR/CFG.h"2963  BasicBlock *BB = ...;2964 2965  for (BasicBlock *Pred : predecessors(BB)) {2966    // ...2967  }2968 2969Similarly, to iterate over successors use ``successors``.2970 2971.. _simplechanges:2972 2973Making simple changes2974---------------------2975 2976There are some primitive transformation operations present in the LLVM2977infrastructure that are worth knowing about.  When performing transformations,2978it's fairly common to manipulate the contents of basic blocks.  This section2979describes some of the common methods for doing so and gives example code.2980 2981.. _schanges_creating:2982 2983Creating and inserting new ``Instruction``\ s2984^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2985 2986*Instantiating Instructions*2987 2988Creation of ``Instruction``\ s is straightforward: simply call the constructor2989for the kind of instruction to instantiate and provide the necessary parameters.2990For example, an ``AllocaInst`` only *requires* a (const-ptr-to) ``Type``.  Thus:2991 2992.. code-block:: c++2993 2994  auto *ai = new AllocaInst(Type::Int32Ty);2995 2996will create an ``AllocaInst`` instance that represents the allocation of one2997integer in the current stack frame, at run time.  Each ``Instruction`` subclass2998is likely to have varying default parameters which change the semantics of the2999instruction, so refer to the `doxygen documentation for the subclass of3000Instruction <https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_ that3001you're interested in instantiating.3002 3003*Naming values*3004 3005It is very useful to name the values of instructions when you're able to, as3006this facilitates the debugging of your transformations.  If you end up looking3007at generated LLVM machine code, you definitely want to have logical names3008associated with the results of instructions!  By supplying a value for the3009``Name`` (default) parameter of the ``Instruction`` constructor, you associate a3010logical name with the result of the instruction's execution at run time.  For3011example, say that I'm writing a transformation that dynamically allocates space3012for an integer on the stack, and that integer is going to be used as some kind3013of index by some other code.  To accomplish this, I place an ``AllocaInst`` at3014the first point in the first ``BasicBlock`` of some ``Function``, and I'm3015intending to use it within the same ``Function``.  I might do:3016 3017.. code-block:: c++3018 3019  auto *pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc");3020 3021where ``indexLoc`` is now the logical name of the instruction's execution value,3022which is a pointer to an integer on the run time stack.3023 3024*Inserting instructions*3025 3026There are essentially three ways to insert an ``Instruction`` into an existing3027sequence of instructions that form a ``BasicBlock``:3028 3029* Insertion into the instruction list of the ``BasicBlock``3030 3031  Given a ``BasicBlock* pb``, an ``Instruction* pi`` within that ``BasicBlock``,3032  and a newly-created instruction we wish to insert before ``*pi``, we do the3033  following:3034 3035  .. code-block:: c++3036 3037      BasicBlock *pb = ...;3038      Instruction *pi = ...;3039      auto *newInst = new Instruction(...);3040 3041      newInst->insertBefore(pi); // Inserts newInst before pi3042 3043  Appending to the end of a ``BasicBlock`` is so common that the ``Instruction``3044  class and ``Instruction``-derived classes provide constructors which take a3045  pointer to a ``BasicBlock`` to be appended to.  For example code that looked3046  like:3047 3048  .. code-block:: c++3049 3050    BasicBlock *pb = ...;3051    auto *newInst = new Instruction(...);3052 3053    newInst->insertInto(pb, pb->end()); // Appends newInst to pb3054 3055  becomes:3056 3057  .. code-block:: c++3058 3059    BasicBlock *pb = ...;3060    auto *newInst = new Instruction(..., pb);3061 3062  which is much cleaner, especially if you are creating long instruction3063  streams.3064 3065* Insertion using an instance of ``IRBuilder``3066 3067  Inserting several ``Instruction``\ s can be quite laborious using the previous3068  methods. The ``IRBuilder`` is a convenience class that can be used to add3069  several instructions to the end of a ``BasicBlock`` or before a particular3070  ``Instruction``. It also supports constant folding and renaming named3071  registers (see ``IRBuilder``'s template arguments).3072 3073  The example below demonstrates a very simple use of the ``IRBuilder`` where3074  three instructions are inserted before the instruction ``pi``. The first two3075  instructions are Call instructions and third instruction multiplies the return3076  value of the two calls.3077 3078  .. code-block:: c++3079 3080    Instruction *pi = ...;3081    IRBuilder<> Builder(pi);3082    CallInst* callOne = Builder.CreateCall(...);3083    CallInst* callTwo = Builder.CreateCall(...);3084    Value* result = Builder.CreateMul(callOne, callTwo);3085 3086  The example below is similar to the above example except that the created3087  ``IRBuilder`` inserts instructions at the end of the ``BasicBlock`` ``pb``.3088 3089  .. code-block:: c++3090 3091    BasicBlock *pb = ...;3092    IRBuilder<> Builder(pb);3093    CallInst* callOne = Builder.CreateCall(...);3094    CallInst* callTwo = Builder.CreateCall(...);3095    Value* result = Builder.CreateMul(callOne, callTwo);3096 3097  See :doc:`tutorial/LangImpl03` for a practical use of the ``IRBuilder``.3098 3099 3100.. _schanges_deleting:3101 3102Deleting Instructions3103^^^^^^^^^^^^^^^^^^^^^3104 3105Deleting an instruction from an existing sequence of instructions that form a3106``BasicBlock`` is very straightforward: just call the instruction's3107``eraseFromParent()`` method.  For example:3108 3109.. code-block:: c++3110 3111  Instruction *I = .. ;3112  I->eraseFromParent();3113 3114This unlinks the instruction from its containing basic block and deletes it.  If3115you'd just like to unlink the instruction from its containing basic block but3116not delete it, you can use the ``removeFromParent()`` method.3117 3118.. _schanges_replacing:3119 3120Replacing an Instruction with another Value3121^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3122 3123Replacing individual instructions3124"""""""""""""""""""""""""""""""""3125 3126Including "`llvm/Transforms/Utils/BasicBlockUtils.h3127<https://llvm.org/doxygen/BasicBlockUtils_8h_source.html>`_" permits use of two3128very useful replace functions: ``ReplaceInstWithValue`` and3129``ReplaceInstWithInst``.3130 3131.. _schanges_deleting_sub:3132 3133Deleting Instructions3134"""""""""""""""""""""3135 3136* ``ReplaceInstWithValue``3137 3138  This function replaces all uses of a given instruction with a value, and then3139  removes the original instruction.  The following example illustrates the3140  replacement of the result of a particular ``AllocaInst`` that allocates memory3141  for a single integer with a null pointer to an integer.3142 3143  .. code-block:: c++3144 3145    AllocaInst* instToReplace = ...;3146    BasicBlock::iterator ii(instToReplace);3147 3148    ReplaceInstWithValue(ii, Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty)));3149 3150* ``ReplaceInstWithInst``3151 3152  This function replaces a particular instruction with another instruction,3153  inserting the new instruction into the basic block at the location where the3154  old instruction was, and replacing any uses of the old instruction with the3155  new instruction.  The following example illustrates the replacement of one3156  ``AllocaInst`` with another.3157 3158  .. code-block:: c++3159 3160    AllocaInst* instToReplace = ...;3161    BasicBlock::iterator ii(instToReplace);3162 3163    ReplaceInstWithInst(instToReplace->getParent(), ii,3164                        new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt"));3165 3166 3167Replacing multiple uses of Users and Values3168"""""""""""""""""""""""""""""""""""""""""""3169 3170You can use ``Value::replaceAllUsesWith`` and ``User::replaceUsesOfWith`` to3171change more than one use at a time.  See the doxygen documentation for the3172`Value Class <https://llvm.org/doxygen/classllvm_1_1Value.html>`_ and `User Class3173<https://llvm.org/doxygen/classllvm_1_1User.html>`_, respectively, for more3174information.3175 3176.. _schanges_deletingGV:3177 3178Deleting GlobalVariables3179^^^^^^^^^^^^^^^^^^^^^^^^3180 3181Deleting a global variable from a module is just as easy as deleting an3182Instruction.  First, you must have a pointer to the global variable that you3183wish to delete.  You use this pointer to erase it from its parent, the module.3184For example:3185 3186.. code-block:: c++3187 3188  GlobalVariable *GV = .. ;3189 3190  GV->eraseFromParent();3191 3192 3193.. _threading:3194 3195Threads and LLVM3196================3197 3198This section describes the interaction of the LLVM APIs with multithreading,3199both on the part of client applications, and in the JIT, in the hosted3200application.3201 3202Note that LLVM's support for multithreading is still relatively young.  Up3203through version 2.5, the execution of threaded hosted applications was3204supported, but not threaded client access to the APIs.  While this use case is3205now supported, clients *must* adhere to the guidelines specified below to ensure3206proper operation in multithreaded mode.3207 3208Note that, on Unix-like platforms, LLVM requires the presence of GCC's atomic3209intrinsics in order to support threaded operation.  If you need a3210multithreading-capable LLVM on a platform without a suitably modern system3211compiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and3212using the resultant compiler to build a copy of LLVM with multithreading3213support.3214 3215.. _shutdown:3216 3217Ending Execution with ``llvm_shutdown()``3218-----------------------------------------3219 3220When you are done using the LLVM APIs, you should call ``llvm_shutdown()`` to3221deallocate memory used for internal structures.3222 3223.. _managedstatic:3224 3225Lazy Initialization with ``ManagedStatic``3226------------------------------------------3227 3228``ManagedStatic`` is a utility class in LLVM used to implement static3229initialization of static resources, such as the global type tables.  In a3230single-threaded environment, it implements a simple lazy initialization scheme.3231When LLVM is compiled with support for multi-threading, however, it uses3232double-checked locking to implement thread-safe lazy initialization.3233 3234.. _llvmcontext:3235 3236Achieving Isolation with ``LLVMContext``3237----------------------------------------3238 3239``LLVMContext`` is an opaque class in the LLVM API which clients can use to3240operate multiple, isolated instances of LLVM concurrently within the same3241address space.  For instance, in a hypothetical compile-server, the compilation3242of an individual translation unit is conceptually independent from all the3243others, and it would be desirable to be able to compile incoming translation3244units concurrently on independent server threads.  Fortunately, ``LLVMContext``3245exists to enable just this kind of scenario!3246 3247Conceptually, ``LLVMContext`` provides isolation.  Every LLVM entity3248(``Module``\ s, ``Value``\ s, ``Type``\ s, ``Constant``\ s, etc.) in LLVM's3249in-memory IR belongs to an ``LLVMContext``.  Entities in different contexts3250*cannot* interact with each other: ``Module``\ s in different contexts cannot be3251linked together, ``Function``\ s cannot be added to ``Module``\ s in different3252contexts, etc.  What this means is that is safe to compile on multiple3253threads simultaneously, as long as no two threads operate on entities within the3254same context.3255 3256In practice, very few places in the API require the explicit specification of a3257``LLVMContext``, other than the ``Type`` creation/lookup APIs.  Because every3258``Type`` carries a reference to its owning context, most other entities can3259determine what context they belong to by looking at their own ``Type``.  If you3260are adding new entities to LLVM IR, please try to maintain this interface3261design.3262 3263.. _jitthreading:3264 3265Threads and the JIT3266-------------------3267 3268LLVM's "eager" JIT compiler is safe to use in threaded programs.  Multiple3269threads can call ``ExecutionEngine::getPointerToFunction()`` or3270``ExecutionEngine::runFunction()`` concurrently, and multiple threads can run3271code output by the JIT concurrently.  The user must still ensure that only one3272thread accesses IR in a given ``LLVMContext`` while another thread might be3273modifying it.  One way to do that is to always hold the JIT lock while accessing3274IR outside the JIT (the JIT *modifies* the IR by adding ``CallbackVH``\ s).3275Another way is to only call ``getPointerToFunction()`` from the3276``LLVMContext``'s thread.3277 3278When the JIT is configured to compile lazily (using3279``ExecutionEngine::DisableLazyCompilation(false)``), there is currently a `race3280condition <https://bugs.llvm.org/show_bug.cgi?id=5184>`_ in updating call sites3281after a function is lazily-jitted.  It's still possible to use the lazy JIT in a3282threaded program if you ensure that only one thread at a time can call any3283particular lazy stub and that the JIT lock guards any IR access, but we suggest3284using only the eager JIT in threaded programs.3285 3286.. _advanced:3287 3288Advanced Topics3289===============3290 3291This section describes some of the advanced or obscure API's that most clients3292do not need to be aware of.  These API's tend manage the inner workings of the3293LLVM system, and only need to be accessed in unusual circumstances.3294 3295.. _SymbolTable:3296 3297The ``ValueSymbolTable`` class3298------------------------------3299 3300The ``ValueSymbolTable`` (`doxygen3301<https://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html>`__) class provides3302a symbol table that the :ref:`Function <c_Function>` and Module_ classes use for3303naming value definitions.  The symbol table can provide a name for any Value_.3304 3305Note that the ``SymbolTable`` class should not be directly accessed by most3306clients.  It should only be used when iteration over the symbol table names3307themselves are required, which is very special purpose.  Note that not all LLVM3308Value_\ s have names, and those without names (i.e., they have an empty name) do3309not exist in the symbol table.3310 3311Symbol tables support iteration over the values in the symbol table with3312``begin/end/iterator`` and supports querying to see if a specific name is in the3313symbol table (with ``lookup``).  The ``ValueSymbolTable`` class exposes no3314public mutator methods, instead, simply call ``setName`` on a value, which will3315autoinsert it into the appropriate symbol table.3316 3317.. _UserLayout:3318 3319The ``User`` and owned ``Use`` classes' memory layout3320-----------------------------------------------------3321 3322The ``User`` (`doxygen <https://llvm.org/doxygen/classllvm_1_1User.html>`__)3323class provides a basis for expressing the ownership of ``User`` towards other3324`Value instance <https://llvm.org/doxygen/classllvm_1_1Value.html>`_\ s.  The3325``Use`` (`doxygen <https://llvm.org/doxygen/classllvm_1_1Use.html>`__) helper3326class is employed to do the bookkeeping and to facilitate *O(1)* addition and3327removal.3328 3329.. _Use2User:3330 3331Interaction and relationship between ``User`` and ``Use`` objects3332^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3333 3334A subclass of ``User`` can choose between incorporating its ``Use`` objects or3335refer to them out-of-line by means of a pointer.  A mixed variant (some ``Use``3336s inline others hung off) is impractical and breaks the invariant that the3337``Use`` objects belonging to the same ``User`` form a contiguous array.3338 3339We have 2 different layouts in the ``User`` (sub)classes:3340 3341* Layout a)3342 3343  The ``Use`` object(s) are inside (resp. at fixed offset) of the ``User``3344  object and there are a fixed number of them.3345 3346* Layout b)3347 3348  The ``Use`` object(s) are referenced by a pointer to an array from the3349  ``User`` object and there may be a variable number of them.3350 3351As of v2.4 each layout still possesses a direct pointer to the start of the3352array of ``Use``\ s.  Though not mandatory for layout a), we stick to this3353redundancy for the sake of simplicity.  The ``User`` object also stores the3354number of ``Use`` objects it has. (Theoretically this information can also be3355calculated given the scheme presented below.)3356 3357Special forms of allocation operators (``operator new``) enforce the following3358memory layouts:3359 3360* Layout a) is modelled by prepending the ``User`` object by the ``Use[]``3361  array.3362 3363  .. code-block:: none3364 3365    ...---.---.---.---.-------...3366      | P | P | P | P | User3367    '''---'---'---'---'-------'''3368 3369* Layout b) is modelled by pointing at the ``Use[]`` array.3370 3371  .. code-block:: none3372 3373    .-------...3374    | User3375    '-------'''3376        |3377        v3378        .---.---.---.---...3379        | P | P | P | P |3380        '---'---'---'---'''3381 3382*(In the above figures* '``P``' *stands for the* ``Use**`` *that is stored in3383each* ``Use`` *object in the member* ``Use::Prev`` *)*3384 3385.. _polymorphism:3386 3387Designing Type Hierarchies and Polymorphic Interfaces3388-----------------------------------------------------3389 3390There are two different design patterns that tend to result in the use of3391virtual dispatch for methods in a type hierarchy in C++ programs. The first is3392a genuine type hierarchy where different types in the hierarchy model3393a specific subset of the functionality and semantics, and these types nest3394strictly within each other. Good examples of this can be seen in the ``Value``3395or ``Type`` type hierarchies.3396 3397A second is the desire to dispatch dynamically across a collection of3398polymorphic interface implementations. This latter use case can be modeled with3399virtual dispatch and inheritance by defining an abstract interface base class3400which all implementations derive from and override. However, this3401implementation strategy forces an **"is-a"** relationship to exist that is not3402actually meaningful. There is often not some nested hierarchy of useful3403generalizations which code might interact with and move up and down. Instead,3404there is a singular interface which is dispatched across a range of3405implementations.3406 3407The preferred implementation strategy for the second use case is that of3408generic programming (sometimes called "compile-time duck typing" or "static3409polymorphism"). For example, a template over some type parameter ``T`` can be3410instantiated across any particular implementation that conforms to the3411interface or *concept*. A good example here is the highly generic properties of3412any type which models a node in a directed graph. LLVM models these primarily3413through templates and generic programming. Such templates include the3414``LoopInfoBase`` and ``DominatorTreeBase``. When this type of polymorphism3415truly needs **dynamic** dispatch you can generalize it using a technique3416called *concept-based polymorphism*. This pattern emulates the interfaces and3417behaviors of templates using a very limited form of virtual dispatch for type3418erasure inside its implementation. You can find examples of this technique in3419the ``PassManager.h`` system, and there is a more detailed introduction to it3420by Sean Parent in several of his talks and papers:3421 3422#. `Inheritance Is The Base Class of Evil3423   <https://learn.microsoft.com/en-us/shows/goingnative-2013/inheritance-base-class-of-evil>`_3424   - The GoingNative 2013 talk describing this technique, and probably the best3425   place to start.3426#. `Value Semantics and Concepts-based Polymorphism3427   <http://www.youtube.com/watch?v=_BpMYeUFXv8>`_ - The C++Now! 2012 talk3428   describing this technique in more detail.3429#. `Sean Parent's Papers and Presentations3430   <https://sean-parent.stlab.cc/papers-and-presentations>`_3431   - Links to slides, videos, and sometimes code.3432 3433When deciding between creating a type hierarchy (with either tagged or virtual3434dispatch) and using templates or concepts-based polymorphism, consider whether3435there is some refinement of an abstract base class which is a semantically3436meaningful type on an interface boundary. If anything more refined than the3437root abstract interface is meaningless to talk about as a partial extension of3438the semantic model, then your use case likely fits better with polymorphism and3439you should avoid using virtual dispatch. However, there may be some exigent3440circumstances that require one technique or the other to be used.3441 3442If you do need to introduce a type hierarchy, we prefer to use explicitly3443closed type hierarchies with manual tagged dispatch and/or RTTI rather than the3444open inheritance model and virtual dispatch that is more common in C++ code.3445This is because LLVM rarely encourages library consumers to extend its core3446types, and leverages the closed and tag-dispatched nature of its hierarchies to3447generate significantly more efficient code. We have also found that a large3448amount of our usage of type hierarchies fits better with tag-based pattern3449matching rather than dynamic dispatch across a common interface. Within LLVM we3450have built custom helpers to facilitate this design. See this document's3451section on :ref:`isa and dyn_cast <isa>` and our :doc:`detailed document3452<HowToSetUpLLVMStyleRTTI>` which describes how you can implement this3453pattern for use with the LLVM helpers.3454 3455.. _abi_breaking_checks:3456 3457ABI Breaking Checks3458-------------------3459 3460Checks and asserts that alter the LLVM C++ ABI are predicated on the3461preprocessor symbol `LLVM_ENABLE_ABI_BREAKING_CHECKS` -- LLVM3462libraries built with `LLVM_ENABLE_ABI_BREAKING_CHECKS` are not ABI3463compatible LLVM libraries built without it defined.  By default,3464turning on assertions also turns on `LLVM_ENABLE_ABI_BREAKING_CHECKS`3465so a default +Asserts build is not ABI compatible with a3466default -Asserts build.  Clients that want ABI compatibility3467between +Asserts and -Asserts builds should use the CMake build system3468to set `LLVM_ENABLE_ABI_BREAKING_CHECKS` independently3469of `LLVM_ENABLE_ASSERTIONS`.3470 3471.. _coreclasses:3472 3473The Core LLVM Class Hierarchy Reference3474=======================================3475 3476``#include "llvm/IR/Type.h"``3477 3478header source: `Type.h <https://llvm.org/doxygen/Type_8h_source.html>`_3479 3480doxygen info: `Type Classes <https://llvm.org/doxygen/classllvm_1_1Type.html>`_3481 3482The Core LLVM classes are the primary means of representing the program being3483inspected or transformed.  The core LLVM classes are defined in header files in3484the ``include/llvm/IR`` directory, and implemented in the ``lib/IR``3485directory. It's worth noting that, for historical reasons, this library is3486called ``libLLVMCore.so``, not ``libLLVMIR.so`` as you might expect.3487 3488.. _Type:3489 3490The Type class and Derived Types3491--------------------------------3492 3493``Type`` is a superclass of all type classes.  Every ``Value`` has a ``Type``.3494``Type`` cannot be instantiated directly but only through its subclasses.3495Certain primitive types (``VoidType``, ``LabelType``, ``FloatType`` and3496``DoubleType``) have hidden subclasses.  They are hidden because they offer no3497useful functionality beyond what the ``Type`` class offers except to distinguish3498themselves from other subclasses of ``Type``.3499 3500All other types are subclasses of ``DerivedType``.  Types can be named, but this3501is not a requirement.  There exists exactly one instance of a given shape at any3502one time.  This allows type equality to be performed with address equality of3503the Type Instance.  That is, given two ``Type*`` values, the types are identical3504if the pointers are identical.3505 3506.. _m_Type:3507 3508Important Public Methods3509^^^^^^^^^^^^^^^^^^^^^^^^3510 3511* ``bool isIntegerTy() const``: Returns true for any integer type.3512 3513* ``bool isFloatingPointTy()``: Return true if this is one of the five3514  floating point types.3515 3516* ``bool isSized()``: Return true if the type has known size.  Things3517  that don't have a size are abstract types, labels and void.3518 3519.. _derivedtypes:3520 3521Important Derived Types3522^^^^^^^^^^^^^^^^^^^^^^^3523 3524``IntegerType``3525  Subclass of DerivedType that represents integer types of any bit width.  Any3526  bit width between ``IntegerType::MIN_INT_BITS`` (1) and3527  ``IntegerType::MAX_INT_BITS`` (~8 million) can be represented.3528 3529  * ``static const IntegerType* get(unsigned NumBits)``: get an integer3530    type of a specific bit width.3531 3532  * ``unsigned getBitWidth() const``: Get the bit width of an integer type.3533 3534``SequentialType``3535  This is subclassed by ArrayType and VectorType.3536 3537  * ``const Type * getElementType() const``: Returns the type of each3538    of the elements in the sequential type.3539 3540  * ``uint64_t getNumElements() const``: Returns the number of elements3541    in the sequential type.3542 3543``ArrayType``3544  This is a subclass of SequentialType and defines the interface for array3545  types.3546 3547``PointerType``3548  Subclass of Type for pointer types.3549 3550``VectorType``3551  Subclass of SequentialType for vector types.  A vector type is similar to an3552  ArrayType but is distinguished because it is a first class type whereas3553  ArrayType is not.  Vector types are used for vector operations and are usually3554  small vectors of an integer or floating point type.3555 3556``StructType``3557  Subclass of DerivedTypes for struct types.3558 3559.. _FunctionType:3560 3561``FunctionType``3562  Subclass of DerivedTypes for function types.3563 3564  * ``bool isVarArg() const``: Returns true if it's a vararg function.3565 3566  * ``const Type * getReturnType() const``: Returns the return type of the3567    function.3568 3569  * ``const Type * getParamType (unsigned i)``: Returns the type of the ith3570    parameter.3571 3572  * ``const unsigned getNumParams() const``: Returns the number of formal3573    parameters.3574 3575.. _Module:3576 3577The ``Module`` class3578--------------------3579 3580``#include "llvm/IR/Module.h"``3581 3582header source: `Module.h <https://llvm.org/doxygen/Module_8h_source.html>`_3583 3584doxygen info: `Module Class <https://llvm.org/doxygen/classllvm_1_1Module.html>`_3585 3586The ``Module`` class represents the top level structure present in LLVM3587programs.  An LLVM module is effectively either a translation unit of the3588original program or a combination of several translation units merged by the3589linker.  The ``Module`` class keeps track of a list of :ref:`Function3590<c_Function>`\ s, a list of GlobalVariable_\ s, and a SymbolTable_.3591Additionally, it contains a few helpful member functions that try to make common3592operations easy.3593 3594.. _m_Module:3595 3596Important Public Members of the ``Module`` class3597^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3598 3599* ``Module::Module(std::string name = "")``3600 3601  Constructing a Module_ is easy.  You can optionally provide a name for it3602  (probably based on the name of the translation unit).3603 3604* | ``Module::iterator`` - Typedef for function list iterator3605  | ``Module::const_iterator`` - Typedef for const_iterator.3606  | ``begin()``, ``end()``, ``size()``, ``empty()``3607 3608  These are forwarding methods that make it easy to access the contents of a3609  ``Module`` object's :ref:`Function <c_Function>` list.3610 3611* ``Module::FunctionListType &getFunctionList()``3612 3613  Returns the list of :ref:`Function <c_Function>`\ s.  This is necessary to use3614  when you need to update the list or perform a complex action that doesn't have3615  a forwarding method.3616 3617----------------3618 3619* | ``Module::global_iterator`` - Typedef for global variable list iterator3620  | ``Module::const_global_iterator`` - Typedef for const_iterator.3621  | ``Module::insertGlobalVariable()`` - Inserts a global variable to the list.3622  | ``Module::removeGlobalVariable()`` - Removes a global variable from the list.3623  | ``Module::eraseGlobalVariable()`` - Removes a global variable from the list and deletes it.3624  | ``global_begin()``, ``global_end()``, ``global_size()``, ``global_empty()``3625 3626  These are forwarding methods that make it easy to access the contents of a3627  ``Module`` object's GlobalVariable_ list.3628 3629----------------3630 3631* ``SymbolTable *getSymbolTable()``3632 3633  Return a reference to the SymbolTable_ for this ``Module``.3634 3635----------------3636 3637* ``Function *getFunction(StringRef Name) const``3638 3639  Look up the specified function in the ``Module`` SymbolTable_.  If it does not3640  exist, return ``null``.3641 3642* ``FunctionCallee getOrInsertFunction(const std::string &Name,3643  const FunctionType *T)``3644 3645  Look up the specified function in the ``Module`` SymbolTable_.  If3646  it does not exist, add an external declaration for the function and3647  return it. Note that the function signature already present may not3648  match the requested signature. Thus, in order to enable the common3649  usage of passing the result directly to EmitCall, the return type is3650  a struct of ``{FunctionType *T, Constant *FunctionPtr}``, rather3651  than simply the ``Function*`` with potentially an unexpected3652  signature.3653 3654* ``std::string getTypeName(const Type *Ty)``3655 3656  If there is at least one entry in the SymbolTable_ for the specified Type_,3657  return it.  Otherwise return the empty string.3658 3659* ``bool addTypeName(const std::string &Name, const Type *Ty)``3660 3661  Insert an entry in the SymbolTable_ mapping ``Name`` to ``Ty``.  If there is3662  already an entry for this name, true is returned and the SymbolTable_ is not3663  modified.3664 3665.. _Value:3666 3667The ``Value`` class3668-------------------3669 3670``#include "llvm/IR/Value.h"``3671 3672header source: `Value.h <https://llvm.org/doxygen/Value_8h_source.html>`_3673 3674doxygen info: `Value Class <https://llvm.org/doxygen/classllvm_1_1Value.html>`_3675 3676The ``Value`` class is the most important class in the LLVM Source base.  It3677represents a typed value that may be used (among other things) as an operand to3678an instruction.  There are many different types of ``Value``\ s, such as3679Constant_\ s, Argument_\ s.  Even Instruction_\ s and :ref:`Function3680<c_Function>`\ s are ``Value``\ s.3681 3682A particular ``Value`` may be used many times in the LLVM representation for a3683program.  For example, an incoming argument to a function (represented with an3684instance of the Argument_ class) is "used" by every instruction in the function3685that references the argument.  To keep track of this relationship, the ``Value``3686class keeps a list of all of the ``User``\ s that is using it (the User_ class3687is a base class for all nodes in the LLVM graph that can refer to ``Value``\ s).3688This use list is how LLVM represents def-use information in the program, and is3689accessible through the ``use_*`` methods, shown below.3690 3691Because LLVM is a typed representation, every LLVM ``Value`` is typed, and this3692Type_ is available through the ``getType()`` method.  In addition, all LLVM3693values can be named.  The "name" of the ``Value`` is a symbolic string printed3694in the LLVM code:3695 3696.. code-block:: llvm3697 3698  %foo = add i32 1, 23699 3700.. _nameWarning:3701 3702The name of this instruction is "foo". **NOTE** that the name of any value may3703be missing (an empty string), so names should **ONLY** be used for debugging3704(making the source code easier to read, debugging printouts), they should not be3705used to keep track of values or map between them.  For this purpose, use a3706``std::map`` of pointers to the ``Value`` itself instead.3707 3708One important aspect of LLVM is that there is no distinction between an SSA3709variable and the operation that produces it.  Because of this, any reference to3710the value produced by an instruction (or the value available as an incoming3711argument, for example) is represented as a direct pointer to the instance of the3712class that represents this value.  Although this may take some getting used to,3713it simplifies the representation and makes it easier to manipulate.3714 3715.. _m_Value:3716 3717Important Public Members of the ``Value`` class3718^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3719 3720* | ``Value::use_iterator`` - Typedef for iterator over the use-list3721  | ``Value::const_use_iterator`` - Typedef for const_iterator over the3722    use-list3723  | ``unsigned use_size()`` - Returns the number of users of the value.3724  | ``bool use_empty()`` - Returns true if there are no users.3725  | ``use_iterator use_begin()`` - Get an iterator to the start of the3726    use-list.3727  | ``use_iterator use_end()`` - Get an iterator to the end of the use-list.3728  | ``User *use_back()`` - Returns the last element in the list.3729 3730  These methods are the interface to access the def-use information in LLVM.3731  As with all other iterators in LLVM, the naming conventions follow the3732  conventions defined by the STL_.3733 3734* ``Type *getType() const``3735  This method returns the Type of the Value.3736 3737* | ``bool hasName() const``3738  | ``std::string getName() const``3739  | ``void setName(const std::string &Name)``3740 3741  This family of methods is used to access and assign a name to a ``Value``, be3742  aware of the :ref:`precaution above <nameWarning>`.3743 3744* ``void replaceAllUsesWith(Value *V)``3745 3746  This method traverses the use list of a ``Value`` changing all User_\ s of the3747  current value to refer to "``V``" instead.  For example, if you detect that an3748  instruction always produces a constant value (for example through constant3749  folding), you can replace all uses of the instruction with the constant like3750  this:3751 3752  .. code-block:: c++3753 3754    Inst->replaceAllUsesWith(ConstVal);3755 3756.. _User:3757 3758The ``User`` class3759------------------3760 3761``#include "llvm/IR/User.h"``3762 3763header source: `User.h <https://llvm.org/doxygen/User_8h_source.html>`_3764 3765doxygen info: `User Class <https://llvm.org/doxygen/classllvm_1_1User.html>`_3766 3767Superclass: Value_3768 3769The ``User`` class is the common base class of all LLVM nodes that may refer to3770``Value``\ s.  It exposes a list of "Operands" that are all of the ``Value``\ s3771that the User is referring to.  The ``User`` class itself is a subclass of3772``Value``.3773 3774The operands of a ``User`` point directly to the LLVM ``Value`` that it refers3775to.  Because LLVM uses Static Single Assignment (SSA) form, there can only be3776one definition referred to, allowing this direct connection.  This connection3777provides the use-def information in LLVM.3778 3779.. _m_User:3780 3781Important Public Members of the ``User`` class3782^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3783 3784The ``User`` class exposes the operand list in two ways: through an index access3785interface and through an iterator based interface.3786 3787* | ``Value *getOperand(unsigned i)``3788  | ``unsigned getNumOperands()``3789 3790  These two methods expose the operands of the ``User`` in a convenient form for3791  direct access.3792 3793* | ``User::op_iterator`` - Typedef for iterator over the operand list3794  | ``op_iterator op_begin()`` - Get an iterator to the start of the operand3795    list.3796  | ``op_iterator op_end()`` - Get an iterator to the end of the operand list.3797 3798  Together, these methods make up the iterator based interface to the operands3799  of a ``User``.3800 3801 3802.. _Instruction:3803 3804The ``Instruction`` class3805-------------------------3806 3807``#include "llvm/IR/Instruction.h"``3808 3809header source: `Instruction.h3810<https://llvm.org/doxygen/Instruction_8h_source.html>`_3811 3812doxygen info: `Instruction Class3813<https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_3814 3815Superclasses: User_, Value_3816 3817The ``Instruction`` class is the common base class for all LLVM instructions.3818It provides only a few methods, but is a very commonly used class.  The primary3819data tracked by the ``Instruction`` class itself is the opcode (instruction3820type) and the parent BasicBlock_ the ``Instruction`` is embedded into.  To3821represent a specific type of instruction, one of many subclasses of3822``Instruction`` are used.3823 3824Because the ``Instruction`` class subclasses the User_ class, its operands can3825be accessed in the same way as for other ``User``\ s (with the3826``getOperand()``/``getNumOperands()`` and ``op_begin()``/``op_end()`` methods).3827An important file for the ``Instruction`` class is the ``llvm/Instruction.def``3828file.  This file contains some meta-data about the various different types of3829instructions in LLVM.  It describes the enum values that are used as opcodes3830(for example ``Instruction::Add`` and ``Instruction::ICmp``), as well as the3831concrete sub-classes of ``Instruction`` that implement the instruction (for3832example BinaryOperator_ and CmpInst_).  Unfortunately, the use of macros in this3833file confuses doxygen, so these enum values don't show up correctly in the3834`doxygen output <https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_.3835 3836.. _s_Instruction:3837 3838Important Subclasses of the ``Instruction`` class3839^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3840 3841.. _BinaryOperator:3842 3843* ``BinaryOperator``3844 3845  This subclass represents all two operand instructions whose operands must be3846  the same type, except for the comparison instructions.3847 3848.. _CastInst:3849 3850* ``CastInst``3851  This subclass is the parent of the 12 casting instructions.  It provides3852  common operations on cast instructions.3853 3854.. _CmpInst:3855 3856* ``CmpInst``3857 3858  This subclass represents the two comparison instructions,3859  `ICmpInst <LangRef.html#i_icmp>`_ (integer operands), and3860  `FCmpInst <LangRef.html#i_fcmp>`_ (floating point operands).3861 3862.. _m_Instruction:3863 3864Important Public Members of the ``Instruction`` class3865^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3866 3867* ``BasicBlock *getParent()``3868 3869  Returns the BasicBlock_ that this3870  ``Instruction`` is embedded into.3871 3872* ``bool mayWriteToMemory()``3873 3874  Returns true if the instruction writes to memory, i.e., it is a ``call``,3875  ``free``, ``invoke``, or ``store``.3876 3877* ``unsigned getOpcode()``3878 3879  Returns the opcode for the ``Instruction``.3880 3881* ``Instruction *clone() const``3882 3883  Returns another instance of the specified instruction, identical in all ways3884  to the original except that the instruction has no parent (i.e., it's not3885  embedded into a BasicBlock_), and it has no name.3886 3887.. _Constant:3888 3889The ``Constant`` class and subclasses3890-------------------------------------3891 3892Constant represents a base class for different types of constants.  It is3893subclassed by ConstantInt, ConstantArray, etc. for representing the various3894types of Constants.  GlobalValue_ is also a subclass, which represents the3895address of a global variable or function.3896 3897.. _s_Constant:3898 3899Important Subclasses of Constant3900^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3901 3902* ConstantInt : This subclass of Constant represents an integer constant of3903  any width.3904 3905  * ``const APInt& getValue() const``: Returns the underlying3906    value of this constant, an ``APInt`` value.3907 3908  * ``int64_t getSExtValue() const``: Converts the underlying APInt value to an3909    ``int64_t`` via sign extension.  If the value (not the bit width) of the APInt3910    is too large to fit in an ``int64_t``, an assertion will result.  For this3911    reason, use of this method is discouraged.3912 3913  * ``uint64_t getZExtValue() const``: Converts the underlying ``APInt`` value3914    to a ``uint64_t`` via zero extension.  If the value (not the bit width) of the3915    APInt is too large to fit in a ``uint64_t``, an assertion will result.  For this3916    reason, use of this method is discouraged.3917 3918  * ``static ConstantInt* get(const APInt& Val)``: Returns the ConstantInt3919    object that represents the value provided by ``Val``.  The type is implied3920    as the IntegerType that corresponds to the bit width of ``Val``.3921 3922  * ``static ConstantInt* get(const Type *Ty, uint64_t Val)``: Returns the3923    ConstantInt object that represents the value provided by ``Val`` for integer3924    type ``Ty``.3925 3926* ConstantFP : This class represents a floating point constant.3927 3928  * ``double getValue() const``: Returns the underlying value of this constant.3929 3930* ConstantArray : This represents a constant array.3931 3932  * ``const std::vector<Use> &getValues() const``: Returns a vector of3933    component constants that makeup this array.3934 3935* ConstantStruct : This represents a constant struct.3936 3937  * ``const std::vector<Use> &getValues() const``: Returns a vector of3938    component constants that makeup this array.3939 3940* GlobalValue : This represents either a global variable or a function.  In3941  either case, the value is a constant fixed address (after linking).3942 3943.. _GlobalValue:3944 3945The ``GlobalValue`` class3946-------------------------3947 3948``#include "llvm/IR/GlobalValue.h"``3949 3950header source: `GlobalValue.h3951<https://llvm.org/doxygen/GlobalValue_8h_source.html>`_3952 3953doxygen info: `GlobalValue Class3954<https://llvm.org/doxygen/classllvm_1_1GlobalValue.html>`_3955 3956Superclasses: Constant_, User_, Value_3957 3958Global values ( GlobalVariable_\ s or :ref:`Function <c_Function>`\ s) are the3959only LLVM values that are visible in the bodies of all :ref:`Function3960<c_Function>`\ s.  Because they are visible at global scope, they are also3961subject to linking with other globals defined in different translation units.3962To control the linking process, ``GlobalValue``\ s know their linkage rules.3963Specifically, ``GlobalValue``\ s know whether they have internal or external3964linkage, as defined by the ``LinkageTypes`` enumeration.3965 3966If a ``GlobalValue`` has internal linkage (equivalent to being ``static`` in C),3967it is not visible to code outside the current translation unit, and does not3968participate in linking.  If it has external linkage, it is visible to external3969code, and does participate in linking.  In addition to linkage information,3970``GlobalValue``\ s keep track of which Module_ they are currently part of.3971 3972Because ``GlobalValue``\ s are memory objects, they are always referred to by3973their **address**.  As such, the Type_ of a global is always a pointer to its3974contents.  It is important to remember this when using the ``GetElementPtrInst``3975instruction because this pointer must be dereferenced first.  For example, if3976you have a ``GlobalVariable`` (a subclass of ``GlobalValue)`` that is an array3977of 24 ints, type ``[24 x i32]``, then the ``GlobalVariable`` is a pointer to3978that array.  Although the address of the first element of this array and the3979value of the ``GlobalVariable`` are the same, they have different types.  The3980``GlobalVariable``'s type is ``[24 x i32]``.  The first element's type is3981``i32.`` Because of this, accessing a global value requires you to dereference3982the pointer with ``GetElementPtrInst`` first, then its elements can be accessed.3983This is explained in the `LLVM Language Reference Manual3984<LangRef.html#globalvars>`_.3985 3986.. _m_GlobalValue:3987 3988Important Public Members of the ``GlobalValue`` class3989^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^3990 3991* | ``bool hasInternalLinkage() const``3992  | ``bool hasExternalLinkage() const``3993  | ``void setInternalLinkage(bool HasInternalLinkage)``3994 3995  These methods manipulate the linkage characteristics of the ``GlobalValue``.3996 3997* ``Module *getParent()``3998 3999  This returns the Module_ that the4000  GlobalValue is currently embedded into.4001 4002.. _c_Function:4003 4004The ``Function`` class4005----------------------4006 4007``#include "llvm/IR/Function.h"``4008 4009header source: `Function.h <https://llvm.org/doxygen/Function_8h_source.html>`_4010 4011doxygen info: `Function Class4012<https://llvm.org/doxygen/classllvm_1_1Function.html>`_4013 4014Superclasses: GlobalValue_, Constant_, User_, Value_4015 4016The ``Function`` class represents a single procedure in LLVM.  It is actually4017one of the more complex classes in the LLVM hierarchy because it must keep track4018of a large amount of data.  The ``Function`` class keeps track of a list of4019BasicBlock_\ s, a list of formal Argument_\ s, and a SymbolTable_.4020 4021The list of BasicBlock_\ s is the most commonly used part of ``Function``4022objects.  The list imposes an implicit ordering of the blocks in the function,4023which indicate how the code will be laid out by the backend.  Additionally, the4024first BasicBlock_ is the implicit entry node for the ``Function``.  It is not4025legal in LLVM to explicitly branch to this initial block.  There are no implicit4026exit nodes, and in fact there may be multiple exit nodes from a single4027``Function``.  If the BasicBlock_ list is empty, this indicates that the4028``Function`` is actually a function declaration: the actual body of the function4029hasn't been linked in yet.4030 4031In addition to a list of BasicBlock_\ s, the ``Function`` class also keeps track4032of the list of formal Argument_\ s that the function receives.  This container4033manages the lifetime of the Argument_ nodes, just like the BasicBlock_ list does4034for the BasicBlock_\ s.4035 4036The SymbolTable_ is a very rarely used LLVM feature that is only used when you4037have to look up a value by name.  Aside from that, the SymbolTable_ is used4038internally to make sure that there are not conflicts between the names of4039Instruction_\ s, BasicBlock_\ s, or Argument_\ s in the function body.4040 4041Note that ``Function`` is a GlobalValue_ and therefore also a Constant_.  The4042value of the function is its address (after linking) which is guaranteed to be4043constant.4044 4045.. _m_Function:4046 4047Important Public Members of the ``Function``4048^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^4049 4050* ``Function(const FunctionType *Ty, LinkageTypes Linkage,4051  const std::string &N = "", Module* Parent = 0)``4052 4053  Constructor used when you need to create new ``Function``\ s to add the4054  program.  The constructor must specify the type of the function to create and4055  what type of linkage the function should have.  The FunctionType_ argument4056  specifies the formal arguments and return value for the function.  The same4057  FunctionType_ value can be used to create multiple functions.  The ``Parent``4058  argument specifies the Module in which the function is defined.  If this4059  argument is provided, the function will automatically be inserted into that4060  module's list of functions.4061 4062* ``bool isDeclaration()``4063 4064  Return whether or not the ``Function`` has a body defined.  If the function is4065  "external", it does not have a body, and thus must be resolved by linking with4066  a function defined in a different translation unit.4067 4068* | ``Function::iterator`` - Typedef for basic block list iterator4069  | ``Function::const_iterator`` - Typedef for const_iterator.4070  | ``begin()``, ``end()``, ``size()``, ``empty()``, ``insert()``,4071    ``splice()``, ``erase()``4072 4073  These are forwarding methods that make it easy to access the contents of a4074  ``Function`` object's BasicBlock_ list.4075 4076* | ``Function::arg_iterator`` - Typedef for the argument list iterator4077  | ``Function::const_arg_iterator`` - Typedef for const_iterator.4078  | ``arg_begin()``, ``arg_end()``, ``arg_size()``, ``arg_empty()``4079 4080  These are forwarding methods that make it easy to access the contents of a4081  ``Function`` object's Argument_ list.4082 4083* ``Function::ArgumentListType &getArgumentList()``4084 4085  Returns the list of Argument_.  This is necessary to use when you need to4086  update the list or perform a complex action that doesn't have a forwarding4087  method.4088 4089* ``BasicBlock &getEntryBlock()``4090 4091  Returns the entry ``BasicBlock`` for the function.  Because the entry block4092  for the function is always the first block, this returns the first block of4093  the ``Function``.4094 4095* | ``Type *getReturnType()``4096  | ``FunctionType *getFunctionType()``4097 4098  This traverses the Type_ of the ``Function`` and returns the return type of4099  the function, or the FunctionType_ of the actual function.4100 4101* ``SymbolTable *getSymbolTable()``4102 4103  Return a pointer to the SymbolTable_ for this ``Function``.4104 4105.. _GlobalVariable:4106 4107The ``GlobalVariable`` class4108----------------------------4109 4110``#include "llvm/IR/GlobalVariable.h"``4111 4112header source: `GlobalVariable.h4113<https://llvm.org/doxygen/GlobalVariable_8h_source.html>`_4114 4115doxygen info: `GlobalVariable Class4116<https://llvm.org/doxygen/classllvm_1_1GlobalVariable.html>`_4117 4118Superclasses: GlobalValue_, Constant_, User_, Value_4119 4120Global variables are represented with the (surprise surprise) ``GlobalVariable``4121class.  Like functions, ``GlobalVariable``\ s are also subclasses of4122GlobalValue_, and as such are always referenced by their address (global values4123must live in memory, so their "name" refers to their constant address).  See4124GlobalValue_ for more on this.  Global variables may have an initial value4125(which must be a Constant_), and if they have an initializer, they may be marked4126as "constant" themselves (indicating that their contents never change at4127runtime).4128 4129.. _m_GlobalVariable:4130 4131Important Public Members of the ``GlobalVariable`` class4132^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^4133 4134* ``GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes &Linkage,4135  Constant *Initializer = 0, const std::string &Name = "", Module* Parent = 0)``4136 4137  Create a new global variable of the specified type.  If ``isConstant`` is true4138  then the global variable will be marked as unchanging for the program.  The4139  Linkage parameter specifies the type of linkage (internal, external, weak,4140  linkonce, appending) for the variable.  If the linkage is InternalLinkage,4141  WeakAnyLinkage, WeakODRLinkage, LinkOnceAnyLinkage or LinkOnceODRLinkage, then4142  the resultant global variable will have internal linkage.  AppendingLinkage4143  concatenates together all instances (in different translation units) of the4144  variable into a single variable but is only applicable to arrays.  See the4145  `LLVM Language Reference <LangRef.html#modulestructure>`_ for further details4146  on linkage types.  Optionally an initializer, a name, and the module to put4147  the variable into may be specified for the global variable as well.4148 4149* ``bool isConstant() const``4150 4151  Returns true if this is a global variable that is known not to be modified at4152  runtime.4153 4154* ``bool hasInitializer()``4155 4156  Returns true if this ``GlobalVariable`` has an initializer.4157 4158* ``Constant *getInitializer()``4159 4160  Returns the initial value for a ``GlobalVariable``.  It is not legal to call4161  this method if there is no initializer.4162 4163.. _BasicBlock:4164 4165The ``BasicBlock`` class4166------------------------4167 4168``#include "llvm/IR/BasicBlock.h"``4169 4170header source: `BasicBlock.h4171<https://llvm.org/doxygen/BasicBlock_8h_source.html>`_4172 4173doxygen info: `BasicBlock Class4174<https://llvm.org/doxygen/classllvm_1_1BasicBlock.html>`_4175 4176Superclass: Value_4177 4178This class represents a single entry single exit section of the code, commonly4179known as a basic block by the compiler community.  The ``BasicBlock`` class4180maintains a list of Instruction_\ s, which form the body of the block.  Matching4181the language definition, the last element of this list of instructions is always4182a terminator instruction.4183 4184In addition to tracking the list of instructions that make up the block, the4185``BasicBlock`` class also keeps track of the :ref:`Function <c_Function>` that4186it is embedded into.4187 4188Note that ``BasicBlock``\ s themselves are Value_\ s, because they are4189referenced by instructions like branches and can go in the switch tables.4190``BasicBlock``\ s have type ``label``.4191 4192.. _m_BasicBlock:4193 4194Important Public Members of the ``BasicBlock`` class4195^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^4196 4197* ``BasicBlock(const std::string &Name = "", Function *Parent = 0)``4198 4199  The ``BasicBlock`` constructor is used to create new basic blocks for4200  insertion into a function.  The constructor optionally takes a name for the4201  new block, and a :ref:`Function <c_Function>` to insert it into.  If the4202  ``Parent`` parameter is specified, the new ``BasicBlock`` is automatically4203  inserted at the end of the specified :ref:`Function <c_Function>`, if not4204  specified, the ``BasicBlock`` must be manually inserted into the :ref:`Function4205  <c_Function>`.4206 4207* | ``BasicBlock::iterator`` - Typedef for instruction list iterator4208  | ``BasicBlock::const_iterator`` - Typedef for const_iterator.4209  | ``begin()``, ``end()``, ``front()``, ``back()``,4210    ``size()``, ``empty()``, ``splice()``4211    STL-style functions for accessing the instruction list.4212 4213  These methods and typedefs are forwarding functions that have the same4214  semantics as the standard library methods of the same names.  These methods4215  expose the underlying instruction list of a basic block in a way that is easy4216  to manipulate.4217 4218* ``Function *getParent()``4219 4220  Returns a pointer to :ref:`Function <c_Function>` the block is embedded into,4221  or a null pointer if it is homeless.4222 4223* ``Instruction *getTerminator()``4224 4225  Returns a pointer to the terminator instruction that appears at the end of the4226  ``BasicBlock``.  If there is no terminator instruction, or if the last4227  instruction in the block is not a terminator, then a null pointer is returned.4228 4229.. _Argument:4230 4231The ``Argument`` class4232----------------------4233 4234This subclass of Value defines the interface for incoming formal arguments to a4235function.  A Function maintains a list of its formal arguments.  An argument has4236a pointer to the parent Function.4237