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