ExplodedGraph.h Source File (original) (raw)

18#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

19#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_EXPLODEDGRAPH_H

28#include "llvm/ADT/ArrayRef.h"

29#include "llvm/ADT/DenseMap.h"

30#include "llvm/ADT/DepthFirstIterator.h"

31#include "llvm/ADT/FoldingSet.h"

32#include "llvm/ADT/GraphTraits.h"

33#include "llvm/ADT/STLExtras.h"

34#include "llvm/ADT/SetVector.h"

35#include "llvm/ADT/iterator_range.h"

36#include "llvm/Support/Allocator.h"

37#include "llvm/Support/Compiler.h"

38#include

39#include

40#include

41#include

42#include

43#include

47class CFG;

49class Expr;

50class ParentMap;

51class Stmt;

53namespace ento {

55class ExplodedGraph;

84 class NodeGroup {

91 public:

92 NodeGroup(bool Flag = false) : P(Flag) {

93 assert(getFlag() == Flag);

94 }

100 unsigned size() const;

101

102 bool empty() const { return P == 0 || getFlag() != 0; }

103

104

105

106

108

109

110

111

112

113

114 void replaceNode(ExplodedNode *node);

115

116

117 bool getFlag() const {

118 return (P & 1);

119 }

120 };

121

122

123

124 const ProgramPoint Location;

125

126

128

129

130 NodeGroup Preds;

131

132

133 NodeGroup Succs;

134

136

137public:

139 int64_t Id, bool IsSink)

140 : Location(loc), State(std::move(state)), Succs(IsSink), Id(Id) {

141 assert(isSink() == IsSink);

142 }

143

144

146

149 }

150

153 }

154

156

158

160

163 }

164

167 }

168

170

171 template std::optional getLocationAs() const & {

172 return Location.getAs<T>();

173 }

174

175

178 }

179

180 static void Profile(llvm::FoldingSetNodeID &ID,

183 bool IsSink) {

185 ID.AddPointer(state.get());

186 ID.AddBoolean(IsSink);

187 }

188

189 void Profile(llvm::FoldingSetNodeID& ID) const {

190

192 }

193

194

195

197

198 unsigned succ_size() const { return Succs.size(); }

199 unsigned pred_size() const { return Preds.size(); }

200 bool succ_empty() const { return Succs.empty(); }

201 bool pred_empty() const { return Preds.empty(); }

202

203 bool isSink() const { return Succs.getFlag(); }

204

207 }

208

211 }

212

215 }

216

219 }

220

223 }

224

225

227 using succ_range = llvm::iterator_range<succ_iterator>;

228

231

233 using pred_range = llvm::iterator_range<pred_iterator>;

234

237

241

244 }

247 }

249

253

256 }

259 }

261

263

264

265

266

267

268

270

271

272

273

274

276

277

278

279

280

282

283

284

285

286

288

289

290

291

292

294

295private:

296 void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }

297 void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }

298};

299

301 llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;

302

304protected:

306

307

309

310

311

312

313

315

316

317

319

320

321 llvm::FoldingSet Nodes;

322

323

324

326

327

329

330

332

333

335

336

337

338

340

341

343

344public:

347

348

349

350

351

353 bool IsSink = false,

354 bool* IsNew = nullptr);

355

356

357

358

359

362 int64_t Id,

363 bool IsSink = false);

364

366 return std::make_unique();

367 }

368

369

372 return V;

373 }

374

375

378 return V;

379 }

380

383

386

387 void reserve(unsigned NodeCount) { Nodes.reserve(NodeCount); }

388

389

391 using AllNodesTy = llvm::FoldingSet;

398

399 llvm::iterator_range<node_iterator> nodes() { return Nodes; }

400

401 llvm::iterator_range<const_node_iterator> nodes() const { return Nodes; }

402

404

406

408

410

412

414

416

418

421

422 using NodeMap = llvm::DenseMap<const ExplodedNode *, ExplodedNode *>;

423

424

425

426

427

428

429

430

431

432

433

434 std::unique_ptr

438

439

440

443 }

444

445

446

448

449

450

452

453private:

454 bool shouldCollect(const ExplodedNode *node);

456};

457

461

462public:

464 assert(N && !static_cast<ExplodedNode*>(N)->isSink());

465 Impl.insert(N);

466 }

467

469

471 if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);

472 }

473

476

477 unsigned size() const { return Impl.size(); }

478 bool empty() const { return Impl.empty(); }

480

481 void clear() { Impl.clear(); }

482

484 assert(&S != this);

486 Impl = S.Impl;

487 else

488 Impl.insert(S.begin(), S.end());

489 }

490

493

496};

497

498}

499

500}

501

502

503

504namespace llvm {

505 template <> struct GraphTraits<clang::ento::ExplodedGraph *> {

510

513 }

514

517 }

518

520 if (predecessorOfTrivial(N))

521 return child_begin(*N->succ_begin());

523 }

524

526 if (predecessorOfTrivial(N))

529 }

530

532 return df_begin(G);

533 }

534

536 return df_end(G);

537 }

538 };

539}

540

541#endif

This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...

Forward-declares and imports various common LLVM datatypes that clang wants to use unqualified.

llvm::BumpPtrAllocator & getAllocator()

Represents a single basic block in a source-level CFG.

Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.

Decl - This represents one declaration (or definition), e.g.

This represents one expression.

It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...

const Decl * getDecl() const

const ParentMap & getParentMap() const

const StackFrameContext * getStackFrame() const

const LocationContext * getLocationContext() const

It represents a stack frame of the call stack (based on CallEvent).

Stmt - This represents one statement.

BranchNodeBuilder is responsible for constructing the nodes corresponding to the two branches of the ...

CoreEngine - Implements the core logic of the graph-reachability analysis.

std::unique_ptr< ExplodedGraph > trim(ArrayRef< const NodeTy * > Nodes, InterExplodedGraphMap *ForwardMap=nullptr, InterExplodedGraphMap *InverseMap=nullptr) const

Creates a trimmed version of the graph that only contains paths leading to the given nodes.

const_roots_iterator roots_begin() const

unsigned num_eops() const

ExplodedNode * addRoot(ExplodedNode *V)

addRoot - Add an untyped node to the set of roots.

roots_iterator roots_end()

BumpVectorContext & getNodeAllocator()

std::vector< ExplodedNode * > NodeVector

unsigned ReclaimCounter

Counter to determine when to reclaim nodes.

void reserve(unsigned NodeCount)

NodeVector ChangedNodes

A list of recently allocated nodes that can potentially be recycled.

int64_t NumNodes

NumNodes - The number of nodes in the graph.

NodeVector Roots

The roots of the simulation graph.

void enableNodeReclamation(unsigned Interval)

Enable tracking of recently allocated nodes for potential reclamation when calling reclaimRecentlyAll...

NodeVector::const_iterator const_roots_iterator

unsigned ReclaimNodeInterval

Determines how often nodes are reclaimed.

NodeVector EndNodes

The nodes in the simulation graph which have been specially marked as the endpoint of an abstract sim...

NodeVector::iterator eop_iterator

const_roots_iterator roots_end() const

llvm::iterator_range< const_node_iterator > nodes() const

void reclaimRecentlyAllocatedNodes()

Reclaim "uninteresting" nodes created since the last time this method was called.

static bool isInterestingLValueExpr(const Expr *Ex)

Returns true if nodes for the given expression kind are always kept around.

AllNodesTy::const_iterator const_node_iterator

unsigned num_roots() const

llvm::BumpPtrAllocator & getAllocator()

std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const

AllNodesTy::iterator node_iterator

llvm::FoldingSet< ExplodedNode > AllNodesTy

ExplodedNode * getNode(const ProgramPoint &L, ProgramStateRef State, bool IsSink=false, bool *IsNew=nullptr)

Retrieve the node associated with a (Location,State) pair, where the 'Location' is a ProgramPoint in ...

const_eop_iterator eop_begin() const

NodeVector::const_iterator const_eop_iterator

BumpVectorContext BVC

BVC - Allocator and context for allocating nodes and their predecessor and successor groups.

llvm::iterator_range< node_iterator > nodes()

roots_iterator roots_begin()

ExplodedNode * createUncachedNode(const ProgramPoint &L, ProgramStateRef State, int64_t Id, bool IsSink=false)

Create a node for a (Location, State) pair, but don't store it for deduplication later.

llvm::FoldingSet< ExplodedNode > Nodes

Nodes - The nodes in the graph.

llvm::DenseMap< const ExplodedNode *, ExplodedNode * > NodeMap

ExplodedNode * addEndOfPath(ExplodedNode *V)

addEndOfPath - Add an untyped node to the set of EOP nodes.

NodeVector::iterator roots_iterator

NodeVector FreeNodes

A list of nodes that can be reused.

const_eop_iterator eop_end() const

bool erase(ExplodedNode *N)

ExplodedNodeSet(ExplodedNode *N)

ImplTy::iterator iterator

ImplTy::const_iterator const_iterator

void insert(const ExplodedNodeSet &S)

const_iterator end() const

void Add(ExplodedNode *N)

ExplodedNodeSet()=default

const_iterator begin() const

const CFGBlock * getCFGBlock() const

llvm::iterator_range< pred_iterator > pred_range

const ProgramStateRef & getState() const

friend class ExplodedGraph

llvm::iterator_range< const_succ_iterator > const_succ_range

pred_iterator pred_begin()

const_pred_iterator pred_begin() const

const Stmt * getStmtForDiagnostics() const

If the node's program point corresponds to a statement, retrieve that statement.

const_succ_iterator succ_begin() const

llvm::iterator_range< succ_iterator > succ_range

bool isTrivial() const

The node is trivial if it has only one successor, only one predecessor, it's predecessor has only one...

const Stmt * getPreviousStmtForDiagnostics() const

Find the statement that was executed immediately before this node.

void Profile(llvm::FoldingSetNodeID &ID) const

ProgramPoint getLocation() const

getLocation - Returns the edge associated with the given node.

void addPredecessor(ExplodedNode *V, ExplodedGraph &G)

addPredeccessor - Adds a predecessor to the current node, and in tandem add this node as a successor ...

llvm::iterator_range< const_pred_iterator > const_pred_range

ExplodedNode * getFirstSucc()

unsigned pred_size() const

static void Profile(llvm::FoldingSetNodeID &ID, const ProgramPoint &Loc, const ProgramStateRef &state, bool IsSink)

const ExplodedNode * getFirstSucc() const

ExplodedNode(const ProgramPoint &loc, ProgramStateRef state, int64_t Id, bool IsSink)

bool hasSinglePred() const

const_succ_range succs() const

succ_iterator succ_begin()

const Stmt * getNextStmtForDiagnostics() const

Find the next statement that was executed on this node's execution path.

const StackFrameContext * getStackFrame() const

ExplodedNode *const * succ_iterator

const ExplodedNode * getFirstPred() const

const_pred_range preds() const

friend class EndOfFunctionNodeBuilder

const ParentMap & getParentMap() const

SVal getSVal(const Stmt *S) const

Get the value of an arbitrary expression at this node.

const LocationContext * getLocationContext() const

std::optional< T > getLocationAs() const &

const Stmt * getCurrentOrPreviousStmtForDiagnostics() const

Find the statement that was executed at or immediately before this node.

const ExplodedNode *const * const_pred_iterator

ExplodedNode * getFirstPred()

const_succ_iterator succ_end() const

unsigned succ_size() const

ExplodedNode *const * pred_iterator

const ExplodedNode *const * const_succ_iterator

const Decl & getCodeDecl() const

const_pred_iterator pred_end() const

This is the simplest builder which generates nodes in the ExplodedGraph.

SVal - This represents a symbolic expression, which can be either an L-value or an R-value.

@ Decl

The l-value was an access to a declared entity or something equivalently strong, like the address of ...

llvm::DenseMap< const ExplodedNode *, const ExplodedNode * > InterExplodedGraphMap

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

The JSON file list parser is used to communicate input to InstallAPI.

const FunctionProtoType * T

Diagnostic wrappers for TextAPI types for error reporting.

__UINTPTR_TYPE__ uintptr_t

An unsigned integer type with the property that any valid pointer to void can be converted to this ty...

static nodes_iterator nodes_end(const GraphTy G)

static bool predecessorOfTrivial(NodeRef N)

static nodes_iterator nodes_begin(const GraphTy G)

static ChildIteratorType child_end(NodeRef N)

llvm::df_iterator< GraphTy > nodes_iterator

clang::ento::ExplodedNode::succ_iterator ChildIteratorType

static NodeRef getEntryNode(const GraphTy G)

static ChildIteratorType child_begin(NodeRef N)