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 "clang/Analysis/Analyses/ReachableCode.h" 16#include "clang/AST/Expr.h" 17#include "clang/AST/ExprCXX.h" 18#include "clang/AST/ExprObjC.h" 19#include "clang/AST/StmtCXX.h" 20#include "clang/Analysis/AnalysisContext.h" 21#include "clang/Analysis/CFG.h" 22#include "clang/Basic/SourceManager.h" 23#include "llvm/ADT/BitVector.h" 24#include "llvm/ADT/SmallVector.h" 25 26using namespace clang; 27 28namespace { 29class DeadCodeScan { 30 llvm::BitVector Visited; 31 llvm::BitVector &Reachable; 32 SmallVector<const CFGBlock *, 10> WorkList; 33 34 typedef 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 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 (Optional<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 std::pair<const CFGBlock *, const Stmt *> *p1, 114 const std::pair<const CFGBlock *, const Stmt *> *p2) { 115 if (p1->second->getLocStart() < p2->second->getLocStart()) 116 return -1; 117 if (p2->second->getLocStart() < p1->second->getLocStart()) 118 return 1; 119 return 0; 120} 121 122unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 123 clang::reachable_code::Callback &CB) { 124 125 unsigned count = 0; 126 enqueue(Start); 127 128 while (!WorkList.empty()) { 129 const CFGBlock *Block = WorkList.pop_back_val(); 130 131 // It is possible that this block has been marked reachable after 132 // it was enqueued. 133 if (Reachable[Block->getBlockID()]) 134 continue; 135 136 // Look for any dead code within the block. 137 const Stmt *S = findDeadCode(Block); 138 139 if (!S) { 140 // No dead code. Possibly an empty block. Look at dead predecessors. 141 for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 142 E = Block->pred_end(); I != E; ++I) { 143 if (const CFGBlock *predBlock = *I) 144 enqueue(predBlock); 145 } 146 continue; 147 } 148 149 // Specially handle macro-expanded code. 150 if (S->getLocStart().isMacroID()) { 151 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 152 continue; 153 } 154 155 if (isDeadCodeRoot(Block)) { 156 reportDeadCode(S, CB); 157 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 158 } 159 else { 160 // Record this statement as the possibly best location in a 161 // strongly-connected component of dead code for emitting a 162 // warning. 163 DeferredLocs.push_back(std::make_pair(Block, S)); 164 } 165 } 166 167 // If we didn't find a dead root, then report the dead code with the 168 // earliest location. 169 if (!DeferredLocs.empty()) { 170 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 171 for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 172 E = DeferredLocs.end(); I != E; ++I) { 173 const CFGBlock *block = I->first; 174 if (Reachable[block->getBlockID()]) 175 continue; 176 reportDeadCode(I->second, CB); 177 count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 178 } 179 } 180 181 return count; 182} 183 184static SourceLocation GetUnreachableLoc(const Stmt *S, 185 SourceRange &R1, 186 SourceRange &R2) { 187 R1 = R2 = SourceRange(); 188 189 if (const Expr *Ex = dyn_cast<Expr>(S)) 190 S = Ex->IgnoreParenImpCasts(); 191 192 switch (S->getStmtClass()) { 193 case Expr::BinaryOperatorClass: { 194 const BinaryOperator *BO = cast<BinaryOperator>(S); 195 return BO->getOperatorLoc(); 196 } 197 case Expr::UnaryOperatorClass: { 198 const UnaryOperator *UO = cast<UnaryOperator>(S); 199 R1 = UO->getSubExpr()->getSourceRange(); 200 return UO->getOperatorLoc(); 201 } 202 case Expr::CompoundAssignOperatorClass: { 203 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 204 R1 = CAO->getLHS()->getSourceRange(); 205 R2 = CAO->getRHS()->getSourceRange(); 206 return CAO->getOperatorLoc(); 207 } 208 case Expr::BinaryConditionalOperatorClass: 209 case Expr::ConditionalOperatorClass: { 210 const AbstractConditionalOperator *CO = 211 cast<AbstractConditionalOperator>(S); 212 return CO->getQuestionLoc(); 213 } 214 case Expr::MemberExprClass: { 215 const MemberExpr *ME = cast<MemberExpr>(S); 216 R1 = ME->getSourceRange(); 217 return ME->getMemberLoc(); 218 } 219 case Expr::ArraySubscriptExprClass: { 220 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 221 R1 = ASE->getLHS()->getSourceRange(); 222 R2 = ASE->getRHS()->getSourceRange(); 223 return ASE->getRBracketLoc(); 224 } 225 case Expr::CStyleCastExprClass: { 226 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 227 R1 = CSC->getSubExpr()->getSourceRange(); 228 return CSC->getLParenLoc(); 229 } 230 case Expr::CXXFunctionalCastExprClass: { 231 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 232 R1 = CE->getSubExpr()->getSourceRange(); 233 return CE->getLocStart(); 234 } 235 case Stmt::CXXTryStmtClass: { 236 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 237 } 238 case Expr::ObjCBridgedCastExprClass: { 239 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 240 R1 = CSC->getSubExpr()->getSourceRange(); 241 return CSC->getLParenLoc(); 242 } 243 default: ; 244 } 245 R1 = S->getSourceRange(); 246 return S->getLocStart(); 247} 248 249void DeadCodeScan::reportDeadCode(const Stmt *S, 250 clang::reachable_code::Callback &CB) { 251 SourceRange R1, R2; 252 SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 253 CB.HandleUnreachable(Loc, R1, R2); 254} 255 256namespace clang { namespace reachable_code { 257 258void Callback::anchor() { } 259 260unsigned ScanReachableFromBlock(const CFGBlock *Start, 261 llvm::BitVector &Reachable) { 262 unsigned count = 0; 263 264 // Prep work queue 265 SmallVector<const CFGBlock*, 32> WL; 266 267 // The entry block may have already been marked reachable 268 // by the caller. 269 if (!Reachable[Start->getBlockID()]) { 270 ++count; 271 Reachable[Start->getBlockID()] = true; 272 } 273 274 WL.push_back(Start); 275 276 // Find the reachable blocks from 'Start'. 277 while (!WL.empty()) { 278 const CFGBlock *item = WL.pop_back_val(); 279 280 // Look at the successors and mark then reachable. 281 for (CFGBlock::const_succ_iterator I = item->succ_begin(), 282 E = item->succ_end(); I != E; ++I) 283 if (const CFGBlock *B = *I) { 284 unsigned blockID = B->getBlockID(); 285 if (!Reachable[blockID]) { 286 Reachable.set(blockID); 287 WL.push_back(B); 288 ++count; 289 } 290 } 291 } 292 return count; 293} 294 295void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { 296 CFG *cfg = AC.getCFG(); 297 if (!cfg) 298 return; 299 300 // Scan for reachable blocks from the entrance of the CFG. 301 // If there are no unreachable blocks, we're done. 302 llvm::BitVector reachable(cfg->getNumBlockIDs()); 303 unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 304 if (numReachable == cfg->getNumBlockIDs()) 305 return; 306 307 // If there aren't explicit EH edges, we should include the 'try' dispatch 308 // blocks as roots. 309 if (!AC.getCFGBuildOptions().AddEHEdges) { 310 for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 311 E = cfg->try_blocks_end() ; I != E; ++I) { 312 numReachable += ScanReachableFromBlock(*I, reachable); 313 } 314 if (numReachable == cfg->getNumBlockIDs()) 315 return; 316 } 317 318 // There are some unreachable blocks. We need to find the root blocks that 319 // contain code that should be considered unreachable. 320 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 321 const CFGBlock *block = *I; 322 // A block may have been marked reachable during this loop. 323 if (reachable[block->getBlockID()]) 324 continue; 325 326 DeadCodeScan DS(reachable); 327 numReachable += DS.scanBackwards(block, CB); 328 329 if (numReachable == cfg->getNumBlockIDs()) 330 return; 331 } 332} 333 334}} // end namespace clang::reachable_code 335