Update LLVM to r84949.

12 files changed, 606 insertions, 115 deletions

diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index c5be616..756ffea 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -40,10 +40,6 @@ using namespace llvm;
 // Useful predicates
 //===----------------------------------------------------------------------===//
 
-static const GEPOperator *isGEP(const Value *V) {
-  return dyn_cast<GEPOperator>(V);
-}
-
 static const Value *GetGEPOperands(const Value *V, 
                                    SmallVector<Value*, 16> &GEPOps) {
   assert(GEPOps.empty() && "Expect empty list to populate!");
@@ -53,7 +49,7 @@ static const Value *GetGEPOperands(const Value *V,
   // Accumulate all of the chained indexes into the operand array
   V = cast<User>(V)->getOperand(0);
 
-  while (const User *G = isGEP(V)) {
+  while (const GEPOperator *G = dyn_cast<GEPOperator>(V)) {
     if (!isa<Constant>(GEPOps[0]) || isa<GlobalValue>(GEPOps[0]) ||
         !cast<Constant>(GEPOps[0])->isNullValue())
       break;  // Don't handle folding arbitrary pointer offsets yet...
@@ -222,7 +218,7 @@ namespace {
 
   private:
     // VisitedPHIs - Track PHI nodes visited by a aliasCheck() call.
-    SmallSet<const PHINode*, 16> VisitedPHIs;
+    SmallPtrSet<const PHINode*, 16> VisitedPHIs;
 
     // aliasGEP - Provide a bunch of ad-hoc rules to disambiguate a GEP instruction
     // against another.
@@ -358,11 +354,13 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS, Value *P, unsigned Size) {
         if (alias(II->getOperand(2), PtrSize, P, Size) == NoAlias)
           return NoModRef;
       }
+      break;
       case Intrinsic::invariant_end: {
         unsigned PtrSize = cast<ConstantInt>(II->getOperand(2))->getZExtValue();
         if (alias(II->getOperand(3), PtrSize, P, Size) == NoAlias)
           return NoModRef;
       }
+      break;
       }
     }
   }
@@ -400,7 +398,7 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
   // Note that we also handle chains of getelementptr instructions as well as
   // constant expression getelementptrs here.
   //
-  if (isGEP(V1) && isGEP(V2)) {
+  if (isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
     const User *GEP1 = cast<User>(V1);
     const User *GEP2 = cast<User>(V2);
     
@@ -419,13 +417,13 @@ BasicAliasAnalysis::aliasGEP(const Value *V1, unsigned V1Size,
     
     // Drill down into the first non-gep value, to test for must-aliasing of
     // the base pointers.
-    while (isGEP(GEP1->getOperand(0)) &&
+    while (isa<GEPOperator>(GEP1->getOperand(0)) &&
            GEP1->getOperand(1) ==
            Constant::getNullValue(GEP1->getOperand(1)->getType()))
       GEP1 = cast<User>(GEP1->getOperand(0));
     const Value *BasePtr1 = GEP1->getOperand(0);
 
-    while (isGEP(GEP2->getOperand(0)) &&
+    while (isa<GEPOperator>(GEP2->getOperand(0)) &&
            GEP2->getOperand(1) ==
            Constant::getNullValue(GEP2->getOperand(1)->getType()))
       GEP2 = cast<User>(GEP2->getOperand(0));
@@ -531,7 +529,7 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize,
   if (!VisitedPHIs.insert(PN))
     return MayAlias;
 
-  SmallSet<Value*, 4> UniqueSrc;
+  SmallPtrSet<Value*, 4> UniqueSrc;
   SmallVector<Value*, 4> V1Srcs;
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
     Value *PV1 = PN->getIncomingValue(i);
@@ -555,7 +553,7 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, unsigned PNSize,
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
     Value *V = V1Srcs[i];
-    AliasResult ThisAlias = aliasCheck(V, PNSize, V2, V2Size);
+    AliasResult ThisAlias = aliasCheck(V2, V2Size, V, PNSize);
     if (ThisAlias != Alias || ThisAlias == MayAlias)
       return MayAlias;
   }
@@ -617,11 +615,11 @@ BasicAliasAnalysis::aliasCheck(const Value *V1, unsigned V1Size,
       isNonEscapingLocalObject(O1) && O1 != O2)
     return NoAlias;
 
-  if (!isGEP(V1) && isGEP(V2)) {
+  if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
     std::swap(V1, V2);
     std::swap(V1Size, V2Size);
   }
-  if (isGEP(V1))
+  if (isa<GEPOperator>(V1))
     return aliasGEP(V1, V1Size, V2, V2Size);
 
   if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
diff --git a/lib/Analysis/CFGPrinter.cpp b/lib/Analysis/CFGPrinter.cpp
index 6fed400..08f070c 100644
--- a/lib/Analysis/CFGPrinter.cpp
+++ b/lib/Analysis/CFGPrinter.cpp
@@ -17,71 +17,12 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
-#include "llvm/Pass.h"
 #include "llvm/Analysis/CFGPrinter.h"
-#include "llvm/Assembly/Writer.h"
-#include "llvm/Support/CFG.h"
+
+#include "llvm/Pass.h"
 #include "llvm/Support/Compiler.h"
-#include "llvm/Support/GraphWriter.h"
 using namespace llvm;
 
-namespace llvm {
-template<>
-struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
-  static std::string getGraphName(const Function *F) {
-    return "CFG for '" + F->getNameStr() + "' function";
-  }
-
-  static std::string getNodeLabel(const BasicBlock *Node,
-                                  const Function *Graph,
-                                  bool ShortNames) {
-    if (ShortNames && !Node->getName().empty())
-      return Node->getNameStr() + ":";
-
-    std::string Str;
-    raw_string_ostream OS(Str);
-
-    if (ShortNames) {
-      WriteAsOperand(OS, Node, false);
-      return OS.str();
-    }
-
-    if (Node->getName().empty()) {
-      WriteAsOperand(OS, Node, false);
-      OS << ":";
-    }
-    
-    OS << *Node;
-    std::string OutStr = OS.str();
-    if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
-
-    // Process string output to make it nicer...
-    for (unsigned i = 0; i != OutStr.length(); ++i)
-      if (OutStr[i] == '\n') {                            // Left justify
-        OutStr[i] = '\\';
-        OutStr.insert(OutStr.begin()+i+1, 'l');
-      } else if (OutStr[i] == ';') {                      // Delete comments!
-        unsigned Idx = OutStr.find('\n', i+1);            // Find end of line
-        OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx);
-        --i;
-      }
-
-    return OutStr;
-  }
-
-  static std::string getEdgeSourceLabel(const BasicBlock *Node,
-                                        succ_const_iterator I) {
-    // Label source of conditional branches with "T" or "F"
-    if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator()))
-      if (BI->isConditional())
-        return (I == succ_begin(Node)) ? "T" : "F";
-    return "";
-  }
-};
-}
-
 namespace {
   struct VISIBILITY_HIDDEN CFGViewer : public FunctionPass {
     static char ID; // Pass identifcation, replacement for typeid
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 1d2f118..d4be986 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -11,6 +11,7 @@ add_llvm_library(LLVMAnalysis
   ConstantFolding.cpp
   DbgInfoPrinter.cpp
   DebugInfo.cpp
+  DomPrinter.cpp
   IVUsers.cpp
   InlineCost.cpp
   InstCount.cpp
diff --git a/lib/Analysis/ConstantFolding.cpp b/lib/Analysis/ConstantFolding.cpp
index 0ce1c24..214caeb 100644
--- a/lib/Analysis/ConstantFolding.cpp
+++ b/lib/Analysis/ConstantFolding.cpp
@@ -24,9 +24,10 @@
 #include "llvm/Instructions.h"
 #include "llvm/Intrinsics.h"
 #include "llvm/LLVMContext.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Target/TargetData.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
-#include "llvm/Target/TargetData.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/GetElementPtrTypeIterator.h"
 #include "llvm/Support/MathExtras.h"
@@ -92,6 +93,265 @@ static bool IsConstantOffsetFromGlobal(Constant *C, GlobalValue *&GV,
   return false;
 }
 
+/// ReadDataFromGlobal - Recursive helper to read bits out of global.  C is the
+/// constant being copied out of. ByteOffset is an offset into C.  CurPtr is the
+/// pointer to copy results into and BytesLeft is the number of bytes left in
+/// the CurPtr buffer.  TD is the target data.
+static bool ReadDataFromGlobal(Constant *C, uint64_t ByteOffset,
+                               unsigned char *CurPtr, unsigned BytesLeft,
+                               const TargetData &TD) {
+  assert(ByteOffset <= TD.getTypeAllocSize(C->getType()) &&
+         "Out of range access");
+  
+  if (isa<ConstantAggregateZero>(C) || isa<UndefValue>(C))
+    return true;
+  
+  if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
+    if (CI->getBitWidth() > 64 ||
+        (CI->getBitWidth() & 7) != 0)
+      return false;
+    
+    uint64_t Val = CI->getZExtValue();
+    unsigned IntBytes = unsigned(CI->getBitWidth()/8);
+    
+    for (unsigned i = 0; i != BytesLeft && ByteOffset != IntBytes; ++i) {
+      CurPtr[i] = (unsigned char)(Val >> ByteOffset * 8);
+      ++ByteOffset;
+    }
+    return true;
+  }
+  
+  if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
+    if (CFP->getType()->isDoubleTy()) {
+      C = ConstantExpr::getBitCast(C, Type::getInt64Ty(C->getContext()));
+      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD);
+    }
+    if (CFP->getType()->isFloatTy()){
+      C = ConstantExpr::getBitCast(C, Type::getInt32Ty(C->getContext()));
+      return ReadDataFromGlobal(C, ByteOffset, CurPtr, BytesLeft, TD);
+    }
+  }
+
+  if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
+    const StructLayout *SL = TD.getStructLayout(CS->getType());
+    unsigned Index = SL->getElementContainingOffset(ByteOffset);
+    uint64_t CurEltOffset = SL->getElementOffset(Index);
+    ByteOffset -= CurEltOffset;
+    
+    while (1) {
+      // If the element access is to the element itself and not to tail padding,
+      // read the bytes from the element.
+      uint64_t EltSize = TD.getTypeAllocSize(CS->getOperand(Index)->getType());
+
+      if (ByteOffset < EltSize &&
+          !ReadDataFromGlobal(CS->getOperand(Index), ByteOffset, CurPtr,
+                              BytesLeft, TD))
+        return false;
+      
+      ++Index;
+      
+      // Check to see if we read from the last struct element, if so we're done.
+      if (Index == CS->getType()->getNumElements())
+        return true;
+
+      // If we read all of the bytes we needed from this element we're done.
+      uint64_t NextEltOffset = SL->getElementOffset(Index);
+
+      if (BytesLeft <= NextEltOffset-CurEltOffset-ByteOffset)
+        return true;
+
+      // Move to the next element of the struct.
+      BytesLeft -= NextEltOffset-CurEltOffset-ByteOffset;
+      ByteOffset = 0;
+      CurEltOffset = NextEltOffset;
+    }
+    // not reached.
+  }
+
+  if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
+    uint64_t EltSize = TD.getTypeAllocSize(CA->getType()->getElementType());
+    uint64_t Index = ByteOffset / EltSize;
+    uint64_t Offset = ByteOffset - Index * EltSize;
+    for (; Index != CA->getType()->getNumElements(); ++Index) {
+      if (!ReadDataFromGlobal(CA->getOperand(Index), Offset, CurPtr,
+                              BytesLeft, TD))
+        return false;
+      if (EltSize >= BytesLeft)
+        return true;
+      
+      Offset = 0;
+      BytesLeft -= EltSize;
+      CurPtr += EltSize;
+    }
+    return true;
+  }
+  
+  if (ConstantVector *CV = dyn_cast<ConstantVector>(C)) {
+    uint64_t EltSize = TD.getTypeAllocSize(CV->getType()->getElementType());
+    uint64_t Index = ByteOffset / EltSize;
+    uint64_t Offset = ByteOffset - Index * EltSize;
+    for (; Index != CV->getType()->getNumElements(); ++Index) {
+      if (!ReadDataFromGlobal(CV->getOperand(Index), Offset, CurPtr,
+                              BytesLeft, TD))
+        return false;
+      if (EltSize >= BytesLeft)
+        return true;
+      
+      Offset = 0;
+      BytesLeft -= EltSize;
+      CurPtr += EltSize;
+    }
+    return true;
+  }
+  
+  // Otherwise, unknown initializer type.
+  return false;
+}
+
+static Constant *FoldReinterpretLoadFromConstPtr(Constant *C,
+                                                 const TargetData &TD) {
+  const Type *LoadTy = cast<PointerType>(C->getType())->getElementType();
+  const IntegerType *IntType = dyn_cast<IntegerType>(LoadTy);
+  
+  // If this isn't an integer load we can't fold it directly.
+  if (!IntType) {
+    // If this is a float/double load, we can try folding it as an int32/64 load
+    // and then bitcast the result.  This can be useful for union cases.  Note
+    // that address spaces don't matter here since we're not going to result in
+    // an actual new load.
+    const Type *MapTy;
+    if (LoadTy->isFloatTy())
+      MapTy = Type::getInt32PtrTy(C->getContext());
+    else if (LoadTy->isDoubleTy())
+      MapTy = Type::getInt64PtrTy(C->getContext());
+    else if (isa<VectorType>(LoadTy)) {
+      MapTy = IntegerType::get(C->getContext(),
+                               TD.getTypeAllocSizeInBits(LoadTy));
+      MapTy = PointerType::getUnqual(MapTy);
+    } else
+      return 0;
+
+    C = ConstantExpr::getBitCast(C, MapTy);
+    if (Constant *Res = FoldReinterpretLoadFromConstPtr(C, TD))
+      return ConstantExpr::getBitCast(Res, LoadTy);
+    return 0;
+  }
+  
+  unsigned BytesLoaded = (IntType->getBitWidth() + 7) / 8;
+  if (BytesLoaded > 32 || BytesLoaded == 0) return 0;
+  
+  GlobalValue *GVal;
+  int64_t Offset;
+  if (!IsConstantOffsetFromGlobal(C, GVal, Offset, TD))
+    return 0;
+  
+  GlobalVariable *GV = dyn_cast<GlobalVariable>(GVal);
+  if (!GV || !GV->isConstant() || !GV->hasInitializer() ||
+      !GV->hasDefinitiveInitializer() ||
+      !GV->getInitializer()->getType()->isSized())
+    return 0;
+
+  // If we're loading off the beginning of the global, some bytes may be valid,
+  // but we don't try to handle this.
+  if (Offset < 0) return 0;
+  
+  // If we're not accessing anything in this constant, the result is undefined.
+  if (uint64_t(Offset) >= TD.getTypeAllocSize(GV->getInitializer()->getType()))
+    return UndefValue::get(IntType);
+  
+  unsigned char RawBytes[32] = {0};
+  if (!ReadDataFromGlobal(GV->getInitializer(), Offset, RawBytes,
+                          BytesLoaded, TD))
+    return 0;
+
+  APInt ResultVal(IntType->getBitWidth(), 0);
+  for (unsigned i = 0; i != BytesLoaded; ++i) {
+    ResultVal <<= 8;
+    ResultVal |= APInt(IntType->getBitWidth(), RawBytes[BytesLoaded-1-i]);
+  }
+
+  return ConstantInt::get(IntType->getContext(), ResultVal);
+}
+
+/// ConstantFoldLoadFromConstPtr - Return the value that a load from C would
+/// produce if it is constant and determinable.  If this is not determinable,
+/// return null.
+Constant *llvm::ConstantFoldLoadFromConstPtr(Constant *C,
+                                             const TargetData *TD) {
+  // First, try the easy cases:
+  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
+    if (GV->isConstant() && GV->hasDefinitiveInitializer())
+      return GV->getInitializer();
+
+  // If the loaded value isn't a constant expr, we can't handle it.
+  ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
+  if (!CE) return 0;
+  
+  if (CE->getOpcode() == Instruction::GetElementPtr) {
+    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
+      if (GV->isConstant() && GV->hasDefinitiveInitializer())
+        if (Constant *V = 
+             ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE))
+          return V;
+  }
+  
+  // Instead of loading constant c string, use corresponding integer value
+  // directly if string length is small enough.
+  std::string Str;
+  if (TD && GetConstantStringInfo(CE->getOperand(0), Str) && !Str.empty()) {
+    unsigned StrLen = Str.length();
+    const Type *Ty = cast<PointerType>(CE->getType())->getElementType();
+    unsigned NumBits = Ty->getPrimitiveSizeInBits();
+    // Replace LI with immediate integer store.
+    if ((NumBits >> 3) == StrLen + 1) {
+      APInt StrVal(NumBits, 0);
+      APInt SingleChar(NumBits, 0);
+      if (TD->isLittleEndian()) {
+        for (signed i = StrLen-1; i >= 0; i--) {
+          SingleChar = (uint64_t) Str[i] & UCHAR_MAX;
+          StrVal = (StrVal << 8) | SingleChar;
+        }
+      } else {
+        for (unsigned i = 0; i < StrLen; i++) {
+          SingleChar = (uint64_t) Str[i] & UCHAR_MAX;
+          StrVal = (StrVal << 8) | SingleChar;
+        }
+        // Append NULL at the end.
+        SingleChar = 0;
+        StrVal = (StrVal << 8) | SingleChar;
+      }
+      return ConstantInt::get(CE->getContext(), StrVal);
+    }
+  }
+  
+  // If this load comes from anywhere in a constant global, and if the global
+  // is all undef or zero, we know what it loads.
+  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getUnderlyingObject())){
+    if (GV->isConstant() && GV->hasDefinitiveInitializer()) {
+      const Type *ResTy = cast<PointerType>(C->getType())->getElementType();
+      if (GV->getInitializer()->isNullValue())
+        return Constant::getNullValue(ResTy);
+      if (isa<UndefValue>(GV->getInitializer()))
+        return UndefValue::get(ResTy);
+    }
+  }
+  
+  // Try hard to fold loads from bitcasted strange and non-type-safe things.  We
+  // currently don't do any of this for big endian systems.  It can be
+  // generalized in the future if someone is interested.
+  if (TD && TD->isLittleEndian())
+    return FoldReinterpretLoadFromConstPtr(CE, *TD);
+  return 0;
+}
+
+static Constant *ConstantFoldLoadInst(const LoadInst *LI, const TargetData *TD){
+  if (LI->isVolatile()) return 0;
+  
+  if (Constant *C = dyn_cast<Constant>(LI->getOperand(0)))
+    return ConstantFoldLoadFromConstPtr(C, TD);
+
+  return 0;
+}
 
 /// SymbolicallyEvaluateBinop - One of Op0/Op1 is a constant expression.
 /// Attempt to symbolically evaluate the result of a binary operator merging
@@ -380,6 +640,9 @@ Constant *llvm::ConstantFoldInstruction(Instruction *I, LLVMContext &Context,
                                            Ops.data(), Ops.size(), 
                                            Context, TD);
   
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
+    return ConstantFoldLoadInst(LI, TD);
+  
   return ConstantFoldInstOperands(I->getOpcode(), I->getType(),
                                   Ops.data(), Ops.size(), Context, TD);
 }
@@ -640,15 +903,15 @@ Constant *llvm::ConstantFoldLoadThroughGEPConstantExpr(Constant *C,
           C = UndefValue::get(ATy->getElementType());
         else
           return 0;
-      } else if (const VectorType *PTy = dyn_cast<VectorType>(*I)) {
-        if (CI->getZExtValue() >= PTy->getNumElements())
+      } else if (const VectorType *VTy = dyn_cast<VectorType>(*I)) {
+        if (CI->getZExtValue() >= VTy->getNumElements())
           return 0;
         if (ConstantVector *CP = dyn_cast<ConstantVector>(C))
           C = CP->getOperand(CI->getZExtValue());
         else if (isa<ConstantAggregateZero>(C))
-          C = Constant::getNullValue(PTy->getElementType());
+          C = Constant::getNullValue(VTy->getElementType());
         else if (isa<UndefValue>(C))
-          C = UndefValue::get(PTy->getElementType());
+          C = UndefValue::get(VTy->getElementType());
         else
           return 0;
       } else {
diff --git a/lib/Analysis/DomPrinter.cpp b/lib/Analysis/DomPrinter.cpp
new file mode 100644
index 0000000..f1b44d0
--- /dev/null
+++ b/lib/Analysis/DomPrinter.cpp
@@ -0,0 +1,265 @@
+//===- DomPrinter.cpp - DOT printer for the dominance trees    ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines '-dot-dom' and '-dot-postdom' analysis passes, which emit
+// a dom.<fnname>.dot or postdom.<fnname>.dot file for each function in the
+// program, with a graph of the dominance/postdominance tree of that
+// function.
+//
+// There are also passes available to directly call dotty ('-view-dom' or
+// '-view-postdom'). By appending '-only' like '-dot-dom-only' only the
+// names of the bbs are printed, but the content is hidden.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DomPrinter.h"
+#include "llvm/Pass.h"
+#include "llvm/Function.h"
+#include "llvm/Analysis/CFGPrinter.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
+
+using namespace llvm;
+
+namespace llvm {
+template<>
+struct DOTGraphTraits<DomTreeNode*> : public DefaultDOTGraphTraits {
+  static std::string getNodeLabel(DomTreeNode *Node, DomTreeNode *Graph,
+                                  bool ShortNames) {
+
+    BasicBlock *BB = Node->getBlock();
+
+    if (!BB)
+      return "Post dominance root node";
+
+    return DOTGraphTraits<const Function*>::getNodeLabel(BB, BB->getParent(),
+                                                         ShortNames);
+  }
+};
+
+template<>
+struct DOTGraphTraits<DominatorTree*> : public DOTGraphTraits<DomTreeNode*> {
+
+  static std::string getGraphName(DominatorTree *DT) {
+    return "Dominator tree";
+  }
+
+  static std::string getNodeLabel(DomTreeNode *Node,
+                                  DominatorTree *G,
+                                  bool ShortNames) {
+    return DOTGraphTraits<DomTreeNode*>::getNodeLabel(Node, G->getRootNode(),
+                                                      ShortNames);
+  }
+};
+
+template<>
+struct DOTGraphTraits<PostDominatorTree*>
+  : public DOTGraphTraits<DomTreeNode*> {
+  static std::string getGraphName(PostDominatorTree *DT) {
+    return "Post dominator tree";
+  }
+  static std::string getNodeLabel(DomTreeNode *Node,
+                                  PostDominatorTree *G,
+                                  bool ShortNames) {
+    return DOTGraphTraits<DomTreeNode*>::getNodeLabel(Node,
+                                                      G->getRootNode(),
+                                                      ShortNames);
+  }
+};
+}
+
+namespace {
+template <class Analysis, bool OnlyBBS>
+struct GenericGraphViewer : public FunctionPass {
+  std::string Name;
+
+  GenericGraphViewer(std::string GraphName, const void *ID) : FunctionPass(ID) {
+    Name = GraphName;
+  }
+
+  virtual bool runOnFunction(Function &F) {
+    Analysis *Graph;
+
+    Graph = &getAnalysis<Analysis>();
+    ViewGraph(Graph, Name, OnlyBBS);
+
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<Analysis>();
+  }
+};
+
+struct DomViewer
+  : public GenericGraphViewer<DominatorTree, false> {
+  static char ID;
+  DomViewer() : GenericGraphViewer<DominatorTree, false>("dom", &ID){}
+};
+
+struct DomOnlyViewer
+  : public GenericGraphViewer<DominatorTree, true> {
+  static char ID;
+  DomOnlyViewer() : GenericGraphViewer<DominatorTree, true>("domonly", &ID){}
+};
+
+struct PostDomViewer
+  : public GenericGraphViewer<PostDominatorTree, false> {
+  static char ID;
+  PostDomViewer() :
+    GenericGraphViewer<PostDominatorTree, false>("postdom", &ID){}
+};
+
+struct PostDomOnlyViewer
+  : public GenericGraphViewer<PostDominatorTree, true> {
+  static char ID;
+  PostDomOnlyViewer() :
+    GenericGraphViewer<PostDominatorTree, true>("postdomonly", &ID){}
+};
+} // end anonymous namespace
+
+char DomViewer::ID = 0;
+RegisterPass<DomViewer> A("view-dom",
+                          "View dominance tree of function");
+
+char DomOnlyViewer::ID = 0;
+RegisterPass<DomOnlyViewer> B("view-dom-only",
+                              "View dominance tree of function "
+                              "(with no function bodies)");
+
+char PostDomViewer::ID = 0;
+RegisterPass<PostDomViewer> C("view-postdom",
+                              "View postdominance tree of function");
+
+char PostDomOnlyViewer::ID = 0;
+RegisterPass<PostDomOnlyViewer> D("view-postdom-only",
+                                  "View postdominance tree of function "
+                                  "(with no function bodies)");
+
+namespace {
+template <class Analysis, bool OnlyBBS>
+struct GenericGraphPrinter : public FunctionPass {
+
+  std::string Name;
+
+  GenericGraphPrinter(std::string GraphName, const void *ID)
+    : FunctionPass(ID) {
+    Name = GraphName;
+  }
+
+  virtual bool runOnFunction(Function &F) {
+    Analysis *Graph;
+    std::string Filename = Name + "." + F.getNameStr() + ".dot";
+    errs() << "Writing '" << Filename << "'...";
+
+    std::string ErrorInfo;
+    raw_fd_ostream File(Filename.c_str(), ErrorInfo);
+    Graph = &getAnalysis<Analysis>();
+
+    if (ErrorInfo.empty())
+      WriteGraph(File, Graph, OnlyBBS);
+    else
+      errs() << "  error opening file for writing!";
+    errs() << "\n";
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<Analysis>();
+  }
+};
+
+struct DomPrinter
+  : public GenericGraphPrinter<DominatorTree, false> {
+  static char ID;
+  DomPrinter() : GenericGraphPrinter<DominatorTree, false>("dom", &ID) {}
+};
+
+struct DomOnlyPrinter
+  : public GenericGraphPrinter<DominatorTree, true> {
+  static char ID;
+  DomOnlyPrinter() : GenericGraphPrinter<DominatorTree, true>("domonly", &ID) {}
+};
+
+struct PostDomPrinter
+  : public GenericGraphPrinter<PostDominatorTree, false> {
+  static char ID;
+  PostDomPrinter() :
+    GenericGraphPrinter<PostDominatorTree, false>("postdom", &ID) {}
+};
+
+struct PostDomOnlyPrinter
+  : public GenericGraphPrinter<PostDominatorTree, true> {
+  static char ID;
+  PostDomOnlyPrinter() :
+    GenericGraphPrinter<PostDominatorTree, true>("postdomonly", &ID) {}
+};
+} // end anonymous namespace
+
+
+
+char DomPrinter::ID = 0;
+RegisterPass<DomPrinter> E("dot-dom",
+                           "Print dominance tree of function "
+                           "to 'dot' file");
+
+char DomOnlyPrinter::ID = 0;
+RegisterPass<DomOnlyPrinter> F("dot-dom-only",
+                               "Print dominance tree of function "
+                               "to 'dot' file "
+                               "(with no function bodies)");
+
+char PostDomPrinter::ID = 0;
+RegisterPass<PostDomPrinter> G("dot-postdom",
+                               "Print postdominance tree of function "
+                               "to 'dot' file");
+
+char PostDomOnlyPrinter::ID = 0;
+RegisterPass<PostDomOnlyPrinter> H("dot-postdom-only",
+                                   "Print postdominance tree of function "
+                                   "to 'dot' file "
+                                   "(with no function bodies)");
+
+// Create methods available outside of this file, to use them
+// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
+// the link time optimization.
+
+FunctionPass *llvm::createDomPrinterPass() {
+  return new DomPrinter();
+}
+
+FunctionPass *llvm::createDomOnlyPrinterPass() {
+  return new DomOnlyPrinter();
+}
+
+FunctionPass *llvm::createDomViewerPass() {
+  return new DomViewer();
+}
+
+FunctionPass *llvm::createDomOnlyViewerPass() {
+  return new DomOnlyViewer();
+}
+
+FunctionPass *llvm::createPostDomPrinterPass() {
+  return new PostDomPrinter();
+}
+
+FunctionPass *llvm::createPostDomOnlyPrinterPass() {
+  return new PostDomOnlyPrinter();
+}
+
+FunctionPass *llvm::createPostDomViewerPass() {
+  return new PostDomViewer();
+}
+
+FunctionPass *llvm::createPostDomOnlyViewerPass() {
+  return new PostDomOnlyViewer();
+}
diff --git a/lib/Analysis/IPA/GlobalsModRef.cpp b/lib/Analysis/IPA/GlobalsModRef.cpp
index f5c1108..7949288 100644
--- a/lib/Analysis/IPA/GlobalsModRef.cpp
+++ b/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -303,7 +303,7 @@ bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
       // Check the value being stored.
       Value *Ptr = SI->getOperand(0)->getUnderlyingObject();
 
-      if (isa<MallocInst>(Ptr) || isMalloc(Ptr)) {
+      if (isMalloc(Ptr)) {
         // Okay, easy case.
       } else if (CallInst *CI = dyn_cast<CallInst>(Ptr)) {
         Function *F = CI->getCalledFunction();
@@ -439,8 +439,7 @@ void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
           if (cast<StoreInst>(*II).isVolatile())
             // Treat volatile stores as reading memory somewhere.
             FunctionEffect |= Ref;
-        } else if (isa<MallocInst>(*II) || isa<FreeInst>(*II) ||
-                   isMalloc(&cast<Instruction>(*II))) {
+        } else if (isMalloc(&cast<Instruction>(*II)) || isa<FreeInst>(*II)) {
           FunctionEffect |= ModRef;
         }
 
diff --git a/lib/Analysis/InlineCost.cpp b/lib/Analysis/InlineCost.cpp
index 3b0d2c9..b833baa 100644
--- a/lib/Analysis/InlineCost.cpp
+++ b/lib/Analysis/InlineCost.cpp
@@ -131,7 +131,7 @@ void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB) {
     }
     
     // These, too, are calls.
-    if (isa<MallocInst>(II) || isa<FreeInst>(II))
+    if (isa<FreeInst>(II))
       NumInsts += InlineConstants::CallPenalty;
 
     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
diff --git a/lib/Analysis/InstCount.cpp b/lib/Analysis/InstCount.cpp
index 83724ca..4cde793 100644
--- a/lib/Analysis/InstCount.cpp
+++ b/lib/Analysis/InstCount.cpp
@@ -76,11 +76,11 @@ FunctionPass *llvm::createInstCountPass() { return new InstCount(); }
 bool InstCount::runOnFunction(Function &F) {
   unsigned StartMemInsts =
     NumGetElementPtrInst + NumLoadInst + NumStoreInst + NumCallInst +
-    NumInvokeInst + NumAllocaInst + NumMallocInst + NumFreeInst;
+    NumInvokeInst + NumAllocaInst + NumFreeInst;
   visit(F);
   unsigned EndMemInsts =
     NumGetElementPtrInst + NumLoadInst + NumStoreInst + NumCallInst +
-    NumInvokeInst + NumAllocaInst + NumMallocInst + NumFreeInst;
+    NumInvokeInst + NumAllocaInst + NumFreeInst;
   TotalMemInst += EndMemInsts-StartMemInsts;
   return false;
 }
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index ce2d29f..e9256b7 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -292,6 +292,9 @@ bool Loop::isLoopSimplifyForm() const {
   // Normal-form loops have a single backedge.
   if (!getLoopLatch())
     return false;
+  // Sort the blocks vector so that we can use binary search to do quick
+  // lookups.
+  SmallPtrSet<BasicBlock *, 16> LoopBBs(block_begin(), block_end());
   // Each predecessor of each exit block of a normal loop is contained
   // within the loop.
   SmallVector<BasicBlock *, 4> ExitBlocks;
@@ -299,7 +302,7 @@ bool Loop::isLoopSimplifyForm() const {
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
     for (pred_iterator PI = pred_begin(ExitBlocks[i]),
          PE = pred_end(ExitBlocks[i]); PI != PE; ++PI)
-      if (!contains(*PI))
+      if (!LoopBBs.count(*PI))
         return false;
   // All the requirements are met.
   return true;
diff --git a/lib/Analysis/MallocHelper.cpp b/lib/Analysis/MallocHelper.cpp
index 89051d1..e7bb41e 100644
--- a/lib/Analysis/MallocHelper.cpp
+++ b/lib/Analysis/MallocHelper.cpp
@@ -130,9 +130,9 @@ static bool isArrayMallocHelper(const CallInst *CI, LLVMContext &Context,
 /// matches the malloc call IR generated by CallInst::CreateMalloc().  This 
 /// means that it is a malloc call with one bitcast use AND the malloc call's 
 /// size argument is:
-///  1. a constant not equal to the malloc's allocated type
+///  1. a constant not equal to the size of the malloced type
 /// or
-///  2. the result of a multiplication by the malloc's allocated type
+///  2. the result of a multiplication by the size of the malloced type
 /// Otherwise it returns NULL.
 /// The unique bitcast is needed to determine the type/size of the array
 /// allocation.
@@ -183,25 +183,60 @@ const Type* llvm::getMallocAllocatedType(const CallInst* CI) {
   return PT ? PT->getElementType() : NULL;
 }
 
+/// isSafeToGetMallocArraySize - Returns true if the array size of a malloc can
+/// be determined.  It can be determined in these 3 cases of malloc codegen:
+/// 1. non-array malloc: The malloc's size argument is a constant and equals the ///    size of the type being malloced.
+/// 2. array malloc: This is a malloc call with one bitcast use AND the malloc
+///    call's size argument is a constant multiple of the size of the malloced
+///    type.
+/// 3. array malloc: This is a malloc call with one bitcast use AND the malloc
+///    call's size argument is the result of a multiplication by the size of the
+///    malloced type.
+/// Otherwise returns false.
+static bool isSafeToGetMallocArraySize(const CallInst *CI,
+                                       LLVMContext &Context,
+                                       const TargetData* TD) {
+  if (!CI)
+    return false;
+
+  // Type must be known to determine array size.
+  const Type* T = getMallocAllocatedType(CI);
+  if (!T) return false;
+
+  Value* MallocArg = CI->getOperand(1);
+  Constant *ElementSize = ConstantExpr::getSizeOf(T);
+  ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, 
+                                                MallocArg->getType());
+
+  // First, check if it is a non-array malloc.
+  if (isa<ConstantExpr>(MallocArg) && (MallocArg == ElementSize))
+    return true;
+
+  // Second, check if it can be determined that this is an array malloc.
+  return isArrayMallocHelper(CI, Context, TD);
+}
+
 /// isConstantOne - Return true only if val is constant int 1.
 static bool isConstantOne(Value *val) {
   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
 }
 
-/// getMallocArraySize - Returns the array size of a malloc call.  The array
-/// size is computated in 1 of 3 ways:
-///  1. If the element type if of size 1, then array size is the argument to 
+/// getMallocArraySize - Returns the array size of a malloc call.  For array
+/// mallocs, the size is computated in 1 of 3 ways:
+///  1. If the element type is of size 1, then array size is the argument to 
 ///     malloc.
 ///  2. Else if the malloc's argument is a constant, the array size is that
 ///     argument divided by the element type's size.
 ///  3. Else the malloc argument must be a multiplication and the array size is
 ///     the first operand of the multiplication.
-/// This function returns constant 1 if:
-///  1. The malloc call's allocated type cannot be determined.
-///  2. IR wasn't created by a call to CallInst::CreateMalloc() with a non-NULL
-///     ArraySize.
+/// For non-array mallocs, the computed size is constant 1. 
+/// This function returns NULL for all mallocs whose array size cannot be
+/// determined.
 Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context,
                                 const TargetData* TD) {
+  if (!isSafeToGetMallocArraySize(CI, Context, TD))
+    return NULL;
+
   // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
   if (!isArrayMalloc(CI, Context, TD))
     return ConstantInt::get(CI->getOperand(1)->getType(), 1);
diff --git a/lib/Analysis/PointerTracking.cpp b/lib/Analysis/PointerTracking.cpp
index 43f4af3..2309fbc 100644
--- a/lib/Analysis/PointerTracking.cpp
+++ b/lib/Analysis/PointerTracking.cpp
@@ -102,8 +102,9 @@ const SCEV *PointerTracking::computeAllocationCount(Value *P,
 
   if (CallInst *CI = extractMallocCall(V)) {
     Value *arraySize = getMallocArraySize(CI, P->getContext(), TD);
-    Ty = getMallocAllocatedType(CI);
-    if (!Ty || !arraySize) return SE->getCouldNotCompute();
+    const Type* AllocTy = getMallocAllocatedType(CI);
+    if (!AllocTy || !arraySize) return SE->getCouldNotCompute();
+    Ty = AllocTy;
     // arraySize elements of type Ty.
     return SE->getSCEV(arraySize);
   }
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index baa347a..dc0d489 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -469,26 +469,11 @@ void llvm::ComputeMaskedBits(Value *V, const APInt &Mask,
     break;
   }
 
-  case Instruction::Alloca:
-  case Instruction::Malloc: {
+  case Instruction::Alloca: {
     AllocationInst *AI = cast<AllocationInst>(V);
     unsigned Align = AI->getAlignment();
-    if (Align == 0 && TD) {
-      if (isa<AllocaInst>(AI))
-        Align = TD->getABITypeAlignment(AI->getType()->getElementType());
-      else if (isa<MallocInst>(AI)) {
-        // Malloc returns maximally aligned memory.
-        Align = TD->getABITypeAlignment(AI->getType()->getElementType());
-        Align =
-          std::max(Align,
-                   (unsigned)TD->getABITypeAlignment(
-                     Type::getDoubleTy(V->getContext())));
-        Align =
-          std::max(Align,
-                   (unsigned)TD->getABITypeAlignment(
-                      Type::getInt64Ty(V->getContext())));
-      }
-    }
+    if (Align == 0 && TD)
+      Align = TD->getABITypeAlignment(AI->getType()->getElementType());
     
     if (Align > 0)
       KnownZero = Mask & APInt::getLowBitsSet(BitWidth,