summaryrefslogtreecommitdiffstats
path: root/clang/lib/StaticAnalyzer
Commit message (Collapse)AuthorAgeFilesLines
...
* [analyzer] Make sure IDC works for ‘NSContainer value/key is nil’ checks.Anna Zaks2013-03-262-14/+23
| | | | | | | | | Register the nil tracking visitors with the region and refactor trackNullOrUndefValue a bit. Also adds the cast and paren stripping before checking if the value is an OpaqueValueExpr or ExprWithCleanups. llvm-svn: 178093
* [analyzer] Change inlining policy to inline small functions when reanalyzing ↵Anna Zaks2013-03-262-15/+18
| | | | | | | | ObjC methods as top level. This allows us to better reason about(inline) small wrapper functions. llvm-svn: 178063
* [analyzer] micro optimization as per Jordan’s feedback on r177905.Anna Zaks2013-03-261-1/+1
| | | | llvm-svn: 178062
* [analyzer] Set concrete offset bindings to UnknownVal when processing ↵Anna Zaks2013-03-251-2/+10
| | | | | | | | | | symbolic offset binding, even if no bindings are present. This addresses an undefined value false positive from concreteOffsetBindingIsInvalidatedBySymbolicOffsetAssignment. Fixes PR14877; radar://12991168. llvm-svn: 177905
* [analyzer] Adds cplusplus.NewDelete checker that check for memory leaks, ↵Anton Yartsev2013-03-252-27/+144
| | | | | | double free, and use-after-free problems of memory managed by new/delete. llvm-svn: 177849
* [analyzer] Teach ConstraintManager to ignore NonLoc <> NonLoc comparisons.Jordan Rose2013-03-241-2/+7
| | | | | | | | | These aren't generated by default, but they are needed when either side of the comparison is tainted. Should fix our internal buildbot. llvm-svn: 177846
* [analyzer] Teach constraint managers about unsigned comparisons.Jordan Rose2013-03-233-20/+35
| | | | | | | | | | | In C, comparisons between signed and unsigned numbers are always done in unsigned-space. Thus, we should know that "i >= 0U" is always true, even if 'i' is signed. Similarly, "u >= 0" is also always true, even though '0' is signed. Part of <rdar://problem/13239003> (false positives related to std::vector) llvm-svn: 177806
* [analyzer] Loc-Loc operations (subtraction or comparison) produce a NonLoc.Jordan Rose2013-03-232-8/+8
| | | | | | | | | | For two concrete locations, we were producing another concrete location and then casting it to an integer. We should just create a nonloc::ConcreteInt to begin with. No functionality change. llvm-svn: 177805
* [analyzer] Also transform "a < b" to "(b - a) > 0" in the constraint manager.Jordan Rose2013-03-231-15/+17
| | | | | | | | | | | | We can support the full range of comparison operations between two locations by canonicalizing them as subtraction, as in the previous commit. This won't work (well) if either location includes an offset, or (again) if the comparisons are not consistent about which region comes first. <rdar://problem/13239003> llvm-svn: 177803
* Add reverseComparisonOp and negateComparisonOp to BinaryOperator.Jordan Rose2013-03-232-46/+5
| | | | | | ...and adopt them in the analyzer. llvm-svn: 177802
* [analyzer] Translate "a != b" to "(b - a) != 0" in the constraint manager.Jordan Rose2013-03-233-23/+44
| | | | | | | | | | | | | | | | | | | | | | | Canonicalizing these two forms allows us to better model containers like std::vector, which use "m_start != m_finish" to implement empty() but "m_finish - m_start" to implement size(). The analyzer should have a consistent interpretation of these two symbolic expressions, even though it's not properly reasoning about either one yet. The other unfortunate thing is that while the size() expression will only ever be written "m_finish - m_start", the comparison may be written "m_finish == m_start" or "m_start == m_finish". Right now the analyzer does not attempt to canonicalize those two expressions, since it doesn't know which length expression to pick. Doing this correctly will probably require implementing unary minus as a new SymExpr kind (<rdar://problem/12351075>). For now, the analyzer inverts the order of arguments in the comparison to build the subtraction, on the assumption that "begin() != end()" is written more often than "end() != begin()". This is purely speculation. <rdar://problem/13239003> llvm-svn: 177801
* [analyzer] Use SymExprs to represent '<loc> - <loc>' and '<loc> == <loc>'.Jordan Rose2013-03-231-17/+22
| | | | | | | | | | We just treat this as opaque symbols, but even that allows us to handle simple cases where the same condition is tested twice. This is very common in the STL, which means that any project using the STL gets spurious errors. Part of <rdar://problem/13239003>. llvm-svn: 177800
* [analyzer] Warn when a nil key or value are passed to NSMutableDictionary ↵Anna Zaks2013-03-231-16/+62
| | | | | | and ensure it works with subscripting. llvm-svn: 177789
* [analyzer] Correct the stale comment.Anna Zaks2013-03-231-3/+3
| | | | llvm-svn: 177788
* Revert "[analyzer] Break cycles (optionally) when trimming an ExplodedGraph."Jordan Rose2013-03-222-19/+3
| | | | | | | | | | | | | | The algorithm used here was ridiculously slow when a potential back-edge pointed to a node that already had a lot of successors. The previous commit makes this feature unnecessary anyway. This reverts r177468 / f4cf6b10f863b9bc716a09b2b2a8c497dcc6aa9b. Conflicts: lib/StaticAnalyzer/Core/BugReporter.cpp llvm-svn: 177765
* [analyzer] Use a forward BFS instead of a reverse BFS to find shortest paths.Jordan Rose2013-03-221-150/+93
| | | | | | | | | | | | | | | | | | | | | | | | | For a given bug equivalence class, we'd like to emit the report with the shortest path. So far to do this we've been trimming the ExplodedGraph to only contain relevant nodes, then doing a reverse BFS (starting at all the error nodes) to find the shortest paths from the root. However, this is fairly expensive when we are suppressing many bug reports in the same equivalence class. r177468-9 tried to solve this problem by breaking cycles during graph trimming, then updating the BFS priorities after each suppressed report instead of recomputing the whole thing. However, breaking cycles is not a cheap operation because an analysis graph minus cycles is still a DAG, not a tree. This fix changes the algorithm to do a single forward BFS (starting from the root) and to use that to choose the report with the shortest path by looking at the error nodes with the lowest BFS priorities. This was Anna's idea, and has the added advantage of requiring no update step: we can just pick the error node with the next lowest priority to produce the next bug report. <rdar://problem/13474689> llvm-svn: 177764
* [analyzer] Fix ExprEngine::ViewGraph to handle C++ initializers.Jordan Rose2013-03-221-40/+55
| | | | | | Debugging aid only, no functionality change. llvm-svn: 177762
* [analyzer] Print return values from debug.DumpCalls checker.Jordan Rose2013-03-211-1/+23
| | | | | | Debug utility only, no functionality change. llvm-svn: 177649
* [analyzer] Appease buildbots: include template arguments in base class ref.Jordan Rose2013-03-201-1/+1
| | | | llvm-svn: 177583
* [analyzer] Don't invalidate globals when there's no call involved.Jordan Rose2013-03-201-11/+9
| | | | | | | | | | | | | | This fixes some mistaken condition logic in RegionStore that caused global variables to be invalidated when /any/ region was invalidated, rather than only as part of opaque function calls. This was only being used by CStringChecker, and so users will now see that strcpy() and friends do not invalidate global variables. Also, add a test case we don't handle properly: explicitly-assigned global variables aren't being invalidated by opaque calls. This is being tracked by <rdar://problem/13464044>. llvm-svn: 177572
* [analyzer] Track malloc'd memory into struct fields.Jordan Rose2013-03-201-6/+0
| | | | | | | | | | | | | | | Due to improper modelling of copy constructors (specifically, their const reference arguments), we were producing spurious leak warnings for allocated memory stored in structs. In order to silence this, we decided to consider storing into a struct to be the same as escaping. However, the previous commit has fixed this issue and we can now properly distinguish leaked memory that happens to be in a struct from a buffer that escapes within a struct wrapper. Originally applied in r161511, reverted in r174468. <rdar://problem/12945937> llvm-svn: 177571
* [analyzer] Invalidate regions indirectly accessible through const pointers.Jordan Rose2013-03-203-66/+79
| | | | | | | | | | | | | | | | | | | | | | | | | | In this case, the value of 'x' may be changed after the call to indirectAccess: struct Wrapper { int *ptr; }; void indirectAccess(const Wrapper &w); void test() { int x = 42; Wrapper w = { x }; clang_analyzer_eval(x == 42); // TRUE indirectAccess(w); clang_analyzer_eval(x == 42); // UNKNOWN } This is important for modelling return-by-value objects in C++, to show that the contents of the struct are escaping in the return copy-constructor. <rdar://problem/13239826> llvm-svn: 177570
* [analyzer] Remove strip of ElementRegion in CallEvent::invalidateRegions.Jordan Rose2013-03-201-26/+0
| | | | | | | | | | | | | | This is a bit of old code trying to deal with the fact that functions that take pointers often use them to access an entire array via pointer arithmetic. However, RegionStore already conservatively assumes you can use pointer arithmetic to access any part of a region. Some day we may want to go back to handling this specifically for calls, but we can do that in the future. No functionality change. llvm-svn: 177569
* [analyzer] Re-apply "Do part of the work to find shortest bug paths up front".Jordan Rose2013-03-201-43/+126
| | | | | | | | | | With the assurance that the trimmed graph does not contain cycles, this patch is safe (with a few tweaks), and provides the performance boost it was intended to. Part of performance work for <rdar://problem/13433687>. llvm-svn: 177469
* [analyzer] Break cycles (optionally) when trimming an ExplodedGraph.Jordan Rose2013-03-202-3/+19
| | | | | | | | | Having a trimmed graph with no cycles (a DAG) is much more convenient for trying to find shortest paths, which is exactly what BugReporter needs to do. Part of the performance work for <rdar://problem/13433687>. llvm-svn: 177468
* [analyzer] Do not believe lazy binding when symbolic region types do not matchAnna Zaks2013-03-191-5/+16
| | | | | | | | | | | This fixes a crash when analyzing LLVM that was exposed by r177220 (modeling of trivial copy/move assignment operators). When we look up a lazy binding for “Builder”, we see the direct binding of Loc at offset 0. Previously, we believed the binding, which led to a crash. Now, we do not believe it as the types do not match. llvm-svn: 177453
* 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] Warn when a ‘nil’ object is added to NSArray or NSMutableArray.Anna Zaks2013-03-181-4/+33
| | | | llvm-svn: 177318
* [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] Address a TODO in the StreamChecker; otherwise the output is ↵Anna Zaks2013-03-151-2/+1
| | | | | | non-deterministic. llvm-svn: 177207
* [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] fixed the logic changed by r176949Anton Yartsev2013-03-131-4/+5
| | | | llvm-svn: 176956
* Refactoring:Anton Yartsev2013-03-131-34/+55
| | | | | | | | | + Individual Report* method for each bug type + Comment improved: missing non-trivial alloca() case annotated + 'range' parameter of ReportBadFree() capitalized + 'SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol();' shorten to 'SymbolRef Sym = C.getSVal(A).getAsSymbol();' llvm-svn: 176949
OpenPOWER on IntegriCloud