LLVM Tutorial #7: What is SSA?

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. In the last part, I struggled to compile the parser code. This time I got the fix and I start chapter 3 with a short explanation of SSA (Static Single Assignment Form).

Transcript

The following transcript was automatically generated by an algorithm.

00:01 : hello there uh top of the morning to ya
00:03 : actually it's pretty late it's 1104.
00:07 : um we're going to continue our
00:09 : walkthrough of the llvm tutorial
00:12 : um we're in the uh
00:15 : we're at the end of uh chapter two
00:20 : last time we were going to finish but we
00:21 : ran up against some compiler problems
00:24 : compilation errors i should say and um
00:28 : and i wasn't able to get to the finish
00:31 : line but um i did a little bit of
00:32 : research
00:34 : uh offline and i figured out how to move
00:37 : forward
00:38 : so i'll share that with you so last time
00:40 : when i was trying to compile the program
00:42 : um uh i think
00:47 : i was doing it like let's see
00:51 : first i was compiling it just like this
00:54 : even without these flags so i was
00:56 : compiling it like
00:58 : gc g plus plus my
01:01 : lang dot cc
01:04 : and then output uh mylang.bin
01:09 : and when i did that i ran up against a
01:12 : lot of compiler errors
01:13 : uh when i when i followed the tutorial
01:16 : suggestion to
01:17 : use these llvm config to generate the
01:20 : flags
01:22 : then that got a lot better
01:29 : actually at this point everything is
01:31 : fixed
01:32 : so those flags are kind of important
01:36 : we can look through those flags to see
01:38 : what they actually did
01:40 : but anyway um now i actually i still had
01:44 : an
01:44 : error which was caused by
01:48 : me forgetting to use the standard move
01:50 : function
01:51 : to move this argument uh
01:55 : so sort of grant the ownership of this
01:57 : argument to this
01:59 : vector i believe so previously i had the
02:01 : code like this
02:04 : i think and and i got this error which i
02:07 : actually
02:08 : showed this in the previous video where
02:10 : it i only had one
02:12 : single error left and i was reading
02:15 : through this
02:16 : ginormous error and i got confused
02:20 : uh and then i try to compile
02:23 : their code as this from from the
02:25 : tutorial because at the end of the
02:27 : part two they actually have a full
02:29 : listing
02:30 : of the code actually this is their code
02:33 : from part three
02:35 : i later on wanted to test part three
02:38 : test compiling
02:39 : their code from part three just make
02:40 : sure we wouldn't run into a hurdle
02:43 : like we did last time anyway but i tried
02:46 : to compile their code from part two
02:47 : and i still had trouble uh
02:51 : but eventually i figured that out as
02:53 : well but anyway i'm gonna stick with my
02:55 : version of the code
02:56 : um and the only thing that was needed to
02:59 : fix this error was to add in this move
03:03 : um
03:05 : to make sure yeah that the surf
03:07 : ownership of this
03:08 : art was granted to the vector that
03:11 : contained it
03:13 : and now this compiles and that is pretty
03:16 : important
03:18 : and and after the thing compiles uh what
03:21 : you get is a program that is sort of
03:24 : like a repo
03:25 : it is a like a for javascript
03:29 : that is like the developer console
03:33 : you can type in code with within this
03:36 : language
03:37 : uh for example and you have to end the
03:39 : line with
03:40 : a semicolon that's how it works so like
03:43 : one plus one
03:44 : and it says i parse a top level expert
03:46 : uh if you want to define a function
03:50 : function kind of looks like this maybe
03:52 : like i don't know
03:53 : fip of n
03:57 : is fib of n
04:00 : minus one plus fib of
04:04 : n minus two uh semicolon and it actually
04:08 : was successful
04:09 : in parsing a function definition uh if i
04:12 : had a syntax error in there
04:14 : somewhere i don't know i had too many
04:17 : parentheses or something
04:19 : i'll just do n plus one then
04:23 : i get a parse error okay so this this
04:26 : all makes sense uh let's try
04:28 : an extern
04:32 : do we have do we support variable
04:35 : assignments like that
04:37 : a known token when expecting an
04:40 : expression
04:41 : i don't actually think we support
04:43 : variable assignments at this moment but
04:45 : we do support uh
04:46 : function definitions uh and numbers
04:50 : like that okay
04:55 : does that work okay so anyway uh we have
04:58 : this
04:58 : parser working from uh
05:01 : part two and that is great uh
05:05 : uh before we move on to uh uh
05:08 : chapter three uh let's look a little bit
05:11 : at
05:11 : what these flags coming from the llvm
05:14 : config
05:15 : is um i wanna check my audio
05:20 : make sure hello can you hear me yeah i
05:23 : think
05:24 : the audio is good okay he's using my
05:27 : yeti mic because one time i
05:28 : recorded this thing and i had my
05:31 : microphone set wrong
05:32 : and then the whole video had no audio in
05:35 : it
05:35 : and i didn't want that to happen again
05:38 : okay
05:40 : so uh why don't we just copy this line
05:44 : out
05:45 : this line that says llvm config with the
05:48 : c xx flags and execute
05:52 : them on their own so llvm
05:56 : config cxx flags
05:59 : and you'll see these flags for the g
06:02 : plus plus
06:03 : compiler um
06:06 : i actually think i have g plus plus
06:09 : alias to clang plus plus
06:13 : um so it's probably
06:17 : in reality using clang this i
06:20 : flag is saying add the include file
06:24 : add the header files within this include
06:27 : directory
06:28 : to the list of header files to to use
06:31 : uh this is saying use the c plus c plus
06:35 : plus 14
06:36 : standard which probably comes with a
06:38 : bunch of
06:39 : um syntax
06:42 : features that the code within the
06:45 : tutorial uses
06:47 : i actually don't think at this point
06:49 : we're using any of the includes
06:51 : from this directory so it's more likely
06:54 : that
06:55 : there's a bunch of these things here
06:59 : std constant macros and std format
07:03 : macros i don't actually know what those
07:05 : things
07:06 : are
07:09 : maybe there are stuff that's defined in
07:12 : this include directory i don't actually
07:14 : know
07:14 : but in any case these are
07:17 : and this is no exceptions
07:20 : i guess we want to turn off exceptions
07:23 : from c
07:24 : plus or something i don't know what all
07:26 : these flags are
07:27 : i just wanted to show you that there's
07:29 : some special flags that
07:31 : llvm has configured for projects using
07:34 : it
07:35 : even though at this point we have
07:37 : written a
07:38 : parser that doesn't actually depend on
07:40 : llvm
07:41 : just yet but we will um so
07:45 : last time i talked about this but i want
07:46 : to say again uh which is that
07:48 : um in the getting started
07:53 : guide for llvm which is in a different
07:56 : part of the
07:57 : let me go go there
08:01 : and i did their getting started guide a
08:04 : long time ago
08:07 : the getting started with the llvm system
08:09 : i followed this tutorial
08:11 : and what they recommend the way they
08:14 : recommend you get started is clone their
08:16 : repository
08:17 : and then go in there and build llvm from
08:20 : source
08:21 : when i tried it last week i had
08:25 : lots of problem with that it was running
08:27 : this compile drop and it seemed
08:29 : never to end so finally i gave up
08:34 : um and maybe if anybody is watching that
08:37 : knows how to compile llvm correctly
08:40 : or more efficiently please let me know
08:43 : because i would like to do this
08:45 : anyway i punted and instead of
08:48 : trying to build llvm from scratch i i
08:51 : downloaded the binary instead
08:54 : so i went to llvm home and i went
08:58 : to this available for download link
09:01 : and i downloaded a binary i went for the
09:04 : latest version which is from march
09:06 : 24th and then i
09:09 : said download and i grabbed the
09:12 : pre-built binary
09:14 : for mac os which is the operating system
09:17 : and as you can see
09:18 : llvm supports all these different types
09:20 : of architectures
09:23 : and that's all various combinations of
09:26 : operating system versus cpu architecture
09:30 : and
09:31 : that is pretty cool so that's
09:34 : that's how i have llvm installed and
09:37 : once i extracted
09:39 : the compressed file that was in this
09:42 : download
09:43 : i then extracted it and put it
09:46 : in a sub directory inside my home
09:49 : directory i called it
09:51 : lang dash llvm because that's what
09:54 : that's the contents within it it
09:57 : contains llvm core
09:58 : as well as clang which is the c compiler
10:02 : and then within this subdirectory
10:05 : there's bin
10:06 : which contains the ll compiler
10:09 : uh as well as other uh
10:12 : tools from the from the llvm suite
10:16 : yeah let's display so all these tools
10:19 : are coming from the llvm suite
10:22 : that i can use from the command line and
10:25 : i added
10:26 : this to my path in my startup login file
10:32 : and as you can see there's also lib in
10:35 : the include directory contains
10:37 : various headers and then
10:40 : the lib directory contains various
10:42 : pre-built
10:44 : binaries for for various parts of the
10:46 : library
10:47 : okay so this is how i got it set up you
10:50 : can set it up the same way or you could
10:53 : maybe try your hand at compiling llvm
10:55 : yourself
10:57 : anyway we're gonna move on to um
11:00 : part three or i should say chapter three
11:05 : which is quite exciting for me because
11:07 : um
11:08 : that's actually a new area for me now uh
11:11 : that's
11:12 : uh yeah so let's get into it
11:15 : we have built a parser which is able to
11:18 : take some source code and generate an
11:21 : ast
11:22 : tree the next step
11:26 : is to write some code that
11:29 : traverses the ast uh
11:32 : the abstract syntax tree uh
11:35 : and and generates code in the
11:39 : llvmir format so we're gonna generate
11:43 : some
11:43 : llvm ir code
11:46 : but we're gonna generate this code with
11:49 : the help
11:50 : of a library a builder library that is
11:53 : provided
11:54 : for us by llvm
11:58 : which will make this process easier
12:04 : i don't know exactly how much easier and
12:06 : also
12:07 : i have taken their code from the end of
12:11 : chapter three and compiled it
12:13 : to verify that i i know how to compile
12:15 : it so
12:16 : uh we hopefully we won't run into the
12:19 : same hurdle we
12:20 : ran into last time uh yeah so uh i
12:23 : answer also i
12:24 : uh oh i created this build file
12:28 : um which will compile the
12:31 : both my code and their code oh i also
12:34 : i found that i when i tried to build the
12:39 : code
12:40 : the prescribed way i got this weird
12:43 : error that says
12:44 : like it's a ld which is the loader it's
12:48 : an ld error that's a it didn't
12:49 : understand one of the option that was
12:51 : supplied
12:52 : to it and that was because the loader
12:54 : that i have
12:55 : on my computer is older than
12:59 : the one that the llvm used to compile
13:02 : itself
13:03 : and if you have that situation what you
13:06 : do
13:07 : is you tell clang the
13:10 : version of your linker using this flag
13:14 : which is what i did i figured out the
13:16 : version of my loader
13:18 : by doing ld with a version flag
13:22 : it tells me the version of my loader and
13:24 : then i just informed
13:26 : the clang plus plus compiler hey my
13:29 : linker's version is
13:31 : that so don't try to give it anything
13:33 : that it doesn't understand
13:34 : so anyway i got this build script i
13:36 : probably use it to do stuff
13:39 : but i'm going to comment out this line
13:42 : and probably will use it later
13:43 : so now i'm going to start out on chapter
13:46 : 3.
13:48 : let's see how far we got um okay i'm
13:50 : going to
13:51 : do it slower because this is a new area
13:53 : for me and that
13:54 : also there's going to be a lot of stuff
13:57 : to cover
13:59 : so welcome to chapter three of
14:01 : implementing a language with llvm
14:03 : tutorial
14:04 : uh we have already uh this chapter will
14:07 : show you how to transform these
14:09 : abstract syntax tree which we built in
14:11 : chapter two into
14:12 : a llvm ir this will teach you a little
14:16 : bit about how
14:16 : llvm does things as well as demonstrate
14:19 : how easy it is to use
14:21 : it's much more work to build a lecture
14:23 : and parser than it is to generate llvm
14:26 : ir code
14:27 : smiley face that's actually um
14:32 : a little bit hard to believe
14:35 : at this point in my knowledge knowledge
14:38 : level
14:39 : but um that's also good to hear from
14:42 : someone
14:45 : please note this the code in this
14:46 : chapter and later requires
14:49 : llvm 3.7 or later well i did download
14:53 : the latest one
14:55 : um i actually downloaded
15:01 : version 10.0.0 that's the one i
15:07 : downloaded
15:08 : which is way later than 3.7
15:12 : holy crap how old is this tutorial
15:16 : i'm really happy that it still works
15:17 : even though the tutorial is like
15:20 : seven versions behind um
15:23 : also well it works so far we'll see
15:27 : also note that you need to use a version
15:30 : of this tutorial that matches your llvm
15:32 : release if you're using
15:34 : an official llvm release use the version
15:37 : of the documentation
15:39 : included with your release or on the
15:43 : llvm.org releases page
15:47 : oh really okay
15:50 : are you saying you have multiple
15:52 : versions of this tutorial
15:54 : but this is like the like master version
15:57 : of the tutorial isn't it um
16:00 : is there like oh
16:04 : documentation okay
16:10 : oh i should put like this flag in front
16:16 : of here is that what you're saying
16:21 : no that doesn't work
16:24 : okay uh
16:28 : intro to getting started
16:31 : let me try that table of contents
16:34 : we're within the 10.10
16:39 : okay so you're saying i should use this
16:41 : version of the tutorial
16:43 : with a 10.00 in front of it but it's
16:46 : still going to say
16:47 : [Music]
16:49 : requires 3.7 or later uh which
16:52 : is fine um okay so i should be using
16:56 : this version of the tutorial i have a
16:58 : feeling though the
16:59 : master version is probably the
17:03 : probably the um current
17:06 : with the latest version of it i'm gonna
17:09 : stick with
17:10 : this master version that's on the
17:12 : website
17:13 : and uh yeah okay so in order to generate
17:17 : llvmir
17:18 : we want some simple setup to get started
17:22 : first we define virtual code generation
17:26 : cogen methods in each ast class so
17:29 : remember
17:30 : how initially when we created
17:33 : this expert ast class this one
17:37 : we had ah come on computer is kind of
17:41 : like sluggish on me we had this
17:44 : virtual uh expert ast
17:48 : destructor but now we're going to add
17:50 : another virtual
17:53 : method on it actually
17:56 : not crazy about doing it this way but
18:00 : again
18:00 : the tutorial did say this is not
18:02 : necessarily the best practice
18:05 : way of doing this so you know
18:08 : i'm taking it with a grain of thought
18:10 : but salt but i'm gonna follow along
18:13 : so we're going to add a virtual method
18:15 : to the base class
18:17 : which requires every subclass to also
18:20 : implement
18:21 : this method this what the heck is this
18:24 : equal
18:25 : 0 by the way that's that's a
18:28 : very specific c plus plus syntax
18:32 : actually that is saying this virtual
18:36 : method uh has no
18:40 : implementation is is not
18:44 : implemented and also
18:48 : it's required that a subclass must
18:51 : implement this this equal zero is how
18:55 : you specify
18:56 : that i find that really weird that's how
18:59 : they designed it in the c
19:00 : plus let's just go with it and not
19:03 : criticize
19:05 : now so given that every subclass
19:10 : including number expert ast variable
19:12 : expert asp etc
19:14 : has to implement like give a real
19:16 : implementation of this method
19:17 : with this value thing we might need to
19:20 : import a header in order to get
19:22 : what value is i think um
19:26 : yeah value is the class
19:30 : used to represent a static single
19:33 : assignment
19:34 : ssa register or a ssa
19:38 : value in llvm i think i'll have to talk
19:41 : about ssa
19:43 : uh shortly um
19:47 : let's go ahead and do that actually and
19:50 : perhaps
19:50 : uh i'll do that i'll talk about ssa
19:53 : and then i'll
19:57 : cut this video short and then we'll
20:00 : continue in the next one
20:01 : okay what what the heck is ssa honestly
20:04 : i
20:05 : am not very knowledgeable about it but
20:07 : what i do know
20:08 : based on reading this wikipedia page
20:11 : um oh i would say that first of all
20:15 : the design of ssa is very very
20:18 : central to the design of llvm
20:21 : um all of llvm
20:25 : there's a lot of architecture within
20:28 : llvm
20:28 : that is based on ssa
20:32 : which is stands for single static single
20:35 : assignment
20:35 : form um and the reason
20:40 : the reason a static single assignment
20:44 : form
20:45 : is desirable and the reason why
20:48 : probably the reason why llvm chose it
20:52 : is because if you have your
20:55 : program written in ssa form
20:59 : it makes possible a bunch of code
21:03 : optimizations which are listed here so
21:06 : constant propagation value range
21:08 : propagation
21:10 : spars conditional constant propagation
21:13 : dead code elimination global value
21:16 : numbering
21:17 : register allocation that's a
21:19 : particularly interesting one for me
21:22 : i don't understand what every one of
21:25 : these are
21:27 : but i guess a
21:30 : a way to summarize it is to say um
21:34 : ssa form is a valuable thing to have
21:39 : because if you you have your program in
21:43 : this form
21:44 : then you can benefit from all of these
21:46 : types of compiler optimizations
21:49 : which are these all of these compiler
21:52 : optimization
21:53 : are well known and well researched and
21:56 : there are good implementations
21:58 : for them good algorithms for them
22:01 : um so which is all to say that
22:04 : that helps your code get faster at the
22:07 : end
22:08 : um so so that's why llvm has chose to
22:12 : center its architecture around ssa
22:15 : what the heck is ssa ssa is saying
22:18 : uh you know what everything it's it's
22:21 : it's a
22:23 : sort of like a rule if if you want to
22:26 : if you have an arbitrary piece of
22:28 : program such as
22:30 : like this one you have this program well
22:33 : that's not
22:34 : in ssa form uh because
22:37 : um ss in order for a program to be in
22:41 : valid ssa form um
22:45 : it requires that every single variable
22:48 : you have in the program can only be
22:50 : assigned
22:51 : to one time so
22:54 : every var
22:58 : can only be
23:02 : assigned
23:06 : once once
23:11 : exclamation point um and therefore
23:15 : it if you wanted to translate this
23:17 : program into
23:19 : sync static single assignment form it
23:22 : should look like this
23:23 : we instead of assigning to y
23:26 : two separate times we actually are gonna
23:29 : need to
23:29 : name a new y call it y two we have
23:32 : y one and y two
23:36 : and then and then
23:40 : we only have one x so that's x 1. so
23:43 : this
23:44 : this program in ssa form
23:47 : is converted to this now why is this
23:50 : valuable
23:52 : well there's some algorithms for
23:55 : figuring out that code right
23:57 : clearly clearly this first line is
24:00 : completely useless
24:02 : because the second line is going to
24:04 : override whatever it does
24:06 : so the first line is like that code we
24:09 : should optimize that away
24:11 : that should just go away we that doesn't
24:14 : need to
24:15 : go into the code at all so an optimizer
24:19 : can come along sort of go through the
24:22 : ast
24:23 : that represents this code and realize
24:25 : that that line of code is completely
24:27 : unnecessary
24:28 : we're going to strip it away from the
24:30 : final resulting program
24:32 : um that kind of algorithm is harder to
24:34 : do when the program is in this form
24:36 : but if you convert it to ssa form that
24:39 : kind of analysis
24:40 : is much more easy and efficient to do
24:45 : uh that kind of analysis it uh includes
24:49 : all of these things all like that code
24:51 : elimination is one of them but all of
24:52 : these things
24:54 : are algorithms that are easier and more
24:57 : efficient if the input is already in
25:00 : this
25:01 : ssa form so that is in a nutshell
25:05 : at a high level what ssa is
25:08 : and all of the code that we generate in
25:12 : in llvm llvmir will be in ssa form
25:16 : and we're gonna see that uh so with that
25:19 : i'm gonna
25:20 : i'm gonna uh stop this video at this
25:23 : point and then in the next
25:25 : video we'll actually start implementing
25:28 : some of the code in chapter 3.