1 Inlining 2 ======== 3 4 There are several options that control which calls the analyzer will consider for 5 inlining. 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 29 Currently, -analyzer-ipa=dynamic-bifurcate is the default mode. 30 31 While -analyzer-ipa determines in general how aggressively the analyzer will try to 32 inline functions, several additional options control which types of functions can 33 inlined, in an all-or-nothing way. These options use the analyzer's configuration 34 table, so they are all specified as follows: 35 36 -analyzer-config OPTION=VALUE 37 38 ### c++-inlining ### 39 40 This option controls which C++ member functions may be inlined. 41 42 -analyzer-config c++-inlining=[none | methods | constructors | destructors] 43 44 Each of these modes implies that all the previous member function kinds will be 45 inlined as well; it doesn't make sense to inline destructors without inlining 46 constructors, for example. 47 48 The default c++-inlining mode is 'methods', meaning only regular member 49 functions and overloaded operators will be inlined. Note that no C++ member 50 functions will be inlined under -analyzer-ipa=none or 51 -analyzer-ipa=basic-inlining. 52 53 ### c++-template-inlining ### 54 55 This option controls whether C++ templated functions may be inlined. 56 57 -analyzer-config c++-template-inlining=[true | false] 58 59 Currently, template functions are considered for inlining by default. 60 61 The motivation behind this option is that very generic code can be a source 62 of false positives, either by considering paths that the caller considers 63 impossible (by some unstated precondition), or by inlining some but not all 64 of a deep implementation of a function. 65 66 ### c++-stdlib-inlining ### 67 68 This option controls whether functions from the C++ standard library, including 69 methods of the container classes in the Standard Template Library, should be 70 considered for inlining. 71 72 -analyzer-config c++-template-inlining=[true | false] 73 74 Currently, C++ standard library functions are NOT considered for inlining by default. 75 76 The standard library functions and the STL in particular are used ubiquitously 77 enough that our tolerance for false positives is even lower here. A false 78 positive due to poor modeling of the STL leads to a poor user experience, since 79 most users would not be comfortable adding assertions to system headers in order 80 to silence analyzer warnings. 81 82 83 Basics of Implementation 84 ----------------------- 85 86 The low-level mechanism of inlining a function is handled in 87 ExprEngine::inlineCall and ExprEngine::processCallExit. 88 89 If the conditions are right for inlining, a CallEnter node is created and added 90 to the analysis work list. The CallEnter node marks the change to a new 91 LocationContext representing the called function, and its state includes the 92 contents of the new stack frame. When the CallEnter node is actually processed, 93 its single successor will be a edge to the first CFG block in the function. 94 95 Exiting an inlined function is a bit more work, fortunately broken up into 96 reasonable steps: 97 98 1. The CoreEngine realizes we're at the end of an inlined call and generates a 99 CallExitBegin node. 100 101 2. 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 106 3. Dead symbols and bindings are cleaned out from the state, including any local 107 bindings. 108 109 4. A CallExitEnd node is generated, which marks the transition back to the 110 caller's LocationContext. 111 112 5. 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 115 Retry Without Inlining 116 ---------------------- 117 118 In some cases, we would like to retry analysis without inlining a particular 119 call. 120 121 Currently, we use this technique to recover coverage in case we stop 122 analyzing a path due to exceeding the maximum block count inside an inlined 123 function. 124 125 When this situation is detected, we walk up the path to find the first node 126 before inlining was started and enqueue it on the WorkList with a special 127 ReplayWithoutInlining bit added to it (ExprEngine::replayWithoutInlining). The 128 path is then re-analyzed from that point without inlining that particular call. 129 130 Deciding When to Inline 131 ----------------------- 132 133 In general, the analyzer attempts to inline as much as possible, since it 134 provides a better summary of what actually happens in the program. There are 135 some 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 173 Dynamic Calls and Devirtualization 174 ---------------------------------- 175 176 "Dynamic" calls are those that are resolved at runtime, such as C++ virtual 177 method calls and Objective-C message sends. Due to the path-sensitive nature of 178 the analysis, the analyzer may be able to reason about the dynamic type of the 179 object whose method is being called and thus "devirtualize" the call. 180 181 This path-sensitive devirtualization occurs when the analyzer can determine what 182 method would actually be called at runtime. This is possible when the type 183 information is constrained enough for a simulated C++/Objective-C object that 184 the analyzer can make such a decision. 185 186 == DynamicTypeInfo == 187 188 As the analyzer analyzes a path, it may accrue information to refine the 189 knowledge about the type of an object. This can then be used to make better 190 decisions about the target method of a call. 191 192 Such type information is tracked as DynamicTypeInfo. This is path-sensitive 193 data that is stored in ProgramState, which defines a mapping from MemRegions to 194 an (optional) DynamicTypeInfo. 195 196 If no DynamicTypeInfo has been explicitly set for a MemRegion, it will be lazily 197 inferred from the region's type or associated symbol. Information from symbolic 198 regions 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 203 The DynamicTypePropagation checker gathers and propagates DynamicTypeInfo, 204 updating it as information is observed along a path that can refine that type 205 information 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 215 The basis of devirtualization is CallEvent's getRuntimeDefinition() method, 216 which returns a RuntimeDefinition object. When asked to provide a definition, 217 the CallEvents for dynamic calls will use the DynamicTypeInfo in their 218 ProgramState to attempt to devirtualize the call. In the case of no dynamic 219 dispatch, or perfectly constrained devirtualization, the resulting 220 RuntimeDefinition contains a Decl corresponding to the definition of the called 221 function, and RuntimeDefinition::mayHaveOtherDefinitions will return FALSE. 222 223 In the case of dynamic dispatch where our information is not perfect, CallEvent 224 can make a guess, but RuntimeDefinition::mayHaveOtherDefinitions will return 225 TRUE. The RuntimeDefinition object will then also include a MemRegion 226 corresponding to the object being called (i.e., the "receiver" in Objective-C 227 parlance), which ExprEngine uses to decide whether or not the call should be 228 inlined. 229 230 == Inlining Dynamic Calls == 231 232 The -analyzer-ipa option has five different modes: none, basic-inlining, 233 inlining, dynamic, and dynamic-bifurcate. Under -analyzer-ipa=dynamic, all 234 dynamic calls are inlined, whether we are certain or not that this will actually 235 be the definition used at runtime. Under -analyzer-ipa=inlining, only 236 "near-perfect" devirtualized calls are inlined*, and other dynamic calls are 237 evaluated 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 244 The last option, -analyzer-ipa=dynamic-bifurcate, behaves similarly to 245 "dynamic", but performs a conservative invalidation in the general virtual case 246 in *addition* to inlining. The details of this are discussed below. 247 248 As stated above, -analyzer-ipa=basic-inlining does not inline any C++ member 249 functions or Objective-C method calls, even if they are non-virtual or can be 250 safely devirtualized. 251 252 253 Bifurcation 254 ----------- 255 256 ExprEngine::BifurcateCall implements the -analyzer-ipa=dynamic-bifurcate 257 mode. 258 259 When a call is made on an object with imprecise dynamic type information 260 (RuntimeDefinition::mayHaveOtherDefinitions() evaluates to TRUE), ExprEngine 261 bifurcates the path and marks the object's region (retrieved from the 262 RuntimeDefinition object) with a path-sensitive "mode" in the ProgramState. 263 264 Currently, 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 280 Going forward along the symbolic execution path, ExprEngine consults the mode 281 of the receiver's MemRegion to make decisions on whether the calls should be 282 inlined or not, which ensures that there is at most one split per region. 283 284 At a high level, "bifurcation mode" allows for increased semantic coverage in 285 cases where the parent method contains code which is only executed when the 286 class is subclassed. The disadvantages of this mode are a (considerable?) 287 performance hit and the possibility of false positives on the path where the 288 conservative mode is used. 289 290 Objective-C Message Heuristics 291 ------------------------------ 292 293 ExprEngine relies on a set of heuristics to partition the set of Objective-C 294 method calls into those that require bifurcation and those that do not. Below 295 are 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 311 C++ Caveats 312 -------------------- 313 314 C++11 [class.cdtor]p4 describes how the vtable of an object is modified as it is 315 being constructed or destructed; that is, the type of the object depends on 316 which base constructors have been completed. This is tracked using 317 DynamicTypeInfo in the DynamicTypePropagation checker. 318 319 There 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 334 CallEvent 335 ========= 336 337 A CallEvent represents a specific call to a function, method, or other body of 338 code. It is path-sensitive, containing both the current state (ProgramStateRef) 339 and stack space (LocationContext), and provides uniform access to the argument 340 values and return type of a call, no matter how the call is written in the 341 source 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 346 CallEvent should be used whenever there is logic dealing with function calls 347 that does not care how the call occurred. 348 349 Examples include checking that arguments satisfy preconditions (such as 350 __attribute__((nonnull))), and attempting to inline a call. 351 352 CallEvents are reference-counted objects managed by a CallEventManager. While 353 there is no inherent issue with persisting them (say, in a ProgramState's GDM), 354 they are intended for short-lived use, and can be recreated from CFGElements or 355 non-top-level StackFrameContexts fairly easily. 356
