Check in LLVM r95781.
diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp
new file mode 100644
index 0000000..bdc0e7c
--- /dev/null
+++ b/lib/Analysis/UninitializedValues.cpp
@@ -0,0 +1,310 @@
+//==- 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())
+ V(VD,AD) = AD.FullUninitTaint ? V(cast<Expr>(I),AD) : 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