ReachableCode.cpp revision f85e193739c953358c865005855253af4f68a497
1//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a flow-sensitive, path-insensitive analysis of 11// determining reachable blocks within a CFG. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/ADT/BitVector.h" 16#include "llvm/ADT/SmallVector.h" 17#include "clang/AST/Expr.h" 18#include "clang/AST/ExprCXX.h" 19#include "clang/AST/ExprObjC.h" 20#include "clang/AST/StmtCXX.h" 21#include "clang/Analysis/Analyses/ReachableCode.h" 22#include "clang/Analysis/CFG.h" 23#include "clang/Analysis/AnalysisContext.h" 24#include "clang/Basic/SourceManager.h" 25 26using namespace clang; 27 28static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, 29 SourceRange &R2) { 30 const Stmt *S = 0; 31 unsigned sn = 0; 32 R1 = R2 = SourceRange(); 33 34 if (sn < b.size()) { 35 const CFGStmt *CS = b[sn].getAs<CFGStmt>(); 36 if (!CS) 37 return SourceLocation(); 38 39 S = CS->getStmt(); 40 } else if (b.getTerminator()) 41 S = b.getTerminator(); 42 else 43 return SourceLocation(); 44 45 if (const Expr *Ex = dyn_cast<Expr>(S)) 46 S = Ex->IgnoreParenImpCasts(); 47 48 switch (S->getStmtClass()) { 49 case Expr::BinaryOperatorClass: { 50 const BinaryOperator *BO = cast<BinaryOperator>(S); 51 if (BO->getOpcode() == BO_Comma) { 52 if (sn+1 < b.size()) 53 return b[sn+1].getAs<CFGStmt>()->getStmt()->getLocStart(); 54 const CFGBlock *n = &b; 55 while (1) { 56 if (n->getTerminator()) 57 return n->getTerminator()->getLocStart(); 58 if (n->succ_size() != 1) 59 return SourceLocation(); 60 n = n[0].succ_begin()[0]; 61 if (n->pred_size() != 1) 62 return SourceLocation(); 63 if (!n->empty()) 64 return n[0][0].getAs<CFGStmt>()->getStmt()->getLocStart(); 65 } 66 } 67 R1 = BO->getLHS()->getSourceRange(); 68 R2 = BO->getRHS()->getSourceRange(); 69 return BO->getOperatorLoc(); 70 } 71 case Expr::UnaryOperatorClass: { 72 const UnaryOperator *UO = cast<UnaryOperator>(S); 73 R1 = UO->getSubExpr()->getSourceRange(); 74 return UO->getOperatorLoc(); 75 } 76 case Expr::CompoundAssignOperatorClass: { 77 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); 78 R1 = CAO->getLHS()->getSourceRange(); 79 R2 = CAO->getRHS()->getSourceRange(); 80 return CAO->getOperatorLoc(); 81 } 82 case Expr::BinaryConditionalOperatorClass: 83 case Expr::ConditionalOperatorClass: { 84 const AbstractConditionalOperator *CO = 85 cast<AbstractConditionalOperator>(S); 86 return CO->getQuestionLoc(); 87 } 88 case Expr::MemberExprClass: { 89 const MemberExpr *ME = cast<MemberExpr>(S); 90 R1 = ME->getSourceRange(); 91 return ME->getMemberLoc(); 92 } 93 case Expr::ArraySubscriptExprClass: { 94 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); 95 R1 = ASE->getLHS()->getSourceRange(); 96 R2 = ASE->getRHS()->getSourceRange(); 97 return ASE->getRBracketLoc(); 98 } 99 case Expr::CStyleCastExprClass: { 100 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); 101 R1 = CSC->getSubExpr()->getSourceRange(); 102 return CSC->getLParenLoc(); 103 } 104 case Expr::CXXFunctionalCastExprClass: { 105 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); 106 R1 = CE->getSubExpr()->getSourceRange(); 107 return CE->getTypeBeginLoc(); 108 } 109 case Stmt::CXXTryStmtClass: { 110 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); 111 } 112 case Expr::ObjCBridgedCastExprClass: { 113 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S); 114 R1 = CSC->getSubExpr()->getSourceRange(); 115 return CSC->getLParenLoc(); 116 } 117 default: ; 118 } 119 R1 = S->getSourceRange(); 120 return S->getLocStart(); 121} 122 123static SourceLocation MarkLiveTop(const CFGBlock *Start, 124 llvm::BitVector &reachable, 125 SourceManager &SM) { 126 127 // Prep work worklist. 128 llvm::SmallVector<const CFGBlock*, 32> WL; 129 WL.push_back(Start); 130 131 SourceRange R1, R2; 132 SourceLocation top = GetUnreachableLoc(*Start, R1, R2); 133 134 bool FromMainFile = false; 135 bool FromSystemHeader = false; 136 bool TopValid = false; 137 138 if (top.isValid()) { 139 FromMainFile = SM.isFromMainFile(top); 140 FromSystemHeader = SM.isInSystemHeader(top); 141 TopValid = true; 142 } 143 144 // Solve 145 CFGBlock::FilterOptions FO; 146 FO.IgnoreDefaultsWithCoveredEnums = 1; 147 148 while (!WL.empty()) { 149 const CFGBlock *item = WL.back(); 150 WL.pop_back(); 151 152 SourceLocation c = GetUnreachableLoc(*item, R1, R2); 153 if (c.isValid() 154 && (!TopValid 155 || (SM.isFromMainFile(c) && !FromMainFile) 156 || (FromSystemHeader && !SM.isInSystemHeader(c)) 157 || SM.isBeforeInTranslationUnit(c, top))) { 158 top = c; 159 FromMainFile = SM.isFromMainFile(top); 160 FromSystemHeader = SM.isInSystemHeader(top); 161 } 162 163 reachable.set(item->getBlockID()); 164 for (CFGBlock::filtered_succ_iterator I = 165 item->filtered_succ_start_end(FO); I.hasMore(); ++I) 166 if (const CFGBlock *B = *I) { 167 unsigned blockID = B->getBlockID(); 168 if (!reachable[blockID]) { 169 reachable.set(blockID); 170 WL.push_back(B); 171 } 172 } 173 } 174 175 return top; 176} 177 178static int LineCmp(const void *p1, const void *p2) { 179 SourceLocation *Line1 = (SourceLocation *)p1; 180 SourceLocation *Line2 = (SourceLocation *)p2; 181 return !(*Line1 < *Line2); 182} 183 184namespace { 185struct ErrLoc { 186 SourceLocation Loc; 187 SourceRange R1; 188 SourceRange R2; 189 ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2) 190 : Loc(l), R1(r1), R2(r2) { } 191}; 192} 193namespace clang { namespace reachable_code { 194 195/// ScanReachableFromBlock - Mark all blocks reachable from Start. 196/// Returns the total number of blocks that were marked reachable. 197unsigned ScanReachableFromBlock(const CFGBlock &Start, 198 llvm::BitVector &Reachable) { 199 unsigned count = 0; 200 llvm::SmallVector<const CFGBlock*, 32> WL; 201 202 // Prep work queue 203 Reachable.set(Start.getBlockID()); 204 ++count; 205 WL.push_back(&Start); 206 207 // Find the reachable blocks from 'Start'. 208 CFGBlock::FilterOptions FO; 209 FO.IgnoreDefaultsWithCoveredEnums = 1; 210 211 while (!WL.empty()) { 212 const CFGBlock *item = WL.back(); 213 WL.pop_back(); 214 215 // Look at the successors and mark then reachable. 216 for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO); 217 I.hasMore(); ++I) 218 if (const CFGBlock *B = *I) { 219 unsigned blockID = B->getBlockID(); 220 if (!Reachable[blockID]) { 221 Reachable.set(blockID); 222 ++count; 223 WL.push_back(B); 224 } 225 } 226 } 227 return count; 228} 229 230void FindUnreachableCode(AnalysisContext &AC, Callback &CB) { 231 CFG *cfg = AC.getCFG(); 232 if (!cfg) 233 return; 234 235 // Scan for reachable blocks. 236 llvm::BitVector reachable(cfg->getNumBlockIDs()); 237 unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable); 238 239 // If there are no unreachable blocks, we're done. 240 if (numReachable == cfg->getNumBlockIDs()) 241 return; 242 243 SourceRange R1, R2; 244 245 llvm::SmallVector<ErrLoc, 24> lines; 246 bool AddEHEdges = AC.getAddEHEdges(); 247 248 // First, give warnings for blocks with no predecessors, as they 249 // can't be part of a loop. 250 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 251 CFGBlock &b = **I; 252 if (!reachable[b.getBlockID()]) { 253 if (b.pred_empty()) { 254 if (!AddEHEdges 255 && dyn_cast_or_null<CXXTryStmt>(b.getTerminator().getStmt())) { 256 // When not adding EH edges from calls, catch clauses 257 // can otherwise seem dead. Avoid noting them as dead. 258 numReachable += ScanReachableFromBlock(b, reachable); 259 continue; 260 } 261 SourceLocation c = GetUnreachableLoc(b, R1, R2); 262 if (!c.isValid()) { 263 // Blocks without a location can't produce a warning, so don't mark 264 // reachable blocks from here as live. 265 reachable.set(b.getBlockID()); 266 ++numReachable; 267 continue; 268 } 269 lines.push_back(ErrLoc(c, R1, R2)); 270 // Avoid excessive errors by marking everything reachable from here 271 numReachable += ScanReachableFromBlock(b, reachable); 272 } 273 } 274 } 275 276 if (numReachable < cfg->getNumBlockIDs()) { 277 // And then give warnings for the tops of loops. 278 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 279 CFGBlock &b = **I; 280 if (!reachable[b.getBlockID()]) 281 // Avoid excessive errors by marking everything reachable from here 282 lines.push_back(ErrLoc(MarkLiveTop(&b, reachable, 283 AC.getASTContext().getSourceManager()), 284 SourceRange(), SourceRange())); 285 } 286 } 287 288 llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp); 289 290 for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end(); 291 I != E; ++I) 292 if (I->Loc.isValid()) 293 CB.HandleUnreachable(I->Loc, I->R1, I->R2); 294} 295 296}} // end namespace clang::reachable_code 297