Charusso updated this revision to Diff 211956.
Charusso edited the summary of this revision.
Charusso added a comment.
- Restrict the generic contradiction-based range evaluation to only affect that
left-hand side operands which constraint range are concrete zero.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D65239/new/
https://reviews.llvm.org/D65239
Files:
clang/include/clang/AST/Expr.h
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h
clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/bitwise-nullability.cpp
clang/test/Analysis/bitwise-ranges.cpp
Index: clang/test/Analysis/bitwise-ranges.cpp
===================================================================
--- /dev/null
+++ clang/test/Analysis/bitwise-ranges.cpp
@@ -0,0 +1,30 @@
+// RUN: %clang_analyze_cc1 \
+// RUN: -analyzer-checker=core,debug.ExprInspection \
+// RUN: -verify %s 2>&1 | FileCheck %s
+
+void clang_analyzer_printState();
+
+void test_range(unsigned int X) {
+ if (X < 2 || X > 3)
+ return;
+
+ unsigned int A = X & 1;
+ unsigned int B = X & 8;
+ unsigned int C = X | 8;
+ unsigned int D = X << 1;
+ unsigned int E = X >> 1;
+
+ if (A && B && C && D && E) {}
+
+ clang_analyzer_printState();
+
+ // CHECK: { "symbol": "reg_$0<unsigned int X>", "range": "{ [2, 3] }" }
+ // CHECK: { "symbol": "(reg_$0<unsigned int X>) & 1U", "range": "{ [1, 1] }" }
+ // CHECK: { "symbol": "(reg_$0<unsigned int X>) & 8U", "range": "{ [1, 8] }" }
+ // CHECK: { "symbol": "(reg_$0<unsigned int X>) << 1U", "range": "{ [1, 4294967295] }" }
+ // CHECK: { "symbol": "(reg_$0<unsigned int X>) >> 1U", "range": "{ [1, 4294967295] }" }
+
+ void(X / 0);
+ // expected-warning@-1 {{division by zero is undefined}}
+ // expected-warning@-2 {{Division by zero}}
+}
Index: clang/test/Analysis/bitwise-nullability.cpp
===================================================================
--- /dev/null
+++ clang/test/Analysis/bitwise-nullability.cpp
@@ -0,0 +1,38 @@
+// RUN: %clang_analyze_cc1 \
+// RUN: -analyzer-checker=core \
+// RUN: -analyzer-output=text -verify %s
+
+typedef unsigned long long uint64_t;
+
+void test_null_lhs_range_to_non_null_result_infeasible(uint64_t Magic) {
+ uint64_t MaskedMagic = Magic & (0xffffffffffffffffULL >> 13);
+
+ if (Magic) {
+ // no-note: 'Assuming 'Magic' is 0' was here.
+ return;
+ }
+
+ if (MaskedMagic) {
+ // no-note: 'Assuming 'MaskedMagic' is not equal to 0' was here.
+ (void)(1 / Magic); // no-warning
+ }
+}
+
+void test_non_null_lhs_range_to_null_result_feasible(uint64_t Magic) {
+ uint64_t MaskedMagic = Magic & (0xffffffffffffffffULL >> 13);
+
+ if (!Magic) {
+ // expected-note@-1 {{Assuming 'Magic' is not equal to 0}}
+ // expected-note@-2 {{Taking false branch}}
+ return;
+ }
+
+ if (!MaskedMagic) {
+ // expected-note@-1 {{Assuming 'MaskedMagic' is 0}}
+ // expected-note@-2 {{Taking true branch}}
+ (void)(1 / !Magic);
+ // expected-note@-1 {{'Magic' is not equal to 0}}
+ // expected-note@-2 {{Division by zero}}
+ // expected-warning@-3 {{Division by zero}}
+ }
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -476,6 +476,55 @@
return Input;
}
+// We do not support evaluating bitwise operations, so that when we check for
+// their results being null we create a new assumption whether the current new
+// symbol is null or non-null. If we are on the non-null assumption's branch
+// we need to check the left-hand side operand's constraint range informations:
+// - It if contradicts with the forming new range 'RS' then it returns a null
+// state as it is an impossible condition.
+// - Otherwise it removes the nullability from its ranges as we know that it
+// cannot be null on that branch.
+static ProgramStateRef applyBitwiseRanges(ProgramStateRef State,
+ BasicValueFactory &BV,
+ RangeSet::Factory &F, RangeSet RS,
+ SymbolRef Sym) {
+ if (RS.isEmpty())
+ return State;
+
+ // If the 'RS' is zero we cannot apply new range informations at that branch
+ // as a bitwise operation result could be null.
+ if (RS.getConcreteValue() && RS.getConcreteValue()->getExtValue() == 0)
+ return State;
+
+ const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Sym);
+ if (!SIE)
+ return State;
+
+ if (!BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+ return State;
+
+ ConstraintRangeTy Constraints = State->get<ConstraintRange>();
+ for (const SymbolRef CurrentSym : SIE->symbols()) {
+ if (CurrentSym == SIE)
+ continue;
+
+ if (const RangeSet *CurrentRS = Constraints.lookup(CurrentSym)) {
+ const RangeSet NewRS = assumeNonZero(BV, F, CurrentSym, *CurrentRS);
+
+ // If the 'NewRS' is not empty it means the 'CurrentSym' is not assumed
+ // to be concrete zero, so it does not contradicts with the non-null
+ // assumption and we could apply the new constraint ranges.
+ if (!NewRS.isEmpty()) {
+ State = State->set<ConstraintRange>(CurrentSym, NewRS);
+ } else {
+ return nullptr;
+ }
+ }
+ }
+
+ return State;
+}
+
RangeSet RangeConstraintManager::getRange(ProgramStateRef State,
SymbolRef Sym) {
ConstraintRangeTy::data_type *V = State->get<ConstraintRange>(Sym);
@@ -567,6 +616,10 @@
// [Int-Adjustment+1, Int-Adjustment-1]
// Notice that the lower bound is greater than the upper bound.
RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, Upper, Lower);
+
+ if (!(St = applyBitwiseRanges(St, getBasicVals(), F, New, Sym)))
+ return nullptr;
+
return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
}
@@ -582,6 +635,10 @@
// [Int-Adjustment, Int-Adjustment]
llvm::APSInt AdjInt = AdjustmentType.convert(Int) - Adjustment;
RangeSet New = getRange(St, Sym).Intersect(getBasicVals(), F, AdjInt, AdjInt);
+
+ if (!(St = applyBitwiseRanges(St, getBasicVals(), F, New, Sym)))
+ return nullptr;
+
return New.isEmpty() ? nullptr : St->set<ConstraintRange>(Sym, New);
}
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h
@@ -86,6 +86,10 @@
symbol_iterator symbol_begin() const { return symbol_iterator(this); }
static symbol_iterator symbol_end() { return symbol_iterator(); }
+ llvm::iterator_range<symbol_iterator> symbols() const {
+ return llvm::make_range(symbol_begin(), symbol_end());
+ }
+
virtual unsigned computeComplexity() const = 0;
/// Find the region from which this symbol originates.
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h
@@ -82,6 +82,8 @@
};
enum { BaseBits = 2, BaseMask = 0x3 };
+ using iterator = SymExpr::symbol_iterator;
+
protected:
const void *Data = nullptr;
@@ -196,7 +198,7 @@
void dumpToStream(raw_ostream &OS) const;
void dump() const;
- SymExpr::symbol_iterator symbol_begin() const {
+ iterator symbol_begin() const {
const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
if (SE)
return SE->symbol_begin();
@@ -204,8 +206,10 @@
return SymExpr::symbol_iterator();
}
- SymExpr::symbol_iterator symbol_end() const {
- return SymExpr::symbol_end();
+ iterator symbol_end() const { return SymExpr::symbol_end(); }
+
+ llvm::iterator_range<iterator> symbols() const {
+ return llvm::make_range(symbol_begin(), symbol_end());
}
};
Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
===================================================================
--- clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
+++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
@@ -118,6 +118,7 @@
RangeSet Negate(BasicValueFactory &BV, Factory &F) const;
void print(raw_ostream &os) const;
+ LLVM_DUMP_METHOD void dump() const { print(llvm::errs()); }
bool operator==(const RangeSet &other) const {
return ranges == other.ranges;
Index: clang/include/clang/AST/Expr.h
===================================================================
--- clang/include/clang/AST/Expr.h
+++ clang/include/clang/AST/Expr.h
@@ -3486,6 +3486,11 @@
static bool isBitwiseOp(Opcode Opc) { return Opc >= BO_And && Opc <= BO_Or; }
bool isBitwiseOp() const { return isBitwiseOp(getOpcode()); }
+ static bool isBitwiseOrShiftOp(Opcode Opc) {
+ return isBitwiseOp(Opc) || isShiftOp(Opc);
+ }
+ bool isBitwiseOrShiftOp() const { return isBitwiseOrShiftOp(getOpcode()); }
+
static bool isRelationalOp(Opcode Opc) { return Opc >= BO_LT && Opc<=BO_GE; }
bool isRelationalOp() const { return isRelationalOp(getOpcode()); }
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
