martong added a comment. I've made some measurements with the diff down below. So, it seems like the chance of being a recursive call is very unlikely (roughly 1/10000). Thus I am going to update this condition with `LLVM_UNLIKELY`. Besides, the depth of the call stack seems to be less than 4 in the majority of cases (99.98%). However, there are edge cases (ffmpeg) when the depth is even bigger than 16. Consequently, a `SmallPtrSet` with 4 as the small buffer size would be better than the `SmallVector`.
Attached the csa-testbanch results. F23289845: stats.html <https://reviews.llvm.org/F23289845> Plus, attached a summarizing excel sheet about the assume stack depth (courtesy of @steakhal). F23289850: assume-stack-depths.xlsx <https://reviews.llvm.org/F23289850> diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h index f1b75a57115b..097d0ff8d162 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h @@ -153,6 +153,7 @@ protected: bool contains(const ProgramState *S) const { return llvm::find(Aux, S) != Aux.end(); } + size_t size() { return Aux.size(); } private: llvm::SmallVector<const ProgramState *, 4> Aux; diff --git a/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp b/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp index 0866d3d0db74..11bbda9dd899 100644 --- a/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp +++ b/clang/lib/StaticAnalyzer/Core/ConstraintManager.cpp @@ -17,10 +17,25 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/ScopeExit.h" +#include "llvm/ADT/Statistic.h" using namespace clang; using namespace ento; +#define DEBUG_TYPE "CoreEngine" + +STATISTIC(NumAssume, "The # of assume calls"); +STATISTIC(NumAssumeRecurse, "The # of recursive assume calls"); +STATISTIC(AssumeStackSize01, "The # of assume stack size between 0 and 1"); +STATISTIC(AssumeStackSize23, "The # of assume stack size between 2 and 3"); +STATISTIC(AssumeStackSize45, "The # of assume stack size between 4 and 5"); +STATISTIC(AssumeStackSize67, "The # of assume stack size between 6 and 7"); +STATISTIC(AssumeStackSize89, "The # of assume stack size between 8 and 9"); +STATISTIC(AssumeStackSize1011, "The # of assume stack size between 10 and 11"); +STATISTIC(AssumeStackSize1213, "The # of assume stack size between 12 and 13"); +STATISTIC(AssumeStackSize1415, "The # of assume stack size between 14 and 15"); +STATISTIC(AssumeStackSize16XX, "The # of assume stack size greater equal than 16"); + ConstraintManager::~ConstraintManager() = default; static DefinedSVal getLocFromSymbol(const ProgramStateRef &State, @@ -53,9 +68,30 @@ ConstraintManager::assumeDualImpl(ProgramStateRef &State, // fixpoint. // We avoid infinite recursion of assume calls by checking already visited // States on the stack of assume function calls. + ++NumAssume; + if (AssumeStack.size() < 2) + ++AssumeStackSize01; + else if (AssumeStack.size() < 4) + ++AssumeStackSize23; + else if (AssumeStack.size() < 6) + ++AssumeStackSize45; + else if (AssumeStack.size() < 8) + ++AssumeStackSize67; + else if (AssumeStack.size() < 10) + ++AssumeStackSize89; + else if (AssumeStack.size() < 12) + ++AssumeStackSize1011; + else if (AssumeStack.size() < 14) + ++AssumeStackSize1213; + else if (AssumeStack.size() < 16) + ++AssumeStackSize1415; + else + ++AssumeStackSize16XX; const ProgramState *RawSt = State.get(); - if (AssumeStack.contains(RawSt)) + if (AssumeStack.contains(RawSt)) { + ++NumAssumeRecurse; return {State, State}; + } AssumeStack.push(RawSt); auto AssumeStackBuilder = llvm::make_scope_exit([this]() { AssumeStack.pop(); }); Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D126560/new/ https://reviews.llvm.org/D126560 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
