[LLVMdev] request for help writing a register allocator

[Susan Horwitz]

Lang -

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!!

Susan Horwitz