1 //==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file defines the interface ProgramPoint, which identifies a
11 //  distinct location in a function.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
16 #define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
17 
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"
27 #include <cassert>
28 #include <string>
29 #include <utility>
30 
31 namespace clang {
32 
33 class AnalysisDeclContext;
34 class FunctionDecl;
35 class LocationContext;
36 
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 {
41 public:
TagKind(tagKind)42   ProgramPointTag(void *tagKind = nullptr) : TagKind(tagKind) {}
43   virtual ~ProgramPointTag();
44   virtual StringRef getTagDescription() const = 0;
45 
46 protected:
47   /// Used to implement 'isKind' in subclasses.
getTagKind()48   const void *getTagKind() { return TagKind; }
49 
50 private:
51   const void *TagKind;
52 };
53 
54 class SimpleProgramPointTag : public ProgramPointTag {
55   std::string Desc;
56 public:
57   SimpleProgramPointTag(StringRef MsgProvider, StringRef Msg);
58   StringRef getTagDescription() const override;
59 };
60 
61 class ProgramPoint {
62 public:
63   enum Kind { BlockEdgeKind,
64               BlockEntranceKind,
65               BlockExitKind,
66               PreStmtKind,
67               PreStmtPurgeDeadSymbolsKind,
68               PostStmtPurgeDeadSymbolsKind,
69               PostStmtKind,
70               PreLoadKind,
71               PostLoadKind,
72               PreStoreKind,
73               PostStoreKind,
74               PostConditionKind,
75               PostLValueKind,
76               PostAllocatorCallKind,
77               MinPostStmtKind = PostStmtKind,
78               MaxPostStmtKind = PostAllocatorCallKind,
79               PostInitializerKind,
80               CallEnterKind,
81               CallExitBeginKind,
82               CallExitEndKind,
83               FunctionExitKind,
84               PreImplicitCallKind,
85               PostImplicitCallKind,
86               MinImplicitCallKind = PreImplicitCallKind,
87               MaxImplicitCallKind = PostImplicitCallKind,
88               LoopExitKind,
89               EpsilonKind};
90 
91 private:
92   const void *Data1;
93   llvm::PointerIntPair<const void *, 2, unsigned> Data2;
94 
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;
98 
99   llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
100 
101 protected:
102   ProgramPoint() = default;
103   ProgramPoint(const void *P,
104                Kind k,
105                const LocationContext *l,
106                const ProgramPointTag *tag = nullptr)
Data1(P)107     : Data1(P),
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);
114       }
115 
116   ProgramPoint(const void *P1,
117                const void *P2,
118                Kind k,
119                const LocationContext *l,
120                const ProgramPointTag *tag = nullptr)
Data1(P1)121     : Data1(P1),
122       Data2(P2, (((unsigned) k) >> 0) & 0x3),
123       L(l, (((unsigned) k) >> 2) & 0x3),
124       Tag(tag, (((unsigned) k) >> 4) & 0x3) {}
125 
126 protected:
getData1()127   const void *getData1() const { return Data1; }
getData2()128   const void *getData2() const { return Data2.getPointer(); }
setData2(const void * d)129   void setData2(const void *d) { Data2.setPointer(d); }
130 
131 public:
132   /// Create a new ProgramPoint object that is the same as the original
133   /// except for using the specified tag value.
withTag(const ProgramPointTag * tag)134   ProgramPoint withTag(const ProgramPointTag *tag) const {
135     return ProgramPoint(getData1(), getData2(), getKind(),
136                         getLocationContext(), tag);
137   }
138 
139   /// Convert to the specified ProgramPoint type, asserting that this
140   /// ProgramPoint is of the desired type.
141   template<typename T>
castAs()142   T castAs() const {
143     assert(T::isKind(*this));
144     T t;
145     ProgramPoint& PP = t;
146     PP = *this;
147     return t;
148   }
149 
150   /// Convert to the specified ProgramPoint type, returning None if this
151   /// ProgramPoint is not of the desired type.
152   template<typename T>
getAs()153   Optional<T> getAs() const {
154     if (!T::isKind(*this))
155       return None;
156     T t;
157     ProgramPoint& PP = t;
158     PP = *this;
159     return t;
160   }
161 
getKind()162   Kind getKind() const {
163     unsigned x = Tag.getInt();
164     x <<= 2;
165     x |= L.getInt();
166     x <<= 2;
167     x |= Data2.getInt();
168     return (Kind) x;
169   }
170 
171   /// Is this a program point corresponding to purge/removal of dead
172   /// symbols and bindings.
isPurgeKind()173   bool isPurgeKind() {
174     Kind K = getKind();
175     return (K == PostStmtPurgeDeadSymbolsKind ||
176             K == PreStmtPurgeDeadSymbolsKind);
177   }
178 
getTag()179   const ProgramPointTag *getTag() const { return Tag.getPointer(); }
180 
getLocationContext()181   const LocationContext *getLocationContext() const {
182     return L.getPointer();
183   }
184 
getStackFrame()185   const StackFrameContext *getStackFrame() const {
186     return getLocationContext()->getStackFrame();
187   }
188 
189   // For use with DenseMap.  This hash is probably slow.
getHashValue()190   unsigned getHashValue() const {
191     llvm::FoldingSetNodeID ID;
192     Profile(ID);
193     return ID.ComputeHash();
194   }
195 
196   bool operator==(const ProgramPoint & RHS) const {
197     return Data1 == RHS.Data1 &&
198            Data2 == RHS.Data2 &&
199            L == RHS.L &&
200            Tag == RHS.Tag;
201   }
202 
203   bool operator!=(const ProgramPoint &RHS) const {
204     return Data1 != RHS.Data1 ||
205            Data2 != RHS.Data2 ||
206            L != RHS.L ||
207            Tag != RHS.Tag;
208   }
209 
Profile(llvm::FoldingSetNodeID & ID)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());
216   }
217 
218   void print(StringRef CR, llvm::raw_ostream &Out) const;
219 
220   LLVM_DUMP_METHOD void dump() const;
221 
222   static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
223                                       const LocationContext *LC,
224                                       const ProgramPointTag *tag);
225 };
226 
227 class BlockEntrance : public ProgramPoint {
228 public:
229   BlockEntrance(const CFGBlock *B, const LocationContext *L,
230                 const ProgramPointTag *tag = nullptr)
ProgramPoint(B,BlockEntranceKind,L,tag)231     : ProgramPoint(B, BlockEntranceKind, L, tag) {
232     assert(B && "BlockEntrance requires non-null block");
233   }
234 
getBlock()235   const CFGBlock *getBlock() const {
236     return reinterpret_cast<const CFGBlock*>(getData1());
237   }
238 
getFirstElement()239   Optional<CFGElement> getFirstElement() const {
240     const CFGBlock *B = getBlock();
241     return B->empty() ? Optional<CFGElement>() : B->front();
242   }
243 
244 private:
245   friend class ProgramPoint;
246   BlockEntrance() = default;
isKind(const ProgramPoint & Location)247   static bool isKind(const ProgramPoint &Location) {
248     return Location.getKind() == BlockEntranceKind;
249   }
250 };
251 
252 class BlockExit : public ProgramPoint {
253 public:
BlockExit(const CFGBlock * B,const LocationContext * L)254   BlockExit(const CFGBlock *B, const LocationContext *L)
255     : ProgramPoint(B, BlockExitKind, L) {}
256 
getBlock()257   const CFGBlock *getBlock() const {
258     return reinterpret_cast<const CFGBlock*>(getData1());
259   }
260 
getTerminator()261   const Stmt *getTerminator() const {
262     return getBlock()->getTerminator();
263   }
264 
265 private:
266   friend class ProgramPoint;
267   BlockExit() = default;
isKind(const ProgramPoint & Location)268   static bool isKind(const ProgramPoint &Location) {
269     return Location.getKind() == BlockExitKind;
270   }
271 };
272 
273 class StmtPoint : public ProgramPoint {
274 public:
StmtPoint(const Stmt * S,const void * p2,Kind k,const LocationContext * L,const ProgramPointTag * tag)275   StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
276             const ProgramPointTag *tag)
277     : ProgramPoint(S, p2, k, L, tag) {
278     assert(S);
279   }
280 
getStmt()281   const Stmt *getStmt() const { return (const Stmt*) getData1(); }
282 
283   template <typename T>
getStmtAs()284   const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
285 
286 protected:
287   StmtPoint() = default;
288 private:
289   friend class ProgramPoint;
isKind(const ProgramPoint & Location)290   static bool isKind(const ProgramPoint &Location) {
291     unsigned k = Location.getKind();
292     return k >= PreStmtKind && k <= MaxPostStmtKind;
293   }
294 };
295 
296 
297 class PreStmt : public StmtPoint {
298 public:
299   PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
300           const Stmt *SubStmt = nullptr)
StmtPoint(S,SubStmt,PreStmtKind,L,tag)301     : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
302 
getSubStmt()303   const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
304 
305 private:
306   friend class ProgramPoint;
307   PreStmt() = default;
isKind(const ProgramPoint & Location)308   static bool isKind(const ProgramPoint &Location) {
309     return Location.getKind() == PreStmtKind;
310   }
311 };
312 
313 class PostStmt : public StmtPoint {
314 protected:
315   PostStmt() = default;
316   PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
317            const ProgramPointTag *tag = nullptr)
StmtPoint(S,data,k,L,tag)318     : StmtPoint(S, data, k, L, tag) {}
319 
320 public:
321   explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L,
322                     const ProgramPointTag *tag = nullptr)
StmtPoint(S,nullptr,k,L,tag)323     : StmtPoint(S, nullptr, k, L, tag) {}
324 
325   explicit PostStmt(const Stmt *S, const LocationContext *L,
326                     const ProgramPointTag *tag = nullptr)
StmtPoint(S,nullptr,PostStmtKind,L,tag)327     : StmtPoint(S, nullptr, PostStmtKind, L, tag) {}
328 
329 private:
330   friend class ProgramPoint;
isKind(const ProgramPoint & Location)331   static bool isKind(const ProgramPoint &Location) {
332     unsigned k = Location.getKind();
333     return k >= MinPostStmtKind && k <= MaxPostStmtKind;
334   }
335 };
336 
337 class FunctionExitPoint : public ProgramPoint {
338 public:
339   explicit FunctionExitPoint(const ReturnStmt *S,
340                              const LocationContext *LC,
341                              const ProgramPointTag *tag = nullptr)
ProgramPoint(S,FunctionExitKind,LC,tag)342       : ProgramPoint(S, FunctionExitKind, LC, tag) {}
343 
getBlock()344   const CFGBlock *getBlock() const {
345     return &getLocationContext()->getCFG()->getExit();
346   }
347 
getStmt()348   const ReturnStmt *getStmt() const {
349     return reinterpret_cast<const ReturnStmt *>(getData1());
350   }
351 
352 private:
353   friend class ProgramPoint;
354   FunctionExitPoint() = default;
isKind(const ProgramPoint & Location)355   static bool isKind(const ProgramPoint &Location) {
356     return Location.getKind() == FunctionExitKind;
357   }
358 };
359 
360 // PostCondition represents the post program point of a branch condition.
361 class PostCondition : public PostStmt {
362 public:
363   PostCondition(const Stmt *S, const LocationContext *L,
364                 const ProgramPointTag *tag = nullptr)
PostStmt(S,PostConditionKind,L,tag)365     : PostStmt(S, PostConditionKind, L, tag) {}
366 
367 private:
368   friend class ProgramPoint;
369   PostCondition() = default;
isKind(const ProgramPoint & Location)370   static bool isKind(const ProgramPoint &Location) {
371     return Location.getKind() == PostConditionKind;
372   }
373 };
374 
375 class LocationCheck : public StmtPoint {
376 protected:
377   LocationCheck() = default;
LocationCheck(const Stmt * S,const LocationContext * L,ProgramPoint::Kind K,const ProgramPointTag * tag)378   LocationCheck(const Stmt *S, const LocationContext *L,
379                 ProgramPoint::Kind K, const ProgramPointTag *tag)
380     : StmtPoint(S, nullptr, K, L, tag) {}
381 
382 private:
383   friend class ProgramPoint;
isKind(const ProgramPoint & location)384   static bool isKind(const ProgramPoint &location) {
385     unsigned k = location.getKind();
386     return k == PreLoadKind || k == PreStoreKind;
387   }
388 };
389 
390 class PreLoad : public LocationCheck {
391 public:
392   PreLoad(const Stmt *S, const LocationContext *L,
393           const ProgramPointTag *tag = nullptr)
LocationCheck(S,L,PreLoadKind,tag)394     : LocationCheck(S, L, PreLoadKind, tag) {}
395 
396 private:
397   friend class ProgramPoint;
398   PreLoad() = default;
isKind(const ProgramPoint & location)399   static bool isKind(const ProgramPoint &location) {
400     return location.getKind() == PreLoadKind;
401   }
402 };
403 
404 class PreStore : public LocationCheck {
405 public:
406   PreStore(const Stmt *S, const LocationContext *L,
407            const ProgramPointTag *tag = nullptr)
LocationCheck(S,L,PreStoreKind,tag)408   : LocationCheck(S, L, PreStoreKind, tag) {}
409 
410 private:
411   friend class ProgramPoint;
412   PreStore() = default;
isKind(const ProgramPoint & location)413   static bool isKind(const ProgramPoint &location) {
414     return location.getKind() == PreStoreKind;
415   }
416 };
417 
418 class PostLoad : public PostStmt {
419 public:
420   PostLoad(const Stmt *S, const LocationContext *L,
421            const ProgramPointTag *tag = nullptr)
PostStmt(S,PostLoadKind,L,tag)422     : PostStmt(S, PostLoadKind, L, tag) {}
423 
424 private:
425   friend class ProgramPoint;
426   PostLoad() = default;
isKind(const ProgramPoint & Location)427   static bool isKind(const ProgramPoint &Location) {
428     return Location.getKind() == PostLoadKind;
429   }
430 };
431 
432 /// Represents a program point after a store evaluation.
433 class PostStore : public PostStmt {
434 public:
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)
PostStmt(S,PostStoreKind,L,tag)440     : PostStmt(S, PostStoreKind, L, tag) {
441     assert(getData2() == nullptr);
442     setData2(Loc);
443   }
444 
445   /// Returns the information about the location used in the store,
446   /// how it was uttered in the code.
getLocationValue()447   const void *getLocationValue() const {
448     return getData2();
449   }
450 
451 private:
452   friend class ProgramPoint;
453   PostStore() = default;
isKind(const ProgramPoint & Location)454   static bool isKind(const ProgramPoint &Location) {
455     return Location.getKind() == PostStoreKind;
456   }
457 };
458 
459 class PostLValue : public PostStmt {
460 public:
461   PostLValue(const Stmt *S, const LocationContext *L,
462              const ProgramPointTag *tag = nullptr)
PostStmt(S,PostLValueKind,L,tag)463     : PostStmt(S, PostLValueKind, L, tag) {}
464 
465 private:
466   friend class ProgramPoint;
467   PostLValue() = default;
isKind(const ProgramPoint & Location)468   static bool isKind(const ProgramPoint &Location) {
469     return Location.getKind() == PostLValueKind;
470   }
471 };
472 
473 /// Represents a point after we ran remove dead bindings BEFORE
474 /// processing the given statement.
475 class PreStmtPurgeDeadSymbols : public StmtPoint {
476 public:
477   PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
478                        const ProgramPointTag *tag = nullptr)
StmtPoint(S,nullptr,PreStmtPurgeDeadSymbolsKind,L,tag)479     : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { }
480 
481 private:
482   friend class ProgramPoint;
483   PreStmtPurgeDeadSymbols() = default;
isKind(const ProgramPoint & Location)484   static bool isKind(const ProgramPoint &Location) {
485     return Location.getKind() == PreStmtPurgeDeadSymbolsKind;
486   }
487 };
488 
489 /// Represents a point after we ran remove dead bindings AFTER
490 /// processing the  given statement.
491 class PostStmtPurgeDeadSymbols : public StmtPoint {
492 public:
493   PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
494                        const ProgramPointTag *tag = nullptr)
StmtPoint(S,nullptr,PostStmtPurgeDeadSymbolsKind,L,tag)495     : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { }
496 
497 private:
498   friend class ProgramPoint;
499   PostStmtPurgeDeadSymbols() = default;
isKind(const ProgramPoint & Location)500   static bool isKind(const ProgramPoint &Location) {
501     return Location.getKind() == PostStmtPurgeDeadSymbolsKind;
502   }
503 };
504 
505 class BlockEdge : public ProgramPoint {
506 public:
BlockEdge(const CFGBlock * B1,const CFGBlock * B2,const LocationContext * L)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");
511   }
512 
getSrc()513   const CFGBlock *getSrc() const {
514     return static_cast<const CFGBlock*>(getData1());
515   }
516 
getDst()517   const CFGBlock *getDst() const {
518     return static_cast<const CFGBlock*>(getData2());
519   }
520 
521 private:
522   friend class ProgramPoint;
523   BlockEdge() = default;
isKind(const ProgramPoint & Location)524   static bool isKind(const ProgramPoint &Location) {
525     return Location.getKind() == BlockEdgeKind;
526   }
527 };
528 
529 class PostInitializer : public ProgramPoint {
530 public:
531   /// Construct a PostInitializer point that represents a location after
532   ///   CXXCtorInitializer expression evaluation.
533   ///
534   /// \param I The initializer.
535   /// \param Loc The location of the field being initialized.
PostInitializer(const CXXCtorInitializer * I,const void * Loc,const LocationContext * L)536   PostInitializer(const CXXCtorInitializer *I,
537                   const void *Loc,
538                   const LocationContext *L)
539     : ProgramPoint(I, Loc, PostInitializerKind, L) {}
540 
getInitializer()541   const CXXCtorInitializer *getInitializer() const {
542     return static_cast<const CXXCtorInitializer *>(getData1());
543   }
544 
545   /// Returns the location of the field.
getLocationValue()546   const void *getLocationValue() const {
547     return getData2();
548   }
549 
550 private:
551   friend class ProgramPoint;
552   PostInitializer() = default;
isKind(const ProgramPoint & Location)553   static bool isKind(const ProgramPoint &Location) {
554     return Location.getKind() == PostInitializerKind;
555   }
556 };
557 
558 /// Represents an implicit call event.
559 ///
560 /// The nearest statement is provided for diagnostic purposes.
561 class ImplicitCallPoint : public ProgramPoint {
562 public:
ImplicitCallPoint(const Decl * D,SourceLocation Loc,Kind K,const LocationContext * L,const ProgramPointTag * Tag)563   ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
564                     const LocationContext *L, const ProgramPointTag *Tag)
565     : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
566 
getDecl()567   const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
getLocation()568   SourceLocation getLocation() const {
569     return SourceLocation::getFromPtrEncoding(getData1());
570   }
571 
572 protected:
573   ImplicitCallPoint() = default;
574 private:
575   friend class ProgramPoint;
isKind(const ProgramPoint & Location)576   static bool isKind(const ProgramPoint &Location) {
577     return Location.getKind() >= MinImplicitCallKind &&
578            Location.getKind() <= MaxImplicitCallKind;
579   }
580 };
581 
582 /// Represents a program point just before an implicit call event.
583 ///
584 /// Explicit calls will appear as PreStmt program points.
585 class PreImplicitCall : public ImplicitCallPoint {
586 public:
587   PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
588                   const ProgramPointTag *Tag = nullptr)
ImplicitCallPoint(D,Loc,PreImplicitCallKind,L,Tag)589     : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
590 
591 private:
592   friend class ProgramPoint;
593   PreImplicitCall() = default;
isKind(const ProgramPoint & Location)594   static bool isKind(const ProgramPoint &Location) {
595     return Location.getKind() == PreImplicitCallKind;
596   }
597 };
598 
599 /// Represents a program point just after an implicit call event.
600 ///
601 /// Explicit calls will appear as PostStmt program points.
602 class PostImplicitCall : public ImplicitCallPoint {
603 public:
604   PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
605                    const ProgramPointTag *Tag = nullptr)
ImplicitCallPoint(D,Loc,PostImplicitCallKind,L,Tag)606     : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
607 
608 private:
609   friend class ProgramPoint;
610   PostImplicitCall() = default;
isKind(const ProgramPoint & Location)611   static bool isKind(const ProgramPoint &Location) {
612     return Location.getKind() == PostImplicitCallKind;
613   }
614 };
615 
616 class PostAllocatorCall : public StmtPoint {
617 public:
618   PostAllocatorCall(const Stmt *S, const LocationContext *L,
619                     const ProgramPointTag *Tag = nullptr)
StmtPoint(S,nullptr,PostAllocatorCallKind,L,Tag)620       : StmtPoint(S, nullptr, PostAllocatorCallKind, L, Tag) {}
621 
622 private:
623   friend class ProgramPoint;
624   PostAllocatorCall() = default;
isKind(const ProgramPoint & Location)625   static bool isKind(const ProgramPoint &Location) {
626     return Location.getKind() == PostAllocatorCallKind;
627   }
628 };
629 
630 /// Represents a point when we begin processing an inlined call.
631 /// CallEnter uses the caller's location context.
632 class CallEnter : public ProgramPoint {
633 public:
CallEnter(const Stmt * stmt,const StackFrameContext * calleeCtx,const LocationContext * callerCtx)634   CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
635             const LocationContext *callerCtx)
636     : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {}
637 
getCallExpr()638   const Stmt *getCallExpr() const {
639     return static_cast<const Stmt *>(getData1());
640   }
641 
getCalleeContext()642   const StackFrameContext *getCalleeContext() const {
643     return static_cast<const StackFrameContext *>(getData2());
644   }
645 
646   /// Returns the entry block in the CFG for the entered function.
getEntry()647   const CFGBlock *getEntry() const {
648     const StackFrameContext *CalleeCtx = getCalleeContext();
649     const CFG *CalleeCFG = CalleeCtx->getCFG();
650     return &(CalleeCFG->getEntry());
651   }
652 
653 private:
654   friend class ProgramPoint;
655   CallEnter() = default;
isKind(const ProgramPoint & Location)656   static bool isKind(const ProgramPoint &Location) {
657     return Location.getKind() == CallEnterKind;
658   }
659 };
660 
661 /// Represents a point when we start the call exit sequence (for inlined call).
662 ///
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:
666 /// - CallExitBegin
667 /// - Bind the return value
668 /// - Run Remove dead bindings (to clean up the dead symbols from the callee).
669 /// - CallExitEnd
670 class CallExitBegin : public ProgramPoint {
671 public:
672   // CallExitBegin uses the callee's location context.
CallExitBegin(const StackFrameContext * L,const ReturnStmt * RS)673   CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS)
674     : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { }
675 
getReturnStmt()676   const ReturnStmt *getReturnStmt() const {
677     return static_cast<const ReturnStmt *>(getData1());
678   }
679 
680 private:
681   friend class ProgramPoint;
682   CallExitBegin() = default;
isKind(const ProgramPoint & Location)683   static bool isKind(const ProgramPoint &Location) {
684     return Location.getKind() == CallExitBeginKind;
685   }
686 };
687 
688 /// Represents a point when we finish the call exit sequence (for inlined call).
689 /// \sa CallExitBegin
690 class CallExitEnd : public ProgramPoint {
691 public:
692   // CallExitEnd uses the caller's location context.
CallExitEnd(const StackFrameContext * CalleeCtx,const LocationContext * CallerCtx)693   CallExitEnd(const StackFrameContext *CalleeCtx,
694               const LocationContext *CallerCtx)
695     : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {}
696 
getCalleeContext()697   const StackFrameContext *getCalleeContext() const {
698     return static_cast<const StackFrameContext *>(getData1());
699   }
700 
701 private:
702   friend class ProgramPoint;
703   CallExitEnd() = default;
isKind(const ProgramPoint & Location)704   static bool isKind(const ProgramPoint &Location) {
705     return Location.getKind() == CallExitEndKind;
706   }
707 };
708 
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 {
716 public:
LoopExit(const Stmt * LoopStmt,const LocationContext * LC)717     LoopExit(const Stmt *LoopStmt, const LocationContext *LC)
718             : ProgramPoint(LoopStmt, nullptr, LoopExitKind, LC) {}
719 
getLoopStmt()720     const Stmt *getLoopStmt() const {
721       return static_cast<const Stmt *>(getData1());
722     }
723 
724 private:
725     friend class ProgramPoint;
726     LoopExit() = default;
isKind(const ProgramPoint & Location)727     static bool isKind(const ProgramPoint &Location) {
728       return Location.getKind() == LoopExitKind;
729     }
730 };
731 
732 /// This is a meta program point, which should be skipped by all the diagnostic
733 /// reasoning etc.
734 class EpsilonPoint : public ProgramPoint {
735 public:
736   EpsilonPoint(const LocationContext *L, const void *Data1,
737                const void *Data2 = nullptr,
738                const ProgramPointTag *tag = nullptr)
ProgramPoint(Data1,Data2,EpsilonKind,L,tag)739     : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
740 
getData()741   const void *getData() const { return getData1(); }
742 
743 private:
744   friend class ProgramPoint;
745   EpsilonPoint() = default;
isKind(const ProgramPoint & Location)746   static bool isKind(const ProgramPoint &Location) {
747     return Location.getKind() == EpsilonKind;
748   }
749 };
750 
751 } // end namespace clang
752 
753 
754 namespace llvm { // Traits specialization for DenseMap
755 
756 template <> struct DenseMapInfo<clang::ProgramPoint> {
757 
758 static inline clang::ProgramPoint getEmptyKey() {
759   uintptr_t x =
760    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
761   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
762 }
763 
764 static inline clang::ProgramPoint getTombstoneKey() {
765   uintptr_t x =
766    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
767   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
768 }
769 
770 static unsigned getHashValue(const clang::ProgramPoint &Loc) {
771   return Loc.getHashValue();
772 }
773 
774 static bool isEqual(const clang::ProgramPoint &L,
775                     const clang::ProgramPoint &R) {
776   return L == R;
777 }
778 
779 };
780 
781 template <>
782 struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
783 
784 } // end namespace llvm
785 
786 #endif
787