397 lines · plain
1Inlining2========3 4There are several options that control which calls the analyzer will consider for5inlining. The major one is ``-analyzer-config ipa``:6 7* ``analyzer-config ipa=none`` - All inlining is disabled. This is the only mode8 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 behave12 like simple C function calls. This is essentially the mode used in13 Xcode 4.4.14 15* ``analyzer-config ipa=inlining`` - Turns on inlining when we can confidently find16 the function/method body corresponding to the call. (C functions, static17 functions, devirtualized C++ methods, Objective-C class methods, Objective-C18 instance methods when ExprEngine is confident about the dynamic type of the19 instance).20 21* ``analyzer-config ipa=dynamic`` - Inline instance methods for which the type is22 determined at runtime and we are not 100% sure that our type info is23 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 the27 other. This mode does not drop the coverage in cases when the parent class28 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 analyzer33will try to inline functions, several additional options control which types of34functions can inlined, in an all-or-nothing way. These options use the35analyzer's configuration table, so they are all specified as follows:36 37 ``-analyzer-config OPTION=VALUE``38 39c++-inlining40------------41 42This option controls which C++ member functions may be inlined.43 44 ``-analyzer-config c++-inlining=[none | methods | constructors | destructors]``45 46Each of these modes implies that all the previous member function kinds will be47inlined as well; it doesn't make sense to inline destructors without inlining48constructors, for example.49 50The default c++-inlining mode is 'destructors', meaning that all member51functions with visible definitions will be considered for inlining. In some52cases the analyzer may still choose not to inline the function.53 54Note that under 'constructors', constructors for types with non-trivial55destructors will not be inlined. Additionally, no C++ member functions will be56inlined under -analyzer-config ipa=none or -analyzer-config ipa=basic-inlining,57regardless of the setting of the c++-inlining mode.58 59c++-template-inlining60^^^^^^^^^^^^^^^^^^^^^61 62This option controls whether C++ templated functions may be inlined.63 64 ``-analyzer-config c++-template-inlining=[true | false]``65 66Currently, template functions are considered for inlining by default.67 68The motivation behind this option is that very generic code can be a source69of false positives, either by considering paths that the caller considers70impossible (by some unstated precondition), or by inlining some but not all71of a deep implementation of a function.72 73c++-stdlib-inlining74^^^^^^^^^^^^^^^^^^^75 76This option controls whether functions from the C++ standard library, including77methods of the container classes in the Standard Template Library, should be78considered for inlining.79 80 ``-analyzer-config c++-stdlib-inlining=[true | false]``81 82Currently, C++ standard library functions are considered for inlining by83default.84 85The standard library functions and the STL in particular are used ubiquitously86enough that our tolerance for false positives is even lower here. A false87positive due to poor modeling of the STL leads to a poor user experience, since88most users would not be comfortable adding assertions to system headers in order89to silence analyzer warnings.90 91c++-container-inlining92^^^^^^^^^^^^^^^^^^^^^^93 94This option controls whether constructors and destructors of "container" types95should be considered for inlining.96 97 ``-analyzer-config c++-container-inlining=[true | false]``98 99Currently, these constructors and destructors are NOT considered for inlining100by default.101 102The current implementation of this setting checks whether a type has a member103named 'iterator' or a member named 'begin'; these names are idiomatic in C++,104with the latter specified in the C++11 standard. The analyzer currently does a105fairly poor job of modeling certain data structure invariants of container-like106objects. For example, these three expressions should be equivalent:107 108 109.. code-block:: cpp110 111 std::distance(c.begin(), c.end()) == 0112 c.begin() == c.end()113 c.empty()114 115Many of these issues are avoided if containers always have unknown, symbolic116state, which is what happens when their constructors are treated as opaque.117In the future, we may decide specific containers are "safe" to model through118inlining, or choose to model them directly using checkers instead.119 120 121Basics of Implementation122------------------------123 124The low-level mechanism of inlining a function is handled in125ExprEngine::inlineCall and ExprEngine::processCallExit.126 127If the conditions are right for inlining, a CallEnter node is created and added128to the analysis work list. The CallEnter node marks the change to a new129LocationContext representing the called function, and its state includes the130contents of the new stack frame. When the CallEnter node is actually processed,131its single successor will be an edge to the first CFG block in the function.132 133Exiting an inlined function is a bit more work, fortunately broken up into134reasonable steps:135 1361. The CoreEngine realizes we're at the end of an inlined call and generates a137 CallExitBegin node.138 1392. ExprEngine takes over (in processCallExit) and finds the return value of the140 function, if it has one. This is bound to the expression that triggered the141 call. (In the case of calls without origin expressions, such as destructors,142 this step is skipped.)143 1443. Dead symbols and bindings are cleaned out from the state, including any local145 bindings.146 1474. A CallExitEnd node is generated, which marks the transition back to the148 caller's LocationContext.149 1505. Custom post-call checks are processed and the final nodes are pushed back151 onto the work list, so that evaluation of the caller can continue.152 153Retry Without Inlining154^^^^^^^^^^^^^^^^^^^^^^155 156In some cases, we would like to retry analysis without inlining a particular157call.158 159Currently, we use this technique to recover coverage in case we stop160analyzing a path due to exceeding the maximum block count inside an inlined161function.162 163When this situation is detected, we walk up the path to find the first node164before inlining was started and enqueue it on the WorkList with a special165ReplayWithoutInlining bit added to it (ExprEngine::replayWithoutInlining). The166path is then re-analyzed from that point without inlining that particular call.167 168Deciding When to Inline169^^^^^^^^^^^^^^^^^^^^^^^170 171In general, the analyzer attempts to inline as much as possible, since it172provides a better summary of what actually happens in the program. There are173some cases, however, where the analyzer chooses not to inline:174 175- If there is no definition available for the called function or method. In176 this case, there is no opportunity to inline.177 178- If the CFG cannot be constructed for a called function, or the liveness179 cannot be computed. These are prerequisites for analyzing a function body,180 with or without inlining.181 182- If the LocationContext chain for a given ExplodedNode reaches a maximum cutoff183 depth. This prevents unbounded analysis due to infinite recursion, but also184 serves as a useful cutoff for performance reasons.185 186- If the function is variadic. This is not a hard limitation, but an engineering187 limitation.188 189 Tracked by: <rdar://problem/12147064> Support inlining of variadic functions190 191- In C++, constructors are not inlined unless the destructor call will be192 processed by the ExprEngine. Thus, if the CFG was built without nodes for193 implicit destructors, or if the destructors for the given object are not194 represented in the CFG, the constructor will not be inlined. (As an exception,195 constructors for objects with trivial constructors can still be inlined.)196 See "C++ Caveats" below.197 198- In C++, ExprEngine does not inline custom implementations of operator 'new'199 or operator 'delete', nor does it inline the constructors and destructors200 associated with these. See "C++ Caveats" below.201 202- Calls resulting in "dynamic dispatch" are specially handled. See more below.203 204- The FunctionSummaries map stores additional information about declarations,205 some of which is collected at runtime based on previous analyses.206 We do not inline functions which were not profitable to inline in a different207 context (for example, if the maximum block count was exceeded; see208 "Retry Without Inlining").209 210 211Dynamic Calls and Devirtualization212^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^213 214"Dynamic" calls are those that are resolved at runtime, such as C++ virtual215method calls and Objective-C message sends. Due to the path-sensitive nature of216the analysis, the analyzer may be able to reason about the dynamic type of the217object whose method is being called and thus "devirtualize" the call.218 219This path-sensitive devirtualization occurs when the analyzer can determine what220method would actually be called at runtime. This is possible when the type221information is constrained enough for a simulated C++/Objective-C object that222the analyzer can make such a decision.223 224DynamicTypeInfo225^^^^^^^^^^^^^^^226 227As the analyzer analyzes a path, it may accrue information to refine the228knowledge about the type of an object. This can then be used to make better229decisions about the target method of a call.230 231Such type information is tracked as DynamicTypeInfo. This is path-sensitive232data that is stored in ProgramState, which defines a mapping from MemRegions to233an (optional) DynamicTypeInfo.234 235If no DynamicTypeInfo has been explicitly set for a MemRegion, it will be lazily236inferred from the region's type or associated symbol. Information from symbolic237regions is weaker than from true typed regions.238 239 EXAMPLE: A C++ object declared "A obj" is known to have the class 'A', but a240 reference "A &ref" may dynamically be a subclass of 'A'.241 242The DynamicTypePropagation checker gathers and propagates DynamicTypeInfo,243updating it as information is observed along a path that can refine that type244information for a region.245 246 WARNING: Not all of the existing analyzer code has been retrofitted to use247 DynamicTypeInfo, nor is it universally appropriate. In particular,248 DynamicTypeInfo always applies to a region with all casts stripped249 off, but sometimes the information provided by casts can be useful.250 251 252RuntimeDefinition253^^^^^^^^^^^^^^^^^254 255The basis of devirtualization is CallEvent's getRuntimeDefinition() method,256which returns a RuntimeDefinition object. When asked to provide a definition,257the CallEvents for dynamic calls will use the DynamicTypeInfo in their258ProgramState to attempt to devirtualize the call. In the case of no dynamic259dispatch, or perfectly constrained devirtualization, the resulting260RuntimeDefinition contains a Decl corresponding to the definition of the called261function, and RuntimeDefinition::mayHaveOtherDefinitions will return FALSE.262 263In the case of dynamic dispatch where our information is not perfect, CallEvent264can make a guess, but RuntimeDefinition::mayHaveOtherDefinitions will return265TRUE. The RuntimeDefinition object will then also include a MemRegion266corresponding to the object being called (i.e., the "receiver" in Objective-C267parlance), which ExprEngine uses to decide whether or not the call should be268inlined.269 270Inlining Dynamic Calls271^^^^^^^^^^^^^^^^^^^^^^272 273The -analyzer-config ipa option has five different modes: none, basic-inlining,274inlining, dynamic, and dynamic-bifurcate. Under -analyzer-config ipa=dynamic,275all dynamic calls are inlined, whether we are certain or not that this will276actually be the definition used at runtime. Under -analyzer-config ipa=inlining,277only "near-perfect" devirtualized calls are inlined*, and other dynamic calls278are evaluated conservatively (as if no definition were available).279 280* Currently, no Objective-C messages are not inlined under281 -analyzer-config ipa=inlining, even if we are reasonably confident of the type282 of the receiver. We plan to enable this once we have tested our heuristics283 more thoroughly.284 285The last option, -analyzer-config ipa=dynamic-bifurcate, behaves similarly to286"dynamic", but performs a conservative invalidation in the general virtual case287in *addition* to inlining. The details of this are discussed below.288 289As stated above, -analyzer-config ipa=basic-inlining does not inline any C++290member functions or Objective-C method calls, even if they are non-virtual or291can be safely devirtualized.292 293 294Bifurcation295^^^^^^^^^^^296 297ExprEngine::BifurcateCall implements the ``-analyzer-config ipa=dynamic-bifurcate``298mode.299 300When a call is made on an object with imprecise dynamic type information301(RuntimeDefinition::mayHaveOtherDefinitions() evaluates to TRUE), ExprEngine302bifurcates the path and marks the object's region (retrieved from the303RuntimeDefinition object) with a path-sensitive "mode" in the ProgramState.304 305Currently, there are 2 modes:306 307* ``DynamicDispatchModeInlined`` - Models the case where the dynamic type information308 of the receiver (MemoryRegion) is assumed to be perfectly constrained so309 that a given definition of a method is expected to be the code actually310 called. When this mode is set, ExprEngine uses the Decl from311 RuntimeDefinition to inline any dynamically dispatched call sent to this312 receiver because the function definition is considered to be fully resolved.313 314* ``DynamicDispatchModeConservative`` - Models the case where the dynamic type315 information is assumed to be incorrect, for example, implies that the method316 definition is overridden in a subclass. In such cases, ExprEngine does not317 inline the methods sent to the receiver (MemoryRegion), even if a candidate318 definition is available. This mode is conservative about simulating the319 effects of a call.320 321Going forward along the symbolic execution path, ExprEngine consults the mode322of the receiver's MemRegion to make decisions on whether the calls should be323inlined or not, which ensures that there is at most one split per region.324 325At a high level, "bifurcation mode" allows for increased semantic coverage in326cases where the parent method contains code which is only executed when the327class is subclassed. The disadvantages of this mode are a (considerable?)328performance hit and the possibility of false positives on the path where the329conservative mode is used.330 331Objective-C Message Heuristics332^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^333 334ExprEngine relies on a set of heuristics to partition the set of Objective-C335method calls into those that require bifurcation and those that do not. Below336are the cases when the DynamicTypeInfo of the object is considered precise337(cannot be a subclass):338 339 - If the object was created with +alloc or +new and initialized with an -init340 method.341 342 - If the calls are property accesses using dot syntax. This is based on the343 assumption that children rarely override properties, or do so in an344 essentially compatible way.345 346 - If the class interface is declared inside the main source file. In this case347 it is unlikely that it will be subclassed.348 349 - If the method is not declared outside of main source file, either by the350 receiver's class or by any superclasses.351 352C++ Caveats353^^^^^^^^^^^354 355C++11 [class.cdtor]p4 describes how the vtable of an object is modified as it is356being constructed or destructed; that is, the type of the object depends on357which base constructors have been completed. This is tracked using358DynamicTypeInfo in the DynamicTypePropagation checker.359 360There are several limitations in the current implementation:361 362* Temporaries are poorly modeled right now because we're not confident in the363 placement of their destructors in the CFG. We currently won't inline their364 constructors unless the destructor is trivial, and don't process their365 destructors at all, not even to invalidate the region.366 367* 'new' is poorly modeled due to some nasty CFG/design issues. This is tracked368 in PR12014. 'delete' is not modeled at all.369 370* Arrays of objects are modeled very poorly right now. ExprEngine currently371 only simulates the first constructor and first destructor. Because of this,372 ExprEngine does not inline any constructors or destructors for arrays.373 374 375CallEvent376^^^^^^^^^377 378A CallEvent represents a specific call to a function, method, or other body of379code. It is path-sensitive, containing both the current state (ProgramStateRef)380and stack space (LocationContext), and provides uniform access to the argument381values and return type of a call, no matter how the call is written in the382source or what sort of code body is being invoked.383 384 NOTE: For those familiar with Cocoa, CallEvent is roughly equivalent to385 NSInvocation.386 387CallEvent should be used whenever there is logic dealing with function calls388that does not care how the call occurred.389 390Examples include checking that arguments satisfy preconditions (such as391__attribute__((nonnull))), and attempting to inline a call.392 393CallEvents are reference-counted objects managed by a CallEventManager. While394there is no inherent issue with persisting them (say, in a ProgramState's GDM),395they are intended for short-lived use, and can be recreated from CFGElements or396non-top-level StackFrameContexts fairly easily.397