This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.
This is part of an effort to migrate from llvm::Optional to
std::optional:
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
* Adds API support for widening of lattice elements and environments,
* Updates the algorithm to apply widening where appropriate,
* Implements widening for boolean values. In the process, moves the unsoundness
of comparison from the default implementation of
`Environment::ValueModel::compare` to model-specific handling inside
`DataflowEnvironment::equivalentTo`. This change is intended to clarify
the source and location of unsoundess.
This patch is a replacement for, and was based substantially on, https://reviews.llvm.org/D131645.
Differential Revision: https://reviews.llvm.org/D137948
This revision fixes typos where there are 2 consecutive words which are
duplicated. There should be no code changes in this revision (only
changes to comments and docs). Do let me know if there are any
undesirable changes in this revision. Thanks.
Currently, the API for a model's custom value comparison returns a
boolean. Therefore, models cannot distinguish between situations where the
values are recognized by the model and different and those where the values are
just not recognized. This patch changes the return value to a tri-valued enum,
allowing models to express "don't know".
This patch is essentially a NFC -- no practical differences result from this
change in this patch. But, it prepares for future patches (particularly,
upcoming patches for widening) which will take advantage of the new flexibility.
Differential Revision: https://reviews.llvm.org/D137334
This patch adds an initial implementation for sign analysis, with the
following lattice (T: top, N: negative, Z: zero, P: positive, B: bottom):
T
/ | \
N Z P
\ | /
B
The lattice is implemented with `BoolValue` properties attached to other
`Value`s.
Differential Revision: https://reviews.llvm.org/D136668
Defines an equivalence relation on the `Value` type to standardize several
places in the code where we replicate the ~same equivalence comparison.
Differential Revision: https://reviews.llvm.org/D135964
Currently, our boolean formulas (`BoolValue`) don't form a lattice, since they
have no Top element. This patch adds such an element, thereby "completing" the
built-in model of bools to be a proper semi-lattice. It still has infinite
height, which is its own problem, but that can be solved separately, through
widening and the like.
Patch 1 for Issue #56931.
Differential Revision: https://reviews.llvm.org/D135397
Extend the context-sensitive analysis to handle a call to a method (of the same
class) from within a method. That, is a member-call expression through `this`.
Differential Revision: https://reviews.llvm.org/D134432
- Remove use of `runDataflowAnalysis` to keep test isolated.
- Add test for `ASTMatchSwitch<CXXCtorInitializer, ...>`.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D133935
To keep API of transfer functions consistent.
The single use of this transfer function in `ChromiumCheckModel` is also updated.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D133933
- Update `transfer` and `diagnose` to take `const CFGElement *` as input in `Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel`.
- Update `clang-tools-extra/clang-tidy/bugprone/UncheckedOptionalAccessCheck.cpp` accordingly.
- Rename `runDataflowAnalysisOnCFG` to `runDataflowAnalysis` and remove the deprecated `runDataflowAnalysis` (this was only used by the now updated optional check).
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D133930
Moves the work required for retrieving annotation states into the `SetupTest` and `PostVisitCFG` callback to avoid having to run a separate pass over the CFG after analysis has completed.
Reviewed By: gribozavr2, sgatev, ymandel
Differential Revision: https://reviews.llvm.org/D132377
- Add `AnalysisInputs` struct as the parameters for `checkDataflow`, and renamed `AnalysisData` struct to `AnalysisOutputs` which contains the data structures generated from a dataflow analysis run.
- Remove compulsory binding from statement to annotations. Instead, `checkDataflow` in the most general form takes a `VerifyResults` callback which takes as input an `AnalysisOutputs` struct. This struct contains the data structures generated by the analysis that can then be tested. We then introduce two overloads/wrappers of `checkDataflow` for different mechanisms of testing - one which exposes annotation line numbers and is not restricted to statements, and the other which exposes states computed after annotated statements. In the future, we should look at retrieving the analysis states for constructs other than statements.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D132147
`MatchSwitch` currently takes in matchers and functions for the `Stmt` class.
This patch generalises the match switch utility (renamed to `ASTMatchSwitch`) to work for different AST node types by introducing a template argument which is the base type for the AST nodes that the match switch will handle.
A `CFGMatchSwitch` is introduced as a wrapper around multiple `ASTMatchSwitch`s for different base types. It works by unwrapping `CFGElement`s into their contained AST nodes and passing the nodes to the relevant `ASTMatchSwitch`. The `CFGMatchSwitch` currently only handles `CFGStmt` and `CFGInitializer`.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D131616
`MatchSwitch` currently takes in matchers and functions for the `Stmt` class.
This patch generalises the match switch utility (renamed to `ASTMatchSwitch`) to work for different AST node types by introducing a template argument which is the base type for the AST nodes that the match switch will handle.
A `CFGMatchSwitch` is introduced as a wrapper around multiple `ASTMatchSwitch`s for different base types. It works by unwrapping `CFGElement`s into their contained AST nodes and passing the nodes to the relevant `ASTMatchSwitch`. The `CFGMatchSwitch` currently only handles `CFGStmt` and `CFGInitializer`.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D131616
Previously, the transfer function `void transfer(const Stmt *, ...)` overriden by users is restricted to apply only on `CFGStmt`s and its contained `Stmt`.
By using a transfer function (`void transfer(const CFGElement *, ...)`) that takes a `CFGElement` as input, this patch extends user-defined analysis to all kinds of `CFGElement`. For example, users can now handle `CFGInitializer`s where `CXXCtorInitializer` AST nodes are contained.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D131614
This patch adds a `Depth` field (default value 2) to `ContextSensitiveOptions`, allowing context-sensitive analysis of functions that call other functions. This also requires replacing the `DeclCtx` field on `Environment` with a `CallString` field that contains a vector of decl contexts, to ensure that the analysis doesn't try to analyze recursive or mutually recursive calls (which would result in a crash, due to the way we handle `StorageLocation`s).
Reviewed By: xazax.hun
Differential Revision: https://reviews.llvm.org/D131809
This patch restructures `DataflowAnalysisOptions` and `TransferOptions` to use `llvm::Optional`, in preparation for adding more sub-options to the `ContextSensitiveOptions` struct introduced here.
Reviewed By: sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D131779
This patch modifies `Environment`'s `pushCall` method to pass over arguments that are missing storage locations, instead of crashing.
Reviewed By: gribozavr2
Differential Revision: https://reviews.llvm.org/D131600
This patch adds the ability to context-sensitively analyze constructor bodies, by changing `pushCall` to allow both `CallExpr` and `CXXConstructExpr`, and extracting the main context-sensitive logic out of `VisitCallExpr` into a new `transferInlineCall` method which is now also called at the end of `VisitCXXConstructExpr`.
Reviewed By: ymandel, sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D131438
This patch modifies `Environment`'s `pushCall` method to pass over arguments that are missing storage locations, instead of crashing.
Reviewed By: gribozavr2
Differential Revision: https://reviews.llvm.org/D131600
This patch adds the ability to context-sensitively analyze constructor bodies, by changing `pushCall` to allow both `CallExpr` and `CXXConstructExpr`, and extracting the main context-sensitive logic out of `VisitCallExpr` into a new `transferInlineCall` method which is now also called at the end of `VisitCXXConstructExpr`.
Reviewed By: ymandel, sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D131438
This patch adds the ability to context-sensitively analyze method bodies, by moving `ThisPointeeLoc` from `DataflowAnalysisContext` to `Environment`, and adding code in `pushCall` to set it.
Reviewed By: ymandel, sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D131170
This patch adds a `ReturnLoc` field to the `Environment`, serving a similar to the `ThisPointeeLoc` field in the `DataflowAnalysisContext`. It then uses that (along with a new `VisitReturnStmt` method in `TransferVisitor`) to handle non-`void`-returning functions in context-sensitive analysis.
Reviewed By: ymandel, sgatev
Differential Revision: https://reviews.llvm.org/D130600
Make the types of the post visit callbacks in `transferBlock` and
`runTypeErasedDataflowAnalysis` consistent.
Differential Revision: https://reviews.llvm.org/D131014
Reviewed-by: ymandel, xazax.hun, gribozavr2
This patch enables context-sensitive analysis of multiple different calls to the same function (see the `ContextSensitiveSetBothTrueAndFalse` example in the `TransferTest` suite) by replacing the `Environment` copy-assignment with a call to the new `popCall` method, which `std::move`s some fields but specifically does not move `DeclToLoc` and `ExprToLoc` from the callee back to the caller.
To enable this, the `StorageLocation` for a given parameter needs to be stable across different calls to the same function, so this patch also improves the modeling of parameter initialization, using `ReferenceValue` when necessary (for arguments passed by reference).
This approach explicitly does not work for recursive calls, because we currently only plan to use this context-sensitive machinery to support specialized analysis models we write, not analysis of arbitrary callees.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D130726
This patch adds initial support for context-sensitive analysis of simple functions whose definition is available in the translation unit, guarded by the `ContextSensitive` flag in the new `TransferOptions` struct. When this option is true, the `VisitCallExpr` case in the builtin transfer function has a fallthrough case which checks for a direct callee with a body. In that case, it constructs a CFG from that callee body, uses the new `pushCall` method on the `Environment` to make an environment to analyze the callee, and then calls `runDataflowAnalysis` with a `NoopAnalysis` (disabling context-sensitive analysis on that sub-analysis, to avoid problems with recursion). After the sub-analysis completes, the `Environment` from its exit block is simply assigned back to the environment at the callsite.
The `pushCall` method (which currently only supports non-method functions with some restrictions) maps the `SourceLocation`s for all the parameters to the existing source locations for the corresponding arguments from the callsite.
This patch adds a few tests to check that this context-sensitive analysis works on simple functions. More sophisticated functionality will be added later; the most important next step is to explicitly model context in some fields of the `DataflowAnalysisContext` class, as mentioned in a `FIXME` comment in the `pushCall` implementation.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D130306
Depends On D130305
This patch adds initial support for context-sensitive analysis of simple functions whose definition is available in the translation unit, guarded by the `ContextSensitive` flag in the new `TransferOptions` struct. When this option is true, the `VisitCallExpr` case in the builtin transfer function has a fallthrough case which checks for a direct callee with a body. In that case, it constructs a CFG from that callee body, uses the new `pushCall` method on the `Environment` to make an environment to analyze the callee, and then calls `runDataflowAnalysis` with a `NoopAnalysis` (disabling context-sensitive analysis on that sub-analysis, to avoid problems with recursion). After the sub-analysis completes, the `Environment` from its exit block is simply assigned back to the environment at the callsite.
The `pushCall` method (which currently only supports non-method functions with some restrictions) first calls `initGlobalVars`, then maps the `SourceLocation`s for all the parameters to the existing source locations for the corresponding arguments from the callsite.
This patch adds a few tests to check that this context-sensitive analysis works on simple functions. More sophisticated functionality will be added later; the most important next step is to explicitly model context in some fields of the `DataflowAnalysisContext` class, as mentioned in a `TODO` comment in the `pushCall` implementation.
Reviewed By: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D130306
Previously we used to desugar implications and biconditionals into
equivalent CNF/DNF as soon as possible. However, this desugaring makes
debug output (Environment::dump()) less readable than it could be.
Therefore, it makes sense to keep the sugared representation of a
boolean formula, and desugar it in the solver.
Reviewed By: sgatev, xazax.hun, wyt
Differential Revision: https://reviews.llvm.org/D130519
BooleanFormula::addClause has an invariant that a clause has no duplicated
literals. When the solver was desugaring a formula into CNF clauses, it
could construct a clause with such duplicated literals in two cases.
Reviewed By: sgatev, ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D130522
Fix `MapLattice` API to return `std::pair<iterator, bool>`,
allowing users to detect when an element has been inserted without
performing a redundant map lookup.
Differential Revision: https://reviews.llvm.org/D130497
This patch connects the check for const-correctness with the new general
utility to add `const` to variables.
The code-transformation is only done, if the detected variable for const-ness
is not part of a group-declaration.
The check allows to control multiple facets of adding `const`, e.g. if pointers themself should be
marked as `const` if they are not changed.
Reviewed By: njames93
Differential Revision: https://reviews.llvm.org/D54943
Fangrui Song