21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/STLExtras.h"
24#include "llvm/Support/Casting.h"
25#include "llvm/Support/ErrorHandling.h"
40template <
typename K,
typename V>
42 const llvm::DenseMap<K, V> &Map2) {
43 llvm::DenseMap<K, V>
Result;
44 for (
auto &Entry : Map1) {
45 auto It = Map2.find(Entry.first);
46 if (It != Map2.end() && Entry.second == It->second)
47 Result.insert({Entry.first, Entry.second});
62 switch (Model.
compare(
Type, Val1, Env1, Val2, Env2)) {
82 llvm_unreachable(
"All cases covered in switch");
96 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
110 auto *Expr1 = cast<BoolValue>(&Val1);
111 auto *Expr2 = cast<BoolValue>(&Val2);
115 MergedEnv.
makeIff(MergedVal, *Expr1)),
117 MergedEnv.
makeIff(MergedVal, *Expr2))));
126 if (Model.
merge(
Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
138 if (isa<BoolValue>(&Prev)) {
139 assert(isa<BoolValue>(Current));
142 if (isa<TopBoolValue>(Prev))
150 if (
auto *W = Model.
widen(
Type, Prev, PrevEnv, Current, CurrentEnv))
161 if (
auto *
V = dyn_cast<VarDecl>(&D))
162 if (
V->hasGlobalStorage())
170 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
171 for (
const auto *B : Decomp->bindings())
172 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
174 if (
const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
183 for (
auto *Child : S.children())
184 if (Child !=
nullptr)
187 if (
auto *DS = dyn_cast<DeclStmt>(&S)) {
188 if (DS->isSingleDecl())
191 for (
auto *D : DS->getDeclGroup())
193 }
else if (
auto *E = dyn_cast<DeclRefExpr>(&S)) {
195 }
else if (
auto *E = dyn_cast<MemberExpr>(&S)) {
197 const ValueDecl *VD = E->getMemberDecl();
199 if (
const auto *FD = dyn_cast<FieldDecl>(VD))
207 for (
const VarDecl *D : Vars) {
218 : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
221 : DACtx(Other.DACtx), CallStack(Other.CallStack),
222 ReturnLoc(Other.ReturnLoc), ThisPointeeLoc(Other.ThisPointeeLoc),
223 DeclToLoc(Other.DeclToLoc), ExprToLoc(Other.ExprToLoc),
224 LocToVal(Other.LocToVal), MemberLocToStruct(Other.MemberLocToStruct),
225 FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
230 *
this = std::move(Copy);
237 CallStack.push_back(&DeclCtx);
239 if (
const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
240 assert(FuncDecl->getBody() !=
nullptr);
247 if (
const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&DeclCtx)) {
248 for (
const auto *Init : CtorDecl->inits()) {
249 if (
const auto *M = Init->getAnyMember())
251 const Expr *E = Init->getInit();
252 assert(E !=
nullptr);
257 if (
const auto *I = F->getInClassInitializer())
264 DACtx.addModeledFields(Fields);
268 for (
const auto *ParamDecl : FuncDecl->parameters()) {
269 assert(ParamDecl !=
nullptr);
276 QualType ReturnType = FuncDecl->getReturnType();
280 if (
const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
281 auto *
Parent = MethodDecl->getParent();
282 assert(
Parent !=
nullptr);
284 MethodDecl = dyn_cast<CXXMethodDecl>(
Parent->getDeclContext());
287 if (MethodDecl && !MethodDecl->isStatic()) {
288 QualType ThisPointeeType = MethodDecl->getThisObjectType();
291 setValue(*ThisPointeeLoc, *ThisPointeeVal);
298 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
307 if (
const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
308 if (
const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
309 if (!isa<CXXThisExpr>(Arg))
316 Env.pushCallInternal(Call->getDirectCallee(),
328 Env.ThisPointeeLoc = Env.ReturnLoc;
330 Env.pushCallInternal(Call->getConstructor(),
336void Environment::pushCallInternal(
const FunctionDecl *FuncDecl,
338 CallStack.push_back(FuncDecl);
344 if (
const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
345 for (
const auto *Init : CtorDecl->inits()) {
346 if (
const auto *M = Init->getAnyMember())
348 const Expr *E = Init->getInit();
349 assert(E !=
nullptr);
357 DACtx->addModeledFields(Fields);
365 for (
unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
366 assert(ParamIt != FuncDecl->
param_end());
368 const Expr *Arg = Args[ArgIndex];
370 if (ArgLoc ==
nullptr)
373 const VarDecl *Param = *ParamIt;
377 QualType ParamType = Param->getType();
378 if (ParamType->isReferenceType()) {
379 auto &Val =
takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
381 }
else if (
auto *ArgVal =
getValue(*ArgLoc)) {
397 this->LocToVal = std::move(CalleeEnv.LocToVal);
398 this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct);
399 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
404 assert(DACtx == Other.DACtx);
406 if (ReturnLoc != Other.ReturnLoc)
409 if (ThisPointeeLoc != Other.ThisPointeeLoc)
412 if (DeclToLoc != Other.DeclToLoc)
415 if (ExprToLoc != Other.ExprToLoc)
419 for (
auto &Entry : LocToVal) {
421 assert(Loc !=
nullptr);
423 Value *Val = Entry.second;
424 assert(Val !=
nullptr);
426 auto It = Other.LocToVal.find(Loc);
427 if (It == Other.LocToVal.end())
429 assert(It->second !=
nullptr);
442 assert(DACtx == PrevEnv.DACtx);
443 assert(ReturnLoc == PrevEnv.ReturnLoc);
444 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
445 assert(CallStack == PrevEnv.CallStack);
461 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
462 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
465 llvm::DenseMap<const StorageLocation *, Value *> WidenedLocToVal;
466 for (
auto &Entry : LocToVal) {
468 assert(Loc !=
nullptr);
470 Value *Val = Entry.second;
471 assert(Val !=
nullptr);
473 auto PrevIt = PrevEnv.LocToVal.find(Loc);
474 if (PrevIt == PrevEnv.LocToVal.end())
476 assert(PrevIt->second !=
nullptr);
479 WidenedLocToVal.insert({Loc, Val});
484 PrevEnv, *Val, *
this, Model);
485 WidenedLocToVal.insert({Loc, &WidenedVal});
486 if (&WidenedVal != PrevIt->second)
489 LocToVal = std::move(WidenedLocToVal);
492 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
493 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
494 LocToVal.size() != PrevEnv.LocToVal.size() ||
495 MemberLocToStruct.size() != PrevEnv.MemberLocToStruct.size())
503 assert(DACtx == Other.DACtx);
504 assert(ReturnLoc == Other.ReturnLoc);
505 assert(ThisPointeeLoc == Other.ThisPointeeLoc);
506 assert(CallStack == Other.CallStack);
512 JoinedEnv.CallStack = CallStack;
513 JoinedEnv.ReturnLoc = ReturnLoc;
514 JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
517 if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
521 if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
524 JoinedEnv.MemberLocToStruct =
526 if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
533 *FlowConditionToken, *Other.FlowConditionToken);
535 for (
auto &Entry : LocToVal) {
537 assert(Loc !=
nullptr);
539 Value *Val = Entry.second;
540 assert(Val !=
nullptr);
542 auto It = Other.LocToVal.find(Loc);
543 if (It == Other.LocToVal.end())
545 assert(It->second !=
nullptr);
548 JoinedEnv.LocToVal.insert({Loc, Val});
552 if (
Value *MergedVal =
555 JoinedEnv.LocToVal.insert({Loc, MergedVal});
559 if (LocToVal.size() != JoinedEnv.LocToVal.size())
562 *
this = std::move(JoinedEnv);
586 assert(!DeclToLoc.contains(&D));
587 DeclToLoc[&D] = &Loc;
592 auto It = DeclToLoc.find(&D);
593 return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
598 assert(!ExprToLoc.contains(&CanonE));
599 ExprToLoc[&CanonE] = &Loc;
606 return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
610 return ThisPointeeLoc;
622 LocToVal[&Loc] = &Val;
624 if (
auto *StructVal = dyn_cast<StructValue>(&Val)) {
625 auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
630 for (
const FieldDecl *Field : DACtx->getReferencedFields(
Type)) {
631 assert(Field !=
nullptr);
633 MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
634 if (
auto *FieldVal = StructVal->getChild(*Field))
639 auto It = MemberLocToStruct.find(&Loc);
640 if (It != MemberLocToStruct.end()) {
644 assert(It->second.first !=
nullptr);
647 assert(It->second.second !=
nullptr);
655 auto It = LocToVal.find(&Loc);
656 return It == LocToVal.end() ? nullptr : It->second;
675 int CreatedValuesCount = 0;
676 Value *Val = createValueUnlessSelfReferential(
Type, Visited, 0,
679 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
685Value *Environment::createValueUnlessSelfReferential(
687 int &CreatedValuesCount) {
688 assert(!
Type.isNull());
696 CreatedValuesCount++;
704 CreatedValuesCount++;
708 if (
Type->isReferenceType()) {
709 CreatedValuesCount++;
710 QualType PointeeType =
Type->castAs<ReferenceType>()->getPointeeType();
713 if (Visited.insert(PointeeType.getCanonicalType()).second) {
714 Value *PointeeVal = createValueUnlessSelfReferential(
715 PointeeType, Visited, Depth, CreatedValuesCount);
716 Visited.erase(PointeeType.getCanonicalType());
718 if (PointeeVal !=
nullptr)
722 return &
takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
725 if (
Type->isPointerType()) {
726 CreatedValuesCount++;
727 QualType PointeeType =
Type->castAs<PointerType>()->getPointeeType();
730 if (Visited.insert(PointeeType.getCanonicalType()).second) {
731 Value *PointeeVal = createValueUnlessSelfReferential(
732 PointeeType, Visited, Depth, CreatedValuesCount);
733 Visited.erase(PointeeType.getCanonicalType());
735 if (PointeeVal !=
nullptr)
739 return &
takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
742 if (
Type->isStructureOrClassType() ||
Type->isUnionType()) {
743 CreatedValuesCount++;
744 llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
745 for (
const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
746 assert(Field !=
nullptr);
748 QualType FieldType =
Field->getType();
749 if (Visited.contains(FieldType.getCanonicalType()))
752 Visited.insert(FieldType.getCanonicalType());
753 if (
auto *FieldValue = createValueUnlessSelfReferential(
754 FieldType, Visited, Depth + 1, CreatedValuesCount))
755 FieldValues.insert({
Field, FieldValue});
756 Visited.erase(FieldType.getCanonicalType());
760 std::make_unique<StructValue>(std::move(FieldValues)));
766StorageLocation &Environment::skip(StorageLocation &Loc,
SkipPast SP)
const {
773 if (
auto *Val = dyn_cast_or_null<ReferenceValue>(
getValue(Loc)))
774 return Val->getReferentLoc();
778 if (
auto *Val = dyn_cast_or_null<PointerValue>(
getValue(LocPastRef)))
779 return Val->getPointeeLoc();
782 llvm_unreachable(
"bad SkipPast kind");
785const StorageLocation &Environment::skip(
const StorageLocation &Loc,
787 return skip(*
const_cast<StorageLocation *
>(&Loc), SP);
801 OS <<
"DeclToLoc:\n";
802 for (
auto [D, L] : DeclToLoc)
803 OS <<
" [" << D->getName() <<
", " << L <<
"]\n";
805 OS <<
"ExprToLoc:\n";
806 for (
auto [E, L] : ExprToLoc)
807 OS <<
" [" << E <<
", " << L <<
"]\n";
810 for (
auto [L,
V] : LocToVal) {
811 OS <<
" [" << L <<
", " <<
V <<
": " << *
V <<
"]\n";
814 OS <<
"FlowConditionToken:\n";
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
C Language Family Type Representation.
Represents a call to a C++ constructor.
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Decl - This represents one declaration (or definition), e.g.
This represents one expression.
Represents a member of a struct/union/class.
const RecordDecl * getParent() const
Returns the parent of this field declaration, which is the struct in which this field is defined.
Represents a function declaration or definition.
Stmt * getBody(const FunctionDecl *&Definition) const
Retrieve the body (definition) of the function.
param_iterator param_end()
param_iterator param_begin()
A (possibly-)qualified type.
field_range fields() const
Stmt - This represents one statement.
The base class of the type hierarchy.
bool isBooleanType() const
bool isIntegerType() const
isIntegerType() does not include complex integers (a GCC extension).
bool isStructureOrClassType() const
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.
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
StorageLocation & getStableStorageLocation(const VarDecl &D)
Returns a stable storage location for D.
bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val)
Returns true if and only if the constraints of the flow condition identified by Token imply that Val ...
void addFlowConditionConstraint(AtomicBoolValue &Token, BoolValue &Constraint)
Adds Constraint to the flow condition identified by Token.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
StorageLocation & createStorageLocation(QualType Type)
Returns a new storage location appropriate for Type.
AtomicBoolValue & joinFlowConditions(AtomicBoolValue &FirstToken, AtomicBoolValue &SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token, llvm::raw_ostream &OS=llvm::dbgs())
Supplements Environment with non-standard comparison and join operations.
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.
virtual Value * 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 bool merge(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2, Value &MergedVal, Environment &MergedEnv)
Modifies MergedVal to approximate both Val1 and Val2.
Holds the state of the program (store and heap) at a given program point.
StorageLocation * getStorageLocation(const ValueDecl &D, SkipPast SP) const
Returns the storage location assigned to D in the environment, applying the SP policy for skipping pa...
std::enable_if_t< std::is_base_of< StorageLocation, T >::value, T & > takeOwnership(std::unique_ptr< T > Loc)
Transfers ownership of Loc to the analysis context and returns a reference to it.
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.
LatticeJoinEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
void addToFlowCondition(BoolValue &Val)
Adds Val to the set of clauses that constitute the flow condition.
Environment pushCall(const CallExpr *Call) const
Creates and returns an environment to use for an inline analysis of the callee.
LLVM_DUMP_METHOD void dump() const
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
BoolValue & makeTopBoolValue() const
Returns a unique instance of boolean Top.
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
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.
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...
bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const
Returns whether this Environment can be extended to analyze the given Callee (i.e.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
Value * createValue(QualType Type)
Creates a value appropriate for Type, if Type is supported, otherwise return null.
void popCall(const Environment &CalleeEnv)
Moves gathered information back into this from a CalleeEnv created via pushCall.
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
AtomicBoolValue & getFlowConditionToken() const
Returns the token that identifies the flow condition of the environment.
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
LatticeJoinEffect join(const Environment &Other, Environment::ValueModel &Model)
Joins the environment with Other by taking the intersection of storage locations and values that are ...
bool flowConditionImplies(BoolValue &Val) const
Returns true if and only if the clauses that constitute the flow condition imply that Val is true.
StorageLocation * getReturnStorageLocation() const
Returns the storage location of the return value or null, if unset.
Environment & operator=(const Environment &Other)
Models a symbolic pointer. Specifically, any value of type T*.
Base class for elements of the local variable store and of the heap.
Models a value of struct or class type, with a flat map of fields to child storage locations,...
void setChild(const ValueDecl &D, Value &Val)
Assigns Val as the child value for D.
Base class for all values computed by abstract interpretation.
static void getFieldsAndGlobalVars(const Decl &D, llvm::DenseSet< const FieldDecl * > &Fields, llvm::DenseSet< const VarDecl * > &Vars)
static Value & widenDistinctValues(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv, Environment::ValueModel &Model)
llvm::DenseMap< K, V > intersectDenseMaps(const llvm::DenseMap< K, V > &Map1, const llvm::DenseMap< K, V > &Map2)
Returns a map consisting of key-value entries that are present in both maps.
static void insertIfGlobal(const Decl &D, llvm::DenseSet< const FieldDecl * > &Fields, llvm::DenseSet< const VarDecl * > &Vars)
Initializes a global storage value.
bool areEquivalentValues(const Value &Val1, const Value &Val2)
An equivalence relation for values.
static constexpr int MaxCompositeValueDepth
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
static Value * mergeDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment &MergedEnv, Environment::ValueModel &Model)
Attempts to merge distinct values Val1 and Val2 in Env1 and Env2, respectively, of the same type Type...
static constexpr int MaxCompositeValueSize
SkipPast
Indicates what kind of indirections should be skipped past when retrieving storage locations or value...
@ ReferenceThenPointer
An optional reference should be skipped past, then an optional pointer should be skipped past.
@ Reference
An optional reference should be skipped past.
@ None
No indirections should be skipped past.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
static bool compareDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment::ValueModel &Model)
@ Result
The result type of a method or function.