TheStringRef class¶

TheStringRef data type represents a reference to a constant string (acharacter array and a length) and supports the common operations available onstd::string, but does not require heap allocation.

It can be implicitly constructed using a C style null-terminated string, anstd::string, or explicitly with a character pointer and length. Forexample, theStringMap find function is declared as:

iteratorfind(StringRefKey);

and clients can call it using any one of:

Map.find("foo");// Lookup "foo"Map.find(std::string("bar"));// Lookup "bar"Map.find(StringRef("\0baz",4));// Lookup "\0baz"

Similarly, APIs which need to return a string may return aStringRefinstance, which can be used directly or converted to anstd::string usingthestr member function. Seellvm/ADT/StringRef.h (doxygen) for moreinformation.

You should rarely use theStringRef class directly, because it containspointers to external memory it is not generally safe to store an instance of theclass (unless you know that the external storage will not be freed).StringRef is small and pervasive enough in LLVM that it should always bepassed by value.

TheTwine class¶

TheTwine (doxygen)class is an efficient way for APIs to accept concatenated strings. For example,a common LLVM paradigm is to name one instruction based on the name of anotherinstruction with a suffix, for example:

New=CmpInst::Create(...,SO->getName()+".cmp");

TheTwine class is effectively a lightweightrope which points totemporary (stack allocated) objects. Twines can be implicitly constructed asthe result of the plus operator applied to strings (i.e., a C strings, anstd::string, or aStringRef). The twine delays the actual concatenationof strings until it is actually required, at which point it can be efficientlyrendered directly into a character array. This avoids unnecessary heapallocation involved in constructing the temporary results of stringconcatenation. Seellvm/ADT/Twine.h (doxygen) andherefor more information.

As with aStringRef,Twine objects point to external memory and shouldalmost never be stored or mentioned directly. They are intended solely for usewhen defining a function which should be able to efficiently accept concatenatedstrings.

Simple formatting¶

A call toformatv involves a singleformat string consisting of 0 or morereplacement sequences, followed by a variable length list ofreplacement values.A replacement sequence is a string of the form{N[[,align]:style]}.

N refers to the 0-based index of the argument from the list of replacementvalues. Note that this means it is possible to reference the same parametermultiple times, possibly with different style and/or alignment options, in any order.

align is an optional string specifying the width of the field to formatthe value into, and the alignment of the value within the field. It is specified asan optionalalignment style followed by a positive integralfield width. Thealignment style can be one of the characters- (left align),= (center align),or+ (right align). The default is right aligned.

style is an optional string consisting of a type specific that controls theformatting of the value. For example, to format a floating point value as a percentage,you can use the style optionP.

Custom formatting¶

There are two ways to customize the formatting behavior for a type.

1. Provide a template specialization ofllvm::format_provider<T> for yourtypeT with the appropriate static format method.

namespacellvm{template<>structformat_provider<MyFooBar>{staticvoidformat(constMyFooBar&V,raw_ostream&Stream,StringRefStyle){// Do whatever is necessary to format `V` into `Stream`}};voidfoo(){MyFooBarX;std::stringS=formatv("{0}",X);}}

This is a useful extensibility mechanism for adding support for formatting your owncustom types with your own custom Style options. But it does not help when you wantto extend the mechanism for formatting a type that the library already knows how toformat. For that, we need something else.

2. Provide aformat adapter inheriting fromllvm::FormatAdapter<T>.

namespaceanything{structformat_int_custom:publicllvm::FormatAdapter<int>{explicitformat_int_custom(intN):llvm::FormatAdapter<int>(N){}voidformat(llvm::raw_ostream&Stream,StringRefStyle)override{// Do whatever is necessary to format ``this->Item`` into ``Stream``}};}namespacellvm{voidfoo(){std::stringS=formatv("{0}",anything::format_int_custom(42));}}

If the type is detected to be derived fromFormatAdapter<T>,formatvwill call theformat method on the argument passing in the specified style. This allowsone to provide custom formatting of any type, including one which already hasa builtin format provider.

formatv Examples¶

Below is intended to provide an incomplete set of examples demonstratingthe usage offormatv. More information can be found by reading thedoxygen documentation or by looking at the unit test suite.

std::stringS;// Simple formatting of basic types and implicit string conversion.S=formatv("{0} ({1:P})",7,0.35);// S == "7 (35.00%)"// Out-of-order referencing and multi-referencingouts()<<formatv("{0} {2} {1} {0}",1,"test",3);// prints "1 3 test 1"// Left, right, and center alignmentS=formatv("{0,7}",'a');// S == "      a";S=formatv("{0,-7}",'a');// S == "a      ";S=formatv("{0,=7}",'a');// S == "   a   ";S=formatv("{0,+7}",'a');// S == "      a";// Custom stylesS=formatv("{0:N} - {0:x} - {1:E}",12345,123908342);// S == "12,345 - 0x3039 - 1.24E8"// AdaptersS=formatv("{0}",fmt_align(42,AlignStyle::Center,7));// S == "  42   "S=formatv("{0}",fmt_repeat("hi",3));// S == "hihihi"S=formatv("{0}",fmt_pad("hi",2,6));// S == "  hi      "// Rangesstd::vector<int>V={8,9,10};S=formatv("{0}",make_range(V.begin(),V.end()));// S == "8, 9, 10"S=formatv("{0:$[+]}",make_range(V.begin(),V.end()));// S == "8+9+10"S=formatv("{0:$[ + ]@[x]}",make_range(V.begin(),V.end()));// S == "0x8 + 0x9 + 0xA"

Programmatic Errors¶

Programmatic errors are violations of program invariants or API contracts, andrepresent bugs within the program itself. Our aim is to document invariants, andto abort quickly at the point of failure (providing some basic diagnostic) wheninvariants are broken at runtime.

The fundamental tools for handling programmatic errors are assertions and thellvm_unreachable function. Assertions are used to express invariant conditions,and should include a message describing the invariant:

assert(isPhysReg(R)&&"All virt regs should have been allocated already.");

The llvm_unreachable function can be used to document areas of control flowthat should never be entered if the program invariants hold:

enum{Foo,Bar,Baz}X=foo();switch(X){caseFoo:/* Handle Foo */;break;caseBar:/* Handle Bar */;break;default:llvm_unreachable("X should be Foo or Bar here");}

Additionally,reportFatalInternalError can be used to report invariantviolations even in builds that do not enable assertions:

if(VerifyFooAnalysis&&!Foo.verify()){reportFatalInternalError("Analysis 'foo' not preserved");}

Recoverable Errors¶

Recoverable errors represent an error in the program’s environment, for examplea resource failure (a missing file, a dropped network connection, etc.), ormalformed input. These errors should be detected and communicated to a level ofthe program where they can be handled appropriately. Handling the error may beas simple as reporting the issue to the user, or it may involve attempts atrecovery.

Recoverable errors are modeled using LLVM’sError scheme. This schemerepresents errors using function return values, similar to classic C integererror codes, or C++’sstd::error_code. However, theError class isactually a lightweight wrapper for user-defined error types, allowing arbitraryinformation to be attached to describe the error. This is similar to the way C++exceptions allow throwing of user-defined types.

Success values are created by callingError::success(), E.g.:

Errorfoo(){// Do something.// Return success.returnError::success();}

Success values are very cheap to construct and return - they have minimalimpact on program performance.

Failure values are constructed usingmake_error<T>, whereT is any classthat inherits from the ErrorInfo utility, E.g.:

classBadFileFormat:publicErrorInfo<BadFileFormat>{public:staticcharID;std::stringPath;BadFileFormat(StringRefPath):Path(Path.str()){}voidlog(raw_ostream&OS)constoverride{OS<<Path<<" is malformed";}std::error_codeconvertToErrorCode()constoverride{returnmake_error_code(object_error::parse_failed);}};charBadFileFormat::ID;// This should be declared in the C++ file.ErrorprintFormattedFile(StringRefPath){if(<checkforvalidformat>)returnmake_error<BadFileFormat>(Path);// print file contents.returnError::success();}

Error values can be implicitly converted to bool: true for error, false forsuccess, enabling the following idiom:

ErrormayFail();Errorfoo(){if(autoErr=mayFail())returnErr;// Success! We can proceed....

For functions that can fail but need to return a value theExpected<T>utility can be used. Values of this type can be constructed with either aT, or anError. Expected<T> values are also implicitly convertible toboolean, but with the opposite convention toError: true for success, falsefor error. If success, theT value can be accessed via the dereferenceoperator. If failure, theError value can be extracted using thetakeError() method. Idiomatic usage looks like:

Expected<FormattedFile>openFormattedFile(StringRefPath){// If badly formatted, return an error.if(autoErr=checkFormat(Path))returnstd::move(Err);// Otherwise return a FormattedFile instance.returnFormattedFile(Path);}ErrorprocessFormattedFile(StringRefPath){// Try to open a formatted fileif(autoFileOrErr=openFormattedFile(Path)){// On success, grab a reference to the file and continue.auto&File=*FileOrErr;...}else// On error, extract the Error value and return it.returnFileOrErr.takeError();}

If anExpected<T> value is in success mode then thetakeError() methodwill return a success value. Using this fact, the above function can berewritten as:

ErrorprocessFormattedFile(StringRefPath){// Try to open a formatted fileautoFileOrErr=openFormattedFile(Path);if(autoErr=FileOrErr.takeError())// On error, extract the Error value and return it.returnErr;// On success, grab a reference to the file and continue.auto&File=*FileOrErr;...}

This second form is often more readable for functions that involve multipleExpected<T> values as it limits the indentation required.

If anExpected<T> value will be moved into an existing variable then themoveInto() method avoids the need to name an extra variable. This isuseful to enableoperator->() theExpected<T> value has pointer-likesemantics. For example:

Expected<std::unique_ptr<MemoryBuffer>>openBuffer(StringRefPath);ErrorprocessBuffer(StringRefBuffer);ErrorprocessBufferAtPath(StringRefPath){// Try to open a buffer.std::unique_ptr<MemoryBuffer>MB;if(autoErr=openBuffer(Path).moveInto(MB))// On error, return the Error value.returnErr;// On success, use MB.returnprocessBuffer(MB->getBuffer());}

This third form works with any type that can be assigned to fromT&&. Thiscan be useful if theExpected<T> value needs to be stored an already-declaredstd::optional<T>. For example:

Expected<StringRef>extractClassName(StringRefDefinition);structClassData{StringRefDefinition;std::optional<StringRef>LazyName;...Errorinitialize(){if(autoErr=extractClassName(Path).moveInto(LazyName))// On error, return the Error value.returnErr;// On success, LazyName has been initialized....}};

AllError instances, whether success or failure, must be either checked ormoved from (viastd::move or a return) before they are destructed.Accidentally discarding an unchecked error will cause a program abort at thepoint where the unchecked value’s destructor is run, making it easy to identifyand fix violations of this rule.

Success values are considered checked once they have been tested (by invokingthe boolean conversion operator):

if(autoErr=mayFail(...))returnErr;// Failure value - move error to caller.// Safe to continue: Err was checked.

In contrast, the following code will always cause an abort, even ifmayFailreturns a success value:

mayFail();// Program will always abort here, even if mayFail() returns Success, since// the value is not checked.

Failure values are considered checked once a handler for the error type hasbeen activated:

handleErrors(processFormattedFile(...),[](constBadFileFormat&BFF){report("Unable to process "+BFF.Path+": bad format");},[](constFileNotFound&FNF){report("File not found "+FNF.Path);});

ThehandleErrors function takes an error as its first argument, followed bya variadic list of “handlers”, each of which must be a callable type (afunction, lambda, or class with a call operator) with one argument. ThehandleErrors function will visit each handler in the sequence and check itsargument type against the dynamic type of the error, running the first handlerthat matches. This is the same decision process that is used decide which catchclause to run for a C++ exception.

Since the list of handlers passed tohandleErrors may not cover every errortype that can occur, thehandleErrors function also returns an Error valuethat must be checked or propagated. If the error value that is passed tohandleErrors does not match any of the handlers it will be returned fromhandleErrors. Idiomatic use ofhandleErrors thus looks like:

if(autoErr=handleErrors(processFormattedFile(...),[](constBadFileFormat&BFF){report("Unable to process "+BFF.Path+": bad format");},[](constFileNotFound&FNF){report("File not found "+FNF.Path);}))returnErr;

In cases where you truly know that the handler list is exhaustive thehandleAllErrors function can be used instead. This is identical tohandleErrors except that it will terminate the program if an unhandlederror is passed in, and can therefore return void. ThehandleAllErrorsfunction should generally be avoided: the introduction of a new error typeelsewhere in the program can easily turn a formerly exhaustive list of errorsinto a non-exhaustive list, risking unexpected program termination. Wherepossible, use handleErrors and propagate unknown errors up the stack instead.

For tool code, where errors can be handled by printing an error message thenexiting with an error code, theExitOnError utilitymay be a better choice than handleErrors, as it simplifies control flow whencalling fallible functions.

In situations where it is known that a particular call to a fallible functionwill always succeed (for example, a call to a function that can only fail on asubset of inputs with an input that is known to be safe) thecantFail functions can be used to remove the error type,simplifying control flow.

// These two lines of code are equivalent:make_error<StringError>("Bad executable",errc::executable_format_error);createStringError(errc::executable_format_error,"Bad executable");

createStringError(inconvertibleErrorCode(),"Bad executable");

createStringError(errc::executable_format_error,"Bad executable: %s",FileName);

std::error_codeerrorToErrorCode(ErrorErr);ErrorerrorCodeToError(std::error_codeEC);template<typenameT>ErrorOr<T>expectedToErrorOr(Expected<T>TOrErr);template<typenameT>Expected<T>errorOrToExpected(ErrorOr<T>TOrEC);

// Error must be handled, no new errors produced:void(UserDefinedError&E);// Error must be handled, new errors can be produced:Error(UserDefinedError&E);// Original error can be inspected, then re-wrapped and returned (or a new// error can be produced):Error(std::unique_ptr<UserDefinedError>E);

ExitOnErrorExitOnErr;

ErrormayFail();Expected<int>mayFail2();voidfoo(){ExitOnErr(mayFail());intX=ExitOnErr(mayFail2());}

intmain(intargc,char*argv[]){ExitOnErr.setBanner(std::string(argv[0])+" error:");ExitOnErr.setExitCodeMapper([](constError&Err){if(Err.isA<BadFileFormat>())return2;return1;});

ErroronlyFailsForSomeXValues(intX);Expected<int>onlyFailsForSomeXValues2(intX);voidfoo(){cantFail(onlyFailsForSomeXValues(KnownSafeValue));intY=cantFail(onlyFailsForSomeXValues2(KnownSafeValue));...}

classFoo{public:staticExpected<Foo>Create(ResourceR1,ResourceR2){ErrorErr=Error::success();FooF(R1,R2,Err);if(Err)returnstd::move(Err);returnstd::move(F);}private:Foo(ResourceR1,ResourceR2,Error&Err){ErrorAsOutParameterEAO(&Err);if(autoErr2=R1.acquire()){Err=std::move(Err2);return;}Err=R2.acquire();}};

ErrorwalkArchive(ArchiveA){for(unsignedI=0;I!=A.numMembers();++I){autoChildOrErr=A.getMember(I);if(autoErr=ChildOrErr.takeError()){if(Err.isA<BadFileFormat>())consumeError(std::move(Err))elsereturnErr;}auto&Child=*ChildOrErr;// Use Child...}returnError::success();}

ErrorwalkArchive(ArchiveA){ErrorDeferredErrs=Error::success();for(unsignedI=0;I!=A.numMembers();++I){autoChildOrErr=A.getMember(I);if(autoErr=ChildOrErr.takeError())if(Err.isA<BadFileFormat>())DeferredErrs=joinErrors(std::move(DeferredErrs),std::move(Err));elsereturnErr;auto&Child=*ChildOrErr;// Use Child...}returnDeferredErrs;}

ErrorErr=Error::success();for(auto&Child:Ar->children(Err)){// Use Child - only enter the loop when it's valid// Allow early exit from the loop body, since we know that Err is success// when we're inside the loop.if(BailOutOn(Child))return;...}// Check Err after the loop to ensure it didn't break due to an error.if(Err)returnErr;

classFallibleChildIterator{public:FallibleChildIterator(Archive&A,unsignedChildIdx);Archive::Child&operator*();friendbooloperator==(constArchiveIterator&LHS,constArchiveIterator&RHS);// operator++/operator-- replaced with fallible increment / decrement:Errorinc(){if(!A.childValid(ChildIdx+1))returnmake_error<BadArchiveMember>(...);++ChildIdx;returnError::success();}Errordec(){...}};

classArchive{public:usingchild_iterator=fallible_iterator<FallibleChildIterator>;child_iteratorchild_begin(Error&Err){returnmake_fallible_itr(FallibleChildIterator(*this,0),Err);}child_iteratorchild_end(){returnmake_fallible_end(FallibleChildIterator(*this,size()));}iterator_range<child_iterator>children(Error&Err){returnmake_range(child_begin(Err),child_end());}};

Function template¶

If you don’t mind putting the definition of your function into a header file,make it a function template that is templated on the callable type.

template<typenameCallable>voidtakeCallback(CallableCallback){Callback(1,2,3);}

Thefunction_ref class template¶

Thefunction_ref(doxygen) classtemplate represents a reference to a callable object, templated over the typeof the callable. This is a good choice for passing a callback to a function,if you don’t need to hold onto the callback after the function returns. In thisway,function_ref is tostd::function asStringRef is tostd::string.

function_ref<Ret(Param1,Param2,...)> can be implicitly constructed fromany callable object that can be called with arguments of typeParam1,Param2, …, and returns a value that can be converted to typeRet.For example:

voidvisitBasicBlocks(Function*F,function_ref<bool(BasicBlock*)>Callback){for(BasicBlock&BB:*F)if(Callback(&BB))return;}

can be called using:

visitBasicBlocks(F,[&](BasicBlock*BB){if(process(BB))returnisEmpty(BB);returnfalse;});

Note that afunction_ref object contains pointers to external memory, so itis not generally safe to store an instance of the class (unless you know thatthe external storage will not be freed). If you need this ability, considerusingstd::function.function_ref is small enough that it should alwaysbe passed by value.

Fine grained debug info withDEBUG_TYPE and the-debug-only option¶

Sometimes you may find yourself in a situation where enabling-debug justturns ontoo much information (such as when working on the code generator).If you want to enable debug information with more fine-grained control, youshould define theDEBUG_TYPE macro and use the-debug-only option asfollows:

#define DEBUG_TYPE "foo"LLVM_DEBUG(dbgs()<<"'foo' debug type\n");#undef  DEBUG_TYPE#define DEBUG_TYPE "bar"LLVM_DEBUG(dbgs()<<"'bar' debug type\n");#undef  DEBUG_TYPE

Then you can run your pass like this:

$ opt < a.bc > /dev/null -mypass<no output>$ opt < a.bc > /dev/null -mypass -debug'foo' debug type'bar' debug type$ opt < a.bc > /dev/null -mypass -debug-only=foo'foo' debug type$ opt < a.bc > /dev/null -mypass -debug-only=bar'bar' debug type$ opt < a.bc > /dev/null -mypass -debug-only=foo,bar'foo' debug type'bar' debug type

Of course, in practice, you should only setDEBUG_TYPE at the top of a file,to specify the debug type for the entire module. Be careful that you only dothis after including Debug.h and not around any #include of headers. Also, youshould use names more meaningful than “foo” and “bar”, because there is nosystem in place to ensure that names do not conflict. If two different modulesuse the same string, they will all be turned on when the name is specified.This allows, for example, all debug information for instruction scheduling to beenabled with-debug-only=InstrSched, even if the source lives in multiplefiles. The name must not include a comma (,) as that is used to separate thearguments of the-debug-only option.

For performance reasons, -debug-only is not available in optimized build(--enable-optimized) of LLVM.

TheDEBUG_WITH_TYPE macro is also available for situations where you wouldlike to setDEBUG_TYPE, but only for one specificDEBUG statement. Ittakes an additional first parameter, which is the type to use. For example, thepreceding example could be written as:

DEBUG_WITH_TYPE("foo",dbgs()<<"'foo' debug type\n");DEBUG_WITH_TYPE("bar",dbgs()<<"'bar' debug type\n");

llvm/ADT/ArrayRef.h¶

Thellvm::ArrayRef class is the preferred class to use in an interface thataccepts a sequential list of elements in memory and just reads from them. Bytaking anArrayRef, the API can be passed a fixed size array, anstd::vector, anllvm::SmallVector and anything else that is contiguousin memory.

Fixed Size Arrays¶

Fixed size arrays are very simple and very fast. They are good if you knowexactly how many elements you have, or you have a (low) upper bound on how manyyou have.

Heap Allocated Arrays¶

Heap allocated arrays (new[] +delete[]) are also simple. They are goodif the number of elements is variable, if you know how many elements you willneed before the array is allocated, and if the array is usually large (if not,consider aSmallVector). The cost of a heap allocatedarray is the cost of the new/delete (aka malloc/free). Also note that if youare allocating an array of a type with a constructor, the constructor anddestructors will be run for every element in the array (re-sizable vectors onlyconstruct those elements actually used).

llvm/ADT/TinyPtrVector.h¶

TinyPtrVector<Type> is a highly specialized collection class that isoptimized to avoid allocation in the case when a vector has zero or oneelements. It has two major restrictions: 1) it can only hold values of pointertype, and 2) it cannot hold a null pointer.

Since this container is highly specialized, it is rarely used.

llvm/ADT/SmallVector.h¶

SmallVector<Type,N> is a simple class that looks and smells just likevector<Type>: it supports efficient iteration, lays out elements in memoryorder (so you can do pointer arithmetic between elements), supports efficientpush_back/pop_back operations, supports efficient random access to its elements,etc.

The main advantage of SmallVector is that it allocates space for some number ofelements (N)in the object itself. Because of this, if the SmallVector isdynamically smaller than N, no malloc is performed. This can be a big win incases where the malloc/free call is far more expensive than the code thatfiddles around with the elements.

This is good for vectors that are “usually small” (e.g. the number ofpredecessors/successors of a block is usually less than 8). On the other hand,this makes the size of the SmallVector itself large, so you don’t want toallocate lots of them (doing so will waste a lot of space). As such,SmallVectors are most useful when on the stack.

In the absence of a well-motivated choice for the number ofinlined elementsN, it is recommended to useSmallVector<T> (that is,omitting theN). This will choose a default number ofinlined elements reasonable for allocation on the stack (for example, tryingto keepsizeof(SmallVector<T>) around 64 bytes).

SmallVector also provides a nice portable and efficient replacement foralloca.

SmallVector has grown a few other minor advantages over std::vector, causingSmallVector<Type,0> to be preferred overstd::vector<Type>.

1. std::vector is exception-safe, and some implementations have pessimizationsthat copy elements when SmallVector would move them.

2. SmallVector understandsstd::is_trivially_copyable<Type> and uses realloc aggressively.

3. Many LLVM APIs take a SmallVectorImpl as an out parameter (see the notebelow).

4. SmallVector with N equal to 0 is smaller than std::vector on 64-bitplatforms, since it usesunsigned (instead ofvoid*) for its sizeand capacity.

// DISCOURAGED: Clients cannot pass e.g. raw arrays.hardcodedContiguousStorage(constSmallVectorImpl<Foo>&In);// ENCOURAGED: Clients can pass any contiguous storage of Foo.allowsAnyContiguousStorage(ArrayRef<Foo>In);voidsomeFunc1(){FooVec[]={/* ... */};hardcodedContiguousStorage(Vec);// Error.allowsAnyContiguousStorage(Vec);// Works.}// DISCOURAGED: Clients cannot pass e.g. SmallVector<Foo, 8>.hardcodedSmallSize(SmallVector<Foo,2>&Out);// ENCOURAGED: Clients can pass any SmallVector<Foo, N>.allowsAnySmallSize(SmallVectorImpl<Foo>&Out);voidsomeFunc2(){SmallVector<Foo,8>Vec;hardcodedSmallSize(Vec);// Error.allowsAnySmallSize(Vec);// Works.}

llvm/ADT/PagedVector.h¶

PagedVector<Type,PageSize> is a random access container that allocatesPageSize elements of typeType when the first element of a page isaccessed via theoperator[]. This is useful for cases where the number ofelements is known in advance; their actual initialization is expensive; andthey are sparsely used. This utility uses page-granular lazy initializationwhen the element is accessed. When the number of used pages is smallsignificant memory savings can be achieved.

The main advantage is that aPagedVector allows to delay the actualallocation of the page until it’s needed, at the extra cost of one pointer perpage and one extra indirection when accessing elements with their positionalindex.

In order to minimise the memory footprint of this container, it’s important tobalance the PageSize so that it’s not too small (otherwise the overhead of thepointer per page might become too high) and not too big (otherwise the memoryis wasted if the page is not fully used).

Moreover, while retaining the order of the elements based on their insertionindex, like a vector, iterating over the elements viabegin() andend()is not provided in the API, due to the fact accessing the elements in orderwould allocate all the iterated pages, defeating memory savings and the purposeof thePagedVector.

Finally amaterialized_begin() andmaterialized_end iterators areprovided to access the elements associated to the accessed pages, which couldspeed up operations that need to iterate over initialized elements in anon-ordered manner.

<vector>¶

std::vector<T> is well loved and respected. However,SmallVector<T,0>is often a better option due to the advantages listed above. std::vector isstill useful when you need to store more thanUINT32_MAX elements or wheninterfacing with code that expects vectors :).

One worthwhile note about std::vector: avoid code like this:

for(...){std::vector<foo>V;// make use of V.}

Instead, write this as:

std::vector<foo>V;for(...){// make use of V.V.clear();}

Doing so will save (at least) one heap allocation and free per iteration of theloop.

<deque>¶

std::deque is, in some senses, a generalized version ofstd::vector.Likestd::vector, it provides constant time random access and other similarproperties, but it also provides efficient access to the front of the list. Itdoes not guarantee continuity of elements within memory.

In exchange for this extra flexibility,std::deque has significantly higherconstant factor costs thanstd::vector. If possible, usestd::vector orsomething cheaper.

<list>¶

std::list is an extremely inefficient class that is rarely useful. Itperforms a heap allocation for every element inserted into it, thus having anextremely high constant factor, particularly for small data types.std::list also only supports bidirectional iteration, not random accessiteration.

In exchange for this high cost, std::list supports efficient access to both endsof the list (likestd::deque, but unlikestd::vector orSmallVector). In addition, the iterator invalidation characteristics ofstd::list are stronger than that of a vector class: inserting or removing anelement into the list does not invalidate iterator or pointers to other elementsin the list.

llvm/ADT/ilist.h¶

ilist<T> implements an ‘intrusive’ doubly-linked list. It is intrusive,because it requires the element to store and provide access to the prev/nextpointers for the list.

ilist has the same drawbacks asstd::list, and additionally requires anilist_traits implementation for the element type, but it provides some novelcharacteristics. In particular, it can efficiently store polymorphic objects,the traits class is informed when an element is inserted or removed from thelist, andilists are guaranteed to support a constant-time spliceoperation.

Anilist and aniplist areusing aliases to one another and thelatter only currently exists for historical purposes.

These properties are exactly what we want for things likeInstructions andbasic blocks, which is why these are implemented withilists.

Related classes of interest are explained in the following subsections:

• ilist_traits

• llvm/ADT/ilist_node.h

• Sentinels

llvm/ADT/PackedVector.h¶

Useful for storing a vector of values using only a few number of bits for eachvalue. Apart from the standard operations of a vector-like container, it canalso perform an ‘or’ set operation.

For example:

enumState{None=0x0,FirstCondition=0x1,SecondCondition=0x2,Both=0x3};Stateget(){PackedVector<State,2>Vec1;Vec1.push_back(FirstCondition);PackedVector<State,2>Vec2;Vec2.push_back(SecondCondition);Vec1|=Vec2;returnVec1[0];// returns 'Both'.}

ilist_traits¶

ilist_traits<T> isilist<T>’s customization mechanism.ilist<T>publicly derives from this traits class.

llvm/ADT/ilist_node.h¶

ilist_node<T> implements the forward and backward links that are expectedby theilist<T> (and analogous containers) in the default manner.

ilist_node<T>s are meant to be embedded in the node typeT, usuallyT publicly derives fromilist_node<T>.

Sentinels¶

ilists have another specialty that must be considered. To be a goodcitizen in the C++ ecosystem, it needs to support the standard containeroperations, such asbegin andend iterators, etc. Also, theoperator-- must work correctly on theend iterator in the case ofnon-emptyilists.

The only sensible solution to this problem is to allocate a so-calledsentinelalong with the intrusive list, which serves as theend iterator, providingthe back-link to the last element. However conforming to the C++ convention itis illegal tooperator++ beyond the sentinel and it also must not bedereferenced.

These constraints allow for some implementation freedom to theilist how toallocate and store the sentinel. The corresponding policy is dictated byilist_traits<T>. By default aT gets heap-allocated whenever the needfor a sentinel arises.

While the default policy is sufficient in most cases, it may break down whenT does not provide a default constructor. Also, in the case of manyinstances ofilists, the memory overhead of the associated sentinels iswasted. To alleviate the situation with numerous and voluminousT-sentinels, sometimes a trick is employed, leading toghostly sentinels.

Ghostly sentinels are obtained by specially-craftedilist_traits<T> whichsuperpose the sentinel with theilist instance in memory. Pointerarithmetic is used to obtain the sentinel, which is relative to theilist’sthis pointer. Theilist is augmented by an extra pointer, which servesas the back-link of the sentinel. This is the only field in the ghostlysentinel which can be legally accessed.

Other Sequential Container options¶

Other STL containers are available, such asstd::string.

There are also various STL adapter classes such asstd::queue,std::priority_queue,std::stack, etc. These provide simplified accessto an underlying container but don’t affect the cost of the container itself.

llvm/ADT/StringRef.h¶

The StringRef class is a simple value class that contains a pointer to acharacter and a length, and is quite related to theArrayRef class (but specialized for arrays of characters). BecauseStringRef carries a length with it, it safely handles strings with embedded nulcharacters in it, getting the length does not require a strlen call, and it evenhas very convenient APIs for slicing and dicing the character range that itrepresents.

StringRef is ideal for passing simple strings around that are known to be live,either because they are C string literals, std::string, a C array, or aSmallVector. Each of these cases has an efficient implicit conversion toStringRef, which doesn’t result in a dynamic strlen being executed.

StringRef has a few major limitations which make more powerful string containersuseful:

1. You cannot directly convert a StringRef to a ‘const char*’ because there isno way to add a trailing nul (unlike the .c_str() method on various strongerclasses).

2. StringRef doesn’t own or keep alive the underlying string bytes.As such it can easily lead to dangling pointers, and is not suitable forembedding in datastructures in most cases (instead, use an std::string orsomething like that).

3. For the same reason, StringRef cannot be used as the return value of amethod if the method “computes” the result string. Instead, use std::string.

4. StringRef’s do not allow you to mutate the pointed-to string bytes and itdoesn’t allow you to insert or remove bytes from the range. For editingoperations like this, it interoperates with theTwineclass.

Because of its strengths and limitations, it is very common for a function totake a StringRef and for a method on an object to return a StringRef that pointsinto some string that it owns.

llvm/ADT/Twine.h¶

The Twine class is used as an intermediary datatype for APIs that want to take astring that can be constructed inline with a series of concatenations. Twineworks by forming recursive instances of the Twine datatype (a simple valueobject) on the stack as temporary objects, linking them together into a treewhich is then linearized when the Twine is consumed. Twine is only safe to useas the argument to a function, and should always be a const reference, e.g.:

voidfoo(constTwine&T);...StringRefX=...unsignedi=...foo(X+"."+Twine(i));

This example forms a string like “blarg.42” by concatenating the valuestogether, and does not form intermediate strings containing “blarg” or “blarg.”.

Because Twine is constructed with temporary objects on the stack, and becausethese instances are destroyed at the end of the current statement, it is aninherently dangerous API. For example, this simple variant contains undefinedbehavior and will probably crash:

voidfoo(constTwine&T);...StringRefX=...unsignedi=...constTwine&Tmp=X+"."+Twine(i);foo(Tmp);

… because the temporaries are destroyed before the call. That said, Twine’sare much more efficient than intermediate std::string temporaries, and they workreally well with StringRef. Just be aware of their limitations.

llvm/ADT/SmallString.h¶

SmallString is a subclass ofSmallVector that adds someconvenience APIs like += that takes StringRef’s. SmallString avoids allocatingmemory in the case when the preallocated space is enough to hold its data, andit calls back to general heap allocation when required. Since it owns its data,it is very safe to use and supports full mutation of the string.

Like SmallVector’s, the big downside to SmallString is their sizeof. While theyare optimized for small strings, they themselves are not particularly small.This means that they work great for temporary scratch buffers on the stack, butshould not generally be put into the heap: it is very rare to see a SmallStringas the member of a frequently-allocated heap data structure or returnedby-value.

std::string¶

The standard C++ std::string class is a very general class that (likeSmallString) owns its underlying data. sizeof(std::string) is very reasonableso it can be embedded into heap data structures and returned by-value. On theother hand, std::string is highly inefficient for inline editing (e.g.concatenating a bunch of stuff together) and because it is provided by thestandard library, its performance characteristics depend a lot of the hoststandard library (e.g. libc++ and MSVC provide a highly optimized string class,GCC contains a really slow implementation).

The major disadvantage of std::string is that almost every operation that makesthem larger can allocate memory, which is slow. As such, it is better to useSmallVector or Twine as a scratch buffer, but then use std::string to persistthe result.

A sorted ‘vector’¶

If you intend to insert a lot of elements, then do a lot of queries, a greatapproach is to use an std::vector (or other sequential container) withstd::sort+std::unique to remove duplicates. This approach works really well ifyour usage pattern has these two distinct phases (insert then query), and can becoupled with a good choice ofsequential container.

This combination provides the several nice properties: the result data iscontiguous in memory (good for cache locality), has few allocations, is easy toaddress (iterators in the final vector are just indices or pointers), and can beefficiently queried with a standard binary search (e.g.std::lower_bound; if you want the whole range of elements comparingequal, usestd::equal_range).

llvm/ADT/SmallSet.h¶

If you have a set-like data structure that is usually small and whose elementsare reasonably small, aSmallSet<Type,N> is a good choice. This set hasspace for N elements in place (thus, if the set is dynamically smaller than N,no malloc traffic is required) and accesses them with a simple linear search.When the set grows beyond N elements, it allocates a more expensiverepresentation that guarantees efficient access (for most types, it falls backtostd::set, but for pointers it uses something far better,SmallPtrSet.

The magic of this class is that it handles small sets extremely efficiently, butgracefully handles extremely large sets without loss of efficiency.

llvm/ADT/SmallPtrSet.h¶

SmallPtrSet has all the advantages ofSmallSet (and aSmallSet ofpointers is transparently implemented with aSmallPtrSet). If more than Ninsertions are performed, a single quadratically probed hash table is allocatedand grows as needed, providing extremely efficient access (constant timeinsertion/deleting/queries with low constant factors) and is very stingy withmalloc traffic.

Note that, unlikestd::set, the iterators ofSmallPtrSetare invalidated whenever an insertion or erasure occurs. Theremove_ifmethod can be used to remove elements while iterating over the set.

Also, the values visited by the iterators are not visited in sorted order.

llvm/ADT/StringSet.h¶

StringSet is a thin wrapper aroundStringMap<char>,and it allows efficient storage and retrieval of unique strings.

Functionally analogous toSmallSet<StringRef>,StringSet also supportsiteration. (The iterator dereferences to aStringMapEntry<char>, so youneed to calli->getKey() to access the item of the StringSet.) On theother hand,StringSet doesn’t support range-insertion andcopy-construction, whichSmallSet andSmallPtrSet do support.

llvm/ADT/DenseSet.h¶

DenseSet is a simple quadratically probed hash table. It excels at supportingsmall values: it uses a single allocation to hold all of the pairs that arecurrently inserted in the set. DenseSet is a great way to unique small valuesthat are not simple pointers (useSmallPtrSet forpointers). Note that DenseSet has the same requirements for the value type thatDenseMap has.

llvm/ADT/SparseSet.h¶

SparseSet holds a small number of objects identified by unsigned keys ofmoderate size. It uses a lot of memory, but provides operations that are almostas fast as a vector. Typical keys are physical registers, virtual registers, ornumbered basic blocks.

SparseSet is useful for algorithms that need very fast clear/find/insert/eraseand fast iteration over small sets. It is not intended for building compositedata structures.

llvm/ADT/SparseMultiSet.h¶

SparseMultiSet adds multiset behavior to SparseSet, while retaining SparseSet’sdesirable attributes. Like SparseSet, it typically uses a lot of memory, butprovides operations that are almost as fast as a vector. Typical keys arephysical registers, virtual registers, or numbered basic blocks.

SparseMultiSet is useful for algorithms that need very fastclear/find/insert/erase of the entire collection, and iteration over sets ofelements sharing a key. It is often a more efficient choice than using compositedata structures (e.g. vector-of-vectors, map-of-vectors). It is not intended forbuilding composite data structures.

llvm/ADT/FoldingSet.h¶

FoldingSet is an aggregate class that is really good at uniquingexpensive-to-create or polymorphic objects. It is a combination of a chainedhash table with intrusive links (uniqued objects are required to inherit fromFoldingSetNode) that usesSmallVector as part of its IDprocess.

Consider a case where you want to implement a “getOrCreateFoo” method for acomplex object (for example, a node in the code generator). The client has adescription ofwhat it wants to generate (it knows the opcode and all theoperands), but we don’t want to ‘new’ a node, then try inserting it into a setonly to find out it already exists, at which point we would have to delete itand return the node that already exists.

To support this style of client, FoldingSet perform a query with aFoldingSetNodeID (which wraps SmallVector) that can be used to describe theelement that we want to query for. The query either returns the elementmatching the ID or it returns an opaque ID that indicates where insertion shouldtake place. Construction of the ID usually does not require heap traffic.

Because FoldingSet uses intrusive links, it can support polymorphic objects inthe set (for example, you can have SDNode instances mixed with LoadSDNodes).Because the elements are individually allocated, pointers to the elements arestable: inserting or removing elements does not invalidate any pointers to otherelements.

<set>¶

std::set is a reasonable all-around set class, which is decent at manythings but great at nothing. std::set allocates memory for each elementinserted (thus it is very malloc intensive) and typically stores three pointersper element in the set (thus adding a large amount of per-element spaceoverhead). It offers guaranteed log(n) performance, which is not particularlyfast from a complexity standpoint (particularly if the elements of the set areexpensive to compare, like strings), and has extremely high constant factors forlookup, insertion and removal.

The advantages of std::set are that its iterators are stable (deleting orinserting an element from the set does not affect iterators or pointers to otherelements) and that iteration over the set is guaranteed to be in sorted order.If the elements in the set are large, then the relative overhead of the pointersand malloc traffic is not a big deal, but if the elements of the set are small,std::set is almost never a good choice.

llvm/ADT/SetVector.h¶

LLVM’sSetVector<Type> is an adapter class that combines your choice of aset-like container along with aSequential Container Theimportant property that this provides is efficient insertion with uniquing(duplicate elements are ignored) with iteration support. It implements this byinserting elements into both a set-like container and the sequential container,using the set-like container for uniquing and the sequential container foriteration.

The difference between SetVector and other sets is that the order of iterationis guaranteed to match the order of insertion into the SetVector. This propertyis really important for things like sets of pointers. Because pointer valuesare non-deterministic (e.g. vary across runs of the program on differentmachines), iterating over the pointers in the set will not be in a well-definedorder.

The drawback of SetVector is that it requires twice as much space as a normalset and has the sum of constant factors from the set-like container and thesequential container that it uses. Use itonly if you need to iterate overthe elements in a deterministic order. SetVector is also expensive to deleteelements out of (linear time), unless you use its “pop_back” method, which isfaster.

SetVector is an adapter class that defaults to usingstd::vector and asize 16SmallSet for the underlying containers, so it is quite expensive.However,"llvm/ADT/SetVector.h" also provides aSmallSetVector class,which defaults to using aSmallVector andSmallSet of a specified size.If you use this, and if your sets are dynamically smaller thanN, you willsave a lot of heap traffic.

llvm/ADT/UniqueVector.h¶

UniqueVector is similar toSetVector but it retains aunique ID for each element inserted into the set. It internally contains a mapand a vector, and it assigns a unique ID for each value inserted into the set.

UniqueVector is very expensive: its cost is the sum of the cost of maintainingboth the map and vector, it has high complexity, high constant factors, andproduces a lot of malloc traffic. It should be avoided.

llvm/ADT/ImmutableSet.h¶

ImmutableSet is an immutable (functional) set implementation based on an AVLtree. Adding or removing elements is done through a Factory object and resultsin the creation of a new ImmutableSet object. If an ImmutableSet already existswith the given contents, then the existing one is returned; equality is comparedwith a FoldingSetNodeID. The time and space complexity of add or removeoperations is logarithmic in the size of the original set.

There is no method for returning an element of the set, you can only check formembership.

Other Set-Like Container Options¶

The STL provides several other options, such as std::multiset andstd::unordered_set. We never use containers like unordered_set becausethey are generally very expensive (each insertion requires a malloc).

std::multiset is useful if you’re not interested in elimination of duplicates,but has all the drawbacks ofstd::set. A sorted vector(where you don’t delete duplicate entries) or some other approach is almostalways better.

A sorted ‘vector’¶

If your usage pattern follows a strict insert-then-query approach, you cantrivially use the same approach assorted vectors for set-like containers. The only difference is that your query function (whichuses std::lower_bound to get efficient log(n) lookup) should only compare thekey, not both the key and value. This yields the same advantages as sortedvectors for sets.

llvm/ADT/StringMap.h¶

Strings are commonly used as keys in maps, and they are difficult to supportefficiently: they are variable length, inefficient to hash and compare whenlong, expensive to copy, etc. StringMap is a specialized container designed tocope with these issues. It supports mapping an arbitrary range of bytes to anarbitrary other object.

The StringMap implementation uses a quadratically-probed hash table, where thebuckets store a pointer to the heap allocated entries (and some other stuff).The entries in the map must be heap allocated because the strings are variablelength. The string data (key) and the element object (value) are stored in thesame allocation with the string data immediately after the element object.This container guarantees the “(char*)(&Value+1)” points to the key stringfor a value.

The StringMap is very fast for several reasons: quadratic probing is very cacheefficient for lookups, the hash value of strings in buckets is not recomputedwhen looking up an element, StringMap rarely has to touch the memory forunrelated objects when looking up a value (even when hash collisions happen),hash table growth does not recompute the hash values for strings already in thetable, and each pair in the map is store in a single allocation (the string datais stored in the same allocation as the Value of a pair).

StringMap also provides query methods that take byte ranges, so it only evercopies a string if a value is inserted into the table.

StringMap iteration order, however, is not guaranteed to be deterministic, soany uses which require that should instead use a std::map.

llvm/ADT/IndexedMap.h¶

IndexedMap is a specialized container for mapping small dense integers (orvalues that can be mapped to small dense integers) to some other type. It isinternally implemented as a vector with a mapping function that maps the keysto the dense integer range.

This is useful for cases like virtual registers in the LLVM code generator: theyhave a dense mapping that is offset by a compile-time constant (the firstvirtual register ID).

llvm/ADT/DenseMap.h¶

DenseMap is a simple quadratically probed hash table. It excels at supportingsmall keys and values: it uses a single allocation to hold all of the pairsthat are currently inserted in the map. DenseMap is a great way to mappointers to pointers, or map other small types to each other.

There are several aspects of DenseMap that you should be aware of, however.The iterators in a DenseMap are invalidated whenever an insertion occurs,unlike map. Also, because DenseMap allocates space for a large number ofkey/value pairs (it starts with 64 by default), it will waste a lot of space ifyour keys or values are large. Finally, you must implement a partialspecialization of DenseMapInfo for the key that you want, if it isn’t alreadysupported. This is required to tell DenseMap about two special marker values(which can never be inserted into the map) that it needs internally.

DenseMap’s find_as() method supports lookup operations using an alternate keytype. This is useful in cases where the normal key type is expensive toconstruct, but cheap to compare against. The DenseMapInfo is responsible fordefining the appropriate comparison and hashing methods for each alternate keytype used.

DenseMap.h also contains a SmallDenseMap variant, that similar toSmallVector performs no heap allocation until thenumber of elements in the template parameter N are exceeded.

llvm/IR/ValueMap.h¶

ValueMap is a wrapper around aDenseMap mappingValue*s (or subclasses) to another type. When a Value is deleted orRAUW’ed, ValueMap will update itself so the new version of the key is mapped tothe same value, just as if the key were a WeakVH. You can configure exactly howthis happens, and what else happens on these two events, by passing aConfigparameter to the ValueMap template.

llvm/ADT/IntervalMap.h¶

IntervalMap is a compact map for small keys and values. It maps key intervalsinstead of single keys, and it will automatically coalesce adjacent intervals.When the map only contains a few intervals, they are stored in the map objectitself to avoid allocations.

The IntervalMap iterators are quite big, so they should not be passed around asSTL iterators. The heavyweight iterators allow a smaller data structure.

llvm/ADT/IntervalTree.h¶

llvm::IntervalTree is a light tree data structure to hold intervals. Itallows finding all intervals that overlap with any given point. At this time,it does not support any deletion or rebalancing operations.

The IntervalTree is designed to be set up once, and then queried without anyfurther additions.

<map>¶

std::map has similar characteristics tostd::set: it uses asingle allocation per pair inserted into the map, it offers log(n) lookup withan extremely large constant factor, imposes a space penalty of 3 pointers perpair in the map, etc.

std::map is most useful when your keys or values are very large, if you need toiterate over the collection in sorted order, or if you need stable iteratorsinto the map (i.e. they don’t get invalidated if an insertion or deletion ofanother element takes place).

llvm/ADT/MapVector.h¶

MapVector<KeyT,ValueT> provides a subset of the DenseMap interface. Themain difference is that the iteration order is guaranteed to be the insertionorder, making it an easy (but somewhat expensive) solution for non-deterministiciteration over maps of pointers.

It is implemented by mapping from key to an index in a vector of key,valuepairs. This provides fast lookup and iteration, but has two main drawbacks:the key is stored twice and removing elements takes linear time. If it isnecessary to remove elements, it’s best to remove them in bulk usingremove_if().

llvm/ADT/IntEqClasses.h¶

IntEqClasses provides a compact representation of equivalence classes of smallintegers. Initially, each integer in the range 0..n-1 has its own equivalenceclass. Classes can be joined by passing two class representatives to thejoin(a, b) method. Two integers are in the same class when findLeader() returnsthe same representative.

Once all equivalence classes are formed, the map can be compressed so eachinteger 0..n-1 maps to an equivalence class number in the range 0..m-1, where mis the total number of equivalence classes. The map must be uncompressed beforeit can be edited again.

llvm/ADT/ImmutableMap.h¶

ImmutableMap is an immutable (functional) map implementation based on an AVLtree. Adding or removing elements is done through a Factory object and resultsin the creation of a new ImmutableMap object. If an ImmutableMap already existswith the given key set, then the existing one is returned; equality is comparedwith a FoldingSetNodeID. The time and space complexity of add or removeoperations is logarithmic in the size of the original map.

Other Map-Like Container Options¶

The STL provides several other options, such as std::multimap andstd::unordered_map. We never use containers like unordered_map becausethey are generally very expensive (each insertion requires a malloc).

std::multimap is useful if you want to map a key to multiple values, but has allthe drawbacks of std::map. A sorted vector or some other approach is almostalways better.

BitVector¶

The BitVector container provides a dynamic size set of bits for manipulation.It supports individual bit setting/testing, as well as set operations. The setoperations take time O(size of bitvector), but operations are performed one wordat a time, instead of one bit at a time. This makes the BitVector very fast forset operations compared to other containers. Use the BitVector when you expectthe number of set bits to be high (i.e. a dense set).

SmallBitVector¶

The SmallBitVector container provides the same interface as BitVector, but it isoptimized for the case where only a small number of bits, less than 25 or so,are needed. It also transparently supports larger bit counts, but slightly lessefficiently than a plain BitVector, so SmallBitVector should only be used whenlarger counts are rare.

At this time, SmallBitVector does not support set operations (and, or, xor), andits operator[] does not provide an assignable lvalue.

SparseBitVector¶

The SparseBitVector container is much like BitVector, with one major difference:Only the bits that are set, are stored. This makes the SparseBitVector muchmore space efficient than BitVector when the set is sparse, as well as makingset operations O(number of set bits) instead of O(size of universe). Thedownside to the SparseBitVector is that setting and testing of random bits isO(N), and on large SparseBitVectors, this can be slower than BitVector. In ourimplementation, setting or testing bits in sorted order (either forwards orreverse) is O(1) worst case. Testing and setting bits within 128 bits (dependson size) of the current bit is also O(1). As a general statement,testing/setting bits in a SparseBitVector is O(distance away from last set bit).

CoalescingBitVector¶

The CoalescingBitVector container is similar in principle to a SparseBitVector,but is optimized to represent large contiguous ranges of set bits compactly. Itdoes this by coalescing contiguous ranges of set bits into intervals. Searchingfor a bit in a CoalescingBitVector is O(log(gaps between contiguous ranges)).

CoalescingBitVector is a better choice than BitVector when gaps between rangesof set bits are large. It’s a better choice than SparseBitVector when find()operations must have fast, predictable performance. However, it’s not a goodchoice for representing sets which have lots of very short ranges. E.g. the set{2*x : x in [0, n)} would be a pathological input.

Thezip* functions¶

zip* functions allow for iterating over elements from two or more rangesat the same time. For example:

SmallVector<size_t>Counts=...;charLetters[26]=...;for(auto[Letter,Count]:zip_equal(Letters,Counts))errs()<<Letter<<": "<<Count<<"\n";

Note that the elements are provided through a ‘reference wrapper’ proxy type(tuple of references), which combined with the structured bindings declarationmakesLetter andCount references to range elements. Any modificationto these references will affect the elements ofLetters orCounts.

Thezip* functions support temporary ranges, for example:

for(auto[Letter,Count]:zip(SmallVector<char>{'a','b','c'},Counts))errs()<<Letter<<": "<<Count<<"\n";

The difference between the functions in thezip family is how they behavewhen the supplied ranges have different lengths:

• zip_equal – requires all input ranges have the same length.

• zip – iteration stops when the end of the shortest range is reached.

• zip_first – requires the first range is the shortest one.

• zip_longest – iteration continues until the end of the longest range isreached. The non-existent elements of shorter ranges are replaced withstd::nullopt.

The length requirements are checked withasserts.

As a rule of thumb, prefer to usezip_equal when you expect allranges to have the same lengths, and consider alternativezip functions onlywhen this is not the case. This is becausezip_equal clearly communicatesthis same-length assumption and has the best (release-mode) runtime performance.

enumerate¶

Theenumerate functions allows to iterate over one or more ranges whilekeeping track of the index of the current loop iteration. For example:

for(auto[Idx,BB,Value]:enumerate(Phi->blocks(),Phi->incoming_values()))errs()<<"#"<<Idx<<" "<<BB->getName()<<": "<<*Value<<"\n";

The current element index is provided as the first structured bindings element.Alternatively, the index and the element value can be obtained with theindex() andvalue() member functions:

charLetters[26]=...;for(autoEn:enumerate(Letters))errs()<<"#"<<En.index()<<" "<<En.value()<<"\n";

Note thatenumerate haszip_equal semantics and provides elementsthrough a ‘reference wrapper’ proxy, which makes them modifiable when accessedthrough structured bindings or thevalue() member function. When two or moreranges are passed,enumerate requires them to have equal lengths (checkedwith anassert).

Iterating over theBasicBlock in aFunction¶

It’s quite common to have aFunction instance that you’d like to transformin some way; in particular, you’d like to manipulate itsBasicBlocks. Tofacilitate this, you’ll need to iterate over all of theBasicBlocks thatconstitute theFunction. The following is an example that prints the nameof aBasicBlock and the number ofInstructions it contains:

Function&Func=...for(BasicBlock&BB:Func)// Print out the name of the basic block if it has one, and then the// number of instructions that it containserrs()<<"Basic block (name="<<BB.getName()<<") has "<<BB.size()<<" instructions.\n";

Iterating over theInstruction in aBasicBlock¶

Just like when dealing withBasicBlocks inFunctions, it’s easy toiterate over the individual instructions that make upBasicBlocks. Here’sa code snippet that prints out each instruction in aBasicBlock:

BasicBlock&BB=...for(Instruction&I:BB)// The next statement works since operator<<(ostream&,...)// is overloaded for Instruction&errs()<<I<<"\n";

However, this isn’t really the best way to print out the contents of aBasicBlock! Since the ostream operators are overloaded for virtuallyanything you’ll care about, you could have just invoked the print routine on thebasic block itself:errs()<<BB<<"\n";.

Iterating over theInstruction in aFunction¶

If you’re finding that you commonly iterate over aFunction’sBasicBlocks and then thatBasicBlock’sInstructions,InstIterator should be used instead. You’ll need to includellvm/IR/InstIterator.h (doxygen) and then instantiateInstIterators explicitly in your code. Here’s a small example that showshow to dump all instructions in a function to the standard error stream:

#include"llvm/IR/InstIterator.h"// F is a pointer to a Function instancefor(inst_iteratorI=inst_begin(F),E=inst_end(F);I!=E;++I)errs()<<*I<<"\n";

Easy, isn’t it? You can also useInstIterators to fill a work list withits initial contents. For example, if you wanted to initialize a work list tocontain all instructions in aFunction F, all you would need to do issomething like:

std::set<Instruction*>worklist;// or better yet, SmallPtrSet<Instruction*, 64> worklist;for(inst_iteratorI=inst_begin(F),E=inst_end(F);I!=E;++I)worklist.insert(&*I);

The STL setworklist would now contain all instructions in theFunctionpointed to by F.

Turning an iterator into a class pointer (and vice-versa)¶

Sometimes, it’ll be useful to grab a reference (or pointer) to a class instancewhen all you’ve got at hand is an iterator. Well, extracting a reference or apointer from an iterator is very straight-forward. Assuming thati is aBasicBlock::iterator andj is aBasicBlock::const_iterator:

Instruction&inst=*i;// Grab reference to instruction referenceInstruction*pinst=&*i;// Grab pointer to instruction referenceconstInstruction&inst=*j;

It’s also possible to turn a class pointer into the corresponding iterator, andthis is a constant time operation (very efficient). The following code snippetillustrates use of the conversion constructors provided by LLVM iterators. Byusing these, you can explicitly grab the iterator of something without actuallyobtaining it via iteration over some structure:

voidprintNextInstruction(Instruction*inst){BasicBlock::iteratorit(inst);++it;// After this line, it refers to the instruction after *instif(it!=inst->getParent()->end())errs()<<*it<<"\n";}

Finding call sites: a slightly more complex example¶

Say that you’re writing a FunctionPass and would like to count all the locationsin the entire module (that is, across everyFunction) where a certainfunction (i.e., someFunction*) is already in scope. As you’ll learnlater, you may want to use anInstVisitor to accomplish this in a much morestraight-forward manner, but this example will allow us to explore how you’d doit if you didn’t haveInstVisitor around. In pseudo-code, this is what wewant to do:

initialize callCounter to zerofor each Function f in the Module  for each BasicBlock b in f    for each Instruction i in b      if (i a Call and calls the given function)        increment callCounter

And the actual code is (remember, because we’re writing aFunctionPass, ourFunctionPass-derived class simply has to override therunOnFunctionmethod):

Function*targetFunc=...;classOurFunctionPass:publicFunctionPass{public:OurFunctionPass():callCounter(0){}virtualrunOnFunction(Function&F){for(BasicBlock&B:F){for(Instruction&I:B){if(auto*CB=dyn_cast<CallBase>(&I)){// We know we've encountered some kind of call instruction (call,// invoke, or callbr), so we need to determine if it's a call to// the function pointed to by m_func or not.if(CB->getCalledFunction()==targetFunc)++callCounter;}}}}private:unsignedcallCounter;};

Iterating over def-use & use-def chains¶

Frequently, we might have an instance of theValue class (doxygen) and we want to determinewhichUsers use theValue. The list of allUsers of a particularValue is called adef-use chain. For example, let’s say we have aFunction* namedF to a particular functionfoo. Finding all of theinstructions thatusefoo is as simple as iterating over thedef-usechain ofF:

Function*F=...;for(User*U:F->users()){if(Instruction*Inst=dyn_cast<Instruction>(U)){errs()<<"F is used in instruction:\n";errs()<<*Inst<<"\n";}

Alternatively, it’s common to have an instance of theUser Class (doxygen) and need to know whatValues are used by it. The list of allValues used by aUser isknown as ause-def chain. Instances of classInstruction are commonUser s, so we might want to iterate over all of the values that a particularinstruction uses (that is, the operands of the particularInstruction):

Instruction*pi=...;for(Use&U:pi->operands()){Value*v=U.get();// ...}

Declaring objects asconst is an important tool of enforcing mutation freealgorithms (such as analyses, etc.). For this purpose above iterators come inconstant flavors asValue::const_use_iterator andValue::const_op_iterator. They automatically arise when callinguse/op_begin() onconstValue*s orconstUser*s respectively.Upon dereferencing, they returnconstUse*s. Otherwise the above patternsremain unchanged.

Iterating over predecessors & successors of blocks¶

Iterating over the predecessors and successors of a block is quite easy with theroutines defined in"llvm/IR/CFG.h". Just use code like this toiterate over all predecessors of BB:

#include"llvm/IR/CFG.h"BasicBlock*BB=...;for(BasicBlock*Pred:predecessors(BB)){// ...}

Similarly, to iterate over successors usesuccessors.

Creating and inserting newInstructions¶

Instantiating Instructions

Creation ofInstructions is straight-forward: simply call the constructorfor the kind of instruction to instantiate and provide the necessary parameters.For example, anAllocaInst onlyrequires a (const-ptr-to)Type. Thus:

auto*ai=newAllocaInst(Type::Int32Ty);

will create anAllocaInst instance that represents the allocation of oneinteger in the current stack frame, at run time. EachInstruction subclassis likely to have varying default parameters which change the semantics of theinstruction, so refer to thedoxygen documentation for the subclass ofInstruction thatyou’re interested in instantiating.

Naming values

It is very useful to name the values of instructions when you’re able to, asthis facilitates the debugging of your transformations. If you end up lookingat generated LLVM machine code, you definitely want to have logical namesassociated with the results of instructions! By supplying a value for theName (default) parameter of theInstruction constructor, you associate alogical name with the result of the instruction’s execution at run time. Forexample, say that I’m writing a transformation that dynamically allocates spacefor an integer on the stack, and that integer is going to be used as some kindof index by some other code. To accomplish this, I place anAllocaInst atthe first point in the firstBasicBlock of someFunction, and I’mintending to use it within the sameFunction. I might do:

auto*pa=newAllocaInst(Type::Int32Ty,0,"indexLoc");

whereindexLoc is now the logical name of the instruction’s execution value,which is a pointer to an integer on the run time stack.

Inserting instructions

There are essentially three ways to insert anInstruction into an existingsequence of instructions that form aBasicBlock:

• Insertion into the instruction list of theBasicBlock

  Given aBasicBlock*pb, anInstruction*pi within thatBasicBlock,and a newly-created instruction we wish to insert before*pi, we do thefollowing:

  BasicBlock*pb=...;Instruction*pi=...;auto*newInst=newInstruction(...);newInst->insertBefore(pi);// Inserts newInst before pi

  Appending to the end of aBasicBlock is so common that theInstructionclass andInstruction-derived classes provide constructors which take apointer to aBasicBlock to be appended to. For example code that lookedlike:

  BasicBlock*pb=...;auto*newInst=newInstruction(...);newInst->insertInto(pb,pb->end());// Appends newInst to pb

  becomes:

  BasicBlock*pb=...;auto*newInst=newInstruction(...,pb);

  which is much cleaner, especially if you are creating long instructionstreams.

• Insertion using an instance ofIRBuilder

  Inserting severalInstructions can be quite laborious using the previousmethods. TheIRBuilder is a convenience class that can be used to addseveral instructions to the end of aBasicBlock or before a particularInstruction. It also supports constant folding and renaming namedregisters (seeIRBuilder’s template arguments).

  The example below demonstrates a very simple use of theIRBuilder wherethree instructions are inserted before the instructionpi. The first twoinstructions are Call instructions and third instruction multiplies the returnvalue of the two calls.

  Instruction*pi=...;IRBuilder<>Builder(pi);CallInst*callOne=Builder.CreateCall(...);CallInst*callTwo=Builder.CreateCall(...);Value*result=Builder.CreateMul(callOne,callTwo);

  The example below is similar to the above example except that the createdIRBuilder inserts instructions at the end of theBasicBlockpb.

  BasicBlock*pb=...;IRBuilder<>Builder(pb);CallInst*callOne=Builder.CreateCall(...);CallInst*callTwo=Builder.CreateCall(...);Value*result=Builder.CreateMul(callOne,callTwo);

  SeeKaleidoscope Tutorial for a practical use of theIRBuilder.

Deleting Instructions¶

Deleting an instruction from an existing sequence of instructions that form aBasicBlock is very straight-forward: just call the instruction’seraseFromParent() method. For example:

Instruction*I=..;I->eraseFromParent();

This unlinks the instruction from its containing basic block and deletes it. Ifyou’d just like to unlink the instruction from its containing basic block butnot delete it, you can use theremoveFromParent() method.

Replacing an Instruction with another Value¶

Deleting GlobalVariables¶

Deleting a global variable from a module is just as easy as deleting anInstruction. First, you must have a pointer to the global variable that youwish to delete. You use this pointer to erase it from its parent, the module.For example:

GlobalVariable*GV=..;GV->eraseFromParent();

Interaction and relationship betweenUser andUse objects¶

A subclass ofUser can choose between incorporating itsUse objects orrefer to them out-of-line by means of a pointer. A mixed variant (someUses inline others hung off) is impractical and breaks the invariant that theUse objects belonging to the sameUser form a contiguous array.

We have 2 different layouts in theUser (sub)classes:

• Layout a)

  TheUse object(s) are inside (resp. at fixed offset) of theUserobject and there are a fixed number of them.

• Layout b)

  TheUse object(s) are referenced by a pointer to an array from theUser object and there may be a variable number of them.

As of v2.4 each layout still possesses a direct pointer to the start of thearray ofUses. Though not mandatory for layout a), we stick to thisredundancy for the sake of simplicity. TheUser object also stores thenumber ofUse objects it has. (Theoretically this information can also becalculated given the scheme presented below.)

Special forms of allocation operators (operatornew) enforce the followingmemory layouts:

• Layout a) is modelled by prepending theUser object by theUse[]array.

  ...---.---.---.---.-------...  | P | P | P | P | User'''---'---'---'---'-------'''

• Layout b) is modelled by pointing at theUse[] array.

  .-------...| User'-------'''    |    v    .---.---.---.---...    | P | P | P | P |    '---'---'---'---'''

(In the above figures ‘P’stands for theUse**that is stored ineachUseobject in the memberUse::Prev)

Important Public Methods¶

• boolisIntegerTy()const: Returns true for any integer type.

• boolisFloatingPointTy(): Return true if this is one of the fivefloating point types.

• boolisSized(): Return true if the type has known size. Thingsthat don’t have a size are abstract types, labels and void.

Important Derived Types¶

IntegerType

Subclass of DerivedType that represents integer types of any bit width. Anybit width betweenIntegerType::MIN_INT_BITS (1) andIntegerType::MAX_INT_BITS (~8 million) can be represented.

• staticconstIntegerType*get(unsignedNumBits): get an integertype of a specific bit width.

• unsignedgetBitWidth()const: Get the bit width of an integer type.

SequentialType

This is subclassed by ArrayType and VectorType.

• constType*getElementType()const: Returns the type of eachof the elements in the sequential type.

• uint64_tgetNumElements()const: Returns the number of elementsin the sequential type.

ArrayType

This is a subclass of SequentialType and defines the interface for arraytypes.

PointerType

Subclass of Type for pointer types.

VectorType

Subclass of SequentialType for vector types. A vector type is similar to anArrayType but is distinguished because it is a first class type whereasArrayType is not. Vector types are used for vector operations and are usuallysmall vectors of an integer or floating point type.

StructType

Subclass of DerivedTypes for struct types.

FunctionType

Subclass of DerivedTypes for function types.

• boolisVarArg()const: Returns true if it’s a vararg function.

• constType*getReturnType()const: Returns the return type of thefunction.

• constType*getParamType(unsignedi): Returns the type of the ithparameter.

• constunsignedgetNumParams()const: Returns the number of formalparameters.

Important Public Members of theModule class¶

• Module::Module(std::stringname="")

  Constructing aModule is easy. You can optionally provide a name for it(probably based on the name of the translation unit).

• Module::iterator - Typedef for function list iterator

  Module::const_iterator - Typedef for const_iterator.

  begin(),end(),size(),empty()

  These are forwarding methods that make it easy to access the contents of aModule object’sFunction list.

• Module::FunctionListType&getFunctionList()

  Returns the list ofFunctions. This is necessary to usewhen you need to update the list or perform a complex action that doesn’t havea forwarding method.

• Module::global_iterator - Typedef for global variable list iterator

  Module::const_global_iterator - Typedef for const_iterator.

  Module::insertGlobalVariable() - Inserts a global variable to the list.

  Module::removeGlobalVariable() - Removes a global variable from the list.

  Module::eraseGlobalVariable() - Removes a global variable from the list and deletes it.

  global_begin(),global_end(),global_size(),global_empty()

  These are forwarding methods that make it easy to access the contents of aModule object’sGlobalVariable list.

• SymbolTable*getSymbolTable()

  Return a reference to theSymbolTable for thisModule.

• Function*getFunction(StringRefName)const

  Look up the specified function in theModuleSymbolTable. If it does notexist, returnnull.

• FunctionCalleegetOrInsertFunction(conststd::string&Name,constFunctionType*T)

  Look up the specified function in theModuleSymbolTable. Ifit does not exist, add an external declaration for the function andreturn it. Note that the function signature already present may notmatch the requested signature. Thus, in order to enable the commonusage of passing the result directly to EmitCall, the return type isa struct of{FunctionType*T,Constant*FunctionPtr}, ratherthan simply theFunction* with potentially an unexpectedsignature.

• std::stringgetTypeName(constType*Ty)

  If there is at least one entry in theSymbolTable for the specifiedType,return it. Otherwise return the empty string.

• booladdTypeName(conststd::string&Name,constType*Ty)

  Insert an entry in theSymbolTable mappingName toTy. If there isalready an entry for this name, true is returned and theSymbolTable is notmodified.

Important Public Members of theValue class¶

• Value::use_iterator - Typedef for iterator over the use-list

  Value::const_use_iterator - Typedef for const_iterator over theuse-list

  unsigneduse_size() - Returns the number of users of the value.

  booluse_empty() - Returns true if there are no users.

  use_iteratoruse_begin() - Get an iterator to the start of theuse-list.

  use_iteratoruse_end() - Get an iterator to the end of the use-list.

  User*use_back() - Returns the last element in the list.

  These methods are the interface to access the def-use information in LLVM.As with all other iterators in LLVM, the naming conventions follow theconventions defined by theSTL.

• Type*getType()constThis method returns the Type of the Value.

• boolhasName()const

  std::stringgetName()const

  voidsetName(conststd::string&Name)

  This family of methods is used to access and assign a name to aValue, beaware of theprecaution above.

• voidreplaceAllUsesWith(Value*V)

  This method traverses the use list of aValue changing allUsers of thecurrent value to refer to “V” instead. For example, if you detect that aninstruction always produces a constant value (for example through constantfolding), you can replace all uses of the instruction with the constant likethis:

  Inst->replaceAllUsesWith(ConstVal);

Important Public Members of theUser class¶

TheUser class exposes the operand list in two ways: through an index accessinterface and through an iterator based interface.

• Value*getOperand(unsignedi)

  unsignedgetNumOperands()

  These two methods expose the operands of theUser in a convenient form fordirect access.

• User::op_iterator - Typedef for iterator over the operand list

  op_iteratorop_begin() - Get an iterator to the start of the operandlist.

  op_iteratorop_end() - Get an iterator to the end of the operand list.

  Together, these methods make up the iterator based interface to the operandsof aUser.

Important Subclasses of theInstruction class¶

• BinaryOperator

  This subclasses represents all two operand instructions whose operands must bethe same type, except for the comparison instructions.

• CastInstThis subclass is the parent of the 12 casting instructions. It providescommon operations on cast instructions.

• CmpInst

  This subclass represents the two comparison instructions,ICmpInst (integer operands), andFCmpInst (floating point operands).

Important Public Members of theInstruction class¶

• BasicBlock*getParent()

  Returns theBasicBlock that thisInstruction is embedded into.

• boolmayWriteToMemory()

  Returns true if the instruction writes to memory, i.e. it is acall,free,invoke, orstore.

• unsignedgetOpcode()

  Returns the opcode for theInstruction.

• Instruction*clone()const

  Returns another instance of the specified instruction, identical in all waysto the original except that the instruction has no parent (i.e. it’s notembedded into aBasicBlock), and it has no name.

Important Subclasses of Constant¶

• ConstantInt : This subclass of Constant represents an integer constant ofany width.

  • constAPInt&getValue()const: Returns the underlyingvalue of this constant, an APInt value.

  • int64_tgetSExtValue()const: Converts the underlying APInt value to anint64_t via sign extension. If the value (not the bit width) of the APIntis too large to fit in an int64_t, an assertion will result. For thisreason, use of this method is discouraged.

  • uint64_tgetZExtValue()const: Converts the underlying APInt valueto a uint64_t via zero extension. IF the value (not the bit width) of theAPInt is too large to fit in a uint64_t, an assertion will result. For thisreason, use of this method is discouraged.

  • staticConstantInt*get(constAPInt&Val): Returns the ConstantIntobject that represents the value provided byVal. The type is impliedas the IntegerType that corresponds to the bit width ofVal.

  • staticConstantInt*get(constType*Ty,uint64_tVal): Returns theConstantInt object that represents the value provided byVal for integertypeTy.

• ConstantFP : This class represents a floating point constant.

  • doublegetValue()const: Returns the underlying value of this constant.

• ConstantArray : This represents a constant array.

  • conststd::vector<Use>&getValues()const: Returns a vector ofcomponent constants that makeup this array.

• ConstantStruct : This represents a constant struct.

  • conststd::vector<Use>&getValues()const: Returns a vector ofcomponent constants that makeup this array.

• GlobalValue : This represents either a global variable or a function. Ineither case, the value is a constant fixed address (after linking).

Important Public Members of theGlobalValue class¶

• boolhasInternalLinkage()const

  boolhasExternalLinkage()const

  voidsetInternalLinkage(boolHasInternalLinkage)

  These methods manipulate the linkage characteristics of theGlobalValue.

• Module*getParent()

  This returns theModule that theGlobalValue is currently embedded into.

Important Public Members of theFunction¶

• Function(constFunctionType*Ty,LinkageTypesLinkage,conststd::string&N="",Module*Parent=0)

  Constructor used when you need to create newFunctions to add theprogram. The constructor must specify the type of the function to create andwhat type of linkage the function should have. TheFunctionType argumentspecifies the formal arguments and return value for the function. The sameFunctionType value can be used to create multiple functions. TheParentargument specifies the Module in which the function is defined. If thisargument is provided, the function will automatically be inserted into thatmodule’s list of functions.

• boolisDeclaration()

  Return whether or not theFunction has a body defined. If the function is“external”, it does not have a body, and thus must be resolved by linking witha function defined in a different translation unit.

• Function::iterator - Typedef for basic block list iterator

  Function::const_iterator - Typedef for const_iterator.

  begin(),end(),size(),empty(),insert(),splice(),erase()

  These are forwarding methods that make it easy to access the contents of aFunction object’sBasicBlock list.

• Function::arg_iterator - Typedef for the argument list iterator

  Function::const_arg_iterator - Typedef for const_iterator.

  arg_begin(),arg_end(),arg_size(),arg_empty()

  These are forwarding methods that make it easy to access the contents of aFunction object’sArgument list.

• Function::ArgumentListType&getArgumentList()

  Returns the list ofArgument. This is necessary to use when you need toupdate the list or perform a complex action that doesn’t have a forwardingmethod.

• BasicBlock&getEntryBlock()

  Returns the entryBasicBlock for the function. Because the entry blockfor the function is always the first block, this returns the first block oftheFunction.

• Type*getReturnType()

  FunctionType*getFunctionType()

  This traverses theType of theFunction and returns the return type ofthe function, or theFunctionType of the actual function.

• SymbolTable*getSymbolTable()

  Return a pointer to theSymbolTable for thisFunction.