23#include "llvm/ADT/DenseMap.h"
24#include "llvm/ADT/DenseSet.h"
25#include "llvm/ADT/MapVector.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/ScopeExit.h"
28#include "llvm/Support/ErrorHandling.h"
32#define DEBUG_TYPE "dataflow"
45 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
46 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {
47 llvm::DenseMap<const ValueDecl *, StorageLocation *>
Result;
48 for (
auto &Entry : DeclToLoc1) {
49 auto It = DeclToLoc2.find(Entry.first);
50 if (It != DeclToLoc2.end() && Entry.second == It->second)
51 Result.insert({Entry.first, Entry.second});
61template <
typename MapT> MapT
joinExprMaps(
const MapT &Map1,
const MapT &Map2) {
64 for (
const auto &Entry : Map2) {
65 [[maybe_unused]]
auto [It, Inserted] =
Result.insert(Entry);
68 assert(It->second == Entry.second);
100 switch (Model.
compare(
Type, Val1, Env1, Val2, Env2)) {
108 llvm_unreachable(
"All cases covered in switch");
122 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
136 auto &Expr1 = cast<BoolValue>(Val1).formula();
137 auto &Expr2 = cast<BoolValue>(Val2).formula();
138 auto &A = JoinedEnv.
arena();
142 A.makeEquals(JoinedVal, Expr1)),
144 A.makeEquals(JoinedVal, Expr2))));
145 return &A.makeBoolValue(JoinedVal);
150 Model.
join(
Type, Val1, Env1, Val2, Env2, *JoinedVal, JoinedEnv);
160 if (isa<BoolValue>(Prev) && isa<BoolValue>(Current)) {
164 auto &PrevBool = cast<BoolValue>(Prev);
165 auto &CurBool = cast<BoolValue>(Current);
167 if (isa<TopBoolValue>(Prev))
175 bool TruePrev = PrevEnv.
proves(PrevBool.formula());
176 bool TrueCur = CurrentEnv.
proves(CurBool.formula());
177 if (TruePrev && TrueCur)
179 if (!TruePrev && !TrueCur &&
190 if (
auto Result = Model.
widen(
Type, Prev, PrevEnv, Current, CurrentEnv))
200template <
typename Key>
202 const llvm::MapVector<Key, Value *> &Map2,
205 for (
auto &Entry : Map1) {
207 assert(K !=
nullptr);
209 Value *Val = Entry.second;
210 assert(Val !=
nullptr);
212 auto It = Map2.find(K);
213 if (It == Map2.end())
215 assert(It->second !=
nullptr);
227static llvm::MapVector<const StorageLocation *, Value *>
228joinLocToVal(
const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
229 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
232 llvm::MapVector<const StorageLocation *, Value *>
Result;
233 for (
auto &Entry : LocToVal) {
235 assert(Loc !=
nullptr);
237 Value *Val = Entry.second;
238 assert(Val !=
nullptr);
240 auto It = LocToVal2.find(Loc);
241 if (It == LocToVal2.end())
243 assert(It->second !=
nullptr);
246 Loc->
getType(), Val, Env1, It->second, Env2, JoinedEnv, Model)) {
247 Result.insert({Loc, JoinedVal});
256template <
typename Key>
257llvm::MapVector<Key, Value *>
259 const llvm::MapVector<Key, Value *> &PrevMap,
262 llvm::MapVector<Key, Value *> WidenedMap;
263 for (
auto &Entry : CurMap) {
265 assert(K !=
nullptr);
267 Value *Val = Entry.second;
268 assert(Val !=
nullptr);
270 auto PrevIt = PrevMap.find(K);
271 if (PrevIt == PrevMap.end())
273 assert(PrevIt->second !=
nullptr);
276 WidenedMap.insert({K, Val});
281 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);
282 WidenedMap.insert({K, WidenedVal});
302 explicit ResultObjectVisitor(
303 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,
304 RecordStorageLocation *LocForRecordReturnVal,
305 DataflowAnalysisContext &DACtx)
306 : ResultObjectMap(ResultObjectMap),
307 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}
309 bool shouldVisitImplicitCode() {
return true; }
311 bool shouldVisitLambdaBody()
const {
return false; }
317 void TraverseConstructorInits(
const CXXConstructorDecl *Ctor,
318 RecordStorageLocation *ThisPointeeLoc) {
319 assert(ThisPointeeLoc !=
nullptr);
320 for (
const CXXCtorInitializer *
Init : Ctor->inits()) {
321 Expr *InitExpr =
Init->getInit();
322 if (FieldDecl *Field =
Init->getMember();
323 Field !=
nullptr &&
Field->getType()->isRecordType()) {
324 PropagateResultObject(InitExpr, cast<RecordStorageLocation>(
325 ThisPointeeLoc->getChild(*Field)));
326 }
else if (
Init->getBaseClass()) {
327 PropagateResultObject(InitExpr, ThisPointeeLoc);
332 TraverseStmt(InitExpr);
336 if (
auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))
337 TraverseStmt(DefaultInit->getExpr());
341 bool TraverseDecl(Decl *D) {
347 if (isa_and_nonnull<RecordDecl>(D) || isa_and_nonnull<FunctionDecl>(D))
353 bool TraverseBindingDecl(BindingDecl *BD) {
356 if (VarDecl *HoldingVar = BD->getHoldingVar())
357 TraverseDecl(HoldingVar);
358 return RecursiveASTVisitor<ResultObjectVisitor>::TraverseBindingDecl(BD);
361 bool VisitVarDecl(VarDecl *VD) {
362 if (VD->getType()->isRecordType() && VD->hasInit())
363 PropagateResultObject(
365 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*VD)));
369 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) {
370 if (MTE->getType()->isRecordType())
371 PropagateResultObject(
373 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*MTE)));
377 bool VisitReturnStmt(ReturnStmt *Return) {
378 Expr *
RetValue = Return->getRetValue();
381 PropagateResultObject(
RetValue, LocForRecordReturnVal);
385 bool VisitExpr(Expr *E) {
391 if (E->isPRValue() && E->getType()->isRecordType() &&
392 !ResultObjectMap.contains(E))
393 PropagateResultObject(
394 E, &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*E)));
399 PropagateResultObjectToRecordInitList(
const RecordInitListHelper &InitList,
400 RecordStorageLocation *Loc) {
401 for (
auto [
Base,
Init] : InitList.base_inits()) {
402 assert(
Base->getType().getCanonicalType() ==
403 Init->getType().getCanonicalType());
408 PropagateResultObject(
Init, Loc);
411 for (
auto [Field,
Init] : InitList.field_inits()) {
414 if (
Field->getType()->isRecordType())
415 PropagateResultObject(
416 Init, cast<RecordStorageLocation>(Loc->getChild(*Field)));
423 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) {
424 if (!E->isPRValue() || !E->getType()->isRecordType()) {
431 ResultObjectMap[E] = Loc;
436 if (isa<CXXConstructExpr>(E) || isa<CallExpr>(E) || isa<LambdaExpr>(E) ||
437 isa<CXXDefaultArgExpr>(E) || isa<CXXDefaultInitExpr>(E) ||
438 isa<CXXStdInitializerListExpr>(E) ||
442 isa<BuiltinBitCastExpr>(E)) {
445 if (
auto *Op = dyn_cast<BinaryOperator>(E);
446 Op && Op->getOpcode() == BO_Cmp) {
451 if (
auto *InitList = dyn_cast<InitListExpr>(E)) {
452 if (!InitList->isSemanticForm())
454 if (InitList->isTransparent()) {
455 PropagateResultObject(InitList->getInit(0), Loc);
459 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList),
464 if (
auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(E)) {
465 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList),
470 if (
auto *Op = dyn_cast<BinaryOperator>(E); Op && Op->isCommaOp()) {
471 PropagateResultObject(Op->getRHS(), Loc);
475 if (
auto *Cond = dyn_cast<AbstractConditionalOperator>(E)) {
476 PropagateResultObject(Cond->getTrueExpr(), Loc);
477 PropagateResultObject(Cond->getFalseExpr(), Loc);
481 if (
auto *SE = dyn_cast<StmtExpr>(E)) {
482 PropagateResultObject(cast<Expr>(SE->getSubStmt()->body_back()), Loc);
488 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end());
490 if (Children.size() != 1)
493 assert(Children.size() == 1);
494 for (Stmt *S : Children)
495 PropagateResultObject(cast<Expr>(S), Loc);
499 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
500 RecordStorageLocation *LocForRecordReturnVal;
501 DataflowAnalysisContext &DACtx;
508 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
513 CallStack.push_back(&DeclCtx);
518 if (DeclCtx ==
nullptr)
521 const auto *FuncDecl = dyn_cast<FunctionDecl>(DeclCtx);
522 if (FuncDecl ==
nullptr)
525 assert(FuncDecl->doesThisDeclarationHaveABody());
527 initFieldsGlobalsAndFuncs(FuncDecl);
529 for (
const auto *ParamDecl : FuncDecl->parameters()) {
530 assert(ParamDecl !=
nullptr);
534 if (FuncDecl->getReturnType()->isRecordType())
535 LocForRecordReturnVal = &cast<RecordStorageLocation>(
538 if (
const auto *MethodDecl = dyn_cast<CXXMethodDecl>(DeclCtx)) {
539 auto *
Parent = MethodDecl->getParent();
540 assert(
Parent !=
nullptr);
544 if (
Capture.capturesVariable()) {
548 }
else if (
Capture.capturesThis()) {
549 const auto *SurroundingMethodDecl =
552 SurroundingMethodDecl->getFunctionObjectParameterType();
554 cast<RecordStorageLocation>(
createObject(ThisPointeeType)));
557 }
else if (MethodDecl->isImplicitObjectMemberFunction()) {
558 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
565 if (!isa<CXXConstructorDecl>(MethodDecl))
572 ResultObjectMap = std::make_shared<PrValueToResultObject>(
574 LocForRecordReturnVal));
579void Environment::initFieldsGlobalsAndFuncs(
const FunctionDecl *FuncDecl) {
586 DACtx->addModeledFields(Referenced.
Fields);
616 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
622 if (
const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(
Call)) {
623 if (
const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
624 if (!isa<CXXThisExpr>(Arg))
632 if (
Call->getType()->isRecordType() &&
Call->isPRValue())
633 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
635 Env.pushCallInternal(
Call->getDirectCallee(),
644 Env.ThisPointeeLoc = &
Env.getResultObjectLocation(*
Call);
645 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
647 Env.pushCallInternal(
Call->getConstructor(),
653void Environment::pushCallInternal(
const FunctionDecl *FuncDecl,
661 CallStack.push_back(FuncDecl);
663 initFieldsGlobalsAndFuncs(FuncDecl);
669 for (
unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
670 assert(ParamIt != FuncDecl->
param_end());
671 const VarDecl *Param = *ParamIt;
675 ResultObjectMap = std::make_shared<PrValueToResultObject>(
677 LocForRecordReturnVal));
688 this->LocToVal = std::move(CalleeEnv.LocToVal);
689 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
691 if (
Call->isGLValue()) {
692 if (CalleeEnv.ReturnLoc !=
nullptr)
694 }
else if (!
Call->getType()->isVoidType()) {
695 if (CalleeEnv.ReturnVal !=
nullptr)
703 this->LocToVal = std::move(CalleeEnv.LocToVal);
704 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
709 assert(DACtx ==
Other.DACtx);
711 if (ReturnVal !=
Other.ReturnVal)
714 if (ReturnLoc !=
Other.ReturnLoc)
717 if (LocForRecordReturnVal !=
Other.LocForRecordReturnVal)
720 if (ThisPointeeLoc !=
Other.ThisPointeeLoc)
723 if (DeclToLoc !=
Other.DeclToLoc)
726 if (ExprToLoc !=
Other.ExprToLoc)
740 assert(DACtx == PrevEnv.DACtx);
741 assert(ReturnVal == PrevEnv.ReturnVal);
742 assert(ReturnLoc == PrevEnv.ReturnLoc);
743 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);
744 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
745 assert(CallStack == PrevEnv.CallStack);
746 assert(ResultObjectMap == PrevEnv.ResultObjectMap);
756 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
757 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
758 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
765 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
766 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
767 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
768 LocToVal.size() != PrevEnv.LocToVal.size())
777 assert(EnvA.DACtx == EnvB.DACtx);
778 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);
779 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
780 assert(EnvA.CallStack == EnvB.CallStack);
781 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);
785 JoinedEnv.CallStack = EnvA.CallStack;
786 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;
787 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;
788 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
790 if (EnvA.CallStack.empty()) {
791 JoinedEnv.ReturnVal =
nullptr;
795 auto *
Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
796 assert(
Func !=
nullptr);
797 JoinedEnv.ReturnVal =
798 joinValues(
Func->getReturnType(), EnvA.ReturnVal, EnvA, EnvB.ReturnVal,
799 EnvB, JoinedEnv, Model);
802 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
803 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
805 JoinedEnv.ReturnLoc =
nullptr;
812 EnvA.FlowConditionToken, EnvB.FlowConditionToken);
815 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model);
818 JoinedEnv.ExprToVal =
joinExprMaps(EnvA.ExprToVal, EnvB.ExprToVal);
819 JoinedEnv.ExprToLoc =
joinExprMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
829 if (Val1 ==
nullptr || Val2 ==
nullptr)
862 assert(!DeclToLoc.contains(&D));
869 DeclToLoc[&D] = &Loc;
873 auto It = DeclToLoc.find(&D);
874 if (It == DeclToLoc.end())
891 assert(!ExprToLoc.contains(&CanonE));
892 ExprToLoc[&CanonE] = &Loc;
900 return It == ExprToLoc.end() ? nullptr : &*It->second;
908 assert(ResultObjectMap !=
nullptr);
910 assert(Loc !=
nullptr);
914 return cast<RecordStorageLocation>(
926 int CreatedValuesCount = 0;
929 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
936 assert(!isa<RecordStorageLocation>(Loc));
937 LocToVal[&Loc] = &Val;
946 ExprToVal[&CanonE] = &Val;
951 assert(!isa<RecordStorageLocation>(Loc));
952 return LocToVal.lookup(&Loc);
968 return It == ExprToVal.end() ? nullptr : It->second;
972 if (It == ExprToLoc.end())
979 int CreatedValuesCount = 0;
983 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
989Value *Environment::createValueUnlessSelfReferential(
991 int &CreatedValuesCount) {
992 assert(!
Type.isNull());
1002 CreatedValuesCount++;
1010 CreatedValuesCount++;
1014 if (
Type->isPointerType()) {
1015 CreatedValuesCount++;
1016 QualType PointeeType =
Type->getPointeeType();
1017 StorageLocation &PointeeLoc =
1018 createLocAndMaybeValue(PointeeType,
Visited, Depth, CreatedValuesCount);
1027Environment::createLocAndMaybeValue(QualType Ty,
1029 int Depth,
int &CreatedValuesCount) {
1030 if (!
Visited.insert(Ty.getCanonicalType()).second)
1032 auto EraseVisited = llvm::make_scope_exit(
1035 Ty = Ty.getNonReferenceType();
1037 if (Ty->isRecordType()) {
1045 if (
Value *Val = createValueUnlessSelfReferential(Ty,
Visited, Depth,
1046 CreatedValuesCount))
1056 int &CreatedValuesCount) {
1057 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
1058 if (FieldType->isRecordType()) {
1059 auto &FieldRecordLoc = cast<RecordStorageLocation>(FieldLoc);
1061 Visited, Depth + 1, CreatedValuesCount);
1065 if (!
Visited.insert(FieldType.getCanonicalType()).second)
1067 if (
Value *Val = createValueUnlessSelfReferential(
1068 FieldType,
Visited, Depth + 1, CreatedValuesCount))
1070 Visited.erase(FieldType.getCanonicalType());
1075 assert(Field !=
nullptr);
1076 QualType FieldType =
Field->getType();
1078 if (FieldType->isReferenceType()) {
1079 Loc.setChild(*Field,
1080 &createLocAndMaybeValue(FieldType,
Visited, Depth + 1,
1081 CreatedValuesCount));
1083 StorageLocation *FieldLoc = Loc.getChild(*Field);
1084 assert(FieldLoc !=
nullptr);
1091 assert(!FieldType->isReferenceType());
1092 initField(FieldType, Loc.getSyntheticField(FieldName));
1096StorageLocation &Environment::createObjectInternal(
const ValueDecl *D,
1098 const Expr *InitExpr) {
1099 if (Ty->isReferenceType()) {
1105 return *InitExprLoc;
1112 return createObjectInternal(D, Ty.getNonReferenceType(),
nullptr);
1115 StorageLocation &Loc =
1118 if (Ty->isRecordType()) {
1119 auto &
RecordLoc = cast<RecordStorageLocation>(Loc);
1123 Value *Val =
nullptr;
1161 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1162 if (LocForRecordReturnVal !=
nullptr)
1163 LocToName[LocForRecordReturnVal] =
"(returned record)";
1164 if (ThisPointeeLoc !=
nullptr)
1165 LocToName[ThisPointeeLoc] =
"this";
1167 OS <<
"DeclToLoc:\n";
1168 for (
auto [D, L] : DeclToLoc) {
1169 auto Iter = LocToName.insert({L, D->getNameAsString()}).first;
1170 OS <<
" [" <<
Iter->second <<
", " << L <<
"]\n";
1172 OS <<
"ExprToLoc:\n";
1173 for (
auto [E, L] : ExprToLoc)
1174 OS <<
" [" << E <<
", " << L <<
"]\n";
1176 OS <<
"ExprToVal:\n";
1177 for (
auto [E,
V] : ExprToVal)
1178 OS <<
" [" << E <<
", " <<
V <<
": " << *
V <<
"]\n";
1180 OS <<
"LocToVal:\n";
1181 for (
auto [L,
V] : LocToVal) {
1183 if (
auto Iter = LocToName.find(L);
Iter != LocToName.end())
1184 OS <<
" (" <<
Iter->second <<
")";
1185 OS <<
", " <<
V <<
": " << *
V <<
"]\n";
1189 if (
Func->getReturnType()->isReferenceType()) {
1190 OS <<
"ReturnLoc: " << ReturnLoc;
1191 if (
auto Iter = LocToName.find(ReturnLoc);
Iter != LocToName.end())
1192 OS <<
" (" <<
Iter->second <<
")";
1194 }
else if (
Func->getReturnType()->isRecordType() ||
1195 isa<CXXConstructorDecl>(
Func)) {
1196 OS <<
"LocForRecordReturnVal: " << LocForRecordReturnVal <<
"\n";
1197 }
else if (!
Func->getReturnType()->isVoidType()) {
1198 if (ReturnVal ==
nullptr)
1199 OS <<
"ReturnVal: nullptr\n";
1201 OS <<
"ReturnVal: " << *ReturnVal <<
"\n";
1204 if (isa<CXXMethodDecl>(
Func)) {
1205 OS <<
"ThisPointeeLoc: " << ThisPointeeLoc <<
"\n";
1215Environment::PrValueToResultObject Environment::buildResultObjectMap(
1221 PrValueToResultObject Map;
1223 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1224 if (
const auto *Ctor = dyn_cast<CXXConstructorDecl>(FuncDecl))
1225 Visitor.TraverseConstructorInits(Ctor, ThisPointeeLoc);
1226 Visitor.TraverseStmt(FuncDecl->
getBody());
1234 if (ImplicitObject ==
nullptr)
1238 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
1241 return cast_or_null<RecordStorageLocation>(
1248 if (
Base ==
nullptr)
1252 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
static void initField(Block *B, std::byte *Ptr, bool IsConst, bool IsMutable, bool IsActive, const Descriptor *D, unsigned FieldOffset)
llvm::DenseSet< const void * > Visited
static bool RetValue(InterpState &S, CodePtr &Pt, APValue &Result)
llvm::MachO::RecordLoc RecordLoc
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....
Expr * getImplicitObjectArgument() const
Retrieve the implicit object argument for the member call.
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 * getNonClosureAncestor()
Find the nearest non-closure ancestor of this context, i.e.
This represents one expression.
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()
bool doesThisDeclarationHaveABody() const
Returns whether this specific declaration of the function has a body.
FunctionDecl * getDefinition()
Get the definition for this declaration.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
A (possibly-)qualified type.
A class that does preorder or postorder depth-first traversal on the entire Clang AST and visits each...
bool TraverseDecl(Decl *D)
Recursively visit a declaration, by dispatching to Traverse*Decl() based on the argument's dynamic ty...
The base class of the type hierarchy.
bool isBooleanType() const
bool isPointerType() const
bool isIntegerType() const
isIntegerType() does not include complex integers (a GCC extension).
bool isReferenceType() const
bool isSpecificBuiltinType(unsigned K) const
Test for a particular builtin type.
bool isRecordType() 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.
const Formula & makeAtomRef(Atom A)
Returns a formula for the variable A.
const Formula & makeNot(const Formula &Val)
Returns a formula for the negation of Val.
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,...
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
Atom joinFlowConditions(Atom FirstToken, Atom SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
void addFlowConditionConstraint(Atom Token, const Formula &Constraint)
Adds Constraint to the flow condition identified by Token.
Atom forkFlowCondition(Atom Token)
Creates a new flow condition with the same constraints as the flow condition identified by Token and ...
StorageLocation & getStableStorageLocation(const ValueDecl &D)
Returns a stable storage location for D.
bool flowConditionImplies(Atom Token, const Formula &F)
Returns true if the constraints of the flow condition identified by Token imply that F is true.
bool flowConditionAllows(Atom Token, const Formula &F)
Returns true if the constraints of the flow condition identified by Token still allow F to be true.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
llvm::StringMap< QualType > getSyntheticFields(QualType Type)
Returns the names and types of the synthetic fields for the given record type.
StorageLocation & createStorageLocation(QualType Type)
Returns a new storage location appropriate for Type.
FieldSet getModeledFields(QualType Type)
Returns the fields of Type, limited to the set of fields modeled by this context.
LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token, llvm::raw_ostream &OS=llvm::dbgs())
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 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.
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.
RecordStorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
Environment pushCall(const CallExpr *Call) const
Creates and returns an environment to use for an inline analysis of the callee.
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
BoolValue & makeTopBoolValue() const
Returns a unique instance of boolean Top.
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.
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.
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...
bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const
Returns whether this Environment can be extended to analyze the given Callee (i.e.
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.
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.
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.
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).
const DeclContext * getDeclCtx() const
Returns the DeclContext of the block being analysed, if any.
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,...
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.
llvm::MapVector< Key, Value * > widenKeyToValueMap(const llvm::MapVector< Key, Value * > &CurMap, const llvm::MapVector< Key, Value * > &PrevMap, Environment &CurEnv, const Environment &PrevEnv, Environment::ValueModel &Model, LatticeEffect &Effect)
bool compareKeyToValueMaps(const llvm::MapVector< Key, Value * > &Map1, const llvm::MapVector< Key, Value * > &Map2, const Environment &Env1, const Environment &Env2, Environment::ValueModel &Model)
static llvm::DenseMap< const ValueDecl *, StorageLocation * > intersectDeclToLoc(const llvm::DenseMap< const ValueDecl *, StorageLocation * > &DeclToLoc1, const llvm::DenseMap< const ValueDecl *, StorageLocation * > &DeclToLoc2)
Returns a map consisting of key-value entries that are present in both maps.
static bool equateUnknownValues(Value::Kind K)
bool areEquivalentValues(const Value &Val1, const Value &Val2)
An equivalence relation for values.
static constexpr int MaxCompositeValueDepth
MapT joinExprMaps(const MapT &Map1, const MapT &Map2)
static constexpr int MaxCompositeValueSize
ReferencedDecls getReferencedDecls(const FunctionDecl &FD)
Returns declarations that are declared in or referenced from FD.
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...
static WidenResult widenDistinctValues(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv, Environment::ValueModel &Model)
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
static llvm::MapVector< const StorageLocation *, Value * > joinLocToVal(const llvm::MapVector< const StorageLocation *, Value * > &LocToVal, const llvm::MapVector< const StorageLocation *, Value * > &LocToVal2, const Environment &Env1, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)
static bool compareDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment::ValueModel &Model)
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...
static Value * joinDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment &JoinedEnv, Environment::ValueModel &Model)
Attempts to join distinct values Val1 and Val2 in Env1 and Env2, respectively, of the same type Type.
LatticeEffect
Effect indicating whether a lattice operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
@ Result
The result type of a method or function.
@ Other
Other implicit parameter.
A collection of several types of declarations, all referenced from the same function.
llvm::DenseSet< const VarDecl * > Globals
All variables with static storage duration, notably including static member variables and static vari...
llvm::DenseSet< const FunctionDecl * > Functions
Free functions and member functions which are referenced (but not necessarily called).
FieldSet Fields
Non-static member variables.
The result of a widen operation.