1204643Srdivacky//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// 2204643Srdivacky// 3204643Srdivacky// The LLVM Compiler Infrastructure 4204643Srdivacky// 5204643Srdivacky// This file is distributed under the University of Illinois Open Source 6204643Srdivacky// License. See LICENSE.TXT for details. 7204643Srdivacky// 8204643Srdivacky//===----------------------------------------------------------------------===// 9204643Srdivacky// 10204643Srdivacky// This file implements a flow-sensitive, path-insensitive analysis of 11204643Srdivacky// determining reachable blocks within a CFG. 12204643Srdivacky// 13204643Srdivacky//===----------------------------------------------------------------------===// 14204643Srdivacky 15252723Sdim#include "clang/Analysis/Analyses/ReachableCode.h" 16204643Srdivacky#include "clang/AST/Expr.h" 17204643Srdivacky#include "clang/AST/ExprCXX.h" 18224145Sdim#include "clang/AST/ExprObjC.h" 19204643Srdivacky#include "clang/AST/StmtCXX.h" 20252723Sdim#include "clang/Analysis/AnalysisContext.h" 21204643Srdivacky#include "clang/Analysis/CFG.h" 22204643Srdivacky#include "clang/Basic/SourceManager.h" 23252723Sdim#include "llvm/ADT/BitVector.h" 24252723Sdim#include "llvm/ADT/SmallVector.h" 25204643Srdivacky 26204643Srdivackyusing namespace clang; 27204643Srdivacky 28226890Sdimnamespace { 29226890Sdimclass DeadCodeScan { 30226890Sdim llvm::BitVector Visited; 31226890Sdim llvm::BitVector &Reachable; 32252723Sdim SmallVector<const CFGBlock *, 10> WorkList; 33226890Sdim 34252723Sdim typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12> 35226890Sdim DeferredLocsTy; 36226890Sdim 37226890Sdim DeferredLocsTy DeferredLocs; 38226890Sdim 39226890Sdimpublic: 40226890Sdim DeadCodeScan(llvm::BitVector &reachable) 41226890Sdim : Visited(reachable.size()), 42226890Sdim Reachable(reachable) {} 43226890Sdim 44226890Sdim void enqueue(const CFGBlock *block); 45226890Sdim unsigned scanBackwards(const CFGBlock *Start, 46226890Sdim clang::reachable_code::Callback &CB); 47226890Sdim 48226890Sdim bool isDeadCodeRoot(const CFGBlock *Block); 49226890Sdim 50226890Sdim const Stmt *findDeadCode(const CFGBlock *Block); 51226890Sdim 52226890Sdim void reportDeadCode(const Stmt *S, 53226890Sdim clang::reachable_code::Callback &CB); 54226890Sdim}; 55226890Sdim} 56226890Sdim 57226890Sdimvoid DeadCodeScan::enqueue(const CFGBlock *block) { 58226890Sdim unsigned blockID = block->getBlockID(); 59226890Sdim if (Reachable[blockID] || Visited[blockID]) 60226890Sdim return; 61226890Sdim Visited[blockID] = true; 62226890Sdim WorkList.push_back(block); 63226890Sdim} 64226890Sdim 65226890Sdimbool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { 66226890Sdim bool isDeadRoot = true; 67226890Sdim 68226890Sdim for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 69226890Sdim E = Block->pred_end(); I != E; ++I) { 70226890Sdim if (const CFGBlock *PredBlock = *I) { 71226890Sdim unsigned blockID = PredBlock->getBlockID(); 72226890Sdim if (Visited[blockID]) { 73226890Sdim isDeadRoot = false; 74226890Sdim continue; 75226890Sdim } 76226890Sdim if (!Reachable[blockID]) { 77226890Sdim isDeadRoot = false; 78226890Sdim Visited[blockID] = true; 79226890Sdim WorkList.push_back(PredBlock); 80226890Sdim continue; 81226890Sdim } 82226890Sdim } 83226890Sdim } 84226890Sdim 85226890Sdim return isDeadRoot; 86226890Sdim} 87226890Sdim 88226890Sdimstatic bool isValidDeadStmt(const Stmt *S) { 89226890Sdim if (S->getLocStart().isInvalid()) 90226890Sdim return false; 91226890Sdim if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) 92226890Sdim return BO->getOpcode() != BO_Comma; 93226890Sdim return true; 94226890Sdim} 95226890Sdim 96226890Sdimconst Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 97226890Sdim for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I) 98252723Sdim if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) { 99226890Sdim const Stmt *S = CS->getStmt(); 100226890Sdim if (isValidDeadStmt(S)) 101226890Sdim return S; 102226890Sdim } 103226890Sdim 104226890Sdim if (CFGTerminator T = Block->getTerminator()) { 105226890Sdim const Stmt *S = T.getStmt(); 106226890Sdim if (isValidDeadStmt(S)) 107226890Sdim return S; 108226890Sdim } 109226890Sdim 110226890Sdim return 0; 111226890Sdim} 112226890Sdim 113263509Sdimstatic int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1, 114263509Sdim const std::pair<const CFGBlock *, const Stmt *> *p2) { 115263509Sdim if (p1->second->getLocStart() < p2->second->getLocStart()) 116263509Sdim return -1; 117263509Sdim if (p2->second->getLocStart() < p1->second->getLocStart()) 118263509Sdim return 1; 119263509Sdim return 0; 120226890Sdim} 121226890Sdim 122226890Sdimunsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 123226890Sdim clang::reachable_code::Callback &CB) { 124226890Sdim 125226890Sdim unsigned count = 0; 126226890Sdim enqueue(Start); 127226890Sdim 128226890Sdim while (!WorkList.empty()) { 129226890Sdim const CFGBlock *Block = WorkList.pop_back_val(); 130226890Sdim 131226890Sdim // It is possible that this block has been marked reachable after 132226890Sdim // it was enqueued. 133226890Sdim if (Reachable[Block->getBlockID()]) 134226890Sdim continue; 135226890Sdim 136226890Sdim // Look for any dead code within the block. 137226890Sdim const Stmt *S = findDeadCode(Block); 138226890Sdim 139226890Sdim if (!S) { 140226890Sdim // No dead code. Possibly an empty block. Look at dead predecessors. 141226890Sdim for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 142226890Sdim E = Block->pred_end(); I != E; ++I) { 143226890Sdim if (const CFGBlock *predBlock = *I) 144226890Sdim enqueue(predBlock); 145226890Sdim } 146226890Sdim continue; 147226890Sdim } 148226890Sdim 149226890Sdim // Specially handle macro-expanded code. 150226890Sdim if (S->getLocStart().isMacroID()) { 151226890Sdim count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 152226890Sdim continue; 153226890Sdim } 154226890Sdim 155226890Sdim if (isDeadCodeRoot(Block)) { 156226890Sdim reportDeadCode(S, CB); 157226890Sdim count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 158226890Sdim } 159226890Sdim else { 160226890Sdim // Record this statement as the possibly best location in a 161226890Sdim // strongly-connected component of dead code for emitting a 162226890Sdim // warning. 163226890Sdim DeferredLocs.push_back(std::make_pair(Block, S)); 164226890Sdim } 165226890Sdim } 166226890Sdim 167226890Sdim // If we didn't find a dead root, then report the dead code with the 168226890Sdim // earliest location. 169226890Sdim if (!DeferredLocs.empty()) { 170226890Sdim llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 171226890Sdim for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 172226890Sdim E = DeferredLocs.end(); I != E; ++I) { 173226890Sdim const CFGBlock *block = I->first; 174226890Sdim if (Reachable[block->getBlockID()]) 175226890Sdim continue; 176226890Sdim reportDeadCode(I->second, CB); 177226890Sdim count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 178226890Sdim } 179226890Sdim } 180226890Sdim 181226890Sdim return count; 182226890Sdim} 183226890Sdim 184226890Sdimstatic SourceLocation GetUnreachableLoc(const Stmt *S, 185226890Sdim SourceRange &R1, 186204643Srdivacky SourceRange &R2) { 187204643Srdivacky R1 = R2 = SourceRange(); 188204643Srdivacky 189218893Sdim if (const Expr *Ex = dyn_cast<Expr>(S)) 190218893Sdim S = Ex->IgnoreParenImpCasts(); 191218893Sdim 192204643Srdivacky switch (S->getStmtClass()) { 193204643Srdivacky case Expr::BinaryOperatorClass: { 194204643Srdivacky const BinaryOperator *BO = cast<BinaryOperator>(S); 195204643Srdivacky return BO->getOperatorLoc(); 196204643Srdivacky } 197204643Srdivacky case Expr::UnaryOperatorClass: { 198204643Srdivacky const UnaryOperator *UO = cast<UnaryOperator>(S); 199204643Srdivacky R1 = UO->getSubExpr()->getSourceRange(); 200204643Srdivacky return UO->getOperatorLoc(); 201204643Srdivacky } 202204643Srdivacky case Expr::CompoundAssignOperatorClass: { 203204643Srdivacky const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 204204643Srdivacky R1 = CAO->getLHS()->getSourceRange(); 205204643Srdivacky R2 = CAO->getRHS()->getSourceRange(); 206204643Srdivacky return CAO->getOperatorLoc(); 207204643Srdivacky } 208218893Sdim case Expr::BinaryConditionalOperatorClass: 209204643Srdivacky case Expr::ConditionalOperatorClass: { 210218893Sdim const AbstractConditionalOperator *CO = 211218893Sdim cast<AbstractConditionalOperator>(S); 212204643Srdivacky return CO->getQuestionLoc(); 213204643Srdivacky } 214204643Srdivacky case Expr::MemberExprClass: { 215204643Srdivacky const MemberExpr *ME = cast<MemberExpr>(S); 216204643Srdivacky R1 = ME->getSourceRange(); 217204643Srdivacky return ME->getMemberLoc(); 218204643Srdivacky } 219204643Srdivacky case Expr::ArraySubscriptExprClass: { 220204643Srdivacky const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 221204643Srdivacky R1 = ASE->getLHS()->getSourceRange(); 222204643Srdivacky R2 = ASE->getRHS()->getSourceRange(); 223204643Srdivacky return ASE->getRBracketLoc(); 224204643Srdivacky } 225204643Srdivacky case Expr::CStyleCastExprClass: { 226204643Srdivacky const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 227204643Srdivacky R1 = CSC->getSubExpr()->getSourceRange(); 228204643Srdivacky return CSC->getLParenLoc(); 229204643Srdivacky } 230204643Srdivacky case Expr::CXXFunctionalCastExprClass: { 231204643Srdivacky const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 232204643Srdivacky R1 = CE->getSubExpr()->getSourceRange(); 233263509Sdim return CE->getLocStart(); 234204643Srdivacky } 235204643Srdivacky case Stmt::CXXTryStmtClass: { 236204643Srdivacky return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 237204643Srdivacky } 238224145Sdim case Expr::ObjCBridgedCastExprClass: { 239224145Sdim const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 240224145Sdim R1 = CSC->getSubExpr()->getSourceRange(); 241224145Sdim return CSC->getLParenLoc(); 242224145Sdim } 243204643Srdivacky default: ; 244204643Srdivacky } 245204643Srdivacky R1 = S->getSourceRange(); 246204643Srdivacky return S->getLocStart(); 247204643Srdivacky} 248204643Srdivacky 249226890Sdimvoid DeadCodeScan::reportDeadCode(const Stmt *S, 250226890Sdim clang::reachable_code::Callback &CB) { 251204643Srdivacky SourceRange R1, R2; 252226890Sdim SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 253226890Sdim CB.HandleUnreachable(Loc, R1, R2); 254204643Srdivacky} 255204643Srdivacky 256204643Srdivackynamespace clang { namespace reachable_code { 257235633Sdim 258235633Sdimvoid Callback::anchor() { } 259235633Sdim 260226890Sdimunsigned ScanReachableFromBlock(const CFGBlock *Start, 261204643Srdivacky llvm::BitVector &Reachable) { 262204643Srdivacky unsigned count = 0; 263226890Sdim 264221345Sdim // Prep work queue 265226890Sdim SmallVector<const CFGBlock*, 32> WL; 266226890Sdim 267226890Sdim // The entry block may have already been marked reachable 268226890Sdim // by the caller. 269226890Sdim if (!Reachable[Start->getBlockID()]) { 270226890Sdim ++count; 271226890Sdim Reachable[Start->getBlockID()] = true; 272226890Sdim } 273226890Sdim 274226890Sdim WL.push_back(Start); 275226890Sdim 276218893Sdim // Find the reachable blocks from 'Start'. 277204643Srdivacky while (!WL.empty()) { 278226890Sdim const CFGBlock *item = WL.pop_back_val(); 279226890Sdim 280226890Sdim // Look at the successors and mark then reachable. 281226890Sdim for (CFGBlock::const_succ_iterator I = item->succ_begin(), 282226890Sdim E = item->succ_end(); I != E; ++I) 283204643Srdivacky if (const CFGBlock *B = *I) { 284204643Srdivacky unsigned blockID = B->getBlockID(); 285204643Srdivacky if (!Reachable[blockID]) { 286204643Srdivacky Reachable.set(blockID); 287226890Sdim WL.push_back(B); 288204643Srdivacky ++count; 289204643Srdivacky } 290204643Srdivacky } 291204643Srdivacky } 292204643Srdivacky return count; 293204643Srdivacky} 294226890Sdim 295235633Sdimvoid FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { 296204643Srdivacky CFG *cfg = AC.getCFG(); 297204643Srdivacky if (!cfg) 298204643Srdivacky return; 299204643Srdivacky 300226890Sdim // Scan for reachable blocks from the entrance of the CFG. 301226890Sdim // If there are no unreachable blocks, we're done. 302204643Srdivacky llvm::BitVector reachable(cfg->getNumBlockIDs()); 303226890Sdim unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 304204643Srdivacky if (numReachable == cfg->getNumBlockIDs()) 305204643Srdivacky return; 306226890Sdim 307226890Sdim // If there aren't explicit EH edges, we should include the 'try' dispatch 308226890Sdim // blocks as roots. 309226890Sdim if (!AC.getCFGBuildOptions().AddEHEdges) { 310226890Sdim for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 311226890Sdim E = cfg->try_blocks_end() ; I != E; ++I) { 312226890Sdim numReachable += ScanReachableFromBlock(*I, reachable); 313204643Srdivacky } 314226890Sdim if (numReachable == cfg->getNumBlockIDs()) 315226890Sdim return; 316204643Srdivacky } 317204643Srdivacky 318226890Sdim // There are some unreachable blocks. We need to find the root blocks that 319226890Sdim // contain code that should be considered unreachable. 320226890Sdim for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 321226890Sdim const CFGBlock *block = *I; 322226890Sdim // A block may have been marked reachable during this loop. 323226890Sdim if (reachable[block->getBlockID()]) 324226890Sdim continue; 325226890Sdim 326226890Sdim DeadCodeScan DS(reachable); 327226890Sdim numReachable += DS.scanBackwards(block, CB); 328226890Sdim 329226890Sdim if (numReachable == cfg->getNumBlockIDs()) 330226890Sdim return; 331204643Srdivacky } 332204643Srdivacky} 333204643Srdivacky 334204643Srdivacky}} // end namespace clang::reachable_code 335