From e46d601ffd85b3d886709a028259f9e2e881f323 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Tue, 25 Nov 2003 01:35:06 +0000 Subject: Apply docs patch fro Reid git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10201 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/Stacker.html | 174 +++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 125 insertions(+), 49 deletions(-) (limited to 'docs/Stacker.html') diff --git a/docs/Stacker.html b/docs/Stacker.html index eabccdf6cf..fbdc5bd2ec 100644 --- a/docs/Stacker.html +++ b/docs/Stacker.html @@ -25,8 +25,10 @@
  1. The Stack
  2. Punctuation +
  3. Comments
  4. Literals
  5. Words +
  6. Standard Style
  7. Built-Ins
@@ -40,6 +42,8 @@
  • The Runtime
  • Compiler Driver
  • Test Programs
    • +
  • Exercise
    • +
  • Things Remaining To Be Done
    • @@ -53,9 +57,9 @@

    This document is another way to learn about LLVM. Unlike the LLVM Reference Manual or -LLVM Programmer's Manual, this -document walks you through the implementation of a programming language -named Stacker. Stacker was invented specifically as a demonstration of +LLVM Programmer's Manual, we learn +about LLVM through the experience of creating a simple programming language +named Stacker. Stacker was invented specifically as a demonstration of LLVM. The emphasis in this document is not on describing the intricacies of LLVM itself, but on how to use it to build your own compiler system.

    @@ -80,7 +84,7 @@ programming language; its very simple. Although it is computationally complete, you wouldn't use it for your next big project. However, the fact that it is complete, its simple, and it doesn't have a C-like syntax make it useful for demonstration purposes. It shows -that LLVM could be applied to a wide variety of language syntaxes.

    +that LLVM could be applied to a wide variety of languages.

    The basic notions behind stacker is very simple. There's a stack of integers (or character pointers) that the program manipulates. Pretty much the only thing the program can do is manipulate the stack and do @@ -106,24 +110,30 @@ written Stacker definitions have that characteristic.

    Lessons I Learned About LLVM
    -

    Stacker was written for two purposes: (a) to get the author over the -learning curve and (b) to provide a simple example of how to write a compiler -using LLVM. During the development of Stacker, many lessons about LLVM were +

    Stacker was written for two purposes:

    +
      +
    1. to get the author over the learning curve, and
      2. +
    2. to provide a simple example of how to write a compiler using LLVM.
      3. +
    +

    During the development of Stacker, many lessons about LLVM were learned. Those lessons are described in the following subsections.

    Everything's a Value!
    -

    Although I knew that LLVM used a Single Static Assignment (SSA) format, +

    Although I knew that LLVM uses a Single Static Assignment (SSA) format, it wasn't obvious to me how prevalent this idea was in LLVM until I really -started using it. Reading the Programmer's Manual and Language Reference I -noted that most of the important LLVM IR (Intermediate Representation) C++ +started using it. Reading the +Programmer's Manual and Language Reference +I noted that most of the important LLVM IR (Intermediate Representation) C++ 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.

    This really makes your programming go faster. Think about compiling code -for the following C/C++ expression: (a|b)*((x+1)/(y+1)). You could write a -function using LLVM that does exactly that, this way:

    +for the following C/C++ expression: (a|b)*((x+1)/(y+1)). Assuming +the values are on the stack in the order a, b, x, y, this could be +expressed in stacker as: 1 + SWAP 1 + / ROT2 OR *. +You could write a function using LLVM that computes this expression like this: 

    
 Value* 
 expression(BasicBlock*bb, Value* a, Value* b, Value* x, Value* y )
@@ -146,19 +156,19 @@ expression(BasicBlock*bb, Value* a, Value* b, Value* x, Value* y )

    "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 -instructions, Constants, Global Variables, etc. Furthermore, if you specify Values -that are incorrect for this sequence of operations, LLVM will either notice right -away (at compilation time) or the LLVM Verifier will pick up the inconsistency -when the compiler runs. In no case will you make a type error that gets passed -through to the generated program. This really helps you write a compiler -that always generates correct code!

    +Instructions, Constants, GlobalVariables, +etc. Furthermore, if you specify Values that are incorrect for this sequence of +operations, LLVM will either notice right away (at compilation time) or the LLVM +Verifier will pick up the inconsistency when the compiler runs. In no case will +you make a type error that gets passed through to the generated program. +This really helps you write a compiler that always generates correct code!

    The second point is that we don't have to worry about branching, registers, stack variables, saving partial results, etc. The instructions we create are the values we use. Note that all that was created in the above code is a Constant value and five operators. Each of the instructions is -the resulting value of that instruction.

    +the resulting value of that instruction. This saves a lot of time.

    The lesson is this: SSA form is very powerful: there is no difference - between a value and the instruction that created it. This is fully +between a value and the instruction that created it. This is fully enforced by the LLVM IR. Use it to your best advantage.

    @@ -186,8 +196,7 @@ the compiler and the module you just created fails on the LLVM Verifier.

    Concrete Blocks

    After a little initial fumbling around, I quickly caught on to how blocks -should be constructed. The use of the standard template library really helps -simply the interface. In general, here's what I learned: +should be constructed. In general, here's what I learned:

    1. Create your blocks early. While writing your compiler, you will encounter several situations where you know apriori that you will @@ -206,19 +215,17 @@ simply the interface. In general, here's what I learned: getTerminator() method on a BasicBlock), it can always be used as the insert_before argument to your instruction constructors. This causes the instruction to automatically be inserted in - the RightPlace&tm; place, just before the terminating instruction. The + the RightPlace™ place, just before the terminating instruction. The nice thing about this design is that you can pass blocks around and insert - new instructions into them without ever known what instructions came + new instructions into them without ever knowing what instructions came before. This makes for some very clean compiler design.

    The foregoing is such an important principal, its worth making an idiom:

    -
    -
+
    
 BasicBlock* bb = new BasicBlock();
 bb->getInstList().push_back( new Branch( ... ) );
 new Instruction(..., bb->getTerminator() );
-
-
    
+

    To make this clear, consider the typical if-then-else statement (see StackerCompiler::handle_if() method). We can set this up in a single function using LLVM in the following way:

    @@ -254,8 +261,7 @@ MyCompiler::handle_if( BasicBlock* bb, SetCondInst* condition ) the instructions for the "then" and "else" parts. They would use the third part of the idiom almost exclusively (inserting new instructions before the terminator). Furthermore, they could even recurse back to handle_if -should they encounter another if/then/else statement and it will all "just work". -

    +should they encounter another if/then/else statement and it will just work.

    Note how cleanly this all works out. In particular, the push_back methods on the BasicBlock's instruction list. These are lists of type Instruction which also happen to be Values. To create @@ -312,10 +318,10 @@ pointer. The second index subscripts the array. If you're a "C" programmer, this will run against your grain because you'll naturally think of the global array variable and the address of its first element as the same. That tripped me up for a while until I realized that they really do differ .. by type. -Remember that LLVM is a strongly typed language itself. Absolutely everything +Remember that LLVM is a strongly typed language itself. Everything has a type. The "type" of the global variable is [24 x int]*. That is, its a pointer to an array of 24 ints. When you dereference that global variable with -a single index, you now have a " [24 x int]" type, the pointer is gone. Although +a single (0) index, you now have a "[24 x int]" type. Although the pointer value of the dereferenced global and the address of the zero'th element in the array will be the same, they differ in their type. The zero'th element has type "int" while the pointer value has type "[24 x int]".

    @@ -333,7 +339,7 @@ the concepts are related and similar but not precisely the same. This can lead you to think you know what a linkage type represents but in fact it is slightly different. I recommend you read the Language Reference on this topic very -carefully.

    +carefully. Then, read it again.

    Here are some handy tips that I discovered along the way:

    • Unitialized means external. That is, the symbol is declared in the current @@ -366,12 +372,13 @@ functions in the LLVM IR that make things easier. Here's what I learned:

    The Stacker Lexicon
    +

    This section describes the Stacker language

    The Stack

    Stacker definitions define what they do to the global stack. Before proceeding, a few words about the stack are in order. The stack is simply a global array of 32-bit integers or pointers. A global index keeps track -of the location of the to of the stack. All of this is hidden from the +of the location of the top of the stack. All of this is hidden from the programmer but it needs to be noted because it is the foundation of the conceptual programming model for Stacker. When you write a definition, you are, essentially, saying how you want that definition to manipulate @@ -384,7 +391,7 @@ can be interpreted as an integer with good results. However, using a word that interprets that boolean value as a pointer to a string to print out will almost always yield a crash. Stacker simply leaves it to the programmer to get it right without any interference or hindering -on interpretation of the stack values. You've been warned :)

    +on interpretation of the stack values. You've been warned. :)

    Punctuation
    @@ -393,8 +400,31 @@ on interpretation of the stack values. You've been warned :)

    characters are used to introduce and terminate a definition (respectively). Except for FORWARD declarations, definitions are all you can specify in Stacker. Definitions are read left to right. -Immediately after the semi-colon comes the name of the word being defined. -The remaining words in the definition specify what the word does.

    +Immediately after the colon comes the name of the word being defined. +The remaining words in the definition specify what the word does. The definition +is terminated by a semi-colon.

    +

    So, your typical definition will have the form:

    +
    : name ... ;
    +

    The name is up to you but it must start with a letter and contain +only letters numbers and underscore. Names are case sensitive and must not be +the same as the name of a built-in word. The ... is replaced by +the stack manipulting words that you wish define name as.

    +

    + +
    Comments
    +
    +

    Stacker supports two types of comments. A hash mark (#) starts a comment + that extends to the end of the line. It is identical to the kind of comments + commonly used in shell scripts. A pair of parentheses also surround a comment. + In both cases, the content of the comment is ignored by the Stacker compiler. The + following does nothing in Stacker. +

    +
    
+# This is a comment to end of line
+( This is an enclosed comment )
+
    +

    See the example program to see how this works in +a real program.

    Literals
    @@ -416,11 +446,11 @@ the stack. It is assumed that the programmer knows how the stack transformation he applies will affect the program.

    Words in a definition come in two flavors: built-in and programmer defined. Simply mentioning the name of a previously defined or declared -programmer-defined word causes that words definition to be invoked. It +programmer-defined word causes that word's definition to be invoked. It is somewhat like a function call in other languages. The built-in words have various effects, described below.

    Sometimes you need to call a word before it is defined. For this, you can -use the FORWARD declaration. It looks like this

    +use the FORWARD declaration. It looks like this:

    FORWARD name ;

    This simply states to Stacker that "name" is the name of a definition that is defined elsewhere. Generally it means the definition can be found @@ -467,7 +497,7 @@ using the following construction:

  • b - a boolean truth value
  • w - a normal integer valued word.
  • s - a pointer to a string value
    • -
  • p - a pointer to a malloc's memory block
    • +
  • p - a pointer to a malloc'd memory block
    • @@ -775,15 +805,14 @@ using the following construction:

    ROLL x0 x1 .. xn n -- x1 .. xn x0 Not Implemented. This one has been left as an exercise to - the student. If you can implement this one you understand Stacker - and probably a fair amount about LLVM since this is one of the - more complicated Stacker operations. See the StackerCompiler.cpp - file in the projects/Stacker/lib/compiler directory. The operation - of ROLL is like a generalized ROT. That is ROLL with n=1 is the - same as ROT. The n value (top of stack) is used as an index to - select a value up the stack that is moved to the top of - the stack. See the implementations of PICk and SELECT to get - some hints.

    + the student. See Exercise. ROLL requires + a value, "n", to be on the top of the stack. This value specifies how + far into the stack to "roll". The n'th value is moved (not + copied) from its location and replaces the "n" value on the top of the + stack. In this way, all the values between "n" and x0 roll up the stack. + The operation of ROLL is a generalized ROT. The "n" value specifies + 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. MEMORY OPERATIONS WordNameOperationDescription @@ -1266,6 +1295,53 @@ directory contains everything, as follows:

    See projects/Stacker/test/*.st

    +
    Exercise
    +
    +

    As you may have noted from a careful inspection of the Built-In word +definitions, the ROLL word is not implemented. This word was left out of +Stacker on purpose so that it can be an exercise for the student. The exercise +is to implement the ROLL functionality (in your own workspace) and build a test +program for it. If you can implement ROLL you understand Stacker and probably +a fair amount about LLVM since this is one of the more complicated Stacker +operations. The work will almost be completely limited to the +compiler. +

    The ROLL word is already recognized by both the lexer and parser but ignored +by the compiler. That means you don't have to futz around with figuring out how +to get the keyword recognized. It already is. The part of the compiler that +you need to implement is the ROLL case in the +StackerCompiler::handle_word(int) method.

    See the implementations +of PICk and SELECT in the same method to get some hints about how to complete +this exercise.

    +

    Good luck!

    +
    + +
    Things Remaining To Be Done
    +
    +

    The initial implementation of Stacker has several deficiencies. If you're +interested, here are some things that could be implemented better:

    +
      +
    1. Write an LLVM pass to compute the correct stack depth needed by the + program.
      2. +
    2. 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.
      3. +
    3. Add -O -O1 -O2 and -O3 optimization switches to the compiler driver to + allow LLVM optimization without using "opt"
      4. +
    4. Make the compiler driver use the LLVM linking facilities (with IPO) before + depending on GCC to do the final link.
      5. +
    5. Clean up parsing. It doesn't handle errors very well.
      6. +
    6. Rearrange the StackerCompiler.cpp code to make better use of inserting + instructions before a block's terminating instruction. I didn't figure this + technique out until I was nearly done with LLVM. As it is, its a bad example + of how to insert instructions!
      7. +
    7. Provide for I/O to arbitrary files instead of just stdin/stdout.
      8. +
    8. Write additional built-in words.
      9. +
    9. Write additional sample Stacker programs.
      10. +
    10. Add your own compiler writing experiences and tips in the + Lessons I Learned About LLVM section.
      11. +
    +
    +
    Reid Spencer
    -- cgit v1.2.3