contrib/llvm/tools/clang/include/clang/Analysis/ProgramPoint.h

   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/FoldingSet.h"
  23 #include "llvm/Support/Casting.h"
  24 #include <cassert>
  25 #include <utility>
  26
  27 namespace clang {
  28
  29 class LocationContext;
  30 class AnalysisContext;
  31 class FunctionDecl;
  32
  33 class ProgramPoint {
  34 public:
  35   enum Kind { BlockEdgeKind,
  36               BlockEntranceKind,
  37               BlockExitKind,
  38               PreStmtKind,
  39               PostStmtKind,
  40               PreLoadKind,
  41               PostLoadKind,
  42               PreStoreKind,
  43               PostStoreKind,
  44               PostPurgeDeadSymbolsKind,
  45               PostStmtCustomKind,
  46               PostConditionKind,
  47               PostLValueKind,
  48               PostInitializerKind,
  49               CallEnterKind,
  50               CallExitKind,
  51               MinPostStmtKind = PostStmtKind,
  52               MaxPostStmtKind = CallExitKind };
  53
  54 private:
  55   std::pair<const void *, const void *> Data;
  56   Kind K;
  57
  58   // The LocationContext could be NULL to allow ProgramPoint to be used in
  59   // context insensitive analysis.
  60   const LocationContext *L;
  61   const void *Tag;
  62
  63 protected:
  64   ProgramPoint(const void* P, Kind k, const LocationContext *l,
  65                const void *tag = 0)
  66     : Data(P, static_cast<const void*>(NULL)), K(k), L(l), Tag(tag) {}
  67
  68   ProgramPoint(const void* P1, const void* P2, Kind k, const LocationContext *l,
  69                const void *tag = 0)
  70     : Data(P1, P2), K(k), L(l), Tag(tag) {}
  71
  72 protected:
  73   const void* getData1() const { return Data.first; }
  74   const void* getData2() const { return Data.second; }
  75
  76 public:
  77   Kind getKind() const { return K; }
  78
  79   const void *getTag() const { return Tag; }
  80
  81   const LocationContext *getLocationContext() const { return L; }
  82
  83   // For use with DenseMap.  This hash is probably slow.
  84   unsigned getHashValue() const {
  85     llvm::FoldingSetNodeID ID;
  86     Profile(ID);
  87     return ID.ComputeHash();
  88   }
  89
  90   static bool classof(const ProgramPoint*) { return true; }
  91
  92   bool operator==(const ProgramPoint & RHS) const {
  93     return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag;
  94   }
  95
  96   bool operator!=(const ProgramPoint& RHS) const {
  97     return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag;
  98   }
  99
 100   void Profile(llvm::FoldingSetNodeID& ID) const {
 101     ID.AddInteger((unsigned) K);
 102     ID.AddPointer(Data.first);
 103     ID.AddPointer(Data.second);
 104     ID.AddPointer(L);
 105     ID.AddPointer(Tag);
 106   }
 107 };
 108
 109 class BlockEntrance : public ProgramPoint {
 110 public:
 111   BlockEntrance(const CFGBlock* B, const LocationContext *L,
 112                 const void *tag = 0)
 113     : ProgramPoint(B, BlockEntranceKind, L, tag) {}
 114
 115   const CFGBlock* getBlock() const {
 116     return reinterpret_cast<const CFGBlock*>(getData1());
 117   }
 118
 119   const CFGElement getFirstElement() const {
 120     const CFGBlock* B = getBlock();
 121     return B->empty() ? CFGElement() : B->front();
 122   }
 123
 124   /// Create a new BlockEntrance object that is the same as the original
 125   /// except for using the specified tag value.
 126   BlockEntrance withTag(const void *tag) {
 127     return BlockEntrance(getBlock(), getLocationContext(), tag);
 128   }
 129
 130   static bool classof(const ProgramPoint* Location) {
 131     return Location->getKind() == BlockEntranceKind;
 132   }
 133 };
 134
 135 class BlockExit : public ProgramPoint {
 136 public:
 137   BlockExit(const CFGBlock* B, const LocationContext *L)
 138     : ProgramPoint(B, BlockExitKind, L) {}
 139
 140   const CFGBlock* getBlock() const {
 141     return reinterpret_cast<const CFGBlock*>(getData1());
 142   }
 143
 144   const Stmt* getTerminator() const {
 145     return getBlock()->getTerminator();
 146   }
 147
 148   static bool classof(const ProgramPoint* Location) {
 149     return Location->getKind() == BlockExitKind;
 150   }
 151 };
 152
 153 class StmtPoint : public ProgramPoint {
 154 public:
 155   StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
 156             const void *tag)
 157     : ProgramPoint(S, p2, k, L, tag) {}
 158
 159   const Stmt *getStmt() const { return (const Stmt*) getData1(); }
 160
 161   template <typename T>
 162   const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); }
 163
 164   static bool classof(const ProgramPoint* Location) {
 165     unsigned k = Location->getKind();
 166     return k >= PreStmtKind && k <= MaxPostStmtKind;
 167   }
 168 };
 169
 170
 171 class PreStmt : public StmtPoint {
 172 public:
 173   PreStmt(const Stmt *S, const LocationContext *L, const void *tag,
 174           const Stmt *SubStmt = 0)
 175     : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
 176
 177   const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
 178
 179   static bool classof(const ProgramPoint* Location) {
 180     return Location->getKind() == PreStmtKind;
 181   }
 182 };
 183
 184 class PostStmt : public StmtPoint {
 185 protected:
 186   PostStmt(const Stmt* S, const void* data, Kind k, const LocationContext *L,
 187            const void *tag =0)
 188     : StmtPoint(S, data, k, L, tag) {}
 189
 190 public:
 191   explicit PostStmt(const Stmt* S, Kind k,
 192                     const LocationContext *L, const void *tag = 0)
 193     : StmtPoint(S, NULL, k, L, tag) {}
 194
 195   explicit PostStmt(const Stmt* S, const LocationContext *L,const void *tag = 0)
 196     : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
 197
 198   static bool classof(const ProgramPoint* Location) {
 199     unsigned k = Location->getKind();
 200     return k >= MinPostStmtKind && k <= MaxPostStmtKind;
 201   }
 202 };
 203
 204 class PostStmtCustom : public PostStmt {
 205 public:
 206   PostStmtCustom(const Stmt* S,
 207                  const std::pair<const void*, const void*>* TaggedData,\
 208                  const LocationContext *L)
 209     : PostStmt(S, TaggedData, PostStmtCustomKind, L) {}
 210
 211   const std::pair<const void*, const void*>& getTaggedPair() const {
 212     return
 213       *reinterpret_cast<const std::pair<const void*, const void*>*>(getData2());
 214   }
 215
 216   const void* getTag() const { return getTaggedPair().first; }
 217
 218   const void* getTaggedData() const { return getTaggedPair().second; }
 219
 220   static bool classof(const ProgramPoint* Location) {
 221     return Location->getKind() == PostStmtCustomKind;
 222   }
 223 };
 224
 225 // PostCondition represents the post program point of a branch condition.
 226 class PostCondition : public PostStmt {
 227 public:
 228   PostCondition(const Stmt* S, const LocationContext *L, const void *tag = 0)
 229     : PostStmt(S, PostConditionKind, L, tag) {}
 230
 231   static bool classof(const ProgramPoint* Location) {
 232     return Location->getKind() == PostConditionKind;
 233   }
 234 };
 235
 236 class LocationCheck : public StmtPoint {
 237 protected:
 238   LocationCheck(const Stmt *S, const LocationContext *L,
 239                 ProgramPoint::Kind K, const void *tag)
 240     : StmtPoint(S, NULL, K, L, tag) {}
 241
 242   static bool classof(const ProgramPoint *location) {
 243     unsigned k = location->getKind();
 244     return k == PreLoadKind || k == PreStoreKind;
 245   }
 246 };
 247
 248 class PreLoad : public LocationCheck {
 249 public:
 250   PreLoad(const Stmt *S, const LocationContext *L, const void *tag = 0)
 251     : LocationCheck(S, L, PreLoadKind, tag) {}
 252
 253   static bool classof(const ProgramPoint *location) {
 254     return location->getKind() == PreLoadKind;
 255   }
 256 };
 257
 258 class PreStore : public LocationCheck {
 259 public:
 260   PreStore(const Stmt *S, const LocationContext *L, const void *tag = 0)
 261   : LocationCheck(S, L, PreStoreKind, tag) {}
 262
 263   static bool classof(const ProgramPoint *location) {
 264     return location->getKind() == PreStoreKind;
 265   }
 266 };
 267
 268 class PostLoad : public PostStmt {
 269 public:
 270   PostLoad(const Stmt* S, const LocationContext *L, const void *tag = 0)
 271     : PostStmt(S, PostLoadKind, L, tag) {}
 272
 273   static bool classof(const ProgramPoint* Location) {
 274     return Location->getKind() == PostLoadKind;
 275   }
 276 };
 277
 278 class PostStore : public PostStmt {
 279 public:
 280   PostStore(const Stmt* S, const LocationContext *L, const void *tag = 0)
 281     : PostStmt(S, PostStoreKind, L, tag) {}
 282
 283   static bool classof(const ProgramPoint* Location) {
 284     return Location->getKind() == PostStoreKind;
 285   }
 286 };
 287
 288 class PostLValue : public PostStmt {
 289 public:
 290   PostLValue(const Stmt* S, const LocationContext *L, const void *tag = 0)
 291     : PostStmt(S, PostLValueKind, L, tag) {}
 292
 293   static bool classof(const ProgramPoint* Location) {
 294     return Location->getKind() == PostLValueKind;
 295   }
 296 };
 297
 298 class PostPurgeDeadSymbols : public PostStmt {
 299 public:
 300   PostPurgeDeadSymbols(const Stmt* S, const LocationContext *L,
 301                        const void *tag = 0)
 302     : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {}
 303
 304   static bool classof(const ProgramPoint* Location) {
 305     return Location->getKind() == PostPurgeDeadSymbolsKind;
 306   }
 307 };
 308
 309 class BlockEdge : public ProgramPoint {
 310 public:
 311   BlockEdge(const CFGBlock* B1, const CFGBlock* B2, const LocationContext *L)
 312     : ProgramPoint(B1, B2, BlockEdgeKind, L) {}
 313
 314   const CFGBlock* getSrc() const {
 315     return static_cast<const CFGBlock*>(getData1());
 316   }
 317
 318   const CFGBlock* getDst() const {
 319     return static_cast<const CFGBlock*>(getData2());
 320   }
 321
 322   static bool classof(const ProgramPoint* Location) {
 323     return Location->getKind() == BlockEdgeKind;
 324   }
 325 };
 326
 327 class PostInitializer : public ProgramPoint {
 328 public:
 329   PostInitializer(const CXXCtorInitializer *I,
 330                   const LocationContext *L)
 331     : ProgramPoint(I, PostInitializerKind, L) {}
 332
 333   static bool classof(const ProgramPoint *Location) {
 334     return Location->getKind() == PostInitializerKind;
 335   }
 336 };
 337
 338 class CallEnter : public StmtPoint {
 339 public:
 340   CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
 341             const LocationContext *callerCtx)
 342     : StmtPoint(stmt, calleeCtx, CallEnterKind, callerCtx, 0) {}
 343
 344   const Stmt *getCallExpr() const {
 345     return static_cast<const Stmt *>(getData1());
 346   }
 347
 348   const StackFrameContext *getCalleeContext() const {
 349     return static_cast<const StackFrameContext *>(getData2());
 350   }
 351
 352   static bool classof(const ProgramPoint *Location) {
 353     return Location->getKind() == CallEnterKind;
 354   }
 355 };
 356
 357 class CallExit : public StmtPoint {
 358 public:
 359   // CallExit uses the callee's location context.
 360   CallExit(const Stmt *S, const LocationContext *L)
 361     : StmtPoint(S, 0, CallExitKind, L, 0) {}
 362
 363   static bool classof(const ProgramPoint *Location) {
 364     return Location->getKind() == CallExitKind;
 365   }
 366 };
 367
 368
 369 } // end namespace clang
 370
 371
 372 namespace llvm { // Traits specialization for DenseMap
 373
 374 template <> struct DenseMapInfo<clang::ProgramPoint> {
 375
 376 static inline clang::ProgramPoint getEmptyKey() {
 377   uintptr_t x =
 378    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
 379   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
 380 }
 381
 382 static inline clang::ProgramPoint getTombstoneKey() {
 383   uintptr_t x =
 384    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
 385   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
 386 }
 387
 388 static unsigned getHashValue(const clang::ProgramPoint& Loc) {
 389   return Loc.getHashValue();
 390 }
 391
 392 static bool isEqual(const clang::ProgramPoint& L,
 393                     const clang::ProgramPoint& R) {
 394   return L == R;
 395 }
 396
 397 };
 398
 399 template <>
 400 struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
 401
 402 } // end namespace llvm
 403
 404 #endif