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