llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-analysis Author: Samira Bazuzi (bazuzi) <details> <summary>Changes</summary> Moves free functions from DataflowEnvironment.h/cc and DataflowAnalysisContext.h/cc to RecordOps and a new ASTOps and exposes them as needed for current use and to expose getReferencedDecls for out-of-tree use. Minimal change in functionality, only to modify the return type of getReferenceDecls to return the collected decls instead of using output params. Tested with `ninja check-clang-tooling`. This started as #<!-- -->88534, but I screwed up the push of changes after a first round of comments and needed to close that PR to avoid spam for recent commit authors. I believe all of the first round comments have been addressed and should be considered marked "Done" and resolved. --- Patch is 31.75 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/88754.diff 10 Files Affected: - (added) clang/include/clang/Analysis/FlowSensitive/ASTOps.h (+75) - (modified) clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h (+1-27) - (modified) clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h (-36) - (modified) clang/include/clang/Analysis/FlowSensitive/RecordOps.h (+29) - (added) clang/lib/Analysis/FlowSensitive/ASTOps.cpp (+214) - (modified) clang/lib/Analysis/FlowSensitive/CMakeLists.txt (+1) - (modified) clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp (+1-52) - (modified) clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp (+6-172) - (modified) clang/lib/Analysis/FlowSensitive/RecordOps.cpp (+37) - (modified) clang/lib/Analysis/FlowSensitive/Transfer.cpp (+2) ``````````diff diff --git a/clang/include/clang/Analysis/FlowSensitive/ASTOps.h b/clang/include/clang/Analysis/FlowSensitive/ASTOps.h new file mode 100644 index 00000000000000..5e3c0f21f5e863 --- /dev/null +++ b/clang/include/clang/Analysis/FlowSensitive/ASTOps.h @@ -0,0 +1,75 @@ +//===-- ASTOps.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 +// +//===----------------------------------------------------------------------===// +// +// Operations on AST nodes that are used in flow-sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ASTOPS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ASTOPS_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SetVector.h" + +namespace clang { +namespace dataflow { +/// Skip past nodes that the CFG does not emit. These nodes are invisible to +/// flow-sensitive analysis, and should be ignored as they will effectively not +/// exist. +/// +/// * `ParenExpr` - The CFG takes the operator precedence into account, but +/// otherwise omits the node afterwards. +/// +/// * `ExprWithCleanups` - The CFG will generate the appropriate calls to +/// destructors and then omit the node. +/// +const Expr &ignoreCFGOmittedNodes(const Expr &E); +const Stmt &ignoreCFGOmittedNodes(const Stmt &S); + +/// A set of `FieldDecl *`. Use `SmallSetVector` to guarantee deterministic +/// iteration order. +using FieldSet = llvm::SmallSetVector<const FieldDecl *, 4>; + +/// Returns the set of all fields in the type. +FieldSet getObjectFields(QualType Type); + +/// Returns whether `Fields` and `FieldLocs` contain the same fields. +bool containsSameFields(const FieldSet &Fields, + const RecordStorageLocation::FieldToLoc &FieldLocs); + +/// Returns the fields of a `RecordDecl` that are initialized by an +/// `InitListExpr`, in the order in which they appear in +/// `InitListExpr::inits()`. +/// `Init->getType()` must be a record type. +std::vector<const FieldDecl *> +getFieldsForInitListExpr(const InitListExpr *InitList); + +// A collection of several types of declarations, all referenced from the same +// function. +struct ReferencedDecls { + // Fields includes non-static data members. + FieldSet Fields; + // Globals includes all variables with global storage, notably including + // static data members and static variables declared within a function. + llvm::DenseSet<const VarDecl *> Globals; + // Functions includes free functions and member functions which are + // referenced, but not necessarily called. + llvm::DenseSet<const FunctionDecl *> Functions; +}; + +/// Collects and returns fields, global variables and functions that are +/// declared in or referenced from `FD`. +ReferencedDecls getReferencedDecls(const FunctionDecl &FD); +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_ASTOPS_H diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h index 909a91059438ca..aa2c366cb164a9 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -18,6 +18,7 @@ #include "clang/AST/Decl.h" #include "clang/AST/Expr.h" #include "clang/AST/TypeOrdering.h" +#include "clang/Analysis/FlowSensitive/ASTOps.h" #include "clang/Analysis/FlowSensitive/AdornedCFG.h" #include "clang/Analysis/FlowSensitive/Arena.h" #include "clang/Analysis/FlowSensitive/Solver.h" @@ -30,38 +31,11 @@ #include <cassert> #include <memory> #include <optional> -#include <type_traits> -#include <utility> -#include <vector> namespace clang { namespace dataflow { class Logger; -/// Skip past nodes that the CFG does not emit. These nodes are invisible to -/// flow-sensitive analysis, and should be ignored as they will effectively not -/// exist. -/// -/// * `ParenExpr` - The CFG takes the operator precedence into account, but -/// otherwise omits the node afterwards. -/// -/// * `ExprWithCleanups` - The CFG will generate the appropriate calls to -/// destructors and then omit the node. -/// -const Expr &ignoreCFGOmittedNodes(const Expr &E); -const Stmt &ignoreCFGOmittedNodes(const Stmt &S); - -/// A set of `FieldDecl *`. Use `SmallSetVector` to guarantee deterministic -/// iteration order. -using FieldSet = llvm::SmallSetVector<const FieldDecl *, 4>; - -/// Returns the set of all fields in the type. -FieldSet getObjectFields(QualType Type); - -/// Returns whether `Fields` and `FieldLocs` contain the same fields. -bool containsSameFields(const FieldSet &Fields, - const RecordStorageLocation::FieldToLoc &FieldLocs); - struct ContextSensitiveOptions { /// The maximum depth to analyze. A value of zero is equivalent to disabling /// context-sensitive analysis entirely. diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index 706664d7db1c25..4277792219c0af 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -775,42 +775,6 @@ RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, const Environment &Env); -/// Returns the fields of a `RecordDecl` that are initialized by an -/// `InitListExpr`, in the order in which they appear in -/// `InitListExpr::inits()`. -/// `Init->getType()` must be a record type. -std::vector<const FieldDecl *> -getFieldsForInitListExpr(const InitListExpr *InitList); - -/// Helper class for initialization of a record with an `InitListExpr`. -/// `InitListExpr::inits()` contains the initializers for both the base classes -/// and the fields of the record; this helper class separates these out into two -/// different lists. In addition, it deals with special cases associated with -/// unions. -class RecordInitListHelper { -public: - // `InitList` must have record type. - RecordInitListHelper(const InitListExpr *InitList); - - // Base classes with their associated initializer expressions. - ArrayRef<std::pair<const CXXBaseSpecifier *, Expr *>> base_inits() const { - return BaseInits; - } - - // Fields with their associated initializer expressions. - ArrayRef<std::pair<const FieldDecl *, Expr *>> field_inits() const { - return FieldInits; - } - -private: - SmallVector<std::pair<const CXXBaseSpecifier *, Expr *>> BaseInits; - SmallVector<std::pair<const FieldDecl *, Expr *>> FieldInits; - - // We potentially synthesize an `ImplicitValueInitExpr` for unions. It's a - // member variable because we store a pointer to it in `FieldInits`. - std::optional<ImplicitValueInitExpr> ImplicitValueInitForUnion; -}; - /// Associates a new `RecordValue` with `Loc` and returns the new value. RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env); diff --git a/clang/include/clang/Analysis/FlowSensitive/RecordOps.h b/clang/include/clang/Analysis/FlowSensitive/RecordOps.h index 8fad45fc11d81e..92c5722d60fbca 100644 --- a/clang/include/clang/Analysis/FlowSensitive/RecordOps.h +++ b/clang/include/clang/Analysis/FlowSensitive/RecordOps.h @@ -66,6 +66,35 @@ inline bool recordsEqual(const RecordStorageLocation &Loc1, return recordsEqual(Loc1, Env, Loc2, Env); } +/// Helper class for initialization of a record with an `InitListExpr`. +/// `InitListExpr::inits()` contains the initializers for both the base classes +/// and the fields of the record; this helper class separates these out into two +/// different lists. In addition, it deals with special cases associated with +/// unions. +class RecordInitListHelper { +public: + // `InitList` must have record type. + RecordInitListHelper(const InitListExpr *InitList); + + // Base classes with their associated initializer expressions. + ArrayRef<std::pair<const CXXBaseSpecifier *, Expr *>> base_inits() const { + return BaseInits; + } + + // Fields with their associated initializer expressions. + ArrayRef<std::pair<const FieldDecl *, Expr *>> field_inits() const { + return FieldInits; + } + +private: + SmallVector<std::pair<const CXXBaseSpecifier *, Expr *>> BaseInits; + SmallVector<std::pair<const FieldDecl *, Expr *>> FieldInits; + + // We potentially synthesize an `ImplicitValueInitExpr` for unions. It's a + // member variable because we store a pointer to it in `FieldInits`. + std::optional<ImplicitValueInitExpr> ImplicitValueInitForUnion; +}; + } // namespace dataflow } // namespace clang diff --git a/clang/lib/Analysis/FlowSensitive/ASTOps.cpp b/clang/lib/Analysis/FlowSensitive/ASTOps.cpp new file mode 100644 index 00000000000000..35fadaeeb9c7c4 --- /dev/null +++ b/clang/lib/Analysis/FlowSensitive/ASTOps.cpp @@ -0,0 +1,214 @@ +//===-- ASTOps.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 +// +//===----------------------------------------------------------------------===// +// +// Operations on AST nodes that are used in flow-sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/FlowSensitive/ASTOps.h" +#include "clang/AST/ComputeDependence.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" +#include <cassert> +#include <iterator> +#include <vector> + +#define DEBUG_TYPE "dataflow" + +namespace clang::dataflow { +std::vector<const FieldDecl *> +getFieldsForInitListExpr(const InitListExpr *InitList) { + const RecordDecl *RD = InitList->getType()->getAsRecordDecl(); + assert(RD != nullptr); + + std::vector<const FieldDecl *> Fields; + + if (InitList->getType()->isUnionType()) { + Fields.push_back(InitList->getInitializedFieldInUnion()); + return Fields; + } + + // Unnamed bitfields are only used for padding and do not appear in + // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s + // field list, and we thus need to remove them before mapping inits to + // fields to avoid mapping inits to the wrongs fields. + llvm::copy_if( + RD->fields(), std::back_inserter(Fields), + [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); }); + return Fields; +} + +static void insertIfGlobal(const Decl &D, + llvm::DenseSet<const VarDecl *> &Vars) { + if (auto *V = dyn_cast<VarDecl>(&D)) + if (V->hasGlobalStorage()) + Vars.insert(V); +} + +static void insertIfFunction(const Decl &D, + llvm::DenseSet<const FunctionDecl *> &Funcs) { + if (auto *FD = dyn_cast<FunctionDecl>(&D)) + Funcs.insert(FD); +} + +static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) { + // Use getCalleeDecl instead of getMethodDecl in order to handle + // pointer-to-member calls. + const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl()); + if (!MethodDecl) + return nullptr; + auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody()); + if (!Body || Body->size() != 1) + return nullptr; + if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin())) + if (auto *Return = RS->getRetValue()) + return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts()); + return nullptr; +} + +static void getReferencedDecls(const Decl &D, FieldSet &Fields, + llvm::DenseSet<const VarDecl *> &Vars, + llvm::DenseSet<const FunctionDecl *> &Funcs) { + insertIfGlobal(D, Vars); + insertIfFunction(D, Funcs); + if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) + for (const auto *B : Decomp->bindings()) + if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) + // FIXME: should we be using `E->getFoundDecl()`? + if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl())) + Fields.insert(FD); +} + +/// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields, +/// global variables and functions that are declared in or referenced from +/// sub-statements. +static void getReferencedDecls(const Stmt &S, FieldSet &Fields, + llvm::DenseSet<const VarDecl *> &Vars, + llvm::DenseSet<const FunctionDecl *> &Funcs) { + for (auto *Child : S.children()) + if (Child != nullptr) + getReferencedDecls(*Child, Fields, Vars, Funcs); + if (const auto *DefaultArg = dyn_cast<CXXDefaultArgExpr>(&S)) + getReferencedDecls(*DefaultArg->getExpr(), Fields, Vars, Funcs); + if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S)) + getReferencedDecls(*DefaultInit->getExpr(), Fields, Vars, Funcs); + + if (auto *DS = dyn_cast<DeclStmt>(&S)) { + if (DS->isSingleDecl()) + getReferencedDecls(*DS->getSingleDecl(), Fields, Vars, Funcs); + else + for (auto *D : DS->getDeclGroup()) + getReferencedDecls(*D, Fields, Vars, Funcs); + } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) { + insertIfGlobal(*E->getDecl(), Vars); + insertIfFunction(*E->getDecl(), Funcs); + } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(&S)) { + // If this is a method that returns a member variable but does nothing else, + // model the field of the return value. + if (MemberExpr *E = getMemberForAccessor(*C)) + if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl())) + Fields.insert(FD); + } else if (auto *E = dyn_cast<MemberExpr>(&S)) { + // FIXME: should we be using `E->getFoundDecl()`? + const ValueDecl *VD = E->getMemberDecl(); + insertIfGlobal(*VD, Vars); + insertIfFunction(*VD, Funcs); + if (const auto *FD = dyn_cast<FieldDecl>(VD)) + Fields.insert(FD); + } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) { + if (InitList->getType()->isRecordType()) + for (const auto *FD : getFieldsForInitListExpr(InitList)) + Fields.insert(FD); + } +} + +ReferencedDecls getReferencedDecls(const FunctionDecl &FD) { + ReferencedDecls Result; + // Look for global variable and field references in the + // constructor-initializers. + if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&FD)) { + for (const auto *Init : CtorDecl->inits()) { + if (Init->isMemberInitializer()) { + Result.Fields.insert(Init->getMember()); + } else if (Init->isIndirectMemberInitializer()) { + for (const auto *I : Init->getIndirectMember()->chain()) + Result.Fields.insert(cast<FieldDecl>(I)); + } + const Expr *E = Init->getInit(); + assert(E != nullptr); + getReferencedDecls(*E, Result.Fields, Result.Globals, Result.Functions); + } + // Add all fields mentioned in default member initializers. + for (const FieldDecl *F : CtorDecl->getParent()->fields()) + if (const auto *I = F->getInClassInitializer()) + getReferencedDecls(*I, Result.Fields, Result.Globals, Result.Functions); + } + getReferencedDecls(*FD.getBody(), Result.Fields, Result.Globals, + Result.Functions); + + return Result; +} + +const Expr &ignoreCFGOmittedNodes(const Expr &E) { + const Expr *Current = &E; + if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) { + Current = EWC->getSubExpr(); + assert(Current != nullptr); + } + Current = Current->IgnoreParens(); + assert(Current != nullptr); + return *Current; +} + +const Stmt &ignoreCFGOmittedNodes(const Stmt &S) { + if (auto *E = dyn_cast<Expr>(&S)) + return ignoreCFGOmittedNodes(*E); + return S; +} + +// FIXME: Does not precisely handle non-virtual diamond inheritance. A single +// field decl will be modeled for all instances of the inherited field. +static void getFieldsFromClassHierarchy(QualType Type, FieldSet &Fields) { + if (Type->isIncompleteType() || Type->isDependentType() || + !Type->isRecordType()) + return; + + for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) + Fields.insert(Field); + if (auto *CXXRecord = Type->getAsCXXRecordDecl()) + for (const CXXBaseSpecifier &Base : CXXRecord->bases()) + getFieldsFromClassHierarchy(Base.getType(), Fields); +} + +/// Gets the set of all fields in the type. +FieldSet getObjectFields(QualType Type) { + FieldSet Fields; + getFieldsFromClassHierarchy(Type, Fields); + return Fields; +} + +bool containsSameFields(const FieldSet &Fields, + const RecordStorageLocation::FieldToLoc &FieldLocs) { + if (Fields.size() != FieldLocs.size()) + return false; + for ([[maybe_unused]] auto [Field, Loc] : FieldLocs) + if (!Fields.contains(cast_or_null<FieldDecl>(Field))) + return false; + return true; +} + +} // namespace clang::dataflow diff --git a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt index a3b5d9adc24bda..6631fe27f3d901 100644 --- a/clang/lib/Analysis/FlowSensitive/CMakeLists.txt +++ b/clang/lib/Analysis/FlowSensitive/CMakeLists.txt @@ -1,6 +1,7 @@ add_clang_library(clangAnalysisFlowSensitive AdornedCFG.cpp Arena.cpp + ASTOps.cpp DataflowAnalysisContext.cpp DataflowEnvironment.cpp Formula.cpp diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp index d520539dd25355..e94fd39c45dc15 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -14,6 +14,7 @@ #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" #include "clang/AST/ExprCXX.h" +#include "clang/Analysis/FlowSensitive/ASTOps.h" #include "clang/Analysis/FlowSensitive/DebugSupport.h" #include "clang/Analysis/FlowSensitive/Formula.h" #include "clang/Analysis/FlowSensitive/Logger.h" @@ -359,55 +360,3 @@ DataflowAnalysisContext::~DataflowAnalysisContext() = default; } // namespace dataflow } // namespace clang - -using namespace clang; - -const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) { - const Expr *Current = &E; - if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) { - Current = EWC->getSubExpr(); - assert(Current != nullptr); - } - Current = Current->IgnoreParens(); - assert(Current != nullptr); - return *Current; -} - -const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) { - if (auto *E = dyn_cast<Expr>(&S)) - return ignoreCFGOmittedNodes(*E); - return S; -} - -// FIXME: Does not precisely handle non-virtual diamond inheritance. A single -// field decl will be modeled for all instances of the inherited field. -static void getFieldsFromClassHierarchy(QualType Type, - clang::dataflow::FieldSet &Fields) { - if (Type->isIncompleteType() || Type->isDependentType() || - !Type->isRecordType()) - return; - - for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) - Fields.insert(Field); - if (auto *CXXRecord = Type->getAsCXXRecordDecl()) - for (const CXXBaseSpecifier &Base : CXXRecord->bases()) - getFieldsFromClassHierarchy(Base.getType(), Fields); -} - -/// Gets the set of all fields in the type. -clang::dataflow::FieldSet clang::dataflow::getObjectFields(QualType Type) { - FieldSet Fields; - getFieldsFromClassHierarchy(Type, Fields); - return Fields; -} - -bool clang::dataflow::containsSameFields( - const clang::dataflow::FieldSet &Fields, - const clang::dataflow::RecordStorageLocation::FieldToLoc &FieldLocs) { - if (Fields.size() != F... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/88754 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
