docs/ExtendingLLVM.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   <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
   6   <title>Extending LLVM: Adding instructions, intrinsics, types, etc.</title>
   7   <link rel="stylesheet" href="_static/llvm.css" type="text/css">
   8 </head>
   9
  10 <body>
  11
  12 <h1>
  13   Extending LLVM: Adding instructions, intrinsics, types, etc.
  14 </h1>
  15
  16 <ol>
  17   <li><a href="#introduction">Introduction and Warning</a></li>
  18   <li><a href="#intrinsic">Adding a new intrinsic function</a></li>
  19   <li><a href="#instruction">Adding a new instruction</a></li>
  20   <li><a href="#sdnode">Adding a new SelectionDAG node</a></li>
  21   <li><a href="#type">Adding a new type</a>
  22   <ol>
  23     <li><a href="#fund_type">Adding a new fundamental type</a></li>
  24     <li><a href="#derived_type">Adding a new derived type</a></li>
  25   </ol></li>
  26 </ol>
  27
  28 <div class="doc_author">
  29   <p>Written by <a href="http://misha.brukman.net">Misha Brukman</a>,
  30   Brad Jones, Nate Begeman,
  31   and <a href="http://nondot.org/sabre">Chris Lattner</a></p>
  32 </div>
  33
  34 <!-- *********************************************************************** -->
  35 <h2>
  36   <a name="introduction">Introduction and Warning</a>
  37 </h2>
  38 <!-- *********************************************************************** -->
  39
  40 <div>
  41
  42 <p>During the course of using LLVM, you may wish to customize it for your
  43 research project or for experimentation. At this point, you may realize that
  44 you need to add something to LLVM, whether it be a new fundamental type, a new
  45 intrinsic function, or a whole new instruction.</p>
  46
  47 <p>When you come to this realization, stop and think. Do you really need to
  48 extend LLVM? Is it a new fundamental capability that LLVM does not support at
  49 its current incarnation or can it be synthesized from already pre-existing LLVM
  50 elements? If you are not sure, ask on the <a
  51 href="http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev">LLVM-dev</a> list. The
  52 reason is that extending LLVM will get involved as you need to update all the
  53 different passes that you intend to use with your extension, and there are
  54 <em>many</em> LLVM analyses and transformations, so it may be quite a bit of
  55 work.</p>
  56
  57 <p>Adding an <a href="#intrinsic">intrinsic function</a> is far easier than
  58 adding an instruction, and is transparent to optimization passes.  If your added
  59 functionality can be expressed as a
  60 function call, an intrinsic function is the method of choice for LLVM
  61 extension.</p>
  62
  63 <p>Before you invest a significant amount of effort into a non-trivial
  64 extension, <span class="doc_warning">ask on the list</span> if what you are
  65 looking to do can be done with already-existing infrastructure, or if maybe
  66 someone else is already working on it. You will save yourself a lot of time and
  67 effort by doing so.</p>
  68
  69 </div>
  70
  71 <!-- *********************************************************************** -->
  72 <h2>
  73   <a name="intrinsic">Adding a new intrinsic function</a>
  74 </h2>
  75 <!-- *********************************************************************** -->
  76
  77 <div>
  78
  79 <p>Adding a new intrinsic function to LLVM is much easier than adding a new
  80 instruction.  Almost all extensions to LLVM should start as an intrinsic
  81 function and then be turned into an instruction if warranted.</p>
  82
  83 <ol>
  84 <li><tt>llvm/docs/LangRef.html</tt>:
  85     Document the intrinsic.  Decide whether it is code generator specific and
  86     what the restrictions are.  Talk to other people about it so that you are
  87     sure it's a good idea.</li>
  88
  89 <li><tt>llvm/include/llvm/Intrinsics*.td</tt>:
  90     Add an entry for your intrinsic.  Describe its memory access characteristics
  91     for optimization (this controls whether it will be DCE'd, CSE'd, etc). Note
  92     that any intrinsic using the <tt>llvm_int_ty</tt> type for an argument will
  93     be deemed by <tt>tblgen</tt> as overloaded and the corresponding suffix
  94     will be required on the intrinsic's name.</li>
  95
  96 <li><tt>llvm/lib/Analysis/ConstantFolding.cpp</tt>: If it is possible to
  97     constant fold your intrinsic, add support to it in the
  98     <tt>canConstantFoldCallTo</tt> and <tt>ConstantFoldCall</tt> functions.</li>
  99
 100 <li><tt>llvm/test/Regression/*</tt>: Add test cases for your test cases to the
 101     test suite</li>
 102 </ol>
 103
 104 <p>Once the intrinsic has been added to the system, you must add code generator
 105 support for it.  Generally you must do the following steps:</p>
 106
 107 <dl>
 108
 109 <dt>Add support to the .td file for the target(s) of your choice in
 110    <tt>lib/Target/*/*.td</tt>.</dt>
 111
 112 <dd>This is usually a matter of adding a pattern to the .td file that matches
 113     the intrinsic, though it may obviously require adding the instructions you
 114     want to generate as well.  There are lots of examples in the PowerPC and X86
 115     backend to follow.</dd>
 116 </dl>
 117
 118 </div>
 119
 120 <!-- *********************************************************************** -->
 121 <h2>
 122   <a name="sdnode">Adding a new SelectionDAG node</a>
 123 </h2>
 124 <!-- *********************************************************************** -->
 125
 126 <div>
 127
 128 <p>As with intrinsics, adding a new SelectionDAG node to LLVM is much easier
 129 than adding a new instruction.  New nodes are often added to help represent
 130 instructions common to many targets.  These nodes often map to an LLVM
 131 instruction (add, sub) or intrinsic (byteswap, population count).  In other
 132 cases, new nodes have been added to allow many targets to perform a common task
 133 (converting between floating point and integer representation) or capture more
 134 complicated behavior in a single node (rotate).</p>
 135
 136 <ol>
 137 <li><tt>include/llvm/CodeGen/ISDOpcodes.h</tt>:
 138     Add an enum value for the new SelectionDAG node.</li>
 139 <li><tt>lib/CodeGen/SelectionDAG/SelectionDAG.cpp</tt>:
 140     Add code to print the node to <tt>getOperationName</tt>.  If your new node
 141     can be evaluated at compile time when given constant arguments (such as an
 142     add of a constant with another constant), find the <tt>getNode</tt> method
 143     that takes the appropriate number of arguments, and add a case for your node
 144     to the switch statement that performs constant folding for nodes that take
 145     the same number of arguments as your new node.</li>
 146 <li><tt>lib/CodeGen/SelectionDAG/LegalizeDAG.cpp</tt>:
 147     Add code to <a href="CodeGenerator.html#selectiondag_legalize">legalize,
 148     promote, and expand</a> the node as necessary.  At a minimum, you will need
 149     to add a case statement for your node in <tt>LegalizeOp</tt> which calls
 150     LegalizeOp on the node's operands, and returns a new node if any of the
 151     operands changed as a result of being legalized.  It is likely that not all
 152     targets supported by the SelectionDAG framework will natively support the
 153     new node.  In this case, you must also add code in your node's case
 154     statement in <tt>LegalizeOp</tt> to Expand your node into simpler, legal
 155     operations.  The case for <tt>ISD::UREM</tt> for expanding a remainder into
 156     a divide, multiply, and a subtract is a good example.</li>
 157 <li><tt>lib/CodeGen/SelectionDAG/LegalizeDAG.cpp</tt>:
 158     If targets may support the new node being added only at certain sizes, you
 159     will also need to add code to your node's case statement in
 160     <tt>LegalizeOp</tt> to Promote your node's operands to a larger size, and
 161     perform the correct operation.  You will also need to add code to
 162     <tt>PromoteOp</tt> to do this as well.  For a good example, see
 163     <tt>ISD::BSWAP</tt>,
 164     which promotes its operand to a wider size, performs the byteswap, and then
 165     shifts the correct bytes right to emulate the narrower byteswap in the
 166     wider type.</li>
 167 <li><tt>lib/CodeGen/SelectionDAG/LegalizeDAG.cpp</tt>:
 168     Add a case for your node in <tt>ExpandOp</tt> to teach the legalizer how to
 169     perform the action represented by the new node on a value that has been
 170     split into high and low halves.  This case will be used to support your
 171     node with a 64 bit operand on a 32 bit target.</li>
 172 <li><tt>lib/CodeGen/SelectionDAG/DAGCombiner.cpp</tt>:
 173     If your node can be combined with itself, or other existing nodes in a
 174     peephole-like fashion, add a visit function for it, and call that function
 175     from <tt></tt>.  There are several good examples for simple combines you
 176     can do; <tt>visitFABS</tt> and <tt>visitSRL</tt> are good starting places.
 177     </li>
 178 <li><tt>lib/Target/PowerPC/PPCISelLowering.cpp</tt>:
 179     Each target has an implementation of the <tt>TargetLowering</tt> class,
 180     usually in its own file (although some targets include it in the same
 181     file as the DAGToDAGISel).  The default behavior for a target is to
 182     assume that your new node is legal for all types that are legal for
 183     that target.  If this target does not natively support your node, then
 184     tell the target to either Promote it (if it is supported at a larger
 185     type) or Expand it.  This will cause the code you wrote in
 186     <tt>LegalizeOp</tt> above to decompose your new node into other legal
 187     nodes for this target.</li>
 188 <li><tt>lib/Target/TargetSelectionDAG.td</tt>:
 189     Most current targets supported by LLVM generate code using the DAGToDAG
 190     method, where SelectionDAG nodes are pattern matched to target-specific
 191     nodes, which represent individual instructions.  In order for the targets
 192     to match an instruction to your new node, you must add a def for that node
 193     to the list in this file, with the appropriate type constraints. Look at
 194     <tt>add</tt>, <tt>bswap</tt>, and <tt>fadd</tt> for examples.</li>
 195 <li><tt>lib/Target/PowerPC/PPCInstrInfo.td</tt>:
 196     Each target has a tablegen file that describes the target's instruction
 197     set.  For targets that use the DAGToDAG instruction selection framework,
 198     add a pattern for your new node that uses one or more target nodes.
 199     Documentation for this is a bit sparse right now, but there are several
 200     decent examples.  See the patterns for <tt>rotl</tt> in
 201     <tt>PPCInstrInfo.td</tt>.</li>
 202 <li>TODO: document complex patterns.</li>
 203 <li><tt>llvm/test/Regression/CodeGen/*</tt>: Add test cases for your new node
 204     to the test suite.  <tt>llvm/test/Regression/CodeGen/X86/bswap.ll</tt> is
 205     a good example.</li>
 206 </ol>
 207
 208 </div>
 209
 210 <!-- *********************************************************************** -->
 211 <h2>
 212   <a name="instruction">Adding a new instruction</a>
 213 </h2>
 214 <!-- *********************************************************************** -->
 215
 216 <div>
 217
 218 <p><span class="doc_warning">WARNING: adding instructions changes the bitcode
 219 format, and it will take some effort to maintain compatibility with
 220 the previous version.</span> Only add an instruction if it is absolutely
 221 necessary.</p>
 222
 223 <ol>
 224
 225 <li><tt>llvm/include/llvm/Instruction.def</tt>:
 226     add a number for your instruction and an enum name</li>
 227
 228 <li><tt>llvm/include/llvm/Instructions.h</tt>:
 229     add a definition for the class that will represent your instruction</li>
 230
 231 <li><tt>llvm/include/llvm/Support/InstVisitor.h</tt>:
 232     add a prototype for a visitor to your new instruction type</li>
 233
 234 <li><tt>llvm/lib/AsmParser/Lexer.l</tt>:
 235     add a new token to parse your instruction from assembly text file</li>
 236
 237 <li><tt>llvm/lib/AsmParser/llvmAsmParser.y</tt>:
 238     add the grammar on how your instruction can be read and what it will
 239     construct as a result</li>
 240
 241 <li><tt>llvm/lib/Bitcode/Reader/Reader.cpp</tt>:
 242     add a case for your instruction and how it will be parsed from bitcode</li>
 243
 244 <li><tt>llvm/lib/VMCore/Instruction.cpp</tt>:
 245     add a case for how your instruction will be printed out to assembly</li>
 246
 247 <li><tt>llvm/lib/VMCore/Instructions.cpp</tt>:
 248     implement the class you defined in
 249     <tt>llvm/include/llvm/Instructions.h</tt></li>
 250
 251 <li>Test your instruction</li>
 252
 253 <li><tt>llvm/lib/Target/*</tt>:
 254     Add support for your instruction to code generators, or add a lowering
 255     pass.</li>
 256
 257 <li><tt>llvm/test/Regression/*</tt>: add your test cases to the test suite.</li>
 258
 259 </ol>
 260
 261 <p>Also, you need to implement (or modify) any analyses or passes that you want
 262 to understand this new instruction.</p>
 263
 264 </div>
 265
 266
 267 <!-- *********************************************************************** -->
 268 <h2>
 269   <a name="type">Adding a new type</a>
 270 </h2>
 271 <!-- *********************************************************************** -->
 272
 273 <div>
 274
 275 <p><span class="doc_warning">WARNING: adding new types changes the bitcode
 276 format, and will break compatibility with currently-existing LLVM
 277 installations.</span> Only add new types if it is absolutely necessary.</p>
 278
 279 <!-- ======================================================================= -->
 280 <h3>
 281   <a name="fund_type">Adding a fundamental type</a>
 282 </h3>
 283
 284 <div>
 285
 286 <ol>
 287
 288 <li><tt>llvm/include/llvm/Type.h</tt>:
 289     add enum for the new type; add static <tt>Type*</tt> for this type</li>
 290
 291 <li><tt>llvm/lib/VMCore/Type.cpp</tt>:
 292     add mapping from <tt>TypeID</tt> =&gt; <tt>Type*</tt>;
 293     initialize the static <tt>Type*</tt></li>
 294
 295 <li><tt>llvm/lib/AsmReader/Lexer.l</tt>:
 296     add ability to parse in the type from text assembly</li>
 297
 298 <li><tt>llvm/lib/AsmReader/llvmAsmParser.y</tt>:
 299     add a token for that type</li>
 300
 301 </ol>
 302
 303 </div>
 304
 305 <!-- ======================================================================= -->
 306 <h3>
 307   <a name="derived_type">Adding a derived type</a>
 308 </h3>
 309
 310 <div>
 311
 312 <ol>
 313 <li><tt>llvm/include/llvm/Type.h</tt>:
 314     add enum for the new type; add a forward declaration of the type
 315     also</li>
 316
 317 <li><tt>llvm/include/llvm/DerivedTypes.h</tt>:
 318     add new class to represent new class in the hierarchy; add forward
 319     declaration to the TypeMap value type</li>
 320
 321 <li><tt>llvm/lib/VMCore/Type.cpp</tt>:
 322     add support for derived type to:
 323 <div class="doc_code">
 324 <pre>
 325 std::string getTypeDescription(const Type &amp;Ty,
 326   std::vector&lt;const Type*&gt; &amp;TypeStack)
 327 bool TypesEqual(const Type *Ty, const Type *Ty2,
 328   std::map&lt;const Type*, const Type*&gt; &amp; EqTypes)
 329 </pre>
 330 </div>
 331     add necessary member functions for type, and factory methods</li>
 332
 333 <li><tt>llvm/lib/AsmReader/Lexer.l</tt>:
 334     add ability to parse in the type from text assembly</li>
 335
 336 <li><tt>llvm/lib/BitCode/Writer/Writer.cpp</tt>:
 337     modify <tt>void BitcodeWriter::outputType(const Type *T)</tt> to serialize
 338     your type</li>
 339
 340 <li><tt>llvm/lib/BitCode/Reader/Reader.cpp</tt>:
 341     modify <tt>const Type *BitcodeReader::ParseType()</tt> to read your data
 342     type</li>
 343
 344 <li><tt>llvm/lib/VMCore/AsmWriter.cpp</tt>:
 345     modify
 346 <div class="doc_code">
 347 <pre>
 348 void calcTypeName(const Type *Ty,
 349                   std::vector&lt;const Type*&gt; &amp;TypeStack,
 350                   std::map&lt;const Type*,std::string&gt; &amp;TypeNames,
 351                   std::string &amp; Result)
 352 </pre>
 353 </div>
 354     to output the new derived type
 355 </li>
 356
 357
 358 </ol>
 359
 360 </div>
 361
 362 </div>
 363
 364 <!-- *********************************************************************** -->
 365
 366 <hr>
 367 <address>
 368   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 369   src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
 370   <a href="http://validator.w3.org/check/referer"><img
 371   src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
 372
 373   <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a>
 374   <br>
 375   Last modified: $Date$
 376 </address>
 377
 378 </body>
 379 </html>