[LLVMdev] Static Profiling Algorithms in LLVM

[Andrei Alvares]

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