1 //==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the interface ProgramPoint, which identifies a
11 // distinct location in a function.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
16 #define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
18 #include "clang/Analysis/AnalysisContext.h"
19 #include "clang/Analysis/CFG.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/FoldingSet.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/PointerIntPair.h"
24 #include "llvm/ADT/StringRef.h"
25 #include "llvm/Support/Casting.h"
26 #include "llvm/Support/DataTypes.h"
33 class AnalysisDeclContext;
35 class LocationContext;
37 /// ProgramPoints can be "tagged" as representing points specific to a given
38 /// analysis entity. Tags are abstract annotations, with an associated
39 /// description and potentially other information.
40 class ProgramPointTag {
42 ProgramPointTag(void *tagKind = nullptr) : TagKind(tagKind) {}
43 virtual ~ProgramPointTag();
44 virtual StringRef getTagDescription() const = 0;
47 /// Used to implement 'isKind' in subclasses.
48 const void *getTagKind() { return TagKind; }
54 class SimpleProgramPointTag : public ProgramPointTag {
57 SimpleProgramPointTag(StringRef MsgProvider, StringRef Msg);
58 StringRef getTagDescription() const override;
63 enum Kind { BlockEdgeKind,
67 PreStmtPurgeDeadSymbolsKind,
68 PostStmtPurgeDeadSymbolsKind,
76 MinPostStmtKind = PostStmtKind,
77 MaxPostStmtKind = PostLValueKind,
84 MinImplicitCallKind = PreImplicitCallKind,
85 MaxImplicitCallKind = PostImplicitCallKind,
90 llvm::PointerIntPair<const void *, 2, unsigned> Data2;
92 // The LocationContext could be NULL to allow ProgramPoint to be used in
93 // context insensitive analysis.
94 llvm::PointerIntPair<const LocationContext *, 2, unsigned> L;
96 llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
100 ProgramPoint(const void *P,
102 const LocationContext *l,
103 const ProgramPointTag *tag = nullptr)
105 Data2(nullptr, (((unsigned) k) >> 0) & 0x3),
106 L(l, (((unsigned) k) >> 2) & 0x3),
107 Tag(tag, (((unsigned) k) >> 4) & 0x3) {
108 assert(getKind() == k);
109 assert(getLocationContext() == l);
110 assert(getData1() == P);
113 ProgramPoint(const void *P1,
116 const LocationContext *l,
117 const ProgramPointTag *tag = nullptr)
119 Data2(P2, (((unsigned) k) >> 0) & 0x3),
120 L(l, (((unsigned) k) >> 2) & 0x3),
121 Tag(tag, (((unsigned) k) >> 4) & 0x3) {}
124 const void *getData1() const { return Data1; }
125 const void *getData2() const { return Data2.getPointer(); }
126 void setData2(const void *d) { Data2.setPointer(d); }
129 /// Create a new ProgramPoint object that is the same as the original
130 /// except for using the specified tag value.
131 ProgramPoint withTag(const ProgramPointTag *tag) const {
132 return ProgramPoint(getData1(), getData2(), getKind(),
133 getLocationContext(), tag);
136 /// \brief Convert to the specified ProgramPoint type, asserting that this
137 /// ProgramPoint is of the desired type.
140 assert(T::isKind(*this));
142 ProgramPoint& PP = t;
147 /// \brief Convert to the specified ProgramPoint type, returning None if this
148 /// ProgramPoint is not of the desired type.
150 Optional<T> getAs() const {
151 if (!T::isKind(*this))
154 ProgramPoint& PP = t;
159 Kind getKind() const {
160 unsigned x = Tag.getInt();
168 /// \brief Is this a program point corresponding to purge/removal of dead
169 /// symbols and bindings.
172 return (K == PostStmtPurgeDeadSymbolsKind ||
173 K == PreStmtPurgeDeadSymbolsKind);
176 const ProgramPointTag *getTag() const { return Tag.getPointer(); }
178 const LocationContext *getLocationContext() const {
179 return L.getPointer();
182 // For use with DenseMap. This hash is probably slow.
183 unsigned getHashValue() const {
184 llvm::FoldingSetNodeID ID;
186 return ID.ComputeHash();
189 bool operator==(const ProgramPoint & RHS) const {
190 return Data1 == RHS.Data1 &&
191 Data2 == RHS.Data2 &&
196 bool operator!=(const ProgramPoint &RHS) const {
197 return Data1 != RHS.Data1 ||
198 Data2 != RHS.Data2 ||
203 void Profile(llvm::FoldingSetNodeID& ID) const {
204 ID.AddInteger((unsigned) getKind());
205 ID.AddPointer(getData1());
206 ID.AddPointer(getData2());
207 ID.AddPointer(getLocationContext());
208 ID.AddPointer(getTag());
211 static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
212 const LocationContext *LC,
213 const ProgramPointTag *tag);
216 class BlockEntrance : public ProgramPoint {
218 BlockEntrance(const CFGBlock *B, const LocationContext *L,
219 const ProgramPointTag *tag = nullptr)
220 : ProgramPoint(B, BlockEntranceKind, L, tag) {
221 assert(B && "BlockEntrance requires non-null block");
224 const CFGBlock *getBlock() const {
225 return reinterpret_cast<const CFGBlock*>(getData1());
228 Optional<CFGElement> getFirstElement() const {
229 const CFGBlock *B = getBlock();
230 return B->empty() ? Optional<CFGElement>() : B->front();
234 friend class ProgramPoint;
236 static bool isKind(const ProgramPoint &Location) {
237 return Location.getKind() == BlockEntranceKind;
241 class BlockExit : public ProgramPoint {
243 BlockExit(const CFGBlock *B, const LocationContext *L)
244 : ProgramPoint(B, BlockExitKind, L) {}
246 const CFGBlock *getBlock() const {
247 return reinterpret_cast<const CFGBlock*>(getData1());
250 const Stmt *getTerminator() const {
251 return getBlock()->getTerminator();
255 friend class ProgramPoint;
257 static bool isKind(const ProgramPoint &Location) {
258 return Location.getKind() == BlockExitKind;
262 class StmtPoint : public ProgramPoint {
264 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
265 const ProgramPointTag *tag)
266 : ProgramPoint(S, p2, k, L, tag) {
270 const Stmt *getStmt() const { return (const Stmt*) getData1(); }
272 template <typename T>
273 const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
278 friend class ProgramPoint;
279 static bool isKind(const ProgramPoint &Location) {
280 unsigned k = Location.getKind();
281 return k >= PreStmtKind && k <= MaxPostStmtKind;
286 class PreStmt : public StmtPoint {
288 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
289 const Stmt *SubStmt = nullptr)
290 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
292 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
295 friend class ProgramPoint;
297 static bool isKind(const ProgramPoint &Location) {
298 return Location.getKind() == PreStmtKind;
302 class PostStmt : public StmtPoint {
305 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
306 const ProgramPointTag *tag = nullptr)
307 : StmtPoint(S, data, k, L, tag) {}
310 explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L,
311 const ProgramPointTag *tag = nullptr)
312 : StmtPoint(S, nullptr, k, L, tag) {}
314 explicit PostStmt(const Stmt *S, const LocationContext *L,
315 const ProgramPointTag *tag = nullptr)
316 : StmtPoint(S, nullptr, PostStmtKind, L, tag) {}
319 friend class ProgramPoint;
320 static bool isKind(const ProgramPoint &Location) {
321 unsigned k = Location.getKind();
322 return k >= MinPostStmtKind && k <= MaxPostStmtKind;
326 // PostCondition represents the post program point of a branch condition.
327 class PostCondition : public PostStmt {
329 PostCondition(const Stmt *S, const LocationContext *L,
330 const ProgramPointTag *tag = nullptr)
331 : PostStmt(S, PostConditionKind, L, tag) {}
334 friend class ProgramPoint;
336 static bool isKind(const ProgramPoint &Location) {
337 return Location.getKind() == PostConditionKind;
341 class LocationCheck : public StmtPoint {
344 LocationCheck(const Stmt *S, const LocationContext *L,
345 ProgramPoint::Kind K, const ProgramPointTag *tag)
346 : StmtPoint(S, nullptr, K, L, tag) {}
349 friend class ProgramPoint;
350 static bool isKind(const ProgramPoint &location) {
351 unsigned k = location.getKind();
352 return k == PreLoadKind || k == PreStoreKind;
356 class PreLoad : public LocationCheck {
358 PreLoad(const Stmt *S, const LocationContext *L,
359 const ProgramPointTag *tag = nullptr)
360 : LocationCheck(S, L, PreLoadKind, tag) {}
363 friend class ProgramPoint;
365 static bool isKind(const ProgramPoint &location) {
366 return location.getKind() == PreLoadKind;
370 class PreStore : public LocationCheck {
372 PreStore(const Stmt *S, const LocationContext *L,
373 const ProgramPointTag *tag = nullptr)
374 : LocationCheck(S, L, PreStoreKind, tag) {}
377 friend class ProgramPoint;
379 static bool isKind(const ProgramPoint &location) {
380 return location.getKind() == PreStoreKind;
384 class PostLoad : public PostStmt {
386 PostLoad(const Stmt *S, const LocationContext *L,
387 const ProgramPointTag *tag = nullptr)
388 : PostStmt(S, PostLoadKind, L, tag) {}
391 friend class ProgramPoint;
393 static bool isKind(const ProgramPoint &Location) {
394 return Location.getKind() == PostLoadKind;
398 /// \brief Represents a program point after a store evaluation.
399 class PostStore : public PostStmt {
401 /// Construct the post store point.
402 /// \param Loc can be used to store the information about the location
403 /// used in the form it was uttered in the code.
404 PostStore(const Stmt *S, const LocationContext *L, const void *Loc,
405 const ProgramPointTag *tag = nullptr)
406 : PostStmt(S, PostStoreKind, L, tag) {
407 assert(getData2() == nullptr);
411 /// \brief Returns the information about the location used in the store,
412 /// how it was uttered in the code.
413 const void *getLocationValue() const {
418 friend class ProgramPoint;
420 static bool isKind(const ProgramPoint &Location) {
421 return Location.getKind() == PostStoreKind;
425 class PostLValue : public PostStmt {
427 PostLValue(const Stmt *S, const LocationContext *L,
428 const ProgramPointTag *tag = nullptr)
429 : PostStmt(S, PostLValueKind, L, tag) {}
432 friend class ProgramPoint;
434 static bool isKind(const ProgramPoint &Location) {
435 return Location.getKind() == PostLValueKind;
439 /// Represents a point after we ran remove dead bindings BEFORE
440 /// processing the given statement.
441 class PreStmtPurgeDeadSymbols : public StmtPoint {
443 PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
444 const ProgramPointTag *tag = nullptr)
445 : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { }
448 friend class ProgramPoint;
449 PreStmtPurgeDeadSymbols() {}
450 static bool isKind(const ProgramPoint &Location) {
451 return Location.getKind() == PreStmtPurgeDeadSymbolsKind;
455 /// Represents a point after we ran remove dead bindings AFTER
456 /// processing the given statement.
457 class PostStmtPurgeDeadSymbols : public StmtPoint {
459 PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
460 const ProgramPointTag *tag = nullptr)
461 : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { }
464 friend class ProgramPoint;
465 PostStmtPurgeDeadSymbols() {}
466 static bool isKind(const ProgramPoint &Location) {
467 return Location.getKind() == PostStmtPurgeDeadSymbolsKind;
471 class BlockEdge : public ProgramPoint {
473 BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
474 : ProgramPoint(B1, B2, BlockEdgeKind, L) {
475 assert(B1 && "BlockEdge: source block must be non-null");
476 assert(B2 && "BlockEdge: destination block must be non-null");
479 const CFGBlock *getSrc() const {
480 return static_cast<const CFGBlock*>(getData1());
483 const CFGBlock *getDst() const {
484 return static_cast<const CFGBlock*>(getData2());
488 friend class ProgramPoint;
490 static bool isKind(const ProgramPoint &Location) {
491 return Location.getKind() == BlockEdgeKind;
495 class PostInitializer : public ProgramPoint {
497 /// \brief Construct a PostInitializer point that represents a location after
498 /// CXXCtorInitializer expression evaluation.
500 /// \param I The initializer.
501 /// \param Loc The location of the field being initialized.
502 PostInitializer(const CXXCtorInitializer *I,
504 const LocationContext *L)
505 : ProgramPoint(I, Loc, PostInitializerKind, L) {}
507 const CXXCtorInitializer *getInitializer() const {
508 return static_cast<const CXXCtorInitializer *>(getData1());
511 /// \brief Returns the location of the field.
512 const void *getLocationValue() const {
517 friend class ProgramPoint;
519 static bool isKind(const ProgramPoint &Location) {
520 return Location.getKind() == PostInitializerKind;
524 /// Represents an implicit call event.
526 /// The nearest statement is provided for diagnostic purposes.
527 class ImplicitCallPoint : public ProgramPoint {
529 ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
530 const LocationContext *L, const ProgramPointTag *Tag)
531 : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
533 const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
534 SourceLocation getLocation() const {
535 return SourceLocation::getFromPtrEncoding(getData1());
539 ImplicitCallPoint() {}
541 friend class ProgramPoint;
542 static bool isKind(const ProgramPoint &Location) {
543 return Location.getKind() >= MinImplicitCallKind &&
544 Location.getKind() <= MaxImplicitCallKind;
548 /// Represents a program point just before an implicit call event.
550 /// Explicit calls will appear as PreStmt program points.
551 class PreImplicitCall : public ImplicitCallPoint {
553 PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
554 const ProgramPointTag *Tag = nullptr)
555 : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
558 friend class ProgramPoint;
560 static bool isKind(const ProgramPoint &Location) {
561 return Location.getKind() == PreImplicitCallKind;
565 /// Represents a program point just after an implicit call event.
567 /// Explicit calls will appear as PostStmt program points.
568 class PostImplicitCall : public ImplicitCallPoint {
570 PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
571 const ProgramPointTag *Tag = nullptr)
572 : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
575 friend class ProgramPoint;
576 PostImplicitCall() {}
577 static bool isKind(const ProgramPoint &Location) {
578 return Location.getKind() == PostImplicitCallKind;
582 /// Represents a point when we begin processing an inlined call.
583 /// CallEnter uses the caller's location context.
584 class CallEnter : public ProgramPoint {
586 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
587 const LocationContext *callerCtx)
588 : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {}
590 const Stmt *getCallExpr() const {
591 return static_cast<const Stmt *>(getData1());
594 const StackFrameContext *getCalleeContext() const {
595 return static_cast<const StackFrameContext *>(getData2());
599 friend class ProgramPoint;
601 static bool isKind(const ProgramPoint &Location) {
602 return Location.getKind() == CallEnterKind;
606 /// Represents a point when we start the call exit sequence (for inlined call).
608 /// The call exit is simulated with a sequence of nodes, which occur between
609 /// CallExitBegin and CallExitEnd. The following operations occur between the
610 /// two program points:
612 /// - Bind the return value
613 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
615 class CallExitBegin : public ProgramPoint {
617 // CallExitBegin uses the callee's location context.
618 CallExitBegin(const StackFrameContext *L)
619 : ProgramPoint(nullptr, CallExitBeginKind, L, nullptr) {}
622 friend class ProgramPoint;
624 static bool isKind(const ProgramPoint &Location) {
625 return Location.getKind() == CallExitBeginKind;
629 /// Represents a point when we finish the call exit sequence (for inlined call).
630 /// \sa CallExitBegin
631 class CallExitEnd : public ProgramPoint {
633 // CallExitEnd uses the caller's location context.
634 CallExitEnd(const StackFrameContext *CalleeCtx,
635 const LocationContext *CallerCtx)
636 : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {}
638 const StackFrameContext *getCalleeContext() const {
639 return static_cast<const StackFrameContext *>(getData1());
643 friend class ProgramPoint;
645 static bool isKind(const ProgramPoint &Location) {
646 return Location.getKind() == CallExitEndKind;
650 /// This is a meta program point, which should be skipped by all the diagnostic
652 class EpsilonPoint : public ProgramPoint {
654 EpsilonPoint(const LocationContext *L, const void *Data1,
655 const void *Data2 = nullptr,
656 const ProgramPointTag *tag = nullptr)
657 : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
659 const void *getData() const { return getData1(); }
662 friend class ProgramPoint;
664 static bool isKind(const ProgramPoint &Location) {
665 return Location.getKind() == EpsilonKind;
669 } // end namespace clang
672 namespace llvm { // Traits specialization for DenseMap
674 template <> struct DenseMapInfo<clang::ProgramPoint> {
676 static inline clang::ProgramPoint getEmptyKey() {
678 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
679 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
682 static inline clang::ProgramPoint getTombstoneKey() {
684 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
685 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
688 static unsigned getHashValue(const clang::ProgramPoint &Loc) {
689 return Loc.getHashValue();
692 static bool isEqual(const clang::ProgramPoint &L,
693 const clang::ProgramPoint &R) {
700 struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
702 } // end namespace llvm