5 Variables (Single Global Scope)

You will need to use the instructions alloca, load, store to get this working. Look at the documentation and examples there for help in getting started.

We are going to implement a single global scope first. My suggestion is that you add a map<string,string< to the context object along with methods to create a binding and fetch a binding. Remember: you are binding an SPL variable name to the name of an LLVM variable that will be a pointer to a memory location; that memory location contains the current value of "the variable". This means bindings never change - once you put something in the map for a given Id, that Id's value in the map is never reassigned.

Rather than try the full test case shown below, think about starting very small and working your way up. For example, you could first just try to get a program to compile that declares a new variable. Then try assigning a variable and printing it out right away. Starting slowly like this and working carefully, examining the code your compiler produces for very simple cases first, will make this whole lab much easier.

2. Get variable declaration with new, assignment, and lookup working. Here's a program which should work now:

   new x := 10;
   write x + 3;
   new y := x * x;
   write y;
   write y + x;
   y := 1101;
   write x+y;

6 Blocks and Lexicial Scope

So, go back to your Context class, and change to a stack of scope ... although I strongly recommend you actually use a vector with .push_back(.) and .pop_back() in place of push and pop, and .back() to peek at the top element of the stack. And then make sure you push and pop as you enter and leave blocks.

3. Get blocks and lexical scope working properly! At this point anything like the following should work properly:

   new i := 5;
   {
     new i := 10;
     write i;
     i := 11;
     write i;
   }
   write i;

7 Control

For example, a code fragment such as

ifelse 3 < 5
{ write 100; }
{ write 200; }
write 300;

might be compiled to

    %v1 = icmp slt i64 3, 5
    br i1 %v1, label %b1, label %b2
b1:
    call void(i64) @write (i64 100)
    br label %b3
b2:
    call void(i64) @write (i64 200)
    br label %b3
b3:
    call void(i64) @write (i64 300)

4. Get if/else and while statements working. After this, a program like the following should compile and run successfully:

   new secret := 42;
   new guess := read;
   while guess != secret {
     ifelse guess < secret
     { write -1; }
     { write 1; }
     guess := read;
   }
   write secret;

8 Function calls - ASSUMING NO NON-LOCAL REFERENCES & NO RECURSION

Getting functions to work really consists of two tasks. First, you have to implement function definitions, as triggered by lambda expressions in the code. Each lambda in the SPL code will correspond to one function in the LLVM IR code that your compiler produces. But at the point of the lambda itself, your compiler is in the middle of emitting code for main(), so you can't just print this function definition. I have provided a second stream for you to write to. It's called delayout. In fact, delayout is an ostringstream, which is a C++ type that is an ostream, which means you can << output to it just like cout and cerr, but it collects all that output in a string that you can access with the .str() method. The starter code is set up so that the last thing the program does is resout << delayout.str(), i.e. anything that has been written to delayout is emitted at the ind of the program. So while you're writing out main, if you come across a function, just output that function to delayout so that it is written after main. Note: to allow for lambdas containing lambdas, you may want to introduce your own ostringstream local variables. That looks like:

ostringstream myout;

At the point of the lambda itself, all your compiler needs to do is convert the function pointer to an i64 type in LLVM, using the ptrtoint-to instruction. For example, check out the very simple (and mostly pointless) SPL program below and the LLVM snippet it might compiler to. Notice how the function name @v2 has type i64(i64)*, i.e. it is a pointer to a function. Also notice that we are referring to the name in main, even though it doesn't get declared until later! There is no "declare-before-use" requirement in LLVM.

new f := lambda x { ret := x*x; };
write 456;

; ... header definitions etc up here ...
define i32 @main() {
    %v3 = ptrtoint i64(i64)* @v2 to i64
    %v1 = alloca i64
    store i64 %v3, i64* %v1
    call i32(i8*,...) @printf(i8* getelementptr([5 x i8], [5 x i8]* @pfmt, i32 0, i32 0), i64 42)
    ret i32 0
}
define i64 @v2 (i64 %v4) {
; ... you'll have to figure out what goes here, of course!
}

	  

Once you have lambdas working well, emitting code for function names like we see above, the next step is to implement function calls. Just as with your interpreter labs, I recommend starting by ignoring arguments and return values and just get the control to go to the function and come back. Just as the example above uses ptrtoint to convert the function pointer to a saved i64 value, at the function call site you will have to convert an i64 back to a function pointer using inttoptr-to.

Important! The key question you have to tackle is this: should the binding of the parameter and ret to memory locations and the storing of the argument value in the parameter's memory location happen a) the code that calls the function, or b) inside the function itself? Note: when we say "function", we're talking about the LLVM function introduced with the "define" keyword. The right answer is b! You can't follow a and do this when the function is called, because you've lost the Lambda* at that point and you won't know what the parameter name is, nor do you have the scope you want --- you won't know what LLVM variable the body of the function will be using to get the locations of the parameter and "ret". So b is the only way to go.

Exercises

5. Get function definitions and function calls working without local references. After this, you can compile some neat programs like this:

   new f := false;
   ifelse read = 2
     { f := lambda x { ret := x*x; }; }
     { f := lambda x { ret := x*x*x; }; }
   new i := 1;
   while i <= 10 {
     write f@i;
     i := i + 1;
   }

   The trickier one to get right is this:

   new g := lambda y {
       new f := lambda x { ret := x*x; };
       ret := f@(y+1);
   };		
   write g@5;

9 Choose your own adventure

Exercises

6. Implement run-time type information in your compiler. This means that you will store - at run time - an extra value alongside every actual SPL value, to hold the type of that value.
   It is up to you how to represent the types in your LLVM IR program. I recommend using an i8 value with something like 0 indicating unset, 1 indicating a number, 2 indicating a boolean, and 3 indicating a function.
   The most visible change in your program is that the write command in SPL should now respect the type of its argument, printing the value of a number, or "true"/"false" for a boolean, or "function" for a function pointer.
   In addition, you should do run-time type checking everywhere your program makes use of a value. For example, an SPL program like write 1 * false; should still compile, but produce a run-time error from the failed coversion of false to a number.
   Note 1: Your compiled program should terminate with exit code 5 when a type error occurs at run-time. You may want to use the standard C library call exit so you can safely terminate from any point in the program.
   Note 2: You may want to look into defining and using a struct type in LLVM IR, which allows you to store a (type,value) pair together in a register and/or in memory. If you go this route, be sure to look up the LLVM instructions extractvalue, insertvalue.
   (You do not need to implement the type checking builtins like isnum.)
7. Implement full lexical scope with closures, allowing non-local references in function calls. This challenging task will allow all kinds of more sophisticated SPL programs to compile, such as:

   new showx := lambda x {
     ret := lambda ignored { write x; };
   };
   new fiver := showx@5;
   new sixer := showx@6;
   fiver@0;
   sixer@0;
   fiver@0;
   fiver@0;

   (Look back to Lab 8 for many more examples!)
   To get this working, you will need to first of all allocate storage for your variables on the heap rather than the stack. Because there is no LLVM instruction to do heap allocation, you will have to do this with system calls to malloc.
   Then, you'll need to store a closure for each function declared, rather than just a pointer to the function itself. This closure needs to contain this function pointer, but also the addresses of all of the variables in scope at the point of the function definition. Then when the function begins, you will need to unwrap this closure and load those addresses back into registers.
   This will be a good challenge, but worthwhile! Ask your instructor if you run into trouble and need some help.
8. Implement the debug statement in SPL, which is any string enclosed in double-quote characters. That string should print out when the compiled program is executed, at that point in the program where the debug statement appears. See Debug's for more information!
   (This was originally an optional exercise at the end of Lab 7.)
   After this, a program like the following should compile:

   "Please enter a positive number."
   new x := read;
   ifelse x > 0
     { "Thank you and good job." }
     { "You will now be punished with 50 punches."
       new i := 0;
       while i < 50 { "punch" i := i + 1; }
     }

9. Implement built-in functions in SPL like you did for Lab 9. You should have (at least) built-in functions for sqrt, rand, and one other function of your choosing.
   The trick here will be to write the code for the built-in functions in LLVM IR and emit those function definitions every time your compiler runs. Inside your main() you'll probably have to have instructions to store those function pointers just like any other variable would be stored, so that function calls to your built-in functions work just like any other function call.
   Hint: Check out the LLVM intrinsic llvm,sqrt.
   (You do not need to implement the type checking builtins like isnum.)
10. Implement short-circuit evaluation of and and or expressions, using phi expressions in LLVM.
    Remember that short-circuiting means the second part of a boolean operation (and or or) is only evaluated if it's necessary. For example, if the first part of an and is false, then we don't need to bother with evaluating the seecond part, because we know already that the entire expression is definitely false.
    This would not be too difficult to do with a simple if/else construct, except that after the blocks come back together, you need to have just a single register that stores the result of the boolean operation. Because of the rules of SSA, you'll find that this isn't straightforward to do. To solve it, you will need to use a phi function in the first basic block after the short-circuited boolean expression completes. Look at the documentation there for guidance and ask your instructor if you need any help!
11. Right now, in order to get variables working, your compiled LLVM IR code probably does an alloca call every time a NewStmt is executed. That means a whole lot of memory gets used even for simple loops like this one to compute \(n^2\) in a very stupid way:

    new n := 1000;
    new i := 1;
    new s := 0;
    while i <= n {
      new j := 1;
      while j <= n {
        new temp := s + 1;
        s := temp;
        j := j + 1;
      }
      i := i + 1;
    }
    write s;

    If you compile and run the program above, you will most likely get a seg fault. But the issue is not in how you are allocating memory, just in how much memory you are allocating! As written, the space for variable temp gets allocated a million itmes. That should be just enough to blow through the 8MB of stack space that Linux gives you by default.
    To fix this, the trick is to allocate the space for every variable just once, at the beginning of the function. For example, the first thing in the main that your compiler outputs should statement(s) to allocate memory for all variables that are used in main. Then, each time a variable is used, you just access that memory address which was alreay allocated. In the example above, this means that the space for temp is only allocated once instead of 1 million times - hooray!

Submit

• Please submit the version without extensions as:

  submit -c=SI413 -p=lab13 *

• Please submit the version with extensions as:

  submit -c=SI413 -p=lab13-ext *

  Note: You must have a README file in your submission that clearly states which of the extensions you have done ... and "done" means it works!