LiveVariables.cpp revision 579ee4f9f5c7b8f939621c8008337a3c1c679957
18d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "clang/Analysis/Analyses/LiveVariables.h" 28d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "clang/Analysis/Analyses/PostOrderCFGView.h" 38d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 48d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "clang/AST/Stmt.h" 5c5ec7f57ead87efa365800228aa0b09a12d9e6c4Dmitry Shmidt#include "clang/Analysis/CFG.h" 6c5ec7f57ead87efa365800228aa0b09a12d9e6c4Dmitry Shmidt#include "clang/Analysis/AnalysisContext.h" 78d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "clang/AST/StmtVisitor.h" 88d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 98d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "llvm/ADT/PostOrderIterator.h" 108d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include "llvm/ADT/DenseMap.h" 118d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 128d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include <deque> 138d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include <algorithm> 148d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt#include <vector> 158d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 168d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtusing namespace clang; 178d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 188d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtnamespace { 1961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 208d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtclass DataflowWorklist { 218d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SmallVector<const CFGBlock *, 20> worklist; 228d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::BitVector enqueuedBlocks; 238d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt PostOrderCFGView *POV; 248d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtpublic: 258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) 268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt : enqueuedBlocks(cfg.getNumBlockIDs()), 278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt POV(Ctx.getAnalysis<PostOrderCFGView>()) {} 288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt void enqueueBlock(const CFGBlock *block); 3004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt void enqueueSuccessors(const CFGBlock *block); 318d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt void enqueuePredecessors(const CFGBlock *block); 328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const CFGBlock *dequeue(); 341f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt void sortWorklist(); 368d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt}; 378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 391f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 401f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidtvoid DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) { 4161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (block && !enqueuedBlocks[block->getBlockID()]) { 4261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt enqueuedBlocks[block->getBlockID()] = true; 4361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt worklist.push_back(block); 4461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 451f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt} 4661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 478d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { 488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const unsigned OldWorklistSize = worklist.size(); 498d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (CFGBlock::const_succ_iterator I = block->succ_begin(), 508d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt E = block->succ_end(); I != E; ++I) { 518d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt enqueueBlock(*I); 528d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 538d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 548d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return; 568d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 578d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt sortWorklist(); 588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 598d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { 618d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const unsigned OldWorklistSize = worklist.size(); 628d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (CFGBlock::const_pred_iterator I = block->pred_begin(), 638d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt E = block->pred_end(); I != E; ++I) { 648d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt enqueueBlock(*I); 651f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (OldWorklistSize == 0 || OldWorklistSize == worklist.size()) 688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return; 698d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 708d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt sortWorklist(); 718d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 728d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 738d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid DataflowWorklist::sortWorklist() { 748d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt std::sort(worklist.begin(), worklist.end(), POV->getComparator()); 758d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 768d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 778d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst CFGBlock *DataflowWorklist::dequeue() { 788d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (worklist.empty()) 798d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return 0; 808d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const CFGBlock *b = worklist.back(); 818d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt worklist.pop_back(); 828d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt enqueuedBlocks[b->getBlockID()] = false; 838d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return b; 848d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 858d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 868d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtnamespace { 878d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtclass LiveVariablesImpl { 8804949598a23f501be6eec21697465fd46a28840aDmitry Shmidtpublic: 8904949598a23f501be6eec21697465fd46a28840aDmitry Shmidt AnalysisDeclContext &analysisContext; 9004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt std::vector<LiveVariables::LivenessValues> cfgBlockValues; 9104949598a23f501be6eec21697465fd46a28840aDmitry Shmidt llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 9204949598a23f501be6eec21697465fd46a28840aDmitry Shmidt llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 9304949598a23f501be6eec21697465fd46a28840aDmitry Shmidt llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 948d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 958d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 9604949598a23f501be6eec21697465fd46a28840aDmitry Shmidt llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 9704949598a23f501be6eec21697465fd46a28840aDmitry Shmidt const bool killAtAssign; 9804949598a23f501be6eec21697465fd46a28840aDmitry Shmidt 998d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::LivenessValues 10004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt merge(LiveVariables::LivenessValues valsA, 1018d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::LivenessValues valsB); 1021f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 1038d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, 1048d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::LivenessValues val, 1058d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::Observer *obs = 0); 1068d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1071f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt void dumpBlockLiveness(const SourceManager& M); 1088d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1098d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) 1108d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt : analysisContext(ac), 1118d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SSetFact(false), // Do not canonicalize ImmutableSets by default. 112d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt DSetFact(false), // This is a *major* performance win. 113d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt killAtAssign(KillAtAssign) {} 114d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt}; 115d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt} 116d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt 117d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidtstatic LiveVariablesImpl &getImpl(void *x) { 118d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt return *((LiveVariablesImpl *) x); 119d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt} 120d5e4923d04122f81300fa68fb07d64ede28fd44dDmitry Shmidt 1218d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt//===----------------------------------------------------------------------===// 1228d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// Operations and queries on LivenessValues. 1231f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt//===----------------------------------------------------------------------===// 1248d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtbool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 1268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return liveStmts.contains(S); 1278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtbool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 1308d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return liveDecls.contains(D); 1311f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt} 1328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtnamespace { 1348d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt template <typename SET> 1358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SET mergeSets(SET A, SET B) { 1361f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (A.isEmpty()) 1378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return B; 1388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1391f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 1408d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt A = A.add(*it); 1411f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 1421f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt return A; 1431f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 1441f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt} 1451f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 1461f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry ShmidtLiveVariables::LivenessValues 1471f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry ShmidtLiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 1481f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt LiveVariables::LivenessValues valsB) { 1491f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 1501f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt llvm::ImmutableSetRef<const Stmt *> 1518d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SSetRefA(valsA.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()), 1528d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SSetRefB(valsB.liveStmts.getRootWithoutRetain(), SSetFact.getTreeFactory()); 1531f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 1548d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::ImmutableSetRef<const VarDecl *> 1568d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DSetRefA(valsA.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()), 1578d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DSetRefB(valsB.liveDecls.getRootWithoutRetain(), DSetFact.getTreeFactory()); 1588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1598d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SSetRefA = mergeSets(SSetRefA, SSetRefB); 1618d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DSetRefA = mergeSets(DSetRefA, DSetRefB); 1628d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1638d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // asImmutableSet() canonicalizes the tree, allowing us to do an easy 16461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // comparison afterwards. 16561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return LiveVariables::LivenessValues(SSetRefA.asImmutableSet(), 1668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DSetRefA.asImmutableSet()); 1678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 1688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 1698d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtbool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 17061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 1711f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt} 17261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 17361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt//===----------------------------------------------------------------------===// 1741f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt// Query methods. 17561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt//===----------------------------------------------------------------------===// 17661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 1771f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidtstatic bool isAlwaysAlive(const VarDecl *D) { 17861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return D->hasGlobalStorage(); 17961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 1808d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 18161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtbool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 1821f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 18361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 18461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 1851f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidtbool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 18661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 18761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 1888d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 18961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtbool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 1901f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 19161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 19261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 1931f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt//===----------------------------------------------------------------------===// 1948d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt// Dataflow computation. 19561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt//===----------------------------------------------------------------------===// 19661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 19761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtnamespace { 19861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtclass TransferFunctions : public StmtVisitor<TransferFunctions> { 19961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariablesImpl &LV; 20061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariables::LivenessValues &val; 20161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariables::Observer *observer; 20261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const CFGBlock *currentBlock; 20361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtpublic: 20461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt TransferFunctions(LiveVariablesImpl &im, 20561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariables::LivenessValues &Val, 20661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariables::Observer *Observer, 20761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const CFGBlock *CurrentBlock) 20861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 20961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 21061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitBinaryOperator(BinaryOperator *BO); 21161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitBlockExpr(BlockExpr *BE); 21261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitDeclRefExpr(DeclRefExpr *DR); 21361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitDeclStmt(DeclStmt *DS); 21461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 21561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 21661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void VisitUnaryOperator(UnaryOperator *UO); 21761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt void Visit(Stmt *S); 21861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt}; 21961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 22061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 22161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtstatic const VariableArrayType *FindVA(QualType Ty) { 22261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const Type *ty = Ty.getTypePtr(); 22361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 22461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 22561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (VAT->getSizeExpr()) 22661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return VAT; 22761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 22861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt ty = VT->getElementType().getTypePtr(); 22961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 23061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 23161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return 0; 23261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 23361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 23461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtvoid TransferFunctions::Visit(Stmt *S) { 23561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (observer) 23661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt observer->observeStmt(S, currentBlock, val); 23761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 23861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt StmtVisitor<TransferFunctions>::Visit(S); 23961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 24061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (isa<Expr>(S)) { 24161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 24261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 2438d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 2441f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt // Mark all children expressions live. 2451f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 2461f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt switch (S->getStmtClass()) { 2471f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt default: 2488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt break; 2491f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt case Stmt::StmtExprClass: { 2501f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt // For statement expressions, look through the compound statement. 2511f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt S = cast<StmtExpr>(S)->getSubStmt(); 2521f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt break; 2531f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 25461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt case Stmt::CXXMemberCallExprClass: { 2558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Include the implicit "this" pointer as being live. 2561f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 2578d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { 2588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt ImplicitObj = ImplicitObj->IgnoreParens(); 2591f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt val.liveStmts = LV.SSetFact.add(val.liveStmts, ImplicitObj); 2608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 2611f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt break; 2621f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 2631f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt case Stmt::DeclStmtClass: { 2641f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt const DeclStmt *DS = cast<DeclStmt>(S); 2651f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 2668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (const VariableArrayType* VA = FindVA(VD->getType()); 2678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt VA != 0; VA = FindVA(VA->getElementType())) { 2681f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt val.liveStmts = LV.SSetFact.add(val.liveStmts, 2691f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt VA->getSizeExpr()->IgnoreParens()); 2708d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 2711f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 2728d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt break; 2731f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt } 2748d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // FIXME: These cases eventually shouldn't be needed. 27561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt case Stmt::ExprWithCleanupsClass: { 27661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt S = cast<ExprWithCleanups>(S)->getSubExpr(); 27761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt break; 27861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 27961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt case Stmt::CXXBindTemporaryExprClass: { 28061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 28161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt break; 28261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 28361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt case Stmt::UnaryExprOrTypeTraitExprClass: { 28461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // No need to unconditionally visit subexpressions. 28561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return; 2868d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 2878d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 28861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 28961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); 29061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt it != ei; ++it) { 29161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (Stmt *child = *it) { 29261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (Expr *Ex = dyn_cast<Expr>(child)) 2938d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt child = Ex->IgnoreParens(); 2948d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 2958d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 2968d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 2978d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 2988d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 2991f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 3001f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidtvoid TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 3011f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (B->isAssignmentOp()) { 3021f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (!LV.killAtAssign) 3038d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return; 3048d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3058d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Assigning to a variable? 3061f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt Expr *LHS = B->getLHS()->IgnoreParens(); 3071f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 30861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(LHS)) 30961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 31061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Assignments to references don't kill the ref's address 3111f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt if (VD->getType()->isReferenceType()) 3121f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt return; 3131f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt 3148d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (!isAlwaysAlive(VD)) { 3158d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // The variable is now dead. 3168d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 3178d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3188d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3198d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (observer) 3208d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt observer->observerKill(DR); 3218d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3228d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3238d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 3248d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 3268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt AnalysisDeclContext::referenced_decls_iterator I, E; 3278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::tie(I, E) = 3288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); 3298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for ( ; I != E ; ++I) { 3308d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const VarDecl *VD = *I; 3318d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (isAlwaysAlive(VD)) 3328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt continue; 3338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 3348d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 3368d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 3388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 3398d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 3408d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 3418d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 3428d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3438d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 3441f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 3458d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DI != DE; ++DI) 3468d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) { 3478d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (!isAlwaysAlive(VD)) 3488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 3498d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3508d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 3518d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3528d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 3538d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Kill the iteration variable. 3548d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt DeclRefExpr *DR = 0; 3558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt const VarDecl *VD = 0; 3568d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3578d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt Stmt *element = OS->getElement(); 3588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 3598d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt VD = cast<VarDecl>(DS->getSingleDecl()); 3608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3618d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 3628d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt VD = cast<VarDecl>(DR->getDecl()); 3638d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 3648d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 3658d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (VD) { 3668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 3678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (observer && DR) 3688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt observer->observerKill(DR); 36904949598a23f501be6eec21697465fd46a28840aDmitry Shmidt } 37004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt} 37104949598a23f501be6eec21697465fd46a28840aDmitry Shmidt 37204949598a23f501be6eec21697465fd46a28840aDmitry Shmidtvoid TransferFunctions:: 37304949598a23f501be6eec21697465fd46a28840aDmitry ShmidtVisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 37404949598a23f501be6eec21697465fd46a28840aDmitry Shmidt{ 37504949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // While sizeof(var) doesn't technically extend the liveness of 'var', it 37604949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // does extent the liveness of metadata if 'var' is a VariableArrayType. 37704949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // We handle that special case here. 37804949598a23f501be6eec21697465fd46a28840aDmitry Shmidt if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 37904949598a23f501be6eec21697465fd46a28840aDmitry Shmidt return; 38004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt 38104949598a23f501be6eec21697465fd46a28840aDmitry Shmidt const Expr *subEx = UE->getArgumentExpr(); 38204949598a23f501be6eec21697465fd46a28840aDmitry Shmidt if (subEx->getType()->isVariableArrayType()) { 38304949598a23f501be6eec21697465fd46a28840aDmitry Shmidt assert(subEx->isLValue()); 38404949598a23f501be6eec21697465fd46a28840aDmitry Shmidt val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 38504949598a23f501be6eec21697465fd46a28840aDmitry Shmidt } 38604949598a23f501be6eec21697465fd46a28840aDmitry Shmidt} 38704949598a23f501be6eec21697465fd46a28840aDmitry Shmidt 38804949598a23f501be6eec21697465fd46a28840aDmitry Shmidtvoid TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 38904949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // Treat ++/-- as a kill. 39004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // Note we don't actually have to do anything if we don't have an observer, 39104949598a23f501be6eec21697465fd46a28840aDmitry Shmidt // since a ++/-- acts as both a kill and a "use". 39204949598a23f501be6eec21697465fd46a28840aDmitry Shmidt if (!observer) 39304949598a23f501be6eec21697465fd46a28840aDmitry Shmidt return; 39404949598a23f501be6eec21697465fd46a28840aDmitry Shmidt 39504949598a23f501be6eec21697465fd46a28840aDmitry Shmidt switch (UO->getOpcode()) { 3961f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt default: 39704949598a23f501be6eec21697465fd46a28840aDmitry Shmidt return; 39804949598a23f501be6eec21697465fd46a28840aDmitry Shmidt case UO_PostInc: 3998d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt case UO_PostDec: 4008d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt case UO_PreInc: 4018d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt case UO_PreDec: 4028d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt break; 4038d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 4048d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 4058d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 4068d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (isa<VarDecl>(DR->getDecl())) { 4078d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Treat ++/-- as a kill. 4088d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt observer->observerKill(DR); 40904949598a23f501be6eec21697465fd46a28840aDmitry Shmidt } 41004949598a23f501be6eec21697465fd46a28840aDmitry Shmidt} 4118d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 4128d520ff1dc2da35cdca849e982051b86468016d8Dmitry ShmidtLiveVariables::LivenessValues 4138d520ff1dc2da35cdca849e982051b86468016d8Dmitry ShmidtLiveVariablesImpl::runOnBlock(const CFGBlock *block, 4148d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::LivenessValues val, 4158d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt LiveVariables::Observer *obs) { 4168d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 4178d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt TransferFunctions TF(*this, val, obs, block); 4188d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 4198d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt // Visit the terminator (if any). 4208d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt if (const Stmt *term = block->getTerminator()) 42161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt TF.Visit(const_cast<Stmt*>(term)); 42261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 42361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Apply the transfer function for all Stmts in the block. 42461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (CFGBlock::const_reverse_iterator it = block->rbegin(), 42561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt ei = block->rend(); it != ei; ++it) { 42661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const CFGElement &elem = *it; 42761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (!isa<CFGStmt>(elem)) 42861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt continue; 42961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 43061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const Stmt *S = cast<CFGStmt>(elem).getStmt(); 43161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt TF.Visit(const_cast<Stmt*>(S)); 43261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt stmtsToLiveness[S] = val; 43361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 43461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return val; 43561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 43661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 43761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtvoid LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 43861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 43961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 44061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 44161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 44261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 44361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry ShmidtLiveVariables::LiveVariables(void *im) : impl(im) {} 44461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 44561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry ShmidtLiveVariables::~LiveVariables() { 44661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt delete (LiveVariablesImpl*) impl; 44761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 44861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 44961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry ShmidtLiveVariables * 45061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry ShmidtLiveVariables::computeLiveness(AnalysisDeclContext &AC, 45161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt bool killAtAssign) { 45261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 45361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // No CFG? Bail out. 45461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt CFG *cfg = AC.getCFG(); 45561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (!cfg) 45661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return 0; 45761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 45861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 45961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 46061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Construct the dataflow worklist. Enqueue the exit block as the 46161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // start of the analysis. 46261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt DataflowWorklist worklist(*cfg, AC); 46361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 46461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 46561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // FIXME: we should enqueue using post order. 46661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 46761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt const CFGBlock *block = *it; 46861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt worklist.enqueueBlock(block); 46961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 47061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 47161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // We need to do this because we lack context in the reverse analysis 47261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // to determine if a DeclRefExpr appears in such a context, and thus 47361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // doesn't constitute a "use". 47461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (killAtAssign) 47561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 47661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt bi != be; ++bi) { 47761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const CFGStmt *cs = bi->getAs<CFGStmt>()) { 47861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) { 47961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (BO->getOpcode() == BO_Assign) { 48061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const DeclRefExpr *DR = 48161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 48261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LV->inAssignment[DR] = 1; 48361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 48961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 49061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt worklist.sortWorklist(); 49161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 49261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt while (const CFGBlock *block = worklist.dequeue()) { 49361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Determine if the block's end value has changed. If not, we 49461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // have nothing left to do for this block. 49561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 49661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 49761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Merge the values of all successor blocks. 49861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LivenessValues val; 49961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt for (CFGBlock::const_succ_iterator it = block->succ_begin(), 50061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt ei = block->succ_end(); it != ei; ++it) { 50161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (const CFGBlock *succ = *it) { 50261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 50361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 50461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 50561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 50661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt if (!everAnalyzedBlock[block->getBlockID()]) 50761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt everAnalyzedBlock[block->getBlockID()] = true; 50861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt else if (prevVal.equals(val)) 50961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt continue; 51061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 51161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt prevVal = val; 51261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 51361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Update the dataflow value for the start of this block. 51461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 51561d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 51661d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt // Enqueue the value to the predecessors. 51761d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt worklist.enqueuePredecessors(block); 51861d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt } 51961d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 52061d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return new LiveVariables(LV); 52161d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt} 52261d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt 52361d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidtstatic bool compare_entries(const CFGBlock *A, const CFGBlock *B) { 52461d9df3e62aaa0e87ad05452fcb95142159a17b6Dmitry Shmidt return A->getBlockID() < B->getBlockID(); 5258d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 5268d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5278d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtstatic bool compare_vd_entries(const Decl *A, const Decl *B) { 5288d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SourceLocation ALoc = A->getLocStart(); 5298d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt SourceLocation BLoc = B->getLocStart(); 5308d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt return ALoc.getRawEncoding() < BLoc.getRawEncoding(); 5318d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 5328d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5338d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid LiveVariables::dumpBlockLiveness(const SourceManager &M) { 5348d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt getImpl(impl).dumpBlockLiveness(M); 5358d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 5368d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5378d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtvoid LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 5388d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt std::vector<const CFGBlock *> vec; 5398d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 5408d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 5418d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt it != ei; ++it) { 5428d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt vec.push_back(it->first); 5438d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 5448d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt std::sort(vec.begin(), vec.end(), compare_entries); 5458d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5468d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt std::vector<const VarDecl*> declVec; 5478d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5488d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (std::vector<const CFGBlock *>::iterator 5498d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt it = vec.begin(), ei = vec.end(); it != ei; ++it) { 5501f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt llvm::errs() << "\n[ B" << (*it)->getBlockID() 5511f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt << " (live variables at block exit) ]\n"; 5528d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5531f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 5548d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt declVec.clear(); 5558d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5568d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (llvm::ImmutableSet<const VarDecl *>::iterator si = 5571f69aa52ea2e0a73ac502565df8c666ee49cab6aDmitry Shmidt vals.liveDecls.begin(), 5588d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt se = vals.liveDecls.end(); si != se; ++si) { 5598d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt declVec.push_back(*si); 5608d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 5618d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5628d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt std::sort(declVec.begin(), declVec.end(), compare_vd_entries); 5638d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5648d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 5658d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt de = declVec.end(); di != de; ++di) { 5668d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::errs() << " " << (*di)->getDeclName().getAsString() 5678d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt << " <"; 5688d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt (*di)->getLocation().dump(M); 5698d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::errs() << ">\n"; 5708d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 5718d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt } 5728d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt llvm::errs() << "\n"; 5738d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt} 5748d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt 5758d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst void *LiveVariables::getTag() { static int x; return &x; } 5768d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidtconst void *RelaxedLiveVariables::getTag() { static int x; return &x; } 5778d520ff1dc2da35cdca849e982051b86468016d8Dmitry Shmidt