29#include "llvm/ADT/STLExtras.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/ErrorHandling.h"
44 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
64template <
typename Derived,
typename M>
66 auto &
V = *cast<Derived>(&B);
72 if (&ULeft == &Left && &URight == &Right)
75 return (
Env.*build)(ULeft, URight);
79 switch (
V.getKind()) {
84 llvm_unreachable(
"BoolValue cannot have any of these kinds.");
94 auto &N = *cast<NegationValue>(&
V);
103 return unpackBinaryBoolValue<ConjunctionValue>(
Env,
V,
106 return unpackBinaryBoolValue<DisjunctionValue>(
Env,
V,
109 return unpackBinaryBoolValue<ImplicationValue>(
112 return unpackBinaryBoolValue<BiconditionalValue>(
Env,
V,
115 llvm_unreachable(
"All reachable cases in switch return");
127 auto *B = dyn_cast_or_null<BoolValue>(Val);
132 if (&UnpackedVal == Val)
165 TransferVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env)
166 : StmtToEnv(StmtToEnv),
Env(
Env) {}
168 void VisitBinaryOperator(
const BinaryOperator *S) {
169 const Expr *LHS = S->getLHS();
170 assert(LHS !=
nullptr);
172 const Expr *RHS = S->getRHS();
173 assert(RHS !=
nullptr);
175 switch (S->getOpcode()) {
177 auto *LHSLoc =
Env.getStorageLocationStrict(*LHS);
178 if (LHSLoc ==
nullptr)
181 auto *RHSVal =
Env.getValueStrict(*RHS);
182 if (RHSVal ==
nullptr)
186 Env.setValue(*LHSLoc, *RHSVal);
189 Env.setStorageLocation(*S, *LHSLoc);
194 auto &Loc =
Env.createStorageLocation(*S);
195 Env.setStorageLocation(*S, Loc);
197 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
198 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
200 if (S->getOpcode() == BO_LAnd)
201 Env.setValue(Loc,
Env.makeAnd(LHSVal, RHSVal));
203 Env.setValue(Loc,
Env.makeOr(LHSVal, RHSVal));
209 auto &Loc =
Env.createStorageLocation(*S);
210 Env.setStorageLocation(*S, Loc);
211 Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
212 :
Env.makeNot(LHSEqRHSValue));
224 void VisitDeclRefExpr(
const DeclRefExpr *S) {
225 const ValueDecl *VD = S->getDecl();
226 assert(VD !=
nullptr);
227 auto *DeclLoc =
Env.getStorageLocation(*VD);
228 if (DeclLoc ==
nullptr)
231 Env.setStorageLocationStrict(*S, *DeclLoc);
234 void VisitDeclStmt(
const DeclStmt *S) {
237 const auto &D = *cast<VarDecl>(S->getSingleDecl());
242 void ProcessVarDecl(
const VarDecl &D) {
244 if (D.hasGlobalStorage())
247 if (D.getType()->isReferenceType()) {
251 if (
Env.getStorageLocation(D) ==
nullptr) {
252 const Expr *InitExpr = D.getInit();
253 assert(InitExpr !=
nullptr);
254 if (
auto *InitExprLoc =
256 Env.setStorageLocation(D, *InitExprLoc);
262 StorageLocation &Loc =
263 Env.createStorageLocation(D.getType().getNonReferenceType());
264 Env.setStorageLocation(D, Loc);
265 if (
Value *Val =
Env.createValue(D.getType().getNonReferenceType()))
266 Env.setValue(Loc, *Val);
272 assert(
Env.getStorageLocation(D) ==
nullptr);
273 StorageLocation &Loc =
Env.createStorageLocation(D);
274 Env.setStorageLocation(D, Loc);
276 const Expr *InitExpr = D.getInit();
277 if (InitExpr ==
nullptr) {
279 if (
Value *Val =
Env.createValue(D.getType()))
280 Env.setValue(Loc, *Val);
284 if (
auto *InitExprVal =
Env.getValueStrict(*InitExpr))
285 Env.setValue(Loc, *InitExprVal);
287 if (
Env.getValue(Loc) ==
nullptr) {
299 if (
Value *Val =
Env.createValue(D.getType()))
300 Env.setValue(Loc, *Val);
307 if (
const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
313 for (
const auto *B : Decomp->bindings()) {
314 if (
auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) {
315 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
321 VisitDeclRefExpr(DE);
325 Env.setStorageLocation(*B, *Loc);
326 }
else if (
auto *VD = B->getHoldingVar()) {
334 auto *VDLoc =
Env.getStorageLocation(*VD);
335 assert(VDLoc !=
nullptr);
336 Env.setStorageLocation(*B, *VDLoc);
342 void VisitImplicitCastExpr(
const ImplicitCastExpr *S) {
343 const Expr *SubExpr = S->getSubExpr();
344 assert(SubExpr !=
nullptr);
346 switch (S->getCastKind()) {
347 case CK_IntegralToBoolean: {
351 if (
auto *SubExprVal =
352 dyn_cast_or_null<BoolValue>(
Env.getValueStrict(*SubExpr)))
353 Env.setValueStrict(*S, *SubExprVal);
357 Env.setValueStrict(*S,
Env.makeAtomicBoolValue());
361 case CK_LValueToRValue: {
366 if (SubExprVal ==
nullptr)
369 auto &ExprLoc =
Env.createStorageLocation(*S);
370 Env.setStorageLocation(*S, ExprLoc);
371 Env.setValue(ExprLoc, *SubExprVal);
375 case CK_IntegralCast:
381 case CK_UncheckedDerivedToBase:
382 case CK_ConstructorConversion:
383 case CK_UserDefinedConversion:
393 case CK_NullToPointer:
394 case CK_NullToMemberPointer: {
395 auto &Loc =
Env.createStorageLocation(S->getType());
396 Env.setStorageLocation(*S, Loc);
398 auto &NullPointerVal =
399 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
400 Env.setValue(Loc, NullPointerVal);
403 case CK_FunctionToPointerDecay: {
404 StorageLocation *PointeeLoc =
406 if (PointeeLoc ==
nullptr)
409 auto &PointerLoc =
Env.createStorageLocation(*S);
410 auto &PointerVal =
Env.create<PointerValue>(*PointeeLoc);
411 Env.setStorageLocation(*S, PointerLoc);
412 Env.setValue(PointerLoc, PointerVal);
420 void VisitUnaryOperator(
const UnaryOperator *S) {
421 const Expr *SubExpr = S->getSubExpr();
422 assert(SubExpr !=
nullptr);
424 switch (S->getOpcode()) {
426 const auto *SubExprVal =
427 cast_or_null<PointerValue>(
Env.getValueStrict(*SubExpr));
428 if (SubExprVal ==
nullptr)
431 Env.setStorageLocationStrict(*S, SubExprVal->getPointeeLoc());
438 StorageLocation *PointeeLoc =
Env.getStorageLocationStrict(*SubExpr);
439 if (PointeeLoc ==
nullptr)
442 Env.setValueStrict(*S,
Env.create<PointerValue>(*PointeeLoc));
447 dyn_cast_or_null<BoolValue>(
Env.getValueStrict(*SubExpr));
448 if (SubExprVal ==
nullptr)
451 auto &ExprLoc =
Env.createStorageLocation(*S);
452 Env.setStorageLocation(*S, ExprLoc);
453 Env.setValue(ExprLoc,
Env.makeNot(*SubExprVal));
461 void VisitCXXThisExpr(
const CXXThisExpr *S) {
462 auto *ThisPointeeLoc =
Env.getThisPointeeStorageLocation();
463 if (ThisPointeeLoc ==
nullptr)
468 auto &Loc =
Env.createStorageLocation(*S);
469 Env.setStorageLocation(*S, Loc);
470 Env.setValue(Loc,
Env.create<PointerValue>(*ThisPointeeLoc));
473 void VisitCXXNewExpr(
const CXXNewExpr *S) {
474 auto &Loc =
Env.createStorageLocation(*S);
475 Env.setStorageLocation(*S, Loc);
476 if (
Value *Val =
Env.createValue(S->getType()))
477 Env.setValue(Loc, *Val);
480 void VisitCXXDeleteExpr(
const CXXDeleteExpr *S) {
487 void VisitReturnStmt(
const ReturnStmt *S) {
488 if (!
Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
491 auto *
Ret = S->getRetValue();
495 if (
Ret->isPRValue()) {
496 auto *Val =
Env.getValueStrict(*Ret);
501 Env.setReturnValue(Val);
503 auto *Loc =
Env.getStorageLocationStrict(*Ret);
508 Env.setReturnStorageLocation(Loc);
512 void VisitMemberExpr(
const MemberExpr *S) {
513 ValueDecl *
Member = S->getMemberDecl();
514 assert(
Member !=
nullptr);
517 if (
Member->isFunctionOrFunctionTemplate())
521 if (isa<EnumConstantDecl>(
Member))
524 if (
auto *D = dyn_cast<VarDecl>(
Member)) {
525 if (D->hasGlobalStorage()) {
526 auto *VarDeclLoc =
Env.getStorageLocation(*D);
527 if (VarDeclLoc ==
nullptr)
530 Env.setStorageLocation(*S, *VarDeclLoc);
536 if (BaseLoc ==
nullptr)
539 auto &MemberLoc = BaseLoc->getChild(*
Member);
540 if (MemberLoc.getType()->isReferenceType()) {
552 if (
auto *
V =
Env.getValue(MemberLoc)) {
553 assert(isa<ReferenceValue>(
V) &&
554 "reference-typed declarations map to `ReferenceValue`s");
555 Env.setStorageLocation(*S, MemberLoc);
558 auto &Loc =
Env.createStorageLocation(*S);
559 Env.setStorageLocation(*S, Loc);
560 Env.setValue(Loc,
Env.create<ReferenceValue>(MemberLoc));
564 void VisitCXXDefaultInitExpr(
const CXXDefaultInitExpr *S) {
565 const Expr *InitExpr = S->getExpr();
566 assert(InitExpr !=
nullptr);
569 if (InitExprVal ==
nullptr)
572 const FieldDecl *
Field = S->getField();
573 assert(Field !=
nullptr);
576 *cast<AggregateStorageLocation>(
Env.getThisPointeeStorageLocation());
577 auto &FieldLoc = ThisLoc.getChild(*Field);
578 Env.setValue(FieldLoc, *InitExprVal);
581 void VisitCXXConstructExpr(
const CXXConstructExpr *S) {
582 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
583 assert(ConstructorDecl !=
nullptr);
585 if (ConstructorDecl->isCopyOrMoveConstructor()) {
588 assert(S->getNumArgs() != 0);
590 const Expr *Arg = S->getArg(0);
591 assert(Arg !=
nullptr);
593 if (S->isElidable()) {
595 if (ArgLoc ==
nullptr)
598 Env.setStorageLocation(*S, *ArgLoc);
600 auto &Loc =
Env.createStorageLocation(*S);
601 Env.setStorageLocation(*S, Loc);
602 Env.setValue(Loc, *ArgVal);
607 auto &Loc =
Env.createStorageLocation(*S);
608 Env.setStorageLocation(*S, Loc);
609 if (
Value *Val =
Env.createValue(S->getType()))
610 Env.setValue(Loc, *Val);
612 transferInlineCall(S, ConstructorDecl);
615 void VisitCXXOperatorCallExpr(
const CXXOperatorCallExpr *S) {
616 if (S->getOperator() == OO_Equal) {
617 assert(S->getNumArgs() == 2);
619 const Expr *Arg0 = S->getArg(0);
620 assert(Arg0 !=
nullptr);
622 const Expr *Arg1 = S->getArg(1);
623 assert(Arg1 !=
nullptr);
627 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
630 if (!Method->isCopyAssignmentOperator() &&
631 !Method->isMoveAssignmentOperator())
635 if (ObjectLoc ==
nullptr)
643 Env.setValue(*ObjectLoc, *Val);
647 Env.setStorageLocation(*S, *ObjectLoc);
651 void VisitCXXFunctionalCastExpr(
const CXXFunctionalCastExpr *S) {
652 if (S->getCastKind() == CK_ConstructorConversion) {
653 const Expr *SubExpr = S->getSubExpr();
654 assert(SubExpr !=
nullptr);
660 void VisitCXXTemporaryObjectExpr(
const CXXTemporaryObjectExpr *S) {
661 if (
Value *Val =
Env.createValue(S->getType()))
662 Env.setValueStrict(*S, *Val);
665 void VisitCallExpr(
const CallExpr *S) {
669 if (S->isCallToStdMove()) {
670 assert(S->getNumArgs() == 1);
672 const Expr *Arg = S->getArg(0);
673 assert(Arg !=
nullptr);
676 if (ArgLoc ==
nullptr)
679 Env.setStorageLocation(*S, *ArgLoc);
680 }
else if (S->getDirectCallee() !=
nullptr &&
681 S->getDirectCallee()->getBuiltinID() ==
682 Builtin::BI__builtin_expect) {
683 assert(S->getNumArgs() > 0);
684 assert(S->getArg(0) !=
nullptr);
688 if (ArgLoc ==
nullptr)
690 Env.setStorageLocation(*S, *ArgLoc);
691 }
else if (
const FunctionDecl *F = S->getDirectCallee()) {
692 transferInlineCall(S, F);
696 void VisitMaterializeTemporaryExpr(
const MaterializeTemporaryExpr *S) {
697 const Expr *SubExpr = S->getSubExpr();
698 assert(SubExpr !=
nullptr);
700 Value *SubExprVal =
Env.getValueStrict(*SubExpr);
701 if (SubExprVal ==
nullptr)
704 auto &Loc =
Env.createStorageLocation(*S);
705 Env.setStorageLocationStrict(*S, Loc);
706 Env.setValue(Loc, *SubExprVal);
709 void VisitCXXBindTemporaryExpr(
const CXXBindTemporaryExpr *S) {
710 const Expr *SubExpr = S->getSubExpr();
711 assert(SubExpr !=
nullptr);
716 void VisitCXXStaticCastExpr(
const CXXStaticCastExpr *S) {
717 if (S->getCastKind() == CK_NoOp) {
718 const Expr *SubExpr = S->getSubExpr();
719 assert(SubExpr !=
nullptr);
725 void VisitConditionalOperator(
const ConditionalOperator *S) {
729 if (S->isGLValue()) {
730 auto &Loc =
Env.createStorageLocation(*S);
731 Env.setStorageLocationStrict(*S, Loc);
732 if (
Value *Val =
Env.createValue(S->getType()))
733 Env.setValue(Loc, *Val);
734 }
else if (
Value *Val =
Env.createValue(S->getType())) {
735 Env.setValueStrict(*S, *Val);
739 void VisitInitListExpr(
const InitListExpr *S) {
740 QualType
Type = S->getType();
742 auto &Loc =
Env.createStorageLocation(*S);
743 Env.setStorageLocation(*S, Loc);
745 auto *Val =
Env.createValue(Type);
749 Env.setValue(Loc, *Val);
751 if (
Type->isStructureOrClassType()) {
756 std::vector<FieldDecl *> Fields;
758 Type->getAsRecordDecl()->fields(), std::back_inserter(Fields),
759 [](
const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
760 for (
auto It : llvm::zip(Fields, S->inits())) {
761 const FieldDecl *
Field = std::get<0>(It);
762 assert(Field !=
nullptr);
764 const Expr *Init = std::get<1>(It);
765 assert(Init !=
nullptr);
768 cast<StructValue>(Val)->setChild(*Field, *InitVal);
774 void VisitCXXBoolLiteralExpr(
const CXXBoolLiteralExpr *S) {
775 Env.setValueStrict(*S,
Env.getBoolLiteralValue(S->getValue()));
778 void VisitParenExpr(
const ParenExpr *S) {
782 auto *SubExpr = S->getSubExpr();
783 assert(SubExpr !=
nullptr);
787 void VisitExprWithCleanups(
const ExprWithCleanups *S) {
791 auto *SubExpr = S->getSubExpr();
792 assert(SubExpr !=
nullptr);
798 BoolValue &getLogicOperatorSubExprValue(
const Expr &SubExpr) {
802 if (
const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
804 dyn_cast_or_null<BoolValue>(SubExprEnv->getValueStrict(SubExpr)))
812 if (
Env.getValueStrict(SubExpr) ==
nullptr)
814 if (
auto *Val = dyn_cast_or_null<BoolValue>(
Env.getValueStrict(SubExpr)))
819 return Env.makeAtomicBoolValue();
824 template <
typename E>
825 void transferInlineCall(
const E *S,
const FunctionDecl *F) {
826 const auto &Options =
Env.getDataflowAnalysisContext().getOptions();
827 if (!(Options.ContextSensitiveOpts &&
828 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
831 const ControlFlowContext *
CFCtx =
832 Env.getDataflowAnalysisContext().getControlFlowContext(F);
840 auto ExitBlock =
CFCtx->getCFG().getExit().getBlockID();
842 auto CalleeEnv =
Env.pushCall(S);
847 assert(
CFCtx->getDecl() !=
nullptr &&
848 "ControlFlowContexts in the environment should always carry a decl");
849 auto Analysis = NoopAnalysis(
CFCtx->getDecl()->getASTContext(),
850 DataflowAnalysisOptions{Options});
852 auto BlockToOutputState =
854 assert(BlockToOutputState);
855 assert(ExitBlock < BlockToOutputState->size());
857 auto ExitState = (*BlockToOutputState)[ExitBlock];
860 Env.popCall(S, ExitState->Env);
863 const StmtToEnvMap &StmtToEnv;
870 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.
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 & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
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...
void setValueStrict(const Expr &E, Value &Val)
Assigns Val as the value of the prvalue E in the environment.
StorageLocation * getStorageLocationStrict(const Expr &E) const
Returns the storage location assigned to the glvalue E in the environment, or null if E isn't assigne...
Value * getValueStrict(const Expr &E) const
Returns the Value assigned to the prvalue E in the environment, or null if E isn't assigned a value i...
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
void setStorageLocationStrict(const Expr &E, StorageLocation &Loc)
Assigns Loc as the storage location of the glvalue E in the environment.
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
BoolValue & makeImplication(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS => RHS.
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.
BoolValue & unpackBinaryBoolValue(Environment &Env, BoolValue &B, M build)
static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, Environment &Env)
static void propagateStorageLocation(const Expr &From, const Expr &To, Environment &Env)
AggregateStorageLocation * 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...
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)
static BoolValue & unpackValue(BoolValue &V, Environment &Env)
static BoolValue & evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, Environment &Env)
@ Reference
An optional reference should be skipped past.
@ None
No indirections should be skipped past.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
bool Ret(InterpState &S, CodePtr &PC, APValue &Result)