#pragma once #ifdef __GNUC__ #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-parameter" #endif //==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- 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 interface ProgramPoint, which identifies a // distinct location in a function. // //===----------------------------------------------------------------------===// #ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H #define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H #include "clang/Analysis/AnalysisDeclContext.h" #include "clang/Analysis/CFG.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/StringRef.h" #include "llvm/Support/Casting.h" #include "llvm/Support/DataTypes.h" #include #include #include #include namespace clang { class AnalysisDeclContext; class LocationContext; /// ProgramPoints can be "tagged" as representing points specific to a given /// analysis entity. Tags are abstract annotations, with an associated /// description and potentially other information. class ProgramPointTag { public: ProgramPointTag(void *tagKind = nullptr) : TagKind(tagKind) {} virtual ~ProgramPointTag(); virtual StringRef getTagDescription() const = 0; /// Used to implement 'isKind' in subclasses. const void *getTagKind() const { return TagKind; } private: const void *const TagKind; }; class SimpleProgramPointTag : public ProgramPointTag { std::string Desc; public: SimpleProgramPointTag(StringRef MsgProvider, StringRef Msg); StringRef getTagDescription() const override; }; class ProgramPoint { public: enum Kind { BlockEdgeKind, BlockEntranceKind, BlockExitKind, PreStmtKind, PreStmtPurgeDeadSymbolsKind, PostStmtPurgeDeadSymbolsKind, PostStmtKind, PreLoadKind, PostLoadKind, PreStoreKind, PostStoreKind, PostConditionKind, PostLValueKind, PostAllocatorCallKind, MinPostStmtKind = PostStmtKind, MaxPostStmtKind = PostAllocatorCallKind, PostInitializerKind, CallEnterKind, CallExitBeginKind, CallExitEndKind, FunctionExitKind, PreImplicitCallKind, PostImplicitCallKind, MinImplicitCallKind = PreImplicitCallKind, MaxImplicitCallKind = PostImplicitCallKind, LoopExitKind, EpsilonKind}; private: const void *Data1; llvm::PointerIntPair Data2; // The LocationContext could be NULL to allow ProgramPoint to be used in // context insensitive analysis. llvm::PointerIntPair L; llvm::PointerIntPair Tag; 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) {} protected: const void *getData1() const { return Data1; } const void *getData2() const { return Data2.getPointer(); } void setData2(const void *d) { Data2.setPointer(d); } public: /// Create a new ProgramPoint object that is the same as the original /// except for using the specified tag value. ProgramPoint withTag(const ProgramPointTag *tag) const { return ProgramPoint(getData1(), getData2(), getKind(), getLocationContext(), tag); } /// Convert to the specified ProgramPoint type, asserting that this /// ProgramPoint is of the desired type. template T castAs() const { assert(T::isKind(*this)); T t; ProgramPoint& PP = t; PP = *this; return t; } /// Convert to the specified ProgramPoint type, returning std::nullopt if this /// ProgramPoint is not of the desired type. template std::optional getAs() const { if (!T::isKind(*this)) return std::nullopt; T t; ProgramPoint& PP = t; PP = *this; return t; } Kind getKind() const { unsigned x = Tag.getInt(); x <<= 2; x |= L.getInt(); x <<= 2; x |= Data2.getInt(); return (Kind) x; } /// Is this a program point corresponding to purge/removal of dead /// symbols and bindings. bool isPurgeKind() { Kind K = getKind(); return (K == PostStmtPurgeDeadSymbolsKind || K == PreStmtPurgeDeadSymbolsKind); } const ProgramPointTag *getTag() const { return Tag.getPointer(); } const LocationContext *getLocationContext() const { return L.getPointer(); } const StackFrameContext *getStackFrame() const { return getLocationContext()->getStackFrame(); } // For use with DenseMap. This hash is probably slow. unsigned getHashValue() const { llvm::FoldingSetNodeID ID; Profile(ID); return ID.ComputeHash(); } bool operator==(const ProgramPoint & RHS) const { return Data1 == RHS.Data1 && Data2 == RHS.Data2 && L == RHS.L && Tag == RHS.Tag; } bool operator!=(const ProgramPoint &RHS) const { return Data1 != RHS.Data1 || Data2 != RHS.Data2 || L != RHS.L || Tag != RHS.Tag; } void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddInteger((unsigned) getKind()); ID.AddPointer(getData1()); ID.AddPointer(getData2()); ID.AddPointer(getLocationContext()); ID.AddPointer(getTag()); } void printJson(llvm::raw_ostream &Out, const char *NL = "\n") const; LLVM_DUMP_METHOD void dump() const; static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K, const LocationContext *LC, const ProgramPointTag *tag); }; class BlockEntrance : public ProgramPoint { public: BlockEntrance(const CFGBlock *B, const LocationContext *L, const ProgramPointTag *tag = nullptr) : ProgramPoint(B, BlockEntranceKind, L, tag) { assert(B && "BlockEntrance requires non-null block"); } const CFGBlock *getBlock() const { return reinterpret_cast(getData1()); } std::optional getFirstElement() const { const CFGBlock *B = getBlock(); return B->empty() ? std::optional() : B->front(); } private: friend class ProgramPoint; BlockEntrance() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockEntranceKind; } }; class BlockExit : public ProgramPoint { public: BlockExit(const CFGBlock *B, const LocationContext *L) : ProgramPoint(B, BlockExitKind, L) {} const CFGBlock *getBlock() const { return reinterpret_cast(getData1()); } const Stmt *getTerminator() const { return getBlock()->getTerminatorStmt(); } private: friend class ProgramPoint; BlockExit() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockExitKind; } }; class StmtPoint : public ProgramPoint { public: StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L, const ProgramPointTag *tag) : ProgramPoint(S, p2, k, L, tag) { assert(S); } const Stmt *getStmt() const { return (const Stmt*) getData1(); } template const T* getStmtAs() const { return dyn_cast(getStmt()); } protected: StmtPoint() = default; private: friend class ProgramPoint; static bool isKind(const ProgramPoint &Location) { unsigned k = Location.getKind(); return k >= PreStmtKind && k <= MaxPostStmtKind; } }; class PreStmt : public StmtPoint { public: PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag, const Stmt *SubStmt = nullptr) : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {} const Stmt *getSubStmt() const { return (const Stmt*) getData2(); } private: friend class ProgramPoint; PreStmt() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreStmtKind; } }; class PostStmt : public StmtPoint { protected: PostStmt() = default; PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, data, k, L, tag) {} public: explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, nullptr, k, L, tag) {} explicit PostStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, nullptr, PostStmtKind, L, tag) {} private: friend class ProgramPoint; static bool isKind(const ProgramPoint &Location) { unsigned k = Location.getKind(); return k >= MinPostStmtKind && k <= MaxPostStmtKind; } }; class FunctionExitPoint : public ProgramPoint { public: explicit FunctionExitPoint(const ReturnStmt *S, const LocationContext *LC, const ProgramPointTag *tag = nullptr) : ProgramPoint(S, FunctionExitKind, LC, tag) {} const CFGBlock *getBlock() const { return &getLocationContext()->getCFG()->getExit(); } const ReturnStmt *getStmt() const { return reinterpret_cast(getData1()); } private: friend class ProgramPoint; FunctionExitPoint() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == FunctionExitKind; } }; // PostCondition represents the post program point of a branch condition. class PostCondition : public PostStmt { public: PostCondition(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : PostStmt(S, PostConditionKind, L, tag) {} private: friend class ProgramPoint; PostCondition() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostConditionKind; } }; class LocationCheck : public StmtPoint { protected: LocationCheck() = default; LocationCheck(const Stmt *S, const LocationContext *L, ProgramPoint::Kind K, const ProgramPointTag *tag) : StmtPoint(S, nullptr, K, L, tag) {} private: friend class ProgramPoint; static bool isKind(const ProgramPoint &location) { unsigned k = location.getKind(); return k == PreLoadKind || k == PreStoreKind; } }; class PreLoad : public LocationCheck { public: PreLoad(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : LocationCheck(S, L, PreLoadKind, tag) {} private: friend class ProgramPoint; PreLoad() = default; static bool isKind(const ProgramPoint &location) { return location.getKind() == PreLoadKind; } }; class PreStore : public LocationCheck { public: PreStore(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : LocationCheck(S, L, PreStoreKind, tag) {} private: friend class ProgramPoint; PreStore() = default; static bool isKind(const ProgramPoint &location) { return location.getKind() == PreStoreKind; } }; class PostLoad : public PostStmt { public: PostLoad(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : PostStmt(S, PostLoadKind, L, tag) {} private: friend class ProgramPoint; PostLoad() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostLoadKind; } }; /// Represents a program point after a store evaluation. class PostStore : public PostStmt { public: /// Construct the post store point. /// \param Loc can be used to store the information about the location /// used in the form it was uttered in the code. PostStore(const Stmt *S, const LocationContext *L, const void *Loc, const ProgramPointTag *tag = nullptr) : PostStmt(S, PostStoreKind, L, tag) { assert(getData2() == nullptr); setData2(Loc); } /// Returns the information about the location used in the store, /// how it was uttered in the code. const void *getLocationValue() const { return getData2(); } private: friend class ProgramPoint; PostStore() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostStoreKind; } }; class PostLValue : public PostStmt { public: PostLValue(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : PostStmt(S, PostLValueKind, L, tag) {} private: friend class ProgramPoint; PostLValue() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostLValueKind; } }; /// Represents a point after we ran remove dead bindings BEFORE /// processing the given statement. class PreStmtPurgeDeadSymbols : public StmtPoint { public: PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { } private: friend class ProgramPoint; PreStmtPurgeDeadSymbols() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreStmtPurgeDeadSymbolsKind; } }; /// Represents a point after we ran remove dead bindings AFTER /// processing the given statement. class PostStmtPurgeDeadSymbols : public StmtPoint { public: PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag = nullptr) : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { } private: friend class ProgramPoint; PostStmtPurgeDeadSymbols() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostStmtPurgeDeadSymbolsKind; } }; class BlockEdge : public ProgramPoint { public: BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L) : ProgramPoint(B1, B2, BlockEdgeKind, L) { assert(B1 && "BlockEdge: source block must be non-null"); assert(B2 && "BlockEdge: destination block must be non-null"); } const CFGBlock *getSrc() const { return static_cast(getData1()); } const CFGBlock *getDst() const { return static_cast(getData2()); } private: friend class ProgramPoint; BlockEdge() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == BlockEdgeKind; } }; class PostInitializer : public ProgramPoint { public: /// Construct a PostInitializer point that represents a location after /// CXXCtorInitializer expression evaluation. /// /// \param I The initializer. /// \param Loc The location of the field being initialized. PostInitializer(const CXXCtorInitializer *I, const void *Loc, const LocationContext *L) : ProgramPoint(I, Loc, PostInitializerKind, L) {} const CXXCtorInitializer *getInitializer() const { return static_cast(getData1()); } /// Returns the location of the field. const void *getLocationValue() const { return getData2(); } private: friend class ProgramPoint; PostInitializer() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostInitializerKind; } }; /// Represents an implicit call event. /// /// The nearest statement is provided for diagnostic purposes. 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 Decl *getDecl() const { return static_cast(getData2()); } SourceLocation getLocation() const { return SourceLocation::getFromPtrEncoding(getData1()); } protected: ImplicitCallPoint() = default; private: friend class ProgramPoint; static bool isKind(const ProgramPoint &Location) { return Location.getKind() >= MinImplicitCallKind && Location.getKind() <= MaxImplicitCallKind; } }; /// Represents a program point just before an implicit call event. /// /// Explicit calls will appear as PreStmt program points. class PreImplicitCall : public ImplicitCallPoint { public: PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, const ProgramPointTag *Tag = nullptr) : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {} private: friend class ProgramPoint; PreImplicitCall() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PreImplicitCallKind; } }; /// Represents a program point just after an implicit call event. /// /// Explicit calls will appear as PostStmt program points. class PostImplicitCall : public ImplicitCallPoint { public: PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L, const ProgramPointTag *Tag = nullptr) : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {} private: friend class ProgramPoint; PostImplicitCall() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostImplicitCallKind; } }; class PostAllocatorCall : public StmtPoint { public: PostAllocatorCall(const Stmt *S, const LocationContext *L, const ProgramPointTag *Tag = nullptr) : StmtPoint(S, nullptr, PostAllocatorCallKind, L, Tag) {} private: friend class ProgramPoint; PostAllocatorCall() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == PostAllocatorCallKind; } }; /// Represents a point when we begin processing an inlined call. /// CallEnter uses the caller's location context. class CallEnter : public ProgramPoint { public: CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx, const LocationContext *callerCtx) : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {} const Stmt *getCallExpr() const { return static_cast(getData1()); } const StackFrameContext *getCalleeContext() const { return static_cast(getData2()); } /// Returns the entry block in the CFG for the entered function. const CFGBlock *getEntry() const { const StackFrameContext *CalleeCtx = getCalleeContext(); const CFG *CalleeCFG = CalleeCtx->getCFG(); return &(CalleeCFG->getEntry()); } private: friend class ProgramPoint; CallEnter() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallEnterKind; } }; /// Represents a point when we start the call exit sequence (for inlined call). /// /// The call exit is simulated with a sequence of nodes, which occur between /// CallExitBegin and CallExitEnd. The following operations occur between the /// two program points: /// - CallExitBegin /// - Bind the return value /// - Run Remove dead bindings (to clean up the dead symbols from the callee). /// - CallExitEnd class CallExitBegin : public ProgramPoint { public: // CallExitBegin uses the callee's location context. CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS) : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { } const ReturnStmt *getReturnStmt() const { return static_cast(getData1()); } private: friend class ProgramPoint; CallExitBegin() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallExitBeginKind; } }; /// Represents a point when we finish the call exit sequence (for inlined call). /// \sa CallExitBegin class CallExitEnd : public ProgramPoint { public: // CallExitEnd uses the caller's location context. CallExitEnd(const StackFrameContext *CalleeCtx, const LocationContext *CallerCtx) : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {} const StackFrameContext *getCalleeContext() const { return static_cast(getData1()); } private: friend class ProgramPoint; CallExitEnd() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == CallExitEndKind; } }; /// Represents a point when we exit a loop. /// When this ProgramPoint is encountered we can be sure that the symbolic /// execution of the corresponding LoopStmt is finished on the given path. /// Note: It is possible to encounter a LoopExit element when we haven't even /// encountered the loop itself. At the current state not all loop exits will /// result in a LoopExit program point. class LoopExit : public ProgramPoint { public: LoopExit(const Stmt *LoopStmt, const LocationContext *LC) : ProgramPoint(LoopStmt, nullptr, LoopExitKind, LC) {} const Stmt *getLoopStmt() const { return static_cast(getData1()); } private: friend class ProgramPoint; LoopExit() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == LoopExitKind; } }; /// This is a meta program point, which should be skipped by all the diagnostic /// reasoning etc. class EpsilonPoint : public ProgramPoint { public: EpsilonPoint(const LocationContext *L, const void *Data1, const void *Data2 = nullptr, const ProgramPointTag *tag = nullptr) : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {} const void *getData() const { return getData1(); } private: friend class ProgramPoint; EpsilonPoint() = default; static bool isKind(const ProgramPoint &Location) { return Location.getKind() == EpsilonKind; } }; } // end namespace clang namespace llvm { // Traits specialization for DenseMap template <> struct DenseMapInfo { static inline clang::ProgramPoint getEmptyKey() { uintptr_t x = reinterpret_cast(DenseMapInfo::getEmptyKey()) & ~0x7; return clang::BlockEntrance(reinterpret_cast(x), nullptr); } static inline clang::ProgramPoint getTombstoneKey() { uintptr_t x = reinterpret_cast(DenseMapInfo::getTombstoneKey()) & ~0x7; return clang::BlockEntrance(reinterpret_cast(x), nullptr); } static unsigned getHashValue(const clang::ProgramPoint &Loc) { return Loc.getHashValue(); } static bool isEqual(const clang::ProgramPoint &L, const clang::ProgramPoint &R) { return L == R; } }; } // end namespace llvm #endif #ifdef __GNUC__ #pragma GCC diagnostic pop #endif