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 | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 182 | // This represents a 'use' of the collection. |
| 183 | Visit(S->getCollection()); |
Ted Kremenek | 8f5aab6 | 2008-11-11 17:42:10 +0000 | [diff] [blame] | 184 | |
| 185 | // This represents a 'kill' for the variable. |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 186 | Stmt* Element = S->getElement(); |
Ted Kremenek | f8cce1d | 2008-11-13 05:26:15 +0000 | [diff] [blame] | 187 | DeclRefExpr *DR = 0; |
Ted Kremenek | e97d9db | 2008-11-11 19:40:47 +0000 | [diff] [blame] | 188 | VarDecl* VD = 0; |
| 189 | |
| 190 | if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) |
| 191 | VD = cast<VarDecl>(DS->getSolitaryDecl()); |
| 192 | else { |
| 193 | DR = cast<DeclRefExpr>(Element); |
| 194 | VD = cast<VarDecl>(DR->getDecl()); |
| 195 | } |
| 196 | |
| 197 | LiveState(VD, AD) = Dead; |
| 198 | if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } |
Ted Kremenek | 8f5aab6 | 2008-11-11 17:42:10 +0000 | [diff] [blame] | 199 | } |
| 200 | |
| 201 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 202 | void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 203 | Expr *E = U->getSubExpr(); |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 204 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 205 | switch (U->getOpcode()) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 206 | case UnaryOperator::PostInc: |
| 207 | case UnaryOperator::PostDec: |
| 208 | case UnaryOperator::PreInc: |
| 209 | case UnaryOperator::PreDec: |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 210 | // Walk through the subexpressions, blasting through ParenExprs |
| 211 | // until we either find a DeclRefExpr or some non-DeclRefExpr |
| 212 | // expression. |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 213 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) |
Ted Kremenek | dace4c9 | 2008-04-15 04:08:54 +0000 | [diff] [blame] | 214 | if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { |
| 215 | // Treat the --/++ operator as a kill. |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 216 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
Ted Kremenek | dace4c9 | 2008-04-15 04:08:54 +0000 | [diff] [blame] | 217 | LiveState(VD, AD) = Alive; |
Ted Kremenek | 5620631 | 2008-02-22 00:34:10 +0000 | [diff] [blame] | 218 | return VisitDeclRefExpr(DR); |
| 219 | } |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 220 | |
| 221 | // Fall-through. |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 222 | |
| 223 | default: |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 224 | return Visit(E); |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 225 | } |
| 226 | } |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 227 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 228 | void TransferFuncs::VisitAssign(BinaryOperator* B) { |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 229 | Expr* LHS = B->getLHS(); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 230 | |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 231 | // Assigning to a variable? |
Ted Kremenek | 5e2b609 | 2008-01-17 17:50:49 +0000 | [diff] [blame] | 232 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { |
Ted Kremenek | 7deed0c | 2008-04-15 18:35:30 +0000 | [diff] [blame] | 233 | |
| 234 | // Update liveness inforamtion. |
| 235 | unsigned bit = AD.getIdx(DR->getDecl()); |
| 236 | LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); |
| 237 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 238 | if (AD.Observer) { AD.Observer->ObserverKill(DR); } |
| 239 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 240 | // Handle things like +=, etc., which also generate "uses" |
| 241 | // of a variable. Do this just by visiting the subexpression. |
Ted Kremenek | bcb07d5 | 2007-09-28 21:29:33 +0000 | [diff] [blame] | 242 | if (B->getOpcode() != BinaryOperator::Assign) |
| 243 | VisitDeclRefExpr(DR); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 244 | } |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 245 | else // Not assigning to a variable. Process LHS as usual. |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 246 | Visit(LHS); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 247 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 248 | Visit(B->getRHS()); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 249 | } |
| 250 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 251 | void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { |
| 252 | // Declarations effectively "kill" a variable since they cannot |
| 253 | // possibly be live before they are declared. |
Ted Kremenek | 14f8b4f | 2008-08-05 20:46:55 +0000 | [diff] [blame] | 254 | for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); |
| 255 | DI != DE; ++DI) |
| 256 | if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { |
Ted Kremenek | 84fa6b9 | 2008-09-26 05:52:45 +0000 | [diff] [blame] | 257 | // The initializer is evaluated after the variable comes into scope. |
| 258 | // Since this is a reverse dataflow analysis, we must evaluate the |
| 259 | // transfer function for this expression first. |
Ted Kremenek | 2bca5e4 | 2008-02-07 02:38:55 +0000 | [diff] [blame] | 260 | if (Expr* Init = VD->getInit()) |
| 261 | Visit(Init); |
Ted Kremenek | 84fa6b9 | 2008-09-26 05:52:45 +0000 | [diff] [blame] | 262 | |
| 263 | // Update liveness information by killing the VarDecl. |
| 264 | unsigned bit = AD.getIdx(VD); |
| 265 | LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); |
Ted Kremenek | dcc4810 | 2008-02-25 22:28:54 +0000 | [diff] [blame] | 266 | } |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 267 | } |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 268 | |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 269 | } // end anonymous namespace |
| 270 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 271 | //===----------------------------------------------------------------------===// |
| 272 | // Merge operator: if something is live on any successor block, it is live |
| 273 | // in the current block (a set union). |
| 274 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 275 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 276 | namespace { |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 277 | |
| 278 | struct Merge { |
Ted Kremenek | 8d798c7 | 2008-11-14 01:14:18 +0000 | [diff] [blame^] | 279 | typedef StmtDeclBitVector_Types::ValTy ValTy; |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 280 | |
| 281 | void operator()(ValTy& Dst, const ValTy& Src) { |
| 282 | Dst.OrDeclBits(Src); |
Ted Kremenek | 8d798c7 | 2008-11-14 01:14:18 +0000 | [diff] [blame^] | 283 | Dst.AndBlkExprBits(Src); |
Ted Kremenek | fa59f1f | 2008-03-20 21:46:49 +0000 | [diff] [blame] | 284 | } |
| 285 | }; |
| 286 | |
| 287 | typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 288 | } // end anonymous namespace |
| 289 | |
| 290 | //===----------------------------------------------------------------------===// |
| 291 | // External interface to run Liveness analysis. |
| 292 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 293 | |
Ted Kremenek | 83c01da | 2008-01-11 00:40:29 +0000 | [diff] [blame] | 294 | void LiveVariables::runOnCFG(CFG& cfg) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 295 | Solver S(*this); |
| 296 | S.runOnCFG(cfg); |
| 297 | } |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 298 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 299 | void LiveVariables::runOnAllBlocks(const CFG& cfg, |
Ted Kremenek | 79649df | 2008-01-17 18:25:22 +0000 | [diff] [blame] | 300 | LiveVariables::ObserverTy* Obs, |
| 301 | bool recordStmtValues) { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 302 | Solver S(*this); |
| 303 | ObserverTy* OldObserver = getAnalysisData().Observer; |
Ted Kremenek | 79649df | 2008-01-17 18:25:22 +0000 | [diff] [blame] | 304 | getAnalysisData().Observer = Obs; |
| 305 | S.runOnAllBlocks(cfg, recordStmtValues); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 306 | getAnalysisData().Observer = OldObserver; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 307 | } |
| 308 | |
| 309 | //===----------------------------------------------------------------------===// |
| 310 | // liveness queries |
| 311 | // |
| 312 | |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 313 | bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { |
Ted Kremenek | 7cb1593 | 2008-03-13 16:55:07 +0000 | [diff] [blame] | 314 | DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); |
| 315 | return i.isValid() ? getBlockData(B).getBit(i) : false; |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 316 | } |
| 317 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 318 | bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { |
Ted Kremenek | 7cb1593 | 2008-03-13 16:55:07 +0000 | [diff] [blame] | 319 | DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); |
| 320 | return i.isValid() ? Live.getBit(i) : false; |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 321 | } |
| 322 | |
Ted Kremenek | 8694674 | 2008-01-17 20:48:37 +0000 | [diff] [blame] | 323 | bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { |
| 324 | return getStmtData(Loc)(StmtVal,getAnalysisData()); |
| 325 | } |
| 326 | |
Ted Kremenek | 2a9da9c | 2008-01-18 00:40:21 +0000 | [diff] [blame] | 327 | bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { |
| 328 | return getStmtData(Loc)(D,getAnalysisData()); |
| 329 | } |
| 330 | |
Ted Kremenek | 055c275 | 2007-09-06 23:00:42 +0000 | [diff] [blame] | 331 | //===----------------------------------------------------------------------===// |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 332 | // printing liveness state for debugging |
| 333 | // |
| 334 | |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 335 | void LiveVariables::dumpLiveness(const ValTy& V, SourceManager& SM) const { |
| 336 | const AnalysisDataTy& AD = getAnalysisData(); |
| 337 | |
Ted Kremenek | f63aa45 | 2007-09-28 20:38:59 +0000 | [diff] [blame] | 338 | for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), |
| 339 | E = AD.end_decl(); I!=E; ++I) |
| 340 | if (V.getDeclBit(I->second)) { |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 341 | SourceLocation PhysLoc = SM.getPhysicalLoc(I->first->getLocation()); |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 342 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 343 | fprintf(stderr, " %s <%s:%u:%u>\n", |
| 344 | I->first->getIdentifier()->getName(), |
| 345 | SM.getSourceName(PhysLoc), |
| 346 | SM.getLineNumber(PhysLoc), |
| 347 | SM.getColumnNumber(PhysLoc)); |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 348 | } |
Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame] | 349 | } |
| 350 | |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 351 | void LiveVariables::dumpBlockLiveness(SourceManager& M) const { |
Ted Kremenek | fdd225e | 2007-09-25 04:31:27 +0000 | [diff] [blame] | 352 | for (BlockDataMapTy::iterator I = getBlockDataMap().begin(), |
| 353 | E = getBlockDataMap().end(); I!=E; ++I) { |
| 354 | fprintf(stderr, "\n[ B%d (live variables at block exit) ]\n", |
Ted Kremenek | 27b07c5 | 2007-09-06 21:26:58 +0000 | [diff] [blame] | 355 | I->first->getBlockID()); |
| 356 | |
| 357 | dumpLiveness(I->second,M); |
| 358 | } |
Ted Kremenek | c0576ca | 2007-09-10 17:36:42 +0000 | [diff] [blame] | 359 | |
| 360 | fprintf(stderr,"\n"); |
| 361 | } |