1=============================================
2Building a JIT: Per-function Lazy Compilation
3=============================================
4
5.. contents::
6   :local:
7
8**This tutorial is under active development. It is incomplete and details may
9change frequently.** Nonetheless we invite you to try it out as it stands, and
10we welcome any feedback.
11
12Chapter 3 Introduction
13======================
14
15Welcome to Chapter 3 of the "Building an ORC-based JIT in LLVM" tutorial. This
16chapter discusses lazy JITing and shows you how to enable it by adding an ORC
17CompileOnDemand layer the JIT from `Chapter 2 <BuildingAJIT2.html>`_.
18
19Lazy Compilation
20================
21
22When we add a module to the KaleidoscopeJIT class from Chapter 2 it is
23immediately optimized, compiled and linked for us by the IRTransformLayer,
24IRCompileLayer and ObjectLinkingLayer respectively. This scheme, where all the
25work to make a Module executable is done up front, is simple to understand and
26its performance characteristics are easy to reason about. However, it will lead
27to very high startup times if the amount of code to be compiled is large, and
28may also do a lot of unnecessary compilation if only a few compiled functions
29are ever called at runtime. A truly "just-in-time" compiler should allow us to
30defer the compilation of any given function until the moment that function is
31first called, improving launch times and eliminating redundant work. In fact,
32the ORC APIs provide us with a layer to lazily compile LLVM IR:
33*CompileOnDemandLayer*.
34
35The CompileOnDemandLayer class conforms to the layer interface described in
36Chapter 2, but its addModuleSet method behaves quite differently from the layers
37we have seen so far: rather than doing any work up front, it just scans the
38Modules being added and arranges for each function in them to be compiled the
39first time it is called. To do this, the CompileOnDemandLayer creates two small
40utilities for each function that it scans: a *stub* and a *compile
41callback*. The stub is a pair of a function pointer (which will be pointed at
42the function's implementation once the function has been compiled) and an
43indirect jump through the pointer. By fixing the address of the indirect jump
44for the lifetime of the program we can give the function a permanent "effective
45address", one that can be safely used for indirection and function pointer
46comparison even if the function's implementation is never compiled, or if it is
47compiled more than once (due to, for example, recompiling the function at a
48higher optimization level) and changes address. The second utility, the compile
49callback, represents a re-entry point from the program into the compiler that
50will trigger compilation and then execution of a function. By initializing the
51function's stub to point at the function's compile callback, we enable lazy
52compilation: The first attempted call to the function will follow the function
53pointer and trigger the compile callback instead. The compile callback will
54compile the function, update the function pointer for the stub, then execute
55the function. On all subsequent calls to the function, the function pointer
56will point at the already-compiled function, so there is no further overhead
57from the compiler. We will look at this process in more detail in the next
58chapter of this tutorial, but for now we'll trust the CompileOnDemandLayer to
59set all the stubs and callbacks up for us. All we need to do is to add the
60CompileOnDemandLayer to the top of our stack and we'll get the benefits of
61lazy compilation. We just need a few changes to the source:
62
63.. code-block:: c++
64
65  ...
66  #include "llvm/ExecutionEngine/SectionMemoryManager.h"
67  #include "llvm/ExecutionEngine/Orc/CompileOnDemandLayer.h"
68  #include "llvm/ExecutionEngine/Orc/CompileUtils.h"
69  ...
70
71  ...
72  class KaleidoscopeJIT {
73  private:
74    std::unique_ptr<TargetMachine> TM;
75    const DataLayout DL;
76    std::unique_ptr<JITCompileCallbackManager> CompileCallbackManager;
77    ObjectLinkingLayer<> ObjectLayer;
78    IRCompileLayer<decltype(ObjectLayer)> CompileLayer;
79
80    typedef std::function<std::unique_ptr<Module>(std::unique_ptr<Module>)>
81      OptimizeFunction;
82
83    IRTransformLayer<decltype(CompileLayer), OptimizeFunction> OptimizeLayer;
84    CompileOnDemandLayer<decltype(OptimizeLayer)> CODLayer;
85
86  public:
87    typedef decltype(CODLayer)::ModuleSetHandleT ModuleHandle;
88
89First we need to include the CompileOnDemandLayer.h header, then add two new
90members: a std::unique_ptr<CompileCallbackManager> and a CompileOnDemandLayer,
91to our class. The CompileCallbackManager member is used by the CompileOnDemandLayer
92to create the compile callback needed for each function.
93
94.. code-block:: c++
95
96  KaleidoscopeJIT()
97      : TM(EngineBuilder().selectTarget()), DL(TM->createDataLayout()),
98        CompileLayer(ObjectLayer, SimpleCompiler(*TM)),
99        OptimizeLayer(CompileLayer,
100                      [this](std::unique_ptr<Module> M) {
101                        return optimizeModule(std::move(M));
102                      }),
103        CompileCallbackManager(
104            orc::createLocalCompileCallbackManager(TM->getTargetTriple(), 0)),
105        CODLayer(OptimizeLayer,
106                 [this](Function &F) { return std::set<Function*>({&F}); },
107                 *CompileCallbackManager,
108                 orc::createLocalIndirectStubsManagerBuilder(
109                   TM->getTargetTriple())) {
110    llvm::sys::DynamicLibrary::LoadLibraryPermanently(nullptr);
111  }
112
113Next we have to update our constructor to initialize the new members. To create
114an appropriate compile callback manager we use the
115createLocalCompileCallbackManager function, which takes a TargetMachine and a
116JITTargetAddress to call if it receives a request to compile an unknown
117function.  In our simple JIT this situation is unlikely to come up, so we'll
118cheat and just pass '0' here. In a production quality JIT you could give the
119address of a function that throws an exception in order to unwind the JIT'd
120code's stack.
121
122Now we can construct our CompileOnDemandLayer. Following the pattern from
123previous layers we start by passing a reference to the next layer down in our
124stack -- the OptimizeLayer. Next we need to supply a 'partitioning function':
125when a not-yet-compiled function is called, the CompileOnDemandLayer will call
126this function to ask us what we would like to compile. At a minimum we need to
127compile the function being called (given by the argument to the partitioning
128function), but we could also request that the CompileOnDemandLayer compile other
129functions that are unconditionally called (or highly likely to be called) from
130the function being called. For KaleidoscopeJIT we'll keep it simple and just
131request compilation of the function that was called. Next we pass a reference to
132our CompileCallbackManager. Finally, we need to supply an "indirect stubs
133manager builder": a utility function that constructs IndirectStubManagers, which
134are in turn used to build the stubs for the functions in each module. The
135CompileOnDemandLayer will call the indirect stub manager builder once for each
136call to addModuleSet, and use the resulting indirect stubs manager to create
137stubs for all functions in all modules in the set. If/when the module set is
138removed from the JIT the indirect stubs manager will be deleted, freeing any
139memory allocated to the stubs. We supply this function by using the
140createLocalIndirectStubsManagerBuilder utility.
141
142.. code-block:: c++
143
144  // ...
145          if (auto Sym = CODLayer.findSymbol(Name, false))
146  // ...
147  return CODLayer.addModuleSet(std::move(Ms),
148                               make_unique<SectionMemoryManager>(),
149                               std::move(Resolver));
150  // ...
151
152  // ...
153  return CODLayer.findSymbol(MangledNameStream.str(), true);
154  // ...
155
156  // ...
157  CODLayer.removeModuleSet(H);
158  // ...
159
160Finally, we need to replace the references to OptimizeLayer in our addModule,
161findSymbol, and removeModule methods. With that, we're up and running.
162
163**To be done:**
164
165** Chapter conclusion.**
166
167Full Code Listing
168=================
169
170Here is the complete code listing for our running example with a CompileOnDemand
171layer added to enable lazy function-at-a-time compilation. To build this example, use:
172
173.. code-block:: bash
174
175    # Compile
176    clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core orc native` -O3 -o toy
177    # Run
178    ./toy
179
180Here is the code:
181
182.. literalinclude:: ../../examples/Kaleidoscope/BuildingAJIT/Chapter3/KaleidoscopeJIT.h
183   :language: c++
184
185`Next: Extreme Laziness -- Using Compile Callbacks to JIT directly from ASTs <BuildingAJIT4.html>`_
186