15#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
16#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/DenseSet.h"
31#include "llvm/ADT/MapVector.h"
32#include "llvm/Support/Compiler.h"
33#include "llvm/Support/ErrorHandling.h"
147 switch (
compare(
Type, Prev, PrevEnv, Current, CurrentEnv)) {
155 llvm_unreachable(
"all cases in switch covered");
163 FlowConditionToken(DACtx.
arena().makeFlowConditionToken()) {}
168 InitialTargetStmt = &S;
181 InitialTargetFunc = &FD;
340 template <
typename T>
341 std::enable_if_t<std::is_base_of_v<StorageLocation, T>,
T *>
345 template <
typename T>
346 std::enable_if_t<std::is_base_of_v<StorageLocation, T>,
T *>
355 return ThisPointeeLoc;
361 ThisPointeeLoc = &
Loc;
457 return createObjectInternal(
nullptr, Ty, InitExpr);
466 return createObjectInternal(&
D,
D.getType(),
D.getInit());
475 return createObjectInternal(&
D,
D.getType(), InitExpr);
533 template <
typename T>
534 std::enable_if_t<std::is_base_of_v<Value, T>,
T *>
538 template <
typename T>
539 std::enable_if_t<std::is_base_of_v<Value, T>,
T *>
543 template <
typename T>
544 std::enable_if_t<std::is_base_of_v<Value, T>,
T *>
get(
const Expr &
E)
const {
555 template <
typename T,
typename... Args>
556 std::enable_if_t<std::is_base_of<Value, T>::value,
T &>
663 return CallStack.empty() ? InitialTargetFunc : CallStack.back();
681 LLVM_DUMP_METHOD
void dump()
const;
682 LLVM_DUMP_METHOD
void dump(raw_ostream &OS)
const;
685 using PrValueToResultObject =
686 llvm::DenseMap<const Expr *, RecordStorageLocation *>;
704 int Depth,
int &CreatedValuesCount);
712 int Depth,
int &CreatedValuesCount);
722 int &CreatedValuesCount);
727 const Expr *InitExpr);
739 static PrValueToResultObject
745 static PrValueToResultObject
759 std::vector<const FunctionDecl *> CallStack;
768 Stmt *InitialTargetStmt =
nullptr;
777 std::shared_ptr<PrValueToResultObject> ResultObjectMap;
783 Value *ReturnVal =
nullptr;
800 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
801 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
806 llvm::MapVector<const Expr *, Value *> ExprToVal;
807 llvm::MapVector<const StorageLocation *, Value *> LocToVal;
809 Atom FlowConditionToken;
817 const Environment &
Env);
823 const Environment &
Env);
llvm::DenseSet< const void * > Visited
C Language Family Type Representation.
Represents a call to a C++ constructor.
Represents a call to a member function that may be written either with member call syntax (e....
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
This represents one expression.
Represents a function declaration or definition.
bool doesThisDeclarationHaveABody() const
Returns whether this specific declaration of the function has a body.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
A (possibly-)qualified type.
Stmt - This represents one statement.
The base class of the type hierarchy.
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Represents a variable declaration or definition.
The Arena owns the objects that model data within an analysis.
IntegerValue & makeIntLiteral(llvm::APInt Value)
Returns a symbolic integer value that models an integer literal equal to Value.
TopBoolValue & makeTopValue()
Creates a fresh Top boolean value.
BoolValue & makeBoolValue(const Formula &)
Creates a BoolValue wrapping a particular formula.
AtomicBoolValue & makeAtomValue()
Creates a fresh atom and wraps in in an AtomicBoolValue.
std::enable_if_t< std::is_base_of< StorageLocation, T >::value, T & > create(Args &&...args)
Creates a T (some subclass of StorageLocation), forwarding args to the constructor,...
const Formula & formula() const
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
Supplements Environment with non-standard comparison and join operations.
virtual std::optional< WidenResult > widen(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv)
This function may widen the current value – replace it with an approximation that can reach a fixed p...
virtual ~ValueModel()=default
virtual void join(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2, Value &JoinedVal, Environment &JoinedEnv)
Modifies JoinedVal to approximate both Val1 and Val2.
virtual ComparisonResult compare(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2)
Returns: Same: Val1 is equivalent to Val2, according to the model.
Holds the state of the program (store and heap) at a given program point.
bool allows(const Formula &) const
Returns true if the formula may be true when this point is reached.
void initializeFieldsWithValues(RecordStorageLocation &Loc)
LatticeEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
std::enable_if_t< std::is_base_of_v< Value, T >, T * > get(const StorageLocation &Loc) const
Returns the result of casting getValue(...) to a subclass of Value (using cast_or_null<T>).
RecordStorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
Environment pushCall(const CallExpr *Call) const
Creates and returns an environment to use for an inline analysis of the callee.
void clearValue(const StorageLocation &Loc)
Clears any association between Loc and a value in the environment.
StorageLocation * getStorageLocation(const ValueDecl &D) const
Returns the storage location assigned to D in the environment, or null if D isn't assigned a storage ...
LLVM_DUMP_METHOD void dump() const
Environment(DataflowAnalysisContext &DACtx, Stmt &S)
Creates an environment that uses DACtx to store objects that encompass the state of a program,...
void setReturnValue(Value *Val)
Sets the return value of the function currently being analyzed.
Environment(Environment &&Other)=default
BoolValue & makeTopBoolValue() const
Returns a unique instance of boolean Top.
StorageLocation & createObject(const VarDecl &D)
Creates an object for the variable declaration D.
void initializeFieldsWithValues(RecordStorageLocation &Loc, QualType Type)
Initializes the fields (including synthetic fields) of Loc with values, unless values of the field ty...
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
Value * getReturnValue() const
Returns the return value of the function currently being analyzed.
Environment fork() const
Returns a new environment that is a copy of this one.
void popCall(const CallExpr *Call, const Environment &CalleeEnv)
Moves gathered information back into this from a CalleeEnv created via pushCall.
Environment(DataflowAnalysisContext &DACtx)
Creates an environment that uses DACtx to store objects that encompass the state of a program.
bool equivalentTo(const Environment &Other, Environment::ValueModel &Model) const
Returns true if and only if the environment is equivalent to Other, i.e the two environments:
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
std::enable_if_t< std::is_base_of_v< Value, T >, T * > get(const ValueDecl &D) const
bool proves(const Formula &) const
Returns true if the formula is always true when this point is reached.
Value * getValue(const StorageLocation &Loc) const
Returns the value assigned to Loc in the environment or null if Loc isn't assigned a value in the env...
Environment & operator=(const Environment &Other)=delete
const FunctionDecl * getCurrentFunc() const
Returns the function currently being analyzed, or null if the code being analyzed isn't part of a fun...
BoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value
StorageLocation & createObject(QualType Ty, const Expr *InitExpr=nullptr)
Creates an object (i.e.
void assume(const Formula &)
Record a fact that must be true if this point in the program is reached.
DataflowAnalysisContext & getDataflowAnalysisContext() const
Returns the DataflowAnalysisContext used by the environment.
static Value * joinValues(QualType Ty, Value *Val1, const Environment &Env1, Value *Val2, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)
Returns a value that approximates both Val1 and Val2, or null if no such value can be produced.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
void removeDecl(const ValueDecl &D)
Removes the location assigned to D in the environment (if any).
RecordStorageLocation & getResultObjectLocation(const Expr &RecordPRValue) const
Returns the location of the result object for a record-type prvalue.
std::enable_if_t< std::is_base_of_v< StorageLocation, T >, T * > get(const Expr &E) const
ExprJoinBehavior
How to treat expression state (ExprToLoc and ExprToVal) in a join.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model, ExprJoinBehavior ExprBehavior)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
Value * createValue(QualType Type)
Creates a value appropriate for Type, if Type is supported, otherwise returns null.
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
IntegerValue & getIntLiteralValue(llvm::APInt Value) const
Returns a symbolic integer value that models an integer literal equal to Value
Environment & operator=(Environment &&Other)=default
void setThisPointeeStorageLocation(RecordStorageLocation &Loc)
Sets the storage location assigned to the this pointee in the environment.
Atom getFlowConditionToken() const
Returns a boolean variable that identifies the flow condition (FC).
Environment(DataflowAnalysisContext &DACtx, const FunctionDecl &FD)
Creates an environment that uses DACtx to store objects that encompass the state of a program,...
StorageLocation & createObject(const ValueDecl &D, const Expr *InitExpr)
Creates an object for the variable declaration D.
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
size_t callStackSize() const
Returns the size of the call stack, not counting the initial analysis target.
bool canDescend(unsigned MaxDepth, const FunctionDecl *Callee) const
Returns whether this Environment can be extended to analyze the given Callee (i.e.
std::enable_if_t< std::is_base_of_v< StorageLocation, T >, T * > get(const ValueDecl &D) const
Returns the result of casting getStorageLocation(...) to a subclass of StorageLocation (using cast_or...
void initialize()
Assigns storage locations and values to all parameters, captures, global variables,...
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
std::enable_if_t< std::is_base_of< Value, T >::value, T & > create(Args &&...args)
Creates a T (some subclass of Value), forwarding args to the constructor, and returns a reference to ...
void setReturnStorageLocation(StorageLocation *Loc)
Sets the storage location for the reference returned by the function currently being analyzed.
StorageLocation * getReturnStorageLocation() const
Returns the storage location for the reference returned by the function currently being analyzed.
std::enable_if_t< std::is_base_of_v< Value, T >, T * > get(const Expr &E) const
BoolValue & makeImplication(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS => RHS.
Models a symbolic pointer. Specifically, any value of type T*.
A storage location for a record (struct, class, or union).
Base class for elements of the local variable store and of the heap.
Base class for all values computed by abstract interpretation.
Atom
Identifies an atomic boolean variable such as "V1".
ComparisonResult
Indicates the result of a tentative comparison.
RecordStorageLocation * getImplicitObjectLocation(const CXXMemberCallExpr &MCE, const Environment &Env)
Returns the storage location for the implicit object of a CXXMemberCallExpr, or null if none is defin...
RecordStorageLocation * getBaseObjectLocation(const MemberExpr &ME, const Environment &Env)
Returns the storage location for the base object of a MemberExpr, or null if none is defined in the e...
LatticeEffect
Effect indicating whether a lattice operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
const FunctionProtoType * T
@ Other
Other implicit parameter.
A collection of several types of declarations, all referenced from the same function.
The result of a widen operation.
LatticeEffect Effect
Whether V represents a "change" (that is, a different value) with respect to the previous value in th...
Value * V
Non-null pointer to a potentially widened version of the input value.