| <html> |
| <head> |
| <title>"Clang" CFE Internals Manual</title> |
| <link type="text/css" rel="stylesheet" href="../menu.css" /> |
| <link type="text/css" rel="stylesheet" href="../content.css" /> |
| <style type="text/css"> |
| td { |
| vertical-align: top; |
| } |
| </style> |
| </head> |
| <body> |
| |
| <!--#include virtual="../menu.html.incl"--> |
| |
| <div id="content"> |
| |
| <h1>"Clang" CFE Internals Manual</h1> |
| |
| <ul> |
| <li><a href="#intro">Introduction</a></li> |
| <li><a href="#libsystem">LLVM System and Support Libraries</a></li> |
| <li><a href="#libbasic">The Clang 'Basic' Library</a> |
| <ul> |
| <li><a href="#Diagnostics">The Diagnostics Subsystem</a></li> |
| <li><a href="#SourceLocation">The SourceLocation and SourceManager |
| classes</a></li> |
| </ul> |
| </li> |
| <li><a href="#liblex">The Lexer and Preprocessor Library</a> |
| <ul> |
| <li><a href="#Token">The Token class</a></li> |
| <li><a href="#Lexer">The Lexer class</a></li> |
| <li><a href="#TokenLexer">The TokenLexer class</a></li> |
| <li><a href="#MultipleIncludeOpt">The MultipleIncludeOpt class</a></li> |
| </ul> |
| </li> |
| <li><a href="#libparse">The Parser Library</a> |
| <ul> |
| </ul> |
| </li> |
| <li><a href="#libast">The AST Library</a> |
| <ul> |
| <li><a href="#Type">The Type class and its subclasses</a></li> |
| <li><a href="#QualType">The QualType class</a></li> |
| <li><a href="#DeclarationName">Declaration names</a></li> |
| <li><a href="#CFG">The CFG class</a></li> |
| <li><a href="#Constants">Constant Folding in the Clang AST</a></li> |
| </ul> |
| </li> |
| </ul> |
| |
| |
| <!-- ======================================================================= --> |
| <h2 id="intro">Introduction</h2> |
| <!-- ======================================================================= --> |
| |
| <p>This document describes some of the more important APIs and internal design |
| decisions made in the Clang C front-end. The purpose of this document is to |
| both capture some of this high level information and also describe some of the |
| design decisions behind it. This is meant for people interested in hacking on |
| Clang, not for end-users. The description below is categorized by |
| libraries, and does not describe any of the clients of the libraries.</p> |
| |
| <!-- ======================================================================= --> |
| <h2 id="libsystem">LLVM System and Support Libraries</h2> |
| <!-- ======================================================================= --> |
| |
| <p>The LLVM libsystem library provides the basic Clang system abstraction layer, |
| which is used for file system access. The LLVM libsupport library provides many |
| underlying libraries and <a |
| href="http://llvm.org/docs/ProgrammersManual.html">data-structures</a>, |
| including command line option |
| processing and various containers.</p> |
| |
| <!-- ======================================================================= --> |
| <h2 id="libbasic">The Clang 'Basic' Library</h2> |
| <!-- ======================================================================= --> |
| |
| <p>This library certainly needs a better name. The 'basic' library contains a |
| number of low-level utilities for tracking and manipulating source buffers, |
| locations within the source buffers, diagnostics, tokens, target abstraction, |
| and information about the subset of the language being compiled for.</p> |
| |
| <p>Part of this infrastructure is specific to C (such as the TargetInfo class), |
| other parts could be reused for other non-C-based languages (SourceLocation, |
| SourceManager, Diagnostics, FileManager). When and if there is future demand |
| we can figure out if it makes sense to introduce a new library, move the general |
| classes somewhere else, or introduce some other solution.</p> |
| |
| <p>We describe the roles of these classes in order of their dependencies.</p> |
| |
| |
| <!-- ======================================================================= --> |
| <h3 id="Diagnostics">The Diagnostics Subsystem</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The Clang Diagnostics subsystem is an important part of how the compiler |
| communicates with the human. Diagnostics are the warnings and errors produced |
| when the code is incorrect or dubious. In Clang, each diagnostic produced has |
| (at the minimum) a unique ID, a <a href="#SourceLocation">SourceLocation</a> to |
| "put the caret", an English translation associated with it, and a severity (e.g. |
| <tt>WARNING</tt> or <tt>ERROR</tt>). They can also optionally include a number |
| of arguments to the dianostic (which fill in "%0"'s in the string) as well as a |
| number of source ranges that related to the diagnostic.</p> |
| |
| <p>In this section, we'll be giving examples produced by the Clang command line |
| driver, but diagnostics can be <a href="#DiagnosticClient">rendered in many |
| different ways</a> depending on how the DiagnosticClient interface is |
| implemented. A representative example of a diagonstic is:</p> |
| |
| <pre> |
| t.c:38:15: error: invalid operands to binary expression ('int *' and '_Complex float') |
| <font color="darkgreen">P = (P-42) + Gamma*4;</font> |
| <font color="blue">~~~~~~ ^ ~~~~~~~</font> |
| </pre> |
| |
| <p>In this example, you can see the English translation, the severity (error), |
| you can see the source location (the caret ("^") and file/line/column info), |
| the source ranges "~~~~", arguments to the diagnostic ("int*" and "_Complex |
| float"). You'll have to believe me that there is a unique ID backing the |
| diagnostic :).</p> |
| |
| <p>Getting all of this to happen has several steps and involves many moving |
| pieces, this section describes them and talks about best practices when adding |
| a new diagnostic.</p> |
| |
| <!-- ============================ --> |
| <h4>The DiagnosticKinds.def file</h4> |
| <!-- ============================ --> |
| |
| <p>Diagnostics are created by adding an entry to the <tt><a |
| href="http://llvm.org/svn/llvm-project/cfe/trunk/include/clang/Basic/DiagnosticKinds.def" |
| >DiagnosticKinds.def</a></tt> file. This file encodes the unique ID of the |
| diagnostic (as an enum, the first argument), the severity of the diagnostic |
| (second argument) and the English translation + format string.</p> |
| |
| <p>There is little sanity with the naming of the unique ID's right now. Some |
| start with err_, warn_, ext_ to encode the severity into the name. Since the |
| enum is referenced in the C++ code that produces the diagnostic, it is somewhat |
| useful for it to be reasonably short.</p> |
| |
| <p>The severity of the diagnostic comes from the set {<tt>NOTE</tt>, |
| <tt>WARNING</tt>, <tt>EXTENSION</tt>, <tt>EXTWARN</tt>, <tt>ERROR</tt>}. The |
| <tt>ERROR</tt> severity is used for diagnostics indicating the program is never |
| acceptable under any circumstances. When an error is emitted, the AST for the |
| input code may not be fully built. The <tt>EXTENSION</tt> and <tt>EXTWARN</tt> |
| severities are used for extensions to the language that Clang accepts. This |
| means that Clang fully understands and can represent them in the AST, but we |
| produce diagnostics to tell the user their code is non-portable. The difference |
| is that the former are ignored by default, and the later warn by default. The |
| <tt>WARNING</tt> severity is used for constructs that are valid in the currently |
| selected source language but that are dubious in some way. The <tt>NOTE</tt> |
| level is used to staple more information onto a previous diagnostics.</p> |
| |
| <p>These <em>severities</em> are mapped into a smaller set (the |
| Diagnostic::Level enum, {<tt>Ignored</tt>, <tt>Note</tt>, <tt>Warning</tt>, |
| <tt>Error</tt> }) of output <em>levels</em> by the diagnostics subsystem based |
| on various configuration options. For example, if the user specifies |
| <tt>-pedantic</tt>, <tt>EXTENSION</tt> maps to <tt>Warning</tt>, if they specify |
| <tt>-pedantic-errors</tt>, it turns into <tt>Error</tt>. Clang also internally |
| supports a fully fine grained mapping mechanism that allows you to map any |
| diagnostic that doesn't have <tt>ERRROR</tt> severity to any output level that |
| you want. This is used to implement options like <tt>-Wunused_macros</tt>, |
| <tt>-Wundef</tt> etc.</p> |
| |
| <!-- ================= --> |
| <h4>The Format String</h4> |
| <!-- ================= --> |
| |
| <p>The format string for the diagnostic is very simple, but it has some power. |
| It takes the form of a string in English with markers that indicate where and |
| how arguments to the diagnostic are inserted and formatted. For example, here |
| are some simple format strings:</p> |
| |
| <pre> |
| "binary integer literals are an extension" |
| "format string contains '\\0' within the string body" |
| "more '<b>%%</b>' conversions than data arguments" |
| "invalid operands to binary expression (<b>%0</b> and <b>%1</b>)" |
| "overloaded '<b>%0</b>' must be a <b>%select{unary|binary|unary or binary}2</b> operator" |
| " (has <b>%1</b> parameter<b>%s1</b>)" |
| </pre> |
| |
| <p>These examples show some important points of format strings. You can use any |
| plain ASCII character in the diagnostic string except "%" without a problem, |
| but these are C strings, so you have to use and be aware of all the C escape |
| sequences (as in the second example). If you want to produce a "%" in the |
| output, use the "%%" escape sequence, like the third diagnostic. Finally, |
| Clang uses the "%...[digit]" sequences to specify where and how arguments to |
| the diagnostic are formatted.</p> |
| |
| <p>Arguments to the diagnostic are numbered according to how they are specified |
| by the C++ code that <a href="#producingdiag">produces them</a>, and are |
| referenced by <tt>%0</tt> .. <tt>%9</tt>. If you have more than 10 arguments |
| to your diagnostic, you are doing something wrong :). Unlike printf, there |
| is no requirement that arguments to the diagnostic end up in the output in |
| the same order as they are specified, you could have a format string with |
| <tt>"%1 %0"</tt> that swaps them, for example. The text in between the |
| percent and digit are formatting instructions. If there are no instructions, |
| the argument is just turned into a string and substituted in.</p> |
| |
| <p>Here are some "best practices" for writing the English format string:</p> |
| |
| <ul> |
| <li>Keep the string short. It should ideally fit in the 80 column limit of the |
| <tt>DiagnosticKinds.def</tt> file. This avoids the diagnostic wrapping when |
| printed, and forces you to think about the important point you are conveying |
| with the diagnostic.</li> |
| <li>Take advantage of location information. The user will be able to see the |
| line and location of the caret, so you don't need to tell them that the |
| problem is with the 4th argument to the function: just point to it.</li> |
| <li>Do not capitalize the diagnostic string, and do not end it with a |
| period.</li> |
| <li>If you need to quote something in the diagnostic string, use single |
| quotes.</li> |
| </ul> |
| |
| <p>Diagnostics should never take random English strings as arguments: you |
| shouldn't use <tt>"you have a problem with %0"</tt> and pass in things like |
| <tt>"your argument"</tt> or <tt>"your return value"</tt> as arguments. Doing |
| this prevents <a href="translation">translating</a> the Clang diagnostics to |
| other languages (because they'll get random English words in their otherwise |
| localized diagnostic). The exceptions to this are C/C++ language keywords |
| (e.g. auto, const, mutable, etc) and C/C++ operators (<tt>/=</tt>). Note |
| that things like "pointer" and "reference" are not keywords. On the other |
| hand, you <em>can</em> include anything that comes from the user's source code, |
| including variable names, types, labels, etc. The 'select' format can be |
| used to achieve this sort of thing in a localizable way, see below.</p> |
| |
| <!-- ==================================== --> |
| <h4>Formatting a Diagnostic Argument</a></h4> |
| <!-- ==================================== --> |
| |
| <p>Arguments to diagnostics are fully typed internally, and come from a couple |
| different classes: integers, types, names, and random strings. Depending on |
| the class of the argument, it can be optionally formatted in different ways. |
| This gives the DiagnosticClient information about what the argument means |
| without requiring it to use a specific presentation (consider this MVC for |
| Clang :).</p> |
| |
| <p>Here are the different diagnostic argument formats currently supported by |
| Clang:</p> |
| |
| <table> |
| <tr><td colspan="2"><b>"s" format</b></td></tr> |
| <tr><td>Example:</td><td><tt>"requires %1 parameter%s1"</tt></td></tr> |
| <tr><td>Class:</td><td>Integers</td></tr> |
| <tr><td>Description:</td><td>This is a simple formatter for integers that is |
| useful when producing English diagnostics. When the integer is 1, it prints |
| as nothing. When the integer is not 1, it prints as "s". This allows some |
| simple grammatical forms to be to be handled correctly, and eliminates the |
| need to use gross things like <tt>"requires %1 parameter(s)"</tt>.</td></tr> |
| |
| <tr><td colspan="2"><b>"select" format</b></td></tr> |
| <tr><td>Example:</td><td><tt>"must be a %select{unary|binary|unary or binary}2 |
| operator"</tt></td></tr> |
| <tr><td>Class:</td><td>Integers</td></tr> |
| <tr><td>Description:</td><td>This format specifier is used to merge multiple |
| related diagnostics together into one common one, without requiring the |
| difference to be specified as an English string argument. Instead of |
| specifying the string, the diagnostic gets an integer argument and the |
| format string selects the numbered option. In this case, the "%2" value |
| must be an integer in the range [0..2]. If it is 0, it prints 'unary', if |
| it is 1 it prints 'binary' if it is 2, it prints 'unary or binary'. This |
| allows other language translations to substitute reasonable words (or entire |
| phrases) based on the semantics of the diagnostic instead of having to do |
| things textually.</td></tr> |
| |
| <tr><td colspan="2"><b>"plural" format</b></td></tr> |
| <tr><td>Example:</td><td><tt>"you have %1 %plural{1:mouse|:mice}1 connected to |
| your computer"</tt></td></tr> |
| <tr><td>Class:</td><td>Integers</td></tr> |
| <tr><td>Description:</td><td><p>This is a formatter for complex plural forms. |
| It is designed to handle even the requirements of languages with very |
| complex plural forms, as many Baltic languages have. The argument consists |
| of a series of expression/form pairs, separated by ':', where the first form |
| whose expression evaluates to true is the result of the modifier.</p> |
| <p>An expression can be empty, in which case it is always true. See the |
| example at the top. Otherwise, it is a series of one or more numeric |
| conditions, separated by ','. If any condition matches, the expression |
| matches. Each numeric condition can take one of three forms.</p> |
| <ul> |
| <li>number: A simple decimal number matches if the argument is the same |
| as the number. Example: <tt>"%plural{1:mouse|:mice}4"</tt></li> |
| <li>range: A range in square brackets matches if the argument is within |
| the range. Then range is inclusive on both ends. Example: |
| <tt>"%plural{0:none|1:one|[2,5]:some|:many}2"</tt></li> |
| <li>modulo: A modulo operator is followed by a number, and |
| equals sign and either a number or a range. The tests are the |
| same as for plain |
| numbers and ranges, but the argument is taken modulo the number first. |
| Example: <tt>"%plural{%100=0:even hundred|%100=[1,50]:lower half|:everything |
| else}1"</tt></li> |
| </ul> |
| <p>The parser is very unforgiving. A syntax error, even whitespace, will |
| abort, as will a failure to match the argument against any |
| expression.</p></td></tr> |
| |
| <tr><td colspan="2"><b>"objcclass" format</b></td></tr> |
| <tr><td>Example:</td><td><tt>"method %objcclass0 not found"</tt></td></tr> |
| <tr><td>Class:</td><td>DeclarationName</td></tr> |
| <tr><td>Description:</td><td><p>This is a simple formatter that indicates the |
| DeclarationName corresponds to an Objective-C class method selector. As |
| such, it prints the selector with a leading '+'.</p></td></tr> |
| |
| <tr><td colspan="2"><b>"objcinstance" format</b></td></tr> |
| <tr><td>Example:</td><td><tt>"method %objcinstance0 not found"</tt></td></tr> |
| <tr><td>Class:</td><td>DeclarationName</td></tr> |
| <tr><td>Description:</td><td><p>This is a simple formatter that indicates the |
| DeclarationName corresponds to an Objective-C instance method selector. As |
| such, it prints the selector with a leading '-'.</p></td></tr> |
| |
| </table> |
| |
| <p>It is really easy to add format specifiers to the Clang diagnostics system, |
| but they should be discussed before they are added. If you are creating a lot |
| of repetitive diagnostics and/or have an idea for a useful formatter, please |
| bring it up on the cfe-dev mailing list.</p> |
| |
| <!-- ===================================================== --> |
| <h4><a name="#producingdiag">Producing the Diagnostic</a></h4> |
| <!-- ===================================================== --> |
| |
| <p>Now that you've created the diagnostic in the DiagnosticKinds.def file, you |
| need to write the code that detects the condition in question and emits the |
| new diagnostic. Various components of Clang (e.g. the preprocessor, Sema, |
| etc) provide a helper function named "Diag". It creates a diagnostic and |
| accepts the arguments, ranges, and other information that goes along with |
| it.</p> |
| |
| <p>For example, the binary expression error comes from code like this:</p> |
| |
| <pre> |
| if (various things that are bad) |
| Diag(Loc, diag::err_typecheck_invalid_operands) |
| << lex->getType() << rex->getType() |
| << lex->getSourceRange() << rex->getSourceRange(); |
| </pre> |
| |
| <p>This shows that use of the Diag method: they take a location (a <a |
| href="#SourceLocation">SourceLocation</a> object) and a diagnostic enum value |
| (which matches the name from DiagnosticKinds.def). If the diagnostic takes |
| arguments, they are specified with the << operator: the first argument |
| becomes %0, the second becomes %1, etc. The diagnostic interface allows you to |
| specify arguments of many different types, including <tt>int</tt> and |
| <tt>unsigned</tt> for integer arguments, <tt>const char*</tt> and |
| <tt>std::string</tt> for string arguments, <tt>DeclarationName</tt> and |
| <tt>const IdentifierInfo*</tt> for names, <tt>QualType</tt> for types, etc. |
| SourceRanges are also specified with the << operator, but do not have a |
| specific ordering requirement.</p> |
| |
| <p>As you can see, adding and producing a diagnostic is pretty straightforward. |
| The hard part is deciding exactly what you need to say to help the user, picking |
| a suitable wording, and providing the information needed to format it correctly. |
| The good news is that the call site that issues a diagnostic should be |
| completely independent of how the diagnostic is formatted and in what language |
| it is rendered. |
| </p> |
| |
| <!-- ============================================================= --> |
| <h4><a name="DiagnosticClient">The DiagnosticClient Interface</a></h4> |
| <!-- ============================================================= --> |
| |
| <p>Once code generates a diagnostic with all of the arguments and the rest of |
| the relevant information, Clang needs to know what to do with it. As previously |
| mentioned, the diagnostic machinery goes through some filtering to map a |
| severity onto a diagnostic level, then (assuming the diagnostic is not mapped to |
| "<tt>Ignore</tt>") it invokes an object that implements the DiagnosticClient |
| interface with the information.</p> |
| |
| <p>It is possible to implement this interface in many different ways. For |
| example, the normal Clang DiagnosticClient (named 'TextDiagnosticPrinter') turns |
| the arguments into strings (according to the various formatting rules), prints |
| out the file/line/column information and the string, then prints out the line of |
| code, the source ranges, and the caret. However, this behavior isn't required. |
| </p> |
| |
| <p>Another implementation of the DiagnosticClient interface is the |
| 'TextDiagnosticBuffer' class, which is used when Clang is in -verify mode. |
| Instead of formatting and printing out the diagnostics, this implementation just |
| captures and remembers the diagnostics as they fly by. Then -verify compares |
| the list of produced diagnostics to the list of expected ones. If they disagree, |
| it prints out its own output. |
| </p> |
| |
| <p>There are many other possible implementations of this interface, and this is |
| why we prefer diagnostics to pass down rich structured information in arguments. |
| For example, an HTML output might want declaration names be linkified to where |
| they come from in the source. Another example is that a GUI might let you click |
| on typedefs to expand them. This application would want to pass significantly |
| more information about types through to the GUI than a simple flat string. The |
| interface allows this to happen.</p> |
| |
| <!-- ====================================================== --> |
| <h4><a name="translation">Adding Translations to Clang</a></h4> |
| <!-- ====================================================== --> |
| |
| <p>Not possible yet! Diagnostic strings should be written in UTF-8, the client |
| can translate to the relevant code page if needed. Each translation completely |
| replaces the format string for the diagnostic.</p> |
| |
| |
| <!-- ======================================================================= --> |
| <h3 id="SourceLocation">The SourceLocation and SourceManager classes</h3> |
| <!-- ======================================================================= --> |
| |
| <p>Strangely enough, the SourceLocation class represents a location within the |
| source code of the program. Important design points include:</p> |
| |
| <ol> |
| <li>sizeof(SourceLocation) must be extremely small, as these are embedded into |
| many AST nodes and are passed around often. Currently it is 32 bits.</li> |
| <li>SourceLocation must be a simple value object that can be efficiently |
| copied.</li> |
| <li>We should be able to represent a source location for any byte of any input |
| file. This includes in the middle of tokens, in whitespace, in trigraphs, |
| etc.</li> |
| <li>A SourceLocation must encode the current #include stack that was active when |
| the location was processed. For example, if the location corresponds to a |
| token, it should contain the set of #includes active when the token was |
| lexed. This allows us to print the #include stack for a diagnostic.</li> |
| <li>SourceLocation must be able to describe macro expansions, capturing both |
| the ultimate instantiation point and the source of the original character |
| data.</li> |
| </ol> |
| |
| <p>In practice, the SourceLocation works together with the SourceManager class |
| to encode two pieces of information about a location: it's physical location |
| and it's virtual location. For most tokens, these will be the same. However, |
| for a macro expansion (or tokens that came from a _Pragma directive) these will |
| describe the location of the characters corresponding to the token and the |
| location where the token was used (i.e. the macro instantiation point or the |
| location of the _Pragma itself).</p> |
| |
| <p>For efficiency, we only track one level of macro instantiations: if a token was |
| produced by multiple instantiations, we only track the source and ultimate |
| destination. Though we could track the intermediate instantiation points, this |
| would require extra bookkeeping and no known client would benefit substantially |
| from this.</p> |
| |
| <p>The Clang front-end inherently depends on the location of a token being |
| tracked correctly. If it is ever incorrect, the front-end may get confused and |
| die. The reason for this is that the notion of the 'spelling' of a Token in |
| Clang depends on being able to find the original input characters for the token. |
| This concept maps directly to the "physical" location for the token.</p> |
| |
| <!-- ======================================================================= --> |
| <h2 id="liblex">The Lexer and Preprocessor Library</h2> |
| <!-- ======================================================================= --> |
| |
| <p>The Lexer library contains several tightly-connected classes that are involved |
| with the nasty process of lexing and preprocessing C source code. The main |
| interface to this library for outside clients is the large <a |
| href="#Preprocessor">Preprocessor</a> class. |
| It contains the various pieces of state that are required to coherently read |
| tokens out of a translation unit.</p> |
| |
| <p>The core interface to the Preprocessor object (once it is set up) is the |
| Preprocessor::Lex method, which returns the next <a href="#Token">Token</a> from |
| the preprocessor stream. There are two types of token providers that the |
| preprocessor is capable of reading from: a buffer lexer (provided by the <a |
| href="#Lexer">Lexer</a> class) and a buffered token stream (provided by the <a |
| href="#TokenLexer">TokenLexer</a> class). |
| |
| |
| <!-- ======================================================================= --> |
| <h3 id="Token">The Token class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The Token class is used to represent a single lexed token. Tokens are |
| intended to be used by the lexer/preprocess and parser libraries, but are not |
| intended to live beyond them (for example, they should not live in the ASTs).<p> |
| |
| <p>Tokens most often live on the stack (or some other location that is efficient |
| to access) as the parser is running, but occasionally do get buffered up. For |
| example, macro definitions are stored as a series of tokens, and the C++ |
| front-end periodically needs to buffer tokens up for tentative parsing and |
| various pieces of look-ahead. As such, the size of a Token matter. On a 32-bit |
| system, sizeof(Token) is currently 16 bytes.</p> |
| |
| <p>Tokens contain the following information:</p> |
| |
| <ul> |
| <li><b>A SourceLocation</b> - This indicates the location of the start of the |
| token.</li> |
| |
| <li><b>A length</b> - This stores the length of the token as stored in the |
| SourceBuffer. For tokens that include them, this length includes trigraphs and |
| escaped newlines which are ignored by later phases of the compiler. By pointing |
| into the original source buffer, it is always possible to get the original |
| spelling of a token completely accurately.</li> |
| |
| <li><b>IdentifierInfo</b> - If a token takes the form of an identifier, and if |
| identifier lookup was enabled when the token was lexed (e.g. the lexer was not |
| reading in 'raw' mode) this contains a pointer to the unique hash value for the |
| identifier. Because the lookup happens before keyword identification, this |
| field is set even for language keywords like 'for'.</li> |
| |
| <li><b>TokenKind</b> - This indicates the kind of token as classified by the |
| lexer. This includes things like <tt>tok::starequal</tt> (for the "*=" |
| operator), <tt>tok::ampamp</tt> for the "&&" token, and keyword values |
| (e.g. <tt>tok::kw_for</tt>) for identifiers that correspond to keywords. Note |
| that some tokens can be spelled multiple ways. For example, C++ supports |
| "operator keywords", where things like "and" are treated exactly like the |
| "&&" operator. In these cases, the kind value is set to |
| <tt>tok::ampamp</tt>, which is good for the parser, which doesn't have to |
| consider both forms. For something that cares about which form is used (e.g. |
| the preprocessor 'stringize' operator) the spelling indicates the original |
| form.</li> |
| |
| <li><b>Flags</b> - There are currently four flags tracked by the |
| lexer/preprocessor system on a per-token basis: |
| |
| <ol> |
| <li><b>StartOfLine</b> - This was the first token that occurred on its input |
| source line.</li> |
| <li><b>LeadingSpace</b> - There was a space character either immediately |
| before the token or transitively before the token as it was expanded |
| through a macro. The definition of this flag is very closely defined by |
| the stringizing requirements of the preprocessor.</li> |
| <li><b>DisableExpand</b> - This flag is used internally to the preprocessor to |
| represent identifier tokens which have macro expansion disabled. This |
| prevents them from being considered as candidates for macro expansion ever |
| in the future.</li> |
| <li><b>NeedsCleaning</b> - This flag is set if the original spelling for the |
| token includes a trigraph or escaped newline. Since this is uncommon, |
| many pieces of code can fast-path on tokens that did not need cleaning. |
| </p> |
| </ol> |
| </li> |
| </ul> |
| |
| <p>One interesting (and somewhat unusual) aspect of tokens is that they don't |
| contain any semantic information about the lexed value. For example, if the |
| token was a pp-number token, we do not represent the value of the number that |
| was lexed (this is left for later pieces of code to decide). Additionally, the |
| lexer library has no notion of typedef names vs variable names: both are |
| returned as identifiers, and the parser is left to decide whether a specific |
| identifier is a typedef or a variable (tracking this requires scope information |
| among other things).</p> |
| |
| <!-- ======================================================================= --> |
| <h3 id="Lexer">The Lexer class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The Lexer class provides the mechanics of lexing tokens out of a source |
| buffer and deciding what they mean. The Lexer is complicated by the fact that |
| it operates on raw buffers that have not had spelling eliminated (this is a |
| necessity to get decent performance), but this is countered with careful coding |
| as well as standard performance techniques (for example, the comment handling |
| code is vectorized on X86 and PowerPC hosts).</p> |
| |
| <p>The lexer has a couple of interesting modal features:</p> |
| |
| <ul> |
| <li>The lexer can operate in 'raw' mode. This mode has several features that |
| make it possible to quickly lex the file (e.g. it stops identifier lookup, |
| doesn't specially handle preprocessor tokens, handles EOF differently, etc). |
| This mode is used for lexing within an "<tt>#if 0</tt>" block, for |
| example.</li> |
| <li>The lexer can capture and return comments as tokens. This is required to |
| support the -C preprocessor mode, which passes comments through, and is |
| used by the diagnostic checker to identifier expect-error annotations.</li> |
| <li>The lexer can be in ParsingFilename mode, which happens when preprocessing |
| after reading a #include directive. This mode changes the parsing of '<' |
| to return an "angled string" instead of a bunch of tokens for each thing |
| within the filename.</li> |
| <li>When parsing a preprocessor directive (after "<tt>#</tt>") the |
| ParsingPreprocessorDirective mode is entered. This changes the parser to |
| return EOM at a newline.</li> |
| <li>The Lexer uses a LangOptions object to know whether trigraphs are enabled, |
| whether C++ or ObjC keywords are recognized, etc.</li> |
| </ul> |
| |
| <p>In addition to these modes, the lexer keeps track of a couple of other |
| features that are local to a lexed buffer, which change as the buffer is |
| lexed:</p> |
| |
| <ul> |
| <li>The Lexer uses BufferPtr to keep track of the current character being |
| lexed.</li> |
| <li>The Lexer uses IsAtStartOfLine to keep track of whether the next lexed token |
| will start with its "start of line" bit set.</li> |
| <li>The Lexer keeps track of the current #if directives that are active (which |
| can be nested).</li> |
| <li>The Lexer keeps track of an <a href="#MultipleIncludeOpt"> |
| MultipleIncludeOpt</a> object, which is used to |
| detect whether the buffer uses the standard "<tt>#ifndef XX</tt> / |
| <tt>#define XX</tt>" idiom to prevent multiple inclusion. If a buffer does, |
| subsequent includes can be ignored if the XX macro is defined.</li> |
| </ul> |
| |
| <!-- ======================================================================= --> |
| <h3 id="TokenLexer">The TokenLexer class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The TokenLexer class is a token provider that returns tokens from a list |
| of tokens that came from somewhere else. It typically used for two things: 1) |
| returning tokens from a macro definition as it is being expanded 2) returning |
| tokens from an arbitrary buffer of tokens. The later use is used by _Pragma and |
| will most likely be used to handle unbounded look-ahead for the C++ parser.</p> |
| |
| <!-- ======================================================================= --> |
| <h3 id="MultipleIncludeOpt">The MultipleIncludeOpt class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The MultipleIncludeOpt class implements a really simple little state machine |
| that is used to detect the standard "<tt>#ifndef XX</tt> / <tt>#define XX</tt>" |
| idiom that people typically use to prevent multiple inclusion of headers. If a |
| buffer uses this idiom and is subsequently #include'd, the preprocessor can |
| simply check to see whether the guarding condition is defined or not. If so, |
| the preprocessor can completely ignore the include of the header.</p> |
| |
| |
| |
| <!-- ======================================================================= --> |
| <h2 id="libparse">The Parser Library</h2> |
| <!-- ======================================================================= --> |
| |
| <!-- ======================================================================= --> |
| <h2 id="libast">The AST Library</h2> |
| <!-- ======================================================================= --> |
| |
| <!-- ======================================================================= --> |
| <h3 id="Type">The Type class and its subclasses</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The Type class (and its subclasses) are an important part of the AST. Types |
| are accessed through the ASTContext class, which implicitly creates and uniques |
| them as they are needed. Types have a couple of non-obvious features: 1) they |
| do not capture type qualifiers like const or volatile (See |
| <a href="#QualType">QualType</a>), and 2) they implicitly capture typedef |
| information. Once created, types are immutable (unlike decls).</p> |
| |
| <p>Typedefs in C make semantic analysis a bit more complex than it would |
| be without them. The issue is that we want to capture typedef information |
| and represent it in the AST perfectly, but the semantics of operations need to |
| "see through" typedefs. For example, consider this code:</p> |
| |
| <code> |
| void func() {<br> |
| typedef int foo;<br> |
| foo X, *Y;<br> |
| typedef foo* bar;<br> |
| bar Z;<br> |
| *X; <i>// error</i><br> |
| **Y; <i>// error</i><br> |
| **Z; <i>// error</i><br> |
| }<br> |
| </code> |
| |
| <p>The code above is illegal, and thus we expect there to be diagnostics emitted |
| on the annotated lines. In this example, we expect to get:</p> |
| |
| <pre> |
| <b>test.c:6:1: error: indirection requires pointer operand ('foo' invalid)</b> |
| *X; // error |
| <font color="blue">^~</font> |
| <b>test.c:7:1: error: indirection requires pointer operand ('foo' invalid)</b> |
| **Y; // error |
| <font color="blue">^~~</font> |
| <b>test.c:8:1: error: indirection requires pointer operand ('foo' invalid)</b> |
| **Z; // error |
| <font color="blue">^~~</font> |
| </pre> |
| |
| <p>While this example is somewhat silly, it illustrates the point: we want to |
| retain typedef information where possible, so that we can emit errors about |
| "<tt>std::string</tt>" instead of "<tt>std::basic_string<char, std:...</tt>". |
| Doing this requires properly keeping typedef information (for example, the type |
| of "X" is "foo", not "int"), and requires properly propagating it through the |
| various operators (for example, the type of *Y is "foo", not "int"). In order |
| to retain this information, the type of these expressions is an instance of the |
| TypedefType class, which indicates that the type of these expressions is a |
| typedef for foo. |
| </p> |
| |
| <p>Representing types like this is great for diagnostics, because the |
| user-specified type is always immediately available. There are two problems |
| with this: first, various semantic checks need to make judgements about the |
| <em>actual structure</em> of a type, ignoring typdefs. Second, we need an |
| efficient way to query whether two types are structurally identical to each |
| other, ignoring typedefs. The solution to both of these problems is the idea of |
| canonical types.</p> |
| |
| <!-- =============== --> |
| <h4>Canonical Types</h4> |
| <!-- =============== --> |
| |
| <p>Every instance of the Type class contains a canonical type pointer. For |
| simple types with no typedefs involved (e.g. "<tt>int</tt>", "<tt>int*</tt>", |
| "<tt>int**</tt>"), the type just points to itself. For types that have a |
| typedef somewhere in their structure (e.g. "<tt>foo</tt>", "<tt>foo*</tt>", |
| "<tt>foo**</tt>", "<tt>bar</tt>"), the canonical type pointer points to their |
| structurally equivalent type without any typedefs (e.g. "<tt>int</tt>", |
| "<tt>int*</tt>", "<tt>int**</tt>", and "<tt>int*</tt>" respectively).</p> |
| |
| <p>This design provides a constant time operation (dereferencing the canonical |
| type pointer) that gives us access to the structure of types. For example, |
| we can trivially tell that "bar" and "foo*" are the same type by dereferencing |
| their canonical type pointers and doing a pointer comparison (they both point |
| to the single "<tt>int*</tt>" type).</p> |
| |
| <p>Canonical types and typedef types bring up some complexities that must be |
| carefully managed. Specifically, the "isa/cast/dyncast" operators generally |
| shouldn't be used in code that is inspecting the AST. For example, when type |
| checking the indirection operator (unary '*' on a pointer), the type checker |
| must verify that the operand has a pointer type. It would not be correct to |
| check that with "<tt>isa<PointerType>(SubExpr->getType())</tt>", |
| because this predicate would fail if the subexpression had a typedef type.</p> |
| |
| <p>The solution to this problem are a set of helper methods on Type, used to |
| check their properties. In this case, it would be correct to use |
| "<tt>SubExpr->getType()->isPointerType()</tt>" to do the check. This |
| predicate will return true if the <em>canonical type is a pointer</em>, which is |
| true any time the type is structurally a pointer type. The only hard part here |
| is remembering not to use the <tt>isa/cast/dyncast</tt> operations.</p> |
| |
| <p>The second problem we face is how to get access to the pointer type once we |
| know it exists. To continue the example, the result type of the indirection |
| operator is the pointee type of the subexpression. In order to determine the |
| type, we need to get the instance of PointerType that best captures the typedef |
| information in the program. If the type of the expression is literally a |
| PointerType, we can return that, otherwise we have to dig through the |
| typedefs to find the pointer type. For example, if the subexpression had type |
| "<tt>foo*</tt>", we could return that type as the result. If the subexpression |
| had type "<tt>bar</tt>", we want to return "<tt>foo*</tt>" (note that we do |
| <em>not</em> want "<tt>int*</tt>"). In order to provide all of this, Type has |
| a getAsPointerType() method that checks whether the type is structurally a |
| PointerType and, if so, returns the best one. If not, it returns a null |
| pointer.</p> |
| |
| <p>This structure is somewhat mystical, but after meditating on it, it will |
| make sense to you :).</p> |
| |
| <!-- ======================================================================= --> |
| <h3 id="QualType">The QualType class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The QualType class is designed as a trivial value class that is small, |
| passed by-value and is efficient to query. The idea of QualType is that it |
| stores the type qualifiers (const, volatile, restrict) separately from the types |
| themselves: QualType is conceptually a pair of "Type*" and bits for the type |
| qualifiers.</p> |
| |
| <p>By storing the type qualifiers as bits in the conceptual pair, it is |
| extremely efficient to get the set of qualifiers on a QualType (just return the |
| field of the pair), add a type qualifier (which is a trivial constant-time |
| operation that sets a bit), and remove one or more type qualifiers (just return |
| a QualType with the bitfield set to empty).</p> |
| |
| <p>Further, because the bits are stored outside of the type itself, we do not |
| need to create duplicates of types with different sets of qualifiers (i.e. there |
| is only a single heap allocated "int" type: "const int" and "volatile const int" |
| both point to the same heap allocated "int" type). This reduces the heap size |
| used to represent bits and also means we do not have to consider qualifiers when |
| uniquing types (<a href="#Type">Type</a> does not even contain qualifiers).</p> |
| |
| <p>In practice, on hosts where it is safe, the 3 type qualifiers are stored in |
| the low bit of the pointer to the Type object. This means that QualType is |
| exactly the same size as a pointer, and this works fine on any system where |
| malloc'd objects are at least 8 byte aligned.</p> |
| |
| <!-- ======================================================================= --> |
| <h3 id="DeclarationName">Declaration names</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The <tt>DeclarationName</tt> class represents the name of a |
| declaration in Clang. Declarations in the C family of languages can |
| take several different forms. Most declarations are named by |
| simple identifiers, e.g., "<code>f</code>" and "<code>x</code>" in |
| the function declaration <code>f(int x)</code>. In C++, declaration |
| names can also name class constructors ("<code>Class</code>" |
| in <code>struct Class { Class(); }</code>), class destructors |
| ("<code>~Class</code>"), overloaded operator names ("operator+"), |
| and conversion functions ("<code>operator void const *</code>"). In |
| Objective-C, declaration names can refer to the names of Objective-C |
| methods, which involve the method name and the parameters, |
| collectively called a <i>selector</i>, e.g., |
| "<code>setWidth:height:</code>". Since all of these kinds of |
| entities - variables, functions, Objective-C methods, C++ |
| constructors, destructors, and operators - are represented as |
| subclasses of Clang's common <code>NamedDecl</code> |
| class, <code>DeclarationName</code> is designed to efficiently |
| represent any kind of name.</p> |
| |
| <p>Given |
| a <code>DeclarationName</code> <code>N</code>, <code>N.getNameKind()</code> |
| will produce a value that describes what kind of name <code>N</code> |
| stores. There are 8 options (all of the names are inside |
| the <code>DeclarationName</code> class)</p> |
| <dl> |
| <dt>Identifier</dt> |
| <dd>The name is a simple |
| identifier. Use <code>N.getAsIdentifierInfo()</code> to retrieve the |
| corresponding <code>IdentifierInfo*</code> pointing to the actual |
| identifier. Note that C++ overloaded operators (e.g., |
| "<code>operator+</code>") are represented as special kinds of |
| identifiers. Use <code>IdentifierInfo</code>'s <code>getOverloadedOperatorID</code> |
| function to determine whether an identifier is an overloaded |
| operator name.</dd> |
| |
| <dt>ObjCZeroArgSelector, ObjCOneArgSelector, |
| ObjCMultiArgSelector</dt> |
| <dd>The name is an Objective-C selector, which can be retrieved as a |
| <code>Selector</code> instance |
| via <code>N.getObjCSelector()</code>. The three possible name |
| kinds for Objective-C reflect an optimization within |
| the <code>DeclarationName</code> class: both zero- and |
| one-argument selectors are stored as a |
| masked <code>IdentifierInfo</code> pointer, and therefore require |
| very little space, since zero- and one-argument selectors are far |
| more common than multi-argument selectors (which use a different |
| structure).</dd> |
| |
| <dt>CXXConstructorName</dt> |
| <dd>The name is a C++ constructor |
| name. Use <code>N.getCXXNameType()</code> to retrieve |
| the <a href="#QualType">type</a> that this constructor is meant to |
| construct. The type is always the canonical type, since all |
| constructors for a given type have the same name.</dd> |
| |
| <dt>CXXDestructorName</dt> |
| <dd>The name is a C++ destructor |
| name. Use <code>N.getCXXNameType()</code> to retrieve |
| the <a href="#QualType">type</a> whose destructor is being |
| named. This type is always a canonical type.</dd> |
| |
| <dt>CXXConversionFunctionName</dt> |
| <dd>The name is a C++ conversion function. Conversion functions are |
| named according to the type they convert to, e.g., "<code>operator void |
| const *</code>". Use <code>N.getCXXNameType()</code> to retrieve |
| the type that this conversion function converts to. This type is |
| always a canonical type.</dd> |
| |
| <dt>CXXOperatorName</dt> |
| <dd>The name is a C++ overloaded operator name. Overloaded operators |
| are named according to their spelling, e.g., |
| "<code>operator+</code>" or "<code>operator new |
| []</code>". Use <code>N.getCXXOverloadedOperator()</code> to |
| retrieve the overloaded operator (a value of |
| type <code>OverloadedOperatorKind</code>).</dd> |
| </dl> |
| |
| <p><code>DeclarationName</code>s are cheap to create, copy, and |
| compare. They require only a single pointer's worth of storage in |
| the common cases (identifiers, zero- |
| and one-argument Objective-C selectors) and use dense, uniqued |
| storage for the other kinds of |
| names. Two <code>DeclarationName</code>s can be compared for |
| equality (<code>==</code>, <code>!=</code>) using a simple bitwise |
| comparison, can be ordered |
| with <code><</code>, <code>></code>, <code><=</code>, |
| and <code>>=</code> (which provide a lexicographical ordering for |
| normal identifiers but an unspecified ordering for other kinds of |
| names), and can be placed into LLVM <code>DenseMap</code>s |
| and <code>DenseSet</code>s.</p> |
| |
| <p><code>DeclarationName</code> instances can be created in different |
| ways depending on what kind of name the instance will store. Normal |
| identifiers (<code>IdentifierInfo</code> pointers) and Objective-C selectors |
| (<code>Selector</code>) can be implicitly converted |
| to <code>DeclarationName</code>s. Names for C++ constructors, |
| destructors, conversion functions, and overloaded operators can be retrieved from |
| the <code>DeclarationNameTable</code>, an instance of which is |
| available as <code>ASTContext::DeclarationNames</code>. The member |
| functions <code>getCXXConstructorName</code>, <code>getCXXDestructorName</code>, |
| <code>getCXXConversionFunctionName</code>, and <code>getCXXOperatorName</code>, respectively, |
| return <code>DeclarationName</code> instances for the four kinds of |
| C++ special function names.</p> |
| |
| <!-- ======================================================================= --> |
| <h3 id="CFG">The <tt>CFG</tt> class</h3> |
| <!-- ======================================================================= --> |
| |
| <p>The <tt>CFG</tt> class is designed to represent a source-level |
| control-flow graph for a single statement (<tt>Stmt*</tt>). Typically |
| instances of <tt>CFG</tt> are constructed for function bodies (usually |
| an instance of <tt>CompoundStmt</tt>), but can also be instantiated to |
| represent the control-flow of any class that subclasses <tt>Stmt</tt>, |
| which includes simple expressions. Control-flow graphs are especially |
| useful for performing |
| <a href="http://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities">flow- |
| or path-sensitive</a> program analyses on a given function.</p> |
| |
| <!-- ============ --> |
| <h4>Basic Blocks</h4> |
| <!-- ============ --> |
| |
| <p>Concretely, an instance of <tt>CFG</tt> is a collection of basic |
| blocks. Each basic block is an instance of <tt>CFGBlock</tt>, which |
| simply contains an ordered sequence of <tt>Stmt*</tt> (each referring |
| to statements in the AST). The ordering of statements within a block |
| indicates unconditional flow of control from one statement to the |
| next. <a href="#ConditionalControlFlow">Conditional control-flow</a> |
| is represented using edges between basic blocks. The statements |
| within a given <tt>CFGBlock</tt> can be traversed using |
| the <tt>CFGBlock::*iterator</tt> interface.</p> |
| |
| <p> |
| A <tt>CFG</tt> object owns the instances of <tt>CFGBlock</tt> within |
| the control-flow graph it represents. Each <tt>CFGBlock</tt> within a |
| CFG is also uniquely numbered (accessible |
| via <tt>CFGBlock::getBlockID()</tt>). Currently the number is |
| based on the ordering the blocks were created, but no assumptions |
| should be made on how <tt>CFGBlock</tt>s are numbered other than their |
| numbers are unique and that they are numbered from 0..N-1 (where N is |
| the number of basic blocks in the CFG).</p> |
| |
| <!-- ===================== --> |
| <h4>Entry and Exit Blocks</h4> |
| <!-- ===================== --> |
| |
| Each instance of <tt>CFG</tt> contains two special blocks: |
| an <i>entry</i> block (accessible via <tt>CFG::getEntry()</tt>), which |
| has no incoming edges, and an <i>exit</i> block (accessible |
| via <tt>CFG::getExit()</tt>), which has no outgoing edges. Neither |
| block contains any statements, and they serve the role of providing a |
| clear entrance and exit for a body of code such as a function body. |
| The presence of these empty blocks greatly simplifies the |
| implementation of many analyses built on top of CFGs. |
| |
| <!-- ===================================================== --> |
| <h4 id ="ConditionalControlFlow">Conditional Control-Flow</h4> |
| <!-- ===================================================== --> |
| |
| <p>Conditional control-flow (such as those induced by if-statements |
| and loops) is represented as edges between <tt>CFGBlock</tt>s. |
| Because different C language constructs can induce control-flow, |
| each <tt>CFGBlock</tt> also records an extra <tt>Stmt*</tt> that |
| represents the <i>terminator</i> of the block. A terminator is simply |
| the statement that caused the control-flow, and is used to identify |
| the nature of the conditional control-flow between blocks. For |
| example, in the case of an if-statement, the terminator refers to |
| the <tt>IfStmt</tt> object in the AST that represented the given |
| branch.</p> |
| |
| <p>To illustrate, consider the following code example:</p> |
| |
| <code> |
| int foo(int x) {<br> |
| x = x + 1;<br> |
| <br> |
| if (x > 2) x++;<br> |
| else {<br> |
| x += 2;<br> |
| x *= 2;<br> |
| }<br> |
| <br> |
| return x;<br> |
| } |
| </code> |
| |
| <p>After invoking the parser+semantic analyzer on this code fragment, |
| the AST of the body of <tt>foo</tt> is referenced by a |
| single <tt>Stmt*</tt>. We can then construct an instance |
| of <tt>CFG</tt> representing the control-flow graph of this function |
| body by single call to a static class method:</p> |
| |
| <code> |
| Stmt* FooBody = ...<br> |
| CFG* FooCFG = <b>CFG::buildCFG</b>(FooBody); |
| </code> |
| |
| <p>It is the responsibility of the caller of <tt>CFG::buildCFG</tt> |
| to <tt>delete</tt> the returned <tt>CFG*</tt> when the CFG is no |
| longer needed.</p> |
| |
| <p>Along with providing an interface to iterate over |
| its <tt>CFGBlock</tt>s, the <tt>CFG</tt> class also provides methods |
| that are useful for debugging and visualizing CFGs. For example, the |
| method |
| <tt>CFG::dump()</tt> dumps a pretty-printed version of the CFG to |
| standard error. This is especially useful when one is using a |
| debugger such as gdb. For example, here is the output |
| of <tt>FooCFG->dump()</tt>:</p> |
| |
| <code> |
| [ B5 (ENTRY) ]<br> |
| Predecessors (0):<br> |
| Successors (1): B4<br> |
| <br> |
| [ B4 ]<br> |
| 1: x = x + 1<br> |
| 2: (x > 2)<br> |
| <b>T: if [B4.2]</b><br> |
| Predecessors (1): B5<br> |
| Successors (2): B3 B2<br> |
| <br> |
| [ B3 ]<br> |
| 1: x++<br> |
| Predecessors (1): B4<br> |
| Successors (1): B1<br> |
| <br> |
| [ B2 ]<br> |
| 1: x += 2<br> |
| 2: x *= 2<br> |
| Predecessors (1): B4<br> |
| Successors (1): B1<br> |
| <br> |
| [ B1 ]<br> |
| 1: return x;<br> |
| Predecessors (2): B2 B3<br> |
| Successors (1): B0<br> |
| <br> |
| [ B0 (EXIT) ]<br> |
| Predecessors (1): B1<br> |
| Successors (0): |
| </code> |
| |
| <p>For each block, the pretty-printed output displays for each block |
| the number of <i>predecessor</i> blocks (blocks that have outgoing |
| control-flow to the given block) and <i>successor</i> blocks (blocks |
| that have control-flow that have incoming control-flow from the given |
| block). We can also clearly see the special entry and exit blocks at |
| the beginning and end of the pretty-printed output. For the entry |
| block (block B5), the number of predecessor blocks is 0, while for the |
| exit block (block B0) the number of successor blocks is 0.</p> |
| |
| <p>The most interesting block here is B4, whose outgoing control-flow |
| represents the branching caused by the sole if-statement |
| in <tt>foo</tt>. Of particular interest is the second statement in |
| the block, <b><tt>(x > 2)</tt></b>, and the terminator, printed |
| as <b><tt>if [B4.2]</tt></b>. The second statement represents the |
| evaluation of the condition of the if-statement, which occurs before |
| the actual branching of control-flow. Within the <tt>CFGBlock</tt> |
| for B4, the <tt>Stmt*</tt> for the second statement refers to the |
| actual expression in the AST for <b><tt>(x > 2)</tt></b>. Thus |
| pointers to subclasses of <tt>Expr</tt> can appear in the list of |
| statements in a block, and not just subclasses of <tt>Stmt</tt> that |
| refer to proper C statements.</p> |
| |
| <p>The terminator of block B4 is a pointer to the <tt>IfStmt</tt> |
| object in the AST. The pretty-printer outputs <b><tt>if |
| [B4.2]</tt></b> because the condition expression of the if-statement |
| has an actual place in the basic block, and thus the terminator is |
| essentially |
| <i>referring</i> to the expression that is the second statement of |
| block B4 (i.e., B4.2). In this manner, conditions for control-flow |
| (which also includes conditions for loops and switch statements) are |
| hoisted into the actual basic block.</p> |
| |
| <!-- ===================== --> |
| <!-- <h4>Implicit Control-Flow</h4> --> |
| <!-- ===================== --> |
| |
| <!-- |
| <p>A key design principle of the <tt>CFG</tt> class was to not require |
| any transformations to the AST in order to represent control-flow. |
| Thus the <tt>CFG</tt> does not perform any "lowering" of the |
| statements in an AST: loops are not transformed into guarded gotos, |
| short-circuit operations are not converted to a set of if-statements, |
| and so on.</p> |
| --> |
| |
| |
| <!-- ======================================================================= --> |
| <h3 id="Constants">Constant Folding in the Clang AST</h3> |
| <!-- ======================================================================= --> |
| |
| <p>There are several places where constants and constant folding matter a lot to |
| the Clang front-end. First, in general, we prefer the AST to retain the source |
| code as close to how the user wrote it as possible. This means that if they |
| wrote "5+4", we want to keep the addition and two constants in the AST, we don't |
| want to fold to "9". This means that constant folding in various ways turns |
| into a tree walk that needs to handle the various cases.</p> |
| |
| <p>However, there are places in both C and C++ that require constants to be |
| folded. For example, the C standard defines what an "integer constant |
| expression" (i-c-e) is with very precise and specific requirements. The |
| language then requires i-c-e's in a lot of places (for example, the size of a |
| bitfield, the value for a case statement, etc). For these, we have to be able |
| to constant fold the constants, to do semantic checks (e.g. verify bitfield size |
| is non-negative and that case statements aren't duplicated). We aim for Clang |
| to be very pedantic about this, diagnosing cases when the code does not use an |
| i-c-e where one is required, but accepting the code unless running with |
| <tt>-pedantic-errors</tt>.</p> |
| |
| <p>Things get a little bit more tricky when it comes to compatibility with |
| real-world source code. Specifically, GCC has historically accepted a huge |
| superset of expressions as i-c-e's, and a lot of real world code depends on this |
| unfortuate accident of history (including, e.g., the glibc system headers). GCC |
| accepts anything its "fold" optimizer is capable of reducing to an integer |
| constant, which means that the definition of what it accepts changes as its |
| optimizer does. One example is that GCC accepts things like "case X-X:" even |
| when X is a variable, because it can fold this to 0.</p> |
| |
| <p>Another issue are how constants interact with the extensions we support, such |
| as __builtin_constant_p, __builtin_inf, __extension__ and many others. C99 |
| obviously does not specify the semantics of any of these extensions, and the |
| definition of i-c-e does not include them. However, these extensions are often |
| used in real code, and we have to have a way to reason about them.</p> |
| |
| <p>Finally, this is not just a problem for semantic analysis. The code |
| generator and other clients have to be able to fold constants (e.g. to |
| initialize global variables) and has to handle a superset of what C99 allows. |
| Further, these clients can benefit from extended information. For example, we |
| know that "foo()||1" always evaluates to true, but we can't replace the |
| expression with true because it has side effects.</p> |
| |
| <!-- ======================= --> |
| <h4>Implementation Approach</h4> |
| <!-- ======================= --> |
| |
| <p>After trying several different approaches, we've finally converged on a |
| design (Note, at the time of this writing, not all of this has been implemented, |
| consider this a design goal!). Our basic approach is to define a single |
| recursive method evaluation method (<tt>Expr::Evaluate</tt>), which is |
| implemented in <tt>AST/ExprConstant.cpp</tt>. Given an expression with 'scalar' |
| type (integer, fp, complex, or pointer) this method returns the following |
| information:</p> |
| |
| <ul> |
| <li>Whether the expression is an integer constant expression, a general |
| constant that was folded but has no side effects, a general constant that |
| was folded but that does have side effects, or an uncomputable/unfoldable |
| value. |
| </li> |
| <li>If the expression was computable in any way, this method returns the APValue |
| for the result of the expression.</li> |
| <li>If the expression is not evaluatable at all, this method returns |
| information on one of the problems with the expression. This includes a |
| SourceLocation for where the problem is, and a diagnostic ID that explains |
| the problem. The diagnostic should be have ERROR type.</li> |
| <li>If the expression is not an integer constant expression, this method returns |
| information on one of the problems with the expression. This includes a |
| SourceLocation for where the problem is, and a diagnostic ID that explains |
| the problem. The diagnostic should be have EXTENSION type.</li> |
| </ul> |
| |
| <p>This information gives various clients the flexibility that they want, and we |
| will eventually have some helper methods for various extensions. For example, |
| Sema should have a <tt>Sema::VerifyIntegerConstantExpression</tt> method, which |
| calls Evaluate on the expression. If the expression is not foldable, the error |
| is emitted, and it would return true. If the expression is not an i-c-e, the |
| EXTENSION diagnostic is emitted. Finally it would return false to indicate that |
| the AST is ok.</p> |
| |
| <p>Other clients can use the information in other ways, for example, codegen can |
| just use expressions that are foldable in any way.</p> |
| |
| <!-- ========== --> |
| <h4>Extensions</h4> |
| <!-- ========== --> |
| |
| <p>This section describes how some of the various extensions Clang supports |
| interacts with constant evaluation:</p> |
| |
| <ul> |
| <li><b><tt>__extension__</tt></b>: The expression form of this extension causes |
| any evaluatable subexpression to be accepted as an integer constant |
| expression.</li> |
| <li><b><tt>__builtin_constant_p</tt></b>: This returns true (as a integer |
| constant expression) if the operand is any evaluatable constant. As a |
| special case, if <tt>__builtin_constant_p</tt> is the (potentially |
| parenthesized) condition of a conditional operator expression ("?:"), only |
| the true side of the conditional operator is considered.</li> |
| <li><b><tt>__builtin_choose_expr</tt></b>: The condition is required to be an |
| integer constant expression, but we accept any constant as an "extension of |
| an extension". This only evaluates one operand depending on which way the |
| condition evaluates.</li> |
| <li><b><tt>__builtin_classify_type</tt></b>: This always returns an integer |
| constant expression.</li> |
| <li><b><tt>__builtin_inf,nan,..</tt></b>: These are treated just like a |
| floating-point literal.</li> |
| <li><b><tt>__builtin_abs,copysign,..</tt></b>: These are constant folded as |
| general constant expressions.</li> |
| </ul> |
| |
| |
| |
| |
| </div> |
| </body> |
| </html> |