LiveVariables.cpp revision 84eaeffe94ef63a182a02fcf935d4c651caf2359
1674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// 2674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 3674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// The LLVM Compiler Infrastructure 4674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 5674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// This file is distributed under the University of Illinois Open Source 6674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// License. See LICENSE.TXT for details. 7674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 8674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 9674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 10674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// This file implements Live Variables analysis for source-level CFGs. 11674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 12674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 13674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 14674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/Analyses/LiveVariables.h" 15674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Basic/SourceManager.h" 16674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/AST/ASTContext.h" 17674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/AST/Expr.h" 18674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/CFG.h" 19674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" 20674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/FlowSensitive/DataflowSolver.h" 21674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/Support/SaveAndRestore.h" 22674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "clang/Analysis/PathSensitive/AnalysisContext.h" 23674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "llvm/ADT/SmallPtrSet.h" 24674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "llvm/ADT/SmallVector.h" 25674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen#include "llvm/Support/raw_ostream.h" 26674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 27674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenusing namespace clang; 28674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 29674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 30674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// Useful constants. 31674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 32674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 33674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenstatic const bool Alive = true; 34674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenstatic const bool Dead = false; 35674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 36674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 37674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// Dataflow initialization logic. 38674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 39674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 40674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogennamespace { 41674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenclass RegisterDecls 42674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen : public CFGRecStmtDeclVisitor<RegisterDecls> { 43674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 44674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveVariables::AnalysisDataTy& AD; 45674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 46674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy; 47674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AlwaysLiveTy AlwaysLive; 48674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 49674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 50674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenpublic: 51674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} 52674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 53674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen ~RegisterDecls() { 54674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 55674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.AlwaysLive.resetValues(AD); 56674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 57674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end(); 58674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen I != E; ++ I) 59674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.AlwaysLive(*I, AD) = Alive; 60674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 61674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 62674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitImplicitParamDecl(ImplicitParamDecl* IPD) { 63674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Register the VarDecl for tracking. 64674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.Register(IPD); 65674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 66674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 67674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitVarDecl(VarDecl* VD) { 68674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Register the VarDecl for tracking. 69674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.Register(VD); 70674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 71674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Does the variable have global storage? If so, it is always live. 72674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (VD->hasGlobalStorage()) 73674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AlwaysLive.push_back(VD); 74674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 75674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 76674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen CFG& getCFG() { return AD.getCFG(); } 77674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen}; 78674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} // end anonymous namespace 79674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 80674060f01e9090cd21b3c5656cc3204912ad17a6Jon BoekenoogenLiveVariables::LiveVariables(AnalysisContext &AC) { 81674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Register all referenced VarDecls. 82674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen CFG &cfg = *AC.getCFG(); 83674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen getAnalysisData().setCFG(cfg); 84674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen getAnalysisData().setContext(AC.getASTContext()); 85674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen getAnalysisData().AC = &AC; 86674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 87674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen RegisterDecls R(getAnalysisData()); 88674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen cfg.VisitBlockStmts(R); 89674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 90674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 91674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 92674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// Transfer functions. 93674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 94674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 95674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogennamespace { 96674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 97674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenclass TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ 98674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveVariables::AnalysisDataTy& AD; 99674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveVariables::ValTy LiveState; 100674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenpublic: 101674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} 102674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 103674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveVariables::ValTy& getVal() { return LiveState; } 104674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen CFG& getCFG() { return AD.getCFG(); } 105674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 106674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitDeclRefExpr(DeclRefExpr* DR); 107674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitBinaryOperator(BinaryOperator* B); 108674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitBlockExpr(BlockExpr *B); 109674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitAssign(BinaryOperator* B); 110674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitDeclStmt(DeclStmt* DS); 111674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); 112674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitUnaryOperator(UnaryOperator* U); 113674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void Visit(Stmt *S); 114674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitTerminator(CFGBlock* B); 115674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 116674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen /// VisitConditionVariableInit - Handle the initialization of condition 117674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen /// variables at branches. Valid statements include IfStmt, ForStmt, 118674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen /// WhileStmt, and SwitchStmt. 119674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void VisitConditionVariableInit(Stmt *S); 120674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 121674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen void SetTopValue(LiveVariables::ValTy& V) { 122674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen V = AD.AlwaysLive; 123674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 124674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 125674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen}; 126674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 127674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::Visit(Stmt *S) { 128674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 129674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (S == getCurrentBlkStmt()) { 130674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 131674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (AD.Observer) 132674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.Observer->ObserveStmt(S,AD,LiveState); 133674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 134674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (getCFG().isBlkExpr(S)) 135674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(S, AD) = Dead; 136674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 137674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen StmtVisitor<TransferFuncs,void>::Visit(S); 138674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 139674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else if (!getCFG().isBlkExpr(S)) { 140674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 141674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (AD.Observer) 142674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.Observer->ObserveStmt(S,AD,LiveState); 143674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 144674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen StmtVisitor<TransferFuncs,void>::Visit(S); 145674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 146674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 147674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else { 148674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // For block-level expressions, mark that they are live. 149674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(S,AD) = Alive; 150674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 151674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 152674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 153674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitConditionVariableInit(Stmt *S) { 154674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen assert(!getCFG().isBlkExpr(S)); 155674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S); 156674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 157674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 158674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitTerminator(CFGBlock* B) { 159674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 160674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen const Stmt* E = B->getTerminatorCondition(); 161674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 162674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (!E) 163674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return; 164674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 165674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen assert (getCFG().isBlkExpr(E)); 166674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(E, AD) = Alive; 167674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 168674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 169674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { 170674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) 171674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(V, AD) = Alive; 172674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 173674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 174674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitBlockExpr(BlockExpr *BE) { 175674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AnalysisContext::referenced_decls_iterator I, E; 176674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl()); 177674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for ( ; I != E ; ++I) { 178674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen DeclBitVector_Types::Idx i = AD.getIdx(*I); 179674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (i.isValid()) 180674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState.getBit(i) = Alive; 181674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 182674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 183674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 184674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { 185674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (B->isAssignmentOp()) VisitAssign(B); 186674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else VisitStmt(B); 187674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 188674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 189674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid 190674060f01e9090cd21b3c5656cc3204912ad17a6Jon BoekenoogenTransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 191674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 192674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // This is a block-level expression. Its value is 'dead' before this point. 193674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(S, AD) = Dead; 194674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 195674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // This represents a 'use' of the collection. 196674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Visit(S->getCollection()); 197674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 198674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // This represents a 'kill' for the variable. 199674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Stmt* Element = S->getElement(); 200674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen DeclRefExpr* DR = 0; 201674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen VarDecl* VD = 0; 202674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 203674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) 204674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen VD = cast<VarDecl>(DS->getSingleDecl()); 205674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else { 206674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); 207674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) 208674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen VD = cast<VarDecl>(DR->getDecl()); 209674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else { 210674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Visit(ElemExpr); 211674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return; 212674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 213674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 214674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 215674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (VD) { 216674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(VD, AD) = Dead; 217674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } 218674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 219674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 220674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 221674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 222674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { 223674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Expr *E = U->getSubExpr(); 224674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 225674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen switch (U->getOpcode()) { 226674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen case UnaryOperator::PostInc: 227674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen case UnaryOperator::PostDec: 228674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen case UnaryOperator::PreInc: 229674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen case UnaryOperator::PreDec: 230674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Walk through the subexpressions, blasting through ParenExprs 231674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // until we either find a DeclRefExpr or some non-DeclRefExpr 232674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // expression. 233674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) 234674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { 235674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Treat the --/++ operator as a kill. 236674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (AD.Observer) { AD.Observer->ObserverKill(DR); } 237674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState(VD, AD) = Alive; 238674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return VisitDeclRefExpr(DR); 239674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 240674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 241674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Fall-through. 242674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 243674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen default: 244674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return Visit(E); 245674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 246674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 247674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 248674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitAssign(BinaryOperator* B) { 249674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Expr* LHS = B->getLHS(); 250674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 251674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Assigning to a variable? 252674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { 253674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 254674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Update liveness inforamtion. 255674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen unsigned bit = AD.getIdx(DR->getDecl()); 256674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 257674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 258674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (AD.Observer) { AD.Observer->ObserverKill(DR); } 259674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 260674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Handle things like +=, etc., which also generate "uses" 261674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // of a variable. Do this just by visiting the subexpression. 262674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (B->getOpcode() != BinaryOperator::Assign) 263674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen VisitDeclRefExpr(DR); 264674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 265674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen else // Not assigning to a variable. Process LHS as usual. 266674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Visit(LHS); 267674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 268674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Visit(B->getRHS()); 269674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 270674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 271674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid TransferFuncs::VisitDeclStmt(DeclStmt* DS) { 272674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Declarations effectively "kill" a variable since they cannot 273674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // possibly be live before they are declared. 274674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 275674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen DI != DE; ++DI) 276674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { 277674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // The initializer is evaluated after the variable comes into scope. 278674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Since this is a reverse dataflow analysis, we must evaluate the 279674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // transfer function for this expression first. 280674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (Expr* Init = VD->getInit()) 281674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Visit(Init); 282674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 283674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen if (const VariableArrayType* VT = 284674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen AD.getContext().getAsVariableArrayType(VD->getType())) { 285674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen StmtIterator I(const_cast<VariableArrayType*>(VT)); 286674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen StmtIterator E; 287674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen for (; I != E; ++I) Visit(*I); 288674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 289674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 290674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen // Update liveness information by killing the VarDecl. 291674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen unsigned bit = AD.getIdx(VD); 292674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); 293674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen } 294674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 295674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 296674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} // end anonymous namespace 297674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 298674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 299674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// Merge operator: if something is live on any successor block, it is live 300674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// in the current block (a set union). 301674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 302674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 303674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogennamespace { 304674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen typedef StmtDeclBitVector_Types::Union Merge; 305674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; 306674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} // end anonymous namespace 307674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 308674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 309674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// External interface to run Liveness analysis. 310674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 311674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 312674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid LiveVariables::runOnCFG(CFG& cfg) { 313674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Solver S(*this); 314674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen S.runOnCFG(cfg); 315674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 316674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 317674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenvoid LiveVariables::runOnAllBlocks(const CFG& cfg, 318674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen LiveVariables::ObserverTy* Obs, 319674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen bool recordStmtValues) { 320674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Solver S(*this); 321674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer, 322674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen Obs); 323674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen S.runOnAllBlocks(cfg, recordStmtValues); 324674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 325674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 326674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen//===----------------------------------------------------------------------===// 327674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// liveness queries 328674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen// 329674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 330674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenbool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { 331674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 332674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return i.isValid() ? getBlockData(B).getBit(i) : false; 333674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 334674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 335674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenbool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { 336674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); 337674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return i.isValid() ? Live.getBit(i) : false; 338674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen} 339674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen 340674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogenbool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { 341674060f01e9090cd21b3c5656cc3204912ad17a6Jon Boekenoogen return getStmtData(Loc)(StmtVal,getAnalysisData()); 342} 343 344bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { 345 return getStmtData(Loc)(D,getAnalysisData()); 346} 347 348//===----------------------------------------------------------------------===// 349// printing liveness state for debugging 350// 351 352void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const { 353 const AnalysisDataTy& AD = getAnalysisData(); 354 355 for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), 356 E = AD.end_decl(); I!=E; ++I) 357 if (V.getDeclBit(I->second)) { 358 llvm::errs() << " " << I->first->getIdentifier()->getName() << " <"; 359 I->first->getLocation().dump(SM); 360 llvm::errs() << ">\n"; 361 } 362} 363 364void LiveVariables::dumpBlockLiveness(const SourceManager& M) const { 365 for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(), 366 E = getBlockDataMap().end(); I!=E; ++I) { 367 llvm::errs() << "\n[ B" << I->first->getBlockID() 368 << " (live variables at block exit) ]\n"; 369 dumpLiveness(I->second,M); 370 } 371 372 llvm::errs() << "\n"; 373} 374