Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / d1fbd142945f5ef0c273c3d756431f8cb9d25ded / . / docs / tutorial / LangImpl7.html
blob: 71bb397b49a8e819196eea8a760eefe76e62da64 [file] [log] [blame]
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3
4<html>
5<head>
6 <title>Kaleidoscope: Extending the Language: Mutable Variables / SSA
7 construction</title>
8 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
9 <meta name="author" content="Chris Lattner">
10 <link rel="stylesheet" href="../llvm.css" type="text/css">
11</head>
12
13<body>
14
15<div class="doc_title">Kaleidoscope: Extending the Language: Mutable Variables</div>
16
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]17<ul>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]18<li><a href="index.html">Up to Tutorial Index</a></li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]19<li>Chapter 7
20 <ol>
21 <li><a href="#intro">Chapter 7 Introduction</a></li>
22 <li><a href="#why">Why is this a hard problem?</a></li>
23 <li><a href="#memory">Memory in LLVM</a></li>
24 <li><a href="#kalvars">Mutable Variables in Kaleidoscope</a></li>
25 <li><a href="#adjustments">Adjusting Existing Variables for
26 Mutation</a></li>
27 <li><a href="#assignment">New Assignment Operator</a></li>
28 <li><a href="#localvars">User-defined Local Variables</a></li>
29 <li><a href="#code">Full Code Listing</a></li>
30 </ol>
31</li>
Chris Lattner0e555b12007-11-05 20:04:56 +0000[diff] [blame]32<li><a href="LangImpl8.html">Chapter 8</a>: Conclusion and other useful LLVM
33 tidbits</li>
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]34</ul>
35
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]36<div class="doc_author">
37 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
38</div>
39
40<!-- *********************************************************************** -->
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]41<div class="doc_section"><a name="intro">Chapter 7 Introduction</a></div>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]42<!-- *********************************************************************** -->
43
44<div class="doc_text">
45
Chris Lattner128eb862007-11-05 19:06:59 +0000[diff] [blame]46<p>Welcome to Chapter 7 of the "<a href="index.html">Implementing a language
47with LLVM</a>" tutorial. In chapters 1 through 6, we've built a very
48respectable, albeit simple, <a
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]49href="http://en.wikipedia.org/wiki/Functional_programming">functional
50programming language</a>. In our journey, we learned some parsing techniques,
51how to build and represent an AST, how to build LLVM IR, and how to optimize
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]52the resultant code as well as JIT compile it.</p>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]53
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]54<p>While Kaleidoscope is interesting as a functional language, the fact that it
55is functional makes it "too easy" to generate LLVM IR for it. In particular, a
56functional language makes it very easy to build LLVM IR directly in <a
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]57href="http://en.wikipedia.org/wiki/Static_single_assignment_form">SSA form</a>.
58Since LLVM requires that the input code be in SSA form, this is a very nice
59property and it is often unclear to newcomers how to generate code for an
60imperative language with mutable variables.</p>
61
62<p>The short (and happy) summary of this chapter is that there is no need for
63your front-end to build SSA form: LLVM provides highly tuned and well tested
64support for this, though the way it works is a bit unexpected for some.</p>
65
66</div>
67
68<!-- *********************************************************************** -->
69<div class="doc_section"><a name="why">Why is this a hard problem?</a></div>
70<!-- *********************************************************************** -->
71
72<div class="doc_text">
73
74<p>
75To understand why mutable variables cause complexities in SSA construction,
76consider this extremely simple C example:
77</p>
78
79<div class="doc_code">
80<pre>
81int G, H;
82int test(_Bool Condition) {
83 int X;
84 if (Condition)
85 X = G;
86 else
87 X = H;
88 return X;
89}
90</pre>
91</div>
92
93<p>In this case, we have the variable "X", whose value depends on the path
94executed in the program. Because there are two different possible values for X
95before the return instruction, a PHI node is inserted to merge the two values.
96The LLVM IR that we want for this example looks like this:</p>
97
98<div class="doc_code">
99<pre>
100@G = weak global i32 0 ; type of @G is i32*
101@H = weak global i32 0 ; type of @H is i32*
102
103define i32 @test(i1 %Condition) {
104entry:
105 br i1 %Condition, label %cond_true, label %cond_false
106
107cond_true:
108 %X.0 = load i32* @G
109 br label %cond_next
110
111cond_false:
112 %X.1 = load i32* @H
113 br label %cond_next
114
115cond_next:
116 %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
117 ret i32 %X.2
118}
119</pre>
120</div>
121
122<p>In this example, the loads from the G and H global variables are explicit in
123the LLVM IR, and they live in the then/else branches of the if statement
124(cond_true/cond_false). In order to merge the incoming values, the X.2 phi node
125in the cond_next block selects the right value to use based on where control
126flow is coming from: if control flow comes from the cond_false block, X.2 gets
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]127the value of X.1. Alternatively, if control flow comes from cond_true, it gets
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]128the value of X.0. The intent of this chapter is not to explain the details of
129SSA form. For more information, see one of the many <a
130href="http://en.wikipedia.org/wiki/Static_single_assignment_form">online
131references</a>.</p>
132
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]133<p>The question for this article is "who places the phi nodes when lowering
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]134assignments to mutable variables?". The issue here is that LLVM
135<em>requires</em> that its IR be in SSA form: there is no "non-ssa" mode for it.
136However, SSA construction requires non-trivial algorithms and data structures,
137so it is inconvenient and wasteful for every front-end to have to reproduce this
138logic.</p>
139
140</div>
141
142<!-- *********************************************************************** -->
143<div class="doc_section"><a name="memory">Memory in LLVM</a></div>
144<!-- *********************************************************************** -->
145
146<div class="doc_text">
147
148<p>The 'trick' here is that while LLVM does require all register values to be
149in SSA form, it does not require (or permit) memory objects to be in SSA form.
150In the example above, note that the loads from G and H are direct accesses to
151G and H: they are not renamed or versioned. This differs from some other
Chris Lattner2e5d07e2007-11-04 19:42:13 +0000[diff] [blame]152compiler systems, which do try to version memory objects. In LLVM, instead of
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]153encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
154href="../WritingAnLLVMPass.html">Analysis Passes</a> which are computed on
155demand.</p>
156
157<p>
158With this in mind, the high-level idea is that we want to make a stack variable
159(which lives in memory, because it is on the stack) for each mutable object in
160a function. To take advantage of this trick, we need to talk about how LLVM
161represents stack variables.
162</p>
163
164<p>In LLVM, all memory accesses are explicit with load/store instructions, and
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]165it is carefully designed not to have (or need) an "address-of" operator. Notice
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]166how the type of the @G/@H global variables is actually "i32*" even though the
167variable is defined as "i32". What this means is that @G defines <em>space</em>
168for an i32 in the global data area, but its <em>name</em> actually refers to the
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]169address for that space. Stack variables work the same way, except that instead of
170being declared with global variable definitions, they are declared with the
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]171<a href="../LangRef.html#i_alloca">LLVM alloca instruction</a>:</p>
172
173<div class="doc_code">
174<pre>
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]175define i32 @example() {
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]176entry:
177 %X = alloca i32 ; type of %X is i32*.
178 ...
179 %tmp = load i32* %X ; load the stack value %X from the stack.
180 %tmp2 = add i32 %tmp, 1 ; increment it
181 store i32 %tmp2, i32* %X ; store it back
182 ...
183</pre>
184</div>
185
186<p>This code shows an example of how you can declare and manipulate a stack
187variable in the LLVM IR. Stack memory allocated with the alloca instruction is
188fully general: you can pass the address of the stack slot to functions, you can
189store it in other variables, etc. In our example above, we could rewrite the
190example to use the alloca technique to avoid using a PHI node:</p>
191
192<div class="doc_code">
193<pre>
194@G = weak global i32 0 ; type of @G is i32*
195@H = weak global i32 0 ; type of @H is i32*
196
197define i32 @test(i1 %Condition) {
198entry:
199 %X = alloca i32 ; type of %X is i32*.
200 br i1 %Condition, label %cond_true, label %cond_false
201
202cond_true:
203 %X.0 = load i32* @G
204 store i32 %X.0, i32* %X ; Update X
205 br label %cond_next
206
207cond_false:
208 %X.1 = load i32* @H
209 store i32 %X.1, i32* %X ; Update X
210 br label %cond_next
211
212cond_next:
213 %X.2 = load i32* %X ; Read X
214 ret i32 %X.2
215}
216</pre>
217</div>
218
219<p>With this, we have discovered a way to handle arbitrary mutable variables
220without the need to create Phi nodes at all:</p>
221
222<ol>
223<li>Each mutable variable becomes a stack allocation.</li>
224<li>Each read of the variable becomes a load from the stack.</li>
225<li>Each update of the variable becomes a store to the stack.</li>
226<li>Taking the address of a variable just uses the stack address directly.</li>
227</ol>
228
229<p>While this solution has solved our immediate problem, it introduced another
230one: we have now apparently introduced a lot of stack traffic for very simple
231and common operations, a major performance problem. Fortunately for us, the
232LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
233this case, promoting allocas like this into SSA registers, inserting Phi nodes
234as appropriate. If you run this example through the pass, for example, you'll
235get:</p>
236
237<div class="doc_code">
238<pre>
239$ <b>llvm-as &lt; example.ll | opt -mem2reg | llvm-dis</b>
240@G = weak global i32 0
241@H = weak global i32 0
242
243define i32 @test(i1 %Condition) {
244entry:
245 br i1 %Condition, label %cond_true, label %cond_false
246
247cond_true:
248 %X.0 = load i32* @G
249 br label %cond_next
250
251cond_false:
252 %X.1 = load i32* @H
253 br label %cond_next
254
255cond_next:
256 %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
257 ret i32 %X.01
258}
259</pre>
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]260</div>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]261
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]262<p>The mem2reg pass implements the standard "iterated dominance frontier"
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]263algorithm for constructing SSA form and has a number of optimizations that speed
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]264up (very common) degenerate cases. The mem2reg optimization pass is the answer to dealing
265with mutable variables, and we highly recommend that you depend on it. Note that
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]266mem2reg only works on variables in certain circumstances:</p>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]267
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]268<ol>
269<li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
270promotes them. It does not apply to global variables or heap allocations.</li>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]271
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]272<li>mem2reg only looks for alloca instructions in the entry block of the
273function. Being in the entry block guarantees that the alloca is only executed
274once, which makes analysis simpler.</li>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]275
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]276<li>mem2reg only promotes allocas whose uses are direct loads and stores. If
277the address of the stack object is passed to a function, or if any funny pointer
278arithmetic is involved, the alloca will not be promoted.</li>
279
Chris Lattnera56b22d2007-11-05 17:45:54 +0000[diff] [blame]280<li>mem2reg only works on allocas of <a
281href="../LangRef.html#t_classifications">first class</a>
282values (such as pointers, scalars and vectors), and only if the array size
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]283of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of
284promoting structs or arrays to registers. Note that the "scalarrepl" pass is
285more powerful and can promote structs, "unions", and arrays in many cases.</li>
286
287</ol>
288
289<p>
290All of these properties are easy to satisfy for most imperative languages, and
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]291we'll illustrate it below with Kaleidoscope. The final question you may be
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]292asking is: should I bother with this nonsense for my front-end? Wouldn't it be
293better if I just did SSA construction directly, avoiding use of the mem2reg
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]294optimization pass? In short, we strongly recommend that you use this technique
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]295for building SSA form, unless there is an extremely good reason not to. Using
296this technique is:</p>
297
298<ul>
299<li>Proven and well tested: llvm-gcc and clang both use this technique for local
300mutable variables. As such, the most common clients of LLVM are using this to
301handle a bulk of their variables. You can be sure that bugs are found fast and
302fixed early.</li>
303
304<li>Extremely Fast: mem2reg has a number of special cases that make it fast in
305common cases as well as fully general. For example, it has fast-paths for
306variables that are only used in a single block, variables that only have one
307assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
308</li>
309
310<li>Needed for debug info generation: <a href="../SourceLevelDebugging.html">
311Debug information in LLVM</a> relies on having the address of the variable
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]312exposed so that debug info can be attached to it. This technique dovetails
313very naturally with this style of debug info.</li>
Chris Lattnere7198312007-11-03 22:22:30 +0000[diff] [blame]314</ul>
315
316<p>If nothing else, this makes it much easier to get your front-end up and
317running, and is very simple to implement. Lets extend Kaleidoscope with mutable
318variables now!
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]319</p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]320
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]321</div>
322
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]323<!-- *********************************************************************** -->
324<div class="doc_section"><a name="kalvars">Mutable Variables in
325Kaleidoscope</a></div>
326<!-- *********************************************************************** -->
327
328<div class="doc_text">
329
330<p>Now that we know the sort of problem we want to tackle, lets see what this
331looks like in the context of our little Kaleidoscope language. We're going to
332add two features:</p>
333
334<ol>
335<li>The ability to mutate variables with the '=' operator.</li>
336<li>The ability to define new variables.</li>
337</ol>
338
339<p>While the first item is really what this is about, we only have variables
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]340for incoming arguments as well as for induction variables, and redefining those only
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]341goes so far :). Also, the ability to define new variables is a
342useful thing regardless of whether you will be mutating them. Here's a
343motivating example that shows how we could use these:</p>
344
345<div class="doc_code">
346<pre>
347# Define ':' for sequencing: as a low-precedence operator that ignores operands
348# and just returns the RHS.
349def binary : 1 (x y) y;
350
351# Recursive fib, we could do this before.
352def fib(x)
353 if (x &lt; 3) then
354 1
355 else
356 fib(x-1)+fib(x-2);
357
358# Iterative fib.
359def fibi(x)
360 <b>var a = 1, b = 1, c in</b>
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]361 (for i = 3, i &lt; x in
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]362 <b>c = a + b</b> :
363 <b>a = b</b> :
364 <b>b = c</b>) :
365 b;
366
367# Call it.
368fibi(10);
369</pre>
370</div>
371
372<p>
373In order to mutate variables, we have to change our existing variables to use
374the "alloca trick". Once we have that, we'll add our new operator, then extend
375Kaleidoscope to support new variable definitions.
376</p>
377
378</div>
379
380<!-- *********************************************************************** -->
381<div class="doc_section"><a name="adjustments">Adjusting Existing Variables for
382Mutation</a></div>
383<!-- *********************************************************************** -->
384
385<div class="doc_text">
386
387<p>
388The symbol table in Kaleidoscope is managed at code generation time by the
389'<tt>NamedValues</tt>' map. This map currently keeps track of the LLVM "Value*"
390that holds the double value for the named variable. In order to support
391mutation, we need to change this slightly, so that it <tt>NamedValues</tt> holds
392the <em>memory location</em> of the variable in question. Note that this
393change is a refactoring: it changes the structure of the code, but does not
394(by itself) change the behavior of the compiler. All of these changes are
395isolated in the Kaleidoscope code generator.</p>
396
397<p>
398At this point in Kaleidoscope's development, it only supports variables for two
399things: incoming arguments to functions and the induction variable of 'for'
400loops. For consistency, we'll allow mutation of these variables in addition to
401other user-defined variables. This means that these will both need memory
402locations.
403</p>
404
405<p>To start our transformation of Kaleidoscope, we'll change the NamedValues
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]406map so that it maps to AllocaInst* instead of Value*. Once we do this, the C++
407compiler will tell us what parts of the code we need to update:</p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]408
409<div class="doc_code">
410<pre>
411static std::map&lt;std::string, AllocaInst*&gt; NamedValues;
412</pre>
413</div>
414
415<p>Also, since we will need to create these alloca's, we'll use a helper
416function that ensures that the allocas are created in the entry block of the
417function:</p>
418
419<div class="doc_code">
420<pre>
421/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
422/// the function. This is used for mutable variables etc.
423static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
424 const std::string &amp;VarName) {
Gabor Greifd6c1ed02009-03-11 19:51:07 +0000[diff] [blame]425 IRBuilder&lt;&gt; TmpB(&amp;TheFunction-&gt;getEntryBlock(),
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]426 TheFunction-&gt;getEntryBlock().begin());
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]427 return TmpB.CreateAlloca(Type::DoubleTy, 0, VarName.c_str());
428}
429</pre>
430</div>
431
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]432<p>This funny looking code creates an IRBuilder object that is pointing at
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]433the first instruction (.begin()) of the entry block. It then creates an alloca
434with the expected name and returns it. Because all values in Kaleidoscope are
435doubles, there is no need to pass in a type to use.</p>
436
437<p>With this in place, the first functionality change we want to make is to
438variable references. In our new scheme, variables live on the stack, so code
439generating a reference to them actually needs to produce a load from the stack
440slot:</p>
441
442<div class="doc_code">
443<pre>
444Value *VariableExprAST::Codegen() {
445 // Look this variable up in the function.
446 Value *V = NamedValues[Name];
447 if (V == 0) return ErrorV("Unknown variable name");
448
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]449 <b>// Load the value.
450 return Builder.CreateLoad(V, Name.c_str());</b>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]451}
452</pre>
453</div>
454
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]455<p>As you can see, this is pretty straightforward. Now we need to update the
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]456things that define the variables to set up the alloca. We'll start with
457<tt>ForExprAST::Codegen</tt> (see the <a href="#code">full code listing</a> for
458the unabridged code):</p>
459
460<div class="doc_code">
461<pre>
462 Function *TheFunction = Builder.GetInsertBlock()->getParent();
463
464 <b>// Create an alloca for the variable in the entry block.
465 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);</b>
466
467 // Emit the start code first, without 'variable' in scope.
468 Value *StartVal = Start-&gt;Codegen();
469 if (StartVal == 0) return 0;
470
471 <b>// Store the value into the alloca.
472 Builder.CreateStore(StartVal, Alloca);</b>
473 ...
474
475 // Compute the end condition.
476 Value *EndCond = End-&gt;Codegen();
477 if (EndCond == 0) return EndCond;
478
479 <b>// Reload, increment, and restore the alloca. This handles the case where
480 // the body of the loop mutates the variable.
481 Value *CurVar = Builder.CreateLoad(Alloca);
482 Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
483 Builder.CreateStore(NextVar, Alloca);</b>
484 ...
485</pre>
486</div>
487
488<p>This code is virtually identical to the code <a
489href="LangImpl5.html#forcodegen">before we allowed mutable variables</a>. The
490big difference is that we no longer have to construct a PHI node, and we use
491load/store to access the variable as needed.</p>
492
493<p>To support mutable argument variables, we need to also make allocas for them.
494The code for this is also pretty simple:</p>
495
496<div class="doc_code">
497<pre>
498/// CreateArgumentAllocas - Create an alloca for each argument and register the
499/// argument in the symbol table so that references to it will succeed.
500void PrototypeAST::CreateArgumentAllocas(Function *F) {
501 Function::arg_iterator AI = F-&gt;arg_begin();
502 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
503 // Create an alloca for this variable.
504 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
505
506 // Store the initial value into the alloca.
507 Builder.CreateStore(AI, Alloca);
508
509 // Add arguments to variable symbol table.
510 NamedValues[Args[Idx]] = Alloca;
511 }
512}
513</pre>
514</div>
515
516<p>For each argument, we make an alloca, store the input value to the function
517into the alloca, and register the alloca as the memory location for the
518argument. This method gets invoked by <tt>FunctionAST::Codegen</tt> right after
519it sets up the entry block for the function.</p>
520
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]521<p>The final missing piece is adding the mem2reg pass, which allows us to get
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]522good codegen once again:</p>
523
524<div class="doc_code">
525<pre>
526 // Set up the optimizer pipeline. Start with registering info about how the
527 // target lays out data structures.
528 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
529 <b>// Promote allocas to registers.
530 OurFPM.add(createPromoteMemoryToRegisterPass());</b>
531 // Do simple "peephole" optimizations and bit-twiddling optzns.
532 OurFPM.add(createInstructionCombiningPass());
533 // Reassociate expressions.
534 OurFPM.add(createReassociatePass());
535</pre>
536</div>
537
538<p>It is interesting to see what the code looks like before and after the
539mem2reg optimization runs. For example, this is the before/after code for our
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]540recursive fib function. Before the optimization:</p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]541
542<div class="doc_code">
543<pre>
544define double @fib(double %x) {
545entry:
546 <b>%x1 = alloca double
547 store double %x, double* %x1
548 %x2 = load double* %x1</b>
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]549 %cmptmp = fcmp ult double %x2, 3.000000e+00
550 %booltmp = uitofp i1 %cmptmp to double
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]551 %ifcond = fcmp one double %booltmp, 0.000000e+00
552 br i1 %ifcond, label %then, label %else
553
554then: ; preds = %entry
555 br label %ifcont
556
557else: ; preds = %entry
558 <b>%x3 = load double* %x1</b>
559 %subtmp = sub double %x3, 1.000000e+00
560 %calltmp = call double @fib( double %subtmp )
561 <b>%x4 = load double* %x1</b>
562 %subtmp5 = sub double %x4, 2.000000e+00
563 %calltmp6 = call double @fib( double %subtmp5 )
564 %addtmp = add double %calltmp, %calltmp6
565 br label %ifcont
566
567ifcont: ; preds = %else, %then
568 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
569 ret double %iftmp
570}
571</pre>
572</div>
573
574<p>Here there is only one variable (x, the input argument) but you can still
575see the extremely simple-minded code generation strategy we are using. In the
576entry block, an alloca is created, and the initial input value is stored into
577it. Each reference to the variable does a reload from the stack. Also, note
578that we didn't modify the if/then/else expression, so it still inserts a PHI
579node. While we could make an alloca for it, it is actually easier to create a
580PHI node for it, so we still just make the PHI.</p>
581
582<p>Here is the code after the mem2reg pass runs:</p>
583
584<div class="doc_code">
585<pre>
586define double @fib(double %x) {
587entry:
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]588 %cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
589 %booltmp = uitofp i1 %cmptmp to double
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]590 %ifcond = fcmp one double %booltmp, 0.000000e+00
591 br i1 %ifcond, label %then, label %else
592
593then:
594 br label %ifcont
595
596else:
597 %subtmp = sub double <b>%x</b>, 1.000000e+00
598 %calltmp = call double @fib( double %subtmp )
599 %subtmp5 = sub double <b>%x</b>, 2.000000e+00
600 %calltmp6 = call double @fib( double %subtmp5 )
601 %addtmp = add double %calltmp, %calltmp6
602 br label %ifcont
603
604ifcont: ; preds = %else, %then
605 %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
606 ret double %iftmp
607}
608</pre>
609</div>
610
611<p>This is a trivial case for mem2reg, since there are no redefinitions of the
612variable. The point of showing this is to calm your tension about inserting
613such blatent inefficiencies :).</p>
614
615<p>After the rest of the optimizers run, we get:</p>
616
617<div class="doc_code">
618<pre>
619define double @fib(double %x) {
620entry:
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]621 %cmptmp = fcmp ult double %x, 3.000000e+00
622 %booltmp = uitofp i1 %cmptmp to double
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]623 %ifcond = fcmp ueq double %booltmp, 0.000000e+00
624 br i1 %ifcond, label %else, label %ifcont
625
626else:
627 %subtmp = sub double %x, 1.000000e+00
628 %calltmp = call double @fib( double %subtmp )
629 %subtmp5 = sub double %x, 2.000000e+00
630 %calltmp6 = call double @fib( double %subtmp5 )
631 %addtmp = add double %calltmp, %calltmp6
632 ret double %addtmp
633
634ifcont:
635 ret double 1.000000e+00
636}
637</pre>
638</div>
639
640<p>Here we see that the simplifycfg pass decided to clone the return instruction
641into the end of the 'else' block. This allowed it to eliminate some branches
642and the PHI node.</p>
643
644<p>Now that all symbol table references are updated to use stack variables,
645we'll add the assignment operator.</p>
646
647</div>
648
649<!-- *********************************************************************** -->
650<div class="doc_section"><a name="assignment">New Assignment Operator</a></div>
651<!-- *********************************************************************** -->
652
653<div class="doc_text">
654
655<p>With our current framework, adding a new assignment operator is really
656simple. We will parse it just like any other binary operator, but handle it
657internally (instead of allowing the user to define it). The first step is to
658set a precedence:</p>
659
660<div class="doc_code">
661<pre>
662 int main() {
663 // Install standard binary operators.
664 // 1 is lowest precedence.
665 <b>BinopPrecedence['='] = 2;</b>
666 BinopPrecedence['&lt;'] = 10;
667 BinopPrecedence['+'] = 20;
668 BinopPrecedence['-'] = 20;
669</pre>
670</div>
671
672<p>Now that the parser knows the precedence of the binary operator, it takes
673care of all the parsing and AST generation. We just need to implement codegen
674for the assignment operator. This looks like:</p>
675
676<div class="doc_code">
677<pre>
678Value *BinaryExprAST::Codegen() {
679 // Special case '=' because we don't want to emit the LHS as an expression.
680 if (Op == '=') {
681 // Assignment requires the LHS to be an identifier.
682 VariableExprAST *LHSE = dynamic_cast&lt;VariableExprAST*&gt;(LHS);
683 if (!LHSE)
684 return ErrorV("destination of '=' must be a variable");
685</pre>
686</div>
687
688<p>Unlike the rest of the binary operators, our assignment operator doesn't
689follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
690as a special case before the other binary operators are handled. The other
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]691strange thing is that it requires the LHS to be a variable. It is invalid to
692have "(x+1) = expr" - only things like "x = expr" are allowed.
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]693</p>
694
695<div class="doc_code">
696<pre>
697 // Codegen the RHS.
698 Value *Val = RHS-&gt;Codegen();
699 if (Val == 0) return 0;
700
701 // Look up the name.
702 Value *Variable = NamedValues[LHSE-&gt;getName()];
703 if (Variable == 0) return ErrorV("Unknown variable name");
704
705 Builder.CreateStore(Val, Variable);
706 return Val;
707 }
708 ...
709</pre>
710</div>
711
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]712<p>Once we have the variable, codegen'ing the assignment is straightforward:
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]713we emit the RHS of the assignment, create a store, and return the computed
714value. Returning a value allows for chained assignments like "X = (Y = Z)".</p>
715
716<p>Now that we have an assignment operator, we can mutate loop variables and
717arguments. For example, we can now run code like this:</p>
718
719<div class="doc_code">
720<pre>
721# Function to print a double.
722extern printd(x);
723
724# Define ':' for sequencing: as a low-precedence operator that ignores operands
725# and just returns the RHS.
726def binary : 1 (x y) y;
727
728def test(x)
729 printd(x) :
730 x = 4 :
731 printd(x);
732
733test(123);
734</pre>
735</div>
736
737<p>When run, this example prints "123" and then "4", showing that we did
738actually mutate the value! Okay, we have now officially implemented our goal:
739getting this to work requires SSA construction in the general case. However,
740to be really useful, we want the ability to define our own local variables, lets
741add this next!
742</p>
743
744</div>
745
746<!-- *********************************************************************** -->
747<div class="doc_section"><a name="localvars">User-defined Local
748Variables</a></div>
749<!-- *********************************************************************** -->
750
751<div class="doc_text">
752
753<p>Adding var/in is just like any other other extensions we made to
754Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
755The first step for adding our new 'var/in' construct is to extend the lexer.
756As before, this is pretty trivial, the code looks like this:</p>
757
758<div class="doc_code">
759<pre>
760enum Token {
761 ...
762 <b>// var definition
763 tok_var = -13</b>
764...
765}
766...
767static int gettok() {
768...
769 if (IdentifierStr == "in") return tok_in;
770 if (IdentifierStr == "binary") return tok_binary;
771 if (IdentifierStr == "unary") return tok_unary;
772 <b>if (IdentifierStr == "var") return tok_var;</b>
773 return tok_identifier;
774...
775</pre>
776</div>
777
778<p>The next step is to define the AST node that we will construct. For var/in,
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]779it looks like this:</p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]780
781<div class="doc_code">
782<pre>
783/// VarExprAST - Expression class for var/in
784class VarExprAST : public ExprAST {
785 std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; VarNames;
786 ExprAST *Body;
787public:
788 VarExprAST(const std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; &amp;varnames,
789 ExprAST *body)
790 : VarNames(varnames), Body(body) {}
791
792 virtual Value *Codegen();
793};
794</pre>
795</div>
796
797<p>var/in allows a list of names to be defined all at once, and each name can
798optionally have an initializer value. As such, we capture this information in
799the VarNames vector. Also, var/in has a body, this body is allowed to access
Chris Lattner1e46a6c2007-11-07 06:34:39 +0000[diff] [blame]800the variables defined by the var/in.</p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]801
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]802<p>With this in place, we can define the parser pieces. The first thing we do is add
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]803it as a primary expression:</p>
804
805<div class="doc_code">
806<pre>
807/// primary
808/// ::= identifierexpr
809/// ::= numberexpr
810/// ::= parenexpr
811/// ::= ifexpr
812/// ::= forexpr
813<b>/// ::= varexpr</b>
814static ExprAST *ParsePrimary() {
815 switch (CurTok) {
816 default: return Error("unknown token when expecting an expression");
817 case tok_identifier: return ParseIdentifierExpr();
818 case tok_number: return ParseNumberExpr();
819 case '(': return ParseParenExpr();
820 case tok_if: return ParseIfExpr();
821 case tok_for: return ParseForExpr();
822 <b>case tok_var: return ParseVarExpr();</b>
823 }
824}
825</pre>
826</div>
827
828<p>Next we define ParseVarExpr:</p>
829
830<div class="doc_code">
831<pre>
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]832/// varexpr ::= 'var' identifier ('=' expression)?
833// (',' identifier ('=' expression)?)* 'in' expression
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]834static ExprAST *ParseVarExpr() {
835 getNextToken(); // eat the var.
836
837 std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; VarNames;
838
839 // At least one variable name is required.
840 if (CurTok != tok_identifier)
841 return Error("expected identifier after var");
842</pre>
843</div>
844
845<p>The first part of this code parses the list of identifier/expr pairs into the
846local <tt>VarNames</tt> vector.
847
848<div class="doc_code">
849<pre>
850 while (1) {
851 std::string Name = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]852 getNextToken(); // eat identifier.
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]853
854 // Read the optional initializer.
855 ExprAST *Init = 0;
856 if (CurTok == '=') {
857 getNextToken(); // eat the '='.
858
859 Init = ParseExpression();
860 if (Init == 0) return 0;
861 }
862
863 VarNames.push_back(std::make_pair(Name, Init));
864
865 // End of var list, exit loop.
866 if (CurTok != ',') break;
867 getNextToken(); // eat the ','.
868
869 if (CurTok != tok_identifier)
870 return Error("expected identifier list after var");
871 }
872</pre>
873</div>
874
875<p>Once all the variables are parsed, we then parse the body and create the
876AST node:</p>
877
878<div class="doc_code">
879<pre>
880 // At this point, we have to have 'in'.
881 if (CurTok != tok_in)
882 return Error("expected 'in' keyword after 'var'");
883 getNextToken(); // eat 'in'.
884
885 ExprAST *Body = ParseExpression();
886 if (Body == 0) return 0;
887
888 return new VarExprAST(VarNames, Body);
889}
890</pre>
891</div>
892
893<p>Now that we can parse and represent the code, we need to support emission of
894LLVM IR for it. This code starts out with:</p>
895
896<div class="doc_code">
897<pre>
898Value *VarExprAST::Codegen() {
899 std::vector&lt;AllocaInst *&gt; OldBindings;
900
901 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
902
903 // Register all variables and emit their initializer.
904 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
905 const std::string &amp;VarName = VarNames[i].first;
906 ExprAST *Init = VarNames[i].second;
907</pre>
908</div>
909
910<p>Basically it loops over all the variables, installing them one at a time.
911For each variable we put into the symbol table, we remember the previous value
912that we replace in OldBindings.</p>
913
914<div class="doc_code">
915<pre>
916 // Emit the initializer before adding the variable to scope, this prevents
917 // the initializer from referencing the variable itself, and permits stuff
918 // like this:
919 // var a = 1 in
920 // var a = a in ... # refers to outer 'a'.
921 Value *InitVal;
922 if (Init) {
923 InitVal = Init-&gt;Codegen();
924 if (InitVal == 0) return 0;
925 } else { // If not specified, use 0.0.
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]926 InitVal = ConstantFP::get(APFloat(0.0));
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]927 }
928
929 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
930 Builder.CreateStore(InitVal, Alloca);
931
932 // Remember the old variable binding so that we can restore the binding when
933 // we unrecurse.
934 OldBindings.push_back(NamedValues[VarName]);
935
936 // Remember this binding.
937 NamedValues[VarName] = Alloca;
938 }
939</pre>
940</div>
941
942<p>There are more comments here than code. The basic idea is that we emit the
943initializer, create the alloca, then update the symbol table to point to it.
944Once all the variables are installed in the symbol table, we evaluate the body
945of the var/in expression:</p>
946
947<div class="doc_code">
948<pre>
949 // Codegen the body, now that all vars are in scope.
950 Value *BodyVal = Body-&gt;Codegen();
951 if (BodyVal == 0) return 0;
952</pre>
953</div>
954
955<p>Finally, before returning, we restore the previous variable bindings:</p>
956
957<div class="doc_code">
958<pre>
959 // Pop all our variables from scope.
960 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
961 NamedValues[VarNames[i].first] = OldBindings[i];
962
963 // Return the body computation.
964 return BodyVal;
965}
966</pre>
967</div>
968
969<p>The end result of all of this is that we get properly scoped variable
970definitions, and we even (trivially) allow mutation of them :).</p>
971
972<p>With this, we completed what we set out to do. Our nice iterative fib
973example from the intro compiles and runs just fine. The mem2reg pass optimizes
974all of our stack variables into SSA registers, inserting PHI nodes where needed,
Chris Lattnerb7e6b1a2007-11-15 04:51:31 +0000[diff] [blame]975and our front-end remains simple: no "iterated dominance frontier" computation
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]976anywhere in sight.</p>
977
978</div>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]979
980<!-- *********************************************************************** -->
981<div class="doc_section"><a name="code">Full Code Listing</a></div>
982<!-- *********************************************************************** -->
983
984<div class="doc_text">
985
986<p>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]987Here is the complete code listing for our running example, enhanced with mutable
988variables and var/in support. To build this example, use:
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]989</p>
990
991<div class="doc_code">
992<pre>
993 # Compile
994 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
995 # Run
996 ./toy
997</pre>
998</div>
999
1000<p>Here is the code:</p>
1001
1002<div class="doc_code">
1003<pre>
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1004#include "llvm/DerivedTypes.h"
1005#include "llvm/ExecutionEngine/ExecutionEngine.h"
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame^]1006#include "llvm/LLVMContext.h"
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1007#include "llvm/Module.h"
1008#include "llvm/ModuleProvider.h"
1009#include "llvm/PassManager.h"
1010#include "llvm/Analysis/Verifier.h"
1011#include "llvm/Target/TargetData.h"
1012#include "llvm/Transforms/Scalar.h"
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]1013#include "llvm/Support/IRBuilder.h"
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1014#include &lt;cstdio&gt;
1015#include &lt;string&gt;
1016#include &lt;map&gt;
1017#include &lt;vector&gt;
1018using namespace llvm;
1019
1020//===----------------------------------------------------------------------===//
1021// Lexer
1022//===----------------------------------------------------------------------===//
1023
1024// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
1025// of these for known things.
1026enum Token {
1027 tok_eof = -1,
1028
1029 // commands
1030 tok_def = -2, tok_extern = -3,
1031
1032 // primary
1033 tok_identifier = -4, tok_number = -5,
1034
1035 // control
1036 tok_if = -6, tok_then = -7, tok_else = -8,
1037 tok_for = -9, tok_in = -10,
1038
1039 // operators
1040 tok_binary = -11, tok_unary = -12,
1041
1042 // var definition
1043 tok_var = -13
1044};
1045
1046static std::string IdentifierStr; // Filled in if tok_identifier
1047static double NumVal; // Filled in if tok_number
1048
1049/// gettok - Return the next token from standard input.
1050static int gettok() {
1051 static int LastChar = ' ';
1052
1053 // Skip any whitespace.
1054 while (isspace(LastChar))
1055 LastChar = getchar();
1056
1057 if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
1058 IdentifierStr = LastChar;
1059 while (isalnum((LastChar = getchar())))
1060 IdentifierStr += LastChar;
1061
1062 if (IdentifierStr == "def") return tok_def;
1063 if (IdentifierStr == "extern") return tok_extern;
1064 if (IdentifierStr == "if") return tok_if;
1065 if (IdentifierStr == "then") return tok_then;
1066 if (IdentifierStr == "else") return tok_else;
1067 if (IdentifierStr == "for") return tok_for;
1068 if (IdentifierStr == "in") return tok_in;
1069 if (IdentifierStr == "binary") return tok_binary;
1070 if (IdentifierStr == "unary") return tok_unary;
1071 if (IdentifierStr == "var") return tok_var;
1072 return tok_identifier;
1073 }
1074
1075 if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+
1076 std::string NumStr;
1077 do {
1078 NumStr += LastChar;
1079 LastChar = getchar();
1080 } while (isdigit(LastChar) || LastChar == '.');
1081
1082 NumVal = strtod(NumStr.c_str(), 0);
1083 return tok_number;
1084 }
1085
1086 if (LastChar == '#') {
1087 // Comment until end of line.
1088 do LastChar = getchar();
Chris Lattnerc80c23f2007-12-02 22:46:01 +0000[diff] [blame]1089 while (LastChar != EOF &amp;&amp; LastChar != '\n' &amp;&amp; LastChar != '\r');
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1090
1091 if (LastChar != EOF)
1092 return gettok();
1093 }
1094
1095 // Check for end of file. Don't eat the EOF.
1096 if (LastChar == EOF)
1097 return tok_eof;
1098
1099 // Otherwise, just return the character as its ascii value.
1100 int ThisChar = LastChar;
1101 LastChar = getchar();
1102 return ThisChar;
1103}
1104
1105//===----------------------------------------------------------------------===//
1106// Abstract Syntax Tree (aka Parse Tree)
1107//===----------------------------------------------------------------------===//
1108
1109/// ExprAST - Base class for all expression nodes.
1110class ExprAST {
1111public:
1112 virtual ~ExprAST() {}
1113 virtual Value *Codegen() = 0;
1114};
1115
1116/// NumberExprAST - Expression class for numeric literals like "1.0".
1117class NumberExprAST : public ExprAST {
1118 double Val;
1119public:
1120 NumberExprAST(double val) : Val(val) {}
1121 virtual Value *Codegen();
1122};
1123
1124/// VariableExprAST - Expression class for referencing a variable, like "a".
1125class VariableExprAST : public ExprAST {
1126 std::string Name;
1127public:
1128 VariableExprAST(const std::string &amp;name) : Name(name) {}
1129 const std::string &amp;getName() const { return Name; }
1130 virtual Value *Codegen();
1131};
1132
1133/// UnaryExprAST - Expression class for a unary operator.
1134class UnaryExprAST : public ExprAST {
1135 char Opcode;
1136 ExprAST *Operand;
1137public:
1138 UnaryExprAST(char opcode, ExprAST *operand)
1139 : Opcode(opcode), Operand(operand) {}
1140 virtual Value *Codegen();
1141};
1142
1143/// BinaryExprAST - Expression class for a binary operator.
1144class BinaryExprAST : public ExprAST {
1145 char Op;
1146 ExprAST *LHS, *RHS;
1147public:
1148 BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs)
1149 : Op(op), LHS(lhs), RHS(rhs) {}
1150 virtual Value *Codegen();
1151};
1152
1153/// CallExprAST - Expression class for function calls.
1154class CallExprAST : public ExprAST {
1155 std::string Callee;
1156 std::vector&lt;ExprAST*&gt; Args;
1157public:
1158 CallExprAST(const std::string &amp;callee, std::vector&lt;ExprAST*&gt; &amp;args)
1159 : Callee(callee), Args(args) {}
1160 virtual Value *Codegen();
1161};
1162
1163/// IfExprAST - Expression class for if/then/else.
1164class IfExprAST : public ExprAST {
1165 ExprAST *Cond, *Then, *Else;
1166public:
1167 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
1168 : Cond(cond), Then(then), Else(_else) {}
1169 virtual Value *Codegen();
1170};
1171
1172/// ForExprAST - Expression class for for/in.
1173class ForExprAST : public ExprAST {
1174 std::string VarName;
1175 ExprAST *Start, *End, *Step, *Body;
1176public:
1177 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
1178 ExprAST *step, ExprAST *body)
1179 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
1180 virtual Value *Codegen();
1181};
1182
1183/// VarExprAST - Expression class for var/in
1184class VarExprAST : public ExprAST {
1185 std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; VarNames;
1186 ExprAST *Body;
1187public:
1188 VarExprAST(const std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; &amp;varnames,
1189 ExprAST *body)
1190 : VarNames(varnames), Body(body) {}
1191
1192 virtual Value *Codegen();
1193};
1194
1195/// PrototypeAST - This class represents the "prototype" for a function,
1196/// which captures its argument names as well as if it is an operator.
1197class PrototypeAST {
1198 std::string Name;
1199 std::vector&lt;std::string&gt; Args;
1200 bool isOperator;
1201 unsigned Precedence; // Precedence if a binary op.
1202public:
1203 PrototypeAST(const std::string &amp;name, const std::vector&lt;std::string&gt; &amp;args,
1204 bool isoperator = false, unsigned prec = 0)
1205 : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {}
1206
1207 bool isUnaryOp() const { return isOperator &amp;&amp; Args.size() == 1; }
1208 bool isBinaryOp() const { return isOperator &amp;&amp; Args.size() == 2; }
1209
1210 char getOperatorName() const {
1211 assert(isUnaryOp() || isBinaryOp());
1212 return Name[Name.size()-1];
1213 }
1214
1215 unsigned getBinaryPrecedence() const { return Precedence; }
1216
1217 Function *Codegen();
1218
1219 void CreateArgumentAllocas(Function *F);
1220};
1221
1222/// FunctionAST - This class represents a function definition itself.
1223class FunctionAST {
1224 PrototypeAST *Proto;
1225 ExprAST *Body;
1226public:
1227 FunctionAST(PrototypeAST *proto, ExprAST *body)
1228 : Proto(proto), Body(body) {}
1229
1230 Function *Codegen();
1231};
1232
1233//===----------------------------------------------------------------------===//
1234// Parser
1235//===----------------------------------------------------------------------===//
1236
1237/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
1238/// token the parser it looking at. getNextToken reads another token from the
1239/// lexer and updates CurTok with its results.
1240static int CurTok;
1241static int getNextToken() {
1242 return CurTok = gettok();
1243}
1244
1245/// BinopPrecedence - This holds the precedence for each binary operator that is
1246/// defined.
1247static std::map&lt;char, int&gt; BinopPrecedence;
1248
1249/// GetTokPrecedence - Get the precedence of the pending binary operator token.
1250static int GetTokPrecedence() {
1251 if (!isascii(CurTok))
1252 return -1;
1253
1254 // Make sure it's a declared binop.
1255 int TokPrec = BinopPrecedence[CurTok];
1256 if (TokPrec &lt;= 0) return -1;
1257 return TokPrec;
1258}
1259
1260/// Error* - These are little helper functions for error handling.
1261ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
1262PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
1263FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
1264
1265static ExprAST *ParseExpression();
1266
1267/// identifierexpr
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1268/// ::= identifier
1269/// ::= identifier '(' expression* ')'
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1270static ExprAST *ParseIdentifierExpr() {
1271 std::string IdName = IdentifierStr;
1272
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1273 getNextToken(); // eat identifier.
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1274
1275 if (CurTok != '(') // Simple variable ref.
1276 return new VariableExprAST(IdName);
1277
1278 // Call.
1279 getNextToken(); // eat (
1280 std::vector&lt;ExprAST*&gt; Args;
1281 if (CurTok != ')') {
1282 while (1) {
1283 ExprAST *Arg = ParseExpression();
1284 if (!Arg) return 0;
1285 Args.push_back(Arg);
1286
1287 if (CurTok == ')') break;
1288
1289 if (CurTok != ',')
Chris Lattner6c4be9c2008-04-14 16:44:41 +0000[diff] [blame]1290 return Error("Expected ')' or ',' in argument list");
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1291 getNextToken();
1292 }
1293 }
1294
1295 // Eat the ')'.
1296 getNextToken();
1297
1298 return new CallExprAST(IdName, Args);
1299}
1300
1301/// numberexpr ::= number
1302static ExprAST *ParseNumberExpr() {
1303 ExprAST *Result = new NumberExprAST(NumVal);
1304 getNextToken(); // consume the number
1305 return Result;
1306}
1307
1308/// parenexpr ::= '(' expression ')'
1309static ExprAST *ParseParenExpr() {
1310 getNextToken(); // eat (.
1311 ExprAST *V = ParseExpression();
1312 if (!V) return 0;
1313
1314 if (CurTok != ')')
1315 return Error("expected ')'");
1316 getNextToken(); // eat ).
1317 return V;
1318}
1319
1320/// ifexpr ::= 'if' expression 'then' expression 'else' expression
1321static ExprAST *ParseIfExpr() {
1322 getNextToken(); // eat the if.
1323
1324 // condition.
1325 ExprAST *Cond = ParseExpression();
1326 if (!Cond) return 0;
1327
1328 if (CurTok != tok_then)
1329 return Error("expected then");
1330 getNextToken(); // eat the then
1331
1332 ExprAST *Then = ParseExpression();
1333 if (Then == 0) return 0;
1334
1335 if (CurTok != tok_else)
1336 return Error("expected else");
1337
1338 getNextToken();
1339
1340 ExprAST *Else = ParseExpression();
1341 if (!Else) return 0;
1342
1343 return new IfExprAST(Cond, Then, Else);
1344}
1345
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1346/// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1347static ExprAST *ParseForExpr() {
1348 getNextToken(); // eat the for.
1349
1350 if (CurTok != tok_identifier)
1351 return Error("expected identifier after for");
1352
1353 std::string IdName = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1354 getNextToken(); // eat identifier.
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1355
1356 if (CurTok != '=')
1357 return Error("expected '=' after for");
1358 getNextToken(); // eat '='.
1359
1360
1361 ExprAST *Start = ParseExpression();
1362 if (Start == 0) return 0;
1363 if (CurTok != ',')
1364 return Error("expected ',' after for start value");
1365 getNextToken();
1366
1367 ExprAST *End = ParseExpression();
1368 if (End == 0) return 0;
1369
1370 // The step value is optional.
1371 ExprAST *Step = 0;
1372 if (CurTok == ',') {
1373 getNextToken();
1374 Step = ParseExpression();
1375 if (Step == 0) return 0;
1376 }
1377
1378 if (CurTok != tok_in)
1379 return Error("expected 'in' after for");
1380 getNextToken(); // eat 'in'.
1381
1382 ExprAST *Body = ParseExpression();
1383 if (Body == 0) return 0;
1384
1385 return new ForExprAST(IdName, Start, End, Step, Body);
1386}
1387
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1388/// varexpr ::= 'var' identifier ('=' expression)?
1389// (',' identifier ('=' expression)?)* 'in' expression
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1390static ExprAST *ParseVarExpr() {
1391 getNextToken(); // eat the var.
1392
1393 std::vector&lt;std::pair&lt;std::string, ExprAST*&gt; &gt; VarNames;
1394
1395 // At least one variable name is required.
1396 if (CurTok != tok_identifier)
1397 return Error("expected identifier after var");
1398
1399 while (1) {
1400 std::string Name = IdentifierStr;
Chris Lattner20a0c802007-11-05 17:54:34 +0000[diff] [blame]1401 getNextToken(); // eat identifier.
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1402
1403 // Read the optional initializer.
1404 ExprAST *Init = 0;
1405 if (CurTok == '=') {
1406 getNextToken(); // eat the '='.
1407
1408 Init = ParseExpression();
1409 if (Init == 0) return 0;
1410 }
1411
1412 VarNames.push_back(std::make_pair(Name, Init));
1413
1414 // End of var list, exit loop.
1415 if (CurTok != ',') break;
1416 getNextToken(); // eat the ','.
1417
1418 if (CurTok != tok_identifier)
1419 return Error("expected identifier list after var");
1420 }
1421
1422 // At this point, we have to have 'in'.
1423 if (CurTok != tok_in)
1424 return Error("expected 'in' keyword after 'var'");
1425 getNextToken(); // eat 'in'.
1426
1427 ExprAST *Body = ParseExpression();
1428 if (Body == 0) return 0;
1429
1430 return new VarExprAST(VarNames, Body);
1431}
1432
1433
1434/// primary
1435/// ::= identifierexpr
1436/// ::= numberexpr
1437/// ::= parenexpr
1438/// ::= ifexpr
1439/// ::= forexpr
1440/// ::= varexpr
1441static ExprAST *ParsePrimary() {
1442 switch (CurTok) {
1443 default: return Error("unknown token when expecting an expression");
1444 case tok_identifier: return ParseIdentifierExpr();
1445 case tok_number: return ParseNumberExpr();
1446 case '(': return ParseParenExpr();
1447 case tok_if: return ParseIfExpr();
1448 case tok_for: return ParseForExpr();
1449 case tok_var: return ParseVarExpr();
1450 }
1451}
1452
1453/// unary
1454/// ::= primary
1455/// ::= '!' unary
1456static ExprAST *ParseUnary() {
1457 // If the current token is not an operator, it must be a primary expr.
1458 if (!isascii(CurTok) || CurTok == '(' || CurTok == ',')
1459 return ParsePrimary();
1460
1461 // If this is a unary operator, read it.
1462 int Opc = CurTok;
1463 getNextToken();
1464 if (ExprAST *Operand = ParseUnary())
1465 return new UnaryExprAST(Opc, Operand);
1466 return 0;
1467}
1468
1469/// binoprhs
1470/// ::= ('+' unary)*
1471static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
1472 // If this is a binop, find its precedence.
1473 while (1) {
1474 int TokPrec = GetTokPrecedence();
1475
1476 // If this is a binop that binds at least as tightly as the current binop,
1477 // consume it, otherwise we are done.
1478 if (TokPrec &lt; ExprPrec)
1479 return LHS;
1480
1481 // Okay, we know this is a binop.
1482 int BinOp = CurTok;
1483 getNextToken(); // eat binop
1484
1485 // Parse the unary expression after the binary operator.
1486 ExprAST *RHS = ParseUnary();
1487 if (!RHS) return 0;
1488
1489 // If BinOp binds less tightly with RHS than the operator after RHS, let
1490 // the pending operator take RHS as its LHS.
1491 int NextPrec = GetTokPrecedence();
1492 if (TokPrec &lt; NextPrec) {
1493 RHS = ParseBinOpRHS(TokPrec+1, RHS);
1494 if (RHS == 0) return 0;
1495 }
1496
1497 // Merge LHS/RHS.
1498 LHS = new BinaryExprAST(BinOp, LHS, RHS);
1499 }
1500}
1501
1502/// expression
1503/// ::= unary binoprhs
1504///
1505static ExprAST *ParseExpression() {
1506 ExprAST *LHS = ParseUnary();
1507 if (!LHS) return 0;
1508
1509 return ParseBinOpRHS(0, LHS);
1510}
1511
1512/// prototype
1513/// ::= id '(' id* ')'
1514/// ::= binary LETTER number? (id, id)
1515/// ::= unary LETTER (id)
1516static PrototypeAST *ParsePrototype() {
1517 std::string FnName;
1518
1519 int Kind = 0; // 0 = identifier, 1 = unary, 2 = binary.
1520 unsigned BinaryPrecedence = 30;
1521
1522 switch (CurTok) {
1523 default:
1524 return ErrorP("Expected function name in prototype");
1525 case tok_identifier:
1526 FnName = IdentifierStr;
1527 Kind = 0;
1528 getNextToken();
1529 break;
1530 case tok_unary:
1531 getNextToken();
1532 if (!isascii(CurTok))
1533 return ErrorP("Expected unary operator");
1534 FnName = "unary";
1535 FnName += (char)CurTok;
1536 Kind = 1;
1537 getNextToken();
1538 break;
1539 case tok_binary:
1540 getNextToken();
1541 if (!isascii(CurTok))
1542 return ErrorP("Expected binary operator");
1543 FnName = "binary";
1544 FnName += (char)CurTok;
1545 Kind = 2;
1546 getNextToken();
1547
1548 // Read the precedence if present.
1549 if (CurTok == tok_number) {
1550 if (NumVal &lt; 1 || NumVal &gt; 100)
1551 return ErrorP("Invalid precedecnce: must be 1..100");
1552 BinaryPrecedence = (unsigned)NumVal;
1553 getNextToken();
1554 }
1555 break;
1556 }
1557
1558 if (CurTok != '(')
1559 return ErrorP("Expected '(' in prototype");
1560
1561 std::vector&lt;std::string&gt; ArgNames;
1562 while (getNextToken() == tok_identifier)
1563 ArgNames.push_back(IdentifierStr);
1564 if (CurTok != ')')
1565 return ErrorP("Expected ')' in prototype");
1566
1567 // success.
1568 getNextToken(); // eat ')'.
1569
1570 // Verify right number of names for operator.
1571 if (Kind &amp;&amp; ArgNames.size() != Kind)
1572 return ErrorP("Invalid number of operands for operator");
1573
1574 return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);
1575}
1576
1577/// definition ::= 'def' prototype expression
1578static FunctionAST *ParseDefinition() {
1579 getNextToken(); // eat def.
1580 PrototypeAST *Proto = ParsePrototype();
1581 if (Proto == 0) return 0;
1582
1583 if (ExprAST *E = ParseExpression())
1584 return new FunctionAST(Proto, E);
1585 return 0;
1586}
1587
1588/// toplevelexpr ::= expression
1589static FunctionAST *ParseTopLevelExpr() {
1590 if (ExprAST *E = ParseExpression()) {
1591 // Make an anonymous proto.
1592 PrototypeAST *Proto = new PrototypeAST("", std::vector&lt;std::string&gt;());
1593 return new FunctionAST(Proto, E);
1594 }
1595 return 0;
1596}
1597
1598/// external ::= 'extern' prototype
1599static PrototypeAST *ParseExtern() {
1600 getNextToken(); // eat extern.
1601 return ParsePrototype();
1602}
1603
1604//===----------------------------------------------------------------------===//
1605// Code Generation
1606//===----------------------------------------------------------------------===//
1607
1608static Module *TheModule;
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame^]1609static IRBuilder&lt;&gt; Builder(getGlobalContext());
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1610static std::map&lt;std::string, AllocaInst*&gt; NamedValues;
1611static FunctionPassManager *TheFPM;
1612
1613Value *ErrorV(const char *Str) { Error(Str); return 0; }
1614
1615/// CreateEntryBlockAlloca - Create an alloca instruction in the entry block of
1616/// the function. This is used for mutable variables etc.
1617static AllocaInst *CreateEntryBlockAlloca(Function *TheFunction,
1618 const std::string &amp;VarName) {
Gabor Greifd6c1ed02009-03-11 19:51:07 +0000[diff] [blame]1619 IRBuilder&lt;&gt; TmpB(&amp;TheFunction-&gt;getEntryBlock(),
Duncan Sands89f6d882008-04-13 06:22:09 +0000[diff] [blame]1620 TheFunction-&gt;getEntryBlock().begin());
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1621 return TmpB.CreateAlloca(Type::DoubleTy, 0, VarName.c_str());
1622}
1623
1624
1625Value *NumberExprAST::Codegen() {
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]1626 return ConstantFP::get(APFloat(Val));
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1627}
1628
1629Value *VariableExprAST::Codegen() {
1630 // Look this variable up in the function.
1631 Value *V = NamedValues[Name];
1632 if (V == 0) return ErrorV("Unknown variable name");
1633
1634 // Load the value.
1635 return Builder.CreateLoad(V, Name.c_str());
1636}
1637
1638Value *UnaryExprAST::Codegen() {
1639 Value *OperandV = Operand-&gt;Codegen();
1640 if (OperandV == 0) return 0;
1641
1642 Function *F = TheModule-&gt;getFunction(std::string("unary")+Opcode);
1643 if (F == 0)
1644 return ErrorV("Unknown unary operator");
1645
1646 return Builder.CreateCall(F, OperandV, "unop");
1647}
1648
1649
1650Value *BinaryExprAST::Codegen() {
1651 // Special case '=' because we don't want to emit the LHS as an expression.
1652 if (Op == '=') {
1653 // Assignment requires the LHS to be an identifier.
1654 VariableExprAST *LHSE = dynamic_cast&lt;VariableExprAST*&gt;(LHS);
1655 if (!LHSE)
1656 return ErrorV("destination of '=' must be a variable");
1657 // Codegen the RHS.
1658 Value *Val = RHS-&gt;Codegen();
1659 if (Val == 0) return 0;
1660
1661 // Look up the name.
1662 Value *Variable = NamedValues[LHSE-&gt;getName()];
1663 if (Variable == 0) return ErrorV("Unknown variable name");
1664
1665 Builder.CreateStore(Val, Variable);
1666 return Val;
1667 }
1668
1669
1670 Value *L = LHS-&gt;Codegen();
1671 Value *R = RHS-&gt;Codegen();
1672 if (L == 0 || R == 0) return 0;
1673
1674 switch (Op) {
1675 case '+': return Builder.CreateAdd(L, R, "addtmp");
1676 case '-': return Builder.CreateSub(L, R, "subtmp");
1677 case '*': return Builder.CreateMul(L, R, "multmp");
1678 case '&lt;':
Chris Lattner71155212007-11-06 01:39:12 +0000[diff] [blame]1679 L = Builder.CreateFCmpULT(L, R, "cmptmp");
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1680 // Convert bool 0/1 to double 0.0 or 1.0
1681 return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp");
1682 default: break;
1683 }
1684
1685 // If it wasn't a builtin binary operator, it must be a user defined one. Emit
1686 // a call to it.
1687 Function *F = TheModule-&gt;getFunction(std::string("binary")+Op);
1688 assert(F &amp;&amp; "binary operator not found!");
1689
1690 Value *Ops[] = { L, R };
1691 return Builder.CreateCall(F, Ops, Ops+2, "binop");
1692}
1693
1694Value *CallExprAST::Codegen() {
1695 // Look up the name in the global module table.
1696 Function *CalleeF = TheModule-&gt;getFunction(Callee);
1697 if (CalleeF == 0)
1698 return ErrorV("Unknown function referenced");
1699
1700 // If argument mismatch error.
1701 if (CalleeF-&gt;arg_size() != Args.size())
1702 return ErrorV("Incorrect # arguments passed");
1703
1704 std::vector&lt;Value*&gt; ArgsV;
1705 for (unsigned i = 0, e = Args.size(); i != e; ++i) {
1706 ArgsV.push_back(Args[i]-&gt;Codegen());
1707 if (ArgsV.back() == 0) return 0;
1708 }
1709
1710 return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
1711}
1712
1713Value *IfExprAST::Codegen() {
1714 Value *CondV = Cond-&gt;Codegen();
1715 if (CondV == 0) return 0;
1716
1717 // Convert condition to a bool by comparing equal to 0.0.
1718 CondV = Builder.CreateFCmpONE(CondV,
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]1719 ConstantFP::get(APFloat(0.0)),
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1720 "ifcond");
1721
1722 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1723
1724 // Create blocks for the then and else cases. Insert the 'then' block at the
1725 // end of the function.
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1726 BasicBlock *ThenBB = BasicBlock::Create("then", TheFunction);
1727 BasicBlock *ElseBB = BasicBlock::Create("else");
1728 BasicBlock *MergeBB = BasicBlock::Create("ifcont");
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1729
1730 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
1731
1732 // Emit then value.
1733 Builder.SetInsertPoint(ThenBB);
1734
1735 Value *ThenV = Then-&gt;Codegen();
1736 if (ThenV == 0) return 0;
1737
1738 Builder.CreateBr(MergeBB);
1739 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
1740 ThenBB = Builder.GetInsertBlock();
1741
1742 // Emit else block.
1743 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
1744 Builder.SetInsertPoint(ElseBB);
1745
1746 Value *ElseV = Else-&gt;Codegen();
1747 if (ElseV == 0) return 0;
1748
1749 Builder.CreateBr(MergeBB);
1750 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
1751 ElseBB = Builder.GetInsertBlock();
1752
1753 // Emit merge block.
1754 TheFunction-&gt;getBasicBlockList().push_back(MergeBB);
1755 Builder.SetInsertPoint(MergeBB);
1756 PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
1757
1758 PN-&gt;addIncoming(ThenV, ThenBB);
1759 PN-&gt;addIncoming(ElseV, ElseBB);
1760 return PN;
1761}
1762
1763Value *ForExprAST::Codegen() {
1764 // Output this as:
1765 // var = alloca double
1766 // ...
1767 // start = startexpr
1768 // store start -&gt; var
1769 // goto loop
1770 // loop:
1771 // ...
1772 // bodyexpr
1773 // ...
1774 // loopend:
1775 // step = stepexpr
1776 // endcond = endexpr
1777 //
1778 // curvar = load var
1779 // nextvar = curvar + step
1780 // store nextvar -&gt; var
1781 // br endcond, loop, endloop
1782 // outloop:
1783
1784 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1785
1786 // Create an alloca for the variable in the entry block.
1787 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1788
1789 // Emit the start code first, without 'variable' in scope.
1790 Value *StartVal = Start-&gt;Codegen();
1791 if (StartVal == 0) return 0;
1792
1793 // Store the value into the alloca.
1794 Builder.CreateStore(StartVal, Alloca);
1795
1796 // Make the new basic block for the loop header, inserting after current
1797 // block.
1798 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1799 BasicBlock *LoopBB = BasicBlock::Create("loop", TheFunction);
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1800
1801 // Insert an explicit fall through from the current block to the LoopBB.
1802 Builder.CreateBr(LoopBB);
1803
1804 // Start insertion in LoopBB.
1805 Builder.SetInsertPoint(LoopBB);
1806
1807 // Within the loop, the variable is defined equal to the PHI node. If it
1808 // shadows an existing variable, we have to restore it, so save it now.
1809 AllocaInst *OldVal = NamedValues[VarName];
1810 NamedValues[VarName] = Alloca;
1811
1812 // Emit the body of the loop. This, like any other expr, can change the
1813 // current BB. Note that we ignore the value computed by the body, but don't
1814 // allow an error.
1815 if (Body-&gt;Codegen() == 0)
1816 return 0;
1817
1818 // Emit the step value.
1819 Value *StepVal;
1820 if (Step) {
1821 StepVal = Step-&gt;Codegen();
1822 if (StepVal == 0) return 0;
1823 } else {
1824 // If not specified, use 1.0.
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]1825 StepVal = ConstantFP::get(APFloat(1.0));
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1826 }
1827
1828 // Compute the end condition.
1829 Value *EndCond = End-&gt;Codegen();
1830 if (EndCond == 0) return EndCond;
1831
1832 // Reload, increment, and restore the alloca. This handles the case where
1833 // the body of the loop mutates the variable.
1834 Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
1835 Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
1836 Builder.CreateStore(NextVar, Alloca);
1837
1838 // Convert condition to a bool by comparing equal to 0.0.
1839 EndCond = Builder.CreateFCmpONE(EndCond,
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]1840 ConstantFP::get(APFloat(0.0)),
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1841 "loopcond");
1842
1843 // Create the "after loop" block and insert it.
1844 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1845 BasicBlock *AfterBB = BasicBlock::Create("afterloop", TheFunction);
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1846
1847 // Insert the conditional branch into the end of LoopEndBB.
1848 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
1849
1850 // Any new code will be inserted in AfterBB.
1851 Builder.SetInsertPoint(AfterBB);
1852
1853 // Restore the unshadowed variable.
1854 if (OldVal)
1855 NamedValues[VarName] = OldVal;
1856 else
1857 NamedValues.erase(VarName);
1858
1859
1860 // for expr always returns 0.0.
1861 return Constant::getNullValue(Type::DoubleTy);
1862}
1863
1864Value *VarExprAST::Codegen() {
1865 std::vector&lt;AllocaInst *&gt; OldBindings;
1866
1867 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
1868
1869 // Register all variables and emit their initializer.
1870 for (unsigned i = 0, e = VarNames.size(); i != e; ++i) {
1871 const std::string &amp;VarName = VarNames[i].first;
1872 ExprAST *Init = VarNames[i].second;
1873
1874 // Emit the initializer before adding the variable to scope, this prevents
1875 // the initializer from referencing the variable itself, and permits stuff
1876 // like this:
1877 // var a = 1 in
1878 // var a = a in ... # refers to outer 'a'.
1879 Value *InitVal;
1880 if (Init) {
1881 InitVal = Init-&gt;Codegen();
1882 if (InitVal == 0) return 0;
1883 } else { // If not specified, use 0.0.
Gabor Greif5934adf2008-06-10 01:52:17 +0000[diff] [blame]1884 InitVal = ConstantFP::get(APFloat(0.0));
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1885 }
1886
1887 AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName);
1888 Builder.CreateStore(InitVal, Alloca);
1889
1890 // Remember the old variable binding so that we can restore the binding when
1891 // we unrecurse.
1892 OldBindings.push_back(NamedValues[VarName]);
1893
1894 // Remember this binding.
1895 NamedValues[VarName] = Alloca;
1896 }
1897
1898 // Codegen the body, now that all vars are in scope.
1899 Value *BodyVal = Body-&gt;Codegen();
1900 if (BodyVal == 0) return 0;
1901
1902 // Pop all our variables from scope.
1903 for (unsigned i = 0, e = VarNames.size(); i != e; ++i)
1904 NamedValues[VarNames[i].first] = OldBindings[i];
1905
1906 // Return the body computation.
1907 return BodyVal;
1908}
1909
1910
1911Function *PrototypeAST::Codegen() {
1912 // Make the function type: double(double,double) etc.
1913 std::vector&lt;const Type*&gt; Doubles(Args.size(), Type::DoubleTy);
1914 FunctionType *FT = FunctionType::get(Type::DoubleTy, Doubles, false);
1915
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1916 Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1917
1918 // If F conflicted, there was already something named 'Name'. If it has a
1919 // body, don't allow redefinition or reextern.
1920 if (F-&gt;getName() != Name) {
1921 // Delete the one we just made and get the existing one.
1922 F-&gt;eraseFromParent();
1923 F = TheModule-&gt;getFunction(Name);
1924
1925 // If F already has a body, reject this.
1926 if (!F-&gt;empty()) {
1927 ErrorF("redefinition of function");
1928 return 0;
1929 }
1930
1931 // If F took a different number of args, reject.
1932 if (F-&gt;arg_size() != Args.size()) {
1933 ErrorF("redefinition of function with different # args");
1934 return 0;
1935 }
1936 }
1937
1938 // Set names for all arguments.
1939 unsigned Idx = 0;
1940 for (Function::arg_iterator AI = F-&gt;arg_begin(); Idx != Args.size();
1941 ++AI, ++Idx)
1942 AI-&gt;setName(Args[Idx]);
1943
1944 return F;
1945}
1946
1947/// CreateArgumentAllocas - Create an alloca for each argument and register the
1948/// argument in the symbol table so that references to it will succeed.
1949void PrototypeAST::CreateArgumentAllocas(Function *F) {
1950 Function::arg_iterator AI = F-&gt;arg_begin();
1951 for (unsigned Idx = 0, e = Args.size(); Idx != e; ++Idx, ++AI) {
1952 // Create an alloca for this variable.
1953 AllocaInst *Alloca = CreateEntryBlockAlloca(F, Args[Idx]);
1954
1955 // Store the initial value into the alloca.
1956 Builder.CreateStore(AI, Alloca);
1957
1958 // Add arguments to variable symbol table.
1959 NamedValues[Args[Idx]] = Alloca;
1960 }
1961}
1962
1963
1964Function *FunctionAST::Codegen() {
1965 NamedValues.clear();
1966
1967 Function *TheFunction = Proto-&gt;Codegen();
1968 if (TheFunction == 0)
1969 return 0;
1970
1971 // If this is an operator, install it.
1972 if (Proto-&gt;isBinaryOp())
1973 BinopPrecedence[Proto-&gt;getOperatorName()] = Proto-&gt;getBinaryPrecedence();
1974
1975 // Create a new basic block to start insertion into.
Gabor Greifdf7d2b42008-04-19 22:25:09 +0000[diff] [blame]1976 BasicBlock *BB = BasicBlock::Create("entry", TheFunction);
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]1977 Builder.SetInsertPoint(BB);
1978
1979 // Add all arguments to the symbol table and create their allocas.
1980 Proto-&gt;CreateArgumentAllocas(TheFunction);
1981
1982 if (Value *RetVal = Body-&gt;Codegen()) {
1983 // Finish off the function.
1984 Builder.CreateRet(RetVal);
1985
1986 // Validate the generated code, checking for consistency.
1987 verifyFunction(*TheFunction);
1988
1989 // Optimize the function.
1990 TheFPM-&gt;run(*TheFunction);
1991
1992 return TheFunction;
1993 }
1994
1995 // Error reading body, remove function.
1996 TheFunction-&gt;eraseFromParent();
1997
1998 if (Proto-&gt;isBinaryOp())
1999 BinopPrecedence.erase(Proto-&gt;getOperatorName());
2000 return 0;
2001}
2002
2003//===----------------------------------------------------------------------===//
2004// Top-Level parsing and JIT Driver
2005//===----------------------------------------------------------------------===//
2006
2007static ExecutionEngine *TheExecutionEngine;
2008
2009static void HandleDefinition() {
2010 if (FunctionAST *F = ParseDefinition()) {
2011 if (Function *LF = F-&gt;Codegen()) {
2012 fprintf(stderr, "Read function definition:");
2013 LF-&gt;dump();
2014 }
2015 } else {
2016 // Skip token for error recovery.
2017 getNextToken();
2018 }
2019}
2020
2021static void HandleExtern() {
2022 if (PrototypeAST *P = ParseExtern()) {
2023 if (Function *F = P-&gt;Codegen()) {
2024 fprintf(stderr, "Read extern: ");
2025 F-&gt;dump();
2026 }
2027 } else {
2028 // Skip token for error recovery.
2029 getNextToken();
2030 }
2031}
2032
2033static void HandleTopLevelExpression() {
2034 // Evaluate a top level expression into an anonymous function.
2035 if (FunctionAST *F = ParseTopLevelExpr()) {
2036 if (Function *LF = F-&gt;Codegen()) {
2037 // JIT the function, returning a function pointer.
2038 void *FPtr = TheExecutionEngine-&gt;getPointerToFunction(LF);
2039
2040 // Cast it to the right type (takes no arguments, returns a double) so we
2041 // can call it as a native function.
2042 double (*FP)() = (double (*)())FPtr;
2043 fprintf(stderr, "Evaluated to %f\n", FP());
2044 }
2045 } else {
2046 // Skip token for error recovery.
2047 getNextToken();
2048 }
2049}
2050
2051/// top ::= definition | external | expression | ';'
2052static void MainLoop() {
2053 while (1) {
2054 fprintf(stderr, "ready&gt; ");
2055 switch (CurTok) {
2056 case tok_eof: return;
2057 case ';': getNextToken(); break; // ignore top level semicolons.
2058 case tok_def: HandleDefinition(); break;
2059 case tok_extern: HandleExtern(); break;
2060 default: HandleTopLevelExpression(); break;
2061 }
2062 }
2063}
2064
2065
2066
2067//===----------------------------------------------------------------------===//
2068// "Library" functions that can be "extern'd" from user code.
2069//===----------------------------------------------------------------------===//
2070
2071/// putchard - putchar that takes a double and returns 0.
2072extern "C"
2073double putchard(double X) {
2074 putchar((char)X);
2075 return 0;
2076}
2077
2078/// printd - printf that takes a double prints it as "%f\n", returning 0.
2079extern "C"
2080double printd(double X) {
2081 printf("%f\n", X);
2082 return 0;
2083}
2084
2085//===----------------------------------------------------------------------===//
2086// Main driver code.
2087//===----------------------------------------------------------------------===//
2088
2089int main() {
2090 // Install standard binary operators.
2091 // 1 is lowest precedence.
2092 BinopPrecedence['='] = 2;
2093 BinopPrecedence['&lt;'] = 10;
2094 BinopPrecedence['+'] = 20;
2095 BinopPrecedence['-'] = 20;
2096 BinopPrecedence['*'] = 40; // highest.
2097
2098 // Prime the first token.
2099 fprintf(stderr, "ready&gt; ");
2100 getNextToken();
2101
2102 // Make the module, which holds all the code.
Owen Andersond1fbd142009-07-08 20:50:47 +0000[diff] [blame^]2103 TheModule = new Module("my cool jit", getGlobalContext());
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]2104
2105 // Create the JIT.
2106 TheExecutionEngine = ExecutionEngine::create(TheModule);
2107
2108 {
2109 ExistingModuleProvider OurModuleProvider(TheModule);
2110 FunctionPassManager OurFPM(&amp;OurModuleProvider);
2111
2112 // Set up the optimizer pipeline. Start with registering info about how the
2113 // target lays out data structures.
2114 OurFPM.add(new TargetData(*TheExecutionEngine-&gt;getTargetData()));
2115 // Promote allocas to registers.
2116 OurFPM.add(createPromoteMemoryToRegisterPass());
2117 // Do simple "peephole" optimizations and bit-twiddling optzns.
2118 OurFPM.add(createInstructionCombiningPass());
2119 // Reassociate expressions.
2120 OurFPM.add(createReassociatePass());
2121 // Eliminate Common SubExpressions.
2122 OurFPM.add(createGVNPass());
2123 // Simplify the control flow graph (deleting unreachable blocks, etc).
2124 OurFPM.add(createCFGSimplificationPass());
2125
2126 // Set the global so the code gen can use this.
2127 TheFPM = &amp;OurFPM;
2128
2129 // Run the main "interpreter loop" now.
2130 MainLoop();
2131
2132 TheFPM = 0;
Chris Lattner515686b2008-02-05 06:18:42 +0000[diff] [blame]2133
2134 // Print out all of the generated code.
2135 TheModule-&gt;dump();
2136
2137 } // Free module provider (and thus the module) and pass manager.
2138
Chris Lattner62a709d2007-11-05 00:23:57 +0000[diff] [blame]2139 return 0;
2140}
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]2141</pre>
2142</div>
2143
Chris Lattner729eb142008-02-10 19:11:04 +0000[diff] [blame]2144<a href="LangImpl8.html">Next: Conclusion and other useful LLVM tidbits</a>
Chris Lattner00c992d2007-11-03 08:55:29 +0000[diff] [blame]2145</div>
2146
2147<!-- *********************************************************************** -->
2148<hr>
2149<address>
2150 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
2151 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
2152 <a href="http://validator.w3.org/check/referer"><img
2153 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
2154
2155 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
2156 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
2157 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
2158</address>
2159</body>
2160</html>