30#include "llvm/Support/Casting.h"
31#include "llvm/Support/Debug.h"
35#define DEBUG_TYPE "dataflow"
45 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
56 if (LHSValue == RHSValue)
59 if (
auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue))
60 if (
auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue))
67 if (
auto *Top = llvm::dyn_cast<TopBoolValue>(&
V)) {
83 auto *B = dyn_cast_or_null<BoolValue>(Val);
88 if (&UnpackedVal == Val)
121 TransferVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env)
122 : StmtToEnv(StmtToEnv),
Env(
Env) {}
124 void VisitBinaryOperator(
const BinaryOperator *S) {
125 const Expr *LHS = S->getLHS();
126 assert(LHS !=
nullptr);
128 const Expr *RHS = S->getRHS();
129 assert(RHS !=
nullptr);
131 switch (S->getOpcode()) {
133 auto *LHSLoc =
Env.getStorageLocation(*LHS);
134 if (LHSLoc ==
nullptr)
137 auto *RHSVal =
Env.getValue(*RHS);
138 if (RHSVal ==
nullptr)
142 Env.setValue(*LHSLoc, *RHSVal);
145 Env.setStorageLocation(*S, *LHSLoc);
150 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
151 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
153 if (S->getOpcode() == BO_LAnd)
154 Env.setValue(*S,
Env.makeAnd(LHSVal, RHSVal));
156 Env.setValue(*S,
Env.makeOr(LHSVal, RHSVal));
162 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
163 :
Env.makeNot(LHSEqRHSValue));
175 void VisitDeclRefExpr(
const DeclRefExpr *S) {
176 const ValueDecl *VD = S->getDecl();
177 assert(VD !=
nullptr);
191 auto *DeclLoc =
Env.getStorageLocation(*VD);
192 if (DeclLoc ==
nullptr)
195 Env.setStorageLocation(*S, *DeclLoc);
198 void VisitDeclStmt(
const DeclStmt *S) {
201 const auto &D = *cast<VarDecl>(S->getSingleDecl());
206 void ProcessVarDecl(
const VarDecl &D) {
208 if (D.hasGlobalStorage())
214 if (D.getType()->isReferenceType() &&
Env.getStorageLocation(D) !=
nullptr)
217 assert(
Env.getStorageLocation(D) ==
nullptr);
219 Env.setStorageLocation(D,
Env.createObject(D));
224 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
230 for (
const auto *B : Decomp->bindings()) {
231 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
232 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
238 VisitDeclRefExpr(DE);
241 if (
auto *Loc =
Env.getStorageLocation(*ME))
242 Env.setStorageLocation(*B, *Loc);
243 }
else if (
auto *VD = B->getHoldingVar()) {
251 auto *VDLoc =
Env.getStorageLocation(*VD);
252 assert(VDLoc !=
nullptr);
253 Env.setStorageLocation(*B, *VDLoc);
259 void VisitImplicitCastExpr(
const ImplicitCastExpr *S) {
260 const Expr *SubExpr = S->getSubExpr();
261 assert(SubExpr !=
nullptr);
263 switch (S->getCastKind()) {
264 case CK_IntegralToBoolean: {
268 if (
auto *SubExprVal =
269 dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr)))
270 Env.setValue(*S, *SubExprVal);
274 Env.setValue(*S,
Env.makeAtomicBoolValue());
278 case CK_LValueToRValue: {
282 if (SubExprVal ==
nullptr)
285 Env.setValue(*S, *SubExprVal);
289 case CK_IntegralCast:
295 case CK_UncheckedDerivedToBase:
296 case CK_ConstructorConversion:
297 case CK_UserDefinedConversion:
307 case CK_NullToPointer: {
308 auto &NullPointerVal =
309 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
310 Env.setValue(*S, NullPointerVal);
313 case CK_NullToMemberPointer:
317 case CK_FunctionToPointerDecay: {
318 StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr);
319 if (PointeeLoc ==
nullptr)
322 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
325 case CK_BuiltinFnToFnPtr:
336 void VisitUnaryOperator(
const UnaryOperator *S) {
337 const Expr *SubExpr = S->getSubExpr();
338 assert(SubExpr !=
nullptr);
340 switch (S->getOpcode()) {
342 const auto *SubExprVal =
343 cast_or_null<PointerValue>(
Env.getValue(*SubExpr));
344 if (SubExprVal ==
nullptr)
347 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
352 if (S->getType()->isMemberPointerType())
355 if (StorageLocation *PointeeLoc =
Env.getStorageLocation(*SubExpr))
356 Env.setValue(*S,
Env.create<PointerValue>(*PointeeLoc));
360 auto *SubExprVal = dyn_cast_or_null<BoolValue>(
Env.getValue(*SubExpr));
361 if (SubExprVal ==
nullptr)
364 Env.setValue(*S,
Env.makeNot(*SubExprVal));
372 void VisitCXXThisExpr(
const CXXThisExpr *S) {
373 auto *ThisPointeeLoc =
Env.getThisPointeeStorageLocation();
374 if (ThisPointeeLoc ==
nullptr)
379 Env.setValue(*S,
Env.create<PointerValue>(*ThisPointeeLoc));
382 void VisitCXXNewExpr(
const CXXNewExpr *S) {
383 if (
Value *Val =
Env.createValue(S->getType()))
384 Env.setValue(*S, *Val);
387 void VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
394 void VisitReturnStmt(
const ReturnStmt *S) {
395 if (!
Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
398 auto *
Ret = S->getRetValue();
402 if (
Ret->isPRValue()) {
403 auto *Val =
Env.getValue(*Ret);
408 Env.setReturnValue(Val);
410 auto *Loc =
Env.getStorageLocation(*Ret);
415 Env.setReturnStorageLocation(Loc);
419 void VisitMemberExpr(
const MemberExpr *S) {
420 ValueDecl *
Member = S->getMemberDecl();
421 assert(
Member !=
nullptr);
424 if (
Member->isFunctionOrFunctionTemplate())
428 if (isa<EnumConstantDecl>(
Member))
431 if (
auto *D = dyn_cast<VarDecl>(
Member)) {
432 if (D->hasGlobalStorage()) {
433 auto *VarDeclLoc =
Env.getStorageLocation(*D);
434 if (VarDeclLoc ==
nullptr)
437 Env.setStorageLocation(*S, *VarDeclLoc);
443 if (BaseLoc ==
nullptr)
446 auto *MemberLoc = BaseLoc->getChild(*
Member);
447 if (MemberLoc ==
nullptr)
449 Env.setStorageLocation(*S, *MemberLoc);
452 void VisitCXXDefaultInitExpr(
const CXXDefaultInitExpr *S) {
453 const Expr *InitExpr = S->getExpr();
454 assert(InitExpr !=
nullptr);
458 void VisitCXXConstructExpr(
const CXXConstructExpr *S) {
459 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
460 assert(ConstructorDecl !=
nullptr);
462 if (ConstructorDecl->isCopyOrMoveConstructor()) {
465 assert(S->getNumArgs() != 0);
467 const Expr *Arg = S->getArg(0);
468 assert(Arg !=
nullptr);
471 cast_or_null<RecordStorageLocation>(
Env.getStorageLocation(*Arg));
472 if (ArgLoc ==
nullptr)
475 if (S->isElidable()) {
476 if (
Value *Val =
Env.getValue(*ArgLoc))
477 Env.setValue(*S, *Val);
479 auto &Val = *cast<RecordValue>(
Env.createValue(S->getType()));
480 Env.setValue(*S, Val);
489 if (S->getType()->isRecordType()) {
490 auto &InitialVal = *cast<RecordValue>(
Env.createValue(S->getType()));
491 Env.setValue(*S, InitialVal);
492 copyRecord(InitialVal.getLoc(),
Env.getResultObjectLocation(*S), Env);
495 transferInlineCall(S, ConstructorDecl);
498 void VisitCXXOperatorCallExpr(
const CXXOperatorCallExpr *S) {
499 if (S->getOperator() == OO_Equal) {
500 assert(S->getNumArgs() == 2);
502 const Expr *Arg0 = S->getArg(0);
503 assert(Arg0 !=
nullptr);
505 const Expr *Arg1 = S->getArg(1);
506 assert(Arg1 !=
nullptr);
510 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
513 if (!Method->isCopyAssignmentOperator() &&
514 !Method->isMoveAssignmentOperator())
517 RecordStorageLocation *LocSrc =
nullptr;
518 if (Arg1->isPRValue()) {
519 if (
auto *Val = cast_or_null<RecordValue>(
Env.getValue(*Arg1)))
520 LocSrc = &Val->getLoc();
523 cast_or_null<RecordStorageLocation>(
Env.getStorageLocation(*Arg1));
526 cast_or_null<RecordStorageLocation>(
Env.getStorageLocation(*Arg0));
528 if (LocSrc ==
nullptr || LocDst ==
nullptr)
534 if (Method->getFunctionObjectParameterType()
536 .getUnqualifiedType() !=
537 LocDst->getType().getCanonicalType().getUnqualifiedType())
541 Env.setStorageLocation(*S, *LocDst);
545 void VisitCXXFunctionalCastExpr(
const CXXFunctionalCastExpr *S) {
546 if (S->getCastKind() == CK_ConstructorConversion) {
547 const Expr *SubExpr = S->getSubExpr();
548 assert(SubExpr !=
nullptr);
554 void VisitCXXTemporaryObjectExpr(
const CXXTemporaryObjectExpr *S) {
555 if (
Value *Val =
Env.createValue(S->getType()))
556 Env.setValue(*S, *Val);
559 void VisitCallExpr(
const CallExpr *S) {
563 if (S->isCallToStdMove()) {
564 assert(S->getNumArgs() == 1);
566 const Expr *Arg = S->getArg(0);
567 assert(Arg !=
nullptr);
569 auto *ArgLoc =
Env.getStorageLocation(*Arg);
570 if (ArgLoc ==
nullptr)
573 Env.setStorageLocation(*S, *ArgLoc);
574 }
else if (S->getDirectCallee() !=
nullptr &&
575 S->getDirectCallee()->getBuiltinID() ==
576 Builtin::BI__builtin_expect) {
577 assert(S->getNumArgs() > 0);
578 assert(S->getArg(0) !=
nullptr);
579 auto *ArgVal =
Env.getValue(*S->getArg(0));
580 if (ArgVal ==
nullptr)
582 Env.setValue(*S, *ArgVal);
583 }
else if (
const FunctionDecl *F = S->getDirectCallee()) {
584 transferInlineCall(S, F);
588 void VisitMaterializeTemporaryExpr(
const MaterializeTemporaryExpr *S) {
589 const Expr *SubExpr = S->getSubExpr();
590 assert(SubExpr !=
nullptr);
592 Value *SubExprVal =
Env.getValue(*SubExpr);
593 if (SubExprVal ==
nullptr)
596 if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) {
597 Env.setStorageLocation(*S, RecordVal->getLoc());
601 StorageLocation &Loc =
Env.createStorageLocation(*S);
602 Env.setValue(Loc, *SubExprVal);
603 Env.setStorageLocation(*S, Loc);
606 void VisitCXXBindTemporaryExpr(
const CXXBindTemporaryExpr *S) {
607 const Expr *SubExpr = S->getSubExpr();
608 assert(SubExpr !=
nullptr);
613 void VisitCXXStaticCastExpr(
const CXXStaticCastExpr *S) {
614 if (S->getCastKind() == CK_NoOp) {
615 const Expr *SubExpr = S->getSubExpr();
616 assert(SubExpr !=
nullptr);
622 void VisitConditionalOperator(
const ConditionalOperator *S) {
631 Env.setStorageLocation(*S,
Env.createObject(S->getType()));
632 else if (
Value *Val =
Env.createValue(S->getType()))
633 Env.setValue(*S, *Val);
636 void VisitInitListExpr(
const InitListExpr *S) {
637 QualType
Type = S->getType();
639 if (!
Type->isStructureOrClassType()) {
640 if (
auto *Val =
Env.createValue(Type))
641 Env.setValue(*S, *Val);
648 if (S->isSemanticForm() && S->isTransparent()) {
653 llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
656 std::vector<FieldDecl *> FieldsForInit =
661 auto Inits = S->inits();
665 if (
auto* R = S->getType()->getAsCXXRecordDecl()) {
666 assert(FieldsForInit.size() + R->getNumBases() == Inits.size());
667 for ([[maybe_unused]]
const CXXBaseSpecifier &
Base : R->bases()) {
668 assert(InitIdx < Inits.size());
669 auto Init = Inits[InitIdx++];
670 assert(
Base.getType().getCanonicalType() ==
671 Init->getType().getCanonicalType());
672 auto* BaseVal = cast_or_null<RecordValue>(
Env.getValue(*
Init));
674 BaseVal = cast<RecordValue>(
Env.createValue(
Init->getType()));
678 auto Children = BaseVal->getLoc().children();
679 FieldLocs.insert(Children.begin(), Children.end());
683 assert(FieldsForInit.size() == Inits.size() - InitIdx);
684 for (
auto Field : FieldsForInit) {
685 assert(InitIdx < Inits.size());
686 auto Init = Inits[InitIdx++];
689 Field->getType().getCanonicalType().getUnqualifiedType() ==
690 Init->getType().getCanonicalType().getUnqualifiedType() ||
692 (
Field->getType()->isReferenceType() &&
693 Field->getType().getCanonicalType()->getPointeeType() ==
694 Init->getType().getCanonicalType()));
696 FieldLocs.insert({
Field, &Loc});
708 Env.getDataflowAnalysisContext().getModeledFields(Type);
709 if (ModeledFields.size() != FieldLocs.size())
711 for ([[maybe_unused]]
auto [Field, Loc] : FieldLocs)
712 if (!ModeledFields.contains(cast_or_null<FieldDecl>(Field)))
718 Env.getDataflowAnalysisContext().arena().create<RecordStorageLocation>(
719 Type, std::move(FieldLocs));
720 RecordValue &RecordVal =
Env.create<RecordValue>(Loc);
722 Env.setValue(Loc, RecordVal);
724 Env.setValue(*S, RecordVal);
729 void VisitCXXBoolLiteralExpr(
const CXXBoolLiteralExpr *S) {
730 Env.setValue(*S,
Env.getBoolLiteralValue(S->getValue()));
733 void VisitIntegerLiteral(
const IntegerLiteral *S) {
734 Env.setValue(*S,
Env.getIntLiteralValue(S->getValue()));
737 void VisitParenExpr(
const ParenExpr *S) {
741 auto *SubExpr = S->getSubExpr();
742 assert(SubExpr !=
nullptr);
746 void VisitExprWithCleanups(
const ExprWithCleanups *S) {
750 auto *SubExpr = S->getSubExpr();
751 assert(SubExpr !=
nullptr);
757 BoolValue &getLogicOperatorSubExprValue(
const Expr &SubExpr) {
761 if (
const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
763 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
771 if (
Env.getValue(SubExpr) ==
nullptr)
773 if (
auto *Val = dyn_cast_or_null<BoolValue>(
Env.getValue(SubExpr)))
778 return Env.makeAtomicBoolValue();
783 template <
typename E>
784 void transferInlineCall(
const E *S,
const FunctionDecl *F) {
785 const auto &Options =
Env.getDataflowAnalysisContext().getOptions();
786 if (!(Options.ContextSensitiveOpts &&
787 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
790 const ControlFlowContext *
CFCtx =
791 Env.getDataflowAnalysisContext().getControlFlowContext(F);
799 auto ExitBlock =
CFCtx->getCFG().getExit().getBlockID();
801 auto CalleeEnv =
Env.pushCall(S);
806 auto Analysis = NoopAnalysis(
CFCtx->getDecl().getASTContext(),
807 DataflowAnalysisOptions{Options});
809 auto BlockToOutputState =
811 assert(BlockToOutputState);
812 assert(ExitBlock < BlockToOutputState->size());
814 auto &ExitState = (*BlockToOutputState)[ExitBlock];
817 Env.popCall(S, ExitState->Env);
820 const StmtToEnvMap &StmtToEnv;
827 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.
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
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.
BoolValue & makeBoolValue(const Formula &)
Creates a BoolValue wrapping a particular formula.
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.
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 ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr)
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.
std::vector< FieldDecl * > getFieldsForInitListExpr(const RecordDecl *RD)
Returns the fields of RD that are initialized by an InitListExpr, in the order in which they appear i...
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)
for(unsigned I=0, E=TL.getNumArgs();I !=E;++I)