Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/Analysis/ReachableCode.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- ReachableCode.cpp - Code Reachability Analysis --------------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements a flow-sensitive, path-insensitive analysis of
10
// determining reachable blocks within a CFG.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/Analysis/Analyses/ReachableCode.h"
15
#include "clang/AST/Expr.h"
16
#include "clang/AST/ExprCXX.h"
17
#include "clang/AST/ExprObjC.h"
18
#include "clang/AST/ParentMap.h"
19
#include "clang/AST/StmtCXX.h"
20
#include "clang/Analysis/AnalysisDeclContext.h"
21
#include "clang/Analysis/CFG.h"
22
#include "clang/Basic/SourceManager.h"
23
#include "clang/Lex/Preprocessor.h"
24
#include "llvm/ADT/BitVector.h"
25
#include "llvm/ADT/SmallVector.h"
26
27
using namespace clang;
28
29
//===----------------------------------------------------------------------===//
30
// Core Reachability Analysis routines.
31
//===----------------------------------------------------------------------===//
32
33
0
static bool isEnumConstant(const Expr *Ex) {
34
0
  const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
35
0
  if (!DR)
36
0
    return false;
37
0
  return isa<EnumConstantDecl>(DR->getDecl());
38
0
}
39
40
3
static bool isTrivialExpression(const Expr *Ex) {
41
3
  Ex = Ex->IgnoreParenCasts();
42
3
  return isa<IntegerLiteral>(Ex) || 
isa<StringLiteral>(Ex)0
||
43
3
         
isa<CXXBoolLiteralExpr>(Ex)0
||
isa<ObjCBoolLiteralExpr>(Ex)0
||
44
3
         
isa<CharacterLiteral>(Ex)0
||
45
3
         
isEnumConstant(Ex)0
;
46
3
}
47
48
170
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
49
170
  // Check if the block ends with a do...while() and see if 'S' is the
50
170
  // condition.
51
170
  if (const Stmt *Term = B->getTerminatorStmt()) {
52
29
    if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
53
5
      const Expr *Cond = DS->getCond()->IgnoreParenCasts();
54
5
      return Cond == S && 
isTrivialExpression(Cond)3
;
55
5
    }
56
165
  }
57
165
  return false;
58
165
}
59
60
167
static bool isBuiltinUnreachable(const Stmt *S) {
61
167
  if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
62
119
    if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
63
103
      return FDecl->getIdentifier() &&
64
103
             FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
65
64
  return false;
66
64
}
67
68
static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S,
69
161
                                 ASTContext &C) {
70
161
  if (B->empty())  {
71
8
    // Happens if S is B's terminator and B contains nothing else
72
8
    // (e.g. a CFGBlock containing only a goto).
73
8
    return false;
74
8
  }
75
153
  if (Optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) {
76
152
    if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
77
90
      return CE->getCallee()->IgnoreCasts() == S && 
CE->isBuiltinAssumeFalse(C)83
;
78
90
    }
79
63
  }
80
63
  return false;
81
63
}
82
83
153
static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
84
153
  // Look to see if the current control flow ends with a 'return', and see if
85
153
  // 'S' is a substatement. The 'return' may not be the last element in the
86
153
  // block, or may be in a subsequent block because of destructors.
87
153
  const CFGBlock *Current = B;
88
154
  while (true) {
89
154
    for (CFGBlock::const_reverse_iterator I = Current->rbegin(),
90
154
                                          E = Current->rend();
91
155
         I != E; 
++I1
) {
92
146
      if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
93
145
        if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
94
34
          if (RS == S)
95
5
            return true;
96
29
          if (const Expr *RE = RS->getRetValue()) {
97
29
            RE = RE->IgnoreParenCasts();
98
29
            if (RE == S)
99
21
              return true;
100
8
            ParentMap PM(const_cast<Expr *>(RE));
101
8
            // If 'S' is in the ParentMap, it is a subexpression of
102
8
            // the return statement.
103
8
            return PM.getParent(S);
104
8
          }
105
29
        }
106
111
        break;
107
111
      }
108
146
    }
109
154
    // Note also that we are restricting the search for the return statement
110
154
    // to stop at control-flow; only part of a return statement may be dead,
111
154
    // without the whole return statement being dead.
112
154
    
if (120
Current->getTerminator().isTemporaryDtorsBranch()120
) {
113
0
      // Temporary destructors have a predictable control flow, thus we want to
114
0
      // look into the next block for the return statement.
115
0
      // We look into the false branch, as we know the true branch only contains
116
0
      // the call to the destructor.
117
0
      assert(Current->succ_size() == 2);
118
0
      Current = *(Current->succ_begin() + 1);
119
120
    } else if (!Current->getTerminatorStmt() && 
Current->succ_size() == 194
) {
120
93
      // If there is only one successor, we're not dealing with outgoing control
121
93
      // flow. Thus, look into the next block.
122
93
      Current = *Current->succ_begin();
123
93
      if (Current->pred_size() > 1) {
124
92
        // If there is more than one predecessor, we're dealing with incoming
125
92
        // control flow - if the return statement is in that block, it might
126
92
        // well be reachable via a different control flow, thus it's not dead.
127
92
        return false;
128
92
      }
129
27
    } else {
130
27
      // We hit control flow or a dead end. Stop searching.
131
27
      return false;
132
27
    }
133
120
  }
134
153
  
llvm_unreachable0
("Broke out of infinite loop.");
135
153
}
136
137
29
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {
138
29
  assert(Loc.isMacroID());
139
29
  SourceLocation Last;
140
59
  while (Loc.isMacroID()) {
141
30
    Last = Loc;
142
30
    Loc = SM.getImmediateMacroCallerLoc(Loc);
143
30
  }
144
29
  return Last;
145
29
}
146
147
/// Returns true if the statement is expanded from a configuration macro.
148
static bool isExpandedFromConfigurationMacro(const Stmt *S,
149
                                             Preprocessor &PP,
150
117
                                             bool IgnoreYES_NO = false) {
151
117
  // FIXME: This is not very precise.  Here we just check to see if the
152
117
  // value comes from a macro, but we can do much better.  This is likely
153
117
  // to be over conservative.  This logic is factored into a separate function
154
117
  // so that we can refine it later.
155
117
  SourceLocation L = S->getBeginLoc();
156
117
  if (L.isMacroID()) {
157
29
    SourceManager &SM = PP.getSourceManager();
158
29
    if (IgnoreYES_NO) {
159
9
      // The Objective-C constant 'YES' and 'NO'
160
9
      // are defined as macros.  Do not treat them
161
9
      // as configuration values.
162
9
      SourceLocation TopL = getTopMostMacro(L, SM);
163
9
      StringRef MacroName = PP.getImmediateMacroName(TopL);
164
9
      if (MacroName == "YES" || 
MacroName == "NO"4
)
165
8
        return false;
166
20
    } else if (!PP.getLangOpts().CPlusPlus) {
167
20
      // Do not treat C 'false' and 'true' macros as configuration values.
168
20
      SourceLocation TopL = getTopMostMacro(L, SM);
169
20
      StringRef MacroName = PP.getImmediateMacroName(TopL);
170
20
      if (MacroName == "false" || 
MacroName == "true"16
)
171
8
        return false;
172
13
    }
173
13
    return true;
174
13
  }
175
88
  return false;
176
88
}
177
178
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
179
180
/// Returns true if the statement represents a configuration value.
181
///
182
/// A configuration value is something usually determined at compile-time
183
/// to conditionally always execute some branch.  Such guards are for
184
/// "sometimes unreachable" code.  Such code is usually not interesting
185
/// to report as unreachable, and may mask truly unreachable code within
186
/// those blocks.
187
static bool isConfigurationValue(const Stmt *S,
188
                                 Preprocessor &PP,
189
                                 SourceRange *SilenceableCondVal = nullptr,
190
                                 bool IncludeIntegers = true,
191
473
                                 bool WrappedInParens = false) {
192
473
  if (!S)
193
32
    return false;
194
441
195
441
  if (const auto *Ex = dyn_cast<Expr>(S))
196
441
    S = Ex->IgnoreImplicit();
197
441
198
441
  if (const auto *Ex = dyn_cast<Expr>(S))
199
441
    S = Ex->IgnoreCasts();
200
441
201
441
  // Special case looking for the sigil '()' around an integer literal.
202
441
  if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
203
32
    if (!PE->getBeginLoc().isMacroID())
204
28
      return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
205
28
                                  IncludeIntegers, true);
206
413
207
413
  if (const Expr *Ex = dyn_cast<Expr>(S))
208
413
    S = Ex->IgnoreCasts();
209
413
210
413
  bool IgnoreYES_NO = false;
211
413
212
413
  switch (S->getStmtClass()) {
213
413
    case Stmt::CallExprClass: {
214
6
      const FunctionDecl *Callee =
215
6
        dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
216
6
      return Callee ? Callee->isConstexpr() : 
false0
;
217
413
    }
218
413
    case Stmt::DeclRefExprClass:
219
61
      return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
220
413
    case Stmt::ObjCBoolLiteralExprClass:
221
13
      IgnoreYES_NO = true;
222
13
      LLVM_FALLTHROUGH;
223
161
    case Stmt::CXXBoolLiteralExprClass:
224
161
    case Stmt::IntegerLiteralClass: {
225
161
      const Expr *E = cast<Expr>(S);
226
161
      if (IncludeIntegers) {
227
141
        if (SilenceableCondVal && 
!SilenceableCondVal->getBegin().isValid()47
)
228
44
          *SilenceableCondVal = E->getSourceRange();
229
141
        return WrappedInParens || 
isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO)117
;
230
141
      }
231
20
      return false;
232
20
    }
233
20
    case Stmt::MemberExprClass:
234
19
      return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
235
20
    case Stmt::UnaryExprOrTypeTraitExprClass:
236
9
      return true;
237
91
    case Stmt::BinaryOperatorClass: {
238
91
      const BinaryOperator *B = cast<BinaryOperator>(S);
239
91
      // Only include raw integers (not enums) as configuration
240
91
      // values if they are used in a logical or comparison operator
241
91
      // (not arithmetic).
242
91
      IncludeIntegers &= (B->isLogicalOp() || 
B->isComparisonOp()53
);
243
91
      return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
244
91
                                  IncludeIntegers) ||
245
91
             isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
246
72
                                  IncludeIntegers);
247
20
    }
248
62
    case Stmt::UnaryOperatorClass: {
249
62
      const UnaryOperator *UO = cast<UnaryOperator>(S);
250
62
      if (UO->getOpcode() != UO_LNot)
251
4
        return false;
252
58
      bool SilenceableCondValNotSet =
253
58
          SilenceableCondVal && 
SilenceableCondVal->getBegin().isInvalid()17
;
254
58
      bool IsSubExprConfigValue =
255
58
          isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
256
58
                               IncludeIntegers, WrappedInParens);
257
58
      // Update the silenceable condition value source range only if the range
258
58
      // was set directly by the child expression.
259
58
      if (SilenceableCondValNotSet &&
260
58
          
SilenceableCondVal->getBegin().isValid()15
&&
261
58
          *SilenceableCondVal ==
262
13
              UO->getSubExpr()->IgnoreCasts()->getSourceRange())
263
11
        *SilenceableCondVal = UO->getSourceRange();
264
58
      return IsSubExprConfigValue;
265
58
    }
266
58
    default:
267
4
      return false;
268
413
  }
269
413
}
270
271
80
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
272
80
  if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
273
12
    return isConfigurationValue(ED->getInitExpr(), PP);
274
68
  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
275
50
    // As a heuristic, treat globals as configuration values.  Note
276
50
    // that we only will get here if Sema evaluated this
277
50
    // condition to a constant expression, which means the global
278
50
    // had to be declared in a way to be a truly constant value.
279
50
    // We could generalize this to local variables, but it isn't
280
50
    // clear if those truly represent configuration values that
281
50
    // gate unreachable code.
282
50
    if (!VD->hasLocalStorage())
283
5
      return true;
284
45
285
45
    // As a heuristic, locals that have been marked 'const' explicitly
286
45
    // can be treated as configuration values as well.
287
45
    return VD->getType().isLocalConstQualified();
288
45
  }
289
18
  return false;
290
18
}
291
292
/// Returns true if we should always explore all successors of a block.
293
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
294
131
                                             Preprocessor &PP) {
295
131
  if (const Stmt *Term = B->getTerminatorStmt()) {
296
131
    if (isa<SwitchStmt>(Term))
297
6
      return true;
298
125
    // Specially handle '||' and '&&'.
299
125
    if (isa<BinaryOperator>(Term)) {
300
11
      return isConfigurationValue(Term, PP);
301
11
    }
302
114
  }
303
114
304
114
  const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
305
114
  return isConfigurationValue(Cond, PP);
306
114
}
307
308
static unsigned scanFromBlock(const CFGBlock *Start,
309
                              llvm::BitVector &Reachable,
310
                              Preprocessor *PP,
311
234k
                              bool IncludeSometimesUnreachableEdges) {
312
234k
  unsigned count = 0;
313
234k
314
234k
  // Prep work queue
315
234k
  SmallVector<const CFGBlock*, 32> WL;
316
234k
317
234k
  // The entry block may have already been marked reachable
318
234k
  // by the caller.
319
234k
  if (!Reachable[Start->getBlockID()]) {
320
234k
    ++count;
321
234k
    Reachable[Start->getBlockID()] = true;
322
234k
  }
323
234k
324
234k
  WL.push_back(Start);
325
234k
326
234k
  // Find the reachable blocks from 'Start'.
327
1.31M
  while (!WL.empty()) {
328
1.10M
    const CFGBlock *item = WL.pop_back_val();
329
1.10M
330
1.10M
    // There are cases where we want to treat all successors as reachable.
331
1.10M
    // The idea is that some "sometimes unreachable" code is not interesting,
332
1.10M
    // and that we should forge ahead and explore those branches anyway.
333
1.10M
    // This allows us to potentially uncover some "always unreachable" code
334
1.10M
    // within the "sometimes unreachable" code.
335
1.10M
    // Look at the successors and mark then reachable.
336
1.10M
    Optional<bool> TreatAllSuccessorsAsReachable;
337
1.10M
    if (!IncludeSometimesUnreachableEdges)
338
1.10M
      TreatAllSuccessorsAsReachable = false;
339
1.10M
340
1.10M
    for (CFGBlock::const_succ_iterator I = item->succ_begin(),
341
2.24M
         E = item->succ_end(); I != E; 
++I1.13M
) {
342
1.16M
      const CFGBlock *B = *I;
343
1.16M
      if (!B) 
do 100k
{
344
100k
        const CFGBlock *UB = I->getPossiblyUnreachableBlock();
345
100k
        if (!UB)
346
30.8k
          break;
347
69.8k
348
69.8k
        if (!TreatAllSuccessorsAsReachable.hasValue()) {
349
131
          assert(PP);
350
131
          TreatAllSuccessorsAsReachable =
351
131
            shouldTreatSuccessorsAsReachable(item, *PP);
352
131
        }
353
69.8k
354
69.8k
        if (TreatAllSuccessorsAsReachable.getValue()) {
355
60
          B = UB;
356
60
          break;
357
60
        }
358
69.8k
      }
359
69.8k
      while (false);
360
1.16M
361
1.16M
      
if (1.13M
B1.13M
) {
362
1.06M
        unsigned blockID = B->getBlockID();
363
1.06M
        if (!Reachable[blockID]) {
364
874k
          Reachable.set(blockID);
365
874k
          WL.push_back(B);
366
874k
          ++count;
367
874k
        }
368
1.06M
      }
369
1.13M
    }
370
1.10M
  }
371
234k
  
return count203k
;
372
234k
}
373
374
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
375
                                            Preprocessor &PP,
376
363
                                            llvm::BitVector &Reachable) {
377
363
  return scanFromBlock(Start, Reachable, &PP, true);
378
363
}
379
380
//===----------------------------------------------------------------------===//
381
// Dead Code Scanner.
382
//===----------------------------------------------------------------------===//
383
384
namespace {
385
  class DeadCodeScan {
386
    llvm::BitVector Visited;
387
    llvm::BitVector &Reachable;
388
    SmallVector<const CFGBlock *, 10> WorkList;
389
    Preprocessor &PP;
390
    ASTContext &C;
391
392
    typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
393
    DeferredLocsTy;
394
395
    DeferredLocsTy DeferredLocs;
396
397
  public:
398
    DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C)
399
    : Visited(reachable.size()),
400
      Reachable(reachable),
401
211
      PP(PP), C(C) {}
402
403
    void enqueue(const CFGBlock *block);
404
    unsigned scanBackwards(const CFGBlock *Start,
405
    clang::reachable_code::Callback &CB);
406
407
    bool isDeadCodeRoot(const CFGBlock *Block);
408
409
    const Stmt *findDeadCode(const CFGBlock *Block);
410
411
    void reportDeadCode(const CFGBlock *B,
412
                        const Stmt *S,
413
                        clang::reachable_code::Callback &CB);
414
  };
415
}
416
417
216
void DeadCodeScan::enqueue(const CFGBlock *block) {
418
216
  unsigned blockID = block->getBlockID();
419
216
  if (Reachable[blockID] || Visited[blockID])
420
0
    return;
421
216
  Visited[blockID] = true;
422
216
  WorkList.push_back(block);
423
216
}
424
425
208
bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
426
208
  bool isDeadRoot = true;
427
208
428
208
  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
429
377
       E = Block->pred_end(); I != E; 
++I169
) {
430
169
    if (const CFGBlock *PredBlock = *I) {
431
41
      unsigned blockID = PredBlock->getBlockID();
432
41
      if (Visited[blockID]) {
433
6
        isDeadRoot = false;
434
6
        continue;
435
6
      }
436
35
      if (!Reachable[blockID]) {
437
35
        isDeadRoot = false;
438
35
        Visited[blockID] = true;
439
35
        WorkList.push_back(PredBlock);
440
35
        continue;
441
35
      }
442
35
    }
443
169
  }
444
208
445
208
  return isDeadRoot;
446
208
}
447
448
234
static bool isValidDeadStmt(const Stmt *S) {
449
234
  if (S->getBeginLoc().isInvalid())
450
0
    return false;
451
234
  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
452
20
    return BO->getOpcode() != BO_Comma;
453
214
  return true;
454
214
}
455
456
247
const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
457
271
  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; 
++I24
)
458
210
    if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
459
202
      const Stmt *S = CS->getStmt();
460
202
      if (isValidDeadStmt(S))
461
186
        return S;
462
202
    }
463
247
464
247
  CFGTerminator T = Block->getTerminator();
465
61
  if (T.isStmtBranch()) {
466
58
    const Stmt *S = T.getStmt();
467
58
    if (S && 
isValidDeadStmt(S)32
)
468
32
      return S;
469
29
  }
470
29
471
29
  return nullptr;
472
29
}
473
474
static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
475
16
                  const std::pair<const CFGBlock *, const Stmt *> *p2) {
476
16
  if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
477
6
    return -1;
478
10
  if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
479
10
    return 1;
480
0
  return 0;
481
0
}
482
483
unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
484
211
                                     clang::reachable_code::Callback &CB) {
485
211
486
211
  unsigned count = 0;
487
211
  enqueue(Start);
488
211
489
462
  while (!WorkList.empty()) {
490
251
    const CFGBlock *Block = WorkList.pop_back_val();
491
251
492
251
    // It is possible that this block has been marked reachable after
493
251
    // it was enqueued.
494
251
    if (Reachable[Block->getBlockID()])
495
4
      continue;
496
247
497
247
    // Look for any dead code within the block.
498
247
    const Stmt *S = findDeadCode(Block);
499
247
500
247
    if (!S) {
501
29
      // No dead code.  Possibly an empty block.  Look at dead predecessors.
502
29
      for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
503
50
           E = Block->pred_end(); I != E; 
++I21
) {
504
21
        if (const CFGBlock *predBlock = *I)
505
5
          enqueue(predBlock);
506
21
      }
507
29
      continue;
508
29
    }
509
218
510
218
    // Specially handle macro-expanded code.
511
218
    if (S->getBeginLoc().isMacroID()) {
512
10
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
513
10
      continue;
514
10
    }
515
208
516
208
    if (isDeadCodeRoot(Block)) {
517
179
      reportDeadCode(Block, S, CB);
518
179
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
519
179
    }
520
29
    else {
521
29
      // Record this statement as the possibly best location in a
522
29
      // strongly-connected component of dead code for emitting a
523
29
      // warning.
524
29
      DeferredLocs.push_back(std::make_pair(Block, S));
525
29
    }
526
208
  }
527
211
528
211
  // If we didn't find a dead root, then report the dead code with the
529
211
  // earliest location.
530
211
  if (!DeferredLocs.empty()) {
531
15
    llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
532
15
    for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
533
44
         E = DeferredLocs.end(); I != E; 
++I29
) {
534
29
      const CFGBlock *Block = I->first;
535
29
      if (Reachable[Block->getBlockID()])
536
22
        continue;
537
7
      reportDeadCode(Block, I->second, CB);
538
7
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
539
7
    }
540
15
  }
541
211
542
211
  return count;
543
211
}
544
545
static SourceLocation GetUnreachableLoc(const Stmt *S,
546
                                        SourceRange &R1,
547
166
                                        SourceRange &R2) {
548
166
  R1 = R2 = SourceRange();
549
166
550
166
  if (const Expr *Ex = dyn_cast<Expr>(S))
551
137
    S = Ex->IgnoreParenImpCasts();
552
166
553
166
  switch (S->getStmtClass()) {
554
166
    case Expr::BinaryOperatorClass: {
555
2
      const BinaryOperator *BO = cast<BinaryOperator>(S);
556
2
      return BO->getOperatorLoc();
557
166
    }
558
166
    case Expr::UnaryOperatorClass: {
559
3
      const UnaryOperator *UO = cast<UnaryOperator>(S);
560
3
      R1 = UO->getSubExpr()->getSourceRange();
561
3
      return UO->getOperatorLoc();
562
166
    }
563
166
    case Expr::CompoundAssignOperatorClass: {
564
2
      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
565
2
      R1 = CAO->getLHS()->getSourceRange();
566
2
      R2 = CAO->getRHS()->getSourceRange();
567
2
      return CAO->getOperatorLoc();
568
166
    }
569
166
    case Expr::BinaryConditionalOperatorClass:
570
2
    case Expr::ConditionalOperatorClass: {
571
2
      const AbstractConditionalOperator *CO =
572
2
      cast<AbstractConditionalOperator>(S);
573
2
      return CO->getQuestionLoc();
574
2
    }
575
2
    case Expr::MemberExprClass: {
576
1
      const MemberExpr *ME = cast<MemberExpr>(S);
577
1
      R1 = ME->getSourceRange();
578
1
      return ME->getMemberLoc();
579
2
    }
580
2
    case Expr::ArraySubscriptExprClass: {
581
2
      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
582
2
      R1 = ASE->getLHS()->getSourceRange();
583
2
      R2 = ASE->getRHS()->getSourceRange();
584
2
      return ASE->getRBracketLoc();
585
2
    }
586
2
    case Expr::CStyleCastExprClass: {
587
2
      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
588
2
      R1 = CSC->getSubExpr()->getSourceRange();
589
2
      return CSC->getLParenLoc();
590
2
    }
591
2
    case Expr::CXXFunctionalCastExprClass: {
592
0
      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
593
0
      R1 = CE->getSubExpr()->getSourceRange();
594
0
      return CE->getBeginLoc();
595
2
    }
596
2
    case Stmt::CXXTryStmtClass: {
597
0
      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
598
2
    }
599
2
    case Expr::ObjCBridgedCastExprClass: {
600
0
      const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
601
0
      R1 = CSC->getSubExpr()->getSourceRange();
602
0
      return CSC->getLParenLoc();
603
2
    }
604
152
    default: ;
605
166
  }
606
166
  R1 = S->getSourceRange();
607
152
  return S->getBeginLoc();
608
166
}
609
610
void DeadCodeScan::reportDeadCode(const CFGBlock *B,
611
                                  const Stmt *S,
612
186
                                  clang::reachable_code::Callback &CB) {
613
186
  // Classify the unreachable code found, or suppress it in some cases.
614
186
  reachable_code::UnreachableKind UK = reachable_code::UK_Other;
615
186
616
186
  if (isa<BreakStmt>(S)) {
617
16
    UK = reachable_code::UK_Break;
618
170
  } else if (isTrivialDoWhile(B, S) || 
isBuiltinUnreachable(S)167
||
619
170
             
isBuiltinAssumeFalse(B, S, C)161
) {
620
17
    return;
621
17
  }
622
153
  else if (isDeadReturn(B, S)) {
623
32
    UK = reachable_code::UK_Return;
624
32
  }
625
186
626
186
  SourceRange SilenceableCondVal;
627
169
628
169
  if (UK == reachable_code::UK_Other) {
629
121
    // Check if the dead code is part of the "loop target" of
630
121
    // a for/for-range loop.  This is the block that contains
631
121
    // the increment code.
632
121
    if (const Stmt *LoopTarget = B->getLoopTarget()) {
633
3
      SourceLocation Loc = LoopTarget->getBeginLoc();
634
3
      SourceRange R1(Loc, Loc), R2;
635
3
636
3
      if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
637
2
        const Expr *Inc = FS->getInc();
638
2
        Loc = Inc->getBeginLoc();
639
2
        R2 = Inc->getSourceRange();
640
2
      }
641
3
642
3
      CB.HandleUnreachable(reachable_code::UK_Loop_Increment,
643
3
                           Loc, SourceRange(), SourceRange(Loc, Loc), R2);
644
3
      return;
645
3
    }
646
118
647
118
    // Check if the dead block has a predecessor whose branch has
648
118
    // a configuration value that *could* be modified to
649
118
    // silence the warning.
650
118
    CFGBlock::const_pred_iterator PI = B->pred_begin();
651
118
    if (PI != B->pred_end()) {
652
93
      if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
653
87
        const Stmt *TermCond =
654
87
            PredBlock->getTerminatorCondition(/* strip parens */ false);
655
87
        isConfigurationValue(TermCond, PP, &SilenceableCondVal);
656
87
      }
657
93
    }
658
118
  }
659
169
660
169
  SourceRange R1, R2;
661
166
  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
662
166
  CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2);
663
166
}
664
665
//===----------------------------------------------------------------------===//
666
// Reachability APIs.
667
//===----------------------------------------------------------------------===//
668
669
namespace clang { namespace reachable_code {
670
671
0
void Callback::anchor() { }
672
673
unsigned ScanReachableFromBlock(const CFGBlock *Start,
674
234k
                                llvm::BitVector &Reachable) {
675
234k
  return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
676
234k
}
677
678
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
679
155
                         Callback &CB) {
680
155
681
155
  CFG *cfg = AC.getCFG();
682
155
  if (!cfg)
683
0
    return;
684
155
685
155
  // Scan for reachable blocks from the entrance of the CFG.
686
155
  // If there are no unreachable blocks, we're done.
687
155
  llvm::BitVector reachable(cfg->getNumBlockIDs());
688
155
  unsigned numReachable =
689
155
    scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
690
155
  if (numReachable == cfg->getNumBlockIDs())
691
50
    return;
692
105
693
105
  // If there aren't explicit EH edges, we should include the 'try' dispatch
694
105
  // blocks as roots.
695
105
  if (!AC.getCFGBuildOptions().AddEHEdges) {
696
105
    for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
697
117
         E = cfg->try_blocks_end() ; I != E; 
++I12
) {
698
12
      numReachable += scanMaybeReachableFromBlock(*I, PP, reachable);
699
12
    }
700
105
    if (numReachable == cfg->getNumBlockIDs())
701
1
      return;
702
104
  }
703
104
704
104
  // There are some unreachable blocks.  We need to find the root blocks that
705
104
  // contain code that should be considered unreachable.
706
610
  
for (CFG::iterator I = cfg->begin(), E = cfg->end(); 104
I != E;
++I506
) {
707
599
    const CFGBlock *block = *I;
708
599
    // A block may have been marked reachable during this loop.
709
599
    if (reachable[block->getBlockID()])
710
388
      continue;
711
211
712
211
    DeadCodeScan DS(reachable, PP, AC.getASTContext());
713
211
    numReachable += DS.scanBackwards(block, CB);
714
211
715
211
    if (numReachable == cfg->getNumBlockIDs())
716
93
      return;
717
211
  }
718
104
}
719
720
}} // end namespace clang::reachable_code