[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] Prefer wrapping SymbolicRegions by ElementRegions

It turns out that in certain cases `SymbolRegions` are wrapped by
`ElementRegions`; in others, it's not. This discrepancy can cause the
a

[analyzer] Prefer wrapping SymbolicRegions by ElementRegions

It turns out that in certain cases `SymbolRegions` are wrapped by
`ElementRegions`; in others, it's not. This discrepancy can cause the
analyzer not to recognize if the two regions are actually referring to
the same entity, which then can lead to unreachable paths discovered.

Consider this example:

```lang=C++
struct Node { int* ptr; };
void with_structs(Node* n1) {
Node c = *n1; // copy
Node* n2 = &c;
clang_analyzer_dump(*n1); // lazy...
clang_analyzer_dump(*n2); // lazy...
clang_analyzer_dump(n1->ptr); // rval(n1->ptr): reg_$2<int * SymRegion{reg_$0<struct Node * n1>}.ptr>
clang_analyzer_dump(n2->ptr); // rval(n2->ptr): reg_$1<int * Element{SymRegion{reg_$0<struct Node * n1>},0 S64b,struct Node}.ptr>
clang_analyzer_eval(n1->ptr != n2->ptr); // UNKNOWN, bad!
(void)(*n1);
(void)(*n2);
}
```

The copy of `n1` will insert a new binding to the store; but for doing
that it actually must create a `TypedValueRegion` which it could pass to
the `LazyCompoundVal`. Since the memregion in question is a
`SymbolicRegion` - which is untyped, it needs to first wrap it into an
`ElementRegion` basically implementing this untyped -> typed conversion
for the sake of passing it to the `LazyCompoundVal`.
So, this is why we have `Element{SymRegion{.}, 0,struct Node}` for `n1`.

The problem appears if the analyzer evaluates a read from the expression
`n1->ptr`. The same logic won't apply for `SymbolRegionValues`, since
they accept raw `SubRegions`, hence the `SymbolicRegion` won't be
wrapped into an `ElementRegion` in that case.

Later when we arrive at the equality comparison, we cannot prove that
they are equal.

For more details check the corresponding thread on discourse:
https://discourse.llvm.org/t/are-symbolicregions-really-untyped/64406

---

In this patch, I'm eagerly wrapping each `SymbolicRegion` by an
`ElementRegion`; basically canonicalizing to this form.
It seems reasonable to do so since any object can be thought of as a single
array of that object; so this should not make much of a difference.

The tests also underpin this assumption, as only a few were broken by
this change; and actually fixed a FIXME along the way.

About the second example, which does the same copy operation - but on
the heap - it will be fixed by the next patch.

Reviewed By: martong

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

show more ...

[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 ...

[clang] Add a raw_ostream operator<< overload for QualType

Under the hood this prints the same as `QualType::getAsString()` but cuts out the middle-man when that string is sent to another raw_ostrea

[clang] Add a raw_ostream operator<< overload for QualType

Under the hood this prints the same as `QualType::getAsString()` but cuts out the middle-man when that string is sent to another raw_ostream.

Also cleaned up all the call sites where this occurs.

Reviewed By: aaron.ballman

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

show more ...

[NFC][analyzer] Return underlying strings directly instead of OS.str()

This avoids an unnecessary copy required by 'return OS.str()', allowing
instead for NRVO or implicit move. The .str() call (whi

[NFC][analyzer] Return underlying strings directly instead of OS.str()

This avoids an unnecessary copy required by 'return OS.str()', allowing
instead for NRVO or implicit move. The .str() call (which flushes the
stream) is no longer required since 65b13610a5226b84889b923bae884ba395ad084d,
which made raw_string_ostream unbuffered by default.

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

show more ...

SValExplainer.h - get APSInt values by const reference instead of value. NFCI.

Avoid unnecessary copies.

[Analyzer] [NFC] Parameter Regions

Currently, parameters of functions without their definition present cannot
be represented as regions because it would be difficult to ensure that the
same declarat

[Analyzer] [NFC] Parameter Regions

Currently, parameters of functions without their definition present cannot
be represented as regions because it would be difficult to ensure that the
same declaration is used in every case. To overcome this, we split
`VarRegion` to two subclasses: `NonParamVarRegion` and `ParamVarRegion`.
The latter does not store the `Decl` of the parameter variable. Instead it
stores the index of the parameter which enables retrieving the actual
`Decl` every time using the function declaration of the stack frame. To
achieve this we also removed storing of `Decl` from `DeclRegion` and made
`getDecl()` pure virtual. The individual `Decl`s are stored in the
appropriate subclasses, such as `FieldRegion`, `ObjCIvarRegion` and the
newly introduced `NonParamVarRegion`.

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

show more ...

Remove Expr.h include from ASTContext.h, NFC

ASTContext.h is popular, prune its includes. Expr.h brings in Attr.h,
which is also expensive.

Move BlockVarCopyInit to Expr.h to accomplish this.

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

Revert "[analyzer] Support generating and reasoning over more symbolic constraint types"

Assertion `Loc::isLocType(SSE->getLHS()->getType())' failed in Analysis/PR3991.m

This reverts commit e469ff2

Revert "[analyzer] Support generating and reasoning over more symbolic constraint types"

Assertion `Loc::isLocType(SSE->getLHS()->getType())' failed in Analysis/PR3991.m

This reverts commit e469ff2759275e67f9072b3d67fac90f647c0fe6.

llvm-svn: 307853

show more ...

[analyzer] Support generating and reasoning over more symbolic constraint types

Summary: Generate more IntSymExpr constraints, perform SVal simplification for IntSymExpr and SymbolCast constraints,

[analyzer] Support generating and reasoning over more symbolic constraint types

Summary: Generate more IntSymExpr constraints, perform SVal simplification for IntSymExpr and SymbolCast constraints, and create fully symbolic SymExprs

Reviewers: zaks.anna, dcoughlin, NoQ, xazax.hun

Subscribers: mgorny, cfe-commits

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

llvm-svn: 307833

show more ...

[analyzer] SValExplainer: Support ObjC ivars and __block variables.

Additionally, explain the difference between normal and heap-based
symbolic regions.

llvm-svn: 288260

[analyzer] Provide .def-files and visitors for SVal/SymExpr/MemRegion, v2.

Provide separate visitor templates for the three hierarchies, and also
the `FullSValVisitor' class, which is a union of all

[analyzer] Provide .def-files and visitors for SVal/SymExpr/MemRegion, v2.

Provide separate visitor templates for the three hierarchies, and also
the `FullSValVisitor' class, which is a union of all three visitors.

Additionally, add a particular example visitor, `SValExplainer', in order to
test the visitor templates. This visitor is capable of explaining the SVal,
SymExpr, or MemRegion in a natural language.

Compared to the reverted r257605, this fixes the test that used to fail
on some triples, and fixes build failure under -fmodules.

Differential Revision: http://reviews.llvm.org/D15448

llvm-svn: 257893

show more ...

[analyzer] Provide .def-files and visitors for SVal/SymExpr/MemRegion.

Provide separate visitor templates for the three hierarchies, and also
the `FullSValVisitor' class, which is a union of all thr

[analyzer] Provide .def-files and visitors for SVal/SymExpr/MemRegion.

Provide separate visitor templates for the three hierarchies, and also
the `FullSValVisitor' class, which is a union of all three visitors.

Additionally, add a particular example visitor, `SValExplainer', in order to
test the visitor templates. This visitor is capable of explaining the SVal,
SymExpr, or MemRegion in a natural language.

Differential Revision: http://reviews.llvm.org/D15448

llvm-svn: 257605

show more ...