X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FInstructionCombining.cpp;h=2a08ced68c85e307e4d0cb695a5dddbb5fd8fa25;hb=d5fa214729e06c7c1e0bc394c5dd9a8d05d588c5;hp=fd6d23e28f1eb7ec070b7c37d63b5585652e2f96;hpb=c10305743c313558405079452138f03124e87581;p=oota-llvm.git

diff --git a/lib/Transforms/Scalar/InstructionCombining.cpp b/lib/Transforms/Scalar/InstructionCombining.cpp
index fd6d23e28f1..2a08ced68c8 100644
--- a/lib/Transforms/Scalar/InstructionCombining.cpp
+++ b/lib/Transforms/Scalar/InstructionCombining.cpp
@@ -39,6 +39,7 @@
 #include "llvm/Pass.h"
 #include "llvm/DerivedTypes.h"
 #include "llvm/GlobalVariable.h"
+#include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Target/TargetData.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
@@ -49,9 +50,13 @@
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/PatternMatch.h"
 #include "llvm/Support/Compiler.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include <algorithm>
+#include <set>
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
@@ -66,9 +71,37 @@ namespace {
     : public FunctionPass,
       public InstVisitor<InstCombiner, Instruction*> {
     // Worklist of all of the instructions that need to be simplified.
-    std::vector<Instruction*> WorkList;
+    std::vector<Instruction*> Worklist;
+    DenseMap<Instruction*, unsigned> WorklistMap;
     TargetData *TD;
+    bool MustPreserveLCSSA;
+  public:
+    /// AddToWorkList - Add the specified instruction to the worklist if it
+    /// isn't already in it.
+    void AddToWorkList(Instruction *I) {
+      if (WorklistMap.insert(std::make_pair(I, Worklist.size())))
+        Worklist.push_back(I);
+    }
+    
+    // RemoveFromWorkList - remove I from the worklist if it exists.
+    void RemoveFromWorkList(Instruction *I) {
+      DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I);
+      if (It == WorklistMap.end()) return; // Not in worklist.
+      
+      // Don't bother moving everything down, just null out the slot.
+      Worklist[It->second] = 0;
+      
+      WorklistMap.erase(It);
+    }
+    
+    Instruction *RemoveOneFromWorkList() {
+      Instruction *I = Worklist.back();
+      Worklist.pop_back();
+      WorklistMap.erase(I);
+      return I;
+    }
 
+    
     /// AddUsersToWorkList - When an instruction is simplified, add all users of
     /// the instruction to the work lists because they might get more simplified
     /// now.
@@ -76,7 +109,7 @@ namespace {
     void AddUsersToWorkList(Value &I) {
       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
            UI != UE; ++UI)
-        WorkList.push_back(cast<Instruction>(*UI));
+        AddToWorkList(cast<Instruction>(*UI));
     }
 
     /// AddUsesToWorkList - When an instruction is simplified, add operands to
@@ -85,7 +118,7 @@ namespace {
     void AddUsesToWorkList(Instruction &I) {
       for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
         if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i)))
-          WorkList.push_back(Op);
+          AddToWorkList(Op);
     }
     
     /// AddSoonDeadInstToWorklist - The specified instruction is about to become
@@ -99,7 +132,7 @@ namespace {
       
       for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
         if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i))) {
-          WorkList.push_back(Op);
+          AddToWorkList(Op);
           // Set the operand to undef to drop the use.
           I.setOperand(i, UndefValue::get(Op->getType()));
         }
@@ -107,10 +140,10 @@ namespace {
       return R;
     }
 
-    // removeFromWorkList - remove all instances of I from the worklist.
-    void removeFromWorkList(Instruction *I);
   public:
     virtual bool runOnFunction(Function &F);
+    
+    bool DoOneIteration(Function &F, unsigned ItNum);
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<TargetData>();
@@ -143,15 +176,18 @@ namespace {
     Instruction *visitAnd(BinaryOperator &I);
     Instruction *visitOr (BinaryOperator &I);
     Instruction *visitXor(BinaryOperator &I);
+    Instruction *visitShl(BinaryOperator &I);
+    Instruction *visitAShr(BinaryOperator &I);
+    Instruction *visitLShr(BinaryOperator &I);
+    Instruction *commonShiftTransforms(BinaryOperator &I);
     Instruction *visitFCmpInst(FCmpInst &I);
     Instruction *visitICmpInst(ICmpInst &I);
     Instruction *visitICmpInstWithCastAndCast(ICmpInst &ICI);
 
     Instruction *FoldGEPICmp(User *GEPLHS, Value *RHS,
                              ICmpInst::Predicate Cond, Instruction &I);
-    Instruction *visitShiftInst(ShiftInst &I);
     Instruction *FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
-                                     ShiftInst &I);
+                                     BinaryOperator &I);
     Instruction *commonCastTransforms(CastInst &CI);
     Instruction *commonIntCastTransforms(CastInst &CI);
     Instruction *visitTrunc(CastInst &CI);
@@ -199,7 +235,7 @@ namespace {
              "New instruction already inserted into a basic block!");
       BasicBlock *BB = Old.getParent();
       BB->getInstList().insert(&Old, New);  // Insert inst
-      WorkList.push_back(New);              // Add to worklist
+      AddToWorkList(New);
       return New;
     }
 
@@ -214,7 +250,7 @@ namespace {
         return ConstantExpr::getCast(opc, CV, Ty);
       
       Instruction *C = CastInst::create(opc, V, Ty, V->getName(), &Pos);
-      WorkList.push_back(C);
+      AddToWorkList(C);
       return C;
     }
 
@@ -248,9 +284,9 @@ namespace {
       if (Old != New)
         Old->replaceAllUsesWith(New);
       if (Instruction *I = dyn_cast<Instruction>(Old))
-        WorkList.push_back(I);
+        AddToWorkList(I);
       if (Instruction *I = dyn_cast<Instruction>(New))
-        WorkList.push_back(I);
+        AddToWorkList(I);
       return true;
     }
     
@@ -261,7 +297,7 @@ namespace {
     Instruction *EraseInstFromFunction(Instruction &I) {
       assert(I.use_empty() && "Cannot erase instruction that is used!");
       AddUsesToWorkList(I);
-      removeFromWorkList(&I);
+      RemoveFromWorkList(&I);
       I.eraseFromParent();
       return 0;  // Don't do anything with FI
     }
@@ -360,7 +396,6 @@ static Value *getBitCastOperand(Value *V) {
 
 /// This function is a wrapper around CastInst::isEliminableCastPair. It
 /// simply extracts arguments and returns what that function returns.
-/// @Determine if it is valid to eliminate a Convert pair
 static Instruction::CastOps 
 isEliminableCastPair(
   const CastInst *CI, ///< The first cast instruction
@@ -446,7 +481,7 @@ bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
           Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
                                                     Op1->getOperand(0),
                                                     Op1->getName(), &I);
-          WorkList.push_back(New);
+          AddToWorkList(New);
           I.setOperand(0, New);
           I.setOperand(1, Folded);
           return true;
@@ -815,6 +850,7 @@ static void ComputeUnsignedMinMaxValuesFromKnownBits(const Type *Ty,
 bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
                                         uint64_t &KnownZero, uint64_t &KnownOne,
                                         unsigned Depth) {
+  const IntegerType *VTy = cast<IntegerType>(V->getType());
   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     // We know all of the bits for a constant!
     KnownOne = CI->getZExtValue() & DemandedMask;
@@ -831,10 +867,10 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     }
     // If this is the root being simplified, allow it to have multiple uses,
     // just set the DemandedMask to all bits.
-    DemandedMask = cast<IntegerType>(V->getType())->getBitMask();
+    DemandedMask = VTy->getBitMask();
   } else if (DemandedMask == 0) {   // Not demanding any bits from V.
-    if (V != UndefValue::get(V->getType()))
-      return UpdateValueUsesWith(V, UndefValue::get(V->getType()));
+    if (V != UndefValue::get(VTy))
+      return UpdateValueUsesWith(V, UndefValue::get(VTy));
     return false;
   } else if (Depth == 6) {        // Limit search depth.
     return false;
@@ -843,7 +879,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
   Instruction *I = dyn_cast<Instruction>(V);
   if (!I) return false;        // Only analyze instructions.
 
-  DemandedMask &= cast<IntegerType>(V->getType())->getBitMask();
+  DemandedMask &= VTy->getBitMask();
   
   uint64_t KnownZero2 = 0, KnownOne2 = 0;
   switch (I->getOpcode()) {
@@ -871,7 +907,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     
     // If all of the demanded bits in the inputs are known zeros, return zero.
     if ((DemandedMask & (KnownZero|KnownZero2)) == DemandedMask)
-      return UpdateValueUsesWith(I, Constant::getNullValue(I->getType()));
+      return UpdateValueUsesWith(I, Constant::getNullValue(VTy));
       
     // If the RHS is a constant, see if we can simplify it.
     if (ShrinkDemandedConstant(I, 1, DemandedMask & ~KnownZero2))
@@ -956,8 +992,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     //    e.g. (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
     if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask) { // all known
       if ((KnownOne & KnownOne2) == KnownOne) {
-        Constant *AndC = ConstantInt::get(I->getType(), 
-                                          ~KnownOne & DemandedMask);
+        Constant *AndC = ConstantInt::get(VTy, ~KnownOne & DemandedMask);
         Instruction *And = 
           BinaryOperator::createAnd(I->getOperand(0), AndC, "tmp");
         InsertNewInstBefore(And, *I);
@@ -1013,7 +1048,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     // Compute the bits in the result that are not present in the input.
     const IntegerType *SrcTy = cast<IntegerType>(I->getOperand(0)->getType());
     uint64_t NotIn = ~SrcTy->getBitMask();
-    uint64_t NewBits = cast<IntegerType>(I->getType())->getBitMask() & NotIn;
+    uint64_t NewBits = VTy->getBitMask() & NotIn;
     
     DemandedMask &= SrcTy->getBitMask();
     if (SimplifyDemandedBits(I->getOperand(0), DemandedMask,
@@ -1028,7 +1063,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     // Compute the bits in the result that are not present in the input.
     const IntegerType *SrcTy = cast<IntegerType>(I->getOperand(0)->getType());
     uint64_t NotIn = ~SrcTy->getBitMask();
-    uint64_t NewBits = cast<IntegerType>(I->getType())->getBitMask() & NotIn;
+    uint64_t NewBits = VTy->getBitMask() & NotIn;
     
     // Get the sign bit for the source type
     uint64_t InSignBit = 1ULL << (SrcTy->getPrimitiveSizeInBits()-1);
@@ -1051,8 +1086,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     // convert this into a zero extension.
     if ((KnownZero & InSignBit) || (NewBits & ~DemandedMask) == NewBits) {
       // Convert to ZExt cast
-      CastInst *NewCast = CastInst::create(
-        Instruction::ZExt, I->getOperand(0), I->getType(), I->getName(), I);
+      CastInst *NewCast = new ZExtInst(I->getOperand(0), VTy, I->getName(), I);
       return UpdateValueUsesWith(I, NewCast);
     } else if (KnownOne & InSignBit) {    // Input sign bit known set
       KnownOne |= NewBits;
@@ -1077,7 +1111,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
       // either.
       
       // Shift the demanded mask up so that it's at the top of the uint64_t.
-      unsigned BitWidth = I->getType()->getPrimitiveSizeInBits();
+      unsigned BitWidth = VTy->getPrimitiveSizeInBits();
       unsigned NLZ = CountLeadingZeros_64(DemandedMask << (64-BitWidth));
       
       // If the top bit of the output is demanded, demand everything from the
@@ -1173,8 +1207,8 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
       
       // Compute the new bits that are at the top now.
       uint64_t HighBits = (1ULL << ShiftAmt)-1;
-      HighBits <<= I->getType()->getPrimitiveSizeInBits() - ShiftAmt;
-      uint64_t TypeMask = cast<IntegerType>(I->getType())->getBitMask();
+      HighBits <<= VTy->getBitWidth() - ShiftAmt;
+      uint64_t TypeMask = VTy->getBitMask();
       // Unsigned shift right.
       if (SimplifyDemandedBits(I->getOperand(0),
                               (DemandedMask << ShiftAmt) & TypeMask,
@@ -1195,8 +1229,8 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
     // the shift amount is >= the size of the datatype, which is undefined.
     if (DemandedMask == 1) {
       // Perform the logical shift right.
-      Value *NewVal = new ShiftInst(Instruction::LShr, I->getOperand(0), 
-                                    I->getOperand(1), I->getName());
+      Value *NewVal = BinaryOperator::createLShr(
+                        I->getOperand(0), I->getOperand(1), I->getName());
       InsertNewInstBefore(cast<Instruction>(NewVal), *I);
       return UpdateValueUsesWith(I, NewVal);
     }    
@@ -1206,8 +1240,8 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
       
       // Compute the new bits that are at the top now.
       uint64_t HighBits = (1ULL << ShiftAmt)-1;
-      HighBits <<= I->getType()->getPrimitiveSizeInBits() - ShiftAmt;
-      uint64_t TypeMask = cast<IntegerType>(I->getType())->getBitMask();
+      HighBits <<= VTy->getBitWidth() - ShiftAmt;
+      uint64_t TypeMask = VTy->getBitMask();
       // Signed shift right.
       if (SimplifyDemandedBits(I->getOperand(0),
                                (DemandedMask << ShiftAmt) & TypeMask,
@@ -1220,15 +1254,15 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
       KnownOne  >>= ShiftAmt;
         
       // Handle the sign bits.
-      uint64_t SignBit = 1ULL << (I->getType()->getPrimitiveSizeInBits()-1);
+      uint64_t SignBit = 1ULL << (VTy->getBitWidth()-1);
       SignBit >>= ShiftAmt;  // Adjust to where it is now in the mask.
         
       // If the input sign bit is known to be zero, or if none of the top bits
       // are demanded, turn this into an unsigned shift right.
       if ((KnownZero & SignBit) || (HighBits & ~DemandedMask) == HighBits) {
         // Perform the logical shift right.
-        Value *NewVal = new ShiftInst(Instruction::LShr, I->getOperand(0), 
-                                      SA, I->getName());
+        Value *NewVal = BinaryOperator::createLShr(
+                          I->getOperand(0), SA, I->getName());
         InsertNewInstBefore(cast<Instruction>(NewVal), *I);
         return UpdateValueUsesWith(I, NewVal);
       } else if (KnownOne & SignBit) { // New bits are known one.
@@ -1241,7 +1275,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
   // If the client is only demanding bits that we know, return the known
   // constant.
   if ((DemandedMask & (KnownZero|KnownOne)) == DemandedMask)
-    return UpdateValueUsesWith(I, ConstantInt::get(I->getType(), KnownOne));
+    return UpdateValueUsesWith(I, ConstantInt::get(VTy, KnownOne));
   return false;
 }  
 
@@ -1257,7 +1291,7 @@ bool InstCombiner::SimplifyDemandedBits(Value *V, uint64_t DemandedMask,
 Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, uint64_t DemandedElts,
                                                 uint64_t &UndefElts,
                                                 unsigned Depth) {
-  unsigned VWidth = cast<PackedType>(V->getType())->getNumElements();
+  unsigned VWidth = cast<VectorType>(V->getType())->getNumElements();
   assert(VWidth <= 64 && "Vector too wide to analyze!");
   uint64_t EltMask = ~0ULL >> (64-VWidth);
   assert(DemandedElts != EltMask && (DemandedElts & ~EltMask) == 0 &&
@@ -1273,8 +1307,8 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, uint64_t DemandedElts,
   }
   
   UndefElts = 0;
-  if (ConstantPacked *CP = dyn_cast<ConstantPacked>(V)) {
-    const Type *EltTy = cast<PackedType>(V->getType())->getElementType();
+  if (ConstantVector *CP = dyn_cast<ConstantVector>(V)) {
+    const Type *EltTy = cast<VectorType>(V->getType())->getElementType();
     Constant *Undef = UndefValue::get(EltTy);
 
     std::vector<Constant*> Elts;
@@ -1290,19 +1324,19 @@ Value *InstCombiner::SimplifyDemandedVectorElts(Value *V, uint64_t DemandedElts,
       }
         
     // If we changed the constant, return it.
-    Constant *NewCP = ConstantPacked::get(Elts);
+    Constant *NewCP = ConstantVector::get(Elts);
     return NewCP != CP ? NewCP : 0;
   } else if (isa<ConstantAggregateZero>(V)) {
-    // Simplify the CAZ to a ConstantPacked where the non-demanded elements are
+    // Simplify the CAZ to a ConstantVector where the non-demanded elements are
     // set to undef.
-    const Type *EltTy = cast<PackedType>(V->getType())->getElementType();
+    const Type *EltTy = cast<VectorType>(V->getType())->getElementType();
     Constant *Zero = Constant::getNullValue(EltTy);
     Constant *Undef = UndefValue::get(EltTy);
     std::vector<Constant*> Elts;
     for (unsigned i = 0; i != VWidth; ++i)
       Elts.push_back((DemandedElts & (1ULL << i)) ? Zero : Undef);
     UndefElts = DemandedElts ^ EltMask;
-    return ConstantPacked::get(Elts);
+    return ConstantVector::get(Elts);
   }
   
   if (!V->hasOneUse()) {    // Other users may use these bits.
@@ -1544,8 +1578,8 @@ struct AddRHS {
   AddRHS(Value *rhs) : RHS(rhs) {}
   bool shouldApply(Value *LHS) const { return LHS == RHS; }
   Instruction *apply(BinaryOperator &Add) const {
-    return new ShiftInst(Instruction::Shl, Add.getOperand(0),
-                         ConstantInt::get(Type::Int8Ty, 1));
+    return BinaryOperator::createShl(Add.getOperand(0),
+                                  ConstantInt::get(Add.getType(), 1));
   }
 };
 
@@ -1593,8 +1627,6 @@ static Value *FoldOperationIntoSelectOperand(Instruction &I, Value *SO,
   else if (CmpInst *CI = dyn_cast<CmpInst>(&I))
     New = CmpInst::create(CI->getOpcode(), CI->getPredicate(), Op0, Op1, 
                           SO->getName()+".cmp");
-  else if (ShiftInst *SI = dyn_cast<ShiftInst>(&I))
-    New = new ShiftInst(SI->getOpcode(), Op0, Op1, SO->getName()+".sh");
   else {
     assert(0 && "Unknown binary instruction type!");
     abort();
@@ -1637,11 +1669,12 @@ Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
 
   // Check to see if all of the operands of the PHI are constants.  If there is
   // one non-constant value, remember the BB it is.  If there is more than one
-  // bail out.
+  // or if *it* is a PHI, bail out.
   BasicBlock *NonConstBB = 0;
   for (unsigned i = 0; i != NumPHIValues; ++i)
     if (!isa<Constant>(PN->getIncomingValue(i))) {
       if (NonConstBB) return 0;  // More than one non-const value.
+      if (isa<PHINode>(PN->getIncomingValue(i))) return 0;  // Itself a phi.
       NonConstBB = PN->getIncomingBlock(i);
       
       // If the incoming non-constant value is in I's block, we have an infinite
@@ -1660,10 +1693,10 @@ Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
   }
 
   // Okay, we can do the transformation: create the new PHI node.
-  PHINode *NewPN = new PHINode(I.getType(), I.getName());
-  I.setName("");
+  PHINode *NewPN = new PHINode(I.getType(), "");
   NewPN->reserveOperandSpace(PN->getNumOperands()/2);
   InsertNewInstBefore(NewPN, *PN);
+  NewPN->takeName(PN);
 
   // Next, add all of the operands to the PHI.
   if (I.getNumOperands() == 2) {
@@ -1686,14 +1719,10 @@ Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
                                 CI->getPredicate(),
                                 PN->getIncomingValue(i), C, "phitmp",
                                 NonConstBB->getTerminator());
-        else if (ShiftInst *SI = dyn_cast<ShiftInst>(&I))
-          InV = new ShiftInst(SI->getOpcode(),
-                              PN->getIncomingValue(i), C, "phitmp",
-                              NonConstBB->getTerminator());
         else
           assert(0 && "Unknown binop!");
         
-        WorkList.push_back(cast<Instruction>(InV));
+        AddToWorkList(cast<Instruction>(InV));
       }
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
@@ -1709,7 +1738,7 @@ Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
         InV = CastInst::create(CI->getOpcode(), PN->getIncomingValue(i), 
                                I.getType(), "phitmp", 
                                NonConstBB->getTerminator());
-        WorkList.push_back(cast<Instruction>(InV));
+        AddToWorkList(cast<Instruction>(InV));
       }
       NewPN->addIncoming(InV, PN->getIncomingBlock(i));
     }
@@ -1744,7 +1773,7 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
       // See if SimplifyDemandedBits can simplify this.  This handles stuff like
       // (X & 254)+1 -> (X&254)|1
       uint64_t KnownZero, KnownOne;
-      if (!isa<PackedType>(I.getType()) &&
+      if (!isa<VectorType>(I.getType()) &&
           SimplifyDemandedBits(&I, cast<IntegerType>(I.getType())->getBitMask(),
                                KnownZero, KnownOne))
         return &I;
@@ -1756,7 +1785,8 @@ Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
     
     ConstantInt *XorRHS = 0;
     Value *XorLHS = 0;
-    if (match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
+    if (isa<ConstantInt>(RHSC) &&
+        match(LHS, m_Xor(m_Value(XorLHS), m_ConstantInt(XorRHS)))) {
       unsigned TySizeBits = I.getType()->getPrimitiveSizeInBits();
       int64_t  RHSSExt = cast<ConstantInt>(RHSC)->getSExtValue();
       uint64_t RHSZExt = cast<ConstantInt>(RHSC)->getZExtValue();
@@ -1955,15 +1985,15 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
     // -(X >>u 31) -> (X >>s 31)
     // -(X >>s 31) -> (X >>u 31)
     if (C->isNullValue()) {
-      if (ShiftInst *SI = dyn_cast<ShiftInst>(Op1))
+      if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op1))
         if (SI->getOpcode() == Instruction::LShr) {
           if (ConstantInt *CU = dyn_cast<ConstantInt>(SI->getOperand(1))) {
             // Check to see if we are shifting out everything but the sign bit.
             if (CU->getZExtValue() == 
                 SI->getType()->getPrimitiveSizeInBits()-1) {
               // Ok, the transformation is safe.  Insert AShr.
-              return new ShiftInst(Instruction::AShr, SI->getOperand(0), CU,
-                                   SI->getName());
+              return BinaryOperator::create(Instruction::AShr, 
+                                          SI->getOperand(0), CU, SI->getName());
             }
           }
         }
@@ -1973,8 +2003,8 @@ Instruction *InstCombiner::visitSub(BinaryOperator &I) {
             if (CU->getZExtValue() == 
                 SI->getType()->getPrimitiveSizeInBits()-1) {
               // Ok, the transformation is safe.  Insert LShr. 
-              return new ShiftInst(Instruction::LShr, SI->getOperand(0), CU, 
-                                   SI->getName());
+              return BinaryOperator::createLShr(
+                                          SI->getOperand(0), CU, SI->getName());
             }
           }
         } 
@@ -2110,7 +2140,7 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) {
     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 
       // ((X << C1)*C2) == (X * (C2 << C1))
-      if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
+      if (BinaryOperator *SI = dyn_cast<BinaryOperator>(Op0))
         if (SI->getOpcode() == Instruction::Shl)
           if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
             return BinaryOperator::createMul(SI->getOperand(0),
@@ -2126,8 +2156,8 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) {
       int64_t Val = (int64_t)cast<ConstantInt>(CI)->getZExtValue();
       if (isPowerOf2_64(Val)) {          // Replace X*(2^C) with X << C
         uint64_t C = Log2_64(Val);
-        return new ShiftInst(Instruction::Shl, Op0,
-                             ConstantInt::get(Type::Int8Ty, C));
+        return BinaryOperator::createShl(Op0,
+                                      ConstantInt::get(Op0->getType(), C));
       }
     } else if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1)) {
       if (Op1F->isNullValue())
@@ -2188,10 +2218,11 @@ Instruction *InstCombiner::visitMul(BinaryOperator &I) {
       if (isa<ConstantInt>(SCIOp1) &&
           isSignBitCheck(SCI->getPredicate(), cast<ConstantInt>(SCIOp1))) {
         // Shift the X value right to turn it into "all signbits".
-        Constant *Amt = ConstantInt::get(Type::Int8Ty,
+        Constant *Amt = ConstantInt::get(SCIOp0->getType(),
                                           SCOpTy->getPrimitiveSizeInBits()-1);
         Value *V =
-          InsertNewInstBefore(new ShiftInst(Instruction::AShr, SCIOp0, Amt,
+          InsertNewInstBefore(
+            BinaryOperator::create(Instruction::AShr, SCIOp0, Amt,
                                             BoolCast->getOperand(0)->getName()+
                                             ".mask"), I);
 
@@ -2321,13 +2352,13 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
     if (uint64_t Val = C->getZExtValue())    // Don't break X / 0
       if (isPowerOf2_64(Val)) {
         uint64_t ShiftAmt = Log2_64(Val);
-        return new ShiftInst(Instruction::LShr, Op0, 
-                              ConstantInt::get(Type::Int8Ty, ShiftAmt));
+        return BinaryOperator::createLShr(Op0, 
+                                    ConstantInt::get(Op0->getType(), ShiftAmt));
       }
   }
 
   // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
-  if (ShiftInst *RHSI = dyn_cast<ShiftInst>(I.getOperand(1))) {
+  if (BinaryOperator *RHSI = dyn_cast<BinaryOperator>(I.getOperand(1))) {
     if (RHSI->getOpcode() == Instruction::Shl &&
         isa<ConstantInt>(RHSI->getOperand(0))) {
       uint64_t C1 = cast<ConstantInt>(RHSI->getOperand(0))->getZExtValue();
@@ -2338,7 +2369,7 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
           Constant *C2V = ConstantInt::get(NTy, C2);
           N = InsertNewInstBefore(BinaryOperator::createAdd(N, C2V, "tmp"), I);
         }
-        return new ShiftInst(Instruction::LShr, Op0, N);
+        return BinaryOperator::createLShr(Op0, N);
       }
     }
   }
@@ -2354,15 +2385,15 @@ Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
             // Compute the shift amounts
             unsigned TSA = Log2_64(TVA), FSA = Log2_64(FVA);
             // Construct the "on true" case of the select
-            Constant *TC = ConstantInt::get(Type::Int8Ty, TSA);
-            Instruction *TSI = 
-              new ShiftInst(Instruction::LShr, Op0, TC, SI->getName()+".t");
+            Constant *TC = ConstantInt::get(Op0->getType(), TSA);
+            Instruction *TSI = BinaryOperator::createLShr(
+                                                   Op0, TC, SI->getName()+".t");
             TSI = InsertNewInstBefore(TSI, I);
     
             // Construct the "on false" case of the select
-            Constant *FC = ConstantInt::get(Type::Int8Ty, FSA); 
-            Instruction *FSI = 
-              new ShiftInst(Instruction::LShr, Op0, FC, SI->getName()+".f");
+            Constant *FC = ConstantInt::get(Op0->getType(), FSA); 
+            Instruction *FSI = BinaryOperator::createLShr(
+                                                   Op0, FC, SI->getName()+".f");
             FSI = InsertNewInstBefore(FSI, I);
 
             // construct the select instruction and return it.
@@ -2434,7 +2465,7 @@ static Constant *GetFactor(Value *V) {
       unsigned Zeros = CountTrailingZeros_64(RHS->getZExtValue());
       if (Zeros != V->getType()->getPrimitiveSizeInBits())
         return ConstantExpr::getShl(Result, 
-                                    ConstantInt::get(Type::Int8Ty, Zeros));
+                                    ConstantInt::get(Result->getType(), Zeros));
     }
   } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
     // Only handle int->int casts.
@@ -2798,23 +2829,23 @@ struct FoldICmpLogical {
 
 // OptAndOp - This handles expressions of the form ((val OP C1) & C2).  Where
 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.  Op is
-// guaranteed to be either a shift instruction or a binary operator.
+// guaranteed to be a binary operator.
 Instruction *InstCombiner::OptAndOp(Instruction *Op,
                                     ConstantInt *OpRHS,
                                     ConstantInt *AndRHS,
                                     BinaryOperator &TheAnd) {
   Value *X = Op->getOperand(0);
   Constant *Together = 0;
-  if (!isa<ShiftInst>(Op))
+  if (!Op->isShift())
     Together = ConstantExpr::getAnd(AndRHS, OpRHS);
 
   switch (Op->getOpcode()) {
   case Instruction::Xor:
     if (Op->hasOneUse()) {
       // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
-      std::string OpName = Op->getName(); Op->setName("");
-      Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName);
+      Instruction *And = BinaryOperator::createAnd(X, AndRHS);
       InsertNewInstBefore(And, TheAnd);
+      And->takeName(Op);
       return BinaryOperator::createXor(And, Together);
     }
     break;
@@ -2824,9 +2855,9 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op,
 
     if (Op->hasOneUse() && Together != OpRHS) {
       // (X | C1) & C2 --> (X | (C1&C2)) & C2
-      std::string Op0Name = Op->getName(); Op->setName("");
-      Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name);
+      Instruction *Or = BinaryOperator::createOr(X, Together);
       InsertNewInstBefore(Or, TheAnd);
+      Or->takeName(Op);
       return BinaryOperator::createAnd(Or, AndRHS);
     }
     break;
@@ -2857,10 +2888,10 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op,
             TheAnd.setOperand(0, X);
             return &TheAnd;
           } else {
-            std::string Name = Op->getName(); Op->setName("");
             // Pull the XOR out of the AND.
-            Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS, Name);
+            Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS);
             InsertNewInstBefore(NewAnd, TheAnd);
+            NewAnd->takeName(Op);
             return BinaryOperator::createXor(NewAnd, AndRHS);
           }
         }
@@ -2914,8 +2945,9 @@ Instruction *InstCombiner::OptAndOp(Instruction *Op,
         // (Val ashr C1) & C2 -> (Val lshr C1) & C2
         // Make the argument unsigned.
         Value *ShVal = Op->getOperand(0);
-        ShVal = InsertNewInstBefore(new ShiftInst(Instruction::LShr, ShVal, 
-                                    OpRHS, Op->getName()), TheAnd);
+        ShVal = InsertNewInstBefore(
+            BinaryOperator::createLShr(ShVal, OpRHS, 
+                                   Op->getName()), TheAnd);
         return BinaryOperator::createAnd(ShVal, AndRHS, TheAnd.getName());
       }
     }
@@ -3062,12 +3094,12 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   // See if we can simplify any instructions used by the instruction whose sole 
   // purpose is to compute bits we don't care about.
   uint64_t KnownZero, KnownOne;
-  if (!isa<PackedType>(I.getType())) {
+  if (!isa<VectorType>(I.getType())) {
     if (SimplifyDemandedBits(&I, cast<IntegerType>(I.getType())->getBitMask(),
                              KnownZero, KnownOne))
     return &I;
   } else {
-    if (ConstantPacked *CP = dyn_cast<ConstantPacked>(Op1)) {
+    if (ConstantVector *CP = dyn_cast<ConstantVector>(Op1)) {
       if (CP->isAllOnesValue())
         return ReplaceInstUsesWith(I, I.getOperand(0));
     }
@@ -3079,7 +3111,7 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
     uint64_t NotAndRHS = AndRHSMask^TypeMask;
 
     // Optimize a variety of ((val OP C1) & C2) combinations...
-    if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
+    if (isa<BinaryOperator>(Op0)) {
       Instruction *Op0I = cast<Instruction>(Op0);
       Value *Op0LHS = Op0I->getOperand(0);
       Value *Op0RHS = Op0I->getOperand(1);
@@ -3288,7 +3320,8 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
                 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
                                                       LHSVal->getName()+".off");
                 InsertNewInstBefore(Add, I);
-                return new ICmpInst(ICmpInst::ICMP_UGT, Add, AddCST);
+                return new ICmpInst(ICmpInst::ICMP_UGT, Add,
+                                    ConstantInt::get(Add->getType(), 1));
               }
               break;                        // (X != 13 & X != 15) -> no change
             }
@@ -3387,16 +3420,17 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
       }
     
   // (X >> Z) & (Y >> Z)  -> (X&Y) >> Z  for all shifts.
-  if (ShiftInst *SI1 = dyn_cast<ShiftInst>(Op1)) {
-    if (ShiftInst *SI0 = dyn_cast<ShiftInst>(Op0))
-      if (SI0->getOpcode() == SI1->getOpcode() && 
+  if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) {
+    if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0))
+      if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() && 
           SI0->getOperand(1) == SI1->getOperand(1) &&
           (SI0->hasOneUse() || SI1->hasOneUse())) {
         Instruction *NewOp =
           InsertNewInstBefore(BinaryOperator::createAnd(SI0->getOperand(0),
                                                         SI1->getOperand(0),
                                                         SI0->getName()), I);
-        return new ShiftInst(SI1->getOpcode(), NewOp, SI1->getOperand(1));
+        return BinaryOperator::create(SI1->getOpcode(), NewOp, 
+                                      SI1->getOperand(1));
       }
   }
 
@@ -3406,7 +3440,7 @@ Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
 /// CollectBSwapParts - Look to see if the specified value defines a single byte
 /// in the result.  If it does, and if the specified byte hasn't been filled in
 /// yet, fill it in and return false.
-static bool CollectBSwapParts(Value *V, std::vector<Value*> &ByteValues) {
+static bool CollectBSwapParts(Value *V, SmallVector<Value*, 8> &ByteValues) {
   Instruction *I = dyn_cast<Instruction>(V);
   if (I == 0) return true;
 
@@ -3417,7 +3451,7 @@ static bool CollectBSwapParts(Value *V, std::vector<Value*> &ByteValues) {
   
   // If this is a shift by a constant int, and it is "24", then its operand
   // defines a byte.  We only handle unsigned types here.
-  if (isa<ShiftInst>(I) && isa<ConstantInt>(I->getOperand(1))) {
+  if (I->isShift() && isa<ConstantInt>(I->getOperand(1))) {
     // Not shifting the entire input by N-1 bytes?
     if (cast<ConstantInt>(I->getOperand(1))->getZExtValue() !=
         8*(ByteValues.size()-1))
@@ -3484,13 +3518,13 @@ static bool CollectBSwapParts(Value *V, std::vector<Value*> &ByteValues) {
 /// MatchBSwap - Given an OR instruction, check to see if this is a bswap idiom.
 /// If so, insert the new bswap intrinsic and return it.
 Instruction *InstCombiner::MatchBSwap(BinaryOperator &I) {
-  // We can only handle bswap of unsigned integers, and cannot bswap one byte.
+  // We cannot bswap one byte.
   if (I.getType() == Type::Int8Ty)
     return 0;
   
   /// ByteValues - For each byte of the result, we keep track of which value
   /// defines each byte.
-  std::vector<Value*> ByteValues;
+  SmallVector<Value*, 8> ByteValues;
   ByteValues.resize(TD->getTypeSize(I.getType()));
     
   // Try to find all the pieces corresponding to the bswap.
@@ -3539,7 +3573,7 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   // See if we can simplify any instructions used by the instruction whose sole 
   // purpose is to compute bits we don't care about.
   uint64_t KnownZero, KnownOne;
-  if (!isa<PackedType>(I.getType()) &&
+  if (!isa<VectorType>(I.getType()) &&
       SimplifyDemandedBits(&I, cast<IntegerType>(I.getType())->getBitMask(),
                            KnownZero, KnownOne))
     return &I;
@@ -3549,17 +3583,17 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
     ConstantInt *C1 = 0; Value *X = 0;
     // (X & C1) | C2 --> (X | C2) & (C1|C2)
     if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
-      Instruction *Or = BinaryOperator::createOr(X, RHS, Op0->getName());
-      Op0->setName("");
+      Instruction *Or = BinaryOperator::createOr(X, RHS);
       InsertNewInstBefore(Or, I);
+      Or->takeName(Op0);
       return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, C1));
     }
 
     // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
     if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
-      std::string Op0Name = Op0->getName(); Op0->setName("");
-      Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
+      Instruction *Or = BinaryOperator::createOr(X, RHS);
       InsertNewInstBefore(Or, I);
+      Or->takeName(Op0);
       return BinaryOperator::createXor(Or,
                  ConstantExpr::getAnd(C1, ConstantExpr::getNot(RHS)));
     }
@@ -3596,17 +3630,19 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   // (X^C)|Y -> (X|Y)^C iff Y&C == 0
   if (Op0->hasOneUse() && match(Op0, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
       MaskedValueIsZero(Op1, C1->getZExtValue())) {
-    Instruction *NOr = BinaryOperator::createOr(A, Op1, Op0->getName());
-    Op0->setName("");
-    return BinaryOperator::createXor(InsertNewInstBefore(NOr, I), C1);
+    Instruction *NOr = BinaryOperator::createOr(A, Op1);
+    InsertNewInstBefore(NOr, I);
+    NOr->takeName(Op0);
+    return BinaryOperator::createXor(NOr, C1);
   }
 
   // Y|(X^C) -> (X|Y)^C iff Y&C == 0
   if (Op1->hasOneUse() && match(Op1, m_Xor(m_Value(A), m_ConstantInt(C1))) &&
       MaskedValueIsZero(Op0, C1->getZExtValue())) {
-    Instruction *NOr = BinaryOperator::createOr(A, Op0, Op1->getName());
-    Op0->setName("");
-    return BinaryOperator::createXor(InsertNewInstBefore(NOr, I), C1);
+    Instruction *NOr = BinaryOperator::createOr(A, Op0);
+    InsertNewInstBefore(NOr, I);
+    NOr->takeName(Op0);
+    return BinaryOperator::createXor(NOr, C1);
   }
 
   // (A & C1)|(B & C2)
@@ -3643,16 +3679,17 @@ Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   }
   
   // (X >> Z) | (Y >> Z)  -> (X|Y) >> Z  for all shifts.
-  if (ShiftInst *SI1 = dyn_cast<ShiftInst>(Op1)) {
-    if (ShiftInst *SI0 = dyn_cast<ShiftInst>(Op0))
-      if (SI0->getOpcode() == SI1->getOpcode() && 
+  if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) {
+    if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0))
+      if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() && 
           SI0->getOperand(1) == SI1->getOperand(1) &&
           (SI0->hasOneUse() || SI1->hasOneUse())) {
         Instruction *NewOp =
         InsertNewInstBefore(BinaryOperator::createOr(SI0->getOperand(0),
                                                      SI1->getOperand(0),
                                                      SI0->getName()), I);
-        return new ShiftInst(SI1->getOpcode(), NewOp, SI1->getOperand(1));
+        return BinaryOperator::create(SI1->getOpcode(), NewOp, 
+                                      SI1->getOperand(1));
       }
   }
 
@@ -3867,7 +3904,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   // See if we can simplify any instructions used by the instruction whose sole 
   // purpose is to compute bits we don't care about.
   uint64_t KnownZero, KnownOne;
-  if (!isa<PackedType>(I.getType()) &&
+  if (!isa<VectorType>(I.getType()) &&
       SimplifyDemandedBits(&I, cast<IntegerType>(I.getType())->getBitMask(),
                            KnownZero, KnownOne))
     return &I;
@@ -3920,7 +3957,7 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
             Constant *CommonBits = ConstantExpr::getAnd(Op0CI, RHS);
             NewRHS = ConstantExpr::getAnd(NewRHS, 
                                           ConstantExpr::getNot(CommonBits));
-            WorkList.push_back(Op0I);
+            AddToWorkList(Op0I);
             I.setOperand(0, Op0I->getOperand(0));
             I.setOperand(1, NewRHS);
             return &I;
@@ -4021,16 +4058,17 @@ Instruction *InstCombiner::visitXor(BinaryOperator &I) {
       }
 
   // (X >> Z) ^ (Y >> Z)  -> (X^Y) >> Z  for all shifts.
-  if (ShiftInst *SI1 = dyn_cast<ShiftInst>(Op1)) {
-    if (ShiftInst *SI0 = dyn_cast<ShiftInst>(Op0))
-      if (SI0->getOpcode() == SI1->getOpcode() && 
+  if (BinaryOperator *SI1 = dyn_cast<BinaryOperator>(Op1)) {
+    if (BinaryOperator *SI0 = dyn_cast<BinaryOperator>(Op0))
+      if (SI0->isShift() && SI0->getOpcode() == SI1->getOpcode() && 
           SI0->getOperand(1) == SI1->getOperand(1) &&
           (SI0->hasOneUse() || SI1->hasOneUse())) {
         Instruction *NewOp =
         InsertNewInstBefore(BinaryOperator::createXor(SI0->getOperand(0),
                                                       SI1->getOperand(0),
                                                       SI0->getName()), I);
-        return new ShiftInst(SI1->getOpcode(), NewOp, SI1->getOperand(1));
+        return BinaryOperator::create(SI1->getOpcode(), NewOp, 
+                                      SI1->getOperand(1));
       }
   }
     
@@ -4595,14 +4633,9 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
           // could exist), turn it into (X & (C2 << C1)) != (C3 << C1).  This
           // happens a LOT in code produced by the C front-end, for bitfield
           // access.
-          ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0));
-
-          // Check to see if there is a noop-cast between the shift and the and.
-          if (!Shift) {
-            if (CastInst *CI = dyn_cast<CastInst>(LHSI->getOperand(0)))
-              if (CI->getOpcode() == Instruction::BitCast)
-                Shift = dyn_cast<ShiftInst>(CI->getOperand(0));
-          }
+          BinaryOperator *Shift = dyn_cast<BinaryOperator>(LHSI->getOperand(0));
+          if (Shift && !Shift->isShift())
+            Shift = 0;
 
           ConstantInt *ShAmt;
           ShAmt = Shift ? dyn_cast<ConstantInt>(Shift->getOperand(1)) : 0;
@@ -4620,7 +4653,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
               int ShAmtVal = Ty->getPrimitiveSizeInBits()-ShAmt->getZExtValue();
               if (ShAmtVal < 0) ShAmtVal = 0; // Out of range shift.
 
-              Constant *OShAmt = ConstantInt::get(Type::Int8Ty, ShAmtVal);
+              Constant *OShAmt = ConstantInt::get(AndTy, ShAmtVal);
               Constant *ShVal =
                 ConstantExpr::getShl(ConstantInt::getAllOnesValue(AndTy), 
                                      OShAmt);
@@ -4654,7 +4687,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
                   NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
                 LHSI->setOperand(1, NewAndCST);
                 LHSI->setOperand(0, Shift->getOperand(0));
-                WorkList.push_back(Shift); // Shift is dead.
+                AddToWorkList(Shift); // Shift is dead.
                 AddUsesToWorkList(I);
                 return &I;
               }
@@ -4670,12 +4703,12 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
             // Compute C << Y.
             Value *NS;
             if (Shift->getOpcode() == Instruction::LShr) {
-              NS = new ShiftInst(Instruction::Shl, AndCST, Shift->getOperand(1),
-                                 "tmp");
+              NS = BinaryOperator::createShl(AndCST, 
+                                          Shift->getOperand(1), "tmp");
             } else {
               // Insert a logical shift.
-              NS = new ShiftInst(Instruction::LShr, AndCST,
-                                 Shift->getOperand(1), "tmp");
+              NS = BinaryOperator::createLShr(AndCST,
+                                          Shift->getOperand(1), "tmp");
             }
             InsertNewInstBefore(cast<Instruction>(NS), I);
 
@@ -4945,9 +4978,9 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
             else if (Value *NegVal = dyn_castNegVal(BOp0))
               return new ICmpInst(I.getPredicate(), NegVal, BOp1);
             else if (BO->hasOneUse()) {
-              Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
-              BO->setName("");
+              Instruction *Neg = BinaryOperator::createNeg(BOp1);
               InsertNewInstBefore(Neg, I);
+              Neg->takeName(BO);
               return new ICmpInst(I.getPredicate(), BOp0, Neg);
             }
           }
@@ -5020,21 +5053,21 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
         default: break;
         case Intrinsic::bswap_i16: 
           // icmp eq (bswap(x)), c -> icmp eq (x,bswap(c))
-          WorkList.push_back(II);  // Dead?
+          AddToWorkList(II);  // Dead?
           I.setOperand(0, II->getOperand(1));
           I.setOperand(1, ConstantInt::get(Type::Int16Ty,
                                            ByteSwap_16(CI->getZExtValue())));
           return &I;
         case Intrinsic::bswap_i32:   
           // icmp eq (bswap(x)), c -> icmp eq (x,bswap(c))
-          WorkList.push_back(II);  // Dead?
+          AddToWorkList(II);  // Dead?
           I.setOperand(0, II->getOperand(1));
           I.setOperand(1, ConstantInt::get(Type::Int32Ty,
                                            ByteSwap_32(CI->getZExtValue())));
           return &I;
         case Intrinsic::bswap_i64:   
           // icmp eq (bswap(x)), c -> icmp eq (x,bswap(c))
-          WorkList.push_back(II);  // Dead?
+          AddToWorkList(II);  // Dead?
           I.setOperand(0, II->getOperand(1));
           I.setOperand(1, ConstantInt::get(Type::Int64Ty,
                                            ByteSwap_64(CI->getZExtValue())));
@@ -5058,7 +5091,7 @@ Instruction *InstCombiner::visitICmpInst(ICmpInst &I) {
               ConstantInt *CUI = cast<ConstantInt>(CI);
               if (CUI->getZExtValue() == 1ULL << (SrcTySize-1))
                 return new ICmpInst(ICmpInst::ICMP_SGT, CastOp, 
-                                    ConstantInt::get(SrcTy, -1));
+                                    ConstantInt::get(SrcTy, -1ULL));
               break;
             }
             case ICmpInst::ICMP_UGT: { // X u> 127 => X s< 0
@@ -5364,13 +5397,25 @@ Instruction *InstCombiner::visitICmpInstWithCastAndCast(ICmpInst &ICI) {
   }
 }
 
-Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
-  assert(I.getOperand(1)->getType() == Type::Int8Ty);
+Instruction *InstCombiner::visitShl(BinaryOperator &I) {
+  return commonShiftTransforms(I);
+}
+
+Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
+  return commonShiftTransforms(I);
+}
+
+Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
+  return commonShiftTransforms(I);
+}
+
+Instruction *InstCombiner::commonShiftTransforms(BinaryOperator &I) {
+  assert(I.getOperand(1)->getType() == I.getOperand(0)->getType());
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // shl X, 0 == X and shr X, 0 == X
   // shl 0, X == 0 and shr 0, X == 0
-  if (Op1 == Constant::getNullValue(Type::Int8Ty) ||
+  if (Op1 == Constant::getNullValue(Op1->getType()) ||
       Op0 == Constant::getNullValue(Op0->getType()))
     return ReplaceInstUsesWith(I, Op0);
   
@@ -5403,7 +5448,7 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
   if (I.isArithmeticShift()) {
     if (MaskedValueIsZero(Op0,
                           1ULL << (I.getType()->getPrimitiveSizeInBits()-1))) {
-      return new ShiftInst(Instruction::LShr, Op0, Op1, I.getName());
+      return BinaryOperator::createLShr(Op0, Op1, I.getName());
     }
   }
 
@@ -5414,10 +5459,8 @@ Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
 }
 
 Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
-                                               ShiftInst &I) {
+                                               BinaryOperator &I) {
   bool isLeftShift    = I.getOpcode() == Instruction::Shl;
-  bool isSignedShift  = I.getOpcode() == Instruction::AShr;
-  bool isUnsignedShift = !isSignedShift;
 
   // See if we can simplify any instructions used by the instruction whose sole 
   // purpose is to compute bits we don't care about.
@@ -5431,10 +5474,10 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
   //
   unsigned TypeBits = Op0->getType()->getPrimitiveSizeInBits();
   if (Op1->getZExtValue() >= TypeBits) {
-    if (isUnsignedShift || isLeftShift)
+    if (I.getOpcode() != Instruction::AShr)
       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
     else {
-      I.setOperand(1, ConstantInt::get(Type::Int8Ty, TypeBits-1));
+      I.setOperand(1, ConstantInt::get(I.getType(), TypeBits-1));
       return &I;
     }
   }
@@ -5464,13 +5507,13 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
         case Instruction::Add:
         case Instruction::And:
         case Instruction::Or:
-        case Instruction::Xor:
+        case Instruction::Xor: {
           // These operators commute.
           // Turn (Y + (X >> C)) << C  ->  (X + (Y << C)) & (~0 << C)
           if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
               match(Op0BO->getOperand(1),
                     m_Shr(m_Value(V1), m_ConstantInt(CC))) && CC == Op1) {
-            Instruction *YS = new ShiftInst(Instruction::Shl, 
+            Instruction *YS = BinaryOperator::createShl(
                                             Op0BO->getOperand(0), Op1,
                                             Op0BO->getName());
             InsertNewInstBefore(YS, I); // (Y << C)
@@ -5484,14 +5527,14 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
           }
           
           // Turn (Y + ((X >> C) & CC)) << C  ->  ((X & (CC << C)) + (Y << C))
-          if (isLeftShift && Op0BO->getOperand(1)->hasOneUse() &&
-              match(Op0BO->getOperand(1),
-                    m_And(m_Shr(m_Value(V1), m_Value(V2)),
-                          m_ConstantInt(CC))) && V2 == Op1 &&
-      cast<BinaryOperator>(Op0BO->getOperand(1))->getOperand(0)->hasOneUse()) {
-            Instruction *YS = new ShiftInst(Instruction::Shl, 
-                                            Op0BO->getOperand(0), Op1,
-                                            Op0BO->getName());
+          Value *Op0BOOp1 = Op0BO->getOperand(1);
+          if (isLeftShift && Op0BOOp1->hasOneUse() && V2 == Op1 &&
+              match(Op0BOOp1, 
+                    m_And(m_Shr(m_Value(V1), m_Value(V2)),m_ConstantInt(CC))) &&
+              cast<BinaryOperator>(Op0BOOp1)->getOperand(0)-> hasOneUse()) {
+            Instruction *YS = BinaryOperator::createShl(
+                                                     Op0BO->getOperand(0), Op1,
+                                                     Op0BO->getName());
             InsertNewInstBefore(YS, I); // (Y << C)
             Instruction *XM =
               BinaryOperator::createAnd(V1, ConstantExpr::getShl(CC, Op1),
@@ -5500,16 +5543,17 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
             
             return BinaryOperator::create(Op0BO->getOpcode(), YS, XM);
           }
+        }
           
-          // FALL THROUGH.
-        case Instruction::Sub:
+        // FALL THROUGH.
+        case Instruction::Sub: {
           // Turn ((X >> C) + Y) << C  ->  (X + (Y << C)) & (~0 << C)
           if (isLeftShift && Op0BO->getOperand(0)->hasOneUse() &&
               match(Op0BO->getOperand(0),
                     m_Shr(m_Value(V1), m_ConstantInt(CC))) && CC == Op1) {
-            Instruction *YS = new ShiftInst(Instruction::Shl, 
-                                            Op0BO->getOperand(1), Op1,
-                                            Op0BO->getName());
+            Instruction *YS = BinaryOperator::createShl(
+                                                     Op0BO->getOperand(1), Op1,
+                                                     Op0BO->getName());
             InsertNewInstBefore(YS, I); // (Y << C)
             Instruction *X =
               BinaryOperator::create(Op0BO->getOpcode(), V1, YS,
@@ -5527,9 +5571,9 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
                           m_ConstantInt(CC))) && V2 == Op1 &&
               cast<BinaryOperator>(Op0BO->getOperand(0))
                   ->getOperand(0)->hasOneUse()) {
-            Instruction *YS = new ShiftInst(Instruction::Shl, 
-                                            Op0BO->getOperand(1), Op1,
-                                            Op0BO->getName());
+            Instruction *YS = BinaryOperator::createShl(
+                                                     Op0BO->getOperand(1), Op1,
+                                                     Op0BO->getName());
             InsertNewInstBefore(YS, I); // (Y << C)
             Instruction *XM =
               BinaryOperator::createAnd(V1, ConstantExpr::getShl(CC, Op1),
@@ -5540,6 +5584,7 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
           }
           
           break;
+        }
       }
       
       
@@ -5569,7 +5614,7 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
         // the constant which would cause it to be modified for this
         // operation.
         //
-        if (isValid && !isLeftShift && isSignedShift) {
+        if (isValid && !isLeftShift && I.getOpcode() == Instruction::AShr) {
           uint64_t Val = Op0C->getZExtValue();
           isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
         }
@@ -5578,10 +5623,9 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
           Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, Op1);
           
           Instruction *NewShift =
-            new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), Op1,
-                          Op0BO->getName());
-          Op0BO->setName("");
+            BinaryOperator::create(I.getOpcode(), Op0BO->getOperand(0), Op1);
           InsertNewInstBefore(NewShift, I);
+          NewShift->takeName(Op0BO);
           
           return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
                                         NewRHS);
@@ -5591,110 +5635,129 @@ Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, ConstantInt *Op1,
   }
   
   // Find out if this is a shift of a shift by a constant.
-  ShiftInst *ShiftOp = 0;
-  if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
-    ShiftOp = Op0SI;
-  else if (BitCastInst *CI = dyn_cast<BitCastInst>(Op0)) {
-    // If this is a noop-integer cast of a shift instruction, use the shift.
-    if (isa<ShiftInst>(CI->getOperand(0))) {
-      ShiftOp = cast<ShiftInst>(CI->getOperand(0));
-    }
-  }
+  BinaryOperator *ShiftOp = dyn_cast<BinaryOperator>(Op0);
+  if (ShiftOp && !ShiftOp->isShift())
+    ShiftOp = 0;
   
   if (ShiftOp && isa<ConstantInt>(ShiftOp->getOperand(1))) {
-    // Find the operands and properties of the input shift.  Note that the
-    // signedness of the input shift may differ from the current shift if there
-    // is a noop cast between the two.
-    bool isShiftOfLeftShift   = ShiftOp->getOpcode() == Instruction::Shl;
-    bool isShiftOfSignedShift = ShiftOp->getOpcode() == Instruction::AShr;
-    bool isShiftOfUnsignedShift = !isShiftOfSignedShift;
-    
     ConstantInt *ShiftAmt1C = cast<ConstantInt>(ShiftOp->getOperand(1));
-
     unsigned ShiftAmt1 = (unsigned)ShiftAmt1C->getZExtValue();
     unsigned ShiftAmt2 = (unsigned)Op1->getZExtValue();
+    assert(ShiftAmt2 != 0 && "Should have been simplified earlier");
+    if (ShiftAmt1 == 0) return 0;  // Will be simplified in the future.
+    Value *X = ShiftOp->getOperand(0);
     
-    // Check for (A << c1) << c2   and   (A >> c1) >> c2.
-    if (isLeftShift == isShiftOfLeftShift) {
-      // Do not fold these shifts if the first one is signed and the second one
-      // is unsigned and this is a right shift.  Further, don't do any folding
-      // on them.
-      if (isShiftOfSignedShift && isUnsignedShift && !isLeftShift)
-        return 0;
-      
-      unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift.
-      if (Amt > Op0->getType()->getPrimitiveSizeInBits())
-        Amt = Op0->getType()->getPrimitiveSizeInBits();
-      
-      Value *Op = ShiftOp->getOperand(0);
-      ShiftInst *ShiftResult = new ShiftInst(I.getOpcode(), Op,
-                                          ConstantInt::get(Type::Int8Ty, Amt));
-      if (I.getType() == ShiftResult->getType())
-        return ShiftResult;
-      InsertNewInstBefore(ShiftResult, I);
-      return CastInst::create(Instruction::BitCast, ShiftResult, I.getType());
+    unsigned AmtSum = ShiftAmt1+ShiftAmt2;   // Fold into one big shift.
+    if (AmtSum > I.getType()->getPrimitiveSizeInBits())
+      AmtSum = I.getType()->getPrimitiveSizeInBits();
+    
+    const IntegerType *Ty = cast<IntegerType>(I.getType());
+    
+    // Check for (X << c1) << c2  and  (X >> c1) >> c2
+    if (I.getOpcode() == ShiftOp->getOpcode()) {
+      return BinaryOperator::create(I.getOpcode(), X,
+                                    ConstantInt::get(Ty, AmtSum));
+    } else if (ShiftOp->getOpcode() == Instruction::LShr &&
+               I.getOpcode() == Instruction::AShr) {
+      // ((X >>u C1) >>s C2) -> (X >>u (C1+C2))  since C1 != 0.
+      return BinaryOperator::createLShr(X, ConstantInt::get(Ty, AmtSum));
+    } else if (ShiftOp->getOpcode() == Instruction::AShr &&
+               I.getOpcode() == Instruction::LShr) {
+      // ((X >>s C1) >>u C2) -> ((X >>s (C1+C2)) & mask) since C1 != 0.
+      Instruction *Shift =
+        BinaryOperator::createAShr(X, ConstantInt::get(Ty, AmtSum));
+      InsertNewInstBefore(Shift, I);
+
+      uint64_t Mask = Ty->getBitMask() >> ShiftAmt2;
+      return BinaryOperator::createAnd(Shift, ConstantInt::get(Ty, Mask));
     }
     
-    // Check for (A << c1) >> c2 or (A >> c1) << c2.  If we are dealing with
-    // signed types, we can only support the (A >> c1) << c2 configuration,
-    // because it can not turn an arbitrary bit of A into a sign bit.
-    if (isUnsignedShift || isLeftShift) {
-      // Calculate bitmask for what gets shifted off the edge.
-      Constant *C = ConstantInt::getAllOnesValue(I.getType());
-      if (isLeftShift)
-        C = ConstantExpr::getShl(C, ShiftAmt1C);
-      else
-        C = ConstantExpr::getLShr(C, ShiftAmt1C);
-      
-      Value *Op = ShiftOp->getOperand(0);
+    // Okay, if we get here, one shift must be left, and the other shift must be
+    // right.  See if the amounts are equal.
+    if (ShiftAmt1 == ShiftAmt2) {
+      // If we have ((X >>? C) << C), turn this into X & (-1 << C).
+      if (I.getOpcode() == Instruction::Shl) {
+        uint64_t Mask = Ty->getBitMask() << ShiftAmt1;
+        return BinaryOperator::createAnd(X, ConstantInt::get(Ty, Mask));
+      }
+      // If we have ((X << C) >>u C), turn this into X & (-1 >>u C).
+      if (I.getOpcode() == Instruction::LShr) {
+        uint64_t Mask = Ty->getBitMask() >> ShiftAmt1;
+        return BinaryOperator::createAnd(X, ConstantInt::get(Ty, Mask));
+      }
+      // We can simplify ((X << C) >>s C) into a trunc + sext.
+      // NOTE: we could do this for any C, but that would make 'unusual' integer
+      // types.  For now, just stick to ones well-supported by the code
+      // generators.
+      const Type *SExtType = 0;
+      switch (Ty->getBitWidth() - ShiftAmt1) {
+      case 8 : SExtType = Type::Int8Ty; break;
+      case 16: SExtType = Type::Int16Ty; break;
+      case 32: SExtType = Type::Int32Ty; break;
+      default: break;
+      }
+      if (SExtType) {
+        Instruction *NewTrunc = new TruncInst(X, SExtType, "sext");
+        InsertNewInstBefore(NewTrunc, I);
+        return new SExtInst(NewTrunc, Ty);
+      }
+      // Otherwise, we can't handle it yet.
+    } else if (ShiftAmt1 < ShiftAmt2) {
+      unsigned ShiftDiff = ShiftAmt2-ShiftAmt1;
       
-      Instruction *Mask =
-        BinaryOperator::createAnd(Op, C, Op->getName()+".mask");
-      InsertNewInstBefore(Mask, I);
+      // (X >>? C1) << C2 --> X << (C2-C1) & (-1 << C2)
+      if (I.getOpcode() == Instruction::Shl) {
+        assert(ShiftOp->getOpcode() == Instruction::LShr ||
+               ShiftOp->getOpcode() == Instruction::AShr);
+        Instruction *Shift =
+          BinaryOperator::createShl(X, ConstantInt::get(Ty, ShiftDiff));
+        InsertNewInstBefore(Shift, I);
+        
+        uint64_t Mask = Ty->getBitMask() << ShiftAmt2;
+        return BinaryOperator::createAnd(Shift, ConstantInt::get(Ty, Mask));
+      }
       
-      // Figure out what flavor of shift we should use...
-      if (ShiftAmt1 == ShiftAmt2) {
-        return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
-      } else if (ShiftAmt1 < ShiftAmt2) {
-        return new ShiftInst(I.getOpcode(), Mask,
-                         ConstantInt::get(Type::Int8Ty, ShiftAmt2-ShiftAmt1));
-      } else if (isShiftOfUnsignedShift || isShiftOfLeftShift) {
-        if (isShiftOfUnsignedShift && !isShiftOfLeftShift && isSignedShift) {
-          return new ShiftInst(Instruction::LShr, Mask, 
-            ConstantInt::get(Type::Int8Ty, ShiftAmt1-ShiftAmt2));
-        } else {
-          return new ShiftInst(ShiftOp->getOpcode(), Mask,
-                    ConstantInt::get(Type::Int8Ty, ShiftAmt1-ShiftAmt2));
-        }
-      } else {
-        // (X >>s C1) << C2  where C1 > C2  === (X >>s (C1-C2)) & mask
+      // (X << C1) >>u C2  --> X >>u (C2-C1) & (-1 >> C2)
+      if (I.getOpcode() == Instruction::LShr) {
+        assert(ShiftOp->getOpcode() == Instruction::Shl);
         Instruction *Shift =
-          new ShiftInst(ShiftOp->getOpcode(), Mask,
-                        ConstantInt::get(Type::Int8Ty, ShiftAmt1-ShiftAmt2));
+          BinaryOperator::createLShr(X, ConstantInt::get(Ty, ShiftDiff));
         InsertNewInstBefore(Shift, I);
         
-        C = ConstantInt::getAllOnesValue(Shift->getType());
-        C = ConstantExpr::getShl(C, Op1);
-        return BinaryOperator::createAnd(Shift, C, Op->getName()+".mask");
+        uint64_t Mask = Ty->getBitMask() >> ShiftAmt2;
+        return BinaryOperator::createAnd(Shift, ConstantInt::get(Ty, Mask));
       }
+      
+      // We can't handle (X << C1) >>s C2, it shifts arbitrary bits in.
     } else {
-      // We can handle signed (X << C1) >>s C2 if it's a sign extend.  In
-      // this case, C1 == C2 and C1 is 8, 16, or 32.
-      if (ShiftAmt1 == ShiftAmt2) {
-        const Type *SExtType = 0;
-        switch (Op0->getType()->getPrimitiveSizeInBits() - ShiftAmt1) {
-        case 8 : SExtType = Type::Int8Ty; break;
-        case 16: SExtType = Type::Int16Ty; break;
-        case 32: SExtType = Type::Int32Ty; break;
-        }
+      assert(ShiftAmt2 < ShiftAmt1);
+      unsigned ShiftDiff = ShiftAmt1-ShiftAmt2;
+
+      // (X >>? C1) << C2 --> X >>? (C1-C2) & (-1 << C2)
+      if (I.getOpcode() == Instruction::Shl) {
+        assert(ShiftOp->getOpcode() == Instruction::LShr ||
+               ShiftOp->getOpcode() == Instruction::AShr);
+        Instruction *Shift =
+          BinaryOperator::create(ShiftOp->getOpcode(), X,
+                                 ConstantInt::get(Ty, ShiftDiff));
+        InsertNewInstBefore(Shift, I);
         
-        if (SExtType) {
-          Instruction *NewTrunc = 
-            new TruncInst(ShiftOp->getOperand(0), SExtType, "sext");
-          InsertNewInstBefore(NewTrunc, I);
-          return new SExtInst(NewTrunc, I.getType());
-        }
+        uint64_t Mask = Ty->getBitMask() << ShiftAmt2;
+        return BinaryOperator::createAnd(Shift, ConstantInt::get(Ty, Mask));
+      }
+      
+      // (X << C1) >>u C2  --> X << (C1-C2) & (-1 >> C2)
+      if (I.getOpcode() == Instruction::LShr) {
+        assert(ShiftOp->getOpcode() == Instruction::Shl);
+        Instruction *Shift =
+          BinaryOperator::createShl(X, ConstantInt::get(Ty, ShiftDiff));
+        InsertNewInstBefore(Shift, I);
+        
+        uint64_t Mask = Ty->getBitMask() >> ShiftAmt2;
+        return BinaryOperator::createAnd(Shift, ConstantInt::get(Ty, Mask));
       }
+      
+      // We can't handle (X << C1) >>a C2, it shifts arbitrary bits in.
     }
   }
   return 0;
@@ -5757,20 +5820,16 @@ Instruction *InstCombiner::PromoteCastOfAllocation(CastInst &CI,
   
   // Remove any uses of AI that are dead.
   assert(!CI.use_empty() && "Dead instructions should be removed earlier!");
-  std::vector<Instruction*> DeadUsers;
+  
   for (Value::use_iterator UI = AI.use_begin(), E = AI.use_end(); UI != E; ) {
     Instruction *User = cast<Instruction>(*UI++);
     if (isInstructionTriviallyDead(User)) {
       while (UI != E && *UI == User)
         ++UI; // If this instruction uses AI more than once, don't break UI.
       
-      // Add operands to the worklist.
-      AddUsesToWorkList(*User);
       ++NumDeadInst;
       DOUT << "IC: DCE: " << *User;
-      
-      User->eraseFromParent();
-      removeFromWorkList(User);
+      EraseInstFromFunction(*User);
     }
   }
   
@@ -5779,8 +5838,8 @@ Instruction *InstCombiner::PromoteCastOfAllocation(CastInst &CI,
   const Type *CastElTy = PTy->getElementType();
   if (!AllocElTy->isSized() || !CastElTy->isSized()) return 0;
 
-  unsigned AllocElTyAlign = TD->getTypeAlignment(AllocElTy);
-  unsigned CastElTyAlign = TD->getTypeAlignment(CastElTy);
+  unsigned AllocElTyAlign = TD->getABITypeAlignment(AllocElTy);
+  unsigned CastElTyAlign = TD->getABITypeAlignment(CastElTy);
   if (CastElTyAlign < AllocElTyAlign) return 0;
 
   // If the allocation has multiple uses, only promote it if we are strictly
@@ -5826,13 +5885,13 @@ Instruction *InstCombiner::PromoteCastOfAllocation(CastInst &CI,
     Amt = InsertNewInstBefore(Tmp, AI);
   }
   
-  std::string Name = AI.getName(); AI.setName("");
   AllocationInst *New;
   if (isa<MallocInst>(AI))
-    New = new MallocInst(CastElTy, Amt, AI.getAlignment(), Name);
+    New = new MallocInst(CastElTy, Amt, AI.getAlignment());
   else
-    New = new AllocaInst(CastElTy, Amt, AI.getAlignment(), Name);
+    New = new AllocaInst(CastElTy, Amt, AI.getAlignment());
   InsertNewInstBefore(New, AI);
+  New->takeName(&AI);
   
   // If the allocation has multiple uses, insert a cast and change all things
   // that used it to use the new cast.  This will also hack on CI, but it will
@@ -5849,35 +5908,62 @@ Instruction *InstCombiner::PromoteCastOfAllocation(CastInst &CI,
 }
 
 /// CanEvaluateInDifferentType - Return true if we can take the specified value
-/// and return it without inserting any new casts.  This is used by code that
-/// tries to decide whether promoting or shrinking integer operations to wider
-/// or smaller types will allow us to eliminate a truncate or extend.
-static bool CanEvaluateInDifferentType(Value *V, const Type *Ty,
+/// and return it as type Ty without inserting any new casts and without
+/// changing the computed value.  This is used by code that tries to decide
+/// whether promoting or shrinking integer operations to wider or smaller types
+/// will allow us to eliminate a truncate or extend.
+///
+/// This is a truncation operation if Ty is smaller than V->getType(), or an
+/// extension operation if Ty is larger.
+static bool CanEvaluateInDifferentType(Value *V, const IntegerType *Ty,
                                        int &NumCastsRemoved) {
-  if (isa<Constant>(V)) return true;
+  // We can always evaluate constants in another type.
+  if (isa<ConstantInt>(V))
+    return true;
   
   Instruction *I = dyn_cast<Instruction>(V);
-  if (!I || !I->hasOneUse()) return false;
+  if (!I) return false;
+  
+  const IntegerType *OrigTy = cast<IntegerType>(V->getType());
   
   switch (I->getOpcode()) {
+  case Instruction::Add:
+  case Instruction::Sub:
   case Instruction::And:
   case Instruction::Or:
   case Instruction::Xor:
+    if (!I->hasOneUse()) return false;
     // These operators can all arbitrarily be extended or truncated.
     return CanEvaluateInDifferentType(I->getOperand(0), Ty, NumCastsRemoved) &&
            CanEvaluateInDifferentType(I->getOperand(1), Ty, NumCastsRemoved);
-  case Instruction::AShr:
-  case Instruction::LShr:
+
   case Instruction::Shl:
-    // If this is just a bitcast changing the sign of the operation, we can
-    // convert if the operand can be converted.
-    if (V->getType()->getPrimitiveSizeInBits() == Ty->getPrimitiveSizeInBits())
-      return CanEvaluateInDifferentType(I->getOperand(0), Ty, NumCastsRemoved);
+    if (!I->hasOneUse()) return false;
+    // If we are truncating the result of this SHL, and if it's a shift of a
+    // constant amount, we can always perform a SHL in a smaller type.
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
+      if (Ty->getBitWidth() < OrigTy->getBitWidth() &&
+          CI->getZExtValue() < Ty->getBitWidth())
+        return CanEvaluateInDifferentType(I->getOperand(0), Ty,NumCastsRemoved);
+    }
+    break;
+  case Instruction::LShr:
+    if (!I->hasOneUse()) return false;
+    // If this is a truncate of a logical shr, we can truncate it to a smaller
+    // lshr iff we know that the bits we would otherwise be shifting in are
+    // already zeros.
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
+      if (Ty->getBitWidth() < OrigTy->getBitWidth() &&
+          MaskedValueIsZero(I->getOperand(0),
+                            OrigTy->getBitMask() & ~Ty->getBitMask()) &&
+          CI->getZExtValue() < Ty->getBitWidth()) {
+        return CanEvaluateInDifferentType(I->getOperand(0), Ty, NumCastsRemoved);
+      }
+    }
     break;
   case Instruction::Trunc:
   case Instruction::ZExt:
   case Instruction::SExt:
-  case Instruction::BitCast:
     // If this is a cast from the destination type, we can trivially eliminate
     // it, and this will remove a cast overall.
     if (I->getOperand(0)->getType() == Ty) {
@@ -5903,7 +5989,7 @@ static bool CanEvaluateInDifferentType(Value *V, const Type *Ty,
 /// CanEvaluateInDifferentType returns true for, actually insert the code to
 /// evaluate the expression.
 Value *InstCombiner::EvaluateInDifferentType(Value *V, const Type *Ty, 
-                                             bool isSigned ) {
+                                             bool isSigned) {
   if (Constant *C = dyn_cast<Constant>(V))
     return ConstantExpr::getIntegerCast(C, Ty, isSigned /*Sext or ZExt*/);
 
@@ -5911,21 +5997,18 @@ Value *InstCombiner::EvaluateInDifferentType(Value *V, const Type *Ty,
   Instruction *I = cast<Instruction>(V);
   Instruction *Res = 0;
   switch (I->getOpcode()) {
+  case Instruction::Add:
+  case Instruction::Sub:
   case Instruction::And:
   case Instruction::Or:
-  case Instruction::Xor: {
-    Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
-    Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
-    Res = BinaryOperator::create((Instruction::BinaryOps)I->getOpcode(),
-                                 LHS, RHS, I->getName());
-    break;
-  }
+  case Instruction::Xor:
   case Instruction::AShr:
   case Instruction::LShr:
   case Instruction::Shl: {
     Value *LHS = EvaluateInDifferentType(I->getOperand(0), Ty, isSigned);
-    Res = new ShiftInst((Instruction::OtherOps)I->getOpcode(), LHS,
-                        I->getOperand(1), I->getName());
+    Value *RHS = EvaluateInDifferentType(I->getOperand(1), Ty, isSigned);
+    Res = BinaryOperator::create((Instruction::BinaryOps)I->getOpcode(),
+                                 LHS, RHS, I->getName());
     break;
   }    
   case Instruction::Trunc:
@@ -6007,8 +6090,8 @@ Instruction *InstCombiner::commonCastTransforms(CastInst &CI) {
   return 0;
 }
 
-/// Only the TRUNC, ZEXT, SEXT, and BITCONVERT can have both operands as
-/// integers. This function implements the common transforms for all those
+/// Only the TRUNC, ZEXT, SEXT, and BITCAST can both operand and result as
+/// integer types. This function implements the common transforms for all those
 /// cases.
 /// @brief Implement the transforms common to CastInst with integer operands
 Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
@@ -6034,9 +6117,11 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
   if (!SrcI || !Src->hasOneUse())
     return 0;
 
-  // Attempt to propagate the cast into the instruction.
+  // Attempt to propagate the cast into the instruction for int->int casts.
   int NumCastsRemoved = 0;
-  if (CanEvaluateInDifferentType(SrcI, DestTy, NumCastsRemoved)) {
+  if (!isa<BitCastInst>(CI) &&
+      CanEvaluateInDifferentType(SrcI, cast<IntegerType>(DestTy),
+                                 NumCastsRemoved)) {
     // If this cast is a truncate, evaluting in a different type always
     // eliminates the cast, so it is always a win.  If this is a noop-cast
     // this just removes a noop cast which isn't pointful, but simplifies
@@ -6045,27 +6130,24 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
     // the input have eliminated at least one cast.  If this is a sign
     // extension, we insert two new casts (to do the extension) so we
     // require that two casts have been eliminated.
-    bool DoXForm = CI.isNoopCast(TD->getIntPtrType());
-    if (!DoXForm) {
-      switch (CI.getOpcode()) {
-        case Instruction::Trunc:
-          DoXForm = true;
-          break;
-        case Instruction::ZExt:
-          DoXForm = NumCastsRemoved >= 1;
-          break;
-        case Instruction::SExt:
-          DoXForm = NumCastsRemoved >= 2;
-          break;
-        case Instruction::BitCast:
-          DoXForm = false;
-          break;
-        default:
-          // All the others use floating point so we shouldn't actually 
-          // get here because of the check above.
-          assert(!"Unknown cast type .. unreachable");
-          break;
-      }
+    bool DoXForm;
+    switch (CI.getOpcode()) {
+    default:
+      // All the others use floating point so we shouldn't actually 
+      // get here because of the check above.
+      assert(0 && "Unknown cast type");
+    case Instruction::Trunc:
+      DoXForm = true;
+      break;
+    case Instruction::ZExt:
+      DoXForm = NumCastsRemoved >= 1;
+      break;
+    case Instruction::SExt:
+      DoXForm = NumCastsRemoved >= 2;
+      break;
+    case Instruction::BitCast:
+      DoXForm = false;
+      break;
     }
     
     if (DoXForm) {
@@ -6163,7 +6245,8 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
       Instruction::CastOps opcode = (DestBitSize == SrcBitSize ?
           Instruction::BitCast : Instruction::Trunc);
       Value *Op0c = InsertOperandCastBefore(opcode, Op0, DestTy, SrcI);
-      return new ShiftInst(Instruction::Shl, Op0c, Op1);
+      Value *Op1c = InsertOperandCastBefore(opcode, Op1, DestTy, SrcI);
+      return BinaryOperator::createShl(Op0c, Op1c);
     }
     break;
   case Instruction::AShr:
@@ -6175,7 +6258,7 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
       unsigned ShiftAmt = cast<ConstantInt>(Op1)->getZExtValue();
       if (SrcBitSize > ShiftAmt && SrcBitSize-ShiftAmt >= DestBitSize) {
         // Insert the new logical shift right.
-        return new ShiftInst(Instruction::LShr, Op0, Op1);
+        return BinaryOperator::createLShr(Op0, Op1);
       }
     }
     break;
@@ -6221,9 +6304,9 @@ Instruction *InstCombiner::commonIntCastTransforms(CastInst &CI) {
             // Perform a logical shr by shiftamt.
             // Insert the shift to put the result in the low bit.
             In = InsertNewInstBefore(
-              new ShiftInst(Instruction::LShr, In,
-                            ConstantInt::get(Type::Int8Ty, ShiftAmt),
-                            In->getName()+".lobit"), CI);
+              BinaryOperator::createLShr(In,
+                                     ConstantInt::get(In->getType(), ShiftAmt),
+                                     In->getName()+".lobit"), CI);
           }
           
           if ((Op1CV != 0) == isNE) { // Toggle the low bit.
@@ -6270,8 +6353,10 @@ Instruction *InstCombiner::visitTrunc(CastInst &CI) {
 
           // Okay, we can shrink this.  Truncate the input, then return a new
           // shift.
-          Value *V = InsertCastBefore(Instruction::Trunc, SrcIOp0, Ty, CI);
-          return new ShiftInst(Instruction::LShr, V, SrcI->getOperand(1));
+          Value *V1 = InsertCastBefore(Instruction::Trunc, SrcIOp0, Ty, CI);
+          Value *V2 = InsertCastBefore(Instruction::Trunc, SrcI->getOperand(1),
+                                       Ty, CI);
+          return BinaryOperator::createLShr(V1, V2);
         }
       } else {     // This is a variable shr.
         
@@ -6281,9 +6366,9 @@ Instruction *InstCombiner::visitTrunc(CastInst &CI) {
         if (CI.getType() == Type::Int1Ty && SrcI->hasOneUse()) {
           Value *One = ConstantInt::get(SrcI->getType(), 1);
 
-          Value *V = InsertNewInstBefore(new ShiftInst(Instruction::Shl, One,
-                                                       SrcI->getOperand(1),
-                                                       "tmp"), CI);
+          Value *V = InsertNewInstBefore(
+              BinaryOperator::createShl(One, SrcI->getOperand(1),
+                                     "tmp"), CI);
           V = InsertNewInstBefore(BinaryOperator::createAnd(V,
                                                             SrcI->getOperand(0),
                                                             "tmp"), CI);
@@ -6414,8 +6499,8 @@ Instruction *InstCombiner::visitBitCast(CastInst &CI) {
 
       // If we found a path from the src to dest, create the getelementptr now.
       if (SrcElTy == DstElTy) {
-        std::vector<Value*> Idxs(NumZeros+1, ZeroUInt);
-        return new GetElementPtrInst(Src, Idxs);
+        SmallVector<Value*, 8> Idxs(NumZeros+1, ZeroUInt);
+        return new GetElementPtrInst(Src, &Idxs[0], Idxs.size());
       }
     }
   }
@@ -6424,8 +6509,8 @@ Instruction *InstCombiner::visitBitCast(CastInst &CI) {
     if (SVI->hasOneUse()) {
       // Okay, we have (bitconvert (shuffle ..)).  Check to see if this is
       // a bitconvert to a vector with the same # elts.
-      if (isa<PackedType>(DestTy) && 
-          cast<PackedType>(DestTy)->getNumElements() == 
+      if (isa<VectorType>(DestTy) && 
+          cast<VectorType>(DestTy)->getNumElements() == 
                 SVI->getType()->getNumElements()) {
         CastInst *Tmp;
         // If either of the operands is a cast from CI.getType(), then
@@ -6487,11 +6572,10 @@ static Constant *GetSelectFoldableConstant(Instruction *I) {
   case Instruction::Sub:
   case Instruction::Or:
   case Instruction::Xor:
-    return Constant::getNullValue(I->getType());
   case Instruction::Shl:
   case Instruction::LShr:
   case Instruction::AShr:
-    return Constant::getNullValue(Type::Int8Ty);
+    return Constant::getNullValue(I->getType());
   case Instruction::And:
     return ConstantInt::getAllOnesValue(I->getType());
   case Instruction::Mul:
@@ -6521,8 +6605,8 @@ Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI,
                             TI->getType());
   }
 
-  // Only handle binary, compare and shift operators here.
-  if (!isa<ShiftInst>(TI) && !isa<BinaryOperator>(TI))
+  // Only handle binary operators here.
+  if (!isa<BinaryOperator>(TI))
     return 0;
 
   // Figure out if the operations have any operands in common.
@@ -6565,12 +6649,8 @@ Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI,
     else
       return BinaryOperator::create(BO->getOpcode(), NewSI, MatchOp);
   }
-
-  assert(isa<ShiftInst>(TI) && "Should only have Shift here");
-  if (MatchIsOpZero)
-    return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), MatchOp, NewSI);
-  else
-    return new ShiftInst(cast<ShiftInst>(TI)->getOpcode(), NewSI, MatchOp);
+  assert(0 && "Shouldn't get here");
+  return 0;
 }
 
 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
@@ -6659,9 +6739,9 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
               // same width. Make an all-ones value by inserting a AShr.
               Value *X = IC->getOperand(0);
               unsigned Bits = X->getType()->getPrimitiveSizeInBits();
-              Constant *ShAmt = ConstantInt::get(Type::Int8Ty, Bits-1);
-              Instruction *SRA = new ShiftInst(Instruction::AShr, X,
-                                               ShAmt, "ones");
+              Constant *ShAmt = ConstantInt::get(X->getType(), Bits-1);
+              Instruction *SRA = BinaryOperator::create(Instruction::AShr, X,
+                                                        ShAmt, "ones");
               InsertNewInstBefore(SRA, SI);
               
               // Finally, convert to the type of the select RHS.  We figure out
@@ -6818,15 +6898,12 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
 
           if (OpToFold) {
             Constant *C = GetSelectFoldableConstant(TVI);
-            std::string Name = TVI->getName(); TVI->setName("");
             Instruction *NewSel =
-              new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C,
-                             Name);
+              new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C);
             InsertNewInstBefore(NewSel, SI);
+            NewSel->takeName(TVI);
             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
               return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel);
-            else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI))
-              return new ShiftInst(SI->getOpcode(), FalseVal, NewSel);
             else {
               assert(0 && "Unknown instruction!!");
             }
@@ -6846,18 +6923,14 @@ Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
 
           if (OpToFold) {
             Constant *C = GetSelectFoldableConstant(FVI);
-            std::string Name = FVI->getName(); FVI->setName("");
             Instruction *NewSel =
-              new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold),
-                             Name);
+              new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold));
             InsertNewInstBefore(NewSel, SI);
+            NewSel->takeName(FVI);
             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
               return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel);
-            else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI))
-              return new ShiftInst(SI->getOpcode(), TrueVal, NewSel);
-            else {
+            else
               assert(0 && "Unknown instruction!!");
-            }
           }
         }
   }
@@ -6878,18 +6951,22 @@ static unsigned GetKnownAlignment(Value *V, TargetData *TD) {
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
     unsigned Align = GV->getAlignment();
     if (Align == 0 && TD) 
-      Align = TD->getTypeAlignment(GV->getType()->getElementType());
+      Align = TD->getPrefTypeAlignment(GV->getType()->getElementType());
     return Align;
   } else if (AllocationInst *AI = dyn_cast<AllocationInst>(V)) {
     unsigned Align = AI->getAlignment();
     if (Align == 0 && TD) {
       if (isa<AllocaInst>(AI))
-        Align = TD->getTypeAlignment(AI->getType()->getElementType());
+        Align = TD->getPrefTypeAlignment(AI->getType()->getElementType());
       else if (isa<MallocInst>(AI)) {
         // Malloc returns maximally aligned memory.
-        Align = TD->getTypeAlignment(AI->getType()->getElementType());
-        Align = std::max(Align, (unsigned)TD->getTypeAlignment(Type::DoubleTy));
-        Align = std::max(Align, (unsigned)TD->getTypeAlignment(Type::Int64Ty));
+        Align = TD->getABITypeAlignment(AI->getType()->getElementType());
+        Align =
+          std::max(Align,
+                   (unsigned)TD->getABITypeAlignment(Type::DoubleTy));
+        Align =
+          std::max(Align,
+                   (unsigned)TD->getABITypeAlignment(Type::Int64Ty));
       }
     }
     return Align;
@@ -6924,10 +7001,12 @@ static unsigned GetKnownAlignment(Value *V, TargetData *TD) {
     if (!TD) return 0;
 
     const Type *BasePtrTy = GEPI->getOperand(0)->getType();
-    if (TD->getTypeAlignment(cast<PointerType>(BasePtrTy)->getElementType())
+    const PointerType *PtrTy = cast<PointerType>(BasePtrTy);
+    if (TD->getABITypeAlignment(PtrTy->getElementType())
         <= BaseAlignment) {
       const Type *GEPTy = GEPI->getType();
-      return TD->getTypeAlignment(cast<PointerType>(GEPTy)->getElementType());
+      const PointerType *GEPPtrTy = cast<PointerType>(GEPTy);
+      return TD->getABITypeAlignment(GEPPtrTy->getElementType());
     }
     return 0;
   }
@@ -7052,7 +7131,7 @@ Instruction *InstCombiner::visitCallInst(CallInst &CI) {
       
     case Intrinsic::ppc_altivec_vperm:
       // Turn vperm(V1,V2,mask) -> shuffle(V1,V2,mask) if mask is a constant.
-      if (ConstantPacked *Mask = dyn_cast<ConstantPacked>(II->getOperand(3))) {
+      if (ConstantVector *Mask = dyn_cast<ConstantVector>(II->getOperand(3))) {
         assert(Mask->getNumOperands() == 16 && "Bad type for intrinsic!");
         
         // Check that all of the elements are integer constants or undefs.
@@ -7227,7 +7306,7 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) {
 
   // Check to see if we are changing the return type...
   if (OldRetTy != FT->getReturnType()) {
-    if (Callee->isExternal() && !Caller->use_empty() && 
+    if (Callee->isDeclaration() && !Caller->use_empty() && 
         OldRetTy != FT->getReturnType() &&
         // Conversion is ok if changing from pointer to int of same size.
         !(isa<PointerType>(FT->getReturnType()) &&
@@ -7263,11 +7342,11 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) {
        ParamTy->getPrimitiveSizeInBits() >= ActTy->getPrimitiveSizeInBits()) ||
       (c && ParamTy->getPrimitiveSizeInBits() >= ActTy->getPrimitiveSizeInBits()
        && c->getSExtValue() > 0);
-    if (Callee->isExternal() && !isConvertible) return false;
+    if (Callee->isDeclaration() && !isConvertible) return false;
   }
 
   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
-      Callee->isExternal())
+      Callee->isDeclaration())
     return false;   // Do not delete arguments unless we have a function body...
 
   // Okay, we decided that this is a safe thing to do: go ahead and start
@@ -7316,21 +7395,21 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) {
     }
 
   if (FT->getReturnType() == Type::VoidTy)
-    Caller->setName("");   // Void type should not have a name...
+    Caller->setName("");   // Void type should not have a name.
 
   Instruction *NC;
   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
     NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
-                        Args, Caller->getName(), Caller);
+                        &Args[0], Args.size(), Caller->getName(), Caller);
     cast<InvokeInst>(II)->setCallingConv(II->getCallingConv());
   } else {
-    NC = new CallInst(Callee, Args, Caller->getName(), Caller);
+    NC = new CallInst(Callee, &Args[0], Args.size(), Caller->getName(), Caller);
     if (cast<CallInst>(Caller)->isTailCall())
       cast<CallInst>(NC)->setTailCall();
    cast<CallInst>(NC)->setCallingConv(cast<CallInst>(Caller)->getCallingConv());
   }
 
-  // Insert a cast of the return type as necessary...
+  // Insert a cast of the return type as necessary.
   Value *NV = NC;
   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
     if (NV->getType() != Type::VoidTy) {
@@ -7357,8 +7436,8 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) {
 
   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
     Caller->replaceAllUsesWith(NV);
-  Caller->getParent()->getInstList().erase(Caller);
-  removeFromWorkList(Caller);
+  Caller->eraseFromParent();
+  RemoveFromWorkList(Caller);
   return true;
 }
 
@@ -7367,8 +7446,8 @@ bool InstCombiner::transformConstExprCastCall(CallSite CS) {
 /// and a single binop.
 Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
-  assert(isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst) ||
-         isa<GetElementPtrInst>(FirstInst) || isa<CmpInst>(FirstInst));
+  assert(isa<BinaryOperator>(FirstInst) || isa<GetElementPtrInst>(FirstInst) ||
+         isa<CmpInst>(FirstInst));
   unsigned Opc = FirstInst->getOpcode();
   Value *LHSVal = FirstInst->getOperand(0);
   Value *RHSVal = FirstInst->getOperand(1);
@@ -7442,8 +7521,6 @@ Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
   else if (CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst))
     return CmpInst::create(CIOp->getOpcode(), CIOp->getPredicate(), LHSVal, 
                            RHSVal);
-  else if (ShiftInst *SI = dyn_cast<ShiftInst>(FirstInst))
-    return new ShiftInst(SI->getOpcode(), LHSVal, RHSVal);
   else {
     assert(isa<GetElementPtrInst>(FirstInst));
     return new GetElementPtrInst(LHSVal, RHSVal);
@@ -7454,12 +7531,36 @@ Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
 /// of the block that defines it.  This means that it must be obvious the value
 /// of the load is not changed from the point of the load to the end of the
 /// block it is in.
+///
+/// Finally, it is safe, but not profitable, to sink a load targetting a
+/// non-address-taken alloca.  Doing so will cause us to not promote the alloca
+/// to a register.
 static bool isSafeToSinkLoad(LoadInst *L) {
   BasicBlock::iterator BBI = L, E = L->getParent()->end();
   
   for (++BBI; BBI != E; ++BBI)
     if (BBI->mayWriteToMemory())
       return false;
+  
+  // Check for non-address taken alloca.  If not address-taken already, it isn't
+  // profitable to do this xform.
+  if (AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
+    bool isAddressTaken = false;
+    for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
+         UI != E; ++UI) {
+      if (isa<LoadInst>(UI)) continue;
+      if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
+        // If storing TO the alloca, then the address isn't taken.
+        if (SI->getOperand(1) == AI) continue;
+      }
+      isAddressTaken = true;
+      break;
+    }
+    
+    if (!isAddressTaken)
+      return false;
+  }
+  
   return true;
 }
 
@@ -7479,8 +7580,7 @@ Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
   bool isVolatile = false;
   if (isa<CastInst>(FirstInst)) {
     CastSrcTy = FirstInst->getOperand(0)->getType();
-  } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst) ||
-             isa<CmpInst>(FirstInst)) {
+  } else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
     // Can fold binop, compare or shift here if the RHS is a constant, 
     // otherwise call FoldPHIArgBinOpIntoPHI.
     ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
@@ -7562,8 +7662,7 @@ Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
     return CmpInst::create(CIOp->getOpcode(), CIOp->getPredicate(), 
                            PhiVal, ConstantOp);
   else
-    return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(),
-                         PhiVal, ConstantOp);
+    assert(0 && "Unknown operation");
 }
 
 /// DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle
@@ -7586,7 +7685,7 @@ static bool DeadPHICycle(PHINode *PN, std::set<PHINode*> &PotentiallyDeadPHIs) {
 //
 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
   // If LCSSA is around, don't mess with Phi nodes
-  if (mustPreserveAnalysisID(LCSSAID)) return 0;
+  if (MustPreserveLCSSA) return 0;
   
   if (Value *V = PN.hasConstantValue())
     return ReplaceInstUsesWith(PN, V);
@@ -7697,9 +7796,9 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
   // is a getelementptr instruction, combine the indices of the two
   // getelementptr instructions into a single instruction.
   //
-  std::vector<Value*> SrcGEPOperands;
+  SmallVector<Value*, 8> SrcGEPOperands;
   if (User *Src = dyn_castGetElementPtr(PtrOp))
-    SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
+    SrcGEPOperands.append(Src->op_begin(), Src->op_end());
 
   if (!SrcGEPOperands.empty()) {
     // Note that if our source is a gep chain itself that we wait for that
@@ -7710,7 +7809,7 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
         cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
       return 0;   // Wait until our source is folded to completion.
 
-    std::vector<Value *> Indices;
+    SmallVector<Value*, 8> Indices;
 
     // Find out whether the last index in the source GEP is a sequential idx.
     bool EndsWithSequential = false;
@@ -7781,20 +7880,22 @@ Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
     }
 
     if (!Indices.empty())
-      return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
+      return new GetElementPtrInst(SrcGEPOperands[0], &Indices[0],
+                                   Indices.size(), GEP.getName());
 
   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
     // GEP of global variable.  If all of the indices for this GEP are
     // constants, we can promote this to a constexpr instead of an instruction.
 
     // Scan for nonconstants...
-    std::vector<Constant*> Indices;
+    SmallVector<Constant*, 8> Indices;
     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
     for (; I != E && isa<Constant>(*I); ++I)
       Indices.push_back(cast<Constant>(*I));
 
     if (I == E) {  // If they are all constants...
-      Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices);
+      Constant *CE = ConstantExpr::getGetElementPtr(GV,
+                                                    &Indices[0],Indices.size());
 
       // Replace all uses of the GEP with the new constexpr...
       return ReplaceInstUsesWith(GEP, CE);
@@ -7984,27 +8085,28 @@ static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
   if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
     const Type *SrcPTy = SrcTy->getElementType();
 
-    if ((DestPTy->isInteger() && DestPTy != Type::Int1Ty) ||
-        isa<PointerType>(DestPTy) || isa<PackedType>(DestPTy)) {
+    if (DestPTy->isInteger() || isa<PointerType>(DestPTy) || 
+         isa<VectorType>(DestPTy)) {
       // If the source is an array, the code below will not succeed.  Check to
       // see if a trivial 'gep P, 0, 0' will help matters.  Only do this for
       // constants.
       if (const ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
         if (Constant *CSrc = dyn_cast<Constant>(CastOp))
           if (ASrcTy->getNumElements() != 0) {
-            std::vector<Value*> Idxs(2, Constant::getNullValue(Type::Int32Ty));
-            CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
+            Value *Idxs[2];
+            Idxs[0] = Idxs[1] = Constant::getNullValue(Type::Int32Ty);
+            CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs, 2);
             SrcTy = cast<PointerType>(CastOp->getType());
             SrcPTy = SrcTy->getElementType();
           }
 
-      if (((SrcPTy->isInteger() && SrcPTy != Type::Int1Ty) ||
-           isa<PointerType>(SrcPTy) || isa<PackedType>(SrcPTy)) &&
+      if ((SrcPTy->isInteger() || isa<PointerType>(SrcPTy) || 
+            isa<VectorType>(SrcPTy)) &&
           // Do not allow turning this into a load of an integer, which is then
           // casted to a pointer, this pessimizes pointer analysis a lot.
           (isa<PointerType>(SrcPTy) == isa<PointerType>(LI.getType())) &&
-          IC.getTargetData().getTypeSize(SrcPTy) ==
-               IC.getTargetData().getTypeSize(DestPTy)) {
+          IC.getTargetData().getTypeSizeInBits(SrcPTy) ==
+               IC.getTargetData().getTypeSizeInBits(DestPTy)) {
 
         // Okay, we are casting from one integer or pointer type to another of
         // the same size.  Instead of casting the pointer before the load, cast
@@ -8095,14 +8197,14 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
 
     // Instcombine load (constant global) into the value loaded.
     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
-      if (GV->isConstant() && !GV->isExternal())
+      if (GV->isConstant() && !GV->isDeclaration())
         return ReplaceInstUsesWith(LI, GV->getInitializer());
 
     // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded.
     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
       if (CE->getOpcode() == Instruction::GetElementPtr) {
         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
-          if (GV->isConstant() && !GV->isExternal())
+          if (GV->isConstant() && !GV->isDeclaration())
             if (Constant *V = 
                ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE))
               return ReplaceInstUsesWith(LI, V);
@@ -8162,7 +8264,7 @@ Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
   return 0;
 }
 
-/// InstCombineStoreToCast - Fold 'store V, (cast P)' -> store (cast V), P'
+/// InstCombineStoreToCast - Fold store V, (cast P) -> store (cast V), P
 /// when possible.
 static Instruction *InstCombineStoreToCast(InstCombiner &IC, StoreInst &SI) {
   User *CI = cast<User>(SI.getOperand(1));
@@ -8172,24 +8274,23 @@ static Instruction *InstCombineStoreToCast(InstCombiner &IC, StoreInst &SI) {
   if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
     const Type *SrcPTy = SrcTy->getElementType();
 
-    if ((DestPTy->isInteger() && DestPTy != Type::Int1Ty) ||
-        isa<PointerType>(DestPTy)) {
+    if (DestPTy->isInteger() || isa<PointerType>(DestPTy)) {
       // If the source is an array, the code below will not succeed.  Check to
       // see if a trivial 'gep P, 0, 0' will help matters.  Only do this for
       // constants.
       if (const ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
         if (Constant *CSrc = dyn_cast<Constant>(CastOp))
           if (ASrcTy->getNumElements() != 0) {
-            std::vector<Value*> Idxs(2, Constant::getNullValue(Type::Int32Ty));
-            CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
+            Value* Idxs[2];
+            Idxs[0] = Idxs[1] = Constant::getNullValue(Type::Int32Ty);
+            CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs, 2);
             SrcTy = cast<PointerType>(CastOp->getType());
             SrcPTy = SrcTy->getElementType();
           }
 
-      if (((SrcPTy->isInteger() && SrcPTy != Type::Int1Ty) ||
-           isa<PointerType>(SrcPTy)) &&
-          IC.getTargetData().getTypeSize(SrcPTy) ==
-               IC.getTargetData().getTypeSize(DestPTy)) {
+      if ((SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
+          IC.getTargetData().getTypeSizeInBits(SrcPTy) ==
+               IC.getTargetData().getTypeSizeInBits(DestPTy)) {
 
         // Okay, we are casting from one integer or pointer type to another of
         // the same size.  Instead of casting the pointer before 
@@ -8202,12 +8303,9 @@ static Instruction *InstCombineStoreToCast(InstCombiner &IC, StoreInst &SI) {
         if (isa<PointerType>(CastDstTy)) {
           if (CastSrcTy->isInteger())
             opcode = Instruction::IntToPtr;
-        } else if (const IntegerType* DITy = dyn_cast<IntegerType>(CastDstTy)) {
+        } else if (isa<IntegerType>(CastDstTy)) {
           if (isa<PointerType>(SIOp0->getType()))
             opcode = Instruction::PtrToInt;
-          else if (const IntegerType* SITy = dyn_cast<IntegerType>(CastSrcTy))
-            assert(DITy->getBitWidth() == SITy->getBitWidth() &&
-                   "Illegal store instruction");
         }
         if (Constant *C = dyn_cast<Constant>(SIOp0))
           NewCast = ConstantExpr::getCast(opcode, C, CastDstTy);
@@ -8296,7 +8394,7 @@ Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
     if (!isa<UndefValue>(Val)) {
       SI.setOperand(0, UndefValue::get(Val->getType()));
       if (Instruction *U = dyn_cast<Instruction>(Val))
-        WorkList.push_back(U);  // Dropped a use.
+        AddToWorkList(U);  // Dropped a use.
       ++NumCombined;
     }
     return 0;  // Do not modify these!
@@ -8408,16 +8506,16 @@ Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
     if ((FPred == FCmpInst::FCMP_ONE || FPred == FCmpInst::FCMP_OLE ||
          FPred == FCmpInst::FCMP_OGE) && BI.getCondition()->hasOneUse()) {
       FCmpInst *I = cast<FCmpInst>(BI.getCondition());
-      std::string Name = I->getName(); I->setName("");
       FCmpInst::Predicate NewPred = FCmpInst::getInversePredicate(FPred);
-      Value *NewSCC =  new FCmpInst(NewPred, X, Y, Name, I);
+      Instruction *NewSCC = new FCmpInst(NewPred, X, Y, "", I);
+      NewSCC->takeName(I);
       // Swap Destinations and condition...
       BI.setCondition(NewSCC);
       BI.setSuccessor(0, FalseDest);
       BI.setSuccessor(1, TrueDest);
-      removeFromWorkList(I);
-      I->getParent()->getInstList().erase(I);
-      WorkList.push_back(cast<Instruction>(NewSCC));
+      RemoveFromWorkList(I);
+      I->eraseFromParent();
+      AddToWorkList(NewSCC);
       return &BI;
     }
 
@@ -8429,16 +8527,16 @@ Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
          IPred == ICmpInst::ICMP_SLE || IPred == ICmpInst::ICMP_UGE ||
          IPred == ICmpInst::ICMP_SGE) && BI.getCondition()->hasOneUse()) {
       ICmpInst *I = cast<ICmpInst>(BI.getCondition());
-      std::string Name = I->getName(); I->setName("");
       ICmpInst::Predicate NewPred = ICmpInst::getInversePredicate(IPred);
-      Value *NewSCC = new ICmpInst(NewPred, X, Y, Name, I);
+      Instruction *NewSCC = new ICmpInst(NewPred, X, Y, "", I);
+      NewSCC->takeName(I);
       // Swap Destinations and condition...
       BI.setCondition(NewSCC);
       BI.setSuccessor(0, FalseDest);
       BI.setSuccessor(1, TrueDest);
-      removeFromWorkList(I);
-      I->getParent()->getInstList().erase(I);
-      WorkList.push_back(cast<Instruction>(NewSCC));
+      RemoveFromWorkList(I);
+      I->eraseFromParent();;
+      AddToWorkList(NewSCC);
       return &BI;
     }
 
@@ -8455,7 +8553,7 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
           SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
                                                 AddRHS));
         SI.setOperand(0, I->getOperand(0));
-        WorkList.push_back(I);
+        AddToWorkList(I);
         return &SI;
       }
   }
@@ -8467,7 +8565,7 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
 static bool CheapToScalarize(Value *V, bool isConstant) {
   if (isa<ConstantAggregateZero>(V)) 
     return true;
-  if (ConstantPacked *C = dyn_cast<ConstantPacked>(V)) {
+  if (ConstantVector *C = dyn_cast<ConstantVector>(V)) {
     if (isConstant) return true;
     // If all elts are the same, we can extract.
     Constant *Op0 = C->getOperand(0);
@@ -8500,8 +8598,10 @@ static bool CheapToScalarize(Value *V, bool isConstant) {
   return false;
 }
 
-/// getShuffleMask - Read and decode a shufflevector mask.  It turns undef
-/// elements into values that are larger than the #elts in the input.
+/// Read and decode a shufflevector mask.
+///
+/// It turns undef elements into values that are larger than the number of
+/// elements in the input.
 static std::vector<unsigned> getShuffleMask(const ShuffleVectorInst *SVI) {
   unsigned NElts = SVI->getType()->getNumElements();
   if (isa<ConstantAggregateZero>(SVI->getOperand(2)))
@@ -8510,7 +8610,7 @@ static std::vector<unsigned> getShuffleMask(const ShuffleVectorInst *SVI) {
     return std::vector<unsigned>(NElts, 2*NElts);
 
   std::vector<unsigned> Result;
-  const ConstantPacked *CP = cast<ConstantPacked>(SVI->getOperand(2));
+  const ConstantVector *CP = cast<ConstantVector>(SVI->getOperand(2));
   for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
     if (isa<UndefValue>(CP->getOperand(i)))
       Result.push_back(NElts*2);  // undef -> 8
@@ -8523,8 +8623,8 @@ static std::vector<unsigned> getShuffleMask(const ShuffleVectorInst *SVI) {
 /// value is already around as a register, for example if it were inserted then
 /// extracted from the vector.
 static Value *FindScalarElement(Value *V, unsigned EltNo) {
-  assert(isa<PackedType>(V->getType()) && "Not looking at a vector?");
-  const PackedType *PTy = cast<PackedType>(V->getType());
+  assert(isa<VectorType>(V->getType()) && "Not looking at a vector?");
+  const VectorType *PTy = cast<VectorType>(V->getType());
   unsigned Width = PTy->getNumElements();
   if (EltNo >= Width)  // Out of range access.
     return UndefValue::get(PTy->getElementType());
@@ -8533,7 +8633,7 @@ static Value *FindScalarElement(Value *V, unsigned EltNo) {
     return UndefValue::get(PTy->getElementType());
   else if (isa<ConstantAggregateZero>(V))
     return Constant::getNullValue(PTy->getElementType());
-  else if (ConstantPacked *CP = dyn_cast<ConstantPacked>(V))
+  else if (ConstantVector *CP = dyn_cast<ConstantVector>(V))
     return CP->getOperand(EltNo);
   else if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
     // If this is an insert to a variable element, we don't know what it is.
@@ -8573,7 +8673,7 @@ Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
   if (isa<ConstantAggregateZero>(EI.getOperand(0)))
     return ReplaceInstUsesWith(EI, Constant::getNullValue(EI.getType()));
   
-  if (ConstantPacked *C = dyn_cast<ConstantPacked>(EI.getOperand(0))) {
+  if (ConstantVector *C = dyn_cast<ConstantVector>(EI.getOperand(0))) {
     // If packed val is constant with uniform operands, replace EI
     // with that operand
     Constant *op0 = C->getOperand(0);
@@ -8673,7 +8773,7 @@ static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
                                          std::vector<Constant*> &Mask) {
   assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() &&
          "Invalid CollectSingleShuffleElements");
-  unsigned NumElts = cast<PackedType>(V->getType())->getNumElements();
+  unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 
   if (isa<UndefValue>(V)) {
     Mask.assign(NumElts, UndefValue::get(Type::Int32Ty));
@@ -8741,10 +8841,10 @@ static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
 /// that computes V and the LHS value of the shuffle.
 static Value *CollectShuffleElements(Value *V, std::vector<Constant*> &Mask,
                                      Value *&RHS) {
-  assert(isa<PackedType>(V->getType()) && 
+  assert(isa<VectorType>(V->getType()) && 
          (RHS == 0 || V->getType() == RHS->getType()) &&
          "Invalid shuffle!");
-  unsigned NumElts = cast<PackedType>(V->getType())->getNumElements();
+  unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 
   if (isa<UndefValue>(V)) {
     Mask.assign(NumElts, UndefValue::get(Type::Int32Ty));
@@ -8844,7 +8944,7 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
         } 
         Mask[InsertedIdx] = ConstantInt::get(Type::Int32Ty, ExtractedIdx);
         return new ShuffleVectorInst(EI->getOperand(0), VecOp,
-                                     ConstantPacked::get(Mask));
+                                     ConstantVector::get(Mask));
       }
       
       // If this insertelement isn't used by some other insertelement, turn it
@@ -8855,7 +8955,7 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
         Value *LHS = CollectShuffleElements(&IE, Mask, RHS);
         if (RHS == 0) RHS = UndefValue::get(LHS->getType());
         // We now have a shuffle of LHS, RHS, Mask.
-        return new ShuffleVectorInst(LHS, RHS, ConstantPacked::get(Mask));
+        return new ShuffleVectorInst(LHS, RHS, ConstantVector::get(Mask));
       }
     }
   }
@@ -8896,7 +8996,7 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
         else
           Elts.push_back(ConstantInt::get(Type::Int32Ty, Mask[i]));
       }
-      SVI.setOperand(2, ConstantPacked::get(Elts));
+      SVI.setOperand(2, ConstantVector::get(Elts));
     }
   }
   
@@ -8924,7 +9024,7 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
     }
     SVI.setOperand(0, SVI.getOperand(1));
     SVI.setOperand(1, UndefValue::get(RHS->getType()));
-    SVI.setOperand(2, ConstantPacked::get(Elts));
+    SVI.setOperand(2, ConstantVector::get(Elts));
     LHS = SVI.getOperand(0);
     RHS = SVI.getOperand(1);
     MadeChange = true;
@@ -8979,21 +9079,16 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
         }
         return new ShuffleVectorInst(LHSSVI->getOperand(0),
                                      LHSSVI->getOperand(1),
-                                     ConstantPacked::get(Elts));
+                                     ConstantVector::get(Elts));
       }
     }
   }
-  
+
   return MadeChange ? &SVI : 0;
 }
 
 
 
-void InstCombiner::removeFromWorkList(Instruction *I) {
-  WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
-                 WorkList.end());
-}
-
 
 /// TryToSinkInstruction - Try to move the specified instruction from its
 /// current block into the beginning of DestBlock, which can only happen if it's
@@ -9026,32 +9121,6 @@ static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
   return true;
 }
 
-/// OptimizeConstantExpr - Given a constant expression and target data layout
-/// information, symbolically evaluate the constant expr to something simpler
-/// if possible.
-static Constant *OptimizeConstantExpr(ConstantExpr *CE, const TargetData *TD) {
-  if (!TD) return CE;
-  
-  Constant *Ptr = CE->getOperand(0);
-  if (CE->getOpcode() == Instruction::GetElementPtr && Ptr->isNullValue() &&
-      cast<PointerType>(Ptr->getType())->getElementType()->isSized()) {
-    // If this is a constant expr gep that is effectively computing an
-    // "offsetof", fold it into 'cast int Size to T*' instead of 'gep 0, 0, 12'
-    bool isFoldableGEP = true;
-    for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
-      if (!isa<ConstantInt>(CE->getOperand(i)))
-        isFoldableGEP = false;
-    if (isFoldableGEP) {
-      std::vector<Value*> Ops(CE->op_begin()+1, CE->op_end());
-      uint64_t Offset = TD->getIndexedOffset(Ptr->getType(), Ops);
-      Constant *C = ConstantInt::get(TD->getIntPtrType(), Offset);
-      return ConstantExpr::getIntToPtr(C, CE->getType());
-    }
-  }
-  
-  return CE;
-}
-
 
 /// AddReachableCodeToWorklist - Walk the function in depth-first order, adding
 /// all reachable code to the worklist.
@@ -9063,11 +9132,11 @@ static Constant *OptimizeConstantExpr(ConstantExpr *CE, const TargetData *TD) {
 /// whose condition is a known constant, we only visit the reachable successors.
 ///
 static void AddReachableCodeToWorklist(BasicBlock *BB, 
-                                       std::set<BasicBlock*> &Visited,
-                                       std::vector<Instruction*> &WorkList,
+                                       SmallPtrSet<BasicBlock*, 64> &Visited,
+                                       InstCombiner &IC,
                                        const TargetData *TD) {
   // We have now visited this block!  If we've already been here, bail out.
-  if (!Visited.insert(BB).second) return;
+  if (!Visited.insert(BB)) return;
     
   for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
     Instruction *Inst = BBI++;
@@ -9081,9 +9150,7 @@ static void AddReachableCodeToWorklist(BasicBlock *BB,
     }
     
     // ConstantProp instruction if trivially constant.
-    if (Constant *C = ConstantFoldInstruction(Inst)) {
-      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
-        C = OptimizeConstantExpr(CE, TD);
+    if (Constant *C = ConstantFoldInstruction(Inst, TD)) {
       DOUT << "IC: ConstFold to: " << *C << " from: " << *Inst;
       Inst->replaceAllUsesWith(C);
       ++NumConstProp;
@@ -9091,7 +9158,7 @@ static void AddReachableCodeToWorklist(BasicBlock *BB,
       continue;
     }
     
-    WorkList.push_back(Inst);
+    IC.AddToWorkList(Inst);
   }
 
   // Recursively visit successors.  If this is a branch or switch on a constant,
@@ -9100,8 +9167,7 @@ static void AddReachableCodeToWorklist(BasicBlock *BB,
   if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
     if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
       bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
-      AddReachableCodeToWorklist(BI->getSuccessor(!CondVal), Visited, WorkList,
-                                 TD);
+      AddReachableCodeToWorklist(BI->getSuccessor(!CondVal), Visited, IC, TD);
       return;
     }
   } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
@@ -9109,30 +9175,33 @@ static void AddReachableCodeToWorklist(BasicBlock *BB,
       // See if this is an explicit destination.
       for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i)
         if (SI->getCaseValue(i) == Cond) {
-          AddReachableCodeToWorklist(SI->getSuccessor(i), Visited, WorkList,TD);
+          AddReachableCodeToWorklist(SI->getSuccessor(i), Visited, IC, TD);
           return;
         }
       
       // Otherwise it is the default destination.
-      AddReachableCodeToWorklist(SI->getSuccessor(0), Visited, WorkList, TD);
+      AddReachableCodeToWorklist(SI->getSuccessor(0), Visited, IC, TD);
       return;
     }
   }
   
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
-    AddReachableCodeToWorklist(TI->getSuccessor(i), Visited, WorkList, TD);
+    AddReachableCodeToWorklist(TI->getSuccessor(i), Visited, IC, TD);
 }
 
-bool InstCombiner::runOnFunction(Function &F) {
+bool InstCombiner::DoOneIteration(Function &F, unsigned Iteration) {
   bool Changed = false;
   TD = &getAnalysis<TargetData>();
+  
+  DEBUG(DOUT << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
+             << F.getNameStr() << "\n");
 
   {
     // Do a depth-first traversal of the function, populate the worklist with
     // the reachable instructions.  Ignore blocks that are not reachable.  Keep
     // track of which blocks we visit.
-    std::set<BasicBlock*> Visited;
-    AddReachableCodeToWorklist(F.begin(), Visited, WorkList, TD);
+    SmallPtrSet<BasicBlock*, 64> Visited;
+    AddReachableCodeToWorklist(F.begin(), Visited, *this, TD);
 
     // Do a quick scan over the function.  If we find any blocks that are
     // unreachable, remove any instructions inside of them.  This prevents
@@ -9153,9 +9222,9 @@ bool InstCombiner::runOnFunction(Function &F) {
       }
   }
 
-  while (!WorkList.empty()) {
-    Instruction *I = WorkList.back();  // Get an instruction from the worklist
-    WorkList.pop_back();
+  while (!Worklist.empty()) {
+    Instruction *I = RemoveOneFromWorkList();
+    if (I == 0) continue;  // skip null values.
 
     // Check to see if we can DCE the instruction.
     if (isInstructionTriviallyDead(I)) {
@@ -9167,14 +9236,12 @@ bool InstCombiner::runOnFunction(Function &F) {
       DOUT << "IC: DCE: " << *I;
 
       I->eraseFromParent();
-      removeFromWorkList(I);
+      RemoveFromWorkList(I);
       continue;
     }
 
     // Instruction isn't dead, see if we can constant propagate it.
-    if (Constant *C = ConstantFoldInstruction(I)) {
-      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C))
-        C = OptimizeConstantExpr(CE, TD);
+    if (Constant *C = ConstantFoldInstruction(I, TD)) {
       DOUT << "IC: ConstFold to: " << *C << " from: " << *I;
 
       // Add operands to the worklist.
@@ -9183,7 +9250,7 @@ bool InstCombiner::runOnFunction(Function &F) {
 
       ++NumConstProp;
       I->eraseFromParent();
-      removeFromWorkList(I);
+      RemoveFromWorkList(I);
       continue;
     }
 
@@ -9222,12 +9289,11 @@ bool InstCombiner::runOnFunction(Function &F) {
         I->replaceAllUsesWith(Result);
 
         // Push the new instruction and any users onto the worklist.
-        WorkList.push_back(Result);
+        AddToWorkList(Result);
         AddUsersToWorkList(*Result);
 
-        // Move the name to the new instruction first...
-        std::string OldName = I->getName(); I->setName("");
-        Result->setName(OldName);
+        // Move the name to the new instruction first.
+        Result->takeName(I);
 
         // Insert the new instruction into the basic block...
         BasicBlock *InstParent = I->getParent();
@@ -9241,13 +9307,11 @@ bool InstCombiner::runOnFunction(Function &F) {
 
         // Make sure that we reprocess all operands now that we reduced their
         // use counts.
-        for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
-          if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
-            WorkList.push_back(OpI);
+        AddUsesToWorkList(*I);
 
         // Instructions can end up on the worklist more than once.  Make sure
         // we do not process an instruction that has been deleted.
-        removeFromWorkList(I);
+        RemoveFromWorkList(I);
 
         // Erase the old instruction.
         InstParent->getInstList().erase(I);
@@ -9259,26 +9323,38 @@ bool InstCombiner::runOnFunction(Function &F) {
         if (isInstructionTriviallyDead(I)) {
           // Make sure we process all operands now that we are reducing their
           // use counts.
-          for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
-            if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
-              WorkList.push_back(OpI);
+          AddUsesToWorkList(*I);
 
           // Instructions may end up in the worklist more than once.  Erase all
           // occurrences of this instruction.
-          removeFromWorkList(I);
+          RemoveFromWorkList(I);
           I->eraseFromParent();
         } else {
-          WorkList.push_back(Result);
-          AddUsersToWorkList(*Result);
+          AddToWorkList(I);
+          AddUsersToWorkList(*I);
         }
       }
       Changed = true;
     }
   }
 
+  assert(WorklistMap.empty() && "Worklist empty, but map not?");
   return Changed;
 }
 
+
+bool InstCombiner::runOnFunction(Function &F) {
+  MustPreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
+  
+  bool EverMadeChange = false;
+
+  // Iterate while there is work to do.
+  unsigned Iteration = 0;
+  while (DoOneIteration(F, Iteration++)) 
+    EverMadeChange = true;
+  return EverMadeChange;
+}
+
 FunctionPass *llvm::createInstructionCombiningPass() {
   return new InstCombiner();
 }