diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -0,0 +1,94 @@ +//===-- DataflowAnalysisContext.h -------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines a DataflowAnalysisContext class that owns objects that +// encompass the state of a program and stores context that is used during +// dataflow analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H + +#include "clang/AST/Decl.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/DenseMap.h" +#include +#include +#include +#include + +namespace clang { +namespace dataflow { + +/// Owns objects that encompass the state of a program and stores additional +/// context that is used during dataflow analysis. +class DataflowAnalysisContext { +public: + /// Takes ownership of `Loc` and returns a pointer to it. + /// + /// Requirements: + /// + /// `Loc` must not be null. + StorageLocation *takeOwnership(std::unique_ptr Loc) { + assert(Loc != nullptr); + Locs.push_back(std::move(Loc)); + return Locs.back().get(); + } + + /// Takes ownership of `Val` and returns a pointer to it. + /// + /// Requirements: + /// + /// `Val` must not be null. + Value *takeOwnership(std::unique_ptr Val) { + assert(Val != nullptr); + Values.push_back(std::move(Val)); + return Values.back().get(); + } + + /// Assigns `Loc` to `D`. + /// + /// Requirements: + /// + /// `D` must not be null. + /// + /// `Loc` must not be null. + /// + /// `D` must not be assigned a storage location. + void setStorageLocation(const VarDecl *D, StorageLocation *Loc) { + assert(D != nullptr); + assert(Loc != nullptr); + assert(VarDeclToLoc.find(D) == VarDeclToLoc.end()); + VarDeclToLoc[D] = Loc; + } + + /// Returns the storage location assigned to `D` or null if `D` has no + /// assigned storage location. + /// + /// Requirements: + /// + /// `D` must not be null. + StorageLocation *getStorageLocation(const VarDecl *D) const { + assert(D != nullptr); + auto It = VarDeclToLoc.find(D); + return It == VarDeclToLoc.end() ? nullptr : It->second; + } + +private: + // Storage for the state of a program. + std::vector> Locs; + std::vector> Values; + llvm::DenseMap VarDeclToLoc; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -15,7 +15,15 @@ #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H +#include "clang/AST/Decl.h" +#include "clang/AST/Type.h" +#include "clang/AST/TypeOrdering.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" namespace clang { namespace dataflow { @@ -23,11 +31,87 @@ /// Holds the state of the program (store and heap) at a given program point. class Environment { public: - bool operator==(const Environment &) const { return true; } + Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {} - LatticeJoinEffect join(const Environment &) { - return LatticeJoinEffect::Unchanged; - } + bool operator==(const Environment &) const; + + LatticeJoinEffect join(const Environment &); + + /// Creates a storage location appropriate for `Type`. Does not assign a value + /// to the returned storage location in the environment. Never returns null. + StorageLocation *createStorageLocation(QualType Type); + + /// Creates a storage location for `Decl`. Does not assign the returned + /// storage location to `Decl` in the environment. Does not assign a value + /// to the returned storage location in the environment. Never returns null. + /// + /// Requirements: + /// + /// `D` must not be null. + StorageLocation *createStorageLocation(const VarDecl *D); + + /// Assigns `Loc` to `D` in the environment. + /// + /// Requirements: + /// + /// `D` must not be null. + /// + /// `Loc` must not be null. + /// + /// `D` must not be assigned a storage location in the environment. + void setStorageLocation(const ValueDecl *D, StorageLocation *Loc); + + /// Returns the storage location assigned to `D` in the environment or null if + /// `D` isn't assigned a storage location in the environment. + /// + /// Requirements: + /// + /// `D` must not be null. + StorageLocation *getStorageLocation(const ValueDecl *D) const; + + /// Creates a value appropriate for `Type` and assigns it to the given storage + /// location. If `Type` is a pointer or reference type, creates all the + /// necessary storage locations and values for indirections until it finds a + /// non-pointer/non-reference type. + /// + /// Requirements: + /// + /// `Loc` must not be null. + Value *initValueInStorageLocation(const StorageLocation *Loc, QualType Type); + + /// Assigns `Val` to `Loc` in the environment. + /// + /// Requirements: + /// + /// `Loc` must not be null. + /// + /// `Val` must not be null. + void setValue(const StorageLocation *Loc, Value *Val); + + /// Returns the value assigned to `Loc` in the environment or null if `Loc` + /// isn't assigned a value in the environment. + /// + /// Requirements: + /// + /// `Loc` must not be null. + Value *getValue(const StorageLocation *Loc) const; + +private: + /// Recursively initializes storage locations and values unless it sees a + /// 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: + /// + /// `Loc` must not be null. + Value *initValueInStorageLocationUnlessSelfReferential( + const StorageLocation *Loc, QualType Type, + llvm::DenseSet &Visited); + + DataflowAnalysisContext *DACtx; + llvm::DenseMap DeclToLoc; + llvm::DenseMap LocToVal; }; } // namespace dataflow diff --git a/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h b/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h @@ -0,0 +1,98 @@ +//===-- StorageLocation.h ---------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines classes that represent elements of the local variable store +// and of the heap during dataflow analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Type.h" +#include "llvm/ADT/DenseMap.h" + +namespace clang { +namespace dataflow { + +/// Base class for elements of the local variable store and of the heap. +/// +/// Each storage location holds a value. The mapping from storage locations to +/// values is stored in the environment. +class StorageLocation { +public: + enum class Kind { Scalar, Aggregate }; + + StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) {} + + virtual ~StorageLocation() = default; + + Kind getKind() const { return LocKind; } + + QualType getType() const { return Type; } + +private: + Kind LocKind; + QualType Type; +}; + +/// A storage location that is not subdivided further for the purposes of +/// abstract interpretation. For example: `int`, `int*`, `int&`. +class ScalarStorageLocation final : public StorageLocation { +public: + explicit ScalarStorageLocation(QualType Type) + : StorageLocation(Kind::Scalar, Type) {} + + static bool classof(const StorageLocation *Loc) { + return Loc->getKind() == Kind::Scalar; + } +}; + +/// A storage location which is subdivided into smaller storage locations that +/// can be traced independently by abstract interpretation. For example: a +/// struct with public members. +class AggregateStorageLocation final : public StorageLocation { +public: + explicit AggregateStorageLocation(QualType Type) + : AggregateStorageLocation( + Type, llvm::DenseMap()) {} + + AggregateStorageLocation( + QualType Type, + llvm::DenseMap Children) + : StorageLocation(Kind::Aggregate, Type), Children(std::move(Children)) {} + + static bool classof(const StorageLocation *Loc) { + return Loc->getKind() == Kind::Aggregate; + } + + /// Returns the child storage location for `D`. + /// + /// Requirements: + /// + /// `D` must not be null. + StorageLocation *getChild(const ValueDecl *D) const { + assert(D != nullptr); + auto It = Children.find(D); + // FIXME: A missing child member means that the sorage location was not + // created correctly. Change the following to assert(it != children_.end()) + // once all cases are modeled correctly. + if (It == Children.end()) + return nullptr; + return It->second; + } + +private: + llvm::DenseMap Children; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -0,0 +1,29 @@ +//===-- Transfer.h ----------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines a transfer function that evaluates a program statement and +// updates an environment accordingly. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H + +#include "clang/AST/Stmt.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" + +namespace clang { +namespace dataflow { + +/// Evaluates `S` and updates `Env` accordingly. +void transfer(const Stmt *S, Environment &Env); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H diff --git a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h --- a/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h +++ b/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -14,6 +14,7 @@ #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H +#include #include #include "clang/AST/ASTContext.h" @@ -75,6 +76,9 @@ /// Model of the state of the program (store and heap). Environment Env; + + TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env) + : Lattice(std::move(Lattice)), Env(std::move(Env)) {} }; /// Transfers the state of a basic block by evaluating each of its statements in diff --git a/clang/include/clang/Analysis/FlowSensitive/Value.h b/clang/include/clang/Analysis/FlowSensitive/Value.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/Value.h @@ -0,0 +1,142 @@ +//===-- Value.h -------------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines classes for values computed by abstract interpretation +// during dataflow analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H + +#include "clang/AST/Decl.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "llvm/ADT/DenseMap.h" +#include +#include + +namespace clang { +namespace dataflow { + +/// Base class for all values computed by abstract interpretation. +class Value { +public: + enum class Kind { Integer, Float, Reference, Pointer, Struct }; + + explicit Value(Kind ValKind) : ValKind(ValKind) {} + + virtual ~Value() {} + + Kind getKind() const { return ValKind; } + +private: + Kind ValKind; +}; + +/// Class that models an integer. +class IntegerValue : public Value { +public: + explicit IntegerValue() : Value(Kind::Integer) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Integer; + } +}; + +/// Class that models a float. +class FloatValue : public Value { +public: + explicit FloatValue() : Value(Kind::Float) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Float; + } +}; + +/// Base class for values that refer to storage locations. +class IndirectionValue : public Value { +public: + /// Constructs a value that refers to `Loc`. + /// + /// Requirements: + /// + /// `Loc` must not be null. + explicit IndirectionValue(Kind ValueKind, StorageLocation *Loc) + : Value(ValueKind), Loc(Loc) { + assert(Loc != nullptr); + } + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Reference || Val->getKind() == Kind::Pointer; + } + + StorageLocation *getLocation() const { return Loc; } + +private: + StorageLocation *Loc; +}; + +/// Class that models a dereferenced pointer. For example, a reference in C++ or +/// an lvalue in C. +class ReferenceValue final : public IndirectionValue { +public: + explicit ReferenceValue(StorageLocation *Loc) + : IndirectionValue(Kind::Reference, Loc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Reference; + } +}; + +/// Class that models a symbolic pointer. Specifically, any value of type `T*`. +class PointerValue final : public IndirectionValue { +public: + explicit PointerValue(StorageLocation *Loc) + : IndirectionValue(Kind::Pointer, Loc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Pointer; + } +}; + +/// Class that models a value of `struct` or `class` type. +class StructValue final : public Value { +public: + StructValue() : StructValue(llvm::DenseMap()) {} + + explicit StructValue(llvm::DenseMap Children) + : Value(Kind::Struct), Children(std::move(Children)) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Struct; + } + + /// Returns the child value for `D`. + /// + /// Requirements: + /// + /// `D` must not be null. + Value *getChild(const ValueDecl *D) const { + assert(D != nullptr); + auto It = Children.find(D); + // FIXME: A missing child member means that the value was not created + // correctly. Change the following to assert(it != children_.end()) once all + // cases are modeled correctly. + if (It == Children.end()) + return nullptr; + return It->second; + } + +private: + const llvm::DenseMap Children; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H diff --git a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -1,5 +1,7 @@ add_clang_library(clangAnalysisFlowSensitive ControlFlowContext.cpp + DataflowEnvironment.cpp + Transfer.cpp TypeErasedDataflowAnalysis.cpp LINK_LIBS diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -0,0 +1,216 @@ +//===-- DataflowEnvironment.cpp ---------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines an Environment class that is used by dataflow analyses +// that run over Control-Flow Graphs (CFGs) to keep track of the state of the +// program at given program points. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include + +namespace clang { +namespace dataflow { + +/// Returns true if and only if the given maps contain the same set of keys, and +/// for each key the values stored in both maps are equal. +template +bool denseMapsAreEqual(const llvm::DenseMap &Map1, + const llvm::DenseMap &Map2) { + if (Map1.size() != Map2.size()) { + return false; + } + for (auto &Entry : Map1) { + auto It = Map2.find(Entry.first); + if (It == Map2.end() || Entry.second != It->second) { + return false; + } + } + return true; +} + +/// Returns a map consisting of key-value entries that are present in both maps. +template +llvm::DenseMap intersectDenseMaps(const llvm::DenseMap &Map1, + const llvm::DenseMap &Map2) { + llvm::DenseMap Result; + for (auto &Entry : Map1) { + auto It = Map2.find(Entry.first); + if (It == Map2.end() || Entry.second != It->second) { + continue; + } + Result.insert({Entry.first, Entry.second}); + } + return Result; +} + +bool Environment::operator==(const Environment &Other) const { + assert(DACtx == Other.DACtx); + return denseMapsAreEqual(DeclToLoc, Other.DeclToLoc) && + denseMapsAreEqual(LocToVal, Other.LocToVal); +} + +LatticeJoinEffect Environment::join(const Environment &Other) { + assert(DACtx == Other.DACtx); + + auto Effect = LatticeJoinEffect::Unchanged; + + const unsigned DeclToLocSizeBefore = DeclToLoc.size(); + DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); + if (DeclToLocSizeBefore != DeclToLoc.size()) + Effect = LatticeJoinEffect::Changed; + + const unsigned LocToValSizeBefore = LocToVal.size(); + LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal); + if (LocToValSizeBefore != LocToVal.size()) + Effect = LatticeJoinEffect::Changed; + + return Effect; +} + +StorageLocation *Environment::createStorageLocation(QualType Type) { + if (Type->isStructureOrClassType()) { + llvm::DenseMap FieldLocs; + for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) { + FieldLocs.insert({Field, createStorageLocation(Field->getType())}); + } + return DACtx->takeOwnership( + std::make_unique(Type, std::move(FieldLocs))); + } + return DACtx->takeOwnership(std::make_unique(Type)); +} + +StorageLocation *Environment::createStorageLocation(const VarDecl *D) { + assert(D != nullptr); + // Evaluated declarations are always assigned the same storage locations to + // ensure that the environment stabilizes across loop iterations. Storage + // locations for evaluated declarations are stored in the analysis context. + if (auto *Loc = DACtx->getStorageLocation(D)) + return Loc; + auto *Loc = createStorageLocation(D->getType()); + DACtx->setStorageLocation(D, Loc); + return Loc; +} + +void Environment::setStorageLocation(const ValueDecl *D, StorageLocation *Loc) { + assert(D != nullptr); + assert(Loc != nullptr); + assert(DeclToLoc.find(D) == DeclToLoc.end()); + DeclToLoc[D] = Loc; +} + +StorageLocation *Environment::getStorageLocation(const ValueDecl *D) const { + assert(D != nullptr); + auto It = DeclToLoc.find(D); + return It == DeclToLoc.end() ? nullptr : It->second; +} + +Value *Environment::initValueInStorageLocation(const StorageLocation *Loc, + QualType Type) { + llvm::DenseSet Visited; + return initValueInStorageLocationUnlessSelfReferential(Loc, Type, Visited); +} + +void Environment::setValue(const StorageLocation *Loc, Value *Value) { + assert(Loc != nullptr); + assert(Value != nullptr); + LocToVal[Loc] = Value; +} + +Value *Environment::getValue(const StorageLocation *Loc) const { + assert(Loc != nullptr); + auto It = LocToVal.find(Loc); + return It == LocToVal.end() ? nullptr : It->second; +} + +Value *Environment::initValueInStorageLocationUnlessSelfReferential( + const StorageLocation *Loc, QualType Type, + llvm::DenseSet &Visited) { + assert(Loc != nullptr); + + if (Type->isIntegerType()) { + auto *Value = DACtx->takeOwnership(std::make_unique()); + setValue(Loc, Value); + return Value; + } + + if (Type->isRealFloatingType()) { + auto *Value = DACtx->takeOwnership(std::make_unique()); + setValue(Loc, Value); + return Value; + } + + if (Type->isReferenceType()) { + QualType PointeeType = Type->getAs()->getPointeeType(); + auto *PointeeLoc = createStorageLocation(PointeeType); + + if (!Visited.contains(PointeeType)) { + Visited.insert(PointeeType); + initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType, + Visited); + Visited.erase(PointeeType); + } + + auto *Value = + DACtx->takeOwnership(std::make_unique(PointeeLoc)); + setValue(Loc, Value); + return Value; + } + + if (Type->isPointerType()) { + QualType PointeeType = Type->getAs()->getPointeeType(); + auto *PointeeLoc = createStorageLocation(PointeeType); + + if (!Visited.contains(PointeeType)) { + Visited.insert(PointeeType); + initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType, + Visited); + Visited.erase(PointeeType); + } + + auto *Value = + DACtx->takeOwnership(std::make_unique(PointeeLoc)); + setValue(Loc, Value); + return Value; + } + + if (Type->isStructureOrClassType()) { + auto *AggregateLoc = cast(Loc); + + llvm::DenseMap FieldValues; + for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) { + QualType FieldType = Field->getType(); + if (Visited.contains(FieldType)) + continue; + + Visited.insert(FieldType); + FieldValues.insert( + {Field, initValueInStorageLocationUnlessSelfReferential( + AggregateLoc->getChild(Field), FieldType, Visited)}); + Visited.erase(FieldType); + } + + auto *Value = DACtx->takeOwnership( + std::make_unique(std::move(FieldValues))); + setValue(Loc, Value); + return Value; + } + + return nullptr; +} + +} // namespace dataflow +} // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -0,0 +1,47 @@ +//===-- Transfer.cpp --------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines transfer functions that evaluate program statements and +// update an environment accordingly. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/FlowSensitive/Transfer.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "llvm/Support/Casting.h" +#include + +namespace clang { +namespace dataflow { + +static void transferVarDecl(const VarDecl *D, Environment &Env) { + auto *Loc = Env.createStorageLocation(D); + Env.setStorageLocation(D, Loc); + Env.initValueInStorageLocation(Loc, D->getType()); +} + +static void transferDeclStmt(const DeclStmt *S, Environment &Env) { + if (const auto *D = dyn_cast(S->getSingleDecl())) { + transferVarDecl(D, Env); + } +} + +void transfer(const Stmt *S, Environment &Env) { + assert(!isa(S)); + + if (const auto *DS = dyn_cast(S)) { + transferDeclStmt(DS, Env); + } +} + +} // namespace dataflow +} // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -18,6 +18,7 @@ #include "clang/Analysis/CFG.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Analysis/FlowSensitive/DataflowWorklist.h" +#include "clang/Analysis/FlowSensitive/Transfer.h" #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" @@ -39,12 +40,6 @@ std::vector> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis) { - // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()` - // to enable building analyses like computation of dominators that initialize - // the state of each basic block differently. - TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(), - InitEnv}; - llvm::DenseSet Preds; Preds.insert(Block.pred_begin(), Block.pred_end()); if (Block.getTerminator().isTemporaryDtorsBranch()) { @@ -77,6 +72,7 @@ } } + llvm::Optional MaybeState; for (const CFGBlock *Pred : Preds) { // Skip if the `Block` is unreachable or control flow cannot get past it. if (!Pred || Pred->hasNoReturnElement()) @@ -91,10 +87,20 @@ const TypeErasedDataflowAnalysisState &PredState = MaybePredState.getValue(); - Analysis.joinTypeErased(State.Lattice, PredState.Lattice); - State.Env.join(PredState.Env); + if (MaybeState.hasValue()) { + Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice); + MaybeState->Env.join(PredState.Env); + } else { + MaybeState = PredState; + } } - return State; + if (!MaybeState.hasValue()) { + // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()` + // to enable building analyses like computation of dominators that + // initialize the state of each basic block differently. + MaybeState.emplace(Analysis.typeErasedInitialElement(), InitEnv); + } + return *MaybeState; } TypeErasedDataflowAnalysisState transferBlock( @@ -109,16 +115,16 @@ computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis); for (const CFGElement &Element : Block) { // FIXME: Evaluate other kinds of `CFGElement`. - const llvm::Optional Stmt = Element.getAs(); - if (!Stmt.hasValue()) + const llvm::Optional CfgStmt = Element.getAs(); + if (!CfgStmt.hasValue()) continue; - // FIXME: Evaluate the statement contained in `Stmt`. + const Stmt *S = CfgStmt.getValue().getStmt(); + transfer(S, State.Env); + State.Lattice = Analysis.transferTypeErased(S, State.Lattice, State.Env); - State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(), - State.Lattice, State.Env); if (HandleTransferredStmt != nullptr) - HandleTransferredStmt(Stmt.getValue(), State); + HandleTransferredStmt(CfgStmt.getValue(), State); } return State; } diff --git a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt --- a/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/unittests/Analysis/FlowSensitive/CMakeLists.txt @@ -7,6 +7,7 @@ SingleVarConstantPropagationTest.cpp TestingSupport.cpp TestingSupportTest.cpp + TransferTest.cpp TypeErasedDataflowAnalysisTest.cpp ) diff --git a/clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h b/clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h @@ -0,0 +1,55 @@ +//===-- NoopAnalysis.h ------------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines a NoopAnalysis class that is used by dataflow analysis +// tests. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H +#define LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include + +namespace clang { +namespace dataflow { + +class NoopLattice { +public: + bool operator==(const NoopLattice &) const { return true; } + + LatticeJoinEffect join(const NoopLattice &) { + return LatticeJoinEffect::Unchanged; + } +}; + +inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) { + return OS << "noop"; +} + +class NoopAnalysis : public DataflowAnalysis { +public: + NoopAnalysis(ASTContext &Context) + : DataflowAnalysis(Context) {} + + static NoopLattice initialElement() { return {}; } + + NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) { + return {}; + } +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h --- a/clang/unittests/Analysis/FlowSensitive/TestingSupport.h +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupport.h @@ -98,7 +98,8 @@ auto CFCtx = ControlFlowContext::build(F, F->getBody(), &F->getASTContext()); ASSERT_TRUE((bool)CFCtx) << "Could not build ControlFlowContext."; - Environment Env; + DataflowAnalysisContext DACtx; + Environment Env(DACtx); auto Analysis = MakeAnalysis(Context, Env); llvm::Expected> diff --git a/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp b/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp @@ -1,4 +1,5 @@ #include "TestingSupport.h" +#include "NoopAnalysis.h" #include "clang/AST/ASTContext.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" @@ -19,32 +20,6 @@ using ::testing::Pair; using ::testing::UnorderedElementsAre; -class NoopLattice { -public: - bool operator==(const NoopLattice &) const { return true; } - - LatticeJoinEffect join(const NoopLattice &) { - return LatticeJoinEffect::Unchanged; - } -}; - -std::ostream &operator<<(std::ostream &OS, const NoopLattice &S) { - OS << "noop"; - return OS; -} - -class NoopAnalysis : public DataflowAnalysis { -public: - NoopAnalysis(ASTContext &Context) - : DataflowAnalysis(Context) {} - - static NoopLattice initialElement() { return {}; } - - NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) { - return {}; - } -}; - template const FunctionDecl *findTargetFunc(ASTContext &Context, T FunctionMatcher) { auto TargetMatcher = diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp new file mode 100644 --- /dev/null +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -0,0 +1,617 @@ +//===- unittests/Analysis/FlowSensitive/TransferTest.cpp ------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "NoopAnalysis.h" +#include "TestingSupport.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include +#include +#include + +namespace { + +using namespace clang; +using namespace dataflow; +using ::testing::_; +using ::testing::ElementsAre; +using ::testing::IsNull; +using ::testing::NotNull; +using ::testing::Pair; + +class TransferTest : public ::testing::Test { +protected: + template + void runDataflow(llvm::StringRef Code, Matcher Match) { + test::checkDataflow( + Code, "target", + [](ASTContext &C, Environment &) { return NoopAnalysis(C); }, + [&Match](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { Match(Results, ASTCtx); }, + {"-fsyntax-only", "-std=c++17"}); + } +}; + +/// Returns the `ValueDecl` for the given identifier. +/// +/// Requirements: +/// +/// `Name` must be unique in `ASTCtx`. +static const ValueDecl *findValueDecl(ASTContext &ASTCtx, + llvm::StringRef Name) { + auto TargetNodes = ast_matchers::match( + ast_matchers::valueDecl(ast_matchers::hasName(Name)).bind("v"), ASTCtx); + assert(TargetNodes.size() == 1 && "Name must be unique"); + auto *const Result = ast_matchers::selectFirst("v", TargetNodes); + assert(Result != nullptr); + return Result; +} + +TEST_F(TransferTest, IntVarDecl) { + std::string Code = R"( + void target() { + int foo; + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); + + const Value *FooVal = Env.getValue(FooLoc); + ASSERT_TRUE(isa_and_nonnull(FooVal)); + }); +} + +TEST_F(TransferTest, FloatVarDecl) { + std::string Code = R"( + void target() { + float foo; + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const auto Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); + + const Value *FooVal = Env.getValue(FooLoc); + ASSERT_TRUE(isa_and_nonnull(FooVal)); + }); +} + +TEST_F(TransferTest, DoubleVarDecl) { + std::string Code = R"( + void target() { + double foo; + // [[p]] + } + )"; + runDataflow(Code, + [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); + + const Value *FooVal = Env.getValue(FooLoc); + ASSERT_TRUE(isa_and_nonnull(FooVal)); + }); +} + +TEST_F(TransferTest, StructVarDecl) { + std::string Code = R"( + struct Foo { + int Bar; + double Baz; + }; + + void target() { + Foo foo; + // [[p]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + ASSERT_TRUE(FooDecl->getType()->isStructureType()); + auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields(); + + FieldDecl *BarDecl = nullptr; + FieldDecl *BazDecl = nullptr; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else if (Field->getNameAsString() == "Baz") { + BazDecl = Field; + } + } + ASSERT_THAT(BarDecl, NotNull()); + ASSERT_THAT(BazDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(FooDecl)); + const auto *BarLoc = + cast(FooLoc->getChild(BarDecl)); + const auto *BazLoc = + cast(FooLoc->getChild(BazDecl)); + + const auto *FooVal = cast(Env.getValue(FooLoc)); + const auto *BarVal = cast(FooVal->getChild(BarDecl)); + const auto *BazVal = cast(FooVal->getChild(BazDecl)); + + ASSERT_EQ(Env.getValue(BarLoc), BarVal); + ASSERT_EQ(Env.getValue(BazLoc), BazVal); + }); +} + +TEST_F(TransferTest, ClassVarDecl) { + std::string Code = R"( + class Foo { + int Bar; + double Baz; + }; + + void target() { + Foo foo; + // [[p]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + ASSERT_TRUE(FooDecl->getType()->isClassType()); + auto FooFields = FooDecl->getType()->getAsRecordDecl()->fields(); + + FieldDecl *BarDecl = nullptr; + FieldDecl *BazDecl = nullptr; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else if (Field->getNameAsString() == "Baz") { + BazDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(BarDecl, NotNull()); + ASSERT_THAT(BazDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(FooDecl)); + const auto *BarLoc = + cast(FooLoc->getChild(BarDecl)); + const auto *BazLoc = + cast(FooLoc->getChild(BazDecl)); + + const auto *FooVal = cast(Env.getValue(FooLoc)); + const auto *BarVal = cast(FooVal->getChild(BarDecl)); + const auto *BazVal = cast(FooVal->getChild(BazDecl)); + + ASSERT_EQ(Env.getValue(BarLoc), BarVal); + ASSERT_EQ(Env.getValue(BazLoc), BazVal); + }); +} + +TEST_F(TransferTest, ReferenceVarDecl) { + std::string Code = R"( + struct Foo {}; + + Foo& getFoo(); + + void target() { + Foo& foo = getFoo(); + // [[p]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); + + const ReferenceValue *FooVal = + cast(Env.getValue(FooLoc)); + const StorageLocation *FooPointeeLoc = FooVal->getLocation(); + ASSERT_TRUE(isa_and_nonnull(FooPointeeLoc)); + + const Value *FooPointeeVal = Env.getValue(FooPointeeLoc); + ASSERT_TRUE(isa_and_nonnull(FooPointeeVal)); + }); +} + +TEST_F(TransferTest, SelfReferentialReferenceVarDecl) { + std::string Code = R"( + struct Foo; + + struct Baz {}; + + struct Bar { + Foo& FooRef; + Foo* FooPtr; + Baz& BazRef; + Baz* BazPtr; + }; + + struct Foo { + Bar& Bar; + }; + + Foo& getFoo(); + + void target() { + Foo& foo = getFoo(); + // [[p]] + } + )"; + runDataflow(Code, [](llvm::ArrayRef>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + ASSERT_TRUE(FooDecl->getType()->isReferenceType()); + ASSERT_TRUE(FooDecl->getType().getNonReferenceType()->isStructureType()); + const auto FooFields = + FooDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields(); + + FieldDecl *BarDecl = nullptr; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(BarDecl, NotNull()); + + ASSERT_TRUE(BarDecl->getType()->isReferenceType()); + ASSERT_TRUE(BarDecl->getType().getNonReferenceType()->isStructureType()); + const auto BarFields = + BarDecl->getType().getNonReferenceType()->getAsRecordDecl()->fields(); + + FieldDecl *FooRefDecl = nullptr; + FieldDecl *FooPtrDecl = nullptr; + FieldDecl *BazRefDecl = nullptr; + FieldDecl *BazPtrDecl = nullptr; + for (FieldDecl *Field : BarFields) { + if (Field->getNameAsString() == "FooRef") { + FooRefDecl = Field; + } else if (Field->getNameAsString() == "FooPtr") { + FooPtrDecl = Field; + } else if (Field->getNameAsString() == "BazRef") { + BazRefDecl = Field; + } else if (Field->getNameAsString() == "BazPtr") { + BazPtrDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(FooRefDecl, NotNull()); + ASSERT_THAT(FooPtrDecl, NotNull()); + ASSERT_THAT(BazRefDecl, NotNull()); + ASSERT_THAT(BazPtrDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(FooDecl)); + const auto *FooVal = cast(Env.getValue(FooLoc)); + const auto *FooPointeeVal = + cast(Env.getValue(FooVal->getLocation())); + + const auto *BarVal = cast(FooPointeeVal->getChild(BarDecl)); + const auto *BarPointeeVal = + cast(Env.getValue(BarVal->getLocation())); + + const auto *FooRefVal = + cast(BarPointeeVal->getChild(FooRefDecl)); + const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation(); + ASSERT_THAT(FooRefPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull()); + + const auto *FooPtrVal = + cast(BarPointeeVal->getChild(FooPtrDecl)); + const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation(); + ASSERT_THAT(FooPtrPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull()); + + const auto *BazRefVal = + cast(BarPointeeVal->getChild(BazRefDecl)); + const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation(); + ASSERT_THAT(BazRefPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull()); + + const auto *BazPtrVal = + cast(BarPointeeVal->getChild(BazPtrDecl)); + const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation(); + ASSERT_THAT(BazPtrPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull()); + }); +} + +TEST_F(TransferTest, PointerVarDecl) { + std::string Code = R"( + struct Foo {}; + + Foo* getFoo(); + + void target() { + Foo* foo = getFoo(); + // [[p]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const StorageLocation *FooLoc = Env.getStorageLocation(FooDecl); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); + + const PointerValue *FooVal = cast(Env.getValue(FooLoc)); + const StorageLocation *FooPointeeLoc = FooVal->getLocation(); + ASSERT_TRUE(isa_and_nonnull(FooPointeeLoc)); + + const Value *FooPointeeVal = Env.getValue(FooPointeeLoc); + ASSERT_TRUE(isa_and_nonnull(FooPointeeVal)); + }); +} + +TEST_F(TransferTest, SelfReferentialPointerVarDecl) { + std::string Code = R"( + struct Foo; + + struct Baz {}; + + struct Bar { + Foo& FooRef; + Foo* FooPtr; + Baz& BazRef; + Baz* BazPtr; + }; + + struct Foo { + Bar* Bar; + }; + + Foo* getFoo(); + + void target() { + Foo* foo = getFoo(); + // [[p]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p", _))); + const Environment &Env = Results[0].second.Env; + + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + ASSERT_TRUE(FooDecl->getType()->isPointerType()); + ASSERT_TRUE(FooDecl->getType() + ->getAs() + ->getPointeeType() + ->isStructureType()); + const auto FooFields = FooDecl->getType() + ->getAs() + ->getPointeeType() + ->getAsRecordDecl() + ->fields(); + + FieldDecl *BarDecl = nullptr; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(BarDecl, NotNull()); + + ASSERT_TRUE(BarDecl->getType()->isPointerType()); + ASSERT_TRUE(BarDecl->getType() + ->getAs() + ->getPointeeType() + ->isStructureType()); + const auto BarFields = BarDecl->getType() + ->getAs() + ->getPointeeType() + ->getAsRecordDecl() + ->fields(); + + FieldDecl *FooRefDecl = nullptr; + FieldDecl *FooPtrDecl = nullptr; + FieldDecl *BazRefDecl = nullptr; + FieldDecl *BazPtrDecl = nullptr; + for (FieldDecl *Field : BarFields) { + if (Field->getNameAsString() == "FooRef") { + FooRefDecl = Field; + } else if (Field->getNameAsString() == "FooPtr") { + FooPtrDecl = Field; + } else if (Field->getNameAsString() == "BazRef") { + BazRefDecl = Field; + } else if (Field->getNameAsString() == "BazPtr") { + BazPtrDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(FooRefDecl, NotNull()); + ASSERT_THAT(FooPtrDecl, NotNull()); + ASSERT_THAT(BazRefDecl, NotNull()); + ASSERT_THAT(BazPtrDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(FooDecl)); + const auto *FooVal = cast(Env.getValue(FooLoc)); + const auto *FooPointeeVal = + cast(Env.getValue(FooVal->getLocation())); + + const auto *BarVal = + cast(FooPointeeVal->getChild(BarDecl)); + const auto *BarPointeeVal = + cast(Env.getValue(BarVal->getLocation())); + + const auto *FooRefVal = + cast(BarPointeeVal->getChild(FooRefDecl)); + const StorageLocation *FooRefPointeeLoc = FooRefVal->getLocation(); + ASSERT_THAT(FooRefPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull()); + + const auto *FooPtrVal = + cast(BarPointeeVal->getChild(FooPtrDecl)); + const StorageLocation *FooPtrPointeeLoc = FooPtrVal->getLocation(); + ASSERT_THAT(FooPtrPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull()); + + const auto *BazRefVal = + cast(BarPointeeVal->getChild(BazRefDecl)); + const StorageLocation *BazRefPointeeLoc = BazRefVal->getLocation(); + ASSERT_THAT(BazRefPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull()); + + const auto *BazPtrVal = + cast(BarPointeeVal->getChild(BazPtrDecl)); + const StorageLocation *BazPtrPointeeLoc = BazPtrVal->getLocation(); + ASSERT_THAT(BazPtrPointeeLoc, NotNull()); + ASSERT_THAT(Env.getValue(BazPtrPointeeLoc), NotNull()); + }); +} + +TEST_F(TransferTest, JoinVarDecl) { + std::string Code = R"( + void target(bool b) { + int foo; + // [[p1]] + if (b) { + int bar; + // [[p2]] + } else { + int baz; + // [[p3]] + } + (void)0; + // [[p4]] + } + )"; + runDataflow( + Code, [](llvm::ArrayRef< + std::pair>> + Results, + ASTContext &ASTCtx) { + ASSERT_THAT(Results, ElementsAre(Pair("p4", _), Pair("p3", _), + Pair("p2", _), Pair("p1", _))); + const ValueDecl *FooDecl = findValueDecl(ASTCtx, "foo"); + ASSERT_THAT(FooDecl, NotNull()); + + const ValueDecl *BarDecl = findValueDecl(ASTCtx, "bar"); + ASSERT_THAT(BarDecl, NotNull()); + + const ValueDecl *BazDecl = findValueDecl(ASTCtx, "baz"); + ASSERT_THAT(BazDecl, NotNull()); + + const Environment &Env1 = Results[3].second.Env; + const StorageLocation *FooLoc = Env1.getStorageLocation(FooDecl); + ASSERT_THAT(FooLoc, NotNull()); + ASSERT_THAT(Env1.getStorageLocation(BarDecl), IsNull()); + ASSERT_THAT(Env1.getStorageLocation(BazDecl), IsNull()); + + const Environment &Env2 = Results[2].second.Env; + ASSERT_EQ(Env2.getStorageLocation(FooDecl), FooLoc); + ASSERT_THAT(Env2.getStorageLocation(BarDecl), NotNull()); + ASSERT_THAT(Env2.getStorageLocation(BazDecl), IsNull()); + + const Environment &Env3 = Results[1].second.Env; + ASSERT_EQ(Env3.getStorageLocation(FooDecl), FooLoc); + ASSERT_THAT(Env3.getStorageLocation(BarDecl), IsNull()); + ASSERT_THAT(Env3.getStorageLocation(BazDecl), NotNull()); + + const Environment &Env4 = Results[0].second.Env; + ASSERT_EQ(Env4.getStorageLocation(FooDecl), FooLoc); + ASSERT_THAT(Env4.getStorageLocation(BarDecl), IsNull()); + ASSERT_THAT(Env4.getStorageLocation(BazDecl), IsNull()); + }); +} + +} // namespace diff --git a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp @@ -6,12 +6,14 @@ // //===----------------------------------------------------------------------===// +#include "NoopAnalysis.h" #include "TestingSupport.h" #include "clang/AST/Decl.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/ASTMatchers/ASTMatchers.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" #include "clang/Analysis/FlowSensitive/DataflowLattice.h" #include "clang/Tooling/Tooling.h" @@ -28,6 +30,8 @@ #include #include +namespace { + using namespace clang; using namespace dataflow; using ::testing::IsEmpty; @@ -50,7 +54,8 @@ ControlFlowContext::build(nullptr, Body, Result.Context)); AnalysisT Analysis(*Result.Context); - Environment Env; + DataflowAnalysisContext DACtx; + Environment Env(DACtx); BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env); } @@ -75,27 +80,6 @@ return Callback.BlockStates; } -class NoopLattice { -public: - bool operator==(const NoopLattice &) const { return true; } - - LatticeJoinEffect join(const NoopLattice &) { - return LatticeJoinEffect::Unchanged; - } -}; - -class NoopAnalysis : public DataflowAnalysis { -public: - NoopAnalysis(ASTContext &Context) - : DataflowAnalysis(Context) {} - - static NoopLattice initialElement() { return {}; } - - NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) { - return {}; - } -}; - TEST(DataflowAnalysisTest, NoopAnalysis) { auto BlockStates = runAnalysis(R"( void target() {} @@ -314,3 +298,5 @@ UnorderedElementsAre("baz", "foo")))))); // FIXME: Called functions at point `p` should contain only "foo". } + +} // namespace