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 context that +/// is used during dataflow analysis. +class DataflowAnalysisContext { +public: + /// Takes ownership of `Loc` and returns a reference 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 reference to it. + /// + /// Requirements: + /// + /// `Val` must not be null. + Value &takeOwnership(std::unique_ptr Val) { + assert(Val != nullptr); + Vals.push_back(std::move(Val)); + return *Vals.back().get(); + } + + /// Assigns `Loc` as the storage location of `D`. + /// + /// Requirements: + /// + /// `D` must not be assigned a storage location. + void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { + assert(DeclToLoc.find(&D) == DeclToLoc.end()); + DeclToLoc[&D] = &Loc; + } + + /// Returns the storage location assigned to `D` or null if `D` has no + /// assigned storage location. + StorageLocation *getStorageLocation(const ValueDecl &D) const { + auto It = DeclToLoc.find(&D); + return It == DeclToLoc.end() ? nullptr : It->second; + } + +private: + // Storage for the state of a program. + std::vector> Locs; + std::vector> Vals; + + // Maps from program declarations and statements to storage locations that are + // assigned to them. These assignments are global (aggregated across all basic + // blocks) and are used to produce stable storage locations when the same + // basic blocks are evaluated multiple times. The storage locations that are + // in scope for a particular basic block are stored in `Environment`. + llvm::DenseMap DeclToLoc; + // FIXME: Add `Expr` to `StorageLocation` map. + + // FIXME: Add `StorageLocation` for `this`. + + // FIXME: Add support for boolean expressions. +}; + +} // 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,81 @@ /// 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. + /// + /// Requirements: + /// + /// `Type` must not be null. + StorageLocation &createStorageLocation(QualType Type); + + /// Creates a storage location for `D`. Does not assign the returned storage + /// location to `D` in the environment. Does not assign a value to the + /// returned storage location in the environment. + StorageLocation &createStorageLocation(const VarDecl &D); + + /// Assigns `Loc` as the storage location of `D` in the environment. + /// + /// Requirements: + /// + /// `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. + StorageLocation *getStorageLocation(const ValueDecl &D) const; + + /// Creates a value appropriate for `Type`, assigns it to `Loc`, and returns + /// it, if `Type` is supported, otherwise return null. 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: + /// + /// `Type` must not be null. + Value *initValueInStorageLocation(const StorageLocation &Loc, QualType Type); + + /// Assigns `Val` as the value of `Loc` in the environment. + 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. + Value *getValue(const StorageLocation &Loc) const; + +private: + /// Returns the value assigned to `Loc` in the environment or null if `Type` + /// isn't supported. + /// + /// Recursively initializes storage locations and values until 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: + /// + /// `Type` must not be null. + Value *initValueInStorageLocationUnlessSelfReferential( + const StorageLocation &Loc, QualType Type, + llvm::DenseSet &Visited); + + DataflowAnalysisContext *DACtx; + + // Maps from program declarations and statements to storage locations that are + // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these + // include only storage locations that are in scope for a particular basic + // block. + llvm::DenseMap DeclToLoc; + // FIXME: Add `Expr` to `StorageLocation` map. + + llvm::DenseMap LocToVal; + + // FIXME: Add flow condition constraints. }; } // 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,89 @@ +//===-- 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`. + StorageLocation &getChild(const ValueDecl &D) const { + auto It = Children.find(&D); + assert(It != Children.end()); + 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,33 @@ +//===-- 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. +/// +/// Requirements: +/// +/// The type of `S` must not be `ParenExpr`. +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,117 @@ +//===-- 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, Reference, Pointer, Struct }; + + explicit Value(Kind ValKind) : ValKind(ValKind) {} + + virtual ~Value() = default; + + Kind getKind() const { return ValKind; } + +private: + Kind ValKind; +}; + +/// Models an integer. +class IntegerValue : public Value { +public: + explicit IntegerValue() : Value(Kind::Integer) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Integer; + } +}; + +/// Base class for values that refer to storage locations. +class IndirectionValue : public Value { +public: + /// Constructs a value that refers to `PointeeLoc`. + explicit IndirectionValue(Kind ValueKind, StorageLocation &PointeeLoc) + : Value(ValueKind), PointeeLoc(PointeeLoc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Reference || Val->getKind() == Kind::Pointer; + } + + StorageLocation &getPointeeLoc() const { return PointeeLoc; } + +private: + StorageLocation &PointeeLoc; +}; + +/// Models a dereferenced pointer. For example, a reference in C++ or an lvalue +/// in C. +class ReferenceValue final : public IndirectionValue { +public: + explicit ReferenceValue(StorageLocation &PointeeLoc) + : IndirectionValue(Kind::Reference, PointeeLoc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Reference; + } +}; + +/// Models a symbolic pointer. Specifically, any value of type `T*`. +class PointerValue final : public IndirectionValue { +public: + explicit PointerValue(StorageLocation &PointeeLoc) + : IndirectionValue(Kind::Pointer, PointeeLoc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Pointer; + } +}; + +/// 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`. + Value &getChild(const ValueDecl &D) const { + auto It = Children.find(&D); + assert(It != Children.end()); + 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,191 @@ +//===-- 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 +#include + +namespace clang { +namespace dataflow { + +/// 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) + Result.insert({Entry.first, Entry.second}); + } + return Result; +} + +bool Environment::operator==(const Environment &Other) const { + assert(DACtx == Other.DACtx); + return DeclToLoc == Other.DeclToLoc && 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; + + // FIXME: Add support for joining distinct values that are assigned to the + // same storage locations in `LocToVal` and `Other.LocToVal`. + const unsigned LocToValSizeBefore = LocToVal.size(); + LocToVal = intersectDenseMaps(LocToVal, Other.LocToVal); + if (LocToValSizeBefore != LocToVal.size()) + Effect = LatticeJoinEffect::Changed; + + return Effect; +} + +StorageLocation &Environment::createStorageLocation(QualType Type) { + assert(!Type.isNull()); + if (Type->isStructureOrClassType()) { + // FIXME: Explore options to avoid eager initialization of fields as some of + // them might not be needed for a particular analysis. + 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) { + // 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(DeclToLoc.find(&D) == DeclToLoc.end()); + DeclToLoc[&D] = &Loc; +} + +StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const { + auto It = DeclToLoc.find(&D); + return It == DeclToLoc.end() ? nullptr : It->second; +} + +void Environment::setValue(const StorageLocation &Loc, Value &Value) { + LocToVal[&Loc] = &Value; +} + +Value *Environment::getValue(const StorageLocation &Loc) const { + auto It = LocToVal.find(&Loc); + return It == LocToVal.end() ? nullptr : It->second; +} + +Value *Environment::initValueInStorageLocation(const StorageLocation &Loc, + QualType Type) { + llvm::DenseSet Visited; + return initValueInStorageLocationUnlessSelfReferential(Loc, Type, Visited); +} + +Value *Environment::initValueInStorageLocationUnlessSelfReferential( + const StorageLocation &Loc, QualType Type, + llvm::DenseSet &Visited) { + assert(!Type.isNull()); + + if (Type->isIntegerType()) { + 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.getCanonicalType())) { + Visited.insert(PointeeType.getCanonicalType()); + initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType, + Visited); + Visited.erase(PointeeType.getCanonicalType()); + } + + 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.getCanonicalType())) { + Visited.insert(PointeeType.getCanonicalType()); + initValueInStorageLocationUnlessSelfReferential(PointeeLoc, PointeeType, + Visited); + Visited.erase(PointeeType.getCanonicalType()); + } + + 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()) { + assert(Field != nullptr); + + QualType FieldType = Field->getType(); + if (Visited.contains(FieldType.getCanonicalType())) + continue; + + Visited.insert(FieldType.getCanonicalType()); + FieldValues.insert( + {Field, initValueInStorageLocationUnlessSelfReferential( + AggregateLoc->getChild(*Field), FieldType, Visited)}); + Visited.erase(FieldType.getCanonicalType()); + } + + 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,72 @@ +//===-- 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/AST/StmtVisitor.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "llvm/Support/Casting.h" +#include + +namespace clang { +namespace dataflow { + +class TransferVisitor : public ConstStmtVisitor { +public: + TransferVisitor(Environment &Env) : Env(Env) {} + + void VisitDeclStmt(const DeclStmt *S) { + // FIXME: Add support for group decls, e.g: `int a, b;` + if (S->isSingleDecl()) { + if (const auto *D = dyn_cast(S->getSingleDecl())) { + visitVarDecl(*D); + } + } + } + + // FIXME: Add support for: + // - BinaryOperator + // - CallExpr + // - CXXBindTemporaryExpr + // - CXXBoolLiteralExpr + // - CXXConstructExpr + // - CXXFunctionalCastExpr + // - CXXOperatorCallExpr + // - CXXStaticCastExpr + // - CXXThisExpr + // - DeclRefExpr + // - ImplicitCastExpr + // - MaterializeTemporaryExpr + // - MemberExpr + // - UnaryOperator + +private: + void visitVarDecl(const VarDecl &D) { + auto &Loc = Env.createStorageLocation(D); + Env.setStorageLocation(D, Loc); + Env.initValueInStorageLocation(Loc, D.getType()); + } + + Environment &Env; +}; + +void transfer(const Stmt &S, Environment &Env) { + assert(!isa(&S)); + TransferVisitor(Env).Visit(&S); +} + +} // 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,18 @@ 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(); + assert(S != nullptr); + + 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,540 @@ +//===- 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, StructVarDecl) { + std::string Code = R"( + struct Foo { + int Bar; + }; + + 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; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(BarDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(*FooDecl)); + const auto *BarLoc = + cast(&FooLoc->getChild(*BarDecl)); + + const auto *FooVal = cast(Env.getValue(*FooLoc)); + const auto *BarVal = cast(&FooVal->getChild(*BarDecl)); + ASSERT_EQ(Env.getValue(*BarLoc), BarVal); + }); +} + +TEST_F(TransferTest, ClassVarDecl) { + std::string Code = R"( + class Foo { + int Bar; + }; + + 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; + for (FieldDecl *Field : FooFields) { + if (Field->getNameAsString() == "Bar") { + BarDecl = Field; + } else { + FAIL() << "Unexpected field: " << Field->getNameAsString(); + } + } + ASSERT_THAT(BarDecl, NotNull()); + + const auto *FooLoc = + cast(Env.getStorageLocation(*FooDecl)); + const auto *BarLoc = + cast(&FooLoc->getChild(*BarDecl)); + + const auto *FooVal = cast(Env.getValue(*FooLoc)); + const auto *BarVal = cast(&FooVal->getChild(*BarDecl)); + ASSERT_EQ(Env.getValue(*BarLoc), BarVal); + }); +} + +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->getPointeeLoc(); + ASSERT_TRUE(isa(&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->getPointeeLoc())); + + const auto *BarVal = + cast(&FooPointeeVal->getChild(*BarDecl)); + const auto *BarPointeeVal = + cast(Env.getValue(BarVal->getPointeeLoc())); + + const auto *FooRefVal = + cast(&BarPointeeVal->getChild(*FooRefDecl)); + const StorageLocation &FooRefPointeeLoc = FooRefVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull()); + + const auto *FooPtrVal = + cast(&BarPointeeVal->getChild(*FooPtrDecl)); + const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull()); + + const auto *BazRefVal = + cast(&BarPointeeVal->getChild(*BazRefDecl)); + const StorageLocation &BazRefPointeeLoc = BazRefVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull()); + + const auto *BazPtrVal = + cast(&BarPointeeVal->getChild(*BazPtrDecl)); + const StorageLocation &BazPtrPointeeLoc = BazPtrVal->getPointeeLoc(); + 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->getPointeeLoc(); + ASSERT_TRUE(isa(&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->getPointeeLoc())); + + const auto *BarVal = + cast(&FooPointeeVal->getChild(*BarDecl)); + const auto *BarPointeeVal = + cast(Env.getValue(BarVal->getPointeeLoc())); + + const auto *FooRefVal = + cast(&BarPointeeVal->getChild(*FooRefDecl)); + const StorageLocation &FooRefPointeeLoc = FooRefVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(FooRefPointeeLoc), IsNull()); + + const auto *FooPtrVal = + cast(&BarPointeeVal->getChild(*FooPtrDecl)); + const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull()); + + const auto *BazRefVal = + cast(&BarPointeeVal->getChild(*BazRefDecl)); + const StorageLocation &BazRefPointeeLoc = BazRefVal->getPointeeLoc(); + ASSERT_THAT(Env.getValue(BazRefPointeeLoc), NotNull()); + + const auto *BazPtrVal = + cast(&BarPointeeVal->getChild(*BazPtrDecl)); + const StorageLocation &BazPtrPointeeLoc = BazPtrVal->getPointeeLoc(); + 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