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