Hi David,
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.
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.
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?
Evan
Index: llvm/include/llvm/CodeGen/RegisterAllocator.h
==================================================================---
llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0)
+++ llvm/include/llvm/CodeGen/RegisterAllocator.h (revision 0)
@@ -0,0 +1,41 @@
+//===-- RegisterAllocator.h - Register Coalescing Interface ------*-
C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is
distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT
for details.
+//
+//
===---------------------------------------------------------------------
-===//
+//
+// This file contains the abstract interface for register allocators,
+// allowing them to provide information to coalescers.
+//
+//
===---------------------------------------------------------------------
-===//
+
+#ifndef LLVM_CODEGEN_REGISTER_ALLOCATOR_H
+#define LLVM_CODEGEN_REGISTER_ALLOCATOR_H
+
+#include <llvm/CodeGen/LiveInterval.h>
+
+namespace llvm
+{
+ class MachineInstruction;
+
+ class RegisterAllocator {
+ public:
+ /// Return whether this copy should be considered for coalescing.
+ virtual bool coalesceThisCopy(const MachineInstruction &) {
+ // Be aggressive, but possibly bad
+ return(true);
This is, stylistically inconsistent with the rest of the code base.
Just "return true;" please.
+ };
+
+ /// Return whether two live ranges interfere.
+ virtual bool interfere(const LiveInterval &a,
+ const LiveInterval &b) {
+ // A naive test
+ return(a.overlaps(b));
+ };
+ };
+}
+
+#endif
Property changes on: llvm/include/llvm/CodeGen/RegisterAllocator.h
___________________________________________________________________
Name: svn:eol-style
+ LF
What's this?
On Jul 13, 2007, at 11:32 AM, David A. Greene wrote:
> On Wednesday 11 July 2007 15:07, Christopher Lamb wrote:
>
>> Could it be possible for there to be a harness type interface that
>> would allow coalescers that support both modes to be hooked into the
>> pass registration, and those that depend on the allocator not be
>> registered as passes?
>
> I have a patch for this kind of thing attached. Please take a look
> and let
> me know if it looks reasonable. It's not complete yet. I'm about
> to embark
> on implementing a new coalescer that will not be managed by
> PassManager
> and as I do that I'll figure out any additional interfaces that are
> needed.
>
> If this looks good, I'll commit it and later on I'll commit any
> additions I
> make to this basic interface.
>
> -Dave
> <coalscing_patch.txt>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Mon, 2007-07-16 at 16:19 -0700, Evan Cheng wrote:> Property changes on: llvm/include/llvm/CodeGen/RegisterAllocator.h > ___________________________________________________________________ > Name: svn:eol-style > + LF > > What's this?Its a property change. In Subversion every file and directory can have properties associated with them. For example the svn:ignore property on a directory tells svn to ignore certain non-versioned files. Simlarly svn:execute tells svn that the file is executable and so should have execute permissions on it when its checked out. This particular one is saying that the end-of-line style for this file should be just LF rather than CR-LF. Our standard is the Unix standard, LF and that is also the subversion default. This property set is superfluous but harmless. Reid.
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. 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 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.> 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. 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. 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. 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. -Dave
On Monday 16 July 2007 18:32, Reid Spencer wrote:> On Mon, 2007-07-16 at 16:19 -0700, Evan Cheng wrote: > > Property changes on: llvm/include/llvm/CodeGen/RegisterAllocator.h > > ___________________________________________________________________ > > Name: svn:eol-style > > + LF > > > > What's this?> This particular one is saying that the end-of-line style for this file > should be > just LF rather than CR-LF. Our standard is the Unix standard, LF and > that is also the subversion default. This property set is superfluous > but harmless.Yeah, I wondered about that too. I haven't ever seen that in any of the commits I've done in the past. I agree it's harmless, but curious. -Dave
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