[LLVMdev] Some questions about live intervals

[Evan Cheng]

On Jan 31, 2008, at 5:05 AM, Roman Levenstein wrote:

> Hi,
>
> I'm trying to sketch an LLVM-based implementation of the Extended
> Linear Scan algorithm, described in this Vivek Sarkar's paper:
> http://www.cs.rice.edu/~vs3/PDF/cc2007.pdf
> Sarkar reports that this version of Linear Scan produces better code
> than graph-coloring regallocs and is also much faster (15x to 68x).
>
> I already started work on the implementation of this algorithm and  
> have
> a few hopefully rather simple questions:
>
> 1) What is the easiest way to understand which MBB a given instruction
> index belongs to? All the required information is available in the
> MBB2IdxMap of the LiveIntervalAnalysis class. Would it be useful to  
> add
> a small function getMBBFromIndex() to this class?

Sure there is a reverse map (actually just a vector) Idx2MBBMap. Just  
add a query.

>
>
> 2) Is there any simple way to iterate over all instructions, where a
> given live interval is live? This functionality is required by many
> register allocation algorithms. I think having some special iterator
> functions for that in the LiveIntervalAnalysis class could be very
> useful for this purpose. And implementation should be fairly
> straightforward by using the information about the beginning and end
> points of live ranges.

Well yes, See addIntervalForSpills. Iterating through the liveranges,  
then for each liverange iterate through every instruction index. It's  
not very inefficient though.

>
>
> 3) This question is related to the previous one. For computation of
> spill costs by some register allocation algorithms, it is required to
> iterate over all uses/defs of a given live interval between two points
> of execution A and B. Does LLVM already maintain such a def/use list  
> at
> the MachineInstr level? Or should I really inspect each instruction?

MachineRegisterInfo now contains the use / def information. The  
register allocator passes have not been changed to make use of them yet.

>
>
> 4) What would be the easiest and the most efficient way to get the set
> of  live intervals that are live at a given point of execution P, i.e.
> at instruction with number P? Of course, one could do one linear scan
> of all intervals and remember for each point P the set of live
> intervals. But this solution may require a lot of memory in case of
> very big functions. May be there are some better/faster possibilities
> available?

There isn't an efficient way right now. I think you can keep some sort  
of interference graph to help with this? Perhaps you can use class  
RegallocQuery in RegisterCoalescer.h for this? David would know since  
he contributed this.

>
>
> As for (1) and (2), I could implement and provide patches for it, if
> you think this is desirable.

Yes, thanks.

Evan

>
>
> Thanks,
> Roman
>
>
>
>      Lesen Sie Ihre E-Mails jetzt einfach von unterwegs.
> www.yahoo.de/go
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev