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 26 using namespace clang; 27 28 namespace { 29 class 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 39 public: 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 57 void 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 65 bool 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 88 static 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 96 const 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 113 static 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 119 unsigned 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 181 static 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 246 void 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 253 namespace clang { namespace reachable_code { 254 255 unsigned 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 290 void FindUnreachableCode(AnalysisContext &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