32#include "llvm/Support/Casting.h"
33#include "llvm/Support/Debug.h"
37#define DEBUG_TYPE "dataflow"
51 if (BlockIt->getSecond()->getBlockID() == CurBlockID)
53 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
64 if (LHSValue == RHSValue)
67 if (
auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
68 if (
auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
75 if (
auto *Top = llvm::dyn_cast<TopBoolValue>(&
V)) {
91 auto *B = dyn_cast_or_null<BoolValue>(Val);
96 if (&UnpackedVal == Val)
131 TransferVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env,
132 Environment::ValueModel &Model)
133 : StmtToEnv(StmtToEnv),
Env(
Env), Model(Model) {}
135 void VisitBinaryOperator(
const BinaryOperator *S) {
136 const Expr *LHS = S->getLHS();
137 assert(LHS !=
nullptr);
139 const Expr *RHS = S->getRHS();
140 assert(RHS !=
nullptr);
142 switch (S->getOpcode()) {
144 auto *LHSLoc =
Env.getStorageLocation(*LHS);
145 if (LHSLoc ==
nullptr)
148 auto *RHSVal =
Env.getValue(*RHS);
149 if (RHSVal ==
nullptr)
153 Env.setValue(*LHSLoc, *RHSVal);
156 Env.setStorageLocation(*S, *LHSLoc);
161 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
162 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
164 if (S->getOpcode() == BO_LAnd)
165 Env.setValue(*S,
Env.makeAnd(LHSVal, RHSVal));
167 Env.setValue(*S,
Env.makeOr(LHSVal, RHSVal));
173 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
174 :
Env.makeNot(LHSEqRHSValue));
186 void VisitDeclRefExpr(
const DeclRefExpr *S) {
187 const ValueDecl *VD = S->getDecl();
188 assert(VD !=
nullptr);
202 auto *DeclLoc =
Env.getStorageLocation(*VD);
203 if (DeclLoc ==
nullptr)
206 Env.setStorageLocation(*S, *DeclLoc);
209 void VisitDeclStmt(
const DeclStmt *S) {
212 const auto &D = *cast<VarDecl>(S->getSingleDecl());
217 void ProcessVarDecl(
const VarDecl &D) {
219 if (D.hasGlobalStorage())
225 if (D.getType()->isReferenceType() &&
Env.getStorageLocation(D) !=
nullptr)
228 assert(
Env.getStorageLocation(D) ==
nullptr);
230 Env.setStorageLocation(D,
Env.createObject(D));
235 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
241 for (
const auto *B : Decomp->bindings()) {
242 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
243 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
249 VisitDeclRefExpr(DE);
252 if (
auto *Loc =
Env.getStorageLocation(*ME))
253 Env.setStorageLocation(*B, *Loc);
254 }
else if (
auto *VD = B->getHoldingVar()) {
262 auto *VDLoc =
Env.getStorageLocation(*VD);
263 assert(VDLoc !=
nullptr);
264 Env.setStorageLocation(*B, *VDLoc);
270 void VisitImplicitCastExpr(
const ImplicitCastExpr *S) {
271 const Expr *SubExpr = S->getSubExpr();
272 assert(SubExpr !=
nullptr);
274 switch (S->getCastKind()) {
275 case CK_IntegralToBoolean: {
279 if (
auto *SubExprVal =
280 dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr)))
281 Env.setValue(*S, *SubExprVal);
285 Env.setValue(*S,
Env.makeAtomicBoolValue());
289 case CK_LValueToRValue: {
293 if (SubExprVal ==
nullptr)
296 Env.setValue(*S, *SubExprVal);
300 case CK_IntegralCast:
306 case CK_UncheckedDerivedToBase:
307 case CK_ConstructorConversion:
308 case CK_UserDefinedConversion:
318 case CK_NullToPointer: {
319 auto &NullPointerVal =
320 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
321 Env.setValue(*S, NullPointerVal);
324 case CK_NullToMemberPointer:
328 case CK_FunctionToPointerDecay: {
329 StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr);
330 if (PointeeLoc ==
nullptr)
333 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
336 case CK_BuiltinFnToFnPtr:
347 void VisitUnaryOperator(
const UnaryOperator *S) {
348 const Expr *SubExpr = S->getSubExpr();
349 assert(SubExpr !=
nullptr);
351 switch (S->getOpcode()) {
353 const auto *SubExprVal =
Env.get<PointerValue>(*SubExpr);
354 if (SubExprVal ==
nullptr)
357 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
362 if (S->getType()->isMemberPointerType())
365 if (StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr))
366 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
370 auto *SubExprVal = dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr));
371 if (SubExprVal ==
nullptr)
374 Env.setValue(*S,
Env.makeNot(*SubExprVal));
382 void VisitCXXThisExpr(
const CXXThisExpr *S) {
383 auto *ThisPointeeLoc =
Env.getThisPointeeStorageLocation();
384 if (ThisPointeeLoc ==
nullptr)
389 Env.setValue(*S,
Env.create<PointerValue>(*ThisPointeeLoc));
392 void VisitCXXNewExpr(
const CXXNewExpr *S) {
393 if (
Value *Val =
Env.createValue(S->getType()))
394 Env.setValue(*S, *Val);
397 void VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
404 void VisitReturnStmt(
const ReturnStmt *S) {
405 if (!
Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
408 auto *
Ret = S->getRetValue();
412 if (
Ret->isPRValue()) {
413 if (
Ret->getType()->isRecordType())
416 auto *Val =
Env.getValue(*Ret);
421 Env.setReturnValue(Val);
423 auto *Loc =
Env.getStorageLocation(*Ret);
428 Env.setReturnStorageLocation(Loc);
432 void VisitMemberExpr(
const MemberExpr *S) {
433 ValueDecl *
Member = S->getMemberDecl();
434 assert(
Member !=
nullptr);
437 if (
Member->isFunctionOrFunctionTemplate())
441 if (isa<EnumConstantDecl>(
Member))
444 if (
auto *D = dyn_cast<VarDecl>(
Member)) {
445 if (D->hasGlobalStorage()) {
446 auto *VarDeclLoc =
Env.getStorageLocation(*D);
447 if (VarDeclLoc ==
nullptr)
450 Env.setStorageLocation(*S, *VarDeclLoc);
456 if (BaseLoc ==
nullptr)
459 auto *MemberLoc = BaseLoc->getChild(*
Member);
460 if (MemberLoc ==
nullptr)
462 Env.setStorageLocation(*S, *MemberLoc);
465 void VisitCXXDefaultArgExpr(
const CXXDefaultArgExpr *S) {
466 const Expr *ArgExpr = S->getExpr();
467 assert(ArgExpr !=
nullptr);
470 if (S->isPRValue() && S->getType()->isRecordType()) {
471 auto &Loc =
Env.getResultObjectLocation(*S);
472 Env.initializeFieldsWithValues(Loc);
476 void VisitCXXDefaultInitExpr(
const CXXDefaultInitExpr *S) {
477 const Expr *InitExpr = S->getExpr();
478 assert(InitExpr !=
nullptr);
483 if (S->getType()->isRecordType() && S->isPRValue())
489 void VisitCXXConstructExpr(
const CXXConstructExpr *S) {
490 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
491 assert(ConstructorDecl !=
nullptr);
496 if (!S->getType()->isRecordType()) {
497 transferInlineCall(S, ConstructorDecl);
501 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
503 if (ConstructorDecl->isCopyOrMoveConstructor()) {
506 assert(S->getNumArgs() != 0);
508 const Expr *Arg = S->getArg(0);
509 assert(Arg !=
nullptr);
511 auto *ArgLoc =
Env.get<RecordStorageLocation>(*Arg);
512 if (ArgLoc ==
nullptr)
522 Env.initializeFieldsWithValues(Loc, S->getType());
524 transferInlineCall(S, ConstructorDecl);
527 void VisitCXXOperatorCallExpr(
const CXXOperatorCallExpr *S) {
528 if (S->getOperator() == OO_Equal) {
529 assert(S->getNumArgs() == 2);
531 const Expr *Arg0 = S->getArg(0);
532 assert(Arg0 !=
nullptr);
534 const Expr *Arg1 = S->getArg(1);
535 assert(Arg1 !=
nullptr);
539 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
542 if (!Method->isCopyAssignmentOperator() &&
543 !Method->isMoveAssignmentOperator())
546 RecordStorageLocation *LocSrc =
nullptr;
547 if (Arg1->isPRValue()) {
548 LocSrc = &
Env.getResultObjectLocation(*Arg1);
550 LocSrc =
Env.get<RecordStorageLocation>(*Arg1);
552 auto *LocDst =
Env.get<RecordStorageLocation>(*Arg0);
554 if (LocSrc ==
nullptr || LocDst ==
nullptr)
561 if (S->isGLValue()) {
562 Env.setStorageLocation(*S, *LocDst);
563 }
else if (S->getType()->isRecordType()) {
576 void VisitCXXRewrittenBinaryOperator(
const CXXRewrittenBinaryOperator *RBO) {
580 void VisitCallExpr(
const CallExpr *S) {
584 if (S->isCallToStdMove()) {
585 assert(S->getNumArgs() == 1);
587 const Expr *Arg = S->getArg(0);
588 assert(Arg !=
nullptr);
590 auto *ArgLoc =
Env.getStorageLocation(*Arg);
591 if (ArgLoc ==
nullptr)
594 Env.setStorageLocation(*S, *ArgLoc);
595 }
else if (S->getDirectCallee() !=
nullptr &&
596 S->getDirectCallee()->getBuiltinID() ==
597 Builtin::BI__builtin_expect) {
598 assert(S->getNumArgs() > 0);
599 assert(S->getArg(0) !=
nullptr);
600 auto *ArgVal =
Env.getValue(*S->getArg(0));
601 if (ArgVal ==
nullptr)
603 Env.setValue(*S, *ArgVal);
604 }
else if (
const FunctionDecl *F = S->getDirectCallee()) {
605 transferInlineCall(S, F);
609 if (S->getType()->isRecordType() && S->isPRValue()) {
610 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
611 Env.initializeFieldsWithValues(Loc);
616 void VisitMaterializeTemporaryExpr(
const MaterializeTemporaryExpr *S) {
617 const Expr *SubExpr = S->getSubExpr();
618 assert(SubExpr !=
nullptr);
620 StorageLocation &Loc =
Env.createStorageLocation(*S);
621 Env.setStorageLocation(*S, Loc);
623 if (SubExpr->getType()->isRecordType())
628 if (
Value *SubExprVal =
Env.getValue(*SubExpr))
629 Env.setValue(Loc, *SubExprVal);
632 void VisitCXXBindTemporaryExpr(
const CXXBindTemporaryExpr *S) {
633 const Expr *SubExpr = S->getSubExpr();
634 assert(SubExpr !=
nullptr);
639 void VisitCXXStaticCastExpr(
const CXXStaticCastExpr *S) {
640 if (S->getCastKind() == CK_NoOp) {
641 const Expr *SubExpr = S->getSubExpr();
642 assert(SubExpr !=
nullptr);
648 void VisitConditionalOperator(
const ConditionalOperator *S) {
649 const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr());
650 const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr());
652 if (TrueEnv ==
nullptr || FalseEnv ==
nullptr) {
660 if (S->isGLValue()) {
661 StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr());
662 StorageLocation *FalseLoc =
663 FalseEnv->getStorageLocation(*S->getFalseExpr());
664 if (TrueLoc == FalseLoc && TrueLoc !=
nullptr)
665 Env.setStorageLocation(*S, *TrueLoc);
666 }
else if (!S->getType()->isRecordType()) {
683 S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv,
684 FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, Model))
685 Env.setValue(*S, *Val);
689 void VisitInitListExpr(
const InitListExpr *S) {
690 QualType
Type = S->getType();
692 if (!
Type->isRecordType()) {
695 if (!
Type->isArrayType() && S->getNumInits() == 1)
701 if (S->isSemanticForm() && S->isTransparent())
704 RecordStorageLocation &Loc =
Env.getResultObjectLocation(*S);
711 RecordInitListHelper InitListHelper(S);
713 for (
auto [Field,
Init] : InitListHelper.field_inits()) {
714 if (
Field->getType()->isRecordType())
716 if (
Field->getType()->isReferenceType()) {
717 assert(
Field->getType().getCanonicalType()->getPointeeType() ==
718 Init->getType().getCanonicalType());
719 Loc.setChild(*Field, &
Env.createObject(
Field->getType(),
Init));
722 assert(
Field->getType().getCanonicalType().getUnqualifiedType() ==
723 Init->getType().getCanonicalType().getUnqualifiedType());
724 StorageLocation *FieldLoc = Loc.getChild(*Field);
726 assert(FieldLoc !=
nullptr);
728 if (Val ==
nullptr && isa<ImplicitValueInitExpr>(
Init) &&
729 Init->getType()->isPointerType())
731 &
Env.getOrCreateNullPointerValue(
Init->getType()->getPointeeType());
733 Val =
Env.createValue(
Field->getType());
735 Env.setValue(*FieldLoc, *Val);
738 for (
const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) {
739 QualType FieldType = FieldLoc->getType();
740 if (FieldType->isRecordType()) {
741 Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc));
743 if (
Value *Val =
Env.createValue(FieldType))
744 Env.setValue(*FieldLoc, *Val);
751 void VisitCXXBoolLiteralExpr(
const CXXBoolLiteralExpr *S) {
752 Env.setValue(*S,
Env.getBoolLiteralValue(S->getValue()));
755 void VisitIntegerLiteral(
const IntegerLiteral *S) {
756 Env.setValue(*S,
Env.getIntLiteralValue(S->getValue()));
759 void VisitParenExpr(
const ParenExpr *S) {
763 auto *SubExpr = S->getSubExpr();
764 assert(SubExpr !=
nullptr);
768 void VisitExprWithCleanups(
const ExprWithCleanups *S) {
772 auto *SubExpr = S->getSubExpr();
773 assert(SubExpr !=
nullptr);
779 BoolValue &getLogicOperatorSubExprValue(
const Expr &SubExpr) {
783 if (
const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
785 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
793 if (
Env.getValue(SubExpr) ==
nullptr)
795 if (
auto *Val = dyn_cast_or_null<BoolValue>(
Env.getValue(SubExpr)))
800 return Env.makeAtomicBoolValue();
805 template <
typename E>
806 void transferInlineCall(
const E *S,
const FunctionDecl *F) {
807 const auto &Options =
Env.getDataflowAnalysisContext().getOptions();
808 if (!(Options.ContextSensitiveOpts &&
809 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
812 const AdornedCFG *ACFG =
Env.getDataflowAnalysisContext().getAdornedCFG(F);
820 auto ExitBlock = ACFG->getCFG().getExit().getBlockID();
822 auto CalleeEnv =
Env.pushCall(S);
827 auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(),
828 DataflowAnalysisOptions{Options});
830 auto BlockToOutputState =
832 assert(BlockToOutputState);
833 assert(ExitBlock < BlockToOutputState->size());
835 auto &ExitState = (*BlockToOutputState)[ExitBlock];
838 Env.popCall(S, ExitState->Env);
841 const StmtToEnvMap &StmtToEnv;
843 Environment::ValueModel &Model;
850 TransferVisitor(StmtToEnv,
Env, Model).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 isRecordType() const
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.
Supplements Environment with non-standard comparison and join operations.
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.
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 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.
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, Environment::ValueModel &Model)
Evaluates S and updates Env accordingly.
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)
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...
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).