Blame - docs/InternalsManual.html - platform/external/clang

blob: 81fefab2adfff407f34d9bcb95754430dcb5be81 [file] [log] [blame]

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>
Ted Kremenek	8bc0571	2007-10-10 23:01:43 +0000	[diff] [blame]	40	<li><a href="#CFG">The CFG class</a></li>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	41	</ul>
				42	</li>
				43	</ul>
				44
				45
				46	<!-- ======================================================================= -->
				47	<h2 id="intro">Introduction</h2>
				48	<!-- ======================================================================= -->
				49
				50	<p>This document describes some of the more important APIs and internal design
				51	decisions made in the clang C front-end. The purpose of this document is to
				52	both capture some of this high level information and also describe some of the
				53	design decisions behind it. This is meant for people interested in hacking on
				54	clang, not for end-users. The description below is categorized by
				55	libraries, and does not describe any of the clients of the libraries.</p>
				56
				57	<!-- ======================================================================= -->
				58	<h2 id="libsystem">LLVM System and Support Libraries</h2>
				59	<!-- ======================================================================= -->
				60
				61	<p>The LLVM libsystem library provides the basic clang system abstraction layer,
				62	which is used for file system access. The LLVM libsupport library provides many
				63	underlying libraries and <a
				64	href="http://llvm.org/docs/ProgrammersManual.html">data-structures</a>,
				65	including command line option
				66	processing and various containers.</p>
				67
				68	<!-- ======================================================================= -->
				69	<h2 id="libbasic">The clang 'Basic' Library</h2>
				70	<!-- ======================================================================= -->
				71
				72	<p>This library certainly needs a better name. The 'basic' library contains a
				73	number of low-level utilities for tracking and manipulating source buffers,
				74	locations within the source buffers, diagnostics, tokens, target abstraction,
				75	and information about the subset of the language being compiled for.</p>
				76
				77	<p>Part of this infrastructure is specific to C (such as the TargetInfo class),
				78	other parts could be reused for other non-C-based languages (SourceLocation,
				79	SourceManager, Diagnostics, FileManager). When and if there is future demand
				80	we can figure out if it makes sense to introduce a new library, move the general
				81	classes somewhere else, or introduce some other solution.</p>
				82
				83	<p>We describe the roles of these classes in order of their dependencies.</p>
				84
				85	<!-- ======================================================================= -->
				86	<h3 id="SourceLocation">The SourceLocation and SourceManager classes</h3>
				87	<!-- ======================================================================= -->
				88
				89	<p>Strangely enough, the SourceLocation class represents a location within the
				90	source code of the program. Important design points include:</p>
				91
				92	<ol>
				93	<li>sizeof(SourceLocation) must be extremely small, as these are embedded into
				94	many AST nodes and are passed around often. Currently it is 32 bits.</li>
				95	<li>SourceLocation must be a simple value object that can be efficiently
				96	copied.</li>
				97	<li>We should be able to represent a source location for any byte of any input
				98	file. This includes in the middle of tokens, in whitespace, in trigraphs,
				99	etc.</li>
				100	<li>A SourceLocation must encode the current #include stack that was active when
				101	the location was processed. For example, if the location corresponds to a
				102	token, it should contain the set of #includes active when the token was
				103	lexed. This allows us to print the #include stack for a diagnostic.</li>
				104	<li>SourceLocation must be able to describe macro expansions, capturing both
				105	the ultimate instantiation point and the source of the original character
				106	data.</li>
				107	</ol>
				108
				109	<p>In practice, the SourceLocation works together with the SourceManager class
				110	to encode two pieces of information about a location: it's physical location
				111	and it's virtual location. For most tokens, these will be the same. However,
				112	for a macro expansion (or tokens that came from a _Pragma directive) these will
				113	describe the location of the characters corresponding to the token and the
				114	location where the token was used (i.e. the macro instantiation point or the
				115	location of the _Pragma itself).</p>
				116
				117	<p>For efficiency, we only track one level of macro instantions: if a token was
				118	produced by multiple instantiations, we only track the source and ultimate
				119	destination. Though we could track the intermediate instantiation points, this
				120	would require extra bookkeeping and no known client would benefit substantially
				121	from this.</p>
				122
				123	<p>The clang front-end inherently depends on the location of a token being
				124	tracked correctly. If it is ever incorrect, the front-end may get confused and
				125	die. The reason for this is that the notion of the 'spelling' of a Token in
				126	clang depends on being able to find the original input characters for the token.
				127	This concept maps directly to the "physical" location for the token.</p>
				128
				129	<!-- ======================================================================= -->
				130	<h2 id="liblex">The Lexer and Preprocessor Library</h2>
				131	<!-- ======================================================================= -->
				132
				133	<p>The Lexer library contains several tightly-connected classes that are involved
				134	with the nasty process of lexing and preprocessing C source code. The main
				135	interface to this library for outside clients is the large <a
				136	href="#Preprocessor">Preprocessor</a> class.
				137	It contains the various pieces of state that are required to coherently read
				138	tokens out of a translation unit.</p>
				139
				140	<p>The core interface to the Preprocessor object (once it is set up) is the
				141	Preprocessor::Lex method, which returns the next <a href="#Token">Token</a> from
				142	the preprocessor stream. There are two types of token providers that the
				143	preprocessor is capable of reading from: a buffer lexer (provided by the <a
				144	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]	145	href="#TokenLexer">TokenLexer</a> class).
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	146
				147
				148	<!-- ======================================================================= -->
				149	<h3 id="Token">The Token class</h3>
				150	<!-- ======================================================================= -->
				151
				152	<p>The Token class is used to represent a single lexed token. Tokens are
				153	intended to be used by the lexer/preprocess and parser libraries, but are not
				154	intended to live beyond them (for example, they should not live in the ASTs).<p>
				155
				156	<p>Tokens most often live on the stack (or some other location that is efficient
				157	to access) as the parser is running, but occasionally do get buffered up. For
				158	example, macro definitions are stored as a series of tokens, and the C++
				159	front-end will eventually need to buffer tokens up for tentative parsing and
				160	various pieces of look-ahead. As such, the size of a Token matter. On a 32-bit
				161	system, sizeof(Token) is currently 16 bytes.</p>
				162
				163	<p>Tokens contain the following information:</p>
				164
				165	<ul>
				166	<li><b>A SourceLocation</b> - This indicates the location of the start of the
				167	token.</li>
				168
				169	<li><b>A length</b> - This stores the length of the token as stored in the
				170	SourceBuffer. For tokens that include them, this length includes trigraphs and
				171	escaped newlines which are ignored by later phases of the compiler. By pointing
				172	into the original source buffer, it is always possible to get the original
				173	spelling of a token completely accurately.</li>
				174
				175	<li><b>IdentifierInfo</b> - If a token takes the form of an identifier, and if
				176	identifier lookup was enabled when the token was lexed (e.g. the lexer was not
				177	reading in 'raw' mode) this contains a pointer to the unique hash value for the
				178	identifier. Because the lookup happens before keyword identification, this
				179	field is set even for language keywords like 'for'.</li>
				180
				181	<li><b>TokenKind</b> - This indicates the kind of token as classified by the
				182	lexer. This includes things like <tt>tok::starequal</tt> (for the "*="
				183	operator), <tt>tok::ampamp</tt> for the "&&" token, and keyword values
				184	(e.g. <tt>tok::kw_for</tt>) for identifiers that correspond to keywords. Note
				185	that some tokens can be spelled multiple ways. For example, C++ supports
				186	"operator keywords", where things like "and" are treated exactly like the
				187	"&&" operator. In these cases, the kind value is set to
				188	<tt>tok::ampamp</tt>, which is good for the parser, which doesn't have to
				189	consider both forms. For something that cares about which form is used (e.g.
				190	the preprocessor 'stringize' operator) the spelling indicates the original
				191	form.</li>
				192
				193	<li><b>Flags</b> - There are currently four flags tracked by the
				194	lexer/preprocessor system on a per-token basis:
				195
				196	<ol>
				197	<li><b>StartOfLine</b> - This was the first token that occurred on its input
				198	source line.</li>
				199	<li><b>LeadingSpace</b> - There was a space character either immediately
				200	before the token or transitively before the token as it was expanded
				201	through a macro. The definition of this flag is very closely defined by
				202	the stringizing requirements of the preprocessor.</li>
				203	<li><b>DisableExpand</b> - This flag is used internally to the preprocessor to
				204	represent identifier tokens which have macro expansion disabled. This
				205	prevents them from being considered as candidates for macro expansion ever
				206	in the future.</li>
				207	<li><b>NeedsCleaning</b> - This flag is set if the original spelling for the
				208	token includes a trigraph or escaped newline. Since this is uncommon,
				209	many pieces of code can fast-path on tokens that did not need cleaning.
				210	</p>
				211	</ol>
				212	</li>
				213	</ul>
				214
				215	<p>One interesting (and somewhat unusual) aspect of tokens is that they don't
				216	contain any semantic information about the lexed value. For example, if the
				217	token was a pp-number token, we do not represent the value of the number that
				218	was lexed (this is left for later pieces of code to decide). Additionally, the
				219	lexer library has no notion of typedef names vs variable names: both are
				220	returned as identifiers, and the parser is left to decide whether a specific
				221	identifier is a typedef or a variable (tracking this requires scope information
				222	among other things).</p>
				223
				224	<!-- ======================================================================= -->
				225	<h3 id="Lexer">The Lexer class</h3>
				226	<!-- ======================================================================= -->
				227
				228	<p>The Lexer class provides the mechanics of lexing tokens out of a source
				229	buffer and deciding what they mean. The Lexer is complicated by the fact that
				230	it operates on raw buffers that have not had spelling eliminated (this is a
				231	necessity to get decent performance), but this is countered with careful coding
				232	as well as standard performance techniques (for example, the comment handling
				233	code is vectorized on X86 and PowerPC hosts).</p>
				234
				235	<p>The lexer has a couple of interesting modal features:</p>
				236
				237	<ul>
				238	<li>The lexer can operate in 'raw' mode. This mode has several features that
				239	make it possible to quickly lex the file (e.g. it stops identifier lookup,
				240	doesn't specially handle preprocessor tokens, handles EOF differently, etc).
				241	This mode is used for lexing within an "<tt>#if 0</tt>" block, for
				242	example.</li>
				243	<li>The lexer can capture and return comments as tokens. This is required to
				244	support the -C preprocessor mode, which passes comments through, and is
				245	used by the diagnostic checker to identifier expect-error annotations.</li>
				246	<li>The lexer can be in ParsingFilename mode, which happens when preprocessing
Chris Lattner	8438624	2007-09-16 19:25:23 +0000	[diff] [blame]	247	after reading a #include directive. This mode changes the parsing of '<'
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	248	to return an "angled string" instead of a bunch of tokens for each thing
				249	within the filename.</li>
				250	<li>When parsing a preprocessor directive (after "<tt>#</tt>") the
				251	ParsingPreprocessorDirective mode is entered. This changes the parser to
				252	return EOM at a newline.</li>
				253	<li>The Lexer uses a LangOptions object to know whether trigraphs are enabled,
				254	whether C++ or ObjC keywords are recognized, etc.</li>
				255	</ul>
				256
				257	<p>In addition to these modes, the lexer keeps track of a couple of other
				258	features that are local to a lexed buffer, which change as the buffer is
				259	lexed:</p>
				260
				261	<ul>
				262	<li>The Lexer uses BufferPtr to keep track of the current character being
				263	lexed.</li>
				264	<li>The Lexer uses IsAtStartOfLine to keep track of whether the next lexed token
				265	will start with its "start of line" bit set.</li>
				266	<li>The Lexer keeps track of the current #if directives that are active (which
				267	can be nested).</li>
				268	<li>The Lexer keeps track of an <a href="#MultipleIncludeOpt">
				269	MultipleIncludeOpt</a> object, which is used to
				270	detect whether the buffer uses the standard "<tt>#ifndef XX</tt> /
				271	<tt>#define XX</tt>" idiom to prevent multiple inclusion. If a buffer does,
				272	subsequent includes can be ignored if the XX macro is defined.</li>
				273	</ul>
				274
				275	<!-- ======================================================================= -->
Chris Lattner	7928125	2008-03-09 02:27:26 +0000	[diff] [blame]	276	<h3 id="TokenLexer">The TokenLexer class</h3>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	277	<!-- ======================================================================= -->
				278
Chris Lattner	7928125	2008-03-09 02:27:26 +0000	[diff] [blame]	279	<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]	280	of tokens that came from somewhere else. It typically used for two things: 1)
				281	returning tokens from a macro definition as it is being expanded 2) returning
				282	tokens from an arbitrary buffer of tokens. The later use is used by _Pragma and
				283	will most likely be used to handle unbounded look-ahead for the C++ parser.</p>
				284
				285	<!-- ======================================================================= -->
				286	<h3 id="MultipleIncludeOpt">The MultipleIncludeOpt class</h3>
				287	<!-- ======================================================================= -->
				288
				289	<p>The MultipleIncludeOpt class implements a really simple little state machine
				290	that is used to detect the standard "<tt>#ifndef XX</tt> / <tt>#define XX</tt>"
				291	idiom that people typically use to prevent multiple inclusion of headers. If a
				292	buffer uses this idiom and is subsequently #include'd, the preprocessor can
				293	simply check to see whether the guarding condition is defined or not. If so,
				294	the preprocessor can completely ignore the include of the header.</p>
				295
				296
				297
				298	<!-- ======================================================================= -->
				299	<h2 id="libparse">The Parser Library</h2>
				300	<!-- ======================================================================= -->
				301
				302	<!-- ======================================================================= -->
				303	<h2 id="libast">The AST Library</h2>
				304	<!-- ======================================================================= -->
				305
				306	<!-- ======================================================================= -->
				307	<h3 id="Type">The Type class and its subclasses</h3>
				308	<!-- ======================================================================= -->
				309
				310	<p>The Type class (and its subclasses) are an important part of the AST. Types
				311	are accessed through the ASTContext class, which implicitly creates and uniques
				312	them as they are needed. Types have a couple of non-obvious features: 1) they
				313	do not capture type qualifiers like const or volatile (See
				314	<a href="#QualType">QualType</a>), and 2) they implicitly capture typedef
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	315	information. Once created, types are immutable (unlike decls).</p>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	316
				317	<p>Typedefs in C make semantic analysis a bit more complex than it would
				318	be without them. The issue is that we want to capture typedef information
				319	and represent it in the AST perfectly, but the semantics of operations need to
				320	"see through" typedefs. For example, consider this code:</p>
				321
				322	<code>
				323	void func() {<br>
Bill Wendling	30d1775	2007-10-06 01:56:01 +0000	[diff] [blame]	324	typedef int foo;<br>
				325	foo X, *Y;<br>
				326	typedef foo* bar;<br>
				327	bar Z;<br>
				328	*X; <i>// error</i><br>
				329	**Y; <i>// error</i><br>
				330	**Z; <i>// error</i><br>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	331	}<br>
				332	</code>
				333
				334	<p>The code above is illegal, and thus we expect there to be diagnostics emitted
				335	on the annotated lines. In this example, we expect to get:</p>
				336
				337	<pre>
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	338	<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]	339	*X; // error
				340	<font color="blue">^~</font>
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	341	<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]	342	**Y; // error
				343	<font color="blue">^~~</font>
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	344	<b>test.c:8:1: error: indirection requires pointer operand ('foo' invalid)</b>
				345	**Z; // error
				346	<font color="blue">^~~</font>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	347	</pre>
				348
				349	<p>While this example is somewhat silly, it illustrates the point: we want to
				350	retain typedef information where possible, so that we can emit errors about
				351	"<tt>std::string</tt>" instead of "<tt>std::basic_string<char, std:...</tt>".
				352	Doing this requires properly keeping typedef information (for example, the type
				353	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]	354	various operators (for example, the type of *Y is "foo", not "int"). In order
				355	to retain this information, the type of these expressions is an instance of the
				356	TypedefType class, which indicates that the type of these expressions is a
				357	typedef for foo.
				358	</p>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	359
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	360	<p>Representing types like this is great for diagnostics, because the
				361	user-specified type is always immediately available. There are two problems
				362	with this: first, various semantic checks need to make judgements about the
Chris Lattner	33fc68a	2007-07-31 18:54:50 +0000	[diff] [blame]	363	<em>actual structure</em> of a type, ignoring typdefs. Second, we need an
				364	efficient way to query whether two types are structurally identical to each
				365	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]	366	canonical types.</p>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	367
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	368	<h4>Canonical Types</h4>
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	<p>Every instance of the Type class contains a canonical type pointer. For
				371	simple types with no typedefs involved (e.g. "<tt>int</tt>", "<tt>int*</tt>",
				372	"<tt>int**</tt>"), the type just points to itself. For types that have a
				373	typedef somewhere in their structure (e.g. "<tt>foo</tt>", "<tt>foo*</tt>",
				374	"<tt>foo**</tt>", "<tt>bar</tt>"), the canonical type pointer points to their
				375	structurally equivalent type without any typedefs (e.g. "<tt>int</tt>",
				376	"<tt>int</tt>", "<tt>int</tt>", and "<tt>int</tt>" respectively).</p>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	377
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	378	<p>This design provides a constant time operation (dereferencing the canonical
				379	type pointer) that gives us access to the structure of types. For example,
				380	we can trivially tell that "bar" and "foo*" are the same type by dereferencing
				381	their canonical type pointers and doing a pointer comparison (they both point
				382	to the single "<tt>int*</tt>" type).</p>
				383
				384	<p>Canonical types and typedef types bring up some complexities that must be
				385	carefully managed. Specifically, the "isa/cast/dyncast" operators generally
				386	shouldn't be used in code that is inspecting the AST. For example, when type
				387	checking the indirection operator (unary '*' on a pointer), the type checker
				388	must verify that the operand has a pointer type. It would not be correct to
				389	check that with "<tt>isa<PointerType>(SubExpr->getType())</tt>",
				390	because this predicate would fail if the subexpression had a typedef type.</p>
				391
				392	<p>The solution to this problem are a set of helper methods on Type, used to
				393	check their properties. In this case, it would be correct to use
				394	"<tt>SubExpr->getType()->isPointerType()</tt>" to do the check. This
				395	predicate will return true if the <em>canonical type is a pointer</em>, which is
				396	true any time the type is structurally a pointer type. The only hard part here
				397	is remembering not to use the <tt>isa/cast/dyncast</tt> operations.</p>
				398
				399	<p>The second problem we face is how to get access to the pointer type once we
				400	know it exists. To continue the example, the result type of the indirection
				401	operator is the pointee type of the subexpression. In order to determine the
				402	type, we need to get the instance of PointerType that best captures the typedef
				403	information in the program. If the type of the expression is literally a
				404	PointerType, we can return that, otherwise we have to dig through the
				405	typedefs to find the pointer type. For example, if the subexpression had type
				406	"<tt>foo*</tt>", we could return that type as the result. If the subexpression
				407	had type "<tt>bar</tt>", we want to return "<tt>foo*</tt>" (note that we do
				408	<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]	409	a getAsPointerType() method that checks whether the type is structurally a
Chris Lattner	8a2bc62	2007-07-31 06:37:39 +0000	[diff] [blame]	410	PointerType and, if so, returns the best one. If not, it returns a null
				411	pointer.</p>
				412
				413	<p>This structure is somewhat mystical, but after meditating on it, it will
				414	make sense to you :).</p>
Chris Lattner	86920d3	2007-07-31 05:42:17 +0000	[diff] [blame]	415
				416	<!-- ======================================================================= -->
				417	<h3 id="QualType">The QualType class</h3>
				418	<!-- ======================================================================= -->
				419
				420	<p>The QualType class is designed as a trivial value class that is small,
				421	passed by-value and is efficient to query. The idea of QualType is that it
				422	stores the type qualifiers (const, volatile, restrict) separately from the types
				423	themselves: QualType is conceptually a pair of "Type*" and bits for the type
				424	qualifiers.</p>
				425
				426	<p>By storing the type qualifiers as bits in the conceptual pair, it is
				427	extremely efficient to get the set of qualifiers on a QualType (just return the
				428	field of the pair), add a type qualifier (which is a trivial constant-time
				429	operation that sets a bit), and remove one or more type qualifiers (just return
				430	a QualType with the bitfield set to empty).</p>
				431
				432	<p>Further, because the bits are stored outside of the type itself, we do not
				433	need to create duplicates of types with different sets of qualifiers (i.e. there
				434	is only a single heap allocated "int" type: "const int" and "volatile const int"
				435	both point to the same heap allocated "int" type). This reduces the heap size
				436	used to represent bits and also means we do not have to consider qualifiers when
				437	uniquing types (<a href="#Type">Type</a> does not even contain qualifiers).</p>
				438
				439	<p>In practice, on hosts where it is safe, the 3 type qualifiers are stored in
				440	the low bit of the pointer to the Type object. This means that QualType is
				441	exactly the same size as a pointer, and this works fine on any system where
				442	malloc'd objects are at least 8 byte aligned.</p>
Ted Kremenek	8bc0571	2007-10-10 23:01:43 +0000	[diff] [blame]	443
				444	<!-- ======================================================================= -->
				445	<h3 id="CFG">The <tt>CFG</tt> class</h3>
				446	<!-- ======================================================================= -->
				447
				448	<p>The <tt>CFG</tt> class is designed to represent a source-level
				449	control-flow graph for a single statement (<tt>Stmt*</tt>). Typically
				450	instances of <tt>CFG</tt> are constructed for function bodies (usually
				451	an instance of <tt>CompoundStmt</tt>), but can also be instantiated to
				452	represent the control-flow of any class that subclasses <tt>Stmt</tt>,
				453	which includes simple expressions. Control-flow graphs are especially
				454	useful for performing
				455	<a href="http://en.wikipedia.org/wiki/Data_flow_analysis#Sensitivities">flow-
				456	or path-sensitive</a> program analyses on a given function.</p>
				457
				458	<h4>Basic Blocks</h4>
				459
				460	<p>Concretely, an instance of <tt>CFG</tt> is a collection of basic
				461	blocks. Each basic block is an instance of <tt>CFGBlock</tt>, which
				462	simply contains an ordered sequence of <tt>Stmt*</tt> (each referring
				463	to statements in the AST). The ordering of statements within a block
				464	indicates unconditional flow of control from one statement to the
				465	next. <a href="#ConditionalControlFlow">Conditional control-flow</a>
				466	is represented using edges between basic blocks. The statements
				467	within a given <tt>CFGBlock</tt> can be traversed using
				468	the <tt>CFGBlock::*iterator</tt> interface.</p>
				469
				470	<p>
Ted Kremenek	18e17e7	2007-10-18 22:50:52 +0000	[diff] [blame]	471	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]	472	the control-flow graph it represents. Each <tt>CFGBlock</tt> within a
				473	CFG is also uniquely numbered (accessible
				474	via <tt>CFGBlock::getBlockID()</tt>). Currently the number is
				475	based on the ordering the blocks were created, but no assumptions
				476	should be made on how <tt>CFGBlock</tt>s are numbered other than their
				477	numbers are unique and that they are numbered from 0..N-1 (where N is
				478	the number of basic blocks in the CFG).</p>
				479
				480	<h4>Entry and Exit Blocks</h4>
				481
				482	Each instance of <tt>CFG</tt> contains two special blocks:
				483	an <i>entry</i> block (accessible via <tt>CFG::getEntry()</tt>), which
				484	has no incoming edges, and an <i>exit</i> block (accessible
				485	via <tt>CFG::getExit()</tt>), which has no outgoing edges. Neither
				486	block contains any statements, and they serve the role of providing a
				487	clear entrance and exit for a body of code such as a function body.
				488	The presence of these empty blocks greatly simplifies the
				489	implementation of many analyses built on top of CFGs.
				490
				491	<h4 id ="ConditionalControlFlow">Conditional Control-Flow</h4>
				492
				493	<p>Conditional control-flow (such as those induced by if-statements
				494	and loops) is represented as edges between <tt>CFGBlock</tt>s.
				495	Because different C language constructs can induce control-flow,
				496	each <tt>CFGBlock</tt> also records an extra <tt>Stmt*</tt> that
				497	represents the <i>terminator</i> of the block. A terminator is simply
				498	the statement that caused the control-flow, and is used to identify
				499	the nature of the conditional control-flow between blocks. For
				500	example, in the case of an if-statement, the terminator refers to
				501	the <tt>IfStmt</tt> object in the AST that represented the given
				502	branch.</p>
				503
				504	<p>To illustrate, consider the following code example:</p>
				505
				506	<code>
				507	int foo(int x) {<br>
				508	x = x + 1;<br>
				509	<br>
				510	if (x > 2) x++;<br>
				511	else {<br>
				512	x += 2;<br>
				513	x *= 2;<br>
				514	}<br>
				515	<br>
				516	return x;<br>
				517	}
				518	</code>
				519
				520	<p>After invoking the parser+semantic analyzer on this code fragment,
				521	the AST of the body of <tt>foo</tt> is referenced by a
				522	single <tt>Stmt*</tt>. We can then construct an instance
				523	of <tt>CFG</tt> representing the control-flow graph of this function
				524	body by single call to a static class method:</p>
				525
				526	<code>
				527	Stmt* FooBody = ...<br>
				528	CFG* FooCFG = <b>CFG::buildCFG</b>(FooBody);
				529	</code>
				530
				531	<p>It is the responsibility of the caller of <tt>CFG::buildCFG</tt>
				532	to <tt>delete</tt> the returned <tt>CFG*</tt> when the CFG is no
				533	longer needed.</p>
				534
				535	<p>Along with providing an interface to iterate over
				536	its <tt>CFGBlock</tt>s, the <tt>CFG</tt> class also provides methods
				537	that are useful for debugging and visualizing CFGs. For example, the
				538	method
				539	<tt>CFG::dump()</tt> dumps a pretty-printed version of the CFG to
				540	standard error. This is especially useful when one is using a
				541	debugger such as gdb. For example, here is the output
				542	of <tt>FooCFG->dump()</tt>:</p>
				543
				544	<code>
				545	[ B5 (ENTRY) ]<br>
				546	Predecessors (0):<br>
				547	Successors (1): B4<br>
				548	<br>
				549	[ B4 ]<br>
				550	1: x = x + 1<br>
				551	2: (x > 2)<br>
				552	<b>T: if [B4.2]</b><br>
				553	Predecessors (1): B5<br>
				554	Successors (2): B3 B2<br>
				555	<br>
				556	[ B3 ]<br>
				557	1: x++<br>
				558	Predecessors (1): B4<br>
				559	Successors (1): B1<br>
				560	<br>
				561	[ B2 ]<br>
				562	1: x += 2<br>
				563	2: x *= 2<br>
				564	Predecessors (1): B4<br>
				565	Successors (1): B1<br>
				566	<br>
				567	[ B1 ]<br>
				568	1: return x;<br>
				569	Predecessors (2): B2 B3<br>
				570	Successors (1): B0<br>
				571	<br>
				572	[ B0 (EXIT) ]<br>
				573	Predecessors (1): B1<br>
				574	Successors (0):
				575	</code>
				576
				577	<p>For each block, the pretty-printed output displays for each block
				578	the number of <i>predecessor</i> blocks (blocks that have outgoing
				579	control-flow to the given block) and <i>successor</i> blocks (blocks
				580	that have control-flow that have incoming control-flow from the given
				581	block). We can also clearly see the special entry and exit blocks at
				582	the beginning and end of the pretty-printed output. For the entry
				583	block (block B5), the number of predecessor blocks is 0, while for the
				584	exit block (block B0) the number of successor blocks is 0.</p>
				585
				586	<p>The most interesting block here is B4, whose outgoing control-flow
				587	represents the branching caused by the sole if-statement
				588	in <tt>foo</tt>. Of particular interest is the second statement in
				589	the block, <b><tt>(x > 2)</tt></b>, and the terminator, printed
				590	as <b><tt>if [B4.2]</tt></b>. The second statement represents the
				591	evaluation of the condition of the if-statement, which occurs before
				592	the actual branching of control-flow. Within the <tt>CFGBlock</tt>
				593	for B4, the <tt>Stmt*</tt> for the second statement refers to the
				594	actual expression in the AST for <b><tt>(x > 2)</tt></b>. Thus
				595	pointers to subclasses of <tt>Expr</tt> can appear in the list of
				596	statements in a block, and not just subclasses of <tt>Stmt</tt> that
				597	refer to proper C statements.</p>
				598
				599	<p>The terminator of block B4 is a pointer to the <tt>IfStmt</tt>
				600	object in the AST. The pretty-printer outputs <b><tt>if
				601	[B4.2]</tt></b> because the condition expression of the if-statement
				602	has an actual place in the basic block, and thus the terminator is
				603	essentially
				604	<i>referring</i> to the expression that is the second statement of
				605	block B4 (i.e., B4.2). In this manner, conditions for control-flow
				606	(which also includes conditions for loops and switch statements) are
				607	hoisted into the actual basic block.</p>
				608
Ted Kremenek	98f19b6	2007-10-10 23:22:00 +0000	[diff] [blame]	609	<!--
Ted Kremenek	8bc0571	2007-10-10 23:01:43 +0000	[diff] [blame]	610	<h4>Implicit Control-Flow</h4>
Ted Kremenek	98f19b6	2007-10-10 23:22:00 +0000	[diff] [blame]	611	-->
Ted Kremenek	8bc0571	2007-10-10 23:01:43 +0000	[diff] [blame]	612
				613	<!--
				614	<p>A key design principle of the <tt>CFG</tt> class was to not require
				615	any transformations to the AST in order to represent control-flow.
				616	Thus the <tt>CFG</tt> does not perform any "lowering" of the
				617	statements in an AST: loops are not transformed into guarded gotos,
				618	short-circuit operations are not converted to a set of if-statements,
				619	and so on.</p>
				620	-->
Ted Kremenek	17a295d	2008-06-11 06:19:49 +0000	[diff] [blame]	621
				622	</div>
				623	</body>
				624	</html>