1905 lines
62 KiB
HTML
1905 lines
62 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
|
|
"http://www.w3.org/TR/html4/strict.dtd">
|
|
|
|
<html>
|
|
<head>
|
|
<title>Kaleidoscope: Extending the Language: Mutable Variables / SSA
|
|
construction</title>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
|
<meta name="author" content="Chris Lattner">
|
|
<meta name="author" content="Max Shawabkeh">
|
|
<link rel="stylesheet"
|
|
href="http://www.llvm.org/docs/llvm.css"
|
|
type="text/css">
|
|
</head>
|
|
|
|
<body>
|
|
|
|
<div class="doc_title">Kaleidoscope: Extending the Language: Mutable
|
|
Variables</div>
|
|
|
|
<ul>
|
|
<li>
|
|
<a href="http://www.llvm.org/docs/tutorial/index.html">
|
|
Up to Tutorial Index
|
|
</a>
|
|
</li>
|
|
<li>Chapter 7
|
|
<ol>
|
|
<li><a href="#intro">Chapter 7 Introduction</a></li>
|
|
<li><a href="#why">Why is this a hard problem?</a></li>
|
|
<li><a href="#memory">Memory in LLVM</a></li>
|
|
<li><a href="#kalvars">Mutable Variables in Kaleidoscope</a></li>
|
|
<li><a href="#adjustments">Adjusting Existing Variables for
|
|
Mutation</a></li>
|
|
<li><a href="#assignment">New Assignment Operator</a></li>
|
|
<li><a href="#localvars">User-defined Local Variables</a></li>
|
|
<li><a href="#code">Full Code Listing</a></li>
|
|
</ol>
|
|
</li>
|
|
<li><a href="PythonLangImpl8.html">Chapter 8</a>: Conclusion and other useful
|
|
LLVM tidbits</li>
|
|
</ul>
|
|
|
|
<div class="doc_author">
|
|
<p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>
|
|
and <a href="http://max99x.com">Max Shawabkeh</a>
|
|
</p>
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="intro">Chapter 7 Introduction</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>Welcome to Chapter 7 of the
|
|
"<a href="http://www.llvm.org/docs/tutorial/index.html">Implementing a language
|
|
with LLVM</a>" tutorial. In chapters 1 through 6, we've built a very
|
|
respectable, albeit simple, <a
|
|
href="http://en.wikipedia.org/wiki/Functional_programming">functional
|
|
programming language</a>. In our journey, we learned some parsing techniques,
|
|
how to build and represent an AST, how to build LLVM IR, and how to optimize
|
|
the resultant code as well as JIT compile it.</p>
|
|
|
|
<p>While Kaleidoscope is interesting as a functional language, the fact that it
|
|
is functional makes it "too easy" to generate LLVM IR for it. In particular, a
|
|
functional language makes it very easy to build LLVM IR directly in <a
|
|
href="http://en.wikipedia.org/wiki/Static_single_assignment_form">SSA form</a>.
|
|
Since LLVM requires that the input code be in SSA form, this is a very nice
|
|
property and it is often unclear to newcomers how to generate code for an
|
|
imperative language with mutable variables.</p>
|
|
|
|
<p>The short (and happy) summary of this chapter is that there is no need for
|
|
your front-end to build SSA form: LLVM provides highly tuned and well tested
|
|
support for this, though the way it works is a bit unexpected for some.</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="why">Why is this a hard problem?</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>
|
|
To understand why mutable variables cause complexities in SSA construction,
|
|
consider this extremely simple C example:
|
|
</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
int G, H;
|
|
int test(_Bool Condition) {
|
|
int X;
|
|
if (Condition)
|
|
X = G;
|
|
else
|
|
X = H;
|
|
return X;
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>In this case, we have the variable "X", whose value depends on the path
|
|
executed in the program. Because there are two different possible values for X
|
|
before the return instruction, a PHI node is inserted to merge the two values.
|
|
The LLVM IR that we want for this example looks like this:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
@G = weak global i32 0 ; type of @G is i32*
|
|
@H = weak global i32 0 ; type of @H is i32*
|
|
|
|
define i32 @test(i1 %Condition) {
|
|
entry:
|
|
br i1 %Condition, label %cond_true, label %cond_false
|
|
|
|
cond_true:
|
|
%X.0 = load i32* @G
|
|
br label %cond_next
|
|
|
|
cond_false:
|
|
%X.1 = load i32* @H
|
|
br label %cond_next
|
|
|
|
cond_next:
|
|
%X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
|
|
ret i32 %X.2
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>In this example, the loads from the G and H global variables are explicit in
|
|
the LLVM IR, and they live in the then/else branches of the if statement
|
|
(cond_true/cond_false). In order to merge the incoming values, the X.2 phi node
|
|
in the cond_next block selects the right value to use based on where control
|
|
flow is coming from: if control flow comes from the cond_false block, X.2 gets
|
|
the value of X.1. Alternatively, if control flow comes from cond_true, it gets
|
|
the value of X.0. The intent of this chapter is not to explain the details of
|
|
SSA form. For more information, see one of the many <a
|
|
href="http://en.wikipedia.org/wiki/Static_single_assignment_form">online
|
|
references</a>.</p>
|
|
|
|
<p>The question for this article is "who places the phi nodes when lowering
|
|
assignments to mutable variables?". The issue here is that LLVM
|
|
<em>requires</em> that its IR be in SSA form: there is no "non-ssa" mode for it.
|
|
However, SSA construction requires non-trivial algorithms and data structures,
|
|
so it is inconvenient and wasteful for every front-end to have to reproduce this
|
|
logic.</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="memory">Memory in LLVM</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>The 'trick' here is that while LLVM does require all register values to be
|
|
in SSA form, it does not require (or permit) memory objects to be in SSA form.
|
|
In the example above, note that the loads from G and H are direct accesses to
|
|
G and H: they are not renamed or versioned. This differs from some other
|
|
compiler systems, which do try to version memory objects. In LLVM, instead of
|
|
encoding dataflow analysis of memory into the LLVM IR, it is handled with <a
|
|
href="http://www.llvm.org/docs/WritingAnLLVMPass.html">Analysis Passes</a>
|
|
which are computed on demand.</p>
|
|
|
|
<p>
|
|
With this in mind, the high-level idea is that we want to make a stack variable
|
|
(which lives in memory, because it is on the stack) for each mutable object in
|
|
a function. To take advantage of this trick, we need to talk about how LLVM
|
|
represents stack variables.
|
|
</p>
|
|
|
|
<p>In LLVM, all memory accesses are explicit with load/store instructions, and
|
|
it is carefully designed not to have (or need) an "address-of" operator.
|
|
Notice how the type of the @G/@H global variables is actually "i32*" even though
|
|
the variable is defined as "i32". What this means is that @G defines
|
|
<em>space</em> for an i32 in the global data area, but its <em>name</em>
|
|
actually refers to the address for that space. Stack variables work the same
|
|
way, except that instead of being declared with global variable definitions,
|
|
they are declared with the
|
|
<a href="http://www.llvm.org/docs/LangRef.html#i_alloca">LLVM alloca
|
|
instruction</a>:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
define i32 @example() {
|
|
entry:
|
|
%X = alloca i32 ; type of %X is i32*.
|
|
...
|
|
%tmp = load i32* %X ; load the stack value %X from the stack.
|
|
%tmp2 = add i32 %tmp, 1 ; increment it
|
|
store i32 %tmp2, i32* %X ; store it back
|
|
...
|
|
</pre>
|
|
</div>
|
|
|
|
<p>This code shows an example of how you can declare and manipulate a stack
|
|
variable in the LLVM IR. Stack memory allocated with the alloca instruction is
|
|
fully general: you can pass the address of the stack slot to functions, you can
|
|
store it in other variables, etc. In our example above, we could rewrite the
|
|
example to use the alloca technique to avoid using a PHI node:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
@G = weak global i32 0 ; type of @G is i32*
|
|
@H = weak global i32 0 ; type of @H is i32*
|
|
|
|
define i32 @test(i1 %Condition) {
|
|
entry:
|
|
%X = alloca i32 ; type of %X is i32*.
|
|
br i1 %Condition, label %cond_true, label %cond_false
|
|
|
|
cond_true:
|
|
%X.0 = load i32* @G
|
|
store i32 %X.0, i32* %X ; Update X
|
|
br label %cond_next
|
|
|
|
cond_false:
|
|
%X.1 = load i32* @H
|
|
store i32 %X.1, i32* %X ; Update X
|
|
br label %cond_next
|
|
|
|
cond_next:
|
|
%X.2 = load i32* %X ; Read X
|
|
ret i32 %X.2
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>With this, we have discovered a way to handle arbitrary mutable variables
|
|
without the need to create Phi nodes at all:</p>
|
|
|
|
<ol>
|
|
<li>Each mutable variable becomes a stack allocation.</li>
|
|
<li>Each read of the variable becomes a load from the stack.</li>
|
|
<li>Each update of the variable becomes a store to the stack.</li>
|
|
<li>Taking the address of a variable just uses the stack address directly.</li>
|
|
</ol>
|
|
|
|
<p>While this solution has solved our immediate problem, it introduced another
|
|
one: we have now apparently introduced a lot of stack traffic for very simple
|
|
and common operations, a major performance problem. Fortunately for us, the
|
|
LLVM optimizer has a highly-tuned optimization pass named "mem2reg" that handles
|
|
this case, promoting allocas like this into SSA registers, inserting Phi nodes
|
|
as appropriate. If you run this example through the pass, for example, you'll
|
|
get:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
$ <b>llvm-as < example.ll | opt -mem2reg | llvm-dis</b>
|
|
@G = weak global i32 0
|
|
@H = weak global i32 0
|
|
|
|
define i32 @test(i1 %Condition) {
|
|
entry:
|
|
br i1 %Condition, label %cond_true, label %cond_false
|
|
|
|
cond_true:
|
|
%X.0 = load i32* @G
|
|
br label %cond_next
|
|
|
|
cond_false:
|
|
%X.1 = load i32* @H
|
|
br label %cond_next
|
|
|
|
cond_next:
|
|
%X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
|
|
ret i32 %X.01
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>The mem2reg pass implements the standard "iterated dominance frontier"
|
|
algorithm for constructing SSA form and has a number of optimizations that speed
|
|
up (very common) degenerate cases. The mem2reg optimization pass is the answer
|
|
to dealing with mutable variables, and we highly recommend that you depend on
|
|
it. Note that mem2reg only works on variables in certain circumstances:</p>
|
|
|
|
<ol>
|
|
<li>mem2reg is alloca-driven: it looks for allocas and if it can handle them, it
|
|
promotes them. It does not apply to global variables or heap allocations.</li>
|
|
|
|
<li>mem2reg only looks for alloca instructions in the entry block of the
|
|
function. Being in the entry block guarantees that the alloca is only executed
|
|
once, which makes analysis simpler.</li>
|
|
|
|
<li>mem2reg only promotes allocas whose uses are direct loads and stores. If
|
|
the address of the stack object is passed to a function, or if any funny pointer
|
|
arithmetic is involved, the alloca will not be promoted.</li>
|
|
|
|
<li>mem2reg only works on allocas of <a
|
|
href="http://www.llvm.org/docs/LangRef.html#t_classifications">first class</a>
|
|
values (such as pointers, scalars and vectors), and only if the array size
|
|
of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of
|
|
promoting structs or arrays to registers. Note that the "scalarrepl" pass is
|
|
more powerful and can promote structs, "unions", and arrays in many cases.</li>
|
|
|
|
</ol>
|
|
|
|
<p>
|
|
All of these properties are easy to satisfy for most imperative languages, and
|
|
we'll illustrate it below with Kaleidoscope. The final question you may be
|
|
asking is: should I bother with this nonsense for my front-end? Wouldn't it be
|
|
better if I just did SSA construction directly, avoiding use of the mem2reg
|
|
optimization pass? In short, we strongly recommend that you use this technique
|
|
for building SSA form, unless there is an extremely good reason not to. Using
|
|
this technique is:</p>
|
|
|
|
<ul>
|
|
<li>Proven and well tested: llvm-gcc and clang both use this technique for local
|
|
mutable variables. As such, the most common clients of LLVM are using this to
|
|
handle a bulk of their variables. You can be sure that bugs are found fast and
|
|
fixed early.</li>
|
|
|
|
<li>Extremely Fast: mem2reg has a number of special cases that make it fast in
|
|
common cases as well as fully general. For example, it has fast-paths for
|
|
variables that are only used in a single block, variables that only have one
|
|
assignment point, good heuristics to avoid insertion of unneeded phi nodes, etc.
|
|
</li>
|
|
|
|
<li>Needed for debug info generation:
|
|
<a href="http://www.llvm.org/docs/SourceLevelDebugging.html">Debug information
|
|
in LLVM</a> relies on having the address of the variable exposed so that debug
|
|
info can be attached to it. This technique dovetails very naturally with this
|
|
style of debug info.</li>
|
|
</ul>
|
|
|
|
<p>If nothing else, this makes it much easier to get your front-end up and
|
|
running, and is very simple to implement. Lets extend Kaleidoscope with mutable
|
|
variables now!
|
|
</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="kalvars">Mutable Variables in
|
|
Kaleidoscope</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>Now that we know the sort of problem we want to tackle, lets see what this
|
|
looks like in the context of our little Kaleidoscope language. We're going to
|
|
add two features:</p>
|
|
|
|
<ol>
|
|
<li>The ability to mutate variables with the '=' operator.</li>
|
|
<li>The ability to define new variables.</li>
|
|
</ol>
|
|
|
|
<p>While the first item is really what this is about, we only have variables
|
|
for incoming arguments as well as for induction variables, and redefining those
|
|
only goes so far :). Also, the ability to define new variables is a
|
|
useful thing regardless of whether you will be mutating them. Here's a
|
|
motivating example that shows how we could use these:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Define ':' for sequencing: as a low-precedence operator that ignores operands
|
|
# and just returns the RHS.
|
|
def binary : 1 (x y) y;
|
|
|
|
# Recursive fib, we could do this before.
|
|
def fib(x)
|
|
if (x < 3) then
|
|
1
|
|
else
|
|
fib(x-1) + fib(x-2)
|
|
|
|
# Iterative fib.
|
|
def fibi(x)
|
|
<b>var a = 1, b = 1, c in</b>
|
|
(for i = 3, i < x in
|
|
<b>c = a + b</b> :
|
|
<b>a = b</b> :
|
|
<b>b = c</b>) :
|
|
b
|
|
|
|
# Call it.
|
|
fibi(10)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>
|
|
In order to mutate variables, we have to change our existing variables to use
|
|
the "alloca trick". Once we have that, we'll add our new operator, then extend
|
|
Kaleidoscope to support new variable definitions.
|
|
</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="adjustments">Adjusting Existing Variables for
|
|
Mutation</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>
|
|
The symbol table in Kaleidoscope is managed at code generation time by the
|
|
<tt>g_named_values</tt> map. This map currently keeps track of the LLVM
|
|
"Value" that holds the double value for the named variable. In order to support
|
|
mutation, we need to change this slightly, so that it holds the <em>memory
|
|
location</em> of the variable in question. Note that this change is a
|
|
refactoring: it changes the structure of the code, but does not (by itself)
|
|
change the behavior of the compiler. All of these changes are isolated in the
|
|
Kaleidoscope code generator.</p>
|
|
|
|
<p>
|
|
At this point in Kaleidoscope's development, it only supports variables for two
|
|
things: incoming arguments to functions and the induction variable of 'for'
|
|
loops. For consistency, we'll allow mutation of these variables in addition to
|
|
other user-defined variables. This means that these will both need memory
|
|
locations.
|
|
</p>
|
|
|
|
<p>To start our transformation of Kaleidoscope, we will need to create the
|
|
allocas that we will store in <tt>g_named_values</tt>. We'll use a helper
|
|
function that ensures that the allocas are created in the entry block of the
|
|
function:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Creates an alloca instruction in the entry block of the function. This is used
|
|
# for mutable variables.
|
|
def CreateEntryBlockAlloca(function, var_name):
|
|
entry = function.get_entry_basic_block()
|
|
builder = Builder.new(entry)
|
|
builder.position_at_beginning(entry)
|
|
return builder.alloca(Type.double(), var_name)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>This code creates a temporary <tt>llvm.core.Builder</tt> that is pointing at
|
|
the first instruction of the entry block. It then creates an alloca with the
|
|
expected name and returns it. Because all values in Kaleidoscope are doubles,
|
|
there is no need to pass in a type to use.</p>
|
|
|
|
<p>With this in place, the first functionality change we want to make is to
|
|
variable references. In our new scheme, variables live on the stack, so code
|
|
generating a reference to them actually needs to produce a load from the stack
|
|
slot:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
def CodeGen(self):
|
|
if self.name in g_named_values:
|
|
return g_llvm_builder.load(g_named_values[self.name], self.name)
|
|
else:
|
|
raise RuntimeError('Unknown variable name: ' + self.name)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>As you can see, this is pretty straightforward. Now we need to update the
|
|
things that define the variables to set up the alloca. We'll start with
|
|
<tt>ForExpressionNode.CodeGen</tt> (see the <a href="#code">full code
|
|
listing</a> for the unabridged code):</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
def CodeGen(self):
|
|
function = g_llvm_builder.basic_block.function
|
|
|
|
<b># Create an alloca for the variable in the entry block.
|
|
alloca = CreateEntryBlockAlloca(function, self.loop_variable)</b>
|
|
|
|
# Emit the start code first, without 'variable' in scope.
|
|
start_value = self.start.CodeGen()
|
|
|
|
<b># Store the value into the alloca.
|
|
g_llvm_builder.store(start_value, alloca)</b>
|
|
...
|
|
<b># Compute the end condition.
|
|
end_condition = self.end.CodeGen()
|
|
|
|
# Reload, increment, and restore the alloca. This handles the case where
|
|
# the body of the loop mutates the variable.
|
|
cur_value = g_llvm_builder.load(alloca, self.loop_variable)
|
|
next_value = g_llvm_builder.fadd(cur_value, step_value, 'nextvar')
|
|
g_llvm_builder.store(next_value, alloca)</b>
|
|
|
|
# Convert condition to a bool by comparing equal to 0.0.
|
|
end_condition_bool = g_llvm_builder.fcmp(
|
|
FCMP_ONE, end_condition, Constant.real(Type.double(), 0), 'loopcond')
|
|
...
|
|
</pre>
|
|
</div>
|
|
|
|
<p>This code is virtually identical to the code <a
|
|
href="PythonLangImpl5.html#forcodegen">before we allowed mutable variables</a>.
|
|
The big difference is that we no longer have to construct a PHI node, and we use
|
|
load/store to access the variable as needed.</p>
|
|
|
|
<p>To support mutable argument variables, we need to also make allocas for them.
|
|
The code for this is also pretty simple:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
class PrototypeNode(object):
|
|
...
|
|
# Create an alloca for each argument and register the argument in the symbol
|
|
# table so that references to it will succeed.
|
|
def CreateArgumentAllocas(self, function):
|
|
for arg_name, arg in zip(self.args, function.args):
|
|
alloca = CreateEntryBlockAlloca(function, arg_name)
|
|
g_llvm_builder.store(arg, alloca)
|
|
g_named_values[arg_name] = alloca
|
|
</pre>
|
|
</div>
|
|
|
|
<p>For each argument, we make an alloca, store the input value to the function
|
|
into the alloca, and register the alloca as the memory location for the
|
|
argument. This method gets invoked by <tt>FunctionNode.CodeGen</tt> right after
|
|
it sets up the entry block for the function.</p>
|
|
|
|
<p>The final missing piece is adding the mem2reg pass, which allows us to get
|
|
good codegen once again:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
from llvm.passes import (<b>PASS_MEM2REG</b>,
|
|
PASS_INSTCOMBINE,
|
|
PASS_REASSOCIATE,
|
|
PASS_GVN,
|
|
PASS_SIMPLIFYCFG)
|
|
...
|
|
def main():
|
|
# Set up the optimizer pipeline. Start with registering info about how the
|
|
# target lays out data structures.
|
|
g_llvm_pass_manager.add(g_llvm_executor.target_data)
|
|
<b># Promote allocas to registers.
|
|
g_llvm_pass_manager.add(PASS_MEM2REG)</b>
|
|
# Do simple "peephole" optimizations and bit-twiddling optzns.
|
|
g_llvm_pass_manager.add(PASS_INSTCOMBINE)
|
|
# Reassociate expressions.
|
|
g_llvm_pass_manager.add(PASS_REASSOCIATE)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>It is interesting to see what the code looks like before and after the
|
|
mem2reg optimization runs. For example, this is the before/after code for our
|
|
recursive fib function. Before the optimization:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
define double @fib(double %x) {
|
|
entry:
|
|
<b>%x1 = alloca double
|
|
store double %x, double* %x1
|
|
%x2 = load double* %x1</b>
|
|
%cmptmp = fcmp ult double %x2, 3.000000e+00
|
|
%booltmp = uitofp i1 %cmptmp to double
|
|
%ifcond = fcmp one double %booltmp, 0.000000e+00
|
|
br i1 %ifcond, label %then, label %else
|
|
|
|
then: ; preds = %entry
|
|
br label %ifcont
|
|
|
|
else: ; preds = %entry
|
|
<b>%x3 = load double* %x1</b>
|
|
%subtmp = fsub double %x3, 1.000000e+00
|
|
%calltmp = call double @fib(double %subtmp)
|
|
<b>%x4 = load double* %x1</b>
|
|
%subtmp5 = fsub double %x4, 2.000000e+00
|
|
%calltmp6 = call double @fib(double %subtmp5)
|
|
%addtmp = fadd double %calltmp, %calltmp6
|
|
br label %ifcont
|
|
|
|
ifcont: ; preds = %else, %then
|
|
%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
|
|
ret double %iftmp
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Here there is only one variable (x, the input argument) but you can still
|
|
see the extremely simple-minded code generation strategy we are using. In the
|
|
entry block, an alloca is created, and the initial input value is stored into
|
|
it. Each reference to the variable does a reload from the stack. Also, note
|
|
that we didn't modify the if/then/else expression, so it still inserts a PHI
|
|
node. While we could make an alloca for it, it is actually easier to create a
|
|
PHI node for it, so we still just make the PHI.</p>
|
|
|
|
<p>Here is the code after the mem2reg pass runs:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
define double @fib(double %x) {
|
|
entry:
|
|
%cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
|
|
%booltmp = uitofp i1 %cmptmp to double
|
|
%ifcond = fcmp one double %booltmp, 0.000000e+00
|
|
br i1 %ifcond, label %then, label %else
|
|
|
|
then:
|
|
br label %ifcont
|
|
|
|
else:
|
|
%subtmp = fsub double <b>%x</b>, 1.000000e+00
|
|
%calltmp = call double @fib(double %subtmp)
|
|
%subtmp5 = fsub double <b>%x</b>, 2.000000e+00
|
|
%calltmp6 = call double @fib(double %subtmp5)
|
|
%addtmp = fadd double %calltmp, %calltmp6
|
|
br label %ifcont
|
|
|
|
ifcont: ; preds = %else, %then
|
|
%iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
|
|
ret double %iftmp
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>This is a trivial case for mem2reg, since there are no redefinitions of the
|
|
variable. The point of showing this is to calm your tension about inserting
|
|
such blatent inefficiencies :).</p>
|
|
|
|
<p>After the rest of the optimizers run, we get:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
define double @fib(double %x) {
|
|
entry:
|
|
%cmptmp = fcmp ult double %x, 3.000000e+00
|
|
%booltmp = uitofp i1 %cmptmp to double
|
|
%ifcond = fcmp ueq double %booltmp, 0.000000e+00
|
|
br i1 %ifcond, label %else, label %ifcont
|
|
|
|
else:
|
|
%subtmp = fsub double %x, 1.000000e+00
|
|
%calltmp = call double @fib(double %subtmp)
|
|
%subtmp5 = fsub double %x, 2.000000e+00
|
|
%calltmp6 = call double @fib(double %subtmp5)
|
|
%addtmp = fadd double %calltmp, %calltmp6
|
|
ret double %addtmp
|
|
|
|
ifcont:
|
|
ret double 1.000000e+00
|
|
}
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Here we see that the simplifycfg pass decided to clone the return instruction
|
|
into the end of the 'else' block. This allowed it to eliminate some branches
|
|
and the PHI node.</p>
|
|
|
|
<p>Now that all symbol table references are updated to use stack variables,
|
|
we'll add the assignment operator.</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="assignment">New Assignment Operator</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>With our current framework, adding a new assignment operator is really
|
|
simple. We will parse it just like any other binary operator, but handle it
|
|
internally (instead of allowing the user to define it). The first step is to
|
|
set a precedence:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
def main():
|
|
...
|
|
# Install standard binary operators.
|
|
# 1 is lowest possible precedence. 40 is the highest.
|
|
<b>g_binop_precedence['='] = 2</b>
|
|
g_binop_precedence['<'] = 10
|
|
g_binop_precedence['+'] = 20
|
|
g_binop_precedence['-'] = 20
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Now that the parser knows the precedence of the binary operator, it takes
|
|
care of all the parsing and AST generation. We just need to implement codegen
|
|
for the assignment operator. This looks like:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
class BinaryOperatorExpressionNode(ExpressionNode):
|
|
...
|
|
def CodeGen(self):
|
|
# A special case for '=' because we don't want to emit the LHS as an
|
|
# expression.
|
|
if self.operator == '=':
|
|
# Assignment requires the LHS to be an identifier.
|
|
if not isinstance(self.left, VariableExpressionNode):
|
|
raise RuntimeError('Destination of "=" must be a variable.')
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Unlike the rest of the binary operators, our assignment operator doesn't
|
|
follow the "emit LHS, emit RHS, do computation" model. As such, it is handled
|
|
as a special case before the other binary operators are handled. The other
|
|
strange thing is that it requires the LHS to be a variable. It is invalid to
|
|
have "(x+1) = expr" - only things like "x = expr" are allowed.
|
|
</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Codegen the RHS.
|
|
value = self.right.CodeGen()
|
|
|
|
# Look up the name.
|
|
variable = g_named_values[self.left.name]
|
|
|
|
# Store the value and return it.
|
|
g_llvm_builder.store(value, variable)
|
|
|
|
return value
|
|
...
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Once we have the variable, CodeGening the assignment is straightforward:
|
|
we emit the RHS of the assignment, create a store, and return the computed
|
|
value. Returning a value allows for chained assignments like "X = (Y = Z)".</p>
|
|
|
|
<p>Now that we have an assignment operator, we can mutate loop variables and
|
|
arguments. For example, we can now run code like this:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Function to print a double.
|
|
extern printd(x)
|
|
|
|
# Define ':' for sequencing: as a low-precedence operator that ignores operands
|
|
# and just returns the RHS.
|
|
def binary : 1 (x y) y
|
|
|
|
def test(x)
|
|
printd(x) :
|
|
x = 4 :
|
|
printd(x)
|
|
|
|
test(123)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>When run, this example prints "123" and then "4", showing that we did
|
|
actually mutate the value! Okay, we have now officially implemented our goal:
|
|
getting this to work requires SSA construction in the general case. However,
|
|
to be really useful, we want the ability to define our own local variables.
|
|
Let's add this next!
|
|
</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="localvars">User-defined Local
|
|
Variables</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>Adding var/in is just like any other other extensions we made to
|
|
Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
|
|
The first step for adding our new 'var/in' construct is to extend the lexer.
|
|
As before, this is pretty trivial, the code looks like this:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
...
|
|
class UnaryToken(object): pass
|
|
<b>class VarToken(object): pass</b>
|
|
...
|
|
def Tokenize(string):
|
|
...
|
|
elif identifier == 'unary':
|
|
yield UnaryToken()
|
|
<b>elif identifier == 'var':
|
|
yield VarToken()</b>
|
|
else:
|
|
yield IdentifierToken(identifier)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>The next step is to define the AST node that we will construct. For var/in,
|
|
it looks like this:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Expression class for var/in.
|
|
class VarExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, variables, body):
|
|
self.variables = variables
|
|
self.body = body
|
|
|
|
def CodeGen(self):
|
|
...
|
|
</pre>
|
|
</div>
|
|
|
|
<p>var/in allows a list of names to be defined all at once, and each name can
|
|
optionally have an initializer value. As such, we capture this information in
|
|
the variables list. Also, var/in has a body, this body is allowed to access
|
|
the variables defined by the var/in.</p>
|
|
|
|
<p>With this in place, we can define the parser pieces. The first thing we do
|
|
is add it as a primary expression:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# primary ::=
|
|
# dentifierexpr | numberexpr | parenexpr | ifexpr | forexpr <b>| varexpr</b>
|
|
def ParsePrimary(self):
|
|
if isinstance(self.current, IdentifierToken):
|
|
return self.ParseIdentifierExpr()
|
|
elif isinstance(self.current, NumberToken):
|
|
return self.ParseNumberExpr()
|
|
elif isinstance(self.current, IfToken):
|
|
return self.ParseIfExpr()
|
|
elif isinstance(self.current, ForToken):
|
|
return self.ParseForExpr()
|
|
<b>elif isinstance(self.current, VarToken):
|
|
return self.ParseVarExpr()</b>
|
|
elif self.current == CharacterToken('('):
|
|
return self.ParseParenExpr()
|
|
else:
|
|
raise RuntimeError('Unknown token when expecting an expression.')
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Next we define ParseVarExpr:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# varexpr ::= 'var' (identifier ('=' expression)?)+ 'in' expression
|
|
def ParseVarExpr(self):
|
|
self.Next() # eat 'var'.
|
|
|
|
variables = {}
|
|
|
|
# At least one variable name is required.
|
|
if not isinstance(self.current, IdentifierToken):
|
|
raise RuntimeError('Expected identifier after "var".')
|
|
</pre>
|
|
</div>
|
|
|
|
<p>The first part of this code parses the list of identifier/expr pairs into the
|
|
local <tt>variables</tt> list.
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
while True:
|
|
var_name = self.current.name
|
|
self.Next() # eat the identifier.
|
|
|
|
# Read the optional initializer.
|
|
if self.current == CharacterToken('='):
|
|
self.Next() # eat '='.
|
|
variables[var_name] = self.ParseExpression()
|
|
else:
|
|
variables[var_name] = None
|
|
|
|
# End of var list, exit loop.
|
|
if self.current != CharacterToken(','):
|
|
break
|
|
self.Next() # eat ','.
|
|
|
|
if not isinstance(self.current, IdentifierToken):
|
|
raise RuntimeError('Expected identifier after "," in a var expression.')
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Once all the variables are parsed, we then parse the body and create the
|
|
AST node:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# At this point, we have to have 'in'.
|
|
if not isinstance(self.current, InToken):
|
|
raise RuntimeError('Expected "in" keyword after "var".')
|
|
self.Next() # eat 'in'.
|
|
|
|
body = self.ParseExpression()
|
|
|
|
return VarExpressionNode(variables, body)
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Now that we can parse and represent the code, we need to support emission of
|
|
LLVM IR for it. This code starts out with:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
class VarExpressionNode(ExpressionNode):
|
|
...
|
|
def CodeGen(self):
|
|
old_bindings = {}
|
|
function = g_llvm_builder.basic_block.function
|
|
|
|
# Register all variables and emit their initializer.
|
|
for var_name, var_expression in self.variables.iteritems():
|
|
# Emit the initializer before adding the variable to scope, this prevents
|
|
# the initializer from referencing the variable itself, and permits stuff
|
|
# like this:
|
|
# var a = 1 in
|
|
# var a = a in ... # refers to outer 'a'.
|
|
if var_expression is not None:
|
|
var_value = var_expression.CodeGen()
|
|
else:
|
|
var_value = Constant.real(Type.double(), 0)
|
|
|
|
alloca = CreateEntryBlockAlloca(function, var_name)
|
|
g_llvm_builder.store(var_value, alloca)
|
|
|
|
# Remember the old variable binding so that we can restore the binding
|
|
# when we unrecurse.
|
|
old_bindings[var_name] = g_named_values.get(var_name, None)
|
|
|
|
# Remember this binding.
|
|
g_named_values[var_name] = alloca
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Basically it loops over all the variables, installing them one at a time.
|
|
For each variable we put into the symbol table, we remember the previous value
|
|
that we replace in <tt>old_bindings</tt>.</p>
|
|
|
|
<p>There are more comments here than code. The basic idea is that we emit the
|
|
initializer, create the alloca, then update the symbol table to point to it.
|
|
Once all the variables are installed in the symbol table, we evaluate the body
|
|
of the var/in expression:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Codegen the body, now that all vars are in scope.
|
|
body = self.body.CodeGen()
|
|
</pre>
|
|
</div>
|
|
|
|
<p>Finally, before returning, we restore the previous variable bindings:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
# Pop all our variables from scope.
|
|
for var_name in self.variables:
|
|
if old_bindings[var_name] is not None:
|
|
g_named_values[var_name] = old_bindings[var_name]
|
|
else:
|
|
del g_named_values[var_name]
|
|
|
|
# Return the body computation.
|
|
return body
|
|
</pre>
|
|
</div>
|
|
|
|
<p>The end result of all of this is that we get properly scoped variable
|
|
definitions, and we even (trivially) allow mutation of them :).</p>
|
|
|
|
<p>With this, we completed what we set out to do. Our nice iterative fib
|
|
example from the intro compiles and runs just fine. The mem2reg pass optimizes
|
|
all of our stack variables into SSA registers, inserting PHI nodes where needed,
|
|
and our front-end remains simple: no "iterated dominance frontier" computation
|
|
anywhere in sight.</p>
|
|
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<div class="doc_section"><a name="code">Full Code Listing</a></div>
|
|
<!-- *********************************************************************** -->
|
|
|
|
<div class="doc_text">
|
|
|
|
<p>
|
|
Here is the complete code listing for our running example, enhanced with mutable
|
|
variables and var/in support:</p>
|
|
|
|
<div class="doc_code">
|
|
<pre>
|
|
#!/usr/bin/env python
|
|
|
|
import re
|
|
from llvm.core import Module, Constant, Type, Function, Builder
|
|
from llvm.ee import ExecutionEngine, TargetData
|
|
from llvm.passes import FunctionPassManager
|
|
|
|
from llvm.core import FCMP_ULT, FCMP_ONE
|
|
from llvm.passes import (PASS_MEM2REG,
|
|
PASS_INSTCOMBINE,
|
|
PASS_REASSOCIATE,
|
|
PASS_GVN,
|
|
PASS_SIMPLIFYCFG)
|
|
|
|
################################################################################
|
|
## Globals
|
|
################################################################################
|
|
|
|
# The LLVM module, which holds all the IR code.
|
|
g_llvm_module = Module.new('my cool jit')
|
|
|
|
# The LLVM instruction builder. Created whenever a new function is entered.
|
|
g_llvm_builder = None
|
|
|
|
# A dictionary that keeps track of which values are defined in the current scope
|
|
# and what their LLVM representation is.
|
|
g_named_values = {}
|
|
|
|
# The function optimization passes manager.
|
|
g_llvm_pass_manager = FunctionPassManager.new(g_llvm_module)
|
|
|
|
# The LLVM execution engine.
|
|
g_llvm_executor = ExecutionEngine.new(g_llvm_module)
|
|
|
|
# The binary operator precedence chart.
|
|
g_binop_precedence = {}
|
|
|
|
# Creates an alloca instruction in the entry block of the function. This is used
|
|
# for mutable variables.
|
|
def CreateEntryBlockAlloca(function, var_name):
|
|
entry = function.get_entry_basic_block()
|
|
builder = Builder.new(entry)
|
|
builder.position_at_beginning(entry)
|
|
return builder.alloca(Type.double(), var_name)
|
|
|
|
################################################################################
|
|
## Lexer
|
|
################################################################################
|
|
|
|
# The lexer yields one of these types for each token.
|
|
class EOFToken(object): pass
|
|
class DefToken(object): pass
|
|
class ExternToken(object): pass
|
|
class IfToken(object): pass
|
|
class ThenToken(object): pass
|
|
class ElseToken(object): pass
|
|
class ForToken(object): pass
|
|
class InToken(object): pass
|
|
class BinaryToken(object): pass
|
|
class UnaryToken(object): pass
|
|
class VarToken(object): pass
|
|
|
|
class IdentifierToken(object):
|
|
def __init__(self, name): self.name = name
|
|
|
|
class NumberToken(object):
|
|
def __init__(self, value): self.value = value
|
|
|
|
class CharacterToken(object):
|
|
def __init__(self, char): self.char = char
|
|
def __eq__(self, other):
|
|
return isinstance(other, CharacterToken) and self.char == other.char
|
|
def __ne__(self, other): return not self == other
|
|
|
|
# Regular expressions that tokens and comments of our language.
|
|
REGEX_NUMBER = re.compile('[0-9]+(?:\.[0-9]+)?')
|
|
REGEX_IDENTIFIER = re.compile('[a-zA-Z][a-zA-Z0-9]*')
|
|
REGEX_COMMENT = re.compile('#.*')
|
|
|
|
def Tokenize(string):
|
|
while string:
|
|
# Skip whitespace.
|
|
if string[0].isspace():
|
|
string = string[1:]
|
|
continue
|
|
|
|
# Run regexes.
|
|
comment_match = REGEX_COMMENT.match(string)
|
|
number_match = REGEX_NUMBER.match(string)
|
|
identifier_match = REGEX_IDENTIFIER.match(string)
|
|
|
|
# Check if any of the regexes matched and yield the appropriate result.
|
|
if comment_match:
|
|
comment = comment_match.group(0)
|
|
string = string[len(comment):]
|
|
elif number_match:
|
|
number = number_match.group(0)
|
|
yield NumberToken(float(number))
|
|
string = string[len(number):]
|
|
elif identifier_match:
|
|
identifier = identifier_match.group(0)
|
|
# Check if we matched a keyword.
|
|
if identifier == 'def':
|
|
yield DefToken()
|
|
elif identifier == 'extern':
|
|
yield ExternToken()
|
|
elif identifier == 'if':
|
|
yield IfToken()
|
|
elif identifier == 'then':
|
|
yield ThenToken()
|
|
elif identifier == 'else':
|
|
yield ElseToken()
|
|
elif identifier == 'for':
|
|
yield ForToken()
|
|
elif identifier == 'in':
|
|
yield InToken()
|
|
elif identifier == 'binary':
|
|
yield BinaryToken()
|
|
elif identifier == 'unary':
|
|
yield UnaryToken()
|
|
elif identifier == 'var':
|
|
yield VarToken()
|
|
else:
|
|
yield IdentifierToken(identifier)
|
|
string = string[len(identifier):]
|
|
else:
|
|
# Yield the ASCII value of the unknown character.
|
|
yield CharacterToken(string[0])
|
|
string = string[1:]
|
|
|
|
yield EOFToken()
|
|
|
|
################################################################################
|
|
## Abstract Syntax Tree (aka Parse Tree)
|
|
################################################################################
|
|
|
|
# Base class for all expression nodes.
|
|
class ExpressionNode(object):
|
|
pass
|
|
|
|
# Expression class for numeric literals like "1.0".
|
|
class NumberExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, value):
|
|
self.value = value
|
|
|
|
def CodeGen(self):
|
|
return Constant.real(Type.double(), self.value)
|
|
|
|
# Expression class for referencing a variable, like "a".
|
|
class VariableExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, name):
|
|
self.name = name
|
|
|
|
def CodeGen(self):
|
|
if self.name in g_named_values:
|
|
return g_llvm_builder.load(g_named_values[self.name], self.name)
|
|
else:
|
|
raise RuntimeError('Unknown variable name: ' + self.name)
|
|
|
|
# Expression class for a binary operator.
|
|
class BinaryOperatorExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, operator, left, right):
|
|
self.operator = operator
|
|
self.left = left
|
|
self.right = right
|
|
|
|
def CodeGen(self):
|
|
# A special case for '=' because we don't want to emit the LHS as an
|
|
# expression.
|
|
if self.operator == '=':
|
|
# Assignment requires the LHS to be an identifier.
|
|
if not isinstance(self.left, VariableExpressionNode):
|
|
raise RuntimeError('Destination of "=" must be a variable.')
|
|
|
|
# Codegen the RHS.
|
|
value = self.right.CodeGen()
|
|
|
|
# Look up the name.
|
|
variable = g_named_values[self.left.name]
|
|
|
|
# Store the value and return it.
|
|
g_llvm_builder.store(value, variable)
|
|
|
|
return value
|
|
|
|
left = self.left.CodeGen()
|
|
right = self.right.CodeGen()
|
|
|
|
if self.operator == '+':
|
|
return g_llvm_builder.fadd(left, right, 'addtmp')
|
|
elif self.operator == '-':
|
|
return g_llvm_builder.fsub(left, right, 'subtmp')
|
|
elif self.operator == '*':
|
|
return g_llvm_builder.fmul(left, right, 'multmp')
|
|
elif self.operator == '<':
|
|
result = g_llvm_builder.fcmp(FCMP_ULT, left, right, 'cmptmp')
|
|
# Convert bool 0 or 1 to double 0.0 or 1.0.
|
|
return g_llvm_builder.uitofp(result, Type.double(), 'booltmp')
|
|
else:
|
|
function = g_llvm_module.get_function_named('binary' + self.operator)
|
|
return g_llvm_builder.call(function, [left, right], 'binop')
|
|
|
|
# Expression class for function calls.
|
|
class CallExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, callee, args):
|
|
self.callee = callee
|
|
self.args = args
|
|
|
|
def CodeGen(self):
|
|
# Look up the name in the global module table.
|
|
callee = g_llvm_module.get_function_named(self.callee)
|
|
|
|
# Check for argument mismatch error.
|
|
if len(callee.args) != len(self.args):
|
|
raise RuntimeError('Incorrect number of arguments passed.')
|
|
|
|
arg_values = [i.CodeGen() for i in self.args]
|
|
|
|
return g_llvm_builder.call(callee, arg_values, 'calltmp')
|
|
|
|
# Expression class for if/then/else.
|
|
class IfExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, condition, then_branch, else_branch):
|
|
self.condition = condition
|
|
self.then_branch = then_branch
|
|
self.else_branch = else_branch
|
|
|
|
def CodeGen(self):
|
|
condition = self.condition.CodeGen()
|
|
|
|
# Convert condition to a bool by comparing equal to 0.0.
|
|
condition_bool = g_llvm_builder.fcmp(
|
|
FCMP_ONE, condition, Constant.real(Type.double(), 0), 'ifcond')
|
|
|
|
function = g_llvm_builder.basic_block.function
|
|
|
|
# Create blocks for the then and else cases. Insert the 'then' block at the
|
|
# end of the function.
|
|
then_block = function.append_basic_block('then')
|
|
else_block = function.append_basic_block('else')
|
|
merge_block = function.append_basic_block('ifcond')
|
|
|
|
g_llvm_builder.cbranch(condition_bool, then_block, else_block)
|
|
|
|
# Emit then value.
|
|
g_llvm_builder.position_at_end(then_block)
|
|
then_value = self.then_branch.CodeGen()
|
|
g_llvm_builder.branch(merge_block)
|
|
|
|
# Codegen of 'Then' can change the current block; update then_block for the
|
|
# PHI node.
|
|
then_block = g_llvm_builder.basic_block
|
|
|
|
# Emit else block.
|
|
g_llvm_builder.position_at_end(else_block)
|
|
else_value = self.else_branch.CodeGen()
|
|
g_llvm_builder.branch(merge_block)
|
|
|
|
# Codegen of 'Else' can change the current block, update else_block for the
|
|
# PHI node.
|
|
else_block = g_llvm_builder.basic_block
|
|
|
|
# Emit merge block.
|
|
g_llvm_builder.position_at_end(merge_block)
|
|
phi = g_llvm_builder.phi(Type.double(), 'iftmp')
|
|
phi.add_incoming(then_value, then_block)
|
|
phi.add_incoming(else_value, else_block)
|
|
|
|
return phi
|
|
|
|
# Expression class for for/in.
|
|
class ForExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, loop_variable, start, end, step, body):
|
|
self.loop_variable = loop_variable
|
|
self.start = start
|
|
self.end = end
|
|
self.step = step
|
|
self.body = body
|
|
|
|
def CodeGen(self):
|
|
# Output this as:
|
|
# var = alloca double
|
|
# ...
|
|
# start = startexpr
|
|
# store start -> var
|
|
# goto loop
|
|
# loop:
|
|
# ...
|
|
# bodyexpr
|
|
# ...
|
|
# loopend:
|
|
# step = stepexpr
|
|
# endcond = endexpr
|
|
#
|
|
# curvar = load var
|
|
# nextvar = curvar + step
|
|
# store nextvar -> var
|
|
# br endcond, loop, endloop
|
|
# outloop:
|
|
|
|
function = g_llvm_builder.basic_block.function
|
|
|
|
# Create an alloca for the variable in the entry block.
|
|
alloca = CreateEntryBlockAlloca(function, self.loop_variable)
|
|
|
|
# Emit the start code first, without 'variable' in scope.
|
|
start_value = self.start.CodeGen()
|
|
|
|
# Store the value into the alloca.
|
|
g_llvm_builder.store(start_value, alloca)
|
|
|
|
# Make the new basic block for the loop, inserting after current block.
|
|
loop_block = function.append_basic_block('loop')
|
|
|
|
# Insert an explicit fall through from the current block to the loop_block.
|
|
g_llvm_builder.branch(loop_block)
|
|
|
|
# Start insertion in loop_block.
|
|
g_llvm_builder.position_at_end(loop_block)
|
|
|
|
# Within the loop, the variable is defined equal to the alloca. If it
|
|
# shadows an existing variable, we have to restore it, so save it now.
|
|
old_value = g_named_values.get(self.loop_variable, None)
|
|
g_named_values[self.loop_variable] = alloca
|
|
|
|
# Emit the body of the loop. This, like any other expr, can change the
|
|
# current BB. Note that we ignore the value computed by the body.
|
|
self.body.CodeGen()
|
|
|
|
# Emit the step value.
|
|
if self.step:
|
|
step_value = self.step.CodeGen()
|
|
else:
|
|
# If not specified, use 1.0.
|
|
step_value = Constant.real(Type.double(), 1)
|
|
|
|
# Compute the end condition.
|
|
end_condition = self.end.CodeGen()
|
|
|
|
# Reload, increment, and restore the alloca. This handles the case where
|
|
# the body of the loop mutates the variable.
|
|
cur_value = g_llvm_builder.load(alloca, self.loop_variable)
|
|
next_value = g_llvm_builder.fadd(cur_value, step_value, 'nextvar')
|
|
g_llvm_builder.store(next_value, alloca)
|
|
|
|
# Convert condition to a bool by comparing equal to 0.0.
|
|
end_condition_bool = g_llvm_builder.fcmp(
|
|
FCMP_ONE, end_condition, Constant.real(Type.double(), 0), 'loopcond')
|
|
|
|
# Create the "after loop" block and insert it.
|
|
after_block = function.append_basic_block('afterloop')
|
|
|
|
# Insert the conditional branch into the end of loop_block.
|
|
g_llvm_builder.cbranch(end_condition_bool, loop_block, after_block)
|
|
|
|
# Any new code will be inserted in after_block.
|
|
g_llvm_builder.position_at_end(after_block)
|
|
|
|
# Restore the unshadowed variable.
|
|
if old_value is not None:
|
|
g_named_values[self.loop_variable] = old_value
|
|
else:
|
|
del g_named_values[self.loop_variable]
|
|
|
|
# for expr always returns 0.0.
|
|
return Constant.real(Type.double(), 0)
|
|
|
|
# Expression class for a unary operator.
|
|
class UnaryExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, operator, operand):
|
|
self.operator = operator
|
|
self.operand = operand
|
|
|
|
def CodeGen(self):
|
|
operand = self.operand.CodeGen()
|
|
function = g_llvm_module.get_function_named('unary' + self.operator)
|
|
return g_llvm_builder.call(function, [operand], 'unop')
|
|
|
|
# Expression class for var/in.
|
|
class VarExpressionNode(ExpressionNode):
|
|
|
|
def __init__(self, variables, body):
|
|
self.variables = variables
|
|
self.body = body
|
|
|
|
def CodeGen(self):
|
|
old_bindings = {}
|
|
function = g_llvm_builder.basic_block.function
|
|
|
|
# Register all variables and emit their initializer.
|
|
for var_name, var_expression in self.variables.iteritems():
|
|
# Emit the initializer before adding the variable to scope, this prevents
|
|
# the initializer from referencing the variable itself, and permits stuff
|
|
# like this:
|
|
# var a = 1 in
|
|
# var a = a in ... # refers to outer 'a'.
|
|
if var_expression is not None:
|
|
var_value = var_expression.CodeGen()
|
|
else:
|
|
var_value = Constant.real(Type.double(), 0)
|
|
|
|
alloca = CreateEntryBlockAlloca(function, var_name)
|
|
g_llvm_builder.store(var_value, alloca)
|
|
|
|
# Remember the old variable binding so that we can restore the binding
|
|
# when we unrecurse.
|
|
old_bindings[var_name] = g_named_values.get(var_name, None)
|
|
|
|
# Remember this binding.
|
|
g_named_values[var_name] = alloca
|
|
|
|
# Codegen the body, now that all vars are in scope.
|
|
body = self.body.CodeGen()
|
|
|
|
# Pop all our variables from scope.
|
|
for var_name in self.variables:
|
|
if old_bindings[var_name] is not None:
|
|
g_named_values[var_name] = old_bindings[var_name]
|
|
else:
|
|
del g_named_values[var_name]
|
|
|
|
# Return the body computation.
|
|
return body
|
|
|
|
# This class represents the "prototype" for a function, which captures its name,
|
|
# and its argument names (thus implicitly the number of arguments the function
|
|
# takes), as well as if it is an operator.
|
|
class PrototypeNode(object):
|
|
|
|
def __init__(self, name, args, is_operator=False, precedence=0):
|
|
self.name = name
|
|
self.args = args
|
|
self.is_operator = is_operator
|
|
self.precedence = precedence
|
|
|
|
def IsBinaryOp(self):
|
|
return self.is_operator and len(self.args) == 2
|
|
|
|
def GetOperatorName(self):
|
|
assert self.is_operator
|
|
return self.name[-1]
|
|
|
|
def CodeGen(self):
|
|
# Make the function type, eg. double(double,double).
|
|
funct_type = Type.function(
|
|
Type.double(), [Type.double()] * len(self.args), False)
|
|
|
|
function = Function.new(g_llvm_module, funct_type, self.name)
|
|
|
|
# If the name conflicted, there was already something with the same name.
|
|
# If it has a body, don't allow redefinition or reextern.
|
|
if function.name != self.name:
|
|
function.delete()
|
|
function = g_llvm_module.get_function_named(self.name)
|
|
|
|
# If the function already has a body, reject this.
|
|
if not function.is_declaration:
|
|
raise RuntimeError('Redefinition of function.')
|
|
|
|
# If the function took a different number of args, reject.
|
|
if len(function.args) != len(self.args):
|
|
raise RuntimeError('Redeclaration of a function with different number '
|
|
'of args.')
|
|
|
|
# Set names for all arguments and add them to the variables symbol table.
|
|
for arg, arg_name in zip(function.args, self.args):
|
|
arg.name = arg_name
|
|
|
|
return function
|
|
|
|
# Create an alloca for each argument and register the argument in the symbol
|
|
# table so that references to it will succeed.
|
|
def CreateArgumentAllocas(self, function):
|
|
for arg_name, arg in zip(self.args, function.args):
|
|
alloca = CreateEntryBlockAlloca(function, arg_name)
|
|
g_llvm_builder.store(arg, alloca)
|
|
g_named_values[arg_name] = alloca
|
|
|
|
# This class represents a function definition itself.
|
|
class FunctionNode(object):
|
|
|
|
def __init__(self, prototype, body):
|
|
self.prototype = prototype
|
|
self.body = body
|
|
|
|
def CodeGen(self):
|
|
# Clear scope.
|
|
g_named_values.clear()
|
|
|
|
# Create a function object.
|
|
function = self.prototype.CodeGen()
|
|
|
|
# If this is a binary operator, install its precedence.
|
|
if self.prototype.IsBinaryOp():
|
|
operator = self.prototype.GetOperatorName()
|
|
g_binop_precedence[operator] = self.prototype.precedence
|
|
|
|
# Create a new basic block to start insertion into.
|
|
block = function.append_basic_block('entry')
|
|
global g_llvm_builder
|
|
g_llvm_builder = Builder.new(block)
|
|
|
|
# Add all arguments to the symbol table and create their allocas.
|
|
self.prototype.CreateArgumentAllocas(function)
|
|
|
|
# Finish off the function.
|
|
try:
|
|
return_value = self.body.CodeGen()
|
|
g_llvm_builder.ret(return_value)
|
|
|
|
# Validate the generated code, checking for consistency.
|
|
function.verify()
|
|
|
|
# Optimize the function.
|
|
g_llvm_pass_manager.run(function)
|
|
except:
|
|
function.delete()
|
|
if self.prototype.IsBinaryOp():
|
|
del g_binop_precedence[self.prototype.GetOperatorName()]
|
|
raise
|
|
|
|
return function
|
|
|
|
|
|
################################################################################
|
|
## Parser
|
|
################################################################################
|
|
|
|
class Parser(object):
|
|
|
|
def __init__(self, tokens):
|
|
self.tokens = tokens
|
|
self.Next()
|
|
|
|
# Provide a simple token buffer. Parser.current is the current token the
|
|
# parser is looking at. Parser.Next() reads another token from the lexer and
|
|
# updates Parser.current with its results.
|
|
def Next(self):
|
|
self.current = self.tokens.next()
|
|
|
|
# Gets the precedence of the current token, or -1 if the token is not a binary
|
|
# operator.
|
|
def GetCurrentTokenPrecedence(self):
|
|
if isinstance(self.current, CharacterToken):
|
|
return g_binop_precedence.get(self.current.char, -1)
|
|
else:
|
|
return -1
|
|
|
|
# identifierexpr ::= identifier | identifier '(' expression* ')'
|
|
def ParseIdentifierExpr(self):
|
|
identifier_name = self.current.name
|
|
self.Next() # eat identifier.
|
|
|
|
if self.current != CharacterToken('('): # Simple variable reference.
|
|
return VariableExpressionNode(identifier_name)
|
|
|
|
# Call.
|
|
self.Next() # eat '('.
|
|
args = []
|
|
if self.current != CharacterToken(')'):
|
|
while True:
|
|
args.append(self.ParseExpression())
|
|
if self.current == CharacterToken(')'):
|
|
break
|
|
elif self.current != CharacterToken(','):
|
|
raise RuntimeError('Expected ")" or "," in argument list.')
|
|
self.Next()
|
|
|
|
self.Next() # eat ')'.
|
|
return CallExpressionNode(identifier_name, args)
|
|
|
|
# numberexpr ::= number
|
|
def ParseNumberExpr(self):
|
|
result = NumberExpressionNode(self.current.value)
|
|
self.Next() # consume the number.
|
|
return result
|
|
|
|
# parenexpr ::= '(' expression ')'
|
|
def ParseParenExpr(self):
|
|
self.Next() # eat '('.
|
|
|
|
contents = self.ParseExpression()
|
|
|
|
if self.current != CharacterToken(')'):
|
|
raise RuntimeError('Expected ")".')
|
|
self.Next() # eat ')'.
|
|
|
|
return contents
|
|
|
|
# ifexpr ::= 'if' expression 'then' expression 'else' expression
|
|
def ParseIfExpr(self):
|
|
self.Next() # eat the if.
|
|
|
|
# condition.
|
|
condition = self.ParseExpression()
|
|
|
|
if not isinstance(self.current, ThenToken):
|
|
raise RuntimeError('Expected "then".')
|
|
self.Next() # eat the then.
|
|
|
|
then_branch = self.ParseExpression()
|
|
|
|
if not isinstance(self.current, ElseToken):
|
|
raise RuntimeError('Expected "else".')
|
|
self.Next() # eat the else.
|
|
|
|
else_branch = self.ParseExpression()
|
|
|
|
return IfExpressionNode(condition, then_branch, else_branch)
|
|
|
|
# forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression
|
|
def ParseForExpr(self):
|
|
self.Next() # eat the for.
|
|
|
|
if not isinstance(self.current, IdentifierToken):
|
|
raise RuntimeError('Expected identifier after for.')
|
|
|
|
loop_variable = self.current.name
|
|
self.Next() # eat the identifier.
|
|
|
|
if self.current != CharacterToken('='):
|
|
raise RuntimeError('Expected "=" after for variable.')
|
|
self.Next() # eat the '='.
|
|
|
|
start = self.ParseExpression()
|
|
|
|
if self.current != CharacterToken(','):
|
|
raise RuntimeError('Expected "," after for start value.')
|
|
self.Next() # eat the ','.
|
|
|
|
end = self.ParseExpression()
|
|
|
|
# The step value is optional.
|
|
if self.current == CharacterToken(','):
|
|
self.Next() # eat the ','.
|
|
step = self.ParseExpression()
|
|
else:
|
|
step = None
|
|
|
|
if not isinstance(self.current, InToken):
|
|
raise RuntimeError('Expected "in" after for variable specification.')
|
|
self.Next() # eat 'in'.
|
|
|
|
body = self.ParseExpression()
|
|
|
|
return ForExpressionNode(loop_variable, start, end, step, body)
|
|
|
|
# varexpr ::= 'var' (identifier ('=' expression)?)+ 'in' expression
|
|
def ParseVarExpr(self):
|
|
self.Next() # eat 'var'.
|
|
|
|
variables = {}
|
|
|
|
# At least one variable name is required.
|
|
if not isinstance(self.current, IdentifierToken):
|
|
raise RuntimeError('Expected identifier after "var".')
|
|
|
|
while True:
|
|
var_name = self.current.name
|
|
self.Next() # eat the identifier.
|
|
|
|
# Read the optional initializer.
|
|
if self.current == CharacterToken('='):
|
|
self.Next() # eat '='.
|
|
variables[var_name] = self.ParseExpression()
|
|
else:
|
|
variables[var_name] = None
|
|
|
|
# End of var list, exit loop.
|
|
if self.current != CharacterToken(','):
|
|
break
|
|
self.Next() # eat ','.
|
|
|
|
if not isinstance(self.current, IdentifierToken):
|
|
raise RuntimeError('Expected identifier after "," in a var expression.')
|
|
|
|
# At this point, we have to have 'in'.
|
|
if not isinstance(self.current, InToken):
|
|
raise RuntimeError('Expected "in" keyword after "var".')
|
|
self.Next() # eat 'in'.
|
|
|
|
body = self.ParseExpression()
|
|
|
|
return VarExpressionNode(variables, body)
|
|
|
|
# primary ::=
|
|
# dentifierexpr | numberexpr | parenexpr | ifexpr | forexpr | varexpr
|
|
def ParsePrimary(self):
|
|
if isinstance(self.current, IdentifierToken):
|
|
return self.ParseIdentifierExpr()
|
|
elif isinstance(self.current, NumberToken):
|
|
return self.ParseNumberExpr()
|
|
elif isinstance(self.current, IfToken):
|
|
return self.ParseIfExpr()
|
|
elif isinstance(self.current, ForToken):
|
|
return self.ParseForExpr()
|
|
elif isinstance(self.current, VarToken):
|
|
return self.ParseVarExpr()
|
|
elif self.current == CharacterToken('('):
|
|
return self.ParseParenExpr()
|
|
else:
|
|
raise RuntimeError('Unknown token when expecting an expression.')
|
|
|
|
# unary ::= primary | unary_operator unary
|
|
def ParseUnary(self):
|
|
# If the current token is not an operator, it must be a primary expression.
|
|
if (not isinstance(self.current, CharacterToken) or
|
|
self.current in [CharacterToken('('), CharacterToken(',')]):
|
|
return self.ParsePrimary()
|
|
|
|
# If this is a unary operator, read it.
|
|
operator = self.current.char
|
|
self.Next() # eat the operator.
|
|
return UnaryExpressionNode(operator, self.ParseUnary())
|
|
|
|
# binoprhs ::= (binary_operator unary)*
|
|
def ParseBinOpRHS(self, left, left_precedence):
|
|
# If this is a binary operator, find its precedence.
|
|
while True:
|
|
precedence = self.GetCurrentTokenPrecedence()
|
|
|
|
# If this is a binary operator that binds at least as tightly as the
|
|
# current one, consume it; otherwise we are done.
|
|
if precedence < left_precedence:
|
|
return left
|
|
|
|
binary_operator = self.current.char
|
|
self.Next() # eat the operator.
|
|
|
|
# Parse the unary expression after the binary operator.
|
|
right = self.ParseUnary()
|
|
|
|
# If binary_operator binds less tightly with right than the operator after
|
|
# right, let the pending operator take right as its left.
|
|
next_precedence = self.GetCurrentTokenPrecedence()
|
|
if precedence < next_precedence:
|
|
right = self.ParseBinOpRHS(right, precedence + 1)
|
|
|
|
# Merge left/right.
|
|
left = BinaryOperatorExpressionNode(binary_operator, left, right)
|
|
|
|
# expression ::= unary binoprhs
|
|
def ParseExpression(self):
|
|
left = self.ParseUnary()
|
|
return self.ParseBinOpRHS(left, 0)
|
|
|
|
# prototype
|
|
# ::= id '(' id* ')'
|
|
# ::= binary LETTER number? (id, id)
|
|
# ::= unary LETTER (id)
|
|
def ParsePrototype(self):
|
|
precedence = None
|
|
if isinstance(self.current, IdentifierToken):
|
|
kind = 'normal'
|
|
function_name = self.current.name
|
|
self.Next() # eat function name.
|
|
elif isinstance(self.current, UnaryToken):
|
|
kind = 'unary'
|
|
self.Next() # eat 'unary'.
|
|
if not isinstance(self.current, CharacterToken):
|
|
raise RuntimeError('Expected an operator after "unary".')
|
|
function_name = 'unary' + self.current.char
|
|
self.Next() # eat the operator.
|
|
elif isinstance(self.current, BinaryToken):
|
|
kind = 'binary'
|
|
self.Next() # eat 'binary'.
|
|
if not isinstance(self.current, CharacterToken):
|
|
raise RuntimeError('Expected an operator after "binary".')
|
|
function_name = 'binary' + self.current.char
|
|
self.Next() # eat the operator.
|
|
if isinstance(self.current, NumberToken):
|
|
if not 1 <= self.current.value <= 100:
|
|
raise RuntimeError('Invalid precedence: must be in range [1, 100].')
|
|
precedence = self.current.value
|
|
self.Next() # eat the precedence.
|
|
else:
|
|
raise RuntimeError('Expected function name, "unary" or "binary" in '
|
|
'prototype.')
|
|
|
|
if self.current != CharacterToken('('):
|
|
raise RuntimeError('Expected "(" in prototype.')
|
|
self.Next() # eat '('.
|
|
|
|
arg_names = []
|
|
while isinstance(self.current, IdentifierToken):
|
|
arg_names.append(self.current.name)
|
|
self.Next()
|
|
|
|
if self.current != CharacterToken(')'):
|
|
raise RuntimeError('Expected ")" in prototype.')
|
|
|
|
# Success.
|
|
self.Next() # eat ')'.
|
|
|
|
if kind == 'unary' and len(arg_names) != 1:
|
|
raise RuntimeError('Invalid number of arguments for a unary operator.')
|
|
elif kind == 'binary' and len(arg_names) != 2:
|
|
raise RuntimeError('Invalid number of arguments for a binary operator.')
|
|
|
|
return PrototypeNode(function_name, arg_names, kind != 'normal', precedence)
|
|
|
|
# definition ::= 'def' prototype expression
|
|
def ParseDefinition(self):
|
|
self.Next() # eat def.
|
|
proto = self.ParsePrototype()
|
|
body = self.ParseExpression()
|
|
return FunctionNode(proto, body)
|
|
|
|
# toplevelexpr ::= expression
|
|
def ParseTopLevelExpr(self):
|
|
proto = PrototypeNode('', [])
|
|
return FunctionNode(proto, self.ParseExpression())
|
|
|
|
# external ::= 'extern' prototype
|
|
def ParseExtern(self):
|
|
self.Next() # eat extern.
|
|
return self.ParsePrototype()
|
|
|
|
# Top-Level parsing
|
|
def HandleDefinition(self):
|
|
self.Handle(self.ParseDefinition, 'Read a function definition:')
|
|
|
|
def HandleExtern(self):
|
|
self.Handle(self.ParseExtern, 'Read an extern:')
|
|
|
|
def HandleTopLevelExpression(self):
|
|
try:
|
|
function = self.ParseTopLevelExpr().CodeGen()
|
|
result = g_llvm_executor.run_function(function, [])
|
|
print 'Evaluated to:', result.as_real(Type.double())
|
|
except Exception, e:
|
|
raise#print 'Error:', e
|
|
try:
|
|
self.Next() # Skip for error recovery.
|
|
except:
|
|
pass
|
|
|
|
def Handle(self, function, message):
|
|
try:
|
|
print message, function().CodeGen()
|
|
except Exception, e:
|
|
raise#print 'Error:', e
|
|
try:
|
|
self.Next() # Skip for error recovery.
|
|
except:
|
|
pass
|
|
|
|
################################################################################
|
|
## Main driver code.
|
|
################################################################################
|
|
|
|
def main():
|
|
# Set up the optimizer pipeline. Start with registering info about how the
|
|
# target lays out data structures.
|
|
g_llvm_pass_manager.add(g_llvm_executor.target_data)
|
|
# Promote allocas to registers.
|
|
g_llvm_pass_manager.add(PASS_MEM2REG)
|
|
# Do simple "peephole" optimizations and bit-twiddling optzns.
|
|
g_llvm_pass_manager.add(PASS_INSTCOMBINE)
|
|
# Reassociate expressions.
|
|
g_llvm_pass_manager.add(PASS_REASSOCIATE)
|
|
# Eliminate Common SubExpressions.
|
|
g_llvm_pass_manager.add(PASS_GVN)
|
|
# Simplify the control flow graph (deleting unreachable blocks, etc).
|
|
g_llvm_pass_manager.add(PASS_SIMPLIFYCFG)
|
|
|
|
g_llvm_pass_manager.initialize()
|
|
|
|
# Install standard binary operators.
|
|
# 1 is lowest possible precedence. 40 is the highest.
|
|
g_binop_precedence['='] = 2
|
|
g_binop_precedence['<'] = 10
|
|
g_binop_precedence['+'] = 20
|
|
g_binop_precedence['-'] = 20
|
|
g_binop_precedence['*'] = 40
|
|
|
|
# Run the main "interpreter loop".
|
|
while True:
|
|
print 'ready<',
|
|
try:
|
|
raw = raw_input()
|
|
except KeyboardInterrupt:
|
|
break
|
|
|
|
parser = Parser(Tokenize(raw))
|
|
while True:
|
|
# top ::= definition | external | expression | EOF
|
|
if isinstance(parser.current, EOFToken):
|
|
break
|
|
if isinstance(parser.current, DefToken):
|
|
parser.HandleDefinition()
|
|
elif isinstance(parser.current, ExternToken):
|
|
parser.HandleExtern()
|
|
else:
|
|
parser.HandleTopLevelExpression()
|
|
|
|
# Print out all of the generated code.
|
|
print '\n', g_llvm_module
|
|
|
|
if __name__ == '__main__':
|
|
main()
|
|
</pre>
|
|
</div>
|
|
|
|
<a href="PythonLangImpl8.html">Next: Conclusion and other useful LLVM
|
|
tidbits</a>
|
|
</div>
|
|
|
|
<!-- *********************************************************************** -->
|
|
<hr>
|
|
<address>
|
|
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
|
|
src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
|
|
<a href="http://validator.w3.org/check/referer"><img
|
|
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
|
|
|
|
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
|
|
<a href="http://max99x.com">Max Shawabkeh</a><br>
|
|
<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
|
|
Last modified: $Date$
|
|
</address>
|
|
</body>
|
|
</html>
|