ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: martong, steakhal, NoQ.
ASDenysPetrov added a project: clang.
Herald added subscribers: manas, dkrupp, donat.nagy, Szelethus,
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware, xazax.hun.
Herald added a project: All.
ASDenysPetrov requested review of this revision.
Herald added a subscriber: cfe-commits.
Infer range using associated unequal symbols from DisequalityMap.
Example:
if(x == 42)
if(x != y)
y; // [-2147483648, 41]U[43, 2147483647]
NOTE: Currently, this revision causes test failure due to assertion in related
to `IteratorModeling.cpp` in `relateSymbols` on line
`assert(isa<SymIntExpr>(CompSym) && "Symbol comparison must be a
`SymIntExpr`");`. It needs to be fixed in some way before loading. The revision
is exposed to show the motivation for D130372
<https://reviews.llvm.org/D130372>.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D131006
Files:
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/range-inferring-from-disequality-map.cpp
Index: clang/test/Analysis/range-inferring-from-disequality-map.cpp
===================================================================
--- /dev/null
+++ clang/test/Analysis/range-inferring-from-disequality-map.cpp
@@ -0,0 +1,57 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
+
+template<typename T>
+void clang_analyzer_value(T x);
+
+void test1(int x, int tmp) {
+ if(tmp != 0)
+ if(x != tmp)
+ clang_analyzer_value(x); // expected-warning {{32s:{ [0, 0] }}}
+ // TODO: TODO: Keep x range correct even if associated disequalities are
+ // already dead.
+ (void)tmp; // Keep alive.
+}
+
+void test2(int x, int tmp) {
+ if(x != tmp)
+ if(tmp < 0)
+ clang_analyzer_value(x); // expected-warning {{32s:{ [0, 2147483647] }}}
+ // TODO: TODO: Keep x range correct even if associated disequalities are
+ // already dead.
+ (void)tmp; // Keep alive.
+}
+
+void test3(int x, int tmp) {
+ if(x != tmp)
+ if(tmp > 42 && tmp < 87)
+ clang_analyzer_value(x); // expected-warning {{32s:{ [-2147483648, 42], [87, 2147483647] }}}
+ // TODO: TODO: Keep x range correct even if associated disequalities are
+ // already dead.
+ (void)tmp; // Keep alive.
+}
+
+void test4(int x, int tmp1, int tmp2) {
+ if(x != tmp1) {
+ if (tmp1 < 0 && tmp2 > 0) {
+ clang_analyzer_value(x); // expected-warning {{32s:{ [0, 2147483647] }}}
+ if(x != tmp2)
+ clang_analyzer_value(x); // expected-warning {{32s:{ [0, 0] }}}
+ }
+ }
+ // TODO: TODO: Keep x range correct even if associated disequalities are
+ // already dead.
+ (void)tmp1; // Keep alive.
+ (void)tmp2; // Keep alive.
+}
+
+void test5(int x, int tmp1, int tmp2) {
+ if (tmp1 < 42 && tmp2 >= 42)
+ if(x != tmp1 && x != tmp2)
+ // TODO: This condition should be infeasible.
+ // Thus, the branch should be unreachable.
+ clang_analyzer_value(x); // expected-warning {{{ empty }}}
+ // TODO: TODO: Keep x range correct even if associated disequalities are
+ // already dead.
+ (void)tmp1; // Keep alive.
+ (void)tmp2; // Keep alive.
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -1327,6 +1327,8 @@
// Of course, we should take the constraint directly
// associated with this symbol into consideration.
getConstraint(State, Sym),
+ // Use inverted ranges from DisequalityMap.
+ getInvertedRangeFromDisequalityMap(State, Sym),
// Apart from the Sym itself, we can infer quite a lot if
// we look into subexpressions of Sym.
Visit(Sym));
@@ -1490,6 +1492,39 @@
return RangeFactory.deletePoint(Domain, IntType.getZeroValue());
}
+ Optional<RangeSet> getInvertedRangeFromDisequalityMap(ProgramStateRef State,
+ SymbolRef Sym) {
+ QualType T = Sym->getType();
+ // We only support integral types.
+ if (!T->isIntegralOrEnumerationType())
+ return llvm::None;
+
+ EquivalenceClass EC = EquivalenceClass::find(State, Sym);
+ const ClassSet *CS = State->get<DisequalityMap>(EC);
+
+ if (!CS)
+ return llvm::None;
+
+ bool IsFirst = true;
+ RangeSet RS = RangeFactory.getEmptySet();
+ for (EquivalenceClass EC : *CS) {
+ if (const RangeSet *RSPtr = getConstraint(State, EC)) {
+ if (IsFirst) {
+ IsFirst = false;
+ RS = *RSPtr;
+ } else
+ RS = RangeFactory.unite(RS, *RSPtr);
+ }
+ }
+
+ if (IsFirst)
+ return llvm::None;
+
+ RS = RangeFactory.castTo(RS, T);
+ RS = RangeFactory.invert(RS);
+ return RS;
+ }
+
template <typename ProduceNegatedSymFunc>
Optional<RangeSet> getRangeForNegatedExpr(ProduceNegatedSymFunc F,
QualType T) {
@@ -3217,8 +3252,12 @@
void RangeConstraintManager::printValue(raw_ostream &Out, ProgramStateRef State,
SymbolRef Sym) {
const RangeSet RS = getRange(State, Sym);
- Out << RS.getBitWidth() << (RS.isUnsigned() ? "u:" : "s:");
- RS.dump(Out);
+ if (RS.isEmpty())
+ Out << "{ empty }";
+ else {
+ Out << RS.getBitWidth() << (RS.isUnsigned() ? "u:" : "s:");
+ RS.dump(Out);
+ }
}
static std::string toString(const SymbolRef &Sym) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
