[LLVMdev] Static Profiling Algorithms in LLVM

[Andrei Alvares]

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