llvm-project

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/Attr.h"
16
#include "clang/AST/Expr.h"
17
#include "clang/AST/ExprCXX.h"
18
#include "clang/AST/ExprObjC.h"
19
#include "clang/AST/ParentMap.h"
20
#include "clang/AST/RecursiveASTVisitor.h"
21
#include "clang/AST/StmtCXX.h"
22
#include "clang/Analysis/AnalysisDeclContext.h"
23
#include "clang/Analysis/CFG.h"
24
#include "clang/Basic/Builtins.h"
25
#include "clang/Basic/SourceManager.h"
26
#include "clang/Lex/Preprocessor.h"
27
#include "llvm/ADT/BitVector.h"
28
#include "llvm/ADT/SmallVector.h"
29
#include <optional>
30

31
using namespace clang;
32

33
//===----------------------------------------------------------------------===//
34
// Core Reachability Analysis routines.
35
//===----------------------------------------------------------------------===//
36

37
static bool isEnumConstant(const Expr *Ex) {
38
  const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex);
39
  if (!DR)
40
    return false;
41
  return isa<EnumConstantDecl>(DR->getDecl());
42
}
43

44
static bool isTrivialExpression(const Expr *Ex) {
45
  Ex = Ex->IgnoreParenCasts();
46
  return isa<IntegerLiteral>(Ex) || isa<StringLiteral>(Ex) ||
47
         isa<CXXBoolLiteralExpr>(Ex) || isa<ObjCBoolLiteralExpr>(Ex) ||
48
         isa<CharacterLiteral>(Ex) ||
49
         isEnumConstant(Ex);
50
}
51

52
static bool isTrivialDoWhile(const CFGBlock *B, const Stmt *S) {
53
  // Check if the block ends with a do...while() and see if 'S' is the
54
  // condition.
55
  if (const Stmt *Term = B->getTerminatorStmt()) {
56
    if (const DoStmt *DS = dyn_cast<DoStmt>(Term)) {
57
      const Expr *Cond = DS->getCond()->IgnoreParenCasts();
58
      return Cond == S && isTrivialExpression(Cond);
59
    }
60
  }
61
  return false;
62
}
63

64
static bool isBuiltinUnreachable(const Stmt *S) {
65
  if (const auto *DRE = dyn_cast<DeclRefExpr>(S))
66
    if (const auto *FDecl = dyn_cast<FunctionDecl>(DRE->getDecl()))
67
      return FDecl->getIdentifier() &&
68
             FDecl->getBuiltinID() == Builtin::BI__builtin_unreachable;
69
  return false;
70
}
71

72
static bool isBuiltinAssumeFalse(const CFGBlock *B, const Stmt *S,
73
                                 ASTContext &C) {
74
  if (B->empty())  {
75
    // Happens if S is B's terminator and B contains nothing else
76
    // (e.g. a CFGBlock containing only a goto).
77
    return false;
78
  }
79
  if (std::optional<CFGStmt> CS = B->back().getAs<CFGStmt>()) {
80
    if (const auto *CE = dyn_cast<CallExpr>(CS->getStmt())) {
81
      return CE->getCallee()->IgnoreCasts() == S && CE->isBuiltinAssumeFalse(C);
82
    }
83
  }
84
  return false;
85
}
86

87
static bool isDeadReturn(const CFGBlock *B, const Stmt *S) {
88
  // Look to see if the current control flow ends with a 'return', and see if
89
  // 'S' is a substatement. The 'return' may not be the last element in the
90
  // block, or may be in a subsequent block because of destructors.
91
  const CFGBlock *Current = B;
92
  while (true) {
93
    for (const CFGElement &CE : llvm::reverse(*Current)) {
94
      if (std::optional<CFGStmt> CS = CE.getAs<CFGStmt>()) {
95
        if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(CS->getStmt())) {
96
          if (RS == S)
97
            return true;
98
          if (const Expr *RE = RS->getRetValue()) {
99
            RE = RE->IgnoreParenCasts();
100
            if (RE == S)
101
              return true;
102
            ParentMap PM(const_cast<Expr *>(RE));
103
            // If 'S' is in the ParentMap, it is a subexpression of
104
            // the return statement.
105
            return PM.getParent(S);
106
          }
107
        }
108
        break;
109
      }
110
    }
111
    // Note also that we are restricting the search for the return statement
112
    // to stop at control-flow; only part of a return statement may be dead,
113
    // without the whole return statement being dead.
114
    if (Current->getTerminator().isTemporaryDtorsBranch()) {
115
      // Temporary destructors have a predictable control flow, thus we want to
116
      // look into the next block for the return statement.
117
      // We look into the false branch, as we know the true branch only contains
118
      // the call to the destructor.
119
      assert(Current->succ_size() == 2);
120
      Current = *(Current->succ_begin() + 1);
121
    } else if (!Current->getTerminatorStmt() && Current->succ_size() == 1) {
122
      // If there is only one successor, we're not dealing with outgoing control
123
      // flow. Thus, look into the next block.
124
      Current = *Current->succ_begin();
125
      if (Current->pred_size() > 1) {
126
        // If there is more than one predecessor, we're dealing with incoming
127
        // control flow - if the return statement is in that block, it might
128
        // well be reachable via a different control flow, thus it's not dead.
129
        return false;
130
      }
131
    } else {
132
      // We hit control flow or a dead end. Stop searching.
133
      return false;
134
    }
135
  }
136
  llvm_unreachable("Broke out of infinite loop.");
137
}
138

139
static SourceLocation getTopMostMacro(SourceLocation Loc, SourceManager &SM) {
140
  assert(Loc.isMacroID());
141
  SourceLocation Last;
142
  do {
143
    Last = Loc;
144
    Loc = SM.getImmediateMacroCallerLoc(Loc);
145
  } while (Loc.isMacroID());
146
  return Last;
147
}
148

149
/// Returns true if the statement is expanded from a configuration macro.
150
static bool isExpandedFromConfigurationMacro(const Stmt *S,
151
                                             Preprocessor &PP,
152
                                             bool IgnoreYES_NO = false) {
153
  // FIXME: This is not very precise.  Here we just check to see if the
154
  // value comes from a macro, but we can do much better.  This is likely
155
  // to be over conservative.  This logic is factored into a separate function
156
  // so that we can refine it later.
157
  SourceLocation L = S->getBeginLoc();
158
  if (L.isMacroID()) {
159
    SourceManager &SM = PP.getSourceManager();
160
    if (IgnoreYES_NO) {
161
      // The Objective-C constant 'YES' and 'NO'
162
      // are defined as macros.  Do not treat them
163
      // as configuration values.
164
      SourceLocation TopL = getTopMostMacro(L, SM);
165
      StringRef MacroName = PP.getImmediateMacroName(TopL);
166
      if (MacroName == "YES" || MacroName == "NO")
167
        return false;
168
    } else if (!PP.getLangOpts().CPlusPlus) {
169
      // Do not treat C 'false' and 'true' macros as configuration values.
170
      SourceLocation TopL = getTopMostMacro(L, SM);
171
      StringRef MacroName = PP.getImmediateMacroName(TopL);
172
      if (MacroName == "false" || MacroName == "true")
173
        return false;
174
    }
175
    return true;
176
  }
177
  return false;
178
}
179

180
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP);
181

182
/// Returns true if the statement represents a configuration value.
183
///
184
/// A configuration value is something usually determined at compile-time
185
/// to conditionally always execute some branch.  Such guards are for
186
/// "sometimes unreachable" code.  Such code is usually not interesting
187
/// to report as unreachable, and may mask truly unreachable code within
188
/// those blocks.
189
static bool isConfigurationValue(const Stmt *S,
190
                                 Preprocessor &PP,
191
                                 SourceRange *SilenceableCondVal = nullptr,
192
                                 bool IncludeIntegers = true,
193
                                 bool WrappedInParens = false) {
194
  if (!S)
195
    return false;
196

197
  if (const auto *Ex = dyn_cast<Expr>(S))
198
    S = Ex->IgnoreImplicit();
199

200
  if (const auto *Ex = dyn_cast<Expr>(S))
201
    S = Ex->IgnoreCasts();
202

203
  // Special case looking for the sigil '()' around an integer literal.
204
  if (const ParenExpr *PE = dyn_cast<ParenExpr>(S))
205
    if (!PE->getBeginLoc().isMacroID())
206
      return isConfigurationValue(PE->getSubExpr(), PP, SilenceableCondVal,
207
                                  IncludeIntegers, true);
208

209
  if (const Expr *Ex = dyn_cast<Expr>(S))
210
    S = Ex->IgnoreCasts();
211

212
  bool IgnoreYES_NO = false;
213

214
  switch (S->getStmtClass()) {
215
    case Stmt::CallExprClass: {
216
      const FunctionDecl *Callee =
217
        dyn_cast_or_null<FunctionDecl>(cast<CallExpr>(S)->getCalleeDecl());
218
      return Callee ? Callee->isConstexpr() : false;
219
    }
220
    case Stmt::DeclRefExprClass:
221
      return isConfigurationValue(cast<DeclRefExpr>(S)->getDecl(), PP);
222
    case Stmt::ObjCBoolLiteralExprClass:
223
      IgnoreYES_NO = true;
224
      [[fallthrough]];
225
    case Stmt::CXXBoolLiteralExprClass:
226
    case Stmt::IntegerLiteralClass: {
227
      const Expr *E = cast<Expr>(S);
228
      if (IncludeIntegers) {
229
        if (SilenceableCondVal && !SilenceableCondVal->getBegin().isValid())
230
          *SilenceableCondVal = E->getSourceRange();
231
        return WrappedInParens ||
232
               isExpandedFromConfigurationMacro(E, PP, IgnoreYES_NO);
233
      }
234
      return false;
235
    }
236
    case Stmt::MemberExprClass:
237
      return isConfigurationValue(cast<MemberExpr>(S)->getMemberDecl(), PP);
238
    case Stmt::UnaryExprOrTypeTraitExprClass:
239
      return true;
240
    case Stmt::BinaryOperatorClass: {
241
      const BinaryOperator *B = cast<BinaryOperator>(S);
242
      // Only include raw integers (not enums) as configuration
243
      // values if they are used in a logical or comparison operator
244
      // (not arithmetic).
245
      IncludeIntegers &= (B->isLogicalOp() || B->isComparisonOp());
246
      return isConfigurationValue(B->getLHS(), PP, SilenceableCondVal,
247
                                  IncludeIntegers) ||
248
             isConfigurationValue(B->getRHS(), PP, SilenceableCondVal,
249
                                  IncludeIntegers);
250
    }
251
    case Stmt::UnaryOperatorClass: {
252
      const UnaryOperator *UO = cast<UnaryOperator>(S);
253
      if (UO->getOpcode() != UO_LNot && UO->getOpcode() != UO_Minus)
254
        return false;
255
      bool SilenceableCondValNotSet =
256
          SilenceableCondVal && SilenceableCondVal->getBegin().isInvalid();
257
      bool IsSubExprConfigValue =
258
          isConfigurationValue(UO->getSubExpr(), PP, SilenceableCondVal,
259
                               IncludeIntegers, WrappedInParens);
260
      // Update the silenceable condition value source range only if the range
261
      // was set directly by the child expression.
262
      if (SilenceableCondValNotSet &&
263
          SilenceableCondVal->getBegin().isValid() &&
264
          *SilenceableCondVal ==
265
              UO->getSubExpr()->IgnoreCasts()->getSourceRange())
266
        *SilenceableCondVal = UO->getSourceRange();
267
      return IsSubExprConfigValue;
268
    }
269
    default:
270
      return false;
271
  }
272
}
273

274
static bool isConfigurationValue(const ValueDecl *D, Preprocessor &PP) {
275
  if (const EnumConstantDecl *ED = dyn_cast<EnumConstantDecl>(D))
276
    return isConfigurationValue(ED->getInitExpr(), PP);
277
  if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
278
    // As a heuristic, treat globals as configuration values.  Note
279
    // that we only will get here if Sema evaluated this
280
    // condition to a constant expression, which means the global
281
    // had to be declared in a way to be a truly constant value.
282
    // We could generalize this to local variables, but it isn't
283
    // clear if those truly represent configuration values that
284
    // gate unreachable code.
285
    if (!VD->hasLocalStorage())
286
      return true;
287

288
    // As a heuristic, locals that have been marked 'const' explicitly
289
    // can be treated as configuration values as well.
290
    return VD->getType().isLocalConstQualified();
291
  }
292
  return false;
293
}
294

295
/// Returns true if we should always explore all successors of a block.
296
static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B,
297
                                             Preprocessor &PP) {
298
  if (const Stmt *Term = B->getTerminatorStmt()) {
299
    if (isa<SwitchStmt>(Term))
300
      return true;
301
    // Specially handle '||' and '&&'.
302
    if (isa<BinaryOperator>(Term)) {
303
      return isConfigurationValue(Term, PP);
304
    }
305
    // Do not treat constexpr if statement successors as unreachable in warnings
306
    // since the point of these statements is to determine branches at compile
307
    // time.
308
    if (const auto *IS = dyn_cast<IfStmt>(Term);
309
        IS != nullptr && IS->isConstexpr())
310
      return true;
311
  }
312

313
  const Stmt *Cond = B->getTerminatorCondition(/* stripParens */ false);
314
  return isConfigurationValue(Cond, PP);
315
}
316

317
static unsigned scanFromBlock(const CFGBlock *Start,
318
                              llvm::BitVector &Reachable,
319
                              Preprocessor *PP,
320
                              bool IncludeSometimesUnreachableEdges) {
321
  unsigned count = 0;
322

323
  // Prep work queue
324
  SmallVector<const CFGBlock*, 32> WL;
325

326
  // The entry block may have already been marked reachable
327
  // by the caller.
328
  if (!Reachable[Start->getBlockID()]) {
329
    ++count;
330
    Reachable[Start->getBlockID()] = true;
331
  }
332

333
  WL.push_back(Start);
334

335
  // Find the reachable blocks from 'Start'.
336
  while (!WL.empty()) {
337
    const CFGBlock *item = WL.pop_back_val();
338

339
    // There are cases where we want to treat all successors as reachable.
340
    // The idea is that some "sometimes unreachable" code is not interesting,
341
    // and that we should forge ahead and explore those branches anyway.
342
    // This allows us to potentially uncover some "always unreachable" code
343
    // within the "sometimes unreachable" code.
344
    // Look at the successors and mark then reachable.
345
    std::optional<bool> TreatAllSuccessorsAsReachable;
346
    if (!IncludeSometimesUnreachableEdges)
347
      TreatAllSuccessorsAsReachable = false;
348

349
    for (CFGBlock::const_succ_iterator I = item->succ_begin(),
350
         E = item->succ_end(); I != E; ++I) {
351
      const CFGBlock *B = *I;
352
      if (!B) do {
353
        const CFGBlock *UB = I->getPossiblyUnreachableBlock();
354
        if (!UB)
355
          break;
356

357
        if (!TreatAllSuccessorsAsReachable) {
358
          assert(PP);
359
          TreatAllSuccessorsAsReachable =
360
            shouldTreatSuccessorsAsReachable(item, *PP);
361
        }
362

363
        if (*TreatAllSuccessorsAsReachable) {
364
          B = UB;
365
          break;
366
        }
367
      }
368
      while (false);
369

370
      if (B) {
371
        unsigned blockID = B->getBlockID();
372
        if (!Reachable[blockID]) {
373
          Reachable.set(blockID);
374
          WL.push_back(B);
375
          ++count;
376
        }
377
      }
378
    }
379
  }
380
  return count;
381
}
382

383
static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
384
                                            Preprocessor &PP,
385
                                            llvm::BitVector &Reachable) {
386
  return scanFromBlock(Start, Reachable, &PP, true);
387
}
388

389
//===----------------------------------------------------------------------===//
390
// Dead Code Scanner.
391
//===----------------------------------------------------------------------===//
392

393
namespace {
394
  class DeadCodeScan {
395
    llvm::BitVector Visited;
396
    llvm::BitVector &Reachable;
397
    SmallVector<const CFGBlock *, 10> WorkList;
398
    Preprocessor &PP;
399
    ASTContext &C;
400

401
    typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
402
    DeferredLocsTy;
403

404
    DeferredLocsTy DeferredLocs;
405

406
  public:
407
    DeadCodeScan(llvm::BitVector &reachable, Preprocessor &PP, ASTContext &C)
408
    : Visited(reachable.size()),
409
      Reachable(reachable),
410
      PP(PP), C(C) {}
411

412
    void enqueue(const CFGBlock *block);
413
    unsigned scanBackwards(const CFGBlock *Start,
414
    clang::reachable_code::Callback &CB);
415

416
    bool isDeadCodeRoot(const CFGBlock *Block);
417

418
    const Stmt *findDeadCode(const CFGBlock *Block);
419

420
    void reportDeadCode(const CFGBlock *B,
421
                        const Stmt *S,
422
                        clang::reachable_code::Callback &CB);
423
  };
424
}
425

426
void DeadCodeScan::enqueue(const CFGBlock *block) {
427
  unsigned blockID = block->getBlockID();
428
  if (Reachable[blockID] || Visited[blockID])
429
    return;
430
  Visited[blockID] = true;
431
  WorkList.push_back(block);
432
}
433

434
bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
435
  bool isDeadRoot = true;
436

437
  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
438
       E = Block->pred_end(); I != E; ++I) {
439
    if (const CFGBlock *PredBlock = *I) {
440
      unsigned blockID = PredBlock->getBlockID();
441
      if (Visited[blockID]) {
442
        isDeadRoot = false;
443
        continue;
444
      }
445
      if (!Reachable[blockID]) {
446
        isDeadRoot = false;
447
        Visited[blockID] = true;
448
        WorkList.push_back(PredBlock);
449
        continue;
450
      }
451
    }
452
  }
453

454
  return isDeadRoot;
455
}
456

457
// Check if the given `DeadStmt` is a coroutine statement and is a substmt of
458
// the coroutine statement. `Block` is the CFGBlock containing the `DeadStmt`.
459
static bool isInCoroutineStmt(const Stmt *DeadStmt, const CFGBlock *Block) {
460
  // The coroutine statement, co_return, co_await, or co_yield.
461
  const Stmt *CoroStmt = nullptr;
462
  // Find the first coroutine statement after the DeadStmt in the block.
463
  bool AfterDeadStmt = false;
464
  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I != E;
465
       ++I)
466
    if (std::optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
467
      const Stmt *S = CS->getStmt();
468
      if (S == DeadStmt)
469
        AfterDeadStmt = true;
470
      if (AfterDeadStmt &&
471
          // For simplicity, we only check simple coroutine statements.
472
          (llvm::isa<CoreturnStmt>(S) || llvm::isa<CoroutineSuspendExpr>(S))) {
473
        CoroStmt = S;
474
        break;
475
      }
476
    }
477
  if (!CoroStmt)
478
    return false;
479
  struct Checker : RecursiveASTVisitor<Checker> {
480
    const Stmt *DeadStmt;
481
    bool CoroutineSubStmt = false;
482
    Checker(const Stmt *S) : DeadStmt(S) {}
483
    bool VisitStmt(const Stmt *S) {
484
      if (S == DeadStmt)
485
        CoroutineSubStmt = true;
486
      return true;
487
    }
488
    // Statements captured in the CFG can be implicit.
489
    bool shouldVisitImplicitCode() const { return true; }
490
  };
491
  Checker checker(DeadStmt);
492
  checker.TraverseStmt(const_cast<Stmt *>(CoroStmt));
493
  return checker.CoroutineSubStmt;
494
}
495

496
static bool isValidDeadStmt(const Stmt *S, const clang::CFGBlock *Block) {
497
  if (S->getBeginLoc().isInvalid())
498
    return false;
499
  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
500
    return BO->getOpcode() != BO_Comma;
501
  // Coroutine statements are never considered dead statements, because removing
502
  // them may change the function semantic if it is the only coroutine statement
503
  // of the coroutine.
504
  return !isInCoroutineStmt(S, Block);
505
}
506

507
const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
508
  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
509
    if (std::optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
510
      const Stmt *S = CS->getStmt();
511
      if (isValidDeadStmt(S, Block))
512
        return S;
513
    }
514

515
  CFGTerminator T = Block->getTerminator();
516
  if (T.isStmtBranch()) {
517
    const Stmt *S = T.getStmt();
518
    if (S && isValidDeadStmt(S, Block))
519
      return S;
520
  }
521

522
  return nullptr;
523
}
524

525
static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
526
                  const std::pair<const CFGBlock *, const Stmt *> *p2) {
527
  if (p1->second->getBeginLoc() < p2->second->getBeginLoc())
528
    return -1;
529
  if (p2->second->getBeginLoc() < p1->second->getBeginLoc())
530
    return 1;
531
  return 0;
532
}
533

534
unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
535
                                     clang::reachable_code::Callback &CB) {
536

537
  unsigned count = 0;
538
  enqueue(Start);
539

540
  while (!WorkList.empty()) {
541
    const CFGBlock *Block = WorkList.pop_back_val();
542

543
    // It is possible that this block has been marked reachable after
544
    // it was enqueued.
545
    if (Reachable[Block->getBlockID()])
546
      continue;
547

548
    // Look for any dead code within the block.
549
    const Stmt *S = findDeadCode(Block);
550

551
    if (!S) {
552
      // No dead code.  Possibly an empty block.  Look at dead predecessors.
553
      for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
554
           E = Block->pred_end(); I != E; ++I) {
555
        if (const CFGBlock *predBlock = *I)
556
          enqueue(predBlock);
557
      }
558
      continue;
559
    }
560

561
    // Specially handle macro-expanded code.
562
    if (S->getBeginLoc().isMacroID()) {
563
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
564
      continue;
565
    }
566

567
    if (isDeadCodeRoot(Block)) {
568
      reportDeadCode(Block, S, CB);
569
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
570
    }
571
    else {
572
      // Record this statement as the possibly best location in a
573
      // strongly-connected component of dead code for emitting a
574
      // warning.
575
      DeferredLocs.push_back(std::make_pair(Block, S));
576
    }
577
  }
578

579
  // If we didn't find a dead root, then report the dead code with the
580
  // earliest location.
581
  if (!DeferredLocs.empty()) {
582
    llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
583
    for (const auto &I : DeferredLocs) {
584
      const CFGBlock *Block = I.first;
585
      if (Reachable[Block->getBlockID()])
586
        continue;
587
      reportDeadCode(Block, I.second, CB);
588
      count += scanMaybeReachableFromBlock(Block, PP, Reachable);
589
    }
590
  }
591

592
  return count;
593
}
594

595
static SourceLocation GetUnreachableLoc(const Stmt *S,
596
                                        SourceRange &R1,
597
                                        SourceRange &R2) {
598
  R1 = R2 = SourceRange();
599

600
  if (const Expr *Ex = dyn_cast<Expr>(S))
601
    S = Ex->IgnoreParenImpCasts();
602

603
  switch (S->getStmtClass()) {
604
    case Expr::BinaryOperatorClass: {
605
      const BinaryOperator *BO = cast<BinaryOperator>(S);
606
      return BO->getOperatorLoc();
607
    }
608
    case Expr::UnaryOperatorClass: {
609
      const UnaryOperator *UO = cast<UnaryOperator>(S);
610
      R1 = UO->getSubExpr()->getSourceRange();
611
      return UO->getOperatorLoc();
612
    }
613
    case Expr::CompoundAssignOperatorClass: {
614
      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
615
      R1 = CAO->getLHS()->getSourceRange();
616
      R2 = CAO->getRHS()->getSourceRange();
617
      return CAO->getOperatorLoc();
618
    }
619
    case Expr::BinaryConditionalOperatorClass:
620
    case Expr::ConditionalOperatorClass: {
621
      const AbstractConditionalOperator *CO =
622
      cast<AbstractConditionalOperator>(S);
623
      return CO->getQuestionLoc();
624
    }
625
    case Expr::MemberExprClass: {
626
      const MemberExpr *ME = cast<MemberExpr>(S);
627
      R1 = ME->getSourceRange();
628
      return ME->getMemberLoc();
629
    }
630
    case Expr::ArraySubscriptExprClass: {
631
      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
632
      R1 = ASE->getLHS()->getSourceRange();
633
      R2 = ASE->getRHS()->getSourceRange();
634
      return ASE->getRBracketLoc();
635
    }
636
    case Expr::CStyleCastExprClass: {
637
      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
638
      R1 = CSC->getSubExpr()->getSourceRange();
639
      return CSC->getLParenLoc();
640
    }
641
    case Expr::CXXFunctionalCastExprClass: {
642
      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
643
      R1 = CE->getSubExpr()->getSourceRange();
644
      return CE->getBeginLoc();
645
    }
646
    case Stmt::CXXTryStmtClass: {
647
      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
648
    }
649
    case Expr::ObjCBridgedCastExprClass: {
650
      const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
651
      R1 = CSC->getSubExpr()->getSourceRange();
652
      return CSC->getLParenLoc();
653
    }
654
    default: ;
655
  }
656
  R1 = S->getSourceRange();
657
  return S->getBeginLoc();
658
}
659

660
void DeadCodeScan::reportDeadCode(const CFGBlock *B,
661
                                  const Stmt *S,
662
                                  clang::reachable_code::Callback &CB) {
663
  // Classify the unreachable code found, or suppress it in some cases.
664
  reachable_code::UnreachableKind UK = reachable_code::UK_Other;
665

666
  if (isa<BreakStmt>(S)) {
667
    UK = reachable_code::UK_Break;
668
  } else if (isTrivialDoWhile(B, S) || isBuiltinUnreachable(S) ||
669
             isBuiltinAssumeFalse(B, S, C)) {
670
    return;
671
  }
672
  else if (isDeadReturn(B, S)) {
673
    UK = reachable_code::UK_Return;
674
  }
675

676
  const auto *AS = dyn_cast<AttributedStmt>(S);
677
  bool HasFallThroughAttr =
678
      AS && hasSpecificAttr<FallThroughAttr>(AS->getAttrs());
679

680
  SourceRange SilenceableCondVal;
681

682
  if (UK == reachable_code::UK_Other) {
683
    // Check if the dead code is part of the "loop target" of
684
    // a for/for-range loop.  This is the block that contains
685
    // the increment code.
686
    if (const Stmt *LoopTarget = B->getLoopTarget()) {
687
      SourceLocation Loc = LoopTarget->getBeginLoc();
688
      SourceRange R1(Loc, Loc), R2;
689

690
      if (const ForStmt *FS = dyn_cast<ForStmt>(LoopTarget)) {
691
        const Expr *Inc = FS->getInc();
692
        Loc = Inc->getBeginLoc();
693
        R2 = Inc->getSourceRange();
694
      }
695

696
      CB.HandleUnreachable(reachable_code::UK_Loop_Increment, Loc,
697
                           SourceRange(), SourceRange(Loc, Loc), R2,
698
                           HasFallThroughAttr);
699
      return;
700
    }
701

702
    // Check if the dead block has a predecessor whose branch has
703
    // a configuration value that *could* be modified to
704
    // silence the warning.
705
    CFGBlock::const_pred_iterator PI = B->pred_begin();
706
    if (PI != B->pred_end()) {
707
      if (const CFGBlock *PredBlock = PI->getPossiblyUnreachableBlock()) {
708
        const Stmt *TermCond =
709
            PredBlock->getTerminatorCondition(/* strip parens */ false);
710
        isConfigurationValue(TermCond, PP, &SilenceableCondVal);
711
      }
712
    }
713
  }
714

715
  SourceRange R1, R2;
716
  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
717
  CB.HandleUnreachable(UK, Loc, SilenceableCondVal, R1, R2, HasFallThroughAttr);
718
}
719

720
//===----------------------------------------------------------------------===//
721
// Reachability APIs.
722
//===----------------------------------------------------------------------===//
723

724
namespace clang { namespace reachable_code {
725

726
void Callback::anchor() { }
727

728
unsigned ScanReachableFromBlock(const CFGBlock *Start,
729
                                llvm::BitVector &Reachable) {
730
  return scanFromBlock(Start, Reachable, /* SourceManager* */ nullptr, false);
731
}
732

733
void FindUnreachableCode(AnalysisDeclContext &AC, Preprocessor &PP,
734
                         Callback &CB) {
735

736
  CFG *cfg = AC.getCFG();
737
  if (!cfg)
738
    return;
739

740
  // Scan for reachable blocks from the entrance of the CFG.
741
  // If there are no unreachable blocks, we're done.
742
  llvm::BitVector reachable(cfg->getNumBlockIDs());
743
  unsigned numReachable =
744
    scanMaybeReachableFromBlock(&cfg->getEntry(), PP, reachable);
745
  if (numReachable == cfg->getNumBlockIDs())
746
    return;
747

748
  // If there aren't explicit EH edges, we should include the 'try' dispatch
749
  // blocks as roots.
750
  if (!AC.getCFGBuildOptions().AddEHEdges) {
751
    for (const CFGBlock *B : cfg->try_blocks())
752
      numReachable += scanMaybeReachableFromBlock(B, PP, reachable);
753
    if (numReachable == cfg->getNumBlockIDs())
754
      return;
755
  }
756

757
  // There are some unreachable blocks.  We need to find the root blocks that
758
  // contain code that should be considered unreachable.
759
  for (const CFGBlock *block : *cfg) {
760
    // A block may have been marked reachable during this loop.
761
    if (reachable[block->getBlockID()])
762
      continue;
763

764
    DeadCodeScan DS(reachable, PP, AC.getASTContext());
765
    numReachable += DS.scanBackwards(block, CB);
766

767
    if (numReachable == cfg->getNumBlockIDs())
768
      return;
769
  }
770
}
771

772
}} // end namespace clang::reachable_code
773