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 (
auto *PrevBool = dyn_cast<BoolValue>(&Prev)) {
161 if (isa<TopBoolValue>(Prev))
169 auto &CurBool = cast<BoolValue>(Current);
170 bool TruePrev = PrevEnv.
proves(PrevBool->formula());
171 bool TrueCur = CurrentEnv.
proves(CurBool.formula());
172 if (TruePrev && TrueCur)
174 if (!TruePrev && !TrueCur &&
185 if (
auto Result = Model.
widen(
Type, Prev, PrevEnv, Current, CurrentEnv))
195template <
typename Key>
197 const llvm::MapVector<Key, Value *> &Map2,
200 for (
auto &Entry : Map1) {
202 assert(K !=
nullptr);
204 Value *Val = Entry.second;
205 assert(Val !=
nullptr);
207 auto It = Map2.find(K);
208 if (It == Map2.end())
210 assert(It->second !=
nullptr);
222static llvm::MapVector<const StorageLocation *, Value *>
223joinLocToVal(
const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
224 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
227 llvm::MapVector<const StorageLocation *, Value *>
Result;
228 for (
auto &Entry : LocToVal) {
230 assert(Loc !=
nullptr);
232 Value *Val = Entry.second;
233 assert(Val !=
nullptr);
235 auto It = LocToVal2.find(Loc);
236 if (It == LocToVal2.end())
238 assert(It->second !=
nullptr);
241 Loc->
getType(), Val, Env1, It->second, Env2, JoinedEnv, Model)) {
242 Result.insert({Loc, JoinedVal});
251template <
typename Key>
252llvm::MapVector<Key, Value *>
254 const llvm::MapVector<Key, Value *> &PrevMap,
257 llvm::MapVector<Key, Value *> WidenedMap;
258 for (
auto &Entry : CurMap) {
260 assert(K !=
nullptr);
262 Value *Val = Entry.second;
263 assert(Val !=
nullptr);
265 auto PrevIt = PrevMap.find(K);
266 if (PrevIt == PrevMap.end())
268 assert(PrevIt->second !=
nullptr);
271 WidenedMap.insert({K, Val});
276 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);
277 WidenedMap.insert({K, WidenedVal});
297 explicit ResultObjectVisitor(
298 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,
299 RecordStorageLocation *LocForRecordReturnVal,
300 DataflowAnalysisContext &DACtx)
301 : ResultObjectMap(ResultObjectMap),
302 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}
304 bool shouldVisitImplicitCode() {
return true; }
306 bool shouldVisitLambdaBody()
const {
return false; }
312 void TraverseConstructorInits(
const CXXConstructorDecl *Ctor,
313 RecordStorageLocation *ThisPointeeLoc) {
314 assert(ThisPointeeLoc !=
nullptr);
315 for (
const CXXCtorInitializer *
Init : Ctor->inits()) {
316 Expr *InitExpr =
Init->getInit();
317 if (FieldDecl *Field =
Init->getMember();
318 Field !=
nullptr &&
Field->getType()->isRecordType()) {
319 PropagateResultObject(InitExpr, cast<RecordStorageLocation>(
320 ThisPointeeLoc->getChild(*Field)));
321 }
else if (
Init->getBaseClass()) {
322 PropagateResultObject(InitExpr, ThisPointeeLoc);
327 TraverseStmt(InitExpr);
331 if (
auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr))
332 TraverseStmt(DefaultInit->getExpr());
336 bool TraverseBindingDecl(BindingDecl *BD) {
339 if (VarDecl *HoldingVar = BD->getHoldingVar())
340 TraverseDecl(HoldingVar);
341 return RecursiveASTVisitor<ResultObjectVisitor>::TraverseBindingDecl(BD);
344 bool VisitVarDecl(VarDecl *VD) {
345 if (VD->getType()->isRecordType() && VD->hasInit())
346 PropagateResultObject(
348 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*VD)));
352 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) {
353 if (MTE->getType()->isRecordType())
354 PropagateResultObject(
356 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*MTE)));
360 bool VisitReturnStmt(ReturnStmt *Return) {
361 Expr *
RetValue = Return->getRetValue();
364 PropagateResultObject(
RetValue, LocForRecordReturnVal);
368 bool VisitExpr(Expr *E) {
374 if (E->isPRValue() && E->getType()->isRecordType() &&
375 !ResultObjectMap.contains(E))
376 PropagateResultObject(
377 E, &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*E)));
382 PropagateResultObjectToRecordInitList(
const RecordInitListHelper &InitList,
383 RecordStorageLocation *Loc) {
384 for (
auto [
Base,
Init] : InitList.base_inits()) {
385 assert(
Base->getType().getCanonicalType() ==
386 Init->getType().getCanonicalType());
391 PropagateResultObject(
Init, Loc);
394 for (
auto [Field,
Init] : InitList.field_inits()) {
397 if (
Field->getType()->isRecordType())
398 PropagateResultObject(
399 Init, cast<RecordStorageLocation>(Loc->getChild(*Field)));
406 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) {
407 if (!E->isPRValue() || !E->getType()->isRecordType()) {
414 ResultObjectMap[E] = Loc;
419 if (isa<CXXConstructExpr>(E) || isa<CallExpr>(E) || isa<LambdaExpr>(E) ||
420 isa<CXXDefaultArgExpr>(E) || isa<CXXDefaultInitExpr>(E) ||
421 isa<CXXStdInitializerListExpr>(E) ||
425 isa<BuiltinBitCastExpr>(E)) {
428 if (
auto *Op = dyn_cast<BinaryOperator>(E);
429 Op && Op->getOpcode() == BO_Cmp) {
434 if (
auto *InitList = dyn_cast<InitListExpr>(E)) {
435 if (!InitList->isSemanticForm())
437 if (InitList->isTransparent()) {
438 PropagateResultObject(InitList->getInit(0), Loc);
442 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList),
447 if (
auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(E)) {
448 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList),
453 if (
auto *Op = dyn_cast<BinaryOperator>(E); Op && Op->isCommaOp()) {
454 PropagateResultObject(Op->getRHS(), Loc);
458 if (
auto *Cond = dyn_cast<AbstractConditionalOperator>(E)) {
459 PropagateResultObject(Cond->getTrueExpr(), Loc);
460 PropagateResultObject(Cond->getFalseExpr(), Loc);
464 if (
auto *SE = dyn_cast<StmtExpr>(E)) {
465 PropagateResultObject(cast<Expr>(SE->getSubStmt()->body_back()), Loc);
471 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end());
473 if (Children.size() != 1)
476 assert(Children.size() == 1);
477 for (Stmt *S : Children)
478 PropagateResultObject(cast<Expr>(S), Loc);
482 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
483 RecordStorageLocation *LocForRecordReturnVal;
484 DataflowAnalysisContext &DACtx;
491 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
496 CallStack.push_back(&DeclCtx);
501 if (DeclCtx ==
nullptr)
504 const auto *FuncDecl = dyn_cast<FunctionDecl>(DeclCtx);
505 if (FuncDecl ==
nullptr)
508 assert(FuncDecl->doesThisDeclarationHaveABody());
510 initFieldsGlobalsAndFuncs(FuncDecl);
512 for (
const auto *ParamDecl : FuncDecl->parameters()) {
513 assert(ParamDecl !=
nullptr);
517 if (FuncDecl->getReturnType()->isRecordType())
518 LocForRecordReturnVal = &cast<RecordStorageLocation>(
521 if (
const auto *MethodDecl = dyn_cast<CXXMethodDecl>(DeclCtx)) {
522 auto *
Parent = MethodDecl->getParent();
523 assert(
Parent !=
nullptr);
527 if (
Capture.capturesVariable()) {
531 }
else if (
Capture.capturesThis()) {
532 const auto *SurroundingMethodDecl =
535 SurroundingMethodDecl->getFunctionObjectParameterType();
537 cast<RecordStorageLocation>(
createObject(ThisPointeeType)));
540 }
else if (MethodDecl->isImplicitObjectMemberFunction()) {
541 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
548 if (!isa<CXXConstructorDecl>(MethodDecl))
555 ResultObjectMap = std::make_shared<PrValueToResultObject>(
557 LocForRecordReturnVal));
562void Environment::initFieldsGlobalsAndFuncs(
const FunctionDecl *FuncDecl) {
569 DACtx->addModeledFields(Referenced.
Fields);
599 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
605 if (
const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(
Call)) {
606 if (
const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
607 if (!isa<CXXThisExpr>(Arg))
615 if (
Call->getType()->isRecordType() &&
Call->isPRValue())
616 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
618 Env.pushCallInternal(
Call->getDirectCallee(),
627 Env.ThisPointeeLoc = &
Env.getResultObjectLocation(*
Call);
628 Env.LocForRecordReturnVal = &
Env.getResultObjectLocation(*
Call);
630 Env.pushCallInternal(
Call->getConstructor(),
636void Environment::pushCallInternal(
const FunctionDecl *FuncDecl,
644 CallStack.push_back(FuncDecl);
646 initFieldsGlobalsAndFuncs(FuncDecl);
652 for (
unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
653 assert(ParamIt != FuncDecl->
param_end());
654 const VarDecl *Param = *ParamIt;
658 ResultObjectMap = std::make_shared<PrValueToResultObject>(
660 LocForRecordReturnVal));
671 this->LocToVal = std::move(CalleeEnv.LocToVal);
672 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
674 if (
Call->isGLValue()) {
675 if (CalleeEnv.ReturnLoc !=
nullptr)
677 }
else if (!
Call->getType()->isVoidType()) {
678 if (CalleeEnv.ReturnVal !=
nullptr)
686 this->LocToVal = std::move(CalleeEnv.LocToVal);
687 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
692 assert(DACtx ==
Other.DACtx);
694 if (ReturnVal !=
Other.ReturnVal)
697 if (ReturnLoc !=
Other.ReturnLoc)
700 if (LocForRecordReturnVal !=
Other.LocForRecordReturnVal)
703 if (ThisPointeeLoc !=
Other.ThisPointeeLoc)
706 if (DeclToLoc !=
Other.DeclToLoc)
709 if (ExprToLoc !=
Other.ExprToLoc)
723 assert(DACtx == PrevEnv.DACtx);
724 assert(ReturnVal == PrevEnv.ReturnVal);
725 assert(ReturnLoc == PrevEnv.ReturnLoc);
726 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);
727 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
728 assert(CallStack == PrevEnv.CallStack);
729 assert(ResultObjectMap == PrevEnv.ResultObjectMap);
739 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
740 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
741 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
748 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
749 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
750 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
751 LocToVal.size() != PrevEnv.LocToVal.size())
760 assert(EnvA.DACtx == EnvB.DACtx);
761 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);
762 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
763 assert(EnvA.CallStack == EnvB.CallStack);
764 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);
768 JoinedEnv.CallStack = EnvA.CallStack;
769 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;
770 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;
771 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
773 if (EnvA.CallStack.empty()) {
774 JoinedEnv.ReturnVal =
nullptr;
778 auto *
Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
779 assert(
Func !=
nullptr);
780 JoinedEnv.ReturnVal =
781 joinValues(
Func->getReturnType(), EnvA.ReturnVal, EnvA, EnvB.ReturnVal,
782 EnvB, JoinedEnv, Model);
785 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
786 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
788 JoinedEnv.ReturnLoc =
nullptr;
795 EnvA.FlowConditionToken, EnvB.FlowConditionToken);
798 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model);
801 JoinedEnv.ExprToVal =
joinExprMaps(EnvA.ExprToVal, EnvB.ExprToVal);
802 JoinedEnv.ExprToLoc =
joinExprMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
812 if (Val1 ==
nullptr || Val2 ==
nullptr)
845 assert(!DeclToLoc.contains(&D));
852 DeclToLoc[&D] = &Loc;
856 auto It = DeclToLoc.find(&D);
857 if (It == DeclToLoc.end())
874 assert(!ExprToLoc.contains(&CanonE));
875 ExprToLoc[&CanonE] = &Loc;
883 return It == ExprToLoc.end() ? nullptr : &*It->second;
891 assert(ResultObjectMap !=
nullptr);
893 assert(Loc !=
nullptr);
897 return cast<RecordStorageLocation>(
909 int CreatedValuesCount = 0;
912 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
919 assert(!isa<RecordStorageLocation>(Loc));
920 LocToVal[&Loc] = &Val;
929 ExprToVal[&CanonE] = &Val;
934 assert(!isa<RecordStorageLocation>(Loc));
935 return LocToVal.lookup(&Loc);
951 return It == ExprToVal.end() ? nullptr : It->second;
955 if (It == ExprToLoc.end())
962 int CreatedValuesCount = 0;
966 llvm::errs() <<
"Attempting to initialize a huge value of type: " <<
Type
972Value *Environment::createValueUnlessSelfReferential(
974 int &CreatedValuesCount) {
975 assert(!
Type.isNull());
985 CreatedValuesCount++;
993 CreatedValuesCount++;
997 if (
Type->isPointerType()) {
998 CreatedValuesCount++;
999 QualType PointeeType =
Type->getPointeeType();
1000 StorageLocation &PointeeLoc =
1001 createLocAndMaybeValue(PointeeType,
Visited, Depth, CreatedValuesCount);
1010Environment::createLocAndMaybeValue(QualType Ty,
1012 int Depth,
int &CreatedValuesCount) {
1013 if (!
Visited.insert(Ty.getCanonicalType()).second)
1015 auto EraseVisited = llvm::make_scope_exit(
1018 Ty = Ty.getNonReferenceType();
1020 if (Ty->isRecordType()) {
1028 if (
Value *Val = createValueUnlessSelfReferential(Ty,
Visited, Depth,
1029 CreatedValuesCount))
1039 int &CreatedValuesCount) {
1040 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
1041 if (FieldType->isRecordType()) {
1042 auto &FieldRecordLoc = cast<RecordStorageLocation>(FieldLoc);
1044 Visited, Depth + 1, CreatedValuesCount);
1048 if (!
Visited.insert(FieldType.getCanonicalType()).second)
1050 if (
Value *Val = createValueUnlessSelfReferential(
1051 FieldType,
Visited, Depth + 1, CreatedValuesCount))
1053 Visited.erase(FieldType.getCanonicalType());
1058 assert(Field !=
nullptr);
1059 QualType FieldType =
Field->getType();
1061 if (FieldType->isReferenceType()) {
1062 Loc.setChild(*Field,
1063 &createLocAndMaybeValue(FieldType,
Visited, Depth + 1,
1064 CreatedValuesCount));
1066 StorageLocation *FieldLoc = Loc.getChild(*Field);
1067 assert(FieldLoc !=
nullptr);
1068 initField(FieldType, *FieldLoc);
1074 assert(!FieldType->isReferenceType());
1075 initField(FieldType, Loc.getSyntheticField(FieldName));
1079StorageLocation &Environment::createObjectInternal(
const ValueDecl *D,
1081 const Expr *InitExpr) {
1082 if (Ty->isReferenceType()) {
1088 return *InitExprLoc;
1095 return createObjectInternal(D, Ty.getNonReferenceType(),
nullptr);
1098 StorageLocation &Loc =
1101 if (Ty->isRecordType()) {
1102 auto &
RecordLoc = cast<RecordStorageLocation>(Loc);
1106 Value *Val =
nullptr;
1144 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1145 if (LocForRecordReturnVal !=
nullptr)
1146 LocToName[LocForRecordReturnVal] =
"(returned record)";
1147 if (ThisPointeeLoc !=
nullptr)
1148 LocToName[ThisPointeeLoc] =
"this";
1150 OS <<
"DeclToLoc:\n";
1151 for (
auto [D, L] : DeclToLoc) {
1152 auto Iter = LocToName.insert({L, D->getNameAsString()}).first;
1153 OS <<
" [" <<
Iter->second <<
", " << L <<
"]\n";
1155 OS <<
"ExprToLoc:\n";
1156 for (
auto [E, L] : ExprToLoc)
1157 OS <<
" [" << E <<
", " << L <<
"]\n";
1159 OS <<
"ExprToVal:\n";
1160 for (
auto [E,
V] : ExprToVal)
1161 OS <<
" [" << E <<
", " <<
V <<
": " << *
V <<
"]\n";
1163 OS <<
"LocToVal:\n";
1164 for (
auto [L,
V] : LocToVal) {
1166 if (
auto Iter = LocToName.find(L);
Iter != LocToName.end())
1167 OS <<
" (" <<
Iter->second <<
")";
1168 OS <<
", " <<
V <<
": " << *
V <<
"]\n";
1172 if (
Func->getReturnType()->isReferenceType()) {
1173 OS <<
"ReturnLoc: " << ReturnLoc;
1174 if (
auto Iter = LocToName.find(ReturnLoc);
Iter != LocToName.end())
1175 OS <<
" (" <<
Iter->second <<
")";
1177 }
else if (
Func->getReturnType()->isRecordType() ||
1178 isa<CXXConstructorDecl>(
Func)) {
1179 OS <<
"LocForRecordReturnVal: " << LocForRecordReturnVal <<
"\n";
1180 }
else if (!
Func->getReturnType()->isVoidType()) {
1181 if (ReturnVal ==
nullptr)
1182 OS <<
"ReturnVal: nullptr\n";
1184 OS <<
"ReturnVal: " << *ReturnVal <<
"\n";
1187 if (isa<CXXMethodDecl>(
Func)) {
1188 OS <<
"ThisPointeeLoc: " << ThisPointeeLoc <<
"\n";
1198Environment::PrValueToResultObject Environment::buildResultObjectMap(
1204 PrValueToResultObject Map;
1206 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1207 if (
const auto *Ctor = dyn_cast<CXXConstructorDecl>(FuncDecl))
1208 Visitor.TraverseConstructorInits(Ctor, ThisPointeeLoc);
1209 Visitor.TraverseStmt(FuncDecl->
getBody());
1217 if (ImplicitObject ==
nullptr)
1221 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
1224 return cast_or_null<RecordStorageLocation>(
1231 if (
Base ==
nullptr)
1235 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
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...
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.