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