Vendor import of clang trunk r130700:

http://llvm.org/svn/llvm-project/cfe/trunk@130700

1 files changed, 643 insertions, 231 deletions

diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp
index c08cbed..88a2db7 100644
--- a/lib/Analysis/UninitializedValues.cpp
+++ b/lib/Analysis/UninitializedValues.cpp
@@ -7,311 +7,723 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements Uninitialized Values analysis for source-level CFGs.
+// This file implements uninitialized values analysis for source-level CFGs.
 //
 //===----------------------------------------------------------------------===//
 
-#include "clang/Analysis/Analyses/UninitializedValues.h"
+#include <utility>
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/AnalysisContext.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"
+#include "clang/Analysis/Analyses/UninitializedValues.h"
+#include "clang/Analysis/Support/SaveAndRestore.h"
 
 using namespace clang;
 
-//===----------------------------------------------------------------------===//
-// Dataflow initialization logic.
-//===----------------------------------------------------------------------===//
-
-namespace {
+static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) {
+  if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() &&
+      !vd->isExceptionVariable() &&
+      vd->getDeclContext() == dc) {
+    QualType ty = vd->getType();
+    return ty->isScalarType() || ty->isVectorType();
+  }
+  return false;
+}
 
-class RegisterDecls
-  : public CFGRecStmtDeclVisitor<RegisterDecls> {
+//------------------------------------------------------------------------====//
+// DeclToIndex: a mapping from Decls we track to value indices.
+//====------------------------------------------------------------------------//
 
-  UninitializedValues::AnalysisDataTy& AD;
+namespace {
+class DeclToIndex {
+  llvm::DenseMap<const VarDecl *, unsigned> map;
 public:
-  RegisterDecls(UninitializedValues::AnalysisDataTy& ad) :  AD(ad) {}
-
-  void VisitVarDecl(VarDecl* VD) { AD.Register(VD); }
-  CFG& getCFG() { return AD.getCFG(); }
+  DeclToIndex() {}
+  
+  /// Compute the actual mapping from declarations to bits.
+  void computeMap(const DeclContext &dc);
+  
+  /// Return the number of declarations in the map.
+  unsigned size() const { return map.size(); }
+  
+  /// Returns the bit vector index for a given declaration.
+  llvm::Optional<unsigned> getValueIndex(const VarDecl *d) const;
 };
+}
 
-} // end anonymous namespace
+void DeclToIndex::computeMap(const DeclContext &dc) {
+  unsigned count = 0;
+  DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()),
+                                               E(dc.decls_end());
+  for ( ; I != E; ++I) {
+    const VarDecl *vd = *I;
+    if (isTrackedVar(vd, &dc))
+      map[vd] = count++;
+  }
+}
 
-void UninitializedValues::InitializeValues(const CFG& cfg) {
-  RegisterDecls R(getAnalysisData());
-  cfg.VisitBlockStmts(R);
+llvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const {
+  llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d);
+  if (I == map.end())
+    return llvm::Optional<unsigned>();
+  return I->second;
 }
 
-//===----------------------------------------------------------------------===//
-// Transfer functions.
-//===----------------------------------------------------------------------===//
+//------------------------------------------------------------------------====//
+// CFGBlockValues: dataflow values for CFG blocks.
+//====------------------------------------------------------------------------//
 
-namespace {
-class TransferFuncs
-  : public CFGStmtVisitor<TransferFuncs,bool> {
+// These values are defined in such a way that a merge can be done using
+// a bitwise OR.
+enum Value { Unknown = 0x0,         /* 00 */
+             Initialized = 0x1,     /* 01 */
+             Uninitialized = 0x2,   /* 10 */
+             MayUninitialized = 0x3 /* 11 */ };
 
-  UninitializedValues::ValTy V;
-  UninitializedValues::AnalysisDataTy& AD;
+static bool isUninitialized(const Value v) {
+  return v >= Uninitialized;
+}
+static bool isAlwaysUninit(const Value v) {
+  return v == Uninitialized;
+}
+
+namespace {
+class ValueVector {
+  llvm::BitVector vec;
 public:
-  TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {}
+  ValueVector() {}
+  ValueVector(unsigned size) : vec(size << 1) {}
+  void resize(unsigned n) { vec.resize(n << 1); }
+  void merge(const ValueVector &rhs) { vec |= rhs.vec; }
+  bool operator!=(const ValueVector &rhs) const { return vec != rhs.vec; }
+  void reset() { vec.reset(); }
+  
+  class reference {
+    ValueVector &vv;
+    const unsigned idx;
+
+    reference();  // Undefined    
+  public:
+    reference(ValueVector &vv, unsigned idx) : vv(vv), idx(idx) {}    
+    ~reference() {}
+    
+    reference &operator=(Value v) {
+      vv.vec[idx << 1] = (((unsigned) v) & 0x1) ? true : false;
+      vv.vec[(idx << 1) | 1] = (((unsigned) v) & 0x2) ? true : false;
+      return *this;
+    }
+    operator Value() {
+      unsigned x = (vv.vec[idx << 1] ? 1 : 0) | (vv.vec[(idx << 1) | 1] ? 2 :0);
+      return (Value) x;      
+    }
+  };
+    
+  reference operator[](unsigned idx) { return reference(*this, idx); }
+};
 
-  UninitializedValues::ValTy& getVal() { return V; }
-  CFG& getCFG() { return AD.getCFG(); }
+typedef std::pair<ValueVector *, ValueVector *> BVPair;
 
-  void SetTopValue(UninitializedValues::ValTy& X) {
-    X.setDeclValues(AD);
-    X.resetBlkExprValues(AD);
+class CFGBlockValues {
+  const CFG &cfg;
+  BVPair *vals;
+  ValueVector scratch;
+  DeclToIndex declToIndex;
+  
+  ValueVector &lazyCreate(ValueVector *&bv);
+public:
+  CFGBlockValues(const CFG &cfg);
+  ~CFGBlockValues();
+  
+  unsigned getNumEntries() const { return declToIndex.size(); }
+  
+  void computeSetOfDeclarations(const DeclContext &dc);  
+  ValueVector &getValueVector(const CFGBlock *block,
+                                const CFGBlock *dstBlock);
+
+  BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate);
+
+  void mergeIntoScratch(ValueVector const &source, bool isFirst);
+  bool updateValueVectorWithScratch(const CFGBlock *block);
+  bool updateValueVectors(const CFGBlock *block, const BVPair &newVals);
+  
+  bool hasNoDeclarations() const {
+    return declToIndex.size() == 0;
   }
+  
+  bool hasEntry(const VarDecl *vd) const {
+    return declToIndex.getValueIndex(vd).hasValue();
+  }
+  
+  bool hasValues(const CFGBlock *block);
+  
+  void resetScratch();
+  ValueVector &getScratch() { return scratch; }
+  
+  ValueVector::reference operator[](const VarDecl *vd);
+};  
+} // end anonymous namespace
 
-  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 VisitAbstractConditionalOperator(AbstractConditionalOperator* C);
-  bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S);
-
-  bool Visit(Stmt *S);
-  bool BlockStmt_VisitExpr(Expr* E);
+CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) {
+  unsigned n = cfg.getNumBlockIDs();
+  if (!n)
+    return;
+  vals = new std::pair<ValueVector*, ValueVector*>[n];
+  memset((void*)vals, 0, sizeof(*vals) * n);
+}
 
-  void VisitTerminator(CFGBlock* B) { }
-    
-  void setCurrentBlock(const CFGBlock *block) {}
-};
+CFGBlockValues::~CFGBlockValues() {
+  unsigned n = cfg.getNumBlockIDs();
+  if (n == 0)
+    return;
+  for (unsigned i = 0; i < n; ++i) {
+    delete vals[i].first;
+    delete vals[i].second;
+  }
+  delete [] vals;
+}
 
-static const bool Initialized = false;
-static const bool Uninitialized = true;
+void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) {
+  declToIndex.computeMap(dc);
+  scratch.resize(declToIndex.size());
+}
 
-bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) {
+ValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) {
+  if (!bv)
+    bv = new ValueVector(declToIndex.size());
+  return *bv;
+}
 
-  if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
-    if (VD->isLocalVarDecl()) {
+/// This function pattern matches for a '&&' or '||' that appears at
+/// the beginning of a CFGBlock that also (1) has a terminator and 
+/// (2) has no other elements.  If such an expression is found, it is returned.
+static BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) {
+  if (block->empty())
+    return 0;
+
+  const CFGStmt *cstmt = block->front().getAs<CFGStmt>();
+  if (!cstmt)
+    return 0;
+
+  BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt->getStmt());
+  
+  if (!b || !b->isLogicalOp())
+    return 0;
+  
+  if (block->pred_size() == 2 &&
+      ((block->succ_size() == 2 && block->getTerminatorCondition() == b) ||
+       block->size() == 1))
+    return b;
+  
+  return 0;
+}
 
-      if (AD.Observer)
-        AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD);
+ValueVector &CFGBlockValues::getValueVector(const CFGBlock *block,
+                                            const CFGBlock *dstBlock) {
+  unsigned idx = block->getBlockID();
+  if (dstBlock && getLogicalOperatorInChain(block)) {
+    if (*block->succ_begin() == dstBlock)
+      return lazyCreate(vals[idx].first);
+    assert(*(block->succ_begin()+1) == dstBlock);
+    return lazyCreate(vals[idx].second);
+  }
 
-      // 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.
+  assert(vals[idx].second == 0);
+  return lazyCreate(vals[idx].first);
+}
 
-      if (AD.FullUninitTaint)
-        return V(VD,AD);
-    }
+bool CFGBlockValues::hasValues(const CFGBlock *block) {
+  unsigned idx = block->getBlockID();
+  return vals[idx].second != 0;  
+}
 
-  return Initialized;
+BVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block,
+                                        bool shouldLazyCreate) {
+  unsigned idx = block->getBlockID();
+  lazyCreate(vals[idx].first);
+  if (shouldLazyCreate)
+    lazyCreate(vals[idx].second);
+  return vals[idx];
 }
 
-static VarDecl* FindBlockVarDecl(Expr* E) {
+void CFGBlockValues::mergeIntoScratch(ValueVector const &source,
+                                      bool isFirst) {
+  if (isFirst)
+    scratch = source;
+  else
+    scratch.merge(source);
+}
+#if 0
+static void printVector(const CFGBlock *block, ValueVector &bv,
+                        unsigned num) {
+  
+  llvm::errs() << block->getBlockID() << " :";
+  for (unsigned i = 0; i < bv.size(); ++i) {
+    llvm::errs() << ' ' << bv[i];
+  }
+  llvm::errs() << " : " << num << '\n';
+}
+#endif
+
+bool CFGBlockValues::updateValueVectorWithScratch(const CFGBlock *block) {
+  ValueVector &dst = getValueVector(block, 0);
+  bool changed = (dst != scratch);
+  if (changed)
+    dst = scratch;
+#if 0
+  printVector(block, scratch, 0);
+#endif
+  return changed;
+}
 
-  // Blast through casts and parentheses to find any DeclRefExprs that
-  // refer to a block VarDecl.
+bool CFGBlockValues::updateValueVectors(const CFGBlock *block,
+                                      const BVPair &newVals) {
+  BVPair &vals = getValueVectors(block, true);
+  bool changed = *newVals.first != *vals.first ||
+                 *newVals.second != *vals.second;
+  *vals.first = *newVals.first;
+  *vals.second = *newVals.second;
+#if 0
+  printVector(block, *vals.first, 1);
+  printVector(block, *vals.second, 2);
+#endif
+  return changed;
+}
 
-  if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()))
-    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
-      if (VD->isLocalVarDecl()) return VD;
+void CFGBlockValues::resetScratch() {
+  scratch.reset();
+}
 
-  return NULL;
+ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) {
+  const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd);
+  assert(idx.hasValue());
+  return scratch[idx.getValue()];
 }
 
-bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) {
+//------------------------------------------------------------------------====//
+// Worklist: worklist for dataflow analysis.
+//====------------------------------------------------------------------------//
 
-  if (VarDecl* VD = FindBlockVarDecl(B->getLHS()))
-    if (B->isAssignmentOp()) {
-      if (B->getOpcode() == BO_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());
-    }
+namespace {
+class DataflowWorklist {
+  llvm::SmallVector<const CFGBlock *, 20> worklist;
+  llvm::BitVector enqueuedBlocks;
+public:
+  DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {}
+  
+  void enqueue(const CFGBlock *block);
+  void enqueueSuccessors(const CFGBlock *block);
+  const CFGBlock *dequeue();
+  
+};
+}
 
-  return VisitStmt(B);
+void DataflowWorklist::enqueue(const CFGBlock *block) {
+  if (!block)
+    return;
+  unsigned idx = block->getBlockID();
+  if (enqueuedBlocks[idx])
+    return;
+  worklist.push_back(block);
+  enqueuedBlocks[idx] = true;
 }
 
-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->isLocalVarDecl()) {
-      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;
-      }
-    }
+void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) {
+  for (CFGBlock::const_succ_iterator I = block->succ_begin(),
+       E = block->succ_end(); I != E; ++I) {
+    enqueue(*I);
   }
-  return Uninitialized; // Value is never consumed.
 }
 
-bool TransferFuncs::VisitCallExpr(CallExpr* C) {
-  VisitChildren(C);
-  return Initialized;
+const CFGBlock *DataflowWorklist::dequeue() {
+  if (worklist.empty())
+    return 0;
+  const CFGBlock *b = worklist.back();
+  worklist.pop_back();
+  enqueuedBlocks[b->getBlockID()] = false;
+  return b;
 }
 
-bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) {
-  switch (U->getOpcode()) {
-    case UO_AddrOf: {
-      VarDecl* VD = FindBlockVarDecl(U->getSubExpr());
-      if (VD && VD->isLocalVarDecl())
-        return V(VD,AD) = Initialized;
-      break;
-    }
+//------------------------------------------------------------------------====//
+// Transfer function for uninitialized values analysis.
+//====------------------------------------------------------------------------//
 
-    default:
-      break;
+namespace {
+class FindVarResult {
+  const VarDecl *vd;
+  const DeclRefExpr *dr;
+public:
+  FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {}
+  
+  const DeclRefExpr *getDeclRefExpr() const { return dr; }
+  const VarDecl *getDecl() const { return vd; }
+};
+  
+class TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> {
+  CFGBlockValues &vals;
+  const CFG &cfg;
+  AnalysisContext &ac;
+  UninitVariablesHandler *handler;
+  const DeclRefExpr *currentDR;
+  const Expr *currentVoidCast;
+  const bool flagBlockUses;
+public:
+  TransferFunctions(CFGBlockValues &vals, const CFG &cfg,
+                    AnalysisContext &ac,
+                    UninitVariablesHandler *handler,
+                    bool flagBlockUses)
+    : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0),
+      currentVoidCast(0), flagBlockUses(flagBlockUses) {}
+  
+  const CFG &getCFG() { return cfg; }
+  void reportUninit(const DeclRefExpr *ex, const VarDecl *vd,
+                    bool isAlwaysUninit);
+
+  void VisitBlockExpr(BlockExpr *be);
+  void VisitDeclStmt(DeclStmt *ds);
+  void VisitDeclRefExpr(DeclRefExpr *dr);
+  void VisitUnaryOperator(UnaryOperator *uo);
+  void VisitBinaryOperator(BinaryOperator *bo);
+  void VisitCastExpr(CastExpr *ce);
+  void VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *se);
+  void VisitCXXTypeidExpr(CXXTypeidExpr *E);
+  void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs);
+  
+  bool isTrackedVar(const VarDecl *vd) {
+    return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl()));
   }
-
-  return Visit(U->getSubExpr());
+  
+  FindVarResult findBlockVarDecl(Expr *ex);
+};
 }
 
-bool
-TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
-  // This represents a use of the 'collection'
-  bool x = Visit(S->getCollection());
+void TransferFunctions::reportUninit(const DeclRefExpr *ex,
+                                     const VarDecl *vd, bool isAlwaysUnit) {
+  if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit);
+}
 
-  if (x == Uninitialized)
-    return Uninitialized;
+FindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) {
+  if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts()))
+    if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl()))
+      if (isTrackedVar(vd))
+        return FindVarResult(vd, dr);  
+  return FindVarResult(0, 0);
+}
 
+void TransferFunctions::BlockStmt_VisitObjCForCollectionStmt(
+    ObjCForCollectionStmt *fs) {
+  
+  Visit(fs->getCollection());
+  
   // 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());
+  Stmt *element = fs->getElement();
+  const VarDecl* vd = 0;
+  
+  if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) {
+    vd = cast<VarDecl>(ds->getSingleDecl());
+    if (!isTrackedVar(vd))
+      vd = 0;
+  }
   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);
+    const FindVarResult &res = findBlockVarDecl(cast<Expr>(element));
+    vd = res.getDecl();
+    if (!vd) {
+      Visit(element);
+      return;
+    }
   }
-
-  V(VD,AD) = Initialized;
-  return Initialized;
+  
+  if (vd)
+    vals[vd] = Initialized;
 }
 
-
-bool TransferFuncs::
-VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
-  Visit(C->getCond());
-
-  bool rhsResult = Visit(C->getFalseExpr());
-  // Handle the GNU extension for missing LHS.
-  if (isa<ConditionalOperator>(C))
-    return Visit(C->getTrueExpr()) & rhsResult; // Yes: we want &, not &&.
-  else
-    return rhsResult;
+void TransferFunctions::VisitBlockExpr(BlockExpr *be) {
+  if (!flagBlockUses || !handler)
+    return;
+  const BlockDecl *bd = be->getBlockDecl();
+  for (BlockDecl::capture_const_iterator i = bd->capture_begin(),
+        e = bd->capture_end() ; i != e; ++i) {
+    const VarDecl *vd = i->getVariable();
+    if (!vd->hasLocalStorage())
+      continue;
+    if (!isTrackedVar(vd))
+      continue;
+    if (i->isByRef()) {
+      vals[vd] = Initialized;
+      continue;
+    }
+    Value v = vals[vd];
+    if (isUninitialized(v))
+      handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v));
+  }
 }
 
-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_range I = S->children(); I; ++I)
-    if (*I && Visit(*I) == Uninitialized) x = Uninitialized;
-
-  return x;
+void TransferFunctions::VisitDeclStmt(DeclStmt *ds) {
+  for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end();
+       DI != DE; ++DI) {
+    if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) {
+      if (isTrackedVar(vd)) {
+        if (Expr *init = vd->getInit()) {
+          Visit(init);
+
+          // If the initializer consists solely of a reference to itself, we
+          // explicitly mark the variable as uninitialized. This allows code
+          // like the following:
+          //
+          //   int x = x;
+          //
+          // to deliberately leave a variable uninitialized. Different analysis
+          // clients can detect this pattern and adjust their reporting
+          // appropriately, but we need to continue to analyze subsequent uses
+          // of the variable.
+          DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(init->IgnoreParenImpCasts());
+          vals[vd] = (DRE && DRE->getDecl() == vd) ? Uninitialized
+                                                   : Initialized;
+        }
+      } else if (Stmt *init = vd->getInit()) {
+        Visit(init);
+      }
+    }
+  }
 }
 
-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);
+void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) {
+  // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast
+  // cannot be block-level expressions.  Therefore, we determine if
+  // a DeclRefExpr is involved in a "load" by comparing it to the current
+  // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
+  // If a DeclRefExpr is not involved in a load, we are essentially computing
+  // its address, either for assignment to a reference or via the '&' operator.
+  // In such cases, treat the variable as being initialized, since this
+  // analysis isn't powerful enough to do alias tracking.
+  if (dr != currentDR)
+    if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl()))
+      if (isTrackedVar(vd))
+        vals[vd] = Initialized;
 }
 
-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;
+void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) {
+  if (bo->isAssignmentOp()) {
+    const FindVarResult &res = findBlockVarDecl(bo->getLHS());
+    if (const VarDecl* vd = res.getDecl()) {
+      // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment"
+      // cannot be block-level expressions.  Therefore, we determine if
+      // a DeclRefExpr is involved in a "load" by comparing it to the current
+      // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
+      SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 
+                                                res.getDeclRefExpr());
+      Visit(bo->getRHS());
+      Visit(bo->getLHS());
+
+      ValueVector::reference val = vals[vd];
+      if (isUninitialized(val)) {
+        if (bo->getOpcode() != BO_Assign)
+          reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val));
+        val = Initialized;
+      }
+      return;
+    }
+  }
+  Visit(bo->getRHS());
+  Visit(bo->getLHS());
 }
 
-} // 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;
+void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) {
+  switch (uo->getOpcode()) {
+    case clang::UO_PostDec:
+    case clang::UO_PostInc:
+    case clang::UO_PreDec:
+    case clang::UO_PreInc: {
+      const FindVarResult &res = findBlockVarDecl(uo->getSubExpr());
+      if (const VarDecl *vd = res.getDecl()) {
+        // We assume that DeclRefExprs wrapped in a unary operator ++/--
+        // cannot be block-level expressions.  Therefore, we determine if
+        // a DeclRefExpr is involved in a "load" by comparing it to the current
+        // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
+        SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 
+                                                  res.getDeclRefExpr());
+        Visit(uo->getSubExpr());
+
+        ValueVector::reference val = vals[vd];
+        if (isUninitialized(val)) {
+          reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val));
+          // Don't cascade warnings.
+          val = Initialized;
+        }
+        return;
+      }
+      break;
+    }
+    default:
+      break;
+  }
+  Visit(uo->getSubExpr());
 }
 
-//===----------------------------------------------------------------------===//
-// Uninitialized values checker.   Scan an AST and flag variable uses
-//===----------------------------------------------------------------------===//
-
-UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {}
-
-namespace {
-class UninitializedValuesChecker
-  : public UninitializedValues::ObserverTy {
+void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) {
+  if (ce->getCastKind() == CK_LValueToRValue) {
+    const FindVarResult &res = findBlockVarDecl(ce->getSubExpr());
+    if (const VarDecl *vd = res.getDecl()) {
+      // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast
+      // cannot be block-level expressions.  Therefore, we determine if
+      // a DeclRefExpr is involved in a "load" by comparing it to the current
+      // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr.
+      // Here we update 'currentDR' to be the one associated with this
+      // lvalue-to-rvalue cast.  Then, when we analyze the DeclRefExpr, we
+      // will know that we are not computing its lvalue for other purposes
+      // than to perform a load.
+      SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, 
+                                                res.getDeclRefExpr());
+      Visit(ce->getSubExpr());
+      if (currentVoidCast != ce) {
+        Value val = vals[vd];
+        if (isUninitialized(val)) {
+          reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val));
+          // Don't cascade warnings.
+          vals[vd] = Initialized;
+        }
+      }
+      return;
+    }
+  }
+  else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) {
+    if (cse->getType()->isVoidType()) {
+      // e.g. (void) x;
+      SaveAndRestore<const Expr *>
+        lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens());
+      Visit(cse->getSubExpr());
+      return;
+    }
+  }
+  Visit(ce->getSubExpr());
+}
 
-  ASTContext &Ctx;
-  Diagnostic &Diags;
-  llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned;
+void TransferFunctions::VisitUnaryExprOrTypeTraitExpr(
+                                          UnaryExprOrTypeTraitExpr *se) {
+  if (se->getKind() == UETT_SizeOf) {
+    if (se->getType()->isConstantSizeType())
+      return;
+    // Handle VLAs.
+    Visit(se->getArgumentExpr());
+  }
+}
 
-public:
-  UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags)
-    : Ctx(ctx), Diags(diags) {}
+void TransferFunctions::VisitCXXTypeidExpr(CXXTypeidExpr *E) {
+  // typeid(expression) is potentially evaluated when the argument is
+  // a glvalue of polymorphic type. (C++ 5.2.8p2-3)
+  if (!E->isTypeOperand() && E->Classify(ac.getASTContext()).isGLValue()) {
+    QualType SubExprTy = E->getExprOperand()->getType();
+    if (const RecordType *Record = SubExprTy->getAs<RecordType>())
+      if (cast<CXXRecordDecl>(Record->getDecl())->isPolymorphic())
+        Visit(E->getExprOperand());
+  }
+}
 
-  virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V,
-                                  UninitializedValues::AnalysisDataTy& AD,
-                                  DeclRefExpr* DR, VarDecl* VD) {
+//------------------------------------------------------------------------====//
+// High-level "driver" logic for uninitialized values analysis.
+//====------------------------------------------------------------------------//
+
+static bool runOnBlock(const CFGBlock *block, const CFG &cfg,
+                       AnalysisContext &ac, CFGBlockValues &vals,
+                       llvm::BitVector &wasAnalyzed,
+                       UninitVariablesHandler *handler = 0,
+                       bool flagBlockUses = false) {
+  
+  wasAnalyzed[block->getBlockID()] = true;
+  
+  if (const BinaryOperator *b = getLogicalOperatorInChain(block)) {
+    CFGBlock::const_pred_iterator itr = block->pred_begin();
+    BVPair vA = vals.getValueVectors(*itr, false);
+    ++itr;
+    BVPair vB = vals.getValueVectors(*itr, false);
+
+    BVPair valsAB;
+    
+    if (b->getOpcode() == BO_LAnd) {
+      // Merge the 'F' bits from the first and second.
+      vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true);
+      vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false);
+      valsAB.first = vA.first;
+      valsAB.second = &vals.getScratch();
+    }
+    else {
+      // Merge the 'T' bits from the first and second.
+      assert(b->getOpcode() == BO_LOr);
+      vals.mergeIntoScratch(*vA.first, true);
+      vals.mergeIntoScratch(*vB.first, false);
+      valsAB.first = &vals.getScratch();
+      valsAB.second = vA.second ? vA.second : vA.first;
+    }
+    return vals.updateValueVectors(block, valsAB);
+  }
 
-    assert ( AD.isTracked(VD) && "Unknown VarDecl.");
+  // Default behavior: merge in values of predecessor blocks.
+  vals.resetScratch();
+  bool isFirst = true;
+  for (CFGBlock::const_pred_iterator I = block->pred_begin(),
+       E = block->pred_end(); I != E; ++I) {
+    vals.mergeIntoScratch(vals.getValueVector(*I, block), isFirst);
+    isFirst = false;
+  }
+  // Apply the transfer function.
+  TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses);
+  for (CFGBlock::const_iterator I = block->begin(), E = block->end(); 
+       I != E; ++I) {
+    if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) {
+      tf.BlockStmt_Visit(cs->getStmt());
+    }
+  }
+  return vals.updateValueVectorWithScratch(block);
+}
 
-    if (V(VD,AD) == Uninitialized)
-      if (AlreadyWarned.insert(VD))
-        Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()),
-                     diag::warn_uninit_val);
+void clang::runUninitializedVariablesAnalysis(const DeclContext &dc,
+                                              const CFG &cfg,
+                                              AnalysisContext &ac,
+                                              UninitVariablesHandler &handler) {
+  CFGBlockValues vals(cfg);
+  vals.computeSetOfDeclarations(dc);
+  if (vals.hasNoDeclarations())
+    return;
+
+  // Mark all variables uninitialized at the entry.
+  const CFGBlock &entry = cfg.getEntry();
+  for (CFGBlock::const_succ_iterator i = entry.succ_begin(), 
+        e = entry.succ_end(); i != e; ++i) {
+    if (const CFGBlock *succ = *i) {
+      ValueVector &vec = vals.getValueVector(&entry, succ);
+      const unsigned n = vals.getNumEntries();
+      for (unsigned j = 0; j < n ; ++j) {
+        vec[j] = Uninitialized;
+      }
+    }
   }
-};
-} // end anonymous namespace
 
-namespace clang {
-void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags,
-                              bool FullUninitTaint) {
+  // Proceed with the workist.
+  DataflowWorklist worklist(cfg);
+  llvm::BitVector previouslyVisited(cfg.getNumBlockIDs());
+  worklist.enqueueSuccessors(&cfg.getEntry());
+  llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false);
+
+  while (const CFGBlock *block = worklist.dequeue()) {
+    // Did the block change?
+    bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed);    
+    if (changed || !previouslyVisited[block->getBlockID()])
+      worklist.enqueueSuccessors(block);    
+    previouslyVisited[block->getBlockID()] = true;
+  }
+  
+  // Run through the blocks one more time, and report uninitialized variabes.
+  for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) {
+    if (wasAnalyzed[(*BI)->getBlockID()])
+      runOnBlock(*BI, cfg, ac, vals, wasAnalyzed, &handler,
+                 /* flagBlockUses */ true);
+  }
+}
 
-  // Compute the uninitialized values information.
-  UninitializedValues U(cfg);
-  U.getAnalysisData().FullUninitTaint = FullUninitTaint;
-  Solver S(U);
-  S.runOnCFG(cfg);
+UninitVariablesHandler::~UninitVariablesHandler() {}
 
-  // Scan for DeclRefExprs that use uninitialized values.
-  UninitializedValuesChecker Observer(Ctx,Diags);
-  U.getAnalysisData().Observer = &Observer;
-  S.runOnAllBlocks(cfg);
-}
-} // end namespace clang