[clang][dataflow] Exclude protobuf types from modeling in the environment.

[ymandel]

Summary

Google's protobufs are often quite large and their internal state is never worth
modeling in the environment. Exclude them during value construction.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

635

Not sure how often is this invoked but we could reduce the number of string comparisons by caching the identifier ptr and do a pointer comparison.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

635

Good question. It means an extra comparison for each type until the pointer is cached (to check if the cache is set) and then, afterwards, 2 comparisons vs ~10 for the common case where the class name is doesn't match. In the matching case, though, it is clearly saving much more.

For proto-heavy code, it seems a win, and a loss otherwise. But, the question is where to put the cache. It seems to me best to move this to be a method on DataflowAnalysisContext (since it is a global, not local env, property) and make the cached pointer a private member of DAC.

Thoughts?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

635

I think it might be nice to have a context that is scoped to the translation unit rather than a function. We might have other stuff that we want to cache here.

An example how the static analyzer is dealing with this: https://github.com/llvm/llvm-project/blob/main/clang/lib/StaticAnalyzer/Checkers/StdLibraryFunctionsChecker.cpp#L960

In case we do not want to be lazy and willing to populate the cache eagerly at the beginning of the analysis, we would not pay for the extra checks to see if the cache is populated.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

635

I'm also fine with not doing caching for now and having a note to consider this in the future if it becomes measurable in the profiles. It is probably fine for now when we only have a couple of short strings to compare. But I guess the number of special cases we handle this way will only increase in the future.

[ymandel]

added FIXME

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

635

I'm also fine with not doing caching for now and having a note to consider this in the future if it becomes measurable in the profiles. It is probably fine for now when we only have a couple of short strings to compare. But I guess the number of special cases we handle this way will only increase in the future.

(sorry for the very long delay in responding). I think holding off on the cache may be best for now, pending performance analysis. I'm hesitant to put too much effort in to optimizing this, because ultimately we want to move to a lazy-initialization model which would obviate the need for this kind of optimization, because we would only model the fields that are used, making the size of the underlying struct irrelevant.

I've added a FIXME to this effect.

[ymandel]

Ping... Gabor, Stanislav: what are your thoughts on this patch? I think we're in a place where I could do performance comparisons before/after if you think that's justified.

Alternatively, I have a relatively simple proposal for lazy initialization that I expect I will implement in the next couple of months. If you're sufficiently concerned with this patch, waiting for that patch is an option as well.

[xazax.hun]

Since there are many moving pieces and the whole framework is experimental without many users, I'm fine with landing this as is as long we are tracking the improvement opportunities (tickets or fixemes).

[ymandel]

Reviving this patch, addressing some of the earlier concerns. However, I may have a better solution which makes this patch irrelevant. So, still WIP.

[ymandel]

Abandoning in favor of https://reviews.llvm.org/D140694.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

 
 /// Returns the set of all fields in the type.
 llvm::DenseSet<const FieldDecl *> getObjectFields(QualType Type);
 
 /// Owns objects that encompass the state of a program and stores context that
 /// is used during dataflow analysis.
 class DataflowAnalysisContext {
 public:
+  struct Options {
+    // FIXME: add comments and change to std::vector<string>
+    bool ExcludeGoogleProtobufs;
+  };
+
   /// Constructs a dataflow analysis context.
   ///
   /// Requirements:
   ///
   ///  `S` must not be null.
-  DataflowAnalysisContext(std::unique_ptr<Solver> S)
+  DataflowAnalysisContext(std::unique_ptr<Solver> S,
+                          Options Opts = {/*ExcludeGoogleProtobufs=*/false})
       : S(std::move(S)), TrueVal(createAtomicBoolValue()),
-        FalseVal(createAtomicBoolValue()) {
+        FalseVal(createAtomicBoolValue()), Options(Opts) {
     assert(this->S != nullptr);
   }
 
   /// Takes ownership of `Loc` and returns a reference to it.
   ///
   /// Requirements:
   ///
   ///  `Loc` must not be null.
public:
   bool equivalentBoolValues(BoolValue &Val1, BoolValue &Val2);
 
   LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token);
 
   /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise,
   /// returns null.
   const ControlFlowContext *getControlFlowContext(const FunctionDecl *F);
 
+  bool isExcludedRecordType(const RecordType &Ty);
+
 private:
   struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> {
     static QualType getEmptyKey() {
       // Allow a NULL `QualType` by using a different value as the empty key.
       return QualType::getFromOpaquePtr(reinterpret_cast<Type *>(1));
     }
 
     using DenseMapInfo::getHashValue;
private:
   // creating a type-independent `NullPointerValue` without a `PointeeLoc`
   // field.
   llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>
       NullPointerVals;
 
   AtomicBoolValue &TrueVal;
   AtomicBoolValue &FalseVal;
 
+  Options Options;
+
   // Indices that are used to avoid recreating the same composite boolean
   // values.
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
       ConjunctionVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *>
       DisjunctionVals;
   llvm::DenseMap<BoolValue *, NegationValue *> NegationVals;
   llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ImplicationValue *>
private:
   // Flow conditions depend on other flow conditions if they are created using
   // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
   // dependencies is stored in the `FlowConditionDeps` map.
   llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>>
       FlowConditionDeps;
   llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionConstraints;
 
   llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts;
+
+  const RecordType *ProtobufBaseTy = nullptr;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

if (Stmt *Body = F->getBody()) {
     assert(CFCtx);
     auto Result = FunctionContexts.insert({F, std::move(*CFCtx)});
     return &Result.first->second;
   }
 
   return nullptr;
 }
 
+// Hard code certain types to exclude from modeling. Currently, we limit to
+// Google protobufs, since they can be very large, and have no value in
+// modeling.
+//
+// FIXME: Remove this specialized exclusion once a more general mechanism is
+// implemented for only modeling accessed fields. Otherwise, consider memoizing
+// this function or caching some of the information on which it relies (like the
+// protobuf `Message` base type) at the TU level.
+bool DataflowAnalysisContext::isExcludedRecordType(const RecordType &Ty) {
+  if (!Options.ExcludeGoogleProtobufs)
+    return false;
+
+  const auto *CD = dyn_cast<CXXRecordDecl>(Ty.getDecl());
+  if (CD == nullptr || !CD->hasDefinition() || CD->getNumBases() != 1)
+    return false;
+
+  QualType BQ = CD->bases_begin()->getType();
+  if (BQ.isNull())
+    return false;
+
+  const RecordType *BaseTy = BQ->getAs<RecordType>();
+  if (BaseTy == nullptr)
+    return false;
+
+  if (ProtobufBaseTy != nullptr)
+    return BaseTy == ProtobufBaseTy;
+
+  const RecordDecl *RD = BaseTy->getDecl();
+  assert(RD != nullptr);
+  IdentifierInfo *II = RD->getIdentifier();
+  if (II == nullptr || !II->isStr("Message"))
+    return false;
+
+  const auto *ND = dyn_cast<NamespaceDecl>(RD->getDeclContext());
+  if (ND == nullptr)
+    return false;
+  IdentifierInfo *NamespaceII = ND->getIdentifier();
+  if (NamespaceII == nullptr)
+    return false;
+  if (NamespaceII->isStr("proto2")) {
+    ProtobufBaseTy = BaseTy;
+    return true;
+  }
+
+  // Check for `::google::protobuf`:
+  if (!NamespaceII->isStr("protobuf"))
+    return false;
+
+  ND = dyn_cast<NamespaceDecl>(ND->getDeclContext());
+  if (ND == nullptr || !ND->getParent()->isTranslationUnit())
+    return false;
+  NamespaceII = ND->getIdentifier();
+  if (NamespaceII != nullptr && NamespaceII->isStr("google")) {
+    ProtobufBaseTy = BaseTy;
+    return true;
+  }
+
+  return false;
+}
+
 } // namespace dataflow
 } // namespace clang
 
 using namespace clang;
 
 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
   const Expr *Current = &E;
   if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

Value *Environment::createValueUnlessSelfReferential(
 
   if (Type->isBooleanType()) {
     CreatedValuesCount++;
     return &makeAtomicBoolValue();
   }
 
   if (Type->isIntegerType()) {
     // FIXME: consider instead `return nullptr`, given that we do nothing useful
     // with integers, and so distinguishing them serves no purpose, but could
     // prevent convergence.
     CreatedValuesCount++;
     return &takeOwnership(std::make_unique<IntegerValue>());
   }
 
   if (Type->isReferenceType()) {
     CreatedValuesCount++;
     QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
if (Visited.insert(PointeeType.getCanonicalType()).second) {
 
       if (PointeeVal != nullptr)
         setValue(PointeeLoc, *PointeeVal);
     }
 
     return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
   }
 
-  if (Type->isStructureOrClassType()) {
+  if (Type->isStructureOrClassType() &&
+      !DACtx->isExcludedRecordType(*Type->getAs<RecordType>())) {
     CreatedValuesCount++;
     // FIXME: Initialize only fields that are accessed in the context that is
     // being analyzed.
     llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
     for (const FieldDecl *Field : getObjectFields(Type)) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();

clang/unittests/Analysis/FlowSensitive/DataflowEnvironmentTest.cpp

 #include "gtest/gtest.h"
 #include <memory>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
 using ::testing::ElementsAre;
+using ::testing::IsNull;
 using ::testing::NotNull;
 using ::testing::Pair;
 
 class EnvironmentTest : public ::testing::Test {
 protected:
   EnvironmentTest() : DAContext(std::make_unique<WatchedLiteralsSolver>()) {}
 
   DataflowAnalysisContext DAContext;
std::string Code = R"cc(
      int Target () { return Global; }
   )cc";
 
   auto Unit =
       tooling::buildASTFromCodeWithArgs(Code, {"-fsyntax-only", "-std=c++11"});
   auto &Context = Unit->getASTContext();
 
   ASSERT_EQ(Context.getDiagnostics().getClient()->getNumErrors(), 0U);
-
   auto Results =
       match(decl(anyOf(varDecl(hasName("Global")).bind("global"),
                        functionDecl(hasName("Target")).bind("target"))),
             Context);
   const auto *Fun = selectFirst<FunctionDecl>("target", Results);
   const auto *Var = selectFirst<VarDecl>("global", Results);
   ASSERT_TRUE(Fun != nullptr);
   ASSERT_THAT(Var, NotNull());
std::string Code = R"cc(
      };
   )cc";
 
   auto Unit =
       tooling::buildASTFromCodeWithArgs(Code, {"-fsyntax-only", "-std=c++11"});
   auto &Context = Unit->getASTContext();
 
   ASSERT_EQ(Context.getDiagnostics().getClient()->getNumErrors(), 0U);
-
   auto Results =
       match(decl(anyOf(
                 varDecl(hasName("Global")).bind("global"),
                 cxxConstructorDecl(ofClass(hasName("Target"))).bind("target"))),
             Context);
   const auto *Ctor = selectFirst<CXXConstructorDecl>("target", Results);
   const auto *Var = selectFirst<VarDecl>("global", Results);
   ASSERT_TRUE(Ctor != nullptr);
   ASSERT_THAT(Var, NotNull());
 
   // Verify the global variable is populated when we analyze `Target`.
   Environment Env(DAContext, *Ctor);
   EXPECT_THAT(Env.getValue(*Var, SkipPast::None), NotNull());
 }
 
+TEST(ExcludeProtobufTypesTest, ExcludeEnabled) {
+  using namespace ast_matchers;
+
+  DataflowAnalysisContext DAContext(std::make_unique<WatchedLiteralsSolver>(),
+                                    {/*ExcludeGoogleProtobufs=*/true});
+  Environment Env(DAContext);
+
+  std::string Code = R"cc(
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+
+    namespace other {
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+    }
+
+    struct Bar : public google::protobuf::Message {
+      bool Field;
+    };
+
+    // Not a protobuf, but looks like it. Verify that it is *not* excluded.
+    struct Zab : public other::google::protobuf::Message {
+      bool Field;
+    };
+
+    void target() {
+      Bar B;
+      Zab Z;
+      (void)0;
+      /*[[check]]*/
+    }
+  )cc";
+
+  auto Unit =
+      tooling::buildASTFromCodeWithArgs(Code, {"-fsyntax-only", "-std=c++11"});
+  auto &Context = Unit->getASTContext();
+
+  ASSERT_EQ(Context.getDiagnostics().getClient()->getNumErrors(), 0U);
+  auto Results = match(varDecl(eachOf(varDecl(hasName("B")).bind("varB"),
+                                      varDecl(hasName("Z")).bind("varZ"))),
+                       Context);
+  const auto *B = selectFirst<VarDecl>("varB", Results);
+  ASSERT_TRUE(B != nullptr);
+  const auto *Z = selectFirst<VarDecl>("varZ", Results);
+  ASSERT_TRUE(Z != nullptr);
+
+  EXPECT_THAT(Env.createValue(B->getType()), IsNull());
+  EXPECT_THAT(Env.createValue(Z->getType()), NotNull());
+}
+
+TEST(ExcludeProtobufTypesTest, ExcludeDisabled) {
+  using namespace ast_matchers;
+
+  DataflowAnalysisContext DAContext(std::make_unique<WatchedLiteralsSolver>(),
+                                    {/*ExcludeGoogleProtobufs=*/false});
+  Environment Env(DAContext);
+
+  std::string Code = R"cc(
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+
+    namespace other {
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+    }
+
+    struct Bar : public google::protobuf::Message {
+      bool Field;
+    };
+
+    // Not a protobuf, but looks like it. Verify that it is *not* excluded.
+    struct Zab : public other::google::protobuf::Message {
+      bool Field;
+    };
+
+    void target() {
+      Bar B;
+      Zab Z;
+      (void)0;
+      /*[[check]]*/
+    }
+  )cc";
+
+  auto Unit =
+      tooling::buildASTFromCodeWithArgs(Code, {"-fsyntax-only", "-std=c++11"});
+  auto &Context = Unit->getASTContext();
+
+  ASSERT_EQ(Context.getDiagnostics().getClient()->getNumErrors(), 0U);
+
+  auto Results = match(varDecl(eachOf(varDecl(hasName("B")).bind("varB"),
+                                      varDecl(hasName("Z")).bind("varZ"))),
+                       Context);
+  const auto *B = selectFirst<VarDecl>("varB", Results);
+  ASSERT_TRUE(B != nullptr);
+  const auto *Z = selectFirst<VarDecl>("varZ", Results);
+  ASSERT_TRUE(Z != nullptr);
+
+  EXPECT_THAT(Env.createValue(B->getType()), NotNull());
+  EXPECT_THAT(Env.createValue(Z->getType()), NotNull());
+}
+
 } // namespace