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