LiveVariables.cpp revision f91a5b008d1a63630ae483247204c2651e512fa1
1#include "clang/Analysis/Analyses/LiveVariables.h" 2#include "clang/AST/Stmt.h" 3#include "clang/Analysis/CFG.h" 4#include "clang/Analysis/AnalysisContext.h" 5#include "clang/AST/StmtVisitor.h" 6 7#include <deque> 8#include <algorithm> 9#include <vector> 10 11using namespace clang; 12 13namespace { 14 class LiveVariablesImpl { 15 public: 16 AnalysisContext &analysisContext; 17 std::vector<LiveVariables::LivenessValues> cfgBlockValues; 18 llvm::ImmutableSet<const Stmt *>::Factory SSetFact; 19 llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; 20 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksEndToLiveness; 21 llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues> blocksBeginToLiveness; 22 llvm::DenseMap<const Stmt *, LiveVariables::LivenessValues> stmtsToLiveness; 23 llvm::DenseMap<const DeclRefExpr *, unsigned> inAssignment; 24 const bool killAtAssign; 25 26 LiveVariables::LivenessValues 27 merge(LiveVariables::LivenessValues valsA, 28 LiveVariables::LivenessValues valsB); 29 30 LiveVariables::LivenessValues runOnBlock(const CFGBlock *block, 31 LiveVariables::LivenessValues val, 32 LiveVariables::Observer *obs = 0); 33 34 void dumpBlockLiveness(const SourceManager& M); 35 36 LiveVariablesImpl(AnalysisContext &ac, bool KillAtAssign) 37 : analysisContext(ac), killAtAssign(KillAtAssign) {} 38 }; 39} 40 41static LiveVariablesImpl &getImpl(void* x) { 42 return *((LiveVariablesImpl *) x); 43} 44 45//===----------------------------------------------------------------------===// 46// Operations and queries on LivenessValues. 47//===----------------------------------------------------------------------===// 48 49bool LiveVariables::LivenessValues::isLive(const Stmt *S) const { 50 return liveStmts.contains(S); 51} 52 53bool LiveVariables::LivenessValues::isLive(const VarDecl *D) const { 54 return liveDecls.contains(D); 55} 56 57namespace { 58 template <typename SET> 59 SET mergeSets(typename SET::Factory &F, SET A, SET B) { 60 for (typename SET::iterator it = B.begin(), ei = B.end(); it != ei; ++it) { 61 A = F.add(A, *it); 62 } 63 return A; 64 } 65} 66 67LiveVariables::LivenessValues 68LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, 69 LiveVariables::LivenessValues valsB) { 70 return LiveVariables::LivenessValues(mergeSets(SSetFact, valsA.liveStmts, valsB.liveStmts), 71 mergeSets(DSetFact, valsA.liveDecls, valsB.liveDecls)); 72} 73 74bool LiveVariables::LivenessValues::equals(const LivenessValues &V) const { 75 return liveStmts == V.liveStmts && liveDecls == V.liveDecls; 76} 77 78//===----------------------------------------------------------------------===// 79// Query methods. 80//===----------------------------------------------------------------------===// 81 82static bool isAlwaysAlive(const VarDecl *D) { 83 return D->hasGlobalStorage(); 84} 85 86bool LiveVariables::isLive(const CFGBlock *B, const VarDecl *D) { 87 return isAlwaysAlive(D) || getImpl(impl).blocksEndToLiveness[B].isLive(D); 88} 89 90bool LiveVariables::isLive(const Stmt *S, const VarDecl *D) { 91 return isAlwaysAlive(D) || getImpl(impl).stmtsToLiveness[S].isLive(D); 92} 93 94bool LiveVariables::isLive(const Stmt *Loc, const Stmt *S) { 95 return getImpl(impl).stmtsToLiveness[Loc].isLive(S); 96} 97 98//===----------------------------------------------------------------------===// 99// Dataflow computation. 100//===----------------------------------------------------------------------===// 101 102namespace { 103class Worklist { 104 llvm::BitVector isBlockEnqueued; 105 std::deque<const CFGBlock *> workListContents; 106public: 107 Worklist(CFG &cfg) : isBlockEnqueued(cfg.getNumBlockIDs()) {} 108 109 bool empty() const { return workListContents.empty(); } 110 111 const CFGBlock *getNextItem() { 112 const CFGBlock *block = workListContents.front(); 113 workListContents.pop_front(); 114 isBlockEnqueued[block->getBlockID()] = false; 115 return block; 116 } 117 118 void enqueueBlock(const CFGBlock *block) { 119 if (!isBlockEnqueued[block->getBlockID()]) { 120 isBlockEnqueued[block->getBlockID()] = true; 121 workListContents.push_back(block); 122 } 123 } 124}; 125 126class TransferFunctions : public StmtVisitor<TransferFunctions> { 127 LiveVariablesImpl &LV; 128 LiveVariables::LivenessValues &val; 129 LiveVariables::Observer *observer; 130 const CFGBlock *currentBlock; 131public: 132 TransferFunctions(LiveVariablesImpl &im, 133 LiveVariables::LivenessValues &Val, 134 LiveVariables::Observer *Observer, 135 const CFGBlock *CurrentBlock) 136 : LV(im), val(Val), observer(Observer), currentBlock(CurrentBlock) {} 137 138 void VisitBinaryOperator(BinaryOperator *BO); 139 void VisitBlockExpr(BlockExpr *BE); 140 void VisitDeclRefExpr(DeclRefExpr *DR); 141 void VisitDeclStmt(DeclStmt *DS); 142 void VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS); 143 void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE); 144 void VisitUnaryOperator(UnaryOperator *UO); 145 void Visit(Stmt *S); 146}; 147} 148 149static const VariableArrayType *FindVA(QualType Ty) { 150 const Type *ty = Ty.getTypePtr(); 151 while (const ArrayType *VT = dyn_cast<ArrayType>(ty)) { 152 if (const VariableArrayType *VAT = dyn_cast<VariableArrayType>(VT)) 153 if (VAT->getSizeExpr()) 154 return VAT; 155 156 ty = VT->getElementType().getTypePtr(); 157 } 158 159 return 0; 160} 161 162void TransferFunctions::Visit(Stmt *S) { 163 if (observer) 164 observer->observeStmt(S, currentBlock, val); 165 166 StmtVisitor<TransferFunctions>::Visit(S); 167 168 if (isa<Expr>(S)) { 169 val.liveStmts = LV.SSetFact.remove(val.liveStmts, S); 170 } 171 172 // Mark all children expressions live. 173 174 switch (S->getStmtClass()) { 175 default: 176 break; 177 case Stmt::StmtExprClass: { 178 // For statement expressions, look through the compound statement. 179 S = cast<StmtExpr>(S)->getSubStmt(); 180 break; 181 } 182 case Stmt::CXXMemberCallExprClass: { 183 // Include the implicit "this" pointer as being live. 184 CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); 185 val.liveStmts = 186 LV.SSetFact.add(val.liveStmts, 187 CE->getImplicitObjectArgument()->IgnoreParens()); 188 break; 189 } 190 case Stmt::DeclStmtClass: { 191 const DeclStmt *DS = cast<DeclStmt>(S); 192 if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { 193 for (const VariableArrayType* VA = FindVA(VD->getType()); 194 VA != 0; VA = FindVA(VA->getElementType())) { 195 val.liveStmts = LV.SSetFact.add(val.liveStmts, 196 VA->getSizeExpr()->IgnoreParens()); 197 } 198 } 199 break; 200 } 201 // FIXME: These cases eventually shouldn't be needed. 202 case Stmt::ExprWithCleanupsClass: { 203 S = cast<ExprWithCleanups>(S)->getSubExpr(); 204 break; 205 } 206 case Stmt::CXXBindTemporaryExprClass: { 207 S = cast<CXXBindTemporaryExpr>(S)->getSubExpr(); 208 break; 209 } 210 case Stmt::MaterializeTemporaryExprClass: { 211 S = cast<MaterializeTemporaryExpr>(S)->GetTemporaryExpr(); 212 break; 213 } 214 case Stmt::UnaryExprOrTypeTraitExprClass: { 215 // No need to unconditionally visit subexpressions. 216 return; 217 } 218 } 219 220 for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); 221 it != ei; ++it) { 222 if (Stmt *child = *it) { 223 if (Expr *Ex = dyn_cast<Expr>(child)) 224 child = Ex->IgnoreParens(); 225 226 val.liveStmts = LV.SSetFact.add(val.liveStmts, child); 227 } 228 } 229} 230 231void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { 232 if (B->isAssignmentOp()) { 233 if (!LV.killAtAssign) 234 return; 235 236 // Assigning to a variable? 237 Expr *LHS = B->getLHS()->IgnoreParens(); 238 239 if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS)) 240 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { 241 // Assignments to references don't kill the ref's address 242 if (VD->getType()->isReferenceType()) 243 return; 244 245 if (!isAlwaysAlive(VD)) { 246 // The variable is now dead. 247 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 248 } 249 250 if (observer) 251 observer->observerKill(DR); 252 } 253 } 254} 255 256void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { 257 AnalysisContext::referenced_decls_iterator I, E; 258 llvm::tie(I, E) = 259 LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); 260 for ( ; I != E ; ++I) { 261 const VarDecl *VD = *I; 262 if (isAlwaysAlive(VD)) 263 continue; 264 val.liveDecls = LV.DSetFact.add(val.liveDecls, VD); 265 } 266} 267 268void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *DR) { 269 if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) 270 if (!isAlwaysAlive(D) && LV.inAssignment.find(DR) == LV.inAssignment.end()) 271 val.liveDecls = LV.DSetFact.add(val.liveDecls, D); 272} 273 274void TransferFunctions::VisitDeclStmt(DeclStmt *DS) { 275 for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); 276 DI != DE; ++DI) 277 if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { 278 if (!isAlwaysAlive(VD)) 279 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 280 } 281} 282 283void TransferFunctions::VisitObjCForCollectionStmt(ObjCForCollectionStmt *OS) { 284 // Kill the iteration variable. 285 DeclRefExpr *DR = 0; 286 const VarDecl *VD = 0; 287 288 Stmt *element = OS->getElement(); 289 if (DeclStmt *DS = dyn_cast<DeclStmt>(element)) { 290 VD = cast<VarDecl>(DS->getSingleDecl()); 291 } 292 else if ((DR = dyn_cast<DeclRefExpr>(cast<Expr>(element)->IgnoreParens()))) { 293 VD = cast<VarDecl>(DR->getDecl()); 294 } 295 296 if (VD) { 297 val.liveDecls = LV.DSetFact.remove(val.liveDecls, VD); 298 if (observer && DR) 299 observer->observerKill(DR); 300 } 301} 302 303void TransferFunctions:: 304VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *UE) 305{ 306 // While sizeof(var) doesn't technically extend the liveness of 'var', it 307 // does extent the liveness of metadata if 'var' is a VariableArrayType. 308 // We handle that special case here. 309 if (UE->getKind() != UETT_SizeOf || UE->isArgumentType()) 310 return; 311 312 const Expr *subEx = UE->getArgumentExpr(); 313 if (subEx->getType()->isVariableArrayType()) { 314 assert(subEx->isLValue()); 315 val.liveStmts = LV.SSetFact.add(val.liveStmts, subEx->IgnoreParens()); 316 } 317} 318 319void TransferFunctions::VisitUnaryOperator(UnaryOperator *UO) { 320 // Treat ++/-- as a kill. 321 // Note we don't actually have to do anything if we don't have an observer, 322 // since a ++/-- acts as both a kill and a "use". 323 if (!observer) 324 return; 325 326 switch (UO->getOpcode()) { 327 default: 328 return; 329 case UO_PostInc: 330 case UO_PostDec: 331 case UO_PreInc: 332 case UO_PreDec: 333 break; 334 } 335 336 if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(UO->getSubExpr()->IgnoreParens())) 337 if (isa<VarDecl>(DR->getDecl())) { 338 // Treat ++/-- as a kill. 339 observer->observerKill(DR); 340 } 341} 342 343LiveVariables::LivenessValues 344LiveVariablesImpl::runOnBlock(const CFGBlock *block, 345 LiveVariables::LivenessValues val, 346 LiveVariables::Observer *obs) { 347 348 TransferFunctions TF(*this, val, obs, block); 349 350 // Visit the terminator (if any). 351 if (const Stmt *term = block->getTerminator()) 352 TF.Visit(const_cast<Stmt*>(term)); 353 354 // Apply the transfer function for all Stmts in the block. 355 for (CFGBlock::const_reverse_iterator it = block->rbegin(), 356 ei = block->rend(); it != ei; ++it) { 357 const CFGElement &elem = *it; 358 if (!isa<CFGStmt>(elem)) 359 continue; 360 361 const Stmt *S = cast<CFGStmt>(elem).getStmt(); 362 TF.Visit(const_cast<Stmt*>(S)); 363 stmtsToLiveness[S] = val; 364 } 365 return val; 366} 367 368void LiveVariables::runOnAllBlocks(LiveVariables::Observer &obs) { 369 const CFG *cfg = getImpl(impl).analysisContext.getCFG(); 370 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) 371 getImpl(impl).runOnBlock(*it, getImpl(impl).blocksEndToLiveness[*it], &obs); 372} 373 374LiveVariables::LiveVariables(void *im) : impl(im) {} 375 376LiveVariables::~LiveVariables() { 377 delete (LiveVariablesImpl*) impl; 378} 379 380LiveVariables * 381LiveVariables::computeLiveness(AnalysisContext &AC, 382 bool killAtAssign) { 383 384 // No CFG? Bail out. 385 CFG *cfg = AC.getCFG(); 386 if (!cfg) 387 return 0; 388 389 LiveVariablesImpl *LV = new LiveVariablesImpl(AC, killAtAssign); 390 391 // Construct the dataflow worklist. Enqueue the exit block as the 392 // start of the analysis. 393 Worklist worklist(*cfg); 394 llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); 395 396 // FIXME: we should enqueue using post order. 397 for (CFG::const_iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) { 398 const CFGBlock *block = *it; 399 worklist.enqueueBlock(block); 400 401 // FIXME: Scan for DeclRefExprs using in the LHS of an assignment. 402 // We need to do this because we lack context in the reverse analysis 403 // to determine if a DeclRefExpr appears in such a context, and thus 404 // doesn't constitute a "use". 405 if (killAtAssign) 406 for (CFGBlock::const_iterator bi = block->begin(), be = block->end(); 407 bi != be; ++bi) { 408 if (const CFGStmt *cs = bi->getAs<CFGStmt>()) { 409 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(cs->getStmt())) { 410 if (BO->getOpcode() == BO_Assign) { 411 if (const DeclRefExpr *DR = 412 dyn_cast<DeclRefExpr>(BO->getLHS()->IgnoreParens())) { 413 LV->inAssignment[DR] = 1; 414 } 415 } 416 } 417 } 418 } 419 } 420 421 while (!worklist.empty()) { 422 // Dequeue blocks in FIFO order. 423 const CFGBlock *block = worklist.getNextItem(); 424 425 // Determine if the block's end value has changed. If not, we 426 // have nothing left to do for this block. 427 LivenessValues &prevVal = LV->blocksEndToLiveness[block]; 428 429 // Merge the values of all successor blocks. 430 LivenessValues val; 431 for (CFGBlock::const_succ_iterator it = block->succ_begin(), 432 ei = block->succ_end(); it != ei; ++it) { 433 if (const CFGBlock *succ = *it) 434 val = LV->merge(val, LV->blocksBeginToLiveness[succ]); 435 } 436 437 if (!everAnalyzedBlock[block->getBlockID()]) 438 everAnalyzedBlock[block->getBlockID()] = true; 439 else if (prevVal.equals(val)) 440 continue; 441 442 prevVal = val; 443 444 // Update the dataflow value for the start of this block. 445 LV->blocksBeginToLiveness[block] = LV->runOnBlock(block, val); 446 447 // Enqueue the value to the predecessors. 448 for (CFGBlock::const_pred_iterator it = block->pred_begin(), 449 ei = block->pred_end(); it != ei; ++it) 450 { 451 if (const CFGBlock *pred = *it) 452 worklist.enqueueBlock(pred); 453 } 454 } 455 456 return new LiveVariables(LV); 457} 458 459static bool compare_entries(const CFGBlock *A, const CFGBlock *B) { 460 return A->getBlockID() < B->getBlockID(); 461} 462 463static bool compare_vd_entries(const Decl *A, const Decl *B) { 464 SourceLocation ALoc = A->getLocStart(); 465 SourceLocation BLoc = B->getLocStart(); 466 return ALoc.getRawEncoding() < BLoc.getRawEncoding(); 467} 468 469void LiveVariables::dumpBlockLiveness(const SourceManager &M) { 470 getImpl(impl).dumpBlockLiveness(M); 471} 472 473void LiveVariablesImpl::dumpBlockLiveness(const SourceManager &M) { 474 std::vector<const CFGBlock *> vec; 475 for (llvm::DenseMap<const CFGBlock *, LiveVariables::LivenessValues>::iterator 476 it = blocksEndToLiveness.begin(), ei = blocksEndToLiveness.end(); 477 it != ei; ++it) { 478 vec.push_back(it->first); 479 } 480 std::sort(vec.begin(), vec.end(), compare_entries); 481 482 std::vector<const VarDecl*> declVec; 483 484 for (std::vector<const CFGBlock *>::iterator 485 it = vec.begin(), ei = vec.end(); it != ei; ++it) { 486 llvm::errs() << "\n[ B" << (*it)->getBlockID() 487 << " (live variables at block exit) ]\n"; 488 489 LiveVariables::LivenessValues vals = blocksEndToLiveness[*it]; 490 declVec.clear(); 491 492 for (llvm::ImmutableSet<const VarDecl *>::iterator si = 493 vals.liveDecls.begin(), 494 se = vals.liveDecls.end(); si != se; ++si) { 495 declVec.push_back(*si); 496 } 497 498 std::sort(declVec.begin(), declVec.end(), compare_vd_entries); 499 500 for (std::vector<const VarDecl*>::iterator di = declVec.begin(), 501 de = declVec.end(); di != de; ++di) { 502 llvm::errs() << " " << (*di)->getDeclName().getAsString() 503 << " <"; 504 (*di)->getLocation().dump(M); 505 llvm::errs() << ">\n"; 506 } 507 } 508 llvm::errs() << "\n"; 509} 510 511