<div dir="ltr">Hi Bhushan, David,<div><br></div><div>Dave's advice on getting started with LLVM is excellent, so I'll just comment on the PBQP bit.</div><div><br></div><div class="gmail_extra">Bernhard and I did some work using Branch and Bound on top of PBQP for register allocation. In our experience it was best to run branch-and-bound as a separate step after the heuristic solver. The idea is that the initial solution from the heuristic solver gives you a tight upper bound for your branch-and-bound search, which speeds convergence.</div><div class="gmail_extra"><br></div><div class="gmail_extra">On the implementation side, you would probably just want to extend the code in lib/CodeGen/RegAllocPBQP.cpp. Currently the main loop (tidied for clarity) looks like:</div><div class="gmail_extra"><br></div><div class="gmail_extra"><font face="monospace, monospace">while (!PBQPRAComplete) {</font></div><font face="monospace, monospace">  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));</font><div><font face="monospace, monospace">  initializeGraph(G, VRM, *VRegSpiller);</font></div><div><font face="monospace, monospace">  ConstraintsRoot->apply(G);<br>  PBQP::Solution Solution = PBQP::RegAlloc::solve(G);</font></div><div><font face="monospace, monospace">  PBQPRAComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);</font><div class="gmail_extra"><font face="monospace, monospace">}</font></div><div class="gmail_extra"><br></div><div class="gmail_extra">You'd want to hook your branch and bound solver up as an additional step between those last two lines (changes shown in red):</div><div class="gmail_extra"><br></div><div class="gmail_extra"><div class="gmail_extra"><font face="monospace, monospace">while (!PBQPRAComplete) {</font></div><font face="monospace, monospace">  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));</font></div><div class="gmail_extra"><div><font face="monospace, monospace">  initializeGraph(G, VRM, *VRegSpiller);</font></div><div><font face="monospace, monospace">  ConstraintsRoot->apply(G);<br></font><font face="monospace, monospace">  <font color="#ff0000">PBQPRAGraph GClone(G);</font><br></font><font face="monospace, monospace">  PBQP::Solution <font color="#ff0000">InitialSolution</font> = PBQP::RegAlloc::solve(G);</font></div><div><font face="monospace, monospace">  <font color="#ff0000">PBQP::Solution BranchAndBoundSolution = PBQP::branchAndBound(GClone, InitialSolution);</font></font></div><div><font face="monospace, monospace">  PBQPRAComplete = mapPBQPToRegAlloc(G, <font color="#ff0000">BranchAndBoundSolution</font>, VRM, *VRegSpiller);</font><div class="gmail_extra"><font face="monospace, monospace">}</font></div></div><div><br></div><div>The clone of the graph is required because the current solver is destructive on the graph. Cloning isn't free but it's reasonably cheap, since the cost-matrices and vectors are shared between the graphs.</div><div><br></div></div><div class="gmail_extra">Cheers,</div><div class="gmail_extra">Lang.</div><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 8, 2015 at 3:23 PM, David Blaikie <span dir="ltr"><<a href="mailto:dblaikie@gmail.com" target="_blank">dblaikie@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span class="">On Fri, Mar 6, 2015 at 7:28 PM, Bhushan Sonawane <span dir="ltr"><<a href="mailto:bhushan.s.94@gmail.com" target="_blank">bhushan.s.94@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><div>Hello,<br><br></div>I have worked on LLVM for my project related to Register Allocation.<br></div><div>Bernhard Scholz suggested that Implementing Branch and Bound Heuristic for Reduce N in PBQP register Allocation for LLVM would be to great project to work on.<br></div></div></blockquote></span><div><br>+Lang, who implemented the PBQP register allocator in LLVM. I believe it shouldn't be too hard to find the reduce N heuristic & implement an alternative one.<br> </div><span class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>I'm looking forward to implement it in LLVM system.<br></div><div>How should i get start about it ?<br></div></div></blockquote></span><div><br>Assuming you've gone through all of this: <a href="http://llvm.org/docs/GettingStarted.html" target="_blank">http://llvm.org/docs/GettingStarted.html</a> and got yourself a build setup, you might want to read <a href="http://llvm.org/docs/DeveloperPolicy.html" target="_blank">http://llvm.org/docs/DeveloperPolicy.html</a> which describes how to contribute to the LLVM project.<br><br>As always: "Patches welcome"<br> </div><span class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div></div><div>I would also like to know about some of the other projects in LLVM.<br></div></div></blockquote></span><div><br>We have a list of open project ideas though it tends to bitrot - so you might want to check before you attempt any (maybe someone's solved it before, or they have some context on prior attempts/suggestions/etc): <a href="http://llvm.org/OpenProjects.html" target="_blank">http://llvm.org/OpenProjects.html</a><br><br>- David<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Thanks,<br></div><div>Bhushan <br></div></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">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></blockquote></div><br></div></div>
</blockquote></div><br></div></div></div>