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 "llvm/ADT/StringRef.h"
  25 #include <cassert>
  26 #include <utility>
  27 #include <string>
  28
  29 namespace clang {
  30
  31 class AnalysisContext;
  32 class FunctionDecl;
  33 class LocationContext;
  34 class ProgramPointTag;
  35
  36 class ProgramPoint {
  37 public:
  38   enum Kind { BlockEdgeKind,
  39               BlockEntranceKind,
  40               BlockExitKind,
  41               PreStmtKind,
  42               PostStmtKind,
  43               PreLoadKind,
  44               PostLoadKind,
  45               PreStoreKind,
  46               PostStoreKind,
  47               PostPurgeDeadSymbolsKind,
  48               PostConditionKind,
  49               PostLValueKind,
  50               PostInitializerKind,
  51               CallEnterKind,
  52               CallExitKind,
  53               MinPostStmtKind = PostStmtKind,
  54               MaxPostStmtKind = CallExitKind };
  55
  56 private:
  57   std::pair<const void *, const void *> Data;
  58   Kind K;
  59
  60   // The LocationContext could be NULL to allow ProgramPoint to be used in
  61   // context insensitive analysis.
  62   const LocationContext *L;
  63   const ProgramPointTag *Tag;
  64
  65   ProgramPoint();
  66
  67 protected:
  68   ProgramPoint(const void *P, Kind k, const LocationContext *l,
  69                const ProgramPointTag *tag = 0)
  70     : Data(P, static_cast<const void*>(NULL)), K(k), L(l), Tag(tag) {}
  71
  72   ProgramPoint(const void *P1, const void *P2, Kind k, const LocationContext *l,
  73                const ProgramPointTag *tag = 0)
  74     : Data(P1, P2), K(k), L(l), Tag(tag) {}
  75
  76 protected:
  77   const void *getData1() const { return Data.first; }
  78   const void *getData2() const { return Data.second; }
  79
  80 public:
  81   /// Create a new ProgramPoint object that is the same as the original
  82   /// except for using the specified tag value.
  83   ProgramPoint withTag(const ProgramPointTag *tag) const {
  84     return ProgramPoint(Data.first, Data.second, K, L, tag);
  85   }
  86
  87   Kind getKind() const { return K; }
  88
  89   const ProgramPointTag *getTag() const { return Tag; }
  90
  91   const LocationContext *getLocationContext() const { return L; }
  92
  93   // For use with DenseMap.  This hash is probably slow.
  94   unsigned getHashValue() const {
  95     llvm::FoldingSetNodeID ID;
  96     Profile(ID);
  97     return ID.ComputeHash();
  98   }
  99
 100   static bool classof(const ProgramPoint*) { return true; }
 101
 102   bool operator==(const ProgramPoint & RHS) const {
 103     return K == RHS.K && Data == RHS.Data && L == RHS.L && Tag == RHS.Tag;
 104   }
 105
 106   bool operator!=(const ProgramPoint &RHS) const {
 107     return K != RHS.K || Data != RHS.Data || L != RHS.L || Tag != RHS.Tag;
 108   }
 109
 110   void Profile(llvm::FoldingSetNodeID& ID) const {
 111     ID.AddInteger((unsigned) K);
 112     ID.AddPointer(Data.first);
 113     ID.AddPointer(Data.second);
 114     ID.AddPointer(L);
 115     ID.AddPointer(Tag);
 116   }
 117
 118   static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
 119                                       const LocationContext *LC,
 120                                       const ProgramPointTag *tag);
 121
 122 };
 123
 124 class BlockEntrance : public ProgramPoint {
 125 public:
 126   BlockEntrance(const CFGBlock *B, const LocationContext *L,
 127                 const ProgramPointTag *tag = 0)
 128     : ProgramPoint(B, BlockEntranceKind, L, tag) {
 129     assert(B && "BlockEntrance requires non-null block");
 130   }
 131
 132   const CFGBlock *getBlock() const {
 133     return reinterpret_cast<const CFGBlock*>(getData1());
 134   }
 135
 136   const CFGElement getFirstElement() const {
 137     const CFGBlock *B = getBlock();
 138     return B->empty() ? CFGElement() : B->front();
 139   }
 140
 141   static bool classof(const ProgramPoint* Location) {
 142     return Location->getKind() == BlockEntranceKind;
 143   }
 144 };
 145
 146 class BlockExit : public ProgramPoint {
 147 public:
 148   BlockExit(const CFGBlock *B, const LocationContext *L)
 149     : ProgramPoint(B, BlockExitKind, L) {}
 150
 151   const CFGBlock *getBlock() const {
 152     return reinterpret_cast<const CFGBlock*>(getData1());
 153   }
 154
 155   const Stmt *getTerminator() const {
 156     return getBlock()->getTerminator();
 157   }
 158
 159   static bool classof(const ProgramPoint* Location) {
 160     return Location->getKind() == BlockExitKind;
 161   }
 162 };
 163
 164 class StmtPoint : public ProgramPoint {
 165 public:
 166   StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
 167             const ProgramPointTag *tag)
 168     : ProgramPoint(S, p2, k, L, tag) {}
 169
 170   const Stmt *getStmt() const { return (const Stmt*) getData1(); }
 171
 172   template <typename T>
 173   const T* getStmtAs() const { return llvm::dyn_cast<T>(getStmt()); }
 174
 175   static bool classof(const ProgramPoint* Location) {
 176     unsigned k = Location->getKind();
 177     return k >= PreStmtKind && k <= MaxPostStmtKind;
 178   }
 179 };
 180
 181
 182 class PreStmt : public StmtPoint {
 183 public:
 184   PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
 185           const Stmt *SubStmt = 0)
 186     : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
 187
 188   const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
 189
 190   static bool classof(const ProgramPoint* Location) {
 191     return Location->getKind() == PreStmtKind;
 192   }
 193 };
 194
 195 class PostStmt : public StmtPoint {
 196 protected:
 197   PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
 198            const ProgramPointTag *tag =0)
 199     : StmtPoint(S, data, k, L, tag) {}
 200
 201 public:
 202   explicit PostStmt(const Stmt *S, Kind k,
 203                     const LocationContext *L, const ProgramPointTag *tag = 0)
 204     : StmtPoint(S, NULL, k, L, tag) {}
 205
 206   explicit PostStmt(const Stmt *S, const LocationContext *L,
 207                     const ProgramPointTag *tag = 0)
 208     : StmtPoint(S, NULL, PostStmtKind, L, tag) {}
 209
 210   static bool classof(const ProgramPoint* Location) {
 211     unsigned k = Location->getKind();
 212     return k >= MinPostStmtKind && k <= MaxPostStmtKind;
 213   }
 214 };
 215
 216 // PostCondition represents the post program point of a branch condition.
 217 class PostCondition : public PostStmt {
 218 public:
 219   PostCondition(const Stmt *S, const LocationContext *L,
 220                 const ProgramPointTag *tag = 0)
 221     : PostStmt(S, PostConditionKind, L, tag) {}
 222
 223   static bool classof(const ProgramPoint* Location) {
 224     return Location->getKind() == PostConditionKind;
 225   }
 226 };
 227
 228 class LocationCheck : public StmtPoint {
 229 protected:
 230   LocationCheck(const Stmt *S, const LocationContext *L,
 231                 ProgramPoint::Kind K, const ProgramPointTag *tag)
 232     : StmtPoint(S, NULL, K, L, tag) {}
 233
 234   static bool classof(const ProgramPoint *location) {
 235     unsigned k = location->getKind();
 236     return k == PreLoadKind || k == PreStoreKind;
 237   }
 238 };
 239
 240 class PreLoad : public LocationCheck {
 241 public:
 242   PreLoad(const Stmt *S, const LocationContext *L,
 243           const ProgramPointTag *tag = 0)
 244     : LocationCheck(S, L, PreLoadKind, tag) {}
 245
 246   static bool classof(const ProgramPoint *location) {
 247     return location->getKind() == PreLoadKind;
 248   }
 249 };
 250
 251 class PreStore : public LocationCheck {
 252 public:
 253   PreStore(const Stmt *S, const LocationContext *L,
 254            const ProgramPointTag *tag = 0)
 255   : LocationCheck(S, L, PreStoreKind, tag) {}
 256
 257   static bool classof(const ProgramPoint *location) {
 258     return location->getKind() == PreStoreKind;
 259   }
 260 };
 261
 262 class PostLoad : public PostStmt {
 263 public:
 264   PostLoad(const Stmt *S, const LocationContext *L,
 265            const ProgramPointTag *tag = 0)
 266     : PostStmt(S, PostLoadKind, L, tag) {}
 267
 268   static bool classof(const ProgramPoint* Location) {
 269     return Location->getKind() == PostLoadKind;
 270   }
 271 };
 272
 273 class PostStore : public PostStmt {
 274 public:
 275   PostStore(const Stmt *S, const LocationContext *L,
 276             const ProgramPointTag *tag = 0)
 277     : PostStmt(S, PostStoreKind, L, tag) {}
 278
 279   static bool classof(const ProgramPoint* Location) {
 280     return Location->getKind() == PostStoreKind;
 281   }
 282 };
 283
 284 class PostLValue : public PostStmt {
 285 public:
 286   PostLValue(const Stmt *S, const LocationContext *L,
 287              const ProgramPointTag *tag = 0)
 288     : PostStmt(S, PostLValueKind, L, tag) {}
 289
 290   static bool classof(const ProgramPoint* Location) {
 291     return Location->getKind() == PostLValueKind;
 292   }
 293 };
 294
 295 class PostPurgeDeadSymbols : public PostStmt {
 296 public:
 297   PostPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
 298                        const ProgramPointTag *tag = 0)
 299     : PostStmt(S, PostPurgeDeadSymbolsKind, L, tag) {}
 300
 301   static bool classof(const ProgramPoint* Location) {
 302     return Location->getKind() == PostPurgeDeadSymbolsKind;
 303   }
 304 };
 305
 306 class BlockEdge : public ProgramPoint {
 307 public:
 308   BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
 309     : ProgramPoint(B1, B2, BlockEdgeKind, L) {
 310     assert(B1 && "BlockEdge: source block must be non-null");
 311     assert(B2 && "BlockEdge: destination block must be non-null");
 312   }
 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 /// ProgramPoints can be "tagged" as representing points specific to a given
 369 /// analysis entity.  Tags are abstract annotations, with an associated
 370 /// description and potentially other information.
 371 class ProgramPointTag {
 372 public:
 373   ProgramPointTag(void *tagKind = 0) : TagKind(tagKind) {}
 374   virtual ~ProgramPointTag();
 375   virtual StringRef getTagDescription() const = 0;
 376
 377 protected:
 378   /// Used to implement 'classof' in subclasses.
 379   const void *getTagKind() { return TagKind; }
 380
 381 private:
 382   const void *TagKind;
 383 };
 384
 385 class SimpleProgramPointTag : public ProgramPointTag {
 386   std::string desc;
 387 public:
 388   SimpleProgramPointTag(StringRef description);
 389   StringRef getTagDescription() const;
 390 };
 391
 392 } // end namespace clang
 393
 394
 395 namespace llvm { // Traits specialization for DenseMap
 396
 397 template <> struct DenseMapInfo<clang::ProgramPoint> {
 398
 399 static inline clang::ProgramPoint getEmptyKey() {
 400   uintptr_t x =
 401    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
 402   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
 403 }
 404
 405 static inline clang::ProgramPoint getTombstoneKey() {
 406   uintptr_t x =
 407    reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
 408   return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), 0);
 409 }
 410
 411 static unsigned getHashValue(const clang::ProgramPoint &Loc) {
 412   return Loc.getHashValue();
 413 }
 414
 415 static bool isEqual(const clang::ProgramPoint &L,
 416                     const clang::ProgramPoint &R) {
 417   return L == R;
 418 }
 419
 420 };
 421
 422 template <>
 423 struct isPodLike<clang::ProgramPoint> { static const bool value = true; };
 424
 425 } // end namespace llvm
 426
 427 #endif