contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp

   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
  26 using namespace clang;
  27
  28 static 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
 123 static 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
 178 static int LineCmp(const void *p1, const void *p2) {
 179   SourceLocation *Line1 = (SourceLocation *)p1;
 180   SourceLocation *Line2 = (SourceLocation *)p2;
 181   return !(*Line1 < *Line2);
 182 }
 183
 184 namespace {
 185 struct 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 }
 193 namespace clang { namespace reachable_code {
 194
 195 /// ScanReachableFromBlock - Mark all blocks reachable from Start.
 196 /// Returns the total number of blocks that were marked reachable.
 197 unsigned 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
 230 void 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