ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: NoQ, xazax.hun, r.stahl.
ASDenysPetrov added a project: clang.
Herald added subscribers: manas, steakhal, martong, dkrupp, donat.nagy,
Szelethus, arphaman, mikhail.ramalho, a.sidorin, rnkovacs, szepet,
baloghadamsoftware.
ASDenysPetrov requested review of this revision.
Herald added a subscriber: cfe-commits.
We can use direct index to retrieve a value from multi-dimensional array
relying on a fact that static constant array is a solid block of memory.
Iterate through a list initialization using a raw index to get the value.
Example:
const int arr[2][2] = {{1}, {3, 4}};
const int *ptr = (int *)arr;
ptr[0]; // 1
ptr[1]; // 0
ptr[2]; // 3
ptr[3]; // 4
Fixes: https://bugs.llvm.org/show_bug.cgi?id=50604
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D104285
Files:
clang/include/clang/AST/Expr.h
clang/include/clang/AST/Type.h
clang/lib/AST/Expr.cpp
clang/lib/AST/Type.cpp
clang/lib/StaticAnalyzer/Core/RegionStore.cpp
clang/test/Analysis/initialization.cpp
Index: clang/test/Analysis/initialization.cpp
===================================================================
--- clang/test/Analysis/initialization.cpp
+++ clang/test/Analysis/initialization.cpp
@@ -1,4 +1,4 @@
-// RUN: %clang_cc1 -std=c++14 -triple i386-apple-darwin10 -analyze -analyzer-checker=core.builtin,debug.ExprInspection -verify %s
+// RUN: %clang_cc1 -std=c++14 -triple i386-apple-darwin10 -analyze -analyzer-checker=core.uninitialized.Assign,core.builtin,debug.ExprInspection -verify %s
void clang_analyzer_eval(int);
@@ -18,3 +18,108 @@
// FIXME: Should recognize that it is 0.
clang_analyzer_eval(arr[i][0]); // expected-warning{{UNKNOWN}}
}
+
+void direct_index1() {
+ int const arr[2][2][3] = {};
+ int const *ptr = (int const *)arr;
+ clang_analyzer_eval(ptr[0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[3] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[4] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[5] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[6] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[7] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[8] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[9] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[10] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[11] == 0); // expected-warning{{TRUE}}
+}
+
+void direct_index2() {
+ int const arr[2][2][3] = {{{1, 2, 3}, {4, 5, 6}}, {{7, 8, 9}, {10, 11, 12}}};
+ int const *ptr = arr[0][0];
+ clang_analyzer_eval(ptr[0] == 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[1] == 2); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[2] == 3); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[3] == 4); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[4] == 5); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[5] == 6); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[6] == 7); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[7] == 8); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[8] == 9); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[9] == 10); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[10] == 11); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[11] == 12); // expected-warning{{TRUE}}
+}
+
+void direct_index3() {
+ int const arr[2][2][3] = {{{}, {}}, {{}, {}}};
+ int const *ptr = &(arr[0][0][0]);
+ clang_analyzer_eval(ptr[0] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[1] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[3] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[4] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[5] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[6] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[7] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[8] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[9] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[10] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[11] == 0); // expected-warning{{TRUE}}
+}
+
+void direct_index4() {
+ int const arr[2][2][3] = {{{1, 2}, {}}, {{7, 8}, {10, 11, 12}}};
+ int const *ptr = (int const *)arr[0];
+ clang_analyzer_eval(ptr[0] == 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[1] == 2); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[3] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[4] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[5] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[6] == 7); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[7] == 8); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[8] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[9] == 10); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[10] == 11); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[11] == 12); // expected-warning{{TRUE}}
+}
+
+void direct_index5() {
+ int arr[2][2][3] = {{{1, 2}}, {{7}}};
+ int *ptr = (int *)arr;
+ clang_analyzer_eval(ptr[0] == 1); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[1] == 2); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[2] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[3] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[4] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[5] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[6] == 7); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[7] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[8] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[9] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[10] == 0); // expected-warning{{TRUE}}
+ clang_analyzer_eval(ptr[11] == 0); // expected-warning{{TRUE}}
+}
+
+void direct_invalid_index1() {
+ const int arr[2][2][3] = {};
+ const int *ptr = (const int *)arr;
+ int idx = -1;
+ auto x = ptr[idx]; // expected-warning{{garbage or undefined}}
+}
+
+void direct_invalid_index2() {
+ const int arr[2][2][3] = {};
+ const int *ptr = (const int *)arr;
+ int idx = 42;
+ auto x = ptr[idx]; // expected-warning{{garbage or undefined}}
+}
+
+static const unsigned RV[1][5] = {{1, 2, 3, 4, 5}};
+void PR50604() {
+ const unsigned *rvp = &(RV[0][0]);
+ auto buf_p = rvp[4]; // no-warning (garbage or undefined)
+}
Index: clang/lib/StaticAnalyzer/Core/RegionStore.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ clang/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -1669,22 +1669,23 @@
// The array index has to be known.
if (auto CI = R->getIndex().getAs<nonloc::ConcreteInt>()) {
int64_t i = CI->getValue().getSExtValue();
- // If it is known that the index is out of bounds, we can return
- // an undefined value.
- if (i < 0)
- return UndefinedVal();
+ const Expr *E = InitList->getExprForConstArrayByRawIndex(i);
- if (auto CAT = Ctx.getAsConstantArrayType(VD->getType()))
- if (CAT->getSize().sle(i))
- return UndefinedVal();
+ // If E is null, then the index is out of bounds. Return Undef.
+ if (!E)
+ return UndefinedVal();
- // If there is a list, but no init, it must be zero.
- if (i >= InitList->getNumInits())
+ // If E is the same as InitList, then there is no value specified
+ // in the list and we shall return a zero value.
+ if (E == InitList)
return svalBuilder.makeZeroVal(R->getElementType());
- if (const Expr *ElemInit = InitList->getInit(i))
- if (Optional<SVal> V = svalBuilder.getConstantVal(ElemInit))
- return *V;
+ // Return a constant value.
+ if (Optional<SVal> V = svalBuilder.getConstantVal(E))
+ return *V;
+
+ // If it is not a constant value, return Undef.
+ return UndefinedVal();
}
}
}
Index: clang/lib/AST/Type.cpp
===================================================================
--- clang/lib/AST/Type.cpp
+++ clang/lib/AST/Type.cpp
@@ -138,6 +138,18 @@
ArrayTypeBits.SizeModifier = sm;
}
+/// Return an array with extents of the declared array type.
+///
+/// E.g. for `const int x[1][2][3];` returns {1,2,3}.
+SmallVector<int64_t, 2> ConstantArrayType::getAllExtents() const {
+ SmallVector<int64_t, 2> Extents;
+ const ConstantArrayType *CAT = this;
+ do {
+ Extents.push_back(*CAT->getSize().getRawData());
+ } while (CAT = dyn_cast<ConstantArrayType>(CAT->getElementType()));
+ return Extents;
+}
+
unsigned ConstantArrayType::getNumAddressingBits(const ASTContext &Context,
QualType ElementType,
const llvm::APInt &NumElements) {
Index: clang/lib/AST/Expr.cpp
===================================================================
--- clang/lib/AST/Expr.cpp
+++ clang/lib/AST/Expr.cpp
@@ -36,6 +36,7 @@
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cstring>
+#include <numeric>
using namespace clang;
const Expr *Expr::getBestDynamicClassTypeExpr() const {
@@ -2338,6 +2339,54 @@
return Lit && Lit->getValue() == 0;
}
+const Expr *InitListExpr::getExprForConstArrayByRawIndex(int64_t Idx) const {
+ // Make sure this is a list initialization for const array.
+ QualType T = getType();
+ if (!isa<ConstantArrayType>(T))
+ return nullptr;
+
+ // Return null if index is invalid.
+ if (Idx < 0)
+ return nullptr;
+
+ SmallVector<int64_t, 2> Extents = cast<ConstantArrayType>(T)->getAllExtents();
+ // Calculate array total size.
+ int64_t Size = std::accumulate(Extents.begin(), Extents.end(), int64_t(1),
+ std::multiplies<int64_t>());
+
+ // Return null if index is out of array bounds.
+ if (Idx >= Size)
+ return nullptr;
+
+ // We can iterate through the multi-dimensional array the same as through
+ // one-dimensional array, because of the solid memory allocation.
+ const InitListExpr *InitList = this;
+ int64_t I = 0;
+ for (int64_t Ext : Extents) {
+ Size /= Ext;
+ I = Idx / Size;
+ Idx -= I * Size;
+
+ // If there is a list but no value, it must be zero.
+ // Return `this` to notify the user of this particular case.
+ // This should be handled by a caller.
+ if (I >= InitList->InitExprs.size())
+ return this;
+
+ const Stmt *Stmt = InitList->InitExprs[I];
+ // If it is not an InitListExpr, then we've reached the actual values.
+ // Return this Expr.
+ if (!isa<InitListExpr>(Stmt))
+ return cast<Expr>(Stmt);
+
+ InitList = cast<InitListExpr>(Stmt);
+ }
+
+ // We shouldn't reach here unless we missed some legal syntax while parsing.
+ // Otherwise, fix parsing logic above.
+ llvm_unreachable("List initialization is formed in an unusual way.");
+}
+
SourceLocation InitListExpr::getBeginLoc() const {
if (InitListExpr *SyntacticForm = getSyntacticForm())
return SyntacticForm->getBeginLoc();
Index: clang/include/clang/AST/Type.h
===================================================================
--- clang/include/clang/AST/Type.h
+++ clang/include/clang/AST/Type.h
@@ -2944,6 +2944,7 @@
public:
const llvm::APInt &getSize() const { return Size; }
+ SmallVector<int64_t, 2> getAllExtents() const;
const Expr *getSizeExpr() const {
return ConstantArrayTypeBits.HasStoredSizeExpr
? *getTrailingObjects<const Expr *>()
Index: clang/include/clang/AST/Expr.h
===================================================================
--- clang/include/clang/AST/Expr.h
+++ clang/include/clang/AST/Expr.h
@@ -4946,6 +4946,20 @@
InitListExprBits.HadArrayRangeDesignator = ARD;
}
+ /// Return an value-expression under the given index.
+ ///
+ /// \param Idx Direct index beginning from the first value of the list.
+ /// It's a direct index as it would be in a one-dimentional array.
+ /// For instance for `Idx = 3`:
+ /// - `const T x[2][2] = {{1,2},{3,4}}` returns '4'
+ /// - `const T x[2][2] = {{1,},{3,4}}` returns '4'
+ /// - `const T x[3][2] = {{1,},{},{5,6}}` returns '0'
+ /// \returns
+ /// - value-expression for the valid index.
+ /// - `this` if there's no expression for the valid index
+ /// - `nullptr` for invalid index (`i < 0` or `i >= array_size`).
+ const Expr *getExprForConstArrayByRawIndex(int64_t Idx) const;
+
SourceLocation getBeginLoc() const LLVM_READONLY;
SourceLocation getEndLoc() const LLVM_READONLY;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
