[LLVMdev] Static Profiling Algorithms in LLVM

[Jeff Kunkel]

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>