[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

163–169

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

163–169

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

[NoQ]

lib/StaticAnalyzer/Core/SymbolManager.cpp

163–169

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

421

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

421

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

421

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

421

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

277

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

277

Oh, thanks! I missed those.

[mikhail.ramalho]

Added missing overrides.

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

 namespace ento {
 
 class MemRegion;
 
 /// Symbolic value. These values used to capture symbolic execution of
 /// the program.
 class SymExpr : public llvm::FoldingSetNode {
   virtual void anchor();
+  mutable unsigned Complexity = 0;
 
 public:
   enum Kind {
 #define SYMBOL(Id, Parent) Id##Kind,
 #define SYMBOL_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
   };
 
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;
 
   /// 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

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));
   }
 
+  unsigned computeComplexity() const override {
+    return 1 + SymExpr::computeComplexity();
+  };
+
   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;
 
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.
   }
 
   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) {
     ID.AddInteger((unsigned) SymbolCastKind);
public:
 
   const SymExpr *getLHS() const { return LHS; }
   const SymExpr *getRHS() const { return RHS; }
 
   void dumpToStream(raw_ostream &os) const override;
 
   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);
   }
 
   void Profile(llvm::FoldingSetNodeID& ID) override {
     Profile(ID, LHS, getOpcode(), RHS, getType());

lib/StaticAnalyzer/Core/SymbolManager.cpp

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