Make a major restructuring of the clang tree: introduce a top-level

lib dir and move all the libraries into it.  This follows the main
llvm tree, and allows the libraries to be built in parallel.  The
top level now enforces that all the libs are built before Driver,
but we don't care what order the libs are built in.  This speeds
up parallel builds, particularly incremental ones.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@48402 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1941 insertions, 0 deletions

diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp
new file mode 100644
index 0000000000..f1108df405
--- /dev/null
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -0,0 +1,1941 @@
+//=-- GRExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines a meta-engine for path-sensitive dataflow analysis that
+//  is built on GREngine, but provides the boilerplate to execute transfer
+//  functions and build the ExplodedGraph at the expression level.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/GRExprEngine.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/Support/Streams.h"
+
+#ifndef NDEBUG
+#include "llvm/Support/GraphWriter.h"
+#include <sstream>
+#endif
+
+// SaveAndRestore - A utility class that uses RIIA to save and restore
+//  the value of a variable.
+template<typename T>
+struct VISIBILITY_HIDDEN SaveAndRestore {
+  SaveAndRestore(T& x) : X(x), old_value(x) {}
+  ~SaveAndRestore() { X = old_value; }
+  T get() { return old_value; }
+  
+  T& X;
+  T old_value;
+};
+
+using namespace clang;
+using llvm::dyn_cast;
+using llvm::cast;
+using llvm::APSInt;
+
+
+ValueState* GRExprEngine::getInitialState() {
+
+  // The LiveVariables information already has a compilation of all VarDecls
+  // used in the function.  Iterate through this set, and "symbolicate"
+  // any VarDecl whose value originally comes from outside the function.
+  
+  typedef LiveVariables::AnalysisDataTy LVDataTy;
+  LVDataTy& D = Liveness.getAnalysisData();
+  
+  ValueState StateImpl = *StateMgr.getInitialState();
+  
+  for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
+    
+    VarDecl* VD = cast<VarDecl>(const_cast<ScopedDecl*>(I->first));
+    
+    if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) {
+      RVal X = RVal::GetSymbolValue(SymMgr, VD);
+      StateMgr.BindVar(StateImpl, VD, X);
+    }
+  }
+  
+  return StateMgr.getPersistentState(StateImpl);
+}      
+      
+ValueState* GRExprEngine::SetRVal(ValueState* St, Expr* Ex, RVal V) {
+
+  bool isBlkExpr = false;
+    
+  if (Ex == CurrentStmt) {
+    isBlkExpr = getCFG().isBlkExpr(Ex);
+    
+    if (!isBlkExpr)
+      return St;
+  }
+
+  return StateMgr.SetRVal(St, Ex, V, isBlkExpr, false);
+}
+
+ValueState* GRExprEngine::MarkBranch(ValueState* St, Stmt* Terminator,
+                                     bool branchTaken) {
+  
+  switch (Terminator->getStmtClass()) {
+    default:
+      return St;
+      
+    case Stmt::BinaryOperatorClass: { // '&&' and '||'
+      
+      BinaryOperator* B = cast<BinaryOperator>(Terminator);
+      BinaryOperator::Opcode Op = B->getOpcode();
+      
+      assert (Op == BinaryOperator::LAnd || Op == BinaryOperator::LOr);
+      
+      // For &&, if we take the true branch, then the value of the whole
+      // expression is that of the RHS expression.
+      //
+      // For ||, if we take the false branch, then the value of the whole
+      // expression is that of the RHS expression.
+      
+      Expr* Ex = (Op == BinaryOperator::LAnd && branchTaken) ||
+                 (Op == BinaryOperator::LOr && !branchTaken)  
+               ? B->getRHS() : B->getLHS();
+        
+      return SetBlkExprRVal(St, B, UndefinedVal(Ex));
+    }
+      
+    case Stmt::ConditionalOperatorClass: { // ?:
+      
+      ConditionalOperator* C = cast<ConditionalOperator>(Terminator);
+      
+      // For ?, if branchTaken == true then the value is either the LHS or
+      // the condition itself. (GNU extension).
+      
+      Expr* Ex;      
+      
+      if (branchTaken)
+        Ex = C->getLHS() ? C->getLHS() : C->getCond();        
+      else
+        Ex = C->getRHS();
+      
+      return SetBlkExprRVal(St, C, UndefinedVal(Ex));
+    }
+      
+    case Stmt::ChooseExprClass: { // ?:
+      
+      ChooseExpr* C = cast<ChooseExpr>(Terminator);
+      
+      Expr* Ex = branchTaken ? C->getLHS() : C->getRHS();      
+      return SetBlkExprRVal(St, C, UndefinedVal(Ex));
+    }
+  }
+}
+
+bool GRExprEngine::ProcessBlockEntrance(CFGBlock* B, ValueState*,
+                                        GRBlockCounter BC) {
+  
+  return BC.getNumVisited(B->getBlockID()) < 3;
+}
+
+void GRExprEngine::ProcessBranch(Expr* Condition, Stmt* Term,
+                                 BranchNodeBuilder& builder) {
+
+  // Remove old bindings for subexpressions.
+  ValueState* PrevState = StateMgr.RemoveSubExprBindings(builder.getState());
+  
+  // Check for NULL conditions; e.g. "for(;;)"
+  if (!Condition) { 
+    builder.markInfeasible(false);
+    return;
+  }
+  
+  RVal V = GetRVal(PrevState, Condition);
+  
+  switch (V.getBaseKind()) {
+    default:
+      break;
+
+    case RVal::UnknownKind:
+      builder.generateNode(MarkBranch(PrevState, Term, true), true);
+      builder.generateNode(MarkBranch(PrevState, Term, false), false);
+      return;
+      
+    case RVal::UndefinedKind: {      
+      NodeTy* N = builder.generateNode(PrevState, true);
+
+      if (N) {
+        N->markAsSink();
+        UndefBranches.insert(N);
+      }
+      
+      builder.markInfeasible(false);
+      return;
+    }      
+  }
+    
+
+  // Process the true branch.
+
+  bool isFeasible = false;  
+  ValueState* St = Assume(PrevState, V, true, isFeasible);
+
+  if (isFeasible)
+    builder.generateNode(MarkBranch(St, Term, true), true);
+  else
+    builder.markInfeasible(true);
+      
+  // Process the false branch.  
+  
+  isFeasible = false;
+  St = Assume(PrevState, V, false, isFeasible);
+  
+  if (isFeasible)
+    builder.generateNode(MarkBranch(St, Term, false), false);
+  else
+    builder.markInfeasible(false);
+}
+
+/// ProcessIndirectGoto - Called by GRCoreEngine.  Used to generate successor
+///  nodes by processing the 'effects' of a computed goto jump.
+void GRExprEngine::ProcessIndirectGoto(IndirectGotoNodeBuilder& builder) {
+
+  ValueState* St = builder.getState();  
+  RVal V = GetRVal(St, builder.getTarget());
+  
+  // Three possibilities:
+  //
+  //   (1) We know the computed label.
+  //   (2) The label is NULL (or some other constant), or Undefined.
+  //   (3) We have no clue about the label.  Dispatch to all targets.
+  //
+  
+  typedef IndirectGotoNodeBuilder::iterator iterator;
+
+  if (isa<lval::GotoLabel>(V)) {
+    LabelStmt* L = cast<lval::GotoLabel>(V).getLabel();
+    
+    for (iterator I=builder.begin(), E=builder.end(); I != E; ++I) {
+      if (I.getLabel() == L) {
+        builder.generateNode(I, St);
+        return;
+      }
+    }
+    
+    assert (false && "No block with label.");
+    return;
+  }
+
+  if (isa<lval::ConcreteInt>(V) || isa<UndefinedVal>(V)) {
+    // Dispatch to the first target and mark it as a sink.
+    NodeTy* N = builder.generateNode(builder.begin(), St, true);
+    UndefBranches.insert(N);
+    return;
+  }
+  
+  // This is really a catch-all.  We don't support symbolics yet.
+  
+  assert (V.isUnknown());
+  
+  for (iterator I=builder.begin(), E=builder.end(); I != E; ++I)
+    builder.generateNode(I, St);
+}
+
+/// ProcessSwitch - Called by GRCoreEngine.  Used to generate successor
+///  nodes by processing the 'effects' of a switch statement.
+void GRExprEngine::ProcessSwitch(SwitchNodeBuilder& builder) {
+  
+  typedef SwitchNodeBuilder::iterator iterator;
+  
+  ValueState* St = builder.getState();  
+  Expr* CondE = builder.getCondition();
+  RVal  CondV = GetRVal(St, CondE);
+
+  if (CondV.isUndef()) {
+    NodeTy* N = builder.generateDefaultCaseNode(St, true);
+    UndefBranches.insert(N);
+    return;
+  }
+  
+  ValueState*  DefaultSt = St;
+  
+  // While most of this can be assumed (such as the signedness), having it
+  // just computed makes sure everything makes the same assumptions end-to-end.
+  
+  unsigned bits = getContext().getTypeSize(CondE->getType());
+
+  APSInt V1(bits, false);
+  APSInt V2 = V1;
+  
+  for (iterator I = builder.begin(), EI = builder.end(); I != EI; ++I) {
+
+    CaseStmt* Case = cast<CaseStmt>(I.getCase());
+    
+    // Evaluate the case.
+    if (!Case->getLHS()->isIntegerConstantExpr(V1, getContext(), 0, true)) {
+      assert (false && "Case condition must evaluate to an integer constant.");
+      return;
+    }
+    
+    // Get the RHS of the case, if it exists.
+    
+    if (Expr* E = Case->getRHS()) {
+      if (!E->isIntegerConstantExpr(V2, getContext(), 0, true)) {
+        assert (false &&
+                "Case condition (RHS) must evaluate to an integer constant.");
+        return ;
+      }
+      
+      assert (V1 <= V2);
+    }
+    else V2 = V1;
+    
+    // FIXME: Eventually we should replace the logic below with a range
+    //  comparison, rather than concretize the values within the range.
+    //  This should be easy once we have "ranges" for NonLVals.
+        
+    do {      
+      nonlval::ConcreteInt CaseVal(BasicVals.getValue(V1));
+      
+      RVal Res = EvalBinOp(BinaryOperator::EQ, CondV, CaseVal);
+      
+      // Now "assume" that the case matches.
+      
+      bool isFeasible = false;      
+      ValueState* StNew = Assume(St, Res, true, isFeasible);
+      
+      if (isFeasible) {
+        builder.generateCaseStmtNode(I, StNew);
+       
+        // If CondV evaluates to a constant, then we know that this
+        // is the *only* case that we can take, so stop evaluating the
+        // others.
+        if (isa<nonlval::ConcreteInt>(CondV))
+          return;
+      }
+      
+      // Now "assume" that the case doesn't match.  Add this state
+      // to the default state (if it is feasible).
+      
+      isFeasible = false;
+      StNew = Assume(DefaultSt, Res, false, isFeasible);
+      
+      if (isFeasible)
+        DefaultSt = StNew;
+
+      // Concretize the next value in the range.      
+      ++V1;
+      
+    } while (V1 < V2);
+  }
+  
+  // If we reach here, than we know that the default branch is
+  // possible.  
+  builder.generateDefaultCaseNode(DefaultSt);
+}
+
+
+void GRExprEngine::VisitLogicalExpr(BinaryOperator* B, NodeTy* Pred,
+                                    NodeSet& Dst) {
+  
+  assert (B->getOpcode() == BinaryOperator::LAnd ||
+          B->getOpcode() == BinaryOperator::LOr);
+  
+  assert (B == CurrentStmt && getCFG().isBlkExpr(B));
+  
+  ValueState* St = GetState(Pred);
+  RVal X = GetBlkExprRVal(St, B);
+  
+  assert (X.isUndef());
+  
+  Expr* Ex = (Expr*) cast<UndefinedVal>(X).getData();
+  
+  assert (Ex);
+  
+  if (Ex == B->getRHS()) {
+    
+    X = GetBlkExprRVal(St, Ex);
+    
+    // Handle undefined values.
+    
+    if (X.isUndef()) {
+      Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
+      return;
+    }
+    
+    // We took the RHS.  Because the value of the '&&' or '||' expression must
+    // evaluate to 0 or 1, we must assume the value of the RHS evaluates to 0
+    // or 1.  Alternatively, we could take a lazy approach, and calculate this
+    // value later when necessary.  We don't have the machinery in place for
+    // this right now, and since most logical expressions are used for branches,
+    // the payoff is not likely to be large.  Instead, we do eager evaluation.
+        
+    bool isFeasible = false;
+    ValueState* NewState = Assume(St, X, true, isFeasible);
+    
+    if (isFeasible)
+      Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(1U, B)));
+      
+    isFeasible = false;
+    NewState = Assume(St, X, false, isFeasible);
+    
+    if (isFeasible)
+      Nodify(Dst, B, Pred, SetBlkExprRVal(NewState, B, MakeConstantVal(0U, B)));
+  }
+  else {
+    // We took the LHS expression.  Depending on whether we are '&&' or
+    // '||' we know what the value of the expression is via properties of
+    // the short-circuiting.
+    
+    X = MakeConstantVal( B->getOpcode() == BinaryOperator::LAnd ? 0U : 1U, B);
+    Nodify(Dst, B, Pred, SetBlkExprRVal(St, B, X));
+  }
+}
+ 
+
+void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
+
+  Builder = &builder;
+  StmtEntryNode = builder.getLastNode();
+  CurrentStmt = S;
+  NodeSet Dst;
+  
+  // Create the cleaned state.
+
+  CleanedState = StateMgr.RemoveDeadBindings(StmtEntryNode->getState(),
+                                             CurrentStmt, Liveness);
+  
+  Builder->SetCleanedState(CleanedState);
+
+  // Visit the statement.
+
+  Visit(S, StmtEntryNode, Dst);
+
+  // If no nodes were generated, generate a new node that has all the
+  // dead mappings removed.
+  
+  if (Dst.size() == 1 && *Dst.begin() == StmtEntryNode)
+    builder.generateNode(S, GetState(StmtEntryNode), StmtEntryNode);
+  
+  // NULL out these variables to cleanup.
+  
+  CurrentStmt = NULL;
+  StmtEntryNode = NULL;
+  Builder = NULL;
+  CleanedState = NULL;
+}
+
+void GRExprEngine::VisitDeclRefExpr(DeclRefExpr* D, NodeTy* Pred, NodeSet& Dst){
+
+  if (D != CurrentStmt) {
+    Dst.Add(Pred); // No-op. Simply propagate the current state unchanged.
+    return;
+  }
+  
+  // If we are here, we are loading the value of the decl and binding
+  // it to the block-level expression.
+  
+  ValueState* St = GetState(Pred);  
+  RVal X = RVal::MakeVal(BasicVals, D);
+  RVal Y = isa<lval::DeclVal>(X) ? GetRVal(St, cast<lval::DeclVal>(X)) : X;
+  Nodify(Dst, D, Pred, SetBlkExprRVal(St, D, Y));
+}
+
+void GRExprEngine::VisitCall(CallExpr* CE, NodeTy* Pred,
+                             CallExpr::arg_iterator AI,
+                             CallExpr::arg_iterator AE,
+                             NodeSet& Dst) {
+  
+  // Process the arguments.
+  
+  if (AI != AE) {
+    
+    NodeSet DstTmp;      
+    Visit(*AI, Pred, DstTmp);    
+    ++AI;
+    
+    for (NodeSet::iterator DI=DstTmp.begin(), DE=DstTmp.end(); DI != DE; ++DI)
+      VisitCall(CE, *DI, AI, AE, Dst);
+    
+    return;
+  }
+
+  // If we reach here we have processed all of the arguments.  Evaluate
+  // the callee expression.
+  
+  NodeSet DstTmp;    
+  Expr* Callee = CE->getCallee()->IgnoreParenCasts();
+
+  VisitLVal(Callee, Pred, DstTmp);
+  
+  if (DstTmp.empty())
+    DstTmp.Add(Pred);
+  
+  // Finally, evaluate the function call.
+  for (NodeSet::iterator DI = DstTmp.begin(), DE = DstTmp.end(); DI!=DE; ++DI) {
+
+    ValueState* St = GetState(*DI);
+    RVal L = GetLVal(St, Callee);
+
+    // FIXME: Add support for symbolic function calls (calls involving
+    //  function pointer values that are symbolic).
+    
+    // Check for undefined control-flow or calls to NULL.
+    
+    if (L.isUndef() || isa<lval::ConcreteInt>(L)) {      
+      NodeTy* N = Builder->generateNode(CE, St, *DI);
+      
+      if (N) {
+        N->markAsSink();
+        BadCalls.insert(N);
+      }
+      
+      continue;
+    }
+    
+    // Check for the "noreturn" attribute.
+    
+    SaveAndRestore<bool> OldSink(Builder->BuildSinks);
+    
+    if (isa<lval::FuncVal>(L)) {      
+      
+      FunctionDecl* FD = cast<lval::FuncVal>(L).getDecl();
+      
+      if (FD->getAttr<NoReturnAttr>())
+        Builder->BuildSinks = true;
+      else {
+        // HACK: Some functions are not marked noreturn, and don't return.
+        //  Here are a few hardwired ones.  If this takes too long, we can
+        //  potentially cache these results.
+        const char* s = FD->getIdentifier()->getName();
+        unsigned n = strlen(s);
+        
+        switch (n) {
+          default:
+            break;
+            
+          case 4:
+            if (!memcmp(s, "exit", 4)) Builder->BuildSinks = true;
+            break;
+
+          case 5:
+            if (!memcmp(s, "panic", 5)) Builder->BuildSinks = true;
+            break;
+        }
+      }
+    }
+    
+    // Evaluate the call.
+    
+    
+    bool invalidateArgs = false;
+    
+    if (L.isUnknown()) {
+      // Check for an "unknown" callee.      
+      invalidateArgs = true;
+    }
+    else if (isa<lval::FuncVal>(L)) {
+      
+      IdentifierInfo* Info = cast<lval::FuncVal>(L).getDecl()->getIdentifier();
+      
+      if (unsigned id = Info->getBuiltinID()) {
+        switch (id) {
+          case Builtin::BI__builtin_expect: {
+            // For __builtin_expect, just return the value of the subexpression.
+            assert (CE->arg_begin() != CE->arg_end());            
+            RVal X = GetRVal(St, *(CE->arg_begin()));
+            Nodify(Dst, CE, *DI, SetRVal(St, CE, X));
+            continue;            
+          }
+            
+          default:
+            invalidateArgs = true;
+            break;
+        }
+      }
+    }
+        
+    if (invalidateArgs) {
+      // Invalidate all arguments passed in by reference (LVals).
+      for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+                                                       I != E; ++I) {
+        RVal V = GetRVal(St, *I);
+
+        if (isa<LVal>(V))
+          St = SetRVal(St, cast<LVal>(V), UnknownVal());
+      }
+      
+      Nodify(Dst, CE, *DI, St);
+    }
+    else {
+
+      // Check any arguments passed-by-value against being undefined.
+
+      bool badArg = false;
+      
+      for (CallExpr::arg_iterator I = CE->arg_begin(), E = CE->arg_end();
+           I != E; ++I) {
+
+        if (GetRVal(GetState(*DI), *I).isUndef()) {        
+          NodeTy* N = Builder->generateNode(CE, GetState(*DI), *DI);
+        
+          if (N) {
+            N->markAsSink();
+            UndefArgs[N] = *I;
+          }
+          
+          badArg = true;
+          break;
+        }
+      }
+        
+      if (badArg)
+        continue;        
+      
+      // Dispatch to the plug-in transfer function.      
+      
+      unsigned size = Dst.size();
+      
+      EvalCall(Dst, CE, cast<LVal>(L), *DI);
+      
+      if (!Builder->BuildSinks && Dst.size() == size)
+        Nodify(Dst, CE, *DI, St);
+    }
+  }
+}
+
+void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){
+  
+  NodeSet S1;
+  QualType T = CastE->getType();
+  
+  if (T->isReferenceType())
+    VisitLVal(Ex, Pred, S1);
+  else
+    Visit(Ex, Pred, S1);
+  
+  // Check for redundant casts or casting to "void"
+  if (T->isVoidType() ||
+      Ex->getType() == T || 
+      (T->isPointerType() && Ex->getType()->isFunctionType())) {
+    
+    for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1)
+      Dst.Add(*I1);
+
+    return;
+  }
+  
+  for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
+    NodeTy* N = *I1;
+    ValueState* St = GetState(N);
+    
+    RVal V = T->isReferenceType() ? GetLVal(St, Ex) : GetRVal(St, Ex);
+    
+    Nodify(Dst, CastE, N, SetRVal(St, CastE, EvalCast(V, CastE->getType())));
+  }
+}
+
+void GRExprEngine::VisitDeclStmt(DeclStmt* DS, GRExprEngine::NodeTy* Pred,
+                                 GRExprEngine::NodeSet& Dst) {
+  
+  ValueState* St = GetState(Pred);
+  
+  for (const ScopedDecl* D = DS->getDecl(); D; D = D->getNextDeclarator())
+    if (const VarDecl* VD = dyn_cast<VarDecl>(D)) {
+      
+      // FIXME: Add support for local arrays.
+      if (VD->getType()->isArrayType())
+        continue;
+      
+      const Expr* Ex = VD->getInit();
+      
+      if (!VD->hasGlobalStorage() || VD->getStorageClass() == VarDecl::Static) {
+        
+        // In this context, Static => Local variable.
+        
+        assert (!VD->getStorageClass() == VarDecl::Static ||
+                !isa<FileVarDecl>(VD));
+        
+        // If there is no initializer, set the value of the
+        // variable to "Undefined".
+        //
+        // FIXME: static variables may have an initializer, but the second
+        //  time a function is called those values may not be current.
+
+        QualType T = VD->getType();
+        
+        if ( VD->getStorageClass() == VarDecl::Static) {
+          
+          // C99: 6.7.8 Initialization
+          //  If an object that has static storage duration is not initialized
+          //  explicitly, then: 
+          //   —if it has pointer type, it is initialized to a null pointer; 
+          //   —if it has arithmetic type, it is initialized to (positive or 
+          //     unsigned) zero; 
+          
+          // FIXME: Handle structs.  Now we treat their values as unknown.
+          
+          if (T->isPointerType()) {
+            
+            St = SetRVal(St, lval::DeclVal(VD),
+                         lval::ConcreteInt(BasicVals.getValue(0, T)));
+          }
+          else if (T->isIntegerType()) {
+            
+            St = SetRVal(St, lval::DeclVal(VD),
+                         nonlval::ConcreteInt(BasicVals.getValue(0, T)));
+          }
+          
+
+        }
+        else {
+          
+          // FIXME: Handle structs.  Now we treat them as unknown.  What
+          //  we need to do is treat their members as unknown.
+          
+          if (T->isPointerType() || T->isIntegerType())
+            St = SetRVal(St, lval::DeclVal(VD),
+                         Ex ? GetRVal(St, Ex) : UndefinedVal());
+        }
+      }
+    }
+
+  Nodify(Dst, DS, Pred, St);
+}
+
+
+void GRExprEngine::VisitGuardedExpr(Expr* Ex, Expr* L, Expr* R,
+                                   NodeTy* Pred, NodeSet& Dst) {
+  
+  assert (Ex == CurrentStmt && getCFG().isBlkExpr(Ex));
+
+  ValueState* St = GetState(Pred);
+  RVal X = GetBlkExprRVal(St, Ex);
+  
+  assert (X.isUndef());
+  
+  Expr* SE = (Expr*) cast<UndefinedVal>(X).getData();
+  
+  assert (SE);
+    
+  X = GetBlkExprRVal(St, SE);
+  
+  // Make sure that we invalidate the previous binding.
+  Nodify(Dst, Ex, Pred, StateMgr.SetRVal(St, Ex, X, true, true));
+}
+
+/// VisitSizeOfAlignOfTypeExpr - Transfer function for sizeof(type).
+void GRExprEngine::VisitSizeOfAlignOfTypeExpr(SizeOfAlignOfTypeExpr* Ex,
+                                              NodeTy* Pred,
+                                              NodeSet& Dst) {
+
+  QualType T = Ex->getArgumentType();
+  uint64_t amt;  
+  
+  if (Ex->isSizeOf()) {
+
+    // FIXME: Add support for VLAs.
+    if (!T.getTypePtr()->isConstantSizeType())
+      return;
+    
+    amt = 1;  // Handle sizeof(void)
+    
+    if (T != getContext().VoidTy)
+      amt = getContext().getTypeSize(T) / 8;
+    
+  }
+  else  // Get alignment of the type.
+    amt = getContext().getTypeAlign(T) / 8;
+  
+  Nodify(Dst, Ex, Pred,
+         SetRVal(GetState(Pred), Ex,
+                 NonLVal::MakeVal(BasicVals, amt, Ex->getType())));  
+}
+
+void GRExprEngine::VisitDeref(UnaryOperator* U, NodeTy* Pred,
+                              NodeSet& Dst, bool GetLVal) {
+
+  Expr* Ex = U->getSubExpr()->IgnoreParens();
+    
+  NodeSet DstTmp;
+  
+  if (isa<DeclRefExpr>(Ex))
+    DstTmp.Add(Pred);
+  else
+    Visit(Ex, Pred, DstTmp);
+  
+  for (NodeSet::iterator I = DstTmp.begin(), DE = DstTmp.end(); I != DE; ++I) {
+
+    NodeTy* N = *I;
+    ValueState* St = GetState(N);
+    
+    // FIXME: Bifurcate when dereferencing a symbolic with no constraints?
+    
+    RVal V = GetRVal(St, Ex);
+    
+    // Check for dereferences of undefined values.
+    
+    if (V.isUndef()) {
+      
+      NodeTy* Succ = Builder->generateNode(U, St, N);
+      
+      if (Succ) {
+        Succ->markAsSink();
+        UndefDeref.insert(Succ);
+      }
+      
+      continue;
+    }
+    
+    // Check for dereferences of unknown values.  Treat as No-Ops.
+    
+    if (V.isUnknown()) {
+      Dst.Add(N);
+      continue;
+    }
+    
+    // After a dereference, one of two possible situations arise:
+    //  (1) A crash, because the pointer was NULL.
+    //  (2) The pointer is not NULL, and the dereference works.
+    // 
+    // We add these assumptions.
+    
+    LVal LV = cast<LVal>(V);    
+    bool isFeasibleNotNull;
+    
+    // "Assume" that the pointer is Not-NULL.
+    
+    ValueState* StNotNull = Assume(St, LV, true, isFeasibleNotNull);
+    
+    if (isFeasibleNotNull) {
+
+      if (GetLVal) Nodify(Dst, U, N, SetRVal(StNotNull, U, LV));
+      else {
+        
+        // FIXME: Currently symbolic analysis "generates" new symbols
+        //  for the contents of values.  We need a better approach.
+      
+        Nodify(Dst, U, N, SetRVal(StNotNull, U,
+                                  GetRVal(StNotNull, LV, U->getType())));
+      }
+    }
+    
+    bool isFeasibleNull;
+    
+    // Now "assume" that the pointer is NULL.
+    
+    ValueState* StNull = Assume(St, LV, false, isFeasibleNull);
+    
+    if (isFeasibleNull) {
+      
+      // We don't use "Nodify" here because the node will be a sink
+      // and we have no intention of processing it later.
+
+      NodeTy* NullNode = Builder->generateNode(U, StNull, N);
+      
+      if (NullNode) {
+
+        NullNode->markAsSink();
+        
+        if (isFeasibleNotNull) ImplicitNullDeref.insert(NullNode);
+        else ExplicitNullDeref.insert(NullNode);
+      }
+    }    
+  }
+}
+
+void GRExprEngine::VisitUnaryOperator(UnaryOperator* U, NodeTy* Pred,
+                                      NodeSet& Dst) {
+  
+  NodeSet S1;
+  
+  assert (U->getOpcode() != UnaryOperator::Deref);
+  assert (U->getOpcode() != UnaryOperator::SizeOf);
+  assert (U->getOpcode() != UnaryOperator::AlignOf);
+  
+  bool use_GetLVal = false;
+  
+  switch (U->getOpcode()) {
+    case UnaryOperator::PostInc:
+    case UnaryOperator::PostDec:
+    case UnaryOperator::PreInc:
+    case UnaryOperator::PreDec:
+    case UnaryOperator::AddrOf:
+      // Evalue subexpression as an LVal.
+      use_GetLVal = true;
+      VisitLVal(U->getSubExpr(), Pred, S1);
+      break;
+      
+    default:
+      Visit(U->getSubExpr(), Pred, S1);
+      break;
+  }
+
+  for (NodeSet::iterator I1 = S1.begin(), E1 = S1.end(); I1 != E1; ++I1) {
+
+    NodeTy* N1 = *I1;
+    ValueState* St = GetState(N1);
+        
+    RVal SubV = use_GetLVal ? GetLVal(St, U->getSubExpr()) : 
+                              GetRVal(St, U->getSubExpr());
+    
+    if (SubV.isUnknown()) {
+      Dst.Add(N1);
+      continue;
+    }
+
+    if (SubV.isUndef()) {
+      Nodify(Dst, U, N1, SetRVal(St, U, SubV));
+      continue;
+    }
+    
+    if (U->isIncrementDecrementOp()) {
+      
+      // Handle ++ and -- (both pre- and post-increment).
+      
+      LVal SubLV = cast<LVal>(SubV); 
+      RVal V  = GetRVal(St, SubLV, U->getType());
+      
+      if (V.isUnknown()) {
+        Dst.Add(N1);
+        continue;
+      }
+
+      // Propagate undefined values.      
+      if (V.isUndef()) {
+        Nodify(Dst, U, N1, SetRVal(St, U, V));
+        continue;
+      }
+      
+      // Handle all other values.
+      
+      BinaryOperator::Opcode Op = U->isIncrementOp() ? BinaryOperator::Add
+                                                     : BinaryOperator::Sub;
+      
+      RVal Result = EvalBinOp(Op, V, MakeConstantVal(1U, U));
+      
+      if (U->isPostfix())
+        St = SetRVal(SetRVal(St, U, V), SubLV, Result);
+      else
+        St = SetRVal(SetRVal(St, U, Result), SubLV, Result);
+        
+      Nodify(Dst, U, N1, St);
+      continue;
+    }    
+    
+    // Handle all other unary operators.
+    
+    switch (U->getOpcode()) {
+        
+      case UnaryOperator::Extension:
+        St = SetRVal(St, U, SubV);
+        break;
+
+      case UnaryOperator::Minus:
+        St = SetRVal(St, U, EvalMinus(U, cast<NonLVal>(SubV)));
+        break;
+        
+      case UnaryOperator::Not:
+        St = SetRVal(St, U, EvalComplement(cast<NonLVal>(SubV)));
+        break;
+        
+      case UnaryOperator::LNot:   
+        
+        // C99 6.5.3.3: "The expression !E is equivalent to (0==E)."
+        //
+        //  Note: technically we do "E == 0", but this is the same in the
+        //    transfer functions as "0 == E".
+
+        if (isa<LVal>(SubV)) {
+          lval::ConcreteInt V(BasicVals.getZeroWithPtrWidth());
+          RVal Result = EvalBinOp(BinaryOperator::EQ, cast<LVal>(SubV), V);
+          St = SetRVal(St, U, Result);
+        }
+        else {
+          Expr* Ex = U->getSubExpr();
+          nonlval::ConcreteInt V(BasicVals.getValue(0, Ex->getType()));
+          RVal Result = EvalBinOp(BinaryOperator::EQ, cast<NonLVal>(SubV), V);
+          St = SetRVal(St, U, Result);
+        }
+        
+        break;
+        
+      case UnaryOperator::AddrOf: {
+        assert (isa<LVal>(SubV));
+        St = SetRVal(St, U, SubV);
+        break;
+      }
+                
+      default: ;
+        assert (false && "Not implemented.");
+    } 
+    
+    Nodify(Dst, U, N1, St);
+  }
+}
+
+void GRExprEngine::VisitSizeOfExpr(UnaryOperator* U, NodeTy* Pred,
+                                   NodeSet& Dst) {
+  
+  QualType T = U->getSubExpr()->getType();
+  
+  // FIXME: Add support for VLAs.
+  if (!T.getTypePtr()->isConstantSizeType())
+    return;
+  
+  uint64_t size = getContext().getTypeSize(T) / 8;                
+  ValueState* St = GetState(Pred);
+  St = SetRVal(St, U, NonLVal::MakeVal(BasicVals, size, U->getType()));
+
+  Nodify(Dst, U, Pred, St);
+}
+
+void GRExprEngine::VisitLVal(Expr* Ex, NodeTy* Pred, NodeSet& Dst) {
+
+  if (Ex != CurrentStmt && getCFG().isBlkExpr(Ex)) {
+    Dst.Add(Pred);
+    return;
+  }
+  
+  Ex = Ex->IgnoreParens();
+  
+  if (isa<DeclRefExpr>(Ex)) {
+    Dst.Add(Pred);
+    return;
+  }
+  
+  if (UnaryOperator* U = dyn_cast<UnaryOperator>(Ex))
+    if (U->getOpcode() == UnaryOperator::Deref) {
+      VisitDeref(U, Pred, Dst, true);
+      return;
+    }
+  
+  Visit(Ex, Pred, Dst);
+}
+
+void GRExprEngine::VisitBinaryOperator(BinaryOperator* B,
+                                       GRExprEngine::NodeTy* Pred,
+                                       GRExprEngine::NodeSet& Dst) {
+  NodeSet S1;
+  
+  if (B->isAssignmentOp())
+    VisitLVal(B->getLHS(), Pred, S1);
+  else
+    Visit(B->getLHS(), Pred, S1);
+
+  for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
+
+    NodeTy* N1 = *I1;
+    
+    // When getting the value for the LHS, check if we are in an assignment.
+    // In such cases, we want to (initially) treat the LHS as an LVal,
+    // so we use GetLVal instead of GetRVal so that DeclRefExpr's are
+    // evaluated to LValDecl's instead of to an NonLVal.
+
+    RVal LeftV = B->isAssignmentOp() ? GetLVal(GetState(N1), B->getLHS())
+                                     : GetRVal(GetState(N1), B->getLHS());
+    
+    // Visit the RHS...
+    
+    NodeSet S2;    
+    Visit(B->getRHS(), N1, S2);
+    
+    // Process the binary operator.
+  
+    for (NodeSet::iterator I2 = S2.begin(), E2 = S2.end(); I2 != E2; ++I2) {
+
+      NodeTy* N2 = *I2;
+      ValueState* St = GetState(N2);
+      Expr* RHS = B->getRHS();
+      RVal RightV = GetRVal(St, RHS);
+
+      BinaryOperator::Opcode Op = B->getOpcode();
+      
+      if ((Op == BinaryOperator::Div || Op == BinaryOperator::Rem)
+          && RHS->getType()->isIntegerType()) {
+
+        // Check if the denominator is undefined.
+        
+        if (!RightV.isUnknown()) {
+        
+          if (RightV.isUndef()) {
+            NodeTy* DivUndef = Builder->generateNode(B, St, N2);
+            
+            if (DivUndef) {
+              DivUndef->markAsSink();
+              ExplicitBadDivides.insert(DivUndef);
+            }
+            
+            continue;
+          }
+            
+          // Check for divide/remainder-by-zero.
+          //
+          // First, "assume" that the denominator is 0 or undefined.
+          
+          bool isFeasibleZero = false;
+          ValueState* ZeroSt =  Assume(St, RightV, false, isFeasibleZero);
+          
+          // Second, "assume" that the denominator cannot be 0.
+          
+          bool isFeasibleNotZero = false;
+          St = Assume(St, RightV, true, isFeasibleNotZero);
+          
+          // Create the node for the divide-by-zero (if it occurred).
+          
+          if (isFeasibleZero)
+            if (NodeTy* DivZeroNode = Builder->generateNode(B, ZeroSt, N2)) {
+              DivZeroNode->markAsSink();
+              
+              if (isFeasibleNotZero)
+                ImplicitBadDivides.insert(DivZeroNode);
+              else
+                ExplicitBadDivides.insert(DivZeroNode);
+
+            }
+          
+          if (!isFeasibleNotZero)
+            continue;
+        }
+        
+        // Fall-through.  The logic below processes the divide.
+      }
+      
+