19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/Support/raw_ostream.h"
24 using namespace clang;
27 class LiveVariablesImpl {
30 llvm::ImmutableSet<const Expr *>::Factory ESetFact;
31 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
32 llvm::ImmutableSet<const BindingDecl *>::Factory BSetFact;
33 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
34 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
35 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
36 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
37 const bool killAtAssign;
51 : analysisContext(ac),
54 BSetFact(
false), killAtAssign(KillAtAssign) {}
59 return *((LiveVariablesImpl *)
x);
71 if (
const auto *DD = dyn_cast<DecompositionDecl>(D)) {
74 alive |= liveBindings.contains(BD);
77 return liveDecls.contains(D);
81 template <
typename SET>
82 SET mergeSets(SET A, SET B) {
86 for (
typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
93 void LiveVariables::Observer::anchor() { }
99 llvm::ImmutableSetRef<const Expr *> SSetRefA(
100 valsA.
liveExprs.getRootWithoutRetain(), ESetFact.getTreeFactory()),
101 SSetRefB(valsB.
liveExprs.getRootWithoutRetain(),
102 ESetFact.getTreeFactory());
104 llvm::ImmutableSetRef<const VarDecl *>
105 DSetRefA(valsA.
liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
106 DSetRefB(valsB.
liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
108 llvm::ImmutableSetRef<const BindingDecl *>
109 BSetRefA(valsA.
liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory()),
110 BSetRefB(valsB.
liveBindings.getRootWithoutRetain(), BSetFact.getTreeFactory());
112 SSetRefA = mergeSets(SSetRefA, SSetRefB);
113 DSetRefA = mergeSets(DSetRefA, DSetRefB);
114 BSetRefA = mergeSets(BSetRefA, BSetRefB);
119 DSetRefA.asImmutableSet(),
120 BSetRefA.asImmutableSet());
124 return liveExprs ==
V.liveExprs && liveDecls ==
V.liveDecls;
144 return getImpl(impl).stmtsToLiveness[Loc].isLive(Val);
152 class TransferFunctions :
public StmtVisitor<TransferFunctions> {
153 LiveVariablesImpl &LV;
158 TransferFunctions(LiveVariablesImpl &im,
162 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
177 while (
const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
179 if (VAT->getSizeExpr())
182 ty = VT->getElementType().getTypePtr();
190 if (
const Expr *Ex = dyn_cast<Expr>(E))
192 if (
const FullExpr *FE = dyn_cast<FullExpr>(E)) {
193 E = FE->getSubExpr();
197 E = OVE->getSourceExpr();
206 llvm::ImmutableSet<const Expr *>::Factory &F,
211 void TransferFunctions::Visit(
Stmt *S) {
213 observer->observeStmt(S, currentBlock, val);
217 if (
const auto *E = dyn_cast<Expr>(S)) {
218 val.liveExprs = LV.ESetFact.remove(val.liveExprs, E);
223 switch (S->getStmtClass()) {
226 case Stmt::StmtExprClass: {
228 S = cast<StmtExpr>(S)->getSubStmt();
231 case Stmt::CXXMemberCallExprClass: {
235 AddLiveExpr(val.liveExprs, LV.ESetFact, ImplicitObj);
239 case Stmt::ObjCMessageExprClass: {
243 val.liveDecls = LV.DSetFact.add(val.liveDecls,
244 LV.analysisContext.getSelfDecl());
247 case Stmt::DeclStmtClass: {
248 const DeclStmt *DS = cast<DeclStmt>(S);
251 VA !=
nullptr; VA =
FindVA(VA->getElementType())) {
252 AddLiveExpr(val.liveExprs, LV.ESetFact, VA->getSizeExpr());
257 case Stmt::PseudoObjectExprClass: {
260 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
263 child = OV->getSourceExpr();
265 val.liveExprs = LV.ESetFact.add(val.liveExprs, child);
270 case Stmt::ExprWithCleanupsClass: {
271 S = cast<ExprWithCleanups>(S)->getSubExpr();
274 case Stmt::CXXBindTemporaryExprClass: {
275 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
278 case Stmt::UnaryExprOrTypeTraitExprClass: {
282 case Stmt::IfStmtClass: {
286 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<IfStmt>(S)->getCond());
289 case Stmt::WhileStmtClass: {
293 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<WhileStmt>(S)->getCond());
296 case Stmt::DoStmtClass: {
300 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<DoStmt>(S)->getCond());
303 case Stmt::ForStmtClass: {
307 AddLiveExpr(val.liveExprs, LV.ESetFact, cast<ForStmt>(S)->getCond());
316 for (
Stmt *Child : S->children()) {
317 if (
const auto *E = dyn_cast_or_null<Expr>(Child))
328 if (LV.killAtAssign && B->
getOpcode() == BO_Assign) {
330 LV.inAssignment[DR] = 1;
334 if (!LV.killAtAssign)
340 if (
DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) {
341 const Decl* D = DR->getDecl();
344 if (
const BindingDecl* BD = dyn_cast<BindingDecl>(D)) {
345 Killed = !BD->getType()->isReferenceType();
347 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
348 }
else if (
const auto *VD = dyn_cast<VarDecl>(D)) {
351 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
355 if (Killed && observer)
356 observer->observerKill(DR);
361 void TransferFunctions::VisitBlockExpr(
BlockExpr *BE) {
363 LV.analysisContext.getReferencedBlockVars(BE->
getBlockDecl())) {
366 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
370 void TransferFunctions::VisitDeclRefExpr(
DeclRefExpr *DR) {
372 bool InAssignment = LV.inAssignment[DR];
373 if (
const auto *BD = dyn_cast<BindingDecl>(D)) {
375 val.liveBindings = LV.BSetFact.
add(val.liveBindings, BD);
376 }
else if (
const auto *VD = dyn_cast<VarDecl>(D)) {
378 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
382 void TransferFunctions::VisitDeclStmt(
DeclStmt *DS) {
383 for (
const auto *DI : DS->
decls()) {
384 if (
const auto *DD = dyn_cast<DecompositionDecl>(DI)) {
385 for (
const auto *BD : DD->bindings())
386 val.liveBindings = LV.BSetFact.remove(val.liveBindings, BD);
387 }
else if (
const auto *VD = dyn_cast<VarDecl>(DI)) {
389 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
399 Stmt *element =
OS->getElement();
400 if (
DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
403 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
404 VD = cast<VarDecl>(DR->
getDecl());
408 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
410 observer->observerKill(DR);
414 void TransferFunctions::
426 val.liveExprs = LV.ESetFact.add(val.liveExprs, subEx->
IgnoreParens());
430 void TransferFunctions::VisitUnaryOperator(
UnaryOperator *UO) {
449 if (isa<VarDecl>(D) || isa<BindingDecl>(D)) {
451 observer->observerKill(DR);
461 TransferFunctions TF(*
this, val, obs, block);
465 TF.Visit(
const_cast<Stmt*
>(term));
469 ei = block->
rend(); it != ei; ++it) {
482 TF.Visit(
const_cast<Stmt*
>(S));
483 stmtsToLiveness[S] = val;
489 const CFG *cfg =
getImpl(impl).analysisContext.getCFG();
491 getImpl(impl).runOnBlock(*it,
getImpl(impl).blocksEndToLiveness[*it], &obs);
494 LiveVariables::LiveVariables(
void *im) : impl(im) {}
497 delete (LiveVariablesImpl*) impl;
500 std::unique_ptr<LiveVariables>
513 LiveVariablesImpl *LV =
new LiveVariablesImpl(AC, killAtAssign);
533 ei = block->
succ_end(); it != ei; ++it) {
535 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
540 everAnalyzedBlock[block->
getBlockID()] =
true;
541 else if (prevVal.
equals(val))
547 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
553 return std::unique_ptr<LiveVariables>(
new LiveVariables(LV));
557 getImpl(impl).dumpBlockLiveness(M);
560 void LiveVariablesImpl::dumpBlockLiveness(
const SourceManager &M) {
561 std::vector<const CFGBlock *> vec;
562 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
563 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
565 vec.push_back(it->first);
571 std::vector<const VarDecl*> declVec;
573 for (std::vector<const CFGBlock *>::iterator
574 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
575 llvm::errs() <<
"\n[ B" << (*it)->getBlockID()
576 <<
" (live variables at block exit) ]\n";
581 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
583 se = vals.
liveDecls.end(); si != se; ++si) {
584 declVec.push_back(*si);
587 llvm::sort(declVec, [](
const Decl *A,
const Decl *B) {
591 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
592 de = declVec.end(); di != de; ++di) {
593 llvm::errs() <<
" " << (*di)->getDeclName().getAsString()
595 (*di)->getLocation().print(llvm::errs(), M);
596 llvm::errs() <<
">\n";
599 llvm::errs() <<
"\n";
603 getImpl(impl).dumpExprLiveness(M);
606 void LiveVariablesImpl::dumpExprLiveness(
const SourceManager &M) {
608 for (
const CFGBlock *B : *analysisContext.getCFG()) {
610 llvm::errs() <<
"\n[ B" << B->getBlockID()
611 <<
" (live expressions at block exit) ]\n";
612 for (
const Expr *E : blocksEndToLiveness[B].liveExprs) {
613 llvm::errs() <<
"\n";
616 llvm::errs() <<
"\n";