[analyzer] Improve simplifySVal performance further.

[NoQ]

Summary

Memoize SValBuilder::simplifySVal() so that it didn't try to re-simplify the same symbolic expression in the same program state.

Speeds up the analysis by ~25% on the artificial test in test/Analysis/hangs.c.

The test is still exponentially exploding though.

[george.karpenkov]

@NoQ we should make sure the memory is not exploding and that we don't make the analyzer slower in other cases. Though we could commit this, and then let CI figure out potential regressions.

[NoQ]

The remaining slowness is in removeDead(). It's going to be fun to optimize. Some parts of it are already memoized (eg. the live set in SymbolReaper).

Memory usage on the artificial test seems stable.

lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp

SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
   // For now, this function tries to constant-fold symbols inside a
   // nonloc::SymbolVal, and does nothing else. More simplifications should
   // be possible, such as constant-folding an index in an ElementRegion.
 
   class Simplifier : public FullSValVisitor<Simplifier, SVal> {
     ProgramStateRef State;
     SValBuilder &SVB;
 
+    // Cache results for the lifetime of the Simplifier. Results change every
+    // time new constraints are added to the program state, which is the whole
+    // point of simplifying, and for that very reason it's pointless to maintain
+    // the same cache for the duration of the whole analysis.
+    llvm::DenseMap<SymbolRef, SVal> Cached;
+
     static bool isUnchanged(SymbolRef Sym, SVal Val) {
       return Sym == Val.getAsSymbol();
     }
 
   public:
     Simplifier(ProgramStateRef State)
         : State(State), SVB(State->getStateManager().getSValBuilder()) {}
 
     SVal VisitSymbolData(const SymbolData *S) {
       if (const llvm::APSInt *I =
               SVB.getKnownValue(State, nonloc::SymbolVal(S)))
         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
                                             : (SVal)SVB.makeIntVal(*I);
       return SVB.makeSymbolVal(S);
     }
 
     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
     // start producing them.
 
     SVal VisitSymIntExpr(const SymIntExpr *S) {
+      auto I = Cached.find(S);
+      if (I != Cached.end())
+        return I->second;
+
       SVal LHS = Visit(S->getLHS());
-      if (isUnchanged(S->getLHS(), LHS))
-        return SVB.makeSymbolVal(S);
+      if (isUnchanged(S->getLHS(), LHS)) {
+        SVal V = SVB.makeSymbolVal(S);
+        Cached[S] = V;
+        return V;
+      }
       SVal RHS;
       // By looking at the APSInt in the right-hand side of S, we cannot
       // figure out if it should be treated as a Loc or as a NonLoc.
       // So make our guess by recalling that we cannot multiply pointers
       // or compare a pointer to an integer.
       if (Loc::isLocType(S->getLHS()->getType()) &&
           BinaryOperator::isComparisonOp(S->getOpcode())) {
         // The usual conversion of $sym to &SymRegion{$sym}, as they have
         // the same meaning for Loc-type symbols, but the latter form
         // is preferred in SVal computations for being Loc itself.
         if (SymbolRef Sym = LHS.getAsSymbol()) {
           assert(Loc::isLocType(Sym->getType()));
           LHS = SVB.makeLoc(Sym);
         }
         RHS = SVB.makeIntLocVal(S->getRHS());
       } else {
         RHS = SVB.makeIntVal(S->getRHS());
       }
-      return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
+
+      SVal V = SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
+      Cached[S] = V;
+      return V;
     }
 
     SVal VisitSymSymExpr(const SymSymExpr *S) {
+      auto I = Cached.find(S);
+      if (I != Cached.end())
+        return I->second;
+
       SVal LHS = Visit(S->getLHS());
       SVal RHS = Visit(S->getRHS());
-      if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))
-        return SVB.makeSymbolVal(S);
-      return SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
+      if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS)) {
+        SVal V = SVB.makeSymbolVal(S);
+        Cached[S] = V;
+        return V;
+      }
+      SVal V = SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType());
+      Cached[S] = V;
+      return V;
     }
 
     SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
 
     SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
 
     SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
       // Simplification is much more costly than computing complexity.