[analyzer] Improve simplifySVal performance.

[NoQ]

Summary

Reported by Mikael Holmén on http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20180416/225349.html - a combination of rC329780 and rC300178 caused a performance regression that seemed to be a hang on the attached test case.

Reducing even further from 20 to 10 gives a ~15% further speed boost on the test, but i don't think it's worth it because such code is not common and therefore accuracy is more important.

[NoQ]

@mikhail.ramalho Does it solve your problems with ffmpeg as well? :)

[george.karpenkov]

@NoQ I'm really wary of magic numbers.

• We should expose it through an analyzer-config flag. We already do so for the budget.
• We should probably have both positive and negative tests. What scenarios _stop_ working after the threshold is decreased? [point 1 is required to be able to test that]
• Finally, do we understand where the slowdown comes from? If it comes from attempted rearrangements due to https://reviews.llvm.org/rC329780 I think we should roll that back instead.

[george.karpenkov]

Also we should make sure that all recursive transformations on expressions represented as DAGs should be memoized.

[baloghadamsoftware]

Hello! Thank you for addressing this problem. Are these kinds of symbols common in real code? For me it seems very artificial. However, I agree with George, it would be better to have this value as an analyzer option with a default value (of 20).

[NoQ]

Optimize simplifySVal() instead of reducing the threshold.

I'll address the memoization separately.

[NoQ]

I only essentially did one optimization - introduce a short path that returns the original value if visiting its sub-values changed nothing, which is a relatively common case. The reason it works though is that evalBinOp() will be called later to combine the sub-values, which may in turn call simplifySVal() again, which is clearly unwanted.

test/Analysis/hangs.c

18–30 ↗

(On Diff #148681)

This currently finishes in 1 second on my machine. This test, unlike the original test, is easy to experiment with.

[NoQ]

Add an explicit brute-force protection against re-entering simplifySVal(). Remove the threshold completely.

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

public:
   Loc makeLoc(const AddrLabelExpr *expr) {
     return loc::GotoLabel(expr->getLabel());
   }
 
   Loc makeLoc(const llvm::APSInt& integer) {
     return loc::ConcreteInt(BasicVals.getValue(integer));
   }
 
+  /// Make an SVal that represents the given symbol. This follows the convention
+  /// of representing Loc-type symbols (symbolic pointers and references)
+  /// as Loc values wrapping the symbol rather than as plain symbol values.
+  SVal makeSymbolVal(SymbolRef Sym) {
+    if (Loc::isLocType(Sym->getType()))
+      return makeLoc(Sym);
+    return nonloc::SymbolVal(Sym);
+  }
+
   /// Return a memory region for the 'this' object reference.
   loc::MemRegionVal getCXXThis(const CXXMethodDecl *D,
                                const StackFrameContext *SFC);
 
   /// Return a memory region for the 'this' object reference.
   loc::MemRegionVal getCXXThis(const CXXRecordDecl *D,
                                const StackFrameContext *SFC);
 };

cfe/trunk/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;
 
+    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 Loc::isLocType(S->getType()) ? (SVal)SVB.makeLoc(S) 
-                                          : nonloc::SymbolVal(S);
+      return SVB.makeSymbolVal(S);
     }
 
     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
     // start producing them.
 
     SVal VisitSymIntExpr(const SymIntExpr *S) {
       SVal LHS = Visit(S->getLHS());
+      if (isUnchanged(S->getLHS(), LHS))
+        return SVB.makeSymbolVal(S);
       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 VisitSymSymExpr(const SymSymExpr *S) {
       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());
     }
 
     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.
       // For high complexity, it may be not worth it.
-      if (V.getSymbol()->computeComplexity() > 100)
-        return V;
       return Visit(V.getSymbol());
     }
 
     SVal VisitSVal(SVal V) { return V; }
   };
 
-  return Simplifier(State).Visit(V);
+  // A crude way of preventing this function from calling itself from evalBinOp.
+  static bool isReentering = false;
+  if (isReentering)
+    return V;
+
+  isReentering = true;
+  SVal SimplifiedV = Simplifier(State).Visit(V);
+  isReentering = false;
+
+  return SimplifiedV;
 }

cfe/trunk/test/Analysis/hangs.c

+// RUN: %clang_analyze_cc1 -analyzer-checker core -verify %s
+
+// expected-no-diagnostics
+
+// Stuff that used to hang.
+
+int g();
+
+int f(int y) {
+  return y + g();
+}
+
+int produce_a_very_large_symbol(int x) {
+  return f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(
+             f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(x))))))))))))))))))))))))))))))));
+}
+
+void produce_an_exponentially_exploding_symbol(int x, int y) {
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+  x += y; y += x + g();
+}