Author: Yitzhak Mandelbaum Date: 2022-02-24T20:51:59Z New Revision: 208c25fcbf483b4dd61fb8b99f8422994cc5072e
URL: https://github.com/llvm/llvm-project/commit/208c25fcbf483b4dd61fb8b99f8422994cc5072e DIFF: https://github.com/llvm/llvm-project/commit/208c25fcbf483b4dd61fb8b99f8422994cc5072e.diff LOG: [clang][dataflow] Add limits to size of modeled data structures in environment. 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. Differential Revision: https://reviews.llvm.org/D120510 Added: Modified: clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp Removed: ################################################################################ diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index 2fb32053a11b5..d82b8b4386d18 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -248,7 +248,8 @@ class Environment { /// /// `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; diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index fc6f9aa2167b0..fd3f91ddb667e 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -29,6 +29,12 @@ 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, @@ -336,25 +342,40 @@ Value *Environment::getValue(const Expr &E, SkipPast SP) const { 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) @@ -365,13 +386,14 @@ Value *Environment::createValueUnlessSelfReferential( } 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) @@ -382,6 +404,7 @@ Value *Environment::createValueUnlessSelfReferential( } if (Type->isStructureOrClassType()) { + CreatedValuesCount++; // FIXME: Initialize only fields that are accessed in the context that is // being analyzed. llvm::DenseMap<const ValueDecl *, Value *> FieldValues; @@ -394,7 +417,8 @@ Value *Environment::createValueUnlessSelfReferential( Visited.insert(FieldType.getCanonicalType()); FieldValues.insert( - {Field, createValueUnlessSelfReferential(FieldType, Visited)}); + {Field, createValueUnlessSelfReferential( + FieldType, Visited, Depth + 1, CreatedValuesCount)}); Visited.erase(FieldType.getCanonicalType()); } _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
