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
Hi Roman,> 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? >The MachineInstr class has a pointer to its MachineBasicBlock (at least in top-of-tree). Call "getParent()" on the MachineInstr. -bw
Hi Bill, --- Bill Wendling <isanbard at gmail.com> schrieb:> > 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? > >> The MachineInstr class has a pointer to its MachineBasicBlock (at > least in top-of-tree). Call "getParent()" on the MachineInstr.This is true. But sometimes, when you work with LiveIntervals, you use start/end indexes coming from live ranges of an interval. And when you call getInstructionFromIndex(start/end index), you sometimes get the NULL pointer back, since instruction with this index was removed in the meantime due to coalescing or something else. Then you still face a problem of determining which BB this instruction index belongs to, but you cannot use the trick proposed by you above. Does it explain more clearly my problem and a reason for a proposed solution? -Roman Lesen Sie Ihre E-Mails jetzt einfach von unterwegs. www.yahoo.de/go
On Thursday 31 January 2008 07:05, Roman Levenstein wrote:> I already started work on the implementation of this algorithm and have > a few hopefully rather simple questions:Roman, I'm excited to hear that you are working on this algorithm. Do you plan to contribute it to the public llvm repository? -Dave
Hi David, --- David Greene <dag at cray.com> schrieb:> On Thursday 31 January 2008 07:05, Roman Levenstein wrote: > > > I already started work on the implementation of this algorithm and > have > > a few hopefully rather simple questions: > > Roman, > > I'm excited to hear that you are working on this algorithm. Do you > plan to contribute it to the public llvm repository?Yes. I plan to contribute it to the public LLVM repository. The skeleton implementation of this algorithm is alsmost done, though I still have some small problems mentioned in my original email. But to make the algorithm really usable, it should be extended to support register classes, since Sarkar's algorithm cannot handle it. I'm going to try out an approach based on Smith's paper about graph coloring register allocation. Hopefully this would solve this issue. - Roman Lesen Sie Ihre E-Mails jetzt einfach von unterwegs. www.yahoo.de/go
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
On Friday 01 February 2008 13:54, Evan Cheng wrote:> 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.RegallocQuery is just an abstract interface class. The intent is for it to be the gateway through which queries to the register allocator are sent. One such query is whether two intervals interfere. The "guts" of the computation is up to some other piece of code, however. A naive implementation might return intA.overlaps(intB), for the interference query, for example. I hadn't thought about a query to return the set of intervals live at a particular point, but that's a good idea. I actually have a number of changes to this interface queued up waiting for upstream submittal. Some of the changes could be contraversial, though, so it might take a bit of iteration to make it happen. It's also tied in with some major coalescing refactoring that I did to allow more code shaing. I also want to get that submitted upstream but it's a huge patch and will take a while to get processed. The bottom line is that RegallocQuery doesn't do any computation on its own. It's only purpose is to allow the register allocator to be decoupled from the rest of the compiler internals. -Dave
Hi Evan, Here is a patch for the LiveIntervalAnalysis that we discussed. --- Evan Cheng <evan.cheng at apple.com> schrieb:> > 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. > Justadd a query.Done. Please find a patch attached to this mail.> > As for (1) and (2), I could implement and provide patches for it, > > if you think this is desirable. > > Yes, thanks.Here you are! -Roman Lesen Sie Ihre E-Mails auf dem Handy. www.yahoo.de/go -------------- next part -------------- A non-text attachment was scrubbed... Name: LiveIntervalAnalysis.patch Type: text/x-diff Size: 2377 bytes Desc: 2881029184-LiveIntervalAnalysis.patch URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080208/5cfee60e/attachment.patch>