[clang][dataflow] Various changes to handling of modeled fields.

[mboehme]

Summary

• Rename getReferencedFields() to getModeledFields(). Move the logic that returns all object fields when doing a context-sensitive analysis to here from DataflowAnalysisContext::createStorageLocation(). I think all callers of the previous getReferencedFields() should use this logic; the fact that they were not doing so looks like a bug.

• Make getModeledFields() public. I have an upcoming patch that will need to use this function from Transfer.cpp, and there doesn't seem to be any reason why this function should not be public.

• Use a SmallSetVector to get deterministic iteration order. I have a pending patch where I'm getting flaky tests because Environment::createValueUnlessSelfReferential() is non-deterministically populating different fields depending on the iteration order. This change fixes those flaky tests.

[mboehme]

libcxx failure looks unrelated

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

 ///   otherwise omits the node afterwards.
 ///
 ///   * `ExprWithCleanups` - The CFG will generate the appropriate calls to
 ///   destructors and then omit the node.
 ///
 const Expr &ignoreCFGOmittedNodes(const Expr &E);
 const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
 
+/// A set of `FieldDecl *`. Use `SmallSetVector` to guarantee deterministic
+/// iteration order.
+using FieldSet = llvm::SmallSetVector<const FieldDecl *, 4>;
+
 /// Returns the set of all fields in the type.
-llvm::DenseSet<const FieldDecl *> getObjectFields(QualType Type);
+FieldSet getObjectFields(QualType Type);
 
 struct ContextSensitiveOptions {
   /// The maximum depth to analyze. A value of zero is equivalent to disabling
   /// context-sensitive analysis entirely.
   unsigned Depth = 2;
 };
 
 /// Owns objects that encompass the state of a program and stores context that
public:
   /// Returns the outcome of satisfiability checking on `Constraints`.
   ///
   /// Flow conditions are not incorporated, so they may need to be manually
   /// included in `Constraints` to provide contextually-accurate results, e.g.
   /// if any definitions or relationships of the values in `Constraints` have
   /// been stored in flow conditions.
   Solver::Result querySolver(llvm::SetVector<const Formula *> Constraints);
 
+  /// Returns the fields of `Type`, limited to the set of fields modeled by this
+  /// context.
+  FieldSet getModeledFields(QualType Type);
+
 private:
   friend class Environment;
 
   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;
     using DenseMapInfo::getTombstoneKey;
     using DenseMapInfo::isEqual;
   };
 
   // Extends the set of modeled field declarations.
-  void addModeledFields(const llvm::DenseSet<const FieldDecl *> &Fields);
-
-  /// Returns the fields of `Type`, limited to the set of fields modeled by this
-  /// context.
-  llvm::DenseSet<const FieldDecl *> getReferencedFields(QualType Type);
+  void addModeledFields(const FieldSet &Fields);
 
   /// Adds all constraints of the flow condition identified by `Token` and all
   /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used
   /// to track tokens of flow conditions that were already visited by recursive
   /// calls.
   void addTransitiveFlowConditionConstraints(
       Atom Token, llvm::SetVector<const Formula *> &Constraints,
       llvm::DenseSet<Atom> &VisitedTokens);
private:
   // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
   // dependencies is stored in the `FlowConditionDeps` map.
   llvm::DenseMap<Atom, llvm::DenseSet<Atom>> FlowConditionDeps;
   llvm::DenseMap<Atom, const Formula *> FlowConditionConstraints;
 
   llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts;
 
   // Fields modeled by environments covered by this context.
-  llvm::DenseSet<const FieldDecl *> ModeledFields;
+  FieldSet ModeledFields;
 
   std::unique_ptr<Logger> LogOwner; // If created via flags.
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

static llvm::cl::opt<std::string> DataflowLog(
     "dataflow-log", llvm::cl::Hidden, llvm::cl::ValueOptional,
     llvm::cl::desc("Emit log of dataflow analysis. With no arg, writes textual "
                    "log to stderr. With an arg, writes HTML logs under the "
                    "specified directory (one per analyzed function)."));
 
 namespace clang {
 namespace dataflow {
 
-void DataflowAnalysisContext::addModeledFields(
-    const llvm::DenseSet<const FieldDecl *> &Fields) {
-  llvm::set_union(ModeledFields, Fields);
-}
-
-llvm::DenseSet<const FieldDecl *>
-DataflowAnalysisContext::getReferencedFields(QualType Type) {
-  llvm::DenseSet<const FieldDecl *> Fields = getObjectFields(Type);
-  llvm::set_intersect(Fields, ModeledFields);
-  return Fields;
-}
-
-StorageLocation &DataflowAnalysisContext::createStorageLocation(QualType Type) {
-  if (!Type.isNull() && Type->isRecordType()) {
-    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
-    // During context-sensitive analysis, a struct may be allocated in one
-    // function, but its field accessed in a function lower in the stack than
-    // the allocation. Since we only collect fields used in the function where
-    // the allocation occurs, we can't apply that filter when performing
-    // context-sensitive analysis. But, this only applies to storage locations,
-    // since field access it not allowed to fail. In contrast, field *values*
-    // don't need this allowance, since the API allows for uninitialized fields.
-    auto Fields = Opts.ContextSensitiveOpts ? getObjectFields(Type)
-                                            : getReferencedFields(Type);
-    for (const FieldDecl *Field : Fields)
+FieldSet DataflowAnalysisContext::getModeledFields(QualType Type) {
+  if (Opts.ContextSensitiveOpts)
+    return getObjectFields(Type);
+
+  return llvm::set_intersection(getObjectFields(Type), ModeledFields);
+}
+
+void DataflowAnalysisContext::addModeledFields(const FieldSet &Fields) {
+  ModeledFields.set_union(Fields);
+}
+
+StorageLocation &DataflowAnalysisContext::createStorageLocation(QualType Type) {
+  if (!Type.isNull() && Type->isRecordType()) {
+    llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
+    for (const FieldDecl *Field : getModeledFields(Type))
       FieldLocs.insert({Field, &createStorageLocation(Field->getType())});
     return arena().create<AggregateStorageLocation>(Type, std::move(FieldLocs));
   }
   return arena().create<ScalarStorageLocation>(Type);
 }
 
 StorageLocation &
 DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {

 const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
   if (auto *E = dyn_cast<Expr>(&S))
     return ignoreCFGOmittedNodes(*E);
   return S;
 }
 
 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single
 // field decl will be modeled for all instances of the inherited field.
-static void
-getFieldsFromClassHierarchy(QualType Type,
-                            llvm::DenseSet<const FieldDecl *> &Fields) {
+static void getFieldsFromClassHierarchy(QualType Type,
+                                        clang::dataflow::FieldSet &Fields) {
   if (Type->isIncompleteType() || Type->isDependentType() ||
       !Type->isRecordType())
     return;
 
   for (const FieldDecl *Field : Type->getAsRecordDecl()->fields())
     Fields.insert(Field);
   if (auto *CXXRecord = Type->getAsCXXRecordDecl())
     for (const CXXBaseSpecifier &Base : CXXRecord->bases())
       getFieldsFromClassHierarchy(Base.getType(), Fields);
 }
 
 /// Gets the set of all fields in the type.
-llvm::DenseSet<const FieldDecl *>
-clang::dataflow::getObjectFields(QualType Type) {
-  llvm::DenseSet<const FieldDecl *> Fields;
+clang::dataflow::FieldSet clang::dataflow::getObjectFields(QualType Type) {
+  FieldSet Fields;
   getFieldsFromClassHierarchy(Type, Fields);
   return Fields;
 }

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 
 static void insertIfFunction(const Decl &D,
                              llvm::DenseSet<const FunctionDecl *> &Funcs) {
   if (auto *FD = dyn_cast<FunctionDecl>(&D))
     Funcs.insert(FD);
 }
 
 static void
-getFieldsGlobalsAndFuncs(const Decl &D,
-                         llvm::DenseSet<const FieldDecl *> &Fields,
+getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields,
                          llvm::DenseSet<const VarDecl *> &Vars,
                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
   insertIfGlobal(D, Vars);
   insertIfFunction(D, Funcs);
   if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
     for (const auto *B : Decomp->bindings())
       if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
         // FIXME: should we be using `E->getFoundDecl()`?
         if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
           Fields.insert(FD);
 }
 
 /// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields,
 /// global variables and functions that are declared in or referenced from
 /// sub-statements.
 static void
-getFieldsGlobalsAndFuncs(const Stmt &S,
-                         llvm::DenseSet<const FieldDecl *> &Fields,
+getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields,
                          llvm::DenseSet<const VarDecl *> &Vars,
                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
   for (auto *Child : S.children())
     if (Child != nullptr)
       getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs);
   if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S))
     getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs);
 
getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields,
   }
 }
 
 // FIXME: Add support for resetting globals after function calls to enable
 // the implementation of sound analyses.
 void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
   assert(FuncDecl->getBody() != nullptr);
 
-  llvm::DenseSet<const FieldDecl *> Fields;
+  FieldSet Fields;
   llvm::DenseSet<const VarDecl *> Vars;
   llvm::DenseSet<const FunctionDecl *> Funcs;
 
   // Look for global variable and field references in the
   // constructor-initializers.
   if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
     for (const auto *Init : CtorDecl->inits()) {
       if (Init->isMemberInitializer()) {
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   LocToVal[&Loc] = &Val;
 
   if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
     auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
 
     const QualType Type = AggregateLoc.getType();
     assert(Type->isRecordType());
 
-    for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
+    for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
       assert(Field != nullptr);
       StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
       MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
       if (auto *FieldVal = StructVal->getChild(*Field))
         setValue(FieldLoc, *FieldVal);
     }
   }
 
if (Type->isReferenceType())
       return &arena().create<ReferenceValue>(PointeeLoc);
     else
       return &arena().create<PointerValue>(PointeeLoc);
   }
 
   if (Type->isRecordType()) {
     CreatedValuesCount++;
     llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
-    for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
+    for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
       assert(Field != nullptr);
 
       QualType FieldType = Field->getType();
       if (Visited.contains(FieldType.getCanonicalType()))
         continue;
 
       Visited.insert(FieldType.getCanonicalType());
       if (auto *FieldValue = createValueUnlessSelfReferential(