原文地址：http://llvm.lyngvig.org/Articles/Mapping-High-Level-Constructs-to-LLVM-IR

Mapping High-Level Constructs to LLVM IR

Table of Contents

Introduction

A Quick Primer

Some Useful LLVM Tools

Mapping Basic Constructs to LLVM IR

Global Variables

Local Variables

Constants

Constant Expressions

Size-Of Computations

Function Prototypes

Function Definitions

Simple Public Functions

Simple Private Functions

Functions with a Variable Number of Parameters

Exception-Aware Functions

Function Pointers

Casts

Bitwise Casts

Zero-Extending Casts (Unsigned Upcasts)

Sign-Extending Casts (Signed Upcasts)

Truncating Casts (Signed and Unsigned Downcasts)

Floating-Point Extending Casts (Float Upcasts)

Floating-Point Truncating Casts (Float Downcasts)

Pointer-to-Integer Casts

Integer-to-Pointer Casts

Address-Space Casts (Pointer Casts)

Incomplete Structure Types

Structures

Nested Structures

Unions

Structure Expressions

Getting a Pointer to a Structure Member

Mapping Control Structures to LLVM IR

Mapping Advanced Constructs to LLVM IR

Lambda Functions

Closures

Generators

Mapping Exception Handling to LLVM IR

Exception Handling by Propagated Return Value

Setjmp/Longjmp Exception Handling

Zero Cost Exception Handling

Resources

Mapping Object-Oriented Constructs to LLVM IR

Classes

Virtual Methods

Single Inheritance

Multiple Inheritance

Virtual Inheritance

Interfaces

Boxing and Unboxing

Class Equivalence Test

Class Inheritance Test

The New Operator

The Instance New Operator

The Array New Operator

Interoperating with a Runtime Library

Interfacing to the Operating System

How to Interface to POSIX Operating Systems

Sample POSIX "Hello World" Application

How to Interface to the Windows Operating System

Sample Windows "Hello World" Application

Resources

Epilogue

Appendix A: How to Implement a String Type in LLVM

Appendix B: Task List

Introduction

In this document we will take a look at how to map various classic high-level programming language constructs to LLVM IR. The purpose of the document is to make the learning curve less steep for aspiring LLVM users.

For the sake of simplicity, we'll be working with a 32-bit target machine so that pointers and word-sized operands are 32-bits.

Also, for the sake of readability we do not mangle (encode) names. Rather, they are given simple, easy-to-read names that reflect their purpose. A production compiler for any language that supports overloading would generally need to
mangle the names so as to avoid conflicts between symbols.

A Quick Primer

Here are a few things that you should know before reading this document:

1. LLVM IR is not machine code, but sort of the step just above assembly.
2. LLVM IR is highly typed so expect to be told when you do something wrong.
3. LLVM IR does not differentiate between signed and unsigned integers.
4. LLVM IR assumes two's complement signed integers so that say trunc works equally well on signed and unsigned integers.
5. Global symbols begin with an at sign (@).
6. Local symbols begin with a percent symbol (%).
7. All symbols must be declared or defined.
8. Don't worry that the LLVM IR at times can seem somewhat lengthy when it comes to expressing something; the optimizer will ensure the output is well optimized and you'll often see two or three LLVM IR instructions be coalesced
   into a single machine code instruction.
9. If in doubt, consult the Language Reference. If there is a conflict between the Language Reference and this document, this document is wrong!
10. All LLVM IR examples are presented without a data layout and without a target triple. You need to add those yourself, if you want to actually build and run the samples. Get them from Clang for your platform.

Some Useful LLVM Tools

The most important LLVM tools for use with this article are as follows:

Name	Function	Reads	Writes	Arguments
clang	C Compiler	.c	.ll	-c -emit-llvm -S
clang++	C++ Compiler	.cpp	.ll	-c -emit-llvm -S
llvm-dis	Disassembler	.bc	.ll
opt	Optimizer	.bc/.ll	same
llc	IR Compiler	.ll	.s

While you are playing around with generating or writing LLVM IR, you may want to add the option -fsanitize=undefined to
Clang/Clang++ insofar you use either of those. This option makes Clang/Clang++ insert run-time checks in places where it would normally output an ud2 instruction.
This will likely save you some trouble if you happen to generate undefined LLVM IR. Please notice that this option only works for C and C++ compiles.

Mapping Basic Constructs to LLVM IR

In this chapter, we'll look at the most basic and simple constructs that are part of nearly all imperative/OOP languages out there.

Global Variables

Global varibles are trivial to implement in LLVM IR:

Becomes:

Please notice that LLVM views global variables as pointers; so you must explicitly dereference the global variable using the loadinstruction
when accessing its value, likewise you must explicitly store the value of a global variable using the store instruction.

Local Variables

There are two kinds of local variables in LLVM:

1. Register-allocated local variables (temporaries).
2. Stack-allocated local variables.

The former is created by introducing a new symbol for the variable:

The latter is created by allocating the variable on the stack:

Please notice that alloca yields a pointer to the allocated type. As is generally the case in LLVM, you must explicitly
use a loador store instruction to read
or write the value respectively.

The use of alloca allows for a neat trick that can simplify your code generator in some cases. The trick is to explicitly
allocate all mutable variables, including arguments, on the stack, initialize them with the appropriate initial value and then operate on the stack as if that was your end goal. The trick is to run the "memory to register promotion" pass on your code as part
of the optimization phase. This will make LLVM store as many of the stack variables in registers as it possibly can. That way you don't have to ensure that the generated program is in SSA form but can generate code without having to worry about this aspect
of the code generation.

This trick is also described in chapter 7.4, Mutable
Variables in Kaleidoscope, in the OCaml tutorial on the LLVM website.

Constants

There are two different kinds of constants:

1. Constants that do not occupy allocated memory.
2. Constants that do occupy allocated memory.

The former are always expanded inline by the compiler as there is no LLVM IR equivalent of those. In other words, the compiler simply inserts the constant value wherever it is being used in a computation:

Constants that do occupy memory are defined using the constant keyword:

Such a constant is really a global variable whose visibility can be limited with private or internal so
that it is invisible outside the current module.

Constant Expressions

TODO: Document the various forms of constant expressions that exist and .. how they can be very useful. For instance,getelementptr constant
expressions are almost unavoidable in all but the simplest programs.

Size-Of Computations

Even though the compiler ought to know the exact size of everything in use (for statically checked languages), it can at times be convenient to ask LLVM to figure out the size of a structure for you. This is done with the following
little snippet of code:

@Struct_size will now contain the size of the structure %Struct.
The trick is to compute the offset of the second element in the zero-based array starting at null and that way get the size of the structure.

Function Prototypes

A function prototype, aka a profile, is translated into an equivalent declare declaration in LLVM IR:

Becomes:

Or you can leave out the descriptive parameter name:

Function Definitions

The translation of function definitions depends on a range of factors, ranging from the calling convention in use, whether the function is exception-aware or not, and if the function is to be publicly available outside the module.

Simple Public Functions

The most basic model is:

Becomes:

Simple Private Functions

A static function is a function private to a module that cannot be referenced from outside of the defining module:

Functions with a Variable Number of Parameters

To call a so-called vararg function, you first need to define or declare it using the elipsis (...) and then you need to make use of a special syntax for function calls that allows you to explictly list the types of the parameters of
the function that is being called. This "hack" exists to allow overriding a call to a function such as a function with variable parameters. Please notice that you only need to specify the return type once, not twice as you'd have to do if it was a true cast:

Exception-Aware Functions

A function that is aware of being part of a larger scheme of exception-handling is called an exception-aware function. Depending upon the type of exception handling being employed, the function may either return a pointer to an exception
instance, create a setjmp/longjmp frame, or simply
specify the uwtable (for UnWind Table) attribute. These cases will all be covered in great detail in the chapter on Exception
Handling below.

Function Pointers

Function pointers are expressed almost like in C and C++:

Becomes:

Casts

There are nine different types of casts:

1. Bitwise casts (type casts).
2. Zero-extending casts (unsigned upcasts).
3. Sign-extending casts (signed upcasts).
4. Truncating casts (signed and unsigned downcasts).
5. Floating-point extending casts (float upcasts).
6. Floating-point truncating casts (float downcasts).
7. Pointer-to-integer casts (todo: Document pointer-to-integer casts).
8. Integer-to-pointer casts (todo: Document integer-to-pointer casts).
9. Address-space casts (pointer casts).

Bitwise Casts

A bitwise cast (bitcast) reinterprets a given bit pattern without changing any bits in the operand. For instance, you could make a bitcast of
a pointer to byte into a pointer to some structure as follows:

Becomes:

Zero-Extending Casts (Unsigned Upcasts)

To upcast an unsigned value like in the example below:

You use the zext instruction:

Sign-Extending Casts (Signed Upcasts)

To upcast a signed value, you replace the zext instruction with the sext instruction
and everything else works just like in the previous section:

Truncating Casts (Signed and Unsigned Downcasts)

Both signed and unsigned integers use the same instruction, trunc, to reduce the size of the number in question. This is because
LLVM IR assumes that all signed integer values are in two's complement format for which reason trunc is sufficient to handle both cases:

Floating-Point Extending Casts (Float Upcasts)

Floating points numbers can be extended using the fpext instruction:

Becomes:

Floating-Point Truncating Casts (Float Downcasts)

Likewise, a floating point number can be truncated to a smaller size:

Pointer-to-Integer Casts

todo: Document pointer-to-integer casts.

Integer-to-Pointer Casts

todo: Document integer-to-pointer casts.

Address-Space Casts (Pointer Casts)

todo: Find a useful example of an address-space casts, using the addrspacecast instruction,
to be included here.

Incomplete Structure Types

Incomplete types are very useful for hiding the details of what fields a given structure has. A well-designed C interface can be made so that no details of the structure are revealed to the client, so that the client cannot inspect
or modify private members inside the structure:

Becomes:

Structures

LLVM IR already includes the concept of structures so there isn't much to do:

It is only a matter of discarding the actual field names and then index with numerals starting from zero:

Nested Structures

Nested structures are straightforward:

Unions

Unions are getting more and more rare as the years have shown that they are quite dangerous to use; especially the C variant that does not have a selector field to indicate which of the union's variants are valid. Some may still have
a legacy reason to use unions. In fact, LLVM does not support unions at all:

Becomes this when run through Clang++:

What happened here? Where did the other union members go? The answer is that in LLVM there are no unions; there are only structs that can be cast into whichever type the front-end want to cast the struct into. So to access the above
union from LLVM IR, you'd use the bitcast instruction to cast a pointer to the "union" into whatever pointer you'd want it to be:

This may seem strange, but the truth is that a union is nothing more than a piece of memory that is being accessed using different implicit pointer casts.

If you want to support unions in your front-end language, you should simply allocate the total size of the union (i.e. the size of the largest member) and then generate code to reinterpret the allocated memory as needed.

The cleanest approach might be to simply allocate a range of bytes (i8), possibly with alignment padding at the end, and then cast whenever you
access the structure. That way you'd be sure you did everything properly all the time.

Structure Expressions

As already told, structure members are referenced by index rather than by name in LLVM IR. And at no point do you need to, or should you, compute the offset of a given structure member yourself. The getelementptr instruction
is available to compute a pointer to any structure member with no overhead (the getelementptr instruction is typically coascaled into the actual load orstore instruction).

Getting a Pointer to a Structure Member

The C++ code below illustrates various things you might want to do:

Becomes:

todo: Document the extractvalue and insertvalue instructions.

Mapping Control Structures to LLVM IR

todo: Add common control structures such as if, for, switch,
and while.

todo: Explain the purpose of the phi instruction;
show how it becomes obvious that you need it as soon as you encounter multiple blocks that contribute a value through different temporaries. In a way, phi ought
to have been called "join" as it sort of joins up subexpressions from different basic blocks.

Mapping Advanced Constructs to LLVM IR

In this chapter, we'll look at various non-OOP constructs that are highly useful and are becoming more and more widespread in use.

Lambda Functions

A lambda function is an anonymous function with the added spice that it may freely refer to the local variables (including argument variables) in the containing function. Lambdas are implemented just like Pascal's nested functions,
except the compiler is responsible for generating an internal name for the lambda function. There are a few different ways of implementing lambda functions (see `Wikipedia on nested functions Wikipedia
on Nested Functions for more information).

Here the "problem" is that the lambda function references a local variable of the caller, namely a, even though the lambda function
is a function of its own. This can be solved easily by passing the local variable in as an implicit argument to the lambda function:

Alternatively, if the lambda function uses more than a few variables, you can wrap them up in a structure which you pass in a pointer to the lambda function:

Becomes:

Obviously there are some possible variations over this theme:

1. You could pass all implicit as explicit arguments as arguments.
2. You could pass all implicit as explicit arguments in the structure.
3. You could pass in a pointer to the frame of the caller and let the lambda function extract the arguments and locals from the input frame.

Closures

todo: Describe closures.

Generators

A generator is a function that repeatedly yields a value in such a way that the function's state is preserved across the repeated calls of the function; this includes the function's local offset at the point it yielded a value.

The most straigthforward way to implement a generator is by wrapping all of its state variables (arguments, local variables, and return values) up into an ad-hoc structure and then pass the address of that structure to the generator.

Somehow, you need to keep track of which block of the generator you are doing on each call. This can be done in various ways; the way we show here is by using LLVM's blockaddress instruction
to save the address of the next local block of code that should be executed. Other implementations use a simple state variable and then do a switch-like
dispatch according to the value of the state variable. In both cases, the end result is the same: A different block of code is executed for each local block in the generator.

The important thing is to think of iterators as a sort of micro-thread that is resumed whenever the iterator is called again. In other words, we need to save the address of how far the iterator got on each pass through so that it can
resume as if a microscopic thread switch had occured. So we save the address of the instruction after the return instruction so that we can resume running as if we never had returned in the first place.

I resort to pseudo-C++ because C++ does not directly support generators. First we look at a very simple case then we advance on to a slightly more complex case:

And now for a slightly more complex example that involves local variables:

This becomes something like this:

Another possible way of doing the above would be to generate an LLVM IR function for each state and then store a function pointer in the context structure, which is updated whenever a new state/function needs to be invoked.

Mapping Exception Handling to LLVM IR

Exceptions can be implemented in one of three ways:

1. The simple way, by using a propagated return value.
2. The bulky way, by using setjmp and longjmp.
3. The efficient way, by using a zero-cost exception ABI.

Please notice that many compiler developers with respect for themselves won't accept the first method as a proper way of handling exceptions. However, it is unbeatable in terms of simplicity and can likely help people to understand
that implementing exceptions does not need to be very difficult.

The second method is used by some production compilers, but it has large overhead both in terms of code bloat and the cost of a try-catch statement
(because all CPU registers are saved using setjmp whenever a try statement
is encountered).

The third method is very advanced but in return does not add any cost to execution paths where no exceptions are being thrown. This method is the de-facto "right" way of implementing exceptions, whether you like it or not. LLVM directly
supports this kind of exception handling.

In the three sections below, we'll be using this sample and transform it:

Exception Handling by Propagated Return Value

This method is a compiler-generated way of implicitly checking each function's return value. Its main advantage is that it is simple - at the cost of many mostly unproductive checks of return values. The great thing about this method
is that it readily interfaces with a host of languages and environments - it is all a matter of returning a pointer to an exception.

The C++ sample above maps to the following code:

Setjmp/Longjmp Exception Handling

The basic idea behind the setjmp and longjmp exception
handling scheme is that you save the CPU state whenever you encounter a try keyword and then do a longjmp whenever
you throw an exception. If there are few try blocks in the program, as is typically the case, the cost of this method is not as high as it might
seem. However, often there are implicit exception handlers due to the need to release local resources such as class instances allocated on the stack and then the cost can become quite high.

Setjmp/longjmp exception handling is often
abbreviated SjLj for SetJmp/LongJmp.

The sample translates into something like this:

Zero Cost Exception Handling

todo: Explain how to implement exception handling using zero cost exception handling.

Resources

1. Compiler
   Internals - Exception Handling.
2. Exception Handling in C without C++.
3. How a C++
   Compiler Implements Exception Handling.
4. DWARF standard - Exception Handling.
5. Itanium C++ ABI.

Mapping Object-Oriented Constructs to LLVM IR

In this chapter we'll look at various object-oriented constructs and see how they can be mapped to LLVM IR.

Classes

A class is nothing more than a structure with an associated set of functions that take an implicit first parameter, namely a pointer to the structure. Therefore, is is very trivial to map a class to LLVM IR:

We first transform this code into two separate pieces:

1. . The structure definition.
2. . The list of methods, including the constructor.

Then we make sure that the constructor (``Foo_Create_Default``) is invoked whenever an instance of the structure is created:

Virtual Methods

A virtual method is no more than a compiler-controlled function pointer. Each virtual method is recorded in the vtable, which is
a structure of all the function pointers needed by a given class:

This becomes:

Please notice that some C++ compilers store _vtable at a negative offset into the structure so that things like memcpy(this,
0, sizeof(*this)) work, even though such commands should always be avoided in an OOP context.

Single Inheritance

Single inheritance is very straightforward: Each "structure" (class) is laid out in memory after one another in declaration order.

Here, a and b will
be laid out to follow one another in memory so that inheriting from a class is simply a matter of declaring a the base class as a first member in the inheriting class:

So the base class simply becomes plain members of the type declaration for the derived class.

And then the compiler must insert appropriate type casts whenever the derived class is being referenced as its base class as shown above with the bitcast operator.

Multiple Inheritance

Multiple inheritance is not that difficult, either, it is merely a question of laying out the multiply inherited "structures" in order inside each derived class.

This is equivalent to the following LLVM IR:

And the compiler then supplies the needed type casts and pointer arithmentic whenever baseB is being referenced as an
instance of BaseB. Please notice that all it takes is a bitcast from
one class to another as well as an adjustment of the last argument togetelementptr.

Virtual Inheritance

Virtual inheritance is actually quite simple as it dictates that identical base classes are to be merged into a single occurence. For instance, given this:

Derived will only contain a single instance of BaseA even
if its inheritance graph dictates that it should have two instances. The result looks something like this:

So the second instance of a is silently ignored because it would cause multiple instances of BaseA to
exist in Derived, which clearly would cause lots of confusion and ambiguities.

Interfaces

An interface is nothing more than a base class with no data members, where all the methods are pure virtual (i.e. has no body).

As such, we've already described how to convert an interface to LLVM IR - it is done precisely the same way that you convert a virtual member function to LLVM IR.

Boxing and Unboxing

Boxing is the process of converting a non-object primitive value into an object. It is as easy as it sounds. You create a wrapper class which you instantiate and initialize with the non-object value:

Unboxing is the reverse of boxing: You downgrade a full object to a mere scalar value by retrieving the boxed value from the box object.

It is important to notice that changes to the boxed value does not affect the original value and vice verse. The code below illustrates both steps:

Class Equivalence Test

There are two ways of doing this:

1. If you can guarantee that each class a unique vtable, you can simply compare the pointers to the vtable.
2. If you cannot guarantee that each class has a unique vtable (because different vtables may have been merged by the linker), you need to add a unique field to the vtable so that you can compare that instead.

The first variant goes roughly as follows (assuming identical strings aren't merged by the compiler, something that they are most of the time):

todo: Finish up class equivalence test sample.

As far as I know, RTTI is simply done by adding two fields to the _vtable structure: parent and signature.
The former is a pointer to the vtable of the parent class and the latter is the mangled (encoded) name of the class. To see if a given class is another class, you simply compare the signature fields.
To see if a given class is a derived class of some other class, you simply walk the chain of parent fields, while checking if you have found
a matching signature.

Class Inheritance Test

A class inheritance test is a question of the form:

Is class X identical to or derived from class Y?

To answer that question, we can use one of two methods:

1. The naive implementation where we search upwards in the chain of parents.
2. The faster implementation where we search a preallocated list of parents.

The naive implementation is documented in the first two exception handling examples as the Object_IsA function.

todo: Document the faster class inheritance test implementation.

The New Operator

The new operator is generally nothing more than a type-safe version of the C malloc function
- in some implementations of C++, they may even be called interchangeably without causing unseen or unwanted side-effects.

The Instance New Operator

All calls of the form new X are mapped into:

Calls of the form new X(Y, Z) are the same, except Y and Z are
passed into the constructor as arguments.

The Array New Operator

New operations involving arrays are equally simple. The code new X[100] is mapped into a loop that initializes each
array element in turn:

Interoperating with a Runtime Library

It is common to provide a set of run-time support functions that are written in another language than LLVM IR and it is trivially easy to interface to such a run-time library. The use of malloc and free in
the examples in this document are examples of such use of externally defined run-time functions.

The advantages of a custom, non-IR run-time library function is that it can be optimized by hand to provide the best possible performance under certain criteria. Also a custom non-IR run-time library function can make explicit use of
native instructions that are foreign to the LLVM infrastructure.

The advantages of IR run-time library functions is that they can be run through the optimizer and thereby also be inlined automatically.

Interfacing to the Operating System

I'll divide this chapter into two sections:

1. How to Interface to POSIX Operating Systems.
2. How to Interface to the Windows Operating System.

How to Interface to POSIX Operating Systems

On POSIX, the presence of the C run-time library is an unavoidable fact for which reason it makes a lot of sense to directly call such C run-time functions.

Sample POSIX "Hello World" Application

On POSIX, it is really very easy to create the Hello world program:

How to Interface to the Windows Operating System

On Windows, the C run-time library is mostly considered of relevance to the C and C++ languages only, so you have a plethora (thousands) of standard system interfaces that any client application may use.

Sample Windows "Hello World" Application

Hello world on Windows is nowhere as straightforward as on POSIX:

Resources

This chapter lists some resources that may be of interest to the reader:

1. Modern Compiler Implementation in Java, 2nd Edition.
2. Alex Darby's series of articles on low-level stuff.

Epilogue

If you discover any errors in this document or you need more information than given here, please write to the author at Mikael
Lyngvig.

Please also remember that you can learn a lot by using the -emit-llvm option to the clang++ compiler.
This gives you a chance to see a live production compiler in action and precisely how it does things.

Appendix A: How to Implement a String Type in LLVM

There are two ways to implement a string type in LLVM:

1. To write the implementation in LLVM IR.
2. To write the implementation in a higher-level language that generates IR.

I'd personally much prefer to use the second method, but for the sake of the example, I'll go ahead and illustrate a simple but useful string type in LLVM IR. It assumes a 32-bit architecture, so please replace all occurences of i32 with i64 if
you are targetting a 64-bit architecture.

We'll be making a dynamic, mutable string type that can be appended to and could also be inserted into, converted to lower case, and so on, depending on which support functions are defined to operate on the string type.

It all boils down to making a suitable type definition for the class and then define a rich set of functions to operate on the type definition:

Appendix B: Task List

This chapter serves as an informal task list and is to be updated as new to-do items are completed:

1. How to enable debug information? (Line and Function, Variable)
2. How to interface with a garbage collector? (link to existing docs)
3. How to express a custom calling convention? (link to existing docs)
4. Representing constructors, destructors, finalization
5. How to examine the stack at runtime? How to modify it? (i.e. reflection, interjection)
6. Representing subtyping checks (with full alias info), TBAA, struct-path TBAA.
7. How to exploit inlining (external, vs within LLVM)?
8. How to express array bounds checks for best optimization?
9. How to express null pointer checks?
10. How to express domain specific optimizations? (i.e. lock elision, or matrix math simplification) (link to existing docs)
11. How to optimize call dispatch or field access in dynamic languages? (ref new patchpoint intrinsics for inline call caching and field access caching)

todo: Ask various front-end implementors (Rust, Haskell (GHC), Rubinius, and more) to review and/or contribute
so as to make the document great.