summaryrefslogtreecommitdiffstats
path: root/clang/lib/StaticAnalyzer/Core
Commit message (Collapse)AuthorAgeFilesLines
...
* Revert "[analyzer] Do part of the work to find shortest bug paths up front."Jordan Rose2013-03-191-115/+42
| | | | | | | | | | | | | The whole reason we were doing a BFS in the first place is because an ExplodedGraph can have cycles. Unfortunately, my removeErrorNode "update" doesn't work at all if there are cycles. I'd still like to be able to avoid doing the BFS every time, but I'll come back to it later. This reverts r177353 / 481fa5071c203bc8ba4f88d929780f8d0f8837ba. llvm-svn: 177448
* [analyzer] Do part of the work to find shortest bug paths up front.Jordan Rose2013-03-181-42/+115
| | | | | | | | | | | | | | Splitting the graph trimming and the path-finding (r177216) already recovered quite a bit of performance lost to increased suppression. We can still do better by also performing the reverse BFS up front (needed for shortest-path-finding) and only walking the shortest path for each report. This does mean we have to walk back up the path and invalidate all the BFS numbers if the report turns out to be invalid, but it's probably still faster than redoing the full BFS every time. More performance work for <rdar://problem/13433687> llvm-svn: 177353
* [analyzer] Replace uses of assume() with isNull() in BR visitors.Jordan Rose2013-03-181-15/+18
| | | | | | | | Also, replace a std::string with a SmallString. No functionality change. llvm-svn: 177352
* [analyzer] Model trivial copy/move assignment operators with a bind as well.Jordan Rose2013-03-162-9/+48
| | | | | | | | | | | | r175234 allowed the analyzer to model trivial copy/move constructors as an aggregate bind. This commit extends that to trivial assignment operators as well. Like the last commit, one of the motivating factors here is not warning when the right-hand object is partially-initialized, which can have legitimate uses. <rdar://problem/13405162> llvm-svn: 177220
* [analyzer] Separate graph trimming from creating the single-path graph.Jordan Rose2013-03-161-58/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | When we generate a path diagnostic for a bug report, we have to take the full ExplodedGraph and limit it down to a single path. We do this in two steps: "trimming", which limits the graph to all the paths that lead to this particular bug, and "creating the report graph", which finds the shortest path in the trimmed path to any error node. With BugReporterVisitor false positive suppression, this becomes more expensive: it's possible for some paths through the trimmed graph to be invalid (i.e. likely false positives) but others to be valid. Therefore we have to run the visitors over each path in the graph until we find one that is valid, or until we've ruled them all out. This can become quite expensive. This commit separates out graph trimming from creating the report graph, performing the first only once per bug equivalence class and the second once per bug report. It also cleans up that portion of the code by introducing some wrapper classes. This seems to recover most of the performance regression described in my last commit. <rdar://problem/13433687> llvm-svn: 177216
* [analyzer] Eliminate InterExplodedGraphMap class and NodeBackMap typedef.Jordan Rose2013-03-163-69/+31
| | | | | | | | | | | | | | | ...in favor of this typedef: typedef llvm::DenseMap<const ExplodedNode *, const ExplodedNode *> InterExplodedGraphMap; Use this everywhere the previous class and typedef were used. Took the opportunity to ArrayRef-ize ExplodedGraph::trim while I'm at it. No functionality change. llvm-svn: 177215
* [analyzer] Don't repeat a bug equivalence class if every report is invalid.Jordan Rose2013-03-161-3/+13
| | | | | | | | I removed this check in the recursion->iteration commit, but forgot that generatePathDiagnostic may be called multiple times if there are multiple PathDiagnosticConsumers. llvm-svn: 177214
* [analyzer] Use isLiveRegion to determine when SymbolRegionValue is dead.Anna Zaks2013-03-151-3/+1
| | | | | | | | | | Fixes a FIXME, improves dead symbol collection, suppresses a false positive, which resulted from reusing the same symbol twice for simulation of 2 calls to the same function. Fixing this lead to 2 possible false negatives in CString checker. Since the checker is still alpha and the solution will not require revert of this commit, move the tests to a FIXME section. llvm-svn: 177206
* [analyzer] BugReporterVisitors: handle the case where a ternary operator is ↵Anna Zaks2013-03-151-8/+11
| | | | | | wrapped in a cast. llvm-svn: 177205
* [analyzer] Address Jordan’s review of r177138 (a micro optimization)Anna Zaks2013-03-151-5/+8
| | | | llvm-svn: 177204
* [analyzer] Make GRBugReporter::generatePathDiagnostic iterative, not recursive.Jordan Rose2013-03-151-112/+103
| | | | | | | | | | | | | | | | | | The previous generatePathDiagnostic() was intended to be tail-recursive, restarting and trying again if a report was marked invalid. However: (1) this leaked all the cloned visitors, which weren't being deleted, and (2) this wasn't actually tail-recursive because some local variables had non-trivial destructors. This was causing us to overflow the stack on inputs with large numbers of reports in the same equivalence class, such as sqlite3.c. Being iterative at least prevents us from blowing out the stack, but doesn't solve the performance issue: suppressing thousands (yes, thousands) of paths in the same equivalence class is expensive. I'm looking into that now. <rdar://problem/13423498> llvm-svn: 177189
* [analyzer] Collect stats on the max # of bug reports in an equivalence class.Jordan Rose2013-03-151-0/+15
| | | | | | | | | | | | | | We discovered that sqlite3.c currently has 2600 reports in a single equivalence class; it would be good to know if this is a recent development or what. (For the curious, the different reports in an equivalence class represent the same bug found along different paths. When we're suppressing false positives, we need to go through /every/ path to make sure there isn't a valid path to a bug. This is a flaw in our after-the-fact suppression, made worse by the fact that that function isn't particularly optimized.) llvm-svn: 177188
* [analyzer] Include opcode in dumping a SymSymExpr.Jordan Rose2013-03-151-34/+15
| | | | | | For debugging use only; no functionality change. llvm-svn: 177187
* [analyzer] Look through ExprWhenCleanups when trying to track a NULL.Jordan Rose2013-03-151-1/+2
| | | | | | Silences a few false positives in LLVM. llvm-svn: 177186
* [analyzer] Refactor checks in IDC visitor for consistency and speedAnna Zaks2013-03-151-6/+6
| | | | llvm-svn: 177138
* [analyzer] Teach trackNullOrUndef to look through ternary operatorsAnna Zaks2013-03-151-3/+14
| | | | | | Allows the suppression visitors trigger more often. llvm-svn: 177137
* [analyzer] Change the way in which IDC Visitor decides to kick in and make ↵Anna Zaks2013-03-141-24/+14
| | | | | | | | | | | | | sure it attaches in the given edge case In the test case below, the value V is not constrained to 0 in ErrorNode but it is in node N. So we used to fail to register the Suppression visitor. We also need to change the way we determine that the Visitor should kick in because the node N belongs to the ExplodedGraph and might not be on the BugReporter path that the visitor sees. Instead of trying to match the node, turn on the visitor when we see the last node in which the symbol is ‘0’. llvm-svn: 177121
* [analyzer] BugReporter - more precise tracking of C++ referencesAnna Zaks2013-03-131-23/+53
| | | | | | | | | | | | | | | | When BugReporter tracks C++ references involved in a null pointer violation, we want to differentiate between a null reference and a reference to a null pointer. In the first case, we want to track the region for the reference location; in the second, we want to track the null pointer. In addition, the core creates CXXTempObjectRegion to represent the location of the C++ reference, so teach FindLastStoreBRVisitor about it. This helps null pointer suppression to kick in. (Patch by Anna and Jordan.) llvm-svn: 176969
* Remove stray space.Ted Kremenek2013-03-131-1/+0
| | | | llvm-svn: 176966
* [analyzer] Handle Objc Fast enumeration for "loop is executed 0 times".Ted Kremenek2013-03-131-0/+7
| | | | | | Fixes <rdar://problem/12322528> llvm-svn: 176965
* [analyzer] Look for calls along with lvalue nodes in trackNullOrUndefValue.Jordan Rose2013-03-111-9/+10
| | | | | | | | | | | | | | | | | | r176737 fixed bugreporter::trackNullOrUndefValue to find nodes for an lvalue even if the rvalue node had already been collected. This commit extends that to call statement nodes as well, so that if a call is contained within implicit casts we can still track the return value. No test case because node reclamation is extremely finicky (dependent on how the AST and CFG are built, and then on our current reclamation rules, and /then/ on how many nodes were generated by the analyzer core and the current set of checkers). I consider this a low-risk change, though, and it will only happen in cases of reclamation when the rvalue node isn't available. <rdar://problem/13340764> llvm-svn: 176829
* [analyzer] Make Suppress IDC checker aware that it might not start from the ↵Anna Zaks2013-03-091-12/+30
| | | | | | | | | | | | | | | | | | | | same node it was registered at The visitor used to assume that the value it’s tracking is null in the first node it examines. This is not true. If we are registering the Suppress Inlined Defensive checks visitor while traversing in another visitor (such as FindlastStoreVisitor). When we restart with the IDC visitor, the invariance of the visitor does not hold since the symbol we are tracking no longer exists at that point. I had to pass the ErrorNode when creating the IDC visitor, because, in some cases, node N is neither the error node nor will be visible along the path (we had not finalized the path at that point and are dealing with ExplodedGraph.) We should revisit the other visitors which might not be aware that they might get nodes, which are later in path than the trigger point. This suppresses a number of inline defensive checks in JavaScriptCore. llvm-svn: 176756
* [analyzer] Look for lvalue nodes when tracking a null pointer.Jordan Rose2013-03-081-81/+76
| | | | | | | | | | | | | | | | | | r176010 introduced the notion of "interesting" lvalue expressions, whose nodes are guaranteed never to be reclaimed by the ExplodedGraph. This was used in bugreporter::trackNullOrUndefValue to find the region that contains the null or undef value being tracked. However, the /rvalue/ nodes (i.e. the loads from these lvalues that produce a null or undef value) /are/ still being reclaimed, and if we couldn't find the node for the rvalue, we just give up. This patch changes that so that we look for the node for either the rvalue or the lvalue -- preferring the former, since it lets us fall back to value-only tracking in cases where we can't get a region, but allowing the latter as well. <rdar://problem/13342842> llvm-svn: 176737
* [analyzer] Don't rely on finding the correct return statement for suppression.Jordan Rose2013-03-081-58/+86
| | | | | | | | | | | | | | | | | | Previously, ReturnVisitor waited to suppress a null return path until it had found the inlined "return" statement. Now, it checks up front whether the return value was NULL, and suppresses the warning right away if so. We still have to wait until generating the path notes to invalidate the bug report, or counter-suppression will never be triggered. (Counter-suppression happens while generating path notes, but the generation won't happen for reports already marked invalid.) This isn't actually an issue today because we never reclaim nodes for top-level statements (like return statements), but it could be an issue some day in the future. (But, no expected behavioral change and no new test case.) llvm-svn: 176736
* [analyzer] Clean up a few doc comments for ProgramState and CallEvent.Jordan Rose2013-03-071-1/+0
| | | | | | No functionality change. llvm-svn: 176600
* [analyzer] IDC: Add config option; perform the idc check on first “null ↵Anna Zaks2013-03-062-2/+13
| | | | | | | | | | node” rather than last “non-null”. The second modification does not lead to any visible result, but, theoretically, is what we should have been looking at to begin with since we are checking if the node was assumed to be null in an inlined function. llvm-svn: 176576
* Silence a number of static analyzer warnings with assertions and such.Jordan Rose2013-03-051-0/+2
| | | | | | No functionality change. llvm-svn: 176469
* [analyzer] Simple inline defensive checks suppressionAnna Zaks2013-03-022-1/+64
| | | | | | | | | | | | | | | | | | | | | Inlining brought a few "null pointer use" false positives, which occur because the callee defensively checks if a pointer is NULL, whereas the caller knows that the pointer cannot be NULL in the context of the given call. This is a first attempt to silence these warnings by tracking the symbolic value along the execution path in the BugReporter. The new visitor finds the node in which the symbol was first constrained to NULL. If the node belongs to a function on the active stack, the warning is reported, otherwise, it is suppressed. There are several areas for follow up work, for example: - How do we differentiate the cases where the first check is followed by another one, which does happen on the active stack? Also, this only silences a fraction of null pointer use warnings. For example, it does not do anything for the cases where NULL was assigned inside a callee. llvm-svn: 176402
* [analyzer] Special-case bitfields when finding sub-region bindings.Jordan Rose2013-03-012-3/+8
| | | | | | | | | | | | | | | Previously we were assuming that we'd never ask for the sub-region bindings of a bitfield, since a bitfield cannot have subregions. However, unification of code paths has made that assumption invalid. While we could take advantage of this by just checking for the single possible binding, it's probably better to do the right thing, so that if/when we someday support unions we'll do the right thing there, too. This fixes a handful of false positives in analyzing LLVM. <rdar://problem/13325522> llvm-svn: 176388
* [analyzer] Suppress paths involving a reference whose rvalue is null.Jordan Rose2013-03-011-13/+33
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Most map types have an operator[] that inserts a new element if the key isn't found, then returns a reference to the value slot so that you can assign into it. However, if the value type is a pointer, it will be initialized to null. This is usually no problem. However, if the user /knows/ the map contains a value for a particular key, they may just use it immediately: // From ClangSACheckersEmitter.cpp recordGroupMap[group]->Checkers In this case the analyzer reports a null dereference on the path where the key is not in the map, even though the user knows that path is impossible here. They could silence the warning by adding an assertion, but that means splitting up the expression and introducing a local variable. (Note that the analyzer has no way of knowing that recordGroupMap[group] will return the same reference if called twice in a row!) We already have logic that says a null dereference has a high chance of being a false positive if the null came from an inlined function. This patch simply extends that to references whose rvalues are null as well, silencing several false positives in LLVM. <rdar://problem/13239854> llvm-svn: 176371
* [analyzer] RegionStore: collectSubRegionKeys -> collectSubRegionBindingsJordan Rose2013-02-281-37/+46
| | | | | | | | | By returning the (key, value) binding pairs, we save lookups afterwards. This also enables further work later on. No functionality change. llvm-svn: 176230
* [analyzer] Teach FindLastStoreBRVisitor to understand stores of the same value.Jordan Rose2013-02-271-4/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | Consider this case: int *p = 0; p = getPointerThatMayBeNull(); *p = 1; If we inline 'getPointerThatMayBeNull', we might know that the value of 'p' is NULL, and thus emit a null pointer dereference report. However, we usually want to suppress such warnings as error paths, and we do so by using FindLastStoreBRVisitor to see where the NULL came from. In this case, though, because 'p' was NULL both before and after the assignment, the visitor would decide that the "last store" was the initialization, not the re-assignment. This commit changes FindLastStoreBRVisitor to consider all PostStore nodes that assign to this region. This still won't catches changes made directly by checkers if they re-assign the same value, but it does handle the common case in user-written code and will trigger ReturnVisitor's suppression machinery as expected. <rdar://problem/13299738> llvm-svn: 176201
* [analyzer] Turn on C++ constructor inlining by default.Jordan Rose2013-02-271-1/+1
| | | | | | | | | | This enables constructor inlining for types with non-trivial destructors. The plan is to enable destructor inlining within the next month, but that needs further verification. <rdar://problem/12295329> llvm-svn: 176200
* [analyzer] Add stop-gap patch to prevent assertion failure when analyzing ↵Ted Kremenek2013-02-271-1/+1
| | | | | | | | | | LLVM codebase. This potentially reduces a performance optimization of throwing away PreStmtPurgeDeadSymbols nodes. I'll investigate the performance impact soon and see if we need something better. llvm-svn: 176149
* [analyzer] If a struct has a partial lazy binding, its fields aren't Undef.Jordan Rose2013-02-272-16/+46
| | | | | | | | | | | | | | | | | | | | | | This is essentially the same problem as r174031: a lazy binding for the first field of a struct may stomp on an existing default binding for the entire struct. Because of the way RegionStore is set up, we can't help but lose the top-level binding, but then we need to make sure that accessing one of the other fields doesn't come back as Undefined. In this case, RegionStore is now correctly detecting that the lazy binding we have isn't the right type, but then failing to follow through on the implications of that: we don't know anything about the other fields in the aggregate. This fix adds a test when searching for other kinds of default values to see if there's a lazy binding we rejected, and if so returns a symbolic value instead of Undefined. The long-term fix for this is probably a new Store model; see <rdar://problem/12701038>. Fixes <rdar://problem/13292559>. llvm-svn: 176144
* [analyzer] Use 'MemRegion::printPretty()' instead of assuming the region is ↵Ted Kremenek2013-02-261-1/+3
| | | | | | | | | | | | a VarRegion. Fixes PR15358 and <rdar://problem/13295437>. Along the way, shorten path diagnostics that say "Variable 'x'" to just be "'x'". By the context, it is obvious that we have a variable, and so this just consumes text space. llvm-svn: 176115
* [analyzer] Don't look through casts when creating pointer temporaries.Jordan Rose2013-02-262-12/+20
| | | | | | | | | | | | | | | Normally, we need to look through derived-to-base casts when creating temporary object regions (added in r175854). However, if the temporary is a pointer (rather than a struct/class instance), we need to /preserve/ the base casts that have been applied. This also ensures that we really do create a new temporary region when we need to: MaterializeTemporaryExpr and lvalue CXXDefaultArgExprs. Fixes PR15342, although the test case doesn't include the crash because I couldn't isolate it. llvm-svn: 176069
* [analyzer] Recover all PreStmtPurgeDeadSymbols nodes with a single successor ↵Ted Kremenek2013-02-251-2/+21
| | | | | | | | | | | | | | or predecessor. These nodes are never consulted by any analyzer client code, so they are used only for machinery for removing dead bindings. Once successor nodes are generated they can be safely removed. This greatly reduces the amount of nodes that are generated in some case, lowering the memory regression when analyzing Sema.cpp introduced by r176010 from 14% to 2%. llvm-svn: 176050
* [analyzer] Address Jordan's code review of r175857.Anna Zaks2013-02-251-20/+15
| | | | llvm-svn: 176043
* [analyzer] Handle reference parameters with default values.Jordan Rose2013-02-252-3/+6
| | | | | | | | | | | | r175026 added support for default values, but didn't take reference parameters into account, which expect the default argument to be an lvalue. Use createTemporaryRegionIfNeeded if we can evaluate the default expr as an rvalue but the expected result is an lvalue. Fixes the most recent report of PR12915. The original report predates default argument support, so that can't be it. llvm-svn: 176042
* [analyzer] Base regions may be invalid when layered on symbolic regions.Jordan Rose2013-02-251-0/+32
| | | | | | | | | | | | | | | | While RegionStore checks to make sure casts on TypedValueRegions are valid, it does not do the same for SymbolicRegions, which do not have perfect type info anyway. Additionally, MemRegion::getAsOffset does not take a ProgramState, so it can't use dynamic type info to determine a better type for the regions. (This could also be dangerous if the type of a super-region changes!) Account for this by checking that a base object region is valid on top of a symbolic region, and falling back to "symbolic offset" mode if not. Fixes PR15345. llvm-svn: 176034
* [analyzer] Relax assumption in FindLastStoreBRVisitor that the thing we are ↵Ted Kremenek2013-02-251-31/+34
| | | | | | | | | | | | looking for is always a VarRegion. This was triggering assertion failures when analyzing the LLVM codebase. This is fallout from r175988. I've got delta chewing away on a test case, but I wanted the fix to go in now. llvm-svn: 176011
* [analyzer] add the notion of an "interesting" lvalue expression for ↵Ted Kremenek2013-02-252-4/+16
| | | | | | | | | | ExplodedNode pruning. r175988 modified the ExplodedGraph trimming algorithm to retain all nodes for "lvalue" expressions. This patch refines that notion to only "interesting" expressions that would be used for diagnostics. llvm-svn: 176010
* [analyzer] tracking stores/constraints now works for ObjC ivars or struct ↵Ted Kremenek2013-02-243-19/+70
| | | | | | | | | | | | | | | | | | | | | | | fields. This required more changes than I originally expected: - ObjCIvarRegion implements "canPrintPretty" et al - DereferenceChecker indicates the null pointer source is an ivar - bugreporter::trackNullOrUndefValue() uses an alternate algorithm to compute the location region to track by scouring the ExplodedGraph. This allows us to get the actual MemRegion for variables, ivars, fields, etc. We only hand construct a VarRegion for C++ references. - ExplodedGraph no longer drops nodes for expressions that are marked 'lvalue'. This is to facilitate the logic in the previous bullet. This may lead to a slight increase in size in the ExplodedGraph, which I have not measured, but it is likely not to be a big deal. I have validated each of the changed plist output. Fixes <rdar://problem/12114812> llvm-svn: 175988
* Add "KnownSVal" to represent SVals that cannot be UnknownSVal.Ted Kremenek2013-02-241-13/+11
| | | | | | | This provides a few sundry cleanups, and allows us to provide a compile-time check for a case that was a runtime assertion. llvm-svn: 175987
* Remove the CFGElement "Invalid" state.David Blaikie2013-02-237-20/+17
| | | | | | | | | | | | | Use Optional<CFG*> where invalid states were needed previously. In the one case where that's not possible (beginAutomaticObjDtorsInsert) just use a dummy CFGAutomaticObjDtor. Thanks for the help from Jordan Rose & discussion/feedback from Ted Kremenek and Doug Gregor. Post commit code review feedback on r175796 by Ted Kremenek. llvm-svn: 175938
* [analyzer] Don't canonicalize the RecordDecl used in CXXBaseObjectRegion.Jordan Rose2013-02-221-2/+2
| | | | | | | | | | | This Decl shouldn't be the canonical Decl; it should be the Decl used by the CXXBaseSpecifier in the subclass. Unfortunately, that means continuing to throw getCanonicalDecl() on all comparisons. This fixes MemRegion::getAsOffset's use of ASTRecordLayout when redeclarations are involved. llvm-svn: 175913
* [analyzer] Implement "Loop executed 0 times" diagnostic correctly.Ted Kremenek2013-02-221-20/+62
| | | | | | Fixes <rdar://problem/13236549> llvm-svn: 175863
* [analyzer] Place all inlining policy checks into one palceAnna Zaks2013-02-221-175/+179
| | | | | | | | | | | | | Previously, we had the decisions about inlining spread out over multiple functions. In addition to the refactor, this commit ensures that we will always inline BodyFarm functions as long as the Decl is available. This fixes false positives due to those functions not being inlined when no or minimal inlining is enabled such (as shallow mode). llvm-svn: 175857
* [analyzer] Make sure a materialized temporary matches its bindings.Jordan Rose2013-02-222-45/+38
| | | | | | | | | | | | | | | | | This is a follow-up to r175830, which made sure a temporary object region created for, say, a struct rvalue matched up with the initial bindings being stored into it. This does the same for the case in which the AST actually tells us that we need to create a temporary via a MaterializeObjectExpr. I've unified the two code paths and moved a static helper function onto ExprEngine. This also caused a bit of test churn, causing us to go back to describing temporary regions without a 'const' qualifier. This seems acceptable; it's our behavior from a few months ago. <rdar://problem/13265460> (part 2) llvm-svn: 175854
OpenPOWER on IntegriCloud