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