17#include <system_error>
32#include "llvm/ADT/ArrayRef.h"
33#include "llvm/ADT/DenseSet.h"
34#include "llvm/ADT/STLExtras.h"
35#include "llvm/Support/Debug.h"
36#include "llvm/Support/Error.h"
38#define DEBUG_TYPE "clang-dataflow"
46 auto BlockPos = llvm::find_if(
48 return Succ && Succ->getBlockID() == Block.getBlockID();
55 switch (T->getStmtClass()) {
56 case Stmt::WhileStmtClass:
57 case Stmt::DoStmtClass:
58 case Stmt::ForStmtClass:
73using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
77class TerminatorVisitor
80 TerminatorVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env,
82 : StmtToEnv(StmtToEnv),
Env(
Env), BlockSuccIdx(BlockSuccIdx) {}
84 TerminatorVisitorRetTy VisitIfStmt(
const IfStmt *S) {
85 auto *Cond = S->getCond();
86 assert(Cond !=
nullptr);
87 return extendFlowCondition(*Cond);
90 TerminatorVisitorRetTy VisitWhileStmt(
const WhileStmt *S) {
91 auto *Cond = S->getCond();
92 assert(Cond !=
nullptr);
93 return extendFlowCondition(*Cond);
96 TerminatorVisitorRetTy VisitDoStmt(
const DoStmt *S) {
97 auto *Cond = S->getCond();
98 assert(Cond !=
nullptr);
99 return extendFlowCondition(*Cond);
102 TerminatorVisitorRetTy VisitForStmt(
const ForStmt *S) {
103 auto *Cond = S->getCond();
105 return extendFlowCondition(*Cond);
106 return {
nullptr,
false};
109 TerminatorVisitorRetTy VisitBinaryOperator(
const BinaryOperator *S) {
110 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
111 auto *LHS = S->getLHS();
112 assert(LHS !=
nullptr);
113 return extendFlowCondition(*LHS);
116 TerminatorVisitorRetTy
117 VisitConditionalOperator(
const ConditionalOperator *S) {
118 auto *Cond = S->getCond();
119 assert(Cond !=
nullptr);
120 return extendFlowCondition(*Cond);
124 TerminatorVisitorRetTy extendFlowCondition(
const Expr &Cond) {
126 if (
Env.getValueStrict(Cond) ==
nullptr)
129 auto *Val = cast_or_null<BoolValue>(
Env.getValueStrict(Cond));
134 if (Val ==
nullptr) {
135 Val = &
Env.makeAtomicBoolValue();
136 Env.setValueStrict(Cond, *Val);
139 bool ConditionValue =
true;
142 if (BlockSuccIdx == 1) {
143 Val = &
Env.makeNot(*Val);
144 ConditionValue =
false;
147 Env.addToFlowCondition(*Val);
148 return {&Cond, ConditionValue};
151 const StmtToEnvMap &StmtToEnv;
157struct AnalysisContext {
158 AnalysisContext(
const ControlFlowContext &CFCtx,
159 TypeErasedDataflowAnalysis &Analysis,
160 const Environment &InitEnv,
166 Log.beginAnalysis(CFCtx, Analysis);
168 ~AnalysisContext() {
Log.endAnalysis(); }
192static TypeErasedDataflowAnalysisState
195 Preds.insert(
Block.pred_begin(),
Block.pred_end());
196 if (
Block.getTerminator().isTemporaryDtorsBranch()) {
219 if (
Block.succ_begin()->getReachableBlock() !=
nullptr &&
220 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
221 auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
222 auto StmtBlock = StmtToBlock.find(
Block.getTerminatorStmt());
223 assert(StmtBlock != StmtToBlock.end());
224 Preds.erase(StmtBlock->getSecond());
228 std::optional<TypeErasedDataflowAnalysisState> MaybeState;
231 for (
const CFGBlock *Pred : Preds) {
233 if (!Pred || Pred->hasNoReturnElement())
238 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
239 AC.BlockStates[Pred->getBlockID()];
245 if (
const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
247 auto [Cond, CondValue] =
248 TerminatorVisitor(StmtToEnv, PredState.
Env,
250 .Visit(PredTerminatorStmt);
263 MaybeState = std::move(PredState);
279 AnalysisContext &AC) {
281 assert(S !=
nullptr);
290 assert(Init !=
nullptr);
292 auto &
Env = InputState.
Env;
293 const auto &ThisLoc =
301 auto *InitStmt = Init->getInit();
302 assert(InitStmt !=
nullptr);
304 if (
Member->getType()->isReferenceType()) {
306 if (InitStmtLoc ==
nullptr)
309 auto &MemberLoc = ThisLoc.getChild(*
Member);
312 auto &MemberLoc = ThisLoc.getChild(*
Member);
319 AnalysisContext &AC) {
352static TypeErasedDataflowAnalysisState
356 PostVisitCFG =
nullptr) {
357 AC.Log.enterBlock(
Block);
359 AC.Log.recordState(State);
360 for (
const auto &Element :
Block) {
361 AC.Log.enterElement(Element);
363 if (AC.Analysis.builtinOptions()) {
368 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
372 PostVisitCFG(Element, State);
374 AC.Log.recordState(State);
401 std::vector<std::optional<TypeErasedDataflowAnalysisState>>
BlockStates(
420 static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
421 static constexpr uint32_t AbsoluteMaxIterations = 1 << 16;
422 const uint32_t RelativeMaxIterations =
424 const uint32_t MaxIterations =
425 std::min(RelativeMaxIterations, AbsoluteMaxIterations);
426 uint32_t Iterations = 0;
428 LLVM_DEBUG(llvm::dbgs()
429 <<
"Processing Block " <<
Block->getBlockID() <<
"\n");
430 if (++Iterations > MaxIterations) {
431 return llvm::createStringError(std::errc::timed_out,
432 "maximum number of iterations reached");
435 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
440 llvm::errs() <<
"New Env:\n";
446 llvm::errs() <<
"Old Env:\n";
447 OldBlockState->Env.dump();
451 NewBlockState.
Lattice, OldBlockState->Lattice);
458 AC.Log.blockConverged();
463 OldBlockState->Env.equivalentTo(NewBlockState.
Env,
Analysis)) {
466 AC.Log.blockConverged();
474 if (
Block->hasNoReturnElement())
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
This class represents a potential adjacent block in the CFG.
Represents a single basic block in a source-level CFG.
succ_iterator succ_begin()
Stmt * getTerminatorStmt()
unsigned getBlockID() const
Represents a top-level expression in a basic block.
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Represents C++ base or member initializer from constructor's initialization list.
CXXCtorInitializer * getInitializer() const
const Stmt * getStmt() const
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Represents a C++ base or member initializer.
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
const CFGBlock * dequeue()
Represents a member of a struct/union/class.
Stmt - This represents one statement.
Holds CFG and other derived context that is needed to perform dataflow analysis.
const CFG & getCFG() const
Returns the CFG that is stored in this context.
Holds the state of the program (store and heap) at a given program point.
LatticeJoinEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
LLVM_DUMP_METHOD void dump() const
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
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.
std::enable_if_t< std::is_base_of< Value, T >::value, T & > create(Args &&...args)
Creates a T (some subclass of Value), forwarding args to the constructor, and returns a reference to ...
Models a dereferenced pointer.
Maps statements to the environments of basic blocks that contain them.
Type-erased base class for dataflow analyses built on a single lattice type.
const std::optional< DataflowAnalysisContext::Options > & builtinOptions() const
If the built-in model is enabled, returns the options to be passed to them.
virtual void transferBranchTypeErased(bool Branch, const Stmt *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.
virtual LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous)=0
Chooses a lattice element that approximates the current element at a program point,...
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &, const TypeErasedLattice &)=0
Joins two type-erased lattice elements by computing their least upper bound.
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< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
static bool isLoopHead(const CFGBlock &B)
static TypeErasedDataflowAnalysisState computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC)
Computes the input state for a given basic block by joining the output states of its predecessors.
TypeErasedDataflowAnalysisState transferBlock(const ControlFlowContext &CFCtx, llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Transfers the state of a basic block by evaluating each of its elements in the context of Analysis an...
static void builtinTransferInitializer(const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
Built-in transfer function for CFGInitializer.
static void builtinTransfer(const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)
static TypeErasedDataflowAnalysisState transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Transfers State by evaluating each element in the Block based on the AC.Analysis specified.
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.
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
static void builtinTransferStatement(const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
A worklist implementation for forward dataflow analysis.
void enqueueSuccessors(const CFGBlock *Block)
Type-erased model of the program at a given program point.
TypeErasedLattice Lattice
Type-erased model of a program property.
Environment Env
Model of the state of the program (store and heap).