What is LLVM? I Tell Huiqi About It. Part 2

This is part 2 of 2 of a conversation I had with Huiqi Zhou where I tell her about LLVM and just can't stop talking. In this episode I show some LLVM IR code examples and explain SSA - Static Single Assignment. LLVM is an open source compiler infrastructure / framework. It contains a state of the art C compiler called clang, and if you want to make your own compiler, it can provide you with building blocks that can make your work easier.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : I'll write a hello world in C you have
00:02 : to include the standard i/o library and
00:06 : the entry point of every C program is a
00:09 : main function normally the way you
00:15 : compile this is GCC hello dot C and you
00:21 : tell it what's the name of the
00:23 : executable file you want to generate and
00:25 : I'll call it hello dot Ben that's the
00:27 : binary file it's the ones and zeros and
00:30 : then with the ones and zeros file you
00:33 : can just call that file directly and
00:36 : your computer will run that program for
00:38 : you so if you want to see the
00:40 : intermediate steps well I have this
00:42 : script called C to L so you takes your C
00:46 : and converts it into LL and we're gonna
00:49 : use the clang compiler to do that the
00:52 : clang compiler coming from the LLVM
00:54 : project so it's gonna tell it to emit
00:56 : the code in LLVM code there's actually a
01:00 : binary version of the LLVM code and then
01:03 : just yet another intermediate layer and
01:06 : then we're gonna disassemble it and
01:08 : print out the human readable version of
01:11 : the LLVM code i'm just gonna call this
01:13 : file on my holo dot C program so it's
01:17 : gonna convert this C file into a hello
01:20 : dot ll file and this is what the LLVM
01:24 : code looks like there's a lot of really
01:27 : busy looking stuff I'm gonna say this
01:29 : stuff don't matter that much and this
01:35 : and then here this one is basically the
01:40 : printf function call okay the string
01:43 : literal was defined up here I know it
01:46 : looks super busy
01:50 : if we take this ll file and convert it
01:54 : into assembly language looks like this
01:57 : and then finally it's gonna take this
01:59 : file and turn it into the dot been the
02:01 : ones and zeros right so that's the
02:05 : pipeline I will show you a little bit of
02:08 : what the LLVM ir language
02:12 : like the smallest possible LLVM program
02:16 : you can write is this you have to define
02:20 : a main function oh you have to specify
02:21 : the type that the main function returns
02:25 : wasn't I
02:28 : 32 means a 32-bit integer okay i stands
02:33 : for integer and 32 stands for 32-bit and
02:37 : normally in c and c++ if you define a
02:41 : variable to be an int it's assumed that
02:44 : is 32 bits long
02:45 : oh and so saying yeah there's a main
02:49 : function and by convention the main
02:51 : function is always the entry point of
02:53 : the program just like C so they kind of
02:55 : took that convention from C and then you
02:58 : need to return a value at the end of the
03:01 : main function and you use this writ
03:03 : statement it's language very very
03:06 : strictly typed so it's very tedious to
03:07 : write code by hand is meant to be a
03:10 : generated code right every single
03:13 : instruction you write you have to
03:15 : specify the type of the arguments and
03:18 : type of the outputs so here is a I'm
03:20 : returning a thing of type I 32 again
03:24 : because now that matches the output type
03:27 : of the function so that makes sense
03:29 : it checks out and I'm just gonna return
03:31 : a 0 so compile it I have a program
03:33 : called ll tube in
03:35 : so compile this ll code to binary so
03:39 : compile it and now I have a plate I've
03:41 : been I can execute it there's nothing
03:47 : let's make it do a little bit of
03:49 : something there's a function that's
03:51 : provided by the standard c library it's
03:55 : called put char in order to use it i
03:57 : have to declare it the fact that it will
04:00 : link it correctly that's another thing I
04:03 : don't totally understand how it works
04:04 : but I just knew that in order to use
04:07 : this put char function which takes a
04:09 : character and print it out into the
04:11 : terminal I have to declare it like that
04:14 : correctly and it takes a integer in 32
04:17 : bits and it'll print it out
04:19 : it returns another integer but you don't
04:22 : really care about what that is in most
04:24 : kids so I'm just gonna say
04:26 : yeah if you want to call a function you
04:28 : say car and then you have to tell LLVM
04:32 : what's the return type of the function
04:34 : even though even though you can kind of
04:37 : figure it out like but you still have to
04:39 : tell it the return type why can't you
04:42 : just look over at the definition and
04:44 : figure it out right no you have to tell
04:46 : me so you have to you have to tell it
04:48 : the type of the input type and then you
04:50 : put in the value that you want to print
04:52 : and the value you're gonna put in is the
04:54 : ASCII code of the character you on the
04:57 : print okay oh let's print a that's 65 so
05:02 : you put in 65 so if you run this is
05:06 : gonna print out friends update and if
05:12 : you want say I want a new line after
05:14 : that well a new line is ASCII code 10 so
05:23 : that's why my hollow world looks like
05:26 : this this is my hollow world program it
05:31 : just prints out every character body its
05:33 : ASCII code a loop looks like this you
05:35 : have to use labels and use VR which
05:39 : stands for branch branch statement to
05:42 : jump from this place to that label again
05:45 : which in assembly language you do it in
05:47 : the exact same way so this is just a
05:50 : construct from assembly language that it
05:52 : carried over here I've made this program
05:55 : with a nested loop there's an outer loop
05:59 : and an inner loop and then I have to
06:02 : have a block called an inner loop so
06:04 : when it's done with the inner loop I
06:06 : have to do this comparison this icon
06:09 : stands for integer comparison so I'm
06:12 : comparing the value of the loop variable
06:15 : to ten if it goes up to ten then I'm
06:19 : gonna branch to n either to the end of
06:22 : the inner loop or back to the top of the
06:24 : inner loop right and then the same thing
06:28 : with the outer loop I have the same
06:31 : structure with the outer loop so this is
06:33 : a nested loop if you run this program
06:37 : there it's a pointer
06:39 : then you just like find the block now
06:42 : you want to execute next yes yeah this
06:46 : is basically like the low-level view of
06:49 : what an if statement or wild actually
06:52 : looks like yeah if you make a
06:55 : programming language you need to make an
06:57 : if statement construct you you're gonna
07:00 : need to do something like this and have
07:02 : these labels you have to plan out your
07:04 : labels have this the end of this label
07:08 : go to that label and so forth
07:10 : if stamen is similar to a loop because
07:13 : again it's the linking together of the
07:15 : labels you do a comparison if it's true
07:18 : you jump to one block if it's false you
07:21 : jump to a different block and you have
07:23 : to plan out the blocks and put put the
07:26 : code the consequential code into the
07:28 : correct blocks and then when you reach
07:31 : the end of either the true block or the
07:33 : false block then you join back together
07:36 : into this exit block so you have to like
07:39 : have a return somewhere like and then
07:42 : you can't get out of here yeah this is a
07:46 : picture from the tutorial that I've been
07:48 : following basically it's like this graph
07:50 : right this is the entry point of
07:52 : statement and then it was the branch to
07:55 : one of these two notes at the end of
07:57 : stamen the two notes have to draw him
08:00 : back to a common note at the end it's
08:02 : the control flow graph this is an add
08:04 : instruction this is a subtract
08:06 : instruction and you can assign variables
08:10 : like sort of similar to what you would
08:13 : expect but all variables in LLVM are
08:19 : immutable it turns out there's this
08:23 : concept called SSA which stands for
08:27 : static single assignment form which the
08:31 : LLVM language adheres to so basically in
08:35 : static assignment form every single
08:38 : variable can only be assigned to once
08:40 : which which is nice for functional
08:43 : programming languages and immutable
08:45 : languages but what do you do if you have
08:48 : a code that doesn't do that well you
08:51 : have to rewrite the code
08:53 : SSA form and and the way you do that is
08:56 : by each time you assign a value to the
08:59 : same variable you actually have to make
09:02 : that variable a differently named
09:05 : variable so like you have to change the
09:08 : first one to y1 and the second one - why
09:11 : - there are actually two different
09:13 : variables so so so visiting you rewrite
09:19 : this program that doesn't satisfy SSA -
09:22 : this in order to satisfy SSA a white
09:25 : powder with SSA why is this important
09:28 : well LLVM uses SSA if you're generating
09:33 : code in LLVM ir it has to be in SSA
09:37 : already why does it want that because if
09:41 : the code is in SSA it allows for a
09:44 : variety of compiler optimizations like
09:49 : there's a whole family of sort of well
09:52 : researched compiler optimization
09:55 : there's compiler experts that know how
09:58 : to do these optimizations a lot of them
10:02 : are either enhanced or made possible by
10:06 : SSA so so by putting this code in SSA it
10:12 : enables LLVM to implement all these
10:16 : different algorithms that can include
10:19 : faster yeah which is basically why LLVM
10:24 : mandates the code be in this form in the
10:27 : first place so when you so if you have
10:31 : y1 and y2 do they take a different like
10:34 : memory slot yes yes like whoa that's
10:39 : kind of weird like what if you actually
10:41 : wanted to mutate variables you actually
10:46 : have to explicitly allocate memory it's
10:49 : what you would do in that case
10:51 : you say hey locate memory for this
10:54 : variable and then you store a value into
10:57 : that memory location and load a value
11:00 : out of the location explicitly in your
11:03 : in your olv Mir code
11:06 : this adds a complication though like
11:09 : it's actually not straightforward
11:12 : to convert any arbitrary program to SSA
11:15 : form because as you can imagine in this
11:19 : example if you have an if statement like
11:22 : stuff gets weird so basically if we have
11:26 : to code looking like this we have first
11:29 : we assign 5 to X and now we assign X
11:32 : minus 3 to X so that's clearly not SSA
11:36 : form we just assign twice to X that's
11:39 : not allowed
11:41 : and then also we have two separate
11:44 : assignments to Y that's also not allowed
11:47 : in SSA form right so so if we convert
11:49 : this to SSA form what would that look
11:52 : like well it would look like this right
11:54 : the first X is X 1 the second X is X 2
11:58 : now when we're comparing X 2 3 we want
12:01 : to use X 2 because there was the last
12:04 : version of X that this program used and
12:07 : then here we have an assignment to Y
12:11 : we're going to assign to Y 2
12:13 : but the next assignment to why we're
12:15 : assigning it to Y by 2
12:16 : oh the first one y one the second one Y
12:18 : 2 and then here's the first assignment
12:22 : to W we're going to assign it to W 1 but
12:26 : then later on we assigned to W again so
12:29 : that's assigning to the what is this
12:33 : symbol ok that's not meant to be there
12:36 : yet so let me remove it the problem with
12:38 : encounter is here we have this statement
12:41 : that references why well we don't know
12:44 : whether wide needs to come from Y 1 or Y
12:47 : 2 exactly like it depends on which
12:51 : branch it took yeah so it's like I don't
12:56 : know I can't figure out which branch you
12:58 : took during compile time so Y is a
13:02 : question mark I know it's either y 1 or
13:05 : Y 2 that need to be referenced in here
13:08 : and in here but that's a question mark
13:10 : and that's why we need the Phi function
13:14 : this is how they solve the problem
13:16 : these compiler experts that came up with
13:19 : this concept
13:20 : they solved it with this Phi function
13:23 : that says oh okay Phi is this chooser
13:27 : that will choose either y1 or y2
13:31 : correctly and it'll choose it based on
13:34 : whether you came from this branch or
13:36 : this branch if you came from this branch
13:38 : I'm using y1 if you came from this
13:40 : branch I'm using y2 and I would choose
13:43 : one of those value and call that y3 and
13:45 : then the next step of the program can
13:49 : use y3 after that and essentially it's a
13:52 : merge right it's like we had to branch
13:55 : off and in who have to merge but we have
13:58 : to unify for this variable that kind of
14:01 : diverged in how it received a value wow
14:06 : that's really strange
14:07 : it's really strange that they had to
14:09 : come up with this thing basically LLVM
14:12 : is saying like I want you to give me
14:15 : code like this I want you to give me
14:17 : this code that has this Phi in it and
14:19 : then I will compile this to machine code
14:21 : for something to compile your code to
14:27 : this code yes yes yes I have to generate
14:31 : code in SSA form which is actually a
14:34 : non-trivial thing to do and they say
14:37 : that in the tutorial is there like yeah
14:40 : it's actually really hard to generate
14:42 : code in SSA form so actually you won't
14:45 : have to do that fortunately but in some
14:48 : cases where it's easy to do this then
14:51 : this is what you should do for pure
14:54 : functions it's actually easy to do this
14:56 : because if you look at the if statements
14:59 : for purely functional program languages
15:02 : like Haskell or Elm the if statement is
15:05 : like if you know some conditional then
15:09 : some value else some other value if
15:14 : Damon always have to have a den part
15:16 : plus an else part you cannot skip the
15:19 : else part and also your if statement
15:22 : always returns you a value yeah which
15:27 : means you can always assign it to
15:29 : something else no matter what the the if
15:33 : statement is an
15:34 : pression that gives you a value so
15:36 : basically you you evaluate that
15:39 : expression to figure out what was that
15:41 : value and you varied that expression to
15:44 : figure out what was that value and
15:45 : that's the output value of the
15:47 : expression so it's easy to generate a
15:50 : final for that because you know there's
15:52 : only one variable that came out of this
15:56 : block and there's only one variable that
15:58 : came out of that block and those are the
16:01 : two values that the five function is
16:03 : gonna take in well as long as your
16:06 : functionality to really but if you have
16:11 : your language has mutation that's a
16:13 : different story and that's where do you
16:15 : have to allocate memory and work with
16:17 : the memory explicitly pretty good amount
16:22 : of time if you have other questions I
16:24 : can try to answer otherwise LLVM
16:31 : currently used in the like say
16:33 : javascript compilers or other like
16:35 : popular c like programming languages
16:39 : compiler okay I don't think it's being
16:42 : used in the JavaScript compilers
16:45 : languages with compilers that use LLVM
16:48 : include ActionScript that's actually
16:52 : something I've used before the
16:55 : ActionScript is associated with flash
16:57 : which as you know died when Steve Jobs
17:00 : said we're not supporting flash on the
17:03 : iPad we have common lisp which used to
17:06 : be the most popular version of lisp
17:08 : haskell yeah Haskell has that
17:11 : objective-c well clang already supports
17:13 : Objective C really I did not know Ruby
17:18 : used LLVM but Russ yeah Russ is one that
17:22 : I heard was like they they use LLVM
17:25 : initially Lua Lua also uses it I didn't
17:29 : talk about
17:30 : but JIT is like just-in-time compilation
17:33 : which means instead of running running
17:37 : the compiler on the command line and
17:39 : then sort of spitting out machine code
17:42 : you don't do that ahead of time you you
17:45 : spit out the machine code while the
17:47 : program is
17:47 : running on demand and JavaScript v8 kind
17:51 : of works like that you just run the
17:53 : JavaScript and it'll read in the
17:55 : JavaScript code and parse it and so
17:57 : forth and then when it needs to execute
17:59 : it it'll generate the machine code right
18:02 : away like in the browser well because
18:04 : the browser is a program that's running
18:06 : everything so the browser is like okay
18:08 : compare that to machine code just in
18:10 : time and then stick the machine code
18:12 : into this piece of memory and then I'll
18:14 : put my program counter on that piece of
18:16 : memory and execute that code line by
18:18 : line and I imagine the dynamic
18:21 : programming languages like Ruby and
18:23 : JavaScript are doing that kind of thing
18:26 : so that that's the kind of thing I've
18:28 : been digging into so furthering my
18:31 : learning of of compilers like which
18:40 : thanks very much for joining me
18:42 : cool yeah thanks for sharing