Hi Carlos, Jakob,
The PBQP allocator was designed to support a very wide range of constraints,
and can handle something like this easily.
Say you have 4 of these orX/irX registers, then for any pair of virtual
registers used in such an add instruction you would add the following
constraint matrix to the PBQP instance:
[ 0 inf inf inf ]
[ inf 0 inf inf ]
[ inf inf 0 inf ]
[ inf inf inf 0 ]
The rows and columns of this matrix reflect the storage locations that the
allocator can assign, and the elements represent the cost of a specific
assignment. Say the rows represent the set { or1, or2, or3, or4 } and the
columns represent { ir1, ir2, ir3, ir4 }. The infinite cost elements
constrain the valid assignments to matching pairs.
Representing the constraint is dead easy, the trick would be making the
allocator aware of the constraint. At present the PBQP allocator only
"knows" about the basic RA constraints (aliasing, classes,
interference,
coalescing) described in LiveIntervals, MachineRegisterInfo and
TargetRegisterInfo. I have been meaning to generalize this though.
The design I have in mind is this: We add a method to TargetRegisterInfo
which returns a PBQPProblemBuilder for the target architectures. I implement
a base PBQPProblemBuilder by simply lifting the current construction process
out of the PBQP allocator and into its own class. Anyone (such as yourself,
Carlos) who wants to represent more esoteric constraints in their
architecture just extends this class, calls the base class to handle all the
basic constraints, then performs their own pass over the function to add in
their constraints:
struct MyTargetPBQPProblemBuilder : public PBQPProblemBuilder {
PBQP::Graph* buildProblemFor(MachineFunction *mf) {
PBQP::Graph* g = PBQPProblemBuilder::buildProblemFor(mf);
// Add additional constraints for my architecture here.
return g;
}
}
Any thoughts or comments? I think this should be a very straightforward
extension.
Cheers,
Lang.
On Wed, Sep 8, 2010 at 8:38 AM, Jakob Stoklund Olesen <stoklund at
2pi.dk>wrote:
>
> On Sep 7, 2010, at 3:01 AM, Carlos Sanchez de La Lama wrote:
>
> > The machine I am targeting has some special requirements for some
> > operations, say:
> >
> > ADD or1, ir1, r5
> >
> > would add ir1 (input reg 1) and r5 and put the result in or1 (output
reg
> > 1). The point id that input and output regs have to go paired (this
> > meaning an addition of ir1 with whatever always goes to or1, or an in
> > general irX + whatever goes to orX).
> >
> > AFAIK, InstrInfo.td only allow "$src = $dst" type
constraints. Is it
> > possible to describe more complex src/dst relations, like the one I
> > need?
>
> No, that is the only type of constraint supported (besides register
> classes).
>
> > This latter way is probably too hackish and that's why I am having
so
> > weird problems, but I have found no other way to achieve this. Is
there
> > one?
>
> It sounds like you need to present a more abstract architecture to the LLVM
> register allocator, but it is difficult to suggest one from the description
> you have given.
>
> /jakob
>
>
> _______________________________________________
> 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/20100908/d7bd4b06/attachment.html>
Hi Lang,> The PBQP allocator was designed to support a very wide range of > constraints, and can handle something like this easily.Glad to hear this :)> Say you have 4 of these orX/irX registers, then for any pair of > virtual registers used in such an add instruction you would add the > following constraint matrix to the PBQP instance: > > > [ 0 inf inf inf ] > [ inf 0 inf inf ] > [ inf inf 0 inf ] > [ inf inf inf 0 ] > > > The rows and columns of this matrix reflect the storage locations that > the allocator can assign, and the elements represent the cost of a > specific assignment. Say the rows represent the set { or1, or2, or3, > or4 } and the columns represent { ir1, ir2, ir3, ir4 }. The infinite > cost elements constrain the valid assignments to matching pairs.I think this is exactly what I need, also because in a future stage I would need to assign weights to some register pairs, not being impossible but being quite expensive in terms of performance.> The design I have in mind is this: We add a method to > TargetRegisterInfo which returns a PBQPProblemBuilder for the target > architectures. I implement a base PBQPProblemBuilder by simply lifting > the current construction process out of the PBQP allocator and into > its own class. Anyone (such as yourself, Carlos) who wants to > represent more esoteric constraints in their architecture just extends > this class, calls the base class to handle all the basic constraints, > then performs their own pass over the function to add in their > constraints: > > > struct MyTargetPBQPProblemBuilder : public PBQPProblemBuilder { > PBQP::Graph* buildProblemFor(MachineFunction *mf) { > PBQP::Graph* g = PBQPProblemBuilder::buildProblemFor(mf); > // Add additional constraints for my architecture here. > return g; > } > } > > > Any thoughts or comments? I think this should be a very > straightforward extension.I find it quite suiting my problem. If this extension is added I will surely use it. Thanks a lot! Carlos
On Sep 7, 2010, at 6:27 PM, Lang Hames wrote:> The design I have in mind is this: We add a method to TargetRegisterInfo which returns a PBQPProblemBuilder for the target architectures. I implement a base PBQPProblemBuilder by simply lifting the current construction process out of the PBQP allocator and into its own class. Anyone (such as yourself, Carlos) who wants to represent more esoteric constraints in their architecture just extends this class, calls the base class to handle all the basic constraints, then performs their own pass over the function to add in their constraints: > > struct MyTargetPBQPProblemBuilder : public PBQPProblemBuilder { > PBQP::Graph* buildProblemFor(MachineFunction *mf) { > PBQP::Graph* g = PBQPProblemBuilder::buildProblemFor(mf); > // Add additional constraints for my architecture here. > return g; > } > } > > Any thoughts or comments? I think this should be a very straightforward extension.If a target requires PBQP to work properly, it is going to be registering a new default register allocator constructor. It might as well register a function that allocates AND configures PBQP properly then. There is no need for a target hook. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100908/ab989fb8/attachment.html> -------------- next part -------------- A non-text attachment was scrubbed... Name: smime.p7s Type: application/pkcs7-signature Size: 1929 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100908/ab989fb8/attachment.bin>
Hi Jakob, That's a good point. I'll factor out the problem builder in the next couple of days and drop a mail to the list explaining how to write extensions. Cheers, Lang. On Thu, Sep 9, 2010 at 12:21 AM, Jakob Stoklund Olesen <stoklund at 2pi.dk>wrote:> > On Sep 7, 2010, at 6:27 PM, Lang Hames wrote: > > The design I have in mind is this: We add a method to TargetRegisterInfo > which returns a PBQPProblemBuilder for the target architectures. I implement > a base PBQPProblemBuilder by simply lifting the current construction process > out of the PBQP allocator and into its own class. Anyone (such as yourself, > Carlos) who wants to represent more esoteric constraints in their > architecture just extends this class, calls the base class to handle all the > basic constraints, then performs their own pass over the function to add in > their constraints: > > struct MyTargetPBQPProblemBuilder : public PBQPProblemBuilder { > PBQP::Graph* buildProblemFor(MachineFunction *mf) { > PBQP::Graph* g = PBQPProblemBuilder::buildProblemFor(mf); > // Add additional constraints for my architecture here. > return g; > } > } > > Any thoughts or comments? I think this should be a very straightforward > extension. > > > If a target requires PBQP to work properly, it is going to be registering a > new default register allocator constructor. > > It might as well register a function that allocates AND configures PBQP > properly then. There is no need for a target hook. > > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100909/560327b3/attachment.html>