clang  16.0.0git
TypeErasedDataflowAnalysis.cpp
Go to the documentation of this file.
1 //===- TypeErasedDataflowAnalysis.cpp -------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines type-erased base types and functions for building dataflow
10 // analyses that run over Control-Flow Graphs (CFGs).
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include <algorithm>
15 #include <memory>
16 #include <system_error>
17 #include <utility>
18 #include <vector>
19 
20 #include "clang/AST/DeclCXX.h"
22 #include "clang/AST/StmtVisitor.h"
24 #include "clang/Analysis/CFG.h"
30 #include "llvm/ADT/ArrayRef.h"
31 #include "llvm/ADT/DenseSet.h"
32 #include "llvm/ADT/None.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/Support/Error.h"
36 #include "llvm/Support/ErrorHandling.h"
37 
38 namespace clang {
39 namespace dataflow {
40 
42 public:
44  const ControlFlowContext &CFCtx,
46  BlockToState)
47  : CFCtx(CFCtx), BlockToState(BlockToState) {}
48 
49  const Environment *getEnvironment(const Stmt &S) const override {
50  auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
51  assert(BlockIt != CFCtx.getStmtToBlock().end());
52  const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
53  assert(State);
54  return &State.value().Env;
55  }
56 
57 private:
58  const ControlFlowContext &CFCtx;
60 };
61 
62 /// Returns the index of `Block` in the successors of `Pred`.
63 static int blockIndexInPredecessor(const CFGBlock &Pred,
64  const CFGBlock &Block) {
65  auto BlockPos = llvm::find_if(
66  Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
67  return Succ && Succ->getBlockID() == Block.getBlockID();
68  });
69  return BlockPos - Pred.succ_begin();
70 }
71 
72 /// Extends the flow condition of an environment based on a terminator
73 /// statement.
74 class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
75 public:
76  TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
77  int BlockSuccIdx, TransferOptions TransferOpts)
78  : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx),
79  TransferOpts(TransferOpts) {}
80 
81  void VisitIfStmt(const IfStmt *S) {
82  auto *Cond = S->getCond();
83  assert(Cond != nullptr);
84  extendFlowCondition(*Cond);
85  }
86 
87  void VisitWhileStmt(const WhileStmt *S) {
88  auto *Cond = S->getCond();
89  assert(Cond != nullptr);
90  extendFlowCondition(*Cond);
91  }
92 
93  void VisitDoStmt(const DoStmt *S) {
94  auto *Cond = S->getCond();
95  assert(Cond != nullptr);
96  extendFlowCondition(*Cond);
97  }
98 
99  void VisitForStmt(const ForStmt *S) {
100  auto *Cond = S->getCond();
101  if (Cond != nullptr)
102  extendFlowCondition(*Cond);
103  }
104 
106  assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
107  auto *LHS = S->getLHS();
108  assert(LHS != nullptr);
109  extendFlowCondition(*LHS);
110  }
111 
113  auto *Cond = S->getCond();
114  assert(Cond != nullptr);
115  extendFlowCondition(*Cond);
116  }
117 
118 private:
119  void extendFlowCondition(const Expr &Cond) {
120  // The terminator sub-expression might not be evaluated.
121  if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr)
122  transfer(StmtToEnv, Cond, Env, TransferOpts);
123 
124  // FIXME: The flow condition must be an r-value, so `SkipPast::None` should
125  // suffice.
126  auto *Val =
127  cast_or_null<BoolValue>(Env.getValue(Cond, SkipPast::Reference));
128  // Value merging depends on flow conditions from different environments
129  // being mutually exclusive -- that is, they cannot both be true in their
130  // entirety (even if they may share some clauses). So, we need *some* value
131  // for the condition expression, even if just an atom.
132  if (Val == nullptr) {
133  // FIXME: Consider introducing a helper for this get-or-create pattern.
134  auto *Loc = Env.getStorageLocation(Cond, SkipPast::None);
135  if (Loc == nullptr) {
136  Loc = &Env.createStorageLocation(Cond);
137  Env.setStorageLocation(Cond, *Loc);
138  }
139  Val = &Env.makeAtomicBoolValue();
140  Env.setValue(*Loc, *Val);
141  }
142 
143  // The condition must be inverted for the successor that encompasses the
144  // "else" branch, if such exists.
145  if (BlockSuccIdx == 1)
146  Val = &Env.makeNot(*Val);
147 
148  Env.addToFlowCondition(*Val);
149  }
150 
151  const StmtToEnvMap &StmtToEnv;
152  Environment &Env;
153  int BlockSuccIdx;
154  TransferOptions TransferOpts;
155 };
156 
157 /// Holds data structures required for running dataflow analysis.
161  const Environment &InitEnv,
163  BlockStates)
166 
167  /// Contains the CFG being analyzed.
169  /// The analysis to be run.
171  /// Initial state to start the analysis.
173  /// Stores the state of a CFG block if it has been evaluated by the analysis.
174  /// The indices correspond to the block IDs.
176 };
177 
178 /// Computes the input state for a given basic block by joining the output
179 /// states of its predecessors.
180 ///
181 /// Requirements:
182 ///
183 /// All predecessors of `Block` except those with loop back edges must have
184 /// already been transferred. States in `AC.BlockStates` that are set to
185 /// `llvm::None` represent basic blocks that are not evaluated yet.
189  Preds.insert(Block.pred_begin(), Block.pred_end());
190  if (Block.getTerminator().isTemporaryDtorsBranch()) {
191  // This handles a special case where the code that produced the CFG includes
192  // a conditional operator with a branch that constructs a temporary and
193  // calls a destructor annotated as noreturn. The CFG models this as follows:
194  //
195  // B1 (contains the condition of the conditional operator) - succs: B2, B3
196  // B2 (contains code that does not call a noreturn destructor) - succs: B4
197  // B3 (contains code that calls a noreturn destructor) - succs: B4
198  // B4 (has temporary destructor terminator) - succs: B5, B6
199  // B5 (noreturn block that is associated with the noreturn destructor call)
200  // B6 (contains code that follows the conditional operator statement)
201  //
202  // The first successor (B5 above) of a basic block with a temporary
203  // destructor terminator (B4 above) is the block that evaluates the
204  // destructor. If that block has a noreturn element then the predecessor
205  // block that constructed the temporary object (B3 above) is effectively a
206  // noreturn block and its state should not be used as input for the state
207  // of the block that has a temporary destructor terminator (B4 above). This
208  // holds regardless of which branch of the ternary operator calls the
209  // noreturn destructor. However, it doesn't cases where a nested ternary
210  // operator includes a branch that contains a noreturn destructor call.
211  //
212  // See `NoreturnDestructorTest` for concrete examples.
213  if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
214  auto &StmtToBlock = AC.CFCtx.getStmtToBlock();
215  auto StmtBlock = StmtToBlock.find(Block.getTerminatorStmt());
216  assert(StmtBlock != StmtToBlock.end());
217  Preds.erase(StmtBlock->getSecond());
218  }
219  }
220 
222 
223  auto &Analysis = AC.Analysis;
224  auto BuiltinTransferOpts = Analysis.builtinTransferOptions();
225 
226  for (const CFGBlock *Pred : Preds) {
227  // Skip if the `Block` is unreachable or control flow cannot get past it.
228  if (!Pred || Pred->hasNoReturnElement())
229  continue;
230 
231  // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
232  // loop back edge to `Block`.
234  AC.BlockStates[Pred->getBlockID()];
235  if (!MaybePredState)
236  continue;
237 
238  TypeErasedDataflowAnalysisState PredState = MaybePredState.value();
239  if (BuiltinTransferOpts) {
240  if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
241  const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates);
242  TerminatorVisitor(StmtToEnv, PredState.Env,
244  *BuiltinTransferOpts)
245  .Visit(PredTerminatorStmt);
246  }
247  }
248 
249  if (MaybeState) {
250  Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
251  MaybeState->Env.join(PredState.Env, Analysis);
252  } else {
253  MaybeState = std::move(PredState);
254  }
255  }
256  if (!MaybeState) {
257  // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
258  // to enable building analyses like computation of dominators that
259  // initialize the state of each basic block differently.
260  MaybeState.emplace(Analysis.typeErasedInitialElement(), AC.InitEnv);
261  }
262  return *MaybeState;
263 }
264 
265 /// Built-in transfer function for `CFGStmt`.
268  AnalysisContext &AC) {
269  const Stmt *S = Elt.getStmt();
270  assert(S != nullptr);
271  transfer(StmtToEnvMapImpl(AC.CFCtx, AC.BlockStates), *S, InputState.Env,
273 }
274 
275 /// Built-in transfer function for `CFGInitializer`.
277  TypeErasedDataflowAnalysisState &InputState) {
278  const CXXCtorInitializer *Init = Elt.getInitializer();
279  assert(Init != nullptr);
280 
281  auto &Env = InputState.Env;
282  const auto &ThisLoc =
283  *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
284 
285  const FieldDecl *Member = Init->getMember();
286  if (Member == nullptr)
287  // Not a field initializer.
288  return;
289 
290  auto *InitStmt = Init->getInit();
291  assert(InitStmt != nullptr);
292 
293  auto *InitStmtLoc = Env.getStorageLocation(*InitStmt, SkipPast::Reference);
294  if (InitStmtLoc == nullptr)
295  return;
296 
297  auto *InitStmtVal = Env.getValue(*InitStmtLoc);
298  if (InitStmtVal == nullptr)
299  return;
300 
301  if (Member->getType()->isReferenceType()) {
302  auto &MemberLoc = ThisLoc.getChild(*Member);
303  Env.setValue(MemberLoc, Env.takeOwnership(std::make_unique<ReferenceValue>(
304  *InitStmtLoc)));
305  } else {
306  auto &MemberLoc = ThisLoc.getChild(*Member);
307  Env.setValue(MemberLoc, *InitStmtVal);
308  }
309 }
310 
311 void builtinTransfer(const CFGElement &Elt,
313  AnalysisContext &AC) {
314  switch (Elt.getKind()) {
315  case CFGElement::Statement: {
317  break;
318  }
321  break;
322  }
323  default:
324  // FIXME: Evaluate other kinds of `CFGElement`.
325  break;
326  }
327 }
328 
329 /// Transfers `State` by evaluating each element in the `Block` based on the
330 /// `AC.Analysis` specified.
331 ///
332 /// Built-in transfer functions (if the option for `ApplyBuiltinTransfer` is set
333 /// by the analysis) will be applied to the element before evaluation by the
334 /// user-specified analysis.
335 /// `PostVisitCFG` (if provided) will be applied to the element after evaluation
336 /// by the user-specified analysis.
337 TypeErasedDataflowAnalysisState
339  std::function<void(const CFGElement &,
341  PostVisitCFG = nullptr) {
342  auto State = computeBlockInputState(Block, AC);
343  for (const auto &Element : Block) {
344  // Built-in analysis
345  if (AC.Analysis.builtinTransferOptions()) {
346  builtinTransfer(Element, State, AC);
347  }
348 
349  // User-provided analysis
350  AC.Analysis.transferTypeErased(&Element, State.Lattice, State.Env);
351 
352  // Post processing
353  if (PostVisitCFG) {
354  PostVisitCFG(Element, State);
355  }
356  }
357  return State;
358 }
359 
361  const ControlFlowContext &CFCtx,
363  const CFGBlock &Block, const Environment &InitEnv,
364  TypeErasedDataflowAnalysis &Analysis,
365  std::function<void(const CFGElement &,
367  PostVisitCFG) {
368  AnalysisContext AC(CFCtx, Analysis, InitEnv, BlockStates);
369  return transferCFGBlock(Block, AC, PostVisitCFG);
370 }
371 
374  const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
375  const Environment &InitEnv,
376  std::function<void(const CFGElement &,
378  PostVisitCFG) {
379  PostOrderCFGView POV(&CFCtx.getCFG());
380  ForwardDataflowWorklist Worklist(CFCtx.getCFG(), &POV);
381 
382  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates(
383  CFCtx.getCFG().size(), llvm::None);
384 
385  // The entry basic block doesn't contain statements so it can be skipped.
386  const CFGBlock &Entry = CFCtx.getCFG().getEntry();
387  BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
388  InitEnv};
389  Worklist.enqueueSuccessors(&Entry);
390 
391  AnalysisContext AC(CFCtx, Analysis, InitEnv, BlockStates);
392 
393  // Bugs in lattices and transfer functions can prevent the analysis from
394  // converging. To limit the damage (infinite loops) that these bugs can cause,
395  // limit the number of iterations.
396  // FIXME: Consider making the maximum number of iterations configurable.
397  // FIXME: Consider restricting the number of backedges followed, rather than
398  // iterations.
399  // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
400  // of iterations, number of functions that time out, etc.
401  static constexpr uint32_t MaxAverageVisitsPerBlock = 4;
402  static constexpr uint32_t AbsoluteMaxIterations = 1 << 16;
403  const uint32_t RelativeMaxIterations =
404  MaxAverageVisitsPerBlock * BlockStates.size();
405  const uint32_t MaxIterations =
406  std::min(RelativeMaxIterations, AbsoluteMaxIterations);
407  uint32_t Iterations = 0;
408  while (const CFGBlock *Block = Worklist.dequeue()) {
409  if (++Iterations > MaxIterations) {
410  return llvm::createStringError(std::errc::timed_out,
411  "maximum number of iterations reached");
412  }
413 
415  BlockStates[Block->getBlockID()];
416  TypeErasedDataflowAnalysisState NewBlockState =
417  transferCFGBlock(*Block, AC);
418 
419  if (OldBlockState &&
420  Analysis.isEqualTypeErased(OldBlockState.value().Lattice,
421  NewBlockState.Lattice) &&
422  OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {
423  // The state of `Block` didn't change after transfer so there's no need to
424  // revisit its successors.
425  continue;
426  }
427 
428  BlockStates[Block->getBlockID()] = std::move(NewBlockState);
429 
430  // Do not add unreachable successor blocks to `Worklist`.
431  if (Block->hasNoReturnElement())
432  continue;
433 
434  Worklist.enqueueSuccessors(Block);
435  }
436  // FIXME: Consider evaluating unreachable basic blocks (those that have a
437  // state set to `llvm::None` at this point) to also analyze dead code.
438 
439  if (PostVisitCFG) {
440  for (const CFGBlock *Block : CFCtx.getCFG()) {
441  // Skip blocks that were not evaluated.
442  if (!BlockStates[Block->getBlockID()])
443  continue;
444  transferCFGBlock(*Block, AC, PostVisitCFG);
445  }
446  }
447 
448  return BlockStates;
449 }
450 
451 } // namespace dataflow
452 } // namespace clang
TypeErasedDataflowAnalysis.h
clang::dataflow::StmtToEnvMapImpl::getEnvironment
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.
Definition: TypeErasedDataflowAnalysis.cpp:49
clang::WhileStmt
WhileStmt - This represents a 'while' stmt.
Definition: Stmt.h:2373
clang::CFGBlock::succ_begin
succ_iterator succ_begin()
Definition: CFG.h:956
clang::CFGBlock::getBlockID
unsigned getBlockID() const
Definition: CFG.h:1075
clang::dataflow::blockIndexInPredecessor
static int blockIndexInPredecessor(const CFGBlock &Pred, const CFGBlock &Block)
Returns the index of Block in the successors of Pred.
Definition: TypeErasedDataflowAnalysis.cpp:63
clang::dataflow::transferCFGBlock
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.
Definition: TypeErasedDataflowAnalysis.cpp:338
clang::FieldDecl
Represents a member of a struct/union/class.
Definition: Decl.h:2878
clang::dataflow::builtinTransferStatement
void builtinTransferStatement(const CFGStmt &Elt, TypeErasedDataflowAnalysisState &InputState, AnalysisContext &AC)
Built-in transfer function for CFGStmt.
Definition: TypeErasedDataflowAnalysis.cpp:266
DeclCXX.h
clang::dataflow::StmtToEnvMapImpl::StmtToEnvMapImpl
StmtToEnvMapImpl(const ControlFlowContext &CFCtx, llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState >> BlockToState)
Definition: TypeErasedDataflowAnalysis.cpp:43
clang::dataflow::Environment::createStorageLocation
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
Definition: DataflowEnvironment.cpp:388
clang::dataflow::TypeErasedDataflowAnalysisState::Lattice
TypeErasedLattice Lattice
Type-erased model of a program property.
Definition: TypeErasedDataflowAnalysis.h:98
clang::IfStmt
IfStmt - This represents an if/then/else.
Definition: Stmt.h:1936
PostOrderCFGView.h
clang::dataflow::SkipPast::Reference
@ Reference
An optional reference should be skipped past.
llvm::Optional
Definition: LLVM.h:40
clang::dataflow::TypeErasedDataflowAnalysis::transferTypeErased
virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given control flow graph element and type-erased lattice...
clang::dataflow::ControlFlowContext::getStmtToBlock
const llvm::DenseMap< const Stmt *, const CFGBlock * > & getStmtToBlock() const
Returns a mapping from statements to basic blocks that contain them.
Definition: ControlFlowContext.h:50
clang::dataflow::TerminatorVisitor::VisitWhileStmt
void VisitWhileStmt(const WhileStmt *S)
Definition: TypeErasedDataflowAnalysis.cpp:87
llvm::Expected
Definition: LLVM.h:41
clang::CFG::size
unsigned size() const
Return the total number of CFGBlocks within the CFG This is simply a renaming of the getNumBlockIDs()...
Definition: CFG.h:1417
clang::dataflow::TerminatorVisitor::VisitBinaryOperator
void VisitBinaryOperator(const BinaryOperator *S)
Definition: TypeErasedDataflowAnalysis.cpp:105
clang::dataflow::Environment::addToFlowCondition
void addToFlowCondition(BoolValue &Val)
Adds Val to the set of clauses that constitute the flow condition.
Definition: DataflowEnvironment.cpp:610
clang::dataflow::Environment::setStorageLocation
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
Definition: DataflowEnvironment.cpp:406
clang::ConditionalOperator
ConditionalOperator - The ?: ternary operator.
Definition: Expr.h:4141
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:577
clang::CFGBlock::succs
succ_range succs()
Definition: CFG.h:966
min
__DEVICE__ int min(int __a, int __b)
Definition: __clang_cuda_math.h:197
clang::dataflow::StmtToEnvMapImpl
Definition: TypeErasedDataflowAnalysis.cpp:41
clang::dataflow::TerminatorVisitor
Extends the flow condition of an environment based on a terminator statement.
Definition: TypeErasedDataflowAnalysis.cpp:74
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3803
clang::dataflow::transferBlock
TypeErasedDataflowAnalysisState transferBlock(const ControlFlowContext &CFCtx, llvm::ArrayRef< llvm::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...
Definition: TypeErasedDataflowAnalysis.cpp:360
clang::dataflow::StmtToEnvMap
Maps statements to the environments of basic blocks that contain them.
Definition: Transfer.h:39
clang::dataflow::AnalysisContext::CFCtx
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
Definition: TypeErasedDataflowAnalysis.cpp:168
clang::dataflow::builtinTransferInitializer
void builtinTransferInitializer(const CFGInitializer &Elt, TypeErasedDataflowAnalysisState &InputState)
Built-in transfer function for CFGInitializer.
Definition: TypeErasedDataflowAnalysis.cpp:276
clang::DeclaratorContext::Member
@ Member
clang::dataflow::SkipPast::None
@ None
No indirections should be skipped past.
clang::dataflow::AnalysisContext
Holds data structures required for running dataflow analysis.
Definition: TypeErasedDataflowAnalysis.cpp:158
clang::CFGInitializer::getInitializer
CXXCtorInitializer * getInitializer() const
Definition: CFG.h:231
clang::dataflow::Environment::setValue
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
Definition: DataflowEnvironment.cpp:442
clang::dataflow::ignoreCFGOmittedNodes
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
Definition: DataflowAnalysisContext.cpp:363
clang::ForStmt
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Definition: Stmt.h:2566
clang::StmtVisitorBase::Visit
RetTy Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:43
clang::CFGElement::Initializer
@ Initializer
Definition: CFG.h:59
llvm::DenseSet
Definition: Sema.h:77
OperationKinds.h
DataflowWorklist.h
clang::dataflow::TerminatorVisitor::VisitDoStmt
void VisitDoStmt(const DoStmt *S)
Definition: TypeErasedDataflowAnalysis.cpp:93
clang::PostOrderCFGView
Definition: PostOrderCFGView.h:28
clang::dataflow::AnalysisContext::InitEnv
const Environment & InitEnv
Initial state to start the analysis.
Definition: TypeErasedDataflowAnalysis.cpp:172
clang::dataflow::computeBlockInputState
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.
Definition: TypeErasedDataflowAnalysis.cpp:187
clang::CFGElement::Statement
@ Statement
Definition: CFG.h:66
clang::dataflow::TypeErasedDataflowAnalysis::typeErasedInitialElement
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
clang::CFGStmt
Definition: CFG.h:132
clang::ForwardDataflowWorklist
A worklist implementation for forward dataflow analysis.
Definition: DataflowWorklist.h:62
clang::CFGElement::castAs
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type.
Definition: CFG.h:98
clang::dataflow::Environment::getValue
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...
Definition: DataflowEnvironment.cpp:475
clang::CFGInitializer
Represents C++ base or member initializer from constructor's initialization list.
Definition: CFG.h:226
clang::dataflow::TerminatorVisitor::VisitConditionalOperator
void VisitConditionalOperator(const ConditionalOperator *S)
Definition: TypeErasedDataflowAnalysis.cpp:112
llvm::ArrayRef
Definition: LLVM.h:34
clang::dataflow::AnalysisContext::Analysis
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
Definition: TypeErasedDataflowAnalysis.cpp:170
clang::DoStmt
DoStmt - This represents a 'do/while' stmt.
Definition: Stmt.h:2510
clang::dataflow::ControlFlowContext
Holds CFG and other derived context that is needed to perform dataflow analysis.
Definition: ControlFlowContext.h:31
clang::dataflow::TerminatorVisitor::VisitForStmt
void VisitForStmt(const ForStmt *S)
Definition: TypeErasedDataflowAnalysis.cpp:99
StmtVisitor.h
clang::DataflowWorklistBase::dequeue
const CFGBlock * dequeue()
Definition: DataflowWorklist.h:42
clang::CFGStmt::getStmt
const Stmt * getStmt() const
Definition: CFG.h:138
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1139
clang::CFG::getEntry
CFGBlock & getEntry()
Definition: CFG.h:1332
DataflowEnvironment.h
clang::ConstStmtVisitor
ConstStmtVisitor - This class implements a simple visitor for Stmt subclasses.
Definition: StmtVisitor.h:193
clang::CFGBlock::AdjacentBlock
This class represents a potential adjacent block in the CFG.
Definition: CFG.h:792
clang::dataflow::Environment::makeAtomicBoolValue
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
Definition: DataflowEnvironment.h:287
clang::ForwardDataflowWorklist::enqueueSuccessors
void enqueueSuccessors(const CFGBlock *Block)
Definition: DataflowWorklist.h:71
clang::dataflow::TypeErasedDataflowAnalysis
Type-erased base class for dataflow analyses built on a single lattice type.
Definition: TypeErasedDataflowAnalysis.h:53
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
clang::dataflow::TerminatorVisitor::TerminatorVisitor
TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env, int BlockSuccIdx, TransferOptions TransferOpts)
Definition: TypeErasedDataflowAnalysis.cpp:76
clang::dataflow::AnalysisContext::AnalysisContext
AnalysisContext(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState >> BlockStates)
Definition: TypeErasedDataflowAnalysis.cpp:159
Transfer.h
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::TransferOptions
Definition: Transfer.h:30
CFG.h
clang::DeclaratorContext::Block
@ Block
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:70
clang::dataflow::AnalysisContext::BlockStates
llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
Definition: TypeErasedDataflowAnalysis.cpp:175
clang::dataflow::TypeErasedDataflowAnalysis::isEqualTypeErased
virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
clang::CFGElement::getKind
Kind getKind() const
Definition: CFG.h:118
clang::dataflow::transfer
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, TransferOptions Options)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:711
clang::dataflow::builtinTransfer
void builtinTransfer(const CFGElement &Elt, TypeErasedDataflowAnalysisState &State, AnalysisContext &AC)
Definition: TypeErasedDataflowAnalysis.cpp:311
clang::dataflow::Environment::getStorageLocation
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...
Definition: DataflowEnvironment.cpp:411
clang::dataflow::TerminatorVisitor::VisitIfStmt
void VisitIfStmt(const IfStmt *S)
Definition: TypeErasedDataflowAnalysis.cpp:81
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:57
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::dataflow::TypeErasedDataflowAnalysisState
Type-erased model of the program at a given program point.
Definition: TypeErasedDataflowAnalysis.h:96
clang::CXXCtorInitializer
Represents a C++ base or member initializer.
Definition: DeclCXX.h:2207
clang::dataflow::TypeErasedDataflowAnalysisState::Env
Environment Env
Model of the state of the program (store and heap).
Definition: TypeErasedDataflowAnalysis.h:101
Value.h
clang::dataflow::Environment::makeNot
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
Definition: DataflowEnvironment.h:309
clang::dataflow::runTypeErasedDataflowAnalysis
llvm::Expected< std::vector< llvm::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...
Definition: TypeErasedDataflowAnalysis.cpp:373
clang::dataflow::TypeErasedDataflowAnalysis::builtinTransferOptions
llvm::Optional< TransferOptions > builtinTransferOptions() const
If the built-in transfer functions (which model the heap and stack in the Environment) are to be appl...
Definition: TypeErasedDataflowAnalysis.h:90
clang::dataflow::ControlFlowContext::getCFG
const CFG & getCFG() const
Returns the CFG that is stored in this context.
Definition: ControlFlowContext.h:47