diff options
Diffstat (limited to 'contrib/llvm-project/clang/include/clang/Analysis')
56 files changed, 4109 insertions, 304 deletions
diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/CalledOnceCheck.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/CalledOnceCheck.h index a0c767bf92d2..6a1528a2da24 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/CalledOnceCheck.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/CalledOnceCheck.h @@ -20,7 +20,6 @@ class AnalysisDeclContext; class BlockDecl; class CFG; class Decl; -class DeclContext; class Expr; class ParmVarDecl; class Stmt; @@ -29,7 +28,7 @@ class Stmt; /// \enum IfThen -- then branch of the if statement has no call. /// \enum IfElse -- else branch of the if statement has no call. /// \enum Switch -- one of the switch cases doesn't have a call. -/// \enum SwitchSkipped -- there is no call if none of the cases appies. +/// \enum SwitchSkipped -- there is no call if none of the cases applies. /// \enum LoopEntered -- no call when the loop is entered. /// \enum LoopSkipped -- no call when the loop is not entered. /// \enum FallbackReason -- fallback case when we were not able to figure out @@ -80,7 +79,7 @@ public: /// the path containing the call and not containing the call. This helps us /// to pinpoint a bad path for the user. /// \param Parameter -- parameter that should be called once. - /// \param Function -- function declaration where the problem occured. + /// \param Function -- function declaration where the problem occurred. /// \param Where -- the least common ancestor statement. /// \param Reason -- a reason describing the path without a call. /// \param IsCalledDirectly -- true, if parameter actually gets called on diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Consumed.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Consumed.h index dec1ae3b2b4b..3e2788cac3c9 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Consumed.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Consumed.h @@ -153,8 +153,11 @@ namespace consumed { public: ConsumedStateMap() = default; ConsumedStateMap(const ConsumedStateMap &Other) - : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap), - TmpMap() {} + : Reachable(Other.Reachable), From(Other.From), VarMap(Other.VarMap) {} + + // The copy assignment operator is defined as deleted pending further + // motivation. + ConsumedStateMap &operator=(const ConsumedStateMap &) = delete; /// Warn if any of the parameters being tracked are not in the state /// they were declared to be in upon return from a function. @@ -241,7 +244,7 @@ namespace consumed { ConsumedBlockInfo BlockInfo; std::unique_ptr<ConsumedStateMap> CurrStates; - ConsumedState ExpectedReturnState; + ConsumedState ExpectedReturnState = CS_None; void determineExpectedReturnState(AnalysisDeclContext &AC, const FunctionDecl *D); @@ -259,7 +262,7 @@ namespace consumed { /// Check a function's CFG for consumed violations. /// /// We traverse the blocks in the CFG, keeping track of the state of each - /// value who's type has uniquness annotations. If methods are invoked in + /// value who's type has uniqueness annotations. If methods are invoked in /// the wrong state a warning is issued. Each block in the CFG is traversed /// exactly once. void run(AnalysisDeclContext &AC); diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h index 25a5ba9d83fe..7dd54c5ce262 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h @@ -193,7 +193,7 @@ namespace IDFCalculatorDetail { /// Specialize ChildrenGetterTy to skip nullpointer successors. template <bool IsPostDom> struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> { - using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef; + using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef; using ChildrenTy = SmallVector<NodeRef, 8>; ChildrenTy get(const NodeRef &N) { @@ -202,7 +202,7 @@ struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> { auto Children = children<OrderedNodeTy>(N); ChildrenTy Ret{Children.begin(), Children.end()}; - Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end()); + llvm::erase(Ret, nullptr); return Ret; } }; diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h index 9397c5df78ab..1ceef944fbc3 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ExprMutationAnalyzer.h @@ -38,6 +38,8 @@ public: } const Stmt *findPointeeMutation(const Expr *Exp); const Stmt *findPointeeMutation(const Decl *Dec); + static bool isUnevaluated(const Stmt *Smt, const Stmt &Stm, + ASTContext &Context); private: using MutationFinder = const Stmt *(ExprMutationAnalyzer::*)(const Expr *); diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/IntervalPartition.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/IntervalPartition.h new file mode 100644 index 000000000000..28a7afad41a7 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/IntervalPartition.h @@ -0,0 +1,123 @@ +//===- IntervalPartition.h - CFG Partitioning into Intervals -----*- 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 functionality for partitioning a CFG into intervals and +// building a weak topological order (WTO) of the nodes, based on the +// partitioning. The concepts and implementations for the graph partitioning +// are based on the presentation in "Compilers" by Aho, Sethi and Ullman (the +// "dragon book"), pages 664-666. The concepts around WTOs is taken from the +// paper "Efficient chaotic iteration strategies with widenings," by +// F. Bourdoncle ([Bourdoncle1993]). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H + +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/DenseSet.h" +#include <deque> +#include <memory> +#include <vector> + +namespace clang { +/// A _weak topological ordering_ (WTO) of CFG nodes provides a total order over +/// the CFG (defined in `WTOCompare`, below), which can guide the order in which +/// to visit nodes in fixpoint computations over the CFG. +/// +/// Roughly, a WTO a) groups the blocks so that loop heads are grouped with +/// their bodies and any nodes they dominate after the loop and b) orders the +/// groups topologically. As a result, the blocks in a series of loops are +/// ordered such that all nodes in loop `i` are earlier in the order than nodes +/// in loop `j`. This ordering, when combined with widening, bounds the number +/// of times a node must be visited for a dataflow algorithm to reach a +/// fixpoint. For the precise definition of a WTO and its properties, see +/// [Bourdoncle1993]. +/// +/// Here, we provide a simplified WTO which drops its nesting structure, +/// maintaining only the ordering itself. The ordering is built from the limit +/// flow graph of `Cfg` (derived from iteratively partitioning it into +/// intervals) if and only if it is reducible (its limit flow graph has one +/// node). Returns `nullopt` when `Cfg` is not reducible. +/// +/// This WTO construction is described in Section 4.2 of [Bourdoncle1993]. +using WeakTopologicalOrdering = std::vector<const CFGBlock *>; +std::optional<WeakTopologicalOrdering> getIntervalWTO(const CFG &Cfg); + +struct WTOCompare { + WTOCompare(const WeakTopologicalOrdering &WTO); + + bool operator()(const CFGBlock *B1, const CFGBlock *B2) const { + auto ID1 = B1->getBlockID(); + auto ID2 = B2->getBlockID(); + + unsigned V1 = ID1 >= BlockOrder.size() ? 0 : BlockOrder[ID1]; + unsigned V2 = ID2 >= BlockOrder.size() ? 0 : BlockOrder[ID2]; + return V1 > V2; + } + + std::vector<unsigned> BlockOrder; +}; + +namespace internal { +// An interval is a strongly-connected component of the CFG along with a +// trailing acyclic structure. An interval can be constructed directly from CFG +// blocks or from a graph of other intervals. Each interval has one _header_ +// block, from which the interval is built. The _header_ of the interval is +// either the graph's entry block or has at least one predecessor outside of the +// interval. All other blocks in the interval have only predecessors also in the +// interval. +struct CFGIntervalNode { + CFGIntervalNode() = default; + CFGIntervalNode(unsigned ID) : ID(ID) {} + + CFGIntervalNode(unsigned ID, std::vector<const CFGBlock *> Nodes) + : ID(ID), Nodes(std::move(Nodes)) {} + + const llvm::SmallDenseSet<const CFGIntervalNode *> &preds() const { + return Predecessors; + } + const llvm::SmallDenseSet<const CFGIntervalNode *> &succs() const { + return Successors; + } + + // Unique identifier of this interval relative to other intervals in the same + // graph. + unsigned ID; + + std::vector<const CFGBlock *> Nodes; + + // Predessor intervals of this interval: those intervals for which there + // exists an edge from a node in that other interval to the head of this + // interval. + llvm::SmallDenseSet<const CFGIntervalNode *> Predecessors; + + // Successor intervals of this interval: those intervals for which there + // exists an edge from a node in this interval to the head of that other + // interval. + llvm::SmallDenseSet<const CFGIntervalNode *> Successors; +}; + +// Since graphs are built from pointers to nodes, we use a deque to ensure +// pointer stability. +using CFGIntervalGraph = std::deque<CFGIntervalNode>; + +std::vector<const CFGBlock *> buildInterval(const CFGBlock *Header); + +// Partitions `Cfg` into intervals and constructs the graph of the intervals +// based on the edges between nodes in these intervals. +CFGIntervalGraph partitionIntoIntervals(const CFG &Cfg); + +// (Further) partitions `Graph` into intervals and constructs the graph of the +// intervals based on the edges between nodes (themselves intervals) in these +// intervals. +CFGIntervalGraph partitionIntoIntervals(const CFGIntervalGraph &Graph); +} // namespace internal +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_INTERVALPARTITION_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h index 100029894560..4356834adf76 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h @@ -18,7 +18,6 @@ #include "clang/Basic/LLVM.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/None.h" #include "llvm/ADT/PostOrderIterator.h" #include <utility> #include <vector> @@ -48,17 +47,18 @@ public: /// Set the bit associated with a particular CFGBlock. /// This is the important method for the SetType template parameter. - std::pair<llvm::NoneType, bool> insert(const CFGBlock *Block) { + std::pair<std::nullopt_t, bool> insert(const CFGBlock *Block) { // Note that insert() is called by po_iterator, which doesn't check to // make sure that Block is non-null. Moreover, the CFGBlock iterator will // occasionally hand out null pointers for pruned edges, so we catch those // here. if (!Block) - return std::make_pair(None, false); // if an edge is trivially false. + return std::make_pair(std::nullopt, + false); // if an edge is trivially false. if (VisitedBlockIDs.test(Block->getBlockID())) - return std::make_pair(None, false); + return std::make_pair(std::nullopt, false); VisitedBlockIDs.set(Block->getBlockID()); - return std::make_pair(None, true); + return std::make_pair(std::nullopt, true); } /// Check if the bit for a CFGBlock has been already set. diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ReachableCode.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ReachableCode.h index 514b9458d331..f1b63f74b6c8 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ReachableCode.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ReachableCode.h @@ -48,11 +48,9 @@ class Callback { virtual void anchor(); public: virtual ~Callback() {} - virtual void HandleUnreachable(UnreachableKind UK, - SourceLocation L, - SourceRange ConditionVal, - SourceRange R1, - SourceRange R2) = 0; + virtual void HandleUnreachable(UnreachableKind UK, SourceLocation L, + SourceRange ConditionVal, SourceRange R1, + SourceRange R2, bool HasFallThroughAttr) = 0; }; /// ScanReachableFromBlock - Mark all blocks reachable from Start. diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafety.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafety.h index bfa9870a1e1f..0866b09bab29 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafety.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafety.h @@ -47,7 +47,13 @@ enum ProtectedOperationKind { POK_PassByRef, /// Passing a pt-guarded variable by reference. - POK_PtPassByRef + POK_PtPassByRef, + + /// Returning a guarded variable by reference. + POK_ReturnByRef, + + /// Returning a pt-guarded variable by reference. + POK_PtReturnByRef, }; /// This enum distinguishes between different kinds of lock actions. For @@ -98,9 +104,8 @@ public: virtual ~ThreadSafetyHandler(); /// Warn about lock expressions which fail to resolve to lockable objects. - /// \param Kind -- the capability's name parameter (role, mutex, etc). /// \param Loc -- the SourceLocation of the unresolved expression. - virtual void handleInvalidLockExp(StringRef Kind, SourceLocation Loc) {} + virtual void handleInvalidLockExp(SourceLocation Loc) {} /// Warn about unlock function calls that do not have a prior matching lock /// expression. @@ -169,14 +174,12 @@ public: SourceLocation Loc2) {} /// Warn when a protected operation occurs while no locks are held. - /// \param Kind -- the capability's name parameter (role, mutex, etc). /// \param D -- The decl for the protected variable or function /// \param POK -- The kind of protected operation (e.g. variable access) /// \param AK -- The kind of access (i.e. read or write) that occurred /// \param Loc -- The location of the protected operation. - virtual void handleNoMutexHeld(StringRef Kind, const NamedDecl *D, - ProtectedOperationKind POK, AccessKind AK, - SourceLocation Loc) {} + virtual void handleNoMutexHeld(const NamedDecl *D, ProtectedOperationKind POK, + AccessKind AK, SourceLocation Loc) {} /// Warn when a protected operation occurs while the specific mutex protecting /// the operation is not locked. diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h index 4a58fe870944..13e37ac2b56b 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h @@ -30,6 +30,8 @@ #include "clang/Analysis/CFG.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Casting.h" #include <sstream> @@ -155,7 +157,7 @@ public: return false; // Ignore anonymous functions. - if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) + if (!isa_and_nonnull<NamedDecl>(AC.getDecl())) return false; SortedGraph = AC.getAnalysis<PostOrderCFGView>(); @@ -269,28 +271,36 @@ private: // translateAttrExpr needs it, but that should be moved too. class CapabilityExpr { private: - /// The capability expression. - const til::SExpr* CapExpr; + /// The capability expression and whether it's negated. + llvm::PointerIntPair<const til::SExpr *, 1, bool> CapExpr; - /// True if this is a negative capability. - bool Negated; + /// The kind of capability as specified by @ref CapabilityAttr::getName. + StringRef CapKind; public: - CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} + CapabilityExpr() : CapExpr(nullptr, false) {} + CapabilityExpr(const til::SExpr *E, StringRef Kind, bool Neg) + : CapExpr(E, Neg), CapKind(Kind) {} - const til::SExpr* sexpr() const { return CapExpr; } - bool negative() const { return Negated; } + // Don't allow implicitly-constructed StringRefs since we'll capture them. + template <typename T> CapabilityExpr(const til::SExpr *, T, bool) = delete; + + const til::SExpr *sexpr() const { return CapExpr.getPointer(); } + StringRef getKind() const { return CapKind; } + bool negative() const { return CapExpr.getInt(); } CapabilityExpr operator!() const { - return CapabilityExpr(CapExpr, !Negated); + return CapabilityExpr(CapExpr.getPointer(), CapKind, !CapExpr.getInt()); } bool equals(const CapabilityExpr &other) const { - return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); + return (negative() == other.negative()) && + sx::equals(sexpr(), other.sexpr()); } bool matches(const CapabilityExpr &other) const { - return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); + return (negative() == other.negative()) && + sx::matches(sexpr(), other.sexpr()); } bool matchesUniv(const CapabilityExpr &CapE) const { @@ -298,27 +308,27 @@ public: } bool partiallyMatches(const CapabilityExpr &other) const { - return (Negated == other.Negated) && - sx::partiallyMatches(CapExpr, other.CapExpr); + return (negative() == other.negative()) && + sx::partiallyMatches(sexpr(), other.sexpr()); } const ValueDecl* valueDecl() const { - if (Negated || CapExpr == nullptr) + if (negative() || sexpr() == nullptr) return nullptr; - if (const auto *P = dyn_cast<til::Project>(CapExpr)) + if (const auto *P = dyn_cast<til::Project>(sexpr())) return P->clangDecl(); - if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) + if (const auto *P = dyn_cast<til::LiteralPtr>(sexpr())) return P->clangDecl(); return nullptr; } std::string toString() const { - if (Negated) - return "!" + sx::toString(CapExpr); - return sx::toString(CapExpr); + if (negative()) + return "!" + sx::toString(sexpr()); + return sx::toString(sexpr()); } - bool shouldIgnore() const { return CapExpr == nullptr; } + bool shouldIgnore() const { return sexpr() == nullptr; } bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } @@ -345,13 +355,13 @@ public: const NamedDecl *AttrDecl; // Implicit object argument -- e.g. 'this' - const Expr *SelfArg = nullptr; + llvm::PointerUnion<const Expr *, til::SExpr *> SelfArg = nullptr; // Number of funArgs unsigned NumArgs = 0; // Function arguments - const Expr *const *FunArgs = nullptr; + llvm::PointerUnion<const Expr *const *, til::SExpr *> FunArgs = nullptr; // is Self referred to with -> or .? bool SelfArrow = false; @@ -369,10 +379,18 @@ public: // Translate a clang expression in an attribute to a til::SExpr. // Constructs the context from D, DeclExp, and SelfDecl. CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, - const Expr *DeclExp, VarDecl *SelfD=nullptr); + const Expr *DeclExp, + til::SExpr *Self = nullptr); CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); + // Translate a variable reference. + til::LiteralPtr *createVariable(const VarDecl *VD); + + // Create placeholder for this: we don't know the VarDecl on construction yet. + std::pair<til::LiteralPtr *, StringRef> + createThisPlaceholder(const Expr *Exp); + // Translate a clang statement or expression to a TIL expression. // Also performs substitution of variables; Ctx provides the context. // Dispatches on the type of S. @@ -466,8 +484,6 @@ private: SMap.insert(std::make_pair(S, E)); } - til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); - til::SExpr *addStatement(til::SExpr *E, const Stmt *S, const ValueDecl *VD = nullptr); til::SExpr *lookupVarDecl(const ValueDecl *VD); @@ -517,4 +533,4 @@ void printSCFG(CFGWalker &Walker); } // namespace threadSafety } // namespace clang -#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h index 77a800c28754..65dd66ee093f 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTIL.h @@ -50,8 +50,6 @@ #include "clang/Analysis/Analyses/ThreadSafetyUtil.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Casting.h" #include "llvm/Support/raw_ostream.h" @@ -60,6 +58,7 @@ #include <cstddef> #include <cstdint> #include <iterator> +#include <optional> #include <string> #include <utility> @@ -75,7 +74,7 @@ namespace til { class BasicBlock; /// Enum for the different distinct classes of SExpr -enum TIL_Opcode { +enum TIL_Opcode : unsigned char { #define TIL_OPCODE_DEF(X) COP_##X, #include "ThreadSafetyOps.def" #undef TIL_OPCODE_DEF @@ -278,7 +277,7 @@ class SExpr { public: SExpr() = delete; - TIL_Opcode opcode() const { return static_cast<TIL_Opcode>(Opcode); } + TIL_Opcode opcode() const { return Opcode; } // Subclasses of SExpr must define the following: // @@ -320,8 +319,9 @@ public: protected: SExpr(TIL_Opcode Op) : Opcode(Op) {} SExpr(const SExpr &E) : Opcode(E.Opcode), Flags(E.Flags) {} + SExpr &operator=(const SExpr &) = delete; - const unsigned char Opcode; + const TIL_Opcode Opcode; unsigned char Reserved = 0; unsigned short Flags = 0; unsigned SExprID = 0; @@ -332,7 +332,7 @@ protected: namespace ThreadSafetyTIL { inline bool isTrivial(const SExpr *E) { - unsigned Op = E->opcode(); + TIL_Opcode Op = E->opcode(); return Op == COP_Variable || Op == COP_Literal || Op == COP_LiteralPtr; } @@ -489,6 +489,10 @@ public: Undefined(const Stmt *S = nullptr) : SExpr(COP_Undefined), Cstmt(S) {} Undefined(const Undefined &U) : SExpr(U), Cstmt(U.Cstmt) {} + // The copy assignment operator is defined as deleted pending further + // motivation. + Undefined &operator=(const Undefined &) = delete; + static bool classof(const SExpr *E) { return E->opcode() == COP_Undefined; } template <class V> @@ -567,6 +571,10 @@ public: LiteralT(T Dat) : Literal(ValueType::getValueType<T>()), Val(Dat) {} LiteralT(const LiteralT<T> &L) : Literal(L), Val(L.Val) {} + // The copy assignment operator is defined as deleted pending further + // motivation. + LiteralT &operator=(const LiteralT<T> &) = delete; + T value() const { return Val;} T& value() { return Val; } @@ -634,15 +642,14 @@ typename V::R_SExpr Literal::traverse(V &Vs, typename V::R_Ctx Ctx) { /// At compile time, pointer literals are represented by symbolic names. class LiteralPtr : public SExpr { public: - LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) { - assert(D && "ValueDecl must not be null"); - } + LiteralPtr(const ValueDecl *D) : SExpr(COP_LiteralPtr), Cvdecl(D) {} LiteralPtr(const LiteralPtr &) = default; static bool classof(const SExpr *E) { return E->opcode() == COP_LiteralPtr; } // The clang declaration for the value that this pointer points to. const ValueDecl *clangDecl() const { return Cvdecl; } + void setClangDecl(const ValueDecl *VD) { Cvdecl = VD; } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -651,6 +658,8 @@ public: template <class C> typename C::CType compare(const LiteralPtr* E, C& Cmp) const { + if (!Cvdecl || !E->Cvdecl) + return Cmp.comparePointers(this, E); return Cmp.comparePointers(Cvdecl, E->Cvdecl); } @@ -957,7 +966,7 @@ public: private: SExpr* Rec; - mutable llvm::Optional<std::string> SlotName; + mutable std::optional<std::string> SlotName; const ValueDecl *Cvdecl; }; @@ -1430,9 +1439,7 @@ public: BasicBlock *elseBlock() { return Branches[1]; } /// Return the list of basic blocks that this terminator can branch to. - ArrayRef<BasicBlock*> successors() { - return llvm::makeArrayRef(Branches); - } + ArrayRef<BasicBlock *> successors() { return llvm::ArrayRef(Branches); } template <class V> typename V::R_SExpr traverse(V &Vs, typename V::R_Ctx Ctx) { @@ -1463,7 +1470,7 @@ public: static bool classof(const SExpr *E) { return E->opcode() == COP_Return; } /// Return an empty list. - ArrayRef<BasicBlock *> successors() { return None; } + ArrayRef<BasicBlock *> successors() { return std::nullopt; } SExpr *returnValue() { return Retval; } const SExpr *returnValue() const { return Retval; } @@ -1489,7 +1496,7 @@ inline ArrayRef<BasicBlock*> Terminator::successors() { case COP_Branch: return cast<Branch>(this)->successors(); case COP_Return: return cast<Return>(this)->successors(); default: - return None; + return std::nullopt; } } diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h index e81c00d3dddb..6fc55130655a 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyTraverse.h @@ -623,7 +623,10 @@ protected: } void printLiteralPtr(const LiteralPtr *E, StreamType &SS) { - SS << E->clangDecl()->getNameAsString(); + if (const NamedDecl *D = E->clangDecl()) + SS << D->getNameAsString(); + else + SS << "<temporary>"; } void printVariable(const Variable *V, StreamType &SS, bool IsVarDecl=false) { diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h index e3b6e61d3026..ac7b24cdb4a6 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h @@ -204,11 +204,11 @@ public: } llvm::iterator_range<reverse_iterator> reverse() { - return llvm::make_range(rbegin(), rend()); + return llvm::reverse(*this); } llvm::iterator_range<const_reverse_iterator> reverse() const { - return llvm::make_range(rbegin(), rend()); + return llvm::reverse(*this); } private: @@ -240,6 +240,10 @@ class CopyOnWriteVector { VectorData() = default; VectorData(const VectorData &VD) : Vect(VD.Vect) {} + + // The copy assignment operator is defined as deleted pending further + // motivation. + VectorData &operator=(const VectorData &) = delete; }; public: @@ -354,4 +358,4 @@ inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { } // namespace threadSafety } // namespace clang -#endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H +#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsage.h b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsage.h new file mode 100644 index 000000000000..b28f2c6b99c5 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsage.h @@ -0,0 +1,122 @@ +//===- UnsafeBufferUsage.h - Replace pointers with modern C++ ---*- 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 analysis that aids replacing buffer accesses through +// raw pointers with safer C++ abstractions such as containers and views/spans. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H +#define LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "llvm/Support/Debug.h" + +namespace clang { + +using VarGrpTy = std::vector<const VarDecl *>; +using VarGrpRef = ArrayRef<const VarDecl *>; + +class VariableGroupsManager { +public: + VariableGroupsManager() = default; + virtual ~VariableGroupsManager() = default; + /// Returns the set of variables (including `Var`) that need to be fixed + /// together in one step. + /// + /// `Var` must be a variable that needs fix (so it must be in a group). + /// `HasParm` is an optional argument that will be set to true if the set of + /// variables, where `Var` is in, contains parameters. + virtual VarGrpRef getGroupOfVar(const VarDecl *Var, + bool *HasParm = nullptr) const =0; + + /// Returns the non-empty group of variables that include parameters of the + /// analyzing function, if such a group exists. An empty group, otherwise. + virtual VarGrpRef getGroupOfParms() const =0; +}; + +/// The interface that lets the caller handle unsafe buffer usage analysis +/// results by overriding this class's handle... methods. +class UnsafeBufferUsageHandler { +#ifndef NDEBUG +public: + // A self-debugging facility that you can use to notify the user when + // suggestions or fixits are incomplete. + // Uses std::function to avoid computing the message when it won't + // actually be displayed. + using DebugNote = std::pair<SourceLocation, std::string>; + using DebugNoteList = std::vector<DebugNote>; + using DebugNoteByVar = std::map<const VarDecl *, DebugNoteList>; + DebugNoteByVar DebugNotesByVar; +#endif + +public: + UnsafeBufferUsageHandler() = default; + virtual ~UnsafeBufferUsageHandler() = default; + + /// This analyses produces large fixits that are organized into lists + /// of primitive fixits (individual insertions/removals/replacements). + using FixItList = llvm::SmallVectorImpl<FixItHint>; + + /// Invoked when an unsafe operation over raw pointers is found. + virtual void handleUnsafeOperation(const Stmt *Operation, + bool IsRelatedToDecl, ASTContext &Ctx) = 0; + + /// Invoked when a fix is suggested against a variable. This function groups + /// all variables that must be fixed together (i.e their types must be changed + /// to the same target type to prevent type mismatches) into a single fixit. + /// + /// `D` is the declaration of the callable under analysis that owns `Variable` + /// and all of its group mates. + virtual void handleUnsafeVariableGroup(const VarDecl *Variable, + const VariableGroupsManager &VarGrpMgr, + FixItList &&Fixes, const Decl *D) = 0; + +#ifndef NDEBUG +public: + bool areDebugNotesRequested() { + DEBUG_WITH_TYPE("SafeBuffers", return true); + return false; + } + + void addDebugNoteForVar(const VarDecl *VD, SourceLocation Loc, + std::string Text) { + if (areDebugNotesRequested()) + DebugNotesByVar[VD].push_back(std::make_pair(Loc, Text)); + } + + void clearDebugNotes() { + if (areDebugNotesRequested()) + DebugNotesByVar.clear(); + } +#endif + +public: + /// Returns a reference to the `Preprocessor`: + virtual bool isSafeBufferOptOut(const SourceLocation &Loc) const = 0; + + virtual std::string + getUnsafeBufferUsageAttributeTextAt(SourceLocation Loc, + StringRef WSSuffix = "") const = 0; +}; + +// This function invokes the analysis and allows the caller to react to it +// through the handler class. +void checkUnsafeBufferUsage(const Decl *D, UnsafeBufferUsageHandler &Handler, + bool EmitSuggestions); + +namespace internal { +// Tests if any two `FixItHint`s in `FixIts` conflict. Two `FixItHint`s +// conflict if they have overlapping source ranges. +bool anyConflict(const llvm::SmallVectorImpl<FixItHint> &FixIts, + const SourceManager &SM); +} // namespace internal +} // end namespace clang + +#endif /* LLVM_CLANG_ANALYSIS_ANALYSES_UNSAFEBUFFERUSAGE_H */ diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def new file mode 100644 index 000000000000..c97661688365 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/Analyses/UnsafeBufferUsageGadgets.def @@ -0,0 +1,46 @@ +//=- UnsafeBufferUsageGadgets.def - List of ways to use a buffer --*- 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 +// +//===----------------------------------------------------------------------===// + +/// A gadget is an individual operation in the code that may be of interest to +/// the UnsafeBufferUsage analysis. +#ifndef GADGET +#define GADGET(name) +#endif + +/// Unsafe gadgets correspond to unsafe code patterns that warrant +/// an immediate warning. +#ifndef WARNING_GADGET +#define WARNING_GADGET(name) GADGET(name) +#endif + +/// Safe gadgets correspond to code patterns that aren't unsafe but need to be +/// properly recognized in order to emit correct warnings and fixes over unsafe +/// gadgets. +#ifndef FIXABLE_GADGET +#define FIXABLE_GADGET(name) GADGET(name) +#endif + +WARNING_GADGET(Increment) +WARNING_GADGET(Decrement) +WARNING_GADGET(ArraySubscript) +WARNING_GADGET(PointerArithmetic) +WARNING_GADGET(UnsafeBufferUsageAttr) +WARNING_GADGET(DataInvocation) +FIXABLE_GADGET(ULCArraySubscript) // `DRE[any]` in an Unspecified Lvalue Context +FIXABLE_GADGET(DerefSimplePtrArithFixable) +FIXABLE_GADGET(PointerDereference) +FIXABLE_GADGET(UPCAddressofArraySubscript) // '&DRE[any]' in an Unspecified Pointer Context +FIXABLE_GADGET(UPCStandalonePointer) +FIXABLE_GADGET(UPCPreIncrement) // '++Ptr' in an Unspecified Pointer Context +FIXABLE_GADGET(UUCAddAssign) // 'Ptr += n' in an Unspecified Untyped Context +FIXABLE_GADGET(PointerAssignment) +FIXABLE_GADGET(PointerInit) + +#undef FIXABLE_GADGET +#undef WARNING_GADGET +#undef GADGET diff --git a/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDeclContext.h b/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDeclContext.h index 102970a1d55e..a517a4e757c9 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDeclContext.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDeclContext.h @@ -229,7 +229,9 @@ private: protected: LocationContext(ContextKind k, AnalysisDeclContext *ctx, const LocationContext *parent, int64_t ID) - : Kind(k), Ctx(ctx), Parent(parent), ID(ID) {} + : Kind(k), Ctx(ctx), Parent(parent), ID(ID) { + assert(ctx); + } public: virtual ~LocationContext(); @@ -238,8 +240,10 @@ public: int64_t getID() const { return ID; } + LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext *getAnalysisDeclContext() const { return Ctx; } + /// It might return null. const LocationContext *getParent() const { return Parent; } bool isParentOf(const LocationContext *LC) const; @@ -327,7 +331,7 @@ public: unsigned getIndex() const { return Index; } CFGElement getCallSiteCFGElement() const { return (*Block)[Index]; } - + void Profile(llvm::FoldingSetNodeID &ID) override; static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ADC, diff --git a/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDiagnostic.h b/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDiagnostic.h deleted file mode 100644 index fd5f2ffe6483..000000000000 --- a/contrib/llvm-project/clang/include/clang/Analysis/AnalysisDiagnostic.h +++ /dev/null @@ -1,14 +0,0 @@ -//===--- DiagnosticAnalysis.h - Diagnostics for libanalysis -----*- 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 -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H -#define LLVM_CLANG_ANALYSIS_ANALYSISDIAGNOSTIC_H - -#include "clang/Basic/DiagnosticAnalysis.h" - -#endif diff --git a/contrib/llvm-project/clang/include/clang/Analysis/AnyCall.h b/contrib/llvm-project/clang/include/clang/Analysis/AnyCall.h index 846ff7719ce1..48abce062d13 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/AnyCall.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/AnyCall.h @@ -10,12 +10,13 @@ // //===----------------------------------------------------------------------===// // -#ifndef LLVM_CLANG_ANALYSIS_ANY_CALL_H -#define LLVM_CLANG_ANALYSIS_ANY_CALL_H +#ifndef LLVM_CLANG_ANALYSIS_ANYCALL_H +#define LLVM_CLANG_ANALYSIS_ANYCALL_H #include "clang/AST/Decl.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" +#include <optional> namespace clang { @@ -108,8 +109,8 @@ public: } /// If @c E is a generic call (to ObjC method /function/block/etc), - /// return a constructed @c AnyCall object. Return None otherwise. - static Optional<AnyCall> forExpr(const Expr *E) { + /// return a constructed @c AnyCall object. Return std::nullopt otherwise. + static std::optional<AnyCall> forExpr(const Expr *E) { if (const auto *ME = dyn_cast<ObjCMessageExpr>(E)) { return AnyCall(ME); } else if (const auto *CE = dyn_cast<CallExpr>(E)) { @@ -123,26 +124,26 @@ public: } else if (const auto *CXCIE = dyn_cast<CXXInheritedCtorInitExpr>(E)) { return AnyCall(CXCIE); } else { - return None; + return std::nullopt; } } /// If @c D is a callable (Objective-C method or a function), return - /// a constructed @c AnyCall object. Return None otherwise. + /// a constructed @c AnyCall object. Return std::nullopt otherwise. // FIXME: block support. - static Optional<AnyCall> forDecl(const Decl *D) { + static std::optional<AnyCall> forDecl(const Decl *D) { if (const auto *FD = dyn_cast<FunctionDecl>(D)) { return AnyCall(FD); } else if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) { return AnyCall(MD); } - return None; + return std::nullopt; } /// \returns formal parameters for direct calls (including virtual calls) ArrayRef<ParmVarDecl *> parameters() const { if (!D) - return None; + return std::nullopt; if (const auto *FD = dyn_cast<FunctionDecl>(D)) { return FD->parameters(); @@ -151,7 +152,7 @@ public: } else if (const auto *BD = dyn_cast<BlockDecl>(D)) { return BD->parameters(); } else { - return None; + return std::nullopt; } } @@ -215,4 +216,4 @@ public: } -#endif // LLVM_CLANG_ANALYSIS_ANY_CALL_H +#endif // LLVM_CLANG_ANALYSIS_ANYCALL_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/BodyFarm.h b/contrib/llvm-project/clang/include/clang/Analysis/BodyFarm.h index 72607f8839f5..52be29cb7885 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/BodyFarm.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/BodyFarm.h @@ -11,20 +11,19 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_LIB_ANALYSIS_BODYFARM_H -#define LLVM_CLANG_LIB_ANALYSIS_BODYFARM_H +#ifndef LLVM_CLANG_ANALYSIS_BODYFARM_H +#define LLVM_CLANG_ANALYSIS_BODYFARM_H #include "clang/AST/DeclBase.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" +#include <optional> namespace clang { class ASTContext; class FunctionDecl; class ObjCMethodDecl; -class ObjCPropertyDecl; class Stmt; class CodeInjector; @@ -41,8 +40,11 @@ public: /// Remove copy constructor to avoid accidental copying. BodyFarm(const BodyFarm &other) = delete; + /// Delete copy assignment operator. + BodyFarm &operator=(const BodyFarm &other) = delete; + private: - typedef llvm::DenseMap<const Decl *, Optional<Stmt *>> BodyMap; + typedef llvm::DenseMap<const Decl *, std::optional<Stmt *>> BodyMap; ASTContext &C; BodyMap Bodies; diff --git a/contrib/llvm-project/clang/include/clang/Analysis/CFG.h b/contrib/llvm-project/clang/include/clang/Analysis/CFG.h index 9e32eb8e066a..9f776ca6cc26 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/CFG.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/CFG.h @@ -14,15 +14,14 @@ #ifndef LLVM_CLANG_ANALYSIS_CFG_H #define LLVM_CLANG_ANALYSIS_CFG_H -#include "clang/Analysis/Support/BumpVector.h" -#include "clang/Analysis/ConstructionContext.h" +#include "clang/AST/Attr.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/ExprObjC.h" +#include "clang/Analysis/ConstructionContext.h" +#include "clang/Analysis/Support/BumpVector.h" #include "clang/Basic/LLVM.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/None.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" @@ -32,6 +31,7 @@ #include <cstddef> #include <iterator> #include <memory> +#include <optional> #include <vector> namespace clang { @@ -75,7 +75,8 @@ public: MemberDtor, TemporaryDtor, DTOR_BEGIN = AutomaticObjectDtor, - DTOR_END = TemporaryDtor + DTOR_END = TemporaryDtor, + CleanupFunction, }; protected: @@ -103,12 +104,11 @@ public: return t; } - /// Convert to the specified CFGElement type, returning None if this + /// Convert to the specified CFGElement type, returning std::nullopt if this /// CFGElement is not of the desired type. - template<typename T> - Optional<T> getAs() const { + template <typename T> std::optional<T> getAs() const { if (!T::isKind(*this)) - return None; + return std::nullopt; T t; CFGElement& e = t; e = *this; @@ -131,7 +131,7 @@ public: class CFGStmt : public CFGElement { public: - explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) { + explicit CFGStmt(const Stmt *S, Kind K = Statement) : CFGElement(K, S) { assert(isKind(*this)); } @@ -155,7 +155,8 @@ protected: /// this is only used by the analyzer's CFG. class CFGConstructor : public CFGStmt { public: - explicit CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C) + explicit CFGConstructor(const CXXConstructExpr *CE, + const ConstructionContext *C) : CFGStmt(CE, Constructor) { assert(C); Data2.setPointer(const_cast<ConstructionContext *>(C)); @@ -185,7 +186,7 @@ class CFGCXXRecordTypedCall : public CFGStmt { public: /// Returns true when call expression \p CE needs to be represented /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt. - static bool isCXXRecordTypedCall(Expr *E) { + static bool isCXXRecordTypedCall(const Expr *E) { assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E)); // There is no such thing as reference-type expression. If the function // returns a reference, it'll return the respective lvalue or xvalue @@ -194,7 +195,7 @@ public: E->getType().getCanonicalType()->getAsCXXRecordDecl(); } - explicit CFGCXXRecordTypedCall(Expr *E, const ConstructionContext *C) + explicit CFGCXXRecordTypedCall(const Expr *E, const ConstructionContext *C) : CFGStmt(E, CXXRecordTypedCall) { assert(isCXXRecordTypedCall(E)); assert(C && (isa<TemporaryObjectConstructionContext>(C) || @@ -202,7 +203,8 @@ public: isa<ReturnedValueConstructionContext>(C) || isa<VariableConstructionContext>(C) || isa<ConstructorInitializerConstructionContext>(C) || - isa<ArgumentConstructionContext>(C))); + isa<ArgumentConstructionContext>(C) || + isa<LambdaCaptureConstructionContext>(C))); Data2.setPointer(const_cast<ConstructionContext *>(C)); } @@ -224,7 +226,7 @@ private: /// list. class CFGInitializer : public CFGElement { public: - explicit CFGInitializer(CXXCtorInitializer *initializer) + explicit CFGInitializer(const CXXCtorInitializer *initializer) : CFGElement(Initializer, initializer) {} CXXCtorInitializer* getInitializer() const { @@ -263,7 +265,7 @@ private: }; /// Represents the point where a loop ends. -/// This element is is only produced when building the CFG for the static +/// This element is only produced when building the CFG for the static /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. /// /// Note: a loop exit element can be reached even when the loop body was never @@ -383,6 +385,32 @@ private: } }; +class CFGCleanupFunction final : public CFGElement { +public: + CFGCleanupFunction() = default; + CFGCleanupFunction(const VarDecl *VD) + : CFGElement(Kind::CleanupFunction, VD) { + assert(VD->hasAttr<CleanupAttr>()); + } + + const VarDecl *getVarDecl() const { + return static_cast<VarDecl *>(Data1.getPointer()); + } + + /// Returns the function to be called when cleaning up the var decl. + const FunctionDecl *getFunctionDecl() const { + const CleanupAttr *A = getVarDecl()->getAttr<CleanupAttr>(); + return A->getFunctionDecl(); + } + +private: + friend class CFGElement; + + static bool isKind(const CFGElement E) { + return E.getKind() == Kind::CleanupFunction; + } +}; + /// Represents C++ object destructor implicitly generated for automatic object /// or temporary bound to const reference at the point of leaving its local /// scope. @@ -481,7 +509,7 @@ private: /// expression for temporary object. class CFGTemporaryDtor : public CFGImplicitDtor { public: - CFGTemporaryDtor(CXXBindTemporaryExpr *expr) + CFGTemporaryDtor(const CXXBindTemporaryExpr *expr) : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} const CXXBindTemporaryExpr *getBindTemporaryExpr() const { @@ -515,7 +543,7 @@ public: /// of the most derived class while we're in the base class. VirtualBaseBranch, - /// Number of different kinds, for sanity checks. We subtract 1 so that + /// Number of different kinds, for assertions. We subtract 1 so that /// to keep receiving compiler warnings when we don't cover all enum values /// in a switch. NumKindsMinusOne = VirtualBaseBranch @@ -707,7 +735,7 @@ class CFGBlock { template <bool IsOtherConst> ElementRefIterator(ElementRefIterator<true, IsOtherConst> E) - : ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {} + : ElementRefIterator(E.Parent, std::make_reverse_iterator(E.Pos)) {} bool operator<(ElementRefIterator Other) const { assert(Parent == Other.Parent); @@ -1122,19 +1150,10 @@ public: Elements.push_back(CFGScopeBegin(VD, S), C); } - void prependScopeBegin(const VarDecl *VD, const Stmt *S, - BumpVectorContext &C) { - Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C); - } - void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { Elements.push_back(CFGScopeEnd(VD, S), C); } - void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { - Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C); - } - void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { Elements.push_back(CFGBaseDtor(BS), C); } @@ -1151,6 +1170,10 @@ public: Elements.push_back(CFGAutomaticObjDtor(VD, S), C); } + void appendCleanupFunction(const VarDecl *VD, BumpVectorContext &C) { + Elements.push_back(CFGCleanupFunction(VD), C); + } + void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) { Elements.push_back(CFGLifetimeEnds(VD, S), C); } @@ -1162,44 +1185,6 @@ public: void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { Elements.push_back(CFGDeleteDtor(RD, DE), C); } - - // Destructors must be inserted in reversed order. So insertion is in two - // steps. First we prepare space for some number of elements, then we insert - // the elements beginning at the last position in prepared space. - iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, - BumpVectorContext &C) { - return iterator(Elements.insert(I.base(), Cnt, - CFGAutomaticObjDtor(nullptr, nullptr), C)); - } - iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { - *I = CFGAutomaticObjDtor(VD, S); - return ++I; - } - - // Scope leaving must be performed in reversed order. So insertion is in two - // steps. First we prepare space for some number of elements, then we insert - // the elements beginning at the last position in prepared space. - iterator beginLifetimeEndsInsert(iterator I, size_t Cnt, - BumpVectorContext &C) { - return iterator( - Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C)); - } - iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) { - *I = CFGLifetimeEnds(VD, S); - return ++I; - } - - // Scope leaving must be performed in reversed order. So insertion is in two - // steps. First we prepare space for some number of elements, then we insert - // the elements beginning at the last position in prepared space. - iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) { - return iterator( - Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C)); - } - iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) { - *I = CFGScopeEnd(VD, S); - return ++I; - } }; /// CFGCallback defines methods that should be called when a logical @@ -1209,6 +1194,7 @@ public: CFGCallback() = default; virtual ~CFGCallback() = default; + virtual void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} virtual void compareBitwiseEquality(const BinaryOperator *B, bool isAlwaysTrue) {} @@ -1229,7 +1215,9 @@ public: //===--------------------------------------------------------------------===// class BuildOptions { - std::bitset<Stmt::lastStmtConstant> alwaysAddMask; + // Stmt::lastStmtConstant has the same value as the last Stmt kind, + // so make sure we add one to account for this! + std::bitset<Stmt::lastStmtConstant + 1> alwaysAddMask; public: using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>; @@ -1337,6 +1325,7 @@ public: const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } using try_block_iterator = std::vector<const CFGBlock *>::const_iterator; + using try_block_range = llvm::iterator_range<try_block_iterator>; try_block_iterator try_blocks_begin() const { return TryDispatchBlocks.begin(); @@ -1346,6 +1335,10 @@ public: return TryDispatchBlocks.end(); } + try_block_range try_blocks() const { + return try_block_range(try_blocks_begin(), try_blocks_end()); + } + void addTryDispatchBlock(const CFGBlock *block) { TryDispatchBlocks.push_back(block); } @@ -1393,7 +1386,7 @@ public: for (const_iterator I = begin(), E = end(); I != E; ++I) for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); BI != BE; ++BI) { - if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) + if (std::optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) O(const_cast<Stmt *>(stmt->getStmt())); } } @@ -1460,6 +1453,8 @@ private: llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; }; +Expr *extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE); + } // namespace clang //===----------------------------------------------------------------------===// @@ -1489,9 +1484,6 @@ template <> struct GraphTraits< ::clang::CFGBlock *> { static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } }; -template <> struct GraphTraits<clang::CFGBlock> - : GraphTraits<clang::CFGBlock *> {}; - template <> struct GraphTraits< const ::clang::CFGBlock *> { using NodeRef = const ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; @@ -1501,9 +1493,6 @@ template <> struct GraphTraits< const ::clang::CFGBlock *> { static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } }; -template <> struct GraphTraits<const clang::CFGBlock> - : GraphTraits<clang::CFGBlock *> {}; - template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { using NodeRef = ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; @@ -1516,9 +1505,6 @@ template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } }; -template <> struct GraphTraits<Inverse<clang::CFGBlock>> - : GraphTraits<clang::CFGBlock *> {}; - template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { using NodeRef = const ::clang::CFGBlock *; using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; @@ -1531,9 +1517,6 @@ template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } }; -template <> struct GraphTraits<const Inverse<clang::CFGBlock>> - : GraphTraits<clang::CFGBlock *> {}; - // Traits for: CFG template <> struct GraphTraits< ::clang::CFG* > diff --git a/contrib/llvm-project/clang/include/clang/Analysis/CFGStmtMap.h b/contrib/llvm-project/clang/include/clang/Analysis/CFGStmtMap.h index 8cf02372ff0f..93cd9cfc5bdf 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/CFGStmtMap.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/CFGStmtMap.h @@ -26,6 +26,8 @@ class CFGStmtMap { void *M; CFGStmtMap(ParentMap *pm, void *m) : PM(pm), M(m) {} + CFGStmtMap(const CFGStmtMap &) = delete; + CFGStmtMap &operator=(const CFGStmtMap &) = delete; public: ~CFGStmtMap(); diff --git a/contrib/llvm-project/clang/include/clang/Analysis/CallGraph.h b/contrib/llvm-project/clang/include/clang/Analysis/CallGraph.h index 999ac5da8acb..78f8d1155501 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/CallGraph.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/CallGraph.h @@ -66,7 +66,7 @@ public: /// Determine if a declaration should be included in the graph. static bool includeInGraph(const Decl *D); - /// Determine if a declaration should be included in the graph for the + /// Determine if a declaration should be included in the graph for the /// purposes of being a callee. This is similar to includeInGraph except /// it permits declarations, not just definitions. static bool includeCalleeInGraph(const Decl *D); diff --git a/contrib/llvm-project/clang/include/clang/Analysis/CloneDetection.h b/contrib/llvm-project/clang/include/clang/Analysis/CloneDetection.h index db827c3a6d6f..3385579584b5 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/CloneDetection.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/CloneDetection.h @@ -11,8 +11,8 @@ /// //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_AST_CLONEDETECTION_H -#define LLVM_CLANG_AST_CLONEDETECTION_H +#ifndef LLVM_CLANG_ANALYSIS_CLONEDETECTION_H +#define LLVM_CLANG_ANALYSIS_CLONEDETECTION_H #include "clang/AST/StmtVisitor.h" #include "llvm/Support/Regex.h" @@ -208,13 +208,7 @@ public: // The initial assumption is that there is only one clone group and every // statement is a clone of the others. This clone group will then be // split up with the help of the constraints. - CloneGroup AllClones; - AllClones.reserve(Sequences.size()); - for (const auto &C : Sequences) { - AllClones.push_back(C); - } - - Result.push_back(AllClones); + Result.push_back(Sequences); constrainClones(Result, ConstraintList...); } @@ -235,9 +229,7 @@ public: static void filterGroups( std::vector<CloneDetector::CloneGroup> &CloneGroups, llvm::function_ref<bool(const CloneDetector::CloneGroup &)> Filter) { - CloneGroups.erase( - std::remove_if(CloneGroups.begin(), CloneGroups.end(), Filter), - CloneGroups.end()); + llvm::erase_if(CloneGroups, Filter); } /// Splits the given CloneGroups until the given Compare function returns true @@ -268,7 +260,7 @@ public: /// /// Clones that aren't type II clones are moved into separate clone groups. /// In contrast to the RecursiveCloneTypeIIHashConstraint, all clones in a clone -/// group are guaranteed to be be type II clones of each other, but it is too +/// group are guaranteed to be type II clones of each other, but it is too /// slow to efficiently handle large amounts of clones. class RecursiveCloneTypeIIVerifyConstraint { public: @@ -443,4 +435,4 @@ struct MatchingVariablePatternConstraint { } // end namespace clang -#endif // LLVM_CLANG_AST_CLONEDETECTION_H +#endif // LLVM_CLANG_ANALYSIS_CLONEDETECTION_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/ConstructionContext.h b/contrib/llvm-project/clang/include/clang/Analysis/ConstructionContext.h index 4fa5c8b454a0..e19a20500095 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/ConstructionContext.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/ConstructionContext.h @@ -36,13 +36,14 @@ public: ElidedDestructorKind, ElidableConstructorKind, ArgumentKind, - STATEMENT_WITH_INDEX_KIND_BEGIN=ArgumentKind, - STATEMENT_WITH_INDEX_KIND_END=ArgumentKind, + LambdaCaptureKind, + STATEMENT_WITH_INDEX_KIND_BEGIN = ArgumentKind, + STATEMENT_WITH_INDEX_KIND_END = LambdaCaptureKind, STATEMENT_KIND_BEGIN = VariableKind, - STATEMENT_KIND_END = ArgumentKind, + STATEMENT_KIND_END = LambdaCaptureKind, InitializerKind, - INITIALIZER_KIND_BEGIN=InitializerKind, - INITIALIZER_KIND_END=InitializerKind + INITIALIZER_KIND_BEGIN = InitializerKind, + INITIALIZER_KIND_END = InitializerKind }; LLVM_DUMP_METHOD static StringRef getKindAsString(ItemKind K) { @@ -55,6 +56,8 @@ public: case ElidedDestructorKind: return "elide destructor"; case ElidableConstructorKind: return "elide constructor"; case ArgumentKind: return "construct into argument"; + case LambdaCaptureKind: + return "construct into lambda captured variable"; case InitializerKind: return "construct into member variable"; }; llvm_unreachable("Unknown ItemKind"); @@ -72,7 +75,7 @@ private: bool hasIndex() const { return Kind >= STATEMENT_WITH_INDEX_KIND_BEGIN && - Kind >= STATEMENT_WITH_INDEX_KIND_END; + Kind <= STATEMENT_WITH_INDEX_KIND_END; } bool hasInitializer() const { @@ -120,12 +123,16 @@ public: ConstructionContextItem(const Expr *E, unsigned Index) : Data(E), Kind(ArgumentKind), Index(Index) { assert(isa<CallExpr>(E) || isa<CXXConstructExpr>(E) || - isa<CXXInheritedCtorInitExpr>(E) || isa<ObjCMessageExpr>(E)); + isa<CXXDeleteExpr>(E) || isa<CXXInheritedCtorInitExpr>(E) || + isa<ObjCMessageExpr>(E)); } ConstructionContextItem(const CXXCtorInitializer *Init) : Data(Init), Kind(InitializerKind), Index(0) {} + ConstructionContextItem(const LambdaExpr *LE, unsigned Index) + : Data(LE), Kind(LambdaCaptureKind), Index(Index) {} + ItemKind getKind() const { return Kind; } LLVM_DUMP_METHOD StringRef getKindAsString() const { @@ -253,7 +260,8 @@ public: CXX17ElidedCopyReturnedValueKind, RETURNED_VALUE_BEGIN = SimpleReturnedValueKind, RETURNED_VALUE_END = CXX17ElidedCopyReturnedValueKind, - ArgumentKind + ArgumentKind, + LambdaCaptureKind }; protected: @@ -297,6 +305,11 @@ public: const ConstructionContextLayer *TopLayer); Kind getKind() const { return K; } + + virtual const ArrayInitLoopExpr *getArrayInitLoop() const { return nullptr; } + + // Only declared to silence -Wnon-virtual-dtor warnings. + virtual ~ConstructionContext() = default; }; /// An abstract base class for local variable constructors. @@ -313,6 +326,12 @@ protected: public: const DeclStmt *getDeclStmt() const { return DS; } + const ArrayInitLoopExpr *getArrayInitLoop() const override { + const auto *Var = cast<VarDecl>(DS->getSingleDecl()); + + return dyn_cast<ArrayInitLoopExpr>(Var->getInit()); + } + static bool classof(const ConstructionContext *CC) { return CC->getKind() >= VARIABLE_BEGIN && CC->getKind() <= VARIABLE_END; @@ -380,6 +399,10 @@ protected: public: const CXXCtorInitializer *getCXXCtorInitializer() const { return I; } + const ArrayInitLoopExpr *getArrayInitLoop() const override { + return dyn_cast<ArrayInitLoopExpr>(I->getInit()); + } + static bool classof(const ConstructionContext *CC) { return CC->getKind() >= INITIALIZER_BEGIN && CC->getKind() <= INITIALIZER_END; @@ -519,7 +542,7 @@ public: /// of being immediately copied by an elidable copy/move constructor. /// For example, T t = T(123); includes a temporary T(123) that is immediately /// copied to variable t. In such cases the elidable copy can (but not -/// necessarily should) be omitted ("elided") accodring to the rules of the +/// necessarily should) be omitted ("elided") according to the rules of the /// language; the constructor would then construct variable t directly. /// This construction context contains information of the elidable constructor /// and its respective construction context. @@ -658,6 +681,42 @@ public: } }; +class LambdaCaptureConstructionContext : public ConstructionContext { + // The lambda of which the initializer we capture. + const LambdaExpr *LE; + + // Index of the captured element in the captured list. + unsigned Index; + + friend class ConstructionContext; // Allows to create<>() itself. + + explicit LambdaCaptureConstructionContext(const LambdaExpr *LE, + unsigned Index) + : ConstructionContext(LambdaCaptureKind), LE(LE), Index(Index) {} + +public: + const LambdaExpr *getLambdaExpr() const { return LE; } + unsigned getIndex() const { return Index; } + + const Expr *getInitializer() const { + return *(LE->capture_init_begin() + Index); + } + + const FieldDecl *getFieldDecl() const { + auto It = LE->getLambdaClass()->field_begin(); + std::advance(It, Index); + return *It; + } + + const ArrayInitLoopExpr *getArrayInitLoop() const override { + return dyn_cast_or_null<ArrayInitLoopExpr>(getInitializer()); + } + + static bool classof(const ConstructionContext *CC) { + return CC->getKind() == LambdaCaptureKind; + } +}; + } // end namespace clang #endif // LLVM_CLANG_ANALYSIS_CONSTRUCTIONCONTEXT_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Arena.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Arena.h new file mode 100644 index 000000000000..394ce054e65f --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Arena.h @@ -0,0 +1,152 @@ +//===-- Arena.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 +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H + +#include "clang/Analysis/FlowSensitive/Formula.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/StringRef.h" +#include <vector> + +namespace clang::dataflow { + +/// The Arena owns the objects that model data within an analysis. +/// For example, `Value`, `StorageLocation`, `Atom`, and `Formula`. +class Arena { +public: + Arena() + : True(Formula::create(Alloc, Formula::Literal, {}, 1)), + False(Formula::create(Alloc, Formula::Literal, {}, 0)) {} + Arena(const Arena &) = delete; + Arena &operator=(const Arena &) = delete; + + /// Creates a `T` (some subclass of `StorageLocation`), forwarding `args` to + /// the constructor, and returns a reference to it. + /// + /// The `Arena` takes ownership of the created object. The object will be + /// destroyed when the `Arena` is destroyed. + template <typename T, typename... Args> + std::enable_if_t<std::is_base_of<StorageLocation, T>::value, T &> + create(Args &&...args) { + // Note: If allocation of individual `StorageLocation`s turns out to be + // costly, consider creating specializations of `create<T>` for commonly + // used `StorageLocation` subclasses and make them use a `BumpPtrAllocator`. + return *cast<T>( + Locs.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)) + .get()); + } + + /// Creates a `T` (some subclass of `Value`), forwarding `args` to the + /// constructor, and returns a reference to it. + /// + /// The `Arena` takes ownership of the created object. The object will be + /// destroyed when the `Arena` is destroyed. + template <typename T, typename... Args> + std::enable_if_t<std::is_base_of<Value, T>::value, T &> + create(Args &&...args) { + // Note: If allocation of individual `Value`s turns out to be costly, + // consider creating specializations of `create<T>` for commonly used + // `Value` subclasses and make them use a `BumpPtrAllocator`. + return *cast<T>( + Vals.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)) + .get()); + } + + /// Creates a BoolValue wrapping a particular formula. + /// + /// Passing in the same formula will result in the same BoolValue. + /// FIXME: Interning BoolValues but not other Values is inconsistent. + /// Decide whether we want Value interning or not. + BoolValue &makeBoolValue(const Formula &); + + /// Creates a fresh atom and wraps in in an AtomicBoolValue. + /// FIXME: For now, identical-address AtomicBoolValue <=> identical atom. + /// Stop relying on pointer identity and remove this guarantee. + AtomicBoolValue &makeAtomValue() { + return cast<AtomicBoolValue>(makeBoolValue(makeAtomRef(makeAtom()))); + } + + /// Creates a fresh Top boolean value. + TopBoolValue &makeTopValue() { + // No need for deduplicating: there's no way to create aliasing Tops. + return create<TopBoolValue>(makeAtomRef(makeAtom())); + } + + /// Returns a symbolic integer value that models an integer literal equal to + /// `Value`. These literals are the same every time. + /// Integer literals are not typed; the type is determined by the `Expr` that + /// an integer literal is associated with. + IntegerValue &makeIntLiteral(llvm::APInt Value); + + // Factories for boolean formulas. + // Formulas are interned: passing the same arguments return the same result. + // For commutative operations like And/Or, interning ignores order. + // Simplifications are applied: makeOr(X, X) => X, etc. + + /// Returns a formula for the conjunction of `LHS` and `RHS`. + const Formula &makeAnd(const Formula &LHS, const Formula &RHS); + + /// Returns a formula for the disjunction of `LHS` and `RHS`. + const Formula &makeOr(const Formula &LHS, const Formula &RHS); + + /// Returns a formula for the negation of `Val`. + const Formula &makeNot(const Formula &Val); + + /// Returns a formula for `LHS => RHS`. + const Formula &makeImplies(const Formula &LHS, const Formula &RHS); + + /// Returns a formula for `LHS <=> RHS`. + const Formula &makeEquals(const Formula &LHS, const Formula &RHS); + + /// Returns a formula for the variable A. + const Formula &makeAtomRef(Atom A); + + /// Returns a formula for a literal true/false. + const Formula &makeLiteral(bool Value) { return Value ? True : False; } + + // Parses a formula from its textual representation. + // This may refer to atoms that were not produced by makeAtom() yet! + llvm::Expected<const Formula &> parseFormula(llvm::StringRef); + + /// Returns a new atomic boolean variable, distinct from any other. + Atom makeAtom() { return static_cast<Atom>(NextAtom++); }; + + /// Creates a fresh flow condition and returns a token that identifies it. The + /// token can be used to perform various operations on the flow condition such + /// as adding constraints to it, forking it, joining it with another flow + /// condition, or checking implications. + Atom makeFlowConditionToken() { return makeAtom(); } + +private: + llvm::BumpPtrAllocator Alloc; + + // Storage for the state of a program. + std::vector<std::unique_ptr<StorageLocation>> Locs; + std::vector<std::unique_ptr<Value>> Vals; + + // Indices that are used to avoid recreating the same integer literals and + // composite boolean values. + llvm::DenseMap<llvm::APInt, IntegerValue *> IntegerLiterals; + using FormulaPair = std::pair<const Formula *, const Formula *>; + llvm::DenseMap<FormulaPair, const Formula *> Ands; + llvm::DenseMap<FormulaPair, const Formula *> Ors; + llvm::DenseMap<const Formula *, const Formula *> Nots; + llvm::DenseMap<FormulaPair, const Formula *> Implies; + llvm::DenseMap<FormulaPair, const Formula *> Equals; + llvm::DenseMap<Atom, const Formula *> AtomRefs; + + llvm::DenseMap<const Formula *, BoolValue *> FormulaValues; + unsigned NextAtom = 0; + + const Formula &True, &False; +}; + +} // namespace clang::dataflow + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h new file mode 100644 index 000000000000..ecd8558970f9 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/CFGMatchSwitch.h @@ -0,0 +1,98 @@ +//===---- CFGMatchSwitch.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 the `CFGMatchSwitch` abstraction for building a "switch" +// statement for control flow graph elements. Each case of the switch is +// defined by an ASTMatcher which is applied on the AST node contained in the +// input `CFGElement`. +// +// Currently, the `CFGMatchSwitch` only handles `CFGElement`s of +// `Kind::Statement` and `Kind::Initializer`. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_ +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/MatchSwitch.h" +#include <functional> +#include <utility> + +namespace clang { +namespace dataflow { + +template <typename State, typename Result = void> +using CFGMatchSwitch = + std::function<Result(const CFGElement &, ASTContext &, State &)>; + +/// Collects cases of a "match switch": a collection of matchers paired with +/// callbacks, which together define a switch that can be applied to an AST node +/// contained in a CFG element. +template <typename State, typename Result = void> class CFGMatchSwitchBuilder { +public: + /// Registers an action `A` for `CFGStmt`s that will be triggered by the match + /// of the pattern `M` against the `Stmt` contained in the input `CFGStmt`. + /// + /// Requirements: + /// + /// `NodeT` should be derived from `Stmt`. + template <typename NodeT> + CFGMatchSwitchBuilder && + CaseOfCFGStmt(MatchSwitchMatcher<Stmt> M, + MatchSwitchAction<NodeT, State, Result> A) && { + std::move(StmtBuilder).template CaseOf<NodeT>(M, A); + return std::move(*this); + } + + /// Registers an action `A` for `CFGInitializer`s that will be triggered by + /// the match of the pattern `M` against the `CXXCtorInitializer` contained in + /// the input `CFGInitializer`. + /// + /// Requirements: + /// + /// `NodeT` should be derived from `CXXCtorInitializer`. + template <typename NodeT> + CFGMatchSwitchBuilder && + CaseOfCFGInit(MatchSwitchMatcher<CXXCtorInitializer> M, + MatchSwitchAction<NodeT, State, Result> A) && { + std::move(InitBuilder).template CaseOf<NodeT>(M, A); + return std::move(*this); + } + + CFGMatchSwitch<State, Result> Build() && { + return [StmtMS = std::move(StmtBuilder).Build(), + InitMS = std::move(InitBuilder).Build()](const CFGElement &Element, + ASTContext &Context, + State &S) -> Result { + switch (Element.getKind()) { + case CFGElement::Initializer: + return InitMS(*Element.castAs<CFGInitializer>().getInitializer(), + Context, S); + case CFGElement::Statement: + case CFGElement::Constructor: + case CFGElement::CXXRecordTypedCall: + return StmtMS(*Element.castAs<CFGStmt>().getStmt(), Context, S); + default: + // FIXME: Handle other kinds of CFGElement. + return Result(); + } + }; + } + +private: + ASTMatchSwitchBuilder<Stmt, State, Result> StmtBuilder; + ASTMatchSwitchBuilder<CXXCtorInitializer, State, Result> InitBuilder; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CFGMATCHSWITCH_H_ diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h new file mode 100644 index 000000000000..405e93287a05 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h @@ -0,0 +1,79 @@ +//===-- ControlFlowContext.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 ControlFlowContext class that is used by dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/Support/Error.h" +#include <memory> +#include <utility> + +namespace clang { +namespace dataflow { + +/// Holds CFG and other derived context that is needed to perform dataflow +/// analysis. +class ControlFlowContext { +public: + /// Builds a ControlFlowContext from a `FunctionDecl`. + /// `Func.doesThisDeclarationHaveABody()` must be true, and + /// `Func.isTemplated()` must be false. + static llvm::Expected<ControlFlowContext> build(const FunctionDecl &Func); + + /// Builds a ControlFlowContext from an AST node. `D` is the function in which + /// `S` resides. `D.isTemplated()` must be false. + static llvm::Expected<ControlFlowContext> build(const Decl &D, Stmt &S, + ASTContext &C); + + /// Returns the `Decl` containing the statement used to construct the CFG, if + /// available. + const Decl &getDecl() const { return ContainingDecl; } + + /// Returns the CFG that is stored in this context. + const CFG &getCFG() const { return *Cfg; } + + /// Returns a mapping from statements to basic blocks that contain them. + const llvm::DenseMap<const Stmt *, const CFGBlock *> &getStmtToBlock() const { + return StmtToBlock; + } + + /// Returns whether `B` is reachable from the entry block. + bool isBlockReachable(const CFGBlock &B) const { + return BlockReachable[B.getBlockID()]; + } + +private: + ControlFlowContext(const Decl &D, std::unique_ptr<CFG> Cfg, + llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock, + llvm::BitVector BlockReachable) + : ContainingDecl(D), Cfg(std::move(Cfg)), + StmtToBlock(std::move(StmtToBlock)), + BlockReachable(std::move(BlockReachable)) {} + + /// The `Decl` containing the statement used to construct the CFG. + const Decl &ContainingDecl; + std::unique_ptr<CFG> Cfg; + llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock; + llvm::BitVector BlockReachable; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h new file mode 100644 index 000000000000..b95095d2184c --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h @@ -0,0 +1,332 @@ +//===- DataflowAnalysis.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 base types and functions for building dataflow analyses +// that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H + +#include <iterator> +#include <optional> +#include <type_traits> +#include <utility> +#include <vector> + +#include "clang/AST/ASTContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/MatchSwitch.h" +#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/STLFunctionalExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/Errc.h" +#include "llvm/Support/Error.h" + +namespace clang { +namespace dataflow { + +/// Base class template for dataflow analyses built on a single lattice type. +/// +/// Requirements: +/// +/// `Derived` must be derived from a specialization of this class template and +/// must provide the following public members: +/// * `LatticeT initialElement()` - returns a lattice element that models the +/// initial state of a basic block; +/// * `void transfer(const CFGElement &, LatticeT &, Environment &)` - applies +/// the analysis transfer function for a given CFG element and lattice +/// element. +/// +/// `Derived` can optionally provide the following members: +/// * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice &E, +/// Environment &Env)` - applies the analysis transfer +/// function for a given edge from a CFG block of a conditional statement. +/// +/// `Derived` can optionally override the following members: +/// * `bool merge(QualType, const Value &, const Value &, Value &, +/// Environment &)` - joins distinct values. This could be a strict +/// lattice join or a more general widening operation. +/// +/// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must +/// provide the following public members: +/// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the +/// argument by computing their least upper bound, modifies the object if +/// necessary, and returns an effect indicating whether any changes were +/// made to it; +/// FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)` +/// * `bool operator==(const LatticeT &) const` - returns true if and only if +/// the object is equal to the argument. +/// +/// `LatticeT` can optionally provide the following members: +/// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the +/// lattice element with an approximation that can reach a fixed point more +/// quickly than iterated application of the transfer function alone. The +/// previous value is provided to inform the choice of widened value. The +/// function must also serve as a comparison operation, by indicating whether +/// the widened value is equivalent to the previous value with the returned +/// `LatticeJoinEffect`. +template <typename Derived, typename LatticeT> +class DataflowAnalysis : public TypeErasedDataflowAnalysis { +public: + /// Bounded join-semilattice that is used in the analysis. + using Lattice = LatticeT; + + explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} + + explicit DataflowAnalysis(ASTContext &Context, + DataflowAnalysisOptions Options) + : TypeErasedDataflowAnalysis(Options), Context(Context) {} + + ASTContext &getASTContext() final { return Context; } + + TypeErasedLattice typeErasedInitialElement() final { + return {static_cast<Derived *>(this)->initialElement()}; + } + + TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1, + const TypeErasedLattice &E2) final { + // FIXME: change the signature of join() to avoid copying here. + Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value); + const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); + L1.join(L2); + return {std::move(L1)}; + } + + LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, + const TypeErasedLattice &Previous) final { + Lattice &C = llvm::any_cast<Lattice &>(Current.Value); + const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value); + return widenInternal(Rank0{}, C, P); + } + + bool isEqualTypeErased(const TypeErasedLattice &E1, + const TypeErasedLattice &E2) final { + const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); + const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); + return L1 == L2; + } + + void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E, + Environment &Env) final { + Lattice &L = llvm::any_cast<Lattice &>(E.Value); + static_cast<Derived *>(this)->transfer(Element, L, Env); + } + + void transferBranchTypeErased(bool Branch, const Stmt *Stmt, + TypeErasedLattice &E, Environment &Env) final { + transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt, + E, Env); + } + +private: + // These `Rank` structs are used for template metaprogramming to choose + // between overloads. + struct Rank1 {}; + struct Rank0 : Rank1 {}; + + // The first-choice implementation: use `widen` when it is available. + template <typename T> + static auto widenInternal(Rank0, T &Current, const T &Prev) + -> decltype(Current.widen(Prev)) { + return Current.widen(Prev); + } + + // The second-choice implementation: `widen` is unavailable. Widening is + // merged with equality checking, so when widening is unimplemented, we + // default to equality checking. + static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current, + const Lattice &Prev) { + return Prev == Current ? LatticeJoinEffect::Unchanged + : LatticeJoinEffect::Changed; + } + + // The first-choice implementation: `transferBranch` is implemented. + template <typename Analysis> + static auto transferBranchInternal(Rank0, Analysis &A, bool Branch, + const Stmt *Stmt, TypeErasedLattice &L, + Environment &Env) + -> std::void_t<decltype(A.transferBranch( + Branch, Stmt, std::declval<LatticeT &>(), Env))> { + A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env); + } + + // The second-choice implementation: `transferBranch` is unimplemented. No-op. + template <typename Analysis> + static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *, + TypeErasedLattice &, Environment &) {} + + ASTContext &Context; +}; + +// Model of the program at a given program point. +template <typename LatticeT> struct DataflowAnalysisState { + // Model of a program property. + LatticeT Lattice; + + // Model of the state of the program (store and heap). + Environment Env; +}; + +/// Performs dataflow analysis and returns a mapping from basic block IDs to +/// dataflow analysis states that model the respective basic blocks. The +/// returned vector, if any, will have the same size as the number of CFG +/// blocks, with indices corresponding to basic block IDs. Returns an error if +/// the dataflow analysis cannot be performed successfully. Otherwise, calls +/// `PostVisitCFG` on each CFG element with the final analysis results at that +/// program point. +/// +/// `MaxBlockVisits` caps the number of block visits during analysis. See +/// `runTypeErasedDataflowAnalysis` for a full description. The default value is +/// essentially arbitrary -- large enough to accommodate what seems like any +/// reasonable CFG, but still small enough to limit the cost of hitting the +/// limit. +template <typename AnalysisT> +llvm::Expected<std::vector< + std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> +runDataflowAnalysis( + const ControlFlowContext &CFCtx, AnalysisT &Analysis, + const Environment &InitEnv, + std::function<void(const CFGElement &, const DataflowAnalysisState< + typename AnalysisT::Lattice> &)> + PostVisitCFG = nullptr, + std::int32_t MaxBlockVisits = 20'000) { + std::function<void(const CFGElement &, + const TypeErasedDataflowAnalysisState &)> + PostVisitCFGClosure = nullptr; + if (PostVisitCFG) { + PostVisitCFGClosure = [&PostVisitCFG]( + const CFGElement &Element, + const TypeErasedDataflowAnalysisState &State) { + auto *Lattice = + llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); + // FIXME: we should not be copying the environment here! + // Ultimately the PostVisitCFG only gets a const reference anyway. + PostVisitCFG(Element, DataflowAnalysisState<typename AnalysisT::Lattice>{ + *Lattice, State.Env.fork()}); + }; + } + + auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( + CFCtx, Analysis, InitEnv, PostVisitCFGClosure, MaxBlockVisits); + if (!TypeErasedBlockStates) + return TypeErasedBlockStates.takeError(); + + std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> + BlockStates; + BlockStates.reserve(TypeErasedBlockStates->size()); + + llvm::transform( + std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates), + [](auto &OptState) { + return llvm::transformOptional( + std::move(OptState), [](TypeErasedDataflowAnalysisState &&State) { + return DataflowAnalysisState<typename AnalysisT::Lattice>{ + llvm::any_cast<typename AnalysisT::Lattice>( + std::move(State.Lattice.Value)), + std::move(State.Env)}; + }); + }); + return std::move(BlockStates); +} + +// Create an analysis class that is derived from `DataflowAnalysis`. This is an +// SFINAE adapter that allows us to call two different variants of constructor +// (either with or without the optional `Environment` parameter). +// FIXME: Make all classes derived from `DataflowAnalysis` take an `Environment` +// parameter in their constructor so that we can get rid of this abomination. +template <typename AnalysisT> +auto createAnalysis(ASTContext &ASTCtx, Environment &Env) + -> decltype(AnalysisT(ASTCtx, Env)) { + return AnalysisT(ASTCtx, Env); +} +template <typename AnalysisT> +auto createAnalysis(ASTContext &ASTCtx, Environment &Env) + -> decltype(AnalysisT(ASTCtx)) { + return AnalysisT(ASTCtx); +} + +/// Runs a dataflow analysis over the given function and then runs `Diagnoser` +/// over the results. Returns a list of diagnostics for `FuncDecl` or an +/// error. Currently, errors can occur (at least) because the analysis requires +/// too many iterations over the CFG or the SAT solver times out. +/// +/// The default value of `MaxSATIterations` was chosen based on the following +/// observations: +/// - Non-pathological calls to the solver typically require only a few hundred +/// iterations. +/// - This limit is still low enough to keep runtimes acceptable (on typical +/// machines) in cases where we hit the limit. +/// +/// `MaxBlockVisits` caps the number of block visits during analysis. See +/// `runDataflowAnalysis` for a full description and explanation of the default +/// value. +template <typename AnalysisT, typename Diagnostic> +llvm::Expected<llvm::SmallVector<Diagnostic>> diagnoseFunction( + const FunctionDecl &FuncDecl, ASTContext &ASTCtx, + llvm::function_ref<llvm::SmallVector<Diagnostic>( + const CFGElement &, ASTContext &, + const TransferStateForDiagnostics<typename AnalysisT::Lattice> &)> + Diagnoser, + std::int64_t MaxSATIterations = 1'000'000'000, + std::int32_t MaxBlockVisits = 20'000) { + llvm::Expected<ControlFlowContext> Context = + ControlFlowContext::build(FuncDecl); + if (!Context) + return Context.takeError(); + + auto OwnedSolver = std::make_unique<WatchedLiteralsSolver>(MaxSATIterations); + const WatchedLiteralsSolver *Solver = OwnedSolver.get(); + DataflowAnalysisContext AnalysisContext(std::move(OwnedSolver)); + Environment Env(AnalysisContext, FuncDecl); + AnalysisT Analysis = createAnalysis<AnalysisT>(ASTCtx, Env); + llvm::SmallVector<Diagnostic> Diagnostics; + if (llvm::Error Err = + runTypeErasedDataflowAnalysis( + *Context, Analysis, Env, + [&ASTCtx, &Diagnoser, &Diagnostics]( + const CFGElement &Elt, + const TypeErasedDataflowAnalysisState &State) mutable { + auto EltDiagnostics = Diagnoser( + Elt, ASTCtx, + TransferStateForDiagnostics<typename AnalysisT::Lattice>( + llvm::any_cast<const typename AnalysisT::Lattice &>( + State.Lattice.Value), + State.Env)); + llvm::move(EltDiagnostics, std::back_inserter(Diagnostics)); + }, + MaxBlockVisits) + .takeError()) + return std::move(Err); + + if (Solver->reachedLimit()) + return llvm::createStringError(llvm::errc::interrupted, + "SAT solver timed out"); + + return Diagnostics; +} + +/// Abstract base class for dataflow "models": reusable analysis components that +/// model a particular aspect of program semantics in the `Environment`. For +/// example, a model may capture a type and its related functions. +class DataflowModel : public Environment::ValueModel { +public: + /// Return value indicates whether the model processed the `Element`. + virtual bool transfer(const CFGElement &Element, Environment &Env) = 0; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h new file mode 100644 index 000000000000..20e45cc27b01 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -0,0 +1,304 @@ +//===-- 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/AST/Expr.h" +#include "clang/AST/TypeOrdering.h" +#include "clang/Analysis/FlowSensitive/Arena.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" +#include "clang/Analysis/FlowSensitive/Solver.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/Support/Compiler.h" +#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. + unsigned Depth = 2; +}; + +/// Owns objects that encompass the state of a program and stores context that +/// is used during dataflow analysis. +class DataflowAnalysisContext { +public: + struct Options { + /// Options for analyzing function bodies when present in the translation + /// unit, or empty to disable context-sensitive analysis. Note that this is + /// fundamentally limited: some constructs, such as recursion, are + /// explicitly unsupported. + std::optional<ContextSensitiveOptions> ContextSensitiveOpts; + + /// If provided, analysis details will be recorded here. + /// (This is always non-null within an AnalysisContext, the framework + /// provides a fallback no-op logger). + Logger *Log = nullptr; + }; + + /// Constructs a dataflow analysis context. + /// + /// Requirements: + /// + /// `S` must not be null. + DataflowAnalysisContext(std::unique_ptr<Solver> S, + Options Opts = Options{ + /*ContextSensitiveOpts=*/std::nullopt, + /*Logger=*/nullptr}); + ~DataflowAnalysisContext(); + + /// Sets a callback that returns the names and types of the synthetic fields + /// to add to a `RecordStorageLocation` of a given type. + /// Typically, this is called from the constructor of a `DataflowAnalysis` + /// + /// To maintain the invariant that all `RecordStorageLocation`s of a given + /// type have the same fields: + /// * The callback must always return the same result for a given type + /// * `setSyntheticFieldCallback()` must be called before any + // `RecordStorageLocation`s are created. + void setSyntheticFieldCallback( + std::function<llvm::StringMap<QualType>(QualType)> CB) { + assert(!RecordStorageLocationCreated); + SyntheticFieldCallback = CB; + } + + /// Returns a new storage location appropriate for `Type`. + /// + /// A null `Type` is interpreted as the pointee type of `std::nullptr_t`. + StorageLocation &createStorageLocation(QualType Type); + + /// Creates a `RecordStorageLocation` for the given type and with the given + /// fields. + /// + /// Requirements: + /// + /// `FieldLocs` must contain exactly the fields returned by + /// `getModeledFields(Type)`. + /// `SyntheticFields` must contain exactly the fields returned by + /// `getSyntheticFields(Type)`. + RecordStorageLocation &createRecordStorageLocation( + QualType Type, RecordStorageLocation::FieldToLoc FieldLocs, + RecordStorageLocation::SyntheticFieldMap SyntheticFields); + + /// Returns a stable storage location for `D`. + StorageLocation &getStableStorageLocation(const ValueDecl &D); + + /// Returns a stable storage location for `E`. + StorageLocation &getStableStorageLocation(const Expr &E); + + /// Returns a pointer value that represents a null pointer. Calls with + /// `PointeeType` that are canonically equivalent will return the same result. + /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`. + PointerValue &getOrCreateNullPointerValue(QualType PointeeType); + + /// Adds `Constraint` to current and future flow conditions in this context. + /// + /// Invariants must contain only flow-insensitive information, i.e. facts that + /// are true on all paths through the program. + /// Information can be added eagerly (when analysis begins), or lazily (e.g. + /// when values are first used). The analysis must be careful that the same + /// information is added regardless of which order blocks are analyzed in. + void addInvariant(const Formula &Constraint); + + /// Adds `Constraint` to the flow condition identified by `Token`. + void addFlowConditionConstraint(Atom Token, const Formula &Constraint); + + /// Creates a new flow condition with the same constraints as the flow + /// condition identified by `Token` and returns its token. + Atom forkFlowCondition(Atom Token); + + /// Creates a new flow condition that represents the disjunction of the flow + /// conditions identified by `FirstToken` and `SecondToken`, and returns its + /// token. + Atom joinFlowConditions(Atom FirstToken, Atom SecondToken); + + /// Returns true if the constraints of the flow condition identified by + /// `Token` imply that `F` is true. + /// Returns false if the flow condition does not imply `F` or if the solver + /// times out. + bool flowConditionImplies(Atom Token, const Formula &F); + + /// Returns true if the constraints of the flow condition identified by + /// `Token` still allow `F` to be true. + /// Returns false if the flow condition implies that `F` is false or if the + /// solver times out. + bool flowConditionAllows(Atom Token, const Formula &F); + + /// Returns true if `Val1` is equivalent to `Val2`. + /// Note: This function doesn't take into account constraints on `Val1` and + /// `Val2` imposed by the flow condition. + bool equivalentFormulas(const Formula &Val1, const Formula &Val2); + + LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token, + llvm::raw_ostream &OS = llvm::dbgs()); + + /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise, + /// returns null. + const ControlFlowContext *getControlFlowContext(const FunctionDecl *F); + + const Options &getOptions() { return Opts; } + + Arena &arena() { return *A; } + + /// Returns the outcome of satisfiability checking on `Constraints`. + /// + /// Flow conditions are not incorporated, so they may need to be manually + /// included in `Constraints` to provide contextually-accurate results, e.g. + /// if any definitions or relationships of the values in `Constraints` have + /// been stored in flow conditions. + Solver::Result querySolver(llvm::SetVector<const Formula *> Constraints); + + /// Returns the fields of `Type`, limited to the set of fields modeled by this + /// context. + FieldSet getModeledFields(QualType Type); + + /// Returns the names and types of the synthetic fields for the given record + /// type. + llvm::StringMap<QualType> getSyntheticFields(QualType Type) { + assert(Type->isRecordType()); + if (SyntheticFieldCallback) + return SyntheticFieldCallback(Type); + return {}; + } + +private: + friend class Environment; + + struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> { + static QualType getEmptyKey() { + // Allow a NULL `QualType` by using a different value as the empty key. + return QualType::getFromOpaquePtr(reinterpret_cast<Type *>(1)); + } + + using DenseMapInfo::getHashValue; + using DenseMapInfo::getTombstoneKey; + using DenseMapInfo::isEqual; + }; + + // Extends the set of modeled field declarations. + void addModeledFields(const FieldSet &Fields); + + /// Adds all constraints of the flow condition identified by `Token` and all + /// of its transitive dependencies to `Constraints`. + void + addTransitiveFlowConditionConstraints(Atom Token, + llvm::SetVector<const Formula *> &Out); + + /// Returns true if the solver is able to prove that there is a satisfying + /// assignment for `Constraints`. + bool isSatisfiable(llvm::SetVector<const Formula *> Constraints) { + return querySolver(std::move(Constraints)).getStatus() == + Solver::Result::Status::Satisfiable; + } + + /// Returns true if the solver is able to prove that there is no satisfying + /// assignment for `Constraints` + bool isUnsatisfiable(llvm::SetVector<const Formula *> Constraints) { + return querySolver(std::move(Constraints)).getStatus() == + Solver::Result::Status::Unsatisfiable; + } + + std::unique_ptr<Solver> S; + std::unique_ptr<Arena> A; + + // 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<const ValueDecl *, StorageLocation *> DeclToLoc; + llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; + + // Null pointer values, keyed by the canonical pointee type. + // + // FIXME: The pointer values are indexed by the pointee types which are + // required to initialize the `PointeeLoc` field in `PointerValue`. Consider + // creating a type-independent `NullPointerValue` without a `PointeeLoc` + // field. + llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo> + NullPointerVals; + + Options Opts; + + // Flow conditions are tracked symbolically: each unique flow condition is + // associated with a fresh symbolic variable (token), bound to the clause that + // defines the flow condition. Conceptually, each binding corresponds to an + // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition + // token (an atomic boolean) and `Ci`s are the set of constraints in the flow + // flow condition clause. The set of constraints (C1 ^ C2 ^ ...) are stored in + // the `FlowConditionConstraints` map, keyed by the token of the flow + // condition. + // + // Flow conditions depend on other flow conditions if they are created using + // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition + // dependencies is stored in the `FlowConditionDeps` map. + llvm::DenseMap<Atom, llvm::DenseSet<Atom>> FlowConditionDeps; + llvm::DenseMap<Atom, const Formula *> FlowConditionConstraints; + const Formula *Invariant = nullptr; + + llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts; + + // Fields modeled by environments covered by this context. + FieldSet ModeledFields; + + std::unique_ptr<Logger> LogOwner; // If created via flags. + + std::function<llvm::StringMap<QualType>(QualType)> SyntheticFieldCallback; + + /// Has any `RecordStorageLocation` been created yet? + bool RecordStorageLocationCreated = false; +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h new file mode 100644 index 000000000000..1543f900e401 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -0,0 +1,739 @@ +//===-- DataflowEnvironment.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 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. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H + +#include "clang/AST/Decl.h" +#include "clang/AST/DeclBase.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Type.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "clang/Analysis/FlowSensitive/Formula.h" +#include "clang/Analysis/FlowSensitive/Logger.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include <memory> +#include <type_traits> +#include <utility> + +namespace clang { +namespace dataflow { + +/// Indicates the result of a tentative comparison. +enum class ComparisonResult { + Same, + Different, + Unknown, +}; + +/// Holds the state of the program (store and heap) at a given program point. +/// +/// WARNING: Symbolic values that are created by the environment for static +/// local and global variables are not currently invalidated on function calls. +/// This is unsound and should be taken into account when designing dataflow +/// analyses. +class Environment { +public: + /// Supplements `Environment` with non-standard comparison and join + /// operations. + class ValueModel { + public: + virtual ~ValueModel() = default; + + /// Returns: + /// `Same`: `Val1` is equivalent to `Val2`, according to the model. + /// `Different`: `Val1` is distinct from `Val2`, according to the model. + /// `Unknown`: The model can't determine a relationship between `Val1` and + /// `Val2`. + /// + /// Requirements: + /// + /// `Val1` and `Val2` must be distinct. + /// + /// `Val1` and `Val2` must model values of type `Type`. + /// + /// `Val1` and `Val2` must be assigned to the same storage location in + /// `Env1` and `Env2` respectively. + virtual ComparisonResult compare(QualType Type, const Value &Val1, + const Environment &Env1, const Value &Val2, + const Environment &Env2) { + // FIXME: Consider adding QualType to RecordValue and removing the Type + // argument here. + return ComparisonResult::Unknown; + } + + /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could + /// be a strict lattice join or a more general widening operation. + /// + /// If this function returns true, `MergedVal` will be assigned to a storage + /// location of type `Type` in `MergedEnv`. + /// + /// `Env1` and `Env2` can be used to query child values and path condition + /// implications of `Val1` and `Val2` respectively. + /// + /// Requirements: + /// + /// `Val1` and `Val2` must be distinct. + /// + /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`. + /// + /// `Val1` and `Val2` must be assigned to the same storage location in + /// `Env1` and `Env2` respectively. + virtual bool merge(QualType Type, const Value &Val1, + const Environment &Env1, const Value &Val2, + const Environment &Env2, Value &MergedVal, + Environment &MergedEnv) { + return true; + } + + /// This function may widen the current value -- replace it with an + /// approximation that can reach a fixed point more quickly than iterated + /// application of the transfer function alone. The previous value is + /// provided to inform the choice of widened value. The function must also + /// serve as a comparison operation, by indicating whether the widened value + /// is equivalent to the previous value. + /// + /// Returns either: + /// + /// `nullptr`, if this value is not of interest to the model, or + /// + /// `&Prev`, if the widened value is equivalent to `Prev`, or + /// + /// A non-null value that approximates `Current`. `Prev` is available to + /// inform the chosen approximation. + /// + /// `PrevEnv` and `CurrentEnv` can be used to query child values and path + /// condition implications of `Prev` and `Current`, respectively. + /// + /// Requirements: + /// + /// `Prev` and `Current` must model values of type `Type`. + /// + /// `Prev` and `Current` must be assigned to the same storage location in + /// `PrevEnv` and `CurrentEnv`, respectively. + virtual Value *widen(QualType Type, Value &Prev, const Environment &PrevEnv, + Value &Current, Environment &CurrentEnv) { + // The default implementation reduces to just comparison, since comparison + // is required by the API, even if no widening is performed. + switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { + case ComparisonResult::Same: + return &Prev; + case ComparisonResult::Different: + return &Current; + case ComparisonResult::Unknown: + return nullptr; + } + llvm_unreachable("all cases in switch covered"); + } + }; + + /// Creates an environment that uses `DACtx` to store objects that encompass + /// the state of a program. + explicit Environment(DataflowAnalysisContext &DACtx); + + // Copy-constructor is private, Environments should not be copied. See fork(). + Environment &operator=(const Environment &Other) = delete; + + Environment(Environment &&Other) = default; + Environment &operator=(Environment &&Other) = default; + + /// Creates an environment that uses `DACtx` to store objects that encompass + /// the state of a program. + /// + /// If `DeclCtx` is a function, initializes the environment with symbolic + /// representations of the function parameters. + /// + /// If `DeclCtx` is a non-static member function, initializes the environment + /// with a symbolic representation of the `this` pointee. + Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx); + + /// Assigns storage locations and values to all parameters, captures, global + /// variables, fields and functions referenced in the function currently being + /// analyzed. + /// + /// Requirements: + /// + /// The function must have a body, i.e. + /// `FunctionDecl::doesThisDecalarationHaveABody()` must be true. + void initialize(); + + /// Returns a new environment that is a copy of this one. + /// + /// The state of the program is initially the same, but can be mutated without + /// affecting the original. + /// + /// However the original should not be further mutated, as this may interfere + /// with the fork. (In practice, values are stored independently, but the + /// forked flow condition references the original). + Environment fork() const; + + /// Creates and returns an environment to use for an inline analysis of the + /// callee. Uses the storage location from each argument in the `Call` as the + /// storage location for the corresponding parameter in the callee. + /// + /// Requirements: + /// + /// The callee of `Call` must be a `FunctionDecl`. + /// + /// The body of the callee must not reference globals. + /// + /// The arguments of `Call` must map 1:1 to the callee's parameters. + Environment pushCall(const CallExpr *Call) const; + Environment pushCall(const CXXConstructExpr *Call) const; + + /// Moves gathered information back into `this` from a `CalleeEnv` created via + /// `pushCall`. + void popCall(const CallExpr *Call, const Environment &CalleeEnv); + void popCall(const CXXConstructExpr *Call, const Environment &CalleeEnv); + + /// Returns true if and only if the environment is equivalent to `Other`, i.e + /// the two environments: + /// - have the same mappings from declarations to storage locations, + /// - have the same mappings from expressions to storage locations, + /// - have the same or equivalent (according to `Model`) values assigned to + /// the same storage locations. + /// + /// Requirements: + /// + /// `Other` and `this` must use the same `DataflowAnalysisContext`. + bool equivalentTo(const Environment &Other, + Environment::ValueModel &Model) const; + + /// Joins two environments by taking the intersection of storage locations and + /// values that are stored in them. Distinct values that are assigned to the + /// same storage locations in `EnvA` and `EnvB` are merged using `Model`. + /// + /// Requirements: + /// + /// `EnvA` and `EnvB` must use the same `DataflowAnalysisContext`. + static Environment join(const Environment &EnvA, const Environment &EnvB, + Environment::ValueModel &Model); + + /// Widens the environment point-wise, using `PrevEnv` as needed to inform the + /// approximation. + /// + /// Requirements: + /// + /// `PrevEnv` must be the immediate previous version of the environment. + /// `PrevEnv` and `this` must use the same `DataflowAnalysisContext`. + LatticeJoinEffect widen(const Environment &PrevEnv, + Environment::ValueModel &Model); + + // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`, + // `getStableStorageLocation`, or something more appropriate. + + /// 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 ValueDecl &D); + + /// Creates a storage location for `E`. Does not assign the returned storage + /// location to `E` in the environment. Does not assign a value to the + /// returned storage location in the environment. + StorageLocation &createStorageLocation(const Expr &E); + + /// Assigns `Loc` as the storage location of `D` in the environment. + /// + /// Requirements: + /// + /// `D` must not already have 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; + + /// Removes the location assigned to `D` in the environment (if any). + void removeDecl(const ValueDecl &D); + + /// Assigns `Loc` as the storage location of the glvalue `E` in the + /// environment. + /// + /// Requirements: + /// + /// `E` must not be assigned a storage location in the environment. + /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` + void setStorageLocation(const Expr &E, StorageLocation &Loc); + + /// Returns the storage location assigned to the glvalue `E` in the + /// environment, or null if `E` isn't assigned a storage location in the + /// environment. + /// + /// Requirements: + /// `E` must be a glvalue or a `BuiltinType::BuiltinFn` + StorageLocation *getStorageLocation(const Expr &E) const; + + /// Returns the result of casting `getStorageLocation(...)` to a subclass of + /// `StorageLocation` (using `cast_or_null<T>`). + /// This assert-fails if the result of `getStorageLocation(...)` is not of + /// type `T *`; if the storage location is not guaranteed to have type `T *`, + /// consider using `dyn_cast_or_null<T>(getStorageLocation(...))` instead. + template <typename T> + std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> + get(const ValueDecl &D) const { + return cast_or_null<T>(getStorageLocation(D)); + } + template <typename T> + std::enable_if_t<std::is_base_of_v<StorageLocation, T>, T *> + get(const Expr &E) const { + return cast_or_null<T>(getStorageLocation(E)); + } + + /// Returns the storage location assigned to the `this` pointee in the + /// environment or null if the `this` pointee has no assigned storage location + /// in the environment. + RecordStorageLocation *getThisPointeeStorageLocation() const { + return ThisPointeeLoc; + } + + /// Sets the storage location assigned to the `this` pointee in the + /// environment. + void setThisPointeeStorageLocation(RecordStorageLocation &Loc) { + ThisPointeeLoc = &Loc; + } + + /// Returns the location of the result object for a record-type prvalue. + /// + /// In C++, prvalues of record type serve only a limited purpose: They can + /// only be used to initialize a result object (e.g. a variable or a + /// temporary). This function returns the location of that result object. + /// + /// When creating a prvalue of record type, we already need the storage + /// location of the result object to pass in `this`, even though prvalues are + /// otherwise not associated with storage locations. + /// + /// FIXME: Currently, this simply returns a stable storage location for `E`, + /// but this doesn't do the right thing in scenarios like the following: + /// ``` + /// MyClass c = some_condition()? MyClass(foo) : MyClass(bar); + /// ``` + /// Here, `MyClass(foo)` and `MyClass(bar)` will have two different storage + /// locations, when in fact their storage locations should be the same. + /// Eventually, we want to propagate storage locations from result objects + /// down to the prvalues that initialize them, similar to the way that this is + /// done in Clang's CodeGen. + /// + /// Requirements: + /// `E` must be a prvalue of record type. + RecordStorageLocation & + getResultObjectLocation(const Expr &RecordPRValue) const; + + /// Returns the return value of the current function. This can be null if: + /// - The function has a void return type + /// - No return value could be determined for the function, for example + /// because it calls a function without a body. + /// + /// Requirements: + /// The current function must have a non-reference return type. + Value *getReturnValue() const { + assert(getCurrentFunc() != nullptr && + !getCurrentFunc()->getReturnType()->isReferenceType()); + return ReturnVal; + } + + /// Returns the storage location for the reference returned by the current + /// function. This can be null if function doesn't return a single consistent + /// reference. + /// + /// Requirements: + /// The current function must have a reference return type. + StorageLocation *getReturnStorageLocation() const { + assert(getCurrentFunc() != nullptr && + getCurrentFunc()->getReturnType()->isReferenceType()); + return ReturnLoc; + } + + /// Sets the return value of the current function. + /// + /// Requirements: + /// The current function must have a non-reference return type. + void setReturnValue(Value *Val) { + assert(getCurrentFunc() != nullptr && + !getCurrentFunc()->getReturnType()->isReferenceType()); + ReturnVal = Val; + } + + /// Sets the storage location for the reference returned by the current + /// function. + /// + /// Requirements: + /// The current function must have a reference return type. + void setReturnStorageLocation(StorageLocation *Loc) { + assert(getCurrentFunc() != nullptr && + getCurrentFunc()->getReturnType()->isReferenceType()); + ReturnLoc = Loc; + } + + /// Returns a pointer value that represents a null pointer. Calls with + /// `PointeeType` that are canonically equivalent will return the same result. + PointerValue &getOrCreateNullPointerValue(QualType PointeeType); + + /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise + /// returns 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. + /// + /// If `Type` is a class, struct, or union type, creates values for all + /// modeled fields (including synthetic fields) and calls `setValue()` to + /// associate the `RecordValue` with its storage location + /// (`RecordValue::getLoc()`). + /// + /// If `Type` is one of the following types, this function will always return + /// a non-null pointer: + /// - `bool` + /// - Any integer type + /// - Any class, struct, or union type + /// + /// Requirements: + /// + /// `Type` must not be null. + Value *createValue(QualType Type); + + /// Creates an object (i.e. a storage location with an associated value) of + /// type `Ty`. If `InitExpr` is non-null and has a value associated with it, + /// initializes the object with this value. Otherwise, initializes the object + /// with a value created using `createValue()`. + StorageLocation &createObject(QualType Ty, const Expr *InitExpr = nullptr) { + return createObjectInternal(nullptr, Ty, InitExpr); + } + + /// Creates an object for the variable declaration `D`. If `D` has an + /// initializer and this initializer is associated with a value, initializes + /// the object with this value. Otherwise, initializes the object with a + /// value created using `createValue()`. Uses the storage location returned by + /// `DataflowAnalysisContext::getStableStorageLocation(D)`. + StorageLocation &createObject(const VarDecl &D) { + return createObjectInternal(&D, D.getType(), D.getInit()); + } + + /// Creates an object for the variable declaration `D`. If `InitExpr` is + /// non-null and has a value associated with it, initializes the object with + /// this value. Otherwise, initializes the object with a value created using + /// `createValue()`. Uses the storage location returned by + /// `DataflowAnalysisContext::getStableStorageLocation(D)`. + StorageLocation &createObject(const ValueDecl &D, const Expr *InitExpr) { + return createObjectInternal(&D, D.getType(), InitExpr); + } + + /// Assigns `Val` as the value of `Loc` in the environment. + void setValue(const StorageLocation &Loc, Value &Val); + + /// Clears any association between `Loc` and a value in the environment. + void clearValue(const StorageLocation &Loc) { LocToVal.erase(&Loc); } + + /// Assigns `Val` as the value of the prvalue `E` in the environment. + /// + /// Requirements: + /// + /// - `E` must be a prvalue + /// - If `Val` is a `RecordValue`, its `RecordStorageLocation` must be + /// `getResultObjectLocation(E)`. An exception to this is if `E` is an + /// expression that originally creates a `RecordValue` (such as a + /// `CXXConstructExpr` or `CallExpr`), as these establish the location of + /// the result object in the first place. + void setValue(const Expr &E, 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; + + /// Equivalent to `getValue(getStorageLocation(D))` if `D` is assigned a + /// storage location in the environment, otherwise returns null. + Value *getValue(const ValueDecl &D) const; + + /// Equivalent to `getValue(getStorageLocation(E, SP))` if `E` is assigned a + /// storage location in the environment, otherwise returns null. + Value *getValue(const Expr &E) const; + + /// Returns the result of casting `getValue(...)` to a subclass of `Value` + /// (using `cast_or_null<T>`). + /// This assert-fails if the result of `getValue(...)` is not of type `T *`; + /// if the value is not guaranteed to have type `T *`, consider using + /// `dyn_cast_or_null<T>(getValue(...))` instead. + template <typename T> + std::enable_if_t<std::is_base_of_v<Value, T>, T *> + get(const StorageLocation &Loc) const { + return cast_or_null<T>(getValue(Loc)); + } + template <typename T> + std::enable_if_t<std::is_base_of_v<Value, T>, T *> + get(const ValueDecl &D) const { + return cast_or_null<T>(getValue(D)); + } + template <typename T> + std::enable_if_t<std::is_base_of_v<Value, T>, T *> get(const Expr &E) const { + return cast_or_null<T>(getValue(E)); + } + + // FIXME: should we deprecate the following & call arena().create() directly? + + /// Creates a `T` (some subclass of `Value`), forwarding `args` to the + /// constructor, and returns a reference to it. + /// + /// The analysis context takes ownership of the created object. The object + /// will be destroyed when the analysis context is destroyed. + template <typename T, typename... Args> + std::enable_if_t<std::is_base_of<Value, T>::value, T &> + create(Args &&...args) { + return arena().create<T>(std::forward<Args>(args)...); + } + + /// Returns a symbolic integer value that models an integer literal equal to + /// `Value` + IntegerValue &getIntLiteralValue(llvm::APInt Value) const { + return arena().makeIntLiteral(Value); + } + + /// Returns a symbolic boolean value that models a boolean literal equal to + /// `Value` + BoolValue &getBoolLiteralValue(bool Value) const { + return arena().makeBoolValue(arena().makeLiteral(Value)); + } + + /// Returns an atomic boolean value. + BoolValue &makeAtomicBoolValue() const { + return arena().makeAtomValue(); + } + + /// Returns a unique instance of boolean Top. + BoolValue &makeTopBoolValue() const { + return arena().makeTopValue(); + } + + /// Returns a boolean value that represents the conjunction of `LHS` and + /// `RHS`. Subsequent calls with the same arguments, regardless of their + /// order, will return the same result. If the given boolean values represent + /// the same value, the result will be the value itself. + BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const { + return arena().makeBoolValue( + arena().makeAnd(LHS.formula(), RHS.formula())); + } + + /// Returns a boolean value that represents the disjunction of `LHS` and + /// `RHS`. Subsequent calls with the same arguments, regardless of their + /// order, will return the same result. If the given boolean values represent + /// the same value, the result will be the value itself. + BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const { + return arena().makeBoolValue( + arena().makeOr(LHS.formula(), RHS.formula())); + } + + /// Returns a boolean value that represents the negation of `Val`. Subsequent + /// calls with the same argument will return the same result. + BoolValue &makeNot(BoolValue &Val) const { + return arena().makeBoolValue(arena().makeNot(Val.formula())); + } + + /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with + /// the same arguments, will return the same result. If the given boolean + /// values represent the same value, the result will be a value that + /// represents the true boolean literal. + BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const { + return arena().makeBoolValue( + arena().makeImplies(LHS.formula(), RHS.formula())); + } + + /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with + /// the same arguments, regardless of their order, will return the same + /// result. If the given boolean values represent the same value, the result + /// will be a value that represents the true boolean literal. + BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const { + return arena().makeBoolValue( + arena().makeEquals(LHS.formula(), RHS.formula())); + } + + /// Returns a boolean variable that identifies the flow condition (FC). + /// + /// The flow condition is a set of facts that are necessarily true when the + /// program reaches the current point, expressed as boolean formulas. + /// The flow condition token is equivalent to the AND of these facts. + /// + /// These may e.g. constrain the value of certain variables. A pointer + /// variable may have a consistent modeled PointerValue throughout, but at a + /// given point the Environment may tell us that the value must be non-null. + /// + /// The FC is necessary but not sufficient for this point to be reachable. + /// In particular, where the FC token appears in flow conditions of successor + /// environments, it means "point X may have been reached", not + /// "point X was reached". + Atom getFlowConditionToken() const { return FlowConditionToken; } + + /// Record a fact that must be true if this point in the program is reached. + void assume(const Formula &); + + /// Returns true if the formula is always true when this point is reached. + /// Returns false if the formula may be false (or the flow condition isn't + /// sufficiently precise to prove that it is true) or if the solver times out. + /// + /// Note that there is an asymmetry between this function and `allows()` in + /// that they both return false if the solver times out. The assumption is + /// that if `proves()` or `allows()` returns true, this will result in a + /// diagnostic, and we want to bias towards false negatives in the case where + /// the solver times out. + bool proves(const Formula &) const; + + /// Returns true if the formula may be true when this point is reached. + /// Returns false if the formula is always false when this point is reached + /// (or the flow condition is overly constraining) or if the solver times out. + bool allows(const Formula &) const; + + /// Returns the `DeclContext` of the block being analysed, if any. Otherwise, + /// returns null. + const DeclContext *getDeclCtx() const { return CallStack.back(); } + + /// Returns the function currently being analyzed, or null if the code being + /// analyzed isn't part of a function. + const FunctionDecl *getCurrentFunc() const { + return dyn_cast<FunctionDecl>(getDeclCtx()); + } + + /// Returns the size of the call stack. + size_t callStackSize() const { return CallStack.size(); } + + /// Returns whether this `Environment` can be extended to analyze the given + /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a + /// given `MaxDepth`. + bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const; + + /// Returns the `DataflowAnalysisContext` used by the environment. + DataflowAnalysisContext &getDataflowAnalysisContext() const { return *DACtx; } + + Arena &arena() const { return DACtx->arena(); } + + LLVM_DUMP_METHOD void dump() const; + LLVM_DUMP_METHOD void dump(raw_ostream &OS) const; + +private: + // The copy-constructor is for use in fork() only. + Environment(const Environment &) = default; + + /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise + /// return null. + /// + /// 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 *createValueUnlessSelfReferential(QualType Type, + llvm::DenseSet<QualType> &Visited, + int Depth, int &CreatedValuesCount); + + /// Creates a storage location for `Ty`. Also creates and associates a value + /// with the storage location, unless values of this type are not supported or + /// we hit one of the limits at which we stop producing values (controlled by + /// `Visited`, `Depth`, and `CreatedValuesCount`). + StorageLocation &createLocAndMaybeValue(QualType Ty, + llvm::DenseSet<QualType> &Visited, + int Depth, int &CreatedValuesCount); + + /// Shared implementation of `createObject()` overloads. + /// `D` and `InitExpr` may be null. + StorageLocation &createObjectInternal(const ValueDecl *D, QualType Ty, + const Expr *InitExpr); + + /// Shared implementation of `pushCall` overloads. Note that unlike + /// `pushCall`, this member is invoked on the environment of the callee, not + /// of the caller. + void pushCallInternal(const FunctionDecl *FuncDecl, + ArrayRef<const Expr *> Args); + + /// Assigns storage locations and values to all global variables, fields + /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body. + void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl); + + // `DACtx` is not null and not owned by this object. + DataflowAnalysisContext *DACtx; + + // FIXME: move the fields `CallStack`, `ReturnVal`, `ReturnLoc` and + // `ThisPointeeLoc` into a separate call-context object, shared between + // environments in the same call. + // https://github.com/llvm/llvm-project/issues/59005 + + // `DeclContext` of the block being analysed if provided. + std::vector<const DeclContext *> CallStack; + + // Value returned by the function (if it has non-reference return type). + Value *ReturnVal = nullptr; + // Storage location of the reference returned by the function (if it has + // reference return type). + StorageLocation *ReturnLoc = nullptr; + // The storage location of the `this` pointee. Should only be null if the + // function being analyzed is only a function and not a method. + RecordStorageLocation *ThisPointeeLoc = nullptr; + + // Maps from declarations and glvalue expression 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<const ValueDecl *, StorageLocation *> DeclToLoc; + llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc; + // Maps from prvalue expressions and storage locations to the values that + // are assigned to them. + // We preserve insertion order so that join/widen process values in + // deterministic sequence. This in turn produces deterministic SAT formulas. + llvm::MapVector<const Expr *, Value *> ExprToVal; + llvm::MapVector<const StorageLocation *, Value *> LocToVal; + + Atom FlowConditionToken; +}; + +/// Returns the storage location for the implicit object of a +/// `CXXMemberCallExpr`, or null if none is defined in the environment. +/// Dereferences the pointer if the member call expression was written using +/// `->`. +RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, + const Environment &Env); + +/// Returns the storage location for the base object of a `MemberExpr`, or null +/// if none is defined in the environment. Dereferences the pointer if the +/// member expression was written using `->`. +RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, + const Environment &Env); + +/// Returns the fields of `RD` that are initialized by an `InitListExpr`, in the +/// order in which they appear in `InitListExpr::inits()`. +std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD); + +/// Associates a new `RecordValue` with `Loc` and returns the new value. +RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env); + +/// Associates a new `RecordValue` with `Expr` and returns the new value. +RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h new file mode 100644 index 000000000000..0c81e2f078c2 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowLattice.h @@ -0,0 +1,31 @@ +//===- DataflowLattice.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 base types for building lattices to be used in dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H + +namespace clang { +namespace dataflow { + +/// Effect indicating whether a lattice join operation resulted in a new value. +// FIXME: Rename to `LatticeEffect` since `widen` uses it as well, and we are +// likely removing it from `join`. +enum class LatticeJoinEffect { + Unchanged, + Changed, +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWLATTICE_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h index ab96cd5169a2..2248bcdf3a51 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowValues.h @@ -134,7 +134,7 @@ public: /// getBlockDataMap - Retrieves the internal map between CFGBlocks and /// dataflow values. If the dataflow analysis operates in the forward /// direction, the values correspond to the dataflow values at the start - /// of the block. Otherwise, for a backward analysis, the values correpsond + /// of the block. Otherwise, for a backward analysis, the values correspond /// to the dataflow values at the end of the block. BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h index 90095735ad3d..f1d05743bf7f 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h @@ -12,6 +12,7 @@ #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H +#include "clang/Analysis/Analyses/IntervalPartition.h" #include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/PriorityQueue.h" @@ -21,16 +22,13 @@ namespace clang { /// on the order defined by 'Comp'. template <typename Comp, unsigned QueueSize> class DataflowWorklistBase { llvm::BitVector EnqueuedBlocks; - PostOrderCFGView *POV; llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, QueueSize>, Comp> WorkList; public: - DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C) - : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {} - - const PostOrderCFGView *getCFGView() const { return POV; } + DataflowWorklistBase(const CFG &Cfg, Comp C) + : EnqueuedBlocks(Cfg.getNumBlockIDs()), WorkList(C) {} void enqueueBlock(const CFGBlock *Block) { if (Block && !EnqueuedBlocks[Block->getBlockID()]) { @@ -61,11 +59,25 @@ struct ReversePostOrderCompare { /// the same block multiple times at once. struct ForwardDataflowWorklist : DataflowWorklistBase<ReversePostOrderCompare, 20> { + ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV) + : DataflowWorklistBase(Cfg, + ReversePostOrderCompare{POV->getComparator()}) {} + ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) - : DataflowWorklistBase( - Cfg, Ctx.getAnalysis<PostOrderCFGView>(), - ReversePostOrderCompare{ - Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {} + : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {} + + void enqueueSuccessors(const CFGBlock *Block) { + for (auto B : Block->succs()) + enqueueBlock(B); + } +}; + +/// A worklist implementation for forward dataflow analysis based on a weak +/// topological ordering of the nodes. The worklist cannot contain the same +/// block multiple times at once. +struct WTODataflowWorklist : DataflowWorklistBase<WTOCompare, 20> { + WTODataflowWorklist(const CFG &Cfg, const WTOCompare &Cmp) + : DataflowWorklistBase(Cfg, Cmp) {} void enqueueSuccessors(const CFGBlock *Block) { for (auto B : Block->succs()) @@ -80,8 +92,7 @@ struct BackwardDataflowWorklist : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> { BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx) : DataflowWorklistBase( - Cfg, Ctx.getAnalysis<PostOrderCFGView>(), - Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {} + Cfg, Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {} void enqueuePredecessors(const CFGBlock *Block) { for (auto B : Block->preds()) @@ -91,4 +102,4 @@ struct BackwardDataflowWorklist } // namespace clang -#endif // LLVM_CLANG_ANALYSIS_ANALYSES_CONSUMED_H +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DebugSupport.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DebugSupport.h new file mode 100644 index 000000000000..6b9f3681490a --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/DebugSupport.h @@ -0,0 +1,36 @@ +//===-- DebugSupport.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 functions which generate more readable forms of data +// structures used in the dataflow analyses, for debugging purposes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DEBUGSUPPORT_H_ +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DEBUGSUPPORT_H_ + +#include <string> +#include <vector> + +#include "clang/Analysis/FlowSensitive/Solver.h" +#include "clang/Analysis/FlowSensitive/Value.h" +#include "llvm/ADT/StringRef.h" + +namespace clang { +namespace dataflow { + +/// Returns a string representation of a value kind. +llvm::StringRef debugString(Value::Kind Kind); + +/// Returns a string representation of the result status of a SAT check. +llvm::StringRef debugString(Solver::Result::Status Status); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DEBUGSUPPORT_H_ diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Formula.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Formula.h new file mode 100644 index 000000000000..0e6352403a83 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Formula.h @@ -0,0 +1,147 @@ +//===- Formula.h - Boolean formulas -----------------------------*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_FORMULA_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_FORMULA_H + +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/raw_ostream.h" +#include <cassert> +#include <string> + +namespace clang::dataflow { + +/// Identifies an atomic boolean variable such as "V1". +/// +/// This often represents an assertion that is interesting to the analysis but +/// cannot immediately be proven true or false. For example: +/// - V1 may mean "the program reaches this point", +/// - V2 may mean "the parameter was null" +/// +/// We can use these variables in formulas to describe relationships we know +/// to be true: "if the parameter was null, the program reaches this point". +/// We also express hypotheses as formulas, and use a SAT solver to check +/// whether they are consistent with the known facts. +enum class Atom : unsigned {}; + +/// A boolean expression such as "true" or "V1 & !V2". +/// Expressions may refer to boolean atomic variables. These should take a +/// consistent true/false value across the set of formulas being considered. +/// +/// (Formulas are always expressions in terms of boolean variables rather than +/// e.g. integers because our underlying model is SAT rather than e.g. SMT). +/// +/// Simple formulas such as "true" and "V1" are self-contained. +/// Compound formulas connect other formulas, e.g. "(V1 & V2) || V3" is an 'or' +/// formula, with pointers to its operands "(V1 & V2)" and "V3" stored as +/// trailing objects. +/// For this reason, Formulas are Arena-allocated and over-aligned. +class Formula; +class alignas(const Formula *) Formula { +public: + enum Kind : unsigned { + /// A reference to an atomic boolean variable. + /// We name these e.g. "V3", where 3 == atom identity == Value. + AtomRef, + /// Constant true or false. + Literal, + + Not, /// True if its only operand is false + + // These kinds connect two operands LHS and RHS + And, /// True if LHS and RHS are both true + Or, /// True if either LHS or RHS is true + Implies, /// True if LHS is false or RHS is true + Equal, /// True if LHS and RHS have the same truth value + }; + Kind kind() const { return FormulaKind; } + + Atom getAtom() const { + assert(kind() == AtomRef); + return static_cast<Atom>(Value); + } + + bool literal() const { + assert(kind() == Literal); + return static_cast<bool>(Value); + } + + bool isLiteral(bool b) const { + return kind() == Literal && static_cast<bool>(Value) == b; + } + + ArrayRef<const Formula *> operands() const { + return ArrayRef(reinterpret_cast<Formula *const *>(this + 1), + numOperands(kind())); + } + + using AtomNames = llvm::DenseMap<Atom, std::string>; + // Produce a stable human-readable representation of this formula. + // For example: (V3 | !(V1 & V2)) + // If AtomNames is provided, these override the default V0, V1... names. + void print(llvm::raw_ostream &OS, const AtomNames * = nullptr) const; + + // Allocate Formulas using Arena rather than calling this function directly. + static const Formula &create(llvm::BumpPtrAllocator &Alloc, Kind K, + ArrayRef<const Formula *> Operands, + unsigned Value = 0); + +private: + Formula() = default; + Formula(const Formula &) = delete; + Formula &operator=(const Formula &) = delete; + + static unsigned numOperands(Kind K) { + switch (K) { + case AtomRef: + case Literal: + return 0; + case Not: + return 1; + case And: + case Or: + case Implies: + case Equal: + return 2; + } + llvm_unreachable("Unhandled Formula::Kind enum"); + } + + Kind FormulaKind; + // Some kinds of formula have scalar values, e.g. AtomRef's atom number. + unsigned Value; +}; + +// The default names of atoms are V0, V1 etc in order of creation. +inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Atom A) { + return OS << 'V' << static_cast<unsigned>(A); +} +inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Formula &F) { + F.print(OS); + return OS; +} + +} // namespace clang::dataflow +namespace llvm { +template <> struct DenseMapInfo<clang::dataflow::Atom> { + using Atom = clang::dataflow::Atom; + using Underlying = std::underlying_type_t<Atom>; + + static inline Atom getEmptyKey() { return Atom(Underlying(-1)); } + static inline Atom getTombstoneKey() { return Atom(Underlying(-2)); } + static unsigned getHashValue(const Atom &Val) { + return DenseMapInfo<Underlying>::getHashValue(Underlying(Val)); + } + static bool isEqual(const Atom &LHS, const Atom &RHS) { return LHS == RHS; } +}; +} // namespace llvm +#endif diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Logger.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Logger.h new file mode 100644 index 000000000000..f4bd39f6ed49 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Logger.h @@ -0,0 +1,91 @@ +//===-- Logger.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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_LOGGER_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_LOGGER_H + +#include "clang/Analysis/CFG.h" +#include "llvm/Support/raw_ostream.h" +#include <memory> + +namespace clang::dataflow { +// Forward declarations so we can use Logger anywhere in the framework. +class ControlFlowContext; +class TypeErasedDataflowAnalysis; +struct TypeErasedDataflowAnalysisState; + +/// A logger is notified as the analysis progresses. +/// It can produce a report of the analysis's findings and how it came to them. +/// +/// The framework reports key structural events (e.g. traversal of blocks). +/// The specific analysis can add extra details to be presented in context. +class Logger { +public: + /// Returns a dummy logger that does nothing. + static Logger &null(); + /// A logger that simply writes messages to the specified ostream in real + /// time. + static std::unique_ptr<Logger> textual(llvm::raw_ostream &); + /// A logger that builds an HTML UI to inspect the analysis results. + /// Each function's analysis is written to a stream obtained from the factory. + static std::unique_ptr<Logger> + html(std::function<std::unique_ptr<llvm::raw_ostream>()>); + + virtual ~Logger() = default; + + /// Called by the framework as we start analyzing a new function or statement. + /// Forms a pair with endAnalysis(). + virtual void beginAnalysis(const ControlFlowContext &, + TypeErasedDataflowAnalysis &) {} + virtual void endAnalysis() {} + + // At any time during the analysis, we're computing the state for some target + // program point. + + /// Called when we start (re-)processing a block in the CFG. + /// The target program point is the entry to the specified block. + /// Calls to log() describe transferBranch(), join() etc. + /// `PostVisit` specifies whether we're processing the block for the + /// post-visit callback. + virtual void enterBlock(const CFGBlock &, bool PostVisit) {} + /// Called when we start processing an element in the current CFG block. + /// The target program point is after the specified element. + /// Calls to log() describe the transfer() function. + virtual void enterElement(const CFGElement &) {} + + /// Records the analysis state computed for the current program point. + virtual void recordState(TypeErasedDataflowAnalysisState &) {} + /// Records that the analysis state for the current block is now final. + virtual void blockConverged() {} + + /// Called by the framework or user code to report some event. + /// The event is associated with the current context (program point). + /// The Emit function produces the log message. It may or may not be called, + /// depending on if the logger is interested; it should have no side effects. + void log(llvm::function_ref<void(llvm::raw_ostream &)> Emit) { + if (!ShouldLogText) + return; + std::string S; + llvm::raw_string_ostream OS(S); + Emit(OS); + logText(S); + } + +protected: + /// ShouldLogText should be false for trivial loggers that ignore logText(). + /// This allows log() to skip evaluating its Emit function. + Logger(bool ShouldLogText = true) : ShouldLogText(ShouldLogText) {} + +private: + bool ShouldLogText; + virtual void logText(llvm::StringRef) {} +}; + +} // namespace clang::dataflow + +#endif diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MapLattice.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MapLattice.h new file mode 100644 index 000000000000..16b0c978779a --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MapLattice.h @@ -0,0 +1,143 @@ +//===------------------------ MapLattice.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 parameterized lattice that maps keys to individual +// lattice elements (of the parameter lattice type). A typical usage is lifting +// a particular lattice to all variables in a lexical scope. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H + +#include <ostream> +#include <string> +#include <utility> + +#include "DataflowAnalysis.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringRef.h" + +namespace clang { +namespace dataflow { + +/// A lattice that maps keys to individual lattice elements. When instantiated +/// with an `ElementLattice` that is a bounded semi-lattice, `MapLattice` is +/// itself a bounded semi-lattice, so long as the user limits themselves to a +/// finite number of keys. In that case, `top` is (implicitly), the map +/// containing all valid keys mapped to `top` of `ElementLattice`. +/// +/// Requirements on `ElementLattice`: +/// * Provides standard declarations of a bounded semi-lattice. +template <typename Key, typename ElementLattice> class MapLattice { + using Container = llvm::DenseMap<Key, ElementLattice>; + Container C; + +public: + using key_type = Key; + using mapped_type = ElementLattice; + using value_type = typename Container::value_type; + using iterator = typename Container::iterator; + using const_iterator = typename Container::const_iterator; + + MapLattice() = default; + + explicit MapLattice(Container C) { C = std::move(C); } + + // The `bottom` element is the empty map. + static MapLattice bottom() { return MapLattice(); } + + std::pair<iterator, bool> + insert(const std::pair<const key_type, mapped_type> &P) { + return C.insert(P); + } + + std::pair<iterator, bool> insert(std::pair<const key_type, mapped_type> &&P) { + return C.insert(std::move(P)); + } + + unsigned size() const { return C.size(); } + bool empty() const { return C.empty(); } + + iterator begin() { return C.begin(); } + iterator end() { return C.end(); } + const_iterator begin() const { return C.begin(); } + const_iterator end() const { return C.end(); } + + // Equality is direct equality of underlying map entries. One implication of + // this definition is that a map with (only) keys that map to bottom is not + // equal to the empty map. + friend bool operator==(const MapLattice &LHS, const MapLattice &RHS) { + return LHS.C == RHS.C; + } + + friend bool operator!=(const MapLattice &LHS, const MapLattice &RHS) { + return !(LHS == RHS); + } + + bool contains(const key_type &K) const { return C.find(K) != C.end(); } + + iterator find(const key_type &K) { return C.find(K); } + const_iterator find(const key_type &K) const { return C.find(K); } + + mapped_type &operator[](const key_type &K) { return C[K]; } + + /// If an entry exists in one map but not the other, the missing entry is + /// treated as implicitly mapping to `bottom`. So, the joined map contains the + /// entry as it was in the source map. + LatticeJoinEffect join(const MapLattice &Other) { + LatticeJoinEffect Effect = LatticeJoinEffect::Unchanged; + for (const auto &O : Other.C) { + auto It = C.find(O.first); + if (It == C.end()) { + C.insert(O); + Effect = LatticeJoinEffect::Changed; + } else if (It->second.join(O.second) == LatticeJoinEffect::Changed) + Effect = LatticeJoinEffect::Changed; + } + return Effect; + } +}; + +/// Convenience alias that captures the common use of map lattices to model +/// in-scope variables. +template <typename ElementLattice> +using VarMapLattice = MapLattice<const clang::VarDecl *, ElementLattice>; + +template <typename Key, typename ElementLattice> +std::ostream & +operator<<(std::ostream &Os, + const clang::dataflow::MapLattice<Key, ElementLattice> &M) { + std::string Separator; + Os << "{"; + for (const auto &E : M) { + Os << std::exchange(Separator, ", ") << E.first << " => " << E.second; + } + Os << "}"; + return Os; +} + +template <typename ElementLattice> +std::ostream & +operator<<(std::ostream &Os, + const clang::dataflow::VarMapLattice<ElementLattice> &M) { + std::string Separator; + Os << "{"; + for (const auto &E : M) { + Os << std::exchange(Separator, ", ") << E.first->getName().str() << " => " + << E.second; + } + Os << "}"; + return Os; +} +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__MAPLATTICE_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h new file mode 100644 index 000000000000..085308f7db54 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h @@ -0,0 +1,174 @@ +//===---- MatchSwitch.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 the `ASTMatchSwitch` abstraction for building a "switch" +// statement, where each case of the switch is defined by an AST matcher. The +// cases are considered in order, like pattern matching in functional +// languages. +// +// Currently, the design is catered towards simplifying the implementation of +// `DataflowAnalysis` transfer functions. Based on experience here, this +// library may be generalized and moved to ASTMatchers. +// +//===----------------------------------------------------------------------===// +// +// FIXME: Rename to ASTMatchSwitch.h + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "llvm/ADT/StringRef.h" +#include <functional> +#include <string> +#include <type_traits> +#include <utility> +#include <vector> + +namespace clang { +namespace dataflow { + +/// A common form of state shared between the cases of a transfer function. +template <typename LatticeT> struct TransferState { + TransferState(LatticeT &Lattice, Environment &Env) + : Lattice(Lattice), Env(Env) {} + + /// Current lattice element. + LatticeT &Lattice; + Environment &Env; +}; + +/// A read-only version of TransferState. +/// +/// FIXME: this type is being used as a general (typed) view type for untyped +/// dataflow analysis state, rather than strictly for transfer-function +/// purposes. Move it (and rename it) to DataflowAnalysis.h. +template <typename LatticeT> struct TransferStateForDiagnostics { + TransferStateForDiagnostics(const LatticeT &Lattice, const Environment &Env) + : Lattice(Lattice), Env(Env) {} + + /// Current lattice element. + const LatticeT &Lattice; + const Environment &Env; +}; + +template <typename T> +using MatchSwitchMatcher = ast_matchers::internal::Matcher<T>; + +template <typename T, typename State, typename Result = void> +using MatchSwitchAction = std::function<Result( + const T *, const ast_matchers::MatchFinder::MatchResult &, State &)>; + +template <typename BaseT, typename State, typename Result = void> +using ASTMatchSwitch = + std::function<Result(const BaseT &, ASTContext &, State &)>; + +/// Collects cases of a "match switch": a collection of matchers paired with +/// callbacks, which together define a switch that can be applied to a node +/// whose type derives from `BaseT`. This structure can simplify the definition +/// of `transfer` functions that rely on pattern-matching. +/// +/// For example, consider an analysis that handles particular function calls. It +/// can define the `ASTMatchSwitch` once, in the constructor of the analysis, +/// and then reuse it each time that `transfer` is called, with a fresh state +/// value. +/// +/// \code +/// ASTMatchSwitch<Stmt, TransferState<MyLattice> BuildSwitch() { +/// return ASTMatchSwitchBuilder<TransferState<MyLattice>>() +/// .CaseOf(callExpr(callee(functionDecl(hasName("foo")))), TransferFooCall) +/// .CaseOf(callExpr(argumentCountIs(2), +/// callee(functionDecl(hasName("bar")))), +/// TransferBarCall) +/// .Build(); +/// } +/// \endcode +template <typename BaseT, typename State, typename Result = void> +class ASTMatchSwitchBuilder { +public: + /// Registers an action that will be triggered by the match of a pattern + /// against the input statement. + /// + /// Requirements: + /// + /// `NodeT` should be derived from `BaseT`. + template <typename NodeT> + ASTMatchSwitchBuilder &&CaseOf(MatchSwitchMatcher<BaseT> M, + MatchSwitchAction<NodeT, State, Result> A) && { + static_assert(std::is_base_of<BaseT, NodeT>::value, + "NodeT must be derived from BaseT."); + Matchers.push_back(std::move(M)); + Actions.push_back( + [A = std::move(A)](const BaseT *Node, + const ast_matchers::MatchFinder::MatchResult &R, + State &S) { return A(cast<NodeT>(Node), R, S); }); + return std::move(*this); + } + + ASTMatchSwitch<BaseT, State, Result> Build() && { + return [Matcher = BuildMatcher(), Actions = std::move(Actions)]( + const BaseT &Node, ASTContext &Context, State &S) -> Result { + auto Results = ast_matchers::matchDynamic(Matcher, Node, Context); + if (Results.empty()) { + return Result(); + } + // Look through the map for the first binding of the form "TagN..." use + // that to select the action. + for (const auto &Element : Results[0].getMap()) { + llvm::StringRef ID(Element.first); + size_t Index = 0; + if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) && + Index < Actions.size()) { + return Actions[Index]( + &Node, + ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S); + } + } + return Result(); + }; + } + +private: + ast_matchers::internal::DynTypedMatcher BuildMatcher() { + using ast_matchers::anything; + using ast_matchers::stmt; + using ast_matchers::unless; + using ast_matchers::internal::DynTypedMatcher; + if (Matchers.empty()) + return stmt(unless(anything())); + for (int I = 0, N = Matchers.size(); I < N; ++I) { + std::string Tag = ("Tag" + llvm::Twine(I)).str(); + // Many matchers are not bindable, so ensure that tryBind will work. + Matchers[I].setAllowBind(true); + auto M = *Matchers[I].tryBind(Tag); + // Each anyOf explicitly controls the traversal kind. The anyOf itself is + // set to `TK_AsIs` to ensure no nodes are skipped, thereby deferring to + // the kind of the branches. Then, each branch is either left as is, if + // the kind is already set, or explicitly set to `TK_AsIs`. We choose this + // setting because it is the default interpretation of matchers. + Matchers[I] = + !M.getTraversalKind() ? M.withTraversalKind(TK_AsIs) : std::move(M); + } + // The matcher type on the cases ensures that `Expr` kind is compatible with + // all of the matchers. + return DynTypedMatcher::constructVariadic( + DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<BaseT>(), + std::move(Matchers)); + } + + std::vector<ast_matchers::internal::DynTypedMatcher> Matchers; + std::vector<MatchSwitchAction<BaseT, State, Result>> Actions; +}; + +} // namespace dataflow +} // namespace clang +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_ diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h new file mode 100644 index 000000000000..b4315e41d79f --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/ChromiumCheckModel.h @@ -0,0 +1,38 @@ +//===-- ChromiumCheckModel.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 dataflow model for Chromium's family of CHECK functions. +// +//===----------------------------------------------------------------------===// +#ifndef CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H +#define CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H + +#include "clang/AST/DeclCXX.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "llvm/ADT/DenseSet.h" + +namespace clang { +namespace dataflow { + +/// Models the behavior of Chromium's CHECK, DCHECK, etc. macros, so that code +/// after a call to `*CHECK` can rely on the condition being true. +class ChromiumCheckModel : public DataflowModel { +public: + ChromiumCheckModel() = default; + bool transfer(const CFGElement &Element, Environment &Env) override; + +private: + /// Declarations for `::logging::CheckError::.*Check`, lazily initialized. + llvm::SmallDenseSet<const CXXMethodDecl *> CheckDecls; +}; + +} // namespace dataflow +} // namespace clang + +#endif // CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_CHROMIUMCHECKMODEL_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h new file mode 100644 index 000000000000..09eb8b938226 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.h @@ -0,0 +1,80 @@ +//===-- UncheckedOptionalAccessModel.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 dataflow analysis that detects unsafe uses of optional +// values. +// +//===----------------------------------------------------------------------===// + +#ifndef CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_UNCHECKEDOPTIONALACCESSMODEL_H +#define CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_UNCHECKEDOPTIONALACCESSMODEL_H + +#include "clang/AST/ASTContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/CFGMatchSwitch.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/NoopLattice.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/ADT/SmallVector.h" + +namespace clang { +namespace dataflow { + +// FIXME: Explore using an allowlist-approach, where constructs supported by the +// analysis are always enabled and additional constructs are enabled through the +// `Options`. +struct UncheckedOptionalAccessModelOptions { + /// In generating diagnostics, ignore optionals reachable through overloaded + /// `operator*` or `operator->` (other than those of the optional type + /// itself). The analysis does not equate the results of such calls, so it + /// can't identify when their results are used safely (across calls), + /// resulting in false positives in all such cases. Note: this option does not + /// cover access through `operator[]`. + bool IgnoreSmartPointerDereference = false; +}; + +/// Dataflow analysis that models whether optionals hold values or not. +/// +/// Models the `std::optional`, `absl::optional`, and `base::Optional` types. +class UncheckedOptionalAccessModel + : public DataflowAnalysis<UncheckedOptionalAccessModel, NoopLattice> { +public: + UncheckedOptionalAccessModel(ASTContext &Ctx, dataflow::Environment &Env); + + /// Returns a matcher for the optional classes covered by this model. + static ast_matchers::DeclarationMatcher optionalClassDecl(); + + static NoopLattice initialElement() { return {}; } + + void transfer(const CFGElement &Elt, NoopLattice &L, Environment &Env); + +private: + CFGMatchSwitch<TransferState<NoopLattice>> TransferMatchSwitch; +}; + +class UncheckedOptionalAccessDiagnoser { +public: + UncheckedOptionalAccessDiagnoser( + UncheckedOptionalAccessModelOptions Options = {}); + + llvm::SmallVector<SourceLocation> + operator()(const CFGElement &Elt, ASTContext &Ctx, + const TransferStateForDiagnostics<NoopLattice> &State) { + return DiagnoseMatchSwitch(Elt, Ctx, State.Env); + } + +private: + CFGMatchSwitch<const Environment, llvm::SmallVector<SourceLocation>> + DiagnoseMatchSwitch; +}; + +} // namespace dataflow +} // namespace clang + +#endif // CLANG_ANALYSIS_FLOWSENSITIVE_MODELS_UNCHECKEDOPTIONALACCESSMODEL_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h new file mode 100644 index 000000000000..393f68300cb8 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopAnalysis.h @@ -0,0 +1,41 @@ +//===-- 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 just uses the builtin transfer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H + +#include "clang/AST/ASTContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/NoopLattice.h" + +namespace clang { +namespace dataflow { + +class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> { +public: + NoopAnalysis(ASTContext &Context) + : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {} + + NoopAnalysis(ASTContext &Context, DataflowAnalysisOptions Options) + : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context, Options) {} + + static NoopLattice initialElement() { return {}; } + + void transfer(const CFGElement &E, NoopLattice &L, Environment &Env) {} +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h new file mode 100644 index 000000000000..019219328111 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/NoopLattice.h @@ -0,0 +1,41 @@ +//===-- NoopLattice.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 the lattice with exactly one element. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOP_LATTICE_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOP_LATTICE_H + +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include <ostream> + +namespace clang { +namespace dataflow { + +/// Trivial lattice for dataflow analysis with exactly one element. +/// +/// Useful for analyses that only need the Environment and nothing more. +class NoopLattice { +public: + bool operator==(const NoopLattice &Other) const { return true; } + + LatticeJoinEffect join(const NoopLattice &Other) { + return LatticeJoinEffect::Unchanged; + } +}; + +inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) { + return OS << "noop"; +} + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_NOOP_LATTICE_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/RecordOps.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/RecordOps.h new file mode 100644 index 000000000000..783e53e980aa --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/RecordOps.h @@ -0,0 +1,68 @@ +//===-- RecordOps.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 records (structs, classes, and unions). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_RECORDOPS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_RECORDOPS_H + +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" + +namespace clang { +namespace dataflow { + +/// Copies a record (struct, class, or union) from `Src` to `Dst`. +/// +/// This performs a deep copy, i.e. it copies every field (including synthetic +/// fields) and recurses on fields of record type. +/// +/// If there is a `RecordValue` associated with `Dst` in the environment, this +/// function creates a new `RecordValue` and associates it with `Dst`; clients +/// need to be aware of this and must not assume that the `RecordValue` +/// associated with `Dst` remains the same after the call. +/// +/// Requirements: +/// +/// `Src` and `Dst` must have the same canonical unqualified type. +void copyRecord(RecordStorageLocation &Src, RecordStorageLocation &Dst, + Environment &Env); + +/// Returns whether the records `Loc1` and `Loc2` are equal. +/// +/// Values for `Loc1` are retrieved from `Env1`, and values for `Loc2` are +/// retrieved from `Env2`. A convenience overload retrieves values for `Loc1` +/// and `Loc2` from the same environment. +/// +/// This performs a deep comparison, i.e. it compares every field (including +/// synthetic fields) and recurses on fields of record type. Fields of reference +/// type compare equal if they refer to the same storage location. +/// +/// Note on how to interpret the result: +/// - If this returns true, the records are guaranteed to be equal at runtime. +/// - If this returns false, the records may still be equal at runtime; our +/// analysis merely cannot guarantee that they will be equal. +/// +/// Requirements: +/// +/// `Src` and `Dst` must have the same canonical unqualified type. +bool recordsEqual(const RecordStorageLocation &Loc1, const Environment &Env1, + const RecordStorageLocation &Loc2, const Environment &Env2); + +inline bool recordsEqual(const RecordStorageLocation &Loc1, + const RecordStorageLocation &Loc2, + const Environment &Env) { + return recordsEqual(Loc1, Env, Loc2, Env); +} + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_RECORDOPS_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/SimplifyConstraints.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/SimplifyConstraints.h new file mode 100644 index 000000000000..fadb3caf0a4c --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/SimplifyConstraints.h @@ -0,0 +1,49 @@ +//===-- SimplifyConstraints.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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SIMPLIFYCONSTRAINTS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SIMPLIFYCONSTRAINTS_H + +#include "clang/Analysis/FlowSensitive/Arena.h" +#include "clang/Analysis/FlowSensitive/Formula.h" +#include "llvm/ADT/SetVector.h" + +namespace clang { +namespace dataflow { + +/// Information on the way a set of constraints was simplified. +struct SimplifyConstraintsInfo { + /// List of equivalence classes of atoms. For each equivalence class, the + /// original constraints imply that all atoms in it must be equivalent. + /// Simplification replaces all occurrences of atoms in an equivalence class + /// with a single representative atom from the class. + /// Does not contain equivalence classes with just one member or atoms + /// contained in `TrueAtoms` or `FalseAtoms`. + llvm::SmallVector<llvm::SmallVector<Atom>> EquivalentAtoms; + /// Atoms that the original constraints imply must be true. + /// Simplification replaces all occurrences of these atoms by a true literal + /// (which may enable additional simplifications). + llvm::SmallVector<Atom> TrueAtoms; + /// Atoms that the original constraints imply must be false. + /// Simplification replaces all occurrences of these atoms by a false literal + /// (which may enable additional simplifications). + llvm::SmallVector<Atom> FalseAtoms; +}; + +/// Simplifies a set of constraints (implicitly connected by "and") in a way +/// that does not change satisfiability of the constraints. This does _not_ mean +/// that the set of solutions is the same before and after simplification. +/// `Info`, if non-null, will be populated with information about the +/// simplifications that were made to the formula (e.g. to display to the user). +void simplifyConstraints(llvm::SetVector<const Formula *> &Constraints, + Arena &arena, SimplifyConstraintsInfo *Info = nullptr); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SIMPLIFYCONSTRAINTS_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Solver.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Solver.h new file mode 100644 index 000000000000..079f6802f241 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Solver.h @@ -0,0 +1,98 @@ +//===- Solver.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 an interface for a SAT solver that can be used by +// dataflow analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOLVER_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOLVER_H + +#include "clang/Analysis/FlowSensitive/Formula.h" +#include "clang/Basic/LLVM.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/DenseMap.h" +#include <optional> +#include <vector> + +namespace clang { +namespace dataflow { + +/// An interface for a SAT solver that can be used by dataflow analyses. +class Solver { +public: + struct Result { + enum class Status { + /// Indicates that there exists a satisfying assignment for a boolean + /// formula. + Satisfiable, + + /// Indicates that there is no satisfying assignment for a boolean + /// formula. + Unsatisfiable, + + /// Indicates that the solver gave up trying to find a satisfying + /// assignment for a boolean formula. + TimedOut, + }; + + /// A boolean value is set to true or false in a truth assignment. + enum class Assignment : uint8_t { AssignedFalse = 0, AssignedTrue = 1 }; + + /// Constructs a result indicating that the queried boolean formula is + /// satisfiable. The result will hold a solution found by the solver. + static Result Satisfiable(llvm::DenseMap<Atom, Assignment> Solution) { + return Result(Status::Satisfiable, std::move(Solution)); + } + + /// Constructs a result indicating that the queried boolean formula is + /// unsatisfiable. + static Result Unsatisfiable() { return Result(Status::Unsatisfiable, {}); } + + /// Constructs a result indicating that satisfiability checking on the + /// queried boolean formula was not completed. + static Result TimedOut() { return Result(Status::TimedOut, {}); } + + /// Returns the status of satisfiability checking on the queried boolean + /// formula. + Status getStatus() const { return SATCheckStatus; } + + /// Returns a truth assignment to boolean values that satisfies the queried + /// boolean formula if available. Otherwise, an empty optional is returned. + std::optional<llvm::DenseMap<Atom, Assignment>> getSolution() const { + return Solution; + } + + private: + Result(Status SATCheckStatus, + std::optional<llvm::DenseMap<Atom, Assignment>> Solution) + : SATCheckStatus(SATCheckStatus), Solution(std::move(Solution)) {} + + Status SATCheckStatus; + std::optional<llvm::DenseMap<Atom, Assignment>> Solution; + }; + + virtual ~Solver() = default; + + /// Checks if the conjunction of `Vals` is satisfiable and returns the + /// corresponding result. + /// + /// Requirements: + /// + /// All elements in `Vals` must not be null. + virtual Result solve(llvm::ArrayRef<const Formula *> Vals) = 0; +}; + +llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Solver::Result &); +llvm::raw_ostream &operator<<(llvm::raw_ostream &, Solver::Result::Assignment); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_SOLVER_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h new file mode 100644 index 000000000000..8fcc6a44027a --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/StorageLocation.h @@ -0,0 +1,181 @@ +//===-- 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" +#include "llvm/Support/Debug.h" +#include <cassert> + +#define DEBUG_TYPE "dataflow" + +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, + Record, + }; + + StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) { + assert(Type.isNull() || !Type->isReferenceType()); + } + + // Non-copyable because addresses of storage locations are used as their + // identities throughout framework and user code. The framework is responsible + // for construction and destruction of storage locations. + StorageLocation(const StorageLocation &) = delete; + StorageLocation &operator=(const StorageLocation &) = delete; + + 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 for a record (struct, class, or union). +/// +/// Contains storage locations for all modeled fields of the record (also +/// referred to as "children"). The child map is flat, so accessible members of +/// the base class are directly accessible as children of this location. +/// +/// Record storage locations may also contain so-called synthetic fields. These +/// are typically used to model the internal state of a class (e.g. the value +/// stored in a `std::optional`) without having to depend on that class's +/// implementation details. All `RecordStorageLocation`s of a given type should +/// have the same synthetic fields. +/// +/// The storage location for a field of reference type may be null. This +/// typically occurs in one of two situations: +/// - The record has not been fully initialized. +/// - The maximum depth for modelling a self-referential data structure has been +/// reached. +/// Storage locations for fields of all other types must be non-null. +/// +/// FIXME: Currently, the storage location of unions is modelled the same way as +/// that of structs or classes. Eventually, we need to change this modelling so +/// that all of the members of a given union have the same storage location. +class RecordStorageLocation final : public StorageLocation { +public: + using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>; + using SyntheticFieldMap = llvm::StringMap<StorageLocation *>; + + RecordStorageLocation(QualType Type, FieldToLoc TheChildren, + SyntheticFieldMap TheSyntheticFields) + : StorageLocation(Kind::Record, Type), Children(std::move(TheChildren)), + SyntheticFields(std::move(TheSyntheticFields)) { + assert(!Type.isNull()); + assert(Type->isRecordType()); + assert([this] { + for (auto [Field, Loc] : Children) { + if (!Field->getType()->isReferenceType() && Loc == nullptr) + return false; + } + return true; + }()); + } + + static bool classof(const StorageLocation *Loc) { + return Loc->getKind() == Kind::Record; + } + + /// Returns the child storage location for `D`. + /// + /// May return null if `D` has reference type; guaranteed to return non-null + /// in all other cases. + /// + /// Note that it is an error to call this with a field that does not exist. + /// The function does not return null in this case. + StorageLocation *getChild(const ValueDecl &D) const { + auto It = Children.find(&D); + LLVM_DEBUG({ + if (It == Children.end()) { + llvm::dbgs() << "Couldn't find child " << D.getNameAsString() + << " on StorageLocation " << this << " of type " + << getType() << "\n"; + llvm::dbgs() << "Existing children:\n"; + for ([[maybe_unused]] auto [Field, Loc] : Children) { + llvm::dbgs() << Field->getNameAsString() << "\n"; + } + } + }); + assert(It != Children.end()); + return It->second; + } + + /// Returns the storage location for the synthetic field `Name`. + /// The synthetic field must exist. + StorageLocation &getSyntheticField(llvm::StringRef Name) const { + StorageLocation *Loc = SyntheticFields.lookup(Name); + assert(Loc != nullptr); + return *Loc; + } + + llvm::iterator_range<SyntheticFieldMap::const_iterator> + synthetic_fields() const { + return {SyntheticFields.begin(), SyntheticFields.end()}; + } + + /// Changes the child storage location for a field `D` of reference type. + /// All other fields cannot change their storage location and always retain + /// the storage location passed to the `RecordStorageLocation` constructor. + /// + /// Requirements: + /// + /// `D` must have reference type. + void setChild(const ValueDecl &D, StorageLocation *Loc) { + assert(D.getType()->isReferenceType()); + Children[&D] = Loc; + } + + llvm::iterator_range<FieldToLoc::const_iterator> children() const { + return {Children.begin(), Children.end()}; + } + +private: + FieldToLoc Children; + SyntheticFieldMap SyntheticFields; +}; + +} // namespace dataflow +} // namespace clang + +#undef DEBUG_TYPE + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Transfer.h new file mode 100644 index 000000000000..7713df747cb7 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -0,0 +1,61 @@ +//===-- 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/DataflowAnalysisContext.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" + +namespace clang { +namespace dataflow { + +/// Maps statements to the environments of basic blocks that contain them. +class StmtToEnvMap { +public: + // `CurBlockID` is the ID of the block currently being processed, and + // `CurState` is the pending state currently associated with this block. These + // are supplied separately as the pending state for the current block may not + // yet be represented in `BlockToState`. + StmtToEnvMap(const ControlFlowContext &CFCtx, + llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> + BlockToState, + unsigned CurBlockID, + const TypeErasedDataflowAnalysisState &CurState) + : CFCtx(CFCtx), BlockToState(BlockToState), CurBlockID(CurBlockID), + CurState(CurState) {} + + /// Returns the environment of the basic block that contains `S`. + /// The result is guaranteed never to be null. + const Environment *getEnvironment(const Stmt &S) const; + +private: + const ControlFlowContext &CFCtx; + llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockToState; + unsigned CurBlockID; + const TypeErasedDataflowAnalysisState &CurState; +}; + +/// Evaluates `S` and updates `Env` accordingly. +/// +/// Requirements: +/// +/// `S` must not be `ParenExpr` or `ExprWithCleanups`. +void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h new file mode 100644 index 000000000000..a0ca7440230b --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h @@ -0,0 +1,159 @@ +//===- TypeErasedDataflowAnalysis.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 type-erased base types and functions for building dataflow +// analyses that run over Control-Flow Graphs (CFGs). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H + +#include <optional> +#include <utility> +#include <vector> + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Stmt.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/FlowSensitive/ControlFlowContext.h" +#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" +#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" +#include "clang/Analysis/FlowSensitive/DataflowLattice.h" +#include "llvm/ADT/Any.h" +#include "llvm/Support/Error.h" + +namespace clang { +namespace dataflow { + +struct DataflowAnalysisOptions { + /// Options for the built-in model, or empty to not apply them. + // FIXME: Remove this option once the framework supports composing analyses + // (at which point the built-in transfer functions can be simply a standalone + // analysis). + std::optional<DataflowAnalysisContext::Options> BuiltinOpts = + DataflowAnalysisContext::Options{}; +}; + +/// Type-erased lattice element container. +/// +/// Requirements: +/// +/// The type of the object stored in the container must be a bounded +/// join-semilattice. +struct TypeErasedLattice { + llvm::Any Value; +}; + +/// Type-erased base class for dataflow analyses built on a single lattice type. +class TypeErasedDataflowAnalysis : public Environment::ValueModel { + DataflowAnalysisOptions Options; + +public: + TypeErasedDataflowAnalysis() : Options({}) {} + + TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options) + : Options(Options) {} + + virtual ~TypeErasedDataflowAnalysis() {} + + /// Returns the `ASTContext` that is used by the analysis. + virtual ASTContext &getASTContext() = 0; + + /// Returns a type-erased lattice element that models the initial state of a + /// basic block. + virtual TypeErasedLattice typeErasedInitialElement() = 0; + + /// Joins two type-erased lattice elements by computing their least upper + /// bound. Places the join result in the left element and returns an effect + /// indicating whether any changes were made to it. + virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &, + const TypeErasedLattice &) = 0; + + /// Chooses a lattice element that approximates the current element at a + /// program point, given the previous element at that point. Places the + /// widened result in the current element (`Current`). Widening is optional -- + /// it is only needed to either accelerate convergence (for lattices with + /// non-trivial height) or guarantee convergence (for lattices with infinite + /// height). + /// + /// Returns an indication of whether any changes were made to `Current` in + /// order to widen. This saves a separate call to `isEqualTypeErased` after + /// the widening. + virtual LatticeJoinEffect + widenTypeErased(TypeErasedLattice &Current, + const TypeErasedLattice &Previous) = 0; + + /// Returns true if and only if the two given type-erased lattice elements are + /// equal. + virtual bool isEqualTypeErased(const TypeErasedLattice &, + const TypeErasedLattice &) = 0; + + /// Applies the analysis transfer function for a given control flow graph + /// element and type-erased lattice element. + virtual void transferTypeErased(const CFGElement &, TypeErasedLattice &, + Environment &) = 0; + + /// Applies the analysis transfer function for a given edge from a CFG block + /// of a conditional statement. + /// @param Stmt The condition which is responsible for the split in the CFG. + /// @param Branch True if the edge goes to the basic block where the + /// condition is true. + // FIXME: Change `Stmt` argument to a reference. + virtual void transferBranchTypeErased(bool Branch, const Stmt *, + TypeErasedLattice &, Environment &) = 0; + + /// If the built-in model is enabled, returns the options to be passed to + /// them. Otherwise returns empty. + const std::optional<DataflowAnalysisContext::Options> & + builtinOptions() const { + return Options.BuiltinOpts; + } +}; + +/// Type-erased model of the program at a given program point. +struct TypeErasedDataflowAnalysisState { + /// Type-erased model of a program property. + TypeErasedLattice Lattice; + + /// 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)) {} + + TypeErasedDataflowAnalysisState fork() const { + return TypeErasedDataflowAnalysisState(Lattice, Env.fork()); + } +}; + +/// Performs dataflow analysis and returns a mapping from basic block IDs to +/// dataflow analysis states that model the respective basic blocks. Indices of +/// the returned vector correspond to basic block IDs. Returns an error if the +/// dataflow analysis cannot be performed successfully. Otherwise, calls +/// `PostVisitCFG` on each CFG element with the final analysis results at that +/// program point. +/// +/// `MaxBlockVisits` caps the number of block visits during analysis. It doesn't +/// distinguish between repeat visits to the same block and visits to distinct +/// blocks. This parameter is a backstop to prevent infinite loops, in the case +/// of bugs in the lattice and/or transfer functions that prevent the analysis +/// from converging. +llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> +runTypeErasedDataflowAnalysis( + const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, + const Environment &InitEnv, + std::function<void(const CFGElement &, + const TypeErasedDataflowAnalysisState &)> + PostVisitCFG, + std::int32_t MaxBlockVisits); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Value.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Value.h new file mode 100644 index 000000000000..be1bf9324c87 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Value.h @@ -0,0 +1,231 @@ +//===-- 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/Formula.h" +#include "clang/Analysis/FlowSensitive/StorageLocation.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringRef.h" +#include <cassert> +#include <utility> + +namespace clang { +namespace dataflow { + +/// Base class for all values computed by abstract interpretation. +/// +/// Don't use `Value` instances by value. All `Value` instances are allocated +/// and owned by `DataflowAnalysisContext`. +class Value { +public: + enum class Kind { + Integer, + Pointer, + Record, + + // TODO: Top values should not be need to be type-specific. + TopBool, + AtomicBool, + FormulaBool, + }; + + explicit Value(Kind ValKind) : ValKind(ValKind) {} + + // Non-copyable because addresses of values are used as their identities + // throughout framework and user code. The framework is responsible for + // construction and destruction of values. + Value(const Value &) = delete; + Value &operator=(const Value &) = delete; + + virtual ~Value() = default; + + Kind getKind() const { return ValKind; } + + /// Returns the value of the synthetic property with the given `Name` or null + /// if the property isn't assigned a value. + Value *getProperty(llvm::StringRef Name) const { + return Properties.lookup(Name); + } + + /// Assigns `Val` as the value of the synthetic property with the given + /// `Name`. + /// + /// Properties may not be set on `RecordValue`s; use synthetic fields instead + /// (for details, see documentation for `RecordStorageLocation`). + void setProperty(llvm::StringRef Name, Value &Val) { + assert(getKind() != Kind::Record); + Properties.insert_or_assign(Name, &Val); + } + + llvm::iterator_range<llvm::StringMap<Value *>::const_iterator> + properties() const { + return {Properties.begin(), Properties.end()}; + } + +private: + Kind ValKind; + llvm::StringMap<Value *> Properties; +}; + +/// An equivalence relation for values. It obeys reflexivity, symmetry and +/// transitivity. It does *not* include comparison of `Properties`. +/// +/// Computes equivalence for these subclasses: +/// * PointerValue -- pointee locations are equal. Does not compute deep +/// equality of `Value` at said location. +/// * TopBoolValue -- both are `TopBoolValue`s. +/// +/// Otherwise, falls back to pointer equality. +bool areEquivalentValues(const Value &Val1, const Value &Val2); + +/// Models a boolean. +class BoolValue : public Value { + const Formula *F; + +public: + explicit BoolValue(Kind ValueKind, const Formula &F) + : Value(ValueKind), F(&F) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::TopBool || + Val->getKind() == Kind::AtomicBool || + Val->getKind() == Kind::FormulaBool; + } + + const Formula &formula() const { return *F; } +}; + +/// A TopBoolValue represents a boolean that is explicitly unconstrained. +/// +/// This is equivalent to an AtomicBoolValue that does not appear anywhere +/// else in a system of formula. +/// Knowing the value is unconstrained is useful when e.g. reasoning about +/// convergence. +class TopBoolValue final : public BoolValue { +public: + TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) { + assert(F.kind() == Formula::AtomRef); + } + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::TopBool; + } + + Atom getAtom() const { return formula().getAtom(); } +}; + +/// Models an atomic boolean. +/// +/// FIXME: Merge this class into FormulaBoolValue. +/// When we want to specify atom identity, use Atom. +class AtomicBoolValue final : public BoolValue { +public: + explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) { + assert(F.kind() == Formula::AtomRef); + } + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::AtomicBool; + } + + Atom getAtom() const { return formula().getAtom(); } +}; + +/// Models a compound boolean formula. +class FormulaBoolValue final : public BoolValue { +public: + explicit FormulaBoolValue(const Formula &F) + : BoolValue(Kind::FormulaBool, F) { + assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue"); + } + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::FormulaBool; + } +}; + +/// Models an integer. +class IntegerValue : public Value { +public: + explicit IntegerValue() : Value(Kind::Integer) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Integer; + } +}; + +/// Models a symbolic pointer. Specifically, any value of type `T*`. +class PointerValue final : public Value { +public: + explicit PointerValue(StorageLocation &PointeeLoc) + : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Pointer; + } + + StorageLocation &getPointeeLoc() const { return PointeeLoc; } + +private: + StorageLocation &PointeeLoc; +}; + +/// Models a value of `struct` or `class` type. +/// In C++, prvalues of class type serve only a limited purpose: They can only +/// be used to initialize a result object. It is not possible to access member +/// variables or call member functions on a prvalue of class type. +/// Correspondingly, `RecordValue` also serves only a limited purpose: It +/// conveys a prvalue of class type from the place where the object is +/// constructed to the result object that it initializes. +/// +/// When creating a prvalue of class type, we already need a storage location +/// for `this`, even though prvalues are otherwise not associated with storage +/// locations. `RecordValue` is therefore essentially a wrapper for a storage +/// location, which is then used to set the storage location for the result +/// object when we process the AST node for that result object. +/// +/// For example: +/// MyStruct S = MyStruct(3); +/// +/// In this example, `MyStruct(3) is a prvalue, which is modeled as a +/// `RecordValue` that wraps a `RecordStorageLocation`. This +/// `RecordStorageLocation` is then used as the storage location for `S`. +/// +/// Over time, we may eliminate `RecordValue` entirely. See also the discussion +/// here: https://reviews.llvm.org/D155204#inline-1503204 +class RecordValue final : public Value { +public: + explicit RecordValue(RecordStorageLocation &Loc) + : Value(Kind::Record), Loc(Loc) {} + + static bool classof(const Value *Val) { + return Val->getKind() == Kind::Record; + } + + /// Returns the storage location that this `RecordValue` is associated with. + RecordStorageLocation &getLoc() const { return Loc; } + +private: + RecordStorageLocation &Loc; +}; + +raw_ostream &operator<<(raw_ostream &OS, const Value &Val); + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h new file mode 100644 index 000000000000..5448eecf6d41 --- /dev/null +++ b/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h @@ -0,0 +1,58 @@ +//===- WatchedLiteralsSolver.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 SAT solver implementation that can be used by dataflow +// analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_WATCHEDLITERALSSOLVER_H +#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_WATCHEDLITERALSSOLVER_H + +#include "clang/Analysis/FlowSensitive/Formula.h" +#include "clang/Analysis/FlowSensitive/Solver.h" +#include "llvm/ADT/ArrayRef.h" +#include <limits> + +namespace clang { +namespace dataflow { + +/// A SAT solver that is an implementation of Algorithm D from Knuth's The Art +/// of Computer Programming Volume 4: Satisfiability, Fascicle 6. It is based on +/// the Davis-Putnam-Logemann-Loveland (DPLL) algorithm, keeps references to a +/// single "watched" literal per clause, and uses a set of "active" variables +/// for unit propagation. +class WatchedLiteralsSolver : public Solver { + // Count of the iterations of the main loop of the solver. This spans *all* + // calls to the underlying solver across the life of this object. It is + // reduced with every (non-trivial) call to the solver. + // + // We give control over the abstract count of iterations instead of concrete + // measurements like CPU cycles or time to ensure deterministic results. + std::int64_t MaxIterations = std::numeric_limits<std::int64_t>::max(); + +public: + WatchedLiteralsSolver() = default; + + // `Work` specifies a computational limit on the solver. Units of "work" + // roughly correspond to attempts to assign a value to a single + // variable. Since the algorithm is exponential in the number of variables, + // this is the most direct (abstract) unit to target. + explicit WatchedLiteralsSolver(std::int64_t WorkLimit) + : MaxIterations(WorkLimit) {} + + Result solve(llvm::ArrayRef<const Formula *> Vals) override; + + // The solver reached its maximum number of iterations. + bool reachedLimit() const { return MaxIterations == 0; } +}; + +} // namespace dataflow +} // namespace clang + +#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_WATCHEDLITERALSSOLVER_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/IssueHash.h b/contrib/llvm-project/clang/include/clang/Analysis/IssueHash.h index 9c02b79f58f9..78bebbdb6ec7 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/IssueHash.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/IssueHash.h @@ -5,8 +5,8 @@ // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_STATICANALYZER_CORE_ISSUE_HASH_H -#define LLVM_CLANG_STATICANALYZER_CORE_ISSUE_HASH_H +#ifndef LLVM_CLANG_ANALYSIS_ISSUEHASH_H +#define LLVM_CLANG_ANALYSIS_ISSUEHASH_H #include "llvm/ADT/SmallString.h" diff --git a/contrib/llvm-project/clang/include/clang/Analysis/MacroExpansionContext.h b/contrib/llvm-project/clang/include/clang/Analysis/MacroExpansionContext.h index 57934bfc09d9..2a27aba76656 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/MacroExpansionContext.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/MacroExpansionContext.h @@ -13,9 +13,9 @@ #include "clang/Basic/SourceLocation.h" #include "clang/Lex/Preprocessor.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/SmallVector.h" +#include <optional> namespace clang { @@ -85,14 +85,16 @@ public: /// \param MacroExpansionLoc Must be the expansion location of a macro. /// \return The textual representation of the token sequence which was /// substituted in place of the macro after the preprocessing. - /// If no macro was expanded at that location, returns llvm::None. - Optional<StringRef> getExpandedText(SourceLocation MacroExpansionLoc) const; + /// If no macro was expanded at that location, returns std::nullopt. + std::optional<StringRef> + getExpandedText(SourceLocation MacroExpansionLoc) const; /// \param MacroExpansionLoc Must be the expansion location of a macro. /// \return The text from the original source code which were substituted by /// the macro expansion chain from the given location. - /// If no macro was expanded at that location, returns llvm::None. - Optional<StringRef> getOriginalText(SourceLocation MacroExpansionLoc) const; + /// If no macro was expanded at that location, returns std::nullopt. + std::optional<StringRef> + getOriginalText(SourceLocation MacroExpansionLoc) const; LLVM_DUMP_METHOD void dumpExpansionRangesToStream(raw_ostream &OS) const; LLVM_DUMP_METHOD void dumpExpandedTextsToStream(raw_ostream &OS) const; diff --git a/contrib/llvm-project/clang/include/clang/Analysis/PathDiagnostic.h b/contrib/llvm-project/clang/include/clang/Analysis/PathDiagnostic.h index 539aa20b8168..90559e7efb06 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/PathDiagnostic.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/PathDiagnostic.h @@ -10,8 +10,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H -#define LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H +#ifndef LLVM_CLANG_ANALYSIS_PATHDIAGNOSTIC_H +#define LLVM_CLANG_ANALYSIS_PATHDIAGNOSTIC_H #include "clang/AST/Stmt.h" #include "clang/Analysis/AnalysisDeclContext.h" @@ -19,7 +19,6 @@ #include "clang/Basic/SourceLocation.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/PointerUnion.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" @@ -30,6 +29,7 @@ #include <list> #include <map> #include <memory> +#include <optional> #include <set> #include <string> #include <utility> @@ -41,10 +41,8 @@ class AnalysisDeclContext; class BinaryOperator; class CallEnter; class CallExitEnd; -class CallExpr; class ConditionalOperator; class Decl; -class Expr; class LocationContext; class MemberExpr; class ProgramPoint; @@ -75,14 +73,8 @@ struct PathDiagnosticConsumerOptions { bool ShouldSerializeStats = false; /// If the consumer intends to produce multiple output files, should it - /// use randomly generated file names for these files (with the tiny risk of - /// having random collisions) or deterministic human-readable file names - /// (with a larger risk of deterministic collisions or invalid characters - /// in the file name). We should not really give this choice to the users - /// because deterministic mode is always superior when done right, but - /// for some consumers this mode is experimental and needs to be - /// off by default. - bool ShouldWriteStableReportFilename = false; + /// use a pseudo-random file name or a human-readable file name. + bool ShouldWriteVerboseReportFilename = false; /// Whether the consumer should treat consumed diagnostics as hard errors. /// Useful for breaking your build when issues are found. @@ -151,11 +143,14 @@ public: /// Only runs visitors, no output generated. None, - /// Used for HTML, SARIF, and text output. + /// Used for SARIF and text output. Minimal, /// Used for plist output, used for "arrows" generation. Extensive, + + /// Used for HTML, shows both "arrows" and control notes. + Everything }; virtual PathGenerationScheme getGenerationScheme() const { return Minimal; } @@ -164,7 +159,11 @@ public: return getGenerationScheme() != None; } - bool shouldAddPathEdges() const { return getGenerationScheme() == Extensive; } + bool shouldAddPathEdges() const { return getGenerationScheme() >= Extensive; } + bool shouldAddControlNotes() const { + return getGenerationScheme() == Minimal || + getGenerationScheme() == Everything; + } virtual bool supportsLogicalOpControlFlow() const { return false; } @@ -533,7 +532,7 @@ public: }; class PathDiagnosticEventPiece : public PathDiagnosticSpotPiece { - Optional<bool> IsPrunable; + std::optional<bool> IsPrunable; public: PathDiagnosticEventPiece(const PathDiagnosticLocation &pos, @@ -545,15 +544,13 @@ public: /// flag may have been previously set, at which point it will not /// be reset unless one specifies to do so. void setPrunable(bool isPrunable, bool override = false) { - if (IsPrunable.hasValue() && !override) - return; + if (IsPrunable && !override) + return; IsPrunable = isPrunable; } /// Return true if the diagnostic piece is prunable. - bool isPrunable() const { - return IsPrunable.hasValue() ? IsPrunable.getValue() : false; - } + bool isPrunable() const { return IsPrunable.value_or(false); } void dump() const override; @@ -904,4 +901,4 @@ public: } // namespace ento } // namespace clang -#endif // LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_PATHDIAGNOSTIC_H +#endif // LLVM_CLANG_ANALYSIS_PATHDIAGNOSTIC_H diff --git a/contrib/llvm-project/clang/include/clang/Analysis/ProgramPoint.h b/contrib/llvm-project/clang/include/clang/Analysis/ProgramPoint.h index 546224bfd58d..b9339570e1ae 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/ProgramPoint.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/ProgramPoint.h @@ -18,19 +18,18 @@ #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Casting.h" #include "llvm/Support/DataTypes.h" #include <cassert> +#include <optional> #include <string> #include <utility> namespace clang { class AnalysisDeclContext; -class FunctionDecl; class LocationContext; /// ProgramPoints can be "tagged" as representing points specific to a given @@ -96,35 +95,33 @@ private: llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag; + CFGBlock::ConstCFGElementRef ElemRef = {nullptr, 0}; + protected: ProgramPoint() = default; - ProgramPoint(const void *P, - Kind k, - const LocationContext *l, - const ProgramPointTag *tag = nullptr) - : Data1(P), - Data2(nullptr, (((unsigned) k) >> 0) & 0x3), - L(l, (((unsigned) k) >> 2) & 0x3), - Tag(tag, (((unsigned) k) >> 4) & 0x3) { - assert(getKind() == k); - assert(getLocationContext() == l); - assert(getData1() == P); - } - - ProgramPoint(const void *P1, - const void *P2, - Kind k, - const LocationContext *l, - const ProgramPointTag *tag = nullptr) - : Data1(P1), - Data2(P2, (((unsigned) k) >> 0) & 0x3), - L(l, (((unsigned) k) >> 2) & 0x3), - Tag(tag, (((unsigned) k) >> 4) & 0x3) {} + ProgramPoint(const void *P, Kind k, const LocationContext *l, + const ProgramPointTag *tag = nullptr, + CFGBlock::ConstCFGElementRef ElemRef = {nullptr, 0}) + : Data1(P), Data2(nullptr, (((unsigned)k) >> 0) & 0x3), + L(l, (((unsigned)k) >> 2) & 0x3), Tag(tag, (((unsigned)k) >> 4) & 0x3), + ElemRef(ElemRef) { + assert(getKind() == k); + assert(getLocationContext() == l); + assert(getData1() == P); + } + + ProgramPoint(const void *P1, const void *P2, Kind k, const LocationContext *l, + const ProgramPointTag *tag = nullptr, + CFGBlock::ConstCFGElementRef ElemRef = {nullptr, 0}) + : Data1(P1), Data2(P2, (((unsigned)k) >> 0) & 0x3), + L(l, (((unsigned)k) >> 2) & 0x3), Tag(tag, (((unsigned)k) >> 4) & 0x3), + ElemRef(ElemRef) {} protected: const void *getData1() const { return Data1; } const void *getData2() const { return Data2.getPointer(); } void setData2(const void *d) { Data2.setPointer(d); } + CFGBlock::ConstCFGElementRef getElementRef() const { return ElemRef; } public: /// Create a new ProgramPoint object that is the same as the original @@ -145,12 +142,11 @@ public: return t; } - /// Convert to the specified ProgramPoint type, returning None if this + /// Convert to the specified ProgramPoint type, returning std::nullopt if this /// ProgramPoint is not of the desired type. - template<typename T> - Optional<T> getAs() const { + template <typename T> std::optional<T> getAs() const { if (!T::isKind(*this)) - return None; + return std::nullopt; T t; ProgramPoint& PP = t; PP = *this; @@ -192,17 +188,13 @@ public: } bool operator==(const ProgramPoint & RHS) const { - return Data1 == RHS.Data1 && - Data2 == RHS.Data2 && - L == RHS.L && - Tag == RHS.Tag; + return Data1 == RHS.Data1 && Data2 == RHS.Data2 && L == RHS.L && + Tag == RHS.Tag && ElemRef == RHS.ElemRef; } bool operator!=(const ProgramPoint &RHS) const { - return Data1 != RHS.Data1 || - Data2 != RHS.Data2 || - L != RHS.L || - Tag != RHS.Tag; + return Data1 != RHS.Data1 || Data2 != RHS.Data2 || L != RHS.L || + Tag != RHS.Tag || ElemRef != RHS.ElemRef; } void Profile(llvm::FoldingSetNodeID& ID) const { @@ -211,6 +203,8 @@ public: ID.AddPointer(getData2()); ID.AddPointer(getLocationContext()); ID.AddPointer(getTag()); + ID.AddPointer(ElemRef.getParent()); + ID.AddInteger(ElemRef.getIndexInBlock()); } void printJson(llvm::raw_ostream &Out, const char *NL = "\n") const; @@ -234,9 +228,9 @@ public: return reinterpret_cast<const CFGBlock*>(getData1()); } - Optional<CFGElement> getFirstElement() const { + std::optional<CFGElement> getFirstElement() const { const CFGBlock *B = getBlock(); - return B->empty() ? Optional<CFGElement>() : B->front(); + return B->empty() ? std::optional<CFGElement>() : B->front(); } private: @@ -268,6 +262,7 @@ private: } }; +// FIXME: Eventually we want to take a CFGElementRef as parameter here too. class StmtPoint : public ProgramPoint { public: StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, @@ -559,8 +554,9 @@ private: class ImplicitCallPoint : public ProgramPoint { public: ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K, - const LocationContext *L, const ProgramPointTag *Tag) - : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {} + const LocationContext *L, const ProgramPointTag *Tag, + CFGBlock::ConstCFGElementRef ElemRef) + : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag, ElemRef) {} const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); } SourceLocation getLocation() const { @@ -583,8 +579,9 @@ private: class PreImplicitCall : public ImplicitCallPoint { public: PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, + CFGBlock::ConstCFGElementRef ElemRef, const ProgramPointTag *Tag = nullptr) - : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {} + : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag, ElemRef) {} private: friend class ProgramPoint; @@ -600,8 +597,9 @@ private: class PostImplicitCall : public ImplicitCallPoint { public: PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, + CFGBlock::ConstCFGElementRef ElemRef, const ProgramPointTag *Tag = nullptr) - : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {} + : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag, ElemRef) {} private: friend class ProgramPoint; diff --git a/contrib/llvm-project/clang/include/clang/Analysis/RetainSummaryManager.h b/contrib/llvm-project/clang/include/clang/Analysis/RetainSummaryManager.h index b7ccb0317830..86865b9da421 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/RetainSummaryManager.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/RetainSummaryManager.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_ANALYSIS_RETAINSUMMARY_MANAGER_H -#define LLVM_CLANG_ANALYSIS_RETAINSUMMARY_MANAGER_H +#ifndef LLVM_CLANG_ANALYSIS_RETAINSUMMARYMANAGER_H +#define LLVM_CLANG_ANALYSIS_RETAINSUMMARYMANAGER_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" @@ -25,6 +25,7 @@ #include "clang/Analysis/AnyCall.h" #include "clang/Analysis/SelectorExtras.h" #include "llvm/ADT/STLExtras.h" +#include <optional> using namespace clang; @@ -648,8 +649,9 @@ public: IdentityOrZero }; - Optional<BehaviorSummary> canEval(const CallExpr *CE, const FunctionDecl *FD, - bool &hasTrustedImplementationAnnotation); + std::optional<BehaviorSummary> + canEval(const CallExpr *CE, const FunctionDecl *FD, + bool &hasTrustedImplementationAnnotation); /// \return Whether the type corresponds to a known smart pointer /// implementation (that is, everything about it is inlineable). @@ -686,8 +688,8 @@ private: Selector S, QualType RetTy); /// Determine if there is a special return effect for this function or method. - Optional<RetEffect> getRetEffectFromAnnotations(QualType RetTy, - const Decl *D); + std::optional<RetEffect> getRetEffectFromAnnotations(QualType RetTy, + const Decl *D); void updateSummaryFromAnnotations(const RetainSummary *&Summ, const ObjCMethodDecl *MD); @@ -719,14 +721,14 @@ private: /// type for functions/methods) @c QT has any of the given attributes, /// provided they pass necessary validation checks AND tracking the given /// attribute is enabled. - /// Returns the object kind corresponding to the present attribute, or None, - /// if none of the specified attributes are present. + /// Returns the object kind corresponding to the present attribute, or + /// std::nullopt, if none of the specified attributes are present. /// Crashes if passed an attribute which is not explicitly handled. template <class T> - Optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); + std::optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); template <class T1, class T2, class... Others> - Optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); + std::optional<ObjKind> hasAnyEnabledAttrOf(const Decl *D, QualType QT); friend class RetainSummaryTemplate; }; diff --git a/contrib/llvm-project/clang/include/clang/Analysis/SelectorExtras.h b/contrib/llvm-project/clang/include/clang/Analysis/SelectorExtras.h index d26e9159a937..1e1daf5706bb 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/SelectorExtras.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/SelectorExtras.h @@ -6,8 +6,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_LIB_ANALYSIS_SELECTOREXTRAS_H -#define LLVM_CLANG_LIB_ANALYSIS_SELECTOREXTRAS_H +#ifndef LLVM_CLANG_ANALYSIS_SELECTOREXTRAS_H +#define LLVM_CLANG_ANALYSIS_SELECTOREXTRAS_H #include "clang/AST/ASTContext.h" @@ -16,7 +16,7 @@ namespace clang { template <typename... IdentifierInfos> static inline Selector getKeywordSelector(ASTContext &Ctx, IdentifierInfos *... IIs) { - static_assert(sizeof...(IdentifierInfos), + static_assert(sizeof...(IdentifierInfos) > 0, "keyword selectors must have at least one argument"); SmallVector<IdentifierInfo *, 10> II({&Ctx.Idents.get(IIs)...}); diff --git a/contrib/llvm-project/clang/include/clang/Analysis/Support/BumpVector.h b/contrib/llvm-project/clang/include/clang/Analysis/Support/BumpVector.h index 74092dabbfda..6c3f11e99306 100644 --- a/contrib/llvm-project/clang/include/clang/Analysis/Support/BumpVector.h +++ b/contrib/llvm-project/clang/include/clang/Analysis/Support/BumpVector.h @@ -42,6 +42,15 @@ public: Other.Alloc.setPointer(nullptr); } + // The move assignment operator is defined as deleted pending further + // motivation. + BumpVectorContext &operator=(BumpVectorContext &&) = delete; + + // The copy constrcutor and copy assignment operator is defined as deleted + // pending further motivation. + BumpVectorContext(const BumpVectorContext &) = delete; + BumpVectorContext &operator=(const BumpVectorContext &) = delete; + /// Construct a new BumpVectorContext that reuses an existing /// BumpPtrAllocator. This BumpPtrAllocator is not destroyed when the /// BumpVectorContext object is destroyed. |