efficacy of register allocation algorithms!

Question

i'm trying to do a research/project on register allocation using graph coloring where i am to test the efficiency of different optimizing register allocation algorithms in different scenarios.

how do i start? what are the prerequisites and the grounds with which i can test them. what all algos can i use?

-------------addition--------------

i actually want a quick way out of this, i haven't done much deeper study but want to submit(shamelessly) a readily available analysis into my project with a little stress on 'efficacy' i.e what type of optimization techniques are best for different tasks/compilers/interpreters. so my major task is (how) to implement register allocation in my programs. i use 64bit linux system on a core2duo machine, i know c,cpp and java.

thank you!

Answer 1

Baseline - Presumably you'd need a set of test cases - from simple to complex - that test heavy register usage, particularly spilling. I believe there are some common/standard ones for this. You'd want to profile them, on a basic compiler, and a high-perf modern one, and analyse the assembly output to work out what's going on. That would give you a baseline.

Development - Pick a compiler (or write one). An older one is LCC - it's old, small, simple, but has a book that explains it in full. A newer alternative might be LLVM, or perhaps GCC. Some compilers are already used for this sort of research - you might even be able to switch between a range of allocators using command line switches.

Or, clarify the question - Are we talking C-style languages? Dynamic ones? JITted? What are you trying to find out? What's the CPU being targeted?

Answer 2

LCC is non-optimizing right? Thats okay I assume you are going to want many different compilers because no two versions of the same compiler and no two compilers are going to implement the same optimization the same way.

I think you will need to focus on a disassembler first then analyze the code flow and then get to register usage. Actually before that pick an ISA (instruction set) here again the same code same compiler is going to produce different results for the same optimization depending on the specific target, even specific targets within the same family.

The topic of register allocation results due to optimization algorithms is quite wide and very dynamic. It is on a par with benchmarking. Despite that it still sounds like an interesting topic, I think you will find that with or without optimization, with or without dozens of general purpose registers, most compilers end up using only a handful of registers. (A few to pass arguments and a handful per function to implement the function)