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 | // |
Chris Lattner | 0bc735f | 2007-12-29 19:59:25 +0000 | [diff] [blame] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements Live Variables analysis for source-level CFGs. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Ted Kremenek | cf6e41b | 2007-12-21 21:42:19 +0000 | [diff] [blame] | 14 | #include "clang/Analysis/Analyses/LiveVariables.h" |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 15 | #include "clang/Basic/SourceManager.h" |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 16 | #include "clang/AST/Expr.h" |
| 17 | #include "clang/AST/CFG.h" |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 18 | #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" |
Ted Kremenek | 1de632b | 2007-09-25 21:00:24 +0000 | [diff] [blame] | 19 | #include "clang/Analysis/FlowSensitive/DataflowSolver.h" |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/SmallPtrSet.h" |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/SmallVector.h" |
Ted Kremenek | c2b51d8 | 2008-01-08 18:19:08 +0000 | [diff] [blame] | 22 | #include "llvm/Support/Compiler.h" |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 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 | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 30 | // Useful constants. |
| 31 | //===----------------------------------------------------------------------===// |
| 32 | |
| 33 | static const bool Alive = true; |
| 34 | static const bool Dead = false; |
| 35 | |
| 36 | //===----------------------------------------------------------------------===// |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 37 | // Dataflow initialization logic. |
| 38 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 39 | |
| 40 | namespace { |
Ted Kremenek | c2b51d8 | 2008-01-08 18:19:08 +0000 | [diff] [blame] | 41 | class VISIBILITY_HIDDEN RegisterDecls |
| 42 | : public CFGRecStmtDeclVisitor<RegisterDecls> { |
| 43 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 44 | LiveVariables::AnalysisDataTy& AD; |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 45 | |
| 46 | typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy; |
| 47 | AlwaysLiveTy AlwaysLive; |
| 48 | |
| 49 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 50 | public: |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 51 | RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} |
| 52 | |
| 53 | ~RegisterDecls() { |
| 54 | |
| 55 | AD.AlwaysLive.resetValues(AD); |
| 56 | |
| 57 | for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end(); |
| 58 | I != E; ++ I) |
| 59 | AD.AlwaysLive(*I, AD) = Alive; |
| 60 | } |
| 61 | |
Chris Lattner | 4111024 | 2008-06-17 18:05:57 +0000 | [diff] [blame] | 62 | void VisitImplicitParamDecl(ImplicitParamDecl* IPD) { |
| 63 | // Register the VarDecl for tracking. |
| 64 | AD.Register(IPD); |
| 65 | } |
| 66 | |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 67 | void VisitVarDecl(VarDecl* VD) { |
| 68 | // Register the VarDecl for tracking. |
| 69 | AD.Register(VD); |
| 70 | |
| 71 | // Does the variable have global storage? If so, it is always live. |
| 72 | if (VD->hasGlobalStorage()) |
| 73 | AlwaysLive.push_back(VD); |
| 74 | } |
| 75 | |
| 76 | void VisitUnaryOperator(UnaryOperator* U) { |
| 77 | // Check for '&'. Any VarDecl whose value has its address-taken we |
| 78 | // treat as always being live (flow-insensitive). |
| 79 | |
| 80 | Expr* E = U->getSubExpr()->IgnoreParenCasts(); |
| 81 | |
| 82 | if (U->getOpcode() == UnaryOperator::AddrOf) |
| 83 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E)) |
| 84 | if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { |
| 85 | AD.Register(VD); |
| 86 | AlwaysLive.push_back(VD); |
| 87 | return; |
| 88 | } |
| 89 | |
| 90 | Visit(E); |
| 91 | } |
| 92 | |
Ted Kremenek | 9f9141c | 2007-11-20 03:01:58 +0000 | [diff] [blame] | 93 | CFG& getCFG() { return AD.getCFG(); } |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 94 | }; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 95 | } // end anonymous namespace |
| 96 | |
Ted Kremenek | bffaa83 | 2008-01-29 05:13:23 +0000 | [diff] [blame] | 97 | |
Ted Kremenek | 7cb1593 | 2008-03-13 16:55:07 +0000 | [diff] [blame] | 98 | LiveVariables::LiveVariables(CFG& cfg) { |
| 99 | // Register all referenced VarDecls. |
Ted Kremenek | bffaa83 | 2008-01-29 05:13:23 +0000 | [diff] [blame] | 100 | getAnalysisData().setCFG(&cfg); |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 101 | RegisterDecls R(getAnalysisData()); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 102 | cfg.VisitBlockStmts(R); |
| 103 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 104 | |
| 105 | //===----------------------------------------------------------------------===// |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 106 | // Transfer functions. |
| 107 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 108 | |
| 109 | namespace { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 110 | |
Ted Kremenek | c2b51d8 | 2008-01-08 18:19:08 +0000 | [diff] [blame] | 111 | class VISIBILITY_HIDDEN TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 112 | LiveVariables::AnalysisDataTy& AD; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 113 | LiveVariables::ValTy LiveState; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 114 | public: |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 115 | TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 116 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 117 | LiveVariables::ValTy& getVal() { return LiveState; } |
Ted Kremenek | 9f9141c | 2007-11-20 03:01:58 +0000 | [diff] [blame] | 118 | CFG& getCFG() { return AD.getCFG(); } |
Ted Kremenek | f175805 | 2007-09-12 19:10:52 +0000 | [diff] [blame] | 119 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 120 | void VisitDeclRefExpr(DeclRefExpr* DR); |
| 121 | void VisitBinaryOperator(BinaryOperator* B); |
| 122 | void VisitAssign(BinaryOperator* B); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 123 | void VisitDeclStmt(DeclStmt* DS); |
Ted Kremenek | bfcb712 | 2008-11-12 21:58:46 +0000 | [diff] [blame] | 124 | void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 125 | void VisitUnaryOperator(UnaryOperator* U); |
Ted Kremenek | 8f5aab6 | 2008-11-11 17:42:10 +0000 | [diff] [blame] | 126 | void Visit(Stmt *S); |
Ted Kremenek | 411cdee | 2008-04-16 21:10:48 +0000 | [diff] [blame] | 127 | void VisitTerminator(CFGBlock* B); |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 128 | |
| 129 | void SetTopValue(LiveVariables::ValTy& V) { |
| 130 | V = AD.AlwaysLive; |
| 131 | } |
| 132 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 133 | }; |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 134 | |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 135 | void TransferFuncs::Visit(Stmt *S) { |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 136 | |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 137 | if (S == getCurrentBlkStmt()) { |
Ted Kremenek | 0364865 | 2008-07-03 22:25:27 +0000 | [diff] [blame] | 138 | |
| 139 | if (AD.Observer) |
| 140 | AD.Observer->ObserveStmt(S,AD,LiveState); |
| 141 | |
Ted Kremenek | 1aa9a58 | 2008-03-05 19:26:46 +0000 | [diff] [blame] | 142 | if (getCFG().isBlkExpr(S)) LiveState(S,AD) = Dead; |
Ted Kremenek | 2a9da9c | 2008-01-18 00:40:21 +0000 | [diff] [blame] | 143 | StmtVisitor<TransferFuncs,void>::Visit(S); |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 144 | } |
Ted Kremenek | 0364865 | 2008-07-03 22:25:27 +0000 | [diff] [blame] | 145 | else if (!getCFG().isBlkExpr(S)) { |
| 146 | |
| 147 | if (AD.Observer) |
| 148 | AD.Observer->ObserveStmt(S,AD,LiveState); |
| 149 | |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 150 | StmtVisitor<TransferFuncs,void>::Visit(S); |
Ted Kremenek | 0364865 | 2008-07-03 22:25:27 +0000 | [diff] [blame] | 151 | |
| 152 | } |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 153 | else |
| 154 | // For block-level expressions, mark that they are live. |
| 155 | LiveState(S,AD) = Alive; |
Ted Kremenek | 11e7218 | 2007-10-01 20:33:52 +0000 | [diff] [blame] | 156 | } |
Ted Kremenek | 3762208 | 2008-04-15 04:39:08 +0000 | [diff] [blame] | 157 | |
Ted Kremenek | 411cdee | 2008-04-16 21:10:48 +0000 | [diff] [blame] | 158 | void TransferFuncs::VisitTerminator(CFGBlock* B) { |
| 159 | |
Ted Kremenek | 8ded8d8 | 2008-11-12 21:12:18 +0000 | [diff] [blame] | 160 | const Stmt* E = B->getTerminatorCondition(); |
Ted Kremenek | 411cdee | 2008-04-16 21:10:48 +0000 | [diff] [blame] | 161 | |
Ted Kremenek | 5cd2438 | 2008-04-16 17:07:59 +0000 | [diff] [blame] | 162 | if (!E) |
| 163 | return; |
| 164 | |
Ted Kremenek | 5cd2438 | 2008-04-16 17:07:59 +0000 | [diff] [blame] | 165 | assert (getCFG().isBlkExpr(E)); |
| 166 | LiveState(E, AD) = Alive; |
Ted Kremenek | 3762208 | 2008-04-15 04:39:08 +0000 | [diff] [blame] | 167 | } |
| 168 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 169 | void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { |
| 170 | if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 171 | LiveState(V,AD) = Alive; |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 172 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 173 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 174 | void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { |
Ted Kremenek | f175805 | 2007-09-12 19:10:52 +0000 | [diff] [blame] | 175 | if (B->isAssignmentOp()) VisitAssign(B); |
| 176 | else VisitStmt(B); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 177 | } |
| 178 | |
Ted Kremenek | bfcb712 | 2008-11-12 21:58:46 +0000 | [diff] [blame] | 179 | void |
| 180 | TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { |
| 181 | |
Ted Kremenek | 06529ae | 2008-11-14 21:07:14 +0000 | [diff] [blame^] | 182 | // This is a block-level expression. Its value is 'dead' before this point. |
| 183 | LiveState(S, AD) = Dead; |
| 184 | |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 185 | // This represents a 'use' of the collection. |
| 186 | Visit(S->getCollection()); |
Ted Kremenek | 8f5aab6 | 2008-11-11 17:42:10 +0000 | [diff] [blame] | 187 | |
| 188 | // This represents a 'kill' for the variable. |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 189 | Stmt* Element = S->getElement(); |
Ted Kremenek | 8f64600 | 2008-11-14 01:58:12 +0000 | [diff] [blame] | 190 | DeclRefExpr* DR = 0; |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 191 | VarDecl* VD = 0; |
| 192 | |
| 193 | if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) |
| 194 | VD = cast<VarDecl>(DS->getSolitaryDecl()); |
| 195 | else { |
Ted Kremenek | 8f64600 | 2008-11-14 01:58:12 +0000 | [diff] [blame] | 196 | Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); |
| 197 | if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) |
| 198 | VD = cast<VarDecl>(DR->getDecl()); |
Ted Kremenek | 06529ae | 2008-11-14 21:07:14 +0000 | [diff] [blame^] | 199 | else { |
| 200 | Visit(ElemExpr); |
| 201 | return; |
| 202 | } |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 203 | } |
| 204 | |
Ted Kremenek | 8f64600 | 2008-11-14 01:58:12 +0000 | [diff] [blame] | 205 | if (VD) { |
| 206 | LiveState(VD, AD) = Dead; |
| 207 | if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } |
| 208 | } |
Ted Kremenek | 8f5aab6 | 2008-11-11 17:42:10 +0000 | [diff] [blame] | 209 | } |
| 210 | |
| 211 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 212 | void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 213 | Expr *E = U->getSubExpr(); |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 214 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 215 | switch (U->getOpcode()) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 216 | case UnaryOperator::PostInc: |
| 217 | case UnaryOperator::PostDec: |
| 218 | case UnaryOperator::PreInc: |
| 219 | case UnaryOperator::PreDec: |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 220 | // Walk through the subexpressions, blasting through ParenExprs |
| 221 | // until we either find a DeclRefExpr or some non-DeclRefExpr |
| 222 | // expression. |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 223 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) |
Ted Kremenek | dace4c9 | 2008-04-15 04:08:54 +0000 | [diff] [blame] | 224 | if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { |
| 225 | // Treat the --/++ operator as a kill. |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 226 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
Ted Kremenek | dace4c9 | 2008-04-15 04:08:54 +0000 | [diff] [blame] | 227 | LiveState(VD, AD) = Alive; |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 228 | return VisitDeclRefExpr(DR); |
| 229 | } |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 230 | |
| 231 | // Fall-through. |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 232 | |
| 233 | default: |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 234 | return Visit(E); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 235 | } |
| 236 | } |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 237 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 238 | void TransferFuncs::VisitAssign(BinaryOperator* B) { |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 239 | Expr* LHS = B->getLHS(); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 240 | |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 241 | // Assigning to a variable? |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 242 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 243 | |
| 244 | // Update liveness inforamtion. |
| 245 | unsigned bit = AD.getIdx(DR->getDecl()); |
| 246 | LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); |
| 247 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 248 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
| 249 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 250 | // Handle things like +=, etc., which also generate "uses" |
| 251 | // of a variable. Do this just by visiting the subexpression. |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 252 | if (B->getOpcode() != BinaryOperator::Assign) |
| 253 | VisitDeclRefExpr(DR); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 254 | } |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 255 | else // Not assigning to a variable. Process LHS as usual. |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 256 | Visit(LHS); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 257 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 258 | Visit(B->getRHS()); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 259 | } |
| 260 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 261 | void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { |
| 262 | // Declarations effectively "kill" a variable since they cannot |
| 263 | // possibly be live before they are declared. |
Ted Kremenek | 14f8b4f | 2008-08-05 20:46:55 +0000 | [diff] [blame] | 264 | for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); |
| 265 | DI != DE; ++DI) |
| 266 | if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { |
Ted Kremenek | 84fa6b9 | 2008-09-26 05:52:45 +0000 | [diff] [blame] | 267 | // The initializer is evaluated after the variable comes into scope. |
| 268 | // Since this is a reverse dataflow analysis, we must evaluate the |
| 269 | // transfer function for this expression first. |
Ted Kremenek | 2bca5e4 | 2008-02-07 02:38:55 +0000 | [diff] [blame] | 270 | if (Expr* Init = VD->getInit()) |
| 271 | Visit(Init); |
Ted Kremenek | 84fa6b9 | 2008-09-26 05:52:45 +0000 | [diff] [blame] | 272 | |
| 273 | // Update liveness information by killing the VarDecl. |
| 274 | unsigned bit = AD.getIdx(VD); |
| 275 | LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); |
Ted Kremenek | dcc4810 | 2008-02-25 22:28:54 +0000 | [diff] [blame] | 276 | } |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 277 | } |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 278 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 279 | } // end anonymous namespace |
| 280 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 281 | //===----------------------------------------------------------------------===// |
| 282 | // Merge operator: if something is live on any successor block, it is live |
| 283 | // in the current block (a set union). |
| 284 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 285 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 286 | namespace { |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 287 | |
| 288 | struct Merge { |
Ted Kremenek | 8d798c7 | 2008-11-14 01:14:18 +0000 | [diff] [blame] | 289 | typedef StmtDeclBitVector_Types::ValTy ValTy; |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 290 | |
| 291 | void operator()(ValTy& Dst, const ValTy& Src) { |
| 292 | Dst.OrDeclBits(Src); |
Ted Kremenek | 8d798c7 | 2008-11-14 01:14:18 +0000 | [diff] [blame] | 293 | Dst.AndBlkExprBits(Src); |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 294 | } |
| 295 | }; |
| 296 | |
| 297 | typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 298 | } // end anonymous namespace |
| 299 | |
| 300 | //===----------------------------------------------------------------------===// |
| 301 | // External interface to run Liveness analysis. |
| 302 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 303 | |
Ted Kremenek | 83c01da | 2008-01-11 00:40:29 +0000 | [diff] [blame] | 304 | void LiveVariables::runOnCFG(CFG& cfg) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 305 | Solver S(*this); |
| 306 | S.runOnCFG(cfg); |
| 307 | } |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 308 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 309 | void LiveVariables::runOnAllBlocks(const CFG& cfg, |
Ted Kremenek | 79649df | 2008-01-17 18:25:22 +0000 | [diff] [blame] | 310 | LiveVariables::ObserverTy* Obs, |
| 311 | bool recordStmtValues) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 312 | Solver S(*this); |
| 313 | ObserverTy* OldObserver = getAnalysisData().Observer; |
Ted Kremenek | 79649df | 2008-01-17 18:25:22 +0000 | [diff] [blame] | 314 | getAnalysisData().Observer = Obs; |
| 315 | S.runOnAllBlocks(cfg, recordStmtValues); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 316 | getAnalysisData().Observer = OldObserver; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 317 | } |
| 318 | |
| 319 | //===----------------------------------------------------------------------===// |
| 320 | // liveness queries |
| 321 | // |
| 322 | |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 323 | bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { |
Ted Kremenek | 7cb1593 | 2008-03-13 16:55:07 +0000 | [diff] [blame] | 324 | DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); |
| 325 | return i.isValid() ? getBlockData(B).getBit(i) : false; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 326 | } |
| 327 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 328 | bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { |
Ted Kremenek | 7cb1593 | 2008-03-13 16:55:07 +0000 | [diff] [blame] | 329 | DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); |
| 330 | return i.isValid() ? Live.getBit(i) : false; |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 331 | } |
| 332 | |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 333 | bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { |
| 334 | return getStmtData(Loc)(StmtVal,getAnalysisData()); |
| 335 | } |
| 336 | |
Ted Kremenek | 2a9da9c | 2008-01-18 00:40:21 +0000 | [diff] [blame] | 337 | bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { |
| 338 | return getStmtData(Loc)(D,getAnalysisData()); |
| 339 | } |
| 340 | |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 341 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 342 | // printing liveness state for debugging |
| 343 | // |
| 344 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 345 | void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const { |
| 346 | const AnalysisDataTy& AD = getAnalysisData(); |
| 347 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 348 | for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), |
| 349 | E = AD.end_decl(); I!=E; ++I) |
| 350 | if (V.getDeclBit(I->second)) { |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 351 | SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation()); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 352 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 353 | fprintf(stderr, " %s <%s:%u:%u>\n", |
| 354 | I->first->getIdentifier()->getName(), |
| 355 | SM.getSourceName(PhysLoc), |
| 356 | SM.getLineNumber(PhysLoc), |
| 357 | SM.getColumnNumber(PhysLoc)); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 358 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 359 | } |
| 360 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 361 | void LiveVariables::dumpBlockLiveness(SourceManager& M) const { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 362 | for (BlockDataMapTy::iterator I = getBlockDataMap().begin(), |
| 363 | E = getBlockDataMap().end(); I!=E; ++I) { |
| 364 | fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n", |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 365 | I->first->getBlockID()); |
| 366 | |
| 367 | dumpLiveness(I->second,M); |
| 368 | } |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 369 | |
| 370 | fprintf(stderr,"\n"); |
| 371 | } |