diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 21bb5dc..b017f91 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -1782,8 +1782,12 @@
       NewLIs.push_back(&getOrCreateInterval(NewVReg));
       for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
         MachineOperand &MO = MI->getOperand(i);
-        if (MO.isReg() && MO.getReg() == li.reg)
+        if (MO.isReg() && MO.getReg() == li.reg) {
           MO.setReg(NewVReg);
+          MO.setIsUndef();
+          if (MO.isKill())
+            MO.setIsKill(false);
+        }
       }
     }
   }
diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
index c977508..d44305f 100644
--- a/lib/CodeGen/MachineInstr.cpp
+++ b/lib/CodeGen/MachineInstr.cpp
@@ -120,7 +120,7 @@
 /// the specified value.  If an operand is known to be an register already,
 /// the setReg method should be used.
 void MachineOperand::ChangeToRegister(unsigned Reg, bool isDef, bool isImp,
-                                      bool isKill, bool isDead) {
+                                      bool isKill, bool isDead, bool isUndef) {
   // If this operand is already a register operand, use setReg to update the 
   // register's use/def lists.
   if (isReg()) {
@@ -143,6 +143,7 @@
   IsImp = isImp;
   IsKill = isKill;
   IsDead = isDead;
+  IsUndef = isUndef;
   IsEarlyClobber = false;
   SubReg = 0;
 }
@@ -206,11 +207,11 @@
         OS << "%mreg" << getReg();
     }
 
-    if (getSubReg() != 0) {
+    if (getSubReg() != 0)
       OS << ':' << getSubReg();
-    }
 
-    if (isDef() || isKill() || isDead() || isImplicit() || isEarlyClobber()) {
+    if (isDef() || isKill() || isDead() || isImplicit() || isUndef() ||
+        isEarlyClobber()) {
       OS << '<';
       bool NeedComma = false;
       if (isImplicit()) {
@@ -224,10 +225,15 @@
         OS << "def";
         NeedComma = true;
       }
-      if (isKill() || isDead()) {
+      if (isKill() || isDead() || isUndef()) {
         if (NeedComma) OS << ',';
         if (isKill())  OS << "kill";
         if (isDead())  OS << "dead";
+        if (isUndef()) {
+          if (isKill() || isDead())
+            OS << ',';
+          OS << "undef";
+        }
       }
       OS << '>';
     }
diff --git a/lib/CodeGen/RegAllocLinearScan.cpp b/lib/CodeGen/RegAllocLinearScan.cpp
index 41a42fd..2caa2f9 100644
--- a/lib/CodeGen/RegAllocLinearScan.cpp
+++ b/lib/CodeGen/RegAllocLinearScan.cpp
@@ -905,6 +905,17 @@
     DOUT <<  tri_->getName(physReg) << '\n';
     // Note the register is not really in use.
     vrm_->assignVirt2Phys(cur->reg, physReg);
+    // Since the register allocator is allowed to assign this virtual register
+    // physical register that overlaps other live intervals. Mark these
+    // operands as "Undef" which means later passes, e.g. register scavenger
+    // can ignore them.
+    for (MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(cur->reg),
+           RE = mri_->reg_end(); RI != RE; ++RI) {
+      MachineOperand &MO = RI.getOperand();
+      MO.setIsUndef();
+      if (MO.isKill())
+        MO.setIsKill(false);
+    }
     return;
   }
 
diff --git a/lib/CodeGen/RegisterScavenging.cpp b/lib/CodeGen/RegisterScavenging.cpp
index 3feb92f..7d8e3af 100644
--- a/lib/CodeGen/RegisterScavenging.cpp
+++ b/lib/CodeGen/RegisterScavenging.cpp
@@ -36,7 +36,7 @@
   bool SeenSuperDef = false;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg())
+    if (!MO.isReg() || MO.isUndef())
       continue;
     if (TRI->isSuperRegister(SubReg, MO.getReg())) {
       if (MO.isUse())
@@ -57,28 +57,22 @@
 }
 
 /// setUsed - Set the register and its sub-registers as being used.
-void RegScavenger::setUsed(unsigned Reg, bool ImpDef) {
+void RegScavenger::setUsed(unsigned Reg) {
   RegsAvailable.reset(Reg);
-  ImplicitDefed[Reg] = ImpDef;
 
   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
-       unsigned SubReg = *SubRegs; ++SubRegs) {
+       unsigned SubReg = *SubRegs; ++SubRegs)
     RegsAvailable.reset(SubReg);
-    ImplicitDefed[SubReg] = ImpDef;
-  }
 }
 
 /// setUnused - Set the register and its sub-registers as being unused.
 void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
   RegsAvailable.set(Reg);
-  ImplicitDefed.reset(Reg);
 
   for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
        unsigned SubReg = *SubRegs; ++SubRegs)
-    if (!RedefinesSuperRegPart(MI, Reg, TRI)) {
+    if (!RedefinesSuperRegPart(MI, Reg, TRI))
       RegsAvailable.set(SubReg);
-      ImplicitDefed.reset(SubReg);
-    }
 }
 
 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
@@ -94,7 +88,6 @@
   if (!MBB) {
     NumPhysRegs = TRI->getNumRegs();
     RegsAvailable.resize(NumPhysRegs);
-    ImplicitDefed.resize(NumPhysRegs);
 
     // Create reserved registers bitvector.
     ReservedRegs = TRI->getReservedRegs(MF);
@@ -113,7 +106,6 @@
   ScavengeRestore = NULL;
   CurrDist = 0;
   DistanceMap.clear();
-  ImplicitDefed.reset();
 
   // All registers started out unused.
   RegsAvailable.set();
@@ -195,15 +187,13 @@
     ScavengeRestore = NULL;
   }
 
-  bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF;
-
   // Separate register operands into 3 classes: uses, defs, earlyclobbers.
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.getReg() == 0)
+    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
       continue;
     if (MO.isUse())
       UseMOs.push_back(std::make_pair(&MO,i));
@@ -221,14 +211,7 @@
 
     assert(isUsed(Reg) && "Using an undefined register!");
 
-    // Kill of implicit_def defined registers are ignored. e.g.
-    // entry: 0x2029ab8, LLVM BB @0x1b06080, ID#0:
-    // Live Ins: %R0
-    //  %R0<def> = IMPLICIT_DEF
-    //  %R0<def> = IMPLICIT_DEF
-    //  STR %R0<kill>, %R0, %reg0, 0, 14, %reg0, Mem:ST(4,4) [0x1b06510 + 0]
-    //  %R1<def> = LDR %R0, %reg0, 24, 14, %reg0, Mem:LD(4,4) [0x1b065bc + 0]
-    if (MO.isKill() && !isReserved(Reg) && !isImplicitlyDefined(Reg)) {
+    if (MO.isKill() && !isReserved(Reg)) {
       KillRegs.set(Reg);
 
       // Mark sub-registers as used.
@@ -274,10 +257,9 @@
     // Implicit def is allowed to "re-define" any register. Similarly,
     // implicitly defined registers can be clobbered.
     assert((isReserved(Reg) || isUnused(Reg) ||
-            IsImpDef || isImplicitlyDefined(Reg) ||
             isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
            "Re-defining a live register!");
-    setUsed(Reg, IsImpDef);
+    setUsed(Reg);
   }
 }
 
@@ -297,7 +279,7 @@
   SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI->getOperand(i);
-    if (!MO.isReg() || MO.getReg() == 0)
+    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
       continue;
     if (MO.isUse())
       UseMOs.push_back(std::make_pair(&MO,i));
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
index e372b5b..7926339 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGSDNodesEmit.cpp
@@ -617,7 +617,7 @@
         for (; NumVals; --NumVals, ++i) {
           unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
           MI->addOperand(MachineOperand::CreateReg(Reg, true, false, false, 
-                                                   false, 0, true));
+                                                   false, false, true));
         }
         break;
       case 1:  // Use of register.
diff --git a/lib/CodeGen/VirtRegRewriter.cpp b/lib/CodeGen/VirtRegRewriter.cpp
index bd6584a..bbf1e24 100644
--- a/lib/CodeGen/VirtRegRewriter.cpp
+++ b/lib/CodeGen/VirtRegRewriter.cpp
@@ -356,7 +356,7 @@
                             SmallVector<unsigned, 2> *KillRegs = NULL) {
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI.getOperand(i);
-    if (!MO.isReg() || !MO.isUse() || !MO.isKill())
+    if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
       continue;
     unsigned Reg = MO.getReg();
     if (TargetRegisterInfo::isVirtualRegister(Reg))
@@ -390,12 +390,12 @@
   MachineOperand *DefOp = NULL;
   for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
     MachineOperand &MO = DefMI->getOperand(i);
-    if (MO.isReg() && MO.isDef()) {
-      if (MO.getReg() == Reg)
-        DefOp = &MO;
-      else if (!MO.isDead())
-        HasLiveDef = true;
-    }
+    if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
+      continue;
+    if (MO.getReg() == Reg)
+      DefOp = &MO;
+    else if (!MO.isDead())
+      HasLiveDef = true;
   }
   if (!DefOp)
     return false;
@@ -430,7 +430,7 @@
                         std::vector<MachineOperand*> &KillOps) {
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     MachineOperand &MO = MI.getOperand(i);
-    if (!MO.isReg() || !MO.isUse())
+    if (!MO.isReg() || !MO.isUse() || MO.isUndef())
       continue;
     unsigned Reg = MO.getReg();
     if (Reg == 0)
@@ -1289,8 +1289,7 @@
           if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
             MachineInstr *DeadDef = PrevMII;
             if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
-              // FIXME: This assumes a remat def does not have side
-              // effects.
+              // FIXME: This assumes a remat def does not have side effects.
               VRM.RemoveMachineInstrFromMaps(DeadDef);
               MBB.erase(DeadDef);
               ++NumDRM;
@@ -1569,6 +1568,8 @@
         if (MO.isImplicit())
           // If the virtual register is implicitly defined, emit a implicit_def
           // before so scavenger knows it's "defined".
+          // FIXME: This is a horrible hack done the by register allocator to
+          // remat a definition with virtual register operand.
           VirtUseOps.insert(VirtUseOps.begin(), i);
         else
           VirtUseOps.push_back(i);
@@ -1595,6 +1596,7 @@
           MI.getOperand(i).setReg(RReg);
           MI.getOperand(i).setSubReg(0);
           if (VRM.isImplicitlyDefined(VirtReg))
+            // FIXME: Is this needed?
             BuildMI(MBB, &MI, MI.getDebugLoc(),
                     TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
           continue;
@@ -1604,22 +1606,16 @@
         if (!MO.isUse())
           continue;  // Handle defs in the loop below (handle use&def here though)
 
-        bool AvoidReload = false;
-        if (LIs->hasInterval(VirtReg)) {
-          LiveInterval &LI = LIs->getInterval(VirtReg);
-          if (!LI.liveAt(LIs->getUseIndex(LI.beginNumber())))
-            // Must be defined by an implicit def. It should not be spilled. Note,
-            // this is for correctness reason. e.g.
-            // 8   %reg1024<def> = IMPLICIT_DEF
-            // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
-            // The live range [12, 14) are not part of the r1024 live interval since
-            // it's defined by an implicit def. It will not conflicts with live
-            // interval of r1025. Now suppose both registers are spilled, you can
-            // easily see a situation where both registers are reloaded before
-            // the INSERT_SUBREG and both target registers that would overlap.
-            AvoidReload = true;
-        }
-
+        bool AvoidReload = MO.isUndef();
+        // Check if it is defined by an implicit def. It should not be spilled.
+        // Note, this is for correctness reason. e.g.
+        // 8   %reg1024<def> = IMPLICIT_DEF
+        // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
+        // The live range [12, 14) are not part of the r1024 live interval since
+        // it's defined by an implicit def. It will not conflicts with live
+        // interval of r1025. Now suppose both registers are spilled, you can
+        // easily see a situation where both registers are reloaded before
+        // the INSERT_SUBREG and both target registers that would overlap.
         bool DoReMat = VRM.isReMaterialized(VirtReg);
         int SSorRMId = DoReMat
           ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);