* 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
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
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
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 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
Rename `DataflowAnalysisContext::getStableStorageLocation(QualType)`
to `createStorageLocation`, to make it clear that it doesn't return
a stable storage location.
Differential Revision: https://reviews.llvm.org/D131021
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
The latter way to abbreviate is a lot more common in the LLVM codebase.
Reviewed By: sgatev, xazax.hun
Differential Revision: https://reviews.llvm.org/D130423
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
`createStorageLocation` in `DataflowEnvironment` is now a trivial wrapper around the logic in `DataflowAnalysisContext`.
Additionally, `getObjectFields` and `getFieldsFromClassHierarchy` (required for the implementation of `createStorageLocation`) are also moved to `DataflowAnalysisContext`.
Reviewed By: gribozavr2, sgatev
Differential Revision: https://reviews.llvm.org/D128359
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
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
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
A follow-up to 62b2a47 to centralize the logic that skips expressions
that the CFG does not emit. This allows client code to avoid
sprinkling this logic everywhere.
Add redirects in the transfer function to similarly skip such
expressions by forwarding the visit to the sub-expression.
Differential Revision: https://reviews.llvm.org/D124965
`IgnoreParenImpCasts` will remove implicit casts to bool
(e.g. `PointerToBoolean`), such that the resulting expression may not
be of the `bool` type. The `cast_or_null<BoolValue>` in
`extendFlowCondition` will then trigger an assert, as the pointer
expression will not have a `BoolValue`.
Instead, we only skip `ExprWithCleanups` and `ParenExpr` nodes, as the
CFG does not emit them.
Differential Revision: https://reviews.llvm.org/D124807
Enable efficient implementation of context-aware joining of distinct
boolean values. It can be used to join distinct boolean values while
preserving flow condition information.
Flow conditions are represented as Token <=> Clause iff formulas. To
perform context-aware joining, one can simply add the tokens of flow
conditions to the formula when joining distinct boolean values, e.g:
`makeOr(makeAnd(FC1, Val1), makeAnd(FC2, Val2))`. This significantly
simplifies the implementation of `Environment::join`.
This patch removes the `DataflowAnalysisContext::getSolver` method.
The `DataflowAnalysisContext::flowConditionImplies` method should be
used instead.
Reviewed-by: ymandel, xazax.hun
Differential Revision: https://reviews.llvm.org/D124395
This patch changes `Environment::join`, in the case that two values at the same
location are not (pointer) equal, to structurally compare indirection values
(pointers and references) for equivalence (that is, equivalent pointees) before
resorting to merging.
This change makes join consistent with equivalence, which also performs
structural comparison. It also fixes a bug where the values are `ReferenceValue`
but the merge creates a non-reference value. This case arises when the
`ReferenceValue`s were created to represent an lvalue, so the "reference-ness"
is not reflected in the type. In this case, the pointees will always be
equivalent, because lvalues at the same code location point to the location of a
fixed declaration, whose location is itself stable across blocks.
We were unable to reproduce a unit test for this latter bug, but have verified
the fix in the context of a larger piece of code that triggers the bug.
Differential Revision: https://reviews.llvm.org/D124540
The current implementation mutates the environment as it performs the
join. However, that interferes with the call to the model's `merge` operation,
which can modify `MergedEnv`. Since any modifications are assumed to apply to
the post-join environment, providing the same environment for both is
incorrect. This mismatch is a particular concern for joining the flow
conditions, where modifications in the old environment may not be propagated to
the new one.
Differential Revision: https://reviews.llvm.org/D124104
Under the hood this prints the same as `QualType::getAsString()` but cuts out the middle-man when that string is sent to another raw_ostream.
Also cleaned up all the call sites where this occurs.
Reviewed By: aaron.ballman
Differential Revision: https://reviews.llvm.org/D123926
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 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
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
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/D120711
Yitzhak Mandelbaum