[analyzer] [proposal] Fix for PR20653

[a.sidorin]

Summary

Do not assume SymbolRegionValues live after their regions have direct bindings
http://llvm.org/bugs/show_bug.cgi?id=20563

[jordan_rose]

Hm, yes, this would make sense. It's still not complete because things can remove bindings from the Store, which does not make formerly invalid symbols valid again. But it still seems like a strict improvement over the base. Thanks!

Please add some test cases, following the examples in test/Analysis.

lib/StaticAnalyzer/Core/SymbolManager.cpp

451–452

Please reformat to be two separate lines. We try not to break before . when we can help it.

[a.sidorin]

Thank you Jordan. You're right, I have missed something. But it seems to be not so trivial.

[a.sidorin]

Check if a region changes instead of look up if a region has bindings.

[jordan_rose]

I really don't want states tracking liveness information—for one, you never remove this information even after the symbol is marked dead. Moreover, this still wouldn't handle removing a binding, nor would it handle binding to an entire aggregate region (i.e. what happens for struct assignment). I think the most-semantically-correct thing to do would be to ask the Store to refetch the value of the region, but that's not too cheap. Maybe we just need a new API to ask "are there any bindings to this region or any of its super-regions?".

[a.sidorin]

Thank you Jordan. Sorry for delay.
As I understand, a first revision of this patch has two problems:

1. It doesn't care about bindings to parent regions.
2. It misses a situation where a binding is added and removed before dead symbols removal.

And the second revision is broken completely.
Your idea is good since it solves the first problem but its implementation will take some time. And currently I have no ideas about a nice fix for the second problem.

[jordan_rose]

I'd be okay with committing the original change as a partial measure. Who knows when any of us will get around to implementing something more complete? But I'll let you make that call.

[NoQ]

While investigating http://reviews.llvm.org/D12726 , i accidentally came up with a way to test this patch; with the extension of ExprInspectionChecker in the aforementioned review, which allows testing SymbolReaper directly, the following test passes as soon as the old (accepted) version of this diff is applied:

void clang_analyzer_warnOnDeadSymbol(int);
void clang_analyzer_warnIfReached(void);

// SymbolRegionValue should live as long as its region is live but has no
// direct bindings that override its value.
void test_region_value_lifetime_after_binding(int x) {
  clang_analyzer_warnOnDeadSymbol(x);
  if (x) {}
  x = 0;
  (void)0; // expected-warning{{SYMBOL DEAD}}
  if (x) {
    clang_analyzer_warnIfReached(); // no-warning
  }
} // no-warning

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

     return setDynamicTypeInfo(Reg, DynamicTypeInfo(NewTy, CanBeSubClassed));
   }
 
+  ProgramStateRef setDead(SymbolRef Sym) const;
+  bool isDead(SymbolRef Sym) const;
+
   //==---------------------------------------------------------------------==//
   // Accessing the Generic Data Map (GDM).
   //==---------------------------------------------------------------------==//

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

 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"

     return SE->getType();
   }
 
+  ProgramStateRef notifyBind(ProgramStateRef state, const MemRegion *MR);
+
   /// \brief Add artificial symbol dependency.
   ///
   /// The dependent symbol should stay alive as long as the primary is alive.

   
   const StackFrameContext *LCtx;
   const Stmt *Loc;
+  ProgramStateRef state;
   SymbolManager& SymMgr;
   StoreRef reapedStore;
   llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;

   /// considered live.
   /// If the stack frame context is NULL, everything on stack is considered
   /// dead.
-  SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager& symmgr,
-               StoreManager &storeMgr)
-   : LCtx(Ctx), Loc(s), SymMgr(symmgr),
-     reapedStore(nullptr, storeMgr) {}
+  SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
+               ProgramStateRef currentState);
 
   ~SymbolReaper() {}
 

lib/StaticAnalyzer/Core/ExprEngine.cpp

                                  ArrayRef<const MemRegion *> Explicits,
                                  ArrayRef<const MemRegion *> Regions,
                                  const CallEvent *Call) {
+  for (auto I = Regions.begin(), E = Regions.end(); I != E; I++)
+    state = getSymbolManager().notifyBind(state, *I);
   return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
                                                       Explicits, Regions, Call);
 }

   }
 
   const StackFrameContext *SFC = LC ? LC->getCurrentStackFrame() : nullptr;
-  SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
+  SymbolReaper SymReaper(SFC, ReferenceStmt, CleanedState);
 
   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
 

lib/StaticAnalyzer/Core/ProgramState.cpp

   assert(NewState);
   return NewState;
 }
+
+/// The GDM component containing symbols that were invalidated by direct
+/// binding to their regions
+REGISTER_TRAIT_WITH_PROGRAMSTATE(OverwrittenSymbols,
+                                 llvm::ImmutableSet<SymbolRef>)
+
+ProgramStateRef ProgramState::setDead(SymbolRef Sym) const {
+  return add<OverwrittenSymbols>(Sym);
+}
+
+bool ProgramState::isDead(SymbolRef Sym) const {
+  return contains<OverwrittenSymbols>(Sym);
+}

lib/StaticAnalyzer/Core/SymbolManager.cpp

 //===----------------------------------------------------------------------===//
 
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"

   return cast<SymSymExpr>(data);
 }
 
+ProgramStateRef SymbolManager::notifyBind(ProgramStateRef state,
+                                          const MemRegion *MR) {
+  if (const TypedValueRegion* R = dyn_cast<TypedValueRegion>(MR)) {
+    llvm::FoldingSetNodeID profile;
+    SymbolRegionValue::Profile(profile, R);
+    void *InsertPos;
+    if (SymExpr *Sym = DataSet.FindNodeOrInsertPos(profile, InsertPos))
+      return state->setDead(Sym);
+  }
+  return state;
+}
+
 QualType SymbolConjured::getType() const {
   return T;
 }

   return I->second;
 }
 
+SymbolReaper::SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
+                           ProgramStateRef currentState)
+ : LCtx(Ctx), Loc(s), state(currentState), SymMgr(state->getSymbolManager()),
+   reapedStore(nullptr, state->getStateManager().getStoreManager()) {}
+
+
 void SymbolReaper::markDependentsLive(SymbolRef sym) {
   // Do not mark dependents more then once.
   SymbolMapTy::iterator LI = TheLiving.find(sym);

   bool KnownLive;
   
   switch (sym->getKind()) {
-  case SymExpr::RegionValueKind:
-    KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion());
+  case SymExpr::RegionValueKind: {
+    const SymbolRegionValue *SRV = cast<SymbolRegionValue>(sym);
+    KnownLive = isLiveRegion(SRV->getRegion()) && !state->isDead(sym);
     break;
+  }
   case SymExpr::ConjuredKind:
     KnownLive = false;
     break;