Vikram S. Adve
2008-Oct-29 03:46 UTC
[LLVMdev] 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 at 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 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: tanmingxing at mprc.pku.edu.cn > * tanmx.star at gmail.com > ************************************************** >
Benoit Boissinot
2008-Oct-29 14:05 UTC
[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_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
Owen Anderson
2008-Oct-29 17:19 UTC
[LLVMdev] A new project proposal for LLVM and calling help from a chinese student
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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 2624 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081029/cdbd8ea9/attachment.bin>
Star
2008-Oct-30 05:39 UTC
[LLVMdev] A new project proposal for LLVM and calling help from a chinese student
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:bboissin at gmail.com] 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
Reasonably Related Threads
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student
- [LLVMdev] A new project proposal for LLVM and calling help from a chinese student
- [LLVMdev] Find all backedges of CFG by MachineDominatorTree. please look at my jpg.