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
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
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
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
This patch moves `Analysis/FlowSensitive/NoopAnalysis.h` from `clang/unittests/` to `clang/include/clang/`, so that we can use it for doing context-sensitive analysis.
Reviewed By: ymandel, gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D130304
Treat `std::nullptr_t` as a regular scalar type to avoid tripping
assertions when analyzing code that uses `std::nullptr_t`.
Differential Revision: https://reviews.llvm.org/D129097
Many of our tests are currently written using `TEST_F` where the test fixture class doesn't have any `SetUp` or `TearDown` methods, and just one helper method. In those cases, this patch deletes the class and pulls its method out into a standalone function, using `TEST` instead of `TEST_F`.
There are still a few test files leftover in `clang/unittests/Analysis/FlowSensitive/` that use `TEST_F`:
- `DataflowAnalysisContextTest.cpp` because the class contains a `Context` field which is used
- `DataflowEnvironmentTest.cpp` because the class contains an `Environment` field which is used
- `SolverTest.cpp` because the class contains a `Vals` field which is used
- `TypeErasedDataflowAnalysisTest.cpp` because there are several different classes which all share the same method name
Reviewed By: ymandel, sgatev
Differential Revision: https://reviews.llvm.org/D128924
When a `nullptr` is assigned to a pointer variable, it is wrapped in a `ImplicitCastExpr` with cast kind `CK_NullTo(Member)Pointer`. This patch assigns singleton pointer values representing null to these expressions.
For each pointee type, a singleton null `PointerValue` is created and stored in the `NullPointerVals` map of the `DataflowAnalysisContext` class. The pointee type is retrieved from the implicit cast expression, and used to initialise the `PointeeLoc` field of the `PointerValue`. The `PointeeLoc` created is not mapped to any `Value`, reflecting the absence of value indicated by null pointers.
Reviewed By: gribozavr2, sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D128056
We distinguish between the referent location for `ReferenceValue` and pointee location for `PointerValue`. The former must be non-empty but the latter may be empty in the case of a `nullptr`
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D127745
This patch precedes a future patch to make PointeeLoc for PointerValue possibly empty (for nullptr), by using a pointer instead of a reference type.
ReferenceValue should maintain a non-empty PointeeLoc reference.
Reviewed By: gribozavr2
Differential Revision: https://reviews.llvm.org/D127312
This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.
Differential Revision: https://reviews.llvm.org/D120495
Reviewed-by: ymandel, xazax.hun
Currently, we assert that `CXXCtorInitializer`s are field initializers. Replace
the assertion with an early return. Otherwise, we crash every time we process a
constructor with a non-field (e.g. base class) initializer.
Differential Revision: https://reviews.llvm.org/D126419
The API for `AggregateStorageLocation` does not allow for missing fields (it asserts). Therefore, it is incorrect to filter out any fields at location-creation time which may be accessed by the code. Currently, we limit filtering to private, base-calss fields on the assumption that those can never be accessed. However, `friend` declarations can invalidate that assumption, thereby breaking our invariants.
This patch removes said field filtering to avoid violating the invariant of "no missing fields" for `AggregateStorageLocation`.
Differential Revision: https://reviews.llvm.org/D126420
When constructing the `Environment`, the `this` pointee is established
for a `CXXMethodDecl` by looking at its parent. However, inside of
lambdas, a `CXXThisExpr` refers to the captured `this` coming from the
enclosing member function.
When establishing the `this` pointee for a function, we check whether
the function is a lambda, and check for an enclosing member function
to establish the `this` pointee storage location.
Differential Revision: https://reviews.llvm.org/D126413
Support for unions is incomplete (per 99f7d55e) and the `this` pointee
storage location is not set for unions. The assert in
`VisitCXXThisExpr` is then guaranteed to trigger when analyzing member
functions of a union.
This commit changes the assert to an early-return. Any expression may
be undefined, and so having a value for the `CXXThisExpr` is not a
postcondition of the transfer function.
Differential Revision: https://reviews.llvm.org/D126405
Ignore `MemberLocToStruct` in environment comparison. As an ancillary data
structure, including it is redundant. We also can generate environments which
differ in their `MemberLocToStruct` but are otherwise equivalent.
Differential Revision: https://reviews.llvm.org/D126314
Sub-expressions that are logical operators are not spelled out
separately in basic blocks, so we need to manually visit them when we
encounter them. We do this in both the `TerminatorVisitor`
(conditionally) and the `TransferVisitor` (unconditionally), which can
cause cause an expression to be visited twice when the binary
operators are nested 2+ times.
This changes the visit in `TransferVisitor` to check if it has been
evaluated before trying to visit the sub-expression.
Differential Revision: https://reviews.llvm.org/D125821
Remove constraint that an initializing expression of struct type must have an
associated `Value`. This invariant is not and will not be guaranteed by the
framework, because of potentially uninitialized fields.
Differential Revision: https://reviews.llvm.org/D123961
Currently, when the framework is used with an analysis that does not override
`compareEquivalent`, it does not terminate for most loops. The root cause is the
interaction of (the default implementation of) environment comparison
(`compareEquivalent`) and the means by which locations and values are
allocated. Specifically, the creation of certain values (including: reference
and pointer values; merged values) results in allocations of fresh locations in
the environment. As a result, analysis of even trivial loop bodies produces
different (if isomorphic) environments, on identical inputs. At the same time,
the default analysis relies on strict equality (versus some relaxed notion of
equivalence). Together, when the analysis compares these isomorphic, yet
unequal, environments, to determine whether the successors of the given block
need to be (re)processed, the result is invariably "yes", thus preventing loop
analysis from reaching a fixed point.
There are many possible solutions to this problem, including equivalence that is
less than strict pointer equality (like structural equivalence) and/or the
introduction of an explicit widening operation. However, these solutions will
require care to be implemented correctly. While a high priority, it seems more
urgent that we fix the current default implentation to allow
termination. Therefore, this patch proposes, essentially, to change the default
comparison to trivally equate any two values. As a result, we can say precisely
that the analysis will process the loop exactly twice -- once to establish an
initial result state and the second to produce an updated result which will
(always) compare equal to the previous. While clearly unsound -- we are not
reaching a fix point of the transfer function, in practice, this level of
analysis will find many practical issues where a single iteration of the loop
impacts abstract program state.
Note, however, that the change to the default `merge` operation does not affect
soundness, because the framework already produces a fresh (sound) abstraction of
the value when the two values are distinct. The previous setting was overly
conservative.
Differential Revision: https://reviews.llvm.org/D123586
This patch adds basic modeling of `__builtin_expect`, just to propagate the
(first) argument, making the call transparent.
Driveby: adds tests for proper handling of other builtins.
Differential Revision: https://reviews.llvm.org/D122908
This patch extends the join logic for environments to explicitly handle
boolean values. It creates the disjunction of both source values, guarded by the
respective flow conditions from each input environment. This change allows the
framework to reason about boolean correlations across multiple branches (and
subsequent joins).
Differential Revision: https://reviews.llvm.org/D122838
Currently, the framework does not track derived class access to base
fields. This patch adds that support and a corresponding test.
Differential Revision: https://reviews.llvm.org/D122273
This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.
Differential Revision: https://reviews.llvm.org/D121455
This enables tests out of clang/unittests/Analysis/FlowSensitive to
use the testing support utilities.
Reviewed-by: ymandel, gribozavr2
Differential Revision: https://reviews.llvm.org/D121285
Adds a dataflow analysis that detects unsafe accesses to values of type
`std::optional`, `absl::optional`, or `base::Optional`.
Reviewed-by: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D121197
When pre-initializing fields in the environment, the code assumed that all
fields of a struct would be initialized. However, given limits on value
construction, that assumption is incorrect. This patch changes the code to drop
that assumption and thereby avoid dereferencing a nullptr.
Differential Revision: https://reviews.llvm.org/D121158
This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.
Reviewed-by: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D120984
Kazu Hirata