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

Mingxing,

Your project sounds interesting and if it significantly improves over the live variable analysis that is in LLVM right now, I think it could be a useful contribution. I'm copying the 'llvmdev@cs.uiuc.edu' mailing list, which you should join. Send all related messages to this list to get feedback on your goals and also to get help with any problems you face. Good luck.

--Vikram
Associate Professor, Computer Science
University of Illinois at Urbana-Champaign
http://llvm.org/~vadve

Hello,

For what it's worth, it would be very useful to have fast liveness checking available at the MachineFunction level. We could delay calculating full LiveIntervals until after PHI elimination that way, and it would make Strong PHI Elimination very, very happy.

--Owen

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); 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.
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.
Thanks again, I will try to implement it in LLVM, and further more, try my
best to improve it.

Best wishes,
Star.

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

This is an excellent project. We look forward to seeing your work!

Is it possible for you to implement your work on the mainline and contribute back patches along the way? That way, the community can offer suggestions and we will try *harder* not to break your pass.

Evan

Hi, Evan.
I'm new in LLVM project developing.
How should I work on the mainline? I have check out the latest copy of LLVM
from Subvresion using the Read-Only account.
Do you mean I should provide the patch to the mainline periodic in this
LLVMDEV mailing list?

Anyway, thanks for your advice :slight_smile:

Star

Hi, Evan.
I'm new in LLVM project developing.
How should I work on the mainline? I have check out the latest copy of LLVM
from Subvresion using the Read-Only account.
Do you mean I should provide the patch to the mainline periodic in this
LLVMDEV mailing list?

To start, yes! After a few patches, you'll have commit privilege. You can then commit patches directly. We'll do review after commit.

Anyway, thanks for your advice :slight_smile:

No problem.

Evan