LLVM Tutorial #17: The Φ (Phi) Function

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 the lexer and the parser for the if statement. This time, we talk more about SSA, and more specifically, about the Φ (Phi) function.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hey it's Toby welcome back to the LLVM
00:02 : tutorial walkthrough we're in the middle
00:06 : of chapter 5 we just built the parser
00:10 : for for the if statement or I should say
00:15 : the if expression we weren't able to
00:17 : test the parser yet not suppose whether
00:21 : we're supposed to do that but before
00:23 : doing that I took a detour because the
00:26 : tutorial has has taken one we're going
00:30 : to follow it it's telling us that if we
00:35 : write an if statement like this in the
00:40 : Kaleidoscope language and we compiled it
00:43 : into LLVM i our code that code should
00:47 : look like this let's dig into what this
00:51 : means for a bit and it tells us about
00:55 : this nifty feature of the LLVM opt tool
01:00 : opt stands for optimization I believe
01:05 : everything is abbreviated so I think
01:09 : people just naturally learn these
01:12 : abbreviated names like opt and LLVM as
01:16 : as I believe stands for the assembler so
01:21 : let's let's follow this so it's saying
01:23 : if you copy this code and and put it
01:27 : into a file and call it tol gosh why
01:32 : does it have to be T dot ll what does T
01:35 : mean I'll call it something else I'll
01:38 : call it if example ll I paste it into
01:46 : this file and then I run LLVM - yes and
01:54 : you get my terminal
01:57 : okay oh l vm - yes do I have that yes I
02:01 : do
02:04 : hello p.m. - yes less than sign that
02:10 : means tick the file and type its content
02:15 : into the standard input of LLVM yes I
02:20 : caught it if example dot at all and then
02:24 : took the output of LLB mas I want to
02:27 : just see what is the output of we're
02:30 : attempting to print out a bit code file
02:33 : this is in advisable as it may cause
02:37 : display problems if you really want to
02:40 : taste it I'll help you I'm bit code
02:42 : first hand you can force output with the
02:45 : F option okay let's do it man let's do
02:49 : it
02:49 : oh okay yeah it's kind of
02:54 : incomprehensible agreed but we're not
02:58 : actually going to try to display it
03:00 : because I'm gonna pipe it to the opt
03:04 : program huh and with the analyze flag
03:11 : with the view CFG flag and then it's
03:20 : printing an analysis oh wow
03:25 : why did it open up sublime text it
03:31 : created this digraph file which I think
03:35 : digraph is a program I can download I
03:39 : believe which then will take this file
03:42 : and render that visual for us I'm a
03:46 : little bit sad the saying of window will
03:50 : pop up and I should see this but a
03:52 : window did not pop up
03:58 : did it generate a file
04:08 : it did not I didn't degenerative foil it
04:13 : just unclear where it put it oh it put
04:16 : it inside this okay and it's called dot
04:22 : file and I may need a program in order
04:29 : to open a dot file how do I open a dot
04:36 : file what program do I use to open a dot
04:39 : file it's to graph this I need to graph
04:47 : this
04:48 : do I have graph of this
04:54 : a graph this might be what I want
05:01 : another way to get this is called F dot
05:04 : view C F G or F dot view CFG only where
05:08 : F is a function pointer it's by
05:11 : inserting actual calls into the code and
05:13 : recompiling or by calling these in the
05:16 : debugger OPM has many nice features for
05:19 : visualizing various graphs that's
05:21 : actually really cool and that is an
05:25 : aspect of compilers that I haven't
05:30 : really dug into that much so getting
05:32 : back to the generated code is fairly
05:34 : simple I will try to get the graph
05:40 : visualization working maybe offline and
05:45 : then when I get it working then I'll
05:48 : show it but let's keep going for now
05:50 : getting back to the generator code it is
05:53 : very simple to entry block evaluates the
05:56 : conditional expression X in our case
05:58 : here so that's the conditional
06:03 : expression and it's evaluating this it's
06:11 : comparing the double to zero because if
06:15 : you if you use just a number as the
06:18 : expression then in most languages zero
06:22 : is false E and anything that's not zero
06:25 : is truth e so that's why it's just
06:28 : comparing that number using the F comp
06:31 : instruction
06:33 : it stands for floating-point compare to
06:38 : compare I don't know why there's this
06:42 : one here what that stands for but it's
06:45 : comparing the value of x to zero and
06:50 : then it's gonna branch be R stands for
06:53 : branch it's gonna branch if the result
06:57 : of the compare was one I believe it's
07:01 : gonna branch to the den block if that
07:05 : was true T and branch it to the else
07:08 : block
07:08 : was not truthy and now it's gonna code
07:11 : to this branch or this branch and then
07:13 : after both of them finished they joined
07:16 : back to this if can't
07:18 : if continued block and then we'll have
07:22 : this five function let's read about the
07:24 : five function the five function is a big
07:27 : deal in LLVM and it's kind of weird
07:32 : because in programming school people
07:35 : don't say don't tell you if you write an
07:38 : if statement there's a five function
07:40 : no this is a construct that was
07:45 : introduced by SSA we talked about SSA in
07:50 : the previous video we'll talk about more
07:56 : excuse me
07:59 : so the Phi operation if you're not
08:04 : familiar with SSA this is Stephanie who
08:08 : go read about SSA and and in fact I have
08:12 : read about this on the Wikipedia article
08:16 : which is quite a good read about it
08:22 : excuse me apologize but um basically the
08:32 : premise of SSA again is that if you have
08:36 : multiple assignment to the same variable
08:39 : suggest this case that's actually not
08:41 : allowed in SSA form so how do you deal
08:47 : with any arbitrary program that well
08:50 : you convert a program that would do
08:52 : something like this to SSA form first
08:57 : why do we convert it to SSA form in the
09:00 : first place because when the program is
09:03 : written in SSA form it allows for a
09:07 : variety of compiler optimizations which
09:10 : might otherwise be difficult or
09:12 : impossible so that is why we convert it
09:15 : to SSA form first when you're generating
09:18 : bytecode for
09:22 : for LLVM ir it is assumed actually
09:27 : there's no you have no choice you have
09:29 : to generate that byte code in SSA form
09:32 : which is to say this code here is
09:36 : already in SSA form it you have to
09:40 : conform to the SSA form you have no
09:42 : choice if you're going to be using LLVM
09:45 : to do this and then and then from LLVM
09:49 : perspective oh wow it's already in the
09:52 : SSA form great it can do of the killer
09:55 : compiler optimizations that it's really
09:58 : good at doing so anyway so which begs
10:03 : the question if you have a program like
10:06 : your user of your program and you wrote
10:08 : a program like this and they need to
10:13 : compile it what do you do well you have
10:16 : to convert this to SSA form first how do
10:19 : you do that you basically rename for
10:25 : every single assignment you have to the
10:27 : same variable you rename it to like you
10:33 : suffix the name with a number that's how
10:36 : you rename it so we have instead of Y
10:38 : and y we have y 1 and y 2 which are
10:41 : different variables so it says you just
10:45 : converted the program to this which is
10:48 : well you can now see well in the third
10:52 : line becomes X 1 equals y 2 and it
10:57 : actually now has nothing to do with who
10:59 : I want which is an interesting property
11:01 : of this but anyway let's take a program
11:03 : they have an if statement because it
11:06 : gets more complicated when it has an if
11:08 : statement right so if you have an if
11:10 : statement that says oh if X is less than
11:13 : 3
11:14 : I mean let me actually write this out so
11:19 : this I think the code of this program
11:22 : would be something like Oh x equals y x
11:26 : equals X minus 3
11:29 : if X is less than 3 then y equals x
11:35 : times 2 and W equals y else oh this is
11:44 : not just rainbow color business ok else
11:52 : this block which does y equals X minus 3
11:56 : and then after that if the house we're
12:01 : gonna end and then we're gonna do W
12:06 : equals X minus y in Z equals x plus y so
12:14 : this is what this program is helping you
12:17 : visualize here now we're gonna rewrite
12:24 : this program now actually this might be
12:29 : easier if I wrote this in my text editor
12:31 : so let me do that
12:43 : and we close out supplying text okay so
12:52 : this example maybe I actually called it
12:59 : untitled one okay so let me write this
13:03 : out in this text editor so this is x
13:06 : equals five x equals X minus 1 is if X
13:12 : is less than 3 then Y is equal to x
13:18 : times 2 w is equal to Y else y is equal
13:25 : to X minus 3 and let's just say and more
13:31 : like Ruby and then W is equal to X minus
13:34 : y and z is equal to X plus 5 okay let's
13:40 : convert this guy to SSA form well in SSA
13:44 : form first of all we're not supposed to
13:48 : assign the same inside multiple times to
13:52 : the to the same variable so the second
13:56 : time this has to become a different
13:58 : variable from the first one so SSA form
14:03 : of this program is going to look like X
14:09 : 1 equals 5 and I'm also referring to
14:13 : this flow graph which they have the
14:16 : variable names labeled as well so you
14:19 : can refer to that one if that one helps
14:22 : you understand it so the second
14:27 : assignment to X we have to assign to X 2
14:30 : instead of X 1 and then now if X less
14:36 : than 3 this X is going to refer to X 2
14:39 : because X 2 is the last X that was a
14:43 : scientist so if X 2 is less than 3 then
14:48 : again we're going to refer to X 2 and
14:51 : then
14:51 : now this is gonna be extreme I believe
14:55 : wait oh I messed this up this should be
15:00 : why here okay never mind that
15:04 : so this would be why there's y1 and y2
15:09 : though so y1 is gonna be x 2 x 2 and
15:14 : then we have ww1 and we're gonna just
15:18 : label all the variables whether or not
15:20 : it actually needs it but I think yeah
15:23 : most of them so W 1 is gonna be Y 1 here
15:28 : and then else
15:29 : why Y 2 this time because here we
15:39 : already assigned to Y here we're
15:41 : assigning to Y again so the second time
15:43 : it has to be a different version of Y so
15:45 : Y 2 and as for X we're gonna use X 2
15:51 : that's the last X that was assigned to
15:53 : you so X 2 minus 3 that's what they have
15:57 : here as well I'm gonna end it and then
16:00 : outside of the way I messed up here -
16:04 : this should be W ok and then here it
16:09 : should be W 2 here because we already
16:13 : assigned to W W over here so the second
16:17 : assignment to W has to go to a different
16:19 : W so W 2 is equal to X 2 the last time
16:27 : we assigned your X was X 2 minus y now
16:33 : the question is which Y which why are we
16:38 : are we using for this why when we say W
16:43 : equals X minus y and that's the problem
16:47 : because in this branch we assigned to Y
16:51 : 1 but in the else branch we assigned to
16:54 : Y 2 so it could actually be either Y 1
16:57 : or Y 2 depending on which branch we took
17:02 : for the if statement
17:04 : and which is why this diagram says wide
17:08 : question mark which why and also the
17:12 : next one is Z where sine x + y - Z well
17:17 : X there's only one possibility for X
17:19 : because we didn't assign to X within the
17:23 : branching with an either branch so X has
17:26 : to be X - but why we don't know we don't
17:30 : it could either be Y 1 or Y 2 so what
17:37 : are we gonna do about it well the
17:38 : solution in in the SS a parlons is a Phi
17:47 : function we have to insert a Phi
17:51 : function which will pick either Y 1 or Y
17:56 : 2 and the way you it picks is based on
18:00 : whether you took this branch or this
18:02 : branch so Phi they use this Phi symbol I
18:07 : wonder if I can find the 5 symbol I just
18:11 : copy from here so Phi of Y 1 y 2 Phi is
18:19 : gonna pick either Y 1 or Y 2 and we'll
18:28 : just assume that fine knows whether you
18:32 : took this branch versus this branch and
18:35 : if you took this branch fire is gonna
18:37 : pick Y 1 if you took this branch fire is
18:40 : gonna pick Y 2 is it does say that in
18:45 : once the compiler actually generates
18:49 : code out of this form and produces
18:54 : assembly code or machine code this fire
18:58 : function is not actually implemented as
19:01 : a conditional statement because that
19:03 : would you know you would take a
19:05 : performance hit if it had to do that
19:07 : instead what it usually does is like
19:11 : there's actually a there's actually like
19:15 : a y3 variable Oh
19:17 : actually assigns a y3 variable first and
19:22 : then references the live 3 variable like
19:27 : that so yeah it's sort of it sort of
19:32 : does this more or less you can you can
19:40 : imagine it it's it's doing it like that
19:44 : in reality but um but when we write the
19:49 : when we write the code in SSA form this
19:52 : is what we should write and the five
19:56 : function is something that LLVM has in
20:00 : its syntax okay so and there it is so
20:06 : Phi is actually an instruction in LLVM
20:10 : ir that's the Phi so this instruction is
20:14 : saying okay I want to I want to create
20:19 : this variable called f10 and I want its
20:22 : value to be either Caulton if if we came
20:29 : from the done block which is here or I
20:33 : wanted to be caught and one in the event
20:38 : that we came from the else block okay
20:42 : and LLVM will actually verify that in
20:46 : fact it's possible for you to reach this
20:49 : point from the else block which is
20:51 : because this branching statement is the
20:54 : one that causes the else block to go to
20:57 : the if if can't block if can't standing
21:02 : for if continued right so that's how
21:06 : this stuff works
21:07 : it seems a little weird and because this
21:11 : Phi concept is sort of a construct that
21:15 : is serve comes out of nowhere it's not I
21:20 : mean it's not an instruction that your
21:23 : CPU understands Phi is not an actual CPU
21:27 : instruction is this construct
21:30 : that is in the LLVM ir language and it's
21:34 : it's part of the single the static
21:37 : single assignment form language in a
21:39 : sense and because our Mir is in SSA form
21:45 : we have this Phi instruction that we
21:49 : need to use in the in the event we are
21:51 : doing something like this with if
21:53 : statements so so yeah
22:00 : [Music]
22:11 : so let me read this paragraph so at this
22:15 : point you're probably starting to think
22:17 : oh no this means my simple and elegant
22:20 : Fran and we'll have to start generating
22:21 : SSA form in order to use LLVM
22:25 : fortunately this is not the case and we
22:28 : strongly advise not implementing an SSA
22:31 : construction algorithm in your front-end
22:34 : unless there is an amazingly good reason
22:36 : to do so in practice two sorts of values
22:40 : that float around in code written for
22:42 : your average imperative program language
22:45 : that might need fine notes there are two
22:48 : two sorts of values there's code that
22:53 : involves user variables so I guess
23:00 : something like this I don't understand
23:07 : what they mean by user variables exactly
23:09 : but anyway I think that probably just
23:12 : means some variable that you're gonna
23:14 : assign to more than once like your loop
23:17 : counter values that are implicit in the
23:21 : structure of your ast such as the final
23:25 : in this case
23:33 : okay in Chapter seven of this tutorial
23:36 : mutable variables who will talk about
23:38 : number one in that for now just believe
23:42 : me that you don't need SSA construction
23:45 : to handle this case for case two you
23:48 : have the choice of using the techniques
23:51 : that we will describe for number one or
23:55 : you can insert final directly if
23:58 : convenient in this case it's really easy
24:01 : to generate the final so so we choose to
24:08 : do it directly in this case in which
24:12 : case okay I guess in this case means in
24:20 : the case of the code we're gonna
24:23 : implement in this in this chapter
24:27 : okay alright I hope that was a good
24:32 : explanation of five to five function and
24:37 : SS a and I don't know where the next
24:43 : step is going yet but I'm gonna stop
24:46 : this episode here and then in the next
24:49 : one we'll start building the code
24:51 : generator