[clang][dataflow] Add limits to size of modeled data structures in environment.

[ymandel]

Summary

Adds two new parameters to control the size of data structures modeled in the environment: # of values and depth of data structure. The environment already prevents creation of recursive data structures, but that was insufficient in practice. Very large structs still ground the analysis to a halt. These new parameters allow tuning the size more effectively.

In this patch, the parameters are set as internal constants. We leave to a future patch to make these proper model parameters.

[xazax.hun]

Very large structs still ground the analysis to a halt.

I had similar experience in the past with analyses that tried to represent all values in structs eagerly.

I think a better approach in general to make it as lazy as possible, so if a function does not access a field, never construct a representation for that in the memory.

This patch looks good and we will likely see the need for such limits even with a lazy system to handle certain code patterns. Are there any plans to make this more lazy in the future?

[ymandel]

In D120510#3343935, @xazax.hun wrote:

Very large structs still ground the analysis to a halt.

I had similar experience in the past with analyses that tried to represent all values in structs eagerly.

I think a better approach in general to make it as lazy as possible, so if a function does not access a field, never construct a representation for that in the memory.

This patch looks good and we will likely see the need for such limits even with a lazy system to handle certain code patterns. Are there any plans to make this more lazy in the future?

Yes! Exactly as you mention, we're planning two approaches:

1. Scan the AST of the function body and build the set of accessed fields. That will be consulted as a filter during construction.
2. Support lazy construction. The problem we have is that we're not sure how to ensure that the "thunk" is shared between the "many worlds" that is the forking copies of the environments. We need to ensure that once the value is created lazily in one copy, it's visible in all others.

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

private:
   /// self-referential pointer or reference type. `Visited` is used to track
   /// which types appeared in the reference/pointer chain in order to avoid
   /// creating a cyclic dependency with self-referential pointers/references.
   ///
   /// Requirements:
   ///
   ///  `Type` must not be null.
   Value *createValueUnlessSelfReferential(QualType Type,
-                                          llvm::DenseSet<QualType> &Visited);
+                                          llvm::DenseSet<QualType> &Visited,
+                                          int Depth, int &CreatedValuesCount);
 
   StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
   const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
 
   // `DACtx` is not null and not owned by this object.
   DataflowAnalysisContext *DACtx;
 
   // Maps from program declarations and statements to storage locations that are

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
+// FIXME: convert these to parameters of the analysis or environment. Current
+// settings have been experimentaly validated, but only for a particular
+// analysis.
+static constexpr int MaxCompositeValueDepth = 3;
+static constexpr int MaxCompositeValueSize = 1000;
+
 /// Returns a map consisting of key-value entries that are present in both maps.
 template <typename K, typename V>
 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
                                         const llvm::DenseMap<K, V> &Map2) {
   llvm::DenseMap<K, V> Result;
   for (auto &Entry : Map1) {
     auto It = Map2.find(Entry.first);
     if (It != Map2.end() && Entry.second == It->second)
Value *Environment::getValue(const Expr &E, SkipPast SP) const {
   auto *Loc = getStorageLocation(E, SP);
   if (Loc == nullptr)
     return nullptr;
   return getValue(*Loc);
 }
 
 Value *Environment::createValue(QualType Type) {
   llvm::DenseSet<QualType> Visited;
-  return createValueUnlessSelfReferential(Type, Visited);
+  int CreatedValuesCount = 0;
+  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;
 }
 
 Value *Environment::createValueUnlessSelfReferential(
-    QualType Type, llvm::DenseSet<QualType> &Visited) {
+    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)
+    return nullptr;
+
   if (Type->isIntegerType()) {
+    CreatedValuesCount++;
     return &takeOwnership(std::make_unique<IntegerValue>());
   }
 
   if (Type->isReferenceType()) {
+    CreatedValuesCount++;
     QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
     auto &PointeeLoc = createStorageLocation(PointeeType);
 
     if (!Visited.contains(PointeeType.getCanonicalType())) {
       Visited.insert(PointeeType.getCanonicalType());
-      Value *PointeeVal =
-          createValueUnlessSelfReferential(PointeeType, Visited);
+      Value *PointeeVal = createValueUnlessSelfReferential(
+          PointeeType, Visited, Depth, CreatedValuesCount);
       Visited.erase(PointeeType.getCanonicalType());
 
       if (PointeeVal != nullptr)
         setValue(PointeeLoc, *PointeeVal);
     }
 
     return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
   }
 
   if (Type->isPointerType()) {
+    CreatedValuesCount++;
     QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
     auto &PointeeLoc = createStorageLocation(PointeeType);
 
     if (!Visited.contains(PointeeType.getCanonicalType())) {
       Visited.insert(PointeeType.getCanonicalType());
-      Value *PointeeVal =
-          createValueUnlessSelfReferential(PointeeType, Visited);
+      Value *PointeeVal = createValueUnlessSelfReferential(
+          PointeeType, Visited, Depth, CreatedValuesCount);
       Visited.erase(PointeeType.getCanonicalType());
 
       if (PointeeVal != nullptr)
         setValue(PointeeLoc, *PointeeVal);
     }
 
     return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
   }
 
   if (Type->isStructureOrClassType()) {
+    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 : Type->getAsRecordDecl()->fields()) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();
       if (Visited.contains(FieldType.getCanonicalType()))
         continue;
 
       Visited.insert(FieldType.getCanonicalType());
       FieldValues.insert(
-          {Field, createValueUnlessSelfReferential(FieldType, Visited)});
+          {Field, createValueUnlessSelfReferential(
+                      FieldType, Visited, Depth + 1, CreatedValuesCount)});
       Visited.erase(FieldType.getCanonicalType());
     }
 
     return &takeOwnership(
         std::make_unique<StructValue>(std::move(FieldValues)));
   }
 
   return nullptr;