LLVM Tutorial #21: "For" Expr 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 implemented the parser for the for loop expression, and this time we'll implement its code generator.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello it's toby and welcome
00:03 : back to this series where we walk
00:05 : through the llvm tutorial
00:08 : uh the tutorial is called my first
00:12 : programming language front end with llvm
00:15 : i believe
00:16 : and we're making a programming language
00:18 : called
00:19 : kaleidoscope uh right there
00:22 : and we're in the middle of where we're
00:25 : at the latter half of chapter five uh
00:30 : and in the previous episode we
00:33 : we wrote the parser for the for loop
00:36 : syntax now we're going to write the
00:39 : generator the llvm
00:42 : ir code generator for the for loop
00:46 : construct so let's go do that um
00:50 : let's walk through this llvm code here
00:54 : um llvm is its own
00:58 : language is something i want to mention
01:00 : and its code
01:01 : looks like this and um
01:07 : uh let's let's look through this code
01:10 : for the
01:11 : parts of it that the for loop
01:14 : is going to generate um
01:18 : so this is these labels are like
01:22 : like go-to labels um
01:25 : you might be familiar with labels um
01:28 : with while loops i believe in c
01:31 : and a lot of other c derived languages
01:35 : your while while loop statements can
01:37 : actually jump
01:38 : to labels so this is the entry point
01:43 : label
01:43 : later on some code i don't think
01:46 : anything
01:47 : jumps to the entry point actually it is
01:50 : the entry point
01:51 : uh here we're gonna branch to the loop
01:54 : label
01:56 : uh which is right here on the next line
01:59 : so this is not
02:00 : totally necessary but this is just the
02:02 : construct the standard construct
02:06 : um that
02:10 : that is a convention that we follow i
02:12 : guess
02:14 : i also believe llvm has a scheme
02:17 : where like they have to craft
02:20 : a flow graph a certain way and maybe
02:23 : maybe this is necessary to
02:26 : to start off the the flow graph with a
02:30 : jump statement i'm not sure
02:32 : um later on you're going to
02:36 : jump back to the top of the loop
02:40 : via this what this
02:43 : br statement br
02:46 : means branch is a shorthand for branch
02:50 : so you when you use the branch statement
02:52 : you can use a
02:53 : conditional which in this case
02:57 : it is using but you can also optionally
02:59 : just
03:00 : always branch to a label so
03:05 : so there's two variants of the branch
03:07 : instruction jump
03:08 : always jump to a label or jump based on
03:10 : this
03:11 : conditional whether you jump to this
03:14 : label versus
03:15 : this label after loop is right here so
03:17 : this is saying if
03:19 : the loop condition is false we're going
03:21 : to jump out loop
03:22 : and move on and start the execution at
03:26 : after label um this
03:29 : looks very suspicious like suspiciously
03:32 : like the
03:33 : loop calendar
03:37 : yeah i'm gonna double check
03:40 : to make sure i'm using the correct
03:44 : mic
03:47 : for the recording excuse me
03:52 : yes i am using the correct mic
03:55 : all right all right so
03:58 : uh let's see what's going on here so
04:00 : this is loop counter
04:02 : uh this fi is something i
04:05 : i'm gonna try my best to explain
04:08 : uh it's the five is basically it's gonna
04:12 : merge um
04:16 : basically it's gonna assign to i either
04:20 : this or well either
04:23 : not that either this or this
04:28 : based on from where
04:32 : uh based on from where
04:35 : the execution entered this loop label
04:40 : and as you can see and i guess that's
04:43 : why this entry label is
04:44 : needed actually because in one case
04:48 : we encountered this branch statement
04:51 : which
04:51 : goes into the loop label um and in this
04:56 : case the entry point was
04:58 : entry or in this case i i should say the
05:01 : incoming
05:03 : uh code was from the entry label
05:06 : whereas in a different case
05:10 : we had a branch statement here
05:14 : that jumped to loop and for that case
05:18 : the incoming code was actually from the
05:21 : loop label
05:23 : so so basically what this file statement
05:25 : says is
05:27 : if we came into
05:30 : here via the entry label
05:34 : and assign the uh the number
05:38 : one to i but if we came into here
05:42 : via here
05:45 : then assign next var
05:49 : to i which i guess that was defined over
05:52 : here
05:53 : so that's what that's saying uh that's
05:56 : defy
05:58 : that's the phi construct or the phi
06:00 : instruction
06:02 : i did explain it i believe in a previous
06:05 : episode
06:06 : in the series so if you're confused by
06:08 : that
06:10 : uh go watch that episode
06:14 : although i don't remember which one that
06:15 : was i'm sorry i think i
06:17 : no i i think i had a video that's
06:19 : specifically called the five
06:21 : function or something so look for that
06:23 : one
06:24 : um anyway and then we have this
06:28 : put char which is just the code in the
06:30 : for loop i think i think this could
06:33 : uh the code is
06:36 : this this this is the code so that's the
06:39 : put char d
06:41 : and then we're gonna add one using the f
06:44 : at
06:44 : instruction to i um
06:48 : i guess that's that's just the step
06:52 : amount of one next var
06:55 : next bar eventually comes back here and
06:57 : goes back into i
07:00 : um
07:02 : yeah this this is this is kind of a
07:05 : weird thing
07:06 : the variables in llvm are constants
07:10 : however in this case it's it's almost
07:13 : like for
07:14 : each each iteration of this
07:18 : loop label we get to assign
07:22 : new constants right so the i
07:25 : is like a fresh eye for each time this
07:28 : loop label executes and each time the i
07:32 : gets either this one if we came in from
07:35 : here or
07:35 : whatever is the next var in the previous
07:38 : iteration
07:39 : of this loop and the next var
07:43 : is you know determined here it's based
07:46 : on i
07:47 : plus one in the previous iteration
07:50 : so the previous the next var in the
07:52 : previous x
07:54 : execution of this loop goes into i
07:57 : in this execution of this loop and then
07:59 : we move on and so forth so this is the
08:01 : lvm code
08:03 : oh this is the termination test let me
08:05 : also talk about that
08:07 : so this is saying fcom is a floating
08:09 : point
08:10 : number comparison um
08:14 : floating point number comparison uh this
08:17 : is
08:18 : double that's just the type of the
08:20 : floating point number we're
08:22 : comparing i versus n n was
08:26 : passed in as a parameter so whatever
08:28 : that is
08:29 : and then oh i i didn't see the
08:34 : the kaleidoscope code for print star but
08:37 : whatever
08:38 : um ult
08:42 : i think that means unsigned
08:51 : hello and my parents behaving weird
08:55 : unsigned less than
08:58 : i i believe that's what that means
09:02 : unsigned less than and then here
09:05 : is unsigned integer to floating point
09:09 : we're gonna convert
09:11 : because everything all numbers in this
09:13 : language
09:14 : are doubles if we end up with an integer
09:18 : we're gonna convert it into a double and
09:22 : for all comparison operations i believe
09:26 : the output is always an integer so this
09:28 : guy
09:29 : is an is an integer one actually
09:32 : i one means a one byte integer
09:35 : which means a one by integer is either a
09:38 : zero
09:38 : or one that's the only thing that this
09:40 : guy can be
09:41 : so we're going to convert that one byte
09:43 : integer to a double
09:45 : so it will be a number in double
09:48 : of either zero zero it'll be zero point
09:51 : zero or one point zero basically
09:54 : and then we're gonna do f
09:57 : com again to compare
10:00 : we're comparing one i a one means
10:05 : uh not equal oh i forget what
10:08 : o means but this one actually means
10:14 : o not equal
10:18 : uh there is a menu in uh llvm
10:24 : that lists all these stuff let me see if
10:26 : i can
10:27 : bring it up olvm reference
10:31 : manual or something like that i have
10:33 : used this
10:34 : yeah there we go and i'm gonna
10:37 : search for uh f-comp
10:41 : probably
10:44 : let's try this
10:47 : if it loads we will try it f
10:50 : comp um
10:54 : there so it has a list of all the
10:56 : instructions
10:57 : in the llvm language and it should tell
11:01 : us
11:03 : come on
11:06 : dude it's still
11:09 : trying really hard to load the page i
11:11 : believe
11:13 : there's also documentation for the five
11:15 : function by the way
11:17 : if you're interested in knowing more
11:20 : about
11:20 : any instruction so um there's
11:24 : there's this mode basically parameter
11:27 : which you see here
11:30 : so ult is one of them ult means
11:36 : an oh i was wrong i said unsigned but
11:39 : it's actually unordered it's unordered
11:43 : or less than
11:49 : an ordered or less than
11:53 : i don't understand actually
11:56 : put an order an or an order means
11:59 : either operand maybe a nan
12:03 : oh
12:07 : oh okay so if either if either
12:11 : operand is not a number then it returns
12:14 : true
12:14 : i think that's what that means whereas
12:17 : ordered
12:18 : means neither operand is nan so if
12:22 : oh if o is the first parameter if
12:25 : that means if either one is an n it's
12:29 : true whereas unordered means if either
12:33 : one is a nand it's
12:36 : uh
12:39 : the first one the the first one
12:43 : means uh if either one is a nan
12:47 : it's false actually an order means if
12:49 : either one is a nan it's false
12:52 : an order means if either one is nan is
12:55 : true uh i don't understand why they
12:58 : choose to use
12:59 : unordered in this case and order in this
13:02 : case
13:05 : but okay um
13:09 : all right there must be a re
13:12 : reason to it i'm sure but anyway then
13:15 : we're comparing this number which is
13:18 : either one and zero
13:20 : to zero so if it's it is zero then we
13:23 : doing this branch to test for the
13:25 : zeroness
13:27 : so if it is zero
13:30 : then we're gonna jump back to the top of
13:32 : the loop
13:34 : otherwise we're going to jump to after
13:36 : the loop
13:38 : uh yeah i think that's what's going on
13:40 : this this comparison
13:42 : will tell us whether it is um
13:47 : less than that number yeah
13:51 : and then that'll give us a true or false
13:53 : which is represented with one or zero
13:57 : and then we're casting it to a double
14:03 : uh so it's this this bull temp
14:06 : is zero one and then we're saying if
14:09 : it's
14:10 : zero zero would mean
14:13 : it is not less than n
14:19 : and one oh if and then we're comparing
14:22 : it to
14:24 : zero zero would mean it's not
14:27 : less than
14:30 : whatever this n is and if it's not less
14:34 : than
14:34 : n then that means it's
14:38 : probably n or greater than n then we
14:41 : want to jump out of the loop so if
14:42 : yeah so yeah that's why we're comparing
14:45 : it to
14:46 : zero okay
14:49 : anyway that's the explanation of that
14:53 : code
14:54 : and that's what this is the the code
14:57 : we're going to implement
14:58 : is going to spit out more or less
15:01 : although it's not going to
15:02 : split it's not going to spit it out into
15:04 : this textual form
15:06 : it's going to spit it out using this ast
15:09 : builder
15:11 : which you will see very soon so i'm
15:12 : gonna follow this tutorial now
15:16 : and implement this uh
15:19 : code gen method for the for exper
15:22 : ast class
15:28 : i'm going to copy this code here let me
15:30 : move this
15:31 : a little bit over
15:48 : okay so we're drilling with a lot of
15:49 : stuff here the fourth statement
15:51 : has these bits
15:55 : and we're gonna start with generating
15:57 : the code for this bit this
15:59 : bit is probably just a zero a constant
16:02 : but we're going to need to
16:03 : cogen that and we're gonna check
16:06 : whether that code gen succeeded
16:11 : to give you an idea of what that did
16:16 : that is probably the code that generated
16:22 : this literal here
16:26 : is my guess yeah
16:34 : okay
16:38 : next
16:43 : do i need this semicolon here maybe not
16:46 : okay
16:46 : next we're gonna actually get the
16:50 : make a new basic block
16:53 : for the loop header inserting after
16:57 : current block let me start typing and
17:00 : then i will try to understand
17:02 : what is actually doing
17:16 : oops
17:20 : okay so we're gonna get insert block and
17:23 : get
17:24 : parent i think that is saying i'm going
17:26 : to
17:27 : get the
17:30 : current place uh within which
17:34 : i am which is probably is probably
17:36 : within a function scope or something
17:39 : if this is this word the code probably
17:42 : within
17:42 : a function or yeah it would
17:46 : be within a function where the for loop
17:48 : statement is used
17:50 : so that that's what the function is
18:05 : now i'm gonna get a pre-header bb a
18:08 : basic
18:09 : block i think this is the
18:15 : one of the blocks either the entry point
18:18 : block
18:19 : either this block or this loop block
18:23 : that's what a block means but i'm not
18:26 : sure which one
18:27 : the pre-header bb probably the entry
18:31 : point block
18:31 : is my guess
18:35 : oh yeah i think this is the entry
18:38 : block and this is the loop block
18:41 : although for some weird reason
18:44 : we are using different mechanisms
18:47 : for creating them for creating each one
18:55 : okay so this is i believe this is saying
18:58 : um
18:59 : we're gonna create a basic block called
19:02 : a loop
19:02 : inside this context i don't remember
19:06 : where this context
19:07 : came from and then we're gonna insert it
19:11 : into the function
19:12 : like the function within which we are
19:16 : at this point
19:22 : and then we're gonna go builder.create
19:26 : breakpoint uh uh not breakpoint uh
19:30 : create
19:31 : branch br stands for for branch so
19:34 : that's gonna create this
19:35 : branch statement here for us
19:41 : get insert block this
19:44 : probably this get insert block probably
19:48 : already inserted this block here
19:53 : and then um
19:56 : and then this is saying hey and then
19:58 : that
19:59 : puts the current context at
20:02 : this entry point block and then this is
20:05 : saying
20:07 : um this is saying add another block
20:10 : within the function
20:12 : but don't insert it right here and then
20:14 : we're gonna add a break
20:16 : uh not not brick i keep seeing br and i
20:19 : call it brick
20:20 : add a branch statement that goes to this
20:24 : this loop block and now we're gonna set
20:26 : insertion point at the
20:28 : loop block bb stands for
20:31 : basic block i believe
20:34 : when you set insertion point what that
20:36 : means is the
20:37 : next uh next
20:40 : statement generating functions would go
20:43 : inside of
20:44 : that block
20:51 : which is what the next command does
20:54 : we're going to create a phi node
21:18 : okay
21:29 : okay what is this doing uh we're gonna
21:31 : create this file note
21:33 : which is that guy we're creating this
21:35 : statement
21:36 : essentially is what this is doing
21:40 : um there's going to be a variable
21:44 : this variable is going to be i uh and
21:47 : that's
21:48 : that is going to come from the var name
21:51 : that we have
21:52 : access to because var name is a
21:55 : variable instance variable within
21:58 : the for expert est class
22:02 : so that's where we're getting viral name
22:05 : we're going to create a
22:06 : phi whose type is double
22:10 : that makes sense because the type of our
22:13 : i
22:13 : or whatever variable name that happens
22:16 : to be
22:17 : is a double and in kaleidoscope in the
22:20 : kaleidoscope programming language the
22:22 : only data type is
22:23 : double so that makes that a no-brainer
22:28 : two what the heck does two mean
22:31 : i don't i think that two might mean
22:33 : there's
22:34 : two possible places two two
22:37 : uh entries here to incoming
22:41 : pointers uh for this final that's
22:45 : probably what it means ah
22:48 : that's that's my guess i'm sticking to
22:50 : it
22:51 : unless somebody tells me otherwise
22:55 : and then we're gonna add some incoming
22:59 : links so the first incoming is the
23:03 : start val start val is
23:07 : this it would have been in
23:10 : zero in this example so start val would
23:13 : be this
23:14 : one over here uh and oh start val is
23:18 : whatever
23:19 : our start code gen generated that's the
23:22 : third file so this is saying
23:24 : it's generating uh this part of the
23:26 : statement saying
23:27 : if you're coming from the entry point
23:30 : which
23:30 : i i kind of want to rename this guy to
23:33 : entry bb
23:36 : let me go ahead and do that
23:39 : okay so if you're coming from the entry
23:42 : point then
23:44 : then the variable gets the value of
23:46 : start val
23:48 : which would have been one in this case
23:51 : and we're gonna probably do a second at
23:54 : incoming
23:55 : a little bit later on okay
23:59 : uh and next we're gonna do this stuff
24:12 : we have named values
24:15 : i don't remember these things
24:24 : within the loop the variable is defined
24:27 : equal to the final
24:28 : right um
24:32 : if it shadows an existing variable we
24:34 : have to restore it
24:36 : so save it now
24:41 : oh okay where do we
24:47 : keep this is a global variable
24:50 : holy crap oh
24:56 : wow oh the variable
25:00 : expert ast
25:05 : looks up the name the values okay
25:10 : to resolve variable references
25:13 : and if it doesn't it's not in there
25:17 : then it's an unknown variable name and i
25:19 : would expect
25:20 : like a variable assignment to write to
25:24 : this
25:24 : name values
25:28 : uh a function oh we don't have variable
25:31 : assignments that's right
25:33 : but we do have um function declarations
25:40 : wait oh not function that the the
25:43 : function parameter list the function
25:46 : parameter list go into this
25:48 : named values okay got it
25:52 : um okay i think i
25:55 : vaguely understand why we're doing that
26:04 : and then we're gonna generate the body
26:07 : uh and
26:08 : the body is that basically
26:12 : we generate code for the body
26:15 : and then we're gonna do um
26:18 : if there's a step definition which is
26:21 : that guy
26:22 : we're gonna coach n for that but if
26:24 : there isn't we're gonna default it to
26:27 : a one that's what we're doing now
26:30 : so let's go ahead and do that
26:37 : so if step exists
26:41 : we're going to set step value to
26:44 : the result of coaching the step
26:54 : okay if even after the code gen we
26:56 : didn't get a step valve then
26:59 : there's a problem we're going to return
27:01 : no pointer
27:03 : to signal that it was not good
27:22 : okay if there was no step definition in
27:26 : the first place we're gonna
27:27 : make the default step value one
27:31 : and i guess that's how you do that
27:35 : next
27:43 : this is an ad instruction
27:51 : we're going to create a nextvar variable
27:56 : and create a add instruction which
27:59 : adds the step value to variable
28:02 : which is our i our loop counter
28:06 : where was that defined over here yeah
28:09 : it's
28:10 : it's the result of this phi node
28:14 : we're adding the step value to it and
28:16 : assigning it to a new variable called
28:19 : next far and now we have that
28:22 : then we have a ending
28:25 : a loop terminating condition
28:28 : this is called the n cond
28:34 : i'm going to generate the code for the
28:36 : end condition
28:37 : which is usually something like i less
28:40 : than
28:40 : n or something like that okay we
28:43 : generate the end condition
28:45 : we're going to create a comparison f com
28:48 : one f com o and e which means
28:52 : not equal we're gonna set it to to not
28:55 : equal to zero basically so n condition
28:59 : is i'm going to use the ast builder to
29:02 : create
29:04 : a f comp o and
29:07 : e which stands for ordered
29:11 : not equal
29:31 : okay uh loop count
29:35 : loop count i think is the variable
29:39 : that received the output of this
29:41 : comparison
29:42 : yeah that's that guy and then we're
29:43 : gonna need another branch statement
29:46 : after that i believe
29:48 : and but in order to set up the branch
29:50 : statement we're gonna need to
29:52 : create this after loop basic block
29:56 : bb so that's here
30:02 : please excuse the noise
30:05 : if you hear that outside
30:17 : okay i'm gonna create a loop ending
30:20 : block
30:38 : okay so we create another
30:42 : block using this same pattern here we
30:45 : first or inserting
30:51 : you're inserting a new block that's
30:54 : called the
30:54 : loop and bb
31:03 : oh wait a minute
31:29 : what does luke and bb represent is
31:32 : something that i'm slightly confused
31:34 : about
31:36 : this is saying we're gonna create a
31:37 : conditional branch
31:40 : um just
31:44 : based on the end condition it's either
31:46 : going to jump to loop bb
31:48 : or after bb after bb is this
31:51 : after loop block here
31:55 : loop bb is that but what is
31:59 : loop and bb
32:02 : what is loop and bb is the thing
32:06 : that i don't totally understand
32:13 : maybe just another pointer to the
32:17 : the loop block
32:20 : anyway i'm going to go with that
32:40 : okay and then yeah as i said before we
32:43 : need to add another incoming to the
32:45 : variable
32:48 : for that phi note
32:56 : oh i see i see yes
32:59 : i believe this is the case so loop and
33:02 : bb
33:03 : is referenced by this incoming which is
33:06 : saying
33:07 : that's what we're doing is setting up
33:10 : this entry here
33:12 : so this is saying if excuse me
33:18 : i'm gonna ignore this phone call here
33:20 : i'm sorry about that
33:22 : um it's basically setting up this entry
33:25 : and saying
33:27 : for the phi note if if the incoming is
33:30 : the loop block then i want the next var
33:35 : uh the next the value of the next var
33:38 : variable and
33:43 : the loop and bb is
33:46 : is a basically a reference another
33:49 : reference
33:50 : to the ending the the loop block
33:53 : the loop bb but i think probably because
34:00 : because this loop bb hasn't been
34:03 : inserted yet
34:04 : it's just been created you don't get an
34:08 : insertion until you
34:09 : call get insert block or something like
34:13 : that
34:13 : i believe so you create this loop
34:16 : block somewhere in midair but you
34:19 : haven't inserted it yet
34:21 : but we set insertion point to it so you
34:23 : can insert stuff
34:24 : into it but the loop bb still hasn't
34:27 : been attached
34:29 : until you do
34:34 : maybe no
34:39 : i guess this is like we we had the
34:42 : insertion point
34:43 : in the loop block here yeah
34:46 : i think this is the get insert block
34:50 : is same as this guy but get insert block
34:53 : is
34:53 : wherever your insertion point is
34:57 : get the block where it was whatever that
35:01 : is
35:01 : and in this case our insertion point was
35:03 : already inside the loop block
35:06 : so this is used to reference the loop
35:10 : block
35:11 : in this incoming statement i wonder if
35:14 : would it would have worked
35:16 : if we uh we simply change it to
35:21 : put this loop bb put this loop bb in
35:24 : here
35:26 : that probably would have worked just as
35:28 : well i could test that
35:30 : theory maybe but let me get it working
35:34 : the way that it's prescribed
35:42 : first
35:49 : we're almost to the end of this chapter
35:53 : hang tight
36:00 : okay so this is it's putting back the
36:04 : named values
36:05 : of of the old value whatever that was
36:08 : in case we're shadowing like if i was
36:13 : like a passing parameter of a function
36:17 : or something like that i believe
36:32 : okay i think this is all the code
36:36 : let me try to compile this code
36:40 : and hope it works
36:46 : of course it's not going to use of
36:48 : undeclared identifier constant
36:51 : fpf i probably
36:55 : messed that up it's constant
36:58 : fp not constant 456
37:05 : constant fp
37:21 : i think that worked so i'm going to try
37:23 : to run
37:25 : mylang.bin and try to write a
37:29 : for loop statement
37:34 : how about four
37:39 : i equals zero well
37:42 : i is less than ten
37:47 : put a step of one
37:52 : put char d of
37:55 : i oh let's do i plus
38:07 : i've been looking into some ascii art
38:08 : recently as you can tell
38:12 : okay let's start with
38:17 : zero so let's add 48 to this
38:21 : see if this works oh
38:24 : semicolon unknown function
38:30 : referenced
38:32 : so it turns out that um it was actually
38:35 : a stupid mistake that i made i in order
38:38 : to get the pachardi
38:40 : function i have to use the extern
38:42 : statement first
38:43 : so so i tested this
38:46 : and that does work so i'm going to put
38:49 : extern put char d
38:50 : so now i have the ability to do put char
38:53 : d
38:54 : 48
38:57 : and then that is going to evaluate to
39:01 : zero if i do uh
39:04 : put char d 49
39:08 : that's gonna print out one
39:11 : this one and then it says evaluate it to
39:14 : zero yeah the function evaluated to zero
39:19 : but it print out a one so now we can do
39:22 : a
39:22 : for loop like this so for i
39:26 : is uh what
39:29 : for i is zero while it's less than ten
39:32 : in the step of one
39:37 : will do put char d
39:41 : i plus 48
39:45 : and then it it prints from zero to nine
39:48 : so that proves
39:49 : that our uh our for loop
39:53 : construct works uh okay
39:56 : so i'm gonna stop this one here and uh
39:59 : i'll see you
40:00 : next time and next time we're actually
40:02 : gonna go
40:03 : tackle chapter six
40:07 : see you then