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/AnalysisDeclContext.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 PostAllocatorCallKind,
77 MinPostStmtKind = PostStmtKind,
78 MaxPostStmtKind = PostAllocatorCallKind,
86 MinImplicitCallKind = PreImplicitCallKind,
87 MaxImplicitCallKind = PostImplicitCallKind,
93 llvm::PointerIntPair<const void *, 2, unsigned> Data2;
95 // The LocationContext could be NULL to allow ProgramPoint to be used in
96 // context insensitive analysis.
97 llvm::PointerIntPair<const LocationContext *, 2, unsigned> L;
99 llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
102 ProgramPoint() = default;
103 ProgramPoint(const void *P,
105 const LocationContext *l,
106 const ProgramPointTag *tag = nullptr)
108 Data2(nullptr, (((unsigned) k) >> 0) & 0x3),
109 L(l, (((unsigned) k) >> 2) & 0x3),
110 Tag(tag, (((unsigned) k) >> 4) & 0x3) {
111 assert(getKind() == k);
112 assert(getLocationContext() == l);
113 assert(getData1() == P);
116 ProgramPoint(const void *P1,
119 const LocationContext *l,
120 const ProgramPointTag *tag = nullptr)
122 Data2(P2, (((unsigned) k) >> 0) & 0x3),
123 L(l, (((unsigned) k) >> 2) & 0x3),
124 Tag(tag, (((unsigned) k) >> 4) & 0x3) {}
127 const void *getData1() const { return Data1; }
128 const void *getData2() const { return Data2.getPointer(); }
129 void setData2(const void *d) { Data2.setPointer(d); }
132 /// Create a new ProgramPoint object that is the same as the original
133 /// except for using the specified tag value.
134 ProgramPoint withTag(const ProgramPointTag *tag) const {
135 return ProgramPoint(getData1(), getData2(), getKind(),
136 getLocationContext(), tag);
139 /// Convert to the specified ProgramPoint type, asserting that this
140 /// ProgramPoint is of the desired type.
143 assert(T::isKind(*this));
145 ProgramPoint& PP = t;
150 /// Convert to the specified ProgramPoint type, returning None if this
151 /// ProgramPoint is not of the desired type.
153 Optional<T> getAs() const {
154 if (!T::isKind(*this))
157 ProgramPoint& PP = t;
162 Kind getKind() const {
163 unsigned x = Tag.getInt();
171 /// Is this a program point corresponding to purge/removal of dead
172 /// symbols and bindings.
175 return (K == PostStmtPurgeDeadSymbolsKind ||
176 K == PreStmtPurgeDeadSymbolsKind);
179 const ProgramPointTag *getTag() const { return Tag.getPointer(); }
181 const LocationContext *getLocationContext() const {
182 return L.getPointer();
185 const StackFrameContext *getStackFrame() const {
186 return getLocationContext()->getStackFrame();
189 // For use with DenseMap. This hash is probably slow.
190 unsigned getHashValue() const {
191 llvm::FoldingSetNodeID ID;
193 return ID.ComputeHash();
196 bool operator==(const ProgramPoint & RHS) const {
197 return Data1 == RHS.Data1 &&
198 Data2 == RHS.Data2 &&
203 bool operator!=(const ProgramPoint &RHS) const {
204 return Data1 != RHS.Data1 ||
205 Data2 != RHS.Data2 ||
210 void Profile(llvm::FoldingSetNodeID& ID) const {
211 ID.AddInteger((unsigned) getKind());
212 ID.AddPointer(getData1());
213 ID.AddPointer(getData2());
214 ID.AddPointer(getLocationContext());
215 ID.AddPointer(getTag());
218 void print(StringRef CR, llvm::raw_ostream &Out) const;
220 LLVM_DUMP_METHOD void dump() const;
222 static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
223 const LocationContext *LC,
224 const ProgramPointTag *tag);
227 class BlockEntrance : public ProgramPoint {
229 BlockEntrance(const CFGBlock *B, const LocationContext *L,
230 const ProgramPointTag *tag = nullptr)
231 : ProgramPoint(B, BlockEntranceKind, L, tag) {
232 assert(B && "BlockEntrance requires non-null block");
235 const CFGBlock *getBlock() const {
236 return reinterpret_cast<const CFGBlock*>(getData1());
239 Optional<CFGElement> getFirstElement() const {
240 const CFGBlock *B = getBlock();
241 return B->empty() ? Optional<CFGElement>() : B->front();
245 friend class ProgramPoint;
246 BlockEntrance() = default;
247 static bool isKind(const ProgramPoint &Location) {
248 return Location.getKind() == BlockEntranceKind;
252 class BlockExit : public ProgramPoint {
254 BlockExit(const CFGBlock *B, const LocationContext *L)
255 : ProgramPoint(B, BlockExitKind, L) {}
257 const CFGBlock *getBlock() const {
258 return reinterpret_cast<const CFGBlock*>(getData1());
261 const Stmt *getTerminator() const {
262 return getBlock()->getTerminator();
266 friend class ProgramPoint;
267 BlockExit() = default;
268 static bool isKind(const ProgramPoint &Location) {
269 return Location.getKind() == BlockExitKind;
273 class StmtPoint : public ProgramPoint {
275 StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
276 const ProgramPointTag *tag)
277 : ProgramPoint(S, p2, k, L, tag) {
281 const Stmt *getStmt() const { return (const Stmt*) getData1(); }
283 template <typename T>
284 const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
287 StmtPoint() = default;
289 friend class ProgramPoint;
290 static bool isKind(const ProgramPoint &Location) {
291 unsigned k = Location.getKind();
292 return k >= PreStmtKind && k <= MaxPostStmtKind;
297 class PreStmt : public StmtPoint {
299 PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
300 const Stmt *SubStmt = nullptr)
301 : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
303 const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
306 friend class ProgramPoint;
308 static bool isKind(const ProgramPoint &Location) {
309 return Location.getKind() == PreStmtKind;
313 class PostStmt : public StmtPoint {
315 PostStmt() = default;
316 PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
317 const ProgramPointTag *tag = nullptr)
318 : StmtPoint(S, data, k, L, tag) {}
321 explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L,
322 const ProgramPointTag *tag = nullptr)
323 : StmtPoint(S, nullptr, k, L, tag) {}
325 explicit PostStmt(const Stmt *S, const LocationContext *L,
326 const ProgramPointTag *tag = nullptr)
327 : StmtPoint(S, nullptr, PostStmtKind, L, tag) {}
330 friend class ProgramPoint;
331 static bool isKind(const ProgramPoint &Location) {
332 unsigned k = Location.getKind();
333 return k >= MinPostStmtKind && k <= MaxPostStmtKind;
337 class FunctionExitPoint : public ProgramPoint {
339 explicit FunctionExitPoint(const ReturnStmt *S,
340 const LocationContext *LC,
341 const ProgramPointTag *tag = nullptr)
342 : ProgramPoint(S, FunctionExitKind, LC, tag) {}
344 const CFGBlock *getBlock() const {
345 return &getLocationContext()->getCFG()->getExit();
348 const ReturnStmt *getStmt() const {
349 return reinterpret_cast<const ReturnStmt *>(getData1());
353 friend class ProgramPoint;
354 FunctionExitPoint() = default;
355 static bool isKind(const ProgramPoint &Location) {
356 return Location.getKind() == FunctionExitKind;
360 // PostCondition represents the post program point of a branch condition.
361 class PostCondition : public PostStmt {
363 PostCondition(const Stmt *S, const LocationContext *L,
364 const ProgramPointTag *tag = nullptr)
365 : PostStmt(S, PostConditionKind, L, tag) {}
368 friend class ProgramPoint;
369 PostCondition() = default;
370 static bool isKind(const ProgramPoint &Location) {
371 return Location.getKind() == PostConditionKind;
375 class LocationCheck : public StmtPoint {
377 LocationCheck() = default;
378 LocationCheck(const Stmt *S, const LocationContext *L,
379 ProgramPoint::Kind K, const ProgramPointTag *tag)
380 : StmtPoint(S, nullptr, K, L, tag) {}
383 friend class ProgramPoint;
384 static bool isKind(const ProgramPoint &location) {
385 unsigned k = location.getKind();
386 return k == PreLoadKind || k == PreStoreKind;
390 class PreLoad : public LocationCheck {
392 PreLoad(const Stmt *S, const LocationContext *L,
393 const ProgramPointTag *tag = nullptr)
394 : LocationCheck(S, L, PreLoadKind, tag) {}
397 friend class ProgramPoint;
399 static bool isKind(const ProgramPoint &location) {
400 return location.getKind() == PreLoadKind;
404 class PreStore : public LocationCheck {
406 PreStore(const Stmt *S, const LocationContext *L,
407 const ProgramPointTag *tag = nullptr)
408 : LocationCheck(S, L, PreStoreKind, tag) {}
411 friend class ProgramPoint;
412 PreStore() = default;
413 static bool isKind(const ProgramPoint &location) {
414 return location.getKind() == PreStoreKind;
418 class PostLoad : public PostStmt {
420 PostLoad(const Stmt *S, const LocationContext *L,
421 const ProgramPointTag *tag = nullptr)
422 : PostStmt(S, PostLoadKind, L, tag) {}
425 friend class ProgramPoint;
426 PostLoad() = default;
427 static bool isKind(const ProgramPoint &Location) {
428 return Location.getKind() == PostLoadKind;
432 /// Represents a program point after a store evaluation.
433 class PostStore : public PostStmt {
435 /// Construct the post store point.
436 /// \param Loc can be used to store the information about the location
437 /// used in the form it was uttered in the code.
438 PostStore(const Stmt *S, const LocationContext *L, const void *Loc,
439 const ProgramPointTag *tag = nullptr)
440 : PostStmt(S, PostStoreKind, L, tag) {
441 assert(getData2() == nullptr);
445 /// Returns the information about the location used in the store,
446 /// how it was uttered in the code.
447 const void *getLocationValue() const {
452 friend class ProgramPoint;
453 PostStore() = default;
454 static bool isKind(const ProgramPoint &Location) {
455 return Location.getKind() == PostStoreKind;
459 class PostLValue : public PostStmt {
461 PostLValue(const Stmt *S, const LocationContext *L,
462 const ProgramPointTag *tag = nullptr)
463 : PostStmt(S, PostLValueKind, L, tag) {}
466 friend class ProgramPoint;
467 PostLValue() = default;
468 static bool isKind(const ProgramPoint &Location) {
469 return Location.getKind() == PostLValueKind;
473 /// Represents a point after we ran remove dead bindings BEFORE
474 /// processing the given statement.
475 class PreStmtPurgeDeadSymbols : public StmtPoint {
477 PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
478 const ProgramPointTag *tag = nullptr)
479 : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { }
482 friend class ProgramPoint;
483 PreStmtPurgeDeadSymbols() = default;
484 static bool isKind(const ProgramPoint &Location) {
485 return Location.getKind() == PreStmtPurgeDeadSymbolsKind;
489 /// Represents a point after we ran remove dead bindings AFTER
490 /// processing the given statement.
491 class PostStmtPurgeDeadSymbols : public StmtPoint {
493 PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
494 const ProgramPointTag *tag = nullptr)
495 : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { }
498 friend class ProgramPoint;
499 PostStmtPurgeDeadSymbols() = default;
500 static bool isKind(const ProgramPoint &Location) {
501 return Location.getKind() == PostStmtPurgeDeadSymbolsKind;
505 class BlockEdge : public ProgramPoint {
507 BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
508 : ProgramPoint(B1, B2, BlockEdgeKind, L) {
509 assert(B1 && "BlockEdge: source block must be non-null");
510 assert(B2 && "BlockEdge: destination block must be non-null");
513 const CFGBlock *getSrc() const {
514 return static_cast<const CFGBlock*>(getData1());
517 const CFGBlock *getDst() const {
518 return static_cast<const CFGBlock*>(getData2());
522 friend class ProgramPoint;
523 BlockEdge() = default;
524 static bool isKind(const ProgramPoint &Location) {
525 return Location.getKind() == BlockEdgeKind;
529 class PostInitializer : public ProgramPoint {
531 /// Construct a PostInitializer point that represents a location after
532 /// CXXCtorInitializer expression evaluation.
534 /// \param I The initializer.
535 /// \param Loc The location of the field being initialized.
536 PostInitializer(const CXXCtorInitializer *I,
538 const LocationContext *L)
539 : ProgramPoint(I, Loc, PostInitializerKind, L) {}
541 const CXXCtorInitializer *getInitializer() const {
542 return static_cast<const CXXCtorInitializer *>(getData1());
545 /// Returns the location of the field.
546 const void *getLocationValue() const {
551 friend class ProgramPoint;
552 PostInitializer() = default;
553 static bool isKind(const ProgramPoint &Location) {
554 return Location.getKind() == PostInitializerKind;
558 /// Represents an implicit call event.
560 /// The nearest statement is provided for diagnostic purposes.
561 class ImplicitCallPoint : public ProgramPoint {
563 ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
564 const LocationContext *L, const ProgramPointTag *Tag)
565 : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
567 const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
568 SourceLocation getLocation() const {
569 return SourceLocation::getFromPtrEncoding(getData1());
573 ImplicitCallPoint() = default;
575 friend class ProgramPoint;
576 static bool isKind(const ProgramPoint &Location) {
577 return Location.getKind() >= MinImplicitCallKind &&
578 Location.getKind() <= MaxImplicitCallKind;
582 /// Represents a program point just before an implicit call event.
584 /// Explicit calls will appear as PreStmt program points.
585 class PreImplicitCall : public ImplicitCallPoint {
587 PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
588 const ProgramPointTag *Tag = nullptr)
589 : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
592 friend class ProgramPoint;
593 PreImplicitCall() = default;
594 static bool isKind(const ProgramPoint &Location) {
595 return Location.getKind() == PreImplicitCallKind;
599 /// Represents a program point just after an implicit call event.
601 /// Explicit calls will appear as PostStmt program points.
602 class PostImplicitCall : public ImplicitCallPoint {
604 PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
605 const ProgramPointTag *Tag = nullptr)
606 : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
609 friend class ProgramPoint;
610 PostImplicitCall() = default;
611 static bool isKind(const ProgramPoint &Location) {
612 return Location.getKind() == PostImplicitCallKind;
616 class PostAllocatorCall : public StmtPoint {
618 PostAllocatorCall(const Stmt *S, const LocationContext *L,
619 const ProgramPointTag *Tag = nullptr)
620 : StmtPoint(S, nullptr, PostAllocatorCallKind, L, Tag) {}
623 friend class ProgramPoint;
624 PostAllocatorCall() = default;
625 static bool isKind(const ProgramPoint &Location) {
626 return Location.getKind() == PostAllocatorCallKind;
630 /// Represents a point when we begin processing an inlined call.
631 /// CallEnter uses the caller's location context.
632 class CallEnter : public ProgramPoint {
634 CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
635 const LocationContext *callerCtx)
636 : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {}
638 const Stmt *getCallExpr() const {
639 return static_cast<const Stmt *>(getData1());
642 const StackFrameContext *getCalleeContext() const {
643 return static_cast<const StackFrameContext *>(getData2());
646 /// Returns the entry block in the CFG for the entered function.
647 const CFGBlock *getEntry() const {
648 const StackFrameContext *CalleeCtx = getCalleeContext();
649 const CFG *CalleeCFG = CalleeCtx->getCFG();
650 return &(CalleeCFG->getEntry());
654 friend class ProgramPoint;
655 CallEnter() = default;
656 static bool isKind(const ProgramPoint &Location) {
657 return Location.getKind() == CallEnterKind;
661 /// Represents a point when we start the call exit sequence (for inlined call).
663 /// The call exit is simulated with a sequence of nodes, which occur between
664 /// CallExitBegin and CallExitEnd. The following operations occur between the
665 /// two program points:
667 /// - Bind the return value
668 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
670 class CallExitBegin : public ProgramPoint {
672 // CallExitBegin uses the callee's location context.
673 CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS)
674 : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { }
676 const ReturnStmt *getReturnStmt() const {
677 return static_cast<const ReturnStmt *>(getData1());
681 friend class ProgramPoint;
682 CallExitBegin() = default;
683 static bool isKind(const ProgramPoint &Location) {
684 return Location.getKind() == CallExitBeginKind;
688 /// Represents a point when we finish the call exit sequence (for inlined call).
689 /// \sa CallExitBegin
690 class CallExitEnd : public ProgramPoint {
692 // CallExitEnd uses the caller's location context.
693 CallExitEnd(const StackFrameContext *CalleeCtx,
694 const LocationContext *CallerCtx)
695 : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {}
697 const StackFrameContext *getCalleeContext() const {
698 return static_cast<const StackFrameContext *>(getData1());
702 friend class ProgramPoint;
703 CallExitEnd() = default;
704 static bool isKind(const ProgramPoint &Location) {
705 return Location.getKind() == CallExitEndKind;
709 /// Represents a point when we exit a loop.
710 /// When this ProgramPoint is encountered we can be sure that the symbolic
711 /// execution of the corresponding LoopStmt is finished on the given path.
712 /// Note: It is possible to encounter a LoopExit element when we haven't even
713 /// encountered the loop itself. At the current state not all loop exits will
714 /// result in a LoopExit program point.
715 class LoopExit : public ProgramPoint {
717 LoopExit(const Stmt *LoopStmt, const LocationContext *LC)
718 : ProgramPoint(LoopStmt, nullptr, LoopExitKind, LC) {}
720 const Stmt *getLoopStmt() const {
721 return static_cast<const Stmt *>(getData1());
725 friend class ProgramPoint;
726 LoopExit() = default;
727 static bool isKind(const ProgramPoint &Location) {
728 return Location.getKind() == LoopExitKind;
732 /// This is a meta program point, which should be skipped by all the diagnostic
734 class EpsilonPoint : public ProgramPoint {
736 EpsilonPoint(const LocationContext *L, const void *Data1,
737 const void *Data2 = nullptr,
738 const ProgramPointTag *tag = nullptr)
739 : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
741 const void *getData() const { return getData1(); }
744 friend class ProgramPoint;
745 EpsilonPoint() = default;
746 static bool isKind(const ProgramPoint &Location) {
747 return Location.getKind() == EpsilonKind;
751 } // end namespace clang
754 namespace llvm { // Traits specialization for DenseMap
756 template <> struct DenseMapInfo<clang::ProgramPoint> {
758 static inline clang::ProgramPoint getEmptyKey() {
760 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
761 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
764 static inline clang::ProgramPoint getTombstoneKey() {
766 reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
767 return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
770 static unsigned getHashValue(const clang::ProgramPoint &Loc) {
771 return Loc.getHashValue();
774 static bool isEqual(const clang::ProgramPoint &L,
775 const clang::ProgramPoint &R) {
782 struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
784 } // end namespace llvm