[Analyzer] Use a wider integer type for an array index

[a.sidorin]

Summary

Currently, a default index type in CSA is 'int'. However, this assumption seems to be incorrect for 64-bit platforms where index may be 64-bit as well as the array size. For example, it leads to unexpected overflows while performing pointer arithmetics. Moreover, PointerDiffType and 'int' cannot be used as a common array index type because arrays may have size (and indexes) more than PTRDIFF_MAX but less than SIZE_MAX. Since maximum array size for 64 bits is SIZE_MAX/8, I propose to use 'long long' as a common index type, although it looks a bit hacky for 32 bit.

[xazax.hun]

How is this array index type used? Should it support negative values? If the answer is no, ASTContext has a getSizeType method. If it is yes, it also has a getPointerDiffType method (although it returns a QualType not a CanQualType). Is there a reason not to use them?

[a.sidorin]

In D16063#323462, @xazax.hun wrote:

How is this array index type used?

This type is used to make all the symbolic values for indices to have the same integer type (in SValBuilder).

In D16063#323462, @xazax.hun wrote:

Should it support negative values? If the answer is no, ASTContext has a getSizeType method.

They should support negative values because we are allowed to use negative index expressions.

In D16063#323462, @xazax.hun wrote:

If it is yes, it also has a getPointerDiffType method (although it returns a QualType not a CanQualType). Is there a reason not to use them?

As I described before, PtrDiffType is signed and is limited to SIZE_MAX/2. However, we are allowed to create arrays with the size more than SIZE_MAX/2 (see testIndexTooBig() test for details). But we should not loose the ability to handle such arrays and their indices.That's why I selected a 64-bit arch-independent type.

[xazax.hun]

In D16063#323513, @a.sidorin wrote:

As I described before, PtrDiffType is signed and is limited to SIZE_MAX/2. However, we are allowed to create arrays with the size more than SIZE_MAX/2 (see testIndexTooBig() test for details). But we should not loose the ability to handle such arrays and their indices.That's why I selected a 64-bit arch-independent type.

Oh, I see now, thanks. My only concern left is that, is it guaranteed that LongLongTy is available on all supported platforms including embedded ones?

[a.sidorin]

Fix a test.

[a.sidorin]

LongLongTy is initialized as a built-in type in ASTContext and, as I understand, is always available. It is not 64-bit on some platforms (like TCE), but these platforms don't have a wider type too.

[zaks.anna]

Looks like all of Gabor's comments were addressed. LGTM. Thank you!

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h

 
 public:
   SValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
               ProgramStateManager &stateMgr)
     : Context(context), BasicVals(context, alloc),
       SymMgr(context, BasicVals, alloc),
       MemMgr(context, alloc),
       StateMgr(stateMgr),
-      ArrayIndexTy(context.IntTy),
+      ArrayIndexTy(context.LongLongTy),
       ArrayIndexWidth(context.getTypeSize(ArrayIndexTy)) {}
 
   virtual ~SValBuilder() {}
 
   bool haveSameType(const SymExpr *Sym1, const SymExpr *Sym2) {
     return haveSameType(Sym1->getType(), Sym2->getType());
   }
 

cfe/trunk/test/Analysis/index-type.c

+// RUN: %clang_cc1 -triple x86_64-apple-darwin10 -analyze -analyzer-checker=core,alpha.security.ArrayBoundV2 -verify %s
+// RUN: %clang_cc1 -triple i386-apple-darwin10 -analyze -analyzer-checker=core,alpha.security.ArrayBoundV2 -DM32 -verify %s
+// expected-no-diagnostics
+
+#define UINT_MAX (~0u)
+
+#ifdef M32
+
+#define X86_ARRAY_SIZE (UINT_MAX/2 + 4)
+
+void testIndexTooBig() {
+  char arr[X86_ARRAY_SIZE];
+  char *ptr = arr + UINT_MAX/2;
+  ptr += 2;  // index shouldn't overflow
+  *ptr = 42; // no-warning
+}
+
+#else // 64-bit tests
+
+#define ARRAY_SIZE 0x100000000
+
+void testIndexOverflow64() {
+  char arr[ARRAY_SIZE];
+  char *ptr = arr + UINT_MAX/2;
+  ptr += 2;  // don't overflow 64-bit index
+  *ptr = 42; // no-warning
+}
+
+#define ULONG_MAX (~0ul)
+#define BIG_INDEX (ULONG_MAX/16)
+
+void testIndexTooBig64() {
+  char arr[ULONG_MAX/8-1];
+  char *ptr = arr + BIG_INDEX;
+  ptr += 2;  // don't overflow 64-bit index
+  *ptr = 42; // no-warning
+}
+
+#endif