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