[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

513

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

513

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

513

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

513

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

513

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/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
                                                 CreatedValuesCount);
   if (CreatedValuesCount > MaxCompositeValueSize) {
     llvm::errs() << "Attempting to initialize a huge value of type: "
                  << Type.getAsString() << "\n";
   }
   return Val;
 }
 
+// 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.
+static bool isExcludedRecordType(const RecordType *Ty) {
+  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;
+
+  const RecordDecl *RD = BaseTy->getDecl();
+  if (RD->getIdentifier() == nullptr || RD->getName() != "Message")
+    return false;
+
+  const auto *ND = dyn_cast<NamespaceDecl>(RD->getDeclContext());
+  if (ND == nullptr || ND->getIdentifier() == nullptr)
+    return false;
+  if (ND->getName() == "proto2")
+    return true;
+
+  // Check for `::google::protobuf`:
+  if (ND->getName() != "protobuf")
+    return false;
+
+  ND = dyn_cast<NamespaceDecl>(ND->getDeclContext());
+  return ND != nullptr && ND->getParent()->isTranslationUnit() &&
+         ND->getIdentifier() != nullptr && ND->getName() == "google";
+}
+
 Value *Environment::createValueUnlessSelfReferential(
     QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
     int &CreatedValuesCount) {
   assert(!Type.isNull());
 
   // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
   if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
       Depth > MaxCompositeValueDepth)
if (!Visited.contains(PointeeType.getCanonicalType())) {
 
       if (PointeeVal != nullptr)
         setValue(PointeeLoc, *PointeeVal);
     }
 
     return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
   }
 
-  if (Type->isStructureOrClassType()) {
+  if (Type->isStructureOrClassType() &&
+      !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 : getAccessibleObjectFields(Type)) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();

clang/unittests/Analysis/FlowSensitive/DataflowEnvironmentTest.cpp

 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
-using ::testing::ElementsAre;
-using ::testing::Pair;
+using ::testing::IsNull;
+using ::testing::NotNull;
 
 class EnvironmentTest : public ::testing::Test {
   DataflowAnalysisContext Context;
 
 protected:
   EnvironmentTest()
       : Context(std::make_unique<WatchedLiteralsSolver>()), Env(Context) {}
 
TEST_F(EnvironmentTest, CreateValueRecursiveType) {
   StructValue *SVal = clang::dyn_cast<StructValue>(Val);
   ASSERT_NE(SVal, nullptr);
   Val = SVal->getChild(*R);
   ASSERT_NE(Val, nullptr);
   PointerValue *PV = clang::dyn_cast<PointerValue>(Val);
   EXPECT_NE(PV, nullptr);
 }
 
+TEST_F(EnvironmentTest, ExcludeProtobufTypes) {
+  using namespace ast_matchers;
+
+  std::string Code = R"cc(
+    namespace proto2 {
+    struct Message {};
+    }
+
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+
+    namespace other {
+    namespace google {
+    namespace protobuf {
+    struct Message {};
+    }
+    }
+    }
+
+    struct Foo : public proto2::Message {
+      bool Field;
+    };
+
+    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() {
+      Foo F;
+      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("F")).bind("varF"),
+                                      varDecl(hasName("B")).bind("varB"),
+                                      varDecl(hasName("Z")).bind("varZ"))),
+                       Context);
+  const auto *F = selectFirst<VarDecl>("varF", Results);
+  ASSERT_TRUE(F != nullptr);
+  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(F->getType()), IsNull());
+  EXPECT_THAT(Env.createValue(B->getType()), IsNull());
+  EXPECT_THAT(Env.createValue(Z->getType()), NotNull());
+}
+
 } // namespace