ReachableCode.cpp revision d6a65a9b6c31e721bf992e67f1ddc8e943c55227 
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  CFGBlock::FilterOptions FO;
135  FO.IgnoreDefaultsWithCoveredEnums = 1;
136
137  while (!WL.empty()) {
138    const CFGBlock *item = WL.back();
139    WL.pop_back();
140
141    SourceLocation c = GetUnreachableLoc(*item, R1, R2);
142    if (c.isValid()
143        && (!TopValid
144            || (SM.isFromMainFile(c) && !FromMainFile)
145            || (FromSystemHeader && !SM.isInSystemHeader(c))
146            || SM.isBeforeInTranslationUnit(c, top))) {
147          top = c;
148          FromMainFile = SM.isFromMainFile(top);
149          FromSystemHeader = SM.isInSystemHeader(top);
150        }
151
152    reachable.set(item->getBlockID());
153    for (CFGBlock::filtered_succ_iterator I =
154	   item->filtered_succ_start_end(FO); I.hasMore(); ++I)
155      if (const CFGBlock *B = *I) {
156        unsigned blockID = B->getBlockID();
157        if (!reachable[blockID]) {
158          reachable.set(blockID);
159          WL.push_back(B);
160        }
161      }
162  }
163
164  return top;
165}
166
167static int LineCmp(const void *p1, const void *p2) {
168  SourceLocation *Line1 = (SourceLocation *)p1;
169  SourceLocation *Line2 = (SourceLocation *)p2;
170  return !(*Line1 < *Line2);
171}
172
173namespace {
174struct ErrLoc {
175  SourceLocation Loc;
176  SourceRange R1;
177  SourceRange R2;
178  ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2)
179  : Loc(l), R1(r1), R2(r2) { }
180};
181}
182namespace clang { namespace reachable_code {
183
184/// ScanReachableFromBlock - Mark all blocks reachable from Start.
185/// Returns the total number of blocks that were marked reachable.
186unsigned ScanReachableFromBlock(const CFGBlock &Start,
187                                llvm::BitVector &Reachable) {
188  unsigned count = 0;
189  llvm::SmallVector<const CFGBlock*, 32> WL;
190
191    // Prep work queue
192  Reachable.set(Start.getBlockID());
193  ++count;
194  WL.push_back(&Start);
195
196  // Find the reachable blocks from 'Start'.
197  CFGBlock::FilterOptions FO;
198  FO.IgnoreDefaultsWithCoveredEnums = 1;
199
200  while (!WL.empty()) {
201    const CFGBlock *item = WL.back();
202    WL.pop_back();
203
204      // Look at the successors and mark then reachable.
205    for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO);
206         I.hasMore(); ++I)
207      if (const CFGBlock *B = *I) {
208        unsigned blockID = B->getBlockID();
209        if (!Reachable[blockID]) {
210          Reachable.set(blockID);
211          ++count;
212          WL.push_back(B);
213        }
214      }
215  }
216  return count;
217}
218
219void FindUnreachableCode(AnalysisContext &AC, Callback &CB) {
220  CFG *cfg = AC.getCFG();
221  if (!cfg)
222    return;
223
224  // Scan for reachable blocks.
225  llvm::BitVector reachable(cfg->getNumBlockIDs());
226  unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable);
227
228    // If there are no unreachable blocks, we're done.
229  if (numReachable == cfg->getNumBlockIDs())
230    return;
231
232  SourceRange R1, R2;
233
234  llvm::SmallVector<ErrLoc, 24> lines;
235  bool AddEHEdges = AC.getAddEHEdges();
236
237  // First, give warnings for blocks with no predecessors, as they
238  // can't be part of a loop.
239  for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
240    CFGBlock &b = **I;
241    if (!reachable[b.getBlockID()]) {
242      if (b.pred_empty()) {
243        if (!AddEHEdges && dyn_cast_or_null<CXXTryStmt>(b.getTerminator())) {
244            // When not adding EH edges from calls, catch clauses
245            // can otherwise seem dead.  Avoid noting them as dead.
246          numReachable += ScanReachableFromBlock(b, reachable);
247          continue;
248        }
249        SourceLocation c = GetUnreachableLoc(b, R1, R2);
250        if (!c.isValid()) {
251            // Blocks without a location can't produce a warning, so don't mark
252            // reachable blocks from here as live.
253          reachable.set(b.getBlockID());
254          ++numReachable;
255          continue;
256        }
257        lines.push_back(ErrLoc(c, R1, R2));
258          // Avoid excessive errors by marking everything reachable from here
259        numReachable += ScanReachableFromBlock(b, reachable);
260      }
261    }
262  }
263
264  if (numReachable < cfg->getNumBlockIDs()) {
265      // And then give warnings for the tops of loops.
266    for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
267      CFGBlock &b = **I;
268      if (!reachable[b.getBlockID()])
269          // Avoid excessive errors by marking everything reachable from here
270        lines.push_back(ErrLoc(MarkLiveTop(&b, reachable,
271                                         AC.getASTContext().getSourceManager()),
272                               SourceRange(), SourceRange()));
273    }
274  }
275
276  llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp);
277
278  for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end();
279       I != E; ++I)
280    if (I->Loc.isValid())
281      CB.HandleUnreachable(I->Loc, I->R1, I->R2);
282}
283
284}} // end namespace clang::reachable_code
285