1 files changed, 314 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp
new file mode 100644
index 0000000..7a62864
--- /dev/null
+++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp
@@ -0,0 +1,314 @@
+//==- UninitializedValues.cpp - Find Uninitialized Values -------*- 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 Uninitialized Values analysis for source-level CFGs.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/Analyses/UninitializedValues.h"
+#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h"
+#include "clang/Analysis/AnalysisDiagnostic.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/Analysis/FlowSensitive/DataflowSolver.h"
+
+#include "llvm/ADT/SmallPtrSet.h"
+
+using namespace clang;
+
+//===----------------------------------------------------------------------===//
+// Dataflow initialization logic.
+//===----------------------------------------------------------------------===//
+
+namespace {
+
+class RegisterDecls
+  : public CFGRecStmtDeclVisitor<RegisterDecls> {
+
+  UninitializedValues::AnalysisDataTy& AD;
+public:
+  RegisterDecls(UninitializedValues::AnalysisDataTy& ad) :  AD(ad) {}
+
+  void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
+  CFG& getCFG() { return AD.getCFG(); }
+};
+
+} // end anonymous namespace
+
+void UninitializedValues::InitializeValues(const CFG& cfg) {
+  RegisterDecls R(getAnalysisData());
+  cfg.VisitBlockStmts(R);
+}
+
+//===----------------------------------------------------------------------===//
+// Transfer functions.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class TransferFuncs
+  : public CFGStmtVisitor<TransferFuncs,bool> {
+
+  UninitializedValues::ValTy V;
+  UninitializedValues::AnalysisDataTy& AD;
+public:
+  TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {}
+
+  UninitializedValues::ValTy& getVal() { return V; }
+  CFG& getCFG() { return AD.getCFG(); }
+
+  void SetTopValue(UninitializedValues::ValTy& X) {
+    X.setDeclValues(AD);
+    X.resetBlkExprValues(AD);
+  }
+
+  bool VisitDeclRefExpr(DeclRefExpr* DR);
+  bool VisitBinaryOperator(BinaryOperator* B);
+  bool VisitUnaryOperator(UnaryOperator* U);
+  bool VisitStmt(Stmt* S);
+  bool VisitCallExpr(CallExpr* C);
+  bool VisitDeclStmt(DeclStmt* D);
+  bool VisitConditionalOperator(ConditionalOperator* C);
+  bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
+
+  bool Visit(Stmt *S);
+  bool BlockStmt_VisitExpr(Expr* E);
+
+  void VisitTerminator(CFGBlock* B) { }
+};
+
+static const bool Initialized = false;
+static const bool Uninitialized = true;
+
+bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+
+  if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
+    if (VD->isBlockVarDecl()) {
+
+      if (AD.Observer)
+        AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD);
+
+      // Pseudo-hack to prevent cascade of warnings.  If an accessed variable
+      // is uninitialized, then we are already going to flag a warning for
+      // this variable, which a "source" of uninitialized values.
+      // We can otherwise do a full "taint" of uninitialized values.  The
+      // client has both options by toggling AD.FullUninitTaint.
+
+      if (AD.FullUninitTaint)
+        return V(VD,AD);
+    }
+
+  return Initialized;
+}
+
+static VarDecl* FindBlockVarDecl(Expr* E) {
+
+  // Blast through casts and parentheses to find any DeclRefExprs that
+  // refer to a block VarDecl.
+
+  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
+    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
+      if (VD->isBlockVarDecl()) return VD;
+
+  return NULL;
+}
+
+bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
+
+  if (VarDecl* VD = FindBlockVarDecl(B->getLHS()))
+    if (B->isAssignmentOp()) {
+      if (B->getOpcode() == BinaryOperator::Assign)
+        return V(VD,AD) = Visit(B->getRHS());
+      else // Handle +=, -=, *=, etc.  We do want '&', not '&&'.
+        return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS());
+    }
+
+  return VisitStmt(B);
+}
+
+bool TransferFuncs::VisitDeclStmt(DeclStmt* S) {
+  for (DeclStmt::decl_iterator I=S->decl_begin(), E=S->decl_end(); I!=E; ++I) {
+    VarDecl *VD = dyn_cast<VarDecl>(*I);
+    if (VD && VD->isBlockVarDecl()) {
+      if (Stmt* I = VD->getInit()) {
+        // Visit the subexpression to check for uses of uninitialized values,
+        // even if we don't propagate that value.
+        bool isSubExprUninit = Visit(I);
+        V(VD,AD) = AD.FullUninitTaint ? isSubExprUninit : Initialized;
+      }
+      else {
+        // Special case for declarations of array types.  For things like:
+        //
+        //  char x[10];
+        //
+        // we should treat "x" as being initialized, because the variable
+        // "x" really refers to the memory block.  Clearly x[1] is
+        // uninitialized, but expressions like "(char *) x" really do refer to
+        // an initialized value.  This simple dataflow analysis does not reason
+        // about the contents of arrays, although it could be potentially
+        // extended to do so if the array were of constant size.
+        if (VD->getType()->isArrayType())
+          V(VD,AD) = Initialized;
+        else
+          V(VD,AD) = Uninitialized;
+      }
+    }
+  }
+  return Uninitialized; // Value is never consumed.
+}
+
+bool TransferFuncs::VisitCallExpr(CallExpr* C) {
+  VisitChildren(C);
+  return Initialized;
+}
+
+bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
+  switch (U->getOpcode()) {
+    case UnaryOperator::AddrOf: {
+      VarDecl* VD = FindBlockVarDecl(U->getSubExpr());
+      if (VD && VD->isBlockVarDecl())
+        return V(VD,AD) = Initialized;
+      break;
+    }
+
+    default:
+      break;
+  }
+
+  return Visit(U->getSubExpr());
+}
+
+bool
+TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
+  // This represents a use of the 'collection'
+  bool x = Visit(S->getCollection());
+
+  if (x == Uninitialized)
+    return Uninitialized;
+
+  // This represents an initialization of the 'element' value.
+  Stmt* Element = S->getElement();
+  VarDecl* VD = 0;
+
+  if (DeclStmt* DS = dyn_cast<DeclStmt>(Element))
+    VD = cast<VarDecl>(DS->getSingleDecl());
+  else {
+    Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens();
+
+    // Initialize the value of the reference variable.
+    if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(ElemExpr))
+      VD = cast<VarDecl>(DR->getDecl());
+    else
+      return Visit(ElemExpr);
+  }
+
+  V(VD,AD) = Initialized;
+  return Initialized;
+}
+
+
+bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) {
+  Visit(C->getCond());
+
+  bool rhsResult = Visit(C->getRHS());
+  // Handle the GNU extension for missing LHS.
+  if (Expr *lhs = C->getLHS())
+    return Visit(lhs) & rhsResult; // Yes: we want &, not &&.
+  else
+    return rhsResult;
+}
+
+bool TransferFuncs::VisitStmt(Stmt* S) {
+  bool x = Initialized;
+
+  // We don't stop at the first subexpression that is Uninitialized because
+  // evaluating some subexpressions may result in propogating "Uninitialized"
+  // or "Initialized" to variables referenced in the other subexpressions.
+  for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I)
+    if (*I && Visit(*I) == Uninitialized) x = Uninitialized;
+
+  return x;
+}
+
+bool TransferFuncs::Visit(Stmt *S) {
+  if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD);
+  else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S);
+}
+
+bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) {
+  bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E);
+  if (AD.isTracked(E)) V(E,AD) = x;
+  return x;
+}
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Merge operator.
+//
+//  In our transfer functions we take the approach that any
+//  combination of uninitialized values, e.g.
+//      Uninitialized + ___ = Uninitialized.
+//
+//  Merges take the same approach, preferring soundness.  At a confluence point,
+//  if any predecessor has a variable marked uninitialized, the value is
+//  uninitialized at the confluence point.
+//===----------------------------------------------------------------------===//
+
+namespace {
+  typedef StmtDeclBitVector_Types::Union Merge;
+  typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver;
+}
+
+//===----------------------------------------------------------------------===//
+// Uninitialized values checker.   Scan an AST and flag variable uses
+//===----------------------------------------------------------------------===//
+
+UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
+
+namespace {
+class UninitializedValuesChecker
+  : public UninitializedValues::ObserverTy {
+
+  ASTContext &Ctx;
+  Diagnostic &Diags;
+  llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned;
+
+public:
+  UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags)
+    : Ctx(ctx), Diags(diags) {}
+
+  virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V,
+                                  UninitializedValues::AnalysisDataTy& AD,
+                                  DeclRefExpr* DR, VarDecl* VD) {
+
+    assert ( AD.isTracked(VD) && "Unknown VarDecl.");
+
+    if (V(VD,AD) == Uninitialized)
+      if (AlreadyWarned.insert(VD))
+        Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
+                     diag::warn_uninit_val);
+  }
+};
+} // end anonymous namespace
+
+namespace clang {
+void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags,
+                              bool FullUninitTaint) {
+
+  // Compute the uninitialized values information.
+  UninitializedValues U(cfg);
+  U.getAnalysisData().FullUninitTaint = FullUninitTaint;
+  Solver S(U);
+  S.runOnCFG(cfg);
+
+  // Scan for DeclRefExprs that use uninitialized values.
+  UninitializedValuesChecker Observer(Ctx,Diags);
+  U.getAnalysisData().Observer = &Observer;
+  S.runOnAllBlocks(cfg);
+}
+} // end namespace clang