This repository acts as the "Work Product Submission" for my Google Summer of Code 2018 project. My project was implementing a register allocator for libjit. Register allocation is the process of determining which variables of a function reside in registers and which in memory. While working on my GSoC project I also wrote a paper which explains the theory behind writing a graph coloring based register allocator.
All my commits done during GSoC as well as the code changed can be viewed here
- Implement computation of the liveness sets
UEVar,VarKillandLiveOut. - Make function prologs and epilogs on x86-64 only store the base pointer when required and only move the stack pointer when required.
- Implement computing live ranges for each value using the computed liveness sets.
- Extend the the rules parser to include a section with register usage information for each instruction.
- Add internal live ranges when instructions use or clobber registers
- Implement a graph coloring based register allocator as described by Chaitin/Briggs:
- Build the interference graph
- Remove nodes from the graph and pushing them on a stack
- Pop live ranges from the stack and color them.
- If a live range was left uncoloured in the previous step spill it and restart the process.
- Add a flag to instructions which support a value to be in memory, so there is no need for creating a spill range for that value
- Add a diagnostic function which dumps all live ranges of a function
- Correctly move values into destination registers before instructions
- The orginal Chaitin Briggs allocator has an additional step which coalesces live ranges. This is currently missing in libjit.
- In libjit there are special "manual" instructions which manually perform register operations. Currently only ARM has manual instructions. The new register allocator is untested with them.
This repository contains various programs and scripts for comparing the the new and old register allocators. Their execution speed is then measured and visualized.
The Mandelbrot fractal viewer is a good speed comparasion example, as it is a common program. The new allocator is approximately 35% faster.
This program sums all numbers from 0 to n. The generated code looks nearly the same with both register allocators, so there is no real difference in execution speed.
This is a program constructed to perform better with a good register allocator. The code does not do anything useful, but contains many values and basic blocks.
