Ted Kremenek | 17a295d | 2008-06-11 06:19:49 +0000 | [diff] [blame] | 1 | <html> |
| 2 | <head> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 3 | <title>"clang" CFE Internals Manual</title> |
Ted Kremenek | 17a295d | 2008-06-11 06:19:49 +0000 | [diff] [blame] | 4 | <link type="text/css" rel="stylesheet" href="../menu.css" /> |
| 5 | <link type="text/css" rel="stylesheet" href="../content.css" /> |
| 6 | </head> |
| 7 | <body> |
| 8 | |
| 9 | <!--#include virtual="../menu.html.incl"--> |
| 10 | |
| 11 | <div id="content"> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 12 | |
| 13 | <h1>"clang" CFE Internals Manual</h1> |
| 14 | |
| 15 | <ul> |
| 16 | <li><a href="#intro">Introduction</a></li> |
| 17 | <li><a href="#libsystem">LLVM System and Support Libraries</a></li> |
| 18 | <li><a href="#libbasic">The clang 'Basic' Library</a> |
| 19 | <ul> |
| 20 | <li><a href="#SourceLocation">The SourceLocation and SourceManager |
| 21 | classes</a></li> |
| 22 | </ul> |
| 23 | </li> |
| 24 | <li><a href="#liblex">The Lexer and Preprocessor Library</a> |
| 25 | <ul> |
| 26 | <li><a href="#Token">The Token class</a></li> |
| 27 | <li><a href="#Lexer">The Lexer class</a></li> |
Chris Lattner | 7928125 | 2008-03-09 02:27:26 +0000 | [diff] [blame] | 28 | <li><a href="#TokenLexer">The TokenLexer class</a></li> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 29 | <li><a href="#MultipleIncludeOpt">The MultipleIncludeOpt class</a></li> |
| 30 | </ul> |
| 31 | </li> |
| 32 | <li><a href="#libparse">The Parser Library</a> |
| 33 | <ul> |
| 34 | </ul> |
| 35 | </li> |
| 36 | <li><a href="#libast">The AST Library</a> |
| 37 | <ul> |
| 38 | <li><a href="#Type">The Type class and its subclasses</a></li> |
| 39 | <li><a href="#QualType">The QualType class</a></li> |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 40 | <li><a href="#DeclarationName">Declaration names</a></li> |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 41 | <li><a href="#CFG">The CFG class</a></li> |
Chris Lattner | 7bad199 | 2008-11-16 21:48:07 +0000 | [diff] [blame] | 42 | <li><a href="#Constants">Constant Folding in the Clang AST</a></li> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 43 | </ul> |
| 44 | </li> |
| 45 | </ul> |
| 46 | |
| 47 | |
| 48 | <!-- ======================================================================= --> |
| 49 | <h2 id="intro">Introduction</h2> |
| 50 | <!-- ======================================================================= --> |
| 51 | |
| 52 | <p>This document describes some of the more important APIs and internal design |
| 53 | decisions made in the clang C front-end. The purpose of this document is to |
| 54 | both capture some of this high level information and also describe some of the |
| 55 | design decisions behind it. This is meant for people interested in hacking on |
| 56 | clang, not for end-users. The description below is categorized by |
| 57 | libraries, and does not describe any of the clients of the libraries.</p> |
| 58 | |
| 59 | <!-- ======================================================================= --> |
| 60 | <h2 id="libsystem">LLVM System and Support Libraries</h2> |
| 61 | <!-- ======================================================================= --> |
| 62 | |
| 63 | <p>The LLVM libsystem library provides the basic clang system abstraction layer, |
| 64 | which is used for file system access. The LLVM libsupport library provides many |
| 65 | underlying libraries and <a |
| 66 | href="http://llvm.org/docs/ProgrammersManual.html">data-structures</a>, |
| 67 | including command line option |
| 68 | processing and various containers.</p> |
| 69 | |
| 70 | <!-- ======================================================================= --> |
| 71 | <h2 id="libbasic">The clang 'Basic' Library</h2> |
| 72 | <!-- ======================================================================= --> |
| 73 | |
| 74 | <p>This library certainly needs a better name. The 'basic' library contains a |
| 75 | number of low-level utilities for tracking and manipulating source buffers, |
| 76 | locations within the source buffers, diagnostics, tokens, target abstraction, |
| 77 | and information about the subset of the language being compiled for.</p> |
| 78 | |
| 79 | <p>Part of this infrastructure is specific to C (such as the TargetInfo class), |
| 80 | other parts could be reused for other non-C-based languages (SourceLocation, |
| 81 | SourceManager, Diagnostics, FileManager). When and if there is future demand |
| 82 | we can figure out if it makes sense to introduce a new library, move the general |
| 83 | classes somewhere else, or introduce some other solution.</p> |
| 84 | |
| 85 | <p>We describe the roles of these classes in order of their dependencies.</p> |
| 86 | |
| 87 | <!-- ======================================================================= --> |
| 88 | <h3 id="SourceLocation">The SourceLocation and SourceManager classes</h3> |
| 89 | <!-- ======================================================================= --> |
| 90 | |
| 91 | <p>Strangely enough, the SourceLocation class represents a location within the |
| 92 | source code of the program. Important design points include:</p> |
| 93 | |
| 94 | <ol> |
| 95 | <li>sizeof(SourceLocation) must be extremely small, as these are embedded into |
| 96 | many AST nodes and are passed around often. Currently it is 32 bits.</li> |
| 97 | <li>SourceLocation must be a simple value object that can be efficiently |
| 98 | copied.</li> |
| 99 | <li>We should be able to represent a source location for any byte of any input |
| 100 | file. This includes in the middle of tokens, in whitespace, in trigraphs, |
| 101 | etc.</li> |
| 102 | <li>A SourceLocation must encode the current #include stack that was active when |
| 103 | the location was processed. For example, if the location corresponds to a |
| 104 | token, it should contain the set of #includes active when the token was |
| 105 | lexed. This allows us to print the #include stack for a diagnostic.</li> |
| 106 | <li>SourceLocation must be able to describe macro expansions, capturing both |
| 107 | the ultimate instantiation point and the source of the original character |
| 108 | data.</li> |
| 109 | </ol> |
| 110 | |
| 111 | <p>In practice, the SourceLocation works together with the SourceManager class |
| 112 | to encode two pieces of information about a location: it's physical location |
| 113 | and it's virtual location. For most tokens, these will be the same. However, |
| 114 | for a macro expansion (or tokens that came from a _Pragma directive) these will |
| 115 | describe the location of the characters corresponding to the token and the |
| 116 | location where the token was used (i.e. the macro instantiation point or the |
| 117 | location of the _Pragma itself).</p> |
| 118 | |
| 119 | <p>For efficiency, we only track one level of macro instantions: if a token was |
| 120 | produced by multiple instantiations, we only track the source and ultimate |
| 121 | destination. Though we could track the intermediate instantiation points, this |
| 122 | would require extra bookkeeping and no known client would benefit substantially |
| 123 | from this.</p> |
| 124 | |
| 125 | <p>The clang front-end inherently depends on the location of a token being |
| 126 | tracked correctly. If it is ever incorrect, the front-end may get confused and |
| 127 | die. The reason for this is that the notion of the 'spelling' of a Token in |
| 128 | clang depends on being able to find the original input characters for the token. |
| 129 | This concept maps directly to the "physical" location for the token.</p> |
| 130 | |
| 131 | <!-- ======================================================================= --> |
| 132 | <h2 id="liblex">The Lexer and Preprocessor Library</h2> |
| 133 | <!-- ======================================================================= --> |
| 134 | |
| 135 | <p>The Lexer library contains several tightly-connected classes that are involved |
| 136 | with the nasty process of lexing and preprocessing C source code. The main |
| 137 | interface to this library for outside clients is the large <a |
| 138 | href="#Preprocessor">Preprocessor</a> class. |
| 139 | It contains the various pieces of state that are required to coherently read |
| 140 | tokens out of a translation unit.</p> |
| 141 | |
| 142 | <p>The core interface to the Preprocessor object (once it is set up) is the |
| 143 | Preprocessor::Lex method, which returns the next <a href="#Token">Token</a> from |
| 144 | the preprocessor stream. There are two types of token providers that the |
| 145 | preprocessor is capable of reading from: a buffer lexer (provided by the <a |
| 146 | href="#Lexer">Lexer</a> class) and a buffered token stream (provided by the <a |
Chris Lattner | 7928125 | 2008-03-09 02:27:26 +0000 | [diff] [blame] | 147 | href="#TokenLexer">TokenLexer</a> class). |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 148 | |
| 149 | |
| 150 | <!-- ======================================================================= --> |
| 151 | <h3 id="Token">The Token class</h3> |
| 152 | <!-- ======================================================================= --> |
| 153 | |
| 154 | <p>The Token class is used to represent a single lexed token. Tokens are |
| 155 | intended to be used by the lexer/preprocess and parser libraries, but are not |
| 156 | intended to live beyond them (for example, they should not live in the ASTs).<p> |
| 157 | |
| 158 | <p>Tokens most often live on the stack (or some other location that is efficient |
| 159 | to access) as the parser is running, but occasionally do get buffered up. For |
| 160 | example, macro definitions are stored as a series of tokens, and the C++ |
| 161 | front-end will eventually need to buffer tokens up for tentative parsing and |
| 162 | various pieces of look-ahead. As such, the size of a Token matter. On a 32-bit |
| 163 | system, sizeof(Token) is currently 16 bytes.</p> |
| 164 | |
| 165 | <p>Tokens contain the following information:</p> |
| 166 | |
| 167 | <ul> |
| 168 | <li><b>A SourceLocation</b> - This indicates the location of the start of the |
| 169 | token.</li> |
| 170 | |
| 171 | <li><b>A length</b> - This stores the length of the token as stored in the |
| 172 | SourceBuffer. For tokens that include them, this length includes trigraphs and |
| 173 | escaped newlines which are ignored by later phases of the compiler. By pointing |
| 174 | into the original source buffer, it is always possible to get the original |
| 175 | spelling of a token completely accurately.</li> |
| 176 | |
| 177 | <li><b>IdentifierInfo</b> - If a token takes the form of an identifier, and if |
| 178 | identifier lookup was enabled when the token was lexed (e.g. the lexer was not |
| 179 | reading in 'raw' mode) this contains a pointer to the unique hash value for the |
| 180 | identifier. Because the lookup happens before keyword identification, this |
| 181 | field is set even for language keywords like 'for'.</li> |
| 182 | |
| 183 | <li><b>TokenKind</b> - This indicates the kind of token as classified by the |
| 184 | lexer. This includes things like <tt>tok::starequal</tt> (for the "*=" |
| 185 | operator), <tt>tok::ampamp</tt> for the "&&" token, and keyword values |
| 186 | (e.g. <tt>tok::kw_for</tt>) for identifiers that correspond to keywords. Note |
| 187 | that some tokens can be spelled multiple ways. For example, C++ supports |
| 188 | "operator keywords", where things like "and" are treated exactly like the |
| 189 | "&&" operator. In these cases, the kind value is set to |
| 190 | <tt>tok::ampamp</tt>, which is good for the parser, which doesn't have to |
| 191 | consider both forms. For something that cares about which form is used (e.g. |
| 192 | the preprocessor 'stringize' operator) the spelling indicates the original |
| 193 | form.</li> |
| 194 | |
| 195 | <li><b>Flags</b> - There are currently four flags tracked by the |
| 196 | lexer/preprocessor system on a per-token basis: |
| 197 | |
| 198 | <ol> |
| 199 | <li><b>StartOfLine</b> - This was the first token that occurred on its input |
| 200 | source line.</li> |
| 201 | <li><b>LeadingSpace</b> - There was a space character either immediately |
| 202 | before the token or transitively before the token as it was expanded |
| 203 | through a macro. The definition of this flag is very closely defined by |
| 204 | the stringizing requirements of the preprocessor.</li> |
| 205 | <li><b>DisableExpand</b> - This flag is used internally to the preprocessor to |
| 206 | represent identifier tokens which have macro expansion disabled. This |
| 207 | prevents them from being considered as candidates for macro expansion ever |
| 208 | in the future.</li> |
| 209 | <li><b>NeedsCleaning</b> - This flag is set if the original spelling for the |
| 210 | token includes a trigraph or escaped newline. Since this is uncommon, |
| 211 | many pieces of code can fast-path on tokens that did not need cleaning. |
| 212 | </p> |
| 213 | </ol> |
| 214 | </li> |
| 215 | </ul> |
| 216 | |
| 217 | <p>One interesting (and somewhat unusual) aspect of tokens is that they don't |
| 218 | contain any semantic information about the lexed value. For example, if the |
| 219 | token was a pp-number token, we do not represent the value of the number that |
| 220 | was lexed (this is left for later pieces of code to decide). Additionally, the |
| 221 | lexer library has no notion of typedef names vs variable names: both are |
| 222 | returned as identifiers, and the parser is left to decide whether a specific |
| 223 | identifier is a typedef or a variable (tracking this requires scope information |
| 224 | among other things).</p> |
| 225 | |
| 226 | <!-- ======================================================================= --> |
| 227 | <h3 id="Lexer">The Lexer class</h3> |
| 228 | <!-- ======================================================================= --> |
| 229 | |
| 230 | <p>The Lexer class provides the mechanics of lexing tokens out of a source |
| 231 | buffer and deciding what they mean. The Lexer is complicated by the fact that |
| 232 | it operates on raw buffers that have not had spelling eliminated (this is a |
| 233 | necessity to get decent performance), but this is countered with careful coding |
| 234 | as well as standard performance techniques (for example, the comment handling |
| 235 | code is vectorized on X86 and PowerPC hosts).</p> |
| 236 | |
| 237 | <p>The lexer has a couple of interesting modal features:</p> |
| 238 | |
| 239 | <ul> |
| 240 | <li>The lexer can operate in 'raw' mode. This mode has several features that |
| 241 | make it possible to quickly lex the file (e.g. it stops identifier lookup, |
| 242 | doesn't specially handle preprocessor tokens, handles EOF differently, etc). |
| 243 | This mode is used for lexing within an "<tt>#if 0</tt>" block, for |
| 244 | example.</li> |
| 245 | <li>The lexer can capture and return comments as tokens. This is required to |
| 246 | support the -C preprocessor mode, which passes comments through, and is |
| 247 | used by the diagnostic checker to identifier expect-error annotations.</li> |
| 248 | <li>The lexer can be in ParsingFilename mode, which happens when preprocessing |
Chris Lattner | 8438624 | 2007-09-16 19:25:23 +0000 | [diff] [blame] | 249 | after reading a #include directive. This mode changes the parsing of '<' |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 250 | to return an "angled string" instead of a bunch of tokens for each thing |
| 251 | within the filename.</li> |
| 252 | <li>When parsing a preprocessor directive (after "<tt>#</tt>") the |
| 253 | ParsingPreprocessorDirective mode is entered. This changes the parser to |
| 254 | return EOM at a newline.</li> |
| 255 | <li>The Lexer uses a LangOptions object to know whether trigraphs are enabled, |
| 256 | whether C++ or ObjC keywords are recognized, etc.</li> |
| 257 | </ul> |
| 258 | |
| 259 | <p>In addition to these modes, the lexer keeps track of a couple of other |
| 260 | features that are local to a lexed buffer, which change as the buffer is |
| 261 | lexed:</p> |
| 262 | |
| 263 | <ul> |
| 264 | <li>The Lexer uses BufferPtr to keep track of the current character being |
| 265 | lexed.</li> |
| 266 | <li>The Lexer uses IsAtStartOfLine to keep track of whether the next lexed token |
| 267 | will start with its "start of line" bit set.</li> |
| 268 | <li>The Lexer keeps track of the current #if directives that are active (which |
| 269 | can be nested).</li> |
| 270 | <li>The Lexer keeps track of an <a href="#MultipleIncludeOpt"> |
| 271 | MultipleIncludeOpt</a> object, which is used to |
| 272 | detect whether the buffer uses the standard "<tt>#ifndef XX</tt> / |
| 273 | <tt>#define XX</tt>" idiom to prevent multiple inclusion. If a buffer does, |
| 274 | subsequent includes can be ignored if the XX macro is defined.</li> |
| 275 | </ul> |
| 276 | |
| 277 | <!-- ======================================================================= --> |
Chris Lattner | 7928125 | 2008-03-09 02:27:26 +0000 | [diff] [blame] | 278 | <h3 id="TokenLexer">The TokenLexer class</h3> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 279 | <!-- ======================================================================= --> |
| 280 | |
Chris Lattner | 7928125 | 2008-03-09 02:27:26 +0000 | [diff] [blame] | 281 | <p>The TokenLexer class is a token provider that returns tokens from a list |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 282 | of tokens that came from somewhere else. It typically used for two things: 1) |
| 283 | returning tokens from a macro definition as it is being expanded 2) returning |
| 284 | tokens from an arbitrary buffer of tokens. The later use is used by _Pragma and |
| 285 | will most likely be used to handle unbounded look-ahead for the C++ parser.</p> |
| 286 | |
| 287 | <!-- ======================================================================= --> |
| 288 | <h3 id="MultipleIncludeOpt">The MultipleIncludeOpt class</h3> |
| 289 | <!-- ======================================================================= --> |
| 290 | |
| 291 | <p>The MultipleIncludeOpt class implements a really simple little state machine |
| 292 | that is used to detect the standard "<tt>#ifndef XX</tt> / <tt>#define XX</tt>" |
| 293 | idiom that people typically use to prevent multiple inclusion of headers. If a |
| 294 | buffer uses this idiom and is subsequently #include'd, the preprocessor can |
| 295 | simply check to see whether the guarding condition is defined or not. If so, |
| 296 | the preprocessor can completely ignore the include of the header.</p> |
| 297 | |
| 298 | |
| 299 | |
| 300 | <!-- ======================================================================= --> |
| 301 | <h2 id="libparse">The Parser Library</h2> |
| 302 | <!-- ======================================================================= --> |
| 303 | |
| 304 | <!-- ======================================================================= --> |
| 305 | <h2 id="libast">The AST Library</h2> |
| 306 | <!-- ======================================================================= --> |
| 307 | |
| 308 | <!-- ======================================================================= --> |
| 309 | <h3 id="Type">The Type class and its subclasses</h3> |
| 310 | <!-- ======================================================================= --> |
| 311 | |
| 312 | <p>The Type class (and its subclasses) are an important part of the AST. Types |
| 313 | are accessed through the ASTContext class, which implicitly creates and uniques |
| 314 | them as they are needed. Types have a couple of non-obvious features: 1) they |
| 315 | do not capture type qualifiers like const or volatile (See |
| 316 | <a href="#QualType">QualType</a>), and 2) they implicitly capture typedef |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 317 | information. Once created, types are immutable (unlike decls).</p> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 318 | |
| 319 | <p>Typedefs in C make semantic analysis a bit more complex than it would |
| 320 | be without them. The issue is that we want to capture typedef information |
| 321 | and represent it in the AST perfectly, but the semantics of operations need to |
| 322 | "see through" typedefs. For example, consider this code:</p> |
| 323 | |
| 324 | <code> |
| 325 | void func() {<br> |
Bill Wendling | 30d1775 | 2007-10-06 01:56:01 +0000 | [diff] [blame] | 326 | typedef int foo;<br> |
| 327 | foo X, *Y;<br> |
| 328 | typedef foo* bar;<br> |
| 329 | bar Z;<br> |
| 330 | *X; <i>// error</i><br> |
| 331 | **Y; <i>// error</i><br> |
| 332 | **Z; <i>// error</i><br> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 333 | }<br> |
| 334 | </code> |
| 335 | |
| 336 | <p>The code above is illegal, and thus we expect there to be diagnostics emitted |
| 337 | on the annotated lines. In this example, we expect to get:</p> |
| 338 | |
| 339 | <pre> |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 340 | <b>test.c:6:1: error: indirection requires pointer operand ('foo' invalid)</b> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 341 | *X; // error |
| 342 | <font color="blue">^~</font> |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 343 | <b>test.c:7:1: error: indirection requires pointer operand ('foo' invalid)</b> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 344 | **Y; // error |
| 345 | <font color="blue">^~~</font> |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 346 | <b>test.c:8:1: error: indirection requires pointer operand ('foo' invalid)</b> |
| 347 | **Z; // error |
| 348 | <font color="blue">^~~</font> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 349 | </pre> |
| 350 | |
| 351 | <p>While this example is somewhat silly, it illustrates the point: we want to |
| 352 | retain typedef information where possible, so that we can emit errors about |
| 353 | "<tt>std::string</tt>" instead of "<tt>std::basic_string<char, std:...</tt>". |
| 354 | Doing this requires properly keeping typedef information (for example, the type |
| 355 | of "X" is "foo", not "int"), and requires properly propagating it through the |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 356 | various operators (for example, the type of *Y is "foo", not "int"). In order |
| 357 | to retain this information, the type of these expressions is an instance of the |
| 358 | TypedefType class, which indicates that the type of these expressions is a |
| 359 | typedef for foo. |
| 360 | </p> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 361 | |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 362 | <p>Representing types like this is great for diagnostics, because the |
| 363 | user-specified type is always immediately available. There are two problems |
| 364 | with this: first, various semantic checks need to make judgements about the |
Chris Lattner | 33fc68a | 2007-07-31 18:54:50 +0000 | [diff] [blame] | 365 | <em>actual structure</em> of a type, ignoring typdefs. Second, we need an |
| 366 | efficient way to query whether two types are structurally identical to each |
| 367 | other, ignoring typedefs. The solution to both of these problems is the idea of |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 368 | canonical types.</p> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 369 | |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 370 | <h4>Canonical Types</h4> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 371 | |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 372 | <p>Every instance of the Type class contains a canonical type pointer. For |
| 373 | simple types with no typedefs involved (e.g. "<tt>int</tt>", "<tt>int*</tt>", |
| 374 | "<tt>int**</tt>"), the type just points to itself. For types that have a |
| 375 | typedef somewhere in their structure (e.g. "<tt>foo</tt>", "<tt>foo*</tt>", |
| 376 | "<tt>foo**</tt>", "<tt>bar</tt>"), the canonical type pointer points to their |
| 377 | structurally equivalent type without any typedefs (e.g. "<tt>int</tt>", |
| 378 | "<tt>int*</tt>", "<tt>int**</tt>", and "<tt>int*</tt>" respectively).</p> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 379 | |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 380 | <p>This design provides a constant time operation (dereferencing the canonical |
| 381 | type pointer) that gives us access to the structure of types. For example, |
| 382 | we can trivially tell that "bar" and "foo*" are the same type by dereferencing |
| 383 | their canonical type pointers and doing a pointer comparison (they both point |
| 384 | to the single "<tt>int*</tt>" type).</p> |
| 385 | |
| 386 | <p>Canonical types and typedef types bring up some complexities that must be |
| 387 | carefully managed. Specifically, the "isa/cast/dyncast" operators generally |
| 388 | shouldn't be used in code that is inspecting the AST. For example, when type |
| 389 | checking the indirection operator (unary '*' on a pointer), the type checker |
| 390 | must verify that the operand has a pointer type. It would not be correct to |
| 391 | check that with "<tt>isa<PointerType>(SubExpr->getType())</tt>", |
| 392 | because this predicate would fail if the subexpression had a typedef type.</p> |
| 393 | |
| 394 | <p>The solution to this problem are a set of helper methods on Type, used to |
| 395 | check their properties. In this case, it would be correct to use |
| 396 | "<tt>SubExpr->getType()->isPointerType()</tt>" to do the check. This |
| 397 | predicate will return true if the <em>canonical type is a pointer</em>, which is |
| 398 | true any time the type is structurally a pointer type. The only hard part here |
| 399 | is remembering not to use the <tt>isa/cast/dyncast</tt> operations.</p> |
| 400 | |
| 401 | <p>The second problem we face is how to get access to the pointer type once we |
| 402 | know it exists. To continue the example, the result type of the indirection |
| 403 | operator is the pointee type of the subexpression. In order to determine the |
| 404 | type, we need to get the instance of PointerType that best captures the typedef |
| 405 | information in the program. If the type of the expression is literally a |
| 406 | PointerType, we can return that, otherwise we have to dig through the |
| 407 | typedefs to find the pointer type. For example, if the subexpression had type |
| 408 | "<tt>foo*</tt>", we could return that type as the result. If the subexpression |
| 409 | had type "<tt>bar</tt>", we want to return "<tt>foo*</tt>" (note that we do |
| 410 | <em>not</em> want "<tt>int*</tt>"). In order to provide all of this, Type has |
Chris Lattner | 11406c1 | 2007-07-31 16:50:51 +0000 | [diff] [blame] | 411 | a getAsPointerType() method that checks whether the type is structurally a |
Chris Lattner | 8a2bc62 | 2007-07-31 06:37:39 +0000 | [diff] [blame] | 412 | PointerType and, if so, returns the best one. If not, it returns a null |
| 413 | pointer.</p> |
| 414 | |
| 415 | <p>This structure is somewhat mystical, but after meditating on it, it will |
| 416 | make sense to you :).</p> |
Chris Lattner | 86920d3 | 2007-07-31 05:42:17 +0000 | [diff] [blame] | 417 | |
| 418 | <!-- ======================================================================= --> |
| 419 | <h3 id="QualType">The QualType class</h3> |
| 420 | <!-- ======================================================================= --> |
| 421 | |
| 422 | <p>The QualType class is designed as a trivial value class that is small, |
| 423 | passed by-value and is efficient to query. The idea of QualType is that it |
| 424 | stores the type qualifiers (const, volatile, restrict) separately from the types |
| 425 | themselves: QualType is conceptually a pair of "Type*" and bits for the type |
| 426 | qualifiers.</p> |
| 427 | |
| 428 | <p>By storing the type qualifiers as bits in the conceptual pair, it is |
| 429 | extremely efficient to get the set of qualifiers on a QualType (just return the |
| 430 | field of the pair), add a type qualifier (which is a trivial constant-time |
| 431 | operation that sets a bit), and remove one or more type qualifiers (just return |
| 432 | a QualType with the bitfield set to empty).</p> |
| 433 | |
| 434 | <p>Further, because the bits are stored outside of the type itself, we do not |
| 435 | need to create duplicates of types with different sets of qualifiers (i.e. there |
| 436 | is only a single heap allocated "int" type: "const int" and "volatile const int" |
| 437 | both point to the same heap allocated "int" type). This reduces the heap size |
| 438 | used to represent bits and also means we do not have to consider qualifiers when |
| 439 | uniquing types (<a href="#Type">Type</a> does not even contain qualifiers).</p> |
| 440 | |
| 441 | <p>In practice, on hosts where it is safe, the 3 type qualifiers are stored in |
| 442 | the low bit of the pointer to the Type object. This means that QualType is |
| 443 | exactly the same size as a pointer, and this works fine on any system where |
| 444 | malloc'd objects are at least 8 byte aligned.</p> |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 445 | |
| 446 | <!-- ======================================================================= --> |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 447 | <h3 id="DeclarationName">Declaration names</h3> |
| 448 | <!-- ======================================================================= --> |
| 449 | |
| 450 | <p>The <tt>DeclarationName</tt> class represents the name of a |
| 451 | declaration in Clang. Declarations in the C family of languages can |
| 452 | take several different forms. Most declarations are named by are |
| 453 | simple identifiers, e.g., "<code>f</code>" and "<code>x</code>" in |
| 454 | the function declaration <code>f(int x)</code>. In C++, declaration |
| 455 | names can also name class constructors ("<code>Class</code>" |
| 456 | in <code>struct Class { Class(); }</code>), class destructors |
| 457 | ("<code>~Class</code>"), overloaded operator names ("operator+"), |
| 458 | and conversion functions ("<code>operator void const *</code>"). In |
| 459 | Objective-C, declaration names can refer to the names of Objective-C |
| 460 | methods, which involve the method name and the parameters, |
| 461 | collectively called a <i>selector</i>, e.g.., |
| 462 | "<code>setWidth:height:</code>". Since all of these kinds of |
| 463 | entities--variables, functions, Objective-C methods, C++ |
| 464 | constructors, destructors, and operators---are represented as |
| 465 | subclasses of Clang's common <code>NamedDecl</code> |
| 466 | class, <code>DeclarationName</code> is designed to efficiently |
| 467 | represent any kind of name.</p> |
| 468 | |
| 469 | <p>Given |
| 470 | a <code>DeclarationName</code> <code>N</code>, <code>N.getNameKind()</code> |
Douglas Gregor | 2def483 | 2008-11-17 20:34:05 +0000 | [diff] [blame] | 471 | will produce a value that describes what kind of name <code>N</code> |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 472 | stores. There are 8 options (all of the names are inside |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 473 | the <code>DeclarationName</code> class)</p> |
| 474 | <dl> |
| 475 | <dt>Identifier</dt> |
| 476 | <dd>The name is a simple |
| 477 | identifier. Use <code>N.getAsIdentifierInfo()</code> to retrieve the |
| 478 | corresponding <code>IdentifierInfo*</code> pointing to the actual |
| 479 | identifier. Note that C++ overloaded operators (e.g., |
| 480 | "<code>operator+</code>") are represented as special kinds of |
| 481 | identifiers. Use <code>IdentifierInfo</code>'s <code>getOverloadedOperatorID</code> |
| 482 | function to determine whether an identifier is an overloaded |
| 483 | operator name.</dd> |
| 484 | |
| 485 | <dt>ObjCZeroArgSelector, ObjCOneArgSelector, |
| 486 | ObjCMultiArgSelector</dt> |
| 487 | <dd>The name is an Objective-C selector, which can be retrieved as a |
| 488 | <code>Selector</code> instance |
| 489 | via <code>N.getObjCSelector()</code>. The three possible name |
| 490 | kinds for Objective-C reflect an optimization within |
| 491 | the <code>DeclarationName</code> class: both zero- and |
| 492 | one-argument selectors are stored as a |
| 493 | masked <code>IdentifierInfo</code> pointer, and therefore require |
| 494 | very little space, since zero- and one-argument selectors are far |
| 495 | more common than multi-argument selectors (which use a different |
| 496 | structure).</dd> |
| 497 | |
| 498 | <dt>CXXConstructorName</dt> |
| 499 | <dd>The name is a C++ constructor |
| 500 | name. Use <code>N.getCXXNameType()</code> to retrieve |
| 501 | the <a href="#QualType">type</a> that this constructor is meant to |
| 502 | construct. The type is always the canonical type, since all |
| 503 | constructors for a given type have the same name.</dd> |
| 504 | |
| 505 | <dt>CXXDestructorName</dt> |
| 506 | <dd>The name is a C++ destructor |
| 507 | name. Use <code>N.getCXXNameType()</code> to retrieve |
| 508 | the <a href="#QualType">type</a> whose destructor is being |
| 509 | named. This type is always a canonical type.</dd> |
| 510 | |
| 511 | <dt>CXXConversionFunctionName</dt> |
| 512 | <dd>The name is a C++ conversion function. Conversion functions are |
| 513 | named according to the type they convert to, e.g., "<code>operator void |
| 514 | const *</code>". Use <code>N.getCXXNameType()</code> to retrieve |
| 515 | the type that this conversion function converts to. This type is |
| 516 | always a canonical type.</dd> |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 517 | |
| 518 | <dt>CXXOperatorName</dt> |
| 519 | <dd>The name is a C++ overloaded operator name. Overloaded operators |
| 520 | are named according to their spelling, e.g., |
| 521 | "<code>operator+</code>" or "<code>operator new |
| 522 | []</code>". Use <code>N.getCXXOverloadedOperator()</code> to |
| 523 | retrieve the overloaded operator (a value of |
| 524 | type <code>OverloadedOperatorKind</code>).</dd> |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 525 | </dl> |
| 526 | |
| 527 | <p><code>DeclarationName</code>s are cheap to create, copy, and |
| 528 | compare. They require only a single pointer's worth of storage in |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 529 | the common cases (identifiers, zero- |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 530 | and one-argument Objective-C selectors) and use dense, uniqued |
| 531 | storage for the other kinds of |
| 532 | names. Two <code>DeclarationName</code>s can be compared for |
| 533 | equality (<code>==</code>, <code>!=</code>) using a simple bitwise |
| 534 | comparison, can be ordered |
| 535 | with <code><</code>, <code>></code>, <code><=</code>, |
| 536 | and <code>>=</code> (which provide a lexicographical ordering for |
| 537 | normal identifiers but an unspecified ordering for other kinds of |
| 538 | names), and can be placed into LLVM <code>DenseMap</code>s |
| 539 | and <code>DenseSet</code>s.</p> |
| 540 | |
| 541 | <p><code>DeclarationName</code> instances can be created in different |
| 542 | ways depending on what kind of name the instance will store. Normal |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 543 | identifiers (<code>IdentifierInfo</code> pointers) and Objective-C selectors |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 544 | (<code>Selector</code>) can be implicitly converted |
| 545 | to <code>DeclarationName</code>s. Names for C++ constructors, |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 546 | destructors, conversion functions, and overloaded operators can be retrieved from |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 547 | the <code>DeclarationNameTable</code>, an instance of which is |
| 548 | available as <code>ASTContext::DeclarationNames</code>. The member |
| 549 | functions <code>getCXXConstructorName</code>, <code>getCXXDestructorName</code>, |
Douglas Gregor | e94ca9e4 | 2008-11-18 14:39:36 +0000 | [diff] [blame] | 550 | <code>getCXXConversionFunctionName</code>, and <code>getCXXOperatorName</code>, respectively, |
| 551 | return <code>DeclarationName</code> instances for the four kinds of |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 552 | C++ special function names.</p> |
| 553 | |
| 554 | <!-- ======================================================================= --> |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 555 | <h3 id="CFG">The <tt>CFG</tt> class</h3> |
| 556 | <!-- ======================================================================= --> |
| 557 | |
| 558 | <p>The <tt>CFG</tt> class is designed to represent a source-level |
| 559 | control-flow graph for a single statement (<tt>Stmt*</tt>). Typically |
| 560 | instances of <tt>CFG</tt> are constructed for function bodies (usually |
| 561 | an instance of <tt>CompoundStmt</tt>), but can also be instantiated to |
| 562 | represent the control-flow of any class that subclasses <tt>Stmt</tt>, |
| 563 | which includes simple expressions. Control-flow graphs are especially |
| 564 | useful for performing |
| 565 | <a href="http://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities">flow- |
| 566 | or path-sensitive</a> program analyses on a given function.</p> |
| 567 | |
| 568 | <h4>Basic Blocks</h4> |
| 569 | |
| 570 | <p>Concretely, an instance of <tt>CFG</tt> is a collection of basic |
| 571 | blocks. Each basic block is an instance of <tt>CFGBlock</tt>, which |
| 572 | simply contains an ordered sequence of <tt>Stmt*</tt> (each referring |
| 573 | to statements in the AST). The ordering of statements within a block |
| 574 | indicates unconditional flow of control from one statement to the |
| 575 | next. <a href="#ConditionalControlFlow">Conditional control-flow</a> |
| 576 | is represented using edges between basic blocks. The statements |
| 577 | within a given <tt>CFGBlock</tt> can be traversed using |
| 578 | the <tt>CFGBlock::*iterator</tt> interface.</p> |
| 579 | |
| 580 | <p> |
Ted Kremenek | 18e17e7 | 2007-10-18 22:50:52 +0000 | [diff] [blame] | 581 | A <tt>CFG</tt> object owns the instances of <tt>CFGBlock</tt> within |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 582 | the control-flow graph it represents. Each <tt>CFGBlock</tt> within a |
| 583 | CFG is also uniquely numbered (accessible |
| 584 | via <tt>CFGBlock::getBlockID()</tt>). Currently the number is |
| 585 | based on the ordering the blocks were created, but no assumptions |
| 586 | should be made on how <tt>CFGBlock</tt>s are numbered other than their |
| 587 | numbers are unique and that they are numbered from 0..N-1 (where N is |
| 588 | the number of basic blocks in the CFG).</p> |
| 589 | |
| 590 | <h4>Entry and Exit Blocks</h4> |
| 591 | |
| 592 | Each instance of <tt>CFG</tt> contains two special blocks: |
| 593 | an <i>entry</i> block (accessible via <tt>CFG::getEntry()</tt>), which |
| 594 | has no incoming edges, and an <i>exit</i> block (accessible |
| 595 | via <tt>CFG::getExit()</tt>), which has no outgoing edges. Neither |
| 596 | block contains any statements, and they serve the role of providing a |
| 597 | clear entrance and exit for a body of code such as a function body. |
| 598 | The presence of these empty blocks greatly simplifies the |
| 599 | implementation of many analyses built on top of CFGs. |
| 600 | |
| 601 | <h4 id ="ConditionalControlFlow">Conditional Control-Flow</h4> |
| 602 | |
| 603 | <p>Conditional control-flow (such as those induced by if-statements |
| 604 | and loops) is represented as edges between <tt>CFGBlock</tt>s. |
| 605 | Because different C language constructs can induce control-flow, |
| 606 | each <tt>CFGBlock</tt> also records an extra <tt>Stmt*</tt> that |
| 607 | represents the <i>terminator</i> of the block. A terminator is simply |
| 608 | the statement that caused the control-flow, and is used to identify |
| 609 | the nature of the conditional control-flow between blocks. For |
| 610 | example, in the case of an if-statement, the terminator refers to |
| 611 | the <tt>IfStmt</tt> object in the AST that represented the given |
| 612 | branch.</p> |
| 613 | |
| 614 | <p>To illustrate, consider the following code example:</p> |
| 615 | |
| 616 | <code> |
| 617 | int foo(int x) {<br> |
| 618 | x = x + 1;<br> |
| 619 | <br> |
| 620 | if (x > 2) x++;<br> |
| 621 | else {<br> |
| 622 | x += 2;<br> |
| 623 | x *= 2;<br> |
| 624 | }<br> |
| 625 | <br> |
| 626 | return x;<br> |
| 627 | } |
| 628 | </code> |
| 629 | |
| 630 | <p>After invoking the parser+semantic analyzer on this code fragment, |
| 631 | the AST of the body of <tt>foo</tt> is referenced by a |
| 632 | single <tt>Stmt*</tt>. We can then construct an instance |
| 633 | of <tt>CFG</tt> representing the control-flow graph of this function |
| 634 | body by single call to a static class method:</p> |
| 635 | |
| 636 | <code> |
| 637 | Stmt* FooBody = ...<br> |
| 638 | CFG* FooCFG = <b>CFG::buildCFG</b>(FooBody); |
| 639 | </code> |
| 640 | |
| 641 | <p>It is the responsibility of the caller of <tt>CFG::buildCFG</tt> |
| 642 | to <tt>delete</tt> the returned <tt>CFG*</tt> when the CFG is no |
| 643 | longer needed.</p> |
| 644 | |
| 645 | <p>Along with providing an interface to iterate over |
| 646 | its <tt>CFGBlock</tt>s, the <tt>CFG</tt> class also provides methods |
| 647 | that are useful for debugging and visualizing CFGs. For example, the |
| 648 | method |
| 649 | <tt>CFG::dump()</tt> dumps a pretty-printed version of the CFG to |
| 650 | standard error. This is especially useful when one is using a |
| 651 | debugger such as gdb. For example, here is the output |
| 652 | of <tt>FooCFG->dump()</tt>:</p> |
| 653 | |
| 654 | <code> |
| 655 | [ B5 (ENTRY) ]<br> |
| 656 | Predecessors (0):<br> |
| 657 | Successors (1): B4<br> |
| 658 | <br> |
| 659 | [ B4 ]<br> |
| 660 | 1: x = x + 1<br> |
| 661 | 2: (x > 2)<br> |
| 662 | <b>T: if [B4.2]</b><br> |
| 663 | Predecessors (1): B5<br> |
| 664 | Successors (2): B3 B2<br> |
| 665 | <br> |
| 666 | [ B3 ]<br> |
| 667 | 1: x++<br> |
| 668 | Predecessors (1): B4<br> |
| 669 | Successors (1): B1<br> |
| 670 | <br> |
| 671 | [ B2 ]<br> |
| 672 | 1: x += 2<br> |
| 673 | 2: x *= 2<br> |
| 674 | Predecessors (1): B4<br> |
| 675 | Successors (1): B1<br> |
| 676 | <br> |
| 677 | [ B1 ]<br> |
| 678 | 1: return x;<br> |
| 679 | Predecessors (2): B2 B3<br> |
| 680 | Successors (1): B0<br> |
| 681 | <br> |
| 682 | [ B0 (EXIT) ]<br> |
| 683 | Predecessors (1): B1<br> |
| 684 | Successors (0): |
| 685 | </code> |
| 686 | |
| 687 | <p>For each block, the pretty-printed output displays for each block |
| 688 | the number of <i>predecessor</i> blocks (blocks that have outgoing |
| 689 | control-flow to the given block) and <i>successor</i> blocks (blocks |
| 690 | that have control-flow that have incoming control-flow from the given |
| 691 | block). We can also clearly see the special entry and exit blocks at |
| 692 | the beginning and end of the pretty-printed output. For the entry |
| 693 | block (block B5), the number of predecessor blocks is 0, while for the |
| 694 | exit block (block B0) the number of successor blocks is 0.</p> |
| 695 | |
| 696 | <p>The most interesting block here is B4, whose outgoing control-flow |
| 697 | represents the branching caused by the sole if-statement |
| 698 | in <tt>foo</tt>. Of particular interest is the second statement in |
| 699 | the block, <b><tt>(x > 2)</tt></b>, and the terminator, printed |
| 700 | as <b><tt>if [B4.2]</tt></b>. The second statement represents the |
| 701 | evaluation of the condition of the if-statement, which occurs before |
| 702 | the actual branching of control-flow. Within the <tt>CFGBlock</tt> |
| 703 | for B4, the <tt>Stmt*</tt> for the second statement refers to the |
| 704 | actual expression in the AST for <b><tt>(x > 2)</tt></b>. Thus |
| 705 | pointers to subclasses of <tt>Expr</tt> can appear in the list of |
| 706 | statements in a block, and not just subclasses of <tt>Stmt</tt> that |
| 707 | refer to proper C statements.</p> |
| 708 | |
| 709 | <p>The terminator of block B4 is a pointer to the <tt>IfStmt</tt> |
| 710 | object in the AST. The pretty-printer outputs <b><tt>if |
| 711 | [B4.2]</tt></b> because the condition expression of the if-statement |
| 712 | has an actual place in the basic block, and thus the terminator is |
| 713 | essentially |
| 714 | <i>referring</i> to the expression that is the second statement of |
| 715 | block B4 (i.e., B4.2). In this manner, conditions for control-flow |
| 716 | (which also includes conditions for loops and switch statements) are |
| 717 | hoisted into the actual basic block.</p> |
| 718 | |
Ted Kremenek | 98f19b6 | 2007-10-10 23:22:00 +0000 | [diff] [blame] | 719 | <!-- |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 720 | <h4>Implicit Control-Flow</h4> |
Ted Kremenek | 98f19b6 | 2007-10-10 23:22:00 +0000 | [diff] [blame] | 721 | --> |
Ted Kremenek | 8bc0571 | 2007-10-10 23:01:43 +0000 | [diff] [blame] | 722 | |
| 723 | <!-- |
| 724 | <p>A key design principle of the <tt>CFG</tt> class was to not require |
| 725 | any transformations to the AST in order to represent control-flow. |
| 726 | Thus the <tt>CFG</tt> does not perform any "lowering" of the |
| 727 | statements in an AST: loops are not transformed into guarded gotos, |
| 728 | short-circuit operations are not converted to a set of if-statements, |
| 729 | and so on.</p> |
| 730 | --> |
Ted Kremenek | 17a295d | 2008-06-11 06:19:49 +0000 | [diff] [blame] | 731 | |
Chris Lattner | 7bad199 | 2008-11-16 21:48:07 +0000 | [diff] [blame] | 732 | |
| 733 | <!-- ======================================================================= --> |
| 734 | <h3 id="Constants">Constant Folding in the Clang AST</h3> |
| 735 | <!-- ======================================================================= --> |
| 736 | |
| 737 | <p>There are several places where constants and constant folding matter a lot to |
| 738 | the Clang front-end. First, in general, we prefer the AST to retain the source |
| 739 | code as close to how the user wrote it as possible. This means that if they |
| 740 | wrote "5+4", we want to keep the addition and two constants in the AST, we don't |
| 741 | want to fold to "9". This means that constant folding in various ways turns |
| 742 | into a tree walk that needs to handle the various cases.</p> |
| 743 | |
| 744 | <p>However, there are places in both C and C++ that require constants to be |
| 745 | folded. For example, the C standard defines what an "integer constant |
| 746 | expression" (i-c-e) is with very precise and specific requirements. The |
| 747 | language then requires i-c-e's in a lot of places (for example, the size of a |
| 748 | bitfield, the value for a case statement, etc). For these, we have to be able |
| 749 | to constant fold the constants, to do semantic checks (e.g. verify bitfield size |
| 750 | is non-negative and that case statements aren't duplicated). We aim for Clang |
| 751 | to be very pedantic about this, diagnosing cases when the code does not use an |
| 752 | i-c-e where one is required, but accepting the code unless running with |
| 753 | <tt>-pedantic-errors</tt>.</p> |
| 754 | |
| 755 | <p>Things get a little bit more tricky when it comes to compatibility with |
| 756 | real-world source code. Specifically, GCC has historically accepted a huge |
| 757 | superset of expressions as i-c-e's, and a lot of real world code depends on this |
| 758 | unfortuate accident of history (including, e.g., the glibc system headers). GCC |
| 759 | accepts anything its "fold" optimizer is capable of reducing to an integer |
| 760 | constant, which means that the definition of what it accepts changes as its |
| 761 | optimizer does. One example is that GCC accepts things like "case X-X:" even |
| 762 | when X is a variable, because it can fold this to 0.</p> |
| 763 | |
| 764 | <p>Another issue are how constants interact with the extensions we support, such |
| 765 | as __builtin_constant_p, __builtin_inf, __extension__ and many others. C99 |
| 766 | obviously does not specify the semantics of any of these extensions, and the |
| 767 | definition of i-c-e does not include them. However, these extensions are often |
| 768 | used in real code, and we have to have a way to reason about them.</p> |
| 769 | |
| 770 | <p>Finally, this is not just a problem for semantic analysis. The code |
| 771 | generator and other clients have to be able to fold constants (e.g. to |
| 772 | initialize global variables) and has to handle a superset of what C99 allows. |
| 773 | Further, these clients can benefit from extended information. For example, we |
| 774 | know that "foo()||1" always evaluates to true, but we can't replace the |
| 775 | expression with true because it has side effects.</p> |
| 776 | |
| 777 | <!-- ======================= --> |
| 778 | <h4>Implementation Approach</h4> |
| 779 | <!-- ======================= --> |
| 780 | |
| 781 | <p>After trying several different approaches, we've finally converged on a |
| 782 | design (Note, at the time of this writing, not all of this has been implemented, |
| 783 | consider this a design goal!). Our basic approach is to define a single |
| 784 | recursive method evaluation method (<tt>Expr::Evaluate</tt>), which is |
| 785 | implemented in <tt>AST/ExprConstant.cpp</tt>. Given an expression with 'scalar' |
| 786 | type (integer, fp, complex, or pointer) this method returns the following |
| 787 | information:</p> |
| 788 | |
| 789 | <ul> |
| 790 | <li>Whether the expression is an integer constant expression, a general |
| 791 | constant that was folded but has no side effects, a general constant that |
| 792 | was folded but that does have side effects, or an uncomputable/unfoldable |
| 793 | value. |
| 794 | </li> |
| 795 | <li>If the expression was computable in any way, this method returns the APValue |
| 796 | for the result of the expression.</li> |
| 797 | <li>If the expression is not evaluatable at all, this method returns |
| 798 | information on one of the problems with the expression. This includes a |
| 799 | SourceLocation for where the problem is, and a diagnostic ID that explains |
| 800 | the problem. The diagnostic should be have ERROR type.</li> |
| 801 | <li>If the expression is not an integer constant expression, this method returns |
| 802 | information on one of the problems with the expression. This includes a |
| 803 | SourceLocation for where the problem is, and a diagnostic ID that explains |
| 804 | the problem. The diagnostic should be have EXTENSION type.</li> |
| 805 | </ul> |
| 806 | |
| 807 | <p>This information gives various clients the flexibility that they want, and we |
| 808 | will eventually have some helper methods for various extensions. For example, |
| 809 | Sema should have a <tt>Sema::VerifyIntegerConstantExpression</tt> method, which |
| 810 | calls Evaluate on the expression. If the expression is not foldable, the error |
| 811 | is emitted, and it would return true. If the expression is not an i-c-e, the |
| 812 | EXTENSION diagnostic is emitted. Finally it would return false to indicate that |
| 813 | the AST is ok.</p> |
| 814 | |
| 815 | <p>Other clients can use the information in other ways, for example, codegen can |
| 816 | just use expressions that are foldable in any way.</p> |
| 817 | |
| 818 | <!-- ========== --> |
| 819 | <h4>Extensions</h4> |
| 820 | <!-- ========== --> |
| 821 | |
| 822 | <p>This section describes how some of the various extensions clang supports |
| 823 | interacts with constant evaluation:</p> |
| 824 | |
| 825 | <ul> |
| 826 | <li><b><tt>__extension__</tt></b>: The expression form of this extension causes |
| 827 | any evaluatable subexpression to be accepted as an integer constant |
| 828 | expression.</li> |
| 829 | <li><b><tt>__builtin_constant_p</tt></b>: This returns true (as a integer |
| 830 | constant expression) if the operand is any evaluatable constant.</li> |
| 831 | <li><b><tt>__builtin_choose_expr</tt></b>: The condition is required to be an |
| 832 | integer constant expression, but we accept any constant as an "extension of |
| 833 | an extension". This only evaluates one operand depending on which way the |
| 834 | condition evaluates.</li> |
| 835 | <li><b><tt>__builtin_classify_type</tt></b>: This always returns an integer |
| 836 | constant expression.</li> |
| 837 | <li><b><tt>__builtin_inf,nan,..</tt></b>: These are treated just like a |
| 838 | floating-point literal.</li> |
| 839 | <li><b><tt>__builtin_abs,copysign,..</tt></b>: These are constant folded as |
| 840 | general constant expressions.</li> |
| 841 | </ul> |
| 842 | |
| 843 | |
| 844 | |
| 845 | |
Ted Kremenek | 17a295d | 2008-06-11 06:19:49 +0000 | [diff] [blame] | 846 | </div> |
| 847 | </body> |
Douglas Gregor | 2e1cd42 | 2008-11-17 14:58:09 +0000 | [diff] [blame] | 848 | </html> |