[analyzer] Memoize complexity of SymExpr

[mikhail.ramalho]

Summary

This patch introduces a new member to SymExpr, which stores the symbol complexity, avoiding recalculating it every time computeComplexity() is called.

Also, increase the complexity of conjured Symbols by one, so it's clear that it has a greater complexity than its underlying symbols.

[NoQ]

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

97–100

I'd much rather return 1 here. There's nothing to iterate through in SymbolConjured or generally in SymbolData, those are pretty much atomic.

[mikhail.ramalho]

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

97–100

Right, should I move it to SymbolData then?

[mikhail.ramalho]

Don't iterate though SymbolData's symbol as they're atomic.

[NoQ]

lib/StaticAnalyzer/Core/SymbolManager.cpp

161–162

Why not just sum up the complexity of direct sub-symbols? That'd be a bit more code (you'll need to override the function for SymIntExpr, IntSymExpr, SymSymExpr, SymbolCast), but it sounds a lot more efficient.

[mikhail.ramalho]

lib/StaticAnalyzer/Core/SymbolManager.cpp

161–162

Sure, I'll move this code to SymbolCast::computeComplexity() and BinarySymExpr::computeComplexity(), and check if it's faster.

[NoQ]

lib/StaticAnalyzer/Core/SymbolManager.cpp

161–162

Like, i mean, recursion instead of iterators.

[mikhail.ramalho]

Update how to calculate complexity.

[mikhail.ramalho]

Is that what you suggested, @NoQ?

This version seems to be 1% faster compared to the other one.

[NoQ]

unsigned SymSymExpr::computeComplexity() {
  if (Complexity == 0)
    Complexity = LHS->computeComplexity() + RHS->computeComplexity();
  return Complexity;
}

etc.

Because symbol_iterator iterates over all sub-symbols, while we're only interested in direct sub-symbols as recursion takes care of the rest.

[mikhail.ramalho]

Updated complexity calculation by getting the complexity of sub-symbols + 1 (for the current wrapper).

[NoQ]

Yeah, that's what i expected to work. Now the trick, of course, would be to avoid infinite recursion :P

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

435

I don't thing this "1" thing is necessary in this specific case. We'll anyway have a bigger complexity than that of each operand.

[mikhail.ramalho]

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

435

But the idea is that wrappers always increase the complexity by 1, right? That's why I left it there.

[NoQ]

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

435

That's not much of an idea, all we need is to make sure that bigger symbols have larger complexity, so that we couldn't construct arbitrarily long symbolic expressions of complexity 1, which doesn't require any extra effort here.

[george.karpenkov]

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

435

i'm happy either way, both approaches make sense.

[mikhail.ramalho]

I just tried without the +1 and there's a regression:

error: 'warning' diagnostics expected but not seen: 
  File /home/mramalho/llvm/tools/clang/test/Analysis/taint-generic.c Line 268: Division by a tainted value, possibly zero
1 error generated.

which is strange, as removing the +1 actually decreases the complexity so it's not like the expression is being discarded.

[NoQ]

Curious. Might there be an overflow?

[george.karpenkov]

@NoQ I think the analyzer would hang if we construct an expression with a complexity of 2^32

[mikhail.ramalho]

The complexity values are still quite small and, without the +1, a lot more expressions are below the 25 threshold.

[NoQ]

In D49232#1165540, @mikhail.ramalho wrote:

The complexity values are still quite small and, without the +1, a lot more expressions are below the 25 threshold.

Yeah, i guess it's just about yielding the exact same values as the old algorithm. The regression disappears when i bump the limit from 25 to 33.

I'd suggest to remove the +1 and speculatively bump the limit to, say, 35, without spending much time evaluating the exact number; would that be scary?

[mikhail.ramalho]

In D49232#1165864, @NoQ wrote:

In D49232#1165540, @mikhail.ramalho wrote:

The complexity values are still quite small and, without the +1, a lot more expressions are below the 25 threshold.

Yeah, i guess it's just about yielding the exact same values as the old algorithm. The regression disappears when i bump the limit from 25 to 33.

I'd suggest to remove the +1 and speculatively bump the limit to, say, 35, without spending much time evaluating the exact number; would that be scary?

Sounds good to me.

[mikhail.ramalho]

Bumped the max symbol complexity threshold to 35.

[NoQ]

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

273

Before i forget: these also need an override to satisfy our -Werror buildbots.

[NoQ]

LGTM otherwise!

[mikhail.ramalho]

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

273

Oh, thanks! I missed those.

[mikhail.ramalho]

Added missing overrides.

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

protected:
   SymExpr(Kind k) : K(k) {}
 
   static bool isValidTypeForSymbol(QualType T) {
     // FIXME: Depending on whether we choose to deprecate structural symbols,
     // this may become much stricter.
     return !T.isNull() && !T->isVoidType();
   }
 
+  mutable unsigned Complexity = 0;
+
 public:
   virtual ~SymExpr() = default;
 
   Kind getKind() const { return K; }
 
   virtual void dump() const;
 
   virtual void dumpToStream(raw_ostream &os) const {}
public:
 
     bool operator==(const symbol_iterator &X) const;
     bool operator!=(const symbol_iterator &X) const;
   };
 
   symbol_iterator symbol_begin() const { return symbol_iterator(this); }
   static symbol_iterator symbol_end() { return symbol_iterator(); }
 
-  unsigned computeComplexity() const;
+  virtual unsigned computeComplexity() const = 0;
 
   /// Find the region from which this symbol originates.
   ///
   /// Whenever the symbol was constructed to denote an unknown value of
   /// a certain memory region, return this region. This method
   /// allows checkers to make decisions depending on the origin of the symbol.
   /// Symbol classes for which the origin region is known include
   /// SymbolRegionValue which denotes the value of the region before
SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
     assert(classof(this));
   }
 
 public:
   ~SymbolData() override = default;
 
   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();
     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
   }
 };
 
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H

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

SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
     // that was caused by a destructor call on a temporary object,
     // which has no statement associated with it.
     // Due to this, we might be creating the same invalidation symbol for
     // two different invalidation passes (for two different temporaries).
     assert(lctx);
     assert(isValidTypeForSymbol(t));
   }
 
   const Stmt *getStmt() const { return S; }
   unsigned getCount() const { return Count; }
   const void *getTag() const { return SymbolTag; }
 
   QualType getType() const override;
 
   void dumpToStream(raw_ostream &os) const override;
 
   static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
                       QualType T, unsigned Count, const LocationContext *LCtx,
                       const void *SymbolTag) {
     profile.AddInteger((unsigned) SymbolConjuredKind);
public:
   SymbolCast(const SymExpr *In, QualType From, QualType To)
       : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) {
     assert(In);
     assert(isValidTypeForSymbol(From));
     // FIXME: GenericTaintChecker creates symbols of void type.
     // Otherwise, 'To' should also be a valid type.
   }
 
+  unsigned computeComplexity() const {
+    if (Complexity == 0)
+      Complexity = 1 + Operand->computeComplexity();
+    return Complexity;
+  }
+
   QualType getType() const override { return ToTy; }
 
   const SymExpr *getOperand() const { return Operand; }
 
   void dumpToStream(raw_ostream &os) const override;
 
   static void Profile(llvm::FoldingSetNodeID& ID,
                       const SymExpr *In, QualType From, QualType To) {
SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
     assert(lhs);
   }
 
   void dumpToStream(raw_ostream &os) const override;
 
   const SymExpr *getLHS() const { return LHS; }
   const llvm::APSInt &getRHS() const { return RHS; }
 
+  unsigned computeComplexity() const {
+    if (Complexity == 0)
+      Complexity = 1 + LHS->computeComplexity();
+    return Complexity;
+  }
+
   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
                       BinaryOperator::Opcode op, const llvm::APSInt& rhs,
                       QualType t) {
     ID.AddInteger((unsigned) SymIntExprKind);
     ID.AddPointer(lhs);
     ID.AddInteger(op);
     ID.AddPointer(&rhs);
     ID.Add(t);
IntSymExpr(const llvm::APSInt &lhs, BinaryOperator::Opcode op,
     assert(rhs);
   }
 
   void dumpToStream(raw_ostream &os) const override;
 
   const SymExpr *getRHS() const { return RHS; }
   const llvm::APSInt &getLHS() const { return LHS; }
 
+  unsigned computeComplexity() const {
+    if (Complexity == 0)
+      Complexity = 1 + RHS->computeComplexity();
+    return Complexity;
+  }
+
   static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
                       BinaryOperator::Opcode op, const SymExpr *rhs,
                       QualType t) {
     ID.AddInteger((unsigned) IntSymExprKind);
     ID.AddPointer(&lhs);
     ID.AddInteger(op);
     ID.AddPointer(rhs);
     ID.Add(t);
SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
     assert(rhs);
   }
 
   const SymExpr *getLHS() const { return LHS; }
   const SymExpr *getRHS() const { return RHS; }
 
   void dumpToStream(raw_ostream &os) const override;
 
+  unsigned computeComplexity() const {
+    if (Complexity == 0)
+      Complexity = 1 + RHS->computeComplexity() + LHS->computeComplexity();
+    return Complexity;
+  }
+
   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
                     BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
     ID.AddInteger((unsigned) SymSymExprKind);
     ID.AddPointer(lhs);
     ID.AddInteger(op);
     ID.AddPointer(rhs);
     ID.Add(t);
   }

lib/StaticAnalyzer/Core/SymbolManager.cpp

case SymExpr::SymSymExprKind: {
       const auto *x = cast<SymSymExpr>(SE);
       itr.push_back(x->getLHS());
       itr.push_back(x->getRHS());
       return;
     }
   }
   llvm_unreachable("unhandled expansion case");
 }
 
-unsigned SymExpr::computeComplexity() const {
-  unsigned R = 0;
-  for (symbol_iterator I = symbol_begin(), E = symbol_end(); I != E; ++I)
-    R++;
-  return R;
-}
-
 const SymbolRegionValue*
 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
   llvm::FoldingSetNodeID profile;
   SymbolRegionValue::Profile(profile, R);
   void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
     new (SD) SymbolRegionValue(SymbolCounter, R);