1193326Sed//==- ProgramPoint.h - Program Points for Path-Sensitive Analysis --*- C++ -*-//
2193326Sed//
3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4353358Sdim// See https://llvm.org/LICENSE.txt for license information.
5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6193326Sed//
7193326Sed//===----------------------------------------------------------------------===//
8193326Sed//
9193326Sed//  This file defines the interface ProgramPoint, which identifies a
10193326Sed//  distinct location in a function.
11193326Sed//
12193326Sed//===----------------------------------------------------------------------===//
13193326Sed
14280031Sdim#ifndef LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
15280031Sdim#define LLVM_CLANG_ANALYSIS_PROGRAMPOINT_H
16193326Sed
17327952Sdim#include "clang/Analysis/AnalysisDeclContext.h"
18198092Srdivacky#include "clang/Analysis/CFG.h"
19193326Sed#include "llvm/ADT/DenseMap.h"
20249423Sdim#include "llvm/ADT/FoldingSet.h"
21249423Sdim#include "llvm/ADT/Optional.h"
22234353Sdim#include "llvm/ADT/PointerIntPair.h"
23249423Sdim#include "llvm/ADT/StringRef.h"
24193326Sed#include "llvm/Support/Casting.h"
25249423Sdim#include "llvm/Support/DataTypes.h"
26193326Sed#include <cassert>
27249423Sdim#include <string>
28193326Sed#include <utility>
29193326Sed
30193326Sednamespace clang {
31198092Srdivacky
32234353Sdimclass AnalysisDeclContext;
33204643Srdivackyclass FunctionDecl;
34226633Sdimclass LocationContext;
35341825Sdim
36296417Sdim/// ProgramPoints can be "tagged" as representing points specific to a given
37296417Sdim/// analysis entity.  Tags are abstract annotations, with an associated
38296417Sdim/// description and potentially other information.
39296417Sdimclass ProgramPointTag {
40296417Sdimpublic:
41296417Sdim  ProgramPointTag(void *tagKind = nullptr) : TagKind(tagKind) {}
42296417Sdim  virtual ~ProgramPointTag();
43341825Sdim  virtual StringRef getTagDescription() const = 0;
44296417Sdim
45296417Sdim  /// Used to implement 'isKind' in subclasses.
46353358Sdim  const void *getTagKind() const { return TagKind; }
47341825Sdim
48296417Sdimprivate:
49353358Sdim  const void *const TagKind;
50296417Sdim};
51296417Sdim
52296417Sdimclass SimpleProgramPointTag : public ProgramPointTag {
53296417Sdim  std::string Desc;
54296417Sdimpublic:
55296417Sdim  SimpleProgramPointTag(StringRef MsgProvider, StringRef Msg);
56296417Sdim  StringRef getTagDescription() const override;
57296417Sdim};
58296417Sdim
59193326Sedclass ProgramPoint {
60193326Sedpublic:
61198092Srdivacky  enum Kind { BlockEdgeKind,
62198092Srdivacky              BlockEntranceKind,
63198092Srdivacky              BlockExitKind,
64198092Srdivacky              PreStmtKind,
65239462Sdim              PreStmtPurgeDeadSymbolsKind,
66239462Sdim              PostStmtPurgeDeadSymbolsKind,
67198092Srdivacky              PostStmtKind,
68199482Srdivacky              PreLoadKind,
69198092Srdivacky              PostLoadKind,
70199482Srdivacky              PreStoreKind,
71198092Srdivacky              PostStoreKind,
72221345Sdim              PostConditionKind,
73198092Srdivacky              PostLValueKind,
74341825Sdim              PostAllocatorCallKind,
75239462Sdim              MinPostStmtKind = PostStmtKind,
76341825Sdim              MaxPostStmtKind = PostAllocatorCallKind,
77218893Sdim              PostInitializerKind,
78204643Srdivacky              CallEnterKind,
79239462Sdim              CallExitBeginKind,
80239462Sdim              CallExitEndKind,
81344779Sdim              FunctionExitKind,
82239462Sdim              PreImplicitCallKind,
83239462Sdim              PostImplicitCallKind,
84239462Sdim              MinImplicitCallKind = PreImplicitCallKind,
85239462Sdim              MaxImplicitCallKind = PostImplicitCallKind,
86327952Sdim              LoopExitKind,
87234353Sdim              EpsilonKind};
88193326Sed
89193326Sedprivate:
90239462Sdim  const void *Data1;
91234353Sdim  llvm::PointerIntPair<const void *, 2, unsigned> Data2;
92198092Srdivacky
93198092Srdivacky  // The LocationContext could be NULL to allow ProgramPoint to be used in
94198092Srdivacky  // context insensitive analysis.
95234353Sdim  llvm::PointerIntPair<const LocationContext *, 2, unsigned> L;
96234353Sdim
97239462Sdim  llvm::PointerIntPair<const ProgramPointTag *, 2, unsigned> Tag;
98198092Srdivacky
99193326Sedprotected:
100341825Sdim  ProgramPoint() = default;
101234353Sdim  ProgramPoint(const void *P,
102234353Sdim               Kind k,
103234353Sdim               const LocationContext *l,
104276479Sdim               const ProgramPointTag *tag = nullptr)
105239462Sdim    : Data1(P),
106276479Sdim      Data2(nullptr, (((unsigned) k) >> 0) & 0x3),
107239462Sdim      L(l, (((unsigned) k) >> 2) & 0x3),
108239462Sdim      Tag(tag, (((unsigned) k) >> 4) & 0x3) {
109234353Sdim        assert(getKind() == k);
110234353Sdim        assert(getLocationContext() == l);
111234353Sdim        assert(getData1() == P);
112234353Sdim      }
113341825Sdim
114234353Sdim  ProgramPoint(const void *P1,
115234353Sdim               const void *P2,
116234353Sdim               Kind k,
117234353Sdim               const LocationContext *l,
118276479Sdim               const ProgramPointTag *tag = nullptr)
119239462Sdim    : Data1(P1),
120239462Sdim      Data2(P2, (((unsigned) k) >> 0) & 0x3),
121239462Sdim      L(l, (((unsigned) k) >> 2) & 0x3),
122239462Sdim      Tag(tag, (((unsigned) k) >> 4) & 0x3) {}
123193326Sed
124193326Sedprotected:
125239462Sdim  const void *getData1() const { return Data1; }
126234353Sdim  const void *getData2() const { return Data2.getPointer(); }
127234353Sdim  void setData2(const void *d) { Data2.setPointer(d); }
128193326Sed
129198092Srdivackypublic:
130226633Sdim  /// Create a new ProgramPoint object that is the same as the original
131226633Sdim  /// except for using the specified tag value.
132226633Sdim  ProgramPoint withTag(const ProgramPointTag *tag) const {
133234353Sdim    return ProgramPoint(getData1(), getData2(), getKind(),
134234353Sdim                        getLocationContext(), tag);
135226633Sdim  }
136226633Sdim
137341825Sdim  /// Convert to the specified ProgramPoint type, asserting that this
138249423Sdim  /// ProgramPoint is of the desired type.
139249423Sdim  template<typename T>
140249423Sdim  T castAs() const {
141249423Sdim    assert(T::isKind(*this));
142249423Sdim    T t;
143249423Sdim    ProgramPoint& PP = t;
144249423Sdim    PP = *this;
145249423Sdim    return t;
146249423Sdim  }
147249423Sdim
148341825Sdim  /// Convert to the specified ProgramPoint type, returning None if this
149249423Sdim  /// ProgramPoint is not of the desired type.
150249423Sdim  template<typename T>
151249423Sdim  Optional<T> getAs() const {
152249423Sdim    if (!T::isKind(*this))
153249423Sdim      return None;
154249423Sdim    T t;
155249423Sdim    ProgramPoint& PP = t;
156249423Sdim    PP = *this;
157249423Sdim    return t;
158249423Sdim  }
159249423Sdim
160234353Sdim  Kind getKind() const {
161239462Sdim    unsigned x = Tag.getInt();
162234353Sdim    x <<= 2;
163239462Sdim    x |= L.getInt();
164239462Sdim    x <<= 2;
165234353Sdim    x |= Data2.getInt();
166234353Sdim    return (Kind) x;
167234353Sdim  }
168198092Srdivacky
169341825Sdim  /// Is this a program point corresponding to purge/removal of dead
170239462Sdim  /// symbols and bindings.
171239462Sdim  bool isPurgeKind() {
172239462Sdim    Kind K = getKind();
173239462Sdim    return (K == PostStmtPurgeDeadSymbolsKind ||
174239462Sdim            K == PreStmtPurgeDeadSymbolsKind);
175239462Sdim  }
176218893Sdim
177239462Sdim  const ProgramPointTag *getTag() const { return Tag.getPointer(); }
178239462Sdim
179234353Sdim  const LocationContext *getLocationContext() const {
180234353Sdim    return L.getPointer();
181234353Sdim  }
182198092Srdivacky
183341825Sdim  const StackFrameContext *getStackFrame() const {
184341825Sdim    return getLocationContext()->getStackFrame();
185341825Sdim  }
186341825Sdim
187193326Sed  // For use with DenseMap.  This hash is probably slow.
188193326Sed  unsigned getHashValue() const {
189193326Sed    llvm::FoldingSetNodeID ID;
190198092Srdivacky    Profile(ID);
191193326Sed    return ID.ComputeHash();
192193326Sed  }
193198092Srdivacky
194193326Sed  bool operator==(const ProgramPoint & RHS) const {
195234982Sdim    return Data1 == RHS.Data1 &&
196234353Sdim           Data2 == RHS.Data2 &&
197234353Sdim           L == RHS.L &&
198234353Sdim           Tag == RHS.Tag;
199193326Sed  }
200193326Sed
201226633Sdim  bool operator!=(const ProgramPoint &RHS) const {
202234353Sdim    return Data1 != RHS.Data1 ||
203234353Sdim           Data2 != RHS.Data2 ||
204234353Sdim           L != RHS.L ||
205234353Sdim           Tag != RHS.Tag;
206193326Sed  }
207198092Srdivacky
208193326Sed  void Profile(llvm::FoldingSetNodeID& ID) const {
209234353Sdim    ID.AddInteger((unsigned) getKind());
210234353Sdim    ID.AddPointer(getData1());
211234353Sdim    ID.AddPointer(getData2());
212234353Sdim    ID.AddPointer(getLocationContext());
213239462Sdim    ID.AddPointer(getTag());
214193326Sed  }
215226633Sdim
216353358Sdim  void printJson(llvm::raw_ostream &Out, const char *NL = "\n") const;
217344779Sdim
218344779Sdim  LLVM_DUMP_METHOD void dump() const;
219344779Sdim
220226633Sdim  static ProgramPoint getProgramPoint(const Stmt *S, ProgramPoint::Kind K,
221226633Sdim                                      const LocationContext *LC,
222226633Sdim                                      const ProgramPointTag *tag);
223193326Sed};
224198092Srdivacky
225193326Sedclass BlockEntrance : public ProgramPoint {
226193326Sedpublic:
227226633Sdim  BlockEntrance(const CFGBlock *B, const LocationContext *L,
228276479Sdim                const ProgramPointTag *tag = nullptr)
229341825Sdim    : ProgramPoint(B, BlockEntranceKind, L, tag) {
230226633Sdim    assert(B && "BlockEntrance requires non-null block");
231226633Sdim  }
232198092Srdivacky
233226633Sdim  const CFGBlock *getBlock() const {
234212904Sdim    return reinterpret_cast<const CFGBlock*>(getData1());
235193326Sed  }
236198092Srdivacky
237249423Sdim  Optional<CFGElement> getFirstElement() const {
238226633Sdim    const CFGBlock *B = getBlock();
239249423Sdim    return B->empty() ? Optional<CFGElement>() : B->front();
240193326Sed  }
241341825Sdim
242249423Sdimprivate:
243249423Sdim  friend class ProgramPoint;
244341825Sdim  BlockEntrance() = default;
245249423Sdim  static bool isKind(const ProgramPoint &Location) {
246249423Sdim    return Location.getKind() == BlockEntranceKind;
247193326Sed  }
248193326Sed};
249193326Sed
250193326Sedclass BlockExit : public ProgramPoint {
251193326Sedpublic:
252226633Sdim  BlockExit(const CFGBlock *B, const LocationContext *L)
253198092Srdivacky    : ProgramPoint(B, BlockExitKind, L) {}
254198092Srdivacky
255226633Sdim  const CFGBlock *getBlock() const {
256212904Sdim    return reinterpret_cast<const CFGBlock*>(getData1());
257193326Sed  }
258193326Sed
259226633Sdim  const Stmt *getTerminator() const {
260353358Sdim    return getBlock()->getTerminatorStmt();
261193326Sed  }
262198092Srdivacky
263249423Sdimprivate:
264249423Sdim  friend class ProgramPoint;
265341825Sdim  BlockExit() = default;
266249423Sdim  static bool isKind(const ProgramPoint &Location) {
267249423Sdim    return Location.getKind() == BlockExitKind;
268193326Sed  }
269193326Sed};
270193326Sed
271198092Srdivackyclass StmtPoint : public ProgramPoint {
272198092Srdivackypublic:
273198092Srdivacky  StmtPoint(const Stmt *S, const void *p2, Kind k, const LocationContext *L,
274226633Sdim            const ProgramPointTag *tag)
275243830Sdim    : ProgramPoint(S, p2, k, L, tag) {
276243830Sdim    assert(S);
277243830Sdim  }
278193326Sed
279198092Srdivacky  const Stmt *getStmt() const { return (const Stmt*) getData1(); }
280198092Srdivacky
281198092Srdivacky  template <typename T>
282249423Sdim  const T* getStmtAs() const { return dyn_cast<T>(getStmt()); }
283198092Srdivacky
284249423Sdimprotected:
285341825Sdim  StmtPoint() = default;
286249423Sdimprivate:
287249423Sdim  friend class ProgramPoint;
288249423Sdim  static bool isKind(const ProgramPoint &Location) {
289249423Sdim    unsigned k = Location.getKind();
290198092Srdivacky    return k >= PreStmtKind && k <= MaxPostStmtKind;
291198092Srdivacky  }
292198092Srdivacky};
293198092Srdivacky
294198092Srdivacky
295198092Srdivackyclass PreStmt : public StmtPoint {
296193326Sedpublic:
297226633Sdim  PreStmt(const Stmt *S, const LocationContext *L, const ProgramPointTag *tag,
298276479Sdim          const Stmt *SubStmt = nullptr)
299198092Srdivacky    : StmtPoint(S, SubStmt, PreStmtKind, L, tag) {}
300193326Sed
301198092Srdivacky  const Stmt *getSubStmt() const { return (const Stmt*) getData2(); }
302193326Sed
303249423Sdimprivate:
304249423Sdim  friend class ProgramPoint;
305341825Sdim  PreStmt() = default;
306249423Sdim  static bool isKind(const ProgramPoint &Location) {
307249423Sdim    return Location.getKind() == PreStmtKind;
308198092Srdivacky  }
309198092Srdivacky};
310198092Srdivacky
311198092Srdivackyclass PostStmt : public StmtPoint {
312198092Srdivackyprotected:
313341825Sdim  PostStmt() = default;
314226633Sdim  PostStmt(const Stmt *S, const void *data, Kind k, const LocationContext *L,
315276479Sdim           const ProgramPointTag *tag = nullptr)
316198092Srdivacky    : StmtPoint(S, data, k, L, tag) {}
317198092Srdivacky
318198092Srdivackypublic:
319276479Sdim  explicit PostStmt(const Stmt *S, Kind k, const LocationContext *L,
320276479Sdim                    const ProgramPointTag *tag = nullptr)
321276479Sdim    : StmtPoint(S, nullptr, k, L, tag) {}
322218893Sdim
323226633Sdim  explicit PostStmt(const Stmt *S, const LocationContext *L,
324276479Sdim                    const ProgramPointTag *tag = nullptr)
325276479Sdim    : StmtPoint(S, nullptr, PostStmtKind, L, tag) {}
326198092Srdivacky
327249423Sdimprivate:
328249423Sdim  friend class ProgramPoint;
329249423Sdim  static bool isKind(const ProgramPoint &Location) {
330249423Sdim    unsigned k = Location.getKind();
331193326Sed    return k >= MinPostStmtKind && k <= MaxPostStmtKind;
332193326Sed  }
333193326Sed};
334193326Sed
335344779Sdimclass FunctionExitPoint : public ProgramPoint {
336344779Sdimpublic:
337344779Sdim  explicit FunctionExitPoint(const ReturnStmt *S,
338344779Sdim                             const LocationContext *LC,
339344779Sdim                             const ProgramPointTag *tag = nullptr)
340344779Sdim      : ProgramPoint(S, FunctionExitKind, LC, tag) {}
341344779Sdim
342344779Sdim  const CFGBlock *getBlock() const {
343344779Sdim    return &getLocationContext()->getCFG()->getExit();
344344779Sdim  }
345344779Sdim
346344779Sdim  const ReturnStmt *getStmt() const {
347344779Sdim    return reinterpret_cast<const ReturnStmt *>(getData1());
348344779Sdim  }
349344779Sdim
350344779Sdimprivate:
351344779Sdim  friend class ProgramPoint;
352344779Sdim  FunctionExitPoint() = default;
353344779Sdim  static bool isKind(const ProgramPoint &Location) {
354344779Sdim    return Location.getKind() == FunctionExitKind;
355344779Sdim  }
356344779Sdim};
357344779Sdim
358221345Sdim// PostCondition represents the post program point of a branch condition.
359221345Sdimclass PostCondition : public PostStmt {
360221345Sdimpublic:
361226633Sdim  PostCondition(const Stmt *S, const LocationContext *L,
362276479Sdim                const ProgramPointTag *tag = nullptr)
363221345Sdim    : PostStmt(S, PostConditionKind, L, tag) {}
364221345Sdim
365249423Sdimprivate:
366249423Sdim  friend class ProgramPoint;
367341825Sdim  PostCondition() = default;
368249423Sdim  static bool isKind(const ProgramPoint &Location) {
369249423Sdim    return Location.getKind() == PostConditionKind;
370221345Sdim  }
371221345Sdim};
372221345Sdim
373199482Srdivackyclass LocationCheck : public StmtPoint {
374199482Srdivackyprotected:
375341825Sdim  LocationCheck() = default;
376199482Srdivacky  LocationCheck(const Stmt *S, const LocationContext *L,
377226633Sdim                ProgramPoint::Kind K, const ProgramPointTag *tag)
378276479Sdim    : StmtPoint(S, nullptr, K, L, tag) {}
379341825Sdim
380249423Sdimprivate:
381249423Sdim  friend class ProgramPoint;
382249423Sdim  static bool isKind(const ProgramPoint &location) {
383249423Sdim    unsigned k = location.getKind();
384199482Srdivacky    return k == PreLoadKind || k == PreStoreKind;
385193326Sed  }
386193326Sed};
387341825Sdim
388199482Srdivackyclass PreLoad : public LocationCheck {
389193326Sedpublic:
390226633Sdim  PreLoad(const Stmt *S, const LocationContext *L,
391276479Sdim          const ProgramPointTag *tag = nullptr)
392199482Srdivacky    : LocationCheck(S, L, PreLoadKind, tag) {}
393341825Sdim
394249423Sdimprivate:
395249423Sdim  friend class ProgramPoint;
396341825Sdim  PreLoad() = default;
397249423Sdim  static bool isKind(const ProgramPoint &location) {
398249423Sdim    return location.getKind() == PreLoadKind;
399193326Sed  }
400193326Sed};
401198092Srdivacky
402199482Srdivackyclass PreStore : public LocationCheck {
403193326Sedpublic:
404226633Sdim  PreStore(const Stmt *S, const LocationContext *L,
405276479Sdim           const ProgramPointTag *tag = nullptr)
406199482Srdivacky  : LocationCheck(S, L, PreStoreKind, tag) {}
407341825Sdim
408249423Sdimprivate:
409249423Sdim  friend class ProgramPoint;
410341825Sdim  PreStore() = default;
411249423Sdim  static bool isKind(const ProgramPoint &location) {
412249423Sdim    return location.getKind() == PreStoreKind;
413193326Sed  }
414193326Sed};
415198092Srdivacky
416193326Sedclass PostLoad : public PostStmt {
417193326Sedpublic:
418226633Sdim  PostLoad(const Stmt *S, const LocationContext *L,
419276479Sdim           const ProgramPointTag *tag = nullptr)
420198092Srdivacky    : PostStmt(S, PostLoadKind, L, tag) {}
421198092Srdivacky
422249423Sdimprivate:
423249423Sdim  friend class ProgramPoint;
424341825Sdim  PostLoad() = default;
425249423Sdim  static bool isKind(const ProgramPoint &Location) {
426249423Sdim    return Location.getKind() == PostLoadKind;
427193326Sed  }
428193326Sed};
429198092Srdivacky
430341825Sdim/// Represents a program point after a store evaluation.
431193326Sedclass PostStore : public PostStmt {
432193326Sedpublic:
433234353Sdim  /// Construct the post store point.
434341825Sdim  /// \param Loc can be used to store the information about the location
435234353Sdim  /// used in the form it was uttered in the code.
436234353Sdim  PostStore(const Stmt *S, const LocationContext *L, const void *Loc,
437276479Sdim            const ProgramPointTag *tag = nullptr)
438234353Sdim    : PostStmt(S, PostStoreKind, L, tag) {
439276479Sdim    assert(getData2() == nullptr);
440234353Sdim    setData2(Loc);
441234353Sdim  }
442198092Srdivacky
443341825Sdim  /// Returns the information about the location used in the store,
444234353Sdim  /// how it was uttered in the code.
445234353Sdim  const void *getLocationValue() const {
446234353Sdim    return getData2();
447234353Sdim  }
448234353Sdim
449249423Sdimprivate:
450249423Sdim  friend class ProgramPoint;
451341825Sdim  PostStore() = default;
452249423Sdim  static bool isKind(const ProgramPoint &Location) {
453249423Sdim    return Location.getKind() == PostStoreKind;
454249423Sdim  }
455193326Sed};
456193326Sed
457193326Sedclass PostLValue : public PostStmt {
458193326Sedpublic:
459226633Sdim  PostLValue(const Stmt *S, const LocationContext *L,
460276479Sdim             const ProgramPointTag *tag = nullptr)
461198092Srdivacky    : PostStmt(S, PostLValueKind, L, tag) {}
462198092Srdivacky
463249423Sdimprivate:
464249423Sdim  friend class ProgramPoint;
465341825Sdim  PostLValue() = default;
466249423Sdim  static bool isKind(const ProgramPoint &Location) {
467249423Sdim    return Location.getKind() == PostLValueKind;
468193326Sed  }
469198092Srdivacky};
470198092Srdivacky
471239462Sdim/// Represents a point after we ran remove dead bindings BEFORE
472239462Sdim/// processing the given statement.
473239462Sdimclass PreStmtPurgeDeadSymbols : public StmtPoint {
474193326Sedpublic:
475239462Sdim  PreStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
476276479Sdim                       const ProgramPointTag *tag = nullptr)
477276479Sdim    : StmtPoint(S, nullptr, PreStmtPurgeDeadSymbolsKind, L, tag) { }
478198092Srdivacky
479249423Sdimprivate:
480249423Sdim  friend class ProgramPoint;
481341825Sdim  PreStmtPurgeDeadSymbols() = default;
482249423Sdim  static bool isKind(const ProgramPoint &Location) {
483249423Sdim    return Location.getKind() == PreStmtPurgeDeadSymbolsKind;
484193326Sed  }
485193326Sed};
486198092Srdivacky
487239462Sdim/// Represents a point after we ran remove dead bindings AFTER
488239462Sdim/// processing the  given statement.
489239462Sdimclass PostStmtPurgeDeadSymbols : public StmtPoint {
490239462Sdimpublic:
491239462Sdim  PostStmtPurgeDeadSymbols(const Stmt *S, const LocationContext *L,
492276479Sdim                       const ProgramPointTag *tag = nullptr)
493276479Sdim    : StmtPoint(S, nullptr, PostStmtPurgeDeadSymbolsKind, L, tag) { }
494239462Sdim
495249423Sdimprivate:
496249423Sdim  friend class ProgramPoint;
497341825Sdim  PostStmtPurgeDeadSymbols() = default;
498249423Sdim  static bool isKind(const ProgramPoint &Location) {
499249423Sdim    return Location.getKind() == PostStmtPurgeDeadSymbolsKind;
500239462Sdim  }
501239462Sdim};
502239462Sdim
503193326Sedclass BlockEdge : public ProgramPoint {
504193326Sedpublic:
505226633Sdim  BlockEdge(const CFGBlock *B1, const CFGBlock *B2, const LocationContext *L)
506226633Sdim    : ProgramPoint(B1, B2, BlockEdgeKind, L) {
507226633Sdim    assert(B1 && "BlockEdge: source block must be non-null");
508341825Sdim    assert(B2 && "BlockEdge: destination block must be non-null");
509226633Sdim  }
510198092Srdivacky
511226633Sdim  const CFGBlock *getSrc() const {
512212904Sdim    return static_cast<const CFGBlock*>(getData1());
513193326Sed  }
514198092Srdivacky
515226633Sdim  const CFGBlock *getDst() const {
516212904Sdim    return static_cast<const CFGBlock*>(getData2());
517193326Sed  }
518198092Srdivacky
519249423Sdimprivate:
520249423Sdim  friend class ProgramPoint;
521341825Sdim  BlockEdge() = default;
522249423Sdim  static bool isKind(const ProgramPoint &Location) {
523249423Sdim    return Location.getKind() == BlockEdgeKind;
524193326Sed  }
525193326Sed};
526193326Sed
527218893Sdimclass PostInitializer : public ProgramPoint {
528218893Sdimpublic:
529341825Sdim  /// Construct a PostInitializer point that represents a location after
530249423Sdim  ///   CXXCtorInitializer expression evaluation.
531249423Sdim  ///
532249423Sdim  /// \param I The initializer.
533249423Sdim  /// \param Loc The location of the field being initialized.
534249423Sdim  PostInitializer(const CXXCtorInitializer *I,
535249423Sdim                  const void *Loc,
536218893Sdim                  const LocationContext *L)
537249423Sdim    : ProgramPoint(I, Loc, PostInitializerKind, L) {}
538218893Sdim
539249423Sdim  const CXXCtorInitializer *getInitializer() const {
540249423Sdim    return static_cast<const CXXCtorInitializer *>(getData1());
541218893Sdim  }
542249423Sdim
543341825Sdim  /// Returns the location of the field.
544249423Sdim  const void *getLocationValue() const {
545249423Sdim    return getData2();
546249423Sdim  }
547249423Sdim
548249423Sdimprivate:
549249423Sdim  friend class ProgramPoint;
550341825Sdim  PostInitializer() = default;
551249423Sdim  static bool isKind(const ProgramPoint &Location) {
552249423Sdim    return Location.getKind() == PostInitializerKind;
553249423Sdim  }
554218893Sdim};
555218893Sdim
556239462Sdim/// Represents an implicit call event.
557239462Sdim///
558239462Sdim/// The nearest statement is provided for diagnostic purposes.
559239462Sdimclass ImplicitCallPoint : public ProgramPoint {
560204643Srdivackypublic:
561239462Sdim  ImplicitCallPoint(const Decl *D, SourceLocation Loc, Kind K,
562239462Sdim                    const LocationContext *L, const ProgramPointTag *Tag)
563239462Sdim    : ProgramPoint(Loc.getPtrEncoding(), D, K, L, Tag) {}
564239462Sdim
565239462Sdim  const Decl *getDecl() const { return static_cast<const Decl *>(getData2()); }
566239462Sdim  SourceLocation getLocation() const {
567239462Sdim    return SourceLocation::getFromPtrEncoding(getData1());
568239462Sdim  }
569239462Sdim
570249423Sdimprotected:
571341825Sdim  ImplicitCallPoint() = default;
572249423Sdimprivate:
573249423Sdim  friend class ProgramPoint;
574249423Sdim  static bool isKind(const ProgramPoint &Location) {
575249423Sdim    return Location.getKind() >= MinImplicitCallKind &&
576249423Sdim           Location.getKind() <= MaxImplicitCallKind;
577239462Sdim  }
578239462Sdim};
579239462Sdim
580239462Sdim/// Represents a program point just before an implicit call event.
581239462Sdim///
582239462Sdim/// Explicit calls will appear as PreStmt program points.
583239462Sdimclass PreImplicitCall : public ImplicitCallPoint {
584239462Sdimpublic:
585276479Sdim  PreImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
586276479Sdim                  const ProgramPointTag *Tag = nullptr)
587239462Sdim    : ImplicitCallPoint(D, Loc, PreImplicitCallKind, L, Tag) {}
588239462Sdim
589249423Sdimprivate:
590249423Sdim  friend class ProgramPoint;
591341825Sdim  PreImplicitCall() = default;
592249423Sdim  static bool isKind(const ProgramPoint &Location) {
593249423Sdim    return Location.getKind() == PreImplicitCallKind;
594239462Sdim  }
595239462Sdim};
596239462Sdim
597239462Sdim/// Represents a program point just after an implicit call event.
598239462Sdim///
599239462Sdim/// Explicit calls will appear as PostStmt program points.
600239462Sdimclass PostImplicitCall : public ImplicitCallPoint {
601239462Sdimpublic:
602276479Sdim  PostImplicitCall(const Decl *D, SourceLocation Loc, const LocationContext *L,
603276479Sdim                   const ProgramPointTag *Tag = nullptr)
604239462Sdim    : ImplicitCallPoint(D, Loc, PostImplicitCallKind, L, Tag) {}
605239462Sdim
606249423Sdimprivate:
607249423Sdim  friend class ProgramPoint;
608341825Sdim  PostImplicitCall() = default;
609249423Sdim  static bool isKind(const ProgramPoint &Location) {
610249423Sdim    return Location.getKind() == PostImplicitCallKind;
611239462Sdim  }
612239462Sdim};
613239462Sdim
614341825Sdimclass PostAllocatorCall : public StmtPoint {
615341825Sdimpublic:
616341825Sdim  PostAllocatorCall(const Stmt *S, const LocationContext *L,
617341825Sdim                    const ProgramPointTag *Tag = nullptr)
618341825Sdim      : StmtPoint(S, nullptr, PostAllocatorCallKind, L, Tag) {}
619341825Sdim
620341825Sdimprivate:
621341825Sdim  friend class ProgramPoint;
622341825Sdim  PostAllocatorCall() = default;
623341825Sdim  static bool isKind(const ProgramPoint &Location) {
624341825Sdim    return Location.getKind() == PostAllocatorCallKind;
625341825Sdim  }
626341825Sdim};
627341825Sdim
628239462Sdim/// Represents a point when we begin processing an inlined call.
629243830Sdim/// CallEnter uses the caller's location context.
630239462Sdimclass CallEnter : public ProgramPoint {
631239462Sdimpublic:
632341825Sdim  CallEnter(const Stmt *stmt, const StackFrameContext *calleeCtx,
633218893Sdim            const LocationContext *callerCtx)
634276479Sdim    : ProgramPoint(stmt, calleeCtx, CallEnterKind, callerCtx, nullptr) {}
635198092Srdivacky
636204643Srdivacky  const Stmt *getCallExpr() const {
637204643Srdivacky    return static_cast<const Stmt *>(getData1());
638204643Srdivacky  }
639204643Srdivacky
640218893Sdim  const StackFrameContext *getCalleeContext() const {
641218893Sdim    return static_cast<const StackFrameContext *>(getData2());
642204643Srdivacky  }
643204643Srdivacky
644309124Sdim  /// Returns the entry block in the CFG for the entered function.
645309124Sdim  const CFGBlock *getEntry() const {
646309124Sdim    const StackFrameContext *CalleeCtx = getCalleeContext();
647309124Sdim    const CFG *CalleeCFG = CalleeCtx->getCFG();
648309124Sdim    return &(CalleeCFG->getEntry());
649309124Sdim  }
650309124Sdim
651249423Sdimprivate:
652249423Sdim  friend class ProgramPoint;
653341825Sdim  CallEnter() = default;
654249423Sdim  static bool isKind(const ProgramPoint &Location) {
655249423Sdim    return Location.getKind() == CallEnterKind;
656204643Srdivacky  }
657204643Srdivacky};
658204643Srdivacky
659239462Sdim/// Represents a point when we start the call exit sequence (for inlined call).
660239462Sdim///
661239462Sdim/// The call exit is simulated with a sequence of nodes, which occur between
662239462Sdim/// CallExitBegin and CallExitEnd. The following operations occur between the
663239462Sdim/// two program points:
664239462Sdim/// - CallExitBegin
665239462Sdim/// - Bind the return value
666239462Sdim/// - Run Remove dead bindings (to clean up the dead symbols from the callee).
667239462Sdim/// - CallExitEnd
668239462Sdimclass CallExitBegin : public ProgramPoint {
669204643Srdivackypublic:
670239462Sdim  // CallExitBegin uses the callee's location context.
671314564Sdim  CallExitBegin(const StackFrameContext *L, const ReturnStmt *RS)
672314564Sdim    : ProgramPoint(RS, CallExitBeginKind, L, nullptr) { }
673204643Srdivacky
674341825Sdim  const ReturnStmt *getReturnStmt() const {
675341825Sdim    return static_cast<const ReturnStmt *>(getData1());
676341825Sdim  }
677341825Sdim
678249423Sdimprivate:
679249423Sdim  friend class ProgramPoint;
680341825Sdim  CallExitBegin() = default;
681249423Sdim  static bool isKind(const ProgramPoint &Location) {
682249423Sdim    return Location.getKind() == CallExitBeginKind;
683204643Srdivacky  }
684204643Srdivacky};
685204643Srdivacky
686239462Sdim/// Represents a point when we finish the call exit sequence (for inlined call).
687239462Sdim/// \sa CallExitBegin
688239462Sdimclass CallExitEnd : public ProgramPoint {
689239462Sdimpublic:
690239462Sdim  // CallExitEnd uses the caller's location context.
691239462Sdim  CallExitEnd(const StackFrameContext *CalleeCtx,
692239462Sdim              const LocationContext *CallerCtx)
693276479Sdim    : ProgramPoint(CalleeCtx, CallExitEndKind, CallerCtx, nullptr) {}
694239462Sdim
695239462Sdim  const StackFrameContext *getCalleeContext() const {
696239462Sdim    return static_cast<const StackFrameContext *>(getData1());
697239462Sdim  }
698239462Sdim
699249423Sdimprivate:
700249423Sdim  friend class ProgramPoint;
701341825Sdim  CallExitEnd() = default;
702249423Sdim  static bool isKind(const ProgramPoint &Location) {
703249423Sdim    return Location.getKind() == CallExitEndKind;
704239462Sdim  }
705239462Sdim};
706239462Sdim
707327952Sdim/// Represents a point when we exit a loop.
708327952Sdim/// When this ProgramPoint is encountered we can be sure that the symbolic
709327952Sdim/// execution of the corresponding LoopStmt is finished on the given path.
710327952Sdim/// Note: It is possible to encounter a LoopExit element when we haven't even
711327952Sdim/// encountered the loop itself. At the current state not all loop exits will
712327952Sdim/// result in a LoopExit program point.
713327952Sdimclass LoopExit : public ProgramPoint {
714327952Sdimpublic:
715327952Sdim    LoopExit(const Stmt *LoopStmt, const LocationContext *LC)
716327952Sdim            : ProgramPoint(LoopStmt, nullptr, LoopExitKind, LC) {}
717327952Sdim
718327952Sdim    const Stmt *getLoopStmt() const {
719327952Sdim      return static_cast<const Stmt *>(getData1());
720327952Sdim    }
721327952Sdim
722327952Sdimprivate:
723327952Sdim    friend class ProgramPoint;
724341825Sdim    LoopExit() = default;
725327952Sdim    static bool isKind(const ProgramPoint &Location) {
726327952Sdim      return Location.getKind() == LoopExitKind;
727327952Sdim    }
728327952Sdim};
729327952Sdim
730234353Sdim/// This is a meta program point, which should be skipped by all the diagnostic
731234353Sdim/// reasoning etc.
732234353Sdimclass EpsilonPoint : public ProgramPoint {
733234353Sdimpublic:
734234353Sdim  EpsilonPoint(const LocationContext *L, const void *Data1,
735276479Sdim               const void *Data2 = nullptr,
736276479Sdim               const ProgramPointTag *tag = nullptr)
737234353Sdim    : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
738234353Sdim
739234353Sdim  const void *getData() const { return getData1(); }
740234353Sdim
741249423Sdimprivate:
742249423Sdim  friend class ProgramPoint;
743341825Sdim  EpsilonPoint() = default;
744249423Sdim  static bool isKind(const ProgramPoint &Location) {
745249423Sdim    return Location.getKind() == EpsilonKind;
746234353Sdim  }
747234353Sdim};
748234353Sdim
749193326Sed} // end namespace clang
750193326Sed
751193326Sed
752198092Srdivackynamespace llvm { // Traits specialization for DenseMap
753198092Srdivacky
754193326Sedtemplate <> struct DenseMapInfo<clang::ProgramPoint> {
755193326Sed
756193326Sedstatic inline clang::ProgramPoint getEmptyKey() {
757193326Sed  uintptr_t x =
758198092Srdivacky   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getEmptyKey()) & ~0x7;
759276479Sdim  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
760193326Sed}
761193326Sed
762193326Sedstatic inline clang::ProgramPoint getTombstoneKey() {
763193326Sed  uintptr_t x =
764198092Srdivacky   reinterpret_cast<uintptr_t>(DenseMapInfo<void*>::getTombstoneKey()) & ~0x7;
765276479Sdim  return clang::BlockEntrance(reinterpret_cast<clang::CFGBlock*>(x), nullptr);
766193326Sed}
767193326Sed
768226633Sdimstatic unsigned getHashValue(const clang::ProgramPoint &Loc) {
769193326Sed  return Loc.getHashValue();
770193326Sed}
771193326Sed
772226633Sdimstatic bool isEqual(const clang::ProgramPoint &L,
773226633Sdim                    const clang::ProgramPoint &R) {
774193326Sed  return L == R;
775193326Sed}
776193326Sed
777193326Sed};
778341825Sdim
779193326Sed} // end namespace llvm
780193326Sed
781193326Sed#endif
782