Project 6 (Register Allocation)
Goal Implement register allocation based on graph coloring.
Download the Project Tests
Download and unzip the tests for this project under $j/j--.
Run the following command inside the $j/j-- directory to compile the j-- compiler with your changes:
& ~/workspace/j--
$ ant
To compile a j-- program P.java for the MIPS target, using register allocation based on “graph coloring”, run the following
command:
& ~/workspace/j--
$ bash ./bin/j-- -s graph P.java
Use the -r
Run the following command to run the MIPS program P.s:
& ~/workspace/j--
$ spim -f P.s
Problem 1. (Register Allocation) Modify the file $j/j--/src/jminusminus/NGraphRegisterAllocator.java to implement register alloca-
tion algorithm based on graph coloring.
Directions:
(cid:136) Build liveness intervals.
(cid:136) Use the liveness intervals to build an interference graph G.
(cid:136) Apply “degree (cid:136) If G is r-colorable, allocate physical registers to the virtual registers — there’s no need to generate spill instructions. (cid:136) If G is not r-colorable, allocate physical registers to the virtual registers, generating spill instructions as needed. & ~/workspace/j-- $ $j/j--/bin/j-- -s graph -r 3 project6/Factorial.java $ spim -f Factorial.s SPIM Version 8.0 of January 8, 2010 Copyright 1990-2010, James R. Larus. All Rights Reserved. See the file README for a full copyright notice. Loaded: /usr/lib/spim/exceptions.s 5040 5040 Before you submit your files, make sure: (cid:136) Your code is adequately commented and follows good programming principles. (cid:136) You edit the sections (#1 mandatory, #2 if applicable, and #3 optional) in the given notes.txt file as appropriate. Section #1 must provide a clear high-level description of the project in no more than 200 words. Files to submit: 1. NGraphRegisterAllocator.java 2. notes.txt 1 / 1
