Ted Kremenek | e4e6334 | 2007-09-06 00:17:54 +0000 | [diff] [blame^] | 1 | //==- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by Ted Kremenek and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements Live Variables analysis for source-level CFGs. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "clang/Analysis/LiveVariables.h" |
| 15 | #include "clang/AST/Expr.h" |
| 16 | #include "clang/AST/CFG.h" |
| 17 | #include "clang/AST/StmtVisitor.h" |
| 18 | #include "clang/Lex/IdentifierTable.h" |
| 19 | #include "llvm/ADT/SmallPtrSet.h" |
| 20 | |
| 21 | #include <iostream> |
| 22 | |
| 23 | using namespace clang; |
| 24 | |
| 25 | //===----------------------------------------------------------------------===// |
| 26 | // RegisterDecls - Utility class to create VarInfo objects for all |
| 27 | // Decls referenced in a function. |
| 28 | // |
| 29 | |
| 30 | namespace { |
| 31 | |
| 32 | class RegisterDecls : public StmtVisitor<RegisterDecls,void> { |
| 33 | LiveVariables& L; |
| 34 | const CFG& cfg; |
| 35 | public: |
| 36 | RegisterDecls(LiveVariables& l, const CFG& c) |
| 37 | : L(l), cfg(c) {} |
| 38 | |
| 39 | void VisitStmt(Stmt* S); |
| 40 | void VisitDeclRefExpr(DeclRefExpr* DR); |
| 41 | void Register(Decl* D); |
| 42 | void RegisterUsedDecls(); |
| 43 | }; |
| 44 | |
| 45 | void RegisterDecls::VisitStmt(Stmt* S) { |
| 46 | for (Stmt::child_iterator I = S->child_begin(),E = S->child_end(); I != E;++I) |
| 47 | Visit(*I); |
| 48 | } |
| 49 | |
| 50 | void RegisterDecls::VisitDeclRefExpr(DeclRefExpr* DR) { |
| 51 | for (Decl* D = DR->getDecl() ; D != NULL ; D = D->getNextDeclarator()) |
| 52 | Register(D); |
| 53 | } |
| 54 | |
| 55 | void RegisterDecls::Register(Decl* D) { |
| 56 | LiveVariables::VPair& VP = L.getVarInfoMap()[const_cast<const Decl*>(D)]; |
| 57 | |
| 58 | VP.V.AliveBlocks.reserve(cfg.getNumBlockIDs()); |
| 59 | VP.Idx = L.getNumDecls()++; |
| 60 | } |
| 61 | |
| 62 | void RegisterDecls::RegisterUsedDecls() { |
| 63 | for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) |
| 64 | for (CFGBlock::const_iterator SI=BI->begin(),SE = BI->end();SI != SE;++SI) |
| 65 | Visit(const_cast<Stmt*>(*SI)); |
| 66 | } |
| 67 | |
| 68 | |
| 69 | } // end anonymous namespace |
| 70 | |
| 71 | //===----------------------------------------------------------------------===// |
| 72 | // WorkList - Data structure representing the liveness algorithm worklist. |
| 73 | // |
| 74 | |
| 75 | namespace { |
| 76 | |
| 77 | class WorkListTy { |
| 78 | typedef llvm::SmallPtrSet<const CFGBlock*,20> BlockSet; |
| 79 | BlockSet wlist; |
| 80 | public: |
| 81 | void enqueue(const CFGBlock* B) { wlist.insert(B); } |
| 82 | |
| 83 | const CFGBlock* dequeue() { |
| 84 | assert (!wlist.empty()); |
| 85 | const CFGBlock* B = *wlist.begin(); |
| 86 | wlist.erase(B); |
| 87 | return B; |
| 88 | } |
| 89 | |
| 90 | bool isEmpty() const { return wlist.empty(); } |
| 91 | }; |
| 92 | |
| 93 | } // end anonymous namespace |
| 94 | |
| 95 | //===----------------------------------------------------------------------===// |
| 96 | // TFuncs |
| 97 | // |
| 98 | |
| 99 | namespace { |
| 100 | |
| 101 | class LivenessTFuncs : public StmtVisitor<LivenessTFuncs,void> { |
| 102 | LiveVariables& L; |
| 103 | llvm::BitVector Live; |
| 104 | llvm::BitVector Killed; |
| 105 | public: |
| 106 | LivenessTFuncs(LiveVariables& l) : L(l) { |
| 107 | Live.resize(l.getNumDecls()); |
| 108 | Killed.resize(l.getNumDecls()); |
| 109 | } |
| 110 | |
| 111 | void VisitStmt(Stmt* S); |
| 112 | void VisitDeclRefExpr(DeclRefExpr* DR); |
| 113 | void VisitBinaryOperator(BinaryOperator* B); |
| 114 | void VisitAssign(BinaryOperator* B); |
| 115 | void VisitStmtExpr(StmtExpr* S); |
| 116 | |
| 117 | unsigned getIdx(const Decl* D) { |
| 118 | LiveVariables::VarInfoMap& V = L.getVarInfoMap(); |
| 119 | LiveVariables::VarInfoMap::iterator I = V.find(D); |
| 120 | assert (I != V.end()); |
| 121 | return I->second.Idx; |
| 122 | } |
| 123 | |
| 124 | bool ProcessBlock(const CFGBlock* B); |
| 125 | llvm::BitVector* getLiveness(const CFGBlock* B); |
| 126 | |
| 127 | }; |
| 128 | |
| 129 | void LivenessTFuncs::VisitStmt(Stmt* S) { |
| 130 | // Evaluate the transfer functions for all subexpressions. Note that |
| 131 | // each invocation of "Visit" will have a side-effect: "Liveness" and "Kills" |
| 132 | // will be updated. |
| 133 | for (Stmt::child_iterator I = S->child_begin(),E = S->child_end(); I != E;++I) |
| 134 | Visit(*I); |
| 135 | } |
| 136 | |
| 137 | void LivenessTFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { |
| 138 | // Register a use of the variable. |
| 139 | Live.set(getIdx(DR->getDecl())); |
| 140 | } |
| 141 | |
| 142 | void LivenessTFuncs::VisitStmtExpr(StmtExpr* S) { |
| 143 | // Do nothing. The substatements of S are segmented into separate |
| 144 | // statements in the CFG. |
| 145 | } |
| 146 | |
| 147 | void LivenessTFuncs::VisitBinaryOperator(BinaryOperator* B) { |
| 148 | switch (B->getOpcode()) { |
| 149 | case BinaryOperator::LAnd: |
| 150 | case BinaryOperator::LOr: |
| 151 | case BinaryOperator::Comma: |
| 152 | // Do nothing. These operations are broken up into multiple |
| 153 | // statements in the CFG. All these expressions do is return |
| 154 | // the value of their subexpressions, but these expressions will |
| 155 | // be evalualated elsewhere in the CFG. |
| 156 | break; |
| 157 | |
| 158 | // FIXME: handle '++' and '--' |
| 159 | default: |
| 160 | if (B->isAssignmentOp()) VisitAssign(B); |
| 161 | else Visit(B); |
| 162 | } |
| 163 | } |
| 164 | |
| 165 | |
| 166 | void LivenessTFuncs::VisitAssign(BinaryOperator* B) { |
| 167 | Stmt* LHS = B->getLHS(); |
| 168 | |
| 169 | if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) { |
| 170 | unsigned i = getIdx(DR->getDecl()); |
| 171 | Live.reset(i); |
| 172 | Killed.set(i); |
| 173 | } |
| 174 | else Visit(LHS); |
| 175 | |
| 176 | Visit(B->getRHS()); |
| 177 | } |
| 178 | |
| 179 | |
| 180 | llvm::BitVector* LivenessTFuncs::getLiveness(const CFGBlock* B) { |
| 181 | LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap(); |
| 182 | |
| 183 | LiveVariables::BlockLivenessMap::iterator I = BMap.find(B); |
| 184 | return (I == BMap.end()) ? NULL : &(I->second); |
| 185 | } |
| 186 | |
| 187 | bool LivenessTFuncs::ProcessBlock(const CFGBlock* B) { |
| 188 | // First: merge all predecessors. |
| 189 | Live.reset(); |
| 190 | Killed.reset(); |
| 191 | |
| 192 | for (CFGBlock::const_succ_iterator I=B->succ_begin(),E=B->succ_end();I!=E;++I) |
| 193 | if (llvm::BitVector* V = getLiveness(*I)) |
| 194 | Live |= *V; |
| 195 | |
| 196 | // Second: march up the statements and process the transfer functions. |
| 197 | for (CFGBlock::const_reverse_iterator I=B->rbegin(), E=B->rend(); I!=E; ++I) { |
| 198 | Visit(*I); |
| 199 | } |
| 200 | |
| 201 | // Third: compare the computed "Live" values with what we already have |
| 202 | // for this block. |
| 203 | bool hasChanged = false; |
| 204 | |
| 205 | LiveVariables::BlockLivenessMap& BMap = L.getLiveAtBlockEntryMap(); |
| 206 | LiveVariables::BlockLivenessMap::iterator I = BMap.find(B); |
| 207 | if (I == BMap.end()) { |
| 208 | hasChanged = true; |
| 209 | llvm::BitVector& V = BMap[B]; |
| 210 | V.resize(L.getNumDecls()); |
| 211 | V |= Live; |
| 212 | } |
| 213 | else if (I->second != Live) { |
| 214 | hasChanged = true; |
| 215 | I->second = Live; |
| 216 | } |
| 217 | |
| 218 | return hasChanged; |
| 219 | } |
| 220 | |
| 221 | } // end anonymous namespace |
| 222 | |
| 223 | //===----------------------------------------------------------------------===// |
| 224 | // runOnCFG - Method to run the actual liveness computation. |
| 225 | // |
| 226 | |
| 227 | void LiveVariables::runOnCFG(const CFG& cfg) { |
| 228 | // Scan a CFG for DeclRefStmts. For each one, create a VarInfo object. |
| 229 | { |
| 230 | RegisterDecls R(*this,cfg); |
| 231 | R.RegisterUsedDecls(); |
| 232 | } |
| 233 | |
| 234 | // Create the worklist and enqueue the exit block. |
| 235 | WorkListTy WorkList; |
| 236 | WorkList.enqueue(&cfg.getExit()); |
| 237 | |
| 238 | // Create the state for transfer functions. |
| 239 | LivenessTFuncs TF(*this); |
| 240 | |
| 241 | // Process the worklist until it is empty. |
| 242 | |
| 243 | while (!WorkList.isEmpty()) { |
| 244 | const CFGBlock* B = WorkList.dequeue(); |
| 245 | if (TF.ProcessBlock(B)) |
| 246 | for (CFGBlock::const_pred_iterator I = B->pred_begin(), E = B->pred_end(); |
| 247 | I != E; ++I) |
| 248 | WorkList.enqueue(*I); |
| 249 | } |
| 250 | |
| 251 | // Go through each block and reserve a bitvector. |
| 252 | for (CFG::const_iterator I = cfg.begin(), E = cfg.end(); I != E; ++I) |
| 253 | LiveAtBlockEntryMap[&(*I)].resize(NumDecls); |
| 254 | } |
| 255 | |
| 256 | //===----------------------------------------------------------------------===// |
| 257 | // printing liveness state for debugging |
| 258 | // |
| 259 | |
| 260 | void LiveVariables::printLiveness(const llvm::BitVector& V, |
| 261 | std::ostream& OS) const { |
| 262 | |
| 263 | for (VarInfoMap::iterator I = VarInfos.begin(), E=VarInfos.end(); I!=E; ++I) { |
| 264 | if (V[I->second.Idx]) { |
| 265 | OS << I->first->getIdentifier()->getName() << "\n"; |
| 266 | } |
| 267 | } |
| 268 | } |
| 269 | |
| 270 | void LiveVariables::printBlockLiveness(std::ostream& OS) const { |
| 271 | for (BlockLivenessMap::iterator I = LiveAtBlockEntryMap.begin(), |
| 272 | E = LiveAtBlockEntryMap.end(); |
| 273 | I != E; ++I) { |
| 274 | OS << "\n[ B" << I->first->getBlockID() |
| 275 | << " (live variables at block entry) ]\n"; |
| 276 | printLiveness(I->second, OS); |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | void LiveVariables::DumpBlockLiveness() const { |
| 281 | printBlockLiveness(std::cerr); |
| 282 | } |