LiveVariables.cpp Source File (original) (raw)

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

20#include "llvm/Support/raw_ostream.h"

21#include

22#include

23#include

25using namespace clang;

27namespace {

28class LiveVariablesImpl {

29public:

31 llvm::ImmutableSet<const Expr *>::Factory ESetFact;

32 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;

33 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;

34 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;

35 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;

36 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;

37 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;

38 const bool killAtAssign;

52 : analysisContext(ac),

53 ESetFact(false),

54 DSetFact(false),

55 BSetFact(false), killAtAssign(KillAtAssign) {}

56};

57}

59static LiveVariablesImpl &getImpl(void *x) {

60 return *((LiveVariablesImpl *) x);

61}

69}

72 if (const auto *DD = dyn_cast(D)) {

73 bool alive = false;

74 for (const BindingDecl *BD : DD->bindings())

75 alive |= liveBindings.contains(BD);

80 alive |= liveDecls.contains(DD);

81 return alive;

82 }

83 return liveDecls.contains(D);

84}

86namespace {

87 template

88 SET mergeSets(SET A, SET B) {

89 if (A.isEmpty())

90 return B;

92 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {

93 A = A.add(*it);

94 }

95 return A;

96 }

97}

99void LiveVariables::Observer::anchor() { }

100

104

105 llvm::ImmutableSetRef<const Expr *> SSetRefA(

106 valsA.liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),

107 SSetRefB(valsB.liveExprs.getRootWithoutRetain(),

108 ESetFact.getTreeFactory());

109

110 llvm::ImmutableSetRef<const VarDecl *>

111 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),

112 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());

113

114 llvm::ImmutableSetRef<const BindingDecl *>

115 BSetRefA(valsA.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),

116 BSetRefB(valsB.liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());

117

118 SSetRefA = mergeSets(SSetRefA, SSetRefB);

119 DSetRefA = mergeSets(DSetRefA, DSetRefB);

120 BSetRefA = mergeSets(BSetRefA, BSetRefB);

121

122

123

125 DSetRefA.asImmutableSet(),

126 BSetRefA.asImmutableSet());

127}

128

130 return liveExprs == V.liveExprs && liveDecls == V.liveDecls;

131}

132

133

134

135

136

138 return D->hasGlobalStorage();

139}

140

143}

144

147}

148

150 return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);

151}

152

153

154

155

156

157namespace {

158class TransferFunctions : public StmtVisitor {

159 LiveVariablesImpl &LV;

162 const CFGBlock *currentBlock;

163public:

164 TransferFunctions(LiveVariablesImpl &im,

168 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}

169

171 void VisitBlockExpr(BlockExpr *BE);

173 void VisitDeclStmt(DeclStmt *DS);

177 void Visit(Stmt *S);

178};

179}

180

183 while (const ArrayType *VT = dyn_cast(ty)) {

184 if (const VariableArrayType *VAT = dyn_cast(VT))

185 if (VAT->getSizeExpr())

186 return VAT;

187

188 ty = VT->getElementType().getTypePtr();

189 }

190

191 return nullptr;

192}

193

195 while (E) {

196 if (const Expr *Ex = dyn_cast(E))

198 if (const FullExpr *FE = dyn_cast(E)) {

199 E = FE->getSubExpr();

200 continue;

201 }

202 if (const OpaqueValueExpr *OVE = dyn_cast(E)) {

203 E = OVE->getSourceExpr();

204 continue;

205 }

206 break;

207 }

208 return E;

209}

210

212 llvm::ImmutableSet<const Expr *>::Factory &F,

215}

216

217

218

219

220

221

223 llvm::ImmutableSet<const Expr *>::Factory &F,

224 const Expr *Cond) {

226 if (auto const *BO = dyn_cast(Cond->IgnoreParens());

227 BO && BO->isLogicalOp()) {

230 }

231}

232

233void TransferFunctions::Visit(Stmt *S) {

234 if (observer)

235 observer->observeStmt(S, currentBlock, val);

236

238

239 if (const auto *E = dyn_cast(S)) {

240 val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);

241 }

242

243

244

245 switch (S->getStmtClass()) {

246 default:

247 break;

248 case Stmt::StmtExprClass: {

249

250 S = cast(S)->getSubStmt();

251 break;

252 }

253 case Stmt::CXXMemberCallExprClass: {

254

257 AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);

258 }

259 break;

260 }

261 case Stmt::ObjCMessageExprClass: {

262

265 val.liveDecls = LV.DSetFact.add(val.liveDecls,

266 LV.analysisContext.getSelfDecl());

267 break;

268 }

269 case Stmt::DeclStmtClass: {

270 const DeclStmt *DS = cast(S);

273 VA != nullptr; VA = FindVA(VA->getElementType())) {

274 AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());

275 }

276 }

277 break;

278 }

279 case Stmt::PseudoObjectExprClass: {

280

281

282 Expr *child = cast(S)->getResultExpr();

283 if (!child) return;

284 if (OpaqueValueExpr *OV = dyn_cast(child))

285 child = OV->getSourceExpr();

287 val.liveExprs = LV.ESetFact.add(val.liveExprs, child);

288 return;

289 }

290

291

292 case Stmt::ExprWithCleanupsClass: {

293 S = cast(S)->getSubExpr();

294 break;

295 }

296 case Stmt::CXXBindTemporaryExprClass: {

297 S = cast(S)->getSubExpr();

298 break;

299 }

300 case Stmt::UnaryExprOrTypeTraitExprClass: {

301

302 return;

303 }

304 case Stmt::IfStmtClass: {

305

306

307

308 AddLiveExpr(val.liveExprs, LV.ESetFact, cast(S)->getCond());

309 return;

310 }

311 case Stmt::WhileStmtClass: {

312

313

314

315 AddLiveExpr(val.liveExprs, LV.ESetFact, cast(S)->getCond());

316 return;

317 }

318 case Stmt::DoStmtClass: {

319

320

321

322 AddLiveExpr(val.liveExprs, LV.ESetFact, cast(S)->getCond());

323 return;

324 }

325 case Stmt::ForStmtClass: {

326

327

328

329 AddLiveExpr(val.liveExprs, LV.ESetFact, cast(S)->getCond());

330 return;

331 }

332 case Stmt::ConditionalOperatorClass: {

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347 auto const *CO = cast(S);

349 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getTrueExpr());

350 AddLiveExpr(val.liveExprs, LV.ESetFact, CO->getFalseExpr());

351 return;

352 }

353 }

354

355

356

357

358 for (Stmt *Child : S->children()) {

359 if (const auto *E = dyn_cast_or_null(Child))

361 }

362}

363

367}

368

369void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {

370 if (LV.killAtAssign && B->getOpcode() == BO_Assign) {

371 if (const auto *DR = dyn_cast(B->getLHS()->IgnoreParens())) {

372 LV.inAssignment[DR] = 1;

373 }

374 }

376 if (!LV.killAtAssign)

377 return;

378

379

381

382 if (DeclRefExpr *DR = dyn_cast(LHS)) {

383 const Decl* D = DR->getDecl();

384 bool Killed = false;

385

386 if (const BindingDecl* BD = dyn_cast(D)) {

387 Killed = !BD->getType()->isReferenceType();

388 if (Killed) {

389 if (const auto *HV = BD->getHoldingVar())

390 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);

391

392 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);

393 }

394 } else if (const auto *VD = dyn_cast(D)) {

396 if (Killed)

397 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);

398

399 }

400

401 if (Killed && observer)

402 observer->observerKill(DR);

403 }

404 }

405}

406

407void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {

409 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl())) {

411 continue;

412 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);

413 }

414}

415

416void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {

418 bool InAssignment = LV.inAssignment[DR];

419 if (const auto *BD = dyn_cast(D)) {

420 if (!InAssignment) {

421 if (const auto *HV = BD->getHoldingVar())

422 val.liveDecls = LV.DSetFact.add(val.liveDecls, HV);

423

424 val.liveBindings = LV.BSetFact.add(val.liveBindings, BD);

425 }

426 } else if (const auto *VD = dyn_cast(D)) {

428 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);

429 }

430}

431

432void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {

433 for (const auto *DI : DS->decls()) {

434 if (const auto *DD = dyn_cast(DI)) {

435 for (const auto *BD : DD->bindings()) {

436 if (const auto *HV = BD->getHoldingVar())

437 val.liveDecls = LV.DSetFact.remove(val.liveDecls, HV);

438

439 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);

440 }

441

442

443

444 val.liveDecls = LV.DSetFact.remove(val.liveDecls, DD);

445 } else if (const auto *VD = dyn_cast(DI)) {

447 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);

448 }

449 }

450}

451

453

455 const VarDecl *VD = nullptr;

456

457 Stmt *element = OS->getElement();

458 if (DeclStmt *DS = dyn_cast(element)) {

460 }

461 else if ((DR = dyn_cast(cast(element)->IgnoreParens()))) {

462 VD = cast(DR->getDecl());

463 }

464

465 if (VD) {

466 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);

467 if (observer && DR)

468 observer->observerKill(DR);

469 }

470}

471

472void TransferFunctions::

474{

475

476

477

479 return;

480

484 val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->IgnoreParens());

485 }

486}

487

488void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {

489

490

491

492 if (!observer)

493 return;

494

496 default:

497 return;

498 case UO_PostInc:

499 case UO_PostDec:

500 case UO_PreInc:

501 case UO_PreDec:

502 break;

503 }

504

507 if (isa(D) || isa(D)) {

508

509 observer->observerKill(DR);

510 }

511 }

512}

513

515LiveVariablesImpl::runOnBlock(const CFGBlock *block,

518

519 TransferFunctions TF(*this, val, obs, block);

520

521

523 TF.Visit(const_cast<Stmt*>(term));

524

525

527 ei = block->rend(); it != ei; ++it) {

529

530 if (std::optional Dtor =

533 continue;

534 }

535

537 continue;

538

540 TF.Visit(const_cast<Stmt*>(S));

541 stmtsToLiveness[S] = val;

542 }

543 return val;

544}

545

547 const CFG *cfg = getImpl(impl).analysisContext.getCFG();

549 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);

550}

551

552LiveVariables::LiveVariables(void *im) : impl(im) {}

553

555 delete (LiveVariablesImpl*) impl;

556}

557

558std::unique_ptr

560

561

562 CFG *cfg = AC.getCFG();

563 if (!cfg)

564 return nullptr;

565

566

567

569 return nullptr;

570

571 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);

572

573

574

576 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());

577

578

581 }

582

584

585

586 LivenessValues &prevVal = LV->blocksEndToLiveness[block];

587

588

591 ei = block->succ_end(); it != ei; ++it) {

592 if (const CFGBlock *succ = *it) {

593 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);

594 }

595 }

596

597 if (!everAnalyzedBlock[block->getBlockID()])

598 everAnalyzedBlock[block->getBlockID()] = true;

599 else if (prevVal.equals(val))

600 continue;

601

602 prevVal = val;

603

604

605 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);

606

607

609 }

610

611 return std::unique_ptr(new LiveVariables(LV));

612}

613

615 getImpl(impl).dumpBlockLiveness(M);

616}

617

618void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {

619 std::vector<const CFGBlock *> vec;

620 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator

621 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();

622 it != ei; ++it) {

623 vec.push_back(it->first);

624 }

627 });

628

629 std::vector<const VarDecl*> declVec;

630

631 for (std::vector<const CFGBlock *>::iterator

632 it = vec.begin(), ei = vec.end(); it != ei; ++it) {

633 llvm::errs() << "\n[ B" << (*it)->getBlockID()

634 << " (live variables at block exit) ]\n";

635

637 declVec.clear();

638

639 for (llvm::ImmutableSet<const VarDecl *>::iterator si =

641 se = vals.liveDecls.end(); si != se; ++si) {

642 declVec.push_back(*si);

643 }

644

645 llvm::sort(declVec, [](const Decl *A, const Decl *B) {

647 });

648

649 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),

650 de = declVec.end(); di != de; ++di) {

651 llvm::errs() << " " << (*di)->getDeclName().getAsString()

652 << " <";

653 (*di)->getLocation().print(llvm::errs(), M);

654 llvm::errs() << ">\n";

655 }

656 }

657 llvm::errs() << "\n";

658}

659

661 getImpl(impl).dumpExprLiveness(M);

662}

663

664void LiveVariablesImpl::dumpExprLiveness(const SourceManager &M) {

665

666 for (const CFGBlock *B : *analysisContext.getCFG()) {

667

668 llvm::errs() << "\n[ B" << B->getBlockID()

669 << " (live expressions at block exit) ]\n";

670 for (const Expr *E : blocksEndToLiveness[B].liveExprs) {

671 llvm::errs() << "\n";

673 }

674 llvm::errs() << "\n";

675 }

676}

677

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

static const VariableArrayType * FindVA(const Type *t)

static bool writeShouldKill(const VarDecl *VD)

static void AddLiveExpr(llvm::ImmutableSet< const Expr * > &Set, llvm::ImmutableSet< const Expr * >::Factory &F, const Expr *E)

static LiveVariablesImpl & getImpl(void *x)

static const Expr * LookThroughExpr(const Expr *E)

static void AddAllConditionalTerms(llvm::ImmutableSet< const Expr * > &Set, llvm::ImmutableSet< const Expr * >::Factory &F, const Expr *Cond)

Add as a live expression all individual conditions in a logical expression.

static bool isAlwaysAlive(const VarDecl *D)

const CFGBlock * CurrentBlock

static bool runOnBlock(const CFGBlock *block, const CFG &cfg, AnalysisDeclContext &ac, CFGBlockValues &vals, const ClassifyRefs &classification, llvm::BitVector &wasAnalyzed, UninitVariablesHandler &handler)

AnalysisDeclContext contains the context data for the function, method or block under analysis.

Represents an array type, per C99 6.7.5.2 - Array Declarators.

A builtin binary operation expression such as "x + y" or "x <= y".

static bool isAssignmentOp(Opcode Opc)

A binding in a decomposition declaration.

BlockExpr - Adaptor class for mixing a BlockDecl with expressions.

const BlockDecl * getBlockDecl() const

Represents C++ object destructor implicitly generated for automatic object or temporary bound to cons...

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

reverse_iterator rbegin()

succ_iterator succ_begin()

Stmt * getTerminatorStmt()

unsigned getBlockID() const

AdjacentBlocks::const_iterator const_succ_iterator

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.

std::optional< T > getAs() const

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

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

unsigned getNumBlockIDs() const

Returns the total number of BlockIDs allocated (which start at 0).

llvm::iterator_range< iterator > nodes()

Represents a call to a member function that may be written either with member call syntax (e....

Expr * getImplicitObjectArgument() const

Retrieve the implicit object argument for the member call.

void enqueueBlock(const CFGBlock *Block)

const CFGBlock * dequeue()

A reference to a declared variable, function, enum, etc.

DeclStmt - Adaptor class for mixing declarations with statements and expressions.

const Decl * getSingleDecl() const

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

SourceLocation getBeginLoc() const LLVM_READONLY

This represents one expression.

Expr * IgnoreParens() LLVM_READONLY

Skip past any parentheses which might surround this expression until reaching a fixed point.

bool isLValue() const

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

FullExpr - Represents a "full-expression" node.

llvm::ImmutableSet< const BindingDecl * > liveBindings

llvm::ImmutableSet< const Expr * > liveExprs

llvm::ImmutableSet< const VarDecl * > liveDecls

bool isLive(const Expr *E) const

bool equals(const LivenessValues &V) const

void dumpExprLiveness(const SourceManager &M)

Print to stderr the expression liveness information associated with each basic block.

void dumpBlockLiveness(const SourceManager &M)

Print to stderr the variable liveness information associated with each basic block.

void runOnAllBlocks(Observer &obs)

~LiveVariables() override

static const void * getTag()

bool isLive(const CFGBlock *B, const VarDecl *D)

Return true if a variable is live at the end of a specified block.

static std::unique_ptr< LiveVariables > computeLiveness(AnalysisDeclContext &analysisContext, bool killAtAssign)

Compute the liveness information for a given CFG.

Represents Objective-C's collection statement.

An expression that sends a message to the given Objective-C object or class.

@ SuperInstance

The receiver is the instance of the superclass object.

ReceiverKind getReceiverKind() const

Determine the kind of receiver that this message is being sent to.

OpaqueValueExpr - An expression referring to an opaque object of a fixed type and value class.

A (possibly-)qualified type.

const Type * getTypePtr() const

Retrieves a pointer to the underlying (unqualified) type.

static const void * getTag()

This class handles loading and caching of source files into memory.

RetTy Visit(PTR(Stmt) S, ParamTys... P)

StmtVisitor - This class implements a simple visitor for Stmt subclasses.

Stmt - This represents one statement.

void dump() const

Dumps the specified AST fragment and all subtrees to llvm::errs().

The base class of the type hierarchy.

bool isReferenceType() const

bool isVariableArrayType() const

UnaryExprOrTypeTraitExpr - expression with either a type or (unevaluated) expression operand.

bool isArgumentType() const

UnaryExprOrTypeTrait getKind() const

UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...

Expr * getSubExpr() const

Represents a variable declaration or definition.

Represents a C array with a specified size that is not an integer-constant-expression.

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

A worklist implementation for backward dataflow analysis.

void enqueuePredecessors(const CFGBlock *Block)