[LLVMdev] A new project proposal for LLVM and calling help from a chinese student

['Benoit Boissinot']

On Thu, Oct 30, 2008 at 01:39:46PM +0800, Star wrote:
> Hi, Benoit,
> Thanks very much for your advice.
> You see the algorithm greatly improve the performance of liveness analysis.
> However, it seems still not efficient.
> First, it is inefficient in space. You have to pre-compute all Tq for every
> Tq and save them, even though only the highest nodes of Tq are needed for a
> given query(q,v);

Sure there are probably some improvements to be done. But remember that
you don't know what the highest point is because you want the highest
point from the set "Tq intersected with the nodes dominated by the definition".
So the highest point depends on the variable you're interested in, while
Tq only depends on the CFG (that's the point of the algorithm).

Maybe you can compute the Tq more lazily. Or use sparse bitsets.

> Second, it is inefficient in time. Given any query(q,v),
> you have to  traverse all Tq to find the highest nodes. When the Tq is
> large, it maybe will cost a lot. To conquer this problem, you first order
> nodes according to dominance, and then the "highest node" will be the first
> node. However, when many nodes are not dominated by each other, you have to
> traverse them.

If you have no highest point, then the CFG is not reducible, this is
not the common case.

> In fact, I think the highest node proposed in your new slice is very similar
> to the entry of SCC if the node is a loop entry. So, maybe I could use this
> information to improve this algorithm, even though I don't know clearly how
> to improve it now.

Yes, we later discovered we can generalize the algorithm to use the loop
forest information. I don't think it makes the algorithm faster, because
you'll still have some problem with irreducible CFG.

> Thanks again, I will try to implement it in LLVM, and further more, try my
> best to improve it.

Have fun!

regards,

Benoit
-- 
:wq