Hi Susan,<div><br></div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">You may find the PBQP allocator implementation useful as a reference<br>

to what's involved in adding a new allocator to LLVM. It's located in<br>
lib/CodeGen/RegAllocPBQP.cpp, with supporting files in the lib/CodeGen/<br>
PBQP directory.<br></blockquote><div><br></div><div>Yes - as far as working allocators go PBQP is pretty simple. If you're just interested in LLVM API details you can focus on the lower half of the RegAllocPBQP.cpp source file (everything from PBQPRegAlloc::findVRegIntervalsToAlloc()). The rest of the source (class declaration at the top of RegAllocPBQP.cpp aside) is mostly concerned with PBQP algorithm specifics, such as constructing cost matrices, or carrying out the PBQP graph reduction algorithm.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">
> Is there anyone who has written an LLVM register allocator who would<br>
> be<br>
> willing to help me understand the basic ideas?  I understand the<br>
> algorithm, it's LLVM that I don't understand.  For example:<br>
><br>
> - When allocating registers, how do I know which register class to<br>
> use,<br>
>   and which registers of that class are available?<br></div></div></blockquote><div><br></div><div>For each virtual register the MachineRegisterInfo::getRegClass(<vreg>) method will give you a TargetRegisterClass. You can use the allocation_order_begin/allocation_order_end methods to iterate over the allocable physregs in that class.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">
> - How do I know which operands of a Machine Instruction are candidates<br>
>   for (simple) register allocation (e.g., are of type int)?<br></div></div></blockquote><div><br></div><div>Each operand of a MachineInstr has a corresponding MachineOperand object. You can query this object using the "isReg()" method to check if an operand is a register. You'd then have to use "TargetRegisterInfo::isVirtualRegister(<reg>)" to test whether the operand is virtual, and from there perform your allocation.</div>
<div><br></div><div>I've attached a demo allocator that'll get you started with the above APIs.</div><div><br></div><div>LLVM's CodeGen library is target independent though, and the register allocator is expected to be able to allocate for _all_ virtregs, regardless of their class (and to handle things like register aliasing). There's no built-in distinction of "simple" candidates, as opposed to trickier ones.</div>
<div><br></div><div>If it helps you could hard code a test for your chosen platform (presumably something nice and clean) at the start of the allocator, and from there on work on the assumption that you're dealing with that platform. Then it'd be up to you to decide which classes the students would have to allocate for. You'd still need a way to allocate any "hard" classes though if you want a working program.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">
> - How do I replace a virtual register with a physical one? </div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">> - Do I need to generate spill code to handle virtual registers that </div>
</div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div class="h5">>   cannot be replaced with physical ones, and if so, how?</div></div></blockquote>
<div><br></div><div>You could re-write it in place (using MachineRegisterOperand::setReg(<reg>) if you want to manipulate the code yourself, or you can store the mapping in a VirtRegMap object and have the LLVM VirtRegRewriter apply the changes for you. The latter would have to be used in conjunction with the other LLVM regalloc components. You'd get liveness (LiveIntervals) and spilling (LiveIntervals/VirtRegRewriter) for free, at the cost of some extra work to understand their somewhat curious APIs. Looking at RegAllocPBQP.cpp is probably the best way to get your head around how those components are used by register allocation.</div>
<div> </div><div><br></div><div>Regards,</div><div>Lang Hames.</div></div></div>