ReachableCode.cpp revision 1d26f48dc2eea1c07431ca1519d7034a21b9bcff
1868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// 2868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 3868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// The LLVM Compiler Infrastructure 4868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 5868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 6868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// License. See LICENSE.TXT for details. 7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 8868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//===----------------------------------------------------------------------===// 9868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 10868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// This file implements a flow-sensitive, path-insensitive analysis of 11868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// determining reachable blocks within a CFG. 12868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 13868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)//===----------------------------------------------------------------------===// 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 15868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "llvm/ADT/BitVector.h" 16868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "llvm/ADT/SmallVector.h" 171320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/AST/Expr.h" 181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci#include "clang/AST/ExprCXX.h" 19868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/AST/ExprObjC.h" 20a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles)#include "clang/AST/StmtCXX.h" 21868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/Analysis/Analyses/ReachableCode.h" 22868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/Analysis/CFG.h" 23868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/Analysis/AnalysisContext.h" 24868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)#include "clang/Basic/SourceManager.h" 25868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 26868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)using namespace clang; 27868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 28868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)namespace { 29868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)class DeadCodeScan { 30a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) llvm::BitVector Visited; 31868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) llvm::BitVector &Reachable; 32868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) llvm::SmallVector<const CFGBlock *, 10> WorkList; 33868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 34868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) typedef llvm::SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12> 35868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DeferredLocsTy; 36868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 37868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) DeferredLocsTy DeferredLocs; 381320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci 391320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tuccipublic: 401320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci DeadCodeScan(llvm::BitVector &reachable) 411320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci : Visited(reachable.size()), 42868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Reachable(reachable) {} 43a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 44868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) void enqueue(const CFGBlock *block); 45868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) unsigned scanBackwards(const CFGBlock *Start, 46868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) clang::reachable_code::Callback &CB); 47868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 48868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) bool isDeadCodeRoot(const CFGBlock *Block); 49a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) 50868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) const Stmt *findDeadCode(const CFGBlock *Block); 51868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 52868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) void reportDeadCode(const Stmt *S, 53868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) clang::reachable_code::Callback &CB); 54868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)}; 55868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 56868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 57868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)void DeadCodeScan::enqueue(const CFGBlock *block) { 58868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) unsigned blockID = block->getBlockID(); 59868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (Reachable[blockID] || Visited[blockID]) 60868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return; 61868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Visited[blockID] = true; 62868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) WorkList.push_back(block); 63868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)} 64868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 65868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { 66868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) bool isDeadRoot = true; 67868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 68a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 69868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) E = Block->pred_end(); I != E; ++I) { 70a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) if (const CFGBlock *PredBlock = *I) { 71868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) unsigned blockID = PredBlock->getBlockID(); 72868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (Visited[blockID]) { 73868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) isDeadRoot = false; 74868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) continue; 75a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 76868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) if (!Reachable[blockID]) { 77a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) isDeadRoot = false; 78868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) Visited[blockID] = true; 79868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) WorkList.push_back(PredBlock); 80868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) continue; 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) } 83f8ee788a64d60abd8f2d742a5fdedde054ecd910Torne (Richard Coles) } 84868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) 85868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) return isDeadRoot; 86} 87 88static bool isValidDeadStmt(const Stmt *S) { 89 if (S->getLocStart().isInvalid()) 90 return false; 91 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) 92 return BO->getOpcode() != BO_Comma; 93 return true; 94} 95 96const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 97 for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I) 98 if (const CFGStmt *CS = I->getAs<CFGStmt>()) { 99 const Stmt *S = CS->getStmt(); 100 if (isValidDeadStmt(S)) 101 return S; 102 } 103 104 if (CFGTerminator T = Block->getTerminator()) { 105 const Stmt *S = T.getStmt(); 106 if (isValidDeadStmt(S)) 107 return S; 108 } 109 110 return 0; 111} 112 113static int SrcCmp(const void *p1, const void *p2) { 114 return 115 ((std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() < 116 ((std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart(); 117} 118 119unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 120 clang::reachable_code::Callback &CB) { 121 122 unsigned count = 0; 123 enqueue(Start); 124 125 while (!WorkList.empty()) { 126 const CFGBlock *Block = WorkList.pop_back_val(); 127 128 // It is possible that this block has been marked reachable after 129 // it was enqueued. 130 if (Reachable[Block->getBlockID()]) 131 continue; 132 133 // Look for any dead code within the block. 134 const Stmt *S = findDeadCode(Block); 135 136 if (!S) { 137 // No dead code. Possibly an empty block. Look at dead predecessors. 138 for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 139 E = Block->pred_end(); I != E; ++I) { 140 if (const CFGBlock *predBlock = *I) 141 enqueue(predBlock); 142 } 143 continue; 144 } 145 146 // Specially handle macro-expanded code. 147 if (S->getLocStart().isMacroID()) { 148 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 149 continue; 150 } 151 152 if (isDeadCodeRoot(Block)) { 153 reportDeadCode(S, CB); 154 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 155 } 156 else { 157 // Record this statement as the possibly best location in a 158 // strongly-connected component of dead code for emitting a 159 // warning. 160 DeferredLocs.push_back(std::make_pair(Block, S)); 161 } 162 } 163 164 // If we didn't find a dead root, then report the dead code with the 165 // earliest location. 166 if (!DeferredLocs.empty()) { 167 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 168 for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 169 E = DeferredLocs.end(); I != E; ++I) { 170 const CFGBlock *block = I->first; 171 if (Reachable[block->getBlockID()]) 172 continue; 173 reportDeadCode(I->second, CB); 174 count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 175 } 176 } 177 178 return count; 179} 180 181static SourceLocation GetUnreachableLoc(const Stmt *S, 182 SourceRange &R1, 183 SourceRange &R2) { 184 R1 = R2 = SourceRange(); 185 186 if (const Expr *Ex = dyn_cast<Expr>(S)) 187 S = Ex->IgnoreParenImpCasts(); 188 189 switch (S->getStmtClass()) { 190 case Expr::BinaryOperatorClass: { 191 const BinaryOperator *BO = cast<BinaryOperator>(S); 192 return BO->getOperatorLoc(); 193 } 194 case Expr::UnaryOperatorClass: { 195 const UnaryOperator *UO = cast<UnaryOperator>(S); 196 R1 = UO->getSubExpr()->getSourceRange(); 197 return UO->getOperatorLoc(); 198 } 199 case Expr::CompoundAssignOperatorClass: { 200 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 201 R1 = CAO->getLHS()->getSourceRange(); 202 R2 = CAO->getRHS()->getSourceRange(); 203 return CAO->getOperatorLoc(); 204 } 205 case Expr::BinaryConditionalOperatorClass: 206 case Expr::ConditionalOperatorClass: { 207 const AbstractConditionalOperator *CO = 208 cast<AbstractConditionalOperator>(S); 209 return CO->getQuestionLoc(); 210 } 211 case Expr::MemberExprClass: { 212 const MemberExpr *ME = cast<MemberExpr>(S); 213 R1 = ME->getSourceRange(); 214 return ME->getMemberLoc(); 215 } 216 case Expr::ArraySubscriptExprClass: { 217 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 218 R1 = ASE->getLHS()->getSourceRange(); 219 R2 = ASE->getRHS()->getSourceRange(); 220 return ASE->getRBracketLoc(); 221 } 222 case Expr::CStyleCastExprClass: { 223 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 224 R1 = CSC->getSubExpr()->getSourceRange(); 225 return CSC->getLParenLoc(); 226 } 227 case Expr::CXXFunctionalCastExprClass: { 228 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 229 R1 = CE->getSubExpr()->getSourceRange(); 230 return CE->getTypeBeginLoc(); 231 } 232 case Stmt::CXXTryStmtClass: { 233 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 234 } 235 case Expr::ObjCBridgedCastExprClass: { 236 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 237 R1 = CSC->getSubExpr()->getSourceRange(); 238 return CSC->getLParenLoc(); 239 } 240 default: ; 241 } 242 R1 = S->getSourceRange(); 243 return S->getLocStart(); 244} 245 246void DeadCodeScan::reportDeadCode(const Stmt *S, 247 clang::reachable_code::Callback &CB) { 248 SourceRange R1, R2; 249 SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 250 CB.HandleUnreachable(Loc, R1, R2); 251} 252 253namespace clang { namespace reachable_code { 254 255unsigned ScanReachableFromBlock(const CFGBlock *Start, 256 llvm::BitVector &Reachable) { 257 unsigned count = 0; 258 259 // Prep work queue 260 SmallVector<const CFGBlock*, 32> WL; 261 262 // The entry block may have already been marked reachable 263 // by the caller. 264 if (!Reachable[Start->getBlockID()]) { 265 ++count; 266 Reachable[Start->getBlockID()] = true; 267 } 268 269 WL.push_back(Start); 270 271 // Find the reachable blocks from 'Start'. 272 while (!WL.empty()) { 273 const CFGBlock *item = WL.pop_back_val(); 274 275 // Look at the successors and mark then reachable. 276 for (CFGBlock::const_succ_iterator I = item->succ_begin(), 277 E = item->succ_end(); I != E; ++I) 278 if (const CFGBlock *B = *I) { 279 unsigned blockID = B->getBlockID(); 280 if (!Reachable[blockID]) { 281 Reachable.set(blockID); 282 WL.push_back(B); 283 ++count; 284 } 285 } 286 } 287 return count; 288} 289 290void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { 291 CFG *cfg = AC.getCFG(); 292 if (!cfg) 293 return; 294 295 // Scan for reachable blocks from the entrance of the CFG. 296 // If there are no unreachable blocks, we're done. 297 llvm::BitVector reachable(cfg->getNumBlockIDs()); 298 unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 299 if (numReachable == cfg->getNumBlockIDs()) 300 return; 301 302 // If there aren't explicit EH edges, we should include the 'try' dispatch 303 // blocks as roots. 304 if (!AC.getCFGBuildOptions().AddEHEdges) { 305 for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 306 E = cfg->try_blocks_end() ; I != E; ++I) { 307 numReachable += ScanReachableFromBlock(*I, reachable); 308 } 309 if (numReachable == cfg->getNumBlockIDs()) 310 return; 311 } 312 313 // There are some unreachable blocks. We need to find the root blocks that 314 // contain code that should be considered unreachable. 315 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 316 const CFGBlock *block = *I; 317 // A block may have been marked reachable during this loop. 318 if (reachable[block->getBlockID()]) 319 continue; 320 321 DeadCodeScan DS(reachable); 322 numReachable += DS.scanBackwards(block, CB); 323 324 if (numReachable == cfg->getNumBlockIDs()) 325 return; 326 } 327} 328 329}} // end namespace clang::reachable_code 330