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