COMP 412: Topics in Compiler Construction Keith Cooper Department of Computer Science Rice University Houston, Texas, USA Fall 2009: Room 1046, Duncan Hall, Monday, Wednesday, Friday, 11:00am

Notes:

1. Notes on the lab report, and the 2-up version
2. Look at the Lectures page for more information.
3. You should post questions to the class newsgroup and check the newsgroup for clarifications, corrections, and insightful comments.
4. Last year's grading sheet can be found here. You can expect this year's grading to be based on similar if not identical factors.

Lab 1: Local Register Allocation

Your program should take three command line arguments. They are, in order

1. The number, k, of registers that the allocator will assume for the target machine.
   
   
2. A flag that indicates which allocation algorithm will be used in the run.
   Your program should recognize t for the top-down allocator and b for the bottom-up allocator.
   
   
3. The name of the input file.

The output file should be written to stdout. The executable should be named 412alloc. For example, if you are allocating the file block.i using 5 registers in a top-down manner the command would be: 412alloc 5 t block.i

[These issues are specified in excruciating detail to simplify the task of grading the labs. The laboratory assistants must not only read your reports (see below), but also run enough test blocks to verify the correct functioning of your lab. A standardized interface allows them to automate much of this process.]

The input blocks and output blocks are written in a subset of the ILOC representation. Limited information about ILOC appears in Appendix A of the book. The specific subset of ILOC instructions you need to support is the following:

	load	:	retrieve a value from memory into a register
	loadI	:	retrieve a value from the instruction stream into a register
	store	:	store a value from a register into memory
	add	:	add the value from two registers & place the result in a third register
	sub	:	subtract the value in the second register from the value in the first register & place the result in a third register
	mult	:	multiply the value from two registers & place the result in a third register
	lshift	:	shift the value in a register to the left by an amount specified in a second register
	rshift	:	shift the value in a register to the right by an amount specified in a second register
	output	:	write a value to the standard output stream

You may assume that memory locations 0 through 1023 are reserved for the register allocator. (The ILOC machine has separate program and data memory. The examples will all assume that no programmer-stored values should go into "low" memory.) Thus, the allocator can spill values into those locations.

Due Date

The lab report is due the following Friday, at 11:59 pm on September 18 2009. The lag between the due dates should allow you to sleep, if necessary, before writing the lab report.

If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor before September 10, 2008.

Specific Details

1. Implement a top-down local register allocator, based on the algorithm in Section 13.3.1 and Exercise 2.a of Section 13.3 (page 774 in the text).
   Answer parts b & c of Exercise 2.a (Section 13.3) in your lab report. Propose a technique for solving b, but don't implement it.
   
   
2. Implement a bottom-up local register allocator, based on the algorithm in Section 13.3.2
   
   
3. Test your allocators thoroughly. Test blocks are available to help in this process.

   Invent at least 4 of your own test blocks and leave them in your Lab 1 directory (explained below).

   Use the simulator (in ~comp412/Lab1 on OwlNet) to ensure that your allocated code is correct and to determine its execution time.
   
   

4. Run your allocator on each of the Report blocks. Check their correctness and performance using the ILOC simulator.
   
   
5. Write up a brief (five to ten pages) report on the lab. It should include:
   
   
   1. descriptions of the algorithms that you implemented, highlighting differences between your implementations and the discussion in the text;
   2. an explanation of how to invoke the allocator, including both necessary and optional command line arguments;
   3. a table showing the results of running your allocator on each report block for a machine with five (5) registers, one with ten (10) registers, and one with twenty (20) registers; and
   4. a concise discussion of the experimental results and what conclusions you draw about the performance of the two local allocators.
   
   The report should be in either PostScript or PDF form with the name report.*, where * is either ps or pdf respectively. When converting to PostScript or PDF please make sure that the document displays properly from an OwlNet computer.
   
   
6. Leave all the code and the documentation in a directory named 412/Lab1 on your OwlNet account.
   Be sure to set the permissions so that the professor and laboratory assistants can read the directory and execute your code.
   Thanks to the new campus-wide storage system, it may actually be difficult to accomplish this situation. More on the subject in class.

Grading Criteria

• 50% of the points will be based on the quality and content of your lab report. This includes both how you perform the experiments and how you explain your results. (That's why you should go home and sleep before writing up the lab report.)
  
  
• 25% of your grade will be based on the correctness of the code that your allocator generates for the various input blocks.

  The labbies will test your lab for correctness on blocks that are not included in the "report" block set. Thus, you should invent your own "torture" tests and verify that the allocator works correctly on them.
  

• 25% of your grade will be based on the number of operations (loads, stores, adds, and loadIs) that your allocator inserts into the code. Fewer inserted operations are better. These points will be awarded using a formula that gives full credit to the best solution generated this semester, and a decreasing percentage of the points for solutions that use more operations.

Your lab should perform register allocation, not general optimization.

There is no bonus for linguistic virtuosity. Writing the lab in an odd dialect of an irrelevant language gets no more points than writing it in a mainline language such as Scheme, C, C++, Java, or ML. However, don't forget that scripting languages, specifically PERL and Python, are not allowed.