0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 ==============================================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 Kaleidoscope: Adding JIT and Optimizer Support
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 ==============================================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 .. contents::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 :local:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 Chapter 4 Introduction
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 ======================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 Welcome to Chapter 4 of the "`Implementing a language with
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 LLVM <index.html>`_" tutorial. Chapters 1-3 described the implementation
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 of a simple language and added support for generating LLVM IR. This
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 chapter describes two new techniques: adding optimizer support to your
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 language, and adding JIT compiler support. These additions will
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 demonstrate how to get nice, efficient code for the Kaleidoscope
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 language.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
19 Trivial Constant Folding
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20 ========================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 Our demonstration for Chapter 3 is elegant and easy to extend.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 Unfortunately, it does not produce wonderful code. The IRBuilder,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 however, does give us obvious optimizations when compiling simple code:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 ready> def test(x) 1+2+x;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 define double @test(double %x) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 %addtmp = fadd double 3.000000e+00, %x
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33 ret double %addtmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 This code is not a literal transcription of the AST built by parsing the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 input. That would be:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 ready> def test(x) 1+2+x;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 define double @test(double %x) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 %addtmp = fadd double 2.000000e+00, 1.000000e+00
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 %addtmp1 = fadd double %addtmp, %x
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 ret double %addtmp1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 Constant folding, as seen above, in particular, is a very common and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 very important optimization: so much so that many language implementors
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52 implement constant folding support in their AST representation.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
53
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
54 With LLVM, you don't need this support in the AST. Since all calls to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
55 build LLVM IR go through the LLVM IR builder, the builder itself checked
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 to see if there was a constant folding opportunity when you call it. If
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57 so, it just does the constant fold and return the constant instead of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58 creating an instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
59
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 Well, that was easy :). In practice, we recommend always using
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 ``IRBuilder`` when generating code like this. It has no "syntactic
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 overhead" for its use (you don't have to uglify your compiler with
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 constant checks everywhere) and it can dramatically reduce the amount of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64 LLVM IR that is generated in some cases (particular for languages with a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 macro preprocessor or that use a lot of constants).
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 On the other hand, the ``IRBuilder`` is limited by the fact that it does
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 all of its analysis inline with the code as it is built. If you take a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69 slightly more complex example:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 ready> def test(x) (1+2+x)*(x+(1+2));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 ready> Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 define double @test(double %x) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 %addtmp = fadd double 3.000000e+00, %x
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
78 %addtmp1 = fadd double %x, 3.000000e+00
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79 %multmp = fmul double %addtmp, %addtmp1
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
80 ret double %multmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83 In this case, the LHS and RHS of the multiplication are the same value.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 We'd really like to see this generate "``tmp = x+3; result = tmp*tmp;``"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 instead of computing "``x+3``" twice.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 Unfortunately, no amount of local analysis will be able to detect and
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 correct this. This requires two transformations: reassociation of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
89 expressions (to make the add's lexically identical) and Common
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
90 Subexpression Elimination (CSE) to delete the redundant add instruction.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 Fortunately, LLVM provides a broad range of optimizations that you can
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 use, in the form of "passes".
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 LLVM Optimization Passes
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 ========================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 LLVM provides many optimization passes, which do many different sorts of
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 things and have different tradeoffs. Unlike other systems, LLVM doesn't
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99 hold to the mistaken notion that one set of optimizations is right for
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
100 all languages and for all situations. LLVM allows a compiler implementor
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 to make complete decisions about what optimizations to use, in which
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 order, and in what situation.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 As a concrete example, LLVM supports both "whole module" passes, which
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 look across as large of body of code as they can (often a whole file,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 but if run at link time, this can be a substantial portion of the whole
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107 program). It also supports and includes "per-function" passes which just
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 operate on a single function at a time, without looking at other
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 functions. For more information on passes and how they are run, see the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 `How to Write a Pass <../WritingAnLLVMPass.html>`_ document and the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 `List of LLVM Passes <../Passes.html>`_.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 For Kaleidoscope, we are currently generating functions on the fly, one
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 at a time, as the user types them in. We aren't shooting for the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 ultimate optimization experience in this setting, but we also want to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116 catch the easy and quick stuff where possible. As such, we will choose
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
117 to run a few per-function optimizations as the user types the function
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
118 in. If we wanted to make a "static Kaleidoscope compiler", we would use
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 exactly the code we have now, except that we would defer running the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 optimizer until the entire file has been parsed.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 In order to get per-function optimizations going, we need to set up a
|
|
100
|
123 `FunctionPassManager <../WritingAnLLVMPass.html#what-passmanager-doesr>`_ to hold
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124 and organize the LLVM optimizations that we want to run. Once we have
|
|
95
|
125 that, we can add a set of optimizations to run. We'll need a new
|
|
|
126 FunctionPassManager for each module that we want to optimize, so we'll
|
|
|
127 write a function to create and initialize both the module and pass manager
|
|
|
128 for us:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
129
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
130 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131
|
|
95
|
132 void InitializeModuleAndPassManager(void) {
|
|
|
133 // Open a new module.
|
|
|
134 TheModule = llvm::make_unique<Module>("my cool jit", getGlobalContext());
|
|
|
135 TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136
|
|
95
|
137 // Create a new pass manager attached to it.
|
|
|
138 TheFPM = llvm::make_unique<FunctionPassManager>(TheModule.get());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139
|
|
95
|
140 // Provide basic AliasAnalysis support for GVN.
|
|
|
141 TheFPM.add(createBasicAliasAnalysisPass());
|
|
|
142 // Do simple "peephole" optimizations and bit-twiddling optzns.
|
|
|
143 TheFPM.add(createInstructionCombiningPass());
|
|
|
144 // Reassociate expressions.
|
|
|
145 TheFPM.add(createReassociatePass());
|
|
|
146 // Eliminate Common SubExpressions.
|
|
|
147 TheFPM.add(createGVNPass());
|
|
|
148 // Simplify the control flow graph (deleting unreachable blocks, etc).
|
|
|
149 TheFPM.add(createCFGSimplificationPass());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150
|
|
95
|
151 TheFPM.doInitialization();
|
|
|
152 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153
|
|
95
|
154 This code initializes the global module ``TheModule``, and the function pass
|
|
100
|
155 manager ``TheFPM``, which is attached to ``TheModule``. Once the pass manager is
|
|
95
|
156 set up, we use a series of "add" calls to add a bunch of LLVM passes.
|
|
|
157
|
|
|
158 In this case, we choose to add five passes: one analysis pass (alias analysis),
|
|
|
159 and four optimization passes. The passes we choose here are a pretty standard set
|
|
|
160 of "cleanup" optimizations that are useful for a wide variety of code. I won't
|
|
|
161 delve into what they do but, believe me, they are a good starting place :).
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 Once the PassManager is set up, we need to make use of it. We do this by
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164 running it after our newly created function is constructed (in
|
|
95
|
165 ``FunctionAST::codegen()``), but before it is returned to the client:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168
|
|
95
|
169 if (Value *RetVal = Body->codegen()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
170 // Finish off the function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
171 Builder.CreateRet(RetVal);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173 // Validate the generated code, checking for consistency.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 verifyFunction(*TheFunction);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176 // Optimize the function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 TheFPM->run(*TheFunction);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 return TheFunction;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 As you can see, this is pretty straightforward. The
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
183 ``FunctionPassManager`` optimizes and updates the LLVM Function\* in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 place, improving (hopefully) its body. With this in place, we can try
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 our test above again:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
189 ready> def test(x) (1+2+x)*(x+(1+2));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 ready> Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 define double @test(double %x) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
193 %addtmp = fadd double %x, 3.000000e+00
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 %multmp = fmul double %addtmp, %addtmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 ret double %multmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 As expected, we now get our nicely optimized code, saving a floating
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199 point add instruction from every execution of this function.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201 LLVM provides a wide variety of optimizations that can be used in
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202 certain circumstances. Some `documentation about the various
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203 passes <../Passes.html>`_ is available, but it isn't very complete.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204 Another good source of ideas can come from looking at the passes that
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205 ``Clang`` runs to get started. The "``opt``" tool allows you to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206 experiment with passes from the command line, so you can see if they do
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 anything.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
208
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
209 Now that we have reasonable code coming out of our front-end, lets talk
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210 about executing it!
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
211
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212 Adding a JIT Compiler
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213 =====================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
214
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
215 Code that is available in LLVM IR can have a wide variety of tools
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
216 applied to it. For example, you can run optimizations on it (as we did
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
217 above), you can dump it out in textual or binary forms, you can compile
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
218 the code to an assembly file (.s) for some target, or you can JIT
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
219 compile it. The nice thing about the LLVM IR representation is that it
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
220 is the "common currency" between many different parts of the compiler.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
221
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
222 In this section, we'll add JIT compiler support to our interpreter. The
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
223 basic idea that we want for Kaleidoscope is to have the user enter
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
224 function bodies as they do now, but immediately evaluate the top-level
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
225 expressions they type in. For example, if they type in "1 + 2;", we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
226 should evaluate and print out 3. If they define a function, they should
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
227 be able to call it from the command line.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
228
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
229 In order to do this, we first declare and initialize the JIT. This is
|
|
95
|
230 done by adding a global variable ``TheJIT``, and initializing it in
|
|
|
231 ``main``:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
232
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
233 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
234
|
|
95
|
235 static std::unique_ptr<KaleidoscopeJIT> TheJIT;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
236 ...
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
237 int main() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
238 ..
|
|
95
|
239 TheJIT = llvm::make_unique<KaleidoscopeJIT>();
|
|
|
240
|
|
|
241 // Run the main "interpreter loop" now.
|
|
|
242 MainLoop();
|
|
|
243
|
|
|
244 return 0;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246
|
|
95
|
247 The KaleidoscopeJIT class is a simple JIT built specifically for these
|
|
|
248 tutorials. In later chapters we will look at how it works and extend it with
|
|
|
249 new features, but for now we will take it as given. Its API is very simple::
|
|
|
250 ``addModule`` adds an LLVM IR module to the JIT, making its functions
|
|
|
251 available for execution; ``removeModule`` removes a module, freeing any
|
|
|
252 memory associated with the code in that module; and ``findSymbol`` allows us
|
|
|
253 to look up pointers to the compiled code.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
254
|
|
95
|
255 We can take this simple API and change our code that parses top-level expressions to
|
|
|
256 look like this:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
257
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
258 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
259
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
260 static void HandleTopLevelExpression() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
261 // Evaluate a top-level expression into an anonymous function.
|
|
95
|
262 if (auto FnAST = ParseTopLevelExpr()) {
|
|
|
263 if (FnAST->codegen()) {
|
|
|
264
|
|
|
265 // JIT the module containing the anonymous expression, keeping a handle so
|
|
|
266 // we can free it later.
|
|
|
267 auto H = TheJIT->addModule(std::move(TheModule));
|
|
|
268 InitializeModuleAndPassManager();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
269
|
|
95
|
270 // Search the JIT for the __anon_expr symbol.
|
|
|
271 auto ExprSymbol = TheJIT->findSymbol("__anon_expr");
|
|
|
272 assert(ExprSymbol && "Function not found");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
273
|
|
95
|
274 // Get the symbol's address and cast it to the right type (takes no
|
|
|
275 // arguments, returns a double) so we can call it as a native function.
|
|
|
276 double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
277 fprintf(stderr, "Evaluated to %f\n", FP());
|
|
95
|
278
|
|
|
279 // Delete the anonymous expression module from the JIT.
|
|
|
280 TheJIT->removeModule(H);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
281 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
282
|
|
95
|
283 If parsing and codegen succeeed, the next step is to add the module containing
|
|
|
284 the top-level expression to the JIT. We do this by calling addModule, which
|
|
|
285 triggers code generation for all the functions in the module, and returns a
|
|
|
286 handle that can be used to remove the module from the JIT later. Once the module
|
|
|
287 has been added to the JIT it can no longer be modified, so we also open a new
|
|
|
288 module to hold subsequent code by calling ``InitializeModuleAndPassManager()``.
|
|
|
289
|
|
|
290 Once we've added the module to the JIT we need to get a pointer to the final
|
|
|
291 generated code. We do this by calling the JIT's findSymbol method, and passing
|
|
|
292 the name of the top-level expression function: ``__anon_expr``. Since we just
|
|
|
293 added this function, we assert that findSymbol returned a result.
|
|
|
294
|
|
|
295 Next, we get the in-memory address of the ``__anon_expr`` function by calling
|
|
|
296 ``getAddress()`` on the symbol. Recall that we compile top-level expressions
|
|
|
297 into a self-contained LLVM function that takes no arguments and returns the
|
|
|
298 computed double. Because the LLVM JIT compiler matches the native platform ABI,
|
|
|
299 this means that you can just cast the result pointer to a function pointer of
|
|
|
300 that type and call it directly. This means, there is no difference between JIT
|
|
|
301 compiled code and native machine code that is statically linked into your
|
|
|
302 application.
|
|
|
303
|
|
|
304 Finally, since we don't support re-evaluation of top-level expressions, we
|
|
|
305 remove the module from the JIT when we're done to free the associated memory.
|
|
|
306 Recall, however, that the module we created a few lines earlier (via
|
|
|
307 ``InitializeModuleAndPassManager``) is still open and waiting for new code to be
|
|
|
308 added.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
309
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
310 With just these two changes, lets see how Kaleidoscope works now!
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
311
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
312 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
313
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
314 ready> 4+5;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
315 Read top-level expression:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316 define double @0() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 ret double 9.000000e+00
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
319 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
320
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
321 Evaluated to 9.000000
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
322
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
323 Well this looks like it is basically working. The dump of the function
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
324 shows the "no argument function that always returns double" that we
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
325 synthesize for each top-level expression that is typed in. This
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
326 demonstrates very basic functionality, but can we do more?
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
327
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
328 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330 ready> def testfunc(x y) x + y*2;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331 Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
332 define double @testfunc(double %x, double %y) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
333 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
334 %multmp = fmul double %y, 2.000000e+00
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335 %addtmp = fadd double %multmp, %x
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 ret double %addtmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 ready> testfunc(4, 10);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340 Read top-level expression:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341 define double @1() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
343 %calltmp = call double @testfunc(double 4.000000e+00, double 1.000000e+01)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344 ret double %calltmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
346
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
347 Evaluated to 24.000000
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
348
|
|
95
|
349 ready> testfunc(5, 10);
|
|
|
350 ready> LLVM ERROR: Program used external function 'testfunc' which could not be resolved!
|
|
|
351
|
|
|
352
|
|
|
353 Function definitions and calls also work, but something went very wrong on that
|
|
|
354 last line. The call looks valid, so what happened? As you may have guessed from
|
|
|
355 the the API a Module is a unit of allocation for the JIT, and testfunc was part
|
|
|
356 of the same module that contained anonymous expression. When we removed that
|
|
|
357 module from the JIT to free the memory for the anonymous expression, we deleted
|
|
|
358 the definition of ``testfunc`` along with it. Then, when we tried to call
|
|
|
359 testfunc a second time, the JIT could no longer find it.
|
|
|
360
|
|
|
361 The easiest way to fix this is to put the anonymous expression in a separate
|
|
|
362 module from the rest of the function definitions. The JIT will happily resolve
|
|
|
363 function calls across module boundaries, as long as each of the functions called
|
|
|
364 has a prototype, and is added to the JIT before it is called. By putting the
|
|
|
365 anonymous expression in a different module we can delete it without affecting
|
|
|
366 the rest of the functions.
|
|
|
367
|
|
|
368 In fact, we're going to go a step further and put every function in its own
|
|
|
369 module. Doing so allows us to exploit a useful property of the KaleidoscopeJIT
|
|
|
370 that will make our environment more REPL-like: Functions can be added to the
|
|
|
371 JIT more than once (unlike a module where every function must have a unique
|
|
|
372 definition). When you look up a symbol in KaleidoscopeJIT it will always return
|
|
|
373 the most recent definition:
|
|
|
374
|
|
|
375 ::
|
|
|
376
|
|
|
377 ready> def foo(x) x + 1;
|
|
|
378 Read function definition:
|
|
|
379 define double @foo(double %x) {
|
|
|
380 entry:
|
|
|
381 %addtmp = fadd double %x, 1.000000e+00
|
|
|
382 ret double %addtmp
|
|
|
383 }
|
|
|
384
|
|
|
385 ready> foo(2);
|
|
|
386 Evaluated to 3.000000
|
|
|
387
|
|
|
388 ready> def foo(x) x + 2;
|
|
|
389 define double @foo(double %x) {
|
|
|
390 entry:
|
|
|
391 %addtmp = fadd double %x, 2.000000e+00
|
|
|
392 ret double %addtmp
|
|
|
393 }
|
|
|
394
|
|
|
395 ready> foo(2);
|
|
|
396 Evaluated to 4.000000
|
|
|
397
|
|
|
398
|
|
|
399 To allow each function to live in its own module we'll need a way to
|
|
|
400 re-generate previous function declarations into each new module we open:
|
|
|
401
|
|
|
402 .. code-block:: c++
|
|
|
403
|
|
|
404 static std::unique_ptr<KaleidoscopeJIT> TheJIT;
|
|
|
405
|
|
|
406 ...
|
|
|
407
|
|
|
408 Function *getFunction(std::string Name) {
|
|
|
409 // First, see if the function has already been added to the current module.
|
|
|
410 if (auto *F = TheModule->getFunction(Name))
|
|
|
411 return F;
|
|
|
412
|
|
|
413 // If not, check whether we can codegen the declaration from some existing
|
|
|
414 // prototype.
|
|
|
415 auto FI = FunctionProtos.find(Name);
|
|
|
416 if (FI != FunctionProtos.end())
|
|
|
417 return FI->second->codegen();
|
|
|
418
|
|
|
419 // If no existing prototype exists, return null.
|
|
|
420 return nullptr;
|
|
|
421 }
|
|
|
422
|
|
|
423 ...
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
424
|
|
95
|
425 Value *CallExprAST::codegen() {
|
|
|
426 // Look up the name in the global module table.
|
|
|
427 Function *CalleeF = getFunction(Callee);
|
|
|
428
|
|
|
429 ...
|
|
|
430
|
|
|
431 Function *FunctionAST::codegen() {
|
|
|
432 // Transfer ownership of the prototype to the FunctionProtos map, but keep a
|
|
|
433 // reference to it for use below.
|
|
|
434 auto &P = *Proto;
|
|
|
435 FunctionProtos[Proto->getName()] = std::move(Proto);
|
|
|
436 Function *TheFunction = getFunction(P.getName());
|
|
|
437 if (!TheFunction)
|
|
|
438 return nullptr;
|
|
|
439
|
|
|
440
|
|
|
441 To enable this, we'll start by adding a new global, ``FunctionProtos``, that
|
|
|
442 holds the most recent prototype for each function. We'll also add a convenience
|
|
|
443 method, ``getFunction()``, to replace calls to ``TheModule->getFunction()``.
|
|
|
444 Our convenience method searches ``TheModule`` for an existing function
|
|
|
445 declaration, falling back to generating a new declaration from FunctionProtos if
|
|
|
446 it doesn't find one. In ``CallExprAST::codegen()`` we just need to replace the
|
|
|
447 call to ``TheModule->getFunction()``. In ``FunctionAST::codegen()`` we need to
|
|
|
448 update the FunctionProtos map first, then call ``getFunction()``. With this
|
|
|
449 done, we can always obtain a function declaration in the current module for any
|
|
|
450 previously declared function.
|
|
|
451
|
|
|
452 We also need to update HandleDefinition and HandleExtern:
|
|
|
453
|
|
|
454 .. code-block:: c++
|
|
|
455
|
|
|
456 static void HandleDefinition() {
|
|
|
457 if (auto FnAST = ParseDefinition()) {
|
|
|
458 if (auto *FnIR = FnAST->codegen()) {
|
|
|
459 fprintf(stderr, "Read function definition:");
|
|
|
460 FnIR->dump();
|
|
|
461 TheJIT->addModule(std::move(TheModule));
|
|
|
462 InitializeModuleAndPassManager();
|
|
|
463 }
|
|
|
464 } else {
|
|
|
465 // Skip token for error recovery.
|
|
|
466 getNextToken();
|
|
|
467 }
|
|
|
468 }
|
|
|
469
|
|
|
470 static void HandleExtern() {
|
|
|
471 if (auto ProtoAST = ParseExtern()) {
|
|
|
472 if (auto *FnIR = ProtoAST->codegen()) {
|
|
|
473 fprintf(stderr, "Read extern: ");
|
|
|
474 FnIR->dump();
|
|
|
475 FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST);
|
|
|
476 }
|
|
|
477 } else {
|
|
|
478 // Skip token for error recovery.
|
|
|
479 getNextToken();
|
|
|
480 }
|
|
|
481 }
|
|
|
482
|
|
|
483 In HandleDefinition, we add two lines to transfer the newly defined function to
|
|
|
484 the JIT and open a new module. In HandleExtern, we just need to add one line to
|
|
|
485 add the prototype to FunctionProtos.
|
|
|
486
|
|
|
487 With these changes made, lets try our REPL again (I removed the dump of the
|
|
|
488 anonymous functions this time, you should get the idea by now :) :
|
|
|
489
|
|
|
490 ::
|
|
|
491
|
|
|
492 ready> def foo(x) x + 1;
|
|
|
493 ready> foo(2);
|
|
|
494 Evaluated to 3.000000
|
|
|
495
|
|
|
496 ready> def foo(x) x + 2;
|
|
|
497 ready> foo(2);
|
|
|
498 Evaluated to 4.000000
|
|
|
499
|
|
|
500 It works!
|
|
|
501
|
|
|
502 Even with this simple code, we get some surprisingly powerful capabilities -
|
|
|
503 check this out:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
504
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
505 ::
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
506
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 ready> extern sin(x);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 Read extern:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
509 declare double @sin(double)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
511 ready> extern cos(x);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
512 Read extern:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
513 declare double @cos(double)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
514
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
515 ready> sin(1.0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
516 Read top-level expression:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
517 define double @2() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
518 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
519 ret double 0x3FEAED548F090CEE
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
520 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
521
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
522 Evaluated to 0.841471
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
523
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
524 ready> def foo(x) sin(x)*sin(x) + cos(x)*cos(x);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
525 Read function definition:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
526 define double @foo(double %x) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
527 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
528 %calltmp = call double @sin(double %x)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
529 %multmp = fmul double %calltmp, %calltmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
530 %calltmp2 = call double @cos(double %x)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
531 %multmp4 = fmul double %calltmp2, %calltmp2
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
532 %addtmp = fadd double %multmp, %multmp4
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
533 ret double %addtmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
534 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
535
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
536 ready> foo(4.0);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
537 Read top-level expression:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
538 define double @3() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
539 entry:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
540 %calltmp = call double @foo(double 4.000000e+00)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
541 ret double %calltmp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
542 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
543
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
544 Evaluated to 1.000000
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
545
|
|
95
|
546 Whoa, how does the JIT know about sin and cos? The answer is surprisingly
|
|
|
547 simple: The KaleidoscopeJIT has a straightforward symbol resolution rule that
|
|
|
548 it uses to find symbols that aren't available in any given module: First
|
|
|
549 it searches all the modules that have already been added to the JIT, from the
|
|
|
550 most recent to the oldest, to find the newest definition. If no definition is
|
|
|
551 found inside the JIT, it falls back to calling "``dlsym("sin")``" on the
|
|
|
552 Kaleidoscope process itself. Since "``sin``" is defined within the JIT's
|
|
|
553 address space, it simply patches up calls in the module to call the libm
|
|
|
554 version of ``sin`` directly.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
555
|
|
95
|
556 In the future we'll see how tweaking this symbol resolution rule can be used to
|
|
|
557 enable all sorts of useful features, from security (restricting the set of
|
|
|
558 symbols available to JIT'd code), to dynamic code generation based on symbol
|
|
|
559 names, and even lazy compilation.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
560
|
|
95
|
561 One immediate benefit of the symbol resolution rule is that we can now extend
|
|
|
562 the language by writing arbitrary C++ code to implement operations. For example,
|
|
|
563 if we add:
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
564
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
565 .. code-block:: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
566
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
567 /// putchard - putchar that takes a double and returns 0.
|
|
95
|
568 extern "C" double putchard(double X) {
|
|
|
569 fputc((char)X, stderr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
570 return 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
571 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
572
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
573 Now we can produce simple output to the console by using things like:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
574 "``extern putchard(x); putchard(120);``", which prints a lowercase 'x'
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
575 on the console (120 is the ASCII code for 'x'). Similar code could be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
576 used to implement file I/O, console input, and many other capabilities
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
577 in Kaleidoscope.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
578
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
579 This completes the JIT and optimizer chapter of the Kaleidoscope
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
580 tutorial. At this point, we can compile a non-Turing-complete
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
581 programming language, optimize and JIT compile it in a user-driven way.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
582 Next up we'll look into `extending the language with control flow
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 constructs <LangImpl5.html>`_, tackling some interesting LLVM IR issues
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
584 along the way.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
585
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
586 Full Code Listing
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587 =================
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
588
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
589 Here is the complete code listing for our running example, enhanced with
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590 the LLVM JIT and optimizer. To build this example, use:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
591
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
592 .. code-block:: bash
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
594 # Compile
|
|
83
|
595 clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core mcjit native` -O3 -o toy
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 # Run
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597 ./toy
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 If you are compiling this on Linux, make sure to add the "-rdynamic"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
600 option as well. This makes sure that the external functions are resolved
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
601 properly at runtime.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
602
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
603 Here is the code:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
604
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605 .. literalinclude:: ../../examples/Kaleidoscope/Chapter4/toy.cpp
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 :language: c++
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
607
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
608 `Next: Extending the language: control flow <LangImpl5.html>`_
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609
|
