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 1555fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/Analyses/ReachableCode.h" 1672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/Expr.h" 1772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/ExprCXX.h" 18f85e193739c953358c865005855253af4f68a497John McCall#include "clang/AST/ExprObjC.h" 1972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/AST/StmtCXX.h" 2072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/Analysis/AnalysisContext.h" 2155fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Analysis/CFG.h" 2272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek#include "clang/Basic/SourceManager.h" 2355fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "llvm/ADT/BitVector.h" 2455fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "llvm/ADT/SmallVector.h" 253d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek 263d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenekusing namespace clang; 273d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek 280f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremeneknamespace { 290f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekclass DeadCodeScan { 300f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::BitVector Visited; 310f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::BitVector &Reachable; 32cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko SmallVector<const CFGBlock *, 10> WorkList; 330f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 34cfa88f893915ceb8ae4ce2f17c46c24a4d67502fDmitri Gribenko typedef 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) { 89e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek if (S->getLocStart().isInvalid()) 900f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return false; 91e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S)) 920f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return BO->getOpcode() != BO_Comma; 930f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return true; 940f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 950f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 960f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekconst Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) { 970f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I) 98b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) { 99b07805485c603be3d8011f72611465324c9e664bDavid Blaikie const Stmt *S = CS->getStmt(); 1000f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isValidDeadStmt(S)) 1010f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return S; 1020f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1030f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1040f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (CFGTerminator T = Block->getTerminator()) { 1050f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *S = T.getStmt(); 1060f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isValidDeadStmt(S)) 1070f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return S; 1080f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1090f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1100f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return 0; 1110f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1120f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1130f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekstatic int SrcCmp(const void *p1, const void *p2) { 1140f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return 11531ba6135375433b617a8587ea6cc836a014ebd86Roman Divacky ((const std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() < 11631ba6135375433b617a8587ea6cc836a014ebd86Roman Divacky ((const std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart(); 1170f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1180f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1190f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekunsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start, 1200f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB) { 12172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 1220f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned count = 0; 1230f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek enqueue(Start); 1240f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1250f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek while (!WorkList.empty()) { 1260f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *Block = WorkList.pop_back_val(); 1270f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1280f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // It is possible that this block has been marked reachable after 1290f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // it was enqueued. 1300f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Reachable[Block->getBlockID()]) 1310f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1320f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1330f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Look for any dead code within the block. 1340f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const Stmt *S = findDeadCode(Block); 1350f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1360f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!S) { 1370f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // No dead code. Possibly an empty block. Look at dead predecessors. 1380f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_pred_iterator I = Block->pred_begin(), 1390f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = Block->pred_end(); I != E; ++I) { 1400f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (const CFGBlock *predBlock = *I) 1410f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek enqueue(predBlock); 1420f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1430f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1440f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 145e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek 146e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek // Specially handle macro-expanded code. 147e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek if (S->getLocStart().isMacroID()) { 148e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 149e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek continue; 150e7a2764b2c98859aa42a3fd36d55cd34c7fe883eTed Kremenek } 151eeef924c4fcb79a3bcc8782afce343e641bbcb83Chandler Carruth 1520f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (isDeadCodeRoot(Block)) { 1530f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek reportDeadCode(S, CB); 1540f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable); 1550f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1560f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek else { 1570f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Record this statement as the possibly best location in a 1580f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // strongly-connected component of dead code for emitting a 1590f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // warning. 1600f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeferredLocs.push_back(std::make_pair(Block, S)); 1610f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1620f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1630f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1640f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If we didn't find a dead root, then report the dead code with the 1650f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // earliest location. 1660f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!DeferredLocs.empty()) { 1670f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp); 1680f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (DeferredLocsTy::iterator I = DeferredLocs.begin(), 1690f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = DeferredLocs.end(); I != E; ++I) { 1700f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *block = I->first; 1710f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (Reachable[block->getBlockID()]) 1720f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 1730f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek reportDeadCode(I->second, CB); 1740f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek count += clang::reachable_code::ScanReachableFromBlock(block, Reachable); 1750f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1760f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 1770f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1780f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return count; 1790f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek} 1800f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 1810f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekstatic SourceLocation GetUnreachableLoc(const Stmt *S, 1820f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceRange &R1, 1830f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceRange &R2) { 1840f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek R1 = R2 = SourceRange(); 18572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 186892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 187892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek S = Ex->IgnoreParenImpCasts(); 188892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek 18972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek switch (S->getStmtClass()) { 19072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::BinaryOperatorClass: { 19172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const BinaryOperator *BO = cast<BinaryOperator>(S); 19272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return BO->getOperatorLoc(); 19372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 19472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::UnaryOperatorClass: { 19572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const UnaryOperator *UO = cast<UnaryOperator>(S); 19672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = UO->getSubExpr()->getSourceRange(); 19772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return UO->getOperatorLoc(); 19872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 19972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CompoundAssignOperatorClass: { 20072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 20172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CAO->getLHS()->getSourceRange(); 20272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = CAO->getRHS()->getSourceRange(); 20372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CAO->getOperatorLoc(); 20472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 20556ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall case Expr::BinaryConditionalOperatorClass: 20672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ConditionalOperatorClass: { 20756ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall const AbstractConditionalOperator *CO = 20856ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall cast<AbstractConditionalOperator>(S); 20972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CO->getQuestionLoc(); 21072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 21172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::MemberExprClass: { 21272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const MemberExpr *ME = cast<MemberExpr>(S); 21372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ME->getSourceRange(); 21472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ME->getMemberLoc(); 21572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 21672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ArraySubscriptExprClass: { 21772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 21872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ASE->getLHS()->getSourceRange(); 21972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = ASE->getRHS()->getSourceRange(); 22072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ASE->getRBracketLoc(); 22172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 22272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CStyleCastExprClass: { 22372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 22472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CSC->getSubExpr()->getSourceRange(); 22572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CSC->getLParenLoc(); 22672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 22772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CXXFunctionalCastExprClass: { 22872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 22972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CE->getSubExpr()->getSourceRange(); 23072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CE->getTypeBeginLoc(); 23172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 23272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Stmt::CXXTryStmtClass: { 23372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 23472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 235f85e193739c953358c865005855253af4f68a497John McCall case Expr::ObjCBridgedCastExprClass: { 236f85e193739c953358c865005855253af4f68a497John McCall const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 237f85e193739c953358c865005855253af4f68a497John McCall R1 = CSC->getSubExpr()->getSourceRange(); 238f85e193739c953358c865005855253af4f68a497John McCall return CSC->getLParenLoc(); 239f85e193739c953358c865005855253af4f68a497John McCall } 24072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek default: ; 24172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 24272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = S->getSourceRange(); 24372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return S->getLocStart(); 24472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 24572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2460f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekvoid DeadCodeScan::reportDeadCode(const Stmt *S, 2470f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek clang::reachable_code::Callback &CB) { 24872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R1, R2; 2490f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SourceLocation Loc = GetUnreachableLoc(S, R1, R2); 2500f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek CB.HandleUnreachable(Loc, R1, R2); 25172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 25272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 25372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremeneknamespace clang { namespace reachable_code { 25499ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 25599ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikievoid Callback::anchor() { } 25699ba9e3bd70671f3441fb974895f226a83ce0e66David Blaikie 2570f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenekunsigned ScanReachableFromBlock(const CFGBlock *Start, 25872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector &Reachable) { 2593d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned count = 0; 2600f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2612166948cc721b138b3aaf4358d28ec2dada22901Nico Weber // Prep work queue 2620f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek SmallVector<const CFGBlock*, 32> WL; 2630f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2640f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // The entry block may have already been marked reachable 2650f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // by the caller. 2660f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!Reachable[Start->getBlockID()]) { 2670f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ++count; 2680f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek Reachable[Start->getBlockID()] = true; 2690f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek } 2700f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2710f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek WL.push_back(Start); 2720f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2738caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek // Find the reachable blocks from 'Start'. 2743d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek while (!WL.empty()) { 2750f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *item = WL.pop_back_val(); 2760f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2770f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Look at the successors and mark then reachable. 2780f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFGBlock::const_succ_iterator I = item->succ_begin(), 2790f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = item->succ_end(); I != E; ++I) 2803d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (const CFGBlock *B = *I) { 2813d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned blockID = B->getBlockID(); 2823d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (!Reachable[blockID]) { 2833d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek Reachable.set(blockID); 2843d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek WL.push_back(B); 2850f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek ++count; 2863d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2873d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2883d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2893d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek return count; 2903d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek} 2910f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 2921d26f48dc2eea1c07431ca1519d7034a21b9bcffTed Kremenekvoid FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { 29372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CFG *cfg = AC.getCFG(); 29472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!cfg) 29572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 29672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2970f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // Scan for reachable blocks from the entrance of the CFG. 2980f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If there are no unreachable blocks, we're done. 29972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector reachable(cfg->getNumBlockIDs()); 3000f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable); 30172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 30272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 3030f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 3040f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // If there aren't explicit EH edges, we should include the 'try' dispatch 3050f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // blocks as roots. 3060f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (!AC.getCFGBuildOptions().AddEHEdges) { 3070f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFG::try_block_iterator I = cfg->try_blocks_begin(), 3080f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek E = cfg->try_blocks_end() ; I != E; ++I) { 3090f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek numReachable += ScanReachableFromBlock(*I, reachable); 31072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 3110f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 3120f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return; 31372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 31472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 3150f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // There are some unreachable blocks. We need to find the root blocks that 3160f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // contain code that should be considered unreachable. 3170f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 3180f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek const CFGBlock *block = *I; 3190f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek // A block may have been marked reachable during this loop. 3200f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (reachable[block->getBlockID()]) 3210f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek continue; 3220f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 3230f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek DeadCodeScan DS(reachable); 3240f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek numReachable += DS.scanBackwards(block, CB); 3250f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek 3260f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 3270f3b4ca1764cd6d457f511d340fba504f41763c3Ted Kremenek return; 32872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 32972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 33072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 33172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek}} // end namespace clang::reachable_code 332