LiveVariables.cpp Source File (original) (raw)

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

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

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

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

24#include

25#include

27using namespace clang;

29namespace {

30class LiveVariablesImpl {

31public:

32 AnalysisDeclContext &analysisContext;

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

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

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

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

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

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

39 llvm::DenseSet<const DeclRefExpr *> inAssignment;

40 const bool killAtAssign;

42 LiveVariables::LivenessValues

43 merge(LiveVariables::LivenessValues valsA,

44 LiveVariables::LivenessValues valsB);

46 LiveVariables::LivenessValues

47 runOnBlock(const CFGBlock *block, LiveVariables::LivenessValues val,

48 LiveVariables::Observer *obs = nullptr);

50 void dumpBlockLiveness(const SourceManager& M);

51 void dumpExprLiveness(const SourceManager& M);

53 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)

54 : analysisContext(ac),

55 ESetFact(false),

56 DSetFact(false),

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

58};

59}

61static LiveVariablesImpl &getImpl(void *x) {

62 return *((LiveVariablesImpl *) x);

63}

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

79 return true;

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

83 return true;

84 }

85 return false;

86 }

88}

90namespace {

91 template

92 SET mergeSets(SET A, SET B) {

93 if (A.isEmpty())

94 return B;

96 for (const auto *Elem : B) {

97 A = A.add(Elem);

98 }

99 return A;

100 }

101}

102

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

104

105LiveVariables::LivenessValues

106LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,

107 LiveVariables::LivenessValues valsB) {

108

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

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

111 SSetRefB(valsB.liveExprs.getRootWithoutRetain(),

112 ESetFact.getTreeFactory());

113

114 llvm::ImmutableSetRef<const VarDecl *>

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

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

117

118 llvm::ImmutableSetRef<const BindingDecl *>

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

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

121

122 SSetRefA = mergeSets(SSetRefA, SSetRefB);

123 DSetRefA = mergeSets(DSetRefA, DSetRefB);

124 BSetRefA = mergeSets(BSetRefA, BSetRefB);

125

126

127

128 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),

129 DSetRefA.asImmutableSet(),

130 BSetRefA.asImmutableSet());

131}

132

137

138

139

140

141

145

149

153

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

156}

157

158

159

160

161

162namespace {

163class TransferFunctions : public StmtVisitor {

164 LiveVariablesImpl &LV;

167 const CFGBlock *currentBlock;

168public:

169 TransferFunctions(LiveVariablesImpl &im,

172 const CFGBlock *CurrentBlock)

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

174

176 void VisitBlockExpr(BlockExpr *BE);

178 void VisitDeclStmt(DeclStmt *DS);

181 void Visit(Stmt *S);

182};

183}

184

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

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

189 if (VAT->getSizeExpr())

190 return VAT;

191

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

193 }

194

195 return nullptr;

196}

197

199 while (E) {

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

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

203 E = FE->getSubExpr();

204 continue;

205 }

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

207 E = OVE->getSourceExpr();

208 continue;

209 }

210 break;

211 }

212 return E;

213}

214

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

217 const Expr *E) {

219}

220

221

222

223

224

225

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

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

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

234 }

235}

236

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

238 if (observer)

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

240

242

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

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

245 }

246

247

248

250 default:

251 break;

252 case Stmt::StmtExprClass: {

253

255 break;

256 }

257 case Stmt::CXXMemberCallExprClass: {

258

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

262 }

263 break;

264 }

265 case Stmt::ObjCMessageExprClass: {

266

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

270 LV.analysisContext.getSelfDecl());

271 break;

272 }

273 case Stmt::DeclStmtClass: {

275 if (const VarDecl *VD = dyn_cast(DS->getSingleDecl())) {

276 for (const VariableArrayType* VA = FindVA(VD->getType());

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

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

279 }

280 }

281 break;

282 }

283 case Stmt::PseudoObjectExprClass: {

284

285

287 if (!child) return;

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

289 child = OV->getSourceExpr();

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

292 return;

293 }

294

295

296 case Stmt::ExprWithCleanupsClass: {

298 break;

299 }

300 case Stmt::CXXBindTemporaryExprClass: {

302 break;

303 }

304 case Stmt::UnaryExprOrTypeTraitExprClass: {

305

306 return;

307 }

308 case Stmt::IfStmtClass: {

309

310

311

313 return;

314 }

315 case Stmt::WhileStmtClass: {

316

317

318

320 return;

321 }

322 case Stmt::DoStmtClass: {

323

324

325

327 return;

328 }

329 case Stmt::ForStmtClass: {

330

331

332

334 return;

335 }

336 case Stmt::ConditionalOperatorClass: {

337

338

339

340

341

342

343

344

345

346

347

348

349

350

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

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

355 return;

356 }

357 }

358

359

360

361

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

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

364 AddLiveExpr(val.liveExprs, LV.ESetFact, E);

365 }

366}

367

372

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

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

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

376 LV.inAssignment.insert(DR);

377 }

378 }

380 if (!LV.killAtAssign)

381 return;

382

383

385

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

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

388 bool Killed = false;

389

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

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

392 if (Killed) {

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

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

395

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

397 }

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

400 if (Killed)

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

402 }

403 }

404 }

405}

406

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

408 for (const VarDecl *VD :

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

452void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {

453

454 DeclRefExpr *DR = nullptr;

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()))) {

463 }

464

465 if (VD) {

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

467 }

468}

469

470void TransferFunctions::

471VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)

472{

473

474

475

477 return;

478

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

483 }

484}

485

486LiveVariables::LivenessValues

487LiveVariablesImpl::runOnBlock(const CFGBlock *block,

488 LiveVariables::LivenessValues val,

489 LiveVariables::Observer *obs) {

490

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

492

493

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

496

497

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

500 const CFGElement &elem = *it;

501

502 if (std::optional Dtor =

503 elem.getAs()) {

505 continue;

506 }

507

508 if (!elem.getAs())

509 continue;

510

511 const Stmt *S = elem.castAs().getStmt();

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

513 stmtsToLiveness[S] = val;

514 }

515 return val;

516}

517

521 getImpl(impl).runOnBlock(B, getImpl(impl).blocksEndToLiveness[B], &obs);

522}

523

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

525

527 delete (LiveVariablesImpl*) impl;

528}

529

530std::unique_ptr

532

533

535 if (!cfg)

536 return nullptr;

537

538

539

541 return nullptr;

542

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

544

545

546

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

549

550

553 }

554

556

557

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

559

560

563 if (succ) {

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

565 }

566 }

567

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

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

570 else if (prevVal == val)

571 continue;

572

573 prevVal = val;

574

575

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

577

578

580 }

581

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

583}

584

586 getImpl(impl).dumpBlockLiveness(M);

587}

588

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

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

591 vec.reserve(blocksEndToLiveness.size());

592 llvm::append_range(vec, llvm::make_first_range(blocksEndToLiveness));

595 });

596

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

598

599 for (const CFGBlock *block : vec) {

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

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

602 declVec.clear();

603 llvm::append_range(declVec, blocksEndToLiveness[block].liveDecls);

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

606 });

607

608 for (const VarDecl *VD : declVec) {

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

612 }

613 }

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

615}

616

618 getImpl(impl).dumpExprLiveness(M);

619}

620

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

622 const ASTContext &Ctx = analysisContext.getASTContext();

623 auto ByIDs = [&Ctx](const Expr *L, const Expr *R) {

624 return L->getID(Ctx) < R->getID(Ctx);

625 };

626

627

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

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

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

631 std::vector<const Expr *> LiveExprs;

632 llvm::append_range(LiveExprs, blocksEndToLiveness[B].liveExprs);

633 llvm::sort(LiveExprs, ByIDs);

634 for (const Expr *E : LiveExprs) {

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

636 E->dump();

637 }

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

639 }

640}

641

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)

Definition LiveVariables.cpp:368

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

Definition LiveVariables.cpp:215

static LiveVariablesImpl & getImpl(void *x)

Definition LiveVariables.cpp:61

static const Expr * LookThroughExpr(const Expr *E)

Definition LiveVariables.cpp:198

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.

Definition LiveVariables.cpp:226

static bool isAlwaysAlive(const VarDecl *D)

Definition LiveVariables.cpp:142

Defines the SourceManager interface.

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

Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...

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 a single basic block in a source-level CFG.

reverse_iterator rbegin()

ElementList::const_reverse_iterator const_reverse_iterator

Stmt * getTerminatorStmt()

unsigned getBlockID() const

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

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 getLocation() const

SourceLocation getBeginLoc() const LLVM_READONLY

std::string getAsString() const

Retrieve the human-readable string for this name.

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

bool operator==(const LivenessValues &V) const

Definition LiveVariables.cpp:133

llvm::ImmutableSet< const VarDecl * > liveDecls

bool isLive(const Expr *E) const

Definition LiveVariables.cpp:69

void dumpExprLiveness(const SourceManager &M)

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

Definition LiveVariables.cpp:617

void dumpBlockLiveness(const SourceManager &M)

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

Definition LiveVariables.cpp:585

void runOnAllBlocks(Observer &obs)

Definition LiveVariables.cpp:518

~LiveVariables() override

Definition LiveVariables.cpp:526

static const void * getTag()

Definition LiveVariables.cpp:642

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

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

Definition LiveVariables.cpp:146

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

Compute the liveness information for a given CFG.

Definition LiveVariables.cpp:531

DeclarationName getDeclName() const

Get the actual, stored name of the declaration, which may be a special name.

Represents Objective-C's collection statement.

@ 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()

Definition LiveVariables.cpp:643

void print(raw_ostream &OS, const SourceManager &SM) const

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

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

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

Stmt - This represents one statement.

StmtClass getStmtClass() const

int64_t getID(const ASTContext &Context) const

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

Represents a variable declaration or definition.

bool hasGlobalStorage() const

Returns true for all variables that do not have local storage.

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

@ OS

Indicates that the tracking object is a descendant of a referenced-counted OSObject,...

std::variant< struct RequiresDecl, struct HeaderDecl, struct UmbrellaDirDecl, struct ModuleDecl, struct ExcludeDecl, struct ExportDecl, struct ExportAsDecl, struct ExternModuleDecl, struct UseDecl, struct LinkDecl, struct ConfigMacrosDecl, struct ConflictDecl > Decl

All declarations that can appear in a module declaration.

RangeSelector merge(RangeSelector First, RangeSelector Second)

Selects the merge of the two ranges, i.e.

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

U cast(CodeGen::Address addr)

A worklist implementation for backward dataflow analysis.

void enqueuePredecessors(const CFGBlock *Block)