<head>
<title>Stacker: An Example Of Using LLVM</title>
<link rel="stylesheet" href="llvm.css" type="text/css">
- <style>
- table, tr, td { border: 2px solid gray }
- table { border-collapse: collapse; margin-bottom: 2em }
- </style>
</head>
<body>
classes were derived from the Value class. The full power of that simple
design only became fully understood once I started constructing executable
expressions for Stacker.</p>
+
<p>This really makes your programming go faster. Think about compiling code
for the following C/C++ expression: <code>(a|b)*((x+1)/(y+1))</code>. Assuming
the values are on the stack in the order a, b, x, y, this could be
expressed in stacker as: <code>1 + SWAP 1 + / ROT2 OR *</code>.
-You could write a function using LLVM that computes this expression like this: </p>
-<pre><code>
+You could write a function using LLVM that computes this expression like
+this: </p>
+
+<div class="doc_code"><pre>
Value*
expression(BasicBlock* bb, Value* a, Value* b, Value* x, Value* y )
{
- Instruction* tail = bb->getTerminator();
- ConstantSInt* one = ConstantSInt::get( Type::IntTy, 1);
- BinaryOperator* or1 =
- BinaryOperator::create( Instruction::Or, a, b, "", tail );
- BinaryOperator* add1 =
- BinaryOperator::create( Instruction::Add, x, one, "", tail );
- BinaryOperator* add2 =
- BinaryOperator::create( Instruction::Add, y, one, "", tail );
- BinaryOperator* div1 =
- BinaryOperator::create( Instruction::Div, add1, add2, "", tail);
- BinaryOperator* mult1 =
- BinaryOperator::create( Instruction::Mul, or1, div1, "", tail );
-
+ ConstantInt* one = ConstantInt::get(Type::IntTy, 1);
+ BinaryOperator* or1 = BinaryOperator::createOr(a, b, "", bb);
+ BinaryOperator* add1 = BinaryOperator::createAdd(x, one, "", bb);
+ BinaryOperator* add2 = BinaryOperator::createAdd(y, one, "", bb);
+ BinaryOperator* div1 = BinaryOperator::createDiv(add1, add2, "", bb);
+ BinaryOperator* mult1 = BinaryOperator::createMul(or1, div1, "", bb);
return mult1;
}
-</code></pre>
+</pre></div>
+
<p>"Okay, big deal," you say? It is a big deal. Here's why. Note that I didn't
have to tell this function which kinds of Values are being passed in. They could be
<code>Instruction</code>s, <code>Constant</code>s, <code>GlobalVariable</code>s, or
<li><em>Create your blocks early.</em> While writing your compiler, you
will encounter several situations where you know apriori that you will
need several blocks. For example, if-then-else, switch, while, and for
- statements in C/C++ all need multiple blocks for expression in LVVM.
+ statements in C/C++ all need multiple blocks for expression in LLVM.
The rule is, create them early.</li>
<li><em>Terminate your blocks early.</em> This just reduces the chances
that you forget to terminate your blocks which is required (go
<pre>
using namespace llvm;
BasicBlock*
-MyCompiler::handle_if( BasicBlock* bb, SetCondInst* condition )
+MyCompiler::handle_if( BasicBlock* bb, ICmpInst* condition )
{
// Create the blocks to contain code in the structure of if/then/else
BasicBlock* then_bb = new BasicBlock();
</p>
<pre>
std::vector<Value*> index_vector;
-index_vector.push_back( ConstantSInt::get( Type::LongTy, 0 );
+index_vector.push_back( ConstantInt::get( Type::LongTy, 0 );
// ... push other indices ...
GetElementPtrInst* gep = new GetElementPtrInst( ptr, index_vector );
</pre>
<ul>
<li>Constants are Values like anything else and can be operands of instructions</li>
<li>Integer constants, frequently needed, can be created using the static "get"
- methods of the ConstantInt, ConstantSInt, and ConstantUInt classes. The nice thing
- about these is that you can "get" any kind of integer quickly.</li>
- <li>There's a special method on Constant class which allows you to get the null
+ methods of the ConstantInt class. The nice thing about these is that you can
+ "get" any kind of integer quickly.</li>
+ <li>There's a special method on Constant class which allows you to get the null
constant for <em>any</em> type. This is really handy for initializing large
arrays or structures, etc.</li>
</ul>
</ol>
</div>
<div class="doc_text" >
- <table class="doc_table">
-<tr class="doc_table"><td colspan="4">Definition Of Operation Of Built In Words</td></tr>
-<tr class="doc_table"><td colspan="4"><b>LOGICAL OPERATIONS</b></td></tr>
-<tr class="doc_table">
+ <table>
+<tr><th colspan="4">Definition Of Operation Of Built In Words</th></tr>
+<tr><th colspan="4"><b>LOGICAL OPERATIONS</b></th></tr>
+<tr>
<td>Word</td>
<td>Name</td>
<td>Operation</td>
<td>Description</td>
</tr>
-<tr class="doc_table">
+<tr>
<td><</td>
<td>LT</td>
<td>w1 w2 -- b</td>
<td> -- b</td>
<td>The boolean value TRUE (-1) is pushed on to the stack.</td>
</tr>
-<tr><td colspan="4"><b>BITWISE OPERATORS</b></td></tr>
+<tr><th colspan="4"><b>BITWISE OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
are bitwise exclusive OR'd together and pushed back on the stack.
For example, The sequence 1 3 XOR yields 2.</td>
</tr>
-<tr><td colspan="4"><b>ARITHMETIC OPERATORS</b></td></tr>
+<tr><th colspan="4"><b>ARITHMETIC OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
<td>Two values are popped off the stack. The larger value is pushed back
on to the stack.</td>
</tr>
-<tr><td colspan="4"><b>STACK MANIPULATION OPERATORS</b></td></tr>
+<tr><th colspan="4"><b>STACK MANIPULATION OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
</tr>
<tr><td>RROT</td>
<td>RROT</td>
- <td>w1 w2 w3 -- w2 w3 w1</td>
+ <td>w1 w2 w3 -- w3 w1 w2</td>
<td>Reverse rotation. Like ROT, but it rotates the other way around.
Essentially, the third element on the stack is moved to the top
of the stack.</td>
how much to rotate. That is, ROLL with n=1 is the same as ROT and
ROLL with n=2 is the same as ROT2.</td>
</tr>
-<tr><td colspan="4"><b>MEMORY OPERATORS</b></td></tr>
+<tr><th colspan="4"><b>MEMORY OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
pushed back on the stack so this doesn't count as a "use ptr"
in the FREE idiom.</td>
</tr>
-<tr><td colspan="4"><b>CONTROL FLOW OPERATORS</b></td></tr>
+<tr><th colspan="4"><b>CONTROL FLOW OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
executed. In either case, after the (words....) have executed, execution continues
immediately following the ENDIF. </td>
</tr>
-<tr><td>WHILE (words...) END</td>
- <td>WHILE (words...) END</td>
+<tr><td>WHILE word END</td>
+ <td>WHILE word END</td>
<td>b -- b </td>
- <td>The boolean value on the top of the stack is examined. If it is non-zero then the
- "words..." between WHILE and END are executed. Execution then begins again at the WHILE where another
- boolean is popped off the stack. To prevent this operation from eating up the entire
- stack, you should push on to the stack (just before the END) a boolean value that indicates
- whether to terminate. Note that since booleans and integers can be coerced you can
- use the following "for loop" idiom:<br/>
- <code>(push count) WHILE (words...) -- END</code><br/>
+ <td>The boolean value on the top of the stack is examined (not popped). If
+ it is non-zero then the "word" between WHILE and END is executed.
+ Execution then begins again at the WHILE where the boolean on the top of
+ the stack is examined again. The stack is not modified by the WHILE...END
+ loop, only examined. It is imperative that the "word" in the body of the
+ loop ensure that the top of the stack contains the next boolean to examine
+ when it completes. Note that since booleans and integers can be coerced
+ you can use the following "for loop" idiom:<br/>
+ <code>(push count) WHILE word -- END</code><br/>
For example:<br/>
- <code>10 WHILE DUP >d -- END</code><br/>
- This will print the numbers from 10 down to 1. 10 is pushed on the stack. Since that is
- non-zero, the while loop is entered. The top of the stack (10) is duplicated and then
- printed out with >d. The top of the stack is decremented, yielding 9 and control is
- transfered back to the WHILE keyword. The process starts all over again and repeats until
- the top of stack is decremented to 0 at which the WHILE test fails and control is
- transfered to the word after the END.</td>
-</tr>
-<tr><td colspan="4"><b>INPUT & OUTPUT OPERATORS</b></td></tr>
+ <code>10 WHILE >d -- END</code><br/>
+ This will print the numbers from 10 down to 1. 10 is pushed on the
+ stack. Since that is non-zero, the while loop is entered. The top of
+ the stack (10) is printed out with >d. The top of the stack is
+ decremented, yielding 9 and control is transfered back to the WHILE
+ keyword. The process starts all over again and repeats until
+ the top of stack is decremented to 0 at which point the WHILE test
+ fails and control is transfered to the word after the END.
+ </td>
+</tr>
+<tr><th colspan="4"><b>INPUT & OUTPUT OPERATORS</b></th></tr>
<tr>
<td>Word</td>
<td>Name</td>
<div class="doc_subsection"> <a name="directory">Directory Structure</a></div>
<div class="doc_text">
<p>The source code, test programs, and sample programs can all be found
-under the LLVM "projects" directory. You will need to obtain the LLVM sources
-to find it (either via anonymous CVS or a tarball. See the
-<a href="GettingStarted.html">Getting Started</a> document).</p>
-<p>Under the "projects" directory there is a directory named "Stacker". That
-directory contains everything, as follows:</p>
+in the LLVM repository named <tt>llvm-stacker</tt> This should be checked out to
+the <tt>projects</tt> directory so that it will auto-configure. To do that, make
+sure you have the llvm sources in <tt><i>llvm</i></tt>
+(see <a href="GettingStarted.html">Getting Started</a>) and then use these
+commands:<pre>
+ cd <i>llvm</i>/projects
+ cvs co llvm-stacker</pre>
+</p>
+<p>Under the <tt>projects/llvm-stacker</tt> directory you will find the
+implementation of the Stacker compiler, as follows:</p>
<ul>
<li><em>lib</em> - contains most of the source code
<ul>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="lexer"></a>The Lexer</div>
<div class="doc_text">
-<p>See projects/Stacker/lib/compiler/Lexer.l</p>
+<p>See projects/llvm-stacker/lib/compiler/Lexer.l</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="parser"></a>The Parser</div>
<div class="doc_text">
-<p>See projects/Stacker/lib/compiler/StackerParser.y</p>
+<p>See projects/llvm-stacker/lib/compiler/StackerParser.y</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="compiler"></a>The Compiler</div>
<div class="doc_text">
-<p>See projects/Stacker/lib/compiler/StackerCompiler.cpp</p>
+<p>See projects/llvm-stacker/lib/compiler/StackerCompiler.cpp</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="runtime"></a>The Runtime</div>
<div class="doc_text">
-<p>See projects/Stacker/lib/runtime/stacker_rt.c</p>
+<p>See projects/llvm-stacker/lib/runtime/stacker_rt.c</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="driver"></a>Compiler Driver</div>
<div class="doc_text">
-<p>See projects/Stacker/tools/stkrc/stkrc.cpp</p>
+<p>See projects/llvm-stacker/tools/stkrc/stkrc.cpp</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"><a name="tests"></a>Test Programs</div>
<div class="doc_text">
-<p>See projects/Stacker/test/*.st</p>
+<p>See projects/llvm-stacker/test/*.st</p>
</div>
<!-- ======================================================================= -->
<div class="doc_subsection"> <a name="exercise">Exercise</a></div>
<li>Write an LLVM pass to optimize the use of the global stack. The code
emitted currently is somewhat wasteful. It gets cleaned up a lot by existing
passes but more could be done.</li>
- <li>Add -O -O1 -O2 and -O3 optimization switches to the compiler driver to
- allow LLVM optimization without using "opt."</li>
<li>Make the compiler driver use the LLVM linking facilities (with IPO)
before depending on GCC to do the final link.</li>
<li>Clean up parsing. It doesn't handle errors very well.</li>
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:rspencer@x10sys.com">Reid Spencer</a><br>
- <a href="http://llvm.cs.uiuc.edu">LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>