• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
26 using namespace clang;
27 
GetUnreachableLoc(const CFGBlock & b,SourceRange & R1,SourceRange & R2)28 static 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 
MarkLiveTop(const CFGBlock * Start,llvm::BitVector & reachable,SourceManager & SM)123 static SourceLocation MarkLiveTop(const CFGBlock *Start,
124                                   llvm::BitVector &reachable,
125                                   SourceManager &SM) {
126 
127   // Prep work worklist.
128   llvm::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 
LineCmp(const void * p1,const void * p2)178 static int LineCmp(const void *p1, const void *p2) {
179   SourceLocation *Line1 = (SourceLocation *)p1;
180   SourceLocation *Line2 = (SourceLocation *)p2;
181   return !(*Line1 < *Line2);
182 }
183 
184 namespace {
185 struct ErrLoc {
186   SourceLocation Loc;
187   SourceRange R1;
188   SourceRange R2;
ErrLoc__anonb5af8de40111::ErrLoc189   ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2)
190   : Loc(l), R1(r1), R2(r2) { }
191 };
192 }
193 namespace clang { namespace reachable_code {
194 
195 /// ScanReachableFromBlock - Mark all blocks reachable from Start.
196 /// Returns the total number of blocks that were marked reachable.
ScanReachableFromBlock(const CFGBlock & Start,llvm::BitVector & Reachable)197 unsigned ScanReachableFromBlock(const CFGBlock &Start,
198                                 llvm::BitVector &Reachable) {
199   unsigned count = 0;
200   llvm::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 
FindUnreachableCode(AnalysisContext & AC,Callback & CB)230 void 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   llvm::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 (llvm::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