[LLVMdev] Complex regalloc contraints

[Lang Hames]

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>