LLVM Tutorial #9: CodeGen for Functions

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 wrote some code to generate LLVM IR code for the first time. This time we continue on generating IR code for function definitions.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hey welcome back to this series where we
00:04 : follow the LLVM tutorial for building
00:08 : our first programming language using
00:10 : LLVM we're in the middle of the chapter
00:16 : 3 and at this point at this point we've
00:19 : written some code to generate the LLVM
00:23 : representation of several of the
00:26 : language elements including variable
00:29 : references numeric competence binary
00:34 : operations now we're gonna work on the
00:38 : function code generation so we also made
00:43 : the did that for a function call
00:46 : expression as well but this time we're
00:48 : going to generate the LLVM ir code for a
00:53 : function definition so close so let's
01:01 : see how to do that
01:03 : we're first going to generate the code
01:07 : implement a code Chen method for the
01:10 : prototype ast node and as a reminder the
01:17 : prototype ast node means the signature
01:22 : of a function so if you define a
01:24 : function like I'm gonna define a
01:27 : function it's gonna add x and y together
01:33 : then the proto of the function is just
01:38 : that part that's called the prototype of
01:41 : the function for for some reason that's
01:44 : what they call it I also hear it
01:47 : commonly referred to as the signature of
01:50 : the function I like that name better but
01:54 : anyway in this tutorial they call that
01:56 : the prototype of the function and so
01:59 : we're gonna generate something that
02:02 : represents that in LLVM I our land so
02:07 : let's let's copy this bit of code
02:12 : so it's gonna return a function whatever
02:17 : that is it's a pretty cool doubt that in
02:23 : LLVM i are just the concept called
02:27 : function that we can just hook into
02:31 : because clearly our language has a
02:35 : concept called functions okay so what is
02:51 : this doing here
02:53 : whoops I didn't mean to make a
02:55 : breakpoint so what is this doing here
02:57 : we're creating a vector that contains
03:05 : these pointers to types okay so I think
03:12 : we want to represent the type of each
03:16 : argument or each parameter of the
03:21 : function so like as in what's the type
03:24 : of X we have to actually define the type
03:28 : of X and the type of Y for LLVM I are
03:33 : before it's willing to do its job so and
03:37 : we said early on in the tutorial that
03:40 : this language only supports one type and
03:45 : that's doubles double double for ten
03:50 : point numbers so that's the type it's
03:55 : going to be for any number of arguments
03:59 : and that kind of makes it easy that's
04:02 : that's cool
04:02 : so this is get double type I think this
04:06 : is how you sort of instantiate a type
04:12 : this probably just says set every
04:17 : element
04:18 : up to this size to that value that's
04:22 : what I'm guessing this means and then
04:26 : we're gonna also make a function type it
04:29 : looks like function type I bet you is
04:35 : like function signature so this function
04:53 : type probably it takes some parameters
04:56 : but the first parameter is the argument
05:00 : list the types of the argument list
05:03 : which we already have figured out and
05:08 : then actually no I think the second
05:15 : argument to this function type get is
05:19 : the types of the argument this but the
05:21 : first one I bet you is the return type
05:26 : and I guess the return type is always
05:29 : going to be a double I don't know what
05:32 : this false means let me read this the
05:36 : tutorial probably explains it this code
05:41 : packs a lot of power into a few lines
05:44 : love it note first that this function
05:47 : returns a function pointer instead of a
05:50 : value pointer because a prototype really
05:53 : talks about the external interface were
05:56 : a function not the value computed by an
05:59 : expression it makes sense for it to
06:04 : return the LLVM function it corresponds
06:07 : to when cogent cogent that's a verb
06:12 : clearly the call to function type get
06:17 : creates the function type that should be
06:20 : used for a given prototype since all
06:22 : function arguments to Kaleidoscope are
06:25 : of type double the first line creates a
06:30 : vector of
06:31 : LLVM double types it then uses the
06:34 : function type get : : get methods to get
06:37 : to create a function type that takes n
06:40 : doubles as arguments returns 1 double as
06:44 : a result and that is not var art the
06:48 : false parameter indicates this Oh false
06:51 : means it's not VAR arc VAR Erik means
06:55 : variable length argument of s so it does
06:58 : not take any number of arguments is what
07:00 : false means qu let's write the next line
07:05 : and then maybe read the tutorial ok I
07:16 : think my computer has calmed down which
07:21 : is good I mean double check to make sure
07:24 : it's still recording you never know
07:27 : alright it is recording external linkage
07:42 : the module attack text editor is getting
07:49 : in my way yeah okay the module : get so
07:57 : what does this do well we're gonna
07:59 : create a function based on this function
08:02 : type and this external linkage I it
08:10 : probably means external like I didn't
08:13 : supply the definition the definition of
08:16 : this function or this is is a function
08:20 : signature definition and the name of the
08:23 : function
08:23 : so did I bet you that creating this
08:26 : function then later on will allow this
08:30 : previous get function call over here
08:33 : which is used by the core function
08:37 : co-expression to work and then this
08:45 : module get I guess it will put this
08:48 : function inside this module that's my
08:51 : guess okay so the final line above above
08:56 : actually creates the I our function
08:58 : corresponding to the prototype this
09:00 : indicates the type linkage and name to
09:03 : use as well as which module to insert
09:06 : into external linkage means that the
09:10 : function may be defined outside the
09:12 : current module and or that is callable
09:15 : by functions outside the module the name
09:18 : passed in is the name the user specified
09:24 : right since the module is specified this
09:28 : name is registered in the mod Rose
09:31 : symbol table that makes sense okay now
09:37 : now we need to set the names for all the
09:40 : arguments interesting okay let's do that
10:08 : okay how does this work
10:13 : oh we to this function apparently has
10:20 : these arcs already sort of like
10:25 : pre-populated but they need names okay I
10:28 : bet you these arcs are created based on
10:31 : the function type because the function
10:34 : types it had these many arguments right
10:39 : but but we still have to go to and set
10:41 : the names for for each for each arc this
10:51 : arc is referring to this part that was
10:55 : parsed during the parsing process and
10:59 : then finally we got our function we're
11:01 : gonna return it from this cogent method
11:04 : okay got it
11:06 : so this seems to make sense now finally
11:09 : it's right the cogent method for the
11:11 : function ast so in the parser we kind of
11:15 : split up a function ast into the proto
11:20 : part and the function part and the
11:23 : function contains the proto part plus a
11:26 : body which is a an expression so now we
11:32 : have just implemented the cogent method
11:34 : for the proto but now we need to do that
11:37 : for the function
12:03 : okay was this first name first line
12:06 : doing it's just getting the D function
12:11 : based on the name that from the proto
12:15 : but which assumes has already been
12:19 : defined why can it assume that if it
12:31 : doesn't if it's not there then
12:33 : then we're gonna Ghent Cochin the proto
12:36 : interesting
12:37 : so maybe the function has already been
12:40 : defined I don't know hmm interesting
12:48 : I'm not entirely sure how this logic
12:52 : works but I mean keep typing out this
12:57 : code first so if we didn't actually get
13:03 : a function from the module like that we
13:06 : haven't already defined this function
13:09 : then we're gonna lazily tell our proto
13:14 : to define the function because we just
13:16 : real code coach encode inside the proto
13:19 : to do that so yeah if it's not already
13:23 : defined we're gonna define it
13:25 : essentially but if if even after that if
13:32 : even after that we still don't have a
13:35 : function then something really wrong has
13:38 : happened and we're just gonna return the
13:40 : null pointer you know when in doubt
13:44 : return null pointer and then
13:53 : if the function is empty I don't even
13:56 : know what that means
13:59 : function cannot be redefined I'm gonna
14:02 : ever out I'm gonna just call my generic
14:10 : log error function C function cannot be
14:15 : redefined I don't really understand why
14:18 : let me read the tutorial explain itself
14:22 : function definitions we start by
14:26 : searching the module symbol table for an
14:29 : existing version of this function in
14:31 : case one has already been created using
14:33 : an external statement so like okay I got
14:36 : it
14:36 : so maybe like you had an external
14:40 : statement extern I don't know there's a
14:45 : distance function that takes X Y x2 y2
14:53 : or something and now you're trying to
14:57 : define another dist function in blah
15:01 : blah blah and then you know it'll find
15:05 : the first one the previous and those
15:07 : that was defined and so and so you're
15:12 : not gonna try to do that again but okay
15:17 : interesting
15:19 : if module gets function returns no then
15:24 : no previous version was exists so we'll
15:27 : Cochin one from the prototype in either
15:29 : case we want to assert that the function
15:30 : is empty that it has no body yet so okay
15:35 : so we at this point the function MT
15:39 : means the function has no body yet we're
15:43 : gonna define it but it already has a
15:45 : body that's a problem because we don't
15:47 : we don't want because we don't want to
15:50 : nuke what it already has so so we error
15:55 : out and say we cannot redefine it but if
15:58 : it's not empty I mean if it is empty
16:01 : then that's good we're gonna
16:02 : we're gonna define what the function has
16:05 : now great so that's the next step so
16:11 : we're gonna do basic block B b1 star not
16:16 : too basic block colon colon create the
16:21 : context entry the function builder that
16:30 : set insert point
16:32 : PB what does this mean named values not
16:38 : clear why are we clearing the named
16:42 : values this doesn't make sense
16:45 : record the function arguments in the
16:48 : named values map but why are we clearing
16:51 : it what like what if another function to
16:59 : create some named values and now that's
17:02 : gone right
17:18 : okay so why are we doing this that's
17:23 : sweet that's read together an
17:25 : explanation now we get to the point
17:27 : where the Builder is setup the first
17:28 : line creates a basic block that I
17:31 : imagine that's like the code block which
17:35 : is inserting is the function so we're
17:37 : gonna create a basic block this is the
17:43 : function reference to tell it to insert
17:46 : into the context is just global context
17:51 : it doesn't matter that much entry I
17:54 : don't really know why we call it entry I
17:57 : guess we just named the block I have to
18:00 : give the block a name we're gonna name
18:01 : it entry so there's the block we're
18:05 : gonna set insert point what does that
18:09 : mean the second line then tells the
18:11 : Builder that new instructions should be
18:14 : inserted into the end of the new basic
18:17 : block okay interesting
18:21 : okay so the new instructions by new
18:24 : instructions I think it means whenever
18:27 : it's doing stuff like builder that
18:32 : create call or builder that create F hat
18:37 : builder that create F sub etc that has
18:40 : to get inserted into this graph this is
18:44 : kind of like jQuery training so we're to
18:49 : relate it to jQuery but that's kind of
18:52 : like to the insert point is like stick
18:56 : it into this subtree so so like yeah and
19:01 : Drake for you right we may explain this
19:05 : in terms of cheek right but in jQuery
19:07 : you you might do something like a I want
19:10 : to select this element with the ID of
19:15 : the thing and and I wanna like do a
19:21 : whole bunch of stuff to it maybe like
19:25 : add a class to it blah blah blah I want
19:32 : to change the attribute etc and then so
19:37 : all of these instructions apply to this
19:40 : subtree which is started by that thing
19:44 : but you know if we didn't do that if we
19:47 : just started at the top of the document
19:50 : or something then the insert point is at
19:55 : the document or maybe document that body
19:58 : would be more correct
19:59 : so the insert point is like the current
20:02 : point within the tree that all these
20:06 : create statements are going to go into
20:08 : and here we're saying we created this
20:12 : function that looks like this and we
20:17 : just created this function block we're
20:20 : gonna call this entry and insert point
20:24 : is here so whenever you're gonna create
20:26 : a statement it's great whatever
20:31 : the thing that gets created gets
20:33 : inserted in here so that's what set
20:35 : insert point is doing for us record the
20:41 : function arguments in the named value
20:44 : snap okay so I wrote this code already
20:52 : let me get an explanation for it basic
20:54 : blocks in your VM are an important an
20:57 : important part of functions right that
21:01 : we define the control flow graph since
21:04 : we don't have any control flow graph our
21:06 : functions will only contain one block at
21:08 : this point we'll fix this in Chapter
21:10 : five next we add the function arguments
21:13 : to the named values map after first
21:16 : clearing it out that's so that they're
21:19 : accessible to variable X / ast nodes
21:24 : why don't we cleared out that too part
21:28 : I'm confused about
21:32 : [Music]
21:46 : okay we'll figure that out later okay
21:49 : next well we add the function arguments
21:54 : to the name value snaps yeah we already
21:58 : read that okay the next part is this
22:00 : alright let's type that code in there's
22:04 : a lot to this if the value R it Wow
22:12 : I prefer to do it as as a separate line
22:21 : okay so if we code gen the body and we
22:26 : got something back that's not null then
22:31 : we're gonna say builder that create
22:34 : reach that's a return value I bet it's
22:39 : like a return statement and then we're
22:41 : gonna verify the function okay it's
22:51 : interesting that we need to verify the
22:53 : function I don't know how we do that let
22:57 : that make sense to me so whatever is the
23:00 : currently the body of the function only
23:02 : has one expression in it we're gonna
23:05 : code gen that expression and then
23:09 : whatever the value is we'll use that in
23:12 : the return statement okay so once the
23:15 : insert an insertion point has been set
23:17 : up in the name value map populated we
23:19 : call the code gen method for the route
23:22 : expression of the function excuse me and
23:27 : if no error happens this emits code 2d
23:30 : compute to compute the expression into
23:34 : the entry block and returns the value
23:35 : that was computed assuming no error we
23:38 : then create an LLVM rich for a return
23:42 : instruction which completes the function
23:44 : instead function is built we call verify
23:46 : function which is provided by LLVM so we
23:49 : didn't have to read that this function
23:51 : does a variety of consistency checks
23:54 : with a generated code
23:56 : many of our compiler is doing everything
23:58 : right using this is important it can
24:01 : catch a lot of bugs once the function is
24:04 : finished and validated we return it okay
24:11 : we ever reading body remove function no
24:19 : I guess oh I see if we didn't
24:27 : successfully get a body to code Jen then
24:32 : we actually want to erase like clean up
24:35 : clean up everything that we made he
24:38 : raised more or less and then we turn a
24:42 : null pointer okay Emily please left here
24:47 : is handling up the error case for
24:48 : simplicity we handle this primarily
24:50 : deleting the function we produced with
24:53 : the erase from parent method this allows
24:55 : the user to redefine a function that
24:57 : they incorrectly typed and before if we
25:01 : didn't delete it it would live in the
25:03 : symbol table with a body preventing
25:05 : future redefinition if this code does
25:08 : have a bug though if function ast cochin
25:12 : method finds the existing ir function it
25:15 : does not validate its signature against
25:17 : the the definitions own prototype this
25:21 : means that an earlier external
25:23 : declaration will take precedence over
25:25 : the function definitions signature which
25:27 : can cause cogent to fail
25:29 : for instance if difference yeah yeah
25:32 : that makes sense
25:33 : but what is saying is that if you yeah
25:36 : kind of this scenario I actually already
25:38 : laid out before if a cogent f it takes X
25:42 : for example but then you wanna later on
25:46 : redefine F with a different parameter
25:49 : list
25:50 : I think there's no comma then this case
25:57 : will fail because it will actually use
25:59 : this signature of the function but with
26:03 : a body
26:06 : that's defined in here maybe it returns
26:09 : X plus y times Z I don't know and then
26:14 : there's gonna be inconsistencies I think
26:20 : that validate function will error out
26:22 : probably when you do this anyway so
26:26 : driver changes and closing thoughts so
26:28 : from now code generation to VMV LLVM
26:31 : doesn't really get us much except that
26:33 : we can look at the pretty ir a calls so
26:36 : let's look at those pretty ir calls so
26:39 : this sample code inserts calls to code
26:42 : gen into the handle definition handle
26:47 : extern etcetera functions and dumps out
26:49 : LLVM ir this is a nice way to look at
26:52 : that LOV Mir for simple functions for
26:56 : example you can use this rap oh now type
26:59 : in an expression it will show you the
27:02 : LLVM let's actually get it to do that
27:04 : though it so we'll have to steal that
27:08 : from the full code listing because it
27:14 : didn't actually show that as part of the
27:18 : tutorial strangely but I think the only
27:23 : parts we need to grab is these three
27:26 : handle functions handle definition
27:29 : handle its turn and handle top-level
27:31 : expression I am a little bit surprised
27:36 : that it didn't explain this because this
27:42 : is gonna give us a I guess it's gonna
27:46 : get the result of parse definition and
27:49 : then call Cochin on it to get a ir form
27:53 : of the code and then we can actually
27:58 : print it oh the ir form of the code has
28:02 : a print method why are we giving to
28:07 : print this errors thing I have no idea
28:10 : what that is but in any case we can
28:13 : print it
28:15 : so let's steal these three functions
28:19 : stick it in our code I'm gonna replace
28:22 : those same three functions which came
28:26 : from the previous chapter replace them
28:30 : with B's and hopefully it can build I
28:35 : don't know if it can but I'm gonna call
28:37 : my built script which will attempt to
28:41 : build it that did not work use of
28:46 : undeclared identifier builder 20 errors
28:50 : generated let me look at my build screen
28:58 : um first of all I think ooh they're
29:08 : built come in has these extra stuff in
29:11 : it so I'm gonna use this so this this is
29:13 : the command that I used to build used to
29:18 : build their version of the code so I'm
29:20 : gonna steal from that probably I used G
29:24 : plus plus I think that's the same as
29:26 : clang plus plus not 100% right oom a CH
29:32 : my build command to their build come in
29:39 : still no luck
29:47 : try to change this to clang plus plus
29:50 : maybe that makes a difference
29:59 : nope okay I'm gonna need to debug this
30:04 : so I'm gonna do a just just do a visual
30:10 : comparison of what I have versus what
30:13 : they have hopefully that can give me
30:17 : some hints as to what the problem is
30:21 : because I think building their code with
30:27 : this command does work I have tested it
30:29 : last night
30:41 : with all of these warning but it does
30:43 : work so now my code does not have some
30:50 : of these includes maybe they are needed
30:53 : so I'm gonna try adding them in this
30:59 : algorithm CC type CS standard io CS c
31:08 : standard lip okay
31:12 : oh we're using namespace LLVM that's a
31:17 : biggie do we need that maybe we need
31:24 : that I bet we need that okay let's do
31:28 : using namespace LLVM
31:37 : it's still 20 error generator use of
31:43 : undeclared identifier the context oh
31:46 : okay I think this is just a where I
31:49 : declared the thing so I'm gonna move
31:52 : these guys to the top I have to define
31:56 : it before code actually tries to use it
32:00 : is what it is perhaps I'll have to
32:07 : static global variables all the way at
32:12 : the top together these are for the
32:16 : parser and lexer and these are for the
32:22 : couch in okay now try to compile it
32:39 : still 20 errors too many years but we
32:42 : did get rid of that first error so out
32:45 : of line definition of Coach n does not
32:47 : match any declaration in variable expert
32:51 : ASE oh I see
32:53 : I think I know what is this I did not
32:59 : see how okay I'm gonna close there to it
33:03 : for a moment see how in here for the
33:07 : number expert ast I actually had to
33:10 : write this repeat this definition of the
33:14 : code gen method in the body of the
33:16 : number X / ast class and I actually
33:20 : didn't do that for the other subclasses
33:24 : so I actually have to do that for every
33:29 : subclass I'm just gonna copy it to every
33:32 : subclass
33:55 : okay and I think I just did that so let
33:58 : me try compiling it again 15 years yes
34:09 : the list is actually tractable now it
34:13 : didn't say too many errors it it's not
34:21 : too many errors it's just the right
34:23 : number of they're just the right amount
34:26 : of errors okay anyway
34:28 : log error use of undeclared identifier I
34:32 : bet I just need to move like I have a
34:35 : four declaration of log error is
34:37 : probably what I need yeah or I can just
34:42 : move this whole thing on to the top
34:44 : actually that's what I'm gonna do
34:48 : or near the top
35:04 : eleven error okay I'm getting smaller I
35:08 : cannot return the thing that's supposed
35:13 : to be void right 178 so I so here I'm
35:23 : just deviating from the tutorial and
35:27 : that's the difference ten errors who he
35:41 : is not declared 209 so a lot of these
35:44 : errors are coming from tool Knights who
35:46 : can probably kill a lot of with one shot
35:49 : he has not been declared
35:54 : like what is this e equals here not
36:00 : daddy this e e equals R X dot sighs they
36:09 : didn't declare e either
36:11 : what the heck where is e oh oh this is
36:18 : Cana this is a comma not a semicolon I
36:25 : think that makes a difference
36:26 : oh this e is unsigned so that I see this
36:31 : is a variable declaration list that
36:34 : declares first I and then e okay that
36:39 : will probably fix it done only for
36:45 : errors left okay
36:47 : return type of out of line definition of
36:50 : prototype est coach and differs from
36:52 : that in the definition 232 it is saying
37:01 : oh okay
37:06 : yours is saying that hey you said it's a
37:09 : return a value but value point of it
37:12 : actually returned the function pointer
37:14 : okay fine let's make them match I hope
37:17 : that works because the superclass
37:19 : actually said is a value pointer you
37:22 : know a function I assume is a subtype of
37:26 : value that did fix it when they have two
37:30 : errors left the error is d module is in
37:41 : is not a class namespace or enumeration
37:46 : the module is declared over here
37:52 : [Music]
38:03 : he D module right we declared the module
38:11 : I just copied his code man
38:13 : it is a unique pointer to a model so the
38:22 : line is complaining about is 239 let's
38:25 : go back there and this line it looks
38:31 : like function : : create oh it's D model
38:39 : that get not not the module : : get
38:56 : one last error okay so this one is
39:00 : similar to a previous one that I fixed
39:03 : this returns a function pointer and 262
39:10 : and so I just need to make this
39:13 : signature a match over here
39:36 : and it built with all of these errors
39:39 : that says my like diversion of the
39:44 : library it was compiled for is newer
39:47 : than my max especially saying my Mac is
39:52 : old I'm gonna ignore those warnings I
39:56 : think it was successful in building my
39:59 : binary program so at this point I have
40:04 : this rep whole and you make the font
40:07 : size a little bigger that there's ripple
40:09 : now and I can type expressions in the
40:12 : language within the ripple a semicolon
40:16 : and when I hit enter it's sick it's sick
40:33 : faults oh man this is gonna be a painful
40:36 : or potentially it could be a painful
40:38 : buck hunt actually um let me think this
40:48 : session has gone on so I'm gonna stop
40:51 : this video short the good news is we
40:55 : figured out how to build the program the
40:56 : bad news is it has a sick fault we will
41:00 : need to use some debugging techniques I
41:04 : think to get to the bottom of the sick
41:07 : for but yeah I'm gonna end this video
41:12 : here and I'll see you on the other side