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