LLVM Tutorial #14: JIT

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 got LLVM optimizers working. This time we make a "JIT". What is a JIT? Watch and find out.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello there this is Toby we're gonna
00:02 : continue this series where we walk
00:05 : through the LLVM tutorial from LLVM org
00:10 : so we're in the middle of chapter four
00:13 : and we're about to add a JIT compiler
00:17 : what the heck is a JIT compiler Welch it
00:20 : stands for just-in-time it means when
00:23 : you write a program when you write a
00:28 : program some somebody wrote a program
00:32 : well as you know if you've seen my
00:36 : previous videos explaining the
00:38 : architecture you you're gonna parse the
00:40 : code and then you're going to generate
00:44 : some good some generate some machine
00:47 : code I kind of merged two boxes into one
00:52 : here you need some machine code beef and
00:57 : then send that machine code to your cpu
01:03 : is basically saying well I'm gonna
01:07 : do this step on the fly as as needed as
01:12 : needed basis and I'm gonna have this
01:15 : program that is actually in interpreting
01:19 : your code this program and in particular
01:23 : because it makes sense for this toy
01:25 : language because this toy language is
01:28 : running within this repo loop where you
01:33 : type some code into it that you type a
01:36 : little bit of code into it it it's gonna
01:39 : let compile it compile it and it's gonna
01:44 : generate some machine code or at this
01:47 : point not yet but at this point it's
01:49 : gonna generate some so-called IR code
01:53 : but this I argued then if we want to
01:56 : actually execute the program we have to
02:00 : go through this generate process
02:05 : to give it that looks horrible it goes
02:11 : this IR has to go to a box to convert it
02:15 : into a machine code which can then be
02:18 : fed into the CPU and this process here
02:23 : we're gonna do this just in time just in
02:30 : time as as needed
02:32 : okay that's what is Matt instead of
02:35 : ahead of time ahead of time is you give
02:37 : me the entire program I'm gonna convert
02:41 : all of it to machine code and then
02:43 : execute it just in time music you know
02:45 : you have this program fine you just
02:49 : typed it in or it's maybe it's even on
02:53 : disk I'm not gonna compile it until I'm
02:56 : planning to execute it when I want to
02:58 : execute it
02:59 : I will compile it into machine code and
03:01 : then we'll and then I'll execute it
03:03 : right away so that's what just-in-time
03:05 : is and apparently OPM has support for
03:10 : that that sounds awesome
03:12 : so in this section we will add JIT
03:17 : compiler support to our interpreter the
03:19 : basic idea is that we want kaleidoscope
03:21 : to have the user enter function bodies
03:24 : as they do now but immediately evaluate
03:27 : top-level expressions that they type in
03:29 : for example if they type in one plus two
03:33 : we should evaluate it and print out
03:34 : three if they define a function they
03:37 : should be able to call it from the
03:38 : command line in order to do this we
03:41 : first prepare the environment to create
03:43 : code for the current native func
03:46 : argot and declared the in and
03:49 : initialized the jet I love it that they
03:53 : called it the jet this is the jet this
03:59 : is done by calling some initialized
04:02 : native target functions and adding a
04:04 : global variable the jet and initializing
04:08 : it in main
04:12 : okay so alright there's a lot of
04:17 : mysterious stuff going on I guess
04:20 : this code was already there in their
04:23 : example although I didn't choose to use
04:24 : this president's map here so I just need
04:28 : to add these three lines I believe and
04:33 : also this line and also this line to
04:36 : initialize this static global variable
04:41 : called digit this is this header file
04:47 : called a kaleidoscope jet we'll get to
04:50 : that later but you will need it if
04:52 : you're following along I have the module
04:58 : the fpm and the jet and now I need to
05:06 : add these three initialize function
05:09 : calls to the top of the main function I
05:15 : not sure whether it should go if before
05:18 : my other initialize function or after
05:21 : I'll do it before and then I need to
05:26 : initialize the jet before I start the
05:30 : main loop okay yeah I have done it I
05:34 : guess I'll delete this test code that I
05:37 : wrote for debugging the problem earlier
05:40 : on alright now we also need to set up
05:44 : data layout for the jet so I'll go into
05:50 : this initialize module and pass manager
05:54 : function which is right here you need to
05:57 : add this line to say set the data layout
06:04 : I don't know what that means
06:08 : okay
06:12 : and then we need to create a I guess we
06:17 : already have this line that's so this oh
06:21 : by the way I think I cover this in the
06:32 : last video but this actually needs to be
06:35 : legacy : function past manager instead
06:40 : of function past manager so this is a
06:44 : mistake
06:44 : in the tutorial but but their final code
06:48 : listing if you just skip instead of
06:52 : using these code snippets you go to the
06:54 : final code listing that code actually
06:57 : works so if all fails just fall back to
07:00 : the final code listing at the bottom of
07:02 : this chapter the Kaleidoscope JIT class
07:08 : is a simple jet built specifically for
07:12 : these tutorials it's available inside
07:14 : the LLVM source code so this file I have
07:18 : dug it out of the LLVM source code and
07:21 : I've copied it and and put it in my
07:25 : project the way you get hold of it is to
07:31 : just go to the source code page for LLVM
07:35 : I think they have a github pretty sure
07:40 : that they do yes it's actually a mirror
07:45 : of code in another repository I believe
07:56 : and if you cook you can clone this
07:59 : entire directory there's a lot of stuff
08:02 : in there but if you don't a clone it I
08:05 : believe you can go into the examples
08:08 : directory may be within LLVM yeah yes
08:14 : so LLVM project / le m / examples /
08:20 : kaleidoscope include that's where a
08:26 : kaleidoscope that HS and you can go here
08:32 : and you can get this file what's the
08:37 : best way to get this file you can click
08:38 : on raw and then just copy this content
08:44 : from your web browser and paste it into
08:46 : a file with that same name although if
08:50 : you call it a different name it's not a
08:51 : problem as long as you reference the
08:55 : name that you have for it so I think
09:00 : that means I need to include that and
09:03 : I'll do it in the top so reference
09:07 : kaleidos kaleidoscope with a cake okay
09:13 : so I include this header file here which
09:17 : I have copied into my own project and
09:23 : let's go back to the chapter so in later
09:27 : chapters
09:28 : so one thing obviously one question I
09:31 : have at this point is like if you look
09:33 : at this source code for this so-called
09:37 : kaleidoscope jet actually that's this
09:41 : code is you know there's 130 some lines
09:46 : I mean it's not a ton but is still you
09:51 : know you're gonna throw this much code
09:53 : at me without explanation so I will
09:59 : probably want to go in this code and
10:02 : figure out what is doing
10:05 : but let's get through this chapter first
10:07 : before we do that so in later chapters
10:12 : we will look at how it works
10:14 : oh okay in later chapters no that's fine
10:19 : great thanks and we'll extend it with
10:23 : new features but for now we will take it
10:25 : as given its API is very simple add
10:28 : module at a LLVM I our module to the jet
10:32 : making its functions available for
10:35 : execution remove module removes a module
10:38 : freeing any memory associated with that
10:41 : code and fine symbol allows us to look
10:44 : up pointers to the compiled code you can
10:48 : take this simple API and change our code
10:50 : that parses the top-level expression to
10:54 : look like this okay let's go to the
10:57 : handle top-level expression function
11:03 : alright so right now it is relatively
11:09 : simple we're gonna add a whole bunch of
11:11 : stuff into it it looks like first we're
11:15 : gonna use the jet to get the module
11:18 : let me type this in by hand because I
11:22 : want to internalize this better are we
11:26 : still gonna print out that we read a
11:31 : top-level expression I guess no I'll
11:35 : leave it in there
11:44 : okay so I'll say Auto H equals the
12:02 : standard module okay so this is saying
12:10 : we're gonna oh we're actually going to
12:14 : move the ownership of the module to the
12:18 : jet so the jet is responsible for the
12:22 : motor
12:22 : interesting I'm going to initialize
12:28 : module and pass manager I think that
12:34 : means for every single expression
12:37 : we're in reinitializing the module and
12:41 : the past manager interesting get the
12:51 : module containing the anonymous
12:53 : expression keeping a handle so we can
12:58 : free it later
13:06 : okay then we're gonna search the jet for
13:10 : the a non-expert symbol do we even have
13:20 : this underscore underscore unknown
13:35 : expert and then we're gonna assert
13:40 : expert symbol okay
13:54 : whoa
13:59 : so the symbols address and get the
14:03 : symbols address and cast it to the right
14:05 : type I guess the right what even is that
14:12 : takes no arguments returns a double so
14:16 : we can call it as a native function Oh
14:21 : so it's saying whatever that address is
14:25 : it's pointing to a function that's gonna
14:28 : return a double wow
14:56 : okay so that's interesting so int
15:01 : pointer T the problem he just means well
15:07 : whatever the address gives you it's
15:09 : really just a number which represents
15:12 : the address to some member location and
15:14 : we're gonna interpret that as a pointer
15:16 : to a function that's gonna return a
15:20 : double so then we're able to call this
15:23 : function now using that I see and then
15:35 : calling this function will actually
15:37 : evaluate the code that seems very cool
15:43 : and then we're gonna delete the module
15:48 : the JIT remove module H oh we're gonna
15:53 : create a module just to execute this
15:56 : code and then we're gonna remove it this
15:58 : is a temporary a transient module this
16:04 : is compiled now and we'll try compiling
16:07 : this
16:14 : okay let me try building this program
16:36 : does not built a nun type name
16:41 : kaleidoscope I did include this
17:06 : header file that's the thing that I did
17:10 : do it did reference distil they spelled
17:18 : it wrong
17:19 : I might have spelt
17:39 : right I guess I didn't mean that
17:44 : maybe oh because we define oh I see I
17:50 : says it's a namespace thing so I want to
17:55 : use the namespace Oh RC because LLVM or
18:03 : C is where this class was defined
18:26 : an expected : that you mean double : I
18:31 : probably meant double : I am not that
18:36 : good at that probably needs to be a
18:42 : double : thanks for giving me that
18:49 : suggestion huh is that claim plus plus
18:54 : giving me dead suggestions use of
18:56 : undeclared identifier initialized module
19:02 : and past manager so I guess I need to
19:06 : forward declare that Sakura let's do
19:15 : that where do i forward declare these
19:18 : things just gonna do it near the top
19:24 : like here
19:47 : okay one more error so this is saying
19:52 : cannot convert expected LLVM jet target
20:00 : address aka expected unsigned long long
20:10 : to int pointer T aka long without a
20:17 : conversion operator I didn't get this
20:32 : while compiling their version of the
20:36 : code maybe I should look at their
20:39 : version
20:45 : by the way yeah in general so for you or
20:50 : anyone else who are you know in the
20:54 : business of building software you're
20:56 : having to learn new things all the time
20:59 : and you're gonna try to work through
21:03 : some tutorials some learning material
21:07 : and get stuck there's no avoiding that
21:12 : and this is why a troubleshooting skills
21:15 : is so important so the book sandwich
21:20 : technique is a really really useful
21:22 : technique for getting you out of this
21:25 : kind of situation and yeah if you're
21:30 : interested in learning more about that
21:34 : again go to debug school com4 for some
21:39 : of the videos that I made about
21:42 : debugging hopefully I would like to help
21:46 : you improve your debugging skills in the
21:50 : long in the long run okay anyway I'm so
21:53 : what I'm gonna do right now is try to
21:56 : maybe do a comparison between my could
21:59 : versus their tooth in the place where I
22:03 : have this thing here this expert symbol
22:09 : thing for me it looks like this I'm
22:13 : going to look at their code what it
22:15 : looks like over here they this thing
22:19 : called can't fail I don't have that
22:30 : really what does can't fail can't fail
22:41 : is a function
22:42 : they clearly they added this just to get
22:45 : around this compiler error I think so
22:50 : I'm gonna have to slap a can't fail on
22:52 : mine this is hilarious it's like oh
22:56 : shoot compile error what do I do
23:00 : I'll just make a workaround to to shut
23:05 : up the compiler that's what I do how
23:08 : cool it can't fail so that it can't fail
23:30 : I think that what segmentation fault
23:38 : okay I wonder I should read on a little
23:43 : more before trying this or no I think
23:47 : this is it actually no I might need to
23:51 : debug the segmentation fault okay if
23:55 : parsing let me just read this paragraph
23:58 : and then I'm gonna decide whether I
24:00 : should go into the debugging session or
24:03 : leave it leave that to the next episode
24:07 : okay so if parsing and Cochin succeeded
24:11 : the next step is to add the module
24:16 : where's the oh yeah that step continued
24:21 : in table level expression to the jet we
24:23 : do this by calling out module which
24:25 : triggers code generation for all the
24:28 : functions in the module oh I see code
24:31 : generation that what they mean is it
24:34 : actually generates the machine code
24:36 : that's what that means it returns a
24:39 : handle that can be used to remove the
24:42 : module from the JIT later once the
24:45 : module has been added to the jet it can
24:48 : no longer be modified so we also open a
24:51 : new module to hold subsequent code by
25:00 : calling initialized module and past
25:06 : manager so
25:13 : so I guess you're doing that too I don't
25:22 : really understand why this this these
25:26 : two sentences
25:27 : once the murderer that that has been
25:29 : added to the jet it can no longer be
25:31 : modified so I guess it's because we want
25:37 : that add this added module to be
25:40 : temporary this h module we wanted to be
25:43 : temporary but once we add it there's no
25:46 : way to remove it so in order to have the
25:50 : temporariness we kind of have to
25:52 : reinitialize the global module which
25:56 : kind of deletes everything from it
25:58 : doesn't it once we've added the module
26:01 : to the jet we need to get a pointer to
26:04 : the final generated code we do this by
26:08 : calling the Jets find symbol method
26:15 : excuse me and finding the name of the
26:18 : top-level expression function which is
26:21 : underscore underscore a non underscore
26:24 : is since we just added this function we
26:27 : assert the defined module returned a
26:31 : result next we get the in memory address
26:34 : of the Anan expression function by
26:36 : calling get address on the symbol recall
26:38 : that we compiled top-level expressions
26:41 : into a self-contained LLVM function that
26:44 : takes no arguments and returns the
26:46 : computed double because the LLVM JIT
26:52 : compiler matches the native platform
26:54 : ABI this means that you can just cast
26:58 : the result pointer to a function pointer
27:02 : of that type and code directly let me
27:07 : try to process that sentence because the
27:11 : LLVM Jacob and Matt is the native
27:14 : platform ABI what is the native platform
27:20 : I don't really know okay I have to
27:25 : research that later but because of that
27:27 : you can just call that function directly
27:30 : this means there's no difference between
27:32 : JIT compiled code and native machine
27:34 : code that is statically linked into your
27:37 : application and that is pretty rad
27:40 : finally which means it will be fast that
27:43 : that's really what they're trying to get
27:45 : at it's like it's fast it's fast
27:48 : trust me it's fast finally since we
27:52 : don't support evaluation of top-level
27:55 : expressions we remove the module from
27:59 : the jet when we're done to free D
28:04 : associated memory recall however that
28:06 : the model we created a few lines earlier
28:08 : via initialize module and pass manager
28:12 : is still open and waiting for a new code
28:17 : to be added with just these two changes
28:21 : let's see how kaleidoscope works now it
28:26 : evaluates to nine well basically looks
28:28 : like it's basically working mine is not
28:31 : working though so I'm thinking should I
28:36 : should I try to debug this or sure I'm
28:43 : gonna try a little bit to debug this
28:45 : actually we got a segmentation fault
28:57 : I guess there's a few ways to debug this
29:01 : one is I can again look at theirs and
29:04 : see how there is different from mine
29:07 : another idea is I can do a step debugger
29:10 : line by line I figure out at which step
29:14 : did things crapped out but it looks like
29:18 : it just initially it already crapped out
29:23 : and it could be that maybe we shouldn't
29:28 : call yeah they took this initialized
29:36 : module and passed manager away from the
29:39 : main function so maybe I should do that
29:43 : will that prevent it from seek folding
29:47 : probably now the compile time is quite
29:54 : long one pain point I feel like of
30:04 : developing code in C++ is the compile
30:08 : time and that's a sentiment I get that I
30:12 : like like I felt from C++ developers and
30:18 : that it's a really pain for them to have
30:20 : to wait for the compile to finish so
30:25 : that's yeah okay so I'm gonna do one
30:28 : plus one semicolon okay I'm gonna
30:39 : compare my initialize module and pass
30:42 : manager to theirs let's do a split
30:44 : screen
30:56 : Oh actually they did it down here after
31:01 : the jet okay maybe that's what I should
31:06 : do but I'm still gonna do this
31:08 : comparison what is this stuff here okay
31:13 : it's probably coming later
31:17 : I want to read their initialize module
31:22 : and past manager function see whether
31:26 : there are differences that one
31:32 : [Music]
31:35 : looks the same okay let me rebuild it
31:38 : and hope that fix the problem
32:22 : it were already compiled 1+1 oh uh it
32:31 : was close
32:32 : assertion failed expert symbol not found
32:36 : okay we can work with that we we
32:40 : generated IR code but now is this
32:44 : assertion which I do remember writing
32:46 : that assertion that assertion failed
32:51 : okay
32:52 : and that assertion let's find it let me
32:58 : compare it with their code okay
33:12 : hmm it looks the same as their killed a
33:16 : non-expert a non-expert and we're
33:21 : asserting the exper symbol exists
33:40 : I guess
33:46 : what is the assertion for again
34:09 : we assert the fine symbol returned a
34:13 : result
34:18 : I don't detect a difference is there
34:24 : some other thing you have to do in order
34:35 : for this to work that we call this uh
34:38 : Nanak oh this is the name they named
34:47 : that outermost function I had a feeling
34:51 : that's what it was but they never
34:53 : explicitly told me that maybe they did
35:04 : and I missed it that could be but anyway
35:07 : oh I accidentally closed out my terminal
35:12 : again okay try to build this again
35:54 : okay compiled that was actually faster
35:57 : than last time quite a bit faster one
36:00 : plus one semicolon Oh evaluated too -
36:03 : okay the compilation is working we have
36:09 : machine code and we have a jet and it
36:13 : works that's beautiful I can do more
36:15 : complicated stuff maybe maybe I can let
36:19 : me try to define a function maybe the
36:22 : function is called add and we're just
36:25 : gonna add X&Y
36:29 : ok and now let's do add four and five
36:36 : together
36:37 : I wrote it tonight
36:40 : oh that's freaking awesome beautiful
36:43 : okay so I'm going to stop this episode
36:46 : here in the next episode we'll keep
36:49 : going and hopefully finish chapter 4 see
36:53 : you on the other side