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