[LLVMdev] request for help writing a register allocator
horwitz at cs.wisc.edu
Wed Oct 21 18:28:29 CDT 2009
I've made some progress writing my register allocator, but now I'm stuck.
I have 2 questions for you:
1. I tried running the PBQP allocator (as a dynamic pass), but that didn't
work. When I type this:
llc -f -load Debug/lib/regalloc.so -regalloc=pbqp simple.bc
I get the following error:
llc: /afs/cs.wisc.edu/p/course/cs701-horwitz/public/llvm-root/llvm/include/llvm/Support/CommandLine.h:483: void llvm::cl::parser<DataType>::addLiteralOption(const char*, const DT&, const char*) [with DT = llvm::FunctionPass* (*)(), DataType = llvm::FunctionPass* (*)()]: Assertion `findOption(Name) == Values.size() && "Option already exists!"' failed.
Can you tell from this what I'm doing wrong?
2. I tried writing a very simple register allocator. It works as follows:
Step 1: Find out which physical registers are already used. Do this by
iterating over all instructions and testing each operand. Store results
(including aliases) in a set.
Step 2: For each target reg class, save one (unused) physical register to
be used for spills. (Some classes have no unused physical registers.
This would be detected in Step 3 if there were a virtual register in that
class, but it hasn't happened for my tests so far.)
Step 3: Iterate over all instructions again allocating virtual registers
to available physical ones (in the appropriate class) or, if no such
physical reg is available, allocate the virtual register both to the
saved "spill" register for its class and to a stack slot. Keep track of
the set of virtual registers already processed so none is processed twice.
When a physical register is allocated, add it (and any aliases) to the set
of used physical registers.
Step 4: Run the spiller.
This allocator works on very simple C code, but fails (with an
uninformative segmentation fault) as soon as I include a call to scanf, or
a loop, or an if-else.
Do you see any obvious errors in the approach outlined above?
If not, can you suggest a way to find out what is going wrong?
Thanks for any help you can give me!!
More information about the LLVMdev