Simpler types in TableGen isel patterns

Project Infrastructure LLVM Dev List Archives
1

Currently, instruction selection patterns are defined like this:

  def : Pat<(and (not GR32:$src1), GR32:$src2),
            (ANDN32rr GR32:$src1, GR32:$src2)>;
  def : Pat<(and (not GR64:$src1), GR64:$src2),
            (ANDN64rr GR64:$src1, GR64:$src2)>;

TableGen infers the types of $src1 and $src2 from the specified register classes, and that is the only purpose of the register classes in a pattern like that. SelectionDAG doesn't really understand register classes, it only uses types.

If I try to constrain the register class in a pattern, like this:

  def : Pat<(and (not GR32_ABCD:$src1), GR32_ABCD:$src2),
            (ANDN32rr GR32_ABCD:$src1, GR32_ABCD:$src2)>;

I get completely ignored. SelectionDAG's InstrEmitter will still use the GR32 register class that was assigned to the i32 type.

When using register classes as proxies for types, it also becomes very difficult to support more than one legal type in a register class. If I were to entertain the heretic notion that an f32 might fit in a 32-bit register:

  def GR32 : RegisterClass<"X86", [i32, f32], 32, ...

TableGen explodes with a thousand type inference errors.

I think in most cases it would be much simpler and safer to specify pattern types directly:

  def : Pat<(and (not i32:$src1), i32:$src2),
            (ANDN32rr i32:$src1, i32:$src2)>;
  def : Pat<(and (not i64:$src1), i64:$src2),
            (ANDN64rr i64:$src1, i64:$src2)>;

This doesn't lose any type checking because the register classes of the instructions in the output pattern are still checked. It avoids the problem where type inference makes it impractical to add types to a register class to model instruction set extensions, and it makes it clear that patterns operate on types, not register classes.

I'll add support for this syntax unless someone can think of a reason I shouldn't. The notation using register classes gets to stay, I'm not removing it.

/jakob

2

From: "Jakob Stoklund Olesen" <stoklund@2pi.dk>
To: llvmdev@cs.uiuc.edu, llvmdev@cs.uiuc.edu, llvmdev@cs.uiuc.edu, llvmdev@cs.uiuc.edu
Sent: Thursday, March 21, 2013 1:26:25 PM
Subject: [LLVMdev] Simpler types in TableGen isel patterns

Currently, instruction selection patterns are defined like this:

  def : Pat<(and (not GR32:$src1), GR32:$src2),
            (ANDN32rr GR32:$src1, GR32:$src2)>;
  def : Pat<(and (not GR64:$src1), GR64:$src2),
            (ANDN64rr GR64:$src1, GR64:$src2)>;

TableGen infers the types of $src1 and $src2 from the specified
register classes, and that is the only purpose of the register
classes in a pattern like that. SelectionDAG doesn't really
understand register classes, it only uses types.

If I try to constrain the register class in a pattern, like this:

  def : Pat<(and (not GR32_ABCD:$src1), GR32_ABCD:$src2),
            (ANDN32rr GR32_ABCD:$src1, GR32_ABCD:$src2)>;

I get completely ignored. SelectionDAG's InstrEmitter will still use
the GR32 register class that was assigned to the i32 type.

When using register classes as proxies for types, it also becomes
very difficult to support more than one legal type in a register
class. If I were to entertain the heretic notion that an f32 might
fit in a 32-bit register:

  def GR32 : RegisterClass<"X86", [i32, f32], 32, ...

TableGen explodes with a thousand type inference errors.

I think in most cases it would be much simpler and safer to specify
pattern types directly:

  def : Pat<(and (not i32:$src1), i32:$src2),
            (ANDN32rr i32:$src1, i32:$src2)>;
  def : Pat<(and (not i64:$src1), i64:$src2),
            (ANDN64rr i64:$src1, i64:$src2)>;

This doesn't lose any type checking because the register classes of
the instructions in the output pattern are still checked. It avoids
the problem where type inference makes it impractical to add types
to a register class to model instruction set extensions, and it
makes it clear that patterns operate on types, not register classes.

I'll add support for this syntax unless someone can think of a reason
I shouldn't. The notation using register classes gets to stay, I'm
not removing it.

I think this is a good idea.

Is there a reason why we need the types again in the expansion? Would it be easy to make the syntax like this?

  def : Pat<(and (not i64:$src1), i64:$src2),
            (ANDN64rr $src1, $src2)>;

Thanks again,
Hal

3

This sounds great! I’ve been bitten in the past by trying to use a single class for multiple types.

Would it make sense to extend this to all DAG patterns? If I have an instruction def:

def ANDN64 : MyInst<(outs Reg64:$d), (ins Reg64:$a, Reg64:$b), “and.64 $d, $a, $b”, [(set Reg64:$d, (and (not (Reg64:$a, Reg64:$b))))]>;

would I now be able to write:

def ANDN64 : MyInst<(outs Reg64:$d), (ins Reg64:$a, Reg64:$b), “and.64 $d, $a, $b”, [(set i64:$d, (and (not (i64:$a, i64:$b))))]>;

?

4

That's just a quirk of the generic TableGen DAG syntax.

The 'i64' is the actual operand, and '$src1' is the name of the operand. The name is optional, but the operand itself is not.

It wouldn't be that hard to make the parser treat $src2 as ?:$src2 where '?' represents an UndefInit.

/jakob

5

Yes, that was my plan.

The ins and outs lists still need to be register classes for the instruction constraints, but the set pattern doesn't need them.

/jakob

6

Hey Jakob,

7

This makes a huge amount of sense to me. Besides your motivating problem, writing an isel pattern that matches things in terms of register classes doesn't make *any* sense: the input graph has type labels that are MVTs.

If you want to get *really* crazy, the ideal type system for dag nodes would be to allow either an EVT or a register class: after isel (and after some custom dag combines) the types of nodes should be register classes, since they are more specific than an MVT (or EVT).

-Chris

8

I think in most cases it would be much simpler and safer to specify pattern types directly:

def : Pat<(and (not i32:$src1), i32:$src2),
          (ANDN32rr i32:$src1, i32:$src2)>;
def : Pat<(and (not i64:$src1), i64:$src2),
          (ANDN64rr i64:$src1, i64:$src2)>;

This doesn't lose any type checking because the register classes of the instructions in the output pattern are still checked. It avoids the problem where type inference makes it impractical to add types to a register class to model instruction set extensions, and it makes it clear that patterns operate on types, not register classes.

This makes a huge amount of sense to me. Besides your motivating problem, writing an isel pattern that matches things in terms of register classes doesn't make *any* sense: the input graph has type labels that are MVTs.

Exactly. The register classes are misleading.

If you want to get *really* crazy, the ideal type system for dag nodes would be to allow either an EVT or a register class: after isel (and after some custom dag combines) the types of nodes should be register classes, since they are more specific than an MVT (or EVT).

Yes, that is also the direction I would like to go.

We have started taking baby steps in this direction with the 'untyped' MVT. The register class for an untyped DAG edge is determined by the defining instruction alone. TLI.getRegClassFor() is not consulted.

To clarify how register classes are computed today:

- For a typed edge, the RC is computed as the intersection of TLI.getRegClassFor(type) and the register constraints imposed by all the virtual register's uses and defs.

- For an untyped edge, the RC is the intersection of the def constraint and all the uses' constraints.

Thanks,
/jakob

9

The problem here is that SelectionDAG's type system doesn't always match architectures well.

Sometimes you need more fine grained distinctions than offered by the types, like in your example.

Sometimes you need something coarser than types, like when the PowerPC floating point registers can hold both f32 and f64 types. The fabs and fneg instructions are effectively polymorphic, operating on both f32 and f64 values.

Many modern architectures can perform integer arithmetic in their vector/float registers, but LLVM will always use the integer registers because of the type <-> register class mapping. This causes more cross-class copies than is necessary.

To address these problems, I think we will need to support multiple patterns matching the same primitive typed operation. The output patterns can select different instructions with different operand register classes, and we need to solve a graph coloring problem to minimize the cross-class copies produced.

Thanks,
/jakob

10

How come the Hexagone backend is able to get away with that then?

def IntRegs : RegisterClass<"Hexagon", [i32,f32], 32,

11

They have to use explicit type casts everywhere:

def rr : ALU32_rr<(outs IntRegs:$dst), (ins IntRegs:$b, IntRegs:$c),
!strconcat("$dst = ", !strconcat(OpcStr, “($b, $c)”)),
[(set (i32 IntRegs:$dst), (OpNode (i32 IntRegs:$b),
(i32 IntRegs:$c)))]>;

/jakob