[analyzer] Fix the "Zombie symbols" issue.

[NoQ]

Summary

This patch fixes problems in multiple leak-like static analyzer checkers, which failed to mark symbols managed by them as possibly-dead, and due to that the leak was not detected even though the symbol was removed from the rest of the program state.

Original discussion in cfe-dev started here: http://lists.llvm.org/pipermail/cfe-dev/2016-March/047922.html

The patch implements the solution proposed by Ted Kremenek and described in cfe-dev here: http://lists.llvm.org/pipermail/cfe-dev/2016-March/048215.html

The patch eliminates the "dead set" from the SymbolReaper as a whole, because we now assume that the set of dead symbols is potentially infinite. Hence,dead_iterator, dead_begin(), dead_end() are removed. The maybeDead() API, which was used for marking symbols dead, is removed in order to avoid confusion. The hasDeadSymbols() function is removed as well. The isDead() is modified to mean !isLive().

In case API break is undesired, there's no problem bringing maybeDead() back as a synonym to isDead(), and define hasDeadSymbols() to always return true.

The patch passes the new test for SimpleStreamChecker described in the mailing lists above. It also fixes a FIXME test in unions.cpp, and throws a new warning in pr22954.c.

The new warning in pr22954.c seems correct with the current ideology, however we should probably eventually fix it. My reasoning for this is as follows. The pointer gets lost upon invalidation of m28[j].s4 after binding to l28->s1[l] which in fact aliases to m28[1].s3[l]. According to docs/analyzer/RegionStore.txt, such invalidation is the correct behavior: it is possible that j is equal to 1, and l is out of bounds and the binding actually overwrites one of the bytes in m28[j].s4. So it is the valid behavior of the analyzer to scrap all the bindings to the whole m28 variable region after this bind, which is being tested. However, because it is not *certain* that our pointer gets overwritten, we are not conservative enough when we are suspecting that our pointer was overwritten, so the report is not quite valid, and i may easily imagine false positives (eg. l when is constrained to [0, 3] on that path, we won't be able to handle that). So i should probably mark this as FIXME. However, i don't think this issue is the problem of the current patch; it should be solved separately, either by creating a special kind of PointerEscape to catch such cases, or improving invalidation accuracy by supporting offset constraints (or probably both).

There are a couple of shameful hotfixes in my code in the ExprInspection checker - included here because a problem was exposed by this patch in the symbol-reaper.c test, which now tests ExprInspection deeper.

I avoided fixing some FIXMEs in StreamChecker just around the new code, saving for another patch.

The patch was tested on Android open-source platform source code. I didn't test the patch on any large objective-c codebases, even though the patch alters some objective-c checkers. Performance has slightly degraded (~5%) - hmm, i guess the original approach is very performance-oriented. Also, it has found exactly one(!) new positive, which i'm attaching:

report-ae6984.html149 KBDownload

. Not sure if it is a true bug (depends on external factors about the program which the analyzer could not have guessed anyway), but it is expected from the analyzer to find this positive, so i'm happy with this positive. Still funny to see how issues that seem major in description may actually be very minor when it comes to statistical quality.

So, overally, the patch fixes all the issues and simplifies checker API, but i'm not exactly sure we should go this way; probably going directly for smart data map traits would retain the performance while fixing the issue equally well. Probably we can revert this patch when we allow the core to introspect GDM contents and mark symbols dead automatically.

[zaks.anna]

Thanks for working on this!

The main unfinished task here is to investigate ways of reducing the performance hit. See more info below.

The patch was tested on Android open-source platform source code.

Just to double check, have you compare the pre and after results and all of them but this one issue are the same?

Performance has slightly degraded (~5%) - hmm

5% is a considerable regression :(

lib/StaticAnalyzer/Core/Environment.cpp

200

We are removing this because the maybeDead is no longer used, correct?

lib/StaticAnalyzer/Core/ExprEngine.cpp

685

This removes an optimization to address the following issue:
"removeDeadBindings is not run right after the last reference to the object is lost, which leads to imprecise error reports and failure to report the leak in some cases. It's because of how hasDeadSymbols() is implemented. That problem is solved if we disable the optimization, but I do not know how that effects performance. Maybe we can come up with something more clever.
"
I suspect the removal of this optimization causes the performance regression. In the patch I sent to the list, this was just a hack to demonstrate what causes the issue. I am not sure we should not just remove the optimization... The best proposal I have is to trigger remove dead bindings at the end of every basic block. This would degrade diagnostics (you will see leaks only at the end of the basic block), but should give us performance back or even improve performance.

Artem and Devin, WDYT?

Artem, can you experiment with this and investigate if the diagnostics become much worse? Maybe send a couple of examples? I suggest we implement this mode behind a flag as a separate patch.

lib/StaticAnalyzer/Core/RegionStore.cpp

2591

Looks like we are saying that we should no longer add to maybeDead because it's not used.

[xazax.hun]

What is the status of this patch? Is there a consensus?

[george.karpenkov]

@NoQ can we get the evaluation re-done?

[george.karpenkov]

The change LGTM after nits and rebasing IF the new evaluation will not show a too large regression.

lib/StaticAnalyzer/Checkers/RetainCountChecker.cpp

3925 ↗

(On Diff #52895)

for .. in loop?

lib/StaticAnalyzer/Checkers/StreamChecker.cpp

397

foreach loop?

[NoQ]

Rebase!

Changes on large codebase runs still look mild and reasonable, with much less slowdown than before. Even if there's in fact a 5-10% slowdown, i believe we can live with that, as there doesn't seem to be a better solution for the purposes of correctness.

The most important consequence of the rebase was the conflict that lead to test failure in MacOSKeychainAPIChecker on the radar_19196494() test. The story here is that D28330 unconsciously adds a suppression that relies on zombie symbols. I replaced this suppression with another ugly suppression that should be at least a tiny bit in the right direction.

[NoQ]

lib/StaticAnalyzer/Core/Environment.cpp

200

Yup.

lib/StaticAnalyzer/Core/ExprEngine.cpp

685

This cannot be kept around because .hasDeadSymbols() cannot be implemented correctly.

lib/StaticAnalyzer/Core/RegionStore.cpp

2591

Yup.

[george.karpenkov]

test/Analysis/self-assign.cpp

42

Woo-hoo!

test/Analysis/simple-stream-checks.c

96

Woo-hoo, were we losing this case before?

[NoQ]

test/Analysis/simple-stream-checks.c

96

Yes, this is the whole point of the patch.

[NoQ]

Ha! Apart from Zombie symbols that are neither dead nor alive and therefore not buried properly, there are also Schrödinger symbols that are dead and alive at the same time. Moreover, asking whether a Schrödinger symbol is isLive() or maybeDead() would immediately collapse it into an alive-only state. Moreover, if a checker iterates through the dead set and asks whether a Schrödinger symbol is alive, undefined behavior occurs. Ah, thin ice.

As far as i understand, this only happens to derived symbols under fairly specific circumstances. Namely, if the derived symbol is marked as dead and then its parent symbol is marked as live, the derived symbol is not automatically removed from the "dead set". It is impossible to automatically add derived symbols to the dead set because there may be infinitely many symbols derived from the same parent symbol. Therefore there exists moment of time when the derived symbol is still in the dead set, but asking whether it is isLive() would yield true (because it'll check whether the parent symbol is alive). Additionally, when isLive() notices that it's alive, it automatically removes the symbol from the dead set in order to "memoize" the answer, so it becomes purely alive. In particular, it invalidates dead set iterators, which results in undefined behavior (which in practice boils down to past-end iterator access, ultimately crashing Clang).

Schrödinger symbols cause false positive leaks, unlike zombies who only cause false negative leaks. But those false positives are relatively rare because most checkers don't track derived symbols; eg., MallocChecker only tracks pure conjured symbols. RetainCountChecker is affected, as demonstrated by the newly added test. Not sure if it's possible to make CStringChecker track a derived symbol and forget a string length due to that effect. MacOSKeychainAPI checker should also be affected, i think, but i didn't try. NullabilityChecker is probably unaffected; its behavior on dead symbols is pretty weird, but it seems safe; it also has a separate bug that was exposed but i'll address in a separate patch.

[NoQ]

Just to be clear - this newly found problem is also automatically fixed by that patch.

[Szelethus]

I read through your patch multiple times, have read your mail on cfe-dev, and I still couldn't find eve minor nits, well done!

However, both in the mail, and in this discussion, there are a lot of invaluable information about the inner workings of the analyzer, that I fear will be lost once this revision is closed, even though I don't think the main logic will change in the near future. It would be neat to document it for the next generation somewhere.

Another thing, since we're directly testing the functionality of SymbolReaper, maybe it'd be worth to also include unit tests.

I'll probably revisit this revision as I read through your followup patches, but I can't seem to find errors in the main logic straight away. GG!

[NoQ]

Add an interesting test for the MisusedMovedObject checker that demonstrates one more potential source of false positives caused by the zombie symbol problem. In this test there are, well, no symbols. Therefore, there are no dead symbols or zombie symbols. Therefore SymReaper.hasDeadSymbols() is always false. Therefore checkDeadSymbols() is never called at all. However, MisusedMovedObject checker is not interested in symbols; it is only interested in regions, including concrete regions that aren't based on symbols. So it was missing the checkDeadSymbols() callback that would have unmarked the region for variable e (in inlined function or not in inlined function - doesn't matter). And next time it sees variable e in that function within the same stack frame, it thinks it's the same variable that has just been moved.

This problem was already discussed in D24246?id=82469#inline-249803.

Add tests in loop-block-counts.c that demonstrate the other source of the problem in MisusedMovedObject: in fact, variable e should not be the same variable on different iterations of the loop. In case of the inlined function, the problem is caused by how our StackFrameContext doesn't contain "block count" for the entrance - which is a hack to discriminate between different iterations of the loop that is used for, eg., conjured symbols, but, unfortunately, not for addresses of variables / temporaries. In case of non-inlined functions, the problem is deeper: we simply don't have a LocationContext for a single loop iteration, so there's no way we can discriminate between loop locals on different loop iterations by their memory spaces.

[NoQ]

The manual region cleanup is removed from MisusedMovedObjectChecker in D54372.

Another thing, since we're directly testing the functionality of SymbolReaper, maybe it'd be worth to also include unit tests.

Sounds like a great idea, and/or i should add ExprInspection-based tests into test/Analysis/symbol-reaper.c.

[NoQ]

In D18860#1284805, @NoQ wrote:

RetainCountChecker is affected, as demonstrated by the newly added test.

RetainCountChecker is affected due to temporary insanity in the checker that was induced by trusting summaries of inlined calls, which was reverted in D53902. I'll keep the FP/TN test, but i'll need to come up with a new test in order to test whatever i wanted to test, which will most likely be a unit test.

[NoQ]

Nope, unit tests aren't quite useful here. I can't unit-test the behavior of API that i'm about to remove... right?

[Szelethus]

In D18860#1297742, @NoQ wrote:

Nope, unit tests aren't quite useful here. I can't unit-test the behavior of API that i'm about to remove... right?

Hmmm, can't really argue with that, can I? :D

[Szelethus]

Let's also have the link to your most recent mail about this issue here: http://lists.llvm.org/pipermail/cfe-dev/2018-November/060038.html

I re-read the mailing list conversation from 2016, @szepet's MisusedMoveChecker patch, so I have a better graps on whats happening.

I think this really is non-trivial stuff. When I initially read your workbook, SymbolReaper (along with what inlining really is) was among the biggest unsolved mysteries for me. The explanation of it you wrote back in 2016[1] is awesome, I feel enlightened after reading it, it's very well constructed, but I find it unfortunate that it took me almost a year of working in the analyzer to find it. After looking at SymbolManager.cpp's history, I can see that the logic didn't change since, I'd very strongly prefer to have this goldnugget copy-pasted even to a simple txt file, and have it commited with this patch.

[1] http://lists.llvm.org/pipermail/cfe-dev/2016-March/048142.html

In D18860#1306359, @Szelethus wrote:

In D18860#1297742, @NoQ wrote:

Nope, unit tests aren't quite useful here. I can't unit-test the behavior of API that i'm about to remove... right?

Hmmm, can't really argue with that, can I? :D

Well, we probably should implement unit tests for these anyways, SymbolReaper is not only performance-critical, but is also among the few data structures that's an essential part of the analysis, and it's change in functionality could be very easily shown in dedicated test files. But that's an issue for another time, and until then, debug.ExprInspection still does the job well enough. Let's not delay this patch longer just because of that, and enjoy the post zombie apocalypse analyzer.

[NoQ]

I'd very strongly prefer to have this goldnugget copy-pasted even to a simple txt file, and have it commited with this patch.

I guess i'll do it a bit later because it needs to be cleaned up after the behavior changes with this patch. There are a few other such discussions that i wanted to add to our docs.

include/clang/StaticAnalyzer/Core/PathSensitive/SMTConstraintManager.h

public:
   }
 
   ProgramStateRef removeDeadBindings(ProgramStateRef State,
                                      SymbolReaper &SymReaper) override {
     auto CZ = State->get<ConstraintSMT>();
     auto &CZFactory = State->get_context<ConstraintSMT>();
 
     for (auto I = CZ.begin(), E = CZ.end(); I != E; ++I) {
-      if (SymReaper.maybeDead(I->first))
+      if (SymReaper.isDead(I->first))
         CZ = CZFactory.remove(CZ, *I);
     }
 
     return State->set<ConstraintSMT>(CZ);
   }
 
   void print(ProgramStateRef St, raw_ostream &OS, const char *nl,
              const char *sep) override {

include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h

class SymbolReaper {
   };
 
   using SymbolSetTy = llvm::DenseSet<SymbolRef>;
   using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;
   using RegionSetTy = llvm::DenseSet<const MemRegion *>;
 
   SymbolMapTy TheLiving;
   SymbolSetTy MetadataInUse;
-  SymbolSetTy TheDead;
 
   RegionSetTy RegionRoots;
 
   const StackFrameContext *LCtx;
   const Stmt *Loc;
   SymbolManager& SymMgr;
   StoreRef reapedStore;
   llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
public:
   ///
   /// For metadata symbols,
   /// this will keep the symbol alive as long as its associated region is also
   /// live. For other symbols, this has no effect; checkers are not permitted
   /// to influence the life of other symbols. This should be used before any
   /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
   void markInUse(SymbolRef sym);
 
-  /// If a symbol is known to be live, marks the symbol as live.
-  ///
-  ///  Otherwise, if the symbol cannot be proven live, it is marked as dead.
-  ///  Returns true if the symbol is dead, false if live.
-  bool maybeDead(SymbolRef sym);
-
-  using dead_iterator = SymbolSetTy::const_iterator;
-
-  dead_iterator dead_begin() const { return TheDead.begin(); }
-  dead_iterator dead_end() const { return TheDead.end(); }
-
-  bool hasDeadSymbols() const {
-    return !TheDead.empty();
-  }
-
   using region_iterator = RegionSetTy::const_iterator;
 
   region_iterator region_begin() const { return RegionRoots.begin(); }
   region_iterator region_end() const { return RegionRoots.end(); }
 
   /// Returns whether or not a symbol has been confirmed dead.
   ///
   /// This should only be called once all marking of dead symbols has completed.
-  /// (For checkers, this means only in the evalDeadSymbols callback.)
-  bool isDead(SymbolRef sym) const {
-    return TheDead.count(sym);
+  /// (For checkers, this means only in the checkDeadSymbols callback.)
+  bool isDead(SymbolRef sym) {
+    return !isLive(sym);
   }
 
   void markLive(const MemRegion *region);
   void markElementIndicesLive(const MemRegion *region);
 
   /// Set to the value of the symbolic store after
   /// StoreManager::removeDeadBindings has been called.
   void setReapedStore(StoreRef st) { reapedStore = st; }

lib/StaticAnalyzer/Checkers/CStringChecker.cpp

for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end();
     for (SymExpr::symbol_iterator si = Len.symbol_begin(),
         se = Len.symbol_end(); si != se; ++si)
       SR.markInUse(*si);
   }
 }
 
 void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
     CheckerContext &C) const {
-  if (!SR.hasDeadSymbols())
-    return;
-
   ProgramStateRef state = C.getState();
   CStringLengthTy Entries = state->get<CStringLength>();
   if (Entries.isEmpty())
     return;
 
   CStringLengthTy::Factory &F = state->get_context<CStringLength>();
   for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end();
       I != E; ++I) {

lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR,
   DynamicTypeMapImpl TypeMap = State->get<DynamicTypeMap>();
   for (DynamicTypeMapImpl::iterator I = TypeMap.begin(), E = TypeMap.end();
        I != E; ++I) {
     if (!SR.isLiveRegion(I->first)) {
       State = State->remove<DynamicTypeMap>(I->first);
     }
   }
 
-  if (!SR.hasDeadSymbols()) {
-    C.addTransition(State);
-    return;
-  }
-
   MostSpecializedTypeArgsMapTy TyArgMap =
       State->get<MostSpecializedTypeArgsMap>();
   for (MostSpecializedTypeArgsMapTy::iterator I = TyArgMap.begin(),
                                               E = TyArgMap.end();
        I != E; ++I) {
     if (SR.isDead(I->first)) {
       State = State->remove<MostSpecializedTypeArgsMap>(I->first);
     }

lib/StaticAnalyzer/Checkers/MPI-Checker/MPIChecker.cpp

if (!ErrorNode) {
     Ctx.addTransition(State);
   } else {
     Ctx.addTransition(State, ErrorNode);
   }
 }
 
 void MPIChecker::checkMissingWaits(SymbolReaper &SymReaper,
                                    CheckerContext &Ctx) const {
-  if (!SymReaper.hasDeadSymbols())
-    return;
-
   ProgramStateRef State = Ctx.getState();
   const auto &Requests = State->get<RequestMap>();
   if (Requests.isEmpty())
     return;
 
   static CheckerProgramPointTag Tag("MPI-Checker", "MissingWait");
   ExplodedNode *ErrorNode{nullptr};
 

lib/StaticAnalyzer/Checkers/MacOSKeychainAPIChecker.cpp

 // SecKeychainFindGenericPassword, SecKeychainFindInternetPassword functions has
 // to be freed using a call to SecKeychainItemFreeContent.
 //===----------------------------------------------------------------------===//
 
 #include "ClangSACheckers.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
 class MacOSKeychainAPIChecker : public Checker<check::PreStmt<CallExpr>,
                                                check::PostStmt<CallExpr>,
                                                check::DeadSymbols,
+                                               check::PointerEscape,
                                                eval::Assume> {
   mutable std::unique_ptr<BugType> BT;
 
 public:
   /// AllocationState is a part of the checker specific state together with the
   /// MemRegion corresponding to the allocated data.
   struct AllocationState {
     /// The index of the allocator function.
void Profile(llvm::FoldingSetNodeID &ID) const {
       ID.AddInteger(AllocatorIdx);
       ID.AddPointer(Region);
     }
   };
 
   void checkPreStmt(const CallExpr *S, CheckerContext &C) const;
   void checkPostStmt(const CallExpr *S, CheckerContext &C) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  ProgramStateRef checkPointerEscape(ProgramStateRef State,
+                                     const InvalidatedSymbols &Escaped,
+                                     const CallEvent *Call,
+                                     PointerEscapeKind Kind) const;
   ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond,
                              bool Assumption) const;
   void printState(raw_ostream &Out, ProgramStateRef State,
                   const char *NL, const char *Sep) const;
 
 private:
   typedef std::pair<SymbolRef, const AllocationState*> AllocationPair;
   typedef SmallVector<AllocationPair, 2> AllocationPairVec;
void MacOSKeychainAPIChecker::checkDeadSymbols(SymbolReaper &SR,
   // Generate the error reports.
   for (const auto &P : Errors)
     C.emitReport(generateAllocatedDataNotReleasedReport(P, N, C));
 
   // Generate the new, cleaned up state.
   C.addTransition(State, N);
 }
 
+ProgramStateRef MacOSKeychainAPIChecker::checkPointerEscape(
+    ProgramStateRef State, const InvalidatedSymbols &Escaped,
+    const CallEvent *Call, PointerEscapeKind Kind) const {
+  // FIXME: This branch doesn't make any sense at all, but it is an overfitted
+  // replacement for a previous overfitted code that was making even less sense.
+  if (!Call || Call->getDecl())
+    return State;
+
+  for (auto I : State->get<AllocatedData>()) {
+    SymbolRef Sym = I.first;
+    if (Escaped.count(Sym))
+      State = State->remove<AllocatedData>(Sym);
+
+    // This checker is special. Most checkers in fact only track symbols of
+    // SymbolConjured type, eg. symbols returned from functions such as
+    // malloc(). This checker tracks symbols returned as out-parameters.
+    //
+    // When a function is evaluated conservatively, the out-parameter's pointee
+    // base region gets invalidated with a SymbolConjured. If the base region is
+    // larger than the region we're interested in, the value we're interested in
+    // would be SymbolDerived based on that SymbolConjured. However, such
+    // SymbolDerived will never be listed in the Escaped set when the base
+    // region is invalidated because ExprEngine doesn't know which symbols
+    // were derived from a given symbol, while there can be infinitely many
+    // valid symbols derived from any given symbol.
+    //
+    // Hence the extra boilerplate: remove the derived symbol when its parent
+    // symbol escapes.
+    //
+    if (const auto *SD = dyn_cast<SymbolDerived>(Sym)) {
+      SymbolRef ParentSym = SD->getParentSymbol();
+      if (Escaped.count(ParentSym))
+        State = State->remove<AllocatedData>(Sym);
+    }
+  }
+  return State;
+}
+
 std::shared_ptr<PathDiagnosticPiece>
 MacOSKeychainAPIChecker::SecKeychainBugVisitor::VisitNode(
     const ExplodedNode *N, BugReporterContext &BRC, BugReport &BR) {
   const AllocationState *AS = N->getState()->get<AllocatedData>(Sym);
   if (!AS)
     return nullptr;
   const AllocationState *ASPrev =
       N->getFirstPred()->getState()->get<AllocatedData>(Sym);

lib/StaticAnalyzer/Checkers/MallocChecker.cpp

void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N,
   R->markInteresting(Sym);
   R->addVisitor(llvm::make_unique<MallocBugVisitor>(Sym, true));
   C.emitReport(std::move(R));
 }
 
 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                      CheckerContext &C) const
 {
-  if (!SymReaper.hasDeadSymbols())
-    return;
-
   ProgramStateRef state = C.getState();
   RegionStateTy RS = state->get<RegionState>();
   RegionStateTy::Factory &F = state->get_context<RegionState>();
 
   SmallVector<SymbolRef, 2> Errors;
   for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
     if (SymReaper.isDead(I->first)) {
       if (I->second.isAllocated() || I->second.isAllocatedOfSizeZero())

lib/StaticAnalyzer/Checkers/NullabilityChecker.cpp

void NullabilityChecker::reportBugIfInvariantHolds(StringRef Msg,
   }
 
   reportBug(Msg, Error, N, Region, C.getBugReporter(), ValueExpr);
 }
 
 /// Cleaning up the program state.
 void NullabilityChecker::checkDeadSymbols(SymbolReaper &SR,
                                           CheckerContext &C) const {
-  if (!SR.hasDeadSymbols())
-    return;
-
   ProgramStateRef State = C.getState();
   NullabilityMapTy Nullabilities = State->get<NullabilityMap>();
   for (NullabilityMapTy::iterator I = Nullabilities.begin(),
                                   E = Nullabilities.end();
        I != E; ++I) {
     const auto *Region = I->first->getAs<SymbolicRegion>();
     assert(Region && "Non-symbolic region is tracked.");
     if (SR.isDead(Region->getSymbol())) {

lib/StaticAnalyzer/Checkers/RetainCountChecker/RetainCountChecker.cpp

void RetainCountChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                           CheckerContext &C) const {
   ExplodedNode *Pred = C.getPredecessor();
 
   ProgramStateRef state = C.getState();
   RefBindingsTy B = state->get<RefBindings>();
   SmallVector<SymbolRef, 10> Leaked;
 
   // Update counts from autorelease pools
-  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
-       E = SymReaper.dead_end(); I != E; ++I) {
-    SymbolRef Sym = *I;
-    if (const RefVal *T = B.lookup(Sym)){
-      // Use the symbol as the tag.
-      // FIXME: This might not be as unique as we would like.
+  for (const auto &I: state->get<RefBindings>()) {
+    SymbolRef Sym = I.first;
+    if (SymReaper.isDead(Sym)) {
       static CheckerProgramPointTag Tag(this, "DeadSymbolAutorelease");
-      state = handleAutoreleaseCounts(state, Pred, &Tag, C, Sym, *T);
+      const RefVal &V = I.second;
+      state = handleAutoreleaseCounts(state, Pred, &Tag, C, Sym, V);
       if (!state)
         return;
 
       // Fetch the new reference count from the state, and use it to handle
       // this symbol.
-      state = handleSymbolDeath(state, *I, *getRefBinding(state, Sym), Leaked);
+      state = handleSymbolDeath(state, Sym, *getRefBinding(state, Sym), Leaked);
     }
   }
 
   if (Leaked.empty()) {
     C.addTransition(state);
     return;
   }
 

lib/StaticAnalyzer/Checkers/StreamChecker.cpp

ProgramStateRef StreamChecker::CheckDoubleClose(const CallExpr *CE,
   }
 
   // Close the File Descriptor.
   return state->set<StreamMap>(Sym, StreamState::getClosed(CE));
 }
 
 void StreamChecker::checkDeadSymbols(SymbolReaper &SymReaper,
                                      CheckerContext &C) const {
-  // TODO: Clean up the state.
-  for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
-         E = SymReaper.dead_end(); I != E; ++I) {
-    SymbolRef Sym = *I;
-    ProgramStateRef state = C.getState();
-    const StreamState *SS = state->get<StreamMap>(Sym);
-    if (!SS)
+
+  // TODO: Clean up the state.
+  const StreamMapTy &Map = state->get<StreamMap>();
+  for (const auto &I: Map) {
+    SymbolRef Sym = I.first;
+    const StreamState &SS = I.second;
+    if (!SymReaper.isDead(Sym) || !SS.isOpened())
       continue;
 
-    if (SS->isOpened()) {
-      ExplodedNode *N = C.generateErrorNode();
-      if (N) {
-        if (!BT_ResourceLeak)
-          BT_ResourceLeak.reset(new BuiltinBug(
-              this, "Resource Leak",
+    if (!N)
+      return;
+
+      BT_ResourceLeak.reset(
+          new BuiltinBug(this, "Resource Leak",
                          "Opened File never closed. Potential Resource leak."));
-        C.emitReport(llvm::make_unique<BugReport>(
-            *BT_ResourceLeak, BT_ResourceLeak->getDescription(), N));
-      }
-    }
-  }
-}
 
 void ento::registerStreamChecker(CheckerManager &mgr) {
   mgr.registerChecker<StreamChecker>();
 }

lib/StaticAnalyzer/Core/Environment.cpp

for (Environment::iterator I = Env.begin(), E = Env.end();
     const SVal &X = I.getData();
 
     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
       // Copy the binding to the new map.
       EBMapRef = EBMapRef.add(BlkExpr, X);
 
       // Mark all symbols in the block expr's value live.
       RSScaner.scan(X);
-      continue;
-    } else {
-      SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
-      for (; SI != SE; ++SI)
-        SymReaper.maybeDead(*SI);
     }
   }
 
   NewEnv.ExprBindings = EBMapRef.asImmutableMap();
   return NewEnv;
 }
 
 void Environment::print(raw_ostream &Out, const char *NL,

lib/StaticAnalyzer/Core/ExprEngine.cpp

void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
   // Create a state in which dead bindings are removed from the environment
   // and the store. TODO: The function should just return new env and store,
   // not a new state.
   CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
 
   // Process any special transfer function for dead symbols.
   // A tag to track convenience transitions, which can be removed at cleanup.
   static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
-  if (!SymReaper.hasDeadSymbols()) {
-    // Generate a CleanedNode that has the environment and store cleaned
-    // up. Since no symbols are dead, we can optimize and not clean out
-    // the constraint manager.
-    StmtNodeBuilder Bldr(Pred, Out, *currBldrCtx);
-    Bldr.generateNode(DiagnosticStmt, Pred, CleanedState, &cleanupTag, K);
-
-  } else {
-    // Call checkers with the non-cleaned state so that they could query the
-    // values of the soon to be dead symbols.
-    ExplodedNodeSet CheckedSet;
-    getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
-                                                  DiagnosticStmt, *this, K);
 
-    // For each node in CheckedSet, generate CleanedNodes that have the
-    // environment, the store, and the constraints cleaned up but have the
-    // user-supplied states as the predecessors.
-    StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
-    for (const auto I : CheckedSet) {
-      ProgramStateRef CheckerState = I->getState();
 
-      // The constraint manager has not been cleaned up yet, so clean up now.
-      CheckerState = getConstraintManager().removeDeadBindings(CheckerState,
-                                                               SymReaper);
+    CheckerState =
+        getConstraintManager().removeDeadBindings(CheckerState, SymReaper);
 
-      assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
            "Checkers are not allowed to modify the Environment as a part of "
            "checkDeadSymbols processing.");
-      assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
            "Checkers are not allowed to modify the Store as a part of "
            "checkDeadSymbols processing.");
 
-      // Create a state based on CleanedState with CheckerState GDM and
-      // generate a transition to that state.
-      ProgramStateRef CleanedCheckerSt =
         StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
-      Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
-    }
-  }
-}
 
 void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
   // Reclaim any unnecessary nodes in the ExplodedGraph.
   G.reclaimRecentlyAllocatedNodes();
 
   PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
                                 currStmt->getBeginLoc(),
                                 "Error evaluating statement");

lib/StaticAnalyzer/Core/RangeConstraintManager.cpp

 RangeConstraintManager::removeDeadBindings(ProgramStateRef State,
                                            SymbolReaper &SymReaper) {
   bool Changed = false;
   ConstraintRangeTy CR = State->get<ConstraintRange>();
   ConstraintRangeTy::Factory &CRFactory = State->get_context<ConstraintRange>();
 
   for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
     SymbolRef Sym = I.getKey();
-    if (SymReaper.maybeDead(Sym)) {
+    if (SymReaper.isDead(Sym)) {
       Changed = true;
       CR = CRFactory.remove(CR, Sym);
     }
   }
 
   return Changed ? State->set<ConstraintRange>(CR) : State;
 }
 

lib/StaticAnalyzer/Core/RegionStore.cpp

StoreRef RegionStoreManager::removeDeadBindings(Store store,
 
   // We have now scanned the store, marking reachable regions and symbols
   // as live.  We now remove all the regions that are dead from the store
   // as well as update DSymbols with the set symbols that are now dead.
   for (RegionBindingsRef::iterator I = B.begin(), E = B.end(); I != E; ++I) {
     const MemRegion *Base = I.getKey();
 
     // If the cluster has been visited, we know the region has been marked.
-    if (W.isVisited(Base))
-      continue;
-
-    // Remove the dead entry.
+    // Otherwise, remove the dead entry.
+    if (!W.isVisited(Base))
       B = B.remove(Base);
-
-    if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(Base))
-      SymReaper.maybeDead(SymR->getSymbol());
-
-    // Mark all non-live symbols that this binding references as dead.
-    const ClusterBindings &Cluster = I.getData();
-    for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
-         CI != CE; ++CI) {
-      SVal X = CI.getData();
-      SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
-      for (; SI != SE; ++SI)
-        SymReaper.maybeDead(*SI);
-    }
   }
 
   return StoreRef(B.asStore(), *this);
 }
 
 //===----------------------------------------------------------------------===//
 // Utility methods.
 //===----------------------------------------------------------------------===//

lib/StaticAnalyzer/Core/SymbolManager.cpp

for (const auto I : *Deps) {
         continue;
       markLive(I);
     }
   }
 }
 
 void SymbolReaper::markLive(SymbolRef sym) {
   TheLiving[sym] = NotProcessed;
-  TheDead.erase(sym);
   markDependentsLive(sym);
 }
 
 void SymbolReaper::markLive(const MemRegion *region) {
   RegionRoots.insert(region);
   markElementIndicesLive(region);
 }
 
 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
   for (auto SR = dyn_cast<SubRegion>(region); SR;
        SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
     if (const auto ER = dyn_cast<ElementRegion>(SR)) {
       SVal Idx = ER->getIndex();
       for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
         markLive(*SI);
     }
   }
 }
 
 void SymbolReaper::markInUse(SymbolRef sym) {
   if (isa<SymbolMetadata>(sym))
     MetadataInUse.insert(sym);
 }
 
-bool SymbolReaper::maybeDead(SymbolRef sym) {
-  if (isLive(sym))
-    return false;
-
-  TheDead.insert(sym);
-  return true;
-}
-
 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
   if (RegionRoots.count(MR))
     return true;
 
   MR = MR->getBaseRegion();
 
   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
     return isLive(SR->getSymbol());

test/Analysis/MisusedMovedObject.cpp

 }
 
 void reportSuperClass() {
   C c;
   C c1 = std::move(c); // expected-note {{'c' became 'moved-from' here}}
   c.foo();             // expected-warning {{Method call on a 'moved-from' object 'c'}} expected-note {{Method call on a 'moved-from' object 'c'}}
   C c2 = c;            // no-warning
 }
+
+struct Empty {};
+
+Empty inlinedCall() {
+  // Used to warn because region 'e' failed to be cleaned up because no symbols
+  // have ever died during the analysis and the checkDeadSymbols callback
+  // was skipped entirely.
+  Empty e{};
+  return e; // no-warning
+}
+
+void checkInlinedCallZombies() {
+  while (true)
+    inlinedCall();
+}
+
+void checkLoopZombies() {
+  while (true) {
+    Empty e{};
+    Empty f = std::move(e); // no-warning
+  }
+}

test/Analysis/keychainAPI.m

int foo(CFTypeRef keychainOrArray, SecProtocolType protocol,
   st = SecKeychainFindInternetPassword(keychainOrArray, 
                                        16, "server", 16, "domain", 16, "account",
                                        16, "path", 222, protocol, authenticationType,
                                        &length, &(outData[3]), itemRef);
   if (length == 5) {
     if (st == noErr)
       SecKeychainItemFreeContent(ptr, outData[3]);
   }
-  if (length) { // TODO: We do not report a warning here since the symbol is no longer live, but it's not marked as dead.
+  if (length) { // expected-warning{{Allocated data is not released: missing a call to 'SecKeychainItemFreeContent'}}
     length++;
   }
   return 0;
 }
 
 int testErrorCodeAsLHS(CFTypeRef keychainOrArray, SecProtocolType protocol,
         SecAuthenticationType authenticationType, SecKeychainItemRef *itemRef) {
   unsigned int *ptr = 0;
@autoreleasepool {
     OSStatus err = SecKeychainFindGenericPassword(0, 0, "", 0, "", (UInt32 *)&login_password.length, (void**)&login_password.data, 0);
     cb.SetContextVal(&login_password);
     if (err == noErr) {
       SecKeychainItemFreeContent(0, login_password.data);
     }
   }
   return 0;
 }
+int radar_19196494_v2() {
+  @autoreleasepool {
+    AuthorizationValue login_password = {};
+    OSStatus err = SecKeychainFindGenericPassword(0, 0, "", 0, "", (UInt32 *)&login_password.length, (void**)&login_password.data, 0);
+    if (!login_password.data) return 0;
+    cb.SetContextVal(&login_password);
+    if (err == noErr) {
+      SecKeychainItemFreeContent(0, login_password.data);
+    }
+  }
+  return 0;
+}

test/Analysis/loop-block-counts.c

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+void callee(void **p) {
+  int x;
+  *p = &x;
+}
+
+void loop() {
+  void *arr[2];
+  for (int i = 0; i < 2; ++i)
+    callee(&arr[i]);
+  // FIXME: Should be UNKNOWN.
+  clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{TRUE}}
+}
+
+void loopWithCall() {
+  void *arr[2];
+  for (int i = 0; i < 2; ++i) {
+    int x;
+    arr[i] = &x;
+  }
+  // FIXME: Should be UNKNOWN.
+  clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{TRUE}}
+}

test/Analysis/pr22954.c

 }
 
 int f28(int i, int j, int k, int l) {
   struct mm m28[2];
   m28[i].s4 = strdup("hello");
   m28[j].s3[k] = 1;
   struct ll * l28 = (struct ll*)(&m28[1]);
   l28->s1[l] = 2;
-  char input[] = {'a', 'b', 'c', 'd'};
+  char input[] = {'a', 'b', 'c', 'd'}; // expected-warning{{Potential leak of memory pointed to by field 's4'}}
   memcpy(l28->s1, input, 4);
   clang_analyzer_eval(m28[0].s3[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[2] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[0].s3[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(m28[1].s3[2] == 1); // expected-warning{{UNKNOWN}}

test/Analysis/retain-release-cpp-classes.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,osx -analyzer-output=text -verify %s
+
+// expected-no-diagnostics
+
+typedef void *CFTypeRef;
+typedef struct _CFURLCacheRef *CFURLCacheRef;
+
+CFTypeRef CustomCFRetain(CFTypeRef);
+void invalidate(void *);
+struct S1 {
+  CFTypeRef s;
+  CFTypeRef returnFieldAtPlus0() {
+    return s;
+  }
+};
+struct S2 {
+  S1 *s1;
+};
+void foo(S1 *s1) {
+  invalidate(s1);
+  S2 s2;
+  s2.s1 = s1;
+  CustomCFRetain(s1->returnFieldAtPlus0());
+
+  // Definitely no leak end-of-path note here. The retained pointer
+  // is still accessible through s1 and s2.
+  ((void) 0); // no-warning
+
+  // FIXME: Ideally we need to warn after this invalidate(). The per-function
+  // retain-release contract is violated: the programmer should release
+  // the symbol after it was retained, within the same function.
+  invalidate(&s2);
+}

test/Analysis/self-assign.cpp

 StringUsed::~StringUsed() {
   free(str);
 }
 
 StringUsed& StringUsed::operator=(const StringUsed &rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
   clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
   free(str); // expected-note{{Memory is released}}
   str = strdup(rhs.str); // expected-warning{{Use of memory after it is freed}}  expected-note{{Use of memory after it is freed}}
+// expected-note@-1{{Memory is allocated}}
   return *this;
 }
 
 StringUsed& StringUsed::operator=(StringUsed &&rhs) { // expected-note{{Assuming rhs == *this}} expected-note{{Assuming rhs != *this}}
   clang_analyzer_eval(*this == rhs); // expected-warning{{TRUE}} expected-warning{{UNKNOWN}} expected-note{{TRUE}} expected-note{{UNKNOWN}}
   str = rhs.str;
-  rhs.str = nullptr; // FIXME: An improved leak checker should warn here
+  rhs.str = nullptr; // expected-warning{{Potential memory leak}} expected-note{{Potential memory leak}}
   return *this;
 }
 
 StringUsed::operator const char*() const {
   return str;
 }
 
 class StringUnused {

 
 StringUnused::operator const char*() const {
   return str;
 }
 
 
 int main() {
   StringUsed s1 ("test"), s2;
-  s2 = s1;
-  s2 = std::move(s1);
+  s2 = s1; // expected-note{{Calling copy assignment operator for 'StringUsed'}} // expected-note{{Returned allocated memory}}
+  s2 = std::move(s1); // expected-note{{Calling move assignment operator for 'StringUsed'}}
   return 0;
 }

test/Analysis/simple-stream-checks.c

void testPassConstPointer() {
   return; // expected-warning {{Opened file is never closed; potential resource leak}}
 }
 
 void testPassToSystemHeaderFunctionIndirectly() {
   FileStruct fs;
   fs.p = fopen("myfile.txt", "w");
   fakeSystemHeaderCall(&fs); // invalidates fs, making fs.p unreachable
 }  // no-warning
+
+void testOverwrite() {
+  FILE *fp = fopen("myfile.txt", "w");
+  fp = 0;
+} // expected-warning {{Opened file is never closed; potential resource leak}}

test/Analysis/unions.cpp

namespace PR17596 {
   void testInvalidation() {
     IntOrString uu;
     uu.s = strdup("");
 
     IntOrString vv;
     char str[] = "abc";
     vv.s = str;
 
-    // FIXME: This is a leak of uu.s.
     uu = vv;
-  }
+  } // expected-warning{{leak}}
 
   void testIndirectInvalidation() {
     IntOrString uu;
     char str[] = "abc";
     uu.s = str;
 
     clang_analyzer_eval(uu.s[0] == 'a'); // expected-warning{{TRUE}}