LLVM Tutorial #15: Finishing "The 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 made the JIT and it worked!! This time we extend it to be able to redefined functions.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hey there's Toby welcome back we're
00:03 : gonna continue walking through the LLVM
00:07 : tutorial from LLVM org we're in the
00:12 : latter part of chapter four and we was
00:16 : successful in creating the JIT the
00:19 : just-in-time compiler I'll show it to
00:23 : you briefly so if I do an expression
00:28 : like four times five then you know it
00:35 : will generate the LLVM ir code compile
00:39 : that into machine code and then execute
00:43 : the machine code and get the answer and
00:48 : there's pretty cool stuff so let's
00:52 : continue reading this chapter and see
00:56 : what else the author has in store for us
00:59 : I don't know the name of the person who
01:03 : wrote this tutorial if I find their name
01:08 : or it could be multiple authors I don't
01:11 : know then I will definitely give them
01:13 : credit later okay so this is basically
01:18 : working the dumb of the function shows
01:21 : the null argument function that always
01:25 : returns double that we synthesized for
01:30 : each top-level expression that is typed
01:32 : in this demonstrates very basic
01:35 : functionality but can we do more so he's
01:41 : saying let's make a test function that
01:43 : does some calculations right let's do
01:46 : what he does I that compiles the
01:50 : function and then we're going to test
02:00 : function
02:11 : if we try to run Chanukah it fails
02:15 : because every single time it it destroys
02:20 : the global module after executing
02:22 : something and there's hilarious so I
02:27 : guess we're gonna fix that next some
02:29 : function definitions and calls also work
02:32 : because something went very wrong in the
02:34 : last line that car looks valid so what
02:37 : happened as you might have guessed from
02:38 : the API a module in from the API a
02:44 : module is a unit of allocation for the
02:46 : JIT and test function was part of the
02:50 : same module that contained anonymous
02:54 : expression when we removed that module
02:57 : from the jet to free the memory for the
03:01 : anonymous expression we deleted the
03:03 : definition of test phone long with it
03:07 : then when we tried to call it test func
03:09 : a second time the JIT could no longer
03:10 : find it the easiest way to fix this is
03:13 : to put the anonymous expression in a
03:17 : separate module from the rest of the
03:19 : function definitions okay I see the JIT
03:27 : will happily resolve a function calls
03:29 : across module boundary as long as each
03:33 : of the functions called has a prototype
03:36 : and is added to the jet before it is
03:40 : called okay by putting the anonymous
03:46 : expression in a different module we can
03:48 : delete it without affecting the rest of
03:51 : the functions in fact we're going to go
03:53 : a step further and put every function in
03:55 : its own module doing so allows us to
03:59 : exploit a useful property of the
04:02 : Kaleidoscope JIT that will make our
04:05 : environment more repple like functions
04:08 : can be added to the JIT more than once
04:11 : unlike a module where every function
04:15 : must have a unique definitions a unique
04:18 : definition when you look up a symbol in
04:20 : kaleidoscope jet
04:23 : you always return the most recent
04:26 : definition interesting okay
04:31 : he's showing us that if you define the
04:34 : fou COFF you redefine foo we call foo
04:39 : LLL always execute the most recent
04:43 : definition of foo
04:44 : so to allow its function to live on in
04:47 : its own model we'll need a way to
04:49 : regenerate previous function
04:51 : declarations into each new mod row that
04:56 : we open interesting okay I guess we need
05:03 : this get function function do we already
05:08 : have okay so we can add a get function
05:32 : function apparently which the first
05:36 : asked the module to get a function to
05:42 : see if it's already been defined the
05:45 : function with that name has already been
05:46 : defined if not see whether we can code
05:50 : gender declaration from some existing
05:53 : prototype oh we're gonna have a map that
05:57 : cache is our function prototypes
06:00 : I see and then if we find it we're gonna
06:07 : Cochin it again and return that I see
06:11 : okay I understand this I'm just gonna
06:15 : copy it
06:21 : put this near the bottom okay so we're
06:26 : gonna make a map make this function
06:28 : proto's map I believe which is a map of
06:37 : AST pointer to ast node I think and then
06:43 : in later on in the cogent of the core
06:50 : exper ast we're gonna change it to call
06:55 : gate function instead of door module
06:58 : gate function that makes sense let's go
07:00 : to call X / a T cogent and we're
07:07 : changing this to call the get function
07:11 : function I think we need a four
07:14 : declaration for it to be able to use it
07:16 : so I'll put the four declaration here
07:24 : and then in the cogent method of
07:29 : function est we need to transfer
07:36 : ownership of the prototype to the
07:38 : function proto's map but keep a
07:42 : reference to it for use pillow very
07:46 : interesting okay let's go there ast
07:55 : colon colon Cochin I'm going to let's
08:02 : see first of all change this to get
08:05 : function
08:09 : but before that we're gonna what is this
08:15 : get a soapy I guess P is the actual
08:26 : proto yeah okay do we need to do that
08:42 : I'll do it like that but part of me is
08:46 : questioning whether that's actually
08:49 : necessary all right I mean I already got
08:52 : the name yeah it's the only using P to
08:56 : get the name so I'm not gonna do this
08:57 : I'm not gonna do this Auto key thing
09:01 : okay
09:02 : I think it's fine
09:07 : okay let me copy this code line by line
09:09 : because I want to absorb it better all
09:14 : right so I'm going to still haven't
09:18 : defined the function proto's map I
09:25 : already have then if we didn't have the
09:48 : function if we don't have the function
09:53 : we actually not gonna do proto Jenna
09:56 : yeah no we don't have the function we
10:01 : just returned a null pointer which we
10:03 : already had this part here got it okay I
10:07 : think this is good we do need to define
10:11 : function proto's which would be a
10:15 : standard map that contains whatever that
10:21 : is which is a it's a unique pointer to a
10:26 : prototype AST such define that
10:34 : so it's a map that takes a string are
10:43 : the keys or strings and the values are
10:48 : unique pointers to prototype ast nodes
11:01 : function photos plural yeah okay okay
11:09 : now to enable this we'll start by adding
11:12 : a new global function produce that holds
11:16 : the most recent prototype for each
11:19 : function also add a convenience method
11:22 : function right convenience method
11:31 : searches the module for an existing
11:33 : function declaration falling back to
11:35 : generating a new declaration from the
11:38 : function produce if it doesn't find one
11:41 : in call expert is T code John we just
11:45 : which here we just need to replace the
11:51 : call today module get function yes I
11:55 : went through this we also need to update
11:57 : the handle definition and handle extern
12:02 : like so
12:05 : so update it by we wouldn't add the
12:14 : module to the gym and then reinitialize
12:21 : the module and passenger here okay and
12:31 : then for handle extern we want to I
12:37 : guess take this proto because the next
12:41 : turn is a is a prototype of a function
12:44 : and we're gonna stick it into the
12:47 : function proto's okay sounds good
12:58 : in handled okay yep we're gonna
13:01 : recompile it and according to the author
13:06 : it works let's build it and see if it
13:09 : actually works
13:16 : if we can build it
13:21 : undeclared prototype ast and we need a
13:24 : four declaration
13:46 : okay I guess I will do a forward
13:49 : declaration I don't know I really know
13:52 : how to organize C++ code
14:16 : I think that compiled so this run it so
14:22 : all right what is the test that they
14:26 : okay so if you redefine a function first
14:31 : of all if you define a function it
14:34 : shouldn't go away after the first time
14:36 : you call it
14:37 : so foo of 2 is 3
14:40 : what about foo of 5 6
14:45 : great now we're gonna redefine this
14:47 : function okay it works beautiful so even
14:57 : with this simple code we get some
14:59 : surprising the powerful capabilities
15:02 : check this out
15:05 : then define X turn sine and cosine now
15:10 : you call it oh you already get sine and
15:14 : cosine because sine and cosine are
15:16 : defined in the standard c library I
15:19 : think that's what they mean yeah who is
15:29 : it
15:32 : so ya extern the external functions just
15:36 : worked and we're taking external
15:38 : functions from the c library here so
15:43 : whoa how does JIT know about sine and
15:46 : cosine the answer is surprisingly simple
15:48 : the Kaleidoscope jet has a
15:50 : straightforward symbol resolution rule
15:53 : that it uses to find symbols that aren't
15:56 : available in any given model first it
15:58 : searches all the models that have
16:01 : already been added to the jet from the
16:04 : most recent to the oldest to find the
16:07 : newest definition if no definition is
16:09 : found inside the jet it falls back to
16:12 : calling DL sim sign on the Kaleidoscope
16:17 : process itself since sine is defined
16:21 : within the jets address space now if for
16:26 : back to the calling dynamic symbol
16:30 : sin on the on the Kaleidoscope process
16:34 : itself since science defined within the
16:36 : Jets address space it simply patches up
16:39 : calls on the module to call the Lib M
16:42 : version of sign directly but in some
16:44 : cases this even goes further as sine and
16:48 : cosine are names of standard math
16:50 : functions the constant folder will
16:53 : directly evaluate the function calls to
16:56 : the correct result when called with
16:58 : constants like in the sine one above in
17:06 : the future we'll see how treating this
17:07 : symbol resolution rule can be used in
17:10 : able all sorts of useful features from
17:12 : security restricting the set of symbols
17:15 : available to jaded code to dynamic code
17:18 : generation based on symbol names and
17:20 : even lazy compilation one immediate
17:23 : benefit of the symbol resolution rule is
17:26 : that we can now extend the language by
17:28 : writing arbitrary C++ code to implement
17:31 : operations for example if we add this
17:40 : function put shard function note that
17:46 : for Windows we need to actually export
17:48 : the functions because the dynamic symbol
17:52 : loader will use get proc address to find
17:56 : the symbols that thing for Windows ok so
18:03 : now after this we can produce simple
18:06 : output to the console but using things
18:09 : like extern which art put chart 120
18:12 : which prints a lowercase X on the
18:15 : console Wow
18:18 : similar code could be used to implement
18:21 : file i/o console input and many other
18:23 : capabilities in 'caleidoscope this
18:26 : completes the JIT and optimizer chapter
18:29 : of the Kaleidoscope tutorial at this
18:31 : point we can compile a non Turing
18:35 : complete code from the language ok I
18:37 : guess we're gonna go do something
18:40 : touring complete next
18:43 : next up we'll look into extending the
18:46 : language with control flow structs
18:48 : constructs tackling some interesting
18:51 : LLVM ir issues along the way so let's
18:54 : try to put chardee put shard but i think
19:00 : it means put char which takes a double I
19:05 : will put that into the goat recompile
19:42 : okay it compiled and so let me try
19:47 : extern put charred X and let me try to
19:56 : put charred 48 yeah that's the zero that
20:04 : got printed nice cuz 48 is the ASCII
20:08 : code for for zero charred I don't know
20:15 : 67 that's C awesome yeah we can
20:22 : externalize these functions written C to
20:26 : this programming language that we've
20:27 : created that is really cool and the jet
20:31 : is really cool basically to put it in
20:36 : perspective
20:37 : basically we've managed to complete the
20:42 : whole whole pipeline in compiler design
20:47 : in particular we we've taken some code
20:51 : that is written here they say 1+1 you
20:57 : know put it through the parser which we
21:01 : wrote in chapters 1 & 2
21:06 : the parser generated some AST code I
21:09 : mean not code ast structure we
21:14 : translated this ast into I guess this
21:22 : coachin we have a bunch of cogent
21:26 : methods which when combined converts
21:31 : this ast to code in the LLVM ir format
21:40 : and then we've taken this code whenever
21:45 : we take this code and see add it to the
21:49 : module i believe me when we add module i
21:59 : believe that's when the cochin actually
22:01 : happens so it's this point i believe
22:07 : when the JIT we called the JIT add
22:11 : module because we've added the functions
22:16 : to the module and the module is just a
22:20 : representation in in IR but when we when
22:25 : we add the module which is our
22:29 : representation to the JIT that's when
22:32 : the JIT will actually compile the code
22:36 : into machine code so we take this guy go
22:41 : through the jet
22:51 : and the JIT generates machine code which
23:03 : we're gonna execute we execute this
23:06 : function this machine code we generate
23:09 : this machine code which we send it to
23:12 : the CPU and the CPU gives us back the
23:19 : result we have completed this entire
23:22 : pipeline which is usually a number in
23:26 : this language
23:27 : and the place where that happens is when
23:32 : we do this weird get address get address
23:37 : gets us the address to this machine code
23:40 : and then it exposes it to us as a C
23:44 : function which we can call and when we
23:47 : call it it sends this machine code to
23:50 : the CPU the CPU executes it and gives us
23:53 : the result so this is the final picture
23:56 : that we have and I'm very proud of
24:01 : myself for for getting this far and I'm
24:04 : proud of you for staying with me thus
24:07 : far and yeah I'm gonna stop this episode
24:12 : here and in the next episode I'm gonna
24:14 : get into chapter 5
24:22 : you