16#include <system_error>
34#include "llvm/ADT/ArrayRef.h"
35#include "llvm/ADT/STLExtras.h"
36#include "llvm/ADT/SmallBitVector.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Support/Error.h"
40#define DEBUG_TYPE "clang-dataflow"
48 auto BlockPos = llvm::find_if(
50 return Succ && Succ->getBlockID() == Block.getBlockID();
71using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
75class TerminatorVisitor
78 TerminatorVisitor(
const StmtToEnvMap &StmtToEnv, Environment &Env,
80 : StmtToEnv(StmtToEnv),
Env(
Env), BlockSuccIdx(BlockSuccIdx) {}
82 TerminatorVisitorRetTy VisitIfStmt(
const IfStmt *S) {
83 auto *Cond = S->getCond();
84 assert(Cond !=
nullptr);
85 return extendFlowCondition(*Cond);
88 TerminatorVisitorRetTy VisitWhileStmt(
const WhileStmt *S) {
89 auto *Cond = S->getCond();
90 assert(Cond !=
nullptr);
91 return extendFlowCondition(*Cond);
94 TerminatorVisitorRetTy VisitDoStmt(
const DoStmt *S) {
95 auto *Cond = S->getCond();
96 assert(Cond !=
nullptr);
97 return extendFlowCondition(*Cond);
100 TerminatorVisitorRetTy VisitForStmt(
const ForStmt *S) {
101 auto *Cond = S->getCond();
103 return extendFlowCondition(*Cond);
104 return {
nullptr,
false};
107 TerminatorVisitorRetTy VisitCXXForRangeStmt(
const CXXForRangeStmt *) {
110 return {
nullptr,
false};
113 TerminatorVisitorRetTy VisitBinaryOperator(
const BinaryOperator *S) {
114 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
115 auto *LHS = S->getLHS();
116 assert(LHS !=
nullptr);
117 return extendFlowCondition(*LHS);
120 TerminatorVisitorRetTy
121 VisitConditionalOperator(
const ConditionalOperator *S) {
122 auto *Cond = S->getCond();
123 assert(Cond !=
nullptr);
124 return extendFlowCondition(*Cond);
128 TerminatorVisitorRetTy extendFlowCondition(
const Expr &Cond) {
130 if (
Env.getValue(Cond) ==
nullptr)
133 auto *Val = cast_or_null<BoolValue>(
Env.getValue(Cond));
138 if (Val ==
nullptr) {
139 Val = &
Env.makeAtomicBoolValue();
140 Env.setValue(Cond, *Val);
143 bool ConditionValue =
true;
146 if (BlockSuccIdx == 1) {
147 Val = &
Env.makeNot(*Val);
148 ConditionValue =
false;
151 Env.assume(Val->formula());
152 return {&Cond, ConditionValue};
155 const StmtToEnvMap &StmtToEnv;
161struct AnalysisContext {
162 AnalysisContext(
const ControlFlowContext &CFCtx,
163 TypeErasedDataflowAnalysis &Analysis,
164 const Environment &InitEnv,
170 Log.beginAnalysis(CFCtx, Analysis);
172 ~AnalysisContext() {
Log.endAnalysis(); }
186class PrettyStackTraceAnalysis :
public llvm::PrettyStackTraceEntry {
188 PrettyStackTraceAnalysis(
const ControlFlowContext &
CFCtx,
const char *Message)
191 void print(raw_ostream &OS)
const override {
192 OS << Message <<
"\n";
194 CFCtx.getDecl().dump(OS);
196 CFCtx.getCFG().print(OS, LangOptions(),
false);
200 const ControlFlowContext &
CFCtx;
204class PrettyStackTraceCFGElement :
public llvm::PrettyStackTraceEntry {
206 PrettyStackTraceCFGElement(
const CFGElement &Element,
int BlockIdx,
207 int ElementIdx,
const char *Message)
208 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
211 void print(raw_ostream &OS)
const override {
212 OS << Message <<
": Element [B" << BlockIdx <<
"." << ElementIdx <<
"]\n";
213 if (
auto Stmt = Element.getAs<CFGStmt>()) {
215 ASTDumper Dumper(OS,
false);
216 Dumper.Visit(Stmt->getStmt());
221 const CFGElement ∈
231class JoinedStateBuilder {
233 std::vector<const TypeErasedDataflowAnalysisState *>
All;
234 std::deque<TypeErasedDataflowAnalysisState> Owned;
236 TypeErasedDataflowAnalysisState
237 join(
const TypeErasedDataflowAnalysisState &L,
238 const TypeErasedDataflowAnalysisState &R) {
239 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
244 JoinedStateBuilder(AnalysisContext &AC) : AC(AC) {}
246 void addOwned(TypeErasedDataflowAnalysisState State) {
247 Owned.push_back(std::move(State));
248 All.push_back(&Owned.back());
250 void addUnowned(
const TypeErasedDataflowAnalysisState &State) {
251 All.push_back(&State);
253 TypeErasedDataflowAnalysisState take() && {
258 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
264 return {
All[0]->Lattice,
267 auto Result = join(*All[0], *All[1]);
268 for (
unsigned I = 2; I <
All.size(); ++I)
284static TypeErasedDataflowAnalysisState
286 std::vector<const CFGBlock *> Preds(
Block.pred_begin(),
Block.pred_end());
287 if (
Block.getTerminator().isTemporaryDtorsBranch()) {
310 if (
Block.succ_begin()->getReachableBlock() !=
nullptr &&
311 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
312 auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
313 auto StmtBlock = StmtToBlock.find(
Block.getTerminatorStmt());
314 assert(StmtBlock != StmtToBlock.end());
315 llvm::erase(Preds, StmtBlock->getSecond());
319 JoinedStateBuilder Builder(AC);
320 for (
const CFGBlock *Pred : Preds) {
322 if (!Pred || Pred->hasNoReturnElement())
327 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
328 AC.BlockStates[Pred->getBlockID()];
332 if (AC.Analysis.builtinOptions()) {
333 if (
const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
339 auto [Cond, CondValue] =
340 TerminatorVisitor(StmtToEnv,
Copy.Env,
342 .Visit(PredTerminatorStmt);
346 AC.Analysis.transferBranchTypeErased(CondValue, Cond,
Copy.Lattice,
348 Builder.addOwned(std::move(
Copy));
352 Builder.addUnowned(*MaybePredState);
354 return std::move(Builder).take();
361 AnalysisContext &AC) {
363 assert(S !=
nullptr);
372 assert(
Init !=
nullptr);
374 auto &
Env = InputState.
Env;
377 if (!
Init->isAnyMemberInitializer())
381 auto *InitExpr =
Init->getInit();
382 assert(InitExpr !=
nullptr);
387 if (
Init->isMemberInitializer()) {
389 MemberLoc = ThisLoc.getChild(*
Member);
392 assert(IndirectField !=
nullptr);
393 MemberLoc = &ThisLoc;
394 for (
const auto *I : IndirectField->
chain()) {
395 Member = cast<FieldDecl>(I);
396 ParentLoc = cast<RecordStorageLocation>(MemberLoc);
400 assert(
Member !=
nullptr);
401 assert(MemberLoc !=
nullptr);
410 if (
Member->getType()->isReferenceType()) {
412 if (InitExprLoc ==
nullptr)
416 }
else if (
auto *InitExprVal =
Env.
getValue(*InitExpr)) {
417 if (
Member->getType()->isRecordType()) {
418 auto *InitValStruct = cast<RecordValue>(InitExprVal);
424 *cast<RecordStorageLocation>(MemberLoc),
Env);
433 AnalysisContext &AC) {
448 State.Env.removeDecl(*VD);
464static TypeErasedDataflowAnalysisState
468 PostVisitCFG =
nullptr) {
469 AC.Log.enterBlock(
Block, PostVisitCFG !=
nullptr);
471 AC.Log.recordState(State);
473 for (
const auto &Element :
Block) {
474 PrettyStackTraceCFGElement CrashInfo(Element,
Block.getBlockID(),
475 ElementIdx++,
"transferCFGBlock");
477 AC.Log.enterElement(Element);
479 if (AC.Analysis.builtinOptions()) {
484 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);
488 PostVisitCFG(Element, State);
490 AC.Log.recordState(State);
502 PrettyStackTraceAnalysis CrashInfo(
CFCtx,
"runTypeErasedDataflowAnalysis");
504 std::optional<Environment> MaybeStartingEnv;
510 MaybeStartingEnv ? *MaybeStartingEnv :
InitEnv;
516 std::vector<std::optional<TypeErasedDataflowAnalysisState>>
BlockStates(
535 static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
536 static constexpr uint32_t AbsoluteMaxIterations = 1 << 16;
537 const uint32_t RelativeMaxIterations =
539 const uint32_t MaxIterations =
540 std::min(RelativeMaxIterations, AbsoluteMaxIterations);
541 uint32_t Iterations = 0;
543 LLVM_DEBUG(llvm::dbgs()
544 <<
"Processing Block " <<
Block->getBlockID() <<
"\n");
545 if (++Iterations > MaxIterations) {
546 return llvm::createStringError(std::errc::timed_out,
547 "maximum number of iterations reached");
550 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
555 llvm::errs() <<
"New Env:\n";
561 llvm::errs() <<
"Old Env:\n";
562 OldBlockState->Env.dump();
566 NewBlockState.
Lattice, OldBlockState->Lattice);
573 AC.Log.blockConverged();
578 OldBlockState->Env.equivalentTo(NewBlockState.
Env,
Analysis)) {
581 AC.Log.blockConverged();
589 if (
Block->hasNoReturnElement())
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
static void print(llvm::raw_ostream &OS, const T &V, ASTContext &, QualType)
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()
const Stmt * getLoopTarget() const
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
Represents the point where the lifetime of an automatic object ends.
const VarDecl * getVarDecl() const
const Stmt * getStmt() const
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
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.
Represents a field injected from an anonymous union/struct into the parent scope.
ArrayRef< NamedDecl * > chain() const
Stmt - This represents one statement.
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
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.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
LatticeJoinEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
RecordStorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
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 ...
LLVM_DUMP_METHOD void dump() const
Environment fork() const
Returns a new environment that is a copy of this one.
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 setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
size_t callStackSize() const
Returns the size of the call stack.
void initialize()
Assigns storage locations and values to all parameters, captures, global variables,...
A storage location for a record (struct, class, or union).
StorageLocation * getChild(const ValueDecl &D) const
Returns the child storage location for D.
void setChild(const ValueDecl &D, StorageLocation *Loc)
Changes the child storage location for a field D of reference type.
Maps statements to the environments of basic blocks that contain them.
Base class for elements of the local variable store and of the heap.
Type-erased base class for dataflow analyses built on a single lattice type.
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 bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
constexpr XRayInstrMask All
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 TypeErasedDataflowAnalysisState computeBlockInputState(const CFGBlock &Block, AnalysisContext &AC)
Computes the input state for a given basic block by joining the output states of its predecessors.
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.
static bool isBackedgeNode(const CFGBlock &B)
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
void copyRecord(RecordStorageLocation &Src, RecordStorageLocation &Dst, Environment &Env)
Copies a record (struct, class, or union) from Src to Dst.
static void builtinTransferStatement(const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
@ Result
The result type of a method or function.
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).