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

[clang][dataflow] Refactor `widen` API to be explicit about change effect. (#87233)

The previous API relied on pointer equality of inputs and outputs to
signal whether a change occured. This was to

[clang][dataflow] Refactor `widen` API to be explicit about change effect. (#87233)

The previous API relied on pointer equality of inputs and outputs to
signal whether a change occured. This was too subtle and led to bugs in
practice. It was also very limiting: the override could not return an equivalent (but
not identical) value.

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][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] Fix inaccuracies in `buildStmtToBasicBlockMap()`. (#82496)

See the comments added to the code for details on the inaccuracies that
have
now been fixed.

The patch adds tests that f

[clang][dataflow] Fix inaccuracies in `buildStmtToBasicBlockMap()`. (#82496)

See the comments added to the code for details on the inaccuracies that
have
now been fixed.

The patch adds tests that fail with the old implementation.

show more ...

[clang][dataflow] Add new `join` API and replace existing `merge` implementations. (#80361)

This patch adds a new interface for the join operation, now properly
called `join`. Originally, the framew

[clang][dataflow] Add new `join` API and replace existing `merge` implementations. (#80361)

This patch adds a new interface for the join operation, now properly
called `join`. Originally, the framework offered a single `merge`
operation, which could serve either as a join or a widening. In
practice, though we found this conflation didn't work for non-trivial
anlyses, and split of the widening operation (`widen`). This change
completes the transition by introducing a proper `join` with strict join
semantics.

In the process, it drops an odd (and often misused) aspect of `merge`
wherein callees could implictly instruct the framework to drop the
current entry by returning `false`. This features was never used
correctly in analyses and doesn't belong in a join operation, so it is
omitted.

---------

Co-authored-by: Dmitri Gribenko <gribozavr@gmail.com>
Co-authored-by: martinboehme <mboehme@google.com>

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

[clang][dataflow] Remove a redundant trailing semicolon. NFC.

This silences the following warning with GCC:

llvm-project/llvm/tools/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnal

[clang][dataflow] Remove a redundant trailing semicolon. NFC.

This silences the following warning with GCC:

llvm-project/llvm/tools/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp:89:4: warning: extra ‘;’ [-Wpedantic]
89 | };
| ^
| -

show more ...

[clang][dataflow] Disallow setting properties on `RecordValue`s. (#76042)

Instead, synthetic fields should now be used for the same purpose. These
have a
number of advantages, as described in
https:

[clang][dataflow] Disallow setting properties on `RecordValue`s. (#76042)

Instead, synthetic fields should now be used for the same purpose. These
have a
number of advantages, as described in
https://github.com/llvm/llvm-project/pull/73860, and longer-term, we
want to
eliminate `RecordValue` entirely.

As `RecordValue`s cannot have properties any more, I have replaced the
`OptionalIntAnalysis` with an equivalent analysis that tracks nullness
of
pointers (instead of whether an optional has a value). This serves the
same
purpose, namely to check whether the framework applies a custom
`merge()`
operation to widen properties.

show more ...

[clang][dataflow] Convert `SpecialBoolAnalysis` to synthetic fields. (#74706)

We're working towards eliminating `RecordValue`; this eliminates one
more
blocker on that path.

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

[clang][nullability] Use `proves()` and `assume()` instead of deprecated synonyms. (#70297)

[clang][dataflow] Check for backedges directly (instead of loop statements). (#68923)

Widen on backedge nodes, instead of nodes with a loop statement as
terminator.
This fixes #67834 and a precision

[clang][dataflow] Check for backedges directly (instead of loop statements). (#68923)

Widen on backedge nodes, instead of nodes with a loop statement as
terminator.
This fixes #67834 and a precision loss from assignment in a loop
condition. The
commit contains tests for both of these issues.

show more ...

[clang] Remove unused using decls (NFC)

Identified with misc-unused-using-decls.

[clang][dataflow] Remove declarations from `DeclToLoc` when their lifetime ends. (#67300)

After https://reviews.llvm.org/D153273, we're now able to use
`CFGLifetimeEnds`
together with the other CFG

[clang][dataflow] Remove declarations from `DeclToLoc` when their lifetime ends. (#67300)

After https://reviews.llvm.org/D153273, we're now able to use
`CFGLifetimeEnds`
together with the other CFG options we use.

show more ...

[clang][dataflow] Change `diagnoseFunction` to use `llvm::SmallVector` instead of `std::vector`. (#66014)

The template is agnostic as to the type used by the list, as long as it
is
compatible with `

[clang][dataflow] Change `diagnoseFunction` to use `llvm::SmallVector` instead of `std::vector`. (#66014)

The template is agnostic as to the type used by the list, as long as it
is
compatible with `llvm::move` and `std::back_inserter`. In practice,
we've
encountered analyses which use different types (`llvm::SmallVector` vs
`std::vector`), so it seems preferable to leave this open to the caller.

show more ...

[clang][dataflow] Eliminate deprecated `DataflowAnalysis` constructor.

Reviewed By: ymandel, xazax.hun

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

[clang][dataflow][NFC] Remove obsolete references to `ReferenceValue` from comments.

`ReferenceValue` was removed in https://reviews.llvm.org/D155922.

Reviewed By: xazax.hun

Differential Revision:

[clang][dataflow][NFC] Remove obsolete references to `ReferenceValue` from comments.

`ReferenceValue` was removed in https://reviews.llvm.org/D155922.

Reviewed By: xazax.hun

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

show more ...

[clang][dataflow] Support range-for loops in fixpoint algorithm.

Adds support for recognizing range-for loops in the main algorithm for computing
the model fixpoint.

Differential Revision: https://

[clang][dataflow] Support range-for loops in fixpoint algorithm.

Adds support for recognizing range-for loops in the main algorithm for computing
the model fixpoint.

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

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] Remove `Strict` suffix from accessors.

For the time being, we're keeping the `Strict` versions around as deprecated synonyms so that clients can be migrated, but these synonyms wil

[clang][dataflow] Remove `Strict` suffix from accessors.

For the time being, we're keeping the `Strict` versions around as deprecated synonyms so that clients can be migrated, but these synonyms will be removed soon.

Depends On D156673

Reviewed By: ymandel, xazax.hun

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

show more ...

[clang][dataflow] Reverse course on `getValue()` deprecation.

In the [value categories RFC](https://discourse.llvm.org/t/70086), I proposed that the end state of the migration should be that `getVal

[clang][dataflow] Reverse course on `getValue()` deprecation.

In the [value categories RFC](https://discourse.llvm.org/t/70086), I proposed that the end state of the migration should be that `getValue()` should only be legal to call on prvalues.

As a stepping stone, to allow migrating off existing calls to `getValue()`, I proposed introducing `getValueStrict()`, which would already have the new semantics.

However, I've now reconsidered this. Any expression, whether prvalue or glvalue, has a value, so really there isn't any reason to forbid calling `getValue()` on glvalues. I'm therefore removing the deprecation from `getValue()` and transitioning existing `getValueStrict()` calls back to `getValue()`.

The other "strict" accessors are a different case. `setValueStrict()` should only be called on prvalues because glvalues need to have a storage location associated with them; it doesn't make sense to only set a value for them. And, of course, `getStorageLocationStrict()` and `setStorageLocationStrict()` should obviously only be called on glvalues because prvalues don't have storage locations.

Reviewed By: ymandel, xazax.hun

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

show more ...

[clang][dataflow] Add convenience function for analysing and `FunctionDecl` and diagnosing it.

The convenience function captures running the analysis and then collecting
diagnostics based on a `Diag

[clang][dataflow] Add convenience function for analysing and `FunctionDecl` and diagnosing it.

The convenience function captures running the analysis and then collecting
diagnostics based on a `Diagnoser` object. This pattern is valuable to
clang-tidy checks which analyze a function at a time, though it could be more
generally useful for analysis clients.

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

show more ...

[clang][dataflow] Add `refreshStructValue()`.

Besides being a useful abstraction, this function will help insulate existing clients of the framework from upcoming changes to the API of `StructValue`

[clang][dataflow] Add `refreshStructValue()`.

Besides being a useful abstraction, this function will help insulate existing clients of the framework from upcoming changes to the API of `StructValue` and `AggregateStorageLocation`.

Depends On D155202

Reviewed By: ymandel, xazax.hun

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

show more ...