Coverage Report

Created: 2020-02-15 09:57

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