32#include "llvm/Support/Casting.h"
33#include "llvm/Support/Debug.h"
37#define DEBUG_TYPE "dataflow"
47 if (BlockIt->getSecond()->getBlockID() == CurBlockID)
49 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
60 if (LHSValue == RHSValue)
63 if (
auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
64 if (
auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
71 if (
auto *Top = llvm::dyn_cast<TopBoolValue>(&
V)) {
87 auto *B = dyn_cast_or_null<BoolValue>(Val);
92 if (&UnpackedVal == Val)
125 TransferVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env)
126 : StmtToEnv(StmtToEnv),
Env(
Env) {}
128 void VisitBinaryOperator(
const BinaryOperator *S) {
129 const Expr *LHS = S->getLHS();
130 assert(LHS !=
nullptr);
132 const Expr *RHS = S->getRHS();
133 assert(RHS !=
nullptr);
135 switch (S->getOpcode()) {
137 auto *LHSLoc =
Env.getStorageLocation(*LHS);
138 if (LHSLoc ==
nullptr)
141 auto *RHSVal =
Env.getValue(*RHS);
142 if (RHSVal ==
nullptr)
146 Env.setValue(*LHSLoc, *RHSVal);
149 Env.setStorageLocation(*S, *LHSLoc);
154 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
155 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
157 if (S->getOpcode() == BO_LAnd)
158 Env.setValue(*S,
Env.makeAnd(LHSVal, RHSVal));
160 Env.setValue(*S,
Env.makeOr(LHSVal, RHSVal));
166 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
167 :
Env.makeNot(LHSEqRHSValue));
179 void VisitDeclRefExpr(
const DeclRefExpr *S) {
180 const ValueDecl *VD = S->getDecl();
181 assert(VD !=
nullptr);
195 auto *DeclLoc =
Env.getStorageLocation(*VD);
196 if (DeclLoc ==
nullptr)
199 Env.setStorageLocation(*S, *DeclLoc);
202 void VisitDeclStmt(
const DeclStmt *S) {
205 const auto &D = *cast<VarDecl>(S->getSingleDecl());
210 void ProcessVarDecl(
const VarDecl &D) {
212 if (D.hasGlobalStorage())
218 if (D.getType()->isReferenceType() &&
Env.getStorageLocation(D) !=
nullptr)
221 assert(
Env.getStorageLocation(D) ==
nullptr);
223 Env.setStorageLocation(D,
Env.createObject(D));
228 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
234 for (
const auto *B : Decomp->bindings()) {
235 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
236 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
242 VisitDeclRefExpr(DE);
245 if (
auto *Loc =
Env.getStorageLocation(*ME))
246 Env.setStorageLocation(*B, *Loc);
247 }
else if (
auto *VD = B->getHoldingVar()) {
255 auto *VDLoc =
Env.getStorageLocation(*VD);
256 assert(VDLoc !=
nullptr);
257 Env.setStorageLocation(*B, *VDLoc);
263 void VisitImplicitCastExpr(
const ImplicitCastExpr *S) {
264 const Expr *SubExpr = S->getSubExpr();
265 assert(SubExpr !=
nullptr);
267 switch (S->getCastKind()) {
268 case CK_IntegralToBoolean: {
272 if (
auto *SubExprVal =
273 dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr)))
274 Env.setValue(*S, *SubExprVal);
278 Env.setValue(*S,
Env.makeAtomicBoolValue());
282 case CK_LValueToRValue: {
286 if (SubExprVal ==
nullptr)
289 Env.setValue(*S, *SubExprVal);
293 case CK_IntegralCast:
299 case CK_UncheckedDerivedToBase:
300 case CK_ConstructorConversion:
301 case CK_UserDefinedConversion:
311 case CK_NullToPointer: {
312 auto &NullPointerVal =
313 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
314 Env.setValue(*S, NullPointerVal);
317 case CK_NullToMemberPointer:
321 case CK_FunctionToPointerDecay: {
322 StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr);
323 if (PointeeLoc ==
nullptr)
326 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
329 case CK_BuiltinFnToFnPtr:
340 void VisitUnaryOperator(
const UnaryOperator *S) {
341 const Expr *SubExpr = S->getSubExpr();
342 assert(SubExpr !=
nullptr);
344 switch (S->getOpcode()) {
346 const auto *SubExprVal =
Env.get<PointerValue>(*SubExpr);
347 if (SubExprVal ==
nullptr)
350 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
355 if (S->getType()->isMemberPointerType())
358 if (StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr))
359 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
363 auto *SubExprVal = dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr));
364 if (SubExprVal ==
nullptr)
367 Env.setValue(*S,
Env.makeNot(*SubExprVal));
375 void VisitCXXThisExpr(
const CXXThisExpr *S) {
376 auto *ThisPointeeLoc =
Env.getThisPointeeStorageLocation();
377 if (ThisPointeeLoc ==
nullptr)
382 Env.setValue(*S,
Env.create<PointerValue>(*ThisPointeeLoc));
385 void VisitCXXNewExpr(
const CXXNewExpr *S) {
386 if (
Value *Val =
Env.createValue(S->getType()))
387 Env.setValue(*S, *Val);
390 void VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
397 void VisitReturnStmt(
const ReturnStmt *S) {
398 if (!
Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
401 auto *
Ret = S->getRetValue();
405 if (
Ret->isPRValue()) {
406 auto *Val =
Env.getValue(*Ret);
411 Env.setReturnValue(Val);
413 auto *Loc =
Env.getStorageLocation(*Ret);
418 Env.setReturnStorageLocation(Loc);
422 void VisitMemberExpr(
const MemberExpr *S) {
423 ValueDecl *
Member = S->getMemberDecl();
424 assert(
Member !=
nullptr);
427 if (
Member->isFunctionOrFunctionTemplate())
431 if (isa<EnumConstantDecl>(
Member))
434 if (
auto *D = dyn_cast<VarDecl>(
Member)) {
435 if (D->hasGlobalStorage()) {
436 auto *VarDeclLoc =
Env.getStorageLocation(*D);
437 if (VarDeclLoc ==
nullptr)
440 Env.setStorageLocation(*S, *VarDeclLoc);
446 if (BaseLoc ==
nullptr)
449 auto *MemberLoc = BaseLoc->getChild(*
Member);
450 if (MemberLoc ==
nullptr)
452 Env.setStorageLocation(*S, *MemberLoc);
455 void VisitCXXDefaultArgExpr(
const CXXDefaultArgExpr *S) {
456 const Expr *ArgExpr = S->getExpr();
457 assert(ArgExpr !=
nullptr);
463 if (S->isPRValue() && S->getType()->isRecordType()) {
464 if (
Env.getValue(*S) ==
nullptr) {
465 auto &Loc =
Env.getResultObjectLocation(*S);
466 Env.initializeFieldsWithValues(Loc);
472 void VisitCXXDefaultInitExpr(
const CXXDefaultInitExpr *S) {
473 const Expr *InitExpr = S->getExpr();
474 assert(InitExpr !=
nullptr);
479 if (S->getType()->isRecordType() && S->isPRValue())
485 void VisitCXXConstructExpr(
const CXXConstructExpr *S) {
486 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
487 assert(ConstructorDecl !=
nullptr);
492 if (!S->getType()->isRecordType()) {
493 transferInlineCall(S, ConstructorDecl);
497 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
500 if (ConstructorDecl->isCopyOrMoveConstructor()) {
503 assert(S->getNumArgs() != 0);
505 const Expr *Arg = S->getArg(0);
506 assert(Arg !=
nullptr);
508 auto *ArgLoc =
Env.get<RecordStorageLocation>(*Arg);
509 if (ArgLoc ==
nullptr)
519 Env.initializeFieldsWithValues(Loc, S->getType());
521 transferInlineCall(S, ConstructorDecl);
524 void VisitCXXOperatorCallExpr(
const CXXOperatorCallExpr *S) {
525 if (S->getOperator() == OO_Equal) {
526 assert(S->getNumArgs() == 2);
528 const Expr *Arg0 = S->getArg(0);
529 assert(Arg0 !=
nullptr);
531 const Expr *Arg1 = S->getArg(1);
532 assert(Arg1 !=
nullptr);
536 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
539 if (!Method->isCopyAssignmentOperator() &&
540 !Method->isMoveAssignmentOperator())
543 RecordStorageLocation *LocSrc =
nullptr;
544 if (Arg1->isPRValue()) {
545 if (
auto *Val =
Env.get<RecordValue>(*Arg1))
546 LocSrc = &Val->getLoc();
548 LocSrc =
Env.get<RecordStorageLocation>(*Arg1);
550 auto *LocDst =
Env.get<RecordStorageLocation>(*Arg0);
552 if (LocSrc ==
nullptr || LocDst ==
nullptr)
559 if (S->isGLValue()) {
560 Env.setStorageLocation(*S, *LocDst);
561 }
else if (S->getType()->isRecordType()) {
574 void VisitCXXRewrittenBinaryOperator(
const CXXRewrittenBinaryOperator *RBO) {
578 void VisitCXXFunctionalCastExpr(
const CXXFunctionalCastExpr *S) {
579 if (S->getCastKind() == CK_ConstructorConversion) {
580 const Expr *SubExpr = S->getSubExpr();
581 assert(SubExpr !=
nullptr);
587 void VisitCallExpr(
const CallExpr *S) {
591 if (S->isCallToStdMove()) {
592 assert(S->getNumArgs() == 1);
594 const Expr *Arg = S->getArg(0);
595 assert(Arg !=
nullptr);
597 auto *ArgLoc =
Env.getStorageLocation(*Arg);
598 if (ArgLoc ==
nullptr)
601 Env.setStorageLocation(*S, *ArgLoc);
602 }
else if (S->getDirectCallee() !=
nullptr &&
603 S->getDirectCallee()->getBuiltinID() ==
604 Builtin::BI__builtin_expect) {
605 assert(S->getNumArgs() > 0);
606 assert(S->getArg(0) !=
nullptr);
607 auto *ArgVal =
Env.getValue(*S->getArg(0));
608 if (ArgVal ==
nullptr)
610 Env.setValue(*S, *ArgVal);
611 }
else if (
const FunctionDecl *F = S->getDirectCallee()) {
612 transferInlineCall(S, F);
616 if (S->getType()->isRecordType() && S->isPRValue())
617 if (
Env.getValue(*S) ==
nullptr) {
618 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
619 Env.initializeFieldsWithValues(Loc);
625 void VisitMaterializeTemporaryExpr(
const MaterializeTemporaryExpr *S) {
626 const Expr *SubExpr = S->getSubExpr();
627 assert(SubExpr !=
nullptr);
629 Value *SubExprVal =
Env.getValue(*SubExpr);
630 if (SubExprVal ==
nullptr)
633 if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) {
634 Env.setStorageLocation(*S, RecordVal->getLoc());
638 StorageLocation &Loc =
Env.createStorageLocation(*S);
639 Env.setValue(Loc, *SubExprVal);
640 Env.setStorageLocation(*S, Loc);
643 void VisitCXXBindTemporaryExpr(
const CXXBindTemporaryExpr *S) {
644 const Expr *SubExpr = S->getSubExpr();
645 assert(SubExpr !=
nullptr);
650 void VisitCXXStaticCastExpr(
const CXXStaticCastExpr *S) {
651 if (S->getCastKind() == CK_NoOp) {
652 const Expr *SubExpr = S->getSubExpr();
653 assert(SubExpr !=
nullptr);
659 void VisitConditionalOperator(
const ConditionalOperator *S) {
668 Env.setStorageLocation(*S,
Env.createObject(S->getType()));
669 else if (!S->getType()->isRecordType()) {
670 if (
Value *Val =
Env.createValue(S->getType()))
671 Env.setValue(*S, *Val);
675 void VisitInitListExpr(
const InitListExpr *S) {
676 QualType
Type = S->getType();
678 if (!
Type->isRecordType()) {
681 if (!
Type->isArrayType() && S->getNumInits() == 1)
688 if (S->isSemanticForm() && S->isTransparent()) {
693 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
701 RecordInitListHelper InitListHelper(S);
703 for (
auto [Field,
Init] : InitListHelper.field_inits()) {
704 if (
Field->getType()->isRecordType())
706 if (
Field->getType()->isReferenceType()) {
707 assert(
Field->getType().getCanonicalType()->getPointeeType() ==
708 Init->getType().getCanonicalType());
709 Loc.setChild(*Field, &
Env.createObject(
Field->getType(),
Init));
712 assert(
Field->getType().getCanonicalType().getUnqualifiedType() ==
713 Init->getType().getCanonicalType().getUnqualifiedType());
714 StorageLocation *FieldLoc = Loc.getChild(*Field);
716 assert(FieldLoc !=
nullptr);
718 if (Val ==
nullptr && isa<ImplicitValueInitExpr>(
Init) &&
719 Init->getType()->isPointerType())
721 &
Env.getOrCreateNullPointerValue(
Init->getType()->getPointeeType());
723 Val =
Env.createValue(
Field->getType());
725 Env.setValue(*FieldLoc, *Val);
728 for (
const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) {
729 QualType FieldType = FieldLoc->getType();
730 if (FieldType->isRecordType()) {
731 Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc));
733 if (
Value *Val =
Env.createValue(FieldType))
734 Env.setValue(*FieldLoc, *Val);
741 void VisitCXXBoolLiteralExpr(
const CXXBoolLiteralExpr *S) {
742 Env.setValue(*S,
Env.getBoolLiteralValue(S->getValue()));
745 void VisitIntegerLiteral(
const IntegerLiteral *S) {
746 Env.setValue(*S,
Env.getIntLiteralValue(S->getValue()));
749 void VisitParenExpr(
const ParenExpr *S) {
753 auto *SubExpr = S->getSubExpr();
754 assert(SubExpr !=
nullptr);
758 void VisitExprWithCleanups(
const ExprWithCleanups *S) {
762 auto *SubExpr = S->getSubExpr();
763 assert(SubExpr !=
nullptr);
769 BoolValue &getLogicOperatorSubExprValue(
const Expr &SubExpr) {
773 if (
const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
775 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
783 if (
Env.getValue(SubExpr) ==
nullptr)
785 if (
auto *Val = dyn_cast_or_null<BoolValue>(
Env.getValue(SubExpr)))
790 return Env.makeAtomicBoolValue();
795 template <
typename E>
796 void transferInlineCall(
const E *S,
const FunctionDecl *F) {
797 const auto &Options =
Env.getDataflowAnalysisContext().getOptions();
798 if (!(Options.ContextSensitiveOpts &&
799 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
802 const AdornedCFG *ACFG =
Env.getDataflowAnalysisContext().getAdornedCFG(F);
810 auto ExitBlock = ACFG->getCFG().getExit().getBlockID();
812 auto CalleeEnv =
Env.pushCall(S);
817 auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(),
818 DataflowAnalysisOptions{Options});
820 auto BlockToOutputState =
822 assert(BlockToOutputState);
823 assert(ExitBlock < BlockToOutputState->size());
825 auto &ExitState = (*BlockToOutputState)[ExitBlock];
828 Env.popCall(S, ExitState->Env);
831 const StmtToEnvMap &StmtToEnv;
838 TransferVisitor(StmtToEnv,
Env).Visit(&S);
Defines enum values for all the target-independent builtin functions.
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
Defines the clang::Expr interface and subclasses for C++ expressions.
Defines an enumeration for C++ overloaded operators.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
This represents one expression.
Stmt - This represents one statement.
bool isBlockReachable(const CFGBlock &B) const
Returns whether B is reachable from the entry block.
const llvm::DenseMap< const Stmt *, const CFGBlock * > & getStmtToBlock() const
Returns a mapping from statements to basic blocks that contain them.
BoolValue & makeBoolValue(const Formula &)
Creates a BoolValue wrapping a particular formula.
Holds the state of the program (store and heap) at a given program point.
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
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 ...
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...
BoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value
DataflowAnalysisContext & getDataflowAnalysisContext() const
Returns the DataflowAnalysisContext used by the environment.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
Maps statements to the environments of basic blocks that contain them.
const Environment * getEnvironment(const Stmt &S) const
Returns the environment of the basic block that contains S.
Base class for all values computed by abstract interpretation.
static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, Environment &Env)
static void propagateStorageLocation(const Expr &From, const Expr &To, Environment &Env)
llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr, std::int32_t MaxBlockVisits=20 '000)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
static void propagateValue(const Expr &From, const Expr &To, Environment &Env)
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
static Value * maybeUnpackLValueExpr(const Expr &E, Environment &Env)
void copyRecord(RecordStorageLocation &Src, RecordStorageLocation &Dst, Environment &Env)
Copies a record (struct, class, or union) from Src to Dst.
static BoolValue & unpackValue(BoolValue &V, Environment &Env)
static BoolValue & evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, Environment &Env)
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
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...
RecordValue & refreshRecordValue(RecordStorageLocation &Loc, Environment &Env)
Associates a new RecordValue with Loc and returns the new value.
bool Ret(InterpState &S, CodePtr &PC, APValue &Result)
The JSON file list parser is used to communicate input to InstallAPI.
Environment Env
Model of the state of the program (store and heap).