1 files changed, 278 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp
new file mode 100644
index 0000000..f959e5c
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp
@@ -0,0 +1,278 @@
+//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a flow-sensitive, path-insensitive analysis of
+// determining reachable blocks within a CFG.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/SmallVector.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/Analysis/Analyses/ReachableCode.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Basic/SourceManager.h"
+
+using namespace clang;
+
+static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1,
+                                        SourceRange &R2) {
+  const Stmt *S = 0;
+  unsigned sn = 0;
+  R1 = R2 = SourceRange();
+
+top:
+  if (sn < b.size())
+    S = b[sn].getStmt();
+  else if (b.getTerminator())
+    S = b.getTerminator();
+  else
+    return SourceLocation();
+
+  switch (S->getStmtClass()) {
+    case Expr::BinaryOperatorClass: {
+      const BinaryOperator *BO = cast<BinaryOperator>(S);
+      if (BO->getOpcode() == BinaryOperator::Comma) {
+        if (sn+1 < b.size())
+          return b[sn+1].getStmt()->getLocStart();
+        const CFGBlock *n = &b;
+        while (1) {
+          if (n->getTerminator())
+            return n->getTerminator()->getLocStart();
+          if (n->succ_size() != 1)
+            return SourceLocation();
+          n = n[0].succ_begin()[0];
+          if (n->pred_size() != 1)
+            return SourceLocation();
+          if (!n->empty())
+            return n[0][0].getStmt()->getLocStart();
+        }
+      }
+      R1 = BO->getLHS()->getSourceRange();
+      R2 = BO->getRHS()->getSourceRange();
+      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::ConditionalOperatorClass: {
+      const ConditionalOperator *CO = cast<ConditionalOperator>(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->getTypeBeginLoc();
+    }
+    case Expr::ImplicitCastExprClass:
+      ++sn;
+      goto top;
+    case Stmt::CXXTryStmtClass: {
+      return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc();
+    }
+    default: ;
+  }
+  R1 = S->getSourceRange();
+  return S->getLocStart();
+}
+
+static SourceLocation MarkLiveTop(const CFGBlock *Start,
+                                  llvm::BitVector &reachable,
+                                  SourceManager &SM) {
+
+  // Prep work worklist.
+  llvm::SmallVector<const CFGBlock*, 32> WL;
+  WL.push_back(Start);
+
+  SourceRange R1, R2;
+  SourceLocation top = GetUnreachableLoc(*Start, R1, R2);
+
+  bool FromMainFile = false;
+  bool FromSystemHeader = false;
+  bool TopValid = false;
+
+  if (top.isValid()) {
+    FromMainFile = SM.isFromMainFile(top);
+    FromSystemHeader = SM.isInSystemHeader(top);
+    TopValid = true;
+  }
+
+  // Solve
+  while (!WL.empty()) {
+    const CFGBlock *item = WL.back();
+    WL.pop_back();
+
+    SourceLocation c = GetUnreachableLoc(*item, R1, R2);
+    if (c.isValid()
+        && (!TopValid
+            || (SM.isFromMainFile(c) && !FromMainFile)
+            || (FromSystemHeader && !SM.isInSystemHeader(c))
+            || SM.isBeforeInTranslationUnit(c, top))) {
+          top = c;
+          FromMainFile = SM.isFromMainFile(top);
+          FromSystemHeader = SM.isInSystemHeader(top);
+        }
+
+    reachable.set(item->getBlockID());
+    for (CFGBlock::const_succ_iterator I=item->succ_begin(), E=item->succ_end();
+         I != E; ++I)
+      if (const CFGBlock *B = *I) {
+        unsigned blockID = B->getBlockID();
+        if (!reachable[blockID]) {
+          reachable.set(blockID);
+          WL.push_back(B);
+        }
+      }
+  }
+
+  return top;
+}
+
+static int LineCmp(const void *p1, const void *p2) {
+  SourceLocation *Line1 = (SourceLocation *)p1;
+  SourceLocation *Line2 = (SourceLocation *)p2;
+  return !(*Line1 < *Line2);
+}
+
+namespace {
+struct ErrLoc {
+  SourceLocation Loc;
+  SourceRange R1;
+  SourceRange R2;
+  ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2)
+  : Loc(l), R1(r1), R2(r2) { }
+};
+}
+namespace clang { namespace reachable_code {
+
+/// ScanReachableFromBlock - Mark all blocks reachable from Start.
+/// Returns the total number of blocks that were marked reachable.
+unsigned ScanReachableFromBlock(const CFGBlock &Start,
+                                llvm::BitVector &Reachable) {
+  unsigned count = 0;
+  llvm::SmallVector<const CFGBlock*, 32> WL;
+
+    // Prep work queue
+  Reachable.set(Start.getBlockID());
+  ++count;
+  WL.push_back(&Start);
+
+    // Find the reachable blocks from 'Start'.
+  while (!WL.empty()) {
+    const CFGBlock *item = WL.back();
+    WL.pop_back();
+
+      // Look at the successors and mark then reachable.
+    for (CFGBlock::const_succ_iterator I=item->succ_begin(), E=item->succ_end();
+         I != E; ++I)
+      if (const CFGBlock *B = *I) {
+        unsigned blockID = B->getBlockID();
+        if (!Reachable[blockID]) {
+          Reachable.set(blockID);
+          ++count;
+          WL.push_back(B);
+        }
+      }
+  }
+  return count;
+}
+
+void FindUnreachableCode(AnalysisContext &AC, Callback &CB) {
+  CFG *cfg = AC.getCFG();
+  if (!cfg)
+    return;
+
+  // Scan for reachable blocks.
+  llvm::BitVector reachable(cfg->getNumBlockIDs());
+  unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable);
+
+    // If there are no unreachable blocks, we're done.
+  if (numReachable == cfg->getNumBlockIDs())
+    return;
+
+  SourceRange R1, R2;
+
+  llvm::SmallVector<ErrLoc, 24> lines;
+  bool AddEHEdges = AC.getAddEHEdges();
+
+  // First, give warnings for blocks with no predecessors, as they
+  // can't be part of a loop.
+  for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
+    CFGBlock &b = **I;
+    if (!reachable[b.getBlockID()]) {
+      if (b.pred_empty()) {
+        if (!AddEHEdges && dyn_cast_or_null<CXXTryStmt>(b.getTerminator())) {
+            // When not adding EH edges from calls, catch clauses
+            // can otherwise seem dead.  Avoid noting them as dead.
+          numReachable += ScanReachableFromBlock(b, reachable);
+          continue;
+        }
+        SourceLocation c = GetUnreachableLoc(b, R1, R2);
+        if (!c.isValid()) {
+            // Blocks without a location can't produce a warning, so don't mark
+            // reachable blocks from here as live.
+          reachable.set(b.getBlockID());
+          ++numReachable;
+          continue;
+        }
+        lines.push_back(ErrLoc(c, R1, R2));
+          // Avoid excessive errors by marking everything reachable from here
+        numReachable += ScanReachableFromBlock(b, reachable);
+      }
+    }
+  }
+
+  if (numReachable < cfg->getNumBlockIDs()) {
+      // And then give warnings for the tops of loops.
+    for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) {
+      CFGBlock &b = **I;
+      if (!reachable[b.getBlockID()])
+          // Avoid excessive errors by marking everything reachable from here
+        lines.push_back(ErrLoc(MarkLiveTop(&b, reachable,
+                                         AC.getASTContext().getSourceManager()),
+                               SourceRange(), SourceRange()));
+    }
+  }
+
+  llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp);
+
+  for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end();
+       I != E; ++I)
+    if (I->Loc.isValid())
+      CB.HandleUnreachable(I->Loc, I->R1, I->R2);
+}
+
+}} // end namespace clang::reachable_code