llvm dev - Sep 2010 - [LLVMdev] Complex regalloc contraints

Hi all,

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?

Also, I have tried making say or1 and ir1 parts of a single superreg
(op1reg), using "$src = $dst" and a pattern to wrap the operations
with
EXTRACT_SUBREG/INSERT_SUBREG compounds. But in that case I have two
problems: 1) the LLVM op operates over a vector reg, thus *overwrites*
the input also (and that is not what our machine does) 2) LLVM needs to
be able to copy those regs for two-addr instruction rewritting, but
input regs are not readable and output regs are not writable.

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?

Thanks and BR,

Carlos

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

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>