ReachableCode.cpp revision 4ba72a0b28135209c435630682febe1f854ccfa6 
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    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  switch (S->getStmtClass()) {
46    case Expr::BinaryOperatorClass: {
47      const BinaryOperator *BO = cast<BinaryOperator>(S);
48      if (BO->getOpcode() == BO_Comma) {
49        if (sn+1 < b.size())
50          return b[sn+1].getAs<CFGStmt>().getStmt()->getLocStart();
51        const CFGBlock *n = &b;
52        while (1) {
53          if (n->getTerminator())
54            return n->getTerminator()->getLocStart();
55          if (n->succ_size() != 1)
56            return SourceLocation();
57          n = n[0].succ_begin()[0];
58          if (n->pred_size() != 1)
59            return SourceLocation();
60          if (!n->empty())
61            return n[0][0].getAs<CFGStmt>().getStmt()->getLocStart();
62        }
63      }
64      R1 = BO->getLHS()->getSourceRange();
65      R2 = BO->getRHS()->getSourceRange();
66      return BO->getOperatorLoc();
67    }
68    case Expr::UnaryOperatorClass: {
69      const UnaryOperator *UO = cast<UnaryOperator>(S);
70      R1 = UO->getSubExpr()->getSourceRange();
71      return UO->getOperatorLoc();
72    }
73    case Expr::CompoundAssignOperatorClass: {
74      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
75      R1 = CAO->getLHS()->getSourceRange();
76      R2 = CAO->getRHS()->getSourceRange();
77      return CAO->getOperatorLoc();
78    }
79    case Expr::ConditionalOperatorClass: {
80      const ConditionalOperator *CO = cast<ConditionalOperator>(S);
81      return CO->getQuestionLoc();
82    }
83    case Expr::MemberExprClass: {
84      const MemberExpr *ME = cast<MemberExpr>(S);
85      R1 = ME->getSourceRange();
86      return ME->getMemberLoc();
87    }
88    case Expr::ArraySubscriptExprClass: {
89      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
90      R1 = ASE->getLHS()->getSourceRange();
91      R2 = ASE->getRHS()->getSourceRange();
92      return ASE->getRBracketLoc();
93    }
94    case Expr::CStyleCastExprClass: {
95      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
96      R1 = CSC->getSubExpr()->getSourceRange();
97      return CSC->getLParenLoc();
98    }
99    case Expr::CXXFunctionalCastExprClass: {
100      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
101      R1 = CE->getSubExpr()->getSourceRange();
102      return CE->getTypeBeginLoc();
103    }
104    case Expr::ImplicitCastExprClass:
105      ++sn;
106      goto top;
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
116static 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
171static int LineCmp(const void *p1, const void *p2) {
172  SourceLocation *Line1 = (SourceLocation *)p1;
173  SourceLocation *Line2 = (SourceLocation *)p2;
174  return !(*Line1 < *Line2);
175}
176
177namespace {
178struct 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}
186namespace clang { namespace reachable_code {
187
188/// ScanReachableFromBlock - Mark all blocks reachable from Start.
189/// Returns the total number of blocks that were marked reachable.
190unsigned 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
223void 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
290