docs/TableGenFundamentals.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
   2                       "http://www.w3.org/TR/html4/strict.dtd">
   3 <html>
   4 <head>
   5   <title>TableGen Fundamentals</title>
   6   <link rel="stylesheet" href="llvm.css" type="text/css">
   7 </head>
   8 <body>
   9
  10 <div class="doc_title">TableGen Fundamentals</div>
  11
  12 <ul>
  13   <li><a href="#introduction">Introduction</a></li>
  14   <ol>
  15     <li><a href="#concepts">Basic concepts</a></li>
  16     <li><a href="#example">An example record</a></li>
  17     <li><a href="#running">Running TableGen</a></li>
  18   </ol>
  19   <li><a href="#syntax">TableGen syntax</a></li>
  20   <ol>
  21     <li><a href="#primitives">TableGen primitives</a></li>
  22     <ol>
  23       <li><a href="#comments">TableGen comments</a></li>
  24       <li><a href="#types">The TableGen type system</a></li>
  25       <li><a href="#values">TableGen values and expressions</a></li>
  26     </ol>
  27     <li><a href="#classesdefs">Classes and definitions</a></li>
  28     <ol>
  29       <li><a href="#valuedef">Value definitions</a></li>
  30       <li><a href="#recordlet">'let' expressions</a></li>
  31       <li><a href="#templateargs">Class template arguments</a></li>
  32     </ol>
  33     <li><a href="#filescope">File scope entities</a></li>
  34     <ol>
  35       <li><a href="#include">File inclusion</a></li>
  36       <li><a href="#globallet">'let' expressions</a></li>
  37     </ol>
  38   </ol>
  39   <li><a href="#backends">TableGen backends</a></li>
  40   <ol>
  41     <li><a href="#">todo</a></li>
  42   </ol>
  43   <li><a href="#codegenerator">The LLVM code generator</a></li>
  44   <ol>
  45     <li><a href="#">todo</a></li>
  46   </ol>
  47 </ul>
  48
  49 <!-- *********************************************************************** -->
  50 <div class="doc_section"><a name="introduction">Introduction</a></div>
  51 <!-- *********************************************************************** -->
  52
  53 <div class="doc_text">
  54
  55 <p>TableGen's purpose is to help a human develop and maintain records of
  56 domain-specific information.  Because there may be a large number of these
  57 records, it is specifically designed to allow writing flexible descriptions and
  58 for common features of these records to be factored out.  This reduces the
  59 amount of duplication in the description, reduces the chance of error, and
  60 makes it easier to structure domain specific information.</p>
  61
  62 <p>The core part of TableGen <a href="#syntax">parses a file</a>, instantiates
  63 the declarations, and hands the result off to a domain-specific "<a
  64 href="#backends">TableGen backend</a>" for processing.  The current major user
  65 of TableGen is the <a href="#codegenerator">LLVM code generator</a>.
  66 </p>
  67
  68 <p>
  69 Note that if you work on TableGen much, and use emacs or vim, that you can find
  70 an emacs "TableGen mode" and a vim language file in <tt>llvm/utils/emacs</tt>
  71 and <tt>llvm/utils/vim</tt> directory of your LLVM distribution, respectively.
  72 </p>
  73
  74 </div>
  75
  76 <!-- ======================================================================= -->
  77 <div class="doc_subsection">
  78   <a name="running">Basic concepts</a>
  79 </div>
  80
  81 <div class="doc_text">
  82
  83 <p>
  84 TableGen files consist of two key parts: 'classes' and 'definitions', both of
  85 which are considered 'records'.
  86 </p>
  87
  88 <p>
  89 <b>TableGen records</b> have a unique name, a list of values, and a list of
  90 superclasses.  The list of values is main data that TableGen builds for each
  91 record, it is this that holds the domain specific information for the
  92 application.  The interpretation of this data is left to a specific <a
  93 href="#backends">TableGen backend</a>, but the structure and format rules are
  94 taken care of and fixed by TableGen.
  95 </p>
  96
  97 <p>
  98 <b>TableGen definitions</b> are the concrete form of 'records'.  These generally
  99 do not have any undefined values, and are marked with the '<tt>def</tt>'
 100 keyword.
 101 </p>
 102
 103 <p>
 104 <b>TableGen classes</b> are abstract records that are used to build and describe
 105 other records.  These 'classes' allow the end-user to build abstractions for
 106 either the domain they are targetting (such as "Register", "RegisterClass", and
 107 "Instruction" in the LLVM code generator) or for the implementor to help factor
 108 out common properties of records (such as "FPInst", which is used to represent
 109 floating point instructions in the X86 backend).  TableGen keeps track of all of
 110 the classes that are used to build up a definition, so the backend can find all
 111 definitions of a particular class, such as "Instruction".
 112 </p>
 113
 114 </div>
 115
 116 <!-- ======================================================================= -->
 117 <div class="doc_subsection">
 118   <a name="example">An example record</a>
 119 </div>
 120
 121 <div class="doc_text">
 122
 123 <p>
 124 With no other arguments, TableGen parses the specified file and prints out all
 125 of the classes, then all of the definitions.  This is a good way to see what the
 126 various definitions expand to fully.  Running this on the <tt>X86.td</tt> file
 127 prints this (at the time of this writing):
 128 </p>
 129
 130 <p>
 131 <pre>
 132 ...
 133 <b>def</b> ADDrr8 {    <i>// Instruction X86Inst I2A8 Pattern</i>
 134   <b>string</b> Name = "add";
 135   <b>string</b> Namespace = "X86";
 136   <b>list</b>&lt;Register&gt; Uses = [];
 137   <b>list</b>&lt;Register&gt; Defs = [];
 138   <b>bit</b> isReturn = 0;
 139   <b>bit</b> isBranch = 0;
 140   <b>bit</b> isCall = 0;
 141   <b>bit</b> isTwoAddress = 1;
 142   <b>bit</b> isTerminator = 0;
 143   <b>dag</b> Pattern = (set R8, (plus R8, R8));
 144   <b>bits</b>&lt;8&gt; Opcode = { 0, 0, 0, 0, 0, 0, 0, 0 };
 145   Format Form = MRMDestReg;
 146   <b>bits</b>&lt;5&gt; FormBits = { 0, 0, 0, 1, 1 };
 147   ArgType Type = Arg8;
 148   <b>bits</b>&lt;3&gt; TypeBits = { 0, 0, 1 };
 149   <b>bit</b> hasOpSizePrefix = 0;
 150   <b>bit</b> printImplicitUses = 0;
 151   <b>bits</b>&lt;4&gt; Prefix = { 0, 0, 0, 0 };
 152   FPFormat FPForm = ?;
 153   <b>bits</b>&lt;3&gt; FPFormBits = { 0, 0, 0 };
 154 }
 155 ...
 156 </pre><p>
 157
 158 <p>
 159 This definition corresponds to an 8-bit register-register add instruction in the
 160 X86.  The string after the '<tt>def</tt>' string indicates the name of the
 161 record ("<tt>ADDrr8</tt>" in this case), and the comment at the end of the line
 162 indicates the superclasses of the definition.  The body of the record contains
 163 all of the data that TableGen assembled for the record, indicating that the
 164 instruction is part of the "X86" namespace, should be printed as "<tt>add</tt>"
 165 in the assembly file, it is a two-address instruction, has a particular
 166 encoding, etc.  The contents and semantics of the information in the record is
 167 specific to the needs of the X86 backend, and is only shown as an example.
 168 </p>
 169
 170 <p>
 171 As you can see, a lot of information is needed for every instruction supported
 172 by the code generator, and specifying it all manually would be unmaintainble,
 173 prone to bugs, and tiring to do in the first place.  Because we are using
 174 TableGen, all of the information was derived from the following definition:
 175 </p>
 176
 177 <p><pre>
 178 <b>def</b> ADDrr8   : I2A8&lt;"add", 0x00, MRMDestReg&gt;,
 179                Pattern&lt;(set R8, (plus R8, R8))&gt;;
 180 </pre></p>
 181
 182 <p>
 183 This definition makes use of the custom I2A8 (two address instruction with 8-bit
 184 operand) class, which is defined in the X86-specific TableGen file to factor out
 185 the common features that instructions of its class share.  A key feature of
 186 TableGen is that it allows the end-user to define the abstractions they prefer
 187 to use when describing their information.
 188 </p>
 189
 190 </div>
 191
 192 <!-- ======================================================================= -->
 193 <div class="doc_subsection">
 194   <a name="running">Running TableGen</a>
 195 </div>
 196
 197 <div class="doc_text">
 198
 199 <p>
 200 TableGen runs just like any other LLVM tool.  The first (optional) argument
 201 specifies the file to read.  If a filename is not specified, <tt>tblgen</tt>
 202 reads from standard input.
 203 </p>
 204
 205 <p>
 206 To be useful, one of the <a href="#backends">TableGen backends</a> must be used.
 207 These backends are selectable on the command line (type '<tt>tblgen --help</tt>'
 208 for a list).  For example, to get a list of all of the definitions that subclass
 209 a particular type (which can be useful for building up an enum list of these
 210 records), use the <tt>--print-enums</tt> option:
 211 </p>
 212
 213 <p><pre>
 214 $ tblgen X86.td -print-enums -class=Register
 215 AH, AL, AX, BH, BL, BP, BX, CH, CL, CX, DH, DI, DL, DX,
 216 EAX, EBP, EBX, ECX, EDI, EDX, ESI, ESP, FP0, FP1, FP2, FP3, FP4, FP5, FP6,
 217 SI, SP, ST0, ST1, ST2, ST3, ST4, ST5, ST6, ST7,
 218
 219 $ tblgen X86.td -print-enums -class=Instruction
 220 ADCrr32, ADDri16, ADDri16b, ADDri32, ADDri32b, ADDri8, ADDrr16, ADDrr32,
 221 ADDrr8, ADJCALLSTACKDOWN, ADJCALLSTACKUP, ANDri16, ANDri16b, ANDri32, ANDri32b,
 222 ANDri8, ANDrr16, ANDrr32, ANDrr8, BSWAPr32, CALLm32, CALLpcrel32, ...
 223 </pre></p>
 224
 225 <p>
 226 The default backend prints out all of the records, as described <a
 227 href="#example">above</a>.
 228 </p>
 229
 230 <p>
 231 If you plan to use TableGen for some purpose, you will most likely have to <a
 232 href="#backends">write a backend</a> that extracts the information specific to
 233 what you need and formats it in the appropriate way.
 234 </p>
 235
 236 </div>
 237
 238
 239 <!-- *********************************************************************** -->
 240 <div class="doc_section"><a name="syntax">TableGen syntax</a></div>
 241 <!-- *********************************************************************** -->
 242
 243 <div class="doc_text">
 244
 245 <p>
 246 TableGen doesn't care about the meaning of data (that is up to the backend to
 247 define), but it does care about syntax, and it enforces a simple type system.
 248 This section describes the syntax and the constructs allowed in a TableGen file.
 249 </p>
 250
 251 </div>
 252
 253 <!-- ======================================================================= -->
 254 <div class="doc_subsection">
 255   <a name="primitives">TableGen primitives</tt></a>
 256 </div>
 257
 258 <!----------------------------------------------------------------------------->
 259 <div class="doc_subsubsection">
 260   <a name="comments">TableGen comments</tt></a>
 261 </div>
 262
 263 <div class="doc_text">
 264
 265 <p>TableGen supports BCPL style "<tt>//</tt>" comments, which run to the end of
 266 the line, and it also supports <b>nestable</b> "<tt>/* */</tt>" comments.</p>
 267
 268 </div>
 269
 270
 271 <!----------------------------------------------------------------------------->
 272 <div class="doc_subsubsection">
 273   <a name="types">The TableGen type system</tt></a>
 274 </div>
 275
 276 <div class="doc_text">
 277 <p>
 278 TableGen files are strongly typed, in a simple (but complete) type-system.
 279 These types are used to perform automatic conversions, check for errors, and to
 280 help interface designers constrain the input that they allow.  Every <a
 281 href="#valuedef">value definition</a> is required to have an associated type.
 282 </p>
 283
 284 <p>
 285 TableGen supports a mixture of very low-level types (such as <tt>bit</tt>) and
 286 very high-level types (such as <tt>dag</tt>).  This flexibility is what allows
 287 it to describe a wide range of information conveniently and compactly.  The
 288 TableGen types are:
 289 </p>
 290
 291 <p>
 292 <ul>
 293 <li>"<tt><b>bit</b></tt>" - A 'bit' is a boolean value that can hold either 0 or
 294 1.</li>
 295
 296 <li>"<tt><b>int</b></tt>" - The 'int' type represents a simple 32-bit integer
 297 value, such as 5.</li>
 298
 299 <li>"<tt><b>string</b></tt>" - The 'string' type represents an ordered sequence
 300 of characters of arbitrary length.</li>
 301
 302 <li>"<tt><b>bits</b>&lt;n&gt;</tt>" - A 'bits' type is a arbitrary, but fixed,
 303 size integer that is broken up into individual bits.  This type is useful
 304 because it can handle some bits being defined while others are undefined.</li>
 305
 306 <li>"<tt><b>list</b>&lt;ty&gt;</tt>" - This type represents a list whose
 307 elements are some other type.  The contained type is arbitrary: it can even be
 308 another list type.</li>
 309
 310 <li>Class type - Specifying a class name in a type context means that the
 311 defined value must be a subclass of the specified class.  This is useful in
 312 conjunction with the "list" type, for example, to constrain the elements of the
 313 list to a common base class (e.g., a <tt><b>list</b>&lt;Register&gt;</tt> can
 314 only contain definitions derived from the "<tt>Register</tt>" class).</li>
 315
 316 <li>"<tt><b>code</b></tt>" - This represents a big hunk of text.  NOTE: I don't
 317 remember why this is distinct from string!</li>
 318
 319 <li>"<tt><b>dag</b></tt>" - This type represents a nestable directed graph of
 320 elements.</li>
 321 </ul>
 322 </p>
 323
 324 <p>
 325 To date, these types have been sufficient for describing things that TableGen
 326 has been used for, but it is straight-forward to extend this list if needed.
 327 </p>
 328
 329 </div>
 330
 331 <!----------------------------------------------------------------------------->
 332 <div class="doc_subsubsection">
 333   <a name="values">TableGen values and expressions</tt></a>
 334 </div>
 335
 336 <div>
 337 <p>
 338 TableGen allows for a pretty reasonable number of different expression forms
 339 when building up values.  These forms allow the TableGen file to be written in a
 340 natural syntax and flavor for the application.  The current expression forms
 341 supported include:
 342 </p>
 343
 344 <p><ul>
 345 <li>? - Uninitialized field.</li>
 346 <li>0b1001011 - Binary integer value.</li>
 347 <li>07654321 - Octal integer value (indicated by a leading 0).</li>
 348 <li>7 - Decimal integer value.</li>
 349 <li>0x7F - Hexadecimal integer value.</li>
 350 <li>"foo" - String value.</li>
 351 <li>[{ .... }] - Code fragment.</li>
 352 <li>[ X, Y, Z ] - List value.</li>
 353 <li>{ a, b, c } - Initializer for a "bits&lt;3&gt;" value.</li>
 354 <li>value - Value reference.</li>
 355 <li>value{17} - Access to one or more bits of a value.</li>
 356 <li>DEF - Reference to a record definition.</li>
 357 <li>X.Y - Reference to the subfield of a value.</li>
 358
 359 <li>(DEF a, b) - A dag value.  The first element is required to be a record
 360 definition, the remaining elements in the list may be arbitrary other values,
 361 including nested 'dag' values.</li>
 362
 363 </ul></p>
 364
 365 <p>
 366 Note that all of the values have rules specifying how they convert to to values
 367 for different types.  These rules allow you to assign a value like "7" to a
 368 "bits&lt;4&gt;" value, for example.
 369 </p>
 370
 371
 372
 373 </div>
 374
 375
 376 <!-- ======================================================================= -->
 377 <div class="doc_subsection">
 378   <a name="classesdefs">Classes and definitions</tt></a>
 379 </div>
 380
 381 <div>
 382 <p>
 383 As mentioned in the <a href="#concepts">intro</a>, classes and definitions
 384 (collectively known as 'records') in TableGen are the main high-level unit of
 385 information that TableGen collects.  Records are defined with a <tt>def</tt> or
 386 <tt>class</tt> keyword, the record name, and an optional list of "<a
 387 href="templateargs">template arguments</a>".  If the record has superclasses,
 388 they are specified as a comma seperated list that starts with a colon character
 389 (":").  If <a href="#valuedef">value definitions</a> or <a href="#recordlet">let
 390 expressions</a> are needed for the class they are enclosed in curly braces
 391 ("{}"), otherwise the record ends with a semicolon.  Here is a simple TableGen
 392 file:
 393 </p>
 394
 395 <p><pre>
 396 <b>class</b> C { <b>bit</b> V = 1; }
 397 <b>def</b> X : C;
 398 <b>def</b> Y : C {
 399   <b>string</b> Greeting = "hello";
 400 }
 401 </pre></p>
 402
 403 <p>
 404 This example defines two definitions, <tt>X</tt> and <tt>Y</tt>, both of which
 405 derive from the <tt>C</tt> class.  Because of this, they both get the <tt>V</tt>
 406 bit value.  The <tt>Y</tt> definition also gets the Greeting member as well.
 407 </p>
 408
 409 </div>
 410
 411 <!----------------------------------------------------------------------------->
 412 <div class="doc_subsubsection">
 413   <a name="valuedef">Value definitions</tt></a>
 414 </div>
 415
 416 <div class="doc_text">
 417 <p>
 418 Value definitions define named entries in records.  A value must be defined
 419 before it can be referred to as the operand for another value definition, or
 420 before the value is reset with a <a href="#recordlet">let expression</a>.  A
 421 value is defined by specifying a <a href="#types">TableGen type</a> and a name.
 422 If an initial value is available, it may be specified after the type with an
 423 equal sign.  Value definitions require terminating semicolons.
 424 </div>
 425
 426 <!----------------------------------------------------------------------------->
 427 <div class="doc_subsubsection">
 428   <a name="recordlet">'let' expressions</tt></a>
 429 </div>
 430
 431 <div class="doc_text">
 432 <p>
 433 A record-level let expression is used to change the value of a value definition
 434 in a record.  This is primarily useful when a superclass defines a value that a
 435 derived class or definitions wants to override.  Let expressions consist of the
 436 '<tt>let</tt>' keyword, followed by a value name, an equal sign ("="), and a new
 437 value for example, a new class could be added to the example above, redefining
 438 the <tt>V</tt> field for all of its subclasses:</p>
 439
 440 <p><pre>
 441 <b>class</b> D : C { let V = 0; }
 442 <b>def</b> Z : D;
 443 </pre></p>
 444
 445 <p>
 446 In this case, the <tt>Z</tt> definition will have a zero value for its "V"
 447 value, despite the fact that it derives (indirectly) from the <tt>C</tt> class,
 448 because the <tt>D</tt> class overrode its value.
 449 </p>
 450
 451 </div>
 452
 453 <!----------------------------------------------------------------------------->
 454 <div class="doc_subsubsection">
 455   <a name="templateargs">Class template arguments</tt></a>
 456 </div>
 457
 458 <div class="doc_text">
 459 and default values...
 460 </div>
 461
 462
 463
 464 <!-- ======================================================================= -->
 465 <div class="doc_subsection">
 466   <a name="filescope">File scope entities</tt></a>
 467 </div>
 468
 469 <!----------------------------------------------------------------------------->
 470 <div class="doc_subsubsection">
 471   <a name="include">File inclusion</tt></a>
 472 </div>
 473
 474 <div class="doc_text">
 475 <p>
 476 TableGen supports the '<tt>include</tt>' token, which textually substitutes the
 477 specified file in place of the include directive.  The filename should be
 478 specified as a double quoted string immediately after the '<tt>include</tt>'
 479 keyword.  Example:
 480
 481 <p><pre>
 482   <b>include</b> "foo.td"
 483 </pre></p>
 484
 485 </div>
 486
 487 <!----------------------------------------------------------------------------->
 488 <div class="doc_subsubsection">
 489   <a name="globallet">'let' expressions</tt></a>
 490 </div>
 491
 492 <div class="doc_text">
 493 <p>
 494 "let" expressions at file scope are similar to <a href="#recordlet">"let"
 495 expressions within a record</a>, except they can specify a value binding for
 496 multiple records at a time, and may be useful in certain other cases.
 497 File-scope let expressions are really just another way that TableGen allows the
 498 end-user to factor out commonality from the records.
 499 </p>
 500
 501 <p>
 502 File-scope "let" expressions take a comma-seperated list of bindings to apply,
 503 and one of more records to bind the values in.  Here are some examples:
 504 </p>
 505
 506 <p><pre>
 507 <b>let</b> isTerminator = 1, isReturn = 1 <b>in</b>
 508   <b>def</b> RET : X86Inst&lt;"ret", 0xC3, RawFrm, NoArg&gt;;
 509
 510 <b>let</b> isCall = 1 <b>in</b>
 511   <i>// All calls clobber the non-callee saved registers...</i>
 512   <b>let</b> Defs = [EAX, ECX, EDX, FP0, FP1, FP2, FP3, FP4, FP5, FP6] in {
 513     <b>def</b> CALLpcrel32 : X86Inst&lt;"call", 0xE8, RawFrm, NoArg&gt;;
 514     <b>def</b> CALLr32     : X86Inst&lt;"call", 0xFF, MRMS2r, Arg32&gt;;
 515     <b>def</b> CALLm32     : X86Inst&lt;"call", 0xFF, MRMS2m, Arg32&gt;;
 516   }
 517 </pre></p>
 518
 519 <p>
 520 File-scope "let" expressions are often useful when a couple of definitions need
 521 to be added to several records, and the records do not otherwise need to be
 522 opened, as in the case with the CALL* instructions above.
 523 </p>
 524 </div>
 525
 526
 527 <!-- *********************************************************************** -->
 528 <div class="doc_section"><a name="backends">TableGen backends</a></div>
 529 <!-- *********************************************************************** -->
 530
 531 <div class="doc_text">
 532
 533 <p>
 534 How they work, how to write one.  This section should not contain details about
 535 any particular backend, except maybe -print-enums as an example.  This should
 536 highlight the APIs in TableGen/Record.h.
 537 </p>
 538
 539 </div>
 540
 541
 542 <!-- *********************************************************************** -->
 543 <div class="doc_section"><a name="codegenerator">The LLVM code generator</a></div>
 544 <!-- *********************************************************************** -->
 545
 546 <div class="doc_text">
 547
 548 <p>
 549 This is just a temporary, convenient, place to put stuff about the code
 550 generator before it gets its own document.  This should describe all of the
 551 tablegen backends used by the code generator and the classes/definitions they
 552 expect.
 553 </p>
 554
 555 </div>
 556
 557
 558
 559 <!-- *********************************************************************** -->
 560 <hr>
 561 <div class="doc_footer">
 562   <address><a href="mailto:sabre@nondot.org">Chris Lattner</a></address>
 563   <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a>
 564   <br>
 565   Last modified: $Date$
 566 </div>
 567
 568 </body>
 569 </html>