# LLVM Tutorial #18: CodeGen For If Statement

Published on Jun 20th 2020Duration: 36:19

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: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