My god! I would love a branch predictor! It would simplify many aspects of my register allocator. Second, I am surprised it did not make it into the tree. Since more is being done with register allocation as a while "RegAllocBasic" was just put in, I hope this is looked at again. Do you have a working svn copy? Also, could you send me a copy/link to that '94 paper off the list please? -Thanks -Jeff Kunkel On Tue, Nov 2, 2010 at 6:57 PM, kapil anand <kapilanand2 at gmail.com> wrote:> Thanks Andrei! > > I haven't read the paper. I would see whether this fulfills my requirements > or whether I need to make any changes. > > --Kapil > > > On Tue, Nov 2, 2010 at 12:43 PM, Andrei Alvares <logytech at gmail.com>wrote: > >> Hello Kapil, >> >> I have implemented a static profiler for LLVM as a google summer of >> code project in 2009. I wrote it for the 2.4 branch, but the >> implementation never made into the tree. I have recently ported it to >> LLVM 2.8, but I haven't tested it. You can take a look at the code >> from: http://homepages.dcc.ufmg.br/~rimsa/tools/stprof-llvm.patch<http://homepages.dcc.ufmg.br/%7Erimsa/tools/stprof-llvm.patch> >> >> The implementation is based on Wu's [1994] paper and provides a >> branch predictor that calculates probabilities. The implementation >> also covers an intraprocedural and interprocedural frequency >> calculator for edges and functions. >> >> Reference: >> Youfeng Wu and James R. Larus. Static branch frequency and program >> profile analysis. In MICRO 27: Proceedings of the 27th annual >> international symposium on Microarchitecture. IEEE, 1994. >> >> Regards, >> Andrei >> >> On Tue, Nov 2, 2010 at 10:46 AM, Andrew Lenharth <andrewl at lenharth.org> >> wrote: >> > On Tue, Nov 2, 2010 at 12:28 AM, kapil anand <kapilanand2 at gmail.com> >> wrote: >> >> Hi all, >> >> >> >> Does LLVM infrastructure contain implementation of any static profiling >> >> algorithm apart from "Spill-Weight" calculation present in Live >> Intervals >> >> class? The future work page does suggest implementation of some "static >> >> profiling" algorithms to make an educated guesses about the relative >> >> execution frequencies of various parts of the code. >> > >> > If you look at old releases, there was a profiling library and >> > transforms, including infrastructure to do any of the profiling with >> > random sampling. Those were unmaintained and removed not that long >> > ago. What you could profile was somewhat limited. >> > >> > Andrew >> > >> > >> >> Thanks >> >> >> >> --Kapil >> >> >> >> _______________________________________________ >> >> LLVM Developers mailing list >> >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >> >> >> > >> > _______________________________________________ >> > LLVM Developers mailing list >> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > >> > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101102/478ce0ab/attachment.html>
Hello Jeff, On Tue, Nov 2, 2010 at 9:17 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:> My god! I would love a branch predictor! It would simplify many aspects of > my register allocator.The branch predictor of the implementation is not as accurate as the one from the paper, but it is close enough. Unfortunately, the branch predictor is a very expensive pass, because it relies on post domination information for some heuristics which is costly to calculate.> Second, I am surprised it did not make it into the tree. Since more is being > done with register allocation as a while "RegAllocBasic" was just put in, I > hope this is looked at again. > Do you have a working svn copy?I created the patch based on the official 2.8 branch release, but as I said before I didn't get the time to fully tested it on this release.> Also, could you send me a copy/link to that '94 paper off the list please?You can get it from the following link: http://ftp.cs.wisc.edu/pub/techreports/1994/TR1248.pdf Regards, Andrei> -Thanks > -Jeff Kunkel > On Tue, Nov 2, 2010 at 6:57 PM, kapil anand <kapilanand2 at gmail.com> wrote: >> >> Thanks Andrei! >> >> I haven't read the paper. I would see whether this fulfills my >> requirements or whether I need to make any changes. >> >> --Kapil >> >> On Tue, Nov 2, 2010 at 12:43 PM, Andrei Alvares <logytech at gmail.com> >> wrote: >>> >>> Hello Kapil, >>> >>> I have implemented a static profiler for LLVM as a google summer of >>> code project in 2009. I wrote it for the 2.4 branch, but the >>> implementation never made into the tree. I have recently ported it to >>> LLVM 2.8, but I haven't tested it. You can take a look at the code >>> from: http://homepages.dcc.ufmg.br/~rimsa/tools/stprof-llvm.patch >>> >>> The implementation is based on Wu's [1994] paper and provides a >>> branch predictor that calculates probabilities. The implementation >>> also covers an intraprocedural and interprocedural frequency >>> calculator for edges and functions. >>> >>> Reference: >>> Youfeng Wu and James R. Larus. Static branch frequency and program >>> profile analysis. In MICRO 27: Proceedings of the 27th annual >>> international symposium on Microarchitecture. IEEE, 1994. >>> >>> Regards, >>> Andrei >>> >>> On Tue, Nov 2, 2010 at 10:46 AM, Andrew Lenharth <andrewl at lenharth.org> >>> wrote: >>> > On Tue, Nov 2, 2010 at 12:28 AM, kapil anand <kapilanand2 at gmail.com> >>> > wrote: >>> >> Hi all, >>> >> >>> >> Does LLVM infrastructure contain implementation of any static >>> >> profiling >>> >> algorithm apart from "Spill-Weight" calculation present in Live >>> >> Intervals >>> >> class? The future work page does suggest implementation of some >>> >> "static >>> >> profiling" algorithms to make an educated guesses about the relative >>> >> execution frequencies of various parts of the code. >>> > >>> > If you look at old releases, there was a profiling library and >>> > transforms, including infrastructure to do any of the profiling with >>> > random sampling. Those were unmaintained and removed not that long >>> > ago. What you could profile was somewhat limited. >>> > >>> > Andrew >>> > >>> > >>> >> Thanks >>> >> >>> >> --Kapil >>> >> >>> >> _______________________________________________ >>> >> LLVM Developers mailing list >>> >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> >> >>> >> >>> > >>> > _______________________________________________ >>> > LLVM Developers mailing list >>> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>> > >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> > >
You said it was expensive, but if you had to put a big-o estimate on it, what would it be? -Thanks Jeff Kunkel On Tue, Nov 2, 2010 at 8:54 PM, Andrei Alvares <logytech at gmail.com> wrote:> Hello Jeff, > > On Tue, Nov 2, 2010 at 9:17 PM, Jeff Kunkel <jdkunk3 at gmail.com> wrote: > > My god! I would love a branch predictor! It would simplify many aspects > of > > my register allocator. > > The branch predictor of the implementation is not as accurate as the > one from the paper, but it is close enough. Unfortunately, the branch > predictor is a very expensive pass, because it relies on post > domination information for some heuristics which is costly to > calculate. > > > Second, I am surprised it did not make it into the tree. Since more is > being > > done with register allocation as a while "RegAllocBasic" was just put in, > I > > hope this is looked at again. > > Do you have a working svn copy? > > I created the patch based on the official 2.8 branch release, but as I > said before I didn't get the time to fully tested it on this release. > > > Also, could you send me a copy/link to that '94 paper off the list > please? > > You can get it from the following link: > http://ftp.cs.wisc.edu/pub/techreports/1994/TR1248.pdf > > Regards, > Andrei > > > -Thanks > > -Jeff Kunkel > > On Tue, Nov 2, 2010 at 6:57 PM, kapil anand <kapilanand2 at gmail.com> > wrote: > >> > >> Thanks Andrei! > >> > >> I haven't read the paper. I would see whether this fulfills my > >> requirements or whether I need to make any changes. > >> > >> --Kapil > >> > >> On Tue, Nov 2, 2010 at 12:43 PM, Andrei Alvares <logytech at gmail.com> > >> wrote: > >>> > >>> Hello Kapil, > >>> > >>> I have implemented a static profiler for LLVM as a google summer of > >>> code project in 2009. I wrote it for the 2.4 branch, but the > >>> implementation never made into the tree. I have recently ported it to > >>> LLVM 2.8, but I haven't tested it. You can take a look at the code > >>> from: http://homepages.dcc.ufmg.br/~rimsa/tools/stprof-llvm.patch > >>> > >>> The implementation is based on Wu's [1994] paper and provides a > >>> branch predictor that calculates probabilities. The implementation > >>> also covers an intraprocedural and interprocedural frequency > >>> calculator for edges and functions. > >>> > >>> Reference: > >>> Youfeng Wu and James R. Larus. Static branch frequency and program > >>> profile analysis. In MICRO 27: Proceedings of the 27th annual > >>> international symposium on Microarchitecture. IEEE, 1994. > >>> > >>> Regards, > >>> Andrei > >>> > >>> On Tue, Nov 2, 2010 at 10:46 AM, Andrew Lenharth <andrewl at lenharth.org > > > >>> wrote: > >>> > On Tue, Nov 2, 2010 at 12:28 AM, kapil anand <kapilanand2 at gmail.com> > >>> > wrote: > >>> >> Hi all, > >>> >> > >>> >> Does LLVM infrastructure contain implementation of any static > >>> >> profiling > >>> >> algorithm apart from "Spill-Weight" calculation present in Live > >>> >> Intervals > >>> >> class? The future work page does suggest implementation of some > >>> >> "static > >>> >> profiling" algorithms to make an educated guesses about the relative > >>> >> execution frequencies of various parts of the code. > >>> > > >>> > If you look at old releases, there was a profiling library and > >>> > transforms, including infrastructure to do any of the profiling with > >>> > random sampling. Those were unmaintained and removed not that long > >>> > ago. What you could profile was somewhat limited. > >>> > > >>> > Andrew > >>> > > >>> > > >>> >> Thanks > >>> >> > >>> >> --Kapil > >>> >> > >>> >> _______________________________________________ > >>> >> LLVM Developers mailing list > >>> >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >>> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >>> >> > >>> >> > >>> > > >>> > _______________________________________________ > >>> > LLVM Developers mailing list > >>> > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >>> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >>> > > >> > >> > >> _______________________________________________ > >> LLVM Developers mailing list > >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >> > > > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101103/9d06c22b/attachment.html>