LiveVariables.cpp revision 9c378f705405d37f49795d5e915989de774fe11f 
1#include "clang/Analysis/Analyses/LiveVariables.h"
2#include "clang/AST/Stmt.h"
3#include "clang/Analysis/CFG.h"
4#include "clang/Analysis/AnalysisContext.h"
5#include "clang/AST/StmtVisitor.h"
6
7#include <deque>
8#include <algorithm>
9#include <vector>
10
11using namespace clang;
12
13namespace {
14  class LiveVariablesImpl {
15  public:
16    AnalysisContext &analysisContext;
17    std::vector<LiveVariables::LivenessValues> cfgBlockValues;
18    llvm::ImmutableSet<const Stmt *>::Factory SSetFact;
19    llvm::ImmutableSet<const VarDecl *>::Factory DSetFact;
20    llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness;
21    llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness;
22    llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness;
23    llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment;
24    const bool killAtAssign;
25
26    LiveVariables::LivenessValues
27    merge(LiveVariables::LivenessValues valsA,
28          LiveVariables::LivenessValues valsB);
29
30    LiveVariables::LivenessValues runOnBlock(const CFGBlock *block,
31                                             LiveVariables::LivenessValues val,
32                                             LiveVariables::Observer *obs = 0);
33
34    void dumpBlockLiveness(const SourceManager& M);
35
36    LiveVariablesImpl(AnalysisContext &ac, bool KillAtAssign)
37      : analysisContext(ac), killAtAssign(KillAtAssign) {}
38  };
39}
40
41static LiveVariablesImpl &getImpl(void *x) {
42  return *((LiveVariablesImpl *) x);
43}
44
45//===----------------------------------------------------------------------===//
46// Operations and queries on LivenessValues.
47//===----------------------------------------------------------------------===//
48
49bool LiveVariables::LivenessValues::isLive(const Stmt *S) const {
50  return liveStmts.contains(S);
51}
52
53bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const {
54  return liveDecls.contains(D);
55}
56
57namespace {
58  template <typename SET>
59  SET mergeSets(typename SET::Factory &F, SET A, SET B) {
60    for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) {
61      A = F.add(A, *it);
62    }
63    return A;
64  }
65}
66
67LiveVariables::LivenessValues
68LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA,
69                         LiveVariables::LivenessValues valsB) {
70  return LiveVariables::LivenessValues(mergeSets(SSetFact, valsA.liveStmts, valsB.liveStmts),
71                        mergeSets(DSetFact, valsA.liveDecls, valsB.liveDecls));
72}
73
74bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const {
75  return liveStmts == V.liveStmts && liveDecls == V.liveDecls;
76}
77
78//===----------------------------------------------------------------------===//
79// Query methods.
80//===----------------------------------------------------------------------===//
81
82static bool isAlwaysAlive(const VarDecl *D) {
83  return D->hasGlobalStorage();
84}
85
86bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) {
87  return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D);
88}
89
90bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) {
91  return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D);
92}
93
94bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) {
95  return getImpl(impl).stmtsToLiveness[Loc].isLive(S);
96}
97
98//===----------------------------------------------------------------------===//
99// Dataflow computation.
100//===----------------------------------------------------------------------===//
101
102namespace {
103class Worklist {
104  llvm::BitVector isBlockEnqueued;
105  std::deque<const CFGBlock *> workListContents;
106public:
107  Worklist(CFG &cfg) : isBlockEnqueued(cfg.getNumBlockIDs()) {}
108
109  bool empty() const { return workListContents.empty(); }
110
111  const CFGBlock *getNextItem() {
112    const CFGBlock *block = workListContents.front();
113    workListContents.pop_front();
114    isBlockEnqueued[block->getBlockID()] = false;
115    return block;
116  }
117
118  void enqueueBlock(const CFGBlock *block) {
119    if (!isBlockEnqueued[block->getBlockID()]) {
120      isBlockEnqueued[block->getBlockID()] = true;
121      workListContents.push_back(block);
122    }
123  }
124};
125
126class TransferFunctions : public StmtVisitor<TransferFunctions> {
127  LiveVariablesImpl &LV;
128  LiveVariables::LivenessValues &val;
129  LiveVariables::Observer *observer;
130  const CFGBlock *currentBlock;
131public:
132  TransferFunctions(LiveVariablesImpl &im,
133                    LiveVariables::LivenessValues &Val,
134                    LiveVariables::Observer *Observer,
135                    const CFGBlock *CurrentBlock)
136  : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {}
137
138  void VisitBinaryOperator(BinaryOperator *BO);
139  void VisitBlockExpr(BlockExpr *BE);
140  void VisitDeclRefExpr(DeclRefExpr *DR);
141  void VisitDeclStmt(DeclStmt *DS);
142  void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS);
143  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE);
144  void VisitUnaryOperator(UnaryOperator *UO);
145  void Visit(Stmt *S);
146};
147}
148
149static const VariableArrayType *FindVA(QualType Ty) {
150  const Type *ty = Ty.getTypePtr();
151  while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) {
152    if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT))
153      if (VAT->getSizeExpr())
154        return VAT;
155
156    ty = VT->getElementType().getTypePtr();
157  }
158
159  return 0;
160}
161
162void TransferFunctions::Visit(Stmt *S) {
163  if (observer)
164    observer->observeStmt(S, currentBlock, val);
165
166  StmtVisitor<TransferFunctions>::Visit(S);
167
168  if (isa<Expr>(S)) {
169    val.liveStmts = LV.SSetFact.remove(val.liveStmts, S);
170  }
171
172  // Mark all children expressions live.
173
174  switch (S->getStmtClass()) {
175    default:
176      break;
177    case Stmt::StmtExprClass: {
178      // For statement expressions, look through the compound statement.
179      S = cast<StmtExpr>(S)->getSubStmt();
180      break;
181    }
182    case Stmt::CXXMemberCallExprClass: {
183      // Include the implicit "this" pointer as being live.
184      CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S);
185      val.liveStmts =
186        LV.SSetFact.add(val.liveStmts,
187                        CE->getImplicitObjectArgument()->IgnoreParens());
188      break;
189    }
190    case Stmt::DeclStmtClass: {
191      const DeclStmt *DS = cast<DeclStmt>(S);
192      if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) {
193        for (const VariableArrayType* VA = FindVA(VD->getType());
194             VA != 0; VA = FindVA(VA->getElementType())) {
195          val.liveStmts = LV.SSetFact.add(val.liveStmts,
196                                          VA->getSizeExpr()->IgnoreParens());
197        }
198      }
199      break;
200    }
201    // FIXME: These cases eventually shouldn't be needed.
202    case Stmt::ExprWithCleanupsClass: {
203      S = cast<ExprWithCleanups>(S)->getSubExpr();
204      break;
205    }
206    case Stmt::CXXBindTemporaryExprClass: {
207      S = cast<CXXBindTemporaryExpr>(S)->getSubExpr();
208      break;
209    }
210    case Stmt::MaterializeTemporaryExprClass: {
211      S = cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr();
212      break;
213    }
214    case Stmt::UnaryExprOrTypeTraitExprClass: {
215      // No need to unconditionally visit subexpressions.
216      return;
217    }
218  }
219
220  for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end();
221       it != ei; ++it) {
222    if (Stmt *child = *it) {
223      if (Expr *Ex = dyn_cast<Expr>(child))
224        child = Ex->IgnoreParens();
225
226      val.liveStmts = LV.SSetFact.add(val.liveStmts, child);
227    }
228  }
229}
230
231void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) {
232  if (B->isAssignmentOp()) {
233    if (!LV.killAtAssign)
234      return;
235
236    // Assigning to a variable?
237    Expr *LHS = B->getLHS()->IgnoreParens();
238
239    if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS))
240      if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) {
241        // Assignments to references don't kill the ref's address
242        if (VD->getType()->isReferenceType())
243          return;
244
245        if (!isAlwaysAlive(VD)) {
246          // The variable is now dead.
247          val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
248        }
249
250        if (observer)
251          observer->observerKill(DR);
252      }
253  }
254}
255
256void TransferFunctions::VisitBlockExpr(BlockExpr *BE) {
257  AnalysisContext::referenced_decls_iterator I, E;
258  llvm::tie(I, E) =
259    LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl());
260  for ( ; I != E ; ++I) {
261    const VarDecl *VD = *I;
262    if (isAlwaysAlive(VD))
263      continue;
264    val.liveDecls = LV.DSetFact.add(val.liveDecls, VD);
265  }
266}
267
268void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) {
269  if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl()))
270    if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end())
271      val.liveDecls = LV.DSetFact.add(val.liveDecls, D);
272}
273
274void TransferFunctions::VisitDeclStmt(DeclStmt *DS) {
275  for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end();
276       DI != DE; ++DI)
277    if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) {
278      if (!isAlwaysAlive(VD))
279        val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
280    }
281}
282
283void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) {
284  // Kill the iteration variable.
285  DeclRefExpr *DR = 0;
286  const VarDecl *VD = 0;
287
288  Stmt *element = OS->getElement();
289  if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) {
290    VD = cast<VarDecl>(DS->getSingleDecl());
291  }
292  else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) {
293    VD = cast<VarDecl>(DR->getDecl());
294  }
295
296  if (VD) {
297    val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD);
298    if (observer && DR)
299      observer->observerKill(DR);
300  }
301}
302
303void TransferFunctions::
304VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE)
305{
306  // While sizeof(var) doesn't technically extend the liveness of 'var', it
307  // does extent the liveness of metadata if 'var' is a VariableArrayType.
308  // We handle that special case here.
309  if (UE->getKind() != UETT_SizeOf || UE->isArgumentType())
310    return;
311
312  const Expr *subEx = UE->getArgumentExpr();
313  if (subEx->getType()->isVariableArrayType()) {
314    assert(subEx->isLValue());
315    val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens());
316  }
317}
318
319void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) {
320  // Treat ++/-- as a kill.
321  // Note we don't actually have to do anything if we don't have an observer,
322  // since a ++/-- acts as both a kill and a "use".
323  if (!observer)
324    return;
325
326  switch (UO->getOpcode()) {
327  default:
328    return;
329  case UO_PostInc:
330  case UO_PostDec:
331  case UO_PreInc:
332  case UO_PreDec:
333    break;
334  }
335
336  if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens()))
337    if (isa<VarDecl>(DR->getDecl())) {
338      // Treat ++/-- as a kill.
339      observer->observerKill(DR);
340    }
341}
342
343LiveVariables::LivenessValues
344LiveVariablesImpl::runOnBlock(const CFGBlock *block,
345                              LiveVariables::LivenessValues val,
346                              LiveVariables::Observer *obs) {
347
348  TransferFunctions TF(*this, val, obs, block);
349
350  // Visit the terminator (if any).
351  if (const Stmt *term = block->getTerminator())
352    TF.Visit(const_cast<Stmt*>(term));
353
354  // Apply the transfer function for all Stmts in the block.
355  for (CFGBlock::const_reverse_iterator it = block->rbegin(),
356       ei = block->rend(); it != ei; ++it) {
357    const CFGElement &elem = *it;
358    if (!isa<CFGStmt>(elem))
359      continue;
360
361    const Stmt *S = cast<CFGStmt>(elem).getStmt();
362    TF.Visit(const_cast<Stmt*>(S));
363    stmtsToLiveness[S] = val;
364  }
365  return val;
366}
367
368void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) {
369  const CFG *cfg = getImpl(impl).analysisContext.getCFG();
370  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it)
371    getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs);
372}
373
374LiveVariables::LiveVariables(void *im) : impl(im) {}
375
376LiveVariables::~LiveVariables() {
377  delete (LiveVariablesImpl*) impl;
378}
379
380LiveVariables *
381LiveVariables::computeLiveness(AnalysisContext &AC,
382                                 bool killAtAssign) {
383
384  // No CFG?  Bail out.
385  CFG *cfg = AC.getCFG();
386  if (!cfg)
387    return 0;
388
389  LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign);
390
391  // Construct the dataflow worklist.  Enqueue the exit block as the
392  // start of the analysis.
393  Worklist worklist(*cfg);
394  llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs());
395
396  // FIXME: we should enqueue using post order.
397  for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
398    const CFGBlock *block = *it;
399    worklist.enqueueBlock(block);
400
401    // FIXME: Scan for DeclRefExprs using in the LHS of an assignment.
402    // We need to do this because we lack context in the reverse analysis
403    // to determine if a DeclRefExpr appears in such a context, and thus
404    // doesn't constitute a "use".
405    if (killAtAssign)
406      for (CFGBlock::const_iterator bi = block->begin(), be = block->end();
407           bi != be; ++bi) {
408        if (const CFGStmt *cs = bi->getAs<CFGStmt>()) {
409          if (BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) {
410            if (BO->getOpcode() == BO_Assign) {
411              if (const DeclRefExpr *DR =
412                    dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) {
413                LV->inAssignment[DR] = 1;
414              }
415            }
416          }
417        }
418      }
419  }
420
421  while (!worklist.empty()) {
422    // Dequeue blocks in FIFO order.
423    const CFGBlock *block = worklist.getNextItem();
424
425    // Determine if the block's end value has changed.  If not, we
426    // have nothing left to do for this block.
427    LivenessValues &prevVal = LV->blocksEndToLiveness[block];
428
429    // Merge the values of all successor blocks.
430    LivenessValues val;
431    for (CFGBlock::const_succ_iterator it = block->succ_begin(),
432                                       ei = block->succ_end(); it != ei; ++it) {
433      if (const CFGBlock *succ = *it)
434        val = LV->merge(val, LV->blocksBeginToLiveness[succ]);
435    }
436
437    if (!everAnalyzedBlock[block->getBlockID()])
438      everAnalyzedBlock[block->getBlockID()] = true;
439    else if (prevVal.equals(val))
440      continue;
441
442    prevVal = val;
443
444    // Update the dataflow value for the start of this block.
445    LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val);
446
447    // Enqueue the value to the predecessors.
448    for (CFGBlock::const_pred_iterator it = block->pred_begin(),
449                                       ei = block->pred_end(); it != ei; ++it)
450    {
451      if (const CFGBlock *pred = *it)
452        worklist.enqueueBlock(pred);
453    }
454  }
455
456  return new LiveVariables(LV);
457}
458
459static bool compare_entries(const CFGBlock *A, const CFGBlock *B) {
460  return A->getBlockID() < B->getBlockID();
461}
462
463static bool compare_vd_entries(const Decl *A, const Decl *B) {
464  SourceLocation ALoc = A->getLocStart();
465  SourceLocation BLoc = B->getLocStart();
466  return ALoc.getRawEncoding() < BLoc.getRawEncoding();
467}
468
469void LiveVariables::dumpBlockLiveness(const SourceManager &M) {
470  getImpl(impl).dumpBlockLiveness(M);
471}
472
473void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) {
474  std::vector<const CFGBlock *> vec;
475  for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator
476       it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end();
477       it != ei; ++it) {
478    vec.push_back(it->first);
479  }
480  std::sort(vec.begin(), vec.end(), compare_entries);
481
482  std::vector<const VarDecl*> declVec;
483
484  for (std::vector<const CFGBlock *>::iterator
485        it = vec.begin(), ei = vec.end(); it != ei; ++it) {
486    llvm::errs() << "\n[ B" << (*it)->getBlockID()
487                 << " (live variables at block exit) ]\n";
488
489    LiveVariables::LivenessValues vals = blocksEndToLiveness[*it];
490    declVec.clear();
491
492    for (llvm::ImmutableSet<const VarDecl *>::iterator si =
493          vals.liveDecls.begin(),
494          se = vals.liveDecls.end(); si != se; ++si) {
495      declVec.push_back(*si);
496    }
497
498    std::sort(declVec.begin(), declVec.end(), compare_vd_entries);
499
500    for (std::vector<const VarDecl*>::iterator di = declVec.begin(),
501         de = declVec.end(); di != de; ++di) {
502      llvm::errs() << " " << (*di)->getDeclName().getAsString()
503                   << " <";
504      (*di)->getLocation().dump(M);
505      llvm::errs() << ">\n";
506    }
507  }
508  llvm::errs() << "\n";
509}
510
511