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