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