[LLVMdev] Instruction descriptions question

[Chris Lattner]

On Sun, 1 Oct 2006, Roman Levenstein wrote:
> I'm trying to implement a new backend for an embedded CISC processor.
> Therefore I thought that it makes sense to take X86 target as a basis,
> to save some time.

Ok.  Note that the X86 backend is one of the most complex though, because 
it supports several subtargets and ABIs, which makes it more complex than 
some other targets.

> But when I look into the X86InstrInfo.td, I have a very strong feeling
> that it is one of the most complex instruction set descriptions
> compared to other targets.

Yep.

> I can imagine that this is due to the
> complexity of X86's instruction set. But still I have a feeling that it
> is overcomplicated, but may be it is just an initial impression.

Ok.

> Since I just started, here are my first several questions and
> proposals. I hope that some of them make sense for you.

Ok.

> 1. Why does X86 instruction set description provide different
> descriptions for the same instructions, which differ only in the size
> of operands?
> E.g.
>
> def MOV8rm  : I<0x8A, MRMSrcMem, (ops GR8 :$dst, i8mem :$src),
>                "mov{b} {$src, $dst|$dst, $src}",
>                [(set GR8:$dst, (load addr:$src))]>;
> def MOV16rm : I<0x8B, MRMSrcMem, (ops GR16:$dst, i16mem:$src),
>                "mov{w} {$src, $dst|$dst, $src}",
>                [(set GR16:$dst, (load addr:$src))]>, OpSize;
> def MOV32rm : I<0x8B, MRMSrcMem, (ops GR32:$dst, i32mem:$src),
>                "mov{l} {$src, $dst|$dst, $src}",
>                [(set GR32:$dst, (load addr:$src))]>;

We must do this, because they perform different operations.  Specifically, 
the loads all read a different number of bytes (1/2/4).

> For my target processor, only the types of operands (e.g. rm) are
> really important. The size is encoded into the opcode, but otherwise it
> does not affect anything except for constraints on the sizes of
> operands. And constraint is basically that the size of both operands
> should be the same.

Ok.

> Wouldn't it be possible and even more clean to have just one
> description like (I use a pseudo-description here):
>
> def MOVrr  : I<0x88, MRMDestReg, (ops (GR8|GR16|GR32) :$dst,
> (i8mem|i16mem|i32mem):$src),
>                "mov{b} {$src, $dst|$dst, $src}", []>, isSameSize($dst,
> $src);

We already have something like this, but it's a little more general.  The 
X86 backend hasn't been converted to use it.  This is the 'multiclass' 
facility in tblgen:
http://llvm.org/docs/TableGenFundamentals.html#multiclass

Basically this lets you use one definition to implement multiple different 
instructions.  For example, most instructions in the sparc target come in 
"reg,reg" and "reg,imm" forms.  As such, it defines:

multiclass F3_12<string OpcStr, bits<6> Op3Val, SDNode OpNode> {
   def rr  : F3_1<2, Op3Val,
                  (ops IntRegs:$dst, IntRegs:$b, IntRegs:$c),
                  !strconcat(OpcStr, " $b, $c, $dst"),
                  [(set IntRegs:$dst, (OpNode IntRegs:$b, IntRegs:$c))]>;
   def ri  : F3_2<2, Op3Val,
                  (ops IntRegs:$dst, IntRegs:$b, i32imm:$c),
                  !strconcat(OpcStr, " $b, $c, $dst"),
                  [(set IntRegs:$dst, (OpNode IntRegs:$b, simm13:$c))]>;
}

which allows it to use instructions like:

defm AND    : F3_12<"and"  , 0b000001, and>;
defm OR     : F3_12<"or"   , 0b000010, or>;
defm XOR    : F3_12<"xor"  , 0b000011, xor>;
defm SLL    : F3_12<"sll"  , 0b100101, shl>;
defm SRL    : F3_12<"srl"  , 0b100110, srl>;
defm SRA    : F3_12<"sra"  , 0b100111, sra>;
defm ADD    : F3_12<"add"  , 0b000000, add>;
defm ADDCC  : F3_12<"addcc", 0b010000, addc>;
defm ADDX   : F3_12<"addx" , 0b001000, adde>;
defm SUB    : F3_12<"sub"  , 0b000100, sub>;
defm SUBX   : F3_12<"subx" , 0b001100, sube>;
defm SUBCC  : F3_12<"subcc", 0b010100, SPcmpicc>;
...

Each of these 'defm's expand into two instructions.

> The semantic of such a description would mean that $dst should be one
> of GR8, GR16, GR32 and $dst is one of i8mem, i16mem, i32mem with the
> additional constraint that the sizes of both operands are the same
> (this is checked by isSameSize predicate).

Sure.  It would be straight-forward to define a multiclass for your arch, 
in which each use of defm makes three instructions: one for each width.

> More over, in very many cases, the operation (e.g. OR) itself affects
> only the encoding of the operation inside the opcode and of course the
> description of the effect and assembler syntax e.g. [(store (or (load
> addr:$dst), GR8:$src), addr:$dst)]. For OR insn the opreation should be
> or, and for AND insn - obviously and. But operands and operand
> combinations have the same limitations and descriptions also for many
> other operations, e.g. XOR, AND, etc.

Yep.

> Wouldn't it make sense to provide an easier way to describe it?
> For example, one would describe operands combinations (e.g. RR, RM)
> separately and then just say which instructions they are applicable
> for? May be using something like:
>
> def rm : (GR32 :$dst, i32mem:$src)
> {
>  "$assm_op{l} {$src, $dst|$dst, $src}",
>  [(set GR32:$dst, ($insn_effect_op GR16:$dst, (load addr:$src)))]
>
> };

Yep.  tblgen gives you lots of tools to factor your instructions.

> 2. Another related question is about instruciton costs. In BURG-based
> selectors there is usually a possibility to describe costs for the
> instructions so that a least-cost cover can be found during the
> instruction selection process. I have not seen any such cost
> descriptions in TableGen files. Does it mean that it is not supported?

LLVM currently uses assumes that all instructions have cost 1, unless told 
otherwise ('Pat' patterns which produce multiple instructions have cost 
equal to the sum of their result).  Given this, it attempts to match the 
largest patterns possible, which reduces cost.

The 'largest' metric is somewhat intricate, but you can directly affect it 
in your .td files with the 'AddedComplexity'.  If you increase it, it will 
make an instruction more likely to be matched.  However, you really 
shouldn't need to do this, except in extreme cases.  Are you seeing cases 
where the selector is missing an optimal match, or are you just used to 
other tools which aren't as smart at inferring cost as tblgen?

> Why? As far as I understand, LLVM uses BURG/IBURG for instruction
> selection and both of these tools support costs, AFAIK.

Nope, it uses neither.  It uses custom code built into tblgen.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/