ReachableCode.cpp revision 0f3b4ca1764cd6d457f511d340fba504f41763c3
1//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a flow-sensitive, path-insensitive analysis of 11// determining reachable blocks within a CFG. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/BitVector.h" 16#include "llvm/ADT/SmallVector.h" 17#include "clang/AST/Expr.h" 18#include "clang/AST/ExprCXX.h" 19#include "clang/AST/ExprObjC.h" 20#include "clang/AST/StmtCXX.h" 21#include "clang/Analysis/Analyses/ReachableCode.h" 22#include "clang/Analysis/CFG.h" 23#include "clang/Analysis/AnalysisContext.h" 24#include "clang/Basic/SourceManager.h" 25 26using namespace clang; 27 28namespace { 29class DeadCodeScan { 30 llvm::BitVector Visited; 31 llvm::BitVector &Reachable; 32 llvm::SmallVector<const CFGBlock *, 10> WorkList; 33 34 typedef llvm::SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12> 35 DeferredLocsTy; 36 37 DeferredLocsTy DeferredLocs; 38 39public: 40 DeadCodeScan(llvm::BitVector &reachable) 41 : Visited(reachable.size()), 42 Reachable(reachable) {} 43 44 void enqueue(const CFGBlock *block); 45 unsigned scanBackwards(const CFGBlock *Start, 46 clang::reachable_code::Callback &CB); 47 48 bool isDeadCodeRoot(const CFGBlock *Block); 49 50 const Stmt *findDeadCode(const CFGBlock *Block); 51 52 void reportDeadCode(const Stmt *S, 53 clang::reachable_code::Callback &CB); 54}; 55} 56 57void DeadCodeScan::enqueue(const CFGBlock *block) { 58 unsigned blockID = block->getBlockID(); 59 if (Reachable[blockID] || Visited[blockID]) 60 return; 61 Visited[blockID] = true; 62 WorkList.push_back(block); 63} 64 65bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { 66 bool isDeadRoot = true; 67 68 for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 69 E = Block->pred_end(); I != E; ++I) { 70 if (const CFGBlock *PredBlock = *I) { 71 unsigned blockID = PredBlock->getBlockID(); 72 if (Visited[blockID]) { 73 isDeadRoot = false; 74 continue; 75 } 76 if (!Reachable[blockID]) { 77 isDeadRoot = false; 78 Visited[blockID] = true; 79 WorkList.push_back(PredBlock); 80 continue; 81 } 82 } 83 } 84 85 return isDeadRoot; 86} 87 88static bool isValidDeadStmt(const Stmt *S) { 89 SourceLocation Loc = S->getLocStart(); 90 if (!(Loc.isValid() && !Loc.isMacroID())) 91 return false; 92 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) { 93 return BO->getOpcode() != BO_Comma; 94 } 95 return true; 96} 97 98const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 99 for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I) 100 if (const CFGStmt *CS = I->getAs<CFGStmt>()) { 101 const Stmt *S = CS->getStmt(); 102 if (isValidDeadStmt(S)) 103 return S; 104 } 105 106 if (CFGTerminator T = Block->getTerminator()) { 107 const Stmt *S = T.getStmt(); 108 if (isValidDeadStmt(S)) 109 return S; 110 } 111 112 return 0; 113} 114 115static int SrcCmp(const void *p1, const void *p2) { 116 return 117 ((std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() < 118 ((std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart(); 119} 120 121unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 122 clang::reachable_code::Callback &CB) { 123 124 unsigned count = 0; 125 enqueue(Start); 126 127 while (!WorkList.empty()) { 128 const CFGBlock *Block = WorkList.pop_back_val(); 129 130 // It is possible that this block has been marked reachable after 131 // it was enqueued. 132 if (Reachable[Block->getBlockID()]) 133 continue; 134 135 // Look for any dead code within the block. 136 const Stmt *S = findDeadCode(Block); 137 138 if (!S) { 139 // No dead code. Possibly an empty block. Look at dead predecessors. 140 for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 141 E = Block->pred_end(); I != E; ++I) { 142 if (const CFGBlock *predBlock = *I) 143 enqueue(predBlock); 144 } 145 continue; 146 } 147 148 if (isDeadCodeRoot(Block)) { 149 reportDeadCode(S, CB); 150 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 151 } 152 else { 153 // Record this statement as the possibly best location in a 154 // strongly-connected component of dead code for emitting a 155 // warning. 156 DeferredLocs.push_back(std::make_pair(Block, S)); 157 } 158 } 159 160 // If we didn't find a dead root, then report the dead code with the 161 // earliest location. 162 if (!DeferredLocs.empty()) { 163 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 164 for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 165 E = DeferredLocs.end(); I != E; ++I) { 166 const CFGBlock *block = I->first; 167 if (Reachable[block->getBlockID()]) 168 continue; 169 reportDeadCode(I->second, CB); 170 count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 171 } 172 } 173 174 return count; 175} 176 177static SourceLocation GetUnreachableLoc(const Stmt *S, 178 SourceRange &R1, 179 SourceRange &R2) { 180 R1 = R2 = SourceRange(); 181 182 if (const Expr *Ex = dyn_cast<Expr>(S)) 183 S = Ex->IgnoreParenImpCasts(); 184 185 switch (S->getStmtClass()) { 186 case Expr::BinaryOperatorClass: { 187 const BinaryOperator *BO = cast<BinaryOperator>(S); 188 return BO->getOperatorLoc(); 189 } 190 case Expr::UnaryOperatorClass: { 191 const UnaryOperator *UO = cast<UnaryOperator>(S); 192 R1 = UO->getSubExpr()->getSourceRange(); 193 return UO->getOperatorLoc(); 194 } 195 case Expr::CompoundAssignOperatorClass: { 196 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 197 R1 = CAO->getLHS()->getSourceRange(); 198 R2 = CAO->getRHS()->getSourceRange(); 199 return CAO->getOperatorLoc(); 200 } 201 case Expr::BinaryConditionalOperatorClass: 202 case Expr::ConditionalOperatorClass: { 203 const AbstractConditionalOperator *CO = 204 cast<AbstractConditionalOperator>(S); 205 return CO->getQuestionLoc(); 206 } 207 case Expr::MemberExprClass: { 208 const MemberExpr *ME = cast<MemberExpr>(S); 209 R1 = ME->getSourceRange(); 210 return ME->getMemberLoc(); 211 } 212 case Expr::ArraySubscriptExprClass: { 213 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 214 R1 = ASE->getLHS()->getSourceRange(); 215 R2 = ASE->getRHS()->getSourceRange(); 216 return ASE->getRBracketLoc(); 217 } 218 case Expr::CStyleCastExprClass: { 219 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 220 R1 = CSC->getSubExpr()->getSourceRange(); 221 return CSC->getLParenLoc(); 222 } 223 case Expr::CXXFunctionalCastExprClass: { 224 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 225 R1 = CE->getSubExpr()->getSourceRange(); 226 return CE->getTypeBeginLoc(); 227 } 228 case Stmt::CXXTryStmtClass: { 229 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 230 } 231 case Expr::ObjCBridgedCastExprClass: { 232 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 233 R1 = CSC->getSubExpr()->getSourceRange(); 234 return CSC->getLParenLoc(); 235 } 236 default: ; 237 } 238 R1 = S->getSourceRange(); 239 return S->getLocStart(); 240} 241 242void DeadCodeScan::reportDeadCode(const Stmt *S, 243 clang::reachable_code::Callback &CB) { 244 SourceRange R1, R2; 245 SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 246 CB.HandleUnreachable(Loc, R1, R2); 247} 248 249namespace clang { namespace reachable_code { 250 251unsigned ScanReachableFromBlock(const CFGBlock *Start, 252 llvm::BitVector &Reachable) { 253 unsigned count = 0; 254 255 // Prep work queue 256 SmallVector<const CFGBlock*, 32> WL; 257 258 // The entry block may have already been marked reachable 259 // by the caller. 260 if (!Reachable[Start->getBlockID()]) { 261 ++count; 262 Reachable[Start->getBlockID()] = true; 263 } 264 265 WL.push_back(Start); 266 267 // Find the reachable blocks from 'Start'. 268 while (!WL.empty()) { 269 const CFGBlock *item = WL.pop_back_val(); 270 271 // Look at the successors and mark then reachable. 272 for (CFGBlock::const_succ_iterator I = item->succ_begin(), 273 E = item->succ_end(); I != E; ++I) 274 if (const CFGBlock *B = *I) { 275 unsigned blockID = B->getBlockID(); 276 if (!Reachable[blockID]) { 277 Reachable.set(blockID); 278 WL.push_back(B); 279 ++count; 280 } 281 } 282 } 283 return count; 284} 285 286void FindUnreachableCode(AnalysisContext &AC, Callback &CB) { 287 CFG *cfg = AC.getCFG(); 288 if (!cfg) 289 return; 290 291 // Scan for reachable blocks from the entrance of the CFG. 292 // If there are no unreachable blocks, we're done. 293 llvm::BitVector reachable(cfg->getNumBlockIDs()); 294 unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 295 if (numReachable == cfg->getNumBlockIDs()) 296 return; 297 298 // If there aren't explicit EH edges, we should include the 'try' dispatch 299 // blocks as roots. 300 if (!AC.getCFGBuildOptions().AddEHEdges) { 301 for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 302 E = cfg->try_blocks_end() ; I != E; ++I) { 303 numReachable += ScanReachableFromBlock(*I, reachable); 304 } 305 if (numReachable == cfg->getNumBlockIDs()) 306 return; 307 } 308 309 // There are some unreachable blocks. We need to find the root blocks that 310 // contain code that should be considered unreachable. 311 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 312 const CFGBlock *block = *I; 313 // A block may have been marked reachable during this loop. 314 if (reachable[block->getBlockID()]) 315 continue; 316 317 DeadCodeScan DS(reachable); 318 numReachable += DS.scanBackwards(block, CB); 319 320 if (numReachable == cfg->getNumBlockIDs()) 321 return; 322 } 323} 324 325}} // end namespace clang::reachable_code 326