Extra Project (optional)

1. Augment the Tiger compiler to produce descriptors necessary for garbage collection, as described in Chapter 13 of Appel.
2. Write a garbage collector (in C) for your Tiger compiler, as described in Chapter 13 of Appel.
3. Implement Fun-Tiger (Tiger with first-class function values), as described in Chapter 15 of Appel.
4. Implement Object-Tiger (Tiger with classes and objects) as described in Chapter 14 of Appel.
5. Enhance the register allocator to choose callee-save registers, if any are available, for temporaries live immediately after a CALL, and to choose caller-save registers for those not live after any call. This will minimize saving and restoring.
6. Implement spilling in the register allocator, local variables a Tiger program has, you can still compile it.
7. Implement coalescing in the register allocator, to eliminate practically all the MOVE instructions from the program.
8. Figure out other approaches to improving the assembly-language generated by your compiler. Describe on paper; perhaps implement.
9. Implement instruction scheduling to fill branch-delay and load-delay slots in the assembly language. Or, discuss how such a module could be integrated into the existing compiler; what interfaces would have to change, and in what ways.
10. Implement ``perfect pipelining'' (scheduling without worrying about resource constraints) in your compiler.
11. Analyze how adequate the Tiger language itself would be for writing a compiler. What are the smallest possible additions/changes that would make it a much more useful language?
12. In the Tiger language, some record types are recursive and must be implemented as pointers; others are not recursive and could be implemented without pointers. Modify your compiler to take advantage of this.
13. Similarly, some arrays have bounds known at compile time, are not recursive, and are not assigned to other array variables. Modify your compiler so that these arrays are implemented right in the stack frame.
14. Research approaches to alias analysis: that is, given two pointer variables at some point in a program, can they point to the same record or not? Show applications where this information is important.
15. Implement in-line expansion of functions.
16. Suppose an ordinary Tiger program were to run on a parallel machine (a multiprocessor)? How could the compiler automatically make a parallel program out of the original sequential one? Research the approaches.
17. Pick some other optimizations from Chapter 16 or 17 of Appel, and show how they would fit into your compiler.
18. Choose some other compiler-related project not on this list.