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