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