Index: include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
===================================================================
--- include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
@@ -29,6 +29,7 @@
 /// the program.
 class SymExpr : public llvm::FoldingSetNode {
   virtual void anchor();
+  mutable unsigned Complexity = 0;
 
 public:
   enum Kind {
@@ -85,7 +86,7 @@
   symbol_iterator symbol_begin() const { return symbol_iterator(this); }
   static symbol_iterator symbol_end() { return symbol_iterator(); }
 
-  unsigned computeComplexity() const;
+  virtual unsigned computeComplexity() const;
 
   /// Find the region from which this symbol originates.
   ///
@@ -127,6 +128,10 @@
 
   SymbolID getSymbolID() const { return Sym; }
 
+  unsigned computeComplexity() const override {
+    return 1;
+  };
+
   // Implement isa<T> support.
   static inline bool classof(const SymExpr *SE) {
     Kind k = SE->getKind();
Index: lib/StaticAnalyzer/Core/SymbolManager.cpp
===================================================================
--- lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -160,10 +160,12 @@
 }
 
 unsigned SymExpr::computeComplexity() const {
-  unsigned R = 0;
-  for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I)
-    R++;
-  return R;
+  if (Complexity == 0) {
+    for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I)
+      ++Complexity;
+  }
+
+  return Complexity;
 }
 
 const SymbolRegionValue*