[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:488-489
+static ProgramStateRef applyBitwiseRanges(ProgramStateRef State,
+  BasicValueFactory ,
+  RangeSet::Factory , RangeSet RS,
+  SymbolRef Sym) {

I recommend making this method non-static, so that not to have to pass BV and F 
around.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:510
+  const SymExpr *CurrentSym = SIE->getLHS();
+  if (const RangeSet *CurrentRS = Constraints.lookup(CurrentSym)) {
+const RangeSet NewRS = assumeNonZero(BV, F, CurrentSym, *CurrentRS);

If there's no current range in the map, it doesn't mean that there's no current 
range at all. Instead it means that the symbol is completely unconstrained and 
its range is equal to the whole domain of the type's possible values. You 
should use `RangeConstraintManager::getRange()` instead to retrieve the 
"default" range for the symbol. It would also always exist, so no need to check.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:517
+if (!NewRS.isEmpty()) {
+  State = State->set(CurrentSym, NewRS);
+} else {

Aaand at this point you might as well call `applyBitwiseRanges()` recursively. 
Or even call `assume()` recursively. This will be the better way to implement 
your loop idea, because now it's gonna be correct on all recursion depth levels.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso added a comment.

In overall I wanted to keep the [A, B] shape of the tests, but now they are 
more precise, thanks!




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:503
+
+  if (!BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+return State;

NoQ wrote:
> I suspect we have problems with bitwise OR here, which (unlike other 
> bitwise/shift ops) may be true when the LHS is 0.
Whoops, thanks!



Comment at: clang/test/Analysis/bitwise-ranges.cpp:28
+  unsigned int D = X << 1;
+  clang_analyzer_eval((D >= 1 && D <= 4294967295) || D == 0);
+  // expected-warning@-1 {{TRUE}}

NoQ wrote:
> This check is trivially true regardless of the value of D or constraints on 
> it.
Hm, yes. I felt like `D` equals to `E`, but that test fails, so I have just 
removed them.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso updated this revision to Diff 216731.
Charusso marked 7 inline comments as done.
Charusso edited the summary of this revision.
Charusso added a comment.

- Fix.


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/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
+
+void clang_analyzer_eval(int);
+
+void test_range(unsigned int X) {
+  if (X < 2 || X > 3)
+return;
+
+  clang_analyzer_eval(X >= 2 && X <= 3);
+  // expected-warning@-1 {{TRUE}}
+
+  // We have no non-null constraint range information available for 'A'.
+  unsigned int A = X | 8;
+  clang_analyzer_eval(A == 0);
+  // expected-warning@-1 {{FALSE}}
+
+  unsigned int B = X & 8;
+  clang_analyzer_eval((B >= 1 && B <= 8) || B == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  unsigned int C = X & 1;
+  clang_analyzer_eval(C == 1 || C == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  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 & (0xULL >> 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 & (0xULL >> 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,53 @@
   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 (except bitwise OR).
+static ProgramStateRef applyBitwiseRanges(ProgramStateRef State,
+  BasicValueFactory ,
+  RangeSet::Factory , RangeSet RS,
+  SymbolRef Sym) {
+  if (RS.isEmpty())
+return State;
+
+  // If we cannot be sure whether the value is non-null, do nothing.
+  const llvm::APSInt  = BV.getAPSIntType(Sym->getType()).getZeroValue();
+  if (!RS.Intersect(BV, F, Zero, Zero).isEmpty())
+return State;
+
+  const SymIntExpr *SIE = dyn_cast(Sym);
+  if (!SIE)
+return State;
+
+  // Bitwise OR could be null.
+  BinaryOperator::Opcode Op = SIE->getOpcode();
+  if (!BinaryOperator::isBitwiseOrShiftOp(Op) || Op == BO_Or)
+return State;
+
+  ConstraintRangeTy Constraints = State->get();
+  const SymExpr *CurrentSym = SIE->getLHS();
+  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 

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:503
+
+  if (!BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+return State;

I suspect we have problems with bitwise OR here, which (unlike other 
bitwise/shift ops) may be true when the LHS is 0.



Comment at: clang/test/Analysis/bitwise-ranges.cpp:16
+  unsigned int A = X | 8;
+  clang_analyzer_eval((A > 0 && A < 0) || A == 0);
+  // expected-warning@-1 {{FALSE}}

The LHS of || is always false here, regardless of the value of `A` or 
constraints on it. This test tests something strange.



Comment at: clang/test/Analysis/bitwise-ranges.cpp:24
+  unsigned int C = X & 1;
+  clang_analyzer_eval((C >= 1 && C <= 1) || C == 0);
+  // expected-warning@-1 {{TRUE}}

The LHS of || is equivalent to `C == 1`.



Comment at: clang/test/Analysis/bitwise-ranges.cpp:28
+  unsigned int D = X << 1;
+  clang_analyzer_eval((D >= 1 && D <= 4294967295) || D == 0);
+  // expected-warning@-1 {{TRUE}}

This check is trivially true regardless of the value of D or constraints on it.



Comment at: clang/test/Analysis/bitwise-ranges.cpp:32
+  unsigned int E = X >> 1;
+  clang_analyzer_eval((E >= 1 && E <= 4294967295) || E == 0);
+  // expected-warning@-1 {{TRUE}}

Same here.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:496
+  // as a bitwise operation result could be null.
+  if (RS.getConcreteValue() && RS.getConcreteValue()->getExtValue() == 0)
+return State;

NoQ wrote:
> Instead of "we know that the value is null", we should write "we //don't// 
> know that the value is //non-//null". I.e. if we're not sure, we must still 
> do an early return.
Oh, fail. Thanks!



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:507
+  ConstraintRangeTy Constraints = State->get();
+  for (const SymbolRef CurrentSym : SIE->symbols()) {
+if (CurrentSym == SIE)

NoQ wrote:
> This loop doesn't make sense. When your expression looks like `(((a + b) + c) 
> + d) & (e + f)`, you don't want to iterate separately over `a`, `b`, `c`, 
> `d`, `e`, `f`; but that's what this loop would do. You should only look at 
> the LHS and the RHS. If you want to descend further, do so recursively, so 
> that to keep track of the overall structure of the symbolic expression as 
> you're traversing it, rather than traversing sub-expressions in an 
> essentially random order.
It is rather sequential in the bitwise world, but I think if you would look 
only at the LHS `SymExpr`, it should be enough. Also I would like to avoid 
extra overhead, that `symbols()` business was large enough. Thanks!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso updated this revision to Diff 212440.
Charusso marked 6 inline comments as done.
Charusso added a comment.

- Fix.


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/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,38 @@
+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,debug.ExprInspection \
+// RUN:  -verify %s
+
+void clang_analyzer_eval(int);
+
+void test_range(unsigned int X) {
+  if (X < 2 || X > 3)
+return;
+
+  clang_analyzer_eval(X >= 2 && X <= 3);
+  // expected-warning@-1 {{TRUE}}
+
+  // We have no non-null constraint range information available for 'A'.
+  unsigned int A = X | 8;
+  clang_analyzer_eval((A > 0 && A < 0) || A == 0);
+  // expected-warning@-1 {{FALSE}}
+
+  unsigned int B = X & 8;
+  clang_analyzer_eval((B >= 1 && B <= 8) || B == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  unsigned int C = X & 1;
+  clang_analyzer_eval((C >= 1 && C <= 1) || C == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  unsigned int D = X << 1;
+  clang_analyzer_eval((D >= 1 && D <= 4294967295) || D == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  unsigned int E = X >> 1;
+  clang_analyzer_eval((E >= 1 && E <= 4294967295) || E == 0);
+  // expected-warning@-1 {{TRUE}}
+
+  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 & (0xULL >> 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 & (0xULL >> 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,51 @@
   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 ,
+  RangeSet::Factory , RangeSet RS,
+  SymbolRef Sym) {
+  if (RS.isEmpty())
+return State;
+
+  // If we cannot be sure whether the value is non-null, do nothing.
+  const llvm::APSInt  = BV.getAPSIntType(Sym->getType()).getZeroValue();
+  if (!RS.Intersect(BV, F, Zero, Zero).isEmpty())
+return State;
+
+  const SymIntExpr *SIE = dyn_cast(Sym);
+  if (!SIE)
+return State;
+
+  if (!BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+return State;
+
+  ConstraintRangeTy Constraints = State->get();
+  const SymExpr *CurrentSym = SIE->getLHS();
+  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 

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:496
+  // as a bitwise operation result could be null.
+  if (RS.getConcreteValue() && RS.getConcreteValue()->getExtValue() == 0)
+return State;

Instead of "we know that the value is null", we should write "we //don't// know 
that the value is //non-//null". I.e. if we're not sure, we must still do an 
early return.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:507
+  ConstraintRangeTy Constraints = State->get();
+  for (const SymbolRef CurrentSym : SIE->symbols()) {
+if (CurrentSym == SIE)

This loop doesn't make sense. When your expression looks like `(((a + b) + c) + 
d) & (e + f)`, you don't want to iterate separately over `a`, `b`, `c`, `d`, 
`e`, `f`; but that's what this loop would do. You should only look at the LHS 
and the RHS. If you want to descend further, do so recursively, so that to keep 
track of the overall structure of the symbolic expression as you're traversing 
it, rather than traversing sub-expressions in an essentially random order.



Comment at: clang/test/Analysis/bitwise-ranges.cpp:21
+
+  // CHECK: { "symbol": "reg_$0", "range": "{ [2, 3] }" }
+  // CHECK: { "symbol": "(reg_$0) & 1U", "range": "{ [1, 1] }" 
}

This test accidentally tests debug prints. We don't want to test debug prints 
here. I suggest:
```lang=c++
clang_analyzer_eval(X >= 2 && X <= 3); // expected-warning{{TRUE}}
```


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso marked 3 inline comments as done.
Charusso added a comment.

In D65239#1599889 , @NoQ wrote:

> Aha, great, the overall structure of the code is correct!


Thanks! Now it is more formal. The only problem it does not change anything on 
LLVM reports, where we are working with the 
`test_non_null_lhs_range_to_null_result_feasible` test case.




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:477
+
+  // For all of the bitwise operations,
+  // if they remain in that 'SymIntExpr' form that means we cannot evaluate the

NoQ wrote:
> Let's do some math.
> 
> Suppose `$x` is in range `[2, 3]`. In this case the true range for `$x & 1` 
> is `[0, 1]` (because `2 & 1 == 0` and `3 & 1 == 1`).
> 
> The range for `$x & 8` would be `[0, 0]`.
> 
> The range for `$x | 8` would be `[10, 11]`.
> 
> The range for `$x << 1` would be `[4, 4], [6, 6]`.
> 
> The range for `$x >> 1` would be `[0, 1]`.
> 
> None of these ranges are contained within `[2, 3]`. In fact, none of them 
> even contain either `2` or `3`. However, when you intersect the resulting 
> range with `[2, 3]`, you make sure that the resulting range is contained 
> within `[2, 3]`. I don't think that's correct.
I have added a test case to see how bad our evaluation at the moment. That is 
why I saw that we are just narrowing ranges and the contradiction only could 
happen at concrete zero range based.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

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", "range": "{ [2, 3] }" }
+  // CHECK: { "symbol": "(reg_$0) & 1U", "range": "{ [1, 1] }" }
+  // CHECK: { "symbol": "(reg_$0) & 8U", "range": "{ [1, 8] }" }
+  // CHECK: { "symbol": "(reg_$0) << 1U", "range": "{ [1, 4294967295] }" }
+  // CHECK: { "symbol": "(reg_$0) >> 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 & (0xULL >> 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 & (0xULL >> 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 ,
+  RangeSet::Factory , 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(Sym);
+  if (!SIE)
+return State;
+
+  if (!BinaryOperator::isBitwiseOrShiftOp(SIE->getOpcode()))
+return State;
+
+  ConstraintRangeTy Constraints = State->get();
+  for (const SymbolRef CurrentSym : SIE->symbols()) {
+if (CurrentSym == SIE)
+  continue;
+
+if (const RangeSet *CurrentRS = Constraints.lookup(CurrentSym)) {
+  const RangeSet NewRS = 

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

Aha, great, the overall structure of the code is correct!




Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:477
+
+  // For all of the bitwise operations,
+  // if they remain in that 'SymIntExpr' form that means we cannot evaluate the

Let's do some math.

Suppose `$x` is in range `[2, 3]`. In this case the true range for `$x & 1` is 
`[0, 1]` (because `2 & 1 == 0` and `3 & 1 == 1`).

The range for `$x & 8` would be `[0, 0]`.

The range for `$x | 8` would be `[10, 11]`.

The range for `$x << 1` would be `[4, 4], [6, 6]`.

The range for `$x >> 1` would be `[0, 1]`.

None of these ranges are contained within `[2, 3]`. In fact, none of them even 
contain either `2` or `3`. However, when you intersect the resulting range with 
`[2, 3]`, you make sure that the resulting range is contained within `[2, 3]`. 
I don't think that's correct.



Comment at: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp:487-488
+if (!PreviousRS->isEmpty()) {
+  RangeSet::iterator I = PreviousRS->begin();
+  Result = Result.Intersect(BV, F, I->From(), I->To());
+}

You're only taking a single segment out of the range. The range may be a union 
of multiple segments. You should intersect with the whole range instead.


Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D65239/new/

https://reviews.llvm.org/D65239



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D65239: [analyzer] RangeConstraintManager: Apply constraint ranges of bitwise operations

[Csaba Dabis via Phabricator via cfe-commits]

Charusso created this revision.
Charusso added a reviewer: NoQ.
Charusso added a project: clang.
Herald added subscribers: cfe-commits, dkrupp, donat.nagy, Szelethus, 
mikhail.ramalho, a.sidorin, szepet, baloghadamsoftware, xazax.hun.

We do not support evaluating bitwise operations, so that when we check for
their results being null previously we did a state-split because it is a
fresh new symbol and it could be null and non-null as well. The problem was
the left-hand side operand of the operation already has constraint range
informations which could contradicts with the current new assumption.
>From now we apply the constraint range informations of the left-hand side
operand in order to prevent false assumptions.


Repository:
  rC Clang

https://reviews.llvm.org/D65239

Files:
  clang/include/clang/AST/Expr.h
  
clang/include/clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h
  clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
  clang/test/Analysis/bitwise-nullability.cpp

Index: clang/test/Analysis/bitwise-nullability.cpp
===
--- /dev/null
+++ clang/test/Analysis/bitwise-nullability.cpp
@@ -0,0 +1,26 @@
+// RUN: %clang_analyze_cc1 -analyzer-checker=core -verify %s
+
+// expected-no-diagnostics:
+// We do not support evaluating bitwise operations, so that when we check for
+// their results being null previously we did a state-split because it is a
+// fresh new symbol and it could be null and non-null as well. The problem was
+// the left-hand side operand of the operation already has constraint range
+// informations which could contradicts with the current new assumption.
+// From now we apply the constraint range informations of the left-hand side
+// operand in order to prevent false assumptions.
+
+typedef unsigned long long uint64_t;
+
+void test_narrowing_down_range(uint64_t Magic) {
+  uint64_t MaskedMagic = Magic & (0xULL >> 13);
+
+  if (Magic) {
+// no-warning: 'Assuming 'Magic' is 0' was here.
+return;
+  }
+
+  if (MaskedMagic) {
+// no-warning: 'Assuming 'MaskedMagic' is not equal to 0' was here.
+(void)(1 / Magic);
+  }
+}
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -443,16 +443,17 @@
 /// Apply implicit constraints for bitwise OR- and AND-.
 /// For unsigned types, bitwise OR with a constant always returns
 /// a value greater-or-equal than the constant, and bitwise AND
-/// returns a value less-or-equal then the constant.
+/// returns a value less-or-equal than the constant.
+/// Also apply the previously applied constraint range information of the
+/// left-hand side operand of \p SIE in order to prevent false assumptions.
 ///
-/// Pattern matches the expression \p Sym against those rule,
+/// Pattern matches the expression \p SIE against those rules,
 /// and applies the required constraints.
-/// \p Input Previously established expression range set
-static RangeSet applyBitwiseConstraints(
-BasicValueFactory ,
-RangeSet::Factory ,
-RangeSet Input,
-const SymIntExpr* SIE) {
+/// \p Result Previously established expression range set
+static RangeSet applyBitwiseConstraints(ProgramStateRef State,
+BasicValueFactory ,
+RangeSet::Factory , RangeSet Result,
+const SymIntExpr *SIE) {
   QualType T = SIE->getType();
   bool IsUnsigned = T->isUnsignedIntegerType();
   const llvm::APSInt  = SIE->getRHS();
@@ -461,19 +462,34 @@
 
   // For unsigned types, the output of bitwise-or is bigger-or-equal than RHS.
   if (Operator == BO_Or && IsUnsigned)
-return Input.Intersect(BV, F, RHS, BV.getMaxValue(T));
+return Result.Intersect(BV, F, RHS, BV.getMaxValue(T));
 
   // Bitwise-or with a non-zero constant is always non-zero.
   if (Operator == BO_Or && RHS != Zero)
-return assumeNonZero(BV, F, SIE, Input);
+return assumeNonZero(BV, F, SIE, Result);
 
   // For unsigned types, or positive RHS,
   // bitwise-and output is always smaller-or-equal than RHS (assuming two's
   // complement representation of signed types).
   if (Operator == BO_And && (IsUnsigned || RHS >= Zero))
-return Input.Intersect(BV, F, BV.getMinValue(T), RHS);
+Result = Result.Intersect(BV, F, BV.getMinValue(T), RHS);
+
+  // For all of the bitwise operations,
+  // if they remain in that 'SymIntExpr' form that means we cannot evaluate the
+  // operation properly and they remain range-based. At this point we would
+  // introduce a completely new 'RangeSet' with new assumptions and we would
+  // forget about the previous constraint range information of the left-hand
+  // side operand of 'SIE'. Here we apply the previously applied range to the