[analyzer] Upgrading RegionStore to keep track of the region extent

[isuckatcs]

Summary

The goal is to find a solution for the FIXME in RegionStoreManager::getLazyBinding(), when the default binding is overwritten and we lose information.

[NoQ]

Aha I see, this patch attempts to make multiple bindings live together at the same begin-offset when they have different size.

This is very nice progress but also there are a lot more ways in which bindings can overlap. Even if we're talking about C++ base classes, they aren't necessarily at the same offset (multiple inheritance is a thing). Then we have to figure out how to load from an offset that doesn't coincide with either of the bindings' begin-offset (need to figure out which binding is hit, and it could be that both are hit so the *freshest* binding has priority). I don't know whether incremental progress can be made here; we might need to experiment to see if there are easy strict improvements.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

115

This operator== is no longer symmetric, i.e. we can have a situation where X == Y but not Y == X. I'm worried that containers may behave very weirdly in such situation.

146

Using R->getExtent() is a clever solution, I like it! It avoids passing in the type separately.

[isuckatcs]

Trying a different approach.

[isuckatcs]

Removed the hack from RegionStoreManager::getLazyBinding().

[isuckatcs]

Minor tweaks in overlapping region lookup

[isuckatcs]

Can I get a review on this one please, just to see how far it actually is from a viable solution?

[isuckatcs]

Ping @xazax.hun @NoQ

[xazax.hun]

Hey, sorry for not responding earlier, we got a bit busy lately. I think this is a really big change and I think we might want to discuss this in more detail, do some benchmarks on open-source projects and so on.
I think the solution you proposed looks great for the specific problem you want to solve, but I want to know more whether it will have any impact on something else. Historically, we had a lot of trouble with representing conversions (e.g., accessing the same memory through pointers of different type). It would be unfortunate, if some things we want to be collapsed to be the same binding would suddenly become separate and produce unsound results. I am thinking if scenarios like looking at an object as if it was an array of bytes and using different lengths of arrays.

clang/test/Analysis/array-init-loop.cpp

170 ↗

(On Diff #457801)

How do we feel about this change?

clang/test/Analysis/uninit-structured-binding-array.cpp

202 ↗

(On Diff #457801)

What is the reason of deleting this test case? Or was it just too similar to the one before it?

clang/test/Analysis/uninit-structured-binding-struct.cpp

15 ↗

(On Diff #457801)

Are we OK with losing these warnings?

[isuckatcs]

Hey, sorry for not responding earlier, we got a bit busy lately. I think this is a really big change and I think we might want to discuss this in more detail, do some benchmarks on open-source projects and so on.

No worries, I also looked at the problem again in the past couple of days and I'm not happy with this solution yet. It seems to work but I don't like that we fall back to the original lookup strategy. I'm investigating a
different approach and I already started working on a discourse post where I discuss the problem we are facing with extents and a solution (which I still haven't entirely figured out).

we had a lot of trouble with representing conversions (e.g., accessing the same memory through pointers of different type)

This is also something I ran into recently. See #62822. I'm also not sure how to deal with it when extents are there.

Snippet:
  int x = 1024;
  *((char *)&x) = 0;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

Imagine that the next statement is int y = x;.

Snippet:
  int x = 1024;
  *((char *)&x) = 0;
  int y = x;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

We are looking up {"kind": "Default", "offset": 0, "extent": 32} and by looking at the store you would say we have 1 initialized and 3 uninitialized bytes, so the value is Undefined,
however in reality we had 4 initialized bytes, where the last one was changed, but since we don't implement SVal slicing, I think we should return Unknown (even though in this example the value
doesn't actually changes).

But what about this scenario:

Snippet:
  char x = 0;
  int y = *((int *)&x);
Store:
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 0 S8b}

We are looking up {"kind": "Default", "offset": 0, "extent": 32} again, however this time the value should be Undefined. I'm experimenting with returning Unknown it both cases,
even though it's not correct.

Overlapping values are tricky, even leaving both of them in the store would make it difficult to reason about them. Consider these examples:

Snippet:
  int x = 1024;
  *((char *)&x) = 1;

  int y = x;
  char z = *((char *)&x);
Store:
  {"kind": "Direct", "offset": 0, "extent": 32 value: 1024 S32b}
  {"kind": "Direct", "offset": 0, "extent": 8, "value": 1 S8b}

Here z is 1 and y is Unknown (1025 in reality but again we can't handle this yet).

Snippet:
  char x = 1;
  *((int *)&x) = 1024;

  int y = *((int *)&x);
  char z = x;
Store:
  {"kind": "Direct", "offset": 0, "extent": 8 value: 1 S8b}
  {"kind": "Direct", "offset": 0, "extent": 32 value: 1024 S32b}

Here z should be 0 and y should be 1024 (at least pretend that).

Region store however can't track which binding was created first since it uses a map as a representation and even if it had timestamps you would need to keep track of all the overlaping regions and
figure out which region is valid and which has been modified.

clang/test/Analysis/array-init-loop.cpp

170 ↗

(On Diff #457801)

I think we want the warning to appear as it used to be. Sadly I modified this patch since then, but with my current version, when I tried to reproduce this, the analyzer crashed due to a source location issue, so I leave this comment here to investigate it later.

warning: Value assigned to field 'i' in implicit constructor is garbage or undefined [core.uninitialized.Assign]
struct S3 {
       ^
note: Calling implicit copy constructor for 'S3'
clang++: llvm-project/clang/lib/Frontend/TextDiagnostic.cpp:1019: void highlightRange(const clang::CharSourceRange&, unsigned int, clang::FileID, const {anonymous}::SourceColumnMap&, std::string&, const clang::SourceManager&, const clang::LangOptions&): Assertion `StartColNo <= EndColNo && "Invalid range!"' failed.

clang/test/Analysis/uninit-structured-binding-array.cpp

202 ↗

(On Diff #457801)

It's been a while, so I don't remember my exact motives here. It seems like this test case has been combined with the previous one, so both a and c are checked in the same test case after the change.

clang/test/Analysis/uninit-structured-binding-struct.cpp

15 ↗

(On Diff #457801)

We're not losing it, but I want to check if both i and j are Undefined and after the assigment, the analyzer bails out, so I would need to create a different test case to check it for j too.

[isuckatcs]

Trying a more consistent approach.

[isuckatcs]

clang/test/Analysis/casts.c

162 ↗

(On Diff #524906)

Please see my comment under the original patch for explanation.

clang/test/Analysis/cxx-uninitialized-object-ptr-ref.cpp

292 ↗

(On Diff #524906)

I think this is an issue with the checker. I analyze the problem in a comment in the original revision, please see that for explanation.

clang/test/Analysis/pr22954.c

830 ↗

(On Diff #524906)

Here we actually read 1 byte from a place in memory to which we assigned 4 bytes (memory slicing happens). If instead of 11, we assigned a value that cannot be represented on 1 byte, this would be a false positive.

868 ↗

(On Diff #524906)

Same as above.

clang/test/Analysis/pr37802.cpp

26 ↗

(On Diff #524906)

As we don't know what this snippet does and it cannot be executed, I don't know if this warning is correct or not.

Note that this infinitely recursive function should be invoked:

Z g() {
  Z az = g();
  Z e = az;
  Y d;
  e.au(d);
}

74 ↗

(On Diff #524906)

Same as above.

clang/test/Analysis/uninit-structured-binding-struct.cpp

15 ↗

(On Diff #457801)

For the record, the warning is lost because the core checkers have been disabled and this comes from core.uninitialized.Assign.

[isuckatcs]

Rebased

[isuckatcs]

Rebased*

[isuckatcs]

Fixed the issue which caused the patch to fail CI

[isuckatcs]

Added a logic that helps us reason about these snippets:

struct S {
  char a;
  char b;
  char c;
  char d;
};

void everyByteInitialized() {
  S s = {1, 2, 3, 4};
  int x = *((int *)&s);

  // FIXME: Every byte inside 'x' is initialized, we just can't concatenate them.
  clang_analyzer_eval(x); //expected-warning{{UNKNOWN}}
}

void someGarbageBytes() {
  S s;
  s.a = 1;
  s.b = 2;
  s.d = 4;

  // Here one byte of 'x' is a garbage value.
  int x = *((int *)&s); //expected-warning{{Assigned value is garbage or undefined}}
  (void) x;
}

[isuckatcs]

Updated

[isuckatcs]

clang/test/Analysis/array-init-loop.cpp

170 ↗

(On Diff #457801)

Edit: this warning disappeared only due to disabling the core checkers in this test file

clang/test/Analysis/array-punned-region.c

24 ↗

(On Diff #526283)

An explanation can be found in my comment under the patch that added this test case.

[isuckatcs]

Updated

[isuckatcs]

Updated

[isuckatcs]

Addressed the issues related to this snippet:

void issue() {
  int x = 0x01020304;
  *((char *)&x + 1) = 1;

  int y = x;
}

[isuckatcs]

The false positive issue due to bindings getting removed has been mitigated by only removing bindings if we are binding a symbolic region, or the store contains a symbolic region. We are good at handling overlapping non-symbolic bindings.

[steakhal]

Thanks for the proof of concept implementation. It was really thoughtful and constructive.
This will improve the store by a long shot if finished.
This implementation would fix a lot of FN cases in our testsuite.
However, it also introduces some new reports, and those are primarily FPs as far as I can tell.

I'll refer to my comment on the RFC for explaining how we think extents should work.

clang/lib/StaticAnalyzer/Core/MemRegion.cpp

1621–1629

On our testbench we encountered a really rare crash, where Ty was a dependent type.
Given how rare it was and that the given TU had parsing errors it probably not affects regular CSA users, but let's be on the safe side and guard our code against dependent types as well.

When I reduced the case I had this:

} // <-- This needs to be here :D
template <typename a> void b(a); // <-- This shouldn't have a body.
void c() {
  b([](auto d) {
    static auto a(d);
    a;
  });
}

This code is likely not too useful for you, but I'll leave it here for history.

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

112

How about this one: std::tie(Data, Extent) < std::tie(X.Data, X.Extent)

TBH I'm not sure why it's not std::tie(P.getOpaqueValue(), Data, Extent) < std::tie(...) in the first place.

347–356

We should probably also count this as well:

[        B1         ][    B2     ]
          [       K         ]

1639

I'm not really sure why we need to look up a partial binding here.
I wonder what will be the result for a code like this:

struct A {
  int x;
  int y;
};

struct B {
  int z;
  A a;
};

struct C {
  B b;
  int x;
};

void top() {
  C c{}; // bind zero default
  B b{1, {2, 3}};
  c.b = b;
  A a = c.b.a;
  // b:
  // [ dir: 1 | dir: 2 | dir: 3 ]

  // c:
  // [        def: 0         ]
  // [ def: lcv(b) ]

  // a:
  // [ def: lcv(c.b.a) ]
  clang_analyzer_dump(a.x); // I would expect "1" here but I got "0" with this patch.
}

2058–2073

I'm so happy to see this going away.

[isuckatcs]

• Added the contains() and overlapsWith() methods to BindingKey.
• Implemented the proposed Store to binding B ([start, end]) with the modifications discussed in the RFC.
• The store implementation is scattered across different places, which needs to be cleaned up
• Added one more test case, which used to be a false positive

[isuckatcs]

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

112

I'm not sure if creating 2 tuples is more efficient than calling a ternary operator.

TBH I'm not sure why it's not std::tie(P.getOpaqueValue(), Data, Extent) < std::tie(...) in the first place.

Well, I don't use std::tuple<> that much, so I wasn't aware that it's operator< does exactly what this piece of code does. This however is also a con against std::tie(), because it might lead to people, who are not familiar with how std::tuple<> comparison works (like I was) being confused about what happens here.

I don't mark this comment as done, as I'm still considering using std::tie() instead of this.

1639

I'm not really sure why we need to look up a partial binding here.

I'm not sure either. I think this is an artifact, that has been added here accidentally. I'll remove it in the next update.

I wonder what will be the result for a code like this:

That snippet indeed resulted in a false value, which has been fixed by the new add method. I added the snippet as a testcase, however note that a.x should be 2 at the point of the dumping. See on godbolt.

[isuckatcs]

Updated

[isuckatcs]

Cleaned up the patch a bit

[isuckatcs]

clang/test/Analysis/bstring_UninitRead.c

34 ↗

(On Diff #530062)

@steakhal
So we no longer have the FP for the mempcpy, and leaves me wonder why is the diag for clang_analyzer_eval still missing?
In any case, the comment there should be updated.

This is a good catch. The reason is that debug.ExprInspection is not enabled for this source file for some reason.

54 ↗

(On Diff #530062)

@steakhal
Same here as in the previous mempcpy14 case.

Same as above.

clang/test/Analysis/casts.c

159–167 ↗

(On Diff #530062)

@steakhal
I think we could take this opportunity to get rid of these macros and use different -verify=xxx suffixes for 32 and 64 bit systems. It should be possible, because only the outputs should be different in the test for the same code across different RUN lines.

clang/test/Analysis/cxx-uninitialized-object-ptr-ref.cpp

291–298 ↗

(On Diff #530062)

@steakhal
At first glance, it looks fine.
I think in the abstract machine it's valid to dereference the value ptr.
So, I think we don't need a FIXME there, but @Szelethus probably can judge this better.

clang/test/Analysis/cxx-uninitialized-object.cpp

869–882 ↗

(On Diff #530062)

@steakhal
Oh, now that is confusing :D So, the checker counts the members of the functor there.
Put here a FIXME if you want.

clang/test/Analysis/misc-ps-region-store.m

799–806 ↗

(On Diff #530062)

@steakhal
I'm surprised about this one.

Generally, we cannot depend on the initializers of local statics, as this function might have been already called once, and changed the variable, or worse, escaped its address and something magical wrote there something brand new since that.

So, if we had an assignment before loading for the condition, we should track the assigned value; but we cannot trust the initializer.
Consequently, this test case was simply wrong and now works as it should.

BTW this might be related to D139534, but only now surfaces.

clang/test/Analysis/pr22954.c

912–914 ↗

(On Diff #530062)

@steakhal
Isn't this fixed by this patch?

Well, it says it should be UNKNOWN or FALSE, however because it might turn FALSE in the future, I left the fixme here.

clang/test/Analysis/pr37802.cpp

6–28 ↗

(On Diff #530062)

@steakhal
lol, what's going on here? Did you check if this is actually a TP?
Anyway, is probably fine 😅

I have no idea what this is and I cannot run it either because of the reasons in the above comment. 😅

[isuckatcs]

Cleanup

[isuckatcs]

Improved the way MemRegion::getExtent() calculates the extents.

[isuckatcs]

Updated

[isuckatcs]

clang/test/Analysis/misc-ps-region-store.m

799–806 ↗

(On Diff #530062)

This happened because of some issues about calculating the flexible array member extent, nothing wrong with the original patch I think.

[isuckatcs]

Updated how bindings are added to the store.

It turned out there was a different kind of problem with this snippet:

struct rdar_7515938 {
  int x;
  int y[];
};

const struct rdar_7515938 *rdar_7515938(void) {
  static const struct rdar_7515938 z = { 0, { 1, 2 } };
  if (z.y[0] != 1) {
    int *p = 0;
    *p = 0xDEADBEEF; // no-warning
  }
  return &z;
}

These are the bindings that are added to the store in order:

"kind": "Direct", "offset": 0, "extent": 32 0 S32b
-----------------------------------------------
"kind": "Direct", "offset": 32, "extent": 32 1 S32b
-----------------------------------------------
"kind": "Direct", "offset": 64, "extent": 32 2 S32b
-----------------------------------------------
"kind": "Default", "offset": 32, "extent": 9223372036854775807 0 S32b

The Default binding removes the bindings with the value of 1 and 2 from the store.
This is probably some issue with the checker, but for now addition is changed so that a
Default binding cannot remove Direct bindings...

[isuckatcs]

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

[steakhal]

In D132752#4417084, @isuckatcs wrote:

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

I run it, but now the challenge is to share the reproducers in some form to let you investigate them.
However, I use our frontend so the reproducers are in a specific form. Consequently, you wouldn't be able to reduce it.
So, I have to reduce them; but we are speaking of ~8 reproducers.
I'll think about how to do this efficiently on Monday.
But one should note that it's difficult to dedicate time.

[steakhal]

In D132752#4428402, @steakhal wrote:

In D132752#4417084, @isuckatcs wrote:

@steakhal the patch is ready for a run. Can you please test it on IRL projects?

I run it, but now the challenge is to share the reproducers in some form to let you investigate them.
However, I use our frontend so the reproducers are in a specific form. Consequently, you wouldn't be able to reduce it.
So, I have to reduce them; but we are speaking of ~8 reproducers.
I'll think about how to do this efficiently on Monday.
But one should note that it's difficult to dedicate time.

I picked randomly some files for which we had differences. Mostly new uninit read reports.

preprocessed_reproducers.zip2 MBDownload

Clang/clang/lib/AST/APValue.cpp:240 New: Argument to 'delete[]' is uninitialized
Clang/clang/lib/AST/APValue.cpp:249 New: Undefined or garbage value returned to caller
cataclysm-dda/src/npc_class.cpp:472 New: Potential memory leak
cataclysm-dda/src/npc_class.cpp:481 New: Potential memory leak
fmt/test/chrono-test.cc:230 New: The right operand of '==' is a garbage value
git/builtin/log.c:1785 New: 1st function call argument is an uninitialized value
HHVM/hphp/runtime/vm/native.cpp:112 New: Assigned value is garbage or undefined
linux-drivers/drivers/infiniband/hw/qedr/main.c:977 Absent: Assigned value is garbage or undefined

I usually use something like this for the interestingness test for reducing with creduce:

#!/bin/bash

set -e

SCRIPT_DIR=$( cd -- "$( dirname -- "${BASH_SOURCE[0]}" )" &> /dev/null && pwd )

# We had no issues like that, nor were parsing errors.
bash -c "${SCRIPT_DIR}/../old-clang -c -o /dev/null preprocessed_APValue.cpp \
  --analyze -Xclang -analyzer-checker=core --analyzer-output text-minimal \
  2>&1 | grep --extended-regexp \"(warning: Argument to 'delete\[\]' is uninitialized)|(error)\" | wc -l | grep '^0$'" &

# A new issue appeared.
bash -c "${SCRIPT_DIR}/../new-clang -c -o /dev/null preprocessed_APValue.cpp \
  --analyze -Xclang -analyzer-checker=core --analyzer-output text-minimal \
  2>&1 | grep --extended-regexp \"(warning: Argument to 'delete\[\]' is uninitialized)\" | wc -l | grep '^1$'" &

# Wait for the fastest job to early-return on error; otherwise wait for all jobs.
myjobs="$(jobs -p)"
for i in $myjobs; do
  if ! wait -n $myjobs 2>/dev/null; then
    kill -KILL $myjobs 2>/dev/null
    exit 1
  fi
done

[isuckatcs]

I started looking at the preprocessed examples, however there are some that I either can't compile or I can't reproduce.

APValue.cpp      <-- managed to reproduce and reduce
npc_class.cpp    <-- can't reproduce
chrono-test.cc   <-- managed to reproduce and reduce
log.c            <-- only gcc compiles it, and scan-build doesn't work either
native.cpp       <-- can't compile
main.c           <-- managed to reproduce and reduce

These are the reproduced snippets:

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}

// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}

// main
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

I need to allocate more time to investigate them, but all of the differences between the old analyzer and the one using this store
look wrong so far.

For the ones I failed to reduce can you please provide, which clang invocation was used?

[steakhal]

In D132752#4441206, @isuckatcs wrote:

I started looking at the preprocessed examples, however there are some that I either can't compile or I can't reproduce.

APValue.cpp      <-- managed to reproduce and reduce
npc_class.cpp    <-- can't reproduce
chrono-test.cc   <-- managed to reproduce and reduce
log.c            <-- only gcc compiles it, and scan-build doesn't work either
native.cpp       <-- can't compile
main.c           <-- managed to reproduce and reduce

These are the reproduced snippets:

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}

// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}

// main
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

I need to allocate more time to investigate them, but all of the differences between the old analyzer and the one using this store
look wrong so far.

Thanks for your time.

For the ones I failed to reduce can you please provide, which clang invocation was used?

I must admit that since our infra is suited for our tool, I used our fork (while backporting this patch to it). On our fork, we accept parsing errors or similar things if they don't affect directly the Static Analyzer.
This basically means that we select top-level functions without parsing errors and if we encounter a call to a function that has parsing errors, we just conservative eval call of that function instead of trying to inline it.
Usually, this doesn't have an effect to the results, hence the minimal repro would/should still apply to the upstream-clang as well - it's just harder to get there :D

I didn't check for parsing errors prior to submitting these files, so that's my bad.
I don't have an ETA for coming back to reduce those cases myself. A weak maybe is 1.5-2 weeks.

[isuckatcs]

I started looking at the reduced snippets and it seems I was too hasty to say they are false positives. All of them look correct after analyzing them.

APValue

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}

preprocessed_APValue.cpp:9:14: warning: Argument to 'delete[]' is uninitialized [core.CallAndMessage]
  void d() { delete[] g; }
             ^~~~~~~~~~

This first one is correct. class a has only 1 data member, int c, so on x86 sizeof(a) == 32. a::b has one int * member, so on x86 sizeof(b) == 64.
b f = *(b *)&c; takes the address of a 32 bit variable, and treats it as a 64 bit variable, so when the pointer is dereferenced, 64 bits are read, out of
which only 32 is initialized.

This is the performed lookup:

Key: "kind": "Direct", "offset": 0, "extent": 64
{"kind": "Direct", "offset": 0, "extent": 32, "value": derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}}
Overlapping bindings:
{
    derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}
    Undefined
}

The question is, why it isn't reported at the moment of the assigment instead. If the i386-pc-linux-gnu triple is used, the warning is not reported.

chrono-test

// chrono-test
struct a {
  int b;
  int c;
  int d;
};

int e;

auto f(a h) -> bool {
  e == h.d;
  a g;
  f(g);
}

This one is also correct. g is an aggregate type on the stack, so all of it's members contain some garbage values. Then g is passed to f(), which
reads one of it's uninitialized fields.

This is the full bugpath:

preprocessed_chrono-test.cc:8:5: warning: The right operand of '==' is a garbage value [core.UndefinedBinaryOperatorResult]
  e == h.d;
    ^
preprocessed_chrono-test.cc:8:3: note: Assuming 'e' is not equal to field 'd'
  e == h.d;
  ^~~~~~~~
preprocessed_chrono-test.cc:9:3: note: 'g' initialized here
  a g;
  ^~~
preprocessed_chrono-test.cc:10:5: note: Uninitialized value stored to 'h.d'
  f(g);
    ^
preprocessed_chrono-test.cc:10:3: note: Calling 'f'
  f(g);
  ^~~~
preprocessed_chrono-test.cc:8:5: note: The right operand of '==' is a garbage value
  e == h.d;
    ^  ~~~

main

// main.c
char a, b;

void c() {
  char d[2];
  *(int *)d = a;
  b = d[1];
}

Here the warning disappeared because a has a symbolic value. Then this symbolic value is assigned to d, and later we read one byte from it,
so the result is considered Unknown.

This is the performed lookup:

Key: "kind": "Direct", "offset": 8, "extent": 8
{"kind": "Direct", "offset": 0, "extent": 32, "value": reg_$0<char a>}
Overlapping bindings:
{
    reg_$0<char a>
}

Before this patch we reported a warning, because the lookup starts at offset 8, not at offset 0.

[steakhal]

Thanks for the investigation.

In D132752#4444678, @isuckatcs wrote:

I started looking at the reduced snippets and it seems I was too hasty to say they are false positives. All of them look correct after analyzing them.

// APValue.cpp
class a {
  struct b;
  int c;
  a(const a &);
};

struct a::b {
  int *g;
  void d() { delete[] g; }
};

a::a(const a &e) {
  *this = a(e);
  b f = *(b *)&c;
  f.d();
}

preprocessed_APValue.cpp:9:14: warning: Argument to 'delete[]' is uninitialized [core.CallAndMessage]
  void d() { delete[] g; }
             ^~~~~~~~~~

This first one is correct. class a has only 1 data member, int c, so on x86 sizeof(a) == 32. a::b has one int * member, so on x86 sizeof(b) == 64.
b f = *(b *)&c; takes the address of a 32 bit variable, and treats it as a 64 bit variable, so when the pointer is dereferenced, 64 bits are read, out of
which only 32 is initialized.

This is the performed lookup:

Key: "kind": "Direct", "offset": 0, "extent": 64
{"kind": "Direct", "offset": 0, "extent": 32, "value": derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}}
Overlapping bindings:
{
    derived_$5{conj_$2{int, LC5, S1498, #1},temp_object{a, S1498}.c}
    Undefined
}

The question is, why it isn't reported at the moment of the assigment instead. If the i386-pc-linux-gnu triple is used, the warning is not reported.

I think I would agree if I would only look at the reduced case. However, I think it's highly unlikely that such a widely used type as APValue has this sort of bug. Note that it's being used everywhere, the whole constexpr interpreter is based around that.
So, my guess is that it reduced into a different case. I'd recommend to have tighter constraints during reduction. Maybe match the whole sequence of notes (masking the locations, but keeping the order and content) using some fancy regex.

I haven't looked at the rest, but given that the reduction produced a different case than we began with, I'd say it's likely to happen for the rest of the cases as well.
For example, IMO it's similarly unlikely to find (such a banal) bug in gtest or git TBH.

To conclude, I appreciate the effort, but I'm afraid it's going to be more effort to understand why we have the new reports.
I do think we need better tools for such investigations, but unfortunately I don't have anything helpful for such tricky-to-reduce cases.
I think if anyone has ideas what tooling or techniques can help to uncover such questions, let's gather those ideas in a discuss thread.

[isuckatcs]

I think I would agree if I would only look at the reduced case. However, I think it's highly unlikely that such a widely used type as APValue has this sort of bug. Note that it's being used everywhere, the whole constexpr interpreter is based around that.

I tried reducing it with the method you suggested (matching the whole error path), however that was incredibly slow (~2% after 2 hours). Instead I started logging what happens in the store and checked the results. After a while we end up with this in
the environment: "pretty": "this->PathPtr", "value": "Undefined".

I reverted almost all of the changes and I found that before the checker reports the warning, we perform this lookup:

Lookup key: "kind": "Default", "offset": 64, "extent": 512 region: temp_object{APValue, S1124035}
{"kind": "Default", "offset": 64, "extent": 128 value: lazyCompoundVal{0x5581c0cecc00,B}}
{"kind": "Direct", "offset": 0, "extent": 32 value: 0 U32b}
{"kind": "Direct", "offset": 192, "extent": 64 value: 0 S64b}
{"kind": "Direct", "offset": 256, "extent": 32 value: 4294967295 U32b}

Note that with the current store, this would fail but without the extents it returns lazyCompoundVal{0x5581c0cecc00,B}, where B is coming from here: APValue::setLValueUninit(LValueBase B, ...), so we basically confuse the structures.

One more thing worths mentioning is that the variable from which we report the warning (delete [] PathPtr;) is inside a union, which we don't model AFAIK.

union {
  LValuePathEntry Path[InlinePathSpace];
  LValuePathEntry *PathPtr;
};

Now let's take a closer look to the piece of code, from which the warning comes.

struct LVBase {
   ...
  unsigned PathLength;
  ...
};

struct APValue::LV : LVBase {
  ...
  LV() { PathLength = (unsigned)-1; }
  ...
}

struct APValue {
  ...
  typedef llvm::AlignedCharArrayUnion<void *, APSInt, APFloat, ComplexAPSInt,
                                      ComplexAPFloat, Vec, Arr, StructData,
                                      UnionData, AddrLabelDiffData> DataType;
  DataType Data;
  ...
}

void APValue::MakeLValue() {
  ...
  new ((void *)(char *)&Data) LV();
  ...
}

bool hasPath() const { return PathLength != (unsigned)-1; }

bool APValue::hasLValuePath() const {
  ...
  return ((const LV *)(const char *)&Data)->hasPath();
}

case LValue:
    MakeLValue();             <-- PathLength == -1, set in ctor
    if (RHS.hasLValuePath())  <-- PathLength == -1, we fail to evaluate the condition
      setLValue(...);         <-- warning comes from here

So, basically we fail to read a value from a union properly, which causes us to enter a branch, we should not enter otherwise.

I also extracted a reproducer, which interestingly fails with our current implementation too. See on godbolt.
My conclusion is that this bug wasn't introduced by this patch, it was just hidden before.

cc: @NoQ @xazax.hun

[isuckatcs]

For chrono-test, the lines that prevented us from reporting a warning were these:

if (Result.isUndef())
    Result = UnknownVal();

From the source code that caused the issue, I extracted this reproduce:

using time_t = long int;
extern struct tm *gmtime_r(const time_t *__restrict __timer,
                           struct tm *__restrict __tp) throw();
extern void abort() __attribute__((__noreturn__));

struct tm {
  int tm_sec;
  int tm_min;
  int tm_hour;
};

inline tm gmtime(time_t time) {
  struct dispatcher {
    time_t time_;
    tm tm_;

    dispatcher(time_t t) : time_(t) {}

    bool run() { return gmtime_r(&time_, &tm_) != nullptr; }
  };

  dispatcher gt(time);

  if (!gt.run())
    abort();
  return gt.tm_;
}

void foo() {
  auto rhs = gmtime(0xDEADBEEF);
  int x = rhs.tm_sec;
  (void)x;
}

Note that struct tm has 3 members. If I reduce it down to 1 (let small struct binding policy happen), the current clang also reports the warning.
See on godbolt.

Upon taking a closer look it can be seen that dispatcher has a tm member, however it's not initialized explicitly and it's an aggregate, so no
constructor will be run either. Later this tm is returned by gmtime().

The only catch I see here is that gmtime_r() takes a non-const pointer to tm_, which means it could initialize it. But since the current clang
also reports a warning for this struct, this is probably just another case we fail to handle elsewhere.

cc: @NoQ @xazax.hun

[isuckatcs]

I dug deeper into the missing warning too. Below is the snippet that it comes from:

void ether_addr_copy(u8 *dst, const u8 *src)
{
 *(u32 *)dst = *(const u32 *)src;
 *(u16 *)(dst + 4) = *(const u16 *)(src + 4);
}

static void qedr_mac_address_change(struct qedr_dev *dev)
{
 ...
 u8 mac_addr[6];
 ...
 ether_addr_copy(&mac_addr[0], dev->ndev->dev_addr);
 guid[0] = mac_addr[0] ^ 2;
 guid[1] = mac_addr[1];          <-- warning emitted here
 ...
}

This is how the store looks like at this point:

{ 
"cluster": "mac_addr", "pointer": "0x5634ab4d0190", "items": [
      { "kind": "Direct", "offset": 0, "value": "reg_$20<unsigned int Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},0 S64b,unsigned int}>" },
      { "kind": "Direct", "offset": 32, "value": "reg_$21<unsigned short Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},2 S64b,unsigned short}>" }
    ]
}

mac_addr[1] is at offset 8, so here we fail to read a partial value.

With the extends added by this patch, the store looks like this:

{ 
"cluster": "mac_addr", "pointer": "0x564c40a59ce8", "items": [
      { "kind": "Direct", "offset": 0, "extent": 32, "value": "reg_$20<unsigned int Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},0 S64b,unsigned int}>" },
      { "kind": "Direct", "offset": 32, "extent": 16, "value": "reg_$21<unsigned short Element{SymRegion{reg_$19<const unsigned char * Element{SymRegion{reg_$4<struct net_device * Element{SymRegion{reg_$1<struct qedr_dev * dev>},0 S64b,struct qedr_dev}.ndev>},0 S64b,struct net_device}.dev_addr>},2 S64b,unsigned short}>" }
    ]
}

Here it seems like, the false result is the one, that the current clang reports.

cc: @NoQ @xazax.hun

clang/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h

public:
 
   bool hasStackNonParametersStorage() const;
 
   bool hasStackParametersStorage() const;
 
   /// 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;
 
   virtual void dumpToStream(raw_ostream &os) const;
 
   void dump() const;
 
   /// Returns true if this region can be printed in a user-friendly way.

clang/lib/StaticAnalyzer/Core/MemRegion.cpp

 }
 
 RegionOffset MemRegion::getAsOffset() const {
   if (!cachedOffset)
     cachedOffset = calculateOffset(this);
   return *cachedOffset;
 }
 
+uint64_t MemRegion::getExtent() const {
+  const MemRegion *R = this;
+  uint64_t Extent = 0;
+
+  if (const auto *TVR = dyn_cast<TypedValueRegion>(R)) {
+    const auto Ty = TVR->getDesugaredValueType(getContext());
+    if (!Ty->isIncompleteType())
+      Extent = getContext().getTypeSize(Ty);
+  } else if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
+    const auto Ty = SR->getSymbol()->getType().getDesugaredType(getContext());
+    if (!Ty->isIncompleteType())
+      Extent = getContext().getTypeSize(Ty);
+  }
+
+  return Extent;
+}
+
 //===----------------------------------------------------------------------===//
 // BlockDataRegion
 //===----------------------------------------------------------------------===//
 
 std::pair<const VarRegion *, const VarRegion *>
 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
   MemRegionManager &MemMgr = getMemRegionManager();
   const VarRegion *VR = nullptr;
   const VarRegion *OriginalVR = nullptr;
 
   if (!VD->hasAttr<BlocksAttr>() && VD->hasLocalStorage()) {
     VR = MemMgr.getNonParamVarRegion(VD, this);
     OriginalVR = MemMgr.getVarRegion(VD, LC);
   }
   else {
     if (LC) {

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

 class BindingKey {
 public:
   enum Kind { Default = 0x0, Direct = 0x1 };
 private:
   enum { Symbolic = 0x2 };
 
   llvm::PointerIntPair<const MemRegion *, 2> 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<uintptr_t>(Base)) {
+  explicit BindingKey(const SubRegion *r, const SubRegion *Base, Kind k,
+                      uint64_t extent)
+      : P(r, k | Symbolic), Data(reinterpret_cast<uintptr_t>(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<ObjCIvarRegion, CXXDerivedObjectRegion>(r)) &&
            "Not a base");
   }
+
 public:
 
   bool isDirect() const { return P.getInt() & Direct; }
   bool hasSymbolicOffset() const { return P.getInt() & Symbolic; }
 
   const MemRegion *getRegion() const { return P.getPointer(); }
   uint64_t getOffset() const {
     assert(!hasSymbolicOffset());
     return Data;
   }
 
+  uint64_t getExtent() const { return Extent; }
+
   const SubRegion *getConcreteOffsetRegion() const {
     assert(hasSymbolicOffset());
     return reinterpret_cast<const SubRegion *>(static_cast<uintptr_t>(Data));
   }
 
   const MemRegion *getBaseRegion() const {
     if (hasSymbolicOffset())
       return getConcreteOffsetRegion()->getBaseRegion();
     return getRegion()->getBaseRegion();
   }
 
   void Profile(llvm::FoldingSetNodeID& ID) const {
     ID.AddPointer(P.getOpaqueValue());
     ID.AddInteger(Data);
+    ID.AddInteger(Extent);
   }
 
   static BindingKey Make(const MemRegion *R, Kind k);
 
   bool operator<(const BindingKey &X) const {
     if (P.getOpaqueValue() < X.P.getOpaqueValue())
       return true;
     if (P.getOpaqueValue() > X.P.getOpaqueValue())
       return false;
     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
 
 BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
   const RegionOffset &RO = R->getAsOffset();
   if (RO.hasSymbolicOffset())
-    return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k);
+    return BindingKey(cast<SubRegion>(R), cast<SubRegion>(RO.getRegion()), k,
+                      R->getExtent());
 
-  return BindingKey(RO.getRegion(), RO.getOffset(), k);
+  return BindingKey(RO.getRegion(), RO.getOffset(), k, R->getExtent());
 }
 
 namespace llvm {
 static inline raw_ostream &operator<<(raw_ostream &Out, BindingKey K) {
   Out << "\"kind\": \"" << (K.isDirect() ? "Direct" : "Default")
       << "\", \"offset\": ";
 
   if (!K.hasSymbolicOffset())
     Out << K.getOffset();
   else
     Out << "null";
 
+  Out << ", \"extent\": ";
+  Out << K.getExtent();
+
   return Out;
 }
 
 } // namespace llvm
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void BindingKey::dump() const { llvm::errs() << *this; }
 #endif
 
 //===----------------------------------------------------------------------===//
 // Actual Store type.
 //===----------------------------------------------------------------------===//
 
-typedef llvm::ImmutableMap<BindingKey, SVal>    ClusterBindings;
+class ClusterBindings : public llvm::ImmutableMap<BindingKey, SVal> {
+public:
+  ClusterBindings(const llvm::ImmutableMap<BindingKey, SVal> &m)
+      : llvm::ImmutableMap<BindingKey, SVal>(m) {}
+  ClusterBindings(llvm::ImmutableMap<BindingKey, SVal> &&m)
+      : llvm::ImmutableMap<BindingKey, SVal>(m) {}
+
+public:
+  const SVal *lookup(const BindingKey &K) const {
+    const auto lookupInBase = [this](const BindingKey &K) {
+      return llvm::ImmutableMap<BindingKey, SVal>::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<BindingKey, SVal> ClusterBindingsRef;
 typedef std::pair<BindingKey, SVal> BindingPair;
 
 typedef llvm::ImmutableMap<const MemRegion *, ClusterBindings>
         RegionBindings;
 
 namespace {
 class RegionBindingsRef : public llvm::ImmutableMapRef<const MemRegion *,
for (iterator I = begin(); I != end(); ++I) {
       --Space;
       Indent(Out, Space, IsDot) << "]}";
       if (std::next(I) != end())
         Out << ',';
       Out << NL;
     }
   }
 
   LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); }
 };
 } // end anonymous namespace
 
 typedef const RegionBindingsRef& RegionBindingsConstRef;
 
 Optional<SVal> RegionBindingsRef::getDirectBinding(const MemRegion *R) const {
   return Optional<SVal>::create(lookup(R, BindingKey::Direct));
 }
 
 Optional<SVal> RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {
   return Optional<SVal>::create(lookup(R, BindingKey::Default));
 }
 
 RegionBindingsRef RegionBindingsRef::addBinding(BindingKey K, SVal V) const {
   const MemRegion *Base = K.getBaseRegion();
 
   const ClusterBindings *ExistingCluster = lookup(Base);
   ClusterBindings Cluster =
-      (ExistingCluster ? *ExistingCluster : CBFactory->getEmptyMap());
+      (ExistingCluster
+           ? *ExistingCluster
+           : static_cast<ClusterBindings>(CBFactory->getEmptyMap()));
 
   ClusterBindings NewCluster = CBFactory->add(Cluster, K, V);
   return add(Base, NewCluster);
 }
 
 
 RegionBindingsRef RegionBindingsRef::addBinding(const MemRegion *R,
                                                 BindingKey::Kind k,
                                                 SVal V) const {
   return addBinding(BindingKey::Make(R, k), V);
 }
 
 const SVal *RegionBindingsRef::lookup(BindingKey K) const {
   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,
                                       BindingKey::Kind k) const {
   return lookup(BindingKey::Make(R, k));
 }
 
 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {

 ///
 /// Note that unlike RegionStoreManager::findLazyBinding, this will not search
 /// for lazy bindings for super-regions of \p R.
 static Optional<nonloc::LazyCompoundVal>
 getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B,
                        const SubRegion *R, bool AllowSubregionBindings) {
   Optional<SVal> V = B.getDefaultBinding(R);
   if (!V)
     return None;
 
   Optional<nonloc::LazyCompoundVal> LCV = V->getAs<nonloc::LazyCompoundVal>();
   if (!LCV)
     return None;
 
   // If the LCV is for a subregion, the types might not match, and we shouldn't
   // reuse the binding.
   QualType RegionTy = getUnderlyingType(R);
SVal RegionStoreManager::getLazyBinding(const SubRegion *LazyBindingRegion,
                                         RegionBindingsRef LazyBinding) {
   SVal Result;
   if (const ElementRegion *ER = dyn_cast<ElementRegion>(LazyBindingRegion))
     Result = getBindingForElement(LazyBinding, ER);
   else
     Result = getBindingForField(LazyBinding,
                                 cast<FieldRegion>(LazyBindingRegion));
 
   // FIXME: This is a hack to deal with RegionStore's inability to distinguish a
   // default value for /part/ of an aggregate from a default value for the
   // /entire/ aggregate. The most common case of this is when struct Outer
   // has as its first member a struct Inner, which is copied in from a stack
   // variable. In this case, even if the Outer's default value is symbolic, 0,
   // or unknown, it gets overridden by the Inner's default value of undefined.
   //
   // This is a general problem -- if the Inner is zero-initialized, the Outer
   // will now look zero-initialized. The proper way to solve this is with a
   // new version of RegionStore that tracks the extent of a binding as well
   // as the offset.
   //
   // This hack only takes care of the undefined case because that can very
   // quickly result in a warning.
   if (Result.isUndef())
     Result = UnknownVal();
 
   return Result;
 }
 
 SVal
 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
                                                       const TypedValueRegion *R,
                                                       QualType Ty) {

clang/test/Analysis/copy-elision.cpp

 };
 
 class C {
   T t;
 public:
   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}}
   }
 };
 
 
 struct A {
   int x;
   A(): x(0) {}
   ~A() {}

clang/test/Analysis/dump_egraph.cpp

void foo() {
 
   new S;
 }
 
 // CHECK: \"location_context\": \"#0 Call\", \"calling\": \"foo\", \"location\": null, \"items\": [\l        \{ \"stmt_id\": {{[0-9]+}}, \"kind\": \"construct into local variable\", \"argument_index\": null, \"pretty\": \"T t;\", \"value\": \"&t\"
 
 // 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
 

clang/test/Analysis/expr-inspection.c

if (y == 2) {
         clang_analyzer_printState();
     }
   }
 }
 
 // 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": [
 // CHECK-NEXT:     { "lctx_id": {{[0-9]+}}, "location_context": "#0 Call", "calling": "foo", "location": null, "items": [
 // CHECK-NEXT:       { "stmt_id": {{[0-9]+}}, "pretty": "clang_analyzer_printState", "value": "&code{clang_analyzer_printState}" }
 // CHECK-NEXT:     ]}
 // CHECK-NEXT:   ]},
 // CHECK-NEXT:   "constraints": [

clang/test/Analysis/store-extent-rework.cpp

+// 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}}
+}

clang/test/Analysis/uninit-vals.m

 
 void PR14765_test(void) {
   Circle *testObj = calloc(sizeof(Circle), 1);
 
   clang_analyzer_eval(testObj->size == 0); // expected-warning{{TRUE}}
                                            // 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 <rdar://problem/12701038>.
-  // 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);
 }
 
 void PR14765_argument(Circle *testObj) {
   int oldSize = testObj->size;
   clang_analyzer_eval(testObj->size == oldSize); // expected-warning{{TRUE}}
                                                  // expected-note@-1{{TRUE}}
void PR14765_test_int(void) {
   clang_analyzer_eval(testObj->origin.x == 0); // expected-warning{{TRUE}}
                                                // expected-note@-1{{TRUE}}
   clang_analyzer_eval(testObj->origin.y == 0); // expected-warning{{TRUE}}
                                                // expected-note@-1{{TRUE}}
   clang_analyzer_eval(testObj->origin.z == 0); // expected-warning{{TRUE}}
                                                // 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 <rdar://problem/12701038>.
-  // 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}}
                                                // expected-note@-1{{TRUE}}
   clang_analyzer_eval(testObj->origin.z == 0); // expected-warning{{TRUE}}
                                                // expected-note@-1{{TRUE}}
 
   free(testObj);

clang/utils/analyzer/exploded-graph-rewriter.py

def is_different(self, prev):
         return updated is None or len(updated) > 0
 
 
 # A single binding key in a deserialized RegionStore cluster.
 class StoreBindingKey:
     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()
 
     def __hash__(self):
         return hash(self._key())