[analyzer][NFC] Factor out SymbolManager::get<*> (#121781)

Replace the family of `SymbolManager::get*Symbol(...)` member functions
with a single generic `SymbolManager::get<*>` member function.

[analyzer][NFC] Migrate {SymInt,IntSym}Expr to use APSIntPtr (4/4) (#120438)

[analyzer][NFC] Migrate loc::ConcreteInt to use APSIntPtr (3/4) (#120437)

[analyzer][NFC] Migrate nonloc::ConcreteInt to use APSIntPtr (2/4) (#120436)

[analyzer][NFC] Introduce APSIntPtr, a safe wrapper of APSInt (1/4) (#120435)

One could create dangling APSInt references in various ways in the past, that were sometimes assumed to be persisted in

[analyzer][NFC] Introduce APSIntPtr, a safe wrapper of APSInt (1/4) (#120435)

One could create dangling APSInt references in various ways in the past, that were sometimes assumed to be persisted in the BasicValueFactor.

One should always use BasicValueFactory to create persistent APSInts, that could be used by ConcreteInts or SymIntExprs and similar long-living objects.
If one used a temporary or local variables for this, these would dangle.
To enforce the contract of the analyzer BasicValueFactory and the uses of APSInts, let's have a dedicated strong-type for this.

The idea is that APSIntPtr is always owned by the BasicValueFactory, and that is the only component that can construct it.

These PRs are all NFC - besides fixing dangling APSInt references.

show more ...

[analyzer] EvalBinOpLL should return Unknown less often (#114222)

SValBuilder::getKnownValue, getMinValue, getMaxValue use
SValBuilder::simplifySVal.

simplifySVal does repeated simplification un

[analyzer] EvalBinOpLL should return Unknown less often (#114222)

SValBuilder::getKnownValue, getMinValue, getMaxValue use
SValBuilder::simplifySVal.

simplifySVal does repeated simplification until a fixed-point is
reached. A single step is done by SimpleSValBuilder::simplifySValOnce,
using a Simplifier visitor. That will basically decompose SymSymExprs,
and apply constant folding using the constraints we have in the State.
Once it decomposes a SymSymExpr, it simplifies both sides and then uses
the SValBuilder::evalBinOp to reconstruct the same - but now simpler -
SymSymExpr, while applying some caching to remain performant.

This decomposition, and then the subsequent re-composition poses new
challenges to the SValBuilder::evalBinOp, which is built to handle
expressions coming from real C/C++ code, thus applying some implicit
assumptions.

One previous assumption was that nobody would form an expression like
"((int*)0) - q" (where q is an int pointer), because it doesn't really
makes sense to write code like that.

However, during simplification, we may end up with a call to evalBinOp
similar to this.

To me, simplifying a SymbolRef should never result in Unknown or Undef,
unless it was Unknown or Undef initially or, during simplification we
realized that it's a division by zero once we did the constant folding,
etc.

In the following case the simplified SVal should not become UnknownVal:
```c++
void top(char *p, char *q) {
int diff = p - q; // diff: reg<p> - reg<q>
if (!p) // p: NULL
simplify(diff); // diff after simplification should be: 0(loc) - reg<q>
}
```

Returning Unknown from the simplifySVal can weaken analysis precision in
other places too, such as in SValBuilder::getKnownValue, getMinValue, or
getMaxValue because we call simplifySVal before doing anything else.

For nonloc::SymbolVals, this loss of precision is critical, because for
those the SymbolRef carries an accurate type of the encoded computation,
thus we should at least have a conservative upper or lower bound that we
could return from getMinValue or getMaxValue - yet we would just return
nullptr.

```c++
const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
SVal V) {
return getConstValue(state, simplifySVal(state, V));
}

const llvm::APSInt *SimpleSValBuilder::getMinValue(ProgramStateRef state,
SVal V) {
V = simplifySVal(state, V);

if (const llvm::APSInt *Res = getConcreteValue(V))
return Res;

if (SymbolRef Sym = V.getAsSymbol())
return state->getConstraintManager().getSymMinVal(state, Sym);

return nullptr;
}
```

For now, I don't plan to make the simplification bullet-proof, I'm just
explaining why I made this change and what you need to look out for in
the future if you see a similar issue.

CPP-5750

show more ...

[analyzer] Let the checkers query upper and lower bounds on symbols (#74141)

This commit extends the class `SValBuilder` with the methods
`getMinValue()` and `getMaxValue()` to that work like
`SVa

[analyzer] Let the checkers query upper and lower bounds on symbols (#74141)

This commit extends the class `SValBuilder` with the methods
`getMinValue()` and `getMaxValue()` to that work like
`SValBuilder::getKnownValue()` but return the minimal/maximal possible
value the `SVal` is not perfectly constrained.

This extension of the ConstraintManager API is discussed at:
https://discourse.llvm.org/t/expose-the-inferred-range-information-in-warning-messages/75192

As a simple proof-of-concept application of this new API, this commit
extends a message from `core.BitwiseShift` with some range information
that reports the assumptions of the analyzer.

My main motivation for adding these methods is that I'll also want to
use them in `ArrayBoundCheckerV2` to make the error messages less
awkward, but I'm starting with this simpler and less important usecase
because I want to avoid merge conflicts with my other commit
https://github.com/llvm/llvm-project/pull/72107 which is currently under
review.

The testcase `too_large_right_operand_compound()` shows a situation
where querying the range information does not work (and the extra
information is not added to the error message). This also affects the
debug utility `clang_analyzer_value()`, so the problem isn't in the
fresh code. I'll do some investigations to resolve this, but I think
that this commit is a step forward even with this limitation.

show more ...

[analyzer][NFC] Rework SVal kind representation (#71039)

The goal of this patch is to refine how the `SVal` base and sub-kinds
are represented by forming one unified enum describing the possible
S

[analyzer][NFC] Rework SVal kind representation (#71039)

The goal of this patch is to refine how the `SVal` base and sub-kinds
are represented by forming one unified enum describing the possible
SVals. This means that the `unsigned SVal::Kind` and the attached
bit-packing semantics would be replaced by a single unified enum. This
is more conventional and leads to a better debugging experience by
default. This eases the need of using debug pretty-printers, or the use
of runtime functions doing the printing for us like we do today by
calling `Val.dump()` whenever we inspect the values.

Previously, the first 2 bits of the `unsigned SVal::Kind` discriminated
the following quartet: `UndefinedVal`, `UnknownVal`, `Loc`, or `NonLoc`.
The rest of the upper bits represented the sub-kind, where the value
represented the index among only the `Loc`s or `NonLoc`s, effectively
attaching 2 meanings of the upper bits depending on the base-kind. We
don't need to pack these bits, as we have plenty even if we would use
just a plan-old `unsigned char`.

Consequently, in this patch, I propose to lay out all the (non-abstract)
`SVal` kinds into a single enum, along with some metadata (`BEGIN_Loc`,
`END_Loc`, `BEGIN_NonLoc`, `END_NonLoc`) artificial enum values, similar
how we do with the `MemRegions`.

Note that in the unified `SVal::Kind` enum, to differentiate
`nonloc::ConcreteInt` from `loc::ConcreteInt`, I had to prefix them with
`Loc` and `NonLoc` to resolve this ambiguity.
This should not surface in general, because I'm replacing the
`nonloc::Kind` enum items with `inline constexpr` global constants to
mimic the original behavior - and offer nicer spelling to these enum
values.

Some `SVal` constructors were not marked explicit, which I now mark as
such to follow best practices, and marked others as `/*implicit*/` to
clarify the intent.
During refactoring, I also found at least one function not marked
`LLVM_ATTRIBUTE_RETURNS_NONNULL`, so I did that.

The `TypeRetrievingVisitor` visitor had some accidental dead code,
namely: `VisitNonLocConcreteInt` and `VisitLocConcreteInt`.

Previously, the `SValVisitor` expected visit handlers of
`VisitNonLocXXXXX(nonloc::XXXXX)` and `VisitLocXXXXX(loc::XXXXX)`, where
I felt that envoding `NonLoc` and `Loc` in the name is not necessary as
the type of the parameter would select the right overload anyways, so I
simplified the naming of those visit functions.

The rest of the diff is a lot of times just formatting, because
`getKind()` by nature, frequently appears in switches, which means that
the whole switch gets automatically reformatted. I could probably undo
the formatting, but I didn't want to deviate from the rule unless
explicitly requested.

show more ...

[analyzer] Remove inaccurate legacy handling of bad bitwise shifts (#66647)

Previously, bitwise shifts with constant operands were validated by the
checker `core.UndefinedBinaryOperatorResult`. How

[analyzer] Remove inaccurate legacy handling of bad bitwise shifts (#66647)

Previously, bitwise shifts with constant operands were validated by the
checker `core.UndefinedBinaryOperatorResult`. However, this logic was
unreliable, and commit 25b9696b61e53a958e217bb3d0eab66350dc187f added
the dedicated checker `core.BitwiseShift` which validated the
preconditions of all bitwise shifts with a more accurate logic (that
uses the real types from the AST instead of the unreliable type
information encoded in `APSInt` objects).

This commit disables the inaccurate logic that could mark bitwise shifts
as 'undefined' and removes the redundant shift-related warning messages
from core.UndefinedBinaryOperatorResult. The tests that were validating
this logic are also deleted by this commit; but I verified that those
testcases trigger the expected bug reports from `core.BitwiseShift`. (I
didn't convert them to tests of `core.BitwiseShift`, because that
checker already has its own extensive test suite with many analogous
testcases.)

I hope that there will be a time when the constant folding will be
reliable, but until then we need hacky solutions like this improve the
quality of results.

show more ...

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is p

[clang] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Option

[clang] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Optional with
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[StaticAnalyzer] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the am

[StaticAnalyzer] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[clang] LLVM_FALLTHROUGH => [[fallthrough]]. NFC

With C++17 there is no Clang pedantic warning or MSVC C5051.

Reviewed By: aaron.ballman

Differential Revision: https://reviews.llvm.org/D131346

[analyzer][NFC] Prefer using isa<> instead getAs<> in conditions

Depends on D125709

Reviewed By: martong

Differential Revision: https://reviews.llvm.org/D127742

[analyzer][NFC] Relocate unary transfer functions

This is an initial step of removing the SimpleSValBuilder abstraction. The SValBuilder alone should be enough.

Reviewed By: martong

Differential R

[analyzer][NFC] Relocate unary transfer functions

This is an initial step of removing the SimpleSValBuilder abstraction. The SValBuilder alone should be enough.

Reviewed By: martong

Differential Revision: https://reviews.llvm.org/D126127

show more ...

[analyzer] Fix assertion failure after getKnownValue call

Depends on D126560. `getKnownValue` has been changed by the parent patch
in a way that simplification was removed. This is not correct when

[analyzer] Fix assertion failure after getKnownValue call

Depends on D126560. `getKnownValue` has been changed by the parent patch
in a way that simplification was removed. This is not correct when the
function is called by the Checkers. Thus, a new internal function is
introduced, `getConstValue`, which simply queries the constraint manager.
This `getConstValue` is used internally in the `SimpleSValBuilder` when a
binop is evaluated, this way we avoid the recursion into the `Simplifier`.

Differential Revision: https://reviews.llvm.org/D127285

show more ...

[analyzer] Track assume call stack to detect fixpoint

Assume functions might recurse (see `reAssume` or `tryRearrange`).
During the recursion, the State might not change anymore, that means we
reach

[analyzer] Track assume call stack to detect fixpoint

Assume functions might recurse (see `reAssume` or `tryRearrange`).
During the recursion, the State might not change anymore, that means we
reached a fixpoint. In this patch, we avoid infinite recursion of assume
calls by checking already visited States on the stack of assume function
calls. This patch renders the previous "workaround" solution (D47155)
unnecessary. Note that this is not an NFC patch. If we were to limit the
maximum stack depth of the assume calls to 1 then would it be equivalent
with the previous solution in D47155.

Additionally, in D113753, we simplify the symbols right at the beginning
of evalBinOpNN. So, a call to `simplifySVal` in `getKnownValue` (added
in D51252) is no longer needed.

Fixes https://github.com/llvm/llvm-project/issues/55851

Differential Revision: https://reviews.llvm.org/D126560

show more ...

[analyzer] Handle SymbolCast in SValBuilder

Make the SimpleSValBuilder to be able to look up and use a constraint
for an operand of a SymbolCast, when the operand is constrained to a
const value.
Th

[analyzer] Handle SymbolCast in SValBuilder

Make the SimpleSValBuilder to be able to look up and use a constraint
for an operand of a SymbolCast, when the operand is constrained to a
const value.
This part of the SValBuilder is responsible for constant folding. We
need this constant folding, so the engine can work with less symbols,
this way it can be more efficient. Whenever a symbol is constrained with
a constant then we substitute the symbol with the corresponding integer.
If a symbol is constrained with a range, then the symbol is kept and we
fall-back to use the range based constraint manager, which is not that
efficient. This patch is the natural extension of the existing constant
folding machinery with the support of SymbolCast symbols.

Differential Revision: https://reviews.llvm.org/D126481

show more ...

[analyzer][NFC] Inline loc::ConcreteInt::evalBinOp

This patch also refactored some of the enclosing parts.

Reviewed By: martong

Differential Revision: https://reviews.llvm.org/D126128

[analyzer] Add UnarySymExpr

This patch adds a new descendant to the SymExpr hierarchy. This way, now
we can assign constraints to symbolic unary expressions. Only the unary
minus and bitwise negatio

[analyzer] Add UnarySymExpr

This patch adds a new descendant to the SymExpr hierarchy. This way, now
we can assign constraints to symbolic unary expressions. Only the unary
minus and bitwise negation are handled.

Differential Revision: https://reviews.llvm.org/D125318

show more ...

Reland "[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible"

This PR changes the `SymIntExpr` so the expression that uses a
negative value as `RHS`, for example: `x +/- (-N)`, is

Reland "[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible"

This PR changes the `SymIntExpr` so the expression that uses a
negative value as `RHS`, for example: `x +/- (-N)`, is modeled as
`x -/+ N` instead.

This avoids producing a very large `RHS` when the symbol is cased to
an unsigned number, and as consequence makes the value more robust in
presence of casts.

Note that this change is not applied if `N` is the lowest negative
value for which negation would not be representable.

Reviewed By: steakhal

Patch By: tomasz-kaminski-sonarsource!

Differential Revision: https://reviews.llvm.org/D124658

show more ...

Revert "[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible"

It seems like multiple users are affected by a crash introduced by this
commit, thus I'm reverting it for the time be

Revert "[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible"

It seems like multiple users are affected by a crash introduced by this
commit, thus I'm reverting it for the time being.
Read more about the found reproducers at Phabricator.

Differential Revision: https://reviews.llvm.org/D124658

This reverts commit f0d6cb4a5cf5723d7ddab2c7dab74f2f62116a6d.

show more ...

[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible

This PR changes the `SymIntExpr` so the expression that uses a
negative value as `RHS`, for example: `x +/- (-N)`, is modeled

[analyzer] Canonicalize SymIntExpr so the RHS is positive when possible

This PR changes the `SymIntExpr` so the expression that uses a
negative value as `RHS`, for example: `x +/- (-N)`, is modeled as
`x -/+ N` instead.

This avoids producing a very large `RHS` when the symbol is cased to
an unsigned number, and as consequence makes the value more robust in
presence of casts.

Note that this change is not applied if `N` is the lowest negative
value for which negation would not be representable.

Reviewed By: steakhal

Patch By: tomasz-kaminski-sonarsource!

Differential Revision: https://reviews.llvm.org/D124658

show more ...

[analyzer] Avoid checking addrspace pointers in cstring checker

This change fixes an assert that occurs in the SMT layer when refuting a
finding that uses pointers of two different sizes. This was f

[analyzer] Avoid checking addrspace pointers in cstring checker

This change fixes an assert that occurs in the SMT layer when refuting a
finding that uses pointers of two different sizes. This was found in a
downstream build that supports two different pointer sizes, The CString
Checker was attempting to compute an overlap for the 'to' and 'from'
pointers, where the pointers were of different sizes.

In the downstream case where this was found, a specialized memcpy
routine patterned after memcpy_special is used. The analyzer core hits
on this builtin because it matches the 'memcpy' portion of that builtin.
This cannot be duplicated in the upstream test since there are no
specialized builtins that match that pattern, but the case does
reproduce in the accompanying LIT test case. The amdgcn target was used
for this reproducer. See the documentation for AMDGPU address spaces here
https://llvm.org/docs/AMDGPUUsage.html#address-spaces.

The assert seen is:

`*Solver->getSort(LHS) == *Solver->getSort(RHS) && "AST's must have the same sort!"'

Ack to steakhal for reviewing the fix, and creating the test case.

Reviewed By: steakhal

Differential Revision: https://reviews.llvm.org/D118050

show more ...

[clang] Use true/false instead of 1/0 (NFC)

Identified with modernize-use-bool-literals.