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))
71 if (
auto *LHSPtr = dyn_cast_or_null<PointerValue>(LHSValue))
72 if (
auto *RHSPtr = dyn_cast_or_null<PointerValue>(RHSValue))
76 if (&LHSPtr->getPointeeLoc() == &RHSPtr->getPointeeLoc())
83 if (
auto *Top = llvm::dyn_cast<TopBoolValue>(&
V)) {
99 auto *B = dyn_cast_or_null<BoolValue>(Val);
104 if (&UnpackedVal == Val)
139 TransferVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env,
140 Environment::ValueModel &Model)
141 : StmtToEnv(StmtToEnv),
Env(
Env), Model(Model) {}
143 void VisitBinaryOperator(
const BinaryOperator *S) {
144 const Expr *LHS = S->getLHS();
145 assert(LHS !=
nullptr);
147 const Expr *RHS = S->getRHS();
148 assert(RHS !=
nullptr);
154 if (S->isCompoundAssignmentOp())
157 switch (S->getOpcode()) {
159 auto *LHSLoc =
Env.getStorageLocation(*LHS);
160 if (LHSLoc ==
nullptr)
163 auto *RHSVal =
Env.getValue(*RHS);
164 if (RHSVal ==
nullptr)
168 Env.setValue(*LHSLoc, *RHSVal);
171 Env.setStorageLocation(*S, *LHSLoc);
176 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
177 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
179 if (S->getOpcode() == BO_LAnd)
180 Env.setValue(*S,
Env.makeAnd(LHSVal, RHSVal));
182 Env.setValue(*S,
Env.makeOr(LHSVal, RHSVal));
188 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
189 :
Env.makeNot(LHSEqRHSValue));
201 void VisitDeclRefExpr(
const DeclRefExpr *S) {
202 const ValueDecl *VD = S->getDecl();
203 assert(VD !=
nullptr);
217 auto *DeclLoc =
Env.getStorageLocation(*VD);
218 if (DeclLoc ==
nullptr)
221 Env.setStorageLocation(*S, *DeclLoc);
224 void VisitDeclStmt(
const DeclStmt *S) {
227 const auto &
D = *cast<VarDecl>(S->getSingleDecl());
232 void ProcessVarDecl(
const VarDecl &
D) {
234 if (
D.hasGlobalStorage())
240 if (
D.getType()->isReferenceType() &&
Env.getStorageLocation(
D) !=
nullptr)
243 assert(
Env.getStorageLocation(
D) ==
nullptr);
245 Env.setStorageLocation(
D,
Env.createObject(
D));
250 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&
D)) {
256 for (
const auto *B : Decomp->bindings()) {
257 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
258 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
264 VisitDeclRefExpr(DE);
267 if (
auto *
Loc =
Env.getStorageLocation(*ME))
268 Env.setStorageLocation(*B, *
Loc);
269 }
else if (
auto *VD = B->getHoldingVar()) {
277 auto *VDLoc =
Env.getStorageLocation(*VD);
278 assert(VDLoc !=
nullptr);
279 Env.setStorageLocation(*B, *VDLoc);
285 void VisitImplicitCastExpr(
const ImplicitCastExpr *S) {
286 const Expr *SubExpr = S->getSubExpr();
287 assert(SubExpr !=
nullptr);
289 switch (S->getCastKind()) {
290 case CK_IntegralToBoolean: {
294 if (
auto *SubExprVal =
295 dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr)))
296 Env.setValue(*S, *SubExprVal);
300 Env.setValue(*S,
Env.makeAtomicBoolValue());
304 case CK_LValueToRValue: {
308 if (SubExprVal ==
nullptr)
311 Env.setValue(*S, *SubExprVal);
315 case CK_IntegralCast:
321 case CK_UncheckedDerivedToBase:
322 case CK_ConstructorConversion:
323 case CK_UserDefinedConversion:
333 case CK_NullToPointer: {
334 auto &NullPointerVal =
335 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
336 Env.setValue(*S, NullPointerVal);
339 case CK_NullToMemberPointer:
343 case CK_FunctionToPointerDecay: {
344 StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr);
345 if (PointeeLoc ==
nullptr)
348 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
351 case CK_BuiltinFnToFnPtr:
362 void VisitUnaryOperator(
const UnaryOperator *S) {
363 const Expr *SubExpr = S->getSubExpr();
364 assert(SubExpr !=
nullptr);
366 switch (S->getOpcode()) {
368 const auto *SubExprVal =
Env.get<PointerValue>(*SubExpr);
369 if (SubExprVal ==
nullptr)
372 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
377 if (S->getType()->isMemberPointerType())
380 if (StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr))
381 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
385 auto *SubExprVal = dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr));
386 if (SubExprVal ==
nullptr)
389 Env.setValue(*S,
Env.makeNot(*SubExprVal));
399 if (StorageLocation *
Loc =
Env.getStorageLocation(*S->getSubExpr()))
408 if (StorageLocation *
Loc =
Env.getStorageLocation(*S->getSubExpr()))
416 void VisitCXXThisExpr(
const CXXThisExpr *S) {
417 auto *ThisPointeeLoc =
Env.getThisPointeeStorageLocation();
418 if (ThisPointeeLoc ==
nullptr)
423 Env.setValue(*S,
Env.create<PointerValue>(*ThisPointeeLoc));
426 void VisitCXXNewExpr(
const CXXNewExpr *S) {
427 if (
Value *Val =
Env.createValue(S->getType()))
428 Env.setValue(*S, *Val);
431 void VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
438 void VisitReturnStmt(
const ReturnStmt *S) {
439 if (!
Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
442 auto *
Ret = S->getRetValue();
446 if (
Ret->isPRValue()) {
447 if (
Ret->getType()->isRecordType())
450 auto *Val =
Env.getValue(*Ret);
455 Env.setReturnValue(Val);
457 auto *
Loc =
Env.getStorageLocation(*Ret);
462 Env.setReturnStorageLocation(
Loc);
466 void VisitMemberExpr(
const MemberExpr *S) {
467 ValueDecl *
Member = S->getMemberDecl();
468 assert(
Member !=
nullptr);
471 if (
Member->isFunctionOrFunctionTemplate())
475 if (isa<EnumConstantDecl>(
Member))
478 if (
auto *
D = dyn_cast<VarDecl>(
Member)) {
479 if (
D->hasGlobalStorage()) {
480 auto *VarDeclLoc =
Env.getStorageLocation(*
D);
481 if (VarDeclLoc ==
nullptr)
484 Env.setStorageLocation(*S, *VarDeclLoc);
490 if (BaseLoc ==
nullptr)
493 auto *MemberLoc = BaseLoc->getChild(*
Member);
494 if (MemberLoc ==
nullptr)
496 Env.setStorageLocation(*S, *MemberLoc);
499 void VisitCXXDefaultArgExpr(
const CXXDefaultArgExpr *S) {
500 const Expr *ArgExpr = S->getExpr();
501 assert(ArgExpr !=
nullptr);
504 if (S->isPRValue() && S->getType()->isRecordType()) {
505 auto &
Loc =
Env.getResultObjectLocation(*S);
506 Env.initializeFieldsWithValues(
Loc);
510 void VisitCXXDefaultInitExpr(
const CXXDefaultInitExpr *S) {
511 const Expr *InitExpr = S->getExpr();
512 assert(InitExpr !=
nullptr);
517 if (S->getType()->isRecordType() && S->isPRValue())
523 void VisitCXXConstructExpr(
const CXXConstructExpr *S) {
524 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
525 assert(ConstructorDecl !=
nullptr);
530 if (!S->getType()->isRecordType()) {
531 transferInlineCall(S, ConstructorDecl);
535 RecordStorageLocation &
Loc =
Env.getResultObjectLocation(*S);
537 if (ConstructorDecl->isCopyOrMoveConstructor()) {
540 assert(S->getNumArgs() != 0);
542 const Expr *Arg = S->getArg(0);
543 assert(Arg !=
nullptr);
545 auto *ArgLoc =
Env.get<RecordStorageLocation>(*Arg);
546 if (ArgLoc ==
nullptr)
556 Env.initializeFieldsWithValues(
Loc, S->getType());
558 transferInlineCall(S, ConstructorDecl);
561 void VisitCXXOperatorCallExpr(
const CXXOperatorCallExpr *S) {
562 if (S->getOperator() == OO_Equal) {
563 assert(S->getNumArgs() == 2);
565 const Expr *Arg0 = S->getArg(0);
566 assert(Arg0 !=
nullptr);
568 const Expr *Arg1 = S->getArg(1);
569 assert(Arg1 !=
nullptr);
573 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
576 if (!Method->isCopyAssignmentOperator() &&
577 !Method->isMoveAssignmentOperator())
580 RecordStorageLocation *LocSrc =
nullptr;
581 if (Arg1->isPRValue()) {
582 LocSrc = &
Env.getResultObjectLocation(*Arg1);
584 LocSrc =
Env.get<RecordStorageLocation>(*Arg1);
586 auto *LocDst =
Env.get<RecordStorageLocation>(*Arg0);
588 if (LocSrc ==
nullptr || LocDst ==
nullptr)
596 if (S->getType().getCanonicalType().getUnqualifiedType() !=
597 LocDst->getType().getCanonicalType().getUnqualifiedType()) {
598 auto ReturnDecl = S->getType()->getAsCXXRecordDecl();
599 auto DstDecl = LocDst->getType()->getAsCXXRecordDecl();
600 if (ReturnDecl ==
nullptr || DstDecl ==
nullptr)
602 if (!DstDecl->isDerivedFrom(ReturnDecl))
607 Env.setStorageLocation(*S, *LocDst);
619 void VisitCXXRewrittenBinaryOperator(
const CXXRewrittenBinaryOperator *RBO) {
623 void VisitCallExpr(
const CallExpr *S) {
627 if (S->isCallToStdMove()) {
628 assert(S->getNumArgs() == 1);
630 const Expr *Arg = S->getArg(0);
631 assert(Arg !=
nullptr);
633 auto *ArgLoc =
Env.getStorageLocation(*Arg);
634 if (ArgLoc ==
nullptr)
637 Env.setStorageLocation(*S, *ArgLoc);
638 }
else if (S->getDirectCallee() !=
nullptr &&
639 S->getDirectCallee()->getBuiltinID() ==
640 Builtin::BI__builtin_expect) {
641 assert(S->getNumArgs() > 0);
642 assert(S->getArg(0) !=
nullptr);
643 auto *ArgVal =
Env.getValue(*S->getArg(0));
644 if (ArgVal ==
nullptr)
646 Env.setValue(*S, *ArgVal);
647 }
else if (
const FunctionDecl *F = S->getDirectCallee()) {
648 transferInlineCall(S, F);
652 if (S->getType()->isRecordType() && S->isPRValue()) {
653 RecordStorageLocation &
Loc =
Env.getResultObjectLocation(*S);
654 Env.initializeFieldsWithValues(
Loc);
659 void VisitMaterializeTemporaryExpr(
const MaterializeTemporaryExpr *S) {
660 const Expr *SubExpr = S->getSubExpr();
661 assert(SubExpr !=
nullptr);
663 StorageLocation &
Loc =
Env.createStorageLocation(*S);
664 Env.setStorageLocation(*S,
Loc);
666 if (SubExpr->getType()->isRecordType())
671 if (
Value *SubExprVal =
Env.getValue(*SubExpr))
672 Env.setValue(
Loc, *SubExprVal);
675 void VisitCXXBindTemporaryExpr(
const CXXBindTemporaryExpr *S) {
676 const Expr *SubExpr = S->getSubExpr();
677 assert(SubExpr !=
nullptr);
682 void VisitCXXStaticCastExpr(
const CXXStaticCastExpr *S) {
683 if (S->getCastKind() == CK_NoOp) {
684 const Expr *SubExpr = S->getSubExpr();
685 assert(SubExpr !=
nullptr);
691 void VisitConditionalOperator(
const ConditionalOperator *S) {
692 const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr());
693 const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr());
695 if (TrueEnv ==
nullptr || FalseEnv ==
nullptr) {
703 if (S->isGLValue()) {
704 StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr());
705 StorageLocation *FalseLoc =
706 FalseEnv->getStorageLocation(*S->getFalseExpr());
707 if (TrueLoc == FalseLoc && TrueLoc !=
nullptr)
708 Env.setStorageLocation(*S, *TrueLoc);
709 }
else if (!S->getType()->isRecordType()) {
726 S->getType(), TrueEnv->getValue(*S->getTrueExpr()), *TrueEnv,
727 FalseEnv->getValue(*S->getFalseExpr()), *FalseEnv, Env, Model))
728 Env.setValue(*S, *Val);
732 void VisitInitListExpr(
const InitListExpr *S) {
733 QualType
Type = S->getType();
735 if (!
Type->isRecordType()) {
738 if (!
Type->isArrayType() && S->getNumInits() == 1)
744 if (S->isSemanticForm() && S->isTransparent())
747 RecordStorageLocation &
Loc =
Env.getResultObjectLocation(*S);
754 RecordInitListHelper InitListHelper(S);
756 for (
auto [Field,
Init] : InitListHelper.field_inits()) {
757 if (
Field->getType()->isRecordType())
759 if (
Field->getType()->isReferenceType()) {
760 assert(
Field->getType().getCanonicalType()->getPointeeType() ==
761 Init->getType().getCanonicalType());
765 assert(
Field->getType().getCanonicalType().getUnqualifiedType() ==
766 Init->getType().getCanonicalType().getUnqualifiedType());
767 StorageLocation *FieldLoc =
Loc.getChild(*Field);
769 assert(FieldLoc !=
nullptr);
771 if (Val ==
nullptr && isa<ImplicitValueInitExpr>(
Init) &&
772 Init->getType()->isPointerType())
774 &
Env.getOrCreateNullPointerValue(
Init->getType()->getPointeeType());
776 Val =
Env.createValue(
Field->getType());
778 Env.setValue(*FieldLoc, *Val);
781 for (
const auto &[FieldName, FieldLoc] :
Loc.synthetic_fields()) {
782 QualType FieldType = FieldLoc->getType();
783 if (FieldType->isRecordType()) {
784 Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc));
786 if (
Value *Val =
Env.createValue(FieldType))
787 Env.setValue(*FieldLoc, *Val);
794 void VisitCXXBoolLiteralExpr(
const CXXBoolLiteralExpr *S) {
795 Env.setValue(*S,
Env.getBoolLiteralValue(S->getValue()));
798 void VisitIntegerLiteral(
const IntegerLiteral *S) {
799 Env.setValue(*S,
Env.getIntLiteralValue(S->getValue()));
802 void VisitParenExpr(
const ParenExpr *S) {
806 auto *SubExpr = S->getSubExpr();
807 assert(SubExpr !=
nullptr);
811 void VisitExprWithCleanups(
const ExprWithCleanups *S) {
815 auto *SubExpr = S->getSubExpr();
816 assert(SubExpr !=
nullptr);
822 BoolValue &getLogicOperatorSubExprValue(
const Expr &SubExpr) {
826 if (
const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
828 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
836 if (
Env.getValue(SubExpr) ==
nullptr)
838 if (
auto *Val = dyn_cast_or_null<BoolValue>(
Env.getValue(SubExpr)))
843 return Env.makeAtomicBoolValue();
848 template <
typename E>
849 void transferInlineCall(
const E *S,
const FunctionDecl *F) {
850 const auto &Options =
Env.getDataflowAnalysisContext().getOptions();
851 if (!(Options.ContextSensitiveOpts &&
852 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
855 const AdornedCFG *ACFG =
Env.getDataflowAnalysisContext().getAdornedCFG(F);
863 auto ExitBlock = ACFG->getCFG().getExit().getBlockID();
865 auto CalleeEnv =
Env.pushCall(S);
870 auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(),
871 DataflowAnalysisOptions{Options});
873 auto BlockToOutputState =
875 assert(BlockToOutputState);
876 assert(ExitBlock < BlockToOutputState->size());
878 auto &ExitState = (*BlockToOutputState)[ExitBlock];
881 Env.popCall(S, ExitState->Env);
884 const StmtToEnvMap &StmtToEnv;
886 Environment::ValueModel &Model;
893 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.
llvm::Expected< std::vector< std::optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const AdornedCFG &ACFG, AnalysisT &Analysis, const Environment &InitEnv, CFGEltCallbacks< AnalysisT > PostAnalysisCallbacks, std::int32_t MaxBlockVisits=kDefaultMaxBlockVisits)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, Environment &Env)
static void propagateStorageLocation(const Expr &From, const Expr &To, Environment &Env)
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).