1 files changed, 274 insertions, 248 deletions

diff --git a/clang/lib/Analysis/ReachableCode.cpp b/clang/lib/Analysis/ReachableCode.cpp
index 09abcc9b7dc..f563cbdc593 100644
--- a/clang/lib/Analysis/ReachableCode.cpp
+++ b/clang/lib/Analysis/ReachableCode.cpp
@@ -25,227 +25,9 @@
 
 using namespace clang;
 
-namespace {
-class DeadCodeScan {
-  llvm::BitVector Visited;
-  llvm::BitVector &Reachable;
-  SmallVector<const CFGBlock *, 10> WorkList;
-  
-  typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
-      DeferredLocsTy;
-  
-  DeferredLocsTy DeferredLocs;
-  
-public:
-  DeadCodeScan(llvm::BitVector &reachable)
-    : Visited(reachable.size()),
-      Reachable(reachable) {}
-  
-  void enqueue(const CFGBlock *block);  
-  unsigned scanBackwards(const CFGBlock *Start,
-                         clang::reachable_code::Callback &CB);
-  
-  bool isDeadCodeRoot(const CFGBlock *Block);
-  
-  const Stmt *findDeadCode(const CFGBlock *Block);
-  
-  void reportDeadCode(const CFGBlock *B,
-                      const Stmt *S,
-                      clang::reachable_code::Callback &CB);
-};
-}
-
-void DeadCodeScan::enqueue(const CFGBlock *block) {  
-  unsigned blockID = block->getBlockID();
-  if (Reachable[blockID] || Visited[blockID])
-    return;
-  Visited[blockID] = true;
-  WorkList.push_back(block);
-}
-
-bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
-  bool isDeadRoot = true;
-  
-  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
-        E = Block->pred_end(); I != E; ++I) {
-    if (const CFGBlock *PredBlock = *I) {
-      unsigned blockID = PredBlock->getBlockID();
-      if (Visited[blockID]) {
-        isDeadRoot = false;
-        continue;
-      }
-      if (!Reachable[blockID]) {
-        isDeadRoot = false;
-        Visited[blockID] = true;
-        WorkList.push_back(PredBlock);
-        continue;
-      }
-    }
-  }
-  
-  return isDeadRoot;
-}
-
-static bool isValidDeadStmt(const Stmt *S) {
-  if (S->getLocStart().isInvalid())
-    return false;
-  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
-    return BO->getOpcode() != BO_Comma;
-  return true;
-}
-
-const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
-  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
-    if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
-      const Stmt *S = CS->getStmt();
-      if (isValidDeadStmt(S))
-        return S;
-    }
-  
-  if (CFGTerminator T = Block->getTerminator()) {
-    const Stmt *S = T.getStmt();
-    if (isValidDeadStmt(S))
-      return S;    
-  }
-
-  return 0;
-}
-
-static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
-                  const std::pair<const CFGBlock *, const Stmt *> *p2) {
-  if (p1->second->getLocStart() < p2->second->getLocStart())
-    return -1;
-  if (p2->second->getLocStart() < p1->second->getLocStart())
-    return 1;
-  return 0;
-}
-
-unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
-                                     clang::reachable_code::Callback &CB) {
-
-  unsigned count = 0;
-  enqueue(Start);
-  
-  while (!WorkList.empty()) {
-    const CFGBlock *Block = WorkList.pop_back_val();
-
-    // It is possible that this block has been marked reachable after
-    // it was enqueued.
-    if (Reachable[Block->getBlockID()])
-      continue;
-
-    // Look for any dead code within the block.
-    const Stmt *S = findDeadCode(Block);
-    
-    if (!S) {
-      // No dead code.  Possibly an empty block.  Look at dead predecessors.
-      for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
-           E = Block->pred_end(); I != E; ++I) {
-        if (const CFGBlock *predBlock = *I)
-          enqueue(predBlock);
-      }
-      continue;
-    }
-    
-    // Specially handle macro-expanded code.
-    if (S->getLocStart().isMacroID()) {
-      count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
-      continue;
-    }
-
-    if (isDeadCodeRoot(Block)) {
-      reportDeadCode(Block, S, CB);
-      count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
-    }
-    else {
-      // Record this statement as the possibly best location in a
-      // strongly-connected component of dead code for emitting a
-      // warning.
-      DeferredLocs.push_back(std::make_pair(Block, S));
-    }
-  }
-
-  // If we didn't find a dead root, then report the dead code with the
-  // earliest location.
-  if (!DeferredLocs.empty()) {
-    llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
-    for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
-          E = DeferredLocs.end(); I != E; ++I) {
-      const CFGBlock *Block = I->first;
-      if (Reachable[Block->getBlockID()])
-        continue;
-      reportDeadCode(Block, I->second, CB);
-      count += clang::reachable_code::ScanReachableFromBlock(Block, Reachable);
-    }
-  }
-    
-  return count;
-}
-
-static SourceLocation GetUnreachableLoc(const Stmt *S,
-                                        SourceRange &R1,
-                                        SourceRange &R2) {
-  R1 = R2 = SourceRange();
-
-  if (const Expr *Ex = dyn_cast<Expr>(S))
-    S = Ex->IgnoreParenImpCasts();
-
-  switch (S->getStmtClass()) {
-    case Expr::BinaryOperatorClass: {
-      const BinaryOperator *BO = cast<BinaryOperator>(S);
-      return BO->getOperatorLoc();
-    }
-    case Expr::UnaryOperatorClass: {
-      const UnaryOperator *UO = cast<UnaryOperator>(S);
-      R1 = UO->getSubExpr()->getSourceRange();
-      return UO->getOperatorLoc();
-    }
-    case Expr::CompoundAssignOperatorClass: {
-      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
-      R1 = CAO->getLHS()->getSourceRange();
-      R2 = CAO->getRHS()->getSourceRange();
-      return CAO->getOperatorLoc();
-    }
-    case Expr::BinaryConditionalOperatorClass:
-    case Expr::ConditionalOperatorClass: {
-      const AbstractConditionalOperator *CO =
-        cast<AbstractConditionalOperator>(S);
-      return CO->getQuestionLoc();
-    }
-    case Expr::MemberExprClass: {
-      const MemberExpr *ME = cast<MemberExpr>(S);
-      R1 = ME->getSourceRange();
-      return ME->getMemberLoc();
-    }
-    case Expr::ArraySubscriptExprClass: {
-      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
-      R1 = ASE->getLHS()->getSourceRange();
-      R2 = ASE->getRHS()->getSourceRange();
-      return ASE->getRBracketLoc();
-    }
-    case Expr::CStyleCastExprClass: {
-      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
-      R1 = CSC->getSubExpr()->getSourceRange();
-      return CSC->getLParenLoc();
-    }
-    case Expr::CXXFunctionalCastExprClass: {
-      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
-      R1 = CE->getSubExpr()->getSourceRange();
-      return CE->getLocStart();
-    }
-    case Stmt::CXXTryStmtClass: {
-      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
-    }
-    case Expr::ObjCBridgedCastExprClass: {
-      const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
-      R1 = CSC->getSubExpr()->getSourceRange();
-      return CSC->getLParenLoc();
-    }
-    default: ;
-  }
-  R1 = S->getSourceRange();
-  return S->getLocStart();
-}
+//===----------------------------------------------------------------------===//
+// Core Reachability Analysis routines.
+//===----------------------------------------------------------------------===//
 
 static bool bodyEndsWithNoReturn(const CFGBlock *B) {
   for (CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
@@ -385,28 +167,6 @@ static bool isTrivialReturnOrDoWhile(const CFGBlock *B, const Stmt *S) {
   return false;
 }
 
-void DeadCodeScan::reportDeadCode(const CFGBlock *B,
-                                  const Stmt *S,
-                                  clang::reachable_code::Callback &CB) {
-  // Suppress idiomatic cases of calling a noreturn function just
-  // before executing a 'break'.  If there is other code after the 'break'
-  // in the block then don't suppress the warning.
-  if (isBreakPrecededByNoReturn(B, S))
-    return;
-
-  // Suppress trivial 'return' statements that are dead.
-  if (isTrivialReturnOrDoWhile(B, S))
-    return;
-
-  SourceRange R1, R2;
-  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
-  CB.HandleUnreachable(Loc, R1, R2);
-}
-
-namespace clang { namespace reachable_code {
-
-void Callback::anchor() { }  
-
 /// Returns true if the statement is expanded from a configuration macro.
 static bool isExpandedFromConfigurationMacro(const Stmt *S) {
   // FIXME: This is not very precise.  Here we just check to see if the
@@ -470,8 +230,9 @@ static bool shouldTreatSuccessorsAsReachable(const CFGBlock *B) {
   return isConfigurationValue(B->getTerminatorCondition());
 }
 
-unsigned ScanReachableFromBlock(const CFGBlock *Start,
-                                llvm::BitVector &Reachable) {
+static unsigned scanFromBlock(const CFGBlock *Start,
+                              llvm::BitVector &Reachable,
+                              bool IncludeSometimesUnreachableEdges) {
   unsigned count = 0;
   
   // Prep work queue
@@ -497,6 +258,8 @@ unsigned ScanReachableFromBlock(const CFGBlock *Start,
     // within the "sometimes unreachable" code.
     // Look at the successors and mark then reachable.
     Optional<bool> TreatAllSuccessorsAsReachable;
+    if (!IncludeSometimesUnreachableEdges)
+      TreatAllSuccessorsAsReachable = false;
 
     for (CFGBlock::const_succ_iterator I = item->succ_begin(), 
          E = item->succ_end(); I != E; ++I) {
@@ -529,7 +292,269 @@ unsigned ScanReachableFromBlock(const CFGBlock *Start,
   }
   return count;
 }
-  
+
+static unsigned scanMaybeReachableFromBlock(const CFGBlock *Start,
+                                            llvm::BitVector &Reachable) {
+  return scanFromBlock(Start, Reachable, true);
+}
+
+//===----------------------------------------------------------------------===//
+// Dead Code Scanner.
+//===----------------------------------------------------------------------===//
+
+namespace {
+  class DeadCodeScan {
+    llvm::BitVector Visited;
+    llvm::BitVector &Reachable;
+    SmallVector<const CFGBlock *, 10> WorkList;
+
+    typedef SmallVector<std::pair<const CFGBlock *, const Stmt *>, 12>
+    DeferredLocsTy;
+
+    DeferredLocsTy DeferredLocs;
+
+  public:
+    DeadCodeScan(llvm::BitVector &reachable)
+    : Visited(reachable.size()),
+    Reachable(reachable) {}
+
+    void enqueue(const CFGBlock *block);
+    unsigned scanBackwards(const CFGBlock *Start,
+    clang::reachable_code::Callback &CB);
+
+    bool isDeadCodeRoot(const CFGBlock *Block);
+
+    const Stmt *findDeadCode(const CFGBlock *Block);
+
+    void reportDeadCode(const CFGBlock *B,
+    const Stmt *S,
+    clang::reachable_code::Callback &CB);
+    };
+}
+
+void DeadCodeScan::enqueue(const CFGBlock *block) {
+  unsigned blockID = block->getBlockID();
+  if (Reachable[blockID] || Visited[blockID])
+    return;
+  Visited[blockID] = true;
+  WorkList.push_back(block);
+}
+
+bool DeadCodeScan::isDeadCodeRoot(const clang::CFGBlock *Block) {
+  bool isDeadRoot = true;
+
+  for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
+       E = Block->pred_end(); I != E; ++I) {
+    if (const CFGBlock *PredBlock = *I) {
+      unsigned blockID = PredBlock->getBlockID();
+      if (Visited[blockID]) {
+        isDeadRoot = false;
+        continue;
+      }
+      if (!Reachable[blockID]) {
+        isDeadRoot = false;
+        Visited[blockID] = true;
+        WorkList.push_back(PredBlock);
+        continue;
+      }
+    }
+  }
+
+  return isDeadRoot;
+}
+
+static bool isValidDeadStmt(const Stmt *S) {
+  if (S->getLocStart().isInvalid())
+    return false;
+  if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(S))
+    return BO->getOpcode() != BO_Comma;
+  return true;
+}
+
+const Stmt *DeadCodeScan::findDeadCode(const clang::CFGBlock *Block) {
+  for (CFGBlock::const_iterator I = Block->begin(), E = Block->end(); I!=E; ++I)
+    if (Optional<CFGStmt> CS = I->getAs<CFGStmt>()) {
+      const Stmt *S = CS->getStmt();
+      if (isValidDeadStmt(S))
+        return S;
+    }
+
+  if (CFGTerminator T = Block->getTerminator()) {
+    const Stmt *S = T.getStmt();
+    if (isValidDeadStmt(S))
+      return S;
+  }
+
+  return 0;
+}
+
+static int SrcCmp(const std::pair<const CFGBlock *, const Stmt *> *p1,
+                  const std::pair<const CFGBlock *, const Stmt *> *p2) {
+  if (p1->second->getLocStart() < p2->second->getLocStart())
+    return -1;
+  if (p2->second->getLocStart() < p1->second->getLocStart())
+    return 1;
+  return 0;
+}
+
+unsigned DeadCodeScan::scanBackwards(const clang::CFGBlock *Start,
+                                     clang::reachable_code::Callback &CB) {
+
+  unsigned count = 0;
+  enqueue(Start);
+
+  while (!WorkList.empty()) {
+    const CFGBlock *Block = WorkList.pop_back_val();
+
+    // It is possible that this block has been marked reachable after
+    // it was enqueued.
+    if (Reachable[Block->getBlockID()])
+      continue;
+
+    // Look for any dead code within the block.
+    const Stmt *S = findDeadCode(Block);
+
+    if (!S) {
+      // No dead code.  Possibly an empty block.  Look at dead predecessors.
+      for (CFGBlock::const_pred_iterator I = Block->pred_begin(),
+           E = Block->pred_end(); I != E; ++I) {
+        if (const CFGBlock *predBlock = *I)
+          enqueue(predBlock);
+      }
+      continue;
+    }
+
+    // Specially handle macro-expanded code.
+    if (S->getLocStart().isMacroID()) {
+      count += scanMaybeReachableFromBlock(Block, Reachable);
+      continue;
+    }
+
+    if (isDeadCodeRoot(Block)) {
+      reportDeadCode(Block, S, CB);
+      count += scanMaybeReachableFromBlock(Block, Reachable);
+    }
+    else {
+      // Record this statement as the possibly best location in a
+      // strongly-connected component of dead code for emitting a
+      // warning.
+      DeferredLocs.push_back(std::make_pair(Block, S));
+    }
+  }
+
+  // If we didn't find a dead root, then report the dead code with the
+  // earliest location.
+  if (!DeferredLocs.empty()) {
+    llvm::array_pod_sort(DeferredLocs.begin(), DeferredLocs.end(), SrcCmp);
+    for (DeferredLocsTy::iterator I = DeferredLocs.begin(),
+         E = DeferredLocs.end(); I != E; ++I) {
+      const CFGBlock *Block = I->first;
+      if (Reachable[Block->getBlockID()])
+        continue;
+      reportDeadCode(Block, I->second, CB);
+      count += scanMaybeReachableFromBlock(Block, Reachable);
+    }
+  }
+
+  return count;
+}
+
+static SourceLocation GetUnreachableLoc(const Stmt *S,
+                                        SourceRange &R1,
+                                        SourceRange &R2) {
+  R1 = R2 = SourceRange();
+
+  if (const Expr *Ex = dyn_cast<Expr>(S))
+    S = Ex->IgnoreParenImpCasts();
+
+  switch (S->getStmtClass()) {
+    case Expr::BinaryOperatorClass: {
+      const BinaryOperator *BO = cast<BinaryOperator>(S);
+      return BO->getOperatorLoc();
+    }
+    case Expr::UnaryOperatorClass: {
+      const UnaryOperator *UO = cast<UnaryOperator>(S);
+      R1 = UO->getSubExpr()->getSourceRange();
+      return UO->getOperatorLoc();
+    }
+    case Expr::CompoundAssignOperatorClass: {
+      const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S);
+      R1 = CAO->getLHS()->getSourceRange();
+      R2 = CAO->getRHS()->getSourceRange();
+      return CAO->getOperatorLoc();
+    }
+    case Expr::BinaryConditionalOperatorClass:
+    case Expr::ConditionalOperatorClass: {
+      const AbstractConditionalOperator *CO =
+      cast<AbstractConditionalOperator>(S);
+      return CO->getQuestionLoc();
+    }
+    case Expr::MemberExprClass: {
+      const MemberExpr *ME = cast<MemberExpr>(S);
+      R1 = ME->getSourceRange();
+      return ME->getMemberLoc();
+    }
+    case Expr::ArraySubscriptExprClass: {
+      const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S);
+      R1 = ASE->getLHS()->getSourceRange();
+      R2 = ASE->getRHS()->getSourceRange();
+      return ASE->getRBracketLoc();
+    }
+    case Expr::CStyleCastExprClass: {
+      const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S);
+      R1 = CSC->getSubExpr()->getSourceRange();
+      return CSC->getLParenLoc();
+    }
+    case Expr::CXXFunctionalCastExprClass: {
+      const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S);
+      R1 = CE->getSubExpr()->getSourceRange();
+      return CE->getLocStart();
+    }
+    case Stmt::CXXTryStmtClass: {
+      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
+    }
+    case Expr::ObjCBridgedCastExprClass: {
+      const ObjCBridgedCastExpr *CSC = cast<ObjCBridgedCastExpr>(S);
+      R1 = CSC->getSubExpr()->getSourceRange();
+      return CSC->getLParenLoc();
+    }
+    default: ;
+  }
+  R1 = S->getSourceRange();
+  return S->getLocStart();
+}
+
+void DeadCodeScan::reportDeadCode(const CFGBlock *B,
+                                  const Stmt *S,
+                                  clang::reachable_code::Callback &CB) {
+  // Suppress idiomatic cases of calling a noreturn function just
+  // before executing a 'break'.  If there is other code after the 'break'
+  // in the block then don't suppress the warning.
+  if (isBreakPrecededByNoReturn(B, S))
+    return;
+
+  // Suppress trivial 'return' statements that are dead.
+  if (isTrivialReturnOrDoWhile(B, S))
+    return;
+
+  SourceRange R1, R2;
+  SourceLocation Loc = GetUnreachableLoc(S, R1, R2);
+  CB.HandleUnreachable(Loc, R1, R2);
+}
+
+//===----------------------------------------------------------------------===//
+// Reachability APIs.
+//===----------------------------------------------------------------------===//
+
+namespace clang { namespace reachable_code {
+
+void Callback::anchor() { }
+
+unsigned ScanReachableFromBlock(const CFGBlock *Start,
+                                llvm::BitVector &Reachable) {
+  return scanFromBlock(Start, Reachable, false);
+}
+
 void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
   CFG *cfg = AC.getCFG();
   if (!cfg)
@@ -538,7 +563,8 @@ void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
   // Scan for reachable blocks from the entrance of the CFG.  
   // If there are no unreachable blocks, we're done.
   llvm::BitVector reachable(cfg->getNumBlockIDs());
-  unsigned numReachable = ScanReachableFromBlock(&cfg->getEntry(), reachable);
+  unsigned numReachable =
+    scanMaybeReachableFromBlock(&cfg->getEntry(), reachable);
   if (numReachable == cfg->getNumBlockIDs())
     return;
   
@@ -547,7 +573,7 @@ void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) {
   if (!AC.getCFGBuildOptions().AddEHEdges) {
     for (CFG::try_block_iterator I = cfg->try_blocks_begin(),
          E = cfg->try_blocks_end() ; I != E; ++I) {
-      numReachable += ScanReachableFromBlock(*I, reachable);
+      numReachable += scanMaybeReachableFromBlock(*I, reachable);
     }
     if (numReachable == cfg->getNumBlockIDs())
       return;