[LLVMdev] Requiring LiveIntervals

Chris Lattner sabre at nondot.org
Tue Sep 20 20:15:18 PDT 2005

On Tue, 20 Sep 2005, Tzu-Chien Chiu wrote:
> On 20/09/05, Chris Lattner <sabre at nondot.org> wrote:
>>> because LiveVariables do not provide an interface to iterate through
>>> all viritual registers.
>> Ok, you could add a method to LiveVariables that returns
>> VirtRegInfo.size().  The virtual registers are defined by the range:
>> [MRegisterInfo::FirstVirtualRegister,
>>   MRegisterInfo::FirstVirtualRegister+VirtRegInfo.size()]
>> Alternatively, the same information can be obtained from the SSARegMap for
>> the function: given a MachineFunction, use something like:
>> NumVRegs = MF.getSSARegMap()->getLastVirtReg()+1;
>> These also start from MRegisterInfo::FirstVirtualRegister.
> I'm not sure if these two methods work because after the live
> intervals are joined, some virtual registers are coalesced, and their
> indices are invalidated. It's no longer that each register in:
>  [MRegisterInfo::FirstVirtualRegister,
>  MRegisterInfo::FirstVirtualRegister+VirtRegInfo.size()]
> is valid.

I thought you were writing a register allocator?  The register allocator 
itself handles coallescing.  The information here reflects the pre-ra 

>> It was intended to be used as an internal interface, but if you really
>> would like it, I would have no problem promoting it to be a public
>> interface.  Let me know what you'd like.
> A public interface. the interface of LiveIntervals is more convenient
> than LiveVariables when building build the interference graph, which
> is necessary for the family of Chaitin style register allocators.


> Actually I am surprised that some common graph like the interference
> graph and the data dependence graph (a.k.a. data precedence graph or
> scheduling graph) is not available in CodeGen, except the control flow
> graph. Though they are not difficult to construct, it's tedious that
> every target back-end has to re-build them.

> Perhaps:
> 1) All existing targets share the register allocators in CodeGen. There
> is no need for ad hoc register allocator, and therefore no
> interference graph analysis.

Yes, all of the register allocators are currently common, living as 
lib/CodeGen/RegAlloc*.  We have no target-independent graph coloring 
register allocator implementation distributed with LLVM, and nothing else 
needs a real interference graph.

> 2) No target-independent instruction scheduling code, and therefore no
> dependence graph.

The scheduling work is being done on the SelectionDAG infrastructure, 
whose dependence graphs are defined by the 
include/llvm/CodeGen/SelectionDAG*.h files.

Note that these nodes represent the code itself before being laid out in 
basic blocks.  It is not intended to represent dependences between machine 



More information about the llvm-dev mailing list