• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1Inlining
2========
3
4There are several options that control which calls the analyzer will consider for
5inlining. The major one is -analyzer-config ipa:
6
7  -analyzer-config ipa=none - All inlining is disabled. This is the only mode
8     available in LLVM 3.1 and earlier and in Xcode 4.3 and earlier.
9
10  -analyzer-config ipa=basic-inlining - Turns on inlining for C functions, C++
11     static member functions, and blocks -- essentially, the calls that behave
12     like simple C function calls. This is essentially the mode used in
13     Xcode 4.4.
14
15  -analyzer-config ipa=inlining - Turns on inlining when we can confidently find
16    the function/method body corresponding to the call. (C functions, static
17    functions, devirtualized C++ methods, Objective-C class methods, Objective-C
18    instance methods when ExprEngine is confident about the dynamic type of the
19    instance).
20
21  -analyzer-config ipa=dynamic - Inline instance methods for which the type is
22   determined at runtime and we are not 100% sure that our type info is
23   correct. For virtual calls, inline the most plausible definition.
24
25  -analyzer-config ipa=dynamic-bifurcate - Same as -analyzer-config ipa=dynamic,
26   but the path is split. We inline on one branch and do not inline on the
27   other. This mode does not drop the coverage in cases when the parent class
28   has code that is only exercised when some of its methods are overridden.
29
30Currently, -analyzer-config ipa=dynamic-bifurcate is the default mode.
31
32While -analyzer-config ipa determines in general how aggressively the analyzer
33will try to inline functions, several additional options control which types of
34functions can inlined, in an all-or-nothing way. These options use the
35analyzer's configuration table, so they are all specified as follows:
36
37    -analyzer-config OPTION=VALUE
38
39### c++-inlining ###
40
41This option controls which C++ member functions may be inlined.
42
43    -analyzer-config c++-inlining=[none | methods | constructors | destructors]
44
45Each of these modes implies that all the previous member function kinds will be
46inlined as well; it doesn't make sense to inline destructors without inlining
47constructors, for example.
48
49The default c++-inlining mode is 'destructors', meaning that all member
50functions with visible definitions will be considered for inlining. In some
51cases the analyzer may still choose not to inline the function.
52
53Note that under 'constructors', constructors for types with non-trivial
54destructors will not be inlined. Additionally, no C++ member functions will be
55inlined under -analyzer-config ipa=none or -analyzer-config ipa=basic-inlining,
56regardless of the setting of the c++-inlining mode.
57
58### c++-template-inlining ###
59
60This option controls whether C++ templated functions may be inlined.
61
62    -analyzer-config c++-template-inlining=[true | false]
63
64Currently, template functions are considered for inlining by default.
65
66The motivation behind this option is that very generic code can be a source
67of false positives, either by considering paths that the caller considers
68impossible (by some unstated precondition), or by inlining some but not all
69of a deep implementation of a function.
70
71### c++-stdlib-inlining ###
72
73This option controls whether functions from the C++ standard library, including
74methods of the container classes in the Standard Template Library, should be
75considered for inlining.
76
77    -analyzer-config c++-stdlib-inlining=[true | false]
78
79Currently, C++ standard library functions are considered for inlining by
80default.
81
82The standard library functions and the STL in particular are used ubiquitously
83enough that our tolerance for false positives is even lower here. A false
84positive due to poor modeling of the STL leads to a poor user experience, since
85most users would not be comfortable adding assertions to system headers in order
86to silence analyzer warnings.
87
88### c++-container-inlining ###
89
90This option controls whether constructors and destructors of "container" types
91should be considered for inlining.
92
93    -analyzer-config c++-container-inlining=[true | false]
94
95Currently, these constructors and destructors are NOT considered for inlining
96by default.
97
98The current implementation of this setting checks whether a type has a member
99named 'iterator' or a member named 'begin'; these names are idiomatic in C++,
100with the latter specified in the C++11 standard. The analyzer currently does a
101fairly poor job of modeling certain data structure invariants of container-like
102objects. For example, these three expressions should be equivalent:
103
104    std::distance(c.begin(), c.end()) == 0
105    c.begin() == c.end()
106    c.empty())
107
108Many of these issues are avoided if containers always have unknown, symbolic
109state, which is what happens when their constructors are treated as opaque.
110In the future, we may decide specific containers are "safe" to model through
111inlining, or choose to model them directly using checkers instead.
112
113
114Basics of Implementation
115-----------------------
116
117The low-level mechanism of inlining a function is handled in
118ExprEngine::inlineCall and ExprEngine::processCallExit.
119
120If the conditions are right for inlining, a CallEnter node is created and added
121to the analysis work list. The CallEnter node marks the change to a new
122LocationContext representing the called function, and its state includes the
123contents of the new stack frame. When the CallEnter node is actually processed,
124its single successor will be a edge to the first CFG block in the function.
125
126Exiting an inlined function is a bit more work, fortunately broken up into
127reasonable steps:
128
1291. The CoreEngine realizes we're at the end of an inlined call and generates a
130   CallExitBegin node.
131
1322. ExprEngine takes over (in processCallExit) and finds the return value of the
133   function, if it has one. This is bound to the expression that triggered the
134   call. (In the case of calls without origin expressions, such as destructors,
135   this step is skipped.)
136
1373. Dead symbols and bindings are cleaned out from the state, including any local
138   bindings.
139
1404. A CallExitEnd node is generated, which marks the transition back to the
141   caller's LocationContext.
142
1435. Custom post-call checks are processed and the final nodes are pushed back
144   onto the work list, so that evaluation of the caller can continue.
145
146Retry Without Inlining
147----------------------
148
149In some cases, we would like to retry analysis without inlining a particular
150call.
151
152Currently, we use this technique to recover coverage in case we stop
153analyzing a path due to exceeding the maximum block count inside an inlined
154function.
155
156When this situation is detected, we walk up the path to find the first node
157before inlining was started and enqueue it on the WorkList with a special
158ReplayWithoutInlining bit added to it (ExprEngine::replayWithoutInlining).  The
159path is then re-analyzed from that point without inlining that particular call.
160
161Deciding When to Inline
162-----------------------
163
164In general, the analyzer attempts to inline as much as possible, since it
165provides a better summary of what actually happens in the program.  There are
166some cases, however, where the analyzer chooses not to inline:
167
168- If there is no definition available for the called function or method.  In
169  this case, there is no opportunity to inline.
170
171- If the CFG cannot be constructed for a called function, or the liveness
172  cannot be computed.  These are prerequisites for analyzing a function body,
173  with or without inlining.
174
175- If the LocationContext chain for a given ExplodedNode reaches a maximum cutoff
176  depth.  This prevents unbounded analysis due to infinite recursion, but also
177  serves as a useful cutoff for performance reasons.
178
179- If the function is variadic.  This is not a hard limitation, but an engineering
180  limitation.
181
182  Tracked by: <rdar://problem/12147064> Support inlining of variadic functions
183
184- In C++, constructors are not inlined unless the destructor call will be
185  processed by the ExprEngine. Thus, if the CFG was built without nodes for
186  implicit destructors, or if the destructors for the given object are not
187  represented in the CFG, the constructor will not be inlined. (As an exception,
188  constructors for objects with trivial constructors can still be inlined.)
189  See "C++ Caveats" below.
190
191- In C++, ExprEngine does not inline custom implementations of operator 'new'
192  or operator 'delete', nor does it inline the constructors and destructors
193  associated with these. See "C++ Caveats" below.
194
195- Calls resulting in "dynamic dispatch" are specially handled.  See more below.
196
197- The FunctionSummaries map stores additional information about declarations,
198  some of which is collected at runtime based on previous analyses.
199  We do not inline functions which were not profitable to inline in a different
200  context (for example, if the maximum block count was exceeded; see
201  "Retry Without Inlining").
202
203
204Dynamic Calls and Devirtualization
205----------------------------------
206
207"Dynamic" calls are those that are resolved at runtime, such as C++ virtual
208method calls and Objective-C message sends. Due to the path-sensitive nature of
209the analysis, the analyzer may be able to reason about the dynamic type of the
210object whose method is being called and thus "devirtualize" the call.
211
212This path-sensitive devirtualization occurs when the analyzer can determine what
213method would actually be called at runtime.  This is possible when the type
214information is constrained enough for a simulated C++/Objective-C object that
215the analyzer can make such a decision.
216
217 == DynamicTypeInfo ==
218
219As the analyzer analyzes a path, it may accrue information to refine the
220knowledge about the type of an object.  This can then be used to make better
221decisions about the target method of a call.
222
223Such type information is tracked as DynamicTypeInfo.  This is path-sensitive
224data that is stored in ProgramState, which defines a mapping from MemRegions to
225an (optional) DynamicTypeInfo.
226
227If no DynamicTypeInfo has been explicitly set for a MemRegion, it will be lazily
228inferred from the region's type or associated symbol. Information from symbolic
229regions is weaker than from true typed regions.
230
231  EXAMPLE: A C++ object declared "A obj" is known to have the class 'A', but a
232           reference "A &ref" may dynamically be a subclass of 'A'.
233
234The DynamicTypePropagation checker gathers and propagates DynamicTypeInfo,
235updating it as information is observed along a path that can refine that type
236information for a region.
237
238  WARNING: Not all of the existing analyzer code has been retrofitted to use
239           DynamicTypeInfo, nor is it universally appropriate. In particular,
240           DynamicTypeInfo always applies to a region with all casts stripped
241           off, but sometimes the information provided by casts can be useful.
242
243
244 == RuntimeDefinition ==
245
246The basis of devirtualization is CallEvent's getRuntimeDefinition() method,
247which returns a RuntimeDefinition object.  When asked to provide a definition,
248the CallEvents for dynamic calls will use the DynamicTypeInfo in their
249ProgramState to attempt to devirtualize the call.  In the case of no dynamic
250dispatch, or perfectly constrained devirtualization, the resulting
251RuntimeDefinition contains a Decl corresponding to the definition of the called
252function, and RuntimeDefinition::mayHaveOtherDefinitions will return FALSE.
253
254In the case of dynamic dispatch where our information is not perfect, CallEvent
255can make a guess, but RuntimeDefinition::mayHaveOtherDefinitions will return
256TRUE. The RuntimeDefinition object will then also include a MemRegion
257corresponding to the object being called (i.e., the "receiver" in Objective-C
258parlance), which ExprEngine uses to decide whether or not the call should be
259inlined.
260
261 == Inlining Dynamic Calls ==
262
263The -analyzer-config ipa option has five different modes: none, basic-inlining,
264inlining, dynamic, and dynamic-bifurcate. Under -analyzer-config ipa=dynamic,
265all dynamic calls are inlined, whether we are certain or not that this will
266actually be the definition used at runtime. Under -analyzer-config ipa=inlining,
267only "near-perfect" devirtualized calls are inlined*, and other dynamic calls
268are evaluated conservatively (as if no definition were available).
269
270* Currently, no Objective-C messages are not inlined under
271  -analyzer-config ipa=inlining, even if we are reasonably confident of the type
272  of the receiver. We plan to enable this once we have tested our heuristics
273  more thoroughly.
274
275The last option, -analyzer-config ipa=dynamic-bifurcate, behaves similarly to
276"dynamic", but performs a conservative invalidation in the general virtual case
277in *addition* to inlining. The details of this are discussed below.
278
279As stated above, -analyzer-config ipa=basic-inlining does not inline any C++
280member functions or Objective-C method calls, even if they are non-virtual or
281can be safely devirtualized.
282
283
284Bifurcation
285-----------
286
287ExprEngine::BifurcateCall implements the -analyzer-config ipa=dynamic-bifurcate
288mode.
289
290When a call is made on an object with imprecise dynamic type information
291(RuntimeDefinition::mayHaveOtherDefinitions() evaluates to TRUE), ExprEngine
292bifurcates the path and marks the object's region (retrieved from the
293RuntimeDefinition object) with a path-sensitive "mode" in the ProgramState.
294
295Currently, there are 2 modes:
296
297 DynamicDispatchModeInlined - Models the case where the dynamic type information
298   of the receiver (MemoryRegion) is assumed to be perfectly constrained so
299   that a given definition of a method is expected to be the code actually
300   called. When this mode is set, ExprEngine uses the Decl from
301   RuntimeDefinition to inline any dynamically dispatched call sent to this
302   receiver because the function definition is considered to be fully resolved.
303
304 DynamicDispatchModeConservative - Models the case where the dynamic type
305   information is assumed to be incorrect, for example, implies that the method
306   definition is overriden in a subclass. In such cases, ExprEngine does not
307   inline the methods sent to the receiver (MemoryRegion), even if a candidate
308   definition is available. This mode is conservative about simulating the
309   effects of a call.
310
311Going forward along the symbolic execution path, ExprEngine consults the mode
312of the receiver's MemRegion to make decisions on whether the calls should be
313inlined or not, which ensures that there is at most one split per region.
314
315At a high level, "bifurcation mode" allows for increased semantic coverage in
316cases where the parent method contains code which is only executed when the
317class is subclassed. The disadvantages of this mode are a (considerable?)
318performance hit and the possibility of false positives on the path where the
319conservative mode is used.
320
321Objective-C Message Heuristics
322------------------------------
323
324ExprEngine relies on a set of heuristics to partition the set of Objective-C
325method calls into those that require bifurcation and those that do not. Below
326are the cases when the DynamicTypeInfo of the object is considered precise
327(cannot be a subclass):
328
329 - If the object was created with +alloc or +new and initialized with an -init
330   method.
331
332 - If the calls are property accesses using dot syntax. This is based on the
333   assumption that children rarely override properties, or do so in an
334   essentially compatible way.
335
336 - If the class interface is declared inside the main source file. In this case
337   it is unlikely that it will be subclassed.
338
339 - If the method is not declared outside of main source file, either by the
340   receiver's class or by any superclasses.
341
342C++ Caveats
343--------------------
344
345C++11 [class.cdtor]p4 describes how the vtable of an object is modified as it is
346being constructed or destructed; that is, the type of the object depends on
347which base constructors have been completed. This is tracked using
348DynamicTypeInfo in the DynamicTypePropagation checker.
349
350There are several limitations in the current implementation:
351
352- Temporaries are poorly modeled right now because we're not confident in the
353  placement of their destructors in the CFG. We currently won't inline their
354  constructors unless the destructor is trivial, and don't process their
355  destructors at all, not even to invalidate the region.
356
357- 'new' is poorly modeled due to some nasty CFG/design issues.  This is tracked
358  in PR12014.  'delete' is not modeled at all.
359
360- Arrays of objects are modeled very poorly right now.  ExprEngine currently
361  only simulates the first constructor and first destructor. Because of this,
362  ExprEngine does not inline any constructors or destructors for arrays.
363
364
365CallEvent
366=========
367
368A CallEvent represents a specific call to a function, method, or other body of
369code. It is path-sensitive, containing both the current state (ProgramStateRef)
370and stack space (LocationContext), and provides uniform access to the argument
371values and return type of a call, no matter how the call is written in the
372source or what sort of code body is being invoked.
373
374  NOTE: For those familiar with Cocoa, CallEvent is roughly equivalent to
375        NSInvocation.
376
377CallEvent should be used whenever there is logic dealing with function calls
378that does not care how the call occurred.
379
380Examples include checking that arguments satisfy preconditions (such as
381__attribute__((nonnull))), and attempting to inline a call.
382
383CallEvents are reference-counted objects managed by a CallEventManager. While
384there is no inherent issue with persisting them (say, in a ProgramState's GDM),
385they are intended for short-lived use, and can be recreated from CFGElements or
386non-top-level StackFrameContexts fairly easily.
387