LLVM Tutorial #8: CodeGen

In this series I walkthrough the LLVM "Kaleidoscope" Tutorial, where you follow step by step to create your first programming language frontend using LLVM as the backend. Last time we talked briefly about SSA (Static Single Assignment Form). This time we actually write some code to generate LLVM IR.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : all right so now let's talk about I mean
00:06 : not not talked about but let's continue
00:08 : the tutorial and and try to implement
00:13 : some of this code so so we are having to
00:17 : implement this cogent function or method
00:23 : I should say for each of the a triptych
00:26 : ast class ast classes first we're gonna
00:32 : do it for the number expert ast class we
00:39 : still haven't figured out what value is
00:40 : and which header file it comes from we
00:43 : do have their code as a reference but
00:46 : I'm gonna try try not to look at their
00:50 : code actually try to figure it out based
00:53 : on the narrative of the tutorial if
00:56 : possible I kind of prefer that at some
01:00 : point we'll probably need to include a
01:02 : header file that has value in it okay so
01:08 : in C++ when you define of a method you
01:12 : can either define it within a class like
01:16 : that and then you write the content of
01:18 : the method or and this will be weird to
01:22 : people who are not used to C++ or you
01:26 : can define it the method of the class
01:28 : after the class has already been defined
01:31 : and that's how this tutorial proceeds
01:38 : okay so note that instead of adding
01:43 : virtual methods to the ast expert ast
01:47 : class hierarchy it also makes sense to
01:49 : use a visitor pattern or some other way
01:51 : to model this yes that's the way I would
01:54 : prefer to do it actually but I'm gonna
01:58 : follow along with this tutorial do it
02:00 : the way that it does set but I feel
02:03 : pretty confident about doing
02:04 : that way as well so Ted this tutorial
02:08 : won't dwell on good suffer engineering
02:10 : practices for our purposes
02:13 : adding a virtual method is simplest we
02:17 : want to log error method I kind of don't
02:24 : like this pattern that he uses I don't
02:26 : know why we need a log error method for
02:29 : each type of thing and it returns
02:32 : something but it returns a null pointer
02:34 : so I'm not actually gonna do this I'm
02:37 : just gonna called a generic log error
02:40 : function and then explicitly return a
02:42 : null pointer in the places where I want
02:45 : to do that there's a builder object is a
02:49 : helper builder that makes it easy to
02:51 : generate LLVM instructions instances of
02:55 : dir builder class template keep track of
02:57 : the current place to insert instructions
03:00 : and has methods to create new
03:01 : instructions so I'm gonna use be using
03:04 : this IRA builder a lot to create these
03:07 : the sort of operation or just just code
03:13 : elements in terms of LLVM ir and then
03:21 : the module so we're instructed to write
03:24 : this code though I'm gonna skip this log
03:27 : error but I'm gonna put this code here
03:30 : in I'll put it before the main function
03:36 : so we got the context we got the module
03:40 : all these things we are gonna need
03:43 : header files to do oh and for map I'm
03:46 : gonna need to include map
03:50 : for some reason this tutorial doesn't
03:53 : tell you what libraries you need to
03:54 : include it expects you to figure that
03:56 : out for yourself
03:58 : and it's lucky that I have had some
04:02 : experience with working with map and
04:04 : vector er so I already know where they
04:07 : come from but for the LLVM specific
04:10 : stuff I don't actually know where what
04:14 : includes I need and it doesn't tell you
04:16 : unless you reference their final working
04:20 : code I guess okay
04:23 : the module is a LLVM construct that
04:26 : contains functions and global variables
04:28 : I see in many ways it is the top-level
04:33 : structure that LLVM ir uses to contain
04:35 : code it owns the memory for all of the
04:38 : ir that we generate which is why the
04:40 : cogent method returns a raw value
04:44 : pointer rather than a unique pointer so
04:47 : it's saying the module has ownership of
04:50 : the of the various constructs that the
04:54 : ir builder is going to build so yeah we
04:58 : don't we're not going to own those
05:01 : things so we're not gonna be responsible
05:02 : for cleaning them up or freeing up their
05:06 : memory named values map is a map to keep
05:13 : track of defined identifiers what things
05:19 : are defined it'sit's our symbol table
05:22 : for the code yeah so currently we don't
05:27 : even have variables but we have
05:28 : functions so the symbol table will keep
05:31 : track of what functions are defined and
05:33 : what the functions actually are okay so
05:39 : now let's Express code generation so
05:43 : let's write this code I'm gonna define a
05:49 : I wanna this is gonna define a cogent
05:53 : method for the number expert ast class
05:57 : so I'm gonna do it right under this
06:00 : class and I mean copy this code
06:21 : okay so that's the code it it it's
06:26 : actually bothered bothering me that I
06:29 : don't have to write include files so
06:31 : that these are have red squiggly lines
06:35 : in there so I think I'm just gonna bite
06:37 : the bullet and reference their could in
06:40 : order to figure out what include what
06:44 : includes I need at the top here hmm so
06:48 : we got all of these stuff that are
06:50 : coming from LLVM so I mean just copy all
06:54 : of those and see if that makes the
06:59 : things go away so the red the red things
07:03 : go away
07:07 : [Music]
07:17 : I'm not sure that worked no that worked
07:20 : yay I think it worked anyway what are
07:24 : these red squigglies cannot open this
07:27 : source file actually doesn't know how to
07:36 : open the source file I suppose what I
07:39 : could do is have a directory have a LLVM
07:47 : directory next to this project so that
07:55 : but right now I guess the editor doesn't
07:59 : know the editor still doesn't know what
08:01 : these things are but I think the
08:03 : compiler would know based on how I I can
08:10 : inform the compiler sort of where the
08:12 : includes are which is what that ll
08:15 : config tool does for you in any case ok
08:19 : I'm not gonna fret too much about this
08:21 : actually I'm just gonna follow the
08:23 : tutorial I have figured out how to
08:25 : compile the code so that should be good
08:27 : enough for me so so that's um
08:32 : so the code gen method for the number
08:36 : expert ast does this it just defines a
08:39 : constant FP FP
08:45 : what does FP mean if probably means
08:48 : floating point yeah that's what I'm
08:51 : thinking
08:53 : so constant FP which holds the numeric
08:57 : value in an AP float internally yeah so
09:01 : FP stands for a floating point so it's a
09:04 : floating point constant and this makes
09:07 : sense because it represents like numeric
09:11 : literal in your code so so basically
09:15 : we're translating a number in the code
09:19 : into a a floating-point constant
09:26 : construct within LLVM ir that's what
09:30 : we're doing here
09:32 : next let's do this for the variable
09:35 : expert ast so I put it under the
09:38 : variable X per class so again this
09:42 : returns a value a value is apparently a
09:45 : a like a construct or a value in in
09:51 : terms of the LLVM I our language
10:07 : okay we're gonna look up this named
10:09 : values symbol table to see if where does
10:16 : this name come from Oh from our name so
10:22 : this is a variable reference so I'm
10:24 : gonna see if the variable our variable
10:29 : exists in this symbol table if not then
10:33 : we're in trouble
10:34 : okay we're just gonna air out basically
10:52 : we're gonna return the V wouldn't we oh
10:59 : I see if it's undefined if it's no we're
11:04 : also gonna just return that it would
11:06 : just be no that's fine okay I guess
11:12 : we're expecting another piece of code to
11:15 : actually enter values into the named
11:17 : values map aren't we okay let's look at
11:22 : the same the Cochin method for binary
11:26 : expiry is T and let's type that in
11:34 : okay so we're gonna call the Cochin
11:40 : method for whatever is the note on the
11:44 : left hand side because left hand side is
11:46 : another expert est it's a subclass but
11:51 : we don't care what subclass it is we're
11:53 : just gonna call its Kudrin we're gonna
11:55 : do the same with right hand side oops
12:03 : and then and then if if either left hand
12:10 : side or right hand side is non-existent
12:12 : or or didn't work out we're gonna say
12:18 : we're gonna return the null pointer to
12:20 : signal that it didn't work out and then
12:24 : depending on the operation that our
12:30 : binary expression represents because a
12:33 : binary expression represents a binary
12:36 : expression which looks like something
12:38 : like this and that is the pop this
12:40 : operator so we're gonna depending on the
12:43 : operator we're gonna use a different
12:45 : LLVM ir construct we're either gonna use
12:48 : the floating point add the floating
12:51 : point subtract floating point multiply
12:53 : or this is a comp comparison so this is
12:57 : a less than let's compare a LT probably
13:07 : means less than I don't know what you
13:12 : means you may be unsigned probably
13:15 : unsigned less than is what I'm thinking
13:20 : that means all right so let's let's do
13:23 : that let's type that coudn't
13:37 : and these temp variable names that's
13:43 : that's just a suggestion to to the LLVM
13:48 : builder as to what to call this variable
13:51 : you'll see where that shows up so it's
13:55 : not terribly important what we named
13:57 : this at temp is it means like a
14:03 : temporary variable for the result of the
14:06 : end addition is basically what it means
14:16 : copy and paste whoops what is with my
14:21 : computer it's so slow
14:54 : here we're actually going to set he'll
15:01 : assign a new value to elf for some
15:04 : reason not sure why wait does the cursor
15:10 : jumping backwards maybe I have this
15:13 : maybe I have like autosave enabled or
15:18 : something I got turned it off this is
15:21 : really bothering me I'm gonna do that
15:24 : offline later okay and then we're gonna
15:32 : convert this bull zero or one two double
15:36 : zero or one point zero so so this
15:41 : comparison is an unsigned comparison
15:45 : probably I actually don't know it's a
15:49 : less than comparison but the output is a
15:52 : boolean so which is why we we need to
15:56 : the builder to generate a conversion
16:02 : operation I get double type get double
16:10 : type the context okay okay I record this
16:32 : bull temp I thought we were converting
16:38 : the boolean to a double so it would be a
16:40 : double when Lucy Lucy I think later on
16:45 : we can actually get to see the code the
16:48 : LLVM IR code that we generated using
16:51 : this builder and maybe that'll be clear
16:55 : once we see it
17:01 : okay so if it falls through with you an
17:05 : error it's not one of the known binary
17:08 : over I think I did try to allow greater
17:11 : than and divided I'll do that later okay
17:17 : the binary operators start to get more
17:19 : interesting the basic idea is that we
17:21 : recursively an MIT code for the
17:23 : left-hand side of the expression and
17:24 : then the right-hand side right so the
17:26 : left-hand side is yet another binary
17:30 : expression it would recursively go do
17:32 : this stuff again but if the left-hand
17:34 : side was a variable then it would go do
17:37 : this but if the left-hand side was a
17:38 : number then it will go do this right so
17:41 : we'll either get this guy or this guy or
17:45 : the result of this guy depending on what
17:48 : type of node the left hand side or the
17:51 : right hands is but once we get the value
17:53 : for both of them then we sort of combine
17:57 : them using one of these create operation
18:05 : methods on the Builder saying in this
18:12 : code example the builder class is
18:14 : starting to show its value I our builder
18:16 : knows where to insert the newly created
18:19 : instruction all you have to do is
18:20 : specify what instruction to create so
18:24 : we're creating an add instruction yeah
18:28 : an instruction is a good term good noun
18:31 : to use for what these things are one
18:36 : nice thing about LLVM is that the name
18:39 : is just a hint so it's talking about
18:41 : these names here these variable names
18:43 : they're just a hint for instance if the
18:46 : code above and that's multiple apt temp
18:48 : variables yeah like you can have
18:50 : multiple attempts it's not a problem you
18:52 : just automatically make the names unique
18:57 : with a unique numeric suffix and we'll
19:01 : see that later as well
19:08 : so we have strict rules about what
19:12 : operation can happen for example left
19:15 : hand side and right hand side of an add
19:17 : instruction must have the same type and
19:19 : the result type of that must also match
19:21 : the same type on the other hand it
19:29 : specifies that the Afcon instruction
19:32 : which I think is this one this is the F
19:35 : comm instruction it wants the F comp to
19:41 : always return an i1 a one bit integer
19:47 : one bit integer really how do you even
19:51 : like represent a 1 bit integer the
19:56 : problem with this is Kaleidoscope wants
19:58 : to value to be a zero point zero or one
20:02 : point zero value so we combine the F
20:05 : instruction with a u I - FP instruction
20:10 : to convert system yeah I got that ok I
20:14 : was implement the call expression AST
20:17 : method
20:51 : okay so we're gonna get a function from
20:54 : the module hmm based on quality which
20:59 : Kali is just the name of the function
21:01 : it's a string I'm not sure how the
21:05 : module is gonna get a function or maybe
21:07 : it if it's not already there it'll
21:09 : probably just on-the-fly generate one
21:13 : for you that's my suspicion and I guess
21:16 : if it didn't work no I guess not because
21:20 : if it doesn't return you anything it we
21:23 : should reference so I guess not so
21:31 : somebody the the the syntax that defines
21:35 : a function would have to put the
21:37 : function there I think okay so if holy F
21:43 : part size is not the same as our X dot
21:49 : size so if the number of arguments do
21:52 : not match then we also have an error
21:56 : situation I'm gonna return a null
22:00 : pointer that's what I said I would do
22:03 : but I kind of forgot again just in case
22:18 : you're in confused I'm deviating from
22:20 : the way that tutorial does it the
22:23 : tutorial has the law error functions
22:25 : return a type for each specific type
22:31 : that it wants to return and it just
22:34 : returns whatever the login function is
22:38 : returning
22:38 : but in internal e to the log error
22:41 : function it just returns a null pointer
22:43 : so I I think in my opinion it's slightly
22:48 : better to just not have different
22:51 : versions of the log error function and
22:53 : just have one log error function and if
22:55 : you're gonna just return a null pointer
22:57 : just return it
22:59 : of the error function every log error
23:01 : function so that's what I'm doing okay
23:11 : now I'm going to loop through the
23:14 : arguments or we are we generating now
23:17 : we're generating a new vector of
23:19 : arguments interesting why are we doing
23:24 : that unsigned is a unsigned number what
23:41 : the heck is this
23:42 : oh oh this is I plus plus okay that's
23:45 : fine
23:46 : let's see
24:01 : e is the size of Arc's
24:05 : not this arch this is arts V but this
24:08 : arts and this arts is the arts that was
24:12 : the was parsed by the parser so it's
24:17 : saying we're gonna loop through the arcs
24:20 : that was parsed by the parser this is a
24:23 : call expression so it's something like a
24:25 : co expression is like with these parts
24:34 : so these guys are the arcs and this guy
24:38 : is the Khali we're looping through the
24:46 : arcs and for each arc we're gonna add it
24:48 : to this arcs me vector which is like an
24:53 : array again it's a dynamic array and
24:55 : then we're gonna say ask the arc to
24:59 : Cochin itself
25:01 : hey Coco Chen yourself so for each
25:05 : argument we're gonna call the cogent
25:08 : method to generate a LLVM ir
25:11 : representation of that argument and then
25:13 : we're gonna add it to the spectra that
25:16 : makes sense to me
25:17 : and if arcs need that if not arcs need
25:24 : that back we're gonna return a null
25:26 : pointer what the heck does that mean
25:29 : Oryx feed that back what would it was
25:32 : back
25:35 : [Music]
25:41 : does it explain it no it doesn't really
25:49 : bother so I have I'm gonna google it
25:51 : what is the C++ vector back method
25:56 : there's a method called
25:59 : back what is back that might mean the
26:06 : last item in the vector returns a
26:09 : reference to the last element in the
26:10 : vector that makes sense okay so it's
26:13 : saying I guess after I push something to
26:18 : the back if it still doesn't exist
26:21 : what then something happened terribly
26:25 : wrong I probably what happens is if this
26:28 : coachin return a null value a null
26:31 : pointer then push back probably just
26:33 : doesn't do anything
26:35 : Oh doesn't it push a null pointer into
26:40 : the back so then this is like let me
26:43 : look at what thing got pushed to the
26:46 : back and if it's a null pointer then
26:48 : we're airing out of here that's what
26:50 : that's doing okay that makes sense now I
26:55 : hope it made sense to you as well
27:06 : okay so once we have this vector of
27:11 : value pointers that were then we're
27:15 : gonna generate a call instruction which
27:20 : represents a function call in LLVM I our
27:25 : language with this function name and
27:28 : this set of arguments that all makes
27:31 : sense this just feels like translating
27:33 : our AST to almost like another AST that
27:38 : that is actually what is doing it's just
27:41 : we're translating into the ast of the
27:43 : LLVM I our language okay and function
27:50 : code generation I'm thinking I would
27:55 : stop here for this video and then we'll
27:58 : continue finishing up this chapter in
28:02 : the next video hopefully how how much
28:06 : more do we have to go I think yeah I
28:08 : think not much longer in this chapter
28:11 : but I'll finish it up in the next