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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Vikram S. Adve-2
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 '[hidden email]'  
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



On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:

> Hello, Professor Adve:
> I’m a Ph.D student in Peking University of China. In this term,I  
> have a class “Advance Compiler Techniques”, which is about  
> Program Analysis and Compiler Construction. I’m very interested in  
> LLVM for its SSA-based IR and Lifelong Program Analysis. I have read  
> most of the LLVM documents onhttp://www.llvm.org/docs, some papers  
> on http://www.llvm.org/pubs/ and some source code in LLVM2.3. The  
> live variables analysis in LLVM seems not very efficient, and the  
> algorithm presented in Benoit Boissinot, Fast liveness checking for  
> ssa-form programs (the best paper of ACM SIGPLAN CGO’08) is much  
> better, especially for JIT compilation.  So, I want to implement  
> this algorithm in LLVM, which is also planed to be my final project  
> in “Advance Compiler Techniques” class.
> To my knowledge, there has been complete dominator tree  
> implementation in LLVM2.3, so what I need to do is only calculating  
> the back-edge target set(Tsure of this project; can you give me some  
> advices?
>
> 1.     Does it valuable to implement this new liveness checking  
> algorithm for LLVM?
> 2.     If this algorithm is useful for LLVM, is it possible to  
> integrate it to the next standard version LLVM? I really hope to  
> contribute my code to LLVM if possible. Surely I will try my best to  
> get it correct and give the evaluation.
> 3.     If I have problems in this project, how could I get help from  
> you?
>
> Thanks very much. Expect for your reply :)
>
> PS: The following are links about this paper:
> http://portal.acm.org/citation.cfm?id=1356064
> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/EmSoC07_Boissinot.pdf
>
> Yours   Mingxing Tan.
> 2008-10-28
>
> **************************************************
> * Microprocessor R&D Center, Peking University
> *   Beijing, P.R.China, 100871
> *     Tel:   8610-62765828 ext. 833
> *     Fax:   8610-62756231
> *     Email: [hidden email]
> *            [hidden email]
> **************************************************
>


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Benoit Boissinot-2
Hello,

> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
>>
>> PS: The following are links about this paper:
>> http://portal.acm.org/citation.cfm?id=1356064
>> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/EmSoC07_Boissinot.pdf
>>

I've put the slides from CGO online:
http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness-cgo-slides.pdf
They should be much better than the one from my presentation at EmSoC.

regards,

Benoit


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Owen Anderson-2
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

On Oct 29, 2008, at 7:05 AM, Benoit Boissinot wrote:

> Hello,
>
>> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
>>>
>>> PS: The following are links about this paper:
>>> http://portal.acm.org/citation.cfm?id=1356064
>>> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/EmSoC07_Boissinot.pdf
>>>
>
> I've put the slides from CGO online:
> http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness-cgo-slides.pdf
> They should be much better than the one from my presentation at EmSoC.
>
> regards,
>
> Benoit
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

smime.p7s (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

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

Star-7
In reply to this post by Benoit Boissinot-2
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.

-----Original Message-----
From: Benoit Boissinot [mailto:[hidden email]]
Sent: Wednesday, October 29, 2008 10:06 PM
To: LLVM Developers Mailing List
Cc: 谭明星
Subject: Re: [LLVMdev] A new project proposal for LLVM and calling help from
a chinese student

Hello,

> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
>>
>> PS: The following are links about this paper:
>> http://portal.acm.org/citation.cfm?id=1356064
>>
http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/EmSoC07_Bo
issinot.pdf
>>

I've put the slides from CGO online:
http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness-cgo-slide
s.pdf
They should be much better than the one from my presentation at EmSoC.

regards,

Benoit



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Benoit Boissinot-4
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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Evan Cheng-2
In reply to this post by Star-7
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

On Oct 29, 2008, at 10:39 PM, 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); 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.
>
> -----Original Message-----
> From: Benoit Boissinot [mailto:[hidden email]]
> Sent: Wednesday, October 29, 2008 10:06 PM
> To: LLVM Developers Mailing List
> Cc: 谭明星
> Subject: Re: [LLVMdev] A new project proposal for LLVM and calling  
> help from
> a chinese student
>
> Hello,
>
>> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
>>>
>>> PS: The following are links about this paper:
>>> http://portal.acm.org/citation.cfm?id=1356064
>>>
> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/EmSoC07_Bo
> issinot.pdf
>>>
>
> I've put the slides from CGO online:
> http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness-cgo-slide
> s.pdf
> They should be much better than the one from my presentation at EmSoC.
>
> regards,
>
> Benoit
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Star-7
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 :)

Star

> -----Original Message-----
> From: Evan Cheng [mailto:[hidden email]]
> Sent: Thursday, October 30, 2008 11:54 PM
> To: LLVM Developers Mailing List
> Subject: Re: [LLVMdev] A new project proposal for LLVM and calling
> helpfrom a chinese student
>
> 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
>
> On Oct 29, 2008, at 10:39 PM, 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); 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.
> >
> > -----Original Message-----
> > From: Benoit Boissinot [mailto:[hidden email]]
> > Sent: Wednesday, October 29, 2008 10:06 PM
> > To: LLVM Developers Mailing List
> > Cc: 谭明星
> > Subject: Re: [LLVMdev] A new project proposal for LLVM and calling
> > help from
> > a chinese student
> >
> > Hello,
> >
> >> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
> >>>
> >>> PS: The following are links about this paper:
> >>> http://portal.acm.org/citation.cfm?id=1356064
> >>>
> >
> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/
> EmSoC07_Bo
> > issinot.pdf
> >>>
> >
> > I've put the slides from CGO online:
> >
> http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness
> -cgo-slide
> > s.pdf
> > They should be much better than the one from my presentation at EmSoC.
> >
> > regards,
> >
> > Benoit
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > [hidden email]         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

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

Evan Cheng-2

On Oct 30, 2008, at 6:23 PM, Star wrote:

> 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 :)

No problem.

Evan

>
>
> Star
>
>> -----Original Message-----
>> From: Evan Cheng [mailto:[hidden email]]
>> Sent: Thursday, October 30, 2008 11:54 PM
>> To: LLVM Developers Mailing List
>> Subject: Re: [LLVMdev] A new project proposal for LLVM and calling
>> helpfrom a chinese student
>>
>> 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
>>
>> On Oct 29, 2008, at 10:39 PM, 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); 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.
>>>
>>> -----Original Message-----
>>> From: Benoit Boissinot [mailto:[hidden email]]
>>> Sent: Wednesday, October 29, 2008 10:06 PM
>>> To: LLVM Developers Mailing List
>>> Cc: 谭明星
>>> Subject: Re: [LLVMdev] A new project proposal for LLVM and calling
>>> help from
>>> a chinese student
>>>
>>> Hello,
>>>
>>>> On Oct 28, 2008, at 10:10 AM, 谭明星 wrote:
>>>>>
>>>>> PS: The following are links about this paper:
>>>>> http://portal.acm.org/citation.cfm?id=1356064
>>>>>
>>>
>> http://www.if.insa-lyon.fr/chercheurs/jpbabau/emsoc/presentations/
>> EmSoC07_Bo
>>> issinot.pdf
>>>>>
>>>
>>> I've put the slides from CGO online:
>>>
>> http://perso.ens-lyon.fr/benoit.boissinot/upload/bboissin-liveness
>> -cgo-slide
>>> s.pdf
>>> They should be much better than the one from my presentation at  
>>> EmSoC.
>>>
>>> regards,
>>>
>>> Benoit
>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> [hidden email]         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev