15 #include <system_error>
33 #include "llvm/ADT/ArrayRef.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();
66 class TerminatorVisitor
69 TerminatorVisitor() =
default;
70 const Expr *VisitIfStmt(
const IfStmt *S) {
return S->getCond(); }
71 const Expr *VisitWhileStmt(
const WhileStmt *S) {
return S->getCond(); }
72 const Expr *VisitDoStmt(
const DoStmt *S) {
return S->getCond(); }
73 const Expr *VisitForStmt(
const ForStmt *S) {
return S->getCond(); }
74 const Expr *VisitCXXForRangeStmt(
const CXXForRangeStmt *) {
79 const Expr *VisitBinaryOperator(
const BinaryOperator *S) {
80 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
83 const Expr *VisitConditionalOperator(
const ConditionalOperator *S) {
89 struct AnalysisContext {
90 AnalysisContext(
const AdornedCFG &
ACFG, TypeErasedDataflowAnalysis &
Analysis,
99 ~AnalysisContext() {
Log.endAnalysis(); }
113 class PrettyStackTraceAnalysis :
public llvm::PrettyStackTraceEntry {
115 PrettyStackTraceAnalysis(
const AdornedCFG &
ACFG,
const char *Message)
118 void print(raw_ostream &OS)
const override {
119 OS << Message <<
"\n";
121 ACFG.getDecl().dump(OS);
123 ACFG.getCFG().print(OS, LangOptions(),
false);
127 const AdornedCFG &
ACFG;
131 class PrettyStackTraceCFGElement :
public llvm::PrettyStackTraceEntry {
133 PrettyStackTraceCFGElement(
const CFGElement &Element,
int BlockIdx,
134 int ElementIdx,
const char *Message)
135 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),
138 void print(raw_ostream &OS)
const override {
139 OS << Message <<
": Element [B" << BlockIdx <<
"." << ElementIdx <<
"]\n";
140 if (
auto Stmt = Element.getAs<CFGStmt>()) {
142 ASTDumper Dumper(OS,
false);
143 Dumper.Visit(Stmt->getStmt());
148 const CFGElement ∈
158 class JoinedStateBuilder {
161 std::vector<const TypeErasedDataflowAnalysisState *>
All;
162 std::deque<TypeErasedDataflowAnalysisState> Owned;
164 TypeErasedDataflowAnalysisState
165 join(
const TypeErasedDataflowAnalysisState &L,
166 const TypeErasedDataflowAnalysisState &R) {
167 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),
172 JoinedStateBuilder(AnalysisContext &AC,
174 : AC(AC), JoinBehavior(JoinBehavior) {}
176 void addOwned(TypeErasedDataflowAnalysisState
State) {
177 Owned.push_back(std::move(
State));
178 All.push_back(&Owned.back());
180 void addUnowned(
const TypeErasedDataflowAnalysisState &
State) {
183 TypeErasedDataflowAnalysisState take() && {
188 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};
195 AC.Analysis, JoinBehavior)};
197 auto Result = join(*All[0], *All[1]);
198 for (
unsigned I = 2; I <
All.size(); ++I)
199 Result = join(Result, *All[I]);
206 return TerminatorStmt ==
nullptr ? nullptr
207 : TerminatorVisitor().Visit(TerminatorStmt);
218 static TypeErasedDataflowAnalysisState
220 std::vector<const CFGBlock *> Preds(
Block.pred_begin(),
Block.pred_end());
221 if (
Block.getTerminator().isTemporaryDtorsBranch()) {
244 if (
Block.succ_begin()->getReachableBlock() !=
nullptr &&
245 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
246 auto &StmtToBlock = AC.ACFG.getStmtToBlock();
247 auto StmtBlock = StmtToBlock.find(
Block.getTerminatorStmt());
248 assert(StmtBlock != StmtToBlock.end());
249 llvm::erase(Preds, StmtBlock->getSecond());
261 for (
const CFGBlock *Pred : Preds) {
262 if (Pred && AC.ACFG.containsExprConsumedInDifferentBlock(*Pred)) {
268 JoinedStateBuilder Builder(AC, JoinBehavior);
269 for (
const CFGBlock *Pred : Preds) {
271 if (!Pred || Pred->hasNoReturnElement())
276 const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
277 AC.BlockStates[Pred->getBlockID()];
283 if (Cond ==
nullptr) {
284 Builder.addUnowned(PredState);
293 if (AC.Analysis.builtinOptions()) {
299 assert(CondVal !=
nullptr);
301 BranchVal ? CondVal : &
Copy.Env.makeNot(*CondVal);
304 AC.Analysis.transferBranchTypeErased(BranchVal, Cond,
Copy.Lattice,
306 Builder.addOwned(std::move(
Copy));
308 return std::move(Builder).take();
315 AnalysisContext &AC) {
317 assert(S !=
nullptr);
319 InputState.
Env, AC.Analysis);
327 assert(Init !=
nullptr);
329 auto &
Env = InputState.
Env;
332 if (!Init->isAnyMemberInitializer())
336 auto *InitExpr = Init->getInit();
337 assert(InitExpr !=
nullptr);
342 if (Init->isMemberInitializer()) {
343 Member = Init->getMember();
344 MemberLoc = ThisLoc.getChild(*
Member);
347 assert(IndirectField !=
nullptr);
348 MemberLoc = &ThisLoc;
349 for (
const auto *I : IndirectField->
chain()) {
350 Member = cast<FieldDecl>(I);
351 ParentLoc = cast<RecordStorageLocation>(MemberLoc);
355 assert(
Member !=
nullptr);
364 if (
Member->getType()->isReferenceType()) {
366 if (InitExprLoc ==
nullptr)
372 }
else if (!
Member->getType()->isRecordType()) {
373 assert(MemberLoc !=
nullptr);
381 AnalysisContext &AC) {
396 State.Env.removeDecl(*VD);
412 static TypeErasedDataflowAnalysisState
416 PostVisitCFG =
nullptr) {
417 AC.Log.enterBlock(
Block, PostVisitCFG !=
nullptr);
419 AC.Log.recordState(
State);
421 for (
const auto &Element :
Block) {
422 PrettyStackTraceCFGElement CrashInfo(Element,
Block.getBlockID(),
423 ElementIdx++,
"transferCFGBlock");
425 AC.Log.enterElement(Element);
427 if (AC.Analysis.builtinOptions()) {
432 AC.Analysis.transferTypeErased(Element,
State.Lattice,
State.Env);
436 PostVisitCFG(Element,
State);
438 AC.Log.recordState(
State);
446 if (
const Expr *TerminatorCond =
447 dyn_cast_or_null<Expr>(
Block.getTerminatorCondition())) {
448 if (
State.Env.getValue(*TerminatorCond) ==
nullptr)
455 *TerminatorCond,
State.Env, AC.Analysis);
460 if (
State.Env.getValue(*TerminatorCond) ==
nullptr)
461 State.Env.setValue(*TerminatorCond,
State.Env.makeAtomicBoolValue());
462 AC.Log.recordState(
State);
475 std::int32_t MaxBlockVisits) {
476 PrettyStackTraceAnalysis CrashInfo(
ACFG,
"runTypeErasedDataflowAnalysis");
478 std::optional<Environment> MaybeStartingEnv;
484 MaybeStartingEnv ? *MaybeStartingEnv :
InitEnv;
490 std::vector<std::optional<TypeErasedDataflowAnalysisState>>
BlockStates(
500 std::int32_t BlockVisits = 0;
502 LLVM_DEBUG(llvm::dbgs()
503 <<
"Processing Block " <<
Block->getBlockID() <<
"\n");
504 if (++BlockVisits > MaxBlockVisits) {
505 return llvm::createStringError(std::errc::timed_out,
506 "maximum number of blocks processed");
509 const std::optional<TypeErasedDataflowAnalysisState> &OldBlockState =
514 llvm::errs() <<
"New Env:\n";
520 llvm::errs() <<
"Old Env:\n";
521 OldBlockState->Env.dump();
525 NewBlockState.
Lattice, OldBlockState->Lattice);
528 if (Effect1 == LatticeJoinEffect::Unchanged &&
529 Effect2 == LatticeJoinEffect::Unchanged) {
532 AC.Log.blockConverged();
537 OldBlockState->Env.equivalentTo(NewBlockState.
Env,
Analysis)) {
540 AC.Log.blockConverged();
548 if (
Block->hasNoReturnElement())
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
void print(llvm::raw_ostream &OS, const Pointer &P, ASTContext &Ctx, QualType Ty)
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
const AdornedCFG & ACFG
Contains the CFG being analyzed.
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()
This represents one expression.
Represents a member of a struct/union/class.
IfStmt - This represents an if/then/else.
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 with additional information derived from it that is needed to perform dataflow analysis.
const CFG & getCFG() const
Returns the CFG that is stored in this context.
const Formula & formula() const
Holds the state of the program (store and heap) at a given program point.
LatticeEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
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...
ExprJoinBehavior
How to treat expression state (ExprToLoc and ExprToVal) in a join.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model, ExprJoinBehavior ExprBehavior)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
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, not counting the initial analysis target.
RecordStorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
void initialize()
Assigns storage locations and values to all parameters, captures, global variables,...
A storage location for a record (struct, class, or union).
void setChild(const ValueDecl &D, StorageLocation *Loc)
Changes the child storage location for a field D of reference type.
StorageLocation * getChild(const ValueDecl &D) const
Returns the child storage location for D.
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
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, Environment::ValueModel &Model)
Evaluates S and updates Env accordingly.
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 builtinTransfer(unsigned CurBlockID, const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)
static void builtinTransferInitializer(const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
Built-in transfer function for CFGInitializer.
llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG, std::int32_t MaxBlockVisits)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
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.
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)
static const Expr * getTerminatorCondition(const Stmt *TerminatorStmt)
static void builtinTransferStatement(unsigned CurBlockID, const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
LatticeEffect
Effect indicating whether a lattice operation resulted in a new value.
The JSON file list parser is used to communicate input to InstallAPI.
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).