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