[LLVMdev] Open Projects in LLVM

[Lang Hames]

Hi Bhushan, David,

Dave's advice on getting started with LLVM is excellent, so I'll just
comment on the PBQP bit.

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.

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:

while (!PBQPRAComplete) {
  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
  initializeGraph(G, VRM, *VRegSpiller);
  ConstraintsRoot->apply(G);
  PBQP::Solution Solution = PBQP::RegAlloc::solve(G);
  PBQPRAComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);
}

You'd want to hook your branch and bound solver up as an additional step
between those last two lines (changes shown in red):

while (!PBQPRAComplete) {
  PBQPRAGraph G(PBQPRAGraph::GraphMetadata(MF, LIS, MBFI));
  initializeGraph(G, VRM, *VRegSpiller);
  ConstraintsRoot->apply(G);
  PBQPRAGraph GClone(G);
  PBQP::Solution InitialSolution = PBQP::RegAlloc::solve(G);
  PBQP::Solution BranchAndBoundSolution = PBQP::branchAndBound(GClone,
InitialSolution);
  PBQPRAComplete = mapPBQPToRegAlloc(G, BranchAndBoundSolution, VRM,
*VRegSpiller);
}

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.

Cheers,
Lang.

On Sun, Mar 8, 2015 at 3:23 PM, David Blaikie <dblaikie at gmail.com> wrote:

>
>
> On Fri, Mar 6, 2015 at 7:28 PM, Bhushan Sonawane <bhushan.s.94 at gmail.com>
> wrote:
>
>> Hello,
>>
>> I have worked on LLVM for my project related to Register Allocation.
>> 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.
>>
>
> +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.
>
>
>> I'm looking forward to implement it in LLVM system.
>> How should i get start about it ?
>>
>
> Assuming you've gone through all of this:
> http://llvm.org/docs/GettingStarted.html and got yourself a build setup,
> you might want to read http://llvm.org/docs/DeveloperPolicy.html which
> describes how to contribute to the LLVM project.
>
> As always: "Patches welcome"
>
>
>> I would also like to know about some of the other projects in LLVM.
>>
>
> 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):
> http://llvm.org/OpenProjects.html
>
> - David
>
>
>>
>> Thanks,
>> Bhushan
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150309/22c51037/attachment.html>