On Jul 17, 2007, at 8:40 AM, David Greene wrote:> On Monday 16 July 2007 18:19, Evan Cheng wrote: > >> Sorry I should have replied earlier. I really don't like this dual >> interface approach. To me, this muddles things without offering any >> real useful new functionalities. > > Ok. See below for the rationale. > >> IMHO, if a register coalescer is tied to a particular allocator. Then >> either it should simply belong to that allocator or that we have to >> allow the allocator to act as a pass manager itself, i.e. it can >> control what passes to run as part the allocating process. I don't >> know if the pass manager allows that functionality. If not, then >> that's something we should add because there are other passes that >> can benefit from it. > > I'm not sure I fully understand what you're proposing. The reason I > went with the AliasAnalysis-like construct is that I envisioned a > "-coalescer=<type>" user option, similar to how alias analysis and > register allocation works. Somehow we have to make that option > work with independent register coalescers (those derived from > MachineFunctionPass or equivalents that can run through the > PassManager) and those that are tied to some abstract register > allocation algorithm. A coalescer that runs in conjunction with an > allocator need not be tied to a particular implementation of register > allocation. For example, George and Appel's Iterated Register > Coalescing can work with any concrete implementation of graph > coloring (and there are lots of variations out there) and can probably > work with other algorithms as well. So if we can avoid it, I'd > rather not > be limited to hard-coding these things.Ok.> > These two requirements led to the abstract RegisterCoalescer > interface in the patch. This is the interface that register > allocators > know about. Likewise, coalescers need an abstract interface to > register allocators to ask questions and do other things.If the two modules need to share information. I think you want a third module to encapsulate it.> > If we decide that we don't need this flexibility, that's fine with > me. I was > working based on the needs expressed by Tanya and Reid and the > implementation suggested by Christopher Lamb. I'm not wedded to it. > > To me, the most important thing is a simple user interface. We > want one > command-line option that picks a coalescer and the user should not > have > to worry about whether the coalescer is implemented as a separate pass > or works as part of the register allocator. The user should not > have to worry > about whether the coalescer and register allocator he or she specifies > are compatable in the sense that the register allocator knows the > guts of > the coalescer and vice-versa. That seems to drive the need for > abstract > interfaces for both.I don't care for a MachineFunctionPass that can be directly called. I think it's a very good idea to keep the coalescers independent from the allocators. If that's desired, we should enhance passmanager so each allocator can run some sub-passes as part of the allocation pass. For now, I think we leave it as it is. If the user picked a coalescer that doesn't work with the register allocator of choice, we can output an error (or a warning and override the choice).> >> Also, on this particular file below. Seems to me these queries do not >> belong to the register allocator. Perhaps a utility class that tracks >> interference information that can be accessed by both the allocator >> and the coalescer? Also, why is coalesceThisCopy() needed? Shouldn't >> the coalescer be responsible for making the decision? > > Register allocators know information about interference, for example, > the interference graph in a coloring allocator. The classic > coalescing > algorithm examines the interference graph and looks for copies between > allocation units whose corresponding nodes do not have an edge between > them in the graph. That's why that interface is there.Right, then perhaps the interference graph should not be part of allocator. Both the allocator and coalescer can be clients. It's weird to me for the coalescer to directly query the allocator especially since the goal is to keep the coalescer independent from the allocator.> > A utility class is an interesting idea. In fact I've been thinking > about how > one might go about separating the essentials of, say, a graph coloring > allocator and the particular heuristics it uses to make decisions. > A graph > is a graph and could certainly be factored out into a separate > utility class, > which could provide interfaces for queries. A policy-based design > is one > possibility, where a generic graph coloring algorithm is written as > a template > and the developer passes policy types that it uses to configure > itself with > heuristics. > > The larger question is whether a good abstract interface for the > utility class > can be found that can support difference representations such as > graphs, > the linear-scan stuff, etc. It seems hard to me. I'm not even sure a > coalescer that wants to work with an allocator can work with every > register > allocation algorithm. For example, can the linear-scan algorithm > satisfy > the queries asked by a coalescer that expects a graph coloring > algorithm? > I don't know. It would be nice if it could, to ease the burden on > the user as > explained above. I think it can if the queries are not too fine- > grained. The > interface in the patch is pretty much the coarsest grain that I > could think > of. It would be bad, for example, to add interfaces like "does > this graph > node have neighbors of degree > N?" because not every allocator could > answer it.I don't think we need that level of abstraction right now. :-)> > The coalesceThisCopy interface is there for similar reasons. Some > coalescing > algorithms (Briggs' conservative coalescing is a good example) > examine the > interference graph and apply heuristics based on the degree of the > neighbors > of nodes being coalesced. Your utility class could provide > interfaces to make > more fine-grained queries, but as noted above, it seems a bit > harder as > various register allocators may use very difference > representations. So > coalesceThisCopy is certainly a compromise. It does move some of the > decision-making for coalescing into the register allocator. You > raise a good > point and I'll think about how we can improve this.Ok.> > Do you have suggestions for how to move forward based on the > above? I have > some critical work to do here and it's going to require that we get > pluggable > ]coalescers working at some level. We can of course evolve the > interface as > we learn.Assuming the interference graph is available, does the coalescer need any information from the allocator to make decisions? Are you designing the coalescer so it always run before allocation? If so, please keep it simple. :-) Make it operate on existing live interval information (perhaps enhanced if needed) and the new interference graph class (again, if needed). I think as a first step, the coalescer should be as aggressive as possible (i.e. no concerns for what the allocator would do). Evan> > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Tuesday 17 July 2007 13:06, Evan Cheng wrote:> > These two requirements led to the abstract RegisterCoalescer > > interface in the patch. This is the interface that register > > allocators > > know about. Likewise, coalescers need an abstract interface to > > register allocators to ask questions and do other things. > > If the two modules need to share information. I think you want a > third module to encapsulate it.Yes, that makes sense to me.> I don't care for a MachineFunctionPass that can be directly called. I > think it's a very good idea to keep the coalescers independent from > the allocators. If that's desired, we should enhance passmanager so > each allocator can run some sub-passes as part of the allocation > pass.I agree that this is a good long-term goal. Unfortunately, I don't have the time resources to implement it right now. If someone else can take up this as a sub-project, that would be great! I agree that several other passes could make use of it.> For now, I think we leave it as it is. If the user picked a > coalescer that doesn't work with the register allocator of choice, we > can output an error (or a warning and override the choice).Ok.> > Register allocators know information about interference, for example, > > the interference graph in a coloring allocator. The classic > > coalescing > > algorithm examines the interference graph and looks for copies between > > allocation units whose corresponding nodes do not have an edge between > > them in the graph. That's why that interface is there. > > Right, then perhaps the interference graph should not be part of > allocator. Both the allocator and coalescer can be clients. It's > weird to me for the coalescer to directly query the allocator > especially since the goal is to keep the coalescer independent from > the allocator.Good point.> > The larger question is whether a good abstract interface for the > > utility class can be found that can support difference representations > > such as graphs, the linear-scan stuff, etc.> I don't think we need that level of abstraction right now. :-)True enough. But I need some kind of abstraction, because for various reasons I don't have an interference graph implementation I can check in. But yet I want to check something in that others can use.> Assuming the interference graph is available, does the coalescer need > any information from the allocator to make decisions?Not that I'm aware of. And in the future if something more is needed, then we can do another round of factoring.> Are you designing the coalescer so it always run before allocation? If so, > please keep it simple. :-)Believe me, I'm trying to keep it as simple as possible. The coalescer I'm working on doesn't run "before" allocation. It runs in conjunction with it. Decisions have to be made here as to whether it gets pushed out into the public repository and because of the way it's designed, the general llvm community might not be interested in it anyway. It's more complex due to some additional requirements on this end that don't have any relevance to the llvm community.> Make it operate on existing live interval information (perhaps enhanced if > needed)Yep, it does. Hence the factoring effort on the current coalescer.> and the new interference graph class (again, if needed).As stated above, I'd like to make this an abstract interface to an interference graph, due to complexity of my implementation that the llvm community doesn't care about.> I think as a first step, the coalescer should be as aggressive as possible > (i.e. no concerns for what the allocator would do).Well, that's the current coalescer, and the whole reason I'm writing a new one is that we don't want it to be so aggressive. In the end, what I am able to contribute back at this point is the infrastructure to make it easy to implement new coalescers. Due to legal and other issues, I can't contribute any concrete implementations right now, and it's not likely I'll be able to do so any time soon. But I do want to make sure that the infrastructure works for everyone. This is very good feedback. I'll take it and rework the patch. -Dave
On Tuesday 17 July 2007 14:21, David Greene wrote:> > I don't care for a MachineFunctionPass that can be directly called. I > > think it's a very good idea to keep the coalescers independent from > > the allocators. If that's desired, we should enhance passmanager so > > each allocator can run some sub-passes as part of the allocation > > pass. > > I agree that this is a good long-term goal. Unfortunately, I don't have > the time resources to implement it right now. If someone else can take up > this as a sub-project, that would be great! I agree that several other > passes could make use of it.I've got something in the works that provides an interface for the coalescer to query an interference object. So the RegisterAllocator class no longer exists and coalescers don't directly depend on register allocators. As a bonus, the interference interface doesn't make any assumptions about the underlying representation but has the interfaces necessary to make equivalent queries to what a coalescer might ask an interference graph. As a proof of concept, I have an example of what the linear scan algorithm might provide. It's very inefficient and in practice linear scan probably won't ever interact with a coalescer that partners with the allocator but it serves to show that the interface can be met by something that doesn't use a graph. I've also implemented a graph-based realization using what I currently have, but as I said in another message, I'm not at liberty to release that publicly. It's pretty straightforward code, though. The RegisterCoalescer interface still exists because register allocators need to be able to invoke the coalescer, sometimes repeatedly. PassManager can't do that. The current SimpleRegisterCoalescer (which should really be named AggressiveRegisterCoalescer -- another patch on the way) inherits from both MachineFunctionPass and RegisterCoalescer. The former because it is run and managed by PassManager and the latter because it needs to belong to the RegisterAllocator AnalysisGroup, similar to how alias analysis works. We need a way for register allocators to ask PassManager for the coalescer object (even if the coalescer doesn't inherit from MachineFunctionPass) and this is the only way I know how to do it until someone takes on revamping how PassManager works and providing the capability of constructing hierarchies of PassManagers. I'm still working out getting things to build, etc. and will post a patch when I've got through all that. But does this sound like something closer to what we want? -Dave
On Jul 17, 2007, at 12:21 PM, David Greene wrote:> >> Are you designing the coalescer so it always run before >> allocation? If so, >> please keep it simple. :-) > > Believe me, I'm trying to keep it as simple as possible. The > coalescer I'm > working on doesn't run "before" allocation. It runs in conjunction > with it. > Decisions have to be made here as to whether it gets pushed out > into the > public repository and because of the way it's designed, the general > llvm > community might not be interested in it anyway. It's more complex > due to > some additional requirements on this end that don't have any relevance > to the llvm community.Ok. Then I think it's reasonable for it to be tied to the allocator. If there are stuff we want to factor out later. We can do so. Notice I said "we", I am hopeful you will consider contributing it to the public repository. :-)> >> Make it operate on existing live interval information (perhaps >> enhanced if >> needed) > > Yep, it does. Hence the factoring effort on the current coalescer. > >> and the new interference graph class (again, if needed). > > As stated above, I'd like to make this an abstract interface to an > interference graph, due to complexity of my implementation that the > llvm > community doesn't care about.Sounds good.> >> I think as a first step, the coalescer should be as aggressive as >> possible >> (i.e. no concerns for what the allocator would do). > > Well, that's the current coalescer, and the whole reason I'm > writing a new one > is that we don't want it to be so aggressive.Fair enough. I still believe most of the "harms" caused by an over- aggressive coalescer can be fixed later by the allocator with the help of splitting and rematerialization. But given the current implementation doesn't have either, it would be interesting to see what a smarter coalescer can do.> In the end, what I am able to contribute back at this point is the > infrastructure to make it easy to implement new coalescers. Due to > legal and other issues, I can't contribute any concrete > implementations > right now, and it's not likely I'll be able to do so any time > soon. But I do > want to make sure that the infrastructure works for everyone.Great. Thanks! Evan> > This is very good feedback. I'll take it and rework the patch. > > -Dave > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev