RegionStore.cpp Source File (original) (raw)

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

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

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

31#include "llvm/Support/raw_ostream.h"

32#include

33#include

34#include

36using namespace clang;

37using namespace ento;

43namespace {

44class BindingKey {

45public:

46 enum Kind {

47 Default = 0x0,

48 Direct = 0x1,

49 Symbolic = 0x2,

50 };

52private:

53 llvm::PointerIntPair<const MemRegion *, 2> P;

58 explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k)

59 : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(Base)) {

60 assert(r && Base && "Must have known regions.");

61 assert(getConcreteOffsetRegion() == Base && "Failed to store base region");

62 }

65 explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)

66 : P(r, k), Data(offset) {

67 assert(r && "Must have known regions.");

68 assert(getOffset() == offset && "Failed to store offset");

71 "Not a base");

72 }

74public:

75 bool isDirect() const { return P.getInt() & Direct; }

76 bool isDefault() const { return !isDirect(); }

77 bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }

79 const MemRegion *getRegion() const { return P.getPointer(); }

81 assert(!hasSymbolicOffset());

82 return Data;

83 }

85 const SubRegion *getConcreteOffsetRegion() const {

86 assert(hasSymbolicOffset());

87 return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data));

88 }

90 const MemRegion *getBaseRegion() const {

91 if (hasSymbolicOffset())

92 return getConcreteOffsetRegion()->getBaseRegion();

94 }

96 void Profile(llvm::FoldingSetNodeID& ID) const {

97 ID.AddPointer(P.getOpaqueValue());

98 ID.AddInteger(Data);

99 }

100

101 static BindingKey Make(const MemRegion *R, Kind k);

102

103 bool operator<(const BindingKey &X) const {

104 if (P.getOpaqueValue() < X.P.getOpaqueValue())

105 return true;

106 if (P.getOpaqueValue() > X.P.getOpaqueValue())

107 return false;

108 return Data < X.Data;

109 }

110

111 bool operator==(const BindingKey &X) const {

112 return P.getOpaqueValue() == X.P.getOpaqueValue() &&

113 Data == X.Data;

114 }

115

116 LLVM_DUMP_METHOD void dump() const;

117};

118

119std::string locDescr(Loc L) {

120 std::string S;

121 llvm::raw_string_ostream OS(S);

123 return OS.str();

124}

125}

126

127BindingKey BindingKey::Make(const MemRegion *R, Kind k) {

128 const RegionOffset &RO = R->getAsOffset();

131

133}

134

135namespace llvm {

136static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) {

137 Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default")

138 << "\", \"offset\": ";

139

140 if (!K.hasSymbolicOffset())

141 Out << K.getOffset();

142 else

143 Out << "null";

144

145 return Out;

146}

147

148}

149

150#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

151void BindingKey::dump() const { llvm::errs() << *this; }

152#endif

153

154

155

156

157

161

162typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>

164

165namespace {

166class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,

167 ClusterBindings> {

168 ClusterBindings::Factory *CBFactory;

169

170

171

172

173

174

175

176

177

178

179 bool IsMainAnalysis;

180

181public:

182 typedef llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>

183 ParentTy;

184

185 RegionBindingsRef(ClusterBindings::Factory &CBFactory,

186 const RegionBindings::TreeTy *T,

187 RegionBindings::TreeTy::Factory *F, bool IsMainAnalysis)

188 : RegionBindingsRef(ParentTy(T, F), CBFactory, IsMainAnalysis) {}

189

190 RegionBindingsRef(const ParentTy &P, ClusterBindings::Factory &CBFactory,

191 bool IsMainAnalysis)

192 : ParentTy(P), CBFactory(&CBFactory), IsMainAnalysis(IsMainAnalysis) {}

193

194 RegionBindingsRef removeCluster(const MemRegion *BaseRegion) const {

195 return RegionBindingsRef(ParentTy::remove(BaseRegion), *CBFactory,

196 IsMainAnalysis);

197 }

198

199 RegionBindingsRef addBinding(BindingKey K, SVal V) const;

200

201 RegionBindingsRef addBinding(const MemRegion *R,

202 BindingKey::Kind k, SVal V) const;

203

204 const SVal *lookup(BindingKey K) const;

205 const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const;

207

208 RegionBindingsRef removeBinding(BindingKey K);

209

210 RegionBindingsRef removeBinding(const MemRegion *R,

211 BindingKey::Kind k);

212

213 RegionBindingsRef removeBinding(const MemRegion *R) {

214 return removeBinding(R, BindingKey::Direct).

215 removeBinding(R, BindingKey::Default);

216 }

217

218 std::optional getDirectBinding(const MemRegion *R) const;

219

220

221

222 std::optional getDefaultBinding(const MemRegion *R) const;

223

224

225 Store asStore() const {

226 llvm::PointerIntPair<Store, 1, bool> Ptr = {

227 asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};

228 return reinterpret_cast<Store>(Ptr.getOpaqueValue());

229 }

230

231 bool isMainAnalysis() const {

232 return IsMainAnalysis;

233 }

234

235 void printJson(raw_ostream &Out, const char *NL = "\n",

236 unsigned int Space = 0, bool IsDot = false) const {

237 using namespace llvm;

238 DenseMap<const MemRegion *, std::string> StringifyCache;

239 auto ToString = [&StringifyCache](const MemRegion *R) {

240 auto [Place, Inserted] = StringifyCache.try_emplace(R);

241 if (!Inserted)

242 return Place->second;

243 std::string Res;

244 raw_string_ostream OS(Res);

245 OS << R;

246 Place->second = Res;

247 return Res;

248 };

249

250 using Cluster =

251 std::pair<const MemRegion *, ImmutableMap<BindingKey, SVal>>;

252 using Binding = std::pair<BindingKey, SVal>;

253

254 const auto MemSpaceBeforeRegionName = [&ToString](const Cluster *L,

255 const Cluster *R) {

257 return true;

259 return false;

260 return ToString(L->first) < ToString(R->first);

261 };

262

263 const auto SymbolicBeforeOffset = [&ToString](const BindingKey &L,

264 const BindingKey &R) {

265 if (L.hasSymbolicOffset() && !R.hasSymbolicOffset())

266 return true;

267 if (!L.hasSymbolicOffset() && R.hasSymbolicOffset())

268 return false;

269 if (L.hasSymbolicOffset() && R.hasSymbolicOffset())

270 return ToString(L.getRegion()) < ToString(R.getRegion());

271 return L.getOffset() < R.getOffset();

272 };

273

274 const auto DefaultBindingBeforeDirectBindings =

275 [&SymbolicBeforeOffset](const Binding *LPtr, const Binding *RPtr) {

276 const BindingKey &L = LPtr->first;

277 const BindingKey &R = RPtr->first;

278 if (L.isDefault() && !R.isDefault())

279 return true;

280 if (!L.isDefault() && R.isDefault())

281 return false;

282 assert(L.isDefault() == R.isDefault());

283 return SymbolicBeforeOffset(L, R);

284 };

285

286 const auto AddrOf = [](const auto &Item) { return &Item; };

287

288 std::vector<const Cluster *> SortedClusters;

289 SortedClusters.reserve(std::distance(begin(), end()));

290 append_range(SortedClusters, map_range(*this, AddrOf));

291 llvm::sort(SortedClusters, MemSpaceBeforeRegionName);

292

293 for (auto [Idx, C] : llvm::enumerate(SortedClusters)) {

294 const auto &[BaseRegion, Bindings] = *C;

295 Indent(Out, Space, IsDot)

296 << "{ \"cluster\": \"" << BaseRegion << "\", \"pointer\": \""

297 << (const void *)BaseRegion << "\", \"items\": [" << NL;

298

299 std::vector<const Binding *> SortedBindings;

300 SortedBindings.reserve(std::distance(Bindings.begin(), Bindings.end()));

301 append_range(SortedBindings, map_range(Bindings, AddrOf));

302 llvm::sort(SortedBindings, DefaultBindingBeforeDirectBindings);

303

304 ++Space;

305 for (auto [Idx, B] : llvm::enumerate(SortedBindings)) {

306 const auto &[Key, Value] = *B;

307 Indent(Out, Space, IsDot) << "{ " << Key << ", \"value\": ";

308 Value.printJson(Out, true);

309 Out << " }";

310 if (Idx != SortedBindings.size() - 1)

311 Out << ',';

312 Out << NL;

313 }

314 --Space;

315 Indent(Out, Space, IsDot) << "]}";

316 if (Idx != SortedClusters.size() - 1)

317 Out << ',';

318 Out << NL;

319 }

320 }

321

322 LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); }

323

324protected:

325 RegionBindingsRef

326 commitBindingsToCluster(const MemRegion *BaseRegion,

328};

329}

330

331

332

334public:

337 std::optional BindingsLeft)

338 : RegionBindingsRef(Base),

339 EscapedValuesDuringBind(&EscapedValuesDuringBind),

340 BindingsLeft(BindingsLeft) {}

341

343 return BindingsLeft.has_value() && BindingsLeft.value() == 0;

344 }

345

347 EscapedValuesDuringBind->push_back(V);

348 return *this;

349 }

350

354 for (SVal V : llvm::make_range(Begin, End))

356 return *this;

357 }

358

361 data_type_ref BindingKeyAndValue) const {

363 BaseRegion, BindingKeyAndValue),

364 *EscapedValuesDuringBind, BindingsLeft};

365 }

366

369 RegionBindingsRef::removeCluster(BaseRegion), *EscapedValuesDuringBind,

370 BindingsLeft};

371 }

372

374 std::optional NewBindingsLeft = BindingsLeft;

375 if (NewBindingsLeft.has_value()) {

376 assert(NewBindingsLeft.value() != 0);

377 NewBindingsLeft.value() -= 1;

378

379

380

381 if (NewBindingsLeft.value() == 0) {

383 K = BindingKey::Make(K.getRegion(), BindingKey::Default);

385 }

386 }

387

389 *EscapedValuesDuringBind, NewBindingsLeft};

390 }

391

394 return addBinding(BindingKey::Make(R, k), V);

395 }

396

397private:

399 std::optional BindingsLeft;

400};

401

404

405std::optional

406RegionBindingsRef::getDirectBinding(const MemRegion *R) const {

407 const SVal *V = lookup(R, BindingKey::Direct);

408 return V ? std::optional(*V) : std::nullopt;

409}

410

411std::optional

412RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {

413 const SVal *V = lookup(R, BindingKey::Default);

414 return V ? std::optional(*V) : std::nullopt;

415}

416

417RegionBindingsRef RegionBindingsRef::commitBindingsToCluster(

419 return RegionBindingsRef(ParentTy::add(BaseRegion, Bindings), *CBFactory,

420 IsMainAnalysis);

421}

422

423RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const {

424 const MemRegion *Base = K.getBaseRegion();

425

428 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());

430 return commitBindingsToCluster(Base, Bindings);

431}

432

433RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R,

434 BindingKey::Kind k,

435 SVal V) const {

436 return addBinding(BindingKey::Make(R, k), V);

437}

438

439const SVal *RegionBindingsRef::lookup(BindingKey K) const {

440 const ClusterBindings *Cluster = lookup(K.getBaseRegion());

441 if (!Cluster)

442 return nullptr;

443 return Cluster->lookup(K);

444}

445

446const SVal *RegionBindingsRef::lookup(const MemRegion *R,

447 BindingKey::Kind k) const {

448 return lookup(BindingKey::Make(R, k));

449}

450

451RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {

452 const MemRegion *Base = K.getBaseRegion();

454 if (!Cluster)

455 return *this;

456

457 ClusterBindings NewCluster = CBFactory->remove(*Cluster, K);

458 if (NewCluster.isEmpty())

459 return removeCluster(Base);

460 return commitBindingsToCluster(Base, NewCluster);

461}

462

463RegionBindingsRef RegionBindingsRef::removeBinding(const MemRegion *R,

464 BindingKey::Kind k){

465 return removeBinding(BindingKey::Make(R, k));

466}

467

468

469

470

471

472namespace {

473class InvalidateRegionsWorker;

474

475class RegionStoreManager : public StoreManager {

476public:

477 RegionBindings::Factory RBFactory;

478 mutable ClusterBindings::Factory CBFactory;

479

480 typedef std::vector SValListTy;

481private:

482 typedef llvm::DenseMap<const LazyCompoundValData *,

483 SValListTy> LazyBindingsMapTy;

484 LazyBindingsMapTy LazyBindingsMap;

485

486

487

488

489

490

491

492

493

494 const unsigned SmallStructLimit;

495

496

497

498

499

500

501

502

503

504 const unsigned SmallArrayLimit;

505

506

507

508

509

510 const std::optional RegionStoreMaxBindingFanOutPlusOne;

511

512

513

514 void populateWorkList(InvalidateRegionsWorker &W,

515 ArrayRef Values,

516 InvalidatedRegions *TopLevelRegions);

517

518 const AnalyzerOptions &getOptions() {

519 return StateMgr.getOwningEngine().getAnalysisManager().options;

520 }

521

522public:

523 RegionStoreManager(ProgramStateManager &mgr)

524 : StoreManager(mgr), RBFactory(mgr.getAllocator()),

525 CBFactory(mgr.getAllocator()),

526 SmallStructLimit(getOptions().RegionStoreSmallStructLimit),

527 SmallArrayLimit(getOptions().RegionStoreSmallArrayLimit),

528 RegionStoreMaxBindingFanOutPlusOne([&]() -> std::optional {

529 unsigned FanOut = getOptions().RegionStoreMaxBindingFanOut;

530 assert(FanOut != std::numeric_limits::max());

531 if (FanOut == 0)

532 return std::nullopt;

533 return FanOut + 1 ;

534 }()) {}

535

536

537

538

539 LimitedRegionBindingsRef

541 QualType T);

542

543

544

545

546

547

548

549 SVal ArrayToPointer(Loc Array, QualType ElementTy) override;

550

551

552

553 StoreRef getInitialStore(const LocationContext *InitLoc) override {

554 bool IsMainAnalysis = false;

555 if (const auto *FD = dyn_cast(InitLoc->getDecl()))

556 IsMainAnalysis = FD->isMain() && !Ctx.getLangOpts().CPlusPlus;

557 return StoreRef(RegionBindingsRef(RegionBindingsRef::ParentTy(

558 RBFactory.getEmptyMap(), RBFactory),

559 CBFactory, IsMainAnalysis)

560 .asStore(),

561 *this);

562 }

563

564

565

566

567 RegionBindingsRef

569 unsigned Count, const LocationContext *LCtx,

570 RegionBindingsRef B, InvalidatedRegions *Invalidated);

571

572 StoreRef invalidateRegions(Store store, ArrayRef Values,

574 const LocationContext *LCtx, const CallEvent *Call,

576 RegionAndSymbolInvalidationTraits &ITraits,

577 InvalidatedRegions *Invalidated,

578 InvalidatedRegions *InvalidatedTopLevel) override;

579

580 bool scanReachableSymbols(Store S, const MemRegion *R,

581 ScanReachableSymbols &Callbacks) override;

582

583 LimitedRegionBindingsRef

585 std::optional

587 const ElementRegion *R);

588 std::optional

589 getSValFromInitListExpr(const InitListExpr *ILE,

590 const SmallVector<uint64_t, 2> &ConcreteOffsets,

591 QualType ElemT);

592 SVal getSValFromStringLiteral(const StringLiteral *SL, uint64_t Offset,

593 QualType ElemT);

594

595public:

596 BindResult Bind(Store store, Loc LV, SVal V) override {

597 llvm::SmallVector<SVal, 0> EscapedValuesDuringBind;

598 LimitedRegionBindingsRef BoundedBindings =

599 getRegionBindings(store, EscapedValuesDuringBind);

600 return BindResult{StoreRef(bind(BoundedBindings, LV, V).asStore(), *this),

601 std::move(EscapedValuesDuringBind)};

602 }

603

605 SVal V);

606

607

608

609 BindResult BindDefaultInitial(Store store, const MemRegion *R,

610 SVal V) override {

611 RegionBindingsRef B = getRegionBindings(store);

612

613

614 assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&

615 "Double initialization!");

616 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);

617 return BindResult{

618 StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this), {}};

619 }

620

621

622

623 BindResult BindDefaultZero(Store store, const MemRegion *R) override {

624

625

626

627

628

629

630

631

632

633 if (const auto *BR = dyn_cast(R))

634 if (BR->getDecl()->isEmpty())

635 return BindResult{StoreRef(store, *this), {}};

636

637 llvm::SmallVector<SVal, 0> EscapedValuesDuringBind;

638 LimitedRegionBindingsRef B =

639 getRegionBindings(store, EscapedValuesDuringBind);

640 SVal V = svalBuilder.makeZeroVal(Ctx.CharTy);

642 B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);

643 return BindResult{

644 StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this),

645 std::move(EscapedValuesDuringBind)};

646 }

647

648

649

650

651

652

653

654

655

656

657

658 std::optional

660 const RecordDecl *RD, nonloc::LazyCompoundVal LCV);

661

662

664 const TypedValueRegion *R, SVal V);

665

666

668 const TypedValueRegion *R, SVal V);

669

670 std::optional

672 const ArrayType *AT, nonloc::LazyCompoundVal LCV);

673

675 const TypedValueRegion *R, SVal V);

676

677

678

680 const TypedRegion *R, SVal DefaultVal);

681

682

683

684

685 StoreRef killBinding(Store ST, Loc L) override;

686

687 void incrementReferenceCount(Store store) override {

688 getRegionBindings(store).manualRetain();

689 }

690

691

692

693

694 void decrementReferenceCount(Store store) override {

695 getRegionBindings(store).manualRelease();

696 }

697

698 bool includedInBindings(Store store, const MemRegion *region) const override;

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713 SVal getBinding(Store S, Loc L, QualType T) override {

714 return getBinding(getRegionBindings(S), L, T);

715 }

716

717 std::optional getDefaultBinding(Store S, const MemRegion *R) override {

718 RegionBindingsRef B = getRegionBindings(S);

719

720

721

723 }

724

726

728

730

732

734

735 SVal getBindingForLazySymbol(const TypedValueRegion *R);

736

738 const TypedValueRegion *R,

739 QualType Ty);

740

741 SVal getLazyBinding(const SubRegion *LazyBindingRegion,

742 RegionBindingsRef LazyBinding);

743

744

745

746

747

748

752

753

754

755

756

757

758 std::optional

760 const MemRegion *superR,

761 const TypedValueRegion *R, QualType Ty);

762

763

764

765

766

767 std::pair<Store, const SubRegion *>

769 const SubRegion *originalRegion);

770

771

772

773

774

775

776

777

778

779

780

781 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);

782

783

784

785

786

787

788

789 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,

790 SymbolReaper& SymReaper) override;

791

792

793

794

795

796 RegionBindingsRef getRegionBindings(Store store) const {

797 llvm::PointerIntPair<Store, 1, bool> Ptr;

798 Ptr.setFromOpaqueValue(const_cast<void *>(store));

799 return {CBFactory,

800 static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()),

801 RBFactory.getTreeFactory(), Ptr.getInt()};

802 }

803

804 LimitedRegionBindingsRef

805 getRegionBindings(Store store,

806 SmallVectorImpl &EscapedValuesDuringBind) const {

807 return LimitedRegionBindingsRef(

808 getRegionBindings(store), EscapedValuesDuringBind,

809 RegionStoreMaxBindingFanOutPlusOne);

810 }

811

812 void printJson(raw_ostream &Out, Store S, const char *NL = "\n",

813 unsigned int Space = 0, bool IsDot = false) const override;

814

815 void iterBindings(Store store, BindingsHandler& f) override {

816 RegionBindingsRef B = getRegionBindings(store);

817 for (const auto &[Region, Cluster] : B) {

818 for (const auto &[Key, Value] : Cluster) {

819 if (!Key.isDirect())

820 continue;

821 if (const SubRegion *R = dyn_cast(Key.getRegion())) {

822

823 if (!f.HandleBinding(*this, store, R, Value))

824 return;

825 }

826 }

827 }

828 }

829};

830

831}

832

833

834

835

836

837std::unique_ptr

839 return std::make_unique(StMgr);

840}

841

842

843

844

845

846namespace {

847

848

849enum GlobalsFilterKind {

850

851 GFK_None,

852

853 GFK_SystemOnly,

854

855 GFK_All

856};

857

858template

859class ClusterAnalysis {

860protected:

861 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;

862 typedef const MemRegion * WorkListElement;

864

866

868

869 RegionStoreManager &RM;

872

873 RegionBindingsRef B;

874

875

876protected:

878 return B.lookup(R);

879 }

880

881

882

883

884 bool includeEntireMemorySpace(const MemRegion *Base) {

885 return false;

886 }

887

888public:

889 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,

890 RegionBindingsRef b)

891 : RM(rm), Ctx(StateMgr.getContext()),

892 svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {}

893

894 RegionBindingsRef getRegionBindings() const { return B; }

895

896 bool isVisited(const MemRegion *R) {

897 return Visited.count(getCluster(R));

898 }

899

900 void GenerateClusters() {

901

902 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();

903 RI != RE; ++RI){

904 const MemRegion *Base = RI.getKey();

905

907 assert(!Cluster.isEmpty() && "Empty clusters should be removed");

908 static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);

909

910

911

912 if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base))

913 AddToWorkList(WorkListElement(Base), &Cluster);

914 }

915 }

916

917 bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {

918 if (C && !Visited.insert(C).second)

919 return false;

920 WL.push_back(E);

921 return true;

922 }

923

924 bool AddToWorkList(const MemRegion *R) {

925 return static_cast<DERIVED*>(this)->AddToWorkList(R);

926 }

927

928 void RunWorkList() {

929 while (!WL.empty()) {

930 WorkListElement E = WL.pop_back_val();

931 const MemRegion *BaseR = E;

932

933 static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR));

934 }

935 }

936

937 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}

938 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {}

939

940 void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C,

941 bool Flag) {

942 static_cast<DERIVED*>(this)->VisitCluster(BaseR, C);

943 }

944};

945}

946

947

948

949

950

951bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,

952 ScanReachableSymbols &Callbacks) {

953 assert(R == R->getBaseRegion() && "Should only be called for base regions");

954 RegionBindingsRef B = getRegionBindings(S);

956

957 if (!Cluster)

958 return true;

959

960 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();

961 RI != RE; ++RI) {

962 if (!Callbacks.scan(RI.getData()))

963 return false;

964 }

965

966 return true;

967}

968

972

974

976 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");

977

978 const MemRegion *Base = K.getConcreteOffsetRegion();

979 const MemRegion *R = K.getRegion();

980

981 while (R != Base) {

982 if (const FieldRegion *FR = dyn_cast(R))

984 Fields.push_back(FR->getDecl());

985

987 }

988}

989

991 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");

992

993 if (Fields.empty())

994 return true;

995

998

999 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();

1000 if (Delta >= 0)

1001 return std::equal(FieldsInBindingKey.begin() + Delta,

1002 FieldsInBindingKey.end(),

1003 Fields.begin());

1004 else

1005 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),

1006 Fields.begin() - Delta);

1007}

1008

1009

1010

1011

1012

1013

1014

1015

1016

1017

1018static void

1021 const SubRegion *Top, BindingKey TopKey,

1022 bool IncludeAllDefaultBindings) {

1024 if (TopKey.hasSymbolicOffset()) {

1026 Top = TopKey.getConcreteOffsetRegion();

1027 TopKey = BindingKey::Make(Top, BindingKey::Default);

1028 }

1029

1030

1031 uint64_t Length = UINT64_MAX;

1033 if (std::optionalnonloc::ConcreteInt ExtentCI =

1035 const llvm::APSInt &ExtentInt = ExtentCI->getValue();

1036 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());

1037

1039 } else if (const FieldRegion *FR = dyn_cast(Top)) {

1040 if (FR->getDecl()->isBitField())

1041 Length = FR->getDecl()->getBitWidthValue();

1042 }

1043

1044 for (const auto &StoreEntry : Cluster) {

1045 BindingKey NextKey = StoreEntry.first;

1046 if (NextKey.getRegion() == TopKey.getRegion()) {

1047

1048

1049

1050

1051

1052 if (NextKey.getOffset() > TopKey.getOffset() &&

1053 NextKey.getOffset() - TopKey.getOffset() < Length) {

1054

1055

1056 Bindings.push_back(StoreEntry);

1057

1058 } else if (NextKey.getOffset() == TopKey.getOffset()) {

1059

1060

1061

1062

1063

1064

1065 if (IncludeAllDefaultBindings || NextKey.isDirect())

1066 Bindings.push_back(StoreEntry);

1067 }

1068

1069 } else if (NextKey.hasSymbolicOffset()) {

1070 const MemRegion *Base = NextKey.getConcreteOffsetRegion();

1072

1073

1074

1075 if (IncludeAllDefaultBindings || NextKey.isDirect())

1077 Bindings.push_back(StoreEntry);

1078 } else if (const SubRegion *BaseSR = dyn_cast(Base)) {

1079

1080

1081 if (BaseSR->isSubRegionOf(Top))

1083 Bindings.push_back(StoreEntry);

1084 }

1085 }

1086 }

1087}

1088

1089static void

1092 const SubRegion *Top, bool IncludeAllDefaultBindings) {

1094 BindingKey::Make(Top, BindingKey::Default),

1095 IncludeAllDefaultBindings);

1096}

1097

1098LimitedRegionBindingsRef

1100 const SubRegion *Top) {

1101 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);

1102 const MemRegion *ClusterHead = TopKey.getBaseRegion();

1103

1104 if (Top == ClusterHead) {

1105

1107 }

1108

1110 if (!Cluster) {

1111

1112

1113 if (TopKey.hasSymbolicOffset()) {

1114 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();

1115 return B.addBinding(Concrete, BindingKey::Default, UnknownVal());

1116 }

1117 return B;

1118 }

1119

1120 SmallVector<BindingPair, 32> Bindings;

1122 false);

1123

1125 for (BindingKey Key : llvm::make_first_range(Bindings))

1127

1128

1129

1130

1131

1132 if (TopKey.hasSymbolicOffset()) {

1133 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();

1134 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default),

1135 UnknownVal());

1136 }

1137

1138 if (Result.isEmpty())

1141}

1142

1143namespace {

1144class InvalidateRegionsWorker : public ClusterAnalysis

1145{

1147 unsigned Count;

1148 const LocationContext *LCtx;

1150 RegionAndSymbolInvalidationTraits &ITraits;

1152 GlobalsFilterKind GlobalsFilter;

1153public:

1154 InvalidateRegionsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr,

1156 unsigned count, const LocationContext *lctx,

1158 RegionAndSymbolInvalidationTraits &ITraitsIn,

1160 GlobalsFilterKind GFK)

1161 : ClusterAnalysis(rm, stateMgr, b), Elem(elem),

1162 Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),

1163 GlobalsFilter(GFK) {}

1164

1165 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);

1166 void VisitBinding(SVal V);

1167

1168 using ClusterAnalysis::AddToWorkList;

1169

1170 bool AddToWorkList(const MemRegion *R);

1171

1172

1173

1174 bool includeEntireMemorySpace(const MemRegion *Base);

1175

1176

1177

1178 bool isInitiallyIncludedGlobalRegion(const MemRegion *R);

1179};

1180}

1181

1182bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {

1183 bool doNotInvalidateSuperRegion = ITraits.hasTrait(

1185 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();

1186 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));

1187}

1188

1189void InvalidateRegionsWorker::VisitBinding(SVal V) {

1190

1191 if (SymbolRef Sym = V.getAsSymbol())

1192 IS.insert(Sym);

1193

1194 if (const MemRegion *R = V.getAsRegion()) {

1195 AddToWorkList(R);

1196 return;

1197 }

1198

1199

1200 if (std::optionalnonloc::LazyCompoundVal LCS =

1201 V.getAsnonloc::LazyCompoundVal()) {

1202

1203

1204

1205 for (SVal V : RM.getInterestingValues(*LCS))

1207 VisitBinding(V);

1208

1209 return;

1210 }

1211}

1212

1213void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,

1215

1216 bool PreserveRegionsContents =

1219

1220 if (C) {

1221 for (SVal Val : llvm::make_second_range(*C))

1222 VisitBinding(Val);

1223

1224

1225 if (!PreserveRegionsContents)

1227 }

1228

1229 if (const auto *TO = dyn_cast(baseR)) {

1230 if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {

1231

1232

1233

1234

1235 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {

1236 using namespace ast_matchers;

1237

1238 const char *DeclBind = "DeclBind";

1240 to(varDecl(hasStaticStorageDuration()).bind(DeclBind)))));

1241 auto Matches =

1242 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),

1243 RD->getASTContext());

1244

1245 for (BoundNodes &Match : Matches) {

1246 auto *VD = Match.getNodeAs(DeclBind);

1247 const VarRegion *ToInvalidate =

1248 RM.getRegionManager().getVarRegion(VD, LCtx);

1249 AddToWorkList(ToInvalidate);

1250 }

1251 }

1252 }

1253 }

1254

1255

1256

1257 if (const BlockDataRegion *BR = dyn_cast(baseR)) {

1258 for (auto Var : BR->referenced_vars()) {

1259 const VarRegion *VR = Var.getCapturedRegion();

1260 const VarDecl *VD = VR->getDecl();

1262 AddToWorkList(VR);

1263 }

1265

1266

1267

1268

1269

1270 SVal V = RM.getBinding(B, loc::MemRegionVal(VR));

1271 if (std::optional L = V.getAs()) {

1272 if (const MemRegion *LR = L->getAsRegion())

1273 AddToWorkList(LR);

1274 }

1275 }

1276 }

1277 return;

1278 }

1279

1280

1281 if (const SymbolicRegion *SR = dyn_cast(baseR))

1282 IS.insert(SR->getSymbol());

1283

1284

1285 if (PreserveRegionsContents)

1286 return;

1287

1288

1289 if (Regions)

1290 Regions->push_back(baseR);

1291

1293

1294

1295 DefinedOrUnknownSVal V =

1297 B = B.addBinding(baseR, BindingKey::Default, V);

1298 return;

1299 }

1300

1302 return;

1303

1306

1307 if (isInitiallyIncludedGlobalRegion(baseR)) {

1308

1309

1310

1311 return;

1312 }

1313

1315

1316

1317 DefinedOrUnknownSVal V =

1319 B = B.addBinding(baseR, BindingKey::Default, V);

1320 return;

1321 }

1322

1324 bool doNotInvalidateSuperRegion = ITraits.hasTrait(

1325 baseR,

1327

1328 if (doNotInvalidateSuperRegion) {

1329

1330

1331 std::optional<uint64_t> NumElements;

1332

1333

1334 if (const ConstantArrayType *CAT = dyn_cast(AT))

1335 NumElements = CAT->getZExtSize();

1336 if (!NumElements)

1337 goto conjure_default;

1338 QualType ElementTy = AT->getElementType();

1340 const RegionOffset &RO = baseR->getAsOffset();

1341 const MemRegion *SuperR = baseR->getBaseRegion();

1343

1344

1345 if (SuperR)

1346 AddToWorkList(SuperR);

1347 goto conjure_default;

1348 }

1349

1351 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize;

1352 bool UpperOverflow = UpperOffset < LowerOffset;

1353

1354

1355

1356 if (!SuperR)

1357 goto conjure_default;

1358

1360 if ()

1361 goto conjure_default;

1362

1363 for (const auto &[BK, V] : *C) {

1364 std::optional<uint64_t> ROffset =

1365 BK.hasSymbolicOffset() ? std::optional<uint64_t>() : BK.getOffset();

1366

1367

1368

1369 if (!ROffset ||

1370 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) ||

1371 (UpperOverflow &&

1372 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) ||

1373 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) {

1374 B = B.removeBinding(BK);

1375

1376

1377 const MemRegion *R = V.getAsRegion();

1378 if (isa_and_nonnull(R))

1379 VisitBinding(V);

1380 }

1381 }

1382 }

1383 conjure_default:

1384

1386 baseR, Elem, LCtx, AT->getElementType(), Count);

1387 B = B.addBinding(baseR, BindingKey::Default, V);

1388 return;

1389 }

1390

1391 DefinedOrUnknownSVal V =

1394 B = B.addBinding(baseR, BindingKey::Direct, V);

1395}

1396

1397bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(

1398 const MemRegion *R) {

1399 switch (GlobalsFilter) {

1400 case GFK_None:

1401 return false;

1402 case GFK_SystemOnly:

1404 case GFK_All:

1406 }

1407

1408 llvm_unreachable("unknown globals filter");

1409}

1410

1411bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) {

1412 if (isInitiallyIncludedGlobalRegion(Base))

1413 return true;

1414

1415 const MemSpaceRegion *MemSpace = Base->getRawMemorySpace();

1416 return ITraits.hasTrait(MemSpace,

1418}

1419

1420RegionBindingsRef RegionStoreManager::invalidateGlobalRegion(

1422 const LocationContext *LCtx, RegionBindingsRef B,

1423 InvalidatedRegions *Invalidated) {

1424

1425

1426 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);

1428 (const void *)GS, Elem, LCtx,

1429 Ctx.IntTy, Count);

1430

1431 B = B.removeBinding(GS)

1432 .addBinding(BindingKey::Make(GS, BindingKey::Default), V);

1433

1434

1435

1436 if (Invalidated)

1437 Invalidated->push_back(GS);

1438

1439 return B;

1440}

1441

1442void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,

1443 ArrayRef Values,

1444 InvalidatedRegions *TopLevelRegions) {

1445 for (SVal V : Values) {

1446 if (auto LCS = V.getAsnonloc::LazyCompoundVal()) {

1447 for (SVal S : getInterestingValues(*LCS))

1448 if (const MemRegion *R = S.getAsRegion())

1449 W.AddToWorkList(R);

1450

1451 continue;

1452 }

1453

1454 if (const MemRegion *R = V.getAsRegion()) {

1455 if (TopLevelRegions)

1456 TopLevelRegions->push_back(R);

1457 W.AddToWorkList(R);

1458 continue;

1459 }

1460 }

1461}

1462

1463StoreRef RegionStoreManager::invalidateRegions(

1466 RegionAndSymbolInvalidationTraits &ITraits,

1467 InvalidatedRegions *TopLevelRegions, InvalidatedRegions *Invalidated) {

1468 GlobalsFilterKind GlobalsFilter;

1470 if (Call->isInSystemHeader())

1471 GlobalsFilter = GFK_SystemOnly;

1472 else

1473 GlobalsFilter = GFK_All;

1474 } else {

1475 GlobalsFilter = GFK_None;

1476 }

1477

1478 RegionBindingsRef B = getRegionBindings(store);

1479 InvalidateRegionsWorker W(*this, StateMgr, B, Elem, Count, LCtx, IS, ITraits,

1480 Invalidated, GlobalsFilter);

1481

1482

1483 W.GenerateClusters();

1484

1485

1486 populateWorkList(W, Values, TopLevelRegions);

1487

1488 W.RunWorkList();

1489

1490

1491 B = W.getRegionBindings();

1492

1493

1494

1495

1496

1497 switch (GlobalsFilter) {

1498 case GFK_All:

1499 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, Elem,

1500 Count, LCtx, B, Invalidated);

1501 [[fallthrough]];

1502 case GFK_SystemOnly:

1503 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, Elem,

1504 Count, LCtx, B, Invalidated);

1505 [[fallthrough]];

1506 case GFK_None:

1507 break;

1508 }

1509

1510 return StoreRef(B.asStore(), *this);

1511}

1512

1513

1514

1515

1516

1517

1518

1519

1520

1521

1522

1523SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) {

1525 return Array;

1526

1528 return UnknownVal();

1529

1530 const SubRegion *R =

1531 cast(Array.castAsloc::MemRegionVal().getRegion());

1533 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));

1534}

1535

1536

1537

1538

1539

1543

1544

1545

1546

1547

1548

1549

1550 if (L.getAs loc::ConcreteInt()) {

1551 return UnknownVal();

1552 }

1553 if (!L.getAs loc::MemRegionVal()) {

1554 return UnknownVal();

1555 }

1556

1557 const MemRegion *MR = L.castAs loc::MemRegionVal().getRegion();

1558

1560 return UnknownVal();

1561 }

1562

1563

1564 if (T.isNull()) {

1565 if (const auto *TVR = dyn_cast(MR))

1566 T = TVR->getValueType();

1567 else if (const auto *TR = dyn_cast(MR))

1569 else if (const auto *SR = dyn_cast(MR))

1570 T = SR->getPointeeStaticType();

1571 }

1572 assert(.isNull() && "Unable to auto-detect binding type!");

1573 assert(->isVoidType() && "Attempting to dereference a void pointer!");

1574

1577

1578

1579

1582

1583

1584

1586 return UnknownVal();

1587

1588

1589

1590

1591

1592

1593

1594

1595

1597 return getBindingForStruct(B, R);

1598

1599

1601 return createLazyBinding(B, R);

1602

1605 return getBindingForArray(B, R);

1606 else

1607 return UnknownVal();

1608 }

1609

1610

1612 return UnknownVal();

1613

1614 if (const FieldRegion* FR = dyn_cast(R))

1615 return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{});

1616

1617 if (const ElementRegion* ER = dyn_cast(R)) {

1618

1619

1620

1621

1622

1623 return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{});

1624 }

1625

1626 if (const ObjCIvarRegion *IVR = dyn_cast(R)) {

1627

1628

1629

1630

1631

1632

1633 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{});

1634 }

1635

1636 if (const VarRegion *VR = dyn_cast(R)) {

1637

1638

1639

1640

1641

1642

1643 return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{});

1644 }

1645

1646 const SVal *V = B.lookup(R, BindingKey::Direct);

1647

1648

1649 if (V)

1650 return *V;

1651

1652

1653

1654

1656

1657

1658

1659

1660 return UndefinedVal();

1661 }

1662

1663

1665}

1666

1669 if (const TypedValueRegion *TVR = dyn_cast(R))

1670 RegionTy = TVR->getValueType();

1671

1672 if (const SymbolicRegion *SR = dyn_cast(R))

1673 RegionTy = SR->getSymbol()->getType();

1674

1675 return RegionTy;

1676}

1677

1678

1679

1680

1681

1682

1683

1684

1685static std::optionalnonloc::LazyCompoundVal

1687 const SubRegion *R, bool AllowSubregionBindings) {

1688 std::optional V = B.getDefaultBinding(R);

1689 if ()

1690 return std::nullopt;

1691

1692 std::optionalnonloc::LazyCompoundVal LCV =

1694 if (!LCV)

1695 return std::nullopt;

1696

1697

1698

1700 if (!RegionTy.isNull() &&

1702 QualType SourceRegionTy = LCV->getRegion()->getValueType();

1704 return std::nullopt;

1705 }

1706

1707 if (!AllowSubregionBindings) {

1708

1709

1712 true);

1714 return std::nullopt;

1715 }

1716

1717 return *LCV;

1718}

1719

1720std::pair<Store, const SubRegion *>

1722 const SubRegion *R,

1723 const SubRegion *originalRegion) {

1724 if (originalRegion != R) {

1725 if (std::optionalnonloc::LazyCompoundVal V =

1727 return std::make_pair(V->getStore(), V->getRegion());

1728 }

1729

1730 typedef std::pair<Store, const SubRegion *> StoreRegionPair;

1731 StoreRegionPair Result = StoreRegionPair();

1732

1733 if (const ElementRegion *ER = dyn_cast(R)) {

1735 originalRegion);

1736

1738 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);

1739

1740 } else if (const FieldRegion *FR = dyn_cast(R)) {

1742 originalRegion);

1743

1745 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);

1746

1747 } else if (const CXXBaseObjectRegion *BaseReg =

1748 dyn_cast(R)) {

1749

1750

1752 originalRegion);

1753

1755 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,

1757 }

1758

1760}

1761

1762

1763

1764

1765

1766

1767static SmallVector<uint64_t, 2>

1769 assert(CAT && "ConstantArrayType should not be null");

1772 do {

1774 } while ((CAT = dyn_cast(CAT->getElementType())));

1775 return Extents;

1776}

1777

1778

1779

1780

1781

1782

1783

1784

1785

1786

1787

1788

1789

1790

1791

1792static std::pair<SmallVector<SVal, 2>, const MemRegion *>

1794 assert(ER && "ConstantArrayType should not be null");

1797 do {

1798 SValOffsets.push_back(ER->getIndex());

1800 ER = dyn_cast(Base);

1801 } while (ER);

1802 return {SValOffsets, Base};

1803}

1804

1805

1806

1807

1808

1809

1810

1811

1812

1813

1814

1815

1816

1817

1818

1819

1820

1821

1822

1823

1824

1825

1826static std::optional

1830

1831

1832

1833

1834

1835

1836

1837

1838

1839

1840

1841

1842

1843

1844

1845

1846

1847 DstOffsets.resize(SrcOffsets.size());

1848 auto ExtentIt = ArrayExtents.begin();

1849 auto OffsetIt = DstOffsets.begin();

1850

1851 for (SVal V : llvm::reverse(SrcOffsets)) {

1853

1854 const llvm::APSInt &Offset = CI->getValue();

1855 if (Offset.isNegative() || Offset.uge(*(ExtentIt++)))

1857

1858 *(OffsetIt++) = Offset.getZExtValue();

1859 continue;

1860 }

1861

1862

1863

1865 }

1866 return std::nullopt;

1867}

1868

1869std::optional RegionStoreManager::getConstantValFromConstArrayInitializer(

1871 assert(R && "ElementRegion should not be null");

1872

1873

1874 SmallVector<SVal, 2> SValOffsets;

1875 const MemRegion *Base;

1877 const VarRegion *VR = dyn_cast(Base);

1878 if (!VR)

1879 return std::nullopt;

1880

1881 assert(!SValOffsets.empty() && "getElementRegionOffsets guarantees the "

1882 "offsets vector is not empty.");

1883

1884

1885

1886 const VarDecl *VD = VR->getDecl();

1890 return std::nullopt;

1891

1892

1893

1894

1895

1896

1897

1898

1899

1900

1902

1903

1905 return std::nullopt;

1906

1907

1908

1910 if (!CAT)

1911 return std::nullopt;

1912

1913

1915

1916

1917

1918

1919

1920

1921

1922 if (SValOffsets.size() != Extents.size())

1923 return std::nullopt;

1924

1925 SmallVector<uint64_t, 2> ConcreteOffsets;

1927 SValOffsets, Extents, ConcreteOffsets))

1928 return *V;

1929

1930

1931

1932

1933 if (const auto *ILE = dyn_cast(Init))

1934 return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType());

1935

1936

1937

1938

1939 if (const auto *SL = dyn_cast(Init))

1940 return getSValFromStringLiteral(SL, ConcreteOffsets.front(),

1942

1943

1944

1945 return std::nullopt;

1946}

1947

1948

1949

1950

1951

1952

1953

1954

1955

1956

1957

1958

1959

1960

1961

1962

1963

1964

1965std::optional RegionStoreManager::getSValFromInitListExpr(

1966 const InitListExpr *ILE, const SmallVector<uint64_t, 2> &Offsets,

1967 QualType ElemT) {

1968 assert(ILE && "InitListExpr should not be null");

1969

1970 for (uint64_t Offset : Offsets) {

1971

1972

1973

1974

1975

1977 if (const auto *SL = dyn_cast(ILE->getInit(0)))

1978 return getSValFromStringLiteral(SL, Offset, ElemT);

1979

1980

1981

1982

1985

1986 const Expr *E = ILE->getInit(Offset);

1987 const auto *IL = dyn_cast(E);

1988 if (!IL)

1989

1990

1992

1993

1994 ILE = IL;

1995 }

1996

1997 assert(ILE);

1998

1999

2000

2001 return std::nullopt;

2002}

2003

2004

2005

2006

2007

2008

2009

2010

2011

2012

2013

2014

2015

2016

2017

2018

2019

2020

2021

2022

2023

2024

2025

2026

2027

2028

2029SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL,

2030 uint64_t Offset,

2031 QualType ElemT) {

2032 assert(SL && "StringLiteral should not be null");

2033

2034

2035

2037 return svalBuilder.makeIntVal(Code, ElemT);

2038}

2039

2043 assert(BaseRegion);

2048 if (const std::optional &ParentValue =

2049 B.getDirectBinding(BaseRegion)) {

2050 if (SymbolRef ParentValueAsSym = ParentValue->getAsSymbol())

2052

2053 if (ParentValue->isUndef())

2055

2056

2057

2059 }

2060 }

2061 }

2062 return std::nullopt;

2063}

2064

2066 const ElementRegion* R) {

2067

2068 if (const std::optional &V = B.getDirectBinding(R))

2069 return *V;

2070

2072

2073

2074 if (const StringRegion *StrR = dyn_cast(superR)) {

2075

2076

2077

2080 return UnknownVal();

2081 if (const auto CI = R->getIndex().getAs nonloc::ConcreteInt()) {

2082 const llvm::APSInt &Idx = CI->getValue();

2083 if (Idx < 0)

2084 return UndefinedVal();

2085 const StringLiteral *SL = StrR->getStringLiteral();

2086 return getSValFromStringLiteral(SL, Idx.getZExtValue(), T);

2087 }

2089 if (std::optional V = getConstantValFromConstArrayInitializer(B, R))

2090 return *V;

2091 }

2092

2093

2095 return UnknownVal();

2096

2097

2098

2099

2100

2101

2102

2104

2105

2107 return UnknownVal();

2108

2109 if (const TypedValueRegion *baseR = dyn_cast(O.getRegion()))

2111 return *V;

2112

2113 return getBindingForFieldOrElementCommon(B, R, R->getElementType());

2114}

2115

2117 const FieldRegion* R) {

2118

2119

2120 if (const std::optional &V = B.getDirectBinding(R))

2121 return *V;

2122

2123

2124 const FieldDecl *FD = R->getDecl();

2125 QualType Ty = FD->getType();

2127 if (const auto *VR = dyn_cast(superR)) {

2128 const VarDecl *VD = VR->getDecl();

2129 QualType RecordVarTy = VD->getType();

2131

2132

2133

2137 if (const auto *InitList = dyn_cast(Init)) {

2138 if (Index < InitList->getNumInits()) {

2139 if (const Expr *FieldInit = InitList->getInit(Index))

2140 if (std::optional V = svalBuilder.getConstantVal(FieldInit))

2141 return *V;

2142 } else {

2144 }

2145 }

2146 }

2147

2148

2149

2150

2151

2152

2153

2154

2155

2156

2157

2158

2159

2160

2161

2162

2163

2164 if (const auto *Base = dyn_cast(R->getBaseRegion()))

2166 return *V;

2167

2168 return getBindingForFieldOrElementCommon(B, R, Ty);

2169}

2170

2171std::optional RegionStoreManager::getBindingForDerivedDefaultValue(

2173 const TypedValueRegion *R, QualType Ty) {

2174

2175 if (const std::optional &D = B.getDefaultBinding(superR)) {

2176 SVal val = *D;

2179

2182

2184 return val;

2185

2186

2187

2189 return val;

2190

2191 llvm_unreachable("Unknown default value");

2192 }

2193

2194 return std::nullopt;

2195}

2196

2197SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,

2198 RegionBindingsRef LazyBinding) {

2200 if (const ElementRegion *ER = dyn_cast(LazyBindingRegion))

2201 Result = getBindingForElement(LazyBinding, ER);

2202 else

2203 Result = getBindingForField(LazyBinding,

2205

2206

2207

2208

2209

2210

2211

2212

2213

2214

2215

2216

2217

2218

2219

2220 if (Result.isUndef())

2221 Result = UnknownVal();

2222

2224}

2225

2226SVal

2228 const TypedValueRegion *R,

2229 QualType Ty) {

2230

2231

2232

2233

2234

2235 Store lazyBindingStore = nullptr;

2236 const SubRegion *lazyBindingRegion = nullptr;

2237 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);

2238 if (lazyBindingRegion)

2239 return getLazyBinding(lazyBindingRegion,

2240 getRegionBindings(lazyBindingStore));

2241

2242

2243

2244 bool hasSymbolicIndex = false;

2245

2246

2247

2248

2249

2250

2251

2252

2253

2254

2255

2256

2257

2258

2259

2260 bool hasPartialLazyBinding = false;

2261

2262 const SubRegion *SR = R;

2263 while (SR) {

2265 if (std::optional D =

2266 getBindingForDerivedDefaultValue(B, Base, R, Ty)) {

2267 if (D->getAsnonloc::LazyCompoundVal()) {

2268 hasPartialLazyBinding = true;

2269 break;

2270 }

2271

2272 return *D;

2273 }

2274

2275 if (const ElementRegion *ER = dyn_cast(Base)) {

2276 NonLoc index = ER->getIndex();

2278 hasSymbolicIndex = true;

2279 }

2280

2281

2282

2283 SR = dyn_cast(Base);

2284 }

2285

2288

2289

2290 if (const TypedValueRegion *typedSuperR =

2292 if (typedSuperR->getValueType()->isVectorType())

2293 return UnknownVal();

2294 }

2295 }

2296

2297

2298

2299

2300

2301 if (hasSymbolicIndex)

2302 return UnknownVal();

2303

2304

2305

2306

2308 if (const std::optional &V = B.getDefaultBinding(R))

2309 return *V;

2310 return UndefinedVal();

2311 }

2312 }

2313

2314

2316}

2317

2319 const ObjCIvarRegion* R) {

2320

2321 if (const std::optional &V = B.getDirectBinding(R))

2322 return *V;

2323

2325

2326

2327 if (const std::optional &V = B.getDefaultBinding(superR)) {

2328 if (SymbolRef parentSym = V->getAsSymbol())

2330

2331

2332 return UnknownVal();

2333 }

2334

2335 return getBindingForLazySymbol(R);

2336}

2337

2339 const VarRegion *R) {

2340

2341

2342 if (std::optional V = B.getDirectBinding(R))

2343 return *V;

2344

2345 if (std::optional V = B.getDefaultBinding(R))

2346 return *V;

2347

2348

2349 const VarDecl *VD = R->getDecl();

2351

2352

2355

2356

2360 return *V;

2361

2362

2363

2364

2365 return UnknownVal();

2366 }

2367 }

2368

2369

2370

2373

2376

2377

2378 if (B.isMainAnalysis())

2381 return *V;

2382

2383

2384

2385

2386

2389

2390 if (std::optional V = getBindingForDerivedDefaultValue(B, MS, R, T)) {

2391 assert(->getAsnonloc::LazyCompoundVal());

2392 return *V;

2393 }

2394

2396 }

2397

2398 return UndefinedVal();

2399}

2400

2401SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {

2402

2404}

2405

2406const RegionStoreManager::SValListTy &

2407RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {

2408

2409 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());

2410 if (I != LazyBindingsMap.end())

2411 return I->second;

2412

2413

2414 SValListTy List;

2415

2416 const SubRegion *LazyR = LCV.getRegion();

2417 RegionBindingsRef B = getRegionBindings(LCV.getStore());

2418

2419

2420

2422 if (!Cluster)

2423 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));

2424

2425 SmallVector<BindingPair, 32> Bindings;

2427 true);

2428 for (SVal V : llvm::make_second_range(Bindings)) {

2429 if (V.isUnknownOrUndef() || V.isConstant())

2430 continue;

2431

2432 if (auto InnerLCV = V.getAsnonloc::LazyCompoundVal()) {

2433 const SValListTy &InnerList = getInterestingValues(*InnerLCV);

2434 llvm::append_range(List, InnerList);

2435 }

2436

2437 List.push_back(V);

2438 }

2439

2440 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));

2441}

2442

2444 const TypedValueRegion *R) {

2445 if (std::optionalnonloc::LazyCompoundVal V =

2447 return *V;

2448

2449 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R);

2450}

2451

2453 const TypedValueRegion *R) {

2454 const RecordDecl *RD =

2457 return UnknownVal();

2458

2459

2460

2461

2462

2463 return createLazyBinding(B, R);

2464}

2465

2467 const TypedValueRegion *R) {

2469 "Only constant array types can have compound bindings.");

2470

2471 return createLazyBinding(B, R);

2472}

2473

2474bool RegionStoreManager::includedInBindings(Store store,

2475 const MemRegion *region) const {

2476 RegionBindingsRef B = getRegionBindings(store);

2478

2479

2480 if (B.lookup(region))

2481 return true;

2482

2483

2484 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {

2486 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();

2487 CI != CE; ++CI) {

2488 SVal D = CI.getData();

2489 if (const MemRegion *R = D.getAsRegion())

2491 return true;

2492 }

2493 }

2494

2495 return false;

2496}

2497

2498

2499

2500

2501

2502StoreRef RegionStoreManager::killBinding(Store ST, Loc L) {

2503 if (std::optionalloc::MemRegionVal LV = L.getAs loc::MemRegionVal())

2504 if (const MemRegion* R = LV->getRegion())

2505 return StoreRef(getRegionBindings(ST)

2506 .removeBinding(R)

2507 .asImmutableMap()

2508 .getRootWithoutRetain(),

2509 *this);

2510

2511 return StoreRef(ST, *this);

2512}

2513

2514LimitedRegionBindingsRef

2516 llvm::TimeTraceScope TimeScope("RegionStoreManager::bind",

2517 [&L]() { return locDescr(L); });

2518

2521

2522

2523 auto MemRegVal = L.getAs loc::MemRegionVal();

2524 if (!MemRegVal)

2525 return B;

2526

2527 const MemRegion *R = MemRegVal->getRegion();

2528

2529

2530

2531 if (const auto *SymReg = dyn_cast(R)) {

2532 QualType Ty = SymReg->getPointeeStaticType();

2534 Ty = StateMgr.getContext().CharTy;

2535 R = GetElementZeroRegion(SymReg, Ty);

2536 }

2537

2538

2539 if (const TypedValueRegion* TR = dyn_cast(R)) {

2542 return bindArray(B, TR, V);

2544 return bindStruct(B, TR, V);

2546 return bindVector(B, TR, V);

2548 return bindAggregate(B, TR, V);

2549 }

2550

2552 "'this' pointer is not an l-value and is not assignable");

2553

2554

2555 auto NewB = removeSubRegionBindings(B, cast(R));

2556

2557

2559 : BindingKey::Direct;

2560 return NewB.addBinding(BindingKey::Make(R, KeyKind), V);

2561}

2562

2563LimitedRegionBindingsRef

2565 const MemRegion *R, QualType T) {

2567 return B;

2568

2569 SVal V;

2570

2576

2577

2579 }

2580 else {

2581

2582

2583

2584

2586 V = UnknownVal();

2587 }

2588

2589 return B.addBinding(R, BindingKey::Default, V);

2590}

2591

2592std::optional RegionStoreManager::tryBindSmallArray(

2594 const ArrayType *AT, nonloc::LazyCompoundVal LCV) {

2597

2598 auto CAT = dyn_cast(AT);

2599

2600

2601 if (!CAT)

2602 return std::nullopt;

2603

2606 return std::nullopt;

2607

2608

2610 if (ArrSize > SmallArrayLimit)

2611 return std::nullopt;

2612

2613 LimitedRegionBindingsRef NewB = B;

2614

2615 for (uint64_t i = 0; i < ArrSize; ++i) {

2617 const ElementRegion *SrcER =

2618 MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx);

2619 SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER);

2620

2621 const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx);

2622 NewB = bind(NewB, loc::MemRegionVal(DstER), V);

2623 }

2624

2625 return NewB;

2626}

2627

2628LimitedRegionBindingsRef

2630 const TypedValueRegion *R, SVal Init) {

2631 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindArray",

2635

2638 std::optional<uint64_t> Size;

2639

2640 if (const ConstantArrayType* CAT = dyn_cast(AT))

2642

2643

2644

2645

2646 if (std::optionalloc::MemRegionVal MRV = Init.getAsloc::MemRegionVal()) {

2647 SVal V = getBinding(B.asStore(), *MRV, R->getValueType());

2648 return bindAggregate(B, R, V);

2649 }

2650

2651

2652

2653 if (Init.isConstant())

2654 return bindAggregate(B, R, Init);

2655

2656 if (std::optional LCV = Init.getAsnonloc::LazyCompoundVal()) {

2657 if (std::optional NewB = tryBindSmallArray(B, R, AT, *LCV))

2658 return *NewB;

2659 return bindAggregate(B, R, Init);

2660 }

2661

2663 return bindAggregate(B, R, Init);

2664

2665 if (Init.isUnknown())

2666 return bindAggregate(B, R, UnknownVal());

2667

2668

2669 const nonloc::CompoundVal& CV = Init.castAsnonloc::CompoundVal();

2672

2673 LimitedRegionBindingsRef NewB = B;

2674

2675 for (; Size ? i < *Size : true; ++i, ++VI) {

2676

2677 if (VI == VE)

2678 break;

2681

2683 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);

2684

2686 NewB = bindStruct(NewB, ER, *VI);

2688 NewB = bindArray(NewB, ER, *VI);

2689 else

2690 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);

2691 }

2692

2693

2694

2695

2696 if (!Size || i < *Size)

2697 NewB = setImplicitDefaultValue(NewB, R, ElementTy);

2698

2699 return NewB;

2700}

2701

2702LimitedRegionBindingsRef

2704 const TypedValueRegion *R, SVal V) {

2705 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindVector",

2709

2711 const VectorType *VT = T->castAs();

2712

2713

2715 return bindAggregate(B, R, V);

2716

2717

2718

2719

2721 return bindAggregate(B, R, UnknownVal());

2722 }

2723

2725 nonloc::CompoundVal CV = V.castAs nonloc::CompoundVal();

2727 unsigned index = 0, numElements = VT->getNumElements();

2728 LimitedRegionBindingsRef NewB = B;

2729

2730 for ( ; index != numElements ; ++index) {

2731 if (VI == VE)

2732 break;

2733

2736

2738 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);

2739

2741 NewB = bindArray(NewB, ER, *VI);

2743 NewB = bindStruct(NewB, ER, *VI);

2744 else

2745 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);

2746 }

2747 return NewB;

2748}

2749

2750std::optional RegionStoreManager::tryBindSmallStruct(

2752 const RecordDecl *RD, nonloc::LazyCompoundVal LCV) {

2755

2757

2758 if (const CXXRecordDecl *Class = dyn_cast(RD))

2759 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0)

2760 return std::nullopt;

2761

2762 for (const auto *FD : RD->fields()) {

2764 continue;

2765

2766

2767

2768 if (Fields.size() == SmallStructLimit)

2769 return std::nullopt;

2770

2771 QualType Ty = FD->getType();

2772

2773

2776 continue;

2777

2779 return std::nullopt;

2780

2781 Fields.push_back(FD);

2782 }

2783

2784 LimitedRegionBindingsRef NewB = B;

2785

2786 for (const FieldDecl *Field : Fields) {

2787 const FieldRegion *SourceFR = MRMgr.getFieldRegion(Field, LCV.getRegion());

2788 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);

2789

2790 const FieldRegion *DestFR = MRMgr.getFieldRegion(Field, R);

2791 NewB = bind(NewB, loc::MemRegionVal(DestFR), V);

2792 }

2793

2794 return NewB;

2795}

2796

2797LimitedRegionBindingsRef

2799 const TypedValueRegion *R, SVal V) {

2800 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindStruct",

2804

2807

2810 return B;

2811

2812

2813 if (std::optionalnonloc::LazyCompoundVal LCV =

2814 V.getAsnonloc::LazyCompoundVal()) {

2815 if (std::optional NewB = tryBindSmallStruct(B, R, RD, *LCV))

2816 return *NewB;

2817 return bindAggregate(B, R, V);

2818 }

2820 return bindAggregate(B, R, V);

2821

2822

2823

2824

2826 return bindAggregate(B, R, UnknownVal());

2827

2828

2829

2830

2831

2832

2833

2834

2835

2836

2837

2838

2839

2840

2841

2842

2843

2844 const nonloc::CompoundVal& CV = V.castAs nonloc::CompoundVal();

2846

2847 LimitedRegionBindingsRef NewB = B;

2848

2849

2850

2851 if (const auto *CRD = dyn_cast(RD)) {

2852

2853

2854

2855

2856

2857

2858

2859 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) &&

2860 "Non-aggregates are constructed with a constructor!");

2861

2862 for (const auto &B : CRD->bases()) {

2863

2864 assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!");

2865

2866 if (VI == VE)

2867 break;

2870

2871 QualType BTy = B.getType();

2873

2875 assert(BRD && "Base classes must be C++ classes!");

2876

2877 const CXXBaseObjectRegion *BR =

2878 MRMgr.getCXXBaseObjectRegion(BRD, R, false);

2879

2880 NewB = bindStruct(NewB, BR, *VI);

2881

2882 ++VI;

2883 }

2884 }

2885

2887

2889

2890 if (VI == VE)

2891 break;

2892

2895

2896

2897 if (FI->isUnnamedBitField())

2898 continue;

2899

2900 QualType FTy = FI->getType();

2901 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);

2902

2904 NewB = bindArray(NewB, FR, *VI);

2906 NewB = bindStruct(NewB, FR, *VI);

2907 else

2908 NewB = bind(NewB, loc::MemRegionVal(FR), *VI);

2909 ++VI;

2910 }

2911

2914

2915

2916 if (FI != FE) {

2917 NewB = NewB.addBinding(R, BindingKey::Default,

2919 }

2920

2921 return NewB;

2922}

2923

2924LimitedRegionBindingsRef

2926 const TypedRegion *R, SVal Val) {

2927 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindAggregate",

2931

2932

2933

2934 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);

2935}

2936

2937

2938

2939

2940

2941namespace {

2942class RemoveDeadBindingsWorker

2943 : public ClusterAnalysis {

2944 SmallVector<const SymbolicRegion *, 12> Postponed;

2945 SymbolReaper &SymReaper;

2946 const StackFrameContext *CurrentLCtx;

2947

2948public:

2949 RemoveDeadBindingsWorker(RegionStoreManager &rm,

2950 ProgramStateManager &stateMgr,

2951 RegionBindingsRef b, SymbolReaper &symReaper,

2952 const StackFrameContext *LCtx)

2953 : ClusterAnalysis(rm, stateMgr, b),

2954 SymReaper(symReaper), CurrentLCtx(LCtx) {}

2955

2956

2957 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);

2958 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);

2959 using ClusterAnalysis::VisitCluster;

2960

2961 using ClusterAnalysis::AddToWorkList;

2962

2963 bool AddToWorkList(const MemRegion *R);

2964

2965 bool UpdatePostponed();

2966 void VisitBinding(SVal V);

2967};

2968}

2969

2970bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) {

2972 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));

2973}

2974

2975void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,

2977

2978 if (const VarRegion *VR = dyn_cast(baseR)) {

2979 if (SymReaper.isLive(VR))

2980 AddToWorkList(baseR, &C);

2981

2982 return;

2983 }

2984

2985 if (const SymbolicRegion *SR = dyn_cast(baseR)) {

2986 if (SymReaper.isLive(SR->getSymbol()))

2987 AddToWorkList(SR, &C);

2988 else

2989 Postponed.push_back(SR);

2990

2991 return;

2992 }

2993

2995 AddToWorkList(baseR, &C);

2996 return;

2997 }

2998

2999

3000 if (const CXXThisRegion *TR = dyn_cast(baseR)) {

3001 const auto *StackReg =

3003 const StackFrameContext *RegCtx = StackReg->getStackFrame();

3004 if (CurrentLCtx &&

3005 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)))

3006 AddToWorkList(TR, &C);

3007 }

3008}

3009

3010void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,

3012 if ()

3013 return;

3014

3015

3016

3017 if (const SymbolicRegion *SymR = dyn_cast(baseR))

3018 SymReaper.markLive(SymR->getSymbol());

3019

3020 for (const auto &[Key, Val] : *C) {

3021

3023

3024 VisitBinding(Val);

3025 }

3026}

3027

3028void RemoveDeadBindingsWorker::VisitBinding(SVal V) {

3029

3030

3031 if (auto LCS = V.getAsnonloc::LazyCompoundVal()) {

3033

3034 for (SVal V : RM.getInterestingValues(*LCS)) {

3035 if (auto DepLCS = V.getAsnonloc::LazyCompoundVal())

3037 else

3038 VisitBinding(V);

3039 }

3040

3041 return;

3042 }

3043

3044

3045 if (const MemRegion *R = V.getAsRegion()) {

3046 AddToWorkList(R);

3048

3049

3050 if (const BlockDataRegion *BR = dyn_cast(R)) {

3051 for (auto Var : BR->referenced_vars())

3052 AddToWorkList(Var.getCapturedRegion());

3053 }

3054 }

3055

3056

3057

3060}

3061

3062bool RemoveDeadBindingsWorker::UpdatePostponed() {

3063

3064

3066

3067 for (const SymbolicRegion *SR : Postponed) {

3068 if (SymReaper.isLive(SR->getSymbol())) {

3069 Changed |= AddToWorkList(SR);

3070 SR = nullptr;

3071 }

3072 }

3073

3075}

3076

3077StoreRef RegionStoreManager::removeDeadBindings(Store store,

3078 const StackFrameContext *LCtx,

3079 SymbolReaper& SymReaper) {

3080 RegionBindingsRef B = getRegionBindings(store);

3081 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);

3082 W.GenerateClusters();

3083

3084

3085 for (const MemRegion *Reg : SymReaper.regions()) {

3086 W.AddToWorkList(Reg);

3087 }

3088

3089 do W.RunWorkList(); while (W.UpdatePostponed());

3090

3091

3092

3093

3094 for (const MemRegion *Base : llvm::make_first_range(B)) {

3095

3096

3097 if (!W.isVisited(Base))

3098 B = B.removeCluster(Base);

3099 }

3100

3101 return StoreRef(B.asStore(), *this);

3102}

3103

3104

3105

3106

3107

3108void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL,

3109 unsigned int Space, bool IsDot) const {

3110 RegionBindingsRef Bindings = getRegionBindings(S);

3111

3112 Indent(Out, Space, IsDot) << "\"store\": ";

3113

3115 Out << "null," << NL;

3116 return;

3117 }

3118

3119 Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL;

3120 Bindings.printJson(Out, NL, Space + 1, IsDot);

3121 Indent(Out, Space, IsDot) << "]}," << NL;

3122}

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

static const MemRegion * getRegion(const CallEvent &Call, const MutexDescriptor &Descriptor, bool IsLock)

static void dump(llvm::raw_ostream &OS, StringRef FunctionName, ArrayRef< CounterExpression > Expressions, ArrayRef< CounterMappingRegion > Regions)

bool is(tok::TokenKind Kind) const

static std::optional< SVal > convertOffsetsFromSvalToUnsigneds(const SmallVector< SVal, 2 > &SrcOffsets, const SmallVector< uint64_t, 2 > ArrayExtents, SmallVector< uint64_t, 2 > &DstOffsets)

Definition RegionStore.cpp:1827

llvm::ImmutableMap< const MemRegion *, ClusterBindings > RegionBindings

Definition RegionStore.cpp:163

static std::optional< SVal > getDerivedSymbolForBinding(RegionBindingsConstRef B, const TypedValueRegion *BaseRegion, const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB)

Definition RegionStore.cpp:2040

std::pair< BindingKey, SVal > BindingPair

Definition RegionStore.cpp:160

static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields)

Definition RegionStore.cpp:990

SmallVector< const FieldDecl *, 8 > FieldVector

Definition RegionStore.cpp:973

llvm::ImmutableMap< BindingKey, SVal > ClusterBindings

Definition RegionStore.cpp:158

static bool isUnionField(const FieldRegion *FR)

Definition RegionStore.cpp:969

const LimitedRegionBindingsRef & LimitedRegionBindingsConstRef

Definition RegionStore.cpp:403

static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields)

Definition RegionStore.cpp:975

static QualType getUnderlyingType(const SubRegion *R)

Definition RegionStore.cpp:1667

llvm::ImmutableMapRef< BindingKey, SVal > ClusterBindingsRef

Definition RegionStore.cpp:159

static SmallVector< uint64_t, 2 > getConstantArrayExtents(const ConstantArrayType *CAT)

This is a helper function for getConstantValFromConstArrayInitializer.

Definition RegionStore.cpp:1768

static std::pair< SmallVector< SVal, 2 >, const MemRegion * > getElementRegionOffsetsWithBase(const ElementRegion *ER)

This is a helper function for getConstantValFromConstArrayInitializer.

Definition RegionStore.cpp:1793

const RegionBindingsRef & RegionBindingsConstRef

Definition RegionStore.cpp:402

static std::optional< nonloc::LazyCompoundVal > getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B, const SubRegion *R, bool AllowSubregionBindings)

Checks to see if store B has a lazy binding for region R.

Definition RegionStore.cpp:1686

static void collectSubRegionBindings(SmallVectorImpl< BindingPair > &Bindings, SValBuilder &SVB, const ClusterBindings &Cluster, const SubRegion *Top, BindingKey TopKey, bool IncludeAllDefaultBindings)

Collects all bindings in Cluster that may refer to bindings within Top.

Definition RegionStore.cpp:1019

llvm::SmallVector< std::pair< const MemRegion *, SVal >, 4 > Bindings

__PTRDIFF_TYPE__ ptrdiff_t

A signed integer type that is the result of subtracting two pointers.

This class represents the same as RegionBindingsRef, but with a limit on the number of bindings that ...

Definition RegionStore.cpp:333

LimitedRegionBindingsRef removeCluster(const MemRegion *BaseRegion) const

Definition RegionStore.cpp:367

LimitedRegionBindingsRef withValuesEscaped(nonloc::CompoundVal::iterator Begin, nonloc::CompoundVal::iterator End) const

Definition RegionStore.cpp:352

LimitedRegionBindingsRef withValuesEscaped(SVal V) const

Definition RegionStore.cpp:346

LimitedRegionBindingsRef(RegionBindingsRef Base, SmallVectorImpl< SVal > &EscapedValuesDuringBind, std::optional< unsigned > BindingsLeft)

Definition RegionStore.cpp:335

bool hasExhaustedBindingLimit() const

Definition RegionStore.cpp:342

LimitedRegionBindingsRef addBinding(BindingKey K, SVal V) const

Definition RegionStore.cpp:373

LimitedRegionBindingsRef addBinding(const MemRegion *R, BindingKey::Kind k, SVal V) const

Definition RegionStore.cpp:392

LimitedRegionBindingsRef addWithoutDecreasingLimit(const MemRegion *BaseRegion, data_type_ref BindingKeyAndValue) const

Definition RegionStore.cpp:360

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

const ConstantArrayType * getAsConstantArrayType(QualType T) const

static CanQualType getCanonicalType(QualType T)

Return the canonical (structural) type corresponding to the specified potentially non-canonical type ...

const LangOptions & getLangOpts() const

const ArrayType * getAsArrayType(QualType T) const

Type Query functions.

uint64_t getTypeSize(QualType T) const

Return the size of the specified (complete) type T, in bits.

CharUnits getTypeSizeInChars(QualType T) const

Return the size of the specified (complete) type T, in characters.

uint64_t getConstantArrayElementCount(const ConstantArrayType *CA) const

Return number of constant array elements.

static bool hasSameUnqualifiedType(QualType T1, QualType T2)

Determine whether the given types are equivalent after cvr-qualifiers have been removed.

uint64_t getCharWidth() const

Return the size of the character type, in bits.

QualType getElementType() const

Represents the canonical version of C arrays with a specified constant size.

uint64_t getLimitedSize() const

Return the size zero-extended to uint64_t or UINT64_MAX if the value is larger than UINT64_MAX.

uint64_t getZExtSize() const

Return the size zero-extended as a uint64_t.

unsigned getFieldIndex() const

Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...

const RecordDecl * getParent() const

Returns the parent of this field declaration, which is the struct in which this field is defined.

bool isUnnamedBitField() const

Determines whether this is an unnamed bitfield.

bool isStringLiteralInit() const

Is this an initializer for an array of characters, initialized by a string literal or an @encode?

unsigned getNumInits() const

const Expr * getInit(unsigned Init) const

bool isParentOf(const LocationContext *LC) const

const Decl * getDecl() const

A (possibly-)qualified type.

bool isNull() const

Return true if this QualType doesn't point to a type yet.

bool isConstQualified() const

Determine whether this type is const-qualified.

field_iterator field_end() const

field_range fields() const

RecordDecl * getDefinition() const

Returns the RecordDecl that actually defines this struct/union/class.

specific_decl_iterator< FieldDecl > field_iterator

field_iterator field_begin() const

unsigned getLength() const

uint32_t getCodeUnit(size_t i) const

bool isCompleteDefinition() const

Return true if this decl has its body fully specified.

CXXRecordDecl * getAsCXXRecordDecl() const

Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...

bool isConstantArrayType() const

bool isVoidPointerType() const

const T * castAs() const

Member-template castAs.

bool isReferenceType() const

bool isScalarType() const

QualType getPointeeType() const

If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.

bool isIntegralOrEnumerationType() const

Determine whether this type is an integral or enumeration type.

RecordDecl * castAsRecordDecl() const

bool isAnyComplexType() const

QualType getCanonicalTypeInternal() const

bool isStructureOrClassType() const

bool isVectorType() const

const T * castAsCanonical() const

Return this type's canonical type cast to the specified type.

bool isRecordType() const

bool hasGlobalStorage() const

Returns true for all variables that do not have local storage.

bool hasLocalStorage() const

Returns true if a variable with function scope is a non-static local variable.

const Expr * getAnyInitializer() const

Get the initializer for this variable, no matter which declaration it is attached to.

unsigned getNumElements() const

QualType getElementType() const

ElementRegion is used to represent both array elements and casts.

QualType getElementType() const

RegionRawOffset getAsArrayOffset() const

Compute the offset within the array. The array might also be a subobject.

LLVM_ATTRIBUTE_RETURNS_NONNULL const FieldDecl * getDecl() const override

void dumpToStream(raw_ostream &Out) const

static bool isLocType(QualType T)

DefinedOrUnknownSVal getStaticSize(const MemRegion *MR, SValBuilder &SVB) const

MemRegion - The root abstract class for all memory regions.

virtual bool isBoundable() const

RegionOffset getAsOffset() const

Compute the offset within the top level memory object.

std::string getDescriptiveName(bool UseQuotes=true) const

Get descriptive name for memory region.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getBaseRegion() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemSpaceRegion * getRawMemorySpace() const

Deprecated.

@ TK_PreserveContents

Tells that a region's contents is not changed.

@ TK_DoNotInvalidateSuperRegion

@ TK_EntireMemSpace

When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.

bool hasTrait(SymbolRef Sym, InvalidationKinds IK) const

bool hasSymbolicOffset() const

const MemRegion * getRegion() const

It might return null.

int64_t getOffset() const

const MemRegion * getRegion() const

DefinedOrUnknownSVal makeZeroVal(QualType type)

Construct an SVal representing '0' for the specified type.

NonLoc makeArrayIndex(uint64_t idx)

ASTContext & getContext()

nonloc::ConcreteInt makeIntVal(const IntegerLiteral *integer)

SVal evalCast(SVal V, QualType CastTy, QualType OriginalTy)

Cast a given SVal to another SVal using given QualType's.

DefinedOrUnknownSVal getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, const TypedValueRegion *region)

loc::ConcreteInt makeNullWithType(QualType type)

Create NULL pointer, with proper pointer bit-width for given address space.

std::optional< SVal > getConstantVal(const Expr *E)

Returns the value of E, if it can be determined in a non-path-sensitive manner.

DefinedOrUnknownSVal conjureSymbolVal(const void *symbolTag, ConstCFGElementRef elem, const LocationContext *LCtx, unsigned count)

Create a new symbol with a unique 'name'.

NonLoc makeZeroArrayIndex()

DefinedOrUnknownSVal getRegionValueSymbolVal(const TypedValueRegion *region)

Make a unique symbol for value of region.

NonLoc makeLazyCompoundVal(const StoreRef &store, const TypedValueRegion *region)

SVal - This represents a symbolic expression, which can be either an L-value or an R-value.

bool isZeroConstant() const

bool isUnknownOrUndef() const

SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const

If this SVal wraps a symbol return that SymbolRef.

std::optional< T > getAs() const

Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.

const MemRegion * getAsRegion() const

T castAs() const

Convert to the specified SVal type, asserting that this SVal is of the desired type.

bool scan(nonloc::LazyCompoundVal val)

SmallVector< const MemRegion *, 8 > InvalidatedRegions

SubRegion - A region that subsets another larger region.

LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const

bool isSubRegionOf(const MemRegion *R) const override

Check if the region is a subregion of the given region.

MemRegionManager & getMemRegionManager() const override

llvm::iterator_range< symbol_iterator > symbols() const

static bool canSymbolicate(QualType T)

void markLive(SymbolRef sym)

Unconditionally marks a symbol as live.

void markElementIndicesLive(const MemRegion *region)

void markLazilyCopied(const MemRegion *region)

bool isLive(SymbolRef sym)

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

SymbolicRegion - A special, "non-concrete" region.

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

virtual QualType getValueType() const =0

QualType getLocationType() const override

QualType getValueType() const override

const VarDecl * getDecl() const override=0

llvm::ImmutableList< SVal >::iterator iterator

Value representing integer constant.

While nonloc::CompoundVal covers a few simple use cases, nonloc::LazyCompoundVal is a more performant...

LLVM_ATTRIBUTE_RETURNS_NONNULL const LazyCompoundValData * getCVData() const

LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const

This function itself is immaterial.

const void * getStore() const

It might return null.

Defines the clang::TargetInfo interface.

const internal::VariadicDynCastAllOfMatcher< Decl, VarDecl > varDecl

Matches variable declarations.

const internal::VariadicDynCastAllOfMatcher< Stmt, DeclRefExpr > declRefExpr

Matches expressions that refer to declarations.

const internal::ArgumentAdaptingMatcherFunc< internal::HasDescendantMatcher > hasDescendant

Matches AST nodes that have descendant AST nodes that match the provided matcher.

SmallVector< BoundNodes, 1 > match(MatcherT Matcher, const NodeT &Node, ASTContext &Context)

Returns the results of matching Matcher on Node.

internal::Matcher< Stmt > StatementMatcher

const internal::VariadicAllOfMatcher< Stmt > stmt

Matches statements.

llvm::DenseSet< SymbolRef > InvalidatedSymbols

const SymExpr * SymbolRef

@ OS

Indicates that the tracking object is a descendant of a referenced-counted OSObject,...

std::unique_ptr< StoreManager > CreateRegionStoreManager(ProgramStateManager &StMgr)

Definition RegionStore.cpp:838

const void * Store

Store - This opaque type encapsulates an immutable mapping from locations to values.

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

@ Match

This is not an overload because the signature exactly matches an existing declaration.

bool isa(CodeGen::Address addr)

CFGBlock::ConstCFGElementRef ConstCFGElementRef

@ Bind

'bind' clause, allowed on routine constructs.

bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)

bool operator<(DeclarationName LHS, DeclarationName RHS)

Ordering on two declaration names.

raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)

@ Result

The result type of a method or function.

const FunctionProtoType * T

const StreamingDiagnostic & operator<<(const StreamingDiagnostic &DB, const ConceptReference *C)

Insertion operator for diagnostics.

U cast(CodeGen::Address addr)

@ Class

The "class" keyword introduces the elaborated-type-specifier.

Diagnostic wrappers for TextAPI types for error reporting.

__UINTPTR_TYPE__ uintptr_t

An unsigned integer type with the property that any valid pointer to void can be converted to this ty...