LLVM Tutorial #12: Optimizers

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 completed chapter 3 where we generated LLVM IR code from the AST. This time we start chapter 4 where we'll be talking about optimizers within LLVM.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : okay hey this is Toby and we're
00:02 : continuing with following along with the
00:05 : LLVM tutorial that is on LLVM dot-org
00:11 : we completed chapter three last time it
00:16 : was a lengthy chapter and I had some
00:20 : trouble in the middle I had to do some
00:22 : debugging to figure to get past some
00:25 : issues we got through that and now we're
00:27 : gonna move on to chapter four which is
00:30 : about and optimizer or support I
00:33 : really have no idea what to expect here
00:36 : Oh a little bit but not a lot I know
00:39 : what JIT is know how you would do that
00:45 : using LLVM so let's let's look at this
00:50 : so here they say welcome to chapter 4 of
00:54 : the implementing and language with our
00:56 : vm tutorial chapters 1 2 3 describe the
00:58 : implementation of a simple language and
01:01 : add a support for generating ll be Mir
01:04 : this chapter describes two new
01:07 : techniques adding optimizer support to
01:11 : your language excuse me an adding JIT
01:16 : compiler support JIT stands for
01:18 : just-in-time which means rather than
01:22 : compiling your whole program into
01:25 : machine code actually the first that
01:28 : delays that and only compile your
01:31 : program into machine code when you
01:34 : actually need to execute the code and I
01:38 : know the v8 JavaScript engine does this
01:40 : and the Java Virtual Machine as well as
01:44 : as well as the small talk environment
01:47 : and a lot of other language environments
01:51 : nowadays do JIT these additions will
01:56 : demonstrate how to get nice efficient
01:58 : code for the color that kaleidoscope
02:00 : language trivial constant folding okay
02:04 : so our demonstration for chapter 3 is
02:07 : elegant and easy to extend however it
02:09 : does not produce wonderful
02:11 : I are builder however does give us
02:14 : obvious optimizations when compiling
02:16 : simple code such as if you have
02:19 : constants you operate on constants you
02:23 : automatically know to pre calculate
02:29 : whenever both sides of the operation are
02:33 : already constants it just added the one
02:35 : in two and resolved it to a three this
02:39 : code is not a literal transcription of
02:41 : the AST built by parsing the input
02:43 : because that would have been this with
02:46 : an ADD operation in the middle constant
02:48 : folding this is called constant folding
02:51 : this automatic calculation based on
02:55 : constants in particular is a very common
02:58 : and very important optimization so much
03:01 : so that many language implement eight
03:03 : implementers implement constant folding
03:06 : support in their AST representation what
03:10 : LLVM you don't need the support in the
03:12 : AST since all calls to build a VM I are
03:16 : good through the LLVM
03:18 : ir builder the Builder itself checked to
03:21 : see if there was a constant folding
03:23 : opportunity when you call it if so it
03:26 : just does the constant fold and return
03:29 : returns the constant instead of creating
03:32 : an instruction well that was easy
03:37 : yeah nice in practice we recommend
03:41 : always using ir builder when generating
03:44 : code like this it has no synthetic
03:47 : overhead for its use you don't have to
03:50 : uglify your compiler with constant
03:52 : checks everywhere I see so like like I
03:56 : can totally see writing a builder
04:00 : yourself that just generates LLVM ir
04:04 : code in this format yourself but if you
04:10 : build it yourself then it would not
04:12 : benefit from this constant folding that
04:15 : the higher I are builded us
04:16 : automatically for you although you could
04:18 : implement it yourself though
04:22 : so although I also probably I have a
04:27 : feeling LLVM is can probably also
04:30 : optimize this code after the fact and do
04:35 : the constant folding after the fact and
04:37 : sort of do a transform of this program
04:43 : so is saying it can dynamically reduce
04:48 : dramatically reduce the amount of LLVM
04:51 : ir de is generated in some cases on the
04:55 : other hand ir builder is limited by the
04:58 : fact that it does all of its analysis in
05:00 : line with the code s it is built if you
05:04 : take a slightly more complex example
05:05 : like this one in this case left hand
05:14 : side and right hand side of the
05:15 : multiplication are the same value we'd
05:17 : really like to see this generate time
05:19 : equals x plus 3 and then result equals
05:25 : 10 times 10 instead of computing X plus
05:28 : 3 twice
05:29 : unfortunately no amount of local
05:31 : analysis will be able to detect and
05:33 : correct this this requires two
05:35 : transformations three Association of
05:38 : expressions to make the adds lexically
05:42 : identical and common sub-expression
05:44 : elimination to delete the redundant add
05:47 : instruction fortunately LLVM provides a
05:50 : broad range of optimizations that you
05:52 : can use in the form of passes excuse me
06:16 : okay so alright warning due to the
06:22 : transition to the neo pass mender
06:24 : infrastructure this tutorial is based on
06:28 : LLVM legacy function path manager which
06:32 : can be found in legacy pass manager for
06:35 : the purpose of this tutorial the above
06:37 : should be used until the past manager
06:40 : transition is complete okay
06:45 : I did get notified earlier on that we
06:50 : should be using the version of this
06:52 : tutorial
06:54 : that accompanies your version so let me
07:01 : make sure my version is oh oh yeah
07:06 : that's the same thing although it is
07:09 : just in case just in case the one that's
07:16 : public on the website is not the latest
07:19 : version for some reason so we're at
07:29 : chapter 4 there are actually 10 chapters
07:33 : holy smokes okay yep this warning is
07:44 : here so alright so whatever code we
07:49 : write here might get deprecated at some
07:51 : point so LVM provides many optimisation
07:56 : passes which do many different sorts of
07:58 : things and have different trade-offs
08:00 : unlike other system systems lbm doesn't
08:04 : hold the mistaken notion that one set of
08:06 : optimizations is right for all languages
08:09 : and for all situations our OBM allows a
08:13 : compiler and implementer to make
08:15 : complete decisions about what
08:17 : optimizations to use in which order and
08:19 : in what situation so these passes are
08:25 : basically trap
08:27 : going to take this LLVM code and
08:30 : transform it in some way to simplify it
08:35 : remove the unnecessary bits and optimize
08:39 : like look for opportunities where the
08:41 : calculation can be done in a faster way
08:44 : or maybe in a more simple or in a way
08:50 : that takes less steps because that's how
08:53 : you get programs to go faster so support
09:00 : columbium supports both whole module
09:03 : passes which looks across as large of
09:07 : body of code as they can often a whole
09:11 : file but if run at linked time this can
09:14 : be a substantial portion of the whole
09:16 : program
09:17 : it also supports and includes per
09:19 : function passes which just operate on
09:22 : one function at a time without looking
09:24 : at other functions for more information
09:26 : on passes and how they are run see how
09:28 : to write a pass document document and
09:32 : the list of LLVM passes for a
09:36 : kaleidoscope we're currently generating
09:38 : functions on the fly one at a time as
09:40 : the user types two men we aren't
09:43 : shooting for the ultimate optimization
09:46 : experience in this setting but we also
09:48 : want to catch the easy and quick stuff
09:50 : where possible as such we will choose to
09:54 : run a few per function optimizations as
09:57 : the user types the function in if we
10:01 : wanted to make a static kaleidoscope
10:03 : compiler we would use exactly the code
10:07 : we have now except that we would defer
10:10 : running the optimizer until the entire
10:12 : file has been parsed in order to get per
10:18 : function optimizations going we need to
10:21 : set up a function pass manager to hold
10:23 : and organize the LLVM optimizations that
10:26 : we want to run once we have that we can
10:30 : add a set of optimizations to run we'll
10:33 : need a new function pass manager for
10:37 : each module that we want to optimize so
10:39 : we will write a function to create an
10:41 : initial
10:41 : both the module and the past manager for
10:45 : us okay
10:47 : wow this so this is the line that
10:51 : initialized the module that we missed
10:53 : the first time around it's gonna
10:57 : initialize a function past manager like
11:00 : that and then this is I think these four
11:04 : lines are like lines that adds registers
11:11 : these specific passes and we have four
11:17 : right so the first one is called
11:19 : peephole optimizations and bit twiddling
11:24 : optimizations okay I don't know what
11:26 : that means and then the next one is
11:29 : reassociate expressions yeah all these
11:34 : look very foreign to me simplify the
11:36 : control flow graph the leading
11:39 : unreachable box etc okay I'm just gonna
11:42 : copy this it doesn't mean a lot to me
11:46 : right now okay
11:55 : yep I didn't already set these things
11:58 : once the past manager is set up we need
12:01 : to make use of it we do this by running
12:03 : it after our newly created function is
12:05 : constructed in function ast : : code gen
12:10 : but before it is returned to the client
12:12 : so let's go to this cogent code codon to
12:19 : cogent so function code gen this is not
12:24 : function this is a prototype ast we want
12:27 : the function ast cogent it's this one so
12:30 : basically he's saying we create this
12:35 : well we created this function and then
12:38 : we add this basic block onto the
12:40 : function and then work with set the
12:44 : names for the arguments and so forth
12:46 : verify the function I think it's at this
12:49 : point after verifying the function yep
12:52 : we're gonna run the optimizations let's
12:56 : go do that
12:59 : yeah what else as you can see this is
13:04 : pretty straightforward
13:05 : okay I imagine you would need to call
13:10 : this initialize module and pass manager
13:14 : function so I will do that now we don't
13:19 : need to do this line anymore because
13:21 : this line has been moved over here so
13:25 : I'm gonna do that and recompile make
13:30 : this text
13:47 : eleven errors okay
13:51 : use of undeclared I done for our D F
13:54 : p.m. so I need to declare this D F p.m.
14:02 : has a static global I will do that right
14:07 : after D model
14:20 : there
14:31 : hmm I thought I just declared it oh I
14:36 : did it wrong
14:38 : C++ requires a type specifier for all
14:42 : declarations I thought I gave oh this
14:46 : needs to be call unique pointer not make
14:49 : unique because we're not making you need
14:53 : here
15:01 : okay too few arguments to the function
15:07 : call expected to but we only have one
15:11 : shoot
15:14 : [Music]
15:18 : and no member named ad in the past
15:25 : manager it looks like we're dealing with
15:29 : not the function task manager but the
15:33 : past manager which I thought is the
15:36 : newer version and I'm using the legacy
15:39 : one right now
15:44 : okay are we using the legacy okay now
15:50 : look at the final code we want to use
15:58 : the legacy pass manager let me go ahead
16:05 : and do that I'm just gonna copy all
16:08 : these includes Oh Kyle itis go okay
16:18 : not sure how to get that exactly I'm
16:23 : gonna copy all these includes here and
16:27 : replace these with them and see if that
16:33 : will help me compile it
16:44 : we still have two fuel arguments but now
16:47 : we have less errors mmm
16:54 : run is declared in the past manager I
17:00 : thought we were using the legacy pass
17:03 : function pass manager I'm gonna try to
17:14 : compile their version of the code
17:26 : see if it still works maybe it doesn't
17:30 : work anymore
17:31 : with the new version okay well you know
17:33 : you never know stuff go I'll update all
17:36 : the time you know I'm gonna make another
17:38 : file their food poof or and build it so
17:47 : change this to their code for their food
18:04 : Oh for okay
18:08 : i me built I'll just copy this line now
18:11 : and try to build their code this way
18:14 : well we couldn't find that file so
18:17 : that's true
18:19 : [Music]
18:21 : is it possible to
18:27 : not do the JIT parts the jet beautiful
18:38 : the jet I'm gonna comment out the jet
18:45 : parts I'll figure out the later for
18:50 : now I just want to do the optimizer bits
19:06 : making the jet okay let me try this
19:24 : ah
19:26 : you still have a few places that are
19:28 : using the jet so I will an expected
19:33 : namespace name work
19:43 : I'm gonna count this out maybe Express
19:54 : the one 619 do I still have references
20:03 : to the trip
20:12 : okay remove the reference last reference
20:15 : to the jet let's see if it compiles now
20:19 : just one an error expert symbol that get
20:26 : address 615 X per symbol this is related
20:41 : to jet I think I'm gonna ignore it for
20:45 : now handle top-level expression okay he
20:52 : value 8 it to that okay
21:21 : there are some libraries we actually
21:24 : would need to link to but it cannot find
21:30 : them interesting create SFG
21:37 : simplification pass create CFG
21:48 : simplification pass so in order to get
21:51 : that we're gonna need to link to library
21:55 : that does that
22:02 : [Music]
22:18 : this is the end of the section and
22:22 : optimization actually now we move on to
22:25 : jet so I would like to get this to
22:30 : compile but I'm not published how to do
22:34 : that I think there are some libraries in
22:39 : here there are some pass libraries maybe
22:48 : I need to find the specific ones in link
23:03 : so let me see this one called create
23:17 : reassociation pass there's also one
23:22 : called initialize native target ASM
23:27 : parser this little dip LLVM ASM parser
23:36 : maybe I need to link this one we need
23:42 : the native one though let's try linking
23:48 : this one
23:58 : take you just do it
24:00 : I think maybe you just let that file in
24:05 : the command line like here it's just a
24:15 : library so I'm gonna link it clang hello
24:20 : game lip and then inside of lip I want
24:25 : to live how LVM was it he is car sir
24:39 : Volume II he assumed he is
25:00 : and if nothing else I should not see the
25:03 : error about ESM parser anymore if if we
25:08 : got that right no I still get it oh now
25:14 : it's the exact same this is the
25:23 : initialized x86 maybe I need to
25:26 : specifically reference the x86 version
25:30 : of the ASM parser so there's probably an
25:41 : easier way to set this up but maybe it's
25:50 : x86 cap-toe
25:54 : x86 yes here's him parser
26:11 : holy moly
26:16 : okay I think that did something but you
26:24 : still don't have a reference to the
26:26 : printer okay so I think what it is is
26:28 : I'm gonna probably oh my gosh probably
26:35 : need to include each of these static
26:40 : libraries one after another we need the
26:45 : x86 ASM printer x86 target I guess x86
26:51 : target info x86 target MC I'm copy these
26:58 : lines
27:11 : you
27:15 : you
27:18 : and that is a lot of a missing vtable
27:23 : usually means the first non inline
27:26 : Bertram member function has no
27:28 : definition LD symbols not found okay all
27:39 : right
27:39 : so I'm gonna try to find the x86 ASM
27:43 : printer and then 886 target I'm gonna
27:51 : copy this line down probably you know I
27:59 : put this in the build file
28:10 : I'm compiling their total right now okay
28:23 : okay so I'm gonna go find these
28:29 : libraries they start with lip LLVM and
28:45 : the one I'm milking where is x86 printer
28:59 : actually don't see you at 86 treasure
29:07 : this is a sm parser I mean isn't printer
29:23 : okay what else do I need
29:29 : here's an printer I'm gonna need a
29:32 : native target is there something here
29:37 : that's called target no yeah okay I got
29:59 : the target oops wait I wanna computer is
30:10 : freezing up on me okay actually wanna
30:13 : put it in this file this build file okay
30:20 : there's the LLVM lip LLVM target do we
30:24 : have another one target info in this
30:28 : wise okay we probably already have it
30:31 : with the target okay I'm gonna try to
30:34 : run this build file
30:52 : [Music]
30:55 : no still a lot of errors oh no it's the
31:06 : native target a SME printer the x86 ASM
31:14 : printer but does that even exist well so
31:25 : did I put the printer in you I put the
31:30 : parser I did put two parsers in here
31:34 : did I ever put the printer in here oh I
31:38 : did put this printer here is there a
31:59 : there's only one ASM printer and I have
32:05 : included it
32:17 : well we also have some stuff in climbing
32:21 : and see make but I'm not sure if that's
32:25 : what I need I did read something that's
32:37 : something like it's better if you have
32:41 : your project set up as a sibling
32:45 : directory of the LLVM project and and
32:49 : sort of set up the references over to
32:53 : the sources in the LLVM project I'm
32:57 : afraid though that kind of setup might
33:01 : need me to compile the LVN project which
33:06 : last time I was not able to do ok I'm
33:37 : gonna cut this video short and try to
33:40 : think of some ideas of this hurdle of
33:44 : compiling this stuff yeah I figured