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 "llvm/ADT/SmallVector.h"

30#include "llvm/Support/Casting.h"

31#include

32#include

33#include

35using namespace clang;

36using namespace ento;

52 return false;

53 return isa<DeclRefExpr, MemberExpr, ObjCIvarRefExpr, ArraySubscriptExpr>(Ex);

54}

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

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

89 return false;

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

93 return false;

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

97 return false;

100

101 ProgramPoint progPoint = node->getLocation();

103 return !progPoint.getTag();

104

105

107 return false;

108

109

110 if (progPoint.getTag())

111 return false;

112

113

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

118 return false;

119

120

121

123 if (!Ex)

124 return false;

125

126

127

128

130 return false;

131

132

133

134

135

138 return false;

139

140

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

144 return false;

145

146

148 return false;

149

150 return true;

151}

152

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

154

155

156

157

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

161 pred->replaceSuccessor(succ);

162 succ->replacePredecessor(pred);

164 Nodes.RemoveNode(node);

166 node->~ExplodedNode();

167}

168

171 return;

172

173

174

175

178 return;

180

182 if (shouldCollect(node))

183 collectNode(node);

185}

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

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

203

205 assert(->isSink());

206 Preds.addNode(V, G);

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

208}

209

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

211 assert(!getFlag());

212

214 assert(isa<ExplodedNode *>(Storage));

215 Storage = node;

216 assert(isa<ExplodedNode *>(Storage));

217}

218

220 assert(!getFlag());

221

223 if (Storage.isNull()) {

224 Storage = N;

225 assert(isa<ExplodedNode *>(Storage));

226 return;

227 }

228

230

231 if () {

232

233 auto *Old = cast<ExplodedNode *>(Storage);

234

237 V->push_back(Old, Ctx);

238

239 Storage = V;

240 assert(!getFlag());

241 assert(isa<ExplodedNodeVector *>(Storage));

242 }

243

245}

246

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

248 if (getFlag())

249 return 0;

250

253 return 0;

255 return V->size();

256 return 1;

257}

258

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

260 if (getFlag())

261 return nullptr;

262

265 return nullptr;

267 return V->begin();

268 return Storage.getAddrOfPtr1();

269}

270

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

272 if (getFlag())

273 return nullptr;

274

277 return nullptr;

279 return V->end();

280 return Storage.getAddrOfPtr1() + 1;

281}

282

287}

288

292 return BEP->getBlock();

293

294

295

296

302

303 return nullptr;

304}

305

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

312 LC = ParentLC;

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

315 }

316 return LC;

317}

318

320

321

322

325

327 ->getCallSite();

328 }

329

330

333 return SP->getStmt();

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

337 return CE->getCallExpr();

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

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

343 return CEB->getReturnStmt();

345 return FEP->getStmt();

346

347 return nullptr;

348}

349

353 continue;

355

356

357 switch (S->getStmtClass()) {

358 case Stmt::ChooseExprClass:

359 case Stmt::BinaryConditionalOperatorClass:

360 case Stmt::ConditionalOperatorClass:

361 continue;

362 case Stmt::BinaryOperatorClass: {

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

365 continue;

366 break;

367 }

368 default:

369 break;

370 }

371

372 return S;

373 }

374 }

375

376 return nullptr;

377}

378

382 return S;

383

384 return nullptr;

385}

386

389 return S;

390

392}

393

396 bool IsSink,

397 bool* IsNew) {

398

399 llvm::FoldingSetNodeID profile;

400 void *InsertPos = nullptr;

401

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

404

405 if () {

409 }

410 else {

411

413 }

414

417

420

421

422 Nodes.InsertNode(V, InsertPos);

423

424 if (IsNew) *IsNew = true;

425 }

426 else

427 if (IsNew) *IsNew = false;

428

429 return V;

430}

431

434 int64_t Id,

435 bool IsSink) {

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

438 return V;

439}

440

441std::unique_ptr

445 if (Nodes.empty())

446 return nullptr;

447

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

449 Pass1Ty Pass1;

450

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

454

456

457

458 for (const auto Sink : Sinks)

459 if (Sink)

460 WL1.push_back(Sink);

461

462

463 while (!WL1.empty()) {

465

466

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

468 continue;

469

470

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

472 WL2.push_back(N);

473 continue;

474 }

475

476

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

478 }

479

480

481 if (WL2.empty())

482 return nullptr;

483

484

486

487

488 while (!WL2.empty()) {

490

491

492 if (Pass2.contains(N))

493 continue;

494

495

496

499 Pass2[N] = NewN;

500

501

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

503

504

505 if (N->Preds.empty())

506 G->addRoot(NewN);

507

508

509

510

511

512

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

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

516 continue;

517

519 }

520

521

522

523

524

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

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

528 const_cast<ExplodedNode *>(PI->second)->addPredecessor(NewN, *G);

529 continue;

530 }

531

532

533 if (Pass1.count(Succ))

534 WL2.push_back(Succ);

535 }

536 }

537

538 return G;

539}

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

BumpVector< ExplodedNode * > ExplodedNodeVector

static const LocationContext * findTopAutosynthesizedParentContext(const LocationContext *LC)

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.

CFGBlock * getBlock(Stmt *S)

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.

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.

static bool isInterestingLValueExpr(const Expr *Ex)

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

llvm::BumpPtrAllocator & getAllocator()

std::unique_ptr< ExplodedGraph > MakeEmptyGraph() const

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

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.

NodeVector FreeNodes

A list of nodes that can be reused.

const CFGBlock * getCFGBlock() const

const ProgramStateRef & getState() const

const Stmt * getStmtForDiagnostics() const

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

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.

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

ExplodedNode * getFirstSucc()

unsigned pred_size() const

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

const Stmt * getNextStmtForDiagnostics() const

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

const LocationContext * getLocationContext() const

const Stmt * getCurrentOrPreviousStmtForDiagnostics() const

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

ExplodedNode * getFirstPred()

unsigned succ_size() const

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

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