Ted Kremenek | 11de5cb | 2007-09-20 21:42:55 +0000 | [diff] [blame] | 1 | //=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by Ted Kremenek and is distributed under |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 6 | // the University of Illinois Open Source License. See LICENSE.TXT for |
| 7 | // details. |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 8 | // |
| 9 | //===----------------------------------------------------------------------===// |
| 10 | // |
| 11 | // This file implements Live Variables analysis for source-level CFGs. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "clang/Analysis/LiveVariables.h" |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 16 | #include "clang/Basic/SourceManager.h" |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 17 | #include "clang/AST/Expr.h" |
| 18 | #include "clang/AST/CFG.h" |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 19 | #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" |
Ted Kremenek | 1de632b | 2007-09-25 21:00:24 +0000 | [diff] [blame] | 20 | #include "clang/Analysis/FlowSensitive/DataflowSolver.h" |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 21 | #include "clang/Lex/IdentifierTable.h" |
| 22 | #include "llvm/ADT/SmallPtrSet.h" |
| 23 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 24 | #include <string.h> |
| 25 | #include <stdio.h> |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 26 | |
| 27 | using namespace clang; |
| 28 | |
| 29 | //===----------------------------------------------------------------------===// |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 30 | // Dataflow initialization logic. |
| 31 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 32 | |
| 33 | namespace { |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 34 | class RegisterDecls : public CFGRecStmtDeclVisitor<RegisterDecls> { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 35 | LiveVariables::AnalysisDataTy& AD; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 36 | public: |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 37 | RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 38 | void VisitVarDecl(VarDecl* VD) { AD.Register(VD); } |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 39 | }; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 40 | } // end anonymous namespace |
| 41 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 42 | void LiveVariables::InitializeValues(const CFG& cfg) { |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 43 | RegisterDecls R(getAnalysisData()); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 44 | cfg.VisitBlockStmts(R); |
| 45 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 46 | |
| 47 | //===----------------------------------------------------------------------===// |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 48 | // Transfer functions. |
| 49 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 50 | |
| 51 | namespace { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 52 | |
| 53 | static const bool Alive = true; |
| 54 | static const bool Dead = false; |
| 55 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 56 | class TransferFuncs : public CFGStmtVisitor<TransferFuncs> { |
| 57 | LiveVariables::AnalysisDataTy& AD; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 58 | LiveVariables::ValTy LiveState; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 59 | public: |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 60 | TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 61 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 62 | LiveVariables::ValTy& getVal() { return LiveState; } |
Ted Kremenek | f175805 | 2007-09-12 19:10:52 +0000 | [diff] [blame] | 63 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 64 | void VisitDeclRefExpr(DeclRefExpr* DR); |
| 65 | void VisitBinaryOperator(BinaryOperator* B); |
| 66 | void VisitAssign(BinaryOperator* B); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 67 | void VisitDeclStmt(DeclStmt* DS); |
| 68 | void VisitUnaryOperator(UnaryOperator* U); |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 69 | void VisitStmt(Stmt* S); |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 70 | void VisitExpr(Expr* E); |
| 71 | void BlockStmt_VisitExpr(Expr *E); |
| 72 | void Visit(Stmt *S); |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 73 | |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 74 | DeclRefExpr* FindDeclRef(Stmt *S); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 75 | }; |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 76 | |
| 77 | void TransferFuncs::VisitExpr(Expr * E) { |
| 78 | if (AD.getCFG().isBlkExpr(E)) return; |
| 79 | else VisitStmt(E); |
| 80 | } |
| 81 | |
| 82 | void TransferFuncs::VisitStmt(Stmt* S) { VisitChildren(S); } |
| 83 | |
| 84 | void TransferFuncs::Visit(Stmt *S) { |
| 85 | if (AD.Observer) |
| 86 | AD.Observer->ObserveStmt(S,AD,LiveState); |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 87 | |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 88 | static_cast<CFGStmtVisitor<TransferFuncs>*>(this)->Visit(S); |
| 89 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 90 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 91 | void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { |
| 92 | if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 93 | LiveState(V,AD) = Alive; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 94 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 95 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 96 | void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { |
Ted Kremenek | f175805 | 2007-09-12 19:10:52 +0000 | [diff] [blame] | 97 | if (B->isAssignmentOp()) VisitAssign(B); |
| 98 | else VisitStmt(B); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 99 | } |
| 100 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 101 | void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 102 | Stmt *S = U->getSubExpr(); |
| 103 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 104 | switch (U->getOpcode()) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 105 | case UnaryOperator::PostInc: |
| 106 | case UnaryOperator::PostDec: |
| 107 | case UnaryOperator::PreInc: |
| 108 | case UnaryOperator::PreDec: |
| 109 | case UnaryOperator::AddrOf: |
| 110 | // Walk through the subexpressions, blasting through ParenExprs |
| 111 | // until we either find a DeclRefExpr or some non-DeclRefExpr |
| 112 | // expression. |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 113 | if (DeclRefExpr* DR = FindDeclRef(S)) { |
| 114 | // Treat the --/++/& operator as a kill. |
| 115 | LiveState(DR->getDecl(),AD) = Dead; |
| 116 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
| 117 | return VisitDeclRefExpr(DR); |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 118 | } |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 119 | |
| 120 | // Fall-through. |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 121 | |
| 122 | default: |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 123 | return Visit(S); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 124 | } |
| 125 | } |
| 126 | |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 127 | DeclRefExpr* TransferFuncs::FindDeclRef(Stmt *S) { |
| 128 | for (;;) |
| 129 | if (ParenExpr* P = dyn_cast<ParenExpr>(S)) { |
| 130 | S = P->getSubExpr(); continue; |
| 131 | } |
| 132 | else if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(S)) |
| 133 | return DR; |
| 134 | else |
| 135 | return NULL; |
| 136 | } |
| 137 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 138 | void TransferFuncs::VisitAssign(BinaryOperator* B) { |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 139 | Stmt* LHS = B->getLHS(); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 140 | |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 141 | // Assigning to a variable? |
| 142 | if (DeclRefExpr* DR = FindDeclRef(LHS)) { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 143 | LiveState(DR->getDecl(),AD) = Dead; |
| 144 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
| 145 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 146 | // Handle things like +=, etc., which also generate "uses" |
| 147 | // of a variable. Do this just by visiting the subexpression. |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 148 | if (B->getOpcode() != BinaryOperator::Assign) |
| 149 | VisitDeclRefExpr(DR); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 150 | } |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 151 | else // Not assigning to a variable. Process LHS as usual. |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 152 | Visit(LHS); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 153 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 154 | Visit(B->getRHS()); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 155 | } |
| 156 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 157 | void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { |
| 158 | // Declarations effectively "kill" a variable since they cannot |
| 159 | // possibly be live before they are declared. |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 160 | for (ScopedDecl* D = DS->getDecl(); D != NULL; D = D->getNextDeclarator()) |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 161 | LiveState(D,AD) = Dead; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 162 | } |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 163 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 164 | void TransferFuncs::BlockStmt_VisitExpr(Expr* E) { |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame^] | 165 | assert (AD.getCFG().isBlkExpr(E)); |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 166 | static_cast<CFGStmtVisitor<TransferFuncs>*>(this)->Visit(E); |
| 167 | } |
| 168 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 169 | } // end anonymous namespace |
| 170 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 171 | //===----------------------------------------------------------------------===// |
| 172 | // Merge operator: if something is live on any successor block, it is live |
| 173 | // in the current block (a set union). |
| 174 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 175 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 176 | namespace { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 177 | typedef DeclBitVector_Types::Union Merge; |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 178 | typedef DataflowSolver<LiveVariables,TransferFuncs,Merge> Solver; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 179 | } // end anonymous namespace |
| 180 | |
| 181 | //===----------------------------------------------------------------------===// |
| 182 | // External interface to run Liveness analysis. |
| 183 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 184 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 185 | void LiveVariables::runOnCFG(const CFG& cfg) { |
| 186 | Solver S(*this); |
| 187 | S.runOnCFG(cfg); |
| 188 | } |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 189 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 190 | void LiveVariables::runOnAllBlocks(const CFG& cfg, |
| 191 | LiveVariables::ObserverTy& Obs) { |
| 192 | Solver S(*this); |
| 193 | ObserverTy* OldObserver = getAnalysisData().Observer; |
| 194 | getAnalysisData().Observer = &Obs; |
| 195 | S.runOnAllBlocks(cfg); |
| 196 | getAnalysisData().Observer = OldObserver; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 197 | } |
| 198 | |
| 199 | //===----------------------------------------------------------------------===// |
| 200 | // liveness queries |
| 201 | // |
| 202 | |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 203 | bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 204 | return getBlockData(B)(D,getAnalysisData()); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 205 | } |
| 206 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 207 | bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 208 | return Live(D,getAnalysisData()); |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 209 | } |
| 210 | |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 211 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 212 | // printing liveness state for debugging |
| 213 | // |
| 214 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 215 | void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const { |
| 216 | const AnalysisDataTy& AD = getAnalysisData(); |
| 217 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 218 | for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), |
| 219 | E = AD.end_decl(); I!=E; ++I) |
| 220 | if (V.getDeclBit(I->second)) { |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 221 | SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation()); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 222 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 223 | fprintf(stderr, " %s <%s:%u:%u>\n", |
| 224 | I->first->getIdentifier()->getName(), |
| 225 | SM.getSourceName(PhysLoc), |
| 226 | SM.getLineNumber(PhysLoc), |
| 227 | SM.getColumnNumber(PhysLoc)); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 228 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 229 | } |
| 230 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 231 | void LiveVariables::dumpBlockLiveness(SourceManager& M) const { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 232 | for (BlockDataMapTy::iterator I = getBlockDataMap().begin(), |
| 233 | E = getBlockDataMap().end(); I!=E; ++I) { |
| 234 | fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n", |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 235 | I->first->getBlockID()); |
| 236 | |
| 237 | dumpLiveness(I->second,M); |
| 238 | } |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 239 | |
| 240 | fprintf(stderr,"\n"); |
| 241 | } |