| blob | 225a27bbf77556707220239e905f8a3d89dff404 |
3 <html>
4 <head>
7 </head>
8 <body>
12 <ol>
16 <ol>
24 </ol></li>
26 <ol>
34 </ol></li>
37 <ol>
47 </ol></li>
48 </ol>
52 </div>
54 <!-- ======================================================================= -->
57 <p>This document is another way to learn about LLVM. Unlike the
60 about LLVM through the experience of creating a simple programming language
61 named Stacker. Stacker was invented specifically as a demonstration of
62 LLVM. The emphasis in this document is not on describing the
63 intricacies of LLVM itself but on how to use it to build your own
64 compiler system.</p>
65 </div>
66 <!-- ======================================================================= -->
69 <p>Amongst other things, LLVM is a platform for compiler writers.
70 Because of its exceptionally clean and small IR (intermediate
71 representation), compiler writing with LLVM is much easier than with
72 other system. As proof, I wrote the entire compiler (language definition,
74 That's important to know because it shows how quickly you can get a new
76 language the author ever created using LLVM. The learning curve is
77 included in that four days.</p>
78 <p>The language described here, Stacker, is Forth-like. Programs
79 are simple collections of word definitions, and the only thing definitions
80 can do is manipulate a stack or generate I/O. Stacker is not a "real"
81 programming language; it's very simple. Although it is computationally
82 complete, you wouldn't use it for your next big project. However,
84 a C-like syntax make it useful for demonstration purposes. It shows
85 that LLVM could be applied to a wide variety of languages.</p>
86 <p>The basic notions behind stacker is very simple. There's a stack of
87 integers (or character pointers) that the program manipulates. Pretty
88 much the only thing the program can do is manipulate the stack and do
89 some limited I/O operations. The language provides you with several
90 built-in words that manipulate the stack in interesting ways. To get
91 your feet wet, here's how you write the traditional "Hello, World"
92 program in Stacker:</p>
94 : MAIN hello_world ;<br></code></p>
105 written Stacker definitions have that characteristic. </p>
107 </div>
108 <!-- ======================================================================= -->
112 <ol>
115 </ol>
116 <p>During the development of Stacker, many lessons about LLVM were
117 learned. Those lessons are described in the following subsections.<p>
118 </div>
119 <!-- ======================================================================= -->
122 <p>Although I knew that LLVM uses a Single Static Assignment (SSA) format,
123 it wasn't obvious to me how prevalent this idea was in LLVM until I really
126 I noted that most of the important LLVM IR (Intermediate Representation) C++
127 classes were derived from the Value class. The full power of that simple
128 design only became fully understood once I started constructing executable
129 expressions for Stacker.</p>
131 <p>This really makes your programming go faster. Think about compiling code
133 the values are on the stack in the order a, b, x, y, this could be
135 You could write a function using LLVM that computes this expression like
136 this: </p>
139 Value*
140 expression(BasicBlock* bb, Value* a, Value* b, Value* x, Value* y )
141 {
142 ConstantInt* one = ConstantInt::get(Type::IntTy, 1);
143 BinaryOperator* or1 = BinaryOperator::createOr(a, b, "", bb);
144 BinaryOperator* add1 = BinaryOperator::createAdd(x, one, "", bb);
145 BinaryOperator* add2 = BinaryOperator::createAdd(y, one, "", bb);
146 BinaryOperator* div1 = BinaryOperator::createDiv(add1, add2, "", bb);
147 BinaryOperator* mult1 = BinaryOperator::createMul(or1, div1, "", bb);
148 return mult1;
149 }
150 </pre></div>
153 have to tell this function which kinds of Values are being passed in. They could be
156 Furthermore, if you specify Values that are incorrect for this sequence of
157 operations, LLVM will either notice right away (at compilation time) or the LLVM
158 Verifier will pick up the inconsistency when the compiler runs. In either case
159 LLVM prevents you from making a type error that gets passed through to the
161 always generates correct code!<p>
162 <p>The second point is that we don't have to worry about branching, registers,
163 stack variables, saving partial results, etc. The instructions we create
166 the resulting value of that instruction. This saves a lot of time.</p>
168 between a value and the instruction that created it.</em> This is fully
169 enforced by the LLVM IR. Use it to your best advantage.</p>
170 </div>
171 <!-- ======================================================================= -->
174 <p>I had to learn about terminating blocks the hard way: using the debugger
175 to figure out what the LLVM verifier was trying to tell me and begging for
176 help on the LLVMdev mailing list. I hope you avoid this experience.</p>
178 <ul>
180 terminated with a terminating instruction (branch, return, etc.).
181 </li>
182 </ul>
183 <p>Terminating instructions are a semantic requirement of the LLVM IR. There
184 is no facility for implicitly chaining together blocks placed into a function
185 in the order they occur. Indeed, in the general case, blocks will not be
186 added to the function in the order of execution because of the recursive
187 way compilers are written.</p>
188 <p>Furthermore, if you don't terminate your blocks, your compiler code will
189 compile just fine. You won't find out about the problem until you're running
190 the compiler and the module you just created fails on the LLVM Verifier.</p>
191 </div>
192 <!-- ======================================================================= -->
195 <p>After a little initial fumbling around, I quickly caught on to how blocks
196 should be constructed. In general, here's what I learned:
197 <ol>
199 will encounter several situations where you know apriori that you will
200 need several blocks. For example, if-then-else, switch, while, and for
201 statements in C/C++ all need multiple blocks for expression in LLVM.
202 The rule is, create them early.</li>
204 that you forget to terminate your blocks which is required (go
207 that many of the constructors for the Instruction classes take an optional
209 because clearly the normal mode of inserting instructions would be one at
211 if you hold on to your terminating instruction (or use the handy dandy
214 constructors. This causes the instruction to automatically be inserted in
215 the RightPlace™ place, just before the terminating instruction. The
216 nice thing about this design is that you can pass blocks around and insert
217 new instructions into them without ever knowing what instructions came
218 before. This makes for some very clean compiler design.</li>
219 </ol>
221 <pre>
222 BasicBlock* bb = new BasicBlock();
223 bb->getInstList().push_back( new Branch( ... ) );
224 new Instruction(..., bb->getTerminator() );
225 </pre>
226 <p>To make this clear, consider the typical if-then-else statement
227 (see StackerCompiler::handle_if() method). We can set this up
228 in a single function using LLVM in the following way: </p>
229 <pre>
230 using namespace llvm;
231 BasicBlock*
232 MyCompiler::handle_if( BasicBlock* bb, ICmpInst* condition )
233 {
234 // Create the blocks to contain code in the structure of if/then/else
235 BasicBlock* then_bb = new BasicBlock();
236 BasicBlock* else_bb = new BasicBlock();
237 BasicBlock* exit_bb = new BasicBlock();
239 // Insert the branch instruction for the "if"
240 bb->getInstList().push_back( new BranchInst( then_bb, else_bb, condition ) );
242 // Set up the terminating instructions
243 then->getInstList().push_back( new BranchInst( exit_bb ) );
244 else->getInstList().push_back( new BranchInst( exit_bb ) );
246 // Fill in the then part .. details excised for brevity
247 this->fill_in( then_bb );
249 // Fill in the else part .. details excised for brevity
250 this->fill_in( else_bb );
252 // Return a block to the caller that can be filled in with the code
253 // that follows the if/then/else construct.
254 return exit_bb;
255 }
256 </pre>
259 of the idiom almost exclusively (inserting new instructions before the
261 should they encounter another if/then/else statement, and it will just work.</p>
262 <p>Note how cleanly this all works out. In particular, the push_back methods on
266 arguments the blocks to branch to and the condition to branch on. The
269 as an argument. To give the caller a way to keep inserting after calling
271 returned
276 </p>
277 </div>
278 <!-- ======================================================================= -->
281 <p>
282 One of the first things I noticed is the frequent use of the "push_back"
283 method on the various lists. This is so common that it is worth mentioning.
284 The "push_back" inserts a value into an STL list, vector, array, etc. at the
286 Although I've used STL quite frequently, my use of push_back wasn't very
287 high in other programs. In LLVM, you'll use it all the time.
288 </p>
289 </div>
290 <!-- ======================================================================= -->
293 <p>
294 It took a little getting used to and several rounds of postings to the LLVM
295 mailing list to wrap my head around this instruction correctly. Even though I had
296 read the Language Reference and Programmer's Manual a couple times each, I still
298 </p>
299 <ul>
302 <li>Pointers must also be dereferenced with the GetElementPtrInst
303 instruction.</li>
304 </ul>
305 <p>This means that when you look up an element in the global variable (assuming
307 things, this leads to the idiom:
308 </p>
309 <pre>
311 index_vector.push_back( ConstantInt::get( Type::LongTy, 0 );
312 // ... push other indices ...
313 GetElementPtrInst* gep = new GetElementPtrInst( ptr, index_vector );
314 </pre>
317 array, we need two indices, not just one. The first index (0) dereferences the
318 pointer. The second index subscripts the array. If you're a "C" programmer, this
319 will run against your grain because you'll naturally think of the global array
320 variable and the address of its first element as the same. That tripped me up
322 Remember that LLVM is strongly typed. Everything has a type.
324 a pointer to an array of 24 ints. When you dereference that global variable with
326 the pointer value of the dereferenced global and the address of the zero'th element
327 in the array will be the same, they differ in their type. The zero'th element has
329 <p>Get this one aspect of LLVM right in your head, and you'll save yourself
330 a lot of compiler writing headaches down the road.</p>
331 </div>
332 <!-- ======================================================================= -->
335 <p>Linkage types in LLVM can be a little confusing, especially if your compiler
336 writing mind has affixed firm concepts to particular words like "weak",
338 definitions of, say, ELF or GCC, even though they share common terms. To be fair,
339 the concepts are related and similar but not precisely the same. This can lead
340 you to think you know what a linkage type represents but in fact it is slightly
341 different. I recommend you read the
343 carefully. Then, read it again.<p>
345 <ul>
347 module and can be used by that module, but it is not defined by that module.</li>
349 initializer changes a global's linkage type from whatever it was to a normal,
350 defined global (not external). You'll need to call the setLinkage() method to
351 reset it if you specify the initializer after the GlobalValue has been constructed.
352 This is important for LinkOnce and Weak linkage types.</li>
354 be used to keep track of compilation information at runtime. It could be used,
355 for example, to build a full table of all the C++ virtual tables or hold the
356 C++ RTTI data, or whatever. Appending linkage can only be applied to arrays.
357 All arrays with the same name in each module are concatenated together at link
358 time.</li>
359 </ul>
360 </div>
361 <!-- ======================================================================= -->
364 <p>
365 Constants in LLVM took a little getting used to until I discovered a few utility
366 functions in the LLVM IR that make things easier. Here's what I learned: </p>
367 <ul>
370 methods of the ConstantInt class. The nice thing about these is that you can
372 <li>There's a special method on Constant class which allows you to get the null
374 arrays or structures, etc.</li>
375 </ul>
376 </div>
377 <!-- ======================================================================= -->
382 <p>Stacker definitions define what they do to the global stack. Before
383 proceeding, a few words about the stack are in order. The stack is simply
384 a global array of 32-bit integers or pointers. A global index keeps track
385 of the location of the top of the stack. All of this is hidden from the
386 programmer, but it needs to be noted because it is the foundation of the
387 conceptual programming model for Stacker. When you write a definition,
388 you are, essentially, saying how you want that definition to manipulate
389 the global stack.</p>
390 <p>Manipulating the stack can be quite hazardous. There is no distinction
391 given and no checking for the various types of values that can be placed
392 on the stack. Automatic coercion between types is performed. In many
393 cases, this is useful. For example, a boolean value placed on the stack
394 can be interpreted as an integer with good results. However, using a
395 word that interprets that boolean value as a pointer to a string to
396 print out will almost always yield a crash. Stacker simply leaves it
397 to the programmer to get it right without any interference or hindering
398 on interpretation of the stack values. You've been warned. :) </p>
399 </div>
400 <!-- ======================================================================= -->
403 <p>Punctuation in Stacker is very simple. The colon and semi-colon
404 characters are used to introduce and terminate a definition
406 are all you can specify in Stacker. Definitions are read left to right.
407 Immediately after the colon comes the name of the word being defined.
408 The remaining words in the definition specify what the word does. The definition
409 is terminated by a semi-colon.</p>
413 only letters, numbers, and underscore. Names are case sensitive and must not be
416 </div>
417 <!-- ======================================================================= -->
420 <p>Stacker supports two types of comments. A hash mark (#) starts a comment
421 that extends to the end of the line. It is identical to the kind of comments
422 commonly used in shell scripts. A pair of parentheses also surround a comment.
423 In both cases, the content of the comment is ignored by the Stacker compiler. The
424 following does nothing in Stacker.
425 </p>
426 <pre><code>
427 # This is a comment to end of line
428 ( This is an enclosed comment )
429 </code></pre>
431 a real program.</p>
432 </div>
433 <!-- ======================================================================= -->
436 <p>There are three kinds of literal values in Stacker: Integers, Strings,
437 and Booleans. In each case, the stack operation is to simply push the
438 value on to the stack. So, for example:<br/>
440 will push three values on to the stack: the integer 42, the
442 </div>
443 <!-- ======================================================================= -->
446 <p>Each definition in Stacker is composed of a set of words. Words are
447 read and executed in order from left to right. There is very little
448 checking in Stacker to make sure you're doing the right thing with
449 the stack. It is assumed that the programmer knows how the stack
450 transformation he applies will affect the program.</p>
451 <p>Words in a definition come in two flavors: built-in and programmer
452 defined. Simply mentioning the name of a previously defined or declared
453 programmer-defined word causes that word's stack actions to be invoked. It
454 is somewhat like a function call in other languages. The built-in
456 <p>Sometimes you need to call a word before it is defined. For this, you can
460 that is defined elsewhere. Generally it means the definition can be found
461 "forward" in the file. But, it doesn't have to be in the current compilation
463 linking.</p>
464 </div>
465 <!-- ======================================================================= -->
469 </div>
470 <!-- ======================================================================= -->
473 <p>The built-in words of the Stacker language are put in several groups
474 depending on what they do. The groups are as follows:</p>
475 <ol>
484 its elements around.<br/> The words are: DROP DROP2 NIP NIP2 DUP DUP2
485 SWAP SWAP2 OVER OVER2 ROT ROT2 RROT RROT2 TUCK TUCK2 PICK SELECT ROLL</li>
491 and input on the standard input. No other I/O is possible in Stacker.
493 </ol>
494 <p>While you may be familiar with many of these operations from other
495 programming languages, a careful review of their semantics is important
496 for correct programming in Stacker. Of most importance is the effect
497 that each of these built-in words has on the global stack. The effect is
498 not always intuitive. To better describe the effects, we'll borrow from Forth the idiom of
499 describing the effect on the stack with:</p>
501 <p>That is, to the left of the -- is a representation of the stack before
502 the operation. To the right of the -- is a representation of the stack
503 after the operation. In the table below that describes the operation of
504 each of the built in words, we will denote the elements of the stack
505 using the following construction:</p>
506 <ol>
511 </ol>
512 </div>
514 <table>
517 <tr>
522 </tr>
523 <tr>
527 <td>Two values (w1 and w2) are popped off the stack and
528 compared. If w1 is less than w2, TRUE is pushed back on
529 the stack, otherwise FALSE is pushed back on the stack.</td>
530 </tr>
534 <td>Two values (w1 and w2) are popped off the stack and
535 compared. If w1 is greater than w2, TRUE is pushed back on
536 the stack, otherwise FALSE is pushed back on the stack.</td>
537 </tr>
541 <td>Two values (w1 and w2) are popped off the stack and
542 compared. If w1 is greater than or equal to w2, TRUE is
543 pushed back on the stack, otherwise FALSE is pushed back
544 on the stack.</td>
545 </tr>
549 <td>Two values (w1 and w2) are popped off the stack and
550 compared. If w1 is less than or equal to w2, TRUE is
551 pushed back on the stack, otherwise FALSE is pushed back
552 on the stack.</td>
553 </tr>
557 <td>Two values (w1 and w2) are popped off the stack and
558 compared. If w1 is equal to w2, TRUE is
559 pushed back on the stack, otherwise FALSE is pushed back
560 </td>
561 </tr>
565 <td>Two values (w1 and w2) are popped off the stack and
566 compared. If w1 is equal to w2, TRUE is
567 pushed back on the stack, otherwise FALSE is pushed back
568 </td>
569 </tr>
574 </tr>
579 </tr>
581 <tr>
586 </tr>
590 <td>Two values (w1 and w2) are popped off the stack. The w2
591 operand is shifted left by the number of bits given by the
592 w1 operand. The result is pushed back to the stack.</td>
593 </tr>
597 <td>Two values (w1 and w2) are popped off the stack. The w2
598 operand is shifted right by the number of bits given by the
599 w1 operand. The result is pushed back to the stack.</td>
600 </tr>
604 <td>Two values (w1 and w2) are popped off the stack. The values
605 are bitwise OR'd together and pushed back on the stack. This is
607 </tr>
611 <td>Two values (w1 and w2) are popped off the stack. The values
612 are bitwise AND'd together and pushed back on the stack. This is
614 </tr>
618 <td>Two values (w1 and w2) are popped off the stack. The values
619 are bitwise exclusive OR'd together and pushed back on the stack.
621 </tr>
623 <tr>
628 </tr>
632 <td>One value s popped off the stack; its absolute value is computed
635 </tr>
639 <td>One value is popped off the stack which is negated and then
642 </tr>
646 <td>Two values are popped off the stack. Their sum is pushed back
647 on to the stack</td>
648 </tr>
652 <td>Two values are popped off the stack. Their difference is pushed back
653 on to the stack</td>
654 </tr>
658 <td>Two values are popped off the stack. Their product is pushed back
659 on to the stack</td>
660 </tr>
664 <td>Two values are popped off the stack. Their quotient is pushed back
665 on to the stack</td>
666 </tr>
670 <td>Two values are popped off the stack. Their remainder after division
671 of w1 by w2 is pushed back on to the stack</td>
672 </tr>
676 <td>Three values are popped off the stack. The product of w1 and w2 is
677 divided by w3. The result is pushed back on to the stack.</td>
678 </tr>
682 <td>One value is popped off the stack. It is incremented by one and then
683 pushed back on to the stack.</td>
684 </tr>
688 <td>One value is popped off the stack. It is decremented by one and then
689 pushed back on to the stack.</td>
690 </tr>
694 <td>Two values are popped off the stack. The larger one is pushed back
695 on to the stack.</td>
696 </tr>
700 <td>Two values are popped off the stack. The larger value is pushed back
701 on to the stack.</td>
702 </tr>
704 <tr>
709 </tr>
714 </tr>
719 </tr>
723 <td>The second value on the stack is removed from the stack. That is,
724 a value is popped off the stack and retained. Then a second value is
725 popped and the retained value is pushed.</td>
726 </tr>
730 <td>The third and fourth values on the stack are removed from it. That is,
731 two values are popped and retained. Then two more values are popped and
732 the two retained values are pushed back on.</td>
733 </tr>
737 <td>One value is popped off the stack. That value is then pushed on to
738 the stack twice to duplicate the top stack vaue.</td>
739 </tr>
743 <td>The top two values on the stack are duplicated. That is, two vaues
744 are popped off the stack. They are alternately pushed back on the
745 stack twice each.</td>
746 </tr>
750 <td>The top two stack items are reversed in their order. That is, two
751 values are popped off the stack and pushed back on to the stack in
752 the opposite order they were popped.</td>
753 </tr>
757 <td>The top four stack items are swapped in pairs. That is, two values
758 are popped and retained. Then, two more values are popped and retained.
759 The values are pushed back on to the stack in the reverse order but
760 in pairs.</td>
761 </tr>
765 <td>Two values are popped from the stack. They are pushed back
766 on to the stack in the order w1 w2 w1. This seems to cause the
768 </tr>
772 <td>The third and fourth values on the stack are replicated on to the
773 top of the stack</td>
774 </tr>
778 <td>The top three values are rotated. That is, three value are popped
779 off the stack. They are pushed back on to the stack in the order
780 w1 w3 w2.</td>
781 </tr>
785 <td>Like ROT but the rotation is done using three pairs instead of
786 three singles.</td>
787 </tr>
791 <td>Reverse rotation. Like ROT, but it rotates the other way around.
792 Essentially, the third element on the stack is moved to the top
793 of the stack.</td>
794 </tr>
798 <td>Double reverse rotation. Like RROT but the rotation is done using
799 three pairs instead of three singles. The fifth and sixth stack
800 elements are moved to the first and second positions</td>
801 </tr>
805 <td>Similar to OVER except that the second operand is being
806 replicated. Essentially, the first operand is being "tucked"
807 in between two instances of the second operand. Logically, two
808 values are popped off the stack. They are placed back on the
809 stack in the order w2 w1 w2.</td>
810 </tr>
814 <td>Like TUCK but a pair of elements is tucked over two pairs.
815 That is, the top two elements of the stack are duplicated and
816 inserted into the stack at the fifth and positions.</td>
817 </tr>
821 <td>The top of the stack is used as an index into the remainder of
822 the stack. The element at the nth position replaces the index
823 (top of stack). This is useful for cycling through a set of
824 values. Note that indexing is zero based. So, if n=0 then you
825 get the second item on the stack. If n=1 you get the third, etc.
826 Note also that the index is replaced by the n'th value. </td>
827 </tr>
831 <td>This is like PICK but the list is removed and you need to specify
832 both the index and the size of the list. Careful with this one,
833 the wrong value for n can blow away a huge amount of the stack.</td>
834 </tr>
840 a value, "n", to be on the top of the stack. This value specifies how
842 copied) from its location and replaces the "n" value on the top of the
843 stack. In this way, all the values between "n" and x0 roll up the stack.
844 The operation of ROLL is a generalized ROT. The "n" value specifies
845 how much to rotate. That is, ROLL with n=1 is the same as ROT and
847 </tr>
849 <tr>
854 </tr>
858 <td>One value is popped off the stack. The value is used as the size
859 of a memory block to allocate. The size is in bytes, not words.
860 The memory allocation is completed and the address of the memory
861 block is pushed on to the stack.</td>
862 </tr>
866 <td>One pointer value is popped off the stack. The value should be
867 the address of a memory block created by the MALLOC operation. The
868 associated memory block is freed. Nothing is pushed back on the
869 stack. Many bugs can be created by attempting to FREE something
870 that isn't a pointer to a MALLOC allocated memory block. Make
871 sure you know what's on the stack. One way to do this is with
872 the following idiom:<br/>
874 <br/>This ensures that an extra copy of the pointer is placed on
875 the stack (for the FREE at the end) and that every use of the
876 pointer is preceded by a DUP to retain the copy for FREE.</td>
877 </tr>
881 <td>An integer index and a pointer to a memory block are popped of
882 the block. The index is used to index one byte from the memory
883 block. That byte value is retained, the pointer is pushed again
884 and the retained value is pushed. Note that the pointer value
885 s essentially retained in its position so this doesn't count
887 </tr>
891 <td>An integer value is popped of the stack. This is the value to
892 be put into a memory block. Another integer value is popped of
893 the stack. This is the indexed byte in the memory block. A
894 pointer to the memory block is popped off the stack. The
895 first value (w1) is then converted to a byte and written
896 to the element of the memory block(p) at the index given
897 by the second value (w2). The pointer to the memory block is
898 pushed back on the stack so this doesn't count as a "use ptr"
899 in the FREE idiom.</td>
900 </tr>
902 <tr>
907 </tr>
911 <td>The currently executing definition returns immediately to its caller.
913 definition, logically located at the semi-colon. The sequence
915 </tr>
919 <td>A return value for the program is popped off the stack. The program is
920 then immediately terminated. This is normally an abnormal exit from the
922 code will always be zero in accordance with UNIX conventions.</td>
923 </tr>
927 <td>The currently executed definition is called again. This operation is
928 needed since the definition of a word doesn't exist until the semi colon
929 is reacher. Attempting something like:<br/>
931 "recurser" is not defined yet. To accomplish the same thing, change this
932 to:<br/>
934 </tr>
939 are executed. Otherwise, execution continues immediately following the ENDIF.</td>
940 </tr>
945 between IF and ELSE are executed. Otherwise the words between ELSE and ENDIF are
946 executed. In either case, after the (words....) have executed, execution continues
947 immediately following the ENDIF. </td>
948 </tr>
952 <td>The boolean value on the top of the stack is examined (not popped). If
953 it is non-zero then the "word" between WHILE and END is executed.
954 Execution then begins again at the WHILE where the boolean on the top of
955 the stack is examined again. The stack is not modified by the WHILE...END
956 loop, only examined. It is imperative that the "word" in the body of the
957 loop ensure that the top of the stack contains the next boolean to examine
958 when it completes. Note that since booleans and integers can be coerced
961 For example:<br/>
964 stack. Since that is non-zero, the while loop is entered. The top of
966 decremented, yielding 9 and control is transfered back to the WHILE
967 keyword. The process starts all over again and repeats until
968 the top of stack is decremented to 0 at which point the WHILE test
969 fails and control is transfered to the word after the END.
970 </td>
971 </tr>
973 <tr>
978 </tr>
983 </tr>
988 </tr>
993 </tr>
998 </tr>
1002 <td>A value is popped from the stack. It is put out as a decimal
1003 integer.</td>
1004 </tr>
1008 <td>A value is popped from the stack. It is put out as an ASCII
1009 character.</td>
1010 </tr>
1015 The resulting string is pushed on to the stack.</td>
1016 </tr>
1021 The resulting value is pushed on to the stack</td>
1022 </tr>
1028 </tr>
1032 <td>The stack contents are dumped to standard output. This is useful for
1033 debugging your definitions. Put DUMP at the beginning and end of a definition
1034 to see instantly the net effect of the definition.</td>
1035 </tr>
1036 </table>
1038 </div>
1039 <!-- ======================================================================= -->
1042 <p>The following fully documented program highlights many features of both
1043 the Stacker language and what is possible with LLVM. The program has two modes
1044 of operation. If you provide numeric arguments to the program, it checks to see
1045 if those arguments are prime numbers and prints out the results. Without any
1046 arguments, the program prints out any prime numbers it finds between 1 and one
1047 million (there's a lot of them!). The source code comments below tell the
1048 remainder of the story.
1049 </p>
1050 </div>
1052 <pre><code>
1053 ################################################################################
1054 #
1055 # Brute force prime number generator
1056 #
1057 # This program is written in classic Stacker style, that being the style of a
1058 # stack. Start at the bottom and read your way up !
1059 #
1060 # Reid Spencer - Nov 2003
1061 ################################################################################
1062 # Utility definitions
1063 ################################################################################
1064 : print >d CR ;
1065 : it_is_a_prime TRUE ;
1066 : it_is_not_a_prime FALSE ;
1067 : continue_loop TRUE ;
1068 : exit_loop FALSE;
1070 ################################################################################
1071 # This definition tries an actual division of a candidate prime number. It
1072 # determines whether the division loop on this candidate should continue or
1073 # not.
1074 # STACK<:
1075 # div - the divisor to try
1076 # p - the prime number we are working on
1077 # STACK>:
1078 # cont - should we continue the loop ?
1079 # div - the next divisor to try
1080 # p - the prime number we are working on
1081 ################################################################################
1082 : try_dividing
1083 DUP2 ( save div and p )
1084 SWAP ( swap to put divisor second on stack)
1086 IF
1087 exit_loop ( remainder = 0, time to exit )
1088 ELSE
1089 continue_loop ( remainder != 0, keep going )
1090 ENDIF
1091 ;
1093 ################################################################################
1094 # This function tries one divisor by calling try_dividing. But, before doing
1095 # that it checks to see if the value is 1. If it is, it does not bother with
1096 # the division because prime numbers are allowed to be divided by one. The
1097 # top stack value (cont) is set to determine if the loop should continue on
1098 # this prime number or not.
1099 # STACK<:
1100 # cont - should we continue the loop (ignored)?
1101 # div - the divisor to try
1102 # p - the prime number we are working on
1103 # STACK>:
1104 # cont - should we continue the loop ?
1105 # div - the next divisor to try
1106 # p - the prime number we are working on
1107 ################################################################################
1108 : try_one_divisor
1109 DROP ( drop the loop continuation )
1110 DUP ( save the divisor )
1112 exit_loop ( no point dividing by 1 )
1113 ELSE
1114 try_dividing ( have to keep going )
1115 ENDIF
1116 SWAP ( get divisor on top )
1117 -- ( decrement it )
1118 SWAP ( put loop continuation back on top )
1119 ;
1121 ################################################################################
1122 # The number on the stack (p) is a candidate prime number that we must test to
1123 # determine if it really is a prime number. To do this, we divide it by every
1125 # definition which returns a loop continuation value (which we also seed with
1126 # the value 1). After the loop, we check the divisor. If it decremented all
1127 # the way to zero then we found a prime, otherwise we did not find one.
1128 # STACK<:
1129 # p - the prime number to check
1130 # STACK>:
1131 # yn - boolean indicating if its a prime or not
1132 # p - the prime number checked
1133 ################################################################################
1134 : try_harder
1135 DUP ( duplicate to get divisor value ) )
1136 -- ( first divisor is one less than p )
1137 1 ( continue the loop )
1138 WHILE
1139 try_one_divisor ( see if its prime )
1140 END
1141 DROP ( drop the continuation value )
1143 it_is_a_prime ( we found one )
1144 ELSE
1145 it_is_not_a_prime ( nope, this one is not a prime )
1146 ENDIF
1147 ;
1149 ################################################################################
1150 # This definition determines if the number on the top of the stack is a prime
1152 # responding with yes, its a prime. Otherwise, it calls try_harder to actually
1153 # make some calculations to determine its primeness.
1154 # STACK<:
1155 # p - the prime number to check
1156 # STACK>:
1157 # yn - boolean indicating if its a prime or not
1158 # p - the prime number checked
1159 ################################################################################
1160 : is_prime
1161 DUP ( save the prime number )
1163 it_is_a_prime ( its <= 3 just indicate its prime )
1164 ELSE
1165 try_harder ( have to do a little more work )
1166 ENDIF
1167 ;
1169 ################################################################################
1170 # This definition is called when it is time to exit the program, after we have
1171 # found a sufficiently large number of primes.
1172 # STACK<: ignored
1173 # STACK>: exits
1174 ################################################################################
1175 : done
1177 0 EXIT ( exit nicely )
1178 ;
1180 ################################################################################
1181 # This definition checks to see if the candidate is greater than the limit. If
1182 # it is, it terminates the program by calling done. Otherwise, it increments
1183 # the value and calls is_prime to determine if the candidate is a prime or not.
1184 # If it is a prime, it prints it. Note that the boolean result from is_prime is
1185 # gobbled by the following IF which returns the stack to just contining the
1186 # prime number just considered.
1187 # STACK<:
1188 # p - one less than the prime number to consider
1189 # STAC>K
1190 # p+1 - the prime number considered
1191 ################################################################################
1192 : consider_prime
1193 DUP ( save the prime number to consider )
1195 done ( we are done, call "done" )
1196 ENDIF
1197 ++ ( increment to next prime number )
1198 is_prime ( see if it is a prime )
1199 IF
1200 print ( it is, print it )
1201 ENDIF
1202 ;
1204 ################################################################################
1205 # This definition starts at one, prints it out and continues into a loop calling
1206 # consider_prime on each iteration. The prime number candidate we are looking at
1207 # is incremented by consider_prime.
1208 # STACK<: empty
1209 # STACK>: empty
1210 ################################################################################
1211 : find_primes
1213 DROP ( get rid of that pesky string )
1214 1 ( stoke the fires )
1215 print ( print the first one, we know its prime )
1216 WHILE ( loop while the prime to consider is non zero )
1217 consider_prime ( consider one prime number )
1218 END
1219 ;
1221 ################################################################################
1222 #
1223 ################################################################################
1224 : say_yes
1225 >d ( Print the prime number )
1226 " is prime." ( push string to output )
1227 >s ( output it )
1228 CR ( print carriage return )
1229 DROP ( pop string )
1230 ;
1232 : say_no
1233 >d ( Print the prime number )
1234 " is NOT prime." ( push string to put out )
1235 >s ( put out the string )
1236 CR ( print carriage return )
1237 DROP ( pop string )
1238 ;
1240 ################################################################################
1241 # This definition processes a single command line argument and determines if it
1242 # is a prime number or not.
1243 # STACK<:
1244 # n - number of arguments
1245 # arg1 - the prime numbers to examine
1246 # STACK>:
1247 # n-1 - one less than number of arguments
1248 # arg2 - we processed one argument
1249 ################################################################################
1250 : do_one_argument
1251 -- ( decrement loop counter )
1252 SWAP ( get the argument value )
1253 is_prime IF ( determine if its prime )
1254 say_yes ( uhuh )
1255 ELSE
1256 say_no ( nope )
1257 ENDIF
1258 DROP ( done with that argument )
1259 ;
1261 ################################################################################
1262 # The MAIN program just prints a banner and processes its arguments.
1263 # STACK<:
1264 # n - number of arguments
1265 # ... - the arguments
1266 ################################################################################
1267 : process_arguments
1268 WHILE ( while there are more arguments )
1269 do_one_argument ( process one argument )
1270 END
1271 ;
1273 ################################################################################
1274 # The MAIN program just prints a banner and processes its arguments.
1275 # STACK<: arguments
1276 ################################################################################
1277 : MAIN
1278 NIP ( get rid of the program name )
1279 -- ( reduce number of arguments )
1280 DUP ( save the arg counter )
1282 process_arguments ( tell user if they are prime )
1283 ELSE
1284 find_primes ( see how many we can find )
1285 ENDIF
1286 0 ( push return code )
1287 ;
1288 </code>
1289 </pre>
1290 </div>
1291 <!-- ======================================================================= -->
1296 </div>
1297 <!-- ======================================================================= -->
1300 <p>The source code, test programs, and sample programs can all be found
1305 commands:<pre>
1307 cvs co llvm-stacker</pre>
1308 </p>
1310 implementation of the Stacker compiler, as follows:</p>
1311 <ul>
1313 <ul>
1316 </ul></li>
1319 <ul>
1321 </ul</li>
1323 </ul>
1324 </div>
1325 <!-- ======================================================================= -->
1329 </div>
1330 <!-- ======================================================================= -->
1334 </div>
1335 <!-- ======================================================================= -->
1339 </div>
1340 <!-- ======================================================================= -->
1344 </div>
1345 <!-- ======================================================================= -->
1349 </div>
1350 <!-- ======================================================================= -->
1354 </div>
1355 <!-- ======================================================================= -->
1358 <p>As you may have noted from a careful inspection of the Built-In word
1359 definitions, the ROLL word is not implemented. This word was left out of
1360 Stacker on purpose so that it can be an exercise for the student. The exercise
1361 is to implement the ROLL functionality (in your own workspace) and build a test
1362 program for it. If you can implement ROLL, you understand Stacker and probably
1363 a fair amount about LLVM since this is one of the more complicated Stacker
1364 operations. The work will almost be completely limited to the
1366 <p>The ROLL word is already recognized by both the lexer and parser but ignored
1367 by the compiler. That means you don't have to futz around with figuring out how
1368 to get the keyword recognized. It already is. The part of the compiler that
1371 implementations of PICK and SELECT in the same method to get some hints about
1372 how to complete this exercise.<p>
1374 </div>
1375 <!-- ======================================================================= -->
1378 <p>The initial implementation of Stacker has several deficiencies. If you're
1379 interested, here are some things that could be implemented better:</p>
1380 <ol>
1381 <li>Write an LLVM pass to compute the correct stack depth needed by the
1382 program. Currently the stack is set to a fixed number which means programs
1383 with large numbers of definitions might fail.</li>
1384 <li>Write an LLVM pass to optimize the use of the global stack. The code
1385 emitted currently is somewhat wasteful. It gets cleaned up a lot by existing
1386 passes but more could be done.</li>
1387 <li>Make the compiler driver use the LLVM linking facilities (with IPO)
1388 before depending on GCC to do the final link.</li>
1390 <li>Rearrange the StackerCompiler.cpp code to make better use of inserting
1391 instructions before a block's terminating instruction. I didn't figure this
1392 technique out until I was nearly done with LLVM. As it is, its a bad example
1393 of how to insert instructions!</li>
1397 <li>Add your own compiler writing experiences and tips in the
1399 </ol>
1400 </div>
1402 <!-- *********************************************************************** -->
1404 <hr>
1405 <address>
1413 Last modified: $Date$
1414 </address>
1416 </body>
1417 </html>