blob: a2d19c0508295cd5aa8b74ef2dc7ec802cc3c8f0 [file] [log] [blame]
Ted Kremenek3d2eed82010-02-23 02:39:16 +00001//=- 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
Chandler Carruth55fc8732012-12-04 09:13:33 +000015#include "clang/Analysis/Analyses/ReachableCode.h"
Ted Kremenek72919a32010-02-23 05:59:20 +000016#include "clang/AST/Expr.h"
17#include "clang/AST/ExprCXX.h"
John McCallf85e1932011-06-15 23:02:42 +000018#include "clang/AST/ExprObjC.h"
Ted Kremenek72919a32010-02-23 05:59:20 +000019#include "clang/AST/StmtCXX.h"
Ted Kremenek72919a32010-02-23 05:59:20 +000020#include "clang/Analysis/AnalysisContext.h"
Chandler Carruth55fc8732012-12-04 09:13:33 +000021#include "clang/Analysis/CFG.h"
Ted Kremenek72919a32010-02-23 05:59:20 +000022#include "clang/Basic/SourceManager.h"
Chandler Carruth55fc8732012-12-04 09:13:33 +000023#include "llvm/ADT/BitVector.h"
24#include "llvm/ADT/SmallVector.h"
Ted Kremenek3d2eed82010-02-23 02:39:16 +000025
26using namespace clang;
27
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000028namespace {
29class DeadCodeScan {
30 llvm::BitVector Visited;
31 llvm::BitVector &Reachable;
Dmitri Gribenkocfa88f82013-01-12 19:30:44 +000032 SmallVector<const CFGBlock *, 10> WorkList;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000033
Dmitri Gribenkocfa88f82013-01-12 19:30:44 +000034 typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000035 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) {
Ted Kremeneke7a27642011-08-25 19:28:55 +000089 if (S->getLocStart().isInvalid())
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000090 return false;
Ted Kremeneke7a27642011-08-25 19:28:55 +000091 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000092 return BO->getOpcode() != BO_Comma;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +000093 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)
David Blaikieb0780542013-02-23 00:29:34 +000098 if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
99 const Stmt *S = CS->getStmt();
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000100 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
Benjamin Kramer767b3d22013-09-22 14:10:29 +0000113static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
114 const std::pair<const CFGBlock *, const Stmt *> *p2) {
Benjamin Kramer4124c7a2013-09-22 15:02:02 +0000115 if (p1->second->getLocStart() < p2->second->getLocStart())
116 return -1;
117 if (p2->second->getLocStart() < p1->second->getLocStart())
118 return 1;
119 return 0;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000120}
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 }
Ted Kremeneke7a27642011-08-25 19:28:55 +0000148
149 // Specially handle macro-expanded code.
150 if (S->getLocStart().isMacroID()) {
151 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
152 continue;
153 }
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000154
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,
Ted Kremenek72919a32010-02-23 05:59:20 +0000186 SourceRange &R2) {
Ted Kremenek72919a32010-02-23 05:59:20 +0000187 R1 = R2 = SourceRange();
188
Ted Kremenek892697d2010-12-16 07:46:53 +0000189 if (const Expr *Ex = dyn_cast<Expr>(S))
190 S = Ex->IgnoreParenImpCasts();
191
Ted Kremenek72919a32010-02-23 05:59:20 +0000192 switch (S->getStmtClass()) {
193 case Expr::BinaryOperatorClass: {
194 const BinaryOperator *BO = cast<BinaryOperator>(S);
Ted Kremenek72919a32010-02-23 05:59:20 +0000195 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 }
John McCall56ca35d2011-02-17 10:25:35 +0000208 case Expr::BinaryConditionalOperatorClass:
Ted Kremenek72919a32010-02-23 05:59:20 +0000209 case Expr::ConditionalOperatorClass: {
John McCall56ca35d2011-02-17 10:25:35 +0000210 const AbstractConditionalOperator *CO =
211 cast<AbstractConditionalOperator>(S);
Ted Kremenek72919a32010-02-23 05:59:20 +0000212 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();
Eli Friedmancdd4b782013-08-15 22:02:56 +0000233 return CE->getLocStart();
Ted Kremenek72919a32010-02-23 05:59:20 +0000234 }
Ted Kremenek72919a32010-02-23 05:59:20 +0000235 case Stmt::CXXTryStmtClass: {
236 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
237 }
John McCallf85e1932011-06-15 23:02:42 +0000238 case Expr::ObjCBridgedCastExprClass: {
239 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
240 R1 = CSC->getSubExpr()->getSourceRange();
241 return CSC->getLParenLoc();
242 }
Ted Kremenek72919a32010-02-23 05:59:20 +0000243 default: ;
244 }
245 R1 = S->getSourceRange();
246 return S->getLocStart();
247}
248
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000249void DeadCodeScan::reportDeadCode(const Stmt *S,
250 clang::reachable_code::Callback &CB) {
Ted Kremenek72919a32010-02-23 05:59:20 +0000251 SourceRange R1, R2;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000252 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
253 CB.HandleUnreachable(Loc, R1, R2);
Ted Kremenek72919a32010-02-23 05:59:20 +0000254}
255
Ted Kremenek72919a32010-02-23 05:59:20 +0000256namespace clang { namespace reachable_code {
David Blaikie99ba9e32011-12-20 02:48:34 +0000257
258void Callback::anchor() { }
259
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000260unsigned ScanReachableFromBlock(const CFGBlock *Start,
Ted Kremenek72919a32010-02-23 05:59:20 +0000261 llvm::BitVector &Reachable) {
262 unsigned count = 0;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000263
Nico Weber21669482011-04-02 19:45:15 +0000264 // Prep work queue
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000265 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
Ted Kremenek8caec842010-09-09 00:06:10 +0000276 // Find the reachable blocks from 'Start'.
Ted Kremenek72919a32010-02-23 05:59:20 +0000277 while (!WL.empty()) {
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000278 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)
Ted Kremenek3d2eed82010-02-23 02:39:16 +0000283 if (const CFGBlock *B = *I) {
284 unsigned blockID = B->getBlockID();
285 if (!Reachable[blockID]) {
286 Reachable.set(blockID);
Ted Kremenek3d2eed82010-02-23 02:39:16 +0000287 WL.push_back(B);
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000288 ++count;
Ted Kremenek3d2eed82010-02-23 02:39:16 +0000289 }
290 }
291 }
292 return count;
293}
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000294
Ted Kremenek1d26f482011-10-24 01:32:45 +0000295void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
Ted Kremenek72919a32010-02-23 05:59:20 +0000296 CFG *cfg = AC.getCFG();
297 if (!cfg)
298 return;
299
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000300 // Scan for reachable blocks from the entrance of the CFG.
301 // If there are no unreachable blocks, we're done.
Ted Kremenek72919a32010-02-23 05:59:20 +0000302 llvm::BitVector reachable(cfg->getNumBlockIDs());
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000303 unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
Ted Kremenek72919a32010-02-23 05:59:20 +0000304 if (numReachable == cfg->getNumBlockIDs())
305 return;
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000306
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 }
Ted Kremenek72919a32010-02-23 05:59:20 +0000317
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000318 // There are some unreachable blocks. We need to find the root blocks that
319 // contain code that should be considered unreachable.
Ted Kremenek72919a32010-02-23 05:59:20 +0000320 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
Ted Kremenek0f3b4ca2011-08-23 23:05:11 +0000321 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;
Ted Kremenek72919a32010-02-23 05:59:20 +0000331 }
Ted Kremenek72919a32010-02-23 05:59:20 +0000332}
333
334}} // end namespace clang::reachable_code