LLVM Tutorial #18: CodeGen For If Statement

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 about the Φ (Phi) function. This time we continue on with the code and implement the code generation for the if statement as prescribed by the tutorial.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : all right welcome back to the LLVM
00:03 : tutorial walkthrough we're in the middle
00:06 : of chapter 5 we we just talked about in
00:09 : the last episode we talked about the
00:11 : five function now we're gonna implement
00:13 : the code generator for the if expression
00:15 : let's do it okay so yeah okay so I was
00:25 : beginning to do it in a previous episode
00:27 : whoops I did not mean to jump to the
00:31 : file
00:34 : Amy jump back here okay okay let me copy
00:39 : this code line by line okay so we're
00:54 : gonna so this is we're in the if
00:58 : expression ast node if expression is you
01:01 : know has three child ast nodes it has
01:05 : the cond it has the comp node so if has
01:15 : the Connaught the Connaught and then it
01:22 : has the den node and then it has the
01:27 : house node okay these are these are the
01:30 : child nodes of the if expression this
01:36 : whole thing this guy is called the if
01:39 : expression so we're first gonna ask the
01:43 : con node here to generate the code for
01:48 : itself and then we'll probably ask the
01:50 : next two things to do the same so and
01:55 : then hit this is saying well if it
01:57 : didn't work
01:59 : everything it didn't work we're just
02:02 : gonna return a null pointer and then
02:06 : we're gonna actually make a compare
02:10 : instruction and F compare which stands
02:13 : for a floating-point comparison
02:17 : let me type this out I'll do this okay
02:24 : this is a little better okay so khaandvi
02:32 : yv what does B stands for we're gonna
02:36 : this builder is a is a LLVM IR code
02:42 : builder I'm gonna use it to build a F
02:47 : comm one comparison I actually still
02:52 : don't know what the one stands for
03:10 : if Khan
03:12 : I think this if Khan is just a like a
03:15 : variable name a suggested variable name
03:20 : yep
03:21 : so this basically generates the
03:24 : instruction it generates this
03:30 : instruction this is what that line does
03:33 : yeah and then we're gonna let's see what
03:41 : is this get insert block get parent
03:45 : stuff I have no idea what that is but
03:48 : I'm gonna write it
04:05 : a basic block is like a code block
04:10 : within which you can write code so we're
04:22 : gonna create a basic box basic block
04:34 : else VB equals basic block create okay
04:45 : we're gonna create a basic block for
04:47 : then and else but not for F why not
05:03 : and then we're going to create why
05:05 : didn't we need to create a block for the
05:08 : condition the condition was convert the
05:17 : condition to a boolean oh this this
05:23 : would have already generated it maybe
05:25 : that's why hmm yeah this would have
05:30 : already generated into the current
05:31 : insert point I think that's why so it
05:35 : has already been added to the tree in a
05:38 : sense did this call to Cochin okay so
05:45 : now we're gonna face it there's gonna be
05:50 : a merge block
06:06 : and then we're gonna create a create a
06:21 : conditional branching which equates to
06:27 : basically this guy this is this branch
06:32 : condition so we're gonna create this
06:34 : branch condition and I think these basic
06:38 : blocks are going to equate to the these
06:42 : blocks like this denim is a block this
06:45 : else is a block and this if Conte is a
06:48 : block so when we're talking about block
06:50 : we're talking about those things and
06:53 : this conditional branching is
06:56 : referencing all three of these blocks
06:58 : because it needs to jump to the den and
07:01 : else blocks
07:02 : I was not referencing the if can't block
07:06 : sorry but the if can't block will be
07:10 : jumped to by the this line and this line
07:14 : in the den and else box okay so so this
07:22 : code tree is the basic blocks that are
07:23 : related to the if then else statement
07:25 : and correspond directly to blocks in the
07:28 : example above yeah exactly yeah I do
07:32 : wanna know what this get parent oh I
07:38 : think I know the get parent is to get
07:40 : the parent function that we are in right
07:44 : now because you you are we are working
07:49 : with the context of the function so yeah
07:51 : the first line gets the current function
07:53 : object that is being built so when you
07:56 : call kanako-chan
07:59 : it actually generates the line of code
08:02 : you can think of like this get parent as
08:08 : a getting a handle on
08:10 : on this bass function if if we happen to
08:13 : be in the bass function or whatever
08:15 : function you're happening to be in and
08:18 : this coachin function when we generate
08:21 : the code for the conditional it
08:24 : generates this line actually no it
08:29 : doesn't generate this line it generates
08:32 : if it's a variable reference it
08:34 : generates just this bit here if it's a
08:37 : more complicated statement it will
08:39 : generate more stuff but currently this
08:57 : is just a variable reference here so
09:00 : it'll generate just as percent x and
09:02 : then but but that code has to go into
09:06 : some function and there's a concept of
09:09 : the current insert point which is like
09:12 : this entry block so so this coachin will
09:18 : already enter the code into this entry
09:20 : block and the get parent is just getting
09:23 : a reference to this parent function
09:24 : that's all I wanted to say okay oh it
09:31 : needs this function in order to create
09:33 : another basic block because it needs is
09:38 : that right wait a minute
09:45 : the den blah we passed the function to
09:48 : the den block but we didn't have the
09:49 : function to the elves or the if can't
09:52 : block which is kind of suspicious insert
09:59 : the den block the end of the function
10:11 : note that it passes the function into
10:13 : the constructor of the den block this
10:15 : causes the constructor to automatically
10:18 : insert the new block to the end of the
10:20 : specified function the other two blocks
10:22 : are created but aren't yet inserted into
10:26 : the function Oh interesting
10:30 : once the blocks are created we can omit
10:33 : the conditional branch that chooses
10:36 : between them right that was this one
10:41 : note that creating new blocks does not
10:44 : imply implicitly effect the ir builder
10:48 : so it is still inserting into the block
10:52 : that the condition went into is it as in
11:03 : just because we created this den block
11:08 : at the end of the function you can look
11:11 : at it as you can look at it as we've
11:17 : we've created a den block like at the
11:26 : beginning of this code here let's start
11:31 : beginning let's take this slope and
11:33 : explain step by step what's going on at
11:36 : the beginning of this code we had the
11:40 : function actually had nothing but this
11:43 : empty entry block when we did calm dr.
11:48 : Jen I believe it didn't even generate
11:54 : anything until later when we said create
11:58 : this F calm one so I don't know if maybe
12:02 : it generated if this coachin was not
12:07 : just a simple variable then it might
12:10 : have generated another expression to get
12:12 : the variable but I think in this case it
12:15 : doesn't do anything with this code Jam
12:17 : and then with the create F comma one
12:23 : well it it generates this line here and
12:27 : then when we say when we say get the
12:31 : parent it just gets a reference to the
12:33 : function doesn't do anything and then
12:35 : when we create this basic block then it
12:38 : creates a distend block and inserts it
12:41 : to the end of the function but the
12:42 : cursor is still here
12:44 : I'll write the cursor like this right at
12:46 : the beginning the cursor was here but
12:49 : now the cursor is here and we did create
12:53 : this else and if can't blocks but at the
12:58 : moment we have not inserted them into
13:01 : the function yet that's what it tells me
13:03 : and then we're gonna set the insert
13:05 : point to den block so set the insert
13:08 : point moves the insert point to this den
13:10 : block so that we can actually generate
13:14 : the code for the den block and we just
13:17 : say then that code gen it actually puts
13:19 : code in here which is when we get this
13:25 : code I believe but probably not the
13:27 : branching code yet so when we say then
13:33 : that code gen it generate the code
13:35 : that's in the den block and then the
13:37 : insert point now is still in the den
13:39 : block and then we create this branching
13:44 : statement to get the den block to go to
13:47 : the merge BB block which is to say it
13:55 : adds this one the merge BB block is a
13:59 : reference to this if can't block as you
14:03 : can see here so yeah so that not now we
14:06 : generated this stuff and then
14:15 : and now we're gonna ask the Builder to
14:19 : get insert block Cochin have done can
14:24 : change the current block updates them BB
14:28 : fortify after the conditional branding
14:31 : has insert it would move the Builder to
14:33 : start inserting into the den block
14:41 : strictly speaking this call moves the
14:48 : insertion point to the end of the
14:50 : specified block however since the done
14:52 : block is empty it also starts out by
14:55 : inserting at the beginning of the block
14:58 : what I actually confuses me I don't
15:13 : understand I thought we were already in
15:16 : I thought the insertion point is still
15:19 : in the den block and the damn block
15:22 : already has this stuff in it it's what I
15:25 : thought because we set the insertion
15:29 : point to the done block and then we
15:30 : generated code in the den block so we
15:33 : expect to see code here but it's saying
15:36 : the den block is empty I was saying this
15:43 : line oh I see the first the first
15:46 : builder set insert point that makes
15:50 : sense now once insertion point is set we
15:58 : recursively code to end the den
16:00 : expression and then finish off the demo
16:02 : I will create a unconditional branch to
16:06 : the murder block one interesting and
16:07 : very important aspect of this lob are
16:09 : LOV Mir is that it requires all basic
16:12 : blocks to be terminated with a control
16:15 : flow instruction such as return or
16:18 : branch
16:18 : this means that control flow all control
16:22 : flow including 4 throughs must be made
16:25 : explicit in the LLVM ir if you violate
16:28 : this rule
16:29 : there if I will emit an error I like
16:32 : that because makes me feel more
16:35 : comfortable that when I make mistakes
16:37 : they'll be caught early the final line
16:43 : here is quite subtle but is very
16:45 : important the basic issue is that when
16:47 : we create the fine note in the merge
16:49 : block we need to set up the block value
16:52 : pairs that indicate how the fie will
16:55 : work importantly the final expects to
16:59 : have an entry for each predecessor of
17:02 : the Block in CFG why then are we getting
17:09 : the current block when we just set it to
17:12 : then BB five lines above yeah where are
17:18 : we getting the current block exactly
17:20 : that was my question the problem is that
17:23 : the done expression may actually itself
17:26 : change the block that the builder is
17:31 : emitting into if for example it contains
17:37 : a nested if/then/else expression so we
17:43 : have a nested if/then/else
17:45 : expression the den expression may
17:48 : actually itself change the block that
17:50 : the oh I see I think I understand now if
17:57 : the den has another nested if statement
18:01 : inside of it then it's doing weird stuff
18:03 : with set insertion point so this is
18:06 : saying get the current insertion point
18:10 : wherever that might have been my beam is
18:17 : that not sure I'm still confused because
18:22 : if if it did create moved the insertion
18:26 : point inside this code run when we need
18:30 : to fix that before we create this
18:34 : branching statement so still a little
18:37 : confused
18:41 : because call encode recursively could
18:44 : arbitrarily change the notion of the
18:46 : trend block we're required to get an
18:48 : update up-to-date value for code that
18:51 : will set up the final maybe we do want
19:00 : the branching statement to be there
19:03 : wherever the insertion point was at that
19:07 : point because we didn't want it to jump
19:09 : back out maybe not so sure but anyway so
19:16 : so we won we need to get this updated
19:19 : value okay let's type this note this
19:27 : code in here
20:09 : okay next we need to omit the else block
20:35 : okay okay so we're gonna put the block
20:42 : into the end of the basic block list
20:47 : which is a vector or a collection and
20:57 : then now we're going to set the insert
20:59 : point to the else block and emit cook
21:02 : for the else block just make sense
21:19 : and then also we're gonna create a
21:23 : branching statement to jump back to D if
21:30 : continued which is the merge basic block
21:33 : then again we're gonna say okay this is
21:40 : the same pattern as we did before D then
21:49 : but still doesn't totally make sense to
21:52 : me while we're doing this thing code
21:55 : generation for the else block is
21:57 : basically identical to code gen for the
21:59 : den block any significant least
22:04 : significant this difference is the first
22:08 : line which adds the else block to the
22:12 : function this one recall previously that
22:17 : the else block was created but not added
22:19 : to the function now that the den and
22:21 : else blocks are emitted we can finish up
22:24 : with the merge code okay
22:51 : oh I see why the end for this language
23:00 : the five the five variable is easier to
23:05 : deal with it's because everything is an
23:08 : expression it's a it's a pure functional
23:12 : programming language and the if
23:14 : statement is meant to always return a
23:17 : value that is why okay we're almost at
23:28 : the end of this section hopefully we can
23:35 : even build it and run it so we set the
23:43 : insertion point at merge PP there and
23:47 : then we're gonna create this final P n
23:53 : stands for fine out
24:28 : okay so I guess this is the code yeah
24:35 : this is familiar it is you you first
24:39 : push the block to the end of the
24:41 : function and then set the block st
24:45 : insertion point we're gonna create this
24:47 : fine note here which is basically this
24:53 : line here this line of C++ generates
24:58 : this line of LLVM and then at incoming
25:05 : we have to call at incoming on the find
25:08 : out to link up this part and this part
25:12 : which what that does again it says in
25:18 : our example if you watch the previous
25:24 : episode I believe or make where we're
25:26 : explaining the fire function if you come
25:32 : from this branch then I want y3 to be y1
25:38 : if you come from this branch then I want
25:41 : y3 to be y2 so this one is saying if you
25:46 : come from the den branch which the then
25:51 : block then I want the if temp to be
25:54 : caught imp because the den block set
25:57 : that up have you come from this else
25:59 : block here then I want if temp to be
26:04 : called temp one which which was set up
26:07 : within the else block so so that's what
26:11 : that is saying so now finally this code
26:15 : gen function returns to find out as the
26:17 : value computed by if then else
26:19 : expression in our example above this
26:23 : return value will feed the code for the
26:25 : top level function which will create the
26:27 : return instruction overall now we have
26:29 : the ability to execute conditional
26:31 : in 'caleidoscope I think that's the end
26:34 : of the first half of chapter 5 it was
26:38 : quite a it's a little bit much to grok
26:42 : with the five function and everything
26:44 : but let's see we can actually build this
26:46 : code I'm not sure that we can but
26:50 : fingers crossed
27:02 : okay we still get this error okay let's
27:10 : see 359 350 let's try to fix these
27:19 : errors it's saying no member called
27:26 : create F com1 in builder did I messed
27:34 : that up let me let me look at their code
27:41 : create F 1 is in all caps oh yeah one is
27:56 : in all caps okay
28:07 : NextEra 3:55 insane use of undeclared
28:18 : identifier belt it should have been
28:21 : builder okay that was easy and then use
28:25 : of undeclared identifier Vikan yes I
28:28 : didn't mean to be con with the cap Dobby
28:31 : 361 so that needs to be V with a capital
28:37 : V and so it's telling me that convey was
28:46 : declared over here
29:01 : create BR create be our pre create
29:12 : conned BR it should have been create
29:18 : convey our or create BR I think there is
29:21 : a create be our dough no member named
29:27 : convey our online 369
29:44 : oh it's our lowercase R the case matters
30:01 : one there it's the same error that I was
30:04 : seeing ouch okay and I still have to fix
30:10 : this one but I'm not sure how so what
30:14 : I'm gonna do just save this file though
30:17 : I already did actually there look at
30:21 : their code because their version of the
30:23 : code this compiled and does not have
30:26 : this problem so perhaps what I do is go
30:30 : to line 333 here and compare it to their
30:37 : version of if exper ast these are
30:47 : standard unique pointers
30:55 : is there a difference between theirs and
31:01 : mine I do not see a difference or maybe
31:13 : there's a difference I did see this else
31:16 : is green on mine not sure why
31:33 : I'm gonna try copying there and
31:38 : nullifying mine the to check whether
31:43 : it's there's a mistake in mine no that
31:59 : was not it doesnõt it
32:08 : so I'm going to go back to mine
32:21 : maybe try compiling theirs
32:33 : just make sure they're there's this
32:37 : compile and maybe I'll look for the
32:43 : references to this oh we have these move
32:57 : statements here that I don't have in my
33:01 : version maybe that's all I need it
33:21 : okay I'm gonna try again to compare my
33:26 : bird
33:45 : now it works okay I have to say the ever
33:49 : reporting for this problem is not very
33:53 : good
33:54 : well maybe for experts they kind of know
33:59 : that this is the problem it's also quite
34:02 : confusing to me that even though in my
34:06 : constructor I have these moves I have to
34:10 : call these moves again when I called a
34:16 : constructor I like the static
34:19 : initializer I already have two moves in
34:21 : here but when I actually construct a new
34:26 : one I still have to call the move over
34:29 : here hmm I don't totally understand how
34:33 : the smart pointers work but I have a
34:36 : working if statement now I should so
34:41 : let's see if it works
34:42 : so f54 does that work
35:10 : the example looks like dish
35:38 : [Music]
35:46 : I don't think things are working it
35:52 : could be that I implemented the parser
35:55 : wrong that could be the case so I think
35:58 : I'll need a debugging session to figure
36:01 : that out but um since this video has
36:06 : gone on I'm gonna stop this episode here
36:10 : and then hopefully in the next one we
36:12 : can we can do some debugging and fix to
36:15 : fix the code see you next time