Hi, and welcome to the first session of the "Building Programming Language with LLVM"!
My name is Dmitry Soshnikov and I'll be teaching this class and just to set
the agenda this is very practical class. Right, the same as in other classes in the
"building from scratch" series here most of the videos will be actual practical exercise.
And the first thing we need to say this class has set of prerequisites.
First of all we'll need basic C++ experience but at the same time this is not a class about C++
so instead of very specific C++ constructs we'll be using very basic constructs like for example
simple loops instead of algorithm functions the same goes to the very specific LLVM wrappers for
example analyzing LLVM code you will see a lot of StringRef, ArrayRef wrappers - will be emitting
those for brevity but this is something you can use for better performance again our goal is to
show very concise and to the point implementation right I mentioned very specific details now we
will not be using any build system as well like CMake or Make we'll be using plain header files
with a single cpp file again this is not class about C++ so feel free to set up enable system
unit I will be just using the single Command right using clang++ utility to compile and this is how
we're able to execute our programs passing either the expression or the file but of course we will
need certain LLVM core libraries so we'll be using that llvm-config tool which will allow
us including headers from LLVM now in addition to the C++ basic knowledge it is highly recommended
to take two courses "Essentials of Interpretation" known as "Building an Interpreter from scratch"
and also "Building a Virtual Machine" now unless you're familiar with how to build a programming
language at the high level that is at the AST level unless you know concept of environment,
scope chain resolution, how eval works, etc it is highly recommended to take this course
also LLVM is about a lower level implementation of programmer languages so it's also recommended
to take Building a Virtual Machine where we built a lower level VM with a custom bytecode
also we need to say that this specific class on LLVM in contrast for example with other
classes has very basic evergreen concepts and also rapidly dynamically changing for example
if we take a class on the garbage collectors most of the concepts were invented in 1950s
right and still the same like Mark-Sweep garbage collector you can reuse today
not the case with LLVM the implementation for this infrastructure is rapidly changing and
for example until version 14 we had so-called raw pointers right you have specific type and
you have to explicitly cast one pointer type to other pointer type since version 15 LLVM switch
to so-called opaque pointers you can just use ptr instruction and you can also omit explicit casting
so the main takeaway it's literally impossible to design a sustainable knowledge class if we
focus only on dynamically changing details such as different apis format of the IR
etc and this is not the goal of this class instead we'll focus on the very
generic evergreen concepts which will stay the same regardless of the LLVM version such
as generic concept of compilation design patterns of virtual machines and the core ecosystem of LLVM
so in this specific class we use llvm version 14 but again it's not the point for the rapidly
changing parts you have to track and migrate if you would like to newer format but the main
concept will stay the same and we will be focusing exactly on those and despite having VM in its name
LLVM is actually not a virtual machine but rather they compiler infrastructure let's see what it is
so in previous classes we say that we distinguish languages on interpreted and compiled and in fact
it's rather not the languages but implementations right you might have interpreted version of
the same language and compiled version of the same language and LLVM infrastructure supports
actually all of them it has inline interpreter it has ahead of time compiler and JIT compiler
and in this class we will focus on ahead of time (AOT) compiler and we'll slightly talk about how
we can use JIT as well so let's recall the generic ahead of time compiler alright so here's again our
simple program print hello and the first module which meets our program is the tokenizer which
groups individual characters into recognizable stream of tokens which is then is passed to the
next module which is called parser right which ensures that those tokens go in specific order
and as a result of the parser we get so-called AST that is abstract syntax tree that is the
first intermediate representation which we can pass either to interpreter or compiler
in the classic compiler we pass the AST to a module which is called code generator
right which can produce multiple intermediate representations that is IRs which are eventually
translated to the native code right for specific target architecture which is then passed to CPU
and we get the result at runtime again so this is the ahead of time compilation that is we
translate the full source code to the target code before execution and that exactly what
we'll be focusing in this class in terms of LLVM now in compiler design we also have frontend and
backend and LLVM is exactly the infrastructure which allows us reusing existing and well-tested
backend which is capable of generating multiple target architectures so let's see what it is
now here's the same we pass the AST to the module which is called LLVM IR generator
which produces the intermediate representation known as LLVM IR right notes arbitrary bytecode
or bitcode but a specified bitcode which is further passed to the black box called LLVM
right which is the back end and which is capable to produce multiple architectures which again we
passed down to the CPU and get the result so this is the high level picture of this course
now in terms of backend and front-end llvm considers code generation from AST down to
IR is also a front end and this is exactly our Focus right we'll get the AST and produce the IR
we'll be skipping the parsing stage altogether right using just S-expression format as in other
classes however if you're interested how to translate source code down to AST you
might also take parser classes one of them is called "Building a Parser from scratch" right
very practical and manual parser recursive descent or you may even take the "Essentials
of Parsing" where we build automated parser and talk about parsing algorithms such as LL, LR, etc
so with this being said please meet Eva or meet again for those who have taken previous classes
as we said we'll be using S-expression format that is the parenthesized expression where is
the first element that is the type tag defines the expression type in this case we see the addition
expression type tag is plus so the result here is 15. we see the assignment expression type tag set
and also we see complex expressions for example if expression has three nested sub-expressions
here's another example function declaration as you can see we use the def keyword from the Python
and we also need to say that LLVM is actually typed language right this is how the type version
of the parameters and return value looks like we have the pair parameter name and its type and also
may specify the return type and here we use types not for a specific type check and semantics but
rather to understand which operation to apply write for example integer versus float and also
to understand how much memory to allocate however if you are interested in the type
checking semantics you may take the class which is called "Building a Typechecker from scratch"
and where we talk about type theory, type semantics and build a static type checker
we will start talking about LLVM specific constructs such as module context in the next
lectures and already today let's start jumping into the actual practice to the implementation
okay so I'm creating the directory for our project eva-llvm today we'll just slightly touch the
concept of LLVM IR not go into compilation yet which will start in the next lecture again in
this course we use llvm14 again we don't focus on the rapidly changing and specific constructs
rather on generic concepts of compilation right and using LLVM infrastructure ecosystem
so the clang is built on top of the LLVM itself as you can see I have the version 14 for Apple
to install LLVM I use the port Mac ports in the LLVM 14 module name
and then I can use the select command to set the list of installation and to
set the active installation and again we use the set command and it successfully activated
now once installed we'll have a lot of LLVM tools main of which is called llc that is LLVM compiler
which is also as we can see version 14 and it supports multiple targets the one we're interested
in is the x86/x64 but for example it supports also WebAssembly so it's possible to take this code and
compile it to be runnable on the web and before going to compilation let's actually start from the
very simple test file from C++ file which returned the simple number 42. now as the clang is built
on top of LLVM itself we can use the flag called -emit-llvm passing the -S option for the source
which produces the file called test.ll that is LLVM IR let's take a look and here exactly it is
so we can see our value 42 it returned from the main function but there's a lot of metadata here
the main thing is clang is able to take this .ll file and produce the binary code which we
can execute and get the result now in addition to llc which is the ahead of time compiler and the
clang there is also a tool called lli that is llvm interpreter and instead of generating the
native code we can just use interpreter passing the test a little directly and get the same result
so let's take a look at the structure of the LLVM IR as you can see at top we have different meta
information and one of which is called data-layout and this data layout string is the representation
of the memory layout so it describes alignment and the size of data structures as well as
endian little endian big endian the size of the pointer, etc and during this course I recommend
using the language reference located at this this address where you can read about specific data
layout string now this is not very essential for this class moreover all this information can be
automatically inferred as we'll see shortly we can just directly remove it and actually let's
start doing that let's clean up all the metadata for now we don't need those instructions allocate
and storage we'll get to them later just returning 42. okay clean up this one and clean up everything
else so this is the minimum LLVM IR program as you can see we have only the main function and we use
define keyword to define functions one thing to notice we use @ symbol to define global symbols
and all the functions in LLVM are actually global there's no concept of local functions but we will
see how we Implement closures etc and we just return the value 42 specifying the return type
okay we can pass this program down to lli and get correct result let's check it again
and it works so you can use this tool just to play with LLVM IR itself and understand the programs
let's show again we can use clang++ to compile the same file and we get some worrying since clang
uses specific checks so let's actually return the metadata for the target machine architecture
and again it just works in this case again we compile down to native code and then
executed the native file now in addition to that there is a tool which is called LLVM
Assembler in fact this LLVM IR is a readable representation of the bitcode which is used
by the LLVM virtual machine and the compiler so the assembler produces the .bc file which stands
for bitcode right in contrast with Java which make popular term bytecode here we use bitcode
and this bitcode is nothing but the binary representation of the same IR
and there's inverse tool called LLVM Disassembler let's pass the output file name as test2 and as
you can see it's exactly the same files just generated from different modules
again going back to the function the main function is required so this is the main entry point
again as you can see it has return type @ specifying that this is global symbol
and we have return statements with also specified type another point we can pass
this LLVM file down to clang specifying the -S option which will generate the native assembly
code native assembly right so this is test.s and here we also see the value 42. exactly
the same we pass down to clang generate binary code and execute okay so that's it for today
that's the introductory lecture and what will be building in the next lecture we'll start talking
about actual LLVM program structure right we'll talk about what is Module, Context, IR Builder,
and we'll start building the compiler that's it for today thanks and see you in the class