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