Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h @@ -147,6 +147,8 @@ /// Compute the offset within the top level memory object. RegionOffset getAsOffset() const; + uint64_t getExtent() const; + /// Get a string representation of a region for debug use. std::string getString() const; Index: clang/lib/StaticAnalyzer/Core/MemRegion.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/MemRegion.cpp +++ clang/lib/StaticAnalyzer/Core/MemRegion.cpp @@ -1602,6 +1602,23 @@ return *cachedOffset; } +uint64_t MemRegion::getExtent() const { + const MemRegion *R = this; + uint64_t Extent = 0; + + if (const auto *TVR = dyn_cast(R)) { + const auto Ty = TVR->getDesugaredValueType(getContext()); + if (!Ty->isIncompleteType()) + Extent = getContext().getTypeSize(Ty); + } else if (const auto *SR = dyn_cast(R)) { + const auto Ty = SR->getSymbol()->getType().getDesugaredType(getContext()); + if (!Ty->isIncompleteType()) + Extent = getContext().getTypeSize(Ty); + } + + return Extent; +} + //===----------------------------------------------------------------------===// // BlockDataRegion //===----------------------------------------------------------------------===// Index: clang/lib/StaticAnalyzer/Core/RegionStore.cpp =================================================================== --- clang/lib/StaticAnalyzer/Core/RegionStore.cpp +++ clang/lib/StaticAnalyzer/Core/RegionStore.cpp @@ -48,24 +48,29 @@ llvm::PointerIntPair P; uint64_t Data; + uint64_t Extent; /// Create a key for a binding to region \p r, which has a symbolic offset /// from region \p Base. - explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k) - : P(r, k | Symbolic), Data(reinterpret_cast(Base)) { + explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k, + uint64_t extent) + : P(r, k | Symbolic), Data(reinterpret_cast(Base)), + Extent(extent) { assert(r && Base && "Must have known regions."); assert(getConcreteOffsetRegion() == Base && "Failed to store base region"); } /// Create a key for a binding at \p offset from base region \p r. - explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k) - : P(r, k), Data(offset) { + explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k, + uint64_t extent) + : P(r, k), Data(offset), Extent(extent) { assert(r && "Must have known regions."); assert(getOffset() == offset && "Failed to store offset"); assert((r == r->getBaseRegion() || isa(r)) && "Not a base"); } + public: bool isDirect() const { return P.getInt() & Direct; } @@ -77,6 +82,8 @@ return Data; } + uint64_t getExtent() const { return Extent; } + const SubRegion *getConcreteOffsetRegion() const { assert(hasSymbolicOffset()); return reinterpret_cast(static_cast(Data)); @@ -91,6 +98,7 @@ void Profile(llvm::FoldingSetNodeID& ID) const { ID.AddPointer(P.getOpaqueValue()); ID.AddInteger(Data); + ID.AddInteger(Extent); } static BindingKey Make(const MemRegion *R, Kind k); @@ -103,11 +111,30 @@ return Data < X.Data; } - bool operator==(const BindingKey &X) const { + bool isInsideOrEqual(const BindingKey &X) const { + if (hasSymbolicOffset() || X.hasSymbolicOffset()) + return false; + + if (P.getOpaqueValue() != X.P.getOpaqueValue()) + return false; + + return getOffset() >= X.getOffset() && + getOffset() <= + X.getOffset() + + X.getExtent() && // The offset can be negative and in that + // case we might hit an overflow. + getOffset() + getExtent() <= X.getOffset() + X.getExtent(); + } + + bool isSameWithoutExtent(const BindingKey &X) const { return P.getOpaqueValue() == X.P.getOpaqueValue() && Data == X.Data; } + bool operator==(const BindingKey &X) const { + return isSameWithoutExtent(X) && Extent == X.Extent; + } + LLVM_DUMP_METHOD void dump() const; }; } // end anonymous namespace @@ -115,9 +142,10 @@ BindingKey BindingKey::Make(const MemRegion *R, Kind k) { const RegionOffset &RO = R->getAsOffset(); if (RO.hasSymbolicOffset()) - return BindingKey(cast(R), cast(RO.getRegion()), k); + return BindingKey(cast(R), cast(RO.getRegion()), k, + R->getExtent()); - return BindingKey(RO.getRegion(), RO.getOffset(), k); + return BindingKey(RO.getRegion(), RO.getOffset(), k, R->getExtent()); } namespace llvm { @@ -130,6 +158,9 @@ else Out << "null"; + Out << ", \"extent\": "; + Out << K.getExtent(); + return Out; } @@ -143,7 +174,64 @@ // Actual Store type. //===----------------------------------------------------------------------===// -typedef llvm::ImmutableMap ClusterBindings; +class ClusterBindings : public llvm::ImmutableMap { +public: + ClusterBindings(const llvm::ImmutableMap &m) + : llvm::ImmutableMap(m) {} + ClusterBindings(llvm::ImmutableMap &&m) + : llvm::ImmutableMap(m) {} + +public: + const SVal *lookup(const BindingKey &K) const { + const auto lookupInBase = [this](const BindingKey &K) { + return llvm::ImmutableMap::lookup(K); + }; + + // Try to lookup the value by comparing everything. + const auto *ResVal = lookupInBase(K); + + // We might have failed to lookup the value because + // the extent of the current region is smaller than the extent + // of the stored region. In this case we try to find the + // smallest sub-region that contains the region we are searching + // for. + if (!ResVal) { + uint64_t upperBound = UINT64_MAX; + for (auto &&B : *this) { + if (K.isInsideOrEqual(B.first) && + B.first.getOffset() == K.getOffset() && + B.first.getOffset() + B.first.getExtent() <= upperBound) { + upperBound = B.first.getOffset() + B.first.getExtent(); + + ResVal = &B.second; + } + } + } + + // If we still can't get a result, we fall back to our original + // lookup strategy, when only the region and the offset is compared + // and the first result is returned. This can still yield true + // positive results in cases like this: + // + // unsigned u; + // int *x; + // (*((int *)(&x))) = (int)&u; + // *x = 1; <-- the stored extent is 32, but the extent for x is 64 + // clang_analyzer_eval(u == 1); // expected-warning{{TRUE}} + // + if (!ResVal) { + for (auto &&B : *this) { + if (K.isSameWithoutExtent(B.first)) { + ResVal = &B.second; + break; + } + } + } + + return ResVal; + } +}; + typedef llvm::ImmutableMapRef ClusterBindingsRef; typedef std::pair BindingPair; @@ -275,7 +363,9 @@ const ClusterBindings *ExistingCluster = lookup(Base); ClusterBindings Cluster = - (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap()); + (ExistingCluster + ? *ExistingCluster + : static_cast(CBFactory->getEmptyMap())); ClusterBindings NewCluster = CBFactory->add(Cluster, K, V); return add(Base, NewCluster); @@ -292,7 +382,11 @@ const ClusterBindings *Cluster = lookup(K.getBaseRegion()); if (!Cluster) return nullptr; - return Cluster->lookup(K); + + // Try looking up the value. + const auto *ResVal = Cluster->lookup(K); + + return ResVal; } const SVal *RegionBindingsRef::lookup(const MemRegion *R, Index: clang/test/Analysis/copy-elision.cpp =================================================================== --- clang/test/Analysis/copy-elision.cpp +++ clang/test/Analysis/copy-elision.cpp @@ -57,13 +57,8 @@ C() : t(T(4)) { S s = {1, 2, 3}; t.s = s; - // FIXME: Should be TRUE regardless of copy elision. clang_analyzer_eval(t.w == 4); -#ifdef ELIDE - // expected-warning@-2{{TRUE}} -#else - // expected-warning@-4{{UNKNOWN}} -#endif + // expected-warning@-1{{TRUE}} } }; Index: clang/test/Analysis/dump_egraph.cpp =================================================================== --- clang/test/Analysis/dump_egraph.cpp +++ clang/test/Analysis/dump_egraph.cpp @@ -21,7 +21,7 @@ // CHECK: \"location_context\": \"#0 Call\", \"calling\": \"T::T\", \"location\": \{ \"line\": 15, \"column\": 5, \"file\": \"{{.*}}dump_egraph.cpp\" \}, \"items\": [\l        \{ \"init_id\": {{[0-9]+}}, \"kind\": \"construct into member variable\", \"argument_index\": null, \"pretty\": \"s\", \"value\": \"&t.s\" -// CHECK: \"cluster\": \"t\", \"pointer\": \"{{0x[0-9a-f]+}}\", \"items\": [\l        \{ \"kind\": \"Default\", \"offset\": 0, \"value\": \"conj_$2\{int, LC5, no stmt, #1\}\" +// CHECK: \"cluster\": \"t\", \"pointer\": \"{{0x[0-9a-f]+}}\", \"items\": [\l        \{ \"kind\": \"Default\", \"offset\": 0, \"extent\": {{[0-9]+}}, \"value\": \"conj_$2\{int, LC5, no stmt, #1\}\" // CHECK: \"dynamic_types\": [\l      \{ \"region\": \"HeapSymRegion\{conj_$1\{S *, LC1, S{{[0-9]+}}, #1\}\}\", \"dyn_type\": \"S\", \"sub_classable\": false \}\l Index: clang/test/Analysis/expr-inspection.c =================================================================== --- clang/test/Analysis/expr-inspection.c +++ clang/test/Analysis/expr-inspection.c @@ -31,7 +31,7 @@ // CHECK: "program_state": { // CHECK-NEXT: "store": { "pointer": "{{0x[0-9a-f]+}}", "items": [ // CHECK-NEXT: { "cluster": "y", "pointer": "{{0x[0-9a-f]+}}", "items": [ -// CHECK-NEXT: { "kind": "Direct", "offset": {{[0-9]+}}, "value": "2 S32b" } +// CHECK-NEXT: { "kind": "Direct", "offset": {{[0-9]+}}, "extent": {{[0-9]+}}, "value": "2 S32b" } // CHECK-NEXT: ]} // CHECK-NEXT: ]}, // CHECK-NEXT: "environment": { "pointer": "{{0x[0-9a-f]+}}", "items": [ Index: clang/test/Analysis/store-extent-rework.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/store-extent-rework.cpp @@ -0,0 +1,41 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection,alpha.unix.cstring -verify %s + +void clang_analyzer_eval(bool); + +typedef __typeof__(sizeof(int)) size_t; +void *memset(void *dest, int ch, size_t count); + +struct Point +{ + int x; + int y; + int z; +}; + +struct Circle +{ + Point origin; + int size; +}; + +Point makePoint(int x, int y) +{ + Point result; + result.x = x; + result.y = y; + result.z = 3; + return result; +} + +void multipleDefaultOnStack() { + Circle testObj; + memset(&testObj, 0, sizeof(testObj)); + + clang_analyzer_eval(testObj.size == 0); //expected-warning{{TRUE}} + testObj.origin = makePoint(1, 2); + clang_analyzer_eval(testObj.size == 0); //expected-warning{{TRUE}} + + clang_analyzer_eval(testObj.origin.x == 1); //expected-warning{{TRUE}} + clang_analyzer_eval(testObj.origin.y == 2); //expected-warning{{TRUE}} + clang_analyzer_eval(testObj.origin.z == 3); //expected-warning{{TRUE}} +} Index: clang/test/Analysis/uninit-vals.m =================================================================== --- clang/test/Analysis/uninit-vals.m +++ clang/test/Analysis/uninit-vals.m @@ -164,15 +164,11 @@ // expected-note@-1{{TRUE}} testObj->origin = makePoint(0.0, 0.0); - if (testObj->size > 0) { ; } // expected-note{{Assuming field 'size' is <= 0}} + if (testObj->size > 0) { ; } // expected-note{{Field 'size' is <= 0}} // expected-note@-1{{Taking false branch}} - // FIXME: Assigning to 'testObj->origin' kills the default binding for the - // whole region, meaning that we've forgotten that testObj->size should also - // default to 0. Tracked by . - // This should be TRUE. - clang_analyzer_eval(testObj->size == 0); // expected-warning{{UNKNOWN}} - // expected-note@-1{{UNKNOWN}} + clang_analyzer_eval(testObj->size == 0); // expected-warning{{TRUE}} + // expected-note@-1{{TRUE}} free(testObj); } @@ -219,21 +215,17 @@ // expected-note@-1{{TRUE}} testObj->origin = makeIntPoint(1, 2); - if (testObj->size > 0) { ; } // expected-note{{Assuming field 'size' is <= 0}} + if (testObj->size > 0) { ; } // expected-note{{Field 'size' is <= 0}} // expected-note@-1{{Taking false branch}} - // expected-note@-2{{Assuming field 'size' is <= 0}} + // expected-note@-2{{Field 'size' is <= 0}} // expected-note@-3{{Taking false branch}} - // expected-note@-4{{Assuming field 'size' is <= 0}} + // expected-note@-4{{Field 'size' is <= 0}} // expected-note@-5{{Taking false branch}} - // expected-note@-6{{Assuming field 'size' is <= 0}} + // expected-note@-6{{Field 'size' is <= 0}} // expected-note@-7{{Taking false branch}} - // FIXME: Assigning to 'testObj->origin' kills the default binding for the - // whole region, meaning that we've forgotten that testObj->size should also - // default to 0. Tracked by . - // This should be TRUE. - clang_analyzer_eval(testObj->size == 0); // expected-warning{{UNKNOWN}} - // expected-note@-1{{UNKNOWN}} + clang_analyzer_eval(testObj->size == 0); // expected-warning{{TRUE}} + // expected-note@-1{{TRUE}} clang_analyzer_eval(testObj->origin.x == 1); // expected-warning{{TRUE}} // expected-note@-1{{TRUE}} clang_analyzer_eval(testObj->origin.y == 2); // expected-warning{{TRUE}} Index: clang/utils/analyzer/exploded-graph-rewriter.py =================================================================== --- clang/utils/analyzer/exploded-graph-rewriter.py +++ clang/utils/analyzer/exploded-graph-rewriter.py @@ -180,9 +180,10 @@ def __init__(self, json_sk): self.kind = json_sk['kind'] self.offset = json_sk['offset'] + self.extent = json_sk['extent'] if 'extent' in json_sk else None def _key(self): - return (self.kind, self.offset) + return (self.kind, self.offset, self.extent) def __eq__(self, other): return self._key() == other._key()