109467b48Spatrick======================== 209467b48SpatrickLLVM Programmer's Manual 309467b48Spatrick======================== 409467b48Spatrick 509467b48Spatrick.. contents:: 609467b48Spatrick :local: 709467b48Spatrick 809467b48Spatrick.. warning:: 909467b48Spatrick This is always a work in progress. 1009467b48Spatrick 1109467b48Spatrick.. _introduction: 1209467b48Spatrick 1309467b48SpatrickIntroduction 1409467b48Spatrick============ 1509467b48Spatrick 1609467b48SpatrickThis document is meant to highlight some of the important classes and interfaces 1709467b48Spatrickavailable in the LLVM source-base. This manual is not intended to explain what 1809467b48SpatrickLLVM is, how it works, and what LLVM code looks like. It assumes that you know 1909467b48Spatrickthe basics of LLVM and are interested in writing transformations or otherwise 2009467b48Spatrickanalyzing or manipulating the code. 2109467b48Spatrick 2209467b48SpatrickThis document should get you oriented so that you can find your way in the 2309467b48Spatrickcontinuously growing source code that makes up the LLVM infrastructure. Note 2409467b48Spatrickthat this manual is not intended to serve as a replacement for reading the 2509467b48Spatricksource code, so if you think there should be a method in one of these classes to 2609467b48Spatrickdo something, but it's not listed, check the source. Links to the `doxygen 27097a140dSpatrick<https://llvm.org/doxygen/>`__ sources are provided to make this as easy as 2809467b48Spatrickpossible. 2909467b48Spatrick 3009467b48SpatrickThe first section of this document describes general information that is useful 3109467b48Spatrickto know when working in the LLVM infrastructure, and the second describes the 3209467b48SpatrickCore LLVM classes. In the future this manual will be extended with information 3309467b48Spatrickdescribing how to use extension libraries, such as dominator information, CFG 3409467b48Spatricktraversal routines, and useful utilities like the ``InstVisitor`` (`doxygen 35097a140dSpatrick<https://llvm.org/doxygen/InstVisitor_8h_source.html>`__) template. 3609467b48Spatrick 3709467b48Spatrick.. _general: 3809467b48Spatrick 3909467b48SpatrickGeneral Information 4009467b48Spatrick=================== 4109467b48Spatrick 4209467b48SpatrickThis section contains general information that is useful if you are working in 4309467b48Spatrickthe LLVM source-base, but that isn't specific to any particular API. 4409467b48Spatrick 4509467b48Spatrick.. _stl: 4609467b48Spatrick 4709467b48SpatrickThe C++ Standard Template Library 4809467b48Spatrick--------------------------------- 4909467b48Spatrick 5009467b48SpatrickLLVM makes heavy use of the C++ Standard Template Library (STL), perhaps much 5109467b48Spatrickmore than you are used to, or have seen before. Because of this, you might want 5209467b48Spatrickto do a little background reading in the techniques used and capabilities of the 5309467b48Spatricklibrary. There are many good pages that discuss the STL, and several books on 5409467b48Spatrickthe subject that you can get, so it will not be discussed in this document. 5509467b48Spatrick 5609467b48SpatrickHere are some useful links: 5709467b48Spatrick 5809467b48Spatrick#. `cppreference.com 59*d415bd75Srobert <https://en.cppreference.com/w/>`_ - an excellent 6009467b48Spatrick reference for the STL and other parts of the standard C++ library. 6109467b48Spatrick 62*d415bd75Srobert#. `cplusplus.com 63*d415bd75Srobert <https://cplusplus.com/reference/>`_ - another excellent 64*d415bd75Srobert reference like the one above. 65*d415bd75Srobert 6609467b48Spatrick#. `C++ In a Nutshell <http://www.tempest-sw.com/cpp/>`_ - This is an O'Reilly 6709467b48Spatrick book in the making. It has a decent Standard Library Reference that rivals 6809467b48Spatrick Dinkumware's, and is unfortunately no longer free since the book has been 6909467b48Spatrick published. 7009467b48Spatrick 71*d415bd75Srobert#. `C++ Frequently Asked Questions <https://www.parashift.com/c++-faq-lite/>`_. 7209467b48Spatrick 7309467b48Spatrick#. `Bjarne Stroustrup's C++ Page 74*d415bd75Srobert <https://www.stroustrup.com/C++.html>`_. 7509467b48Spatrick 76*d415bd75Srobert#. `Bruce Eckel's Thinking in C++, 2nd ed. Volume 2. 7709467b48Spatrick (even better, get the book) 78*d415bd75Srobert <https://archive.org/details/TICPP2ndEdVolTwo>`_. 7909467b48Spatrick 8009467b48SpatrickYou are also encouraged to take a look at the :doc:`LLVM Coding Standards 8109467b48Spatrick<CodingStandards>` guide which focuses on how to write maintainable code more 8209467b48Spatrickthan where to put your curly braces. 8309467b48Spatrick 8409467b48Spatrick.. _resources: 8509467b48Spatrick 8609467b48SpatrickOther useful references 8709467b48Spatrick----------------------- 8809467b48Spatrick 8909467b48Spatrick#. `Using static and shared libraries across platforms 9009467b48Spatrick <http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html>`_ 9109467b48Spatrick 9209467b48Spatrick.. _apis: 9309467b48Spatrick 9409467b48SpatrickImportant and useful LLVM APIs 9509467b48Spatrick============================== 9609467b48Spatrick 9709467b48SpatrickHere we highlight some LLVM APIs that are generally useful and good to know 9809467b48Spatrickabout when writing transformations. 9909467b48Spatrick 10009467b48Spatrick.. _isa: 10109467b48Spatrick 10209467b48SpatrickThe ``isa<>``, ``cast<>`` and ``dyn_cast<>`` templates 10309467b48Spatrick------------------------------------------------------ 10409467b48Spatrick 10509467b48SpatrickThe LLVM source-base makes extensive use of a custom form of RTTI. These 10609467b48Spatricktemplates have many similarities to the C++ ``dynamic_cast<>`` operator, but 10709467b48Spatrickthey don't have some drawbacks (primarily stemming from the fact that 10809467b48Spatrick``dynamic_cast<>`` only works on classes that have a v-table). Because they are 10909467b48Spatrickused so often, you must know what they do and how they work. All of these 11009467b48Spatricktemplates are defined in the ``llvm/Support/Casting.h`` (`doxygen 111097a140dSpatrick<https://llvm.org/doxygen/Casting_8h_source.html>`__) file (note that you very 11209467b48Spatrickrarely have to include this file directly). 11309467b48Spatrick 11409467b48Spatrick``isa<>``: 11509467b48Spatrick The ``isa<>`` operator works exactly like the Java "``instanceof``" operator. 11609467b48Spatrick It returns true or false depending on whether a reference or pointer points to 11709467b48Spatrick an instance of the specified class. This can be very useful for constraint 11809467b48Spatrick checking of various sorts (example below). 11909467b48Spatrick 12009467b48Spatrick``cast<>``: 12109467b48Spatrick The ``cast<>`` operator is a "checked cast" operation. It converts a pointer 12209467b48Spatrick or reference from a base class to a derived class, causing an assertion 12309467b48Spatrick failure if it is not really an instance of the right type. This should be 12409467b48Spatrick used in cases where you have some information that makes you believe that 12509467b48Spatrick something is of the right type. An example of the ``isa<>`` and ``cast<>`` 12609467b48Spatrick template is: 12709467b48Spatrick 12809467b48Spatrick .. code-block:: c++ 12909467b48Spatrick 13009467b48Spatrick static bool isLoopInvariant(const Value *V, const Loop *L) { 13109467b48Spatrick if (isa<Constant>(V) || isa<Argument>(V) || isa<GlobalValue>(V)) 13209467b48Spatrick return true; 13309467b48Spatrick 13409467b48Spatrick // Otherwise, it must be an instruction... 13509467b48Spatrick return !L->contains(cast<Instruction>(V)->getParent()); 13609467b48Spatrick } 13709467b48Spatrick 13809467b48Spatrick Note that you should **not** use an ``isa<>`` test followed by a ``cast<>``, 13909467b48Spatrick for that use the ``dyn_cast<>`` operator. 14009467b48Spatrick 14109467b48Spatrick``dyn_cast<>``: 14209467b48Spatrick The ``dyn_cast<>`` operator is a "checking cast" operation. It checks to see 14309467b48Spatrick if the operand is of the specified type, and if so, returns a pointer to it 14409467b48Spatrick (this operator does not work with references). If the operand is not of the 14509467b48Spatrick correct type, a null pointer is returned. Thus, this works very much like 14609467b48Spatrick the ``dynamic_cast<>`` operator in C++, and should be used in the same 14709467b48Spatrick circumstances. Typically, the ``dyn_cast<>`` operator is used in an ``if`` 14809467b48Spatrick statement or some other flow control statement like this: 14909467b48Spatrick 15009467b48Spatrick .. code-block:: c++ 15109467b48Spatrick 15209467b48Spatrick if (auto *AI = dyn_cast<AllocationInst>(Val)) { 15309467b48Spatrick // ... 15409467b48Spatrick } 15509467b48Spatrick 15609467b48Spatrick This form of the ``if`` statement effectively combines together a call to 15709467b48Spatrick ``isa<>`` and a call to ``cast<>`` into one statement, which is very 15809467b48Spatrick convenient. 15909467b48Spatrick 16009467b48Spatrick Note that the ``dyn_cast<>`` operator, like C++'s ``dynamic_cast<>`` or Java's 16109467b48Spatrick ``instanceof`` operator, can be abused. In particular, you should not use big 16209467b48Spatrick chained ``if/then/else`` blocks to check for lots of different variants of 16309467b48Spatrick classes. If you find yourself wanting to do this, it is much cleaner and more 16409467b48Spatrick efficient to use the ``InstVisitor`` class to dispatch over the instruction 16509467b48Spatrick type directly. 16609467b48Spatrick 16709467b48Spatrick``isa_and_nonnull<>``: 16809467b48Spatrick The ``isa_and_nonnull<>`` operator works just like the ``isa<>`` operator, 16909467b48Spatrick except that it allows for a null pointer as an argument (which it then 17009467b48Spatrick returns false). This can sometimes be useful, allowing you to combine several 17109467b48Spatrick null checks into one. 17209467b48Spatrick 17309467b48Spatrick``cast_or_null<>``: 17409467b48Spatrick The ``cast_or_null<>`` operator works just like the ``cast<>`` operator, 17509467b48Spatrick except that it allows for a null pointer as an argument (which it then 17609467b48Spatrick propagates). This can sometimes be useful, allowing you to combine several 17709467b48Spatrick null checks into one. 17809467b48Spatrick 17909467b48Spatrick``dyn_cast_or_null<>``: 18009467b48Spatrick The ``dyn_cast_or_null<>`` operator works just like the ``dyn_cast<>`` 18109467b48Spatrick operator, except that it allows for a null pointer as an argument (which it 18209467b48Spatrick then propagates). This can sometimes be useful, allowing you to combine 18309467b48Spatrick several null checks into one. 18409467b48Spatrick 18509467b48SpatrickThese five templates can be used with any classes, whether they have a v-table 18609467b48Spatrickor not. If you want to add support for these templates, see the document 18709467b48Spatrick:doc:`How to set up LLVM-style RTTI for your class hierarchy 18809467b48Spatrick<HowToSetUpLLVMStyleRTTI>` 18909467b48Spatrick 19009467b48Spatrick.. _string_apis: 19109467b48Spatrick 19209467b48SpatrickPassing strings (the ``StringRef`` and ``Twine`` classes) 19309467b48Spatrick--------------------------------------------------------- 19409467b48Spatrick 19509467b48SpatrickAlthough LLVM generally does not do much string manipulation, we do have several 19609467b48Spatrickimportant APIs which take strings. Two important examples are the Value class 19709467b48Spatrick-- which has names for instructions, functions, etc. -- and the ``StringMap`` 19809467b48Spatrickclass which is used extensively in LLVM and Clang. 19909467b48Spatrick 20009467b48SpatrickThese are generic classes, and they need to be able to accept strings which may 20109467b48Spatrickhave embedded null characters. Therefore, they cannot simply take a ``const 20209467b48Spatrickchar *``, and taking a ``const std::string&`` requires clients to perform a heap 20309467b48Spatrickallocation which is usually unnecessary. Instead, many LLVM APIs use a 20409467b48Spatrick``StringRef`` or a ``const Twine&`` for passing strings efficiently. 20509467b48Spatrick 20609467b48Spatrick.. _StringRef: 20709467b48Spatrick 20809467b48SpatrickThe ``StringRef`` class 20909467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 21009467b48Spatrick 21109467b48SpatrickThe ``StringRef`` data type represents a reference to a constant string (a 21209467b48Spatrickcharacter array and a length) and supports the common operations available on 21309467b48Spatrick``std::string``, but does not require heap allocation. 21409467b48Spatrick 21509467b48SpatrickIt can be implicitly constructed using a C style null-terminated string, an 21609467b48Spatrick``std::string``, or explicitly with a character pointer and length. For 217*d415bd75Srobertexample, the ``StringMap`` find function is declared as: 21809467b48Spatrick 21909467b48Spatrick.. code-block:: c++ 22009467b48Spatrick 22109467b48Spatrick iterator find(StringRef Key); 22209467b48Spatrick 22309467b48Spatrickand clients can call it using any one of: 22409467b48Spatrick 22509467b48Spatrick.. code-block:: c++ 22609467b48Spatrick 22709467b48Spatrick Map.find("foo"); // Lookup "foo" 22809467b48Spatrick Map.find(std::string("bar")); // Lookup "bar" 22909467b48Spatrick Map.find(StringRef("\0baz", 4)); // Lookup "\0baz" 23009467b48Spatrick 23109467b48SpatrickSimilarly, APIs which need to return a string may return a ``StringRef`` 23209467b48Spatrickinstance, which can be used directly or converted to an ``std::string`` using 23309467b48Spatrickthe ``str`` member function. See ``llvm/ADT/StringRef.h`` (`doxygen 234097a140dSpatrick<https://llvm.org/doxygen/StringRef_8h_source.html>`__) for more 23509467b48Spatrickinformation. 23609467b48Spatrick 23709467b48SpatrickYou should rarely use the ``StringRef`` class directly, because it contains 23809467b48Spatrickpointers to external memory it is not generally safe to store an instance of the 23909467b48Spatrickclass (unless you know that the external storage will not be freed). 24009467b48Spatrick``StringRef`` is small and pervasive enough in LLVM that it should always be 24109467b48Spatrickpassed by value. 24209467b48Spatrick 24309467b48SpatrickThe ``Twine`` class 24409467b48Spatrick^^^^^^^^^^^^^^^^^^^ 24509467b48Spatrick 246097a140dSpatrickThe ``Twine`` (`doxygen <https://llvm.org/doxygen/classllvm_1_1Twine.html>`__) 24709467b48Spatrickclass is an efficient way for APIs to accept concatenated strings. For example, 24809467b48Spatricka common LLVM paradigm is to name one instruction based on the name of another 24909467b48Spatrickinstruction with a suffix, for example: 25009467b48Spatrick 25109467b48Spatrick.. code-block:: c++ 25209467b48Spatrick 25309467b48Spatrick New = CmpInst::Create(..., SO->getName() + ".cmp"); 25409467b48Spatrick 25509467b48SpatrickThe ``Twine`` class is effectively a lightweight `rope 25609467b48Spatrick<http://en.wikipedia.org/wiki/Rope_(computer_science)>`_ which points to 25709467b48Spatricktemporary (stack allocated) objects. Twines can be implicitly constructed as 25809467b48Spatrickthe result of the plus operator applied to strings (i.e., a C strings, an 25909467b48Spatrick``std::string``, or a ``StringRef``). The twine delays the actual concatenation 26009467b48Spatrickof strings until it is actually required, at which point it can be efficiently 26109467b48Spatrickrendered directly into a character array. This avoids unnecessary heap 26209467b48Spatrickallocation involved in constructing the temporary results of string 26309467b48Spatrickconcatenation. See ``llvm/ADT/Twine.h`` (`doxygen 264097a140dSpatrick<https://llvm.org/doxygen/Twine_8h_source.html>`__) and :ref:`here <dss_twine>` 26509467b48Spatrickfor more information. 26609467b48Spatrick 26709467b48SpatrickAs with a ``StringRef``, ``Twine`` objects point to external memory and should 26809467b48Spatrickalmost never be stored or mentioned directly. They are intended solely for use 26909467b48Spatrickwhen defining a function which should be able to efficiently accept concatenated 27009467b48Spatrickstrings. 27109467b48Spatrick 27209467b48Spatrick.. _formatting_strings: 27309467b48Spatrick 27409467b48SpatrickFormatting strings (the ``formatv`` function) 27509467b48Spatrick--------------------------------------------- 27609467b48SpatrickWhile LLVM doesn't necessarily do a lot of string manipulation and parsing, it 27709467b48Spatrickdoes do a lot of string formatting. From diagnostic messages, to llvm tool 27809467b48Spatrickoutputs such as ``llvm-readobj`` to printing verbose disassembly listings and 27909467b48SpatrickLLDB runtime logging, the need for string formatting is pervasive. 28009467b48Spatrick 28109467b48SpatrickThe ``formatv`` is similar in spirit to ``printf``, but uses a different syntax 28209467b48Spatrickwhich borrows heavily from Python and C#. Unlike ``printf`` it deduces the type 28309467b48Spatrickto be formatted at compile time, so it does not need a format specifier such as 28409467b48Spatrick``%d``. This reduces the mental overhead of trying to construct portable format 28509467b48Spatrickstrings, especially for platform-specific types like ``size_t`` or pointer types. 28609467b48SpatrickUnlike both ``printf`` and Python, it additionally fails to compile if LLVM does 28709467b48Spatricknot know how to format the type. These two properties ensure that the function 28809467b48Spatrickis both safer and simpler to use than traditional formatting methods such as 28909467b48Spatrickthe ``printf`` family of functions. 29009467b48Spatrick 29109467b48SpatrickSimple formatting 29209467b48Spatrick^^^^^^^^^^^^^^^^^ 29309467b48Spatrick 29409467b48SpatrickA call to ``formatv`` involves a single **format string** consisting of 0 or more 29509467b48Spatrick**replacement sequences**, followed by a variable length list of **replacement values**. 29609467b48SpatrickA replacement sequence is a string of the form ``{N[[,align]:style]}``. 29709467b48Spatrick 29809467b48Spatrick``N`` refers to the 0-based index of the argument from the list of replacement 29909467b48Spatrickvalues. Note that this means it is possible to reference the same parameter 30009467b48Spatrickmultiple times, possibly with different style and/or alignment options, in any order. 30109467b48Spatrick 30209467b48Spatrick``align`` is an optional string specifying the width of the field to format 30309467b48Spatrickthe value into, and the alignment of the value within the field. It is specified as 30409467b48Spatrickan optional **alignment style** followed by a positive integral **field width**. The 30509467b48Spatrickalignment style can be one of the characters ``-`` (left align), ``=`` (center align), 30609467b48Spatrickor ``+`` (right align). The default is right aligned. 30709467b48Spatrick 30809467b48Spatrick``style`` is an optional string consisting of a type specific that controls the 30909467b48Spatrickformatting of the value. For example, to format a floating point value as a percentage, 31009467b48Spatrickyou can use the style option ``P``. 31109467b48Spatrick 31209467b48SpatrickCustom formatting 31309467b48Spatrick^^^^^^^^^^^^^^^^^ 31409467b48Spatrick 31509467b48SpatrickThere are two ways to customize the formatting behavior for a type. 31609467b48Spatrick 31709467b48Spatrick1. Provide a template specialization of ``llvm::format_provider<T>`` for your 31809467b48Spatrick type ``T`` with the appropriate static format method. 31909467b48Spatrick 32009467b48Spatrick .. code-block:: c++ 32109467b48Spatrick 32209467b48Spatrick namespace llvm { 32309467b48Spatrick template<> 32409467b48Spatrick struct format_provider<MyFooBar> { 32509467b48Spatrick static void format(const MyFooBar &V, raw_ostream &Stream, StringRef Style) { 32609467b48Spatrick // Do whatever is necessary to format `V` into `Stream` 32709467b48Spatrick } 32809467b48Spatrick }; 32909467b48Spatrick void foo() { 33009467b48Spatrick MyFooBar X; 33109467b48Spatrick std::string S = formatv("{0}", X); 33209467b48Spatrick } 33309467b48Spatrick } 33409467b48Spatrick 33509467b48Spatrick This is a useful extensibility mechanism for adding support for formatting your own 33609467b48Spatrick custom types with your own custom Style options. But it does not help when you want 33709467b48Spatrick to extend the mechanism for formatting a type that the library already knows how to 33809467b48Spatrick format. For that, we need something else. 33909467b48Spatrick 34009467b48Spatrick2. Provide a **format adapter** inheriting from ``llvm::FormatAdapter<T>``. 34109467b48Spatrick 34209467b48Spatrick .. code-block:: c++ 34309467b48Spatrick 34409467b48Spatrick namespace anything { 34509467b48Spatrick struct format_int_custom : public llvm::FormatAdapter<int> { 34609467b48Spatrick explicit format_int_custom(int N) : llvm::FormatAdapter<int>(N) {} 34709467b48Spatrick void format(llvm::raw_ostream &Stream, StringRef Style) override { 34809467b48Spatrick // Do whatever is necessary to format ``this->Item`` into ``Stream`` 34909467b48Spatrick } 35009467b48Spatrick }; 35109467b48Spatrick } 35209467b48Spatrick namespace llvm { 35309467b48Spatrick void foo() { 35409467b48Spatrick std::string S = formatv("{0}", anything::format_int_custom(42)); 35509467b48Spatrick } 35609467b48Spatrick } 35709467b48Spatrick 35809467b48Spatrick If the type is detected to be derived from ``FormatAdapter<T>``, ``formatv`` 35909467b48Spatrick will call the 36009467b48Spatrick ``format`` method on the argument passing in the specified style. This allows 36109467b48Spatrick one to provide custom formatting of any type, including one which already has 36209467b48Spatrick a builtin format provider. 36309467b48Spatrick 36409467b48Spatrick``formatv`` Examples 36509467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 36609467b48SpatrickBelow is intended to provide an incomplete set of examples demonstrating 36709467b48Spatrickthe usage of ``formatv``. More information can be found by reading the 36809467b48Spatrickdoxygen documentation or by looking at the unit test suite. 36909467b48Spatrick 37009467b48Spatrick 37109467b48Spatrick.. code-block:: c++ 37209467b48Spatrick 37309467b48Spatrick std::string S; 37409467b48Spatrick // Simple formatting of basic types and implicit string conversion. 37509467b48Spatrick S = formatv("{0} ({1:P})", 7, 0.35); // S == "7 (35.00%)" 37609467b48Spatrick 37709467b48Spatrick // Out-of-order referencing and multi-referencing 37809467b48Spatrick outs() << formatv("{0} {2} {1} {0}", 1, "test", 3); // prints "1 3 test 1" 37909467b48Spatrick 38009467b48Spatrick // Left, right, and center alignment 38109467b48Spatrick S = formatv("{0,7}", 'a'); // S == " a"; 38209467b48Spatrick S = formatv("{0,-7}", 'a'); // S == "a "; 38309467b48Spatrick S = formatv("{0,=7}", 'a'); // S == " a "; 38409467b48Spatrick S = formatv("{0,+7}", 'a'); // S == " a"; 38509467b48Spatrick 38609467b48Spatrick // Custom styles 38709467b48Spatrick S = formatv("{0:N} - {0:x} - {1:E}", 12345, 123908342); // S == "12,345 - 0x3039 - 1.24E8" 38809467b48Spatrick 38909467b48Spatrick // Adapters 39009467b48Spatrick S = formatv("{0}", fmt_align(42, AlignStyle::Center, 7)); // S == " 42 " 39109467b48Spatrick S = formatv("{0}", fmt_repeat("hi", 3)); // S == "hihihi" 39209467b48Spatrick S = formatv("{0}", fmt_pad("hi", 2, 6)); // S == " hi " 39309467b48Spatrick 39409467b48Spatrick // Ranges 39509467b48Spatrick std::vector<int> V = {8, 9, 10}; 39609467b48Spatrick S = formatv("{0}", make_range(V.begin(), V.end())); // S == "8, 9, 10" 39709467b48Spatrick S = formatv("{0:$[+]}", make_range(V.begin(), V.end())); // S == "8+9+10" 39809467b48Spatrick S = formatv("{0:$[ + ]@[x]}", make_range(V.begin(), V.end())); // S == "0x8 + 0x9 + 0xA" 39909467b48Spatrick 40009467b48Spatrick.. _error_apis: 40109467b48Spatrick 40209467b48SpatrickError handling 40309467b48Spatrick-------------- 40409467b48Spatrick 40509467b48SpatrickProper error handling helps us identify bugs in our code, and helps end-users 40609467b48Spatrickunderstand errors in their tool usage. Errors fall into two broad categories: 40709467b48Spatrick*programmatic* and *recoverable*, with different strategies for handling and 40809467b48Spatrickreporting. 40909467b48Spatrick 41009467b48SpatrickProgrammatic Errors 41109467b48Spatrick^^^^^^^^^^^^^^^^^^^ 41209467b48Spatrick 41309467b48SpatrickProgrammatic errors are violations of program invariants or API contracts, and 41409467b48Spatrickrepresent bugs within the program itself. Our aim is to document invariants, and 41509467b48Spatrickto abort quickly at the point of failure (providing some basic diagnostic) when 41609467b48Spatrickinvariants are broken at runtime. 41709467b48Spatrick 41809467b48SpatrickThe fundamental tools for handling programmatic errors are assertions and the 41909467b48Spatrickllvm_unreachable function. Assertions are used to express invariant conditions, 42009467b48Spatrickand should include a message describing the invariant: 42109467b48Spatrick 42209467b48Spatrick.. code-block:: c++ 42309467b48Spatrick 42409467b48Spatrick assert(isPhysReg(R) && "All virt regs should have been allocated already."); 42509467b48Spatrick 42609467b48SpatrickThe llvm_unreachable function can be used to document areas of control flow 42709467b48Spatrickthat should never be entered if the program invariants hold: 42809467b48Spatrick 42909467b48Spatrick.. code-block:: c++ 43009467b48Spatrick 43109467b48Spatrick enum { Foo, Bar, Baz } X = foo(); 43209467b48Spatrick 43309467b48Spatrick switch (X) { 43409467b48Spatrick case Foo: /* Handle Foo */; break; 43509467b48Spatrick case Bar: /* Handle Bar */; break; 43609467b48Spatrick default: 43709467b48Spatrick llvm_unreachable("X should be Foo or Bar here"); 43809467b48Spatrick } 43909467b48Spatrick 44009467b48SpatrickRecoverable Errors 44109467b48Spatrick^^^^^^^^^^^^^^^^^^ 44209467b48Spatrick 44309467b48SpatrickRecoverable errors represent an error in the program's environment, for example 44409467b48Spatricka resource failure (a missing file, a dropped network connection, etc.), or 44509467b48Spatrickmalformed input. These errors should be detected and communicated to a level of 44609467b48Spatrickthe program where they can be handled appropriately. Handling the error may be 44709467b48Spatrickas simple as reporting the issue to the user, or it may involve attempts at 44809467b48Spatrickrecovery. 44909467b48Spatrick 45009467b48Spatrick.. note:: 45109467b48Spatrick 45209467b48Spatrick While it would be ideal to use this error handling scheme throughout 45309467b48Spatrick LLVM, there are places where this hasn't been practical to apply. In 45409467b48Spatrick situations where you absolutely must emit a non-programmatic error and 45509467b48Spatrick the ``Error`` model isn't workable you can call ``report_fatal_error``, 456097a140dSpatrick which will call installed error handlers, print a message, and abort the 457097a140dSpatrick program. The use of `report_fatal_error` in this case is discouraged. 45809467b48Spatrick 45909467b48SpatrickRecoverable errors are modeled using LLVM's ``Error`` scheme. This scheme 46009467b48Spatrickrepresents errors using function return values, similar to classic C integer 46109467b48Spatrickerror codes, or C++'s ``std::error_code``. However, the ``Error`` class is 46209467b48Spatrickactually a lightweight wrapper for user-defined error types, allowing arbitrary 46309467b48Spatrickinformation to be attached to describe the error. This is similar to the way C++ 46409467b48Spatrickexceptions allow throwing of user-defined types. 46509467b48Spatrick 46609467b48SpatrickSuccess values are created by calling ``Error::success()``, E.g.: 46709467b48Spatrick 46809467b48Spatrick.. code-block:: c++ 46909467b48Spatrick 47009467b48Spatrick Error foo() { 47109467b48Spatrick // Do something. 47209467b48Spatrick // Return success. 47309467b48Spatrick return Error::success(); 47409467b48Spatrick } 47509467b48Spatrick 47609467b48SpatrickSuccess values are very cheap to construct and return - they have minimal 47709467b48Spatrickimpact on program performance. 47809467b48Spatrick 47909467b48SpatrickFailure values are constructed using ``make_error<T>``, where ``T`` is any class 48009467b48Spatrickthat inherits from the ErrorInfo utility, E.g.: 48109467b48Spatrick 48209467b48Spatrick.. code-block:: c++ 48309467b48Spatrick 48409467b48Spatrick class BadFileFormat : public ErrorInfo<BadFileFormat> { 48509467b48Spatrick public: 48609467b48Spatrick static char ID; 48709467b48Spatrick std::string Path; 48809467b48Spatrick 48909467b48Spatrick BadFileFormat(StringRef Path) : Path(Path.str()) {} 49009467b48Spatrick 49109467b48Spatrick void log(raw_ostream &OS) const override { 49209467b48Spatrick OS << Path << " is malformed"; 49309467b48Spatrick } 49409467b48Spatrick 49509467b48Spatrick std::error_code convertToErrorCode() const override { 49609467b48Spatrick return make_error_code(object_error::parse_failed); 49709467b48Spatrick } 49809467b48Spatrick }; 49909467b48Spatrick 50009467b48Spatrick char BadFileFormat::ID; // This should be declared in the C++ file. 50109467b48Spatrick 50209467b48Spatrick Error printFormattedFile(StringRef Path) { 50309467b48Spatrick if (<check for valid format>) 50409467b48Spatrick return make_error<BadFileFormat>(Path); 50509467b48Spatrick // print file contents. 50609467b48Spatrick return Error::success(); 50709467b48Spatrick } 50809467b48Spatrick 50909467b48SpatrickError values can be implicitly converted to bool: true for error, false for 51009467b48Spatricksuccess, enabling the following idiom: 51109467b48Spatrick 51209467b48Spatrick.. code-block:: c++ 51309467b48Spatrick 51409467b48Spatrick Error mayFail(); 51509467b48Spatrick 51609467b48Spatrick Error foo() { 51709467b48Spatrick if (auto Err = mayFail()) 51809467b48Spatrick return Err; 51909467b48Spatrick // Success! We can proceed. 52009467b48Spatrick ... 52109467b48Spatrick 52209467b48SpatrickFor functions that can fail but need to return a value the ``Expected<T>`` 52309467b48Spatrickutility can be used. Values of this type can be constructed with either a 52409467b48Spatrick``T``, or an ``Error``. Expected<T> values are also implicitly convertible to 52509467b48Spatrickboolean, but with the opposite convention to ``Error``: true for success, false 52609467b48Spatrickfor error. If success, the ``T`` value can be accessed via the dereference 52709467b48Spatrickoperator. If failure, the ``Error`` value can be extracted using the 52809467b48Spatrick``takeError()`` method. Idiomatic usage looks like: 52909467b48Spatrick 53009467b48Spatrick.. code-block:: c++ 53109467b48Spatrick 53209467b48Spatrick Expected<FormattedFile> openFormattedFile(StringRef Path) { 53309467b48Spatrick // If badly formatted, return an error. 53409467b48Spatrick if (auto Err = checkFormat(Path)) 53509467b48Spatrick return std::move(Err); 53609467b48Spatrick // Otherwise return a FormattedFile instance. 53709467b48Spatrick return FormattedFile(Path); 53809467b48Spatrick } 53909467b48Spatrick 54009467b48Spatrick Error processFormattedFile(StringRef Path) { 54109467b48Spatrick // Try to open a formatted file 54209467b48Spatrick if (auto FileOrErr = openFormattedFile(Path)) { 54309467b48Spatrick // On success, grab a reference to the file and continue. 54409467b48Spatrick auto &File = *FileOrErr; 54509467b48Spatrick ... 54609467b48Spatrick } else 54709467b48Spatrick // On error, extract the Error value and return it. 54809467b48Spatrick return FileOrErr.takeError(); 54909467b48Spatrick } 55009467b48Spatrick 55109467b48SpatrickIf an ``Expected<T>`` value is in success mode then the ``takeError()`` method 55209467b48Spatrickwill return a success value. Using this fact, the above function can be 55309467b48Spatrickrewritten as: 55409467b48Spatrick 55509467b48Spatrick.. code-block:: c++ 55609467b48Spatrick 55709467b48Spatrick Error processFormattedFile(StringRef Path) { 55809467b48Spatrick // Try to open a formatted file 55909467b48Spatrick auto FileOrErr = openFormattedFile(Path); 56009467b48Spatrick if (auto Err = FileOrErr.takeError()) 56109467b48Spatrick // On error, extract the Error value and return it. 56209467b48Spatrick return Err; 56309467b48Spatrick // On success, grab a reference to the file and continue. 56409467b48Spatrick auto &File = *FileOrErr; 56509467b48Spatrick ... 56609467b48Spatrick } 56709467b48Spatrick 56809467b48SpatrickThis second form is often more readable for functions that involve multiple 56909467b48Spatrick``Expected<T>`` values as it limits the indentation required. 57009467b48Spatrick 571*d415bd75SrobertIf an ``Expected<T>`` value will be moved into an existing variable then the 572*d415bd75Srobert``moveInto()`` method avoids the need to name an extra variable. This is 573*d415bd75Srobertuseful to enable ``operator->()`` the ``Expected<T>`` value has pointer-like 574*d415bd75Srobertsemantics. For example: 575*d415bd75Srobert 576*d415bd75Srobert.. code-block:: c++ 577*d415bd75Srobert 578*d415bd75Srobert Expected<std::unique_ptr<MemoryBuffer>> openBuffer(StringRef Path); 579*d415bd75Srobert Error processBuffer(StringRef Buffer); 580*d415bd75Srobert 581*d415bd75Srobert Error processBufferAtPath(StringRef Path) { 582*d415bd75Srobert // Try to open a buffer. 583*d415bd75Srobert std::unique_ptr<MemoryBuffer> MB; 584*d415bd75Srobert if (auto Err = openBuffer(Path).moveInto(MB)) 585*d415bd75Srobert // On error, return the Error value. 586*d415bd75Srobert return Err; 587*d415bd75Srobert // On success, use MB. 588*d415bd75Srobert return processBuffer(MB->getBuffer()); 589*d415bd75Srobert } 590*d415bd75Srobert 591*d415bd75SrobertThis third form works with any type that can be assigned to from ``T&&``. This 592*d415bd75Srobertcan be useful if the ``Expected<T>`` value needs to be stored an already-declared 593*d415bd75Srobert``Optional<T>``. For example: 594*d415bd75Srobert 595*d415bd75Srobert.. code-block:: c++ 596*d415bd75Srobert 597*d415bd75Srobert Expected<StringRef> extractClassName(StringRef Definition); 598*d415bd75Srobert struct ClassData { 599*d415bd75Srobert StringRef Definition; 600*d415bd75Srobert Optional<StringRef> LazyName; 601*d415bd75Srobert ... 602*d415bd75Srobert Error initialize() { 603*d415bd75Srobert if (auto Err = extractClassName(Path).moveInto(LazyName)) 604*d415bd75Srobert // On error, return the Error value. 605*d415bd75Srobert return Err; 606*d415bd75Srobert // On success, LazyName has been initialized. 607*d415bd75Srobert ... 608*d415bd75Srobert } 609*d415bd75Srobert }; 610*d415bd75Srobert 61109467b48SpatrickAll ``Error`` instances, whether success or failure, must be either checked or 61209467b48Spatrickmoved from (via ``std::move`` or a return) before they are destructed. 61309467b48SpatrickAccidentally discarding an unchecked error will cause a program abort at the 61409467b48Spatrickpoint where the unchecked value's destructor is run, making it easy to identify 61509467b48Spatrickand fix violations of this rule. 61609467b48Spatrick 61709467b48SpatrickSuccess values are considered checked once they have been tested (by invoking 61809467b48Spatrickthe boolean conversion operator): 61909467b48Spatrick 62009467b48Spatrick.. code-block:: c++ 62109467b48Spatrick 62209467b48Spatrick if (auto Err = mayFail(...)) 62309467b48Spatrick return Err; // Failure value - move error to caller. 62409467b48Spatrick 62509467b48Spatrick // Safe to continue: Err was checked. 62609467b48Spatrick 62709467b48SpatrickIn contrast, the following code will always cause an abort, even if ``mayFail`` 62809467b48Spatrickreturns a success value: 62909467b48Spatrick 63009467b48Spatrick.. code-block:: c++ 63109467b48Spatrick 63209467b48Spatrick mayFail(); 63309467b48Spatrick // Program will always abort here, even if mayFail() returns Success, since 63409467b48Spatrick // the value is not checked. 63509467b48Spatrick 63609467b48SpatrickFailure values are considered checked once a handler for the error type has 63709467b48Spatrickbeen activated: 63809467b48Spatrick 63909467b48Spatrick.. code-block:: c++ 64009467b48Spatrick 64109467b48Spatrick handleErrors( 64209467b48Spatrick processFormattedFile(...), 64309467b48Spatrick [](const BadFileFormat &BFF) { 64409467b48Spatrick report("Unable to process " + BFF.Path + ": bad format"); 64509467b48Spatrick }, 64609467b48Spatrick [](const FileNotFound &FNF) { 64709467b48Spatrick report("File not found " + FNF.Path); 64809467b48Spatrick }); 64909467b48Spatrick 65009467b48SpatrickThe ``handleErrors`` function takes an error as its first argument, followed by 65109467b48Spatricka variadic list of "handlers", each of which must be a callable type (a 65209467b48Spatrickfunction, lambda, or class with a call operator) with one argument. The 65309467b48Spatrick``handleErrors`` function will visit each handler in the sequence and check its 65409467b48Spatrickargument type against the dynamic type of the error, running the first handler 65509467b48Spatrickthat matches. This is the same decision process that is used decide which catch 65609467b48Spatrickclause to run for a C++ exception. 65709467b48Spatrick 65809467b48SpatrickSince the list of handlers passed to ``handleErrors`` may not cover every error 65909467b48Spatricktype that can occur, the ``handleErrors`` function also returns an Error value 66009467b48Spatrickthat must be checked or propagated. If the error value that is passed to 66109467b48Spatrick``handleErrors`` does not match any of the handlers it will be returned from 66209467b48SpatrickhandleErrors. Idiomatic use of ``handleErrors`` thus looks like: 66309467b48Spatrick 66409467b48Spatrick.. code-block:: c++ 66509467b48Spatrick 66609467b48Spatrick if (auto Err = 66709467b48Spatrick handleErrors( 66809467b48Spatrick processFormattedFile(...), 66909467b48Spatrick [](const BadFileFormat &BFF) { 67009467b48Spatrick report("Unable to process " + BFF.Path + ": bad format"); 67109467b48Spatrick }, 67209467b48Spatrick [](const FileNotFound &FNF) { 67309467b48Spatrick report("File not found " + FNF.Path); 67409467b48Spatrick })) 67509467b48Spatrick return Err; 67609467b48Spatrick 67709467b48SpatrickIn cases where you truly know that the handler list is exhaustive the 67809467b48Spatrick``handleAllErrors`` function can be used instead. This is identical to 67909467b48Spatrick``handleErrors`` except that it will terminate the program if an unhandled 68009467b48Spatrickerror is passed in, and can therefore return void. The ``handleAllErrors`` 68109467b48Spatrickfunction should generally be avoided: the introduction of a new error type 68209467b48Spatrickelsewhere in the program can easily turn a formerly exhaustive list of errors 68309467b48Spatrickinto a non-exhaustive list, risking unexpected program termination. Where 68409467b48Spatrickpossible, use handleErrors and propagate unknown errors up the stack instead. 68509467b48Spatrick 68609467b48SpatrickFor tool code, where errors can be handled by printing an error message then 68709467b48Spatrickexiting with an error code, the :ref:`ExitOnError <err_exitonerr>` utility 68809467b48Spatrickmay be a better choice than handleErrors, as it simplifies control flow when 68909467b48Spatrickcalling fallible functions. 69009467b48Spatrick 69109467b48SpatrickIn situations where it is known that a particular call to a fallible function 69209467b48Spatrickwill always succeed (for example, a call to a function that can only fail on a 69309467b48Spatricksubset of inputs with an input that is known to be safe) the 69409467b48Spatrick:ref:`cantFail <err_cantfail>` functions can be used to remove the error type, 69509467b48Spatricksimplifying control flow. 69609467b48Spatrick 69709467b48SpatrickStringError 69809467b48Spatrick""""""""""" 69909467b48Spatrick 70009467b48SpatrickMany kinds of errors have no recovery strategy, the only action that can be 70109467b48Spatricktaken is to report them to the user so that the user can attempt to fix the 70209467b48Spatrickenvironment. In this case representing the error as a string makes perfect 70309467b48Spatricksense. LLVM provides the ``StringError`` class for this purpose. It takes two 70409467b48Spatrickarguments: A string error message, and an equivalent ``std::error_code`` for 70509467b48Spatrickinteroperability. It also provides a ``createStringError`` function to simplify 70609467b48Spatrickcommon usage of this class: 70709467b48Spatrick 70809467b48Spatrick.. code-block:: c++ 70909467b48Spatrick 71009467b48Spatrick // These two lines of code are equivalent: 71109467b48Spatrick make_error<StringError>("Bad executable", errc::executable_format_error); 71209467b48Spatrick createStringError(errc::executable_format_error, "Bad executable"); 71309467b48Spatrick 71409467b48SpatrickIf you're certain that the error you're building will never need to be converted 71509467b48Spatrickto a ``std::error_code`` you can use the ``inconvertibleErrorCode()`` function: 71609467b48Spatrick 71709467b48Spatrick.. code-block:: c++ 71809467b48Spatrick 71909467b48Spatrick createStringError(inconvertibleErrorCode(), "Bad executable"); 72009467b48Spatrick 72109467b48SpatrickThis should be done only after careful consideration. If any attempt is made to 72209467b48Spatrickconvert this error to a ``std::error_code`` it will trigger immediate program 72309467b48Spatricktermination. Unless you are certain that your errors will not need 72409467b48Spatrickinteroperability you should look for an existing ``std::error_code`` that you 72509467b48Spatrickcan convert to, and even (as painful as it is) consider introducing a new one as 72609467b48Spatricka stopgap measure. 72709467b48Spatrick 72809467b48Spatrick``createStringError`` can take ``printf`` style format specifiers to provide a 72909467b48Spatrickformatted message: 73009467b48Spatrick 73109467b48Spatrick.. code-block:: c++ 73209467b48Spatrick 73309467b48Spatrick createStringError(errc::executable_format_error, 73409467b48Spatrick "Bad executable: %s", FileName); 73509467b48Spatrick 73609467b48SpatrickInteroperability with std::error_code and ErrorOr 73709467b48Spatrick""""""""""""""""""""""""""""""""""""""""""""""""" 73809467b48Spatrick 73909467b48SpatrickMany existing LLVM APIs use ``std::error_code`` and its partner ``ErrorOr<T>`` 74009467b48Spatrick(which plays the same role as ``Expected<T>``, but wraps a ``std::error_code`` 74109467b48Spatrickrather than an ``Error``). The infectious nature of error types means that an 74209467b48Spatrickattempt to change one of these functions to return ``Error`` or ``Expected<T>`` 74309467b48Spatrickinstead often results in an avalanche of changes to callers, callers of callers, 74409467b48Spatrickand so on. (The first such attempt, returning an ``Error`` from 74509467b48SpatrickMachOObjectFile's constructor, was abandoned after the diff reached 3000 lines, 74609467b48Spatrickimpacted half a dozen libraries, and was still growing). 74709467b48Spatrick 74809467b48SpatrickTo solve this problem, the ``Error``/``std::error_code`` interoperability requirement was 74909467b48Spatrickintroduced. Two pairs of functions allow any ``Error`` value to be converted to a 75009467b48Spatrick``std::error_code``, any ``Expected<T>`` to be converted to an ``ErrorOr<T>``, and vice 75109467b48Spatrickversa: 75209467b48Spatrick 75309467b48Spatrick.. code-block:: c++ 75409467b48Spatrick 75509467b48Spatrick std::error_code errorToErrorCode(Error Err); 75609467b48Spatrick Error errorCodeToError(std::error_code EC); 75709467b48Spatrick 75809467b48Spatrick template <typename T> ErrorOr<T> expectedToErrorOr(Expected<T> TOrErr); 75909467b48Spatrick template <typename T> Expected<T> errorOrToExpected(ErrorOr<T> TOrEC); 76009467b48Spatrick 76109467b48Spatrick 76209467b48SpatrickUsing these APIs it is easy to make surgical patches that update individual 76309467b48Spatrickfunctions from ``std::error_code`` to ``Error``, and from ``ErrorOr<T>`` to 76409467b48Spatrick``Expected<T>``. 76509467b48Spatrick 76609467b48SpatrickReturning Errors from error handlers 76709467b48Spatrick"""""""""""""""""""""""""""""""""""" 76809467b48Spatrick 76909467b48SpatrickError recovery attempts may themselves fail. For that reason, ``handleErrors`` 77009467b48Spatrickactually recognises three different forms of handler signature: 77109467b48Spatrick 77209467b48Spatrick.. code-block:: c++ 77309467b48Spatrick 77409467b48Spatrick // Error must be handled, no new errors produced: 77509467b48Spatrick void(UserDefinedError &E); 77609467b48Spatrick 77709467b48Spatrick // Error must be handled, new errors can be produced: 77809467b48Spatrick Error(UserDefinedError &E); 77909467b48Spatrick 78009467b48Spatrick // Original error can be inspected, then re-wrapped and returned (or a new 78109467b48Spatrick // error can be produced): 78209467b48Spatrick Error(std::unique_ptr<UserDefinedError> E); 78309467b48Spatrick 78409467b48SpatrickAny error returned from a handler will be returned from the ``handleErrors`` 78509467b48Spatrickfunction so that it can be handled itself, or propagated up the stack. 78609467b48Spatrick 78709467b48Spatrick.. _err_exitonerr: 78809467b48Spatrick 78909467b48SpatrickUsing ExitOnError to simplify tool code 79009467b48Spatrick""""""""""""""""""""""""""""""""""""""" 79109467b48Spatrick 79209467b48SpatrickLibrary code should never call ``exit`` for a recoverable error, however in tool 79309467b48Spatrickcode (especially command line tools) this can be a reasonable approach. Calling 79409467b48Spatrick``exit`` upon encountering an error dramatically simplifies control flow as the 79509467b48Spatrickerror no longer needs to be propagated up the stack. This allows code to be 79609467b48Spatrickwritten in straight-line style, as long as each fallible call is wrapped in a 79709467b48Spatrickcheck and call to exit. The ``ExitOnError`` class supports this pattern by 79809467b48Spatrickproviding call operators that inspect ``Error`` values, stripping the error away 79909467b48Spatrickin the success case and logging to ``stderr`` then exiting in the failure case. 80009467b48Spatrick 80109467b48SpatrickTo use this class, declare a global ``ExitOnError`` variable in your program: 80209467b48Spatrick 80309467b48Spatrick.. code-block:: c++ 80409467b48Spatrick 80509467b48Spatrick ExitOnError ExitOnErr; 80609467b48Spatrick 80709467b48SpatrickCalls to fallible functions can then be wrapped with a call to ``ExitOnErr``, 80809467b48Spatrickturning them into non-failing calls: 80909467b48Spatrick 81009467b48Spatrick.. code-block:: c++ 81109467b48Spatrick 81209467b48Spatrick Error mayFail(); 81309467b48Spatrick Expected<int> mayFail2(); 81409467b48Spatrick 81509467b48Spatrick void foo() { 81609467b48Spatrick ExitOnErr(mayFail()); 81709467b48Spatrick int X = ExitOnErr(mayFail2()); 81809467b48Spatrick } 81909467b48Spatrick 82009467b48SpatrickOn failure, the error's log message will be written to ``stderr``, optionally 82109467b48Spatrickpreceded by a string "banner" that can be set by calling the setBanner method. A 82209467b48Spatrickmapping can also be supplied from ``Error`` values to exit codes using the 82309467b48Spatrick``setExitCodeMapper`` method: 82409467b48Spatrick 82509467b48Spatrick.. code-block:: c++ 82609467b48Spatrick 82709467b48Spatrick int main(int argc, char *argv[]) { 82809467b48Spatrick ExitOnErr.setBanner(std::string(argv[0]) + " error:"); 82909467b48Spatrick ExitOnErr.setExitCodeMapper( 83009467b48Spatrick [](const Error &Err) { 83109467b48Spatrick if (Err.isA<BadFileFormat>()) 83209467b48Spatrick return 2; 83309467b48Spatrick return 1; 83409467b48Spatrick }); 83509467b48Spatrick 83609467b48SpatrickUse ``ExitOnError`` in your tool code where possible as it can greatly improve 83709467b48Spatrickreadability. 83809467b48Spatrick 83909467b48Spatrick.. _err_cantfail: 84009467b48Spatrick 84109467b48SpatrickUsing cantFail to simplify safe callsites 84209467b48Spatrick""""""""""""""""""""""""""""""""""""""""" 84309467b48Spatrick 84409467b48SpatrickSome functions may only fail for a subset of their inputs, so calls using known 84509467b48Spatricksafe inputs can be assumed to succeed. 84609467b48Spatrick 84709467b48SpatrickThe cantFail functions encapsulate this by wrapping an assertion that their 84809467b48Spatrickargument is a success value and, in the case of Expected<T>, unwrapping the 84909467b48SpatrickT value: 85009467b48Spatrick 85109467b48Spatrick.. code-block:: c++ 85209467b48Spatrick 85309467b48Spatrick Error onlyFailsForSomeXValues(int X); 85409467b48Spatrick Expected<int> onlyFailsForSomeXValues2(int X); 85509467b48Spatrick 85609467b48Spatrick void foo() { 85709467b48Spatrick cantFail(onlyFailsForSomeXValues(KnownSafeValue)); 85809467b48Spatrick int Y = cantFail(onlyFailsForSomeXValues2(KnownSafeValue)); 85909467b48Spatrick ... 86009467b48Spatrick } 86109467b48Spatrick 86209467b48SpatrickLike the ExitOnError utility, cantFail simplifies control flow. Their treatment 86309467b48Spatrickof error cases is very different however: Where ExitOnError is guaranteed to 86409467b48Spatrickterminate the program on an error input, cantFail simply asserts that the result 86509467b48Spatrickis success. In debug builds this will result in an assertion failure if an error 86609467b48Spatrickis encountered. In release builds the behavior of cantFail for failure values is 86709467b48Spatrickundefined. As such, care must be taken in the use of cantFail: clients must be 86809467b48Spatrickcertain that a cantFail wrapped call really can not fail with the given 86909467b48Spatrickarguments. 87009467b48Spatrick 87109467b48SpatrickUse of the cantFail functions should be rare in library code, but they are 87209467b48Spatricklikely to be of more use in tool and unit-test code where inputs and/or 87309467b48Spatrickmocked-up classes or functions may be known to be safe. 87409467b48Spatrick 87509467b48SpatrickFallible constructors 87609467b48Spatrick""""""""""""""""""""" 87709467b48Spatrick 87809467b48SpatrickSome classes require resource acquisition or other complex initialization that 87909467b48Spatrickcan fail during construction. Unfortunately constructors can't return errors, 88009467b48Spatrickand having clients test objects after they're constructed to ensure that they're 88109467b48Spatrickvalid is error prone as it's all too easy to forget the test. To work around 88209467b48Spatrickthis, use the named constructor idiom and return an ``Expected<T>``: 88309467b48Spatrick 88409467b48Spatrick.. code-block:: c++ 88509467b48Spatrick 88609467b48Spatrick class Foo { 88709467b48Spatrick public: 88809467b48Spatrick 88909467b48Spatrick static Expected<Foo> Create(Resource R1, Resource R2) { 890097a140dSpatrick Error Err = Error::success(); 89109467b48Spatrick Foo F(R1, R2, Err); 89209467b48Spatrick if (Err) 89309467b48Spatrick return std::move(Err); 89409467b48Spatrick return std::move(F); 89509467b48Spatrick } 89609467b48Spatrick 89709467b48Spatrick private: 89809467b48Spatrick 89909467b48Spatrick Foo(Resource R1, Resource R2, Error &Err) { 90009467b48Spatrick ErrorAsOutParameter EAO(&Err); 90109467b48Spatrick if (auto Err2 = R1.acquire()) { 90209467b48Spatrick Err = std::move(Err2); 90309467b48Spatrick return; 90409467b48Spatrick } 90509467b48Spatrick Err = R2.acquire(); 90609467b48Spatrick } 90709467b48Spatrick }; 90809467b48Spatrick 90909467b48Spatrick 91009467b48SpatrickHere, the named constructor passes an ``Error`` by reference into the actual 91109467b48Spatrickconstructor, which the constructor can then use to return errors. The 91209467b48Spatrick``ErrorAsOutParameter`` utility sets the ``Error`` value's checked flag on entry 91309467b48Spatrickto the constructor so that the error can be assigned to, then resets it on exit 91409467b48Spatrickto force the client (the named constructor) to check the error. 91509467b48Spatrick 91609467b48SpatrickBy using this idiom, clients attempting to construct a Foo receive either a 91709467b48Spatrickwell-formed Foo or an Error, never an object in an invalid state. 91809467b48Spatrick 91909467b48SpatrickPropagating and consuming errors based on types 92009467b48Spatrick""""""""""""""""""""""""""""""""""""""""""""""" 92109467b48Spatrick 92209467b48SpatrickIn some contexts, certain types of error are known to be benign. For example, 92309467b48Spatrickwhen walking an archive, some clients may be happy to skip over badly formatted 92409467b48Spatrickobject files rather than terminating the walk immediately. Skipping badly 92509467b48Spatrickformatted objects could be achieved using an elaborate handler method, but the 92609467b48SpatrickError.h header provides two utilities that make this idiom much cleaner: the 92709467b48Spatricktype inspection method, ``isA``, and the ``consumeError`` function: 92809467b48Spatrick 92909467b48Spatrick.. code-block:: c++ 93009467b48Spatrick 93109467b48Spatrick Error walkArchive(Archive A) { 93209467b48Spatrick for (unsigned I = 0; I != A.numMembers(); ++I) { 93309467b48Spatrick auto ChildOrErr = A.getMember(I); 93409467b48Spatrick if (auto Err = ChildOrErr.takeError()) { 93509467b48Spatrick if (Err.isA<BadFileFormat>()) 93609467b48Spatrick consumeError(std::move(Err)) 93709467b48Spatrick else 93809467b48Spatrick return Err; 93909467b48Spatrick } 94009467b48Spatrick auto &Child = *ChildOrErr; 94109467b48Spatrick // Use Child 94209467b48Spatrick ... 94309467b48Spatrick } 94409467b48Spatrick return Error::success(); 94509467b48Spatrick } 94609467b48Spatrick 94709467b48SpatrickConcatenating Errors with joinErrors 94809467b48Spatrick"""""""""""""""""""""""""""""""""""" 94909467b48Spatrick 95009467b48SpatrickIn the archive walking example above ``BadFileFormat`` errors are simply 95109467b48Spatrickconsumed and ignored. If the client had wanted report these errors after 95209467b48Spatrickcompleting the walk over the archive they could use the ``joinErrors`` utility: 95309467b48Spatrick 95409467b48Spatrick.. code-block:: c++ 95509467b48Spatrick 95609467b48Spatrick Error walkArchive(Archive A) { 95709467b48Spatrick Error DeferredErrs = Error::success(); 95809467b48Spatrick for (unsigned I = 0; I != A.numMembers(); ++I) { 95909467b48Spatrick auto ChildOrErr = A.getMember(I); 96009467b48Spatrick if (auto Err = ChildOrErr.takeError()) 96109467b48Spatrick if (Err.isA<BadFileFormat>()) 96209467b48Spatrick DeferredErrs = joinErrors(std::move(DeferredErrs), std::move(Err)); 96309467b48Spatrick else 96409467b48Spatrick return Err; 96509467b48Spatrick auto &Child = *ChildOrErr; 96609467b48Spatrick // Use Child 96709467b48Spatrick ... 96809467b48Spatrick } 96909467b48Spatrick return DeferredErrs; 97009467b48Spatrick } 97109467b48Spatrick 97209467b48SpatrickThe ``joinErrors`` routine builds a special error type called ``ErrorList``, 97309467b48Spatrickwhich holds a list of user defined errors. The ``handleErrors`` routine 97409467b48Spatrickrecognizes this type and will attempt to handle each of the contained errors in 97509467b48Spatrickorder. If all contained errors can be handled, ``handleErrors`` will return 97609467b48Spatrick``Error::success()``, otherwise ``handleErrors`` will concatenate the remaining 97709467b48Spatrickerrors and return the resulting ``ErrorList``. 97809467b48Spatrick 97909467b48SpatrickBuilding fallible iterators and iterator ranges 98009467b48Spatrick""""""""""""""""""""""""""""""""""""""""""""""" 98109467b48Spatrick 98209467b48SpatrickThe archive walking examples above retrieve archive members by index, however 98309467b48Spatrickthis requires considerable boiler-plate for iteration and error checking. We can 98409467b48Spatrickclean this up by using the "fallible iterator" pattern, which supports the 98509467b48Spatrickfollowing natural iteration idiom for fallible containers like Archive: 98609467b48Spatrick 98709467b48Spatrick.. code-block:: c++ 98809467b48Spatrick 989097a140dSpatrick Error Err = Error::success(); 99009467b48Spatrick for (auto &Child : Ar->children(Err)) { 99109467b48Spatrick // Use Child - only enter the loop when it's valid 99209467b48Spatrick 99309467b48Spatrick // Allow early exit from the loop body, since we know that Err is success 99409467b48Spatrick // when we're inside the loop. 99509467b48Spatrick if (BailOutOn(Child)) 99609467b48Spatrick return; 99709467b48Spatrick 99809467b48Spatrick ... 99909467b48Spatrick } 100009467b48Spatrick // Check Err after the loop to ensure it didn't break due to an error. 100109467b48Spatrick if (Err) 100209467b48Spatrick return Err; 100309467b48Spatrick 100409467b48SpatrickTo enable this idiom, iterators over fallible containers are written in a 100509467b48Spatricknatural style, with their ``++`` and ``--`` operators replaced with fallible 100609467b48Spatrick``Error inc()`` and ``Error dec()`` functions. E.g.: 100709467b48Spatrick 100809467b48Spatrick.. code-block:: c++ 100909467b48Spatrick 101009467b48Spatrick class FallibleChildIterator { 101109467b48Spatrick public: 101209467b48Spatrick FallibleChildIterator(Archive &A, unsigned ChildIdx); 101309467b48Spatrick Archive::Child &operator*(); 101409467b48Spatrick friend bool operator==(const ArchiveIterator &LHS, 101509467b48Spatrick const ArchiveIterator &RHS); 101609467b48Spatrick 101709467b48Spatrick // operator++/operator-- replaced with fallible increment / decrement: 101809467b48Spatrick Error inc() { 101909467b48Spatrick if (!A.childValid(ChildIdx + 1)) 102009467b48Spatrick return make_error<BadArchiveMember>(...); 102109467b48Spatrick ++ChildIdx; 102209467b48Spatrick return Error::success(); 102309467b48Spatrick } 102409467b48Spatrick 102509467b48Spatrick Error dec() { ... } 102609467b48Spatrick }; 102709467b48Spatrick 102809467b48SpatrickInstances of this kind of fallible iterator interface are then wrapped with the 102909467b48Spatrickfallible_iterator utility which provides ``operator++`` and ``operator--``, 103009467b48Spatrickreturning any errors via a reference passed in to the wrapper at construction 103109467b48Spatricktime. The fallible_iterator wrapper takes care of (a) jumping to the end of the 103209467b48Spatrickrange on error, and (b) marking the error as checked whenever an iterator is 103309467b48Spatrickcompared to ``end`` and found to be inequal (in particular: this marks the 103409467b48Spatrickerror as checked throughout the body of a range-based for loop), enabling early 103509467b48Spatrickexit from the loop without redundant error checking. 103609467b48Spatrick 103709467b48SpatrickInstances of the fallible iterator interface (e.g. FallibleChildIterator above) 103809467b48Spatrickare wrapped using the ``make_fallible_itr`` and ``make_fallible_end`` 103909467b48Spatrickfunctions. E.g.: 104009467b48Spatrick 104109467b48Spatrick.. code-block:: c++ 104209467b48Spatrick 104309467b48Spatrick class Archive { 104409467b48Spatrick public: 104509467b48Spatrick using child_iterator = fallible_iterator<FallibleChildIterator>; 104609467b48Spatrick 104709467b48Spatrick child_iterator child_begin(Error &Err) { 104809467b48Spatrick return make_fallible_itr(FallibleChildIterator(*this, 0), Err); 104909467b48Spatrick } 105009467b48Spatrick 105109467b48Spatrick child_iterator child_end() { 105209467b48Spatrick return make_fallible_end(FallibleChildIterator(*this, size())); 105309467b48Spatrick } 105409467b48Spatrick 105509467b48Spatrick iterator_range<child_iterator> children(Error &Err) { 105609467b48Spatrick return make_range(child_begin(Err), child_end()); 105709467b48Spatrick } 105809467b48Spatrick }; 105909467b48Spatrick 106009467b48SpatrickUsing the fallible_iterator utility allows for both natural construction of 106109467b48Spatrickfallible iterators (using failing ``inc`` and ``dec`` operations) and 106209467b48Spatrickrelatively natural use of c++ iterator/loop idioms. 106309467b48Spatrick 106409467b48Spatrick.. _function_apis: 106509467b48Spatrick 106609467b48SpatrickMore information on Error and its related utilities can be found in the 106709467b48SpatrickError.h header file. 106809467b48Spatrick 106909467b48SpatrickPassing functions and other callable objects 107009467b48Spatrick-------------------------------------------- 107109467b48Spatrick 107209467b48SpatrickSometimes you may want a function to be passed a callback object. In order to 107309467b48Spatricksupport lambda expressions and other function objects, you should not use the 107409467b48Spatricktraditional C approach of taking a function pointer and an opaque cookie: 107509467b48Spatrick 107609467b48Spatrick.. code-block:: c++ 107709467b48Spatrick 107809467b48Spatrick void takeCallback(bool (*Callback)(Function *, void *), void *Cookie); 107909467b48Spatrick 108009467b48SpatrickInstead, use one of the following approaches: 108109467b48Spatrick 108209467b48SpatrickFunction template 108309467b48Spatrick^^^^^^^^^^^^^^^^^ 108409467b48Spatrick 108509467b48SpatrickIf you don't mind putting the definition of your function into a header file, 108609467b48Spatrickmake it a function template that is templated on the callable type. 108709467b48Spatrick 108809467b48Spatrick.. code-block:: c++ 108909467b48Spatrick 109009467b48Spatrick template<typename Callable> 109109467b48Spatrick void takeCallback(Callable Callback) { 109209467b48Spatrick Callback(1, 2, 3); 109309467b48Spatrick } 109409467b48Spatrick 109509467b48SpatrickThe ``function_ref`` class template 109609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 109709467b48Spatrick 109809467b48SpatrickThe ``function_ref`` 1099097a140dSpatrick(`doxygen <https://llvm.org/doxygen/classllvm_1_1function__ref_3_01Ret_07Params_8_8_8_08_4.html>`__) class 110009467b48Spatricktemplate represents a reference to a callable object, templated over the type 110109467b48Spatrickof the callable. This is a good choice for passing a callback to a function, 110209467b48Spatrickif you don't need to hold onto the callback after the function returns. In this 110309467b48Spatrickway, ``function_ref`` is to ``std::function`` as ``StringRef`` is to 110409467b48Spatrick``std::string``. 110509467b48Spatrick 110609467b48Spatrick``function_ref<Ret(Param1, Param2, ...)>`` can be implicitly constructed from 110709467b48Spatrickany callable object that can be called with arguments of type ``Param1``, 110809467b48Spatrick``Param2``, ..., and returns a value that can be converted to type ``Ret``. 110909467b48SpatrickFor example: 111009467b48Spatrick 111109467b48Spatrick.. code-block:: c++ 111209467b48Spatrick 111309467b48Spatrick void visitBasicBlocks(Function *F, function_ref<bool (BasicBlock*)> Callback) { 111409467b48Spatrick for (BasicBlock &BB : *F) 111509467b48Spatrick if (Callback(&BB)) 111609467b48Spatrick return; 111709467b48Spatrick } 111809467b48Spatrick 111909467b48Spatrickcan be called using: 112009467b48Spatrick 112109467b48Spatrick.. code-block:: c++ 112209467b48Spatrick 112309467b48Spatrick visitBasicBlocks(F, [&](BasicBlock *BB) { 112409467b48Spatrick if (process(BB)) 112509467b48Spatrick return isEmpty(BB); 112609467b48Spatrick return false; 112709467b48Spatrick }); 112809467b48Spatrick 112909467b48SpatrickNote that a ``function_ref`` object contains pointers to external memory, so it 113009467b48Spatrickis not generally safe to store an instance of the class (unless you know that 113109467b48Spatrickthe external storage will not be freed). If you need this ability, consider 113209467b48Spatrickusing ``std::function``. ``function_ref`` is small enough that it should always 113309467b48Spatrickbe passed by value. 113409467b48Spatrick 113509467b48Spatrick.. _DEBUG: 113609467b48Spatrick 113709467b48SpatrickThe ``LLVM_DEBUG()`` macro and ``-debug`` option 113809467b48Spatrick------------------------------------------------ 113909467b48Spatrick 114009467b48SpatrickOften when working on your pass you will put a bunch of debugging printouts and 114109467b48Spatrickother code into your pass. After you get it working, you want to remove it, but 114209467b48Spatrickyou may need it again in the future (to work out new bugs that you run across). 114309467b48Spatrick 114409467b48SpatrickNaturally, because of this, you don't want to delete the debug printouts, but 114509467b48Spatrickyou don't want them to always be noisy. A standard compromise is to comment 114609467b48Spatrickthem out, allowing you to enable them if you need them in the future. 114709467b48Spatrick 114809467b48SpatrickThe ``llvm/Support/Debug.h`` (`doxygen 1149097a140dSpatrick<https://llvm.org/doxygen/Debug_8h_source.html>`__) file provides a macro named 115009467b48Spatrick``LLVM_DEBUG()`` that is a much nicer solution to this problem. Basically, you can 115109467b48Spatrickput arbitrary code into the argument of the ``LLVM_DEBUG`` macro, and it is only 115209467b48Spatrickexecuted if '``opt``' (or any other tool) is run with the '``-debug``' command 115309467b48Spatrickline argument: 115409467b48Spatrick 115509467b48Spatrick.. code-block:: c++ 115609467b48Spatrick 115709467b48Spatrick LLVM_DEBUG(dbgs() << "I am here!\n"); 115809467b48Spatrick 115909467b48SpatrickThen you can run your pass like this: 116009467b48Spatrick 116109467b48Spatrick.. code-block:: none 116209467b48Spatrick 116309467b48Spatrick $ opt < a.bc > /dev/null -mypass 116409467b48Spatrick <no output> 116509467b48Spatrick $ opt < a.bc > /dev/null -mypass -debug 116609467b48Spatrick I am here! 116709467b48Spatrick 116809467b48SpatrickUsing the ``LLVM_DEBUG()`` macro instead of a home-brewed solution allows you to not 116909467b48Spatrickhave to create "yet another" command line option for the debug output for your 117009467b48Spatrickpass. Note that ``LLVM_DEBUG()`` macros are disabled for non-asserts builds, so they 117109467b48Spatrickdo not cause a performance impact at all (for the same reason, they should also 117209467b48Spatricknot contain side-effects!). 117309467b48Spatrick 117409467b48SpatrickOne additional nice thing about the ``LLVM_DEBUG()`` macro is that you can enable or 117509467b48Spatrickdisable it directly in gdb. Just use "``set DebugFlag=0``" or "``set 117609467b48SpatrickDebugFlag=1``" from the gdb if the program is running. If the program hasn't 117709467b48Spatrickbeen started yet, you can always just run it with ``-debug``. 117809467b48Spatrick 117909467b48Spatrick.. _DEBUG_TYPE: 118009467b48Spatrick 118109467b48SpatrickFine grained debug info with ``DEBUG_TYPE`` and the ``-debug-only`` option 118209467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 118309467b48Spatrick 118409467b48SpatrickSometimes you may find yourself in a situation where enabling ``-debug`` just 118509467b48Spatrickturns on **too much** information (such as when working on the code generator). 118609467b48SpatrickIf you want to enable debug information with more fine-grained control, you 118709467b48Spatrickshould define the ``DEBUG_TYPE`` macro and use the ``-debug-only`` option as 118809467b48Spatrickfollows: 118909467b48Spatrick 119009467b48Spatrick.. code-block:: c++ 119109467b48Spatrick 119209467b48Spatrick #define DEBUG_TYPE "foo" 119309467b48Spatrick LLVM_DEBUG(dbgs() << "'foo' debug type\n"); 119409467b48Spatrick #undef DEBUG_TYPE 119509467b48Spatrick #define DEBUG_TYPE "bar" 119609467b48Spatrick LLVM_DEBUG(dbgs() << "'bar' debug type\n"); 119709467b48Spatrick #undef DEBUG_TYPE 119809467b48Spatrick 119909467b48SpatrickThen you can run your pass like this: 120009467b48Spatrick 120109467b48Spatrick.. code-block:: none 120209467b48Spatrick 120309467b48Spatrick $ opt < a.bc > /dev/null -mypass 120409467b48Spatrick <no output> 120509467b48Spatrick $ opt < a.bc > /dev/null -mypass -debug 120609467b48Spatrick 'foo' debug type 120709467b48Spatrick 'bar' debug type 120809467b48Spatrick $ opt < a.bc > /dev/null -mypass -debug-only=foo 120909467b48Spatrick 'foo' debug type 121009467b48Spatrick $ opt < a.bc > /dev/null -mypass -debug-only=bar 121109467b48Spatrick 'bar' debug type 121209467b48Spatrick $ opt < a.bc > /dev/null -mypass -debug-only=foo,bar 121309467b48Spatrick 'foo' debug type 121409467b48Spatrick 'bar' debug type 121509467b48Spatrick 121609467b48SpatrickOf course, in practice, you should only set ``DEBUG_TYPE`` at the top of a file, 121709467b48Spatrickto specify the debug type for the entire module. Be careful that you only do 121809467b48Spatrickthis after including Debug.h and not around any #include of headers. Also, you 121909467b48Spatrickshould use names more meaningful than "foo" and "bar", because there is no 122009467b48Spatricksystem in place to ensure that names do not conflict. If two different modules 122109467b48Spatrickuse the same string, they will all be turned on when the name is specified. 122209467b48SpatrickThis allows, for example, all debug information for instruction scheduling to be 122309467b48Spatrickenabled with ``-debug-only=InstrSched``, even if the source lives in multiple 122409467b48Spatrickfiles. The name must not include a comma (,) as that is used to separate the 122509467b48Spatrickarguments of the ``-debug-only`` option. 122609467b48Spatrick 122709467b48SpatrickFor performance reasons, -debug-only is not available in optimized build 122809467b48Spatrick(``--enable-optimized``) of LLVM. 122909467b48Spatrick 123009467b48SpatrickThe ``DEBUG_WITH_TYPE`` macro is also available for situations where you would 123109467b48Spatricklike to set ``DEBUG_TYPE``, but only for one specific ``DEBUG`` statement. It 123209467b48Spatricktakes an additional first parameter, which is the type to use. For example, the 123309467b48Spatrickpreceding example could be written as: 123409467b48Spatrick 123509467b48Spatrick.. code-block:: c++ 123609467b48Spatrick 123709467b48Spatrick DEBUG_WITH_TYPE("foo", dbgs() << "'foo' debug type\n"); 123809467b48Spatrick DEBUG_WITH_TYPE("bar", dbgs() << "'bar' debug type\n"); 123909467b48Spatrick 124009467b48Spatrick.. _Statistic: 124109467b48Spatrick 124209467b48SpatrickThe ``Statistic`` class & ``-stats`` option 124309467b48Spatrick------------------------------------------- 124409467b48Spatrick 124509467b48SpatrickThe ``llvm/ADT/Statistic.h`` (`doxygen 1246097a140dSpatrick<https://llvm.org/doxygen/Statistic_8h_source.html>`__) file provides a class 124709467b48Spatricknamed ``Statistic`` that is used as a unified way to keep track of what the LLVM 124809467b48Spatrickcompiler is doing and how effective various optimizations are. It is useful to 124909467b48Spatricksee what optimizations are contributing to making a particular program run 125009467b48Spatrickfaster. 125109467b48Spatrick 125209467b48SpatrickOften you may run your pass on some big program, and you're interested to see 125309467b48Spatrickhow many times it makes a certain transformation. Although you can do this with 125409467b48Spatrickhand inspection, or some ad-hoc method, this is a real pain and not very useful 125509467b48Spatrickfor big programs. Using the ``Statistic`` class makes it very easy to keep 125609467b48Spatricktrack of this information, and the calculated information is presented in a 125709467b48Spatrickuniform manner with the rest of the passes being executed. 125809467b48Spatrick 125909467b48SpatrickThere are many examples of ``Statistic`` uses, but the basics of using it are as 126009467b48Spatrickfollows: 126109467b48Spatrick 126209467b48SpatrickDefine your statistic like this: 126309467b48Spatrick 126409467b48Spatrick.. code-block:: c++ 126509467b48Spatrick 1266*d415bd75Srobert #define DEBUG_TYPE "mypassname" // This goes after any #includes. 126709467b48Spatrick STATISTIC(NumXForms, "The # of times I did stuff"); 126809467b48Spatrick 126909467b48SpatrickThe ``STATISTIC`` macro defines a static variable, whose name is specified by 127009467b48Spatrickthe first argument. The pass name is taken from the ``DEBUG_TYPE`` macro, and 127109467b48Spatrickthe description is taken from the second argument. The variable defined 127209467b48Spatrick("NumXForms" in this case) acts like an unsigned integer. 127309467b48Spatrick 127409467b48SpatrickWhenever you make a transformation, bump the counter: 127509467b48Spatrick 127609467b48Spatrick.. code-block:: c++ 127709467b48Spatrick 127809467b48Spatrick ++NumXForms; // I did stuff! 127909467b48Spatrick 128009467b48SpatrickThat's all you have to do. To get '``opt``' to print out the statistics 128109467b48Spatrickgathered, use the '``-stats``' option: 128209467b48Spatrick 128309467b48Spatrick.. code-block:: none 128409467b48Spatrick 128509467b48Spatrick $ opt -stats -mypassname < program.bc > /dev/null 128609467b48Spatrick ... statistics output ... 128709467b48Spatrick 128809467b48SpatrickNote that in order to use the '``-stats``' option, LLVM must be 128909467b48Spatrickcompiled with assertions enabled. 129009467b48Spatrick 129109467b48SpatrickWhen running ``opt`` on a C file from the SPEC benchmark suite, it gives a 129209467b48Spatrickreport that looks like this: 129309467b48Spatrick 129409467b48Spatrick.. code-block:: none 129509467b48Spatrick 129609467b48Spatrick 7646 bitcodewriter - Number of normal instructions 129709467b48Spatrick 725 bitcodewriter - Number of oversized instructions 129809467b48Spatrick 129996 bitcodewriter - Number of bitcode bytes written 129909467b48Spatrick 2817 raise - Number of insts DCEd or constprop'd 130009467b48Spatrick 3213 raise - Number of cast-of-self removed 130109467b48Spatrick 5046 raise - Number of expression trees converted 130209467b48Spatrick 75 raise - Number of other getelementptr's formed 130309467b48Spatrick 138 raise - Number of load/store peepholes 130409467b48Spatrick 42 deadtypeelim - Number of unused typenames removed from symtab 130509467b48Spatrick 392 funcresolve - Number of varargs functions resolved 130609467b48Spatrick 27 globaldce - Number of global variables removed 130709467b48Spatrick 2 adce - Number of basic blocks removed 130809467b48Spatrick 134 cee - Number of branches revectored 130909467b48Spatrick 49 cee - Number of setcc instruction eliminated 131009467b48Spatrick 532 gcse - Number of loads removed 131109467b48Spatrick 2919 gcse - Number of instructions removed 131209467b48Spatrick 86 indvars - Number of canonical indvars added 131309467b48Spatrick 87 indvars - Number of aux indvars removed 131409467b48Spatrick 25 instcombine - Number of dead inst eliminate 131509467b48Spatrick 434 instcombine - Number of insts combined 131609467b48Spatrick 248 licm - Number of load insts hoisted 131709467b48Spatrick 1298 licm - Number of insts hoisted to a loop pre-header 131809467b48Spatrick 3 licm - Number of insts hoisted to multiple loop preds (bad, no loop pre-header) 131909467b48Spatrick 75 mem2reg - Number of alloca's promoted 132009467b48Spatrick 1444 cfgsimplify - Number of blocks simplified 132109467b48Spatrick 132209467b48SpatrickObviously, with so many optimizations, having a unified framework for this stuff 132309467b48Spatrickis very nice. Making your pass fit well into the framework makes it more 132409467b48Spatrickmaintainable and useful. 132509467b48Spatrick 132609467b48Spatrick.. _DebugCounters: 132709467b48Spatrick 132809467b48SpatrickAdding debug counters to aid in debugging your code 132909467b48Spatrick--------------------------------------------------- 133009467b48Spatrick 133109467b48SpatrickSometimes, when writing new passes, or trying to track down bugs, it 133209467b48Spatrickis useful to be able to control whether certain things in your pass 133309467b48Spatrickhappen or not. For example, there are times the minimization tooling 133409467b48Spatrickcan only easily give you large testcases. You would like to narrow 133509467b48Spatrickyour bug down to a specific transformation happening or not happening, 133609467b48Spatrickautomatically, using bisection. This is where debug counters help. 133709467b48SpatrickThey provide a framework for making parts of your code only execute a 133809467b48Spatrickcertain number of times. 133909467b48Spatrick 134009467b48SpatrickThe ``llvm/Support/DebugCounter.h`` (`doxygen 1341097a140dSpatrick<https://llvm.org/doxygen/DebugCounter_8h_source.html>`__) file 134209467b48Spatrickprovides a class named ``DebugCounter`` that can be used to create 134309467b48Spatrickcommand line counter options that control execution of parts of your code. 134409467b48Spatrick 134509467b48SpatrickDefine your DebugCounter like this: 134609467b48Spatrick 134709467b48Spatrick.. code-block:: c++ 134809467b48Spatrick 134909467b48Spatrick DEBUG_COUNTER(DeleteAnInstruction, "passname-delete-instruction", 135009467b48Spatrick "Controls which instructions get delete"); 135109467b48Spatrick 135209467b48SpatrickThe ``DEBUG_COUNTER`` macro defines a static variable, whose name 135309467b48Spatrickis specified by the first argument. The name of the counter 135409467b48Spatrick(which is used on the command line) is specified by the second 135509467b48Spatrickargument, and the description used in the help is specified by the 135609467b48Spatrickthird argument. 135709467b48Spatrick 135809467b48SpatrickWhatever code you want that control, use ``DebugCounter::shouldExecute`` to control it. 135909467b48Spatrick 136009467b48Spatrick.. code-block:: c++ 136109467b48Spatrick 136209467b48Spatrick if (DebugCounter::shouldExecute(DeleteAnInstruction)) 136309467b48Spatrick I->eraseFromParent(); 136409467b48Spatrick 136509467b48SpatrickThat's all you have to do. Now, using opt, you can control when this code triggers using 136609467b48Spatrickthe '``--debug-counter``' option. There are two counters provided, ``skip`` and ``count``. 136709467b48Spatrick``skip`` is the number of times to skip execution of the codepath. ``count`` is the number 136809467b48Spatrickof times, once we are done skipping, to execute the codepath. 136909467b48Spatrick 137009467b48Spatrick.. code-block:: none 137109467b48Spatrick 137209467b48Spatrick $ opt --debug-counter=passname-delete-instruction-skip=1,passname-delete-instruction-count=2 -passname 137309467b48Spatrick 137409467b48SpatrickThis will skip the above code the first time we hit it, then execute it twice, then skip the rest of the executions. 137509467b48Spatrick 137609467b48SpatrickSo if executed on the following code: 137709467b48Spatrick 137809467b48Spatrick.. code-block:: llvm 137909467b48Spatrick 138009467b48Spatrick %1 = add i32 %a, %b 138109467b48Spatrick %2 = add i32 %a, %b 138209467b48Spatrick %3 = add i32 %a, %b 138309467b48Spatrick %4 = add i32 %a, %b 138409467b48Spatrick 138509467b48SpatrickIt would delete number ``%2`` and ``%3``. 138609467b48Spatrick 138709467b48SpatrickA utility is provided in `utils/bisect-skip-count` to binary search 138809467b48Spatrickskip and count arguments. It can be used to automatically minimize the 138909467b48Spatrickskip and count for a debug-counter variable. 139009467b48Spatrick 139109467b48Spatrick.. _ViewGraph: 139209467b48Spatrick 139309467b48SpatrickViewing graphs while debugging code 139409467b48Spatrick----------------------------------- 139509467b48Spatrick 139609467b48SpatrickSeveral of the important data structures in LLVM are graphs: for example CFGs 139709467b48Spatrickmade out of LLVM :ref:`BasicBlocks <BasicBlock>`, CFGs made out of LLVM 139809467b48Spatrick:ref:`MachineBasicBlocks <MachineBasicBlock>`, and :ref:`Instruction Selection 139909467b48SpatrickDAGs <SelectionDAG>`. In many cases, while debugging various parts of the 140009467b48Spatrickcompiler, it is nice to instantly visualize these graphs. 140109467b48Spatrick 140209467b48SpatrickLLVM provides several callbacks that are available in a debug build to do 140309467b48Spatrickexactly that. If you call the ``Function::viewCFG()`` method, for example, the 140409467b48Spatrickcurrent LLVM tool will pop up a window containing the CFG for the function where 140509467b48Spatrickeach basic block is a node in the graph, and each node contains the instructions 140609467b48Spatrickin the block. Similarly, there also exists ``Function::viewCFGOnly()`` (does 140709467b48Spatricknot include the instructions), the ``MachineFunction::viewCFG()`` and 140809467b48Spatrick``MachineFunction::viewCFGOnly()``, and the ``SelectionDAG::viewGraph()`` 140909467b48Spatrickmethods. Within GDB, for example, you can usually use something like ``call 141009467b48SpatrickDAG.viewGraph()`` to pop up a window. Alternatively, you can sprinkle calls to 141109467b48Spatrickthese functions in your code in places you want to debug. 141209467b48Spatrick 141309467b48SpatrickGetting this to work requires a small amount of setup. On Unix systems 141409467b48Spatrickwith X11, install the `graphviz <http://www.graphviz.org>`_ toolkit, and make 141509467b48Spatricksure 'dot' and 'gv' are in your path. If you are running on macOS, download 141609467b48Spatrickand install the macOS `Graphviz program 141709467b48Spatrick<http://www.pixelglow.com/graphviz/>`_ and add 141809467b48Spatrick``/Applications/Graphviz.app/Contents/MacOS/`` (or wherever you install it) to 141909467b48Spatrickyour path. The programs need not be present when configuring, building or 142009467b48Spatrickrunning LLVM and can simply be installed when needed during an active debug 142109467b48Spatricksession. 142209467b48Spatrick 142309467b48Spatrick``SelectionDAG`` has been extended to make it easier to locate *interesting* 142409467b48Spatricknodes in large complex graphs. From gdb, if you ``call DAG.setGraphColor(node, 142509467b48Spatrick"color")``, then the next ``call DAG.viewGraph()`` would highlight the node in 142609467b48Spatrickthe specified color (choices of colors can be found at `colors 142709467b48Spatrick<http://www.graphviz.org/doc/info/colors.html>`_.) More complex node attributes 142809467b48Spatrickcan be provided with ``call DAG.setGraphAttrs(node, "attributes")`` (choices can 142909467b48Spatrickbe found at `Graph attributes <http://www.graphviz.org/doc/info/attrs.html>`_.) 143009467b48SpatrickIf you want to restart and clear all the current graph attributes, then you can 143109467b48Spatrick``call DAG.clearGraphAttrs()``. 143209467b48Spatrick 143309467b48SpatrickNote that graph visualization features are compiled out of Release builds to 143409467b48Spatrickreduce file size. This means that you need a Debug+Asserts or Release+Asserts 143509467b48Spatrickbuild to use these features. 143609467b48Spatrick 143709467b48Spatrick.. _datastructure: 143809467b48Spatrick 143909467b48SpatrickPicking the Right Data Structure for a Task 144009467b48Spatrick=========================================== 144109467b48Spatrick 144209467b48SpatrickLLVM has a plethora of data structures in the ``llvm/ADT/`` directory, and we 144309467b48Spatrickcommonly use STL data structures. This section describes the trade-offs you 144409467b48Spatrickshould consider when you pick one. 144509467b48Spatrick 144609467b48SpatrickThe first step is a choose your own adventure: do you want a sequential 144709467b48Spatrickcontainer, a set-like container, or a map-like container? The most important 144809467b48Spatrickthing when choosing a container is the algorithmic properties of how you plan to 144909467b48Spatrickaccess the container. Based on that, you should use: 145009467b48Spatrick 145109467b48Spatrick 145209467b48Spatrick* a :ref:`map-like <ds_map>` container if you need efficient look-up of a 145309467b48Spatrick value based on another value. Map-like containers also support efficient 145409467b48Spatrick queries for containment (whether a key is in the map). Map-like containers 145509467b48Spatrick generally do not support efficient reverse mapping (values to keys). If you 145609467b48Spatrick need that, use two maps. Some map-like containers also support efficient 145709467b48Spatrick iteration through the keys in sorted order. Map-like containers are the most 145809467b48Spatrick expensive sort, only use them if you need one of these capabilities. 145909467b48Spatrick 146009467b48Spatrick* a :ref:`set-like <ds_set>` container if you need to put a bunch of stuff into 146109467b48Spatrick a container that automatically eliminates duplicates. Some set-like 146209467b48Spatrick containers support efficient iteration through the elements in sorted order. 146309467b48Spatrick Set-like containers are more expensive than sequential containers. 146409467b48Spatrick 146509467b48Spatrick* a :ref:`sequential <ds_sequential>` container provides the most efficient way 146609467b48Spatrick to add elements and keeps track of the order they are added to the collection. 146709467b48Spatrick They permit duplicates and support efficient iteration, but do not support 146809467b48Spatrick efficient look-up based on a key. 146909467b48Spatrick 147009467b48Spatrick* a :ref:`string <ds_string>` container is a specialized sequential container or 147109467b48Spatrick reference structure that is used for character or byte arrays. 147209467b48Spatrick 147309467b48Spatrick* a :ref:`bit <ds_bit>` container provides an efficient way to store and 147409467b48Spatrick perform set operations on sets of numeric id's, while automatically 147509467b48Spatrick eliminating duplicates. Bit containers require a maximum of 1 bit for each 147609467b48Spatrick identifier you want to store. 147709467b48Spatrick 147809467b48SpatrickOnce the proper category of container is determined, you can fine tune the 147909467b48Spatrickmemory use, constant factors, and cache behaviors of access by intelligently 148009467b48Spatrickpicking a member of the category. Note that constant factors and cache behavior 148109467b48Spatrickcan be a big deal. If you have a vector that usually only contains a few 148209467b48Spatrickelements (but could contain many), for example, it's much better to use 148309467b48Spatrick:ref:`SmallVector <dss_smallvector>` than :ref:`vector <dss_vector>`. Doing so 148409467b48Spatrickavoids (relatively) expensive malloc/free calls, which dwarf the cost of adding 148509467b48Spatrickthe elements to the container. 148609467b48Spatrick 148709467b48Spatrick.. _ds_sequential: 148809467b48Spatrick 148909467b48SpatrickSequential Containers (std::vector, std::list, etc) 149009467b48Spatrick--------------------------------------------------- 149109467b48Spatrick 149209467b48SpatrickThere are a variety of sequential containers available for you, based on your 149309467b48Spatrickneeds. Pick the first in this section that will do what you want. 149409467b48Spatrick 149509467b48Spatrick.. _dss_arrayref: 149609467b48Spatrick 149709467b48Spatrickllvm/ADT/ArrayRef.h 149809467b48Spatrick^^^^^^^^^^^^^^^^^^^ 149909467b48Spatrick 150009467b48SpatrickThe ``llvm::ArrayRef`` class is the preferred class to use in an interface that 150109467b48Spatrickaccepts a sequential list of elements in memory and just reads from them. By 150209467b48Spatricktaking an ``ArrayRef``, the API can be passed a fixed size array, an 150309467b48Spatrick``std::vector``, an ``llvm::SmallVector`` and anything else that is contiguous 150409467b48Spatrickin memory. 150509467b48Spatrick 150609467b48Spatrick.. _dss_fixedarrays: 150709467b48Spatrick 150809467b48SpatrickFixed Size Arrays 150909467b48Spatrick^^^^^^^^^^^^^^^^^ 151009467b48Spatrick 151109467b48SpatrickFixed size arrays are very simple and very fast. They are good if you know 151209467b48Spatrickexactly how many elements you have, or you have a (low) upper bound on how many 151309467b48Spatrickyou have. 151409467b48Spatrick 151509467b48Spatrick.. _dss_heaparrays: 151609467b48Spatrick 151709467b48SpatrickHeap Allocated Arrays 151809467b48Spatrick^^^^^^^^^^^^^^^^^^^^^ 151909467b48Spatrick 152009467b48SpatrickHeap allocated arrays (``new[]`` + ``delete[]``) are also simple. They are good 152109467b48Spatrickif the number of elements is variable, if you know how many elements you will 152209467b48Spatrickneed before the array is allocated, and if the array is usually large (if not, 152309467b48Spatrickconsider a :ref:`SmallVector <dss_smallvector>`). The cost of a heap allocated 152409467b48Spatrickarray is the cost of the new/delete (aka malloc/free). Also note that if you 152509467b48Spatrickare allocating an array of a type with a constructor, the constructor and 152609467b48Spatrickdestructors will be run for every element in the array (re-sizable vectors only 152709467b48Spatrickconstruct those elements actually used). 152809467b48Spatrick 152909467b48Spatrick.. _dss_tinyptrvector: 153009467b48Spatrick 153109467b48Spatrickllvm/ADT/TinyPtrVector.h 153209467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^ 153309467b48Spatrick 153409467b48Spatrick``TinyPtrVector<Type>`` is a highly specialized collection class that is 153509467b48Spatrickoptimized to avoid allocation in the case when a vector has zero or one 153609467b48Spatrickelements. It has two major restrictions: 1) it can only hold values of pointer 153709467b48Spatricktype, and 2) it cannot hold a null pointer. 153809467b48Spatrick 153909467b48SpatrickSince this container is highly specialized, it is rarely used. 154009467b48Spatrick 154109467b48Spatrick.. _dss_smallvector: 154209467b48Spatrick 154309467b48Spatrickllvm/ADT/SmallVector.h 154409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^ 154509467b48Spatrick 154609467b48Spatrick``SmallVector<Type, N>`` is a simple class that looks and smells just like 154709467b48Spatrick``vector<Type>``: it supports efficient iteration, lays out elements in memory 154809467b48Spatrickorder (so you can do pointer arithmetic between elements), supports efficient 154909467b48Spatrickpush_back/pop_back operations, supports efficient random access to its elements, 155009467b48Spatricketc. 155109467b48Spatrick 155209467b48SpatrickThe main advantage of SmallVector is that it allocates space for some number of 155309467b48Spatrickelements (N) **in the object itself**. Because of this, if the SmallVector is 155409467b48Spatrickdynamically smaller than N, no malloc is performed. This can be a big win in 155509467b48Spatrickcases where the malloc/free call is far more expensive than the code that 155609467b48Spatrickfiddles around with the elements. 155709467b48Spatrick 155809467b48SpatrickThis is good for vectors that are "usually small" (e.g. the number of 155909467b48Spatrickpredecessors/successors of a block is usually less than 8). On the other hand, 156009467b48Spatrickthis makes the size of the SmallVector itself large, so you don't want to 156109467b48Spatrickallocate lots of them (doing so will waste a lot of space). As such, 156209467b48SpatrickSmallVectors are most useful when on the stack. 156309467b48Spatrick 156473471bf0SpatrickIn the absence of a well-motivated choice for the number of 156573471bf0Spatrickinlined elements ``N``, it is recommended to use ``SmallVector<T>`` (that is, 156673471bf0Spatrickomitting the ``N``). This will choose a default number of 156773471bf0Spatrickinlined elements reasonable for allocation on the stack (for example, trying 156873471bf0Spatrickto keep ``sizeof(SmallVector<T>)`` around 64 bytes). 156973471bf0Spatrick 157009467b48SpatrickSmallVector also provides a nice portable and efficient replacement for 157109467b48Spatrick``alloca``. 157209467b48Spatrick 157309467b48SpatrickSmallVector has grown a few other minor advantages over std::vector, causing 157409467b48Spatrick``SmallVector<Type, 0>`` to be preferred over ``std::vector<Type>``. 157509467b48Spatrick 157609467b48Spatrick#. std::vector is exception-safe, and some implementations have pessimizations 157709467b48Spatrick that copy elements when SmallVector would move them. 157809467b48Spatrick 157973471bf0Spatrick#. SmallVector understands ``std::is_trivially_copyable<Type>`` and uses realloc aggressively. 158009467b48Spatrick 158109467b48Spatrick#. Many LLVM APIs take a SmallVectorImpl as an out parameter (see the note 158209467b48Spatrick below). 158309467b48Spatrick 158409467b48Spatrick#. SmallVector with N equal to 0 is smaller than std::vector on 64-bit 158509467b48Spatrick platforms, since it uses ``unsigned`` (instead of ``void*``) for its size 158609467b48Spatrick and capacity. 158709467b48Spatrick 158809467b48Spatrick.. note:: 158909467b48Spatrick 159073471bf0Spatrick Prefer to use ``ArrayRef<T>`` or ``SmallVectorImpl<T>`` as a parameter type. 159109467b48Spatrick 159273471bf0Spatrick It's rarely appropriate to use ``SmallVector<T, N>`` as a parameter type. 159373471bf0Spatrick If an API only reads from the vector, it should use :ref:`ArrayRef 159473471bf0Spatrick <dss_arrayref>`. Even if an API updates the vector the "small size" is 159573471bf0Spatrick unlikely to be relevant; such an API should use the ``SmallVectorImpl<T>`` 159673471bf0Spatrick class, which is the "vector header" (and methods) without the elements 159773471bf0Spatrick allocated after it. Note that ``SmallVector<T, N>`` inherits from 159873471bf0Spatrick ``SmallVectorImpl<T>`` so the conversion is implicit and costs nothing. E.g. 159909467b48Spatrick 160009467b48Spatrick .. code-block:: c++ 160109467b48Spatrick 160273471bf0Spatrick // DISCOURAGED: Clients cannot pass e.g. raw arrays. 160373471bf0Spatrick hardcodedContiguousStorage(const SmallVectorImpl<Foo> &In); 160473471bf0Spatrick // ENCOURAGED: Clients can pass any contiguous storage of Foo. 160573471bf0Spatrick allowsAnyContiguousStorage(ArrayRef<Foo> In); 160673471bf0Spatrick 160773471bf0Spatrick void someFunc1() { 160873471bf0Spatrick Foo Vec[] = { /* ... */ }; 160973471bf0Spatrick hardcodedContiguousStorage(Vec); // Error. 161073471bf0Spatrick allowsAnyContiguousStorage(Vec); // Works. 161173471bf0Spatrick } 161273471bf0Spatrick 161373471bf0Spatrick // DISCOURAGED: Clients cannot pass e.g. SmallVector<Foo, 8>. 161409467b48Spatrick hardcodedSmallSize(SmallVector<Foo, 2> &Out); 161573471bf0Spatrick // ENCOURAGED: Clients can pass any SmallVector<Foo, N>. 161609467b48Spatrick allowsAnySmallSize(SmallVectorImpl<Foo> &Out); 161709467b48Spatrick 161873471bf0Spatrick void someFunc2() { 161909467b48Spatrick SmallVector<Foo, 8> Vec; 162009467b48Spatrick hardcodedSmallSize(Vec); // Error. 162109467b48Spatrick allowsAnySmallSize(Vec); // Works. 162209467b48Spatrick } 162309467b48Spatrick 162473471bf0Spatrick Even though it has "``Impl``" in the name, SmallVectorImpl is widely used 162573471bf0Spatrick and is no longer "private to the implementation". A name like 162673471bf0Spatrick ``SmallVectorHeader`` might be more appropriate. 162709467b48Spatrick 162809467b48Spatrick.. _dss_vector: 162909467b48Spatrick 163009467b48Spatrick<vector> 163109467b48Spatrick^^^^^^^^ 163209467b48Spatrick 163309467b48Spatrick``std::vector<T>`` is well loved and respected. However, ``SmallVector<T, 0>`` 163409467b48Spatrickis often a better option due to the advantages listed above. std::vector is 163509467b48Spatrickstill useful when you need to store more than ``UINT32_MAX`` elements or when 163609467b48Spatrickinterfacing with code that expects vectors :). 163709467b48Spatrick 163809467b48SpatrickOne worthwhile note about std::vector: avoid code like this: 163909467b48Spatrick 164009467b48Spatrick.. code-block:: c++ 164109467b48Spatrick 164209467b48Spatrick for ( ... ) { 164309467b48Spatrick std::vector<foo> V; 164409467b48Spatrick // make use of V. 164509467b48Spatrick } 164609467b48Spatrick 164709467b48SpatrickInstead, write this as: 164809467b48Spatrick 164909467b48Spatrick.. code-block:: c++ 165009467b48Spatrick 165109467b48Spatrick std::vector<foo> V; 165209467b48Spatrick for ( ... ) { 165309467b48Spatrick // make use of V. 165409467b48Spatrick V.clear(); 165509467b48Spatrick } 165609467b48Spatrick 165709467b48SpatrickDoing so will save (at least) one heap allocation and free per iteration of the 165809467b48Spatrickloop. 165909467b48Spatrick 166009467b48Spatrick.. _dss_deque: 166109467b48Spatrick 166209467b48Spatrick<deque> 166309467b48Spatrick^^^^^^^ 166409467b48Spatrick 166509467b48Spatrick``std::deque`` is, in some senses, a generalized version of ``std::vector``. 166609467b48SpatrickLike ``std::vector``, it provides constant time random access and other similar 166709467b48Spatrickproperties, but it also provides efficient access to the front of the list. It 166809467b48Spatrickdoes not guarantee continuity of elements within memory. 166909467b48Spatrick 167009467b48SpatrickIn exchange for this extra flexibility, ``std::deque`` has significantly higher 167109467b48Spatrickconstant factor costs than ``std::vector``. If possible, use ``std::vector`` or 167209467b48Spatricksomething cheaper. 167309467b48Spatrick 167409467b48Spatrick.. _dss_list: 167509467b48Spatrick 167609467b48Spatrick<list> 167709467b48Spatrick^^^^^^ 167809467b48Spatrick 167909467b48Spatrick``std::list`` is an extremely inefficient class that is rarely useful. It 168009467b48Spatrickperforms a heap allocation for every element inserted into it, thus having an 168109467b48Spatrickextremely high constant factor, particularly for small data types. 168209467b48Spatrick``std::list`` also only supports bidirectional iteration, not random access 168309467b48Spatrickiteration. 168409467b48Spatrick 168509467b48SpatrickIn exchange for this high cost, std::list supports efficient access to both ends 168609467b48Spatrickof the list (like ``std::deque``, but unlike ``std::vector`` or 168709467b48Spatrick``SmallVector``). In addition, the iterator invalidation characteristics of 168809467b48Spatrickstd::list are stronger than that of a vector class: inserting or removing an 168909467b48Spatrickelement into the list does not invalidate iterator or pointers to other elements 169009467b48Spatrickin the list. 169109467b48Spatrick 169209467b48Spatrick.. _dss_ilist: 169309467b48Spatrick 169409467b48Spatrickllvm/ADT/ilist.h 169509467b48Spatrick^^^^^^^^^^^^^^^^ 169609467b48Spatrick 169709467b48Spatrick``ilist<T>`` implements an 'intrusive' doubly-linked list. It is intrusive, 169809467b48Spatrickbecause it requires the element to store and provide access to the prev/next 169909467b48Spatrickpointers for the list. 170009467b48Spatrick 170109467b48Spatrick``ilist`` has the same drawbacks as ``std::list``, and additionally requires an 170209467b48Spatrick``ilist_traits`` implementation for the element type, but it provides some novel 170309467b48Spatrickcharacteristics. In particular, it can efficiently store polymorphic objects, 170409467b48Spatrickthe traits class is informed when an element is inserted or removed from the 170509467b48Spatricklist, and ``ilist``\ s are guaranteed to support a constant-time splice 170609467b48Spatrickoperation. 170709467b48Spatrick 1708*d415bd75SrobertAn ``ilist`` and an ``iplist`` are ``using`` aliases to one another and the 1709*d415bd75Srobertlatter only currently exists for historical purposes. 1710*d415bd75Srobert 171109467b48SpatrickThese properties are exactly what we want for things like ``Instruction``\ s and 171209467b48Spatrickbasic blocks, which is why these are implemented with ``ilist``\ s. 171309467b48Spatrick 171409467b48SpatrickRelated classes of interest are explained in the following subsections: 171509467b48Spatrick 171609467b48Spatrick* :ref:`ilist_traits <dss_ilist_traits>` 171709467b48Spatrick 171809467b48Spatrick* :ref:`llvm/ADT/ilist_node.h <dss_ilist_node>` 171909467b48Spatrick 172009467b48Spatrick* :ref:`Sentinels <dss_ilist_sentinel>` 172109467b48Spatrick 172209467b48Spatrick.. _dss_packedvector: 172309467b48Spatrick 172409467b48Spatrickllvm/ADT/PackedVector.h 172509467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 172609467b48Spatrick 172709467b48SpatrickUseful for storing a vector of values using only a few number of bits for each 172809467b48Spatrickvalue. Apart from the standard operations of a vector-like container, it can 172909467b48Spatrickalso perform an 'or' set operation. 173009467b48Spatrick 173109467b48SpatrickFor example: 173209467b48Spatrick 173309467b48Spatrick.. code-block:: c++ 173409467b48Spatrick 173509467b48Spatrick enum State { 173609467b48Spatrick None = 0x0, 173709467b48Spatrick FirstCondition = 0x1, 173809467b48Spatrick SecondCondition = 0x2, 173909467b48Spatrick Both = 0x3 174009467b48Spatrick }; 174109467b48Spatrick 174209467b48Spatrick State get() { 174309467b48Spatrick PackedVector<State, 2> Vec1; 174409467b48Spatrick Vec1.push_back(FirstCondition); 174509467b48Spatrick 174609467b48Spatrick PackedVector<State, 2> Vec2; 174709467b48Spatrick Vec2.push_back(SecondCondition); 174809467b48Spatrick 174909467b48Spatrick Vec1 |= Vec2; 175009467b48Spatrick return Vec1[0]; // returns 'Both'. 175109467b48Spatrick } 175209467b48Spatrick 175309467b48Spatrick.. _dss_ilist_traits: 175409467b48Spatrick 175509467b48Spatrickilist_traits 175609467b48Spatrick^^^^^^^^^^^^ 175709467b48Spatrick 1758*d415bd75Srobert``ilist_traits<T>`` is ``ilist<T>``'s customization mechanism. ``ilist<T>`` 1759*d415bd75Srobertpublicly derives from this traits class. 176009467b48Spatrick 176109467b48Spatrick.. _dss_ilist_node: 176209467b48Spatrick 176309467b48Spatrickllvm/ADT/ilist_node.h 176409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^ 176509467b48Spatrick 176609467b48Spatrick``ilist_node<T>`` implements the forward and backward links that are expected 176709467b48Spatrickby the ``ilist<T>`` (and analogous containers) in the default manner. 176809467b48Spatrick 176909467b48Spatrick``ilist_node<T>``\ s are meant to be embedded in the node type ``T``, usually 177009467b48Spatrick``T`` publicly derives from ``ilist_node<T>``. 177109467b48Spatrick 177209467b48Spatrick.. _dss_ilist_sentinel: 177309467b48Spatrick 177409467b48SpatrickSentinels 177509467b48Spatrick^^^^^^^^^ 177609467b48Spatrick 177709467b48Spatrick``ilist``\ s have another specialty that must be considered. To be a good 177809467b48Spatrickcitizen in the C++ ecosystem, it needs to support the standard container 177909467b48Spatrickoperations, such as ``begin`` and ``end`` iterators, etc. Also, the 178009467b48Spatrick``operator--`` must work correctly on the ``end`` iterator in the case of 178109467b48Spatricknon-empty ``ilist``\ s. 178209467b48Spatrick 178309467b48SpatrickThe only sensible solution to this problem is to allocate a so-called *sentinel* 178409467b48Spatrickalong with the intrusive list, which serves as the ``end`` iterator, providing 178509467b48Spatrickthe back-link to the last element. However conforming to the C++ convention it 178609467b48Spatrickis illegal to ``operator++`` beyond the sentinel and it also must not be 178709467b48Spatrickdereferenced. 178809467b48Spatrick 178909467b48SpatrickThese constraints allow for some implementation freedom to the ``ilist`` how to 179009467b48Spatrickallocate and store the sentinel. The corresponding policy is dictated by 179109467b48Spatrick``ilist_traits<T>``. By default a ``T`` gets heap-allocated whenever the need 179209467b48Spatrickfor a sentinel arises. 179309467b48Spatrick 179409467b48SpatrickWhile the default policy is sufficient in most cases, it may break down when 179509467b48Spatrick``T`` does not provide a default constructor. Also, in the case of many 179609467b48Spatrickinstances of ``ilist``\ s, the memory overhead of the associated sentinels is 179709467b48Spatrickwasted. To alleviate the situation with numerous and voluminous 179809467b48Spatrick``T``-sentinels, sometimes a trick is employed, leading to *ghostly sentinels*. 179909467b48Spatrick 180009467b48SpatrickGhostly sentinels are obtained by specially-crafted ``ilist_traits<T>`` which 180109467b48Spatricksuperpose the sentinel with the ``ilist`` instance in memory. Pointer 180209467b48Spatrickarithmetic is used to obtain the sentinel, which is relative to the ``ilist``'s 180309467b48Spatrick``this`` pointer. The ``ilist`` is augmented by an extra pointer, which serves 180409467b48Spatrickas the back-link of the sentinel. This is the only field in the ghostly 180509467b48Spatricksentinel which can be legally accessed. 180609467b48Spatrick 180709467b48Spatrick.. _dss_other: 180809467b48Spatrick 180909467b48SpatrickOther Sequential Container options 181009467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 181109467b48Spatrick 181209467b48SpatrickOther STL containers are available, such as ``std::string``. 181309467b48Spatrick 181409467b48SpatrickThere are also various STL adapter classes such as ``std::queue``, 181509467b48Spatrick``std::priority_queue``, ``std::stack``, etc. These provide simplified access 181609467b48Spatrickto an underlying container but don't affect the cost of the container itself. 181709467b48Spatrick 181809467b48Spatrick.. _ds_string: 181909467b48Spatrick 182009467b48SpatrickString-like containers 182109467b48Spatrick---------------------- 182209467b48Spatrick 182309467b48SpatrickThere are a variety of ways to pass around and use strings in C and C++, and 182409467b48SpatrickLLVM adds a few new options to choose from. Pick the first option on this list 182509467b48Spatrickthat will do what you need, they are ordered according to their relative cost. 182609467b48Spatrick 182709467b48SpatrickNote that it is generally preferred to *not* pass strings around as ``const 182809467b48Spatrickchar*``'s. These have a number of problems, including the fact that they 182909467b48Spatrickcannot represent embedded nul ("\0") characters, and do not have a length 183009467b48Spatrickavailable efficiently. The general replacement for '``const char*``' is 183109467b48SpatrickStringRef. 183209467b48Spatrick 183309467b48SpatrickFor more information on choosing string containers for APIs, please see 183409467b48Spatrick:ref:`Passing Strings <string_apis>`. 183509467b48Spatrick 183609467b48Spatrick.. _dss_stringref: 183709467b48Spatrick 183809467b48Spatrickllvm/ADT/StringRef.h 183909467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 184009467b48Spatrick 184109467b48SpatrickThe StringRef class is a simple value class that contains a pointer to a 184209467b48Spatrickcharacter and a length, and is quite related to the :ref:`ArrayRef 184309467b48Spatrick<dss_arrayref>` class (but specialized for arrays of characters). Because 184409467b48SpatrickStringRef carries a length with it, it safely handles strings with embedded nul 184509467b48Spatrickcharacters in it, getting the length does not require a strlen call, and it even 184609467b48Spatrickhas very convenient APIs for slicing and dicing the character range that it 184709467b48Spatrickrepresents. 184809467b48Spatrick 184909467b48SpatrickStringRef is ideal for passing simple strings around that are known to be live, 185009467b48Spatrickeither because they are C string literals, std::string, a C array, or a 185109467b48SpatrickSmallVector. Each of these cases has an efficient implicit conversion to 185209467b48SpatrickStringRef, which doesn't result in a dynamic strlen being executed. 185309467b48Spatrick 185409467b48SpatrickStringRef has a few major limitations which make more powerful string containers 185509467b48Spatrickuseful: 185609467b48Spatrick 185709467b48Spatrick#. You cannot directly convert a StringRef to a 'const char*' because there is 185809467b48Spatrick no way to add a trailing nul (unlike the .c_str() method on various stronger 185909467b48Spatrick classes). 186009467b48Spatrick 186109467b48Spatrick#. StringRef doesn't own or keep alive the underlying string bytes. 186209467b48Spatrick As such it can easily lead to dangling pointers, and is not suitable for 186309467b48Spatrick embedding in datastructures in most cases (instead, use an std::string or 186409467b48Spatrick something like that). 186509467b48Spatrick 186609467b48Spatrick#. For the same reason, StringRef cannot be used as the return value of a 186709467b48Spatrick method if the method "computes" the result string. Instead, use std::string. 186809467b48Spatrick 186909467b48Spatrick#. StringRef's do not allow you to mutate the pointed-to string bytes and it 187009467b48Spatrick doesn't allow you to insert or remove bytes from the range. For editing 187109467b48Spatrick operations like this, it interoperates with the :ref:`Twine <dss_twine>` 187209467b48Spatrick class. 187309467b48Spatrick 187409467b48SpatrickBecause of its strengths and limitations, it is very common for a function to 187509467b48Spatricktake a StringRef and for a method on an object to return a StringRef that points 187609467b48Spatrickinto some string that it owns. 187709467b48Spatrick 187809467b48Spatrick.. _dss_twine: 187909467b48Spatrick 188009467b48Spatrickllvm/ADT/Twine.h 188109467b48Spatrick^^^^^^^^^^^^^^^^ 188209467b48Spatrick 188309467b48SpatrickThe Twine class is used as an intermediary datatype for APIs that want to take a 188409467b48Spatrickstring that can be constructed inline with a series of concatenations. Twine 188509467b48Spatrickworks by forming recursive instances of the Twine datatype (a simple value 188609467b48Spatrickobject) on the stack as temporary objects, linking them together into a tree 188709467b48Spatrickwhich is then linearized when the Twine is consumed. Twine is only safe to use 188809467b48Spatrickas the argument to a function, and should always be a const reference, e.g.: 188909467b48Spatrick 189009467b48Spatrick.. code-block:: c++ 189109467b48Spatrick 189209467b48Spatrick void foo(const Twine &T); 189309467b48Spatrick ... 189409467b48Spatrick StringRef X = ... 189509467b48Spatrick unsigned i = ... 189609467b48Spatrick foo(X + "." + Twine(i)); 189709467b48Spatrick 189809467b48SpatrickThis example forms a string like "blarg.42" by concatenating the values 189909467b48Spatricktogether, and does not form intermediate strings containing "blarg" or "blarg.". 190009467b48Spatrick 190109467b48SpatrickBecause Twine is constructed with temporary objects on the stack, and because 190209467b48Spatrickthese instances are destroyed at the end of the current statement, it is an 190309467b48Spatrickinherently dangerous API. For example, this simple variant contains undefined 190409467b48Spatrickbehavior and will probably crash: 190509467b48Spatrick 190609467b48Spatrick.. code-block:: c++ 190709467b48Spatrick 190809467b48Spatrick void foo(const Twine &T); 190909467b48Spatrick ... 191009467b48Spatrick StringRef X = ... 191109467b48Spatrick unsigned i = ... 191209467b48Spatrick const Twine &Tmp = X + "." + Twine(i); 191309467b48Spatrick foo(Tmp); 191409467b48Spatrick 191509467b48Spatrick... because the temporaries are destroyed before the call. That said, Twine's 191609467b48Spatrickare much more efficient than intermediate std::string temporaries, and they work 191709467b48Spatrickreally well with StringRef. Just be aware of their limitations. 191809467b48Spatrick 191909467b48Spatrick.. _dss_smallstring: 192009467b48Spatrick 192109467b48Spatrickllvm/ADT/SmallString.h 192209467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^ 192309467b48Spatrick 192409467b48SpatrickSmallString is a subclass of :ref:`SmallVector <dss_smallvector>` that adds some 192509467b48Spatrickconvenience APIs like += that takes StringRef's. SmallString avoids allocating 192609467b48Spatrickmemory in the case when the preallocated space is enough to hold its data, and 192709467b48Spatrickit calls back to general heap allocation when required. Since it owns its data, 192809467b48Spatrickit is very safe to use and supports full mutation of the string. 192909467b48Spatrick 193009467b48SpatrickLike SmallVector's, the big downside to SmallString is their sizeof. While they 193109467b48Spatrickare optimized for small strings, they themselves are not particularly small. 193209467b48SpatrickThis means that they work great for temporary scratch buffers on the stack, but 193309467b48Spatrickshould not generally be put into the heap: it is very rare to see a SmallString 193409467b48Spatrickas the member of a frequently-allocated heap data structure or returned 193509467b48Spatrickby-value. 193609467b48Spatrick 193709467b48Spatrick.. _dss_stdstring: 193809467b48Spatrick 193909467b48Spatrickstd::string 194009467b48Spatrick^^^^^^^^^^^ 194109467b48Spatrick 194209467b48SpatrickThe standard C++ std::string class is a very general class that (like 194309467b48SpatrickSmallString) owns its underlying data. sizeof(std::string) is very reasonable 194409467b48Spatrickso it can be embedded into heap data structures and returned by-value. On the 194509467b48Spatrickother hand, std::string is highly inefficient for inline editing (e.g. 194609467b48Spatrickconcatenating a bunch of stuff together) and because it is provided by the 194709467b48Spatrickstandard library, its performance characteristics depend a lot of the host 194809467b48Spatrickstandard library (e.g. libc++ and MSVC provide a highly optimized string class, 194909467b48SpatrickGCC contains a really slow implementation). 195009467b48Spatrick 195109467b48SpatrickThe major disadvantage of std::string is that almost every operation that makes 195209467b48Spatrickthem larger can allocate memory, which is slow. As such, it is better to use 195309467b48SpatrickSmallVector or Twine as a scratch buffer, but then use std::string to persist 195409467b48Spatrickthe result. 195509467b48Spatrick 195609467b48Spatrick.. _ds_set: 195709467b48Spatrick 195809467b48SpatrickSet-Like Containers (std::set, SmallSet, SetVector, etc) 195909467b48Spatrick-------------------------------------------------------- 196009467b48Spatrick 196109467b48SpatrickSet-like containers are useful when you need to canonicalize multiple values 196209467b48Spatrickinto a single representation. There are several different choices for how to do 196309467b48Spatrickthis, providing various trade-offs. 196409467b48Spatrick 196509467b48Spatrick.. _dss_sortedvectorset: 196609467b48Spatrick 196709467b48SpatrickA sorted 'vector' 196809467b48Spatrick^^^^^^^^^^^^^^^^^ 196909467b48Spatrick 197009467b48SpatrickIf you intend to insert a lot of elements, then do a lot of queries, a great 197109467b48Spatrickapproach is to use an std::vector (or other sequential container) with 197209467b48Spatrickstd::sort+std::unique to remove duplicates. This approach works really well if 197309467b48Spatrickyour usage pattern has these two distinct phases (insert then query), and can be 197409467b48Spatrickcoupled with a good choice of :ref:`sequential container <ds_sequential>`. 197509467b48Spatrick 197609467b48SpatrickThis combination provides the several nice properties: the result data is 197709467b48Spatrickcontiguous in memory (good for cache locality), has few allocations, is easy to 197809467b48Spatrickaddress (iterators in the final vector are just indices or pointers), and can be 197909467b48Spatrickefficiently queried with a standard binary search (e.g. 198009467b48Spatrick``std::lower_bound``; if you want the whole range of elements comparing 198109467b48Spatrickequal, use ``std::equal_range``). 198209467b48Spatrick 198309467b48Spatrick.. _dss_smallset: 198409467b48Spatrick 198509467b48Spatrickllvm/ADT/SmallSet.h 198609467b48Spatrick^^^^^^^^^^^^^^^^^^^ 198709467b48Spatrick 198809467b48SpatrickIf you have a set-like data structure that is usually small and whose elements 198909467b48Spatrickare reasonably small, a ``SmallSet<Type, N>`` is a good choice. This set has 199009467b48Spatrickspace for N elements in place (thus, if the set is dynamically smaller than N, 199109467b48Spatrickno malloc traffic is required) and accesses them with a simple linear search. 199209467b48SpatrickWhen the set grows beyond N elements, it allocates a more expensive 199309467b48Spatrickrepresentation that guarantees efficient access (for most types, it falls back 199409467b48Spatrickto :ref:`std::set <dss_set>`, but for pointers it uses something far better, 199509467b48Spatrick:ref:`SmallPtrSet <dss_smallptrset>`. 199609467b48Spatrick 199709467b48SpatrickThe magic of this class is that it handles small sets extremely efficiently, but 199809467b48Spatrickgracefully handles extremely large sets without loss of efficiency. 199909467b48Spatrick 200009467b48Spatrick.. _dss_smallptrset: 200109467b48Spatrick 200209467b48Spatrickllvm/ADT/SmallPtrSet.h 200309467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^ 200409467b48Spatrick 200509467b48Spatrick``SmallPtrSet`` has all the advantages of ``SmallSet`` (and a ``SmallSet`` of 200609467b48Spatrickpointers is transparently implemented with a ``SmallPtrSet``). If more than N 200709467b48Spatrickinsertions are performed, a single quadratically probed hash table is allocated 200809467b48Spatrickand grows as needed, providing extremely efficient access (constant time 200909467b48Spatrickinsertion/deleting/queries with low constant factors) and is very stingy with 201009467b48Spatrickmalloc traffic. 201109467b48Spatrick 201209467b48SpatrickNote that, unlike :ref:`std::set <dss_set>`, the iterators of ``SmallPtrSet`` 201309467b48Spatrickare invalidated whenever an insertion occurs. Also, the values visited by the 201409467b48Spatrickiterators are not visited in sorted order. 201509467b48Spatrick 201609467b48Spatrick.. _dss_stringset: 201709467b48Spatrick 201809467b48Spatrickllvm/ADT/StringSet.h 201909467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 202009467b48Spatrick 202109467b48Spatrick``StringSet`` is a thin wrapper around :ref:`StringMap\<char\> <dss_stringmap>`, 202209467b48Spatrickand it allows efficient storage and retrieval of unique strings. 202309467b48Spatrick 202409467b48SpatrickFunctionally analogous to ``SmallSet<StringRef>``, ``StringSet`` also supports 202509467b48Spatrickiteration. (The iterator dereferences to a ``StringMapEntry<char>``, so you 202609467b48Spatrickneed to call ``i->getKey()`` to access the item of the StringSet.) On the 202709467b48Spatrickother hand, ``StringSet`` doesn't support range-insertion and 202809467b48Spatrickcopy-construction, which :ref:`SmallSet <dss_smallset>` and :ref:`SmallPtrSet 202909467b48Spatrick<dss_smallptrset>` do support. 203009467b48Spatrick 203109467b48Spatrick.. _dss_denseset: 203209467b48Spatrick 203309467b48Spatrickllvm/ADT/DenseSet.h 203409467b48Spatrick^^^^^^^^^^^^^^^^^^^ 203509467b48Spatrick 203609467b48SpatrickDenseSet is a simple quadratically probed hash table. It excels at supporting 203709467b48Spatricksmall values: it uses a single allocation to hold all of the pairs that are 203809467b48Spatrickcurrently inserted in the set. DenseSet is a great way to unique small values 203909467b48Spatrickthat are not simple pointers (use :ref:`SmallPtrSet <dss_smallptrset>` for 204009467b48Spatrickpointers). Note that DenseSet has the same requirements for the value type that 204109467b48Spatrick:ref:`DenseMap <dss_densemap>` has. 204209467b48Spatrick 204309467b48Spatrick.. _dss_sparseset: 204409467b48Spatrick 204509467b48Spatrickllvm/ADT/SparseSet.h 204609467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 204709467b48Spatrick 204809467b48SpatrickSparseSet holds a small number of objects identified by unsigned keys of 204909467b48Spatrickmoderate size. It uses a lot of memory, but provides operations that are almost 205009467b48Spatrickas fast as a vector. Typical keys are physical registers, virtual registers, or 205109467b48Spatricknumbered basic blocks. 205209467b48Spatrick 205309467b48SpatrickSparseSet is useful for algorithms that need very fast clear/find/insert/erase 205409467b48Spatrickand fast iteration over small sets. It is not intended for building composite 205509467b48Spatrickdata structures. 205609467b48Spatrick 205709467b48Spatrick.. _dss_sparsemultiset: 205809467b48Spatrick 205909467b48Spatrickllvm/ADT/SparseMultiSet.h 206009467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 206109467b48Spatrick 206209467b48SpatrickSparseMultiSet adds multiset behavior to SparseSet, while retaining SparseSet's 206309467b48Spatrickdesirable attributes. Like SparseSet, it typically uses a lot of memory, but 206409467b48Spatrickprovides operations that are almost as fast as a vector. Typical keys are 206509467b48Spatrickphysical registers, virtual registers, or numbered basic blocks. 206609467b48Spatrick 206709467b48SpatrickSparseMultiSet is useful for algorithms that need very fast 206809467b48Spatrickclear/find/insert/erase of the entire collection, and iteration over sets of 206909467b48Spatrickelements sharing a key. It is often a more efficient choice than using composite 207009467b48Spatrickdata structures (e.g. vector-of-vectors, map-of-vectors). It is not intended for 207109467b48Spatrickbuilding composite data structures. 207209467b48Spatrick 207309467b48Spatrick.. _dss_FoldingSet: 207409467b48Spatrick 207509467b48Spatrickllvm/ADT/FoldingSet.h 207609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^ 207709467b48Spatrick 207809467b48SpatrickFoldingSet is an aggregate class that is really good at uniquing 207909467b48Spatrickexpensive-to-create or polymorphic objects. It is a combination of a chained 208009467b48Spatrickhash table with intrusive links (uniqued objects are required to inherit from 208109467b48SpatrickFoldingSetNode) that uses :ref:`SmallVector <dss_smallvector>` as part of its ID 208209467b48Spatrickprocess. 208309467b48Spatrick 208409467b48SpatrickConsider a case where you want to implement a "getOrCreateFoo" method for a 208509467b48Spatrickcomplex object (for example, a node in the code generator). The client has a 208609467b48Spatrickdescription of **what** it wants to generate (it knows the opcode and all the 208709467b48Spatrickoperands), but we don't want to 'new' a node, then try inserting it into a set 208809467b48Spatrickonly to find out it already exists, at which point we would have to delete it 208909467b48Spatrickand return the node that already exists. 209009467b48Spatrick 209109467b48SpatrickTo support this style of client, FoldingSet perform a query with a 209209467b48SpatrickFoldingSetNodeID (which wraps SmallVector) that can be used to describe the 209309467b48Spatrickelement that we want to query for. The query either returns the element 209409467b48Spatrickmatching the ID or it returns an opaque ID that indicates where insertion should 209509467b48Spatricktake place. Construction of the ID usually does not require heap traffic. 209609467b48Spatrick 209709467b48SpatrickBecause FoldingSet uses intrusive links, it can support polymorphic objects in 209809467b48Spatrickthe set (for example, you can have SDNode instances mixed with LoadSDNodes). 209909467b48SpatrickBecause the elements are individually allocated, pointers to the elements are 210009467b48Spatrickstable: inserting or removing elements does not invalidate any pointers to other 210109467b48Spatrickelements. 210209467b48Spatrick 210309467b48Spatrick.. _dss_set: 210409467b48Spatrick 210509467b48Spatrick<set> 210609467b48Spatrick^^^^^ 210709467b48Spatrick 210809467b48Spatrick``std::set`` is a reasonable all-around set class, which is decent at many 210909467b48Spatrickthings but great at nothing. std::set allocates memory for each element 211009467b48Spatrickinserted (thus it is very malloc intensive) and typically stores three pointers 211109467b48Spatrickper element in the set (thus adding a large amount of per-element space 211209467b48Spatrickoverhead). It offers guaranteed log(n) performance, which is not particularly 211309467b48Spatrickfast from a complexity standpoint (particularly if the elements of the set are 211409467b48Spatrickexpensive to compare, like strings), and has extremely high constant factors for 211509467b48Spatricklookup, insertion and removal. 211609467b48Spatrick 211709467b48SpatrickThe advantages of std::set are that its iterators are stable (deleting or 211809467b48Spatrickinserting an element from the set does not affect iterators or pointers to other 211909467b48Spatrickelements) and that iteration over the set is guaranteed to be in sorted order. 212009467b48SpatrickIf the elements in the set are large, then the relative overhead of the pointers 212109467b48Spatrickand malloc traffic is not a big deal, but if the elements of the set are small, 212209467b48Spatrickstd::set is almost never a good choice. 212309467b48Spatrick 212409467b48Spatrick.. _dss_setvector: 212509467b48Spatrick 212609467b48Spatrickllvm/ADT/SetVector.h 212709467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 212809467b48Spatrick 212909467b48SpatrickLLVM's ``SetVector<Type>`` is an adapter class that combines your choice of a 213009467b48Spatrickset-like container along with a :ref:`Sequential Container <ds_sequential>` The 213109467b48Spatrickimportant property that this provides is efficient insertion with uniquing 213209467b48Spatrick(duplicate elements are ignored) with iteration support. It implements this by 213309467b48Spatrickinserting elements into both a set-like container and the sequential container, 213409467b48Spatrickusing the set-like container for uniquing and the sequential container for 213509467b48Spatrickiteration. 213609467b48Spatrick 213709467b48SpatrickThe difference between SetVector and other sets is that the order of iteration 213809467b48Spatrickis guaranteed to match the order of insertion into the SetVector. This property 213909467b48Spatrickis really important for things like sets of pointers. Because pointer values 214009467b48Spatrickare non-deterministic (e.g. vary across runs of the program on different 214109467b48Spatrickmachines), iterating over the pointers in the set will not be in a well-defined 214209467b48Spatrickorder. 214309467b48Spatrick 214409467b48SpatrickThe drawback of SetVector is that it requires twice as much space as a normal 214509467b48Spatrickset and has the sum of constant factors from the set-like container and the 214609467b48Spatricksequential container that it uses. Use it **only** if you need to iterate over 214709467b48Spatrickthe elements in a deterministic order. SetVector is also expensive to delete 214809467b48Spatrickelements out of (linear time), unless you use its "pop_back" method, which is 214909467b48Spatrickfaster. 215009467b48Spatrick 215109467b48Spatrick``SetVector`` is an adapter class that defaults to using ``std::vector`` and a 215209467b48Spatricksize 16 ``SmallSet`` for the underlying containers, so it is quite expensive. 215309467b48SpatrickHowever, ``"llvm/ADT/SetVector.h"`` also provides a ``SmallSetVector`` class, 215409467b48Spatrickwhich defaults to using a ``SmallVector`` and ``SmallSet`` of a specified size. 215509467b48SpatrickIf you use this, and if your sets are dynamically smaller than ``N``, you will 215609467b48Spatricksave a lot of heap traffic. 215709467b48Spatrick 215809467b48Spatrick.. _dss_uniquevector: 215909467b48Spatrick 216009467b48Spatrickllvm/ADT/UniqueVector.h 216109467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 216209467b48Spatrick 216309467b48SpatrickUniqueVector is similar to :ref:`SetVector <dss_setvector>` but it retains a 216409467b48Spatrickunique ID for each element inserted into the set. It internally contains a map 216509467b48Spatrickand a vector, and it assigns a unique ID for each value inserted into the set. 216609467b48Spatrick 216709467b48SpatrickUniqueVector is very expensive: its cost is the sum of the cost of maintaining 216809467b48Spatrickboth the map and vector, it has high complexity, high constant factors, and 216909467b48Spatrickproduces a lot of malloc traffic. It should be avoided. 217009467b48Spatrick 217109467b48Spatrick.. _dss_immutableset: 217209467b48Spatrick 217309467b48Spatrickllvm/ADT/ImmutableSet.h 217409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 217509467b48Spatrick 217609467b48SpatrickImmutableSet is an immutable (functional) set implementation based on an AVL 217709467b48Spatricktree. Adding or removing elements is done through a Factory object and results 217809467b48Spatrickin the creation of a new ImmutableSet object. If an ImmutableSet already exists 217909467b48Spatrickwith the given contents, then the existing one is returned; equality is compared 218009467b48Spatrickwith a FoldingSetNodeID. The time and space complexity of add or remove 218109467b48Spatrickoperations is logarithmic in the size of the original set. 218209467b48Spatrick 218309467b48SpatrickThere is no method for returning an element of the set, you can only check for 218409467b48Spatrickmembership. 218509467b48Spatrick 218609467b48Spatrick.. _dss_otherset: 218709467b48Spatrick 218809467b48SpatrickOther Set-Like Container Options 218909467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 219009467b48Spatrick 2191*d415bd75SrobertThe STL provides several other options, such as std::multiset and 2192*d415bd75Srobertstd::unordered_set. We never use containers like unordered_set because 2193*d415bd75Srobertthey are generally very expensive (each insertion requires a malloc). 219409467b48Spatrick 219509467b48Spatrickstd::multiset is useful if you're not interested in elimination of duplicates, 219609467b48Spatrickbut has all the drawbacks of :ref:`std::set <dss_set>`. A sorted vector 219709467b48Spatrick(where you don't delete duplicate entries) or some other approach is almost 219809467b48Spatrickalways better. 219909467b48Spatrick 220009467b48Spatrick.. _ds_map: 220109467b48Spatrick 220209467b48SpatrickMap-Like Containers (std::map, DenseMap, etc) 220309467b48Spatrick--------------------------------------------- 220409467b48Spatrick 220509467b48SpatrickMap-like containers are useful when you want to associate data to a key. As 220609467b48Spatrickusual, there are a lot of different ways to do this. :) 220709467b48Spatrick 220809467b48Spatrick.. _dss_sortedvectormap: 220909467b48Spatrick 221009467b48SpatrickA sorted 'vector' 221109467b48Spatrick^^^^^^^^^^^^^^^^^ 221209467b48Spatrick 221309467b48SpatrickIf your usage pattern follows a strict insert-then-query approach, you can 221409467b48Spatricktrivially use the same approach as :ref:`sorted vectors for set-like containers 221509467b48Spatrick<dss_sortedvectorset>`. The only difference is that your query function (which 221609467b48Spatrickuses std::lower_bound to get efficient log(n) lookup) should only compare the 221709467b48Spatrickkey, not both the key and value. This yields the same advantages as sorted 221809467b48Spatrickvectors for sets. 221909467b48Spatrick 222009467b48Spatrick.. _dss_stringmap: 222109467b48Spatrick 222209467b48Spatrickllvm/ADT/StringMap.h 222309467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 222409467b48Spatrick 222509467b48SpatrickStrings are commonly used as keys in maps, and they are difficult to support 222609467b48Spatrickefficiently: they are variable length, inefficient to hash and compare when 222709467b48Spatricklong, expensive to copy, etc. StringMap is a specialized container designed to 222809467b48Spatrickcope with these issues. It supports mapping an arbitrary range of bytes to an 222909467b48Spatrickarbitrary other object. 223009467b48Spatrick 223109467b48SpatrickThe StringMap implementation uses a quadratically-probed hash table, where the 223209467b48Spatrickbuckets store a pointer to the heap allocated entries (and some other stuff). 223309467b48SpatrickThe entries in the map must be heap allocated because the strings are variable 223409467b48Spatricklength. The string data (key) and the element object (value) are stored in the 223509467b48Spatricksame allocation with the string data immediately after the element object. 223609467b48SpatrickThis container guarantees the "``(char*)(&Value+1)``" points to the key string 223709467b48Spatrickfor a value. 223809467b48Spatrick 223909467b48SpatrickThe StringMap is very fast for several reasons: quadratic probing is very cache 224009467b48Spatrickefficient for lookups, the hash value of strings in buckets is not recomputed 224109467b48Spatrickwhen looking up an element, StringMap rarely has to touch the memory for 224209467b48Spatrickunrelated objects when looking up a value (even when hash collisions happen), 224309467b48Spatrickhash table growth does not recompute the hash values for strings already in the 224409467b48Spatricktable, and each pair in the map is store in a single allocation (the string data 224509467b48Spatrickis stored in the same allocation as the Value of a pair). 224609467b48Spatrick 224709467b48SpatrickStringMap also provides query methods that take byte ranges, so it only ever 224809467b48Spatrickcopies a string if a value is inserted into the table. 224909467b48Spatrick 225009467b48SpatrickStringMap iteration order, however, is not guaranteed to be deterministic, so 225109467b48Spatrickany uses which require that should instead use a std::map. 225209467b48Spatrick 225309467b48Spatrick.. _dss_indexmap: 225409467b48Spatrick 225509467b48Spatrickllvm/ADT/IndexedMap.h 225609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^ 225709467b48Spatrick 225809467b48SpatrickIndexedMap is a specialized container for mapping small dense integers (or 225909467b48Spatrickvalues that can be mapped to small dense integers) to some other type. It is 226009467b48Spatrickinternally implemented as a vector with a mapping function that maps the keys 226109467b48Spatrickto the dense integer range. 226209467b48Spatrick 226309467b48SpatrickThis is useful for cases like virtual registers in the LLVM code generator: they 226409467b48Spatrickhave a dense mapping that is offset by a compile-time constant (the first 226509467b48Spatrickvirtual register ID). 226609467b48Spatrick 226709467b48Spatrick.. _dss_densemap: 226809467b48Spatrick 226909467b48Spatrickllvm/ADT/DenseMap.h 227009467b48Spatrick^^^^^^^^^^^^^^^^^^^ 227109467b48Spatrick 227209467b48SpatrickDenseMap is a simple quadratically probed hash table. It excels at supporting 227309467b48Spatricksmall keys and values: it uses a single allocation to hold all of the pairs 227409467b48Spatrickthat are currently inserted in the map. DenseMap is a great way to map 227509467b48Spatrickpointers to pointers, or map other small types to each other. 227609467b48Spatrick 227709467b48SpatrickThere are several aspects of DenseMap that you should be aware of, however. 227809467b48SpatrickThe iterators in a DenseMap are invalidated whenever an insertion occurs, 227909467b48Spatrickunlike map. Also, because DenseMap allocates space for a large number of 228009467b48Spatrickkey/value pairs (it starts with 64 by default), it will waste a lot of space if 228109467b48Spatrickyour keys or values are large. Finally, you must implement a partial 228209467b48Spatrickspecialization of DenseMapInfo for the key that you want, if it isn't already 228309467b48Spatricksupported. This is required to tell DenseMap about two special marker values 228409467b48Spatrick(which can never be inserted into the map) that it needs internally. 228509467b48Spatrick 228609467b48SpatrickDenseMap's find_as() method supports lookup operations using an alternate key 228709467b48Spatricktype. This is useful in cases where the normal key type is expensive to 228809467b48Spatrickconstruct, but cheap to compare against. The DenseMapInfo is responsible for 228909467b48Spatrickdefining the appropriate comparison and hashing methods for each alternate key 229009467b48Spatricktype used. 229109467b48Spatrick 229209467b48Spatrick.. _dss_valuemap: 229309467b48Spatrick 229409467b48Spatrickllvm/IR/ValueMap.h 229509467b48Spatrick^^^^^^^^^^^^^^^^^^^ 229609467b48Spatrick 229709467b48SpatrickValueMap is a wrapper around a :ref:`DenseMap <dss_densemap>` mapping 229809467b48Spatrick``Value*``\ s (or subclasses) to another type. When a Value is deleted or 229909467b48SpatrickRAUW'ed, ValueMap will update itself so the new version of the key is mapped to 230009467b48Spatrickthe same value, just as if the key were a WeakVH. You can configure exactly how 230109467b48Spatrickthis happens, and what else happens on these two events, by passing a ``Config`` 230209467b48Spatrickparameter to the ValueMap template. 230309467b48Spatrick 230409467b48Spatrick.. _dss_intervalmap: 230509467b48Spatrick 230609467b48Spatrickllvm/ADT/IntervalMap.h 230709467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^ 230809467b48Spatrick 230909467b48SpatrickIntervalMap is a compact map for small keys and values. It maps key intervals 231009467b48Spatrickinstead of single keys, and it will automatically coalesce adjacent intervals. 231109467b48SpatrickWhen the map only contains a few intervals, they are stored in the map object 231209467b48Spatrickitself to avoid allocations. 231309467b48Spatrick 231409467b48SpatrickThe IntervalMap iterators are quite big, so they should not be passed around as 231509467b48SpatrickSTL iterators. The heavyweight iterators allow a smaller data structure. 231609467b48Spatrick 2317*d415bd75Srobert.. _dss_intervaltree: 2318*d415bd75Srobert 2319*d415bd75Srobertllvm/ADT/IntervalTree.h 2320*d415bd75Srobert^^^^^^^^^^^^^^^^^^^^^^^ 2321*d415bd75Srobert 2322*d415bd75Srobert``llvm::IntervalTree`` is a light tree data structure to hold intervals. It 2323*d415bd75Srobertallows finding all intervals that overlap with any given point. At this time, 2324*d415bd75Srobertit does not support any deletion or rebalancing operations. 2325*d415bd75Srobert 2326*d415bd75SrobertThe IntervalTree is designed to be set up once, and then queried without any 2327*d415bd75Srobertfurther additions. 2328*d415bd75Srobert 232909467b48Spatrick.. _dss_map: 233009467b48Spatrick 233109467b48Spatrick<map> 233209467b48Spatrick^^^^^ 233309467b48Spatrick 233409467b48Spatrickstd::map has similar characteristics to :ref:`std::set <dss_set>`: it uses a 233509467b48Spatricksingle allocation per pair inserted into the map, it offers log(n) lookup with 233609467b48Spatrickan extremely large constant factor, imposes a space penalty of 3 pointers per 233709467b48Spatrickpair in the map, etc. 233809467b48Spatrick 233909467b48Spatrickstd::map is most useful when your keys or values are very large, if you need to 234009467b48Spatrickiterate over the collection in sorted order, or if you need stable iterators 234109467b48Spatrickinto the map (i.e. they don't get invalidated if an insertion or deletion of 234209467b48Spatrickanother element takes place). 234309467b48Spatrick 234409467b48Spatrick.. _dss_mapvector: 234509467b48Spatrick 234609467b48Spatrickllvm/ADT/MapVector.h 234709467b48Spatrick^^^^^^^^^^^^^^^^^^^^ 234809467b48Spatrick 234909467b48Spatrick``MapVector<KeyT,ValueT>`` provides a subset of the DenseMap interface. The 235009467b48Spatrickmain difference is that the iteration order is guaranteed to be the insertion 235109467b48Spatrickorder, making it an easy (but somewhat expensive) solution for non-deterministic 235209467b48Spatrickiteration over maps of pointers. 235309467b48Spatrick 235409467b48SpatrickIt is implemented by mapping from key to an index in a vector of key,value 235509467b48Spatrickpairs. This provides fast lookup and iteration, but has two main drawbacks: 235609467b48Spatrickthe key is stored twice and removing elements takes linear time. If it is 235709467b48Spatricknecessary to remove elements, it's best to remove them in bulk using 235809467b48Spatrick``remove_if()``. 235909467b48Spatrick 236009467b48Spatrick.. _dss_inteqclasses: 236109467b48Spatrick 236209467b48Spatrickllvm/ADT/IntEqClasses.h 236309467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 236409467b48Spatrick 236509467b48SpatrickIntEqClasses provides a compact representation of equivalence classes of small 236609467b48Spatrickintegers. Initially, each integer in the range 0..n-1 has its own equivalence 236709467b48Spatrickclass. Classes can be joined by passing two class representatives to the 236809467b48Spatrickjoin(a, b) method. Two integers are in the same class when findLeader() returns 236909467b48Spatrickthe same representative. 237009467b48Spatrick 237109467b48SpatrickOnce all equivalence classes are formed, the map can be compressed so each 237209467b48Spatrickinteger 0..n-1 maps to an equivalence class number in the range 0..m-1, where m 237309467b48Spatrickis the total number of equivalence classes. The map must be uncompressed before 237409467b48Spatrickit can be edited again. 237509467b48Spatrick 237609467b48Spatrick.. _dss_immutablemap: 237709467b48Spatrick 237809467b48Spatrickllvm/ADT/ImmutableMap.h 237909467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 238009467b48Spatrick 238109467b48SpatrickImmutableMap is an immutable (functional) map implementation based on an AVL 238209467b48Spatricktree. Adding or removing elements is done through a Factory object and results 238309467b48Spatrickin the creation of a new ImmutableMap object. If an ImmutableMap already exists 238409467b48Spatrickwith the given key set, then the existing one is returned; equality is compared 238509467b48Spatrickwith a FoldingSetNodeID. The time and space complexity of add or remove 238609467b48Spatrickoperations is logarithmic in the size of the original map. 238709467b48Spatrick 238809467b48Spatrick.. _dss_othermap: 238909467b48Spatrick 239009467b48SpatrickOther Map-Like Container Options 239109467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 239209467b48Spatrick 2393*d415bd75SrobertThe STL provides several other options, such as std::multimap and 2394*d415bd75Srobertstd::unordered_map. We never use containers like unordered_map because 2395*d415bd75Srobertthey are generally very expensive (each insertion requires a malloc). 239609467b48Spatrick 239709467b48Spatrickstd::multimap is useful if you want to map a key to multiple values, but has all 239809467b48Spatrickthe drawbacks of std::map. A sorted vector or some other approach is almost 239909467b48Spatrickalways better. 240009467b48Spatrick 240109467b48Spatrick.. _ds_bit: 240209467b48Spatrick 2403*d415bd75SrobertBit storage containers 2404097a140dSpatrick------------------------------------------------------------------------ 240509467b48Spatrick 2406*d415bd75SrobertThere are several bit storage containers, and choosing when to use each is 2407097a140dSpatrickrelatively straightforward. 240809467b48Spatrick 240909467b48SpatrickOne additional option is ``std::vector<bool>``: we discourage its use for two 241009467b48Spatrickreasons 1) the implementation in many common compilers (e.g. commonly 241109467b48Spatrickavailable versions of GCC) is extremely inefficient and 2) the C++ standards 241209467b48Spatrickcommittee is likely to deprecate this container and/or change it significantly 241309467b48Spatricksomehow. In any case, please don't use it. 241409467b48Spatrick 241509467b48Spatrick.. _dss_bitvector: 241609467b48Spatrick 241709467b48SpatrickBitVector 241809467b48Spatrick^^^^^^^^^ 241909467b48Spatrick 242009467b48SpatrickThe BitVector container provides a dynamic size set of bits for manipulation. 242109467b48SpatrickIt supports individual bit setting/testing, as well as set operations. The set 242209467b48Spatrickoperations take time O(size of bitvector), but operations are performed one word 242309467b48Spatrickat a time, instead of one bit at a time. This makes the BitVector very fast for 242409467b48Spatrickset operations compared to other containers. Use the BitVector when you expect 242509467b48Spatrickthe number of set bits to be high (i.e. a dense set). 242609467b48Spatrick 242709467b48Spatrick.. _dss_smallbitvector: 242809467b48Spatrick 242909467b48SpatrickSmallBitVector 243009467b48Spatrick^^^^^^^^^^^^^^ 243109467b48Spatrick 243209467b48SpatrickThe SmallBitVector container provides the same interface as BitVector, but it is 243309467b48Spatrickoptimized for the case where only a small number of bits, less than 25 or so, 243409467b48Spatrickare needed. It also transparently supports larger bit counts, but slightly less 243509467b48Spatrickefficiently than a plain BitVector, so SmallBitVector should only be used when 243609467b48Spatricklarger counts are rare. 243709467b48Spatrick 243809467b48SpatrickAt this time, SmallBitVector does not support set operations (and, or, xor), and 243909467b48Spatrickits operator[] does not provide an assignable lvalue. 244009467b48Spatrick 244109467b48Spatrick.. _dss_sparsebitvector: 244209467b48Spatrick 244309467b48SpatrickSparseBitVector 244409467b48Spatrick^^^^^^^^^^^^^^^ 244509467b48Spatrick 244609467b48SpatrickThe SparseBitVector container is much like BitVector, with one major difference: 244709467b48SpatrickOnly the bits that are set, are stored. This makes the SparseBitVector much 244809467b48Spatrickmore space efficient than BitVector when the set is sparse, as well as making 244909467b48Spatrickset operations O(number of set bits) instead of O(size of universe). The 245009467b48Spatrickdownside to the SparseBitVector is that setting and testing of random bits is 245109467b48SpatrickO(N), and on large SparseBitVectors, this can be slower than BitVector. In our 245209467b48Spatrickimplementation, setting or testing bits in sorted order (either forwards or 245309467b48Spatrickreverse) is O(1) worst case. Testing and setting bits within 128 bits (depends 245409467b48Spatrickon size) of the current bit is also O(1). As a general statement, 245509467b48Spatricktesting/setting bits in a SparseBitVector is O(distance away from last set bit). 245609467b48Spatrick 2457097a140dSpatrick.. _dss_coalescingbitvector: 2458097a140dSpatrick 2459097a140dSpatrickCoalescingBitVector 2460097a140dSpatrick^^^^^^^^^^^^^^^^^^^ 2461097a140dSpatrick 2462097a140dSpatrickThe CoalescingBitVector container is similar in principle to a SparseBitVector, 2463097a140dSpatrickbut is optimized to represent large contiguous ranges of set bits compactly. It 2464097a140dSpatrickdoes this by coalescing contiguous ranges of set bits into intervals. Searching 2465097a140dSpatrickfor a bit in a CoalescingBitVector is O(log(gaps between contiguous ranges)). 2466097a140dSpatrick 2467097a140dSpatrickCoalescingBitVector is a better choice than BitVector when gaps between ranges 2468097a140dSpatrickof set bits are large. It's a better choice than SparseBitVector when find() 2469097a140dSpatrickoperations must have fast, predictable performance. However, it's not a good 2470097a140dSpatrickchoice for representing sets which have lots of very short ranges. E.g. the set 2471097a140dSpatrick`{2*x : x \in [0, n)}` would be a pathological input. 2472097a140dSpatrick 247309467b48Spatrick.. _debugging: 247409467b48Spatrick 247509467b48SpatrickDebugging 247609467b48Spatrick========= 247709467b48Spatrick 247809467b48SpatrickA handful of `GDB pretty printers 247909467b48Spatrick<https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing.html>`__ are 248009467b48Spatrickprovided for some of the core LLVM libraries. To use them, execute the 248109467b48Spatrickfollowing (or add it to your ``~/.gdbinit``):: 248209467b48Spatrick 248309467b48Spatrick source /path/to/llvm/src/utils/gdb-scripts/prettyprinters.py 248409467b48Spatrick 248509467b48SpatrickIt also might be handy to enable the `print pretty 248609467b48Spatrick<http://ftp.gnu.org/old-gnu/Manuals/gdb/html_node/gdb_57.html>`__ option to 248709467b48Spatrickavoid data structures being printed as a big block of text. 248809467b48Spatrick 248909467b48Spatrick.. _common: 249009467b48Spatrick 249109467b48SpatrickHelpful Hints for Common Operations 249209467b48Spatrick=================================== 249309467b48Spatrick 249409467b48SpatrickThis section describes how to perform some very simple transformations of LLVM 249509467b48Spatrickcode. This is meant to give examples of common idioms used, showing the 249609467b48Spatrickpractical side of LLVM transformations. 249709467b48Spatrick 249809467b48SpatrickBecause this is a "how-to" section, you should also read about the main classes 249909467b48Spatrickthat you will be working with. The :ref:`Core LLVM Class Hierarchy Reference 250009467b48Spatrick<coreclasses>` contains details and descriptions of the main classes that you 250109467b48Spatrickshould know about. 250209467b48Spatrick 250309467b48Spatrick.. _inspection: 250409467b48Spatrick 250509467b48SpatrickBasic Inspection and Traversal Routines 250609467b48Spatrick--------------------------------------- 250709467b48Spatrick 250809467b48SpatrickThe LLVM compiler infrastructure have many different data structures that may be 250909467b48Spatricktraversed. Following the example of the C++ standard template library, the 251009467b48Spatricktechniques used to traverse these various data structures are all basically the 251173471bf0Spatricksame. For an enumerable sequence of values, the ``XXXbegin()`` function (or 251209467b48Spatrickmethod) returns an iterator to the start of the sequence, the ``XXXend()`` 251309467b48Spatrickfunction returns an iterator pointing to one past the last valid element of the 251409467b48Spatricksequence, and there is some ``XXXiterator`` data type that is common between the 251509467b48Spatricktwo operations. 251609467b48Spatrick 251709467b48SpatrickBecause the pattern for iteration is common across many different aspects of the 251809467b48Spatrickprogram representation, the standard template library algorithms may be used on 251909467b48Spatrickthem, and it is easier to remember how to iterate. First we show a few common 252009467b48Spatrickexamples of the data structures that need to be traversed. Other data 252109467b48Spatrickstructures are traversed in very similar ways. 252209467b48Spatrick 252309467b48Spatrick.. _iterate_function: 252409467b48Spatrick 252509467b48SpatrickIterating over the ``BasicBlock`` in a ``Function`` 252609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 252709467b48Spatrick 252809467b48SpatrickIt's quite common to have a ``Function`` instance that you'd like to transform 252909467b48Spatrickin some way; in particular, you'd like to manipulate its ``BasicBlock``\ s. To 253009467b48Spatrickfacilitate this, you'll need to iterate over all of the ``BasicBlock``\ s that 253109467b48Spatrickconstitute the ``Function``. The following is an example that prints the name 253209467b48Spatrickof a ``BasicBlock`` and the number of ``Instruction``\ s it contains: 253309467b48Spatrick 253409467b48Spatrick.. code-block:: c++ 253509467b48Spatrick 253609467b48Spatrick Function &Func = ... 253709467b48Spatrick for (BasicBlock &BB : Func) 253809467b48Spatrick // Print out the name of the basic block if it has one, and then the 253909467b48Spatrick // number of instructions that it contains 254009467b48Spatrick errs() << "Basic block (name=" << BB.getName() << ") has " 254109467b48Spatrick << BB.size() << " instructions.\n"; 254209467b48Spatrick 254309467b48Spatrick.. _iterate_basicblock: 254409467b48Spatrick 254509467b48SpatrickIterating over the ``Instruction`` in a ``BasicBlock`` 254609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 254709467b48Spatrick 254809467b48SpatrickJust like when dealing with ``BasicBlock``\ s in ``Function``\ s, it's easy to 254909467b48Spatrickiterate over the individual instructions that make up ``BasicBlock``\ s. Here's 255009467b48Spatricka code snippet that prints out each instruction in a ``BasicBlock``: 255109467b48Spatrick 255209467b48Spatrick.. code-block:: c++ 255309467b48Spatrick 255409467b48Spatrick BasicBlock& BB = ... 255509467b48Spatrick for (Instruction &I : BB) 255609467b48Spatrick // The next statement works since operator<<(ostream&,...) 255709467b48Spatrick // is overloaded for Instruction& 255809467b48Spatrick errs() << I << "\n"; 255909467b48Spatrick 256009467b48Spatrick 256109467b48SpatrickHowever, this isn't really the best way to print out the contents of a 256209467b48Spatrick``BasicBlock``! Since the ostream operators are overloaded for virtually 256309467b48Spatrickanything you'll care about, you could have just invoked the print routine on the 256409467b48Spatrickbasic block itself: ``errs() << BB << "\n";``. 256509467b48Spatrick 256609467b48Spatrick.. _iterate_insiter: 256709467b48Spatrick 256809467b48SpatrickIterating over the ``Instruction`` in a ``Function`` 256909467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 257009467b48Spatrick 257109467b48SpatrickIf you're finding that you commonly iterate over a ``Function``'s 257209467b48Spatrick``BasicBlock``\ s and then that ``BasicBlock``'s ``Instruction``\ s, 257309467b48Spatrick``InstIterator`` should be used instead. You'll need to include 257409467b48Spatrick``llvm/IR/InstIterator.h`` (`doxygen 2575097a140dSpatrick<https://llvm.org/doxygen/InstIterator_8h.html>`__) and then instantiate 257609467b48Spatrick``InstIterator``\ s explicitly in your code. Here's a small example that shows 257709467b48Spatrickhow to dump all instructions in a function to the standard error stream: 257809467b48Spatrick 257909467b48Spatrick.. code-block:: c++ 258009467b48Spatrick 258109467b48Spatrick #include "llvm/IR/InstIterator.h" 258209467b48Spatrick 258309467b48Spatrick // F is a pointer to a Function instance 258409467b48Spatrick for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 258509467b48Spatrick errs() << *I << "\n"; 258609467b48Spatrick 258709467b48SpatrickEasy, isn't it? You can also use ``InstIterator``\ s to fill a work list with 258809467b48Spatrickits initial contents. For example, if you wanted to initialize a work list to 258909467b48Spatrickcontain all instructions in a ``Function`` F, all you would need to do is 259009467b48Spatricksomething like: 259109467b48Spatrick 259209467b48Spatrick.. code-block:: c++ 259309467b48Spatrick 259409467b48Spatrick std::set<Instruction*> worklist; 259509467b48Spatrick // or better yet, SmallPtrSet<Instruction*, 64> worklist; 259609467b48Spatrick 259709467b48Spatrick for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 259809467b48Spatrick worklist.insert(&*I); 259909467b48Spatrick 260009467b48SpatrickThe STL set ``worklist`` would now contain all instructions in the ``Function`` 260109467b48Spatrickpointed to by F. 260209467b48Spatrick 260309467b48Spatrick.. _iterate_convert: 260409467b48Spatrick 260509467b48SpatrickTurning an iterator into a class pointer (and vice-versa) 260609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 260709467b48Spatrick 260809467b48SpatrickSometimes, it'll be useful to grab a reference (or pointer) to a class instance 260909467b48Spatrickwhen all you've got at hand is an iterator. Well, extracting a reference or a 261009467b48Spatrickpointer from an iterator is very straight-forward. Assuming that ``i`` is a 261109467b48Spatrick``BasicBlock::iterator`` and ``j`` is a ``BasicBlock::const_iterator``: 261209467b48Spatrick 261309467b48Spatrick.. code-block:: c++ 261409467b48Spatrick 261509467b48Spatrick Instruction& inst = *i; // Grab reference to instruction reference 261609467b48Spatrick Instruction* pinst = &*i; // Grab pointer to instruction reference 261709467b48Spatrick const Instruction& inst = *j; 261809467b48Spatrick 261909467b48SpatrickHowever, the iterators you'll be working with in the LLVM framework are special: 262009467b48Spatrickthey will automatically convert to a ptr-to-instance type whenever they need to. 262109467b48SpatrickInstead of dereferencing the iterator and then taking the address of the result, 262209467b48Spatrickyou can simply assign the iterator to the proper pointer type and you get the 262309467b48Spatrickdereference and address-of operation as a result of the assignment (behind the 262409467b48Spatrickscenes, this is a result of overloading casting mechanisms). Thus the second 262509467b48Spatrickline of the last example, 262609467b48Spatrick 262709467b48Spatrick.. code-block:: c++ 262809467b48Spatrick 262909467b48Spatrick Instruction *pinst = &*i; 263009467b48Spatrick 263109467b48Spatrickis semantically equivalent to 263209467b48Spatrick 263309467b48Spatrick.. code-block:: c++ 263409467b48Spatrick 263509467b48Spatrick Instruction *pinst = i; 263609467b48Spatrick 263709467b48SpatrickIt's also possible to turn a class pointer into the corresponding iterator, and 263809467b48Spatrickthis is a constant time operation (very efficient). The following code snippet 263909467b48Spatrickillustrates use of the conversion constructors provided by LLVM iterators. By 264009467b48Spatrickusing these, you can explicitly grab the iterator of something without actually 264109467b48Spatrickobtaining it via iteration over some structure: 264209467b48Spatrick 264309467b48Spatrick.. code-block:: c++ 264409467b48Spatrick 264509467b48Spatrick void printNextInstruction(Instruction* inst) { 264609467b48Spatrick BasicBlock::iterator it(inst); 264709467b48Spatrick ++it; // After this line, it refers to the instruction after *inst 264809467b48Spatrick if (it != inst->getParent()->end()) errs() << *it << "\n"; 264909467b48Spatrick } 265009467b48Spatrick 265109467b48SpatrickUnfortunately, these implicit conversions come at a cost; they prevent these 265209467b48Spatrickiterators from conforming to standard iterator conventions, and thus from being 265309467b48Spatrickusable with standard algorithms and containers. For example, they prevent the 265409467b48Spatrickfollowing code, where ``B`` is a ``BasicBlock``, from compiling: 265509467b48Spatrick 265609467b48Spatrick.. code-block:: c++ 265709467b48Spatrick 265809467b48Spatrick llvm::SmallVector<llvm::Instruction *, 16>(B->begin(), B->end()); 265909467b48Spatrick 266009467b48SpatrickBecause of this, these implicit conversions may be removed some day, and 266109467b48Spatrick``operator*`` changed to return a pointer instead of a reference. 266209467b48Spatrick 266309467b48Spatrick.. _iterate_complex: 266409467b48Spatrick 266509467b48SpatrickFinding call sites: a slightly more complex example 266609467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 266709467b48Spatrick 266809467b48SpatrickSay that you're writing a FunctionPass and would like to count all the locations 266909467b48Spatrickin the entire module (that is, across every ``Function``) where a certain 267009467b48Spatrickfunction (i.e., some ``Function *``) is already in scope. As you'll learn 267109467b48Spatricklater, you may want to use an ``InstVisitor`` to accomplish this in a much more 267209467b48Spatrickstraight-forward manner, but this example will allow us to explore how you'd do 267309467b48Spatrickit if you didn't have ``InstVisitor`` around. In pseudo-code, this is what we 267409467b48Spatrickwant to do: 267509467b48Spatrick 267609467b48Spatrick.. code-block:: none 267709467b48Spatrick 267809467b48Spatrick initialize callCounter to zero 267909467b48Spatrick for each Function f in the Module 268009467b48Spatrick for each BasicBlock b in f 268109467b48Spatrick for each Instruction i in b 2682097a140dSpatrick if (i a Call and calls the given function) 268309467b48Spatrick increment callCounter 268409467b48Spatrick 268509467b48SpatrickAnd the actual code is (remember, because we're writing a ``FunctionPass``, our 268609467b48Spatrick``FunctionPass``-derived class simply has to override the ``runOnFunction`` 268709467b48Spatrickmethod): 268809467b48Spatrick 268909467b48Spatrick.. code-block:: c++ 269009467b48Spatrick 269109467b48Spatrick Function* targetFunc = ...; 269209467b48Spatrick 269309467b48Spatrick class OurFunctionPass : public FunctionPass { 269409467b48Spatrick public: 269509467b48Spatrick OurFunctionPass(): callCounter(0) { } 269609467b48Spatrick 269709467b48Spatrick virtual runOnFunction(Function& F) { 269809467b48Spatrick for (BasicBlock &B : F) { 269909467b48Spatrick for (Instruction &I: B) { 2700097a140dSpatrick if (auto *CB = dyn_cast<CallBase>(&I)) { 2701097a140dSpatrick // We know we've encountered some kind of call instruction (call, 2702097a140dSpatrick // invoke, or callbr), so we need to determine if it's a call to 2703097a140dSpatrick // the function pointed to by m_func or not. 2704097a140dSpatrick if (CB->getCalledFunction() == targetFunc) 270509467b48Spatrick ++callCounter; 270609467b48Spatrick } 270709467b48Spatrick } 270809467b48Spatrick } 270909467b48Spatrick } 271009467b48Spatrick 271109467b48Spatrick private: 271209467b48Spatrick unsigned callCounter; 271309467b48Spatrick }; 271409467b48Spatrick 271509467b48Spatrick.. _iterate_chains: 271609467b48Spatrick 271709467b48SpatrickIterating over def-use & use-def chains 271809467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 271909467b48Spatrick 272009467b48SpatrickFrequently, we might have an instance of the ``Value`` class (`doxygen 2721097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1Value.html>`__) and we want to determine 272209467b48Spatrickwhich ``User``\ s use the ``Value``. The list of all ``User``\ s of a particular 272309467b48Spatrick``Value`` is called a *def-use* chain. For example, let's say we have a 272409467b48Spatrick``Function*`` named ``F`` to a particular function ``foo``. Finding all of the 272509467b48Spatrickinstructions that *use* ``foo`` is as simple as iterating over the *def-use* 272609467b48Spatrickchain of ``F``: 272709467b48Spatrick 272809467b48Spatrick.. code-block:: c++ 272909467b48Spatrick 273009467b48Spatrick Function *F = ...; 273109467b48Spatrick 273209467b48Spatrick for (User *U : F->users()) { 273309467b48Spatrick if (Instruction *Inst = dyn_cast<Instruction>(U)) { 273409467b48Spatrick errs() << "F is used in instruction:\n"; 273509467b48Spatrick errs() << *Inst << "\n"; 273609467b48Spatrick } 273709467b48Spatrick 273809467b48SpatrickAlternatively, it's common to have an instance of the ``User`` Class (`doxygen 2739097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1User.html>`__) and need to know what 274009467b48Spatrick``Value``\ s are used by it. The list of all ``Value``\ s used by a ``User`` is 274109467b48Spatrickknown as a *use-def* chain. Instances of class ``Instruction`` are common 274209467b48Spatrick``User`` s, so we might want to iterate over all of the values that a particular 274309467b48Spatrickinstruction uses (that is, the operands of the particular ``Instruction``): 274409467b48Spatrick 274509467b48Spatrick.. code-block:: c++ 274609467b48Spatrick 274709467b48Spatrick Instruction *pi = ...; 274809467b48Spatrick 274909467b48Spatrick for (Use &U : pi->operands()) { 275009467b48Spatrick Value *v = U.get(); 275109467b48Spatrick // ... 275209467b48Spatrick } 275309467b48Spatrick 275409467b48SpatrickDeclaring objects as ``const`` is an important tool of enforcing mutation free 275509467b48Spatrickalgorithms (such as analyses, etc.). For this purpose above iterators come in 275609467b48Spatrickconstant flavors as ``Value::const_use_iterator`` and 275709467b48Spatrick``Value::const_op_iterator``. They automatically arise when calling 275809467b48Spatrick``use/op_begin()`` on ``const Value*``\ s or ``const User*``\ s respectively. 275909467b48SpatrickUpon dereferencing, they return ``const Use*``\ s. Otherwise the above patterns 276009467b48Spatrickremain unchanged. 276109467b48Spatrick 276209467b48Spatrick.. _iterate_preds: 276309467b48Spatrick 276409467b48SpatrickIterating over predecessors & successors of blocks 276509467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 276609467b48Spatrick 276709467b48SpatrickIterating over the predecessors and successors of a block is quite easy with the 276809467b48Spatrickroutines defined in ``"llvm/IR/CFG.h"``. Just use code like this to 276909467b48Spatrickiterate over all predecessors of BB: 277009467b48Spatrick 277109467b48Spatrick.. code-block:: c++ 277209467b48Spatrick 277309467b48Spatrick #include "llvm/IR/CFG.h" 277409467b48Spatrick BasicBlock *BB = ...; 277509467b48Spatrick 277609467b48Spatrick for (BasicBlock *Pred : predecessors(BB)) { 277709467b48Spatrick // ... 277809467b48Spatrick } 277909467b48Spatrick 278009467b48SpatrickSimilarly, to iterate over successors use ``successors``. 278109467b48Spatrick 278209467b48Spatrick.. _simplechanges: 278309467b48Spatrick 278409467b48SpatrickMaking simple changes 278509467b48Spatrick--------------------- 278609467b48Spatrick 278709467b48SpatrickThere are some primitive transformation operations present in the LLVM 278809467b48Spatrickinfrastructure that are worth knowing about. When performing transformations, 278909467b48Spatrickit's fairly common to manipulate the contents of basic blocks. This section 279009467b48Spatrickdescribes some of the common methods for doing so and gives example code. 279109467b48Spatrick 279209467b48Spatrick.. _schanges_creating: 279309467b48Spatrick 279409467b48SpatrickCreating and inserting new ``Instruction``\ s 279509467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 279609467b48Spatrick 279709467b48Spatrick*Instantiating Instructions* 279809467b48Spatrick 279909467b48SpatrickCreation of ``Instruction``\ s is straight-forward: simply call the constructor 280009467b48Spatrickfor the kind of instruction to instantiate and provide the necessary parameters. 280109467b48SpatrickFor example, an ``AllocaInst`` only *requires* a (const-ptr-to) ``Type``. Thus: 280209467b48Spatrick 280309467b48Spatrick.. code-block:: c++ 280409467b48Spatrick 280509467b48Spatrick auto *ai = new AllocaInst(Type::Int32Ty); 280609467b48Spatrick 280709467b48Spatrickwill create an ``AllocaInst`` instance that represents the allocation of one 280809467b48Spatrickinteger in the current stack frame, at run time. Each ``Instruction`` subclass 280909467b48Spatrickis likely to have varying default parameters which change the semantics of the 281009467b48Spatrickinstruction, so refer to the `doxygen documentation for the subclass of 2811097a140dSpatrickInstruction <https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_ that 281209467b48Spatrickyou're interested in instantiating. 281309467b48Spatrick 281409467b48Spatrick*Naming values* 281509467b48Spatrick 281609467b48SpatrickIt is very useful to name the values of instructions when you're able to, as 281709467b48Spatrickthis facilitates the debugging of your transformations. If you end up looking 281809467b48Spatrickat generated LLVM machine code, you definitely want to have logical names 281909467b48Spatrickassociated with the results of instructions! By supplying a value for the 282009467b48Spatrick``Name`` (default) parameter of the ``Instruction`` constructor, you associate a 282109467b48Spatricklogical name with the result of the instruction's execution at run time. For 282209467b48Spatrickexample, say that I'm writing a transformation that dynamically allocates space 282309467b48Spatrickfor an integer on the stack, and that integer is going to be used as some kind 282409467b48Spatrickof index by some other code. To accomplish this, I place an ``AllocaInst`` at 282509467b48Spatrickthe first point in the first ``BasicBlock`` of some ``Function``, and I'm 282609467b48Spatrickintending to use it within the same ``Function``. I might do: 282709467b48Spatrick 282809467b48Spatrick.. code-block:: c++ 282909467b48Spatrick 283009467b48Spatrick auto *pa = new AllocaInst(Type::Int32Ty, 0, "indexLoc"); 283109467b48Spatrick 283209467b48Spatrickwhere ``indexLoc`` is now the logical name of the instruction's execution value, 283309467b48Spatrickwhich is a pointer to an integer on the run time stack. 283409467b48Spatrick 283509467b48Spatrick*Inserting instructions* 283609467b48Spatrick 283709467b48SpatrickThere are essentially three ways to insert an ``Instruction`` into an existing 283809467b48Spatricksequence of instructions that form a ``BasicBlock``: 283909467b48Spatrick 2840*d415bd75Srobert* Insertion into the instruction list of the ``BasicBlock`` 284109467b48Spatrick 284209467b48Spatrick Given a ``BasicBlock* pb``, an ``Instruction* pi`` within that ``BasicBlock``, 284309467b48Spatrick and a newly-created instruction we wish to insert before ``*pi``, we do the 284409467b48Spatrick following: 284509467b48Spatrick 284609467b48Spatrick .. code-block:: c++ 284709467b48Spatrick 284809467b48Spatrick BasicBlock *pb = ...; 284909467b48Spatrick Instruction *pi = ...; 285009467b48Spatrick auto *newInst = new Instruction(...); 285109467b48Spatrick 2852*d415bd75Srobert newInst->insertBefore(pi); // Inserts newInst before pi 285309467b48Spatrick 285409467b48Spatrick Appending to the end of a ``BasicBlock`` is so common that the ``Instruction`` 285509467b48Spatrick class and ``Instruction``-derived classes provide constructors which take a 285609467b48Spatrick pointer to a ``BasicBlock`` to be appended to. For example code that looked 285709467b48Spatrick like: 285809467b48Spatrick 285909467b48Spatrick .. code-block:: c++ 286009467b48Spatrick 286109467b48Spatrick BasicBlock *pb = ...; 286209467b48Spatrick auto *newInst = new Instruction(...); 286309467b48Spatrick 2864*d415bd75Srobert newInst->insertInto(pb, pb->end()); // Appends newInst to pb 286509467b48Spatrick 286609467b48Spatrick becomes: 286709467b48Spatrick 286809467b48Spatrick .. code-block:: c++ 286909467b48Spatrick 287009467b48Spatrick BasicBlock *pb = ...; 287109467b48Spatrick auto *newInst = new Instruction(..., pb); 287209467b48Spatrick 287309467b48Spatrick which is much cleaner, especially if you are creating long instruction 287409467b48Spatrick streams. 287509467b48Spatrick 287609467b48Spatrick* Insertion using an instance of ``IRBuilder`` 287709467b48Spatrick 287809467b48Spatrick Inserting several ``Instruction``\ s can be quite laborious using the previous 287909467b48Spatrick methods. The ``IRBuilder`` is a convenience class that can be used to add 288009467b48Spatrick several instructions to the end of a ``BasicBlock`` or before a particular 288109467b48Spatrick ``Instruction``. It also supports constant folding and renaming named 288209467b48Spatrick registers (see ``IRBuilder``'s template arguments). 288309467b48Spatrick 288409467b48Spatrick The example below demonstrates a very simple use of the ``IRBuilder`` where 288509467b48Spatrick three instructions are inserted before the instruction ``pi``. The first two 288609467b48Spatrick instructions are Call instructions and third instruction multiplies the return 288709467b48Spatrick value of the two calls. 288809467b48Spatrick 288909467b48Spatrick .. code-block:: c++ 289009467b48Spatrick 289109467b48Spatrick Instruction *pi = ...; 289209467b48Spatrick IRBuilder<> Builder(pi); 289309467b48Spatrick CallInst* callOne = Builder.CreateCall(...); 289409467b48Spatrick CallInst* callTwo = Builder.CreateCall(...); 289509467b48Spatrick Value* result = Builder.CreateMul(callOne, callTwo); 289609467b48Spatrick 289709467b48Spatrick The example below is similar to the above example except that the created 289809467b48Spatrick ``IRBuilder`` inserts instructions at the end of the ``BasicBlock`` ``pb``. 289909467b48Spatrick 290009467b48Spatrick .. code-block:: c++ 290109467b48Spatrick 290209467b48Spatrick BasicBlock *pb = ...; 290309467b48Spatrick IRBuilder<> Builder(pb); 290409467b48Spatrick CallInst* callOne = Builder.CreateCall(...); 290509467b48Spatrick CallInst* callTwo = Builder.CreateCall(...); 290609467b48Spatrick Value* result = Builder.CreateMul(callOne, callTwo); 290709467b48Spatrick 290809467b48Spatrick See :doc:`tutorial/LangImpl03` for a practical use of the ``IRBuilder``. 290909467b48Spatrick 291009467b48Spatrick 291109467b48Spatrick.. _schanges_deleting: 291209467b48Spatrick 291309467b48SpatrickDeleting Instructions 291409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^ 291509467b48Spatrick 291609467b48SpatrickDeleting an instruction from an existing sequence of instructions that form a 291709467b48SpatrickBasicBlock_ is very straight-forward: just call the instruction's 291809467b48Spatrick``eraseFromParent()`` method. For example: 291909467b48Spatrick 292009467b48Spatrick.. code-block:: c++ 292109467b48Spatrick 292209467b48Spatrick Instruction *I = .. ; 292309467b48Spatrick I->eraseFromParent(); 292409467b48Spatrick 292509467b48SpatrickThis unlinks the instruction from its containing basic block and deletes it. If 292609467b48Spatrickyou'd just like to unlink the instruction from its containing basic block but 292709467b48Spatricknot delete it, you can use the ``removeFromParent()`` method. 292809467b48Spatrick 292909467b48Spatrick.. _schanges_replacing: 293009467b48Spatrick 293109467b48SpatrickReplacing an Instruction with another Value 293209467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 293309467b48Spatrick 293409467b48SpatrickReplacing individual instructions 293509467b48Spatrick""""""""""""""""""""""""""""""""" 293609467b48Spatrick 293709467b48SpatrickIncluding "`llvm/Transforms/Utils/BasicBlockUtils.h 2938097a140dSpatrick<https://llvm.org/doxygen/BasicBlockUtils_8h_source.html>`_" permits use of two 293909467b48Spatrickvery useful replace functions: ``ReplaceInstWithValue`` and 294009467b48Spatrick``ReplaceInstWithInst``. 294109467b48Spatrick 294209467b48Spatrick.. _schanges_deleting_sub: 294309467b48Spatrick 294409467b48SpatrickDeleting Instructions 294509467b48Spatrick""""""""""""""""""""" 294609467b48Spatrick 294709467b48Spatrick* ``ReplaceInstWithValue`` 294809467b48Spatrick 294909467b48Spatrick This function replaces all uses of a given instruction with a value, and then 295009467b48Spatrick removes the original instruction. The following example illustrates the 295109467b48Spatrick replacement of the result of a particular ``AllocaInst`` that allocates memory 295209467b48Spatrick for a single integer with a null pointer to an integer. 295309467b48Spatrick 295409467b48Spatrick .. code-block:: c++ 295509467b48Spatrick 295609467b48Spatrick AllocaInst* instToReplace = ...; 295709467b48Spatrick BasicBlock::iterator ii(instToReplace); 295809467b48Spatrick 2959*d415bd75Srobert ReplaceInstWithValue(instToReplace->getParent(), ii, 296009467b48Spatrick Constant::getNullValue(PointerType::getUnqual(Type::Int32Ty))); 296109467b48Spatrick 296209467b48Spatrick* ``ReplaceInstWithInst`` 296309467b48Spatrick 296409467b48Spatrick This function replaces a particular instruction with another instruction, 296509467b48Spatrick inserting the new instruction into the basic block at the location where the 296609467b48Spatrick old instruction was, and replacing any uses of the old instruction with the 296709467b48Spatrick new instruction. The following example illustrates the replacement of one 296809467b48Spatrick ``AllocaInst`` with another. 296909467b48Spatrick 297009467b48Spatrick .. code-block:: c++ 297109467b48Spatrick 297209467b48Spatrick AllocaInst* instToReplace = ...; 297309467b48Spatrick BasicBlock::iterator ii(instToReplace); 297409467b48Spatrick 2975*d415bd75Srobert ReplaceInstWithInst(instToReplace->getParent(), ii, 297609467b48Spatrick new AllocaInst(Type::Int32Ty, 0, "ptrToReplacedInt")); 297709467b48Spatrick 297809467b48Spatrick 297909467b48SpatrickReplacing multiple uses of Users and Values 298009467b48Spatrick""""""""""""""""""""""""""""""""""""""""""" 298109467b48Spatrick 298209467b48SpatrickYou can use ``Value::replaceAllUsesWith`` and ``User::replaceUsesOfWith`` to 298309467b48Spatrickchange more than one use at a time. See the doxygen documentation for the 2984097a140dSpatrick`Value Class <https://llvm.org/doxygen/classllvm_1_1Value.html>`_ and `User Class 2985097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1User.html>`_, respectively, for more 298609467b48Spatrickinformation. 298709467b48Spatrick 298809467b48Spatrick.. _schanges_deletingGV: 298909467b48Spatrick 299009467b48SpatrickDeleting GlobalVariables 299109467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^ 299209467b48Spatrick 299309467b48SpatrickDeleting a global variable from a module is just as easy as deleting an 299409467b48SpatrickInstruction. First, you must have a pointer to the global variable that you 299509467b48Spatrickwish to delete. You use this pointer to erase it from its parent, the module. 299609467b48SpatrickFor example: 299709467b48Spatrick 299809467b48Spatrick.. code-block:: c++ 299909467b48Spatrick 300009467b48Spatrick GlobalVariable *GV = .. ; 300109467b48Spatrick 300209467b48Spatrick GV->eraseFromParent(); 300309467b48Spatrick 300409467b48Spatrick 300509467b48Spatrick.. _threading: 300609467b48Spatrick 300709467b48SpatrickThreads and LLVM 300809467b48Spatrick================ 300909467b48Spatrick 301009467b48SpatrickThis section describes the interaction of the LLVM APIs with multithreading, 301109467b48Spatrickboth on the part of client applications, and in the JIT, in the hosted 301209467b48Spatrickapplication. 301309467b48Spatrick 301409467b48SpatrickNote that LLVM's support for multithreading is still relatively young. Up 301509467b48Spatrickthrough version 2.5, the execution of threaded hosted applications was 301609467b48Spatricksupported, but not threaded client access to the APIs. While this use case is 301709467b48Spatricknow supported, clients *must* adhere to the guidelines specified below to ensure 301809467b48Spatrickproper operation in multithreaded mode. 301909467b48Spatrick 302009467b48SpatrickNote that, on Unix-like platforms, LLVM requires the presence of GCC's atomic 302109467b48Spatrickintrinsics in order to support threaded operation. If you need a 3022097a140dSpatrickmultithreading-capable LLVM on a platform without a suitably modern system 302309467b48Spatrickcompiler, consider compiling LLVM and LLVM-GCC in single-threaded mode, and 302409467b48Spatrickusing the resultant compiler to build a copy of LLVM with multithreading 302509467b48Spatricksupport. 302609467b48Spatrick 302709467b48Spatrick.. _shutdown: 302809467b48Spatrick 302909467b48SpatrickEnding Execution with ``llvm_shutdown()`` 303009467b48Spatrick----------------------------------------- 303109467b48Spatrick 303209467b48SpatrickWhen you are done using the LLVM APIs, you should call ``llvm_shutdown()`` to 303309467b48Spatrickdeallocate memory used for internal structures. 303409467b48Spatrick 303509467b48Spatrick.. _managedstatic: 303609467b48Spatrick 303709467b48SpatrickLazy Initialization with ``ManagedStatic`` 303809467b48Spatrick------------------------------------------ 303909467b48Spatrick 304009467b48Spatrick``ManagedStatic`` is a utility class in LLVM used to implement static 304109467b48Spatrickinitialization of static resources, such as the global type tables. In a 304209467b48Spatricksingle-threaded environment, it implements a simple lazy initialization scheme. 304309467b48SpatrickWhen LLVM is compiled with support for multi-threading, however, it uses 304409467b48Spatrickdouble-checked locking to implement thread-safe lazy initialization. 304509467b48Spatrick 304609467b48Spatrick.. _llvmcontext: 304709467b48Spatrick 304809467b48SpatrickAchieving Isolation with ``LLVMContext`` 304909467b48Spatrick---------------------------------------- 305009467b48Spatrick 305109467b48Spatrick``LLVMContext`` is an opaque class in the LLVM API which clients can use to 305209467b48Spatrickoperate multiple, isolated instances of LLVM concurrently within the same 305309467b48Spatrickaddress space. For instance, in a hypothetical compile-server, the compilation 305409467b48Spatrickof an individual translation unit is conceptually independent from all the 305509467b48Spatrickothers, and it would be desirable to be able to compile incoming translation 305609467b48Spatrickunits concurrently on independent server threads. Fortunately, ``LLVMContext`` 305709467b48Spatrickexists to enable just this kind of scenario! 305809467b48Spatrick 305909467b48SpatrickConceptually, ``LLVMContext`` provides isolation. Every LLVM entity 306009467b48Spatrick(``Module``\ s, ``Value``\ s, ``Type``\ s, ``Constant``\ s, etc.) in LLVM's 306109467b48Spatrickin-memory IR belongs to an ``LLVMContext``. Entities in different contexts 306209467b48Spatrick*cannot* interact with each other: ``Module``\ s in different contexts cannot be 306309467b48Spatricklinked together, ``Function``\ s cannot be added to ``Module``\ s in different 306409467b48Spatrickcontexts, etc. What this means is that is safe to compile on multiple 306509467b48Spatrickthreads simultaneously, as long as no two threads operate on entities within the 306609467b48Spatricksame context. 306709467b48Spatrick 306809467b48SpatrickIn practice, very few places in the API require the explicit specification of a 306909467b48Spatrick``LLVMContext``, other than the ``Type`` creation/lookup APIs. Because every 307009467b48Spatrick``Type`` carries a reference to its owning context, most other entities can 307109467b48Spatrickdetermine what context they belong to by looking at their own ``Type``. If you 307209467b48Spatrickare adding new entities to LLVM IR, please try to maintain this interface 307309467b48Spatrickdesign. 307409467b48Spatrick 307509467b48Spatrick.. _jitthreading: 307609467b48Spatrick 307709467b48SpatrickThreads and the JIT 307809467b48Spatrick------------------- 307909467b48Spatrick 308009467b48SpatrickLLVM's "eager" JIT compiler is safe to use in threaded programs. Multiple 308109467b48Spatrickthreads can call ``ExecutionEngine::getPointerToFunction()`` or 308209467b48Spatrick``ExecutionEngine::runFunction()`` concurrently, and multiple threads can run 308309467b48Spatrickcode output by the JIT concurrently. The user must still ensure that only one 308409467b48Spatrickthread accesses IR in a given ``LLVMContext`` while another thread might be 308509467b48Spatrickmodifying it. One way to do that is to always hold the JIT lock while accessing 308609467b48SpatrickIR outside the JIT (the JIT *modifies* the IR by adding ``CallbackVH``\ s). 308709467b48SpatrickAnother way is to only call ``getPointerToFunction()`` from the 308809467b48Spatrick``LLVMContext``'s thread. 308909467b48Spatrick 309009467b48SpatrickWhen the JIT is configured to compile lazily (using 309109467b48Spatrick``ExecutionEngine::DisableLazyCompilation(false)``), there is currently a `race 309209467b48Spatrickcondition <https://bugs.llvm.org/show_bug.cgi?id=5184>`_ in updating call sites 309309467b48Spatrickafter a function is lazily-jitted. It's still possible to use the lazy JIT in a 309409467b48Spatrickthreaded program if you ensure that only one thread at a time can call any 309509467b48Spatrickparticular lazy stub and that the JIT lock guards any IR access, but we suggest 309609467b48Spatrickusing only the eager JIT in threaded programs. 309709467b48Spatrick 309809467b48Spatrick.. _advanced: 309909467b48Spatrick 310009467b48SpatrickAdvanced Topics 310109467b48Spatrick=============== 310209467b48Spatrick 310309467b48SpatrickThis section describes some of the advanced or obscure API's that most clients 310409467b48Spatrickdo not need to be aware of. These API's tend manage the inner workings of the 310509467b48SpatrickLLVM system, and only need to be accessed in unusual circumstances. 310609467b48Spatrick 310709467b48Spatrick.. _SymbolTable: 310809467b48Spatrick 310909467b48SpatrickThe ``ValueSymbolTable`` class 311009467b48Spatrick------------------------------ 311109467b48Spatrick 311209467b48SpatrickThe ``ValueSymbolTable`` (`doxygen 3113097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1ValueSymbolTable.html>`__) class provides 311409467b48Spatricka symbol table that the :ref:`Function <c_Function>` and Module_ classes use for 311509467b48Spatricknaming value definitions. The symbol table can provide a name for any Value_. 311609467b48Spatrick 311709467b48SpatrickNote that the ``SymbolTable`` class should not be directly accessed by most 311809467b48Spatrickclients. It should only be used when iteration over the symbol table names 311909467b48Spatrickthemselves are required, which is very special purpose. Note that not all LLVM 312009467b48SpatrickValue_\ s have names, and those without names (i.e. they have an empty name) do 312109467b48Spatricknot exist in the symbol table. 312209467b48Spatrick 312309467b48SpatrickSymbol tables support iteration over the values in the symbol table with 312409467b48Spatrick``begin/end/iterator`` and supports querying to see if a specific name is in the 312509467b48Spatricksymbol table (with ``lookup``). The ``ValueSymbolTable`` class exposes no 312609467b48Spatrickpublic mutator methods, instead, simply call ``setName`` on a value, which will 312709467b48Spatrickautoinsert it into the appropriate symbol table. 312809467b48Spatrick 312909467b48Spatrick.. _UserLayout: 313009467b48Spatrick 313109467b48SpatrickThe ``User`` and owned ``Use`` classes' memory layout 313209467b48Spatrick----------------------------------------------------- 313309467b48Spatrick 3134097a140dSpatrickThe ``User`` (`doxygen <https://llvm.org/doxygen/classllvm_1_1User.html>`__) 313509467b48Spatrickclass provides a basis for expressing the ownership of ``User`` towards other 3136097a140dSpatrick`Value instance <https://llvm.org/doxygen/classllvm_1_1Value.html>`_\ s. The 3137097a140dSpatrick``Use`` (`doxygen <https://llvm.org/doxygen/classllvm_1_1Use.html>`__) helper 313809467b48Spatrickclass is employed to do the bookkeeping and to facilitate *O(1)* addition and 313909467b48Spatrickremoval. 314009467b48Spatrick 314109467b48Spatrick.. _Use2User: 314209467b48Spatrick 314309467b48SpatrickInteraction and relationship between ``User`` and ``Use`` objects 314409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 314509467b48Spatrick 314609467b48SpatrickA subclass of ``User`` can choose between incorporating its ``Use`` objects or 314709467b48Spatrickrefer to them out-of-line by means of a pointer. A mixed variant (some ``Use`` 314809467b48Spatricks inline others hung off) is impractical and breaks the invariant that the 314909467b48Spatrick``Use`` objects belonging to the same ``User`` form a contiguous array. 315009467b48Spatrick 315109467b48SpatrickWe have 2 different layouts in the ``User`` (sub)classes: 315209467b48Spatrick 315309467b48Spatrick* Layout a) 315409467b48Spatrick 315509467b48Spatrick The ``Use`` object(s) are inside (resp. at fixed offset) of the ``User`` 315609467b48Spatrick object and there are a fixed number of them. 315709467b48Spatrick 315809467b48Spatrick* Layout b) 315909467b48Spatrick 316009467b48Spatrick The ``Use`` object(s) are referenced by a pointer to an array from the 316109467b48Spatrick ``User`` object and there may be a variable number of them. 316209467b48Spatrick 316309467b48SpatrickAs of v2.4 each layout still possesses a direct pointer to the start of the 316409467b48Spatrickarray of ``Use``\ s. Though not mandatory for layout a), we stick to this 316509467b48Spatrickredundancy for the sake of simplicity. The ``User`` object also stores the 316609467b48Spatricknumber of ``Use`` objects it has. (Theoretically this information can also be 316709467b48Spatrickcalculated given the scheme presented below.) 316809467b48Spatrick 316909467b48SpatrickSpecial forms of allocation operators (``operator new``) enforce the following 317009467b48Spatrickmemory layouts: 317109467b48Spatrick 317209467b48Spatrick* Layout a) is modelled by prepending the ``User`` object by the ``Use[]`` 317309467b48Spatrick array. 317409467b48Spatrick 317509467b48Spatrick .. code-block:: none 317609467b48Spatrick 317709467b48Spatrick ...---.---.---.---.-------... 317809467b48Spatrick | P | P | P | P | User 317909467b48Spatrick '''---'---'---'---'-------''' 318009467b48Spatrick 318109467b48Spatrick* Layout b) is modelled by pointing at the ``Use[]`` array. 318209467b48Spatrick 318309467b48Spatrick .. code-block:: none 318409467b48Spatrick 318509467b48Spatrick .-------... 318609467b48Spatrick | User 318709467b48Spatrick '-------''' 318809467b48Spatrick | 318909467b48Spatrick v 319009467b48Spatrick .---.---.---.---... 319109467b48Spatrick | P | P | P | P | 319209467b48Spatrick '---'---'---'---''' 319309467b48Spatrick 319409467b48Spatrick*(In the above figures* '``P``' *stands for the* ``Use**`` *that is stored in 319509467b48Spatrickeach* ``Use`` *object in the member* ``Use::Prev`` *)* 319609467b48Spatrick 319709467b48Spatrick.. _polymorphism: 319809467b48Spatrick 3199097a140dSpatrickDesigning Type Hierarchies and Polymorphic Interfaces 320009467b48Spatrick----------------------------------------------------- 320109467b48Spatrick 320209467b48SpatrickThere are two different design patterns that tend to result in the use of 320309467b48Spatrickvirtual dispatch for methods in a type hierarchy in C++ programs. The first is 320409467b48Spatricka genuine type hierarchy where different types in the hierarchy model 320509467b48Spatricka specific subset of the functionality and semantics, and these types nest 320609467b48Spatrickstrictly within each other. Good examples of this can be seen in the ``Value`` 320709467b48Spatrickor ``Type`` type hierarchies. 320809467b48Spatrick 320909467b48SpatrickA second is the desire to dispatch dynamically across a collection of 321009467b48Spatrickpolymorphic interface implementations. This latter use case can be modeled with 321109467b48Spatrickvirtual dispatch and inheritance by defining an abstract interface base class 321209467b48Spatrickwhich all implementations derive from and override. However, this 321309467b48Spatrickimplementation strategy forces an **"is-a"** relationship to exist that is not 321409467b48Spatrickactually meaningful. There is often not some nested hierarchy of useful 321509467b48Spatrickgeneralizations which code might interact with and move up and down. Instead, 321609467b48Spatrickthere is a singular interface which is dispatched across a range of 321709467b48Spatrickimplementations. 321809467b48Spatrick 321909467b48SpatrickThe preferred implementation strategy for the second use case is that of 322009467b48Spatrickgeneric programming (sometimes called "compile-time duck typing" or "static 322109467b48Spatrickpolymorphism"). For example, a template over some type parameter ``T`` can be 322209467b48Spatrickinstantiated across any particular implementation that conforms to the 322309467b48Spatrickinterface or *concept*. A good example here is the highly generic properties of 322409467b48Spatrickany type which models a node in a directed graph. LLVM models these primarily 322509467b48Spatrickthrough templates and generic programming. Such templates include the 322609467b48Spatrick``LoopInfoBase`` and ``DominatorTreeBase``. When this type of polymorphism 322709467b48Spatricktruly needs **dynamic** dispatch you can generalize it using a technique 322809467b48Spatrickcalled *concept-based polymorphism*. This pattern emulates the interfaces and 322909467b48Spatrickbehaviors of templates using a very limited form of virtual dispatch for type 323009467b48Spatrickerasure inside its implementation. You can find examples of this technique in 323109467b48Spatrickthe ``PassManager.h`` system, and there is a more detailed introduction to it 323209467b48Spatrickby Sean Parent in several of his talks and papers: 323309467b48Spatrick 323409467b48Spatrick#. `Inheritance Is The Base Class of Evil 323509467b48Spatrick <http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil>`_ 323609467b48Spatrick - The GoingNative 2013 talk describing this technique, and probably the best 323709467b48Spatrick place to start. 323809467b48Spatrick#. `Value Semantics and Concepts-based Polymorphism 323909467b48Spatrick <http://www.youtube.com/watch?v=_BpMYeUFXv8>`_ - The C++Now! 2012 talk 324009467b48Spatrick describing this technique in more detail. 324109467b48Spatrick#. `Sean Parent's Papers and Presentations 324209467b48Spatrick <http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations>`_ 3243097a140dSpatrick - A GitHub project full of links to slides, video, and sometimes code. 324409467b48Spatrick 324509467b48SpatrickWhen deciding between creating a type hierarchy (with either tagged or virtual 324609467b48Spatrickdispatch) and using templates or concepts-based polymorphism, consider whether 324709467b48Spatrickthere is some refinement of an abstract base class which is a semantically 324809467b48Spatrickmeaningful type on an interface boundary. If anything more refined than the 324909467b48Spatrickroot abstract interface is meaningless to talk about as a partial extension of 325009467b48Spatrickthe semantic model, then your use case likely fits better with polymorphism and 325109467b48Spatrickyou should avoid using virtual dispatch. However, there may be some exigent 325209467b48Spatrickcircumstances that require one technique or the other to be used. 325309467b48Spatrick 325409467b48SpatrickIf you do need to introduce a type hierarchy, we prefer to use explicitly 325509467b48Spatrickclosed type hierarchies with manual tagged dispatch and/or RTTI rather than the 325609467b48Spatrickopen inheritance model and virtual dispatch that is more common in C++ code. 325709467b48SpatrickThis is because LLVM rarely encourages library consumers to extend its core 325809467b48Spatricktypes, and leverages the closed and tag-dispatched nature of its hierarchies to 325909467b48Spatrickgenerate significantly more efficient code. We have also found that a large 326009467b48Spatrickamount of our usage of type hierarchies fits better with tag-based pattern 326109467b48Spatrickmatching rather than dynamic dispatch across a common interface. Within LLVM we 326209467b48Spatrickhave built custom helpers to facilitate this design. See this document's 326309467b48Spatricksection on :ref:`isa and dyn_cast <isa>` and our :doc:`detailed document 326409467b48Spatrick<HowToSetUpLLVMStyleRTTI>` which describes how you can implement this 326509467b48Spatrickpattern for use with the LLVM helpers. 326609467b48Spatrick 326709467b48Spatrick.. _abi_breaking_checks: 326809467b48Spatrick 326909467b48SpatrickABI Breaking Checks 327009467b48Spatrick------------------- 327109467b48Spatrick 327209467b48SpatrickChecks and asserts that alter the LLVM C++ ABI are predicated on the 327309467b48Spatrickpreprocessor symbol `LLVM_ENABLE_ABI_BREAKING_CHECKS` -- LLVM 327409467b48Spatricklibraries built with `LLVM_ENABLE_ABI_BREAKING_CHECKS` are not ABI 327509467b48Spatrickcompatible LLVM libraries built without it defined. By default, 327609467b48Spatrickturning on assertions also turns on `LLVM_ENABLE_ABI_BREAKING_CHECKS` 327709467b48Spatrickso a default +Asserts build is not ABI compatible with a 327809467b48Spatrickdefault -Asserts build. Clients that want ABI compatibility 327909467b48Spatrickbetween +Asserts and -Asserts builds should use the CMake build system 328009467b48Spatrickto set `LLVM_ENABLE_ABI_BREAKING_CHECKS` independently 328109467b48Spatrickof `LLVM_ENABLE_ASSERTIONS`. 328209467b48Spatrick 328309467b48Spatrick.. _coreclasses: 328409467b48Spatrick 328509467b48SpatrickThe Core LLVM Class Hierarchy Reference 328609467b48Spatrick======================================= 328709467b48Spatrick 328809467b48Spatrick``#include "llvm/IR/Type.h"`` 328909467b48Spatrick 3290097a140dSpatrickheader source: `Type.h <https://llvm.org/doxygen/Type_8h_source.html>`_ 329109467b48Spatrick 3292097a140dSpatrickdoxygen info: `Type Classes <https://llvm.org/doxygen/classllvm_1_1Type.html>`_ 329309467b48Spatrick 329409467b48SpatrickThe Core LLVM classes are the primary means of representing the program being 329509467b48Spatrickinspected or transformed. The core LLVM classes are defined in header files in 329609467b48Spatrickthe ``include/llvm/IR`` directory, and implemented in the ``lib/IR`` 329709467b48Spatrickdirectory. It's worth noting that, for historical reasons, this library is 329809467b48Spatrickcalled ``libLLVMCore.so``, not ``libLLVMIR.so`` as you might expect. 329909467b48Spatrick 330009467b48Spatrick.. _Type: 330109467b48Spatrick 330209467b48SpatrickThe Type class and Derived Types 330309467b48Spatrick-------------------------------- 330409467b48Spatrick 330509467b48Spatrick``Type`` is a superclass of all type classes. Every ``Value`` has a ``Type``. 330609467b48Spatrick``Type`` cannot be instantiated directly but only through its subclasses. 330709467b48SpatrickCertain primitive types (``VoidType``, ``LabelType``, ``FloatType`` and 330809467b48Spatrick``DoubleType``) have hidden subclasses. They are hidden because they offer no 330909467b48Spatrickuseful functionality beyond what the ``Type`` class offers except to distinguish 331009467b48Spatrickthemselves from other subclasses of ``Type``. 331109467b48Spatrick 331209467b48SpatrickAll other types are subclasses of ``DerivedType``. Types can be named, but this 331309467b48Spatrickis not a requirement. There exists exactly one instance of a given shape at any 331409467b48Spatrickone time. This allows type equality to be performed with address equality of 331509467b48Spatrickthe Type Instance. That is, given two ``Type*`` values, the types are identical 331609467b48Spatrickif the pointers are identical. 331709467b48Spatrick 331809467b48Spatrick.. _m_Type: 331909467b48Spatrick 332009467b48SpatrickImportant Public Methods 332109467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^ 332209467b48Spatrick 332309467b48Spatrick* ``bool isIntegerTy() const``: Returns true for any integer type. 332409467b48Spatrick 332509467b48Spatrick* ``bool isFloatingPointTy()``: Return true if this is one of the five 332609467b48Spatrick floating point types. 332709467b48Spatrick 332809467b48Spatrick* ``bool isSized()``: Return true if the type has known size. Things 332909467b48Spatrick that don't have a size are abstract types, labels and void. 333009467b48Spatrick 333109467b48Spatrick.. _derivedtypes: 333209467b48Spatrick 333309467b48SpatrickImportant Derived Types 333409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^ 333509467b48Spatrick 333609467b48Spatrick``IntegerType`` 333709467b48Spatrick Subclass of DerivedType that represents integer types of any bit width. Any 333809467b48Spatrick bit width between ``IntegerType::MIN_INT_BITS`` (1) and 333909467b48Spatrick ``IntegerType::MAX_INT_BITS`` (~8 million) can be represented. 334009467b48Spatrick 334109467b48Spatrick * ``static const IntegerType* get(unsigned NumBits)``: get an integer 334209467b48Spatrick type of a specific bit width. 334309467b48Spatrick 334409467b48Spatrick * ``unsigned getBitWidth() const``: Get the bit width of an integer type. 334509467b48Spatrick 334609467b48Spatrick``SequentialType`` 334709467b48Spatrick This is subclassed by ArrayType and VectorType. 334809467b48Spatrick 334909467b48Spatrick * ``const Type * getElementType() const``: Returns the type of each 335009467b48Spatrick of the elements in the sequential type. 335109467b48Spatrick 335209467b48Spatrick * ``uint64_t getNumElements() const``: Returns the number of elements 335309467b48Spatrick in the sequential type. 335409467b48Spatrick 335509467b48Spatrick``ArrayType`` 335609467b48Spatrick This is a subclass of SequentialType and defines the interface for array 335709467b48Spatrick types. 335809467b48Spatrick 335909467b48Spatrick``PointerType`` 336009467b48Spatrick Subclass of Type for pointer types. 336109467b48Spatrick 336209467b48Spatrick``VectorType`` 336309467b48Spatrick Subclass of SequentialType for vector types. A vector type is similar to an 336409467b48Spatrick ArrayType but is distinguished because it is a first class type whereas 336509467b48Spatrick ArrayType is not. Vector types are used for vector operations and are usually 336609467b48Spatrick small vectors of an integer or floating point type. 336709467b48Spatrick 336809467b48Spatrick``StructType`` 336909467b48Spatrick Subclass of DerivedTypes for struct types. 337009467b48Spatrick 337109467b48Spatrick.. _FunctionType: 337209467b48Spatrick 337309467b48Spatrick``FunctionType`` 337409467b48Spatrick Subclass of DerivedTypes for function types. 337509467b48Spatrick 337609467b48Spatrick * ``bool isVarArg() const``: Returns true if it's a vararg function. 337709467b48Spatrick 337809467b48Spatrick * ``const Type * getReturnType() const``: Returns the return type of the 337909467b48Spatrick function. 338009467b48Spatrick 338109467b48Spatrick * ``const Type * getParamType (unsigned i)``: Returns the type of the ith 338209467b48Spatrick parameter. 338309467b48Spatrick 338409467b48Spatrick * ``const unsigned getNumParams() const``: Returns the number of formal 338509467b48Spatrick parameters. 338609467b48Spatrick 338709467b48Spatrick.. _Module: 338809467b48Spatrick 338909467b48SpatrickThe ``Module`` class 339009467b48Spatrick-------------------- 339109467b48Spatrick 339209467b48Spatrick``#include "llvm/IR/Module.h"`` 339309467b48Spatrick 3394097a140dSpatrickheader source: `Module.h <https://llvm.org/doxygen/Module_8h_source.html>`_ 339509467b48Spatrick 3396097a140dSpatrickdoxygen info: `Module Class <https://llvm.org/doxygen/classllvm_1_1Module.html>`_ 339709467b48Spatrick 339809467b48SpatrickThe ``Module`` class represents the top level structure present in LLVM 339909467b48Spatrickprograms. An LLVM module is effectively either a translation unit of the 340009467b48Spatrickoriginal program or a combination of several translation units merged by the 340109467b48Spatricklinker. The ``Module`` class keeps track of a list of :ref:`Function 340209467b48Spatrick<c_Function>`\ s, a list of GlobalVariable_\ s, and a SymbolTable_. 340309467b48SpatrickAdditionally, it contains a few helpful member functions that try to make common 340409467b48Spatrickoperations easy. 340509467b48Spatrick 340609467b48Spatrick.. _m_Module: 340709467b48Spatrick 340809467b48SpatrickImportant Public Members of the ``Module`` class 340909467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 341009467b48Spatrick 341109467b48Spatrick* ``Module::Module(std::string name = "")`` 341209467b48Spatrick 341309467b48Spatrick Constructing a Module_ is easy. You can optionally provide a name for it 341409467b48Spatrick (probably based on the name of the translation unit). 341509467b48Spatrick 341609467b48Spatrick* | ``Module::iterator`` - Typedef for function list iterator 341709467b48Spatrick | ``Module::const_iterator`` - Typedef for const_iterator. 341809467b48Spatrick | ``begin()``, ``end()``, ``size()``, ``empty()`` 341909467b48Spatrick 342009467b48Spatrick These are forwarding methods that make it easy to access the contents of a 342109467b48Spatrick ``Module`` object's :ref:`Function <c_Function>` list. 342209467b48Spatrick 342309467b48Spatrick* ``Module::FunctionListType &getFunctionList()`` 342409467b48Spatrick 342509467b48Spatrick Returns the list of :ref:`Function <c_Function>`\ s. This is necessary to use 342609467b48Spatrick when you need to update the list or perform a complex action that doesn't have 342709467b48Spatrick a forwarding method. 342809467b48Spatrick 342909467b48Spatrick---------------- 343009467b48Spatrick 343109467b48Spatrick* | ``Module::global_iterator`` - Typedef for global variable list iterator 343209467b48Spatrick | ``Module::const_global_iterator`` - Typedef for const_iterator. 343309467b48Spatrick | ``global_begin()``, ``global_end()``, ``global_size()``, ``global_empty()`` 343409467b48Spatrick 343509467b48Spatrick These are forwarding methods that make it easy to access the contents of a 343609467b48Spatrick ``Module`` object's GlobalVariable_ list. 343709467b48Spatrick 343809467b48Spatrick* ``Module::GlobalListType &getGlobalList()`` 343909467b48Spatrick 344009467b48Spatrick Returns the list of GlobalVariable_\ s. This is necessary to use when you 344109467b48Spatrick need to update the list or perform a complex action that doesn't have a 344209467b48Spatrick forwarding method. 344309467b48Spatrick 344409467b48Spatrick---------------- 344509467b48Spatrick 344609467b48Spatrick* ``SymbolTable *getSymbolTable()`` 344709467b48Spatrick 344809467b48Spatrick Return a reference to the SymbolTable_ for this ``Module``. 344909467b48Spatrick 345009467b48Spatrick---------------- 345109467b48Spatrick 345209467b48Spatrick* ``Function *getFunction(StringRef Name) const`` 345309467b48Spatrick 345409467b48Spatrick Look up the specified function in the ``Module`` SymbolTable_. If it does not 345509467b48Spatrick exist, return ``null``. 345609467b48Spatrick 345709467b48Spatrick* ``FunctionCallee getOrInsertFunction(const std::string &Name, 345809467b48Spatrick const FunctionType *T)`` 345909467b48Spatrick 346009467b48Spatrick Look up the specified function in the ``Module`` SymbolTable_. If 346109467b48Spatrick it does not exist, add an external declaration for the function and 346209467b48Spatrick return it. Note that the function signature already present may not 346309467b48Spatrick match the requested signature. Thus, in order to enable the common 346409467b48Spatrick usage of passing the result directly to EmitCall, the return type is 346509467b48Spatrick a struct of ``{FunctionType *T, Constant *FunctionPtr}``, rather 346609467b48Spatrick than simply the ``Function*`` with potentially an unexpected 346709467b48Spatrick signature. 346809467b48Spatrick 346909467b48Spatrick* ``std::string getTypeName(const Type *Ty)`` 347009467b48Spatrick 347109467b48Spatrick If there is at least one entry in the SymbolTable_ for the specified Type_, 347209467b48Spatrick return it. Otherwise return the empty string. 347309467b48Spatrick 347409467b48Spatrick* ``bool addTypeName(const std::string &Name, const Type *Ty)`` 347509467b48Spatrick 347609467b48Spatrick Insert an entry in the SymbolTable_ mapping ``Name`` to ``Ty``. If there is 347709467b48Spatrick already an entry for this name, true is returned and the SymbolTable_ is not 347809467b48Spatrick modified. 347909467b48Spatrick 348009467b48Spatrick.. _Value: 348109467b48Spatrick 348209467b48SpatrickThe ``Value`` class 348309467b48Spatrick------------------- 348409467b48Spatrick 348509467b48Spatrick``#include "llvm/IR/Value.h"`` 348609467b48Spatrick 3487097a140dSpatrickheader source: `Value.h <https://llvm.org/doxygen/Value_8h_source.html>`_ 348809467b48Spatrick 3489097a140dSpatrickdoxygen info: `Value Class <https://llvm.org/doxygen/classllvm_1_1Value.html>`_ 349009467b48Spatrick 349109467b48SpatrickThe ``Value`` class is the most important class in the LLVM Source base. It 349209467b48Spatrickrepresents a typed value that may be used (among other things) as an operand to 349309467b48Spatrickan instruction. There are many different types of ``Value``\ s, such as 349409467b48SpatrickConstant_\ s, Argument_\ s. Even Instruction_\ s and :ref:`Function 349509467b48Spatrick<c_Function>`\ s are ``Value``\ s. 349609467b48Spatrick 349709467b48SpatrickA particular ``Value`` may be used many times in the LLVM representation for a 349809467b48Spatrickprogram. For example, an incoming argument to a function (represented with an 349909467b48Spatrickinstance of the Argument_ class) is "used" by every instruction in the function 350009467b48Spatrickthat references the argument. To keep track of this relationship, the ``Value`` 350109467b48Spatrickclass keeps a list of all of the ``User``\ s that is using it (the User_ class 350209467b48Spatrickis a base class for all nodes in the LLVM graph that can refer to ``Value``\ s). 350309467b48SpatrickThis use list is how LLVM represents def-use information in the program, and is 350409467b48Spatrickaccessible through the ``use_*`` methods, shown below. 350509467b48Spatrick 350609467b48SpatrickBecause LLVM is a typed representation, every LLVM ``Value`` is typed, and this 350709467b48SpatrickType_ is available through the ``getType()`` method. In addition, all LLVM 350809467b48Spatrickvalues can be named. The "name" of the ``Value`` is a symbolic string printed 350909467b48Spatrickin the LLVM code: 351009467b48Spatrick 351109467b48Spatrick.. code-block:: llvm 351209467b48Spatrick 351309467b48Spatrick %foo = add i32 1, 2 351409467b48Spatrick 351509467b48Spatrick.. _nameWarning: 351609467b48Spatrick 351709467b48SpatrickThe name of this instruction is "foo". **NOTE** that the name of any value may 351809467b48Spatrickbe missing (an empty string), so names should **ONLY** be used for debugging 351909467b48Spatrick(making the source code easier to read, debugging printouts), they should not be 352009467b48Spatrickused to keep track of values or map between them. For this purpose, use a 352109467b48Spatrick``std::map`` of pointers to the ``Value`` itself instead. 352209467b48Spatrick 352309467b48SpatrickOne important aspect of LLVM is that there is no distinction between an SSA 352409467b48Spatrickvariable and the operation that produces it. Because of this, any reference to 352509467b48Spatrickthe value produced by an instruction (or the value available as an incoming 352609467b48Spatrickargument, for example) is represented as a direct pointer to the instance of the 352709467b48Spatrickclass that represents this value. Although this may take some getting used to, 352809467b48Spatrickit simplifies the representation and makes it easier to manipulate. 352909467b48Spatrick 353009467b48Spatrick.. _m_Value: 353109467b48Spatrick 353209467b48SpatrickImportant Public Members of the ``Value`` class 353309467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 353409467b48Spatrick 353509467b48Spatrick* | ``Value::use_iterator`` - Typedef for iterator over the use-list 353609467b48Spatrick | ``Value::const_use_iterator`` - Typedef for const_iterator over the 353709467b48Spatrick use-list 353809467b48Spatrick | ``unsigned use_size()`` - Returns the number of users of the value. 353909467b48Spatrick | ``bool use_empty()`` - Returns true if there are no users. 354009467b48Spatrick | ``use_iterator use_begin()`` - Get an iterator to the start of the 354109467b48Spatrick use-list. 354209467b48Spatrick | ``use_iterator use_end()`` - Get an iterator to the end of the use-list. 354309467b48Spatrick | ``User *use_back()`` - Returns the last element in the list. 354409467b48Spatrick 354509467b48Spatrick These methods are the interface to access the def-use information in LLVM. 354609467b48Spatrick As with all other iterators in LLVM, the naming conventions follow the 354709467b48Spatrick conventions defined by the STL_. 354809467b48Spatrick 354909467b48Spatrick* ``Type *getType() const`` 355009467b48Spatrick This method returns the Type of the Value. 355109467b48Spatrick 355209467b48Spatrick* | ``bool hasName() const`` 355309467b48Spatrick | ``std::string getName() const`` 355409467b48Spatrick | ``void setName(const std::string &Name)`` 355509467b48Spatrick 355609467b48Spatrick This family of methods is used to access and assign a name to a ``Value``, be 355709467b48Spatrick aware of the :ref:`precaution above <nameWarning>`. 355809467b48Spatrick 355909467b48Spatrick* ``void replaceAllUsesWith(Value *V)`` 356009467b48Spatrick 356109467b48Spatrick This method traverses the use list of a ``Value`` changing all User_\ s of the 356209467b48Spatrick current value to refer to "``V``" instead. For example, if you detect that an 356309467b48Spatrick instruction always produces a constant value (for example through constant 356409467b48Spatrick folding), you can replace all uses of the instruction with the constant like 356509467b48Spatrick this: 356609467b48Spatrick 356709467b48Spatrick .. code-block:: c++ 356809467b48Spatrick 356909467b48Spatrick Inst->replaceAllUsesWith(ConstVal); 357009467b48Spatrick 357109467b48Spatrick.. _User: 357209467b48Spatrick 357309467b48SpatrickThe ``User`` class 357409467b48Spatrick------------------ 357509467b48Spatrick 357609467b48Spatrick``#include "llvm/IR/User.h"`` 357709467b48Spatrick 3578097a140dSpatrickheader source: `User.h <https://llvm.org/doxygen/User_8h_source.html>`_ 357909467b48Spatrick 3580097a140dSpatrickdoxygen info: `User Class <https://llvm.org/doxygen/classllvm_1_1User.html>`_ 358109467b48Spatrick 358209467b48SpatrickSuperclass: Value_ 358309467b48Spatrick 358409467b48SpatrickThe ``User`` class is the common base class of all LLVM nodes that may refer to 358509467b48Spatrick``Value``\ s. It exposes a list of "Operands" that are all of the ``Value``\ s 358609467b48Spatrickthat the User is referring to. The ``User`` class itself is a subclass of 358709467b48Spatrick``Value``. 358809467b48Spatrick 358909467b48SpatrickThe operands of a ``User`` point directly to the LLVM ``Value`` that it refers 359009467b48Spatrickto. Because LLVM uses Static Single Assignment (SSA) form, there can only be 359109467b48Spatrickone definition referred to, allowing this direct connection. This connection 359209467b48Spatrickprovides the use-def information in LLVM. 359309467b48Spatrick 359409467b48Spatrick.. _m_User: 359509467b48Spatrick 359609467b48SpatrickImportant Public Members of the ``User`` class 359709467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 359809467b48Spatrick 359909467b48SpatrickThe ``User`` class exposes the operand list in two ways: through an index access 360009467b48Spatrickinterface and through an iterator based interface. 360109467b48Spatrick 360209467b48Spatrick* | ``Value *getOperand(unsigned i)`` 360309467b48Spatrick | ``unsigned getNumOperands()`` 360409467b48Spatrick 360509467b48Spatrick These two methods expose the operands of the ``User`` in a convenient form for 360609467b48Spatrick direct access. 360709467b48Spatrick 360809467b48Spatrick* | ``User::op_iterator`` - Typedef for iterator over the operand list 360909467b48Spatrick | ``op_iterator op_begin()`` - Get an iterator to the start of the operand 361009467b48Spatrick list. 361109467b48Spatrick | ``op_iterator op_end()`` - Get an iterator to the end of the operand list. 361209467b48Spatrick 361309467b48Spatrick Together, these methods make up the iterator based interface to the operands 361409467b48Spatrick of a ``User``. 361509467b48Spatrick 361609467b48Spatrick 361709467b48Spatrick.. _Instruction: 361809467b48Spatrick 361909467b48SpatrickThe ``Instruction`` class 362009467b48Spatrick------------------------- 362109467b48Spatrick 362209467b48Spatrick``#include "llvm/IR/Instruction.h"`` 362309467b48Spatrick 362409467b48Spatrickheader source: `Instruction.h 3625097a140dSpatrick<https://llvm.org/doxygen/Instruction_8h_source.html>`_ 362609467b48Spatrick 362709467b48Spatrickdoxygen info: `Instruction Class 3628097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_ 362909467b48Spatrick 363009467b48SpatrickSuperclasses: User_, Value_ 363109467b48Spatrick 363209467b48SpatrickThe ``Instruction`` class is the common base class for all LLVM instructions. 363309467b48SpatrickIt provides only a few methods, but is a very commonly used class. The primary 363409467b48Spatrickdata tracked by the ``Instruction`` class itself is the opcode (instruction 363509467b48Spatricktype) and the parent BasicBlock_ the ``Instruction`` is embedded into. To 363609467b48Spatrickrepresent a specific type of instruction, one of many subclasses of 363709467b48Spatrick``Instruction`` are used. 363809467b48Spatrick 363909467b48SpatrickBecause the ``Instruction`` class subclasses the User_ class, its operands can 364009467b48Spatrickbe accessed in the same way as for other ``User``\ s (with the 364109467b48Spatrick``getOperand()``/``getNumOperands()`` and ``op_begin()``/``op_end()`` methods). 364209467b48SpatrickAn important file for the ``Instruction`` class is the ``llvm/Instruction.def`` 364309467b48Spatrickfile. This file contains some meta-data about the various different types of 364409467b48Spatrickinstructions in LLVM. It describes the enum values that are used as opcodes 364509467b48Spatrick(for example ``Instruction::Add`` and ``Instruction::ICmp``), as well as the 364609467b48Spatrickconcrete sub-classes of ``Instruction`` that implement the instruction (for 364709467b48Spatrickexample BinaryOperator_ and CmpInst_). Unfortunately, the use of macros in this 364809467b48Spatrickfile confuses doxygen, so these enum values don't show up correctly in the 3649097a140dSpatrick`doxygen output <https://llvm.org/doxygen/classllvm_1_1Instruction.html>`_. 365009467b48Spatrick 365109467b48Spatrick.. _s_Instruction: 365209467b48Spatrick 365309467b48SpatrickImportant Subclasses of the ``Instruction`` class 365409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 365509467b48Spatrick 365609467b48Spatrick.. _BinaryOperator: 365709467b48Spatrick 365809467b48Spatrick* ``BinaryOperator`` 365909467b48Spatrick 366009467b48Spatrick This subclasses represents all two operand instructions whose operands must be 366109467b48Spatrick the same type, except for the comparison instructions. 366209467b48Spatrick 366309467b48Spatrick.. _CastInst: 366409467b48Spatrick 366509467b48Spatrick* ``CastInst`` 366609467b48Spatrick This subclass is the parent of the 12 casting instructions. It provides 366709467b48Spatrick common operations on cast instructions. 366809467b48Spatrick 366909467b48Spatrick.. _CmpInst: 367009467b48Spatrick 367109467b48Spatrick* ``CmpInst`` 367209467b48Spatrick 367309467b48Spatrick This subclass represents the two comparison instructions, 3674097a140dSpatrick `ICmpInst <LangRef.html#i_icmp>`_ (integer operands), and 367509467b48Spatrick `FCmpInst <LangRef.html#i_fcmp>`_ (floating point operands). 367609467b48Spatrick 367709467b48Spatrick.. _m_Instruction: 367809467b48Spatrick 367909467b48SpatrickImportant Public Members of the ``Instruction`` class 368009467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 368109467b48Spatrick 368209467b48Spatrick* ``BasicBlock *getParent()`` 368309467b48Spatrick 368409467b48Spatrick Returns the BasicBlock_ that this 368509467b48Spatrick ``Instruction`` is embedded into. 368609467b48Spatrick 368709467b48Spatrick* ``bool mayWriteToMemory()`` 368809467b48Spatrick 368909467b48Spatrick Returns true if the instruction writes to memory, i.e. it is a ``call``, 369009467b48Spatrick ``free``, ``invoke``, or ``store``. 369109467b48Spatrick 369209467b48Spatrick* ``unsigned getOpcode()`` 369309467b48Spatrick 369409467b48Spatrick Returns the opcode for the ``Instruction``. 369509467b48Spatrick 369609467b48Spatrick* ``Instruction *clone() const`` 369709467b48Spatrick 369809467b48Spatrick Returns another instance of the specified instruction, identical in all ways 369909467b48Spatrick to the original except that the instruction has no parent (i.e. it's not 370009467b48Spatrick embedded into a BasicBlock_), and it has no name. 370109467b48Spatrick 370209467b48Spatrick.. _Constant: 370309467b48Spatrick 370409467b48SpatrickThe ``Constant`` class and subclasses 370509467b48Spatrick------------------------------------- 370609467b48Spatrick 370709467b48SpatrickConstant represents a base class for different types of constants. It is 370809467b48Spatricksubclassed by ConstantInt, ConstantArray, etc. for representing the various 370909467b48Spatricktypes of Constants. GlobalValue_ is also a subclass, which represents the 371009467b48Spatrickaddress of a global variable or function. 371109467b48Spatrick 371209467b48Spatrick.. _s_Constant: 371309467b48Spatrick 371409467b48SpatrickImportant Subclasses of Constant 371509467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 371609467b48Spatrick 371709467b48Spatrick* ConstantInt : This subclass of Constant represents an integer constant of 371809467b48Spatrick any width. 371909467b48Spatrick 372009467b48Spatrick * ``const APInt& getValue() const``: Returns the underlying 372109467b48Spatrick value of this constant, an APInt value. 372209467b48Spatrick 372309467b48Spatrick * ``int64_t getSExtValue() const``: Converts the underlying APInt value to an 372409467b48Spatrick int64_t via sign extension. If the value (not the bit width) of the APInt 372509467b48Spatrick is too large to fit in an int64_t, an assertion will result. For this 372609467b48Spatrick reason, use of this method is discouraged. 372709467b48Spatrick 372809467b48Spatrick * ``uint64_t getZExtValue() const``: Converts the underlying APInt value 372909467b48Spatrick to a uint64_t via zero extension. IF the value (not the bit width) of the 373009467b48Spatrick APInt is too large to fit in a uint64_t, an assertion will result. For this 373109467b48Spatrick reason, use of this method is discouraged. 373209467b48Spatrick 373309467b48Spatrick * ``static ConstantInt* get(const APInt& Val)``: Returns the ConstantInt 373409467b48Spatrick object that represents the value provided by ``Val``. The type is implied 373509467b48Spatrick as the IntegerType that corresponds to the bit width of ``Val``. 373609467b48Spatrick 373709467b48Spatrick * ``static ConstantInt* get(const Type *Ty, uint64_t Val)``: Returns the 373809467b48Spatrick ConstantInt object that represents the value provided by ``Val`` for integer 373909467b48Spatrick type ``Ty``. 374009467b48Spatrick 374109467b48Spatrick* ConstantFP : This class represents a floating point constant. 374209467b48Spatrick 374309467b48Spatrick * ``double getValue() const``: Returns the underlying value of this constant. 374409467b48Spatrick 374509467b48Spatrick* ConstantArray : This represents a constant array. 374609467b48Spatrick 374709467b48Spatrick * ``const std::vector<Use> &getValues() const``: Returns a vector of 374809467b48Spatrick component constants that makeup this array. 374909467b48Spatrick 375009467b48Spatrick* ConstantStruct : This represents a constant struct. 375109467b48Spatrick 375209467b48Spatrick * ``const std::vector<Use> &getValues() const``: Returns a vector of 375309467b48Spatrick component constants that makeup this array. 375409467b48Spatrick 375509467b48Spatrick* GlobalValue : This represents either a global variable or a function. In 375609467b48Spatrick either case, the value is a constant fixed address (after linking). 375709467b48Spatrick 375809467b48Spatrick.. _GlobalValue: 375909467b48Spatrick 376009467b48SpatrickThe ``GlobalValue`` class 376109467b48Spatrick------------------------- 376209467b48Spatrick 376309467b48Spatrick``#include "llvm/IR/GlobalValue.h"`` 376409467b48Spatrick 376509467b48Spatrickheader source: `GlobalValue.h 3766097a140dSpatrick<https://llvm.org/doxygen/GlobalValue_8h_source.html>`_ 376709467b48Spatrick 376809467b48Spatrickdoxygen info: `GlobalValue Class 3769097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1GlobalValue.html>`_ 377009467b48Spatrick 377109467b48SpatrickSuperclasses: Constant_, User_, Value_ 377209467b48Spatrick 377309467b48SpatrickGlobal values ( GlobalVariable_\ s or :ref:`Function <c_Function>`\ s) are the 377409467b48Spatrickonly LLVM values that are visible in the bodies of all :ref:`Function 377509467b48Spatrick<c_Function>`\ s. Because they are visible at global scope, they are also 377609467b48Spatricksubject to linking with other globals defined in different translation units. 377709467b48SpatrickTo control the linking process, ``GlobalValue``\ s know their linkage rules. 377809467b48SpatrickSpecifically, ``GlobalValue``\ s know whether they have internal or external 377909467b48Spatricklinkage, as defined by the ``LinkageTypes`` enumeration. 378009467b48Spatrick 378109467b48SpatrickIf a ``GlobalValue`` has internal linkage (equivalent to being ``static`` in C), 378209467b48Spatrickit is not visible to code outside the current translation unit, and does not 378309467b48Spatrickparticipate in linking. If it has external linkage, it is visible to external 378409467b48Spatrickcode, and does participate in linking. In addition to linkage information, 378509467b48Spatrick``GlobalValue``\ s keep track of which Module_ they are currently part of. 378609467b48Spatrick 378709467b48SpatrickBecause ``GlobalValue``\ s are memory objects, they are always referred to by 378809467b48Spatricktheir **address**. As such, the Type_ of a global is always a pointer to its 378909467b48Spatrickcontents. It is important to remember this when using the ``GetElementPtrInst`` 379009467b48Spatrickinstruction because this pointer must be dereferenced first. For example, if 379109467b48Spatrickyou have a ``GlobalVariable`` (a subclass of ``GlobalValue)`` that is an array 379209467b48Spatrickof 24 ints, type ``[24 x i32]``, then the ``GlobalVariable`` is a pointer to 379309467b48Spatrickthat array. Although the address of the first element of this array and the 379409467b48Spatrickvalue of the ``GlobalVariable`` are the same, they have different types. The 379509467b48Spatrick``GlobalVariable``'s type is ``[24 x i32]``. The first element's type is 379609467b48Spatrick``i32.`` Because of this, accessing a global value requires you to dereference 379709467b48Spatrickthe pointer with ``GetElementPtrInst`` first, then its elements can be accessed. 379809467b48SpatrickThis is explained in the `LLVM Language Reference Manual 379909467b48Spatrick<LangRef.html#globalvars>`_. 380009467b48Spatrick 380109467b48Spatrick.. _m_GlobalValue: 380209467b48Spatrick 380309467b48SpatrickImportant Public Members of the ``GlobalValue`` class 380409467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 380509467b48Spatrick 380609467b48Spatrick* | ``bool hasInternalLinkage() const`` 380709467b48Spatrick | ``bool hasExternalLinkage() const`` 380809467b48Spatrick | ``void setInternalLinkage(bool HasInternalLinkage)`` 380909467b48Spatrick 381009467b48Spatrick These methods manipulate the linkage characteristics of the ``GlobalValue``. 381109467b48Spatrick 381209467b48Spatrick* ``Module *getParent()`` 381309467b48Spatrick 381409467b48Spatrick This returns the Module_ that the 381509467b48Spatrick GlobalValue is currently embedded into. 381609467b48Spatrick 381709467b48Spatrick.. _c_Function: 381809467b48Spatrick 381909467b48SpatrickThe ``Function`` class 382009467b48Spatrick---------------------- 382109467b48Spatrick 382209467b48Spatrick``#include "llvm/IR/Function.h"`` 382309467b48Spatrick 3824097a140dSpatrickheader source: `Function.h <https://llvm.org/doxygen/Function_8h_source.html>`_ 382509467b48Spatrick 382609467b48Spatrickdoxygen info: `Function Class 3827097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1Function.html>`_ 382809467b48Spatrick 382909467b48SpatrickSuperclasses: GlobalValue_, Constant_, User_, Value_ 383009467b48Spatrick 383109467b48SpatrickThe ``Function`` class represents a single procedure in LLVM. It is actually 383209467b48Spatrickone of the more complex classes in the LLVM hierarchy because it must keep track 383309467b48Spatrickof a large amount of data. The ``Function`` class keeps track of a list of 383409467b48SpatrickBasicBlock_\ s, a list of formal Argument_\ s, and a SymbolTable_. 383509467b48Spatrick 383609467b48SpatrickThe list of BasicBlock_\ s is the most commonly used part of ``Function`` 383709467b48Spatrickobjects. The list imposes an implicit ordering of the blocks in the function, 383809467b48Spatrickwhich indicate how the code will be laid out by the backend. Additionally, the 383909467b48Spatrickfirst BasicBlock_ is the implicit entry node for the ``Function``. It is not 384009467b48Spatricklegal in LLVM to explicitly branch to this initial block. There are no implicit 384109467b48Spatrickexit nodes, and in fact there may be multiple exit nodes from a single 384209467b48Spatrick``Function``. If the BasicBlock_ list is empty, this indicates that the 384309467b48Spatrick``Function`` is actually a function declaration: the actual body of the function 384409467b48Spatrickhasn't been linked in yet. 384509467b48Spatrick 384609467b48SpatrickIn addition to a list of BasicBlock_\ s, the ``Function`` class also keeps track 384709467b48Spatrickof the list of formal Argument_\ s that the function receives. This container 384809467b48Spatrickmanages the lifetime of the Argument_ nodes, just like the BasicBlock_ list does 384909467b48Spatrickfor the BasicBlock_\ s. 385009467b48Spatrick 385109467b48SpatrickThe SymbolTable_ is a very rarely used LLVM feature that is only used when you 385209467b48Spatrickhave to look up a value by name. Aside from that, the SymbolTable_ is used 385309467b48Spatrickinternally to make sure that there are not conflicts between the names of 385409467b48SpatrickInstruction_\ s, BasicBlock_\ s, or Argument_\ s in the function body. 385509467b48Spatrick 385609467b48SpatrickNote that ``Function`` is a GlobalValue_ and therefore also a Constant_. The 385709467b48Spatrickvalue of the function is its address (after linking) which is guaranteed to be 385809467b48Spatrickconstant. 385909467b48Spatrick 386009467b48Spatrick.. _m_Function: 386109467b48Spatrick 386209467b48SpatrickImportant Public Members of the ``Function`` 386309467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 386409467b48Spatrick 386509467b48Spatrick* ``Function(const FunctionType *Ty, LinkageTypes Linkage, 386609467b48Spatrick const std::string &N = "", Module* Parent = 0)`` 386709467b48Spatrick 386809467b48Spatrick Constructor used when you need to create new ``Function``\ s to add the 386909467b48Spatrick program. The constructor must specify the type of the function to create and 387009467b48Spatrick what type of linkage the function should have. The FunctionType_ argument 387109467b48Spatrick specifies the formal arguments and return value for the function. The same 387209467b48Spatrick FunctionType_ value can be used to create multiple functions. The ``Parent`` 387309467b48Spatrick argument specifies the Module in which the function is defined. If this 387409467b48Spatrick argument is provided, the function will automatically be inserted into that 387509467b48Spatrick module's list of functions. 387609467b48Spatrick 387709467b48Spatrick* ``bool isDeclaration()`` 387809467b48Spatrick 387909467b48Spatrick Return whether or not the ``Function`` has a body defined. If the function is 388009467b48Spatrick "external", it does not have a body, and thus must be resolved by linking with 388109467b48Spatrick a function defined in a different translation unit. 388209467b48Spatrick 388309467b48Spatrick* | ``Function::iterator`` - Typedef for basic block list iterator 388409467b48Spatrick | ``Function::const_iterator`` - Typedef for const_iterator. 3885*d415bd75Srobert | ``begin()``, ``end()``, ``size()``, ``empty()``, ``insert()``, 3886*d415bd75Srobert ``splice()``, ``erase()`` 388709467b48Spatrick 388809467b48Spatrick These are forwarding methods that make it easy to access the contents of a 388909467b48Spatrick ``Function`` object's BasicBlock_ list. 389009467b48Spatrick 389109467b48Spatrick* | ``Function::arg_iterator`` - Typedef for the argument list iterator 389209467b48Spatrick | ``Function::const_arg_iterator`` - Typedef for const_iterator. 389309467b48Spatrick | ``arg_begin()``, ``arg_end()``, ``arg_size()``, ``arg_empty()`` 389409467b48Spatrick 389509467b48Spatrick These are forwarding methods that make it easy to access the contents of a 389609467b48Spatrick ``Function`` object's Argument_ list. 389709467b48Spatrick 389809467b48Spatrick* ``Function::ArgumentListType &getArgumentList()`` 389909467b48Spatrick 390009467b48Spatrick Returns the list of Argument_. This is necessary to use when you need to 390109467b48Spatrick update the list or perform a complex action that doesn't have a forwarding 390209467b48Spatrick method. 390309467b48Spatrick 390409467b48Spatrick* ``BasicBlock &getEntryBlock()`` 390509467b48Spatrick 390609467b48Spatrick Returns the entry ``BasicBlock`` for the function. Because the entry block 390709467b48Spatrick for the function is always the first block, this returns the first block of 390809467b48Spatrick the ``Function``. 390909467b48Spatrick 391009467b48Spatrick* | ``Type *getReturnType()`` 391109467b48Spatrick | ``FunctionType *getFunctionType()`` 391209467b48Spatrick 391309467b48Spatrick This traverses the Type_ of the ``Function`` and returns the return type of 391409467b48Spatrick the function, or the FunctionType_ of the actual function. 391509467b48Spatrick 391609467b48Spatrick* ``SymbolTable *getSymbolTable()`` 391709467b48Spatrick 391809467b48Spatrick Return a pointer to the SymbolTable_ for this ``Function``. 391909467b48Spatrick 392009467b48Spatrick.. _GlobalVariable: 392109467b48Spatrick 392209467b48SpatrickThe ``GlobalVariable`` class 392309467b48Spatrick---------------------------- 392409467b48Spatrick 392509467b48Spatrick``#include "llvm/IR/GlobalVariable.h"`` 392609467b48Spatrick 392709467b48Spatrickheader source: `GlobalVariable.h 3928097a140dSpatrick<https://llvm.org/doxygen/GlobalVariable_8h_source.html>`_ 392909467b48Spatrick 393009467b48Spatrickdoxygen info: `GlobalVariable Class 3931097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1GlobalVariable.html>`_ 393209467b48Spatrick 393309467b48SpatrickSuperclasses: GlobalValue_, Constant_, User_, Value_ 393409467b48Spatrick 393509467b48SpatrickGlobal variables are represented with the (surprise surprise) ``GlobalVariable`` 393609467b48Spatrickclass. Like functions, ``GlobalVariable``\ s are also subclasses of 393709467b48SpatrickGlobalValue_, and as such are always referenced by their address (global values 393809467b48Spatrickmust live in memory, so their "name" refers to their constant address). See 393909467b48SpatrickGlobalValue_ for more on this. Global variables may have an initial value 394009467b48Spatrick(which must be a Constant_), and if they have an initializer, they may be marked 394109467b48Spatrickas "constant" themselves (indicating that their contents never change at 394209467b48Spatrickruntime). 394309467b48Spatrick 394409467b48Spatrick.. _m_GlobalVariable: 394509467b48Spatrick 394609467b48SpatrickImportant Public Members of the ``GlobalVariable`` class 394709467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 394809467b48Spatrick 394909467b48Spatrick* ``GlobalVariable(const Type *Ty, bool isConstant, LinkageTypes &Linkage, 395009467b48Spatrick Constant *Initializer = 0, const std::string &Name = "", Module* Parent = 0)`` 395109467b48Spatrick 395209467b48Spatrick Create a new global variable of the specified type. If ``isConstant`` is true 395309467b48Spatrick then the global variable will be marked as unchanging for the program. The 395409467b48Spatrick Linkage parameter specifies the type of linkage (internal, external, weak, 395509467b48Spatrick linkonce, appending) for the variable. If the linkage is InternalLinkage, 395609467b48Spatrick WeakAnyLinkage, WeakODRLinkage, LinkOnceAnyLinkage or LinkOnceODRLinkage, then 395709467b48Spatrick the resultant global variable will have internal linkage. AppendingLinkage 395809467b48Spatrick concatenates together all instances (in different translation units) of the 395909467b48Spatrick variable into a single variable but is only applicable to arrays. See the 396009467b48Spatrick `LLVM Language Reference <LangRef.html#modulestructure>`_ for further details 396109467b48Spatrick on linkage types. Optionally an initializer, a name, and the module to put 396209467b48Spatrick the variable into may be specified for the global variable as well. 396309467b48Spatrick 396409467b48Spatrick* ``bool isConstant() const`` 396509467b48Spatrick 396609467b48Spatrick Returns true if this is a global variable that is known not to be modified at 396709467b48Spatrick runtime. 396809467b48Spatrick 396909467b48Spatrick* ``bool hasInitializer()`` 397009467b48Spatrick 3971097a140dSpatrick Returns true if this ``GlobalVariable`` has an initializer. 397209467b48Spatrick 397309467b48Spatrick* ``Constant *getInitializer()`` 397409467b48Spatrick 397509467b48Spatrick Returns the initial value for a ``GlobalVariable``. It is not legal to call 397609467b48Spatrick this method if there is no initializer. 397709467b48Spatrick 397809467b48Spatrick.. _BasicBlock: 397909467b48Spatrick 398009467b48SpatrickThe ``BasicBlock`` class 398109467b48Spatrick------------------------ 398209467b48Spatrick 398309467b48Spatrick``#include "llvm/IR/BasicBlock.h"`` 398409467b48Spatrick 398509467b48Spatrickheader source: `BasicBlock.h 3986097a140dSpatrick<https://llvm.org/doxygen/BasicBlock_8h_source.html>`_ 398709467b48Spatrick 398809467b48Spatrickdoxygen info: `BasicBlock Class 3989097a140dSpatrick<https://llvm.org/doxygen/classllvm_1_1BasicBlock.html>`_ 399009467b48Spatrick 399109467b48SpatrickSuperclass: Value_ 399209467b48Spatrick 399309467b48SpatrickThis class represents a single entry single exit section of the code, commonly 399409467b48Spatrickknown as a basic block by the compiler community. The ``BasicBlock`` class 399509467b48Spatrickmaintains a list of Instruction_\ s, which form the body of the block. Matching 399609467b48Spatrickthe language definition, the last element of this list of instructions is always 399709467b48Spatricka terminator instruction. 399809467b48Spatrick 399909467b48SpatrickIn addition to tracking the list of instructions that make up the block, the 400009467b48Spatrick``BasicBlock`` class also keeps track of the :ref:`Function <c_Function>` that 400109467b48Spatrickit is embedded into. 400209467b48Spatrick 400309467b48SpatrickNote that ``BasicBlock``\ s themselves are Value_\ s, because they are 400409467b48Spatrickreferenced by instructions like branches and can go in the switch tables. 400509467b48Spatrick``BasicBlock``\ s have type ``label``. 400609467b48Spatrick 400709467b48Spatrick.. _m_BasicBlock: 400809467b48Spatrick 400909467b48SpatrickImportant Public Members of the ``BasicBlock`` class 401009467b48Spatrick^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 401109467b48Spatrick 401209467b48Spatrick* ``BasicBlock(const std::string &Name = "", Function *Parent = 0)`` 401309467b48Spatrick 401409467b48Spatrick The ``BasicBlock`` constructor is used to create new basic blocks for 401509467b48Spatrick insertion into a function. The constructor optionally takes a name for the 401609467b48Spatrick new block, and a :ref:`Function <c_Function>` to insert it into. If the 401709467b48Spatrick ``Parent`` parameter is specified, the new ``BasicBlock`` is automatically 401809467b48Spatrick inserted at the end of the specified :ref:`Function <c_Function>`, if not 401909467b48Spatrick specified, the BasicBlock must be manually inserted into the :ref:`Function 402009467b48Spatrick <c_Function>`. 402109467b48Spatrick 402209467b48Spatrick* | ``BasicBlock::iterator`` - Typedef for instruction list iterator 402309467b48Spatrick | ``BasicBlock::const_iterator`` - Typedef for const_iterator. 402409467b48Spatrick | ``begin()``, ``end()``, ``front()``, ``back()``, 4025*d415bd75Srobert ``size()``, ``empty()``, ``splice()`` 402609467b48Spatrick STL-style functions for accessing the instruction list. 402709467b48Spatrick 402809467b48Spatrick These methods and typedefs are forwarding functions that have the same 402909467b48Spatrick semantics as the standard library methods of the same names. These methods 403009467b48Spatrick expose the underlying instruction list of a basic block in a way that is easy 4031*d415bd75Srobert to manipulate. 403209467b48Spatrick 403309467b48Spatrick* ``Function *getParent()`` 403409467b48Spatrick 403509467b48Spatrick Returns a pointer to :ref:`Function <c_Function>` the block is embedded into, 403609467b48Spatrick or a null pointer if it is homeless. 403709467b48Spatrick 403809467b48Spatrick* ``Instruction *getTerminator()`` 403909467b48Spatrick 404009467b48Spatrick Returns a pointer to the terminator instruction that appears at the end of the 404109467b48Spatrick ``BasicBlock``. If there is no terminator instruction, or if the last 404209467b48Spatrick instruction in the block is not a terminator, then a null pointer is returned. 404309467b48Spatrick 404409467b48Spatrick.. _Argument: 404509467b48Spatrick 404609467b48SpatrickThe ``Argument`` class 404709467b48Spatrick---------------------- 404809467b48Spatrick 404909467b48SpatrickThis subclass of Value defines the interface for incoming formal arguments to a 405009467b48Spatrickfunction. A Function maintains a list of its formal arguments. An argument has 405109467b48Spatricka pointer to the parent Function. 4052