26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/DenseSet.h"
28#include "llvm/ADT/MapVector.h"
29#include "llvm/ADT/PointerUnion.h"
30#include "llvm/ADT/STLExtras.h"
31#include "llvm/ADT/ScopeExit.h"
32#include "llvm/Support/ErrorHandling.h"
38#define DEBUG_TYPE "dataflow"
51 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
52 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {
53 llvm::DenseMap<const ValueDecl *, StorageLocation *>
Result;
54 for (
auto &Entry : DeclToLoc1) {
55 auto It = DeclToLoc2.find(Entry.first);
56 if (It != DeclToLoc2.end() && Entry.second == It->second)
57 Result.insert({Entry.first, Entry.second});
67template <
typename MapT> MapT
joinExprMaps(
const MapT &Map1,
const MapT &Map2) {
70 for (
const auto &Entry : Map2) {
71 [[maybe_unused]]
auto [It, Inserted] =
Result.insert(Entry);
74 assert(It->second == Entry.second);
106 switch (Model.
compare(
Type, Val1, Env1, Val2, Env2)) {
114 llvm_unreachable(
"All cases covered in switch");
128 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
142 auto &Expr1 = cast<BoolValue>(Val1).formula();
143 auto &Expr2 = cast<BoolValue>(Val2).formula();
144 auto &A = JoinedEnv.
arena();
148 A.makeEquals(JoinedVal, Expr1)),
150 A.makeEquals(JoinedVal, Expr2))));
151 return &A.makeBoolValue(JoinedVal);
156 Model.
join(
Type, Val1, Env1, Val2, Env2, *JoinedVal, JoinedEnv);
166 if (isa<BoolValue>(Prev) && isa<BoolValue>(Current)) {
170 auto &PrevBool = cast<BoolValue>(Prev);
171 auto &CurBool = cast<BoolValue>(Current);
173 if (isa<TopBoolValue>(Prev))
181 bool TruePrev = PrevEnv.
proves(PrevBool.formula());
182 bool TrueCur = CurrentEnv.
proves(CurBool.formula());
183 if (TruePrev && TrueCur)
185 if (!TruePrev && !TrueCur &&
196 if (
auto Result = Model.
widen(
Type, Prev, PrevEnv, Current, CurrentEnv))
206template <
typename Key>
208 const llvm::MapVector<Key, Value *> &Map2,
211 for (
auto &Entry : Map1) {
213 assert(K !=
nullptr);
215 Value *Val = Entry.second;
216 assert(Val !=
nullptr);
218 auto It = Map2.find(K);
219 if (It == Map2.end())
221 assert(It->second !=
nullptr);
233static llvm::MapVector<const StorageLocation *, Value *>
234joinLocToVal(
const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
235 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
238 llvm::MapVector<const StorageLocation *, Value *>
Result;
239 for (
auto &Entry : LocToVal) {
241 assert(
Loc !=
nullptr);
243 Value *Val = Entry.second;
244 assert(Val !=
nullptr);
246 auto It = LocToVal2.find(
Loc);
247 if (It == LocToVal2.end())
249 assert(It->second !=
nullptr);
252 Loc->getType(), Val, Env1, It->second, Env2, JoinedEnv, Model)) {
262template <
typename Key>
263llvm::MapVector<Key, Value *>
265 const llvm::MapVector<Key, Value *> &PrevMap,
268 llvm::MapVector<Key, Value *> WidenedMap;
269 for (
auto &Entry : CurMap) {
271 assert(K !=
nullptr);
273 Value *Val = Entry.second;
274 assert(Val !=
nullptr);
276 auto PrevIt = PrevMap.find(K);
277 if (PrevIt == PrevMap.end())
279 assert(PrevIt->second !=
nullptr);
282 WidenedMap.insert({K, Val});
287 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);
288 WidenedMap.insert({K, WidenedVal});
301class ResultObjectVisitor :
public AnalysisASTVisitor<ResultObjectVisitor> {
307 explicit ResultObjectVisitor(
308 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,
309 RecordStorageLocation *LocForRecordReturnVal,
310 DataflowAnalysisContext &DACtx)
311 : ResultObjectMap(ResultObjectMap),
312 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}
318 void TraverseConstructorInits(
const CXXConstructorDecl *Ctor,
319 RecordStorageLocation *ThisPointeeLoc) {
320 assert(ThisPointeeLoc !=
nullptr);
321 for (
const CXXCtorInitializer *
Init : Ctor->inits()) {
322 Expr *InitExpr =
Init->getInit();
323 if (FieldDecl *Field =
Init->getMember();
324 Field !=
nullptr && Field->getType()->isRecordType()) {
325 PropagateResultObject(InitExpr, cast<RecordStorageLocation>(
326 ThisPointeeLoc->getChild(*Field)));
327 }
else if (
Init->getBaseClass()) {
328 PropagateResultObject(InitExpr, ThisPointeeLoc);
333 TraverseStmt(InitExpr);
337 if (
auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))
338 TraverseStmt(DefaultInit->getExpr());
342 bool VisitVarDecl(VarDecl *VD) {
343 if (VD->getType()->isRecordType() && VD->hasInit())
344 PropagateResultObject(
346 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*VD)));
350 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) {
351 if (MTE->getType()->isRecordType())
352 PropagateResultObject(
354 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*MTE)));
358 bool VisitReturnStmt(ReturnStmt *Return) {
359 Expr *
RetValue = Return->getRetValue();
362 PropagateResultObject(
RetValue, LocForRecordReturnVal);
366 bool VisitExpr(Expr *
E) {
372 if (
E->isPRValue() &&
E->getType()->isRecordType() &&
373 !ResultObjectMap.contains(
E))
374 PropagateResultObject(
375 E, &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*
E)));
380 PropagateResultObjectToRecordInitList(
const RecordInitListHelper &InitList,
381 RecordStorageLocation *
Loc) {
382 for (
auto [
Base,
Init] : InitList.base_inits()) {
383 assert(
Base->getType().getCanonicalType() ==
384 Init->getType().getCanonicalType());
389 PropagateResultObject(
Init,
Loc);
392 for (
auto [Field,
Init] : InitList.field_inits()) {
395 if (
Field->getType()->isRecordType())
396 PropagateResultObject(
397 Init, cast<RecordStorageLocation>(
Loc->getChild(*Field)));
404 void PropagateResultObject(Expr *
E, RecordStorageLocation *
Loc) {
405 if (!
E->isPRValue() || !
E->getType()->isRecordType()) {
412 ResultObjectMap[
E] =
Loc;
417 if (isa<CXXConstructExpr>(
E) || isa<CallExpr>(
E) || isa<LambdaExpr>(
E) ||
418 isa<CXXDefaultArgExpr>(
E) || isa<CXXStdInitializerListExpr>(
E) ||
419 isa<AtomicExpr>(
E) || isa<CXXInheritedCtorInitExpr>(
E) ||
423 isa<BuiltinBitCastExpr>(
E)) {
426 if (
auto *Op = dyn_cast<BinaryOperator>(
E);
427 Op && Op->getOpcode() == BO_Cmp) {
432 if (
auto *InitList = dyn_cast<InitListExpr>(
E)) {
433 if (!InitList->isSemanticForm())
435 if (InitList->isTransparent()) {
436 PropagateResultObject(InitList->getInit(0),
Loc);
440 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList),
445 if (
auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(
E)) {
446 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList),
451 if (
auto *Op = dyn_cast<BinaryOperator>(
E); Op && Op->isCommaOp()) {
452 PropagateResultObject(Op->getRHS(),
Loc);
456 if (
auto *Cond = dyn_cast<AbstractConditionalOperator>(
E)) {
457 PropagateResultObject(Cond->getTrueExpr(),
Loc);
458 PropagateResultObject(Cond->getFalseExpr(),
Loc);
462 if (
auto *SE = dyn_cast<StmtExpr>(
E)) {
463 PropagateResultObject(cast<Expr>(SE->getSubStmt()->body_back()),
Loc);
467 if (
auto *DIE = dyn_cast<CXXDefaultInitExpr>(
E)) {
468 PropagateResultObject(DIE->getExpr(),
Loc);
474 SmallVector<Stmt *, 1> Children(
E->child_begin(),
E->child_end());
476 if (Children.size() != 1)
479 assert(Children.size() == 1);
480 for (Stmt *S : Children)
481 PropagateResultObject(cast<Expr>(S),
Loc);
485 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
486 RecordStorageLocation *LocForRecordReturnVal;
487 DataflowAnalysisContext &DACtx;
493 if (InitialTargetStmt ==
nullptr)
496 if (InitialTargetFunc ==
nullptr) {
499 std::make_shared<PrValueToResultObject>(buildResultObjectMap(
507 for (
const auto *ParamDecl : InitialTargetFunc->
parameters()) {
508 assert(ParamDecl !=
nullptr);
513 LocForRecordReturnVal = &cast<RecordStorageLocation>(
516 if (
const auto *MethodDecl = dyn_cast<CXXMethodDecl>(InitialTargetFunc)) {
517 auto *
Parent = MethodDecl->getParent();
518 assert(
Parent !=
nullptr);
522 if (
Capture.capturesVariable()) {
526 }
else if (
Capture.capturesThis()) {
528 const auto *SurroundingMethodDecl = cast<CXXMethodDecl>(Ancestor);
530 SurroundingMethodDecl->getFunctionObjectParameterType();
532 cast<RecordStorageLocation>(
createObject(ThisPointeeType)));
533 }
else if (
auto *FieldBeingInitialized =
534 dyn_cast<FieldDecl>(
Parent->getLambdaContextDecl())) {
538 FieldBeingInitialized->getParent()->getTypeForDecl(), 0))));
540 assert(
false &&
"Unexpected this-capturing lambda context.");
544 }
else if (MethodDecl->isImplicitObjectMemberFunction()) {
545 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
552 if (!isa<CXXConstructorDecl>(MethodDecl))
560 std::make_shared<PrValueToResultObject>(buildResultObjectMap(
562 LocForRecordReturnVal));
568void Environment::initFieldsGlobalsAndFuncs(
const ReferencedDecls &Referenced) {
571 DACtx->addModeledFields(Referenced.
Fields);
601 return CallStack.size() < MaxDepth && !llvm::is_contained(CallStack, Callee);
607 if (
const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(
Call)) {
608 if (
const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
609 if (!isa<CXXThisExpr>(Arg))
617 if (
Call->getType()->isRecordType() &&
Call->isPRValue())
618 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
620 Env.pushCallInternal(
Call->getDirectCallee(),
629 Env.ThisPointeeLoc = &
Env.getResultObjectLocation(*
Call);
630 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
632 Env.pushCallInternal(
Call->getConstructor(),
638void Environment::pushCallInternal(
const FunctionDecl *FuncDecl,
646 CallStack.push_back(FuncDecl);
654 for (
unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
655 assert(ParamIt != FuncDecl->
param_end());
656 const VarDecl *Param = *ParamIt;
660 ResultObjectMap = std::make_shared<PrValueToResultObject>(
662 LocForRecordReturnVal));
673 this->LocToVal = std::move(CalleeEnv.LocToVal);
674 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
676 if (
Call->isGLValue()) {
677 if (CalleeEnv.ReturnLoc !=
nullptr)
679 }
else if (!
Call->getType()->isVoidType()) {
680 if (CalleeEnv.ReturnVal !=
nullptr)
688 this->LocToVal = std::move(CalleeEnv.LocToVal);
689 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
694 assert(DACtx ==
Other.DACtx);
696 if (ReturnVal !=
Other.ReturnVal)
699 if (ReturnLoc !=
Other.ReturnLoc)
702 if (LocForRecordReturnVal !=
Other.LocForRecordReturnVal)
705 if (ThisPointeeLoc !=
Other.ThisPointeeLoc)
708 if (DeclToLoc !=
Other.DeclToLoc)
711 if (ExprToLoc !=
Other.ExprToLoc)
725 assert(DACtx == PrevEnv.DACtx);
726 assert(ReturnVal == PrevEnv.ReturnVal);
727 assert(ReturnLoc == PrevEnv.ReturnLoc);
728 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);
729 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
730 assert(CallStack == PrevEnv.CallStack);
731 assert(ResultObjectMap == PrevEnv.ResultObjectMap);
732 assert(InitialTargetFunc == PrevEnv.InitialTargetFunc);
733 assert(InitialTargetStmt == PrevEnv.InitialTargetStmt);
743 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
744 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
745 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
752 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
753 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
754 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
755 LocToVal.size() != PrevEnv.LocToVal.size())
764 assert(EnvA.DACtx == EnvB.DACtx);
765 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);
766 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
767 assert(EnvA.CallStack == EnvB.CallStack);
768 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);
769 assert(EnvA.InitialTargetFunc == EnvB.InitialTargetFunc);
770 assert(EnvA.InitialTargetStmt == EnvB.InitialTargetStmt);
774 JoinedEnv.CallStack = EnvA.CallStack;
775 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;
776 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;
777 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
778 JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc;
779 JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt;
783 JoinedEnv.ReturnVal =
nullptr;
785 JoinedEnv.ReturnVal =
786 joinValues(
Func->getReturnType(), EnvA.ReturnVal, EnvA, EnvB.ReturnVal,
787 EnvB, JoinedEnv, Model);
790 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
791 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
793 JoinedEnv.ReturnLoc =
nullptr;
800 EnvA.FlowConditionToken, EnvB.FlowConditionToken);
803 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model);
806 JoinedEnv.ExprToVal =
joinExprMaps(EnvA.ExprToVal, EnvB.ExprToVal);
807 JoinedEnv.ExprToLoc =
joinExprMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
817 if (Val1 ==
nullptr || Val2 ==
nullptr)
850 assert(!DeclToLoc.contains(&
D));
855 assert(
D.getType()->isReferenceType() || isa<BindingDecl>(
D) ||
857 DeclToLoc[&
D] = &
Loc;
861 auto It = DeclToLoc.find(&
D);
862 if (It == DeclToLoc.end())
876 assert(
E.isGLValue() ||
877 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
879 assert(!ExprToLoc.contains(&CanonE));
880 ExprToLoc[&CanonE] = &
Loc;
885 assert(
E.isGLValue() ||
886 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
888 return It == ExprToLoc.end() ? nullptr : &*It->second;
896 assert(ResultObjectMap !=
nullptr);
898 assert(
Loc !=
nullptr);
902 return cast<RecordStorageLocation>(
914 int CreatedValuesCount = 0;
917 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
924 assert(!isa<RecordStorageLocation>(
Loc));
925 LocToVal[&
Loc] = &Val;
934 ExprToVal[&CanonE] = &Val;
939 assert(!isa<RecordStorageLocation>(
Loc));
940 return LocToVal.lookup(&
Loc);
952 assert(!
E.getType()->isRecordType());
956 return It == ExprToVal.end() ? nullptr : It->second;
960 if (It == ExprToLoc.end())
967 int CreatedValuesCount = 0;
971 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
977Value *Environment::createValueUnlessSelfReferential(
979 int &CreatedValuesCount) {
980 assert(!
Type.isNull());
990 CreatedValuesCount++;
998 CreatedValuesCount++;
1002 if (
Type->isPointerType()) {
1003 CreatedValuesCount++;
1004 QualType PointeeType =
Type->getPointeeType();
1005 StorageLocation &PointeeLoc =
1006 createLocAndMaybeValue(PointeeType,
Visited, Depth, CreatedValuesCount);
1015Environment::createLocAndMaybeValue(QualType Ty,
1017 int Depth,
int &CreatedValuesCount) {
1018 if (!
Visited.insert(Ty.getCanonicalType()).second)
1020 auto EraseVisited = llvm::make_scope_exit(
1023 Ty = Ty.getNonReferenceType();
1025 if (Ty->isRecordType()) {
1033 if (
Value *Val = createValueUnlessSelfReferential(Ty,
Visited, Depth,
1034 CreatedValuesCount))
1044 int &CreatedValuesCount) {
1045 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
1046 if (FieldType->isRecordType()) {
1047 auto &FieldRecordLoc = cast<RecordStorageLocation>(FieldLoc);
1049 Visited, Depth + 1, CreatedValuesCount);
1053 if (!
Visited.insert(FieldType.getCanonicalType()).second)
1055 if (
Value *Val = createValueUnlessSelfReferential(
1056 FieldType,
Visited, Depth + 1, CreatedValuesCount))
1058 Visited.erase(FieldType.getCanonicalType());
1063 assert(Field !=
nullptr);
1064 QualType FieldType =
Field->getType();
1066 if (FieldType->isReferenceType()) {
1067 Loc.setChild(*Field,
1068 &createLocAndMaybeValue(FieldType,
Visited, Depth + 1,
1069 CreatedValuesCount));
1071 StorageLocation *FieldLoc =
Loc.getChild(*Field);
1072 assert(FieldLoc !=
nullptr);
1079 assert(!FieldType->isReferenceType());
1080 initField(FieldType,
Loc.getSyntheticField(FieldName));
1084StorageLocation &Environment::createObjectInternal(
const ValueDecl *
D,
1086 const Expr *InitExpr) {
1087 if (Ty->isReferenceType()) {
1093 return *InitExprLoc;
1100 return createObjectInternal(
D, Ty.getNonReferenceType(),
nullptr);
1103 StorageLocation &
Loc =
1106 if (Ty->isRecordType()) {
1111 Value *Val =
nullptr;
1149 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1150 if (LocForRecordReturnVal !=
nullptr)
1151 LocToName[LocForRecordReturnVal] =
"(returned record)";
1152 if (ThisPointeeLoc !=
nullptr)
1153 LocToName[ThisPointeeLoc] =
"this";
1155 OS <<
"DeclToLoc:\n";
1156 for (
auto [
D, L] : DeclToLoc) {
1157 auto Iter = LocToName.insert({L,
D->getNameAsString()}).first;
1158 OS <<
" [" <<
Iter->second <<
", " << L <<
"]\n";
1160 OS <<
"ExprToLoc:\n";
1161 for (
auto [
E, L] : ExprToLoc)
1162 OS <<
" [" <<
E <<
", " << L <<
"]\n";
1164 OS <<
"ExprToVal:\n";
1165 for (
auto [
E,
V] : ExprToVal)
1166 OS <<
" [" <<
E <<
", " <<
V <<
": " << *
V <<
"]\n";
1168 OS <<
"LocToVal:\n";
1169 for (
auto [L,
V] : LocToVal) {
1171 if (
auto Iter = LocToName.find(L);
Iter != LocToName.end())
1172 OS <<
" (" <<
Iter->second <<
")";
1173 OS <<
", " <<
V <<
": " << *
V <<
"]\n";
1177 if (
Func->getReturnType()->isReferenceType()) {
1178 OS <<
"ReturnLoc: " << ReturnLoc;
1179 if (
auto Iter = LocToName.find(ReturnLoc);
Iter != LocToName.end())
1180 OS <<
" (" <<
Iter->second <<
")";
1182 }
else if (
Func->getReturnType()->isRecordType() ||
1183 isa<CXXConstructorDecl>(
Func)) {
1184 OS <<
"LocForRecordReturnVal: " << LocForRecordReturnVal <<
"\n";
1185 }
else if (!
Func->getReturnType()->isVoidType()) {
1186 if (ReturnVal ==
nullptr)
1187 OS <<
"ReturnVal: nullptr\n";
1189 OS <<
"ReturnVal: " << *ReturnVal <<
"\n";
1192 if (isa<CXXMethodDecl>(
Func)) {
1193 OS <<
"ThisPointeeLoc: " << ThisPointeeLoc <<
"\n";
1203Environment::PrValueToResultObject Environment::buildResultObjectMap(
1209 PrValueToResultObject Map = buildResultObjectMap(
1210 DACtx, FuncDecl->
getBody(), ThisPointeeLoc, LocForRecordReturnVal);
1212 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1213 if (
const auto *Ctor = dyn_cast<CXXConstructorDecl>(FuncDecl))
1214 Visitor.TraverseConstructorInits(Ctor, ThisPointeeLoc);
1219Environment::PrValueToResultObject Environment::buildResultObjectMap(
1220 DataflowAnalysisContext *DACtx,
Stmt *S,
1221 RecordStorageLocation *ThisPointeeLoc,
1222 RecordStorageLocation *LocForRecordReturnVal) {
1223 PrValueToResultObject Map;
1224 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1225 Visitor.TraverseStmt(S);
1232 if (ImplicitObject ==
nullptr)
1236 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
1239 return cast_or_null<RecordStorageLocation>(
1246 if (
Base ==
nullptr)
1250 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, bool IsUnionField, bool InUnion, const Descriptor *D, unsigned FieldOffset)
Defines the clang::Expr interface and subclasses for C++ expressions.
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]).
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()
QualType getReturnType() const
ArrayRef< ParmVarDecl * > parameters() const
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.
Stmt - This represents one statement.
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 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.
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...
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).
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,...
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.