[LLVMdev] Static Profiling Algorithms in LLVM

Wed Nov 3 13:16:26 PDT 2010

The MachineLoopInfo pass uses machine dominator tree information. So another
pass using it should not cost much. I am going to patch it in and try it
out.

My allocator is running about O(2*k*m + coalescing/phi elimination) speed
and O(m+k) space where m is the number of instructions and k is the number
of registers.

- Thanks
- Jeff Kunkel

On Wed, Nov 3, 2010 at 3:21 PM, Andrei Alvares <logytech at gmail.com> wrote:

> Hi Jeff,
>
>  There is an algorithm to build the dominator tree that is O(n2),
> where n is the number of nodes on the control flow graph. I believe
> exists another that is linear, but I don't which one of them is
> implemented in LLVM.
>
>  The problem is that the branch predictor requires post dominance
> information. None of the LLVM basic passes require post dominance
> information (AFAIK), hence it is not available for us to use for free.
> That's why there is a hidden cost involved with our pass.
>
>  []z, Andrei
>
> On Wed, Nov 3, 2010 at 8:22 AM, Jeff Kunkel <jdkunk3 at gmail.com> wrote:
> > 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/93cf38da/attachment.html>