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 "clang/Analysis/Analyses/ReachableCode.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/ExprCXX.h"
18#include "clang/AST/ExprObjC.h"
19#include "clang/AST/StmtCXX.h"
20#include "clang/Analysis/AnalysisContext.h"
21#include "clang/Analysis/CFG.h"
22#include "clang/Basic/SourceManager.h"
23#include "llvm/ADT/BitVector.h"
24#include "llvm/ADT/SmallVector.h"
25
26using namespace clang;
27
28namespace {
29class DeadCodeScan {
30  llvm::BitVector Visited;
31  llvm::BitVector &Reachable;
32  SmallVector<const CFGBlock *, 10> WorkList;
33
34  typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
35      DeferredLocsTy;
36
37  DeferredLocsTy DeferredLocs;
38
39public:
40  DeadCodeScan(llvm::BitVector &reachable)
41    : Visited(reachable.size()),
42      Reachable(reachable) {}
43
44  void enqueue(const CFGBlock *block);
45  unsigned scanBackwards(const CFGBlock *Start,
46                         clang::reachable_code::Callback &CB);
47
48  bool isDeadCodeRoot(const CFGBlock *Block);
49
50  const Stmt *findDeadCode(const CFGBlock *Block);
51
52  void reportDeadCode(const Stmt *S,
53                      clang::reachable_code::Callback &CB);
54};
55}
56
57void DeadCodeScan::enqueue(const CFGBlock *block) {
58  unsigned blockID = block->getBlockID();
59  if (Reachable[blockID] || Visited[blockID])
60    return;
61  Visited[blockID] = true;
62  WorkList.push_back(block);
63}
64
65bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
66  bool isDeadRoot = true;
67
68  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
69        E = Block->pred_end(); I != E; ++I) {
70    if (const CFGBlock *PredBlock = *I) {
71      unsigned blockID = PredBlock->getBlockID();
72      if (Visited[blockID]) {
73        isDeadRoot = false;
74        continue;
75      }
76      if (!Reachable[blockID]) {
77        isDeadRoot = false;
78        Visited[blockID] = true;
79        WorkList.push_back(PredBlock);
80        continue;
81      }
82    }
83  }
84
85  return isDeadRoot;
86}
87
88static bool isValidDeadStmt(const Stmt *S) {
89  if (S->getLocStart().isInvalid())
90    return false;
91  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
92    return BO->getOpcode() != BO_Comma;
93  return true;
94}
95
96const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
97  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
98    if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
99      const Stmt *S = CS->getStmt();
100      if (isValidDeadStmt(S))
101        return S;
102    }
103
104  if (CFGTerminator T = Block->getTerminator()) {
105    const Stmt *S = T.getStmt();
106    if (isValidDeadStmt(S))
107      return S;
108  }
109
110  return 0;
111}
112
113static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
114                  const std::pair<const CFGBlock *, const Stmt *> *p2) {
115  if (p1->second->getLocStart() < p2->second->getLocStart())
116    return -1;
117  if (p2->second->getLocStart() < p1->second->getLocStart())
118    return 1;
119  return 0;
120}
121
122unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
123                                     clang::reachable_code::Callback &CB) {
124
125  unsigned count = 0;
126  enqueue(Start);
127
128  while (!WorkList.empty()) {
129    const CFGBlock *Block = WorkList.pop_back_val();
130
131    // It is possible that this block has been marked reachable after
132    // it was enqueued.
133    if (Reachable[Block->getBlockID()])
134      continue;
135
136    // Look for any dead code within the block.
137    const Stmt *S = findDeadCode(Block);
138
139    if (!S) {
140      // No dead code.  Possibly an empty block.  Look at dead predecessors.
141      for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
142           E = Block->pred_end(); I != E; ++I) {
143        if (const CFGBlock *predBlock = *I)
144          enqueue(predBlock);
145      }
146      continue;
147    }
148
149    // Specially handle macro-expanded code.
150    if (S->getLocStart().isMacroID()) {
151      count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
152      continue;
153    }
154
155    if (isDeadCodeRoot(Block)) {
156      reportDeadCode(S, CB);
157      count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
158    }
159    else {
160      // Record this statement as the possibly best location in a
161      // strongly-connected component of dead code for emitting a
162      // warning.
163      DeferredLocs.push_back(std::make_pair(Block, S));
164    }
165  }
166
167  // If we didn't find a dead root, then report the dead code with the
168  // earliest location.
169  if (!DeferredLocs.empty()) {
170    llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
171    for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
172          E = DeferredLocs.end(); I != E; ++I) {
173      const CFGBlock *block = I->first;
174      if (Reachable[block->getBlockID()])
175        continue;
176      reportDeadCode(I->second, CB);
177      count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
178    }
179  }
180
181  return count;
182}
183
184static SourceLocation GetUnreachableLoc(const Stmt *S,
185                                        SourceRange &R1,
186                                        SourceRange &R2) {
187  R1 = R2 = SourceRange();
188
189  if (const Expr *Ex = dyn_cast<Expr>(S))
190    S = Ex->IgnoreParenImpCasts();
191
192  switch (S->getStmtClass()) {
193    case Expr::BinaryOperatorClass: {
194      const BinaryOperator *BO = cast<BinaryOperator>(S);
195      return BO->getOperatorLoc();
196    }
197    case Expr::UnaryOperatorClass: {
198      const UnaryOperator *UO = cast<UnaryOperator>(S);
199      R1 = UO->getSubExpr()->getSourceRange();
200      return UO->getOperatorLoc();
201    }
202    case Expr::CompoundAssignOperatorClass: {
203      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
204      R1 = CAO->getLHS()->getSourceRange();
205      R2 = CAO->getRHS()->getSourceRange();
206      return CAO->getOperatorLoc();
207    }
208    case Expr::BinaryConditionalOperatorClass:
209    case Expr::ConditionalOperatorClass: {
210      const AbstractConditionalOperator *CO =
211        cast<AbstractConditionalOperator>(S);
212      return CO->getQuestionLoc();
213    }
214    case Expr::MemberExprClass: {
215      const MemberExpr *ME = cast<MemberExpr>(S);
216      R1 = ME->getSourceRange();
217      return ME->getMemberLoc();
218    }
219    case Expr::ArraySubscriptExprClass: {
220      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
221      R1 = ASE->getLHS()->getSourceRange();
222      R2 = ASE->getRHS()->getSourceRange();
223      return ASE->getRBracketLoc();
224    }
225    case Expr::CStyleCastExprClass: {
226      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
227      R1 = CSC->getSubExpr()->getSourceRange();
228      return CSC->getLParenLoc();
229    }
230    case Expr::CXXFunctionalCastExprClass: {
231      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
232      R1 = CE->getSubExpr()->getSourceRange();
233      return CE->getLocStart();
234    }
235    case Stmt::CXXTryStmtClass: {
236      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
237    }
238    case Expr::ObjCBridgedCastExprClass: {
239      const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
240      R1 = CSC->getSubExpr()->getSourceRange();
241      return CSC->getLParenLoc();
242    }
243    default: ;
244  }
245  R1 = S->getSourceRange();
246  return S->getLocStart();
247}
248
249void DeadCodeScan::reportDeadCode(const Stmt *S,
250                                  clang::reachable_code::Callback &CB) {
251  SourceRange R1, R2;
252  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
253  CB.HandleUnreachable(Loc, R1, R2);
254}
255
256namespace clang { namespace reachable_code {
257
258void Callback::anchor() { }
259
260unsigned ScanReachableFromBlock(const CFGBlock *Start,
261                                llvm::BitVector &Reachable) {
262  unsigned count = 0;
263
264  // Prep work queue
265  SmallVector<const CFGBlock*, 32> WL;
266
267  // The entry block may have already been marked reachable
268  // by the caller.
269  if (!Reachable[Start->getBlockID()]) {
270    ++count;
271    Reachable[Start->getBlockID()] = true;
272  }
273
274  WL.push_back(Start);
275
276  // Find the reachable blocks from 'Start'.
277  while (!WL.empty()) {
278    const CFGBlock *item = WL.pop_back_val();
279
280    // Look at the successors and mark then reachable.
281    for (CFGBlock::const_succ_iterator I = item->succ_begin(),
282         E = item->succ_end(); I != E; ++I)
283      if (const CFGBlock *B = *I) {
284        unsigned blockID = B->getBlockID();
285        if (!Reachable[blockID]) {
286          Reachable.set(blockID);
287          WL.push_back(B);
288          ++count;
289        }
290      }
291  }
292  return count;
293}
294
295void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
296  CFG *cfg = AC.getCFG();
297  if (!cfg)
298    return;
299
300  // Scan for reachable blocks from the entrance of the CFG.
301  // If there are no unreachable blocks, we're done.
302  llvm::BitVector reachable(cfg->getNumBlockIDs());
303  unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
304  if (numReachable == cfg->getNumBlockIDs())
305    return;
306
307  // If there aren't explicit EH edges, we should include the 'try' dispatch
308  // blocks as roots.
309  if (!AC.getCFGBuildOptions().AddEHEdges) {
310    for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
311         E = cfg->try_blocks_end() ; I != E; ++I) {
312      numReachable += ScanReachableFromBlock(*I, reachable);
313    }
314    if (numReachable == cfg->getNumBlockIDs())
315      return;
316  }
317
318  // There are some unreachable blocks.  We need to find the root blocks that
319  // contain code that should be considered unreachable.
320  for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
321    const CFGBlock *block = *I;
322    // A block may have been marked reachable during this loop.
323    if (reachable[block->getBlockID()])
324      continue;
325
326    DeadCodeScan DS(reachable);
327    numReachable += DS.scanBackwards(block, CB);
328
329    if (numReachable == cfg->getNumBlockIDs())
330      return;
331  }
332}
333
334}} // end namespace clang::reachable_code
335