ReachableCode.cpp revision f85e193739c953358c865005855253af4f68a497
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 2872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekstatic SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, 2972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange &R2) { 3072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const Stmt *S = 0; 3172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek unsigned sn = 0; 3272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = R2 = SourceRange(); 3372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 34b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu if (sn < b.size()) { 353c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek const CFGStmt *CS = b[sn].getAs<CFGStmt>(); 36b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu if (!CS) 37eeef924c4fcb79a3bcc8782afce343e641bbcb83Chandler Carruth return SourceLocation(); 38eeef924c4fcb79a3bcc8782afce343e641bbcb83Chandler Carruth 393c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek S = CS->getStmt(); 40b36cd3e1757fb4fcd9509f35558c847b04bef35fZhongxing Xu } else if (b.getTerminator()) 4172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek S = b.getTerminator(); 4272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek else 4372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return SourceLocation(); 4472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 45892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek if (const Expr *Ex = dyn_cast<Expr>(S)) 46892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek S = Ex->IgnoreParenImpCasts(); 47892697dd2287caf7c29aaaa82909b0e90b8b63feTed Kremenek 4872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek switch (S->getStmtClass()) { 4972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::BinaryOperatorClass: { 5072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const BinaryOperator *BO = cast<BinaryOperator>(S); 512de56d1d0c3a504ad1529de2677628bdfbb95cd4John McCall if (BO->getOpcode() == BO_Comma) { 5272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (sn+1 < b.size()) 533c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return b[sn+1].getAs<CFGStmt>()->getStmt()->getLocStart(); 5472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CFGBlock *n = &b; 5572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek while (1) { 5672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (n->getTerminator()) 5772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return n->getTerminator()->getLocStart(); 5872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (n->succ_size() != 1) 5972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return SourceLocation(); 6072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek n = n[0].succ_begin()[0]; 6172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (n->pred_size() != 1) 6272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return SourceLocation(); 6372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!n->empty()) 643c0349e87cdbd7316d06d2411d86ee1086e717a5Ted Kremenek return n[0][0].getAs<CFGStmt>()->getStmt()->getLocStart(); 6572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 6672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 6772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = BO->getLHS()->getSourceRange(); 6872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = BO->getRHS()->getSourceRange(); 6972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return BO->getOperatorLoc(); 7072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 7172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::UnaryOperatorClass: { 7272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const UnaryOperator *UO = cast<UnaryOperator>(S); 7372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = UO->getSubExpr()->getSourceRange(); 7472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return UO->getOperatorLoc(); 7572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 7672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CompoundAssignOperatorClass: { 7772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 7872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CAO->getLHS()->getSourceRange(); 7972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = CAO->getRHS()->getSourceRange(); 8072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CAO->getOperatorLoc(); 8172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 8256ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall case Expr::BinaryConditionalOperatorClass: 8372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ConditionalOperatorClass: { 8456ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall const AbstractConditionalOperator *CO = 8556ca35d396d8692c384c785f9aeebcf22563fe1eJohn McCall cast<AbstractConditionalOperator>(S); 8672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CO->getQuestionLoc(); 8772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 8872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::MemberExprClass: { 8972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const MemberExpr *ME = cast<MemberExpr>(S); 9072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ME->getSourceRange(); 9172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ME->getMemberLoc(); 9272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 9372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::ArraySubscriptExprClass: { 9472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 9572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = ASE->getLHS()->getSourceRange(); 9672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R2 = ASE->getRHS()->getSourceRange(); 9772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return ASE->getRBracketLoc(); 9872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 9972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CStyleCastExprClass: { 10072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 10172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CSC->getSubExpr()->getSourceRange(); 10272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CSC->getLParenLoc(); 10372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 10472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Expr::CXXFunctionalCastExprClass: { 10572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 10672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = CE->getSubExpr()->getSourceRange(); 10772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return CE->getTypeBeginLoc(); 10872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 10972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek case Stmt::CXXTryStmtClass: { 11072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 11172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 112f85e193739c953358c865005855253af4f68a497John McCall case Expr::ObjCBridgedCastExprClass: { 113f85e193739c953358c865005855253af4f68a497John McCall const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 114f85e193739c953358c865005855253af4f68a497John McCall R1 = CSC->getSubExpr()->getSourceRange(); 115f85e193739c953358c865005855253af4f68a497John McCall return CSC->getLParenLoc(); 116f85e193739c953358c865005855253af4f68a497John McCall } 11772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek default: ; 11872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 11972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek R1 = S->getSourceRange(); 12072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return S->getLocStart(); 12172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 12272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 12372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekstatic SourceLocation MarkLiveTop(const CFGBlock *Start, 12472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector &reachable, 12572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceManager &SM) { 12672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 12772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Prep work worklist. 12872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::SmallVector<const CFGBlock*, 32> WL; 12972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek WL.push_back(Start); 13072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 13172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R1, R2; 13272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation top = GetUnreachableLoc(*Start, R1, R2); 13372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 13472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek bool FromMainFile = false; 13572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek bool FromSystemHeader = false; 13672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek bool TopValid = false; 13772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 13872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (top.isValid()) { 13972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek FromMainFile = SM.isFromMainFile(top); 14072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek FromSystemHeader = SM.isInSystemHeader(top); 14172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek TopValid = true; 14272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 14372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 14472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Solve 1458caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek CFGBlock::FilterOptions FO; 1468caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek FO.IgnoreDefaultsWithCoveredEnums = 1; 1478caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek 14872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek while (!WL.empty()) { 14972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek const CFGBlock *item = WL.back(); 15072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek WL.pop_back(); 15172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 15272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation c = GetUnreachableLoc(*item, R1, R2); 15372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (c.isValid() 15472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek && (!TopValid 15572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek || (SM.isFromMainFile(c) && !FromMainFile) 15672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek || (FromSystemHeader && !SM.isInSystemHeader(c)) 15772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek || SM.isBeforeInTranslationUnit(c, top))) { 15872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek top = c; 15972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek FromMainFile = SM.isFromMainFile(top); 16072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek FromSystemHeader = SM.isInSystemHeader(top); 16172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 16272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 16372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek reachable.set(item->getBlockID()); 1648caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek for (CFGBlock::filtered_succ_iterator I = 1658caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek item->filtered_succ_start_end(FO); I.hasMore(); ++I) 16672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (const CFGBlock *B = *I) { 16772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek unsigned blockID = B->getBlockID(); 16872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!reachable[blockID]) { 16972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek reachable.set(blockID); 17072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek WL.push_back(B); 17172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 17272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 17372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 17472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 17572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return top; 17672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 17772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 17872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekstatic int LineCmp(const void *p1, const void *p2) { 17972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation *Line1 = (SourceLocation *)p1; 18072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation *Line2 = (SourceLocation *)p2; 18172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return !(*Line1 < *Line2); 18272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 18372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 18472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremeneknamespace { 18572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekstruct ErrLoc { 18672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation Loc; 18772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R1; 18872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R2; 18972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2) 19072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek : Loc(l), R1(r1), R2(r2) { } 19172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek}; 19272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 19372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremeneknamespace clang { namespace reachable_code { 19472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 1953d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek/// ScanReachableFromBlock - Mark all blocks reachable from Start. 1963d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek/// Returns the total number of blocks that were marked reachable. 19772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekunsigned ScanReachableFromBlock(const CFGBlock &Start, 19872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector &Reachable) { 1993d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned count = 0; 20072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::SmallVector<const CFGBlock*, 32> WL; 20172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2022166948cc721b138b3aaf4358d28ec2dada22901Nico Weber // Prep work queue 2033d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek Reachable.set(Start.getBlockID()); 2043d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek ++count; 2053d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek WL.push_back(&Start); 20672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 2078caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek // Find the reachable blocks from 'Start'. 2088caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek CFGBlock::FilterOptions FO; 2098caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek FO.IgnoreDefaultsWithCoveredEnums = 1; 2108caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek 2113d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek while (!WL.empty()) { 2123d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek const CFGBlock *item = WL.back(); 2133d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek WL.pop_back(); 21472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 21572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Look at the successors and mark then reachable. 2168caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO); 2178caec849a765de7b0b4ae8b9769397ce62236321Ted Kremenek I.hasMore(); ++I) 2183d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (const CFGBlock *B = *I) { 2193d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek unsigned blockID = B->getBlockID(); 2203d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek if (!Reachable[blockID]) { 2213d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek Reachable.set(blockID); 2223d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek ++count; 2233d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek WL.push_back(B); 2243d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2253d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2263d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek } 2273d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek return count; 2283d2eed823d534ee370cfd7742c1e96ab3ee9a80bTed Kremenek} 22972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 23072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenekvoid FindUnreachableCode(AnalysisContext &AC, Callback &CB) { 23172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CFG *cfg = AC.getCFG(); 23272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!cfg) 23372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 23472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 23572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Scan for reachable blocks. 23672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::BitVector reachable(cfg->getNumBlockIDs()); 23772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable); 23872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 23972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // If there are no unreachable blocks, we're done. 24072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (numReachable == cfg->getNumBlockIDs()) 24172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek return; 24272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 24372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange R1, R2; 24472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 24572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::SmallVector<ErrLoc, 24> lines; 24672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek bool AddEHEdges = AC.getAddEHEdges(); 24772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 24872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // First, give warnings for blocks with no predecessors, as they 24972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // can't be part of a loop. 25072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 25172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CFGBlock &b = **I; 25272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!reachable[b.getBlockID()]) { 25372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (b.pred_empty()) { 2544ba72a0b28135209c435630682febe1f854ccfa6Marcin Swiderski if (!AddEHEdges 2554ba72a0b28135209c435630682febe1f854ccfa6Marcin Swiderski && dyn_cast_or_null<CXXTryStmt>(b.getTerminator().getStmt())) { 25672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // When not adding EH edges from calls, catch clauses 25772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // can otherwise seem dead. Avoid noting them as dead. 25872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek numReachable += ScanReachableFromBlock(b, reachable); 25972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek continue; 26072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 26172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceLocation c = GetUnreachableLoc(b, R1, R2); 26272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!c.isValid()) { 26372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Blocks without a location can't produce a warning, so don't mark 26472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // reachable blocks from here as live. 26572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek reachable.set(b.getBlockID()); 26672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek ++numReachable; 26772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek continue; 26872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 26972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek lines.push_back(ErrLoc(c, R1, R2)); 27072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Avoid excessive errors by marking everything reachable from here 27172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek numReachable += ScanReachableFromBlock(b, reachable); 27272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 27372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 27472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 27572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 27672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (numReachable < cfg->getNumBlockIDs()) { 27772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // And then give warnings for the tops of loops. 27872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 27972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CFGBlock &b = **I; 28072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (!reachable[b.getBlockID()]) 28172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek // Avoid excessive errors by marking everything reachable from here 28272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek lines.push_back(ErrLoc(MarkLiveTop(&b, reachable, 28372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek AC.getASTContext().getSourceManager()), 28472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek SourceRange(), SourceRange())); 28572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 28672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek } 28772919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 28872919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp); 28972919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 29072919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end(); 29172919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek I != E; ++I) 29272919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek if (I->Loc.isValid()) 29372919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek CB.HandleUnreachable(I->Loc, I->R1, I->R2); 29472919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek} 29572919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek 29672919a334752bc87001a7e3a0b6e5892768fac20Ted Kremenek}} // end namespace clang::reachable_code 297