[analyzer] Don't clean up dead symbols from constraints twice.

[NoQ]

Summary

A solid 2% analysis speed improvement! Not really - such amounts are barely measurable. Unless?...

But, i mean, everybody knows that dead symbol elimination is the biggest performance bottleneck, so many people tried to improve it, how come nobody noticed this bug before?

[NoQ]

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

750–752

Note: the second invocation is here.

[NoQ]

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

763–764

Note: The results of the first invocation are discarded here, as the updated state is getting frankensteined by attaching ExprEngine's environment and store to checker's GDM, while range constraints also reside in the GDM.

[NoQ]

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

763–764

This whole frankensteining process is kinda necessary because SymbolReaper needs to be populated with the data from the Environment and the Store. I.e., they're supposed to issue their markLive() calls, otherwise we wouldn't be able to properly judge whether something is live in checkDeadSymbols; but at the same time the intent is to provide the uncleaned state to the callback, so that the checkers had access to full information about the dying symbol.

I'm not sure whether any checkers actually take advantage of such information, but the intent to provide this information looks valid, so i don't plan to undo this decision.

[xazax.hun]

Nice catch! I wonder if there is a case where the original code is less wasteful, e.g. the majority of the symbols are dead and a lot of checks splitting the execution. But this sounds very unlikely.

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

public:
   }
 
   CallEventManager &getCallEventManager() { return *CallEventMgr; }
 
   StoreManager &getStoreManager() { return *StoreMgr; }
   ConstraintManager &getConstraintManager() { return *ConstraintMgr; }
   SubEngine &getOwningEngine() { return *Eng; }
 
-  ProgramStateRef removeDeadBindings(ProgramStateRef St,
+  ProgramStateRef
+  removeDeadBindingsFromEnvironmentAndStore(ProgramStateRef St,
                                             const StackFrameContext *LCtx,
-                                    SymbolReaper& SymReaper);
+                                            SymbolReaper &SymReaper);
 
 public:
 
   SVal ArrayToPointer(Loc Array, QualType ElementTy) {
     return StoreMgr->ArrayToPointer(Array, ElementTy);
   }
 
   // Methods that manipulate the GDM.

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

if (const MemRegion *MR = I.second.getAsRegion())
       SymReaper.markLive(MR);
   }
 
   getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
 
   // 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);
+  CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
+      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");
   // 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);
 
     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();
 

clang/lib/StaticAnalyzer/Core/ProgramState.cpp

 
 
 ProgramStateManager::~ProgramStateManager() {
   for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
        I!=E; ++I)
     I->second.second(I->second.first);
 }
 
-ProgramStateRef
-ProgramStateManager::removeDeadBindings(ProgramStateRef state,
-                                   const StackFrameContext *LCtx,
-                                   SymbolReaper& SymReaper) {
+ProgramStateRef ProgramStateManager::removeDeadBindingsFromEnvironmentAndStore(
+    ProgramStateRef state, const StackFrameContext *LCtx,
+    SymbolReaper &SymReaper) {
 
   // This code essentially performs a "mark-and-sweep" of the VariableBindings.
   // The roots are any Block-level exprs and Decls that our liveness algorithm
   // tells us are live.  We then see what Decls they may reference, and keep
   // those around.  This code more than likely can be made faster, and the
   // frequency of which this method is called should be experimented with
   // for optimum performance.
   ProgramState NewState = *state;
 
   NewState.Env = EnvMgr.removeDeadBindings(NewState.Env, SymReaper, state);
 
   // Clean up the store.
   StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
                                                    SymReaper);
   NewState.setStore(newStore);
   SymReaper.setReapedStore(newStore);
 
-  ProgramStateRef Result = getPersistentState(NewState);
-  return ConstraintMgr->removeDeadBindings(Result, SymReaper);
+  return getPersistentState(NewState);
 }
 
 ProgramStateRef ProgramState::bindLoc(Loc LV,
                                       SVal V,
                                       const LocationContext *LCtx,
                                       bool notifyChanges) const {
   ProgramStateManager &Mgr = getStateManager();
   ProgramStateRef newState = makeWithStore(Mgr.StoreMgr->Bind(getStore(),