[LLVMdev] Some questions about live intervals

[Roman Levenstein]

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?

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.

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?

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?

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

Thanks,
 Roman



      Lesen Sie Ihre E-Mails jetzt einfach von unterwegs.
www.yahoo.de/go