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