[clang][dataflow] Allow `DataflowAnalysisContext` to use a non-owned `Solver`. (#91316)

For some callers (see change in DataflowAnalysis.h), this is more
convenient.

[clang][dataflow] Expose getReferencedDecls and relocate free functions. (#88754)

Moves free functions from DataflowEnvironment.h/cc and
DataflowAnalysisContext.h/cc to RecordOps and a new ASTOps a

[clang][dataflow] Expose getReferencedDecls and relocate free functions. (#88754)

Moves free functions from DataflowEnvironment.h/cc and
DataflowAnalysisContext.h/cc to RecordOps and a new ASTOps and exposes
them as needed for current use and to expose getReferencedDecls for
out-of-tree use.

Minimal change in functionality, only to modify the return type of
getReferenceDecls to return the collected decls instead of using output
params.

Tested with `ninja check-clang-tooling`.

show more ...

[clang][dataflow][NFC] Rename `ControlFlowContext` to `AdornedCFG`. (#85640)

This expresses better what the class actually does, and it reduces the
number of
`Context`s that we have in the codebase.

[clang][dataflow][NFC] Rename `ControlFlowContext` to `AdornedCFG`. (#85640)

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.

show more ...

[clang][dataflow] Tighten checking for existence of a function body. (#78163)

In various places, we would previously call `FunctionDecl::hasBody()`
(which
checks whether any redeclaration of the fun

[clang][dataflow] Tighten checking for existence of a function body. (#78163)

In various places, we would previously call `FunctionDecl::hasBody()`
(which
checks whether any redeclaration of the function has a body, not
necessarily the
one on which `hasBody()` is being called).

This is bug-prone, as a recent bug in Crubit's nullability checker has
shown

([fix](https://github.com/google/crubit/commit/4b01ed0f14d953cda20f92d62256e7365d206b2e),
[fix for the
fix](https://github.com/google/crubit/commit/e0c5d8ddd7d647da483c2ae198ff91d131c12055)).

Instead, we now use `FunctionDecl::doesThisDeclarationHaveABody()`
which, as the
name implies, checks whether the specific redeclaration it is being
called on
has a body.

Alternatively, I considered being more lenient and "canonicalizing" to
the
`FunctionDecl` that has the body if the `FunctionDecl` being passed is a
different redeclaration. However, this also risks hiding bugs: A caller
might
inadverently perform the analysis for all redeclarations of a function
and end
up duplicating work without realizing it. By accepting only the
redeclaration
that contains the body, we prevent this.

I've checked, and all clients that I'm aware of do currently pass in the
redeclaration that contains the function body. Typically this is because
they
use the `ast_matchers::hasBody()` matcher which, unlike
`FunctionDecl::hasBody()`, only matches for the redeclaration containing
the
body.

show more ...

[clang][dataflow] Add an early-out to `flowConditionImplies()` / `flowConditionAllows()`. (#78172)

This saves having to assemble the set of constraints and run the SAT
solver in
the trivial case of

[clang][dataflow] Add an early-out to `flowConditionImplies()` / `flowConditionAllows()`. (#78172)

This saves having to assemble the set of constraints and run the SAT
solver in
the trivial case of `flowConditionImplies(true)` or
`flowConditionAllows(false)`.

This is an update / reland of my previous reverted
[#77453](https://github.com/llvm/llvm-project/pull/77453). That PR
contained a
logic bug -- the early-out for `flowConditionAllows()` was wrong because
my
intuition about the logic was wrong. (In particular, note that
`flowConditionImplies(F)` does not imply `flowConditionAllows(F)`, even
though
this may run counter to intuition.)

I've now done what I should have done on the first iteration and added
more
tests. These pass both with and without my early-outs.

This patch is a performance win on the benchmarks for the Crubit
nullability
checker, except for one slight regression on a relatively short
benchmark:

```
name old cpu/op new cpu/op delta
BM_PointerAnalysisCopyPointer 68.5µs ± 7% 67.6µs ± 4% ~ (p=0.159 n=18+19)
BM_PointerAnalysisIntLoop 173µs ± 3% 162µs ± 4% -6.40% (p=0.000 n=19+20)
BM_PointerAnalysisPointerLoop 307µs ± 2% 312µs ± 4% +1.56% (p=0.013 n=18+20)
BM_PointerAnalysisBranch 199µs ± 4% 181µs ± 4% -8.81% (p=0.000 n=20+20)
BM_PointerAnalysisLoopAndBranch 503µs ± 3% 508µs ± 2% ~ (p=0.081 n=18+19)
BM_PointerAnalysisTwoLoops 304µs ± 4% 286µs ± 2% -6.04% (p=0.000 n=19+20)
BM_PointerAnalysisJoinFilePath 4.78ms ± 3% 4.54ms ± 4% -4.97% (p=0.000 n=20+20)
BM_PointerAnalysisCallInLoop 3.05ms ± 3% 2.90ms ± 4% -5.05% (p=0.000 n=19+20)
```

When running clang-tidy on real-world code, the results are less clear.
In
three runs, averaged, on an arbitrarily chosen input file, I get 11.60 s
of user
time without this patch and 11.40 s with it, though with considerable
measurement noise (I'm seeing up to 0.2 s of variation between runs).

Still, this is a very simple change, and it is a clear win in
benchmarks, so I
think it is worth making.

show more ...

Revert "[clang][dataflow] Add an early-out to `flowConditionImplies()` / `flowConditionAllows()`." (#77570)

Reverts llvm/llvm-project#77453

[clang][dataflow] Add an early-out to `flowConditionImplies()` / `flowConditionAllows()`. (#77453)

This saves having to assemble the set of constraints and run the SAT
solver in
the trivial case whe

[clang][dataflow] Add an early-out to `flowConditionImplies()` / `flowConditionAllows()`. (#77453)

This saves having to assemble the set of constraints and run the SAT
solver in
the trivial case where `F` is true.

This is a performance win on the benchmarks for the Crubit nullability
checker:

```
name old cpu/op new cpu/op delta
BM_PointerAnalysisCopyPointer 64.1µs ± 5% 63.1µs ± 0% -1.56% (p=0.000 n=20+17)
BM_PointerAnalysisIntLoop 172µs ± 2% 171µs ± 0% ~ (p=0.752 n=20+17)
BM_PointerAnalysisPointerLoop 408µs ± 3% 355µs ± 0% -12.99% (p=0.000 n=20+17)
BM_PointerAnalysisBranch 201µs ± 2% 184µs ± 0% -8.28% (p=0.000 n=20+19)
BM_PointerAnalysisLoopAndBranch 684µs ± 2% 613µs ± 2% -10.38% (p=0.000 n=20+19)
BM_PointerAnalysisTwoLoops 309µs ± 2% 308µs ± 2% ~ (p=0.728 n=20+19)
BM_PointerAnalysisJoinFilePath 37.9ms ± 2% 37.9ms ± 2% +0.06% (p=0.041 n=20+19)
BM_PointerAnalysisCallInLoop 26.5ms ± 2% 26.4ms ± 4% -0.59% (p=0.024 n=20+20)
```

When running clang-tidy on real-world code, the results are less clear.
In
three runs, averaged, on an arbitrarily chosen input file, I get 11.91 s
of user
time without this patch and 11.81 s with it, though with considerable
measurement noise (I'm seeing up to 0.2 s of variation between runs).

Still, this is a very simple change, and it is a clear win in
benchmarks, so I
think it is worth making.

show more ...

[clang][dataflow] Add synthetic fields to `RecordStorageLocation` (#73860)

Synthetic fields are intended to model the internal state of a class
(e.g. the value stored in a `std::optional`) without

[clang][dataflow] Add synthetic fields to `RecordStorageLocation` (#73860)

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.

show more ...

[clang][dataflow] Fix -Wrange-loop-construct in DataflowAnalysisContext.cpp (NFC)

/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp:247:10: note: use reference type 'const l

[clang][dataflow] Fix -Wrange-loop-construct in DataflowAnalysisContext.cpp (NFC)

/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp:247:10: note: use reference type 'const llvm::Sma
llVector<Atom> &' to prevent copying
for (const llvm::SmallVector<Atom> Class : Info.EquivalentAtoms)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
&
1 error generated.

show more ...

[clang][dataflow] Simplify flow conditions displayed in HTMLLogger. (#70848)

This can make the flow condition significantly easier to interpret; see
below
for an example.

I had hoped that adding th

[clang][dataflow] Simplify flow conditions displayed in HTMLLogger. (#70848)

This can make the flow condition significantly easier to interpret; see
below
for an example.

I had hoped that adding the simplification as a preprocessing step
before the
SAT solver (in `DataflowAnalysisContext::querySolver()`) would also
speed up SAT
solving and maybe even eliminate SAT solver timeouts, but in my testing,
this
actually turns out to be a pessimization. It appears that these
simplifications
are easy enough for the SAT solver to perform itself.

Nevertheless, the improvement in debugging alone makes this a worthwhile
change.

Example of flow condition output with these changes:

```
Flow condition token: V37
Constraints:
(V16 = (((V15 & (V19 = V12)) & V22) & V25))
(V15 = ((V12 & ((V14 = V9) | (V14 = V4))) & (V13 = V14)))
True atoms: (V0, V1, V2, V5, V6, V7, V29, V30, V32, V34, V35, V37)
False atoms: (V3, V8, V17)
Equivalent atoms:
(V11, V15)

Flow condition constraints before simplification:
V37
((!V3 & !V8) & !V17)
(V37 = V34)
(V34 = (V29 & (V35 = V30)))
(V29 = (((V16 | V2) & V32) & (V30 = V32)))
(V16 = (((V15 & (V19 = V12)) & V22) & V25))
(V15 = V11)
(V11 = ((((V7 | V2) & V12) & ((V7 & (V14 = V9)) | (V2 & (V14 = V4)))) & (V13 = V14)))
(V2 = V1)
(V1 = V0)
V0
(V7 = V6)
(V6 = V5)
(V5 = V2)
```

show more ...

[clang][dataflow] Add `Environment::allows()`. (#70046)

This allows querying whether, given the flow condition, a certain
formula still
has a solution (though it is not necessarily implied by the fl

[clang][dataflow] Add `Environment::allows()`. (#70046)

This allows querying whether, given the flow condition, a certain
formula still
has a solution (though it is not necessarily implied by the flow
condition, as
`flowConditionImplies()` would check).

This can be checked today, but only with a double negation, i.e. to
check
whether, given the flow condition, a formula F has a solution, you can
check
`!Env.flowConditionImplies(Arena.makeNot(F))`. The double negation makes
this
hard to reason about, and it would be nicer to have a way of directly
checking
this.

For consistency, this patch also renames `flowConditionImplies()` to
`proves()`;
the old name is kept around for compatibility but deprecated.

show more ...

[clang][dataflow] Remove `DataflowAnalysisContext::flowConditionIsTautology()`. (#69601)

It's only used in its own unit tests.

Reapply "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 3353f7dd3d91c9b2b6a15ba9229bee53e0cb8196.

Fixed test bug (unspecified order of arg evaluation)

[clang][dataflow] Add support for lambda captures (#68558)

This adds support for copy, ref, and this lambda captures to the core
framework and also adds relevant tests in UncheckedOptionalAccessTes

[clang][dataflow] Add support for lambda captures (#68558)

This adds support for copy, ref, and this lambda captures to the core
framework and also adds relevant tests in UncheckedOptionalAccessTest.

show more ...

Revert "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 36bd5bd888f193b70abf43a09bb4fc04cd2a2ff1.

This change is causing a test failure on several build b

Revert "[dataflow] use true/false literals in formulas, rather than variables"

This reverts commit 36bd5bd888f193b70abf43a09bb4fc04cd2a2ff1.

This change is causing a test failure on several build bots:
- https://lab.llvm.org/buildbot/#/builders/139/builds/50255
- https://lab.llvm.org/buildbot/#/builders/216/builds/27735
- https://lab.llvm.org/buildbot/#/builders/247/builds/9334

show more ...

[dataflow] use true/false literals in formulas, rather than variables

And simplify formulas containing true/false
It's unclear to me how useful this is, it does make formulas more
conveniently self-

[dataflow] use true/false literals in formulas, rather than variables

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

show more ...

[dataflow] Add global invariant condition to DataflowAnalysisContext (#65949)

This records facts that are not sensitive to the current flow condition,
and should apply to all environments.

The m

[dataflow] Add global invariant condition to DataflowAnalysisContext (#65949)

This records facts that are not sensitive to the current flow condition,
and should apply to all environments.

The motivating case is recording information about where a Value
originated, such as nullability:
- we may see the same Value for multiple expressions (e.g. reads of the
same field) in multiple environments (multiple blocks or iterations)
- we want to record information only when we first see the Value
(e.g. Nullability annotations on fields only add information if we
don't know where the value came from)
- this information should be expressible as a SAT condition
- we must add this SAT condition to every environment where the
Value may appear

We solve this by recording the information in the global condition.
This doesn't seem particularly elegant, but solves the problem and is
a fairly small and natural extension of the Environment.

Alternatives considered:
- store the constraint directly as a property on the Value.
But it's more composable for such properties to always be variables
(AtomicBoolValue), and constrain them with SAT conditions.
- add a hook whenever values are created, giving the analysis the
chance to populate them.
However the framework relies on/provides the ability to construct
values in arbitrary places without providing the context such a hook
would need, this would be a very invasive change.

show more ...

[clang][dataflow][NFC] Eliminate `getStorageLocation()` / `setStorageLocation()` in `DataflowAnalysisContext`.

Instead, inline them into the `getStableStorageLocation()` overloads, which is the only

[clang][dataflow][NFC] Eliminate `getStorageLocation()` / `setStorageLocation()` in `DataflowAnalysisContext`.

Instead, inline them into the `getStableStorageLocation()` overloads, which is the only place they were called from (and should be called from).

`getStorageLocation()` / `setStorageLocation()` were confusing because neither their name nor their documentation made reference to the fact that the storage location is stable.

It didn't make sense to keep these as private member functions either. The code for the two `getStableStorageLocation()` overloads has become only marginally more complex by inlining these functions, and the `Expr` version is actually more efficient because we only call `ignoreCFGOmittedNodes()` once instead of twice.

Reviewed By: ymandel, xazax.hun

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

show more ...

[clang][dataflow] Rename `AggregateStorageLocation` to `RecordStorageLocation` and `StructValue` to `RecordValue`.

- Both of these constructs are used to represent structs, classes, and unions;
Cl

[clang][dataflow] Rename `AggregateStorageLocation` to `RecordStorageLocation` and `StructValue` to `RecordValue`.

- 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

show more ...

[clang][dataflow] Eliminate duplication between `AggregateStorageLocation` and `StructValue`.

After this change, `StructValue` is just a wrapper for an `AggregateStorageLocation`. For the wider cont

[clang][dataflow] Eliminate duplication between `AggregateStorageLocation` and `StructValue`.

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

show more ...

[clang][dataflow] Add `DataflowEnvironment::createObject()`.

This consolidates the code used in various places to initialize objects (usually for variables) into one central location.

It will also

[clang][dataflow] Add `DataflowEnvironment::createObject()`.

This consolidates the code used in various places to initialize objects (usually for variables) into one central location.

It will also help reduce the number of changes needed when we make the upcoming API changes to `AggregateStorageLocation` and `StructValue`.

Depends On D155074

Reviewed By: ymandel, xazax.hun

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

show more ...

[clang] Create a buildkite-pipeline.yml file for clang

This moves the formatting job to a shell script, which should also fix
the clang pre-commit CI.

Differential Revision: https://reviews.llvm.or

[clang] Create a buildkite-pipeline.yml file for clang

This moves the formatting job to a shell script, which should also fix
the clang pre-commit CI.

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

show more ...

[clang][dataflow] Various changes to handling of modeled fields.

- Rename `getReferencedFields()` to `getModeledFields()`. Move the logic that
returns all object fields when doing a context-sensit

[clang][dataflow] Various changes to handling of modeled fields.

- Rename `getReferencedFields()` to `getModeledFields()`. Move the logic that
returns all object fields when doing a context-sensitive analysis to here from
`DataflowAnalysisContext::createStorageLocation()`. I think all callers of
the previous `getReferencedFields()` should use this logic; the fact that they
were not doing so looks like a bug.

- Make `getModeledFields()` public. I have an upcoming patch that will need to
use this function from Transfer.cpp, and there doesn't seem to be any reason
why this function should not be public.

- Use a `SmallSetVector` to get deterministic iteration order. I have a pending
patch where I'm getting flaky tests because
`Environment::createValueUnlessSelfReferential()` is non-deterministically
populating different fields depending on the iteration order. This change
fixes those flaky tests.

Reviewed By: gribozavr2

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

show more ...

Reland "[dataflow] Add dedicated representation of boolean formulas"

This reverts commit 7a72ce98224be76d9328e65eee472381f7c8e7fe.

Test problems were due to unspecified order of function arg evalua

Reland "[dataflow] Add dedicated representation of boolean formulas"

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

show more ...

Revert "Reland "[dataflow] Add dedicated representation of boolean formulas" and followups

These changes are OK, but they break downstream stuff that needs more time to adapt :-(

This reverts commi

Revert "Reland "[dataflow] Add dedicated representation of boolean formulas" and followups

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.

show more ...