August 18, 2010 at 08:31LLVM from the inside: how it works
I welcome habrayuzer, in this article we will talk about the internal structure of the LLVM compiler. You can read about LLVM in general here or on llvm.org . As you know, LLVM (conditionally) consists of three parts - bytecode, compilation strategy and aka LLVM infrastructure environment. I will consider the latter.Content:
- LLVM assembly
- Snap to Eclipse
- Environment Architecture
- LLVM API
- Optimization Hello, World!
LLVM assembly
LLVM sources can be taken from the official project page , both in the archive and from the repository. Building LLVM is quite simple, but it has its own characteristics: first LLVM itself is assembled, then the front-end (in our case llvm-gcc), without which it will not be possible to compile C / C ++ programs. it is assumed that all the necessary libraries are present in the system, otherwise you will be abused anyway during configuration. So, we are at the root of the source tree, compile LLVM:
mkdir build && cd buildNow build llvm-gcc:
# Configuration
../configure --enable-jit --enable-optimized --enable-shared --prefix = / prefix --enable-targets = host-only
# --enable-shared allows you to build the kernel LLVM as one large shared library
# instead of / prefix, specify the desired installation path
# --enable-targets = host-only means support only for the host architecture
# for additional acceleration, you can add --disable-assertions, they are in the code at every step, in including in cycles
# Build
make -j2 CXXFLAGS = -O3
# -jN is very symbolic, most of the time it will still be collected in one thread,
# nothing can be done about it
# CXXFLAGS = -O3 gives additional GCC optimizations.
# You can also add -flto to enable link-time optimizations in case of GCC 4.5+
# Installation
make install
# We take theIf everything went well, then, for example, such a check will pass:
svn co code http://llvm.org/svn/llvm-project/llvm-gcc-4.2/trunk llvm-gcc
cd llvm-gcc && mkdir build && cd build
# Configuration
../configure --enable-llvm = / path / to / llvm / build --prefix = / prefix / of / llvm --program-prefix = llvm- --enable-languages = c, c ++
# / path / to / llvm / build means the path to the same the build folder created in the previous step
# / prefix / of / llvm - for convenience, the prefix matches the LLVM prefix
# --program-prefix = llvm- is needed to get common binary names like llvm-gcc or llvm-g ++
# Build
make - j2 CFLAGS = -O3
# Installation
make install
/ prefix / of / llvm / llvm-gcc -v
...
gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build)
Snap to Eclipse
For convenience, I’ll tell you how to compile and study the LLVM source code in Eclipse (of course, with C / C ++ support). Create a new project C ++ / File-New - C ++ Project / , set the name “llvm” / Project name / , uncheck the default location / Use default location / and set the path to the LLVM source tree, set the project type to Makefile / Project type: Makefile project - Empty Project / . Next, click "Finish" / Finish / . While Eclipse parses files and builds a navigation index, go to the project properties / Project - Properties / . In the builder settings / Builder Settings / uncheck the default build command / Use default build command /and type “make -j2 CXXFLAGS = -O3”. In the build directory / Build directory /, add "/ build", so that it turns out "$ {workspace_loc: / llvm} / build". Go to the behavior tab / Behavior / and to the right of the build target / Build (Incremental build) / we erase “all”. The latter is not necessary and is needed rather for the identity of manual assembly in the console. Done! You can safely jump through the classes, watch # define and click on the build button / Build / . To avoid possible problems (someone like that), you can delete tests from the tree.
Environment Architecture
LLVM consists of several executables using libLLVM2.x.so (kernel).
opt is a tool that operates with bytecode: it can roll up any available machine-independent optimizations in any order, perform various types of analysis and add profiling. There are optimization levels O0, O1, O2 and O3.
llc - code generator from bytecode to the assembler of the target machine. Performs machine dependent optimizations. There are also optimization levels O0, O1, O2 and O3.
llvm-ld - bytecode linker, i.e. The tool combines several bytecode files into one large BC file. At the same time, link-time optimizations are rolling, which the creators are so proud of.
lli is a bytecode interpreter with JIT compilation capability.
llvm-dis- bytecode converter (bc) to equivalent text representation (ll).
llvm-as is a text representation (ll) to bytecode (bc) converter.
llvm-ar - packer of several files into one. Some kind of bzip2 analogue.
llvmc is the LLVM driver, which calls the language parser (i.e. front-end: llvm-gcc or clang), opt, llc (specified back-end for the target machine), assembler and linker of the target machine. The general scheme is shown in the figure.
It is worth noting that all well-known architectures are supported as a back-end (including x86, x86-64, ARM), and even such exotics as the C language. The latter means that you can convert bytecode directly to the source in C ... but it is unlikely that you will like it without variable names (or rather, with other names assigned in the bytecode), with goto loops, a changed order of commands, and much more with something else. But how else, miracles do not happen. By the way, bytecode can potentially be turned into Java or .NET virtual machine code.
An interesting implementation of the "iron" back-end-s. At an early stage of LLVM build, a utility called tblgen appears. It also converts assembler descriptions in a specific descriptive language into C ++ code, which is subsequently #included into classes that implement code generation. Thus, it is very easy to change or add something to the command system, and support is unified. Unlike GCC, you don’t have to work hard on cross-compilation: when you call llc, just specify -march = armv7, where any supported architecture can stand in place of armv7. I cannot but mention here the fundamental difference between LLVM and, say, Java: LLVM bytecode generally depends on the platform on which it is received and the target machine for which it is compiled. The first is due to linking with OS-specific libraries, the second is due to assembler inserts and porting of code (conditional compilation) to various architectures.
Values of some folders with code:
- include - header files
- tools - implementation of the above tools
- runtime - profile collection implementation
- tools - implementation of LLVM utility utilities, incl. tblgen
- examples - LLVM examples
- lib - the main part
- lib / Analysis - passes that perform analysis (see below for passes)
- lib / CodeGen - implementation of code generation, machine-dependent passes
- lib / Transforms - passes performed on bytecode
LLVM API
The LLVM kernel is a very powerful system. All routine things are hidden from ordinary developers, giving you the opportunity to focus on improving the quality of the compiler. Detailed documentation, a lot of materials allow you to quickly get in the know. Names of classes, methods, inheritance scheme - everything is thought out to the smallest detail. I’ll talk a little about the optimization related API. In order not to be bored, it is advisable to know what such terms as basic block and control flow graph (aka CFG, Control Flow Graph) mean. Enough information from Wikipedia: base unit and control flow graph .
In general, it is customary to talk about passes, rather than optimizations. A pass is an implementation of a particular optimization or part of it. LLVM has a pass manager (PassManager), which works according to the FIFO principle. First, pass descriptions are added, and then the manager will execute them one by one. Moreover, if the passage needs data from some CFG analysis, then the manager will conduct this analysis first if its data is out of date. Passes work as part of a function (inherited from FunctionPass) or the base block (BasicBlockPass). In the first case, the function will be fed to the input of the algorithm, in the second - the base unit. The function can be iterated in the standard way on the base blocks, on the base block, respectively, according to the instructions. You can rearrange everything as you like, add new elements.
LLVM opt supports plugins - such as shared passes. During a call, the library is loaded and taken into account. Thanks to this, to expand the capabilities of the compiler, it is not necessary to make your own code branch and then edit it, the necessary header files are enough. As you know, in GCC this has appeared recently.
As they say, it is better to see once than hear a hundred times. Let's move on to practice.
Optimization Hello, World!
We apply the acquired knowledge to write our own very real machine-independent optimization. All she will do is collect statistics on the average number of instructions in the base unit, and in fact do nothing to optimize. Let's build it in the form of the opt plug-in, so as not to edit the LLVM code. Create the plugins folder in the root of the LLVM source tree, and in it the BasicBlockStats.cpp file with the following contents:
#define DEBUG_TYPE "basic-block-stats"I tried to provide the code with comments as much as possible to make it clear. Now assemble our plug-in:
#include "llvm / Pass.h"
#include "llvm / Function.h"
#include "llvm / Instructions.h"
#include "llvm / BasicBlock.h"
#include "llvm /ADT/Statistic.h "
#include" llvm / Transforms / Scalar.h "
#include" llvm / Support / CFG.h "
using namespace llvm;
// Announcement of collected statistics.
// Each of them can only be an unsigned integer.
// Total number of basic blocks
STATISTIC (NumberOfBasicBlocks, "Number of basic blocks in the module");
// Total number of instructions
STATISTIC (NumberOfInstructions, "Number of instructions in the module");
STATISTIC (AverageInstructionsInBasicBlock, "Average number of instructions in a basic block");
namespace
{
// Structure (class) of the pass (pass)
// In the generally accepted terminology, optimizations are called passes, because
// the action on the module is performed in one complete pass through its contents
struct BasicBlockStats: public FunctionPass
{
// Pass identification number
static char ID;
BasicBlockStats (): FunctionPass (ID) {}
// Overloading a method that tells the pass manager that it uses and changes the given pass
virtual void getAnalysisUsage (AnalysisUsage & AU) const
{
// Don't use anything, don't change anything
AU.setPreservesAll ();
}
// Overloading a method that carries the meaning of a pass - operations on a module function
virtual bool runOnFunction (Function & F);
~ BasicBlockStats ()
{
// When calling the destructor, consider the desired number
AverageInstructionsInBasicBlock = NumberOfInstructions / NumberOfBasicBlocks;
}
};
// We don’t need to identify ourselves
char BasicBlockStats :: ID = 0;
// Register the pass in the pass manager
RegisterPassX ("basic-block-stats", "Basic Block Statistics", true);
} // end of unnamed namespace
// Implementation of the main logic
bool BasicBlockStats :: runOnFunction (Function & F)
{
// We go through each basic block of the
for (Function :: iterator I = F.begin (), E = F.end ( ); I! = E; I ++)
{
NumberOfInstructions + = I-> size ();
}
// Add the number of base blocks
NumberOfBasicBlocks + = F.size ();
return false;
}
g ++ -c -fPIC BasicBlockStats.cpp -o BasicBlockStats.o -I ../include -I ../ build / include -D__STDC_LIMIT_MACROS -D__STDC_CONSTANT_MACROSIt is time to check if it works? I suggest conducting a combat test using SQLite code. Download sqlite-amalgamation-A_B_C_D.zip , unpack it somewhere. Further, I assume that the path to the installed LLVM and llvm-gcc executables, as well as to BasicBlockStats.so, is specified in $ PATH.
gcc -shared -s BasicBlockStats.o -o BasicBlockStats.so
#Collect the SQLite library in the bytecodeSo, the average value of instructions in the base unit in SQLite code is 8.
llvm-gcc -emit-llvm -c sqlite3.c -o sqlite3.bc
# Run our optimization
# -stats shows all statistics collected
opt sqlite3.bc -load BasicBlockStats.so -basic-block-stats - stats -o sqlite3.bc
=== ----------------------------------------------- -------------------------- ===
... Statistics Collected ...
=== ---------- -------------------------------------------------- ------------- ===
8 basic-block-stats - Average number of instructions in a basic block
18871 basic-block-stats - Number of basic blocks in the module
153836 basic-block- stats - Number of instructions in the module
Perhaps the simplicity of writing your own pass (pass) will inspire the reader to research in this area, and I will end here. I will be glad to answer your questions.