ProgramPoint.h revision 28038f33aa2db4833881fea757a1f0daf85ac02b
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              PreStmtPurgeDeadSymbolsKind,
44              PostStmtPurgeDeadSymbolsKind,
45              PostStmtKind,
46              PreLoadKind,
47              PostLoadKind,
48              PreStoreKind,
49              PostStoreKind,
50              PostConditionKind,
51              PostLValueKind,
52              PostInitializerKind,
53              CallEnterKind,
54              CallExitBeginKind,
55              CallExitEndKind,
56              MinPostStmtKind = PostStmtKind,
57              MaxPostStmtKind = 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  static bool classof(const ProgramPoint*) { return true; }
144
145  bool operator==(const ProgramPoint & RHS) const {
146    return Data1 == RHS.Data1 &&
147           Data2 == RHS.Data2 &&
148           L == RHS.L &&
149           Tag == RHS.Tag;
150  }
151
152  bool operator!=(const ProgramPoint &RHS) const {
153    return Data1 != RHS.Data1 ||
154           Data2 != RHS.Data2 ||
155           L != RHS.L ||
156           Tag != RHS.Tag;
157  }
158
159  void Profile(llvm::FoldingSetNodeID& ID) const {
160    ID.AddInteger((unsigned) getKind());
161    ID.AddPointer(getData1());
162    ID.AddPointer(getData2());
163    ID.AddPointer(getLocationContext());
164    ID.AddPointer(getTag());
165  }
166
167  static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
168                                      const LocationContext *LC,
169                                      const ProgramPointTag *tag);
170};
171
172class BlockEntrance : public ProgramPoint {
173public:
174  BlockEntrance(const CFGBlock *B, const LocationContext *L,
175                const ProgramPointTag *tag = 0)
176    : ProgramPoint(B, BlockEntranceKind, L, tag) {
177    assert(B && "BlockEntrance requires non-null block");
178  }
179
180  const CFGBlock *getBlock() const {
181    return reinterpret_cast<const CFGBlock*>(getData1());
182  }
183
184  const CFGElement getFirstElement() const {
185    const CFGBlock *B = getBlock();
186    return B->empty() ? CFGElement() : B->front();
187  }
188
189  static bool classof(const ProgramPoint* Location) {
190    return Location->getKind() == BlockEntranceKind;
191  }
192};
193
194class BlockExit : public ProgramPoint {
195public:
196  BlockExit(const CFGBlock *B, const LocationContext *L)
197    : ProgramPoint(B, BlockExitKind, L) {}
198
199  const CFGBlock *getBlock() const {
200    return reinterpret_cast<const CFGBlock*>(getData1());
201  }
202
203  const Stmt *getTerminator() const {
204    return getBlock()->getTerminator();
205  }
206
207  static bool classof(const ProgramPoint* Location) {
208    return Location->getKind() == BlockExitKind;
209  }
210};
211
212class StmtPoint : public ProgramPoint {
213public:
214  StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
215            const ProgramPointTag *tag)
216    : ProgramPoint(S, p2, k, L, tag) {}
217
218  const Stmt *getStmt() const { return (const Stmt*) getData1(); }
219
220  template <typename T>
221  const T* getStmtAs() const { return llvm::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.
464class CallEnter : public StmtPoint {
465public:
466  CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
467            const LocationContext *callerCtx)
468    : StmtPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {}
469
470  const Stmt *getCallExpr() const {
471    return static_cast<const Stmt *>(getData1());
472  }
473
474  const StackFrameContext *getCalleeContext() const {
475    return static_cast<const StackFrameContext *>(getData2());
476  }
477
478  static bool classof(const ProgramPoint *Location) {
479    return Location->getKind() == CallEnterKind;
480  }
481};
482
483/// Represents a point when we start the call exit sequence (for inlined call).
484///
485/// The call exit is simulated with a sequence of nodes, which occur between
486/// CallExitBegin and CallExitEnd. The following operations occur between the
487/// two program points:
488/// - CallExitBegin
489/// - Bind the return value
490/// - Run Remove dead bindings (to clean up the dead symbols from the callee).
491/// - CallExitEnd
492class CallExitBegin : public StmtPoint {
493public:
494  // CallExitBegin uses the callee's location context.
495  CallExitBegin(const Stmt *S, const LocationContext *L)
496    : StmtPoint(S, 0, CallExitBeginKind, L, 0) {}
497
498  static bool classof(const ProgramPoint *Location) {
499    return Location->getKind() == CallExitBeginKind;
500  }
501};
502
503/// Represents a point when we finish the call exit sequence (for inlined call).
504/// \sa CallExitBegin
505class CallExitEnd : public StmtPoint {
506public:
507  // CallExitEnd uses the caller's location context.
508  CallExitEnd(const Stmt *S, const LocationContext *L)
509    : StmtPoint(S, 0, CallExitEndKind, L, 0) {}
510
511  static bool classof(const ProgramPoint *Location) {
512    return Location->getKind() == CallExitEndKind;
513  }
514};
515
516/// This is a meta program point, which should be skipped by all the diagnostic
517/// reasoning etc.
518class EpsilonPoint : public ProgramPoint {
519public:
520  EpsilonPoint(const LocationContext *L, const void *Data1,
521               const void *Data2 = 0, const ProgramPointTag *tag = 0)
522    : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
523
524  const void *getData() const { return getData1(); }
525
526  static bool classof(const ProgramPoint* Location) {
527    return Location->getKind() == EpsilonKind;
528  }
529};
530
531/// ProgramPoints can be "tagged" as representing points specific to a given
532/// analysis entity.  Tags are abstract annotations, with an associated
533/// description and potentially other information.
534class ProgramPointTag {
535public:
536  ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {}
537  virtual ~ProgramPointTag();
538  virtual StringRef getTagDescription() const = 0;
539
540protected:
541  /// Used to implement 'classof' in subclasses.
542  const void *getTagKind() { return TagKind; }
543
544private:
545  const void *TagKind;
546};
547
548class SimpleProgramPointTag : public ProgramPointTag {
549  std::string desc;
550public:
551  SimpleProgramPointTag(StringRef description);
552  StringRef getTagDescription() const;
553};
554
555} // end namespace clang
556
557
558namespace llvm { // Traits specialization for DenseMap
559
560template <> struct DenseMapInfo<clang::ProgramPoint> {
561
562static inline clang::ProgramPoint getEmptyKey() {
563  uintptr_t x =
564   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
565  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
566}
567
568static inline clang::ProgramPoint getTombstoneKey() {
569  uintptr_t x =
570   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
571  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
572}
573
574static unsigned getHashValue(const clang::ProgramPoint &Loc) {
575  return Loc.getHashValue();
576}
577
578static bool isEqual(const clang::ProgramPoint &L,
579                    const clang::ProgramPoint &R) {
580  return L == R;
581}
582
583};
584
585template <>
586struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
587
588} // end namespace llvm
589
590#endif
591