1 //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs ----------*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements Live Variables analysis for source-level CFGs.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Analysis/Analyses/LiveVariables.h"
15 #include "clang/AST/Stmt.h"
16 #include "clang/AST/StmtVisitor.h"
17 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
18 #include "clang/Analysis/AnalysisContext.h"
19 #include "clang/Analysis/CFG.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/Support/raw_ostream.h"
26 using namespace clang;
30 class DataflowWorklist {
31 SmallVector<const CFGBlock *, 20> worklist;
32 llvm::BitVector enqueuedBlocks;
33 PostOrderCFGView *POV;
35 DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
36 : enqueuedBlocks(cfg.getNumBlockIDs()),
37 POV(Ctx.getAnalysis<PostOrderCFGView>()) {}
39 void enqueueBlock(const CFGBlock *block);
40 void enqueueSuccessors(const CFGBlock *block);
41 void enqueuePredecessors(const CFGBlock *block);
43 const CFGBlock *dequeue();
50 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
51 if (block && !enqueuedBlocks[block->getBlockID()]) {
52 enqueuedBlocks[block->getBlockID()] = true;
53 worklist.push_back(block);
57 void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
58 const unsigned OldWorklistSize = worklist.size();
59 for (CFGBlock::const_succ_iterator I = block->succ_begin(),
60 E = block->succ_end(); I != E; ++I) {
64 if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
70 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
71 const unsigned OldWorklistSize = worklist.size();
72 for (CFGBlock::const_pred_iterator I = block->pred_begin(),
73 E = block->pred_end(); I != E; ++I) {
77 if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
83 void DataflowWorklist::sortWorklist() {
84 std::sort(worklist.begin(), worklist.end(), POV->getComparator());
87 const CFGBlock *DataflowWorklist::dequeue() {
90 const CFGBlock *b = worklist.pop_back_val();
91 enqueuedBlocks[b->getBlockID()] = false;
96 class LiveVariablesImpl {
98 AnalysisDeclContext &analysisContext;
99 std::vector<LiveVariables::LivenessValues> cfgBlockValues;
100 llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
101 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
102 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
103 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
104 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
105 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
106 const bool killAtAssign;
108 LiveVariables::LivenessValues
109 merge(LiveVariables::LivenessValues valsA,
110 LiveVariables::LivenessValues valsB);
112 LiveVariables::LivenessValues runOnBlock(const CFGBlock *block,
113 LiveVariables::LivenessValues val,
114 LiveVariables::Observer *obs = 0);
116 void dumpBlockLiveness(const SourceManager& M);
118 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
119 : analysisContext(ac),
120 SSetFact(false), // Do not canonicalize ImmutableSets by default.
121 DSetFact(false), // This is a *major* performance win.
122 killAtAssign(KillAtAssign) {}
126 static LiveVariablesImpl &getImpl(void *x) {
127 return *((LiveVariablesImpl *) x);
130 //===----------------------------------------------------------------------===//
131 // Operations and queries on LivenessValues.
132 //===----------------------------------------------------------------------===//
134 bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
135 return liveStmts.contains(S);
138 bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
139 return liveDecls.contains(D);
143 template <typename SET>
144 SET mergeSets(SET A, SET B) {
148 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
155 void LiveVariables::Observer::anchor() { }
157 LiveVariables::LivenessValues
158 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
159 LiveVariables::LivenessValues valsB) {
161 llvm::ImmutableSetRef<const Stmt *>
162 SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
163 SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
166 llvm::ImmutableSetRef<const VarDecl *>
167 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
168 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
171 SSetRefA = mergeSets(SSetRefA, SSetRefB);
172 DSetRefA = mergeSets(DSetRefA, DSetRefB);
174 // asImmutableSet() canonicalizes the tree, allowing us to do an easy
175 // comparison afterwards.
176 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
177 DSetRefA.asImmutableSet());
180 bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
181 return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
184 //===----------------------------------------------------------------------===//
186 //===----------------------------------------------------------------------===//
188 static bool isAlwaysAlive(const VarDecl *D) {
189 return D->hasGlobalStorage();
192 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
193 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
196 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
197 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
200 bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
201 return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
204 //===----------------------------------------------------------------------===//
205 // Dataflow computation.
206 //===----------------------------------------------------------------------===//
209 class TransferFunctions : public StmtVisitor<TransferFunctions> {
210 LiveVariablesImpl &LV;
211 LiveVariables::LivenessValues &val;
212 LiveVariables::Observer *observer;
213 const CFGBlock *currentBlock;
215 TransferFunctions(LiveVariablesImpl &im,
216 LiveVariables::LivenessValues &Val,
217 LiveVariables::Observer *Observer,
218 const CFGBlock *CurrentBlock)
219 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
221 void VisitBinaryOperator(BinaryOperator *BO);
222 void VisitBlockExpr(BlockExpr *BE);
223 void VisitDeclRefExpr(DeclRefExpr *DR);
224 void VisitDeclStmt(DeclStmt *DS);
225 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
226 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
227 void VisitUnaryOperator(UnaryOperator *UO);
232 static const VariableArrayType *FindVA(QualType Ty) {
233 const Type *ty = Ty.getTypePtr();
234 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
235 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
236 if (VAT->getSizeExpr())
239 ty = VT->getElementType().getTypePtr();
245 static const Stmt *LookThroughStmt(const Stmt *S) {
247 if (const Expr *Ex = dyn_cast<Expr>(S))
248 S = Ex->IgnoreParens();
249 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) {
250 S = EWC->getSubExpr();
253 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) {
254 S = OVE->getSourceExpr();
262 static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
263 llvm::ImmutableSet<const Stmt *>::Factory &F,
265 Set = F.add(Set, LookThroughStmt(S));
268 void TransferFunctions::Visit(Stmt *S) {
270 observer->observeStmt(S, currentBlock, val);
272 StmtVisitor<TransferFunctions>::Visit(S);
275 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
278 // Mark all children expressions live.
280 switch (S->getStmtClass()) {
283 case Stmt::StmtExprClass: {
284 // For statement expressions, look through the compound statement.
285 S = cast<StmtExpr>(S)->getSubStmt();
288 case Stmt::CXXMemberCallExprClass: {
289 // Include the implicit "this" pointer as being live.
290 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
291 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
292 AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
296 case Stmt::ObjCMessageExprClass: {
297 // In calls to super, include the implicit "self" pointer as being live.
298 ObjCMessageExpr *CE = cast<ObjCMessageExpr>(S);
299 if (CE->getReceiverKind() == ObjCMessageExpr::SuperInstance)
300 val.liveDecls = LV.DSetFact.add(val.liveDecls,
301 LV.analysisContext.getSelfDecl());
304 case Stmt::DeclStmtClass: {
305 const DeclStmt *DS = cast<DeclStmt>(S);
306 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
307 for (const VariableArrayType* VA = FindVA(VD->getType());
308 VA != 0; VA = FindVA(VA->getElementType())) {
309 AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
314 case Stmt::PseudoObjectExprClass: {
315 // A pseudo-object operation only directly consumes its result
317 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
319 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
320 child = OV->getSourceExpr();
321 child = child->IgnoreParens();
322 val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
326 // FIXME: These cases eventually shouldn't be needed.
327 case Stmt::ExprWithCleanupsClass: {
328 S = cast<ExprWithCleanups>(S)->getSubExpr();
331 case Stmt::CXXBindTemporaryExprClass: {
332 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
335 case Stmt::UnaryExprOrTypeTraitExprClass: {
336 // No need to unconditionally visit subexpressions.
341 for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
343 if (Stmt *child = *it)
344 AddLiveStmt(val.liveStmts, LV.SSetFact, child);
348 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
349 if (B->isAssignmentOp()) {
350 if (!LV.killAtAssign)
353 // Assigning to a variable?
354 Expr *LHS = B->getLHS()->IgnoreParens();
356 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
357 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
358 // Assignments to references don't kill the ref's address
359 if (VD->getType()->isReferenceType())
362 if (!isAlwaysAlive(VD)) {
363 // The variable is now dead.
364 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
368 observer->observerKill(DR);
373 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
374 AnalysisDeclContext::referenced_decls_iterator I, E;
376 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
377 for ( ; I != E ; ++I) {
378 const VarDecl *VD = *I;
379 if (isAlwaysAlive(VD))
381 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
385 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
386 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
387 if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
388 val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
391 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
392 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
394 if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) {
395 if (!isAlwaysAlive(VD))
396 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
400 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
401 // Kill the iteration variable.
403 const VarDecl *VD = 0;
405 Stmt *element = OS->getElement();
406 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
407 VD = cast<VarDecl>(DS->getSingleDecl());
409 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
410 VD = cast<VarDecl>(DR->getDecl());
414 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
416 observer->observerKill(DR);
420 void TransferFunctions::
421 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
423 // While sizeof(var) doesn't technically extend the liveness of 'var', it
424 // does extent the liveness of metadata if 'var' is a VariableArrayType.
425 // We handle that special case here.
426 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
429 const Expr *subEx = UE->getArgumentExpr();
430 if (subEx->getType()->isVariableArrayType()) {
431 assert(subEx->isLValue());
432 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
436 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
437 // Treat ++/-- as a kill.
438 // Note we don't actually have to do anything if we don't have an observer,
439 // since a ++/-- acts as both a kill and a "use".
443 switch (UO->getOpcode()) {
453 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
454 if (isa<VarDecl>(DR->getDecl())) {
455 // Treat ++/-- as a kill.
456 observer->observerKill(DR);
460 LiveVariables::LivenessValues
461 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
462 LiveVariables::LivenessValues val,
463 LiveVariables::Observer *obs) {
465 TransferFunctions TF(*this, val, obs, block);
467 // Visit the terminator (if any).
468 if (const Stmt *term = block->getTerminator())
469 TF.Visit(const_cast<Stmt*>(term));
471 // Apply the transfer function for all Stmts in the block.
472 for (CFGBlock::const_reverse_iterator it = block->rbegin(),
473 ei = block->rend(); it != ei; ++it) {
474 const CFGElement &elem = *it;
476 if (Optional<CFGAutomaticObjDtor> Dtor =
477 elem.getAs<CFGAutomaticObjDtor>()) {
478 val.liveDecls = DSetFact.add(val.liveDecls, Dtor->getVarDecl());
482 if (!elem.getAs<CFGStmt>())
485 const Stmt *S = elem.castAs<CFGStmt>().getStmt();
486 TF.Visit(const_cast<Stmt*>(S));
487 stmtsToLiveness[S] = val;
492 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
493 const CFG *cfg = getImpl(impl).analysisContext.getCFG();
494 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
495 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
498 LiveVariables::LiveVariables(void *im) : impl(im) {}
500 LiveVariables::~LiveVariables() {
501 delete (LiveVariablesImpl*) impl;
505 LiveVariables::computeLiveness(AnalysisDeclContext &AC,
509 CFG *cfg = AC.getCFG();
513 // The analysis currently has scalability issues for very large CFGs.
514 // Bail out if it looks too large.
515 if (cfg->getNumBlockIDs() > 300000)
518 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
520 // Construct the dataflow worklist. Enqueue the exit block as the
521 // start of the analysis.
522 DataflowWorklist worklist(*cfg, AC);
523 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
525 // FIXME: we should enqueue using post order.
526 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
527 const CFGBlock *block = *it;
528 worklist.enqueueBlock(block);
530 // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
531 // We need to do this because we lack context in the reverse analysis
532 // to determine if a DeclRefExpr appears in such a context, and thus
533 // doesn't constitute a "use".
535 for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
537 if (Optional<CFGStmt> cs = bi->getAs<CFGStmt>()) {
538 if (const BinaryOperator *BO =
539 dyn_cast<BinaryOperator>(cs->getStmt())) {
540 if (BO->getOpcode() == BO_Assign) {
541 if (const DeclRefExpr *DR =
542 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
543 LV->inAssignment[DR] = 1;
551 worklist.sortWorklist();
553 while (const CFGBlock *block = worklist.dequeue()) {
554 // Determine if the block's end value has changed. If not, we
555 // have nothing left to do for this block.
556 LivenessValues &prevVal = LV->blocksEndToLiveness[block];
558 // Merge the values of all successor blocks.
560 for (CFGBlock::const_succ_iterator it = block->succ_begin(),
561 ei = block->succ_end(); it != ei; ++it) {
562 if (const CFGBlock *succ = *it) {
563 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
567 if (!everAnalyzedBlock[block->getBlockID()])
568 everAnalyzedBlock[block->getBlockID()] = true;
569 else if (prevVal.equals(val))
574 // Update the dataflow value for the start of this block.
575 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
577 // Enqueue the value to the predecessors.
578 worklist.enqueuePredecessors(block);
581 return new LiveVariables(LV);
584 static bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
585 return A->getBlockID() < B->getBlockID();
588 static bool compare_vd_entries(const Decl *A, const Decl *B) {
589 SourceLocation ALoc = A->getLocStart();
590 SourceLocation BLoc = B->getLocStart();
591 return ALoc.getRawEncoding() < BLoc.getRawEncoding();
594 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
595 getImpl(impl).dumpBlockLiveness(M);
598 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
599 std::vector<const CFGBlock *> vec;
600 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
601 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
603 vec.push_back(it->first);
605 std::sort(vec.begin(), vec.end(), compare_entries);
607 std::vector<const VarDecl*> declVec;
609 for (std::vector<const CFGBlock *>::iterator
610 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
611 llvm::errs() << "\n[ B" << (*it)->getBlockID()
612 << " (live variables at block exit) ]\n";
614 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
617 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
618 vals.liveDecls.begin(),
619 se = vals.liveDecls.end(); si != se; ++si) {
620 declVec.push_back(*si);
623 std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
625 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
626 de = declVec.end(); di != de; ++di) {
627 llvm::errs() << " " << (*di)->getDeclName().getAsString()
629 (*di)->getLocation().dump(M);
630 llvm::errs() << ">\n";
633 llvm::errs() << "\n";
636 const void *LiveVariables::getTag() { static int x; return &x; }
637 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }