llvm dev - Aug 2012 - [LLVMdev] TableGen related question for the Hexagon backend

Hi Everyone,

After some more thoughts to the Jacob's suggestion of using multiclasses for
Opcode mapping, this is what I have come up with. Please take a look at the
design below and let me know if you have any suggestions/questions.

I have tried to keep the design target independent so that other targets
could benefit from it.

1) The idea is to add 3 new classes into  include/llvm/Target/Target.td
which provide the basic
infrastructure for relating instructions with each other. 

Class Relations {}  // any target interested in mapping relations, need to
define a
                    // class of its own as a subclass of 'Relations'.

class IFormat<bits<4> value> {  // Used to define basic instruction
formats,
Ex: register-register, register-immediate
  bits<4> Value = value;
}

// class RelationMap is actually used to related instructions with each
other. 
class RelationMap<IFormat pFormat, IFormat iFormat, list<string>
ancestors [] > {
  IFormat ParentFormat = pFormat;
  IFormat InstrFormat = iFormat;
  list <string> Ancestors = ancestors;
}

2) Include some basic setup in the InstrInfo.td file. Any target interested
in mapping relation needs to
 define a class as a subclass of 'Relations'. This class is primarily
used
for the recordkeeping and has one 
string variable for each basic format  required for  relation modeling. All
instructions that want to define
relationship mapping, should inherit from this class in addition to
RelationMap class. This is explained below
 using a prototype model for Hexagon.

Example from Hexagon backend:

class RelHexagon : Relations {
  string InstFormat0; //prev form
  string InstFormat1; //rr (register register)
  string InstFormat2; //ri (register immediate)
  string InstFormat3; //pred true
  string InstFormat4; //pred false
}

Define Instruction formats which are IFormat objects and have a unique
integer value 
associated with them. It is used to access appropriate field within
RelHexagon Class.

def Format_prev : IFormat<0>;    // previous form
def Format_rr : IFormat<1>;         // register register
def Format_ri : IFormat<2>;         // register immediate
def Format_predt : IFormat<3>; // pred true def Format_predf :
IFormat<4>;
// pred false


4) Prototype relationship model for a simple 'add' instruction with 6
variants:

                                            /---- if (p0) R1 = add(R2, R3) 
                                           /        (Predicate true) 
Add register register - R1 = add(R2, R3) --
                                           \
                                            \---- if (!p0) R1 = add(R2, R3)
                                                  (predicate false)


                                               /---- if (p0) R1 = add(R2,
#12) 
                                              /         (Predicate true) 
Add register immediate - R1 = add(R2, #12) --
                                              \
                                               \---- if (!p0) R1 = add(R2,
#12)
                                                    (predicate false)


multiclass Add_rr < IFormat TransformsFrom> {
  def #NAME# : V2_A2_add, RelationMap < TransformsFrom, Format_rr>;
  defm _pt : V2_A2_padd, RelationMap < Format_rr, Format_predt,
["rr"]>;
  defm _pf : V2_A2_padd, RelationMap < Format_rr, Format_predf,
["rr"] >; }

multiclass Add_ri < IFormat TransformsFrom> {
  def #NAME# : V2_A2_addi, RelationMap < TransformsFrom, Format_ri >;
  defm _pt : V2_A2_paddi, RelationMap < Format_ri, Format_predt,
["ri"] >;
  defm _pf :  V2_A2_paddi, RelationMap < Format_ri, Format_predf,
["ri"] >;
}

multiclass Add_base {
  defm rr : Add_rr < Format_rr>;
  defm ri : Add_ri < Format_rr>;
}

defm ADD : Add_base, RelHexagon; <- defm needs to inherit from RelHexagon
Class here


5) We need some changes in the TGParser.cpp so that it can use the
information specified 
through the RelationMap and populate relevant fields in the RelHexagon
class. 
This eventually becomes part of  the instruction definition (record).

bool TGParser::ParseDefm(MultiClass *CurMultiClass) { ...

  if (InheritFromClass) {
    // Process all the classes to inherit as if they were part of a
    // regular 'def' and inherit all record values.
    SubClassReference SubClass = ParseSubClassReference(0, false);
    while (1) {
      // Check for error.
      if (SubClass.Rec == 0) return true;

      // Get the expanded definition prototypes and teach them about
      // the record values the current class to inherit has
      for (unsigned i = 0, e = NewRecDefs.size(); i != e; ++i) {
        Record *CurRec = NewRecDefs[i];
**** proposed changes -begin *****
        if (SubClass.Rec->isSubClassOf("Relations")) {
          std::vector<Init*>
InstrFormats(SubClass.Rec->getValues().size());
         1) Traverse thru all the records to see if CurRec's InstrFormat is
same as the ParentFormat for any of the 
          records and they both share same ancestors. If so, insert that
record at the  appropriate place in the 
         vector using the integer value of the InstrFormat of the children
instructions.
         2) Use Vector to populate fields of the SubClass.Rec (RelHexagon in
our case) Class.
        }
**** proposed changes -end *****
     // All the fields from a subclass are eventually added into the
instruction record -- existing functionality

6) Add a new command line option into TableGen that will emit this
information as a table in a .inc file.

7) Target is required to add its own API to read the table and extract
relevant information.

Thanks,
Jyotsna

--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum.

-----Original Message-----
From: Jakob Stoklund Olesen [mailto:stoklund at 2pi.dk] 
Sent: Thursday, August 02, 2012 5:24 PM
To: Jyotsna Verma
Cc: 'Tony Linthicum'; llvmdev at cs.uiuc.edu
Subject: Re: TableGen related question for the Hexagon backend


On Aug 1, 2012, at 1:53 PM, Jyotsna Verma <jverma at codeaurora.org>
wrote:
> 
> Currently, we rely on switch tables to transform between formats. 
> However, we would like to have a different mechanism to represent 
> these relationships instead of switch tables. I am thinking of 
> modeling these relations in HexagonInstrInfo.td file and use TableGen 
> to generate a table with the information.
That would be a good idea. X86 could also use some help with opcode mapping
tables.
> Idea is to have a new class, say Relations, with some members of type 
> 'Instruction' each representing a specific relation between itself
and
> 'ThisInstr'.
> 
> For example:
> class Relations {
>                Instruction ThisInstr;
>                Instruction BaseForm;
>                Instruction TruePred;
>                Instruction FalsePred;
> }
> 
> def Rel_ADDrr : Relations<ADDrr, ADDrr, ADDrr_p, ADDrr_np>; def 
> Rel_ADDrr_p: Relations<ADDrr_p, ADDrr, , >; def Rel_ADDrr_np : 
> Relations<ADDrr_np,ADDrr, , >;
The problem is, this isn't really any better than having a large switch
statement. You just moved the table into the .td file.

You should be taking advantage of the instruction multiclasses so you don't
have to maintain a full table of opcodes.

/jakob

On Aug 16, 2012, at 1:39 PM, Jyotsna Verma <jverma at codeaurora.org>
wrote:
> Hi Everyone,
> 
> After some more thoughts to the Jacob's suggestion of using
multiclasses for
> Opcode mapping, this is what I have come up with. Please take a look at the
> design below and let me know if you have any suggestions/questions.
Hi Jyotsna,

You are on to something here, but you don't need to define a
'Relations' class on top of the tablegen records. They are already
relations, you just need the proper query language to match the instructions you
want.

You simply use the existing fields in your instructions, or add new ones as
needed. You don't want to be limited to a single 'IFormat' as a
column identifier, there can be many different types of relationships  between
instructions.

Do something like this:

def getPredicatedOpcode : InstrMapping {

  // Only include instructions form the PredRel class.
  let FilterClass = "PredRel";

  // Instructions with the same BaseOpcode field form a row.
  let RowFields = ["BaseOpcode"];

  // Instructions with the same predicate sense form a column.
  let ColFields = ["PredSense"];

  // The key column is the unpredicated instructions.
  let KeyCol = ["nopred"];

  // Value columns are predicate=true and predicate=false
  let ValueCols = [["true"], ["false"]];
};

That should be enough to generate a table:

 // key , PredSense=true, PredSense=false
 {  ADD , ADDtrue,        ADDfalse,       // BaseOpcode="ADD"
 {  SUB , SUBtrue,        SUBfalse,       // BaseOpcode="SUB"
…
> 5) We need some changes in the TGParser.cpp so that it can use the
> information specified 
> through the RelationMap and populate relevant fields in the RelHexagon
> class. 
The tablegen parser is definitely not the right place to implement this.

/jakob

Hi Jacob,

Thanks for the suggestions. I have a few questions here.
> You are on to something here, but you don't need to define a
'Relations'
class
> on top of the tablegen records. They are already relations, you just need
the
> proper query language to match the instructions you want.
Are you saying that the mechanism is already present which allows us to
relate instructions with each other? What do you mean by a proper query
language?
> You don't want to be limited to a single 'IFormat' as a column
> identifier, there can be many different types of relationships  between
> instructions.
We do have different type of relationships between instructions. I define
multiple IFormat objects one per relationship which finally translates into
a unique column into the mapping table.

def Format_rr : IFormat<1>;
def Format_ri : IFormat<2>;
def Format_predt : IFormat<3>;
def Format_predf : IFormat<4>;

Addrr : { Addrr, Addri, Addrr_pt, Addrr_pf, .. , ..}
Addri : { Addrr, Addri, Addri_pt, Addri_pf,..
> Do something like this:
> 
> def getPredicatedOpcode : InstrMapping {
>   // Only include instructions form the PredRel class.
>   let FilterClass = "PredRel";
> 
>   // Instructions with the same BaseOpcode field form a row.
>   let RowFields = ["BaseOpcode"];
> 
>   // Instructions with the same predicate sense form a column.
>   let ColFields = ["PredSense"];
> 
>   // The key column is the unpredicated instructions.
>   let KeyCol = ["nopred"];
> 
>   // Value columns are predicate=true and predicate=false
>   let ValueCols = [["true"], ["false"]]; };
Can you please elaborate it more? It seems interesting but I coundn't
understand it completely. 
Also, how do I get the table from the definition above? For the table, I
need to know the name of the predicated-true and false instructions.
> That should be enough to generate a table:
> 
>  // key , PredSense=true, PredSense=false
>  {  ADD , ADDtrue,        ADDfalse,       // BaseOpcode="ADD"
>  {  SUB , SUBtrue,        SUBfalse,       // BaseOpcode="SUB"
> 
> > 5) We need some changes in the TGParser.cpp so that it can use the
> > information specified through the RelationMap and populate relevant
> > fields in the RelHexagon class.
> 
> The tablegen parser is definitely not the right place to implement this.
I didn't want to modify the tablegen parser either. But, I couldn't
think of
a way around it. Once instructions are expended by the TableGen parser,
there is no way to relate them. Since I wanted to encode this formation
within the instruction itself while they are being expanded, parser appeared
to be the only place to do it. 

Thanks,
Jyotsna