[llvm] Support llvm::Any across shared libraries on windows (#108051)

This is part of the effort to support for enabling plugins on windows by
adding better support for building llvm as a DLL. The

[llvm] Support llvm::Any across shared libraries on windows (#108051)

This is part of the effort to support for enabling plugins on windows by
adding better support for building llvm as a DLL. The export macros used
here were added in #96630

Since shared library symbols aren't deduplicated across multiple
libraries on windows like Linux we have to manually explicitly import
and export `Any::TypeId` template instantiations for the uses of
`llvm::Any` in the LLVM codebase to support LLVM Windows shared library
builds.
This change ensures that external code, including LLVM's own tests, can
use PassManager callbacks when LLVM is built as a DLL.

I also removed the only use of llvm::Any for LoopNest that only existed
in debug code and there also doesn't seem to be any code creating
`Any<LoopNest>`

show more ...

[clang][dataflow] Fix bug in `buildContainsExprConsumedInDifferentBlock()`. (#100874)

This was missing a call to `ignoreCFGOmittedNodes()`. As a result, the
function
would erroneously conclude that

[clang][dataflow] Fix bug in `buildContainsExprConsumedInDifferentBlock()`. (#100874)

This was missing a call to `ignoreCFGOmittedNodes()`. As a result, the
function
would erroneously conclude that a block did not contain an expression
consumed
in a different block if the expression in question was surrounded by a
`ParenExpr` in the consuming block. The patch adds a test that triggers
this
scenario (and fails without the fix).

To prevent this kind of bug in the future, the patch also adds a new
method
`blockForStmt()` to `AdornedCFG` that calls `ignoreCFGOmittedNodes()`
and is
preferred over accessing `getStmtToBlock()` directly.

show more ...

[clang][dataflow] Add a callback run on the pre-transfer state. (#96140)

At the same time, rename `PostVisitCFG` to the more descriptive
`PostAnalysisCallbacks` (which emphasizes the fact that thes

[clang][dataflow] Add a callback run on the pre-transfer state. (#96140)

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.

show more ...

[clang][dataflow] Fully support Environment construction for Stmt analysis. (#91616)

Assume in fewer places that the analysis is of a `FunctionDecl`, and
initialize the `Environment` properly for `

[clang][dataflow] Fully support Environment construction for Stmt analysis. (#91616)

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.

show more ...

Reapply "[clang][dataflow] Model conditional operator correctly." with fixes (#89596)

I reverted https://github.com/llvm/llvm-project/pull/89213 beause it was
causing buildbots to fail with assertio

Reapply "[clang][dataflow] Model conditional operator correctly." with fixes (#89596)

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.

show more ...

Revert "[clang][dataflow] Model conditional operator correctly." (#89577)

Reverts llvm/llvm-project#89213

This is causing buildbot failures.

[clang][dataflow] Model conditional operator correctly. (#89213)

[clang][nullability] Remove `RecordValue`. (#89052)

This class no longer serves any purpose; see also the discussion here:
https://reviews.llvm.org/D155204#inline-1503204

A lot of existing tests in

[clang][nullability] Remove `RecordValue`. (#89052)

This class no longer serves any purpose; see also the discussion here:
https://reviews.llvm.org/D155204#inline-1503204

A lot of existing tests in TransferTest.cpp check for the existence of
`RecordValue`s. Some of these checks are now simply redundant and have
been
removed. In other cases, tests were checking for the existence of a
`RecordValue` as a way of testing whether a record has been initialized.
I have
typically changed these test to instead check whether a field of the
record has
a value.

show more ...

[clang][dataflow] Reland #87320: Propagate locations from result objects to initializers. (#88316)

This relands #87320 and additionally removes the now-unused function
`isOriginalRecordConstructor()

[clang][dataflow] Reland #87320: Propagate locations from result objects to initializers. (#88316)

This relands #87320 and additionally removes the now-unused function
`isOriginalRecordConstructor()`, which was causing buildbots to fail.

show more ...

Revert "[clang][dataflow] Propagate locations from result objects to initializers." (#88315)

Reverts llvm/llvm-project#87320

This is causing buildbots to fail because
`isOriginalRecordConstructo

Revert "[clang][dataflow] Propagate locations from result objects to initializers." (#88315)

Reverts llvm/llvm-project#87320

This is causing buildbots to fail because
`isOriginalRecordConstructor()` is now unused.

show more ...

[clang][dataflow] Propagate locations from result objects to initializers. (#87320)

Previously, we were propagating storage locations the other way around,
i.e.
from initializers to result objects,

[clang][dataflow] Propagate locations from result objects to initializers. (#87320)

Previously, we were propagating storage locations the other way around,
i.e.
from initializers to result objects, using `RecordValue::getLoc()`. This
gave
the wrong behavior in some cases -- see the newly added or fixed tests
in this
patch.

In addition, this patch now unblocks removing the `RecordValue` class
entirely,
as we no longer need `RecordValue::getLoc()`.

With this patch, the test `TransferTest.DifferentReferenceLocInJoin`
started to
fail because the framework now always uses the same storge location for
a
`MaterializeTemporaryExpr`, meaning that the code under test no longer
set up
the desired state where a variable of reference type is mapped to two
different
storage locations in environments being joined. Rather than trying to
modify
this test to set up the test condition again, I have chosen to replace
the test
with an equivalent test in DataflowEnvironmentTest.cpp that sets up the
test
condition directly; because this test is more direct, it will also be
less
brittle in the face of future changes.

show more ...

[clang][dataflow] Refactor processing of terminator element (#84499)

This patch vastly simplifies the code handling terminators, without
changing any
behavior. Additionally, the simplification unb

[clang][dataflow] Refactor processing of terminator element (#84499)

This patch vastly simplifies the code handling terminators, without
changing any
behavior. Additionally, the simplification unblocks our ability to
address a
(simple) FIXME in the code to invoke `transferBranch`, even when builtin
options
are disabled.

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] When analyzing ctors, don't initialize fields of `*this` with values. (#84164)

This is the constructor's job, and we want to be able to test that it
does this.

[clang][nullability] Don't discard expression state before end of full-expression. (#82611)

In https://github.com/llvm/llvm-project/pull/72985, I made a change to
discard
expression state (`ExprTo

[clang][nullability] Don't discard expression state before end of full-expression. (#82611)

In https://github.com/llvm/llvm-project/pull/72985, I made a change to
discard
expression state (`ExprToLoc` and `ExprToVal`) at the beginning of each
basic
block. I did so with the claim that "we never need to access entries
from these
maps outside of the current basic block", noting that there are
exceptions to
this claim when control flow happens inside a full-expression (the
operands of
`&&`, `||`, and the conditional operator live in different basic blocks
than the
operator itself) but that we already have a mechanism for retrieving the
values
of these operands from the environment for the block they are computed
in.

It turns out, however, that the operands of these operators aren't the
only
expressions whose values can be accessed from a different basic block;
when
control flow happens within a full-expression, that control flow can be
"interposed" between an expression and its parent. Here is an example:

```cxx
void f(int*, int);
bool cond();

void target() {
int i = 0;
f(&i, cond() ? 1 : 0);
}
```

([godbolt](https://godbolt.org/z/hrbj1Mj3o))

In the CFG[^1] , note how the expression for `&i` is computed in block
B4,
but the parent of this expression (the `CallExpr`) is located in block
B1.
The the argument expression `&i` and the `CallExpr` are essentially
"torn apart"
into different basic blocks by the conditional operator in the second
argument.
In other words, the edge between the `CallExpr` and its argument `&i`
straddles
the boundary between two blocks.

I used to think that this scenario -- where an edge between an
expression and
one of its children straddles a block boundary -- could only happen
between the
expression that triggers the control flow (`&&`, `||`, or the
conditional
operator) and its children, but the example above shows that other
expressions
can be affected as well; the control flow is still triggered by `&&`,
`||` or
the conditional operator, but the expressions affected lie outside these
operators.

Discarding expression state too soon is harmful. For example, an
analysis that
checks the arguments of the `CallExpr` above would not be able to
retrieve a
value for the `&i` argument.

This patch therefore ensures that we don't discard expression state
before the
end of a full-expression. In other cases -- when the evaluation of a
full-expression is complete -- we still want to discard expression state
for the
reasons explained in https://github.com/llvm/llvm-project/pull/72985
(avoid
performing joins on boolean values that are no longer needed, which
unnecessarily extends the flow condition; improve debuggability by
removing
clutter from the expression state).

The impact on performance from this change is about a 1% slowdown in the
Crubit nullability check benchmarks:

```
name old cpu/op new cpu/op delta
BM_PointerAnalysisCopyPointer 71.9µs ± 1% 71.9µs ± 2% ~ (p=0.987 n=15+20)
BM_PointerAnalysisIntLoop 190µs ± 1% 192µs ± 2% +1.06% (p=0.000 n=14+16)
BM_PointerAnalysisPointerLoop 325µs ± 5% 324µs ± 4% ~ (p=0.496 n=18+20)
BM_PointerAnalysisBranch 193µs ± 0% 192µs ± 4% ~ (p=0.488 n=14+18)
BM_PointerAnalysisLoopAndBranch 521µs ± 1% 525µs ± 3% +0.94% (p=0.017 n=18+19)
BM_PointerAnalysisTwoLoops 337µs ± 1% 341µs ± 3% +1.19% (p=0.004 n=17+19)
BM_PointerAnalysisJoinFilePath 1.62ms ± 2% 1.64ms ± 3% +0.92% (p=0.021 n=20+20)
BM_PointerAnalysisCallInLoop 1.14ms ± 1% 1.15ms ± 4% ~ (p=0.135 n=16+18)
```

[^1]:
```
[B5 (ENTRY)]
Succs (1): B4

[B1]
1: [B4.9] ? [B2.1] : [B3.1]
2: [B4.4]([B4.6], [B1.1])
Preds (2): B2 B3
Succs (1): B0

[B2]
1: 1
Preds (1): B4
Succs (1): B1

[B3]
1: 0
Preds (1): B4
Succs (1): B1

[B4]
1: 0
2: int i = 0;
3: f
4: [B4.3] (ImplicitCastExpr, FunctionToPointerDecay, void (*)(int *, int))
5: i
6: &[B4.5]
7: cond
8: [B4.7] (ImplicitCastExpr, FunctionToPointerDecay, _Bool (*)(void))
9: [B4.8]()
T: [B4.9] ? ... : ...
Preds (1): B5
Succs (2): B2 B3

[B0 (EXIT)]
Preds (1): B1
```

show more ...

[clang][dataflow] Drop block-relative cap on worklist iterations. (#80033)

As per the FIXME, this cap never really served its purpose. This patch
simplifies to a single, caller-specified, absolute

[clang][dataflow] Drop block-relative cap on worklist iterations. (#80033)

As per the FIXME, this cap never really served its purpose. This patch
simplifies to a single, caller-specified, absolute cap.

show more ...

[clang][dataflow] Process terminator condition within `transferCFGBlock()`. (#78127)

In particular, it's important that we create the "fallback" atomic at
this point
(which we produce if the trans

[clang][dataflow] Process terminator condition within `transferCFGBlock()`. (#78127)

In particular, it's important that we create the "fallback" atomic at
this point
(which we produce if the transfer function didn't produce a value for
the
expression) so that it is placed in the correct environment.

Previously, we processed the terminator condition in the
`TerminatorVisitor`,
which put the fallback atomic in a copy of the environment that is
produced as
input for the _successor_ block, rather than the environment for the
block
containing the expression for which we produce the fallback atomic.

As a result, we produce different fallback atomics every time we process
the
successor block, and hence we don't have a consistent representation of
the
terminator condition in the flow condition.

This patch includes a test (authored by ymand@) that fails without the
fix.

show more ...

[clang][dataflow] Make cap on block visits configurable by caller. (#77481)

Previously, we hard-coded the cap on block visits inside the framework.
This
patch enables the caller to specify the cap i

[clang][dataflow] Make cap on block visits configurable by caller. (#77481)

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.

show more ...

Revert "[clang][dataflow] Remove unused private field 'StmtToEnv' (NFC)"

Revert it after 1aacdfe473276ad631db773310fe167ec93fb764

Revert "[clang][dataflow] Process terminator condition within `transferCFGBlock()`." (#77895)

Reverts llvm/llvm-project#77750

[clang][dataflow] Remove unused private field 'StmtToEnv' (NFC)

llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp:148:23:
error: private field 'StmtToEnv' is not used [-W

[clang][dataflow] Remove unused private field 'StmtToEnv' (NFC)

llvm-project/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp:148:23:
error: private field 'StmtToEnv' is not used [-Werror,-Wunused-private-field]
148 | const StmtToEnvMap &StmtToEnv;
| ^
1 error generated.

show more ...

[clang][dataflow] Process terminator condition within `transferCFGBlock()`. (#77750)

In particular, it's important that we create the "fallback" atomic at
this point
(which we produce if the trans

[clang][dataflow] Process terminator condition within `transferCFGBlock()`. (#77750)

In particular, it's important that we create the "fallback" atomic at
this point
(which we produce if the transfer function didn't produce a value for
the
expression) so that it is placed in the correct environment.

Previously, we processed the terminator condition in the
`TerminatorVisitor`,
which put the fallback atomic in a copy of the environment that is
produced as
input for the _successor_ block, rather than the environment for the
block
containing the expression for which we produce the fallback atomic.

As a result, we produce different fallback atomics every time we process
the
successor block, and hence we don't have a consistent representation of
the
terminator condition in the flow condition.

This patch includes a test (authored by ymand@) that fails without the
fix.

show more ...

[clang][dataflow] Add `Environment::get<>()`. (#76027)

This template function casts the result of `getValue()` or
`getStorageLocation()` to a given subclass of `Value` or
`StorageLocation` (using

[clang][dataflow] Add `Environment::get<>()`. (#76027)

This template function casts the result of `getValue()` or
`getStorageLocation()` to a given subclass of `Value` or
`StorageLocation` (using `cast_or_null`).

It's a common pattern to do something like this:

```cxx
auto *Val = cast_or_null<PointerValue>(Env.getValue(E));
```

This can now be expressed more concisely like this:

```cxx
auto *Val = Env.get<PointerValue>(E);
```

Instead of adding a new method `get()`, I had originally considered
simply adding a template parameter to `getValue()` and
`getStorageLocation()` (with a default argument of `Value` or
`StorageLocation`), but this results in an undesirable repetition at the
callsite, e.g. `getStorageLocation<RecordStorageLocation>(...)`. The
`Value` and `StorageLocation` in the method name adds nothing of value
when the template argument already contains this information, so it
seemed best to shorten the method name to simply `get()`.

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] Clear `ExprToLoc` and `ExprToVal` at the start of a block. (#72985)

We never need to access entries from these maps outside of the current
basic
block. This could only ever becom

[clang][dataflow] Clear `ExprToLoc` and `ExprToVal` at the start of a block. (#72985)

We never need to access entries from these maps outside of the current
basic
block. This could only ever become a consideration when flow control
happens
inside a full-expression (i.e. we have multiple basic blocks for a full
expression); there are two kinds of expression where this can happen,
but we
already deal with these in other ways:

* Short-circuiting logical operators (`&&` and `||`) have operands that
live in
different basic blocks than the operator itself, but we already have
code in
the framework to retrieve the value of these operands from the
environment
for the block they are computed in, rather than in the environment of
the
block containing the operator.

* The conditional operator similarly has operands that live in different
basic
blocks. However, we currently don't implement a transfer function for
the
conditional operator. When we do this, we need to retrieve the values of
the
operands from the environments of the basic blocks they live in, as we
already do for logical operators. This patch adds a comment to this
effect
to the code.

Clearing out `ExprToLoc` and `ExprToVal` has two benefits:

* We avoid performing joins on boolean expressions contained in
`ExprToVal` and
hence extending the flow condition in cases where this is not needed.
Simpler
flow conditions should reduce the amount of work we do in the SAT
solver.

* Debugging becomes easier when flow conditions are simpler and
`ExprToLoc` /
`ExprToVal` don’t contain any extraneous entries.

Benchmark results on Crubit's `pointer_nullability_analysis_benchmark
show a
slight runtime increase for simple benchmarks, offset by substantial
runtime
reductions for more complex benchmarks:

```
name old cpu/op new cpu/op delta
BM_PointerAnalysisCopyPointer 29.8µs ± 1% 29.9µs ± 4% ~ (p=0.879 n=46+49)
BM_PointerAnalysisIntLoop 101µs ± 3% 104µs ± 4% +2.96% (p=0.000 n=55+57)
BM_PointerAnalysisPointerLoop 378µs ± 3% 245µs ± 3% -35.09% (p=0.000 n=47+55)
BM_PointerAnalysisBranch 118µs ± 2% 122µs ± 3% +3.37% (p=0.000 n=59+59)
BM_PointerAnalysisLoopAndBranch 779µs ± 3% 413µs ± 5% -47.01% (p=0.000 n=56+45)
BM_PointerAnalysisTwoLoops 187µs ± 3% 192µs ± 5% +2.80% (p=0.000 n=57+58)
BM_PointerAnalysisJoinFilePath 17.4ms ± 3% 7.2ms ± 3% -58.75% (p=0.000 n=58+57)
BM_PointerAnalysisCallInLoop 14.7ms ± 4% 10.3ms ± 2% -29.87% (p=0.000 n=56+58)
```

show more ...