[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 ↗

(On Diff #155158)

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 ↗

(On Diff #155158)

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–168

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–168

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–168

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 ↗

(On Diff #155912)

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 ↗

(On Diff #155912)

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 ↗

(On Diff #155912)

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 ↗

(On Diff #155912)

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 ↗

(On Diff #156030)

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 ↗

(On Diff #156030)

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
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

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);