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