[analyzer] Fix "RhsLoc and LhsLoc bitwidth must be same"

[vabridgers]

Summary

clang: <root>/clang/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp:727:
void assertEqualBitWidths(clang::ento::ProgramStateRef,

clang::ento::Loc, clang::ento::Loc): Assertion `RhsBitwidth ==
LhsBitwidth && "RhsLoc and LhsLoc bitwidth must be same!"'

This change adjusts the bitwidth of the smaller operand for an evalBinOp
as a result of a comparison operation. This can occur in the specific
case represented by the test cases for a target with different pointer
sizes.

[NoQ]

Why doesn't the AST handle this for us through implicit casts? Do we really need to duplicate type promotion logic in the static analyzer?

[vabridgers]

Hi @NoQ, good question :) When I looked into the existing SimpleSValBuilder.cpp code, I found a few places that did width modifications so I concluded this was the correct and accepted way to handle this. A few notes to help decide if my suggestion is correct or is there's a different concrete way to move forward. Looks like we get address space information in the AST, and it's up to the AST client to do the needful (whatever that is). We do get warnings and/or errors in some cases, but it seems this is a case where it's implied that the "void *" cast is same address space as the LHS of the comparison. I'll check the Embedded C Spec to see what it says about this.

The Sample function looks like this:

int fn1() {
  int val = 0;
  __attribute__((address_space(3))) int *dptr = val;
  return dptr == (void *)0;
}

The AST for the return statement "return dptr == (void *)0;" looks like this:

`-ReturnStmt 0x118f2078 <line:21:3, col:26>
  `-BinaryOperator 0x118f2058 <col:10, col:26> 'int' '=='
    |-ImplicitCastExpr 0x118f2028 <col:10> '__attribute__((address_space(3))) int *' <LValueToRValue>
    | `-DeclRefExpr 0x118f1fa8 <col:10> '__attribute__((address_space(3))) int *' lvalue Var 0x118f1af0 'dptr' '__attribute__((address_space(3))) int *'
    `-ImplicitCastExpr 0x118f2040 <col:18, col:26> '__attribute__((address_space(3))) int *' <AddressSpaceConversion>
      `-CStyleCastExpr 0x118f2000 <col:18, col:26> 'void *' <NullToPointer>
        `-IntegerLiteral 0x118f1fc8 <col:26> 'int' 0

[vabridgers]

Apparently, it's up to an implementation to determine the specific relations that can be computed between different address spaces. Perhaps a better way to deal with this for now, to avoid crashes, is follow the DereferenceChecker model. That checker punts on checking relations with any pointers that have a address space. If a downstream compiler wants to compute relations between pointers with address spaces, they are certainly free to do that - but I get the instinct this might not be best to push upstream :/

Ideas? Best!

Here's the snippet, and comment, from clang/lib/StaticAnalyzer/Checkers/DereferenceChecker.cpp

...
112 static bool suppressReport(const Expr *E) {
113   // Do not report dereferences on memory in non-default address spaces.
114   return E->getType().hasAddressSpace();
115 }
...

[NoQ]

I mean, regardless of whether we need to report a warning or an error against this code, the AST says that the RHS type and the LHS type are the same. This means that the same should have applied to our SVals that represent LHS and RHS, rendering std::max(APSIntType(LHSValue), APSIntType(RHSValue)) redundant. So I suspect that the problem is not that we're not std::maxing hard enough, the problem is that our values weren't correct in the first place, so I think you need to take a look at the transfer function corresponding to statement

ImplicitCastExpr 0x118f2040 <col:18, col:26> '__attribute__((address_space(3))) int *' <AddressSpaceConversion>

...and see why didn't it cause the type of the SVal to be updated with the address space attribute.

[vabridgers]

Ahhh, I see now :/

I can dig down into state->getSVal() and see what's going wrong.

in clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp

40 void ExprEngine::VisitBinaryOperator(const BinaryOperator* B,
41                                      ExplodedNode *Pred,
42                                      ExplodedNodeSet &Dst) {
43 
44   Expr *LHS = B->getLHS()->IgnoreParens();
45   Expr *RHS = B->getRHS()->IgnoreParens();
46 
47   // FIXME: Prechecks eventually go in ::Visit().
48   ExplodedNodeSet CheckedSet;
49   ExplodedNodeSet Tmp2;
50   getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, B, *this);
51 
52   // With both the LHS and RHS evaluated, process the operation itself.
53   for (ExplodedNodeSet::iterator it=CheckedSet.begin(), ei=CheckedSet.end();
54          it != ei; ++it) {
55 
56     ProgramStateRef state = (*it)->getState();
57     const LocationContext *LCtx = (*it)->getLocationContext();
58     SVal LeftV = state->getSVal(LHS, LCtx);
59     SVal RightV = state->getSVal(RHS, LCtx);
60

(gdb) frame 12
#12 0x00000000073a029a in clang::ento::ExprEngine::VisitBinaryOperator (this=0x7fffffffa630, B=0xff29e40, Pred=0xff3c700, Dst=...)
    at <root>/clang/lib/StaticAnalyzer/Core/ExprEngineC.cpp:100
100	      SVal Result = evalBinOp(state, Op, LeftV, RightV, B->getType());
(gdb) p LHS
$1 = (clang::Expr *) 0xff29e10
(gdb) p LHS->dump()
ImplicitCastExpr 0xff29e10 '__attribute__((address_space(3))) int *' <LValueToRValue>
`-DeclRefExpr 0xff29d90 '__attribute__((address_space(3))) int *' lvalue Var 0xff29c90 'dptr' '__attribute__((address_space(3))) int *'
$2 = void
(gdb) p RHS->dump()
ImplicitCastExpr 0xff29e28 '__attribute__((address_space(3))) int *' <AddressSpaceConversion>
`-CStyleCastExpr 0xff29de8 'void *' <NullToPointer>
  `-IntegerLiteral 0xff29db0 'int' 0
$3 = void

[NoQ]

getSVal is probably not at fault, it simply retrieves the value it was previously told to put there, it doesn't care what the value is. You probably want to look at ExprEngine::VisitCast().

[vabridgers]

I think I got it, looks like we're losing the width information at line 685, 686 below.

Looks like I need to adjust the bitwidth of V before returning.

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

671 SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy,
672                                   QualType OriginalTy) {
673   // Pointer to bool.
674   if (CastTy->isBooleanType())
675     return makeTruthVal(V.getValue().getBoolValue(), CastTy);
676 
677   // Pointer to integer.
678   if (CastTy->isIntegralOrEnumerationType()) {
679     llvm::APSInt Value = V.getValue();
680     BasicVals.getAPSIntType(CastTy).apply(Value);
681     return makeIntVal(Value);
682   }
683 
684   // Pointer to any pointer.
685   if (Loc::isLocType(CastTy))
686     return V;
687 
688   // Pointer to whatever else.
689   return UnknownVal();
690 }

Breakpoint 8, clang::ento::SValBuilder::evalCastSubKind (this=0xff34500, V=..., CastTy=..., OriginalTy=...)
    at  <root>/clang/lib/StaticAnalyzer/Core/SValBuilder.cpp:674
674	  if (CastTy->isBooleanType())
(gdb) next
678	  if (CastTy->isIntegralOrEnumerationType()) {
(gdb) 
685	  if (Loc::isLocType(CastTy))
(gdb) p V
$25 = {<clang::ento::Loc> = {<clang::ento::DefinedSVal> = {<clang::ento::DefinedOrUnknownSVal> = {<clang::ento::SVal> = {Data = 0xff37cf0, 
          Kind = 2}, <No data fields>}, <No data fields>}, <No data fields>}, <No data fields>}
(gdb) p V.dump()
0 (Loc)$26 = void
(gdb) p CastTy.dump()
PointerType 0xfede460 '__attribute__((address_space(3))) int *'
`-QualType 0xfede418 '__attribute__((address_space(3))) int' __attribute__((address_space(3)))
  `-BuiltinType 0xfedd640 'int'
$27 = void

[vabridgers]

Come up with a more principaled fix, thanks @NoQ :)

[NoQ]

clang/test/Analysis/addrspace-null.c

20

Shouldn't this be AMDGCN_TRIPLE?

[NoQ]

Other than that, looks great now!

[vabridgers]

fix typo in test - ready to land

[vabridgers]

clang/test/Analysis/addrspace-null.c

20

fixed, thank you.

clang/lib/StaticAnalyzer/Core/SValBuilder.cpp

SVal SValBuilder::evalCastSubKind(loc::ConcreteInt V, QualType CastTy,
   // Pointer to integer.
   if (CastTy->isIntegralOrEnumerationType()) {
     llvm::APSInt Value = V.getValue();
     BasicVals.getAPSIntType(CastTy).apply(Value);
     return makeIntVal(Value);
   }
 
   // Pointer to any pointer.
-  if (Loc::isLocType(CastTy))
-    return V;
+  if (Loc::isLocType(CastTy)) {
+    llvm::APSInt Value = V.getValue();
+    BasicVals.getAPSIntType(CastTy).apply(Value);
+    return loc::ConcreteInt(BasicVals.getValue(Value));
+  }
 
   // Pointer to whatever else.
   return UnknownVal();
 }
 
 SVal SValBuilder::evalCastSubKind(loc::GotoLabel V, QualType CastTy,
                                   QualType OriginalTy) {
   // Pointer to bool.

clang/test/Analysis/addrspace-null.c

+// RUN: %clang_analyze_cc1 -triple amdgcn-unknown-unknown \
+// RUN: -analyze -analyzer-checker=core -DAMDGCN_TRIPLE \
+// RUN: -analyze -analyzer-checker=debug.ExprInspection \
+// RUN: -Wno-implicit-int -Wno-int-conversion -verify %s
+//
+// RUN: %clang_analyze_cc1 -triple amdgcn-unknown-unknown \
+// RUN: -analyze -analyzer-checker=core -DDEFAULT_TRIPLE \
+// RUN: -analyze -analyzer-checker=debug.ExprInspection \
+// RUN: -Wno-implicit-int -Wno-int-conversion -verify %s
+
+// From https://llvm.org/docs/AMDGPUUsage.html#address-spaces,
+// select address space 3 (local), since the pointer size is
+// different than Generic.
+
+// expected-no-diagnostics
+
+#define DEVICE __attribute__((address_space(3)))
+
+#if defined(AMDGCN_TRIPLE)
+// this crashes
+int fn1() {
+  int val = 0;
+  DEVICE int *dptr = val;
+  return dptr == (void *)0;
+}
+
+// does not crash
+int fn2() {
+  int val = 0;
+  DEVICE int *dptr = val;
+  return dptr == (DEVICE void *)0;
+}
+
+// this crashes
+int fn3() {
+  int val = 0;
+  int *dptr = val;
+  return dptr == (DEVICE void *)0;
+}
+#endif
+
+// does not crash
+int fn4() {
+  int val = 0;
+  int *dptr = val;
+  return dptr == (void *)0;
+}