<div>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.</div><div><br></div>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. <div>
<br><div><div>- Thanks</div><div>- Jeff Kunkel<br><br><div class="gmail_quote">On Wed, Nov 3, 2010 at 3:21 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;">Hi Jeff,<br>
<br>
There is an algorithm to build the dominator tree that is O(n2),<br>
where n is the number of nodes on the control flow graph. I believe<br>
exists another that is linear, but I don't which one of them is<br>
implemented in LLVM.<br>
<br>
The problem is that the branch predictor requires post dominance<br>
information. None of the LLVM basic passes require post dominance<br>
information (AFAIK), hence it is not available for us to use for free.<br>
That's why there is a hidden cost involved with our pass.<br>
<br>
[]z, Andrei<br>
<div><div></div><div class="h5"><br>
On Wed, Nov 3, 2010 at 8:22 AM, Jeff Kunkel <<a href="mailto:jdkunk3@gmail.com">jdkunk3@gmail.com</a>> wrote:<br>
> You said it was expensive, but if you had to put a big-o estimate on it,<br>
> what would it be?<br>
> -Thanks<br>
> Jeff Kunkel<br>
><br>
> On Tue, Nov 2, 2010 at 8:54 PM, Andrei Alvares <<a href="mailto:logytech@gmail.com">logytech@gmail.com</a>> wrote:<br>
>><br>
>> Hello Jeff,<br>
>><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<br>
>> > of<br>
>> > my register allocator.<br>
>><br>
>> 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>
>><br>
>> > Second, I am surprised it did not make it into the tree. Since more is<br>
>> > being<br>
>> > done with register allocation as a while "RegAllocBasic" was just put<br>
>> > in, I<br>
>> > hope this is looked at again.<br>
>> > Do you have a working svn copy?<br>
>><br>
>> 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>
>><br>
>> > Also, could you send me a copy/link to that '94 paper off the list<br>
>> > please?<br>
>><br>
>> 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>
>> Andrei<br>
>><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>><br>
>> > 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<br>
>> >>> <<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<br>
>> >>> >> 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>
><br>
><br>
</div></div></blockquote></div><br></div></div></div>