TypeErasedDataflowAnalysis.cpp Source File (original) (raw)

14#include

15#include <system_error>

16#include

17#include

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

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

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

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

39#define DEBUG_TYPE "clang-dataflow"

42namespace dataflow {

43class NoopLattice;

44}

45}

47namespace llvm {

52template struct CLANG_EXPORT_TEMPLATE Any::TypeIdclang::dataflow::NoopLattice;

53}

56namespace dataflow {

61 auto BlockPos = llvm::find_if(

63 return Succ && Succ->getBlockID() == Block.getBlockID();

64 });

66}

76}

78namespace {

81class TerminatorVisitor

83public:

84 TerminatorVisitor() = default;

85 const Expr *VisitIfStmt(const IfStmt *S) { return S->getCond(); }

86 const Expr *VisitWhileStmt(const WhileStmt *S) { return S->getCond(); }

87 const Expr *VisitDoStmt(const DoStmt *S) { return S->getCond(); }

88 const Expr *VisitForStmt(const ForStmt *S) { return S->getCond(); }

89 const Expr *VisitCXXForRangeStmt(const CXXForRangeStmt *) {

92 return nullptr;

93 }

94 const Expr *VisitBinaryOperator(const BinaryOperator *S) {

95 assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);

96 return S->getLHS();

97 }

98 const Expr *VisitConditionalOperator(const ConditionalOperator *S) {

99 return S->getCond();

100 }

101};

102

103

104struct AnalysisContext {

105 AnalysisContext(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis,

106 const Environment &InitEnv,

107 llvm::ArrayRef<std::optional>

110 Log(*InitEnv.getDataflowAnalysisContext().getOptions().Log),

113 }

114 ~AnalysisContext() { Log.endAnalysis(); }

115

116

118

120

123

124

126};

127

128class PrettyStackTraceAnalysis : public llvm::PrettyStackTraceEntry {

129public:

130 PrettyStackTraceAnalysis(const AdornedCFG &ACFG, const char *Message)

131 : ACFG(ACFG), Message(Message) {}

132

133 void print(raw_ostream &OS) const override {

134 OS << Message << "\n";

135 OS << "Decl:\n";

136 ACFG.getDecl().dump(OS);

137 OS << "CFG:\n";

138 ACFG.getCFG().print(OS, LangOptions(), false);

139 }

140

141private:

142 const AdornedCFG &ACFG;

143 const char *Message;

144};

145

146class PrettyStackTraceCFGElement : public llvm::PrettyStackTraceEntry {

147public:

148 PrettyStackTraceCFGElement(const CFGElement &Element, int BlockIdx,

149 int ElementIdx, const char *Message)

150 : Element(Element), BlockIdx(BlockIdx), ElementIdx(ElementIdx),

151 Message(Message) {}

152

153 void print(raw_ostream &OS) const override {

154 OS << Message << ": Element [B" << BlockIdx << "." << ElementIdx << "]\n";

155 if (auto Stmt = Element.getAs()) {

156 OS << "Stmt:\n";

157 ASTDumper Dumper(OS, false);

158 Dumper.Visit(Stmt->getStmt());

159 }

160 }

161

162private:

163 const CFGElement ∈

164 int BlockIdx;

165 int ElementIdx;

166 const char *Message;

167};

168

169

170

171

172

173class JoinedStateBuilder {

174 AnalysisContext &AC;

175 Environment::ExprJoinBehavior JoinBehavior;

176 std::vector<const TypeErasedDataflowAnalysisState *> All;

177 std::deque Owned;

178

179 TypeErasedDataflowAnalysisState

180 join(const TypeErasedDataflowAnalysisState &L,

181 const TypeErasedDataflowAnalysisState &R) {

182 return {AC.Analysis.joinTypeErased(L.Lattice, R.Lattice),

183 Environment::join(L.Env, R.Env, AC.Analysis, JoinBehavior)};

184 }

185

186public:

187 JoinedStateBuilder(AnalysisContext &AC,

188 Environment::ExprJoinBehavior JoinBehavior)

189 : AC(AC), JoinBehavior(JoinBehavior) {}

190

191 void addOwned(TypeErasedDataflowAnalysisState State) {

192 Owned.push_back(std::move(State));

193 All.push_back(&Owned.back());

194 }

195 void addUnowned(const TypeErasedDataflowAnalysisState &State) {

196 All.push_back(&State);

197 }

198 TypeErasedDataflowAnalysisState take() && {

199 if (All.empty())

200

201

202

203 return {AC.Analysis.typeErasedInitialElement(), AC.InitEnv.fork()};

204 if (All.size() == 1)

205

206

207

208

209 return {All[0]->Lattice, Environment::join(All[0]->Env, All[0]->Env,

210 AC.Analysis, JoinBehavior)};

211

212 auto Result = join(*All[0], *All[1]);

213 for (unsigned I = 2; I < All.size(); ++I)

214 Result = join(Result, *All[I]);

215 return Result;

216 }

217};

218}

219

221 return TerminatorStmt == nullptr ? nullptr

222 : TerminatorVisitor().Visit(TerminatorStmt);

223}

224

225

226

227

228

229

230

231

232

233static TypeErasedDataflowAnalysisState

235 std::vector<const CFGBlock *> Preds(Block.pred_begin(), Block.pred_end());

236 if (Block.getTerminator().isTemporaryDtorsBranch()) {

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259 if (Block.succ_begin()->getReachableBlock() != nullptr &&

260 Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {

261 const CFGBlock *StmtBlock = nullptr;

262 if (const Stmt *Terminator = Block.getTerminatorStmt())

263 StmtBlock = AC.ACFG.blockForStmt(*Terminator);

264 assert(StmtBlock != nullptr);

265 llvm::erase(Preds, StmtBlock);

266 }

267 }

268

269

270

271

272

273

274

275

277 for (const CFGBlock *Pred : Preds) {

278 if (Pred && AC.ACFG.containsExprConsumedInDifferentBlock(*Pred)) {

279 JoinBehavior = Environment::KeepExprState;

280 break;

281 }

282 }

283

284 JoinedStateBuilder Builder(AC, JoinBehavior);

285 for (const CFGBlock *Pred : Preds) {

286

287 if (!Pred || Pred->hasNoReturnElement())

288 continue;

289

290

291

292 const std::optional &MaybePredState =

293 AC.BlockStates[Pred->getBlockID()];

294 if (!MaybePredState)

295 continue;

296

299 if (Cond == nullptr) {

300 Builder.addUnowned(PredState);

301 continue;

302 }

303

305

306

307

309 if (AC.Analysis.builtinOptions()) {

311

312

313

314

315 assert(CondVal != nullptr);

317 BranchVal ? CondVal : &Copy.Env.makeNot(*CondVal);

319 }

320 AC.Analysis.transferBranchTypeErased(BranchVal, Cond, Copy.Lattice,

322 Builder.addOwned(std::move(Copy));

323 }

324 return std::move(Builder).take();

325}

326

327

328static void

331 AnalysisContext &AC) {

333 assert(S != nullptr);

335 InputState.Env, AC.Analysis);

336}

337

338

339static void

343 assert(Init != nullptr);

344

345 auto &Env = InputState.Env;

346 auto &ThisLoc = *Env.getThisPointeeStorageLocation();

347

348 if (!Init->isAnyMemberInitializer())

349

350 return;

351

352 auto *InitExpr = Init->getInit();

353 assert(InitExpr != nullptr);

354

358 if (Init->isMemberInitializer()) {

359 Member = Init->getMember();

360 MemberLoc = ThisLoc.getChild(*Member);

361 } else {

363 assert(IndirectField != nullptr);

364 MemberLoc = &ThisLoc;

365 for (const auto *I : IndirectField->chain()) {

366 Member = cast(I);

367 ParentLoc = cast(MemberLoc);

369 }

370 }

371 assert(Member != nullptr);

372

373

374

375

376

377

378

379

380 if (Member->getType()->isReferenceType()) {

381 auto *InitExprLoc = Env.getStorageLocation(*InitExpr);

382 if (InitExprLoc == nullptr)

383 return;

384

386

387

388 } else if ( Member ->getType()->isRecordType()) {

389 assert(MemberLoc != nullptr);

390 if (auto *InitExprVal = Env.getValue(*InitExpr))

391 Env.setValue(*MemberLoc, *InitExprVal);

392 }

393}

394

397 AnalysisContext &AC) {

399 case CFGElement::Statement:

401 break;

402 case CFGElement::Initializer:

404 break;

405 case CFGElement::LifetimeEnds:

406

407

408

409

410

412 State.Env.removeDecl(*VD);

413 break;

414 default:

415

416 break;

417 }

418}

419

420

421

422

423

424

425

426

427

428static TypeErasedDataflowAnalysisState

431 AC.Log.enterBlock(Block, PostAnalysisCallbacks.Before != nullptr ||

432 PostAnalysisCallbacks.After != nullptr);

433 auto State = computeBlockInputState(Block, AC);

434 AC.Log.recordState(State);

435 int ElementIdx = 1;

436 for (const auto &Element : Block) {

437 PrettyStackTraceCFGElement CrashInfo(Element, Block.getBlockID(),

438 ElementIdx++, "transferCFGBlock");

439

440 AC.Log.enterElement(Element);

441

442 if (PostAnalysisCallbacks.Before) {

443 PostAnalysisCallbacks.Before(Element, State);

444 }

445

446

447 if (AC.Analysis.builtinOptions()) {

448 builtinTransfer(Block.getBlockID(), Element, State, AC);

449 }

450

451

452 AC.Analysis.transferTypeErased(Element, State.Lattice, State.Env);

453

454 if (PostAnalysisCallbacks.After) {

455 PostAnalysisCallbacks.After(Element, State);

456 }

457

458 AC.Log.recordState(State);

459 }

460

461

462

463

464

465

466 if (const Expr *TerminatorCond =

467 dyn_cast_or_null(Block.getTerminatorCondition())) {

468 if (State.Env.getValue(*TerminatorCond) == nullptr)

469

470

471

472

473

474 transfer(StmtToEnvMap(AC.ACFG, AC.BlockStates, Block.getBlockID(), State),

475 *TerminatorCond, State.Env, AC.Analysis);

476

477

478

479

480 if (State.Env.getValue(*TerminatorCond) == nullptr)

481 State.Env.setValue(*TerminatorCond, State.Env.makeAtomicBoolValue());

482 AC.Log.recordState(State);

483 }

484

485 return State;

486}

487

493 std::int32_t MaxBlockVisits) {

494 PrettyStackTraceAnalysis CrashInfo(ACFG, "runTypeErasedDataflowAnalysis");

495

496 std::optional MaybeStartingEnv;

497 if (InitEnv.callStackSize() == 0) {

498 MaybeStartingEnv = InitEnv.fork();

499 MaybeStartingEnv->initialize();

500 }

502 MaybeStartingEnv ? *MaybeStartingEnv : InitEnv;

503

507

508 std::vector<std::optional> BlockStates(

510

511

514 StartingEnv.fork()};

516

518 std::int32_t BlockVisits = 0;

520 LLVM_DEBUG(llvm::dbgs()

521 << "Processing Block " << Block->getBlockID() << "\n");

522 if (++BlockVisits > MaxBlockVisits) {

523 return llvm::createStringError(std::errc::timed_out,

524 "maximum number of blocks processed");

525 }

526

527 const std::optional &OldBlockState =

531 LLVM_DEBUG({

532 llvm::errs() << "New Env:\n";

533 NewBlockState.Env.dump();

534 });

535

536 if (OldBlockState) {

537 LLVM_DEBUG({

538 llvm::errs() << "Old Env:\n";

539 OldBlockState->Env.dump();

540 });

543 NewBlockState.Lattice, OldBlockState->Lattice);

546 if (Effect1 == LatticeJoinEffect::Unchanged &&

547 Effect2 == LatticeJoinEffect::Unchanged) {

548

549

550 AC.Log.blockConverged();

551 continue;

552 }

553 } else if (Analysis.isEqualTypeErased(OldBlockState->Lattice,

554 NewBlockState.Lattice) &&

555 OldBlockState->Env.equivalentTo(NewBlockState.Env, Analysis)) {

556

557

558 AC.Log.blockConverged();

559 continue;

560 }

561 }

562

564

565

566 if (Block->hasNoReturnElement())

567 continue;

568

570 }

571

572

573

574 if (PostAnalysisCallbacks.Before || PostAnalysisCallbacks.After) {

576

578 continue;

580 }

581 }

582

584}

585

586}

587}

static const Stmt * getTerminatorCondition(const CFGBlock *B)

A customized wrapper for CFGBlock::getTerminatorCondition() which returns the element for ObjCForColl...

Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....

static void print(llvm::raw_ostream &OS, const T &V, ASTContext &ASTCtx, QualType Ty)

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.

const AdornedCFG & ACFG

Contains the CFG being analyzed.

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

LLVM_DUMP_METHOD void dump() const

Environment fork() const

Returns a new environment that is a copy of this one.

ExprJoinBehavior

How to treat expression state (ExprToLoc and ExprToVal) in a join.

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.

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.

static TypeErasedDataflowAnalysisState transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks={})

Transfers State by evaluating each element in the Block based on the AC.Analysis specified.

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)

llvm::Expected< std::vector< std::optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, const CFGEltCallbacksTypeErased &PostAnalysisCallbacks, std::int32_t MaxBlockVisits)

Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...

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.

Diagnostic wrappers for TextAPI types for error reporting.

A worklist implementation for forward dataflow analysis.

void enqueueSuccessors(const CFGBlock *Block)

A pair of callbacks to be called with the state before and after visiting a CFG element.

CFGEltCallbackTypeErased Before

CFGEltCallbackTypeErased After

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