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
26 using namespace clang;
27
28 namespace {
29 class 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
39 public:
DeadCodeScan(llvm::BitVector & reachable)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
enqueue(const CFGBlock * block)57 void 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
isDeadCodeRoot(const clang::CFGBlock * Block)65 bool 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
isValidDeadStmt(const Stmt * S)88 static 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
findDeadCode(const clang::CFGBlock * Block)96 const 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
SrcCmp(const void * p1,const void * p2)113 static int SrcCmp(const void *p1, const void *p2) {
114 return
115 ((const std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() <
116 ((const std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart();
117 }
118
scanBackwards(const clang::CFGBlock * Start,clang::reachable_code::Callback & CB)119 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
120 clang::reachable_code::Callback &CB) {
121
122 unsigned count = 0;
123 enqueue(Start);
124
125 while (!WorkList.empty()) {
126 const CFGBlock *Block = WorkList.pop_back_val();
127
128 // It is possible that this block has been marked reachable after
129 // it was enqueued.
130 if (Reachable[Block->getBlockID()])
131 continue;
132
133 // Look for any dead code within the block.
134 const Stmt *S = findDeadCode(Block);
135
136 if (!S) {
137 // No dead code. Possibly an empty block. Look at dead predecessors.
138 for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
139 E = Block->pred_end(); I != E; ++I) {
140 if (const CFGBlock *predBlock = *I)
141 enqueue(predBlock);
142 }
143 continue;
144 }
145
146 // Specially handle macro-expanded code.
147 if (S->getLocStart().isMacroID()) {
148 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
149 continue;
150 }
151
152 if (isDeadCodeRoot(Block)) {
153 reportDeadCode(S, CB);
154 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
155 }
156 else {
157 // Record this statement as the possibly best location in a
158 // strongly-connected component of dead code for emitting a
159 // warning.
160 DeferredLocs.push_back(std::make_pair(Block, S));
161 }
162 }
163
164 // If we didn't find a dead root, then report the dead code with the
165 // earliest location.
166 if (!DeferredLocs.empty()) {
167 llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
168 for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
169 E = DeferredLocs.end(); I != E; ++I) {
170 const CFGBlock *block = I->first;
171 if (Reachable[block->getBlockID()])
172 continue;
173 reportDeadCode(I->second, CB);
174 count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
175 }
176 }
177
178 return count;
179 }
180
GetUnreachableLoc(const Stmt * S,SourceRange & R1,SourceRange & R2)181 static SourceLocation GetUnreachableLoc(const Stmt *S,
182 SourceRange &R1,
183 SourceRange &R2) {
184 R1 = R2 = SourceRange();
185
186 if (const Expr *Ex = dyn_cast<Expr>(S))
187 S = Ex->IgnoreParenImpCasts();
188
189 switch (S->getStmtClass()) {
190 case Expr::BinaryOperatorClass: {
191 const BinaryOperator *BO = cast<BinaryOperator>(S);
192 return BO->getOperatorLoc();
193 }
194 case Expr::UnaryOperatorClass: {
195 const UnaryOperator *UO = cast<UnaryOperator>(S);
196 R1 = UO->getSubExpr()->getSourceRange();
197 return UO->getOperatorLoc();
198 }
199 case Expr::CompoundAssignOperatorClass: {
200 const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
201 R1 = CAO->getLHS()->getSourceRange();
202 R2 = CAO->getRHS()->getSourceRange();
203 return CAO->getOperatorLoc();
204 }
205 case Expr::BinaryConditionalOperatorClass:
206 case Expr::ConditionalOperatorClass: {
207 const AbstractConditionalOperator *CO =
208 cast<AbstractConditionalOperator>(S);
209 return CO->getQuestionLoc();
210 }
211 case Expr::MemberExprClass: {
212 const MemberExpr *ME = cast<MemberExpr>(S);
213 R1 = ME->getSourceRange();
214 return ME->getMemberLoc();
215 }
216 case Expr::ArraySubscriptExprClass: {
217 const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
218 R1 = ASE->getLHS()->getSourceRange();
219 R2 = ASE->getRHS()->getSourceRange();
220 return ASE->getRBracketLoc();
221 }
222 case Expr::CStyleCastExprClass: {
223 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
224 R1 = CSC->getSubExpr()->getSourceRange();
225 return CSC->getLParenLoc();
226 }
227 case Expr::CXXFunctionalCastExprClass: {
228 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
229 R1 = CE->getSubExpr()->getSourceRange();
230 return CE->getTypeBeginLoc();
231 }
232 case Stmt::CXXTryStmtClass: {
233 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
234 }
235 case Expr::ObjCBridgedCastExprClass: {
236 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
237 R1 = CSC->getSubExpr()->getSourceRange();
238 return CSC->getLParenLoc();
239 }
240 default: ;
241 }
242 R1 = S->getSourceRange();
243 return S->getLocStart();
244 }
245
reportDeadCode(const Stmt * S,clang::reachable_code::Callback & CB)246 void DeadCodeScan::reportDeadCode(const Stmt *S,
247 clang::reachable_code::Callback &CB) {
248 SourceRange R1, R2;
249 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
250 CB.HandleUnreachable(Loc, R1, R2);
251 }
252
253 namespace clang { namespace reachable_code {
254
anchor()255 void Callback::anchor() { }
256
ScanReachableFromBlock(const CFGBlock * Start,llvm::BitVector & Reachable)257 unsigned ScanReachableFromBlock(const CFGBlock *Start,
258 llvm::BitVector &Reachable) {
259 unsigned count = 0;
260
261 // Prep work queue
262 SmallVector<const CFGBlock*, 32> WL;
263
264 // The entry block may have already been marked reachable
265 // by the caller.
266 if (!Reachable[Start->getBlockID()]) {
267 ++count;
268 Reachable[Start->getBlockID()] = true;
269 }
270
271 WL.push_back(Start);
272
273 // Find the reachable blocks from 'Start'.
274 while (!WL.empty()) {
275 const CFGBlock *item = WL.pop_back_val();
276
277 // Look at the successors and mark then reachable.
278 for (CFGBlock::const_succ_iterator I = item->succ_begin(),
279 E = item->succ_end(); I != E; ++I)
280 if (const CFGBlock *B = *I) {
281 unsigned blockID = B->getBlockID();
282 if (!Reachable[blockID]) {
283 Reachable.set(blockID);
284 WL.push_back(B);
285 ++count;
286 }
287 }
288 }
289 return count;
290 }
291
FindUnreachableCode(AnalysisDeclContext & AC,Callback & CB)292 void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
293 CFG *cfg = AC.getCFG();
294 if (!cfg)
295 return;
296
297 // Scan for reachable blocks from the entrance of the CFG.
298 // If there are no unreachable blocks, we're done.
299 llvm::BitVector reachable(cfg->getNumBlockIDs());
300 unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
301 if (numReachable == cfg->getNumBlockIDs())
302 return;
303
304 // If there aren't explicit EH edges, we should include the 'try' dispatch
305 // blocks as roots.
306 if (!AC.getCFGBuildOptions().AddEHEdges) {
307 for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
308 E = cfg->try_blocks_end() ; I != E; ++I) {
309 numReachable += ScanReachableFromBlock(*I, reachable);
310 }
311 if (numReachable == cfg->getNumBlockIDs())
312 return;
313 }
314
315 // There are some unreachable blocks. We need to find the root blocks that
316 // contain code that should be considered unreachable.
317 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
318 const CFGBlock *block = *I;
319 // A block may have been marked reachable during this loop.
320 if (reachable[block->getBlockID()])
321 continue;
322
323 DeadCodeScan DS(reachable);
324 numReachable += DS.scanBackwards(block, CB);
325
326 if (numReachable == cfg->getNumBlockIDs())
327 return;
328 }
329 }
330
331 }} // end namespace clang::reachable_code
332