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