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();
66class 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) {
89struct AnalysisContext {
90 AnalysisContext(
const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,
91 const Environment &InitEnv,
97 Log.beginAnalysis(ACFG, Analysis);
99 ~AnalysisContext() {
Log.endAnalysis(); }
102 const AdornedCFG &ACFG;
113class PrettyStackTraceAnalysis :
public llvm::PrettyStackTraceEntry {
115 PrettyStackTraceAnalysis(
const AdornedCFG &ACFG,
const char *Message)
116 : ACFG(ACFG), Message(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;
131class 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 ∈
158class 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) {
181 All.push_back(&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)
206 return TerminatorStmt ==
nullptr ? nullptr
207 : TerminatorVisitor().Visit(TerminatorStmt);
218static 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()) {
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);
412static 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);
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....
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 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()
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.
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...
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.
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
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 const Expr * getTerminatorCondition(const Stmt *TerminatorStmt)
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 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.
@ 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).