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