Go to the documentation of this file.
15 #include <system_error>
29 #include "llvm/ADT/ArrayRef.h"
30 #include "llvm/ADT/DenseSet.h"
31 #include "llvm/ADT/None.h"
32 #include "llvm/ADT/Optional.h"
33 #include "llvm/ADT/STLExtras.h"
34 #include "llvm/Support/Error.h"
35 #include "llvm/Support/ErrorHandling.h"
46 : CFCtx(CFCtx), BlockToState(BlockToState) {}
51 const auto &
State = BlockToState[BlockIT->getSecond()->getBlockID()];
52 assert(
State.hasValue());
53 return &
State.getValue().Env;
64 auto BlockPos = llvm::find_if(
66 return Succ && Succ->getBlockID() == Block.getBlockID();
77 : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
80 auto *Cond = S->getCond();
81 assert(Cond !=
nullptr);
82 extendFlowCondition(*Cond);
86 auto *Cond = S->getCond();
87 assert(Cond !=
nullptr);
88 extendFlowCondition(*Cond);
92 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
93 auto *LHS = S->getLHS();
94 assert(LHS !=
nullptr);
95 extendFlowCondition(*LHS);
99 auto *Cond = S->getCond();
100 assert(Cond !=
nullptr);
101 extendFlowCondition(*Cond);
105 void extendFlowCondition(
const Expr &Cond) {
118 if (Val ==
nullptr) {
121 if (Loc ==
nullptr) {
131 if (BlockSuccIdx == 1)
137 const StmtToEnvMap &StmtToEnv;
156 Preds.insert(
Block.pred_begin(),
Block.pred_end());
157 if (
Block.getTerminator().isTemporaryDtorsBranch()) {
180 if (
Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
183 Preds.erase(StmtBlock->getSecond());
190 for (
const CFGBlock *Pred : Preds) {
192 if (!Pred || Pred->hasNoReturnElement())
198 BlockStates[Pred->getBlockID()];
199 if (!MaybePredState.hasValue())
203 if (ApplyBuiltinTransfer) {
204 if (
const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
208 .
Visit(PredTerminatorStmt);
212 if (MaybeState.hasValue()) {
214 MaybeState->Env.join(PredState.
Env, Analysis);
216 MaybeState = std::move(PredState);
219 if (!MaybeState.hasValue()) {
236 std::function<
void(
const CFGStmt &,
238 HandleTransferredStmt) {
240 assert(S !=
nullptr);
246 if (HandleTransferredStmt !=
nullptr)
247 HandleTransferredStmt(CfgStmt,
State);
253 const auto &ThisLoc = *cast<AggregateStorageLocation>(
254 State.Env.getThisPointeeStorageLocation());
260 assert(InitStmt !=
nullptr);
264 if (InitStmtLoc ==
nullptr)
267 auto *InitStmtVal =
State.Env.getValue(*InitStmtLoc);
268 if (InitStmtVal ==
nullptr)
272 assert(
Member !=
nullptr);
274 if (
Member->getType()->isReferenceType()) {
275 auto &MemberLoc = ThisLoc.getChild(*
Member);
276 State.Env.setValue(MemberLoc,
277 State.Env.takeOwnership(
278 std::make_unique<ReferenceValue>(*InitStmtLoc)));
280 auto &MemberLoc = ThisLoc.getChild(*
Member);
281 State.Env.setValue(MemberLoc, *InitStmtVal);
290 std::function<
void(
const CFGStmt &,
292 HandleTransferredStmt) {
296 switch (Element.getKind()) {
299 State, HandleTransferredStmt);
320 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
321 BlockStates.resize(CFCtx.
getCFG().
size(), llvm::None);
335 uint32_t Iterations = 0;
336 static constexpr uint32_t MaxIterations = 1 << 16;
338 if (++Iterations > MaxIterations) {
339 return llvm::createStringError(std::errc::timed_out,
340 "maximum number of iterations reached");
344 BlockStates[
Block->getBlockID()];
348 if (OldBlockState.hasValue() &&
351 OldBlockState->Env.equivalentTo(NewBlockState.
Env, Analysis)) {
357 BlockStates[
Block->getBlockID()] = std::move(NewBlockState);
360 if (
Block->hasNoReturnElement())
const Environment * getEnvironment(const Stmt &S) const override
Returns the environment of the basic block that contains S or nullptr if there isn't one.
WhileStmt - This represents a 'while' stmt.
succ_iterator succ_begin()
unsigned getBlockID() const
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
static int blockIndexInPredecessor(const CFGBlock &Pred, const CFGBlock &Block)
Returns the index of Block in the successors of Pred.
Represents a member of a struct/union/class.
StmtToEnvMapImpl(const ControlFlowContext &CFCtx, llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState >> BlockToState)
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
TypeErasedLattice Lattice
Type-erased model of a program property.
IfStmt - This represents an if/then/else.
@ Reference
An optional reference should be skipped past.
const llvm::DenseMap< const Stmt *, const CFGBlock * > & getStmtToBlock() const
Returns a mapping from statements to basic blocks that contain them.
TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, int BlockSuccIdx)
void VisitWhileStmt(const WhileStmt *S)
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
void VisitBinaryOperator(const BinaryOperator *S)
void addToFlowCondition(BoolValue &Val)
Adds Val to the set of clauses that constitute the flow condition.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
ConditionalOperator - The ?: ternary operator.
Represents a single basic block in a source-level CFG.
virtual void transferTypeErased(const Stmt *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given statement and type-erased lattice element.
Extends the flow condition of an environment based on a terminator statement.
A builtin binary operation expression such as "x + y" or "x <= y".
Maps statements to the environments of basic blocks that contain them.
@ None
No indirections should be skipped past.
CXXCtorInitializer * getInitializer() const
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
TypeErasedDataflowAnalysisState transferBlock(const ControlFlowContext &CFCtx, std::vector< llvm::Optional< TypeErasedDataflowAnalysisState >> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, std::function< void(const CFGStmt &, const TypeErasedDataflowAnalysisState &)> HandleTransferredStmt=nullptr)
Transfers the state of a basic block by evaluating each of its statements in the context of Analysis ...
static void transferCFGInitializer(const CFGInitializer &CfgInit, TypeErasedDataflowAnalysisState &State)
Transfers State by evaluating CfgInit.
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
A worklist implementation for forward dataflow analysis.
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...
Represents C++ base or member initializer from constructor's initialization list.
void VisitConditionalOperator(const ConditionalOperator *S)
Holds CFG and other derived context that is needed to perform dataflow analysis.
const CFGBlock * dequeue()
const Stmt * getStmt() const
static TypeErasedDataflowAnalysisState computeBlockInputState(const ControlFlowContext &CFCtx, std::vector< llvm::Optional< TypeErasedDataflowAnalysisState >> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis)
Computes the input state for a given basic block by joining the output states of its predecessors.
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
This class represents a potential adjacent block in the CFG.
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
void enqueueSuccessors(const CFGBlock *Block)
Type-erased base class for dataflow analyses built on a single lattice type.
Represents a top-level expression in a basic block.
Stmt - This represents one statement.
virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
llvm::Expected< std::vector< llvm::Optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &, const TypeErasedLattice &)=0
Joins two type-erased lattice elements by computing their least upper bound.
StorageLocation * getStorageLocation(const ValueDecl &D, SkipPast SP) const
Returns the storage location assigned to D in the environment, applying the SP policy for skipping pa...
void VisitIfStmt(const IfStmt *S)
Holds the state of the program (store and heap) at a given program point.
bool applyBuiltinTransfer() const
Determines whether to apply the built-in transfer functions, which model the heap and stack in the En...
This represents one expression.
Type-erased model of the program at a given program point.
Represents a C++ base or member initializer.
Environment Env
Model of the state of the program (store and heap).
static void transferCFGStmt(const ControlFlowContext &CFCtx, llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState >> BlockStates, const CFGStmt &CfgStmt, TypeErasedDataflowAnalysis &Analysis, TypeErasedDataflowAnalysisState &State, std::function< void(const CFGStmt &, const TypeErasedDataflowAnalysisState &)> HandleTransferredStmt)
Transfers State by evaluating CfgStmt in the context of Analysis.
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
const CFG & getCFG() const
Returns the CFG that is stored in this context.