Skip to main content Link Search Menu Expand Document (external link)
ITP 439

Theme: auto

PA6: Register Allocation

Introduction

LLVM implements register allocation as a MachineFunctionPass – this is like a regular function pass, but runs after both instruction selection and scheduling has completed.

LLVM also provides a RegAllocBase class that custom register allocation passes can inherit from. Subclasses can determine the order virtual register intervals are assigned to physical registers and specify how virtual registers should be split or spilled if no physical register is free.

This assignment focuses on customizing the order register intervals are given physical register assignments. The current implementation in parse/RegAlloc.cpp is copied from LLVM’s RegAllocBasic allocator, which generates valid allocations with no splitting. However, this basic allocator simply allocates registers in descending order based on their spill cost, i.e. virtual registers with the highest spill cost are allocated first.

In this assignment, you will implement part of a Chaitin-Briggs graph coloring allocator. Specifically, you will write the code that generates the interference graph from intervals and then simplifies the graph. Recall that during the simplification step, any virtual registers that are trivially colorable (with \(<k\) neighbors) are removed from the graph and pushed onto a stack. If no trivially colorable registers remain, then the virtual register with the lowest spill cost is removed from the graph and pushed onto the stack.

Once all the virtual registers are removed from the graph, you will tell LLVM to attempt to assign registers in the reverse order the registers were removed. The code for attempting physical register assignments is given, as it comes directly from the RegAllocBasic implementation.

To help understand what’s happening in the register allocation, there’s quite a bit of debug output. To ask USCC to generate assembly code (and run your register allocator), you need to pass in the -s flag. For example, these arguments in Visual Studio Code will allocate registers and generate assembly for quicksort.usc:

"args": ["-s", "quicksort.usc"]

Initially, you will see output but this is just the basic register allocation order.

However, this only tests that you are generating some assembly and there is some debug output. To confirm the assembly isn’t garbage and the code works, you need to run the testAsm.py test suite:

python3 testAsm.py

This test case will generate assembly for your machine using the register allocator and then compile this assembly into a native binary executable. Then, it will run the native binary and confirm that its output matches the expected program output.

Implementation

In this assignment, you only need to make changes to RegAlloc.cpp. When the allocatePhysRegs function is called from runOnMachineFunction, LLVM will call the overridden enqueueImpl function once for every live interval. Once all the intervals are enqueued, they will then be dequeued one by one and selectOrSplit is invoked on each interval.

In order to change the order the registers are allocated, you will need to create the interference graph and simplify it prior to the call to allocatePhysRegs. Then, since the queue is a priority queue, you can use this ordering information to control the order in which virtual registers are dequeued.

You must implement the initGraph function to create the interference graph and the simplifyGraph function that simplifies the graph according to Chaitin-Briggs. These functions are already called prior to the allocatePhysRegs call, so you just need to implement them.

Any function-specific data (such as member data you may add) should be cleared in releaseMemory.

As a simplification, you may assume that any two overlapping intervals interfere. Normally, it would be necessary to check whether the intervals both require the same type of physical register (for example, a floating-point register as opposed to an integral one). However, since all types in USC are integral, this simplification is fine.

To verify that these functions are working correctly, you should implement some debug output. The final version of your code should include debug output demonstrating the order virtual registers are removed from the graph (and whether it was because it was trivially colorable or spilled). Sample output is shown at the end of these instructions.

Once these two functions are implemented, the last step is to change the behavior of std::priority_queue, which can be done by implementing a custom comparator function object (functor) that uses your ordering and changing the declaration of Queue to use your comparator instead of CompSpillWeight.

Tips

  • Before you start programming, consider how you want to represent your interference graph vertices, and how you will associate a LiveInterval with a vertex in the graph

  • To loop over all the live intervals, you can use the following code pattern:

    for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
	// reg ID
	unsigned Reg = Register::index2VirtReg(i);
  	
	// if is not a DEBUG register
	if (MRI->reg_nodbg_empty(Reg))
	  continue;
  	
	// get the respective LiveInterval
	LiveInterval *VirtReg = &LIS->getInterval(Reg);
  
	// Do something with the interval
	// ...
}
  • To check if two LiveInterval variables interfere with each other, use the overlaps member function
  • For the debug output you need to add, you should just use std::cout, but make sure you flush the stream after each line of debug output (remember std::end also flushes the stream)

  • To output debug information for a LiveInterval (including the register name and range), use the dump member function

  • Your code should use the NUM_COLORS member variable, as it can be changed via command line option

Testing Your Implementation

Once you’ve implemented all the functionality as outlined, you will want to make sure that the testAsm.py test suite still works.

Additionally, you should confirm that you see appropriate debug output when you run the -s quicksort.usc test. However, here are a couple of examples of what the output for the partition function in quicksort.usc should roughly look like:

M1 Pro (arm64 Mac) Output 
********** USCC REGISTER ALLOCATION **********
********** Function: partition
NUM_COLORS=4
Trivially colorable (neighbors=3):%19 [464r,480r:0) 0@464r  weight:INF
Removal 0: %19 [464r,480r:0) 0@464r  weight:INF
Trivially colorable (neighbors=3):%10 [16r,96r:0) 0@16r  weight:4.208333e-03
Removal 1: %10 [16r,96r:0) 0@16r  weight:4.208333e-03
Spill candidate (neighbors=7, weight=0.00416667): %22 [496r,576r:0) 0@496r  weight:4.166667e-03
Removal 2: %22 [496r,576r:0) 0@496r  weight:4.166667e-03
Trivially colorable (neighbors=3):%23 [512r,528r:0) 0@512r  weight:INF
Removal 3: %23 [512r,528r:0) 0@512r  weight:INF
Spill candidate (neighbors=5, weight=0.00625): %21 [480r,560r:0) 0@480r  weight:6.250000e-03
Removal 4: %21 [480r,560r:0) 0@480r  weight:6.250000e-03
Trivially colorable (neighbors=3):%26 [544r,560r:0) 0@544r  weight:INF
Removal 5: %26 [544r,560r:0) 0@544r  weight:INF
Trivially colorable (neighbors=2):%25 [528r,576r:0) 0@528r  weight:6.696429e-03
Removal 6: %25 [528r,576r:0) 0@528r  weight:6.696429e-03
Spill candidate (neighbors=6, weight=0.00625): %12 [96r,176r:0) 0@96r  weight:6.250000e-03
Removal 7: %12 [96r,176r:0) 0@96r  weight:6.250000e-03
Spill candidate (neighbors=5, weight=0.00669643): %16 [144r,192r:0) 0@144r  weight:6.696429e-03
Removal 8: %16 [144r,192r:0) 0@144r  weight:6.696429e-03
Spill candidate (neighbors=10, weight=0.0298564): %14 [32r,512r:0)[624B,928B:0) 0@32r  weight:2.985642e-02
Removal 9: %14 [32r,512r:0)[624B,928B:0) 0@32r  weight:2.985642e-02
Trivially colorable (neighbors=3):%17 [160r,176r:0) 0@160r  weight:INF
Removal 10: %17 [160r,176r:0) 0@160r  weight:INF
Spill candidate (neighbors=8, weight=0.0317919): %13 [112r,448B:0)[624B,928B:0) 0@112r  weight:3.179191e-02
Removal 11: %13 [112r,448B:0)[624B,928B:0) 0@112r  weight:3.179191e-02
Trivially colorable (neighbors=3):%27 [352r,368r:0) 0@352r  weight:INF
Removal 12: %27 [352r,368r:0) 0@352r  weight:INF
Spill candidate (neighbors=6, weight=0.0502774): %33 [48r,240B:1)[240B,592r:0)[624B,768r:0)[768r,816B:3)[816B,928B:2) 0@240B-phi 1@48r 2@816B-phi 3@768r  weight:5.027745e-02
Removal 13: %33 [48r,240B:1)[240B,592r:0)[624B,768r:0)[768r,816B:3)[816B,928B:2) 0@240B-phi 1@48r 2@816B-phi 3@768r  weight:5.027745e-02
Spill candidate (neighbors=5, weight=0.0807292): %32 [672r,752r:0) 0@672r  weight:8.072916e-02
Removal 14: %32 [672r,752r:0) 0@672r  weight:8.072916e-02
Spill candidate (neighbors=4, weight=0.0975946): %6 [64r,576r:0)[624B,928B:0) 0@64r  weight:9.759457e-02
Removal 15: %6 [64r,576r:0)[624B,928B:0) 0@64r  weight:9.759457e-02
Trivially colorable (neighbors=3):%36 [720r,736r:0) 0@720r  weight:INF
Removal 16: %36 [720r,736r:0) 0@720r  weight:INF
Trivially colorable (neighbors=2):%35 [704r,752r:0) 0@704r  weight:1.297433e-01
Removal 17: %35 [704r,752r:0) 0@704r  weight:1.297433e-01
Trivially colorable (neighbors=1):%31 [656r,736r:0) 0@656r  weight:1.210938e-01
Removal 18: %31 [656r,736r:0) 0@656r  weight:1.210938e-01
Trivially colorable (neighbors=0):%29 [224r,240B:1)[240B,448B:0)[624B,848r:0)[848r,928B:2) 0@240B-phi 1@224r 2@848r  weight:1.585624e-01
Removal 19: %29 [224r,240B:1)[240B,448B:0)[624B,848r:0)[848r,928B:2) 0@240B-phi 1@224r 2@848r  weight:1.585624e-01
Assigning to physical register: %29 [224r,240B:1)[240B,448B:0)[624B,848r:0)[848r,928B:2) 0@240B-phi 1@224r 2@848r  weight:1.585624e-01
Assigning to physical register: %31 [656r,736r:0) 0@656r  weight:1.210938e-01
Assigning to physical register: %35 [704r,752r:0) 0@704r  weight:1.297433e-01
Assigning to physical register: %36 [720r,736r:0) 0@720r  weight:INF
Assigning to physical register: %6 [64r,576r:0)[624B,928B:0) 0@64r  weight:9.759457e-02
Assigning to physical register: %32 [672r,752r:0) 0@672r  weight:8.072916e-02
Assigning to physical register: %33 [48r,240B:1)[240B,592r:0)[624B,768r:0)[768r,816B:3)[816B,928B:2) 0@240B-phi 1@48r 2@816B-phi 3@768r  weight:5.027745e-02
Assigning to physical register: %27 [352r,368r:0) 0@352r  weight:INF
Assigning to physical register: %13 [112r,448B:0)[624B,928B:0) 0@112r  weight:3.179191e-02
Assigning to physical register: %17 [160r,176r:0) 0@160r  weight:INF
Assigning to physical register: %14 [32r,512r:0)[624B,928B:0) 0@32r  weight:2.985642e-02
Assigning to physical register: %16 [144r,192r:0) 0@144r  weight:6.696429e-03
Assigning to physical register: %12 [96r,176r:0) 0@96r  weight:6.250000e-03
Assigning to physical register: %25 [528r,576r:0) 0@528r  weight:6.696429e-03
Assigning to physical register: %26 [544r,560r:0) 0@544r  weight:INF
Assigning to physical register: %21 [480r,560r:0) 0@480r  weight:6.250000e-03
Assigning to physical register: %23 [512r,528r:0) 0@512r  weight:INF
Assigning to physical register: %22 [496r,576r:0) 0@496r  weight:4.166667e-03
Assigning to physical register: %10 [16r,96r:0) 0@16r  weight:4.208333e-03
Assigning to physical register: %19 [464r,480r:0) 0@464r  weight:INF
GitHub Actions (x86_64 Linux) Output 
********** USCC REGISTER ALLOCATION **********
********** Function: partition
NUM_COLORS=4
Trivially colorable (neighbors=3):%9 [16r,80r:0) 0@16r  weight:4.353448e-03
Removal 0: %9 [16r,80r:0) 0@16r  weight:4.353448e-03
Spill candidate (neighbors=4, weight=0.00446429): %16 [480r,528r:0) 0@480r  weight:4.464286e-03
Removal 1: %16 [480r,528r:0) 0@480r  weight:4.464286e-03
Trivially colorable (neighbors=3):%15 [464r,560r:0) 0@464r  weight:8.145161e-03
Removal 2: %15 [464r,560r:0) 0@464r  weight:8.145161e-03
Trivially colorable (neighbors=2):%18 [496r,512r:0) 0@496r  weight:INF
Removal 3: %18 [496r,512r:0) 0@496r  weight:INF
Spill candidate (neighbors=12, weight=0.00473485): %12 [128r,528r:0)[592B,848B:0) 0@128r  weight:4.734849e-03
Removal 4: %12 [128r,528r:0)[592B,848B:0) 0@128r  weight:4.734849e-03
Spill candidate (neighbors=5, weight=0.00625): %10 [80r,160r:0) 0@80r  weight:6.250000e-03
Removal 5: %10 [80r,160r:0) 0@80r  weight:6.250000e-03
Spill candidate (neighbors=10, weight=0.0320935): %8 [32r,448B:0)[592B,848B:0) 0@32r  weight:3.209346e-02
Removal 6: %8 [32r,448B:0)[592B,848B:0) 0@32r  weight:3.209346e-02
Trivially colorable (neighbors=3):%13 [144r,160r:0) 0@144r  weight:INF
Removal 7: %13 [144r,160r:0) 0@144r  weight:INF
Spill candidate (neighbors=8, weight=0.0328032): %0 [96r,448B:0)[592B,848B:0) 0@96r  weight:3.280318e-02
Removal 8: %0 [96r,448B:0)[592B,848B:0) 0@96r  weight:3.280318e-02
Spill candidate (neighbors=7, weight=0.0575898): %1 [48r,224B:1)[224B,464r:0)[592B,704r:0)[704r,736B:3)[736B,848B:2) 0@224B-phi 1@48r 2@736B-phi 3@704r  weight:5.758978e-02
Removal 9: %1 [48r,224B:1)[224B,464r:0)[592B,704r:0)[704r,736B:3)[736B,848B:2) 0@224B-phi 1@48r 2@736B-phi 3@704r  weight:5.758978e-02
Trivially colorable (neighbors=3):%20 [352r,368r:0) 0@352r  weight:INF
Removal 10: %20 [352r,368r:0) 0@352r  weight:INF
Spill candidate (neighbors=5, weight=0.0835129): %23 [608r,672r:0) 0@608r  weight:8.351293e-02
Removal 11: %23 [608r,672r:0) 0@608r  weight:8.351293e-02
Spill candidate (neighbors=4, weight=0.10596): %6 [64r,528r:0)[592B,848B:0) 0@64r  weight:1.059598e-01
Removal 12: %6 [64r,528r:0)[592B,848B:0) 0@64r  weight:1.059598e-01
Trivially colorable (neighbors=3):%28 [208r,224B:0)[224B,448B:2)[592B,784r:2)[784r,848B:1) 0@208r 1@784r 2@224B-phi  weight:1.423490e-01
Removal 13: %28 [208r,224B:0)[224B,448B:2)[592B,784r:2)[784r,848B:1) 0@208r 1@784r 2@224B-phi  weight:1.423490e-01
Trivially colorable (neighbors=2):%25 [640r,656r:0) 0@640r  weight:INF
Removal 14: %25 [640r,656r:0) 0@640r  weight:INF
Trivially colorable (neighbors=1):%24 [624r,672r:0) 0@624r  weight:1.297433e-01
Removal 15: %24 [624r,672r:0) 0@624r  weight:1.297433e-01
Trivially colorable (neighbors=0):%19 [336r,400B:0)[592B,656r:0) 0@336r  weight:1.908144e-01
Removal 16: %19 [336r,400B:0)[592B,656r:0) 0@336r  weight:1.908144e-01
Assigning to physical register: %19 [336r,400B:0)[592B,656r:0) 0@336r  weight:1.908144e-01
Assigning to physical register: %24 [624r,672r:0) 0@624r  weight:1.297433e-01
Assigning to physical register: %25 [640r,656r:0) 0@640r  weight:INF
Assigning to physical register: %28 [208r,224B:0)[224B,448B:2)[592B,784r:2)[784r,848B:1) 0@208r 1@784r 2@224B-phi  weight:1.423490e-01
Assigning to physical register: %6 [64r,528r:0)[592B,848B:0) 0@64r  weight:1.059598e-01
Assigning to physical register: %23 [608r,672r:0) 0@608r  weight:8.351293e-02
Assigning to physical register: %20 [352r,368r:0) 0@352r  weight:INF
Assigning to physical register: %1 [48r,224B:1)[224B,464r:0)[592B,704r:0)[704r,736B:3)[736B,848B:2) 0@224B-phi 1@48r 2@736B-phi 3@704r  weight:5.758978e-02
Assigning to physical register: %0 [96r,448B:0)[592B,848B:0) 0@96r  weight:3.280318e-02
Assigning to physical register: %13 [144r,160r:0) 0@144r  weight:INF
Assigning to physical register: %8 [32r,448B:0)[592B,848B:0) 0@32r  weight:3.209346e-02
Assigning to physical register: %10 [80r,160r:0) 0@80r  weight:6.250000e-03
Assigning to physical register: %12 [128r,528r:0)[592B,848B:0) 0@128r  weight:4.734849e-03
Assigning to physical register: %18 [496r,512r:0) 0@496r  weight:INF
Assigning to physical register: %15 [464r,560r:0) 0@464r  weight:8.145161e-03
Assigning to physical register: %16 [480r,528r:0) 0@480r  weight:4.464286e-03
Assigning to physical register: %9 [16r,80r:0) 0@16r  weight:4.353448e-03


Because the assembly instructions will vary depending on the host architecture, your output may not match exactly as what is shown here. But the main thing is that registers should get removed both for being trivially colorable and for being a spill candidate, and that the registers are allocated in the reverse order they were simplified from the graph.

Testing on GitHub

Once you pass all the tests locally, you should push your code to GitHub and manually run the PA6 unit tests. If they don’t pass or your code doesn’t compile, you should make the necessary fixes and try again.

For this assignment, there are 20 test cases. Each test case failure is -5 points.

We will also look at your output of quicksort.usc register allocation. The physical registers should be assigned in the reverse order in which they are removed from the graph. For example, if %vreg5 is removed last, then it should be the first which is assigned to a physical register.

  • If you do the assignment order incorrectly, the deduction is -15 points
  • If you didn’t implement the graph coloring allocator at all, you will get a 0

Submitting Your Assignment

Once you have a GitHub Actions run you are happy with, to submit the assignment you need to submit this form on Gradescope. You will have to provide the full URL for the actions run you want us to grade, and also tell us if you are using any of your four slip days.

Make sure you submit this form, as otherwise we will not know that you have a submission you want us to grade. We only grade based on your GitHub Actions run and code on GitHub, and we will not download everyone’s repo. If your code does not compile or you do not submit the form, you will get a 0 on the assignment.

Conclusion

This assignment should help give some insight into how a Chaitin-Briggs graph coloring allocator works. It’s interesting to note that the LLVM register allocation system is designed more so to provide mechanisms for interesting heuristics to decide on spilling or splitting virtual registers, as opposed to attempting to find more optimal colorings. This is predicated on the idea that in larger software programs, there will always be uncolorable interference graphs, so it is better for the compiler to focus on improving its behavior when this occurs.