ExplodedGraph.cpp Source File (original) (raw)

26#include "llvm/ADT/DenseSet.h"

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

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

29#include

30#include

31#include

33using namespace clang;

34using namespace ento;

54bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {

86 if (node->pred_size() != 1 || node->succ_size() != 1)

87 return false;

89 const ExplodedNode *pred = *(node->pred_begin());

91 return false;

93 const ExplodedNode *succ = *(node->succ_begin());

95 return false;

101 return !progPoint.getTag();

102

103

105 return false;

106

107

108 if (progPoint.getTag())

109 return false;

110

111

114 if (state->store != pred_state->store || state->GDM != pred_state->GDM ||

116 return false;

117

118

119

121 if (!Ex)

122 return false;

123

124

125

126

128 return false;

129

130

131

132

133

136 return false;

137

138

140 if (std::optional SP = SuccLoc.getAs<StmtPoint>())

142 return false;

143

144

146 return false;

147

148 return true;

149}

150

151void ExplodedGraph::collectNode(ExplodedNode *node) {

152

153

154

155

156 assert(node->pred_size() == 1 || node->succ_size() == 1);

159 pred->replaceSuccessor(succ);

160 succ->replacePredecessor(pred);

162 Nodes.RemoveNode(node);

164 node->~ExplodedNode();

165}

166

169 return;

170

171

172

173

176 return;

178

180 if (shouldCollect(node))

181 collectNode(node);

183}

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

200using GroupStorage = llvm::PointerUnion<ExplodedNode *, ExplodedNodeVector *>;

201

203 assert(->isSink());

204 Preds.addNode(V, G);

205 V->Succs.addNode(this, G);

206}

207

208void ExplodedNode::NodeGroup::replaceNode(ExplodedNode *node) {

209 assert(!getFlag());

210

213 Storage = node;

215}

216

218 assert(!getFlag());

219

221 if (Storage.isNull()) {

222 Storage = N;

224 return;

225 }

226

228

229 if () {

230

232

235 V->push_back(Old, Ctx);

236

237 Storage = V;

238 assert(!getFlag());

240 }

241

243}

244

245unsigned ExplodedNode::NodeGroup::size() const {

246 if (getFlag())

247 return 0;

248

251 return 0;

253 return V->size();

254 return 1;

255}

256

257ExplodedNode * const *ExplodedNode::NodeGroup::begin() const {

258 if (getFlag())

259 return nullptr;

260

263 return nullptr;

265 return V->begin();

266 return Storage.getAddrOfPtr1();

267}

268

269ExplodedNode * const *ExplodedNode::NodeGroup::end() const {

270 if (getFlag())

271 return nullptr;

272

275 return nullptr;

277 return V->end();

278 return Storage.getAddrOfPtr1() + 1;

279}

280

286

290 return BEP->getBlock();

291

292

293

294

300

301 return nullptr;

302}

303

308 assert(ParentLC && "We don't start analysis from autosynthesized code");

310 LC = ParentLC;

312 assert(ParentLC && "We don't start analysis from autosynthesized code");

313 }

314 return LC;

315}

316

318

319

320

323

325 ->getCallSite();

326 }

327

328

331 return SP->getStmt();

333 return BE->getSrc()->getTerminatorStmt();

335 return CE->getCallExpr();

337 return CEE->getCalleeContext()->getCallSite();

339 return PIPP->getInitializer()->getInit();

341 return CEB->getReturnStmt();

343 return FEP->getStmt();

344

345 return nullptr;

346}

347

351 continue;

353

354

355 switch (S->getStmtClass()) {

356 case Stmt::ChooseExprClass:

357 case Stmt::BinaryConditionalOperatorClass:

358 case Stmt::ConditionalOperatorClass:

359 continue;

360 case Stmt::BinaryOperatorClass: {

362 if (Op == BO_LAnd || Op == BO_LOr)

363 continue;

364 break;

365 }

366 default:

367 break;

368 }

369

370 return S;

371 }

372 }

373

374 return nullptr;

375}

376

380 return S;

381

382 return nullptr;

383}

384

391

394 bool IsSink,

395 bool* IsNew) {

396

397 llvm::FoldingSetNodeID profile;

398 void *InsertPos = nullptr;

399

401 NodeTy* V = Nodes.FindNodeOrInsertPos(profile, InsertPos);

402

403 if () {

407 }

408 else {

409

411 }

412

415

418

419

420 Nodes.InsertNode(V, InsertPos);

421

422 if (IsNew) *IsNew = true;

423 }

424 else

425 if (IsNew) *IsNew = false;

426

427 return V;

428}

429

432 int64_t Id,

433 bool IsSink) {

435 new (V) NodeTy(L, State, Id, IsSink);

436 return V;

437}

438

439std::unique_ptr

443

444

445

446

447 if (Nodes.empty())

448 return nullptr;

449

450 using Pass1Ty = llvm::DenseSet<const ExplodedNode *>;

451 Pass1Ty Pass1;

452

455 Pass2Ty &Pass2 = ForwardMap ? *ForwardMap : Pass2Scratch;

456

458

459

460 for (const auto Sink : Sinks)

461 if (Sink)

462 WL1.push_back(Sink);

463

464

465 while (!WL1.empty()) {

467

468

469 if (!Pass1.insert(N).second)

470 continue;

471

472

473 if (N->Preds.empty()) {

474 assert(N == getRoot() && "Found non-root node with no predecessors!");

475 WL2.push_back(N);

476 continue;

477 }

478

479

480 WL1.append(N->Preds.begin(), N->Preds.end());

481 }

482

483

484 if (WL2.empty())

485 return nullptr;

486

487 assert(WL2.size() == 1 && "There must be only one root!");

488

489

490 std::unique_ptr G = std::make_unique();

491

492

493 while (!WL2.empty()) {

495

496 auto [Place, Inserted] = Pass2.try_emplace(N);

497

498

499 if (!Inserted)

500 continue;

501

502

503

506 Place->second = NewN;

507

508

509 if (InverseMap) (*InverseMap)[NewN] = N;

510

511

512 if (N->Preds.empty()) {

514 G->designateAsRoot(NewN);

515 }

516

517

518

519

520

521

523 Pass2Ty::iterator PI = Pass2.find(Pred);

524 if (PI == Pass2.end())

525 continue;

526

528 }

529

530

531

532

533

535 Pass2Ty::iterator PI = Pass2.find(Succ);

536 if (PI != Pass2.end()) {

538 continue;

539 }

540

541

542 if (Pass1.count(Succ))

543 WL2.push_back(Succ);

544 }

545 }

546

547 return G;

548}

llvm::PointerUnion< ExplodedNode *, ExplodedNodeVector * > GroupStorage

Definition ExplodedGraph.cpp:200

BumpVector< ExplodedNode * > ExplodedNodeVector

Definition ExplodedGraph.cpp:199

static const LocationContext * findTopAutosynthesizedParentContext(const LocationContext *LC)

Definition ExplodedGraph.cpp:305

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

CFGStmtMap * getCFGStmtMap()

bool isBodyAutosynthesized() const

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

const CFGBlock * getBlock(const Stmt *S) const

Returns the CFGBlock the specified Stmt* appears in.

Represents a point when we begin processing an inlined call.

Represents a point when we start the call exit sequence (for inlined call).

Represents a point when we finish the call exit sequence (for inlined call).

This represents one expression.

bool isLValue() const

isLValue - True if this expression is an "l-value" according to the rules of the current language.

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

const ParentMap & getParentMap() const

LLVM_ATTRIBUTE_RETURNS_NONNULL AnalysisDeclContext * getAnalysisDeclContext() const

const LocationContext * getParent() const

It might return null.

bool isConsumedExpr(Expr *E) const

Represents a program point after a store evaluation.

Represents a program point just before an implicit call event.

Represents a point after we ran remove dead bindings BEFORE processing the given statement.

const ProgramPointTag * getTag() const

bool isPurgeKind()

Is this a program point corresponding to purge/removal of dead symbols and bindings.

T castAs() const

Convert to the specified ProgramPoint type, asserting that this ProgramPoint is of the desired type.

std::optional< T > getAs() const

Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...

const LocationContext * getLocationContext() const

const Stmt * getStmt() const

Stmt - This represents one statement.

static bool isCallStmt(const Stmt *S)

Returns true if this is a statement is a function or method call of some kind.

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.

Definition ExplodedGraph.cpp:440

BumpVectorContext & getNodeAllocator()

unsigned ReclaimCounter

Counter to determine when to reclaim nodes.

NodeVector ChangedNodes

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

int64_t NumNodes

NumNodes - The number of nodes in the graph.

unsigned ReclaimNodeInterval

Determines how often nodes are reclaimed.

void reclaimRecentlyAllocatedNodes()

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

Definition ExplodedGraph.cpp:167

static bool isInterestingLValueExpr(const Expr *Ex)

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

Definition ExplodedGraph.cpp:48

llvm::BumpPtrAllocator & getAllocator()

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...

Definition ExplodedGraph.cpp:392

ExplodedNode * getRoot() const

Get the root node of the graph.

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.

Definition ExplodedGraph.cpp:430

llvm::FoldingSet< ExplodedNode > Nodes

Nodes - The nodes in the graph.

NodeVector FreeNodes

A list of nodes that can be reused.

const CFGBlock * getCFGBlock() const

Definition ExplodedGraph.cpp:287

const ProgramStateRef & getState() const

friend class ExplodedGraph

const Stmt * getStmtForDiagnostics() const

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

Definition ExplodedGraph.cpp:317

bool isTrivial() const

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

Definition ExplodedGraph.cpp:281

const Stmt * getPreviousStmtForDiagnostics() const

Find the statement that was executed immediately before this node.

Definition ExplodedGraph.cpp:377

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 ...

Definition ExplodedGraph.cpp:202

ExplodedNode * getFirstSucc()

unsigned pred_size() const

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

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

const Stmt * getNextStmtForDiagnostics() const

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

Definition ExplodedGraph.cpp:348

const LocationContext * getLocationContext() const

const Stmt * getCurrentOrPreviousStmtForDiagnostics() const

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

Definition ExplodedGraph.cpp:385

ExplodedNode * getFirstPred()

unsigned succ_size() const

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

IntrusiveRefCntPtr< const ProgramState > ProgramStateRef

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

bool isa(CodeGen::Address addr)

U cast(CodeGen::Address addr)