1 //=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a flow-sensitive, path-insensitive analysis of
11 // determining reachable blocks within a CFG.
13 //===----------------------------------------------------------------------===//
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"
26 using namespace clang;
30 llvm::BitVector Visited;
31 llvm::BitVector &Reachable;
32 SmallVector<const CFGBlock *, 10> WorkList;
34 typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
37 DeferredLocsTy DeferredLocs;
40 DeadCodeScan(llvm::BitVector &reachable)
41 : Visited(reachable.size()),
42 Reachable(reachable) {}
44 void enqueue(const CFGBlock *block);
45 unsigned scanBackwards(const CFGBlock *Start,
46 clang::reachable_code::Callback &CB);
48 bool isDeadCodeRoot(const CFGBlock *Block);
50 const Stmt *findDeadCode(const CFGBlock *Block);
52 void reportDeadCode(const Stmt *S,
53 clang::reachable_code::Callback &CB);
57 void DeadCodeScan::enqueue(const CFGBlock *block) {
58 unsigned blockID = block->getBlockID();
59 if (Reachable[blockID] || Visited[blockID])
61 Visited[blockID] = true;
62 WorkList.push_back(block);
65 bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
66 bool isDeadRoot = true;
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]) {
76 if (!Reachable[blockID]) {
78 Visited[blockID] = true;
79 WorkList.push_back(PredBlock);
88 static bool isValidDeadStmt(const Stmt *S) {
89 if (S->getLocStart().isInvalid())
91 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
92 return BO->getOpcode() != BO_Comma;
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))
104 if (CFGTerminator T = Block->getTerminator()) {
105 const Stmt *S = T.getStmt();
106 if (isValidDeadStmt(S))
113 static int SrcCmp(const void *p1, const void *p2) {
115 ((const std::pair<const CFGBlock *, const Stmt *>*) p2)->second->getLocStart() <
116 ((const std::pair<const CFGBlock *, const Stmt *>*) p1)->second->getLocStart();
119 unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
120 clang::reachable_code::Callback &CB) {
125 while (!WorkList.empty()) {
126 const CFGBlock *Block = WorkList.pop_back_val();
128 // It is possible that this block has been marked reachable after
130 if (Reachable[Block->getBlockID()])
133 // Look for any dead code within the block.
134 const Stmt *S = findDeadCode(Block);
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)
146 // Specially handle macro-expanded code.
147 if (S->getLocStart().isMacroID()) {
148 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
152 if (isDeadCodeRoot(Block)) {
153 reportDeadCode(S, CB);
154 count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
157 // Record this statement as the possibly best location in a
158 // strongly-connected component of dead code for emitting a
160 DeferredLocs.push_back(std::make_pair(Block, S));
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()])
173 reportDeadCode(I->second, CB);
174 count += clang::reachable_code::ScanReachableFromBlock(block, Reachable);
181 static SourceLocation GetUnreachableLoc(const Stmt *S,
184 R1 = R2 = SourceRange();
186 if (const Expr *Ex = dyn_cast<Expr>(S))
187 S = Ex->IgnoreParenImpCasts();
189 switch (S->getStmtClass()) {
190 case Expr::BinaryOperatorClass: {
191 const BinaryOperator *BO = cast<BinaryOperator>(S);
192 return BO->getOperatorLoc();
194 case Expr::UnaryOperatorClass: {
195 const UnaryOperator *UO = cast<UnaryOperator>(S);
196 R1 = UO->getSubExpr()->getSourceRange();
197 return UO->getOperatorLoc();
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();
205 case Expr::BinaryConditionalOperatorClass:
206 case Expr::ConditionalOperatorClass: {
207 const AbstractConditionalOperator *CO =
208 cast<AbstractConditionalOperator>(S);
209 return CO->getQuestionLoc();
211 case Expr::MemberExprClass: {
212 const MemberExpr *ME = cast<MemberExpr>(S);
213 R1 = ME->getSourceRange();
214 return ME->getMemberLoc();
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();
222 case Expr::CStyleCastExprClass: {
223 const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
224 R1 = CSC->getSubExpr()->getSourceRange();
225 return CSC->getLParenLoc();
227 case Expr::CXXFunctionalCastExprClass: {
228 const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
229 R1 = CE->getSubExpr()->getSourceRange();
230 return CE->getTypeBeginLoc();
232 case Stmt::CXXTryStmtClass: {
233 return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
235 case Expr::ObjCBridgedCastExprClass: {
236 const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
237 R1 = CSC->getSubExpr()->getSourceRange();
238 return CSC->getLParenLoc();
242 R1 = S->getSourceRange();
243 return S->getLocStart();
246 void DeadCodeScan::reportDeadCode(const Stmt *S,
247 clang::reachable_code::Callback &CB) {
249 SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
250 CB.HandleUnreachable(Loc, R1, R2);
253 namespace clang { namespace reachable_code {
255 void Callback::anchor() { }
257 unsigned ScanReachableFromBlock(const CFGBlock *Start,
258 llvm::BitVector &Reachable) {
262 SmallVector<const CFGBlock*, 32> WL;
264 // The entry block may have already been marked reachable
266 if (!Reachable[Start->getBlockID()]) {
268 Reachable[Start->getBlockID()] = true;
273 // Find the reachable blocks from 'Start'.
274 while (!WL.empty()) {
275 const CFGBlock *item = WL.pop_back_val();
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);
292 void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
293 CFG *cfg = AC.getCFG();
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())
304 // If there aren't explicit EH edges, we should include the 'try' dispatch
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);
311 if (numReachable == cfg->getNumBlockIDs())
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()])
323 DeadCodeScan DS(reachable);
324 numReachable += DS.scanBackwards(block, CB);
326 if (numReachable == cfg->getNumBlockIDs())
331 }} // end namespace clang::reachable_code