clang 22.0.0git
RegionStore.cpp
Go to the documentation of this file.
1//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines a basic region store model. In this model, we do have field
10// sensitivity. But we assume nothing about the heap shape. So recursive data
11// structures are largely ignored. Basically we do 1-limiting analysis.
12// Parameter pointers are assumed with no aliasing. Pointee objects of
13// parameters are created lazily.
14//
15//===----------------------------------------------------------------------===//
16
17#include "clang/AST/Attr.h"
18#include "clang/AST/CharUnits.h"
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 <limits>
33#include <optional>
34#include <utility>
35
36using namespace clang;
37using namespace ento;
38
39//===----------------------------------------------------------------------===//
40// Representation of binding keys.
41//===----------------------------------------------------------------------===//
42
43namespace {
44class BindingKey {
45public:
46 enum Kind {
47 Default = 0x0,
48 Direct = 0x1,
49 Symbolic = 0x2,
50 };
51
52private:
53 llvm::PointerIntPair<const MemRegion *, 2> P;
54 uint64_t Data;
55
56 /// Create a key for a binding to region \p r, which has a symbolic offset
57 /// from region \p Base.
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 }
63
64 /// Create a key for a binding at \p offset from base region \p r.
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");
69 assert((r == r->getBaseRegion() ||
71 "Not a base");
72 }
73
74public:
75 bool isDirect() const { return P.getInt() & Direct; }
76 bool isDefault() const { return !isDirect(); }
77 bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }
78
79 const MemRegion *getRegion() const { return P.getPointer(); }
80 uint64_t getOffset() const {
81 assert(!hasSymbolicOffset());
82 return Data;
83 }
84
85 const SubRegion *getConcreteOffsetRegion() const {
86 assert(hasSymbolicOffset());
87 return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data));
88 }
89
90 const MemRegion *getBaseRegion() const {
91 if (hasSymbolicOffset())
92 return getConcreteOffsetRegion()->getBaseRegion();
93 return getRegion()->getBaseRegion();
94 }
95
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);
122 L.dumpToStream(OS);
123 return OS.str();
124}
125} // end anonymous namespace
126
127BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
128 const RegionOffset &RO = R->getAsOffset();
129 if (RO.hasSymbolicOffset())
130 return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k);
131
132 return BindingKey(RO.getRegion(), RO.getOffset(), k);
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} // namespace llvm
149
150#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
151void BindingKey::dump() const { llvm::errs() << *this; }
152#endif
153
154//===----------------------------------------------------------------------===//
155// Actual Store type.
156//===----------------------------------------------------------------------===//
157
158typedef llvm::ImmutableMap<BindingKey, SVal> ClusterBindings;
159typedef llvm::ImmutableMapRef<BindingKey, SVal> ClusterBindingsRef;
160typedef std::pair<BindingKey, SVal> BindingPair;
161
162typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
164
165namespace {
166class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,
167 ClusterBindings> {
168 ClusterBindings::Factory *CBFactory;
169
170 // This flag indicates whether the current bindings are within the analysis
171 // that has started from main(). It affects how we perform loads from
172 // global variables that have initializers: if we have observed the
173 // program execution from the start and we know that these variables
174 // have not been overwritten yet, we can be sure that their initializers
175 // are still relevant. This flag never gets changed when the bindings are
176 // updated, so it could potentially be moved into RegionStoreManager
177 // (as if it's the same bindings but a different loading procedure)
178 // however that would have made the manager needlessly stateful.
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;
206 using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup;
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<SVal> getDirectBinding(const MemRegion *R) const;
219
220 /// getDefaultBinding - Returns an SVal* representing an optional default
221 /// binding associated with a region and its subregions.
222 std::optional<SVal> getDefaultBinding(const MemRegion *R) const;
223
224 /// Return the internal tree as a Store.
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) {
256 if (isa<MemSpaceRegion>(L->first) && !isa<MemSpaceRegion>(R->first))
257 return true;
258 if (!isa<MemSpaceRegion>(L->first) && isa<MemSpaceRegion>(R->first))
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, /*AddQuotes=*/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,
327 const ClusterBindings &Bindings) const;
328};
329} // end anonymous namespace
330
331/// This class represents the same as \c RegionBindingsRef, but with a limit on
332/// the number of bindings that can be added.
333class LimitedRegionBindingsRef : public RegionBindingsRef {
334public:
336 SmallVectorImpl<SVal> &EscapedValuesDuringBind,
337 std::optional<unsigned> 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 {
362 return LimitedRegionBindingsRef{RegionBindingsRef::commitBindingsToCluster(
363 BaseRegion, BindingKeyAndValue),
364 *EscapedValuesDuringBind, BindingsLeft};
365 }
366
369 RegionBindingsRef::removeCluster(BaseRegion), *EscapedValuesDuringBind,
370 BindingsLeft};
371 }
372
374 std::optional<unsigned> NewBindingsLeft = BindingsLeft;
375 if (NewBindingsLeft.has_value()) {
376 assert(NewBindingsLeft.value() != 0);
377 NewBindingsLeft.value() -= 1;
378
379 // If we just exhausted the binding limit, highjack
380 // this bind call for the default binding.
381 if (NewBindingsLeft.value() == 0) {
383 K = BindingKey::Make(K.getRegion(), BindingKey::Default);
384 V = UnknownVal();
385 }
386 }
387
388 return LimitedRegionBindingsRef{RegionBindingsRef::addBinding(K, V),
389 *EscapedValuesDuringBind, NewBindingsLeft};
390 }
391
392 LimitedRegionBindingsRef addBinding(const MemRegion *R, BindingKey::Kind k,
393 SVal V) const {
394 return addBinding(BindingKey::Make(R, k), V);
395 }
396
397private:
398 SmallVectorImpl<SVal> *EscapedValuesDuringBind; // nonnull
399 std::optional<unsigned> BindingsLeft;
400};
401
402typedef const RegionBindingsRef& RegionBindingsConstRef;
404
405std::optional<SVal>
406RegionBindingsRef::getDirectBinding(const MemRegion *R) const {
407 const SVal *V = lookup(R, BindingKey::Direct);
408 return V ? std::optional<SVal>(*V) : std::nullopt;
409}
410
411std::optional<SVal>
412RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {
413 const SVal *V = lookup(R, BindingKey::Default);
414 return V ? std::optional<SVal>(*V) : std::nullopt;
415}
416
417RegionBindingsRef RegionBindingsRef::commitBindingsToCluster(
418 const MemRegion *BaseRegion, const ClusterBindings &Bindings) const {
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
426 const ClusterBindings *ExistingCluster = lookup(Base);
428 (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
429 Bindings = CBFactory->add(Bindings, K, V);
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();
453 const ClusterBindings *Cluster = lookup(Base);
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// Main RegionStore logic.
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<SVal> SValListTy;
481private:
482 typedef llvm::DenseMap<const LazyCompoundValData *,
483 SValListTy> LazyBindingsMapTy;
484 LazyBindingsMapTy LazyBindingsMap;
485
486 /// The largest number of fields a struct can have and still be
487 /// considered "small".
488 ///
489 /// This is currently used to decide whether or not it is worth "forcing" a
490 /// LazyCompoundVal on bind.
491 ///
492 /// This is controlled by 'region-store-small-struct-limit' option.
493 /// To disable all small-struct-dependent behavior, set the option to "0".
494 const unsigned SmallStructLimit;
495
496 /// The largest number of element an array can have and still be
497 /// considered "small".
498 ///
499 /// This is currently used to decide whether or not it is worth "forcing" a
500 /// LazyCompoundVal on bind.
501 ///
502 /// This is controlled by 'region-store-small-struct-limit' option.
503 /// To disable all small-struct-dependent behavior, set the option to "0".
504 const unsigned SmallArrayLimit;
505
506 /// The number of bindings a single bind operation can scatter into.
507 /// For example, binding the initializer-list of an array would recurse and
508 /// bind all the individual array elements, potentially causing scalability
509 /// issues. Nullopt if the limit is disabled.
510 const std::optional<unsigned> RegionStoreMaxBindingFanOutPlusOne;
511
512 /// A helper used to populate the work list with the given set of
513 /// regions.
514 void populateWorkList(InvalidateRegionsWorker &W,
515 ArrayRef<SVal> 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<unsigned> {
529 unsigned FanOut = getOptions().RegionStoreMaxBindingFanOut;
530 assert(FanOut != std::numeric_limits<unsigned>::max());
531 if (FanOut == 0)
532 return std::nullopt;
533 return FanOut + 1 /*for the default binding*/;
534 }()) {}
535
536 /// setImplicitDefaultValue - Set the default binding for the provided
537 /// MemRegion to the value implicitly defined for compound literals when
538 /// the value is not specified.
539 LimitedRegionBindingsRef
540 setImplicitDefaultValue(LimitedRegionBindingsConstRef B, const MemRegion *R,
541 QualType T);
542
543 /// ArrayToPointer - Emulates the "decay" of an array to a pointer
544 /// type. 'Array' represents the lvalue of the array being decayed
545 /// to a pointer, and the returned SVal represents the decayed
546 /// version of that lvalue (i.e., a pointer to the first element of
547 /// the array). This is called by ExprEngine when evaluating
548 /// casts from arrays to pointers.
549 SVal ArrayToPointer(Loc Array, QualType ElementTy) override;
550
551 /// Creates the Store that correctly represents memory contents before
552 /// the beginning of the analysis of the given top-level stack frame.
553 StoreRef getInitialStore(const LocationContext *InitLoc) override {
554 bool IsMainAnalysis = false;
555 if (const auto *FD = dyn_cast<FunctionDecl>(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 // Binding values to regions.
566 //===-------------------------------------------------------------------===//
567 RegionBindingsRef
568 invalidateGlobalRegion(MemRegion::Kind K, ConstCFGElementRef Elem,
569 unsigned Count, const LocationContext *LCtx,
570 RegionBindingsRef B, InvalidatedRegions *Invalidated);
571
572 StoreRef invalidateRegions(Store store, ArrayRef<SVal> Values,
573 ConstCFGElementRef Elem, unsigned Count,
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
584 removeSubRegionBindings(LimitedRegionBindingsConstRef B, const SubRegion *R);
585 std::optional<SVal>
586 getConstantValFromConstArrayInitializer(RegionBindingsConstRef B,
587 const ElementRegion *R);
588 std::optional<SVal>
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: // Part of public interface to class.
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
604 LimitedRegionBindingsRef bind(LimitedRegionBindingsConstRef B, Loc LV,
605 SVal V);
606
607 // BindDefaultInitial is only used to initialize a region with
608 // a default value.
609 BindResult BindDefaultInitial(Store store, const MemRegion *R,
610 SVal V) override {
611 RegionBindingsRef B = getRegionBindings(store);
612 // Use other APIs when you have to wipe the region that was initialized
613 // earlier.
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 // BindDefaultZero is used for zeroing constructors that may accidentally
622 // overwrite existing bindings.
623 BindResult BindDefaultZero(Store store, const MemRegion *R) override {
624 // FIXME: The offsets of empty bases can be tricky because of
625 // of the so called "empty base class optimization".
626 // If a base class has been optimized out
627 // we should not try to create a binding, otherwise we should.
628 // Unfortunately, at the moment ASTRecordLayout doesn't expose
629 // the actual sizes of the empty bases
630 // and trying to infer them from offsets/alignments
631 // seems to be error-prone and non-trivial because of the trailing padding.
632 // As a temporary mitigation we don't create bindings for empty bases.
633 if (const auto *BR = dyn_cast<CXXBaseObjectRegion>(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);
641 B = removeSubRegionBindings(B, cast<SubRegion>(R));
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 /// Attempt to extract the fields of \p LCV and bind them to the struct region
649 /// \p R.
650 ///
651 /// This path is used when it seems advantageous to "force" loading the values
652 /// within a LazyCompoundVal to bind memberwise to the struct region, rather
653 /// than using a Default binding at the base of the entire region. This is a
654 /// heuristic attempting to avoid building long chains of LazyCompoundVals.
655 ///
656 /// \returns The updated store bindings, or \c std::nullopt if binding
657 /// non-lazily would be too expensive.
658 std::optional<LimitedRegionBindingsRef>
659 tryBindSmallStruct(LimitedRegionBindingsConstRef B, const TypedValueRegion *R,
660 const RecordDecl *RD, nonloc::LazyCompoundVal LCV);
661
662 /// BindStruct - Bind a compound value to a structure.
663 LimitedRegionBindingsRef bindStruct(LimitedRegionBindingsConstRef B,
664 const TypedValueRegion *R, SVal V);
665
666 /// BindVector - Bind a compound value to a vector.
667 LimitedRegionBindingsRef bindVector(LimitedRegionBindingsConstRef B,
668 const TypedValueRegion *R, SVal V);
669
670 std::optional<LimitedRegionBindingsRef>
671 tryBindSmallArray(LimitedRegionBindingsConstRef B, const TypedValueRegion *R,
672 const ArrayType *AT, nonloc::LazyCompoundVal LCV);
673
674 LimitedRegionBindingsRef bindArray(LimitedRegionBindingsConstRef B,
675 const TypedValueRegion *R, SVal V);
676
677 /// Clears out all bindings in the given region and assigns a new value
678 /// as a Default binding.
679 LimitedRegionBindingsRef bindAggregate(LimitedRegionBindingsConstRef B,
680 const TypedRegion *R, SVal DefaultVal);
681
682 /// Create a new store with the specified binding removed.
683 /// \param ST the original store, that is the basis for the new store.
684 /// \param L the location whose binding should be removed.
685 StoreRef killBinding(Store ST, Loc L) override;
686
687 void incrementReferenceCount(Store store) override {
688 getRegionBindings(store).manualRetain();
689 }
690
691 /// If the StoreManager supports it, decrement the reference count of
692 /// the specified Store object. If the reference count hits 0, the memory
693 /// associated with the object is recycled.
694 void decrementReferenceCount(Store store) override {
695 getRegionBindings(store).manualRelease();
696 }
697
698 bool includedInBindings(Store store, const MemRegion *region) const override;
699
700 /// Return the value bound to specified location in a given state.
701 ///
702 /// The high level logic for this method is this:
703 /// getBinding (L)
704 /// if L has binding
705 /// return L's binding
706 /// else if L is in killset
707 /// return unknown
708 /// else
709 /// if L is on stack or heap
710 /// return undefined
711 /// else
712 /// return symbolic
713 SVal getBinding(Store S, Loc L, QualType T) override {
714 return getBinding(getRegionBindings(S), L, T);
715 }
716
717 std::optional<SVal> getUniqueDefaultBinding(RegionBindingsConstRef B,
718 const TypedValueRegion *R) const;
719 std::optional<SVal>
720 getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const;
721
722 std::optional<SVal> getDefaultBinding(Store S, const MemRegion *R) override {
723 RegionBindingsRef B = getRegionBindings(S);
724 // Default bindings are always applied over a base region so look up the
725 // base region's default binding, otherwise the lookup will fail when R
726 // is at an offset from R->getBaseRegion().
727 return B.getDefaultBinding(R->getBaseRegion());
728 }
729
730 SVal getBinding(RegionBindingsConstRef B, Loc L, QualType T = QualType());
731
732 SVal getBindingForElement(RegionBindingsConstRef B, const ElementRegion *R);
733
734 SVal getBindingForField(RegionBindingsConstRef B, const FieldRegion *R);
735
736 SVal getBindingForObjCIvar(RegionBindingsConstRef B, const ObjCIvarRegion *R);
737
738 SVal getBindingForVar(RegionBindingsConstRef B, const VarRegion *R);
739
740 SVal getBindingForLazySymbol(const TypedValueRegion *R);
741
742 SVal getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
743 const TypedValueRegion *R,
744 QualType Ty);
745
746 SVal getLazyBinding(const SubRegion *LazyBindingRegion,
747 RegionBindingsRef LazyBinding);
748
749 /// Get bindings for the values in a struct and return a CompoundVal, used
750 /// when doing struct copy:
751 /// struct s x, y;
752 /// x = y;
753 /// y's value is retrieved by this method.
754 SVal getBindingForStruct(RegionBindingsConstRef B, const TypedValueRegion *R);
755 SVal getBindingForArray(RegionBindingsConstRef B, const TypedValueRegion *R);
756 NonLoc createLazyBinding(RegionBindingsConstRef B, const TypedValueRegion *R);
757
758 /// Used to lazily generate derived symbols for bindings that are defined
759 /// implicitly by default bindings in a super region.
760 ///
761 /// Note that callers may need to specially handle LazyCompoundVals, which
762 /// are returned as is in case the caller needs to treat them differently.
763 std::optional<SVal>
764 getBindingForDerivedDefaultValue(RegionBindingsConstRef B,
765 const MemRegion *superR,
766 const TypedValueRegion *R, QualType Ty);
767
768 /// Get the state and region whose binding this region \p R corresponds to.
769 ///
770 /// If there is no lazy binding for \p R, the returned value will have a null
771 /// \c second. Note that a null pointer can represents a valid Store.
772 std::pair<Store, const SubRegion *>
773 findLazyBinding(RegionBindingsConstRef B, const SubRegion *R,
774 const SubRegion *originalRegion);
775
776 /// Returns the cached set of interesting SVals contained within a lazy
777 /// binding.
778 ///
779 /// The precise value of "interesting" is determined for the purposes of
780 /// RegionStore's internal analysis. It must always contain all regions and
781 /// symbols, but may omit constants and other kinds of SVal.
782 ///
783 /// In contrast to compound values, LazyCompoundVals are also added
784 /// to the 'interesting values' list in addition to the child interesting
785 /// values.
786 const SValListTy &getInterestingValues(nonloc::LazyCompoundVal LCV);
787
788 //===------------------------------------------------------------------===//
789 // State pruning.
790 //===------------------------------------------------------------------===//
791
792 /// removeDeadBindings - Scans the RegionStore of 'state' for dead values.
793 /// It returns a new Store with these values removed.
794 StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
795 SymbolReaper& SymReaper) override;
796
797 //===------------------------------------------------------------------===//
798 // Utility methods.
799 //===------------------------------------------------------------------===//
800
801 RegionBindingsRef getRegionBindings(Store store) const {
802 llvm::PointerIntPair<Store, 1, bool> Ptr;
803 Ptr.setFromOpaqueValue(const_cast<void *>(store));
804 return {CBFactory,
805 static_cast<const RegionBindings::TreeTy *>(Ptr.getPointer()),
806 RBFactory.getTreeFactory(), Ptr.getInt()};
807 }
808
809 LimitedRegionBindingsRef
810 getRegionBindings(Store store,
811 SmallVectorImpl<SVal> &EscapedValuesDuringBind) const {
812 return LimitedRegionBindingsRef(
813 getRegionBindings(store), EscapedValuesDuringBind,
814 /*BindingsLeft=*/RegionStoreMaxBindingFanOutPlusOne);
815 }
816
817 void printJson(raw_ostream &Out, Store S, const char *NL = "\n",
818 unsigned int Space = 0, bool IsDot = false) const override;
819
820 void iterBindings(Store store, BindingsHandler& f) override {
821 RegionBindingsRef B = getRegionBindings(store);
822 for (const auto &[Region, Cluster] : B) {
823 for (const auto &[Key, Value] : Cluster) {
824 if (!Key.isDirect())
825 continue;
826 if (const SubRegion *R = dyn_cast<SubRegion>(Key.getRegion())) {
827 // FIXME: Possibly incorporate the offset?
828 if (!f.HandleBinding(*this, store, R, Value))
829 return;
830 }
831 }
832 }
833 }
834};
835
836} // end anonymous namespace
837
838//===----------------------------------------------------------------------===//
839// RegionStore creation.
840//===----------------------------------------------------------------------===//
841
842std::unique_ptr<StoreManager>
844 return std::make_unique<RegionStoreManager>(StMgr);
845}
846
847//===----------------------------------------------------------------------===//
848// Region Cluster analysis.
849//===----------------------------------------------------------------------===//
850
851namespace {
852/// Used to determine which global regions are automatically included in the
853/// initial worklist of a ClusterAnalysis.
854enum GlobalsFilterKind {
855 /// Don't include any global regions.
856 GFK_None,
857 /// Only include system globals.
858 GFK_SystemOnly,
859 /// Include all global regions.
860 GFK_All
861};
862
863template <typename DERIVED>
864class ClusterAnalysis {
865protected:
866 typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
867 typedef const MemRegion * WorkListElement;
869
871
872 WorkList WL;
873
874 RegionStoreManager &RM;
875 ASTContext &Ctx;
876 SValBuilder &svalBuilder;
877
878 RegionBindingsRef B;
879
880
881protected:
882 const ClusterBindings *getCluster(const MemRegion *R) {
883 return B.lookup(R);
884 }
885
886 /// Returns true if all clusters in the given memspace should be initially
887 /// included in the cluster analysis. Subclasses may provide their
888 /// own implementation.
889 bool includeEntireMemorySpace(const MemRegion *Base) {
890 return false;
891 }
892
893public:
894 ClusterAnalysis(RegionStoreManager &rm, ProgramStateManager &StateMgr,
895 RegionBindingsRef b)
896 : RM(rm), Ctx(StateMgr.getContext()),
897 svalBuilder(StateMgr.getSValBuilder()), B(std::move(b)) {}
898
899 RegionBindingsRef getRegionBindings() const { return B; }
900
901 bool isVisited(const MemRegion *R) {
902 return Visited.count(getCluster(R));
903 }
904
905 void GenerateClusters() {
906 // Scan the entire set of bindings and record the region clusters.
907 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end();
908 RI != RE; ++RI){
909 const MemRegion *Base = RI.getKey();
910
911 const ClusterBindings &Cluster = RI.getData();
912 assert(!Cluster.isEmpty() && "Empty clusters should be removed");
913 static_cast<DERIVED*>(this)->VisitAddedToCluster(Base, Cluster);
914
915 // If the base's memspace should be entirely invalidated, add the cluster
916 // to the workspace up front.
917 if (static_cast<DERIVED*>(this)->includeEntireMemorySpace(Base))
918 AddToWorkList(WorkListElement(Base), &Cluster);
919 }
920 }
921
922 bool AddToWorkList(WorkListElement E, const ClusterBindings *C) {
923 if (C && !Visited.insert(C).second)
924 return false;
925 WL.push_back(E);
926 return true;
927 }
928
929 bool AddToWorkList(const MemRegion *R) {
930 return static_cast<DERIVED*>(this)->AddToWorkList(R);
931 }
932
933 void RunWorkList() {
934 while (!WL.empty()) {
935 WorkListElement E = WL.pop_back_val();
936 const MemRegion *BaseR = E;
937
938 static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR));
939 }
940 }
941
942 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}
943 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {}
944
945 void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C,
946 bool Flag) {
947 static_cast<DERIVED*>(this)->VisitCluster(BaseR, C);
948 }
949};
950}
951
952//===----------------------------------------------------------------------===//
953// Binding invalidation.
954//===----------------------------------------------------------------------===//
955
956bool RegionStoreManager::scanReachableSymbols(Store S, const MemRegion *R,
957 ScanReachableSymbols &Callbacks) {
958 assert(R == R->getBaseRegion() && "Should only be called for base regions");
959 RegionBindingsRef B = getRegionBindings(S);
960 const ClusterBindings *Cluster = B.lookup(R);
961
962 if (!Cluster)
963 return true;
964
965 for (ClusterBindings::iterator RI = Cluster->begin(), RE = Cluster->end();
966 RI != RE; ++RI) {
967 if (!Callbacks.scan(RI.getData()))
968 return false;
969 }
970
971 return true;
972}
973
974static inline bool isUnionField(const FieldRegion *FR) {
975 return FR->getDecl()->getParent()->isUnion();
976}
977
979
980static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields) {
981 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");
982
983 const MemRegion *Base = K.getConcreteOffsetRegion();
984 const MemRegion *R = K.getRegion();
985
986 while (R != Base) {
987 if (const FieldRegion *FR = dyn_cast<FieldRegion>(R))
988 if (!isUnionField(FR))
989 Fields.push_back(FR->getDecl());
990
991 R = cast<SubRegion>(R)->getSuperRegion();
992 }
993}
994
995static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields) {
996 assert(K.hasSymbolicOffset() && "Not implemented for concrete offset keys");
997
998 if (Fields.empty())
999 return true;
1000
1001 FieldVector FieldsInBindingKey;
1002 getSymbolicOffsetFields(K, FieldsInBindingKey);
1003
1004 ptrdiff_t Delta = FieldsInBindingKey.size() - Fields.size();
1005 if (Delta >= 0)
1006 return std::equal(FieldsInBindingKey.begin() + Delta,
1007 FieldsInBindingKey.end(),
1008 Fields.begin());
1009 else
1010 return std::equal(FieldsInBindingKey.begin(), FieldsInBindingKey.end(),
1011 Fields.begin() - Delta);
1012}
1013
1014/// Collects all bindings in \p Cluster that may refer to bindings within
1015/// \p Top.
1016///
1017/// Each binding is a pair whose \c first is the key (a BindingKey) and whose
1018/// \c second is the value (an SVal).
1019///
1020/// The \p IncludeAllDefaultBindings parameter specifies whether to include
1021/// default bindings that may extend beyond \p Top itself, e.g. if \p Top is
1022/// an aggregate within a larger aggregate with a default binding.
1023static void
1025 SValBuilder &SVB, const ClusterBindings &Cluster,
1026 const SubRegion *Top, BindingKey TopKey,
1027 bool IncludeAllDefaultBindings) {
1028 FieldVector FieldsInSymbolicSubregions;
1029 if (TopKey.hasSymbolicOffset()) {
1030 getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions);
1031 Top = TopKey.getConcreteOffsetRegion();
1032 TopKey = BindingKey::Make(Top, BindingKey::Default);
1033 }
1034
1035 // Find the length (in bits) of the region being invalidated.
1036 uint64_t Length = UINT64_MAX;
1037 SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB);
1038 if (std::optional<nonloc::ConcreteInt> ExtentCI =
1039 Extent.getAs<nonloc::ConcreteInt>()) {
1040 const llvm::APSInt &ExtentInt = ExtentCI->getValue();
1041 assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());
1042 // Extents are in bytes but region offsets are in bits. Be careful!
1043 Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth();
1044 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) {
1045 if (FR->getDecl()->isBitField())
1046 Length = FR->getDecl()->getBitWidthValue();
1047 }
1048
1049 for (const auto &StoreEntry : Cluster) {
1050 BindingKey NextKey = StoreEntry.first;
1051 if (NextKey.getRegion() == TopKey.getRegion()) {
1052 // FIXME: This doesn't catch the case where we're really invalidating a
1053 // region with a symbolic offset. Example:
1054 // R: points[i].y
1055 // Next: points[0].x
1056
1057 if (NextKey.getOffset() > TopKey.getOffset() &&
1058 NextKey.getOffset() - TopKey.getOffset() < Length) {
1059 // Case 1: The next binding is inside the region we're invalidating.
1060 // Include it.
1061 Bindings.push_back(StoreEntry);
1062
1063 } else if (NextKey.getOffset() == TopKey.getOffset()) {
1064 // Case 2: The next binding is at the same offset as the region we're
1065 // invalidating. In this case, we need to leave default bindings alone,
1066 // since they may be providing a default value for a regions beyond what
1067 // we're invalidating.
1068 // FIXME: This is probably incorrect; consider invalidating an outer
1069 // struct whose first field is bound to a LazyCompoundVal.
1070 if (IncludeAllDefaultBindings || NextKey.isDirect())
1071 Bindings.push_back(StoreEntry);
1072 }
1073
1074 } else if (NextKey.hasSymbolicOffset()) {
1075 const MemRegion *Base = NextKey.getConcreteOffsetRegion();
1076 if (Top->isSubRegionOf(Base) && Top != Base) {
1077 // Case 3: The next key is symbolic and we just changed something within
1078 // its concrete region. We don't know if the binding is still valid, so
1079 // we'll be conservative and include it.
1080 if (IncludeAllDefaultBindings || NextKey.isDirect())
1081 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
1082 Bindings.push_back(StoreEntry);
1083 } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
1084 // Case 4: The next key is symbolic, but we changed a known
1085 // super-region. In this case the binding is certainly included.
1086 if (BaseSR->isSubRegionOf(Top))
1087 if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
1088 Bindings.push_back(StoreEntry);
1089 }
1090 }
1091 }
1092}
1093
1094static void
1096 SValBuilder &SVB, const ClusterBindings &Cluster,
1097 const SubRegion *Top, bool IncludeAllDefaultBindings) {
1098 collectSubRegionBindings(Bindings, SVB, Cluster, Top,
1099 BindingKey::Make(Top, BindingKey::Default),
1100 IncludeAllDefaultBindings);
1101}
1102
1103LimitedRegionBindingsRef
1104RegionStoreManager::removeSubRegionBindings(LimitedRegionBindingsConstRef B,
1105 const SubRegion *Top) {
1106 BindingKey TopKey = BindingKey::Make(Top, BindingKey::Default);
1107 const MemRegion *ClusterHead = TopKey.getBaseRegion();
1108
1109 if (Top == ClusterHead) {
1110 // We can remove an entire cluster's bindings all in one go.
1111 return B.removeCluster(Top);
1112 }
1113
1114 const ClusterBindings *Cluster = B.lookup(ClusterHead);
1115 if (!Cluster) {
1116 // If we're invalidating a region with a symbolic offset, we need to make
1117 // sure we don't treat the base region as uninitialized anymore.
1118 if (TopKey.hasSymbolicOffset()) {
1119 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
1120 return B.addBinding(Concrete, BindingKey::Default, UnknownVal());
1121 }
1122 return B;
1123 }
1124
1125 SmallVector<BindingPair, 32> Bindings;
1126 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, Top, TopKey,
1127 /*IncludeAllDefaultBindings=*/false);
1128
1129 ClusterBindingsRef Result(*Cluster, CBFactory);
1130 for (BindingKey Key : llvm::make_first_range(Bindings))
1131 Result = Result.remove(Key);
1132
1133 // If we're invalidating a region with a symbolic offset, we need to make sure
1134 // we don't treat the base region as uninitialized anymore.
1135 // FIXME: This isn't very precise; see the example in
1136 // collectSubRegionBindings.
1137 if (TopKey.hasSymbolicOffset()) {
1138 const SubRegion *Concrete = TopKey.getConcreteOffsetRegion();
1139 Result = Result.add(BindingKey::Make(Concrete, BindingKey::Default),
1140 UnknownVal());
1141 }
1142
1143 if (Result.isEmpty())
1144 return B.removeCluster(ClusterHead);
1145 return B.addWithoutDecreasingLimit(ClusterHead, Result.asImmutableMap());
1146}
1147
1148namespace {
1149class InvalidateRegionsWorker : public ClusterAnalysis<InvalidateRegionsWorker>
1150{
1151 ConstCFGElementRef Elem;
1152 unsigned Count;
1153 const LocationContext *LCtx;
1155 RegionAndSymbolInvalidationTraits &ITraits;
1157 GlobalsFilterKind GlobalsFilter;
1158public:
1159 InvalidateRegionsWorker(RegionStoreManager &rm, ProgramStateManager &stateMgr,
1160 RegionBindingsRef b, ConstCFGElementRef elem,
1161 unsigned count, const LocationContext *lctx,
1163 RegionAndSymbolInvalidationTraits &ITraitsIn,
1165 GlobalsFilterKind GFK)
1166 : ClusterAnalysis<InvalidateRegionsWorker>(rm, stateMgr, b), Elem(elem),
1167 Count(count), LCtx(lctx), IS(is), ITraits(ITraitsIn), Regions(r),
1168 GlobalsFilter(GFK) {}
1169
1170 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);
1171 void VisitBinding(SVal V);
1172
1173 using ClusterAnalysis::AddToWorkList;
1174
1175 bool AddToWorkList(const MemRegion *R);
1176
1177 /// Returns true if all clusters in the memory space for \p Base should be
1178 /// be invalidated.
1179 bool includeEntireMemorySpace(const MemRegion *Base);
1180
1181 /// Returns true if the memory space of the given region is one of the global
1182 /// regions specially included at the start of invalidation.
1183 bool isInitiallyIncludedGlobalRegion(const MemRegion *R);
1184};
1185}
1186
1187bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {
1188 bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1190 const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();
1191 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
1192}
1193
1194void InvalidateRegionsWorker::VisitBinding(SVal V) {
1195 // A symbol? Mark it touched by the invalidation.
1196 if (SymbolRef Sym = V.getAsSymbol())
1197 IS.insert(Sym);
1198
1199 if (const MemRegion *R = V.getAsRegion()) {
1200 AddToWorkList(R);
1201 return;
1202 }
1203
1204 // Is it a LazyCompoundVal? All references get invalidated as well.
1205 if (std::optional<nonloc::LazyCompoundVal> LCS =
1206 V.getAs<nonloc::LazyCompoundVal>()) {
1207
1208 // `getInterestingValues()` returns SVals contained within LazyCompoundVals,
1209 // so there is no need to visit them.
1210 for (SVal V : RM.getInterestingValues(*LCS))
1212 VisitBinding(V);
1213
1214 return;
1215 }
1216}
1217
1218void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
1219 const ClusterBindings *C) {
1220
1221 bool PreserveRegionsContents =
1222 ITraits.hasTrait(baseR,
1224
1225 if (C) {
1226 for (SVal Val : llvm::make_second_range(*C))
1227 VisitBinding(Val);
1228
1229 // Invalidate regions contents.
1230 if (!PreserveRegionsContents)
1231 B = B.removeCluster(baseR);
1232 }
1233
1234 if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) {
1235 if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {
1236
1237 // Lambdas can affect all static local variables without explicitly
1238 // capturing those.
1239 // We invalidate all static locals referenced inside the lambda body.
1240 if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {
1241 using namespace ast_matchers;
1242
1243 const char *DeclBind = "DeclBind";
1245 to(varDecl(hasStaticStorageDuration()).bind(DeclBind)))));
1246 auto Matches =
1247 match(RefToStatic, *RD->getLambdaCallOperator()->getBody(),
1248 RD->getASTContext());
1249
1250 for (BoundNodes &Match : Matches) {
1251 auto *VD = Match.getNodeAs<VarDecl>(DeclBind);
1252 const VarRegion *ToInvalidate =
1253 RM.getRegionManager().getVarRegion(VD, LCtx);
1254 AddToWorkList(ToInvalidate);
1255 }
1256 }
1257 }
1258 }
1259
1260 // BlockDataRegion? If so, invalidate captured variables that are passed
1261 // by reference.
1262 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(baseR)) {
1263 for (auto Var : BR->referenced_vars()) {
1264 const VarRegion *VR = Var.getCapturedRegion();
1265 const VarDecl *VD = VR->getDecl();
1266 if (VD->hasAttr<BlocksAttr>() || !VD->hasLocalStorage()) {
1267 AddToWorkList(VR);
1268 }
1269 else if (Loc::isLocType(VR->getValueType())) {
1270 // Map the current bindings to a Store to retrieve the value
1271 // of the binding. If that binding itself is a region, we should
1272 // invalidate that region. This is because a block may capture
1273 // a pointer value, but the thing pointed by that pointer may
1274 // get invalidated.
1275 SVal V = RM.getBinding(B, loc::MemRegionVal(VR));
1276 if (std::optional<Loc> L = V.getAs<Loc>()) {
1277 if (const MemRegion *LR = L->getAsRegion())
1278 AddToWorkList(LR);
1279 }
1280 }
1281 }
1282 return;
1283 }
1284
1285 // Symbolic region?
1286 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR))
1287 IS.insert(SR->getSymbol());
1288
1289 // Nothing else should be done in the case when we preserve regions context.
1290 if (PreserveRegionsContents)
1291 return;
1292
1293 // Otherwise, we have a normal data region. Record that we touched the region.
1294 if (Regions)
1295 Regions->push_back(baseR);
1296
1298 // Invalidate the region by setting its default value to
1299 // conjured symbol. The type of the symbol is irrelevant.
1300 DefinedOrUnknownSVal V =
1301 svalBuilder.conjureSymbolVal(baseR, Elem, LCtx, Ctx.IntTy, Count);
1302 B = B.addBinding(baseR, BindingKey::Default, V);
1303 return;
1304 }
1305
1306 if (!baseR->isBoundable())
1307 return;
1308
1309 const TypedValueRegion *TR = cast<TypedValueRegion>(baseR);
1310 QualType T = TR->getValueType();
1311
1312 if (isInitiallyIncludedGlobalRegion(baseR)) {
1313 // If the region is a global and we are invalidating all globals,
1314 // erasing the entry is good enough. This causes all globals to be lazily
1315 // symbolicated from the same base symbol.
1316 return;
1317 }
1318
1319 if (T->isRecordType()) {
1320 // Invalidate the region by setting its default value to
1321 // conjured symbol. The type of the symbol is irrelevant.
1322 DefinedOrUnknownSVal V =
1323 svalBuilder.conjureSymbolVal(baseR, Elem, LCtx, Ctx.IntTy, Count);
1324 B = B.addBinding(baseR, BindingKey::Default, V);
1325 return;
1326 }
1327
1328 if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
1329 bool doNotInvalidateSuperRegion = ITraits.hasTrait(
1330 baseR,
1332
1333 if (doNotInvalidateSuperRegion) {
1334 // We are not doing blank invalidation of the whole array region so we
1335 // have to manually invalidate each elements.
1336 std::optional<uint64_t> NumElements;
1337
1338 // Compute lower and upper offsets for region within array.
1339 if (const ConstantArrayType *CAT = dyn_cast<ConstantArrayType>(AT))
1340 NumElements = CAT->getZExtSize();
1341 if (!NumElements) // We are not dealing with a constant size array
1342 goto conjure_default;
1343 QualType ElementTy = AT->getElementType();
1344 uint64_t ElemSize = Ctx.getTypeSize(ElementTy);
1345 const RegionOffset &RO = baseR->getAsOffset();
1346 const MemRegion *SuperR = baseR->getBaseRegion();
1347 if (RO.hasSymbolicOffset()) {
1348 // If base region has a symbolic offset,
1349 // we revert to invalidating the super region.
1350 if (SuperR)
1351 AddToWorkList(SuperR);
1352 goto conjure_default;
1353 }
1354
1355 uint64_t LowerOffset = RO.getOffset();
1356 uint64_t UpperOffset = LowerOffset + *NumElements * ElemSize;
1357 bool UpperOverflow = UpperOffset < LowerOffset;
1358
1359 // Invalidate regions which are within array boundaries,
1360 // or have a symbolic offset.
1361 if (!SuperR)
1362 goto conjure_default;
1363
1364 const ClusterBindings *C = B.lookup(SuperR);
1365 if (!C)
1366 goto conjure_default;
1367
1368 for (const auto &[BK, V] : *C) {
1369 std::optional<uint64_t> ROffset =
1370 BK.hasSymbolicOffset() ? std::optional<uint64_t>() : BK.getOffset();
1371
1372 // Check offset is not symbolic and within array's boundaries.
1373 // Handles arrays of 0 elements and of 0-sized elements as well.
1374 if (!ROffset ||
1375 ((*ROffset >= LowerOffset && *ROffset < UpperOffset) ||
1376 (UpperOverflow &&
1377 (*ROffset >= LowerOffset || *ROffset < UpperOffset)) ||
1378 (LowerOffset == UpperOffset && *ROffset == LowerOffset))) {
1379 B = B.removeBinding(BK);
1380 // Bound symbolic regions need to be invalidated for dead symbol
1381 // detection.
1382 const MemRegion *R = V.getAsRegion();
1383 if (isa_and_nonnull<SymbolicRegion>(R))
1384 VisitBinding(V);
1385 }
1386 }
1387 }
1388 conjure_default:
1389 // Set the default value of the array to conjured symbol.
1390 DefinedOrUnknownSVal V = svalBuilder.conjureSymbolVal(
1391 baseR, Elem, LCtx, AT->getElementType(), Count);
1392 B = B.addBinding(baseR, BindingKey::Default, V);
1393 return;
1394 }
1395
1396 DefinedOrUnknownSVal V =
1397 svalBuilder.conjureSymbolVal(baseR, Elem, LCtx, T, Count);
1398 assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
1399 B = B.addBinding(baseR, BindingKey::Direct, V);
1400}
1401
1402bool InvalidateRegionsWorker::isInitiallyIncludedGlobalRegion(
1403 const MemRegion *R) {
1404 switch (GlobalsFilter) {
1405 case GFK_None:
1406 return false;
1407 case GFK_SystemOnly:
1409 case GFK_All:
1411 }
1412
1413 llvm_unreachable("unknown globals filter");
1414}
1415
1416bool InvalidateRegionsWorker::includeEntireMemorySpace(const MemRegion *Base) {
1417 if (isInitiallyIncludedGlobalRegion(Base))
1418 return true;
1419
1420 const MemSpaceRegion *MemSpace = Base->getRawMemorySpace();
1421 return ITraits.hasTrait(MemSpace,
1423}
1424
1425RegionBindingsRef RegionStoreManager::invalidateGlobalRegion(
1426 MemRegion::Kind K, ConstCFGElementRef Elem, unsigned Count,
1427 const LocationContext *LCtx, RegionBindingsRef B,
1428 InvalidatedRegions *Invalidated) {
1429 // Bind the globals memory space to a new symbol that we will use to derive
1430 // the bindings for all globals.
1431 const GlobalsSpaceRegion *GS = MRMgr.getGlobalsRegion(K);
1432 SVal V = svalBuilder.conjureSymbolVal(
1433 /* symbolTag = */ (const void *)GS, Elem, LCtx,
1434 /* type does not matter */ Ctx.IntTy, Count);
1435
1436 B = B.removeBinding(GS)
1437 .addBinding(BindingKey::Make(GS, BindingKey::Default), V);
1438
1439 // Even if there are no bindings in the global scope, we still need to
1440 // record that we touched it.
1441 if (Invalidated)
1442 Invalidated->push_back(GS);
1443
1444 return B;
1445}
1446
1447void RegionStoreManager::populateWorkList(InvalidateRegionsWorker &W,
1448 ArrayRef<SVal> Values,
1449 InvalidatedRegions *TopLevelRegions) {
1450 for (SVal V : Values) {
1451 if (auto LCS = V.getAs<nonloc::LazyCompoundVal>()) {
1452 for (SVal S : getInterestingValues(*LCS))
1453 if (const MemRegion *R = S.getAsRegion())
1454 W.AddToWorkList(R);
1455
1456 continue;
1457 }
1458
1459 if (const MemRegion *R = V.getAsRegion()) {
1460 if (TopLevelRegions)
1461 TopLevelRegions->push_back(R);
1462 W.AddToWorkList(R);
1463 continue;
1464 }
1465 }
1466}
1467
1468StoreRef RegionStoreManager::invalidateRegions(
1469 Store store, ArrayRef<SVal> Values, ConstCFGElementRef Elem, unsigned Count,
1470 const LocationContext *LCtx, const CallEvent *Call, InvalidatedSymbols &IS,
1471 RegionAndSymbolInvalidationTraits &ITraits,
1472 InvalidatedRegions *TopLevelRegions, InvalidatedRegions *Invalidated) {
1473 GlobalsFilterKind GlobalsFilter;
1474 if (Call) {
1475 if (Call->isInSystemHeader())
1476 GlobalsFilter = GFK_SystemOnly;
1477 else
1478 GlobalsFilter = GFK_All;
1479 } else {
1480 GlobalsFilter = GFK_None;
1481 }
1482
1483 RegionBindingsRef B = getRegionBindings(store);
1484 InvalidateRegionsWorker W(*this, StateMgr, B, Elem, Count, LCtx, IS, ITraits,
1485 Invalidated, GlobalsFilter);
1486
1487 // Scan the bindings and generate the clusters.
1488 W.GenerateClusters();
1489
1490 // Add the regions to the worklist.
1491 populateWorkList(W, Values, TopLevelRegions);
1492
1493 W.RunWorkList();
1494
1495 // Return the new bindings.
1496 B = W.getRegionBindings();
1497
1498 // For calls, determine which global regions should be invalidated and
1499 // invalidate them. (Note that function-static and immutable globals are never
1500 // invalidated by this.)
1501 // TODO: This could possibly be more precise with modules.
1502 switch (GlobalsFilter) {
1503 case GFK_All:
1504 B = invalidateGlobalRegion(MemRegion::GlobalInternalSpaceRegionKind, Elem,
1505 Count, LCtx, B, Invalidated);
1506 [[fallthrough]];
1507 case GFK_SystemOnly:
1508 B = invalidateGlobalRegion(MemRegion::GlobalSystemSpaceRegionKind, Elem,
1509 Count, LCtx, B, Invalidated);
1510 [[fallthrough]];
1511 case GFK_None:
1512 break;
1513 }
1514
1515 return StoreRef(B.asStore(), *this);
1516}
1517
1518//===----------------------------------------------------------------------===//
1519// Location and region casting.
1520//===----------------------------------------------------------------------===//
1521
1522/// ArrayToPointer - Emulates the "decay" of an array to a pointer
1523/// type. 'Array' represents the lvalue of the array being decayed
1524/// to a pointer, and the returned SVal represents the decayed
1525/// version of that lvalue (i.e., a pointer to the first element of
1526/// the array). This is called by ExprEngine when evaluating casts
1527/// from arrays to pointers.
1528SVal RegionStoreManager::ArrayToPointer(Loc Array, QualType T) {
1529 if (isa<loc::ConcreteInt>(Array))
1530 return Array;
1531
1532 if (!isa<loc::MemRegionVal>(Array))
1533 return UnknownVal();
1534
1535 const SubRegion *R =
1536 cast<SubRegion>(Array.castAs<loc::MemRegionVal>().getRegion());
1537 NonLoc ZeroIdx = svalBuilder.makeZeroArrayIndex();
1538 return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, R, Ctx));
1539}
1540
1541//===----------------------------------------------------------------------===//
1542// Loading values from regions.
1543//===----------------------------------------------------------------------===//
1544
1545SVal RegionStoreManager::getBinding(RegionBindingsConstRef B, Loc L, QualType T) {
1546 assert(!isa<UnknownVal>(L) && "location unknown");
1547 assert(!isa<UndefinedVal>(L) && "location undefined");
1548
1549 // For access to concrete addresses, return UnknownVal. Checks
1550 // for null dereferences (and similar errors) are done by checkers, not
1551 // the Store.
1552 // FIXME: We can consider lazily symbolicating such memory, but we really
1553 // should defer this when we can reason easily about symbolicating arrays
1554 // of bytes.
1555 if (L.getAs<loc::ConcreteInt>()) {
1556 return UnknownVal();
1557 }
1558 if (!L.getAs<loc::MemRegionVal>()) {
1559 return UnknownVal();
1560 }
1561
1562 const MemRegion *MR = L.castAs<loc::MemRegionVal>().getRegion();
1563
1564 if (isa<BlockDataRegion>(MR)) {
1565 return UnknownVal();
1566 }
1567
1568 // Auto-detect the binding type.
1569 if (T.isNull()) {
1570 if (const auto *TVR = dyn_cast<TypedValueRegion>(MR))
1571 T = TVR->getValueType();
1572 else if (const auto *TR = dyn_cast<TypedRegion>(MR))
1573 T = TR->getLocationType()->getPointeeType();
1574 else if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
1575 T = SR->getPointeeStaticType();
1576 }
1577 assert(!T.isNull() && "Unable to auto-detect binding type!");
1578 assert(!T->isVoidType() && "Attempting to dereference a void pointer!");
1579
1580 if (!isa<TypedValueRegion>(MR))
1581 MR = GetElementZeroRegion(cast<SubRegion>(MR), T);
1582
1583 // FIXME: Perhaps this method should just take a 'const MemRegion*' argument
1584 // instead of 'Loc', and have the other Loc cases handled at a higher level.
1585 const TypedValueRegion *R = cast<TypedValueRegion>(MR);
1586 QualType RTy = R->getValueType();
1587
1588 // FIXME: we do not yet model the parts of a complex type, so treat the
1589 // whole thing as "unknown".
1590 if (RTy->isAnyComplexType())
1591 return UnknownVal();
1592
1593 // FIXME: We should eventually handle funny addressing. e.g.:
1594 //
1595 // int x = ...;
1596 // int *p = &x;
1597 // char *q = (char*) p;
1598 // char c = *q; // returns the first byte of 'x'.
1599 //
1600 // Such funny addressing will occur due to layering of regions.
1601 if (RTy->isStructureOrClassType())
1602 return getBindingForStruct(B, R);
1603
1604 // FIXME: Handle unions.
1605 if (RTy->isUnionType())
1606 return createLazyBinding(B, R);
1607
1608 if (RTy->isArrayType()) {
1609 if (RTy->isConstantArrayType())
1610 return getBindingForArray(B, R);
1611 else
1612 return UnknownVal();
1613 }
1614
1615 // FIXME: handle Vector types.
1616 if (RTy->isVectorType())
1617 return UnknownVal();
1618
1619 if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
1620 return svalBuilder.evalCast(getBindingForField(B, FR), T, QualType{});
1621
1622 if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
1623 // FIXME: Here we actually perform an implicit conversion from the loaded
1624 // value to the element type. Eventually we want to compose these values
1625 // more intelligently. For example, an 'element' can encompass multiple
1626 // bound regions (e.g., several bound bytes), or could be a subset of
1627 // a larger value.
1628 return svalBuilder.evalCast(getBindingForElement(B, ER), T, QualType{});
1629 }
1630
1631 if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
1632 // FIXME: Here we actually perform an implicit conversion from the loaded
1633 // value to the ivar type. What we should model is stores to ivars
1634 // that blow past the extent of the ivar. If the address of the ivar is
1635 // reinterpretted, it is possible we stored a different value that could
1636 // fit within the ivar. Either we need to cast these when storing them
1637 // or reinterpret them lazily (as we do here).
1638 return svalBuilder.evalCast(getBindingForObjCIvar(B, IVR), T, QualType{});
1639 }
1640
1641 if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
1642 // FIXME: Here we actually perform an implicit conversion from the loaded
1643 // value to the variable type. What we should model is stores to variables
1644 // that blow past the extent of the variable. If the address of the
1645 // variable is reinterpretted, it is possible we stored a different value
1646 // that could fit within the variable. Either we need to cast these when
1647 // storing them or reinterpret them lazily (as we do here).
1648 return svalBuilder.evalCast(getBindingForVar(B, VR), T, QualType{});
1649 }
1650
1651 const SVal *V = B.lookup(R, BindingKey::Direct);
1652
1653 // Check if the region has a binding.
1654 if (V)
1655 return *V;
1656
1657 // The location does not have a bound value. This means that it has
1658 // the value it had upon its creation and/or entry to the analyzed
1659 // function/method. These are either symbolic values or 'undefined'.
1661 // All stack variables are considered to have undefined values
1662 // upon creation. All heap allocated blocks are considered to
1663 // have undefined values as well unless they are explicitly bound
1664 // to specific values.
1665 return UndefinedVal();
1666 }
1667
1668 // All other values are symbolic.
1669 return svalBuilder.getRegionValueSymbolVal(R);
1670}
1671
1673 QualType RegionTy;
1674 if (const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(R))
1675 RegionTy = TVR->getValueType();
1676
1677 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
1678 RegionTy = SR->getSymbol()->getType();
1679
1680 return RegionTy;
1681}
1682
1683/// Checks to see if store \p B has a lazy binding for region \p R.
1684///
1685/// If \p AllowSubregionBindings is \c false, a lazy binding will be rejected
1686/// if there are additional bindings within \p R.
1687///
1688/// Note that unlike RegionStoreManager::findLazyBinding, this will not search
1689/// for lazy bindings for super-regions of \p R.
1690static std::optional<nonloc::LazyCompoundVal>
1692 const SubRegion *R, bool AllowSubregionBindings) {
1693 std::optional<SVal> V = B.getDefaultBinding(R);
1694 if (!V)
1695 return std::nullopt;
1696
1697 std::optional<nonloc::LazyCompoundVal> LCV =
1698 V->getAs<nonloc::LazyCompoundVal>();
1699 if (!LCV)
1700 return std::nullopt;
1701
1702 // If the LCV is for a subregion, the types might not match, and we shouldn't
1703 // reuse the binding.
1704 QualType RegionTy = getUnderlyingType(R);
1705 if (!RegionTy.isNull() &&
1706 !RegionTy->isVoidPointerType()) {
1707 QualType SourceRegionTy = LCV->getRegion()->getValueType();
1708 if (!SVB.getContext().hasSameUnqualifiedType(RegionTy, SourceRegionTy))
1709 return std::nullopt;
1710 }
1711
1712 if (!AllowSubregionBindings) {
1713 // If there are any other bindings within this region, we shouldn't reuse
1714 // the top-level binding.
1716 collectSubRegionBindings(Bindings, SVB, *B.lookup(R->getBaseRegion()), R,
1717 /*IncludeAllDefaultBindings=*/true);
1718 if (Bindings.size() > 1)
1719 return std::nullopt;
1720 }
1721
1722 return *LCV;
1723}
1724
1725std::pair<Store, const SubRegion *>
1726RegionStoreManager::findLazyBinding(RegionBindingsConstRef B,
1727 const SubRegion *R,
1728 const SubRegion *originalRegion) {
1729 if (originalRegion != R) {
1730 if (std::optional<nonloc::LazyCompoundVal> V =
1731 getExistingLazyBinding(svalBuilder, B, R, true))
1732 return std::make_pair(V->getStore(), V->getRegion());
1733 }
1734
1735 typedef std::pair<Store, const SubRegion *> StoreRegionPair;
1736 StoreRegionPair Result = StoreRegionPair();
1737
1738 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
1739 Result = findLazyBinding(B, cast<SubRegion>(ER->getSuperRegion()),
1740 originalRegion);
1741
1742 if (Result.second)
1743 Result.second = MRMgr.getElementRegionWithSuper(ER, Result.second);
1744
1745 } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(R)) {
1746 Result = findLazyBinding(B, cast<SubRegion>(FR->getSuperRegion()),
1747 originalRegion);
1748
1749 if (Result.second)
1750 Result.second = MRMgr.getFieldRegionWithSuper(FR, Result.second);
1751
1752 } else if (const CXXBaseObjectRegion *BaseReg =
1753 dyn_cast<CXXBaseObjectRegion>(R)) {
1754 // C++ base object region is another kind of region that we should blast
1755 // through to look for lazy compound value. It is like a field region.
1756 Result = findLazyBinding(B, cast<SubRegion>(BaseReg->getSuperRegion()),
1757 originalRegion);
1758
1759 if (Result.second)
1760 Result.second = MRMgr.getCXXBaseObjectRegionWithSuper(BaseReg,
1761 Result.second);
1762 }
1763
1764 return Result;
1765}
1766
1767/// This is a helper function for `getConstantValFromConstArrayInitializer`.
1768///
1769/// Return an array of extents of the declared array type.
1770///
1771/// E.g. for `int x[1][2][3];` returns { 1, 2, 3 }.
1772static SmallVector<uint64_t, 2>
1774 assert(CAT && "ConstantArrayType should not be null");
1777 do {
1778 Extents.push_back(CAT->getZExtSize());
1779 } while ((CAT = dyn_cast<ConstantArrayType>(CAT->getElementType())));
1780 return Extents;
1781}
1782
1783/// This is a helper function for `getConstantValFromConstArrayInitializer`.
1784///
1785/// Return an array of offsets from nested ElementRegions and a root base
1786/// region. The array is never empty and a base region is never null.
1787///
1788/// E.g. for `Element{Element{Element{VarRegion},1},2},3}` returns { 3, 2, 1 }.
1789/// This represents an access through indirection: `arr[1][2][3];`
1790///
1791/// \param ER The given (possibly nested) ElementRegion.
1792///
1793/// \note The result array is in the reverse order of indirection expression:
1794/// arr[1][2][3] -> { 3, 2, 1 }. This helps to provide complexity O(n), where n
1795/// is a number of indirections. It may not affect performance in real-life
1796/// code, though.
1797static std::pair<SmallVector<SVal, 2>, const MemRegion *>
1799 assert(ER && "ConstantArrayType should not be null");
1800 const MemRegion *Base;
1801 SmallVector<SVal, 2> SValOffsets;
1802 do {
1803 SValOffsets.push_back(ER->getIndex());
1804 Base = ER->getSuperRegion();
1805 ER = dyn_cast<ElementRegion>(Base);
1806 } while (ER);
1807 return {SValOffsets, Base};
1808}
1809
1810/// This is a helper function for `getConstantValFromConstArrayInitializer`.
1811///
1812/// Convert array of offsets from `SVal` to `uint64_t` in consideration of
1813/// respective array extents.
1814/// \param SrcOffsets [in] The array of offsets of type `SVal` in reversed
1815/// order (expectedly received from `getElementRegionOffsetsWithBase`).
1816/// \param ArrayExtents [in] The array of extents.
1817/// \param DstOffsets [out] The array of offsets of type `uint64_t`.
1818/// \returns:
1819/// - `std::nullopt` for successful convertion.
1820/// - `UndefinedVal` or `UnknownVal` otherwise. It's expected that this SVal
1821/// will be returned as a suitable value of the access operation.
1822/// which should be returned as a correct
1823///
1824/// \example:
1825/// const int arr[10][20][30] = {}; // ArrayExtents { 10, 20, 30 }
1826/// int x1 = arr[4][5][6]; // SrcOffsets { NonLoc(6), NonLoc(5), NonLoc(4) }
1827/// // DstOffsets { 4, 5, 6 }
1828/// // returns std::nullopt
1829/// int x2 = arr[42][5][-6]; // returns UndefinedVal
1830/// int x3 = arr[4][5][x2]; // returns UnknownVal
1831static std::optional<SVal>
1833 const SmallVector<uint64_t, 2> ArrayExtents,
1834 SmallVector<uint64_t, 2> &DstOffsets) {
1835 // Check offsets for being out of bounds.
1836 // C++20 [expr.add] 7.6.6.4 (excerpt):
1837 // If P points to an array element i of an array object x with n
1838 // elements, where i < 0 or i > n, the behavior is undefined.
1839 // Dereferencing is not allowed on the "one past the last
1840 // element", when i == n.
1841 // Example:
1842 // const int arr[3][2] = {{1, 2}, {3, 4}};
1843 // arr[0][0]; // 1
1844 // arr[0][1]; // 2
1845 // arr[0][2]; // UB
1846 // arr[1][0]; // 3
1847 // arr[1][1]; // 4
1848 // arr[1][-1]; // UB
1849 // arr[2][0]; // 0
1850 // arr[2][1]; // 0
1851 // arr[-2][0]; // UB
1852 DstOffsets.resize(SrcOffsets.size());
1853 auto ExtentIt = ArrayExtents.begin();
1854 auto OffsetIt = DstOffsets.begin();
1855 // Reverse `SValOffsets` to make it consistent with `ArrayExtents`.
1856 for (SVal V : llvm::reverse(SrcOffsets)) {
1857 if (auto CI = V.getAs<nonloc::ConcreteInt>()) {
1858 // When offset is out of array's bounds, result is UB.
1859 const llvm::APSInt &Offset = CI->getValue();
1860 if (Offset.isNegative() || Offset.uge(*(ExtentIt++)))
1861 return UndefinedVal();
1862 // Store index in a reversive order.
1863 *(OffsetIt++) = Offset.getZExtValue();
1864 continue;
1865 }
1866 // Symbolic index presented. Return Unknown value.
1867 // FIXME: We also need to take ElementRegions with symbolic indexes into
1868 // account.
1869 return UnknownVal();
1870 }
1871 return std::nullopt;
1872}
1873
1874std::optional<SVal> RegionStoreManager::getConstantValFromConstArrayInitializer(
1875 RegionBindingsConstRef B, const ElementRegion *R) {
1876 assert(R && "ElementRegion should not be null");
1877
1878 // Treat an n-dimensional array.
1879 SmallVector<SVal, 2> SValOffsets;
1880 const MemRegion *Base;
1881 std::tie(SValOffsets, Base) = getElementRegionOffsetsWithBase(R);
1882 const VarRegion *VR = dyn_cast<VarRegion>(Base);
1883 if (!VR)
1884 return std::nullopt;
1885
1886 assert(!SValOffsets.empty() && "getElementRegionOffsets guarantees the "
1887 "offsets vector is not empty.");
1888
1889 // Check if the containing array has an initialized value that we can trust.
1890 // We can trust a const value or a value of a global initializer in main().
1891 const VarDecl *VD = VR->getDecl();
1892 if (!VD->getType().isConstQualified() &&
1894 (!B.isMainAnalysis() || !VD->hasGlobalStorage()))
1895 return std::nullopt;
1896
1897 // Array's declaration should have `ConstantArrayType` type, because only this
1898 // type contains an array extent. It may happen that array type can be of
1899 // `IncompleteArrayType` type. To get the declaration of `ConstantArrayType`
1900 // type, we should find the declaration in the redeclarations chain that has
1901 // the initialization expression.
1902 // NOTE: `getAnyInitializer` has an out-parameter, which returns a new `VD`
1903 // from which an initializer is obtained. We replace current `VD` with the new
1904 // `VD`. If the return value of the function is null than `VD` won't be
1905 // replaced.
1906 const Expr *Init = VD->getAnyInitializer(VD);
1907 // NOTE: If `Init` is non-null, then a new `VD` is non-null for sure. So check
1908 // `Init` for null only and don't worry about the replaced `VD`.
1909 if (!Init)
1910 return std::nullopt;
1911
1912 // Array's declaration should have ConstantArrayType type, because only this
1913 // type contains an array extent.
1914 const ConstantArrayType *CAT = Ctx.getAsConstantArrayType(VD->getType());
1915 if (!CAT)
1916 return std::nullopt;
1917
1918 // Get array extents.
1919 SmallVector<uint64_t, 2> Extents = getConstantArrayExtents(CAT);
1920
1921 // The number of offsets should equal to the numbers of extents,
1922 // otherwise wrong type punning occurred. For instance:
1923 // int arr[1][2][3];
1924 // auto ptr = (int(*)[42])arr;
1925 // auto x = ptr[4][2]; // UB
1926 // FIXME: Should return UndefinedVal.
1927 if (SValOffsets.size() != Extents.size())
1928 return std::nullopt;
1929
1930 SmallVector<uint64_t, 2> ConcreteOffsets;
1931 if (std::optional<SVal> V = convertOffsetsFromSvalToUnsigneds(
1932 SValOffsets, Extents, ConcreteOffsets))
1933 return *V;
1934
1935 // Handle InitListExpr.
1936 // Example:
1937 // const char arr[4][2] = { { 1, 2 }, { 3 }, 4, 5 };
1938 if (const auto *ILE = dyn_cast<InitListExpr>(Init))
1939 return getSValFromInitListExpr(ILE, ConcreteOffsets, R->getElementType());
1940
1941 // Handle StringLiteral.
1942 // Example:
1943 // const char arr[] = "abc";
1944 if (const auto *SL = dyn_cast<StringLiteral>(Init))
1945 return getSValFromStringLiteral(SL, ConcreteOffsets.front(),
1946 R->getElementType());
1947
1948 // FIXME: Handle CompoundLiteralExpr.
1949
1950 return std::nullopt;
1951}
1952
1953/// Returns an SVal, if possible, for the specified position of an
1954/// initialization list.
1955///
1956/// \param ILE The given initialization list.
1957/// \param Offsets The array of unsigned offsets. E.g. for the expression
1958/// `int x = arr[1][2][3];` an array should be { 1, 2, 3 }.
1959/// \param ElemT The type of the result SVal expression.
1960/// \return Optional SVal for the particular position in the initialization
1961/// list. E.g. for the list `{{1, 2},[3, 4],{5, 6}, {}}` offsets:
1962/// - {1, 1} returns SVal{4}, because it's the second position in the second
1963/// sublist;
1964/// - {3, 0} returns SVal{0}, because there's no explicit value at this
1965/// position in the sublist.
1966///
1967/// NOTE: Inorder to get a valid SVal, a caller shall guarantee valid offsets
1968/// for the given initialization list. Otherwise SVal can be an equivalent to 0
1969/// or lead to assertion.
1970std::optional<SVal> RegionStoreManager::getSValFromInitListExpr(
1971 const InitListExpr *ILE, const SmallVector<uint64_t, 2> &Offsets,
1972 QualType ElemT) {
1973 assert(ILE && "InitListExpr should not be null");
1974
1975 for (uint64_t Offset : Offsets) {
1976 // C++20 [dcl.init.string] 9.4.2.1:
1977 // An array of ordinary character type [...] can be initialized by [...]
1978 // an appropriately-typed string-literal enclosed in braces.
1979 // Example:
1980 // const char arr[] = { "abc" };
1981 if (ILE->isStringLiteralInit())
1982 if (const auto *SL = dyn_cast<StringLiteral>(ILE->getInit(0)))
1983 return getSValFromStringLiteral(SL, Offset, ElemT);
1984
1985 // C++20 [expr.add] 9.4.17.5 (excerpt):
1986 // i-th array element is value-initialized for each k < i ≤ n,
1987 // where k is an expression-list size and n is an array extent.
1988 if (Offset >= ILE->getNumInits())
1989 return svalBuilder.makeZeroVal(ElemT);
1990
1991 const Expr *E = ILE->getInit(Offset);
1992 const auto *IL = dyn_cast<InitListExpr>(E);
1993 if (!IL)
1994 // Return a constant value, if it is presented.
1995 // FIXME: Support other SVals.
1996 return svalBuilder.getConstantVal(E);
1997
1998 // Go to the nested initializer list.
1999 ILE = IL;
2000 }
2001
2002 assert(ILE);
2003
2004 // FIXME: Unhandeled InitListExpr sub-expression, possibly constructing an
2005 // enum?
2006 return std::nullopt;
2007}
2008
2009/// Returns an SVal, if possible, for the specified position in a string
2010/// literal.
2011///
2012/// \param SL The given string literal.
2013/// \param Offset The unsigned offset. E.g. for the expression
2014/// `char x = str[42];` an offset should be 42.
2015/// E.g. for the string "abc" offset:
2016/// - 1 returns SVal{b}, because it's the second position in the string.
2017/// - 42 returns SVal{0}, because there's no explicit value at this
2018/// position in the string.
2019/// \param ElemT The type of the result SVal expression.
2020///
2021/// NOTE: We return `0` for every offset >= the literal length for array
2022/// declarations, like:
2023/// const char str[42] = "123"; // Literal length is 4.
2024/// char c = str[41]; // Offset is 41.
2025/// FIXME: Nevertheless, we can't do the same for pointer declaraions, like:
2026/// const char * const str = "123"; // Literal length is 4.
2027/// char c = str[41]; // Offset is 41. Returns `0`, but Undef
2028/// // expected.
2029/// It should be properly handled before reaching this point.
2030/// The main problem is that we can't distinguish between these declarations,
2031/// because in case of array we can get the Decl from VarRegion, but in case
2032/// of pointer the region is a StringRegion, which doesn't contain a Decl.
2033/// Possible solution could be passing an array extent along with the offset.
2034SVal RegionStoreManager::getSValFromStringLiteral(const StringLiteral *SL,
2035 uint64_t Offset,
2036 QualType ElemT) {
2037 assert(SL && "StringLiteral should not be null");
2038 // C++20 [dcl.init.string] 9.4.2.3:
2039 // If there are fewer initializers than there are array elements, each
2040 // element not explicitly initialized shall be zero-initialized [dcl.init].
2041 uint32_t Code = (Offset >= SL->getLength()) ? 0 : SL->getCodeUnit(Offset);
2042 return svalBuilder.makeIntVal(Code, ElemT);
2043}
2044
2045static std::optional<SVal> getDerivedSymbolForBinding(
2046 RegionBindingsConstRef B, const TypedValueRegion *BaseRegion,
2047 const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB) {
2048 assert(BaseRegion);
2049 QualType BaseTy = BaseRegion->getValueType();
2050 QualType Ty = SubReg->getValueType();
2051 if (BaseTy->isScalarType() && Ty->isScalarType()) {
2052 if (Ctx.getTypeSizeInChars(BaseTy) >= Ctx.getTypeSizeInChars(Ty)) {
2053 if (const std::optional<SVal> &ParentValue =
2054 B.getDirectBinding(BaseRegion)) {
2055 if (SymbolRef ParentValueAsSym = ParentValue->getAsSymbol())
2056 return SVB.getDerivedRegionValueSymbolVal(ParentValueAsSym, SubReg);
2057
2058 if (ParentValue->isUndef())
2059 return UndefinedVal();
2060
2061 // Other cases: give up. We are indexing into a larger object
2062 // that has some value, but we don't know how to handle that yet.
2063 return UnknownVal();
2064 }
2065 }
2066 }
2067 return std::nullopt;
2068}
2069
2070SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
2071 const ElementRegion* R) {
2072 // Check if the region has a binding.
2073 if (const std::optional<SVal> &V = B.getDirectBinding(R))
2074 return *V;
2075
2076 const MemRegion* superR = R->getSuperRegion();
2077
2078 // Check if the region is an element region of a string literal.
2079 if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
2080 // FIXME: Handle loads from strings where the literal is treated as
2081 // an integer, e.g., *((unsigned int*)"hello"). Such loads are UB according
2082 // to C++20 7.2.1.11 [basic.lval].
2083 QualType T = Ctx.getAsArrayType(StrR->getValueType())->getElementType();
2084 if (!Ctx.hasSameUnqualifiedType(T, R->getElementType()))
2085 return UnknownVal();
2086 if (const auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
2087 const llvm::APSInt &Idx = CI->getValue();
2088 if (Idx < 0)
2089 return UndefinedVal();
2090 const StringLiteral *SL = StrR->getStringLiteral();
2091 return getSValFromStringLiteral(SL, Idx.getZExtValue(), T);
2092 }
2093 } else if (isa<ElementRegion, VarRegion>(superR)) {
2094 if (std::optional<SVal> V = getConstantValFromConstArrayInitializer(B, R))
2095 return *V;
2096 }
2097
2098 // Check for loads from a code text region. For such loads, just give up.
2099 if (isa<CodeTextRegion>(superR))
2100 return UnknownVal();
2101
2102 // Handle the case where we are indexing into a larger scalar object.
2103 // For example, this handles:
2104 // int x = ...
2105 // char *y = &x;
2106 // return *y;
2107 // FIXME: This is a hack, and doesn't do anything really intelligent yet.
2108 const RegionRawOffset &O = R->getAsArrayOffset();
2109
2110 // If we cannot reason about the offset, return an unknown value.
2111 if (!O.getRegion())
2112 return UnknownVal();
2113
2114 if (const TypedValueRegion *baseR = dyn_cast<TypedValueRegion>(O.getRegion()))
2115 if (auto V = getDerivedSymbolForBinding(B, baseR, R, Ctx, svalBuilder))
2116 return *V;
2117
2118 return getBindingForFieldOrElementCommon(B, R, R->getElementType());
2119}
2120
2121SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
2122 const FieldRegion* R) {
2123
2124 // Check if the region has a binding.
2125 if (const std::optional<SVal> &V = B.getDirectBinding(R))
2126 return *V;
2127
2128 // If the containing record was initialized, try to get its constant value.
2129 const FieldDecl *FD = R->getDecl();
2130 QualType Ty = FD->getType();
2131 const MemRegion* superR = R->getSuperRegion();
2132 if (const auto *VR = dyn_cast<VarRegion>(superR)) {
2133 const VarDecl *VD = VR->getDecl();
2134 QualType RecordVarTy = VD->getType();
2135 unsigned Index = FD->getFieldIndex();
2136 // Either the record variable or the field has an initializer that we can
2137 // trust. We trust initializers of constants and, additionally, respect
2138 // initializers of globals when analyzing main().
2139 if (RecordVarTy.isConstQualified() || Ty.isConstQualified() ||
2140 (B.isMainAnalysis() && VD->hasGlobalStorage()))
2141 if (const Expr *Init = VD->getAnyInitializer())
2142 if (const auto *InitList = dyn_cast<InitListExpr>(Init)) {
2143 if (Index < InitList->getNumInits()) {
2144 if (const Expr *FieldInit = InitList->getInit(Index))
2145 if (std::optional<SVal> V = svalBuilder.getConstantVal(FieldInit))
2146 return *V;
2147 } else {
2148 return svalBuilder.makeZeroVal(Ty);
2149 }
2150 }
2151 }
2152
2153 // Handle the case where we are accessing into a larger scalar object.
2154 // For example, this handles:
2155 // struct header {
2156 // unsigned a : 1;
2157 // unsigned b : 1;
2158 // };
2159 // struct parse_t {
2160 // unsigned bits0 : 1;
2161 // unsigned bits2 : 2; // <-- header
2162 // unsigned bits4 : 4;
2163 // };
2164 // int parse(parse_t *p) {
2165 // unsigned copy = p->bits2;
2166 // header *bits = (header *)&copy;
2167 // return bits->b; <-- here
2168 // }
2169 if (const auto *Base = dyn_cast<TypedValueRegion>(R->getBaseRegion()))
2170 if (auto V = getDerivedSymbolForBinding(B, Base, R, Ctx, svalBuilder))
2171 return *V;
2172
2173 return getBindingForFieldOrElementCommon(B, R, Ty);
2174}
2175
2176std::optional<SVal> RegionStoreManager::getBindingForDerivedDefaultValue(
2177 RegionBindingsConstRef B, const MemRegion *superR,
2178 const TypedValueRegion *R, QualType Ty) {
2179
2180 if (const std::optional<SVal> &D = B.getDefaultBinding(superR)) {
2181 SVal val = *D;
2182 if (SymbolRef parentSym = val.getAsSymbol())
2183 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
2184
2185 if (val.isZeroConstant())
2186 return svalBuilder.makeZeroVal(Ty);
2187
2188 if (val.isUnknownOrUndef())
2189 return val;
2190
2191 // Lazy bindings are usually handled through getExistingLazyBinding().
2192 // We should unify these two code paths at some point.
2194 return val;
2195
2196 llvm_unreachable("Unknown default value");
2197 }
2198
2199 return std::nullopt;
2200}
2201
2202SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
2203 RegionBindingsRef LazyBinding) {
2204 SVal Result;
2205 if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
2206 Result = getBindingForElement(LazyBinding, ER);
2207 else
2208 Result = getBindingForField(LazyBinding,
2209 cast<FieldRegion>(LazyBindingRegion));
2210
2211 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a
2212 // default value for /part/ of an aggregate from a default value for the
2213 // /entire/ aggregate. The most common case of this is when struct Outer
2214 // has as its first member a struct Inner, which is copied in from a stack
2215 // variable. In this case, even if the Outer's default value is symbolic, 0,
2216 // or unknown, it gets overridden by the Inner's default value of undefined.
2217 //
2218 // This is a general problem -- if the Inner is zero-initialized, the Outer
2219 // will now look zero-initialized. The proper way to solve this is with a
2220 // new version of RegionStore that tracks the extent of a binding as well
2221 // as the offset.
2222 //
2223 // This hack only takes care of the undefined case because that can very
2224 // quickly result in a warning.
2225 if (Result.isUndef())
2226 Result = UnknownVal();
2227
2228 return Result;
2229}
2230
2231SVal
2232RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
2233 const TypedValueRegion *R,
2234 QualType Ty) {
2235
2236 // At this point we have already checked in either getBindingForElement or
2237 // getBindingForField if 'R' has a direct binding.
2238
2239 // Lazy binding?
2240 Store lazyBindingStore = nullptr;
2241 const SubRegion *lazyBindingRegion = nullptr;
2242 std::tie(lazyBindingStore, lazyBindingRegion) = findLazyBinding(B, R, R);
2243 if (lazyBindingRegion)
2244 return getLazyBinding(lazyBindingRegion,
2245 getRegionBindings(lazyBindingStore));
2246
2247 // Record whether or not we see a symbolic index. That can completely
2248 // be out of scope of our lookup.
2249 bool hasSymbolicIndex = false;
2250
2251 // FIXME: This is a hack to deal with RegionStore's inability to distinguish a
2252 // default value for /part/ of an aggregate from a default value for the
2253 // /entire/ aggregate. The most common case of this is when struct Outer
2254 // has as its first member a struct Inner, which is copied in from a stack
2255 // variable. In this case, even if the Outer's default value is symbolic, 0,
2256 // or unknown, it gets overridden by the Inner's default value of undefined.
2257 //
2258 // This is a general problem -- if the Inner is zero-initialized, the Outer
2259 // will now look zero-initialized. The proper way to solve this is with a
2260 // new version of RegionStore that tracks the extent of a binding as well
2261 // as the offset.
2262 //
2263 // This hack only takes care of the undefined case because that can very
2264 // quickly result in a warning.
2265 bool hasPartialLazyBinding = false;
2266
2267 const SubRegion *SR = R;
2268 while (SR) {
2269 const MemRegion *Base = SR->getSuperRegion();
2270 if (std::optional<SVal> D =
2271 getBindingForDerivedDefaultValue(B, Base, R, Ty)) {
2272 if (D->getAs<nonloc::LazyCompoundVal>()) {
2273 hasPartialLazyBinding = true;
2274 break;
2275 }
2276
2277 return *D;
2278 }
2279
2280 if (const ElementRegion *ER = dyn_cast<ElementRegion>(Base)) {
2281 NonLoc index = ER->getIndex();
2282 if (!index.isConstant())
2283 hasSymbolicIndex = true;
2284 }
2285
2286 // If our super region is a field or element itself, walk up the region
2287 // hierarchy to see if there is a default value installed in an ancestor.
2288 SR = dyn_cast<SubRegion>(Base);
2289 }
2290
2292 if (isa<ElementRegion>(R)) {
2293 // Currently we don't reason specially about Clang-style vectors. Check
2294 // if superR is a vector and if so return Unknown.
2295 if (const TypedValueRegion *typedSuperR =
2296 dyn_cast<TypedValueRegion>(R->getSuperRegion())) {
2297 if (typedSuperR->getValueType()->isVectorType())
2298 return UnknownVal();
2299 }
2300 }
2301
2302 // FIXME: We also need to take ElementRegions with symbolic indexes into
2303 // account. This case handles both directly accessing an ElementRegion
2304 // with a symbolic offset, but also fields within an element with
2305 // a symbolic offset.
2306 if (hasSymbolicIndex)
2307 return UnknownVal();
2308
2309 // Additionally allow introspection of a block's internal layout.
2310 // Try to get direct binding if all other attempts failed thus far.
2311 // Else, return UndefinedVal()
2312 if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) {
2313 if (const std::optional<SVal> &V = B.getDefaultBinding(R))
2314 return *V;
2315 return UndefinedVal();
2316 }
2317 }
2318
2319 // All other values are symbolic.
2320 return svalBuilder.getRegionValueSymbolVal(R);
2321}
2322
2323SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
2324 const ObjCIvarRegion* R) {
2325 // Check if the region has a binding.
2326 if (const std::optional<SVal> &V = B.getDirectBinding(R))
2327 return *V;
2328
2329 const MemRegion *superR = R->getSuperRegion();
2330
2331 // Check if the super region has a default binding.
2332 if (const std::optional<SVal> &V = B.getDefaultBinding(superR)) {
2333 if (SymbolRef parentSym = V->getAsSymbol())
2334 return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
2335
2336 // Other cases: give up.
2337 return UnknownVal();
2338 }
2339
2340 return getBindingForLazySymbol(R);
2341}
2342
2343SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
2344 const VarRegion *R) {
2345
2346 // Check if the region has a binding.
2347 if (std::optional<SVal> V = B.getDirectBinding(R))
2348 return *V;
2349
2350 if (std::optional<SVal> V = B.getDefaultBinding(R))
2351 return *V;
2352
2353 // Lazily derive a value for the VarRegion.
2354 const VarDecl *VD = R->getDecl();
2355 const MemSpaceRegion *MS = R->getRawMemorySpace();
2356
2357 // Arguments are always symbolic.
2359 return svalBuilder.getRegionValueSymbolVal(R);
2360
2361 // Is 'VD' declared constant? If so, retrieve the constant value.
2362 if (VD->getType().isConstQualified()) {
2363 if (const Expr *Init = VD->getAnyInitializer()) {
2364 if (std::optional<SVal> V = svalBuilder.getConstantVal(Init))
2365 return *V;
2366
2367 // If the variable is const qualified and has an initializer but
2368 // we couldn't evaluate initializer to a value, treat the value as
2369 // unknown.
2370 return UnknownVal();
2371 }
2372 }
2373
2374 // This must come after the check for constants because closure-captured
2375 // constant variables may appear in UnknownSpaceRegion.
2377 return svalBuilder.getRegionValueSymbolVal(R);
2378
2379 if (isa<GlobalsSpaceRegion>(MS)) {
2380 QualType T = VD->getType();
2381
2382 // If we're in main(), then global initializers have not become stale yet.
2383 if (B.isMainAnalysis())
2384 if (const Expr *Init = VD->getAnyInitializer())
2385 if (std::optional<SVal> V = svalBuilder.getConstantVal(Init))
2386 return *V;
2387
2388 // Function-scoped static variables are default-initialized to 0; if they
2389 // have an initializer, it would have been processed by now.
2390 // FIXME: This is only true when we're starting analysis from main().
2391 // We're losing a lot of coverage here.
2393 return svalBuilder.makeZeroVal(T);
2394
2395 if (std::optional<SVal> V = getBindingForDerivedDefaultValue(B, MS, R, T)) {
2396 assert(!V->getAs<nonloc::LazyCompoundVal>());
2397 return *V;
2398 }
2399
2400 return svalBuilder.getRegionValueSymbolVal(R);
2401 }
2402
2403 return UndefinedVal();
2404}
2405
2406SVal RegionStoreManager::getBindingForLazySymbol(const TypedValueRegion *R) {
2407 // All other values are symbolic.
2408 return svalBuilder.getRegionValueSymbolVal(R);
2409}
2410
2411const RegionStoreManager::SValListTy &
2412RegionStoreManager::getInterestingValues(nonloc::LazyCompoundVal LCV) {
2413 // First, check the cache.
2414 LazyBindingsMapTy::iterator I = LazyBindingsMap.find(LCV.getCVData());
2415 if (I != LazyBindingsMap.end())
2416 return I->second;
2417
2418 // If we don't have a list of values cached, start constructing it.
2419 SValListTy List;
2420
2421 const SubRegion *LazyR = LCV.getRegion();
2422 RegionBindingsRef B = getRegionBindings(LCV.getStore());
2423
2424 // If this region had /no/ bindings at the time, there are no interesting
2425 // values to return.
2426 const ClusterBindings *Cluster = B.lookup(LazyR->getBaseRegion());
2427 if (!Cluster)
2428 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2429
2430 SmallVector<BindingPair, 32> Bindings;
2431 collectSubRegionBindings(Bindings, svalBuilder, *Cluster, LazyR,
2432 /*IncludeAllDefaultBindings=*/true);
2433 for (SVal V : llvm::make_second_range(Bindings)) {
2434 if (V.isUnknownOrUndef() || V.isConstant())
2435 continue;
2436
2437 if (auto InnerLCV = V.getAs<nonloc::LazyCompoundVal>()) {
2438 const SValListTy &InnerList = getInterestingValues(*InnerLCV);
2439 llvm::append_range(List, InnerList);
2440 }
2441
2442 List.push_back(V);
2443 }
2444
2445 return (LazyBindingsMap[LCV.getCVData()] = std::move(List));
2446}
2447
2448NonLoc RegionStoreManager::createLazyBinding(RegionBindingsConstRef B,
2449 const TypedValueRegion *R) {
2450 if (std::optional<nonloc::LazyCompoundVal> V =
2451 getExistingLazyBinding(svalBuilder, B, R, false))
2452 return *V;
2453
2454 return svalBuilder.makeLazyCompoundVal(StoreRef(B.asStore(), *this), R);
2455}
2456
2457SVal RegionStoreManager::getBindingForStruct(RegionBindingsConstRef B,
2458 const TypedValueRegion *R) {
2459 const RecordDecl *RD =
2460 R->getValueType()->castAsCanonical<RecordType>()->getOriginalDecl();
2461 if (!RD->getDefinition())
2462 return UnknownVal();
2463
2464 // We also create a LCV for copying empty structs because then the store
2465 // behavior doesn't depend on the struct layout.
2466 // This way even an empty struct can carry taint, no matter if creduce drops
2467 // the last field member or not.
2468
2469 // Try to avoid creating a LCV if it would anyways just refer to a single
2470 // default binding.
2471 if (std::optional<SVal> Val = getUniqueDefaultBinding(B, R))
2472 return *Val;
2473 return createLazyBinding(B, R);
2474}
2475
2476SVal RegionStoreManager::getBindingForArray(RegionBindingsConstRef B,
2477 const TypedValueRegion *R) {
2478 assert(Ctx.getAsConstantArrayType(R->getValueType()) &&
2479 "Only constant array types can have compound bindings.");
2480
2481 return createLazyBinding(B, R);
2482}
2483
2484bool RegionStoreManager::includedInBindings(Store store,
2485 const MemRegion *region) const {
2486 RegionBindingsRef B = getRegionBindings(store);
2487 region = region->getBaseRegion();
2488
2489 // Quick path: if the base is the head of a cluster, the region is live.
2490 if (B.lookup(region))
2491 return true;
2492
2493 // Slow path: if the region is the VALUE of any binding, it is live.
2494 for (RegionBindingsRef::iterator RI = B.begin(), RE = B.end(); RI != RE; ++RI) {
2495 const ClusterBindings &Cluster = RI.getData();
2496 for (ClusterBindings::iterator CI = Cluster.begin(), CE = Cluster.end();
2497 CI != CE; ++CI) {
2498 SVal D = CI.getData();
2499 if (const MemRegion *R = D.getAsRegion())
2500 if (R->getBaseRegion() == region)
2501 return true;
2502 }
2503 }
2504
2505 return false;
2506}
2507
2508//===----------------------------------------------------------------------===//
2509// Binding values to regions.
2510//===----------------------------------------------------------------------===//
2511
2512StoreRef RegionStoreManager::killBinding(Store ST, Loc L) {
2513 if (std::optional<loc::MemRegionVal> LV = L.getAs<loc::MemRegionVal>())
2514 if (const MemRegion* R = LV->getRegion())
2515 return StoreRef(getRegionBindings(ST)
2516 .removeBinding(R)
2517 .asImmutableMap()
2518 .getRootWithoutRetain(),
2519 *this);
2520
2521 return StoreRef(ST, *this);
2522}
2523
2524LimitedRegionBindingsRef
2525RegionStoreManager::bind(LimitedRegionBindingsConstRef B, Loc L, SVal V) {
2526 llvm::TimeTraceScope TimeScope("RegionStoreManager::bind",
2527 [&L]() { return locDescr(L); });
2528
2530 return B.withValuesEscaped(V);
2531
2532 // We only care about region locations.
2533 auto MemRegVal = L.getAs<loc::MemRegionVal>();
2534 if (!MemRegVal)
2535 return B;
2536
2537 const MemRegion *R = MemRegVal->getRegion();
2538
2539 // Binding directly to a symbolic region should be treated as binding
2540 // to element 0.
2541 if (const auto *SymReg = dyn_cast<SymbolicRegion>(R)) {
2542 QualType Ty = SymReg->getPointeeStaticType();
2543 if (Ty->isVoidType())
2544 Ty = StateMgr.getContext().CharTy;
2545 R = GetElementZeroRegion(SymReg, Ty);
2546 }
2547
2548 // Check if the region is a struct region.
2549 if (const TypedValueRegion* TR = dyn_cast<TypedValueRegion>(R)) {
2550 QualType Ty = TR->getValueType();
2551 if (Ty->isArrayType())
2552 return bindArray(B, TR, V);
2553 if (Ty->isStructureOrClassType())
2554 return bindStruct(B, TR, V);
2555 if (Ty->isVectorType())
2556 return bindVector(B, TR, V);
2557 if (Ty->isUnionType())
2558 return bindAggregate(B, TR, V);
2559 }
2560
2561 assert((!isa<CXXThisRegion>(R) || !B.lookup(R)) &&
2562 "'this' pointer is not an l-value and is not assignable");
2563
2564 // Clear out bindings that may overlap with this binding.
2565 auto NewB = removeSubRegionBindings(B, cast<SubRegion>(R));
2566
2567 // LazyCompoundVals should be always bound as 'default' bindings.
2568 auto KeyKind = isa<nonloc::LazyCompoundVal>(V) ? BindingKey::Default
2569 : BindingKey::Direct;
2570 return NewB.addBinding(BindingKey::Make(R, KeyKind), V);
2571}
2572
2573LimitedRegionBindingsRef
2574RegionStoreManager::setImplicitDefaultValue(LimitedRegionBindingsConstRef B,
2575 const MemRegion *R, QualType T) {
2577 return B;
2578
2579 SVal V;
2580
2581 if (Loc::isLocType(T))
2582 V = svalBuilder.makeNullWithType(T);
2583 else if (T->isIntegralOrEnumerationType())
2584 V = svalBuilder.makeZeroVal(T);
2585 else if (T->isStructureOrClassType() || T->isArrayType()) {
2586 // Set the default value to a zero constant when it is a structure
2587 // or array. The type doesn't really matter.
2588 V = svalBuilder.makeZeroVal(Ctx.IntTy);
2589 }
2590 else {
2591 // We can't represent values of this type, but we still need to set a value
2592 // to record that the region has been initialized.
2593 // If this assertion ever fires, a new case should be added above -- we
2594 // should know how to default-initialize any value we can symbolicate.
2595 assert(!SymbolManager::canSymbolicate(T) && "This type is representable");
2596 V = UnknownVal();
2597 }
2598
2599 return B.addBinding(R, BindingKey::Default, V);
2600}
2601
2602std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallArray(
2603 LimitedRegionBindingsConstRef B, const TypedValueRegion *R,
2604 const ArrayType *AT, nonloc::LazyCompoundVal LCV) {
2606 return B.withValuesEscaped(LCV);
2607
2608 auto CAT = dyn_cast<ConstantArrayType>(AT);
2609
2610 // If we don't know the size, create a lazyCompoundVal instead.
2611 if (!CAT)
2612 return std::nullopt;
2613
2614 QualType Ty = CAT->getElementType();
2615 if (!(Ty->isScalarType() || Ty->isReferenceType()))
2616 return std::nullopt;
2617
2618 // If the array is too big, create a LCV instead.
2619 uint64_t ArrSize = CAT->getLimitedSize();
2620 if (ArrSize > SmallArrayLimit)
2621 return std::nullopt;
2622
2623 LimitedRegionBindingsRef NewB = B;
2624
2625 for (uint64_t i = 0; i < ArrSize; ++i) {
2626 auto Idx = svalBuilder.makeArrayIndex(i);
2627 const ElementRegion *SrcER =
2628 MRMgr.getElementRegion(Ty, Idx, LCV.getRegion(), Ctx);
2629 SVal V = getBindingForElement(getRegionBindings(LCV.getStore()), SrcER);
2630
2631 const ElementRegion *DstER = MRMgr.getElementRegion(Ty, Idx, R, Ctx);
2632 NewB = bind(NewB, loc::MemRegionVal(DstER), V);
2633 }
2634
2635 return NewB;
2636}
2637
2638LimitedRegionBindingsRef
2639RegionStoreManager::bindArray(LimitedRegionBindingsConstRef B,
2640 const TypedValueRegion *R, SVal Init) {
2641 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindArray",
2642 [R]() { return R->getDescriptiveName(); });
2644 return B.withValuesEscaped(Init);
2645
2646 const ArrayType *AT =cast<ArrayType>(Ctx.getCanonicalType(R->getValueType()));
2647 QualType ElementTy = AT->getElementType();
2648 std::optional<uint64_t> Size;
2649
2650 if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(AT))
2651 Size = CAT->getZExtSize();
2652
2653 // Check if the init expr is a literal. If so, bind the rvalue instead.
2654 // FIXME: It's not responsibility of the Store to transform this lvalue
2655 // to rvalue. ExprEngine or maybe even CFG should do this before binding.
2656 if (std::optional<loc::MemRegionVal> MRV = Init.getAs<loc::MemRegionVal>()) {
2657 SVal V = getBinding(B.asStore(), *MRV, R->getValueType());
2658 return bindAggregate(B, R, V);
2659 }
2660
2661 // Handle lazy compound values.
2662 if (std::optional LCV = Init.getAs<nonloc::LazyCompoundVal>()) {
2663 if (std::optional NewB = tryBindSmallArray(B, R, AT, *LCV))
2664 return *NewB;
2665
2666 return bindAggregate(B, R, Init);
2667 }
2668
2669 if (Init.isUnknown())
2670 return bindAggregate(B, R, UnknownVal());
2671
2672 // Remaining case: explicit compound values.
2673 const nonloc::CompoundVal& CV = Init.castAs<nonloc::CompoundVal>();
2674 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2675 uint64_t i = 0;
2676
2677 LimitedRegionBindingsRef NewB = B;
2678
2679 for (; Size ? i < *Size : true; ++i, ++VI) {
2680 // The init list might be shorter than the array length.
2681 if (VI == VE)
2682 break;
2683 if (NewB.hasExhaustedBindingLimit())
2684 return NewB.withValuesEscaped(VI, VE);
2685
2686 NonLoc Idx = svalBuilder.makeArrayIndex(i);
2687 const ElementRegion *ER = MRMgr.getElementRegion(ElementTy, Idx, R, Ctx);
2688
2689 if (ElementTy->isStructureOrClassType())
2690 NewB = bindStruct(NewB, ER, *VI);
2691 else if (ElementTy->isArrayType())
2692 NewB = bindArray(NewB, ER, *VI);
2693 else
2694 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2695 }
2696
2697 // If the init list is shorter than the array length (or the array has
2698 // variable length), set the array default value. Values that are already set
2699 // are not overwritten.
2700 if (!Size || i < *Size)
2701 NewB = setImplicitDefaultValue(NewB, R, ElementTy);
2702
2703 return NewB;
2704}
2705
2706LimitedRegionBindingsRef
2707RegionStoreManager::bindVector(LimitedRegionBindingsConstRef B,
2708 const TypedValueRegion *R, SVal V) {
2709 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindVector",
2710 [R]() { return R->getDescriptiveName(); });
2712 return B.withValuesEscaped(V);
2713
2714 QualType T = R->getValueType();
2715 const VectorType *VT = T->castAs<VectorType>(); // Use castAs for typedefs.
2716
2717 // Handle lazy compound values and symbolic values.
2719 return bindAggregate(B, R, V);
2720
2721 // We may get non-CompoundVal accidentally due to imprecise cast logic or
2722 // that we are binding symbolic struct value. Kill the field values, and if
2723 // the value is symbolic go and bind it as a "default" binding.
2725 return bindAggregate(B, R, UnknownVal());
2726 }
2727
2728 QualType ElemType = VT->getElementType();
2729 nonloc::CompoundVal CV = V.castAs<nonloc::CompoundVal>();
2730 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2731 unsigned index = 0, numElements = VT->getNumElements();
2732 LimitedRegionBindingsRef NewB = B;
2733
2734 for ( ; index != numElements ; ++index) {
2735 if (VI == VE)
2736 break;
2737
2738 if (NewB.hasExhaustedBindingLimit())
2739 return NewB.withValuesEscaped(VI, VE);
2740
2741 NonLoc Idx = svalBuilder.makeArrayIndex(index);
2742 const ElementRegion *ER = MRMgr.getElementRegion(ElemType, Idx, R, Ctx);
2743
2744 if (ElemType->isArrayType())
2745 NewB = bindArray(NewB, ER, *VI);
2746 else if (ElemType->isStructureOrClassType())
2747 NewB = bindStruct(NewB, ER, *VI);
2748 else
2749 NewB = bind(NewB, loc::MemRegionVal(ER), *VI);
2750 }
2751 return NewB;
2752}
2753
2754std::optional<SVal>
2755RegionStoreManager::getUniqueDefaultBinding(RegionBindingsConstRef B,
2756 const TypedValueRegion *R) const {
2757 if (R != R->getBaseRegion())
2758 return std::nullopt;
2759
2760 const auto *Cluster = B.lookup(R);
2761 if (!Cluster || !llvm::hasSingleElement(*Cluster))
2762 return std::nullopt;
2763
2764 const auto [Key, Value] = *Cluster->begin();
2765 return Key.isDirect() ? std::optional<SVal>{} : Value;
2766}
2767
2768std::optional<SVal>
2769RegionStoreManager::getUniqueDefaultBinding(nonloc::LazyCompoundVal LCV) const {
2770 auto B = getRegionBindings(LCV.getStore());
2771 return getUniqueDefaultBinding(B, LCV.getRegion());
2772}
2773
2774std::optional<LimitedRegionBindingsRef> RegionStoreManager::tryBindSmallStruct(
2775 LimitedRegionBindingsConstRef B, const TypedValueRegion *R,
2776 const RecordDecl *RD, nonloc::LazyCompoundVal LCV) {
2778 return B.withValuesEscaped(LCV);
2779
2780 // If we try to copy a Conjured value representing the value of the whole
2781 // struct, don't try to element-wise copy each field.
2782 // That would unnecessarily bind Derived symbols slicing off the subregion for
2783 // the field from the whole Conjured symbol.
2784 //
2785 // struct Window { int width; int height; };
2786 // Window getWindow(); <-- opaque fn.
2787 // Window w = getWindow(); <-- conjures a new Window.
2788 // Window w2 = w; <-- trivial copy "w", calling "tryBindSmallStruct"
2789 //
2790 // We should not end up with a new Store for "w2" like this:
2791 // Direct [ 0..31]: Derived{Conj{}, w.width}
2792 // Direct [32..63]: Derived{Conj{}, w.height}
2793 // Instead, we should just bind that Conjured value instead.
2794 if (std::optional<SVal> Val = getUniqueDefaultBinding(LCV)) {
2795 return B.addBinding(BindingKey::Make(R, BindingKey::Default), Val.value());
2796 }
2797
2798 FieldVector Fields;
2799
2800 if (const CXXRecordDecl *Class = dyn_cast<CXXRecordDecl>(RD))
2801 if (Class->getNumBases() != 0 || Class->getNumVBases() != 0)
2802 return std::nullopt;
2803
2804 for (const auto *FD : RD->fields()) {
2805 if (FD->isUnnamedBitField())
2806 continue;
2807
2808 // If there are too many fields, or if any of the fields are aggregates,
2809 // just use the LCV as a default binding.
2810 if (Fields.size() == SmallStructLimit)
2811 return std::nullopt;
2812
2813 QualType Ty = FD->getType();
2814
2815 // Zero length arrays are basically no-ops, so we also ignore them here.
2816 if (Ty->isConstantArrayType() &&
2818 continue;
2819
2820 if (!(Ty->isScalarType() || Ty->isReferenceType()))
2821 return std::nullopt;
2822
2823 Fields.push_back(FD);
2824 }
2825
2826 LimitedRegionBindingsRef NewB = B;
2827
2828 for (const FieldDecl *Field : Fields) {
2829 const FieldRegion *SourceFR = MRMgr.getFieldRegion(Field, LCV.getRegion());
2830 SVal V = getBindingForField(getRegionBindings(LCV.getStore()), SourceFR);
2831
2832 const FieldRegion *DestFR = MRMgr.getFieldRegion(Field, R);
2833 NewB = bind(NewB, loc::MemRegionVal(DestFR), V);
2834 }
2835
2836 return NewB;
2837}
2838
2839LimitedRegionBindingsRef
2840RegionStoreManager::bindStruct(LimitedRegionBindingsConstRef B,
2841 const TypedValueRegion *R, SVal V) {
2842 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindStruct",
2843 [R]() { return R->getDescriptiveName(); });
2845 return B.withValuesEscaped(V);
2846
2847 QualType T = R->getValueType();
2848 assert(T->isStructureOrClassType());
2849
2850 const auto *RD = T->castAsRecordDecl();
2851 if (!RD->isCompleteDefinition())
2852 return B;
2853
2854 // Handle lazy compound values and symbolic values.
2855 if (std::optional<nonloc::LazyCompoundVal> LCV =
2856 V.getAs<nonloc::LazyCompoundVal>()) {
2857 if (std::optional NewB = tryBindSmallStruct(B, R, RD, *LCV))
2858 return *NewB;
2859 return bindAggregate(B, R, V);
2860 }
2862 return bindAggregate(B, R, V);
2863
2864 // We may get non-CompoundVal accidentally due to imprecise cast logic or
2865 // that we are binding symbolic struct value. Kill the field values, and if
2866 // the value is symbolic go and bind it as a "default" binding.
2867 if (V.isUnknown() || !isa<nonloc::CompoundVal>(V))
2868 return bindAggregate(B, R, UnknownVal());
2869
2870 // The raw CompoundVal is essentially a symbolic InitListExpr: an (immutable)
2871 // list of other values. It appears pretty much only when there's an actual
2872 // initializer list expression in the program, and the analyzer tries to
2873 // unwrap it as soon as possible.
2874 // This code is where such unwrap happens: when the compound value is put into
2875 // the object that it was supposed to initialize (it's an *initializer* list,
2876 // after all), instead of binding the whole value to the whole object, we bind
2877 // sub-values to sub-objects. Sub-values may themselves be compound values,
2878 // and in this case the procedure becomes recursive.
2879 // FIXME: The annoying part about compound values is that they don't carry
2880 // any sort of information about which value corresponds to which sub-object.
2881 // It's simply a list of values in the middle of nowhere; we expect to match
2882 // them to sub-objects, essentially, "by index": first value binds to
2883 // the first field, second value binds to the second field, etc.
2884 // It would have been much safer to organize non-lazy compound values as
2885 // a mapping from fields/bases to values.
2886 const nonloc::CompoundVal& CV = V.castAs<nonloc::CompoundVal>();
2887 nonloc::CompoundVal::iterator VI = CV.begin(), VE = CV.end();
2888
2889 LimitedRegionBindingsRef NewB = B;
2890
2891 // In C++17 aggregates may have base classes, handle those as well.
2892 // They appear before fields in the initializer list / compound value.
2893 if (const auto *CRD = dyn_cast<CXXRecordDecl>(RD)) {
2894 // If the object was constructed with a constructor, its value is a
2895 // LazyCompoundVal. If it's a raw CompoundVal, it means that we're
2896 // performing aggregate initialization. The only exception from this
2897 // rule is sending an Objective-C++ message that returns a C++ object
2898 // to a nil receiver; in this case the semantics is to return a
2899 // zero-initialized object even if it's a C++ object that doesn't have
2900 // this sort of constructor; the CompoundVal is empty in this case.
2901 assert((CRD->isAggregate() || (Ctx.getLangOpts().ObjC && VI == VE)) &&
2902 "Non-aggregates are constructed with a constructor!");
2903
2904 for (const auto &B : CRD->bases()) {
2905 // (Multiple inheritance is fine though.)
2906 assert(!B.isVirtual() && "Aggregates cannot have virtual base classes!");
2907
2908 if (VI == VE)
2909 break;
2910 if (NewB.hasExhaustedBindingLimit())
2911 return NewB.withValuesEscaped(VI, VE);
2912
2913 QualType BTy = B.getType();
2914 assert(BTy->isStructureOrClassType() && "Base classes must be classes!");
2915
2916 const CXXRecordDecl *BRD = BTy->getAsCXXRecordDecl();
2917 assert(BRD && "Base classes must be C++ classes!");
2918
2919 const CXXBaseObjectRegion *BR =
2920 MRMgr.getCXXBaseObjectRegion(BRD, R, /*IsVirtual=*/false);
2921
2922 NewB = bindStruct(NewB, BR, *VI);
2923
2924 ++VI;
2925 }
2926 }
2927
2929
2930 for (FI = RD->field_begin(), FE = RD->field_end(); FI != FE; ++FI) {
2931
2932 if (VI == VE)
2933 break;
2934
2935 if (NewB.hasExhaustedBindingLimit())
2936 return NewB.withValuesEscaped(VI, VE);
2937
2938 // Skip any unnamed bitfields to stay in sync with the initializers.
2939 if (FI->isUnnamedBitField())
2940 continue;
2941
2942 QualType FTy = FI->getType();
2943 const FieldRegion* FR = MRMgr.getFieldRegion(*FI, R);
2944
2945 if (FTy->isArrayType())
2946 NewB = bindArray(NewB, FR, *VI);
2947 else if (FTy->isStructureOrClassType())
2948 NewB = bindStruct(NewB, FR, *VI);
2949 else
2950 NewB = bind(NewB, loc::MemRegionVal(FR), *VI);
2951 ++VI;
2952 }
2953
2954 if (NewB.hasExhaustedBindingLimit())
2955 return NewB.withValuesEscaped(VI, VE);
2956
2957 // There may be fewer values in the initialize list than the fields of struct.
2958 if (FI != FE) {
2959 NewB = NewB.addBinding(R, BindingKey::Default,
2960 svalBuilder.makeIntVal(0, false));
2961 }
2962
2963 return NewB;
2964}
2965
2966LimitedRegionBindingsRef
2967RegionStoreManager::bindAggregate(LimitedRegionBindingsConstRef B,
2968 const TypedRegion *R, SVal Val) {
2969 llvm::TimeTraceScope TimeScope("RegionStoreManager::bindAggregate",
2970 [R]() { return R->getDescriptiveName(); });
2972 return B.withValuesEscaped(Val);
2973
2974 // Remove the old bindings, using 'R' as the root of all regions
2975 // we will invalidate. Then add the new binding.
2976 return removeSubRegionBindings(B, R).addBinding(R, BindingKey::Default, Val);
2977}
2978
2979//===----------------------------------------------------------------------===//
2980// State pruning.
2981//===----------------------------------------------------------------------===//
2982
2983namespace {
2984class RemoveDeadBindingsWorker
2985 : public ClusterAnalysis<RemoveDeadBindingsWorker> {
2986 SmallVector<const SymbolicRegion *, 12> Postponed;
2987 SymbolReaper &SymReaper;
2988 const StackFrameContext *CurrentLCtx;
2989
2990public:
2991 RemoveDeadBindingsWorker(RegionStoreManager &rm,
2992 ProgramStateManager &stateMgr,
2993 RegionBindingsRef b, SymbolReaper &symReaper,
2994 const StackFrameContext *LCtx)
2995 : ClusterAnalysis<RemoveDeadBindingsWorker>(rm, stateMgr, b),
2996 SymReaper(symReaper), CurrentLCtx(LCtx) {}
2997
2998 // Called by ClusterAnalysis.
2999 void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C);
3000 void VisitCluster(const MemRegion *baseR, const ClusterBindings *C);
3001 using ClusterAnalysis<RemoveDeadBindingsWorker>::VisitCluster;
3002
3003 using ClusterAnalysis::AddToWorkList;
3004
3005 bool AddToWorkList(const MemRegion *R);
3006
3007 bool UpdatePostponed();
3008 void VisitBinding(SVal V);
3009};
3010}
3011
3012bool RemoveDeadBindingsWorker::AddToWorkList(const MemRegion *R) {
3013 const MemRegion *BaseR = R->getBaseRegion();
3014 return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
3015}
3016
3017void RemoveDeadBindingsWorker::VisitAddedToCluster(const MemRegion *baseR,
3018 const ClusterBindings &C) {
3019
3020 if (const VarRegion *VR = dyn_cast<VarRegion>(baseR)) {
3021 if (SymReaper.isLive(VR))
3022 AddToWorkList(baseR, &C);
3023
3024 return;
3025 }
3026
3027 if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(baseR)) {
3028 if (SymReaper.isLive(SR->getSymbol()))
3029 AddToWorkList(SR, &C);
3030 else
3031 Postponed.push_back(SR);
3032
3033 return;
3034 }
3035
3037 AddToWorkList(baseR, &C);
3038 return;
3039 }
3040
3041 // CXXThisRegion in the current or parent location context is live.
3042 if (const CXXThisRegion *TR = dyn_cast<CXXThisRegion>(baseR)) {
3043 const auto *StackReg =
3045 const StackFrameContext *RegCtx = StackReg->getStackFrame();
3046 if (CurrentLCtx &&
3047 (RegCtx == CurrentLCtx || RegCtx->isParentOf(CurrentLCtx)))
3048 AddToWorkList(TR, &C);
3049 }
3050}
3051
3052void RemoveDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
3053 const ClusterBindings *C) {
3054 if (!C)
3055 return;
3056
3057 // Mark the symbol for any SymbolicRegion with live bindings as live itself.
3058 // This means we should continue to track that symbol.
3059 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
3060 SymReaper.markLive(SymR->getSymbol());
3061
3062 for (const auto &[Key, Val] : *C) {
3063 // Element index of a binding key is live.
3064 SymReaper.markElementIndicesLive(Key.getRegion());
3065
3066 VisitBinding(Val);
3067 }
3068}
3069
3070void RemoveDeadBindingsWorker::VisitBinding(SVal V) {
3071 // Is it a LazyCompoundVal? All referenced regions are live as well.
3072 // The LazyCompoundVal itself is not live but should be readable.
3073 if (auto LCS = V.getAs<nonloc::LazyCompoundVal>()) {
3074 SymReaper.markLazilyCopied(LCS->getRegion());
3075
3076 for (SVal V : RM.getInterestingValues(*LCS)) {
3077 if (auto DepLCS = V.getAs<nonloc::LazyCompoundVal>())
3078 SymReaper.markLazilyCopied(DepLCS->getRegion());
3079 else
3080 VisitBinding(V);
3081 }
3082
3083 return;
3084 }
3085
3086 // If V is a region, then add it to the worklist.
3087 if (const MemRegion *R = V.getAsRegion()) {
3088 AddToWorkList(R);
3089 SymReaper.markLive(R);
3090
3091 // All regions captured by a block are also live.
3092 if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
3093 for (auto Var : BR->referenced_vars())
3094 AddToWorkList(Var.getCapturedRegion());
3095 }
3096 }
3097
3098
3099 // Update the set of live symbols.
3100 for (SymbolRef Sym : V.symbols())
3101 SymReaper.markLive(Sym);
3102}
3103
3104bool RemoveDeadBindingsWorker::UpdatePostponed() {
3105 // See if any postponed SymbolicRegions are actually live now, after
3106 // having done a scan.
3107 bool Changed = false;
3108
3109 for (const SymbolicRegion *SR : Postponed) {
3110 if (SymReaper.isLive(SR->getSymbol())) {
3111 Changed |= AddToWorkList(SR);
3112 SR = nullptr;
3113 }
3114 }
3115
3116 return Changed;
3117}
3118
3119StoreRef RegionStoreManager::removeDeadBindings(Store store,
3120 const StackFrameContext *LCtx,
3121 SymbolReaper& SymReaper) {
3122 RegionBindingsRef B = getRegionBindings(store);
3123 RemoveDeadBindingsWorker W(*this, StateMgr, B, SymReaper, LCtx);
3124 W.GenerateClusters();
3125
3126 // Enqueue the region roots onto the worklist.
3127 for (const MemRegion *Reg : SymReaper.regions()) {
3128 W.AddToWorkList(Reg);
3129 }
3130
3131 do W.RunWorkList(); while (W.UpdatePostponed());
3132
3133 // We have now scanned the store, marking reachable regions and symbols
3134 // as live. We now remove all the regions that are dead from the store
3135 // as well as update DSymbols with the set symbols that are now dead.
3136 for (const MemRegion *Base : llvm::make_first_range(B)) {
3137 // If the cluster has been visited, we know the region has been marked.
3138 // Otherwise, remove the dead entry.
3139 if (!W.isVisited(Base))
3140 B = B.removeCluster(Base);
3141 }
3142
3143 return StoreRef(B.asStore(), *this);
3144}
3145
3146//===----------------------------------------------------------------------===//
3147// Utility methods.
3148//===----------------------------------------------------------------------===//
3149
3150void RegionStoreManager::printJson(raw_ostream &Out, Store S, const char *NL,
3151 unsigned int Space, bool IsDot) const {
3152 RegionBindingsRef Bindings = getRegionBindings(S);
3153
3154 Indent(Out, Space, IsDot) << "\"store\": ";
3155
3156 if (Bindings.isEmpty()) {
3157 Out << "null," << NL;
3158 return;
3159 }
3160
3161 Out << "{ \"pointer\": \"" << Bindings.asStore() << "\", \"items\": [" << NL;
3162 Bindings.printJson(Out, NL, Space + 1, IsDot);
3163 Indent(Out, Space, IsDot) << "]}," << NL;
3164}
#define V(N, I)
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
#define X(type, name)
Definition Value.h:97
static std::optional< SVal > convertOffsetsFromSvalToUnsigneds(const SmallVector< SVal, 2 > &SrcOffsets, const SmallVector< uint64_t, 2 > ArrayExtents, SmallVector< uint64_t, 2 > &DstOffsets)
llvm::ImmutableMap< const MemRegion *, ClusterBindings > RegionBindings
static std::optional< SVal > getDerivedSymbolForBinding(RegionBindingsConstRef B, const TypedValueRegion *BaseRegion, const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB)
std::pair< BindingKey, SVal > BindingPair
static bool isCompatibleWithFields(BindingKey K, const FieldVector &Fields)
SmallVector< const FieldDecl *, 8 > FieldVector
llvm::ImmutableMap< BindingKey, SVal > ClusterBindings
static bool isUnionField(const FieldRegion *FR)
const LimitedRegionBindingsRef & LimitedRegionBindingsConstRef
static void getSymbolicOffsetFields(BindingKey K, FieldVector &Fields)
static QualType getUnderlyingType(const SubRegion *R)
llvm::ImmutableMapRef< BindingKey, SVal > ClusterBindingsRef
static SmallVector< uint64_t, 2 > getConstantArrayExtents(const ConstantArrayType *CAT)
This is a helper function for getConstantValFromConstArrayInitializer.
static std::pair< SmallVector< SVal, 2 >, const MemRegion * > getElementRegionOffsetsWithBase(const ElementRegion *ER)
This is a helper function for getConstantValFromConstArrayInitializer.
const RegionBindingsRef & RegionBindingsConstRef
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.
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.
llvm::SmallVector< std::pair< const MemRegion *, SVal >, 4 > Bindings
__device__ __2f16 b
__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 ...
LimitedRegionBindingsRef removeCluster(const MemRegion *BaseRegion) const
LimitedRegionBindingsRef withValuesEscaped(nonloc::CompoundVal::iterator Begin, nonloc::CompoundVal::iterator End) const
LimitedRegionBindingsRef withValuesEscaped(SVal V) const
LimitedRegionBindingsRef(RegionBindingsRef Base, SmallVectorImpl< SVal > &EscapedValuesDuringBind, std::optional< unsigned > BindingsLeft)
bool hasExhaustedBindingLimit() const
LimitedRegionBindingsRef addBinding(BindingKey K, SVal V) const
LimitedRegionBindingsRef addBinding(const MemRegion *R, BindingKey::Kind k, SVal V) const
LimitedRegionBindingsRef addWithoutDecreasingLimit(const MemRegion *BaseRegion, data_type_ref BindingKeyAndValue) const
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition ASTContext.h:188
const ConstantArrayType * getAsConstantArrayType(QualType T) const
CanQualType getCanonicalType(QualType T) const
Return the canonical (structural) type corresponding to the specified potentially non-canonical type ...
const LangOptions & getLangOpts() const
Definition ASTContext.h:894
CanQualType IntTy
bool hasSameUnqualifiedType(QualType T1, QualType T2) const
Determine whether the given types are equivalent after cvr-qualifiers have been removed.
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.
uint64_t getCharWidth() const
Return the size of the character type, in bits.
QualType getElementType() const
Definition TypeBase.h:3750
Represents the canonical version of C arrays with a specified constant size.
Definition TypeBase.h:3776
uint64_t getLimitedSize() const
Return the size zero-extended to uint64_t or UINT64_MAX if the value is larger than UINT64_MAX.
Definition TypeBase.h:3865
uint64_t getZExtSize() const
Return the size zero-extended as a uint64_t.
Definition TypeBase.h:3852
bool hasAttr() const
Definition DeclBase.h:577
unsigned getFieldIndex() const
Returns the index of this field within its record, as appropriate for passing to ASTRecordLayout::get...
Definition Decl.h:3242
const RecordDecl * getParent() const
Returns the parent of this field declaration, which is the struct in which this field is defined.
Definition Decl.h:3393
bool isUnnamedBitField() const
Determines whether this is an unnamed bitfield.
Definition Decl.h:3263
bool isStringLiteralInit() const
Is this an initializer for an array of characters, initialized by a string literal or an @encode?
Definition Expr.cpp:2443
unsigned getNumInits() const
Definition Expr.h:5265
const Expr * getInit(unsigned Init) const
Definition Expr.h:5289
bool isParentOf(const LocationContext *LC) const
const Decl * getDecl() const
A (possibly-)qualified type.
Definition TypeBase.h:937
bool isNull() const
Return true if this QualType doesn't point to a type yet.
Definition TypeBase.h:1004
bool isConstQualified() const
Determine whether this type is const-qualified.
Definition TypeBase.h:8416
field_iterator field_end() const
Definition Decl.h:4515
field_range fields() const
Definition Decl.h:4512
RecordDecl * getDefinition() const
Returns the RecordDecl that actually defines this struct/union/class.
Definition Decl.h:4493
specific_decl_iterator< FieldDecl > field_iterator
Definition Decl.h:4509
field_iterator field_begin() const
Definition Decl.cpp:5154
unsigned getLength() const
Definition Expr.h:1911
uint32_t getCodeUnit(size_t i) const
Definition Expr.h:1884
bool isCompleteDefinition() const
Return true if this decl has its body fully specified.
Definition Decl.h:3809
bool isUnion() const
Definition Decl.h:3919
bool isVoidType() const
Definition TypeBase.h:8936
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition Type.h:26
bool isConstantArrayType() const
Definition TypeBase.h:8683
bool isVoidPointerType() const
Definition Type.cpp:712
bool isArrayType() const
Definition TypeBase.h:8679
const T * castAs() const
Member-template castAs<specific type>.
Definition TypeBase.h:9226
bool isReferenceType() const
Definition TypeBase.h:8604
bool isScalarType() const
Definition TypeBase.h:9038
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
Definition Type.cpp:752
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition TypeBase.h:9054
RecordDecl * castAsRecordDecl() const
Definition Type.h:48
bool isAnyComplexType() const
Definition TypeBase.h:8715
QualType getCanonicalTypeInternal() const
Definition TypeBase.h:3137
bool isStructureOrClassType() const
Definition Type.cpp:706
bool isVectorType() const
Definition TypeBase.h:8719
const T * castAsCanonical() const
Return this type's canonical type cast to the specified type.
Definition TypeBase.h:2946
bool isRecordType() const
Definition TypeBase.h:8707
bool isUnionType() const
Definition Type.cpp:718
QualType getType() const
Definition Decl.h:722
bool hasGlobalStorage() const
Returns true for all variables that do not have local storage.
Definition Decl.h:1225
bool hasLocalStorage() const
Returns true if a variable with function scope is a non-static local variable.
Definition Decl.h:1183
const Expr * getAnyInitializer() const
Get the initializer for this variable, no matter which declaration it is attached to.
Definition Decl.h:1357
unsigned getNumElements() const
Definition TypeBase.h:4206
QualType getElementType() const
Definition TypeBase.h:4205
ElementRegion is used to represent both array elements and casts.
Definition MemRegion.h:1227
QualType getElementType() const
Definition MemRegion.h:1251
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
Definition MemRegion.h:1153
void dumpToStream(raw_ostream &Out) const
Definition SVals.cpp:379
static bool isLocType(QualType T)
Definition SVals.h:262
DefinedOrUnknownSVal getStaticSize(const MemRegion *MR, SValBuilder &SVB) const
MemRegion - The root abstract class for all memory regions.
Definition MemRegion.h:98
virtual bool isBoundable() const
Definition MemRegion.h:211
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.
Definition MemRegion.h:1672
@ TK_EntireMemSpace
When applied to a MemSpaceRegion, indicates the entire memory space should be invalidated.
Definition MemRegion.h:1682
bool hasTrait(SymbolRef Sym, InvalidationKinds IK) const
bool hasSymbolicOffset() const
Definition MemRegion.h:83
const MemRegion * getRegion() const
It might return null.
Definition MemRegion.h:81
int64_t getOffset() const
Definition MemRegion.h:85
const MemRegion * getRegion() const
Definition MemRegion.h:1220
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'.
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.
Definition SVals.h:56
bool isZeroConstant() const
Definition SVals.cpp:257
bool isUnknownOrUndef() const
Definition SVals.h:109
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition SVals.cpp:103
bool isConstant() const
Definition SVals.cpp:245
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition SVals.h:87
const MemRegion * getAsRegion() const
Definition SVals.cpp:119
T castAs() const
Convert to the specified SVal type, asserting that this SVal is of the desired type.
Definition SVals.h:83
bool scan(nonloc::LazyCompoundVal val)
SmallVector< const MemRegion *, 8 > InvalidatedRegions
Definition Store.h:211
SubRegion - A region that subsets another larger region.
Definition MemRegion.h:474
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getSuperRegion() const
Definition MemRegion.h:487
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
Definition SymExpr.h:107
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.
Definition MemRegion.h:808
TypedValueRegion - An abstract class representing regions having a typed value.
Definition MemRegion.h:563
virtual QualType getValueType() const =0
QualType getLocationType() const override
Definition MemRegion.h:574
QualType getValueType() const override
Definition MemRegion.h:999
const VarDecl * getDecl() const override=0
llvm::ImmutableList< SVal >::iterator iterator
Definition SVals.h:352
Value representing integer constant.
Definition SVals.h:300
While nonloc::CompoundVal covers a few simple use cases, nonloc::LazyCompoundVal is a more performant...
Definition SVals.h:389
LLVM_ATTRIBUTE_RETURNS_NONNULL const LazyCompoundValData * getCVData() const
Definition SVals.h:399
LLVM_ATTRIBUTE_RETURNS_NONNULL const TypedValueRegion * getRegion() const
This function itself is immaterial.
Definition SVals.cpp:193
const void * getStore() const
It might return null.
Definition SVals.cpp:189
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
Definition Store.h:51
const SymExpr * SymbolRef
Definition SymExpr.h:133
@ OS
Indicates that the tracking object is a descendant of a referenced-counted OSObject,...
std::unique_ptr< StoreManager > CreateRegionStoreManager(ProgramStateManager &StMgr)
const void * Store
Store - This opaque type encapsulates an immutable mapping from locations to values.
Definition StoreRef.h:27
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.
Definition Sema.h:816
bool isa(CodeGen::Address addr)
Definition Address.h:330
CFGBlock::ConstCFGElementRef ConstCFGElementRef
Definition CFG.h:1199
@ Bind
'bind' clause, allowed on routine constructs.
bool operator==(const CallGraphNode::CallRecord &LHS, const CallGraphNode::CallRecord &RHS)
Definition CallGraph.h:204
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
const StreamingDiagnostic & operator<<(const StreamingDiagnostic &DB, const ASTContext::SectionInfo &Section)
Insertion operator for diagnostics.
raw_ostream & Indent(raw_ostream &Out, const unsigned int Space, bool IsDot)
Definition JsonSupport.h:21
@ Result
The result type of a method or function.
Definition TypeBase.h:905
const FunctionProtoType * T
U cast(CodeGen::Address addr)
Definition Address.h:327
@ Class
The "class" keyword introduces the elaborated-type-specifier.
Definition TypeBase.h:5892
unsigned long uint64_t
unsigned int uint32_t
Diagnostic wrappers for TextAPI types for error reporting.
Definition Dominators.h:30
__UINTPTR_TYPE__ uintptr_t
An unsigned integer type with the property that any valid pointer to void can be converted to this ty...