[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

132

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.

181

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–171

How do we feel about this change?

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

202

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

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–171

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

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

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

Please see my comment under the original patch for explanation.

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

292–293

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

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

Same as above.

clang/test/Analysis/pr37802.cpp

26

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

Same as above.

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

15

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–171

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

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

24

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

1636–1644

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

128

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.

386–395

We should probably also count this as well:

[        B1         ][    B2     ]
          [       K         ]

1866

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.
}

2062–2077

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

128

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.

1866

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

@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

@steakhal
Same here as in the previous mempcpy14 case.

Same as above.

clang/test/Analysis/casts.c

159–167

@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

@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

@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

@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

@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;
 
+  int64_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;
 }
 
+// FIXME: This function is similar to MemRegionManager::getStaticSize(). In the
+// future they could be merged somehow.
+int64_t MemRegion::getExtent() const {
+  const MemRegion *R = this;
+
+  // Prior to this patch we assumed the
+  // extent of all region is infinite, so in case
+  // we fail to find the extent, we default to
+  // "infinity".
+  int64_t Extent = INT64_MAX;
+
+  if (const auto *SR = dyn_cast<StringRegion>(R))
+    return SR->getStringLiteral()->getByteLength() + 1;
+
+  if (const auto *FR = dyn_cast<FieldRegion>(R)) {
+    const FieldDecl *FD = FR->getDecl();
+    if (FD->isBitField())
+      return FD->getBitWidthValue(getContext());
+
+    // FIXME: This check for flexible array members could be improved by gaining
+    // access to the analyzer options. See MemRegionManager::getStaticSize() for
+    // more information.
+    const auto Ty = FR->getDesugaredValueType(getContext());
+    if (isa<IncompleteArrayType>(Ty))
+      return Extent;
+
+    if (const auto *CAT = dyn_cast<ConstantArrayType>(Ty);
+        CAT && CAT->getSize() == 0)
+      return Extent;
+  }
+
+  if (const auto *TVR = dyn_cast<TypedValueRegion>(R)) {
+    const auto Ty = TVR->getDesugaredValueType(getContext());
+
+    if (isa<VariableArrayType>(Ty))
+      return Extent;
+
+    if (Ty->isIncompleteType() || Ty->isDependentType())
+      return Extent;
+
+    Extent = getContext().getTypeSize(Ty);
+  } else if (const auto *SR = dyn_cast<SymbolicRegion>(R)) {
+    const auto Ty = SR->getSymbol()->getType().getDesugaredType(getContext());
+
+    if (!Ty->isIncompleteType() && !Ty->isDependentType() &&
+        !Ty->isVoidPointerType())
+      Extent = getContext().getTypeSize(Ty);
+  }
+
+  // We either failed to find the extent or we assign something to a
+  // placeholder. E.g.:
+  //  struct hh {
+  //    char s1[0];
+  //    char *s2;
+  //  };
+  //
+  //  memcpy(h0.s1, input, 4);
+  if (Extent == 0)
+    return INT64_MAX;
+
+  return Extent;
+}
+
 //===----------------------------------------------------------------------===//
 // BlockDataRegion
 //===----------------------------------------------------------------------===//
 
 std::pair<const VarRegion *, const VarRegion *>
 BlockDataRegion::getCaptureRegions(const VarDecl *VD) {
   MemRegionManager &MemMgr = getMemRegionManager();
   const VarRegion *VR = nullptr;

clang/lib/StaticAnalyzer/Core/RegionStore.cpp

 namespace {
 class BindingKey {
 public:
   enum Kind { Default = 0x0, Direct = 0x1 };
 private:
   enum { Symbolic = 0x2 };
 
   llvm::PointerIntPair<const MemRegion *, 2> P;
-  uint64_t Data;
+  int64_t Data;
+  int64_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,
+                      int64_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, int64_t offset, Kind k,
+                      int64_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 {
+  int64_t getOffset() const {
     assert(!hasSymbolicOffset());
     return Data;
   }
+  int64_t getExtent() const { return Extent; }
+
+  int64_t getRangeBegin() const {
+    assert(!hasSymbolicOffset());
+    return getOffset();
+  }
+  int64_t getRangeEnd() const {
+    assert(!hasSymbolicOffset());
+
+    // Try to avoid overflow.
+    if (getExtent() == INT64_MAX)
+      return getExtent();
+
+    return getOffset() + getExtent();
+  }
 
   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);
 
+  static BindingKey Make(const MemRegion *R, int64_t offset, int64_t extent,
+                         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;
+
+    return Data == X.Data ? Extent < X.Extent : Data < X.Data;
   }
 
   bool operator==(const BindingKey &X) const {
-    return P.getOpaqueValue() == X.P.getOpaqueValue() &&
-           Data == X.Data;
+    return P.getOpaqueValue() == X.P.getOpaqueValue() && Data == X.Data &&
+           Extent == X.Extent;
+  }
+
+  bool contains(const BindingKey &X) const {
+    if (hasSymbolicOffset() || X.hasSymbolicOffset())
+      return false;
+
+    if (getRegion() != X.getRegion())
+      return false;
+
+    return X.getRangeBegin() >= getRangeBegin() &&
+           X.getRangeBegin() < getRangeEnd() &&
+           X.getRangeEnd() <= getRangeEnd() &&
+           X.getRangeEnd() > getRangeBegin();
+  }
+
+  bool overlapsWith(const BindingKey &X) const {
+    if (hasSymbolicOffset() || X.hasSymbolicOffset())
+      return false;
+
+    if (getRegion() != X.getRegion())
+      return false;
+
+    uint64_t keyBegin = getRangeBegin();
+    uint64_t keyEnd = getRangeEnd();
+    uint64_t KBegin = X.getRangeBegin();
+    uint64_t KEnd = X.getRangeEnd();
+
+    // this: |-----|
+    //    X:    |-----|
+    if (keyBegin <= KBegin && KBegin < keyEnd)
+      return true;
+    // this:    |-----|
+    //    X: |-----|
+    if (keyBegin >= KBegin && keyBegin < KEnd)
+      return true;
+
+    return contains(X) || X.contains(*this);
   }
 
   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());
 }
 
+BindingKey BindingKey::Make(const MemRegion *R, int64_t offset, int64_t extent,
+                            Kind k) {
+  return BindingKey(R, offset, k, extent);
+}
 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;
+// FIXME: Remove this artifact once the patch is finalized.
+#define RSPPDEBUG 0
+
+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 {
+
+#if RSPPDEBUG
+    llvm::errs() << "Lookup key: ";
+    K.dump();
+    llvm::errs() << "\n";
+    dump();
+#endif
+
+    auto res = llvm::ImmutableMap<BindingKey, SVal>::lookup(K);
+
+#if RSPPDEBUG
+    llvm::errs() << "Found: " << res << '\n';
+    llvm::errs() << "--------------------------------------------------\n";
+#endif
+
+    return res;
+  }
+
+  const SVal *lookupPartial(const BindingKey &K) const {
+#if RSPPDEBUG
+    llvm::errs() << "Partial lookup key: ";
+    K.dump();
+    llvm::errs() << "\n";
+    dump();
+#endif
+
+    if (K.hasSymbolicOffset())
+      return nullptr;
+
+    // Try to find the smallest binding, the key is the part of.
+    int64_t lowerBound = 0;
+    int64_t upperBound = INT64_MAX;
+    const SVal *smallest = nullptr;
+    for (auto &[Key, Val] : *this)
+      if (Key.isDirect() == K.isDirect() && Key.contains(K) &&
+          Key.getRangeBegin() >= lowerBound &&
+          Key.getRangeEnd() <= upperBound) {
+        lowerBound = Key.getRangeBegin();
+        upperBound = Key.getRangeEnd();
+        smallest = &Val;
+      }
+
+#if RSPPDEBUG
+    llvm::errs() << "hit: ";
+    if (smallest)
+      smallest->dump();
+    else
+      llvm::errs() << "nullptr";
+
+    llvm::errs() << "\n--------------------------------------------------\n";
+#endif
+
+    return smallest;
+  }
+
+  using Binding = std::pair<BindingKey, SVal>;
+  std::vector<Binding> getBindingsCoveringBinding(const BindingKey &K) const {
+    // We can't reason about symbolic offsets.
+    if (K.hasSymbolicOffset())
+      return {};
+
+    // The algorithm used in this function is heavy and we only
+    // want it to run on bindings that overlap the one we look for.
+    using BindingRef = const Binding *;
+    std::vector<BindingRef> filteredCluster;
+
+    for (auto &B : *this)
+      if (B.first.overlapsWith(K))
+        filteredCluster.emplace_back(&B);
+
+    // If there are no bindings in the cluster, that overlap the
+    // current one, we return here.
+    if (filteredCluster.empty())
+      return {};
+
+    // Sort the bidnings by their ranges in ascending order.
+    std::sort(filteredCluster.begin(), filteredCluster.end(),
+              [](BindingRef lhs, BindingRef rhs) {
+                // Note that we want the wider binding to be placed before the
+                // narrower.
+                if (lhs->first.getRangeBegin() == rhs->first.getRangeBegin())
+                  return lhs->first.getRangeEnd() > rhs->first.getRangeEnd();
+
+                return lhs->first.getRangeBegin() < rhs->first.getRangeBegin();
+              });
+
+    // Concatenate the ranges and values.
+    std::vector<Binding> out;
+    out.reserve(filteredCluster.size());
+
+    std::vector<BindingRef> stack;
+    stack.reserve(filteredCluster.size());
+
+    auto lastCovered = [&] {
+      return out.empty() ? K.getRangeBegin() : out.back().first.getRangeEnd();
+    };
+
+    auto insertUpTo = [&](int64_t pos, BindingRef entry) {
+      if (pos > lastCovered()) {
+        // FIXME: Ideally a new key for the UndefinedVal{} should be created
+        // here.
+        out.push_back(entry ? *entry : Binding(K, UndefinedVal{}));
+      }
+    };
+
+    auto pushOverlapingStartingOn = [&](auto it, int64_t pos) {
+      auto last = it;
+      do {
+        // Append all binding starting at ths point
+        stack.push_back(*it);
+        last = it;
+
+        if (++it == filteredCluster.end())
+          break;
+
+      } while ((*it)->first.getRangeBegin() == pos);
+      return last;
+    };
+
+    auto popFinishedBindignsAndUpdateCoverage = [&](int64_t pos) {
+      // Pop all binidings, that are not longer overlaping with pos
+      while (!stack.empty() && (stack.back()->first.getRangeEnd() <= pos)) {
+        BindingRef top = stack.back();
+        insertUpTo(top->first.getRangeEnd(), top);
+        stack.pop_back();
+      }
+    };
+
+    auto bindingIt = filteredCluster.begin();
+    for (int64_t pos = (*bindingIt)->first.getRangeBegin();
+         pos < K.getRangeEnd(); ++pos) {
+      // Find the first binding with getRangBegin() >= pos.
+      bindingIt = std::lower_bound(
+          bindingIt, filteredCluster.end(), pos,
+          [](BindingRef e, int64_t v) { return e->first.getRangeBegin() < v; });
+      if (bindingIt == filteredCluster.end())
+        break;
+
+      pos = (*bindingIt)->first.getRangeBegin();
+      popFinishedBindignsAndUpdateCoverage(pos);
+
+      auto const *top = stack.empty() ? nullptr : stack.back();
+      bindingIt = pushOverlapingStartingOn(bindingIt, pos);
+
+      if (pos >= K.getRangeBegin()) {
+        insertUpTo((*bindingIt)->first.getRangeBegin(), top);
+        out.push_back(**bindingIt);
+      }
+    }
+
+    popFinishedBindignsAndUpdateCoverage(K.getRangeEnd());
+    insertUpTo(K.getRangeEnd(), stack.empty() ? nullptr : stack.back());
+
+#if RSPPDEBUG
+    llvm::errs() << "Key: " << K << '\n';
+    dump();
+
+    llvm::errs() << "Overlapping bindings: \n";
+    llvm::errs() << "{\n";
+    for (auto &&v : out) {
+      llvm::errs() << "    " << v.second << '\n';
+    }
+    llvm::errs() << "}\n";
+    llvm::errs()
+        << "---------------------------------------------------------\n";
+#endif
+
+    return out;
+  };
+
+#if RSPPDEBUG
+  void dump() const {
+    for (auto &&[Key, Val] : *this) {
+      llvm::errs() << '{';
+      Key.dump();
+      llvm::errs() << " value: ";
+      Val.dump();
+      llvm::errs() << '}' << '\n';
+    }
+  }
+#endif
+};
+
 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 *,
return RegionBindingsRef(static_cast<const ParentTy *>(this)->remove(K),
                              *CBFactory, IsMainAnalysis);
   }
 
   RegionBindingsRef addBinding(BindingKey K, SVal V) const;
 
   RegionBindingsRef addBinding(const MemRegion *R,
                                BindingKey::Kind k, SVal V) const;
 
-  const SVal *lookup(BindingKey K) const;
+  const SVal *lookup(BindingKey K, bool partial = false) const;
   const SVal *lookup(const MemRegion *R, BindingKey::Kind k) const;
   using llvm::ImmutableMapRef<const MemRegion *, ClusterBindings>::lookup;
 
   RegionBindingsRef removeBinding(BindingKey K);
 
   RegionBindingsRef removeBinding(const MemRegion *R,
                                   BindingKey::Kind k);
 
   RegionBindingsRef removeBinding(const MemRegion *R) {
     return removeBinding(R, BindingKey::Direct).
            removeBinding(R, BindingKey::Default);
   }
 
-  std::optional<SVal> getDirectBinding(const MemRegion *R) const;
+  std::optional<SVal> getDirectBinding(const MemRegion *R,
+                                       SValBuilder &SVB) const;
 
   /// getDefaultBinding - Returns an SVal* representing an optional default
   ///  binding associated with a region and its subregions.
   std::optional<SVal> getDefaultBinding(const MemRegion *R) const;
 
+  std::optional<SVal> getPartialBinding(const MemRegion *R,
+                                        BindingKey::Kind Kind) const;
+
+  std::vector<std::pair<BindingKey, SVal>>
+  getBindingsCoveringRegion(const MemRegion *R, BindingKey::Kind Kind) const;
+
   /// Return the internal tree as a Store.
   Store asStore() const {
     llvm::PointerIntPair<Store, 1, bool> Ptr = {
         asImmutableMap().getRootWithoutRetain(), IsMainAnalysis};
     return reinterpret_cast<Store>(Ptr.getOpaqueValue());
   }
 
   bool isMainAnalysis() const {
public:
 
   LLVM_DUMP_METHOD void dump() const { printJson(llvm::errs()); }
 };
 } // end anonymous namespace
 
 typedef const RegionBindingsRef& RegionBindingsConstRef;
 
 std::optional<SVal>
-RegionBindingsRef::getDirectBinding(const MemRegion *R) const {
-  const SVal *V = lookup(R, BindingKey::Direct);
+RegionBindingsRef::getDirectBinding(const MemRegion *R,
+                                    SValBuilder &SVB) const {
+  auto K = BindingKey::Make(R, BindingKey::Direct);
+
+  if (K.hasSymbolicOffset()) {
+    const SVal *V = lookup(K);
     return V ? std::optional<SVal>(*V) : std::nullopt;
   }
 
+  auto Bindings = getBindingsCoveringRegion(R, BindingKey::Direct);
+  if (Bindings.empty())
+    return std::nullopt;
+
+  if (Bindings.size() > 1) {
+    // FIXME: Find a more efficient way to handle this.
+    for (auto &&[Key, Val] : Bindings)
+      if (Val.isUndef())
+        return std::nullopt;
+
+    return UnknownVal{};
+  }
+
+  const auto &[Key, Val] = Bindings[0];
+
+  if (!Key.isDirect())
+    return std::nullopt;
+
+  if (!(Key == K)) {
+    assert(!Val.isUndef() && "Undefined binding returned when not expected!");
+
+    if (SymbolRef parentSym = Val.getAsSymbol())
+      return SVB.getDerivedRegionValueSymbolVal(parentSym,
+                                                cast<TypedValueRegion>(R));
+
+    return UnknownVal{};
+  }
+
+  return Val;
+}
+
 std::optional<SVal>
 RegionBindingsRef::getDefaultBinding(const MemRegion *R) const {
   const SVal *V = lookup(R, BindingKey::Default);
   return V ? std::optional<SVal>(*V) : std::nullopt;
 }
 
+std::optional<SVal>
+RegionBindingsRef::getPartialBinding(const MemRegion *R,
+                                     BindingKey::Kind Kind) const {
+  const SVal *V = lookup(BindingKey::Make(R, Kind), true);
+  return V ? std::optional<SVal>(*V) : std::nullopt;
+}
+
+std::vector<std::pair<BindingKey, SVal>>
+RegionBindingsRef::getBindingsCoveringRegion(const MemRegion *R,
+                                             BindingKey::Kind Kind) const {
+  auto K = BindingKey::Make(R, Kind);
+  const ClusterBindings *Cluster = lookup(K.getBaseRegion());
+  if (!Cluster)
+    return {};
+  return Cluster->getBindingsCoveringBinding(K);
+}
+
 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()));
+
+  auto tmpCluster = Cluster;
+  if (!K.hasSymbolicOffset() && K.isDirect()) {
+    auto begin = K.getRangeBegin();
+    auto end = K.getRangeEnd();
+    for (auto &&B : Cluster) {
+      if (!K.overlapsWith(B.first) || B.first.hasSymbolicOffset())
+        continue;
 
-  ClusterBindings NewCluster = CBFactory->add(Cluster, K, V);
-  return add(Base, NewCluster);
+      if (K.contains(B.first))
+        tmpCluster = CBFactory->remove(tmpCluster, B.first);
+      if (B.first.contains(K))
+        continue;
+
+      begin = std::min(begin, B.first.getRangeBegin());
+      end = std::max(end, B.first.getRangeEnd());
+      tmpCluster = CBFactory->remove(tmpCluster, B.first);
     }
 
+    auto key = BindingKey::Make(K.getRegion(), begin, end - begin,
+                                BindingKey::Default);
+    if (!K.contains(key)) {
+      tmpCluster =
+          CBFactory->add(tmpCluster,
+                         BindingKey::Make(K.getRegion(), begin, end - begin,
+                                          BindingKey::Default),
+                         UnknownVal{});
+    }
+  }
+
+  ClusterBindings NewCluster = CBFactory->add(tmpCluster, 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 SVal *RegionBindingsRef::lookup(BindingKey K, bool partial) const {
   const ClusterBindings *Cluster = lookup(K.getBaseRegion());
   if (!Cluster)
     return nullptr;
-  return Cluster->lookup(K);
+  return partial ? Cluster->lookupPartial(K) : Cluster->lookup(K);
 }
 
 const SVal *RegionBindingsRef::lookup(const MemRegion *R,
                                       BindingKey::Kind k) const {
   return lookup(BindingKey::Make(R, k));
 }
 
 RegionBindingsRef RegionBindingsRef::removeBinding(BindingKey K) {
public: // Part of public interface to class.
 
   // BindDefaultInitial is only used to initialize a region with
   // a default value.
   StoreRef BindDefaultInitial(Store store, const MemRegion *R,
                               SVal V) override {
     RegionBindingsRef B = getRegionBindings(store);
     // Use other APIs when you have to wipe the region that was initialized
     // earlier.
-    assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R)) &&
+    assert(!(B.getDefaultBinding(R) || B.getDirectBinding(R, svalBuilder)) &&
            "Double initialization!");
     B = B.addBinding(BindingKey::Make(R, BindingKey::Default), V);
     return StoreRef(B.asImmutableMap().getRootWithoutRetain(), *this);
   }
 
   // BindDefaultZero is used for zeroing constructors that may accidentally
   // overwrite existing bindings.
   StoreRef BindDefaultZero(Store store, const MemRegion *R) override {
collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
                          bool IncludeAllDefaultBindings) {
   FieldVector FieldsInSymbolicSubregions;
   if (TopKey.hasSymbolicOffset()) {
     getSymbolicOffsetFields(TopKey, FieldsInSymbolicSubregions);
     Top = TopKey.getConcreteOffsetRegion();
     TopKey = BindingKey::Make(Top, BindingKey::Default);
   }
 
-  // Find the length (in bits) of the region being invalidated.
-  uint64_t Length = UINT64_MAX;
-  SVal Extent = Top->getMemRegionManager().getStaticSize(Top, SVB);
-  if (std::optional<nonloc::ConcreteInt> ExtentCI =
-          Extent.getAs<nonloc::ConcreteInt>()) {
-    const llvm::APSInt &ExtentInt = ExtentCI->getValue();
-    assert(ExtentInt.isNonNegative() || ExtentInt.isUnsigned());
-    // Extents are in bytes but region offsets are in bits. Be careful!
-    Length = ExtentInt.getLimitedValue() * SVB.getContext().getCharWidth();
-  } else if (const FieldRegion *FR = dyn_cast<FieldRegion>(Top)) {
-    if (FR->getDecl()->isBitField())
-      Length = FR->getDecl()->getBitWidthValue(SVB.getContext());
-  }
-
   for (ClusterBindings::iterator I = Cluster.begin(), E = Cluster.end();
        I != E; ++I) {
     BindingKey NextKey = I.getKey();
-    if (NextKey.getRegion() == TopKey.getRegion()) {
-      // FIXME: This doesn't catch the case where we're really invalidating a
-      // region with a symbolic offset. Example:
-      //      R: points[i].y
-      //   Next: points[0].x
-
-      if (NextKey.getOffset() > TopKey.getOffset() &&
-          NextKey.getOffset() - TopKey.getOffset() < Length) {
-        // Case 1: The next binding is inside the region we're invalidating.
-        // Include it.
-        Bindings.push_back(*I);
-
-      } else if (NextKey.getOffset() == TopKey.getOffset()) {
-        // Case 2: The next binding is at the same offset as the region we're
-        // invalidating. In this case, we need to leave default bindings alone,
-        // since they may be providing a default value for a regions beyond what
-        // we're invalidating.
-        // FIXME: This is probably incorrect; consider invalidating an outer
-        // struct whose first field is bound to a LazyCompoundVal.
-        if (IncludeAllDefaultBindings || NextKey.isDirect())
-          Bindings.push_back(*I);
-      }
-
+    if (TopKey.hasSymbolicOffset()) {
     } else if (NextKey.hasSymbolicOffset()) {
       const MemRegion *Base = NextKey.getConcreteOffsetRegion();
       if (Top->isSubRegionOf(Base) && Top != Base) {
-        // Case 3: The next key is symbolic and we just changed something within
+        // The next key is symbolic and we just changed something within
         // its concrete region. We don't know if the binding is still valid, so
         // we'll be conservative and include it.
         if (IncludeAllDefaultBindings || NextKey.isDirect())
           if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
             Bindings.push_back(*I);
       } else if (const SubRegion *BaseSR = dyn_cast<SubRegion>(Base)) {
-        // Case 4: The next key is symbolic, but we changed a known
+        // The next key is symbolic, but we changed a known
         // super-region. In this case the binding is certainly included.
-        if (BaseSR->isSubRegionOf(Top))
-          if (isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
-            Bindings.push_back(*I);
+        if (BaseSR->isSubRegionOf(Top) &&
+            isCompatibleWithFields(NextKey, FieldsInSymbolicSubregions))
       }
+    } else if (TopKey.contains(NextKey)) {
+      Bindings.push_back(*I);
     }
   }
 }
 
 static void
 collectSubRegionBindings(SmallVectorImpl<BindingPair> &Bindings,
                          SValBuilder &SVB, const ClusterBindings &Cluster,
                          const SubRegion *Top, bool IncludeAllDefaultBindings) {

 ///
 /// Note that unlike RegionStoreManager::findLazyBinding, this will not search
 /// for lazy bindings for super-regions of \p R.
 static std::optional<nonloc::LazyCompoundVal>
 getExistingLazyBinding(SValBuilder &SVB, RegionBindingsConstRef B,
                        const SubRegion *R, bool AllowSubregionBindings) {
   std::optional<SVal> V = B.getDefaultBinding(R);
   if (!V)
     return std::nullopt;
 
   std::optional<nonloc::LazyCompoundVal> LCV =
       V->getAs<nonloc::LazyCompoundVal>();
   if (!LCV)
     return std::nullopt;
 
   // If the LCV is for a subregion, the types might not match, and we shouldn't
   // reuse the binding.
static std::optional<SVal> getDerivedSymbolForBinding(
     RegionBindingsConstRef B, const TypedValueRegion *BaseRegion,
     const TypedValueRegion *SubReg, const ASTContext &Ctx, SValBuilder &SVB) {
   assert(BaseRegion);
   QualType BaseTy = BaseRegion->getValueType();
   QualType Ty = SubReg->getValueType();
   if (BaseTy->isScalarType() && Ty->isScalarType()) {
     if (Ctx.getTypeSizeInChars(BaseTy) >= Ctx.getTypeSizeInChars(Ty)) {
       if (const std::optional<SVal> &ParentValue =
-              B.getDirectBinding(BaseRegion)) {
+              B.getDirectBinding(BaseRegion, SVB)) {
         if (SymbolRef ParentValueAsSym = ParentValue->getAsSymbol())
           return SVB.getDerivedRegionValueSymbolVal(ParentValueAsSym, SubReg);
 
         if (ParentValue->isUndef())
           return UndefinedVal();
 
         // Other cases: give up.  We are indexing into a larger object
         // that has some value, but we don't know how to handle that yet.
         return UnknownVal();
       }
     }
   }
   return std::nullopt;
 }
 
 SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
                                               const ElementRegion* R) {
   // Check if the region has a binding.
-  if (const std::optional<SVal> &V = B.getDirectBinding(R))
+  if (const std::optional<SVal> &V = B.getDirectBinding(R, svalBuilder))
     return *V;
 
   const MemRegion* superR = R->getSuperRegion();
 
   // Check if the region is an element region of a string literal.
   if (const StringRegion *StrR = dyn_cast<StringRegion>(superR)) {
     // FIXME: Handle loads from strings where the literal is treated as
     // an integer, e.g., *((unsigned int*)"hello"). Such loads are UB according
SVal RegionStoreManager::getBindingForElement(RegionBindingsConstRef B,
 
   return getBindingForFieldOrElementCommon(B, R, R->getElementType());
 }
 
 SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
                                             const FieldRegion* R) {
 
   // Check if the region has a binding.
-  if (const std::optional<SVal> &V = B.getDirectBinding(R))
+  if (const std::optional<SVal> &V = B.getDirectBinding(R, svalBuilder))
     return *V;
 
   // If the containing record was initialized, try to get its constant value.
   const FieldDecl *FD = R->getDecl();
   QualType Ty = FD->getType();
   const MemRegion* superR = R->getSuperRegion();
   if (const auto *VR = dyn_cast<VarRegion>(superR)) {
     const VarDecl *VD = VR->getDecl();
SVal RegionStoreManager::getBindingForField(RegionBindingsConstRef B,
 
   return getBindingForFieldOrElementCommon(B, R, Ty);
 }
 
 std::optional<SVal> RegionStoreManager::getBindingForDerivedDefaultValue(
     RegionBindingsConstRef B, const MemRegion *superR,
     const TypedValueRegion *R, QualType Ty) {
 
-  if (const std::optional<SVal> &D = B.getDefaultBinding(superR)) {
+  std::optional<SVal> D = B.getDefaultBinding(superR);
+  if (!D)
+    D = B.getPartialBinding(superR, BindingKey::Default);
+
+  if (D) {
     const SVal &val = *D;
     if (SymbolRef parentSym = val.getAsSymbol())
       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
 
     if (val.isZeroConstant())
       return svalBuilder.makeZeroVal(Ty);
 
     if (val.isUnknownOrUndef())

 }
 
 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();
-
+    Result =
+        getBindingForField(LazyBinding, cast<FieldRegion>(LazyBindingRegion));
   return Result;
 }
 
 SVal
 RegionStoreManager::getBindingForFieldOrElementCommon(RegionBindingsConstRef B,
                                                       const TypedValueRegion *R,
                                                       QualType Ty) {
 
if (hasSymbolicIndex)
       return UnknownVal();
 
     // Additionally allow introspection of a block's internal layout.
     // Try to get direct binding if all other attempts failed thus far.
     // Else, return UndefinedVal()
     if (!hasPartialLazyBinding && !isa<BlockDataRegion>(R->getBaseRegion())) {
       if (const std::optional<SVal> &V = B.getDefaultBinding(R))
         return *V;
+      if (const std::optional<SVal> &V =
+              B.getPartialBinding(R, BindingKey::Default))
+        return *V;
       return UndefinedVal();
     }
   }
 
   // All other values are symbolic.
   return svalBuilder.getRegionValueSymbolVal(R);
 }
 
 SVal RegionStoreManager::getBindingForObjCIvar(RegionBindingsConstRef B,
                                                const ObjCIvarRegion* R) {
   // Check if the region has a binding.
-  if (const std::optional<SVal> &V = B.getDirectBinding(R))
+  if (const std::optional<SVal> &V = B.getDirectBinding(R, svalBuilder))
     return *V;
 
   const MemRegion *superR = R->getSuperRegion();
 
   // Check if the super region has a default binding.
-  if (const std::optional<SVal> &V = B.getDefaultBinding(superR)) {
+  std::optional<SVal> V = B.getDefaultBinding(superR);
+  if (!V)
+    V = B.getPartialBinding(superR, BindingKey::Default);
+
+  if (V) {
     if (SymbolRef parentSym = V->getAsSymbol())
       return svalBuilder.getDerivedRegionValueSymbolVal(parentSym, R);
 
     // Other cases: give up.
     return UnknownVal();
   }
 
   return getBindingForLazySymbol(R);
 }
 
 SVal RegionStoreManager::getBindingForVar(RegionBindingsConstRef B,
                                           const VarRegion *R) {
 
   // Check if the region has a binding.
-  if (std::optional<SVal> V = B.getDirectBinding(R))
+  if (std::optional<SVal> V = B.getDirectBinding(R, svalBuilder))
     return *V;
 
   if (std::optional<SVal> V = B.getDefaultBinding(R))
     return *V;
 
+  if (std::optional<SVal> V = B.getPartialBinding(R, BindingKey::Default))
+    return *V;
+
   // Lazily derive a value for the VarRegion.
   const VarDecl *VD = R->getDecl();
   const MemSpaceRegion *MS = R->getMemorySpace();
 
   // Arguments are always symbolic.
   if (isa<StackArgumentsSpaceRegion>(MS))
     return svalBuilder.getRegionValueSymbolVal(R);
 

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

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -std=c++17 -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -std=c++17 -verify %s
 
 void clang_analyzer_eval(bool);
 
 void array_init() {
   int arr[] = {1, 2, 3, 4, 5};
 
   auto [a, b, c, d, e] = arr;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(b == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(c == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(d == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(e == 5); // expected-warning{{TRUE}}
 }
 
 void array_uninit() {
   int arr[5];
 
   auto [a, b, c, d, e] = arr;
 
-  int x = e; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(d); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(e); // expected-warning{{UNDEFINED}}
 }
 
 void lambda_init() {
   int arr[] = {1, 2, 3, 4, 5};
 
   auto l = [arr] { return arr[0]; }();
   clang_analyzer_eval(l == 1); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[1]; }();
   clang_analyzer_eval(l == 2); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[2]; }();
   clang_analyzer_eval(l == 3); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[3]; }();
   clang_analyzer_eval(l == 4); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[4]; }();
   clang_analyzer_eval(l == 5); // expected-warning{{TRUE}}
 }
 
 void lambda_uninit() {
   int arr[5];
 
-  // FIXME: These should be Undefined, but we fail to read Undefined from a lazyCompoundVal
-  int l = [arr] { return arr[0]; }();
-  clang_analyzer_eval(l); // expected-warning{{UNKNOWN}}
+  int l = [arr] { return arr[0]; }(); 
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 
   l = [arr] { return arr[1]; }();
-  clang_analyzer_eval(l); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 
   l = [arr] { return arr[2]; }();
-  clang_analyzer_eval(l); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 
   l = [arr] { return arr[3]; }();
-  clang_analyzer_eval(l); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 
   l = [arr] { return arr[4]; }();
-  clang_analyzer_eval(l); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 }
 
 struct S {
   int arr[5];
 };
 
 void copy_ctor_init() {
   S orig;
void copy_ctor_init() {
   clang_analyzer_eval(copy.arr[4] == 5); // expected-warning{{TRUE}}
 }
 
 void copy_ctor_uninit() {
   S orig;
 
   S copy = orig;
 
-  // FIXME: These should be Undefined, but we fail to read Undefined from a lazyCompoundVal.
-  // If the struct is not considered a small struct, instead of a copy, we store a lazy compound value.
-  // As the struct has an array data member, it is not considered small.
-  clang_analyzer_eval(copy.arr[0]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(copy.arr[1]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(copy.arr[2]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(copy.arr[3]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(copy.arr[4]); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(copy.arr[0]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(copy.arr[1]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(copy.arr[2]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(copy.arr[3]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(copy.arr[4]); // expected-warning{{UNDEFINED}}
 }
 
 void move_ctor_init() {
   S orig;
   orig.arr[0] = 1;
   orig.arr[1] = 2;
   orig.arr[2] = 3;
   orig.arr[3] = 4;
   orig.arr[4] = 5;
 
   S moved = (S &&) orig;
 
   clang_analyzer_eval(moved.arr[0] == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[1] == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[2] == 3); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[3] == 4); // expected-warning{{TRUE}}
   clang_analyzer_eval(moved.arr[4] == 5); // expected-warning{{TRUE}}
 }
 
 void move_ctor_uninit() {
   S orig;
 
   S moved = (S &&) orig;
 
-  // FIXME: These should be Undefined, but we fail to read Undefined from a lazyCompoundVal.
-  clang_analyzer_eval(moved.arr[0]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(moved.arr[1]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(moved.arr[2]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(moved.arr[3]); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(moved.arr[4]); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(moved.arr[0]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(moved.arr[1]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(moved.arr[2]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(moved.arr[3]); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(moved.arr[4]); // expected-warning{{UNDEFINED}}
 }
 
 // The struct has a user defined copy and move ctor, which allow us to
 // track the values more precisely when an array of this struct is being
 // copy/move initialized by ArrayInitLoopExpr.
 struct S2 {
   inline static int c = 0;
   int i;

 // The duplicate is required to emit a warning at 2 different places. 
 struct S3_duplicate {
   int i;
 };
 
 void array_uninit_non_pod() {
   S3 arr[1];
 
-  auto [a] = arr; // expected-warning@159{{ in implicit constructor is garbage or undefined }}
+  auto [a] = arr;
+  clang_analyzer_eval(a.i); // expected-warning{{UNDEFINED}}
 }
 
 void lambda_init_non_pod() {
   S2::c = 0;
   S2 arr[4];
 
   auto l = [arr] { return arr[0].i; }();
   clang_analyzer_eval(l == 2); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[1].i; }();
   clang_analyzer_eval(l == 3); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[2].i; }();
   clang_analyzer_eval(l == 4); // expected-warning{{TRUE}}
 
   l = [arr] { return arr[3].i; }();
   clang_analyzer_eval(l == 5); // expected-warning{{TRUE}}
 }
 
 void lambda_uninit_non_pod() {
   S3_duplicate arr[4];
 
-  int l = [arr] { return arr[3].i; }(); // expected-warning@164{{ in implicit constructor is garbage or undefined }}
+  int l = [arr] { return arr[3].i; }();
+  clang_analyzer_eval(l); // expected-warning{{UNDEFINED}}
 }
 
 // If this struct is being copy/move constructed by the implicit ctors, ArrayInitLoopExpr
 // is responsible for the initialization of 'arr' by copy/move constructing each of the
 // elements.
 struct S5 {
   S2 arr[4];
 };

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

void array_struct_bitfield_1() {
   clang_analyzer_eval(*((int *)pff + 1) == 0); // expected-warning{{TRUE}}
   ff.b[0] = 3;
   clang_analyzer_eval(*((int *)pff + 1) == 3); // expected-warning{{TRUE}}
 }
 
 int array_struct_bitfield_2() {
   BITFIELD_CAST ff = {0};
   BITFIELD_CAST *pff = &ff;
-  int a = *((int *)pff + 2); // expected-warning{{Assigned value is garbage or undefined [core.uninitialized.Assign]}}
+  int a = *((int *)pff + 2);
+  clang_analyzer_eval(a == 0); // expected-warning{{TRUE}}
   return a;
 }
 
 typedef struct {
   unsigned int a : 1;
   unsigned int x : 31;
   unsigned int c : 1;
   int b[2];
 } mystruct;
 
 void array_struct_bitfield_3() {
   mystruct ff;
   mystruct *pff = &ff;
   ff.b[0] = 3;
   clang_analyzer_eval(*((int *)pff + 2) == 3); // expected-warning{{TRUE}}
 }

clang/test/Analysis/bstring_UninitRead.c

 // RUN: %clang_analyze_cc1 -verify %s \
-// RUN: -analyzer-checker=core,alpha.unix.cstring
+// RUN: -analyzer-checker=core,alpha.unix.cstring,debug.ExprInspection
 
 
 // This file is generally for the alpha.unix.cstring.UninitializedRead Checker, the reason for putting it into
 // the separate file because the checker is break the some existing test cases in bstring.c file , so we don't 
 // wanna mess up with some existing test case so it's better to create separate file for it, this file also include 
 // the broken test for the reference in future about the broken tests.
 
 

 
 void *mempcpy(void *restrict s1, const void *restrict s2, size_t n);
 
 void mempcpy14() {
   int src[] = {1, 2, 3, 4};
   int dst[5] = {0};
   int *p;
 
-  p = mempcpy(dst, src, 4 * sizeof(int)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
-   // FIXME: This behaviour is actually surprising and needs to be fixed, 
-   // mempcpy seems to consider the very last byte of the src buffer uninitialized
-   // and returning undef unfortunately. It should have returned unknown or a conjured value instead.
+  p = mempcpy(dst, src, 4 * sizeof(int));
 
-  clang_analyzer_eval(p == &dst[4]); // no-warning (above is fatal)
+  clang_analyzer_eval(p == &dst[4]); // expected-warning{{TRUE}}
 }
 
 struct st {
   int i;
   int j;
 };
 
 
 void mempcpy15() {
   struct st s1 = {0};
   struct st s2;
   struct st *p1;
   struct st *p2;
 
   p1 = (&s2) + 1;
-  p2 = mempcpy(&s2, &s1, sizeof(struct st)); // expected-warning{{Bytes string function accesses uninitialized/garbage values}}
-  // FIXME: It seems same as mempcpy14() case.
+  p2 = mempcpy(&s2, &s1, sizeof(struct st));
   
-  clang_analyzer_eval(p1 == p2); // no-warning (above is fatal)
+  clang_analyzer_eval(p1 == p2); // expected-warning{{TRUE}}
 }

clang/test/Analysis/casts.c

 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin9 -fenable-matrix -analyzer-checker=core,alpha.core,debug.ExprInspection -Wno-pointer-to-int-cast -Wno-strict-prototypes -verify -analyzer-config eagerly-assume=false %s
-// RUN: %clang_analyze_cc1 -triple i386-apple-darwin9 -fenable-matrix -analyzer-checker=core,alpha.core,debug.ExprInspection -Wno-pointer-to-int-cast -Wno-strict-prototypes -verify -analyzer-config eagerly-assume=false %s
+// RUN: %clang_analyze_cc1 -triple i386-apple-darwin9 -fenable-matrix -analyzer-checker=core,alpha.core,debug.ExprInspection -Wno-pointer-to-int-cast -Wno-strict-prototypes -verify -analyzer-config eagerly-assume=false -DBIT32TEST=1 %s
 // RUN: %clang_analyze_cc1 -triple x86_64-apple-darwin9 -fenable-matrix -analyzer-checker=core,alpha.core,debug.ExprInspection -Wno-pointer-to-int-cast -Wno-strict-prototypes -verify -DEAGERLY_ASSUME=1 -w %s
 // RUN: %clang_analyze_cc1 -triple i386-apple-darwin9 -fenable-matrix -analyzer-checker=core,alpha.core,debug.ExprInspection -Wno-pointer-to-int-cast -Wno-strict-prototypes -verify -DEAGERLY_ASSUME=1 -DBIT32=1 -w %s
 
 extern void clang_analyzer_eval(_Bool);
 
 // Test if the 'storage' region gets properly initialized after it is cast to
 // 'struct sockaddr *'. 
 
void multiDimensionalArrayPointerCasts(void) {
   // FIXME: should be TRUE (i.e. same symbol).
   clang_analyzer_eval(*y1 == *y3); // expected-warning{{UNKNOWN}}
 
   clang_analyzer_eval(*((char *)y1) == *((char *) y3)); // expected-warning{{TRUE}}
 }
 
 void *getVoidPtr(void);
 
 void testCastVoidPtrToIntPtrThroughIntTypedAssignment(void) {
   int *x;
   (*((int *)(&x))) = (int)getVoidPtr();
+  #if defined I386 || defined BIT32TEST
   *x = 1; // no-crash
+  #else
+  *x = 1; // expected-warning{{undefined}}
+  #endif
 }
 
 void testCastUIntPtrToIntPtrThroughIntTypedAssignment(void) {
   unsigned u;
   int *x;
   (*((int *)(&x))) = (int)&u;
+  #if defined I386 || defined BIT32TEST
   *x = 1;
   clang_analyzer_eval(u == 1); // expected-warning{{TRUE}}
+  #else
+  *x = 1; // expected-warning{{undefined}}
+  #endif
 }
 
 void testCastVoidPtrToIntPtrThroughUIntTypedAssignment(void) {
   int *x;
   (*((int *)(&x))) = (int)(unsigned *)getVoidPtr();
+  #if defined I386 || defined BIT32TEST
   *x = 1; // no-crash
+  #else
+  *x = 1; // expected-warning{{undefined}}
+  #endif
 }
 
 void testLocNonLocSymbolAssume(int a, int *b) {
   if ((int)b < a) {} // no-crash
 }
 
 void testLocNonLocSymbolRemainder(int a, int *b) {
   int c = ((int)b) % a;

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/ctor.mm

 #ifdef I386
     clang_analyzer_eval(z == 3); // expected-warning{{TRUE}}
 #else
     // FIXME: Should be TRUE. Initialized in B().
     clang_analyzer_eval(z == 3); // expected-warning{{UNKNOWN}}
 #endif
     clang_analyzer_eval(w == 4); // expected-warning{{TRUE}}
 
-    // FIXME: Should be UNKNOWN. Changed in B() since glob_y was assigned.
-    clang_analyzer_eval(y == glob_y); // expected-warning{{TRUE}}
+    clang_analyzer_eval(y == glob_y); // expected-warning{{UNKNOWN}}
 
 #ifdef I386
     clang_analyzer_eval(z == glob_z); // expected-warning{{UNKNOWN}}
 #else
     // FIXME: Should be UNKNOWN. Changed in B() since glob_z was assigned.
     clang_analyzer_eval(z == glob_z); // expected-warning{{TRUE}}
 #endif
 

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

 };
 
 void __vector_size__PointeeTest() {
   VectorSizePointee::MyVectorType i;
   // TODO: Report v.x's pointee.
   VectorSizePointee v(&i);
 }
 
 struct CyclicPointerTest1 {
-  int *ptr; // expected-note{{object references itself 'this->ptr'}}
+  // FIXME: Should be a note for self reference.
+  int *ptr;
   int dontGetFilteredByNonPedanticMode = 0;
 
-  CyclicPointerTest1() : ptr(reinterpret_cast<int *>(&ptr)) {} // expected-warning{{1 uninitialized field}}
+  // FIXME: Should be uninitialized field.
+  CyclicPointerTest1() : ptr(reinterpret_cast<int *>(&ptr)) {}
 };
 
 void fCyclicPointerTest1() {
   CyclicPointerTest1();
 }
 
 struct CyclicPointerTest2 {
   int **pptr; // expected-note{{object references itself 'this->pptr'}}
   int dontGetFilteredByNonPedanticMode = 0;

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

 
 void fMultipleLambdaCapturesTest1() {
   int b1, b2 = 3, b3;
   auto equals = [&b1, &b2, &b3](int a) { return a == b1 == b2 == b3; }; // expected-note{{uninitialized pointee 'this->functor./*captured variable*/b1'}}
   // expected-note@-1{{uninitialized pointee 'this->functor./*captured variable*/b3'}}
   MultipleLambdaCapturesTest1<decltype(equals)>(equals, int());
 }
 
 template <class Callable>
 struct MultipleLambdaCapturesTest2 {
   Callable functor;
   int dontGetFilteredByNonPedanticMode = 0;
 
-  MultipleLambdaCapturesTest2(const Callable &functor, int) : functor(functor) {} // expected-warning{{1 uninitialized field}}
+  MultipleLambdaCapturesTest2(const Callable &functor, int) : functor(functor) {} // expected-warning{{2 uninitialized field}}
 };
 
 void fMultipleLambdaCapturesTest2() {
   int b1, b2 = 3, b3;
   auto equals = [b1, &b2, &b3](int a) { return a == b1 == b2 == b3; }; // expected-note{{uninitialized pointee 'this->functor./*captured variable*/b3'}}
+  // expected-note@-1{{uninitialized field 'this->functor./*captured variable*/b1'}}
   MultipleLambdaCapturesTest2<decltype(equals)>(equals, int());
 }
 
 struct LambdaWrapper {
   void *func; // no-crash
   int dontGetFilteredByNonPedanticMode = 0;
 
   LambdaWrapper(void *ptr) : func(ptr) {} // expected-warning{{1 uninitialized field}}
 };
 

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]+}}, "kind": "ImplicitCastExpr", "pretty": "clang_analyzer_printState", "value": "&code{clang_analyzer_printState}" }
 // CHECK-NEXT:     ]}
 // CHECK-NEXT:   ]},
 // CHECK-NEXT:   "constraints": [

clang/test/Analysis/pr22954.c

int f37(struct zz * z37) {
   clang_analyzer_eval(z37->s1[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[2] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s2 == 11); // expected-warning{{TRUE}}
 
   z37 = (struct zz *)((char*)(z37) + 4); // Increment back.
 
-  clang_analyzer_eval(z37->s1[0] == 11); // expected-warning{{TRUE}}
+  clang_analyzer_eval(z37->s1[0] == 11); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[2] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s1[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z37->s2 == 10); // expected-warning{{TRUE}}
 
   return 0;
 }
 
int f38(struct zz * z38) {
   clang_analyzer_eval(z38->s1[2] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z38->s1[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z38->s2 == 11); // expected-warning{{TRUE}}
 
   z38 = (struct zz *)((char*)(z38) + 2); // Increment back.
 
   clang_analyzer_eval(z38->s1[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z38->s1[1] == 1); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(z38->s1[2] == 11); // expected-warning{{TRUE}}
+  clang_analyzer_eval(z38->s1[2] == 11); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z38->s1[3] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(z38->s2 == 10); // expected-warning{{UNKNOWN}}
 
   return 0;
 }
 
 // Test negative offsets with a different structure layout.
 struct z0 {
int f39(struct z0 * d39) {
   clang_analyzer_eval(d39->s2 == 11); // expected-warning{{TRUE}}
 
   d39 = (struct z0 *)((char*)(d39) + 2); // Increment back.
 
   clang_analyzer_eval(d39->s1[0] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(d39->s1[1] == 1); // expected-warning{{UNKNOWN}}
   clang_analyzer_eval(d39->s1[2] == 2); // expected-warning{{TRUE}}
   clang_analyzer_eval(d39->s1[3] == 3); // expected-warning{{TRUE}}
   // FIXME: d39->s2 should evaluate to at least UNKNOWN or FALSE,
   // 'collectSubRegionBindings(...)' in RegionStore.cpp will need to
   // handle a regions' upper boundary overflowing.
-  clang_analyzer_eval(d39->s2 == 10); // expected-warning{{TRUE}}
+  clang_analyzer_eval(d39->s2 == 10); // expected-warning{{UNKNOWN}}
 
   return 0;
 }
 

clang/test/Analysis/pr37802.cpp

 // RUN: %clang_analyze_cc1 -w -analyzer-checker=core -verify %s
 
-// expected-no-diagnostics
-
 typedef __typeof(sizeof(int)) size_t;
 void *operator new(size_t, void *h) { return h; }
 
 // I've no idea what this code does, but it used to crash, so let's keep it.
 namespace pr37802_v1 {
 struct J {
   int *p;
 };
 class X {
   void *ar;
 
 public:
   X(void *t) : ar(t) {}
   template <typename T>
   void f(const T &t) {
     new (ar) T(t);
   }
 };
 class Y {
 public:
   template <typename T>
   void f(T &&);
   void f(J t) {
-    f(*t.p);
+    f(*t.p); // expected-warning{{function call argument is an uninitialized value}}
   }
 };
 class Z {
   int at() const {}
 
 public:
   Z(const Z &other) {
     other.au(X(this));
   }
   template <typename T>
public:
   void f(const J &t) { new (ar) J(t); }
   void f(const bool &t) { new (ar) bool(t); }
 };
 
 class Y {
 public:
   void boolf(bool &&);
   void f(J &&);
-  void f(J t) { boolf(*t.p); }
+  void f(J t) { boolf(*t.p); } // expected-warning{{Dereference of undefined pointer}}
 };
 
 class Z {
   int at() const {}
 
 public:
   Z(const Z &other) { other.au(X(this)); }
   void au(X t) const {

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

+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection,alpha.unix.cstring -verify %s
+
+template<typename T>
+void clang_analyzer_eval(T);
+
+template<typename T>
+void clang_analyzer_explain(T);
+
+template<typename T>
+void clang_analyzer_dump(T);
+
+typedef __typeof__(sizeof(int)) size_t;
+void *memset(void *dest, int ch, size_t count);
+void *calloc(size_t count, size_t size);
+
+namespace multipleDefaults {
+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}}
+}
+} // namespace multipleDefaults
+
+namespace multipleCovered {
+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 garbageByte1() {
+  S s;
+  s.b = 2;
+  s.c = 3;
+  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;
+}
+
+void garbageByte2() {
+  S s;
+  s.a = 1;
+  s.c = 3;
+  s.d = 4;
+
+  int x = *((int *)&s); //expected-warning{{Assigned value is garbage or undefined}}
+  (void) x;
+}
+
+void garbageByte3() {
+  S s;
+  s.a = 1;
+  s.b = 2;
+  s.d = 4;
+
+  int x = *((int *)&s); //expected-warning{{Assigned value is garbage or undefined}}
+  (void) x;
+}
+
+void garbageByte4() {
+  S s;
+  s.a = 1;
+  s.b = 2;
+  s.c = 3;
+
+  int x = *((int *)&s); //expected-warning{{Assigned value is garbage or undefined}}
+  (void) x;
+}
+} // namespace multipleCovered
+
+namespace Overlapping {
+void overlapping1() {
+  int x = 0x01020304;
+  *((char *)&x + 1) = 1;
+
+  // FIXME: Should be 0x01020301
+  clang_analyzer_eval(x); //expected-warning{{UNKNOWN}}
+
+  clang_analyzer_dump(*((char *)&x + 1)); //expected-warning{{1}}
+}
+
+void overlapping2() {
+  int x = 0x01020304;
+  *(char *)&x = 0;
+
+  clang_analyzer_dump(*(char *)&x); //expected-warning{{0}}
+  
+  // FIXME: Should be 0x01020300.
+  clang_analyzer_eval(x); //expected-warning{{UNKNOWN}}
+}
+} // namespace Overlapping
+
+namespace PartialLCV {
+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;
+  clang_analyzer_dump(a.x); //expected-warning{{2}}
+}
+} // namespace PartialLCV
+
+namespace MixingDirectAndDefault {
+void mix() {
+  int *arr[4] = {0};
+  arr[3] = (int*)calloc(1, sizeof(char));
+  int x = **(int **)((int *)&arr[2] + 1);
+
+  clang_analyzer_eval(x); // expected-warning{{UNKNOWN}}
+}
+} // namespace MixingDirectAndDefault

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

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -std=c++17 -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -std=c++17 -verify %s
 
 void clang_analyzer_eval(bool);
 
 void array_value_a(void) {
   int arr[2];
   auto [a, b] = arr;
   arr[0] = 0;
 
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
 }
 
 void array_value_b(void) {
   int arr[] = {1, 2};
   auto [a, b] = arr;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(b == 2); // expected-warning{{TRUE}}
-
-  int x = a; // no-warning
 }
 
 void array_value_c(void) {
   int arr[3];
 
   arr[1] = 1;
 
   auto [a, b, c] = arr;
 
   clang_analyzer_eval(b == arr[1]); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
 }
 
 void array_value_d(void) {
   int arr[3];
 
   arr[1] = 1;
 
   auto [a, b, c] = arr;
 
   clang_analyzer_eval(b == arr[1]); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = c; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
 }
 
 void array_value_e(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto [i, j] = init;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(j == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // no-warning
 }
 
 void array_value_f(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto [i, j] = uninit;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void array_lref_a(void) {
   int arr[2];
   auto &[a, b] = arr;
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
+
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
 }
 
 void array_lref_b(void) {
   int arr[] = {1, 2};
   auto &[a, b] = arr;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(b == 2); // expected-warning{{TRUE}}
-
-  int x = a; // no-warning
 }
 
 void array_lref_c(void) {
   int arr[2];
   auto &[a, b] = arr;
 
   arr[0] = 1;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
-
-  int x = a; // no-warning
-  int y = b; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
 }
 
 void array_lref_d(void) {
   int arr[3];
 
   arr[1] = 1;
 
   auto &[a, b, c] = arr;
 
   clang_analyzer_eval(b == 1); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
 }
 
 void array_lref_e(void) {
   int arr[3];
 
   arr[1] = 1;
 
   auto &[a, b, c] = arr;
 
   clang_analyzer_eval(b == 1); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = c; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
 }
 
 void array_lref_f(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto &[i, j] = init;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(j == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // no-warning
 }
 
 void array_lref_g(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto &[i, j] = uninit;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void array_rref_a(void) {
   int arr[2];
   auto &&[a, b] = arr;
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
 }
 
 void array_rref_b(void) {
   int arr[] = {1, 2};
   auto &&[a, b] = arr;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(b == 2); // expected-warning{{TRUE}}
 
   int x = a; // no-warning
 }
 
 void array_rref_c(void) {
   int arr[2];
   auto &&[a, b] = arr;
 
   arr[0] = 1;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
-
-  int x = a; // no-warning
-  int y = b; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
 }
 
 void array_rref_d(void) {
   int arr[3];
 
   arr[1] = 1;
 
   auto &&[a, b, c] = arr;
 
   clang_analyzer_eval(b == 1); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = a; // expected-warning{{Assigned value is garbage or undefined}}
-}
-
-void array_rref_e(void) {
-  int arr[3];
-
-  arr[1] = 1;
-
-  auto &&[a, b, c] = arr;
-
-  clang_analyzer_eval(b == 1); // expected-warning{{TRUE}}
-
-  int y = b; // no-warning
-  int x = c; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
 }
 
 void array_rref_f(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto &&[i, j] = init;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
   clang_analyzer_eval(j == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // no-warning
 }
 
 void array_rref_g(void) {
   int uninit[2];
   int init[2] = {0};
 
   uninit[0] = init[0];
 
   auto &&[i, j] = uninit;
 
   clang_analyzer_eval(i == 0); // expected-warning{{TRUE}}
-
-  int a = i; // no-warning
-  int b = j; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void array_change_a(void) {
   int arr[] = {1, 2};
 
   auto [a, b] = arr;
 
   clang_analyzer_eval(a == 1); // expected-warning{{TRUE}}
void array_change_b(void) {
   clang_analyzer_eval(arr[1] == 2); // expected-warning{{TRUE}}
 }
 
 void array_small_a(void) {
   int arr[5];
 
   auto [a, b, c, d, e] = arr;
 
-  int x = e; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(d); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(e); // expected-warning{{UNDEFINED}}
 }
 
 void array_big_a(void) {
   int arr[6];
 
   auto [a, b, c, d, e, f] = arr;
 
-  // FIXME: These will be Undefined when we handle reading Undefined values from lazyCompoundVal.
-  clang_analyzer_eval(a == 1); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(b == 2); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(c == 3); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(d == 4); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(e == 5); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(f == 6); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(b); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(c); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(d); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(e); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(f); // expected-warning{{UNDEFINED}}
 }
 
 struct S {
   int a = 1;
   int b = 2;
 };
 
 void non_pod_val(void) {

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

-// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -std=c++17 -verify %s
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -std=c++17 -verify %s
 
 void clang_analyzer_eval(bool);
 
 struct s {
   int a;
   int b;
 };
 
 void a(void) {
   s tst;
 
   auto [i, j] = tst;
 
-  int x = i; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(i); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void b(void) {
   s tst;
   tst.a = 1;
 
   auto [i, j] = tst;
 
   clang_analyzer_eval(i == 1); // expected-warning{{TRUE}}
-  int y = j;                   // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void c(void) {
   s tst;
 
   auto &[i, j] = tst;
 
-  int x = i; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(i); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void d(void) {
   s tst;
   tst.a = 1;
 
   auto &[i, j] = tst;
 
   clang_analyzer_eval(i == 1); // expected-warning{{TRUE}}
   i = 2;
   clang_analyzer_eval(tst.a == 2); // expected-warning{{TRUE}}
 
-  int y = j; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void e(void) {
   s tst;
   tst.a = 1;
 
   auto &[i, j] = tst;
 
   clang_analyzer_eval(i == 1); // expected-warning{{TRUE}}
 
   tst.b = 2;
   clang_analyzer_eval(j == 2); // expected-warning{{TRUE}}
 }
 
 void f(void) {
   s tst;
 
   auto &&[i, j] = tst;
 
-  int x = i; // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(i); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 void g(void) {
   s tst;
   tst.a = 1;
 
   auto &&[i, j] = tst;
 
   clang_analyzer_eval(i == 1); // expected-warning{{TRUE}}
-  int y = j;                   // expected-warning{{Assigned value is garbage or undefined}}
+  clang_analyzer_eval(j); // expected-warning{{UNDEFINED}}
 }
 
 struct s2 {
   int a = 1;
   int b = 2;
 };
 
 struct s3 {
   s x;
   s2 y;
 };
 
 void h(void) {
   s3 tst;
 
   clang_analyzer_eval(tst.y.a == 1); // expected-warning{{TRUE}}
 
   auto [i, j] = tst;
 
-  // FIXME: These should be undefined, but we have to fix
-  // reading undefined from lazy compound values first.
-  clang_analyzer_eval(i.a); // expected-warning{{UNKNOWN}}
-  clang_analyzer_eval(i.b); // expected-warning{{UNKNOWN}}
+  clang_analyzer_eval(i.a); // expected-warning{{UNDEFINED}}
+  clang_analyzer_eval(i.b); // expected-warning{{UNDEFINED}}
 
   clang_analyzer_eval(j.a == 1); // expected-warning{{TRUE}}
   clang_analyzer_eval(j.b == 2); // expected-warning{{TRUE}}
 }
 
 void i(void) {
   s3 tst;
 

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);

 
 void testLargeStructsNotCopiedPerField(void) {
   IntPoint a;
   a.x = 0;
 
   IntPoint b = a;
   extern void useInt(int);
   useInt(b.x); // no-warning
-  useInt(b.y); // no-warning
+  useInt(b.y); // expected-warning{{uninitialized}}
+               // expected-note@-1{{uninitialized}}
 }
 
 void testSmallStructInLargerStruct(void) {
   IntCircle2D *testObj = calloc(sizeof(IntCircle2D), 1);
 
   clang_analyzer_eval(testObj->size == 0); // expected-warning{{TRUE}}
                                            // expected-note@-1{{TRUE}}
   clang_analyzer_eval(testObj->origin.x == 0); // expected-warning{{TRUE}}

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

class GenericEnvironment:
     def is_different(self, prev):
         updated = self.diff_frames(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.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())