Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 | "http://www.w3.org/TR/html4/strict.dtd"> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3 | <html> |
| 4 | <head> |
| 5 | <title>LLVM Programmer's Manual</title> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 6 | <link rel="stylesheet" href="llvm.css" type="text/css"> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 7 | </head> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 8 | <body> |
| 9 | |
| 10 | <div class="doc_title"> |
| 11 | LLVM Programmer's Manual |
| 12 | </div> |
| 13 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 14 | <ol> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 15 | <li><a href="#introduction">Introduction</a></li> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 16 | <li><a href="#general">General Information</a> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 17 | <ul> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 18 | <li><a href="#stl">The C++ Standard Template Library</a></li> |
| 19 | <!-- |
| 20 | <li>The <tt>-time-passes</tt> option</li> |
| 21 | <li>How to use the LLVM Makefile system</li> |
| 22 | <li>How to write a regression test</li> |
Chris Lattner | 61db465 | 2004-12-08 19:05:44 +0000 | [diff] [blame] | 23 | |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 24 | --> |
Chris Lattner | 84b7f8d | 2003-08-01 22:20:59 +0000 | [diff] [blame] | 25 | </ul> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 26 | </li> |
| 27 | <li><a href="#apis">Important and useful LLVM APIs</a> |
| 28 | <ul> |
| 29 | <li><a href="#isa">The <tt>isa<></tt>, <tt>cast<></tt> |
| 30 | and <tt>dyn_cast<></tt> templates</a> </li> |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 31 | <li><a href="#DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 32 | option</a> |
| 33 | <ul> |
| 34 | <li><a href="#DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> |
| 35 | and the <tt>-debug-only</tt> option</a> </li> |
| 36 | </ul> |
| 37 | </li> |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 38 | <li><a href="#Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 39 | option</a></li> |
| 40 | <!-- |
| 41 | <li>The <tt>InstVisitor</tt> template |
| 42 | <li>The general graph API |
| 43 | --> |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 44 | <li><a href="#ViewGraph">Viewing graphs while debugging code</a></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 45 | </ul> |
| 46 | </li> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 47 | <li><a href="#datastructure">Picking the Right Data Structure for a Task</a> |
| 48 | <ul> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 49 | <li><a href="#ds_sequential">Sequential Containers (std::vector, std::list, etc)</a> |
| 50 | <ul> |
| 51 | <li><a href="#dss_fixedarrays">Fixed Size Arrays</a></li> |
| 52 | <li><a href="#dss_heaparrays">Heap Allocated Arrays</a></li> |
| 53 | <li><a href="#dss_smallvector">"llvm/ADT/SmallVector.h"</a></li> |
| 54 | <li><a href="#dss_vector"><vector></a></li> |
| 55 | <li><a href="#dss_deque"><deque></a></li> |
| 56 | <li><a href="#dss_list"><list></a></li> |
| 57 | <li><a href="#dss_ilist">llvm/ADT/ilist</a></li> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 58 | <li><a href="#dss_other">Other Sequential Container Options</a></li> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 59 | </ul></li> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 60 | <li><a href="#ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a> |
| 61 | <ul> |
| 62 | <li><a href="#dss_sortedvectorset">A sorted 'vector'</a></li> |
| 63 | <li><a href="#dss_smallset">"llvm/ADT/SmallSet.h"</a></li> |
| 64 | <li><a href="#dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a></li> |
| 65 | <li><a href="#dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a></li> |
| 66 | <li><a href="#dss_set"><set></a></li> |
| 67 | <li><a href="#dss_setvector">"llvm/ADT/SetVector.h"</a></li> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 68 | <li><a href="#dss_uniquevector">"llvm/ADT/UniqueVector.h"</a></li> |
| 69 | <li><a href="#dss_otherset">Other Set-Like ContainerOptions</a></li> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 70 | </ul></li> |
Chris Lattner | f369252 | 2007-02-03 19:51:56 +0000 | [diff] [blame] | 71 | <li><a href="#ds_map">Map-Like Containers (std::map, DenseMap, etc)</a> |
| 72 | <ul> |
| 73 | <li><a href="#dss_sortedvectormap">A sorted 'vector'</a></li> |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 74 | <li><a href="#dss_stringmap">"llvm/ADT/StringMap.h"</a></li> |
Chris Lattner | f369252 | 2007-02-03 19:51:56 +0000 | [diff] [blame] | 75 | <li><a href="#dss_indexedmap">"llvm/ADT/IndexedMap.h"</a></li> |
| 76 | <li><a href="#dss_densemap">"llvm/ADT/DenseMap.h"</a></li> |
| 77 | <li><a href="#dss_map"><map></a></li> |
| 78 | <li><a href="#dss_othermap">Other Map-Like Container Options</a></li> |
| 79 | </ul></li> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 80 | </ul> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 81 | </li> |
Chris Lattner | ae7f759 | 2002-09-06 18:31:18 +0000 | [diff] [blame] | 82 | <li><a href="#common">Helpful Hints for Common Operations</a> |
Chris Lattner | ae7f759 | 2002-09-06 18:31:18 +0000 | [diff] [blame] | 83 | <ul> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 84 | <li><a href="#inspection">Basic Inspection and Traversal Routines</a> |
| 85 | <ul> |
| 86 | <li><a href="#iterate_function">Iterating over the <tt>BasicBlock</tt>s |
| 87 | in a <tt>Function</tt></a> </li> |
| 88 | <li><a href="#iterate_basicblock">Iterating over the <tt>Instruction</tt>s |
| 89 | in a <tt>BasicBlock</tt></a> </li> |
| 90 | <li><a href="#iterate_institer">Iterating over the <tt>Instruction</tt>s |
| 91 | in a <tt>Function</tt></a> </li> |
| 92 | <li><a href="#iterate_convert">Turning an iterator into a |
| 93 | class pointer</a> </li> |
| 94 | <li><a href="#iterate_complex">Finding call sites: a more |
| 95 | complex example</a> </li> |
| 96 | <li><a href="#calls_and_invokes">Treating calls and invokes |
| 97 | the same way</a> </li> |
| 98 | <li><a href="#iterate_chains">Iterating over def-use & |
| 99 | use-def chains</a> </li> |
| 100 | </ul> |
| 101 | </li> |
| 102 | <li><a href="#simplechanges">Making simple changes</a> |
| 103 | <ul> |
| 104 | <li><a href="#schanges_creating">Creating and inserting new |
| 105 | <tt>Instruction</tt>s</a> </li> |
| 106 | <li><a href="#schanges_deleting">Deleting <tt>Instruction</tt>s</a> </li> |
| 107 | <li><a href="#schanges_replacing">Replacing an <tt>Instruction</tt> |
| 108 | with another <tt>Value</tt></a> </li> |
| 109 | </ul> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 110 | </li> |
Chris Lattner | ae7f759 | 2002-09-06 18:31:18 +0000 | [diff] [blame] | 111 | <!-- |
| 112 | <li>Working with the Control Flow Graph |
| 113 | <ul> |
| 114 | <li>Accessing predecessors and successors of a <tt>BasicBlock</tt> |
| 115 | <li> |
| 116 | <li> |
| 117 | </ul> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 118 | --> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 119 | </ul> |
| 120 | </li> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 121 | |
| 122 | <li><a href="#advanced">Advanced Topics</a> |
| 123 | <ul> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 124 | <li><a href="#TypeResolve">LLVM Type Resolution</a> |
| 125 | <ul> |
| 126 | <li><a href="#BuildRecType">Basic Recursive Type Construction</a></li> |
| 127 | <li><a href="#refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a></li> |
| 128 | <li><a href="#PATypeHolder">The PATypeHolder Class</a></li> |
| 129 | <li><a href="#AbstractTypeUser">The AbstractTypeUser Class</a></li> |
| 130 | </ul></li> |
| 131 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 132 | <li><a href="#SymbolTable">The <tt>SymbolTable</tt> class </a></li> |
| 133 | </ul></li> |
| 134 | |
Joel Stanley | 9b96c44 | 2002-09-06 21:55:13 +0000 | [diff] [blame] | 135 | <li><a href="#coreclasses">The Core LLVM Class Hierarchy Reference</a> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 136 | <ul> |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 137 | <li><a href="#Type">The <tt>Type</tt> class</a> </li> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 138 | <li><a href="#Module">The <tt>Module</tt> class</a></li> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 139 | <li><a href="#Value">The <tt>Value</tt> class</a> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 140 | <ul> |
| 141 | <li><a href="#User">The <tt>User</tt> class</a> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 142 | <ul> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 143 | <li><a href="#Instruction">The <tt>Instruction</tt> class</a></li> |
| 144 | <li><a href="#Constant">The <tt>Constant</tt> class</a> |
| 145 | <ul> |
| 146 | <li><a href="#GlobalValue">The <tt>GlobalValue</tt> class</a> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 147 | <ul> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 148 | <li><a href="#Function">The <tt>Function</tt> class</a></li> |
| 149 | <li><a href="#GlobalVariable">The <tt>GlobalVariable</tt> class</a></li> |
| 150 | </ul> |
| 151 | </li> |
| 152 | </ul> |
| 153 | </li> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 154 | </ul> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 155 | </li> |
| 156 | <li><a href="#BasicBlock">The <tt>BasicBlock</tt> class</a></li> |
| 157 | <li><a href="#Argument">The <tt>Argument</tt> class</a></li> |
| 158 | </ul> |
Reid Spencer | fe8f4ff | 2004-11-01 09:02:53 +0000 | [diff] [blame] | 159 | </li> |
| 160 | </ul> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 161 | </li> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 162 | </ol> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 163 | |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 164 | <div class="doc_author"> |
| 165 | <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>, |
Chris Lattner | 94c4359 | 2004-05-26 16:52:55 +0000 | [diff] [blame] | 166 | <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a>, |
| 167 | <a href="mailto:jstanley@cs.uiuc.edu">Joel Stanley</a>, and |
| 168 | <a href="mailto:rspencer@x10sys.com">Reid Spencer</a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 169 | </div> |
| 170 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 171 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 172 | <div class="doc_section"> |
| 173 | <a name="introduction">Introduction </a> |
| 174 | </div> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 175 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 176 | |
| 177 | <div class="doc_text"> |
| 178 | |
| 179 | <p>This document is meant to highlight some of the important classes and |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 180 | interfaces available in the LLVM source-base. This manual is not |
| 181 | intended to explain what LLVM is, how it works, and what LLVM code looks |
| 182 | like. It assumes that you know the basics of LLVM and are interested |
| 183 | in writing transformations or otherwise analyzing or manipulating the |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 184 | code.</p> |
| 185 | |
| 186 | <p>This document should get you oriented so that you can find your |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 187 | way in the continuously growing source code that makes up the LLVM |
| 188 | infrastructure. Note that this manual is not intended to serve as a |
| 189 | replacement for reading the source code, so if you think there should be |
| 190 | a method in one of these classes to do something, but it's not listed, |
| 191 | check the source. Links to the <a href="/doxygen/">doxygen</a> sources |
| 192 | are provided to make this as easy as possible.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 193 | |
| 194 | <p>The first section of this document describes general information that is |
| 195 | useful to know when working in the LLVM infrastructure, and the second describes |
| 196 | the Core LLVM classes. In the future this manual will be extended with |
| 197 | information describing how to use extension libraries, such as dominator |
| 198 | information, CFG traversal routines, and useful utilities like the <tt><a |
| 199 | href="/doxygen/InstVisitor_8h-source.html">InstVisitor</a></tt> template.</p> |
| 200 | |
| 201 | </div> |
| 202 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 203 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 204 | <div class="doc_section"> |
| 205 | <a name="general">General Information</a> |
| 206 | </div> |
| 207 | <!-- *********************************************************************** --> |
| 208 | |
| 209 | <div class="doc_text"> |
| 210 | |
| 211 | <p>This section contains general information that is useful if you are working |
| 212 | in the LLVM source-base, but that isn't specific to any particular API.</p> |
| 213 | |
| 214 | </div> |
| 215 | |
| 216 | <!-- ======================================================================= --> |
| 217 | <div class="doc_subsection"> |
| 218 | <a name="stl">The C++ Standard Template Library</a> |
| 219 | </div> |
| 220 | |
| 221 | <div class="doc_text"> |
| 222 | |
| 223 | <p>LLVM makes heavy use of the C++ Standard Template Library (STL), |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 224 | perhaps much more than you are used to, or have seen before. Because of |
| 225 | this, you might want to do a little background reading in the |
| 226 | techniques used and capabilities of the library. There are many good |
| 227 | pages that discuss the STL, and several books on the subject that you |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 228 | can get, so it will not be discussed in this document.</p> |
| 229 | |
| 230 | <p>Here are some useful links:</p> |
| 231 | |
| 232 | <ol> |
| 233 | |
| 234 | <li><a href="http://www.dinkumware.com/refxcpp.html">Dinkumware C++ Library |
| 235 | reference</a> - an excellent reference for the STL and other parts of the |
| 236 | standard C++ library.</li> |
| 237 | |
| 238 | <li><a href="http://www.tempest-sw.com/cpp/">C++ In a Nutshell</a> - This is an |
Tanya Lattner | 09cf73c | 2004-06-22 04:24:55 +0000 | [diff] [blame] | 239 | O'Reilly book in the making. It has a decent |
| 240 | Standard Library |
| 241 | Reference that rivals Dinkumware's, and is unfortunately no longer free since the book has been |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 242 | published.</li> |
| 243 | |
| 244 | <li><a href="http://www.parashift.com/c++-faq-lite/">C++ Frequently Asked |
| 245 | Questions</a></li> |
| 246 | |
| 247 | <li><a href="http://www.sgi.com/tech/stl/">SGI's STL Programmer's Guide</a> - |
| 248 | Contains a useful <a |
| 249 | href="http://www.sgi.com/tech/stl/stl_introduction.html">Introduction to the |
| 250 | STL</a>.</li> |
| 251 | |
| 252 | <li><a href="http://www.research.att.com/%7Ebs/C++.html">Bjarne Stroustrup's C++ |
| 253 | Page</a></li> |
| 254 | |
Tanya Lattner | 79445ba | 2004-12-08 18:34:56 +0000 | [diff] [blame] | 255 | <li><a href="http://64.78.49.204/"> |
Reid Spencer | 096603a | 2004-05-26 08:41:35 +0000 | [diff] [blame] | 256 | Bruce Eckel's Thinking in C++, 2nd ed. Volume 2 Revision 4.0 (even better, get |
| 257 | the book).</a></li> |
| 258 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 259 | </ol> |
| 260 | |
| 261 | <p>You are also encouraged to take a look at the <a |
| 262 | href="CodingStandards.html">LLVM Coding Standards</a> guide which focuses on how |
| 263 | to write maintainable code more than where to put your curly braces.</p> |
| 264 | |
| 265 | </div> |
| 266 | |
| 267 | <!-- ======================================================================= --> |
| 268 | <div class="doc_subsection"> |
| 269 | <a name="stl">Other useful references</a> |
| 270 | </div> |
| 271 | |
| 272 | <div class="doc_text"> |
| 273 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 274 | <ol> |
| 275 | <li><a href="http://www.psc.edu/%7Esemke/cvs_branches.html">CVS |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 276 | Branch and Tag Primer</a></li> |
Misha Brukman | a0f71e4 | 2004-06-18 18:39:00 +0000 | [diff] [blame] | 277 | <li><a href="http://www.fortran-2000.com/ArnaudRecipes/sharedlib.html">Using |
| 278 | static and shared libraries across platforms</a></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 279 | </ol> |
| 280 | |
| 281 | </div> |
| 282 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 283 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 284 | <div class="doc_section"> |
| 285 | <a name="apis">Important and useful LLVM APIs</a> |
| 286 | </div> |
| 287 | <!-- *********************************************************************** --> |
| 288 | |
| 289 | <div class="doc_text"> |
| 290 | |
| 291 | <p>Here we highlight some LLVM APIs that are generally useful and good to |
| 292 | know about when writing transformations.</p> |
| 293 | |
| 294 | </div> |
| 295 | |
| 296 | <!-- ======================================================================= --> |
| 297 | <div class="doc_subsection"> |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 298 | <a name="isa">The <tt>isa<></tt>, <tt>cast<></tt> and |
| 299 | <tt>dyn_cast<></tt> templates</a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 300 | </div> |
| 301 | |
| 302 | <div class="doc_text"> |
| 303 | |
| 304 | <p>The LLVM source-base makes extensive use of a custom form of RTTI. |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 305 | These templates have many similarities to the C++ <tt>dynamic_cast<></tt> |
| 306 | operator, but they don't have some drawbacks (primarily stemming from |
| 307 | the fact that <tt>dynamic_cast<></tt> only works on classes that |
| 308 | have a v-table). Because they are used so often, you must know what they |
| 309 | do and how they work. All of these templates are defined in the <a |
Chris Lattner | 695b78b | 2005-04-26 22:56:16 +0000 | [diff] [blame] | 310 | href="/doxygen/Casting_8h-source.html"><tt>llvm/Support/Casting.h</tt></a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 311 | file (note that you very rarely have to include this file directly).</p> |
| 312 | |
| 313 | <dl> |
| 314 | <dt><tt>isa<></tt>: </dt> |
| 315 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 316 | <dd><p>The <tt>isa<></tt> operator works exactly like the Java |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 317 | "<tt>instanceof</tt>" operator. It returns true or false depending on whether |
| 318 | a reference or pointer points to an instance of the specified class. This can |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 319 | be very useful for constraint checking of various sorts (example below).</p> |
| 320 | </dd> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 321 | |
| 322 | <dt><tt>cast<></tt>: </dt> |
| 323 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 324 | <dd><p>The <tt>cast<></tt> operator is a "checked cast" operation. It |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 325 | converts a pointer or reference from a base class to a derived cast, causing |
| 326 | an assertion failure if it is not really an instance of the right type. This |
| 327 | should be used in cases where you have some information that makes you believe |
| 328 | that something is of the right type. An example of the <tt>isa<></tt> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 329 | and <tt>cast<></tt> template is:</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 330 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 331 | <div class="doc_code"> |
| 332 | <pre> |
| 333 | static bool isLoopInvariant(const <a href="#Value">Value</a> *V, const Loop *L) { |
| 334 | if (isa<<a href="#Constant">Constant</a>>(V) || isa<<a href="#Argument">Argument</a>>(V) || isa<<a href="#GlobalValue">GlobalValue</a>>(V)) |
| 335 | return true; |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 336 | |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 337 | // <i>Otherwise, it must be an instruction...</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 338 | return !L->contains(cast<<a href="#Instruction">Instruction</a>>(V)->getParent()); |
| 339 | } |
| 340 | </pre> |
| 341 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 342 | |
| 343 | <p>Note that you should <b>not</b> use an <tt>isa<></tt> test followed |
| 344 | by a <tt>cast<></tt>, for that use the <tt>dyn_cast<></tt> |
| 345 | operator.</p> |
| 346 | |
| 347 | </dd> |
| 348 | |
| 349 | <dt><tt>dyn_cast<></tt>:</dt> |
| 350 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 351 | <dd><p>The <tt>dyn_cast<></tt> operator is a "checking cast" operation. |
| 352 | It checks to see if the operand is of the specified type, and if so, returns a |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 353 | pointer to it (this operator does not work with references). If the operand is |
| 354 | not of the correct type, a null pointer is returned. Thus, this works very |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 355 | much like the <tt>dynamic_cast<></tt> operator in C++, and should be |
| 356 | used in the same circumstances. Typically, the <tt>dyn_cast<></tt> |
| 357 | operator is used in an <tt>if</tt> statement or some other flow control |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 358 | statement like this:</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 359 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 360 | <div class="doc_code"> |
| 361 | <pre> |
| 362 | if (<a href="#AllocationInst">AllocationInst</a> *AI = dyn_cast<<a href="#AllocationInst">AllocationInst</a>>(Val)) { |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 363 | // <i>...</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 364 | } |
| 365 | </pre> |
| 366 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 367 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 368 | <p>This form of the <tt>if</tt> statement effectively combines together a call |
| 369 | to <tt>isa<></tt> and a call to <tt>cast<></tt> into one |
| 370 | statement, which is very convenient.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 371 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 372 | <p>Note that the <tt>dyn_cast<></tt> operator, like C++'s |
| 373 | <tt>dynamic_cast<></tt> or Java's <tt>instanceof</tt> operator, can be |
| 374 | abused. In particular, you should not use big chained <tt>if/then/else</tt> |
| 375 | blocks to check for lots of different variants of classes. If you find |
| 376 | yourself wanting to do this, it is much cleaner and more efficient to use the |
| 377 | <tt>InstVisitor</tt> class to dispatch over the instruction type directly.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 378 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 379 | </dd> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 380 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 381 | <dt><tt>cast_or_null<></tt>: </dt> |
| 382 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 383 | <dd><p>The <tt>cast_or_null<></tt> operator works just like the |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 384 | <tt>cast<></tt> operator, except that it allows for a null pointer as an |
| 385 | argument (which it then propagates). This can sometimes be useful, allowing |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 386 | you to combine several null checks into one.</p></dd> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 387 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 388 | <dt><tt>dyn_cast_or_null<></tt>: </dt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 389 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 390 | <dd><p>The <tt>dyn_cast_or_null<></tt> operator works just like the |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 391 | <tt>dyn_cast<></tt> operator, except that it allows for a null pointer |
| 392 | as an argument (which it then propagates). This can sometimes be useful, |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 393 | allowing you to combine several null checks into one.</p></dd> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 394 | |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 395 | </dl> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 396 | |
| 397 | <p>These five templates can be used with any classes, whether they have a |
| 398 | v-table or not. To add support for these templates, you simply need to add |
| 399 | <tt>classof</tt> static methods to the class you are interested casting |
| 400 | to. Describing this is currently outside the scope of this document, but there |
| 401 | are lots of examples in the LLVM source base.</p> |
| 402 | |
| 403 | </div> |
| 404 | |
| 405 | <!-- ======================================================================= --> |
| 406 | <div class="doc_subsection"> |
Misha Brukman | 2c122ce | 2005-11-01 21:12:49 +0000 | [diff] [blame] | 407 | <a name="DEBUG">The <tt>DEBUG()</tt> macro and <tt>-debug</tt> option</a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 408 | </div> |
| 409 | |
| 410 | <div class="doc_text"> |
| 411 | |
| 412 | <p>Often when working on your pass you will put a bunch of debugging printouts |
| 413 | and other code into your pass. After you get it working, you want to remove |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 414 | it, but you may need it again in the future (to work out new bugs that you run |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 415 | across).</p> |
| 416 | |
| 417 | <p> Naturally, because of this, you don't want to delete the debug printouts, |
| 418 | but you don't want them to always be noisy. A standard compromise is to comment |
| 419 | them out, allowing you to enable them if you need them in the future.</p> |
| 420 | |
Chris Lattner | 695b78b | 2005-04-26 22:56:16 +0000 | [diff] [blame] | 421 | <p>The "<tt><a href="/doxygen/Debug_8h-source.html">llvm/Support/Debug.h</a></tt>" |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 422 | file provides a macro named <tt>DEBUG()</tt> that is a much nicer solution to |
| 423 | this problem. Basically, you can put arbitrary code into the argument of the |
| 424 | <tt>DEBUG</tt> macro, and it is only executed if '<tt>opt</tt>' (or any other |
| 425 | tool) is run with the '<tt>-debug</tt>' command line argument:</p> |
| 426 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 427 | <div class="doc_code"> |
| 428 | <pre> |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 429 | DOUT << "I am here!\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 430 | </pre> |
| 431 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 432 | |
| 433 | <p>Then you can run your pass like this:</p> |
| 434 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 435 | <div class="doc_code"> |
| 436 | <pre> |
| 437 | $ opt < a.bc > /dev/null -mypass |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 438 | <i><no output></i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 439 | $ opt < a.bc > /dev/null -mypass -debug |
| 440 | I am here! |
| 441 | </pre> |
| 442 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 443 | |
| 444 | <p>Using the <tt>DEBUG()</tt> macro instead of a home-brewed solution allows you |
| 445 | to not have to create "yet another" command line option for the debug output for |
| 446 | your pass. Note that <tt>DEBUG()</tt> macros are disabled for optimized builds, |
| 447 | so they do not cause a performance impact at all (for the same reason, they |
| 448 | should also not contain side-effects!).</p> |
| 449 | |
| 450 | <p>One additional nice thing about the <tt>DEBUG()</tt> macro is that you can |
| 451 | enable or disable it directly in gdb. Just use "<tt>set DebugFlag=0</tt>" or |
| 452 | "<tt>set DebugFlag=1</tt>" from the gdb if the program is running. If the |
| 453 | program hasn't been started yet, you can always just run it with |
| 454 | <tt>-debug</tt>.</p> |
| 455 | |
| 456 | </div> |
| 457 | |
| 458 | <!-- _______________________________________________________________________ --> |
| 459 | <div class="doc_subsubsection"> |
Chris Lattner | c915108 | 2005-04-26 22:57:07 +0000 | [diff] [blame] | 460 | <a name="DEBUG_TYPE">Fine grained debug info with <tt>DEBUG_TYPE</tt> and |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 461 | the <tt>-debug-only</tt> option</a> |
| 462 | </div> |
| 463 | |
| 464 | <div class="doc_text"> |
| 465 | |
| 466 | <p>Sometimes you may find yourself in a situation where enabling <tt>-debug</tt> |
| 467 | just turns on <b>too much</b> information (such as when working on the code |
| 468 | generator). If you want to enable debug information with more fine-grained |
| 469 | control, you define the <tt>DEBUG_TYPE</tt> macro and the <tt>-debug</tt> only |
| 470 | option as follows:</p> |
| 471 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 472 | <div class="doc_code"> |
| 473 | <pre> |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 474 | DOUT << "No debug type\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 475 | #undef DEBUG_TYPE |
| 476 | #define DEBUG_TYPE "foo" |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 477 | DOUT << "'foo' debug type\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 478 | #undef DEBUG_TYPE |
| 479 | #define DEBUG_TYPE "bar" |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 480 | DOUT << "'bar' debug type\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 481 | #undef DEBUG_TYPE |
| 482 | #define DEBUG_TYPE "" |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 483 | DOUT << "No debug type (2)\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 484 | </pre> |
| 485 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 486 | |
| 487 | <p>Then you can run your pass like this:</p> |
| 488 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 489 | <div class="doc_code"> |
| 490 | <pre> |
| 491 | $ opt < a.bc > /dev/null -mypass |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 492 | <i><no output></i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 493 | $ opt < a.bc > /dev/null -mypass -debug |
| 494 | No debug type |
| 495 | 'foo' debug type |
| 496 | 'bar' debug type |
| 497 | No debug type (2) |
| 498 | $ opt < a.bc > /dev/null -mypass -debug-only=foo |
| 499 | 'foo' debug type |
| 500 | $ opt < a.bc > /dev/null -mypass -debug-only=bar |
| 501 | 'bar' debug type |
| 502 | </pre> |
| 503 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 504 | |
| 505 | <p>Of course, in practice, you should only set <tt>DEBUG_TYPE</tt> at the top of |
| 506 | a file, to specify the debug type for the entire module (if you do this before |
Chris Lattner | 695b78b | 2005-04-26 22:56:16 +0000 | [diff] [blame] | 507 | you <tt>#include "llvm/Support/Debug.h"</tt>, you don't have to insert the ugly |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 508 | <tt>#undef</tt>'s). Also, you should use names more meaningful than "foo" and |
| 509 | "bar", because there is no system in place to ensure that names do not |
| 510 | conflict. If two different modules use the same string, they will all be turned |
| 511 | on when the name is specified. This allows, for example, all debug information |
| 512 | for instruction scheduling to be enabled with <tt>-debug-type=InstrSched</tt>, |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 513 | even if the source lives in multiple files.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 514 | |
| 515 | </div> |
| 516 | |
| 517 | <!-- ======================================================================= --> |
| 518 | <div class="doc_subsection"> |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 519 | <a name="Statistic">The <tt>Statistic</tt> class & <tt>-stats</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 520 | option</a> |
| 521 | </div> |
| 522 | |
| 523 | <div class="doc_text"> |
| 524 | |
| 525 | <p>The "<tt><a |
Chris Lattner | 695b78b | 2005-04-26 22:56:16 +0000 | [diff] [blame] | 526 | href="/doxygen/Statistic_8h-source.html">llvm/ADT/Statistic.h</a></tt>" file |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 527 | provides a class named <tt>Statistic</tt> that is used as a unified way to |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 528 | keep track of what the LLVM compiler is doing and how effective various |
| 529 | optimizations are. It is useful to see what optimizations are contributing to |
| 530 | making a particular program run faster.</p> |
| 531 | |
| 532 | <p>Often you may run your pass on some big program, and you're interested to see |
| 533 | how many times it makes a certain transformation. Although you can do this with |
| 534 | hand inspection, or some ad-hoc method, this is a real pain and not very useful |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 535 | for big programs. Using the <tt>Statistic</tt> class makes it very easy to |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 536 | keep track of this information, and the calculated information is presented in a |
| 537 | uniform manner with the rest of the passes being executed.</p> |
| 538 | |
| 539 | <p>There are many examples of <tt>Statistic</tt> uses, but the basics of using |
| 540 | it are as follows:</p> |
| 541 | |
| 542 | <ol> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 543 | <li><p>Define your statistic like this:</p> |
| 544 | |
| 545 | <div class="doc_code"> |
| 546 | <pre> |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 547 | #define <a href="#DEBUG_TYPE">DEBUG_TYPE</a> "mypassname" <i>// This goes before any #includes.</i> |
| 548 | STATISTIC(NumXForms, "The # of times I did stuff"); |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 549 | </pre> |
| 550 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 551 | |
Chris Lattner | 0be6fdf | 2006-12-19 21:46:21 +0000 | [diff] [blame] | 552 | <p>The <tt>STATISTIC</tt> macro defines a static variable, whose name is |
| 553 | specified by the first argument. The pass name is taken from the DEBUG_TYPE |
| 554 | macro, and the description is taken from the second argument. The variable |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 555 | defined ("NumXForms" in this case) acts like an unsigned integer.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 556 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 557 | <li><p>Whenever you make a transformation, bump the counter:</p> |
| 558 | |
| 559 | <div class="doc_code"> |
| 560 | <pre> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 561 | ++NumXForms; // <i>I did stuff!</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 562 | </pre> |
| 563 | </div> |
| 564 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 565 | </li> |
| 566 | </ol> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 567 | |
| 568 | <p>That's all you have to do. To get '<tt>opt</tt>' to print out the |
| 569 | statistics gathered, use the '<tt>-stats</tt>' option:</p> |
| 570 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 571 | <div class="doc_code"> |
| 572 | <pre> |
| 573 | $ opt -stats -mypassname < program.bc > /dev/null |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 574 | <i>... statistics output ...</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 575 | </pre> |
| 576 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 577 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 578 | <p> When running <tt>gccas</tt> on a C file from the SPEC benchmark |
| 579 | suite, it gives a report that looks like this:</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 580 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 581 | <div class="doc_code"> |
| 582 | <pre> |
| 583 | 7646 bytecodewriter - Number of normal instructions |
| 584 | 725 bytecodewriter - Number of oversized instructions |
| 585 | 129996 bytecodewriter - Number of bytecode bytes written |
| 586 | 2817 raise - Number of insts DCEd or constprop'd |
| 587 | 3213 raise - Number of cast-of-self removed |
| 588 | 5046 raise - Number of expression trees converted |
| 589 | 75 raise - Number of other getelementptr's formed |
| 590 | 138 raise - Number of load/store peepholes |
| 591 | 42 deadtypeelim - Number of unused typenames removed from symtab |
| 592 | 392 funcresolve - Number of varargs functions resolved |
| 593 | 27 globaldce - Number of global variables removed |
| 594 | 2 adce - Number of basic blocks removed |
| 595 | 134 cee - Number of branches revectored |
| 596 | 49 cee - Number of setcc instruction eliminated |
| 597 | 532 gcse - Number of loads removed |
| 598 | 2919 gcse - Number of instructions removed |
| 599 | 86 indvars - Number of canonical indvars added |
| 600 | 87 indvars - Number of aux indvars removed |
| 601 | 25 instcombine - Number of dead inst eliminate |
| 602 | 434 instcombine - Number of insts combined |
| 603 | 248 licm - Number of load insts hoisted |
| 604 | 1298 licm - Number of insts hoisted to a loop pre-header |
| 605 | 3 licm - Number of insts hoisted to multiple loop preds (bad, no loop pre-header) |
| 606 | 75 mem2reg - Number of alloca's promoted |
| 607 | 1444 cfgsimplify - Number of blocks simplified |
| 608 | </pre> |
| 609 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 610 | |
| 611 | <p>Obviously, with so many optimizations, having a unified framework for this |
| 612 | stuff is very nice. Making your pass fit well into the framework makes it more |
| 613 | maintainable and useful.</p> |
| 614 | |
| 615 | </div> |
| 616 | |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 617 | <!-- ======================================================================= --> |
| 618 | <div class="doc_subsection"> |
| 619 | <a name="ViewGraph">Viewing graphs while debugging code</a> |
| 620 | </div> |
| 621 | |
| 622 | <div class="doc_text"> |
| 623 | |
| 624 | <p>Several of the important data structures in LLVM are graphs: for example |
| 625 | CFGs made out of LLVM <a href="#BasicBlock">BasicBlock</a>s, CFGs made out of |
| 626 | LLVM <a href="CodeGenerator.html#machinebasicblock">MachineBasicBlock</a>s, and |
| 627 | <a href="CodeGenerator.html#selectiondag_intro">Instruction Selection |
| 628 | DAGs</a>. In many cases, while debugging various parts of the compiler, it is |
| 629 | nice to instantly visualize these graphs.</p> |
| 630 | |
| 631 | <p>LLVM provides several callbacks that are available in a debug build to do |
| 632 | exactly that. If you call the <tt>Function::viewCFG()</tt> method, for example, |
| 633 | the current LLVM tool will pop up a window containing the CFG for the function |
| 634 | where each basic block is a node in the graph, and each node contains the |
| 635 | instructions in the block. Similarly, there also exists |
| 636 | <tt>Function::viewCFGOnly()</tt> (does not include the instructions), the |
| 637 | <tt>MachineFunction::viewCFG()</tt> and <tt>MachineFunction::viewCFGOnly()</tt>, |
| 638 | and the <tt>SelectionDAG::viewGraph()</tt> methods. Within GDB, for example, |
Jim Laskey | 543a0ee | 2006-10-02 12:28:07 +0000 | [diff] [blame] | 639 | you can usually use something like <tt>call DAG.viewGraph()</tt> to pop |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 640 | up a window. Alternatively, you can sprinkle calls to these functions in your |
| 641 | code in places you want to debug.</p> |
| 642 | |
| 643 | <p>Getting this to work requires a small amount of configuration. On Unix |
| 644 | systems with X11, install the <a href="http://www.graphviz.org">graphviz</a> |
| 645 | toolkit, and make sure 'dot' and 'gv' are in your path. If you are running on |
| 646 | Mac OS/X, download and install the Mac OS/X <a |
| 647 | href="http://www.pixelglow.com/graphviz/">Graphviz program</a>, and add |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 648 | <tt>/Applications/Graphviz.app/Contents/MacOS/</tt> (or wherever you install |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 649 | it) to your path. Once in your system and path are set up, rerun the LLVM |
| 650 | configure script and rebuild LLVM to enable this functionality.</p> |
| 651 | |
Jim Laskey | 543a0ee | 2006-10-02 12:28:07 +0000 | [diff] [blame] | 652 | <p><tt>SelectionDAG</tt> has been extended to make it easier to locate |
| 653 | <i>interesting</i> nodes in large complex graphs. From gdb, if you |
| 654 | <tt>call DAG.setGraphColor(<i>node</i>, "<i>color</i>")</tt>, then the |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 655 | next <tt>call DAG.viewGraph()</tt> would highlight the node in the |
Jim Laskey | 543a0ee | 2006-10-02 12:28:07 +0000 | [diff] [blame] | 656 | specified color (choices of colors can be found at <a |
Chris Lattner | 302da1e | 2007-02-03 03:05:57 +0000 | [diff] [blame] | 657 | href="http://www.graphviz.org/doc/info/colors.html">colors</a>.) More |
Jim Laskey | 543a0ee | 2006-10-02 12:28:07 +0000 | [diff] [blame] | 658 | complex node attributes can be provided with <tt>call |
| 659 | DAG.setGraphAttrs(<i>node</i>, "<i>attributes</i>")</tt> (choices can be |
| 660 | found at <a href="http://www.graphviz.org/doc/info/attrs.html">Graph |
| 661 | Attributes</a>.) If you want to restart and clear all the current graph |
| 662 | attributes, then you can <tt>call DAG.clearGraphAttrs()</tt>. </p> |
| 663 | |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 664 | </div> |
| 665 | |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 666 | <!-- *********************************************************************** --> |
| 667 | <div class="doc_section"> |
| 668 | <a name="datastructure">Picking the Right Data Structure for a Task</a> |
| 669 | </div> |
| 670 | <!-- *********************************************************************** --> |
| 671 | |
| 672 | <div class="doc_text"> |
| 673 | |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 674 | <p>LLVM has a plethora of data structures in the <tt>llvm/ADT/</tt> directory, |
| 675 | and we commonly use STL data structures. This section describes the trade-offs |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 676 | you should consider when you pick one.</p> |
| 677 | |
| 678 | <p> |
| 679 | The first step is a choose your own adventure: do you want a sequential |
| 680 | container, a set-like container, or a map-like container? The most important |
| 681 | thing when choosing a container is the algorithmic properties of how you plan to |
| 682 | access the container. Based on that, you should use:</p> |
| 683 | |
| 684 | <ul> |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 685 | <li>a <a href="#ds_map">map-like</a> container if you need efficient look-up |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 686 | of an value based on another value. Map-like containers also support |
| 687 | efficient queries for containment (whether a key is in the map). Map-like |
| 688 | containers generally do not support efficient reverse mapping (values to |
| 689 | keys). If you need that, use two maps. Some map-like containers also |
| 690 | support efficient iteration through the keys in sorted order. Map-like |
| 691 | containers are the most expensive sort, only use them if you need one of |
| 692 | these capabilities.</li> |
| 693 | |
| 694 | <li>a <a href="#ds_set">set-like</a> container if you need to put a bunch of |
| 695 | stuff into a container that automatically eliminates duplicates. Some |
| 696 | set-like containers support efficient iteration through the elements in |
| 697 | sorted order. Set-like containers are more expensive than sequential |
| 698 | containers. |
| 699 | </li> |
| 700 | |
| 701 | <li>a <a href="#ds_sequential">sequential</a> container provides |
| 702 | the most efficient way to add elements and keeps track of the order they are |
| 703 | added to the collection. They permit duplicates and support efficient |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 704 | iteration, but do not support efficient look-up based on a key. |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 705 | </li> |
| 706 | |
| 707 | </ul> |
| 708 | |
| 709 | <p> |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 710 | Once the proper category of container is determined, you can fine tune the |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 711 | memory use, constant factors, and cache behaviors of access by intelligently |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 712 | picking a member of the category. Note that constant factors and cache behavior |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 713 | can be a big deal. If you have a vector that usually only contains a few |
| 714 | elements (but could contain many), for example, it's much better to use |
| 715 | <a href="#dss_smallvector">SmallVector</a> than <a href="#dss_vector">vector</a> |
| 716 | . Doing so avoids (relatively) expensive malloc/free calls, which dwarf the |
| 717 | cost of adding the elements to the container. </p> |
| 718 | |
| 719 | </div> |
| 720 | |
| 721 | <!-- ======================================================================= --> |
| 722 | <div class="doc_subsection"> |
| 723 | <a name="ds_sequential">Sequential Containers (std::vector, std::list, etc)</a> |
| 724 | </div> |
| 725 | |
| 726 | <div class="doc_text"> |
| 727 | There are a variety of sequential containers available for you, based on your |
| 728 | needs. Pick the first in this section that will do what you want. |
| 729 | </div> |
| 730 | |
| 731 | <!-- _______________________________________________________________________ --> |
| 732 | <div class="doc_subsubsection"> |
| 733 | <a name="dss_fixedarrays">Fixed Size Arrays</a> |
| 734 | </div> |
| 735 | |
| 736 | <div class="doc_text"> |
| 737 | <p>Fixed size arrays are very simple and very fast. They are good if you know |
| 738 | exactly how many elements you have, or you have a (low) upper bound on how many |
| 739 | you have.</p> |
| 740 | </div> |
| 741 | |
| 742 | <!-- _______________________________________________________________________ --> |
| 743 | <div class="doc_subsubsection"> |
| 744 | <a name="dss_heaparrays">Heap Allocated Arrays</a> |
| 745 | </div> |
| 746 | |
| 747 | <div class="doc_text"> |
| 748 | <p>Heap allocated arrays (new[] + delete[]) are also simple. They are good if |
| 749 | the number of elements is variable, if you know how many elements you will need |
| 750 | before the array is allocated, and if the array is usually large (if not, |
| 751 | consider a <a href="#dss_smallvector">SmallVector</a>). The cost of a heap |
| 752 | allocated array is the cost of the new/delete (aka malloc/free). Also note that |
| 753 | if you are allocating an array of a type with a constructor, the constructor and |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 754 | destructors will be run for every element in the array (re-sizable vectors only |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 755 | construct those elements actually used).</p> |
| 756 | </div> |
| 757 | |
| 758 | <!-- _______________________________________________________________________ --> |
| 759 | <div class="doc_subsubsection"> |
| 760 | <a name="dss_smallvector">"llvm/ADT/SmallVector.h"</a> |
| 761 | </div> |
| 762 | |
| 763 | <div class="doc_text"> |
| 764 | <p><tt>SmallVector<Type, N></tt> is a simple class that looks and smells |
| 765 | just like <tt>vector<Type></tt>: |
| 766 | it supports efficient iteration, lays out elements in memory order (so you can |
| 767 | do pointer arithmetic between elements), supports efficient push_back/pop_back |
| 768 | operations, supports efficient random access to its elements, etc.</p> |
| 769 | |
| 770 | <p>The advantage of SmallVector is that it allocates space for |
| 771 | some number of elements (N) <b>in the object itself</b>. Because of this, if |
| 772 | the SmallVector is dynamically smaller than N, no malloc is performed. This can |
| 773 | be a big win in cases where the malloc/free call is far more expensive than the |
| 774 | code that fiddles around with the elements.</p> |
| 775 | |
| 776 | <p>This is good for vectors that are "usually small" (e.g. the number of |
| 777 | predecessors/successors of a block is usually less than 8). On the other hand, |
| 778 | this makes the size of the SmallVector itself large, so you don't want to |
| 779 | allocate lots of them (doing so will waste a lot of space). As such, |
| 780 | SmallVectors are most useful when on the stack.</p> |
| 781 | |
| 782 | <p>SmallVector also provides a nice portable and efficient replacement for |
| 783 | <tt>alloca</tt>.</p> |
| 784 | |
| 785 | </div> |
| 786 | |
| 787 | <!-- _______________________________________________________________________ --> |
| 788 | <div class="doc_subsubsection"> |
| 789 | <a name="dss_vector"><vector></a> |
| 790 | </div> |
| 791 | |
| 792 | <div class="doc_text"> |
| 793 | <p> |
| 794 | std::vector is well loved and respected. It is useful when SmallVector isn't: |
| 795 | when the size of the vector is often large (thus the small optimization will |
| 796 | rarely be a benefit) or if you will be allocating many instances of the vector |
| 797 | itself (which would waste space for elements that aren't in the container). |
| 798 | vector is also useful when interfacing with code that expects vectors :). |
| 799 | </p> |
Chris Lattner | 32d8476 | 2007-02-05 06:30:51 +0000 | [diff] [blame] | 800 | |
| 801 | <p>One worthwhile note about std::vector: avoid code like this:</p> |
| 802 | |
| 803 | <div class="doc_code"> |
| 804 | <pre> |
| 805 | for ( ... ) { |
| 806 | std::vector<foo> V; |
| 807 | use V; |
| 808 | } |
| 809 | </pre> |
| 810 | </div> |
| 811 | |
| 812 | <p>Instead, write this as:</p> |
| 813 | |
| 814 | <div class="doc_code"> |
| 815 | <pre> |
| 816 | std::vector<foo> V; |
| 817 | for ( ... ) { |
| 818 | use V; |
| 819 | V.clear(); |
| 820 | } |
| 821 | </pre> |
| 822 | </div> |
| 823 | |
| 824 | <p>Doing so will save (at least) one heap allocation and free per iteration of |
| 825 | the loop.</p> |
| 826 | |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 827 | </div> |
| 828 | |
| 829 | <!-- _______________________________________________________________________ --> |
| 830 | <div class="doc_subsubsection"> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 831 | <a name="dss_deque"><deque></a> |
| 832 | </div> |
| 833 | |
| 834 | <div class="doc_text"> |
| 835 | <p>std::deque is, in some senses, a generalized version of std::vector. Like |
| 836 | std::vector, it provides constant time random access and other similar |
| 837 | properties, but it also provides efficient access to the front of the list. It |
| 838 | does not guarantee continuity of elements within memory.</p> |
| 839 | |
| 840 | <p>In exchange for this extra flexibility, std::deque has significantly higher |
| 841 | constant factor costs than std::vector. If possible, use std::vector or |
| 842 | something cheaper.</p> |
| 843 | </div> |
| 844 | |
| 845 | <!-- _______________________________________________________________________ --> |
| 846 | <div class="doc_subsubsection"> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 847 | <a name="dss_list"><list></a> |
| 848 | </div> |
| 849 | |
| 850 | <div class="doc_text"> |
| 851 | <p>std::list is an extremely inefficient class that is rarely useful. |
| 852 | It performs a heap allocation for every element inserted into it, thus having an |
| 853 | extremely high constant factor, particularly for small data types. std::list |
| 854 | also only supports bidirectional iteration, not random access iteration.</p> |
| 855 | |
| 856 | <p>In exchange for this high cost, std::list supports efficient access to both |
| 857 | ends of the list (like std::deque, but unlike std::vector or SmallVector). In |
| 858 | addition, the iterator invalidation characteristics of std::list are stronger |
| 859 | than that of a vector class: inserting or removing an element into the list does |
| 860 | not invalidate iterator or pointers to other elements in the list.</p> |
| 861 | </div> |
| 862 | |
| 863 | <!-- _______________________________________________________________________ --> |
| 864 | <div class="doc_subsubsection"> |
| 865 | <a name="dss_ilist">llvm/ADT/ilist</a> |
| 866 | </div> |
| 867 | |
| 868 | <div class="doc_text"> |
| 869 | <p><tt>ilist<T></tt> implements an 'intrusive' doubly-linked list. It is |
| 870 | intrusive, because it requires the element to store and provide access to the |
| 871 | prev/next pointers for the list.</p> |
| 872 | |
| 873 | <p>ilist has the same drawbacks as std::list, and additionally requires an |
| 874 | ilist_traits implementation for the element type, but it provides some novel |
| 875 | characteristics. In particular, it can efficiently store polymorphic objects, |
| 876 | the traits class is informed when an element is inserted or removed from the |
| 877 | list, and ilists are guaranteed to support a constant-time splice operation. |
| 878 | </p> |
| 879 | |
| 880 | <p>These properties are exactly what we want for things like Instructions and |
| 881 | basic blocks, which is why these are implemented with ilists.</p> |
| 882 | </div> |
| 883 | |
| 884 | <!-- _______________________________________________________________________ --> |
| 885 | <div class="doc_subsubsection"> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 886 | <a name="dss_other">Other Sequential Container options</a> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 887 | </div> |
| 888 | |
| 889 | <div class="doc_text"> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 890 | <p>Other STL containers are available, such as std::string.</p> |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 891 | |
| 892 | <p>There are also various STL adapter classes such as std::queue, |
| 893 | std::priority_queue, std::stack, etc. These provide simplified access to an |
| 894 | underlying container but don't affect the cost of the container itself.</p> |
| 895 | |
| 896 | </div> |
| 897 | |
| 898 | |
| 899 | <!-- ======================================================================= --> |
| 900 | <div class="doc_subsection"> |
| 901 | <a name="ds_set">Set-Like Containers (std::set, SmallSet, SetVector, etc)</a> |
| 902 | </div> |
| 903 | |
| 904 | <div class="doc_text"> |
| 905 | |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 906 | <p>Set-like containers are useful when you need to canonicalize multiple values |
| 907 | into a single representation. There are several different choices for how to do |
| 908 | this, providing various trade-offs.</p> |
| 909 | |
| 910 | </div> |
| 911 | |
| 912 | |
| 913 | <!-- _______________________________________________________________________ --> |
| 914 | <div class="doc_subsubsection"> |
| 915 | <a name="dss_sortedvectorset">A sorted 'vector'</a> |
| 916 | </div> |
| 917 | |
| 918 | <div class="doc_text"> |
| 919 | |
Chris Lattner | 3b23a8c | 2007-02-03 08:10:45 +0000 | [diff] [blame] | 920 | <p>If you intend to insert a lot of elements, then do a lot of queries, a |
| 921 | great approach is to use a vector (or other sequential container) with |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 922 | std::sort+std::unique to remove duplicates. This approach works really well if |
Chris Lattner | 3b23a8c | 2007-02-03 08:10:45 +0000 | [diff] [blame] | 923 | your usage pattern has these two distinct phases (insert then query), and can be |
| 924 | coupled with a good choice of <a href="#ds_sequential">sequential container</a>. |
| 925 | </p> |
| 926 | |
| 927 | <p> |
| 928 | This combination provides the several nice properties: the result data is |
| 929 | contiguous in memory (good for cache locality), has few allocations, is easy to |
| 930 | address (iterators in the final vector are just indices or pointers), and can be |
| 931 | efficiently queried with a standard binary or radix search.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 932 | |
| 933 | </div> |
| 934 | |
| 935 | <!-- _______________________________________________________________________ --> |
| 936 | <div class="doc_subsubsection"> |
| 937 | <a name="dss_smallset">"llvm/ADT/SmallSet.h"</a> |
| 938 | </div> |
| 939 | |
| 940 | <div class="doc_text"> |
| 941 | |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 942 | <p>If you have a set-like data structure that is usually small and whose elements |
Chris Lattner | 4ddfac1 | 2007-02-03 07:59:51 +0000 | [diff] [blame] | 943 | are reasonably small, a <tt>SmallSet<Type, N></tt> is a good choice. This set |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 944 | has space for N elements in place (thus, if the set is dynamically smaller than |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 945 | N, no malloc traffic is required) and accesses them with a simple linear search. |
| 946 | When the set grows beyond 'N' elements, it allocates a more expensive representation that |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 947 | guarantees efficient access (for most types, it falls back to std::set, but for |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 948 | pointers it uses something far better, <a |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 949 | href="#dss_smallptrset">SmallPtrSet</a>).</p> |
| 950 | |
| 951 | <p>The magic of this class is that it handles small sets extremely efficiently, |
| 952 | but gracefully handles extremely large sets without loss of efficiency. The |
| 953 | drawback is that the interface is quite small: it supports insertion, queries |
| 954 | and erasing, but does not support iteration.</p> |
| 955 | |
| 956 | </div> |
| 957 | |
| 958 | <!-- _______________________________________________________________________ --> |
| 959 | <div class="doc_subsubsection"> |
| 960 | <a name="dss_smallptrset">"llvm/ADT/SmallPtrSet.h"</a> |
| 961 | </div> |
| 962 | |
| 963 | <div class="doc_text"> |
| 964 | |
| 965 | <p>SmallPtrSet has all the advantages of SmallSet (and a SmallSet of pointers is |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 966 | transparently implemented with a SmallPtrSet), but also supports iterators. If |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 967 | more than 'N' insertions are performed, a single quadratically |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 968 | probed hash table is allocated and grows as needed, providing extremely |
| 969 | efficient access (constant time insertion/deleting/queries with low constant |
| 970 | factors) and is very stingy with malloc traffic.</p> |
| 971 | |
| 972 | <p>Note that, unlike std::set, the iterators of SmallPtrSet are invalidated |
| 973 | whenever an insertion occurs. Also, the values visited by the iterators are not |
| 974 | visited in sorted order.</p> |
| 975 | |
| 976 | </div> |
| 977 | |
| 978 | <!-- _______________________________________________________________________ --> |
| 979 | <div class="doc_subsubsection"> |
| 980 | <a name="dss_FoldingSet">"llvm/ADT/FoldingSet.h"</a> |
| 981 | </div> |
| 982 | |
| 983 | <div class="doc_text"> |
| 984 | |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 985 | <p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 986 | FoldingSet is an aggregate class that is really good at uniquing |
| 987 | expensive-to-create or polymorphic objects. It is a combination of a chained |
| 988 | hash table with intrusive links (uniqued objects are required to inherit from |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 989 | FoldingSetNode) that uses <a href="#dss_smallvector">SmallVector</a> as part of |
| 990 | its ID process.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 991 | |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 992 | <p>Consider a case where you want to implement a "getOrCreateFoo" method for |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 993 | a complex object (for example, a node in the code generator). The client has a |
| 994 | description of *what* it wants to generate (it knows the opcode and all the |
| 995 | operands), but we don't want to 'new' a node, then try inserting it into a set |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 996 | only to find out it already exists, at which point we would have to delete it |
| 997 | and return the node that already exists. |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 998 | </p> |
| 999 | |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1000 | <p>To support this style of client, FoldingSet perform a query with a |
| 1001 | FoldingSetNodeID (which wraps SmallVector) that can be used to describe the |
| 1002 | element that we want to query for. The query either returns the element |
| 1003 | matching the ID or it returns an opaque ID that indicates where insertion should |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1004 | take place. Construction of the ID usually does not require heap traffic.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1005 | |
| 1006 | <p>Because FoldingSet uses intrusive links, it can support polymorphic objects |
| 1007 | in the set (for example, you can have SDNode instances mixed with LoadSDNodes). |
| 1008 | Because the elements are individually allocated, pointers to the elements are |
| 1009 | stable: inserting or removing elements does not invalidate any pointers to other |
| 1010 | elements. |
| 1011 | </p> |
| 1012 | |
| 1013 | </div> |
| 1014 | |
| 1015 | <!-- _______________________________________________________________________ --> |
| 1016 | <div class="doc_subsubsection"> |
| 1017 | <a name="dss_set"><set></a> |
| 1018 | </div> |
| 1019 | |
| 1020 | <div class="doc_text"> |
| 1021 | |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1022 | <p><tt>std::set</tt> is a reasonable all-around set class, which is decent at |
| 1023 | many things but great at nothing. std::set allocates memory for each element |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1024 | inserted (thus it is very malloc intensive) and typically stores three pointers |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1025 | per element in the set (thus adding a large amount of per-element space |
| 1026 | overhead). It offers guaranteed log(n) performance, which is not particularly |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1027 | fast from a complexity standpoint (particularly if the elements of the set are |
| 1028 | expensive to compare, like strings), and has extremely high constant factors for |
| 1029 | lookup, insertion and removal.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1030 | |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1031 | <p>The advantages of std::set are that its iterators are stable (deleting or |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1032 | inserting an element from the set does not affect iterators or pointers to other |
| 1033 | elements) and that iteration over the set is guaranteed to be in sorted order. |
| 1034 | If the elements in the set are large, then the relative overhead of the pointers |
| 1035 | and malloc traffic is not a big deal, but if the elements of the set are small, |
| 1036 | std::set is almost never a good choice.</p> |
| 1037 | |
| 1038 | </div> |
| 1039 | |
| 1040 | <!-- _______________________________________________________________________ --> |
| 1041 | <div class="doc_subsubsection"> |
| 1042 | <a name="dss_setvector">"llvm/ADT/SetVector.h"</a> |
| 1043 | </div> |
| 1044 | |
| 1045 | <div class="doc_text"> |
Chris Lattner | edca3c5 | 2007-02-04 00:00:26 +0000 | [diff] [blame] | 1046 | <p>LLVM's SetVector<Type> is an adapter class that combines your choice of |
| 1047 | a set-like container along with a <a href="#ds_sequential">Sequential |
| 1048 | Container</a>. The important property |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1049 | that this provides is efficient insertion with uniquing (duplicate elements are |
| 1050 | ignored) with iteration support. It implements this by inserting elements into |
| 1051 | both a set-like container and the sequential container, using the set-like |
| 1052 | container for uniquing and the sequential container for iteration. |
| 1053 | </p> |
| 1054 | |
| 1055 | <p>The difference between SetVector and other sets is that the order of |
| 1056 | iteration is guaranteed to match the order of insertion into the SetVector. |
| 1057 | This property is really important for things like sets of pointers. Because |
| 1058 | pointer values are non-deterministic (e.g. vary across runs of the program on |
Chris Lattner | edca3c5 | 2007-02-04 00:00:26 +0000 | [diff] [blame] | 1059 | different machines), iterating over the pointers in the set will |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1060 | not be in a well-defined order.</p> |
| 1061 | |
| 1062 | <p> |
| 1063 | The drawback of SetVector is that it requires twice as much space as a normal |
| 1064 | set and has the sum of constant factors from the set-like container and the |
| 1065 | sequential container that it uses. Use it *only* if you need to iterate over |
| 1066 | the elements in a deterministic order. SetVector is also expensive to delete |
Chris Lattner | edca3c5 | 2007-02-04 00:00:26 +0000 | [diff] [blame] | 1067 | elements out of (linear time), unless you use it's "pop_back" method, which is |
| 1068 | faster. |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1069 | </p> |
| 1070 | |
Chris Lattner | edca3c5 | 2007-02-04 00:00:26 +0000 | [diff] [blame] | 1071 | <p>SetVector is an adapter class that defaults to using std::vector and std::set |
| 1072 | for the underlying containers, so it is quite expensive. However, |
| 1073 | <tt>"llvm/ADT/SetVector.h"</tt> also provides a SmallSetVector class, which |
| 1074 | defaults to using a SmallVector and SmallSet of a specified size. If you use |
| 1075 | this, and if your sets are dynamically smaller than N, you will save a lot of |
| 1076 | heap traffic.</p> |
| 1077 | |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1078 | </div> |
| 1079 | |
| 1080 | <!-- _______________________________________________________________________ --> |
| 1081 | <div class="doc_subsubsection"> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1082 | <a name="dss_uniquevector">"llvm/ADT/UniqueVector.h"</a> |
| 1083 | </div> |
| 1084 | |
| 1085 | <div class="doc_text"> |
| 1086 | |
| 1087 | <p> |
| 1088 | UniqueVector is similar to <a href="#dss_setvector">SetVector</a>, but it |
| 1089 | retains a unique ID for each element inserted into the set. It internally |
| 1090 | contains a map and a vector, and it assigns a unique ID for each value inserted |
| 1091 | into the set.</p> |
| 1092 | |
| 1093 | <p>UniqueVector is very expensive: its cost is the sum of the cost of |
| 1094 | maintaining both the map and vector, it has high complexity, high constant |
| 1095 | factors, and produces a lot of malloc traffic. It should be avoided.</p> |
| 1096 | |
| 1097 | </div> |
| 1098 | |
| 1099 | |
| 1100 | <!-- _______________________________________________________________________ --> |
| 1101 | <div class="doc_subsubsection"> |
| 1102 | <a name="dss_otherset">Other Set-Like Container Options</a> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1103 | </div> |
| 1104 | |
| 1105 | <div class="doc_text"> |
| 1106 | |
| 1107 | <p> |
| 1108 | The STL provides several other options, such as std::multiset and the various |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1109 | "hash_set" like containers (whether from C++ TR1 or from the SGI library).</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1110 | |
| 1111 | <p>std::multiset is useful if you're not interested in elimination of |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1112 | duplicates, but has all the drawbacks of std::set. A sorted vector (where you |
| 1113 | don't delete duplicate entries) or some other approach is almost always |
| 1114 | better.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1115 | |
| 1116 | <p>The various hash_set implementations (exposed portably by |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1117 | "llvm/ADT/hash_set") is a simple chained hashtable. This algorithm is as malloc |
| 1118 | intensive as std::set (performing an allocation for each element inserted, |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1119 | thus having really high constant factors) but (usually) provides O(1) |
| 1120 | insertion/deletion of elements. This can be useful if your elements are large |
Chris Lattner | 14868db | 2007-02-03 08:20:15 +0000 | [diff] [blame] | 1121 | (thus making the constant-factor cost relatively low) or if comparisons are |
| 1122 | expensive. Element iteration does not visit elements in a useful order.</p> |
Chris Lattner | 74c4ca1 | 2007-02-03 07:59:07 +0000 | [diff] [blame] | 1123 | |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 1124 | </div> |
| 1125 | |
| 1126 | <!-- ======================================================================= --> |
| 1127 | <div class="doc_subsection"> |
| 1128 | <a name="ds_map">Map-Like Containers (std::map, DenseMap, etc)</a> |
| 1129 | </div> |
| 1130 | |
| 1131 | <div class="doc_text"> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1132 | Map-like containers are useful when you want to associate data to a key. As |
| 1133 | usual, there are a lot of different ways to do this. :) |
| 1134 | </div> |
| 1135 | |
| 1136 | <!-- _______________________________________________________________________ --> |
| 1137 | <div class="doc_subsubsection"> |
| 1138 | <a name="dss_sortedvectormap">A sorted 'vector'</a> |
| 1139 | </div> |
| 1140 | |
| 1141 | <div class="doc_text"> |
| 1142 | |
| 1143 | <p> |
| 1144 | If your usage pattern follows a strict insert-then-query approach, you can |
| 1145 | trivially use the same approach as <a href="#dss_sortedvectorset">sorted vectors |
| 1146 | for set-like containers</a>. The only difference is that your query function |
| 1147 | (which uses std::lower_bound to get efficient log(n) lookup) should only compare |
| 1148 | the key, not both the key and value. This yields the same advantages as sorted |
| 1149 | vectors for sets. |
| 1150 | </p> |
| 1151 | </div> |
| 1152 | |
| 1153 | <!-- _______________________________________________________________________ --> |
| 1154 | <div class="doc_subsubsection"> |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1155 | <a name="dss_stringmap">"llvm/ADT/StringMap.h"</a> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1156 | </div> |
| 1157 | |
| 1158 | <div class="doc_text"> |
| 1159 | |
| 1160 | <p> |
| 1161 | Strings are commonly used as keys in maps, and they are difficult to support |
| 1162 | efficiently: they are variable length, inefficient to hash and compare when |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1163 | long, expensive to copy, etc. StringMap is a specialized container designed to |
| 1164 | cope with these issues. It supports mapping an arbitrary range of bytes to an |
| 1165 | arbitrary other object.</p> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1166 | |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1167 | <p>The StringMap implementation uses a quadratically-probed hash table, where |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1168 | the buckets store a pointer to the heap allocated entries (and some other |
| 1169 | stuff). The entries in the map must be heap allocated because the strings are |
| 1170 | variable length. The string data (key) and the element object (value) are |
| 1171 | stored in the same allocation with the string data immediately after the element |
| 1172 | object. This container guarantees the "<tt>(char*)(&Value+1)</tt>" points |
| 1173 | to the key string for a value.</p> |
| 1174 | |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1175 | <p>The StringMap is very fast for several reasons: quadratic probing is very |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1176 | cache efficient for lookups, the hash value of strings in buckets is not |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1177 | recomputed when lookup up an element, StringMap rarely has to touch the |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1178 | memory for unrelated objects when looking up a value (even when hash collisions |
| 1179 | happen), hash table growth does not recompute the hash values for strings |
| 1180 | already in the table, and each pair in the map is store in a single allocation |
| 1181 | (the string data is stored in the same allocation as the Value of a pair).</p> |
| 1182 | |
Chris Lattner | 796f9fa | 2007-02-08 19:14:21 +0000 | [diff] [blame] | 1183 | <p>StringMap also provides query methods that take byte ranges, so it only ever |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1184 | copies a string if a value is inserted into the table.</p> |
| 1185 | </div> |
| 1186 | |
| 1187 | <!-- _______________________________________________________________________ --> |
| 1188 | <div class="doc_subsubsection"> |
| 1189 | <a name="dss_indexedmap">"llvm/ADT/IndexedMap.h"</a> |
| 1190 | </div> |
| 1191 | |
| 1192 | <div class="doc_text"> |
| 1193 | <p> |
| 1194 | IndexedMap is a specialized container for mapping small dense integers (or |
| 1195 | values that can be mapped to small dense integers) to some other type. It is |
| 1196 | internally implemented as a vector with a mapping function that maps the keys to |
| 1197 | the dense integer range. |
| 1198 | </p> |
| 1199 | |
| 1200 | <p> |
| 1201 | This is useful for cases like virtual registers in the LLVM code generator: they |
| 1202 | have a dense mapping that is offset by a compile-time constant (the first |
| 1203 | virtual register ID).</p> |
| 1204 | |
| 1205 | </div> |
| 1206 | |
| 1207 | <!-- _______________________________________________________________________ --> |
| 1208 | <div class="doc_subsubsection"> |
| 1209 | <a name="dss_densemap">"llvm/ADT/DenseMap.h"</a> |
| 1210 | </div> |
| 1211 | |
| 1212 | <div class="doc_text"> |
| 1213 | |
| 1214 | <p> |
| 1215 | DenseMap is a simple quadratically probed hash table. It excels at supporting |
| 1216 | small keys and values: it uses a single allocation to hold all of the pairs that |
| 1217 | are currently inserted in the map. DenseMap is a great way to map pointers to |
| 1218 | pointers, or map other small types to each other. |
| 1219 | </p> |
| 1220 | |
| 1221 | <p> |
| 1222 | There are several aspects of DenseMap that you should be aware of, however. The |
| 1223 | iterators in a densemap are invalidated whenever an insertion occurs, unlike |
| 1224 | map. Also, because DenseMap allocates space for a large number of key/value |
Chris Lattner | a4a264d | 2007-02-03 20:17:53 +0000 | [diff] [blame] | 1225 | pairs (it starts with 64 by default), it will waste a lot of space if your keys |
| 1226 | or values are large. Finally, you must implement a partial specialization of |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1227 | DenseMapKeyInfo for the key that you want, if it isn't already supported. This |
| 1228 | is required to tell DenseMap about two special marker values (which can never be |
Chris Lattner | a4a264d | 2007-02-03 20:17:53 +0000 | [diff] [blame] | 1229 | inserted into the map) that it needs internally.</p> |
Chris Lattner | c572243 | 2007-02-03 19:49:31 +0000 | [diff] [blame] | 1230 | |
| 1231 | </div> |
| 1232 | |
| 1233 | <!-- _______________________________________________________________________ --> |
| 1234 | <div class="doc_subsubsection"> |
| 1235 | <a name="dss_map"><map></a> |
| 1236 | </div> |
| 1237 | |
| 1238 | <div class="doc_text"> |
| 1239 | |
| 1240 | <p> |
| 1241 | std::map has similar characteristics to <a href="#dss_set">std::set</a>: it uses |
| 1242 | a single allocation per pair inserted into the map, it offers log(n) lookup with |
| 1243 | an extremely large constant factor, imposes a space penalty of 3 pointers per |
| 1244 | pair in the map, etc.</p> |
| 1245 | |
| 1246 | <p>std::map is most useful when your keys or values are very large, if you need |
| 1247 | to iterate over the collection in sorted order, or if you need stable iterators |
| 1248 | into the map (i.e. they don't get invalidated if an insertion or deletion of |
| 1249 | another element takes place).</p> |
| 1250 | |
| 1251 | </div> |
| 1252 | |
| 1253 | <!-- _______________________________________________________________________ --> |
| 1254 | <div class="doc_subsubsection"> |
| 1255 | <a name="dss_othermap">Other Map-Like Container Options</a> |
| 1256 | </div> |
| 1257 | |
| 1258 | <div class="doc_text"> |
| 1259 | |
| 1260 | <p> |
| 1261 | The STL provides several other options, such as std::multimap and the various |
| 1262 | "hash_map" like containers (whether from C++ TR1 or from the SGI library).</p> |
| 1263 | |
| 1264 | <p>std::multimap is useful if you want to map a key to multiple values, but has |
| 1265 | all the drawbacks of std::map. A sorted vector or some other approach is almost |
| 1266 | always better.</p> |
| 1267 | |
| 1268 | <p>The various hash_map implementations (exposed portably by |
| 1269 | "llvm/ADT/hash_map") are simple chained hash tables. This algorithm is as |
| 1270 | malloc intensive as std::map (performing an allocation for each element |
| 1271 | inserted, thus having really high constant factors) but (usually) provides O(1) |
| 1272 | insertion/deletion of elements. This can be useful if your elements are large |
| 1273 | (thus making the constant-factor cost relatively low) or if comparisons are |
| 1274 | expensive. Element iteration does not visit elements in a useful order.</p> |
| 1275 | |
Chris Lattner | 098129a | 2007-02-03 03:04:03 +0000 | [diff] [blame] | 1276 | </div> |
| 1277 | |
Chris Lattner | f623a08 | 2005-10-17 01:36:23 +0000 | [diff] [blame] | 1278 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1279 | <!-- *********************************************************************** --> |
| 1280 | <div class="doc_section"> |
| 1281 | <a name="common">Helpful Hints for Common Operations</a> |
| 1282 | </div> |
| 1283 | <!-- *********************************************************************** --> |
| 1284 | |
| 1285 | <div class="doc_text"> |
| 1286 | |
| 1287 | <p>This section describes how to perform some very simple transformations of |
| 1288 | LLVM code. This is meant to give examples of common idioms used, showing the |
| 1289 | practical side of LLVM transformations. <p> Because this is a "how-to" section, |
| 1290 | you should also read about the main classes that you will be working with. The |
| 1291 | <a href="#coreclasses">Core LLVM Class Hierarchy Reference</a> contains details |
| 1292 | and descriptions of the main classes that you should know about.</p> |
| 1293 | |
| 1294 | </div> |
| 1295 | |
| 1296 | <!-- NOTE: this section should be heavy on example code --> |
| 1297 | <!-- ======================================================================= --> |
| 1298 | <div class="doc_subsection"> |
| 1299 | <a name="inspection">Basic Inspection and Traversal Routines</a> |
| 1300 | </div> |
| 1301 | |
| 1302 | <div class="doc_text"> |
| 1303 | |
| 1304 | <p>The LLVM compiler infrastructure have many different data structures that may |
| 1305 | be traversed. Following the example of the C++ standard template library, the |
| 1306 | techniques used to traverse these various data structures are all basically the |
| 1307 | same. For a enumerable sequence of values, the <tt>XXXbegin()</tt> function (or |
| 1308 | method) returns an iterator to the start of the sequence, the <tt>XXXend()</tt> |
| 1309 | function returns an iterator pointing to one past the last valid element of the |
| 1310 | sequence, and there is some <tt>XXXiterator</tt> data type that is common |
| 1311 | between the two operations.</p> |
| 1312 | |
| 1313 | <p>Because the pattern for iteration is common across many different aspects of |
| 1314 | the program representation, the standard template library algorithms may be used |
| 1315 | on them, and it is easier to remember how to iterate. First we show a few common |
| 1316 | examples of the data structures that need to be traversed. Other data |
| 1317 | structures are traversed in very similar ways.</p> |
| 1318 | |
| 1319 | </div> |
| 1320 | |
| 1321 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1322 | <div class="doc_subsubsection"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1323 | <a name="iterate_function">Iterating over the </a><a |
| 1324 | href="#BasicBlock"><tt>BasicBlock</tt></a>s in a <a |
| 1325 | href="#Function"><tt>Function</tt></a> |
| 1326 | </div> |
| 1327 | |
| 1328 | <div class="doc_text"> |
| 1329 | |
| 1330 | <p>It's quite common to have a <tt>Function</tt> instance that you'd like to |
| 1331 | transform in some way; in particular, you'd like to manipulate its |
| 1332 | <tt>BasicBlock</tt>s. To facilitate this, you'll need to iterate over all of |
| 1333 | the <tt>BasicBlock</tt>s that constitute the <tt>Function</tt>. The following is |
| 1334 | an example that prints the name of a <tt>BasicBlock</tt> and the number of |
| 1335 | <tt>Instruction</tt>s it contains:</p> |
| 1336 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1337 | <div class="doc_code"> |
| 1338 | <pre> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1339 | // <i>func is a pointer to a Function instance</i> |
| 1340 | for (Function::iterator i = func->begin(), e = func->end(); i != e; ++i) |
| 1341 | // <i>Print out the name of the basic block if it has one, and then the</i> |
| 1342 | // <i>number of instructions that it contains</i> |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1343 | llvm::cerr << "Basic block (name=" << i->getName() << ") has " |
| 1344 | << i->size() << " instructions.\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1345 | </pre> |
| 1346 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1347 | |
| 1348 | <p>Note that i can be used as if it were a pointer for the purposes of |
Joel Stanley | 9b96c44 | 2002-09-06 21:55:13 +0000 | [diff] [blame] | 1349 | invoking member functions of the <tt>Instruction</tt> class. This is |
| 1350 | because the indirection operator is overloaded for the iterator |
Chris Lattner | 7496ec5 | 2003-08-05 22:54:23 +0000 | [diff] [blame] | 1351 | classes. In the above code, the expression <tt>i->size()</tt> is |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1352 | exactly equivalent to <tt>(*i).size()</tt> just like you'd expect.</p> |
| 1353 | |
| 1354 | </div> |
| 1355 | |
| 1356 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1357 | <div class="doc_subsubsection"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1358 | <a name="iterate_basicblock">Iterating over the </a><a |
| 1359 | href="#Instruction"><tt>Instruction</tt></a>s in a <a |
| 1360 | href="#BasicBlock"><tt>BasicBlock</tt></a> |
| 1361 | </div> |
| 1362 | |
| 1363 | <div class="doc_text"> |
| 1364 | |
| 1365 | <p>Just like when dealing with <tt>BasicBlock</tt>s in <tt>Function</tt>s, it's |
| 1366 | easy to iterate over the individual instructions that make up |
| 1367 | <tt>BasicBlock</tt>s. Here's a code snippet that prints out each instruction in |
| 1368 | a <tt>BasicBlock</tt>:</p> |
| 1369 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1370 | <div class="doc_code"> |
Chris Lattner | 55c0461 | 2005-03-06 06:00:13 +0000 | [diff] [blame] | 1371 | <pre> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1372 | // <i>blk is a pointer to a BasicBlock instance</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1373 | for (BasicBlock::iterator i = blk->begin(), e = blk->end(); i != e; ++i) |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1374 | // <i>The next statement works since operator<<(ostream&,...)</i> |
| 1375 | // <i>is overloaded for Instruction&</i> |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1376 | llvm::cerr << *i << "\n"; |
Chris Lattner | 55c0461 | 2005-03-06 06:00:13 +0000 | [diff] [blame] | 1377 | </pre> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1378 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1379 | |
| 1380 | <p>However, this isn't really the best way to print out the contents of a |
| 1381 | <tt>BasicBlock</tt>! Since the ostream operators are overloaded for virtually |
| 1382 | anything you'll care about, you could have just invoked the print routine on the |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1383 | basic block itself: <tt>llvm::cerr << *blk << "\n";</tt>.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1384 | |
| 1385 | </div> |
| 1386 | |
| 1387 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1388 | <div class="doc_subsubsection"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1389 | <a name="iterate_institer">Iterating over the </a><a |
| 1390 | href="#Instruction"><tt>Instruction</tt></a>s in a <a |
| 1391 | href="#Function"><tt>Function</tt></a> |
| 1392 | </div> |
| 1393 | |
| 1394 | <div class="doc_text"> |
| 1395 | |
| 1396 | <p>If you're finding that you commonly iterate over a <tt>Function</tt>'s |
| 1397 | <tt>BasicBlock</tt>s and then that <tt>BasicBlock</tt>'s <tt>Instruction</tt>s, |
| 1398 | <tt>InstIterator</tt> should be used instead. You'll need to include <a |
| 1399 | href="/doxygen/InstIterator_8h-source.html"><tt>llvm/Support/InstIterator.h</tt></a>, |
| 1400 | and then instantiate <tt>InstIterator</tt>s explicitly in your code. Here's a |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1401 | small example that shows how to dump all instructions in a function to the standard error stream:<p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1402 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1403 | <div class="doc_code"> |
| 1404 | <pre> |
| 1405 | #include "<a href="/doxygen/InstIterator_8h-source.html">llvm/Support/InstIterator.h</a>" |
| 1406 | |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1407 | // <i>F is a pointer to a Function instance</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1408 | for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1409 | llvm::cerr << *i << "\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1410 | </pre> |
| 1411 | </div> |
| 1412 | |
| 1413 | <p>Easy, isn't it? You can also use <tt>InstIterator</tt>s to fill a |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1414 | work list with its initial contents. For example, if you wanted to |
| 1415 | initialize a work list to contain all instructions in a <tt>Function</tt> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1416 | F, all you would need to do is something like:</p> |
| 1417 | |
| 1418 | <div class="doc_code"> |
| 1419 | <pre> |
| 1420 | std::set<Instruction*> worklist; |
| 1421 | worklist.insert(inst_begin(F), inst_end(F)); |
| 1422 | </pre> |
| 1423 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1424 | |
| 1425 | <p>The STL set <tt>worklist</tt> would now contain all instructions in the |
| 1426 | <tt>Function</tt> pointed to by F.</p> |
| 1427 | |
| 1428 | </div> |
| 1429 | |
| 1430 | <!-- _______________________________________________________________________ --> |
| 1431 | <div class="doc_subsubsection"> |
| 1432 | <a name="iterate_convert">Turning an iterator into a class pointer (and |
| 1433 | vice-versa)</a> |
| 1434 | </div> |
| 1435 | |
| 1436 | <div class="doc_text"> |
| 1437 | |
| 1438 | <p>Sometimes, it'll be useful to grab a reference (or pointer) to a class |
Joel Stanley | 9b96c44 | 2002-09-06 21:55:13 +0000 | [diff] [blame] | 1439 | instance when all you've got at hand is an iterator. Well, extracting |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1440 | a reference or a pointer from an iterator is very straight-forward. |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1441 | Assuming that <tt>i</tt> is a <tt>BasicBlock::iterator</tt> and <tt>j</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1442 | is a <tt>BasicBlock::const_iterator</tt>:</p> |
| 1443 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1444 | <div class="doc_code"> |
| 1445 | <pre> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1446 | Instruction& inst = *i; // <i>Grab reference to instruction reference</i> |
| 1447 | Instruction* pinst = &*i; // <i>Grab pointer to instruction reference</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1448 | const Instruction& inst = *j; |
| 1449 | </pre> |
| 1450 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1451 | |
| 1452 | <p>However, the iterators you'll be working with in the LLVM framework are |
| 1453 | special: they will automatically convert to a ptr-to-instance type whenever they |
| 1454 | need to. Instead of dereferencing the iterator and then taking the address of |
| 1455 | the result, you can simply assign the iterator to the proper pointer type and |
| 1456 | you get the dereference and address-of operation as a result of the assignment |
| 1457 | (behind the scenes, this is a result of overloading casting mechanisms). Thus |
| 1458 | the last line of the last example,</p> |
| 1459 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1460 | <div class="doc_code"> |
| 1461 | <pre> |
| 1462 | Instruction* pinst = &*i; |
| 1463 | </pre> |
| 1464 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1465 | |
| 1466 | <p>is semantically equivalent to</p> |
| 1467 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1468 | <div class="doc_code"> |
| 1469 | <pre> |
| 1470 | Instruction* pinst = i; |
| 1471 | </pre> |
| 1472 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1473 | |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1474 | <p>It's also possible to turn a class pointer into the corresponding iterator, |
| 1475 | and this is a constant time operation (very efficient). The following code |
| 1476 | snippet illustrates use of the conversion constructors provided by LLVM |
| 1477 | iterators. By using these, you can explicitly grab the iterator of something |
| 1478 | without actually obtaining it via iteration over some structure:</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1479 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1480 | <div class="doc_code"> |
| 1481 | <pre> |
| 1482 | void printNextInstruction(Instruction* inst) { |
| 1483 | BasicBlock::iterator it(inst); |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1484 | ++it; // <i>After this line, it refers to the instruction after *inst</i> |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1485 | if (it != inst->getParent()->end()) llvm::cerr << *it << "\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1486 | } |
| 1487 | </pre> |
| 1488 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1489 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1490 | </div> |
| 1491 | |
| 1492 | <!--_______________________________________________________________________--> |
| 1493 | <div class="doc_subsubsection"> |
| 1494 | <a name="iterate_complex">Finding call sites: a slightly more complex |
| 1495 | example</a> |
| 1496 | </div> |
| 1497 | |
| 1498 | <div class="doc_text"> |
| 1499 | |
| 1500 | <p>Say that you're writing a FunctionPass and would like to count all the |
| 1501 | locations in the entire module (that is, across every <tt>Function</tt>) where a |
| 1502 | certain function (i.e., some <tt>Function</tt>*) is already in scope. As you'll |
| 1503 | learn later, you may want to use an <tt>InstVisitor</tt> to accomplish this in a |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1504 | much more straight-forward manner, but this example will allow us to explore how |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1505 | you'd do it if you didn't have <tt>InstVisitor</tt> around. In pseudo-code, this |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1506 | is what we want to do:</p> |
| 1507 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1508 | <div class="doc_code"> |
| 1509 | <pre> |
| 1510 | initialize callCounter to zero |
| 1511 | for each Function f in the Module |
| 1512 | for each BasicBlock b in f |
| 1513 | for each Instruction i in b |
| 1514 | if (i is a CallInst and calls the given function) |
| 1515 | increment callCounter |
| 1516 | </pre> |
| 1517 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1518 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1519 | <p>And the actual code is (remember, because we're writing a |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1520 | <tt>FunctionPass</tt>, our <tt>FunctionPass</tt>-derived class simply has to |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1521 | override the <tt>runOnFunction</tt> method):</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1522 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1523 | <div class="doc_code"> |
| 1524 | <pre> |
| 1525 | Function* targetFunc = ...; |
| 1526 | |
| 1527 | class OurFunctionPass : public FunctionPass { |
| 1528 | public: |
| 1529 | OurFunctionPass(): callCounter(0) { } |
| 1530 | |
| 1531 | virtual runOnFunction(Function& F) { |
| 1532 | for (Function::iterator b = F.begin(), be = F.end(); b != be; ++b) { |
| 1533 | for (BasicBlock::iterator i = b->begin(); ie = b->end(); i != ie; ++i) { |
| 1534 | if (<a href="#CallInst">CallInst</a>* callInst = <a href="#isa">dyn_cast</a><<a |
| 1535 | href="#CallInst">CallInst</a>>(&*i)) { |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1536 | // <i>We know we've encountered a call instruction, so we</i> |
| 1537 | // <i>need to determine if it's a call to the</i> |
| 1538 | // <i>function pointed to by m_func or not</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1539 | |
| 1540 | if (callInst->getCalledFunction() == targetFunc) |
| 1541 | ++callCounter; |
| 1542 | } |
| 1543 | } |
| 1544 | } |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1545 | } |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1546 | |
| 1547 | private: |
| 1548 | unsigned callCounter; |
| 1549 | }; |
| 1550 | </pre> |
| 1551 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1552 | |
| 1553 | </div> |
| 1554 | |
Brian Gaeke | f1972c6 | 2003-11-07 19:25:45 +0000 | [diff] [blame] | 1555 | <!--_______________________________________________________________________--> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1556 | <div class="doc_subsubsection"> |
| 1557 | <a name="calls_and_invokes">Treating calls and invokes the same way</a> |
| 1558 | </div> |
| 1559 | |
| 1560 | <div class="doc_text"> |
| 1561 | |
| 1562 | <p>You may have noticed that the previous example was a bit oversimplified in |
| 1563 | that it did not deal with call sites generated by 'invoke' instructions. In |
| 1564 | this, and in other situations, you may find that you want to treat |
| 1565 | <tt>CallInst</tt>s and <tt>InvokeInst</tt>s the same way, even though their |
| 1566 | most-specific common base class is <tt>Instruction</tt>, which includes lots of |
| 1567 | less closely-related things. For these cases, LLVM provides a handy wrapper |
| 1568 | class called <a |
Reid Spencer | 05fe4b0 | 2006-03-14 05:39:39 +0000 | [diff] [blame] | 1569 | href="http://llvm.org/doxygen/classllvm_1_1CallSite.html"><tt>CallSite</tt></a>. |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1570 | It is essentially a wrapper around an <tt>Instruction</tt> pointer, with some |
| 1571 | methods that provide functionality common to <tt>CallInst</tt>s and |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1572 | <tt>InvokeInst</tt>s.</p> |
| 1573 | |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1574 | <p>This class has "value semantics": it should be passed by value, not by |
| 1575 | reference and it should not be dynamically allocated or deallocated using |
| 1576 | <tt>operator new</tt> or <tt>operator delete</tt>. It is efficiently copyable, |
| 1577 | assignable and constructable, with costs equivalents to that of a bare pointer. |
| 1578 | If you look at its definition, it has only a single pointer member.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1579 | |
| 1580 | </div> |
| 1581 | |
Chris Lattner | 1a3105b | 2002-09-09 05:49:39 +0000 | [diff] [blame] | 1582 | <!--_______________________________________________________________________--> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1583 | <div class="doc_subsubsection"> |
| 1584 | <a name="iterate_chains">Iterating over def-use & use-def chains</a> |
| 1585 | </div> |
| 1586 | |
| 1587 | <div class="doc_text"> |
| 1588 | |
| 1589 | <p>Frequently, we might have an instance of the <a |
Chris Lattner | 0081517 | 2007-01-04 22:01:45 +0000 | [diff] [blame] | 1590 | href="/doxygen/classllvm_1_1Value.html">Value Class</a> and we want to |
Misha Brukman | 384047f | 2004-06-03 23:29:12 +0000 | [diff] [blame] | 1591 | determine which <tt>User</tt>s use the <tt>Value</tt>. The list of all |
| 1592 | <tt>User</tt>s of a particular <tt>Value</tt> is called a <i>def-use</i> chain. |
| 1593 | For example, let's say we have a <tt>Function*</tt> named <tt>F</tt> to a |
| 1594 | particular function <tt>foo</tt>. Finding all of the instructions that |
| 1595 | <i>use</i> <tt>foo</tt> is as simple as iterating over the <i>def-use</i> chain |
| 1596 | of <tt>F</tt>:</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1597 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1598 | <div class="doc_code"> |
| 1599 | <pre> |
| 1600 | Function* F = ...; |
| 1601 | |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1602 | for (Value::use_iterator i = F->use_begin(), e = F->use_end(); i != e; ++i) |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1603 | if (Instruction *Inst = dyn_cast<Instruction>(*i)) { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 1604 | llvm::cerr << "F is used in instruction:\n"; |
| 1605 | llvm::cerr << *Inst << "\n"; |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1606 | } |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1607 | </pre> |
| 1608 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1609 | |
| 1610 | <p>Alternately, it's common to have an instance of the <a |
Misha Brukman | 384047f | 2004-06-03 23:29:12 +0000 | [diff] [blame] | 1611 | href="/doxygen/classllvm_1_1User.html">User Class</a> and need to know what |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1612 | <tt>Value</tt>s are used by it. The list of all <tt>Value</tt>s used by a |
| 1613 | <tt>User</tt> is known as a <i>use-def</i> chain. Instances of class |
| 1614 | <tt>Instruction</tt> are common <tt>User</tt>s, so we might want to iterate over |
| 1615 | all of the values that a particular instruction uses (that is, the operands of |
| 1616 | the particular <tt>Instruction</tt>):</p> |
| 1617 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1618 | <div class="doc_code"> |
| 1619 | <pre> |
| 1620 | Instruction* pi = ...; |
| 1621 | |
| 1622 | for (User::op_iterator i = pi->op_begin(), e = pi->op_end(); i != e; ++i) { |
| 1623 | Value* v = *i; |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1624 | // <i>...</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1625 | } |
| 1626 | </pre> |
| 1627 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1628 | |
Chris Lattner | 1a3105b | 2002-09-09 05:49:39 +0000 | [diff] [blame] | 1629 | <!-- |
| 1630 | def-use chains ("finding all users of"): Value::use_begin/use_end |
| 1631 | use-def chains ("finding all values used"): User::op_begin/op_end [op=operand] |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1632 | --> |
| 1633 | |
| 1634 | </div> |
| 1635 | |
| 1636 | <!-- ======================================================================= --> |
| 1637 | <div class="doc_subsection"> |
| 1638 | <a name="simplechanges">Making simple changes</a> |
| 1639 | </div> |
| 1640 | |
| 1641 | <div class="doc_text"> |
| 1642 | |
| 1643 | <p>There are some primitive transformation operations present in the LLVM |
Joel Stanley | 753eb71 | 2002-09-11 22:32:24 +0000 | [diff] [blame] | 1644 | infrastructure that are worth knowing about. When performing |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1645 | transformations, it's fairly common to manipulate the contents of basic |
| 1646 | blocks. This section describes some of the common methods for doing so |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1647 | and gives example code.</p> |
| 1648 | |
| 1649 | </div> |
| 1650 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1651 | <!--_______________________________________________________________________--> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1652 | <div class="doc_subsubsection"> |
| 1653 | <a name="schanges_creating">Creating and inserting new |
| 1654 | <tt>Instruction</tt>s</a> |
| 1655 | </div> |
| 1656 | |
| 1657 | <div class="doc_text"> |
| 1658 | |
| 1659 | <p><i>Instantiating Instructions</i></p> |
| 1660 | |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1661 | <p>Creation of <tt>Instruction</tt>s is straight-forward: simply call the |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1662 | constructor for the kind of instruction to instantiate and provide the necessary |
| 1663 | parameters. For example, an <tt>AllocaInst</tt> only <i>requires</i> a |
| 1664 | (const-ptr-to) <tt>Type</tt>. Thus:</p> |
| 1665 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1666 | <div class="doc_code"> |
| 1667 | <pre> |
| 1668 | AllocaInst* ai = new AllocaInst(Type::IntTy); |
| 1669 | </pre> |
| 1670 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1671 | |
| 1672 | <p>will create an <tt>AllocaInst</tt> instance that represents the allocation of |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1673 | one integer in the current stack frame, at run time. Each <tt>Instruction</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1674 | subclass is likely to have varying default parameters which change the semantics |
| 1675 | of the instruction, so refer to the <a |
Misha Brukman | 31ca1de | 2004-06-03 23:35:54 +0000 | [diff] [blame] | 1676 | href="/doxygen/classllvm_1_1Instruction.html">doxygen documentation for the subclass of |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1677 | Instruction</a> that you're interested in instantiating.</p> |
| 1678 | |
| 1679 | <p><i>Naming values</i></p> |
| 1680 | |
| 1681 | <p>It is very useful to name the values of instructions when you're able to, as |
| 1682 | this facilitates the debugging of your transformations. If you end up looking |
| 1683 | at generated LLVM machine code, you definitely want to have logical names |
| 1684 | associated with the results of instructions! By supplying a value for the |
| 1685 | <tt>Name</tt> (default) parameter of the <tt>Instruction</tt> constructor, you |
| 1686 | associate a logical name with the result of the instruction's execution at |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1687 | run time. For example, say that I'm writing a transformation that dynamically |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1688 | allocates space for an integer on the stack, and that integer is going to be |
| 1689 | used as some kind of index by some other code. To accomplish this, I place an |
| 1690 | <tt>AllocaInst</tt> at the first point in the first <tt>BasicBlock</tt> of some |
| 1691 | <tt>Function</tt>, and I'm intending to use it within the same |
| 1692 | <tt>Function</tt>. I might do:</p> |
| 1693 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1694 | <div class="doc_code"> |
| 1695 | <pre> |
| 1696 | AllocaInst* pa = new AllocaInst(Type::IntTy, 0, "indexLoc"); |
| 1697 | </pre> |
| 1698 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1699 | |
| 1700 | <p>where <tt>indexLoc</tt> is now the logical name of the instruction's |
Reid Spencer | 128a7a7 | 2007-02-03 21:06:43 +0000 | [diff] [blame] | 1701 | execution value, which is a pointer to an integer on the run time stack.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1702 | |
| 1703 | <p><i>Inserting instructions</i></p> |
| 1704 | |
| 1705 | <p>There are essentially two ways to insert an <tt>Instruction</tt> |
| 1706 | into an existing sequence of instructions that form a <tt>BasicBlock</tt>:</p> |
| 1707 | |
Joel Stanley | 9dd1ad6 | 2002-09-18 03:17:23 +0000 | [diff] [blame] | 1708 | <ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1709 | <li>Insertion into an explicit instruction list |
| 1710 | |
| 1711 | <p>Given a <tt>BasicBlock* pb</tt>, an <tt>Instruction* pi</tt> within that |
| 1712 | <tt>BasicBlock</tt>, and a newly-created instruction we wish to insert |
| 1713 | before <tt>*pi</tt>, we do the following: </p> |
| 1714 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1715 | <div class="doc_code"> |
| 1716 | <pre> |
| 1717 | BasicBlock *pb = ...; |
| 1718 | Instruction *pi = ...; |
| 1719 | Instruction *newInst = new Instruction(...); |
| 1720 | |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1721 | pb->getInstList().insert(pi, newInst); // <i>Inserts newInst before pi in pb</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1722 | </pre> |
| 1723 | </div> |
Alkis Evlogimenos | 9a5dc4f | 2004-05-27 00:57:51 +0000 | [diff] [blame] | 1724 | |
| 1725 | <p>Appending to the end of a <tt>BasicBlock</tt> is so common that |
| 1726 | the <tt>Instruction</tt> class and <tt>Instruction</tt>-derived |
| 1727 | classes provide constructors which take a pointer to a |
| 1728 | <tt>BasicBlock</tt> to be appended to. For example code that |
| 1729 | looked like: </p> |
| 1730 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1731 | <div class="doc_code"> |
| 1732 | <pre> |
| 1733 | BasicBlock *pb = ...; |
| 1734 | Instruction *newInst = new Instruction(...); |
| 1735 | |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1736 | pb->getInstList().push_back(newInst); // <i>Appends newInst to pb</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1737 | </pre> |
| 1738 | </div> |
Alkis Evlogimenos | 9a5dc4f | 2004-05-27 00:57:51 +0000 | [diff] [blame] | 1739 | |
| 1740 | <p>becomes: </p> |
| 1741 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1742 | <div class="doc_code"> |
| 1743 | <pre> |
| 1744 | BasicBlock *pb = ...; |
| 1745 | Instruction *newInst = new Instruction(..., pb); |
| 1746 | </pre> |
| 1747 | </div> |
Alkis Evlogimenos | 9a5dc4f | 2004-05-27 00:57:51 +0000 | [diff] [blame] | 1748 | |
| 1749 | <p>which is much cleaner, especially if you are creating |
| 1750 | long instruction streams.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1751 | |
| 1752 | <li>Insertion into an implicit instruction list |
| 1753 | |
| 1754 | <p><tt>Instruction</tt> instances that are already in <tt>BasicBlock</tt>s |
| 1755 | are implicitly associated with an existing instruction list: the instruction |
| 1756 | list of the enclosing basic block. Thus, we could have accomplished the same |
| 1757 | thing as the above code without being given a <tt>BasicBlock</tt> by doing: |
| 1758 | </p> |
| 1759 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1760 | <div class="doc_code"> |
| 1761 | <pre> |
| 1762 | Instruction *pi = ...; |
| 1763 | Instruction *newInst = new Instruction(...); |
| 1764 | |
| 1765 | pi->getParent()->getInstList().insert(pi, newInst); |
| 1766 | </pre> |
| 1767 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1768 | |
| 1769 | <p>In fact, this sequence of steps occurs so frequently that the |
| 1770 | <tt>Instruction</tt> class and <tt>Instruction</tt>-derived classes provide |
| 1771 | constructors which take (as a default parameter) a pointer to an |
| 1772 | <tt>Instruction</tt> which the newly-created <tt>Instruction</tt> should |
| 1773 | precede. That is, <tt>Instruction</tt> constructors are capable of |
| 1774 | inserting the newly-created instance into the <tt>BasicBlock</tt> of a |
| 1775 | provided instruction, immediately before that instruction. Using an |
| 1776 | <tt>Instruction</tt> constructor with a <tt>insertBefore</tt> (default) |
| 1777 | parameter, the above code becomes:</p> |
| 1778 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1779 | <div class="doc_code"> |
| 1780 | <pre> |
| 1781 | Instruction* pi = ...; |
| 1782 | Instruction* newInst = new Instruction(..., pi); |
| 1783 | </pre> |
| 1784 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1785 | |
| 1786 | <p>which is much cleaner, especially if you're creating a lot of |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1787 | instructions and adding them to <tt>BasicBlock</tt>s.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1788 | </ul> |
| 1789 | |
| 1790 | </div> |
| 1791 | |
| 1792 | <!--_______________________________________________________________________--> |
| 1793 | <div class="doc_subsubsection"> |
| 1794 | <a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a> |
| 1795 | </div> |
| 1796 | |
| 1797 | <div class="doc_text"> |
| 1798 | |
| 1799 | <p>Deleting an instruction from an existing sequence of instructions that form a |
Chris Lattner | 69bf8a9 | 2004-05-23 21:06:58 +0000 | [diff] [blame] | 1800 | <a href="#BasicBlock"><tt>BasicBlock</tt></a> is very straight-forward. First, |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1801 | you must have a pointer to the instruction that you wish to delete. Second, you |
| 1802 | need to obtain the pointer to that instruction's basic block. You use the |
| 1803 | pointer to the basic block to get its list of instructions and then use the |
| 1804 | erase function to remove your instruction. For example:</p> |
| 1805 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1806 | <div class="doc_code"> |
| 1807 | <pre> |
| 1808 | <a href="#Instruction">Instruction</a> *I = .. ; |
| 1809 | <a href="#BasicBlock">BasicBlock</a> *BB = I->getParent(); |
| 1810 | |
| 1811 | BB->getInstList().erase(I); |
| 1812 | </pre> |
| 1813 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1814 | |
| 1815 | </div> |
| 1816 | |
| 1817 | <!--_______________________________________________________________________--> |
| 1818 | <div class="doc_subsubsection"> |
| 1819 | <a name="schanges_replacing">Replacing an <tt>Instruction</tt> with another |
| 1820 | <tt>Value</tt></a> |
| 1821 | </div> |
| 1822 | |
| 1823 | <div class="doc_text"> |
| 1824 | |
| 1825 | <p><i>Replacing individual instructions</i></p> |
| 1826 | |
| 1827 | <p>Including "<a href="/doxygen/BasicBlockUtils_8h-source.html">llvm/Transforms/Utils/BasicBlockUtils.h</a>" |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1828 | permits use of two very useful replace functions: <tt>ReplaceInstWithValue</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1829 | and <tt>ReplaceInstWithInst</tt>.</p> |
| 1830 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1831 | <h4><a name="schanges_deleting">Deleting <tt>Instruction</tt>s</a></h4> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1832 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1833 | <ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1834 | <li><tt>ReplaceInstWithValue</tt> |
| 1835 | |
| 1836 | <p>This function replaces all uses (within a basic block) of a given |
| 1837 | instruction with a value, and then removes the original instruction. The |
| 1838 | following example illustrates the replacement of the result of a particular |
Chris Lattner | 5836082 | 2005-01-17 00:12:04 +0000 | [diff] [blame] | 1839 | <tt>AllocaInst</tt> that allocates memory for a single integer with a null |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1840 | pointer to an integer.</p> |
| 1841 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1842 | <div class="doc_code"> |
| 1843 | <pre> |
| 1844 | AllocaInst* instToReplace = ...; |
| 1845 | BasicBlock::iterator ii(instToReplace); |
| 1846 | |
| 1847 | ReplaceInstWithValue(instToReplace->getParent()->getInstList(), ii, |
| 1848 | Constant::getNullValue(PointerType::get(Type::IntTy))); |
| 1849 | </pre></div></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1850 | |
| 1851 | <li><tt>ReplaceInstWithInst</tt> |
| 1852 | |
| 1853 | <p>This function replaces a particular instruction with another |
| 1854 | instruction. The following example illustrates the replacement of one |
| 1855 | <tt>AllocaInst</tt> with another.</p> |
| 1856 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1857 | <div class="doc_code"> |
| 1858 | <pre> |
| 1859 | AllocaInst* instToReplace = ...; |
| 1860 | BasicBlock::iterator ii(instToReplace); |
| 1861 | |
| 1862 | ReplaceInstWithInst(instToReplace->getParent()->getInstList(), ii, |
| 1863 | new AllocaInst(Type::IntTy, 0, "ptrToReplacedInt")); |
| 1864 | </pre></div></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 1865 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1866 | |
| 1867 | <p><i>Replacing multiple uses of <tt>User</tt>s and <tt>Value</tt>s</i></p> |
| 1868 | |
| 1869 | <p>You can use <tt>Value::replaceAllUsesWith</tt> and |
| 1870 | <tt>User::replaceUsesOfWith</tt> to change more than one use at a time. See the |
Chris Lattner | 0081517 | 2007-01-04 22:01:45 +0000 | [diff] [blame] | 1871 | doxygen documentation for the <a href="/doxygen/classllvm_1_1Value.html">Value Class</a> |
Misha Brukman | 384047f | 2004-06-03 23:29:12 +0000 | [diff] [blame] | 1872 | and <a href="/doxygen/classllvm_1_1User.html">User Class</a>, respectively, for more |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1873 | information.</p> |
| 1874 | |
| 1875 | <!-- Value::replaceAllUsesWith User::replaceUsesOfWith Point out: |
| 1876 | include/llvm/Transforms/Utils/ especially BasicBlockUtils.h with: |
| 1877 | ReplaceInstWithValue, ReplaceInstWithInst --> |
| 1878 | |
| 1879 | </div> |
| 1880 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 1881 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 1882 | <div class="doc_section"> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 1883 | <a name="advanced">Advanced Topics</a> |
| 1884 | </div> |
| 1885 | <!-- *********************************************************************** --> |
| 1886 | |
| 1887 | <div class="doc_text"> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1888 | <p> |
| 1889 | This section describes some of the advanced or obscure API's that most clients |
| 1890 | do not need to be aware of. These API's tend manage the inner workings of the |
| 1891 | LLVM system, and only need to be accessed in unusual circumstances. |
| 1892 | </p> |
| 1893 | </div> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 1894 | |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1895 | <!-- ======================================================================= --> |
| 1896 | <div class="doc_subsection"> |
| 1897 | <a name="TypeResolve">LLVM Type Resolution</a> |
| 1898 | </div> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 1899 | |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1900 | <div class="doc_text"> |
| 1901 | |
| 1902 | <p> |
| 1903 | The LLVM type system has a very simple goal: allow clients to compare types for |
| 1904 | structural equality with a simple pointer comparison (aka a shallow compare). |
| 1905 | This goal makes clients much simpler and faster, and is used throughout the LLVM |
| 1906 | system. |
| 1907 | </p> |
| 1908 | |
| 1909 | <p> |
| 1910 | Unfortunately achieving this goal is not a simple matter. In particular, |
| 1911 | recursive types and late resolution of opaque types makes the situation very |
| 1912 | difficult to handle. Fortunately, for the most part, our implementation makes |
| 1913 | most clients able to be completely unaware of the nasty internal details. The |
| 1914 | primary case where clients are exposed to the inner workings of it are when |
| 1915 | building a recursive type. In addition to this case, the LLVM bytecode reader, |
| 1916 | assembly parser, and linker also have to be aware of the inner workings of this |
| 1917 | system. |
| 1918 | </p> |
| 1919 | |
Chris Lattner | 0f876db | 2005-04-25 15:47:57 +0000 | [diff] [blame] | 1920 | <p> |
| 1921 | For our purposes below, we need three concepts. First, an "Opaque Type" is |
| 1922 | exactly as defined in the <a href="LangRef.html#t_opaque">language |
| 1923 | reference</a>. Second an "Abstract Type" is any type which includes an |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 1924 | opaque type as part of its type graph (for example "<tt>{ opaque, i32 }</tt>"). |
| 1925 | Third, a concrete type is a type that is not an abstract type (e.g. "<tt>{ i32, |
Chris Lattner | 0f876db | 2005-04-25 15:47:57 +0000 | [diff] [blame] | 1926 | float }</tt>"). |
| 1927 | </p> |
| 1928 | |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1929 | </div> |
| 1930 | |
| 1931 | <!-- ______________________________________________________________________ --> |
| 1932 | <div class="doc_subsubsection"> |
| 1933 | <a name="BuildRecType">Basic Recursive Type Construction</a> |
| 1934 | </div> |
| 1935 | |
| 1936 | <div class="doc_text"> |
| 1937 | |
| 1938 | <p> |
| 1939 | Because the most common question is "how do I build a recursive type with LLVM", |
| 1940 | we answer it now and explain it as we go. Here we include enough to cause this |
| 1941 | to be emitted to an output .ll file: |
| 1942 | </p> |
| 1943 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1944 | <div class="doc_code"> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1945 | <pre> |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 1946 | %mylist = type { %mylist*, i32 } |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1947 | </pre> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1948 | </div> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1949 | |
| 1950 | <p> |
| 1951 | To build this, use the following LLVM APIs: |
| 1952 | </p> |
| 1953 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1954 | <div class="doc_code"> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1955 | <pre> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1956 | // <i>Create the initial outer struct</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1957 | <a href="#PATypeHolder">PATypeHolder</a> StructTy = OpaqueType::get(); |
| 1958 | std::vector<const Type*> Elts; |
| 1959 | Elts.push_back(PointerType::get(StructTy)); |
| 1960 | Elts.push_back(Type::IntTy); |
| 1961 | StructType *NewSTy = StructType::get(Elts); |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1962 | |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 1963 | // <i>At this point, NewSTy = "{ opaque*, i32 }". Tell VMCore that</i> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1964 | // <i>the struct and the opaque type are actually the same.</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1965 | cast<OpaqueType>(StructTy.get())-><a href="#refineAbstractTypeTo">refineAbstractTypeTo</a>(NewSTy); |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1966 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1967 | // <i>NewSTy is potentially invalidated, but StructTy (a <a href="#PATypeHolder">PATypeHolder</a>) is</i> |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1968 | // <i>kept up-to-date</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1969 | NewSTy = cast<StructType>(StructTy.get()); |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1970 | |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 1971 | // <i>Add a name for the type to the module symbol table (optional)</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1972 | MyModule->addTypeName("mylist", NewSTy); |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1973 | </pre> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 1974 | </div> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1975 | |
| 1976 | <p> |
| 1977 | This code shows the basic approach used to build recursive types: build a |
| 1978 | non-recursive type using 'opaque', then use type unification to close the cycle. |
| 1979 | The type unification step is performed by the <tt><a |
Chris Lattner | aff26d1 | 2007-02-03 03:06:52 +0000 | [diff] [blame] | 1980 | href="#refineAbstractTypeTo">refineAbstractTypeTo</a></tt> method, which is |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 1981 | described next. After that, we describe the <a |
| 1982 | href="#PATypeHolder">PATypeHolder class</a>. |
| 1983 | </p> |
| 1984 | |
| 1985 | </div> |
| 1986 | |
| 1987 | <!-- ______________________________________________________________________ --> |
| 1988 | <div class="doc_subsubsection"> |
| 1989 | <a name="refineAbstractTypeTo">The <tt>refineAbstractTypeTo</tt> method</a> |
| 1990 | </div> |
| 1991 | |
| 1992 | <div class="doc_text"> |
| 1993 | <p> |
| 1994 | The <tt>refineAbstractTypeTo</tt> method starts the type unification process. |
| 1995 | While this method is actually a member of the DerivedType class, it is most |
| 1996 | often used on OpaqueType instances. Type unification is actually a recursive |
| 1997 | process. After unification, types can become structurally isomorphic to |
| 1998 | existing types, and all duplicates are deleted (to preserve pointer equality). |
| 1999 | </p> |
| 2000 | |
| 2001 | <p> |
| 2002 | In the example above, the OpaqueType object is definitely deleted. |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 2003 | Additionally, if there is an "{ \2*, i32}" type already created in the system, |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 2004 | the pointer and struct type created are <b>also</b> deleted. Obviously whenever |
| 2005 | a type is deleted, any "Type*" pointers in the program are invalidated. As |
| 2006 | such, it is safest to avoid having <i>any</i> "Type*" pointers to abstract types |
| 2007 | live across a call to <tt>refineAbstractTypeTo</tt> (note that non-abstract |
| 2008 | types can never move or be deleted). To deal with this, the <a |
| 2009 | href="#PATypeHolder">PATypeHolder</a> class is used to maintain a stable |
| 2010 | reference to a possibly refined type, and the <a |
| 2011 | href="#AbstractTypeUser">AbstractTypeUser</a> class is used to update more |
| 2012 | complex datastructures. |
| 2013 | </p> |
| 2014 | |
| 2015 | </div> |
| 2016 | |
| 2017 | <!-- ______________________________________________________________________ --> |
| 2018 | <div class="doc_subsubsection"> |
| 2019 | <a name="PATypeHolder">The PATypeHolder Class</a> |
| 2020 | </div> |
| 2021 | |
| 2022 | <div class="doc_text"> |
| 2023 | <p> |
| 2024 | PATypeHolder is a form of a "smart pointer" for Type objects. When VMCore |
| 2025 | happily goes about nuking types that become isomorphic to existing types, it |
| 2026 | automatically updates all PATypeHolder objects to point to the new type. In the |
| 2027 | example above, this allows the code to maintain a pointer to the resultant |
| 2028 | resolved recursive type, even though the Type*'s are potentially invalidated. |
| 2029 | </p> |
| 2030 | |
| 2031 | <p> |
| 2032 | PATypeHolder is an extremely light-weight object that uses a lazy union-find |
| 2033 | implementation to update pointers. For example the pointer from a Value to its |
| 2034 | Type is maintained by PATypeHolder objects. |
| 2035 | </p> |
| 2036 | |
| 2037 | </div> |
| 2038 | |
| 2039 | <!-- ______________________________________________________________________ --> |
| 2040 | <div class="doc_subsubsection"> |
| 2041 | <a name="AbstractTypeUser">The AbstractTypeUser Class</a> |
| 2042 | </div> |
| 2043 | |
| 2044 | <div class="doc_text"> |
| 2045 | |
| 2046 | <p> |
| 2047 | Some data structures need more to perform more complex updates when types get |
| 2048 | resolved. The <a href="#SymbolTable">SymbolTable</a> class, for example, needs |
| 2049 | move and potentially merge type planes in its representation when a pointer |
| 2050 | changes.</p> |
| 2051 | |
| 2052 | <p> |
| 2053 | To support this, a class can derive from the AbstractTypeUser class. This class |
| 2054 | allows it to get callbacks when certain types are resolved. To register to get |
| 2055 | callbacks for a particular type, the DerivedType::{add/remove}AbstractTypeUser |
Chris Lattner | 0f876db | 2005-04-25 15:47:57 +0000 | [diff] [blame] | 2056 | methods can be called on a type. Note that these methods only work for <i> |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 2057 | abstract</i> types. Concrete types (those that do not include any opaque |
| 2058 | objects) can never be refined. |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 2059 | </p> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2060 | </div> |
| 2061 | |
| 2062 | |
| 2063 | <!-- ======================================================================= --> |
| 2064 | <div class="doc_subsection"> |
| 2065 | <a name="SymbolTable">The <tt>SymbolTable</tt> class</a> |
| 2066 | </div> |
Chris Lattner | f1b200b | 2005-04-23 17:27:36 +0000 | [diff] [blame] | 2067 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2068 | <div class="doc_text"> |
| 2069 | <p>This class provides a symbol table that the <a |
| 2070 | href="#Function"><tt>Function</tt></a> and <a href="#Module"> |
| 2071 | <tt>Module</tt></a> classes use for naming definitions. The symbol table can |
Reid Spencer | a636224 | 2007-01-07 00:41:39 +0000 | [diff] [blame] | 2072 | provide a name for any <a href="#Value"><tt>Value</tt></a>. |
| 2073 | <tt>SymbolTable</tt> is an abstract data type. It hides the data it contains |
| 2074 | and provides access to it through a controlled interface.</p> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2075 | |
Reid Spencer | a636224 | 2007-01-07 00:41:39 +0000 | [diff] [blame] | 2076 | <p>Note that the <tt>SymbolTable</tt> class should not be directly accessed |
| 2077 | by most clients. It should only be used when iteration over the symbol table |
| 2078 | names themselves are required, which is very special purpose. Note that not |
| 2079 | all LLVM |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2080 | <a href="#Value">Value</a>s have names, and those without names (i.e. they have |
| 2081 | an empty name) do not exist in the symbol table. |
| 2082 | </p> |
| 2083 | |
| 2084 | <p>To use the <tt>SymbolTable</tt> well, you need to understand the |
| 2085 | structure of the information it holds. The class contains two |
| 2086 | <tt>std::map</tt> objects. The first, <tt>pmap</tt>, is a map of |
| 2087 | <tt>Type*</tt> to maps of name (<tt>std::string</tt>) to <tt>Value*</tt>. |
Reid Spencer | a636224 | 2007-01-07 00:41:39 +0000 | [diff] [blame] | 2088 | Thus, Values are stored in two-dimensions and accessed by <tt>Type</tt> and |
| 2089 | name.</p> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2090 | |
| 2091 | <p>The interface of this class provides three basic types of operations: |
| 2092 | <ol> |
| 2093 | <li><em>Accessors</em>. Accessors provide read-only access to information |
| 2094 | such as finding a value for a name with the |
| 2095 | <a href="#SymbolTable_lookup">lookup</a> method.</li> |
| 2096 | <li><em>Mutators</em>. Mutators allow the user to add information to the |
| 2097 | <tt>SymbolTable</tt> with methods like |
| 2098 | <a href="#SymbolTable_insert"><tt>insert</tt></a>.</li> |
| 2099 | <li><em>Iterators</em>. Iterators allow the user to traverse the content |
| 2100 | of the symbol table in well defined ways, such as the method |
Reid Spencer | a636224 | 2007-01-07 00:41:39 +0000 | [diff] [blame] | 2101 | <a href="#SymbolTable_plane_begin"><tt>plane_begin</tt></a>.</li> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2102 | </ol> |
| 2103 | |
| 2104 | <h3>Accessors</h3> |
| 2105 | <dl> |
| 2106 | <dt><tt>Value* lookup(const Type* Ty, const std::string& name) const</tt>: |
| 2107 | </dt> |
| 2108 | <dd>The <tt>lookup</tt> method searches the type plane given by the |
| 2109 | <tt>Ty</tt> parameter for a <tt>Value</tt> with the provided <tt>name</tt>. |
| 2110 | If a suitable <tt>Value</tt> is not found, null is returned.</dd> |
| 2111 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2112 | <dt><tt>bool isEmpty() const</tt>:</dt> |
| 2113 | <dd>This function returns true if both the value and types maps are |
| 2114 | empty</dd> |
| 2115 | </dl> |
| 2116 | |
| 2117 | <h3>Mutators</h3> |
| 2118 | <dl> |
| 2119 | <dt><tt>void insert(Value *Val)</tt>:</dt> |
| 2120 | <dd>This method adds the provided value to the symbol table. The Value must |
| 2121 | have both a name and a type which are extracted and used to place the value |
| 2122 | in the correct type plane under the value's name.</dd> |
| 2123 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2124 | <dt><tt>void remove(Value* Val)</tt>:</dt> |
| 2125 | <dd> This method removes a named value from the symbol table. The |
| 2126 | type and name of the Value are extracted from \p N and used to |
| 2127 | lookup the Value in the correct type plane. If the Value is |
| 2128 | not in the symbol table, this method silently ignores the |
| 2129 | request.</dd> |
| 2130 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2131 | </dl> |
| 2132 | |
| 2133 | <h3>Iteration</h3> |
| 2134 | <p>The following functions describe three types of iterators you can obtain |
| 2135 | the beginning or end of the sequence for both const and non-const. It is |
| 2136 | important to keep track of the different kinds of iterators. There are |
| 2137 | three idioms worth pointing out:</p> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2138 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2139 | <table> |
| 2140 | <tr><th>Units</th><th>Iterator</th><th>Idiom</th></tr> |
| 2141 | <tr> |
| 2142 | <td align="left">Planes Of name/Value maps</td><td>PI</td> |
| 2143 | <td align="left"><pre><tt> |
| 2144 | for (SymbolTable::plane_const_iterator PI = ST.plane_begin(), |
| 2145 | PE = ST.plane_end(); PI != PE; ++PI ) { |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 2146 | PI->first // <i>This is the Type* of the plane</i> |
| 2147 | PI->second // <i>This is the SymbolTable::ValueMap of name/Value pairs</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2148 | } |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2149 | </tt></pre></td> |
| 2150 | </tr> |
| 2151 | <tr> |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2152 | <td align="left">name/Value pairs in a plane</td><td>VI</td> |
| 2153 | <td align="left"><pre><tt> |
| 2154 | for (SymbolTable::value_const_iterator VI = ST.value_begin(SomeType), |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2155 | VE = ST.value_end(SomeType); VI != VE; ++VI ) { |
Bill Wendling | 82e2eea | 2006-10-11 18:00:22 +0000 | [diff] [blame] | 2156 | VI->first // <i>This is the name of the Value</i> |
| 2157 | VI->second // <i>This is the Value* value associated with the name</i> |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2158 | } |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2159 | </tt></pre></td> |
| 2160 | </tr> |
| 2161 | </table> |
| 2162 | |
| 2163 | <p>Using the recommended iterator names and idioms will help you avoid |
| 2164 | making mistakes. Of particular note, make sure that whenever you use |
| 2165 | value_begin(SomeType) that you always compare the resulting iterator |
| 2166 | with value_end(SomeType) not value_end(SomeOtherType) or else you |
| 2167 | will loop infinitely.</p> |
| 2168 | |
| 2169 | <dl> |
| 2170 | |
| 2171 | <dt><tt>plane_iterator plane_begin()</tt>:</dt> |
| 2172 | <dd>Get an iterator that starts at the beginning of the type planes. |
| 2173 | The iterator will iterate over the Type/ValueMap pairs in the |
| 2174 | type planes. </dd> |
| 2175 | |
| 2176 | <dt><tt>plane_const_iterator plane_begin() const</tt>:</dt> |
| 2177 | <dd>Get a const_iterator that starts at the beginning of the type |
| 2178 | planes. The iterator will iterate over the Type/ValueMap pairs |
| 2179 | in the type planes. </dd> |
| 2180 | |
| 2181 | <dt><tt>plane_iterator plane_end()</tt>:</dt> |
| 2182 | <dd>Get an iterator at the end of the type planes. This serves as |
| 2183 | the marker for end of iteration over the type planes.</dd> |
| 2184 | |
| 2185 | <dt><tt>plane_const_iterator plane_end() const</tt>:</dt> |
| 2186 | <dd>Get a const_iterator at the end of the type planes. This serves as |
| 2187 | the marker for end of iteration over the type planes.</dd> |
| 2188 | |
| 2189 | <dt><tt>value_iterator value_begin(const Type *Typ)</tt>:</dt> |
| 2190 | <dd>Get an iterator that starts at the beginning of a type plane. |
| 2191 | The iterator will iterate over the name/value pairs in the type plane. |
| 2192 | Note: The type plane must already exist before using this.</dd> |
| 2193 | |
| 2194 | <dt><tt>value_const_iterator value_begin(const Type *Typ) const</tt>:</dt> |
| 2195 | <dd>Get a const_iterator that starts at the beginning of a type plane. |
| 2196 | The iterator will iterate over the name/value pairs in the type plane. |
| 2197 | Note: The type plane must already exist before using this.</dd> |
| 2198 | |
| 2199 | <dt><tt>value_iterator value_end(const Type *Typ)</tt>:</dt> |
| 2200 | <dd>Get an iterator to the end of a type plane. This serves as the marker |
| 2201 | for end of iteration of the type plane. |
| 2202 | Note: The type plane must already exist before using this.</dd> |
| 2203 | |
| 2204 | <dt><tt>value_const_iterator value_end(const Type *Typ) const</tt>:</dt> |
| 2205 | <dd>Get a const_iterator to the end of a type plane. This serves as the |
| 2206 | marker for end of iteration of the type plane. |
| 2207 | Note: the type plane must already exist before using this.</dd> |
| 2208 | |
Chris Lattner | d9d6e10 | 2005-04-23 16:10:52 +0000 | [diff] [blame] | 2209 | <dt><tt>plane_const_iterator find(const Type* Typ ) const</tt>:</dt> |
| 2210 | <dd>This method returns a plane_const_iterator for iteration over |
| 2211 | the type planes starting at a specific plane, given by \p Ty.</dd> |
| 2212 | |
| 2213 | <dt><tt>plane_iterator find( const Type* Typ </tt>:</dt> |
| 2214 | <dd>This method returns a plane_iterator for iteration over the |
| 2215 | type planes starting at a specific plane, given by \p Ty.</dd> |
| 2216 | |
| 2217 | </dl> |
| 2218 | </div> |
| 2219 | |
| 2220 | |
| 2221 | |
| 2222 | <!-- *********************************************************************** --> |
| 2223 | <div class="doc_section"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2224 | <a name="coreclasses">The Core LLVM Class Hierarchy Reference </a> |
| 2225 | </div> |
| 2226 | <!-- *********************************************************************** --> |
| 2227 | |
| 2228 | <div class="doc_text"> |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 2229 | <p><tt>#include "<a href="/doxygen/Type_8h-source.html">llvm/Type.h</a>"</tt> |
| 2230 | <br>doxygen info: <a href="/doxygen/classllvm_1_1Type.html">Type Class</a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2231 | |
| 2232 | <p>The Core LLVM classes are the primary means of representing the program |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2233 | being inspected or transformed. The core LLVM classes are defined in |
| 2234 | header files in the <tt>include/llvm/</tt> directory, and implemented in |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2235 | the <tt>lib/VMCore</tt> directory.</p> |
| 2236 | |
| 2237 | </div> |
| 2238 | |
| 2239 | <!-- ======================================================================= --> |
| 2240 | <div class="doc_subsection"> |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 2241 | <a name="Type">The <tt>Type</tt> class and Derived Types</a> |
| 2242 | </div> |
| 2243 | |
| 2244 | <div class="doc_text"> |
| 2245 | |
| 2246 | <p><tt>Type</tt> is a superclass of all type classes. Every <tt>Value</tt> has |
| 2247 | a <tt>Type</tt>. <tt>Type</tt> cannot be instantiated directly but only |
| 2248 | through its subclasses. Certain primitive types (<tt>VoidType</tt>, |
| 2249 | <tt>LabelType</tt>, <tt>FloatType</tt> and <tt>DoubleType</tt>) have hidden |
| 2250 | subclasses. They are hidden because they offer no useful functionality beyond |
| 2251 | what the <tt>Type</tt> class offers except to distinguish themselves from |
| 2252 | other subclasses of <tt>Type</tt>.</p> |
| 2253 | <p>All other types are subclasses of <tt>DerivedType</tt>. Types can be |
| 2254 | named, but this is not a requirement. There exists exactly |
| 2255 | one instance of a given shape at any one time. This allows type equality to |
| 2256 | be performed with address equality of the Type Instance. That is, given two |
| 2257 | <tt>Type*</tt> values, the types are identical if the pointers are identical. |
| 2258 | </p> |
| 2259 | </div> |
| 2260 | |
| 2261 | <!-- _______________________________________________________________________ --> |
| 2262 | <div class="doc_subsubsection"> |
| 2263 | <a name="m_Value">Important Public Methods</a> |
| 2264 | </div> |
| 2265 | |
| 2266 | <div class="doc_text"> |
| 2267 | |
| 2268 | <ul> |
Chris Lattner | 8f79df3 | 2007-01-15 01:55:32 +0000 | [diff] [blame] | 2269 | <li><tt>bool isInteger() const</tt>: Returns true for any integer type.</li> |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 2270 | |
| 2271 | <li><tt>bool isFloatingPoint()</tt>: Return true if this is one of the two |
| 2272 | floating point types.</li> |
| 2273 | |
| 2274 | <li><tt>bool isAbstract()</tt>: Return true if the type is abstract (contains |
| 2275 | an OpaqueType anywhere in its definition).</li> |
| 2276 | |
| 2277 | <li><tt>bool isSized()</tt>: Return true if the type has known size. Things |
| 2278 | that don't have a size are abstract types, labels and void.</li> |
| 2279 | |
| 2280 | </ul> |
| 2281 | </div> |
| 2282 | |
| 2283 | <!-- _______________________________________________________________________ --> |
| 2284 | <div class="doc_subsubsection"> |
| 2285 | <a name="m_Value">Important Derived Types</a> |
| 2286 | </div> |
| 2287 | <div class="doc_text"> |
| 2288 | <dl> |
| 2289 | <dt><tt>IntegerType</tt></dt> |
| 2290 | <dd>Subclass of DerivedType that represents integer types of any bit width. |
| 2291 | Any bit width between <tt>IntegerType::MIN_INT_BITS</tt> (1) and |
| 2292 | <tt>IntegerType::MAX_INT_BITS</tt> (~8 million) can be represented. |
| 2293 | <ul> |
| 2294 | <li><tt>static const IntegerType* get(unsigned NumBits)</tt>: get an integer |
| 2295 | type of a specific bit width.</li> |
| 2296 | <li><tt>unsigned getBitWidth() const</tt>: Get the bit width of an integer |
| 2297 | type.</li> |
| 2298 | </ul> |
| 2299 | </dd> |
| 2300 | <dt><tt>SequentialType</tt></dt> |
| 2301 | <dd>This is subclassed by ArrayType and PointerType |
| 2302 | <ul> |
| 2303 | <li><tt>const Type * getElementType() const</tt>: Returns the type of each |
| 2304 | of the elements in the sequential type. </li> |
| 2305 | </ul> |
| 2306 | </dd> |
| 2307 | <dt><tt>ArrayType</tt></dt> |
| 2308 | <dd>This is a subclass of SequentialType and defines the interface for array |
| 2309 | types. |
| 2310 | <ul> |
| 2311 | <li><tt>unsigned getNumElements() const</tt>: Returns the number of |
| 2312 | elements in the array. </li> |
| 2313 | </ul> |
| 2314 | </dd> |
| 2315 | <dt><tt>PointerType</tt></dt> |
Chris Lattner | 302da1e | 2007-02-03 03:05:57 +0000 | [diff] [blame] | 2316 | <dd>Subclass of SequentialType for pointer types.</dd> |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 2317 | <dt><tt>PackedType</tt></dt> |
| 2318 | <dd>Subclass of SequentialType for packed (vector) types. A |
| 2319 | packed type is similar to an ArrayType but is distinguished because it is |
| 2320 | a first class type wherease ArrayType is not. Packed types are used for |
| 2321 | vector operations and are usually small vectors of of an integer or floating |
| 2322 | point type.</dd> |
| 2323 | <dt><tt>StructType</tt></dt> |
| 2324 | <dd>Subclass of DerivedTypes for struct types.</dd> |
| 2325 | <dt><tt>FunctionType</tt></dt> |
| 2326 | <dd>Subclass of DerivedTypes for function types. |
| 2327 | <ul> |
| 2328 | <li><tt>bool isVarArg() const</tt>: Returns true if its a vararg |
| 2329 | function</li> |
| 2330 | <li><tt> const Type * getReturnType() const</tt>: Returns the |
| 2331 | return type of the function.</li> |
| 2332 | <li><tt>const Type * getParamType (unsigned i)</tt>: Returns |
| 2333 | the type of the ith parameter.</li> |
| 2334 | <li><tt> const unsigned getNumParams() const</tt>: Returns the |
| 2335 | number of formal parameters.</li> |
| 2336 | </ul> |
| 2337 | </dd> |
| 2338 | <dt><tt>OpaqueType</tt></dt> |
| 2339 | <dd>Sublcass of DerivedType for abstract types. This class |
| 2340 | defines no content and is used as a placeholder for some other type. Note |
| 2341 | that OpaqueType is used (temporarily) during type resolution for forward |
| 2342 | references of types. Once the referenced type is resolved, the OpaqueType |
| 2343 | is replaced with the actual type. OpaqueType can also be used for data |
| 2344 | abstraction. At link time opaque types can be resolved to actual types |
| 2345 | of the same name.</dd> |
| 2346 | </dl> |
| 2347 | </div> |
| 2348 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2349 | |
| 2350 | |
| 2351 | <!-- ======================================================================= --> |
| 2352 | <div class="doc_subsection"> |
| 2353 | <a name="Module">The <tt>Module</tt> class</a> |
| 2354 | </div> |
| 2355 | |
| 2356 | <div class="doc_text"> |
| 2357 | |
| 2358 | <p><tt>#include "<a |
| 2359 | href="/doxygen/Module_8h-source.html">llvm/Module.h</a>"</tt><br> doxygen info: |
| 2360 | <a href="/doxygen/classllvm_1_1Module.html">Module Class</a></p> |
| 2361 | |
| 2362 | <p>The <tt>Module</tt> class represents the top level structure present in LLVM |
| 2363 | programs. An LLVM module is effectively either a translation unit of the |
| 2364 | original program or a combination of several translation units merged by the |
| 2365 | linker. The <tt>Module</tt> class keeps track of a list of <a |
| 2366 | href="#Function"><tt>Function</tt></a>s, a list of <a |
| 2367 | href="#GlobalVariable"><tt>GlobalVariable</tt></a>s, and a <a |
| 2368 | href="#SymbolTable"><tt>SymbolTable</tt></a>. Additionally, it contains a few |
| 2369 | helpful member functions that try to make common operations easy.</p> |
| 2370 | |
| 2371 | </div> |
| 2372 | |
| 2373 | <!-- _______________________________________________________________________ --> |
| 2374 | <div class="doc_subsubsection"> |
| 2375 | <a name="m_Module">Important Public Members of the <tt>Module</tt> class</a> |
| 2376 | </div> |
| 2377 | |
| 2378 | <div class="doc_text"> |
| 2379 | |
| 2380 | <ul> |
| 2381 | <li><tt>Module::Module(std::string name = "")</tt></li> |
| 2382 | </ul> |
| 2383 | |
| 2384 | <p>Constructing a <a href="#Module">Module</a> is easy. You can optionally |
| 2385 | provide a name for it (probably based on the name of the translation unit).</p> |
| 2386 | |
| 2387 | <ul> |
| 2388 | <li><tt>Module::iterator</tt> - Typedef for function list iterator<br> |
| 2389 | <tt>Module::const_iterator</tt> - Typedef for const_iterator.<br> |
| 2390 | |
| 2391 | <tt>begin()</tt>, <tt>end()</tt> |
| 2392 | <tt>size()</tt>, <tt>empty()</tt> |
| 2393 | |
| 2394 | <p>These are forwarding methods that make it easy to access the contents of |
| 2395 | a <tt>Module</tt> object's <a href="#Function"><tt>Function</tt></a> |
| 2396 | list.</p></li> |
| 2397 | |
| 2398 | <li><tt>Module::FunctionListType &getFunctionList()</tt> |
| 2399 | |
| 2400 | <p> Returns the list of <a href="#Function"><tt>Function</tt></a>s. This is |
| 2401 | necessary to use when you need to update the list or perform a complex |
| 2402 | action that doesn't have a forwarding method.</p> |
| 2403 | |
| 2404 | <p><!-- Global Variable --></p></li> |
| 2405 | </ul> |
| 2406 | |
| 2407 | <hr> |
| 2408 | |
| 2409 | <ul> |
| 2410 | <li><tt>Module::global_iterator</tt> - Typedef for global variable list iterator<br> |
| 2411 | |
| 2412 | <tt>Module::const_global_iterator</tt> - Typedef for const_iterator.<br> |
| 2413 | |
| 2414 | <tt>global_begin()</tt>, <tt>global_end()</tt> |
| 2415 | <tt>global_size()</tt>, <tt>global_empty()</tt> |
| 2416 | |
| 2417 | <p> These are forwarding methods that make it easy to access the contents of |
| 2418 | a <tt>Module</tt> object's <a |
| 2419 | href="#GlobalVariable"><tt>GlobalVariable</tt></a> list.</p></li> |
| 2420 | |
| 2421 | <li><tt>Module::GlobalListType &getGlobalList()</tt> |
| 2422 | |
| 2423 | <p>Returns the list of <a |
| 2424 | href="#GlobalVariable"><tt>GlobalVariable</tt></a>s. This is necessary to |
| 2425 | use when you need to update the list or perform a complex action that |
| 2426 | doesn't have a forwarding method.</p> |
| 2427 | |
| 2428 | <p><!-- Symbol table stuff --> </p></li> |
| 2429 | </ul> |
| 2430 | |
| 2431 | <hr> |
| 2432 | |
| 2433 | <ul> |
| 2434 | <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt> |
| 2435 | |
| 2436 | <p>Return a reference to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> |
| 2437 | for this <tt>Module</tt>.</p> |
| 2438 | |
| 2439 | <p><!-- Convenience methods --></p></li> |
| 2440 | </ul> |
| 2441 | |
| 2442 | <hr> |
| 2443 | |
| 2444 | <ul> |
| 2445 | <li><tt><a href="#Function">Function</a> *getFunction(const std::string |
| 2446 | &Name, const <a href="#FunctionType">FunctionType</a> *Ty)</tt> |
| 2447 | |
| 2448 | <p>Look up the specified function in the <tt>Module</tt> <a |
| 2449 | href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, return |
| 2450 | <tt>null</tt>.</p></li> |
| 2451 | |
| 2452 | <li><tt><a href="#Function">Function</a> *getOrInsertFunction(const |
| 2453 | std::string &Name, const <a href="#FunctionType">FunctionType</a> *T)</tt> |
| 2454 | |
| 2455 | <p>Look up the specified function in the <tt>Module</tt> <a |
| 2456 | href="#SymbolTable"><tt>SymbolTable</tt></a>. If it does not exist, add an |
| 2457 | external declaration for the function and return it.</p></li> |
| 2458 | |
| 2459 | <li><tt>std::string getTypeName(const <a href="#Type">Type</a> *Ty)</tt> |
| 2460 | |
| 2461 | <p>If there is at least one entry in the <a |
| 2462 | href="#SymbolTable"><tt>SymbolTable</tt></a> for the specified <a |
| 2463 | href="#Type"><tt>Type</tt></a>, return it. Otherwise return the empty |
| 2464 | string.</p></li> |
| 2465 | |
| 2466 | <li><tt>bool addTypeName(const std::string &Name, const <a |
| 2467 | href="#Type">Type</a> *Ty)</tt> |
| 2468 | |
| 2469 | <p>Insert an entry in the <a href="#SymbolTable"><tt>SymbolTable</tt></a> |
| 2470 | mapping <tt>Name</tt> to <tt>Ty</tt>. If there is already an entry for this |
| 2471 | name, true is returned and the <a |
| 2472 | href="#SymbolTable"><tt>SymbolTable</tt></a> is not modified.</p></li> |
| 2473 | </ul> |
| 2474 | |
| 2475 | </div> |
| 2476 | |
| 2477 | |
Reid Spencer | 303c4b4 | 2007-01-12 17:26:25 +0000 | [diff] [blame] | 2478 | <!-- ======================================================================= --> |
| 2479 | <div class="doc_subsection"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2480 | <a name="Value">The <tt>Value</tt> class</a> |
| 2481 | </div> |
| 2482 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2483 | <div class="doc_text"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2484 | |
| 2485 | <p><tt>#include "<a href="/doxygen/Value_8h-source.html">llvm/Value.h</a>"</tt> |
| 2486 | <br> |
Chris Lattner | 0081517 | 2007-01-04 22:01:45 +0000 | [diff] [blame] | 2487 | doxygen info: <a href="/doxygen/classllvm_1_1Value.html">Value Class</a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2488 | |
| 2489 | <p>The <tt>Value</tt> class is the most important class in the LLVM Source |
| 2490 | base. It represents a typed value that may be used (among other things) as an |
| 2491 | operand to an instruction. There are many different types of <tt>Value</tt>s, |
| 2492 | such as <a href="#Constant"><tt>Constant</tt></a>s,<a |
| 2493 | href="#Argument"><tt>Argument</tt></a>s. Even <a |
| 2494 | href="#Instruction"><tt>Instruction</tt></a>s and <a |
| 2495 | href="#Function"><tt>Function</tt></a>s are <tt>Value</tt>s.</p> |
| 2496 | |
| 2497 | <p>A particular <tt>Value</tt> may be used many times in the LLVM representation |
| 2498 | for a program. For example, an incoming argument to a function (represented |
| 2499 | with an instance of the <a href="#Argument">Argument</a> class) is "used" by |
| 2500 | every instruction in the function that references the argument. To keep track |
| 2501 | of this relationship, the <tt>Value</tt> class keeps a list of all of the <a |
| 2502 | href="#User"><tt>User</tt></a>s that is using it (the <a |
| 2503 | href="#User"><tt>User</tt></a> class is a base class for all nodes in the LLVM |
| 2504 | graph that can refer to <tt>Value</tt>s). This use list is how LLVM represents |
| 2505 | def-use information in the program, and is accessible through the <tt>use_</tt>* |
| 2506 | methods, shown below.</p> |
| 2507 | |
| 2508 | <p>Because LLVM is a typed representation, every LLVM <tt>Value</tt> is typed, |
| 2509 | and this <a href="#Type">Type</a> is available through the <tt>getType()</tt> |
| 2510 | method. In addition, all LLVM values can be named. The "name" of the |
| 2511 | <tt>Value</tt> is a symbolic string printed in the LLVM code:</p> |
| 2512 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2513 | <div class="doc_code"> |
| 2514 | <pre> |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 2515 | %<b>foo</b> = add i32 1, 2 |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2516 | </pre> |
| 2517 | </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2518 | |
| 2519 | <p><a name="#nameWarning">The name of this instruction is "foo".</a> <b>NOTE</b> |
| 2520 | that the name of any value may be missing (an empty string), so names should |
| 2521 | <b>ONLY</b> be used for debugging (making the source code easier to read, |
| 2522 | debugging printouts), they should not be used to keep track of values or map |
| 2523 | between them. For this purpose, use a <tt>std::map</tt> of pointers to the |
| 2524 | <tt>Value</tt> itself instead.</p> |
| 2525 | |
| 2526 | <p>One important aspect of LLVM is that there is no distinction between an SSA |
| 2527 | variable and the operation that produces it. Because of this, any reference to |
| 2528 | the value produced by an instruction (or the value available as an incoming |
Chris Lattner | d5fc4fc | 2004-03-18 14:58:55 +0000 | [diff] [blame] | 2529 | argument, for example) is represented as a direct pointer to the instance of |
| 2530 | the class that |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2531 | represents this value. Although this may take some getting used to, it |
| 2532 | simplifies the representation and makes it easier to manipulate.</p> |
| 2533 | |
| 2534 | </div> |
| 2535 | |
| 2536 | <!-- _______________________________________________________________________ --> |
| 2537 | <div class="doc_subsubsection"> |
| 2538 | <a name="m_Value">Important Public Members of the <tt>Value</tt> class</a> |
| 2539 | </div> |
| 2540 | |
| 2541 | <div class="doc_text"> |
| 2542 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2543 | <ul> |
| 2544 | <li><tt>Value::use_iterator</tt> - Typedef for iterator over the |
| 2545 | use-list<br> |
| 2546 | <tt>Value::use_const_iterator</tt> - Typedef for const_iterator over |
| 2547 | the use-list<br> |
| 2548 | <tt>unsigned use_size()</tt> - Returns the number of users of the |
| 2549 | value.<br> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 2550 | <tt>bool use_empty()</tt> - Returns true if there are no users.<br> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2551 | <tt>use_iterator use_begin()</tt> - Get an iterator to the start of |
| 2552 | the use-list.<br> |
| 2553 | <tt>use_iterator use_end()</tt> - Get an iterator to the end of the |
| 2554 | use-list.<br> |
| 2555 | <tt><a href="#User">User</a> *use_back()</tt> - Returns the last |
| 2556 | element in the list. |
| 2557 | <p> These methods are the interface to access the def-use |
| 2558 | information in LLVM. As with all other iterators in LLVM, the naming |
| 2559 | conventions follow the conventions defined by the <a href="#stl">STL</a>.</p> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2560 | </li> |
| 2561 | <li><tt><a href="#Type">Type</a> *getType() const</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2562 | <p>This method returns the Type of the Value.</p> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2563 | </li> |
| 2564 | <li><tt>bool hasName() const</tt><br> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 2565 | <tt>std::string getName() const</tt><br> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2566 | <tt>void setName(const std::string &Name)</tt> |
| 2567 | <p> This family of methods is used to access and assign a name to a <tt>Value</tt>, |
| 2568 | be aware of the <a href="#nameWarning">precaution above</a>.</p> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2569 | </li> |
| 2570 | <li><tt>void replaceAllUsesWith(Value *V)</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2571 | |
| 2572 | <p>This method traverses the use list of a <tt>Value</tt> changing all <a |
| 2573 | href="#User"><tt>User</tt>s</a> of the current value to refer to |
| 2574 | "<tt>V</tt>" instead. For example, if you detect that an instruction always |
| 2575 | produces a constant value (for example through constant folding), you can |
| 2576 | replace all uses of the instruction with the constant like this:</p> |
| 2577 | |
Bill Wendling | 3cd5ca6 | 2006-10-11 06:30:10 +0000 | [diff] [blame] | 2578 | <div class="doc_code"> |
| 2579 | <pre> |
| 2580 | Inst->replaceAllUsesWith(ConstVal); |
| 2581 | </pre> |
| 2582 | </div> |
| 2583 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2584 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2585 | |
| 2586 | </div> |
| 2587 | |
| 2588 | <!-- ======================================================================= --> |
| 2589 | <div class="doc_subsection"> |
| 2590 | <a name="User">The <tt>User</tt> class</a> |
| 2591 | </div> |
| 2592 | |
| 2593 | <div class="doc_text"> |
| 2594 | |
| 2595 | <p> |
| 2596 | <tt>#include "<a href="/doxygen/User_8h-source.html">llvm/User.h</a>"</tt><br> |
Misha Brukman | 384047f | 2004-06-03 23:29:12 +0000 | [diff] [blame] | 2597 | doxygen info: <a href="/doxygen/classllvm_1_1User.html">User Class</a><br> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2598 | Superclass: <a href="#Value"><tt>Value</tt></a></p> |
| 2599 | |
| 2600 | <p>The <tt>User</tt> class is the common base class of all LLVM nodes that may |
| 2601 | refer to <a href="#Value"><tt>Value</tt></a>s. It exposes a list of "Operands" |
| 2602 | that are all of the <a href="#Value"><tt>Value</tt></a>s that the User is |
| 2603 | referring to. The <tt>User</tt> class itself is a subclass of |
| 2604 | <tt>Value</tt>.</p> |
| 2605 | |
| 2606 | <p>The operands of a <tt>User</tt> point directly to the LLVM <a |
| 2607 | href="#Value"><tt>Value</tt></a> that it refers to. Because LLVM uses Static |
| 2608 | Single Assignment (SSA) form, there can only be one definition referred to, |
| 2609 | allowing this direct connection. This connection provides the use-def |
| 2610 | information in LLVM.</p> |
| 2611 | |
| 2612 | </div> |
| 2613 | |
| 2614 | <!-- _______________________________________________________________________ --> |
| 2615 | <div class="doc_subsubsection"> |
| 2616 | <a name="m_User">Important Public Members of the <tt>User</tt> class</a> |
| 2617 | </div> |
| 2618 | |
| 2619 | <div class="doc_text"> |
| 2620 | |
| 2621 | <p>The <tt>User</tt> class exposes the operand list in two ways: through |
| 2622 | an index access interface and through an iterator based interface.</p> |
| 2623 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2624 | <ul> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2625 | <li><tt>Value *getOperand(unsigned i)</tt><br> |
| 2626 | <tt>unsigned getNumOperands()</tt> |
| 2627 | <p> These two methods expose the operands of the <tt>User</tt> in a |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2628 | convenient form for direct access.</p></li> |
| 2629 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2630 | <li><tt>User::op_iterator</tt> - Typedef for iterator over the operand |
| 2631 | list<br> |
Chris Lattner | 5836082 | 2005-01-17 00:12:04 +0000 | [diff] [blame] | 2632 | <tt>op_iterator op_begin()</tt> - Get an iterator to the start of |
| 2633 | the operand list.<br> |
| 2634 | <tt>op_iterator op_end()</tt> - Get an iterator to the end of the |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2635 | operand list. |
| 2636 | <p> Together, these methods make up the iterator based interface to |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2637 | the operands of a <tt>User</tt>.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2638 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2639 | |
| 2640 | </div> |
| 2641 | |
| 2642 | <!-- ======================================================================= --> |
| 2643 | <div class="doc_subsection"> |
| 2644 | <a name="Instruction">The <tt>Instruction</tt> class</a> |
| 2645 | </div> |
| 2646 | |
| 2647 | <div class="doc_text"> |
| 2648 | |
| 2649 | <p><tt>#include "</tt><tt><a |
| 2650 | href="/doxygen/Instruction_8h-source.html">llvm/Instruction.h</a>"</tt><br> |
Misha Brukman | 31ca1de | 2004-06-03 23:35:54 +0000 | [diff] [blame] | 2651 | doxygen info: <a href="/doxygen/classllvm_1_1Instruction.html">Instruction Class</a><br> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2652 | Superclasses: <a href="#User"><tt>User</tt></a>, <a |
| 2653 | href="#Value"><tt>Value</tt></a></p> |
| 2654 | |
| 2655 | <p>The <tt>Instruction</tt> class is the common base class for all LLVM |
| 2656 | instructions. It provides only a few methods, but is a very commonly used |
| 2657 | class. The primary data tracked by the <tt>Instruction</tt> class itself is the |
| 2658 | opcode (instruction type) and the parent <a |
| 2659 | href="#BasicBlock"><tt>BasicBlock</tt></a> the <tt>Instruction</tt> is embedded |
| 2660 | into. To represent a specific type of instruction, one of many subclasses of |
| 2661 | <tt>Instruction</tt> are used.</p> |
| 2662 | |
| 2663 | <p> Because the <tt>Instruction</tt> class subclasses the <a |
| 2664 | href="#User"><tt>User</tt></a> class, its operands can be accessed in the same |
| 2665 | way as for other <a href="#User"><tt>User</tt></a>s (with the |
| 2666 | <tt>getOperand()</tt>/<tt>getNumOperands()</tt> and |
| 2667 | <tt>op_begin()</tt>/<tt>op_end()</tt> methods).</p> <p> An important file for |
| 2668 | the <tt>Instruction</tt> class is the <tt>llvm/Instruction.def</tt> file. This |
| 2669 | file contains some meta-data about the various different types of instructions |
| 2670 | in LLVM. It describes the enum values that are used as opcodes (for example |
Reid Spencer | c92d25d | 2006-12-19 19:47:19 +0000 | [diff] [blame] | 2671 | <tt>Instruction::Add</tt> and <tt>Instruction::ICmp</tt>), as well as the |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2672 | concrete sub-classes of <tt>Instruction</tt> that implement the instruction (for |
| 2673 | example <tt><a href="#BinaryOperator">BinaryOperator</a></tt> and <tt><a |
Reid Spencer | c92d25d | 2006-12-19 19:47:19 +0000 | [diff] [blame] | 2674 | href="#CmpInst">CmpInst</a></tt>). Unfortunately, the use of macros in |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2675 | this file confuses doxygen, so these enum values don't show up correctly in the |
Misha Brukman | 31ca1de | 2004-06-03 23:35:54 +0000 | [diff] [blame] | 2676 | <a href="/doxygen/classllvm_1_1Instruction.html">doxygen output</a>.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2677 | |
| 2678 | </div> |
| 2679 | |
| 2680 | <!-- _______________________________________________________________________ --> |
| 2681 | <div class="doc_subsubsection"> |
Reid Spencer | c92d25d | 2006-12-19 19:47:19 +0000 | [diff] [blame] | 2682 | <a name="s_Instruction">Important Subclasses of the <tt>Instruction</tt> |
| 2683 | class</a> |
| 2684 | </div> |
| 2685 | <div class="doc_text"> |
| 2686 | <ul> |
| 2687 | <li><tt><a name="BinaryOperator">BinaryOperator</a></tt> |
| 2688 | <p>This subclasses represents all two operand instructions whose operands |
| 2689 | must be the same type, except for the comparison instructions.</p></li> |
| 2690 | <li><tt><a name="CastInst">CastInst</a></tt> |
| 2691 | <p>This subclass is the parent of the 12 casting instructions. It provides |
| 2692 | common operations on cast instructions.</p> |
| 2693 | <li><tt><a name="CmpInst">CmpInst</a></tt> |
| 2694 | <p>This subclass respresents the two comparison instructions, |
| 2695 | <a href="LangRef.html#i_icmp">ICmpInst</a> (integer opreands), and |
| 2696 | <a href="LangRef.html#i_fcmp">FCmpInst</a> (floating point operands).</p> |
| 2697 | <li><tt><a name="TerminatorInst">TerminatorInst</a></tt> |
| 2698 | <p>This subclass is the parent of all terminator instructions (those which |
| 2699 | can terminate a block).</p> |
| 2700 | </ul> |
| 2701 | </div> |
| 2702 | |
| 2703 | <!-- _______________________________________________________________________ --> |
| 2704 | <div class="doc_subsubsection"> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2705 | <a name="m_Instruction">Important Public Members of the <tt>Instruction</tt> |
| 2706 | class</a> |
| 2707 | </div> |
| 2708 | |
| 2709 | <div class="doc_text"> |
| 2710 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2711 | <ul> |
| 2712 | <li><tt><a href="#BasicBlock">BasicBlock</a> *getParent()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2713 | <p>Returns the <a href="#BasicBlock"><tt>BasicBlock</tt></a> that |
| 2714 | this <tt>Instruction</tt> is embedded into.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2715 | <li><tt>bool mayWriteToMemory()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2716 | <p>Returns true if the instruction writes to memory, i.e. it is a |
| 2717 | <tt>call</tt>,<tt>free</tt>,<tt>invoke</tt>, or <tt>store</tt>.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2718 | <li><tt>unsigned getOpcode()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2719 | <p>Returns the opcode for the <tt>Instruction</tt>.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2720 | <li><tt><a href="#Instruction">Instruction</a> *clone() const</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2721 | <p>Returns another instance of the specified instruction, identical |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2722 | in all ways to the original except that the instruction has no parent |
| 2723 | (ie it's not embedded into a <a href="#BasicBlock"><tt>BasicBlock</tt></a>), |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2724 | and it has no name</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2725 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2726 | |
| 2727 | </div> |
| 2728 | |
| 2729 | <!-- ======================================================================= --> |
| 2730 | <div class="doc_subsection"> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2731 | <a name="Constant">The <tt>Constant</tt> class and subclasses</a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2732 | </div> |
| 2733 | |
| 2734 | <div class="doc_text"> |
| 2735 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2736 | <p>Constant represents a base class for different types of constants. It |
| 2737 | is subclassed by ConstantInt, ConstantArray, etc. for representing |
| 2738 | the various types of Constants. <a href="#GlobalValue">GlobalValue</a> is also |
| 2739 | a subclass, which represents the address of a global variable or function. |
| 2740 | </p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2741 | |
| 2742 | </div> |
| 2743 | |
| 2744 | <!-- _______________________________________________________________________ --> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2745 | <div class="doc_subsubsection">Important Subclasses of Constant </div> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2746 | <div class="doc_text"> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2747 | <ul> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2748 | <li>ConstantInt : This subclass of Constant represents an integer constant of |
| 2749 | any width. |
| 2750 | <ul> |
| 2751 | <li><tt>int64_t getSExtValue() const</tt>: Returns the underlying value of |
| 2752 | this constant as a sign extended signed integer value.</li> |
| 2753 | <li><tt>uint64_t getZExtValue() const</tt>: Returns the underlying value |
| 2754 | of this constant as a zero extended unsigned integer value.</li> |
| 2755 | <li><tt>static ConstantInt* get(const Type *Ty, uint64_t Val)</tt>: |
| 2756 | Returns the ConstantInt object that represents the value provided by |
| 2757 | <tt>Val</tt> for integer type <tt>Ty</tt>.</li> |
| 2758 | </ul> |
| 2759 | </li> |
| 2760 | <li>ConstantFP : This class represents a floating point constant. |
| 2761 | <ul> |
| 2762 | <li><tt>double getValue() const</tt>: Returns the underlying value of |
| 2763 | this constant. </li> |
| 2764 | </ul> |
| 2765 | </li> |
| 2766 | <li>ConstantArray : This represents a constant array. |
| 2767 | <ul> |
| 2768 | <li><tt>const std::vector<Use> &getValues() const</tt>: Returns |
| 2769 | a vector of component constants that makeup this array. </li> |
| 2770 | </ul> |
| 2771 | </li> |
| 2772 | <li>ConstantStruct : This represents a constant struct. |
| 2773 | <ul> |
| 2774 | <li><tt>const std::vector<Use> &getValues() const</tt>: Returns |
| 2775 | a vector of component constants that makeup this array. </li> |
| 2776 | </ul> |
| 2777 | </li> |
| 2778 | <li>GlobalValue : This represents either a global variable or a function. In |
| 2779 | either case, the value is a constant fixed address (after linking). |
| 2780 | </li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2781 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2782 | </div> |
| 2783 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 2784 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2785 | <!-- ======================================================================= --> |
| 2786 | <div class="doc_subsection"> |
| 2787 | <a name="GlobalValue">The <tt>GlobalValue</tt> class</a> |
| 2788 | </div> |
| 2789 | |
| 2790 | <div class="doc_text"> |
| 2791 | |
| 2792 | <p><tt>#include "<a |
| 2793 | href="/doxygen/GlobalValue_8h-source.html">llvm/GlobalValue.h</a>"</tt><br> |
Misha Brukman | 384047f | 2004-06-03 23:29:12 +0000 | [diff] [blame] | 2794 | doxygen info: <a href="/doxygen/classllvm_1_1GlobalValue.html">GlobalValue |
| 2795 | Class</a><br> |
Reid Spencer | be5e85e | 2006-04-14 14:11:48 +0000 | [diff] [blame] | 2796 | Superclasses: <a href="#Constant"><tt>Constant</tt></a>, |
| 2797 | <a href="#User"><tt>User</tt></a>, <a href="#Value"><tt>Value</tt></a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2798 | |
| 2799 | <p>Global values (<a href="#GlobalVariable"><tt>GlobalVariable</tt></a>s or <a |
| 2800 | href="#Function"><tt>Function</tt></a>s) are the only LLVM values that are |
| 2801 | visible in the bodies of all <a href="#Function"><tt>Function</tt></a>s. |
| 2802 | Because they are visible at global scope, they are also subject to linking with |
| 2803 | other globals defined in different translation units. To control the linking |
| 2804 | process, <tt>GlobalValue</tt>s know their linkage rules. Specifically, |
| 2805 | <tt>GlobalValue</tt>s know whether they have internal or external linkage, as |
Reid Spencer | 8b2da7a | 2004-07-18 13:10:31 +0000 | [diff] [blame] | 2806 | defined by the <tt>LinkageTypes</tt> enumeration.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2807 | |
| 2808 | <p>If a <tt>GlobalValue</tt> has internal linkage (equivalent to being |
| 2809 | <tt>static</tt> in C), it is not visible to code outside the current translation |
| 2810 | unit, and does not participate in linking. If it has external linkage, it is |
| 2811 | visible to external code, and does participate in linking. In addition to |
| 2812 | linkage information, <tt>GlobalValue</tt>s keep track of which <a |
| 2813 | href="#Module"><tt>Module</tt></a> they are currently part of.</p> |
| 2814 | |
| 2815 | <p>Because <tt>GlobalValue</tt>s are memory objects, they are always referred to |
| 2816 | by their <b>address</b>. As such, the <a href="#Type"><tt>Type</tt></a> of a |
| 2817 | global is always a pointer to its contents. It is important to remember this |
| 2818 | when using the <tt>GetElementPtrInst</tt> instruction because this pointer must |
| 2819 | be dereferenced first. For example, if you have a <tt>GlobalVariable</tt> (a |
| 2820 | subclass of <tt>GlobalValue)</tt> that is an array of 24 ints, type <tt>[24 x |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 2821 | i32]</tt>, then the <tt>GlobalVariable</tt> is a pointer to that array. Although |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2822 | the address of the first element of this array and the value of the |
| 2823 | <tt>GlobalVariable</tt> are the same, they have different types. The |
Reid Spencer | 06565dc | 2007-01-12 17:11:23 +0000 | [diff] [blame] | 2824 | <tt>GlobalVariable</tt>'s type is <tt>[24 x i32]</tt>. The first element's type |
| 2825 | is <tt>i32.</tt> Because of this, accessing a global value requires you to |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2826 | dereference the pointer with <tt>GetElementPtrInst</tt> first, then its elements |
| 2827 | can be accessed. This is explained in the <a href="LangRef.html#globalvars">LLVM |
| 2828 | Language Reference Manual</a>.</p> |
| 2829 | |
| 2830 | </div> |
| 2831 | |
| 2832 | <!-- _______________________________________________________________________ --> |
| 2833 | <div class="doc_subsubsection"> |
| 2834 | <a name="m_GlobalValue">Important Public Members of the <tt>GlobalValue</tt> |
| 2835 | class</a> |
| 2836 | </div> |
| 2837 | |
| 2838 | <div class="doc_text"> |
| 2839 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2840 | <ul> |
| 2841 | <li><tt>bool hasInternalLinkage() const</tt><br> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 2842 | <tt>bool hasExternalLinkage() const</tt><br> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2843 | <tt>void setInternalLinkage(bool HasInternalLinkage)</tt> |
| 2844 | <p> These methods manipulate the linkage characteristics of the <tt>GlobalValue</tt>.</p> |
| 2845 | <p> </p> |
| 2846 | </li> |
| 2847 | <li><tt><a href="#Module">Module</a> *getParent()</tt> |
| 2848 | <p> This returns the <a href="#Module"><tt>Module</tt></a> that the |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2849 | GlobalValue is currently embedded into.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2850 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2851 | |
| 2852 | </div> |
| 2853 | |
| 2854 | <!-- ======================================================================= --> |
| 2855 | <div class="doc_subsection"> |
| 2856 | <a name="Function">The <tt>Function</tt> class</a> |
| 2857 | </div> |
| 2858 | |
| 2859 | <div class="doc_text"> |
| 2860 | |
| 2861 | <p><tt>#include "<a |
| 2862 | href="/doxygen/Function_8h-source.html">llvm/Function.h</a>"</tt><br> doxygen |
Misha Brukman | 31ca1de | 2004-06-03 23:35:54 +0000 | [diff] [blame] | 2863 | info: <a href="/doxygen/classllvm_1_1Function.html">Function Class</a><br> |
Reid Spencer | be5e85e | 2006-04-14 14:11:48 +0000 | [diff] [blame] | 2864 | Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>, |
| 2865 | <a href="#Constant"><tt>Constant</tt></a>, |
| 2866 | <a href="#User"><tt>User</tt></a>, |
| 2867 | <a href="#Value"><tt>Value</tt></a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2868 | |
| 2869 | <p>The <tt>Function</tt> class represents a single procedure in LLVM. It is |
| 2870 | actually one of the more complex classes in the LLVM heirarchy because it must |
| 2871 | keep track of a large amount of data. The <tt>Function</tt> class keeps track |
Reid Spencer | be5e85e | 2006-04-14 14:11:48 +0000 | [diff] [blame] | 2872 | of a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, a list of formal |
| 2873 | <a href="#Argument"><tt>Argument</tt></a>s, and a |
| 2874 | <a href="#SymbolTable"><tt>SymbolTable</tt></a>.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2875 | |
| 2876 | <p>The list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s is the most |
| 2877 | commonly used part of <tt>Function</tt> objects. The list imposes an implicit |
| 2878 | ordering of the blocks in the function, which indicate how the code will be |
| 2879 | layed out by the backend. Additionally, the first <a |
| 2880 | href="#BasicBlock"><tt>BasicBlock</tt></a> is the implicit entry node for the |
| 2881 | <tt>Function</tt>. It is not legal in LLVM to explicitly branch to this initial |
| 2882 | block. There are no implicit exit nodes, and in fact there may be multiple exit |
| 2883 | nodes from a single <tt>Function</tt>. If the <a |
| 2884 | href="#BasicBlock"><tt>BasicBlock</tt></a> list is empty, this indicates that |
| 2885 | the <tt>Function</tt> is actually a function declaration: the actual body of the |
| 2886 | function hasn't been linked in yet.</p> |
| 2887 | |
| 2888 | <p>In addition to a list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s, the |
| 2889 | <tt>Function</tt> class also keeps track of the list of formal <a |
| 2890 | href="#Argument"><tt>Argument</tt></a>s that the function receives. This |
| 2891 | container manages the lifetime of the <a href="#Argument"><tt>Argument</tt></a> |
| 2892 | nodes, just like the <a href="#BasicBlock"><tt>BasicBlock</tt></a> list does for |
| 2893 | the <a href="#BasicBlock"><tt>BasicBlock</tt></a>s.</p> |
| 2894 | |
| 2895 | <p>The <a href="#SymbolTable"><tt>SymbolTable</tt></a> is a very rarely used |
| 2896 | LLVM feature that is only used when you have to look up a value by name. Aside |
| 2897 | from that, the <a href="#SymbolTable"><tt>SymbolTable</tt></a> is used |
| 2898 | internally to make sure that there are not conflicts between the names of <a |
| 2899 | href="#Instruction"><tt>Instruction</tt></a>s, <a |
| 2900 | href="#BasicBlock"><tt>BasicBlock</tt></a>s, or <a |
| 2901 | href="#Argument"><tt>Argument</tt></a>s in the function body.</p> |
| 2902 | |
Reid Spencer | 8b2da7a | 2004-07-18 13:10:31 +0000 | [diff] [blame] | 2903 | <p>Note that <tt>Function</tt> is a <a href="#GlobalValue">GlobalValue</a> |
| 2904 | and therefore also a <a href="#Constant">Constant</a>. The value of the function |
| 2905 | is its address (after linking) which is guaranteed to be constant.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2906 | </div> |
| 2907 | |
| 2908 | <!-- _______________________________________________________________________ --> |
| 2909 | <div class="doc_subsubsection"> |
| 2910 | <a name="m_Function">Important Public Members of the <tt>Function</tt> |
| 2911 | class</a> |
| 2912 | </div> |
| 2913 | |
| 2914 | <div class="doc_text"> |
| 2915 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2916 | <ul> |
| 2917 | <li><tt>Function(const </tt><tt><a href="#FunctionType">FunctionType</a> |
Chris Lattner | ac479e5 | 2004-08-04 05:10:48 +0000 | [diff] [blame] | 2918 | *Ty, LinkageTypes Linkage, const std::string &N = "", Module* Parent = 0)</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2919 | |
| 2920 | <p>Constructor used when you need to create new <tt>Function</tt>s to add |
| 2921 | the the program. The constructor must specify the type of the function to |
Chris Lattner | ac479e5 | 2004-08-04 05:10:48 +0000 | [diff] [blame] | 2922 | create and what type of linkage the function should have. The <a |
| 2923 | href="#FunctionType"><tt>FunctionType</tt></a> argument |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2924 | specifies the formal arguments and return value for the function. The same |
| 2925 | <a href="#FunctionTypel"><tt>FunctionType</tt></a> value can be used to |
| 2926 | create multiple functions. The <tt>Parent</tt> argument specifies the Module |
| 2927 | in which the function is defined. If this argument is provided, the function |
| 2928 | will automatically be inserted into that module's list of |
| 2929 | functions.</p></li> |
| 2930 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2931 | <li><tt>bool isExternal()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2932 | |
| 2933 | <p>Return whether or not the <tt>Function</tt> has a body defined. If the |
| 2934 | function is "external", it does not have a body, and thus must be resolved |
| 2935 | by linking with a function defined in a different translation unit.</p></li> |
| 2936 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2937 | <li><tt>Function::iterator</tt> - Typedef for basic block list iterator<br> |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 2938 | <tt>Function::const_iterator</tt> - Typedef for const_iterator.<br> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2939 | |
Chris Lattner | 77d6924 | 2005-03-15 05:19:20 +0000 | [diff] [blame] | 2940 | <tt>begin()</tt>, <tt>end()</tt> |
| 2941 | <tt>size()</tt>, <tt>empty()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2942 | |
| 2943 | <p>These are forwarding methods that make it easy to access the contents of |
| 2944 | a <tt>Function</tt> object's <a href="#BasicBlock"><tt>BasicBlock</tt></a> |
| 2945 | list.</p></li> |
| 2946 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2947 | <li><tt>Function::BasicBlockListType &getBasicBlockList()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2948 | |
| 2949 | <p>Returns the list of <a href="#BasicBlock"><tt>BasicBlock</tt></a>s. This |
| 2950 | is necessary to use when you need to update the list or perform a complex |
| 2951 | action that doesn't have a forwarding method.</p></li> |
| 2952 | |
Chris Lattner | 89cc265 | 2005-03-15 04:48:32 +0000 | [diff] [blame] | 2953 | <li><tt>Function::arg_iterator</tt> - Typedef for the argument list |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2954 | iterator<br> |
Chris Lattner | 89cc265 | 2005-03-15 04:48:32 +0000 | [diff] [blame] | 2955 | <tt>Function::const_arg_iterator</tt> - Typedef for const_iterator.<br> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2956 | |
Chris Lattner | 77d6924 | 2005-03-15 05:19:20 +0000 | [diff] [blame] | 2957 | <tt>arg_begin()</tt>, <tt>arg_end()</tt> |
Chris Lattner | 89cc265 | 2005-03-15 04:48:32 +0000 | [diff] [blame] | 2958 | <tt>arg_size()</tt>, <tt>arg_empty()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2959 | |
| 2960 | <p>These are forwarding methods that make it easy to access the contents of |
| 2961 | a <tt>Function</tt> object's <a href="#Argument"><tt>Argument</tt></a> |
| 2962 | list.</p></li> |
| 2963 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2964 | <li><tt>Function::ArgumentListType &getArgumentList()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2965 | |
| 2966 | <p>Returns the list of <a href="#Argument"><tt>Argument</tt></a>s. This is |
| 2967 | necessary to use when you need to update the list or perform a complex |
| 2968 | action that doesn't have a forwarding method.</p></li> |
| 2969 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2970 | <li><tt><a href="#BasicBlock">BasicBlock</a> &getEntryBlock()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2971 | |
| 2972 | <p>Returns the entry <a href="#BasicBlock"><tt>BasicBlock</tt></a> for the |
| 2973 | function. Because the entry block for the function is always the first |
| 2974 | block, this returns the first block of the <tt>Function</tt>.</p></li> |
| 2975 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2976 | <li><tt><a href="#Type">Type</a> *getReturnType()</tt><br> |
| 2977 | <tt><a href="#FunctionType">FunctionType</a> *getFunctionType()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2978 | |
| 2979 | <p>This traverses the <a href="#Type"><tt>Type</tt></a> of the |
| 2980 | <tt>Function</tt> and returns the return type of the function, or the <a |
| 2981 | href="#FunctionType"><tt>FunctionType</tt></a> of the actual |
| 2982 | function.</p></li> |
| 2983 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2984 | <li><tt><a href="#SymbolTable">SymbolTable</a> *getSymbolTable()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2985 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2986 | <p> Return a pointer to the <a href="#SymbolTable"><tt>SymbolTable</tt></a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2987 | for this <tt>Function</tt>.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 2988 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 2989 | |
| 2990 | </div> |
| 2991 | |
| 2992 | <!-- ======================================================================= --> |
| 2993 | <div class="doc_subsection"> |
| 2994 | <a name="GlobalVariable">The <tt>GlobalVariable</tt> class</a> |
| 2995 | </div> |
| 2996 | |
| 2997 | <div class="doc_text"> |
| 2998 | |
| 2999 | <p><tt>#include "<a |
| 3000 | href="/doxygen/GlobalVariable_8h-source.html">llvm/GlobalVariable.h</a>"</tt> |
| 3001 | <br> |
Tanya Lattner | a3da777 | 2004-06-22 08:02:25 +0000 | [diff] [blame] | 3002 | doxygen info: <a href="/doxygen/classllvm_1_1GlobalVariable.html">GlobalVariable |
Reid Spencer | be5e85e | 2006-04-14 14:11:48 +0000 | [diff] [blame] | 3003 | Class</a><br> |
| 3004 | Superclasses: <a href="#GlobalValue"><tt>GlobalValue</tt></a>, |
| 3005 | <a href="#Constant"><tt>Constant</tt></a>, |
| 3006 | <a href="#User"><tt>User</tt></a>, |
| 3007 | <a href="#Value"><tt>Value</tt></a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3008 | |
| 3009 | <p>Global variables are represented with the (suprise suprise) |
| 3010 | <tt>GlobalVariable</tt> class. Like functions, <tt>GlobalVariable</tt>s are also |
| 3011 | subclasses of <a href="#GlobalValue"><tt>GlobalValue</tt></a>, and as such are |
| 3012 | always referenced by their address (global values must live in memory, so their |
Reid Spencer | be5e85e | 2006-04-14 14:11:48 +0000 | [diff] [blame] | 3013 | "name" refers to their constant address). See |
| 3014 | <a href="#GlobalValue"><tt>GlobalValue</tt></a> for more on this. Global |
| 3015 | variables may have an initial value (which must be a |
| 3016 | <a href="#Constant"><tt>Constant</tt></a>), and if they have an initializer, |
| 3017 | they may be marked as "constant" themselves (indicating that their contents |
| 3018 | never change at runtime).</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3019 | </div> |
| 3020 | |
| 3021 | <!-- _______________________________________________________________________ --> |
| 3022 | <div class="doc_subsubsection"> |
| 3023 | <a name="m_GlobalVariable">Important Public Members of the |
| 3024 | <tt>GlobalVariable</tt> class</a> |
| 3025 | </div> |
| 3026 | |
| 3027 | <div class="doc_text"> |
| 3028 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3029 | <ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3030 | <li><tt>GlobalVariable(const </tt><tt><a href="#Type">Type</a> *Ty, bool |
| 3031 | isConstant, LinkageTypes& Linkage, <a href="#Constant">Constant</a> |
| 3032 | *Initializer = 0, const std::string &Name = "", Module* Parent = 0)</tt> |
| 3033 | |
| 3034 | <p>Create a new global variable of the specified type. If |
| 3035 | <tt>isConstant</tt> is true then the global variable will be marked as |
| 3036 | unchanging for the program. The Linkage parameter specifies the type of |
| 3037 | linkage (internal, external, weak, linkonce, appending) for the variable. If |
| 3038 | the linkage is InternalLinkage, WeakLinkage, or LinkOnceLinkage, then |
| 3039 | the resultant global variable will have internal linkage. AppendingLinkage |
| 3040 | concatenates together all instances (in different translation units) of the |
| 3041 | variable into a single variable but is only applicable to arrays. See |
| 3042 | the <a href="LangRef.html#modulestructure">LLVM Language Reference</a> for |
| 3043 | further details on linkage types. Optionally an initializer, a name, and the |
| 3044 | module to put the variable into may be specified for the global variable as |
| 3045 | well.</p></li> |
| 3046 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3047 | <li><tt>bool isConstant() const</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3048 | |
| 3049 | <p>Returns true if this is a global variable that is known not to |
| 3050 | be modified at runtime.</p></li> |
| 3051 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3052 | <li><tt>bool hasInitializer()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3053 | |
| 3054 | <p>Returns true if this <tt>GlobalVariable</tt> has an intializer.</p></li> |
| 3055 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3056 | <li><tt><a href="#Constant">Constant</a> *getInitializer()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3057 | |
| 3058 | <p>Returns the intial value for a <tt>GlobalVariable</tt>. It is not legal |
| 3059 | to call this method if there is no initializer.</p></li> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3060 | </ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3061 | |
| 3062 | </div> |
| 3063 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3064 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3065 | <!-- ======================================================================= --> |
| 3066 | <div class="doc_subsection"> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3067 | <a name="BasicBlock">The <tt>BasicBlock</tt> class</a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3068 | </div> |
| 3069 | |
| 3070 | <div class="doc_text"> |
| 3071 | |
| 3072 | <p><tt>#include "<a |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3073 | href="/doxygen/BasicBlock_8h-source.html">llvm/BasicBlock.h</a>"</tt><br> |
| 3074 | doxygen info: <a href="/doxygen/structllvm_1_1BasicBlock.html">BasicBlock |
| 3075 | Class</a><br> |
| 3076 | Superclass: <a href="#Value"><tt>Value</tt></a></p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3077 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3078 | <p>This class represents a single entry multiple exit section of the code, |
| 3079 | commonly known as a basic block by the compiler community. The |
| 3080 | <tt>BasicBlock</tt> class maintains a list of <a |
| 3081 | href="#Instruction"><tt>Instruction</tt></a>s, which form the body of the block. |
| 3082 | Matching the language definition, the last element of this list of instructions |
| 3083 | is always a terminator instruction (a subclass of the <a |
| 3084 | href="#TerminatorInst"><tt>TerminatorInst</tt></a> class).</p> |
| 3085 | |
| 3086 | <p>In addition to tracking the list of instructions that make up the block, the |
| 3087 | <tt>BasicBlock</tt> class also keeps track of the <a |
| 3088 | href="#Function"><tt>Function</tt></a> that it is embedded into.</p> |
| 3089 | |
| 3090 | <p>Note that <tt>BasicBlock</tt>s themselves are <a |
| 3091 | href="#Value"><tt>Value</tt></a>s, because they are referenced by instructions |
| 3092 | like branches and can go in the switch tables. <tt>BasicBlock</tt>s have type |
| 3093 | <tt>label</tt>.</p> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3094 | |
| 3095 | </div> |
| 3096 | |
| 3097 | <!-- _______________________________________________________________________ --> |
| 3098 | <div class="doc_subsubsection"> |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3099 | <a name="m_BasicBlock">Important Public Members of the <tt>BasicBlock</tt> |
| 3100 | class</a> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3101 | </div> |
| 3102 | |
| 3103 | <div class="doc_text"> |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3104 | <ul> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3105 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3106 | <li><tt>BasicBlock(const std::string &Name = "", </tt><tt><a |
| 3107 | href="#Function">Function</a> *Parent = 0)</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3108 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3109 | <p>The <tt>BasicBlock</tt> constructor is used to create new basic blocks for |
| 3110 | insertion into a function. The constructor optionally takes a name for the new |
| 3111 | block, and a <a href="#Function"><tt>Function</tt></a> to insert it into. If |
| 3112 | the <tt>Parent</tt> parameter is specified, the new <tt>BasicBlock</tt> is |
| 3113 | automatically inserted at the end of the specified <a |
| 3114 | href="#Function"><tt>Function</tt></a>, if not specified, the BasicBlock must be |
| 3115 | manually inserted into the <a href="#Function"><tt>Function</tt></a>.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3116 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3117 | <li><tt>BasicBlock::iterator</tt> - Typedef for instruction list iterator<br> |
| 3118 | <tt>BasicBlock::const_iterator</tt> - Typedef for const_iterator.<br> |
| 3119 | <tt>begin()</tt>, <tt>end()</tt>, <tt>front()</tt>, <tt>back()</tt>, |
| 3120 | <tt>size()</tt>, <tt>empty()</tt> |
| 3121 | STL-style functions for accessing the instruction list. |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3122 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3123 | <p>These methods and typedefs are forwarding functions that have the same |
| 3124 | semantics as the standard library methods of the same names. These methods |
| 3125 | expose the underlying instruction list of a basic block in a way that is easy to |
| 3126 | manipulate. To get the full complement of container operations (including |
| 3127 | operations to update the list), you must use the <tt>getInstList()</tt> |
| 3128 | method.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3129 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3130 | <li><tt>BasicBlock::InstListType &getInstList()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3131 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3132 | <p>This method is used to get access to the underlying container that actually |
| 3133 | holds the Instructions. This method must be used when there isn't a forwarding |
| 3134 | function in the <tt>BasicBlock</tt> class for the operation that you would like |
| 3135 | to perform. Because there are no forwarding functions for "updating" |
| 3136 | operations, you need to use this if you want to update the contents of a |
| 3137 | <tt>BasicBlock</tt>.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3138 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3139 | <li><tt><a href="#Function">Function</a> *getParent()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3140 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3141 | <p> Returns a pointer to <a href="#Function"><tt>Function</tt></a> the block is |
| 3142 | embedded into, or a null pointer if it is homeless.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3143 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3144 | <li><tt><a href="#TerminatorInst">TerminatorInst</a> *getTerminator()</tt> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3145 | |
Chris Lattner | 2b78d96 | 2007-02-03 20:02:25 +0000 | [diff] [blame] | 3146 | <p> Returns a pointer to the terminator instruction that appears at the end of |
| 3147 | the <tt>BasicBlock</tt>. If there is no terminator instruction, or if the last |
| 3148 | instruction in the block is not a terminator, then a null pointer is |
| 3149 | returned.</p></li> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3150 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3151 | </ul> |
| 3152 | |
| 3153 | </div> |
| 3154 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3155 | |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3156 | <!-- ======================================================================= --> |
| 3157 | <div class="doc_subsection"> |
| 3158 | <a name="Argument">The <tt>Argument</tt> class</a> |
| 3159 | </div> |
| 3160 | |
| 3161 | <div class="doc_text"> |
| 3162 | |
| 3163 | <p>This subclass of Value defines the interface for incoming formal |
Chris Lattner | 5836082 | 2005-01-17 00:12:04 +0000 | [diff] [blame] | 3164 | arguments to a function. A Function maintains a list of its formal |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3165 | arguments. An argument has a pointer to the parent Function.</p> |
| 3166 | |
| 3167 | </div> |
| 3168 | |
Chris Lattner | 9355b47 | 2002-09-06 02:50:58 +0000 | [diff] [blame] | 3169 | <!-- *********************************************************************** --> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3170 | <hr> |
| 3171 | <address> |
| 3172 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
| 3173 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
| 3174 | <a href="http://validator.w3.org/check/referer"><img |
| 3175 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a> |
| 3176 | |
| 3177 | <a href="mailto:dhurjati@cs.uiuc.edu">Dinakar Dhurjati</a> and |
| 3178 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
Reid Spencer | 05fe4b0 | 2006-03-14 05:39:39 +0000 | [diff] [blame] | 3179 | <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br> |
Misha Brukman | 13fd15c | 2004-01-15 00:14:41 +0000 | [diff] [blame] | 3180 | Last modified: $Date$ |
| 3181 | </address> |
| 3182 | |
Chris Lattner | 261efe9 | 2003-11-25 01:02:51 +0000 | [diff] [blame] | 3183 | </body> |
| 3184 | </html> |