At the same time, rename `PostVisitCFG` to the more descriptive
`PostAnalysisCallbacks` (which emphasizes the fact that these callbacks
are run
after the dataflow analysis itself has converged).
Before this patch, it was only possible to run a callback on the state
_after_
the transfer function had been applied, but for many analyses, it's more
natural
to to check the state _before_ the transfer function has been applied,
because we
are usually checking the preconditions for some operation. Some checks
are
impossible to perform on the "after" state because we can no longer
check the
precondition; for example, the `++` / `--` operators on raw pointers
require the
operand to be nonnull, but after the transfer function for the operator
has been
applied, the original value of the pointer can no longer be accessed.
`UncheckedOptionalAccessModelTest` has been modified to run the
diagnosis
callback on the "before" state. In this particular case, diagnosis can
be run
unchanged on either the "before" or "after" state, but we want this test
to
demonstrate that running diagnosis on the "before" state is usually the
preferred approach.
This change is backwards-compatible; all existing analyses will continue
to run
the callback on the "after" state.
Assume in fewer places that the analysis is of a `FunctionDecl`, and
initialize the `Environment` properly for `Stmt`s.
Moves constructors for `Environment` to header to make it more obvious
that there are only minor differences between them and very little
initialization in the constructors.
Tested with check-clang-tooling.
I reverted https://github.com/llvm/llvm-project/pull/89213 beause it was
causing buildbots to fail with assertion failures.
Embarrassingly, it turns out I had been running tests locally in
`Release` mode, i.e. with `assert()` compiled away.
This PR re-lands #89213 with fixes for the failing assertions.
This expresses better what the class actually does, and it reduces the
number of
`Context`s that we have in the codebase.
A deprecated alias `ControlFlowContext` is available from the old
header.
This fixes a crash introduced by
https://github.com/llvm/llvm-project/pull/82348
but also adds additional handling to make sure that we treat empty
initializer
lists for both unions and structs/classes correctly (see tests added in
this
patch).
Reverts llvm/llvm-project#82348, which caused crashes when analyzing
empty InitListExprs for unions, e.g.
```cc
union U {
double double_value;
int int_value;
};
void target() {
U value;
value = {};
}
```
Co-authored-by: Samira Bazuzi <bazuzi@users.noreply.github.com>
Previously, we hard-coded the cap on block visits inside the framework.
This
patch enables the caller to specify the cap in the APIs for running an
analysis.
Synthetic fields are intended to model the internal state of a class
(e.g. the value stored in a `std::optional`) without having to depend on
that class's implementation details.
Today, this is typically done with properties on `RecordValue`s, but
these have several drawbacks:
* Care must be taken to call `refreshRecordValue()` before modifying a
property so that the modified property values aren’t seen by other
environments that may have access to the same `RecordValue`.
* Properties aren’t associated with a storage location. If an analysis
needs to associate a location with the value stored in a property (e.g.
to model the reference returned by `std::optional::value()`), it needs
to manually add an indirection using a `PointerValue`. (See for example
the way this is done in UncheckedOptionalAccessModel.cpp, specifically
in `maybeInitializeOptionalValueMember()`.)
* Properties don’t participate in the builtin compare, join, and widen
operations. If an analysis needs to apply these operations to
properties, it needs to override the corresponding methods of
`ValueModel`.
* Longer-term, we plan to eliminate `RecordValue`, as by-value
operations on records aren’t really “a thing” in C++ (see
https://discourse.llvm.org/t/70086#changed-structvalue-api-14). This
would obviously eliminate the ability to set properties on
`RecordValue`s.
To demonstrate the advantages of synthetic fields, this patch converts
UncheckedOptionalAccessModel.cpp to synthetic fields. This greatly
simplifies the implementation of the check.
This PR is pretty big; to make it easier to review, I have broken it
down into a stack of three commits, each of which contains a set of
logically related changes. I considered submitting each of these as a
separate PR, but the commits only really make sense when taken together.
To review, I suggest first looking at the changes in
UncheckedOptionalAccessModel.cpp. This gives a flavor for how the
various API changes work together in the context of an analysis. Then,
review the rest of the changes.
And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-contained now (we can usefully print them without
carrying around the "true/false" labels)
(while here, simplify !!X to X, too)
Differential Revision: https://reviews.llvm.org/D153485
We want to eliminate the `RecordStorageLocation` from `RecordValue` and,
ultimately, eliminate `RecordValue` entirely (see the discussion linked
in the
`RecordValue` class comment). This is one step in that direction.
To eliminate `RecordValue::getChild()`, we also eliminate the last
remaining
caller, namely the `getFieldValue(const RecordValue *, ...)` overload.
Calls
to this overload have been rewritten to use the
`getFieldValue(const RecordStorageLocation *, ...)` overload. Note that
this
also makes the code slightly simpler in many cases.
These are broken out from https://reviews.llvm.org/D156658, which it now seems obvious isn't the right way to solve the non-convergence.
Instead, my plan is to address the non-convergence through pointer value widening, but the exact way this should be implemented is TBD. In the meantime, I think there's value in getting these repros submitted to record the current undesirable behavior.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D158513
- Both of these constructs are used to represent structs, classes, and unions;
Clang uses the collective term "record" for these.
- The term "aggregate" in `AggregateStorageLocation` implies that, at some
point, the intention may have been to use it also for arrays, but it don't
think it's possible to use it for arrays. Records and arrays are very
different and therefore need to be modeled differently. Records have a fixed
set of named fields, which can have different type; arrays have a variable
number of elements, but they all have the same type.
- Futhermore, "aggregate" has a very specific meaning in C++
(https://en.cppreference.com/w/cpp/language/aggregate_initialization).
Aggregates of class type may not have any user-declared or inherited
constructors, no private or protected non-static data members, no virtual
member functions, and so on, but we use `AggregateStorageLocations` to model all objects of class type.
In addition, for consistency, we also rename the following:
- `getAggregateLoc()` (in `RecordValue`, formerly known as `StructValue`) to
simply `getLoc()`.
- `refreshStructValue()` to `refreshRecordValue()`
We keep the old names around as deprecated synonyms to enable clients to be migrated to the new names.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D156788
After this change, `StructValue` is just a wrapper for an `AggregateStorageLocation`. For the wider context, see https://discourse.llvm.org/t/70086.
## How to review
- Start by looking at the comments added / changed in Value.h, StorageLocation.h,
and DataflowEnvironment.h. This will give you a good overview of the semantic
changes.
- Look at the corresponding .cpp files that implement the semantic changes.
- Transfer.cpp, TypeErasedDataflowAnalysis.cpp, and RecordOps.cpp show how the
core of the framework is affected by the semantic changes.
- UncheckedOptionalAccessModel.cpp shows how this complex model is affected by
the changes.
- Many of the changes in the rest of the patch are mechanical in nature.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D155446
These insulate tests against changes to the `getChild()` functions of `AggregateStorageLocation` and `StructValue` that will happen as part of the migration to strict handling of value categories (see https://discourse.llvm.org/t/70086 for details):
- `AggregateStorageLocation::getChild()` will soon return a `StorageLocation *`
instead of a `StorageLocation &`. When this happens, `getFieldValue()` will be
changed to return null if `AggregateStorageLocation::getChild()` returns null;
test code will not need to change as it should already be checking whether the
return value of `getFieldValue()` is null.
- `StructValue::getChild()` will soon return a `StorageLocation *` instead of a
`Value *`. When this happens, `getFieldValue()` will be changed to look up the
`Value *` in the `Environment`. Again, test code will not need to change.
The test helpers will continue to serve a useful purpose once the API changes are complete, so the intent is to leave them in place.
This patch changes DataflowEnvironmentTest.cpp and RecordOpsTest.cpp to use the test helpers. TransferTest.cpp will be changed in an upcoming patch to help keep patch sizes manageable for review.
Depends On D154934
Reviewed By: ymandel, xazax.hun, gribozavr2
Differential Revision: https://reviews.llvm.org/D154935
This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.
Test problems were due to unspecified order of function arg evaluation.
Reland "[dataflow] Replace most BoolValue subclasses with references to Formula (and AtomicBoolValue => Atom and BoolValue => Formula where appropriate)"
This properly frees the Value hierarchy from managing boolean formulas.
We still distinguish AtomicBoolValue; this type is used in client code.
However we expect to convert such uses to BoolValue (where the
distinction is not needed) or Atom (where atomic identity is intended),
and then fold AtomicBoolValue into FormulaBoolValue.
We also distinguish TopBoolValue; this has distinct rules for
widen/join/equivalence, and top-ness is not represented in Formula.
It'd be nice to find a cleaner representation (e.g. the absence of a
formula), but no immediate plans.
For now, BoolValues with the same Formula are deduplicated. This doesn't
seem desirable, as Values are mutable by their creators (properties).
We can probably drop this for FormulaBoolValue immediately (not in this
patch, to isolate changes). For AtomicBoolValue we first need to update
clients to stop using value pointers for atom identity.
The data structures around flow conditions are updated:
- flow condition tokens are Atom, rather than AtomicBoolValue*
- conditions are Formula, rather than BoolValue
Most APIs were changed directly, some with many clients had a
new version added and the existing one deprecated.
The factories for BoolValues in Environment keep their existing
signatures for now (e.g. makeOr(BoolValue, BoolValue) => BoolValue)
and are not deprecated. These have very many clients and finding the
most ergonomic API & migration path still needs some thought.
Differential Revision: https://reviews.llvm.org/D153469
These changes are OK, but they break downstream stuff that needs more time to adapt :-(
This reverts commit 71579569f4399d3cf6bc618dcd449b5388d749cc.
This reverts commit 5e4ad816bf100b0325ed45ab1cfea18deb3ab3d1.
This reverts commit 1c3ac8dfa16c42a631968aadd0396cfe7f7778e0.
And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-contained now (we can usefully print them without
carrying around the "true/false" labels)
(while here, simplify !!X to X, too)
Differential Revision: https://reviews.llvm.org/D153485
It turns out this didn't need to be a template at all.
Likewise, change callers to they're non-template functions.
Also, correct / clarify some comments in RecordOps.h.
This is in response to post-commit comments on https://reviews.llvm.org/D153006.
Reviewed By: gribozavr2
Differential Revision: https://reviews.llvm.org/D154339
This is the first step in untangling the two current jobs of BoolValue.
=== Desired end-state: ===
- BoolValue will model C++ booleans e.g. held in StorageLocations.
this includes describing uncertainty (e.g. "top" is a Value concern)
- Formula describes analysis-level assertions in terms of SAT atoms.
These can still be linked together: a BoolValue may have a corresponding
SAT atom which is constrained by formulas.
=== Done in this patch: ===
BoolValue is left intact, Formula is just the input type to the
SAT solver, and we build formulas as needed to invoke the solver.
=== Incidental changes to debug string printing: ===
- variables renamed from B0 etc to V0 etc
B0 collides with the names of basic blocks, which is confusing when
debugging flow conditions.
- debug printing of formulas (Formula and Atom) uses operator<<
rather than debugString(), so works with gtest.
Therefore moved out of DebugSupport.h
- Did the same to Solver::Result, and some helper changes to SolverTest,
so that we get useful messages on unit test failures
- formulas are now printed as infix expressions on one line, rather than
wrapped/indented S-exprs. My experience is that this is easier to scan
FCs for small examples, and large ones are unreadable either way.
- most of the several debugString() functions for constraints/results
are unused, so removed them rather than updating tests.
Inlined the one that was actually used into its callsite.
Differential Revision: https://reviews.llvm.org/D153366
This serves two purposes:
- Because, today, we only copy the `StructValue`, modifying the destination of
the copy also modifies the source. This is demonstrated by the new checks
added to `CopyConstructor` and `MoveConstructor`, which fail without the
deep copy.
- It lays the groundwork for eliminating the redundancy between
`AggregateStorageLocation` and `StructValue`, which will happen as part of the
ongoing migration to strict handling of value categories (seeo
https://discourse.llvm.org/t/70086 for details). This will involve turning
`StructValue` into essentially just a wrapper for `AggregateStorageLocation`;
under this scheme, the current "shallow" copy (copying a `StructValue` from
one `AggregateStorageLocation` to another) will no longer be possible.
Because we now perform deep copies, tests need to perform a deep equality
comparison instead of just comparing for equal identity of the `StructValue`s.
The new function `recordsEqual()` provides such a deep equality comparison.
Reviewed By: xazax.hun
Differential Revision: https://reviews.llvm.org/D153006
Environments are heavyweight, and copies are observably different from the
original: they introduce new SAT variables, which degrade performance &
debugging. Copies should only be done deliberately, where justified.
Empirically there are several places in the framework where we perform dubious
copies, sometimes entirely accidentally. (see e.g. D153491). Making these
explicit makes this mistake harder.
This patch forces copies to go through fork(), the copy-constructor is private.
This requires changes to existing callsites: some are correct and call fork(),
some are incorrect and are fixed, others are difficult and I left a FIXME.
Differential Revision: https://reviews.llvm.org/D153674
When introducing this new overload in https://reviews.llvm.org/D151183, I didn't consider that the `ASTContext` parameter was unnecessary because it could also be obtained from the `FunctionDecl`.
Reviewed By: gribozavr2, xazax.hun
Differential Revision: https://reviews.llvm.org/D151549
This is the most common use case, so it makes sense to have a specific overload for it.
Reviewed By: xazax.hun
Differential Revision: https://reviews.llvm.org/D151183
Attempting to analyze templated code doesn't have a good cost-benefit ratio. We
have so far done a best-effort attempt at this, but maintaining this support has
an ongoing high maintenance cost because the AST for templates can violate a lot
of the invariants that otherwise hold for the AST of concrete code. As just one
example, in concrete code the operand of a UnaryOperator '*' is always a prvalue
(https://godbolt.org/z/s3e5xxMd1), but in templates this isn't true
(https://godbolt.org/z/6W9xxGvoM).
Further rationale for not analyzing templates:
* The semantics of a template itself are weakly defined; semantics can depend
strongly on the concrete template arguments. Analyzing the template itself (as
opposed to an instantiation) therefore has limited value.
* Analyzing templates requires a lot of special-case code that isn't necessary
for concrete code because dependent types are hard to deal with and the AST
violates invariants that otherwise hold for concrete code (see above).
* There's precedent in that neither Clang Static Analyzer nor the flow-sensitive
warnings in Clang (such as uninitialized variables) support analyzing
templates.
Reviewed By: gribozavr2, xazax.hun
Differential Revision: https://reviews.llvm.org/D150352
This parameter was already a no-op, so removing it doesn't change behavior.
Reviewed By: ymandel
Differential Revision: https://reviews.llvm.org/D150137
The crash happened because the transfer fucntion for `&&` and `||`
unconditionally tried to retrieve the value of the RHS. However, if the RHS
is unreachable, there is no environment for it, and trying to retrieve the
operand's value causes an assertion failure.
See also the comments in the code for further details.
Reviewed By: xazax.hun, ymandel, sgatev, gribozavr2
Differential Revision: https://reviews.llvm.org/D146514
In unit tests for concrete dataflow analyses we typically use the
testonly `checkDataflow()` helper to analyse a free function called
"target". This pattern allows our tests to be uniform and focused on
specific statement- or expression-level C++ features.
As we expand our feature coverage, we want to analyze functions whose
names we don't fully control, like constructors, destructors, operators
etc. In such tests it is often convenient to analyze all functions
defined in the input code, to avoid having to carefully craft an AST
matcher that finds the exact function we're interested in. That can be
easily done by providing `checkDataflow()` with a catch-all matcher like
`functionDecl()`.
It is also often convenient to define multiple special member functions
in a single unit test, for example, multiple constructors, and share the
rest of the class definition code between constructors. As a result, it
makes sense to analyze multiple functions in one unit test.
This change allows `checkDataflow()` to correctly handle AST matchers
that match more than one function. Previously, it would only ever
analyze the first matched function, and silently ignore the rest. Now it
runs dataflow analysis in a loop, and calls `VerifyResults` for each
function that was found in the input and analyzed.
Reviewed By: ymandel, sgatev
Differential Revision: https://reviews.llvm.org/D140859
The Annotations helper class does not have a gtest or gmock dependency, but because it's bundled with the rest of TestingSupport, it gets one. By splitting it out, a target can use it without being forced to use LLVM's copy of gtest.
Reviewed By: GMNGeoffrey, sammccall, gribozavr2
Differential Revision: https://reviews.llvm.org/D141175
Merges `TransferOptions` into the newly-introduced
`DataflowAnalysisContext::Options` and removes explicit parameter for
`TransferOptions`, relying instead on the common options carried by the analysis
context. Given that there was no intent to allow different options between calls
to `transfer`, a common value for the options is preferable.
Differential Revision: https://reviews.llvm.org/D140703
This reverts commit 2b1a517a92bfdfa3b692a660e19a2bb22513a567. It's a fix forward
with two memory errors fixed, one of which was the cause of the build breakage
in the buildbots.
Original message:
Previously, the model for structs modeled all fields in a struct when
`createValue` was called for that type. This patch adds a prepass on the
function under analysis to discover the fields referenced in the scope and then
limits modeling to only those fields. This reduces wasted memory usage
(modeling unused fields) which can be important for programs that use large
structs.
Note: This patch obviates the need for https://reviews.llvm.org/D123032.
Previously, the model for structs modeled all fields in a struct when
`createValue` was called for that type. This patch adds a prepass on the
function under analysis to discover the fields referenced in the scope and then
limits modeling to only those fields. This reduces wasted memory usage
(modeling unused fields) which can be important for programss that use large
structs.
Note: This patch obviates the need for https://reviews.llvm.org/D123032.
Differential Revision: https://reviews.llvm.org/D140694
Previously, the diagnoser could only receive the Environment at a given program point. Now, it receives the complete dataflow state: the environment and lattice element.
This change does not contain any tests because we modify the checkDataflow function to rely on the newly introduced lattice element in PostVisitCFG, and existing tests that verify lattice elements depend on this overload of checkDataflow.
Reviewed By: gribozavr2, ymandel
Differential Revision: https://reviews.llvm.org/D139868
