ProgramPoint.h revision cfa88f893915ceb8ae4ce2f17c46c24a4d67502f
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/PointerIntPair.h"
23#include "llvm/ADT/StringRef.h"
24#include "llvm/Support/Casting.h"
25#include "llvm/Support/DataTypes.h"
26#include <cassert>
27#include <string>
28#include <utility>
29
30namespace clang {
31
32class AnalysisDeclContext;
33class FunctionDecl;
34class LocationContext;
35class ProgramPointTag;
36
37class ProgramPoint {
38public:
39  enum Kind { BlockEdgeKind,
40              BlockEntranceKind,
41              BlockExitKind,
42              PreStmtKind,
43              PreStmtPurgeDeadSymbolsKind,
44              PostStmtPurgeDeadSymbolsKind,
45              PostStmtKind,
46              PreLoadKind,
47              PostLoadKind,
48              PreStoreKind,
49              PostStoreKind,
50              PostConditionKind,
51              PostLValueKind,
52              MinPostStmtKind = PostStmtKind,
53              MaxPostStmtKind = PostLValueKind,
54              PostInitializerKind,
55              CallEnterKind,
56              CallExitBeginKind,
57              CallExitEndKind,
58              PreImplicitCallKind,
59              PostImplicitCallKind,
60              MinImplicitCallKind = PreImplicitCallKind,
61              MaxImplicitCallKind = PostImplicitCallKind,
62              EpsilonKind};
63
64private:
65  const void *Data1;
66  llvm::PointerIntPair<const void *, 2, unsigned> Data2;
67
68  // The LocationContext could be NULL to allow ProgramPoint to be used in
69  // context insensitive analysis.
70  llvm::PointerIntPair<const LocationContext *, 2, unsigned> L;
71
72  llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
73
74  ProgramPoint();
75
76protected:
77  ProgramPoint(const void *P,
78               Kind k,
79               const LocationContext *l,
80               const ProgramPointTag *tag = 0)
81    : Data1(P),
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);
88      }
89
90  ProgramPoint(const void *P1,
91               const void *P2,
92               Kind k,
93               const LocationContext *l,
94               const ProgramPointTag *tag = 0)
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  Kind getKind() const {
114    unsigned x = Tag.getInt();
115    x <<= 2;
116    x |= L.getInt();
117    x <<= 2;
118    x |= Data2.getInt();
119    return (Kind) x;
120  }
121
122  /// \brief Is this a program point corresponding to purge/removal of dead
123  /// symbols and bindings.
124  bool isPurgeKind() {
125    Kind K = getKind();
126    return (K == PostStmtPurgeDeadSymbolsKind ||
127            K == PreStmtPurgeDeadSymbolsKind);
128  }
129
130  const ProgramPointTag *getTag() const { return Tag.getPointer(); }
131
132  const LocationContext *getLocationContext() const {
133    return L.getPointer();
134  }
135
136  // For use with DenseMap.  This hash is probably slow.
137  unsigned getHashValue() const {
138    llvm::FoldingSetNodeID ID;
139    Profile(ID);
140    return ID.ComputeHash();
141  }
142
143  bool operator==(const ProgramPoint & RHS) const {
144    return Data1 == RHS.Data1 &&
145           Data2 == RHS.Data2 &&
146           L == RHS.L &&
147           Tag == RHS.Tag;
148  }
149
150  bool operator!=(const ProgramPoint &RHS) const {
151    return Data1 != RHS.Data1 ||
152           Data2 != RHS.Data2 ||
153           L != RHS.L ||
154           Tag != RHS.Tag;
155  }
156
157  void Profile(llvm::FoldingSetNodeID& ID) const {
158    ID.AddInteger((unsigned) getKind());
159    ID.AddPointer(getData1());
160    ID.AddPointer(getData2());
161    ID.AddPointer(getLocationContext());
162    ID.AddPointer(getTag());
163  }
164
165  static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
166                                      const LocationContext *LC,
167                                      const ProgramPointTag *tag);
168};
169
170class BlockEntrance : public ProgramPoint {
171public:
172  BlockEntrance(const CFGBlock *B, const LocationContext *L,
173                const ProgramPointTag *tag = 0)
174    : ProgramPoint(B, BlockEntranceKind, L, tag) {
175    assert(B && "BlockEntrance requires non-null block");
176  }
177
178  const CFGBlock *getBlock() const {
179    return reinterpret_cast<const CFGBlock*>(getData1());
180  }
181
182  const CFGElement getFirstElement() const {
183    const CFGBlock *B = getBlock();
184    return B->empty() ? CFGElement() : B->front();
185  }
186
187  static bool classof(const ProgramPoint* Location) {
188    return Location->getKind() == BlockEntranceKind;
189  }
190};
191
192class BlockExit : public ProgramPoint {
193public:
194  BlockExit(const CFGBlock *B, const LocationContext *L)
195    : ProgramPoint(B, BlockExitKind, L) {}
196
197  const CFGBlock *getBlock() const {
198    return reinterpret_cast<const CFGBlock*>(getData1());
199  }
200
201  const Stmt *getTerminator() const {
202    return getBlock()->getTerminator();
203  }
204
205  static bool classof(const ProgramPoint* Location) {
206    return Location->getKind() == BlockExitKind;
207  }
208};
209
210class StmtPoint : public ProgramPoint {
211public:
212  StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
213            const ProgramPointTag *tag)
214    : ProgramPoint(S, p2, k, L, tag) {
215    assert(S);
216  }
217
218  const Stmt *getStmt() const { return (const Stmt*) getData1(); }
219
220  template <typename T>
221  const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
222
223  static bool classof(const ProgramPoint* Location) {
224    unsigned k = Location->getKind();
225    return k >= PreStmtKind && k <= MaxPostStmtKind;
226  }
227};
228
229
230class PreStmt : public StmtPoint {
231public:
232  PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
233          const Stmt *SubStmt = 0)
234    : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
235
236  const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
237
238  static bool classof(const ProgramPoint* Location) {
239    return Location->getKind() == PreStmtKind;
240  }
241};
242
243class PostStmt : public StmtPoint {
244protected:
245  PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
246           const ProgramPointTag *tag = 0)
247    : StmtPoint(S, data, k, L, tag) {}
248
249public:
250  explicit PostStmt(const Stmt *S, Kind k,
251                    const LocationContext *L, const ProgramPointTag *tag = 0)
252    : StmtPoint(S, NULL, k, L, tag) {}
253
254  explicit PostStmt(const Stmt *S, const LocationContext *L,
255                    const ProgramPointTag *tag = 0)
256    : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
257
258  static bool classof(const ProgramPoint* Location) {
259    unsigned k = Location->getKind();
260    return k >= MinPostStmtKind && k <= MaxPostStmtKind;
261  }
262};
263
264// PostCondition represents the post program point of a branch condition.
265class PostCondition : public PostStmt {
266public:
267  PostCondition(const Stmt *S, const LocationContext *L,
268                const ProgramPointTag *tag = 0)
269    : PostStmt(S, PostConditionKind, L, tag) {}
270
271  static bool classof(const ProgramPoint* Location) {
272    return Location->getKind() == PostConditionKind;
273  }
274};
275
276class LocationCheck : public StmtPoint {
277protected:
278  LocationCheck(const Stmt *S, const LocationContext *L,
279                ProgramPoint::Kind K, const ProgramPointTag *tag)
280    : StmtPoint(S, NULL, K, L, tag) {}
281
282  static bool classof(const ProgramPoint *location) {
283    unsigned k = location->getKind();
284    return k == PreLoadKind || k == PreStoreKind;
285  }
286};
287
288class PreLoad : public LocationCheck {
289public:
290  PreLoad(const Stmt *S, const LocationContext *L,
291          const ProgramPointTag *tag = 0)
292    : LocationCheck(S, L, PreLoadKind, tag) {}
293
294  static bool classof(const ProgramPoint *location) {
295    return location->getKind() == PreLoadKind;
296  }
297};
298
299class PreStore : public LocationCheck {
300public:
301  PreStore(const Stmt *S, const LocationContext *L,
302           const ProgramPointTag *tag = 0)
303  : LocationCheck(S, L, PreStoreKind, tag) {}
304
305  static bool classof(const ProgramPoint *location) {
306    return location->getKind() == PreStoreKind;
307  }
308};
309
310class PostLoad : public PostStmt {
311public:
312  PostLoad(const Stmt *S, const LocationContext *L,
313           const ProgramPointTag *tag = 0)
314    : PostStmt(S, PostLoadKind, L, tag) {}
315
316  static bool classof(const ProgramPoint* Location) {
317    return Location->getKind() == PostLoadKind;
318  }
319};
320
321/// \brief Represents a program point after a store evaluation.
322class PostStore : public PostStmt {
323public:
324  /// Construct the post store point.
325  /// \param Loc can be used to store the information about the location
326  /// used in the form it was uttered in the code.
327  PostStore(const Stmt *S, const LocationContext *L, const void *Loc,
328            const ProgramPointTag *tag = 0)
329    : PostStmt(S, PostStoreKind, L, tag) {
330    assert(getData2() == 0);
331    setData2(Loc);
332  }
333
334  static bool classof(const ProgramPoint* Location) {
335    return Location->getKind() == PostStoreKind;
336  }
337
338  /// \brief Returns the information about the location used in the store,
339  /// how it was uttered in the code.
340  const void *getLocationValue() const {
341    return getData2();
342  }
343
344};
345
346class PostLValue : public PostStmt {
347public:
348  PostLValue(const Stmt *S, const LocationContext *L,
349             const ProgramPointTag *tag = 0)
350    : PostStmt(S, PostLValueKind, L, tag) {}
351
352  static bool classof(const ProgramPoint* Location) {
353    return Location->getKind() == PostLValueKind;
354  }
355};
356
357/// Represents a point after we ran remove dead bindings BEFORE
358/// processing the given statement.
359class PreStmtPurgeDeadSymbols : public StmtPoint {
360public:
361  PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
362                       const ProgramPointTag *tag = 0)
363    : StmtPoint(S, 0, PreStmtPurgeDeadSymbolsKind, L, tag) { }
364
365  static bool classof(const ProgramPoint* Location) {
366    return Location->getKind() == PreStmtPurgeDeadSymbolsKind;
367  }
368};
369
370/// Represents a point after we ran remove dead bindings AFTER
371/// processing the  given statement.
372class PostStmtPurgeDeadSymbols : public StmtPoint {
373public:
374  PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
375                       const ProgramPointTag *tag = 0)
376    : StmtPoint(S, 0, PostStmtPurgeDeadSymbolsKind, L, tag) { }
377
378  static bool classof(const ProgramPoint* Location) {
379    return Location->getKind() == PostStmtPurgeDeadSymbolsKind;
380  }
381};
382
383class BlockEdge : public ProgramPoint {
384public:
385  BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
386    : ProgramPoint(B1, B2, BlockEdgeKind, L) {
387    assert(B1 && "BlockEdge: source block must be non-null");
388    assert(B2 && "BlockEdge: destination block must be non-null");
389  }
390
391  const CFGBlock *getSrc() const {
392    return static_cast<const CFGBlock*>(getData1());
393  }
394
395  const CFGBlock *getDst() const {
396    return static_cast<const CFGBlock*>(getData2());
397  }
398
399  static bool classof(const ProgramPoint* Location) {
400    return Location->getKind() == BlockEdgeKind;
401  }
402};
403
404class PostInitializer : public ProgramPoint {
405public:
406  PostInitializer(const CXXCtorInitializer *I,
407                  const LocationContext *L)
408    : ProgramPoint(I, PostInitializerKind, L) {}
409
410  static bool classof(const ProgramPoint *Location) {
411    return Location->getKind() == PostInitializerKind;
412  }
413};
414
415/// Represents an implicit call event.
416///
417/// The nearest statement is provided for diagnostic purposes.
418class ImplicitCallPoint : public ProgramPoint {
419public:
420  ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
421                    const LocationContext *L, const ProgramPointTag *Tag)
422    : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
423
424  const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
425  SourceLocation getLocation() const {
426    return SourceLocation::getFromPtrEncoding(getData1());
427  }
428
429  static bool classof(const ProgramPoint *Location) {
430    return Location->getKind() >= MinImplicitCallKind &&
431           Location->getKind() <= MaxImplicitCallKind;
432  }
433};
434
435/// Represents a program point just before an implicit call event.
436///
437/// Explicit calls will appear as PreStmt program points.
438class PreImplicitCall : public ImplicitCallPoint {
439public:
440  PreImplicitCall(const Decl *D, SourceLocation Loc,
441                  const LocationContext *L, const ProgramPointTag *Tag = 0)
442    : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
443
444  static bool classof(const ProgramPoint *Location) {
445    return Location->getKind() == PreImplicitCallKind;
446  }
447};
448
449/// Represents a program point just after an implicit call event.
450///
451/// Explicit calls will appear as PostStmt program points.
452class PostImplicitCall : public ImplicitCallPoint {
453public:
454  PostImplicitCall(const Decl *D, SourceLocation Loc,
455                   const LocationContext *L, const ProgramPointTag *Tag = 0)
456    : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
457
458  static bool classof(const ProgramPoint *Location) {
459    return Location->getKind() == PostImplicitCallKind;
460  }
461};
462
463/// Represents a point when we begin processing an inlined call.
464/// CallEnter uses the caller's location context.
465class CallEnter : public ProgramPoint {
466public:
467  CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
468            const LocationContext *callerCtx)
469    : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {}
470
471  const Stmt *getCallExpr() const {
472    return static_cast<const Stmt *>(getData1());
473  }
474
475  const StackFrameContext *getCalleeContext() const {
476    return static_cast<const StackFrameContext *>(getData2());
477  }
478
479  static bool classof(const ProgramPoint *Location) {
480    return Location->getKind() == CallEnterKind;
481  }
482};
483
484/// Represents a point when we start the call exit sequence (for inlined call).
485///
486/// The call exit is simulated with a sequence of nodes, which occur between
487/// CallExitBegin and CallExitEnd. The following operations occur between the
488/// two program points:
489/// - CallExitBegin
490/// - Bind the return value
491/// - Run Remove dead bindings (to clean up the dead symbols from the callee).
492/// - CallExitEnd
493class CallExitBegin : public ProgramPoint {
494public:
495  // CallExitBegin uses the callee's location context.
496  CallExitBegin(const StackFrameContext *L)
497    : ProgramPoint(0, CallExitBeginKind, L, 0) {}
498
499  static bool classof(const ProgramPoint *Location) {
500    return Location->getKind() == CallExitBeginKind;
501  }
502};
503
504/// Represents a point when we finish the call exit sequence (for inlined call).
505/// \sa CallExitBegin
506class CallExitEnd : public ProgramPoint {
507public:
508  // CallExitEnd uses the caller's location context.
509  CallExitEnd(const StackFrameContext *CalleeCtx,
510              const LocationContext *CallerCtx)
511    : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, 0) {}
512
513  const StackFrameContext *getCalleeContext() const {
514    return static_cast<const StackFrameContext *>(getData1());
515  }
516
517  static bool classof(const ProgramPoint *Location) {
518    return Location->getKind() == CallExitEndKind;
519  }
520};
521
522/// This is a meta program point, which should be skipped by all the diagnostic
523/// reasoning etc.
524class EpsilonPoint : public ProgramPoint {
525public:
526  EpsilonPoint(const LocationContext *L, const void *Data1,
527               const void *Data2 = 0, const ProgramPointTag *tag = 0)
528    : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
529
530  const void *getData() const { return getData1(); }
531
532  static bool classof(const ProgramPoint* Location) {
533    return Location->getKind() == EpsilonKind;
534  }
535};
536
537/// ProgramPoints can be "tagged" as representing points specific to a given
538/// analysis entity.  Tags are abstract annotations, with an associated
539/// description and potentially other information.
540class ProgramPointTag {
541public:
542  ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {}
543  virtual ~ProgramPointTag();
544  virtual StringRef getTagDescription() const = 0;
545
546protected:
547  /// Used to implement 'classof' in subclasses.
548  const void *getTagKind() { return TagKind; }
549
550private:
551  const void *TagKind;
552};
553
554class SimpleProgramPointTag : public ProgramPointTag {
555  std::string desc;
556public:
557  SimpleProgramPointTag(StringRef description);
558  StringRef getTagDescription() const;
559};
560
561} // end namespace clang
562
563
564namespace llvm { // Traits specialization for DenseMap
565
566template <> struct DenseMapInfo<clang::ProgramPoint> {
567
568static inline clang::ProgramPoint getEmptyKey() {
569  uintptr_t x =
570   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
571  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
572}
573
574static inline clang::ProgramPoint getTombstoneKey() {
575  uintptr_t x =
576   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
577  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
578}
579
580static unsigned getHashValue(const clang::ProgramPoint &Loc) {
581  return Loc.getHashValue();
582}
583
584static bool isEqual(const clang::ProgramPoint &L,
585                    const clang::ProgramPoint &R) {
586  return L == R;
587}
588
589};
590
591template <>
592struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
593
594} // end namespace llvm
595
596#endif
597