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