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