similar to: [LLVMdev] Removing the bigblock register allocator.

Hi Lang, There are at least two projects that were using BigBlock, directly or indirectly. One approach is described in the paper "Register Spilling and Live-Range Splitting for SSA-Form Programs" by Matthias Braun and Sebastian Hack. It can be found here: http://pp.info.uni-karlsruhe.de/publication.php?id=braun09cc http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf

On Jul 29, 2009, at 3:14 PM, Roman Levenstein wrote: > Hi Lang, > > There are at least two projects that were using BigBlock, directly or > indirectly. Hi Roman, We have many plans to rip out linscan and replace it with something that handles large blocks better. That's not the issue :). The problem is that bigblock is unmaintained and bitrotted. Since noone is working

Hi I just stumbled upon this paper. While i just skimmed over it it seems as if the authors say that their algorithm is more efficient than the llvm 2.3 algorithm? So i thought that might be interesting? http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf Disclaimer: I have no affiliation with the authors and stumbled in a slightly unrelated search over this paper. ST

Hi Chris, 2009/7/30 Chris Lattner <clattner at apple.com>: > > On Jul 29, 2009, at 3:14 PM, Roman Levenstein wrote: > >> Hi Lang, >> >> There are at least two projects that were using BigBlock, directly or >> indirectly. > > Hi Roman, > > We have many plans to rip out linscan and replace it with something > that handles large blocks better.

On Thursday 14 January 2010 15:56, ST wrote: > Hi > > I just stumbled upon this paper. While i just skimmed over it it seems as > if the authors say that their algorithm is more efficient than the llvm 2.3 > algorithm? So i thought that might be interesting? > > http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf Don't trust it. The abstract clearly

Am Donnerstag, den 14.01.2010, 16:35 -0600 schrieb David Greene: > On Thursday 14 January 2010 15:56, ST wrote: > > Hi > > > > I just stumbled upon this paper. While i just skimmed over it it seems as > > if the authors say that their algorithm is more efficient than the llvm 2.3 > > algorithm? So i thought that might be interesting? > > > >

The allocator you are building, is it the Hack's and Goos's polynomial time algorithm? On Tue, Oct 5, 2010 at 7:14 PM, Cameron Zwarich <zwarich at apple.com> wrote: > There is nothing that currently handles this properly, as far as I know. If you have a phi > > c = phi(a, b) > > where a, b and c are all assigned distinct stack slots, then copies must be inserted in

For spilling, I plan to use the Hack-Braun generalization of the furthest-first heuristic for SSA: http://pp.info.uni-karlsruhe.de/uploads/publikationen/braun09cc.pdf For coloring, there are a few different approaches you can take, e.g. dominator tree scan, puzzle-solving, or a modified graph coloring / coalescing heuristic like IRC. The best quality for the least amount of implementation effort

Hi, The libFirm library ( http://www.info.uni-karlsruhe.de/software/libfirm/index.php?title=Main_Page ) is GPLed some time ago. libFirm is a library that provides an intermediate representation and optimizations for compilers. Programs are represented in a graph based SSA form. Several targets are supported, especially the x86. Many optimizations are very similar to those of LLVM. But there are

Hi Leslie, I suggest adding these 3 papers to your reading list. Register allocation for programs in SSA-form Sebastian Hack, Daniel Grund, and Gerhard Goos http://www.rw.cdl.uni-saarland.de/~grund/papers/cc06-ra_ssa.pdf Simple and Efficient Construction of Static Single Assignment Form Matthias Braun , Sebastian Buchwald , Sebastian Hack , Roland Leißa , Christoph Mallon , and Andreas

On Jul 29, 2009, at 10:31 PM, Roman Levenstein wrote: > As far as I know, we have these ambitious plans since a while (just X > years), but there is no good replacement for a LLVM linear scan yet :) > The alternatives are either slower at compile time or generate > slower code. Sure, we've been able to make the current algorithm significantly better over the years. However,

Hi Duraid, > Hi everyone, > > Quick summary: > > LLVM now has a new register allocator particularly suitable for > compiling (very) large, machine-generated functions. Congrats! Very good job! > Longer story: > > I've recently been using LLVM in an application that involves JITing > > fairly large functions that have no control flow - they're

Hi everyone, Quick summary: LLVM now has a new register allocator particularly suitable for compiling (very) large, machine-generated functions. Longer story: I've recently been using LLVM in an application that involves JITing fairly large functions that have no control flow - they're just flat sequences of instructions, anywhere from 100 to 10000+ in size. (The control flow is

Hi Roman, > True. I'm working on the version of the linear scan based on Wimmer's > thesis. It supports live range splitting. I'd like to compare it with > yours. Do you have any good examples of those fairly large functions > that are just flat sequences of instructions, anywhere from 100 to > 10000+ in size??? You can find a couple attached to bug #1512, but I'm

Hi Roman, > BTW, the research papers that I mentioned are not about improving > register allocation for large blocks (which was the target in the case > of BigBlock). They are about register allocation for general purpose > CFGs. And they report improvements (greatly reduced number of > load/stores for spills) over linear scan. The compilation time is also > comparable with

Hi Lang and Arnaud, I've been testing out the PBQP allocator for Thumb-2 and have ran into a problem I'd love to get your input on. The problem is exemplfied in the codegen for the function @bar in the attached IR file: bar: push {r4, lr} sub sp, #12 (1) movw r2, :lower16:.L_MergedGlobals (1) movt r2, :upper16:.L_MergedGlobals ldm.w r2,

Hi James, I’ve tried to play in the past with the allocation order, which can definitely be tweaked and improved. The metric we use for spill cost being what it is (i.e. not targeted for PBQP, but that’s a different subject), I found it made real sense to use some other heuristics to sort nodes (on top of the spill cost) when there was a tie between them. Of course, that’s a heuristic and it can

On 08/22/2017 03:59 AM, Alex Bradbury via llvm-dev wrote: > On 21 August 2017 at 13:23, Martin J. O'Riordan via llvm-dev > <llvm-dev at lists.llvm.org> wrote: >> But there is a downside. >> >> For each of the above I also have variations that are a result of different >> processor and ISA versions, and because of this I have to use >> ‘multiclass/defm’

Hi, > > I think one idea to improve the situation is to consider the cost vector of adjacent nodes during RN. Let's say you decided to do a RN for node A and want to compute the costs for choosing register %Ri. The current implementation does this by computing min(row/column i of edge A <--> B) but you can do better by adding B's cost vector to the row/column before computing

Quoting Bill Wendling <isanbard at gmail.com>: > Hi Nikolaos, > > I have an alpha version of Chow & Hennesey's priority-based graph > coloring algorithm. It's suffering from some bit-rotting -- e.g., > there's some trouble with how it calculates "forbidden" registers. > You're welcome to the code, if you'd like to hack on it. I've been