similar to: linear-scan RA

How precise is the interference checking (to my mind, a great weakness of linear scan)? Is there way to do coalescing (the great strength of coloring)? I ask these questions because we (guys I work with) see loops where there's a little register juggling that seems unnecessary. Is there a paper that describes what y'all do? Thanks, Preston On Mon, Sep 10, 2018 at 9:57 AM, Matthias

> The underlying liveness datastructure is a list of ranges where each vreg is alive > (ranges in terms of instructions numbered). I remember a couple of later linear scan > papers describing the same thing (Traub et.al. being the first if I remember correctly). > That should be as accurate as you can get in terms of liveness information. It depends on the details. For example, given

The phi instruction is irrelevant; just the way I think about things. The question is if the allocator believes that t0 and t2 interfere. Perhaps the coalescing example was too simple. In the general case, we can't coalesce without a notion of interference. My worry is that looking at interference by ranges of instruction numbers leads to inaccuracies when a range is introduced by a copy.

> On Sep 10, 2018, at 5:25 PM, Matthias Braun <mbraun at apple.com> wrote: > > > >> On Sep 10, 2018, at 5:11 PM, Preston Briggs <preston.briggs at gmail.com <mailto:preston.briggs at gmail.com>> wrote: >> >> The phi instruction is irrelevant; just the way I think about things. >> The question is if the allocator believes that t0 and t2

Hi, Using Chaitin's approach, removing a copy via coalescing could expose more opportunities for coalescing. So he would iteratively rebuild the interference graph and check for more opportunities. Chaitin was also careful to make sure that the source and destination of a copy didn't interfere unnecessarily (because of the copy alone); that is, his approach to interference was very

Yes, I quite liked the things I've read about the PBQP allocator. Given what the hardware folks have to go through to get 1% improvements in scalar code, spending 20% (or whatever) compile time (under control of a flag) seems like nothing. And falling back on "average code" is a little disingenuous. People looking for performance don't care about average code; they care about

> On Sep 11, 2018, at 11:42 AM, Quentin Colombet <quentin.colombet at gmail.com> wrote: > > Le mar. 11 sept. 2018 à 11:23, Preston Briggs > <preston.briggs at gmail.com> a écrit : >> >> Yes, I quite liked the things I've read about the PBQP allocator. >> >> Given what the hardware folks have to go through to get 1% improvements in scalar code,

Hi GCC and LLVM developers, I am learning Register Allocation algorithms and I am clear that: * Unlimited VirtReg (pseudo) -> limited or fixed or alias[1] PhysReg (hard) * Memory (20 - 100 cycles) is expensive than Register (1 cycle), but it has to spill code when PhysReg is unavailable * Folding spill code into instructions, handling register coallescing, splitting live ranges, doing

On 12/14/2017 10:18 PM, Leslie Zhai wrote: > Hi GCC and LLVM developers, > > I am learning Register Allocation algorithms and I am clear that: > > * Unlimited VirtReg (pseudo) -> limited or fixed or alias[1] PhysReg > (hard) > > * Memory (20 - 100 cycles) is expensive than Register (1 cycle), but > it has to spill code when PhysReg is unavailable > It might be

I'm just starting to dive into llvm, hoping to implement a good graph coloring register allocator. I gather that this has been discussed before. What is the RegAllocGraphColoring.cpp currently in the sources? It seems to be the Fred Chow algorithm but it's not mentioned in the documentation anywhere. Does it work? -Dave

On 4/3/07, David Greene <greened at obbligato.org> wrote: > > I'm just starting to dive into llvm, hoping to implement a > good graph coloring register allocator. I gather that this > has been discussed before. > > What is the RegAllocGraphColoring.cpp currently in the > sources? It seems to be the Fred Chow algorithm but > it's not mentioned in the

I'm working on generating code for a machine that has a register set kind of like the 68000. For those who don't recall, the 68K has 8 Data registers that can be used for ordinary integer instructions like add, subtract, multiply, shift, etc., and 8 Address registers that can be use for integer addition and a few other things, especially base registers for addressing modes. The Data

Erkan, you're right. Sorry about that. Attached is the most recent version. Preston Hi Preston, > I am trying to use DA as well. I used your example and commands that you > wrote in order to get DA information. > However, it does not report any dependence info. > I am wondering whether your local copy differs from the one on the > repository ? > Thanks. > Erkan.

On Wed, Oct 3, 2012 at 10:15 AM, Matthieu Moy <Matthieu.Moy at grenoble-inp.fr> wrote: > Preston Briggs <preston.briggs at gmail.com> writes: >> Think about costs asymptotically; that's what matters. Calls and >> returns require constant time, just like addition and multiplication. > > Constant time, but not necessarily constant memory. > > Deep recursion

Hi all, Unfortunately, all my Hunks are failed when I apply : patch -p1 < da.patch command. The problem might be due to the fact that da.patch file was created against revision 167549, but I am on revision 167719 (I believe the most recent one). I am not sure if this cause the problem ? But Preston may I ask you to generate the patch file against revison 167719 ? Thanks in advance. On

On 11/02/2012 11:02 AM, Hal Finkel wrote: > ----- Original Message ----- >> From: "Tobias Grosser" <tobias at grosser.es> >> To: "preston briggs" <preston.briggs at gmail.com> >> Cc: "Benjamin Kramer" <benny.kra at gmail.com>, "LLVM Developers Mailing List" <llvmdev at cs.uiuc.edu> >> Sent: Friday, November

I just uploaded a blog post outlining the new register allocation algorithm in LLVM 3.0. http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html Please direct comments here. /jakob

On 11/02/2012 10:21 AM, Preston Briggs wrote: > > My initial guess is that a conservative fix is quick and small (make > sure the underlying pointers are loop invariant, otherwise give up). A > better approach would be to somehow turn code like the example into > array references that can be analyzed. I'll need to think about this and > do some reading. Hi Preston, I looked

Preston, thanks for the explanation and patch. Now it's printing the direction and distance values. On Tue, Nov 13, 2012 at 12:22 PM, Preston Briggs <preston.briggs at gmail.com>wrote: > Erkan, you're right. Sorry about that. > Attached is the most recent version. > > Preston > > > > Hi Preston, >> I am trying to use DA as well. I used your example

I'd like a value, call it Bottom, such that SE->getAddExpr(Bottom, X) => Bottom SE->getMulExpr(Bottom, X,) => Bottom isKnownPredicate(any, Bottom, X) => false etc. I can write code to make NULL work like I want, but it would be simpler if something was already defined. I'm wondering about SCEV::Unknown. The documentation suggests I could perhaps use it for a