ReachableCode.cpp revision 2de56d1d0c3a504ad1529de2677628bdfbb95cd4 
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
25using namespace clang;
26
27static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1,
28                                        SourceRange &R2) {
29  const Stmt *S = 0;
30  unsigned sn = 0;
31  R1 = R2 = SourceRange();
32
33top:
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
112static 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
164static int LineCmp(const void *p1, const void *p2) {
165  SourceLocation *Line1 = (SourceLocation *)p1;
166  SourceLocation *Line2 = (SourceLocation *)p2;
167  return !(*Line1 < *Line2);
168}
169
170namespace {
171struct 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}
179namespace clang { namespace reachable_code {
180
181/// ScanReachableFromBlock - Mark all blocks reachable from Start.
182/// Returns the total number of blocks that were marked reachable.
183unsigned 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
213void 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
279