SymbolManager.h Source File (original) (raw)

14#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H

15#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H

25#include "llvm/ADT/DenseMap.h"

26#include "llvm/ADT/DenseSet.h"

27#include "llvm/ADT/FoldingSet.h"

28#include "llvm/ADT/ImmutableSet.h"

29#include "llvm/ADT/iterator_range.h"

30#include "llvm/Support/Allocator.h"

31#include

35class ASTContext;

36class Stmt;

38namespace ento {

40class BasicValueFactory;

41class StoreManager;

49 : SymbolData(SymbolRegionValueKind, sym), R(r) {

50 assert(r);

52 }

54public:

55 LLVM_ATTRIBUTE_RETURNS_NONNULL

59 profile.AddInteger((unsigned) SymbolRegionValueKind);

60 profile.AddPointer(R);

61 }

63 void Profile(llvm::FoldingSetNodeID& profile) override {

65 }

67 StringRef getKindStr() const override;

69 void dumpToStream(raw_ostream &os) const override;

76 return SE->getKind() == SymbolRegionValueKind;

77 }

78};

83 const Stmt *S;

85 unsigned Count;

87 const void *SymbolTag;

91 QualType t, unsigned count, const void *symbolTag)

92 : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),

93 LCtx(lctx), SymbolTag(symbolTag) {

99 assert(lctx);

101 }

102

103public:

104

106 unsigned getCount() const { return Count; }

107

108 const void *getTag() const { return SymbolTag; }

109

111

112 StringRef getKindStr() const override;

113

114 void dumpToStream(raw_ostream &os) const override;

115

116 static void Profile(llvm::FoldingSetNodeID &profile, const Stmt *S,

118 const void *SymbolTag) {

119 profile.AddInteger((unsigned)SymbolConjuredKind);

120 profile.AddPointer(S);

121 profile.AddPointer(LCtx);

122 profile.Add(T);

123 profile.AddInteger(Count);

124 profile.AddPointer(SymbolTag);

125 }

126

127 void Profile(llvm::FoldingSetNodeID& profile) override {

128 Profile(profile, S, LCtx, T, Count, SymbolTag);

129 }

130

131

133 return SE->getKind() == SymbolConjuredKind;

134 }

135};

136

137

138

142

145 : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {

146 assert(parent);

147 assert(r);

149 }

150

151public:

152 LLVM_ATTRIBUTE_RETURNS_NONNULL

154 LLVM_ATTRIBUTE_RETURNS_NONNULL

156

158

159 StringRef getKindStr() const override;

160

161 void dumpToStream(raw_ostream &os) const override;

163

166 profile.AddInteger((unsigned) SymbolDerivedKind);

167 profile.AddPointer(r);

168 profile.AddPointer(parent);

169 }

170

171 void Profile(llvm::FoldingSetNodeID& profile) override {

172 Profile(profile, parentSymbol, R);

173 }

174

175

177 return SE->getKind() == SymbolDerivedKind;

178 }

179};

180

181

182

183

186

189 : SymbolData(SymbolExtentKind, sym), R(r) {

190 assert(r);

191 }

192

193public:

194 LLVM_ATTRIBUTE_RETURNS_NONNULL

196

198

199 StringRef getKindStr() const override;

200

201 void dumpToStream(raw_ostream &os) const override;

202

203 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {

204 profile.AddInteger((unsigned) SymbolExtentKind);

205 profile.AddPointer(R);

206 }

207

208 void Profile(llvm::FoldingSetNodeID& profile) override {

210 }

211

212

214 return SE->getKind() == SymbolExtentKind;

215 }

216};

217

218

219

220

221

224 const Stmt *S;

227

228

229 unsigned Count;

230 const void *Tag;

231

234 const LocationContext *LCtx, unsigned count, const void *tag)

235 : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx),

236 Count(count), Tag(tag) {

237 assert(r);

238 assert(s);

240 assert(LCtx);

241 assert(tag);

242 }

243

244 public:

245 LLVM_ATTRIBUTE_RETURNS_NONNULL

247

248 LLVM_ATTRIBUTE_RETURNS_NONNULL

250

251 LLVM_ATTRIBUTE_RETURNS_NONNULL

253

254 unsigned getCount() const { return Count; }

255

256 LLVM_ATTRIBUTE_RETURNS_NONNULL

257 const void *getTag() const { return Tag; }

258

260

261 StringRef getKindStr() const override;

262

263 void dumpToStream(raw_ostream &os) const override;

264

267 unsigned Count, const void *Tag) {

268 profile.AddInteger((unsigned)SymbolMetadataKind);

269 profile.AddPointer(R);

270 profile.AddPointer(S);

271 profile.Add(T);

272 profile.AddPointer(LCtx);

273 profile.AddInteger(Count);

274 profile.AddPointer(Tag);

275 }

276

277 void Profile(llvm::FoldingSetNodeID& profile) override {

278 Profile(profile, R, S, T, LCtx, Count, Tag);

279 }

280

281

283 return SE->getKind() == SymbolMetadataKind;

284 }

285};

286

287

290

291

293

294

296

299 : SymExpr(SymbolCastKind, Sym), Operand(In), FromTy(From), ToTy(To) {

300 assert(In);

302

303

304 }

305

306public:

309 Complexity = 1 + Operand->computeComplexity();

311 }

312

314

315 LLVM_ATTRIBUTE_RETURNS_NONNULL

317

318 void dumpToStream(raw_ostream &os) const override;

319

320 static void Profile(llvm::FoldingSetNodeID& ID,

322 ID.AddInteger((unsigned) SymbolCastKind);

323 ID.AddPointer(In);

324 ID.Add(From);

325 ID.Add(To);

326 }

327

328 void Profile(llvm::FoldingSetNodeID& ID) override {

329 Profile(ID, Operand, FromTy, ToTy);

330 }

331

332

334 return SE->getKind() == SymbolCastKind;

335 }

336};

337

338

343

347 : SymExpr(UnarySymExprKind, Sym), Operand(In), Op(Op), T(T) {

348

349

350 assert((Op == UO_Minus || Op == UO_Not) && "non-supported unary expression");

351

352

353

355 assert( Loc::isLocType (T) && "unary symbol should be nonloc");

356 }

357

358public:

361 Complexity = 1 + Operand->computeComplexity();

363 }

364

368

369 void dumpToStream(raw_ostream &os) const override;

370

373 ID.AddInteger((unsigned)UnarySymExprKind);

374 ID.AddPointer(In);

375 ID.AddInteger(Op);

376 ID.Add(T);

377 }

378

379 void Profile(llvm::FoldingSetNodeID &ID) override {

381 }

382

383

385 return SE->getKind() == UnarySymExprKind;

386 }

387};

388

389

393

394protected:

396 : SymExpr(k, Sym), Op(op), T(t) {

398

399

400

402 }

403

404public:

405

406

408

410

411

414 return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;

415 }

416

417protected:

419 return Value->computeComplexity();

420 }

422 return 1;

423 }

424

427

431};

432

433

434template <class LHSTYPE, class RHSTYPE, SymExpr::Kind ClassKind>

436 LHSTYPE LHS;

437 RHSTYPE RHS;

438

442 : BinarySymExpr(Sym, ClassKind, op, t), LHS(lhs), RHS(rhs) {

445 }

446

447public:

452 }

453

454 LHSTYPE getLHS() const { return LHS; }

455 RHSTYPE getRHS() const { return RHS; }

456

462 }

463

464 static void Profile(llvm::FoldingSetNodeID &ID, LHSTYPE lhs,

466 ID.AddInteger((unsigned)ClassKind);

468 ID.AddInteger(op);

470 ID.Add(t);

471 }

472

473 void Profile(llvm::FoldingSetNodeID &ID) override {

475 }

476

477

479};

480

481

483 SymExpr::Kind::SymIntExprKind>;

484

485

487 SymExpr::Kind::IntSymExprKind>;

488

489

491 SymExpr::Kind::SymSymExprKind>;

492

495 llvm::BumpPtrAllocator &Alloc;

496

497public:

498 explicit SymExprAllocator(llvm::BumpPtrAllocator &Alloc) : Alloc(Alloc) {}

499

500 template <class SymT, typename... ArgsT> SymT *make(ArgsT &&...Args) {

501 return new (Alloc) SymT(nextID(), std::forward(Args)...);

502 }

503

504private:

505 SymbolID nextID() { return NextSymbolID++; }

506};

507

509 using DataSetTy = llvm::FoldingSet;

510 using SymbolDependTy =

511 llvm::DenseMap<SymbolRef, std::unique_ptr>;

512

513 DataSetTy DataSet;

514

515

516

517 SymbolDependTy SymbolDependencies;

518

522

523public:

525 llvm::BumpPtrAllocator &bpalloc)

526 : SymbolDependencies(16), Alloc(bpalloc), BV(bv), Ctx(ctx) {}

527

529

530

531

532

533 template <typename SymExprT, typename... Args>

534 const SymExprT *acquire(Args &&...args);

535

539 const void *SymbolTag = nullptr) {

540 return acquire(E, LCtx, T, VisitCount, SymbolTag);

541 }

542

546 const void *SymbolTag = nullptr) {

548 }

549

552 }

553

554

555

556

558

560

563};

564

565

567 enum SymbolStatus {

568 NotProcessed,

569 HaveMarkedDependents

570 };

571

572 using SymbolSetTy = llvm::DenseSet;

573 using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;

574 using RegionSetTy = llvm::DenseSet<const MemRegion *>;

575

576 SymbolMapTy TheLiving;

577 SymbolSetTy MetadataInUse;

578

579 RegionSetTy LiveRegionRoots;

580

581

582

583

584 RegionSetTy LazilyCopiedRegionRoots;

585

590 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;

591

592public:

593

594

595

596

597

598

599

602 : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {}

603

604

606

610 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;

611

612

613

614

615

616

618

619

620

621

622

623

624

625

627

628 llvm::iterator_rangeRegionSetTy::const\_iterator regions() const {

629 return LiveRegionRoots;

630 }

631

632

633

634

635

638 }

639

643

644

645

647

648private:

649 bool isLazilyCopiedRegion(const MemRegion *region) const;

650

651

652

653 bool isReadableRegion(const MemRegion *region);

654

655

656 void markDependentsLive(SymbolRef sym);

657};

658

660protected:

662

663public:

667

668

669

672

673

674

675

676

679};

680

681template <typename T, typename... Args>

683 llvm::FoldingSetNodeID profile;

684 T::Profile(profile, args...);

685 void *InsertPos;

686 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);

687 if (!SD) {

688 SD = Alloc.make<T>(std::forward(args)...);

689 DataSet.InsertNode(SD, InsertPos);

690 }

691 return cast(SD);

692}

693

694}

695

696}

697

698

699

700

701

702

703template <>

704struct llvm::ImutContainerInfo<clang::ento::SymbolRef>

712

715

718 }

719

722 }

723

724

725

726

728};

729

730#endif

This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...

Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.

llvm::DenseMap< const CFGBlock *, unsigned > VisitCount

C Language Family Type Representation.

__device__ __2f16 float __ockl_bool s

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

This represents one expression.

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

A (possibly-)qualified type.

It represents a stack frame of the call stack (based on CallEvent).

Stmt - This represents one statement.

A safe wrapper around APSInt objects allocated and owned by BasicValueFactory.

Template implementation for all binary symbolic expressions.

static void Profile(llvm::FoldingSetNodeID &ID, LHSTYPE lhs, BinaryOperator::Opcode op, RHSTYPE rhs, QualType t)

void Profile(llvm::FoldingSetNodeID &ID) override

void dumpToStream(raw_ostream &os) const override

unsigned computeComplexity() const override

static bool classof(const SymExpr *SE)

Represents a symbolic expression involving a binary operator.

QualType getType() const override

BinaryOperator::Opcode getOpcode() const

static unsigned computeOperandComplexity(const SymExpr *Value)

static void dumpToStreamImpl(raw_ostream &os, const SymExpr *Value)

static bool classof(const SymExpr *SE)

static unsigned computeOperandComplexity(const llvm::APSInt &Value)

BinarySymExpr(SymbolID Sym, Kind k, BinaryOperator::Opcode op, QualType t)

static const llvm::APSInt * getPointer(APSIntPtr Value)

static const SymExpr * getPointer(const SymExpr *Value)

static bool isLocType(QualType T)

MemRegion - The root abstract class for all memory regions.

SubRegion - A region that subsets another larger region.

SymT * make(ArgsT &&...Args)

SymExprAllocator(llvm::BumpPtrAllocator &Alloc)

static bool isValidTypeForSymbol(QualType T)

virtual QualType getType() const =0

SymbolID getSymbolID() const

Get a unique identifier for this symbol.

Represents a cast expression.

static bool classof(const SymExpr *SE)

static void Profile(llvm::FoldingSetNodeID &ID, const SymExpr *In, QualType From, QualType To)

QualType getType() const override

void Profile(llvm::FoldingSetNodeID &ID) override

void dumpToStream(raw_ostream &os) const override

LLVM_ATTRIBUTE_RETURNS_NONNULL const SymExpr * getOperand() const

unsigned computeComplexity() const override

A symbol representing the result of an expression in the case when we do not know anything about what...

void Profile(llvm::FoldingSetNodeID &profile) override

unsigned getCount() const

static bool classof(const SymExpr *SE)

StringRef getKindStr() const override

Get a string representation of the kind of the region.

static void Profile(llvm::FoldingSetNodeID &profile, const Stmt *S, const LocationContext *LCtx, QualType T, unsigned Count, const void *SymbolTag)

const void * getTag() const

It might return null.

void dumpToStream(raw_ostream &os) const override

QualType getType() const override

const Stmt * getStmt() const

It might return null.

A symbol representing data which can be stored in a memory location (region).

A symbol representing the value of a MemRegion whose parent region has symbolic value.

LLVM_ATTRIBUTE_RETURNS_NONNULL SymbolRef getParentSymbol() const

StringRef getKindStr() const override

Get a string representation of the kind of the region.

void dumpToStream(raw_ostream &os) const override

const MemRegion * getOriginRegion() const override

Find the region from which this symbol originates.

static void Profile(llvm::FoldingSetNodeID &profile, SymbolRef parent, const TypedValueRegion *r)

void Profile(llvm::FoldingSetNodeID &profile) override

QualType getType() const override

LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const

static bool classof(const SymExpr *SE)

SymbolExtent - Represents the extent (size in bytes) of a bounded region.

static bool classof(const SymExpr *SE)

LLVM_ATTRIBUTE_RETURNS_NONNULL const SubRegion * getRegion() const

void dumpToStream(raw_ostream &os) const override

QualType getType() const override

static void Profile(llvm::FoldingSetNodeID &profile, const SubRegion *R)

StringRef getKindStr() const override

Get a string representation of the kind of the region.

void Profile(llvm::FoldingSetNodeID &profile) override

SymbolManager(ASTContext &ctx, BasicValueFactory &bv, llvm::BumpPtrAllocator &bpalloc)

const SymExprT * acquire(Args &&...args)

Create or retrieve a SymExpr of type SymExprT for the given arguments.

const SymbolConjured * conjureSymbol(const Stmt *E, const LocationContext *LCtx, QualType T, unsigned VisitCount, const void *SymbolTag=nullptr)

void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent)

Add artificial symbol dependency.

BasicValueFactory & getBasicVals()

QualType getType(const SymExpr *SE) const

const SymbolConjured * conjureSymbol(const Expr *E, const LocationContext *LCtx, unsigned VisitCount, const void *SymbolTag=nullptr)

const SymbolRefSmallVectorTy * getDependentSymbols(const SymbolRef Primary)

static bool canSymbolicate(QualType T)

ASTContext & getContext()

A class responsible for cleaning up unused symbols.

void markLive(SymbolRef sym)

Unconditionally marks a symbol as live.

void markElementIndicesLive(const MemRegion *region)

SymbolReaper(const StackFrameContext *Ctx, const Stmt *s, SymbolManager &symmgr, StoreManager &storeMgr)

Construct a reaper object, which removes everything which is not live before we execute statement s i...

bool isDead(SymbolRef sym)

Returns whether or not a symbol has been confirmed dead.

void markInUse(SymbolRef sym)

Marks a symbol as important to a checker.

bool isLiveRegion(const MemRegion *region)

void markLazilyCopied(const MemRegion *region)

const LocationContext * getLocationContext() const

It might return null.

void setReapedStore(StoreRef st)

Set to the value of the symbolic store after StoreManager::removeDeadBindings has been called.

bool isLive(SymbolRef sym)

llvm::iterator_range< RegionSetTy::const_iterator > regions() const

A symbol representing the value stored at a MemRegion.

void dumpToStream(raw_ostream &os) const override

const MemRegion * getOriginRegion() const override

Find the region from which this symbol originates.

void Profile(llvm::FoldingSetNodeID &profile) override

LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const

static void Profile(llvm::FoldingSetNodeID &profile, const TypedValueRegion *R)

QualType getType() const override

StringRef getKindStr() const override

Get a string representation of the kind of the region.

static bool classof(const SymExpr *SE)

virtual bool VisitMemRegion(const MemRegion *)

SymbolVisitor(const SymbolVisitor &)=default

SymbolVisitor(SymbolVisitor &&)

SymbolVisitor & operator=(SymbolVisitor &&)=delete

SymbolVisitor & operator=(const SymbolVisitor &)=delete

virtual bool VisitSymbol(SymbolRef sym)=0

A visitor method invoked by ProgramStateManager::scanReachableSymbols.

TypedValueRegion - An abstract class representing regions having a typed value.

virtual QualType getValueType() const =0

Represents a symbolic expression involving a unary operator.

void dumpToStream(raw_ostream &os) const override

void Profile(llvm::FoldingSetNodeID &ID) override

QualType getType() const override

static bool classof(const SymExpr *SE)

UnaryOperator::Opcode getOpcode() const

unsigned computeComplexity() const override

static void Profile(llvm::FoldingSetNodeID &ID, const SymExpr *In, UnaryOperator::Opcode Op, QualType T)

const SymExpr * getOperand() const

const SymExpr * SymbolRef

The JSON file list parser is used to communicate input to InstallAPI.

const FunctionProtoType * T

static key_type_ref KeyOfValue(value_type_ref D)

static data_type_ref DataOfValue(value_type_ref)

static bool isEqual(clang::ento::SymbolRef LHS, clang::ento::SymbolRef RHS)

static bool isLess(clang::ento::SymbolRef LHS, clang::ento::SymbolRef RHS)

static bool isDataEqual(data_type_ref, data_type_ref)