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/StmtCXX.h"
20 #include "clang/Analysis/Analyses/ReachableCode.h"
21 #include "clang/Analysis/CFG.h"
22 #include "clang/Analysis/AnalysisContext.h"
23 #include "clang/Basic/SourceManager.h"
24 
25 using namespace clang;
26 
27 static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1,
28                                         SourceRange &R2) {
29   const Stmt *S = 0;
30   unsigned sn = 0;
31   R1 = R2 = SourceRange();
32 
33 top:
34   if (sn < b.size()) {
35     CFGStmt CS = b[sn].getAs<CFGStmt>();
36     if (!CS)
37       goto top;
38 
39     S = CS.getStmt();
40   } else if (b.getTerminator())
41     S = b.getTerminator();
42   else
43     return SourceLocation();
44 
45   switch (S->getStmtClass()) {
46     case Expr::BinaryOperatorClass: {
47       const BinaryOperator *BO = cast<BinaryOperator>(S);
48       if (BO->getOpcode() == BO_Comma) {
49         if (sn+1 < b.size())
50           return b[sn+1].getAs<CFGStmt>().getStmt()->getLocStart();
51         const CFGBlock *n = &b;
52         while (1) {
53           if (n->getTerminator())
54             return n->getTerminator()->getLocStart();
55           if (n->succ_size() != 1)
56             return SourceLocation();
57           n = n[0].succ_begin()[0];
58           if (n->pred_size() != 1)
59             return SourceLocation();
60           if (!n->empty())
61             return n[0][0].getAs<CFGStmt>().getStmt()->getLocStart();
62         }
63       }
64       R1 = BO->getLHS()->getSourceRange();
65       R2 = BO->getRHS()->getSourceRange();
66       return BO->getOperatorLoc();
67     }
68     case Expr::UnaryOperatorClass: {
69       const UnaryOperator *UO = cast<UnaryOperator>(S);
70       R1 = UO->getSubExpr()->getSourceRange();
71       return UO->getOperatorLoc();
72     }
73     case Expr::CompoundAssignOperatorClass: {
74       const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
75       R1 = CAO->getLHS()->getSourceRange();
76       R2 = CAO->getRHS()->getSourceRange();
77       return CAO->getOperatorLoc();
78     }
79     case Expr::ConditionalOperatorClass: {
80       const ConditionalOperator *CO = cast<ConditionalOperator>(S);
81       return CO->getQuestionLoc();
82     }
83     case Expr::MemberExprClass: {
84       const MemberExpr *ME = cast<MemberExpr>(S);
85       R1 = ME->getSourceRange();
86       return ME->getMemberLoc();
87     }
88     case Expr::ArraySubscriptExprClass: {
89       const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
90       R1 = ASE->getLHS()->getSourceRange();
91       R2 = ASE->getRHS()->getSourceRange();
92       return ASE->getRBracketLoc();
93     }
94     case Expr::CStyleCastExprClass: {
95       const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
96       R1 = CSC->getSubExpr()->getSourceRange();
97       return CSC->getLParenLoc();
98     }
99     case Expr::CXXFunctionalCastExprClass: {
100       const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
101       R1 = CE->getSubExpr()->getSourceRange();
102       return CE->getTypeBeginLoc();
103     }
104     case Expr::ImplicitCastExprClass:
105       ++sn;
106       goto top;
107     case Stmt::CXXTryStmtClass: {
108       return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
109     }
110     default: ;
111   }
112   R1 = S->getSourceRange();
113   return S->getLocStart();
114 }
115 
116 static SourceLocation MarkLiveTop(const CFGBlock *Start,
117                                   llvm::BitVector &reachable,
118                                   SourceManager &SM) {
119 
120   // Prep work worklist.
121   llvm::SmallVector<const CFGBlock*, 32> WL;
122   WL.push_back(Start);
123 
124   SourceRange R1, R2;
125   SourceLocation top = GetUnreachableLoc(*Start, R1, R2);
126 
127   bool FromMainFile = false;
128   bool FromSystemHeader = false;
129   bool TopValid = false;
130 
131   if (top.isValid()) {
132     FromMainFile = SM.isFromMainFile(top);
133     FromSystemHeader = SM.isInSystemHeader(top);
134     TopValid = true;
135   }
136 
137   // Solve
138   CFGBlock::FilterOptions FO;
139   FO.IgnoreDefaultsWithCoveredEnums = 1;
140 
141   while (!WL.empty()) {
142     const CFGBlock *item = WL.back();
143     WL.pop_back();
144 
145     SourceLocation c = GetUnreachableLoc(*item, R1, R2);
146     if (c.isValid()
147         && (!TopValid
148             || (SM.isFromMainFile(c) && !FromMainFile)
149             || (FromSystemHeader && !SM.isInSystemHeader(c))
150             || SM.isBeforeInTranslationUnit(c, top))) {
151           top = c;
152           FromMainFile = SM.isFromMainFile(top);
153           FromSystemHeader = SM.isInSystemHeader(top);
154         }
155 
156     reachable.set(item->getBlockID());
157     for (CFGBlock::filtered_succ_iterator I =
158 	   item->filtered_succ_start_end(FO); I.hasMore(); ++I)
159       if (const CFGBlock *B = *I) {
160         unsigned blockID = B->getBlockID();
161         if (!reachable[blockID]) {
162           reachable.set(blockID);
163           WL.push_back(B);
164         }
165       }
166   }
167 
168   return top;
169 }
170 
171 static int LineCmp(const void *p1, const void *p2) {
172   SourceLocation *Line1 = (SourceLocation *)p1;
173   SourceLocation *Line2 = (SourceLocation *)p2;
174   return !(*Line1 < *Line2);
175 }
176 
177 namespace {
178 struct ErrLoc {
179   SourceLocation Loc;
180   SourceRange R1;
181   SourceRange R2;
182   ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2)
183   : Loc(l), R1(r1), R2(r2) { }
184 };
185 }
186 namespace clang { namespace reachable_code {
187 
188 /// ScanReachableFromBlock - Mark all blocks reachable from Start.
189 /// Returns the total number of blocks that were marked reachable.
190 unsigned ScanReachableFromBlock(const CFGBlock &Start,
191                                 llvm::BitVector &Reachable) {
192   unsigned count = 0;
193   llvm::SmallVector<const CFGBlock*, 32> WL;
194 
195     // Prep work queue
196   Reachable.set(Start.getBlockID());
197   ++count;
198   WL.push_back(&Start);
199 
200   // Find the reachable blocks from 'Start'.
201   CFGBlock::FilterOptions FO;
202   FO.IgnoreDefaultsWithCoveredEnums = 1;
203 
204   while (!WL.empty()) {
205     const CFGBlock *item = WL.back();
206     WL.pop_back();
207 
208       // Look at the successors and mark then reachable.
209     for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO);
210          I.hasMore(); ++I)
211       if (const CFGBlock *B = *I) {
212         unsigned blockID = B->getBlockID();
213         if (!Reachable[blockID]) {
214           Reachable.set(blockID);
215           ++count;
216           WL.push_back(B);
217         }
218       }
219   }
220   return count;
221 }
222 
223 void FindUnreachableCode(AnalysisContext &AC, Callback &CB) {
224   CFG *cfg = AC.getCFG();
225   if (!cfg)
226     return;
227 
228   // Scan for reachable blocks.
229   llvm::BitVector reachable(cfg->getNumBlockIDs());
230   unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable);
231 
232     // If there are no unreachable blocks, we're done.
233   if (numReachable == cfg->getNumBlockIDs())
234     return;
235 
236   SourceRange R1, R2;
237 
238   llvm::SmallVector<ErrLoc, 24> lines;
239   bool AddEHEdges = AC.getAddEHEdges();
240 
241   // First, give warnings for blocks with no predecessors, as they
242   // can't be part of a loop.
243   for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
244     CFGBlock &b = **I;
245     if (!reachable[b.getBlockID()]) {
246       if (b.pred_empty()) {
247         if (!AddEHEdges && dyn_cast_or_null<CXXTryStmt>(b.getTerminator())) {
248             // When not adding EH edges from calls, catch clauses
249             // can otherwise seem dead.  Avoid noting them as dead.
250           numReachable += ScanReachableFromBlock(b, reachable);
251           continue;
252         }
253         SourceLocation c = GetUnreachableLoc(b, R1, R2);
254         if (!c.isValid()) {
255             // Blocks without a location can't produce a warning, so don't mark
256             // reachable blocks from here as live.
257           reachable.set(b.getBlockID());
258           ++numReachable;
259           continue;
260         }
261         lines.push_back(ErrLoc(c, R1, R2));
262           // Avoid excessive errors by marking everything reachable from here
263         numReachable += ScanReachableFromBlock(b, reachable);
264       }
265     }
266   }
267 
268   if (numReachable < cfg->getNumBlockIDs()) {
269       // And then give warnings for the tops of loops.
270     for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
271       CFGBlock &b = **I;
272       if (!reachable[b.getBlockID()])
273           // Avoid excessive errors by marking everything reachable from here
274         lines.push_back(ErrLoc(MarkLiveTop(&b, reachable,
275                                          AC.getASTContext().getSourceManager()),
276                                SourceRange(), SourceRange()));
277     }
278   }
279 
280   llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp);
281 
282   for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end();
283        I != E; ++I)
284     if (I->Loc.isValid())
285       CB.HandleUnreachable(I->Loc, I->R1, I->R2);
286 }
287 
288 }} // end namespace clang::reachable_code
289