Page MenuHomePhabricator

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

Authored by a.sidorin on Jan 11 2016, 6:58 AM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

a.sidorin updated this revision to Diff 44485.Jan 11 2016, 6:58 AM
a.sidorin retitled this revision from to [Analyzer] Use a wider integer type for an array index.
a.sidorin updated this object.
a.sidorin set the repository for this revision to rL LLVM.
a.sidorin added a subscriber: cfe-commits.
xazax.hun edited edge metadata.Jan 11 2016, 7:14 AM

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?

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

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.

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.

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 updated this revision to Diff 44606.Jan 12 2016, 12:50 AM
a.sidorin edited edge metadata.
a.sidorin removed rL LLVM as the repository for this revision.

Fix a test.

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 accepted this revision.Jan 29 2016, 11:35 PM
zaks.anna edited edge metadata.

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

This revision is now accepted and ready to land.Jan 29 2016, 11:35 PM
This revision was automatically updated to reflect the committed changes.