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