Hi,

I'm trying to sketch an LLVM-based implementation of the Extended

Linear Scan algorithm, described in this Vivek Sarkar's paper:

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