[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki abandoned this revision. danielmarjamaki added a comment. Herald added subscribers: llvm-commits, a.sidorin, rnkovacs. I will not continue working on this. Feel free to take over the patch or write a new patch. Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki updated this revision to Diff 121726.
danielmarjamaki added a comment.
Herald added a subscriber: szepet.
I have updated the patch so it uses evalBinOpNN. This seems to work properly.
I have a number of TODOs in the test cases that should be fixed. Truncations
are not handled properly.
Here is a short example code:
void f(unsigned char X) {
if (X >= 10 && X <= 50) {
unsigned char Y = X + 0x100; // truncation
clang_analyzer_eval(Y >= 10 && Y <= 50); // expected-warning{{FALSE}}
}
}
The expected-warning should be TRUE but currently FALSE is written.
When the "Y >= 10" condition is evaluated the ProgramState is:
Store (direct and default bindings), 0x222ab0fe5f8 :
(Y,0,direct) : (unsigned char) ((reg_$0) + 256)
Expressions:
(0x222a96d6050,0x222ab0eb930) X + 256 : (unsigned char) ((reg_$0) + 256)
(0x222a96d6050,0x222ab0eb960) clang_analyzer_eval :
&code{clang_analyzer_eval}
(0x222a96d6050,0x222ab0eb988) Y : &Y
(0x222a96d6050,0x222ab0eb9d8) Y : (unsigned char) ((reg_$0)
+ 256)
(0x222a96d6050,0x222ab0eb9f0) Y : (unsigned char) ((reg_$0)
+ 256)
(0x222a96d6050,0x222ab0eba08) Y >= 10 : ((unsigned char) ((reg_$0) + 256)) >= 10
(0x222a96d6050,0x222ab0ebb28) clang_analyzer_eval :
&code{clang_analyzer_eval}
Ranges of symbol values:
reg_$0 : { [10, 50] }
(reg_$0) + 256 : { [10, 50] }
It seems to me that the symbol initialization does not handle the range
properly. Imho there is nothing wrong with the calculation. What you think
about adding a range like below?
(unsigned char) ((reg_$0) + 256) : { [10, 50] }
Repository:
rL LLVM
https://reviews.llvm.org/D36471
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
include/clang/StaticAnalyzer/Core/PathSensitive/SimpleConstraintManager.h
lib/StaticAnalyzer/Core/ExprEngineC.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
test/Analysis/range_calc.c
Index: test/Analysis/range_calc.c
===
--- test/Analysis/range_calc.c
+++ test/Analysis/range_calc.c
@@ -0,0 +1,143 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+#define INT_MAX((signed int)((~0U)>>1))
+#define INT_MIN((signed int)(~((~0U)>>1)))
+
+void addInts(int X)
+{
+ if (X >= 10 && X <= 50) {
+int Y = X + 2;
+clang_analyzer_eval(Y >= 12 && Y <= 52); // expected-warning{{TRUE}}
+ }
+
+ if (X < 5) {
+int Y = X + 1;
+clang_analyzer_eval(Y < 6); // expected-warning{{TRUE}}
+ }
+
+ if (X >= 1000) {
+int Y = X + 1; // might overflow
+clang_analyzer_eval(Y >= 1001); // expected-warning{{UNKNOWN}}
+clang_analyzer_eval(Y == INT_MIN); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(Y == INT_MIN || Y >= 1001); // expected-warning{{TRUE}}
+ }
+}
+
+void addU8(unsigned char X)
+{
+ if (X >= 10 && X <= 50) {
+unsigned char Y = X + 2;
+clang_analyzer_eval(Y >= 12 && Y <= 52); // expected-warning{{TRUE}}
+ }
+
+ if (X < 5) {
+unsigned char Y = X + 1;
+clang_analyzer_eval(Y < 6); // expected-warning{{TRUE}}
+ }
+
+ // TODO
+ if (X >= 10 && X <= 50) {
+unsigned char Y = X + (-256); // truncation
+clang_analyzer_eval(Y >= 10 && Y <= 50); // expected-warning{{FALSE}}
+ }
+
+ // TODO
+ if (X >= 10 && X <= 50) {
+unsigned char Y = X + 256; // truncation
+clang_analyzer_eval(Y >= 10 && Y <= 50); // expected-warning{{FALSE}} expected-warning{{UNKNOWN}}
+ }
+
+ // TODO
+ if (X >= 100) {
+unsigned char Y = X + 1; // truncation
+ clang_analyzer_eval(Y == 0); // expected-warning{{FALSE
+ clang_analyzer_eval(Y >= 101); // expected-warning{{TRUE}}
+clang_analyzer_eval(Y == 0 || Y >= 101); // expected-warning{{TRUE}}
+ }
+
+ if (X >= 100) {
+unsigned short Y = X + 1;
+clang_analyzer_eval(Y >= 101 && Y <= 256); // expected-warning{{TRUE}}
+ }
+}
+
+void sub1(int X)
+{
+ if (X >= 10 && X <= 50) {
+int Y = X - 2;
+clang_analyzer_eval(Y >= 8 && Y <= 48); // expected-warning{{TRUE}}
+ }
+
+ if (X >= 10 && X <= 50) {
+unsigned char Y = (unsigned int)X - 20; // truncation
+clang_analyzer_eval(Y <= 30 || Y >= 246); // expected-warning{{TRUE}}
+ }
+
+ // TODO
+ if (X >= 10 && X <= 50) {
+unsigned char Y = (unsigned int)X - 256; // truncation
+clang_analyzer_eval(Y >= 10 && Y <= 50); // expected-warning{{FALSE}} expected-warning{{UNKNOWN}}
+ }
+
+ if (X < 5) {
+int Y = X - 1; // might overflow
+clang_analyzer_eval(Y < 4); // expected-warning{{UNKNOWN}}
+clang_analyzer_eval(Y == INT_MAX); // expected-warning{{UNKNOWN}}
+ clang_analyzer_eval(Y == INT_MAX || Y < 4); // expected-warning{{TRUE}}
+ }
+
+ if (X >= 1000) {
+int Y = X - 1;
+clang_analyzer_eval(Y >= 999); // expected-warning{{TRUE}}
+ }
+}
+
+void subU8(unsigned char X)
+{
+ if (X >= 10 && X <= 50) {
+unsigned char Y = X - 2;
+clang_analyzer_eval(Y >=
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
xazax.hun added a subscriber: NoQ. xazax.hun added a comment. I think this change is very useful but it is also important to get these changes right. I think one of the main reason you did not get review comments yet is that it is not easy to verify that these changes are sound. In general, there are false positives in the analyzer due to limits in the constraint manager (or missing parts in modeling the language). But in general, we try to avoid having false positives due to unsound assumptions (apart from some cases like assuming const methods will not change the fields of a class). While the change you introduced is indeed very useful the soundness probably depends on the details of how promotions, conversions, and other corner cases are handled. In order to introduce a change like this, we need to have those cases covered to ensure that we have the soundness we want and this needs to be verified with test cases. Also once the solution is sound it would be great to measure the performance to ensure that we did not regress too much. I understand that you do not want to work on something that might not get accepted but also with the available information it might be hard to decide whether this is a good approach to the problem or not. But of course, I am just guessing here, @dcoughlin, @zaks.anna, @NoQ might have a different opinion. A bit more technical comment: did you consider using `SValBuilder`'s `evalBinOpNN`? I believe it already handles at least some of the conversions you did not cover here. Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. ping Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. ping Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. ping Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. ping Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki updated this revision to Diff 113969.
danielmarjamaki added a comment.
minor code cleanup
Repository:
rL LLVM
https://reviews.llvm.org/D36471
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
lib/StaticAnalyzer/Core/ExprEngineC.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -304,6 +304,8 @@
void print(ProgramStateRef State, raw_ostream &Out, const char *nl,
const char *sep) override;
+ ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) override;
+
//===--===//
// Implementation for interface from RangedConstraintManager.
//===--===//
@@ -741,3 +743,56 @@
}
Out << nl;
}
+
+ProgramStateRef RangeConstraintManager::evalRangeOp(ProgramStateRef St,
+SVal V) {
+ const SymExpr *SE = V.getAsSymExpr();
+ if (!SE)
+return nullptr;
+
+ const SymIntExpr *SIE = dyn_cast(SE);
+ if (!SIE)
+return nullptr;
+
+ const clang::BinaryOperatorKind Opc = SIE->getOpcode();
+
+ if (Opc != BO_Add && Opc != BO_Sub && Opc != BO_Div)
+return nullptr;
+
+ const SymExpr *LHS = SIE->getLHS();
+ const llvm::APSInt &RHS = SIE->getRHS();
+
+ ConstraintRangeTy Ranges = St->get();
+ for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E;
+ ++I) {
+if (LHS != I.getKey())
+ continue;
+const auto D = I.getData();
+for (auto I = D.begin(); I != D.end(); ++I) {
+ if (I->From().isUnsigned() != RHS.isUnsigned())
+// TODO: Handle sign conversions.
+return nullptr;
+ if (I->From().getBitWidth() != RHS.getBitWidth())
+// TODO: Promote values.
+return nullptr;
+ if (I->From().isNegative())
+// TODO: Handle negative range values
+return nullptr;
+
+ BasicValueFactory &BVF = getBasicVals();
+ const llvm::APSInt *Lower = BVF.evalAPSInt(Opc, I->From(), RHS);
+ if (!Lower)
+return nullptr;
+ const llvm::APSInt *Upper = BVF.evalAPSInt(Opc, I->To(), RHS);
+ if (!Upper)
+return nullptr;
+
+ SymbolRef Sym = V.getAsSymbol();
+ RangeSet RS =
+ getRange(St, Sym).Intersect(getBasicVals(), F, *Lower, *Upper);
+ // TODO: This only evaluates the first range. Evaluate all ranges.
+ return RS.isEmpty() ? nullptr : St->set(Sym, RS);
+}
+ }
+ return nullptr;
+}
Index: lib/StaticAnalyzer/Core/ExprEngineC.cpp
===
--- lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -98,7 +98,9 @@
}
state = state->BindExpr(B, LCtx, Result);
- Bldr.generateNode(B, *it, state);
+ ProgramStateRef state2 =
+ getConstraintManager().evalRangeOp(state, Result);
+ Bldr.generateNode(B, *it, state2 ? state2 : state);
continue;
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
@@ -142,13 +142,15 @@
/// Scan all symbols referenced by the constraints. If the symbol is not
/// alive, remove it.
virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
- SymbolReaper& SymReaper) = 0;
+ SymbolReaper &SymReaper) = 0;
- virtual void print(ProgramStateRef state,
- raw_ostream &Out,
- const char* nl,
+ virtual void print(ProgramStateRef state, raw_ostream &Out, const char *nl,
const char *sep) = 0;
+ virtual ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) {
+return nullptr;
+ }
+
virtual void EndPath(ProgramStateRef state) {}
/// Convenience method to query the state to see if a symbol is null or
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. Should evalAPSInt() have machinery to do standard sign/type promotions? I suggest that I add one more argument `bool promote = false`, do you think that sounds good? Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki updated this revision to Diff 110378.
danielmarjamaki added a comment.
Refactoring, use BasicValueFactory::evalAPSInt
Repository:
rL LLVM
https://reviews.llvm.org/D36471
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
lib/StaticAnalyzer/Core/ExprEngineC.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
test/Analysis/eval-range.c
Index: test/Analysis/eval-range.c
===
--- test/Analysis/eval-range.c
+++ test/Analysis/eval-range.c
@@ -0,0 +1,18 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+void test1(int a) {
+ if (a >= 10 && a <= 50) {
+int b;
+
+b = a + 2;
+clang_analyzer_eval(b >= 12 && b <= 52); // expected-warning{{TRUE}}
+
+b = a - 2;
+clang_analyzer_eval(b >= 8 && b <= 48); // expected-warning{{TRUE}}
+
+b = a / 2;
+clang_analyzer_eval(b >= 5 && b <= 25); // expected-warning{{TRUE}}
+ }
+}
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -304,6 +304,8 @@
void print(ProgramStateRef State, raw_ostream &Out, const char *nl,
const char *sep) override;
+ ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) override;
+
//===--===//
// Implementation for interface from RangedConstraintManager.
//===--===//
@@ -741,3 +743,56 @@
}
Out << nl;
}
+
+ProgramStateRef RangeConstraintManager::evalRangeOp(ProgramStateRef St,
+SVal V) {
+ const SymExpr *SE = V.getAsSymExpr();
+ if (!SE)
+return nullptr;
+
+ const SymIntExpr *SIE = dyn_cast(SE);
+ if (!SIE)
+return nullptr;
+
+ const clang::BinaryOperatorKind Opc = SIE->getOpcode();
+
+ if (Opc != BO_Add && Opc != BO_Sub && Opc != BO_Div)
+return nullptr;
+
+ const SymExpr *LHS = SIE->getLHS();
+ const llvm::APSInt &RHS = SIE->getRHS();
+
+ ConstraintRangeTy Ranges = St->get();
+ for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E;
+ ++I) {
+if (LHS == I.getKey()) {
+ const auto D = I.getData();
+ for (auto I = D.begin(); I != D.end(); ++I) {
+if (I->From().isUnsigned() != RHS.isUnsigned())
+ // TODO: Handle sign conversions.
+ return nullptr;
+if (I->From().getBitWidth() != RHS.getBitWidth())
+ // TODO: Promote values.
+ return nullptr;
+if (I->From().isNegative())
+ // TODO: Handle negative range values
+ return nullptr;
+
+BasicValueFactory &BVF = getBasicVals();
+const llvm::APSInt *Lower = BVF.evalAPSInt(Opc, I->From(), RHS);
+if (!Lower)
+ return nullptr;
+const llvm::APSInt *Upper = BVF.evalAPSInt(Opc, I->To(), RHS);
+if (!Upper)
+ return nullptr;
+
+SymbolRef Sym = V.getAsSymbol();
+RangeSet RS =
+getRange(St, Sym).Intersect(getBasicVals(), F, *Lower, *Upper);
+// TODO: This only evaluates the first range. Evaluate all ranges.
+return RS.isEmpty() ? nullptr : St->set(Sym, RS);
+ }
+}
+ }
+ return nullptr;
+}
Index: lib/StaticAnalyzer/Core/ExprEngineC.cpp
===
--- lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -98,7 +98,9 @@
}
state = state->BindExpr(B, LCtx, Result);
- Bldr.generateNode(B, *it, state);
+ ProgramStateRef state2 =
+ getConstraintManager().evalRangeOp(state, Result);
+ Bldr.generateNode(B, *it, state2 ? state2 : state);
continue;
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
@@ -142,13 +142,15 @@
/// Scan all symbols referenced by the constraints. If the symbol is not
/// alive, remove it.
virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
- SymbolReaper& SymReaper) = 0;
+ SymbolReaper &SymReaper) = 0;
- virtual void print(ProgramStateRef state,
- raw_ostream &Out,
- const char* nl,
+ virtual void print(ProgramStateRef state, raw_ostream &Out, const char *nl,
const char *sep) = 0;
+ virtual ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) {
+return nullptr;
+ }
+
virtual
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki added a comment. In https://reviews.llvm.org/D36471#835410, @xazax.hun wrote: > Can't you reuse somehow some machinery already available to evaluate the > arithmetic operators? Those should already handle most of your TODOs and > overflows. Sounds good.. I have not seen that machinery.. I will look around. To me it seems it would be nice if this machinery was builtin in APSInt so I could calculate (x+y) even if x and y did not have the same signedness and that the result would be unsigned. Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki updated this revision to Diff 110220.
danielmarjamaki added a comment.
A minor code cleanup. No functional change.
Repository:
rL LLVM
https://reviews.llvm.org/D36471
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
lib/StaticAnalyzer/Core/ExprEngineC.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
test/Analysis/eval-range.c
Index: test/Analysis/eval-range.c
===
--- test/Analysis/eval-range.c
+++ test/Analysis/eval-range.c
@@ -0,0 +1,18 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+void test1(int a) {
+ if (a >= 10 && a <= 50) {
+int b;
+
+b = a + 2;
+clang_analyzer_eval(b >= 12 && b <= 52); // expected-warning{{TRUE}}
+
+b = a - 2;
+clang_analyzer_eval(b >= 8 && b <= 48); // expected-warning{{TRUE}}
+
+b = a / 2;
+clang_analyzer_eval(b >= 5 && b <= 25); // expected-warning{{TRUE}}
+ }
+}
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -304,6 +304,8 @@
void print(ProgramStateRef State, raw_ostream &Out, const char *nl,
const char *sep) override;
+ ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) override;
+
//===--===//
// Implementation for interface from RangedConstraintManager.
//===--===//
@@ -741,3 +743,65 @@
}
Out << nl;
}
+
+ProgramStateRef RangeConstraintManager::evalRangeOp(ProgramStateRef St,
+SVal V) {
+ const SymExpr *SE = V.getAsSymExpr();
+ if (!SE)
+return nullptr;
+
+ const SymIntExpr *SIE = dyn_cast(SE);
+ if (!SIE)
+return nullptr;
+
+ const clang::BinaryOperatorKind Opc = SIE->getOpcode();
+
+ if (Opc != BO_Add && Opc != BO_Sub && Opc != BO_Div)
+return nullptr;
+
+ const SymExpr *LHS = SIE->getLHS();
+ const llvm::APSInt &RHS = SIE->getRHS();
+
+ if (RHS.isNegative())
+// TODO: Handle negative values.
+return nullptr;
+
+ ConstraintRangeTy Ranges = St->get();
+ for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E;
+ ++I) {
+if (LHS == I.getKey()) {
+ const auto D = I.getData();
+ for (auto I = D.begin(); I != D.end(); ++I) {
+if (I->From().isUnsigned() != RHS.isUnsigned())
+ // TODO: Handle sign conversions.
+ return nullptr;
+if (I->From().getBitWidth() != RHS.getBitWidth())
+ // TODO: Promote values.
+ return nullptr;
+if (I->From().isNegative())
+ // TODO: Handle negative range values
+ return nullptr;
+llvm::APSInt Lower;
+llvm::APSInt Upper;
+if (Opc == BO_Add) {
+ Lower = I->From() + RHS;
+ Upper = I->To() + RHS;
+} else if (Opc == BO_Sub) {
+ if (RHS > I->From())
+return nullptr;
+ Lower = I->From() - RHS;
+ Upper = I->To() - RHS;
+} else if (Opc == BO_Div) {
+ Lower = I->From() / RHS;
+ Upper = I->To() / RHS;
+}
+SymbolRef Sym = V.getAsSymbol();
+RangeSet RS =
+getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+// TODO: This only evaluates the first range. Evaluate all ranges.
+return RS.isEmpty() ? nullptr : St->set(Sym, RS);
+ }
+}
+ }
+ return nullptr;
+}
Index: lib/StaticAnalyzer/Core/ExprEngineC.cpp
===
--- lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -98,7 +98,9 @@
}
state = state->BindExpr(B, LCtx, Result);
- Bldr.generateNode(B, *it, state);
+ ProgramStateRef state2 =
+ getConstraintManager().evalRangeOp(state, Result);
+ Bldr.generateNode(B, *it, state2 ? state2 : state);
continue;
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
@@ -142,13 +142,15 @@
/// Scan all symbols referenced by the constraints. If the symbol is not
/// alive, remove it.
virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
- SymbolReaper& SymReaper) = 0;
+ SymbolReaper &SymReaper) = 0;
- virtual void print(ProgramStateRef state,
- raw_ostream &Out,
- const char* nl,
+ vir
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
xazax.hun added a comment. Can't you reuse somehow some machinery already available to evaluate the arithmetic operators? Those should already handle most of your TODOs and overflows. Repository: rL LLVM https://reviews.llvm.org/D36471 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D36471: [StaticAnalyzer] Try to calculate arithmetic result when operand has a range of possible values
danielmarjamaki created this revision.
In the code below the division result should be a value between 5 and 25.
if (a >= 10 && a <= 50) {
int b = a / 2;
}
This patch will calculate results for additions, subtractions and divisions.
I intentionally do not try to handle all possible cases that can be handled. I
want to know if my approach is ok.
Repository:
rL LLVM
https://reviews.llvm.org/D36471
Files:
include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
lib/StaticAnalyzer/Core/ExprEngineC.cpp
lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
test/Analysis/eval-range.c
Index: test/Analysis/eval-range.c
===
--- test/Analysis/eval-range.c
+++ test/Analysis/eval-range.c
@@ -0,0 +1,18 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core,debug.ExprInspection -verify %s
+
+void clang_analyzer_eval(int);
+
+void test1(int a) {
+ if (a >= 10 && a <= 50) {
+int b;
+
+b = a + 2;
+clang_analyzer_eval(b >= 12 && b <= 52); // expected-warning{{TRUE}}
+
+b = a - 2;
+clang_analyzer_eval(b >= 8 && b <= 48); // expected-warning{{TRUE}}
+
+b = a / 2;
+clang_analyzer_eval(b >= 5 && b <= 25); // expected-warning{{TRUE}}
+ }
+}
Index: lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -304,6 +304,8 @@
void print(ProgramStateRef State, raw_ostream &Out, const char *nl,
const char *sep) override;
+ ProgramStateRef evalRangeOp(ProgramStateRef state, SVal V) override;
+
//===--===//
// Implementation for interface from RangedConstraintManager.
//===--===//
@@ -741,3 +743,65 @@
}
Out << nl;
}
+
+ProgramStateRef RangeConstraintManager::evalRangeOp(ProgramStateRef St,
+SVal V) {
+ const SymExpr *SE = V.getAsSymExpr();
+ if (!SE)
+return nullptr;
+
+ const SymIntExpr *SIE = dyn_cast(SE);
+ if (!SIE)
+return nullptr;
+
+ const clang::BinaryOperatorKind Opc = SIE->getOpcode();
+
+ if (Opc != BO_Add && Opc != BO_Sub && Opc != BO_Div)
+return nullptr;
+
+ const SymExpr *LHS = SIE->getLHS();
+ const llvm::APSInt &RHS = SIE->getRHS();
+
+ if (RHS.isNegative())
+// TODO: Handle negative values.
+return nullptr;
+
+ ConstraintRangeTy Ranges = St->get();
+ for (ConstraintRangeTy::iterator I = Ranges.begin(), E = Ranges.end(); I != E;
+ ++I) {
+if (LHS == I.getKey()) {
+ const auto D = I.getData();
+ for (auto I = D.begin(); I != D.end(); ++I) {
+if (I->From().isUnsigned() != RHS.isUnsigned())
+ // TODO: Handle sign conversions.
+ return nullptr;
+if (I->From().getBitWidth() != RHS.getBitWidth())
+ // TODO: Promote values.
+ return nullptr;
+if (I->From().isNegative())
+ // TODO: Handle negative range values
+ return nullptr;
+llvm::APSInt Lower;
+llvm::APSInt Upper;
+if (Opc == BO_Add) {
+ Lower = I->From() + RHS;
+ Upper = I->To() + RHS;
+} else if (Opc == BO_Sub) {
+ if (RHS > I->From())
+return nullptr;
+ Lower = I->From() - RHS;
+ Upper = I->To() - RHS;
+} else if (Opc == BO_Div) {
+ Lower = I->From() / RHS;
+ Upper = I->To() / RHS;
+}
+SymbolRef Sym = V.getAsSymbol();
+RangeSet RS =
+getRange(St, Sym).Intersect(getBasicVals(), F, Lower, Upper);
+// TODO: This only evaluates the first range. Evaluate all ranges.
+return RS.isEmpty() ? nullptr : St->set(Sym, RS);
+ }
+}
+ }
+ return nullptr;
+}
Index: lib/StaticAnalyzer/Core/ExprEngineC.cpp
===
--- lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -98,6 +98,14 @@
}
state = state->BindExpr(B, LCtx, Result);
+
+ {
+ProgramStateRef St2 = getConstraintManager().evalRangeOp(state, Result);
+if (St2) {
+ Bldr.generateNode(B, *it, St2);
+ continue;
+}
+ }
Bldr.generateNode(B, *it, state);
continue;
}
Index: include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
===
--- include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
+++ include/clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h
@@ -142,13 +142,15 @@
/// Scan all symbols referenced by the constraints. If the symbol is not
/// alive, remove it.
virtual ProgramStateRef removeDeadBindings(ProgramStateRef state,
-
