ReachableCode.cpp revision 0f3b4ca1764cd6d457f511d340fba504f41763c3
13d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// 23d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// 33d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// The LLVM Compiler Infrastructure 43d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// 53d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// This file is distributed under the University of Illinois Open Source 63d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// License. See LICENSE.TXT for details. 73d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// 83d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek//===----------------------------------------------------------------------===// 93d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// 103d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// This file implements a flow-sensitive, path-insensitive analysis of 113d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// determining reachable blocks within a CFG. 123d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek// 133d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek//===----------------------------------------------------------------------===// 143d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek 153d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek#include "llvm/ADT/BitVector.h" 163d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek#include "llvm/ADT/SmallVector.h" 1772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/Expr.h" 1872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/ExprCXX.h" 19f85e193739c953358c865005855253af4f68a497John McCall#include "clang/AST/ExprObjC.h" 2072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/StmtCXX.h" 213d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek#include "clang/Analysis/Analyses/ReachableCode.h" 223d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek#include "clang/Analysis/CFG.h" 2372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/Analysis/AnalysisContext.h" 2472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/Basic/SourceManager.h" 253d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek 263d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenekusing namespace clang; 273d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek 280f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremeneknamespace { 290f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekclass DeadCodeScan { 300f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::BitVector Visited; 310f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::BitVector &Reachable; 320f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::SmallVector<const CFGBlock *, 10> WorkList; 330f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 340f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek typedef llvm::SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12> 350f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeferredLocsTy; 360f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 370f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeferredLocsTy DeferredLocs; 380f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 390f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekpublic: 400f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeadCodeScan(llvm::BitVector &reachable) 410f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek : Visited(reachable.size()), 420f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek Reachable(reachable) {} 430f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 440f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek void enqueue(const CFGBlock *block); 450f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned scanBackwards(const CFGBlock *Start, 460f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB); 470f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 480f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek bool isDeadCodeRoot(const CFGBlock *Block); 490f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 500f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *findDeadCode(const CFGBlock *Block); 510f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 520f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek void reportDeadCode(const Stmt *S, 530f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB); 540f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek}; 550f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 560f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 570f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekvoid DeadCodeScan::enqueue(const CFGBlock *block) { 580f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned blockID = block->getBlockID(); 590f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Reachable[blockID] || Visited[blockID]) 600f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return; 610f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek Visited[blockID] = true; 620f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek WorkList.push_back(block); 630f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 640f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 650f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekbool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) { 660f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek bool isDeadRoot = true; 670f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 680f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 690f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = Block->pred_end(); I != E; ++I) { 700f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (const CFGBlock *PredBlock = *I) { 710f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned blockID = PredBlock->getBlockID(); 720f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Visited[blockID]) { 730f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek isDeadRoot = false; 740f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 750f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 760f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!Reachable[blockID]) { 770f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek isDeadRoot = false; 780f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek Visited[blockID] = true; 790f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek WorkList.push_back(PredBlock); 800f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 810f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 820f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 830f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 840f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 850f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return isDeadRoot; 860f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 870f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 880f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekstatic bool isValidDeadStmt(const Stmt *S) { 890f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceLocation Loc = S->getLocStart(); 900f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!(Loc.isValid() && !Loc.isMacroID())) 910f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return false; 920f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) { 930f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return BO->getOpcode() != BO_Comma; 940f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 950f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return true; 960f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 970f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 980f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekconst Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 990f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I) 1000f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (const CFGStmt *CS = I->getAs<CFGStmt>()) { 1010f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *S = CS->getStmt(); 1020f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isValidDeadStmt(S)) 1030f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return S; 1040f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1050f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1060f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (CFGTerminator T = Block->getTerminator()) { 1070f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *S = T.getStmt(); 1080f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isValidDeadStmt(S)) 1090f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return S; 1100f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1110f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1120f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return 0; 1130f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1140f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1150f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekstatic int SrcCmp(const void *p1, const void *p2) { 1160f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return 1170f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ((std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() < 1180f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ((std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart(); 1190f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1200f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1210f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekunsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 1220f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB) { 12372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 1240f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned count = 0; 1250f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek enqueue(Start); 1260f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1270f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek while (!WorkList.empty()) { 1280f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *Block = WorkList.pop_back_val(); 1290f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1300f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // It is possible that this block has been marked reachable after 1310f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // it was enqueued. 1320f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Reachable[Block->getBlockID()]) 1330f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1340f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1350f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Look for any dead code within the block. 1360f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *S = findDeadCode(Block); 1370f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1380f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!S) { 1390f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // No dead code. Possibly an empty block. Look at dead predecessors. 1400f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 1410f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = Block->pred_end(); I != E; ++I) { 1420f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (const CFGBlock *predBlock = *I) 1430f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek enqueue(predBlock); 1440f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1450f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1460f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 147eeef924c4fcb79a3bcc8782afce343e641bbcb83Chandler Carruth 1480f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isDeadCodeRoot(Block)) { 1490f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek reportDeadCode(S, CB); 1500f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 1510f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1520f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek else { 1530f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Record this statement as the possibly best location in a 1540f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // strongly-connected component of dead code for emitting a 1550f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // warning. 1560f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeferredLocs.push_back(std::make_pair(Block, S)); 1570f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1580f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1590f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1600f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If we didn't find a dead root, then report the dead code with the 1610f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // earliest location. 1620f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!DeferredLocs.empty()) { 1630f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 1640f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 1650f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = DeferredLocs.end(); I != E; ++I) { 1660f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *block = I->first; 1670f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Reachable[block->getBlockID()]) 1680f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1690f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek reportDeadCode(I->second, CB); 1700f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 1710f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1720f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1730f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1740f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return count; 1750f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1760f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1770f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekstatic SourceLocation GetUnreachableLoc(const Stmt *S, 1780f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceRange &R1, 1790f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceRange &R2) { 1800f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek R1 = R2 = SourceRange(); 18172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 182892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 183892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek S = Ex->IgnoreParenImpCasts(); 184892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek 18572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek switch (S->getStmtClass()) { 18672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::BinaryOperatorClass: { 18772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const BinaryOperator *BO = cast<BinaryOperator>(S); 18872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return BO->getOperatorLoc(); 18972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 19072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::UnaryOperatorClass: { 19172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const UnaryOperator *UO = cast<UnaryOperator>(S); 19272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = UO->getSubExpr()->getSourceRange(); 19372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return UO->getOperatorLoc(); 19472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 19572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CompoundAssignOperatorClass: { 19672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 19772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CAO->getLHS()->getSourceRange(); 19872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = CAO->getRHS()->getSourceRange(); 19972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CAO->getOperatorLoc(); 20072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 20156ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall case Expr::BinaryConditionalOperatorClass: 20272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ConditionalOperatorClass: { 20356ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall const AbstractConditionalOperator *CO = 20456ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall cast<AbstractConditionalOperator>(S); 20572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CO->getQuestionLoc(); 20672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 20772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::MemberExprClass: { 20872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const MemberExpr *ME = cast<MemberExpr>(S); 20972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ME->getSourceRange(); 21072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ME->getMemberLoc(); 21172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 21272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ArraySubscriptExprClass: { 21372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 21472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ASE->getLHS()->getSourceRange(); 21572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = ASE->getRHS()->getSourceRange(); 21672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ASE->getRBracketLoc(); 21772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 21872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CStyleCastExprClass: { 21972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 22072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CSC->getSubExpr()->getSourceRange(); 22172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CSC->getLParenLoc(); 22272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 22372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CXXFunctionalCastExprClass: { 22472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 22572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CE->getSubExpr()->getSourceRange(); 22672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CE->getTypeBeginLoc(); 22772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 22872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Stmt::CXXTryStmtClass: { 22972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 23072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 231f85e193739c953358c865005855253af4f68a497John McCall case Expr::ObjCBridgedCastExprClass: { 232f85e193739c953358c865005855253af4f68a497John McCall const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 233f85e193739c953358c865005855253af4f68a497John McCall R1 = CSC->getSubExpr()->getSourceRange(); 234f85e193739c953358c865005855253af4f68a497John McCall return CSC->getLParenLoc(); 235f85e193739c953358c865005855253af4f68a497John McCall } 23672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek default: ; 23772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 23872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = S->getSourceRange(); 23972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return S->getLocStart(); 24072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 24172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2420f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekvoid DeadCodeScan::reportDeadCode(const Stmt *S, 2430f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB) { 24472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R1, R2; 2450f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 2460f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek CB.HandleUnreachable(Loc, R1, R2); 24772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 24872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 24972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremeneknamespace clang { namespace reachable_code { 2500f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2510f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekunsigned ScanReachableFromBlock(const CFGBlock *Start, 25272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector &Reachable) { 2533d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned count = 0; 2540f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2552166948cc721b138b3aaf4358d28ec2dada22901Nico Weber // Prep work queue 2560f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SmallVector<const CFGBlock*, 32> WL; 2570f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2580f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // The entry block may have already been marked reachable 2590f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // by the caller. 2600f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!Reachable[Start->getBlockID()]) { 2610f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ++count; 2620f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek Reachable[Start->getBlockID()] = true; 2630f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 2640f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2650f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek WL.push_back(Start); 2660f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2678caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek // Find the reachable blocks from 'Start'. 2683d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek while (!WL.empty()) { 2690f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *item = WL.pop_back_val(); 2700f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2710f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Look at the successors and mark then reachable. 2720f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_succ_iterator I = item->succ_begin(), 2730f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = item->succ_end(); I != E; ++I) 2743d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (const CFGBlock *B = *I) { 2753d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned blockID = B->getBlockID(); 2763d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (!Reachable[blockID]) { 2773d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek Reachable.set(blockID); 2783d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek WL.push_back(B); 2790f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ++count; 2803d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2813d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2823d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2833d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek return count; 2843d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek} 2850f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 28672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekvoid FindUnreachableCode(AnalysisContext &AC, Callback &CB) { 28772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CFG *cfg = AC.getCFG(); 28872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!cfg) 28972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 29072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2910f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Scan for reachable blocks from the entrance of the CFG. 2920f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If there are no unreachable blocks, we're done. 29372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector reachable(cfg->getNumBlockIDs()); 2940f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 29572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 29672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 2970f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2980f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If there aren't explicit EH edges, we should include the 'try' dispatch 2990f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // blocks as roots. 3000f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!AC.getCFGBuildOptions().AddEHEdges) { 3010f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 3020f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = cfg->try_blocks_end() ; I != E; ++I) { 3030f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek numReachable += ScanReachableFromBlock(*I, reachable); 30472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 3050f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 3060f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return; 30772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 30872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 3090f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // There are some unreachable blocks. We need to find the root blocks that 3100f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // contain code that should be considered unreachable. 3110f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 3120f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *block = *I; 3130f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // A block may have been marked reachable during this loop. 3140f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (reachable[block->getBlockID()]) 3150f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 3160f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 3170f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeadCodeScan DS(reachable); 3180f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek numReachable += DS.scanBackwards(block, CB); 3190f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 3200f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 3210f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return; 32272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 32372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 32472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 32572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek}} // end namespace clang::reachable_code 326