[analyzer] canonicalize special case of structure/pointer deref

[vabridgers]

Summary

This simple change addresses a special case of structure/pointer
aliasing that produced different symbolvals, leading to false positives
during analysis.

The reproducer is as simple as this.

struct s {
  int v;
};

void foo(struct s *ps) {
  struct s ss = *ps;
  clang_analyzer_dump(ss.v); // reg_$1<int Element{SymRegion{reg_$0<struct s *ps>},0 S64b,struct s}.v>
  clang_analyzer_dump(ps->v); //reg_$3<int SymRegion{reg_$0<struct s *ps>}.v>
  clang_analyzer_eval(ss.v == ps->v); // UNKNOWN
}

Acks: Many thanks to @steakhal and @martong for the group debug session.

[vabridgers]

Just an initial push to get this patch out there for review. I think this is pretty close. Thanks @steakhal and @martong for the debug session!

[vabridgers]

[vabridgers]

update test case

[martong]

Thanks Vince! Nice work!

Do you think it would be worth to have a test that checks the equality of a double pointer and a bi-dimensional array? Something like:

void struct_pointer_canon(struct s **ps) {
  struct s ss = **ps;
  clang_analyzer_eval(&(ps[0][0].v) == &((*ps)->v)); // expected-warning{{TRUE}}
}

[vabridgers]

@martong, Thanks for yes for sure! I'll post an update soon with a few minor test improvements.

[vabridgers]

improve test cases per @martong

[steakhal]

nits

clang/test/Analysis/ptr-arith.c

337

It's probably unnecessary.

340

I would probably put this at the top of the file.

345

You should not hardcode the internal counter in the tests.
You can use regexp matching to workaround the issue. Here is an example:
// expected-warning-re@-2 {{reg_${{[[:digit:]]+}}<int v>}}

@-2 denotes that we expect a warning two lines above.

[vabridgers]

updates per @steakhal comments

[vabridgers]

Thanks @steakhal and @martong for the comments! The patch has been updated.

[ASDenysPetrov]

I think we need to get canonical types.
Check, please, aliased types:

struct s {
  int v;
};
using T1 = s;
typedef s T2;
void foo(T1 *ps) {
  T2 ss = *ps;
  ...
}

[vabridgers]

update per comments from Denys

[vabridgers]

@ASDenysPetrov , thank you for the comment. I added a test case per your suggestion.

[steakhal]

'using' is the same as 'typedef' AFAIK.
So, you could simply use only typedefs and implement the test in the c test file. Seeing all the tests close together would aid readability IMO.
WDYT Denys? Btw does the SVval::getType return a canonical type in all cases?

[ASDenysPetrov]

In D110625#3035616, @steakhal wrote:

'using' is the same as 'typedef' AFAIK.
So, you could simply use only typedefs and implement the test in the c test file. Seeing all the tests close together would aid readability IMO.

You're right. I'm OK with typedef.

WDYT Denys? Btw does the SVval::getType return a canonical type in all cases?

SVal::getType returns a QualType which can be aliased and cv-qualified. So, it may mismatch in comparison BT->getPointeeType() == elementType. That is my concern.

[vabridgers]

added typedef case to C file for comparison, discussion

[vabridgers]

move test case from cpp file to c file

[vabridgers]

add const test case

[vabridgers]

I moved the test cases from ptr-arith.cpp to ptr-arith - using to typedef, and created an extra test case that uses const. I believe this may address all concerns discussed thus far? Please let me know if we need anything more and I'll get it done. Best!

[steakhal]

In D110625#3035843, @ASDenysPetrov wrote:

In D110625#3035616, @steakhal wrote:

WDYT Denys? Btw does the SVval::getType return a canonical type in all cases?

SVal::getType returns a QualType which can be aliased and cv-qualified. So, it may mismatch in comparison BT->getPointeeType() == elementType. That is my concern.

I thought that SVal::getType should return an already canonical QualType. If it doesn't do that we would need to do canonicalization at each callsite, which is less than ideal IMO.
If it's not yet canonical, we should probably canonicalize within the getType() function probably. WDYT?

---

In D110625#3035866, @vabridgers wrote:

I moved the test cases from ptr-arith.cpp to ptr-arith - using to typedef, and created an extra test case that uses const. I believe this may address all concerns discussed thus far? Please let me know if we need anything more and I'll get it done. Best!

I think your change is good, but we need to sort some things out before moving forward with that.

[ASDenysPetrov]

In D110625#3035929, @steakhal wrote:

I thought that SVal::getType should return an already canonical QualType. If it doesn't do that we would need to do canonicalization at each callsite, which is less than ideal IMO.
If it's not yet canonical, we should probably canonicalize within the getType() function probably. WDYT?

I believe that it returns non-canonical type. Yes, we shall get canonical versions separately for most cases in practice. This is not ideal but it would be worse to return canonical types at once along with loss of extra information.

[steakhal]

In D110625#3035974, @ASDenysPetrov wrote:

In D110625#3035929, @steakhal wrote:

I thought that SVal::getType should return an already canonical QualType. If it doesn't do that we would need to do canonicalization at each callsite, which is less than ideal IMO.
If it's not yet canonical, we should probably canonicalize within the getType() function probably. WDYT?

I believe that it returns non-canonical type. Yes, we shall get canonical versions separately for most cases in practice. This is not ideal but it would be worse to return canonical types at once along with loss of extra information.

Okay, if this is the case, we will need to use getCanonicalType() on both BT and elementType.
Vince, could you update your change, just to make sure it will work in the future, even if the test doesn't show much difference with the current behavior?
Note that you cannot call getCanonicalType() on a null-type.

[vabridgers]

Use canonical types for comparison

[vabridgers]

I'm refactoring the code change a bit. I'll push another update soon. Thanks for the comments.

[vabridgers]

Refactor compare a little bit

[steakhal]

It looks great.
Thanks Vince!

clang/lib/StaticAnalyzer/Core/Store.cpp

 }
 
 SVal StoreManager::getLValueIvar(const ObjCIvarDecl *decl, SVal base) {
   return getLValueFieldOrIvar(decl, base);
 }
 
 SVal StoreManager::getLValueElement(QualType elementType, NonLoc Offset,
                                     SVal Base) {
+
+  // Special case, if index is 0, return the same type as if
+  // this was not an array dereference.
+  if (Offset.isZeroConstant()) {
+    QualType BT = Base.getType(this->Ctx);
+    if (!BT.isNull() && !elementType.isNull()) {
+      QualType PointeeTy = BT->getPointeeType();
+      if (!PointeeTy.isNull() &&
+          PointeeTy.getCanonicalType() == elementType.getCanonicalType())
+        return Base;
+    }
+  }
+
   // If the base is an unknown or undefined value, just return it back.
   // FIXME: For absolute pointer addresses, we just return that value back as
   //  well, although in reality we should return the offset added to that
   //  value. See also the similar FIXME in getLValueFieldOrIvar().
   if (Base.isUnknownOrUndef() || Base.getAs<loc::ConcreteInt>())
     return Base;
 
   if (Base.getAs<loc::GotoLabel>())

clang/test/Analysis/ptr-arith.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=alpha.core.FixedAddr,alpha.core.PointerArithm,alpha.core.PointerSub,debug.ExprInspection -analyzer-store=region -Wno-pointer-to-int-cast -verify -triple x86_64-apple-darwin9 -Wno-tautological-pointer-compare -analyzer-config eagerly-assume=false %s
 // RUN: %clang_analyze_cc1 -analyzer-checker=alpha.core.FixedAddr,alpha.core.PointerArithm,alpha.core.PointerSub,debug.ExprInspection -analyzer-store=region -Wno-pointer-to-int-cast -verify -triple i686-apple-darwin9 -Wno-tautological-pointer-compare -analyzer-config eagerly-assume=false %s
 
 void clang_analyzer_eval(int);
+void clang_analyzer_dump(int);
 
 void f1() {
   int a[10];
   int *p = a;
   ++p;
 }
 
 char* foo();

 label:;
 }
 
 typedef __attribute__((__ext_vector_type__(2))) float simd_float2;
 float test_nowarning_on_vector_deref() {
   simd_float2 x = {0, 1};
   return x[1]; // no-warning
 }
+
+struct s {
+  int v;
+};
+
+// These three expressions should produce the same sym vals.
+void struct_pointer_canon(struct s *ps) {
+  struct s ss = *ps;
+  clang_analyzer_dump((*ps).v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<struct s * ps>}.v>}}
+  clang_analyzer_dump(ps[0].v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<struct s * ps>}.v>}}
+  clang_analyzer_dump(ps->v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<struct s * ps>}.v>}}
+  clang_analyzer_eval((*ps).v == ps[0].v); // expected-warning{{TRUE}}
+  clang_analyzer_eval((*ps).v == ps->v);   // expected-warning{{TRUE}}
+  clang_analyzer_eval(ps[0].v == ps->v);   // expected-warning{{TRUE}}
+}
+
+void struct_pointer_canon_bidim(struct s **ps) {
+  struct s ss = **ps;
+  clang_analyzer_eval(&(ps[0][0].v) == &((*ps)->v)); // expected-warning{{TRUE}}
+}
+
+typedef struct s T1;
+typedef struct s T2;
+void struct_pointer_canon_typedef(T1 *ps) {
+  T2 ss = *ps;
+  clang_analyzer_dump((*ps).v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<T1 * ps>}.v>}}
+  clang_analyzer_dump(ps[0].v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<T1 * ps>}.v>}}
+  clang_analyzer_dump(ps->v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<T1 * ps>}.v>}}
+  clang_analyzer_eval((*ps).v == ps[0].v); // expected-warning{{TRUE}}
+  clang_analyzer_eval((*ps).v == ps->v);   // expected-warning{{TRUE}}
+  clang_analyzer_eval(ps[0].v == ps->v);   // expected-warning{{TRUE}}
+}
+
+void struct_pointer_canon_bidim_typedef(T1 **ps) {
+  T2 ss = **ps;
+  clang_analyzer_eval(&(ps[0][0].v) == &((*ps)->v)); // expected-warning{{TRUE}}
+}
+
+void struct_pointer_canon_const(const struct s *ps) {
+  struct s ss = *ps;
+  clang_analyzer_dump((*ps).v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<const struct s * ps>}.v>}}
+  clang_analyzer_dump(ps[0].v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<const struct s * ps>}.v>}}
+  clang_analyzer_dump(ps->v);
+  // expected-warning-re@-1{{reg_${{[[:digit:]]+}}<int SymRegion{reg_${{[[:digit:]]+}}<const struct s * ps>}.v>}}
+  clang_analyzer_eval((*ps).v == ps[0].v); // expected-warning{{TRUE}}
+  clang_analyzer_eval((*ps).v == ps->v);   // expected-warning{{TRUE}}
+  clang_analyzer_eval(ps[0].v == ps->v);   // expected-warning{{TRUE}}
+}