[LLVMdev] Requiring LiveIntervals

[Chris Lattner]

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 
code.

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

Ok.

> 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 
instructions.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/