1 #include "clang/Analysis/Analyses/LiveVariables.h"
2 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
4 #include "clang/AST/Stmt.h"
5 #include "clang/Analysis/CFG.h"
6 #include "clang/Analysis/AnalysisContext.h"
7 #include "clang/AST/StmtVisitor.h"
9 #include "llvm/ADT/PostOrderIterator.h"
10 #include "llvm/ADT/DenseMap.h"
16 using namespace clang;
20 class DataflowWorklist {
21 SmallVector<const CFGBlock *, 20> worklist;
22 llvm::BitVector enqueuedBlocks;
23 PostOrderCFGView *POV;
25 DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
26 : enqueuedBlocks(cfg.getNumBlockIDs()),
27 POV(Ctx.getAnalysis<PostOrderCFGView>()) {}
29 void enqueueBlock(const CFGBlock *block);
30 void enqueueSuccessors(const CFGBlock *block);
31 void enqueuePredecessors(const CFGBlock *block);
33 const CFGBlock *dequeue();
40 void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
41 if (block && !enqueuedBlocks[block->getBlockID()]) {
42 enqueuedBlocks[block->getBlockID()] = true;
43 worklist.push_back(block);
47 void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
48 const unsigned OldWorklistSize = worklist.size();
49 for (CFGBlock::const_succ_iterator I = block->succ_begin(),
50 E = block->succ_end(); I != E; ++I) {
54 if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
60 void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
61 const unsigned OldWorklistSize = worklist.size();
62 for (CFGBlock::const_pred_iterator I = block->pred_begin(),
63 E = block->pred_end(); I != E; ++I) {
67 if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
73 void DataflowWorklist::sortWorklist() {
74 std::sort(worklist.begin(), worklist.end(), POV->getComparator());
77 const CFGBlock *DataflowWorklist::dequeue() {
80 const CFGBlock *b = worklist.back();
82 enqueuedBlocks[b->getBlockID()] = false;
87 class LiveVariablesImpl {
89 AnalysisDeclContext &analysisContext;
90 std::vector<LiveVariables::LivenessValues> cfgBlockValues;
91 llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
92 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
93 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
94 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
95 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
96 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
97 const bool killAtAssign;
99 LiveVariables::LivenessValues
100 merge(LiveVariables::LivenessValues valsA,
101 LiveVariables::LivenessValues valsB);
103 LiveVariables::LivenessValues runOnBlock(const CFGBlock *block,
104 LiveVariables::LivenessValues val,
105 LiveVariables::Observer *obs = 0);
107 void dumpBlockLiveness(const SourceManager& M);
109 LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign)
110 : analysisContext(ac),
111 SSetFact(false), // Do not canonicalize ImmutableSets by default.
112 DSetFact(false), // This is a *major* performance win.
113 killAtAssign(KillAtAssign) {}
117 static LiveVariablesImpl &getImpl(void *x) {
118 return *((LiveVariablesImpl *) x);
121 //===----------------------------------------------------------------------===//
122 // Operations and queries on LivenessValues.
123 //===----------------------------------------------------------------------===//
125 bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
126 return liveStmts.contains(S);
129 bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
130 return liveDecls.contains(D);
134 template <typename SET>
135 SET mergeSets(SET A, SET B) {
139 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
146 void LiveVariables::Observer::anchor() { }
148 LiveVariables::LivenessValues
149 LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
150 LiveVariables::LivenessValues valsB) {
152 llvm::ImmutableSetRef<const Stmt *>
153 SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()),
154 SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory());
157 llvm::ImmutableSetRef<const VarDecl *>
158 DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()),
159 DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory());
162 SSetRefA = mergeSets(SSetRefA, SSetRefB);
163 DSetRefA = mergeSets(DSetRefA, DSetRefB);
165 // asImmutableSet() canonicalizes the tree, allowing us to do an easy
166 // comparison afterwards.
167 return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(),
168 DSetRefA.asImmutableSet());
171 bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
172 return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
175 //===----------------------------------------------------------------------===//
177 //===----------------------------------------------------------------------===//
179 static bool isAlwaysAlive(const VarDecl *D) {
180 return D->hasGlobalStorage();
183 bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
184 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
187 bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
188 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
191 bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
192 return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
195 //===----------------------------------------------------------------------===//
196 // Dataflow computation.
197 //===----------------------------------------------------------------------===//
200 class TransferFunctions : public StmtVisitor<TransferFunctions> {
201 LiveVariablesImpl &LV;
202 LiveVariables::LivenessValues &val;
203 LiveVariables::Observer *observer;
204 const CFGBlock *currentBlock;
206 TransferFunctions(LiveVariablesImpl &im,
207 LiveVariables::LivenessValues &Val,
208 LiveVariables::Observer *Observer,
209 const CFGBlock *CurrentBlock)
210 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
212 void VisitBinaryOperator(BinaryOperator *BO);
213 void VisitBlockExpr(BlockExpr *BE);
214 void VisitDeclRefExpr(DeclRefExpr *DR);
215 void VisitDeclStmt(DeclStmt *DS);
216 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
217 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
218 void VisitUnaryOperator(UnaryOperator *UO);
223 static const VariableArrayType *FindVA(QualType Ty) {
224 const Type *ty = Ty.getTypePtr();
225 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
226 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
227 if (VAT->getSizeExpr())
230 ty = VT->getElementType().getTypePtr();
236 static const Stmt *LookThroughStmt(const Stmt *S) {
238 if (const Expr *Ex = dyn_cast<Expr>(S))
239 S = Ex->IgnoreParens();
240 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) {
241 S = EWC->getSubExpr();
244 if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) {
245 S = OVE->getSourceExpr();
253 static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set,
254 llvm::ImmutableSet<const Stmt *>::Factory &F,
256 Set = F.add(Set, LookThroughStmt(S));
259 void TransferFunctions::Visit(Stmt *S) {
261 observer->observeStmt(S, currentBlock, val);
263 StmtVisitor<TransferFunctions>::Visit(S);
266 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
269 // Mark all children expressions live.
271 switch (S->getStmtClass()) {
274 case Stmt::StmtExprClass: {
275 // For statement expressions, look through the compound statement.
276 S = cast<StmtExpr>(S)->getSubStmt();
279 case Stmt::CXXMemberCallExprClass: {
280 // Include the implicit "this" pointer as being live.
281 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
282 if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) {
283 AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj);
287 case Stmt::DeclStmtClass: {
288 const DeclStmt *DS = cast<DeclStmt>(S);
289 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
290 for (const VariableArrayType* VA = FindVA(VD->getType());
291 VA != 0; VA = FindVA(VA->getElementType())) {
292 AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr());
297 case Stmt::PseudoObjectExprClass: {
298 // A pseudo-object operation only directly consumes its result
300 Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr();
302 if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child))
303 child = OV->getSourceExpr();
304 child = child->IgnoreParens();
305 val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
309 // FIXME: These cases eventually shouldn't be needed.
310 case Stmt::ExprWithCleanupsClass: {
311 S = cast<ExprWithCleanups>(S)->getSubExpr();
314 case Stmt::CXXBindTemporaryExprClass: {
315 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
318 case Stmt::UnaryExprOrTypeTraitExprClass: {
319 // No need to unconditionally visit subexpressions.
324 for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
326 if (Stmt *child = *it)
327 AddLiveStmt(val.liveStmts, LV.SSetFact, child);
331 void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
332 if (B->isAssignmentOp()) {
333 if (!LV.killAtAssign)
336 // Assigning to a variable?
337 Expr *LHS = B->getLHS()->IgnoreParens();
339 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
340 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
341 // Assignments to references don't kill the ref's address
342 if (VD->getType()->isReferenceType())
345 if (!isAlwaysAlive(VD)) {
346 // The variable is now dead.
347 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
351 observer->observerKill(DR);
356 void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
357 AnalysisDeclContext::referenced_decls_iterator I, E;
359 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
360 for ( ; I != E ; ++I) {
361 const VarDecl *VD = *I;
362 if (isAlwaysAlive(VD))
364 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
368 void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
369 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
370 if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
371 val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
374 void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
375 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
377 if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) {
378 if (!isAlwaysAlive(VD))
379 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
383 void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
384 // Kill the iteration variable.
386 const VarDecl *VD = 0;
388 Stmt *element = OS->getElement();
389 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
390 VD = cast<VarDecl>(DS->getSingleDecl());
392 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
393 VD = cast<VarDecl>(DR->getDecl());
397 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
399 observer->observerKill(DR);
403 void TransferFunctions::
404 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
406 // While sizeof(var) doesn't technically extend the liveness of 'var', it
407 // does extent the liveness of metadata if 'var' is a VariableArrayType.
408 // We handle that special case here.
409 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
412 const Expr *subEx = UE->getArgumentExpr();
413 if (subEx->getType()->isVariableArrayType()) {
414 assert(subEx->isLValue());
415 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
419 void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
420 // Treat ++/-- as a kill.
421 // Note we don't actually have to do anything if we don't have an observer,
422 // since a ++/-- acts as both a kill and a "use".
426 switch (UO->getOpcode()) {
436 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
437 if (isa<VarDecl>(DR->getDecl())) {
438 // Treat ++/-- as a kill.
439 observer->observerKill(DR);
443 LiveVariables::LivenessValues
444 LiveVariablesImpl::runOnBlock(const CFGBlock *block,
445 LiveVariables::LivenessValues val,
446 LiveVariables::Observer *obs) {
448 TransferFunctions TF(*this, val, obs, block);
450 // Visit the terminator (if any).
451 if (const Stmt *term = block->getTerminator())
452 TF.Visit(const_cast<Stmt*>(term));
454 // Apply the transfer function for all Stmts in the block.
455 for (CFGBlock::const_reverse_iterator it = block->rbegin(),
456 ei = block->rend(); it != ei; ++it) {
457 const CFGElement &elem = *it;
458 if (!isa<CFGStmt>(elem))
461 const Stmt *S = cast<CFGStmt>(elem).getStmt();
462 TF.Visit(const_cast<Stmt*>(S));
463 stmtsToLiveness[S] = val;
468 void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
469 const CFG *cfg = getImpl(impl).analysisContext.getCFG();
470 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
471 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
474 LiveVariables::LiveVariables(void *im) : impl(im) {}
476 LiveVariables::~LiveVariables() {
477 delete (LiveVariablesImpl*) impl;
481 LiveVariables::computeLiveness(AnalysisDeclContext &AC,
485 CFG *cfg = AC.getCFG();
489 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
491 // Construct the dataflow worklist. Enqueue the exit block as the
492 // start of the analysis.
493 DataflowWorklist worklist(*cfg, AC);
494 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
496 // FIXME: we should enqueue using post order.
497 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
498 const CFGBlock *block = *it;
499 worklist.enqueueBlock(block);
501 // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
502 // We need to do this because we lack context in the reverse analysis
503 // to determine if a DeclRefExpr appears in such a context, and thus
504 // doesn't constitute a "use".
506 for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
508 if (const CFGStmt *cs = bi->getAs<CFGStmt>()) {
509 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) {
510 if (BO->getOpcode() == BO_Assign) {
511 if (const DeclRefExpr *DR =
512 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
513 LV->inAssignment[DR] = 1;
521 worklist.sortWorklist();
523 while (const CFGBlock *block = worklist.dequeue()) {
524 // Determine if the block's end value has changed. If not, we
525 // have nothing left to do for this block.
526 LivenessValues &prevVal = LV->blocksEndToLiveness[block];
528 // Merge the values of all successor blocks.
530 for (CFGBlock::const_succ_iterator it = block->succ_begin(),
531 ei = block->succ_end(); it != ei; ++it) {
532 if (const CFGBlock *succ = *it) {
533 val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
537 if (!everAnalyzedBlock[block->getBlockID()])
538 everAnalyzedBlock[block->getBlockID()] = true;
539 else if (prevVal.equals(val))
544 // Update the dataflow value for the start of this block.
545 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
547 // Enqueue the value to the predecessors.
548 worklist.enqueuePredecessors(block);
551 return new LiveVariables(LV);
554 static bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
555 return A->getBlockID() < B->getBlockID();
558 static bool compare_vd_entries(const Decl *A, const Decl *B) {
559 SourceLocation ALoc = A->getLocStart();
560 SourceLocation BLoc = B->getLocStart();
561 return ALoc.getRawEncoding() < BLoc.getRawEncoding();
564 void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
565 getImpl(impl).dumpBlockLiveness(M);
568 void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
569 std::vector<const CFGBlock *> vec;
570 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
571 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
573 vec.push_back(it->first);
575 std::sort(vec.begin(), vec.end(), compare_entries);
577 std::vector<const VarDecl*> declVec;
579 for (std::vector<const CFGBlock *>::iterator
580 it = vec.begin(), ei = vec.end(); it != ei; ++it) {
581 llvm::errs() << "\n[ B" << (*it)->getBlockID()
582 << " (live variables at block exit) ]\n";
584 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
587 for (llvm::ImmutableSet<const VarDecl *>::iterator si =
588 vals.liveDecls.begin(),
589 se = vals.liveDecls.end(); si != se; ++si) {
590 declVec.push_back(*si);
593 std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
595 for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
596 de = declVec.end(); di != de; ++di) {
597 llvm::errs() << " " << (*di)->getDeclName().getAsString()
599 (*di)->getLocation().dump(M);
600 llvm::errs() << ">\n";
603 llvm::errs() << "\n";
606 const void *LiveVariables::getTag() { static int x; return &x; }
607 const void *RelaxedLiveVariables::getTag() { static int x; return &x; }