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