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_PROGRAM_POINT
16 #define LLVM_CLANG_ANALYSIS_PROGRAM_POINT
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;
36 class ProgramPointTag;
40 enum Kind { BlockEdgeKind,
44 PreStmtPurgeDeadSymbolsKind,
45 PostStmtPurgeDeadSymbolsKind,
53 MinPostStmtKind = PostStmtKind,
54 MaxPostStmtKind = PostLValueKind,
61 MinImplicitCallKind = PreImplicitCallKind,
62 MaxImplicitCallKind = PostImplicitCallKind,
67 llvm::PointerIntPair<const void *, 2, unsigned> Data2;
69 // The LocationContext could be NULL to allow ProgramPoint to be used in
70 // context insensitive analysis.
71 llvm::PointerIntPair<const LocationContext *, 2, unsigned> L;
73 llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
77 ProgramPoint(const void *P,
79 const LocationContext *l,
80 const ProgramPointTag *tag = 0)
82 Data2(0, (((unsigned) k) >> 0) & 0x3),
83 L(l, (((unsigned) k) >> 2) & 0x3),
84 Tag(tag, (((unsigned) k) >> 4) & 0x3) {
85 assert(getKind() == k);
86 assert(getLocationContext() == l);
87 assert(getData1() == P);
90 ProgramPoint(const void *P1,
93 const LocationContext *l,
94 const ProgramPointTag *tag = 0)
96 Data2(P2, (((unsigned) k) >> 0) & 0x3),
97 L(l, (((unsigned) k) >> 2) & 0x3),
98 Tag(tag, (((unsigned) k) >> 4) & 0x3) {}
101 const void *getData1() const { return Data1; }
102 const void *getData2() const { return Data2.getPointer(); }
103 void setData2(const void *d) { Data2.setPointer(d); }
106 /// Create a new ProgramPoint object that is the same as the original
107 /// except for using the specified tag value.
108 ProgramPoint withTag(const ProgramPointTag *tag) const {
109 return ProgramPoint(getData1(), getData2(), getKind(),
110 getLocationContext(), tag);
113 /// \brief Convert to the specified ProgramPoint type, asserting that this
114 /// ProgramPoint is of the desired type.
117 assert(T::isKind(*this));
119 ProgramPoint& PP = t;
124 /// \brief Convert to the specified ProgramPoint type, returning None if this
125 /// ProgramPoint is not of the desired type.
127 Optional<T> getAs() const {
128 if (!T::isKind(*this))
131 ProgramPoint& PP = t;
136 Kind getKind() const {
137 unsigned x = Tag.getInt();
145 /// \brief Is this a program point corresponding to purge/removal of dead
146 /// symbols and bindings.
149 return (K == PostStmtPurgeDeadSymbolsKind ||
150 K == PreStmtPurgeDeadSymbolsKind);
153 const ProgramPointTag *getTag() const { return Tag.getPointer(); }
155 const LocationContext *getLocationContext() const {
156 return L.getPointer();
159 // For use with DenseMap. This hash is probably slow.
160 unsigned getHashValue() const {
161 llvm::FoldingSetNodeID ID;
163 return ID.ComputeHash();
166 bool operator==(const ProgramPoint & RHS) const {
167 return Data1 == RHS.Data1 &&
168 Data2 == RHS.Data2 &&
173 bool operator!=(const ProgramPoint &RHS) const {
174 return Data1 != RHS.Data1 ||
175 Data2 != RHS.Data2 ||
180 void Profile(llvm::FoldingSetNodeID& ID) const {
181 ID.AddInteger((unsigned) getKind());
182 ID.AddPointer(getData1());
183 ID.AddPointer(getData2());
184 ID.AddPointer(getLocationContext());
185 ID.AddPointer(getTag());
188 static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
189 const LocationContext *LC,
190 const ProgramPointTag *tag);
193 class BlockEntrance : public ProgramPoint {
195 BlockEntrance(const CFGBlock *B, const LocationContext *L,
196 const ProgramPointTag *tag = 0)
197 : ProgramPoint(B, BlockEntranceKind, L, tag) {
198 assert(B && "BlockEntrance requires non-null block");
201 const CFGBlock *getBlock() const {
202 return reinterpret_cast<const CFGBlock*>(getData1());
205 Optional<CFGElement> getFirstElement() const {
206 const CFGBlock *B = getBlock();
207 return B->empty() ? Optional<CFGElement>() : B->front();
211 friend class ProgramPoint;
213 static bool isKind(const ProgramPoint &Location) {
214 return Location.getKind() == BlockEntranceKind;
218 class BlockExit : public ProgramPoint {
220 BlockExit(const CFGBlock *B, const LocationContext *L)
221 : ProgramPoint(B, BlockExitKind, L) {}
223 const CFGBlock *getBlock() const {
224 return reinterpret_cast<const CFGBlock*>(getData1());
227 const Stmt *getTerminator() const {
228 return getBlock()->getTerminator();
232 friend class ProgramPoint;
234 static bool isKind(const ProgramPoint &Location) {
235 return Location.getKind() == BlockExitKind;
239 class StmtPoint : public ProgramPoint {
241 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
242 const ProgramPointTag *tag)
243 : ProgramPoint(S, p2, k, L, tag) {
247 const Stmt *getStmt() const { return (const Stmt*) getData1(); }
249 template <typename T>
250 const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
255 friend class ProgramPoint;
256 static bool isKind(const ProgramPoint &Location) {
257 unsigned k = Location.getKind();
258 return k >= PreStmtKind && k <= MaxPostStmtKind;
263 class PreStmt : public StmtPoint {
265 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
266 const Stmt *SubStmt = 0)
267 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
269 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
272 friend class ProgramPoint;
274 static bool isKind(const ProgramPoint &Location) {
275 return Location.getKind() == PreStmtKind;
279 class PostStmt : public StmtPoint {
282 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
283 const ProgramPointTag *tag = 0)
284 : StmtPoint(S, data, k, L, tag) {}
287 explicit PostStmt(const Stmt *S, Kind k,
288 const LocationContext *L, const ProgramPointTag *tag = 0)
289 : StmtPoint(S, NULL, k, L, tag) {}
291 explicit PostStmt(const Stmt *S, const LocationContext *L,
292 const ProgramPointTag *tag = 0)
293 : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
296 friend class ProgramPoint;
297 static bool isKind(const ProgramPoint &Location) {
298 unsigned k = Location.getKind();
299 return k >= MinPostStmtKind && k <= MaxPostStmtKind;
303 // PostCondition represents the post program point of a branch condition.
304 class PostCondition : public PostStmt {
306 PostCondition(const Stmt *S, const LocationContext *L,
307 const ProgramPointTag *tag = 0)
308 : PostStmt(S, PostConditionKind, L, tag) {}
311 friend class ProgramPoint;
313 static bool isKind(const ProgramPoint &Location) {
314 return Location.getKind() == PostConditionKind;
318 class LocationCheck : public StmtPoint {
321 LocationCheck(const Stmt *S, const LocationContext *L,
322 ProgramPoint::Kind K, const ProgramPointTag *tag)
323 : StmtPoint(S, NULL, K, L, tag) {}
326 friend class ProgramPoint;
327 static bool isKind(const ProgramPoint &location) {
328 unsigned k = location.getKind();
329 return k == PreLoadKind || k == PreStoreKind;
333 class PreLoad : public LocationCheck {
335 PreLoad(const Stmt *S, const LocationContext *L,
336 const ProgramPointTag *tag = 0)
337 : LocationCheck(S, L, PreLoadKind, tag) {}
340 friend class ProgramPoint;
342 static bool isKind(const ProgramPoint &location) {
343 return location.getKind() == PreLoadKind;
347 class PreStore : public LocationCheck {
349 PreStore(const Stmt *S, const LocationContext *L,
350 const ProgramPointTag *tag = 0)
351 : LocationCheck(S, L, PreStoreKind, tag) {}
354 friend class ProgramPoint;
356 static bool isKind(const ProgramPoint &location) {
357 return location.getKind() == PreStoreKind;
361 class PostLoad : public PostStmt {
363 PostLoad(const Stmt *S, const LocationContext *L,
364 const ProgramPointTag *tag = 0)
365 : PostStmt(S, PostLoadKind, L, tag) {}
368 friend class ProgramPoint;
370 static bool isKind(const ProgramPoint &Location) {
371 return Location.getKind() == PostLoadKind;
375 /// \brief Represents a program point after a store evaluation.
376 class PostStore : public PostStmt {
378 /// Construct the post store point.
379 /// \param Loc can be used to store the information about the location
380 /// used in the form it was uttered in the code.
381 PostStore(const Stmt *S, const LocationContext *L, const void *Loc,
382 const ProgramPointTag *tag = 0)
383 : PostStmt(S, PostStoreKind, L, tag) {
384 assert(getData2() == 0);
388 /// \brief Returns the information about the location used in the store,
389 /// how it was uttered in the code.
390 const void *getLocationValue() const {
395 friend class ProgramPoint;
397 static bool isKind(const ProgramPoint &Location) {
398 return Location.getKind() == PostStoreKind;
402 class PostLValue : public PostStmt {
404 PostLValue(const Stmt *S, const LocationContext *L,
405 const ProgramPointTag *tag = 0)
406 : PostStmt(S, PostLValueKind, L, tag) {}
409 friend class ProgramPoint;
411 static bool isKind(const ProgramPoint &Location) {
412 return Location.getKind() == PostLValueKind;
416 /// Represents a point after we ran remove dead bindings BEFORE
417 /// processing the given statement.
418 class PreStmtPurgeDeadSymbols : public StmtPoint {
420 PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
421 const ProgramPointTag *tag = 0)
422 : StmtPoint(S, 0, PreStmtPurgeDeadSymbolsKind, L, tag) { }
425 friend class ProgramPoint;
426 PreStmtPurgeDeadSymbols() {}
427 static bool isKind(const ProgramPoint &Location) {
428 return Location.getKind() == PreStmtPurgeDeadSymbolsKind;
432 /// Represents a point after we ran remove dead bindings AFTER
433 /// processing the given statement.
434 class PostStmtPurgeDeadSymbols : public StmtPoint {
436 PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
437 const ProgramPointTag *tag = 0)
438 : StmtPoint(S, 0, PostStmtPurgeDeadSymbolsKind, L, tag) { }
441 friend class ProgramPoint;
442 PostStmtPurgeDeadSymbols() {}
443 static bool isKind(const ProgramPoint &Location) {
444 return Location.getKind() == PostStmtPurgeDeadSymbolsKind;
448 class BlockEdge : public ProgramPoint {
450 BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
451 : ProgramPoint(B1, B2, BlockEdgeKind, L) {
452 assert(B1 && "BlockEdge: source block must be non-null");
453 assert(B2 && "BlockEdge: destination block must be non-null");
456 const CFGBlock *getSrc() const {
457 return static_cast<const CFGBlock*>(getData1());
460 const CFGBlock *getDst() const {
461 return static_cast<const CFGBlock*>(getData2());
465 friend class ProgramPoint;
467 static bool isKind(const ProgramPoint &Location) {
468 return Location.getKind() == BlockEdgeKind;
472 class PostInitializer : public ProgramPoint {
474 /// \brief Construct a PostInitializer point that represents a location after
475 /// CXXCtorInitializer expression evaluation.
477 /// \param I The initializer.
478 /// \param Loc The location of the field being initialized.
479 PostInitializer(const CXXCtorInitializer *I,
481 const LocationContext *L)
482 : ProgramPoint(I, Loc, PostInitializerKind, L) {}
484 const CXXCtorInitializer *getInitializer() const {
485 return static_cast<const CXXCtorInitializer *>(getData1());
488 /// \brief Returns the location of the field.
489 const void *getLocationValue() const {
494 friend class ProgramPoint;
496 static bool isKind(const ProgramPoint &Location) {
497 return Location.getKind() == PostInitializerKind;
501 /// Represents an implicit call event.
503 /// The nearest statement is provided for diagnostic purposes.
504 class ImplicitCallPoint : public ProgramPoint {
506 ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
507 const LocationContext *L, const ProgramPointTag *Tag)
508 : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
510 const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
511 SourceLocation getLocation() const {
512 return SourceLocation::getFromPtrEncoding(getData1());
516 ImplicitCallPoint() {}
518 friend class ProgramPoint;
519 static bool isKind(const ProgramPoint &Location) {
520 return Location.getKind() >= MinImplicitCallKind &&
521 Location.getKind() <= MaxImplicitCallKind;
525 /// Represents a program point just before an implicit call event.
527 /// Explicit calls will appear as PreStmt program points.
528 class PreImplicitCall : public ImplicitCallPoint {
530 PreImplicitCall(const Decl *D, SourceLocation Loc,
531 const LocationContext *L, const ProgramPointTag *Tag = 0)
532 : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
535 friend class ProgramPoint;
537 static bool isKind(const ProgramPoint &Location) {
538 return Location.getKind() == PreImplicitCallKind;
542 /// Represents a program point just after an implicit call event.
544 /// Explicit calls will appear as PostStmt program points.
545 class PostImplicitCall : public ImplicitCallPoint {
547 PostImplicitCall(const Decl *D, SourceLocation Loc,
548 const LocationContext *L, const ProgramPointTag *Tag = 0)
549 : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
552 friend class ProgramPoint;
553 PostImplicitCall() {}
554 static bool isKind(const ProgramPoint &Location) {
555 return Location.getKind() == PostImplicitCallKind;
559 /// Represents a point when we begin processing an inlined call.
560 /// CallEnter uses the caller's location context.
561 class CallEnter : public ProgramPoint {
563 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
564 const LocationContext *callerCtx)
565 : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {}
567 const Stmt *getCallExpr() const {
568 return static_cast<const Stmt *>(getData1());
571 const StackFrameContext *getCalleeContext() const {
572 return static_cast<const StackFrameContext *>(getData2());
576 friend class ProgramPoint;
578 static bool isKind(const ProgramPoint &Location) {
579 return Location.getKind() == CallEnterKind;
583 /// Represents a point when we start the call exit sequence (for inlined call).
585 /// The call exit is simulated with a sequence of nodes, which occur between
586 /// CallExitBegin and CallExitEnd. The following operations occur between the
587 /// two program points:
589 /// - Bind the return value
590 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
592 class CallExitBegin : public ProgramPoint {
594 // CallExitBegin uses the callee's location context.
595 CallExitBegin(const StackFrameContext *L)
596 : ProgramPoint(0, CallExitBeginKind, L, 0) {}
599 friend class ProgramPoint;
601 static bool isKind(const ProgramPoint &Location) {
602 return Location.getKind() == CallExitBeginKind;
606 /// Represents a point when we finish the call exit sequence (for inlined call).
607 /// \sa CallExitBegin
608 class CallExitEnd : public ProgramPoint {
610 // CallExitEnd uses the caller's location context.
611 CallExitEnd(const StackFrameContext *CalleeCtx,
612 const LocationContext *CallerCtx)
613 : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, 0) {}
615 const StackFrameContext *getCalleeContext() const {
616 return static_cast<const StackFrameContext *>(getData1());
620 friend class ProgramPoint;
622 static bool isKind(const ProgramPoint &Location) {
623 return Location.getKind() == CallExitEndKind;
627 /// This is a meta program point, which should be skipped by all the diagnostic
629 class EpsilonPoint : public ProgramPoint {
631 EpsilonPoint(const LocationContext *L, const void *Data1,
632 const void *Data2 = 0, const ProgramPointTag *tag = 0)
633 : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
635 const void *getData() const { return getData1(); }
638 friend class ProgramPoint;
640 static bool isKind(const ProgramPoint &Location) {
641 return Location.getKind() == EpsilonKind;
645 /// ProgramPoints can be "tagged" as representing points specific to a given
646 /// analysis entity. Tags are abstract annotations, with an associated
647 /// description and potentially other information.
648 class ProgramPointTag {
650 ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {}
651 virtual ~ProgramPointTag();
652 virtual StringRef getTagDescription() const = 0;
655 /// Used to implement 'isKind' in subclasses.
656 const void *getTagKind() { return TagKind; }
662 class SimpleProgramPointTag : public ProgramPointTag {
665 SimpleProgramPointTag(StringRef description);
666 StringRef getTagDescription() const;
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), 0);
682 static inline clang::ProgramPoint getTombstoneKey() {
684 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
685 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
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