milestone report

Here is our milestone report from April 15 (about 1.5 weeks ago). (better late than never, right?)

What we have done so far:

1. explored LLVM's infrastructure enough to determine that its backend is not flexible/amenable enough to make global register allocation (at least, in the more sophisticated form we want to do) feasible for a 6-week project.
   
2. devised a bottom-up-and-top-down algorithm for performing GRA, in a manner that supports rewriting calling conventions per-function
3. planned new infrastructure for our undergrad compiler to support the algorithm

The major change, of course, is that we have elected to switch from LLVM to POBBLES, the C0 compiler we implemented in 15-411. We missed the milestone, which was to have a basic implementation (with few features) for LLVM working correctly.

We expect infrastructure to be much easier to manipulate in our compiler than in LLVM. In essence, we are tearing out and rewriting the back-most parts (register allocation, code generation - everything up through liveness and function inlining will remain intact) with new pipeline stages. A vague checklist of what needs to be done:

1. find and iterate over strongly connected components of a call graph
2. register allocator support for inserting conflict-resolving register move instructions, and for allocating on "virtual" and "hardware" registers at the same time
3. main GRA pass, which will go top-down and bottom-up propagating constraints, and invoke the register allocator as necessary, and also keep track of register-used sets to determine when saving and restoring registers is needed
4. code generation backend rewritten to respect the calling conventions we decide on instead of the standard x86 one

This week we have been devising in more depth the algorithm we will use, and putting new infrastructure in place to support the algorithm on top of it. Next week will hopefully be for algorithm implementation, with the goal of "proof-of-concept" functionality (our original milestone, minus the LLVM part). The week after will be for adding features and polishing details of the implementation, and for benchmarking. (We may wish to continue benchmarking and polishing during exam week.)

For benchmarking, we plan to re-use the benchmark suite from 15-411, which has several complicated computation-heavy programs, such as a collatz conjecture solver and hunt the wumpus. If this proves to be insufficient (and probably even if it doesn't), we will spend some time generating more test cases. (Note: I expect the "coming up with a new algorithm" thing will take much energy away from benchmarking, so I personally would be proud to have a full-featured correct implementation even without thorough benchmarking.)